Multiobjective Optimization for Multicast Routing in Overlay Networks using Evolutionary Algorithms
Main Article Content
Keywords
multicast, overlay networks, multiobjective optimization, MOEA
Abstract
Multicast plays an important role in supporting a new generation of applications. At present and for different reasons, technical and non–technical, multicast IP hasn’t yet been totally adopted for Internet. During recent years, an active area of research is that of implementing this kind of traffic in the application layer where the multicast functionality isn´t a responsibility of the routers but that of the hosts, which we know as Multicast Overlay Networks (MON). In this article, routing in an MON is put forward as a multiobjective optimization problem (MOP) where two functions are optimized: 1) the total end to end delay of the multicast tree and 2) the maximum link utilization. The simultaneous optimization of these two functions is an NP–Complete problem and to solve this we suggest using Multiobjective Evolutionary Algorithms (MOEA), specifically NSGA–II.
Downloads
Download data is not yet available.
References
[1] L. Sahasrabuddhe and B. Mukherjee. Multicast routing algorithms and protocols: A tutorial . IEEE Network, ISSN 0890–8044, 14(1), 90–102 (Jan–Feb 2000).
[2] Stephen E. Deering. Multicast routing in internetworks and extended LANs. SIGCOMM ’88: Symposium proceedings on Communications architectures and protocols, ISBN 0–89791–279–9, 55–64 (August 1988).
[3] Christophe Diot, Brian Neil Levine, Bryan Lyles, Hassan Kassem and Doug Balensiefen. Deployment issues for the IP multicast service and architecture. IEEE Network, ISSN 0890–8044, 14(1), 78–88 (Jan–Feb 2000).
[4] Yang-hua Chu, Sanjay G. Rao, Srinivasan Seshan and Hui Zhang. A case for end system multicast . IEEE Journal on selected areas in Communications, ISSN 0733–8716, 20, 1456–1471 (October 2002).
[5] Yatin Dilip Chawathe. Scattercast: An Architecture for Internet Broadcast Dis- tribution as an Infrastructure Service. Doctoral Thesis, ISBN 0–493–10435–6, (2000).
[6] John Jannotti, David K. Gifford, Kirk L. Johnson, M. Frans Kaashoek and James W. O’Toole, Jr. Overcast: Reliable multicasting with an overlay network. Proc. 4th Symp. Operating Systems Design and Implementation (OSDI), 197–212 (October 2000).
[7] Yezid Donoso and Ramón Fabregat. Multi–objective Optimization in Compu- ter Networks Using Metaheuristics. Auerbach Publications Taylor and Francis Group, ISBN 0849380847, March 2007.
[8] Zhi Li and PrasantMohapatra. The impact of topology on overlay routing service. INFOCOM 2004, Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, ISSN 0743–166X , 1, 418 (March 2004).
[9] Zhi Li and PrasantMohapatra. QRON: QoS-aware Routing in Overlay Networks. IEEE Journal on Selected Areas in Communications, ISSN 0733–8716, 22(1), 29– 40 (January 2004).
[10] Yun Pan, Zhenwei Yu and Licheng Wang. A genetic algorithm for the overlay multicast routing problem. Proceedings of the 2003 International Conference on Computer Networks and Mobile Computing (ICCNMC’03), ISSN 0–7695–2033–2, 261–265, (October 2003).
[11] Cheng Peng, Dai Qionghai and Wu Qiufeng. An application layer multicast routing algorithm based on genetic algorithms. Telecommunications, 2005. ConTEL 2005. Proceedings of the 8th International Conference on, ISBN 953–184–081–4, 2, 413–418 (June 2005).
[12] H. Ishibuchi and K. Narukawa. Comparison of evolutionary multiobjective op- timization with reference solution–based single–objective approach. GECCO ’05: Proceedings of the 2005 conference on Genetic and evolutionary computation, ISBN 1–59593–010–8, 787–794 (2005).
[13] Eckart Zitzler, Marco Laumanns and Lothar Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems (EUROGEN 2001), 95–100, (June 2002).
[14] K. Deb and A Pratap and S. Agarwal and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA–II . IEEE transactions on Evolutionary Computation, ISSN 1089–778X, 6(2), 182–197 (April 2002).
[15] Thomas Back. Evolutionary Algorithms in Theory and Practice, ISBN 978- 0195099713, Oxford University Press, January 1996.
[16] Kalyanmoy Deb. Multi–Objective Optimization Using Evolutionary Algorithms, ISBN 978–0471873396, UK: J. Wiley Sons, June 2001.
[17] Carlos A. Coello Coello. An Updated Survey of GA–Based Multiobjective Optimization Techniques. ACM Computing Surveys, ISSN 0360–0300, 32(2), 109–143 (June 2000).
[18] E. Zitzler, L. Thiele and K. Deb. Comparisons of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, ISSN 1063–6560, 8, 173–195 (June 2000).
[19] Alberto Medina, Anukool Lakhina, Ibrahim Matta and John Byers. BRITE: An approach to universal topology generation. In Proceedings of IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), ISBN 0–7695–1315–8, 346–353 (August 2001).
[2] Stephen E. Deering. Multicast routing in internetworks and extended LANs. SIGCOMM ’88: Symposium proceedings on Communications architectures and protocols, ISBN 0–89791–279–9, 55–64 (August 1988).
[3] Christophe Diot, Brian Neil Levine, Bryan Lyles, Hassan Kassem and Doug Balensiefen. Deployment issues for the IP multicast service and architecture. IEEE Network, ISSN 0890–8044, 14(1), 78–88 (Jan–Feb 2000).
[4] Yang-hua Chu, Sanjay G. Rao, Srinivasan Seshan and Hui Zhang. A case for end system multicast . IEEE Journal on selected areas in Communications, ISSN 0733–8716, 20, 1456–1471 (October 2002).
[5] Yatin Dilip Chawathe. Scattercast: An Architecture for Internet Broadcast Dis- tribution as an Infrastructure Service. Doctoral Thesis, ISBN 0–493–10435–6, (2000).
[6] John Jannotti, David K. Gifford, Kirk L. Johnson, M. Frans Kaashoek and James W. O’Toole, Jr. Overcast: Reliable multicasting with an overlay network. Proc. 4th Symp. Operating Systems Design and Implementation (OSDI), 197–212 (October 2000).
[7] Yezid Donoso and Ramón Fabregat. Multi–objective Optimization in Compu- ter Networks Using Metaheuristics. Auerbach Publications Taylor and Francis Group, ISBN 0849380847, March 2007.
[8] Zhi Li and PrasantMohapatra. The impact of topology on overlay routing service. INFOCOM 2004, Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, ISSN 0743–166X , 1, 418 (March 2004).
[9] Zhi Li and PrasantMohapatra. QRON: QoS-aware Routing in Overlay Networks. IEEE Journal on Selected Areas in Communications, ISSN 0733–8716, 22(1), 29– 40 (January 2004).
[10] Yun Pan, Zhenwei Yu and Licheng Wang. A genetic algorithm for the overlay multicast routing problem. Proceedings of the 2003 International Conference on Computer Networks and Mobile Computing (ICCNMC’03), ISSN 0–7695–2033–2, 261–265, (October 2003).
[11] Cheng Peng, Dai Qionghai and Wu Qiufeng. An application layer multicast routing algorithm based on genetic algorithms. Telecommunications, 2005. ConTEL 2005. Proceedings of the 8th International Conference on, ISBN 953–184–081–4, 2, 413–418 (June 2005).
[12] H. Ishibuchi and K. Narukawa. Comparison of evolutionary multiobjective op- timization with reference solution–based single–objective approach. GECCO ’05: Proceedings of the 2005 conference on Genetic and evolutionary computation, ISBN 1–59593–010–8, 787–794 (2005).
[13] Eckart Zitzler, Marco Laumanns and Lothar Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems (EUROGEN 2001), 95–100, (June 2002).
[14] K. Deb and A Pratap and S. Agarwal and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA–II . IEEE transactions on Evolutionary Computation, ISSN 1089–778X, 6(2), 182–197 (April 2002).
[15] Thomas Back. Evolutionary Algorithms in Theory and Practice, ISBN 978- 0195099713, Oxford University Press, January 1996.
[16] Kalyanmoy Deb. Multi–Objective Optimization Using Evolutionary Algorithms, ISBN 978–0471873396, UK: J. Wiley Sons, June 2001.
[17] Carlos A. Coello Coello. An Updated Survey of GA–Based Multiobjective Optimization Techniques. ACM Computing Surveys, ISSN 0360–0300, 32(2), 109–143 (June 2000).
[18] E. Zitzler, L. Thiele and K. Deb. Comparisons of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, ISSN 1063–6560, 8, 173–195 (June 2000).
[19] Alberto Medina, Anukool Lakhina, Ibrahim Matta and John Byers. BRITE: An approach to universal topology generation. In Proceedings of IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), ISBN 0–7695–1315–8, 346–353 (August 2001).