Subject: [Lsr] Enhancements on flooding topology encoding

From: Huaimo Chen <[email-masked]>
Date: Wed, 15 May 2019 15:42:08 +0000

Hi Tony,

Two enhancements for the flooding topology encoding using Path TLVs, and another flooding topology encoding using Block TLVs are described below for discussions.

In one current encoding, Path TLVs are used to encode the flooding topology. A Path TLV represents a path on the flooding topology. The value field of a Path TLV contains the indexes of the nodes on the path in order from one end of the path to the other end of the path. The size of the index in the TLV is 16 bits. This may be optimized in a couple of ways.

In one way, a TLV called Node Index Size TLV is defined. Its value field of one octet contains an index size (i.e., a number of bits). When this TLV is included in an LSP/LSA containing Path TLVs, all the node indexes in the Path TLVs are represented using the number of bits given by the index size in the Node Index Size TLV. The index size is the minimum number of bits needed to represent the maximum node index in the Path TLVs.

In another way, 5 bits of the Reserved field in the IS-IS Area System IDs TLV and OSPF Area Node IDs TLV with L set to one indicates the index size that is used for all the node indexes in all the Path TLVs included in every LSP/LSA. The index size is the minimum number of bits needed to represent the maximum node index in the area.

In another encoding, Block TLVs are used to encode the flooding topology. A Block TLV represents a block of the flooding topology.  The value field of a Block TLV starts with 5 bits to indicate the index size, which is followed by the index of a local node, the number of adjacent nodes (in 3 bits), and the indexes of the adjacent/remote nodes of the local node. This part is similar to the one in a router LSA to represent the part of the topology from the local node to the adjacent nodes of the local node, which can be considered as a block of the topology in one level. This block can be extended to multiple levels. Each of the adjacent nodes has an extension flag bit E.  An adjacent/remote node with E = 1 is considered as a new local node, and its adjacent nodes are added. This encoding seems more efficient.

Best Regards,

Huaimo

---

From: [email-masked]
Date: Wed, 15 May 2019 08:55:04 -0700

Hi Huaimo,

> In one way, a TLV called Node Index Size TLV is defined. Its value field of one octet contains an index size (i.e., a number of bits). When this TLV is included in an LSP/LSA containing Path TLVs,…

Yes, Tony P. also made this suggestion quite some time ago in a private communication.  We also observed that no separate signaling of the size is actually needed, as each node can look at the number of indices listed in the Node Id TLV and take ceil(log2(# nodes)) and use that many bits for each index.
 
> In another way, 5 bits of the Reserved field in the IS-IS Area System IDs TLV and OSPF Area Node IDs TLV with L set to one indicates the index size that is used for all the node indexes in all the…

Yes, you could do that too.  That’s for ‘free’, assuming that you agree that the L bit is required.

> In another encoding, Block TLVs are used to encode the flooding topology. A Block TLV represents a block of the flooding topology.  The value field of a Block TLV starts with 5 bits to indicate the…

A bold claim.  Do you have any proof for this?  It seems counter-intuitive, as for a bi-connected node, it would seem that its index must appear at least twice, once per link.  

The advantage of the path encoding is that for almost all nodes, an index can appear a single time.

Example:

IS-IS Instance: Amun VRF: default
  Level 1:
    Path: 3 16 8
    Path: 0 18 9 10 11 17 15 6
    Path: 0 13 1 19 5 4 14 8
    Path: 0 3 6 7 2 8 12 0

Tony