Re: [Lsr] Enhancements on flooding topology encoding

[Acee Lindem (acee)]

Speaking as WG member:

Huaimo,

I’m against adding more complexity to the encoding. I don’t even really like 
that we’ve evolved to a level of indirection for Router-iDs and System-IDs just 
to save a few bytes. In the case of OSPF, where there can be multiple LSAs for 
the flooding topology, I see this as unneeded complexity since if the flooding 
topology changes, a clever implementation will have used “reasonable” sized 
LSAs and only update the one(s) that change.

I’m adamantly opposed to any optimizations involving bit shifting and masking. 
Please cease and desist 😉

Thanks,
Acee

From: Lsr  on behalf of Huaimo Chen 
Date: Wednesday, May 29, 2019 at 11:07 PM
To: Tony Li 
Cc: "lsr@ietf.org" 
Subject: Re: [Lsr] Enhancements on flooding topology encoding


Hi Tony,



Thank you for your comments!

My explanations are inline below.


Best Regards,
Huaimo

From: Tony Li  on behalf of tony...@tony.li 

Sent: Wednesday, May 29, 2019 11:20 AM
To: Huaimo Chen
Cc: lsr@ietf.org
Subject: Re: Enhancements on flooding topology encoding


Hi Huaimo,

Thank you for the interesting numbers, but without some understanding of the 
experiment that you’re performing, we have no way of understanding the point 
that you’re trying to make.

If we are to make a change, we need to all understand and agree that there is 
an improvement and that the improvement is worthwhile in terms of complexity 
vs. gain.

The block encoding that you have proposed seems to require at least one TLV for 
every other node in a path and thus seems like an extremely inefficient way of 
encoding a topology. If you have ways of using this efficiently, please explain.

[HC] There is no such requirement. A block of FT (maybe a whole FT) can be 
encoded in a Block TLV. A path can be considered as a special block of FT and 
encoded in a Block TLV.

Compressing the path TLV into a bit stream (similar to encoding B) has been 
proposed, but to date we have not bit off on that complexity.  As noted, the 
savings that you get decrease with scale, which is unfortunate because at scale 
is when we need it.  So far, the consensus seems to be that this is not worth 
the effort.

[HC] It seems that there is no issue on scale.

Regards,
Tony




On May 29, 2019, at 8:05 AM, Huaimo Chen 
mailto:hc...@futurewei.com>> wrote:

Hi Tony,

For the three encodings below,
· Encoding A: Plain Path TLVs, where each node index uses 2 bytes,
· Encoding B: Compact Path TLVs, where each of node indexes in Path 
TLVs has the same size given by a field in the Area Node IDs TLV with L set to 
one, which is the size (in bits) of the maximum node index value,
· Encoding C:  Block TLVs,
it seems that C is more efficient than A and B in general, B is more efficient 
than A.
For example, for representing 63 nodes flooding topology (FT for short) of a 
binary tree in IS-IS, some comparisons among three encodings are listed in the 
table below (In case that the formats may be messed up, a .pdf file is 
attached).

Encoding
Bytes used
Comparisons
A (Plain Path TLVs)
248
179/248 = 0.72 (72%)
B (Compact Path TLVs)
179
121/179 = 0.68 (68%)
C (Block TLVs)
121
121/248 = 0.49 (49%)


From the table, we can see that 248, 179 and 121 bytes are used for 
representing the FT by A, B and C respectively. 121/248 = 0.49 (49%) means that 
C uses about 49% of the flooding resource that A uses. 121/179 = 0.68 (68%) 
means that C uses about 68% of the flooding resource that B uses. 179/248=0.72 
(72%) means that B uses about 72% of the flooding resource that A uses.

From this example, we can see that C is more efficient than A and B, and B 
is more efficient than A.

Best Regards,
Huaimo
From: Tony Li [mailto:tony1ath...@gmail.com] On Behalf Of 
tony...@tony.li<mailto:tony...@tony.li>
Sent: Wednesday, May 15, 2019 11:55 AM
To: Huaimo Chen 
Cc: lsr@ietf.org
Subject: Re: Enhancements on flooding topology encoding




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, 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..




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 Path TLVs included in every LSP/LSA. 

Re: [Lsr] Enhancements on flooding topology encoding

[Huaimo Chen]

Hi Tony,


Thank you for your comments!

My explanations are inline below.


Best Regards,
Huaimo

From: Tony Li  on behalf of tony...@tony.li 

Sent: Wednesday, May 29, 2019 11:20 AM
To: Huaimo Chen
Cc: lsr@ietf.org
Subject: Re: Enhancements on flooding topology encoding


Hi Huaimo,

Thank you for the interesting numbers, but without some understanding of the 
experiment that you’re performing, we have no way of understanding the point 
that you’re trying to make.

If we are to make a change, we need to all understand and agree that there is 
an improvement and that the improvement is worthwhile in terms of complexity 
vs. gain.

The block encoding that you have proposed seems to require at least one TLV for 
every other node in a path and thus seems like an extremely inefficient way of 
encoding a topology. If you have ways of using this efficiently, please explain.

[HC] There is no such requirement. A block of FT (maybe a whole FT) can be 
encoded in a Block TLV. A path can be considered as a special block of FT and 
encoded in a Block TLV.

Compressing the path TLV into a bit stream (similar to encoding B) has been 
proposed, but to date we have not bit off on that complexity.  As noted, the 
savings that you get decrease with scale, which is unfortunate because at scale 
is when we need it.  So far, the consensus seems to be that this is not worth 
the effort.

[HC] It seems that there is no issue on scale.

Regards,
Tony



On May 29, 2019, at 8:05 AM, Huaimo Chen 
mailto:hc...@futurewei.com>> wrote:

Hi Tony,


For the three encodings below,

  *   Encoding A: Plain Path TLVs, where each node index uses 2 bytes,
  *   Encoding B: Compact Path TLVs, where each of node indexes in Path TLVs 
has the same size given by a field in the Area Node IDs TLV with L set to one, 
which is the size (in bits) of the maximum node index value,
  *   Encoding C:  Block TLVs,

it seems that C is more efficient than A and B in general, B is more efficient 
than A.
For example, for representing 63 nodes flooding topology (FT for short) of a 
binary tree in IS-IS, some comparisons among three encodings are listed in the 
table below (In case that the formats may be messed up, a .pdf file is 
attached).

Encoding
Bytes used
Comparisons
A (Plain Path TLVs)
248
179/248 = 0.72 (72%)
B (Compact Path TLVs)
179
121/179 = 0.68 (68%)
C (Block TLVs)
121
121/248 = 0.49 (49%)



From the table, we can see that 248, 179 and 121 bytes are used for 
representing the FT by A, B and C respectively. 121/248 = 0.49 (49%) means that 
C uses about 49% of the flooding resource that A uses. 121/179 = 0.68 (68%) 
means that C uses about 68% of the flooding resource that B uses. 179/248=0.72 
(72%) means that B uses about 72% of the flooding resource that A uses.

From this example, we can see that C is more efficient than A and B, and B 
is more efficient than A.


Best Regards,
Huaimo
From: Tony Li [mailto:tony1ath...@gmail.com] On Behalf Of 
tony...@tony.li
Sent: Wednesday, May 15, 2019 11:55 AM
To: Huaimo Chen 
Cc: lsr@ietf.org
Subject: Re: Enhancements on flooding topology encoding





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, 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.





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 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.





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 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 bl

Re: [Lsr] Enhancements on flooding topology encoding

[tony . li]

Hi Huaimo,

Thank you for the interesting numbers, but without some understanding of the 
experiment that you’re performing, we have no way of understanding the point 
that you’re trying to make.

If we are to make a change, we need to all understand and agree that there is 
an improvement and that the improvement is worthwhile in terms of complexity 
vs. gain.

The block encoding that you have proposed seems to require at least one TLV for 
every other node in a path and thus seems like an extremely inefficient way of 
encoding a topology. If you have ways of using this efficiently, please explain.

Compressing the path TLV into a bit stream (similar to encoding B) has been 
proposed, but to date we have not bit off on that complexity.  As noted, the 
savings that you get decrease with scale, which is unfortunate because at scale 
is when we need it.  So far, the consensus seems to be that this is not worth 
the effort.

Regards,
Tony



> On May 29, 2019, at 8:05 AM, Huaimo Chen  wrote:
> 
> Hi Tony,
> 
> For the three encodings below,
> Encoding A: Plain Path TLVs, where each node index uses 2 bytes,
> Encoding B: Compact Path TLVs, where each of node indexes in Path TLVs has 
> the same size given by a field in the Area Node IDs TLV with L set to one, 
> which is the size (in bits) of the maximum node index value,
> Encoding C:  Block TLVs,
> it seems that C is more efficient than A and B in general, B is more 
> efficient than A.
> For example, for representing 63 nodes flooding topology (FT for short) of a 
> binary tree in IS-IS, some comparisons among three encodings are listed in 
> the table below (In case that the formats may be messed up, a .pdf file is 
> attached).
> 
> Encoding
> Bytes used
> Comparisons
> A (Plain Path TLVs)
> 248
> 179/248 = 0.72 (72%)
> B (Compact Path TLVs)
> 179
> 121/179 = 0.68 (68%)
> C (Block TLVs)
> 121
> 121/248 = 0.49 (49%)
>  
> From the table, we can see that 248, 179 and 121 bytes are used for 
> representing the FT by A, B and C respectively. 121/248 = 0.49 (49%) means 
> that C uses about 49% of the flooding resource that A uses. 121/179 = 0.68 
> (68%) means that C uses about 68% of the flooding resource that B uses. 
> 179/248=0.72 (72%) means that B uses about 72% of the flooding resource that 
> A uses.
> 
> From this example, we can see that C is more efficient than A and B, and 
> B is more efficient than A.
> 
> Best Regards,
> Huaimo
> From: <> Tony Li [mailto:tony1ath...@gmail.com] On Behalf Of tony...@tony.li
> Sent: Wednesday, May 15, 2019 11:55 AM
> To: Huaimo Chen 
> Cc: lsr@ietf.org
> Subject: Re: Enhancements on flooding topology encoding
>  
>  
> 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, 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.
>  
>  
> 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 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.
>  
>  
> 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 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.
>  
>  
> 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.  
>  
> Th

Re: [Lsr] Enhancements on flooding topology encoding

[tony . li]

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, 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.


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 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.


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 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.


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


___
Lsr mailing list
Lsr@ietf.org
https://www.ietf.org/mailman/listinfo/lsr

[Lsr] Enhancements on flooding topology encoding

[Huaimo Chen]

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

___
Lsr mailing list
Lsr@ietf.org
https://www.ietf.org/mailman/listinfo/lsr