臺灣博碩士論文加值系統

群播路由 (Multicast Routing)的技術，可以支援網路上的即時通訊及多媒體服務，並透過傳送一份多媒體資料到所有群組成員的方式來更有效的使用網路資源。因此，為了要支援新的應用程式與服務，經常需要網路提供品質服務的保證。在本論文中，我們提出一個以Dijkstra`s演算法延伸的新的演算法來解決大型網路中具有多重服務品質限制的多媒體群播路由問題，其中包含最小頻寬需求、最大延遲、延遲變化率與遺失率之限制。為了要建立一個有效率機制以處理存在有多重路徑時，可以選擇出一個較好路徑，故在本論文中我們亦提出一個結合各個QoS參數成本的新的成本函數。在模擬實驗結果上，與一些已被提出的演算法比較後發現，本論文所提出DHQMRA (Degree-Heuristic QoS Multicast Routing Algorithm)演算法比上述之演算法的確有著較佳的搜尋解能力。

Multicast routing supports real-time communication and multimedia services over Internet and allows to use network resources more efficiently by sending only a single copy of multimedia data to all group members. In order to support those new applications and services often require quality of service (QoS) guarantees from the network. For solving multiple QoS constrains of multicast routing problem in large scale networks, this thesis proposes a new algorithm called DHQMRA (Degree-Heuristic QoS Multicast Routing Algorithm) using extened Dijkstra’s algorithm and considering multiple QoS metrics, such as bandwidth, delay, delay jitter and packet loss. Moreover，to have an efficient mechanism to select the good path in case of multiple paths, this thesis presents a new cost function which is a combination of partially cost related to each QoS parameter. Comparing with some existing well-known approaches, it is observed that DHQMRA have better ability in solving multicast routing problem with QoS support .

摘要 I
Abstract II
誌謝 III
目錄 IV
圖目錄 VI
表目錄 VII
1. 緒論 1
1.1 研究動機與目的 1
1.2 研究流程與架構 3
1.3 論文架構 5
1.4 研究限制 6
2. 文獻探討 7
2.1 群播路由技術 7
2.1.1 封包傳遞模式 8
2.1.2 群播路由資訊管理 11
2.1.3 群播路由資訊使用的範圍 12
2.1.4 群播路由選擇方式 13
2.1.5 群播群組型態的定義 14
2.1.6 網路服務品質實現的基本型態 15
2.2 群播路由問題 16
2.2.1 群播路由問題描述 19
2.2.2 具有QoS群播路由問題描述 20
2.3 群播路由演算法 22
2.3.1 貪婪演算法 22
2.3.2 NMA演算法 24
2.3.3 BCMA演算法 27
2.3.4 BSMA演算法 30
3. 研究方法 32
3.1 DHMRA (Degree-Heuristic Multicast Routing Algorithm) 34
3.1.1 DHMRA演算法流程示意圖 37
3.1.2 DHMRA演算法 38
3.1.3 DHMRA演算法例子說明 39
3.1.4 DHMRA時間複雜度 41
3.2 MDHMRA (Modified DHMRA)演算法設計 42
3.2.1 MDHMRA演算法 43
3.2.2 MDHMRA演算法例子說明 44
3.3 DHQMRA(Degree-Heuristic QoS Multicast Routing Algorithm) 46
3.3.1 變數定義 47
3.3.2 DHQMRA演算法流程示意圖 52
3.3.3 DHQMRA演算法 53
3.3.4 MDHMRA演算法例子說明 55
4. 實驗設計與結果分析 60
4.1 模擬實驗之軟硬體設施 61
4.2 MST (Minimal Spanning Tree)實驗模擬資料說明 62
4.2.1 DHMR於MST (Minimal Spanning Tree)實驗結果分析 65
4.2.2 MDHMRA於MST (Minimal Spanning Tree)實驗結果分析 67
4.2.3 DHMRA、MDHMRA於模擬大型網路之實驗結果分析 70
4.3 QoS (Quality of Service)實驗模擬資料說明 72
4.3.1 解決DCLC問題之實驗一 76
4.3.2 解決DCLC問題之實驗二 79
4.3.3 解決DCLC問題之實驗三 82
4.3.4 解決Multi-Constrained QoS問題之實驗一 85
4.3.5 解決Multi-Constrained QoS問題之實驗二 88
5. 結論與未來展望 91
5.1 結論 91
5.2 未來研究方向 93
參考文獻 94

[1]王彰人，具有服務品質需求之高效率的群播路由演算法設計，國立屏東科技大學資訊管理研究所，2005。

[2]蔡正發，劉姿吟，莊順斌， "一個有效率的分支修剪多重路由群播演算法"，第十五屆物件導向技術及應用研討會，2004。

[3]蔡正發，莊順斌，楊澤，"多媒體網路中一個新的有效率之多重群播繞送演算法之設計"，第五屆電子化企業經營管理理論暨實務研討會，CD-ROM Paper no. 343，民國93年。

[4]Alpert, C.J., Hu, T.C., Huang, J.H., and Kahng, A.B., "A Direct Combination of the Prim and Dijkstra Constructions for Improved Performance-Driven Global Routing, "Proceeding of the IEEE International Symposium on Circuits and Systems, pp. 1869-1872, 1993.

[5]Calvert, K.L., Zegura, E.W., and Donahoo, M.J., "Core selection methods for multicast routing,", Proceedings of Fourth International Conference on Computer Communications and Networks, pp.20-23, Sept. 1995

[6]Chu C.H., Gu J.H., and Hou X. D., "A heuristic ant algorithm for solving QoS multicast routing problem," In Proc. of 2002 Congress on Evolutionary Computation, pp. 1630–1635, 2002.

[7]Dijkstra, E.W., "A Note on Two Problems on Connection with Graphs, "Numerische Mathematik, vol. 1, pp. 395-412, 1959.

[8]Hwang, F.K., Richards, D.S., and Winter, P., "The Steiner Tree Problem," Annals of Discrete Mathematics, vol. 53, pp. 203-282, 1992.

[9]Hwang, R.H., Do., W.Y., and Yang, S.C., "Multicast Routing Based on Genetic Algorithms," Journal of Information Science and Engineering, vol. 16, no. 5, pp. 885-901, 2000.

[10]Jia, X., Cao, J., and Jia, W., "Real-Time Multicast Routing with Optimal Network Cost," Proceedings of the 3th. International Workshop on Real- Time Computing Systems Application, IEEE Computer Society Press, pp. 49-56, 1996.

[11]MNIF Kais, RONG Bo and KADOCH Michel, "Adaptative algorithm for supporting multi-constrained QoS for real-time and multimedia applications," Control, Communications and Signal Processing, 2004.

[12] Charikar, M., Naor, J., and Schieber, B., "Resource optimization in QoS multicast routing of real-time multimedia," IEEE/ACM Transactions on Networking, vol. 12, pp. 340–348, April 2004.

[13]Sheikh, W.A., Bashandy, A.R., and Ghafoor, A., "A combined approach for QoS based multicast routing and resource allocation," International Communications Conference, vol. 1, pp. 136-142, 2005.

[14] Chen Shigang and Nahrstedt Klara, "Distributed QoS Routing with Imprecise State Information," Proceedings of 7th IEEE International Conference on Computer, Communications and Networks, pp. 614-621, October 1998.

[15] Tsai, C.W., Tsai, C.F., and Chen, C.P., "A Novel Algorithm for multimedia Multicast Routing in a Large scale network," The Journal of Systems and Software, vol. 72, pp. 431-441, 2004.

[16]Tsai, C.W., Tsai, C.F., and Chen, C.P., "A Novel Multiple-Searching Genetic Algorithm for Multimedia Multicast Routing," Proceeding of the 2002 IEEE Congress on Evolutionary Computation, pp. 506-511, 2002.

[17] Tsai, C.F., Tsai, C.W., and Wu, H.C., "A Novel Multimedia Multicast Routing Approach For The Internet," Proceedings of the 2001 IEEE International Conference on Multimedia and EXPO, pp. 589-592, 2001.

[18]Wang Bin and Hou Jennifer C., "Multicast Routing and its QoS Extension: Problems, Algorithms and Protocols," IEEE Network, pp. 22-36, January/February 2000

[19] Waxman, B.M., "Routing of Multipoint Connections," IEEE Journal on Selected Areas in Communication, vol. 6, no. 9, pp. 1617-1622, 1988.

[20]Wang Zheng and Crowcroft Jon, "Quality-of-Service Routing for Supporting Multimedia Applications," IEEE Journal on Selected Areas in Communication, vol. 14, no. 7, pp. 1228-1234, 1996

[21] Zhu Qing, Parsa M., and Garcia-Luna-Aceves J.J., "A source-based algorithm for delay-constrained minimum-cost multicasting," Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies, vol. 1, p. 377, 1995.