Efficiency of Interval Routing: Dilation and Stretch Factor

Whereas compactness, linearity, and strictness are qualitative parameters of the labeling, we can also define several other criteria to measure the quality of the routing induced by the IRS. Here the graphs considered have uniform weights on all the links.

By taking a labeling like a depth first search along a minimum
spanning tree, the result of [SK85] implies that every graph *G*
of diameter *D* satisfies 1-
(more precisely, twice
the radius of *G*). Moreover, by combining Theorem 2,
we can conclude that every graph of diameter *D* has a 1-SIRS of
dilation at most 2*D* which can be implemented with
bits
in each router.

First, let us emphasize that the behavior between 1-IRS and 1-LIRS is different for the dilation.

The following result of [TL97b] shows that the IRS proposed by [SK85] based on a spanning tree is close to the optimal.

However, allowing more than one interval per edge, it is possible to decrease the dilation.

Combined with the result of [GP97] (cf. the remark of Theorem 15), it is possible to improve the labeling of the regions defined in the proof of [KRS97a] in order to show that actually one can choose .

It should be noted that the dilation is quite sensitive to the additive term around 3/2 the diameter.

For bounded degree graphs we have:

- Is the lower bound for the dilation of 1-LIRS tight?

- What is the smallest integer

Although, using a 1-IRS based on depth first search, the routing path lengths remains always linear in the diameter, this length might be very large for nodes that are relatively close.

In practice we are interested in designing *k*-IRS with the smallest
possible stretch factor. So, IRS of stretch factor 1 is of special
interest.

So, shortest path IRS are IRS of stretch factor 1.

The compactness of *G*=(*V*,*E*) is called sometimes the IRS number of
*G*. As we saw previously the space complexity for the storage of a
routing scheme in *x* is
bits or
bits in total. Therefore the compactness, *k*, is an important
parameter in the design of compact routing schemes.

We can define similarly the linear compactness ( ) and the strict or strict-linear compactness ( and ) of graphs. However, up to an additive constant these variants are equivalent.

The dilation of any *t*-regional IRS is at most *n*-(*t*+1), if *n*-(*t*+1)
> *t*+1, i.e., if
.
So, the stretch factor of a
*t*-regional IRS is at most *n*/(*t*+1) - 1.

- Is there an

- What are the general bounds for

- Do all graphs support a 1-regional 1-IRS?

We will see that there is no hope to extend Theorem 11
to 2-regional IRS. Indeed in Paragraph 3.1,
Theorem 16 states that shortest path IRS in *n*-node
graphs of diameter 2 require *n*/4 - *o*(*n*) intervals in the
worst-case. The 2-regional linear IRS satisfy the following property:

The parameters dilation and stretch factor do not necessary reflect the quality of a routing scheme. The density of long routing paths may be small. We believe that for a better analysis of the real networks it would be relevant to consider the average dilation and the average stretch factor.

In the next definition
denotes the routing path length
induced by the routing scheme *R* from *x* to *y*, and *s*(*x*,*y*) the
ratio between
and the distance between *x* and *y*.

The average stretch factor has been studied for Interval Routing in 2D-grids in [SML94]. For general graphs we have:

- What are the bounds on average dilation and average stretch factor of