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

Chia sẻ: Tien Van Van | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST

Báo xấu

81
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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) 9 The Genetic Adaptive Routing Algorithm Masaharu Munetomo 9.1 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 status, 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. 9.2 Routing algorithms in the Internet From 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, Ltd
152 Telecommunications Optimization: Heuristic and Adaptive Techniques The Routing Information Protocol (RIP) (Hedrick, 1988) based on the vector-distance algorithm with hop count metric is commonly used even now in small local area networks. The algorithm yields many communication overheads in larger networks because they periodically 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 number of nodes in a network) and the size of a routing table is proportional to n, which means that the total communication overhead for the routing information exchange becomes O(n 3 ). The vector distance algorithm also suffers from its slow convergence because it is necessary for the routing tables to reach all the nodes in the network to obtain the correct distance. To reduce communication overhead, routing algorithms based on link status information such as the SPF (Shortest Path First protocol) send broadcast messages that only contain information on link status. Based on a topological database generated from the collected link status, the algorithm calculates the shortest paths employing Dijkstra’s shortest path algorithm (Dijkstra, 1959) in each node. The SPF broadcasts messages that only contain the nodes’ link status instead of the entire routing table. Therefore, the size of a message that contains link status information becomes O(1) when the degree of nodes is constant such as 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 in larger 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 link failure. It seems easy to collect information on the communication latency of links and calculate routes with minimum delay; however, it is almost impossible in large networks. This is because we need to collect the communication latency of all the links frequently by broadcast messages, which leads to extremely heavy communication overheads. In addition, delayed information for the latency may create far from optimal routes. In a huge network such as the Internet, it is essentially important for routing algorithms to be scalable. To achieve scalability in adaptive network routing algorithms, it is necessary to observe communication latency with as few communication overheads as possible. 9.3 GAs in Network Resource Management Before introducing our routing algorithm by GA, this section gives a brief review of related work concerning the application of GAs to network resource management problems. Since many of the problems are classified into combinatorial optimization problems, they can directly be solved by GAs. For example, an application of GA to network routing in telecommunication networks is proposed in the Handbook of Genetic Algorithms (Davis, 1991) by Cox et al. (1991). The authors solved a constrained optimization problem that allocates link bandwidth to each connection. For another approach, Munakata and Hashier (1993) solved the maximum network flow problem. The objective of this optimization problem is to maximize the network flow based on the global information of the network. These two algorithms cannot be applied directly to routing in packet-switching networks such as the Internet because they are based on circuit-switching networks, in which the
The Genetic Adaptive Routing Algorithm 153 bandwidth of the network is allocated to circuits – connections between nodes (Tanenbaum, 1988). On the other hand, Carse et al. (1995; and Chapter 8) applied a Fuzzy Classifier System (FCS) to a distributed routing algorithm on packet-switching networks in which each packet is routed independently by a routing table. This routing algorithm, however, only decides whether a packet should take a direct route or an indirect route by using a FCS. Therefore, the algorithm cannot be directly applied to actual routing algorithms. 9.4 Overview of the GARA The Genetic Adaptive Routing Algorithm (GARA) is an adaptive routing algorithm that employs genetic operators to create alternative routes in a routing table. It is based on source routing algorithms, which determine the entire route of a packet in its source node. Each node has a routing table containing a set of alternative routes, each of which is created by genetic operators. Each packet selects one of the alternative routes to the destination. The algorithm observes the communication latency of routes frequently used. Network 1 6 0 3 2 Node 4 Routing table Delay Query & Dest. Route Delay Weight Answer 1 (0 1) 100 1.0 4 (0 6 4) 70 0.7 5 (0 3 4) 90 0.3 5 (0 3 5) 100 0.7 Applying (0 3 4 5) 150 0.1 Path Genetic Operators (0 6 4 5) 130 0.2 6 (0 6) 50 1.0 (Only contains routes frequently used) Figure 9.1 Overview of the GARA. Figure 9.1 shows an overview of the GARA. Each node has a routing table that contains routes to destinations. For each destination, a set of alternative routes is assigned. Each route has its weight value (as its fitness) that specifies the probability for the route to be selected from a set of alternative routes. The weight is calculated from the communication latency, observed by sending delay query packets. At the beginning, the routing table is empty. When a packet must be sent to a destination, a default route to the destination is generated by using Dijkstra’s shortest path algorithm based on hop count metric. After a specified number of packets are sent along a route, a packet is sent to observe the
154 Telecommunications Optimization: Heuristic and Adaptive Techniques communication latency of the route. To generate alternative routes, path genetic operators are invoked at a specified probability after every evaluation of weight values. To prevent overflow of a routing table, selection operators are applied to reduce its size. A selection operator deletes a route that has the lowest weight among the routes to a destination. Moreover, another selection operator may be applied; this deletes all the routes to a destination to which the number of packets sent is the smallest among all the destinations in a routing table. The GARA can greatly reduce communication overheads for dynamic observation of network status by limiting the observation to alternative routes frequently used. It can also reduce the possibility of congestion by distributing packets probabilistically among the alternative routes. 9.5 Path Genetic Operators For the GARA, path genetic operators such as path mutation and path crossover are designed to generate alternative routes based on the topological information of the network. The path mutation operator causes a perturbation of a route in order to create an alternative route. The path crossover exchanges sub-routes between a pair of routes. A route (path) is encoded into a list of node IDs from its source node to its destination. For example, a route from node 0 to node 9 is encoded into a list of nodes along the route: (0 12 5 8 2 9). The route is constrained to the network topology; that is, each step of a route must pass through a physical link of the network. 9.5.1 Path Mutation The path mutation generates an alternative route by means of a perturbation. Figure 9.2 shows how to perform this mutation operator. To perform a mutation, first, a node is selected randomly from the original route, which is called a mutation node. Secondly, another node is randomly selected from nodes directly connected to the mutation node. Thirdly, an alternative route is generated by connecting the source node to the selected node and the selected node to the destination employing Dijkstra’s shortest path algorithm. More precisely, the path mutation proceeds according to the following sequence where r is the original route and r′ is its mutated one. 1. A mutation node nm is selected randomly from all nodes along the route r, except its source and destination nodes. 2. Another node nm ′ is selected randomly from neighbors of the mutation node, i.e. nm ′ ∈ ε (nm ). 3. It generates a shortest path r1 from the source node to nm ′, and another shortest path r2 from nm ′ to the destination. 4. If there is no duplication of nodes between r1 and r2 , they are connected to have a mutated route r = r1 + r2 . Otherwise, they are discarded and no mutation is performed.
The Genetic Adaptive Routing Algorithm 155 Original Path nm Mutation r2 r1 n’m Mutated Path Figure 9.2 Path mutation applied to a route. Suppose that the mutation operator is applied to a route r = (0 3 5 6 7 10 12 15). First, we select, for example, a node 7 as a mutation node. Secondly, another node 8, for example, is randomly selected from the neighbors of the mutation node. Thirdly, by Dijkstra’s shortest path algorithm, we connect the source node 0 and the selected node 8 to generate a path r1 =(0 2 4 8). We also connect node 8 and the destination node 15 to generate another path r2 = (8 10 12 15). We finish the mutation by connecting the routes r1 and r2 to eventually have r′ = (0 2 4 8 10 12 15). We do not generate a route r′ if any duplication exists between r1 and r2 . This is because we need to avoid creating any loop in a route that passes through the same nodes twice or more. 9.5.2 Path crossover The path crossover exchanges sub-routes between a pair of routes. To perform the crossover, the pair should have the same source node and destination node. A crossing site of the path crossover operator is selected from nodes contained in both routes. The crossover exchanges sub-routes after the selected crossing site. Figure 9.3 shows an overview of the operator. The crossover operator applied to a pair of routes r1 and r2 proceeds as the following sequence. 1. A set of nodes N c included in both r1 and r2 (excluding source and destination nodes) are selected as potential crossing sites. If N c is an empty set, we do not perform the crossover. 2. A node nc is selected randomly from N c as a crossing site. 3. The crossover is performed by exchanging all nodes after the crossing site nc between r1 and r2 . Suppose that a path crossover is applied to a pair of routes r1 and r2 from node 0 to node 20 as in the following:
156 Telecommunications Optimization: Heuristic and Adaptive Techniques Route r1 Route r2 Potential crossing site Crossing Site Selected crossing site Crossover Route r1 (Changed) Route r2 (Changed) Crossing Site Figure 9.3 Path crossover applied to a pair of routes. r1 = (0 2 3 7 9 11 12 15 17 18 20), r2 = (0 4 5 7 10 11 13 15 16 20). Their potential crossing sites are nodes 7, 11 and 15. When we select, for example, the node 11 as a crossing site, the offspring are generated by exchanging the sub-routes after the crossing site: r1 = (0 2 3 7 9 11 13 15 16 20), r2 = (0 4 5 7 10 11 12 15 17 18 20). When we do not have a common node in a pair of routes, we cannot select a crossing site and we do not perform a crossover. In our earlier work such as Amano et al. (1993) and Murai et al. (1996), in order to perform a crossover even when the pair has no common nodes, we connect crossing sites by calculating the shortest path between them. However, a pair of routes without any similarity is not worth crossing-over, because the operator may generate routes which are too far from their parents for such routes, which may lead to random regenerations of routes.
The Genetic Adaptive Routing Algorithm 157 9.6 Maintaining Routing Tables Table 9.1 shows a routing table used in the GARA. The routing table consists of five entries named destination, route, frequency, delay and weight. For each destination, we have a set of alternative routes. The frequency of a route specifies the number of packets sent to the destination along the route. The delay entry stores the communication latency of packets sent along the route. The weight of a route is calculated by its communication latency, which specifies the probability for the route to be selected when a packet is sent. From a GA’s point of view, the weight corresponds to a fitness value. Table 9.1 A routing table. Destination Route Frequency Delay Weight 2 (1 3 2)* 7232 50 0.7 (1 3 4 2) 2254 60 0.2 (1 3 4 5 2) 1039 70 0.1 6 (1 8 6)* 20983 100 0.4 (1 10 11 6) 34981 105 0.6 8 (1 8)* 30452 40 0.9 (1 7 8) 3083 40 0.1 In the table, routes marked with asterisks are the default routes which are the shortest paths based on hop-count metric. Initially, the routing table is empty. When it becomes necessary to send a packet to a destination, and if there is no route to the destination, a default route is generated by Dijkstra’s algorithm and is inserted to the routing table. After sending a specified number of packets along a route, we send a packet that observes the communication latency of the route. The fitness value is calculated after receiving its answer. After the observation, path genetic operators are applied to the routes at a specified probability to generate alternative routes. 9.7 Fitness Evaluation A weight value (fitness value) of a route specifies the probability for the route to be selected from alternative routes. It is calculated from the communication latency along the routes. To observe delay along the route, a delay query message is issued at a specified interval. Using the delay obtained, we calculate weight values wi using the following equations: 1 / ηi di wi = , where ηi = (9.1) ∑ j ∈S 1/η j ∑ j ∈S d j
158 Telecommunications Optimization: Heuristic and Adaptive Techniques where d i is the delay for route i and S is a set of routes to the same destination. In the above equations, we first normalize the delay values d i by dividing by their total sum to yield ηi . Second, we calculate the reciprocal number of ηi and normalize them to have a weight value. This is because we need to have a larger weight of wi for a smaller delay of d i . Consequently, a route with smaller delay is frequently employed in sending packets. However, note that the selection of routes is a randomized one; routes with longer delay also have a chance to be selected. 9.8 Execution Flow In the GARA, each node executes the same algorithm independently. Figure 9.4 shows a pseudo PASCAL code of the algorithm. Each packet has entries such as type, route and next, where type specifies type of a packet, route entry is the route of the packet, and next indicates next hop in its route. Types of packets are DataPacket (which contains data), DelayRequest (for requesting delay of a link), and DelayAnswer (for answering a DelayRequest packet). DelayRequst and DelayAnswer packets have DelayEntry which records the communication latency of the packets. Every time a packet is created at a node, the node determines a route for the packet based on its routing table. For a packet arriving from another node, if its type is DataPacket, the node simply forwards the packet according to its route. In the initial state, a routing table is empty. If the routing table does not contain a route for the destination of a packet created, a default route is generated by employing Dijkstra’s shortest path algorithm and is inserted to the table. Each time after a specified number of packets are sent along a route, a DelayRequest packet is sent to observe the communication latency along the route. If the packet arrives at the destination, a DelayAnswer packet is sent back. After receiving the answer, the communication latency of the route is obtained by calculating the average amount of time sending a DelayRequest packet and receiving a DelayAnswer packet. After obtaining the delay of a route, weight values of routes are calculated according to equation 9.1. After every evaluation of weights, genetic operators are invoked at a specified probability to create alternative routes in the routing table. If the size of the routing table exceeds a limit, we perform a selection to reduce its size. We have two types of selection operators: local selection is invoked if the number of strings exceeds a limit, and it deletes a route with the smallest weight among routes with the same destination; and global selection is invoked when the number of destinations in the routing table exceeds a limit, and it deletes all the routes to a destination of which frequencies of sending packets is the smallest among all destinations in the routing table. 9.9 Empirical Results To evaluate routing algorithms, it is important to perform experiments for networks large enough. In the following experiments, also discussed in Munetomo et al. (1998a), a sample network with 20 nodes is employed (Figure 9.5). The bandwidth of a link is represented by its thickness. The thicker link is for the link with 4.5 Mbps, and the thinner one has bandwidth of 1.5 Mbps.
The Genetic Adaptive Routing Algorithm 159 begin Initialize routing table; while not terminated do begin wait for a packet to be received or input from user; if packet.type = DataPacket then begin if the packet is sent from other node then begin if packet.destination = this node ID then receive packet; else send the packet to the node of packet.next; end else (* if the packet is input from user at the node *) begin if routing table for the destination is empty then begin create a default route by using Dijkstra’s algorithm; add the default route to the routing table; reset frequency entry of the default route; packet.route := default route; if the number of destination > limit then delete routes of a destination least frequently used; end else begin select a route from the routing table by roulette wheel selection; increment frequency entry of the selected route; packet.route := the selected route; if route.frequency mod EvaluationInterval = 0 then begin packet.type := DelayRequest; packet.route := route; send the packet according to the route; end end end end if packet.type = DelayRequest then begin packet.DelayEntry := CurrentTime – packet.CreateTime; packet.CreateTime := CurrentTime; packet.type := DelayAnswer; send packet to its source; end; if packet.type = DelayAnswer then begin packet.DelayEntry := packet.DelayEntry + CurrentTime – packet.CreateTime; packet.delay_entry := packet.DelayEntry/2; change delay of the route based on packet.DelayEntry; if random < Pmutation then begin apply a mutation to a route in the routing table; add the string created to the routing table; if table_size > limit then delete a string of the lowest weight; end if random < Pcrossover then begin apply a crossover to a pair of route in the routing table; add the string created to the routing table; if table_size > limit then delete a string of the lowest weight; end end; end end. Figure 9.4 Pseudo PASCAL code for the GARA.
160 Telecommunications Optimization: Heuristic and Adaptive Techniques 0 4.5 M 1.5 M 1 2 3 10 4 5 14 16 7 6 8 15 12 11 17 9 13 19 18 Figure 9.5 A sample network for the experiment. We compare the GARA with conventional routing algorithms under the following conditions: at each node in the network, data packets are randomly generated at a specified interval that is exponentially distributed. The destination of a packet is randomly selected from nodes that are represented by circles with gray inside (see Figure 9.5). Delay query packets are sent every after 10 data packets are sent. The probability to apply a mutation after an evaluation is 0.1 and that to apply a crossover is 0.05. The maximum population size is 100. We continue the simulation for 3000(s) to obtain the following results. In Figure 9.6, we compare the mean arrival time of data packets for the RIP, for the SPF, for an adaptive version of the SPF, and for the GARA. The adaptive SPF observes communication latency of links to calculate the shortest paths (we set the delay observation interval at 30(s) and 60(s) for the experiments). The mean arrival time indicates the mean value of the time it took to arrive at destinations of packets from their creation on the source nodes. We can change the frequency of generating data packets by changing the mean generation interval of data packets which is exponentially distributed. This figure shows that the mean arrival time of packets is smallest when we employ the GARA algorithm for routing. The SPF is slightly better than the RIP. Adaptive SPFs suffer from communication overhead caused by their frequent observation of the link status of all links, especially when the network is lightly loaded (longer mean generation interval). For a 2000 (ms) interval of creating packets, which leads to heavily loaded links in the network, the GARA achieves about 20% of the mean arrival time compared with those of the RIP and the SPF. This means that packets sent by the GARA arrived at their destinations five times faster than those sent by the other algorithms. In this experiment, the adaptive SPF
The Genetic Adaptive Routing Algorithm 161 with a 30 (s) observation interval becomes the best in a heavily loaded situation; however, in larger networks, the observation of delay of all links in the networks must cause a serious communication overhead. 100000 RIP SPF Mean arrival time (ms) adaptive SPF (60s) 10000 adaptive SPF (30s) GARA 1000 1800 2000 2200 2400 2600 2800 Mean generation interval (ms) Figure 9.6 Mean arrival time of packets. Figure 9.7 shows the number of packets sent by the routing algorithms in the network. For frequent observations, the adaptive SPF needs to send a number of packets. The RIP and the SPF send almost the same number of packets (the size of each packet is different). To reduce the number of packets in the adaptive SPF, it is necessary to increase the observation interval. In this experiment, the adaptive SPF with a 60s interval could reduce
162 Telecommunications Optimization: Heuristic and Adaptive Techniques the number to nearly the same as the RIP and the SPF. However, less frequent observation causes inaccurate observed latency of links, which may not generate the shortest paths. This degrades total arrival time as shown in Figure 9.6. On the other hand, the GARA achieves a smaller arrival time with much lower communication overheads. The number of packets sent becomes less than 20% of those sent for the RIP and the SPF. 80000 adaptive SPF (30s) 70000 60000 The number of packets 50000 SPF RIP 40000 adaptive SPF (60s) 30000 20000 10000 GARA 0 1800 2000 2200 2400 2600 2800 Mean generation interval (ms) Figure 9.7 The number of packets sent by the routing algorithms. To see the communication overheads of the network, Figures 9.8–9.11 display load status of links for the RIP, the SPF, the adaptive SPF and the GARA. The width of each link represents the log-scaled mean queue length for the link.
The Genetic Adaptive Routing Algorithm 163 0 1 2 3 10 4 5 14 16 7 6 8 15 12 11 17 9 13 19 18 Figure 9.8 Load status of links (RIP). In the routing information protocol, a path such as 11 ⇒ 13 ⇒ 18 becomes extremely heavily loaded. On the other hand, a path such as 11 ⇒ 12 ⇒ 15 ⇒ 16 ⇒ 17 ⇒ 18, which is an alternative to 11 ⇒ 13 ⇒ 18, is not frequently used at all; therefore, links for this more roundabout path are lightly loaded. By employing the shortest-path first protocol, we can slightly reduce the load on the links. For the adaptive shortest path first protocol, the majority of the links become heavily loaded because of the frequently broadcast messages to observe the communication latency of all links. On the other hand, the GARA can greatly reduce the load of links, especially on heavily loaded ones. This is not only because the GARA algorithm calculates paths which minimize communication latency with less communication overhead, but also because it distributes packets among alternative paths in the routing table which avoids heavily loaded links. Table 9.2 shows a routing table generated in the node 0 after a simulation run under a 2200 (ms) arrival interval of creating packets. With reference to Table 9.2, we can observe the following points. For a destination node 12, the best route in terms of delay is clearly (0 4 7 11 12). An alternative route (0 4 10 12) is the shortest path from node 0 to node 12 in terms of the hop-count metric, but it is not the path with minimum delay because the links from node 7 to 11 and from node 11 to 12 have more bandwidth than the other links. This result also shows that a load balancing among alternative routes is realized by distributing packets probabilistically based on their weight values.
164 Telecommunications Optimization: Heuristic and Adaptive Techniques 0 1 2 3 10 4 5 14 16 7 6 8 15 12 11 17 9 13 19 18 Figure 9.9 Load status of links (SPF). 0 1 2 3 10 4 5 14 16 7 6 8 15 12 11 17 9 13 19 18 Figure 9.10 Load status of links (adaptive SPF, 30 s interval).
The Genetic Adaptive Routing Algorithm 165 0 1 2 3 10 4 5 14 16 7 6 8 15 12 11 17 9 13 19 18 Figure 9.11 Load status of links (GARA). Table 9.2 The routing table in node 0 generated after the simulation. Destination Route Delay Weight 3 (0 1 3) 554 0.802636 (0 4 2 3) 2253 0.197364 7 (0 4 7) 5052 1.000000 11 (0 4 7 11) 4423 0.533488 (0 1 3 7 11) 5058 0.466512 12 (0 4 7 11 12) 2941 0.564116 (0 4 10 12) 6210 0.267160 (0 1 2 4 10 12) 9833 0.168724 17 (0 4 10 14 16 17) 2 859 1.000000
166 Telecommunications Optimization: Heuristic and Adaptive Techniques 9.10 Conclusions The GARA realizes an effective adaptive routing with less communication overhead by the following mechanisms: • It observes the communication latency of routes frequently used. • It generates an appropriate set of alternative routes employing genetic operators. • It distributes packets among the alternative routes, which realizes a load balancing mechanism among them. Concerning communication overhead of the GARA, only O(kn) messages are necessary to observe the load status of routes, where k is the number of data packets sent from a node and n is the number of nodes. On the other hand, the RIP needs O(n 3 ) communication overhead and the SPF needs at least O(n 2 ) (it depends on the network topology) for the observation. This means that the GARA is a scalable routing algorithm which works much better in a larger size network than the conventional routing algorithms. A possible problem in applying the GARA to the Interior Gateway Protocols (IGPs) will be in its source routing approach. The Internet Protocol (IP) (Black, 1995) has a source routing option, but is not usually employed in the IGPs. Instead, it specifies the next hop for a packet to be forwarded. Obtaining the next hop from the route in the routing table generated by the GARA seems not so difficult, but it may cause some problems such as loops or invalid routes that never reach their destinations. Despite the above problem, the GARA is easily applied to Exterior Gateway Protocols (EGPs) such as the BGP4 (Border Gateway Protocols) which employ source routing mechanisms.