CS598: Advanced Internet

Instructor: Brighten Godfrey
Time: Tuesdays and Thursdays 3:30 - 4:45 pm
Location: 1302 SC
Office hours: Thursday 4:45 - 5:45 pm, 3128 Siebel

The Internet has become the basis of most of humanity's remote communication. Its amazing growth and the fact that we use it in so many unexpected ways attest to the groundbreaking flexibility of its design. But because of this growth, the Internet's architecture has encountered a range of challenges including providing high reliability, accommodating enormous scale, dealing with economics and self-interested and malicious parties, and evolving the Internet itself.

This course will explore how the Internet works, how it fails to work, and cutting-edge research re-envisioning the architecture. Students will read and present papers ranging from the classics to the latest innovations, and from systems design to analytical foundations. Students will also carry out a research project with the goal of publication in a conference.

Knowledge of networking basics, as supplied by an undergraduate-level networking course, will be assumed but not required.

Major topics covered will include:

Announcements

Schedule

DateTopicReadingsPresenters and slidesComments
Introduction
Aug 25 Course overview, Internet history

No reviews due.

Vannevar Bush. As we may think. Atlantic Monthly, July 1945.

Barry M. Leiner, Vinton G. Cerf, David D. Clark, Robert E. Kahn, Leonard Kleinrock, Daniel C. Lynch, Jon Postel, Larry G. Roberts, Stephen Wolff. A brief history of the Internet.

Brighten
Aug 27 Project description and suggested topics

None.

Brighten
Classic Architecture
Sep 1 TCP / IP

Vinton Cerf and Robert Kahn. A protocol for packet network intercommunication. IEEE Transactions on Communications, Vol. 22 No. 5, May 1974.

David Clark, The Design Philosophy of the DARPA Internet Protocols. Proc. SIGCOMM 1988.

Brighten
Sep 3 Architectural approaches and principles

Jon Postel. Internetwork protocol approaches. IEEE Transactions on Communications, 28(4):604-611, April 1980.

J.H. Saltzer, D.P. Reed and D.D. Clark. End-to-End Arguments in System Design. ACM Trans. on Computer Systems, Vol. 2, No. 4, Nov 1984, pp. 277-288

Virajith Jalaparti

Ankit Singla

Congestion Control
Sep 8 Dealing with independence: TCP congestion control

Van Jacobson. Congestion Avoidance and Control. Proc. SIGCOMM 1988, pp. 314-329. NOTE: You need not read the appendices of this paper.

Dah-Ming Chiu and Raj Jain. Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks. Computer Networks and ISDN Systems, Vol. 17, No. 1, June 1989, pp. 1-14. NOTE: There appears to be a typo: on p. 8, in the third line of math, (bI + 1) should be (bI - 1).

Naveen Cherukuri

Ashish Vulimiri

Sep 10 TCP congestion control ... and Dealing with selfishness: Fair queueing

Dina Katabi, Mark Handley, and Charlie Rohrs. Congestion Control for High Bandwidth-Delay Product Networks. SIGCOMM 2002.

Alan Demers, Srinivasan Keshav, and Scott Shenker. Analysis and Simulation of a Fair Queueing Algorithm. Proc. ACM SIGCOMM 1989, pp. 1-12.

Optional reading: Abhay K. Parekh and Robert G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The single-node case. IEEE/ACM Transactions on Networking, pp. 344-357, June 1993.

Chi-Yao Hong

Brighten

You may pick one of these three papers to review, rather than the usual two reviews.
Sep 15 Recent approaches to selfishness and incentives

Bob Briscoe, Arnaud Jacquet, Carla Di Cairano-Gilfedder, Alessandro Salvatori, Andrea Soppera, and Martin Koyabe. Policing Congestion Response in an Internetwork using Re-feedback. SIGCOMM 2005.

Bob Briscoe. Flow Rate Fairness: Dismantling a Religion. ACM Computer Communications Review 37(2), pps. 63-74, April 2007.

Haohui Mai

Brighten

You may pick one of these papers to review.

Project proposals due

Intradomain routing
Sep 17 Router architecture

Craig Partridge, Philip P. Carvey, Ed Burgess, Isidro Castineyra, Tom Clarke, Lise Graham, Michael Hathaway, Phil Herman, Allen King, Steve Kohalmi, Tracy Ma, Trevor Mendez, Walter Milliken, Ronald Pettyjohn, John Rokosz, Joshua Seeger, Michael Sollins, Steve Storch, Benjamin Tober, Gregory D. Troxel, David Waitzman, and Scott Winterble. A 50-Gb/s IP Router. IEEE/ACM Transactions on Networking, June 1998.

Mihai Dobrescu, Norbert Egi, Katerina Argyraki, Byung-Gon Chun, Kevin Fall, Gianluca Iannaccone, Allan Knies, Maziar Manesh, and Sylvia Ratnasamy. RouteBricks: Exploiting Parallelism to Scale Software Routers. SOSP 2009.

Congestion Control discussion questions (No presentation of Partridge et al.)

Shuyi Chen

Sep 22 Intradomain routing algorithms

Radia Perlman. Fault-Tolerant Broadcast of Routing Information. Computer Networks, vol 7, 1983, pp. 395-405.

Yakov Rekhter, Bruce Davie, Eric Rosen, George Swallow, Dino Farinacci, Dave Katz. Tag Switching Architecture Overview. 1997.

See also (no review due): RFC 3031: Multiprotocol Label Switching (MPLS) Architecture.

Brighten (Intro)

Yusuf Sarwar

Imranul Hoque

Sep 24 Traffic engineering

Tag switching / MPLS continued

A. Khanna and J. Zinky. The Revised ARPANET Routing Metric. ACM SIGCOMM 1989, Austin, TX, USA, September 1989.

Imranul Hoque

Shuyi Chen

Announcements

Sep 29 Traffic engineering
and
New intradomain architectures

Srikanth Kandula, Dina Katabi, Bruce Davie, and Anna Charny. Walking the Tightrope: Responsive Yet Stable Traffic Engineering. SIGCOMM 2005.

Martin Casado, Michael Freedman, Justin Pettit, Nick McKeown, and Scott Shenker. Ethane: Taking Control of the Enterprise. SIGCOMM 2007.

Aparna Sundar

Giang Nguyen

Oct 1 New intradomain architectures

Ethane continued

Changhoon Kim, Matthew Caesar, and Jennifer Rexford. Floodless in SEATTLE: A Scalable Ethernet Architecture for Large Enterprises. SIGCOMM 2008.

Giang Nguyen

Chi-Yao Hong

Internet routing and big challenges for routing
Oct 6 Observed problems

Vern Paxson. End-to-End Routing Behavior in the Internet. SIGCOMM 1996.

Stefan Savage, Andy Collins, Eric Hoffman John Snell, and Thomas Anderson. The End-to-End Effects of Internet Path Selection. SIGCOMM 1999.

Hee Dong Jung

Imranul Hoque

Oct 8 Reliable routing

K. Lakshminarayanan, M. Caesar, M. Rangan (UCB), T. Anderson (Univ. of Washington), S. Shenker (UCB/ICSI), I. Stoica. Achieving Convergence-Free Routing using Failure-Carrying Packets. SIGCOMM 2007.

John P. John, Ethan Katz-Bassett, Arvind Krishnamurthy, Thomas Anderson, and Arun Venkataramani. Consensus Routing: The Internet as a Distributed System. NSDI 2008.

Chi-Yao Hong

Naveen Cherukuri

Oct 13 BGP games

Timothy G. Griffin, F. Bruce Shepherd, and Gordon Wilfong. The Stable Paths Problem and Interdomain Routing. IEEE/ACM Transactions on Networking, 10(2), pp. 232-243, April 2002.

Joan Feigenbaum, Christos Papadimitriou, Rahul Sami, and Scott Shenker. A BGP-based Mechanism for Lowest-Cost Routing. Distributed Computing 18 (2005), pp. 61-72. (Special issue of selected papers from Proc. of ACM PODC 2002.)

Rachit Agarwal

Tony Huang

Pick one to review.
Oct 15 Selfish routing

Tim Roughgarden and Eva Tardos. How Bad is Selfish Routing?. JACM 2002. Originally appeared in FOCS 2000.

Lili Qiu, Yang Richard Yang, Yin Zhang, and Scott Shenker. On selfish routing in internet-like environments. SIGCOMM 2003.

Brighten

Giang Nguyen

Pick one to review.
Oct 20 Scalable routing

Leonard Kleinrock and Farouk Kamoun. Hierarchical Routing for Large Networks: Performance Evaluation and Optimization. Computer Networks, 1(3), pp. 155-174, January 1977.

Mikkel Thorup and Uri Zwick. Compact routing schemes. SPAA 2001. NOTE: We will cover Sections 1 and 3 only, so you can restrict your reading to those sections if you wish.

Naveen Cherukuri

Ankit Singla

Pick one to review.
Oct 22 Project midterm presentations None. half o' y'all Project midterm presentations due (See what should be in your presentation (slide 4))
Oct 27 Project midterm presentations Part 2 None.

the other half o' y'all

Announcements

New architectures
Oct 29 Principles for the future

David Clark, John Wroclawski, Karen Sollins, and Robert Braden. Tussle in Cyberspace: Defining Tomorrow's Internet. Transactions in Networking, June 2005.

Tom Anderson, Scott Shenker, Ion Stoica, and David Wetherall. Design Guidelines for Robust Internet Protocols. HOTNETS 2002.

Kong Lam

Ankit Singla

Nov 3 NIRA and Pathlets

Xiaowei Yang, David Clark, and Arthur Berger. NIRA: A New Inter-Domain Routing Architecture. IEEE/ACM Transactions on Network (ToN), vol 15, no. 4, Aug. 2007.

P. Brighten Godfrey, Igor Ganichev, Scott Shenker, and Ion Stoica. Pathlet routing. SIGCOMM 2009.

Rachit Agarwal

Brighten

Nov 5 MINT and DONA

Vytautas Valancius, Nick Feamster, Ramesh Johari, and Vijay Vazirani. MINT: A Market for Internet Transit. ACM ReArch 2008.

Teemu Koponen, Mohit Chawla, Byung-Gon Chun, Andrey Ermolinskiy, Kye Hyun Kim, Scott Shenker, and Ion Stoica. A Data-Oriented (and Beyond) Network Architecture. SIGCOMM 2007.

Kong Lam

Tony Huang

Security
Nov 10 Measuring malice

A. Ramachandran and N. Feamster. Understanding the Network-level Behavior of Spammers. SIGCOMM 2006.

Christian Kreibich, Chris Kanich, Kirill Levchenko, Brandon Enright, Geoffrey M. Voelker, Vern Paxson, and Stefan Savage. Spamcraft: An Inside Look At Spam Campaign Orchestration. Second USENIX Workshop on Large-scale Exploits and Emergent Threats (LEET '09), 2009, Boston, USA.

Yusuf Sarwar

Imranul Hoque

Nov 12 DDoS defense

M. Walfish, M. Vutukuru, H. Balakrishnan, D. Karger, and S. Shenker. DDoS Defense by Offense. SIGCOMM 2006.

Xin Liu, Xiaowei Yang, and Yanbin Lu. To Filter or to Authorize: Network-Layer DoS Defense Against Multimillion-node Botnets. SIGCOMM 2008.

Kong Lam

Giang Nguyen

Nov 17 Spam and botnet defense

Yinglian Xie, Fang Yu, Kannan Achan, Rina Panigrahy, Geoff Hulten, and Ivan Osipkov. Spamming Botnets: Signatures and Characteristics. SIGCOMM 2008.

Ramakrishna Gummadi, Hari Balakrishnan, Petros Maniatis and Sylvia Ratnasamy. Not-a-Bot: Improving Service Availability in the Face of Botnet Attacks. USENIX NSDI 2009.

Hee Dong Jung

Ashish Vulimiri

Nov 19 Where is your traffic going?

Not-a-Bot continued

Hitesh Ballani, Paul Francis, and Xinyang Zhang. A Study of Prefix Hijacking and Interception in the Internet. SIGCOMM 2007.

Ashish Vulimiri

Tony Huang

Dec 1 Secure control planes

Sharon Goldberg, Shai Halevi, Aaron D. Jaggard, Vijay Ramachandran, and Rebecca N. Wright. Rationality and Traffic Attraction: Incentives for Honest Path Announcements in BGP. SIGCOMM 2008.

Josh Karlin, Stephanie Forrest, and Jennifer Rexford. Autonomous security for autonomous systems. Computer Networks 52 (2008): 2908-2923. (Originally appeared in ICNP 2006.)

Rachit Agarwal

Virajith Jalaparti

Dec 3 Secure control planes

and

New architectures

Lakshminarayanan Subramanian, Volker Roth, Ion Stoica, Scott Shenker, and Randy H. Katz. Listen and Whisper: Security Mechanisms for BGP. NSDI 2004.

David G. Andersen, Hari Balakrishnan, Nick Feamster, Teemu Koponen, Daekyeong Moon and Scott Shenker. Accountable Internet Protocol (AIP). SIGCOMM 2008.

Ashish Vulimiri

Virajith Jalaparti

Dec 8 New architectures

and

Project presentation

Arun Seehra, Jad Naous, Michael Walfish, David Mazieres, Antonio Nicolosi, and Scott Shenker. A policy framework for the future Internet. HOTNETS 2009. See also the tech report version.

Yusuf Sarwar project presentation

Haohui Mai

Yusuf Sarwar

The Last Word

Project report and poster session
Dec 10 Project final report due 11:59 pm (See what should be in your report (slide 5))
Dec 15 Project poster session 1:30 - 4:30 p.m. Project posters due