Advanced Topics in Computer Science

Prerequisites: None.

The course discusses the design and analysis of algorithms for several problems that arise in the context of high preformance networking technologies. The course focuses on abstract mathematical models that capture some key features of existing and proposed technologies, such as ATM or all-optical networks, but are not limited to the precise details of this or other standard.

The purpose of the course is twofold. Students interested in theory of computation will get a taste of a range of combinatorial and probabilistic techniques through the lens of communication applications. Students interested in communication networks will get a taste of rigorous algorithmic solutions to some network management problems.

The topics studied are roughly divided into three categories: network control, network design, and applications. One major omission from the syllabus is the issue of security. This issue is discussed in other courses given by the department.

Teaching Staff:

- Instructor: Dr. Yuval Rabani

- Lecture 1:
Congestion minimization in virtual circuit routing.
Handout 1: Course outline.

- Lecture 2:
Congestion minimization continued,
throughtput maximization in admission control and virtual
circuit routing.
- Lecture 3:
Throughput maximization continued, admission control and virtual
circuit routing of high bandwidth connections.
- Lecture 4:
Universal packet switching algorithms.
Homework assignment #1 is out.

- Lecture 5:
Universal packet switching algorithms continued.
- Lecture 6:
Universal local-control packet switching algorithms,
scheduling streams of packets.
- Lecture 7:
Stability results in adversarial queueing theory.
Homework assignment #2 is out.

- Lectures 8-9:
End-to-end communication.
- Lecture 10:
Sparse partitions and their construction.
- Lecture 11:
Applications using sparse partitions.
- Lecture 12:
Network design problems.
(Scribe notes are not available.)
- Lecture 13:
Primal-dual algorithms for network design problems.
(Scribe notes are not available.)

- J. Aspens, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts.
On-line
load balancing with applications to machine scheduling and
virtual circuit routing. In Proc. of 25th STOC (1993), pp. 623-631.
- B. Awerbuch, Y. Azar, and S. Plotkin.
Throughput
competitive online routing. In Proc. of 34th FOCS (1993), pp. 32-40.
- Garay, Gopal, Kutten, Mansour, and Yung.
Efficient
on-line call control algorithms
Manuscript.
- B. Awerbuch, Y. Bartal, A. Fiat, and A. Rosen.
Competitive non-preemptive call control.
In Proc. of 5th SODA (1994).
- B. Awerbuch, R. Gawlick, F.T. Leighton, and Y. Rabani.
On-line admission control
and circuit routing for high performance computing and
communication. In Proc. of 35th FOCS (1994).
- Y. Aumann and Y. Rabani.
Improved bounds for all-optical
routing. In Proc. of 6th SODA (1995).
- J. Kleinberg and E. Tardos.
Approximations
for the disjoint paths problem in high-diameter planar networks.
In Proc. of 27th STOC (1995), pp. 26-35.
- J. Kleinberg and E. Tardos.
Disjoint
paths in densely embedded graphs.
In Proc. of 36th FOCS (1995), pp. 52-61.
- F.T. Leighton, B.M. Maggs, and S.B. Rao.
Packet routing and job-shop scheduling in
O(congestion+dilation) steps.
Combinatorica, Vol. 14, No. 2, 1994, pp. 167-180.
- F.T. Leighton, B.M. Maggs, S.B. Rao, and A.G. Ranade.
Randomized routing and sorting on
fixed-connection networks.
Journal of Algorithms, Vol. 17, No. 1, July 1994, pp. 157-205.
- Y. Rabani and E. Tardos.
Distributed packet switching
in arbitrary networks.
In Proc. of 28th STOC (1996).
- R. Cypher, F. Meyer auf der Heide, C. Scheideler, and B. Vocking.
Universal algorithms for store-and-forward and wormhole routing.
In Proc. of 28th STOC (1996).
- A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, and D. Williamson.
Adversarial queueing theory.
In Proc. of 28th STOC (1995), pp. 376-385.
- D.M. Andrews, B. Awerbuch, A. Fernandez, J. Kleinberg, F.T. Leighton,
and Z. Liu.
Universal
stability results for greedy contention-resolution protocols.
In Proc. of 37th FOCS (1996).
- Y. Afek, E. Gafni, and A. Rosen.
The Slide
mechanism with applications in dynamic networks.
In Proc. of PODC '92.
- B. Awerbuch and F.T. Leighton.
A simple approximation algorithm for multicommodity flow, with
applications to on-line packet routing in distributed networks.
In Proc. of 34th FOCS (1993).
- B. Awerbuch and F.T. Leighton.
Improved approximation algorithms for the multi-commodity flow
problem and local competitive routing in dynamic networks,.
In Proc. of 26th STOC (1994).
- B. Awerbuch and D. Peleg.
Sparse partitions.
In Proc. of 31st FOCS (1990).
- B. Awerbuch and D. Peleg.
Online tracking of mobile users.
- Y. Bartal, A. Fiat, and Y. Rabani.
Competitive algorithms for
distributed data management.
J. Comput. System Sci., 51(3):341--358, December 1995.
(Preliminary version in STOC '92)
- M.X. Goemans and D.P. Williamson.
A
general approximation technique for constrained forest problems.
SIAM J. Comput., 24:296--317, 1995.
- M.X. Goemans and D.P. Williamson.
The
primal-dual method for approximation algorithms and its application
to network design problems.
In "Approximation Algorithms," D. Hochbaum, Ed., 1997.

- acn-header.sty: style file for scribe notes.
- sample.tex: sample LaTeX file for scribe notes.

- ATM Networks
- Optical Networking Home Page
- Cornell University OR 739: Selected Topics in Optimization (Algorithmic Aspects of Communication Networks, Spring 1997, given by Eva Tardos)