Re: [Lsr] Comments regarding convergence regarding draft-cc-lsr-flooding-reduction and draft-li-lsr-dynamic-flooding

[Huaimo Chen <[e-mail]>]

Hi Everyone,



Our answers/explanations to Tony’s comments/questions are in line below with prefix [HC] and in red.



Best Regards,

Huaimo



Hi all,



I wanted to address some of the points that Huaimo has raised.  I’ve taken the editorial liberty of reformatting some of Huaimo’s comments.



> 1.                  Flooding topology encoding

>

> The encoding in "draft-li-lsr-dynamic-flooding" comprises two parts. One part is the encoding of the flooding topology using the TLVs of the paths constituting the flooding topology; the second part is the encoding of the mapping from the nodes in the area to their indexes. The TLVs use the indexes of the nodes in the paths.



> There are two encodings in "draft-cc-lsr-flooding-reduction", each of

> which can be used to encode the flooding topology. One encoding is

> called "Links Encoding". The other is called "Block Encoding”.





Not distributing the encoding of the indices is an issue that needs to be addressed. Without an explicit encoding, all systems are forced to rely on the complete and area-wide synchronization of the entire LSDB. This seems like it is a significant risk. What happens if there is an expired LSP and one system has expunged it from the database but another has not? This would perturb the indices. If a new node has been added to the topology and its presence has not completed flooding, then the indices would also be perturbed.



[HC]  Area-wide synchronization is the pre-requisite for IGP to work correctly by default. When the network has some nodes having their LSDBs out of synchronization, in general, the issue on the indexes is even bigger if the mapping from the nodes to their indexes is generated by the leader of the area using its LSDB and is flooded to all the other nodes.



> The former encodes the links between a local node and its adjacent

> nodes using the compact indexes of these nodes. The whole flooding

> topology is represented by the links and nodes on it. This is like the normal topology representation in an IGP, in which the topology is represented by the links and nodes in an IGP area.  No mapping encoding and flooding is needed. Every node creates and maintains the mapping from the nodes to their indexes. It is simpler and faster for the node to have the mapping in this way.





The use of two different encodings for the topology is highly unusual.



It is not at all clear about how it should be done. Ambiguity in a specification results in differing interpretations, that leads to complexity and interoperability errors. In this specific case, it would also seem to result in redundancy.  It would be better to have a single encoding.



[HC]  At this stage, we proposed two options in our draft. At last, one single encoding will be used.





The use of the “compact index” is not clear.  At 14 bits, it is clearly not large enough to support large areas. While we are generally not exceeding 16k systems today, that may grow. It wasn’t long ago that areas were practically confined to 1k nodes.  That’s exceeded now.



[HC] How did you get 14 bits?

The idea of compact node indexes or say a variable size (or length) of node indexes, is used in our links encoding and block encoding.



For the links from a local node to its adjacent nodes, the size (or length) of the indexes of these nodes (i.e., the local node and the adjacent nodes) is set to the maximum among the sizes of these node indexes. For example, suppose that these nodes have indexes 1, 126, 245, and 511. The sizes of their indexes are 1, 7, 8, and 9 bits respectively. The maximum among 1, 7, 8, and 9 is 9 (bits). This maximum size (i.e., 9) is represented by an element, which is the 4 bits field. This element can be a byte, a word, or even a TLV if you want. After this element, these four node indexes (i.e., 1, 126, 245, and 511) are represented by four 9 bits fields, which contain 1, 126, 245, and 511 respectively.



When a block of flooding topology is encoded in our block encoding, the size (or length) of the indexes of the nodes in this block is set to the maximum among the sizes of these node indexes.



When the value of 4 bits (from 0 to 15) is directly used to indicate the size of node indexes, it is big enough to support 32k (i.e., 2^15) nodes. When the links from a local node to its adjacent nodes are encoded, the size of these node indexes is indicated by the value of this 4 bits, which is the maximum among the sizes of these node indexes.



From section 6.2.1.1 in our draft, the size of node indexes is the value of 4 bits field (called ENSI) plus 8. The range of 4 bits value is from 0 to 15. Thus the range of the size of node indexes is from 8 bits to 23 bits. Any node index from 0 to 2^23 can be represented. When (the value of the 4 bits field plus 8) is used to indicate the size of these node indexes, it is the maximum among the sizes of these node indexes or 8 in case where the maximum is less than 8.





A better way of encoding the indices is to make them variable length, depending on the number of nodes in the area (credit: Tony P.). In our draft, the explicit encoding of the mapping from system to index makes it very clear how many systems there are, and thus how many bits should be used in this encoding.  Please note that this optimization is not yet reflected in our draft.



[HC] We see that your better way is an application of our idea about “variable size (or length) of node indexes”.



Our idea can be used in the encoding in your draft in a few different ways.

In one way, a variable size (or length) of node indexes is used in a Path TLV. For all the nodes in this Path TLV, the size (or length) of the indexes of these nodes is set to the maximum among the sizes of these node indexes. The size (or length) of indexes is represented by an element, which can be a 4 bits field, a byte, a word or even a TLV.

In another way, a variable size (or length) of node indexes is used in an LSP/LSA for all the nodes contained in the Path TLVs in the LSP/LSA.

In a third way, a variable size (or length) of node indexes is used in the mapping for all the nodes in an area. The size (or length) of indexes is represented by an element. After this element, all the node indexes, including those in paths TLVs, are represented by the fields of the size indicated by the element.





> For example, one issue is that different types of messages (i.e., the messages for the mapping, and the messages for the TLVs of the paths in the flooding topology, depending on the mapping) for the flooding topology may be out of order on a receiving router. This may cause incorrect/corrupted flooding topology.





As I’ve explained, the ordering is irrelevant.



[HC] The ordering is critical. The TLVs for paths contain the indexes of the nodes in the paths. The indexes of these nodes are generated by the leader of the area, and the mapping from the nodes to the indexes is created by the leader. We can see that the TLVs (i.e., the indexes of the nodes in the TLVs for paths) depend on the mapping.



The ordering of the TLVs for the mapping from node to index is self describing. Each TLV carries the starting index for the contents of its TLV.



[HC] The ordering that you talked about is not the ordering we discussed. The former is the ordering of the TLVs in the mapping, i.e., the ordering of the same type of the TLVs for the mapping. Latter is ordering of the different types of TLVs. One type of TLVs is the TLVs for the paths containing the indexes of the nodes in the paths. The second type of TLVs is the TLVs for the mapping from nodes to indexes.



The ordering of arrival of various LSP segments is also irrelevant as the computation need only be deferred until all segments have arrived.  This is already commonly done as part of SPF scheduling. This is also a necessity for all proposals, as any computation with inconsistent segments is going to yield dubious results.





> 2.                  Fault tolerance to multiple failures

>

> An efficient method for fault tolerance to multiple failures on the

> flooding topology is very important to centralized flooding reduction.

> Without it, the network convergence will slow down significantly. In general, the convergence time will be more than doubled comparing to normal convergence when the flooding topology is split by multiple failures.





Multiple simultaneous failures are an extremely unlikely event. Routers are not designed to survive multiple concurrent hardware failures. Most topologies run at commercially viable loading levels cannot survive multiple critical link or node failures without manual intervention. What is critical is to survive a single failure efficiently. Our proposal is to compute a biconnected flooding topology. This protects against single failures, retaining a functioning flooding topology in the event of a failure. At that point, the system computes a new bi-connected flooding topology, protecting against further failures.



[HC] A network without flooding reduction deployment may survive multiple failures due to “reliable flooding” as we know that flooding is occurring on every link. After flooding reduction is deployed, if failure occurs on more than one links or/and nodes that are on the flooding topology, the network can not survive at all.



Carrying arbitrary alternate information to protect against multiple failures negates your point about encoding efficiency. Backup links are not a tractable solution.



[HC] There is no arbitrary alternate information to protect against multiple failures that is encoded or flooded in our proposal.



> The more time the network convergence takes, the more customers'

> traffic in the network gets lost in general. Thus after the centralized flooding reduction without fault tolerance to multiple failures is deployed in a network, some customers' traffic lose will be more than doubled when multiple failures splitting the flooding topology occur comparing to the same network without the flooding reduction.





If there are multiple failures, in our proposal, this can easily be detected. The flooding topology would clearly be partitioned. Systems on the edge of the partition can explicitly request temporary changes to the flooding topology, immediately restoring the connectivity of the flooding topology if that is possible.  Thus, the convergence time is going to be on the order of two LSP propagation times: one to detect the failure and another to repair it and converge.



[HC] From your description above, we can not see any details or description on how to restore the connectivity of the flooding topology.



The convergence time is the total of the times for finishing followings:

    1) the failures are flooded to the leader in the area through updated LSAs/LSPs,

    2) the leader computes a new flooding topology after receiving the LSAs/LSPs,

    3) the leader floods the new flooding topology to every other node in the area,

    4) every other node receives, decodes and installs the new flooding topology, and

5) some nodes resynchronize their LSDBs with their neighbors.



The time for the leader to compute a new flooding topology depends on the complexity of the algorithm. For computing a flooding topology from any network topology that survives any one failure, the algorithm is very complex in term of time in general.





Tree topologies are particularly vulnerable to failures since each and every link failure creates a partition of the flooding topology.



Repairing this in a distributed fashion is also not perceptibly better.  After a partition, it will require at least one LSP propagation time to detect the failure. Then execution of the algorithm, followed by another LSP propagation time before a complete SPF can be run.



[HC] Tree topologies we mentioned are just for examples.



> "draft-cc-lsr-flooding-reduction" has a light-weight method for providing fault tolerance to multiple failures on the flooding topology. This method makes sure that the network still converges fast when the multiple failures happen. Thus the failures have almost minimal impact on the network convergence in the network with the flooding reduction deployment. The customers' traffic lose is significantly reduced (or almost minimized) when the failures occur in the network with the flooding reduction.





Your proposal is to revert to almost full flooding.  You bound the flooding to three hops (maybe, this is not defined), but in a LS topology, that is the full topology.  This is not a solution.  If we could support full flooding, we would not have problem in the first place.



[HC] This is one optional solution. When multiple failures on the flooding topology happen, the nodes around the failure points revert to their normal (or full) flooding temporarily until a new flooding topology is built. This normal (or full) flooding on some nodes is only temporary for the emergency where multiple failures occur. After the new flooding topology is built on these nodes, they revert to flooding to the links on the flooding topology.

There is another solution in our draft, which is a light-weight method for providing fault tolerance to multiple failures on the flooding topology.





> "draft-li-lsr-dynamic-flooding" just mentions that the edges of split

> parts will do something after the split of the flooding topology happens. However, it needs time to determine if a split of the flooding topology occurs and to find backup paths to connect split parts. There is no description on how to determine a split or find backup paths. This is not useful for implementors or users.





It is described. Please see section 6.7.11. After a topology change, all nodes can examine the existing flooding topology and the faults that have occurred.  If it is clear that the flooding topology has partitioned, then nodes that have adjacencies that are not reachable on the flooding topology make a temporary request to their adjacencies to add to the flooding topology.  This creates a temporary repair until the next flooding topology is distributed.



[HC] From both your draft and your description above, we can not see any details or description on how to determine a node has adjacencies that are not reachable on the flooding topology, and how does the node make a temporary request to their adjacencies to add to the flooding topology.

If the TLV with R bit in IS-IS Hello or FR-bit in OSPF Hello is used to request for adding a link to flooding topology temporarily (or say enabling temporary flooding over the link), then there is a big issue. For example, if the first Hello packet containing the TLV with R bit in IS-IS (or FR-bit in OSPF) gets lost, then the request to add/enable “temporary flooding” on the link will take more than a Hello interval (typically 10 seconds in OSPF). This is too long to accept!



> In addition, the algorithm for computing a flooding topology that can survive any one link failure on the flooding topology (i.e., any one link failure on the flooding topology does not split the flooding topology) will be very complex, at least in terms of time. With a good method for fault tolerance, the algorithm is not required to compute a flooding topology that can survive any one link failure on the flooding topology.





Collapsing the network is not a 'good method'.



[HC] The above paragraph just was proposed as an optional solution, which works and reduces the complexity of the algorithm for computing a flooding topology, but is not mandatory for implementation.





> 3.                  A New Node and Link Addition

>

> Two different procedures for handling a new node and link addition to the topology are described in the two drafts ("draft-li-lsr-dynamic-flooding" and "draft-cc-lsr-flooding-reduction").

>

> The procedure in "draft-cc-lsr-flooding-reduction": After the new node (say node A) and an existing node (say node B) establishes the adjacency over the link, A and B add the link to the flooding topology temporarily until a new flooding topology is built.





If A and B are already on the flooding topology, then this is redundant and harmful.



[HC] It is impossible that a new node A and a new link are on the flooding topology already.





> The procedure in "draft-li-lsr-dynamic-flooding": A new TLV with R bit in IIH (IS-IS Hello), and FR-bit in OSPF Hello LLS Extended Options are defined. The new node (say node A) and an existing node (say node B), send each other the TLV with R bit in IS-IS Hello or FR-bit in OSPF Hello to request for adding the link to flooding topology temporarily (or say enabling temporary flooding over the link).





This only happens if the other node does not appear on the flooding topology.



[HC] The case that we talked is “A New Node and Link Addition” from the title above.

The new node is not on the flooding topology. This case applies to your procedure.



> The procedure in "draft-cc-lsr-flooding-reduction" is simpler and more efficient. We can see that the two procedures try to achieve the same result ("

> temporary flooding" on the link) in different approaches. When a new

> node a nd link is added to the topology/network, it is deterministic

> that the link needs to be added to the flooding topology temporarily

> by the two end node s of the link. There is no need for the end nodes

> to add/enable "temporary flooding" on the link through (new TLV in IIH

> or FR-Bit in OSPF Hello LLS) signaling over the link.





Automatically adding to the flooding topology risks collapsing the network, again contradicting the entire goal of reducing the flooding topology.



[HC] The results produced by the two procedures in the two drafts are the same.

The differences between the two procedures is that one procedure is simpler and more efficient than the other one.

There is no risk collapsing the network. It does not contradict the entire goal of reducing the flooding topology.

The new link is added to the flooding topology “temporarily” by the two end nodes of the link locally.

This link “temporarily” on the flooding topology is not flooded to the other nodes.

It is just for link states to be flooded “temporarily” over this link before a new flooding topology is built.





> During internal review of "draft-li-lsr-dynamic-flooding" we observed

> significant procedure issues, which are big issues for implementations

> and users.  For example in one issue, if the first Hello packet

> containing the TLV with R bit in IS-IS (or FR-bit in OSPF) gets lost,

> then to add/enable "temporary flooding" on the link will take more

> than a Hello interval (typically

> 10 seconds in OSPF). This is too long to accept!





Loss of a hello also implies that the adjacency will be delayed in coming up, so this is the same in both situations.



[HC] There is a case mentioned above, which is only for your draft. The case is under title “2. Fault tolerance to multiple failures”.





> 4.                  An Existing Link Addition

>

> The approach in "draft-cc-lsr-flooding-reduction": The end node sends

> its adjacent node over the adjacency the link states with changes it received or originated during the period of time in which the flooding topology may split.





This requires the implementation to retain state about every LSP on every link, even when it is down.



[HC] There is no such requirement in our approach.

Our approach defines a variable TimeOf1stLinkDown, which stores the time at time the first link on the flooding topology is down after a new flooding topology is built.

It uses the time information of an LSA/LSP in LSDB, the time at which a changed LSA/LSP is received or originated. If a current OSPF/IS-IS implementation does not have this time information, it can be easily added.

When adding an existing link/adjacency not on the flooding topology between two end nodes to the flooding topology after building another new topology, each end node of the link sends its adjacent node over the adjacency the changed LSA/LSPs from TimeOf1stLinkDown if there is a link down (i.e., TimeOf1stLinkDown != 0).

As we explained, this approach is more efficient.





> The approach in "draft-li-lsr-dynamic-flooding": A full LSDB

> resynchronization is requested over the existing adjacency/link between two end nodes for possible flooding topology split which may cause LSDB out of synchronization.





Resynchronization is a normal part of the protocol process at link up anyway.



[HC] This case is not about link up. It is about adding an existing link/adjacency not on the flooding topology between two end nodes to the flooding topology. The following is the original text for your reference:

“Two different approaches for adding an existing link/adjacency not on the flooding topology between two end nodes to the flooding topology are described in the two drafts (“draft-li-lsr-dynamic-flooding” and “draft-cc-lsr-flooding-reduction”).”

Even though the adjacency between two end nodes is already there and their LSDBs are the same in most of situations, your approach still requests for a full LSDB resynchronization, which consumes (or wastes) the power for processing IGP messages and the link bandwidth for transferring IGP messages. This is contradicting with the entire goal of the flooding reduction.



Regards,

Tony