Ant algorithm for flow assignment in connection-oriented networks

Krzysztof Walkowiak

International Journal of Applied Mathematics and Computer Science (2005)

  • Volume: 15, Issue: 2, page 205-220
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Walkowiak, Krzysztof. "Ant algorithm for flow assignment in connection-oriented networks." International Journal of Applied Mathematics and Computer Science 15.2 (2005): 205-220. <http://eudml.org/doc/207736>.

@article{Walkowiak2005,
abstract = {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.},
author = {Walkowiak, Krzysztof},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {flow assignment; computer networks; ant algorithms; computer network},
language = {eng},
number = {2},
pages = {205-220},
title = {Ant algorithm for flow assignment in connection-oriented networks},
url = {http://eudml.org/doc/207736},
volume = {15},
year = {2005},
}

TY - JOUR
AU - Walkowiak, Krzysztof
TI - Ant algorithm for flow assignment in connection-oriented networks
JO - International Journal of Applied Mathematics and Computer Science
PY - 2005
VL - 15
IS - 2
SP - 205
EP - 220
AB - 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.
LA - eng
KW - flow assignment; computer networks; ant algorithms; computer network
UR - http://eudml.org/doc/207736
ER -

References

top
  1. Assad A. (1978): Multicommodity network flows - A survey. - Network, Vol. 8, No. 1, pp. 37-91. Zbl0381.90040
  2. Bienstock D. (2002): Potential Function Methods for Approximately Solving Linear Programming Problems, Theory and Practice. - Boston: Kluwer. Zbl1088.90001
  3. 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. 
  4. Cantor D. and Gerla M. (1974): Optimal routing in a packet-switched computer network. - IEEE Trans. Comm., Vol. 23, No. 10, pp. 1062-1069. Zbl0291.90031
  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. Zbl0863.90120
  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. Zbl0910.68182
  9. Dorigo M., Maniezzo V. and Colorni A. (1991): Positive feedback as a search strategy. - Techn. Rep. No. 91-016, Politechnico di Milano, Italy. Zbl0825.90549
  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. Zbl1131.90321
  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. Zbl1026.90010
  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 band width 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. Zbl0324.05003
  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. Pioro M. and Medhi D. (2004): Routing, Flow, and Capacity Design in Communication and Computer Networks. - Amsterdam: Morgan Kaufmann. Zbl1069.68021
  25. 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. 
  26. 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. 
  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. Zbl0348.90062
  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. Zbl1046.68921
  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. Zbl1038.90503
  34. Walkowiak K. (2003a): A new approach to survivability of connection oriented networks. - Lect. Notes Comput. Sci., Vol. 2657, pp. 501-510. Zbl1033.68528
  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. Zbl1044.90093
  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, USA, pp. 802-809. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.