Optimal routing tables
Harry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitanyi · 1996
The optimal space used to represent routing schemes in communication networks is established, both for worst-case static networks and on the average for all static networks. Several factors may influence the cost of representing a routing scheme for a particular network. It is therefore unavoidable that we first describe several reasonable models in which to measure this cost. Failure to do so in the past has obfuscated previous results. We show that, in most models, for almost all graphs \\Theta(n 2 ) bits are necessary and sufficient for shortest path routing. By `almost all graphs' we mean the Kolmogorov random graphs which constitute a fraction of 1 \\Gamma 1=n c of all graphs on n nodes, where c 3 is an arbitrary fixed constant. In contrast, there is a model that rises the average case lower bound to \\Omega\\Gamma n 2 log n) and another model where the average case upper bound drops to O(n log 2 n). This clearly exposes the sensitivity of such bounds to the model under consi...