scientific article; zbMATH DE number 1173684

We discuss the following problems: (1) whether, and for which networks, online protocols can reach the best possible time of routing arbitrary permutations; (2) whether, and for which networks, adaptive routing protocols are more efficient than protocols using oblivious routing strategies; (3) whether, and for which networks, randomized routing strategies are more efficient than deterministic routing strategies; and (4) how space limitations at the processors (such as bounded buffers or limited space for storing routing tables) influence the routing time. Concerning the first question, we found out that, given any network of size \(N\) with routing number \(R\) at least \(\Omega(\log^{1+\varepsilon} N)\) for some constant \(\varepsilon> 0\), the online protocol by Ostrovsky and Rabani yield a protocol that can route any permutation in time \(O(R)\), w.h.p., which is optimal in the worst case (and average case). For all bounded degree networks with smaller routing number, replacing the protocol by Ostrovsky and Rabani by the duplication protocol yields a protocol whose runtime deviates by at most a factor of \((\log \log N)^2\) from an optimal runtime of \(O(R)\), w.h.p. It is still an open problem, whether also for these networks a runtime of \(O(R)\) can be reached. Concerning the second question, it follows from above that if random bits are available then for any network with sufficiently large routing number adaptive routing protocols can not beat protocols using oblivious routing strategies. This, however, only holds for the worst case (and average case) time of routing arbitrary permutations. We did not address the problem of reaching the optimal time for any particular permutation. The main obstacle in solving this problem is to construct for any permutation routing problem a path collection that is (asymptotically) optimal. If random bits are not available than oblivious protocols behave very poorly. Here we could show that adaptive protocols can reach much better time bounds. Note that for the case that only a limited randomness is used to choose paths in a given path system, Krizanc proved a general time-randomness tradeoff for the congestion of worst case permutations. Concerning the third question, we could show that for any network with sufficiently large routing number there exists an (asymptotically) optimal deterministic routing strategy for routing arbitrary permutations using only constant size buffers. Hence for these networks and routing problems randomized strategies (asymptotically) can not beat deterministic strategies. For networks with small routing number this is still an open problem. Note that even for the butterfly network it is not known so far how fast deterministic strategies for routing arbitrary permutations can get. We could also advance in answering the fourth question by presenting upper bounds for the relationship between space for storing routing information and the slowdown for routing arbitrary permutations in arbitrary networks.

Recommendations

Cited in

(11)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4397705)