Path Recovery Performances

Path Recovery Performances

of Routing Protocols

Chia Hoo Hon

HT023558M

Ng Hian James

HT035267U

Abstract

This is the report for the project worked on by two students for the module CS5224: High Speed Networks and Multimedia Networking. In this project, the two general routing protocols, link state routing and distance vector routing, are being investigated for their path recovery performances due to link failures. By running simulations using the NS2 simulator, it can be deduced that link state routing is a better routing protocol than distance vector routing when it comes to throughput and delay but it also incurs a higher overhead for the total number of data transmitted. However, when there are anincreasing number of failed links, distance vector routing is better with smaller increases of overheads and delay.

1. Introduction

In the world of computer networks, every node is important in having the task of relaying data packets from one end-point to another end-point. The source end-point will send its data packets to the nearest router node that is closer to the destination end-point, if the source cannot reach the destination directly. The router node will forward the data packets to the next router one step closer to the destination, which will in turn do the same. Eventually, the router node that is connected to the destination end-point will receive the data packets and forward them to the destination. Depending on the routing protocol being deployed, a set of router nodes is selected to make up the path which the data packets will travel in.

Like all hardware, routers are not infallible. A router may not be functioning due to power failures (blackouts), damages to internal hardware (circuitry), system malfunctions, or software errors (in the case of a first generation router with a general CPU and OS). A backup router is usually available for switchovers for each node in critical networks but for regular networks, no backup router is, more often than not, available. In the absence of one, a new relay path, or at least a sub-path bypassing the failed router, has to be created. This is called path recovery. The efficiency of path recovery depends on the routing protocol employed in the network concerned.

In this project, we are investigatingthe two general routing protocols: link state routing and distance vector routing. We have obtained sufficient results for the comparison, evaluationand analysis on the performance of link state routing and distance vector routing in the presence of link failure(s) through simulation. We hope that our simulation can help to answer the question about which routing protocol is better in dealing with link failures, both small and big numbers of them.

The rest of the paper is organized as follows: Section 2 gives a brief overview of the routing protocols we are looking into. Section 3 describes our simulation and Section 4 contains our analysis of the results obtained. In Section 5 we provide a conclusion on our findings.

1. Routing Protocols

Routing is the process of finding a path from a source to every destination in the network. It is accomplished by means of routing protocols that establish mutually consistent routing tables in every router in the network. A routing table contains at least two columns: the first is the address of a destination endpoint or a destination network, and the second is the address of the network element that is the next hop in the “best” path to this destination. In a network, links and routers are unreliable, alternative paths are scarce, and traffic patterns can change unpredictably. It is not surprising that routing follows a different path. The two fundamental routing algorithms in packet-switched networks are distance-vector and link-state.[1]

1. LinkState Routing

The notion of linkstate routing was first introduced and deployed on the Arpanet back in the late 1970s.[2]Subsequent revisions and improvements to the basic function now give network engineers a choice of link state routing protocols to deploy.Two such protocols that have emerged as the preferred choices are the Open Shortest Path First and its close cousin, Intermediate System to Intermediate System (IS-IS).[3]

In link state routing, a router knows the entire network topology (or at least a partial map of the network) and is able to compute the shortest path by itself. These are possible because of link state packets (LSPs, figure 1), which are controllably flooded throughout the network and stored in the routers’ topology databases.A LSP contains information regarding a router’s neighbors. Whenever a router receives a LSP, it will check the LSP with the entries in its database. If the LSP is found to be new, the router then forwards it to every interface other than the incoming one. It will reach all routers that are connected to this one and will be forwarded to other routers in the similar fashion.The Dijkstra algorithm is then used to calculate routes which are belongs to the shortest paths.

In the event of a router failure, information is passed to other routers with the use of HELLO packets. With the rest of the routers knowing about the failed router, an alternative sub-path around the failed router can be found.

Figure 1: Link-state packets. Each router participating in link-state routing creates and distributes a set of link-state packets that contain the router’s cost to reach each neighbor.[1]

1. Distance Vector Routing

This type of routing protocol requires that each router simply inform its neighbors of its routing table. For each network path, the receiving routers pick the neighbor advertising the lowest cost, then add this entry into its routing table for re-advertisement.[4]One such common protocol that has been widely used is known as Routing Information Protocol (RIP).

In distance vector routing, a router tells its neighbors its best idea of distance to every other router in the network. It does this by sending and receiving distance vectors to and from its neighbors. Upon receiving such distance vectors, a router then updates its notion of best path to each destination, and the next hop for this destination (figure 2). This is in a way like having each router casting its entire routing table to its neighbors. This mode of getting routes is known as the Distributed Asynchronous Bellman-Ford algorithm.

Routers detect router failures with the exchange of periodic “Hello” or distance vector messages. In the event of a router failure, path recovery is done by the routers around the failed one. Since all routers know the routing tables of their neighbors, the neighbors of the failed router can always find an alternative path linking the routers that the failed one would have used.

Figure 2: Distance-vector algorithm at node A. A receives a distance vector from its neighbor B. It uses this information to find that it can reach nodes C and D at a lower cost. It therefore updates its own distance vector and chooses B as its next hop to C and D.[1]

1. LinkState vs. Distance Vector

Both protocols are evenly matched and widely used. While link state algorithms send small updates everywhere, distance vector algorithms send larger updates only to neighboring routers. Because they converge more quickly, link-state algorithms are somewhat less prone to routing loops than distance vector algorithms. On the other hand, linkstate algorithms require more CPU power and memory than distance vector algorithms. Link-state algorithms, therefore, can be more expensive to implement and support. Link-state protocols are generally more scalable than distance vector protocols.[5]

1. Coping with Link Failures

When links are subject to failure, the problem in routing, which is the transfer of control information from points in the network where it is collected to other points where it is needed, becomes very challenging. Getting routing information reliably to the places where it is needed in the presence of potential link failures involves some difficulties. These difficulties also arise in the context of broadcasting information related to the congestion status of each link.

As it is impossible to for every node to know the correct network topology at all times, an algorithm for broadcasting routing information must at least can cope successfully with any finite number of topological changes within finite time. As the network will not always remain connected, a topology update algorithm working with some protocol for bringing up links should be capable of starting up the network from a state where all links are down. Hence there is the development of basic algorithms that broadcast routing information resulting in the flooding algorithm using sequence numbers, the flooding algorithm without periodic updates, and the broadcast algorithm without sequence numbers.[6]

1. Simulation

In our simulations, we are using a 41-node network topology(figure 3) with uni-cast routing to test both Distance Vector and LinkState routing. The application protocol we used is the File Transfer Protocol (FTP) which sends data from the following source nodes to the following destination nodes:

We will be testing the 2 routing protocols based on 2 scenarios. For Scenario 1 (figure 4), the following set of links will be down from time 5 sec onwards and then up from 7 sec:

For Scenario 2 (figure 5), there will be links that will be down, and is a further extension from Scenario 1. Like Scenario 1, the following set of links will be down from time 5 sec onwards and up from time 7 sec. However, before the following first set of links is up, a second set of links will be down from 6 sec and up from 9 sec.

For both scenarios, the FTP applications will start at 0.1 sec and stop at 10 sec. Both simulations will stop at 10.5 sec.

Figure 3: The original network topology

Figure 4: Scenario 1 network topology

Figure 5: Scenario 2 network topology

1. Analysis

Results of the simulations are obtained from data in the form of traces contained in trace files. We are interested in the performances of the two routing protocols in doing path recovery. This translated to reading the trace files for information regarding the amount of bytes and delay occurred for reestablishing paths. We did step-by-step analysis of what the information we wanted and can be extracted from the trace files. Once we had settled on the information we wanted and the methods of extracting them from the data, a Java™ program with the appropriate data extraction methods is written to parse the trace files for link state routing and distance vector routing.

Firstly, we are able to extract information about how much data has been passing around the network within the simulated time under link state routing (LSR) or distance vector routing (DVR). To do this, we start by keeping counts on the number of packets and bytes passing through the network. The results are given in table 1 and from them we can notice thatwithin the same simulated time, DVR transmitted less packets and bytes in the network than LSR for all three scenarios.

However, such results are insufficient for us to give a conclusive deduction of the performances of the routing protocols. The smaller number of packets used in DVR does not necessary mean that it was efficient in having less message exchanges between for setting or recovering routes. Similarly, the bigger number of bytes transmitted in LSR does not necessary mean that it was better in data transmission.

Nonetheless, one observation can be drawn from the results and that is both the routing protocols saw an increase in the number of packets and bytes transmitted when there were link failures. There is also a trend that more packets and bytes were transmitted as more links failed. The increase is also about 28-58% lesser for DVR than for LSR. This implies that DVR responds better than LSR in the face of link failures by incurring fewer overheads.

Since the results obtained so far are not conclusive, we need to parse the trace files again to capture other data. For better analysis, we would need to know the throughput and delay of only the FTP data packets the routing protocols provide under the different scenarios. Therefore we modified the Java™ program to allow the capturing of data pertaining to packet type, throughput and delay when the trace files are parsed in.The statistics for the FTP data packets is given in table 2 while the results of the throughput and delay are discussed in the following subsections.

Table 1(a): Total number of packets

Table 1(b): Total number of bytes

Table 2(a): Number of FTP packets

Table 2(b): Number of FTP bytes

Looking at the statistics for the FTP data packets given, it can be seen that both routing protocols transmitted the same amount of packets and bytes despite the different numbers of link failures. However, comparing the protocols against each other, we can see that LSR was able to transmit more data than DVRwithin the simulated time across all three scenarios.

If we compare table 1 against table 2, we can observe that there were more additional data packets transmitted using LSR than DVR. This implies that LSR incurred a higher overhead for setting up the routes as the additional data clearly belongs to the messages passed between the network nodes. We can further deduce from the results that the overhead increased more for LSR when more links failed.

1. Throughput

To record the throughput of the routing protocols, we kept track of the number of packets and bytes arriving at the destination nodes. This is simple to implement as we already defined the destination nodes (38, 39, 40, and 41) in the network setup. The results of this round of data capture and information extraction are given in table 3.

Table 3(a): Number of FTP packets

Table 3(b): Number of FTP bytes

From the results we can observe that the throughput of LSR is much greater than the throughput of DVR. Thus we may conclude that LSP is a more efficient routing protocol in terms of transmitting data than DVR.

1. Delay

To record the delay of packets under the different routing protocols is a little harder. We have to make a simplifying assumption that packets received are in the same order as they are sent. This makes it easier for us to keep track of the timings and perform the necessary computations. We are safe to make this assumption because we are looking at the average timing of all the packets transmitted from source to destination. The order of the packets is thus not important. The results obtained are given in table 4.

Table 4: Average delay

From the results we can observe that the average delay of packet transmission is longer for DVR than for LSR. Therefore we may conclude that LSR is a more efficient routing protocol in terms of timing. However, when the number of failed links increased, the average delay for LSR increased more than that of DVR.

Our observations, discussion and analysis so far are summarized graphically in figure 6 and 7. Figure 6 shows the overheads incurred by the two routing protocols. Figure 7 shows the throughputs and average delays of LSR and DVR.

Having provided our analysis, we think it is necessary and prudent to give a brief discussion on the limitation of our project due to time constraint. We should have run a couple of simulations more and run them longer for better results and a more complete analysis. We also cannot rule out completely the possibility of the simulations being flawed. There is no easy way for us to know whether the trace files contained all the path recoveries and that all the data transmissions giving the throughput values are captured correctly. A situation that may arise is that the routing tables of all the nodes affected by the failed links have yet to be updated and data packets for the updates are still in the network. In this way, the timing results will not be accurate.

1. Conclusion

For this project, we have designed simulations to find out the performances of link state routing and distance vector routing when dealing with link failures. The observations we have gotten are that both the routing protocols have their own merits. The link state routing gives a higher throughput and average delay but the distance vector routing gives a smaller number of data overheads and a smaller increase in average delay for more link failures. Therefore we can conclude that distance vector routing be used if the network is highly unstable with link failures occurring frequently and link state routing be used if the network does not change much at all.