EL 933 Network Measurement and
Instructor: Yong Liu
Networks, and the Internet in particular, have experienced exponential
growth, becoming one of the largest engineering systems ever
constructed. Management of this large system is of critical importance,
and challenging at the same time. Measurements and models based on
these measurements are integral components to understand network
behavior and provide basis for better management. This seminar covers
topics both in measurement, ranging from traffic/protocol/application
characterization to anomaly detection, and in traffic engineering,
including congestion control and optimal routing. The follows is the
list of subjects to be covered:
- Internet Traffic Analysis: self-similarity and long-range
- Packet Loss/Delay Characterization: statistical models
- Packet Probing: capacity available bandwidth estimation
- Network Tomography: inference from the edge
- Anomaly Detection: worm, DDoS attacks, link failures
- Traffic Matrix Estimation: existing and new approaches
- Distributed Measurement: network of network sensors
- Network Routing: optimal routing in a changing world
- Overlay Routing: application level routing adaptation
- Congestion Control: a closed-loop analysis
EL536 or equivalent, elementary probability course
Students will be evaluated by class participation and a final
project. The final project can be either a study of a paper from major
networking conferences and journals or student’s original work on
network measurement and traffic engineering. For both cases, a
presentation and a term paper is required.
A list of conferences:
Passive & Active Measurement
ACM Special Interest
Group on Data Communications (SIGCOMM)
IEEE Conference on Computer
and Communications (INFOCOM)
Conference on Measurement and Modeling of Computer Systems (SIGMETRICS)
IEEE International Conference on
Network Protocols (ICNP)
- “Data Networks (2nd Edition)”, D. Bertsekas and R.
- “Computer Networking, a top down approach featuring the
(3rd edition)”, James F. Kurose and Keith W. Ross.
- “Nonlinear Programming”, Dimitri P. Bertsekas.
- “The Mathematics of Internet Congestion Control”, R.
Class 1: Introduction slides
Class 2: Internet Traffic Analysis slides
Class 3: Network Status Characterization: packet loss and
delay slides handout in pdf
- W. Leland, M. Taqqu, W. Willinger, D. Wilson. "On the Self-Similar Nature of Ethernet
Traffic (Extended Version)," IEEE/ACM Transactions on Networking,
2(1):1-15, February 1994.
- V. Paxson, S. Floyd. "Wide-Area Traffic: The Failure of
Poisson Modeling," IEEE/ACM Transactions on Networking,
3(3):226-244, June 1995.
- M.E. Crovella, A. Bestavros. "Self-Similarity in World
Web Traffic: Evidence and Possible Causes," IEEE/ACM Transactions
on Networking, 5(6):835--846, December 1997.
Class 4: Packet Probing: capacity, available
bandwidth and bottle-necks slides handout
- M. Yajnik, S.B. Moon, J. Kurose, D. Towsley "Measurement and Modeling of the Temporal
Dependence in Packet Loss" Proc. IEEE/INFOCOM 1999 (New York, NY,
- K. Papagiannaki, S. Moon, C. Fraleigh, P. Thiran, F. Tobagi, C.
Diot, "Analysis of Measured Single-Hop Delay
from an Operational Backbone Network", appeared in IEEE JSAC
special issue on network measurement, an earlier version appeared in
IEEE/INFOCOM 2002, New York.
- Daniel Aguayo John Bicket Sanjit Biswas Glenn Judd †
Morris, "Link-level Measurements from an
802.11b Mesh Network", Proc. ACM/SIGCOMM 2004.
Class 5: Network Tomography: end-end inference of network
characteristics slides handout
- C. Dovrolis, P.Ramanathan, D.Moore "What Do Packet Dispersion Techniques
Measure?", Proc. IEEE/INFOCOM 2001.
- M. Jain, C. Dovrolis, "Pathload:
A Measurement Tool for End-to-end Available Bandwidth", Proceedings
of the 3rd Passive and Active Measurements (PAM) Workshop, March 2002.
- N. Hu, L. Li, Z. Mao, P. Steenkiste, J. Wang, "Locating Internet Bottlenecks:
Algorithms, Measurements, and Implications". Proc.
Class 6: Anomaly Detection: worm, DDoS attacks, link
failures slides handout
- R. Caceres, N.G. Duffield, J. Horowitz, D. Towsley, "Multicast-based Inference of Network-Internal
Loss Characteristics", IEEE Transactions on Information Theory,
- R. Cáceres, N. Duffield, S.B. Moon, D. Towsley, "Inference of Internal Loss Rates in the MBone",
Proc. IEEE Global Internet'99, Rio de Janeiro, Brazil, December 1999.
- M. Coates, R. Castro, R. Nowak, M. Gadhiok, R. King, Y. Tsang, "Maximum likelihood network topology
identification from edge-based unicast measurements",
Class 7: Selected Topics from IMC 2005
- D. Moore, C. Shannon, K. Claffy, "Code-Red: a case study on the spread and
victims of an Internet worm", ACM SIGCOMM Internet Measurement
Workshop (IMW) 2002.
- V. Yegneswaran, P. Barford, J. Ullrich, "Internet Intrusions: Global
Characteristics and Prevalence", in Proceedings of ACM SIGMETRICS,
- P. Barford, J. Kline, D. Plonka, A. Ron, "A Signal Analysis of Network Traffic Anomalies",
ACM SIGCOMM Internet Measurement Workshop (IMW) 2002.
Class 8: Traffic Matrix Estimation slides
- "Exploiting Underlying Structure
for Detailed Reconstruction of an Internet-scale Event", Abhishek
Kumar, Georgia Institute of Technology; Vern Paxson and Nicholas
Weaver, ICSI, Slides in pdf.
- "Characterization and Measurement
of TCP Traversal Through NATs and Firewalls", Saikat Guha and Paul
Francis, Cornell University, Slides in
- "Should Internet Service Providers
Fear Peer-Assisted Content Distribution?", Thomas Karagiannis,
University of California, Riverside; Pablo Rodriguez, Microsoft
Research; Konstantina Papagiannaki, Intel Research Cambridge, Slides in pdf.
Class 9: Internet Traffic Engineering slides
Class 10: Network Congestion Control slides
Class 11: Design and Analysis of Overlay Networks slides handout
- "Traffic Matrix Estimation: Existing
Techniques and New Directions", A. Madina, N. Taft, K. Salamatian,
S. Bhattacharyya, C. Diot, ACM SIGCOMM 2002.
- "Fast Accurate Computation of
Large-Scale IP Traffic Matrices from Link Loads", Y. Zhang, M.
Roughan, N. Duffield, A. Greenberg, ACM SIGMETRICS 2003.
Class 12: Student Presentations Group I
- "Application Level Relay for
High-bandwidth Data Transport'', Yong Liu, Yu Gu, Honggang Zhang,
Weibo Gong and Don Towsley, the First Workshop on Networks for Grid
Applications (GridNets) , San Jose, October 2004.
- "On the Interaction Between
Overlay Routing and Traffic Engineering'', Yong Liu, Honggang
Zhang, Weibo Gong and Don Towsley, In Proc. of IEEE/INFOCOM 2005.
Class 13: Student Presentations Group II,
- "A First Look at Modern Enterprise
Traffic", Ruoming Pang, Mark Allman, Mike Bennett, Jason Lee, Vern
Paxson, Brian Tierney, In Proc. of ACM/IMC 2005, presented by Loizos
Konomou, slides in ppt.
- "Joint Data Streaming and Sampling
Techniques for Detection of Super Sources and Destinations", Qi
(George) Zhao, Abhishek Kumar, and Jun (Jim) Xu, In Proc. of ACM/IMC
2005, presented by Chao Liang, slides in ppt.
- "Detecting Mass-Mailing Worm
Infected Hosts by Mining DNS Traffic Data", Keisuke Ishibashi,
Tsuyoshi Toyono, Katsuyasu Toyama, Masahiro Ishino, Haruhiko Ohshima,
and Ichiro Mizukoshi, In Proc. of ACM/SIGCOMM MineNet Workshop 2005,
presented by Anagha Mudigonda, slides in
Class 14: Student Presentations Group III,
- "Combining Filtering and Statistical
Methods for Anomaly Detection", Augustin Soule, Kave Salamatian,
Nina Taft, In Proc. of ACM/IMC
2005, presented by Dhruvi Roshni, slides
- "Robust TCP Stream Reassembly In
the Presence of Adversaries", Sarang Dharmapurikar Vern
Paxson, Proc. USENIX Security Symposium 2005, presented by Sertac
Artan, slides in pdf.
- "Meridian: A Lightweight Network
Location Service without Virtual Coordinates", Bernard Wong,
Aleksandrs Slivkins, Emin Gun Sirer, In Proc. of ACM/SIGCOMM 2005,
presented by Xiaojun Hei, slides in ppt.
Class 15: Student Presentations Group IV,
- Survey on Bittorrent Network, presented by Jian Liang, slides in ppt.
Analysis, and Modeling of BitTorrent-like Systems", Lei Guo,
Songqing Chen, Zhen Xiao, Enhua Tan, Xiaoning Ding, and Xiaodong Zhang,
In Proc. of ACM/IMC
- "Analyzing and Improving BitTorrent
Performance", Ashwin R. Bharambe and Cormac Herley, to appear in
IEEE INFOCOM 2006.
- "Network Anomography", Yin
Zhang, Zihui Ge, Albert Greenberg, and Matthew Roughan, In Proc. of
ACM/IMC 2005, presented by Huizhong Sun, slides
- " ClassBench: A Packet
Classification Benchmark", David E. Taylor, Jonathan S. Turner, In
Proc. of IEEE/INFOCOM 2005, presented by James Yang, slides in ppt.
- "EXOR: Opportunistic Multi-Hop Routing
for Wireless Networks", Sanjit Biswas and Robert Morris, In
Proc. of ACM/SIGCOMM 2005, presented by Shunyuan Ye, slides in ppt.
- “Network Structure Optimization by
GA (Genetic Algorithm)”, T.B.Le, H.B.Tran, H.T.Tran,
D.T.Duy, D.V.Dinh, 25th International conference Asian
Info-communications Council (AIC), Shanghai – China, 2001,
Tan Ba Le, slides in pdf.
Office: LC 258
Phone : (718) 260-3959
FAX: (718) 260-3906