Notes on Routing in Networks

Eva Tardos (eva@cs.cornell.edu)
Computer Science Department,Cornell University

Download slides here (gzipped PostScript file).

The first part of the talk focused on the Disjoint Paths Problem: do there exist disjoint paths connecting a given set of source-sink pairs in a given network? Different variants of the problem were described, varying according to allowed interference of paths (node/edge -disjoint versions). Most of the talk centered on optimization versions of the problem. Two particular objectives discussed were (1) admission control: route as many of the source/sink pairs via disjoint paths and (2) congestion control: route all pairs and minimize the maximum number of paths using an edge (this quantity is called congestion). Since all variants are NP-hard, approximation algorithms are considered.

Two more ways to modify the problem:

  1. adding capacities: up to u(e) paths can share the edge e
  2. online problem: network is given offline but requests for connections arrive online and must be routed immediately. Rerouting is not allowed.

The online problem reminds of Nemhauser's talk and airline recovery problems, but the different versions (online/offline) of routing problems are very interrelated and most frequently same techniques are applicable.

Clarifications of some slides:

On Klein-Plotkin-Stein-Tardos:
edge-costs have a role of putting a penalty on the overload of an edge, so this can be thought of as a kind of Lagrangean relaxation
On the online version (Awerbuch-Azar-Plotkin):
-assume the capacity is the same for all edges
-the real background of this result is that the algorithm can solve linear programs in a combinatorial way
-the admission control result in the online case is best possible on directed graphs because of the online character of the problem (not because of some complexity result)
On approximation results:
there are only a few positive results, and a sense of hopelessness is given by the negative result which says that there is no O(n^e) approximation algorithm for the maximum number of disjoint paths for some e>0.
On the Garg-Vazirani-Yannakakis algorithm
-turning point is defined as the least common ancestor of the source and sink nodes in the rooted tree
-choice of the root is arbitrary!

The next part of the talk, on finding disjoint paths on the mesh, is a survey of the papers of Kleinberg and Tardos, available here

The Summary slide:
The average case results means that the approximation holds for any graph, but requests for routes arrive from a specific distribution which essentially allows the online problem to be treated as if it were offline.
On disjoint paths with no sharing: -can we route trees, short paths, etc?
-the speaker believes this can be done in existing networks, and there is some work in progress but no quantifiable results yet

The second part of the talk was on the Packet Scheduling problem: given a set of packets with their respective origins and destinations, schedule the motion of packets in time. Some requirements are that

  1. all packets between a given origin/destination pair follow the same path
  2. congestion not be too large
  3. (in synchronized networks) there is at most one packet per edge at each time step
The objective is to minimize the total time needed to deliver all packets.

Some papers referred to in the talk:

Prabhakar Raghavan and Clark  D. Thompson  Randomized Rounding: A technique for provably good algorithms and algorithmic proofs,  Combinatorica, Vol. 7, 1987.

Prabhakar Raghavan and Clark D. Thompson   Multiterminal global rounding: A deterministic approximation scheme, Algorithmica, Vol 6, pp 73--82,   1991.

Philip Klein and Serge Plotkin and Clifford Stein and Eva Tardos:     Faster Approximation Algorithms for the Unit-Capacity Concurrent Flow Problem with Applications to     Routing and Finding Sparse Cuts. SIAM J. Comput. 23 (1994), no. 3, 466--487.

B. Awerbuch and Y. Azar and S. Plotkin     Throughput-competitive online routing     34th IEEE Symposium on Foundations of Computer Science, 1993.

Naveen Garg and Vijay V. Vazirani and Mihalis Yannakakis     Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees     Algorithmica, 18(1), pp. 3-20, May 1997.

B. Awerbuch and R. Gawlick and T. Leighton and Y. Rabani     On-Line Admission Control and Circuit Routing for High Performance Computing and Communication     Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 412-423, IEEE     Computer Society Press, November 1994.

Jon Kleinberg and Éva Tardos     Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks     Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing,     pp. 26-35,  29 May - 1. jun 1995.

Jon Kleinberg and Eva Tardos     Disjoint Paths in Densely Embedded Graphs     36th Annual Symposium on Foundations of Computer Science (FOCS'95), pp. 52-61, IEEE Computer     Society Press, October 1995.

Andrei Z. Broder and Alan M. Frieze and Stephen Suen and Eli Upfal     An Efficient Algorithm for the Vertex-Disjoint Paths Problem in Random Graphs     Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 261-268,     ACM/SIAM, 28-30* January 1996.

Anil Kamath and Omri Palmon and Serge Plotkin     Routing and Admission Control in General Topology Networks with Poisson Arrivals     Journal of Algorithms, 27(2), pp. 236-258, May 1998.

Tom Leighton and Bruce Maggs and Satish Rao     Universal Packet Routing Algorithms (Extended Abstract)     29th Annual Symposium on Foundations of Computer Science, pp. 256-269, 24-26 October 1988.

Yuval Rabani and Éva Tardos     Distributed Packet Switching in Arbitrary Networks     Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pp. 366-375,     22-24 May 1996.

Matthew Andrews and Antonio Fernández and Mor Harchol-Balter and Tom Leighton and Lisa Zhang     General Dynamic Routing with Per-Packet Delay Guarantees of $O(\textdistance + 1 / \textsession     rate)$     38th Annual Symposium on Foundations of Computer Science, pp. 294-302, 20-22 October 1997.

T. Leighton and B. Maggs     Fast Algorithms for Finding O(Congestion+Dilation) Packet Routing Schedules     Proceedings of the 28th Annual Hawaii International Conference on System Sciences. Volume 2:     Software Technology, pp. 555-563, IEEE Computer Society Press, January 1995.