Ant Algorithm for Flow Assignment in Connection-oriented Networks

Walkowiak, K.

International Journal of Applied Mathematics and Computer Science, Tome 15 (2005) no. 2, pp. 205-220.

Résumé

This work introduces ANB (Ant Algorithm for Non-Bifurcated Flows), a novel approach to capacitated static optimization of flows in connection-oriented computer networks. The problem considered arises naturally from several optimization problems that have recently received significant attention. The proposed ANB is an ant algorithm motivated by recent works on the application of the ant algorithm to solving various problems related to computer networks. However, few works concern the use of ant algorithms in the assignment of static flows in connection-oriented networks. We analyze the major characteristics of the ANB and try to explain its performance. We report results of many experiments over various networks.

Détail

Keywords: ant algorithms, flow assignment, computer networks
Mots-clés : algorytm mrówkowy, przypisanie przepływu, sieć komputerowa

Bibliographie

[1] Assad A. (1978): Multicommodity network flows – A survey. — Network, Vol. 8, No. 1, pp. 37–91.

[2] Bienstock D. (2002): Potential Function Methods for Approximately Solving Linear Programming Problems, Theory and Practice.— Boston: Kluwer.

[3] Burns J., Ott T., Krzesinski A. and Muller K. (2003): Path selection and bandwidth allocation in MPLS networks. — Perform. Eval., Vol. 52, No. 2–3, pp. 133–152.

[4] Cantor D. and Gerla M. (1974): Optimal routing in a packets-witched computer network. — IEEE Trans. Comm., Vol. 23, No. 10, pp. 1062–1069.

[5] Colorni A., Dorigo M., Maffioli F., Maniezzo V., Righini G. and Trubian M. (1996): Heuristics from nature for hard combinatorial problems. — Int. Trans. Oper. Res., Vol. 3, No. 1, pp. 1–21.

[6] Corne D., Oates M. and Smith D. (Eds.) (2000): Telecommunications Optimization: Heuristic and Adaptive Techniques. — New York: Wiley.

[7] Di Caro G. and Dorigo M. (1998a): Mobile agents for adaptive routing. — Proc. 31st Hawaii Int. Conf. System, Kohala Coast, Hawaii, USA, pp. 74–83.

[8] Di Caro G. and Dorigo M. (1998b): AntNet: Distributed stigmergetic control for communications networks.—J. Artif. Intell. Res., Vol. 9, pp. 317–365.

[9] Dorigo M., Maniezzo V. and Colorni A. (1991): Positive feedback as a search strategy.—Techn. Rep. No. 91–016, Politechnico di Milano, Italy.

[10] Dorigo M., Di Caro G. and Gambardella L. (1999): Ant algorithms for discrete optimization. — Artif. Life, Vol. 5, No. 2, pp. 137–172.

[11] Elbaum R. and Sidi M. (1996): Topological design of local-area networks using genetic algorithms. — IEEE/ACM Trans. Networking, Vol. 4, No. 5, pp. 766–778.

[12] Fratta L., Gerla M. and Kleinrock L. (1973): The flow deviation method: An approach to store-and-forward communication network design. —Networks, Vol. 3, pp. 97–133.

[13] Garlick R. and Barr R. (2003): Dynamic wavelength routing in WDM networks via ant colony optimization.—Lect. Notes Comput. Sci., Vol. 2463, pp. 250–255.

[14] Gendron B., Crainic T.G. and Frangioni A. (1998): Multicommodity capacitated network design, In: Telecommunications Network Planning (B. Sans‘o and P. Soriano, Eds.). —Norwell, MA: Kluwer, pp. 1–19.

[15] Girard A. and Sanso B. (1998): Multicommodity flow models, failure propagation and reliable loss network design. — IEEE/ACM Trans. Networking, Vol. 6, No. 1, pp. 82–93.

[16] Grover W. (2004): Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking. — Upper Saddle River, NJ: Prentice Hall.

[17] Herzberg M., Bye S. and Utano A. (1995): The hop-limit approach for spare-capacity assignment in survivable networks. — IEEE/ACM Trans. Networking, No. 6 pp. 775–784.

[18] Kar K., Kodialam M. and Lakshman, T.V. (2000): Minimum interference routing of bandwidth guaranteed tunnels with MPLS traffic engineering applications. — IEEE J. Select. Areas Commun., Vol. 18, No. 12, pp. 2566–2579.

[19] Karp R. (1975): On the computational complexity of combinatorical problems. —Networks, Vol. 5, No. 1, pp. 45–68.

[20] Kasprzak A. (2001): Design of Wide Area Networks. — Wrocław: Wrocław University of Technology Press, (in Polish).

[21] Kassabalidis I., El-Sharkawi M.A., Marks II R.J., Arabshahi P. and Gray A.A. (2001): Swarm intelligence for routing in communication networks.—Proc. IEEE Conf. Globecom, San Antonio, Texas, USA, pp. 541–546.

[22] Murakami K. and Kim H. (1996): Virtual path routing for survivable ATM networks. — IEEE/ACM Trans. Networking, Vol. 4, No. 1, pp. 22–39.

[23] Ott T., Bogovic T., Carpenter T., Krishnan K.R. and Shallcross D. (2001): Algorithms for flow allocation for multi protocol label switching. — Telcordia Techn. Memorandum TM-26027.

[24] Pióro M. and Medhi D. (2004): Routing, Flow, and Capacity Design in Communication and Computer Networks. — Amsterdam: Morgan Kaufmann.

[25] Pióro M., Srivastava S., Krithikaivasan B. and Medhi D. (2003): Path generation technique for robust design of wide area communication networks. — Proc. 10-th Polish Teletraffic Symp., Cracow, Poland, pp. 67–80.

[26] Schoonderwoerd R., Holland O. and Bruten J. (1997): Antlike agents for load balancing in telecommunications networks.— Proc. Conf. Agents’97, Marina del Rey, California, USA, pp. 209–216.

[27] Schwartz M. and Cheung C. (1976): The gradient projection algorithm for multpile-routing in message switched networks. — IEEE Trans. Comm., Vol. 24, No. 4, pp. 449–456.

[28] Subramanian D., Druschel P. and Chen J. (1997): Ants and reinforcement learning: A case study in routing in dynamic networks. — Proc. Int. Joint Conf. Artificial Intelligence, Nagoya, Aichi, Japan pp. 832–838.

[29] Szeto W., Boutaba R. and Iraqi Y. (2002): Dynamic online routing algorithm for MPLS traffic engineering.—Lect. Notes Comput. Sci., Vol. 2345, pp. 936–946.

[30] Varela N.G. and Sinclair M.C. (1999): ant colony optimisation for virtual-wavelength-path routing and wavelength allocation. — Proc. Congress Evolutionary Computation, Washington, USA, pp. 1809–1816.

[31] Walkowiak K. (2001a): Genetic approach to virtual paths assignment in survivable ATM networks. — Proc. 7-th Int. Conf. Soft Computing MENDEL, Brno, Czech Republic, pp. 13–18.

[32] Walkowiak K. (2001b): Ant algorithms for design of computer networks. — Proc. 7-th Int. Conf. Soft Computing MENDEL, Brno, Czech Republic, pp. 149–154.

[33] Walkowiak K. (2002): The branch and bound algorithm for backup virtual path assignment in survivable ATM networks. — Appl. Math. Comput. Sci., Vol. 12, No. 2, pp. 257–267.

[34] Walkowiak K. (2003a): A new approach to survivability of connection oriented networks. — Lect. Notes Comput. Sci., Vol. 2657, pp. 501–510.

[35] Walkowiak K. (2003b): Heuristic algorithms for assignment of non-bifurcated multicommodity flows. — Proc. Conf. Advanced Simulation of Systems ASIS, Sv Hostyn, Czech Republic, pp. 243–248.

[36] Walkowiak K. (2004): A branch and bound algorithm for primary routes assignment in survivable connection oriented networks. — Comput. Optim. Applic., Vol. 27, No. 2, pp. 149–171.

[37] White T., Pagurek B. and Oppacher F. (1998): Connection management using adaptive mobile agents. — Proc. Int. Conf. Parallel and Distributed Processing Techniques and Applications, Las Vegas, and Distributed Processing Techniques and Applications, Las Vegas, USA, pp. 802–809.