19 Network Layer: Routing

Prof. Bhushan Trivedi

Introduction

We have looked at services the network layer provides in the previous module. The most important services are routing and forwarding. In this module, we will be looking at what a good routing algorithm requires and also will look at one of the most commonly used algorithms used in IETF standard, called Link State or LS. We start with learning how a routing algorithm adjusts with changes in the network topology. We will also see how a routing table is updated. We will also be looking at some important criteria for a good routing algorithm like dynamism and flexibility, performance, etc. We will also look at router architecture and how it processes each packet. We will end the module with describing the LS algorithm.

Routing algorithms

We mentioned routing many times so far. It is the time to look at routing in detail. Let us look at an example.

Figure 21.1 and 21.3 depicts a case where a typical node D is working and a routing table of a node B. The third entry in the routing table of the node B indicates that for reaching a destination known as I, the next best node is D which is at the second interface. We are now describing a case where D is out of order. Figures 21.2 and 21.4 indicates the difference in the third entry. Now C has replaced D as it is the next router if the packet is to be sent to I. If ever, the D comes back to life, the routing table should again be the same as depicted in 21.3.

The job of routing algorithms to map the network topology into routing tables of individual machines so much so that for every destination, that machine knows the best next neighbor on the optimal path; despite frequent route changes especially when data passes through congested networks. The routing algorithms remain transparent to users in a way that except variable delay, there is nothing else which user can see. How to achieve that is the concern of this module.

We will begin with the list of characteristics of a good routing as well as forwarding algorithm.

Forwarding algorithms work hand in hand with routing so we prefer to discuss them together.

An optimized routing and a forwarding algorithm

A router receives packets continuously and needs to process them at very fast speed. For example, one typical type of a CISCO serious router, called CRS-3 multi-chassis version, can process data as 322 Terabits/second. The packets should be processed at least as fast as they arrive or even faster to make sure the router does not become the bottleneck in the performance of the network. To work at such a speed, the forwarding algorithm must be able to function at very high speed and must be simple enough to be embedded in hardware. Also, they need to work using parallel modules etc. to improve the speed of processing. It must be impartial to all members of the network and also fault tolerant to continue functioning despite nodes and lines failing and coming up continuously. The changes in the routes should not be so oscillating to the extent that they hinder the forwarding process. Most of these requirements (like speed) are self-evident but other requirements need some explanation. Let us list the required characteristics of the routing and forwarding algorithms and describe the details.

Dynamic and flexible

The routing algorithm should be both, adapt to the changing requirements of the user and flexible enough to continue function in different circumstances. In fact, two different types of algorithms are needed. One type, which is inter-AS, needs policy based routing. For example, consider policies like data originating from South Korea to the US should not pass through North Korea. A data originating from an AirTel customer should not pass through AS from Reliance, etc. The routing algorithm must be able to route in such a way that such policies are obeyed in the routing process. Unlike that, the routing process within the AS only needs to confirm best possible live path before choosing the next node. However, the dynamic network situation needs to be considered and the algorithm must adapt to the network changes before making those decisions. Good algorithms continuously monitor the status of the surrounding and exchange that information with neighboring routers to learn about updates and act accordingly. When a number of routers are very large in number, another method called hierarchical routing is used. The router only stores local addresses in the routing table, for faraway addresses, only one of the entire group is entered in the routing table. The routing algorithm needs to be dynamic and flexible to manage all these issues.

Performance

As we have seen in the example of CRS-3, forwarding algorithms need to be lightning fast to accommodate the amount of inflow that is coming in. Quite surprisingly, the algorithms are not always implemented as algorithms. As far as possible, they are implemented in form of some formula so the decision can be taken instantaneously. Whenever we discuss two important jobs of the router and state that they are routing as well as forwarding, most of us, at the first glance understand that the routing is more complicated as compared to forwarding. In actual sense, it is exactly opposite. Why? Because routing can be done after a few seconds, and if delayed, the performance is not directly and immediately affected. The forwarding, on the contrary, must be done in real time and the instant job must be done.

To complete the forwarding process in time, routers play many clever tricks. Most high-end routers have a lot of hardware to process many packets in parallel and have devised a lot of optimized methods to implement these network algorithms. This module does not explore this topic further. An excellent resource on this is a book by prof. George Varghese, Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices (The Morgan Kaufmann Series in Networking).

Let us explore some generic issues in router’s performance, which tells upon the performance of the entire network; forwarding algorithms in particular.

There are two important demands a router designer must be able to respond to. First, the router should scale up to the size of the network at least to some reasonable extent as well as the change in traffic patterns and volume of traffic. Networks grow and shrink as per the demands of the organizations they are attached to.

The second issue is about providing quality of service (QoS). Speed (which is also known as delay) is just one aspect of it. There are many other issues, like delay tolerance (the packets must not be delayed beyond a point), bandwidth (provide specific bandwidth dedicated to a specific connection, for example, less for a 2G connection and more for a 3G connection) are many other issues to be addressed. The routing algorithms that we discuss in this and subsequent modules do not do that job completely. SDN (Software Defined Networks) that we study in modules 31,32 and 33) will discuss that issue at length. Such issues are more serious for real-time applications like VOIP calls, video conferencing etc.

The ISPs also need typical performance measures to be carried out based on different customers and the packages that they have selected and their typical applications. A customer who has opted for a high-end package must be provided better services as compared to customers who have opted for a low-end package. Different companies enter into different service MOUs with ISPs and demand special types of services (including routing). The routing algorithms must be able to honor any such MOUs. As the routing algorithms that conventional routers are using are not capable of handling these issues, another scheme called MPLS (Multi-Protocol Label Switching) is deployed. We will also look at MPLS in module 23.

Routers also have redundant components for managing failover. When a typical component starts malfunctioning, another component can take its place in a transparent way. Sometimes routers come equipped with high availability solutions which even include redundant hard disks and processors etc. So even with hard disk or processor fails the routers keep on running. Sometimes even spare routers are kept and they remain in continuous sync with the working routers. As soon as the main router goes out of order, the spare router takes charge automatically, without any user learning about it. This level of performance demand routing algorithms which can switch over to communicate with a spare router in no time.

Router architecture

Routers route using three steps depicted in the figure 21.5. When a packet enters the router, it is processed in three steps depicted in figure 21.6. A generic and simplified architecture of the router is depicted in the figure 21.7.

Let us, first of all, understand the functions of the router. Kindly consider the figure 21.7. For simplicity, we have divided ports into input and output ports. The incoming packets arrive at input ports based on how they are connected. When they arrive at the input port, the first job performed by the router is to extract the destination address from the packet. Every input port contains a copy of the routing table and the next job is to lookup in the routing table and decides the outgoing port. The movement of the packet to right output port is managed by switching logic. Once the packet arrives at the output port, it is dispatched immediately if the port is free. If it is not, it is queued there and sent as soon as the line is free. The figure 21.7 displays both input and output ports separately but in the true sense, every port is both an input port as well as an output port. Both functionalities, choosing the right path and thus right output port for each incoming packet and queuing and sending outgoing packets is to be carried out at each port. Normally, each port contains two different paths for incoming and outgoing packets so our simple figure is not outright incorrect. One can simplify the presentation by dividing every port into two parts, input and output logically in the fashion we depicted. The content of the figure 21.6 may now be clear. Let us look at each of the operations in little more detail. Let us begin with the lookup process.

The lookup process begins when the IP address is extracted from the packet and is made available to the process. Lookup process is responsible for looking at the copy of the routing table and determine the outgoing line (and thus the port connected to it). Look at figure 21.8. a typical routing table is depicted there. The table contains the leftmost column as a partial address. These addresses may be of any length and thus IPv4 or IPv6 both addresses can be handled, as long as their prefixes are different. The prefixes help in shortening the length of the routing table as a single entry match with many addresses. For example, in above table, the entry 1010* indicates any address begins with 1010. The routing table entry indicates that any address which begins with 1010 should be sent over to R1. And for that, it should be forwarded to port 1.

The first instruction (forwarded to R1) is critical for constructing the frame for the next network and second is useful for the switching fabric to move the packet there. Another reason for truncation of entries is to make sure the entries are reduced to the size of a number of interfaces. Suppose a router has three interfaces, any input packet must go to any one of the three interfaces. If the entries are more than three, more than one entry point to the same interface. If entries are reduced to three, that is the best. Thus the entries have addresses truncated to the level that it divides the number of addresses into three groups, each group is represented by one such entry.

Input packet processing is depicted in 21.9. If the input packet contains some error, it is dropped and an ICMP (Internet Control Message Protocol) error packet is sent to the sender. The bottom line is, the packet must be processed as fast as possible, lesser the entries, faster the processing. Handling error also consumes some part of the processing time.

Switching is the next phase of processing. If input and output ports are directly connected, that process can be extremely fast. However, if there are n input and m output ports, such a mechanism needs n X m interconnections. More interconnections mean more hardware and more money. High-end routers try to reach to that level by using more hardware.

The third phase is queueing of packets at an output port. If all input ports and output ports work at the same speed, and the packets coming in are going out to each output port with equal probability, no output port receives more than one packet at any given point of time. The input, however, is hardly distributed in that fashion. The output ports are chosen, for example, based on user’s choice of websites they want to access. For example, if a 10th or 12th result is announced, the port (thus the line) connecting to the board’s website is busier than others. In that case, when more than one packets are competing for the outgoing line, the output ports must buffer the remaining packets and thus the capacity of the output port determines if the packets are dropped or not.

Apart from the three operations discussed above, routers must also process the packets, calculate the checksum to figure out whether the contents are altered in transit, take part in the routing process and update the current routing table every few seconds or minutes, process ICMP (Internet Control and Message Protocol) packets, IGMP (Internet Group Management Protocol, a protocol used to manage transmission to the groups of users) and also SNMP (Simple Network Management Protocol) packets. Although these tasks are not of the same priority as the first three tasks that we discussed (lookup, switching, and queuing), they consume router’s time.

A good routing algorithm is one which can help manage all these operations together in a most optimistic way. It may appear as an uphill task, but the actual requirements are much less. Usually, the algorithm has very little impact on the process of lookup, switching, or output queuing. An ideal algorithm is one which does not have any.

Better load balance is another critical requirement of the routing algorithm. Look at the figure 21.10.

There are two different paths between two networks. All conventional algorithms only can use one of the paths but an algorithm which can load balance and use both lines and not one. If only one line is used, the algorithm oscillates between two paths, sometimes one path is considered best and used, while sometimes the other is considered better. Such an oscillation hinders the performance of the routing algorithm.

Now it is the time to look at one of the most used types of routing algorithm, known as Link State or LS algorithm. LS is used in current IETF standard.

Link State Routing

The current IETF (Internet Engineering Task Force) standard is called OSPF (Open Shortest Path First). It is based on LS algorithm which we discuss in the following. Both LS and OSPF are covered in detail in Reference-

2. In this module, we will brief about the LS routing process.

The idea of link state routing can be described in two steps.

1. Collect the information about neighbors; (i.e. directly connected nodes). The information is regarding the metric denoted as the distance for an optimal routing process. The word distance does not mean physical distance but can be any other metric like delay, bandwidth, load etc.

2.The complete information is stored in a packet known as LS packet. Send this LS packet to all other routers of the AS.

Once this process is carried out by all routers, The second phase starts

1. Every router gets information about all neighbors of all other routers of the AS.

2.Compiling all such information helps construct the complete AS topology as a graph including all routers as nodes and arcs as distances between them

3.Generate a spanning tree based on that AS topology graph, based on optimized arc value, for every destination, giving the best path to that destination

4. Once that path is learned, a routing table is generated based on that information.

Both of above phases are periodically repeated and the routing tables are updated.

One advantage of this process is that any node or line failure or coming up can be recorded by all routers in a single cycle. The downside is that the LS packets are broadcasted every few seconds by all routers and consume a large amount of bandwidth. As every AS belongs to a single party, the required bandwidth is normally provided so it is normally not a serious issue.

Let us take an example to understand. Consider a figure 21.11. This is the same network that we have seen before. Let us take this network and learn how LS algorithm handles this network.

The first task is to find neighbors and delay to them. Each router from A to J send Hello packet to each of their neighbors. For each of Hello packet, the receiver sends back the ack. The round trip time is calculated and divided by 2 to get the delay value. If some other parameter is to be used, for example, the load on the line, that is calculated accordingly. Usually, multiple samples are taken for a better estimate. For example, calculation of delay is decided based on multiple RTT observations and taking an average value. If B gets delay values from three of its neighbors, E, D, and A, he will build a link state packet depicted in the figure 21.12. If the round trip times are 10, 12 and 6 microseconds, the delay is considered to be 5,6, and 3 ms. Based on these values a Link State Packet is constructed. The header contains a few fields which are needed in processing this packets by the receiver. The first field is the ID of the sender. Second is a sequence number and third is an interesting field called age. The ID is needed as the receiver must know who the sender is. The sequence number serves another important purpose. A broadcasted packet may reach to any receiver from any direction and in a large network, a node might receive multiple packets from the same sender from various paths.

The sequence number helps the receiver learn which one is latest. If the receiver receives a packet, for example, with sequence number 25, and later get another with value 23 or 24, considers them old and discard. The sender, when sends LS packets, give each one an increasing sequence number. Every receiving node broadcasts the received packet to all neighbors except where it has received. If it has received the LS packet from multiple neighbors, it only sends it to others. All receivers also send ack to correctly received LS packets to all neighbors. This algorithm, that is why, is known as selective flooding, flooding the packets to only selected directions and not all.

The sequence number might change during the transition (mostly due to the malfunctioning memory of intermediary routers) and a new problem emerges. Consider an example. Suppose the sequence number of the packet is 16 and thus the binary number is …0000 1000, and the single bit at position 5 is inverted, making it ….0001 1000 which makes it 48! That means all subsequent LS packets 17.18….48 will be ignored by the receiver. This may not be a big problem. However, in a 32-bit sequence number, if the 32nd bit is inverted the difference it adds is 232, it is about  , which might take many years for others to accept a new packet as valid.

The problem is solved using another field. This field is called age. By default, after every 10 seconds, a new LS packet is sent. In a minute, 6 of such packets are sent. The age field indicates the age of every packet. It begins with the value of 60 (one minute). When the information about LS is received, the Age of the packet is also stored at the receiver and updated every second. When it reaches zero, the entry is purged.

How this solves our problem? Let us try to understand. Every link state packet’s life is now decided to be one minute. If this LS packet has a garbled sequence number, after six more packets, which are received but discarded assuming older, the receiver purges the garbled sequence number entry and now ready to accept a fresh packet, problem solved! Wait a minute! What if the six consecutive packets are lost? The same thing happens and a genuine packet’s entry is discarded! However, modern networks with the state of the art cables in an AS owned by a single party is quite unlikely to happen.

The age field, additionally, is decremented even when the LS packet is moving from sender to the receiver. This will make it work even if the receiver is quite far and at the other end of the network. When the packet is received at the receiver, it probably has the age value 45, or 50 etc. Thus the age field works the same for near and far nodes. There are few other refinements done to improve the processing of LS packets.

   1. All LS packets are acked. They are retransmitted if not acked in time.

2. As long as normal packets are flowing the LS packet is kept to wait, they are only sent when the line is free. So they do not compete with normal data traffic. Thus this algorithm does not affect normal traffic

3. Even when the line is free, packets are sent after a small period to make sure all neighbors who received their own copies also send us those. We only need to flood packets to those who does not send.

Once the packets are received, the construction of routing tables can begin which is quite straight forward.

Consider following LS packets are received from all nodes and received by E. The complete data from all other routers is listed in a table depicted in figure 21.13

E can construct the routing table based on this data. Find out the best route to all members of the network and find the next router on the best route. For that, it has to build the topology. Once the topology is constructed a minimum spanning tree from it and making all least cost paths. Next job is to construct one spanning tree for each router in AS, having that router as the root of it. Once the all the least cost spanning tree is constructed, for each of the routers of the AS being the root, we know their shortest path to every other router of AS. When we construct such a spanning tree where E is the root, we know all the shortest paths to E, from every other node. Such spanning trees are constructed by each of the router (for the same topology that they construct on their own) considering themselves as the root of the tree. Thus, they follow the same shortest route when the distance is same.

Suppose this tree is constructed by K, it now learns that if he wants to send anything to E, the best route is via A. H also constructs a similar spanning tree for E and learns that D is the best neighbor for E and so on. Similar tree for every other neighbor will give K and H best neighbors for every other neighbor. In fact, the same process is also carried out in each and every router to get the same spanning tree for each router of the network and thus they follow the same path for sending it to a specific destination.

Finally, the routing table for E is generated as depicted in the figure 21.16. You can see that the first column describes the network and for each of them we have one of the neighbors acting as next router. In this simplified example, we only have two neighbors so the second column we have a value either B or D. The delay is calculated on the basis of the complete delay for the entire path. The actual routing table contains many other things we have not shown in this example.

Network	Next Router	Delay
A	B	8
B	B	5
D	D	4
K	B	15
H	D	6
G	D	9
J	D	10

Figure 21.16 E’s routing table

Summary

We looked at how routing tables change based on router and lines going down and coming up, why routing algorithms need to be dynamic, flexible and provide performance demanded by users. We have seen how the router look up their routing table when a packet arrives, switching fabric is invited to deliver the packet to the output port and how queuing at the output port is required to forward packets when multiple packets are competing go out from the same port. Link state routing is used in OSPF and has two parts. In the first part, it generates an LS packets and sends them to all members of the network. In the second part, the LS packets collected from all other routers of the network is used to generate the topology of the network, generating a minimum value spanning tree from it and use that for generating a routing table.

References

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