idnits 2.17.00 (12 Aug 2021) /tmp/idnits49084/draft-zxd-rtgwg-ordered-metric-adjustment-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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 18, 2013) is 3136 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'RFC1195' is defined on line 417, but no explicit reference was found in the text == Unused Reference: 'RFC2328' is defined on line 423, but no explicit reference was found in the text == Unused Reference: 'RFC5715' is defined on line 425, but no explicit reference was found in the text == Unused Reference: 'RFC6976' is defined on line 428, but no explicit reference was found in the text ** Downref: Normative reference to an Informational RFC: RFC 5715 ** Downref: Normative reference to an Informational RFC: RFC 6976 Summary: 2 errors (**), 0 flaws (~~), 5 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group X. Zhang 3 Internet-Draft G. Yan 4 Intended status: Standards Track Huawei Technologies 5 Expires: April 21, 2014 October 18, 2013 7 Algorithm for Ordered Metric Adjustment 8 draft-zxd-rtgwg-ordered-metric-adjustment-00 10 Abstract 12 Upon link down event or link up event, each device in network 13 individually schedules route calculation. Because of different 14 hardware capabilities and internal/external environments, the time to 15 update forwarding entries on these devices are disordered which can 16 cause a transient forwarding loop. This document introduces a method 17 to prevent forwarding loop by adjusting link metric gradually for 18 several times. 20 Requirements Language 22 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 23 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 24 document are to be interpreted as described in RFC 2119 [RFC2119]. 26 Status of This Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF). Note that other groups may also distribute 33 working documents as Internet-Drafts. The list of current Internet- 34 Drafts is at http://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on April 21, 2014. 43 Copyright Notice 45 Copyright (c) 2013 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents 50 (http://trustee.ietf.org/license-info) in effect on the date of 51 publication of this document. Please review these documents 52 carefully, as they describe your rights and restrictions with respect 53 to this document. Code Components extracted from this document must 54 include Simplified BSD License text as described in Section 4.e of 55 the Trust Legal Provisions and are provided without warranty as 56 described in the Simplified BSD License. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 61 2. Overview of Algorithm . . . . . . . . . . . . . . . . . . . . 3 62 2.1. Link up event . . . . . . . . . . . . . . . . . . . . . . 4 63 2.2. Link down event . . . . . . . . . . . . . . . . . . . . . 7 64 3. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 8 65 3.1. Calculating the adjustment range of link metric for each 66 node . . . . . . . . . . . . . . . . . . . . . . . . . . 8 67 3.2. Determine existing forwarding loop or not between two 68 direct nodes . . . . . . . . . . . . . . . . . . . . . . 8 69 3.3. Algorithm of multiple nodes simultaneously switch optimal 70 path without forwarding loop . . . . . . . . . . . . . . 9 71 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 72 5. Security Considerations . . . . . . . . . . . . . . . . . . . 10 73 6. Normative References . . . . . . . . . . . . . . . . . . . . 10 74 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 76 1. Introduction 78 The internet is the most popular network, it is a distributed system, 79 Depend on its configuration, each network device communicates with 80 its neighbor, calculate routes and generate the FIB individually, 81 finally, the packet will be forwarded hop by hop. But due to the 82 difference of each device hardware capabilities and internal/external 83 environments, the route calculation cannot be scheduled at same time, 84 the micro-loop occur, and some mechanisms are already provided in 85 IETF to resolve this issue, like ordered FIB. 87 This document tries to provide a different method to resolve this 88 issue. 90 In figure 1, there are some forwarding loop scenarios: 92 o Upon link BA down event, for the destination A, if B updates its 93 forwarding entry before G, a transient forwarding loop occurs 94 between B and G. Node failure MAY be treated as multiple links' 95 failure, such as B fails, the links GB, BA, BC go to down. For 96 the destination A, if G updates its forwarding entry before I, a 97 transient forwarding loop occurs between I and G. 99 o Upon link BA up event, for the destination A, if G updates its 100 forwarding entry before B, a transient forwarding loop occurs 101 between B and G. Node failure recovery MAY be treated as multiple 102 links' failure recovery, such as B recovers, the links GB, BA, BC 103 go to up. For the destination A, if I updates its forwarding 104 entry before G, a transient forwarding loop occurs between I and 105 G. 107 D-------E 108 | | 109 | | 110 C F 111 | | 112 | | 113 B-------A 114 | | 115 | | 116 G J 117 / \ / 118 / \ / 119 H I 121 Figure 1 Topology (all links with metric 10 except links AF and AJ 122 with metric 100) 124 2. Overview of Algorithm 126 This document introduces a method to prevent forwarding loop by 127 adjusting link metric gradually. There are two cases to be 128 considered here: 130 o Link up event: The link metric will be decreased from maximum to 131 configuration value. Node failure recovery MAY be treated as 132 multiple links' failure recovery. 134 o Link down event: The link metric will be increased from 135 configuration value to maximum. Node failure MAY be treated as 136 multiple links' failures. 138 2.1. Link up event 140 As we know, the optimal paths from other nodes to node R can be 141 represented as the RSPF tree with root R. We assume that the link XR 142 between node X and R goes to up, some nodes MAY switch their optimal 143 paths to R and the new optimal paths include the link XR. If the 144 metric of link XR is small enough, X will be the children of R in 145 RSPF tree and the nodes of the sub-tree under X on the RSPF tree will 146 switch their optimal paths to R, other nodes' optimal paths are not 147 changed. The nodes whose optimal paths to the R are changed are 148 denoted by set of S. If the nodes in S switch their optimal paths 149 when link XR goes to up, some forwarding loop MAY exist as described 150 in section 1. In order to prevent the forwarding loop, we can 151 control the nodes in S to switch optimal paths gradually instead of 152 switching all the nodes at the same time. For the case of link up 153 event, the metric of link XR is decreased gradually by several times. 154 Once the metric of link XR is adjusted, one node or several nodes any 155 two of which do not have forwarding loop will switch optimal path to 156 R. Until the metric of link XR is decreased to configuration value, 157 all the nodes in S switch their optimal paths to R. We give an 158 example to describe the procedure of adjusting link metric as 159 follows: 161 In Figure 1, suppose the link BA is down. All the paths of the other 162 nodes to node A can be represented as RSPF(Reverse Shortest Path 163 First ) tree with root A(as figure 2 below). 165 A 166 / \ 167 / \ 168 J F 169 / \ 170 / \ 171 I E 172 / \ 173 / \ 174 G D 175 /| \ 176 / | \ 177 B H C 179 Figure 2 Reverse Shortest Path First Tree 181 After link BA going to up, node B will start to adjust the metric of 182 link BA and repeat adjusting several times as below: 184 o The metric of link BA is set to 121. For the destination A, only 185 B's optimal path has changed. The following figure 3 describes 186 the RSPF tree with root A after the first adjustment. 188 A 189 /|\ 190 / | \ 191 J B F 192 / \ 193 / \ 194 I E 195 / \ 196 / \ 197 G D 198 | \ 199 | \ 200 H C 202 Figure 3 Reverse Shortest Path First Tree (The metric of link BA is 203 121) 205 o The metric of link BA is set to 101. For the destination A, the 206 node C, G and H's optimal paths have changed. The following 207 figure 4 describes the RSPF tree with root A after this 208 adjustment. 210 A 211 /|\ 212 / | \ 213 J B F 214 / / \ \ 215 / / \ \ 216 I C G E 217 \ \ 218 \ \ 219 H D 221 Figure 4 Reverse Shortest Path First Tree(The metric of link BA is 222 101) 224 o The metric of link BA is set to 81. For the destination A, the 225 node D and I's optimal paths have changed. The figure 5 below 226 describes the RSPF tree with root A after this adjustment. 228 A 229 /|\ 230 / | \ 231 J B F 232 / \ \ 233 / \ \ 234 C G E 235 | |\ 236 | | \ 237 D I H 239 Figure 5 Reverse Shortest Path First Tree(The metric of link BA is 240 81) 242 o The metric of link BA is set to 61. For the destination A, the 243 node E and J's optimal paths have changed. The figure 6 below 244 describes the RSPF tree with root A after this adjustment. 246 A 247 |\ 248 | \ 249 B F 250 / \ 251 / \ 252 C G 253 | |\ 254 | | \ 255 D I H 256 | | 257 | | 258 E J 260 Figure 6 Reverse Shortest Path First Tree(The metric of link BA is 261 61) 263 o The metric of link BA is set to 10 which is configuration value. 264 For the destination A, node F's optimal path has changed. The 265 figure 7 below describes the RSPF tree with root A after this 266 adjustment. 268 A 269 | 270 | 271 B 272 / \ 273 / \ 274 C G 275 | |\ 276 | | \ 277 D I H 278 | | 279 | | 280 E J 281 | 282 | 283 F 285 Figure 7 Reverse Shortest Path First Tree(The metric of link BA is 286 10) 288 As shown in the example above, one or more nodes' optimal paths to 289 node A will be affected when the metric of link is adjusted every 290 time. The nodes not affected keep the outgoing interfaces and next 291 hops unchanged. There is no forwarding loop during this 292 adjustment.(as in Figure 3 H, G, etc. ). 294 Once the link metric is adjusted, the new LSP/LSA will be generated 295 with the new metric information and will be flooded to the same area/ 296 level, and all the nodes in the same area/level will calculate 297 routes. So all the nodes need enough time to flood new LSP/LSA and 298 calculate routes before the next adjustment of link metric. Usually, 299 it needs a few seconds to tens of seconds delay to start a new 300 adjustment. The delay between different adjustments will avoid to 301 affect each other. 303 Similarly, for the destination B, we can use the same method to 304 adjust the metric of link AB to avoid forwarding loop. 306 2.2. Link down event 308 In Figure 1, supposing the link BA goes to down, for the destination 309 A, it can avoid forwarding loop by increasing metric of link BA from 310 configured value to maximum. The process of adjustment is reverse to 311 the process of link up event. And the RSPF tree with root A is 312 changed from figure 7 to figure 2 gradually. 314 The adjustment of metric just involves the nodes connected to the 315 failure link, other nodes just do normal route calculation. So the 316 method is very convenient for incremental deployment. 318 3. Algorithm Sections 320 In figure3, the metric of the link BA is set to 121, node B switches 321 an optimal path to A, while the other nodes do not switch their 322 optimal paths. In fact the metrics ranged from 121 to 129 of the 323 link BA is also valid to ensure that only the node B has to switch to 324 an optimal path to A. The following algorithm 3.1 is used to 325 calculate a reasonable adjustment metric range for each node to 326 switch its optimal path without forwarding loop. 328 We first assume the failure link is L(for example, link BA in figure 329 1), and its configuration metric value is K. The destination node of 330 link L is root node(for example, node A) which is referenced in the 331 following sections. 333 3.1. Calculating the adjustment range of link metric for each node 335 1. Supposing the link L(for example, link BA in figure 1) is down, 336 the metric of link L can be considered as maximum. It is easy to 337 use RSPF algorithm to calculate the distance of each node i to 338 root node. The distance from each node i to the root is recorded 339 as D(i, max). 341 2. Supposing the link L is up, the metric of link L is set to 342 configured value. It is easy to use RSPF algorithm to calculate 343 the distance of each node i to root which is the destination node 344 of link L. The distance from each node i to the root is recorded 345 as D(i, min). 347 3. If node i switches its optimal path to root node, the reasonable 348 upper metric of link L can be adjusted is COST(i, max), COST(i, 349 max) = D(i, max) - D(i, min)+K. 351 4. If node i switches its optimal path to root node, the reasonable 352 lower metric of link L can be adjusted is COST(i, min), COST(i, 353 min) = MAX{COST(j, max)}, where j is the son of node i in case of 354 link L being up. 356 5. When the link L's metric is set in the range of (COST(i, min), 357 COST(i, max)), node i can be switched to its optimal path to the 358 root node without forwarding loop. 360 3.2. Determine existing forwarding loop or not between two direct nodes 361 F is the parent node, S is its son node. if COST(F, max) equals 362 COST(S, max), when F switches to the new optimal path to root 363 because of link L's metric's adjustment, S will switches 364 simultaneously with F without forwarding loop. 366 3.3. Algorithm of multiple nodes simultaneously switch optimal path 367 without forwarding loop 369 1. Initialize three queues: TentList, CandList, OutPutList. 371 2. The destination node of link L is recorded as root. 373 3. Push the root node to TentList. 375 4. Get the node N from TentList, where N is the node whose COST(i, 376 min) is maximum in TentList. if TentList is empty, we cannot get 377 any node, then this algorithm terminates. 379 5. Move node N to the tail of OutPutList. 381 6. Push every son node Si of N to CandList, where COST(Si, max) 382 does not equal COST(N, max). 384 7. For each node mi in TentList, if COST(mi, max) > COST(N, min), 385 remove the node mi from TentList. 387 8. When mi is deleted from TentList, push every son node Sj of mi 388 to CandList, where COST(Sj, max) does not equal COST(mi, max). 390 9. Move all the nodes from CandList to Tentlist, then CandList is 391 empty. 393 10. goto 4. 395 11. When the algorithm finishes, OutPutList stores node N1, N2,... 396 Ns, 398 * In case of link L going to up, the adjustment process of 399 metric of link L is COST(N1, min)+1, COST(N2, min)+1,... 400 COST(Ns, min)+1, and configuration value K. 402 * In case of link L going to down, the adjustment process of 403 metric of link L is configuration value K, COST(Ns, min)+1, 404 ... COST(N2, min)+1 and COST(N1, min)+1. 406 4. IANA Considerations 408 This document includes no request to IANA. 410 5. Security Considerations 412 This document is not currently believed to introduce new security 413 concerns. 415 6. Normative References 417 [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and 418 dual environments", RFC 1195, December 1990. 420 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 421 Requirement Levels", BCP 14, RFC 2119, March 1997. 423 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998. 425 [RFC5715] Shand, M. and S. Bryant, "A Framework for Loop-Free 426 Convergence", RFC 5715, January 2010. 428 [RFC6976] Shand, M., Bryant, S., Previdi, S., Filsfils, C., 429 Francois, P., and O. Bonaventure, "Framework for Loop-Free 430 Convergence Using the Ordered Forwarding Information Base 431 (oFIB) Approach", RFC 6976, July 2013. 433 Authors' Addresses 435 Xudong Zhang 436 Huawei Technologies 437 Huawei Bld., No.156 Beiqing Rd. 438 Beijing 100095 439 China 441 Email: zhangxudong@huawei.com 443 Gang Yan 444 Huawei Technologies 445 Huawei Bld., No.156 Beiqing Rd. 446 Beijing 100095 447 China 449 Email: yangang@huawei.com