Network Measurement, Monitoring, Diagnosis and Inference

Goal

To understand the behavior of Internet and provide adaptation to Internet applications with overlay network monitoring, diagnosis and inferences.

People

• Yan Chen
• Yao Zhao
• Chi Yin Cheung (undergrad)

Collaborators

• David Bindel (grad, UC Berkeley)
• Guohan Lu (Tsinghua University, China)

Past Collaborators

• Brian Chavez (undergrad, UCSC)
• Hanhee Song (undergrad, UC Berkeley)
• Randy Katz (faculty, UC Berkeley)
• Lili Qiu (Microsoft Research)
• Tony McGregor (NLANR)
• Chris Overton, Jing Zhi (Keynote)

Publications (please follow the link)

Projects

• Tomography-based Overlay Network Monitoring (TOM): measure the minimal number of paths (O(nlogn)) to infer the loss rates of all other paths on an overlay network of n nodes.
• Operationally Deterministic Network Diagnosis (ODD)
1. Pure end-to-end based measurement to infer the link-level loss rate.
2. Poster in ACM SIGCOMM, Aug., 2005.
• Fragmentation Aided Diagnosis (FAD): a router-response based approach to infer link-level loss rate without any receiver support.
• Packet fOrwarding Priority Inference (POPI): use end-to-end measurements to infer the packet forwarding priorities on routers.

Impact of Research

Our SIGCOMM 2004 paper on scalable overlay network monitoring has been extensively used in networking Ph.D. qualification exams and for seminar readings at various institutes: Cornell Systems Lunch, Rutgers system course, Columbia University (ELEN E6768 Emerging Topics in Emerging Networks), Boston University Networks Reading Group, National Taiwan University research group.

Presentations

• Tomography-based Monitoring: algebraic approach for scalable loss rate estimation for overlay network
1. SAHARA Summer Retreat (06/2003)
2. Berkeley Linear Algebra Group (by D. Bindel, 06/2003), more mathematical.
3. HP Lab (08/2003)
4. ICIR (The ICSI Center for Internet Research) (09/2003)
5. ACM SIGCOMM IMC conference (10/2003)
6. ACM SIGCOMM (8/2004)
• Internet Iso-bar: scalable latency estimation for overlay network
1. SAHARA Winter Retreat Presentations (01/2003)
2. Ericsson Berkeley Lab Meeting Presentations (01/2002)
3. Ericsson Budapest Lab Visit Slides (06/2001)
• Overview talks
1. NINJA/ICEBERG 2001 Winter Retreat Poster
2. Endeavor Retreat Slides

References (a bit out of date)

• Network Topology Discovery
• Octopus project: Network Topology Discovery at Cornell. Representative paper: Discovering Internet Topology, R. Siamwalla, R. Sharma and K. Keshav, Proceedings of IEEE INFOCOM '99.
• Topology Discovery in Heterogeneous IP Networks, Yuri Breitbart, Minos Garofalakis, Cliff Martin, Rajeev Rastogi, S. Seshadri, Abraham Silberschatz. Proceedings of IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000 .
• Dynamic Distance Maps of the Internet, Wolfgang Theilmann, Kurt Rothermel, Proceedings of IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000 .
• Heuristics for Internet Map Discovery, Ramesh Govindan, Hongsuda Tangmunarunkit,Proceedings of IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000 .
• Network Performance Measurement/Monitoring
• CAIDA has very good third-party bandwidth/throughput measurement tools comparison here.
• Workshop on Passive and Active Measurements (PAM) 2001
• IP Performance Metrics by IETF
• Passive Measurement/Monitoring
• SPAND: Shared Passive Network Performance Discovery project. Representative paper: A Network Measurement Architecture for Adaptive Applications. Mark Stemm, Randy H. Katz and Srinivasan Seshan, Proceedings of IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000. For more details, refer to Mark Stemm's Qual paper here.
• Nettimer at Stanford provides packet pair passive measuring for bandwidth and latency. SIGCOMM 2000 paper. (It has software release, which we may use for deploying the probes.)
• Passive Measurement and Analysis from The National Laboratory for Applied Network Research (NLANR) use dedicated hardware to collect traffic header and provides industry-strength analysis. It is similar to CoralReef at CAIDA.
• Trajectory Sampling for Direct Traffic Observation, Nick Duffield, Matthias Grossglauser (AT&T Research), SIGCOMM 2000.
• An Extensible Probe Architecture for Network Protocol Performance Measurement, G. Robert Malan and Farnam Jahanian (University of Michigan), SIGCOMM 1998.
• Active Measurement/Monitoring
• Scalable, Low-Overhead Network Delay Estimation, Volkan Ozdemir, S. Muthukrishnan, Injong Rhee, Proceedings of IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000.
• National Internet Measurement Infrastructure project by Vern Paxson, representative paper: Experiences with NIMI, Proceeding of PAM 2000.
• Using pathchar to Estimate Internet Link Characteristics, by Allen Downey.
• Self-Configuring Active Network Monitoring (SCAN) at ISI of USC
• OceanSpy references link by Chen-Nee Chuah.
• IP Backbone Measurement/Monitoring
• Architecture of a Passive Monitoring System for Backbone IP Networks, Chuck Fraleigh, Sue Moon, Christophe Diot, Bryan Lyles, Fouad Tobagi, Sprint ATL, October 2000. (submitted for publication).
• Measurement and analysis of IP network usage and behavior, R. Caceres, N. Duffield (MINC), A. Feldmann, J. Friedmann, A. Greenberg, R. Greer, T. Johnson, C. Kalmanek, B., Krishnamurthy, D. Lavelle, P. Mishra, K.K. Ramakrishnan, J. Rexford, F. True, and J. van der Merwe, AT&T. IEEE Communications Magazine, May 2000.
• Deriving Traffic Demands for Operational IP Networks: Methodology and Experience Anja Feldmann (University of Saarbruecken), Albert Greenberg, Carsten Lund, Nick Reingold, Jennifer Rexford, Fred True (AT&T Research), SIGCOMM 2000.
• End-to-End Measurement/Monitoring

§ RON: Resilient Overlay Network, David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris, SOSP 2001. Classical work on adaptive overlay network. Here is the RON project homepage.

§ User-level Internet Path Diagnosis, Ratul Mahajan, Neil Spring, David Wetherall, Thomas Anderson, SOSP 2003. Use single source-dest pair for diagnosis.

§ Comparison of some Internet Active End-to-end Performance Measurement projects from SLAC

• Internet End-to-End Performance Monitoring from Stanford, very informative.
• SPAND, Nettimer and many others in active/passive monitoring belong to this category.

• BGP/routing Measurement
• Network Performance Data Analysis

• On the Characteristics and Origins of Internet Flow Rates, Yin Zhang, Lee Breslau, Vern Paxson and Scott Shenker, IMW 2001. It applies math and statistics to data study, cool!
• Detecting Shared Congestion of Flows Via End-to-end Measurement, Dan Rubenstein, Jim Kurose, and Don Towsley, SIGMETRICS 2000.

• General Internet Services Enabled

• An architecture for a global internet host distance estimation service, Paul Francis, Sugih Jamin, Vern Paxson, Lixia Zhang, Daniel Gryniewicz, and Yixin Jin, In Proceedings of the IEEE INFOCOM '99, New York, NY, March 1999. IDMaps homepage.
• SONAR: A Network Proximity Service by NetLib and UTK.

Data Available Online

• NLANR has the largest amount of public data:
• Active measurement data: rtt, loss and topology
• Passive measurement data
• Research Network Maps and Statistics
• InternetPulse has backbone measurement data from Keynote

Tools

• Traceroute manual