Universal Local Control Packet Switching Algorithms
Rafail Ostrovsky, Bellcore
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, Maggs, and Richa 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. Last year, Rabani and Tardos presented a
randomized local-control algorithm which with high probability
delivers all packets in time
$O\left(C \ + \ D \cdot \\
\left((\log^*N)^{O(\log^*N)}\right) + \right.$ $+\left.(\log N)^6\right)$.
In this paper, we show a nearly optimal local control algorithm for
this long-standing open problem. That is, we show a randomized local
control 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. Our result has
implications to ATM (Asynchronous Transfer Mode) packet switching
algorithms and other applications.
(Joint work with Yuval Rabani)