Facebook Instagram Twitter RSS Feed PodBean Back to top on side

Optimum Multi-Dimensional Interval Routing Schemes on Networks with Dynamic Cost Links

In: Computing and Informatics, vol. 22, no. 1
Yashar Ganjali

Details:

Year, pages: 2003, 1 - 17
Keywords:
Internal routing, networks, routing algorithms, dynamic, multi-dimensional, characterization
About article:
One of the fundamental tasks in any distributed computing system is routing messages between pairs of nodes. An Interval Routing Scheme (IRS) is a~space efficient way of routing messages in a network. The problem of characterizing graphs that support an IRS is a well-known problem and has been studied for some variants of IRS. It is natural to assume that the costs of links may vary over time (dynamic cost links) and to try to find an IRS which routes all messages on shortest paths (optimum IRS). In this paper, we study this problem for a~variant of IRS in which the labels assigned to the vertices are $d$-ary integer tuples ($d$-dimensional IRS). The only known results in this case are for specific graphs like hypercubes, $n$-dimensional grids, or for the 1-dimensional case. We give a complete characterization for the class of networks supporting multi-dimensional strict and linear (no cyclic intervals) interval routing schemes with dynamic cost links.
How to cite:
ISO 690:
Ganjali, Y. 2003. Optimum Multi-Dimensional Interval Routing Schemes on Networks with Dynamic Cost Links. In Computing and Informatics, vol. 22, no.1, pp. 1-17. 1335-9150.

APA:
Ganjali, Y. (2003). Optimum Multi-Dimensional Interval Routing Schemes on Networks with Dynamic Cost Links. Computing and Informatics, 22(1), 1-17. 1335-9150.