20 Routing in MANets and Exterior Routing

Prof. Bhushan Trivedi

Introduction

In this module, we will look at two important topics to extend our network layer discussion. The first is how the routing process is carried out in MANets and second describes how BGP provides exterior routing. MANet presents many challenges unknown to the wired world as well as the wireless world of Wi-Fi. There are many issues demanding special attention in MANet which we will throw light on. The exterior routing has a policy as the main criteria to route and not the shortest path like interior routing process. We will brief about how BGP tries to handle the complexity of exterior routing between approximately 50,000 Autonomous Systems.

Difference in MANets

Routing algorithms like LS cannot work in wireless MANets as it is quite different than conventional wired networks. Here are some differences.

Nodes act as routers

Unlike normal wired or wireless network, there are no special purpose routers in MANets. As the topology is ad hoc, the nodes themselves have to take the additional burden to routing packets for others. The consequence of this is another problem, these ‘routers’ may switch off or just vanish from the scene without informing others. Such a thing never happens in a conventional wired network.

Topology is not fixed

Any assumption about topology won’t work as the topology continues to change. Unlike conventional wired networks, a neighbor may no longer remain a neighbor after a while. No assumption about the topology can be entertained.

Best path assumptions can be invalidated in no time

Unlike wired networks, where the network changes best paths once in a while, happens continuously in MANets. Conventional methods for building routing tables and maintaining them is out of the question for most MANets.

Power requirements are crucial

Routing tables should also consider power conditions of intermediaries, unlike conventional routing process where the only shortest path is considered. In wired networks, for example. If the best path from X to Z is through Y, we will always choose X-Y-Z as the best path. In the case of MANets, if the battery of Y is dipping, it might not be chosen even if shortest.

Number of security issues

MANets accept nodes from everywhere. Anybody can join MANets including a malicious node. Once it is connected, it can play a host of tricks to compromise the network. Security issues are of paramount importance in MANet routing.

There are many algorithms used for routing in MANets, one of the most used is called Adhoc On-Demand Distance Vector (AODV). Many variants of AODV are used in practice and much more are proposed every day. We will be describing a basic algorithm here.

Ad-hoc On-Demand Distance Vector (AODV)

The AODV works on ad hoc networks, it is a variant of DV (distance vector) but with a difference as the route is decided when the packet is ready to be sent; so, on demand word is also added.

Figure 22.1 the process of routing in MANets using AODV

Here is some description on how AODV works.

In AODV, when a node is interested in sending a packet if follows a process called route discovery. The route discovery finds the shortest path to the destination at the point of sending the packet. Let us take an example to learn about route discovery process.

The AODV algorithm is reactive and not proactive like LS. Consider the network shown in figure 22.1; the nodes are wireless nodes and the links are wireless. When it shows that D is connected to E and not connected to K means that E is in the range of D while K is not.

Let us assume that E has a packet for J, farthest from it. In 22.1(a) broadcasting range of E is shown. That range implies that whenever E broadcasts, this is the area it covers and any node inside that range will receive. Such a range exists for all nodes but not shown. The range indicates that when E broadcasts only B and D can listen. The route discovery process starts with E broadcasts. B and D both responds back positively if they know the location of J. Otherwise, they broadcast the same further and the process continues as shown in 22.1 subsequent figures. Ultimately, the query reaches the destination if nobody knows where the destination is, the very J. In this case, the request comes from multiple neighbors and J responds back to all of them. How do the intermediaries pass the information back? Each receiver remembers the sender. In the case of the first broadcast of E, both B and D remembers E as a sender. The arrow indicates this process. That also means that if the response comes back, this is the path to forward it. In a way, the actual sender, E gets a response from all of its neighbors. How does it learn the best path? When J sends the information back, it initializes the path length value to 0, and all subsequence pass back increments that value by 1. Eventually, when E receives multiple responses, they contain respective path lengths. What E has to choose is to pick up the shortest length path. During the pass back process, the intermediaries can also provide other information like the battery life which helps the sender to decide whether to choose that path or not. However, basic AODV does not have any mechanism for power management.

If you have followed the process depicted in 22.1, you can see that there is a phase where D receives the response from two neighbors. How can it decide what path to forward? Again, it has to look at the path length, if the new path has a shorter length, it will resend the value with an update, if not, it just discards that response. Similarly, when there is a query being sent, D again receive the query from both E itself and then A. When it receives the SAME query from A, it understands it to be a duplicate and does not broadcast if further.

This process eventually gets E the path that it wanted. The dynamic nature of MANet means the path may not remain for long. How does E know? MANet nodes periodically broadcast Hello packets to assess the availability of the neighbors. If the neighbors do not respond back after a few attempts, it is considered moved away and removed from the path. On the other hand, every intermediary sends packets and expects the ack, after a few retries if a packet is not acked, the neighbor is considered to be invalid and removed.

The process of route discovery

The on-demand search of a route is the most important feature of AODV. It is done by sending a packet known as Route Request. Every Route Request contains the structure depicted in 22.21.

Let us learn about each field. The source ID indicates who the sender is. Destination ID, similarly, contains the ID of the node whose path is being searched for. When an old path is invalidated, the sender needs to send a fresh request for the same destination. The new request bears an incremented sequence number. An incremented number indicates a new request. This prevents intermediaries to send an old response back. When an intermediary receives a request with number n, the intermediary remembers the pair (Sender Node, Request No) and thus remembers the latest request from each node. This value helps it to remember the latest request and discard older requests. When the same request number is found again, it can be discarded as a duplicate. Similarly, destination sequence number indicates the sequence number indicating the destination path information it has received for various destinations. Every intermediary must keep this value and thus is aware of the latest response for all destinations that they have ever received information about. For example, when E receives this path related information from J, assuming this is the first time this happened, J provides 1 as destination sequence number in its response. When E sends another request for J when the older path is invalidated, it uses 1 in its request, anybody who has a better path will have a higher value of destination sequence number. If not, eventually J will respond back with a destination sequence number one more than the earlier, in this case, 2. Every node where this information passes through records the value with destination sequence number 2.

The hop count the sender starts with is zero and incremented at each broadcast. When the receiver responds back, the response contains this value which indicates how long the responded path is.

Time to live limits the response to a limit. It is decremented after every broadcast and once reaches zero, that broadcast packet is discarded. The broadcast begins with TTL value as 1 (only look at the neighbors), if no response comes back, TTL value is incremented to 2 (only look at neighbors of neighbors) and so on till the response comes back. Though we have shown TTL here, it is part of IP header. AODV does not store but provides value of TTL to IP for its work.

Maintaining routes

The MANets experience unexpected movement and abrupt switching off of nodes and that is why it becomes difficult for it to keep the correct routing information. Generally, two methods are deployed to check other nodes moving out or switching off. First, is based on hello packet to all the neighbors. Second is a response from the receiver of a normal data packet. If no ack arrives in time a few times, the node is concluded to be moved out.

1 This is a simplified version of an actual packet which contains some other flags etc. Time to Live is actually borrowed from the IP.

Thus neighbors learn about a node being absent. How about others who believe that the node (which is non-existent in the network at this point in time) is reachable through the neighbor who has now learned that it is not available? For example, if G has moved away and D learned about that. Now E believes that G is reachable through D must be informed about that. This is done in the process of route maintenance. Every node remembers who has asked for a whose address and the response that it gave. That means D remembers that E has asked for G and it has responded positively before. Now when G is not present, it must inform E about this update. In this case, E is known as an active neighbor. The information about who has asked for which node is kept in a table and purged over a period of time; thus only storing recent searches and their responses. Here is an example depicted in figure 23.3.

You can see that the information about all destinations and next hop for D is stored in the routing table with an additional column called active neighbors. These are nodes which have recently asked for the path to the node depicted in the entry, the destination. For example, the first entry indicates that G and H have asked for B and this node (whose routing table is this, the

D)  has responded back. So when B goes out, G and H must be informed. This helps in purging all routes that do not work and keep the routing algorithm work in changing conditions.

BGP

We have seen enough of interior protocols (intra-AS). Let us learn a few things about BGP (Border Gateway Protocol), an IETF standard for exterior routing (inter-AS). The BGP routes packets between AS. Unlike the LS or AODV, this algorithm has to work with policies that user demand for routing. We have already seen some policies, here are some more.

1. When a packet from US army is sent, the path should not touch Afghanistan

2. Let all packets pass through Airtel AS but not Reliance or Idea etc.

3. I will forward packets only if you pay me, not otherwise

4.  I will only forward packets who are my subscribers’ and not others

Thus BGP doesn’t bother about the shortest path, it finds a path that complies with the policy and use that path to deliver the packets. Let us try to see how BGP is able to do so.

The BGP divides AS in three different types. Closely observe 22.4. You can see that nodes C and F indicate AS which only have one connection to other AS and rest of them have two or more connections. When an AS has only one connection is called stub and it is a customer’s AS. The second type of AS has more than one connection but do not allow itself for transit network. For example, H in above example has 3 connections but it might not allow any transit traffic, for example, a traffic from D to G, is not allowed to pass through H. This is again a customer who has multiple connections to the Internet. This is done for load sharing as well as fault tolerance generally. The final type also contains two or more connections but they allow transit traffic, based on the fees paid. They are the service providers. It is hard to learn from the figure which AS belongs to the second or third type. The difference between them is just one; their willingness to forward the traffic. The third type usually is carrier companies like Reliance and AirTel etc.

Features of BGP

BGP is by far the most complex protocol for the Internet TCP/IP protocol stack. We will try to brief about its functionality here.

1. The LS algorithm which works so well for interior routing algorithm cannot work here, as currently, a number of AS is approaching 50,000. Sending broadcasts in such a huge network is quite a task. It requires a huge bandwidth for the routing updates only. Storing and retrieving such large amount of data also demands huge processing. Thus, a variant of another algorithm called DV (Distance Vector) is used. Both reference 1 and 2 describe DV in detail.

2. Unlike Interior algorithms, the BGP follows a path vector routing approach. This means it won’t only choose the next node of the path but entire path while routing. There is no autonomy to intermediaries to choose the next node like LS or AODV. There are two reasons, first, it is only possible to judge if the policy is followed, by looking at the entire path. The sender generates entire paths and compares them for policy enforcement abilities and approve only that path which does so. Subsequently, all packets are forwarded on that path only. The second reason is to avoid a problem of loops in the path. When routers autonomously decide the path, they might incorrectly choose the path with a loop. When the entire path is available for inspection, any loops, if exists, can be found out and removed. Thus instead of learning about the next path, a sender gets information about all paths completely and choose the best. This process is known as path vector routing.

3. BGP needs to reflect on business relationships. For example, E and A are connected and both of them are service providers. They may have a business relationship such that If E allows 1 Gb or

A, A should allow 2 Gb of E. Any additional traffic may be charged ₹ 10 for each 1 Gb. Once that business relationship ceased to exist, the BGP should not route the traffic accordingly but on other routes where a new relationship is established. For example, if the new business contract is signed between E and D, BGP may like to favor that transit route. Figure 22.5 lists all features of BGP.

BGP processing

Let us try to understand how BGP routing is carried out. Every AS is given a unique id. At & T has 7018 while Reliance has 32400 as a unique AS ids assigned for example. A router of any AS can communicate using a TCP connection using a special port number 179 to any other AS. These two routers can share a lot of information about both AS, quite similar to LS algorithm but in much larger scale and much more complex manner. The updates are sent in two cases. When a new and better route to a destination is found and when an old working route is no longer available. A path is a sequence of AS numbers, for example, 12 34 56 1026 is a BGP path to AS no. 1026 via AS 12, 34, and 56.

In figure 22.6, AS-11 wants to let others know about its existence so it sends a BGP packet to all of its neighbors, in our case we are only showing it to AS-6. The other neighbor AS-9 also gets the similar message but we do not show that here for simplicity. Now it is the turn of AS-6’s to broadcast this message. When it broadcasts, it adds its own AS number to it. Again we only show one neighbor AS-5. AS-5 follows suit and both AS-4 and AS-7 receives the message and AS-11 finally receives two paths to AS-4 (11 6 5 4) and 11 6 7 4) contending for the best path. Again we ignore other paths. These two paths are compared for policy implementation and the best path chosen provides the best implementation of policy.

A customer may prefer one path over another. For example, if an AS is connected to others by two connections, Connection-1 and connection-2, it is quite possible that the customer only announces connection-1 to the rest of the world and keep connection-2 for some special purpose, may be for R & D or for connecting other branches of the company etc. Sometimes some route announcements coming from specific AS are not trusted as being a mistake or from the suspicious party. They are not forwarded and not considered for processing. The BGP also looks at the willingness of the intermediaries. For example, a customer, lets us call him A, might have two connections to the Internet say using two different ISPs, AirTel and Reliance. Now if an AirTel customer, let us call him customer B, wants to talk to another customer of Reliance, customer C, and the shortest path passes through AS of customer A. Do BGP allow B-A-C path? No. Here the customer has two connections but does not want to act as an intermediary so BGP does not do so.

Another characteristic of the BGP algorithm is known as Hot Potato algorithm. Every AS prefers to route the packet in a way that it spends minimum time in the AS, irrespective of it being the shortest path. Suppose there are two paths, one is actually shorter but spends more time in AS and another one is longer but spends less time in AS. In this case, an entry level router in AS chooses the second path as the AS won’t like additional intermediary traffic. Figure 22.7 shows the case. The path from H to X is better to be sent using H-M-L-Q-P-X but L forwards that to a longer route starting from G, as it is part of another AS, the AS-1. This algorithm is known as hot potato as everybody wants to get their hands off the packet and transfer to somebody else. It is quite possible that a packet may unnecessarily oscillate between different AS and take a much longer time to reach the destination due to this problem.

Another important feature of BGP processing is that BGP routing process also involves internal routing. Closely observe 22.8. The internal routing indicates a critical point. One cannot judge a shorter path only looking at the AS sequence like as shown in figure 22.6. Paths 11 6 5 4 and 11 6 7 4 cannot be compared based on this length. The internal path between two AS actually involves some routers of the AS and the actual length depends on the intermediary routers along the internal path as well. In figure 22.8, when F sends data to X, the path includes four nodes F-G-AS2-X considering AS2 as a single node. It is not really the case, as it turns out, AS2 is a collection of routers and the process of routing includes both interior and exterior routing including internal routers of AS2. If an outsider looks at, the path is simple AS-1-AS2-AS3 which indicates a length 3 and have three hops. The actual path is F-G-L-Q-P-X which is of length 6. Not only the length is different, the interior routing is also different and BGP cannot guarantee any path related optimum solution.

After path selection, the packet is sent on the specified route. The process is more complicated than it looks on the face. The forwarding and internal path selection is a complex and difficult process. Another problem is that BGP is based on the trust model. Any AS provides any information to any AS is to be accepted without any verification. There are issues when a careless AS provides information which is not completely correct. There are cases where AS provides purposefully incorrect information as well. The BGP does not have any control over any AS and is kind of service provided on top of a very untrustworthy model. There are cases of malicious propagation of information which resulted into halting specific Internet services in past.

However, some researchers are working in the direction of making the BGP more secure and not vulnerable to such attacks. Making approximately 50,000 AS work in sync is not a joke and unless all such AS work in a collaborative way, it is hard to provide a better solution. BGP is still evolving and new refinements are suggested, tested and implemented every day.

Hierarchical Routing

The Internet is growing at a rapid pace and number of routes connected to the Internet is growing with that as well. It is not possible for every router to keep information about every other router in the world or even in a large network. There are two problems, first, if all other router’s information is kept the routing table will grow extremely large and impossible to be kept in the memory. The second reason is that even if we can somehow store that information, it would be impossible for a router to process such routing tables in real time for each incoming packets. Another point which we have already made is that the router actually needs only as many entries as a number of interfaces are. There is no point having more entries. We have already looked at the prefix based routing process. Another method to do so is to provide a hierarchical routing. This is a method where a single entry for an entire group is provided in the routing table.

Look at the figure 22.9. R1 only have four entries for four different groups of networks as shown in the figure. Such a mechanism where a single router’s address is kept when a forwarding process needs to forward a packet to a group is known as hierarchical routing.

IPv6 based routing can have two different types of hierarchy, ISP based as well as location based. All networks under a single ISP can be segregated using a single network prefix and a single entry will do. Similarly, networks for specific location also share the same prefix and thus can be kept as a single entry. You can refer to Reference-2 for learning further on how IPv6 enables these two hierarchies.

Sometimes networks demand to send the packet to all nodes, that is known as broadcast routing. Many situations including the LS packet distribution demands this process. There are three different ways to implement this process. The first process is called individual delivery. This process is not exactly sending one packet to one recipient. Figure 22.10 indicates the waste. If 1 has to send a packet to each of the 2 to 5 nodes, it has to send five packets. A better scheme is to send one packet which is just copied by individual recipients before forwarding further.

A little better method is known as flooding. We have looked at flooding before. That process introduces so much overhead that it is also not considered to be a good method. However, flooding is used in many cases like LS broadcasting.

A little better method is known as reverse path forwarding. Any packet, when coming from a network on a specific port is marked as the shortest route to that port. Only when a packet come from that router on that port, it is broadcasted and not otherwise.

A final method is based on finding the shortest path to all other routers and building a spanning tree connecting to a specific node. It takes some time to generate the topology and the spanning tree but once it is constructed, a packet is only sent over those paths and no other path. This is the best solution and employed in many groups related broadcasting by IGMP (Internet Group Management Protocol). Figure 22. 11 shows the shortest path from node A to all other nodes of the network. Once such path is available, a broadcast only travels along these paths and no loops or additional packets traveling on other lines are observed.

Summary

In this module, we have seen how route discovery process in MANet is carried out to provide on-demand routing process. The route maintenance process helps MANets in getting the obsolete routes purged periodically. We have seen how BGP manages organization policies and business relations etc. into policy based path vector routing. Various issues like a hot potato, interior routing needed for exterior routing etc. are also discussed. Finally, we briefed about two important categories to route, hierarchical and broadcast routing.

References

1. Computer Networks by Bhushan Trivedi, Oxford University Press
2. Data Communication and Networking, Bhushan Trivedi, Oxford University Press