跳到主要內容

臺灣博碩士論文加值系統

(44.197.230.180) 您好!臺灣時間:2022/08/20 10:54
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳冠伶
研究生(外文):Kuan-Ling Chen
論文名稱:平面網路中藉由條理伸張樹改良的路徑表
論文名稱(外文):Improved Succinct Routing Tables for Planar Networks (via Orderly Spanning Trees)
指導教授:黃能富黃能富引用關係呂學一
指導教授(外文):Nen-Fu HuangHsueh-I Lu
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:31
中文關鍵詞:平面網路條理伸張樹路徑表路由表
外文關鍵詞:compact routingorderly spanning treerouting tablesplanar networksgraph encoding
相關次數:
  • 被引用被引用: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 of
implicit representations of sparse graphs. Discrete Applied Mathematics, 78:1—
16, 1997.
[3] A. Brodnik and J. I. Munro. Membership in constant time and almost-minimum
space. 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 applications
to 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 encodings
of planar graphs via canonical ordering and multiple parentheses. In K. G.
Larsen, S. Skyum, and G. Winskel, editors, Proceedings of the 25th International
Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer
Science 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 Symposium
on Discrete Algorithms (A Conference on Theoretical and Experimental
Analysis of Discrete Algorithms), 1999.
[9] N. Deo and B. Litow. A structural approach to graph compression. In Proceedings
of MFCS’98 Satellite Workshop on Communications, pages 91—101, 1998.
[10] T. Eilam, C. Gavoille, and D. Peleg. Compact routing schemes with low stretch
factor. 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-up
algorithms. Journal of Computer and System Sciences, 51(2):261—272, 1995.
[12] P. Fraigniaud and C. Gavoille. Local memory requirement of universal routing
schemes. 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 Distributed
Computing, 10:65—78, 1997.
[14] P. Fraigniaud and C. Gavoille. A theoretical model for routing complexity. In
L. Gargano and D. Peleg, editors, 5th International Colloquium on Structural
Information & Communication Complexity (SIROCCO), pages 98—113. Carleton
Scientific, July 1998.
[15] P. Fraigniaud and C. Gavoille. Routing in trees. In F. Orejas, P. G. Spirakis, and
J. v. Leeuwen, editors, 28th International Colloquium on Automata, Languages
and 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. In
19th 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 minimum
spanning 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 factor
three. In D. Krizanc and P. Widmayer, editors, 4th International Colloquium on
Structural Information & Communication Complexity (SIROCCO), pages 162—
175. Carleton Scientific, July 1997.
[21] C. Gavoille and M. Gengler. Space-efficiency of routing schemes of stretch factor
three. Journal of Parallel and Distributed Computing, 61:679—687, 2001.
[22] C. Gavoille and E. Gu´evremont. On the compactness of bounded degree graphs
for 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 interval
routing. Journal of Algorithms, 27:1—25, 1998.
[24] C. Gavoille and N. Hanusse. Compact routing tables for graphs of bounded
genus. In J. Wiedermann, P. van Emde Boas, and M. Nielsen, editors, 26th
International Colloquium on Automata, Languages and Programming, volume
Lecture 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 distance
labeling schemes. In F. M. auf der Heide, editor, 9th Annual European Symposium
on Algorithms (ESA), volume Lecture Notes in Computer Science 2161, pages
476—488. Springer, Aug. 2001.
[27] C. Gavoille and D. Peleg. The compactness of interval routing. SIAM Journal
on Discrete Mathematics, 12(4):459—473, Oct. 1999.
[28] C. Gavoille and D. Peleg. The compactness of interval routing for almost all
graphs. 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 International
Colloquium 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. Journal
of Discrete Algorithms, 2001. To appear.
[32] R. Grossi and E. Lodi. Simple planar graph partition into three forests. Discrete
Applied Mathematics, 84:121—132, 1998.
[33] X. He, M.-Y. Kao, and H.-I. Lu. Linear-time succinct encodings of planar graphs
via canonical orderings. SIAM Journal on Discrete Mathematics, 12(3):317—325,
1999.
[34] IEEE. Proceedings of the 38th Annual Symposium on Foundations of Computer
Science, 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 30th
Annual Symposium on Foundations of Computer Science, pages 549—554, Research
Triangle 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. Discrete
Applied 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 theoretically
optimal number of bits. In Proceedings of the 13th Annual ACMSIAM
Symposium on Discrete Algorithms, pages 223—224, San Francisco, 6—8
Jan. 2002.
[41] J. I. Munro. Tables. In Proceedings of the 16th Conference on Foundations of
Software Technology and Theoretical Computer Science, Lecture Notes in Computer
Science 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 on
Foundations of Computer Science [34], pages 118—126.
[43] J. I. Munro, V. Raman, and A. Storm. Representing dynamic binary trees
succinctly. In ACM/SIAM [1], pages 529—536.
[44] M. Naor. Succinct representation of general unlabeled graphs. Discrete Applied
Mathematics, 28:303—307, 1990.
[45] R. Pagh. Low redundancy in static dictionaries with constant query time. SIAM
Journal on Computing, 31(2):353—363, 2001.
[46] D. Peleg. Distributed Computing: A Locality-Sensitive Approach. Monographs
on Discrete Mathematics and Applications. SIAM, 2000.
[47] D. Peleg and E. Upfal. A trade-o® between space and efficiency for routing
tables. 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 First
Annual ACM-SIAM Symposium on Discrete Algorithms, pages 138—148, 1990.
[50] M. Thorup. Undirected single source shortest paths in linear time. In Proceedings
of the 38th Annual Symposium on Foundations of Computer Science [34], pages
12—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.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top