Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method.
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 the Kolmogorov random graphs which constitute a fraction of 1 - 1/nc 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 may 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.
Introduction
. In very large communication networks like the global telephone
network or the internet connecting the worlds computers, the message volume
being routed creates bottlenecks degrading performance. We analyze a tiny part of
this issue by determining the optimal space to represent routing schemes in communication
networks for allmost all static network topologies. The results give also the
average space cost over all network topologies.
A universal routing strategy for static communication networks will, for every
network, generate a routing scheme for that particular network. Such a routing scheme
comprises a local routing function for every node in this network. The routing function
of node u returns for every destination v 6= u an edge incident to u on a path from u to
v. This way, a routing scheme describes a path, called a route, between every pair of
nodes u; v in the network. The stretch factor of a routing scheme equals the maximum
ratio between the length of a route it produces, and the shortest path between the
endpoints of that route.
It is easy to see that we can do shortest path routing by entering a routing table
in each node u which for each destination node v indicates to what adjacent node w
a message to v should be routed first. If u has degree d, it requires a table of at most
log d bits 1 and the overall number of bits in all local routing tables never exceeds
The stretch factor of a routing strategy equals the maximal stretch factor attained
A preliminary version of part of this work was presented at the 15th ACM Conf. Principles
Distribut. Comput., Philadelphia, PA, USA, May 1996. All authors were partially supported by
the European Union through NeuroCOLT ESPRIT Working Group Nr. 8556, and by NWO through
NFI Project ALADDIN number NF 62-376.
y CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands; Email: buhrman@cwi.nl.
z KPN Research, P.O. Box 15000, 9700 CD Groningen, The Netherlands; Email:
J.H.Hoepman@research.kpn.com
x CWI and University of Amsterdam. Address: CWI, Kruislaan 413, 1098 SJ Amsterdam, The
Netherlands; Email: paulv@cwi.nl
denotes the binary logarithm.
M. BUHRMAN, J. H. HOEPMAN, AND P. M. B. VIT '
ANYI
by any of the routing schemes it generates. If the stretch factor of a routing strategy
equals 1, it is called a shortest path routing strategy because then it generates for every
graph a routing scheme that will route a message between arbitrary u and v over a
shortest path between u and v.
In a full information shortest path routing scheme, the routing function in u
must, for each destination v return all edges incident to u on shortest paths from u to
v. These schemes allow alternative, shortest, paths to be taken whenever an outgoing
link is down.
We consider point to point communication networks on n nodes described by
an undirected graph G. The nodes of the graph initially have unique labels taken
from a set Edges incident to a node v with degree d(v)
are connected to ports , with fixed labels by a so called port assignment .
This labeling corresponds to the minimal local knowledge a node needs to route: a)
a unique identity to determine whether it is the destination of an incoming message,
b) the guarantee that each of its neighbours can be reached over a link connected to
exactly one of its ports, and c) that it can distinguish these ports.
1.1. Cost Measures for Routing Tables. The space requirements of a routing
scheme is measured as the sum over all nodes of the number of bits needed on each
node to encode its routing function. If the nodes are not labeled with
minimal set of labels-we have to add to the space requirement, for each node, the
number of bits needed to encode its label. Otherwise, the bits needed to represent
the routing function could be appended to the original identity yielding a large label
that is not charged for but does contain all necessary information to route.
The cost of representing a routing function at a particular node depends on the
amount of (uncharged) information initially there. Moreover, if we are allowed to
relabel the graph and change its port assignment before generating a routing scheme
for it, the resulting routing functions may be simpler and easier to encode. On a
chain, for example, the routing function is much less complicated if we can relabel
the graph and number the nodes in increasing order along the chain. We list these
assumptions below, and argue that each of them is reasonable for certain systems.
We start with the three options for the amount of information initially available at a
node.
I Nodes do not initially know the labels of their neighbours, and use ports to
distinguish the incident edges. This models the basic system without prior
knowledge.
IA The assignment of ports to edges is fixed and cannot be altered. This
assumption is reasonable for systems running several jobs where the
optimal port assignment for routing may actually be bad for those other
jobs.
IB The assignment of ports to edges is free and can be altered before computing
the routing scheme (as long as neighbouring nodes remain neighbours
after re-assignment). Port re-assignment is justifiable as a local
action that usually can be performed without informing other nodes.
II Nodes know the labels of their neighbours, and know over which edge to
reach them. This information is for free. Or, to put it another way, an incident
edge carries the same label as the node it connects to. This model is
concerned only with the additional cost of routing messages beyond the immediate
neighbours, and applies to systems where the neighbours are already
COMPACT ROUTING TABLES 3
known for various other reasons 2 .
Orthogonal to that, the following three options regarding the labels of the nodes are
distinguished.
ff Nodes cannot be relabeled. For large scale distributed systems relabeling
requires global coordination that may be undesirable or simply impossible.
Nodes may be relabeled before computing the routing scheme, but the range
of the labels must remain This model allows a bad distributions of
labels to be avoided.
Nodes may be given arbitrary labels before computing the routing scheme,
but the number of bits used to store its label is added to the space requirements
of a node. Destinations are given using the new, complex, labels 3 .
This model allows us to store additional routing information, e.g. topological
information, in the label of a node. This sort of network may be appropriate
for centrally designed interconnect networks for multiprocessors and communication
networks. A common example architecture of this type is the binary
n-cube network where the 2 n nodes are labeled with elements of f0; 1g n such
that there is an edge between each pair of nodes iff their labels differ in exactly
one bit position. In this case one can shortest path route using only the
labels by successively traversing edges corresponding to flipping successive
bits in the positions where source node and destination node differ.
These two orthogonal sets of assumptions IA, IB, or II, and ff, fi, or fl, define the nine
different models we will consider in this paper. We remark that the lower bounds for
models without relabeling are less surprising and less hard to prove than the bounds
for the other models.
1.2. Outline. We determine the optimum space used to represent shortest path
routing schemes on almost all labeled graphs, namely the Kolmogorov random graphs
with randomness deficiency at most c log n which constitute a fraction of at least
of all graphs, for every fixed constant c ? 0. These bounds straightforwardly
imply the same bounds for the average case over all graphs provided we choose c - 3.
For an overview of the results, refer to Table 1 4 .
We prove that for almost all
are necessary to represent the
routing scheme, if relabeling is not allowed and nodes know their neighbours (II -
ff) or nodes do not know their neighbours (IA - IB) 5 . Partially matching this lower
bound, we show that O(n 2 ) bits are sufficient to represent the routing scheme, if the
port assignment may be changed or if nodes do know their neighbours (IB - II). In
2 We do not consider models that give neighbours for free and, at the same time, allow free
port assignment. For, given a labeling of the edges by the nodes they connect to, the actual port
assignment doesn't matter at all, and can in fact be used to represent bits of the
routing function. Namely, each assignment of ports corresponds to a permutation of the ranks of the
neighbours - the neighbours at port i moves to position i. There are d(v)! such permutations.
3 In this model it is assumed that a routing function cannot tell valid from invalid labels, and
that a routing function always receives a valid destination label as input. Requiring otherwise makes
the problem harder.
4 In this table, arrows indicate that the bound for that particular model follows from the bound
found by tracing the arrow. In particular, the average case lower bound for model IA - fi is the
same as the IA - fl bound found by tracing !. The reader may have guessed that a ? marks an
open question
5 We write A - B to indicate that the results hold under model A or model B. Similarly, we
to indicate the result holds only if the conditions of both model A and model B hold
simultaneously. If only one of the two 'dimensions' is mentioned, the other may be taken arbitrary
(i.e., IA is a shorthand for (IA - ff) - (IA - fi) - (IA - fl)).
4 H. M. BUHRMAN, J. H. HOEPMAN, AND P. M. B. VIT '
ANYI
no relabeling permutation free relabeling
worst case - lower bounds
port assignment free
neighbours known (II) (n 2 =9) log n [Thm 4.4]
average case - upper bounds
port assignment fixed (IA) (n 2 =2) log n [Thm 3.6] / /
port assignment free
neighbours known (II) 3n 2 [Thm 3.1] / 6n log 2 n [Thm 3.2]
average case - lower bounds
port assignment fixed
port assignment free
neighbours known (II) n 2 =2 [Thm 4.1] ? ?

Table
Size of shortest path routing schemes: overview of results. The results presented in this paper are
quoted with exact constants and asymptotically (with the lower order of magnitude terms suppressed).
contrast, for almost all graphs, the lower bound rises to asymptotically n 2 =2 log n bits
if both relabeling and changing the port assignment are not allowed (IA - ff), and
this number of bits is also sufficient for almost all graphs. And, again for almost all
graphs, the upper bound drops to O(n log 2 n) bits if nodes know the labels of their
neighbours and nodes may be arbitrarily relabeled (II - fl).
Full information shortest path routing schemes are shown to require, on almost
all graphs, asymptotically n 3 =4 bits to be stored, if relabeling is not allowed (ff), and
this number of bits is also shown to be sufficient for almost all graphs. (The obvious
upper bound for all graphs is n 3 bits.)
For stretch factors larger than 1 we obtain the following results. When nodes
know their neighbours (II), for almost all graphs, routing schemes achieving stretch
factors s with can be stored using a total of O(n log n) bits 6 . Similarly, for
almost all graphs in the same models (II), O(n log log n) bits are sufficient for routing
with stretch factor - 2. Finally, for stretch factors - 6 log n on almost all graphs
again in the same model (II), the routing scheme occupies only O(n) bits.
For worst case static networks we prove, by construction of explicit graphs, a
log n) lower bound on the total size of any routing scheme with stretch factor
nodes may not be relabeled (ff).
The novel incompressibility technique based on Kolmogorov complexity, [9], has
already been applied in many areas but not so much in a distributed setting. A
methodological contribution of this paper is to show how to apply the incompressibility
method to obtain results in distributed computing for almost all objects concerned,
rather than for the worst-case object. This hinges on our use of Kolmogorov random
graphs in a fixed family of graphs. Our results hold also averaged over all objects
concerned.
Independent recent work [8, 7] applies Kolmogorov complexity to obtain related
worst-case results mentioned in next section. They show for example that for each
there exist graphs on n nodes which may not be relabeled (ff), that require in the
worst
bits to store a full information shortest path routing scheme. We
prove for the same model that for almost all graphs full information routing n 3 =4 bits
in total is necessary and sufficient (asymptotically).
6 For Kolmogorov random graphs which have diameter 2 by Lemma 2.6 routing schemes with
are the only ones possible in this range.
COMPACT ROUTING TABLES 5
1.3. Related Work. Previous upper- and lower bounds on the total number of
bits necessary and sufficient to store the routing scheme in worst-case static communication
networks are due to Peleg and Upfal [10], and Fraigniaud and Gavoille [4].
In [10] it was shown that for any stretch factor s - 1, the total number of bits
required to store the routing scheme for some n-node graph is at
and that there exist routing schemes for all n-node graphs, with stretch factor
using O(k 3 n 1+1=k log n) bits in total. For example, with stretch factor
we have method guarantees O(n 2 log n) bits to store the routing
scheme. The lower bound is shown in the model where nodes may be arbitrarily
relabeled and where nodes know their neighbours (II - fl). Free port-assignment in
conjunction with a model where the neighbours are known (II) can, however, not be
allowed. Otherwise, each node would gain n log n bits to store the routing function in
(see the footnote to model II).
Fraigniaud and Gavoille [4] showed that for stretch factors s ! 2 there are routing
schemes that require a total of \Omega\Gamma bits to be stored in the worst case if nodes may
be relabeled by permutation (fi). This was improved for shortest path routing by
Gavoille and P'erenn'es [5] who showed that for each d - n there are shortest path
routing schemes that require a total of \Omega\Gamma n 2 log d) bits to be stored in the worst case
for some graphs with maximal degree d, if nodes may be relabeled by permutation and
the port-assignment may be changed (IB - fi). This last result is clearly optimal for
the worst case, both for general networks (d = \Theta(n)) and bounded degree networks
n). In [7] it was shown that for each d - 3 there are networks for which any
routing scheme with stretch factor ! 2 requires a total of \Omega\Gamma bits.
Interval routing on a graph ng is a routing strategy
where for each node i, for each incident edge e of i, a (possibly empty) set of pairs
of node labels represent disjoint intervals with wrap-around. Each pair indicates the
initial edge on a shortest path from i to any node in the interval, and for each node
there is such a pair. We are allowed to permute the labels of graph G to optimize
the interval setting.
[5] shows that there exist graphs for each bounded degree d - 3 such that for
each interval routing scheme, each of \Omega\Gamma n) edges are labeled by \Omega\Gamma n) intervals. This
shows that interval routing can be worse than straightforward coding of routing tables
which can be trivially done in O(n 2 log d) bits total. (This improves [7] showing that
there exist graphs such that for each interval routing scheme some incident edge on
each of \Omega\Gamma n) nodes is labeled by \Omega\Gamma n) intervals, and for each d - 3 there are graphs
of maximal node degree d such that for each interval routing scheme some incident
edge on each of \Omega\Gamma n) nodes is labeled by \Omega\Gamma n= log n) intervals.)
The paper [3] contains history and background on the compactness (or lack of it) of
interval routing using probabilistic proof methods. To the best of our knowledge, one
of the authors of that paper, Jan van Leeuwen, was the first to formulate explicitly the
question of what exactly is the minimal size of the routing functions, and he recently
drew also our attention to this group of problems.
2. Kolmogorov Complexity. The Kolmogorov complexity, [6], of x is the
length of the shortest effective description of x. That is, the Kolmogorov complexity
C(x) of a finite string x is simply the length of the shortest program, say in
FORTRAN (or in Turing machine codes) encoded in binary, which prints x without
any input. A similar definition holds conditionally, in the sense that C(xjy) is the
length of the shortest binary program which computes x given y as input. It can be
shown that the Kolmogorov complexity is absolute in the sense of being independent
6 H. M. BUHRMAN, J. H. HOEPMAN, AND P. M. B. VIT '
ANYI
of the programming language, up to a fixed additional constant term which depends
on the programming language but not on x. We now fix one canonical programming
language once and for all as reference and thereby C().
For the theory and applications, see [9]. Let x; denotes the natural
numbers. according to the correspondence (0; ffl); (1; 0); (2; 1),
Hence, the length jxj of x is the number of bits in the binary string
x. Let T be a standard enumeration of all Turing machines. Let h\Delta; \Deltai be a
standard invertible effective bijection from N \Theta N to N . This can be iterated to
hh\Delta; \Deltai; \Deltai.
Definition 2.1. Let U be an appropriate universal Turing machine such that
yi. The Kolmogorov complexity of x given y
(for free) is
2.1. Kolmogorov random graphs. One way to express irregularity or randomness
of an individual network topology is by a modern notion of randomness like
Kolmogorov complexity. A simple counting argument shows that for each y in the
condition and each length n there exists at least one x of length n which is incompressible
in the sense of C(xjy) - n, 50% of all x's of length n is incompressible but for
of all x's is incompressible but for 2 bits (C(xjy) -
and in general a fraction of 1 \Gamma 1=2 c of all strings cannot be compressed by more than
c bits, [9].
Definition 2.2. Each labeled graph E) on n nodes ng can
be coded by a binary string E(G) of length n(n \Gamma 1)=2. We enumerate the n(n \Gamma 1)=2
possible edges (u; v) in a graph on n nodes in standard lexicographical order without
repetitions and set the ith bit in the string to 1 if the i-th edge is present and to 0
otherwise. Conversely, each binary string of length n(n \Gamma 1)=2 encodes a graph on n
nodes. Hence we can identify each such graph with its corresponding binary string.
We define the high complexity graphs in a particular family G of graphs.
Definition 2.3. A labeled graph G on n nodes of a family G of graphs has
randomness deficiency at most ffi(n) and is called ffi(n)-random in G if it satisfies
(1)
In this paper we use G is the set of all labeled graphs on n nodes. Then, log
precisely the length of the encoding of Definition 2.2. In the sequel
we say just 'ffi(n)-random' with G understood. Elementary counting shows that a
fraction of at least
of all labeled graphs on n nodes in G has that high complexity, [9].
2.2. Self-Delimiting Binary Strings. We need the notion of self-delimiting
binary strings.
Definition 2.4. We call x a prefix of y if there is a z such that
A ' f0; 1g   is prefix-free, if no element in A is the prefix of another element in A. A
code if its range is prefix-free. A simple prefix-code we use throughout is obtained by
COMPACT ROUTING TABLES 7
reserving one symbol, say 0, as a stop sign and encoding
Sometimes we need the shorter prefix-code x
We call - x or x 0 a self-delimiting version of the binary string x. We can effectively
recover both x and y unambiguously from the binary strings -
xy or x 0 y. For example,
and 1. The self-delimiting form x allows the concatenated binary sub-
descriptions to be parsed and unpacked into the individual items the code
encodes a separation delimiter for x, using 2dlog(jxj bits, and so on,
[9].
2.3. Topological Properties of Kolmogorov Random Graphs. High complexity
labeled graphs have many specific topological properties which seems to contradict
their randomness. However, randomness is not 'lawlessness' but rather enforces
strict statistical regularities. For example, to have diameter exactly two. Note that
randomly generated graphs have diameter two with high probability. In another paper
[2] two of us explored the relation between high probability properties of random
graphs and properties of individual Kolmogorov random graphs. For this discussion it
is relevant to mention that, in a precisely quantified way, every Kolmogorov random
graph individually possesses all simple properties which hold with high probability
for randomly generated graphs.
Lemma 2.5. The degree d of every node of a ffi(n)-random labeled graph on n
nodes satisfies
log n)n
Proof. Assume that there is a node such that the deviation of its degree d from
k. From the lower bound
on C(E(G)jn; ffi; G) corresponding to the assumption that G is random in G, we can
estimate an upper bound on k, as follows:
In a description of E) given n; ffi we can indicate which edges are incident
on node i by giving the index of the interconnection pattern (the characteristic
sequence of the set V bits where the jth bit is 1
in the ensemble of
d
(2)
possibilities. The last inequality follows from a general estimate of the tail probability
of the binomial distribution, with s n the number of successful outcomes in n experiments
with probability of success Namely, by Chernoff's bounds, in the form
used in [1, 9],
To describe G it then suffices to modify the old code of G by prefixing it with
8 H. M. BUHRMAN, J. H. HOEPMAN, AND P. M. B. VIT '
ANYI
(i) A description of this discussion in O(1) bits;
(ii) the identity of node i in dlog(n
(iii) the value of d in dlog(n possibly adding nonsignificant 0's to pad
up to this amount;
(iv) the index of the interconnection pattern in log m bits (we know n; k and
hence log m); followed by
(v) the old code for G with the bits in the code denoting the presence or absence
of the possible edges that are incident on node i deleted.
Clearly, given n we can reconstruct the graph G from the new description. The total
description we have achieved is an effective program of
log m+ log nk
bits. This must be at least the length of the shortest effective binary program, which
is C(E(G)jn; ffi; G), satisfying Equation 1. Therefore,
log
Since we have estimated in Equation 2 that
log
it follows that k -
Lemma 2.6. Every o(n)-random labeled graph on n nodes has diameter 2.
Proof. The only graphs with diameter 1 are the complete graphs which can be
described in O(1) bits, given n, and hence are not random. It remains to consider
E) is an o(n)-random graph with diameter greater than 2. which contradicts
Eq. (1) from some n onwards.
It remains to consider E) is an o(n)-random graph with diameter greater
than 2. Let i; j be a pair of nodes with distance greater than 2. Then we can describe
G by modifying the old code for G as follows:
(i) A description of this discussion in O(1) bits;
(ii) The identities of
(iii) The old code E(G) of G with all bits representing presence or absence of an
edge (j; each k with (i; We know that all the bits
representing such edges must be 0 since the existence of any such edge shows that
is a path of length 2 between i and j, contradicting the assumption that i
and j have distance ? 2. This way we save at least n=4 bits, since we save bits for as
many edges (j; k) as there are edges (i; k), that is, the degree of i, which is n=2 \Sigma o(n)
by Lemma 2.5.
Since we know the identities of i and j and the nodes adjacent to i (they are in the
prefix of code E(G) where no bits have been deleted), we can reconstruct G from this
discussion and the new description, given n. Since by Lemma 2.5 the degree of i is at
least n=4, the new description of G, given n, requires at most
bits, which contradicts Equation 1 for large n.
Lemma 2.7. Let c - 0 be a fixed constant and let G is a c log n-random labeled
graph. Then from each node i all other nodes are either directly connected to i or are
directly connected to one of the least (c nodes directly adjacent to i.
COMPACT ROUTING TABLES 9
Proof. Given i, let A be the set of the least (c nodes directly adjacent
to i. Assume by way of contradiction that there is a node k of G that is not directly
connected to a node in A
fig. We can describe G as follows:
(i) A description of this discussion in O(1) bits;
(ii) A literal description of i in log n bits;
(iii) A literal description of the presence or absence of edges between i and the
other nodes in
(iv) A literal description of k and its incident edges in log n+n
bits;
(v) The encoding E(G) with the edges incident with nodes i and k deleted,
saving at least 2n \Gamma 2 bits.
Altogether the resultant description has
bits, which contradicts the c log n-randomness of G by Equation 1.
In the description we have explicitly added the adjacency pattern of node i, which
we deleted later again. This zero-sum swap is necessary to be able to unambiguously
identify the adjacency pattern of i in order to reconstruct G. Since we know the
identities of i and the nodes adjacent to i (they are the prefix where no bits have been
deleted), we can reconstruct G from this discussion and the new description, given n.
3. Upper Bounds. We give methods to route messages over Kolmogorov random
graphs with compact routing schemes. Specifically we show that in general (on
almost all graphs) one can use shortest path routing schemes occupying at most O(n 2 )
bits. If one can relabel the graph in advance, and if nodes know their neighbours,
shortest path routing schemes are shown to occupy only O(n log 2 n) bits. Allowing
stretch factors larger than one reduces the space requirements-to O(n) bits for
stretch factors of O(log n).
Let G be an O(log n)-random labeled graph on n nodes. By Lemma 2.7 we know
that from each node u we can shortest path route to each node v through the least
O(log n) directly adjacent nodes of u. By Lemma 2.6, G has diameter 2. Once the
message reached node v its destination is either node v or a direct neighbor of node
v (which is known in node v by assumption). Therefore, routing functions of size
O(n log log n) bits per node can be used to do shortest path routing. However, we can
do better.
Theorem 3.1. Let G be an O(log n)-random labeled graph on n nodes. Assume
that the port assignment may be changed or nodes know their neighbours (IB - II).
Then, for shortest path routing it suffices to have local routing functions stored in 3n
bits per node. Hence the complete routing scheme is represented by 3n 2 bits.
Proof. Let G be as in the statement of the theorem. By Lemma 2.7 we know
that from each node u we can route via shortest paths to each node v through the
O(log n) directly adjacent nodes of u that have the least indexes. By Lemma 2.6, G
has diameter 2. Once the message has reached node v its destination is either node v
or a direct neighbor of node v (which is known in node v by assumption). Therefore,
routing functions of size O(n log log n) can be used to do shortest-path routing. We
can do better than this.
Let A 0 ' V be the set of nodes in G which are not directly connected to u. Let
be the O(log n) least indexed nodes directly adjacent to node u (Lemma 2.7)
through which we can shortest path route to all nodes in A 0 . For
M. BUHRMAN, J. H. HOEPMAN, AND P. M. B. VIT '
ANYI
Let l be the first t such that m t ! n= log log n. Then we claim that v t is connected
by an edge in E to at least 1=3 of the nodes not connected by edges in E to nodes
Proof. Suppose, by way of contradiction, that there exists a least t - l such that
Then we can describe G, given n, as follows.
(i) This discussion in O(1) bits;
(ii) Nodes u; v t in 2 log n bits, padded with 0's if need be;
(iii) The presence or absence of edges incident with nodes u;
bits. This gives us the characteristic sequences of A
in V , where a characteristic sequence of A in V is a string of jV j bits with, for each
, the vth bit equals 1 if v 2 A and the vth bit is 0 otherwise;
(iv) A self-delimiting description of the characteristic sequence of A t in A
using Chernoff's bound Equation 3, in at most m
O(log
(v) The description E(G) with all bits corresponding to the presence or absence
of edges between v t and the nodes in A
more, we delete also all bits corresponding to presence or absence of edges incident
with saving a further r bits.
This description of G uses at most
bits, which contradicts the O(log n)-randomness of G by Equation 1, because
n= log log n.
Recall that l is the least integer such that m l ! n= log log n. We construct the
local routing function F (u) as follows.
(i) A table of intermediate routing node entries for all the nodes in A 0 in increasing
order. For each node w in
l
A s we enter in the wth position in the table
the unary representation of the least intermediate node v, with (u; v); (v; w) 2 E,
followed by a 0. For the nodes that are not in
l
A s we enter a 0 in their position
in the table indicating that an entry for this node can be found in the second table.
By Claim 1, the size of this table is bounded by:
l
(ii) A table with explicitly binary coded intermediate nodes on a shortest path
for the ordered set of the remaining destination nodes. Those nodes had a 0 entry in
the first table and there are at most m l ! n= log log n of them, namely the nodes in
l
A s . Each entry consists of the code of length log log n+O(1) for the position
in increasing order of a node out of v
Hence this second table requires at most 2n bits.
The routing algorithm is as follows. The direct neighbors of u are known in node u
and are routed without routing table. If we route from start node u to target node w
which is not directly adjacent to u, then we do the following. If node w has an entry
in the first table then route over the edge coded in unary, otherwise find an entry for
node w in the second table.
COMPACT ROUTING TABLES 11
Altogether, we have jF (u)j - 6n. Adding another n\Gamma1 in case the port assignment
may be chosen arbitrarily, this proves the theorem with 7n instead of 6n. Slightly
more precise counting and choosing l such that m l is the first such quantity ! n= log n
shows jF (u)j - 3n.
If we allow arbitrary labels for the nodes, then shortest path routing schemes of
O(n log 2 n) bits suffice on Kolmogorov random graphs, as witnessed by the following
theorem.
Theorem 3.2. Let c - 0 be a constant and let G be a c log n-random labeled graph
on n nodes. Assume that nodes know their neighbours and nodes may be arbitrarily
relabeled (II - fl), and we allow the use of labels of (1 log n) log n bits. Then
we can shortest path route with local routing functions stored in O(1) bits per node
(hence the complete routing scheme is represented by (c
bits).
Proof. Let c and G be as in the statement of the theorem. By Lemma 2.7 we
know that from each node u we can shortest path route to each node w through the
first (c +3) log n directly adjacent nodes of u. By lemma 2.6, G has
diameter 2. Relabel G such that the label of node u equals u followed by the original
labels of the first (c directly adjacent nodes f(u). This new label occupies
log n) log n bits. To route from source u to destination v do the following.
If v is directly adjacent to u we route to v in 1 step in our model (nodes know their
neighbours). If v is not directly adjacent to u, we consider the immediate neighbours
f(v) contained in the name of v. By Lemma 2.7 at least one of the neighbours of u
must have a label whose original label (stored in the first log n bits of its new label)
corresponds to one of the labels in f(v). Node u routes the message to any such
neighbour. This routing function can be stored in O(1) bits.
relabeling routing using less than O(n 2 ) bits is possible if we allow stretch
factors larger than 1. The next three theorems clearly show a trade-off between the
stretch factor and the size of the routing scheme.
Theorem 3.3. Let c - 0 be a constant and let G be a c log n-random labeled
graph on n nodes. Assume that nodes know their neighbours (II). For routing with
any stretch factor ? 1 it suffices to have nodes with local routing
functions stored in at most dlog(n + 1)e bits per node, and 1+ nodes with
local routing functions stored in 3n bits per node (hence the complete routing scheme
is represented by less than (3c+20)n log n bits). Moreover, the stretch is at most 1.5.
Proof. Let c and G be as in the statement of the theorem. By Lemma 2.7 we know
that from each node u we can shortest path route to each node w through the first
log n directly adjacent nodes v of u. By Lemma 2.6, G has diameter 2.
Consequently, each node in V is directly adjacent to some node in g.
Hence, it suffices to select the nodes of B as routing centers and store, in each node
shortest path routing function F (w) to all other nodes, occupying 3n bits
(the same routing function as constructed in the proof of Theorem 3.1 if the neighbours
are known). Nodes route any destination unequal to their own label to
some fixed directly adjacent node w 2 B. Then jF (v)j - dlog(n
this gives the bit count in the theorem
To route from a originating node v to a target node w the following steps are
taken. If w is directly adjacent to v we route to w in 1 step in our model. If w is not
directly adjacent to v then we first route in 1 step from v to its directly connected
node in B, and then via a shortest path to w. Altogether, this takes either 2 or 3
steps whereas the shortest path has length 2. Hence the stretch factor is at most 1:5
12 H. M. BUHRMAN, J. H. HOEPMAN, AND P. M. B. VIT '
ANYI
which for graphs of diameter 2 (i.e., all c log n-random graphs by Lemma 2.6) is the
only possibility between stretch factors 1 and 2. This proves the theorem.
Theorem 3.4. Let c - 0 be a constant and let G be a c log n-random labeled
graph on n nodes. Assume that the nodes know their neighbours (II). For routing
with stretch factor 2 it suffices to have nodes with local routing functions stored
in at most log log n bits per node and 1 node with its local routing function stored in
3n bits (hence the complete routing scheme is represented by n log log n
Proof. Let c and G be as in the statement of the theorem. By Lemma 2.6, G has
diameter 2. Therefore the following routing scheme has stretch factor 2. Let node 1
store a shortest path routing function. All other nodes only store a shortest path to
node 1. To route from a originating node v to a target node w the following steps are
taken. If w is an immediate neighbour of v, we route to w in 1 step in our model. If
not, we first route the message to node 1 in at most 2 steps, and then from node 1
through a node v to node w in again 2 steps. Because node 1 stores a shortest path
routing function, either or w is a direct neighbour of v.
Node 1 can store a shortest path routing function in at most 3n bits using the
same construction as used in the proof of Theorem 3.1 (if the neighbours are known).
The immediate neighbours of 1 either route to 1 or directly to the destination of the
message. For these nodes, the routing function occupies O(1) bits. For nodes v at
distance 2 of node 1 we use Lemma 2.7, which tells us that we can shortest path
route to node 1 through the first (c directly adjacent nodes of v. Hence, to
represent this edge takes log log n+log(c+3) bits and hence the local routing function
F (v) occupies at most log log n +O(1) bits.
Theorem 3.5. Let c - 0 be a constant and let G be a c log n-random labeled
graph on n nodes. Assume that nodes know their neighbours (II). For routing with
stretch it suffices to have local routing functions stored in O(1) bits
per node (hence the complete routing scheme is represented by O(n) bits).
Proof. Let c and G be as in the statement of the theorem. From Lemma 2.7
we know that from each node u we can shortest path route to each node v through
the first (c directly adjacent nodes of u. By Lemma 2.6, G has diameter 2.
So the local routing function - representable in O(1) bits - is to route directly to
the target node if it is a directly adjacent node, otherwise to simply traverse the first
incident edges of the starting node and look in each of the visited nodes
whether the target node is a directly adjacent node. If so, the message is forwarded
to that node, otherwise it is returned to the starting node for trying the next node.
Hence each message for a destination at distance 2 traverses at most 2(c
edges.
Strictly speaking we do not use routing tables at all. We use the fact that a
message can go back and forth several times to a node. The header of the message
can code some extra information as a tag "failed." In this case it is possible to
describe an O(1) bit size routing function allowing to extract the header from the
destination without knowing about log n, for example by the use of self-delimiting
encoding.
Theorem 3.6. Let G be an O(log n)-random labeled graph on n nodes. Assume
that nodes do not know their neighbors and relabeling and changing the port assignment
is not allowed (IA - ff). Then, for shortest path routing it suffices that each local
routing function uses (n=2) log n(1 bits (hence the complete routing scheme
uses at most (n 2 =2) log n(1 bits to be stored).
Proof. At each node we can give the neighbors by the positions of the 1's in a
COMPACT ROUTING TABLES 13
binary string of length n \Gamma 1. Since each node has at most n=2 neighbours
by Lemma 2.5, a permutation of port-assignments to neighbors can have Kolmogorov
complexity at most (n=2) log n(1 + o(1)) [9]. This permutation - describes part of
the local routing function by for each direct neighbour determining the port to route
messages for that neighbour over. If G is O(log n)-random then we only require O(n)
bits additional routing information in each node by Theorem 3.1. Namely, because
the assignment of ports (outgoing edges) to direct neighbors is known by permutation
- we can use an additional routing table in 3n bits per node to route to the remaining
non-neighbor nodes as described in the proof of Theorem 3.1. In total this gives
Our last theorem of this section determines the upper bounds for full information
shortest path routing schemes on Kolmogorov random graphs.
Theorem 3.7. For full-information shortest path routing on o(n)-random labeled
graphs on n nodes where relabeling is not allowed (ff), the local routing function occupies
at most n 2 =4 bits for every node (hence the complete routing scheme
takes at most n 3 =4 bits to be stored).
Proof. Since for o(n)-random labeled graphs on n the node degree of every node
is 2.5, we can in each source node describe the appropriate
outgoing edges (ports) for each destination node by the 1's in a binary string of
length o(n). For each source node it suffices to store at most n=2 + o(n) such
binary strings corresponding to the non-neighboring destination nodes. In each node
we can give the neighbors by the positions of the 1's in a binary string of length n \Gamma 1.
Moreover, in each node we can give the permutation of port assignments to neighbors
in (n=2) log n(1 bits. This leads to a total of at most (n 2 =4)(1
node and hence to (n 3 =4)(1 bits to store the overall routing scheme.
4. Lower Bounds. The first two theorems of this section together show that
are necessary to route on Kolmogorov random graphs in all models
we consider, except for the models where nodes know their neighbours and label
permutation or relabeling is allowed (II - fi or II - fl). Hence the upper bound in
Theorem 3.1 is tight up to order of magnitude.
Theorem 4.1. For shortest path routing in o(n)-random labeled graphs where
relabeling is not allowed and nodes know their neighbours (II - ff), each local routing
function must be stored in at least n=2 \Gamma o(n) bits per node (hence the complete routing
scheme requires at least n 2 bits to be stored).
Proof. Let G be an o(n)-random graph. Let F (u) be the local routing function
of node u of G, and let jF (u)j be the number of bits used to store F (u). Let E(G)
be the standard encoding of G in n(n \Gamma 1)=2 bits as in Definition 2.2. We now give
another way to describe G using some local routing function F (u).
(i) A description of this discussion in O(1) bits;
(ii) A description of u in exactly log n bits, padded with 0's if needed;
(iii) A description of the presence or absence of edges between u and the other
nodes in V in
(iv) A self-delimiting description of F (u) in jF (u)j
(v) The code E(G) with all bits deleted corresponding to edges (v; w) 2 E for
each v and w such that F (u) routes messages to w through the least intermediary
node v. This saves at least n=2 \Gamma o(n) bits since there are at least n=2 \Gamma o(n) nodes w
such that (u;
2.5, and since the diameter of G is 2 by Lemma 2.6
there is a shortest path (u; v); (v; w) v. Furthermore, we delete all bits
corresponding to the presence or absence of edges between u and the other nodes in
14 H. M. BUHRMAN, J. H. HOEPMAN, AND P. M. B. VIT '
ANYI
saving another bits. This corresponds to the bits for edges connected
to u which we added in one connected block above.
In the description we have explicitly added the adjacency pattern of node u which
explicitly added the adjacency pattern of node u which we deleted elswewhere. This
zero-sum swap is necessary to be able to unambiguously identify the adjacency pattern
of u in order to reconstruct G given n, as follows: Reconstruct the bits corresponding
to the deleted edges using u and F (u) and subsequently insert them in the appropriate
positions of the remnants of E(G). We can do so because these positions can be simply
reconstructed in increasing order. In total this new description has
which must be at least n(n \Gamma 1)=2 \Gamma o(n) by Equation 1. Hence, jF (u)j -
which proves the theorem.
Theorem 4.2. Let G be an o(n)-random labeled graph on n nodes. Assume
that the neighbours are not known (IA - IB) but relabeling is allowed (fl). Then, for
shortest path routing the complete routing scheme requires at least n 2
to be stored.
Proof. In the proof of this theorem we need the following combinatorial result.
2. Let k and n be arbitrary natural numbers such that 1 - k - n. Let x i ,
natural numbers such that x i - 1. If
Proof. By induction on k. If clearly dlog ne -
Supposing the claim holds for k and arbitrary n and x i , we now prove it for
arbitrary x i . Let
. Now
e
By the induction hypothesis the first term on the right-hand side is less than or equal
to
which proves the claim.
Recall that in model fl each router must be able to output its own label. Using
the routing scheme we can enumerate the labels of all nodes. If we cannot enumerate
the labels of all nodes using less than n 2 =32 bits of information, then the routing
scheme requires at least that many bits of information and we are done. So assume
we can (this includes models ff and fi where the labels are not charged for, but can
be described using log n bits). Let G be an o(n)-random graph.
3. Given the labels of all nodes, we can describe the interconnection
pattern of a node u using the local routing function of node u plus an additional
COMPACT ROUTING TABLES 15
Proof. Apply the local routing function to each of the labels of the nodes in turn
(these are given by assumption). This will return for each edge a list of destinations
reached over that edge. To describe the interconnection pattern it remains to encode,
for each edge, which of the destinations reached is actually its immediate neighbour.
If edge i routes x i destinations, this will cost dlog x i e bits. By Lemma 2.5 the degree
of a node in G is at least n=2 \Gamma o(n). Then in total,
bits will be
sufficient; separations need not be encoded because they can be determined using the
knowledge of all x i 's. Using Claim 2 finishes the proof.
Now we show that there are n=2 nodes in G whose local routing function requires
at least n=8 \Gamma 3 log n bits to describe (which implies the theorem).
Assume, by way of contradiction, that there are n=2 nodes in G whose local
routing function requires at most n=8 \Gamma 3 log n bits to describe. Then we can describe
G as follows:
(i) A description of this discussion in O(1) bits,
(ii) The enumeration of all labels in at most n 2 =32 (by assumption),
(iii) A description of the n=2 nodes in this enumeration in at most n bits,
(iv) The interconnection patterns of these n=2 nodes in n=8 \Gamma 3 log n plus n=2+
bits each (by assumption, and using Claim 3). This amounts to n=2(5n=8 \Gamma
3 log n) bits in total, with separations encoded in another n log n bits,
(v) The interconnection patterns of the remaining n=2 nodes only among themselves
using the standard encoding, in 1=2(n=2) 2 bits.
This description altogether uses
bits, contradicting the o(n)-randomness of G by Eq. (1). We conclude that on at least
n=2 nodes a total of n 2 are used to store the routing scheme.
If neither relabeling nor changing the port assignment is allowed, the next theorem
implies that for shortest path routing on almost all such 'static' graphs one
cannot do better than storing part of the routing tables literally, in (n 2 =2) log n bits.
Note that it is known [5] that there are worst-case graphs (even in models where
relabeling is allowed) such that n 2 log are required to store the routing
scheme, and this matches the trivial upper bound for all graphs exactly. But in our
Theorem 4.3 we show that in a certain restricted model for almost all graphs asymptotically
(n 2 =2) log n bits are required and by Theorem 3.6 that many bits are also
sufficient.
Theorem 4.3. Let G be an o(n)-random labeled graph on n nodes. Assume that
nodes do not know their neighbors and relabeling and changing the port assignment
is not allowed (IA - ff). Then, for shortest path routing each local routing function
must be stored in at least (n=2) log bits per node (hence the complete routing
scheme requires at least (n 2 =2) log bits to be stored).
Proof. If the graph cannot be relabeled and the port-assignment cannot be
changed, the adversary can set the port-assignment of each node to correspond to
a permutation of the destination nodes. Since each node has at least n=2 \Gamma o(n)
neighbours by Lemma 2.5, such a permutation can have Kolmogorov complexity as
high as (n=2) log Because the neighbours are not known, the local routing
function must for each neighbor node determine the port to route messages for
that neighbor node over. Hence the local routing function completely describes the
M. BUHRMAN, J. H. HOEPMAN, AND P. M. B. VIT '
ANYI
Fig. 1. Graph G k .
permutation, given the neighbors, and thus it must occupy at least (n=2) log
bits per node.
Note that in this model (IA - ff) we can trivially find by the same method a lower
bound of n 2 log like the complete graph and this
matches exactly the trivial upper bound in the worst case. However, Theorem 4.3
shows that for this model the for almost all labeled graphs asymptotically 50% of this
number of bits of total routing information is both necessary and sufficient.
Even if stretch factors between 1 and 2 are allowed, the next theorem shows that
n) bits are necessary to represent the routing scheme in the worst case.
Theorem 4.4. For routing with stretch factor ! 2 in labeled graphs where relabeling
is not allowed (ff), there exist graphs on n nodes (almost (n=3)! such graphs) where
the local routing function must be stored in at least (n=3) log bits per node at
n=3 nodes (hence the complete routing scheme requires at least (n 2 =9) log
bits to be stored).
Proof. Consider the graph G k with nodes depicted in Figure 1. Each
node v i in v is connected to v i+k and to each of the nodes v . Fix a
labeling of the nodes v with labels from 2kg. Then any labeling of the
nodes with labels from f2k corresponds to a permutation
of f2k vice versa.
Clearly, for any two nodes v i and v j with
the shortest path from v i to v j passes through node v j \Gammak and has length 2, whereas
any other path from v i to v j has length at least 4. Hence any routing function on
G k with stretch factor ! 2 routes such v j from v i over the edge (v at
each of the k nodes v the local routing functions corresponding to any two
labelings of the nodes v are different. Hence each representation of a local
routing function at the k nodes v i corresponds one-one to a permutation
of f2k 3kg. So given such a local routing function we can reconstruct the
permutation (by collecting the response of the local routing function for each of the
nodes grouping all pairs reached over the same edge). The number
of such permutations is k!. A fraction at least 1 \Gamma 1=2 k of such permutations - has
Kolmogorov complexity Because - can be reconstructed
given any of the k local routing functions, these k local routing functions each must
have Kolmogorov complexity k log k \Gamma O(k) too. This proves the theorem for n a
multiple of 3. For use G k , dropping v k and v k\Gamma1 .
COMPACT ROUTING TABLES 17
Note that the proof only requires that there be no relabeling; apart from that the
direct neighbors of a node may be known and ports may be reassigned.
By the above calculation there are at least (1 \Gamma 1=2 n=3 )(n=3)! labeled graphs on
n nodes for which the theorem holds.
Our last theorem shows that for full information shortest path routing schemes
on Kolmogorov random graphs one cannot do better than the trivial upper bound.
Theorem 4.5. For full-information shortest path routing on o(n)-random labeled
graphs on n nodes where relabeling is not allowed (ff), the local routing function occupies
at least n 2 bits for every node (hence the complete routing scheme
requires at least n 3 bits to be stored).
Proof. Let G be a graph on nodes f1; ng satisfying Eq. (1) with
Then we know that G satisfies Lemmas 2.5, 2.6. Let F (u) be the local routing function
of node u of G, and let jF (u)j be the number of bits used to encode F (u). Let E(G)
be the standard encoding of G in n(n \Gamma 1)=2 bits as in Def. 2.2. We now give another
way to describe G using some local routing function F (u).
(i) A description of this discussion in O(1) bits.
(ii) A description of u in log n bits. (If it is less pad the description with 0's.)
(iii) A description of the presence or absence of edges between u and the other
nodes in V in
(iv) A description of F (u) in jF (u)j bits (the logarithmic term
to make the description self-delimiting).
(v) The code E(G) with all bits deleted corresponding to the presence or absence
of edges between each w and v such that v is a neighbour of u and w is not a neighbour
of u. Since there are at least n=2 \Gamma o(n) nodes w such that (u;
E and at least
nodes v such that (u; v) 2 E, by Lemma 2.5, this saves at least (n=2 \Gamma
bits.
From this description we can reconstruct G, given n, by reconstructing the bits corresponding
to the deleted edges from u and F (u) and subsequently inserting them in
the appropriate positions to reconstruct E(G). We can do so because F (u) represents
a full information routing scheme implying that (v; w) 2 E iff (u; v) is among the
edges used to route from u to w. In total this new description has
which must be at least n(n \Gamma 1)=2 \Gamma o(n) by Eq. (1). We conclude that jF
which proves the theorem.
Note that the proof only requires that there be no relabeling; apart from that the
direct neighbors of a node may be known and ports may be reassigned.
5. Average Case. What about the average cost, taken over all labeled graphs of
n nodes, of representing a routing scheme for graphs over n nodes? The results above
concerned precise overwhelmingly large fractions of the set of all labeled graphs. The
numerical values of randomness deficiencies and bit costs involved show that these
results are actually considerably stronger than the corresponding average case results
which are straightforward.
Definition 5.1. For each labeled graph G, let TS (G) be the minimal total
number of bits used to store a routing scheme of type S (where S indicates shortest
path routing, full-information routing, and the like. The average minimal total
number of bits to store a routing scheme for S-routing over labeled graphs on n nodes
is
with the sum taken over all graphs G on nodes f1; ng.
(That is, the uniform average over all the labeled graphs on n nodes.)
M. BUHRMAN, J. H. HOEPMAN, AND P. M. B. VIT '
ANYI
The results on Kolmogorov random graphs above have the following corollaries.
The set of (3 log n)-random graphs constitutes a fraction of at least (1 \Gamma 1=n 3 ) of the
set of all graphs on n nodes. The trivial upper bound on the minimal total number
of bits for all routing functions together is O(n 2 log n) for shortest path routing on
all graphs on n nodes (or O(n 3 ) for full-information shortest path routing). Simple
computation shows that the average total number of bits to store the routing scheme
for graphs of n nodes is (asymptotically and ignoring lower order of magnitude terms
as in

Table

1. - 3n 2 for shortest path routing in model IB - II (Theorem 3.1);
2. - 6n log 2 n for shortest path routing in model II - fl where the average is
taken over the initially labeled graphs on n nodes with labels in f1; ng before
they were relabeled with new and longer labels giving routing information (Theo-
rem 3.2);
3. - 38n log n for routing with any stretch factor s for in model II
(Theorem 3.3);
4. - n log log n for routing with stretch factor 2 in model II (Theorem 3.4);
5. O(n) for routing with stretch factor 6 log n in model II (Theorem 3.5 with
shortest path routing in model ff (Theorem 4.1);
7. shortest path routing in model IA and IB (under all relabeling
conventions, Theorem 4.2);
log n for shortest path routing in model IA - ff (Theorem 3.6 and
Theorem 4.3);
full information shortest path routing in model ff (Theorem 3.7
and Theorem 4.5).
6. Conclusion. The space requirements for compact routing for almost all labeled
graphs on n nodes, and hence for the average case of all graphs on n nodes, is
conclusively determined in this paper. We introduce a novel application of the incompressibility
method. The next question arising in compact routing is the following.
For practical purposes the class of all graphs is too broad in that most graphs have
high node degree (around n=2). Such high node degrees are unrealistic in real communication
networks for large n. The question arises to extend the current treatment to
almost all graphs on n nodes of maximal node degree d where d ranges from O(1) to n.
Clearly, for shortest path routing O(n 2 log d) bits suffice, and [5] showed that for each
there are shortest path routing schemes that require a total of \Omega\Gamma n 2 log d) bits
to be stored in the worst case for some graphs with maximal degree d, where we allow
that nodes are relabeled by permutation and the port-assignment may be changed
This does not hold for average routing since by our Theorem 3.1
bits suffice for (Trivially, O(n 2 ) bits suffice for routing in every graph with
We believe it may be possible to show by an extension of our method that
bits (independent of d) are necessary and sufficient for shortest path routing in
almost all graphs of maximum node degree d, provided d grows unboundedly with n.
Another research direction is to resolve the questions addressed in this paper for
Kolmogorov random unlabeled graphs in particular with respect to the free relabeling
model (insofar as they do not follow a fortiori from the results presented here).

Acknowledgements

. We thank Jan van Leeuwen, Evangelos Kranakis and
Danny Krizanc for helpful discussions, and the anonymous referees for comments
and corrections.
COMPACT ROUTING TABLES 19



--R

Fast probabilistic algorithms for hamiltonian circuits and match- ings
The complexity of interval routing on random graphs
Memory requirement for universal routing schemes

Three approaches to the quantitative definition of information
Lower bounds for compact routing schemes
Compact routing and shortest path information
A trade-off between space and efficiency for routing tables
--TR

--CTR
Ittai Abraham , Cyril Gavoille , Dahlia Malkhi, On space-stretch trade-offs: lower bounds, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
Tamar Eilam , Cyril Gavoille , David Peleg, Average stretch analysis of compact routing schemes, Discrete Applied Mathematics, v.155 n.5, p.598-610, March, 2007
Cyril Gavoille, Routing in distributed networks: overview and open problems, ACM SIGACT News, v.32 n.1, March 2001
Cyril Gavoille , David Peleg, Compact and localized distributed data structures, Distributed Computing, v.16 n.2-3, p.111-120, September
kolmogorov complexity;compact routing tables;average-case complexity;incompressibility method;space complexity;random graphs;routing algorithms;computer networks