臺灣博碩士論文加值系統

本研究探討同時考量總成本最小化和滿足延遲服務品質要求的群播樹建構問題。其次，本研究探討群播網路中單一鏈路損壞的情形下，同時考量總成本最小化和滿足延遲服務品質要求的備援路徑規劃問題。第三，我們探討相關於路徑問題的頻寬議題。所謂成本最小化意指有效的使用頻寬資源，因此，我們討論有關於如何適當地估計訊務頻寬需求的頻寬配置問題。同時，我們也討論了有關多個要求服務品質的群播通訊應用同時發生，而需要妥善配置的問題。本研究應用塔布搜尋(Tabu Search, TS)的方法，發展出解決考量服務品質需求的群播路徑問題的演算法。根據路徑復原機制，我們也發展了塔布搜尋演算法來決定出近似最佳且符合延遲限制之備援路徑。而根據鏈路、子樹、樹狀的復原架構，藉由定義延遲標籤來評估每條路徑的延遲服務品質需求，進而發展出四個啟發式演算法來決定出在不同的復原架構下具有最小的總成本且符合延遲限制之備援路徑。另外，我們提出了頻寬配置程序模式來配置適當的頻寬給訊務，以有效的利用有限的頻寬資源。而當多個要求群播通訊應用同時發生時，我們建立了關於多個要求服務品質的群播通訊應用間配置的數學模式，並且建議了可運用於發展有效的演算法中的可能求解程序和關鍵重點。

At first, we study the multicast routing problem considering both cost minimization and fulfillment of QoS requirements in terms of the end-to-end delay. Secondly, for the scenario of a single link failure, we investigate the backup paths planning problem also considering both cost minimization and delay fulfillment. Thirdly, we discuss the bandwidth issues related to the routing problems. The bandwidth allocation about estimating the bandwidth requirement of the traffic is discussed. Furthermore, when multiple multicast sessions occur simultaneously, the problems of constructing a set of multicast trees are also discussed.
Tabu Search (TS) approach is applied to solve both the QoS-based multicast routing and QoS-based backup path planning problems. According to the path restoration scheme, a TS algorithm is proposed to determine the optimal or near optimal delay-constrained backup paths. Based on the link, subtree, and tree restoration schemes, four delay label heuristic algorithms are proposed to minimize the total cost of all the backup paths with the satisfaction in end-to-end delay constraint for all the cases of a single link failure.
Additionally, the bandwidth allocation process model is proposed to allocate the adequate amount of bandwidth to the traffic. When multiple multicast sessions occur simultaneously, the mathematical model is formulated for the delay-constrained multicast tree packing problem. The possible solution procedures and key issues are suggested in the development of the efficient algorithm.

中文摘要 I
ABSTRACT II
誌謝辭 III
LIST OF TABLES VI
LIST OF FIGURES VII
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Research Objective 4
1.3 Limitations and Assumptions 6
1.4 Framework of Dissertation 6
Chapter 2 Literature Review 8
2.1 Multicast Routing 8
2.1.1 Multicast Routing Problems 8
2.1.2 Multicast Routing Algorithms 11
2.2 Restoration Schemes and Algorithms 16
2.2.1 Restoration Schemes 16
2.2.2 Restoration Algorithms 19
Chapter 3 A Tabu Search Algorithm for QoS-based Multicast Routing 21
3.1 Problem Formulation 22
3.2 The Proposed Tabu Search Algorithm 23
3.2.1 Initial Solution 25
3.2.2 Neighborhood Solutions and Move 26
3.2.3 Tabu List and Aspiration Criterion 27
3.2.4 Diversification and Intensification 28
3.2.5 Termination Rule 29
3.2.6 Tabu Search Algorithm 29
3.2.7 The Illustrated Example 30
3.2.8 Time Complexity Analysis 33
3.3 Computational Experiments 34
3.4 Summary 38
Chapter 4 A Tabu Search Algorithm for QoS-based Backup Path Planning 41
4.1 Problem Formulation 42
4.2 The Proposed Tabu Search Algorithm 44
4.2.1 Initial Solution 44
4.2.2 Neighborhood Solution and Move 46
4.2.3 Tabu List and Aspiration Criterion 47
4.2.4 Diversification and Intensification 48
4.2.5 Termination Rule 50
4.2.6 Tabu Search Algorithm 50
4.2.7 The Illustrated Example 51
4.2.8 Time Complexity Analysis 54
4.3 Computational and Experimental Results 55
4.4 Summary 59
Chapter 5 A Delay Label Heuristic Algorithm for QoS-based Backup Path Planning 62
5.1 Problem Definition 62
5.2 The Proposed Algorithms 64
5.2.1 Delay Labels 66
5.2.2 Algorithm for Tree-based Restoration Scheme 66
5.2.3 Algorithm for Subtree-based Restoration Scheme 69
5.2.4 Algorithm for Link-based Restoration Scheme 70
5.2.5 The Illustrated Example 70
5.2.6 Time Complexity Analysis 74
5.3 Computational and Experimental Results 74
5.4 Summary 78
Chapter 6 Discussion on the Bandwidth Issues related to the Routing Problem 79
6.1 Importance of Bandwidth 79
6.2 Bandwidth Allocation 79
6.2.1 Traffic Model 80
6.2.2 Bandwidth Estimation 81
6.2.3 Bandwidth Allocation Process 82
6.3 Discussion on Multiple QoS-based Multicast Routing 84
6.3.1 Problem Formulation 84
6.3.2 Solution Procedures 86
Chapter 7 Conclusion and Future Research 90
7.1 Conclusion 90
7.2 Future Research 92
References 94

[1] Anderson, J, Doshi, B. T., Dravida, S, and Harsha-Vardhana, P. “Fast restoration of ATM networks,” IEEE Journal on Selected Areas in Communications, 12(1), 128-138 (1994).
[2] Anderson, C. A., Fraughnaugh, K., Parker, M., and Ryan, J., “Path assignment for call routing: an application of tabu search,” Annals of Operations Research, 41, 301-312 (1993).
[3] Asaka, T., Miyoshi, T., and Tanaka, Y., “Dynamic multicast algorithm using predetermined path search,” IEICE Transactions on Communications, E83-B(5), 1128-1134 (2000).
[4] Asaka, T., Miyoshi, T., and Tanaka, Y., “Label algorithm for delay-constrained dynamic multicast routing,” IEICE Transactions on Communications, E84-B(1), 55-62 (2001).
[5] Azuma, M., Fujii, Y., Sato, Y., Chujo, T., and Murakami, K., “Network restoration algorithm for multimedia communication services and its performance characteristics,” IEIEC Transaction on Communications, E78-B, 987-993 (1995).
[6] Bauer, E. and Verma, A., “Degree-constrained multicasting in point-to-point networks,” IEEE INFOCOM’95, 369-376 (1995).
[7] Bertsekas, D. and Gallagher, R., Data Networks, Prentice Hall (1992).
[8] Beran, J., Sherman, R., Taqqu, M.S., and Willinger, W., “Long-range Dependence in Variable-bit-rate Video Traffic,” IEEE Transactions on Communications, 43, 1566-1579 (1995).
[9] Bettahar, H. and Bouabdallah, A., “A new approach for delay-constrained routing,” Computer Communications, 25(18), 1751-1764 (2002).
[10] Chakrabarti, A. and Manimaran, G., “A case for tree migration and integrated tree maintenance in QoS multicasting,” Computer Communications, 26(9), 1007-1017 (2003).
[11] Chakraborty, D. and Chakraborty, G., “A distributed routing method for dynamic multicasting,” Telecommunication Systems, 25(3,4), 299-315(2004).
[12] Chen, Y. L. and Chin, Y. H., “The Quickest Path Problem,” Computers and Operations Research, 17(2), 153-161 (1990).
[13] Chen, S., Gunluk, O., and Yener, B., “The multicast packing problem,” IEEE/ACM Transaction on Networking, 8(3), 311-318 (2000).
[14] Cormen, T. H., Leiserson, C. E., and Rivest, R. L., Introduction to Algorithms, MIT Press (1997).
[15] Deering, S and Cheriton D., “Multicast routing in datagram internetworks and extended LANs,” ACM Transactions on Computer Systems, 8(2), 85-111(1990).
[16] Doar, M. and Leslie, I., “How bad is naïve multicast routing,” Proceedings of IEEE INFOCOM’93, 82-89 (1993).
[17] Esbensen, H., “Computing near-optimal solutions to the Steiner problem in a graph using a genetic algorithm,” Network, 26, 173-185 (1995).
[18] Feng, G. and Siew, C. K., “Restorable VP-layout design in ATM networks for efficient support for multicast traffic,” IEE Proceedings-Communications, 148(5), 290-300 (2001).
[19] Fujii, H. and Yoshikai, N., “Restoration message transfer mechanism and restoration characteristics of double-search self-healing ATM networks,” IEEE Journal on Selected Areas in Communications, 12(1), 149-158 (1994).
[20] Fujinoki, H. and Christensen, K. J., “A routing algorithm for dynamic multicast trees with end-to-end path length control,” Computer Communications, 23, 101-114 (2000).
[21] Gallager, R., Humblet, P., and Spira, P., “A distributed algorithm for minimum-weight spanning trees,” ACM Transactions on Programming Language and System, 66-77(1983).
[22] Glover, F., “Future paths for integer programming and linkage to artificial intelligence,” Computers and Operations Research, 13, 533-549 (1986).
[23] Glover, F., “Tabu search - Part I,” ORSA Journal on Computing, 1, 190-206 (1989).
[24] Glover, F., “Tabu search - Part II,” ORSA Journal on Computing, 2:4-32 (1990).
[25] Guerin, R., Ahmadi, H., and Naghshineh, M., “Equivalent Capacity and Its Application to Bandwidth Allocation in High-speed Networks,” IEEE Journal on Selected Areas in Communications, 9, 968-981 (1994).
[26] Haghighat, A. T., Faez, K., Dehghan, M., Mowlaei, A., and Ghahreman, Y., “GA-based heuristic algorithms for bandwidth-delay-constrained least-cost multicast routing,” Computer Communications, 27(1), 111-127 (2004).
[27] Hong, S., Lee, H., and Park, B. H., “An efficient multicast routing for multimedia applications,” IEEE INFOCOM’98, 1433-1440 (1998).
[28] Hwang, F. K, and Richard D. S., “Steiner tree problem,” Networks, 22, 55-89 (1992).
[29] Jia, X., “A distributed algorithm of delay-bounded multicast routing for multimedia applications in wide area networks,” IEEE/ACM Transactions on Networking, 6(6), 828-387 (1993).
[30] Jia, X. and Wang, L., “A group multicast routing algorithm by using multiple minimum Steiner trees,” Computer Communications, 20(9), 750-758 (1997).
[31] Jiang, X., “Routing broadband multicast streams,” Computer Communications, 15(1), 45-51 (1992).
[32] Kapsalis, A., Rayward-Smith, V. J., and Smith, G.. D., “Solving the graphical Steiner tree problem using genetic algorithms,” Journal of the Operational Research Society, 44(4), 397-406 (1993).
[33] Katanyutaveetip, D., “Real-time optimal multicast routing,” Computer Communication, 25(18), 1297-1304 (2002).
[34] Kawamura, R., Sato, K., and Tokizawa, I., “Self-healing ATM networks based on virtual path concept,” IEEE Journal on Selected Areas in Communications, 12(1), 120-127 (1994).
[35] Kompella, V. P., Pasquale, J. C., and Polyzos, G. C., “Multicast routing for multimedia communication,” IEEE/ACM Transactions on Networking, 1(3), 286-292 (1993).
[36] Kosiur, D., IP Multicasting: The complete guide to interactive corporate networks, Willy computer publishing, New York (1998).
[37] Kou, L., Markowsky, G., and Berman, L., “A fast algorithm for Steiner trees,” Acta Informatica, 15, 141-145 (1981).
[38] Kuipers, F. and Mieghem, P. V., “MAMCRA: a constrained-based multicast routing algorithm,” Computer Communications, 25(20), 802-811 (2002).
[39] Kwong, S., Lam, D. W. F., Tang, K. S., and Man, K. F., “Optimization of spare capacity in self-healing multicast ATM network using genetic algorithm,” IEEE Transactions on Industrial Electronics, 47(6), 1334–1343 (2000).
[40] Laguna, M. and Glover, F., “Bandwidth packing: a tabu search approach,” Management Science, 39(4), 492-500 (1993).
[41] Leland, W.E., Taqqu, M.S., Willinger, W., and Wilson, D.V., “On the Self-similar Nature of Ethernet Traffic (Extended version),” IEEE/ACM Transactions on Networking, 2, 1-15 (1994).
[42] Lee, C. Y. and Cho, H. K., “Multiple multicast tree allocation in IP network,” Computer and Operations Research, 31(7), 1115-1133 (2004).
[43] Lee, H., Chung, J., and Chung, S. J., “A state-dependent preplanned ATM VP restoration scheme,” IEEE INFOCOM’98, 1766-1771 (1998).
[44] Lee, K., “IEEE 1451: A standard in support of smart transducer networking,” Proceedings of the 17th IEEE Instrumentation and Measurement Technology Conference, IMTC 2000, 2, 525-528 (2000).
[45] Leung, Y., Li, G., and Xu, Z. B., “A genetic algorithm for the multiple destination routing problems,” IEEE Transactions on Evolutionary Computation, 2(4), 150-161 (1998).
[46] Li, L and Li, C., “QoS-based routing algorithms for ATM network,” Computer Communication, 24, 416-421(2001).
[47] Liaw, C. F., “An efficient tabu search approach for the two-machine preemptive open shop scheduling problem,” Computers and Operations Research, 30(14), 2081-2095 (2003).
[48] Lin, H. and Lai, S., “VTDM-A dynamic multicast routing algorithm,” Proceedings of IEEE INFOCOM’98, 1426-1432 (1998).
[49] Low, C. P. and Song, X., “On finding feasible solutions for the delay constrained group multicast routing problem,” IEEE Transactions on Computers, 51(5), 581-588 (2002).
[50] Low, C. P. and Wang, N., “An efficient algorithm for group multicast routing with bandwidth reservation,” Computer Communications, 23(18), 1740-1746 (1997).
[51] Low, C. P, Wang, N., and Ng, J. M., “Dynamic group multicast routing with bandwidth reservations,” International Journal of Communication Systems, 15, 665-682 (2002).
[52] Miller, C. K., Multicast Networking and Application, Addison-Wesley Longman (1999).
[53] Murakami, K. and Kim, H. S., “Virtual path routing for survivable ATM network,” IEEE/ACM Transaction on Networking, 4(1), 22-39 (1996).
[54] Ng, J. and Ng, P, “Cost-delay path selection function for real-time multicast routing,” Proceedings of the IEEE International Symposium on Modeling Analysis and Simulation of Computer and Telecommunication Systems, 56-61 (1998).
[55] Noronha, C. and Tobag, F., “Optimum routing of multicast streams,” IEEE INFOCOM’94, 865-873 (1994).
[56] Norros, I., “On the Use of Fractional Brownian Motion in the Theory of Connectionless Networks,” IEEE Journal on Selected Areas in Communications, 13, 953-962 (1995).
[57] Novak, R., Rugelj, J., and Kandus, G., “A note on distributed multicast routing in point-to-point networks,” Computers and Operations Research, 28(12), 1149-1164 (2001).
[58] Oliveira, C. A. S. and Pardalos P. M., "A survey of combinatorial optimization problems in multicast routing", Computers and Operations Research, 32(8), 1953-1982 (2005).
[59] Prased, A.R., Stavrov, B., and Schoute, F.C., “Generation and Testing of Self-similar Traffic in ATM Networks,” IEEE ICPWC’96, 200-205 (1996).
[60] Paul, S., Multicasting on the internet and its applications, Kluwer academic publishers, (1998).
[61] Raghavan, S. and Manimaran, G., “A re-arrangeable algorithm for the construction of delay-constrained dynamic multicast trees,” IEEE/ACM Transactions on Networking, 7(4), 514-529 (1999).
[62] Roohy, L. E., Abdou, E., Hopkins, J., and Wagner, M. A., “A procedure for designing a low connected survivable fiber network,” IEEE Journal on Selected Areas in Communications, 4(7), 1112-1117 (1986).
[63] Rouskas, G.N. and Baldine, I., “Multicast Routing with end-to-end delay and delay variation constraints,” IEEE Journal on Selected Areas in Communications, 15(3), 346-356 (1997).
[64] Sahasrabuddhe, L. H. and Mukherjee, B., “Multicast routing algorithms and protocols: a tutorial,” IEEE Network, 4(1), 90-102 (2000).
[65] Salama, H. F., Reeves, D. S., and Viniotis, Y., “Evaluation of multicast routing algorithms for real-time communication on high speed networks,” IEEE Journal on Selected Areas in Communications, 15(3), 332-346 (1997).
[66] Sarkar, S. and Tassiulas L., “Fair bandwidth allocation for multicast in networks with discrete feasible set,” IEEE Transactions on Computers, 53(7), 785-797 (2004).
[67] Sheu, P. R. and Chen, S. T., “A fast and efficient heuristic algorithm for the delay- and delay variation-bounded multicast tree problem,” Computer Communications, 25(8), 825-833 (2002).
[68] Shi, J. and Dong, T. L., “The application of genetic algorithm in multicast routing,” Acta Electronica Sinica, 28(5), 88-99 (2000).
[69] Shyur, C. C., Lu, T. C., and Wen, U. P., “Applying tabu search to spare capacity planning for network restoration,” Computers and Operations Research, 26(12), 175-194 (1999).
[70] Shyur, C. C. and Wen, U. P., “Optimizing the system of virtual path by tabu search,” European Journal of Operational Research, 129, 650-662 (2001).
[71] Skorin-Kapov, N. and Kos, M., “The application of Steiner trees to delay constrained multicast routing: a tabu search approach,” Proceedings of the 7th International Conference on Telecommunications, 443-448 (2003).
[72] Sun, Q. and Langendoerfer H., “Efficient multicast routing for delay-sensitive applications,” Proceedings of the Second Workshop on Protocols for Multimedia Systems, 452-458 (1995).
[73] Sveda, M. and Vrba, R., “Integrated smart sensor networking framework for sensor-based appliances,” IEEE Sensor Journal, 3(5), 579-586 (2003).
[74] Takahashi, H. and Matsuyama, A., “An approximate solution for the Steiner problem in graphs,” Mathematica Japonica, 6, 573-577 (1980).
[75] Tawfig, A. and Taieb, Z., “Delay-constrained, low-cost multicast routing in multimedia networks,” Journal of Parallel and Distributed Computing, 61, 1307-36 (2001).
[76] Tsai, C. F, Tsai, C. W., and Chen, C. P., “A novel algorithm for multimedia multicast routing in a large-scale network,” The Journal of Systems and Software, 72, 431-441 (2004).
[77] Wang, B. and Hou, J. C., “Multicast routing and its QoS extension: problems, algorithms, and protocols,” IEEE Network, 14(1), 22-36 (2000).
[78] Wang, C. F., Lai, B. R., and Jan, R. H., “Optimum multicast of multimedia streams,” Computer and Operations Research, 26(5), 461-480 (1999).
[79] Wang, C. F., Liang, C. T., and Jan, R. H., “Heuristic algorithms for packing of multiple-group multicasting,” Computer and Operations Research, 29(7), 905-924 (2002).
[80] Wang, H., Wang, J., Wang H., and Sun, Y. M., “TSDLMRA: an efficient multicast routing algorithm based on tabu search,” Journal of Network and Computer Applications, 27(2), 77–90 (2004).
[81] Wang, X. H., and Wang, G. X., “A multicast routing approach with delay-constrained minimum-cost based genetic algorithm,” Journal of China Institute of Communication, 23(3), 112-117 (2002).
[82] Wang, Y. F. and Chang, R. F., “Self-healing on ATM multicast tree,” IEIEC Transactions on Communications, E81-B(8), 1590-1598 (1998).
[83] Wang, Y. F. and Huang, J. F., “Preplanned restoration and optimal capacity placement on ATM multicast tree,” IEIEC Transactions on Communications, E83-B(2), 281-292 (2000).
[84] Wang, Z., “On the complexity of quality of service routing,” Information Processing Letter, 69, 111-114 (1999).
[85] Wang, Z., Shi, B., and Zhao, E., “Bandwidth-delay-constrained least-cost multicast routing based on heuristic genetic algorithm,” Computer Communications, 24(7-8), 685-692 (2001).
[86] Wang, Z. and Crowcroft, J., “Quality-of Service routing for supporting multimedia applications,” IEEE Journal on Selected Areas in Communications, 14(7), 1228-34 (1996).
[87] Waxman, B. M., “Routing of multipoint connections,” IEEE Journal on Selected Areas in Communications, 6(9), 128-138 (1988).
[88] Winter, P., “Steiner problem in networks: a survey,” Networks, 17, 129-167 (1987).
[89] Wu, C. S. and Lee, S. W., “Backup VP planning for multicast connections in ATM networks,” Computer Communications, 22(10), 898-906 (1999).
[90] Wu, C. S., Lee, S. W., and Hou, Y. T., “Backup VP preplanning strategies for survivable multicast ATM networks,” Proceedings of IEEE ICC’97, 267-271 (1997).
[91] Wu, J. J., Hwang, R. H., and Lu, H. I., “Multicast routing with multiple QoS constraints in ATM networks,” Information Science, 124, 29-57 (2000).
[92] Xiong, Y. and Mason, L., “Restoration strategies and spare capacity requirements in self-healing ATM networks,” IEEE/ACM Transactions on Networking, 7, 98-110 (1999).
[93] Yang, C. B., Hung, C. W., and Wen, U. P., “Bandwidth allocation for broad transport network,” International Journal of Operations Research, 1(1), 1-10 (2004).
[94] Yang, W. L., “A tabu-search based algorithm for the multicast-streams distribution problem,” Computer Networks, 39(6), 729-747 (2000).
[95] Yang, W. L., “Optimal and heuristic algorithms for quality-of–service routing with multiple constraints”, Performance Evaluation, 57, 261-278 (2004).
[96] Yang, W. L., “A heuristic algorithm for the multi-constrained multicast tree,” Lecture Notes in Computer Science, 2839, 78–89(2003).
[97] Youssef, H., Al-Mulhem, A., Sait, S. M., and Tahir, M. A., “QoS-driven multicast tree generation using tabu search,” Computer Communications, 25(11-12), 1140-1149 (2002).
[98] Zhu, Q., Parsa, M., and Garcia-Luna-Aceves, J., “A sourced-based algorithm for delay-constrained minimum-cost multicasting,” Proceedings of IEEE INFOCOM’95, 377-385 (1995).