CAS CS 556
Spring 2005

Computer Networks II 

FINAL EXAM: Monday 05/09, 9:00-11:00am.

This course emphasizes the design, analysis, and implementation of (existing and emerging) protocols from link-level to applications.

This is a tentative syllabus and subject to change. Please check this page regularly and follow announcements in class. Dates are approximate. 

Not all topics listed below will be necessarily covered or covered in detail. Speed and level of coverage will depend to some extent on the maturity and background of the class.

Readings will include lecture slides, notes, some papers and RFCs. Some of the papers/RFCs (or portions thereof) are must-read, the rest are supplementary. This page will include links to these readings. PLEASE SCROLL ALL THE WAY DOWN.

Click here for Active IETF (Internet Engineering Task Force) Working Groups.

The TF (Karim Mattar) will maintain a web page with hints related to ns and lab assignments.

Lecture slides below are in PDF format. PDF files require Adobe Acrobat Reader. You can view PostScript files using ghostview.
 
Dates  
(Tue, Thu)
Topics
Notes/Assignments

1/18, 1/20
Introduction: architectural design issues: end-to-end vs. network support

intro-1 intro-2

1/25, 1/27

 Simulation: discrete-event simulation, confidence intervals, the ns tool

intro-3
simulation

2/1, 2/3
2/8, 2/10
2/15, 2/17
Flow/Congestion Control: implementation, modeling (optimization, deterministic/probabilistic analysis, control theory), fairness, stability, open-loop vs. closed-loop, traffic specification (leaky-bucket), window vs. rate, implicit vs. explicit feedback. TCP variants (Tahoe, Reno, New-Reno, SACK, Vegas,...)

intro-4 netsim dynamics-1

tcp-primer dynamics-2

dynamics-3 dynamics-4

2/22          

NO CLASS (substitute Monday schedule)
       2/24
3/1, 3/3

Congestion Control (continued): congestion-sensitive streaming, drop strategies (tail-drop, RED, WRED,...), effect of wireless links and attacks 

buffer
other-adaptations
3/8, 3/10

SPRING RECESS (Sat March 5 - Sun March 13)

  
3/15

Catch Up & REVIEW

  
        3/17

MIDTERM

  

3/22, 3/24
3/29, 3/31
4/5, 4/7                    
Routing: implementation, stability/convergence, link-state vs. distance-vector vs. path-vector, conventional routing (RIP, IGRP, BGP, OSPF,...), multi-path and type-of-service (ToS) routing, quality-of-service (QoS) or constrained-based routing (QOSPF,...), approaches to reduce communication and processing costs (hierarchical routing, limited broadcast, threshold-based schemes, pre-computation, caching, ...), conventional multicast routing (DVMRP, MOSPF, PIM-sm/dm, CBT), performance-aware multicast routing (bandwidth-aware heuristics, scalability issues)

control-theory-1 control-theory-2 control-theory-3 dynamics-5
routing-1

4/12, 4/14          
Scheduling: implementation, fairness, performance bounds, priorities, work conservation, scheduling best-effort flows and guaranteed-service flows (GPS, WRR, DRR, WFQ,...)

routing-2 routing-3

4/19, 4/21
4/26, 4/28             
Architectures: traffic classes, DiffServ and IntServ service models, class-based allocation, overlays (file sharing), voice-over-IP, wireless ad-hoc and sensor networks

mcast-1
mcast-2(up to the 5th slide required)
wireless-1 manet
5/3

Wrap Up & REVIEW

wrap-up
             
FINAL EXAM (Monday May 9, 9:00-11:00 AM)
 

 

READINGS

Introduction

J. Saltzer, D. Reed, and D. Clark. End-to-End Arguments in System Design. ACM Transactions on Computer Systems (TOCS), vol. 2, no. 4, pp. 195-206, 1984.

David D. Clark. The Design Philosophy of the DARPA Internet Protocols. Proc. ACM SIGCOMM 1988, pp. 106-114.

Review of M/M/1 and variants covered by Prof. Azer Bestavros in CAS CS-350.

Optional / Fun Readings:

bulletDavid D. Clark and Marjory S. Blumenthal. Rethinking the design of the Internet: The end to end arguments vs. the brave new world. Workshop on Policy Implications of End-to-End. December 1, 2000. 
bulletDavid Clark, John Wroclawski, Karen Sollins, Robert Braden. Tussle in Cyberspace: Defining Tomorrow's Internet. ACM SIGCOMM 2002.
bulletP. Molinero-Fernandez, Nick McKeown, and Hui Zhang. Is IP going to take over the world (of communications)? ACM HotNets 2002.
bulletQueueing Analysis by Stallings.

Simulation

Discrete-Event Simulation - skip Section 7 (by Udaya Shankar).

Confidence Intervals, S. Waner, Finite Mathematics and Applied Calculus.

V. Paxson and S. Floyd, Why We Don't Know How to Simulate the Internet, In Proceedings of the Winter Simulation Conference, December 1997.

NS Network Simulator:

bulletHow to run ns on our CS machines
bulletThe ns simulator tutorial: http://www.isi.edu/nsnam/ns/tutorial/index.html
bulletns by example: http://nile.wpi.edu/NS/

Optional Readings:

bulletAlberto Medina, Ibrahim Matta, and John Byers. On the Origin of Power Laws in Internet Topologies. ACM Computer Communication Review, 30(2), April 2000.
bulletNetwork Topology Generators: Degree-Based vs. Structural. H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, W. Willinger. ACM SIGCOMM 2002.

Congestion Control

Van Jacobson and Michael J. Karels. Congestion Avoidance and Control. ACM SIGCOMM 1988, pp. 273-288.

F. P. Kelly, A.K. Maulloo and D.K.H. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society 49 (1998), 237-252. (required reading up to page 3, equation 4)

Kevin Fall and Sally Floyd. Simulation based Comparisons of Tahoe, Reno, and SACK TCP. ACM CCR, July 1996.

Jitendra Padhye, Victor Firoiu, Don Towsley, Jim Kurose. Modeling TCP Throughput: A Simple Model and its Empirical Validation. Proceedings of the ACM SIGCOMM '98. (required reading up to and including section 2.1)

D. Chiu and R. Jain. Analysis of the Increase/Decrease Algorithms for Congestion Avoidance in Computer Networks. Journal of Computer Networks and ISDN, Vol. 17, No. 1, June 1989, pp. 1-14.

S. Floyd and V. Jacobson. Random Early Detection gateways for Congestion Avoidance. IEEE/ACM Transactions on Networking, V.1 N.4, August 1993, p. 397-413.

J. Mo, R. La, V. Anantharam, and J. Walrand. Analysis and Comparison of TCP Reno and Vegas. IEEE INFOCOM 1999.

TCP-friendly Congestion Control for Real-time Streaming Applications, D. Bansal and H. Balakrishnan. In Proceedings of IEEE INFOCOM 2001.

Control Theory Tutorial -- not required: Matlab toolbox, and gain/phase margins and bode tests.

Optional Readings:

bulletF. Kelly. Mathematical modelling of the Internet. In "Mathematics Unlimited - 2001 and Beyond" (Editors B. Engquist and W. Schmid). Springer-Verlag, Berlin, 2001. 685-702.
bulletThe RED Home Page
bulletECN (Explicit Congestion Notification) in TCP/IP
bulletTCP and ECN, ACM CCR, 1994.
bulletThe Vegas Home Page
bulletShudong Jin, Liang Guo, Ibrahim Matta, and Azer Bestavros. TCP-friendly SIMD Congestion Control and Its Convergence Behavior. In IEEE/ACM Transactions on Networking, June 2003.
bulletR. Rejaie, M. Handley, and D. Estrin. RAP: An End-to-End Rate-based Congestion Control Mechanism for Realtime Streams in the Internet. Proc. IEEE Infocom 1999.

Routing

A. Khanna and J. Zinky, A Revised ARPANET Routing Metric, ACM SIGCOMM 1989.

T. Griffin and G. Wilfong. An Analysis of BGP Convergence Properties. ACM SIGCOMM 1999.

Timothy G. Griffin and  Gordon Wilfong,  A Safe Path Vector Protocol, IEEE Infocom 2000.

S. Iyer and S. Bhattacharyya and N. Taft and N. McKeown and C. Diot (2003). An Approach to Alleviate Link Overload as Observed on an IP Backbone. IEEE Infocom. San Francisco. Mar 2003.

David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris. Resilient Overlay Networks. SOSP 2001.

R. Guerin, A. Orda, and D. Williams. QoS Routing Mechanisms and OSPF Extensions. Global Internet 1997.

Optional Readings:

bulletAnindya Basu and Jon Riecke. Stability Issues in OSPF Routing. ACM SIGCOMM 2001.
bulletSelma Yilmaz and Ibrahim Matta. A Randomized Solution to BGP Divergence. CCN'04.
bulletV. Paxson, End-to-End Routing Behavior in the Internet, IEEE/ACM Trans. on Networking, Vol. 5, No. 5, pp. 601-615, October 1997 (Earlier version in Proc. SIGCOMM '96, Stanford, CA, August 1996.)
bulletFloyd, S., and Jacobson, V., The Synchronization of Periodic Routing Messages. IEEE/ACM Transactions on Networking, V.2 N.2, p. 122-136, April 1994.
bulletL. Guo and I. Matta. Search Space Reduction in QoS Routing. In Computer Networks (COMNET), volume 41, issue 1, 15 January 2003, pp. 73-88.
bulletG. Apostolopoulos, R. Guerin, S. Kamat, and S. Tripathi. Quality of Service Routing: A Performance Perspective. ACM SIGCOMM 1998.
bulletW. Zhao and S. Tripathi. Routing Guaranteed Quality of Service Connections in Integrated Services Packet Networks. ICNP 1997.
bulletShi, S and Turner, J. Routing in Overlay Multicast Networks. IEEE INFOCOM 2002.

Wireless Access and Mobility

H. Balakrishnan, S. Seshan, and R. Katz. Improving Reliable Transport and Handoff Performance in Cellular Wireless Networks. ACM Wireless Networks, Dec. 1995.

J. Liu and S. Singh. ATCP: TCP for mobile ad hoc networks. IEEE JSAC 2001.

Karthikeyan Sundaresan, Vaidyanathan Anantharaman, Hung-Yun Hsieh, and Raghupathy Sivakumar.  ATP: A Reliable Transport Protocol for Ad-hoc Networks. MobiHoc 2003.

Optional Readings:

bulletVassilis Tsaoussidis and Ibrahim Matta. Open Issues on TCP for Mobile Computing. Journal of Wireless Communications and Mobile Computing -- Special Issue on Reliable Transport Protocols for Mobile Computing, 2(1), February 2002.
bulletLong Thin Networks, RFC 2757.

Back to course home page
Last updated  Tuesday May 03, 2005