請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40529
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 呂學一(Hsueh-I Lu) | |
dc.contributor.author | Hung-Wei Liu | en |
dc.contributor.author | 劉弘偉 | zh_TW |
dc.date.accessioned | 2021-06-14T16:50:20Z | - |
dc.date.available | 2008-08-05 | |
dc.date.copyright | 2008-08-05 | |
dc.date.issued | 2007 | |
dc.date.submitted | 2008-07-31 | |
dc.identifier.citation | [1] T. Bell, J. Cleary, and I. Witten. Text compression. Prentice-Hall, Inc. Upper Saddle River, NJ,
USA, 1990. [2] Y.-T. Chiang, C.-C. Lin, and H.-I. Lu. Orderly spanning trees with applications. SIAM Journal on Computing, 34(4):924–945, Feb. 2005. [3] P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 21:194–203, 1975. [4] C. Gavoille and N. Hanusse. Compact routing tables for graphs of bounded genus (extended abstract). In Proceeding of 26th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 1644:pages 351–360, Spinger, July 1999. [5] X. He, M.-Y. Kao, and H.-I. Lu. A fast general methodology for information-theoretically optimal encodings of graphs. SIAM Journal on Computing, 30(3):838–846, 2000. [6] H.-I. Lu. Improved compact routing tables for planar networks via orderly spanning trees. In Proceedings of the 8th Annual International Computing and Combinatorics Conference, pages pages 57–66, August 15-17, 2002, Singapore, LNCS 2387, Springer, 2002. [7] H.-I. Lu and C.-C. Yeh. Balanced parentheses strike back. ACM Transactions on Algorithms, 4(3):1–13, 2008. [8] G. Miller. Finding small simple cycle separators for 2-connected planar graphs. Journal of Computer and System Sciences, 32:265–279, 1986. [9] R. Raman, V. Raman, and S. Rao. Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In Proceedings of the 13th annual ACM-SIAM symposium on Discrete algorithms, pages 233–242, 2002. [10] P. van Emde Boas. Machine models and simulation. In Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity (A), pages 1–66. MIT Press, 1990. [11] M. Yannakais. Embedding planar graphs in four pages. Journal of Computer and System Sciences,38(1):36–67, 1989. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40529 | - |
dc.description.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)。 | zh_TW |
dc.description.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. 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 ε. | en |
dc.description.provenance | Made available in DSpace on 2021-06-14T16:50:20Z (GMT). No. of bitstreams: 1 ntu-96-R93944009-1.pdf: 603606 bytes, checksum: 00df7a7225ee9241799ab48f99865cef (MD5) Previous issue date: 2007 | en |
dc.description.tableofcontents | Acknowledgements . . . . . . . . . .. . . . . . . . . . . . . . . . i
Chinese Abstract . . . . . . . . . .. . . . . . . . . . . . . . . . ii English Abstract . . . . . . . . . .. . . . . . . . . . . . . . . . iii Contents . . . . . . . . . .. . . . . . . . . . . . . . . . . . v List of Tables . . . . . . . . . .. . . . . . . . . . . . . . . . . vii List of Figures . . . . . . . . . .. . . . . . . . . . . . . . . . viii 1 Introduction . . . . . . . . . .. . . . . . . . . . . . . . . . . 1 2 Preliminaries . . . . . . . . . .. . . . . . . . . . . . . . . . 5 3 Design of routing table Rr . . . . . . . . . .. . . . . . . . . . 8 3.1 Label scheme . . . . . . . . . .. . . . . . . . . . . . . . 11 3.1.1 The method of dividing tree . . . . . . . . . .. . . . 16 3.1.2 Generate a T′r with the same routing table as Tr . . . 19 3.2 Port assignment . . . . . . . . . .. . . . . . . . . . . . 25 3.3 Compact routing table . . . . . . . . . .. . . . . . . . . 26 4 Conclusion . . . . . . . . . .. . . . . . . . . . . . . . . . . 29 Bibliography . . . . . . . . . .. . . . . . . . . . . . . . . . . . 30 | |
dc.language.iso | en | |
dc.title | 平面網路路由表之空間最佳化 | zh_TW |
dc.title | Routing Tables for Planar Network in Optimal Space | en |
dc.type | Thesis | |
dc.date.schoolyear | 96-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 徐讚昇(Tsan-sheng Hsu),陳維美(Wei-Mei Chen) | |
dc.subject.keyword | 網路,平面圖,路由表, | zh_TW |
dc.subject.keyword | network,planar graph,routing table, | en |
dc.relation.page | 31 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2008-07-31 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊網路與多媒體研究所 | zh_TW |
顯示於系所單位: | 資訊網路與多媒體研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-96-1.pdf 目前未授權公開取用 | 589.46 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。