The Compactness of Interval Routing.
The compactness of a graph measures the space complexity of its shortest path routing tables. Each outgoing edge of a node x is assigned a (pairwise disjoint) set of addresses, such that the unique outgoing edge containing the address of a node y is the first edge of a shortest path from x to y. The complexity measure used in the context of interval routing is the minimum number of intervals of consecutive addresses needed to represent each such set, minimized over all possible choices of addresses and all choices of shortest paths. This paper establishes asymptotically tight bounds of n/4 on the compactness of an n-node graph. More specifically, it is shown that every n-node graph has compactness at most n/4+o(n), and conversely, there exists an n-node graph whose compactness is n/4 - o(n). Both bounds improve upon known results. preliminary version of the lower bound has been partially published in Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci. 1300, pp. 259--268, 1997.)
Introduction
An interval routing scheme is a way of implenting routing schemes on arbitrary
networks. It is based on representing the routing table stored at each node in a
compact manner, by grouping the set of destination addresses that use the same
output port into intervals of consecutive addresses. A possible way of representing
such a scheme is to use a connected undirected labeled graph, providing the
underlying topology of the network. The addresses are assigned to the nodes,
and the sets of destination addresses are assigned to each endpoint of the edges.
As originally introduced in [17], the scheme required each set of destinations to
consist of a single interval. This scheme was subsequently generalized in [18] to
allow more than one interval per edge.
Formally, consider an undirected n-node graph E). Since G is undi-
rected, each edge fu; vg 2 E between u and v can be viewed as two arcs, i.e., two
ordered pairs, (u; v) and (v; u). The graph G is said to support an interval routing
scheme (IRS for short) if there exists a labeling L of V , which labels every node
by a unique integer taken from labeling I of the outgoing edges,
which labels every exit endpoint of each arc of E by a subset of
that between any pair of nodes x 6= y there exists a path
satisfying that L(y) 2 I(u 1g. The resulting
routing scheme, denoted is called a k-interval routing scheme (k-IRS
for short) if for every arc (u; v), the collection of labels I(u; v) assigned to it is
composed of at most k intervals of consecutive integers (1 and n being considered
as consecutive).
The standard definition of k-IRS assumes a single routing path between any
two nodes. It therefore forces any two incident arcs e 6= e 0 to have disjoint labels,
Here we assume that a given destination may belong
to many labels of different arcs incident to a same node. This freedom allows
us to implement some adaptive routing schemes, and code for example the full
shortest path information, as does the boolean routing scheme [4]. Our upper
and lower bounds apply also to the recent extension of interval routing known as
multi-dimensional interval routing [3].
To measure the space efficiency of a given IRS, we use the compactness mea-
sure, defined as follows. The compactness of a graph G, denoted by IRS(G), is
the smallest integer k such that G supports a k-IRS of single shortest paths, that
is, a k-IRS that provides only one shortest path between any pair of nodes.
If the degree of every node in G is bounded by d, then a k-IRS for G is
required to store at most O(dk log n) bits of information per node (as each set
I(e) can be coded using 2k log n bits 2 ), and O(km log n) bits in total, where m
2 A more accurate coding allows to use only O(dk log (n=k)) bits per node, cf. [7].
is the total number of edges of the graph. The compactness of a graph is an
important parameter for the general study of the compact routing, whose goal is
to design distributed routing algorithms with space-efficient data structures for
each router.

Figure

1 shows an example of a 2-IRS on a graph G. For instance, arc (7; 1) is
assigned two intervals: I(7; 5g. Whereas it is quite easy to verify that
this labeling is a single shortest path for G, it is more difficult to check whether
G has compactness 1. Actually, in [9] it is shown that 2. Recently,
it was proven in [1] that for general graphs, the problem of deciding whether
[3,5]
[1][5]
[2,3]
[2,3] [6,7]
[1,2][5]
[3,4][6]

Figure

1: A 2-IRS for a graph G.
The compactness of many graph classes has been studied. Its value is 1
for trees [17], outerplanar graphs [6], hypercubes and meshes [18], r-partite
graphs [12], interval graphs [16], and unit-circular graphs [5]. It is 2 for tori [18],
at most 3 for 2-trees [16], and at most 2
n for chordal rings on n nodes [15]
(see [7] for a survey of recent State-of-the-Art). Finally, it has been proved that
compactness \Theta(n) might be required [9].
The next section presents the results of the paper. In Section 3 we prove
that are always sufficient, and in Section 4 that n=4 \Gamma o(n)
intervals might be required. We conclude in Section 5.
2 The Results
Clearly, the compactness of a graph cannot exceed n=2, since any set I(e) ae
ng containing more than n=2 integers must contain at least two consecutive
integers, which can be merged into a same interval. On the other hand
it has been proved in [9] that for every n - 1 there exists a n-node graph of
compactness at least n=12, and n=8 for every n power of 2.
In this paper we close this gap, by showing that n=4 is asymptotically a tight
bound for the compactness of n-node graphs. More specifically:
Theorem 1 Every n-node graph G satisfies
Theorem 2 For every sufficiently large integer n, there exists an n-node graph
G such that
Moreover, G has diameter 2, maximum degree at most n=2, and fewer than
edges, and every single k-IRS on G with k ! IRS(G) contains
some routing path of length at least 3.
We later show that both the upper and the lower bounds hold even if the
single and/or shortest path assumptions are relaxed.
Theorem 1 improved directly the results of [5, Theorem 11], of [3, Theorem 2],
and also a result of [2, Theorem 9].
The lower bound is proved using Kolmogorov complexity. As a result, only
the existence of such a worst-case graph G can be proved. Moreover, the bound
gives an asymptotic bound since the Kolmogorov complexity is defined up to a
constant. This is in contrast to the technique of [9], which gave explicit recursive
constructions of worst-case graphs of compactness n=12, for every n - 1.
3 The Upper Bound
The basic idea for the upper bound, and partially for the lower bound, is to give
a boolean matrix representation M(R) for a given k-IRS on a graph
E). Recall that for each arc e, I(e) is the set of addresses that labels
the arc e. Let u e be the characteristic sequence of the subset I(e) in
namely, the ith element of u e is 1 if i 2 I(e), and 0 otherwise. It is easy to see
that there is a one-to-one correspondence between the intervals of I(e) and the
blocks of consecutive ones in u e . The number of blocks of consecutive ones in u e
can be seen as the occurence number of 01-sequences 3 in the binary vector u e .
By collecting all the u e 's sequences in order to form a boolean matrix M(R) of
dimensions n \Theta 2jEj, the problem of finding a node-labeling L of G such that
each set I(e) is composed of at most k intervals is equivalent to the problem of
finding a row permutation of M(R) such that every column has at most k blocks
of consecutive ones.
Throughout this section, M denotes a boolean matrix of n rows and p columns.
For every column u of M , and for every row permutation -, we denote by c(u; -)
the number of blocks of consecutive ones in the column u under -. For every
matrix M , define the compactness of M , denoted comp(M ), as the smallest
integer k such that there exists a row permutation - of M satisfying, for every
column u of M , c(u; - k.
The following theorem is the key of the proof of Theorem 1.
Theorem 3 Let M be an n \Theta p boolean let u be a column of
M , and let A u kg be the set of row permutations of M that
provides k blocks of consecutive ones for the column u. Then for every integer k
in the range n=4
jA
Proof. Let us consider a column u of M and an integer k. Let a (respectively, b)
be the number of 0's (resp., 1's) of u. Clearly, if a ! k or b ! k, the theorem holds
because in this case A u Hence suppose a; b - k, with a There
are a! permutations of the rows fx containing 1, and b! permutations
of the rows fy containing 0 in u, and each such pair of permutations
creates a different and disjoint set of permutations in A u (k). Moreover, each of
the a! permutations needs to be broken into k non-empty blocks, which can be
done in
a
ways, and similarly for the b! permutations of the rows fy g.
Each partitioned pair can be merges, alternating a block of 1's and a block of 0's,
in order to yield a permutation in A u (k). Overall, jA u
i a
, and we
need to show that
a!
a
pn
Using Formula (9.91) of [11] on page 481, derived from Stirling's formula, we have
for every n - 1, ' n
e
e
3 If u e does not contain any 0, u e is composed of exactly one block of consecutive ones.
\Gamman 4
2-n
\Gamman 4
From Stirling's bound, for every k in the range
a
' a
s
a
This bound cannot apply for us first handle the extremal cases.
3.1 Inequality (1) holds for
n=2.
Proof. In both cases assumed in the claim, Inequality (1) is equivalent to
pn 3=2
The ratio (n Indeed, in this range
It is thus sufficient to prove Inequality (4) for n=2, in which case it becomes
pn
Using Stirling's bound, (n=2)! 2 ! (n=2) n e \Gamman simplifying with the lower
bound of Inequality (2), we get that to prove Inequality (5) it suffices to prove
This last inequality is satisfied for every n - 1, since
is equivalent to n=2 ! n(ln which is trivial because
This completes the proof of Claim 3.1. 2
For the remainder of the proof, let us assume that k ! a; b. Therefore, it is
possible to apply the bound of Inequality (3), which gives
a!
a
! a a
' a
ab e \Gamman fl 4
3.2 For every integers k, a, b and n such that a and a
ab
Proof. Set
ab
f(a)
Observing that ab - (a suffices to prove that
f(a)
Let us lower bound the term k
f(a). Noting that f(a) is symmetric around the
point n=2, let us assume without loss of generality that a - n=2. In this range
in the desired range f(a) attains its minimum where a
is minimum, and thus k
which is of the same sign that n \Gamma 3k. Hence in
the range first decreases until its minimum at the point n=3,
then increases between n=3 and n=2. So, f 2 Therefore
f(a)
which completes the proof of Claim 3.2. 2
In view of Claim 3.2, Inequality (6) becomes
a!
a
! a a
' a
e \Gamman fl 4 3
Simplifying and applying the lower bound of Inequality (2), we obtain that to
prove Inequality (1) it suffices to show:
a a
' a
pn
Noting that 16
remains to prove that
Assume that k
(pn). The case b - a is dual, and at most doubles the number of
permutations (which is taken in account in the removing of the multiplicative
constant 5.57 in Inequality (7)).
To establish Inequality (7) and complete the proof, it remains only to show the
following lemma.
Lemma 3.3 f(a) ? 0 in the range k
Proof. Write
remains to
prove that f 2 (a) ? 0 in the range k n=2. The first derivative of f 2 is
a
in the range k
Proof. It suffices to show that in the range specified in the claim,
a
or
This is shown by noting that f 3 (a) is increasing in this range, hence its maximum
is attained at the point To show that f 3 (a)
is increasing, we need to show that f 3
range. This is shown by noting that f 3
0 (a) is decreasing in this range, hence its
minimum is attained at the point
To show that f 3
0 (a) is decreasing, we need to show that
this range, which is trivial since a - n=2. This completes
the proof of Claim 3.4. 2
It follows from Claim 3.4 that f 2 (a) is decreasing in this range, and hence its
minimum is attained at a = n=2. Hence in this range,
Consequently, it remains to prove that f 2 (n=2) ? 0 in the desired range. Sim-
plifying, we need to show that k 2k (n \Gamma in the range
we need to prove that
or that
2ff log ff
log (pn)
in the range k 0 =n ! ff ! 1=2 (the function log represents logarithm to base 2).
It remains to prove the
following claim.
log (pn)
n in the range
Proof. Note that k 0
. So, if
thus the range for ff is not empty. Moreover,
In the range 1=4 us show that g 000 (ff) ? 0. This happens
which is trivial since ff ? 1=4. Moreover
2. Thus we have the following bound for g(ff):
So, it suffices to take ff such
log (pn)
s
to complete the proof of Claim 3.5. 2
This completes also the proof of Lemma 3.3, and subsequently of Theorem 3. 2 2
Corollary 3.6 Let M be an n \Theta p boolean
2n
Proof. We need to show that there exists a row permutation - of M , such
that c(u; -)
2n ln (pn) for every column u of M . Let us set
permutation - is said to be "bad" if there exists
a column u of M such that c(u; -) ? k 0 . Let B u be the set of bad permutations
for the column u, i.e.,
A u (k):
The entire set of bad permutations for M is
all the p columns
of M . Theorem 3 implies that for every u,
jB
because It follows that jBj ! n!. Therefore, there is at least
one "good" permutation for the rows of M , i.e., a permutation providing at
most bk 0 c blocks of consecutive ones for each of the columns. We conclude by
remarking that bk 0 c ! k 0 , since ln (pn) cannot be an integer for integer pn ? 1. 2
Proof of Theorem 1: Let us consider any node labeling L of V , and any routing
G, e.g., a single shortest path routing function. Form
the n \Theta p boolean matrix M(R) as explained earlier. By Corollary 3.6 (which
is clearly applicable as there exists a row permutation - such that
2n ln (pn) for every column u of M . Permute the labeling
of the nodes of V according to -, to obtain a labeling L 0 such that the resulting
interval routing scheme, R is a q-IRS for
namely, R 0 has fewer than q intervals on each arc. Let us show that only p - 3n
arcs has to be considered.
In the case of single IRS, each destination is assigned to a unique set I(e)
in each node. For each node of degree three or less, we consider all its outgoing
edges. Consider a node x of degree greater than three, and let I; J; K be the
three largest cardinality sets assigned to outgoing edges of x. Assume that the
nodes are relabeled using the permutation - in such a way that all the sets I; J; K
are composed respectively of i, j, and k intervals. We remark that
3n=4+o(n) by Corollary 3.6. Hence all the other sets share at most n=4 intervals,
and do not need to be considered.
We complete the proof by plugging Inequality (8). 2
Remark. The parameter p of Inequality (8) represents the total number of arcs
we are required to consider. For graphs with fewer edges one can choose
which is better than 3n only for graphs of average degree at most 3. Note that
there exists some 3-regular graphs of compactness \Theta(n) [10].
Here we give another application of Theorem 3.
Corollary 3.7 Let M be an n \Theta p boolean
an arbitrary row permutation of M . With probability at least 1
column u of M .
Proof. Let M be an n \Theta p boolean matrix with . Build from M a
composed of all the p columns of M and completed by (n \Gamma 1)p other
columns, each filled up with 0's. M 0 has dimensions n \Theta pn. Clearly, the set of
"bad" permutations for M 0 and M is the same. The total set of bad permutations
for M 0 is
A
where the union is taken over all the pn columns u of M 0 , and k
Theorem 3 implies that jBj ! n!=n, noting that pn ! e n=2 =n.
We conclude that the number of "good" permutations for M 0 (hence for M ),
i.e., providing at most bk 0 c blocks of consecutive ones for all the columns, is at
least which is a fraction of 1 of all the row permutations of M .
The proof is completed by remarking that bk 0 c ! k 0 , for every integer pn 2 ? 1. 2
Therefore, to have a labeling with fewer than n=4
log n) intervals
on all the edges of G, it suffices to fix a node labeling, and a routing function
on G, then to randomly permute the n labels of nodes by choosing a random
permutation - of ng.
Note that the previous algorithm applies not only to single shortest path
routing schemes, but also to any routing scheme implementable by using interval
routing schemes. Thus for every IRS on every graph we can relabel the nodes in
order to have at most n=4
log n) intervals per arc. It is still unknown
whether there exists a polynomial time deterministic IRS construction algorithm
that guarantees at most n=4 + o(n) intervals per edges.
We do not know whether the upper bound is reached for certain graphs. How-
ever, it is well-known that some small graphs have compactness strictly greater
than n=4. In [9], it is shown that the example depicted on Figure 1 with 7 nodes
and 8 edges, has compactness 2, whereas all graphs of order at most 6 have compactness
1. Note also that the compactness of the Petersen graph is 3, whereas
its order is 10, and its size 15.
4 The Lower Bound
The lower bound idea is based on a representation similar to the one used in the
upper bound, namely, a boolean matrix M representation of the k-IRS on G.
However, this time we need to show that no row permutation of M yields fewer
than k blocks of consecutive ones on all the columns. Furthermore, this must be
shown for every choice of shortest routing paths. For instance, every
grid has compactness 1, using the standard node labeling and single-bend YX-
routing paths. Clearly, a different choice of shortest routing paths would increase
the number of intervals per edge. That is why we use smaller matrices, say of
dimensions jW j \Theta jAj, by considering only a subset of nodes, W , and a subset
of arcs, A, where the shortest paths between the tails of the arcs of A and the
nodes of W are all unique.
Our worst-case graph construction is a function of a boolean matrix M , denoted
GM . For every p \Theta q boolean matrix M , define the graph GM as follows.
For every associate with the ith row of M a vertex v i . For every
associate with the jth column of M a pair of vertices
connected by an edge. In addition, for every
we add to GM an edge connecting v i to a j , and otherwise we connect v i
to b j . Note that the graph obtained from GM by contracting the edges
is a complete bipartite graph K p;q . It is easy to see that the shortest
path from any a j to any v i is unique, and is determined by the entry m i;j of
M .
For integers p; q, let M be the collection of p \Theta q boolean matrices having
bp=2c 1-entries per column. Let M 1 be the subset of matrices of M such that all
the rows are pairwise non complementing, and let M 2 be the subset of matrices
of M such that for every pair of columns the 2 \Theta p matrix composed of the
pair of columns contains the sub-matrix 4 [
to column permutation. We
next use a direct consequence of a result proved recently in [8]. In the following,
means that
Lemma 4.1 (Gavoille, Gengler [8]) Let p; q be two sufficiently large integers.
Throughout the remainder of the paper, we set M . We will
see later that the graphs GM built from the matrices M 2 M 0 have diameter 2
exactly. Furthermore, almost all matrices are in M 0 .
We will see that the compactness of M is a lower bound of the compactness
of GM . Here we give a lower bound of the compactness of matrices of M 0 .
Lemma 4.2 For every sufficiently large integers p; q such that 3 log
there exists a p \Theta q boolean matrix M of M 0 of compactness
Proof. We use a counting argument which can be formalized using Kolmogorov
complexity (see [14] for an introduction). Basically, the Kolmogorov complexity
of an individual object X is the length (in bits) of the smallest program, written
in a fixed programming language, which prints X and halts. A simple counting
argument allows us to argue that no program of length less than K can print a
certain X 0 taken from a set of more than 2 K elements.
Let us begin by showing that the claim of the lemma holds for some matrices
of M. For every M 2 M, we define cl(M) to be the subset of the matrices
of M obtained by row permutation of M . We claim that there exists a matrix
such that all the matrices of cl(M 0 ) have Kolmogorov complexity at
least
there exists a matrix M 0
may be described by an ordered pair (i
is the index of the row
permutation of M 0
. Such an integer can be coded, in a self-delimiting
way, by log(p!) bits. (2dlog pe bits are sufficient to describe p,
thus the length of any i 0 - p!, in a self-delimiting way.) Hence the Kolmogorov
4 A is a sub-matrix of B if A can be obtained from B by removing some columns and rows
in B.
complexity of M 0 is at most C log jMj. By the
counting argument mentioned earlier, it is impossible for all matrices M
to have such low complexity.
The class M is of size
bp=2c
log log p), and log
All the matrices of M have q columns, each one of Kolmogorov complexity
bounded by p +O(1). Therefore there exists a matrix M 0 such that every matrix
in cl(M 0 ) has a column of Kolmogorov complexity at least
O
log p
The term 2 log p codes the length of the description of such a column in a self-delimiting
way. Define a deficiency function as a IN 7! IN function such that it
is possible to retrieve n and ffi(n) from n \Gamma ffi(n) by a self-delimiting program of
constant size. From [14, Theorem 2.15, page 131], every binary string of length
bits and of Kolmogorov complexity at least p \Gamma ffi(p) contains at least
s
occurrences of 01-sequences, for any deficiency function ffi, and some constant
c depending on the definition of the Kolmogorov complexity. Since each 01-
sequence in a binary string necessarily starts a new block of consecutive ones, we
get a lower bound on the number of blocks of consecutive ones for such strings.
By choosing for ffi the function log p), and by
Inequality (11), it follows that M 0 has compactness
Finally, let us show that the result of the lemma, shown for some matrices in
M, holds also for the compactness of some matrices of M 0 . From Lemma 4.1,
because Similarly,
implies that
log log jMj+ o(1), and thus Inequalities (9), (10), (11), and (12) hold for
as well, which completes the proof. 2
Remark. The proof of Lemma 4.2 is nonconstructive. As a result, it can prove
only the existence of such a worst-case graph GM .
We are now ready to prove Theorem 2.
Proof of Theorem 2: Let M 2 M 0 be a matrix satisfying Lemma 4.2, and
consider the graph GM , built from M . Let us show that the diameter of GM
is 2. For any two nodes x; y, denote by dist(x; y) the distance between x and y in
GM . The distance between any a j (or b j ) and any v i is at most 2 (since a j and b j
are adjacent). The fact that M 2 M 1 implies that rows of M are pairwise non
complementing. Thus for every
which implies dist(v 2.
has the following property: for any two columns
there exists some
. Therefore in GM ,
2. It follows that GM is of
diameter 2.
be any interval routing scheme on GM .
4.3 For every arc (a builds a path of length at
least 3.
Proof. Any "wrong" decision of R in routing from a j to v i (meaning, any decision
to start the route from a j to v i on any outgoing arc of a j other than the arc
results in a route that goes through some vertex v i 0
reaches
. The claim now follows from the fact that there is no path shorter than two
hops between any two vertices
. 2
comp(M) be the compactness of M .
Proof. The claim is proved by showing that if there is an IRS R that uses no
more than per arc, then R builds some path of length at least 3.
Since GM is of diameter 2,this implies that R is not a shortest paths scheme.
Given Claim 4.3, it suffices to prove that if there is an IRS R that uses no
more than per arc, then R must make the wrong decision for some
be a column of M composed of at least k blocks of consecutive ones.
Such a column exists because the compactness of M is k. Let us consider the
tuple defined by setting
otherwise, for every
is composed of at most k \Gamma 1
intervals, u is composed of at most k \Gamma 1 blocks of consecutive ones. Thus the
and the tuple u differ in at least one place. Let i 0 be an index such that
. If u
1. Claim 4.4 now follows by applying Claim 4.3.The order of GM is us choose
cn 2=3 ln 1=3 n
, where
1:14. The maximum degree of GM is maxfq; dp=2e
nodes a j are connected to b j and to the v i 's
corresponding to all the 0-entries of the jth column of M ). The total number of
edges in GM is
applying Lemma 4.2, the compactness of M , k, satisfies
Noting that O(n 2 =q
we get
s
Therefore, we have shown that if R uses at most k \Gamma 1 intervals per arc, R
builds a route of length at least 3. It remains to show that this result holds also
if R uses at most IRS(GM
4.5 For every 2-connected graph G of girth g, if k ! IRS(G) then the
longest path of every (non shortest paths) single k-IRS is at least bg=2c + 1.
Proof. Let G be a graph as in the claim, and let R be a single k-IRS for G.
must exist two nodes x; y at distance d such that the
routing specified by R from x to y is not along a shortest path. The routing path
uses an alternative on a cycle between x and y. The length of this alternative
path, l, satisfies l +d - g, which implies that l - g=2, because d - g=2. However
impossible, otherwise the message would use a shortest path, hence
l
Clearly, the graph GM is 2-connected and has no triangles, thus its girth is
at least 4, and therefore any single k-IRS of GM has a routing path of length at
least 3, completing the proof of Claim 4.5. 2
Remark. Theorem 2 is tight for the length of the longest path since it is proven
in [13] that
lp
per arc are sufficient to guarantee routes of
length at most d3D=2e, where D is the diameter of the graph. Hence for the
graphs considered here, which are of diameter 2, this yields paths of length at
most 3. Using this IRS, G cannot have a routing path of length 4.
To our best knowledge, the "best" worst-case construction which does not use
randomization remains that of [9], which yields graphs G with IRS(G) - n=8,
for every n power of 2.
Corollary 4.6 For every sufficiently large integer n, and for every integer D -
there exists an n-node graph G of diameter D such that
Proof. Take the worst-case n-node graph G of Theorem 2. G has diameter 2,
hence it has a node x of eccentricity 2. Construct a new graph G 0 obtained
from G by adding a path of length D \Gamma 2 to x. G 0 has diameter D exactly, and
nodes. The proof of Theorem 2 applies on G 0 as well. It turns
out that G 0 has compactness at least n=4 \Gamma O(n 2=3 log 1=3 n), that is n
replacing n by
We conclude this section by showing that the lower bound can be applied to
k-IRS that are not of shortest paths, and not single routing schemes.
A routing scheme R on G is of stretch factor s if for all nodes x; y, x 6= y,
the routing path length from x to y is at most s times longer than the distance
in G between x and y. In particular, a shortest path k-IRS is a routing scheme
of stretch factor 1.
For every integer ff - 1, a routing scheme R on G is ff-adaptive if for all nodes
y, x 6= y, there exist minfff; ffig edge-disjoint routing paths between x and y,
where ffi is the total number of "possible" edge-disjoint routing paths between
x and y in G having different first edges. A single shortest path k-IRS is a 1-
adaptive routing scheme of stretch factor 1. A full-adaptive k-IRS on G is a
\Delta-adaptive routing scheme on G, where \Delta is the maximum degree of G.
Since for GM the shortest paths between the nodes a j and v i are unique, and
since any wrong decision will route along paths of length at least 3/2 times the
distance, we have the following trivial lower bound.
Corollary 4.7 For every sufficiently large integer n, for every s, 1
and every integer ff - 1, there exists an n-node graph G such that no ff-adaptive
k-IRS of stretch factor s on G exists if
5 Conclusion
ffl Since the lower bound is based on Kolmogorov complexity of the labels of
the edges, the resulting bound can be applied to every kind of edge-labeling
based routing schemes. Moreover, the bounds can apply to adaptive (or
routing schemes.
ffl It would be interesting to find tighter upper bounds for small values of n,
and also to express these bounds as a function of other parameters and
properties of the graphs under study, such as their maximum degree, pla-
narity, genus, tree-width, and so on.

Acknowledgement

We would like to thank Alexander Kostochka.



--R

The complexity of the characterization of networks supporting shortest-path interval routing


in 7 th International Workshop on Distributed Algorithms (WDAG)
schemes, Research Report 94-04
Designing networks with compact routing tables
A survey on interval routing scheme

Worst case bounds for shortest path interval routing

Concrete Mathemat- ics
On multi-label linear interval routing schemes

Compact routing on chordal rings
Characterizations of networks supporting shortest-path interval labeling schemes
Labelling and implicit routing in networks
The Computer Journal
--TR

--CTR
Tamar Eilam , Cyril Gavoille , David Peleg, Compact routing schemes with low stretch factor, Journal of Algorithms, v.46 n.2, p.97-114, February
Cyril Gavoille , Martin Nehz, Interval routing in reliability networks, Theoretical Computer Science, v.333 n.3, p.415-432, 3 March 2005
Cyril Gavoille , Akka Zemmari, The compactness of adaptive routing tables, Journal of Discrete Algorithms, v.1 n.2, p.237-254, April
Pierre Fraigniaud , Cyril Gavoille , Bernard Mans, Interval routing schemes allow broadcasting with linear message-complexity (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.11-20, July 16-19, 2000, Portland, Oregon, United States
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
shortest path;random graphs;compact routing tables;interval routing