Tối ưu hóa viễn thông và thích nghi Kỹ thuật Heuristic P9

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. ...
Nội dung trích xuất từ tài liệu:
Tối ưu hóa viễn thông và thích nghi Kỹ thuật Heuristic P9 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)9The Genetic Adaptive RoutingAlgorithmMasaharu Munetomo9.1 IntroductionA routing algorithm constructs routing tables to forward communication packets based onnetwork status information. Rapid inflation of the Internet increases demand for scalableand adaptive network routing algorithms. Conventional protocols such as the RoutingInformation Protocol (RIP) (Hedrick, 1988) and the Open Shortest-Path First protocol(OSPF) (Comer, 1995) are not adaptive algorithms; they because they only rely on hopcount metrics to calculate shortest paths. In large networks, it is difficult to realize anadaptive algorithm based on conventional approaches. This is because they employbroadcasts to collect information on routing tables or network link status, which causesexcessive overheads in adaptive algorithms. In this chapter, we describee an adaptive routing algorithm called the Genetic AdaptiveRouting Algorithm (GARA). The algorithm maintains a limited number of alternativeroutes that are frequently used. Instead of broadcasting a whole routing table or link status,it only observes communication latency for the alternative routes. It also tries to balancelink loads by distributing packets among the alternative routes in its routing table. Thealternative routes are generated by path genetic operators.9.2 Routing algorithms in the InternetFrom the early history of the Internet, vector distance routing algorithms based on Bellman-Ford’s algorithm (Bellman, 1957; Ford and Fulkerson, 1962) have usually been employed.Telecommunications Optimization: Heuristic and Adaptive Techniques, edited by D.W. Corne, M.J. Oates and G.D. Smith© 2000 John Wiley & Sons, Ltd152 Telecommunications Optimization: Heuristic and Adaptive TechniquesThe Routing Information Protocol (RIP) (Hedrick, 1988) based on the vector-distancealgorithm with hop count metric is commonly used even now in small local area networks.The algorithm yields many communication overheads in larger networks because theyperiodically send broadcast messages that contain a whole routing table. More precisely,the number of messages to broadcast routing tables is proportional to n 2 (n is the numberof nodes in a network) and the size of a routing table is proportional to n, which means thatthe total communication overhead for the routing information exchange becomes O(n 3 ).The vector distance algorithm also suffers from its slow convergence because it isnecessary for the routing tables to reach all the nodes in the network to obtain the correctdistance. To reduce communication overhead, routing algorithms based on link status informationsuch as the SPF (Shortest Path First protocol) send broadcast messages that only containinformation on link status. Based on a topological database generated from the collectedlink status, the algorithm calculates the shortest paths employing Dijkstra’s shortest pathalgorithm (Dijkstra, 1959) in each node. The SPF broadcasts messages that only contain thenodes’ link status instead of the entire routing table. Therefore, the size of a message thatcontains link status information becomes O(1) when the degree of nodes is constant suchas in a mesh network, and the size becomes O(log n) in a hypercube network. However,the number of messages is also proportional to n 2 , which leads to extensive overheads inlarger size network. Therefore, the OSPF (Open Shortest Path First protocol) (Moy, 1989),a widely used network routing protocol for Interior Gateway Protocol (IGP) (Comer, 1995)based on the SPF, relies on hop count metric and detects topological changes such as linkfailure. It seems easy to collect information on the communication latency of links and calculateroutes with minimum delay; however, it is almost impossible in large networks. This isbecause we need to collect the communication latency of all the links frequently bybroadcast messages, which leads to extremely heavy communication overheads. Inaddition, delayed information for the latency may create far from optimal routes. In a hugenetwork such as the Internet, it is essentially important for routing algorithms to bescalable. To achieve scalability in adaptive network routing algorithms, it is necessary toobserve communication latency with as few communication overheads as possible.9.3 GAs in Network Resource ManagementBefore introducing our rout ...