Application layer multicast routing solution based on genetic algorithms

Abstract

Application layer multicast routing is a multi-objective optimization problem. Three routing constraints, tree's cost, tree's balance and network layer load distribution are analyzed in this paper. The three fitness functions are used to evaluate a multicast tree on the three indexes respectively and one general fitness function is generated. A novel approach based on genetic algorithms is proposed. Numerical simulations show that, compared with geometrical routing rules, the proposed algorithm improve all three indexes, especially on cost and network layer load distribution indexes.

Keywords

multicast / application layer multicast / genetic algorithms / multicast routing

References

[1] LiebeherrJ, NahasM, SiW S. Application-layer multicasting with delaunay triangulation overlays. IEEE Journal on Selected Areas in Communications, 2002, 20(8): 1472–1488

[2] PendarakisD, ShiS, VermaD, . ALMI: An application level multicast infrastructure. In: Proceedings of 3rd Usenix Symposium on Internet Technologies and Systems, 2001

[3] HwangR H, DoW Y, YangS C. Multicast routing based on genetic algorithms. Journal of Information Science and Engineering, 2000, 16(6): 885–901

[4] ShiS Y, TurnerJ S. Routing in overlay multicast networks. In: Proceedings of IEEE INFOCOM, 2002, 3: 1200–1208

[5] PanY, YuZ W, WangL C. A genetic algorithm for the overlay multicast routing problem. In: Proceedings of ICCNMC'03, 2003, 261–265

[6] KranakisE, SinghH, UrrutiaJ. Compass routing on geometric networks. In: Proceedings of 11th Canada Conference on Computational Geometry (CCCG'90), 1999, 51–54

[7] HamdanM, El-HawaryM E. A novel genetic algorithm searching approach for dynamic constrained multicast routing. In: Proceedings of CCECE 2003, 2003, 2: 1127–1130

[8] HaghighatA T, FaezK, DehghanM, . GA-based heuristic algorithms for bandwidth-delay-constrained least-cost multicast routing. Computer Communications, 2004, 27(1): 111–127

[9] WangZ Y, ShiB X, ZhaoE. Bandwidth-delay-constrained least-cost multicast routing based on heuristic genetic. Computer Communications, 2001, 24(7): 685–692

[10] SunQ, LangendoerferH. Computation of constrained multicast trees using a genetic algorithm. European Transactions on Telecommunications, 1999, 10(5): 513–516

[11] HamdanM, El-HawaryM E. Hopfield-Genetic approach for solving the routing problem in computer networks. In: Proceedings of IEEE Canadian Conference on Electrical and Computer Engineering, 2002, 2: 823–827

[12] ZeguraE W, CalvertK L, BhattacharjeeS. How to model an internetwork. In: Proceedings of IEEE INFOCOM'96, San Francisco. 1996, 2: 594–602

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant No. 60432030).

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg