Re: [Srcomp] Comments on REQ-8-17-FWD-EFFICIENCY

[Ron Bonica <[e-mail]>]

Wim,

I disagree. The metric is misleading because it assumes that:


  *   All lookup are equally expensive.
  *   You can reliably determine how many lookups a compression mechanism requires.

Neither of these assumptions are safe.

Normally, I would avoid discussing any particular compression mechanism in the requirements stage. But in this case, it is convenient to illustrate my point using the CRH.

All lookups are not equally expensive
==============================
When a node process a packet that contains the CRH, it might execute the following lookups:


  *   A longest-match lookup of the IPv6 Destination Address in an IPv6 FIB
  *   An indexed lookup of the 16-bit SID in the CRH-FIB

The first lookup (i.e., the longest-match lookup) is relatively expensive because:


  *   The longest-match lookup algorithm is relatively complex
  *   The IPv6 FIB can be very large

The second lookup (i.e., the indexed lookup) is relatively inexpensive because:


  *   The indexed lookup algorithm is relatively simple
  *   The CRH-FIB is likely to be small


It is not always possible to determine how many lookups a compression mechanism requires.
============================================================================

For example, the CRH draft describes a simple implementation that maintains the following data structures:


  *   An IPv6 FIB that is indexed by a prefix and contains a pointer to the forwarding next-hop table
  *   A CRH-FIB that is indexed by a 16-bit SID and contains an IPv6 address and a forwarding method
  *   A forwarding next hop table that contains layer 2 details

Reading through the draft, you might assume that CRH processing requires the following lookups:


  1.  A longest-match lookup of the IPv6 Destination Address in an IPv6 FIB
  2.  An indexed lookup of the 16-bit SID in the CRH-FIB
  3.  Another longest-match lookup. This time, we are searching for the IPv6 address that we found in the CRH-FIB. Again, we are searching in the IPv6 FIB.

However, this would be a sub-optimal implementation. An optimized implementation would contain the following data structures:


  *   An IPv6 FIB that is indexed by a prefix and contains a pointer to the forwarding next-hop table
  *   A CRH-FIB that is indexed by a 16-bit SID and contains an IPv6 address and a * pointer to the forwarding next-hop table*
  *   A forwarding next hop table that contains layer 2 details


This implementation requires only the following lookups:


  1.  A longest-match lookup of the IPv6 Destination Address in an IPv6 FIB
  2.  An indexed lookup of the 16-bit SID in the CRH-FIB

A third lookup is not required because the CRH-FIB contains a pointer to the forwarding next hop table. This implementation is relatively efficient, because it requires one longest-match lookup and one indexed lookup, as opposed to many others that require two longest-match lookups.

This was a fairly obvious optimization. For any compression mechanism, there may be many optimizations that are not so obvious.







Juniper Business Use Only
From: Henderickx, Wim (Nokia - BE/Antwerp) <[e-mail]>
Sent: Thursday, September 24, 2020 12:23 AM
To: Ron Bonica <[e-mail]>; srcomp <[e-mail]>
Subject: Re: [Srcomp] Comments on REQ-8-17-FWD-EFFICIENCY

[External Email. Be cautious of content]

I do believe there is value in showing the lookups needed for a certain proposal for srcomp and compare them. The reason is this technology will be implemented by many asic (hopefully) and less lookups will be better. The more you need the more transistors/memory you burn and the result will be less performance in a given package. As such this is an important factor in the comparison of the options in my view.

In other words a solution that does 2 lookup versus 3 will be more future safe.

From: Srcomp <[e-mail]<mailto:[e-mail]>> on behalf of Ron Bonica <rbonica=[e-mail]<mailto:rbonica=[e-mail]>>
Date: Wednesday, 23 September 2020 at 21:06
To: "[e-mail]<mailto:[e-mail]>" <[e-mail]<mailto:[e-mail]>>
Subject: [Srcomp] Comments on REQ-8-17-FWD-EFFICIENCY

Folks,

The metrics associate with REQ-8-17-FWD-EFFICIENCY are invalid. Currently, the metrics are:


  *   D.PRS(segment list): worst-case number of headers parsed during processing of the segment list.
  *   D.LKU(segment list): worst-case number of FIB lookups during processing of the segment list.

D.PRS assumes that parsing a second extension header is expensive on all ASICs. While it may be expensive on some ASIC's it is extremely inexpensive on others. Retaining this metric doesn't optimize the solution for operators. It merely creates an advantage for the ASIC that can't parse additional extension headers efficiently.

D.LKU assumes that it is possible to determine how many lookups a particular compression mechanism requires. It ignores the fact that the FIB can be optimized to reduce the number of lookups. Furthermore, it fails to make a distinction between longest match lookups and index lookups.

Finally, this requirement should be stated from the network operators perspective, not the ASIC developer's. The network operator doesn't care how many headers were parsed or how many lookups were execute. It cares about:


  *   How many packet per second the ASIC can process
  *   How much power the ASIC consumes
  *   How much heat the ASIC generates
  *   How much the ASIC costs

Unless we can develop better metric for this requirement, we should drop it.

                                                                                           Ron





Juniper Business Use Only