摘要
随着当前Internet的发展和各种多媒体应用的出现，组播技术得到大量应用。组播指将同一信息从源结点传送到网络中多个结点（不一定是网络中所有结点）。实现组播的一般方式是建立组播树, 组播树的优点在于：首先，信息以并行方式沿着树枝发送到不同的组播终点，从而降低了信息传递的时延；其次，信息的复制只在树的分支处进行，因此网络中需要传送的复制信息量最少，能够节约网络带宽资源，降低网络负载，减少拥塞。因此组播成为目前研究最多、应用最广的网络信息传输方式。组播路由算法主要用来建立一棵性能良好的组播树，并使它能够满足各种业务的服务质量需求。
本文首先对网络路由选择技术，包括单播路由、组播路由和基于遗传算法的组播路由选择技术进行了分析总结，指出简单性、通用性、外延性、层次型路由和不精确状态信息下的路由是未来服务质量组播路由的研究重点。
然后分析了组播和组播路由选择技术的原理，组播路由算法通常采用启发式技术，要么太复杂难以求解，要么太费时不能实际应用，而遗传算法简单高效，非常适用于组播路由选择。随后介绍了遗传算法的基本思想和运行过程以及遗传算法的数学基础，并对遗传算法的基本要素设计技术和改进策略进行了分析总结。
在此基础上，将多种群并行技术和退火技术相结合，以克服现有基于遗传算法的组播路由算法过早收敛和后期搜索速度较慢的缺陷，且使用树状编码方法，提出求解带宽、时延、时延抖动和分组丢失率约束的代价最小组播树的多种群并行退火遗传组播路由算法。从理论和实验上验证了算法的正确性，并分析了算法的最坏时间复杂度和空间复杂度，其最坏时间复杂度为(max(e+n㏒+k ,n2))，最坏空间复杂度为( kn2)，它们均为多项式解，表明算法也是有效的。
With the development of Internet and the advent of various multimedia applications, multicasting technology is widely applied. Multicast routing constructs paths along with data packets from a source are distributed to reach many, but not all, destinations in a communication network. Tree construction is a commonly used approach in solving the multicast routing problem. One advantage of multicast tree is that data are distributed to different multicasting destinations along the branches in parallel, which reduces the delay. The other is that message need only be replicated at forking nodes, which minimizes the data replication, spares the network bandwidth, reduces the network load and lessens the congestion. Thus multicasting is mostly researched and utilized at present. Multicast routing algorithms are used to compute multicast trees that satisfy quality of service requirement.
Firstly, this paper analyses and summarizes the routing technology, including unicast routing, multicast routing and multicast routing based on genetic algorithm, presents the research of quality of service multicast routing will be focused on simplicity, generality, extensibility, hierarchical routing and routing with imprecise state information.
Then, the paper analyses the principle of multicast and multicast routing technology. Commonly multicast routing algorithms use heuristic technology, either too complex to solve problems, or too time-consuming to be applied, and genetic algorithm is simple and effective, suitable for multicast routing. Subsequently the paper introduces the basic idea, the process and the mathematical fundament of genetic algorithm, analyses and summarizes the basic element design technology and the improvement methods of genetic algorithm.
On the above, to overcome the pre-maturity and low speed of search in the late phase of multicast routing algorithm based on genetic algorithm, the author gives the multi-population parallel annealing genetic multicast routing algorithm to solve the bandwidth, delay, delay jitter and packet loss constrained least-cost multicast routing problem, which combines the
multi-population parallel technology and annealing technology, adopts tree-like coding approach. In addition, the author verifies the correction of the algorithm theoretically and experimentally, and analyzes the time complexity and the space complexity, points out the worst time complexity is (max(e+n㏒+k ,n2)) and the worst space complexity is (kn2), which are polynomial solutions and indicate the algorithm is effective.
引文
[1] 谢希仁. 计算机网络. 第2版. 北京：电子工业出版社，2000.
[2] 陈国良，王煦法，庄镇泉，王东生. 遗传算法及其应用. 北京：人民邮电出版社，1996.
[3] 肖征荣，崔丙锋，高国飞，张冰. IP组播技术综述. 通讯技术与设备，2001，27(8)：25-27
[4] Z. Wang , J. Crowcroft. QoS Routing for Supporting Resource Reservation. IEEE Journal on Selected Areas in Communications, September 1996：1228-1234
[5] R.A.Guerin, A.Orda. Networks with advance reservations: The routing perspective. In: Sidi, M. ed. Precedings of the IEEE INFOCOM'00. Israel: IEEE Communication Society, 2000. 118-127
[6] J.Bennett, H.Zhang. Hierarchical packet fair queueing algorithms. ACM Computer Communication Review, 1996, 26(4): 143-156
[7] Q.Ma, P.Steenkiste. Quality-of-service routing with performance guarantees. In: Campbell, A. T., Nahrstedt, K. eds. Precedings of the 4th International IFIP Workshop on Quality of Service. New York: IFIP WG6.1, 1997.1-12
[8] A.Orda. Routing with end-to-end QoS guarantees in broadband networks. IEEE/ACM Transactions on Networking, 1999, 7(3): 365-374
[9] C.Pornavalai, G.Chakraborty, N.Shiratori. QoS based routing algorithm in integrated services packet networks, Journal of High Speed Networks, 1998, 7(2): 99-112
[10] D.Clark, J.Pasquale, D.Estrin, et al. Strategic directions in networks and telecommunications, ACM Computing Surveys, 1996,28(4): 679-690
[11] I.Cidon, R.Rom, Y.Shavitt. Multi-path routing combined with resource reservation. In: Hasegawa, T. Pickholtz, R. eds.Precedings of the IEEE INFOCOM'97. Kobe, Japan: IEEE Communication Society, 1997.92-100
[12] K. G.Shin, C. C.Chou. A distributed route-selection scheme for establishing real-time channel. In Puigjaner, R. ed. Precedings of IFIP Sixth International Conference on High Performance Networking (HPN'95). Palma, Spain: Chapman & Hall, 1995. 319-329
[13] S.Chen, K.Nahrstedt. Distributed quality-of-service routing in high-speed networks based on selective probing. In: Nolley. E.Proceedings of the 23rd Annual Conference on Local Computer Networks(LCN'98). Boston, MA: IEEE Communication Society,1998. 80-89
[14] S.Chen, K.Nahrstedt. Distributed QoS routing with imprecise state information. In: Pressley, A. Proceedings of the 7th International Conference on Computer Communications and Networks (IC3N'98). Louisiana: IEEE Communication Society. 614-621
[15] S.Chen, K.Nahrstedt. On finding multi-constrained paths. In: Goldston, R. ed. Precedings of the
IEEE International Conference on Communications(ICC'98). Atlanta: IEEE Communication Society, 1998. 874-879
[16] H.F.Salama, D.S.Reeves, Y.Viniotis. A distributed algorithm for delay-constrained unicast routing. IEEE/ACM Transactions on Networking, 2000, 8(2): 239-250
[17] A.Shaikh, J.Rexford, K. G.Shin. Evaluating the impact of stale link state on quality-of-service routing. IEEE/ACM Transactions on Networking, 2001, 9(2): 162-176
[18] F.Ergun, R.Sinha, L.Zhang. QoS routing with performance-dependent costs, In: Sidi, M. ed. Precedings of the IEEE INFOCOM'00. Israel: IEEE Communication Society, 2000. 137-146
[19] H.Lorenz, A.Orda. Optimal partition of QoS requirements on uncicast paths and multicast trees. In: Doshi, B. ed. Precedings of the IEEE INFOCOM'99. New York: IEEE Communication Society, 1999. 246-253
[20] D.Raz, Y.Shavitt, D.Raz, et al. Optimal partition of QoS requirements with discrete cost functions, In: Sidi, M. ed. Precedings of the IEEE INFOCOM'00. Israel: IEEE Communication Society, 2000. 613 -622
[21] R. Gallager, P. Humblet, P. Spira. A Distributed Algorithm for Minimum-Weight spanning trees. ACM Trans. Programming Lang. and Sys.,Jan. 1983. 66-77
[22] N. Shacham. Multipoint Communication by Hierarchically Encoded Data. Proc. IEEE INFOCOM '92, May 1992. 2107-2114
[23] P. Winter. Steiner Problem in Networks: A Survey. Networks, 1987. 129-167
[24] F. K. Hwang. Steiner Tree Problems Networks, 1992. 55-89
[25] L. Kou, G. Markowsky, L. Berman. A Fast Algorithm for Steiner Trees. Acta Informatica, 1981. 141-145
[26] H. Takahashi, A. Matsuyama. An Approximate Solution for the Steiner Problem in Graphs. Math. Japonica, 1980. 573-577
[27] F. Bauer, A. Varma. Distributed Algorithms for Multicast Path Setup in Data Networks. Comp. Eng. Dept., UC Santa Cruz, UCSC-CRL-95-10, Aug. 1995.
[28] Q. Zhu, M. Parsa, J. Garcia-Luna-Aceves. A Source-Based Algorithm for Delay-Constrained Minimal-Cost Multicasting. Proc. IEEE INFOCOM '95, 1995. 377-384
[29] V. P. Kompella, J. C. Pasquale, G. C. Polyzo. Multicast Routing for Multimedia Communication. IEEE/ACM Trans. Net., 1993. 286-292
[30] B. K. Haberman, G. Rouskas. Cost, Delay, and Delay Variation Conscious Multicast Routing. Tech. rep. TR-97-03, NC State Univ., 1997.
[31] V. P. Kompella, J. C. Pasquale, G. C. Polyzo. Two Distributed Algorithms for Multicasting Multimedia Information. Proc. ICCCN '93, 1993. 343-349
[32] R .Widyono. The Design and Evaluation of Routing Algorithms for Real-Time Channels. Technical rep.,ICSI TR-94-024,Univ.CA of Berkeley Int'l. Comp.Sci.Inst.,June 1994
[33] Wang Chia-Jiu, Weissler N. Paul. The use of artificial neural networks for optimal message routing. IEEE Networks, 1995,9(2):16-24
[34] P. Chotipat, C.Goutam, S.Norio. Neural network approach to multicast routing in real-time communication networks. In: IEEE Proceedings of the 1995 International Conference on Network Protocols, Los Anamitos, CA,1995:332-339
[35] http://www.ietf.org/proceedings/99mar/I-D/draft-ietf-mospf-mospf-01.txt
[36] http://www.ietf.org/proceedings/00dec/I-D/draft-ietf-idmr-dvmrp-v3-10.txt
[37] http://www.ietf.org/proceedings/02jul/I-D/draft-ietf-pim-dm-new-v2-01.txt
[38] H.W.Holbrook, D.R.Cheriton. IP Multicast Channels: EXPRESS Support for Large-Scale Single-Source Applications. ACM SIGCOMM′99,1999.
[39] http://www.ietf.org/internet-drafts/draft-ietf-pim-sm-v2-new-07.txt
[40] http://www.ietf.org/proceedings/98dec/I-D/draft-ietf-idmr-cbt-spec-v3-01.txt
[41] http://www.ietf.org/mail-archive/ietf-announce/Current/msg02610.html
[42] Ren-Hung Hwang, Wei-Yuan Do, Shyi-Chang Yang. Multicast Routing Based on Genetic Algorithms. Joural of Information Science and Engineering, 2000(16):885-901
[43] 石坚，邹玲，董天临，赵尔墩. 遗传算法在组播路由选择中的应用. 电子学报，2000，28(5)：88-89
[44] Chun-Wei Tsai, Cheng-Fa Tsai, Chi-Ping Chen. A Novel Multiple-Searching Genetic Algorithm for Multimedia Multicast Routing. Proceedings of the 2002 Congress on Evolutionary Computation CEC2002. 506-511
[45] http://www.ifip.or.at/con2000/icct2000/icct069.pdf
[46] Esbensen Henrik. Computing near-optimal solutions to the steiner problem in a graph using a genetic algorithm. Networks, 1995, 26:173-185
[47] http://citeseer.nj.nec.com/95768.html
[48] 何小燕，费翔，罗军舟，吴介一. Internet中一种基于遗传算法的ＱoＳ路由选择策略. 计算机学报，2000, 23(11):1171-1178
[49] 王征应, 石冰心. 基于启发式遗传算法的QoS组播路由问题求解. 计算机学报, 2001, 24(1):55-61
[50] 王征应, 石冰心, 赵尔敦. QoS组播路由的启发式遗传算法. 电子学报, 2001, 29(2):253-256
[51] 王新红，杜荔，王光兴. 一种基于遗传算法的组播路由选择方法. 东北大学学报，2001，22(5):513-516
[52] 陈明,李志杰. 基于遗传算法的实时组播通信路由算法.软件学报,2001, 12 (5):721-728
[53] http://www.csm.ornl.gov/~dunigan/oci/uni_rpf.pdf
[54] http://www.cis.ohio-state.edu/cgi-bin/rfc/rfc2236.html
[55] 王小平，曹立明.遗传算法.西安：西安交通大学出版社，2002
[56] http://home.earthlink.net/~akiraoyama/Phdthesis/chapter2.pdf
[57] R. Hinterding, Z. Michalewicz, and A. E. Eiben. Adaptation in evolutionary computation: A survey. Proceedings of the Fourth International Conference on Evolutionary Computation (ICEC 97). IEEE Press, Piscataway (NJ), 1997: 65-69
[58] Rudolph G. Convergence analysis of canonical genetic algorithms.IEEE Trans on Neural Networks,1994,5(1):96-101
[59] Clifford A.Shaffer.张铭, 刘晓丹. Data Structures and Algorithm analysis. 北京：电子工业出版社，2000.
[60] D. Eppstein. Finding the k shortest paths. 35th IEEE Symp. Foundations of Comp. Sci., Santa Fe, 1994:154-165