1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
|
<pre>Internet Engineering Task Force (IETF) B. Decraene
Request for Comments: 8405 Orange
Category: Standards Track S. Litkowski
ISSN: 2070-1721 Orange Business Service
H. Gredler
RtBrick Inc.
A. Lindem
Cisco Systems
P. Francois
C. Bowers
Juniper Networks, Inc.
June 2018
<span class="h1">Shortest Path First (SPF) Back-Off Delay Algorithm for Link-State IGPs</span>
Abstract
This document defines a standard algorithm to temporarily postpone or
"back off" link-state IGP Shortest Path First (SPF) computations.
This reduces the computational load and churn on IGP nodes when
multiple temporally close network events trigger multiple SPF
computations.
Having one standard algorithm improves interoperability by reducing
the probability and/or duration of transient forwarding loops during
the IGP convergence when the IGP reacts to multiple temporally close
IGP events.
Status of This Memo
This is an Internet Standards Track document.
This document is a product of the Internet Engineering Task Force
(IETF). It represents the consensus of the IETF community. It has
received public review and has been approved for publication by the
Internet Engineering Steering Group (IESG). Further information on
Internet Standards is available in <a href="./rfc7841#section-2">Section 2 of RFC 7841</a>.
Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
<a href="https://www.rfc-editor.org/info/rfc8405">https://www.rfc-editor.org/info/rfc8405</a>.
<span class="grey">Decraene, et al. Standards Track [Page 1]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span>
<span class="grey"><a href="./rfc8405">RFC 8405</a> SPF Back-Off Delay Algorithm June 2018</span>
Copyright Notice
Copyright (c) 2018 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to <a href="https://www.rfc-editor.org/bcp/bcp78">BCP 78</a> and the IETF Trust's Legal
Provisions Relating to IETF Documents
(<a href="https://trustee.ietf.org/license-info">https://trustee.ietf.org/license-info</a>) 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
<a href="#section-1">1</a>. Introduction . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-2">2</a>
<a href="#section-1.1">1.1</a>. Requirements Language . . . . . . . . . . . . . . . . . . <a href="#page-3">3</a>
<a href="#section-2">2</a>. High-Level Goals . . . . . . . . . . . . . . . . . . . . . . <a href="#page-3">3</a>
<a href="#section-3">3</a>. Definitions and Parameters . . . . . . . . . . . . . . . . . <a href="#page-4">4</a>
<a href="#section-4">4</a>. Principles of the SPF Delay Algorithm . . . . . . . . . . . . <a href="#page-5">5</a>
<a href="#section-5">5</a>. Specification of the SPF Delay State Machine . . . . . . . . <a href="#page-6">6</a>
<a href="#section-5.1">5.1</a>. State Machine . . . . . . . . . . . . . . . . . . . . . . <a href="#page-6">6</a>
<a href="#section-5.2">5.2</a>. States . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-7">7</a>
<a href="#section-5.3">5.3</a>. Timers . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-7">7</a>
<a href="#section-5.4">5.4</a>. FSM Events . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-7">7</a>
<a href="#section-6">6</a>. Parameters . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-9">9</a>
<a href="#section-7">7</a>. Partial Deployment . . . . . . . . . . . . . . . . . . . . . <a href="#page-10">10</a>
<a href="#section-8">8</a>. Impact on Micro-loops . . . . . . . . . . . . . . . . . . . . <a href="#page-11">11</a>
<a href="#section-9">9</a>. IANA Considerations . . . . . . . . . . . . . . . . . . . . . <a href="#page-11">11</a>
<a href="#section-10">10</a>. Security Considerations . . . . . . . . . . . . . . . . . . . <a href="#page-11">11</a>
<a href="#section-11">11</a>. References . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-11">11</a>
<a href="#section-11.1">11.1</a>. Normative References . . . . . . . . . . . . . . . . . . <a href="#page-11">11</a>
<a href="#section-11.2">11.2</a>. Informative References . . . . . . . . . . . . . . . . . <a href="#page-11">11</a>
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-13">13</a>
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-13">13</a>
<span class="grey">Decraene, et al. Standards Track [Page 2]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span>
<span class="grey"><a href="./rfc8405">RFC 8405</a> SPF Back-Off Delay Algorithm June 2018</span>
<span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. Introduction</span>
Link-state IGPs, such as IS-IS [<a href="#ref-ISO10589">ISO10589</a>], OSPF [<a href="./rfc2328" title=""OSPF Version 2"">RFC2328</a>], and OSPFv3
[<a href="./rfc5340" title=""OSPF for IPv6"">RFC5340</a>], perform distributed route computation on all routers in
the area/level. In order to have consistent routing tables across
the network, such distributed computation requires that all routers
have the same version of the network topology (Link-State Database
(LSDB)) and perform their computation essentially at the same time.
In general, when the network is stable, there is a desire to trigger
a new Shortest Path First (SPF) computation as soon as a failure is
detected in order to quickly route around the failure. However, when
the network is experiencing multiple failures over a short period of
time, there is a conflicting desire to limit the frequency of SPF
computations, which would allow a reduction in control plane
resources used by IGPs and all protocols/subsystems reacting to the
attendant route change, such as LDP [<a href="./rfc5036" title=""LDP Specification"">RFC5036</a>], RSVP-TE [<a href="./rfc3209" title=""RSVP-TE: Extensions to RSVP for LSP Tunnels"">RFC3209</a>], BGP
[<a href="./rfc4271" title=""A Border Gateway Protocol 4 (BGP-4)"">RFC4271</a>], Fast Reroute computations (e.g., Loop-Free Alternates
(LFAs) [<a href="./rfc5286" title=""Basic Specification for IP Fast Reroute: Loop-Free Alternates"">RFC5286</a>]), FIB updates, etc. This also reduces network churn
and, in particular, reduces side effects (such as micro-loops
[<a href="./rfc5715" title=""A Framework for Loop-Free Convergence"">RFC5715</a>]) that ensue during IGP convergence.
To allow for this, IGPs usually implement an SPF Back-Off Delay
algorithm that postpones or backs off the SPF computation. However,
different implementations chose different algorithms. Hence, in a
multi-vendor network, it's not possible to ensure that all routers
trigger their SPF computation after the same delay. This situation
increases the average and maximum differential delay between routers
completing their SPF computation. It also increases the probability
that different routers compute their FIBs based on different LSDB
versions. Both factors increase the probability and/or duration of
micro-loops as discussed in <a href="#section-8">Section 8</a>.
This document specifies a standard algorithm to allow multi-vendor
networks to have all routers delay their SPF computations for the
same duration.
<span class="h3"><a class="selflink" id="section-1.1" href="#section-1.1">1.1</a>. Requirements Language</span>
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in
<a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a> [<a href="./rfc2119" title=""Key words for use in RFCs to Indicate Requirement Levels"">RFC2119</a>] [<a href="./rfc8174" title=""Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words"">RFC8174</a>] when, and only when, they appear in all
capitals, as shown here.
<span class="grey">Decraene, et al. Standards Track [Page 3]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span>
<span class="grey"><a href="./rfc8405">RFC 8405</a> SPF Back-Off Delay Algorithm June 2018</span>
<span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>. High-Level Goals</span>
The high-level goals of this algorithm are the following:
o very fast convergence for a single event (e.g., link failure),
o paced fast convergence for multiple temporally close IGP events
while IGP stability is considered acceptable,
o delayed convergence when IGP stability is problematic (this will
allow the IGP and related processes to conserve resources during
the period of instability), and
o avoidance of having different SPF_DELAY timer values (<a href="#section-3">Section 3</a>)
across different routers in the area/level. This requires
specific consideration as different routers may receive IGP
messages at different intervals, or even in different orders, due
to differences both in the distance from the originator of the IGP
event and in flooding implementations.
<span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. Definitions and Parameters</span>
IGP event: The reception or origination of an IGP LSDB change
requiring a new routing table computation. Some examples are a
topology change, a prefix change, and a metric change on a link or
prefix. Note that locally triggering a routing table computation is
not considered an IGP event since other IGP routers are unaware of
this occurrence.
Routing table computation, in this document, is scoped to the IGP;
so, this is the computation of the IGP RIB, performed by the IGP,
using the IGP LSDB. No distinction is made between the type of
computation performed, e.g., full SPF, incremental SPF, or Partial
Route Computation (PRC); the type of computation is a local
consideration. This document may interchangeably use the terms
"routing table computation" and "SPF computation".
SPF_DELAY: The delay between the first IGP event triggering a new
routing table computation and the start of that routing table
computation. It can take the following values:
INITIAL_SPF_DELAY: A very small delay to quickly handle a single
isolated link failure, e.g., 0 milliseconds.
SHORT_SPF_DELAY: A small delay to provide fast convergence in the
case of a single component failure (such as a node failure or Shared
Risk Link Group (SRLG) failure) that leads to multiple IGP events,
e.g., 50-100 milliseconds.
<span class="grey">Decraene, et al. Standards Track [Page 4]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span>
<span class="grey"><a href="./rfc8405">RFC 8405</a> SPF Back-Off Delay Algorithm June 2018</span>
LONG_SPF_DELAY: A long delay when the IGP is unstable, e.g., 2
seconds. Note that this allows the IGP network to stabilize.
TIME_TO_LEARN_INTERVAL: This is the maximum duration typically needed
to learn all the IGP events related to a single component failure
(such as router failure or SRLG failure), e.g., 1 second. It's
mostly dependent on failure detection time variation between all
routers that are adjacent to the failure. Additionally, it may
depend on the different IGP implementations/parameters across the
network and their relation to the origination and flooding of link
state advertisements.
HOLDDOWN_INTERVAL: The time required with no received IGP event
before considering the IGP to be stable again and allowing the
SPF_DELAY to be restored to INITIAL_SPF_DELAY, e.g., a
HOLDDOWN_INTERVAL of 3 seconds. The HOLDDOWN_INTERVAL MUST be
defaulted or configured to be longer than the TIME_TO_LEARN_INTERVAL.
<span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>. Principles of the SPF Delay Algorithm</span>
For the first IGP event, we assume that there has been a single
simple change in the network, which can be taken into account using a
single routing computation (e.g., link failure, prefix (metric)
change), and we optimize for very fast convergence by delaying the
initial routing computation for a small interval, INITIAL_SPF_DELAY.
Under this assumption, there is no benefit in delaying the routing
computation. In a typical network, this is the most common type of
IGP event. Hence, it makes sense to optimize this case.
If subsequent IGP events are received in a short period of time
(TIME_TO_LEARN_INTERVAL), we then assume that a single component
failed, but that this failure requires the knowledge of multiple IGP
events in order for IGP routing to converge. Under this assumption,
we want fast convergence since this is a normal network situation.
However, there is a benefit in waiting for all IGP events related to
this single component failure: the IGP can then compute the post-
failure routing table in a single additional route computation. In
this situation, we delay the routing computation by SHORT_SPF_DELAY.
If IGP events are still received after TIME_TO_LEARN_INTERVAL from
the initial IGP event received in QUIET state (see <a href="#section-5.1">Section 5.1</a>), then
the network is presumably experiencing multiple independent failures.
In this case, while waiting for network stability, the computations
are delayed for a longer time, which is represented by
LONG_SPF_DELAY. This SPF delay is used until no IGP events are
received for HOLDDOWN_INTERVAL.
<span class="grey">Decraene, et al. Standards Track [Page 5]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span>
<span class="grey"><a href="./rfc8405">RFC 8405</a> SPF Back-Off Delay Algorithm June 2018</span>
Note that in order to increase the consistency network wide, the
algorithm uses a delay (TIME_TO_LEARN_INTERVAL) from the initial IGP
event rather than the number of SPF computations performed. Indeed,
as all routers may receive the IGP events at different times, we
cannot assume that all routers will perform the same number of SPF
computations. For example, assuming that the SPF delay is 50
milliseconds, router R1 may receive three IGP events (E1, E2, E3) in
those 50 milliseconds and hence will perform a single routing
computation, while another router R2 may only receive two events (E1,
E2) in those 50 milliseconds and hence will schedule another routing
computation when receiving E3.
<span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a>. Specification of the SPF Delay State Machine</span>
This section specifies the Finite State Machine (FSM) intended to
control the timing of the execution of SPF calculations in response
to IGP events.
<span class="h3"><a class="selflink" id="section-5.1" href="#section-5.1">5.1</a>. State Machine</span>
The FSM is initialized to the QUIET state with all three timers
(SPF_TIMER, HOLDDOWN_TIMER, and LEARN_TIMER) deactivated.
The events that may change the FSM states are an IGP event or the
expiration of one timer (SPF_TIMER, HOLDDOWN_TIMER, or LEARN_TIMER).
The following diagram briefly describes the state transitions.
<span class="grey">Decraene, et al. Standards Track [Page 6]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span>
<span class="grey"><a href="./rfc8405">RFC 8405</a> SPF Back-Off Delay Algorithm June 2018</span>
+-------------------+
+---->| |<-------------------+
| | QUIET | |
+-----| |<---------+ |
7: +-------------------+ | |
SPF_TIMER | | |
expiration | | |
| 1: IGP event | |
| | |
v | |
+-------------------+ | |
+---->| | | |
| | SHORT_WAIT |----->----+ |
+-----| | |
2: +-------------------+ 6: HOLDDOWN_TIMER |
IGP event | expiration |
8: SPF_TIMER | |
expiration | |
| 3: LEARN_TIMER |
| expiration |
| |
v |
+-------------------+ |
+---->| | |
| | LONG_WAIT |------------>-------+
+-----| |
4: +-------------------+ 5: HOLDDOWN_TIMER
IGP event expiration
9: SPF_TIMER expiration
Figure 1: State Machine
<span class="h3"><a class="selflink" id="section-5.2" href="#section-5.2">5.2</a>. States</span>
The naming and semantics of each state corresponds directly to the
SPF delay used for IGP events received in that state. Three states
are defined:
QUIET: This is the initial state, when no IGP events have occurred
for at least HOLDDOWN_INTERVAL since the last routing table
computation. The state is meant to handle link failures very
quickly.
SHORT_WAIT: This is the state entered when an IGP event has been
received in QUIET state. This state is meant to handle a single
component failure requiring multiple IGP events (e.g., node, SRLG).
<span class="grey">Decraene, et al. Standards Track [Page 7]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span>
<span class="grey"><a href="./rfc8405">RFC 8405</a> SPF Back-Off Delay Algorithm June 2018</span>
LONG_WAIT: This is the state reached after TIME_TO_LEARN_INTERVAL in
state SHORT_WAIT. This state is meant to handle multiple independent
component failures during periods of IGP instability.
<span class="h3"><a class="selflink" id="section-5.3" href="#section-5.3">5.3</a>. Timers</span>
SPF_TIMER: This is the FSM timer that uses the computed SPF delay.
Upon expiration, the routing table computation (as defined in
<a href="#section-3">Section 3</a>) is performed.
HOLDDOWN_TIMER: This is the FSM timer that is (re)started when an IGP
event is received and set to HOLDDOWN_INTERVAL. Upon expiration, the
FSM is moved to the QUIET state.
LEARN_TIMER: This is the FSM timer that is started when an IGP event
is received while the FSM is in the QUIET state. Upon expiration,
the FSM is moved to the LONG_WAIT state.
<span class="h3"><a class="selflink" id="section-5.4" href="#section-5.4">5.4</a>. FSM Events</span>
This section describes the events and the actions performed in
response.
Transition 1: IGP event while in QUIET state
Actions on event 1:
o If SPF_TIMER is not already running, start it with value
INITIAL_SPF_DELAY.
o Start LEARN_TIMER with TIME_TO_LEARN_INTERVAL.
o Start HOLDDOWN_TIMER with HOLDDOWN_INTERVAL.
o Transition to SHORT_WAIT state.
Transition 2: IGP event while in SHORT_WAIT
Actions on event 2:
o Reset HOLDDOWN_TIMER to HOLDDOWN_INTERVAL.
o If SPF_TIMER is not already running, start it with value
SHORT_SPF_DELAY.
o Remain in current state.
<span class="grey">Decraene, et al. Standards Track [Page 8]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span>
<span class="grey"><a href="./rfc8405">RFC 8405</a> SPF Back-Off Delay Algorithm June 2018</span>
Transition 3: LEARN_TIMER expiration
Actions on event 3:
o Transition to LONG_WAIT state.
Transition 4: IGP event while in LONG_WAIT
Actions on event 4:
o Reset HOLDDOWN_TIMER to HOLDDOWN_INTERVAL.
o If SPF_TIMER is not already running, start it with value
LONG_SPF_DELAY.
o Remain in current state.
Transition 5: HOLDDOWN_TIMER expiration while in LONG_WAIT
Actions on event 5:
o Transition to QUIET state.
Transition 6: HOLDDOWN_TIMER expiration while in SHORT_WAIT
Actions on event 6:
o Deactivate LEARN_TIMER.
o Transition to QUIET state.
Transition 7: SPF_TIMER expiration while in QUIET
Actions on event 7:
o Compute SPF.
o Remain in current state.
<span class="grey">Decraene, et al. Standards Track [Page 9]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span>
<span class="grey"><a href="./rfc8405">RFC 8405</a> SPF Back-Off Delay Algorithm June 2018</span>
Transition 8: SPF_TIMER expiration while in SHORT_WAIT
Actions on event 8:
o Compute SPF.
o Remain in current state.
Transition 9: SPF_TIMER expiration while in LONG_WAIT
Actions on event 9:
o Compute SPF.
o Remain in current state.
<span class="h2"><a class="selflink" id="section-6" href="#section-6">6</a>. Parameters</span>
All the parameters MUST be configurable at the protocol instance
level. They MAY be configurable on a per IGP LSDB basis (e.g., IS-IS
level, OSPF area, or IS-IS Level 1 area). All the delays
(INITIAL_SPF_DELAY, SHORT_SPF_DELAY, LONG_SPF_DELAY,
TIME_TO_LEARN_INTERVAL, and HOLDDOWN_INTERVAL) SHOULD be configurable
with a granularity of a millisecond. They MUST be configurable with
a granularity of at least a tenth of a second. The configurable
range for all the parameters SHOULD be from 0 milliseconds to at
least 6000 milliseconds. The HOLDDOWN_INTERVAL MUST be defaulted or
configured to be longer than the TIME_TO_LEARN_INTERVAL.
If this SPF Back-Off algorithm is enabled by default, then in order
to have consistent SPF delays between implementations with default
configuration, the following default values SHOULD be implemented:
INITIAL_SPF_DELAY 50 ms
SHORT_SPF_DELAY 200 ms
LONG_SPF_DELAY 5000 ms
TIME_TO_LEARN_INTERVAL 500 ms
HOLDDOWN_INTERVAL 10000 ms
In order to satisfy the goals stated in <a href="#section-2">Section 2</a>, operators are
RECOMMENDED to configure delay intervals such that INITIAL_SPF_DELAY
<= SHORT_SPF_DELAY and SHORT_SPF_DELAY <= LONG_SPF_DELAY.
When setting (default) values, one should consider the customers and
their application requirements, the computational power of the
routers, the size of the network as determined primarily by the
number of IP prefixes advertised in the IGP, the frequency and number
<span class="grey">Decraene, et al. Standards Track [Page 10]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span>
<span class="grey"><a href="./rfc8405">RFC 8405</a> SPF Back-Off Delay Algorithm June 2018</span>
of IGP events, and the number of protocol reactions/computations
triggered by IGP SPF computation (e.g., BGP, Path Computation Element
Communication Protocol (PCEP), Traffic Engineering Constrained SPF
(CSPF), and Fast Reroute computations). Note that some or all of
these factors may change over the life of the network. In case of
doubt, it's RECOMMENDED that timer intervals should be chosen
conservatively (i.e., longer timer values).
For the standard algorithm to be effective in mitigating micro-loops,
it is RECOMMENDED that all routers in the IGP domain, or at least all
the routers in the same area/level, have exactly the same configured
values.
<span class="h2"><a class="selflink" id="section-7" href="#section-7">7</a>. Partial Deployment</span>
In general, the SPF Back-Off Delay algorithm is only effective in
mitigating micro-loops if it is deployed with the same parameters on
all routers in the IGP domain or, at least, all routers in an IGP
area/level. The impact of partial deployment is dependent on the
particular event, the topology, and the algorithm(s) used on other
routers in the IGP area/level. In cases where the previous SPF Back-
Off Delay algorithm was implemented uniformly, partial deployment
will increase the frequency and duration of micro-loops. Hence, it
is RECOMMENDED that all routers in the IGP domain, or at least within
the same area/level, be migrated to the SPF algorithm described
herein at roughly the same time.
Note that this is not a new consideration; over time, network
operators have changed SPF delay parameters in order to accommodate
new customer requirements for fast convergence, as permitted by new
software and hardware. They may also have progressively replaced an
implementation using a given SPF Back-Off Delay algorithm with
another implementation using a different one.
<span class="h2"><a class="selflink" id="section-8" href="#section-8">8</a>. Impact on Micro-loops</span>
Micro-loops during IGP convergence are due to a non-synchronized or
non-ordered update of FIBs [<a href="./rfc5715" title=""A Framework for Loop-Free Convergence"">RFC5715</a>] [<a href="./rfc6976" title=""Framework for Loop-Free Convergence Using the Ordered Forwarding Information Base (oFIB) Approach"">RFC6976</a>] [<a href="#ref-SPF-MICRO">SPF-MICRO</a>]. FIBs are
installed after multiple steps, such as flooding of the IGP event
across the network, SPF wait time, SPF computation, FIB distribution
across line cards, and FIB update. This document only addresses the
contribution from the SPF wait time. This standardized procedure
reduces the probability and/or duration of micro-loops when IGPs
experience multiple temporally close events. It does not prevent all
micro-loops; however, it is beneficial and is less complex and costly
to implement when compared to full solutions such as Distributed
Tunnels [<a href="./rfc5715" title=""A Framework for Loop-Free Convergence"">RFC5715</a>], Synchronized FIB Update [<a href="./rfc5715" title=""A Framework for Loop-Free Convergence"">RFC5715</a>], or the ordered
FIB approach [<a href="./rfc6976" title=""Framework for Loop-Free Convergence Using the Ordered Forwarding Information Base (oFIB) Approach"">RFC6976</a>].
<span class="grey">Decraene, et al. Standards Track [Page 11]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-12" ></span>
<span class="grey"><a href="./rfc8405">RFC 8405</a> SPF Back-Off Delay Algorithm June 2018</span>
<span class="h2"><a class="selflink" id="section-9" href="#section-9">9</a>. IANA Considerations</span>
This document has no IANA actions.
<span class="h2"><a class="selflink" id="section-10" href="#section-10">10</a>. Security Considerations</span>
The algorithm presented in this document does not compromise IGP
security. An attacker having the ability to generate IGP events
would be able to delay the IGP convergence time. The LONG_SPF_DELAY
state may help mitigate the effects of Denial-of-Service (DoS)
attacks generating many IGP events.
<span class="h2"><a class="selflink" id="section-11" href="#section-11">11</a>. References</span>
<span class="h3"><a class="selflink" id="section-11.1" href="#section-11.1">11.1</a>. Normative References</span>
[<a id="ref-RFC2119">RFC2119</a>] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", <a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a>, <a href="./rfc2119">RFC 2119</a>,
DOI 10.17487/RFC2119, March 1997,
<<a href="https://www.rfc-editor.org/info/rfc2119">https://www.rfc-editor.org/info/rfc2119</a>>.
[<a id="ref-RFC8174">RFC8174</a>] Leiba, B., "Ambiguity of Uppercase vs Lowercase in <a href="./rfc2119">RFC</a>
<a href="./rfc2119">2119</a> Key Words", <a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a>, <a href="./rfc8174">RFC 8174</a>, DOI 10.17487/RFC8174,
May 2017, <<a href="https://www.rfc-editor.org/info/rfc8174">https://www.rfc-editor.org/info/rfc8174</a>>.
<span class="h3"><a class="selflink" id="section-11.2" href="#section-11.2">11.2</a>. Informative References</span>
[<a id="ref-ISO10589">ISO10589</a>]
International Organization for Standardization,
"Information technology -- Telecommunications and
information exchange between systems -- Intermediate
System to Intermediate System intra-domain routeing
information exchange protocol for use in conjunction with
the protocol for providing the connectionless-mode network
service (ISO 8473)", ISO/IEC 10589:2002, Second Edition,
November 2002.
[<a id="ref-RFC2328">RFC2328</a>] Moy, J., "OSPF Version 2", STD 54, <a href="./rfc2328">RFC 2328</a>,
DOI 10.17487/RFC2328, April 1998,
<<a href="https://www.rfc-editor.org/info/rfc2328">https://www.rfc-editor.org/info/rfc2328</a>>.
[<a id="ref-RFC3209">RFC3209</a>] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V.,
and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP
Tunnels", <a href="./rfc3209">RFC 3209</a>, DOI 10.17487/RFC3209, December 2001,
<<a href="https://www.rfc-editor.org/info/rfc3209">https://www.rfc-editor.org/info/rfc3209</a>>.
<span class="grey">Decraene, et al. Standards Track [Page 12]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-13" ></span>
<span class="grey"><a href="./rfc8405">RFC 8405</a> SPF Back-Off Delay Algorithm June 2018</span>
[<a id="ref-RFC4271">RFC4271</a>] Rekhter, Y., Ed., Li, T., Ed., and S. Hares, Ed., "A
Border Gateway Protocol 4 (BGP-4)", <a href="./rfc4271">RFC 4271</a>,
DOI 10.17487/RFC4271, January 2006,
<<a href="https://www.rfc-editor.org/info/rfc4271">https://www.rfc-editor.org/info/rfc4271</a>>.
[<a id="ref-RFC5036">RFC5036</a>] Andersson, L., Ed., Minei, I., Ed., and B. Thomas, Ed.,
"LDP Specification", <a href="./rfc5036">RFC 5036</a>, DOI 10.17487/RFC5036,
October 2007, <<a href="https://www.rfc-editor.org/info/rfc5036">https://www.rfc-editor.org/info/rfc5036</a>>.
[<a id="ref-RFC5286">RFC5286</a>] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for
IP Fast Reroute: Loop-Free Alternates", <a href="./rfc5286">RFC 5286</a>,
DOI 10.17487/RFC5286, September 2008,
<<a href="https://www.rfc-editor.org/info/rfc5286">https://www.rfc-editor.org/info/rfc5286</a>>.
[<a id="ref-RFC5340">RFC5340</a>] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF
for IPv6", <a href="./rfc5340">RFC 5340</a>, DOI 10.17487/RFC5340, July 2008,
<<a href="https://www.rfc-editor.org/info/rfc5340">https://www.rfc-editor.org/info/rfc5340</a>>.
[<a id="ref-RFC5715">RFC5715</a>] Shand, M. and S. Bryant, "A Framework for Loop-Free
Convergence", <a href="./rfc5715">RFC 5715</a>, DOI 10.17487/RFC5715, January
2010, <<a href="https://www.rfc-editor.org/info/rfc5715">https://www.rfc-editor.org/info/rfc5715</a>>.
[<a id="ref-RFC6976">RFC6976</a>] 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", <a href="./rfc6976">RFC 6976</a>, DOI 10.17487/RFC6976, July
2013, <<a href="https://www.rfc-editor.org/info/rfc6976">https://www.rfc-editor.org/info/rfc6976</a>>.
[<a id="ref-SPF-MICRO">SPF-MICRO</a>]
Litkowski, S., Decraene, B., and M. Horneffer, "Link State
protocols SPF trigger and delay algorithm impact on IGP
micro-loops", Work in Progress, <a href="./draft-ietf-rtgwg-spf-uloop-pb-statement-07">draft-ietf-rtgwg-spf-</a>
<a href="./draft-ietf-rtgwg-spf-uloop-pb-statement-07">uloop-pb-statement-07</a>, May 2018.
<span class="grey">Decraene, et al. Standards Track [Page 13]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-14" ></span>
<span class="grey"><a href="./rfc8405">RFC 8405</a> SPF Back-Off Delay Algorithm June 2018</span>
Acknowledgements
We would like to acknowledge Les Ginsberg, Uma Chunduri, Mike Shand,
and Alexander Vainshtein for the discussions and comments related to
this document.
Authors' Addresses
Bruno Decraene
Orange
Email: bruno.decraene@orange.com
Stephane Litkowski
Orange Business Service
Email: stephane.litkowski@orange.com
Hannes Gredler
RtBrick Inc.
Email: hannes@rtbrick.com
Acee Lindem
Cisco Systems
301 Midenhall Way
Cary, NC 27513
United States of America
Email: acee@cisco.com
Pierre Francois
Email: pfrpfr@gmail.com
Chris Bowers
Juniper Networks, Inc.
1194 N. Mathilda Ave.
Sunnyvale, CA 94089
United States of America
Email: cbowers@juniper.net
Decraene, et al. Standards Track [Page 14]
</pre>
|
