**
Universal O(congestion+dilation+\log^{1+\epsilon} N)
Local Control Packet Switching Algorithm
**

*
Rafail Ostrovsky, Yuval Rabani
*

**
Abstract:
**

In 1988, Leighton, Maggs and Rao proved a much celebrated result: that for any network, given any collection of packets with a specified route for each packet, there exists an "optimal" schedule for all these packets. That is, there exists a schedule of the motion of the packets such that at each step, every edge is crossed by at most one packet, and all the packets are delivered to their destinations in O(C + D) steps, where C is the "congestion" (i.e., the maximum number of paths that share the same edge), and D is the "dilation" (i.e., the length of the longest path). The proof was non-constructive and relied on Lov\'asz Local Lemma. In a followup paper, Leighton and Maggs gave a centralized algorithm for finding the schedule. The original paper left open the question whether there exists a constructive distributed "on-line" algorithm with the same optimal performance.

In this paper, we show a nearly optimal **local control** algorithm for
this long-standing open problem. We show a randomized algorithm which
for any network topology delivers all the packets to their
destinations in time O(C + D + \log^{1+\epsilon}N) with
high probability, where N is the size of the problem, and
\epsilon>0 is arbitrary.

**comment:**
Appeared
In
Proceedings of
The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97)

Fetch PostScript file of the paper Fetch PDF file of the paper

Back to Publications List |