Subject: [forces] LFBLib v3: comment #2 LPM/NH

From: Jamal Hadi Salim <[email-masked]>
Date: Thu, 10 Mar 2011 09:48:48 -0500

I am going to skip a few other issues i have and jump to this one
because it may take more discussion to resolve.

Implementations vary but the most common denominator for ASICs
involves passing some index to some NH table or LFB to find the
NH details. Typically the NH info is pre-populated by the CE when
the route entry in the LPM is set.
For software based FEs alternatively the NH information
could be resolved at runtime (although even Linux allows for ARP to
be offloaded to user space).
If i am reading correctly, the document assumes a non-offload only.
My fear is we are adding unnecessary overhead for the offload
scheme - therefore we need to support both models.

cheers,
jamal

---

From: "Joel M. Halpern" <[email-masked]>
Date: Fri, 11 Mar 2011 13:54:17 -0500

Sorry, I missed something.

I do not know what "resolved at run time" means in this context.  This 
tables are always dynamically filled in every implementation, hardware 
or software.

The table structure in the model separates the LPM from the NextHop, 
with the LPM returning an index for the nexthop.  That allows the common 
hardware implementation.
If the implementation wants a single-stage lookup, then the FE keeps 
track of the two sets of information, and folds them together to 
populate the single table.  it can do this under the covers perfectly 
legitimately.  (Such an implementation would declare in its capabilities 
that an LPM must be followed by a next-hop table, so that the CE does 
not try to insert anything between the two pieces.

Yours,
Joel

On 3/10/2011 9:48 AM, Jamal Hadi Salim wrote:
> _______________________________________________
> forces mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/forces
>

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sat, 12 Mar 2011 11:16:48 -0500

Whatever model conceptualization one chooses will always be favoring one
implementation approach over another. Yes, modelling shouldnt care
about those details but to be fair and to make ForCES more usable, we need
to minimally justify the choices made. If i was doing a MIB i wouldnt  worry
as much - but my view is we are too close to the metal to ignore things....
I think it may be sufficient in the document to pick a few examples of
real world approaches and say how one would morph the LFBlib model
onto them. Joel, your email provided one such example at the end.
There are many others...

I will try to be verbose below to flesh out some details.

For the sake of context in discussion, let me repeat what a successful
LPM lookup must provide:
1) NH details i.e i) what port to go out and ii) what destination
MACaddr to use
2) src details i.e i) what src MACaddr to use ii) optionally what VLAN
info to use.

I will try to spell out the variables involved in modeling the above in an
implementation.
There are a lot of permutations on how info can be stored in an FE and how
a packet traverses them; I am going to use the two that have come up so
far in the last 2 emails:

A) both #1 and #2 in the LPM table - if all you are implementing is an
L3 router, this would be a lot more efficient lookup-wise at the expense
of storage and modularity. A lot of software implementations go this path.
B) #1 and #2 in separate tables (from the LPM table). A lot of ASICs
implement this way. This is clearly more efficient storage wise, definetely
more modular, but I doubt it can beat #A lookup cycle-wise.

The LFBlib went with a variant of #B without saying why.
The LFBlib should also say what other approaches should provide an
example or two of how to scrape/massage information from the CE to
their datapath.

If you go with #B, then:
- there are several permutations on what each table takes as input.
For example, the LFBlib uses an IP address as an index to lookup the
NH. An IP address implies context lookup; the typical approach is to
use a table index. We dont say why.
- there are several permutations of the details of the different tables get
populated in order to approach the lookup efficiency of #A. The most common
trick is "offloading" things like ARP/ND to the CE and pre-populating all the
required tables from the CE once we know the route.

The LFBlib approach implies an ARP/ND living at the FE.
I think we need to allow for a minimal the ARP/ND offloading to the CE
in addition. I am not sure what to do with the IP address as metadata for
NH lookup (it looks clever and fits well with a datapath NH resolution, but
there is no need for it in a datapath).

I apologize for the long email - I hope my view was not lost in
the details at the end.

cheers,
jamal

On Fri, Mar 11, 2011 at 1:54 PM, Joel M. Halpern <[email-masked]> wrote:
> tables are always dynamically filled in every implementation, hardware or
> software.
>
> The table structure in the model separates the LPM from the NextHop, with
> the LPM returning an index for the nexthop.  That allows the common hardware
> implementation.
> If the implementation wants a single-stage lookup, then the FE keeps track
> of the two sets of information, and folds them together to populate the
> single table.  it can do this under the covers perfectly legitimately.
>  (Such an implementation would declare in its capabilities that an LPM must
> be followed by a next-hop table, so that the CE does not try to insert
> anything between the two pieces.
>
> Yours,
> Joel
>

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sun, 13 Mar 2011 12:01:36 -0400

Two points:

1) I thought we had articulated why we went with the decomposed 
structure (what you call B) rather than combined.  The basic reason is 
that it is easy for an FE to transform a decomposed structure into a 
combined implementation.  It is hard for an FE to decompose a combined 
structure into a separated implementation.  (I will admit that the fact 
that virtually all routers use the decomposed structure was also 
relevant., but I believe the above was the primary reason.)

2) The structure proposed does not require ARP/ND protocol processing to 
be on the FE.  The most likely CE implementation of ARP/ND that is 
relevant is taht for any routing next hop, the CE does the ARP/ND 
resolution first, so it can fill in the table on the FE.  (Yes, the 
ARP/ND tables are needed, but the protocol processing isn't.)

Yours,
Joel

PS: I thought we had this discussion years ago.

On 3/12/2011 11:16 AM, Jamal Hadi Salim wrote:
> On Fri, Mar 11, 2011 at 1:54 PM, Joel M. Halpern<[email-masked]>  wrote:

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sun, 13 Mar 2011 13:03:22 -0400

On Sun, Mar 13, 2011 at 12:01 PM, Joel M. Halpern <[email-masked]> wrote:
> Two points:
>
> 1) I thought we had articulated why we went with the decomposed structure
> (what you call B) rather than combined.  The basic reason is that it is easy
> for an FE to transform a decomposed structure into a combined
> implementation.  It is hard for an FE to decompose a combined structure into
> a separated implementation.  (I will admit that the fact that virtually all
> routers use the decomposed structure was also relevant., but I believe the
> above was the primary reason.)

Iam sorry for rehashing this specific point; i did that mainly to
provide a context
for the ARP/ND resolution (point #2 below). But there is still confusion even
if we ignored the ARP/ND issue which i think could be cleared with at least
some example text (maybe an appendix) what the massaging constitutes.
[I had someone who had done an L3 ASIC in the past (the combined approach)
and he was confused as to how he would fit without a huge amount of scrapping.]

> 2) The structure proposed does not require ARP/ND protocol processing to be
> on the FE.  The most likely CE implementation of ARP/ND that is relevant is
> taht for any routing next hop, the CE does the ARP/ND resolution first, so
> it can fill in the table on the FE.  (Yes, the ARP/ND tables are needed, but
> the protocol processing isn't.)

Thats my feeling as well. That is not the proposal in this document.
The approach discussed considers that an LPM entry can exist
without a resolved corresponding NH entry. i.e, the LPM points to the
neighbors IP address and further downstream, the packet processing
assumes it needs to resolve an ARP/ND for that neighbors IP address
and does that while buffering the packet (whose LPM is already resolved)
somewhere.
I actually like this scheme (it is the approach Linux kernel uses)
but i think we need to allow for the model you described; besided
that one could argue that in a dynamic routing environment
the approach described is susceptible to a race condition where
the NH for the destination may change while we are waiting for the
neighbor to be resolved via ARP/ND.

Again apologies for the long email - i dont have a TL;DR version.

cheers,
jamal

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 14 Mar 2011 21:57:51 -0400

In line.

On 3/13/2011 1:03 PM, Jamal Hadi Salim wrote:
> On Sun, Mar 13, 2011 at 12:01 PM, Joel M. Halpern<[email-masked]>  wrote:
>> Two points:
>>

The quesiton I guess is whether he understood the basic idea that he can 
mapp the tables together in the FE processor, or whether the ability to 
build intermediate structures there had not occurred to him.  WIthout 
those, it would be hard.  With those, I think it is easy.
Doing it the other way appears somewhat harder no matter what.
And trying to do it both ways will, I fear, create confused and 
complicated CEs.

> neighbor to be resolved via ARP/ND.
I think my description works with the structure in the document.  It can 
use some extra descriptive words.  Even if the logic is ostensibly set 
up so that one can take a miss on the ARP/ND table, the CE can still 
prepopulate everything.

The piece we are missing probably is that there ought to be a hook so 
that the CE can tell that it needs to provide the ARP/ND and 
prepopulation functionality.  If we have done things right, taht could 
be represented simply by the FE not supporting certain LFBs.  But we 
still need a place for the table.

Yours,
Joel

---

From: Jamal Hadi Salim <[email-masked]>
Date: Tue, 15 Mar 2011 09:14:50 -0400

On Mon, Mar 14, 2011 at 9:57 PM, Joel M. Halpern <[email-masked]> wrote:

> build intermediate structures there had not occurred to him.  WIthout those,
> it would be hard.  With those, I think it is easy.

My take was he thought it was too much work. But probably would have been
easier if it was explained sufficiently well in the doc. I am going to try and
use him as the guinea-pig to see what kind of info we need to provide.

> And trying to do it both ways will, I fear, create confused and complicated
> CEs.

No need to change the current approach (Like you said we resolved
that at least 2 years back). We just need to have better explanation for
issues like above.

> I think my description works with the structure in the document.  It can use
> some extra descriptive words.  Even if the logic is ostensibly set up so
> that one can take a miss on the ARP/ND table, the CE can still prepopulate
> everything.

True.

> The piece we are missing probably is that there ought to be a hook so that
> the CE can tell that it needs to provide the ARP/ND and prepopulation
> functionality.  If we have done things right, taht could be represented
> simply by the FE not supporting certain LFBs.  But we still need a place for
> the table.

That would be a good start but i think we need to do more; not sure where
to start maybe we need to review that whole path, here's one part that
bothers me:

Currently:
1) LPM feeding a NH applicator a NHID
2) NH applicator only finds one destination detail: the output port
3) NH applicator feeds etherencap an IP address and output portid
4) Somewhere within Etherencap we take the IP(4/6) address and do a
lookup then we either ARP or find the dstMAC address.
5) We then find the src info (srcMAC and VLAN)

I think the idea of an IP address passed in #4 is useful for the assumption
that we are going to resolve the dst link address downstream (which i dont
mind supporting) but an IP address implies content search which someone
is going to have to scrape if they use an index to do the src info.

What most common (ASIC, ignoring ECMP) approaches do is something like:

1) LPM feeds into some form of NH applicator with a NHID
2) NHapplicator finds _all_ of the destination info (output port + dstMAC)
3) NH applicator feeds into some form etherencap a srcindex
used to select a pre-populated table with srcMAC and VLAN.

So #2 and #3 are very different from the current approach and whoever
has a scheme like this will have to maintain a lot of scrapping/translation.

cheers,
jamal

---

From: "Joel M. Halpern" <[email-masked]>
Date: Tue, 15 Mar 2011 13:51:44 -0400

I think the NH applicator selects the NHOP IP address.
I suspect that we have been sloppy, because this has to work with 
unnumbered point-to-point links too.

The MAC lookup is based not on the original IP address, but rather on 
the next-hop IP address.

Yours,
Joel

On 3/15/2011 9:14 AM, Jamal Hadi Salim wrote:
...
> is going to have to scrape if they use an index to do the src info.
...

---

From: Jamal Hadi Salim <[email-masked]>
Date: Thu, 17 Mar 2011 08:53:49 -0400

> I think the NH applicator selects the NHOP IP address.

It is.

> I suspect that we have been sloppy, because this has to work with unnumbered
> point-to-point links too.

Did not think of this but that may be a good reason to revisit.

So we need further discussion at the meeting? I have other issues
i want to raise..

cheers,
jamal