Algorithmic Problems in Communication Networks
(236603 - Advanced Topics in CS)
Place and Time: Taub 8, Mon. 14:30-16:30 (term A 2000/2001)
Description, prerequisites, requirements: Hebrew (will be handed
in class); English
Translation (.ps)
Lectures
(please read
the notes with a grain of suspicion...)
-
30/10 - motivation; approximation algorithms; on-line algorithms
-
6/11 - (notes)
the call admission and routing problem; the maximum edge disjoint paths
problem; AAP
-
13/11 - (refs)
off-line approximations: Raghavan-Thompson; on-line approximations: O(log
n) for trees
-
20/11 - (refs)
on-line approximations: O(log D) for trees with high probability; varying
profits
-
27/11 - (notes)
on-line approximations: varying profits and durations; lower bounds
-
4/12 - (refs)
packet switching networks; Leighton-Maggs-Rao
-
11/12 - (notes)
dynamic problems in packet switching networks; adversarial models;
results for DAGs
-
18/12 - (refs)
universal stability of the ring; non-stable examples on the ring
for r=1
-
25/12 - (notes)
stability of FTG with r=1; characterization of universally stable networks
(start)
-
1/1 - (refs)
characterization of universally stable networks; FIFO is not universally
stable (with r<1)
-
8/1 - (refs)
universal stability of LIS; LIS on DAGs
-
22/1 - (refs)
models for worst-case analysis of packet switching; adaptive routing and
scheduling (start)
-
25/1 - (refs)
adaptive routing and scheduling
-
29/1 - open problems
Resources
style
file for class notes
template
for class notes
example of notes (from another course) (notes)(.tex
[for Latex2e])