Routing Tables for Planar Network in Optimal Space
Date Issued
2007
Date
2007
Author(s)
Liu, Hung-Wei
Abstract
We address the problem of designing compact routing tables for an unlabeled n-node connected planar graph G.For each node r of G, a routing spanning tree T_r rooted at r is given. T_r describes how node r forwards packets to the rest of G.or node r of T_{r}, it has distinct ports in the range {1, 2, ..., d_r }, where d_r is the degree of node r. ne port is assigned to one neighbor of r in a one-to-one manner. e have the freedom to decide the policies about how to assign label and port number of each node of G.e denote the port number of node r, which routes packets to the destination node v, as port_r(v).he routing table design problem is to design a compact routing table R_r for r such that port_r(v) can be answered from R_r and the label of v.ased on orderly spanning trees, Lu gave the best previously known result for this problem [COCOON 2002, pages 57-66]: Each port_r(v) is computable in O(log^{2+ε}{n}) bit operations for any positive constant ε, and the number of bits needed to encode each R_r is at most 7.181n + o(n). n this thesis, we make trade-off in the code length of R_r and computation time. After preprocessing in O(nlog{n}) time, the code length of R_r is information-theoretically optimal, and the time required to answer port_r(v) is O(log^{2+ε}{n}) time under word RAM model for any positive constant ε.
Subjects
network
planar graph
routing table
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-96-R93944009-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):c1a21bdf2b431fd55f816286af6989fe