An <i>Interval Routing Scheme (IRS)</i> 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 <i>k</i> intervals per edge label is called a <i>k-IRS</i>. In this thesis, we propose a new type of interval routing scheme, called an <i>Ordered Interval Routing Scheme (OIRS)</i>, that uses an ordering of the outgoing edges at each vertex and allows nondisjoint intervals in the labels of those edges. Our results on a number of graphs show that using an OIRS instead of an IRS reduces the size of the routing tables in the case of <i>optimal</i> routing, i. e. , routing along shortest paths. We show that optimal routing in any <i>k</i>-tree is possible using an OIRS with at most 2<sup>k-1</sup> intervals per edge label, although the best known result for an IRS is 2<sup>k+1</sup> 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, <i>k</i>-garland graphs and a few other graphs.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/1137 |
| Date | January 2004 |
| Creators | Ahmed, Mustaq |
| Publisher | University of Waterloo |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Format | application/pdf, 624258 bytes, application/pdf |
| Rights | Copyright: 2004, Ahmed, Mustaq. All rights reserved. |
Page generated in 0.0018 seconds