Ants and Reinforcement Learning: A Case Study in Routing in Dynamic Networks

1 Introduction

Efficiently routing data in a dynamic network is a diffi­ cult and important problem in computer networking. By dynamic we mean a network subject to frequent and un­ predictable changes in topology a~d link costs ( e:g., due to congestion). One of the most widely used solutiOns for routing on such networks [Coltun, 1989] places substan­ tial space and time requirements on all the routers to guarantee effective performance, thus limiting its. scal­ ability. In this paper, we investigate two algonthms for this problem inspired by the dynamics of how ~nt colonies learn the shortest routes to food sources, usmg very little state and computation [Beckers et a/., 1992]. The first algorithm, which we call the regular ant al­ gorithm, is based on earlier work by Holland et. al. [Schooenderwoerd et a/., 1996] for call routing in tele­ phone networks. The regular ant algorithm is a single shortest path algorithm and is only applicable to net­ works with symmetric path costs. We have developed a second algorithm, called the uniform ant algorithm, which is a natural multi-path routing algorithm that is applicable to data networks with or without path cost symmetry. We provide a summary of theoretical prop­ erties of both ant algorithms as well as an empirical eval­ uation on a low-level network simulator.

A major reliability issue in data networks is the re­ silience of the routing algorithms to corruption of router state. Current routing algorithms are more susceptible to such failures since they maintain more network state at each router. We experimentally demonstrate that the ant-based algorithms are far more resilient. Even though the routing traffic generated by our ant algorithms ex­ ceeds that of existing algorithms, ants can be readily piggybacked onto data packets on a h?p-by-h?P ~asis, since they are small and are of fixed size. This piggy­ backing helps to significantly defray the routing over­ head. Finally, the routing overhead of ant algorithms is independent of the rate of change (link/recoveries and failures and link cost changes) in the network, making these algorithms very attractive for highly dynamic net­ works.

The paper is organized as follows. In Section 2, we describe the routing problem in brief and present two current solutions to it. In Section 3, we describe the two ant algorithms and prove their convergence properties. In Section 4, we present an detailed empirical evaluation of the ant algorithms.

2 The Routing Problem

The challenge of routing in packet-switched communi­ cation network is the need for a fully distributed algo­ rithm that is able, without central coordination to dis­ seminate knowledge about the network, to find shortest paths robustly and efficiently in the face of changing net-

Johnny Chen work topologies as well as changing link costs. There are two major classes of adaptive, distributed packet rout­ ing algorithms in the literature: distance-vector algo­ rithms and link-state algorithms. Distance-vector algo­ rithms are dynamic programming algorithms which only propagate cost information. No node, at any time, has complete knowledge of the topology of the whole net­ work. Link state algorithms require all nodes to know the topology of the network before computing shortest paths. Link state methods have each node periodically broadcast its local topology and costs to the entire net­ work. The Internet Open Shortest First (OSPF) Proto­ col [Coltun, 1989] uses a link state algorithm.

3 Ant Routing Algorithms

To facilitate the description of our algorithms we dis­ tinguish between two types of nodes on the network: hosts and routers. Hosts are communication end-points, that is, they can initiate and terminate data messages 1 . Routers are nodes which forward data messages and can send and receive routing messages. There are three key conceptual ideas underlying our two ant algorithms.

Ants that explore the network: The hosts take a very active role in gathering information about the costs of various paths in the network. Periodically, each host hd in the network generates a message to another randomly chosen host h,. This message is of the form (hd, h, , c) where c is a cost that starts out at zero and is the cost to get to hd. The message is sent out on the network where it is forwarded to h, by routers it encounters, which also increment the cost c to reflect the cost in reverse 2 of links it has traveled on thus far . When the message reaches its destination h,, the cost c is the end-to-end cost of send­ ing a message from hd to h, . The message 3 is destroyed at host h, . These messages are small (size 0(1), 6 to 10 bytes) , and we refer to them as ants. Ants explore paths backward from destination nodes in the network to source nodes. How ants are routed through the network, and the rate at which they are generated (the generation rate is the same for all hosts in the network) are key pa­ rameters in the definition of the ant routing algorithms. Probabilistic routing tables: Unlike link state and distance-vector algorithms which compute determinis­ tic forwarding tables for each router, our forwarding tables are probabilistic. The router r maintains for each destination node x in the network , an entry of the form (x, (Yl ,Pl) , (Y2 ,P2) , ... , (Yn,Pn)), where Vi, (r , y;) is a point-to-point link and 2::7= 1 p; = 1. When r receives a message destined for host x it forwards it to its neigh­ bor y; with probability p;. The probabilistic tables are a mechanism for exploring alternate paths in the net­ work and keeping estimates of their lengths relative to the current best paths.

1 In general, a host represents a network destination for which the ant algorithms compute routes; a destination could be a single computer attached to the network, a subnetwork within an internetwork, or a routing domain within a hierar­ chical routing architecture.

2 When a message traverses a link from node a to node b, c is incremented by the cost of the link from b to a.

3 In fact, we do not require that the message get to h, since h, could be an inaccessible host . Any other host in the net­ work can absorb the message, and the message is destroyed once c increases beyond a pre-set threshold.

Probabilistic updates of routing tables by ants: An ant ( hd, h,, c) generated by host hd to host h, probabilis­ tically updates the routing tables of all the routers it encounters along its path. The update rules are simi­ lar in spirit to those in traditional reinforcement learn­ ing algorithms [Kaelbling et a/. , 1996] ; the key techni­ cal difference is that the update rules are non-linear. If router r receives the ant ( hd, h, , c) on link /; from node y; , it updates c by adding the cost of traversing I; in reverse, and then updates its entry for hd which is (hd , (yl ,Pl) , ... , (yn ,Pn)) as follows :

where !::.p = yfu, k > 0, and f(c) is a non-decreasing function of c.

These update rules are drawn from [Schooenderwoerd et a/., 1996]. The constant k is called the learning rate ofthe algorithm. It is generally less than 0.1. The learn­ ing rate needs to be set high enough that each ant has some effect on Pi, and low enough so we can guarantee convergence of the routing probabilities. Note that the router's probabilities to the host which generated the ant are updated. Ants perform a form of backward learning.

Unlike traditional adaptive algorithms in this context, including [Littman and Boyan, 1994; Kaelbling et a/., 1996] the extent of the reinforcement is not the direct cost c of the ant , rather it is a decreasing non-linear function 4 of c.

A router r forwards the ant ( hd, h,, c) after updating its table as discussed above. It uses the routing probabil­ ities for ant forwarding as follows. Let the routing entry for destination h, be ( h,, (Yl, Pl), ... , (Yn, Pn) . The reg­ ular ant algorithm uses Pr( ant sent to Yi) = Pi and the uniform ant algorithm uses Pr(ant sent to Yi) = ~·

Regular ants use the learned forwarding tables to route ants. If a good, non-congested route is found, new ants will be more likely to be forwarded on that route. Ex­ ploration of less desirable routes is curtailed by this pol­ icy, so eventually the ants converge to a single shortest route . Regular ants require path costs in the network to be symmetric: i.e., the cost of getting from node a to node b has to be the same as the cost of getting from node b to node a.

Uniform ants are unbiased by the forwarding probabil­ ities and explore all paths with equal probability. Uni­ form ants are natural multi-path routers, they increase available bandwidth and are not prone to route oscil­ lation problems that single shortest path routing algorithms have. Uniform ants have a much simpler struc­ ture than regular ants. A uniform ant is of the form (hd, c) where hd is the host that generated it and c, ini­ tialized to zero at the source, is the cost to get to hd on the links it has traveled on so far . Uniform ants have a time to live, after which they are terminated. Uniform ants do not require a destination, a fact of great prac­ tical importance because not every host on the network knows about all the other hosts.

i We normalize actual path costs, so that the f::.p's are not affected by linear scaling of link costs in the network.

3.1 A simple example and its analysis

We present the example in Figure 1 to illustrate the ant algorithms in more detail. We will , in the context of this example, also demonstrate convergence properties of the update rules for both regular and uniform ants.

Figure 1: A simple network with two hosts and two routers. The routing tables for the two routers are also shown. Link 1 has cost C1 and Link 2 has cost C2.

Regular Ants

For regular ants, the probabilities p(t) and q(t) evolve simultaneously according to the coupled stochastic dis­ crete difference equations shown below.

Proposition 1 For regular ants, if C1 < C2 in the net­ work in Figure 1,

':fhe system of equations above form a non-stationary discrete-time Markov chain on the reals. Space consid­ erations prevent us from including the proof which can be found in our technical report [Subramanian et al., 1997]. This proposition can be generalized to any sym­ metric network to show that regular ants will converge to the shortest path 5 .

5 the shortest path is with respect to any specified link cost metric.

Uniform Ants

For uniform ants, the probabilities p(t) and q(t) evolve simultaneously according to the stochastic discrete dif­ ference equations shown below. Note however that the equations for p(t) and q(t) are no longer coupled.

This allows us to establish a convergence theorem much more readily, because p(t) and q(t) are stationary Markov chains over the reals.

Proposition 2 For uniform ants, in the network of Fig­ ure 1,

provided 6.p1 and 6.p2 are positive constants close to 0, and f(c) =c.

Proof: Omitted for lack of space, but is in our technical report . When there are two loop-free, link disjoint paths between any two nodes in a general network, the prob­ abilities p and q on these nodes evolve as shown above with the probability 0.5 replaced by a, where 0 < a < 1. a is determined by network topology and can be in­ terpreted as the ratio of the fraction of ants arriving from one node to the other along the two paths. The limiting values of the probabilities can be shown to be aC2 d (1-a)C, h C d C th aC2+(1-a)c, an ac 2 +( 1-a)c,, w ere 1 an 2 are e end-to-end costs along the two paths. Note that when a = 0.5, uniform ants divide traffic along the two paths in inverse ratio of the path costs; a highly desirable traf­ fic split that can optimize available bandwidth. Further generalizations are in our techreport.

Both Proposition 1 and Proposition 2 are statements of asymptotic convergence; the rates 6 of convergence (which depend on the ant generation rate as well as the topology of the network) are determined empirically in Section 4.

3.2 Improving Adaptiveness

Once the regular ants reach steady state, the forwarding probabilities converge toO's and 1 's as shown in Proposi­ tion 1. If there are topology changes or link cost changes after convergence, the regular ant policy of forwarding ants according to the learned probabilities will prevent them from adapting to the new situation. Uniform ants are immune to this problem because all paths in the net­ work are explored at all times with equal probability. So Table 1: A comparison of resource requirements for the entire network. n is the sum of the number h of hosts in the network and the number r of routers in the network. I is the number of point-to-point links in the network. d is the diameter of the network and e is the average number of links per router.

6 lt is very difficult to obtain general results on convergence rates for these systems of equations.

changes in the network will be detected and the proba­ bilities will adapt at a pace dependent on the learning rate k.

We use the solution in [Schooenderwoerd et a/. , 1996) to allow regular ants to perform a certain degree of ran­ dom exploration. A certain percentage of the time (!%), a router forwards ants uniformly randomly (i.e., using the uniform ant routing policy), and the rest of the time ( 1 - J%) the router forwards ants according to the for­ warding probability tables (i.e., using the regular ant routing policy) . This noise only affects ant forwarding and not the data packets. With f > 0, the probabilities of a single path never reach 0 or 1. This guarantees that if a primary .route becomes no longer available, the up­ date rules remforce the second best paths fairly quickly. Only the ants traveling on the second best path get to reinforce the forwarding probabilities to the source and there are no ants to reinforce the former best path. We summarize this phenomenon by the slogan: bad news travels fast . However, if a better path suddenly becomes available, the only ants available to reinforce it are the ones routed through it by the noise; and so the system takes longer to switch to the better path. We character­ ize this as: good news travels slower than bad news. To make good news travel faster , we can crank up the noise levels or increase the learning rate.

Table 1 summarizes the key resource requirements of the ant family of algorithms, the distance-vector and the link state algorithms. This table makes it clear that the link state algorithm pays a significant overhead in terms of state on each router and in terms of time to compute shortest paths. This investment in state in the routers allo_ws it to reduce the number of routing messages sent durmg the computation of initial routes. The distance­ vector and the ant algorithms have significantly lower router state·, but this comes at the expense of increased routing message traffic. While the distance-vector and ants use roughly the same order of bytes of routing traf­ fic, the ant algorithms use a factor of h (where h is the number of hosts) more messages than the distance-vector ~ethod. I.t is important to note that ant messages, un­ hke the distance-vector messages, are of constant size, and ca.n be piggybacked on to data packets. On high bandwidth networks this virtually gives us ant routing traffic for free.

4 Experimental Results

In this section, we present the results of extensive simula­ t!ons that were performed to evaluate the proposed algo­ nthms, and to compare their behavior with that of the d.istance-vector (~V) and link-state (LS) routing algo­ nthms. The algonthms are evaluated on networks with simple topology, and more realistic topologies derived from a subset of the Internet inter-domain topology.

4.1 Simple Topology

The first, simple network used in our simulations is de­ picted in Figure 3. In this network, all links are of equal unit cost. Thus, for instance, the shortest path from Rl to R5 has cost two 7 . Simulations were run for 60 sec­ onds of simulated time. This time was chosen such that each routing protocol can reach steady state conditions between successive changes in the state of the network. Each host generates ants at a rate of 8/ second. At time t = Os, the network is started with initial conditions. The link connecting R2 and R5 fails at time t = 20s and it recovers at timet = 40s. The learning rate is .OS and the noise level is 10%.

Our first experiment quantifies end-to-end delivery la­ t~ncy, , which is an importan~ aspect of a routing algo­ r~thm s performance as perceived by a network applica­ tion. Figure 3 shows the end-to-end delivery delay, in number of network hops, measured during the simula­ tion described above. Host H1 periodically sends mes­ sages at a rate of 670bytes/ second to Host H5. The figures show the results for regular ants, uniform ants, and ~he distance-vector algorithm respectively. We omit the hnk-state plot because it is identical to the distance­ vector plot . A reported delay of zero hops means that the packet was lost, i.e., it was never delivered to its destination.

To a first approximation , all algorithms achieve the minimal delivery delay of 2 hops during the interval be­ tween t = 20s and t = 40s, and a delay of 3 hops oth­ er~ise. Uniform ants split traffic among multiple paths. This results in some jitter (i.e. , variance in delay) when Table 2: Routing traffic per link per second for Uniform Ant (UA), Regular Ant (RA), Distance Vector (DV), and Link State (LS) algorithms.

7 The link between a host and its associated router is not included in any path cost calculations. This is purely a mat­ ter of implementation convenience. It has no effect on the routing algorithm.

traffic is split over paths with different costs, as can be seen in the graph up to t = 4s and between t = 40 and t = 42s . Traffic is also split between t = 30s and t = 40s, but here the traffic is split over equal cost path, with no impact on jitter. Splitting traffic in this way also leads to an increase in available bandwidth, but this is not evident from the delay plot .

In response to the failure of the shortest path link at t = 20s, packets are lost for a period of three to five seconds, depending on the algorithm used. With the ant algorithms, this time is determined by the transi­ tion time of the forwarding probabilities, caused by the reinforcement of alternate paths.

Table 2 shows the amount of routing traffic generated by each of the algorithms in our simulation. Whenever a routing message traverses one link of the network, one message transmission is recorded, and the size of the message is added to the number of bytes of routing traf­ fic.

In this experiment, the amount of routing traffic gen­ erated by the ant algorithms exceeds that of LS and DV by roughly a factor of 10, both in terms of messages and data. Note, however, that all ant routing messages are small and of fixed size. Therefore, these messages can be piggy-backed onto data packets, substantially defraying their cost to the network. The messages generated by the LS and DV algorithms are larger and not of fixed size; therefore, they do not lend themselves easily to piggy­ backing. In the subsequent section, we will present data that quantifies the dependence of routing traffic on net­ work size and rate of change in the link costs.

Resilience to State Corruption

The next set of experiments attempt to quantify the be­ havior of our routing algorithms in the event of failures. Specifically, we are interested in failure modes where a router's internal state is corrupted. This case is of great practical importance. Router state corruptions can oc­ cur in practice due to intermittent software and hard­ ware faults , and configuration errors. Unlike communi­ cation errors affecting routing messages, such errors are difficult to detect and/or correct. At t = 30s in the simu­ lation, router R2 suffers an intermittent fault that causes its routing state to be overwritten with random values. Since we are interested in evaluating the robustness of the various algorithms, rather than that of their imple­ mentation, the routing state is corrupted with random but plausible values.

With LS, the recovery period is bounded by the peri­ odic link-state broadcast interval. In practice, the broad­ cast interval tends to be quite long, for instance 30 min­ utes in the OSPF protocol. During the recovery period, the router is unable to calculate correct routes, which may result in routing loops and the associated loss of connectivity. With DV, once the router has learned its actual local topology, it will eventually converge to the actual shortest paths after a number of message ex­ changes that is proportional to the diameter of the net­ work, and the range of the path cost metric 8 . In practice, the process can be expected to take time on the order of seconds. During the recovery period, routing loops may exist and cause loss of connectivity.

Figure 4 shows the end-to-end packet delivery delay from H1 to H5. It is evident that both uniform and reg­ ular ants perform extremely well in the event of a router corruption. With uniform ants, only a small number of packets suffer an increased delay of four hops for ap­ proximately 2 seconds following the router failure . No packets are lost with either algorithm. In comparison, with LS and DV protocols, one expects loss of connec­ tivity (packet loss) after the router failure for a period of time ranging from seconds to minutes.

8 A count-to-infinity may occur in a loop of routers involv­ ing the failed router .

4.2 Scalable Topology

The second topology we use for our experimental evalu­ ation more closely reflects the structure of realistic data networks. The topology is based loosely on the Internet inter-domain routing topology. The network is roughly a partial 6-ary tree where one of the six leaf nodes of each parent is connected to one leaf node of the adjacent parent . We use graphs with 3, 4, and 5 levels with a total of 21, 26, and 31 nodes. For each size of the net­ work, we measure the routing traffic generated by each of the algorithms necessary to achieve a given speed of convergence of 5 seconds.

Figure 4 shows the number of routing messages gener­ ated by each algorithm for networks with 21, 26, and 31 nodes, during a 60 second simulation with parameters equal to those used in the earlier simulations. Thus, for realistic wide-area network topologies that are character­ ized by low degrees of connectivity, all these algorithms scale well .

In our final simulation, we measure the generated rout­ ing traffic as a function of the rate of topological change for each of the algorithms. Topological change is mod­ eled here as the number of links that fail and recover over the simulation period of 60 seconds. Figure 5 shows the amount of routing traffic generated by each algorithm in the 5 level network, for various rates of link failures and recoveries. As predicted, the routing traffic gener­ ated by the ant algorithms remains nearly unaffected by the amount of topological change in the network. With link-state and DV, the routing traffic increases more than linearly with the amount of change. This demonstrates one of the key advantages of ant algorithms over LS and DV.

5 Related Work

5.1 Q-Routing and Ants

In Q-Routing [Littman and Boyan, 1994], each node keeps Q-values of the form Qx(d, y), representing node x's cost estimate to d via neighbor y. Whenever x for­ wards data to d, x consults its Q table and forwards to the neighbor with the least cost estimates to d. On receiving a packet from x , neighboring node y immedi­ ately sends its least cost estimate to d back to x. x then adjusts its cost estimate Qx(d, y) based on y's message.

Q-Routing uses a dynamic, i.e. , traffic-dependent, routing metric (delay) . Therefore, it can adapt to changes in topology as well as traffic conditions. Ants, as well as LS and DV, can be made to do the same simply by choosing an appropriate link cost metric 9 ·

Q-Routing differs from regular ants in two key aspects. First, unlike ants, Q-routing is not guaranteed to find the shortest path. Second, the amount ofrouting traffic with Q routing is directly proportional to the amount of data traffic in the network, while routing traffic is constant with ants. Uniform ants have the additional capability of routing packets along multiple paths.

Q routing can discover changes in route cost (delay in this case) only on the currently used route. Since the currently used route is the best known route, only an increase in the cost of the currently used route can cause Q routing to select a different route. A decrease in the cost of a route other than the currently used route cannot be discovered, causing Q routing to potentially use a suboptimal route. The full echo variant of Q routing overcomes this deficiency for the special case where a better route other than the currently used route is known to a neighbor of the message source. Full echo comes at the cost of increased routing traffic, but can still not guarantee convergence to the shortest path. The regular ant algorithm can be shown to always converge to the single shortest path.

To illustrate this point, consider Figure 5, which shows the packet delivery delay for Q-Routing and regular ants in the 6x6 irregular network used in [Littman and Boyan, 1994]. For both algorithms, the routing cost metric is end-to-end delivery delay. At t = 20s, the background network load increases, causing a change in the optimal path between source and destination. At t = 40s, the network is restored to its original load. It is evident that at t = 20s, Q-Routing adapts to increasing load and discovers the new optimal path, but fail to "rediscover" the original path when the background traffic subsides at t = 40s. As a result, the delivery delay never re­ turns to its value before t = 20s. The ant algorithms, on the other hand, is able to converge to the optimal path in both cases. Data packets that are forwarded more than 30 times are considered undeliverable and are shown as having a delivery time of zero. As evident from the graph, a substantial number of packets are not delivered with Q routing during the transition phases following t = Os and t = 20s.

9 For instance, to implement a delay-based metric, neigh­ boring routers can periodically exchange ping-pong messages, and assign the measured delay as the cost of the associated link.

With ant algorithms, the routing traffic is independent of the data traffic. The rate of ant generation deter­ mines a fixed tradeoff between amount of routing traffic and rate of convergence. In Q-Routing, the number of routing messages is directly proportional to the num­ ber of transmitted data messages. This means that at low network load, Q-routing is slow to adapt to network changes. At high network load, Q-Routing overhead in­ creases, thus limiting the aggregate capacity of the net­ work.

5.2 Link-state and Distance-vector Algorithms

Ant routing algorithms differ from LS and DV algo­ rithms in various aspects. Raw ant routing traffic ex­ ceeds that of LS and DV by a small factor, but this must be seen in light of the following facts. First, the absolute amount of routing traffic for a 31 node network is still modest (201 Bytes/sec and 20 msgs/sec of traffic are generated per link) . The small, fixed sized (6 bytes for uniform, 10 bytes for regular) ant messages can be piggy-backed onto data packets on a hop-by-hop basis, which largely defrays their cost to the network. Unlike LS and DV, ant routing traffic does not increase with the rate of change in the network, making these algorithms suitable for highly dynamic networks. Ant algorithms maintain minimal state in the routers, which meets the needs of networks with scarce router resources. Thus they are particularly suitable, for instance, in mobile, wireless networks used for personal communication net­ works where topology and load changes frequently, and where resources in the routers are scarce. Finally, the ant algorithms have additional capabilities (multi-path and improved resilience to router state corruption) not present in LS and DV.