Ordered interval routing schemes

An Interval Routing Scheme (IRS) represents the routing tables in a network in a space-efficient way by labeling each vertex with an unique integer address, and the outgoing edges at each vertex with disjoint subintervals of these addresses. An IRS that has at most k intervals per edge label is called a k-IRS. In this paper, we propose a new type of interval routing scheme, called an Ordered Interval Routing Scheme (OIRS), that uses an ordering of the outgoing edges at each vertex and allows non-disjoint intervals in the labels of those edges. We show for a number of graph classes that using an OIRS instead of an IRS reduces the size of the routing tables in the case of optimal routing, i.e., routing along shortest paths. We show that optimal routing in any k-tree is possible using an OIRS with at most 2k−1 intervals per edge label, although the best known result for an IRS is 2k+1 intervals per edge label. Any torus has an optimal 1-OIRS, although it may not have an optimal 1-IRS. We present similar results for the Petersen graph, k-garland graphs and a few other graphs.