LS Flooding Reduction
draft-cc-lsr-flooding-reduction-01
This document is an Internet-Draft (I-D).
Anyone may submit an I-D to the IETF.
This I-D is not endorsed by the IETF and has no formal standing in the
IETF standards process.
The information below is for an old version of the document.
| Document | Type |
This is an older version of an Internet-Draft whose latest revision state is "Expired".
|
|
|---|---|---|---|
| Authors | Huaimo Chen , Dean Cheng , Mehmet Toy , Yi Yang , Aijun Wang , Xufeng Liu , Yanhe Fan , Lei Liu | ||
| Last updated | 2019-01-07 (Latest revision 2018-12-10) | ||
| RFC stream | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-cc-lsr-flooding-reduction-01
Network Working Group H. Chen
Internet-Draft D. Cheng
Intended status: Standards Track Huawei Technologies
Expires: July 11, 2019 M. Toy
Verizon
Y. Yang
IBM
A. Wang
China Telecom
X. Liu
Volta Networks
Y. Fan
Casa Systems
L. Liu
January 7, 2019
LS Flooding Reduction
draft-cc-lsr-flooding-reduction-01
Abstract
This document proposes an approach to flood link states on a topology
that is a subgraph of the complete topology per underline physical
network, so that the amount of flooding traffic in the network is
greatly reduced, and it would reduce convergence time with a more
stable and optimized routing environment. The approach can be
applied to any network topology in a single area.
Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
Chen, et al. Expires July 11, 2019 [Page 1]
Internet-Draft Flooding Reduction January 2019
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on July 11, 2019.
Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) 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
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Conventions Used in This Document . . . . . . . . . . . . . . 4
4. Problem Statement . . . . . . . . . . . . . . . . . . . . . . 5
5. Flooding Topology . . . . . . . . . . . . . . . . . . . . . . 5
5.1. Construct Flooding Topology . . . . . . . . . . . . . . . 6
5.2. Protect Flooding Topology Split . . . . . . . . . . . . . 7
6. Extensions to OSPF . . . . . . . . . . . . . . . . . . . . . 8
6.1. Extensions for Operations . . . . . . . . . . . . . . . . 8
6.2. Extensions for Centralized Mode . . . . . . . . . . . . . 9
6.2.1. Message for Flooding Topology . . . . . . . . . . . . 9
6.2.2. Leaders Selection . . . . . . . . . . . . . . . . . . 17
7. Extensions to IS-IS . . . . . . . . . . . . . . . . . . . . . 18
7.1. Extensions for Operations . . . . . . . . . . . . . . . . 18
7.2. Extensions for Centralized Mode . . . . . . . . . . . . . 19
7.2.1. TLV for Flooding Topology . . . . . . . . . . . . . . 19
7.2.2. Leaders Selection . . . . . . . . . . . . . . . . . . 20
8. Flooding Behavior . . . . . . . . . . . . . . . . . . . . . . 20
8.1. Nodes Perform Flooding Reduction without Failure . . . . 21
8.1.1. Receiving an LS . . . . . . . . . . . . . . . . . . . 21
8.1.2. Originating an LS . . . . . . . . . . . . . . . . . . 21
8.1.3. Establishing Adjacencies . . . . . . . . . . . . . . 21
8.2. An Exception Case . . . . . . . . . . . . . . . . . . . . 22
8.2.1. Multiple Failures . . . . . . . . . . . . . . . . . . 22
8.2.2. Changes on Flooding Topology . . . . . . . . . . . . 23
9. Operations on Flooding Reduction . . . . . . . . . . . . . . 23
Chen, et al. Expires July 11, 2019 [Page 2]
Internet-Draft Flooding Reduction January 2019
9.1. Configuring Flooding Reduction . . . . . . . . . . . . . 24
9.1.1. Configurations for Centralized Flooding Reduction . . 24
9.1.2. Configurations for Distributed Flooding Reduction . . 24
9.2. Migration to Flooding Reduction . . . . . . . . . . . . . 24
9.2.1. Migration to Centralized Flooding Reduction . . . . . 24
9.2.2. Migration to Distributed Flooding Reduction . . . . . 25
9.3. Roll Back to Normal Flooding . . . . . . . . . . . . . . 25
9.4. Transfer from Distributed to Centralized Mode . . . . . . 26
9.5. Transfer from Centralized to Distributed Mode . . . . . . 27
9.6. Adding a New Node to Network . . . . . . . . . . . . . . 27
10. Manageability Considerations . . . . . . . . . . . . . . . . 28
11. Security Considerations . . . . . . . . . . . . . . . . . . . 28
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28
12.1. OSPFv2 . . . . . . . . . . . . . . . . . . . . . . . . . 28
12.2. OSPFv3 . . . . . . . . . . . . . . . . . . . . . . . . . 29
12.3. IS-IS . . . . . . . . . . . . . . . . . . . . . . . . . 30
13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 30
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 30
14.1. Normative References . . . . . . . . . . . . . . . . . . 30
14.2. Informative References . . . . . . . . . . . . . . . . . 31
Appendix A. Algorithms to Build Flooding Topology . . . . . . . 32
A.1. Algorithms to Build Tree without Considering Others . . . 32
A.2. Algorithms to Build Tree Considering Others . . . . . . . 33
A.3. Connecting Leaves . . . . . . . . . . . . . . . . . . . . 35
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 36
1. Introduction
For some networks such as dense Data Center (DC) networks, the
existing Link State (LS) flooding mechanism is not efficient and may
have some issues. The extra LS flooding consumes network bandwidth.
Processing the extra LS flooding, including receiving, buffering and
decoding the extra LSs, wastes memory space and processor time. This
may cause scalability issues and affect the network convergence
negatively.
This document proposes an approach to minimize the amount of flooding
traffic in the network. Thus the workload for processing the extra
LS flooding is decreased significantly. This would improve the
scalability, speed up the network convergence, stable and optimize
the routing environment.
This approach is also flexible. It has multiple modes for
computation of flooding topology. Users can select a mode they
prefer, and smoothly switch from one mode to another. The approach
is applicable to any network topology in a single area. It is
backward compatible.
Chen, et al. Expires July 11, 2019 [Page 3]
Internet-Draft Flooding Reduction January 2019
2. Terminology
Flooding Topology:
A sub-graph or sub-network of a given (physical) network topology
that has the same reachability to every node as the given network
topology, through which link states are flooded.
Critical link or interface on a flooding topology:
A only link or interface among some nodes on the flooding
topology. When this link or interface goes down, the flooding
topology will be split.
Critical node on a flooding topology:
A only node connecting some nodes on the flooding topology. When
this node goes down, the flooding topology will be split.
Backup path:
A path or a sequence of links, providing an alternative
connection between the two end nodes of a link on the flooding
topology or between the two end nodes of a path crossing a node
on the flooding topology. when a critical link goes down, the
backup path for the link provides a connection to connect two
parts of a split flooding topology. When a critical node goes
down, the backup paths for the paths crossing the node connect
all the split parts of the floooding topology into one.
Remaining Flooding Topology:
A topology from a flooding topology by removing the failed links
and nodes from the flooding topology.
LSA:
A Link State Advertisement in OSPF.
LSP:
A Link State Protocol Data Unit (PDU) in IS-IS.
LS:
A Link Sate, which is an LSA or LSP.
3. Conventions Used in This Document
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
Chen, et al. Expires July 11, 2019 [Page 4]
Internet-Draft Flooding Reduction January 2019
4. Problem Statement
OSPF and IS-IS deploy a so-called reliable flooding mechanism, where
a node must transmit a received or self-originated LS to all its
interfaces (except for the interface where an LS is received). While
this mechanism assures each LS being distributed to every node in an
area or domain, the side-effect is that the mechanism often causes
redundant LS, which in turn forces nodes to process identical LS more
than once. This results in the waste of link bandwidth and nodes'
computing resources, and the delay of topology convergence.
This becomes more serious in networks with large number of nodes and
links, and in particular, higher degree of interconnection (e.g.,
meshed topology, spine-leaf topology, etc.). In some environments
such as in data centers, the drawback of the existing flooding
mechanism has already caused operational issues, including waves of
flooding storms, choke of computing resources, slow convergence,
oscillating topology changes, and instability of routing environment.
One example is as shown in Figure 1, where Node 1, Node 2 and Node 3
are interconnected in a mesh. When Node 1 receives a new or updated
LS on its interface I11, it by default would forward the LS to its
interface Il2 and I13 towards Node 2 and Node 3, respectively, after
processing. Node 2 and Node 3 upon reception of the LS and after
processing, would potentially flood the same LS over their respective
interface I23 and I32 toward each other, which is obviously not
necessary and at the cost of link bandwidth as well as both nodes'
computing resource.
|
|I11
+--o---+
|Node 1|
+-o--o-+
I12 / \ I13
/ \
I21/ \I31
+----o-+ I32+-o----+
|Node 2|------|Node 3|
+------+I23 +------+
Figure 1
5. Flooding Topology
For a given network topology, a flooding topology is a sub-graph or
sub-network of the given network topology that has the same
reachability to every node as the given network topology. Thus all
Chen, et al. Expires July 11, 2019 [Page 5]
Internet-Draft Flooding Reduction January 2019
the nodes in the given network topology MUST be in the flooding
topology. All the nodes MUST be inter-connected directly or
indirectly. As a result, LS flooding will in most cases occur only
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
original topology, any single LS MUST still be disseminated in the
entire network.
5.1. Construct Flooding Topology
Many different flooding topologies can be constructed for a given
network topology. A chain connecting all the nodes in the given
network topology is a flooding topology. A circle connecting all the
nodes is another flooding topology. A tree connecting all the nodes
is a flooding topology. In addition, the tree plus the connections
between some leaves of the tree and branch nodes of the tree is a
flooding topology.
The following parameters need to be considered for constructing a
flooding topology:
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,
the smaller the number of links, the less the amount of LS
flooding.
o Diameter: The shortest distance between the two most distant nodes
on the flooding topology (i.e., the diameter of the flooding
topology) is a key factor for reducing the network convergence
time. The smaller the diameter, the less the convergence time.
o Redundancy: The redundancy of the flooding topology means a
tolerance to the failures of some links and nodes on the flooding
topology. If the flooding topology is split by some failures, it
is not tolerant to these failures. In general, the larger the
number of links on the flooding topology is, the more tolerant the
flooding topology to failures.
There are many different ways to construct a flooding topology for a
given network topology. A few of them are listed below:
o Centralized Mode: One node in the network builds a flooding
topology and floods the flooding topology to all the other nodes
in the network (Note: Flooding the flooding topology may increase
the flooding. The amount of traffic for flooding the flooding
topology should be minimized.);
Chen, et al. Expires July 11, 2019 [Page 6]
Internet-Draft Flooding Reduction January 2019
o Distributed Mode: Each node in the network automatically
calculates a flooding topology by using the same algorithm (No
flooding for flooding topology);
o Static Mode: Links on the flooding topology are configured
statically.
Note that the flooding topology constructed by a node is dynamic in
nature, that means when the base topology (the entire topology graph)
changes, the flooding topology (the sub-graph) MUST be re-computed/
re-constructed to ensure that any node that is reachable on the base
topology MUST also be reachable on the flooding topology.
For reference purpose, some algorithms that allow nodes to
automatically compute flooding topology are elaborated in Appendix A.
However, this document does not attempt to standardize how a flooding
topology is established.
5.2. Protect Flooding Topology Split
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. For example, in centralized mode, it takes some time
for the leader to detect the failures through receiving the link
states, compute a new flooding topology and flood the new flooding
topology. In addition, it takes some time for each of the other
nodes to receive the new flooding topology (piece by piece), decode
it and build it locally. 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 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 other failures on the flooding topology, node N
adds the links (e.g., L1 and L2) to the flooding topology temporarily
until a new flooding topology is built. Suppose that the two end
nodes of link L is A and B, and A's ID is smaller than B's. Node N
Chen, et al. Expires July 11, 2019 [Page 7]
Internet-Draft Flooding Reduction January 2019
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.
6. Extensions to OSPF
The extensions to OSPF comprises two parts: one part is for
operations on flooding reduction, the other is specially for
centralized flooding reduction (or say flooding reduction in
centralized mode).
6.1. Extensions for Operations
A new TLV is defined in OSPF RI LSA [RFC7770]. It contains
instructions about flooding reduction, and is called Flooding
Reduction Instruction TLV or Instruction TLV for short. This TLV is
originated from only one node and has the format 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| INST-TLV-Type (TBD1) | TLV-Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OP | MOD | Algorithm | Reserved (MUST be zero) | NL |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ sub TLVs (optional) ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Flooding Reduction Instruction TLV
A OP field of three bits is defined in the TLV. It may have a value
of the followings.
o 0x001 (R): Perform flooding Reduction, which instructs the nodes
in an area to perform flooding reduction.
o 0x010 (N): Roll back to Normal flooding, which instructs the nodes
in an area to roll back to perform normal flooding.
When any of the other values is received, it is ignored.
A MOD field of three bits is defined in the TLV and may have a value
of the followings.
o 0x001 (C): Centralized Mode, which instructs: 1) the nodes in an
area to select leaders (primary/designated leader, secondary/
backup leader, and so on); 2) the primary leader to compute a
flooding topology and flood it to all the other nodes in the area;
Chen, et al. Expires July 11, 2019 [Page 8]
Internet-Draft Flooding Reduction January 2019
3) every node in the area to receive and use the flooding topology
originated by the primary leader.
o 0x010 (D): Distributed Mode, which instructs every node in an area
to compute and use its own flooding topology.
o 0x011 (S): Static Mode, which instructs every node in an area to
use the flooding topology statically configured on the node.
When any of the other values is received, it is ignored.
An Algorithm field of eight bits is defined in the TLV to instruct
the leader node in centralized mode or every node in distributed mode
to use the algorithm indicated in this field for computing a flooding
topology.
A NL field of three bits is defined in the TLV, which indicates the
number of leaders to be selected when Centralized Mode is used. NL
set to 2 means two leaders (a designated/primary leader and a backup/
secondary leader) to be selected for an area, and NL set to 3 means
three leaders to be selected. When Centralized Mode is not used, The
NL field is not valid.
Some optional sub TLVs may be defined in the future, but none is
defined now.
6.2. Extensions for Centralized Mode
6.2.1. Message for Flooding Topology
A flooding topology can be represented by the links in the flooding
topology. For the links between a local node and its adjacent (or
remote) nodes, we can encode the local node and its adjacent nodes.
After all the links in the flooding topology are encoded, the encoded
links can be flooded to every node in the network. After receiving
the encoded links, every node decodes the links and creates and/or
updates the flooding topology.
Every node orders the nodes by their node IDs (router IDs in OSPF,
system IDs in IS-IS) in ascending order, and generates the same
sequence of the nodes in the area. The sequence of nodes have the
index 0, 1, 2, and so on respectively. Every node in the encoded
links is represented by its index.
Chen, et al. Expires July 11, 2019 [Page 9]
Internet-Draft Flooding Reduction January 2019
6.2.1.1. Links Encoding
A local node can be encoded in two parts: encoded node index size
indication (ENSI) of 4 bits and compact node index (CNI). ENSI value
plus 8 gives the size of compact node index. For example, ENSI = 0
indicates that the size of CNIs is 8 bits. In the figure below,
Local node LN1 is encoded as ENSI=0 using 4 bits and CNI=LN1's Index
using 8 bits. LN1 is encoded in 12 bits in total.
0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
|0 0 0 0| ENSI (4 bits) [0 + 8 = 8 bits CNI]
+-+-+-+-+-+-+-+-+
| LN1's Index | CNI (8 bits)
+-+-+-+-+-+-+-+-+
Encoding for local node LN1
The adjacent nodes can be encoded in two parts: Number of Nodes (NN)
of 4 bits and compact node indexes (CNIs). The size of CNIs is the
same as the local node. For example, local node LN1 has three
adjacent nodes RN1, RN2 and RN3 in the following figure.
o LN1
/ | \
/ | \
/ | \
o RN1 o RN2 o RN3
Links from LN1 to its adjacent nodes RN1, RN2 and RN3
These three adjacent nodes RN1, RN2 and RN3 are encoded below in 28
bits (i.e., 3.5 bytes).
Chen, et al. Expires July 11, 2019 [Page 10]
Internet-Draft Flooding Reduction January 2019
0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
|0 0 1 1| NN