Next: Complexity of Characterization Up: The Model of Interval Previous: Characterizations   Contents

## 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 2D 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:

Open question 1
- Is the lower bound for the dilation of 1-LIRS tight?
- What is the smallest integer k (as function of n and D) such that k- , for every n-node graph G of diameter D?

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.

Open question 2
- Is there an n-node graph G, for every n large enough, such that 1- ? (The best known lower bound is a constant. It is derived from the result of [TL97a] showing the construction of a graph G such that 1- ).
- What are the general bounds for k- , k > 1?
- 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:

Open question 3
- What are the bounds on average dilation and average stretch factor of k-IRS for arbitrary graphs?

Next: Complexity of Characterization Up: The Model of Interval Previous: Characterizations   Contents

2000-03-21