Multiple Routing Configurations For Fast IP Network Recovery

Multiple Routing Configurations For Fast IP Network Recovery

Multiple Routing Configurations For Fast IP

Network Recovery

1M-Tech II Year student, 2 Asst.Prof ,Nimra Institute Of Technology, 3HOD,.Professor .Nimra Institute Of Science & Technology

V.Lakshman narayana1 , Sk.Mastan,M-Tecp , Dr.M.Kishore kumar M-tech, Ph.D.3

AbstractNow A Days Internet plays a major role in day to day communication,if a network gets failed the recovery is becoming a major problem. It takes a much time to re-establish the Link 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 pure connectionless, and assumes only destination based peer-to-peer 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,shortest path discovery, 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.

Index TermsAvailability, computer network reliability, Communication system fault tolerance, communication system routing, protection.

TRANSACTIONS ON NETWORKING Editor J. Yates. First published July 25, 2008; current version published April 15,

2009.

A. Kvalbein and A. F. Hansen are with Simula Research Laboratory, 1367 Lysaker, Norway (e-mail: amundk@simula.no).

1. Cicic´ was with Simula Research Laboratory, 1367 Lysaker, Norway. He is now with Media Network Services, Norway, and also with the Department of Informatics, University of Oslo, 1371 Oslo, Norway.

   The main idea of MRC is to use the network graph and the associated link weights to produce a small set of backup network configurations. The link weights in these backup

   1. Inrecent 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.

      Manuscript received December 21, 2006; revised July 20,

      2007 and February 06, 2008; approved by IEEE/ACM

      configurations are manipulated so that for each link and node failure, and regardless of whether it is a link or node failure,

      the node that detects the failure can safely forward the incoming packets towards the destination on an alternate link. MRC assumes that the network uses shortest path routing and destination based hop-by-hop forwarding.

      The shifting of traffic to links bypassing the failure can lead to congestion and packet loss in parts of the network [9]. This limits the time that the proactive recovery scheme can be used

      to forward traffic before the global routing protocol is informed about the failure, and hence reduces the

      chance that a transient failure can be handled without a full global routing re-convergence

      The rest of this paper is organized as follows. In Section II we describe the basic concepts and functionality of MRC. We then define MRC formally and present an algorithm used to create the needed backup configurations in Section III. In Section IV, we explain how the generated configurations can be used to forward the traffic safely to its destination in case of a failure.We present performance evaluations of the proposed method in Section V. In Section VI, we discuss how we can improve the recovery traffic distribution if we have an estimate of the demands in the network. In Section VII, we discuss related work, and finally we conclude in Section VIII.

   2. 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. 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.

      In our approach, we construct the backup configurations so that for all links and nodes in the network, there is a configuration where that link or node is not used to forward traffic. Thus, for any single link or node failure, there will exist a configuration that will route the traffic to its destination on a path that avoids the failed element. In Section III, we formally describe MRC and how to generate configurations that protect every link and node in a network.

      Using a standard shortest path calculation, each router creates a set of configuration-specific forwarding tables. For simplicity, we say that a packet is forwarded according to a

      configuration, meaning that it is forwarded using the forwarding table calculated based on that configuration. In this paper we talk about building a separate forwarding table for each configuration, but we believe that more efficient solutions can be found in a practical implementation.

      When a router detects that a neighbor can no longer be reached through one of its interfaces, it does not immediately inform the rest of the network about the connectivity failure. Instead, packets that would normally be forwarded over the failed interface are marked as belonging to a backup configuration,and forwarded on an alternative interface towards its destination. The selection of the correct backup configuration and thus also the backup next-hop, is detailed in Section IV.

      If a failure lasts for more than a specified time interval, a normal re-convergence will be triggered. MRC does not interfere with this convergence process, or make it longer than normal. However, MRC gives continuous packet forwarding during the convergence, and hence makes it easier to use mechanisms that prevents micro- loops during convergence, at the cost of longer convergence times [12]. If a failure is deemed permanent, new configurations must be generated based on the altered topology.

   3. 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 atthe initial start-up of the network, and each time a node or link is permanently added or removed.

      Isolated links do not carry any traffic. Restricted links are used to isolate nodes from traffic forwarding. The restricted link weight r must be set to a sufficiently high, finite value to achieve that. Nodes are isolated by assigning at least the restricted link weight to all their attached links. For a node to be reachable, we cannot isolate all links attached to te node in the same configuration. More than one node may be isolated in a configuration. The set of isolated nodes in i is denoted Si and the set of normal (non-isolated) nodes.

      Definition: A node µ N is isolated in Ci if

      With MRC, restricted and isolated links are always attached

      to isolated nodes as given by the following rules. For all links

      (u,v) A,

      This means that a restricted link always connects an isolated node to a non-isolated node. An isolated link either connects an isolated node to a non-isolated node, or it connects two isolated nodes. Importantly, this means that a link is always isolated in the same configuration as at least one of its attached

      nodes. These two rules are required by the MRC forwarding process described in Section IV in order to give correct forwarding without knowing the root cause of failure. When we talk of a backup configuration, we refer to a configuration that adheres to (2) and (3).

      Fig. 1. Left: node 5 is isolated (shaded color) by setting a high weight on all

      its connected links (stapled). Only traffic to and from the isolated node will use

      these restricted links. Right: a configuration where nodes 1, 4 and 5, and the

      links 12, 35 and 45 are isolated (dotted).

      Definition: A configuration Ci is valid if and only if

      We observe that all backup configurations retain a characteristic internal structure, in that all isolated nodes are directly connected to a core of nodes connected by links with normal weights:

      (5)

      A backbone is connected if all nodes in s I are connected by

      paths containing links with normal weights only:

      Definition: A backbone Bi is connected if and only if

      An important invariant in our algorithm for creating backup

      configurations is that the backbone remains connected.

      Since

      all backup configurations must adhere to (2) and (3), we can

      show that a backup configuration with a connected backbone is equivalent to a valid backup configuration:

      In backup configurations, transit traffic is constrained to the

      configuration backbone. A restricted link weight µr In backup configurations, transit traffic is constrained to the configuration backbone. A restricted link weight:

      Proposition 3.2: Let be a node isolated in the valid backup Configuration Ci. Then, restricted link weight value

      link queue is initially empty, but all links in the network will have to pass through it. Method First retrns the first item in the queue, removing it from the queue.

      µr= A. max (9)

      To guarantee recovery after any component failure, every node and every link must be isolated in one backup configuration. Let C={ C1,..Cn} be a set of backup configurations. We say that

      Definition: A set,of backup configurations is complete if

      The algorithm can be implemented either in a network management system, or in the routers. As long as all routers have the same view of the network topology, they will compute the same set of backup configurations.

      Main loop: Initially, n backup configurations are created as copies of the normal configuration. A queue of nodes

      (Qn) and a queue of links (Qa) are initiated. The node queue contains all nodes in an arbitrary sequence. The

      Proposition 4.1: Node selects configuration Ci so that

      N(Pi( , d)) , if d.

      Proof: If d. node selects C() in step 2, and neither node nor link ( , ) will be in the shortest path Pi( , d). If C() = Ci and C()= Ci as in Fig. 3(a), then C( , ) = Ci according to the definition of an isolated node and (2). Forwarding step 2 will select C()= Ci and A(Pi( , )) does not contain ( , ) .

      Fig. 3.

      1. Implementation Issues

      The forwarding process can be implemented in the routing equipment as presented above, requiring the detecting node to know the backup configuration C() for

      each of its neighbors. Node would then perform at most two additional next-hop look-ups in the case of a failure. However, all nodes in the network have full knowledge of the structure of all backup configurations.

      The shifting of traffic from the normal path to a recovery path changes the load distribution in the network, and can in some cases lead to congestion and packet loss. We therefore test the effect our scheme has on the load distribution after a failure. To do this, we have performed simulations of the European COST239 network [22] shown in Fig. 4, designed to connect

      major cities across Europe. All links in the network have

      Fig. 4. The COST239 network.

      equal capacity. To achieve a good load distribution and inimize

      the chances of congestion in the failure-free case, we adopt the link weight optimization heuristic introduced in [23]. They define a piecewise linear cost function that is dependent on the load l (a) on each of the links in the network. is convex and resembles an exponentially growing function. They then introduce a local search heuristic that tries to minimize the value of by

      randomly perturbing the link weights. This local search heuristic has been shown to give performance that is close to the optimal solution that can be achieved by a connection oriented technology like MPLS.

      Backup Path Lengths

      Fig. 6 shows path length distribution of the recovery paths after a node failure. The numbers are based on 100 different synthetic Waxman topologies with 32 nodes and 64 links. All the topologies have unit weight links, in order to focus more on the topological characteristics than on a specific link weight

      configuration. Results for link failures show the same tendency

      and are not presented.

      Fig. 6. Backup path lengths in the case of a node failure.

      Fig. 8. Load on all unidirectional links in the failure free case, after IGP re-convergence, and when MRC is used to recover traffic. Shows each individual links worst case scenario.

      1. RECOVERY LOAD DISTRIBUTION

         MRC recovery is local, and the recovered traffic is routed in a backup configuration from the point of failure to the egress node. This shifting of traffic from the original path to a backup

         path affects the load distribution in the network, and might lead to congestion. If MRC is used for fast recovery, the load distribution in the network during the failure depends on three factors:

         1. The link weight assignment used in the normal Configuration C0,

         2. The structure of the backup configurations, i.e.,

            which links and nodes are isolated in each Ci

            {C1,Cn},

         3. The link weight assignments used in the backbones B1.Bn of the backup configurations.

         The link weights in the normal configuration (a) are important since MRC uses backup configurations only for the traffic affected by the failure, and all non-affected traffic is distributed according to them. The backup configuration structure (b) dictates which links can be used used in the recovery paths for each failure. The backup configuration link weight assignments (c) determine which among the available backup paths are actually used.

         Definition: The potential () of a node is the sum of the

         load on all its incoming and outgoing links:

         Definition: The potential i of a backup configuration Ci is the sum of the potential of all nodes that are isolated in Ci:

         Our modified backup configuration construction method is defined in Algorithm 3. As in Algorithm 1, the input to our algorithm for generating backup configurations is the normal configuration C0 and the number n of backup configurations we want to create. We start our configuration generation algorithm by ordering all nodes with respect to their potential and assigning each node to a tentative backup configuration CT() (line 6 in Algorithm 3), so that the potential i of each backup configuration is approximately equal:

         Fig. 9. Load on all unidirectional links in the COST239 network after the worst case link failure. Top: OptimizedMRC versus complete IGP rerouting. Bottom: Standard versus optimized MRC.

      2. RELATED WORK

MRC operates without knowing the root cause of failure, i.e., whether the forwarding disruption is caused by a node or link failure. This is achieved by using careful link weight assignment according to the rules we have described. The link weight assignment rules also provide basis for the specification of a forwarding procedure that successfully solves the last hop problem. The performance of the algorithm and the forwarding mechanism has been evaluated using simulations. We have shown that MRC scales well: 3 or 4 backup configurations is typically enough to isolate all links and nodes in our test topologies. MRC backup path lengths are comparable to the optimal backup path lengths MRC backup paths are typically zero to two hops longer. MRC thus achieves fast recovery with a very limited performance penalty.

REFERENCES

1. D. D. Clark, The design philosophy of theDARPAinternet protocols, ACM SIGCOMM Comput. Commun. Rev., vol. 18, no. 4, pp. 106114, Aug. 1988.

2. A. Basu and J. G. Riecke, Stability issues in OSPF routing, in Proc. ACM SIGCOMM, San Diego, CA, Aug. 2001, pp. 225236. [3] C. Labovitz, A. Ahuja, A. Bose, and F. Jahanian, Delayed internet routing convergence, IEEE/ACM Trans. Networking, vol. 9, no. 3, pp. 293306, Jun. 2001.

1. C. Boutremans, G. Iannaccone, and C. Diot, Impact of link failures on

   VoIP performance, in Proc. Int. Workshop on Network and Operating System Support for Digital Audio and Video, 2002, pp. 6371.

2. D.Watson, F. Jahanian, and C. Labovitz, Experiences with

   monitoring OSPF on a regional service provider network, in Proc. 23rd Int. Conf.

   Distributed Computing Systems (ICDCS03), Washington, DC, 2003, pp. 204213, IEEE Computer Society.

3. P. Francois, C. Filsfils, J. Evans, and O. Bonaventure, Achieving sub-second IGP convergence in large IP networks, ACM SIGCOMM Comput. Commun. Rev., vol. 35, no. 2, pp. 3544, Jul. 2005.

4. A. Markopoulou, G. Iannaccone, S. Bhattacharyya, C.-N. Chuah, and

   C. Diot, Characterization of failures in an IP backbone network, in

   Proc. IEEE INFOCOM, Mar. 2004, vol. 4, pp. 23072317.

5. S. Nelakuditi, S. Lee, Y. Yu, Z.-L. Zhang, and C.-N. Chuah, Fast local

   rerouting for handling transient link failures, IEEE/ACM Trans. Networking,

   vol. 15, no. 2, pp. 359372, Apr. 2007.

6. S. Iyer, S. Bhattacharyya, N. Taft, and C. Diot, An approach to alleviate

   link overload as observed on an IP backbone, in Proc. IEEE INFOCOM, Mar. 2003, pp. 406416.

7. S. Rai, B. Mukherjee, and O. Deshpande, IP resilience within an autonomous system: Current approaches, challenges, and future directions,

   IEEE Commun. Mag., vol. 43, no. 10, pp. 142149, Oct. 2005.

8. S. Bryant, M. Shand, and S. Previdi, IP fast reroute using not-via addresses, Internet Draft (work in progress), draft-ietf-rtgwg- ipfrrnotvia-

   addresses-01, Jun. 2007.

9. P. Francois, M. Shand, and O. Bonaventure, Disruption free topology

   reconfiguration in OSPF networks, in Proc. IEEE INFOCOM, Anchorage,

   AK, May 2007, pp. 8997.

10. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA: W. H. Freeman & Co., 1979.

11. P. Psenak, S. Mirtorabi, A. Roy, L. Nguen, and P. Pillay-Esnault, MTOSPF: Multi Topology (MT) routing in OSPF, IETF Internet Draft (work in progress), draft-ietf-ospf-mt-07.txt, Nov. 2006.

12. T. Przygienda, N. Shen, and N. Sheth, M-ISIS: Multi Topology (MT)

    routing in IS-IS, Internet Draft (work in progress), draft-ietf-isis- wgmulti-

    topology-11.txt, Oct. 2005.

13. M. Menth and R. Martin, Network resilience through multi- topology

    routing, in Proc. 5th Int. Workshop on Design of Reliable Communication Networks (DRCN), Oct. 2005, pp. 271277.

14. A. Medina, A. Lakhina, I. Matta, and J. Byers, BRITE: An approach to

    universal topology generation, in Proc. IEEE MASCOTS, Aug. 2001, pp. 346353.

15. B. M. Waxman, Routing of multipoint connections, IEEE J. Sel.

    Areas Commun., vol. 6, no. 9, pp. 16171622, Dec. 1988.

16. T. Bu and D. Towsley, On distinguishing between internet power law

    topology generators, in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 638647.

17. Rocketfuel Topology Mapping. [Online]. Available: http://www.cs. washington.edu