Space-efficient routing tables for almost all networks and the incompressibility method

We use the incompressibility method based on Kolmogorov complexity to deter mine the total number of bits of routing information for almost all network topologies. In most models for routing, for almost all labeled graphs, The ta(n(2)) bits are necessary and sufficient for shortest path routing. By "a lmost all graphs" we mean the Kolmogorov random graphs which constitute a f raction of 1 ? 1/n(c) of all graphs on n nodes, where c > 0 is an arbitrary fixed constant. There is a model for which the average case lower bound ri ses to Omega(n(2) log n) and another model where the average case upper bou nd drops to O(n log(2) n). This clearly exposes the sensitivity of such bou nds to the model under consideration. If paths have to be short, but need n ot be shortest (if the stretch factor may be larger than 1), then much less space is needed on average, even in the more demanding models. Full-inform ation routing requires Theta(n(3)) bits on average. For worst-case static n etworks we prove an Omega(n(2) log n) lower bound for shortest path routing and all stretch factors < 2 in some networks where free relabeling is not allowed.