Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols

In this paper we present a deterministic protocol for routing arbitrary permutations in arbitrary networks. The protocol is analyzed in terms of the size of the network and the routing number of the network. Given a network H of size n, the routing number of H is defined as the maximum over all permutations ß on [n] of the minimal number of steps to route ß offline in H . We can show that for any network H of size n with routing number R our protocol needs O(log R n \Delta R) time to route any permutation in H using only constant size edge buffers. This significantly improves all previously known results on deterministic routing. In particular, our result yields optimal deterministic routing protocols for arbitrary networks with diameter\Omega\Gamma n ffl ) or bisection width O(n 1\Gammaffl ), ffl ? 0 constant. Furthermore we can extend our result to deterministic compact routing. This yields, e.g., a deterministic routing protocol with runtime O( log n log log n R) for arbitra..