請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33864完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 李德財(Der-Tsai Lee) | |
| dc.contributor.author | Tzu-Lun Huang | en |
| dc.contributor.author | 黃子倫 | zh_TW |
| dc.date.accessioned | 2021-06-13T05:47:43Z | - |
| dc.date.available | 2006-07-12 | |
| dc.date.copyright | 2006-07-12 | |
| dc.date.issued | 2006 | |
| dc.date.submitted | 2006-07-10 | |
| dc.identifier.citation | [1] R. Bellman, “Dynamic Programming”, Princeton University Press, 1957.
[2] K. Bharath-Kumar and J. M. Jaffe, “Routing to Multiple Destinations in Computer Networks,” IEEE Transactions on Communications, Vol. Com-31, No. 3, March, 1983, pp. 343-351. [3] J. Chen, S.-H. G. Chan, and O. K. Li, “Multipath Routing for Video Delivery Over Bandwidth-Limited Networks,” IEEE Journal on Selected Areas in Communications, Vol. 22, No. 10, December 2004, pp. 1920-1932. [4] S. Chen and Y. Shavitt, “A Scalable Distributed QoS Multicast Routing Protocol,” Proceedings of IEEE International Conference on Communications, June 2004, pp.1161-1165. [5] S. Chen, K. Nahrstedt, and Y. Shavitt, “A QoS-Aware Multicast Routing Protocol,” IEEE Journal on Selected Areas in Communications, Vol. 18, No. 12, December 2000, pp.2580-2592. [6] C. Chen, R. Riley, S. Kumar, and J. Garcia-Luna-Aceves, “A loop-free extended Bellman-Ford routing protocol without bouncing effect,” ACM Computer Communication Review, Vol. 19, No. 4, September 1989, pp. 224-236. [7] T. H. Cormen, C. E. Leiserson and R. L. Rivest, “Introduction to algorithms,” The MIT Press, 1990. [8] Y. H. Chu, S. G. Rao, S. Seshan, and H. Zhang, “A Case for End System Multicast, IEEE Journal on Selected Areas in Communications,” Vol. 20, No. 8, October 2002, pp. 1456-1471. [9] S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, and L. Wei, “The PIM architecture for wide-area multicast routing,” IEEE/ACM Transactions on Networking, Vol. 4, No.2 April 1996, pp. 153-162. [10] M. Faloutsos, A. Banerjea, and R. PanKaj, “QoSMIC: Quality of Service sensitive Multicast Internet protocol”, Proceedings of ACM SIGCOMM, September 1998, pp. 144-153. [11] A. Fei, M. Gerla, “Receiver-Initiated Multicasting with Multiple QoS Constraints”, Proceedings of IEEE INFOCOM, Vol. 1, March 2000, pp. 62-70. [12] J. Ford and D. R. Fulkerson, “Flows in Networks, Princeton,” Princeton University Press, NJ, 1962. [13] M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” Freeman, San Francisco, CA 1979. [14] J. Garcia-Luna-Aceves, “Loop-Free Routing Using Diffusing Computations,” IEEE/ACM Transactions on Networking, Vol. 1, No. 1, February 1993, pp. 130-141. [15] C. Hedrick, “Routing Information Protocol”, RFC 1058, Rutgers University, June, 1988. [16] T.-L. Huang and D. T. Lee, “A Distributed Multicast Routing Algorithm for Real-Time Applications in Wide Area Networks,” Proceedings of IEEE International Symposium on Parallel Architectures, Algorithms, and Networks (ISPAN), May 2002, pp. 295-300. [17] T.-L. Huang and D. T. Lee, “Comments and Improvement on ‘A Distributed Algorithm of Delay-Bounded Multicast Routing for Multimedia Applications in Wide Area Networks’,” IEEE/ACM Transactions on Networking, Vol. 13, No. 6, December 2005, pp. 1410-1411. [18] T.-L. Huang and D. T. Lee, “A Distributed Multicast Routing Algorithm for Real-Time Applications in Wide Area Networks,” accepted for publication in Networks. [19] T.-L. Huang and D. T. Lee, “An Iterative Distributed Multicast Routing Algorithm for Multi-Constraint Multicast Routing,” accepted for publication in Computer Communications. [20] C. Huitema, “Routing in the Internet,” Prentice Hall, 1995. [21] Y. Im, Y. Lee, S. Wi, and Y. Choi, “Delay constrained distributed multicast routing algorithm,” Computer Communications, Vol. 20, Issue 1, January, 1997, pp. 60-66. [22] X. Jia, C.H. Lee, K. Makki, and N. Pissinou, “Efficient multicast tree algorithm in ATM networks,” Computer Communications, Vol. 19, Issue 8, July 1996, pp. 637-644. [23] X. Jia, N. Pissinou and K. Makki, “A real-time multicast routing algorithm for multimedia applications,” Computer Communications, Vol. 20, Issue 20, January 1997, pp. 1098-1106. [24] X. Jia, “A Distributed Algorithm of Delay-Bounded Multicast Routing for Multimedia Applications in Wide Area Networks,” IEEE/ACM Transactions on Networking, Vol. 6, No. 6, December 1998, pp. 828-837. [25] X. Jia, Y. Zhang, N. Pissinou, K. Makki, “A distributed multicast routing protocol for real-time multicast applications,” Computer Networks, Vol. 31, Issue 12, January 1999, pp. 101-110 [26] T. Korkmaz and M. Krunz, “A Randomized algorithm for finding a path subject to multiple QoS requirements,” Computer Networks, Vol. 36, 2001, pp. 251-268. [27] V. P. Kompella, J. C. Pasquale, and G. C. Polyzos, “Two distributed algorithms for the constrained Steiner tree problem”, Proceedings of 2nd International Conference on Computer Communications and Networks, 1993, pp. 343-349. [28] V. P. Kompella, J. C. Pasquale, and G. C. Polyzos, “Multicast Routing for Multimedia Communication,” IEEE/ACM Transactions on Networking, Vol. 1, No. 3, June 1993, pp. 286-292. [29] C. P. Low, “On Finding Feasible Solutions for the Delay Constrained Group Multicast Routing Problem,” IEEE Transactions on Computers, Vol. 51, No. 5, May 2002, pp. 581-588. [30] K.-S. Lui, K. Nahrstedt, and S. Chen, “Routing with Topology Aggregation in Delay-Bandwidth Sensitive Networks,” IEEE/ACM Transactions on Networking, Vol. 12, No. 1, February 2004, pp. 17-29. [31] P. V. Mieghem and F. A. Kuipers, “Concepts of Exact QoS Routing Algorithms,” IEEE/ACM Transactions on Networking, Vol. 12, No. 5, October 2004, pp. 851-864. [32] J. Moy, “Multicast Routing Extensions for OSPF”, Communications of the ACM, Vol. 37, No. 8, August 1994, pp. 61-67,. [33] M. Parsa, Q. Zhu, and J. J. Garcia-Luna-Aceves, “An Iterative Algorithm for Delay-Constrained Minimum-Cost Multicasting,” IEEE/ACM Transactions on. Networking, Vol. 6, No. 4, August 1998, pp. 461-474. [34] D. S. Reeves and H. F. Salama, “A Distributed Algorithm for Delay-Constrained Unicast Routing,” IEEE/ACM Transactions on. Networking, Vol. 8, No. 2, April 2000, pp. 239-250. [35] J. Rugelj and S. Klavzar, “Distributed Multicast Routing in Point-To-Point Networks,” Computers & Operations Research, Vol. 24, Issue. 6, June 1997, pp. 512-527. [36] H. F. Salama, “Multicast Routing for Real-time Communication on High-Speed Networks,” Ph.D. thesis, Department of Electrical and Computer Engineering, North Carolina State University, 1996. [37] H. F. Salama, D. S. Reeves, and Y. Viniotis, “Evaluation of multicast routing algorithms for real-time communication on high speed networks,” IEEE Journal on Selected Areas in Communications, Vol. 15, No.3, April 1997, pp. 332-345,. [38] Q. Sun and H. Langendoerfer, “Efficient Multicast Routing for Delay-Sensitive Applications,” Proceedings of 2nd International Workshop on Protocols for Multimedia Systems, 1995, pp. 452-458. [39] Q. Sun and H. Langendorfer, “A new Distributed Routing Algorithm for Supporting Delay-Sensitive Unicast Routing,” Computer Communications, Vol. 21, Issue 5, May 1998, pp. 572-578. [40] Q. Sun and H. Langendorfer, “A distributed delay-constrained dynamic multicast routing algorithm,” Telecommunication Systems, Vol. 11, January 1999, pp. 47-58. [41] H. Ural and K. Zhu, “An Efficient Distributed QoS-based Multicast Routing Algorithm,” Proceedings of IEEE 21st International Conference on Performance, Computing, and Communications, 2002, pp. 27-36. [42] H. Ural and K. Zhu, “Distributed Delay Constrained Multicast Routing Algorithm with Efficient Fault Recovery,” Networks, Vol. 47, Issue 1, January 2006, pp. 37-51. [43] H. Takahashi and A. Matsuyama, “An approximation solution for the Steiner problem in graphs,” Mathematica Japonica, Vol. 24, No. 6, 1980, pp. 573-577. [44] B. M. Waxman, “Routing of multipoint connection,” IEEE Journal on Selected Areas in Communications, Vol. 6, No. 9, December 1988, pp. 1617-1622. [45] Z. Wang and J. Crowcroft, “Quality-of-Service Routing for Supporting Multimedia Applications,” IEEE Journal on Selected Areas in Communications”, Vol. 14, No. 7, September 1996, pp.1228-1234. [46] D. Waitzmann, C. Partridge, and S. Deering, “Distance vector multicast routing protocol,” RFC 1075, November 1988. [47] D. H. Wolpert and W. G. Macready, “No Free Lunch Theorems for Optimization,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, April 1997, pp. 67-82. [48] S. Yan, M. Faloutsos, and A.Banerjea, “QoS-Aware Multicast Routing for the Internet: The Design and Evaluation of QoSMIC”, IEEE/ACM Transactions on. Networking, Vol. 10, No. 1, February 2002, pp.54-66. [49] X. Yuan, “Heuristic Algorithms for Multiconstrained Quality-of-Service Routing”, IEEE/ACM Transactions on Networking, Vol. 10, No. 2, April 2002, pp. 244-256. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33864 | - |
| dc.description.abstract | 自從1990年左右開始, 專家們便開始討論如何在廣域網路或是網際網路上提供具有服務品質保證的路由. 這個問題到目前為止一直都是一個很重要且尚未解決的研究議題. 在博士論文內, 我們將提出以經驗為主的分散式演算法去對付多條件限制群播路由的問題. 議題將分成兩個部分討論, 雙條件限制路由與多條件限制路由. 在雙條件限制路由的部分, 我們首先針對現有相關文獻的做法做探討並列出這些做法的優缺點. 接著, 我們提出兩個反例去證明賈 教授在論文[24]內演算法上所發生的兩個嚴重的錯誤與我們所提出相對的解決的方法(演算法). 我們所提出的演算法不僅能夠提供正確的解答之外, 而且在假設上我們還延伸了賈 教授在論文內的限制, 亦即在我們的論文內delay與cost這兩個參數彼此是相互獨立的. 此外, 我們也提供了有效率的演算法讓網路內的節點能夠動態的加入或離開現有的群播連線. 同時, 我們也提供了容錯的機制以避免因為某個或是某些節點發生錯誤而造成其它節點在服務品質上的影響.
在多條件限制路由的議題上, 我們是以雙條件限制路由的做法為基礎並做延伸. 我們先對所要解決的問題做正確的數學定義, 然後提出相對的分散式演算法去求解多條件限制路由的問題. 我們把演算法的過程與結果與三篇知名的論文做比較並對比較結果做詳細的解釋與說明. 不管是雙條件限制或是多條件限制路由, 我們所提出的演算法的表現均優於同等級的被比較論文. 是否存在更有效率與表現更好的演算法, 值得我們做更近一步的研究與探討. | zh_TW |
| dc.description.abstract | How to provide an efficient quality of service (QoS) routing in wide area networks (WAN) or in Internet has been an important research issue since about 1990. In the dissertation, we propose efficient heuristic-based distributed algorithms for addressing the problem of multicast routing with multiple QoS constraints. Two types of multicast routing problem are considered, bi-criteria routing and multi-criteria routing. In bi-criteria routing, we first review some existing algorithms, and point out errors in the well-known algorithm due to Jia [24] by two counter examples. We then propose an algorithm that improves Jia’s algorithm. A fix to Jia’s algorithm is given, and a generalization of his algorithm, including relaxation of routing constraints, allowing for dynamic updating of multicast group, and consideration of fault-tolerance and recovery in the routing network. In multi-criteria routing, we extend our result, based on our new algorithm of bi-criteria routing, to consider a generalized model of the QoS routing. We point out an inherent distinction between these two problems in terms of solution complexities. For both algorithms, we have made a computational analysis and given correctness proofs. To compare with many well-known algorithms/protocols, we perform simulations. Our simulation results indicate that our proposed algorithms have a better performance than existing ones. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T05:47:43Z (GMT). No. of bitstreams: 1 ntu-95-D88526002-1.pdf: 767954 bytes, checksum: 023c0fb76717726bd8db932a7087648b (MD5) Previous issue date: 2006 | en |
| dc.description.tableofcontents | 1. Introduction 10
2. Bi-Criteria Routing 14 2.1 Problem Definition 14 2.2 Related Work 15 2.3 Counterexamples to Jia’s and Prior Works 18 2.4 Routing Information and Assumptions 22 2.4.1 Routing Information 22 2.4.2 Assumptions 25 2.5 Our Algorithm 25 2.5.1 Heuristic Function of the Distributed Algorithm 25 2.5.2 Basic Idea of the Distributed Algorithm 28 2.5.2.1 Construction of the MRT 28 2.5.2.1.1 Tree Construction 28 2.5.2.1.2 Cycle Processing 30 2.5.2.1.3 Tree Pruning 31 2.5.2.2 Dynamic Join and Leave of Multicast Memberships 32 2.5.2.3 Fault Recovery of the MRT 35 2.5.3 The Distributed Algorithm 37 2.6 Analysis, Correctness Proof, and Comparison 46 2.6.1 Analysis of the Algorithm 46 2.6.2 Correctness of the Algorithm 51 2.6.3 Complexity Comparison with other related Algorithms 56 2.7 Simulations 57 2.7.1 Simulation Environment 57 2.7.2 Performance Evaluation 59 2.7.2.1 Comparison with Jia’s Algorithm 59 2.7.2.2 Comparison with other Algorithms 62 2.7.2.3 The frequency of cycle occurrences 66 3. Multi-Criteria Routing 68 3.1 Problem Definition 68 3.2 Related Work 72 3.3 Our Iterative Distributed Algorithm 77 3.3.1 Architecture and Assumptions 77 3.3.2 Algorithm Description 79 3.3.2.1 Basic Idea 79 3.3.2.2 An Example of the Algorithm 84 3.3.2.3 The Iterative Distributed Algorithm 94 3.3.3 Dynamic Join/Leave of the MRT 100 3.4 Analysis and Comparison 102 3.4.1 Analysis 102 3.4.2 Comparison 104 3.5 Simulation 109 3.5.1 Simulation Environment 109 3.5.2 Simulation Result 110 4. Conclusion 116 References 118 Publication 125 | |
| dc.language.iso | en | |
| dc.subject | 分散式演算法 | zh_TW |
| dc.subject | 多條件限制路由 | zh_TW |
| dc.subject | 群播路由 | zh_TW |
| dc.subject | 多條件限制 | zh_TW |
| dc.subject | QoS 路由演算法 | zh_TW |
| dc.subject | QoS 路由協定 | zh_TW |
| dc.subject | 容錯 | zh_TW |
| dc.subject | heuristics | en |
| dc.subject | multicast routing | en |
| dc.subject | distributed algorithm | en |
| dc.subject | constrained Steiner tree | en |
| dc.subject | multi-constrained routing | en |
| dc.subject | multiple constraints | en |
| dc.subject | QoS routing algorithm | en |
| dc.subject | QoS routing protocol | en |
| dc.subject | fault tolerant | en |
| dc.subject | NP-completeness | en |
| dc.title | 分散式QoS群播路由演算法的設計與分析 | zh_TW |
| dc.title | Design and Analysis of Distributed QoS Multicast Routing Algorithms | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 94-2 | |
| dc.description.degree | 博士 | |
| dc.contributor.oralexamcommittee | 高成炎(Cheng-Yan Kao),趙坤茂(Kun-Mao Chao Professor),陳省隆(Hsing-Lung Chen),高明達(Ming-Tat Ko),項天瑞(Tien-Ruey Hsiang) | |
| dc.subject.keyword | 群播路由,分散式演算法,多條件限制路由,多條件限制,QoS 路由演算法,QoS 路由協定,容錯, | zh_TW |
| dc.subject.keyword | multicast routing,distributed algorithm,constrained Steiner tree,multi-constrained routing,multiple constraints,QoS routing algorithm,QoS routing protocol,fault tolerant,NP-completeness,heuristics, | en |
| dc.relation.page | 126 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2006-07-11 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-95-1.pdf 未授權公開取用 | 749.96 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。