多播路由算法和容错多播的研究
|
摘要
因特网上的多播通信的核心在于多播树的生成，这需要高效的多播树生成算法和协议，本文介绍了多种多播路由算法和路由协议，并对它们的优点与不足进行了比较分析。在本文中，探讨了平衡延迟和带宽消耗的算法，提出了改进的最短路径树算法(ASPT)。ASPT算法在路径长度增加程度可控的程度下最小化带宽消耗，模拟试验表明此算法能够在路径长度有限增加的情况下在很大程度上减少了带宽消耗。另外在RS算法基础上提出受限搜索RS(RSRS)算法，可以在很大程度上的减少建立多播树所花费的时间，同时保证生成的多播树最优。现在关于多播路由的研究大多着眼于多播树的生成，一旦多播树出现故障，就需要对故障点以下的所有多播接收节点进行重新路由甚至对整个多播树进行重新构造，这一方面降低了服务质量，另一方面有些多播应用不允许长时间的中断，对此本文提出了一种多播容错方案，采用在分枝节点之间建立备份路径的措施，可以在很大程度上减少额外的代价，能够在最快的时间内恢复多播树的故障，并使得恢复后的多播树形状基本上没有改变。
The core of multicast communication researches on the Internet is how to generate optimized multicast tree. Efficient multicast routing algorithms and protocols are needed. This dissertation introduced many kinds of routing algorithms and protocols, also with the algorithm performance analyses together. In this dissertation, algorithms for generating multicast trees with a trade-off in delay and bandwidth consumption are investigated. The Ameliorated Shortest Path Tree (ASPT) is proposed. The ASPT algorithm minimizes bandwidth consumption. Simulation experiment demonstrates that ASPT algorithm reduces bandwidth consumption greatly with path length increasing a little. In addition, The Restricted Search RS algorithm (RSRS) is proposed based on RS algorithm. It can reduce the time complexity of RS algorithm, at the same time, it guarantee the multicast tree is optimization. Nowadays most of researches on the multicast routing are how to generate multicast tree. In case of multicast tree failure, there need to
re-route all of nodes behind the failure point so much as re-build the whole tree, this will deteriorate Quality-of-Service, on the other hand, it is insufferable in some multicast applications. We proposed a Fault-Tolerant multicast scheme to resolve this problem. Our scheme creates backup paths crosswise in the ramose node. It can reduce additional cost greatly and recover the failure of multicast tree rapidly. At the same time, the multicast tree has tiny change.
The core of multicast communication researches on the Internet is how to generate optimized multicast tree. Efficient multicast routing algorithms and protocols are needed. This dissertation introduced many kinds of routing algorithms and protocols, also with the algorithm performance analyses together. In this dissertation, algorithms for generating multicast trees with a trade-off in delay and bandwidth consumption are investigated. The Ameliorated Shortest Path Tree (ASPT) is proposed. The ASPT algorithm minimizes bandwidth consumption. Simulation experiment demonstrates that ASPT algorithm reduces bandwidth consumption greatly with path length increasing a little. In addition, The Restricted Search RS algorithm (RSRS) is proposed based on RS algorithm. It can reduce the time complexity of RS algorithm, at the same time, it guarantee the multicast tree is optimization. Nowadays most of researches on the multicast routing are how to generate multicast tree. In case of multicast tree failure, there need to
re-route all of nodes behind the failure point so much as re-build the whole tree, this will deteriorate Quality-of-Service, on the other hand, it is insufferable in some multicast applications. We proposed a Fault-Tolerant multicast scheme to resolve this problem. Our scheme creates backup paths crosswise in the ramose node. It can reduce additional cost greatly and recover the failure of multicast tree rapidly. At the same time, the multicast tree has tiny change.
引文
[1] K. Bharah-Kumar and J. Jaffe, "Routing to Multiple Destinations in Computer Networks", IEEE Transactions on Communications, Vol.31, No.3, pp.343-351, March 1983.
[2] S. Cheng and K. Nahrstedt, "An Overview of Quality of Service Routing for Next-Generation High-Speed Networks: Problems and Solutions", IEEE Network Magazine, pp.64-79, Vol.5, No.2, December 1998.
[3] V. P. Kompella, J. C. Pasqual, G. C. Polyzos, "Multicast routing for multimedia communication", IEEE/ACM Trans. On Networking, Vol. 1 (3), pp.286-292, 1993.
[4] 赵印茹，“多播”，URL:http://www.btxx.cn.net/china-tc/200203/20020309.htm.
[5] B. Leiner, D. Nielson, and F. Tobagi, "Issues in Packet Radio Network Design", Proceedings of the IEEE, Vol.75, No.1, pp.6-20, January 1987.
[6] S. Deering and D. Cheriton, "Multicast Routing in Datagram Internetworks and Extended LANs", ACM Transactions on Computer Systems, Vol.8, No.2, pp.85-111, May 1990.
[7] H. Salama, D. Reeves, and Y. Viniotis, "Evaluation of Multicast Routing Algorithms for Real-Time Communication on High-Speed Networks", IEEE Journal on Selected Areas in Communications, Vo. 15, No.9, pp.332-356, April 1997.
[8] A. Banchs, C. Tschudin, W. Effelsberg, and V. Turau, "Multicasting Multimedia Streams with Active Networks", Proceedings of IEEE Conference on Local Computer Networks, pp.150-159, 1998.
[9] Q. Zhu, M. Parsa, J. J. Garcia-Luna-Aceves, "A source-based algorithm for delay-constrained minimum-cost multicasting." Proc IEEE INFOCOM'95, Boston, MA, pp.452-458, 1995.
[10] A. Legout, J. Nonnenmacher, and E. Biersack, "Bandwidth Allocation Policies for Unicast and Multicast Flows", Proceedings of IEEE INFOCOM, pp.254-261, 1999.
[11] L. Wei and D. Estrin, "The Tradeoffs of Multicast Trees and Algorithms", Proceedings of the Fourth International Conference on Computer Communications and Networks, pp.150-157, September 1995.
[12] B. Waxman, "Routing of Multipoint Connections", IEEE Journal of Selected Areas in Communications, Vol.6, No.9, pp. 1617-1622, December 1988.
[13] D. Farinacci et al., "Multicast Source Discovery Protocol (MSDP)", Internet Draft, February 2000.
[14] T. Cormen, C. Leiserson, and R. Rivest, "Introduction to Algorithms", The MIT Press, Massachusetts, 1989.
[15] The CIDR Report, URL:http://www. employees, org:80/～tdates/cidr-report, html.
[16] Internet Host and Traffic Growth, University of Columbia, URL:http://www. cs. columbia, edu/～hgs/internet/growth, html.
[17] D. Estrin, Y. Rekhter, and S. Hotz, "Scalable Inter-Domain Routing Architecture", Computer Communication Review, Vol.22, No.4, pp.322-330, 1992.
[18] P. Traina, "BGP-4 Protocol Analysis", RFC1774, March 1995.
[19] B. Cain, S. Deering, I. Kouvelas, B. Fenner, A. Thyagarajan, "Internet Group Management Protocol, Version 3", RFC3376, October 2002.
[20] J. Kruskal, "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem", Proceedings of the American Mathematical Society, Vol.7, pp.48-50, 1956.
[21] R. Prim, "Shortest Connection Networks and Some Generalizations", Bell System Technical Journal, Vol 36, No.4, pp. 1389-1401, 1957.
[22] Q. Zhu, M. Parsa, and J. Garcia-Luna-Aceves, "A Source-Based Algorithm for Delay-Constrained Minimum-Cost Multicasting", Proceedings of IEEE INFOCOM, pp.377-385, May 1995.
[23] E. Dijkstra, "A Note on Two Problems in Connection with Groups", Numeric Mathematics, Vol. 1, pp.269-271, 1959.
[24] R. Bellmann, Dynamic Programming, Princeton University Press, Princeton, 1957.
[25] J. Moy, "Multicast Extensions to OSPF", RFC-1584, March 1994.
[26] G. N. Rouskas, I. Baldine, "Multicast routing with end-to-end delay and delay variation constraints[J]", IEEE JSAC, Vol. 15(3), pp.346-356, 1997.
[27] S. Deering, "Distance Vector Multicast Routing Protocol", RFC 1075, November 1988.
[28] V.J.Rayward-Smith. "On finding Steiner Vertices". Networks. Vol. 16, pp. 283-294, 1986.
[29] M. Macedonia, D. Brutzman, "MBone Provides Audio and Video Across the Internet", IEEE Computer Magazine, pp.30-35, April, 1994.
[30] R. Karp, Reducibility among Combinatorial Problems, Plennum Press, New York, 1972.
[31] L. Kou, G. Markowsky, and L. Berman, "A Fast Algorithm for Steiner Trees", Acta
Inform-atica, Vol. 15, pp. 141-145, 1981.
[32]H. Takahashi and A. Matsuyama, "An Approximate Solution for the Steiner Problem in Graph", Mathematics Japonica, Vol.24, No.3, pp.573-577, 1980.
[33]P. Winter, "Steiner Problem in Networks: A Survey", Networks, Vol.17, No.2, pp. 129-167, December 1987.
[34]B. Waxman, "Performance Evaluation of Multipoint Routing Algorithms", Proceedings of IEEE INFOCOM, pp.980-986, 1993.
[35]K. Carlberg and J. Crowcroft, "Building Shared Trees Using a One-to-Many Joining Mechanism", Computer Communication Review, Vol.27, No. 1, pp.5-11, January 1997.
[36]Y. Dalai and R. Metcalf, "Reverse Path Forwarding of Broadcast Packets", Communications of the A CM, Vol.21, No. 12, pp. 1040-1048, December 1978.
[37]A. Ballardie, P. Francis, and J. Crowcroft, "Core Base Trees (CBT)", in Proc. ACM SIGCOMM'93, pp.85-95, September 1993.
[38]S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, and L. Wei, "The PIM architecture for wide-area multicast routing", IEEE/ACM Trans. Networking, Vol.4(2), pp.153-162, April 1996.
[39]S. Han and K. G.Shin. Fast restoration of real-time communication services from component failures in multi-hop networks. In Proc. ACM SIGCOMM'97, September 1997.
[40]R. Kawamura, K. Sato, and I. Tokizawa, "Self-healing ATM networks based on virtual path concept", IEEE J. Select. Areas in Commun., Vol.12(1), pp.120-127, January 1997.
[41]K. Murakami, H. S. Kim, "Optimal capacity and flow assignment for self-healing ATM networks base on line and end-to-end restoration", IEEE/ACM Trans. Networking, Vol.6 (2), pp.207-221, April 1998.
[42]T. Wu, "Fiber network survivability", New York, Artech House, 1992.
[43]C. Wu, W. Lee, Y. Hou and W. Chu. "A new preplanned self-healing scheme for multicast ATM network", Proc. IEEE ICCT'96, Vol.2, pp.888-891, May 1996.
[44]C. Wu, W. Lee, and Y. Hou, "Back-up VP preplanning strategies for survivable multicast ATM networks", Proc. IEEE ICC'97, Vol.1, pp.267-271, June1997.
[45]Y.Xiong and L.G. Mason. "Restoration strategies and spare capacity requirements in self-healing ATM networks", IEEE/ACM Trans. Networking, Vol.7 (1), pp. 98-110, February 1999.
[46]Aiguo Fei, "Multicast routing with QoS constrains ". PhD thesis, University of
California, pp. 117-132, 2001.
[47]Dong Xuan, "Routing support to enhance network services". PhD thesis, Texas A&M University, pp.90-127, December 2001.
[2] S. Cheng and K. Nahrstedt, "An Overview of Quality of Service Routing for Next-Generation High-Speed Networks: Problems and Solutions", IEEE Network Magazine, pp.64-79, Vol.5, No.2, December 1998.
[3] V. P. Kompella, J. C. Pasqual, G. C. Polyzos, "Multicast routing for multimedia communication", IEEE/ACM Trans. On Networking, Vol. 1 (3), pp.286-292, 1993.
[4] 赵印茹，“多播”，URL:http://www.btxx.cn.net/china-tc/200203/20020309.htm.
[5] B. Leiner, D. Nielson, and F. Tobagi, "Issues in Packet Radio Network Design", Proceedings of the IEEE, Vol.75, No.1, pp.6-20, January 1987.
[6] S. Deering and D. Cheriton, "Multicast Routing in Datagram Internetworks and Extended LANs", ACM Transactions on Computer Systems, Vol.8, No.2, pp.85-111, May 1990.
[7] H. Salama, D. Reeves, and Y. Viniotis, "Evaluation of Multicast Routing Algorithms for Real-Time Communication on High-Speed Networks", IEEE Journal on Selected Areas in Communications, Vo. 15, No.9, pp.332-356, April 1997.
[8] A. Banchs, C. Tschudin, W. Effelsberg, and V. Turau, "Multicasting Multimedia Streams with Active Networks", Proceedings of IEEE Conference on Local Computer Networks, pp.150-159, 1998.
[9] Q. Zhu, M. Parsa, J. J. Garcia-Luna-Aceves, "A source-based algorithm for delay-constrained minimum-cost multicasting." Proc IEEE INFOCOM'95, Boston, MA, pp.452-458, 1995.
[10] A. Legout, J. Nonnenmacher, and E. Biersack, "Bandwidth Allocation Policies for Unicast and Multicast Flows", Proceedings of IEEE INFOCOM, pp.254-261, 1999.
[11] L. Wei and D. Estrin, "The Tradeoffs of Multicast Trees and Algorithms", Proceedings of the Fourth International Conference on Computer Communications and Networks, pp.150-157, September 1995.
[12] B. Waxman, "Routing of Multipoint Connections", IEEE Journal of Selected Areas in Communications, Vol.6, No.9, pp. 1617-1622, December 1988.
[13] D. Farinacci et al., "Multicast Source Discovery Protocol (MSDP)", Internet Draft, February 2000.
[14] T. Cormen, C. Leiserson, and R. Rivest, "Introduction to Algorithms", The MIT Press, Massachusetts, 1989.
[15] The CIDR Report, URL:http://www. employees, org:80/～tdates/cidr-report, html.
[16] Internet Host and Traffic Growth, University of Columbia, URL:http://www. cs. columbia, edu/～hgs/internet/growth, html.
[17] D. Estrin, Y. Rekhter, and S. Hotz, "Scalable Inter-Domain Routing Architecture", Computer Communication Review, Vol.22, No.4, pp.322-330, 1992.
[18] P. Traina, "BGP-4 Protocol Analysis", RFC1774, March 1995.
[19] B. Cain, S. Deering, I. Kouvelas, B. Fenner, A. Thyagarajan, "Internet Group Management Protocol, Version 3", RFC3376, October 2002.
[20] J. Kruskal, "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem", Proceedings of the American Mathematical Society, Vol.7, pp.48-50, 1956.
[21] R. Prim, "Shortest Connection Networks and Some Generalizations", Bell System Technical Journal, Vol 36, No.4, pp. 1389-1401, 1957.
[22] Q. Zhu, M. Parsa, and J. Garcia-Luna-Aceves, "A Source-Based Algorithm for Delay-Constrained Minimum-Cost Multicasting", Proceedings of IEEE INFOCOM, pp.377-385, May 1995.
[23] E. Dijkstra, "A Note on Two Problems in Connection with Groups", Numeric Mathematics, Vol. 1, pp.269-271, 1959.
[24] R. Bellmann, Dynamic Programming, Princeton University Press, Princeton, 1957.
[25] J. Moy, "Multicast Extensions to OSPF", RFC-1584, March 1994.
[26] G. N. Rouskas, I. Baldine, "Multicast routing with end-to-end delay and delay variation constraints[J]", IEEE JSAC, Vol. 15(3), pp.346-356, 1997.
[27] S. Deering, "Distance Vector Multicast Routing Protocol", RFC 1075, November 1988.
[28] V.J.Rayward-Smith. "On finding Steiner Vertices". Networks. Vol. 16, pp. 283-294, 1986.
[29] M. Macedonia, D. Brutzman, "MBone Provides Audio and Video Across the Internet", IEEE Computer Magazine, pp.30-35, April, 1994.
[30] R. Karp, Reducibility among Combinatorial Problems, Plennum Press, New York, 1972.
[31] L. Kou, G. Markowsky, and L. Berman, "A Fast Algorithm for Steiner Trees", Acta
Inform-atica, Vol. 15, pp. 141-145, 1981.
[32]H. Takahashi and A. Matsuyama, "An Approximate Solution for the Steiner Problem in Graph", Mathematics Japonica, Vol.24, No.3, pp.573-577, 1980.
[33]P. Winter, "Steiner Problem in Networks: A Survey", Networks, Vol.17, No.2, pp. 129-167, December 1987.
[34]B. Waxman, "Performance Evaluation of Multipoint Routing Algorithms", Proceedings of IEEE INFOCOM, pp.980-986, 1993.
[35]K. Carlberg and J. Crowcroft, "Building Shared Trees Using a One-to-Many Joining Mechanism", Computer Communication Review, Vol.27, No. 1, pp.5-11, January 1997.
[36]Y. Dalai and R. Metcalf, "Reverse Path Forwarding of Broadcast Packets", Communications of the A CM, Vol.21, No. 12, pp. 1040-1048, December 1978.
[37]A. Ballardie, P. Francis, and J. Crowcroft, "Core Base Trees (CBT)", in Proc. ACM SIGCOMM'93, pp.85-95, September 1993.
[38]S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. Liu, and L. Wei, "The PIM architecture for wide-area multicast routing", IEEE/ACM Trans. Networking, Vol.4(2), pp.153-162, April 1996.
[39]S. Han and K. G.Shin. Fast restoration of real-time communication services from component failures in multi-hop networks. In Proc. ACM SIGCOMM'97, September 1997.
[40]R. Kawamura, K. Sato, and I. Tokizawa, "Self-healing ATM networks based on virtual path concept", IEEE J. Select. Areas in Commun., Vol.12(1), pp.120-127, January 1997.
[41]K. Murakami, H. S. Kim, "Optimal capacity and flow assignment for self-healing ATM networks base on line and end-to-end restoration", IEEE/ACM Trans. Networking, Vol.6 (2), pp.207-221, April 1998.
[42]T. Wu, "Fiber network survivability", New York, Artech House, 1992.
[43]C. Wu, W. Lee, Y. Hou and W. Chu. "A new preplanned self-healing scheme for multicast ATM network", Proc. IEEE ICCT'96, Vol.2, pp.888-891, May 1996.
[44]C. Wu, W. Lee, and Y. Hou, "Back-up VP preplanning strategies for survivable multicast ATM networks", Proc. IEEE ICC'97, Vol.1, pp.267-271, June1997.
[45]Y.Xiong and L.G. Mason. "Restoration strategies and spare capacity requirements in self-healing ATM networks", IEEE/ACM Trans. Networking, Vol.7 (1), pp. 98-110, February 1999.
[46]Aiguo Fei, "Multicast routing with QoS constrains ". PhD thesis, University of
California, pp. 117-132, 2001.
[47]Dong Xuan, "Routing support to enhance network services". PhD thesis, Texas A&M University, pp.90-127, December 2001.