Renesys Corp

Presentations

Leiden workshops on Global Internet Measurements, Analysis and Modeling

Multiresolution Analysis of Global Internet Measurements

Monday Sept 10 - Friday Sept 14, 2001
Lorentz Center, Leiden University, Leiden, the Netherlands

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

Workshop Program, Viewgraphs and Links

Talk Abstracts

• Abha Ahuja, Arbor Networks

  Observations on Internet Routing - an operator's perspective

  In this talk, I will be presenting some of the analysis and data from our IPMA study of BGP route convergence. I describe the instrumentation used to measure BGP behavior and the experimental results of BGP performance after failures, fail-overs and route repair. I will also describe the expected and worst-case BGP convergence behaviors and the role that provider policy plays in BGP performance. In addition, I will review some of the results from our current work on routing system scaling issues and observations of internet routing.

• Paul Barford, Boston U & U. Wisconsin

  Interdomain Traffic Analysis

  Internet traffic at the highest levels consists of flows of packets between separate administrative domains. Packet flows at this level are governed by both private administrative policy and public standardized protocols. In this talk, we will present work-in-progress that focuses on understanding Internet traffic at the interdomain level. We will present our methods as well as preliminary results showing how interdomain traffic sources, destinations and flows can be visualized and analyzed both statically and temporally. As the work matures we hope to be able to show how policy and protocol interact. The eventual goal of this work is to be able to characterize Internet traffic from a global perspective and to develop methods to better facilitate global traffic management.

• Supratik Bhattacharyya, Sprint

  Understanding Traffic Dynamics at a Backbone POP

  This talk will center around the Sprint IP Monitoring project. We have designed a passive measurement system which collects header information from every packet on OC-3, OC-12 and OC-48 links, and uses GPS synchronized clocks to accurately timestamp the packet headers. We have collected multiple full-day traces from Sprint's operational IP backbone. The talk will provide a broad outline of a number of ongoing projects that uses the data collected , but will focus on a specific project where we are studying traffic dynamics at a backbone POP.

• Olivier Bonaventure, Univ. Namur

  Implications of interdomain traffic characteristics on traffic engineering

  We study the interdomain traffic as seen by two non-transit ISP, based on a week long trace covering all the interdomain links of these ISP. Our analysis considers the relationships between the interdomain traffic and the interdomain topology. We discuss the day-to-day stability of the interdomain traffic to evaluate the feasibility of interdomain traffic engineering. Then, we study the variability of the interdomain flows for several aggregation levels (prefix, AS and sink tree) and with respect to the interdomain topology seen by BGP. We then discuss the implications of these traffic characteristics on the traffic engineering and interdomain routing.

  This is joint work with Steve Uhlig.

• Andre Broido and KC Claffy, CAIDA

  Internet Topology: connectivity of IP graphs

  In this paper we introduce a framework for analyzing local properties of Internet connectivity. We compare BGP and probed topology data, finding that currently probed topology data yields much denser coverage of AS-level connectivity. We describe data acquisition and construction of several IP-level graphs derived from a collection of 220M skitter traceroutes. We find that a graph consisting of IP nodes and links contains 90.5% of its 629K nodes in the acyclic subgraph. In particular, 55% of the IP nodes are in trees. Full bidirectional connectivity is observed for a giant component containing 8.3%of IP nodes.

  We analyze the same structures (trees, acyclic part, core, giant component) for other combinatorial models of Internet (IP-level) topology, including arc graphs and place-holder graphs. We also show that Weibull distrbution N{X >x} = a exp(-(x/b)c approximates outdegree distribution with 10-15% relative accuracy in the region of generic object sizes, spanning two to three orders of magnitude up to the point where sizes become unique.

  The extended version of this paper includes dynamic and functorial properties of Internet topology, including properties of and diffusion on aggregated graphs, invariance of a reachability function's shape regardless of node choice or aggregation level, analysis of topological resilience under wide range of scenarios. We also demonstrate that the Weibull distribution provides a good fit to a variety of local object sizes.

• Andre Broido and KC Claffy, CAIDA

  Complexity of global routing policies

  In this paper we introduce a framework for analyzing BGP connectivity, and evaluate a number of new complexity measures for a union of core backbone BGP tables. Sensitive to engineering resource limitations of router memory and CPU cycles, we focus on techniques to estimate redundancy of the merged tables, in particular how many entries are essential for complete and correct routing.
  We introduced the notion of policy atoms as part of a calculus in routing table analysis. We found that the number of atoms and individual counts of atoms with a given number of prefixes properly scale with the Internet's growth and with filtering of prefixes by length. We show that the use of atoms can potentially reduce the number of route announcements by a factor of two, with all routing policies being preserved. Atoms thus represent Internet properties in an accurate way, yet with much smaller complexity.

  Several of our analysis results suggest that commonly held Internet engineering beliefs require re-consideration. We find that more specific routes had a relatively constant share of routes in backbone tables across 2000/2001. On the other hand, the churn of more specific routes was much larger than that of top prefixes. We also find that deaggregation of existing announcements is a second major source (beyond announcement of recently allocated address space) of new top (least specific) prefixes in global BGP tables. We also provide examples of misconguration and noise in BGP data, including multi-origin prefixes, AS paths with apparent routing loops (some of them due to typographical errors, other actual loops undetected by local BGP speakers), inadvertent transit through customer ASes.

• Fan Chung-Graham, UCSD

  Random graphs and Internet graphs

  Many very large graphs that arise in Internet and telecommunications applications share various properties with random graphs (while some differences remain). We will discuss some recent developments and mention a number of problems in random graphs and algorithmic design suggested by the study of these "massive" graphs.

• Mark Crovella, Boston Univ.

  Lessons from Merging Traceroutes

  I will talk about the visibility of IP routing paths possible when merging collections of traceroute (skitter) measurements.

• Dave Donoho, Stanford

  Wavelet Stepping Stone detection, Opportunities for Modern Statistical Methods in Network Measurements

  The talk concerns detecting network intruders who use universities and similar facilities as third-party launching pads (stepping stones) for attacks against other facilities. The most recent development is an idea to defeat the intruder who tries to “mask” the interactive session by making local jittering of packet arrival times so they won't be identical. By using wavelets we can still recognize the identity of the streams and so defeat this countermeasure.

  This is joint work with Vern Paxson and others.

• Tim Griffin, AT&T Labs-Research and BJ Premore, Dartmouth

  SSFNet simulations of the Border Gateway Protocol (BGP); BGP Tutorial

  We will describe our simulations of BGP using SSFNet that explore the impact of various configuration settings on convergence time, update rates, and router workloads. We'll also describe a very general set of scripts the we have developed that allow users to easily manage a large number of SSFNet experiments. (Joint work with Srdjan Petrovic.)

• Stephane Jaffard, Université Paris XII TBA

  Piet Van Mieghem and Willem Vree, Delft Univ. Visualisation of the RIPE-TT project data

  We will give a demonstration of our first results in visualising the data of the RIPE-TT project, and a sketch of possible directions we could follow in dealing with the measured delay-data. Piet van Mieghem may also give a short presentation on statistical properties we have found in this data so far.

• Stephen North, AT&T Labs-Research

  Graph drawing and network visualization software

  I will talk about tools for network visualization (graph drawing and massive network visualization software) and some experiments we've done in Internet mapping.

• Andy Ogielski, Renesys

  Analysis of BGP message streams from multiple peers

  We will show preliminary results of our analysis of BGP message streams from all RIPE NCC collection points (about 160 peering sessions) for the past several months.

  This is a joint work with Yougu Yuan, BJ Premore and Jim Cowie at Renesys.

• Kave Salamatian, Univ. Paris VI TBA

  Steve Uhlig, Univ. Namur Understanding Interdomain Traffic Dynamics at the Flow-Level : a spatio-temporal perspective

  We discuss the problem of our understanding of the dynamics of interdomain traffic by using the temporal, spatial and spatio-temporal perspectives. We review the current understanding of the dynamics of interdomain traffic in the Internet (at the flow level) with respect to each perspective, but without specific mention to the network topology and its properties. Then, we try to determine what should be done in order to better understand the traffic dynamics in the Internet at a large scale. We insist in particular on the methodology that should be used to understand the traffic dynamics (measurements vs. simulations), with an emphasis on the conceptual point of view.

• Henk Uijterwaal, RIPE NCC

  Collecting data on the Internet

  I'll describe the technical aspects of measuring on the Internet, in particular the RIPE NCC TTM (www.ripe.net/test-traffic) and RIS (www.ripe.net/ris/ris-index.html) setup. I'll also show some interesting recent results from both projects.

• Walter Willinger, AT&T Labs-Research TBA

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: Mrs. Reini Cremer, cremer@lc.leidenuniv.nl, phone +31-71-527 5401.
Fax number of the Lorentz Center: +31-71-527 5415

Workshop Information

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

Multiresolution Analysis of Global Internet Measurements

Multiresolution and aggreggation techniques lead to scalability, and scalability is at the core of large scale networking. The objective is to get closer to the goal of establishing a systematic foundation for new spatio-temporal, multi-scale techniques for Internet data representation and analysis, and from there to demonstrably scalable network and protocol designs.

The workshop focus will be equally on empirical data, and on new multiresolution concepts and techniques in modeling and analysis.

The speakers will give approximately one-hour lectures, each followed by a free discussion. By design, timing will be flexible so that hot (or hotly disputed) topics can get ample time, and all questions can be discussed.

Large scale Internet measurements - what and how is measured,
Network topology and routing analyses,
Multiresolution representations and analysis of traffic, topology, and other network data, Multiresolution and graph-theoretic techniques.

After the workshop, we'll collect slides, links to people's projects, etc., and put them on a workshop proceedings website.

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