CS 7270
Network Applications and Services

Spring 2004

TuTh 4:35-5:55

Description
 This course builds on the material covered in CS 6250 (Computer Networks), to provide depth in the upper layer(s) of the protocol stack. The course covers a selection of network applications, services, and some lower-layer mechanisms that support them.  The topics and the reading list may vary from one offering to the next. In Spring 2004, the set of topics will include peer-to-peer and overlay networks, measurement services and methodologies, content distribution networks, security/secure services, and possibly other useful network services. The course material will come primarily from research papers. The course may or may not include substantial programming assignments, depending on the level of TA support that will be provided to the course.
Instructor
Jun (Jim) Xu
Main office: 217 GCATT (250 14th Street), 404-385-2168
Shared CoC office: TBD
Office hours: Immediately after class in the shared CoC office (or by appointment)
jx@cc.gatech.edu

Teaching Assistant: TBA

Newsgroup (tentative)
news:git.cc.class.cs7270
The newsgroup will be used to post class announcements, answer common questions, make corrections to assignments (if needed), and perhaps to conduct further discussions about class material. You should read the newsgroup with some regularity.

Required Background

Students are expected to have had CS 6250 or equivalent. In particular, I will assume that you have a solid grasp of the topics listed below. If you do not have this background, you will find CS 7270 very difficult, and I encourage you to reconsider taking this course until you have this background.

Required background topics:

Basics of TCP, UDP, IP (including routing)
Client/server paradigm
C programming
Sockets programming

Resources

Course Material
This is a paper course. The list of papers will be available later. We will cover the papers in the order they appear on the reading list, with 1-2 papers covered in each class. You are expected to read the paper before it is covered in class. Over the semester, you are required to turn in a short review of three of the papers on the reading list, prior to the class in which we discuss the papers. These reviews will be graded and included in the homework part of your overall grade. More details on the required content of the reviews can be found on the reading list page.

While I will present papers for some weeks, the rest will be presented by students.  The presentations will be evaluated and become a part of your grade (in the homework/project part).  A draft slide will be due to me sometime before the presentation date and feedback will be provided to you before your presentation.  Such training on research presentations will benefit you in future oral/proposal/defense.

Sockets Information
We will not be covering sockets programming in class, though feel free to post questions about the sockets interface to the news group. If you are unfamiliar with sockets programming, the following on-line tutorials will get you started.

RPI Sockets Tutorial (strongly recommended)
Jim Frost's BSD Sockets Primer (recommended; sockets by analogy to telephones)
Berkeley UNIX System Calls and Interprocess Communication, L. Besaw, with revisions by M. Solomon (recommended)
UNIX Socket FAQ

Grading and Academic Honesty

Your grade will be determined by your performance on homework assignments (including short reviews of papers on the reading list), participation in class, and the midterm exam. The tentative weights are as follows:
Class participation - 5%
Homework/Projects - 60%
Midterm exam (scheduled in April) - 35%
Students are expected to abide by the Georgia Tech Honor Code. Honest and ethical behavior is expected at all times. All incidents of suspected dishonesty will be reported to and handled by the office of student affairs. You are to do all assignments yourself, unless explicitly told otherwise. You may discuss the assignments with your classmates, but you may not copy any solution (or part of a solution) from a classmate.

Syllabus

The tentative order of topics is listed below. Please see the reading list for the specific papers you are responsible for on each day of class. Note that the schedule is subject to change.
Introduction to the course
Peer-to-peer and overlay networks (3 weeks)
Other ......


Schedule

You need to read the assigned papers before the class.


Jan. 6 

Reading assignment:

Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications.
Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan,.
To Appear in IEEE/ACM Transactions on Networking.

A Scalable Content-Addressable Network
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker
In Proceedings of ACM SIGCOMM 2001. 

Jan. 8

Reading assignment:

On the Fundamental Tradeoffs between Routing Table Size and Network Diameter in Peer-to-Peer Networks.
Xu, J., Kumar, A., and Yu, X.
accepted to IEEE Journal on Selected Areas in Communications. (A preliminary version appeared in IEEE Infocom 2003). 

Jan. 13

Lecture:

Overlay Networks: Distributed Hash Tables.
Kevin LaiXu, J., Kumar, A., and Yu, X.
Lecture slides in CS268 at Berkeley, Spring 2002. 

Reading assignment:

Ulysses: A Robust, Low-Diameter, Low-Latency Peer-to-peer Network.
Xu, J., Kumar, A., and Yu, X.
IEEE ICNP 2003. 

Jan. 15

Lecture:

On the Fundamental Tradeoffs between Routing Table Size and Network Diameter in Peer-to-Peer Networks.  (Slides)
Xu, J., Kumar, A., and Yu, X.
accepted to IEEE Journal on Selected Areas in Communications. (A preliminary version appeared in IEEE Infocom 2003).

Chord (cont'd)

Jan. 20

Lecture:

Ulysses: A Robust, Low-Diameter, Low-Latency Peer-to-peer Network. (Slides)
Xu, J., Kumar, A., and Yu, X.
IEEE ICNP 2003. 

Jan. 22

Lecture:

Simple Load Balancing for Distributed Hash Tables.
John Byers, Jeffrey Considine, Michael Mitzenmacher
IPTPS '03.

Koorde: A Simple Degree-optimal Hash Table.
Frans Kaashoek, David R. Karger
IPTPS '03.

Jan. 27

Lecture:

Replication Strategies in Unstructured Peer-to-Peer Networks
Edith Cohen and Scott Shenker.
Sigcomm '02

Jan. 29

Lecture:

Practical Network Support For IP Traceback.
Stefan Savege, David Wtherall, Anna Karlin, Tom Anderson
Sigcomm'00.

Advanced and Authenticated Marking Schemes for IP Traceback.
Dawn Xiaodong Song (University of California at Berkeley), Adrian Perrig (University of California at Berkeley)
Infocom'01.

Feb. 3

Lecture:

Large-Scale IP Traceback in High-Speed Internet: Practical Techniques and Theoretical Foundation
Jun Li, Minho Sung, Jun Xu, et al.
IEEE S&P'04.

Hash-Based IP Traceback.
Alex C. Snoeren, Craig Partridge,  et al.
Sigcomm'01.

Feb. 5

Lecture:

IP Traceback-based Intelligent Packet Filtering: A Novel Technique for Defending Against Internet DDoS Attacks.
Minho Sung, Jun Xu
JSAC'03.

Feb. 12

Lecture:

Pi: A Path Identification Mechanism to Defend against DDoS Attacks.
Avi Yaar, Dawn Xiaodong Song , Adrian Perrig
IEEE S&P'03.

Feb. 17

Lecture:

On the Design and Performance of Prefix-Preserving IP Traffic Trace Anonymization.
Jun Xu, Jinliang Fan, Mostafa Ammar, Sue Moon
ICNP'02.

Feb. 19

Lecture:

Data Streaming Algorithms for Efficient and Accurate Estimation of Flow Size Distribution.
Abhishek Kumar, Minho Sung, Jun Xu, Jia Wang
SIGMETRICS'04.

Feb. 24

Lecture:

Space-Code Bloom Filter for Efficient Per-Flow Traffic Measurement.
Abhishek Kumar, Jun Xu, Li Li, Jia Wang
Infocom'04.

Feb. 26

Lecture:

Bitmap Algorithms for Counting Active Flows On Hight speed links.
Cristian Estan, George Varghese, Mike Fisk
IMC'03.

Mar. 2

Lecture:

Efficient Implementation of a Statistics Counter Architecture.
Sriram Ramabhad, George Varghese
Sigmetrics'03.

 New Directions in Traffic Measurement and Accounting.
Cristian Estan, George Varghese
Sigcomm'02.

Mar. 4

Lecture:

Estimating Flow Distributions from Sampled Flow Statistics.
Nick Duffield, Castern Lund, Mikkel Thorup
Sigcomm'03.

Mar. 16

Lecture is cancelled -- Students should spend time reading and reviewing the papers that have been  covered.

Mar. 18

Lecture:

Cost-Effective Flow Table Designs for High-Speed Internet Routers: Architecture and Performance Evaluation.
Jun Xu, M Singhal
IEEE Transactions on Computers, 2002.
TAKE-HOME MIDTERM EXAM (New!)

Mar. 25

Lecture:

Efficient fair queuing using deficit round-robin.
M. Shreedhar, G. Varghese
IEEE Transactions on Networking, 1996.

Mar. 30

Lecture:

Service Disciplines for Guaranteed Performance Service in Packet-Switching Networks.
H.Zhang
IEEE Proceedings of the IEEE, 1995.

A generalized processor sharing approach to flow control in integrated services networks : The Single-Node case.
A. Parekh and R. Gallager.
IEEE Transacting on Networking, 1993.

Apr. 1

Lecture:

WF2Q : Worst-case Fair Weighted Fair Queueing.
J. Bennett, H. Zhang
IEEE Infocom, 1996.

Latency-Rate Servers: A General Model for Analysis of Traffic Scheduling Algorithms.
D. Stiliadis, A. Varma
IEEE Transaction on Networking, 1998.

Apr. 6,

Lecture (Student Presentation) :

Making Gnutella-like P2P Systems Scalable.
Yatin Chawathe, Sylvia Ratnasamy, Lee Breslau
Sigcomm'03
Presented by Feng Li (Slides)

Georgraphic Routing without Location Information.
Ananth Rao, Sylvia Ratnasamy, Christos Papadimitriou, Scott Shenker, Ion Stoica
Mobicom'03
Presented by  Sanjeev Dwivedi (Slides)

Apr. 8,

Lecture (Student Presentation) :
On the Constancy of Internet Path Properties.
Yin Zhang, Nick Duffield, Vern Paxon and Scott Shenker
IMW'01
Presented by Zhongtang Cai (Slides)

Apr. 15,

Lecture :

Discuss the midterm exam

Apr. 20,

Lecture :
On Fundamental Tradeoffs between Delay Bounds and Computational Complexity in Packet Scheduling Algorithms.
Jun Xu, Richard Lipton
Sigcomm'02

Apr. 22,

Lecture :
On the Computational Complexity of Maintaining GPS Clock in Packet Scheduling.
Qi Zhao, Jun Xu
Infocom'04

Note: The term report is due on April 30 4:00 PM.