Interval routing schemes allow broadcasting with linear message-complexity (extended abstract).
The purpose of compact routing is to provide a labeling of the nodes of a network, and a way to encode the routing tables so that routing can be performed efficiently (e.g., on shortest paths) while keeping the memory-space required to store the routing tables as small as possible. In this paper, we answer a long-standing conjecture by showing that compact routing can also help to perform distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows to broadcast with an O(n) message-complexity, where n is the number of nodes of the network. As a consequence, we prove that O(n) messages suffice to solve leader-election for any graph labeled by a shortest path interval routing scheme, improving therefore the O(m previous known bound.
INTRODUCTION
This paper addresses a problem originally formulated by
D. Peleg, and that can be informally summarized as follows:
\Does networks supporting shortest path compact routing
schemes present specic ability in term of distributed com-
putation? E.g., broadcasting, leader-election, etc." This pa-
Part of this work has been done while the third author
was visiting the Computer Science Department of University
Paris-Sud at LRI, supported by the Australian-French
ARC/CNRS cooperation #99N92/0523
y Laboratoire de Recherche en Informatique, B^at. 490, Univ.
Paris-Sud, 91405 Orsay cedex, France. Additional support
by the CNRS. http://www.lri.fr/~pierre
z Laboratoire Bordelais de Recherche en Informatique, Univ.
Bordeaux I, 33405 Talence cedex, France. Additional
support by the Aquitaine Region project #98024002.
http://dept-info.labri.u-bordeaux.fr/~gavoille
x Department of Computing, Division of ICS,
Macquarie Univ., Sydney, NSW 2109, Australia.
http://www.comp.mq.edu.au/~bmans
per answers by the a-rmative, by showing that n-node networks
supporting interval routing schemes [26, 27] (IRS for
allow broadcasting with O(n) message-complexity.
More formally, a network E) (in this paper, by
network, we will always mean a connected undirected graph
without loop and multiple edge) supports an IRS if the nodes
of that network can be labeled from 1 to in such a
way that the following is satised: given any node x 2 V of
degree d, there is a set of d intervals
one for each edge ed incident to x, such that (1) V n
implies that there is a shortest path from x to y passing
through the edge e i . So, IRS is a shortest path routing table
having the property that the set of destination-addresses
using a given link is a consecutive set of integers. IRS is a
famous technique for the purpose of compact routing since
a network of maximum degree  and supporting an IRS
has its routing table of size O( log n) bits, to be compared
with the (n log ) bits of a routing table returning, for
every destination, the output port corresponding to that
destination. For more about IRS, we refer to [6, 10, 17, 19,
21, 22], and to [16] for a recent survey. For more about
compact routing in general, we refer to [12, 13, 14, 18, 20,
On the other hand, broadcasting is the information dissemination
problem which consists, for an arbitrary node of a
network, to send a same message to all the other nodes.
The message-complexity of broadcasting lies
between
n)
since, on one hand, the reception of
the message by every node but the source requires at least
messages, and, on the other hand, broadcasting can
always be performed by
ooding the network, that is, upon
reception of the message, every node forwards that message
through all its incident edges (apart the one on which it has
received the message). Better upper and lower bounds can
be derived as a function of the knowledge of the nodes of the
network (e.g., see [1, 2, 4]), and of the maximal size of the
message-headers (e.g., see [24]). In the following, the only
knowledge of every node is its label in some IRS, and the
intervals attached to its incident edges in the same IRS. The
size of each message-header transmitted by our broadcasting
protocol is dlog 2 ne bits.
The relationship between IRS and broadcasting was previously
investigated. For instances, van Leeuwen and Tan [27]
proved that minimum spanning tree construction, and therefore
broadcasting, and other related distributed problems
such as leader-election can be solved by exchanging O(n)
messages in a ring labeled by an IRS, and O(m+n) messages
for arbitrary graphs labeled by an IRS. Recall that leader-
election without any network knowledge requires (n log n)
messages for a ring, and (m+n log n) messages for an arbitrary
graph [15]. More generally, the question of how much
a labeling can help in the solution of distributed problems
was studied in [8, 9] in the framework of Sense of Direction
It was shown in [5] that the message-complexity
of the broadcast problem is n 1 in the restricted class of
networks supporting all-shortest-path IRS (an IRS where all
the shortest paths are represented) with additional restrictions
on the intervals (strictness and linearity). Finally, de la
Torre, Narayanan and Peleg [3] showed that the same result
holds in IRS networks satisfying the so-called ssr-tree prop-
erty. (Informally, this property states that, for any node x,
the set of paths induced by the IRS originated at x, and
ending at all the other nodes, is a tree.) In this paper, we
improve these results by showing that a network supporting
standard shortest path IRS supports a broadcast protocol
of message-complexity (n).
Our result has many consequences on other problems, such
as leader-election or distributed spanning tree. For instance
Korach et al. [23] have shown that the leader-election problem
can be solved using (b(n)+n)(log
b(n) is the message-complexity of broadcasting in an n-node
networks. Therefore, n-node networks supporting shortest
path IRS allow the leader-election problem to be solved with
O(n log n) message-complexity (instead of O(m+n log n) for
arbitrary networks). In fact, we prove that O(n) messages
su-ce to solve leader-election for any graphs labeled by a
shortest path IRS (see [11] for a proof), improving therefore
the O(m+n) previous bound of van Leeuwen and Tan [27].
The paper is organized according to several hypotheses on
the IRS. These hypotheses will be relaxed while going further
and further in the paper. We can indeed distinguish
two types of intervals: an interval [a;
b  a is said to be linear, whereas an interval [a; b] with
b < a refers to the set bg, and is said to be
cyclic. The class of networks supporting linear IRS (LIRS
for short), that is such that all intervals of the IRS are lin-
ear, is strictly included in the class of networks supporting
an IRS which possibly includes cyclic intervals. We can also
distinguish the case V
I i for every node x, from
the case in which x appears in the interval of one of its incident
edges, for at least one node x. In the former case,
the IRS is said to be strict. Hence we get four types of
interval routing schemes: IRS, LIRS, strict IRS, and strict
LIRS. The following section presents some preliminary re-
sults. Section 3 is dedicated to networks supporting strict
LIRS. Sections 4 and 5 then successively relax the strictness
requirement and the linearity requirement, in order to
present our main result given in Theorem 1.
2. PRELIMINARY RESULTS
In this section, we will present a distributed broadcast protocol
for a network supporting an IRS. This protocol is very
simple though very e-cient since its message-complexity
will be shown to be at most O(n). It is called the up/down
protocol. The second part of the section presents tools for
the analysis of this protocol.
2.1 The up/down broadcast protocol
Let  be the source of the broadcast, identied by its label
in the IRS. The source initiates the broadcast by sending
two copies of the message, one destinated to node  1,
and the other destinated to node  + 1. The latter copy is
called the \up" copy whereas the former is called the \down"
copy. (Obviously, if source sends
only one copy.) There will be at most two copies of the
message circulating in the network. Let us concentrate on
the up copy destinated to +1. The message will eventually
reach by the shortest path set by the IRS. It may
possibly cross intermediate nodes, but these nodes will just
forward the message to its destination stored in the message-
header, without taking care of its content. Once the node
receives the message, it reads its content, modies the
header by replacing
the node labeled  2. More generally, once a node labeled
receives the message destinated to x, it reads
its content, modies the header by replacing x by x
and forwards it toward the node labeled x + 1. When the
node labeled n receives the message, it reads its content, and
removes it from the network. The same strategy is applied
for the down copy, by replacing x
until it reaches node labeled 1 which reads its content and
removes it from the network. Again, at every given time, a
copy of the message is destinated to only one specic node,
called the target, and when a node dierent from that target
receives the message, it does not take the opportunity to
read its content, but just forwards the message to the target
along the shortest path set by the IRS that leads to that
target.
Clearly, the message-complexity of the up/down protocol is
equal to
denotes the distance
between the node labeled x and the node labeled y in G.
Unfortunately, up to the knowledge of the authors, there is
no good bounds on networks supporting IRS.
Let us just point out that it is known [5] that
for networks supporting all-shortest-path strict LIRS that is
for networks such that the strict LIRS encodes all shortest
paths. The class of networks supporting all-shortest-path
strict LIRS is very restricted (see [16]), and, as we will see,
only weaker results can be proved for (single shortest path)
LIRS or IRS.
Assume that the source is labeled 1, and let
be the sequence of nodes visited by the message from its
source w1 (labeled 1) to its nal destination w (labeled n).
The same node may appear several times in W . However, a
node x can only appear once as a target node, and thus the
possible other occurrences of node x correspond to steps of
the protocol in which x is traversed by a message destinated
to a target node y 6= x. Let us complement the sequence
W by two virtual nodes, These
two nodes are not target nodes. More precisely, W can be
as:
is a maximal sequence of consecutive
target nodes, and Y i , is the sequence of non
target nodes between the last node of X i and the rst node
of X i+1 . In particular, . The nodes
of the Y i 's are called intermediate nodes.
Notation. For every i, throughout the paper, we will always
make use of the following
the last node of X i , y the last node of Y i , and z
the rst node of Y i .
2.2 Intermediate nodes sequences
The next lemmas give some properties satised by the intermediate
nodes in the Y i 's. These properties will be shown
to be helpful to compute the message-complexity of the
up/down protocol.
Lemma 1. Let G be a network supporting a strict LIRS.
x 1) be the shortest path from the node labeled x to the
node labeled x to node labeled x 1) in a strict
LIRS. Then u1 > u2 >    >
< vk 1 < x 1).
Proof. Let I i be the interval of edge at
We have x by denition of the
path
is the unique shortest from u i to u i+1 . On the
other hand,
by denition of the path
because the
LIRS is strict. Therefore, since the intervals are all linear,
Similarly, one can show
that
Lemma 1 states that, in strict LIRS networks, once a target
node x has received the message in the up (resp. down)
protocol, no node of label smaller (resp. greater) or equal
to x will be visited anymore.
Corollary 1. In a network supporting a strict LIRS,
ig.
The next lemma analyzes the relationship between consecutive
sequences of intermediate nodes. Its aim is to answer
the following: given an intermediate node w i 2 W , where
can we nd another intermediate node w j 2 W , j > i, whose
label is smaller than the label of w i ? (Lemma 1 answers
this question if w i is not the last node of an intermediate
sequence Yr .)
For any set of nodes S  V , and any node u 2 V , we
denote by d(u; S) the distance between u and S, that is
below says that if w i
is the last node of the sequence Yr 1 (i.e., d(w
and if 'r > kr (i.e., jYr j > jXr j), then the (kr + 1)-th node
of Yr is smaller than w i . In other words w
1). The look for such a w j when 'r  kr is
more complex. It depends mainly on the relative lengths of
the Ys 's and Xs 's for s  r.
Lemma 2. Let G be a network supporting a strict LIRS,
and let u be a node of G. Let r
Assume that there exists s  r such that
ks
every intermediate node w
Proof. First note that
implies that
's . Note also that
implies that
ks 2. Let us show by induction on i, that
for every
Note that Let I1 be the interval on the edge
at xr , and, for i > 1, let I i be the interval on the
edge . For every i  1, we have xr +1 2 I i ,
and
I i . From Lemma 1, we also have u1 >    >
and u  u ' r . Thus, since u i 2 I i , we get that u 2 I i for
every Therefore, a shortest path from xr to u
goes through . As a consequence 'r
Assume now that d(u; y
some i, r  i < s 1, and let us show that d(u; y i+1)
(- 1)+
For the same reasons as for the case
we get that a shortest path from the last node x i+1
of X i+1 to u goes through all nodes of Y i+1 . We get that
and thus d(u; y i+1)  (- 1)+
the proof of Equation 2.
A consequence of Equation 2 is that
ks
So now, let I1 be the interval on edge (xs ; v1 ) at xs , and,
be the interval on edge (v
and thus, d(u; xs) >  1, a contradiction. Thus u  v i for
some i   1, and therefore u > v by Lemma 1. This
completes the proof of Lemma 2.
Now, we know enough to start the analysis of the up/down
protocol.
3. STRICT LINEAR INTERVAL ROUTING
SCHEMES
In this section, we show that the message-complexity of the
up/down protocol is at most 3n on a network of order n
supporting a strict LIRS.
3.1 Partition: a sequence-decomposition algorith

Assume rst that the source is the node 1. We make use
of the sequence W as displayed in Equation 1. Since the
total number of target nodes is n, we have
n. Therefore, the aim of the rest of the proof is to bound
the total number
of intermediate nodes. For that
purpose, we will partition the intermediate nodes of W in
three types of (pairwise disjoint) subsequences. The result
of this partition is called the sequence-decomposition. More
precisely, the sequence-decomposition will be composed of
an active path, of dead-end paths, and of jumped paths. The
active path is built starting a walk from w0 up to w+1 .
Along the construction of the sequence-decomposition, some
parts of the active path become dead-end paths. At the end
of the decomposition, the two extremities of the active path
are w0 and w+1 , and the total number of nodes kept in
the active path will be at most O(n). Also, at the end of
the construction, the sum of the lengths of the dead-end
paths, and the sum of the lengths of the jumped paths will
be both bounded by O(n). Therefore, the total number of
intermediate nodes will be O(n), and jW O(n). A careful
analysis of the constants will actually show that jW j  3n.
The sequence-decomposition is performed by visiting all intermediate
nodes of the sequence W from w0 to w+1 , constructing
in this way the active path. One may \jump" over
some intermediate nodes if the length of the jump can be
bounded by the number of jumped targets. The result of
a jump is a jumped path. One may also backtrack along
the active path for a bounded number of nodes. The result
of a backtrack is a dead-end path. The decomposition
requires two parameters: the mark m, and the direction d.
The role of the mark is to keep in mind the progression along
the sequence W . In general, the mark indicates the current
position, or, more precisely, the index i of the current set
Y i . The mark is an important parameter because of the
backtracks. When a backtrack occurs, the mark is set to
remember the current maximum position ever reached. The
direction indicates whether a backtrack recently occurred.
In that case
Initially, the active path is reduced to w0 , and there is neither
a dead-end path nor a jumped path. The mark m
is set to 0, and the direction is set to +1. The construction
of the sequence-decomposition is precisely described in
Algorithm 1. The explanations of the several steps of the
construction are given below.
In Case 1, the construction is currently visiting some Yr .
While the last node of this sequence of intermediate nodes
is not reached, the active path is updated by adding all the
forthcoming nodes of the current sequence. Informally, from
Lemma 1, the size of the active path will not increase too
much since the labels of the nodes are in a strictly decreasing
order. Case 2 happens in particular when the last node of
the current sequence Yr is reached. The denition of s is
motivated by Lemma 2. If s does not exist, the construction
stops. If s does exist, then we make a jump in the sequence
W as explained thereafter. (Note that, like in Lemma 2,
In Case 2.1.1, we simply jump at the next
intermediate node w whose label is smaller than the label of
the current node. Case 2.1.2 can be seen as an extremal case
Algorithm 1 One step of the construction of the sequence-
decomposition for a strict LIRS
The current active path is
r be such that p t 2 Yr , and let
Case 1: +1. Then the active path is
updated to There is neither a new
dead-end path nor a jumped path. The mark and the direction
are not modied.
Case 2:
be the smallest index such that
does not exist, then the active path is
updated to there is no new dead-end
path, all intermediate nodes between the last node of Ym
and w +1 form a new jumped path, and the construction
stops. If s exists, then let ks
Assume that two cases are considered:
Case 2.1:
again two cases may
occur.
Case 2.1.1: There is an intermediate node w in
Then pick the rst node w of that type. The active
path is updated to
intermediate nodes between the last node of Ym
and w form a jumped path. Assume w 2 Y ,
then the mark m is set to .
Case 2.1.2: For every intermediate node w in
. Then the
active path is updated to p0 ;
all intermediate nodes between the last node of
Ym and v forms a jumped path. The mark m is
set to s.
In both cases, there is no new dead-end path, and the
direction d is set to +1.
Case 2.2:
. Then the direction d is set
to 1. Let t 0 1g be the largest index
such that p t
forms a dead-end path. Assume
> m+ 1, all intermediate nodes of [  1
a jumped path. The mark m is updated to  1.
of Case 2.1.1. We know from Lemma 2 that jumping at v
is ne since the label of that node is smaller than the label
of the current node p t . The mark is updated to contain the
index of the sequence Y of intermediate nodes reached after
the jump. Case 2.2 is a particular case because a backtrack
occurs. This backtrack is motivated by the fact that one
cannot nd an intermediate node with a label smaller that
the label of p t . Informally, we backtrack along the active
path reach a node p t 0 , t 0 < t, for which
Lemma 2 can be applied. Note that t 0 is well dened since
ng.
Lemma 3. The construction of the sequence-decomposition
given in Algorithm 1 produces a set of paths in which every
intermediate node appears exactly once.
The proof is based on the following claim.
Claim 1. If
Proof. This claim initially holds. Assume the claim
holds before some step i, and consider the several cases of
Algorithm 1. In Case 1, p t+1 will still be in Ym , and d
will still be +1. In Case 2.1, the direction is set to +1 and
by denition of the setting of the mark m in both
Cases 2.1.1, and 2.1.2. Case 2.2 sets d to 1. So the claim
holds after step i too.
The proof of the lemma is then as follows:
Proof. After every step i, let us dene m i as the resulting
mark, and
last node of Ym i otherwise.
We claim that, at every step i, all intermediate nodes before
appears exactly once in the sequence-decomposition.
This claim initially holds. Assume it holds before step i.
In Case 1, from Claim 1, q . The active
path is upgraded by adding the next node of the sequence,
thus the claim holds after step i. In
Case 2.1, m i is set such that p t+1 2 Ym i , and thus q
Every intermediate node between the last node of Ym
that is q are put in a jumped path, so the
claim holds after step i. In Case 2.2, some part of the active
path becomes a dead-end path. By the setting of m i , all the
intermediate nodes not yet assigned to any type of paths,
that is all intermediate nodes in [ m i
are put in a
jumped path. Thus every intermediate node between q
and q i are put in a jumped path. Therefore, after step i,
all intermediate nodes before q i appears exactly once in the
sequence-decomposition.
We complete the proof of the lemma by noticing that, after
every step, either the active path is increased, or a part of
the active path is put in a dead-end path. By the setting
of the mark, an intermediate-node put in a dead-end path
or in a jumped path will not be considered anymore in the
further steps. Therefore the construction of the sequence-
decomposition of Algorithm 1 ends after a nite number of
steps.
3.2 Message-complexity of the up/down pro-
tocol
From the sequence-decomposition algorithm, let us compute
the message-complexity of the up/down protocol.
Lemma 4. The number of intermediate nodes in the active
path is at most n, excluding w0 and w+1 . More pre-
cisely, the labels of the nodes of the active path, including
w0 and w+1 , form a decreasing sequence in n
Proof. To prove that lemma, let us go again through the
several cases of a step of the decomposition. Let p t be the
last node of the current active path. In Case 1, Lemma 1
insures that p t+1 < p t . In Case 2, if s does not exist, then
the next node of the active path is which is smaller
than every other nodes of the current active path. So, in the
remaining of this proof, we assume that s does exist. Since
Case 2.2 does not add new node to the active path, we focus
on case 2.1. In Case 2.1.1, the new node added to the active
path is, by denition, smaller than p t . In Case 2.1.2, v < p t
by application of Lemma 2, which completes the proof of
that lemma.
Lemma 5. The number of nodes in the dead-end paths is
at most n.
Proof. A dead-end path is composed of a sequence of
nodes that were formerly in the active path, and through
which a backtrack occurred. Every backtrack is driven by
a set of target nodes [
Similarly, let
From Lemma 4, the number of nodes of the dead-end path
corresponding to
because the active path, traversed in the
reverse direction, produced a sequence of nodes of increasing
labels. Now, m is updated to  1 after the backtrack, and
thus not be considered anymore for the
counting of the number of nodes in the dead-end paths. X
may be considered again in another dead-end path since m 0
can be equal to m. However, only the k i last nodes of
X will be involved. As a consequence, the total number of
nodes in dead-end paths is bounded by
2. Assume that two jumps J 0 and J successively
occurred at x (that is J 0 occurred, and then later a backtrack
led back to x, and J occurred). Let y
and y 2 Y be the respective extremities of J 0 and J, and
assume y be the setting
of the mark and the distance when J
Proof. By denition
by the setting of m when backtracking through J 0 as
On the other hand, by the same
arguments as for Equation 2, d(y m 0
More generally, d(y
which completes the proof of the claim.
Lemma 6. The number of nodes in the jumped paths is at
most n.
Proof. As dead-end paths, the jumped paths are characterized
by disjoint sets of target nodes of the form [ s
Let us rst consider the jumped paths created by application
of Case 2.1 of Algorithm 1. Assume that a jump J
occurred between x 2 Yr , and y 2 Y , r <   s. If
< s, then the number of nodes of the jumped path is at
most
then assume that
Thus, the number of nodes of the
corresponding jumped path is at most
(- 1)+
j. So, in any case, the number of nodes
of the jumped path is at most (-
setting corresponds to another jump J 0
occurred at x, say between x and y
be respectively the value of the mark
and of the distance when J 0 occurred. From Claim 2, we
have
On the other hand, the size of the jump at y 0 is
It yields that the number of node for the two
jumps is at most (- 0 1)+
can repeat for - 0 what we did for -, until we have considered
all jumps that successively occurred at x. It yields that the
total number of nodes of the set of jumped paths occurring
at the same node x is at most
contains
the other extremity of the last jump occurred at x.
The analysis is the same for the jumped paths created in
Case 2.2 by proceeding as if the jump occurred between p t 0
and the last node of Y 1 (recall that p t 0
We conclude the proof by noticing that due to the setting
of the mark m, no two jumps occur above the same set of
target nodes, and therefore the total number of nodes is at
most
Combining Lemmas 4, 5, and 6 with Lemma 3 allows to
conclude that the total number of intermediate nodes is at
most 3n. We can actually improve this upper bound to 2n.
Let x be the extremity of the active path when s cannot be
dened, that is when
nodes of the active
path belong to [ %
by application of Lemma 4. By
application of the same lemma, the total number of nodes
in the active path is at most
j. Since the sets
were not used to bound the total number of
dead-end paths, we can conclude that the sum of the number
of nodes in the active path plus the number of nodes in the
dead-end paths is at most n. From all what precede, the
total number of nodes in the sequence-decomposition, and
therefore the total number of intermediate nodes, is at most
2n. Therefore, the total number of nodes in the sequence
W is at most 3n, and hence the message-complexity of the
up/down protocol is at most 3n.
If the source node is not the node labeled 1, then let  > 1
be the label of the source. From Lemma 1, the message
complexity of the copy going upward is at most 3(n )
whereas the message-complexity of the copy going downward
is at most 3.
To summarize, we get:
Property 1. The message-complexity of the up/down
broadcast protocol is at most 3n in a network of order n
supporting any strict LIRS.
Note that K2;n 2 , the complete bipartite graph with one
partition of size 2, and another partition of size n 2, supports
a strict LIRS for which the up/down protocol uses
messages.
4. LINEARINTERVALROUTINGSCHEMES
The next lemma is a variant of Lemma 1 adapted to (non
strict) LIRS networks.
Lemma 7. Let G be a network supporting an LIRS. Let
1) be the shortest path from the node labeled x to the node
labeled x+1 (resp. to node labeled x 1) in an LIRS. Then,
for every i, k > i > 1, we have
for every
Proof. Let I i be the interval of edge at
1. By denition, we have x+1 2 I i , and u
For
I i (otherwise there would exist
a shorter path from x to x
More generally, if i  1, then
I i for every j  i 1.
Therefore, since all the intervals are linear, u
every 1. The result for the v i 's is obtained in
a similar way.
Corollary 2. In a network supporting an LIRS,
ig.
The dierence between Lemma 1 and Lemma 7 motivates
the following adaptation of Lemma 2 for LIRS networks that
are non necessarily strict.
Lemma 8. Let G be a network supporting an LIRS, and
let u be a node of G. Let r and assume that
Assume that there exists s  r such that
r+1)+- for every s 0 , r  s 0 < s. Let
2(s r)+-, and let . Assume that u > x for
every
for every intermediate node
Proof. Note rst that,
implies  > ks  1, and
implies   's 2. We proceed is a way similar to the proof
of Lemma 2. We show that, for every
r. The shortest path from zr to u set by the IRS
goes through all nodes of Yr . Thus 'r 1
Therefore,
Equation 3 holds for Assume Equation 3 holds for i,
and let us show that it holds for 1. Again, the shortest
path from z i+1 to u set by the IRS goes through all nodes
of Y i+1 , and thus '
and hence d(y
and Equation 3 holds for
A consequence of Equation 3 is that
ks
Thus there is a node in v+1g such that v i  u.
Indeed, otherwise, the path set by the IRS from zs to u
would go through thus would not be a
shortest path. Let i be the smallest index in
such that v i  u. If i < +1, then v+2 < u from Lemma 7.
and the
result holds.
In order to analyze the up/down protocol in networks supporting
LIRS, we partition the sequence W in slightly different
manner than in the previous section. The formal
decomposition is given in Algorithm 2. The decomposition
for LIRS actually looks very similar to the decomposition
for strict LIRS. A fourth type of path is introduced:
the auxiliary path. This path is motivated by the fact the
active path will include one node every two, according to
Lemma 7. Every node in between two nodes of the active
path is dropped in the auxiliary path. Let us just mention
some dierences appearing at every step of the sequence-
decomposition. Case 1 is roughly the same as Case 1 in
Algorithm 1, that is the decomposition uses the current
intermediate sequence to construct the active path. The
only modication is that one node every two is dropped in
the auxiliary path, and that one may stop at u ' r 1 or u ' r .
Therefore, Case 2 considers also the case
if true, implies that u ' r is put in the auxiliary path. Case 2
also diers from Case 2 in Algorithm 1 by the denition of
both s and . The new settings are adapted from the statement
of Lemma 8. Otherwise, the general structure of the
decomposition for LIRS is the same as Algorithm 1.
We will show the following results. Firstly, the labels of
the nodes of the active path form a non increasing sequence
such that the number
of times that p is at most %. Thus the number
of intermediate nodes in the active path is at most n
This result can be rened by showing that the number of
nodes in dead-end paths or in the active path is at most
direct consequence is that the number of nodes
in the auxiliary path is at most n + % since the number
of nodes in the auxiliary path does not exceed the number
of nodes in the active path or in the dead-end path. The
contribution of the jumped paths is a bit larger since the
number of nodes in the jumped paths is at most n
Therefore,
Lemma 9. The number of intermediate nodes in the active
path is at most n excluding w0 and w+1 . More
precisely, the labels of the nodes of the active path form a
non increasing sequence
such that the number of times that p is at most %.
Proof. From lemma 7, Case 1 insures that p
In Case 2, if s does not exist, then p
assume that s exists. There is no setting of the
active path in Case 2.2. In case 2.1.1, a jump occurs and
by denition. In case 2.1.2, a jump occurs too
and p t+1  p t from Lemma 8. The number of jumps is at
most %.
Lemma 10. The number of nodes in dead-end paths or in
the active path is at most n
Proof. By similar arguments as in the proof of Lemma 5,
and using the same notation, the number of nodes of a dead-end
path corresponding to the sets is at most
plus the number of jumps occurring
in the portion p t 0 of W . It yields a total number
of nodes in dead-end paths of at most
Now, as we observed in the strict LIRS case, if x 2 [ %
is the last node of the active path dierent from w+1 , then
the total number of nodes in the active path is at most
is the number of jumps
of the nal active path. The sets were not
used to enumerate the nodes in the dead-end paths, and the
total number of jumps cannot exceed %. Therefore, the total
number of nodes in the active path or in dead-end paths is
at most n
Lemma 11. The number of nodes in the auxiliary path is
at most n
Proof. This is a direct consequence of Lemma 10 since
the number of nodes in the auxiliary path does not exceed
the number of nodes in the active path or in the dead-end
path. Indeed, at most one node is dropped in the auxiliary
path for every node entering the active path. Some nodes
formerly in the active path become member of a dead-end
path.
Lemma 12. The number of nodes in the jumped paths is
at most n
Proof. Let us rst consider a jump created by application
of Case 2.1. Let J be a jump corresponding to the sets
. Assume that J occurred between x 2 Yr and
then the jump was over at
most
nodes, with
Therefore, in any case, the number of jumped intermediate
nodes is at most (-
then this setting corresponds to another jump J 0 occurred
at x, say between x and y
be the value of the mark, and the value of the
distance, respectively, when this jump occurred. We have
by the
setting of m when backtracking through J 0 as y
Therefore, -  d(x; y 0 ), and, by the same arguments as in
the proof of Claim 2,
The size of the jump J 0 is
thus the size of the two jumps is at most
then one can apply on - 0 the same arguments. We
get that the number of nodes of the set of jumped paths occurring
at the same node x 2 Yr is at most 1+
contains the extremity of the last jump
occurred at x.
The analysis is the same for the jumped paths created in
Case 2.2 by proceeding as if the jump occurred between p t 0
and the last node of Y 1 (recall that p t 0
The worst case is reached when every jump is over a single
whose cost in term of nodes is 1
for a total number of nodes at most
Therefore, we get:
Property 2. The message-complexity of the up/down
broadcast protocol is at most 9n in a network of order n
supporting any LIRS.
5. INTERVAL ROUTING SCHEMES
As opposed to linear IRS, the labels of the nodes of an IRS
play all the same role. Therefore, we slightly modify the
up/down protocol to adapt it to IRS networks. If the source
is labeled , 1 <  < n, then there is only one copy of the
message, going upward from  to n, then from n to 1, and
nally from 1 to  1, rather than two copies, one going
downward from  to 1, and the other going upward from
to n. This protocol is denoted by up/1/up. So, as far as the
up/1/up protocol is concerned, one can assume, w.l.g., that
the source is labeled 1.
Again, in order to analyze the up/1/up protocol, we make
use of the sequence W dened in Equation 1. For every
ng 7! ng
by
We have 1. By using the same
techniques as Lemmas 1 and 7, the reader can check that:
Lemma 13. Let G be a network supporting an IRS. Let
1) be the shortest path from the node labeled x to the node
labeled to node labeled x 1) in this IRS.
If the IRS is strict, then
n).
Otherwise, for every i, k > i > 1, we have
and
for every
By using the same techniques as Lemmas 2 and 8, the reader
can also check that:
Lemma 14. Let G be a network supporting an IRS, and
let u be any node of G. Let r and assume that
If the IRS is strict, then assume that there exists s  r
such that
1 for every s 0 , r  s 0 < s. Let ks
-, and let
and every x 2 X i , Lx i (u) > Lx i (x), and if, for every
every intermediate node w
Otherwise, assume that there exists s  r such that
If, for every
every
intermediate node w
then minfLxs (v+1); Lxs (v+2)g  Lxs (u).
Therefore, the sequence-decomposition of Algorithm 1, and
its adaptation to LIRS networks described in Section 4 can
be applied by introducing the relabeling Lx 's every time
that a comparison is performed between two labels. The
resulting algorithms are given in Algorithms 3 and 4.
The previous lemmas of this section show that there is no
major dierence between the sequence-decomposition for
LIRS networks and the sequence-decomposition for IRS net-
works. In fact, the up/1/up protocol for IRS and strict IRS
networks satisfy the same properties as the up/down protocol
for LIRS and strict LIRS networks, respectively. The
key of the proof is the following result:
Lemma 15. Assume
Then Lx (p i+1) < Lxr (p i ) in the sequence-decomposition
for strict IRS networks, and Lx (p i+1)  Lxr (p i ), where the
maximum number of equality is at most %, in the sequence-
decomposition for IRS networks.
Proof. According to the statement of the lemma, we are
considering Case 2.1 of the sequence decomposition. Hence
precisely
from the
possible setting of the mark after several backtracks ending
at us rst consider the strict IRS decomposition.
We have us assume
that Lxr Then, since from Lemma 13,
1), we get that p i is equal to a target
node in [
contradiction with the hypothesis
of Case 2.1. Therefore Lxr
arguments allow to show that Lx (p i+1)  Lxr (p i ) in
the sequence-decomposition for IRS networks.
Therefore, if f(i) denotes the index such that
then the active path p0 ; resulting from the
sequence-decomposition for strict IRS networks satises
any pair (i; j), 1  i < j  t. In IRS networks, there might
be up to % equalities in the sequence. As a consequence:
Theorem 1. The message-complexity of the up/1/up
broadcast protocol is respectively at most 3n in a network
of order n supporting any strict IRS, and at most 9n in a
network of order n supporting any IRS. As a consequence,
networks supporting a shortest path Interval Routing Scheme
allows broadcasting with O(n) message-complexity.
Corollary 3. In a network supporting any strict IRS,
the average distance between two nodes labeled by two consecutive
integers is at most 3+O(1=n). In a network supporting
any IRS, the average distance between two nodes labeled by
two consecutive integers is at most 9 +O(1=n).
6.



--R

Optimal broadcast with partial knowledge.
A tradeo

The impact of knowledge on broadcasting time in radio networks.
Broadcast in linear messages in IRS representing all shortest paths.
The complexity of interval routing on random graphs.
Sense of direction: De
On the impact of Sense of Direction on Message Complexity.
Sense of direction in distributed computing.
Interval routing schemes.
Interval Routing Schemes allow Broadcasting with Linear Message-Complexity
Searching among intervals and compact routing tables.

Designing networks with compact routing tables.
A distributed algorithm for minimal spanning tree.
A survey on interval routing.

Compact routing tables for graphs of bounded genus.
The compactness of interval routing.

Lower bounds for compact routing.
On multi-label linear interval routing schemes
A modular technique for the design of e-cient distributed leader nding algorithms

A trade-o between space and e-ciency for routing tables
Labelling and implicit routing in networks.
Interval routing.
--TR
Interval routing
A tradeoff between space and efficiency for routing tables
A trade-off between space and efficiency for routing tables
A modular technique for the design of efficient distributed leader finding algorithms
A trade-off between information and communication in broadcast protocols
Memory requirement for routing in distributed networks
On the impact of sense of direction on message complexity
Worst case bounds for shortest path interval routing
Optimal Broadcast with Partial Knowledge
The Compactness of Interval Routing
A survey on interval routing
A Distributed Algorithm for Minimum-Weight Spanning Trees
The Complexity of Interval Routing on Random Graphs
Sense of Direction in Distributed Computing
Compact Routing Tables for Graphs of Bounded Genus
Lower Bounds for Compact Routing (Extended Abstract)
On Multi-Label Linear Interval Routing Schemes (Extended Abstract)
The Impact of Knowledge on Broadcasting Time in Radio Networks
Searching among Intervals and Compact Routing Tables

--CTR
Cyril Gavoille, Routing in distributed networks: overview and open problems, ACM SIGACT News, v.32 n.1, March 2001
broadcasting;distributed computing;compact routing;interval routing