臺灣博碩士論文加值系統

面對未來網路需求的不斷變化，相關QoS (服務品質)的群播網路問題也愈受許多研究者重視，在3G時代的來臨下，依目前網路設定現況並無法符合使用者需求，所以必須有一好的群播演算法以適合的方式來服務使用者。在本論文中提到了有以Native、Greedy、WGA、DDMA等方法建立動態群播路由，但是其效果並不彰顯，主要原因係因Native、Greedy、WGA等演算法中，只考慮了以路徑成本最小的單一因素，尚無加上其它QoS的限制。而在DDMA中，不僅考慮了路徑成本，還加上了時延這一限制，不過卻沒有加入移除節點和暫留時間(Duration)的觀念，以上這些方法在問題上的解決條件並不是很充份。故本論文提出了一個改良式的動態群播演算法稱為Dynamic Delay-constrained with K’s Fitness Multicasting Algorithm (DDKFMA)，它不僅可以改善上述的缺失，另外加上頻寬限制、延遲抖動、封包遺失等其它QoS因素，在選擇較適路徑上提出以乘性、減性、除性這三者方式用隨機性區間比例法來建構符合限制下的最適路徑。測試資料上使用統計中的卜瓦松機率分配決定節點出現個數及指數分配機率，以決定每一群播節點的停留時間，使其能具體地模擬網路上各節點的加入與移出情況，使得本演算法能真正的趨於完整，並可以說明其在動態環境上是有效地服務於群播使用者。

關鍵詞：動態群播、服務品質、通訊網路

With unceasing variant requirements about future network, QoS of the multicast routing problem attachs great importance to many researchers. Under 3G’s era will be approaching, it’s no longer come up to user’s requirements by current network settings. So it should use better multicast routing method to serve them by means of suitable ways. In other papers, they have introduced some methods to construct dynamic multicast routing, such as Naïve, Greedy, WGA, DDMA, but outcomes weren’t obvious that we expected. The first three algorithms consider only one factor of least cost and no other QoS parameters. On the other hand, DDMA adds both path cost and delay, but without considering node’s duration of add/remove requests. Hence, this thesis proposes a modified algorithm named Dynamic Delay-constrained with K’s Fitness Multicasting Algorithm (DDKFMA). In addition to revise the above-mentioned drawbacks, it also adds other QoS such as bandwidth, delay jitter, and packet loss. Besides, DDKFMA presents a hybrid method to discover find_fit_path that applies a random interval proportion to construct path and conform to constraints. In test data, the request sequences use statistic Poisson distribution to decide how many nodes appear in unit time and every node produces its duration time by Exponential distribution. Using these settings in our experiments can concretely simulate network’s node add/remove and prove our algorithm can efficiently implement in dynamic environment.

Keyword：Dynamic multicast routing, QoS, communication network

目錄
摘要 I
Abstract II
誌謝 III
目錄 IV
圖表索引 VI
第1章 緒論 1
1.1 研究背景與動機 1
1.2 研究流程 3
1.3 流程描述 4
1.4 論文架構 5
1.5 研究範圍與限制 6
第2章 文獻探討 7
2.1 路由定義 7
2.1.1 路由播送 8
2.1.2 路徑建構 9
2.2 群播路由型態 10
2.2.1 靜態群播路由 11
2.2.2 動態群播路由 13
2.3 群播問題基本定義 14
2.4 動態群播路由演算法 15
2.4.1 Naïve Algorithm 16
2.4.2 Greedy Algorithm 17
2.4.3 WGA (Weighted Greedy Algorithm) 18
2.4.4 Dynamic Delay-constrained Multicasting Algorithm 21
2.5 QoS (Quality of Service) 26
第3章 研究方法 30
3.1 節點標記 31
3.2 前k條路徑 33
3.3 選擇較適路徑的方法 36
3.4 節點加入與移除節點 42
3.5 DDKFMA演算法 43
3.6 DDKFMA範例說明 47
第4章 實驗模擬 52
4.1 測試資料與相關參數設定 52
4.2 實驗模擬結果 58
4.2.1 群播節點要求成功率比較 59
4.2.2 不同來源節點在不同網路圖下最低延遲成功比較 61
4.2.3 群播成功平均跳點數比較 75
4.2.4 群播點平均延遲成本比較 79
4.2.5 演算法執行時間成本比較 82
第5章 結論 87
5.1 綜合結論分析 87
5.2 本論文的貢獻 90
5.3 未來研究方向 90
參考文獻 92

參考文獻
[1] Ballardie, A., “Core Based Trees (CBT) Multicast Routing Architecture,” RFC2201, September 1997.
[2] Biersack, E., and Nonnenmacher, J., “WAVE: A New Multicast Routing Algorithm for Static and Dynamic Multicast Groups,” in proceedings of 5th Workshop on Network and Operation System Support for Digital Audio and Video, pp. 228-239, 1995.
[3] Chakraborty, D., Pronavalai, C., Chakraborty, G., and Shiratori, N., “An Efficient Routing to Minimize the Cost for Dynamic Multicasting,” Asia-Pacific Conf. on Circuit and Systems, November 1998.
[4] Chakraborty, D., Pronavalai, C., Chakraborty, G., and Shiratori, N., “Optimal Routing for Dynamic Multipoint Connection,” Special Issue on Architectures, Protocols and Quality of Service for the Internet of the Future ETT, vol. 10, no. 2, pp. 183-190, March/April 1999.
[5] Chakraborty, D., Pronavalai, C., Chakraborty, G., and Shiratori, N., “A Dynamic Multicast Routing Satisfying Multiple QoS Constraints,” International Journal of Network Management, vol. 13, no. 5, pp. 321-335, Sept. 2003.
[6] Chin, K. W., and Kumar, M., “AMTree: an active approach to multicasting in mobile networks,” Mobile Networks and Applications, vol. 6, no. 4, pp. 361-376, Aug. 2001.
[7] Cho, J., and Breen, J., “Analysis of the Performance of Dynamic Multicast Routing Algorithms,” Technical Report, School of Computer Science and Software Engineering, 1998.
[8] Cidon, I., Rom, R., and Shavitt, Y., “Multi-Path Routing Combined with Resource Reservation,” IEEE INFOCOM’97, pp. 92-100, April 1997.
[9] Doar, M., and Leslie, I., “How bad is naive multicast routing,” in Proceedings of IEEE INFOCOM ’93, vol. 1, pp. 82-89, 1993.
[10] Estrin, D., Farinacci, D., Helmy, A., Thaler, D., Deering, S., Handley, M., Jacobson, V., Liu, C., Sharma, P., and Wei, L., “Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification,” RFC 2117, June 1997.
[11] Fei, Z., “A new consistency algorithm for dynamic documents in content distribution networks,” Journal of Parallel and Distributed Computing, vol. 63, no. 10, pp. 916-926, October 2003.
[12] Feng, G., and Yum, T. S., “Efficient Multicast Routing with Delay Constraints,” International Journal of Communication Systems, vol. 12, pp. 181-195, 1999.
[13] Fujinoki, H., and Christensen, K., “The new shortest best path tree (SBPT) Algorithm for dynamic multicast tree,” IEEE Computer Society, Proc. of the 24th IEEE Int’l Conf. on Local Computer Networks, Los Alamitos, IEEE Press, pp. 204-211, 1999.
[14] Goshi, J., and Ladner, R. E., “Algorithms for dynamic multicast key distribution trees,” Proceedings of the twenty-second annual symposium on Principles of distributed computing, pp. 243-251, Boston, Massachusetts, July 13-16, 2003.
[15] Guo, L., and Matta, I., “QDMR: An Efficient QoS Dependent Multicast Routing Algorithm,” Technical Report NU-CCS-98-05, College of Computer Science, North-eastern University, August 1998.
[16] Kadirire, J., and Knight, G., “Comparison of dynamic multicast routing Algorithms for wide-area packet switched (asynchronous transfer mode) networks,” in Proceedings of IEEE INFOCOM ’95, vol. 1, pp. 212-219, 1995.
[17] Koha, S. J., Yi, J. H., Hahm, J. H., Chin, B. M., and Park, C. H., “Minimizing Cost and Delay in Shared Multicast Trees,” ETRI Journal, vol. 22, Number 1, March 2000.
[18] Korkmaz, T., and Krunz, M., “Multi-constrained optimal path selection,” in INFOCOM 2001, vol. 2, pp. 834-843, 2001.
[19] Low, C. P., and Lee, Y. J., “Distributed multicast routing, with end-to-end delay and delay variation constraints,” Computer Communications, vol. 24, no. 9, pp. 848-862, 2000.
[20] Lu, H. M., Xiang, Y., Shi, M. L., and Yang, M., “A QoS-based dynamic multicast routing algorithm for streaming layered data,” Journal of Software, vol. 15, no. 6, pp. 928-939, 2004.
[21] Moh, W. M., and Nguyen, B., “An optimal QoS-guaranteed multicast routing algorithm with dynamic membership support,” in: Proceedings of IEEE International Conference on Communications, ICC’99, Vancouver, Canada, pp. 727-732, June 1999.
[22] Mokbel, M.F., El-Haweet, W.A., El-Derini, M.N., “A delay-constrained shortest path algorithm for multicast routing in multimedia applications,” In: Proc. of the IEEE Middle East Workshop on Networking, 1999.
[23] Oliveira, Carlos A. S., and Pardalos, Panos M., “A survey of combinatorial optimization problems in multicast routing,” Computers and Operations Research, vol. 32, no. 8, pp. 1953-1981, August 2005.
[24] Özkasap Öznur, “Performance study of a probabilistic multicast transport protocol,” Performance Evaluation, vol. 57, no. 2, pp. 177-198, June 2004.
[25] Park, S., and Park, D., “Adaptive core multicast routing protocol,” Wireless Networks, vol. 10, no. 1, pp. 53-60, January 2004.
[26] Parsa, M., Zhu, Q., and Garcia-Luna-Acevez, J. J., “An Iterative Algorithm for Delay-Constrained Minimum-Cost Multicasting,” IEEE/ACM Transactions on Networking, vol. 6, no. 4, pp. 461-473, August 1998.
[27] Pusateri, T., “Distance Vector Multicast Routing Protocol,” Internet-Draft, March 1998.
[28] Rouskas, George N., and Baldine Illia, “Multicast routing with end-to-end delay and delay variation constraints,” IEEE Journal on Selected Areas in Communications, vol. 15, no. 3, pp. 346-356, 1997.
[29] Sarkar, S., and Tassiulas, L., “Fair Bandwidth Allocation for Multicasting in Networks with Discrete Feasible Set,” IEEE Transactions on Computers, vol. 53, no. 7, pp. 785-797, July 2004.
[30] Tran, Hieu T., and Harris, Richard J., “QoS multicast routing with delay constraints,” in International Network Optimization Conference (INOC), Evry, France, 2003.
[31] Waitzman, D., Deering, S., and Partridge, C., “Distance Vecter Multicast Routing Protocol,” RFC 1075, Nov. 1988.
[32] Wang, B., and Hou, C. J., “A survey on multicast routing and its QoS extension: problems, Algorithms, and protocols,” IEEE Network, vol. 14, no. 1, pp. 22-36, January/February 2000.
[33] Wang, T. Y., Wuu, L. C., and Huang, S. T., “A Scalable Core Migration Protocol for Dynamic Multicast Tree,” Journal of Information Science and Engineering, vol. 19, no. 3, pp. 479-501, 2003.
[34] Wang, Z., Shi, B., and Zou, L., “A Delay-Constrained Least-Cost Multicast Routing Heuristicfor Dynamic Multicast Groups,” Electronic Commerce Research, vol. 2, no. 4, pp. 323-335, 2002.
[35] Waters, A. G., and Bishop, T. L. J., “Delay considerations in multicast routing for ATM networks,” Tenth UK Teletraffic Symposium Performance Engineering in Telecommunications Networks, pp. 12/1-6, 1993.
[36] Waxman, B. M., “Performance evaluation of multipoint routing Algorithms,” INFOCOM, vol. 3, pp. 980-986, Mar. 1993.
[37] Waxman, B. M., “Routing of multipoint connections,” IEEE Journal on Selected Areas in Communications, vol. 6, no. 9, pp.1617-1622, 1988.
[38] Wei, L., and Estrin, D., “A Comparison of Multicast Trees and Algorithms,” Computer Science Department, University of Southern California, USA, Technical Report USCCS-93-560, September 1993.
[39] Zhao, W., Ammar, M., and Zegura, E., “Multicasting in delay tolerant networks: semantic models and routing algorithms,” Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, pp. 268-275, Philadelphia, Pennsylvania, USA, August 26-26, 2005.
[40] Zhu, Q., Parsa, M., and Garcia-Luna-Aceves, J. J., “A source-based Algorithm for delay constrained minimum-cost multicasting,” in Proceedings of IEEE INFOCOM ’95, vol. 1, pp. 337-385, 1995.