Back to search

University of Waterloo

Ordered Interval Routing Schemes

Abstract

dc:description.abstract

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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2004

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ahmed, Mustaq

Subjects

dc:subject × 6

Rights

dc:rights
Statement dc:rights
  • Copyright: 2004, Ahmed, Mustaq. All rights reserved.
Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/1137

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ahmed, Mustaq. Ordered Interval Routing Schemes. University of Waterloo, 2004. http://hdl.handle.net/10012/1137