Colloquium

Due to the Internet structure and routing the only way to map its topology is by having measurement presence in almost every corner of the Internet. Managing thousands of measurement boxes is impractical, thus, we sugget instead a light-weight software measurement agent to be downloaded by volunteers around the world. The DIMES agent can be executed on every PC (and in the future even smaller devices, like PDAs) and enables us to map the Internet and track its evolution in time in several levels of granularity from the fine router level to the coarse Autonomous System (AS)level. Currently, DIMES has over 4300 installations in the 75 nations around the world, which produce over 5 million measurements a day.

The talk will describe the rational behind DIMES, and explore some of our results, at the AS, router, and IP level. We will also describe our vision to build an Internet evolution model that takes into account external stimuli like economic growth, and show some example of the strong connection between the Internet structure and world economics.

This tutorial will shed light on the art and the science of managing big IP networks, such as tier 1 ISPs. It consists of four parts: (i) architecture of a typical tier-1 service provider network, and operational challenges associated with running such networks; (ii) detailed description of various management and operational tasks; (iii) a case study of supporting an emerging application, VoIP; and (iv) research directions.

We describe the architecture of typical tier-1 service provider networks, in terms of scale and diversity of equipment, protocols and services, and show how these factors make management and operations of these networks a challenging task. We then discuss the key tasks of network operations: customer provisioning and care, network care, traffic engineering, network architecture and design, and security. We describe each task in detail, and how research and innovation in systems and tools fit in. We then consider the challenges of introducing new applications with VoIP as an example. Finally, we discuss challenges and areas where further research and innovation are needed, including automation of operational tasks, managing the network as a whole rather than on a box by box basis, gauging the impact of network activities on customer performance, and scheduling of maintenance activities in a seamless fashion.

Biographies

Aman Shaikh is a Technical Specialist at AT&T Labs (Research). He has published several papers on routing and network management. He has been responsible for design, development and implementation of an OSPF monitor which is deployed in enterprise and service provider networks. He is also actively involed in various activities related to innovation and realization of route monitoring and network management. Recently he spent a month at AT&T Network Operations Center (NOC) talking to several people who work "on the floor" day in day out, and watching the network operations from close quarters. This sort of interaction with Operations with a Research hat on will come through in many of the examples presented at the tutorial.

Albert Greenberg heads the Network Measurement and Engineering Dept. at AT&T Labs-Research, a group which conducts research in networking, with an emphasis on large scale IP networks and systems, and emerging Internet technologies. His research interests include Internet traffic measurement, modeling and engineering, network management, and optical networking. In collaboration with several others at AT&T Labs, he is developing a unified toolkit to manage IP networks. In recent years, he has also worked with Aman Shaikh and others at AT&T on the monitoring and management of large IP routing infrastructures. Albert has had his hands in AT&T's operational IP networks since their birth, with a focus on research on analysis, algorithms, and tools for operational network management.

The available bandwidth (avail-bw) of a network path is an important performance metric and its end-to-end estimation has recently received significant attention. Previous work focused on the estimation of the average avail-bw, ignoring the significant variability of this metric in different time scales.

In this paper, we show how to estimate a given percentile of the avail-bw distribution at a user-specified time scale. If two estimated percentiles cover the bulk of the distribution (say 10% to 90%), the user can obtain a practical estimate for the avail-bw variation range. We present two estimation techniques. The first is iterative and non-parametric, meaning that it is more appropriate for very short time scales (typically less than 100ms), or in bottlenecks with limited flow multiplexing (where the avail-bw distribution may be non-Gaussian). The second technique is parametric, because it assumes that the avail-bw follows the Gaussian distribution, and it can produce an estimate faster because it is not iterative. The two techniques have been implemented in a measurement tool called Pathvar. Pathvar can track the avail-bw variation range within 10-20%, even under non-stationary conditions. Finally, we identify four factors that play a crucial role in the variation range of the avail-bw: traffic load, number of competing flows, rate of competing flows, and of course the measurement time scale.

The combinatorial landscape is fraught with complexity. Computing optimal solutions to natural problems is often intractable, and understanding discrete systems can be difficult without the presence of richer structures to guide our intuition. When we are able to geometrize a system or to realize our combinatorial structures as part of a larger geometry, there is the potential to greatly increase our depth of understanding. This allows us to employ powerful tools and intuitions developed in fields like non-linear functional analysis, Riemannian geometry, and geometric group theory.

This talk focuses on two examples. The first involves low-distortion embeddings of finite metric spaces, and its application to algorithms and structural theorems for cuts, flows, and balanced separators in graphs. The second revolves around abstract notions of dimension and how they can be used to characterize the complexity of certain problems on metric spaces and networks. In each case, I will discuss how the techniques developed in solving computational problems have not only borrowed from known geometric tools, but have contributed back to those communities as well.

The talk is intended for a general CS audience.

Intuitively, it is clear that trust or shared taste enables a community of users to be more productive, as it allows cooperative learning and avoiding unnecessary repetition of mistakes. In this paper we develop algorithms for the users in such a community to make decisions about selecting products or resources, in a model characterized by two key features:

The quality of the products or resources may vary over time.

Some of the users in the system may be dishonest, manipulating their actions in a Byzantine manner to achieve other goals.

Such algorithms are a fundamental primitive required by applications such as reputation systems in e-commerce, personalized web search, locating resources in peer-to-peer networks, or spam filtering. Note that in all of these applications, it is essential to deal with resources whose quality changes over time (e.g. a seller on eBay may perform perfectly in some transactions but may delay or withhold delivery in others) and to deal with the presence of dishonest agents in the system (again using the eBay example, a seller may cooperate with a ``shill'' whose objective is to boost that seller's reputation).

Our problem can be viewed as unification or generalization of a number of different research frameworks, including -- Online learning theory, specifically the multi-armed bandit problem -- Collaborative filtering and recommendation

We provide algorithms that enable honest users with similar taste to dynamically adapt their choices, so that in the aggregate, their performance nearly matches that of the single best static action.

The main result in this paper is a new algorithm for trust and collaborative filtering, whose convergence time (defined, roughly, as the number of steps required to become constant-competitive) is polylogarithmic in the problem size. Previous methods suffered from a linear convergence time.

Joint work with R. Kleinberg

Despite decades of research in fault tolerance, commodity operating systems, such as Windows and Linux, continue to crash. In this talk, I will describe a new reliability subsystem for operating systems that prevents the most common cause of crashes, device driver failures, without requiring changes to drivers themselves. To date, the subsystem has been used in Linux to prevent system crashes in the presence of driver failures, recover failed drivers transparently to the OS and applications, and update drivers "on the fly" without requiring a system reboot after installation. Measurements show that the system is extremely effective at protecting the OS from driver failures, while imposing little runtime overhead.

Imagine if computers possessed the ability of small children to observe and comprehend their dynamic environment. Very young children can track moving objects, differentiate them, identify them, understand their activity, and understand their interactions with static objects and with other moving objects in the world. There are amazing benefits in coupling these basic human abilities with the unique capabilities of computers: to communicate instantly with high bandwidth; to store and index massive quantities of observations with perfect recall; to process in parallel; and to draw inferences over extremely large stores of data. These benefits have driven the increased interest in automated computer vision applications, such as intelligent visual surveillance, automated traffic analysis, quantitative experimental animal observation, and wide-area scene understanding enabling high-level computer vision research that are predicated on the ability to detect and localize certain types of objects.

This talk describes my work in Perceptual Data Mining (PDM), a bottom-up data-driven framework for bootstrapping visual intelligence in novel environments. This work is focused on developing computational analogs for basic human perception and exploiting the strengths of computers to take full advantage of these capabilities. This research has centered on the development of systems that are capable of: automatically tracking multiple objects in real-time across multiple overlapping and non-overlapping cameras in unstructured indoor and outdoor environments; automatically modeling the types of objects in a particular environment; automatically modeling the activities that these objects perform; learning patterns of the activities over extended periods of time; and detecting unusual objects or behavior. Even without supervision, this system can create a compact description of the objects and activities in an environment that enables effective query retrieval. With minimal supervision, this system can communicate and summarize the activity in an environment. More information: http://www.csail.mit.edu/~stauffer/

"Digital divide" vs."melting pot", "great liberator" vs."social stratifier". In all of the rhetoric comparing Internet use among diverse populations, remarkably little attention has been paid to the voices of the users themselves. In this talk I will discuss an on-line community designed to unite over 3000 young people from 139 countries, and the research analyzing their on-line discourse over a period of five years. The participants, aged 10 to 16, spoke many different languages and represented a wide variety of economic and cultural backgrounds. Without ever seeing each other face-to-face, and in a community almost entirely free of adult intervention, these young people traded messages, and then elected leaders to represent their community in a real-world meeting in Boston with political and industry leaders from around the world. I will discuss results from our empirical study on the linguistic style differences and language cues that predict who was elected a leader on-line. Results demonstrate the ways in which leadership and community involvement for these young people on-line takes on very different forms from that prized by adults, and from that described for young people in the face-to-face world. This lecture is part of the /@rts series which explores interrelations of new technologies and traditional practices of arts and humanities.

For more information about this lecture, /@rts the series and sponsoring organizations, please visit our website: http://www.princeton.edu/slasharts

An important, open vision problem is to automatically describe what people are doing in a sequence of video. This problem is difficult for several reasons. First, one needs to determine how many people (if any) are in each frame and estimate their configurations (where they are and what their arms and legs are doing). But finding people and localizing their limbs is hard because people (a) wear a variety of different clothes, (b) appear in a variety of poses and (c) tend to partially occlude themselves and each other. Secondly, one must sew together estimated configuration reports from across frames into a motion path; this is tricky because people can move fast and unpredictably. Finally, one must describe what each person is doing; this problem is poorly understood, not least because there is no natural or canonical set of categories into which to classify activities. In this talk I will discuss our progress on this problem. We develop a tracker that works in two stages; i t first (a) builds a model of appearance of each person in a video and then (b) tracks by detecting those models in each frame ("tracking by model-building and detection"). We then marry our tracker with a motion synthesis engine that works by re-assembling pre-recorded motion clips. The synthesis engine generates new motions that are human-like and close to the image measurements reported by the tracker. By using labeled motion clips, our synthesizer also generates activity labels for each image frame ("analysis by synthesis"). We have extensively tested our system, running it on hundreds of thousands of frames of unscripted indoor and outdoor activity, a feature-length film, and legacy sports footage.