Bandwidth Optimization through Dynamic Routing in ATM Networks: Genetic Algorithm and Tabu Search Approach

Asynchronous Transfer Mode (ATM) is widely used in telecommunications systems to send data, video and voice at a very high speed. In ATM network optimizing the bandwidth through dynamic routing is an important consideration. Previous research work shows that traditional optimization heuristics result in suboptimal solution. In this paper we have explored non-traditional optimization technique. We propose comparison of two such algorithms - Genetic Algorithm (GA) and Tabu search (TS), based on non-traditional Optimization approach, for solving the dynamic routing problem in ATM networks which in return will optimize the bandwidth. The optimized bandwidth could mean that some attractive business applications would become feasible such as high speed LAN interconnection, teleconferencing etc. We have also performed a comparative study of the selection mechanisms in GA and listed the best selection mechanism and a new initialization technique which improves the efficiency of the GA.

Authors:

• Susmi Routray
• A. M. Sherry
• B. V. R. Reddy

Keywords:

• Asynchronous Transfer Mode(ATM)
• GeneticAlgorithm(GA)
• Tabu Search(TS).

References:

[1] D. Raychaudhuri and D. Wilson, "ATM-Based Transport Architecture
for Multiservices Wireless Personal Communication Networks ", IEEE
Journal On Selected Areas In Communications, vol 12, No 8, pp 1401 -
1413, Oct. 1994.
[2] P. Wong and D. Britland, " Mobile Data Communication ", Artech
House, 1993.
[3] S. Gupta et. al., "Routing in virtual path based ATM networks", IEEE
GLOBECOM92, vol. 27, 1993.
[4] K. I. Sato and I. Tokisawa, "Flexible Asynhronous Transfer Mode
network utilizing virtual path", Proc. IEEE SUPERCOMM ICC 90, 831-
838, 16-19 April 1990.
[5] J. L. Adams, "The virtual identifier and its application for routing and
priority of connectionless and connection-oriented service", Int. Journal
of Digital and Analog Cabled Networks, 257-262, 16-19 April-1988.
[6] S. Tanterdtid et al., "Optimizing ATM network throughput based on
Virtual Paths concept by using Genetic Algorithm", Proc. IEEE
ICIPS-97, Beijing, 1634-1639, 1997.
[7] S. W. Park and W. K. Tsai, "Optimal routing algorithm for high-speed
(ATM) networks", Proc. IEEE INFOCOM-93, San Francisco, CA, USA,
3, 972-979, 28 March-1 April-1993.
[8] F. Y. S. Lin and K. T. Cheng, "Virtual Path assignment and virtual
circuit routing", Proc. IEEE GLOBECOM-93, Houston, TX, USA, 1,
436-441, 29 November-2 December 1993.
[9] E. W. M. Wong et. al., "Bandwidth allocation and routing in virtual
path based ATM networks", Proc. IEEE ICC/SUPER COMM-96, June
1996.
[10] S. Al-Sharhan et. al., "Learning-based resource optimization in
asynchronous transfer mode (ATM) networks", Systems, Man and
Cybernetics, Part B, IEEE Transactions on, Volume 33, Issue 1,
Page(s):122 - 132, Feb. 2003.
[11] A. Vasilakos, et. al., "Optimizing QoS routing in hierarchical ATM
networks using computational intelligence techniques", Systems, Man
and Cybernetics, Part C, IEEE Transactions on, Volume 33, Issue 3,
Page(s):297 - 312, Aug. 2003.
[12] DE. Goldberg, Genetic Algorithm in search , "optimization and machine
learning", NewYork, Addison Wesley,1991.
[13] M. Srinivas, Lalit M. Patnaik, "Genetic Algorithms: A survey", IEEE,
1994.
[14] M. Srinivas, Lalit M. Patnaik, "Adaptive probabilities of crossover and
Mutation in Genetic Algorithms", IEEE Trans. System, 1994.
[15] D. R. Thompson, G. L. Bilbro, "Comparison of a genetic algorithm with
a simulated annealing algorithm for the design of an ATM network",
Communications Letters, IEEE Volume 4, Issue 8, Page(s):267 - 269,
Aug. 2000.
[16] H. Pan and I. Y. Wang, "The bandwidth allocation of ATM through
Genetic Algorithm", Proc. IEEE GLOBECOM-91, Phoenix, AZ, USA,
125-129,1991.
[17] N. Shimamoto, A. Hiramatsu and K. Yamasaki, "A dynamic routing
control based on a Genetic Algorithm",Proc. IEEE ICNN-93, San
Francisco, CA, USA,1123-1128, 28 March-1 April 1993.
[18] S. Tanterdtid et al., "An optimum virtual paths network-based ATM
network using the Genetic Algorithm", Proc. International Journal of
Network Management, 8,158-169 , 1998.
[19] Glover, F., "Tabu Search" Part I, ORSA Journal on Computing 1 1989.
[20] F. Glover and M. Laguna: Tabu search, Kluwer Academic Publishers,
1997.
[21] S. Chamberland, "On the overlay network design problem for the S-PVC
connections in ATM networks", Global Telecommunications
Conference, 2000. GLOBECOM' 00. IEEE
Volume 3, Page(s):1752 - 1755 vol.3 27 Nov.-1 Dec. 2000.
[22] S. Chamberland, "On the planning of the S-PVC overlay in ATM
networks", Communications Letters, IEEE Volume 6, Issue 3,
Page(s):114 - 116, March 2002.
[23] Y. Sato and K. Sato, "Virtual path and link capacity design of ATM
networks", IEEE journal on selected areas of communications, Vol. 9,
No. 1, pp. 104 - 111, Jan 1991.
[24] M. Gerla et. al.," Topology design and bandwidth allocation in ATM
nets,", IEEE journal on selected areas of communications, Vol. 7, No. 8,
pp. 1253 - 1262, October 1989.