CS598: Advanced Internet
Instructor: Brighten GodfreyTime: 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:
- Classic Architecture
- Congestion Control
- Routing
- Security
- Measurement
- New Internet Architectures
- Recent Topics in Networking Research
Announcements
- Dec 9: If you're interested in reading more, you may enjoy browsing CCR's recommended reading on various topics in networking.
- Oct 27: Clarification: If you present a paper, you don't have to send me a review for it. But you should still review the other paper presented in the same class, unless you would like to use one of your four free passes.
- Sep 24: Several announcements; in particular, you may skip any four paper reviews for free.
- Sep 18: Future office hours will be held Thursdays after class.
- Sep 8: Please email me your final exam schedule, so that we can schedule the poster session.
- Sep 7: As you have your project proposal deadline approaching, you may pick one of the papers (instead of both) to read and review for Sept 10 and 15.
- Sep 7: Minor changes to the reading list on Sep 10, Sep 15, Oct 6.
- Sep 4: Please send me the three papers you'd most like to present from the reading list by Wednesday, September 9.
- Aug 25: If you are planning to take the course, please email me (pbg at illinois dot edu) your name, email address, and educational situation (Masters / PhD, research area, one or two sentences about your background in networking)
Schedule
| Date | Topic | Readings | Presenters and slides | Comments |
|---|---|---|---|---|
| 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 |
||
| 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). |
||
| 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. |
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. |
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.) |
|
| 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. |
||
| 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 |
|
| Sep 29 | Traffic engineering andNew 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. |
||
| 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 |
|
| 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. |
||
| 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. |
||
| 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.) |
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. |
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. |
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 |
|
| 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. |
||
| 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. |
||
| 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. |
||
| 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 |
|
| 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. |
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. |
||
| 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 |
|
| 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.) |
||
| 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. |
||
| 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 |
|
| 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 | ||