< draft-ietf-rtgwg-backoff-algo-03.txt   draft-ietf-rtgwg-backoff-algo-04.txt >
Network Working Group B. Decraene Network Working Group B. Decraene
Internet-Draft Orange Internet-Draft Orange
Intended status: Standards Track S. Litkowski Intended status: Standards Track S. Litkowski
Expires: January 5, 2017 Orange Business Service Expires: July 13, 2017 Orange Business Service
H. Gredler H. Gredler
RtBrick Inc RtBrick Inc
A. Lindem A. Lindem
P. Francois
Cisco Systems Cisco Systems
P. Francois
C. Bowers C. Bowers
Juniper Networks, Inc. Juniper Networks, Inc.
July 4, 2016 January 9, 2017
SPF Back-off algorithm for link state IGPs SPF Back-off algorithm for link state IGPs
draft-ietf-rtgwg-backoff-algo-03 draft-ietf-rtgwg-backoff-algo-04
Abstract Abstract
This document defines a standard algorithm to back-off link-state IGP This document defines a standard algorithm to back-off link-state IGP
SPF computations. SPF computations.
Having one standard algorithm improves interoperability by reducing Having one standard algorithm improves interoperability by reducing
the probability and/or duration of transient forwarding loops during the probability and/or duration of transient forwarding loops during
the IGP convergence when the IGP reacts to multiple proximate IGP the IGP convergence when the IGP reacts to multiple proximate IGP
events. events.
skipping to change at page 2, line 4 skipping to change at page 2, line 4
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on January 5, 2017. This Internet-Draft will expire on July 13, 2017.
Copyright Notice Copyright Notice
Copyright (c) 2016 IETF Trust and the persons identified as the Copyright (c) 2017 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
skipping to change at page 5, line 18 skipping to change at page 5, line 18
it makes sense to optimize this case. it makes sense to optimize this case.
If subsequent IGP events are received in a short period of time If subsequent IGP events are received in a short period of time
(TIME_TO_LEARN_INTERVAL), we then assume that a single component (TIME_TO_LEARN_INTERVAL), we then assume that a single component
failed, but that this failure requires the knowledge of multiple IGP failed, but that this failure requires the knowledge of multiple IGP
events in order for IGP routing to converge. Under this assumption, events in order for IGP routing to converge. Under this assumption,
we want fast convergence since this is a normal network situation. we want fast convergence since this is a normal network situation.
However, there is a benefit in waiting for all IGP events related to However, there is a benefit in waiting for all IGP events related to
this single component failure so that the IGP can compute the post- this single component failure so that the IGP can compute the post-
failure routing table in a single route computation. In this failure routing table in a single route computation. In this
situation, we delay the routing computation by LONG_WAIT. situation, we delay the routing computation by SHORT_SPF_DELAY.
If IGP events are still received after TIME_TO_LEARN_INTERVAL from If IGP events are still received after TIME_TO_LEARN_INTERVAL from
the initial IGP event received in QUIET state, then the network is the initial IGP event received in QUIET state, then the network is
presumably experiencing multiple independent failures. In this case, presumably experiencing multiple independent failures. In this case,
while waiting for network stability, the computations are delayed for while waiting for network stability, the computations are delayed for
a longer time represented by LONG_SPF_DELAY. This SPF delay is kept a longer time represented by LONG_SPF_DELAY. This SPF delay is kept
until no IGP events are received for HOLDDOWN_INTERVAL. until no IGP events are received for HOLDDOWN_INTERVAL.
Note that previous SPF delay algorithms used to count the number of Note that previous SPF delay algorithms used to count the number of
SPF computations. However, as all routers may receive the IGP events SPF computations. However, as all routers may receive the IGP events
skipping to change at page 6, line 6 skipping to change at page 6, line 6
This section describes the state machine. The naming and semantics This section describes the state machine. The naming and semantics
of each state corresponds directly to the SPF delay used for IGP of each state corresponds directly to the SPF delay used for IGP
events received in that state. Three states are defined: events received in that state. Three states are defined:
QUIET: This is the initial state, when no IGP events have occured for QUIET: This is the initial state, when no IGP events have occured for
at least HOLDDOWN_INTERVAL since the previous routing table at least HOLDDOWN_INTERVAL since the previous routing table
computation. The state is meant to handle link failures very computation. The state is meant to handle link failures very
quickly. quickly.
SHORT_WAIT: State entered when an IGP event has been received in SHORT_WAIT: State entered when an IGP event has been received in
QUIET state and exited when no IGP events have been received for QUIET state. This state is meant to handle single component failure
HOLDDOWN_TIMER. This state is meant to handle single component requiring multiple IGP events (e.g., node, SRLG).
failure requiring multiple IGP events (e.g., node, SRLG).
LONG_WAIT: State reached after TIME_TO_LEARN_INTERVAL. In other LONG_WAIT: State reached after TIME_TO_LEARN_INTERVAL. In other
words, state reached after TIME_TO_LEARN_INTERVAL in state words, state reached after TIME_TO_LEARN_INTERVAL in state
SHORT_WAIT. This state is meant to handle multiple independent SHORT_WAIT. This state is meant to handle multiple independent
component failures during periods of IGP instability. component failures during periods of IGP instability.
5.2. States Transitions 5.2. States Transitions
The FSM is initialized to the QUIET_STATE with all three timers The FSM is initialized to the QUIET_STATE with all three timers
deactivated. The following diagram describes briefly the state deactivated. The following diagram describes briefly the state
skipping to change at page 7, line 10 skipping to change at page 7, line 10
4: +-------------------+ 5: HOLDDOWN_TIMER 4: +-------------------+ 5: HOLDDOWN_TIMER
IGP event expiration IGP event expiration
Figure 1: State Machine Figure 1: State Machine
5.3. FSM Events 5.3. FSM Events
This section describes the events and the actions performed in This section describes the events and the actions performed in
response. response.
Event 1: IGP events, while in QUIET_STATE. Event 1: IGP event, while in QUIET_STATE.
Actions on event 1: Actions on event 1:
o If SPF_TIMER is not already running, start it with value o If SPF_TIMER is not already running, start it with value
INITIAL_SPF_DELAY. INITIAL_SPF_DELAY.
o Start LEARN_TIMER with TIME_TO_LEARN_INTERVAL. o Start LEARN_TIMER with TIME_TO_LEARN_INTERVAL.
o Start HOLDDOWN_TIMER with HOLDDOWN_INTERVAL. o Start HOLDDOWN_TIMER with HOLDDOWN_INTERVAL.
o Transition to SHORT_WAIT state. o Transition to SHORT_WAIT state.
Event 2: IGP events, while in SHORT_WAIT. Event 2: IGP event, while in SHORT_WAIT.
Actions on event 2: Actions on event 2:
o Reset HOLDDOWN_TIMER to HOLDDOWN_INTERVAL. o Reset HOLDDOWN_TIMER to HOLDDOWN_INTERVAL.
o If SPF_TIMER is not already running, start it with value o If SPF_TIMER is not already running, start it with value
SHORT_SPF_DELAY. SHORT_SPF_DELAY.
o Remain in current state. o Remain in current state.
Event 3: LEARN_TIMER expiration. Event 3: LEARN_TIMER expiration.
Actions on event 3: Actions on event 3:
o Transition to LONG_WAIT state. o Transition to LONG_WAIT state.
Event 4: IGP events, while in LONG_WAIT. Event 4: IGP event, while in LONG_WAIT.
Actions on event 4: Actions on event 4:
o Reset HOLDDOWN_TIMER to HOLDDOWN_INTERVAL. o Reset HOLDDOWN_TIMER to HOLDDOWN_INTERVAL.
o If SPF_TIMER is not already running, start it with value o If SPF_TIMER is not already running, start it with value
LONG_SPF_DELAY. LONG_SPF_DELAY.
o Remain in current state. o Remain in current state.
skipping to change at page 11, line 13 skipping to change at page 11, line 13
Email: hannes@rtbrick.com Email: hannes@rtbrick.com
Acee Lindem Acee Lindem
Cisco Systems Cisco Systems
301 Midenhall Way 301 Midenhall Way
Cary, NC 27513 Cary, NC 27513
USA USA
Email: acee@cisco.com Email: acee@cisco.com
Pierre Francois Pierre Francois
Cisco Systems
Email: pifranco@cisco.com Email: pfrpfr@gmail.com
Chris Bowers Chris Bowers
Juniper Networks, Inc. Juniper Networks, Inc.
1194 N. Mathilda Ave. 1194 N. Mathilda Ave.
Sunnyvale, CA 94089 Sunnyvale, CA 94089
US US
Email: cbowers@juniper.net Email: cbowers@juniper.net
 End of changes. 14 change blocks. 
15 lines changed or deleted 14 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/