Subject: Re: [Forces-protocol] RE: Protocol/model discussion?

From: "Khosravi, Hormuzd M" <[email-masked]>
Date: Wed, 11 Aug 2004 14:28:30 -0700

I agree with this notion as well, based on our implementation
experience. 
Just using indexing could force the CE to maintain a lot of state.

Hormuzd

-----Original Message-----
From: Forwarding and Control Element Separation
[mailto:[email-masked]] On Behalf Of Steven Blake

>
> I would strongly suggest that given the information the CE has, we
just use
> normally indexed arrays, not associative lookups <bold> for CE access
> </bold>.

I can give a counter example where it would be desirable for the CE to
be able to access a FE table by value and not by index: a prefix table.
The CE will have to maintain one or more FIBs, each distributed to one
or more (or all) FEs.  It is fairly easy for the CE to maintain the FEs'
prefix tables by feeding updates (inserts/delete by value) to them as
its FIBs are updated, without maintaining copies of each FE's prefix
tables.

Regards,

// Steve

---

From: "Joel M. Halpern" <[email-masked]>
Date: Wed, 11 Aug 2004 17:39:03 -0400

Clearly, I am missing something.

The CE needs to know what the FE has in its tables.
If the different FEs are structured differently, the CE will have to manage
them separately, so I will assume that we are dealing with similar FEs.
In that case, all the CE needs to do to use direct indexing is to keep
track, for each FE, of what slot it has put the forwarding entry in.  This
is not difficult for it to track.
Adding content based array's to the ForCES data model seems a significant
complexity.  And it definitely adds complexity to the process of selecting
elements.

If we really need it, I suppose we should add it.  But at the moment I am
missing why the CE can not easily have enough information to just use
direct indexing.

Yours,
Joel

---

From: John Renwick <[email-masked]>
Date: Thu, 12 Aug 2004 08:42:49 -0500

Joel,

...
> is not difficult for it to track.

Some prefix lookup structures (that aren't based on CAMs) don't have the
concept of a "slot"; the prefix value itself is the natural way of
referencing an entry.  To allow the structure to be referenced by an
index might require the FE to maintain a separate table so that it can
translate each index to the prefix value that was meant by it.

Best regards,

John Renwick

---

From: "Joel M. Halpern" <[email-masked]>
Date: Thu, 12 Aug 2004 10:22:00 -0400

One could of course turn that around and observe that if the actual
implementation is not content addressed, supporting content based indexing
will require the FE to do a lot more work.

If there is a real need for the CE to understand the LFB in terms of a
content addressable table, then we should support such a
mechanism.  However, without a clear reason (and the LPM in and of itself
is not sufficient justification) I would prefer not to add top level
support for additional data types.  Yes, in PERL the slogan is "there are
many ways to do anything", but that is not a good slogan for protocol
design targeting interoperability.

[As a minor note, if we support content indexing, we are going to need to
support multi-parameter content indexing, since one for example may need an
IP address and a mask length.]

Yours,
Joel

---

From: John Renwick <[email-masked]>
Date: Thu, 12 Aug 2004 09:54:08 -0500

For what it's worth, the NPF Service APIs for this are content-addressed.
See http://www.npforum.org/techinfo/IPv4-Rev2_IA.pdf and
http://www.npforum.org/techinfo/IPv6-Rev2_IA.pdf.
The IPv4 Prefix FAPI draft is also, but it hasn't been published yet.

Frankly, we (NPF) never discussed using indexes for LPM tables.
(We were probably most influenced by the BSD routing socket model.)
As a table structure, LPM might be different enough to warrant making
it a special case.

Best Regards,

John

> [mailto:[email-masked]]On Behalf Of Joel M. Halpern
> Sent: Thursday, August 12, 2004 9:22 AM
> To: [email-masked]
> Subject: Re: [Forces-protocol] RE: Protocol/model discussion?
>
>

---

From: Zsolt Haraszti <[email-masked]>
Date: Thu, 12 Aug 2004 11:00:41 -0400

> IP address and a mask length.]

As you can see in my "Table Model" write-up, I intentionally
restricted the key to be a top-level field of the struct
(if the table is an array of structs), or the full entry (if the
table is an array of atomic types).  The field used for
addressing can of course be a struct by itself (in case
of prefix it has two sub-fields, the address and the prefix
length info).

I just wanted to avoid the headache associated with arbitrary
multi-field keys.

/zsolt

--
Zsolt Haraszti                Phone:  +1 919-765-0027/2017
Modular Networks              Mobile:      +1 919-522-2337
                              Email:  [email-masked]

---

From: Steven Blake <[email-masked]>
Date: Thu, 12 Aug 2004 11:03:18 -0400

Joel,

I completely agree with you in principal.  But in the specific case of
LPM, I agree with John: an LPM "table" is by its nature content
addressable.  To generalize: there are some tables in LFBs whose entries
are indexed by packet metadata, and there are others that are accessed
by packet header fields.  In the latter case, the notion of indexing is
strictly useful for table management, in the former it is necessary for
basic datapath functioning.

It won't be a disaster if, by limiting LFB table addressing in this case
to index-only, we force the CE to directly mirror the FE table contents.
We need to coordinate the table ids between FEs anyway if we are going
to have any hope of exploiting multicast for this case, so its not
likely necessary to keep multiple identical copies of the same prefix
table shared between FEs in the CE.

// Steve

---

From: Alistair Munro <[email-masked]>
Date: Thu, 12 Aug 2004 17:24:33 +0100

Hi All,

Sorry, I think I am entering into this discussion half-way through, hence
the change of topic.

I am against putting a content addressable abstraction into the model. I
think Joel said he was against it too? Using a CAM seems to be an
implementation choice that benefits the FE (obviously) but I am not sure
about trying to turn this to the CE's advantage (if that is what is
proposed) - doesn't the CE have to keep all the prefixes anyway to be able
to decide what it puts into the LPM "tables"? If we have proper
transactional semantics on the execution of a request to add an entry, then
the CE should know what information is in there or not.

Sorry if I've missed something. We've had the discussion about queries
several times in the past and I thought we'd sorted tis issue out.

Regards,

Alistair

Regards,

Alistair

--
Alistair Munro,
Principal Engineer, U4EA Technologies Ltd.
City Point, Temple Gate, Bristol, BS1 6PL, U.K.
E-mail: [email-masked]
Tel: (work) +44-117-373-6765, (home) +44-1275-462707, (mobile)
+44-7974-922-442;
Fax: +44-117-373-6751
Web: http://www.u4eagroup.com

---

From: "Wang,Weiming" <[email-masked]>
Date: Thu, 19 Aug 2004 14:56:30 +0800

Hi Steve and Joel,

----- Original Message -----
From: "Steven Blake" <[email-masked]>
To: <[email-masked]>
Sent: Thursday, August 12, 2004 11:03 PM
Subject: Re: [Forces-protocol] RE: Protocol/model discussion?

> > will require the FE to do a lot more work.
[Weiming]I'v seen some accordance and also seen the key difference with the
different views. I don't think there are guys who against using an index
identifier to address an LFB attribute which has table structure. The key
difference is at what level the ForCES protocol should be in charge of, i.e,
which addressing id should be explicitly expressed in the protocol. One view
(which I agreed) is to have the protocol only address the "attribute type"
level, leaving further addressing as value matching. The other view is for the
protocol to explicitly define an table entry id for addressing. I see the
accordance is the two ideas are actually the same in implementation. I have to
say addressing based on tabel entry id is still "content based indexing" as
mentioned above. I don't think there are implementation complexity difference
with them. One the contrary, I just a little worry if to define such table index
id in the protocol layer may more or less complex the protocol. Moreover, as
Steve mentioned below, it seems other value based addressing than tabel entry id
seems unavoidable, to explicitly and uniquely define table entry id as the only
addressing key in the protocol layer may quite limit the addressing ability for
ForCES system.

Thank you.
Weiming

---

From: "Joel M. Halpern" <[email-masked]>
Date: Thu, 19 Aug 2004 10:59:13 -0400

One of the things that concerns me is that even for tables which might be
"content addressable", we will still need to also have index access.
The reason I see for this is that the CE needs to be able to extract the
current set of values in the table.  There are three choices for this.  We
could require that the CE fetch the whole table in one operation (which
could be quite large, and seems to me to be undesirable.)  We could add an
iterator operation so that one could fetch successive elements of the table
without indexing (ugly, painful, prone to interesting timing problems, and
complex.)  Or we could allow indexed access so that the CE can go through
the table as it chooses.

Given that we must be able to set and get by index, clearly everything
necessary can be done without content based addressing.
Clearly, for some tables in some LFBs content addressing is a useful
abstraction.  But is it worth the complication?

Yours,
Joel