CS536: Data Communications and Computer Networks

Course Information

MWF 12:30p–1:20p
LWSN B134

PSO-P02:
Tue, Haas 257, 9:30a–11:20a

PSO-P01:
Fri, Haas 257, 9:30a–11:20a

Course Contact Email

For corresponance regarding the course, rather than email the professor or TA individually, please email both the professor AND the TA. This will help make sure the course is handled consistently and fairly.

Instructor

Charles Killian
email: ckillian@cs.purdue.edu
phone: 765–807–7996
office: LWSN 1187 office hours: by appointment, drop-ins welcome

Teaching Assistant

Brent Gregory Roth
email: broth at cs

Textbook

James F. Kurose and Keith W. Ross. Computer Networking - A Top Down Approach Featuring the Internet.. 5th Edition.
(Note: students with an earlier edition will probably be OK, but if you are looking to buy the book for yourself, I recommend getting the latest edition. Additionally, the course materials will come from the 5th edition, and may vary a little from earlier editions.)

Announcements

• 2011–11–18: Note: no class next Wednesday or Friday (Thankgiving Break).
• 2011–11–18: HW4 posted, due 12/2.
• 2011–11–04: Midterm grades posted. HW3 Due date moved to 11/14.
• 2011–10–26: Assigned Papers posted through the end of the semester.
• 2011–10–26: HW3 Posted. Due 11/10.
• 2011–10–03: HW2 Posted. Due 10/16. A great way to study for the midterm (the next day).
• 2011–09–26: Programming Assignment 2 Posted. Due 10/24 (but early work rewarded).
• 2011–09–20: HW1 Due date moved to 9/26.
• 2011–09–08: Assigned Papers posted through 10/14.
• 2011–09–08: HW1 Posted. Due 9/21.
• 2011–08–29: Programming Assignment 1 Posted. Due 9/18.
• 2011–08–21: Reading assignment 1 due THIS FRIDAY (8/26). Submit via Blackboard.
• 2011–08–21: No PSOs in week 1 (8/22–8/26). Discussion forums available on Blackboard.
• 2011–08–21: The webpage is created. New content added as available. The book is Kurose-Ross for all those asking.

Course Description

This course is intended to provide a tour through the basic concepts underlying data communications and computer networks with an eye toward research and implementation. The structure and components of computer networks, packet switching, layered architectures, TCP/IP, physical layer, error control, window flow control, local area networks (Ethernet, Token Ring, FDDI), network layer, congestion control, quality of service and so on will be covered in this course.

Pre-requisites

1. This course is focused on the principles of field of computer networks. A major part of this understanding is to learn network programming. The programming language of choice in this course is C; so, if you are unfamiliar with C, please take the undergraduate C programming course before you register for this course. This is a strong requirement and no exceptions will be made at all.

2. CS 354 (undergraduate operating systems) or CS 422 (undergraduate networks) or equivalent courses or experience. While this course will cover the basics of computer networking, it’s task is to prepare you for research in the field of networks. Thus, we will be covering basic material quickly, to enable more of the field to be covered, as well as making room for discussion of classical papers in the field of networking.

   If in doubt, please see me before you register. These courses are not required but no exposure to any of these courses would make it really hard for you to follow the course.

3. Speaking and reading in English. Written and spoken English is essential since most exams will be in English (US or UK should be fine, i.e., you can spell color as color or colour and not be afraid of getting penalized).

Grades

Subject to change.
UPDATED: 22 August, 2011

• 20%: Programming assignments
• 10%: Written homeworks & reading discussion
  • The grade will be computed as follows: HWavg/100 × Reviews/2. Below, the method for computing the review score is given, and has a maximum score of 20.
• 20%: Final project
• 20%: Midterm
  • The grade will be computed as follows: RawMidterm/100 × (15 + Reviews/4). Below, the method for computing the review score is given, and has a maximum score of 20.
• 30%: Final exam
  • The grade will be computed as follows: RawFinal/100 × (25 + Reviews/4). Below, the method for computing the review score is given, and has a maximum score of 20.

Schedule

Updated in an ongoing basis. Note that the paper review schedule is below.

• Week 1 (Aug 24–28): Policies (slides: Policies) Chapter 1/Intro (slides: Chapter 1)
• Week 2–3 (Aug 29-Sept 9): Finish Intro, Chapter 2/Application Layer (slides: Chapter 2)
• Week 4–8 (Sept 12-October 14): Chapter 3/Transport Layer (slides: Chapter 3 TCP Vegas)
  • October 10th: October Break, no class
• Week 9: (Oct 17–19) Tentative Midterm Date
  • (In-class midterm - likely Monday and part of Wednesday)
• Week 9–11: (Oct 21-Nov 4): Chapter 4/Network Layer (slides: Chapter 4 Delayed Convergence Example, see also these slides from the authors at a security class at NorthWestern. For XL, useful slides can be found here)
• Week 12–14: (Nov 7–21) Chapter 5/Link Layer (slides: Chapter 5)
  • Nov 23rd and 25th: Thanksgiving Break, no class
• Week 15: (Nov 28-Dec 2) Finish Link Layer, Discuss Papers (slides: Rethinking…, Floodless in SEATTLE), Physical Layer (slides: Physical Slides Notes on the Physical Layer)
• Week 16: (Dec 5–9) Final Project Presentations and Exam Review (slides: Final Review)

Programming Assignments

There will be two individual programming assigments. The first will be development of a network application such as a web server, and the second will involve development of a network transport protocol. The full details will be released as the assignments are ready.

• Programming Assignment 1: Web Server
• Programming Assignment 2: STCP

Written Homeworks

There will be around four written homeworks this semester. Homeworks must be written up individually. Collaboration on the homeworks is allowed, provided that the homework explicitly state who collaboration was done with, and that the homework is written up completely independently. NOTE: “collaborating” with previous similar solutions is not acceptable (i.e. no sharing of text, solutions, etc.). Homeworks are to be submitted electronically, not by paper. Use either a TXT file or a PDF file. If you need to draw a diagram by hand, that is fine, provided that you scan in the paper and submit it as a PDF.

They will be posted here as they become available:

• Written Homework 1 (Due date moved to 9/26).
• Written Homework 2 (Due 10/16).
• Written Homework 3 (Due date moved to 11/14).
• Written Homework 4 (Due 12/2). Solutions

Reading Discussion

There will be about 1 paper each week. Students will review each paper in an online submission prior to the class in which it is due. This is included as part of the overall homework grade. If you do not have experience reading research papers, this pamphlet may help you figure out how to read research papers efficiently.

Reviews should be submitted via BlackBoard in the appropriate assignment. Reviews are DUE by class time. Reviews should include the following:

• State the main contribution of the paper
• Describe the soundness of the methodology. For example: do the experiments support the conclusions? Are the assumptions practical? Are there other experiments which would have been better? Were there other methodological errors?
• What are the three strongest/most interesting ideas in the paper?
• What are the three biggest weaknesses of the paper?
• What question would you ask the author if seen presented at a conference?

Reviews will be graded on a 0–2 point scale. 0 points will be awarded if there is no submission (or a submission not in good faith). 1 point will be awarded if the submission does not follow the guidelines above. 2 points will be awarded if the review is submitted and meets the guidelines above. The total score for assigned reviews will max out at 20 (in essence, 3 reviews of your choosing may be omitted).

Assigned reviews

• Week 1: (8/26) 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.
• Week 2: (9/2) Akamai tutorial: Globally Distributed Content Delivery, John Dilley et. al., IEEE Computer, 2002.
• Week 3: (9/9) Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan, Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, ACM SIGCOMM 2001, San Deigo, CA, August 2001, pp. 149–160.
• Week 4: (9/16) “Resilient Overlay Networks,” David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris, Proc. 18th ACM SOSP, Banff, Canada, October 2001.
• Week 5: (9/23) “Reverse Traceroute,” E. Katz-Bassett, H. Madhyastha, V. Adhikari, C. Scott, J. Sherry, P. van Wesep, A. Krishnamurthy, T. Anderson USENIX Symposium on Networked Systems Design & Implementation (NSDI), 2010.
• Week 6: (9/30) “Modeling TCP Throughput: A Simple Model and Its Empirical Validation,” by Jitendra Padhye, Victor Firoiu, Don Towsley, and Jim Kurose, Proc. of ACM SIGCOMM 1998.
• Week 7: (10/7) L. S. Brakmo and L. L. Peterson, TCP Vegas: End to End Congestion Avoidance on a Global Internet. IEEE Journal of Selected Areas in Communication, Vol. 13, No. 8, pp. 1465–1480, October 1995.
• Week 8: (10/14) Floyd, Sally; Jacobson, Van (August 1993). “Random Early Detection (RED) gateways for Congestion Avoidance”. IEEE/ACM Transactions on Networking 1 (4): 397–413. doi:10.1109/90.251892
• Week 9: (10/21) No reading assigned.
• Week 10: (10/28) (Accepted until Monday, however). Craig Labovitz, Abha Ahuja, Abhijit Abose, Farnam Jahanian, An Experimental Study of Delayed Internet Routing Convergence. Proc. of Sigcomm, August 2000.
• Week 11: (11/4) XL: An Efficient Network Routing Algorithm, Kirill Levchenko, Geoffrey M. Voelker, Ramamohan Paturi, and Stefan Savage, Proceedings of the ACM SIGCOMM Conference, Seattle, WA, August 2008.
• Week 12: (11/11) Andy Myers, Eugene Ng, Hui Zhang, “Rethinking the Service Model: Scaling Ethernet to a Million Nodes” ACM SIGCOMM HotNets’04
• Week 13: (11/18) Kim, C., Caesar, M., and Rexford, J. 2008. Floodless in seattle: a scalable ethernet architecture for large enterprises. In Proceedings of the ACM SIGCOMM 2008 Conference on Data Communication (Seattle, WA, USA, August 17 - 22, 2008). SIGCOMM ’08. ACM, New York, NY, 3–14. DOI= http://doi.acm.org/10.1145/1402958.1402961
• Week 14: (11/25) No reading assigned. Happy Thanksgiving.
• Week 15: (12/2) Review your topic paper from your final project.
• Week 16: (12/9) No reading assigned.

Final Project

Topics

The networking final project must have a distinct networking component. In particular, security and distributed systems are courses of their own, and so projects of that flavor, with only a minimal network component, should be conducted there. The project topics must be centered on one or more published research papers. To find appropriate papers, you can look at papers published in TON (Transactions on Networking), SIGCOMM, and INFOCOM, or other related networking conferences. In most cases, a well done project has the potential to (with additional work) go on and be published. The end of the project will be a great time to evaluate whether you are interested in continuing the project, and what faculty members might be interested in continued involvement in the project.

In order of desirability (most desirable first), the following are possible types of projects:

• New and novel networking research. This type of project would be to take a new idea of your own, and proceed to prepare a conference submission for the idea. For this course, you would essentially be getting started on the project, and developing the first workshop paper for the idea.
• Measurement project. Rather than designing and implementing some new network functionaity or feature, you could seek to conduct original measurements of real network environments with an eye towards increasing understanding of networks for the purpose of building better networks or better networked systems.
• Renewing a paper. This type of project will involve taking a research paper, and implementing the idea of the paper, and conducting analysis of the idea. Basic analysis would answer the question “is the idea in the paper still true today, if it was ever true?” Extended analysis might include evaluating the paper in new environments or scenarios for which the paper does not describe, to further analyze the applicability of the idea.
• Survey paper. The bar for survey papers is intentionally higher, since this is the one type of project which will not contain a software artifact. To complete a successful survey paper, the authors must do more than just describe a set of related papers, but must do analysis, categorization, comparison, and create taxonomies of the ideas described in the papers. A successful survey paper will allow its readers to easily understand how the surveyed papers fit together in the overal research scope. A survey paper must include at least 8 papers per team member.

See the course slides for details and suggestions.

Deliverables: The final project will be done in groups of 2–3 (no more, no less, except by special exception). We will expect more work from a 3-person project than a 2-person project. The final project deliverables are:

• (10/19) Notify us of your team by email. A short email will suffice, one from each team. After receiving the email, we will create a group in BlackBoard for your team so that future components can be submitted as a team.

• (10/26) A project proposal, submitted to BlackBoard The project proposal should be .5 to 1 page, in extended abstract format. It should contain the title of the project, the team members, a problem statement, a possible approach you can take, and references for the work. If the project is a survey paper, the proposal should contain the references you intend to read for the project (at least 8 papers per project member). You need not have read them, but should have identified what papers you plan to read.

  Teams may wish to meet with the professor prior to the proposal, or he may request meetings after the proposal, to discuss the proposed work and help refine it to a suitable course project. Feel free to email to request such meetings.

• (11/16) A status report, submitted to BlackBoard The status report is essentially an extension and refinement of the proposal. To it should be added a discussion of the work completed thus far, as well as a timeline for the remaining work, including a collaboration plan describing the division of work. Following the status report, the project shepherd will again work with the team to make sure that the work outlined and conducted for the project is both adequately enough for a course project and not too much work to be completed.

• (12/9) The final report, submitted to BlackBoard The final report should be roughly 5–7 pages, in conference style (typeset in 2-column, 9 or 10 point font). The final report should contain sections for Introduction/Motivation/Problem Statement, Challenges/Background/Related Work, Approach/Technique, Results/Evaluation, and Future Work. In a survey paper, the related work section will be of critical importance, and instead of Approach and Results section, you should have a section to present the analysis of the surveyed work, including any taxonomies, categorizations, and comparisons. In all papers, the future work section is important to identify what work remains to turn this paper into a conference submission (should you choose to do so), and also may present ideas for future projects. Note that the SIGCOMM deadline is in late January, and would be an excellent venue for good projects to be submitted with extra work.

• (12/5 and 12/7) The project presentations, in class Presentations will be roughly 10–15 minutes, and will be in class. We will use random assignment to determine the order of presentations. In your presentation you should describe the problem, the approach you took, and the results you have found.

Additional guidelines: The work for this course project is to be conducted between now and the deadline for the project. Work previously conducted is not appropriate for this course, nor is work completed after the semester ends. We welcome projects which you can also use in your research; however, the work done for this course project must not be used toward any other course you are concurrently taking. That includes independent studies. At the same time, however, it may be appropriate to define a larger project for multiple courses, and identify which part of the project is being done for this course.

Resources: In conducting the course projects, you may find that you need resources for running various experiments. Talking to the professor is a great way to find out what resources are available, but in particular, you might expect to be able to use network simulators (NS2, NS3), network emulators (ModelNet), virtual machines, local clusters of machines, PlanetLab, and possibly Amazon’s EC2.

Grading: Subject to change, the grading for the final project is available in the rubric.

Course Mailing-lists

We will sometimes use an ITAP-maintained announce-only mailing list to send announcements to the class. ITAP automatically adds your official Purdue email to the mailing list when you are registered for the class. You should make sure you can receive mail at that address.

Course Policies

See Also: Policies

Late Policy

All assignments are due on the day and time posted. Paper discussion responses may not be turned in late. Written homeworks may be turned in up to 1 day late, and late submissions will be scored out of 90 points instead of 100. On programming assignments only, students may have 6 free late half-days to spread across the two programming assignments as they see fit. After the late time is used up, 10 points will be deducted from the assignment score per day late. No programming assignment will be accepted more than 6 days after the assigned due date.

Ample time is given in advance for assignments, so excuses that you did not have enough will not be considered. Extraordinary circumstances will be considered at the discretion of the professor, contact him if you think these apply to you. If you have forseeable circumstantial problems, the best advise is to get the assignment done early. If that will not be possible, contact the professor.

Emergencies

In the event of a major campus emergency, course requirements, deadlines and grading percentages are subject to changes that may be necessitated by a revised semester calendar or other circumstances. Here are ways to get information about changes in this course. The course web page, the class mailing list, or by contacting the professors directly.

General policies

This course further adheres to the policies posted at http://spaf.cerias.purdue.edu/cpolicy.html. Please familiarize yourself with them.

Special note on academic dishonesty

In particular, note the section on academic honesty. Violations of this policy are treated as very significant, and will be dealt with both through punitive grading and notification to the Dean of Students.