Improved Compact Routing Tables for Planar Networks via Orderly Spanning Trees
Resource
SIAM J DISCRETE MATH,23(4),2079-2092.
Journal
SIAM Journal on Discrete Mathematics
Pages
2079-2092
Date Issued
2010-01
Date
2010-01
Author(s)
Lu, Hsueh-I
Abstract
We address the problem of designing compact routing tables for an unlabeled connected n-node planar network G. For each node r of G, the designer is given a routing spanning tree Tr of G rooted at r, which specifies the routes for sending packets from r to the rest of G. Each node r of G is equipped with ports 1,2,..., degr, where degr is the degree of r in T r. Each port of r is supposed to be assigned to a neighbor of r in Tr in a one-to-one manner. For each node v of G with v ≠ r, let portr(v) be the port to which r should forward packets with destination v. Under the assumption that the designer has the freedom to determine the label and the port assignment of each node in G, the routing table design problem is to design a compact routing table Rr for each node r such that portr(v) can be determined merely from Rr and the label of v. Compact routing tables for various network topologies have been extensively studied in the literature. Planar networks are particularly important for routing with geometric metrics. Based upon four-page decompositions of G, Gavoille and Hanusse gave the best previously known polynomial-time computable result for this problem with linear-space routing tables, where the time complexity is measured under the conventional unit-cost RAM model of computation: • Each portr(v) is computable from Rr and the label of v in O(log2+η n) time for any positive constant ε. • The number of bits required to encode each Rr is at most 8n + o(n). • The time required to compute each Rr is O(n). Based on orderly spanning trees of G, our design achieves the following improved bounds without increasing the time complexity for computing each Rr: • Each portr(v) is computable from R r and the label of v in O(log1+η n) time for any positive constant ε. • The number of bits required to encode each Rr is at most 7.181n + o(n). • The overall code length of all n routing tables is at most 7n2 + o(n2) bits. © 2009 Society for Industrial and Applied Mathematics.
Type
journal article