236604
Advanced Topics in Computer Science
236604 is a graduate course given at the
Technion's
Computer Science
Department. The topics studied vary from year to year.
The 1996-7 Winter Semester course presents
algorithmic issues in high-performance networks.
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:
Meets on: Thursdays, 12:30-14:30, 104 Ullman.
Lectures
Warning: some of the notes need revision.
- 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.)
Some relevant papers (links supplied when the paper is available
on-line at an author's site):
- 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.
Useful Files
Relevant Sites