< draft-cc-lsr-flooding-reduction-03.txt   draft-cc-lsr-flooding-reduction-04.txt >
Network Working Group H. Chen Network Working Group H. Chen
Internet-Draft D. Cheng Internet-Draft Futurewei
Intended status: Standards Track Huawei Technologies Intended status: Standards Track D. Cheng
Expires: September 12, 2019 M. Toy Expires: January 8, 2020 Individual
M. Toy
Verizon Verizon
Y. Yang Y. Yang
IBM IBM
A. Wang A. Wang
China Telecom China Telecom
X. Liu X. Liu
Volta Networks Volta Networks
Y. Fan Y. Fan
Casa Systems Casa Systems
L. Liu L. Liu
March 11, 2019 Fujitsu
July 7, 2019
LS Distributed Flooding Reduction Flooding Topology Computation Algorithm
draft-cc-lsr-flooding-reduction-03 draft-cc-lsr-flooding-reduction-04
Abstract Abstract
This document proposes an approach to flood link states on a topology This document proposes an algorithm for a node to compute a flooding
that is a subgraph of the complete topology per underline physical topology, which is a subgraph of the complete topology per underline
network, so that the amount of flooding traffic in the network is physical network. When every node in an area automatically
greatly reduced, and it would reduce convergence time with a more calculates a flooding topology by using a same algorithm and floods
stable and optimized routing environment. The approach can be the link states using the flooding topology, the amount of flooding
applied to any network topology in a single area. In this approach, traffic in the network is greatly reduced. This would reduce
every node in the area automatically calculates a flooding topology convergence time with a more stable and optimized routing
by using a same algorithm concurrently. environment.
Requirements Language Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119]. document are to be interpreted as described in RFC 2119 [RFC2119].
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
skipping to change at page 2, line 10 skipping to change at page 2, line 10
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 https://datatracker.ietf.org/drafts/current/. Drafts is at https://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 September 12, 2019. This Internet-Draft will expire on January 8, 2020.
Copyright Notice Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2019 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
(https://trustee.ietf.org/license-info) in effect on the date of (https://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
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Flooding Topology . . . . . . . . . . . . . . . . . . . . . . 4 3. Flooding Topology . . . . . . . . . . . . . . . . . . . . . . 3
3.1. Flooding Topology Construction . . . . . . . . . . . . . 4 3.1. Flooding Topology Construction . . . . . . . . . . . . . 3
3.2. Scheduling for Flooding Topology Computation . . . . . . 5 4. Algorithms to Compute Flooding Topology . . . . . . . . . . . 4
3.2.1. Scheduler with Exponential Delay . . . . . . . . . . 6 4.1. Algorithm with Considering Degree . . . . . . . . . . . . 5
3.2.2. Scheduler with Constant Delay . . . . . . . . . . . . 6 4.2. Algorithm with Considering Others . . . . . . . . . . . . 5
3.3. Flooding Topology Consistency . . . . . . . . . . . . . . 7 5. Security Considerations . . . . . . . . . . . . . . . . . . . 6
3.4. Flooding Topology Protection . . . . . . . . . . . . . . 7 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6
4. Protocol Extensions . . . . . . . . . . . . . . . . . . . . . 8 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 7
4.1. Extensions for Operations . . . . . . . . . . . . . . . . 8 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.1.1. Extensions to OSPF . . . . . . . . . . . . . . . . . 8 8.1. Normative References . . . . . . . . . . . . . . . . . . 7
4.1.2. Extensions to IS-IS . . . . . . . . . . . . . . . . . 10 8.2. Informative References . . . . . . . . . . . . . . . . . 7
4.2. Extensions for Consistency . . . . . . . . . . . . . . . 11 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 7
4.2.1. Extensions to OSPF . . . . . . . . . . . . . . . . . 11
4.2.2. Extensions to IS-IS . . . . . . . . . . . . . . . . . 12
5. Flooding Behavior . . . . . . . . . . . . . . . . . . . . . . 12
5.1. Nodes Perform Flooding Reduction without Failure . . . . 13
5.1.1. Receiving an LS . . . . . . . . . . . . . . . . . . . 13
5.1.2. Originating an LS . . . . . . . . . . . . . . . . . . 13
5.1.3. Establishing Adjacencies . . . . . . . . . . . . . . 13
5.2. An Exception Case . . . . . . . . . . . . . . . . . . . . 14
5.2.1. Multiple Failures . . . . . . . . . . . . . . . . . . 14
5.2.2. Changes on Flooding Topology . . . . . . . . . . . . 14
6. Operations on Flooding Reduction . . . . . . . . . . . . . . 15
6.1. Configuring Flooding Reduction . . . . . . . . . . . . . 15
6.1.1. Configurations for Distributed Flooding Reduction . . 15
6.2. Migration to Flooding Reduction . . . . . . . . . . . . . 15
6.2.1. Migration to Distributed Flooding Reduction . . . . . 15
6.3. Roll Back to Normal Flooding . . . . . . . . . . . . . . 15
7. Manageability Considerations . . . . . . . . . . . . . . . . 16
8. Security Considerations . . . . . . . . . . . . . . . . . . . 16
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16
9.1. OSPF . . . . . . . . . . . . . . . . . . . . . . . . . . 16
9.2. IS-IS . . . . . . . . . . . . . . . . . . . . . . . . . . 17
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 17
11. References . . . . . . . . . . . . . . . . . . . . . . . . . 17
11.1. Normative References . . . . . . . . . . . . . . . . . . 17
11.2. Informative References . . . . . . . . . . . . . . . . . 18
Appendix A. Algorithms to Build Flooding Topology . . . . . . . 19
A.1. Algorithms to Build Tree without Considering Others . . . 19
A.2. Algorithms to Build Tree Considering Others . . . . . . . 20
A.3. Connecting Leaves . . . . . . . . . . . . . . . . . . . . 22
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 23
1. Introduction 1. Introduction
For some networks such as dense Data Center (DC) networks, the For some networks such as dense Data Center (DC) networks, the
existing Link State (LS) flooding mechanism is not efficient and may existing Link State (LS) flooding mechanism is not efficient and may
have some issues. The extra LS flooding consumes network bandwidth. have some issues. The extra LS flooding consumes network bandwidth.
Processing the extra LS flooding, including receiving, buffering and Processing the extra LS flooding, including receiving, buffering and
decoding the extra LSs, wastes memory space and processor time. This decoding the extra LSs, wastes memory space and processor time. This
may cause scalability issues and affect the network convergence may cause scalability issues and affect the network convergence
negatively. negatively.
This document proposes an approach to minimize the amount of flooding This document proposes an algorithm for a node to compute a flooding
traffic in the network. Thus the workload for processing the extra topology, which is a subgraph of the complete topology per underline
LS flooding is decreased significantly. This would improve the physical network. When every node in an area automatically
scalability, speed up the network convergence, stable and optimize calculates a flooding topology by using a same algorithm and floods
the routing environment. the link states using the flooding topology, the amount of flooding
traffic in the network is greatly reduced. This would reduce
convergence time with a more stable and optimized routing
environment.
In this approach, every node in the network automatically calculates
a flooding topology by using a same algorithm concurrently at almost
the same time. It floods a link state on the flooding topology.
There may be multiple algorithms for computing a flooding topology. There may be multiple algorithms for computing a flooding topology.
Users can select one they prefer, and smoothly switch from one to Users can select one they prefer, and smoothly switch from one to
another. The approach is applicable to any network topology in a another.
single area. It is backward compatible.
2. Terminology 2. Terminology
LSA: A Link State Advertisement in OSPF. LSA: A Link State Advertisement in OSPF.
LSP: A Link State Protocol Data Unit (PDU) in IS-IS. LSP: A Link State Protocol Data Unit (PDU) in IS-IS.
LS: A Link Sate, which is an LSA or LSP. LS: A Link Sate, which is an LSA or LSP.
FT: Flooding Topology.
FTC: Flooding Topology Computation. FTC: Flooding Topology Computation.
3. Flooding Topology 3. Flooding Topology
For a given network topology, a flooding topology is a sub-graph or For a given network topology, a flooding topology is a sub-graph or
sub-network of the given network topology that has the same sub-network of the given network topology that has the same
reachability to every node as the given network topology. Thus all reachability to every node as the given network topology. Thus all
the nodes in the given network topology MUST be in the flooding the nodes in the given network topology MUST be in the flooding
topology. All the nodes MUST be inter-connected directly or topology. All the nodes MUST be inter-connected directly or
indirectly. As a result, LS flooding will in most cases occur only indirectly. As a result, LS flooding will in most cases occur only
on the flooding topology, that includes all nodes but a subset of on the flooding topology, that includes all nodes but a subset of
links. Note even though the flooding topology is a sub-graph of the links. Note even though the flooding topology is a sub-graph of the
original topology, any single LS MUST still be disseminated in the original topology, any single LS MUST still be disseminated in the
entire network. entire network.
3.1. Flooding Topology Construction 3.1. Flooding Topology Construction
Many different flooding topologies can be constructed for a given Many different flooding topologies can be constructed for a given
network topology. A chain connecting all the nodes in the given network topology. For example, a chain connecting all the nodes in
network topology is a flooding topology. A circle connecting all the the given network topology is a flooding topology. A circle
nodes is another flooding topology. A tree connecting all the nodes connecting all the nodes is another flooding topology. A tree
is a flooding topology. In addition, the tree plus the connections connecting all the nodes is a flooding topology. In addition, the
between some leaves of the tree and branch nodes of the tree is a tree plus the connections between some leaves of the tree and branch
flooding topology. nodes of the tree is a flooding topology.
The following parameters need to be considered for constructing a The following parameters need to be considered for constructing a
flooding topology: flooding topology:
o Degree: The degree of the flooding topology is the maximum degree
among the degrees of the nodes on the flooding topology. The
degree of a node on the flooding topology is the number of
connections on the flooding topology it has to other nodes.
o Number of links: The number of links on the flooding topology is a o Number of links: The number of links on the flooding topology is a
key factor for reducing the amount of LS flooding. In general, key factor for reducing the amount of LS flooding. In general,
the smaller the number of links, the less the amount of LS the smaller the number of links, the less the amount of LS
flooding. flooding.
o Diameter: The shortest distance between the two most distant nodes o Diameter: The diameter of the flooding topology is the shortest
on the flooding topology (i.e., the diameter of the flooding distance between the two most distant nodes on the flooding
topology) is a key factor for reducing the network convergence topology. It is a key factor for reducing the network convergence
time. The smaller the diameter, the less the convergence time. time. The smaller the diameter, the less the convergence time.
o Redundancy: The redundancy of the flooding topology means a o Redundancy: The redundancy of the flooding topology means a
tolerance to the failures of some links and nodes on the flooding tolerance to the failures of some links and nodes on the flooding
topology. If the flooding topology is split by some failures, it topology. If the flooding topology is split by some failures, it
is not tolerant to these failures. In general, the larger the is not tolerant to these failures. In general, the larger the
number of links on the flooding topology is, the more tolerant the number of links on the flooding topology is, the more tolerant the
flooding topology to failures. flooding topology to failures.
There are three different ways to construct a flooding topology for a
given network topology: centralized, distributed and static mode.
This document focuses on the distributed mode, in which each node in
the network automatically calculates a flooding topology by using a
same algorithm concurrently at almost the same time.
Note that the flooding topology constructed by a node is dynamic in Note that the flooding topology constructed by a node is dynamic in
nature, that means when the base topology (the entire topology graph) nature, that means when the base topology (the entire topology graph)
changes, the flooding topology (the sub-graph) MUST be re-computed/ changes, the flooding topology (the sub-graph) MUST be re-computed/
re-constructed to ensure that any node that is reachable on the base re-constructed to ensure that any node that is reachable on the base
topology MUST also be reachable on the flooding topology. topology MUST also be reachable on the flooding topology.
For reference purpose, some algorithms that allow nodes to 4. Algorithms to Compute Flooding Topology
automatically compute flooding topology are elaborated in Appendix A.
However, this document does not attempt to standardize how a flooding
topology is established.
3.2. Scheduling for Flooding Topology Computation
In a network consisting of routers from multiple vendors, there are
different schedulers for SPF. Using different schedulers is in favor
of creating more micro routing loops during the convergence process
due to discrepancies of schedulers than using a same scheduler. More
micro routing loops will lead to more traffic lose. Service
providers are already aware to use similar timers (values and
behavior), but sometimes it is not possible due to limitations of
schedulers [I-D.ietf-rtgwg-spf-uloop-pb-statement]. In order to let
every node run a flooding topology computation (FTC) at almost the
same time, we need to have a same scheduler for FTC to be implemented
by multiple vendors.
Two schedulers are described below. One uses a constant delay such
as 200ms for each of multiple consecutive FTCs. For example, for
four consecutive FTCs, the second FTC will be triggered 200ms after
the first FTC; the third FTC will be triggered 200ms after the second
FTC; and the forth FTC will be triggered 200ms after the third FTC.
The other uses an exponential delay starting from a given hold time
such as 100ms for consecutive FTCs. For example, for four
consecutive FTCs, the second FTC will be triggered 2 x 100ms = 200ms
after the first FTC; the third FTC will be triggered 2 x 200ms =
400ms after the second FTC; and the forth FTC will be triggered 2 x
400ms = 800ms after the second FTC.
If these two schedulers are used in a network, it is almost
impossible to let every node in the network run FTC at almost same
time for multiple consecutive FTCs.
3.2.1. Scheduler with Exponential Delay
There are three parameters for the scheduler: initial-delay, minimum-
hold-time and maximum-wait-time. The initial-delay is the delay in
milliseconds from detecting a topology change to triggering FTC. Its
default value is 50ms.
The minimum-hold-time is the minimum hold time in milliseconds
between two consecutive FTCs. Its default value is 100ms.
The maximum-wait-time is the maximum wait time in milliseconds for
triggering FTC. Its default value is 2000ms.
The behavior of the scheduler with these parameters is described as
follows:
1. When FTC is to be called first time, initial-delay for FTC.
2. When FTC is to be called n-th (n > 1) time consecutively,
delay T = minimum-hold-time x 2^(n-2) for FTC if T is less
than maximum-wait-time
3. When T = hold-time x 2^(n-2) reaches maximum-wait-time,
delay maximum-wait-time for FTC. Then repeats step 1
(i.e., the next FTC call is considered as first time again).
Scheduler with Exponential Delay
3.2.2. Scheduler with Constant Delay
There are three parameters for the scheduler: constant-delay, number-
of-runs and maximum-wait-time. The constant-delay is the constant
time to delay in milliseconds from detecting a topology change to
triggering FTC. Its default value is 200ms.
The number-of-runs is the maximum number of times that FTC can run
consecutively. Its default value is 5.
The maximum-wait-time is the maximum wait time in milliseconds for
triggering FTC. Its default value is 2000ms.
The behavior of the scheduler with these parameters is described as
follows:
1. When FTC is to be called first time, constant-delay for FTC.
2. When FTC is to be called n-th (n > 1) time consecutively,
delay constant-delay for FTC if n <= number-of-runs
3. If n == number-of-runs,
delay maximum-wait-time, and then repeats step 1
(i.e., the next FTC call is considered as first time again).
Scheduler with Constant Delay
3.3. Flooding Topology Consistency
The flooding topology computed by one node needs to be the same as
the one computed by another node. When two flooding topologies
computed by two nodes are different, this inconsistency needs to be
detected and handled accordingly.
3.4. Flooding Topology Protection
It is hard to construct a flooding topology that reduces the amount
of LS flooding greatly and is tolerant to multiple failures. Without
any protection against a flooding topology split when multiple
failures on the flooding topology happen, we may have a slow
convergence. It is better to have some simple and fast methods for
protecting the flooding topology split. Thus the convergence is not
slowed down.
In one way, when two or more failures on the current flooding
topology occur almost in the same time, each of the nodes within a
given distance (such as 3 hops) to a failure point, floods the link
state (LS) that it receives to all the links (except for the one from
which the LS is received) until a new flooding topology is built.
In other words, when the failures happen, each of the nodes within a
given distance to a failure point, adds all its local links to the
flooding topology temporarily until a new flooding topology is built.
In another way, each node computes and maintains a small number of
backup paths. For a backup path for a link L on the flooding
topology, a node N computes and maintains it only if the backup path
goes through node N. Node N stores the links (e.g., local link L1
and L2) attached to it and on the backup path. When link L fails and
there are one or more failures on the flooding topology (and
additionally the number of nodes collected through traversing the
flooding topology is less than the number of live nodes in the area),
node N adds the links (e.g., L1 and L2) to the flooding topology
temporarily until a new flooding topology is built. Note that
checking the additional condition will slow down the convergence when
the flooding topology is split. It is optional.
Suppose that the two end nodes of link L is A and B, and A's ID is
smaller than B's. Node N computes a path from A to B with minimum
hops and whose links are not on the flooding topology. This path is
a backup path for link L. A backup path can be computed before link
L fails or computed after link L fails and there is a need for it.
Using the former will make the convergence time shorter. For the
former, when the pre-computed backup path is broken because of
failures, a new backup path needs to be computed.
Similarly, for a backup path for a connection crossing a node M on
the flooding topology, a node N computes and maintains it only if the
backup path goes through node N. Node N stores the links (e.g.,
local link La and Lb) attached to it and on the backup path for node
M.
4. Protocol Extensions
The extensions comprises two parts: one part is for operations on
flooding reduction, the other is for flooding topology consistency.
4.1. Extensions for Operations
4.1.1. Extensions to OSPF
The OSPF Dynamic Flooding sub-TLV and area leader sub-TLV are defined
in [I-D.ietf-lsr-dynamic-flooding]. The former may contains a number
of algorithms. The latter contains instructions about flooding
reduction.
Every node supporting the distributed flooding reduction MUST
indicate its algorithms for flooding topology computation in a OSPF
Dynamic Flooding sub-TLV. This sub-TLV in a RI LSA will be
advertised to the area leader.
When the distributed flooding reduction is selected, every node MUST
receive the OSPF area leader sub-TLV in a RI LSA from the area
leader, which indicates the distributed mode and an algorithm to be
used. It SHOULD receive the parameters needed for the algorithm and
the distributed mode.
The parameters for the distributed mode include those three
parameters configured for the scheduler for flooding topology
computation. Through configuring these parameters on one place such
as the area leader and automatically advertising them to every node
in the network, we simplify the operation on flooding reduction and
reduce the errors on configurations (comparing to manually
configuring these parameters on every node).
A new sub-TLV, called OSPF Scheduler Parameters sub-TLV, is defined
for advertising the three parameters configured for the scheduler.
Its format is illustrated below.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type (TBD1) | Length (8) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| initial-delay | minimum-hold-time |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| maximum-wait-time | Reserved (MUST be zero) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
OSPF Scheduler Parameters sub-TLV
Type: TBD1 for Scheduler Parameters is to be assigned by IANA.
Length: 8.
initial-delay: 2 octets' field representing the initial delay in
milliseconds.
minimum-hold-time: 2 octets' field representing the minimum hold
time in milliseconds.
maximum-wait-time: 2 octets' field representing the maximum wait
time in milliseconds.
Reserved: MUST be set to 0 while sending and ignored on receipt.
In the case where the distributed flooding reduction is selected and
an algorithm for flooding topology computation is given already,
there are some operational changes. These changes include:
1 the algorithm given is changed to another algorithm;
2 the distributed flooding reduction is rolled back to normal
flooding; and
3 the distributed flooding reduction is changed to centralized
flooding reduction.
For the first change, every node MUST receive the OSPF area leader
sub-TLV in a RI LSA from the leader, which indicates that another
algorithm is to be used. After receiving the sub-TLV, it uses the
new algorithm to compute a new flooding topology, and floods link
states over both the flooding topology computed by the old algorithm
and the new flooding topology for a given time. And then it will
floods link states over the flooding topology computed by the new
algorithm.
For the second change, every node MUST receive the OSPF area leader
sub-TLV in a RI LSA from the leader, which indicates the current
flooding reduction is to be rolled back to normal flooding. After
receiving the sub-TLV, it stops computing flooding topology and
flooding link states over a flooding topology. It floods link states
using all its local links instead of the local links on the flooding
topology.
Note that the OSPF area leader sub-TLV defined in
[I-D.ietf-lsr-dynamic-flooding] needs to be extended to allow users
to roll back to normal flooding. The Flooding Reduction Instruction
sub-TLV defined in version 01 of this draft supports this.
4.1.2. Extensions to IS-IS
Similar to OSPF, the IS-IS Dynamic Flooding sub-TLV and area leader
sub-TLV are also defined in [I-D.ietf-lsr-dynamic-flooding].
Every node supporting the distributed flooding reduction MUST
indicate its algorithms for flooding topology computation in an IS-IS
Dynamic Flooding sub-TLV in an LSP to be advertised to the leader.
When the distributed flooding reduction is selected, every node MUST
receive the IS-IS area leader sub-TLV in an LSP, which indicates the
distributed mode and an algorithm to be used. It SHOULD receive the
parameters needed for the algorithm and the distributed mode.
A new sub-TLV, called IS-IS Scheduler Parameters sub-TLV, is defined
for advertising the three parameters configured for the scheduler.
Its format is illustrated below.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type (TBD2) | Length (8) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| initial-delay | minimum-hold-time |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| maximum-wait-time | Reserved (MUST be zero) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
IS-IS Scheduler Parameters sub-TLV
Type: TBD1 for Scheduler Parameters is to be assigned by IANA.
Length: 8.
initial-delay: 2 octets' field representing the initial delay in
milliseconds.
minimum-hold-time: 2 octets' field representing the minimum hold
time in milliseconds.
maximum-wait-time: 2 octets' field representing the maximum wait
time in milliseconds.
Reserved: MUST be set to 0 while sending and ignored on receipt.
4.2. Extensions for Consistency
4.2.1. Extensions to OSPF
RFC 5613 defines a TLV called Extended Options and Flag (EOF) TLV. A
OSPF Hello may contain this TLV in link-local signaling (LLS) data
block. A new flag bit (bit 30 suggested), called link on flooding
topology (FT-bit for short), is defined in EOF TLV.
When a node B receives a Hello from its adjacent node A over a link,
FT-bit set to one in the Hello indicates that the link is on the
flooding topology (FT) from node A's point of view.
For a link between node A and node B, not on the current FT, after
node A computes a new FT and the link is on the new FT, it sends a
Hello with FT-bit set to one to node B. Similarly, after node B
computes a new FT and the link is on the new FT, it sends a Hello
with FT-bit set to one to node A. Note that Hello may include FT-bit
after the state of the adjacency between A and B is FULL.
For a link between node A and node B, on the current FT, after node A
computes a new FT and the link is not on the new FT, it sends a Hello
with FT-bit set to zero to node B. Similarly, after node B computes
a new FT and the link is not on the new FT, it sends a Hello with FT-
bit set to zero to node A.
If the Hellos from the two nodes have the same FT-bit value, then the
FT for the link between the two nodes is consistent; otherwise, it is
not consistent.
If one of the two nodes receives the Hellos with FT-bit set to one
from the other, but sends the Hellos with FT-bit set to zero for a
number of Hellos such as 5 Hellos or a given time, then the FT for
the link between the two nodes is not consistent.
When an inconsistency on the FT for a link is detected, a warning is
issued or logged, and the node receiving the Hellos with FT-bit set
to one from the other node assumes that the link is on the FT
temporarily and floods the link states over the link.
4.2.2. Extensions to IS-IS
A new TLV, called Extended Options and Flag (EOF) TLV, is defined.
It may be included in an IS-IS Hello. Its format is shown below.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type (TBD) | Length (4) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Extended Options and Flags |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
EOF-TLV in IS-IS Hello
Similar to OSPF, a new flag bit (bit 31 suggested), called link on
flooding topology (FT-bit for short), is defined in EOF TLV. When a
node B receives a Hello from its adjacent node A over a link, FT-bit
set to one in the Hello indicates that the link is on the FT from
node A's point of view.
5. Flooding Behavior
This section describes the revised flooding behavior for a node. The
revised flooding procedure MUST flood an LS to every node in the
network in any case, as the standard flooding procedure does.
5.1. Nodes Perform Flooding Reduction without Failure
5.1.1. Receiving an LS
When a node receives a newer LS that is not originated by itself from
one of its interfaces, it floods the LS only to all the other
interfaces that are on the flooding topology.
When the LS is received from an interface on the flooding topology,
it is flooded only to all the other interfaces that are on the
flooding topology. When the LS is received on an interface that is
not on the flooding topology, it is also flooded only to all the
other interfaces that are on the flooding topology.
In any case, the LS must not be transmitted back to the receiving
interface.
Note before forwarding a received LS, the node would do the normal
processing as usual.
5.1.2. Originating an LS
When a node originates an LS, it floods the LS to its interfaces on
the flooding topology if the LS is a refresh LS (i.e., there is no
significant change in the LS comparing to the previous LS); otherwise
(i.e., there are significant changes such as link down in the LS), it
floods the LS to all its interfaces. Choosing flooding the LS with
significant changes to all the interfaces instead of limiting to the
interfaces on the flooding topology would speed up the distribution
of the significant link state changes.
5.1.3. Establishing Adjacencies
Adjacencies being established can be classified into two categories:
adjacencies to new nodes and adjacencies to existing nodes.
5.1.3.1. Adjacency to New Node
An adjacency to a new node is an adjacency between an existing node
(say node E) on the flooding topology and the new node (say node N)
which is not on the flooding topology. There is not any adjacency
between node N and a node in the network area. The procedure for
establishing the adjacency between E and N is the existing normal
procedure unchanged.
When the adjacency between N and E is established, node E adds node N
and the link between N and E to the flooding topology temporarily
until a new flooding topology is built. New node N adds node N and
the link between N and E to the flooding topology temporarily until a
new flooding topology is built.
5.1.3.2. Adjacency to Existing Node
An adjacency to an existing node is an adjacency between two nodes
(say nodes E and X) on the flooding topology. The procedure for
establishing the adjacency between E and X is the existing normal
procedure unchanged.
Both node E and node X assume that the link between E and X is not on
the flooding topology until a new flooding topology is built. After
the adjacency between E and X is established, node E does not send
node X any new or updated LS that it receives or originates, and node
X does not send node E any new or updated LS that it receives or
originates until a new flooding topology is built.
5.2. An Exception Case
5.2.1. Multiple Failures
When a node detects that two or more failures on the current flooding
topology occur before a new flooding topology is built, it enables
one flooding topology protection method in section 3.4.
5.2.2. Changes on Flooding Topology There are many algorithms to compute a flooding topology. A simple
and efficient one is briefed below.
After one or more failures split the current (old) flooding topology, o Select a node R0 according to a rule such as the node with the
some link states may be out of synchronization among some nodes. smallest node ID;
This can be resolved as follows.
After a node N computes a new flooding topology, for a local link L o Build a tree using R0 as root of the tree; and then
attached to node N, if 1) link L is not on the current (old) flooding
topology and is on the new flooding topology, and 2) there is a
failure after the current (old) flooding topology is built, then node
N sends a delta of the link states that it received or originated to
its adjacent node over link L.
For node N, the delta of the link states is the link states with o Connect each node whose degree is one to the tree to have a
changes that node N received or originated during the period of time flooding topology.
in which the current (old) flooding topology is split.
Suppose that Max_Split_Period is a number (in seconds), which is the 4.1. Algorithm with Considering Degree
maximum period of time in which a flooding topology is split. Tc is
the time at which the current (old) flooding topology is built, Tn is
the time at which the new flooding topology is built, and Ts is the
bigger one between Tc and (Tn - Max_Split_Period). Node N sends its
adjacent node over link L the link states with changes that it
received or originated from Ts to Tn.
6. Operations on Flooding Reduction The algorithm starts from node R0 as root with a given maximum degree
MaxD, a candidate queue Cq = {(R0, D = 0, PHs = { })}, and an empty
flooding topology FT = { }. Cq contains one element (R0, D = 0, PHs
= { }), where node R0 is the root, D = 0 indicates that the Degree (D
for short) of R0 is 0 (i.e., the number of links on the flooding
topology connected to R0 is 0), PHs = { } indicates that the Previous
Hops (PHs for short) of R0 is empty.
6.1. Configuring Flooding Reduction 1. Finding and removing the first element with node A in Cq that is
not on FT and one PH's D in PHs < MaxD.
This section describes configurations for distributed flooding If there is no element with a node in Cq whose PHs != { } and one
reduction (i.e., flooding reduction in distributed mode). PH in PHs whose D < MaxD,
6.1.1. Configurations for Distributed Flooding Reduction then MaxD++ and restarts algorithm from R0, MaxD, Cq =
{(R0,D=0,PHs = { })}, FT = { };
For distributed flooding reduction, an algorithm for computing a otherwise (i.e., A with one PH's D in PHs < MaxD or PHs = { }),
flooding topology needs to be configured. The algorithm and
distributed mode are configured on a node such as the area leader,
which tells the other nodes in the area the algorithm and the mode
via advertising the number of the algorithm and the mode. Every node
participating in the distributed flooding reduction uses this same
algorithm.
6.2. Migration to Flooding Reduction if PHs = { } (i.e., A is the root),
Migrating a OSPF or IS-IS area from normal flooding to flooding then mark A on FT and add A with D=0 and PHs={ } into FT;
reduction smoothly takes a few steps or stages. This section
describes the steps for migrating an area to distributed flooding
reduction from normal flooding.
6.2.1. Migration to Distributed Flooding Reduction otherwise (i.e., A is not the root. Assume that PH is the
first one in PHs whose D < MaxD), PH's D++, mark A on FT and
add A with D=1 and PHs={PH} to FT.
At first, a user selects the distributed mode on a node such as the 2. If all the nodes are on the FT, then goto step 4;
area leader node, which tells the other nodes in the area to use
distributed flooding reduction.
After a node knows that the distributed mode is used, it advertises 3. Suppose that node Xi (i = 1, 2,..., n) is connected to node A and
the algorithms it supports. A user may check whether every node not on FT, and X1, X2,..., Xn are in an increasing order by their
advertises its supporting algorithms through showing the link state IDs (i.e., X1's ID < X2's ID < ... < Xn's ID). If Xi is not in
containing the algorithms. Cq, then add it into the end of Cq with D = 0 and PHs = {A};
otherwise (i.e., Xi is in Cq), add A into Xi's PHs and elements
in PHs are in an increasing order by their degrees first and then
IDs; Goto step 1.
And then, a user selects an algorithm and activates the flooding 4. For each node B in FT whose D is one, find a link L attached to B
reduction through using configurations such as perform flooding such that L's remote node R whose D and ID are minimum; increase
Reduction, which tells all the nodes in the area to use the given B's D and R's D by one. Return FT.
algorithm and start the distributed flooding reduction.
6.3. Roll Back to Normal Flooding 4.2. Algorithm with Considering Others
For rolling back from flooding reduction to normal flooding, a user There may be some contraints on some nodes in a network. For
de-activates the flooding reduction through configuring roll back to example, in a spine-and-leaf network, there may be a constraint on
normal flooding on a node, which tells all the nodes in the area to the degree of every leaf node on the flooding topology, which is that
roll back to normal flooding. the degree of every leaf node is not greater than a given number
ConMaxD such as ConMaxD = 2. For each of the other nodes such as the
spine nodes, there is no such constraint, that is that ConMaxD is a
huge number for each of these nodes.
After receiving a configuration to roll back to normal flooding, the Step 1 of the algorithm described above is updated below to consider
node floods link states using all its local links instead of the this constraint. In addition to checking constraint PH's D < MaxD,
local links on the flooding topology. It also advertises the roll step 1 checks another constraint PH's D < PH's ConMaxD.
back to Normal flooding to all the other nodes in the area. When
each of the other nodes receives the advertisement, it rolls back to
normal flooding (i.e., floods link states using all its local links
instead of the local links on the flooding topology).
In distributed mode, every node in the area will not compute or build 1. Finding and removing the first element with node A in Cq that is
flooding topology. not on FT and one PH's D in PHs < MaxD and PH's D < PH's ConMaxD.
7. Manageability Considerations If there is no element with a node in Cq whose PHs != { } and one
PH in PHs whose D < MaxD and PH's D < PH's ConMaxD,
Section 6 "Operations on Flooding Reduction" outlines the then MaxD++ and restarts algorithm from R0, MaxD, Cq =
configuration process and deployment scenarios for link state {(R0,D=0,PHs = { })}, FT = { };
flooding reduction. The flooding reduction function may be
controlled by a policy module and assigned a suitable user privilege
level to enable. A suitable model may be required to verify the
flooding reduction status on routers participating in the flooding
reduction, including their role as a normal node advertising link
states using flooding topology. The mechanisms defined in this
document do not imply any new liveness detection and monitoring
requirements in addition to those indicated in [RFC2328] and
[RFC1195].
8. Security Considerations otherwise (i.e., node A with one PH's D in PHs < MaxD and PH's D
< PH's ConMaxD or PHS = { }),
A notable beneficial security aspect of link state flooding reduction if PHs = { } (i.e., A is the root),
is that a link state is not advertised over every link, but over the
links on the flooding topology. The malicious node could inject a
link state with a different algorithm, which could trigger the
flooding topology computation using the algorithm. Good security
practice might reuse the IS-IS authentication in [RFC5304] as well as
[RFC5310], and the OSPF authentication and other security mechanisms
described in [RFC2328], [RFC4552] and [RFC7474] to mitigate this type
of risk.
9. IANA Considerations then mark A on FT and add A with D=0 and PHs={ } into FT;
9.1. OSPF otherwise (i.e., A is not the root. Assume that PH is the
first one in PHs whose D < MaxD and PH's D < PH's ConMaxD),
PH's D++, mark A on FT and add A with D=1 and PHs={PH} to FT.
Under Registry Name: OSPF Router Information (RI) TLVs [RFC7770], 5. Security Considerations
IANA is requested to assign one new TLV value for OSPF distributed
flooding reduction as follows:
+===========+===========================+===============+ This document does not introduce any new security issue.
| TLV Value | TLV Name | reference |
+===========+===========================+===============+
| 11 | Scheduler Parameters TLV | This document |
+-----------+---------------------------+---------------+
9.2. IS-IS 6. IANA Considerations
Under Registry Name: IS-IS TLV Codepoints, IANA is requested to Under Registry Name: "IGP Algorithm Type For Computing Flooding
assign new TLV values for IS-IS distributed flooding reduction as Topology" under an existing "Interior Gateway Protocol (IGP)
Parameters" IANA registries (refer to Section 7.3. IGP
[I-D.ietf-lsr-dynamic-flooding]), IANA is requested to assign one
value of IGP Algorithm Type For Computing Flooding Topology as
follows: follows:
+===========+==============================+===============+ +==========+========================================+=============+
| TLV Value | TLV Name | reference | |Type Value| Type Name | reference |
+===========+==============================+===============+ +==========+========================================+=============+
| 151 |Scheduler Parameters TLV | This document | | 1 | Breadth First Minimum Degree Algorithm |This document|
+-----------+------------------------------+---------------+ +----------+----------------------------------------+-------------+
| 152 |Extended Options and Flag TLV | This document |
+-----------+------------------------------+---------------+
10. Acknowledgements 7. Acknowledgements
The authors would like to thank Acee Lindem, Zhibo Hu, Robin Li, The authors would like to thank Acee Lindem, Zhibo Hu, Robin Li,
Stephane Litkowski and Alvaro Retana for their valuable suggestions Stephane Litkowski and Alvaro Retana for their valuable suggestions
and comments on this draft. and comments on this draft.
11. References 8. References
11.1. Normative References 8.1. Normative References
[I-D.ietf-lsr-dynamic-flooding] [I-D.ietf-lsr-dynamic-flooding]
Li, T., Psenak, P., Ginsberg, L., Przygienda, T., Cooper, Li, T., Psenak, P., Ginsberg, L., Chen, H., Przygienda,
D., Jalil, L., and S. Dontula, "Dynamic Flooding on Dense T., Cooper, D., Jalil, L., and S. Dontula, "Dynamic
Graphs", draft-ietf-lsr-dynamic-flooding-00 (work in Flooding on Dense Graphs", draft-ietf-lsr-dynamic-
progress), February 2019. flooding-03 (work in progress), June 2019.
[RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and [RFC1195] Callon, R., "Use of OSI IS-IS for routing in TCP/IP and
dual environments", RFC 1195, DOI 10.17487/RFC1195, dual environments", RFC 1195, DOI 10.17487/RFC1195,
December 1990, <https://www.rfc-editor.org/info/rfc1195>. December 1990, <https://www.rfc-editor.org/info/rfc1195>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
DOI 10.17487/RFC2328, April 1998, DOI 10.17487/RFC2328, April 1998,
<https://www.rfc-editor.org/info/rfc2328>. <https://www.rfc-editor.org/info/rfc2328>.
[RFC4552] Gupta, M. and N. Melam, "Authentication/Confidentiality 8.2. Informative References
for OSPFv3", RFC 4552, DOI 10.17487/RFC4552, June 2006,
<https://www.rfc-editor.org/info/rfc4552>.
[RFC5250] Berger, L., Bryskin, I., Zinin, A., and R. Coltun, "The
OSPF Opaque LSA Option", RFC 5250, DOI 10.17487/RFC5250,
July 2008, <https://www.rfc-editor.org/info/rfc5250>.
[RFC5304] Li, T. and R. Atkinson, "IS-IS Cryptographic
Authentication", RFC 5304, DOI 10.17487/RFC5304, October
2008, <https://www.rfc-editor.org/info/rfc5304>.
[RFC5310] Bhatia, M., Manral, V., Li, T., Atkinson, R., White, R.,
and M. Fanto, "IS-IS Generic Cryptographic
Authentication", RFC 5310, DOI 10.17487/RFC5310, February
2009, <https://www.rfc-editor.org/info/rfc5310>.
[RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF
for IPv6", RFC 5340, DOI 10.17487/RFC5340, July 2008,
<https://www.rfc-editor.org/info/rfc5340>.
[RFC7474] Bhatia, M., Hartman, S., Zhang, D., and A. Lindem, Ed.,
"Security Extension for OSPFv2 When Using Manual Key
Management", RFC 7474, DOI 10.17487/RFC7474, April 2015,
<https://www.rfc-editor.org/info/rfc7474>.
[RFC7770] Lindem, A., Ed., Shen, N., Vasseur, JP., Aggarwal, R., and
S. Shaffer, "Extensions to OSPF for Advertising Optional
Router Capabilities", RFC 7770, DOI 10.17487/RFC7770,
February 2016, <https://www.rfc-editor.org/info/rfc7770>.
11.2. Informative References
[I-D.ietf-rtgwg-spf-uloop-pb-statement] [I-D.ietf-rtgwg-spf-uloop-pb-statement]
Litkowski, S., Decraene, B., and M. Horneffer, "Link State Litkowski, S., Decraene, B., and M. Horneffer, "Link State
protocols SPF trigger and delay algorithm impact on IGP protocols SPF trigger and delay algorithm impact on IGP
micro-loops", draft-ietf-rtgwg-spf-uloop-pb-statement-10 micro-loops", draft-ietf-rtgwg-spf-uloop-pb-statement-10
(work in progress), January 2019. (work in progress), January 2019.
[RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for
IANA Considerations Section in RFCs", RFC 5226, Writing an IANA Considerations Section in RFCs", BCP 26,
DOI 10.17487/RFC5226, May 2008, RFC 8126, DOI 10.17487/RFC8126, June 2017,
<https://www.rfc-editor.org/info/rfc5226>. <https://www.rfc-editor.org/info/rfc8126>.
Appendix A. Algorithms to Build Flooding Topology
There are many algorithms to build a flooding topology. A simple and
efficient one is briefed below.
o Select a node R according to a rule such as the node with the
biggest/smallest node ID;
o Build a tree using R as root of the tree (details below); and then
o Connect k (k>=0) leaves to the tree to have a flooding topology
(details follow).
A.1. Algorithms to Build Tree without Considering Others
An algorithm for building a tree from node R as root starts with a
candidate queue Cq containing R and an empty flooding topology Ft:
1. Remove the first node A from Cq and add A into Ft
2. If Cq is empty, then return with Ft
3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A
and not in Ft and X1, X2, ..., Xn are in a special order. For
example, X1, X2, ..., Xn are ordered by the cost of the link
between A and Xi. The cost of the link between A and Xi is less
than the cost of the link between A and Xj (j = i + 1). If two
costs are the same, Xi's ID is less than Xj's ID. In another
example, X1, X2, ..., Xn are ordered by their IDs. If they are
not ordered, then make them in the order.
4. Add Xi (i = 1, 2, ..., n) into the end of Cq, goto step 1.
Another algorithm for building a tree from node R as root starts with
a candidate queue Cq containing R and an empty flooding topology Ft:
1. Remove the first node A from Cq and add A into Ft
2. If Cq is empty, then return with Ft
3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A
and not in Ft and X1, X2, ..., Xn are in a special order. For
example, X1, X2, ..., Xn are ordered by the cost of the link
between A and Xi. The cost of the link between A and Xi is less
than the cost of the link between A and Xj (j = i + 1). If two
costs are the same, Xi's ID is less than Xj's ID. In another
example, X1, X2, ..., Xn are ordered by their IDs. If they are
not ordered, then make them in the order.
4. Add Xi (i = 1, 2, ..., n) into the front of Cq and goto step 1.
A third algorithm for building a tree from node R as root starts with
a candidate list Cq containing R associated with cost 0 and an empty
flooding topology Ft:
1. Remove the first node A from Cq and add A into Ft
2. If all the nodes are on Ft, then return with Ft
3. Suppose that node A is associated with a cost Ca which is the
cost from root R to node A, node Xi (i = 1, 2, ..., n) is
connected to node A and not in Ft and the cost of the link
between A and Xi is LCi (i=1, 2, ..., n). Compute Ci = Ca + LCi,
check if Xi is in Cq and if Cxi (cost from R to Xi) < Ci. If Xi
is not in Cq, then add Xi with cost Ci into Cq; If Xi is in Cq,
then If Cxi > Ci then replace Xi with cost Cxi by Xi with Ci in
Cq; If Cxi == Ci then add Xi with cost Ci into Cq.
4. Make sure Cq is in a special order. Suppose that Ai (i=1, 2,
..., m) are the nodes in Cq, Cai is the cost associated with Ai,
and IDi is the ID of Ai. One order is that for any k = 1, 2,
..., m-1, Cak < Caj (j = k+1) or Cak = Caj and IDk < IDj. Goto
step 1.
A.2. Algorithms to Build Tree Considering Others
An algorithm for building a tree from node R as root with
consideration of others's support for flooding reduction starts with
a candidate queue Cq containing R associated with previous hop PH=0
and an empty flooding topology Ft:
1. Remove the first node A that supports flooding reduction from the
candidate queue Cq if there is such a node A; otherwise (i.e., if
there is not such node A in Cq), then remove the first node A
from Cq. Add A into the flooding topology Ft.
2. If Cq is empty or all nodes are on Ft, then return with Ft
3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A
and not in the flooding topology Ft and X1, X2, ..., Xn are in a
special order considering whether some of them that support
flooding reduction (. For example, X1, X2, ..., Xn are ordered
by the cost of the link between A and Xi. The cost of the link
between A and Xi is less than that of the link between A and Xj
(j = i + 1). If two costs are the same, Xi's ID is less than
Xj's ID. The cost of a link is redefined such that 1) the cost
of a link between A and Xi both support flooding reduction is
much less than the cost of any link between A and Xk where Xk
with F=0; 2) the real metric of a link between A and Xi and the
real metric of a link between A and Xk are used as their costs
for determining the order of Xi and Xk if they all (i.e., A, Xi
and Xk) support flooding reduction or none of Xi and Xk support
flooding reduction.
4. Add Xi (i = 1, 2, ..., n) associated with previous hop PH=A into
the end of the candidate queue Cq, and goto step 1.
Another algorithm for building a tree from node R as root with
consideration of others' support for flooding reduction starts with a
candidate queue Cq containing R associated with previous hop PH=0 and
an empty flooding topology Ft:
1. Remove the first node A that supports flooding reduction from the
candidate queue Cq if there is such a node A; otherwise (i.e., if
there is not such node A in Cq), then remove the first node A
from Cq. Add A into the flooding topology Ft.
2. If Cq is empty or all nodes are on Ft, then return with Ft.
3. Suppose that node Xi (i = 1, 2, ..., n) is connected to node A
and not in the flooding topology Ft and X1, X2, ..., Xn are in a
special order considering whether some of them support flooding
reduction. For example, X1, X2, ..., Xn are ordered by the cost
of the link between A and Xi. The cost of the link between A and
Xi is less than the cost of the link between A and Xj (j = i +
1). If two costs are the same, Xi's ID is less than Xj's ID.
The cost of a link is redefined such that 1) the cost of a link
between A and Xi both support flooding reduction is much less
than the cost of any link between A and Xk where Xk does not
support flooding reduction; 2) the real metric of a link between
A and Xi and the real metric of a link between A and Xk are used
as their costs for determining the order of Xi and Xk if they all
(i.e., A, Xi and Xk) support flooding reduction or none of Xi and
Xk supports flooding reduction.
4. Add Xi (i = 1, 2, ..., n) associated with previous hop PH=A into
the front of the candidate queue Cq, and goto step 1.
A third algorithm for building a tree from node R as root with
consideration of others' support for flooding reduction (using flag F
= 1 for support, and F = 0 for not support in the following) starts
with a candidate list Cq containing R associated with low order cost
Lc=0, high order cost Hc=0 and previous hop ID PH=0, and an empty
flooding topology Ft:
1. Remove the first node A from Cq and add A into Ft.
2. If all the nodes are on Ft, then return with Ft
3. Suppose that node A is associated with a cost Ca which is the
cost from root R to node A, node Xi (i = 1, 2, ..., n) is
connected to node A and not in Ft and the cost of the link
between A and Xi is LCi (i=1, 2, ..., n). Compute Ci = Ca + LCi,
check if Xi is in Cq and if Cxi (cost from R to Xi) < Ci. If Xi
is not in Cq, then add Xi with cost Ci into Cq; If Xi is in Cq,
then If Cxi > Ci then replace Xi with cost Cxi by Xi with Ci in
Cq; If Cxi == Ci then add Xi with cost Ci into Cq.
4. Suppose that node A is associated with a low order cost LCa which
is the low order cost from root R to node A and a high order cost
HCa which is the high order cost from R to A, node Xi (i = 1, 2,
..., n) is connected to node A and not in the flooding topology
Ft and the real cost of the link between A and Xi is Ci (i=1, 2,
..., n). Compute LCxi and HCxi: LCxi = LCa + Ci if both A and Xi
have flag F set to one, otherwise LCxi = LCa HCxi = HCa + Ci if A
or Xi does not have flag F set to one, otherwise HCxi = HCa If Xi
is not in Cq, then add Xi associated with LCxi, HCxi and PH = A
into Cq; If Xi associated with LCxi' and HCxi' and PHxi' is in
Cq, then If HCxi' > HCxi then replace Xi with HCxi', LCxi' and
PHxi' by Xi with HCxi, LCxi and PH=A in Cq; otherwise (i.e.,
HCxi' == HCxi) if LCxi' > LCxi , then replace Xi with HCxi',
LCxi' and PHxi' by Xi with HCxi, LCxi and PH=A in Cq; otherwise
(i.e., HCxi' == HCxi and LCxi' == LCxi) if PHxi' > PH, then
replace Xi with HCxi', LCxi' and PHxi' by Xi with HCxi, LCxi and
PH=A in Cq.
5. Make sure Cq is in a special order. Suppose that Ai (i=1, 2,
..., m) are the nodes in Cq, HCai and LCai are low order cost and
high order cost associated with Ai, and IDi is the ID of Ai. One
order is that for any k = 1, 2, ..., m-1, HCak < HCaj (j = k+1)
or HCak = HCaj and LCak < LCaj or HCak = HCaj and LCak = LCaj and
IDk < IDj. Goto step 1.
A.3. Connecting Leaves
Suppose that we have a flooding topology Ft built by one of the
algorithms described above. Ft is like a tree. We may connect k (k
>=0) leaves to the tree to have a enhanced flooding topology with
more connectivity.
Suppose that there are m (0 < m) leaves directly connected to a node
X on the flooding topology Ft. Select k (k <= m) leaves through
using a deterministic algorithm or rule. One algorithm or rule is to
select k leaves that have smaller or larger IDs (i.e., the IDs of
these k leaves are smaller/bigger than the IDs of the other leaves
directly connected to node X). Since every node has a unique ID,
selecting k leaves with smaller or larger IDs is deterministic.
If k = 1, the leaf selected has the smallest/largest node ID among
the IDs of all the leaves directly connected to node X.
For a selected leaf L directly connected to a node N in the flooding
topology Ft, select a connection/adjacency to another node from node
L in Ft through using a deterministic algorithm or rule.
Suppose that leaf node L is directly connected to nodes Ni (i =
1,2,...,s) in the flooding topology Ft via adjacencies and node Ni is
not node N, IDi is the ID of node Ni, and Hi (i = 1,2,...,s) is the
number of hops from node L to node Ni in the flooding topology Ft.
One Algorithm or rule is to select the connection to node Nj (1 <= j
<= s) such that Hj is the largest among H1, H2, ..., Hs. If there is
another node Na ( 1 <= a <= s) and Hj = Ha, then select the one with
smaller (or larger) node ID. That is that if Hj == Ha and IDj < IDa
then select the connection to Nj for selecting the one with smaller
node ID (or if Hj == Ha and IDj < IDa then select the connection to
Na for selecting the one with larger node ID).
Suppose that the number of connections in total between leaves
selected and the nodes in the flooding topology Ft to be added is
NLc. We may have a limit to NLc.
Authors' Addresses Authors' Addresses
Huaimo Chen Huaimo Chen
Huawei Technologies Futurewei
Boston Boston
USA USA
Email: huaimo.chen@huawei.com Email: huaimo.chen@futurewei.com
Dean Cheng Dean Cheng
Huawei Technologies Individual
Santa Clara Santa Clara
USA USA
Email: dean.cheng@huawei.com Email: deanccheng@gmail.com
Mehmet Toy Mehmet Toy
Verizon Verizon
USA USA
Email: mehmet.toy@verizon.com Email: mehmet.toy@verizon.com
Yi Yang Yi Yang
IBM IBM
Cary, NC Cary, NC
United States of America United States of America
skipping to change at page 24, line 31 skipping to change at page 9, line 4
China China
Email: wangaj.bri@chinatelecom.cn Email: wangaj.bri@chinatelecom.cn
Xufeng Liu Xufeng Liu
Volta Networks Volta Networks
McLean, VA McLean, VA
USA USA
Email: xufeng.liu.ietf@gmail.com Email: xufeng.liu.ietf@gmail.com
Yanhe Fan Yanhe Fan
Casa Systems Casa Systems
USA USA
Email: yfan@casa-systems.com Email: yfan@casa-systems.com
Lei Liu Lei Liu
Fujitsu
USA USA
Email: liulei.kddi@gmail.com Email: liulei.kddi@gmail.com
 End of changes. 59 change blocks. 
885 lines changed or deleted 150 lines changed or added

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