The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Space-Efficient Routing Tables for Almost All Networks and the Incompressibility Method
Harry Buhrman, Jaap-Henk Hoepman, Paul Vitanyi,
Pages. 1414-1432
Abstract We use the incompressibility method based on Kolmogorov complexity to determine the total number of bits of routing information for almost all network
topologies. In most models for routing, for almost all labeled graphs,
$Theta(n^2)$ bits are necessary and sufficient for shortest path routing. By
""almost all graphs"" we mean that Kolmogorov random graphs which constitute a
fraction 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 rises to
$Omega(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 consideration. If paths have to be short, but need not be shortest
(if the stretch factor many be larger than 1), then much less space is needed on
average, even in the more demanding models. Full-information routing requires
$Theta(n^3)$ bits on average. For worst-case static networks 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.
Contents 1. Introduction
1.1. Cost measures for routing tables
1.2. Outline
1.3. Related work
2. Kolmogorov complexity
2.1. Kolmogorov random graphs
2.2. Self-delimiting binary strings
2.3. Topological properties of Kolmogorov random graphs
3. Upper bounds
4. Lower bounds
5. Average case
6. Conclusion
Key words computer networks, routing algorithms, compact routing, tables, Kolmogorov complexity, incompressibility method, random graphs, average-case complexity, space complexity
Mathmatical Subject Classification 68M10, 68Q25, 68Q30, 68R10, 90