平面網路路由表之空間最佳化

Abstract

我們發表一個方法,是針對$n$個點的無標籤的連通平面圖G,設計精簡的路由表的問題。 對於G上的每一個點r,會給予一個以r為根的路由生成樹T_r,它描述了封包如何從r送到G上其它的點。 而T_r上的根r,他有著d_r個編號不同,而且範圍在{1,2,...,d_r}的埠。 d_r是r的鄰居的數目。 每個埠會一對一的分配給他的每個鄰居。 對G上的每一個點,我們可以自由的決定如何分配每個點的標籤和埠號。 而當封包由r送到v時,所經過的埠號,我們稱為port_r(v)。 而路由表設計就是要設計一個路由表使得只要有R_r和v點的標籤,就能回答port_r(v)的問題。 根據條理伸長樹,目前最好的一個解, 每個port_r(v)在log^{2+ε}{n}的位元運算內就能算出來,ε為一個正數, 而且R_r最長需要7.181n+o(n)個位元記錄。 在本篇論文中,花費了O(nlog{n})的時間做前置處理後，我們改善R_r至最佳的長度,並且在word RAM計算模型下, 可以在log^{2+ε}(n)的時間內回答port_r(v)。

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. For 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. One port is assigned to one neighbor of r in a one-to-one manner. We have the freedom to decide the policies about how to assign label and port number of each node of G. We denote the port number of node r, which routes packets to the destination node v, as port_r(v). The 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. Based 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). In 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 ε.