<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T19:47:03Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/1137" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/1137</identifier><datestamp>2017-03-21T19:35:19Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" lang="en" authority="3d727478-ae34-41ca-a89e-169cf002696a" confidence="600">Ahmed, Mustaq</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2006-08-22T14:23:34Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2006-08-22T14:23:34Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2004</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2004</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/1137</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">An &amp;lt;i&amp;gt;Interval Routing Scheme (IRS)&amp;lt;/i&amp;gt; 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 &amp;lt;i&amp;gt;k&amp;lt;/i&amp;gt; intervals per edge label is called a &amp;lt;i&amp;gt;k-IRS&amp;lt;/i&amp;gt;.   In this thesis, we propose a new type of interval routing scheme, called an &amp;lt;i&amp;gt;Ordered Interval Routing Scheme (OIRS)&amp;lt;/i&amp;gt;, 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 &amp;lt;i&amp;gt;optimal&amp;lt;/i&amp;gt; routing, i.  e.  , routing along shortest paths.   We show that optimal routing in any &amp;lt;i&amp;gt;k&amp;lt;/i&amp;gt;-tree is possible using an OIRS with at most 2&amp;lt;sup&amp;gt;k-1&amp;lt;/sup&amp;gt; intervals per edge label, although the best known result for an IRS is 2&amp;lt;sup&amp;gt;k+1&amp;lt;/sup&amp;gt; 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, &amp;lt;i&amp;gt;k&amp;lt;/i&amp;gt;-garland graphs and a few other graphs.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">624258 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="rights" lang="en">Copyright: 2004, 
  Ahmed, Mustaq. All rights reserved.</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Interval Routing Scheme</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Routing</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">OIRS</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">OLIRS</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">IRS</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Ordered Interval Routing Schemes</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>