Abstract
Traditional routing protocols schemes allow traffic to pass via the single shortest path. Pre-computing an alternative aims to route the traffic through it when the primary path goes down. A new algorithm schema has been proposed in this paper to find an alternative and disjoint path with primary one by creating a new backup routing table based on adjacent nodes for each node connected with the primary one. The results showing that loss packets, reroute and end to end delay times have been improved between source and destination with avoid loops on the network. The result obtained showed that new schema does not degrade from the network performance by sending an additional messages to create a new backup routing table. The Simulation results (using NS2 simulator) show a comparison between existing link state protocol and the proposed algorithm.
Keywords: component, Link state, ART (Alternative Routing Table), Dijkstra algorithm.
Introduction
Network communication continues to increase and thus the system is required to tolerate large volumes of traffic with respect to huge capacity of links. Network communication is affected by frequent failures and this leads to find an efficient recovery mechanism. In current networks, failure occur frequently, which will affect the stability of the network. When there is a link or node failure, the node that is connected to that failure needs to re-compute their routing table and propagate the up- dates for all nodes concerned with this failure. Recovery mechanism has a motivation that concerns two cases. First, the time required to detect failure. Second, the time to compute a new shortest path takes roughly 70ms. However, the slow convergence time of the routing protocol for the network when failure occurs has inducted to find an optimal solution to carry all traffic to route from an alternative path until the routing protocol update the routing table and re-compute a new shortest path. Alternative Rout- ing Table (ART) algorithm aims to recover the network from failure during short period of time. Precisely, when link or node goes down, it aims to reduce delays and improve throughput in the network. Hence, the pre-computed alternative path can be used when link or node failure on the primary path without waiting for the routing protocol to re-compute a new shortest path[11]. The Open Shortest Path First (OSPF) routing pro-tocol is used as a dynamic link state protocol for TCP/IP or UDP traffic and is designed to update the information for topology by sending a Link State Advertisement (LSA) based on the presence of a failure. The convergence time of the recovery mechanism is still too large for the real application. The convergence time can be of the order of 100′s of millisecond or even 10′s of seconds in the BGP networks. In table 1 indicates to the default and minimum times for the routing protocol to re-compute a new shortest path. Hence, during the process, while the routing protocol is converging micro-loopsmay be created. The affection of this can lead to increase loss of packets and end to end delay in almost applications such as video or VOIP traffic; because the source will keep sending packets until it receives a notification that a failure has occurred. In this paper, we concentrate on the original routing table, which is computed by the Link State Pro- tocol. We propose a new algorithm to create a new backup routing table with excluding all primary paths in the original routing table. The main contribution of this paper is an alternative and full disjoint path computed by using the original routing table, which guarantees that the backup path does not join with any node or link on the primary path between source and destination to avoid loop in the network. The rest of the paper is organised as follows. In Section 2 we will discuss the related work. In Section 3 illustrates the basic concept for our algorithm. In Section 4 explains the mechanism of ART algorithm. In Section 5 explains the result and in Section 6 concludes how we can improve our algorithm and future work.
Related Work
An efficient routing protocol algorithm has been built for achieving robustness and fast convergence within a short time in case of failure. In [5] indicates to classifications of failure. The result shows that 80% of all failures are unplanned. According to that, the 70% of failure effect a single link failure at a time, and the remained effect a shared link risk groups. The protection schema is a proactive mechanism, which calculates backup routes in advance while the restoration schema is reactive by calculating the backup routes when failure has been detected [1,9]. The restoration schema considers more flexibility with regard to the location of failures. The disjoint path between source and destination considers the best solution to recover the network from failure, which is guaranteed to pass the traffic through it to the destination with reduced loss of packets [14]. In[4,3] the author discusses the cost of the links in the network, which is considered to be an important parameter in determining the best path through the routing protocol algorithm. The minimum path cost will be determined by comparing it with other candidate paths. There are two kinds of the Dijkstra algorithms. Firstly, there is a Dijkstra algorithm to compute the best path by removing the links with bandwidths less than the threshold. Secondly, there is an on demand Dijkstra algorithm, which generates the shortest path tree to the pre-computation node[2]. The node will be added to the tree depending on the bandwidth request [15]. In [10,13] the author proposed a new mechanism, termed Failure Insensitive Technique. FIR uses the specific forwarding interface to provide a backup next hop with loop free. The FIR mechanism makes the node, which is connected to the failure to add a new header by re-encapsulating the packets and then re-sending them to the adjacent nodes to inform them about the fault through the interface packets that arrive. Hence, based on the interface packets when failure occurred, the adjacent node will reroute the affected packets and the other nodes will not know about the failure by sending packets according to pre-computed routing tables.
Table 1. Components of the Failure Restoration Time [6]
|
Timer |
Default Value |
Minimum Value |
|
Notification timer |
2s |
10ms |
|
Link state Packet (LSP) generation timer |
50ms |
1ms |
|
Shortest path computation timer |
5.5s |
1ms |
|
Processing phase Typical values |
Processing phase Typical values |
|
|
LSP processing |
lOms/hop |
|
|
SPF computation |
100 – 400 ms |
|
|
Forwarding information update |
20 entries / ms |
|
FIR has many drawbacks as follows: the encapsulation of packets it is not desirable because that will reduce the throughput and make the end-to-end delay longer. In addition, FIR cannot provide protection against node failure. The Internet Protocol Fast Re-Route (IPFRR) is an applicable technique. It includes the LFA, U-turn and not-via address [8,12]. The drawback to the IPFRR technique is that loop free is not guaranteed because the packet can be returned to the source with regard to a specific forwarding pre-computed routing table for each node on the network. In addition, not-via address needs to encapsulate / de-capsulate packet, which affects network performance[7].
Algorithm Overview
The basic idea of ART algorithm by considering a link or node failure on the primary path. In this section,in fig.2 we show the flowchart of ART algorithm used to find the backup path between source and destination. There are four steps for ART algorithm to create a new backup routing table as below:
- First: All nodes on the topology act as source and destination.
- Second: All adjacent nodes will start check if they have a disjoint path to the destination not connected with a primary path.
- Third: the adjacent node will send an acknowledgement to the source if it has a disjoint path or not.
- Fourth: If the neighbour of the adjacent node has a disjoint path then the source node will add the adjacent node as a first backup hop and her neighbours as the second hop in the new routing table.
The OSPF protocol computes the shortest path depending on the cost of the link. The ART algorithm computes a backup routing table based on the original routing table, which is computed by the OSPF protocol to create a new backup one. However, each node on the topology sends a packet to all adjacent nodes not connected to the primary path between the source and destination in the network. This adjacent node will check from the routing table if it has a disjoint path with the primary one to the destination. When the adjacent node has checked the routing table to see if there is any node or link joined to any corresponding ones on the primary path, then it will send an acknowledgement message that informs the source node "I cannot be a backup node in case of failure". Hereafter, when the source node receives a negative acknowledgement, it will then check the other ones it has received from other adjacent nodes. On the other hand, if the source node receives "Yes" then it will add this node to the new routing table as a first next hop in case of failure.
Fig. 1. The primary path and backup path
However, if source node receives an answer from all adjacent nodes that there is no disjoint path to the destination then the source node will send a packet to each one not on the primary path to check whether their neighbours have a disjoint route to the destination or not. Hence, the adjacent node will receive an acknowledgement from its neighbours that inform it if there is a disjoint path to the destination. In this case, if any acknowledgement has a positive answer the adjacent node will send an acknowledgement to the source, "Yes, I have a disjoint path via me and my neighbours". The source node will then add the adjacent node as a first hop and her neighbours as second one in the new backup routing table. Our algorithm will repeat these steps until the backup routing table completed.
For example in fig.1 illustrates how ART algorithm works to create a new backup routing table. The source node will send packets to the adjacent nodes {2 and 3}excluding node 1 because it is the first hop on the primary path. Node 2 will check if there is any disjoint path to the destination node but not via {S, 1, 6, 9} from the routing table. Node 2 will send an acknowledgement to inform the source if it can act as a backup or not. Node 2 cannot be a backup because there is a common node in its path to the destination, which is node 6. Hereafter, the source node will check the other answers from other adjacent nodes. Node 3 will send acknowledgement to the source that, "I have a disjoint path to the destination without any nodes/links joined to the primary path".
Fig. 2. Algorithm Flowchart
When the source node receives this answer, node 3 will add itself into the backup routing table as a first next hop in case of failure. On the other hand, if node {3 and 2} cannot be a backup adjacent node and they do not have a disjoint path with the primary path to the destination, then the source node will send a packet for node {3 and 2}to check if they have an adjacent node that has a disjoint path to the destination. Hence, node 2 will send a packet to node 7 to ask if there is a disjoint path with the primary path to the destination. Node 7 will check the routing table if there is any path available. As we can see in fig. 1 node 7 has a different route to the destination, then node 2 will send an acknowledgement that it can be a backup adjacent node via node 7 to the destination. The source node will add node 2 in the backup routing table as a first and node 7 as a second hop.
Our Proposition
The originality of ART algorithm is how it can find a backup path from the original routing table. The ART will select the backup adjacent node with respect to the original routing table. This will give each node a high possibility to anticipate the second shortest path. However, the second shortest path will actively re-route the packets in case of failure. In addition, when any node on the primary path goes down all links connected to that node will also loss the connectivity.
Algorithm 1. AlternativePath returns a set of alternative paths for every possible path in the routing table.
This will force the routing protocol to take more time to re-converge the network and to re-compute a new routing table. ART algorithm is shown in Algorithm 1. The ART algorithm is a pre-active mechanism (PAM) because it has computed a new routing table including a backup path for all nodes on the topology in advance. However, we assume the source node has at least one adjacent node not connected to the primary path. When the protocol starts to converge along the network, then our technique will begin to operate after the routing protocol builds the routing table for each node on the topology. Depending on the routing table, each node on the topology will send a special packet to enquire from the adjacent node if there is any alternative route to the destination. Hence, ART algorithm will exclude the first next hop for each node with regard to the routing table. Hereafter, when all nodes receive the packets, they will start to check if there is an alternative route to each destination. They will reply by an acknowledgement, which will contain the answer "Yes, I have a different route and I can be a backup node in case failure" or "No, I cannot be a backup adjacent to the destination". When the source node checks the answer and is "Yes" then it will add this node to the new routing table as a backup. If the answer is "No" the source will check the answers from other adjacent nodes. Hereafter, if the answer from all adjacent nodes are "No" then our algorithm will send another packet to ask the adjacent node if it has a node unconnected to the primary path with a disjoint route to the destination (but not via the primary path). If the answer is "Yes" then the adjacent node will send an acknowledgement that contains "Yes, I can be a backup node via my adjacent node". When the source node receives a "Yes" then it will add the adjacent node as a first hop backup and the node that is adjacent to the first hop will add it as a second next hop.
Results
We have used the NS2 simulator to evaluate the ART algorithm. In this experiment, we ran the simulator 50 times with a configured failure randomly between source and destination. Failure can be made to occur instantaneously and at any time. In addition, we configured the source and destination randomly. The duration time for each simulation was 50.0s. We configured the LS protocol to work on this topology. The CBR traffic for all source nodes start sending from 0.5 to 50.0s. During that period, we caused many failures in different links by creating variables [Random /Uniform]. This caused failure to occur arbitrarily. Hence, the links went down haphazardly. Each failure selected the best route, which was computed by the routing algorithm (Dijkstra’s algorithm).
We configured the simulation with respect to these values. In figure 3 (a) shows the average loss packets versus the number of hops to the destination. The traffic will be re-routed along an alternative path, which is computed by our algorithm until the LS protocol updates the information in the routing table and computes the new shortest path.
On the other hand, fig.3 (b) shows throughput in the network when the link state in our algorithm works and improves it. When the failure occurs far from the source, the throughput is reduced because the source node will keep sending traffic until it receives a notification to inform it about any failures. When failure occurs, the source node will wait to receive a notification from other nodes about it and then the routing protocol will start to re-compute and update the routing table.
Fig. 3. Loss Pcakets and Throughput
Fig. 4. Load
In this case, fig.6 (b) shows the rerouting time for the link state with the ART algorithm reduced because the source node will reroute the traffic from the backup path when it receives this notification without waiting for the routing protocol to re-compute and update the routing table. In addition, considerable traffic in the network will make the notification time longer to be received by the source node with regard to the congestion, queue and link delay in the network. In figure 4 shows the load for the link state protocol with the ART algorithm and link state. The load of the link state with the ART algorithm is higher than load by the link state, because our mechanism make all nodes on the topology send a small packets to ask all adjacent nodes if there is any route to the destination disjoint with the primary path.
Fig. 5. The Utilisation of link Exceed in the network topology
Fig. 6. End to End delay and Reroute Time in Sec
Hence, the comparison shows that the ART algorithm does not make a high load that can be degrade from the network performance. Additionally, the load increases when a failure occurs far from the source node by considering a LSA messages that is sent by the link state protocol to update the routing table. On the other hand, in figure 5 shows the utilization of the links on the network. In link state protocols its utilization can exceed the limit size of the links because when a failure occurs a loop occur, which leads to increase loss of packets and degrades the network performance. On the other hand, the link state with an ART algorithm shows a high utilization and avoids exceeding the limit size of the link because the ART algorithm offers a backup path for re-routing packets in case of failure. This will avoid loop in the network. Fig.6 (a)shows the end-to-end delay between source and destination. The delay by our algorithm, in some cases, is better than the link state protocol because our algorithm can select an alternative path, which is both the shortest and the same path for the new routing table. On the other hand, our algorithm, in a different case, will choose an alternative path but not necessarily the shortest one.
Conclusions
This paper presented a new algorithm for computing an alternative path for each source on the network. The ART algorithm invests in the routing table, which is computed by a link state to find an alternative disjoint path to the destination by creating a new backup routing table. Although the ART algorithm gives a recovery path that can be the shortest one, we have shown that backup paths contain a number of hops to the destination. For real traffic, the result shows that our algorithm reduces the loss of packets and delay between source and destination node. Additionally, we have proved that the ART algorithm can avoid loop in the network by keep the utilization stable compared with the link state protocol. The ART algorithm has its own messages that are sent between nodes to create the new shortest path and we have shown these packets do not affect the performance of the network. In the future work, we will make the ART algorithm re-route the traffic from the node that is connected directly with link failure.
