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

From: "Henderickx, Wim (Nokia - BE/Antwerp)" <[email-masked]>
Date: Thu, 24 Sep 2020 04:22:46 +0000

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 <[email-masked]> on behalf of Ron Bonica <rbonica=[email-masked]>
Date: Wednesday, 23 September 2020 at 21:06
To: "[email-masked]" <[email-masked]>
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

---

From: "Chengli (Cheng Li)" <[email-masked]>
Date: Thu, 24 Sep 2020 09:29:18 +0000

Hi Wim and Ron,

I agree with Wim. There is value to show the times of lookup. Some forwarding efficiency MUST be dropped in any extra table lookup.

Please see my reply inline.

Respect,
Cheng

From: Srcomp [mailto:[email-masked]] On Behalf Of Henderickx, Wim (Nokia - BE/Antwerp)
Sent: Thursday, September 24, 2020 12:23 PM
To: Ron Bonica <rbonica=[email-masked]>; srcomp <[email-masked]>
Subject: Re: [Srcomp] Comments on REQ-8-17-FWD-EFFICIENCY

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

Folks,

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

[Cheng] Sure, different hardware have different capabilities. We may specify what kind of hardware, correct? Also, why we only list the worst-case?

We should list all the possible cases, the best case, normal cases, and the worst case.

Also, the percentage of each cases should be provided. Like, in  0.1 percent to have the worst case, then there is no meaning to analysize it? But if in 10 or more percent we will meet the worst case, then it is valuable to have the data.

[Cheng] Yes, FIB can be optimized to reduce the number of lookups, this should be explicitly noted.

Also, the forwarding efficiencies of using LPM and EM are different. But for some vendors’ hardware, they can make them almost the same. I think it depends on the hardware implementation. Perhaps, we can do some theoretical analysis?

-          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

                                                                                           Ron

---

From: Ron Bonica <[email-masked]>
Date: Thu, 24 Sep 2020 21:54:58 +0000

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) <[email-masked]>
Sent: Thursday, September 24, 2020 12:23 AM
To: Ron Bonica <[email-masked]>; srcomp <[email-masked]>
Subject: Re: [Srcomp] Comments on REQ-8-17-FWD-EFFICIENCY

[External Email. Be cautious of content]

Folks,

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.

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:

                                                                                           Ron

---

From: Ron Bonica <[email-masked]>
Date: Fri, 25 Sep 2020 00:07:00 +0000

Cheng,

Adding to my last email.....

Network operators care about the efficiency of implementations. They want to know that:

  *   Implementation A of compression mechanism A can forward N packets per second
  *   Implementation B of compression mechanism A can forward M packets per second
  *   Implementation A of compression mechanism B can forward P packets per second
  *   Implementation B of compression mechanism B can forward Q packets per second

The comparison would be even more meaningful of all implementations consumed the same amount of power, generated the same amount of heat, and were available at the same price.

Sadly, we can't provide such metrics. So, we generate metrics like D.PRS and D.IKU, hoping that they estimate the metrics that network operators really want. Sadly, we have no guarantee that D.PRS or D.IKU can estimate the desired metrics.

In order to estimate the desired metrics, we would have to measure *every* operation that the compression mechanism executes (e.g., bit shifting). Then, we would have to assign a relative cost to each operation. It is impossible to assign a relative cost to each operation because:

  *   An operation might be expensive on one platform and inexpensive on another
  *   All instances of an operation may not have the same cost (e.g., longest-match lookups versus indexed lookups)

In summary, I think that D.PRS and D.IKU may do more harm than good, because they may be interpreted as estimates of the desired metrics, even though they are not.

                                                                                                Ron

Juniper Business Use Only
From: Srcomp <[email-masked]> On Behalf Of Chengli (Cheng Li)
Sent: Thursday, September 24, 2020 5:29 AM
To: Henderickx, Wim (Nokia - BE/Antwerp) <[email-masked]>; Ron Bonica <rbonica=[email-masked]>; srcomp <[email-masked]>
Subject: Re: [Srcomp] Comments on REQ-8-17-FWD-EFFICIENCY

Hi Wim and Ron,

Respect,
Cheng

From: Srcomp [mailto:[email-masked]] On Behalf Of Henderickx, Wim (Nokia - BE/Antwerp)
Sent: Thursday, September 24, 2020 12:23 PM
To: Ron Bonica <rbonica=[email-masked]<mailto:rbonica=[email-masked]>>; srcomp <[email-masked]<mailto:[email-masked]>>
Subject: Re: [Srcomp] Comments on REQ-8-17-FWD-EFFICIENCY

Folks,

Also, the forwarding efficiencies of using LPM and EM are different. But for some vendors' hardware, they can make them almost the same. I think it depends on the hardware implementation. Perhaps, we can do some theoretical analysis?

                                                                                           Ron

---

From: <[email-masked]>
Date: Fri, 25 Sep 2020 10:09:29 +0800 (CST)

Hi all,

For this point, I agree with Ron. 

If I didn't understand it wrong, an additional index based table can contain full forwarding information, that is easy to do this and implementation related, so that it is exactly an optimization to LPM (i.e, another longest-match looking up according to updated DA after obtaining the next SID is avoied), but not never a degradation to forwarding performance.

I think any optimization that avoids LPM is worth trying.

Regards,

PSF

原始邮件

发件人：RonBonica
收件人：Henderickx, Wim (Nokia - BE/Antwerp);srcomp;
日 期 ：2020年09月25日 05:55
主 题 ：Re: [Srcomp] Comments on REQ-8-17-FWD-EFFICIENCY

-- 
Srcomp mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/srcomp

Wim,

 

All lookup are equally expensive.

You can reliably determine how many lookups a compression mechanism requires.

 

 

 

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 longest-match lookup algorithm is relatively complex

The IPv6 FIB can be very large

 

The indexed lookup algorithm is relatively simple

The CRH-FIB is likely to be small

 

 

 

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

 

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

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.

 

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

 

 

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

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.

 

 

 

 

 

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.

 

 

Folks,

 

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.

 

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

 

                                                                                           Ron

---

From: <[email-masked]>
Date: Fri, 25 Sep 2020 10:14:39 +0800 (CST)

Sorry for spelling mistakes, I mean 

" but never a degradation to forwarding performance", 

not

 "but not never ..."

Regards,

PSF

原始邮件

发件人：彭少富10053815
收件人：RonBonica;
抄送人：Henderickx, Wim (Nokia - BE/Antwerp);srcomp;
日 期 ：2020年09月25日 10:09
主 题 ：Re:[Srcomp] Comments on REQ-8-17-FWD-EFFICIENCY

Hi all,

Regards,

PSF

发件人：RonBonica

Wim,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Folks,

 

 

 

 

 

How much the ASIC costs

 

                                                                                           Ron

---

From: "Henderickx, Wim (Nokia - BE/Antwerp)" <[email-masked]>
Date: Fri, 25 Sep 2020 03:57:28 +0000

I am not implying the expenses of a lookup, but implementations that have fewer will be able to do more with the same die. I think you bring up a god point and we should also asses the complexity of the lookup and use that in the metric.

It might be worth doing this given some scenario’s/deployments and asses this in such context. At least people get a view of what we are talking about

From: Ron Bonica <[email-masked]>
Date: Thursday, 24 September 2020 at 23:55
To: "Henderickx, Wim (Nokia - BE/Antwerp)" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: RE: [Srcomp] Comments on REQ-8-17-FWD-EFFICIENCY

Wim,

Folks,

                                                                                           Ron