Network Working Group X. Zhang Internet-Draft G. Yan Intended status: Standards Track Huawei Technologies Expires: April 21, 2014 October 18, 2013 Algorithm for Ordered Metric Adjustment draft-zxd-rtgwg-ordered-metric-adjustment-00 Abstract Upon link down event or link up event, each device in network individually schedules route calculation. Because of different hardware capabilities and internal/external environments, the time to update forwarding entries on these devices are disordered which can cause a transient forwarding loop. This document introduces a method to prevent forwarding loop by adjusting link metric gradually for several times. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. 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." This Internet-Draft will expire on April 21, 2014. Copyright Notice Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved. Zhang & Yan Expires April 21, 2014 [Page 1] Internet-Draft Ordered Metric Adjustment(OMA) October 2013 This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Overview of Algorithm . . . . . . . . . . . . . . . . . . . . 3 2.1. Link up event . . . . . . . . . . . . . . . . . . . . . . 4 2.2. Link down event . . . . . . . . . . . . . . . . . . . . . 7 3. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 8 3.1. Calculating the adjustment range of link metric for each node . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2. Determine existing forwarding loop or not between two direct nodes . . . . . . . . . . . . . . . . . . . . . . 8 3.3. Algorithm of multiple nodes simultaneously switch optimal path without forwarding loop . . . . . . . . . . . . . . 9 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 5. Security Considerations . . . . . . . . . . . . . . . . . . . 10 6. Normative References . . . . . . . . . . . . . . . . . . . . 10 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 1. Introduction The internet is the most popular network, it is a distributed system, Depend on its configuration, each network device communicates with its neighbor, calculate routes and generate the FIB individually, finally, the packet will be forwarded hop by hop. But due to the difference of each device hardware capabilities and internal/external environments, the route calculation cannot be scheduled at same time, the micro-loop occur, and some mechanisms are already provided in IETF to resolve this issue, like ordered FIB. This document tries to provide a different method to resolve this issue. In figure 1, there are some forwarding loop scenarios: o Upon link BA down event, for the destination A, if B updates its forwarding entry before G, a transient forwarding loop occurs between B and G. Node failure MAY be treated as multiple links' failure, such as B fails, the links GB, BA, BC go to down. For Zhang & Yan Expires April 21, 2014 [Page 2] Internet-Draft Ordered Metric Adjustment(OMA) October 2013 the destination A, if G updates its forwarding entry before I, a transient forwarding loop occurs between I and G. o Upon link BA up event, for the destination A, if G updates its forwarding entry before B, a transient forwarding loop occurs between B and G. Node failure recovery MAY be treated as multiple links' failure recovery, such as B recovers, the links GB, BA, BC go to up. For the destination A, if I updates its forwarding entry before G, a transient forwarding loop occurs between I and G. D-------E | | | | C F | | | | B-------A | | | | G J / \ / / \ / H I Figure 1 Topology (all links with metric 10 except links AF and AJ with metric 100) 2. Overview of Algorithm This document introduces a method to prevent forwarding loop by adjusting link metric gradually. There are two cases to be considered here: o Link up event: The link metric will be decreased from maximum to configuration value. Node failure recovery MAY be treated as multiple links' failure recovery. o Link down event: The link metric will be increased from configuration value to maximum. Node failure MAY be treated as multiple links' failures. Zhang & Yan Expires April 21, 2014 [Page 3] Internet-Draft Ordered Metric Adjustment(OMA) October 2013 2.1. Link up event As we know, the optimal paths from other nodes to node R can be represented as the RSPF tree with root R. We assume that the link XR between node X and R goes to up, some nodes MAY switch their optimal paths to R and the new optimal paths include the link XR. If the metric of link XR is small enough, X will be the children of R in RSPF tree and the nodes of the sub-tree under X on the RSPF tree will switch their optimal paths to R, other nodes' optimal paths are not changed. The nodes whose optimal paths to the R are changed are denoted by set of S. If the nodes in S switch their optimal paths when link XR goes to up, some forwarding loop MAY exist as described in section 1. In order to prevent the forwarding loop, we can control the nodes in S to switch optimal paths gradually instead of switching all the nodes at the same time. For the case of link up event, the metric of link XR is decreased gradually by several times. Once the metric of link XR is adjusted, one node or several nodes any two of which do not have forwarding loop will switch optimal path to R. Until the metric of link XR is decreased to configuration value, all the nodes in S switch their optimal paths to R. We give an example to describe the procedure of adjusting link metric as follows: In Figure 1, suppose the link BA is down. All the paths of the other nodes to node A can be represented as RSPF(Reverse Shortest Path First ) tree with root A(as figure 2 below). A / \ / \ J F / \ / \ I E / \ / \ G D /| \ / | \ B H C Figure 2 Reverse Shortest Path First Tree After link BA going to up, node B will start to adjust the metric of link BA and repeat adjusting several times as below: Zhang & Yan Expires April 21, 2014 [Page 4] Internet-Draft Ordered Metric Adjustment(OMA) October 2013 o The metric of link BA is set to 121. For the destination A, only B's optimal path has changed. The following figure 3 describes the RSPF tree with root A after the first adjustment. A /|\ / | \ J B F / \ / \ I E / \ / \ G D | \ | \ H C Figure 3 Reverse Shortest Path First Tree (The metric of link BA is 121) o The metric of link BA is set to 101. For the destination A, the node C, G and H's optimal paths have changed. The following figure 4 describes the RSPF tree with root A after this adjustment. A /|\ / | \ J B F / / \ \ / / \ \ I C G E \ \ \ \ H D Figure 4 Reverse Shortest Path First Tree(The metric of link BA is 101) o The metric of link BA is set to 81. For the destination A, the node D and I's optimal paths have changed. The figure 5 below describes the RSPF tree with root A after this adjustment. Zhang & Yan Expires April 21, 2014 [Page 5] Internet-Draft Ordered Metric Adjustment(OMA) October 2013 A /|\ / | \ J B F / \ \ / \ \ C G E | |\ | | \ D I H Figure 5 Reverse Shortest Path First Tree(The metric of link BA is 81) o The metric of link BA is set to 61. For the destination A, the node E and J's optimal paths have changed. The figure 6 below describes the RSPF tree with root A after this adjustment. A |\ | \ B F / \ / \ C G | |\ | | \ D I H | | | | E J Figure 6 Reverse Shortest Path First Tree(The metric of link BA is 61) o The metric of link BA is set to 10 which is configuration value. For the destination A, node F's optimal path has changed. The figure 7 below describes the RSPF tree with root A after this adjustment. Zhang & Yan Expires April 21, 2014 [Page 6] Internet-Draft Ordered Metric Adjustment(OMA) October 2013 A | | B / \ / \ C G | |\ | | \ D I H | | | | E J | | F Figure 7 Reverse Shortest Path First Tree(The metric of link BA is 10) As shown in the example above, one or more nodes' optimal paths to node A will be affected when the metric of link is adjusted every time. The nodes not affected keep the outgoing interfaces and next hops unchanged. There is no forwarding loop during this adjustment.(as in Figure 3 H, G, etc. ). Once the link metric is adjusted, the new LSP/LSA will be generated with the new metric information and will be flooded to the same area/ level, and all the nodes in the same area/level will calculate routes. So all the nodes need enough time to flood new LSP/LSA and calculate routes before the next adjustment of link metric. Usually, it needs a few seconds to tens of seconds delay to start a new adjustment. The delay between different adjustments will avoid to affect each other. Similarly, for the destination B, we can use the same method to adjust the metric of link AB to avoid forwarding loop. 2.2. Link down event In Figure 1, supposing the link BA goes to down, for the destination A, it can avoid forwarding loop by increasing metric of link BA from configured value to maximum. The process of adjustment is reverse to the process of link up event. And the RSPF tree with root A is changed from figure 7 to figure 2 gradually. Zhang & Yan Expires April 21, 2014 [Page 7] Internet-Draft Ordered Metric Adjustment(OMA) October 2013 The adjustment of metric just involves the nodes connected to the failure link, other nodes just do normal route calculation. So the method is very convenient for incremental deployment. 3. Algorithm Sections In figure3, the metric of the link BA is set to 121, node B switches an optimal path to A, while the other nodes do not switch their optimal paths. In fact the metrics ranged from 121 to 129 of the link BA is also valid to ensure that only the node B has to switch to an optimal path to A. The following algorithm 3.1 is used to calculate a reasonable adjustment metric range for each node to switch its optimal path without forwarding loop. We first assume the failure link is L(for example, link BA in figure 1), and its configuration metric value is K. The destination node of link L is root node(for example, node A) which is referenced in the following sections. 3.1. Calculating the adjustment range of link metric for each node 1. Supposing the link L(for example, link BA in figure 1) is down, the metric of link L can be considered as maximum. It is easy to use RSPF algorithm to calculate the distance of each node i to root node. The distance from each node i to the root is recorded as D(i, max). 2. Supposing the link L is up, the metric of link L is set to configured value. It is easy to use RSPF algorithm to calculate the distance of each node i to root which is the destination node of link L. The distance from each node i to the root is recorded as D(i, min). 3. If node i switches its optimal path to root node, the reasonable upper metric of link L can be adjusted is COST(i, max), COST(i, max) = D(i, max) - D(i, min)+K. 4. If node i switches its optimal path to root node, the reasonable lower metric of link L can be adjusted is COST(i, min), COST(i, min) = MAX{COST(j, max)}, where j is the son of node i in case of link L being up. 5. When the link L's metric is set in the range of (COST(i, min), COST(i, max)), node i can be switched to its optimal path to the root node without forwarding loop. 3.2. Determine existing forwarding loop or not between two direct nodes Zhang & Yan Expires April 21, 2014 [Page 8] Internet-Draft Ordered Metric Adjustment(OMA) October 2013 F is the parent node, S is its son node. if COST(F, max) equals COST(S, max), when F switches to the new optimal path to root because of link L's metric's adjustment, S will switches simultaneously with F without forwarding loop. 3.3. Algorithm of multiple nodes simultaneously switch optimal path without forwarding loop 1. Initialize three queues: TentList, CandList, OutPutList. 2. The destination node of link L is recorded as root. 3. Push the root node to TentList. 4. Get the node N from TentList, where N is the node whose COST(i, min) is maximum in TentList. if TentList is empty, we cannot get any node, then this algorithm terminates. 5. Move node N to the tail of OutPutList. 6. Push every son node Si of N to CandList, where COST(Si, max) does not equal COST(N, max). 7. For each node mi in TentList, if COST(mi, max) > COST(N, min), remove the node mi from TentList. 8. When mi is deleted from TentList, push every son node Sj of mi to CandList, where COST(Sj, max) does not equal COST(mi, max). 9. Move all the nodes from CandList to Tentlist, then CandList is empty. 10. goto 4. 11. When the algorithm finishes, OutPutList stores node N1, N2,... Ns, * In case of link L going to up, the adjustment process of metric of link L is COST(N1, min)+1, COST(N2, min)+1,... COST(Ns, min)+1, and configuration value K. * In case of link L going to down, the adjustment process of metric of link L is configuration value K, COST(Ns, min)+1, ... COST(N2, min)+1 and COST(N1, min)+1. 4. IANA Considerations This document includes no request to IANA. Zhang & Yan Expires April 21, 2014 [Page 9] Internet-Draft Ordered Metric Adjustment(OMA) October 2013 5. Security Considerations This document is not currently believed to introduce new security concerns. 6. Normative References [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and dual environments", RFC 1195, December 1990. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free Convergence", RFC 5715, January 2010. [RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C., Francois, P., and O. Bonaventure, "Framework for Loop-Free Convergence Using the Ordered Forwarding Information Base (oFIB) Approach", RFC 6976, July 2013. Authors' Addresses Xudong Zhang Huawei Technologies Huawei Bld., No.156 Beiqing Rd. Beijing 100095 China Email: zhangxudong@huawei.com Gang Yan Huawei Technologies Huawei Bld., No.156 Beiqing Rd. Beijing 100095 China Email: yangang@huawei.com Zhang & Yan Expires April 21, 2014 [Page 10]