CSL858, Winter 2011: Advanced Computer Networks



We will go beyond what we studied in CSL 374 to explore in detail some fundamental aspects of computer networks and current research areas. Computer networks is one of the most interesting fields of computer science because it has heavy components of both theory and practice. There are certain topics where theory has preceded its application, but lots others where economics or pragmatic urgency or Moore's Law has set the direction for technology development, leaving the science to catch up much later. Throughout the course, we will examine current research and its impact in this broader context. Students will learn in detail some fundamental concepts of networks, basic theoretical tools, get a peep into current research topics, and broadly understand how research problems are identified, addressed, and sometimes are able to find their way to deployment. Our emphasis on wireless networks will be low because another course is being offered in parallel.


Readings and outline

[L] indicates a lecture, [P] indicates a student presentation, [O] indicates optional (depending on time)

Paper review website

Physical layer The various acronyms!
[L] Digital modulation: BPSK, QPSK, QAM. Encoding: NRZ, AMI, 2B1Q, 4B/5B. Analog modulation. Analog sampling
Error control Error checking, correcting, estimation
[L] Block coding: Hamming distance, parity check, Hamming codes, interleaving. Convolution coding.
[L] Chen: Error estimating codes, Sigcomm 2010.
[L] Huitema: Packet level FEC, IFIP TC6, 1996. Network coding, tornado codes
MAC Winners and losers
[L] Saltzer: Why a ring, Sigcomm 1981
[P] Leland: Self similarity of Ethernet traffic, Sigcomm 1993
Trends in wireless MAC
[P] Sen: CSMA/CN, MobiCom 2010

[L] Das: Async data traffic over Bluetooth, Infocom 2001
Switching Basics
[L] Switch internals: Fabrics, banyan network, CAM

Keeping up...
[P] Keshav: Trends in router design, IEEE Communications Magazine, May 1998
[P] Varghese: L4 switching, Sigcomm 1998
[P] Moon: GPUs in switches, Sigcomm 2010

Packet switching Vs circuit switching: The tussle continues
[P] Katz: Tag based switching, Proceedings of IEEE, Dec 1997
[L] Molinero: Circuit switching in the core
Scheduling and QoS Basics
[L] Queueing theory introduction
[L] Max-min, proportional fairness, fairness index, scheduling Vs E2E flow control

[P] Keshav: WFQ, ACM 1989. Varghese: DRR, Sigcomm 1995

[P] Zhang: RSVP, IEEE Network Magazine, 1993
[P] Clark: IntServ, Sigcomm 1992
Flow and congestion control Basics
[L] Open and closed loop flow control, rate based, window based
[L] Basics of control theory
[L] Jacobson: Congestion control, Sigcomm 1988. Jain: AIMD analysis

Case studies
[P] Floyd: RED, IEEE/ACM Transactions on Networking, Aug 1993.
Floyd: ECN, ACM Sigcomm Computer Communication Review, Oct 1994.
Jacobson: RED in a different light, Sep 1999
[O] Floyd: TCP variants and comparison, Computer Communication Review, July 1996
[P] Floyd: DCCP, Sigcomm 2006.
Fall: E2E congestion control, IEEE/ACM Transactions on Networking (TON), Aug. 1999

Sanity check
[P] Smith: AQM performance for web traffic, Sigcomm 2000

Other techniques and fixes
[P] McKeown: Buffer sizing, Infocom 2006

Transport layer error control and performance
[P] NetBlt, Sigcomm 1987
Routing Classics
[P] Perlman: Ethernet spanning tree, Sigcomm 1985

Need better solutions!
[P] Paxson: Routing behaviour, ACM SIGCOMM Computer Communication Review, Oct 2006
[P] Mahajan: BGP stability, Sigcomm 2002. Labovitz: Internet routing convergence,Sigcomm 2000
[O] Varghese: Routing table sizes, Sigcomm 2003

You can't build it right unless you can measure it
[P] Doyle: Routing topology, Sigcomm 2004. Spring: Rocketfuel, Sigcomm 2002

Traffic management according to preferences
[L] Bayesian inference, expectation maximization, principal component analysis
[P] Diot: Traffic matrices, Sigcomm 2002
[P] Zhang: Traffic engineering, IMC 2003

Fault management
[P] Diot: Network wide anomalies, Sigcomm 2004
[P] Bahl: Fault diagnosis, Sigcomm 2007

[O] Estan: Internet measurements, ACM Transactions on Computer Systems (TOCS), Aug 2003
Internet architecture and clean slate design Evolution
[L] Schroeder: Grapevine, ACM Transactions on Computer Systems (TOCS), Feb 1984.
Clark: DARPA protocols, Sigcomm 1988.
Shiv: Evolving Internet.
Kelly: Self managed Internet, Philosophical Transactions of the Royal Society A358 (2000)

Thoughts from clean slate designs
[P] Stoica: I3, Sigcomm 2002
[P] Balakrishnan: Layered naming architecture, Sigcomm 2004
[P] Jacobson: Networking named content, ACM CoNEXT 2009
[O] Jokela: Line-speed publish subscribe, Sigcomm 2009

Measurements leading to models for re-design
[P] Paxson: E2E Internet packet dynamics, IEEE/ACM Transactions on Networking 7(3),
Bolot: E2E packet delay and loss behaviour, Sigcomm 1993.
Wang: Internet bottlenecks, Infocom 2005.
Gummadi: Residential broadband, IMC’07
[P] Floyd: Wide area traffic self similarity, IEEE/ACM Transactions on Networking, June '95
[P] Bestavros: Web traffic self similarity, IEEE/ACM Transactions on Networking, Dec '97

[L] Towsley: Soft state protocols, Sigcomm 2003
[L] Sirer: Trickles, Proceedings of Networked System Design and Implementation, May 2005
Actual architectural responses Topology responses
[P] Mahanti: Flattening Internet, PAM'08.
Labovitz: Internet inter-domain traffic, Sigcomm 2010

[P] Morris: Vivaldi
[P] Stoica: Chord, Infocom 2004

Architectural responses: Overlay, P2P, CDNs, caching
[P] Morris: RON, Proc. 18th ACM SOSP, Oct 2001
[O] Zhang: End system multicast, Sigmetrics 2000
[P] Shenker: Scalable Gnutella, Sigcomm 2003
[O] Gummadi: P2P workloads, SIgcomm 2003
[O] Huang: P2P VoD, Sigcomm 2008
[P] Luby: Digital fountain approach to bulk data transfers, Sigcomm 1998
[P] Saroiu: Measurement of CDNs, ACM SIGOPS Operating Systems Review - OSDI '02
[P] Broder: Wide area cache sharing, IEEE/ACM Transactions on Networking, Jun 2000
[O] Su: Akamai drafting, Sigcomm 2006
[O] Rodriguez: Bulk data transfers, Sigmetrics/Performance 2009
New types of networks DTNs, data centers, OSNs, mobile networks
[P] Fall: DTN, Sigcomm 2003
[O] Jain: DTN routing, Sigcomm 2004
[P] Vahdat: Commodity data center, Sigcomm 2008
[O] Padhye: Data centre TCP, Sigcomm 2010
[P] Rodriguez: SPAR, Sigcomm 2010
[P] Hui: Haggle routing, Philosophical Transactions of the Royal Society A, June 2008


Project ideas

  • Core networks
    • Write a passive monitoring tool for bandwidth and link analysis. The tool can monitor incoming and outgoing packets, attach flags such as record route options in IP packets, send pings, etc, but should consume minimal bandwidth itself
    • Write a link profiler which infers properties of the access link, and accordingly sets parameters on some open-source link emulation tool
    • Write an extremely easy-to-use tool for photo and video upload over a flaky Internet connection in rural areas. Think about using layered codecs so that a poor-resolution upload can be done immediately over MMS for example, while higher-resolution uploads follows later over GPRS or DSL or VSAT links. As a second step, publish the content on Facebook and build an application which allows users to leave voice-based comments on the content.
    • Collect logs from the IIT proxy and analyze its caching effectiveness. Improve the effectiveness by caching streaming content.
    • Set up a CDN or a P2P VoD service on campus. Write a Firefox or Chrome plugin to use the infrastructure through the browser, especially for streaming video such as through YouTube. Study its performance under different link emulation and content distribution scenarios
    • Write a Facebook application for an iPhone or Android or Symbian client, which does not upload photos and videos all the way to Facebook, but uses a local CDN for video delivery. Study the performance with different mobility scenarios.
    • On a network of PlanetLab nodes, use DNS to find out the closest Akamai servers. Then study if you can find a pattern to which YouTube or Facebook videos are cached on these servers by fetching a list of recent videos, popular videos, etc from YouTube.
  • Application of networks concepts
    • Model the paper trail in the IIT adminstration as a network and analyze its properties
    • Kleinberg XXX
  • Applications
    • Write a social network crawler for Twitter, Facebook, etc, which can crawl based on different sampling criteria, and store the network in a distributed database
    • Design a campaign system on Facebook: Content is pushed automatically to a subset of volunteers seeded in different parts of the social network, and then routed to groups to which the volunteers are subscribed. Keep track in real time of content accesses, and learn the efficacy of the volunteers to popularize issues.
  • Survey papers
    • Do a history study of the development and popularization of the Ethernet, scheduling and flow control in computer networks, P2P, and other topics. How research built upon other prior work, how extraneous factors influenced the development, which works made it to the real world, etc.
    • Do a survey on intrusion detection systems, prevention of DDoS attacks, bot-nets, etc.
    • Do a survey on the state of the art in data center networking.