Optimum multi-dimensional interval routing schemes on networks with dynamic cost links
Yashar Ganjali · 2003
I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required nal revisions, as accepted by my examiners. I understand that my thesis may be electronically available to public. ii Routing messages between pairs of nodes is one of the most fundamental tasks in any distributed computing system. An Interval Routing Scheme (IRS) is a well-known, space-eÆcient routing strategy for routing messages in a network. In this scheme, each node of the network is assigned an integer label and each link at each node is labeled with an interval. The interval assigned to a link l at a node v indicates the set of destination addresses of the messages which should be forwarded through l at v. When studying interval routing schemes, there are two main problems to be considered: a) Which classes of networks do support a specic routing scheme? b) Assuming that a given network supports IRS, how good are the paths traversed by messages? The rst problem is known as the characterization problem and has been studied for several