Renesys Corp

Presentations

Leiden workshops on Global Internet Measurements, Analysis and Modeling

Workshop The Global Internet: Measurement, Modeling and Analysis

Monday Sept 11 - Friday Sept 15, 2000
Lorentz Center, Leiden University, Leiden, the Netherlands

• Program, Speakers' Viewgraphs and Links
• Abstracts
• Local Info
• Workshop Info

Workshop Program, Viewgraphs and Links

Talk Abstracts

• Reka Albert, Notre Dame Univ.

  Emergence of Scaling in Complex Networks

  A common property of many large networks, including the Internet, is that their vertex connectivities follow a scale-free power-law distribution. This feature is a consequence of two generic mechanisms shared by many networks: networks expand continuously by the addition of new vertices, and new vertices attach preferentially to already well connected sites. A model based on these two ingredients reproduces the observed stationary scale-free distributions, indicating that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems. The topological inhomogeneities of these scale-free networks have important consequences on their error and attack tolerance.

• Paul Barford, Boston U & U. Wisconsin

  The performance of wide area services running over the Internet - such as the World Wide Web -- can be highly variable. Users are often frustrated by long delays in accessing Web pages; yet, the root causes of delays in the Web are not easy to discover. In this talk I will describe the difficulties in pinpointing delays in the Web, and a project that addresses these difficulties. The Wide Area Web Measurement (WAWM) project is developing a laboratory for studying and analyzing the performance of the Web, using synthetic workload generation and an infrastructure distributed across the Internet. Key components of this project are the accurate generation of representative Web workloads and an analysis technique for pinpointing the sources of delay. I will describe our methods for addressing each of these in the talk.

• Bruno Codenotti, Pisa

  A Tutorial on Small Worlds Networks

  A survey talk about the "small worlds" nework models and Kleinberg's recent results.

• George Cybenko, Dartmouth

  Modeling Web content dynamics

  Unlike most traditional library content, web content changes. The changes can be large or small, at regular or irregular time intervals. We present an analytic model for describing the statistical rate at which web pages change. We will present data on over 2 million web pages that we monitored for almost a year and apply the model to that data. This allows us to estimate the rates of revisits to web pages so that web search engines can be optimally up-to-date with respect to concrete performance metrics.

• John Doyle, Caltech

  Robustness and complexity of the Internet

  We'll place the Internet in the broader context of complex networks using extensions of theory from controls, dynamical systems, and information theory, and compare the robustness and performance properties of the Internet with other networks and complex multiscale systems, such as the power grid, air transportation, highways, turbulent shear flows, biological signal transduction and gene regulation, forest fires, etc.

• Avi Freedman, Akamai

  Distributed BGP Prefix Churn Analysis Project

  In an attempt to better route around poorly performing links, Akamai has begun correlating BGP churn as seen from over 200 eBGP multi-hop feeds against performance data. We'll present preliminary data showing a correlation between a prefix churning from within a remote AS, and future performance measurements showing packet loss and reduced throughput. We will also discuss the future application of this data for real-time debugging and real-time and forensic analysis.

  There has been concern among those in the Internet modeling community about the behavior of Akamai's (re-)routing methods. We will present information about how Akamai in particular, and other Content Distribution Networks and IP networks control traffic flow.

• Erol Gelenbe, U. Central Florida

  Towards Networks with Cognitive Packets

  In the Infinite Internet, routing intelligence should move to the users and packets. We will describe a simple scheme we and test-bed (Cognitive Packet Network) with neural net based self-routing packets. We present analytical best and worst case performance estimates using G-networks, and average behavior based on simulation and measurement.

• Ramesh Govindan, USC/ISI

  Topology Discovery and Routing Policy Impact

  This talk will describe practical Internet topology discovery techniques. It will also assess the impact that routing policy has on Internet paths.

• Tim Griffin, AT&T Labs-Research

  The "Stable Paths Problem" as a model of BGP routing

  Dynamic routing protocols such as RIP and OSPF essentially implement distributed algorithms for solving the Shortest Paths Problem. Can BGP be viewed as a distributed algorithm for solving some simple underlying problem? This talk says "yes" and presents the Stable Paths Problem.

• Sugih Jamin, U. Michigan

  On the Use of Power-Law Random Graph to Model Internet Topology

  Power-law random graph (PLRG), a random graph in which node outdegree distribution follows a power-law, has recently been proposed as a model for Internet topology. In this talk, I present some of our results in using PLRG to model the Internet.

• Frank Kelly, Cambridge

  Congestion control: fairness, pricing and stability

  This talk will discuss the stability and fairness of congestion control algorithms, and how a shadow price may be defined on the sample path of a queueing process. The aim will be to understand how microscopic packet level processes, of an apparently crude and statistical nature, may lead to sophisticated macroscopic behaviour interpretable as the global optimization of a large-scale network. http://www.statslab.cam.ac.uk/~frank/

• Craig Labovitz, Microsoft Research

  Understanding the Large-Scale Dynamics of Internet Routing Protocols

  In this talk, we will explore many of the myths and conventional wisdom about Internet routing. Based on several years of experimental Internet infrastructure measurements, we will demonstrate that Internet routing does not posses many of its traditionally assumed capabilities, including fast re-routing after failures, and improved fault-tolerance through multi-homing. Finally, we will provide insight into both the origins and impact of routing path changes in the Internet.

• David Nicol, Dartmouth

  Fluid Modeling of TCP

  This talk considers how to formulate a model of TCP, assuming a fluid-based description of traffic flow. We point out that the central problems are: 1) determining whether smoothing out variability at a short time scale can be done without loosing essential behavioral characteristics; 2) formulating a model of switching that operates at the same time-scale as fluid-based TCP agents.

• Andy Ogielski, Renesys

  Modeling & simulations of spatio-temporal Internet dynamics

  Measurement and analysis of simulated multi-domain internetworks with tens or hundreds of thousands of multiprotocol hosts and routers poses problems similar to those arising in real large networks: protocol validation, scalable database-based model configuration, scalable distributed monitoring infrastructure, not to mention scalable performance. I will discuss the SSFNet project, describing how we solved such scalability problems, how the package is used in the studies of interdomain routing dynamics jointly with measurement-based workload generation, and what we'll do next. The SSFNet software (including some large models) is available from www.ssfnet.org.

• Maarten van Steen, Vrije U.

  On differentiating distribution strategies for Internet applications

  To attain scalability in large-scale Internet applications such as the Web, it is necessary to provide mechanisms that allow flexible co-existence and interoperability of a myriad of distribution strategies. In this presentation, I will show, based on empirical data, why it makes sense to differentiate strategies, and show how it can be supported in reality. While doing so, I will touch upon the problem of gathering real-world data for validating research in wide-area systems.

• Sergio Valverde, U. Poli.

  Catalunya Complexity in Computer Networks

  Computer networks are one of the best examples of human-made complex systems. Internet dynamics in particular seem to display some of the characteristic features of complex systems close to critical points: optimal information transfer, high unpredictability and self-similar behavior. We have explored this problem by using simulation models of Internet traffic dynamics that exhibit some of the well-known features of real traffic when poised close to phase transitions. It suggests that optimal traffic is obtained close to criticality and thus optimality is linked with high unpredictability.

• Walter Willinger, AT&T Labs-Research

  Abstract not available.

Local Information

Lorentz Center is in Leiden, 20 minutes from Amsterdam Schiphol airport. The Center provides the participants with office space, and other conveniences. See their website for more information.

Directions to Lorentz Center

Local arrangements and help: Workshop coordinator: Ms. Kirsten Kol, phone +31-71-527 5837. Fax number of the Lorentz Center: +31-71-527 5415

Workshop Information

Organizers: George Cybenko (Dartmouth College) and Andy Ogielski (Renesys Corporation).

Workshop Format: In-depth discussions of the latest research leading towards new understanding of the spatial structure, dynamics and evolution of the global Internet:

global Internet topology (discovery, analysis, evolution),
global Internet dynamics (traffic, routing dynamics, the web),
global Internet models, analytic and simulations,

with emphasis on scaling behaviors, emergent dynamic phenomena, and scalability of performance. The focus will be equally on empirical data, and on new concepts in modeling and analysis.

The speakers will give approximately one-hour lectures, each followed by a free discussion. We'll be flexible with timing of the discussion periods to make sure that hot (or hotly disputed) topics get ample time.

The workshop size is limited to approximately 30 participants in order to promote intensive discussions and collaborative work.

Last updated Sept 24, 2000. Andy T. Ogielski