This work introduces ANB (bf Ant Algorithm for bf Non-bf 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.
@article{bwmeta1.element.bwnjournal-article-amcv15i2p205bwm,
author = {Walkowiak, Krzysztof},
title = {Ant algorithm for flow assignment in connection-oriented networks},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {15},
year = {2005},
pages = {205-220},
zbl = {1095.90068},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv15i2p205bwm}
}
Walkowiak, Krzysztof. Ant algorithm for flow assignment in connection-oriented networks. International Journal of Applied Mathematics and Computer Science, Tome 15 (2005) pp. 205-220. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv15i2p205bwm/
[000] Assad A. (1978): Multicommodity network flows - A survey. - Network, Vol. 8, No. 1, pp. 37-91. | Zbl 0381.90040
[001] Bienstock D. (2002): Potential Function Methods for Approximately Solving Linear Programming Problems, Theory and Practice. - Boston: Kluwer. | Zbl 1088.90001
[002] Burns J., Ott T., Krzesinski A. and Muller K. (2003): Path selection and band width allocation in MPLS networks. - Perform. Eval., Vol. 52, No. 2-3, pp. 133-152.
[003] Cantor D. and Gerla M. (1974): Optimal routing in a packet-switched computer network. - IEEE Trans. Comm., Vol. 23, No. 10, pp. 1062-1069. | Zbl 0291.90031
[004] 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. | Zbl 0863.90120
[005] Corne D., Oates M. and Smith D. (Eds.) (2000): Telecommunications Optimization: Heuristic and Adaptive Techniques. - New York: Wiley.
[006] 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.
[007] Di Caro G. and Dorigo M. (1998b): AntNet: Distributed stigmergetic control for communications networks. - J. Artif. Intell. Res., Vol. 9, pp. 317-365. | Zbl 0910.68182
[008] Dorigo M., Maniezzo V. and Colorni A. (1991): Positive feedback as a search strategy. - Techn. Rep. No. 91-016, Politechnico di Milano, Italy. | Zbl 0825.90549
[009] Dorigo M., Di Caro G. and Gambardella L. (1999): Ant algorithms for discrete optimization. - Artif. Life, Vol. 5, No. 2, pp. 137-172.
[010] 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.
[011] 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. | Zbl 1131.90321
[012] 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.
[013] 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. | Zbl 1026.90010
[014] 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.
[015] Grover W. (2004): Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking. - Upper Saddle River, NJ:Prentice Hall.
[016] 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.
[017] Kar K., Kodialam M. and Lakshman, T.V. (2000): Minimum interference routing of band width guaranteed tunnels with MPLS traffic engineering applications. - IEEE J. Select. Areas Commun., Vol. 18, No. 12, pp. 2566-2579.
[018] Karp R. (1975): On the computational complexity of combinatorical problems. - Networks, Vol. 5, No. 1, pp. 45-68. | Zbl 0324.05003
[019] Kasprzak A. (2001): Design of Wide Area Networks. - Wrocław: Wrocław University of Technology Press, (in Polish).
[020] 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.
[021] Murakami K. and Kim H. (1996): Virtual path routing for survivable ATM networks. - IEEE/ACM Trans. Networking, Vol. 4, No. 1, pp. 22-39.
[022] 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.
[023] Pioro M. and Medhi D. (2004): Routing, Flow, and Capacity Design in Communication and Computer Networks. - Amsterdam: Morgan Kaufmann. | Zbl 1069.68021
[024] Pioro 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.
[025] Schoonderwoerd R., Holland O. and Bruten J. (1997): Ant-like agents for load balancing in telecommunications networks. - Proc. Conf. Agents'97, Marina del Rey, California, USA, pp. 209-216.
[026] 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. | Zbl 0348.90062
[027] 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.
[028] 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. | Zbl 1046.68921
[029] 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.
[030] 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.
[031] Walkowiak K. (2001b): Ant algorithms for design of computer networks. - Proc. 7-th Int. Conf. Soft Computing MENDEL, Brno, Czech Republic, pp. 149-154.
[032] 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. | Zbl 1038.90503
[033] Walkowiak K. (2003a): A new approach to survivability of connection oriented networks. - Lect. Notes Comput. Sci., Vol. 2657, pp. 501-510. | Zbl 1033.68528
[034] 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.
[035] 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. | Zbl 1044.90093
[036] 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, USA, pp. 802-809.