The routing information of a node is entirely determined by the
knowledge of all the labels (its local name and the labels of its
incident arcs). Implicitly, in the Interval Routing model one can
permute the output ports numbers in advance. We mean that for the
routing decision of a node x towards a destination y, x is able
to determine the output port number such that
,
and
to send the message onto this port (i.e., through the edge e)
without extra information, excepted, of course, the knowledge of the
label
.
We invite the reader to see [BHV96] for a discussion of the
impact of the node and/or port relabeling on routing information
complexity. In all the following, the function
denotes the
logarithm in base 2.
Let x be a node. For each
,
we denote
by [ai,bi] the i-th interval of x (with Condition 2b the
intervals do not overlap), and by ei the output port number on
which is assigned this interval. First, we remark that only 2
intervals at most can be non-strict and/or cyclic. So, with an
overhead of
bits only, it is easy to implement any
k-IRS, k-SIRS, or k-LIRS, from its strict and linear version.
W.l.o.g. we assume that the ai's are sorted in increasing order,
the intervals [ai,bi] are strict and linear, and we know the
integers n, d, K, and
with an overhead of
bits2. To code all the labels in x, it
suffices to store the sequences
and
.
Indeed the bi's can be computed as
follows: If i<K, then bi=ai+1-1 (=ai+1-2 if
), otherwise bK = n (=n-1 if
). S1
is a sequence of K distinct integers in the range 1 to n,
therefore it can be stored with
bits [LV93].
Let d be the number of output ports used by the IRS in x, i.e.,
.
The IRS does not use necessarily all
the arcs incident to x, so d might be less than the degree of x.
The number of ways to obtain S2 is at most
.
Indeed,
is a sequence composed of exactly d
different values ei taken from
located in K
possible places, and of K-d independent integers of
.
So, there is at most
choices of
the d different values of the sequences, and dK-d ways for the
K-d other elements; thus a total of
different sequences
.
However the permutation of
the output ports numbers can be made in advance. Since d ports are
used, at least d! sequences are equivalent up to a permutation of
the ports, coding the same IRS. Each different IRS has a sequence
S2 which can be coded with
bits.
Thus the total number of bits used to store all the labels in x is
bounded by
,
for a suitable constant
.
On the other hand,
.
Moreover
,
and
.
Hence
So, let us assume .
If, furthermore,
,
where
,
then it
implies that
,
which is impossible for
.
So,
.
In this case it implies that:
Theorem 1 implies that every 1-IRS (and its variants)
can be coded with
bits per node. Moreover, the
implementation is quite easy using an n-bit vector coding within the
1's the left-boundary of each interval. The time complexity of the
routing function is linear in n in this case (the time to locally
compute the output port from any destination). However, adding a table
of
integers, i.e., o(n) extra bits for some
function f such that
,
the routing function can
compute the output port in O(f(n)) bit-operations: Split the vector
in
blocks of length at most f(n) bits, and tabulate
for the ith block the number of 1's which is contained in the vector
up to the position
.
One can even reduce the amount of bits needed to route for trees.
Let T be an n-node tree, and r be a node of T chosen as
the root of T. For every edge (u,v), the graph obtained by
removing (u,v) in T is composed of two connected components. We
denote by T(u,v) the component that contains v. We say
that T(u,v) is the subtree of T induced by (u,v). For all
integers n,k, a k-partition of n is an integer sequence
such that
,
and
.
We label the nodes of T with a particular depth first search scheme
as follows: We initialize the labeling process by labeling r with 1.
For each node x, let
be the children of x
ordered such that
.
We start to label recursively the subtrees
in this order. If
,
we
assign the output port number 1 to the edge towards r, i.e., the
edge (x,y) with y the father of x, and for each
the output port number i+1 to the edge (x,yi).
For x=r we assign the output port number i to the edge (x,yi).
Consider a node .
We set
,
for each
,
set
ni = |V(T(x,yi))|, and finally we set
.
We remark that
,
or
equivalently
is a k-partition of n-n0. We
store in x:
itemize
the label of x;
the values n, n0, and k;
the k-partition of n-n0:
.
itemize
For x = r we set ,
and n0 = 1, and we store similarly
the values n, k, and the k-partition of n-n0 defined by
.
To simplify, x and y represent the labels of
the node x and y respectively.
The routing scheme is the following: Assume the node x must route a
message to the destination y. If x=y then the routing process
ends. If
,
then the message is forwarded to
the father of x through the output port 1 (the case never happens if
x = r). Otherwise, one computes the unique integer
such
that
.
The
message is forwarded through the output port p+1, if
,
and
p for x = r. Clearly such a scheme corresponds to a 1-SIRS,
because the union of all the intervals cover
,
and all
the intervals are pairwise disjoint. Moreover they never contain x.
The process routes correctly. Indeed, by the construction of the
node-labeling if
,
then y is necessarily a node of the subtree T(x,yp),
and the output port assigned to the edge (x,yp) is p+1 if
,
and p if x = r. And if
,
then y is
not a descendent of x, and hence must be forwarded to its father.
Let us compute the amount of information required. The integer values
of n, n0, k, and the label of x can be stored using
bits. Knowing n and k, any k-partition of n,
P, can be coded using at most
bits, where Un
is the total number of partitions of n. Indeed, there exists very
simple algorithm that, knowing n, enumerates all the partitions of
n. So, it suffices to store the index of P in such an enumeration.
Furthermore, we have the well-known formula due to Harder and
Ramanujan in 1917 [Hal86, Equation (4.2.7) page 44]:
Note that in [EGP98], it is shown that to route in an arbitrary
n-node tree
bits are required, showing that the
bound of Theorem 2 is tight.
We remark that the distinction between the variants of Interval
Routing has no real impact on the coding of IRS in local memory of the
nodes, up to an additive term of
bits. The interest of
these variants will appear in Theorem 43 of
Section 3.8.
Since every edge needs
bits of information to code its
labels, the total amount of routing information for the entire graph
G=(V,E) is bounded by
bits.