An optimal time bound for oblivious routing (Q908701)

The routing problem is the problem of routing n data packets in a network of n processors. Usually, such a network is assumed to be constant- degree, i.e. each processor is connected to a constant number of other processors. A routing scheme is oblivious if the route taken by each packet depends only on its source and destination. Previous results by Borodin, Hopcroft and Lang show that oblivious routing can be done optimally in \(\theta\) (\(\sqrt{n})\) time. The author considers the case when more than n processors are available; more precisely, he shows that if p processors are available, then oblivious routing can be done in \(\theta\) (n/\(\sqrt{p}+\log n)\) time. Applications of these results are also given.