Interval Routing for Distributed Problems

The general question ``how much a labeling can help in the solution of
some distributed problems'' was posed by [FMS98a], and then
further studied by [FMS97,FMS98b] in the framework of *Sense
of Direction*.

Recently, David Peleg asked the question in [SRS97]: *``In
many contexts and many areas, once a good representation is
constructed, it is often useful for more than one application. Yet
in the particular case of Interval Routing, IRS representations seem
to be used only for routing. Given that we have invested all
this time and efforts in constructing them, it should be nice if we
could use them (once constructed) to solve other problems more
efficiently, in addition to routing.''*

Originally the investigation of Interval Routing came from distributed
computing in asynchronous networks. [vLT87] proved that minimum
spanning tree, leader-election (when the node-labeling is not
restricted to
), and other related distributed
problems can be solved in a ring labeled with a 1-IRS by exchanging
*O*(*n*) messages only, and *O*(|E| + *n*) messages for arbitrary graphs,
whereas in the general case
messages for the ring, and
messages for arbitrary graph are
required [GHS83].

More precisely, David Peleg posed in [SRS97] the question:
*``is it possible to broadcast by exchanging a total of O(n)
messages for any graph supporting a shortest path 1-IRS?
(adding
extra bits to the message)''*

The general problem is still open but there are some partial results
in the case of all-shortest paths *k*-IRS (recall that an all-shortest
path IRS is a multipath IRS that encodes all the shortest paths from
every source node cf. Paragraph 4.3). In
particular [EPTZ97] shows that:

It implies that the algorithm which consists in sending first the
message to destination 1, then, after reception, to destination 2,
and so on until the node labeled *n*, turns out a total of at
most 3*n* messages. It is interesting to remark that if *G* has a
full-adaptive 1-IRS of stretch factor *s*, then by a simulation of the
previous algorithm, *G* has a *O*(*sn*) messages broadcast algorithm.

Only partial results are known for (single) shortest path 1-IRS. In particular we have the property:

It follows that nodes 1 and 2, and by symmetry the nodes *n*-1 and
*n*, are neighbors. Because the grid with its usual shortest path
1-SLIRS labeling, the bound of Theorem 65 is tight.

Other broadcast algorithms have been proposed in [dlTNP98]
leading also to a linear time solution: The SSR-CAST algorithm.
In the following, *R* is an IRS, *s* the source node, and *M* is the
message to broadcast.

**Algorithm [dlTNP98]:**
itemize

Initialization: *s* sends the message *M* and the set *I*(*s*,*u*)
to each of its neighbors *u*.
Forwarding step for :
Upon receipt of the message *M*
and a set *I* from some neighbor *u*, the node *v* identifies each
neighbor
such that
,
and
then forwards to *w* the message *M* along with the set
.

itemize

It turns out an optimal solution, i.e., *n*-1 messages and a time *D*,
for graphs that admit an all-shortest paths 1-IRS. Note that the
SSR-CAST algorithm must send per edge up to
extra
bits added to the message to represent the set .
Indeed, in [dlTNP98], it is proved that
is
composed of at most two intervals. The same performances hold for
graphs that admit a shortest path 1-IRS such that from each node the
routing paths induced by the 1-IRS form a tree. Such IRS are denoted
IRS
.
Note that the same algorithm can be used
to compute a minimum spanning tree of the graph.

- Is 1-IRS = 1-IRS ?

- Same question for

To conclude, we think that Interval Routing is certainly a sufficiently simple model for the theoretical study of the structural and implicit information of distributed networks. It is quite easy to predict that this model will be extended and/or exploited in many fashions. This is what seems to be the thesis of the paper of [dlTNP98].

I would like to thank the anonymous reviewers for their helpful comments.