A routing algorithm constructs routing tables to forward communication packets based on network status information. Rapid inflation of the Internet increases demand for scalable and adaptive network routing algorithms. Conventional protocols such as the Routing Information Protocol (RIP) (Hedrick, 1988) and the Open Shortest-Path First protocol (OSPF) (Comer, 1995) are not adaptive algorithms; they because they only rely on hop count metrics to calculate shortest paths. In large networks, it is difficult to realize an adaptive algorithm based on conventional approaches. . | Telecommunications Optimization Heuristic and Adaptive Techniques. Edited by David W. Corne Martin J. Oates George D. Smith Copyright 2000 John Wiley Sons Ltd ISBNs 0-471-98855-3 Hardback 0-470-84163X Electronic 9 The Genetic Adaptive Routing Algorithm Masaharu Munetomo Introduction A routing algorithm constructs routing tables to forward communication packets based on network status information. Rapid inflation of the Internet increases demand for scalable and adaptive network routing algorithms. Conventional protocols such as the Routing Information Protocol RIP Hedrick 1988 and the Open Shortest-Path First protocol OSPF Comer 1995 are not adaptive algorithms they because they only rely on hop count metrics to calculate shortest paths. In large networks it is difficult to realize an adaptive algorithm based on conventional approaches. This is because they employ broadcasts to collect information on routing tables or network link status which causes excessive overheads in adaptive algorithms. In this chapter we describee an adaptive routing algorithm called the Genetic Adaptive Routing Algorithm GARA . The algorithm maintains a limited number of alternative routes that are frequently used. Instead of broadcasting a whole routing table or link it only observes communication latency for the alternative routes. It also tries to balance link loads by distributing packets among the alternative routes in its routing table. The alternative routes are generated by path genetic operators. Routing algorithms in the Internet From the early history of the Internet vector distance routing algorithms based on BellmanFord s algorithm Bellman 1957 Ford and Fulkerson 1962 have usually been employed. Telecommunications Optimization Heuristic and Adaptive Techniques edited by . Corne . Oates and . Smith 2000 John Wiley Sons Ltd 152 Telecommunications Optimization Heuristic and Adaptive Techniques The Routing Information Protocol RIP Hedrick 1988 based on .
