Improved Compact Routing Tables for Planar Networks via Orderly Spanning Trees
Hsueh-I Lu · SIAM Journal on Discrete Mathematics · 2010
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 $T_r$ 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,\ldots,\mathit{deg}_r$, where $\mathit{deg}_r$ is the degree of r in $T_r$. Each port of r is supposed to be assigned to a neighbor of r in $T_r$ in a one-to-one manner. For each node v of G with $v eq r$, let $\mathit{port}_r(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 $R_r$ for each node r such that $\mathit{port}_r(v)$ can be determined merely from $R_r$ 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 $\mathit{port}_r(v)$ is computable from $R_r$ and the label of v in $O(\log^{2+\epsilon}n)$ time for any positive constant $\epsilon$. The number of bits required to encode each $R_r$ is at most $8n+o(n)$. The time required to compute each $R_r$ 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 $R_r$: Each $\mathit{port}_r(v)$ is computable from $R_r$ and the label of v in $O(\log^{1+\epsilon}n)$ time for any positive constant $\epsilon$. The number of bits required to encode each $R_r$ is at most $7.181n+o(n)$. The overall code length of all n routing tables is at most $7n^2+o(n^2)$ bits.