# 臺灣博碩士論文加值系統

(44.197.230.180) 您好！臺灣時間：2022/08/20 10:54

:::

### 詳目顯示

:

• 被引用:0
• 點閱:149
• 評分:
• 下載:0
• 書目收藏:0
 在網路上的路由器扮演著轉送封包的重要角色，影響網路效能的因素之一在於路由器的路徑表設計好壞。路由器必須能根據每個封包的目的網路位址，在路徑表中查詢最適合封包去的下一站。好的路徑表設計，必須能提供有效率的查詢，並在有限的記憶體資源下，能滿足低空間的需求。 本論文的研究主題專注於在平面網路上簡潔路徑表的設計。利用平面圖已知最好的壓縮編碼工具-條理伸張樹(orderly spanning tree)，我們希望能改進前人的結果，即每個路徑表大小能比8n+o(n) bits還小，且維持相差不多的查詢時間。更精確地描述，對於一個有n個無編號節點的無向圖，我們研究如何將每個節點上的最佳網路路徑代表圖(例如最短路徑擴張樹)，壓縮成一個簡潔的路徑表，使得以下的目標可以被達成： (a) 用來識別每個節點所需的編號長度很短 (b) 每個節點所需記住的路徑表很小 (c) 根據路徑表用來計算下一個節點所需的時間很小 針對平面網路，我們的改進結果如下： 結果一：改良後的每個路徑表最多只有7.2n+o(n)。計算下一個節點所需花的時間在O(log^(1+ε)n)之內，適用任一正的常數ε。 結果二：保證n個路徑表總共花的記憶空間大小在7.2n^2+o(n^2)之內。 結果三：在我們所提的方法中，若允許每個節點的編號長度為原來的3倍，則每個路徑表所需的大小可減少至7.05n+(n)。
 We address problem of designing compact routing tables for an n-node unlabeled connected network G. For each node r of G, we are given a spanning tree Tr of G rooted at r. Each node r of G are equipped with ports 1,2,…,dr, where dr is the degree of r in Tr. Each port of r is supposed to be assigned to a neighbor of r in Tr in a one-to-one manner. Suppose that we have the freedom to determine (a) the node labels of G, and (b) the assignment of r’s ports to the neighbors of r in Tr. For each node v of G with v≠r, let pr(v) denote the port of r assigned to s, where s is the neighbor of r in Tr whose removal disconnects v and r in Tr. The requirement of the table design problem is to come up with a compact routing table Rr for each node r of G such that pr(v) can be determined only from Rr and the label of v. Natural objectives of this problem include 1. minimizing the time required to compute the port number of s from Rr; 2. minimizing the bit count of the label of each node; 3. minimizing the bit count of Rr for each node r of G; and 4. minimizing the overall bit count of Rr for all nodes r of G. Since these objectives are often in conflict, several trade-offs have been shown in the literature. In particular, Gavoille and Hanusse showed in 1999 how to ensure that each Rr spends no more than 8n + o(n) bits, while each pr(v) can be answered from Rr and the label of v in O(log^(2+ε) n) time for any positive constant . In the present paper, we obtain the following improved results: Result 1: The bit count of each routing table is improved to at most 7.2n+o(n). Each routing decision takes O(log^(2+ε) n) time for any positive constant ε. Result 2: The overall bit count of all n routing tables is ensured to be no more than 7.05n^2+o(n^2). Result 3: In the above designs, the label of each node is restricted to be (log n) bits. If the label of each is allowed to be 3(log n) bits, then the bit count of each routing table can be reduced to no more than 7.05n+o(n).
 Chapter 1 Introduction 1.1 The routing problem 1.2 Compact routing 1.3 Our contribution Chapter 2 Our routing tables 2.1 Preliminaries 2.2 The content of our routing table Chapter 3 Our routing algorithm 3.1 Determining the parent in the routing tree 3.2 Determining the port number 3.3 Implementation 3.3.1 First routing algorithm 3.3.2 Faster routing algorithm Chapter 4 Extensions and concluding remarks 4.1 Extensions 4.2 Open questions
 [1] Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms,Washington, DC, 7—9 Jan. 2001.[2] S. R. Arikati, A. Maheshwari, and C. D. Zaroliagis. Efficient computation ofimplicit representations of sparse graphs. Discrete Applied Mathematics, 78:1—16, 1997.[3] A. Brodnik and J. I. Munro. Membership in constant time and almost-minimumspace. SIAM Journal on Computing, 28(5):1627—1640, 2000.[4] L. P. Chew. There are planar graphs almost as good as the complete graph.Journal of Computer and System Sciences, 39:205—219, 1989.[5] Y.-T. Chiang, C.-C. Lin, and H.-I. Lu. Orderly spanning trees with applicationsto graph drawing and graph encoding. In ACM/SIAM [1], pages 506—515.[6] R. C.-N. Chuang, A. Garg, X. He, M.-Y. Kao, and H.-I. Lu. Compact encodingsof planar graphs via canonical ordering and multiple parentheses. In K. G.Larsen, S. Skyum, and G. Winskel, editors, Proceedings of the 25th InternationalColloquium on Automata, Languages, and Programming, Lecture Notes in ComputerScience 1443, pages 118—129, Aalborg, Denmark, 1998. Springer-Verlag.[7] D. R. Clark. Compact PAT Trees. PhD thesis, University of Waterloo, 1996.[8] Cowen. Compact routing with minimum stretch. In SODA: ACM-SIAM Symposiumon Discrete Algorithms (A Conference on Theoretical and ExperimentalAnalysis of Discrete Algorithms), 1999.[9] N. Deo and B. Litow. A structural approach to graph compression. In Proceedingsof MFCS’98 Satellite Workshop on Communications, pages 91—101, 1998.[10] T. Eilam, C. Gavoille, and D. Peleg. Compact routing schemes with low stretchfactor. In 17th Annual ACM Symposium on Principles of Distributed Computing(PODC), pages 11—20. ACM PRESS, Aug. 1998.[11] T. Feder and R. Motwani. Clique partitions, graph compression and speeding-upalgorithms. Journal of Computer and System Sciences, 51(2):261—272, 1995.[12] P. Fraigniaud and C. Gavoille. Local memory requirement of universal routingschemes. In 8th Annual ACM Symposium on Parallel Algorithms and Architecture(SPAA), pages 183—188. ACM PRESS, June 1996.[13] P. Fraigniaud and C. Gavoille. Universal routing schemes. Journal of DistributedComputing, 10:65—78, 1997.[14] P. Fraigniaud and C. Gavoille. A theoretical model for routing complexity. InL. Gargano and D. Peleg, editors, 5th International Colloquium on StructuralInformation & Communication Complexity (SIROCCO), pages 98—113. CarletonScientific, July 1998.[15] P. Fraigniaud and C. Gavoille. Routing in trees. In F. Orejas, P. G. Spirakis, andJ. v. Leeuwen, editors, 28th International Colloquium on Automata, Languagesand Programming (ICALP), volume 2076 of Lecture Notes in Computer Science,pages 757—772. Springer, July 2001.[16] P. Fraigniaud and C. Gavoille. A space lower bound for routing in trees. In19th Annual Symposium on Theoretical Aspects of Computer Science (STACS),volume Lecture Notes in Computer Science. Springer, Mar. 2002. To appear.[17] M. L. Fredman and D. E. Willard. Trans-dichotomous algorithms for minimumspanning trees and shortest paths. Journal of Computer and System Sciences,48(3):533—551, June 1994.[18] C. Gavoille. A survey on interval routing. Theoretical Computer Science,245(2):217—253, 2000.[19] C. Gavoille. Routing in distributed networks: Overview and open problems.ACM SIGACT News - Distributed Computing Column, 32(1):36—52, Mar. 2001.[20] C. Gavoille and M. Gengler. Space-efficiency of routing schemes of stretch factorthree. In D. Krizanc and P. Widmayer, editors, 4th International Colloquium onStructural Information & Communication Complexity (SIROCCO), pages 162—175. Carleton Scientific, July 1997.[21] C. Gavoille and M. Gengler. Space-efficiency of routing schemes of stretch factorthree. Journal of Parallel and Distributed Computing, 61:679—687, 2001.[22] C. Gavoille and E. Gu´evremont. On the compactness of bounded degree graphsfor shortest path interval routing. In L. M. Kirousis and E. Kranakis, editors,2nd International Colloquium on Structural Information & Communication Complexity(SIROCCO), pages 113—121. Carleton University Press, June 1995.[23] C. Gavoille and E. Gu´evremont. Worst case bounds for shortest path intervalrouting. Journal of Algorithms, 27:1—25, 1998.[24] C. Gavoille and N. Hanusse. Compact routing tables for graphs of boundedgenus. In J. Wiedermann, P. van Emde Boas, and M. Nielsen, editors, 26thInternational Colloquium on Automata, Languages and Programming, volumeLecture Notes in Computer Science 1644, pages 351—360. Springer, July 1999.[25] C. Gavoille and N. Hanusse. On compact encoding of pagenumber k graphs.Submitted for publication, 2001.[26] C. Gavoille, M. Katz, N. A. Katz, C. Paul, and D. Peleg. Approximate distancelabeling schemes. In F. M. auf der Heide, editor, 9th Annual European Symposiumon Algorithms (ESA), volume Lecture Notes in Computer Science 2161, pages476—488. Springer, Aug. 2001.[27] C. Gavoille and D. Peleg. The compactness of interval routing. SIAM Journalon Discrete Mathematics, 12(4):459—473, Oct. 1999.[28] C. Gavoille and D. Peleg. The compactness of interval routing for almost allgraphs. SIAM Journal on Computing, 31(3):706—721, 2001.[29] C. Gavoille and S. P´erenn`es. Memory requirement for routing in distributed networks.In 15th Annual ACM Symposium on Principles of Distributed Computing(PODC), pages 125—133. ACM PRESS, May 1996.[30] C. Gavoille and A. Zemmari. The compactness of adaptive routing tables.In M. Flammini, E. Nardelli, G. Proietti, and P. Spirakis, editors, 7th InternationalColloquium on Structural Information & Communication Complexity(SIROCCO), pages 127—140. Carleton Scientific, June 2000.[31] C. Gavoille and A. Zemmari. The compactness of adaptive routing tables. Journalof Discrete Algorithms, 2001. To appear.[32] R. Grossi and E. Lodi. Simple planar graph partition into three forests. DiscreteApplied Mathematics, 84:121—132, 1998.[33] X. He, M.-Y. Kao, and H.-I. Lu. Linear-time succinct encodings of planar graphsvia canonical orderings. SIAM Journal on Discrete Mathematics, 12(3):317—325,1999.[34] IEEE. Proceedings of the 38th Annual Symposium on Foundations of ComputerScience, Miami Beach, Florida, 20—22 Oct. 1997.[35] A. Itai and M. Rodeh. Representation of graphs. Acta Informatica, 17:215—219,1982.[36] G. Jacobson. Space-efficient static trees and graphs. In Proceedings of the 30thAnnual Symposium on Foundations of Computer Science, pages 549—554, ResearchTriangle Park, North Carolina, 30 Oct.—1 Nov. 1989. IEEE.[37] G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica,16(1):4—32, 1996.[38] K. Keeler and J.Westbrook. Short encodings of planar graphs and maps. DiscreteApplied Mathematics, 58:239—252, 1995.[39] C.-C. Liao, H.-I. Lu, and H.-C. Yen. Floor-planning via orderly spanning trees.Submitted for publication, 2001.[40] H.-I. Lu. Linear-time compression of bound-genus graphs into information theoreticallyoptimal number of bits. In Proceedings of the 13th Annual ACMSIAMSymposium on Discrete Algorithms, pages 223—224, San Francisco, 6—8Jan. 2002.[41] J. I. Munro. Tables. In Proceedings of the 16th Conference on Foundations ofSoftware Technology and Theoretical Computer Science, Lecture Notes in ComputerScience 1180, pages 37—42, Hyderabad, India, 1996. Springer-Verlag.[42] J. I. Munro and V. Raman. Succinct representation of balanced parentheses,static trees and planar graphs. In Proceedings of the 38th Annual Symposium onFoundations of Computer Science [34], pages 118—126.[43] J. I. Munro, V. Raman, and A. Storm. Representing dynamic binary treessuccinctly. In ACM/SIAM [1], pages 529—536.[44] M. Naor. Succinct representation of general unlabeled graphs. Discrete AppliedMathematics, 28:303—307, 1990.[45] R. Pagh. Low redundancy in static dictionaries with constant query time. SIAMJournal on Computing, 31(2):353—363, 2001.[46] D. Peleg. Distributed Computing: A Locality-Sensitive Approach. Monographson Discrete Mathematics and Applications. SIAM, 2000.[47] D. Peleg and E. Upfal. A trade-o® between space and efficiency for routingtables. Journal of the ACM, 36(3):510—530, 1989.[48] W. Schnyder. Planar graphs and poset dimension. Order, 5:323—343, 1989.[49] W. Schnyder. Embedding planar graphs on the grid. In Proceedings of the FirstAnnual ACM-SIAM Symposium on Discrete Algorithms, pages 138—148, 1990.[50] M. Thorup. Undirected single source shortest paths in linear time. In Proceedingsof the 38th Annual Symposium on Foundations of Computer Science [34], pages12—21.[51] M. Thorup. On RAM priority queues. SIAM Journal on Computing, 30:86—109,2000.[52] P. van Emde Boas. Machine models and simulations. In J. van Leeuwen, editor,Handbook of Theoretical Computer Science, volume A, chapter 1, pages 1—60.Elsevier, Amsterdam, 1990.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 使用有序擴展樹及新增的括號字串之支援查詢功能的平面圖編碼

 1 2. 沈中華（1999），「銀行危機形成原因探討」，存款保險資訊季刊，第十二卷第四期，頁88-102。 2 1. 沈中華，謝孟芬（1999），「事件風險：以貨幣危機及銀行危機為例」，企銀季刊，第廿二卷第二期，頁1-17。 3 7.梅家瑗（1999），「從亞洲金融危機談預警指標」，主計月報，第八十七卷第一期，頁37-45。

 1 二維置移排序 2 有向平面圖上的最小切割與最短迴圈 3 支援零知識查詢的集合封存方案 4 內部史坦納森林之近似演算 5 一個相容超樹問題的改進演算法 6 正則雙分圖與有限共鄰圖上之隨機著色 7 點棒可視圖的厚度最佳漸近上界 8 平面網路路由表之空間最佳化 9 四連接平面圖的可視性呈現之研究 10 具優先權之網路自私路由 11 矩形繪圖緊密編碼法之改良 12 市場均衡之可近似性之拓展 13 平面網路上防疫問題之近似演算法 14 加權外部平面圖之最小迴圈基底 15 字尾樹在快速感測器資料傳送的應用

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室