TITLE:A Theoretical Model for Routing Complexity AUTHORS:Pierre Fraigniaud and Cyril Gavoille ABSTRACT: This paper introduces a formal model for studying the complexity of routing in networks. The aim of this model is to capture both time complexity and space complexity. In particular, the model takes into account the input and output facilities of routers. A routing program is a RAM-program with five additional instructions that allow to handle incoming and outgoing headers, and input and output ports. One of these five additional instructions, called release, captures the possible use of hardware facilities to speed up routing.
Using our model, we show that there are routing functions which, if compacted, would require an arbitrarily large computation time to be decoded. The latency is the sum of the time (in bit-operation) required at every intermediate node to establish the route. We also show that, in any $n$-node network of diameter $D$, the latency is bounded by $O(D + n^{1/k}\log n)$, for every constant $k \geq 2$. This latter result has to be compared with the latency of the routing tables which is $\Theta(D\log n)$.