14-12-2012, 01:31 PM
MULTIPLE ROUTING CONFIGURATIONS FOR FAST IP NETWORK RECOVERY
Multiple Routing Configurations for.docx (Size: 267.05 KB / Downloads: 24)
ABSTRACT
As the Internet takes an increasingly central role in our communications infrastructure, the slow convergence of routing protocols after a network failure becomes a growing problem. To assure fast recovery from link and node failures in IP networks, we present a new recovery scheme called Multiple Routing Configurations (MRC). Our proposed scheme guarantees recovery in all single failure scenarios, using a single mechanism to handle both link and node failures, and without knowing the root cause of the failure. MRC is strictly connectionless, and assumes only destination based hop-by-hop forwarding. MRC is based on keeping additional routing information in the routers, and allows packet forwarding to continue on an alternative output link immediately after the detection of a failure. It can be implemented with only minor changes to existing solutions. In this paper we present MRC, and analyze its performance with respect to scalability, backup path lengths, and load distribution after a failure. We also show how an estimate of the traffic demands in the network can be used to improve the distribution of the recovered traffic, and thus reduce the chances of congestion when MRC is used.
INTRODUCTION
In recent years the Internet has been transformed from a
special purpose network to an ubiquitous platform for a wide
range of everyday communication services. The demands on
Internet reliability and availability have increased accordingly.
A disruption of a link in central parts of a network has the potential
to affect hundreds of thousands of phone conversations
or TCP connections, with obvious adverse effects.
The ability to recover from failures has always been a central
design goal in the Internet [1]. IP networks are intrinsically
robust, since IGP routing protocols like OSPF are designed
to update the forwarding information based on the changed
topology after a failure. This re-convergence assumes full
distribution of the new link state to all routers in the network
domain. When the new state information is distributed, each
router individually calculates new valid routing tables.
This network-wide IP re-convergence is a time consuming
process, and a link or node failure is typically followed by a
period of routing instability. During this period, packets may
be dropped due to invalid routes. This phenomenon has been
studied in both IGP [2] and BGP context [3], and has an
adverse effect on real-time applications [4]. Events leading
to a re-convergence have been shown to occur frequently [5].
Much effort has been devoted to optimizing the different
steps of the convergence of IP routing, i.e., detection, dissemination
of information and shortest path calculation, but the
Manuscript received December 21, 2006, revised July 21 2007
All authors are with Simula Research Laboratory, Oslo, Norway
convergence time is still too large for applications with real
time demands [6].
MRC OVERVIEW
MRC is based on building a small set of backup routing
configurations, that are used to route recovered traffic on
alternate paths after a failure. The backup configurations differ
from the normal routing configuration in that link weights
are set so as to avoid routing traffic in certain parts of the
network. We observe that if all links attached to a node are
given sufficiently high link weights, traffic will never be routed
through that node. The failure of that node will then only
affect traffic that is sourced at or destined for the node itself.
Similarly, to exclude a link (or a group of links) from taking
part in the routing, we give it infinite weight. The link can
then fail without any consequences for the traffic.
Our MRC approach is threefold. First, we create a set of
backup configurations, so that every network component is
excluded from packet forwarding in one configuration. Second,
for each configuration, a standard routing algorithm like OSPF
is used to calculate configuration specific shortest paths and
create forwarding tables in each router, based on the configurations.
The use of a standard routing algorithm guarantees
loop-free forwarding within one configuration. Finally, we
design a forwarding process that takes advantage of the backup
configurations to provide fast recovery from a component
failure.
GENERATING BACKUP CONFIGURATIONS
In this section, we will first detail the requirements that must
be put on the backup configurations used in MRC. Then, we
propose an algorithm that can be used to automatically create
such configurations. The algorithm will typically be run once
at the initial start-up of the network, and each time a node or
link is permanently added or removed.
Configurations Structure
MRC configurations are defined by the network topology,
which is the same in all configurations, and the associated
link weights, which differ among configurations. We formally
represent the network topology as a graph G = (N,A), with
a set of nodes N and a set of unidirectional links (arcs) A1. In
order to guarantee single-fault tolerance, the topology graph
G must be bi-connected.
Proposed system
Our proposed scheme guarantees recovery in all single failure scenarios, using a single mechanism to handle both link and node failures, and without knowing the root cause of the failure. MRC is strictly connectionless, and assumes only destination based hop-by-hop forwarding. MRC is based on keeping additional routing information in the routers, and allows packet forwarding to continue on an alternative output link immediately after the detection of a failure. It can be implemented with only minor changes to existing solutions.
We present a new scheme for handling link and node failures in IP networks. Multiple Routing Configurations (MRC) is a proactive and local protection mechanism that allows recovery in the range of milliseconds. MRC allows packet forwarding to continue over preconfigured alternative next-hops immediately after the detection of the failure. Using MRC as a first line of defense against network failures, the normal IP convergence process can be put on hold. This process is then initiated only as a consequence of non-transient failures. Since no global re-routing is performed, fast failure detection mechanisms like fast hellos or hardware alerts can be used to trigger MRC without compromising network stability [8]. MRC guarantees recovery from any single link or node failure, which constitutes a large majority of the failures experienced in a network [7]. MRC makes no assumptions with respect to the root cause of failure, e.g., whether the packet forwarding is disrupted due to a failed link or a failed Router.
Existing System
In the existing system if there is any node failure the router sends the packets from failure node to the source node and then source finds the shortest path to the destination,in our proposed system the failure node finds the shortest path and take the back up of the remaining data and send the packets to the destination. It improves the performance and speed of the transmission. The efficiency is more our project.
In recent years the Internet has been transformed from a special purpose network to a ubiquitous platform for a wide range of everyday communication services. The demands on Internet reliability and availability have increased accordingly. A disruption of a link in central parts of a network has the potential to affect hundreds of thousands of phone conversations or TCP connections, with obvious adverse effects. The ability to recover from failures has always been a central design goal in the Internet [1]. IP networks are intrinsically robust, since IGP routing protocols like OSPF are designed to update the forwarding information based on the changed topology after a failure. This re- convergence assumes full distribution of the new link state to all routers in the network domain. When the new state information is distributed, each router individually
Calculates new valid routing tables.
This network-wide IP re-convergence is a time consuming process, and a link or node failure is typically followed by a period of routing instability. During this period, packets may be dropped due to invalid routes. This phenomenon has been studied in both IGP [2] and BGP context [3], and has an adverse effect on real-time applications [4]. Events leading to a re-convergence have been shown to occur frequently [5]. Much effort has been devoted to optimizing the different steps of the convergence of IP routing, i.e., detection, dissemination of information and shortest path calculation, but the convergence time is still too large for applications with real time demands [6]. A key problem is that since most network failures are short lived [7], too rapid triggering of the re-convergence process can cause route flapping and increased network instability [2].