idnits 2.17.1 draft-geng-iac-caba-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The abstract seems to contain references ([RFC5286]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (May 12, 2020) is 1444 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force Geng, Ed. 3 Internet-Draft Shanxi Univ. 4 Intended status: Informational Zhang 5 Expires: November 13, 2020 Beihang Univ. 6 Shi 7 Wang 8 Yin 9 Tsinghua Univ. 10 May 12, 2020 12 Efficient Implementation Method for Loop-free Criterion 13 draft-geng-iac-caba-00 15 Abstract 17 [RFC5286] introduces Loop-Free Criterion (LFC) in detail, which is a 18 technology for local fast rerouting when network failures occur. 19 With LFC, alternate next hops are stored alongside with the default 20 next hops in a routers forwarding table, and can be immediately 21 activated to invoke a loop free repair path in face of link failure. 22 As long as not introducing routing loops, these alternative next hops 23 can also be used for multipath transmission if there are stringent 24 demands on bandwidth or load balancing. However, in such link state 25 networks, computing loop free alternates typically requires one or 26 more rounds of full shortest path tree computation on a graph, and 27 poses a heavy burden to both the processor load and the memory 28 consumption of a network equipment. In this document, we describe an 29 efficient Loop-free Criterion (LFC) implementation method which is 30 based on incremental shortest path first (i-SPF), which is suitable 31 for practical deployment in large scale networks. The computational 32 complexity of the method is independent of the average node degree of 33 the network. 35 Status of This Memo 37 This Internet-Draft is submitted in full conformance with the 38 provisions of BCP 78 and BCP 79. 40 Internet-Drafts are working documents of the Internet Engineering 41 Task Force (IETF). Note that other groups may also distribute 42 working documents as Internet-Drafts. The list of current Internet- 43 Drafts is at https://datatracker.ietf.org/drafts/current/. 45 Internet-Drafts are draft documents valid for a maximum of six months 46 and may be updated, replaced, or obsoleted by other documents at any 47 time. It is inappropriate to use Internet-Drafts as reference 48 material or to cite them other than as "work in progress." 49 This Internet-Draft will expire on November 13, 2020. 51 Copyright Notice 53 Copyright (c) 2020 IETF Trust and the persons identified as the 54 document authors. All rights reserved. 56 This document is subject to BCP 78 and the IETF Trust's Legal 57 Provisions Relating to IETF Documents 58 (https://trustee.ietf.org/license-info) in effect on the date of 59 publication of this document. Please review these documents 60 carefully, as they describe your rights and restrictions with respect 61 to this document. Code Components extracted from this document must 62 include Simplified BSD License text as described in Section 4.e of 63 the Trust Legal Provisions and are provided without warranty as 64 described in the Simplified BSD License. 66 Table of Contents 68 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 69 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 2 70 3. Overview of Solution . . . . . . . . . . . . . . . . . . . . 3 71 4. Security Considerations . . . . . . . . . . . . . . . . . . . 5 72 5. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . 5 73 6. Normative References . . . . . . . . . . . . . . . . . . . . 5 74 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 6 76 1. Introduction 78 Existing algorithms for computing LFC rely on one or more rounds of 79 full shortest path tree computation on a graph, and cannot achieve 80 both good coverage of alternates and low computational complexity at 81 the same time. Based on graph properties we newly find, this 82 document propose Incremental Alternates Computation IAC, which can 83 compute the full set of alternates for a given network topology in a 84 highly efficient way. IAC performs incremental shortest path 85 computation on specific link cost update, where the sign of some cost 86 is simply reversed. 88 2. Terminology 90 In this document, we employ OSPF as an example to explain our method. 91 Each router in a single routing area maintains an identical network 92 map which allows them to compute the shortest path to every other 93 router in a routing area. Then each router construct its FIB table 94 employing the above information. When a packet arrives at a router, 95 a destination address based method is using to determine how to 96 forward the packets to its corresponding interface. When the network 97 topology changes, the routers adjacent to the changed component 98 detects the change and then propagates the information to its 99 neighboring router through the LSA (link state advertisement) 100 information. After a period of time, all routers in this routing 101 area are aware of the change information and update their routing 102 tables accordingly, then the network is at a stable state. 104 LFC: x can be chosen when C(x,d) is lower than C(x,c)+C(c,d), which 105 means when packets are routed from x to d, they will not be routed 106 back to c, since C(x,c) + C(c,d) is the lowest cost of any path from 107 x to d that passes c. So the protection route will bypass c, thus 108 bypass link (c,b) too. 110 In order to implement LFC rule, each node needs to obtain costs for 111 its neighbors as well as itself. With a linkstate protocol, it 112 requires multiple shortest-path computations. In this document, the 113 notation C(x,d) refers to the shortest path cost from node x to node 114 d, x refers to the neighboring node of node c. w(c,x) refers to the 115 weight of link (c,x), Tc refers to the shortest path tree rooted at 116 node c, Tc(c,x) refers to the shortest path tree rooted at node c 117 when the weight of the link (c,x) is changed to -w(c,x), D(Tc,x) 118 refers to the descendants of node x (x is included) in the Tc, 119 D(Tc(c,x),x) refers to the descendants of node x (x is included) in 120 the Tc(c,x). 122 3. Overview of Solution 124 In general, in order to compute the LFCs set for a spcific 125 destination d, a router needs to know the following information: 127 (1) the shortest path cost from the calculating router, for example 128 router c, to the destination d (C(c,d)). 130 (2) the shortest path cost from the neighboring node x of c to the 131 destination d (C(x,d)). 133 (3) the shortest path cost from the neighboring node x of c to itself 134 (C(x,c)). 136 C(c,d) can be obtained from the shortest path tree Tc, C(x,c) is 137 equal to w(x,c) which can be obtained from OSPF protocol, C(x,c) can 138 be obtained by performing additional SPF calculations. Therefore, 139 the induced cost will be particularly high for high degree nodes. 141 This document describes how to efficiently implement LFC rule on 142 backbone networks. In order to implement LFC efficiently, the next 143 hop computation rule is proposed. 145 Next hop computation rule: 147 For a node d, if d is not in the set of D(Tc,x), while d is in the 148 set of D(Tc(c,x),x), we can get the node x is a valid next hop from c 149 to d. 151 c 152 /\ 153 3/ \5 154 / \ 155 a b 156 | | 157 3 | |3 158 | | 159 d------e 160 3 162 Figure 1: Network Topology 164 c 165 /\ 166 3/ \5 167 / \ 168 a b 169 | | 170 3| |3 171 | | 172 d e 174 Figure 2: Shortest path first rooted at node c 176 c 177 /\ 178 -3/ \5 179 / \ 180 a b 181 | 182 3| 183 | 184 d 185 | 186 3| 187 | 188 e 190 Figure 3: Shortest path first rooted at node c when the weight of 191 link (c,a) is changed to -3 192 c 193 /\ 194 3/ \-5 195 / \ 196 a b 197 | 198 3| 199 | 200 e 201 | 202 3| 203 | 204 d 206 Figure 4: Shortest path first rooted at node c when the weight of 207 link (c,b) is changed to -5 209 IAC cleverly uses Next hop computation rule, so it can realize LFC 210 efficiently. IAC is suitable for incremental deployment within a 211 network, including a network that is already deploying iSPF. We will 212 use the following example to explain how ICA works. Fig. 1 depicts a 213 network topology consisting of 5 nodes and 6 edges, while the 214 corresponding SPT Tc is depicted in Fig. 2(b), with c being the root. 215 Fig. 3 shows the shortest path tree constructed using i-SPF when the 216 weight of link (c,a) is changed to -3. Fig. 4 is the shortest path 217 tree constructed using i-SPF when the weight of link (c,b) is changed 218 to -5. We can see that node a can be a viable backup next-hop from c 219 to e according to the next hop computation rule. We can get that 220 node b can be a viable backup next-hop from c to d in the same way. 222 4. Security Considerations 224 The security considerations of [RFC5286] also apply. 226 5. Conclusions 228 The purpose of this document is to describe an efficient way to 229 implement LFC, which can compute the full set of alternates with 230 incremental shortest path first computation on specific link cost 231 update. Therefore, IAC is suitable for deploying in the larger scale 232 networks. 234 6. Normative References 236 [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for 237 IP Fast Reroute: Loop-Free Alternates", RFC 5286, 238 DOI 10.17487/RFC5286, September 2008, 239 . 241 Authors' Addresses 243 Haijun Geng (editor) 244 Shanxi Univ. 245 Taiyuan 246 CN 248 Email: genghaijun@sxu.edu.cn 250 Han Zhang 251 Beihang Univ. 252 Beijing 253 CN 255 Email: zhhan@buaa.edu.cn 257 Xingang Shi 258 Tsinghua Univ. 259 Beijing 260 CN 262 Email: shixg@cernet.edu.cn 264 Zhiliang Wang 265 Tsinghua Univ. 266 Beijing 267 CN 269 Email: wzl@cernet.edu.cn 271 Xia Yin 272 Tsinghua Univ. 273 Beijing 274 CN 276 Email: yxia@tsinghua.edu.cn