Internet Draft Sriganesh Kini Expires : October 2002 Yibin Yang - Mahi Networks May 2002 Traffic restoration in link state protocols using neighbor's shortest path draft-kini-traf-restore-nsp-00.txt Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract Traffic recovery time when a link (or node) fails is typically in the order of tens of seconds for a link state IGP. The recovery time is governed by factors like the time it takes to detect an adjacency down, the time taken to propagate link state database changes throughout the network and the time it takes to run the SPF algorithm and install the new routes in the FIB. Till this entire process is complete, traffic in the network can be blackholed. This draft describes a technique to reduce the time for which traffic is blackholed by routing the traffic through a neighbor's shortest path. Kini, Yang [Page 1] Internet Draft May 2002 1. Introduction Link state protocols like OSPF [1] and ISIS [2][3] are used as IGPs. On a link or node failure the adjacency is torn down, and new link-state is flooded throughout the network. The next SPF computation restores traffic. Some traffic can be lost between the time the link/node going down and the next SPF. This draft describes a technique to reduce loss of traffic. Section 2 clarifies the scope of the draft. Section 3 defines the problem being solved in greater detail. Section 4 and 5 describe what is a neighbor's shortest path (NSP) and how it is computed. Section 6 explains how NSPs should be used in a real architecture. Section 7 provides an example to illustrate the technique. Section 8 provides simulation results to quantify the "goodness" factor of using NSP. 2. Scope This draft describes a technique to limit the loss of traffic when an adjacency goes down. Specifically we do not aim to do the following 1. The hello protocol typically takes tens of seconds to detect adjacency failure. This duration constitutes a significant portion of the entire traffic recovery time. This proposal does NOT aim to provide a faster mechanism to detect adjacency failures. Note : As analyzed in [4] link bandwidth and propagation delay should be taken into account to configure hello intervals. On high speed links hello-interval can be in the sub-second range, resulting in a adjacency failure detection time of the order of a few seconds. 2. This proposal does NOT aim to provide faster link state protocol convergence in the "conventional sense". For example, we do not dictate implementations to prioritize LSP flooding over SPF calculation as in [4]. 3. Problem After a link state protocol adjacency failure is detected, for some time traffic which was being forwarded along that adjacency is lost. This traffic is restored at the next SPF. SPF calculation has traditionally been throttled for a variety of reasons. These include a. SPF is a CPU intensive task. b. A change in the topology can result in several link state updates which can be bunched together into a single SPF instead of doing several SPFs. The throttling mechanism is implemented in several ways, e.g., a. An initial wait period for SPF after receiving a link state update. b. Minimum time before two consecutive SPFs are executed. etc. Kini, Yang [Page 2] Internet Draft May 2002 [4] recommends that there be no throttling. However service providers have deployed it and found it to be useful. In fact [5] analytically proves that reducing throttling will actually reduce the network stability. It is wise to assume that SPF throttling will remain a useful and deployed technique in the future. The flip side of throttling is that traffic will be lost till the next SPF. As throttling is increased to improve network scalability and stability, the duration for which traffic is lost will also increase. This draft describes a technique to limit the loss of traffic even when SPF throttling is applied. 4. Neighbor's shortest path (NSP) Notation: Let NSP(S, D) denote the "Neighbor's Shortest Paths" starting from node S and terminating at node D. Let SP(S, D) denote the set of (equal cost) shortest paths from node S to node D. Definition : NSP(S,D) = for each neighbor N of S edge(S, N) prefixed to each path in SP(N, D) if NONE of the paths in SP(N, D) pass through S. Notation : Let NSP(S, D, N) denote the paths in NSP(S, D) that have next-hop at S as N. Let NSP(S) denote NSP(S, D) for all nodes D (other than S) in a given graph. 5. How to calculate NSP Notation : Let SP-DAG(S) denote the Shortest Path Directed Acyclic Graph rooted at S. Algorithm : First let us calculate NSP(S, D, N) where N is a neighbor of S. Calculate SP-DAG(S) and SP-DAG(N). 1. Nodes downstream of S (including S) in SP-DAG(N) should not be considered. 2. Nodes downstream of N in SP-DAG(S) should not be considered. Kini, Yang [Page 3] Internet Draft May 2002 3. For the remaining nodes prefix edge(S, N) to paths in SP(N, D). This gives NSP(S, D, N). Doing this calculation for all neighbors of node S gives the complete NSP(S). For each path in NSP(S, D) we also record if it passes through any of S's shortest path nexthops. This will help us to restore traffic in case of node failure (Note : Node failure protection is optional). 6. How NSP can be used NSPs computation can be CPU intensive. Since NSPs are pre-calculated the computation can be run in the background. When an adjacency goes down all the FIB entries should be processed. For each prefix the associated NSP (if one exists) should be installed as the new nexthop. There could be some sticky issues here regarding how much time it takes for the forwarding table to be updated, but we are hopeful it can be updated in an order of milliseconds. The NSP nexthop should be replaced when the SPF is completed. The NSP computation for the new topology can be then initiated (in the background). 7. Example +---+ | B | +---+ 5 / \10 / \ +---+ +---+ +---+ +---+ | C |----------| A |----------| F |--------| G | +---+ 10 +---+ 3 +---+ 12 +---+ | | \ / 10| 20| 7 \ /20 | | \ / +---+ 10 +---+ +---+ | E |----------| D | | H | +---+ +---+ +---+ Figure 1. A sample topology to illustrate NSP 73 % of source-destination pairs have NSPs. Kini, Yang [Page 4] Internet Draft May 2002 Routing Information at node A : ___________________________________________________________ Destination | Shortest Path | NSP-next-hop | Next Hop |{SP next-hop it passes thru} ------------+----------------+----------------------------- B | B | C C | C | B, D D | D | C E | C | B{C}, D F | F | G | F | H | F | ----------------------------------------------------------- Assuming each link has equal failure probability and traffic between any two nodes is equal, 72 % of traffic that will be ultimately repaired by the SPF is restored by using a NSP. Similar results hold true for node failure. 8. Simulation We evaluate the effectiveness of traffic restoration by NSPs based on the 100-node sample graphs provided in [6], using edge length as link cost. Single link and node failures are simulated, with the following assumptions a. Equal amount of traffic goes between any two vertexes in a graph. b. Each link or node has the same probability of failure. c. Traffic between two nodes is considered restored only if all its multipaths are repaired. When a link or node fails, the traffic between two nodes can fall into the following categories a. Unaffected: none of its equal cost shortest paths are affected by the failure. b. Unrepairable: no path can be found after running a SPF. c. Repairable: running a SPF can yield another path. For each link or node failure, we calculate the ratio of path repaired against path repairable. The average of these ratios is presented below as goodness measurement of our proposal. For the purpose of comparison, we use the following two traffic repair algorithms a. ECMP: when an adjacency goes down, redirect traffic to all other equal cost multipath nexthops. b. NSP: when an adjacency goes down, redirect traffic according to the following preferences 1. The lowest cost NSP not going through the unreachable neighbor. 2. All other equal cost multipath nexthops. Kini, Yang [Page 5] Internet Draft May 2002 3. The lowest cost NSP going through the unreachable neighbor. The "goodness" factor of the algorithm is calculated as the ratio of repaired paths to repairable paths. +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | | r0 | r1 | r2 | r3 | r4 | r5 | r6 | r7 | r8 | r9 | +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | ECMP | .02 | .02 | .01 | .00 | .01 | .03 | .00 | .01 | .02 | .00 | +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | NSP | .64 | .63 | .58 | .61 | .62 | .62 | .59 | .63 | .58 | .64 | +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ Table 1: average link failure restoration ratios for random graphs +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | | r0 | r1 | r2 | r3 | r4 | r5 | r6 | r7 | r8 | r9 | +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | ECMP | .03 | .02 | .01 | .00 | .01 | .01 | .00 | .01 | .01 | .01 | +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | NSP | .73 | .72 | .69 | .69 | .69 | .74 | .64 | .64 | .66 | .70 | +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ Table 2: average node failure restoration ratios for random graphs +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | | ts0 | ts1 | ts2 | ts3 | ts4 | ts5 | ts6 | ts7 | ts8 | ts9 | +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | ECMP | .13 | .18 | .14 | .12 | .09 | .08 | .04 | .11 | .13 | .13 | +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | NSP | .91 | .91 | .91 | .90 | .92 | .94 | .92 | .94 | .93 | .93 | +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ Table 3: average link failure restoration ratios for transit-stub graphs +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | | ts0 | ts1 | ts2 | ts3 | ts4 | ts5 | ts6 | ts7 | ts8 | ts9 | +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | ECMP | .18 | .19 | .20 | .13 | .14 | .04 | .11 | .13 | .15 | .13 | +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | NSP | .90 | .88 | .88 | .90 | .91 | .90 | .92 | .92 | .94 | .97 | +------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ Table 4: average node failure restoration ratios for transit-stub graphs For these sample topologies NSP is at least 5 times better at restoring traffic. 9. Interoperability Issues Since no protocol changes are suggested, interoperability issues do Kini, Yang [Page 6] Internet Draft May 2002 not arise. This technique can be deployed gradually in a network without any disruption. 10. Future Work a. Analyze simulation results using topologies from other topology generators [7][8]. b. Technique to prevent loss of traffic when a link comes up. c. Analyze effectiveness in case of multiple link/node failure. d. A more efficient algorithm to compute NSP. 11. Security Considerations This document raises no new security issues. 12. Acknowledgments The authors would like to thank M. Sundaram, B. Gao and R. Dube for their comments on this work. 13. References [1] Moy, J, "OSPF Version 2," RFC 2328, April 1998. [2] "Intermediate System to Intermediate System Intra-Domain Routeing Exchange Protocol for use in Conjunction with the Protocol for Providing the Connectionless mode Network Service (ISO 8473)," ISO DP 10589, February 1990. [3] Callon, R.W., "Use of OSI IS-IS for routing in TCP/IP and dual environments," RFC 1195, Dec. 1990. [4] Alaettinoglu, C, et al "Towards Milli-Second IGP Convergence," Work in progress, Internet Draft , Nov. 2000. [5] Maunder, A.S., "Explicit Marking and Prioritized Treatment of Specific IGP Packets for Faster IGP Convergence and Improved Network Scalability and Stability," Work in progress, Internet Draft , March 2001. [6] Zegura, W, et al. GT-ITM (Georgia Tech - Internet Topology Modeler), http://www.cc.gatech.edu/projects/gtitm/ [7] Medina, A, et al. BRITE (Boston university Representative Internet Topology gEnerator), http://www.cs.bu.edu/brite [8] Jin, C, et al. Inet Internet Topology Generator, http://topology.eecs.umich.edu/inet Kini, Yang [Page 7] Internet Draft May 2002 Authors' Addresses Sriganesh Kini Mahi Networks, 1039 N McDowell Blvd, Petaluma, CA 94954 Phone : 707 283 1257 Email : skini@mahinetworks.com Yibin Yang Mahi Networks, 1039 N McDowell Blvd, Petaluma, CA 94954 Phone : 707 283 1114 Email : yyang@mahinetworks.com Full Copyright Statement Copyright (C) The Internet Society (2000). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." Kini, Yang [Page 8]