Subject: Apology & Clarification on indexing

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 22 Nov 2004 09:20:25 -0500

Before the chairs feel a needx to censure me, allow me to correct myself
and apologize.
Weiming, the restriction to a single field is not yet agreed by the working
group.  Thinking about it I realized that it was something I had read into
the agreement.  Sorry.

Now, to clarify the implications, assume an LFB library with structure
definitions (simplified) of:

tst: structure
    t1: uint32, id = 1
    t2: uint32, id = 2
   end structure

sst: structure
    s1: uint32, id = 1
    s2: type=tst, id = 2
    s3: uint32, id = 3
   end structure

and assume that in the LFB class definition of interest we have a field
definition:

farr: array, variable, id = 1
     type = sst
     key = s1
   end array

this allows farr to be subscripted, or to be indexed by the value of the s1
field.
A declaration of key = s2 would allow farr to be indexed by a complex value
representing the value of the s2 field.

We could extend this to allow the declaration of synthetic fields for
indexing.  In order to assign ids to these keys (for clarity of reference),
I will introduce the notion of kid, to represent the field id that occurs
in the path after the array to indicate which key is used (kid 0 for the
subscript).  We could then allow
     key = s1, s3, kid = 4
or
     key = s2.t1, kid = 5

However, even if we do this, there is not point in allowing both
    key = s1, kid = 3
    key = s1, s3, kid = 4
since a key must be unique in the array.  If s1 is unique, there is never a
point in also including s3 in the indexing expression.

I would personally prefer not to create this additional complexity of
synthetic key fields, but it can be supported if the group wants to.  My
feeling is that fields which together form a unique value to bve used for
indexing ought to be in a declared structure together.  If folks feel this
is too limiting, then I'll live with that.

Yours,
Joel

---

From: Jamal Hadi Salim <[email-masked]>
Date: Mon, 22 Nov 2004 09:51:17 -0500

Joel,

my concern:
how do i add new keys/kids or how do i extend existing ones
post definition time? the example i gave is if LFB definition said we
are going to have the prefix/mask pair as the key and then later (a year
down the road) i want to extend it to be prefix/mask/NHid - do i need to
go back and redefine the XML?

cheers,
jamal

On Mon, 2004-11-22 at 09:20, Joel M. Halpern wrote:
[..]

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 22 Nov 2004 10:24:27 -0500

Adding a new key will require going back and extending the XML.

If we want the ability to change the set of fields which are unique for
indexing, then we will need the key declaration with multiple fields.
However, I believe that this will break backwards compatibility.
That is, we have said that if we want to evolve a class foo, we can only
evolve it in ways that will allow the CE to keep operating even if the CE
has the old definition and the FE has the new definition.  (The other way
around is the CEs problem.)
In particular, this mean that for a given class, and its subclasses and new
versions, we must not cause a index expression to cease being unique during
evolution.

Thus, I think we end up ruling out extending an index by adding fields.
We could still have the case where the index was f1 & f2, and we want to
allow f1 & f3 (where f3 might even be new) as an alternative index.
This would need the multi-field key declaration and probably leads to the
keyIDs for path usage.
That is not fatal.

Yours,
Joel

PS: With regard to IP prefix and NextHop ID, I expect that one would have a
table indexed by the nextHop/prefixLength pair.  The structure inside the
table entries would likely include a table of nextHops.  This, indexing by
nextHop/prefLength/nextHopID is probably two subscripts, and
supportable.  But that is separate from the underlying question you wer
getting at.

---

From: Jamal Hadi Salim <[email-masked]>
Date: Mon, 22 Nov 2004 21:05:48 -0500

> Adding a new key will require going back and extending the XML.

Thats what i thought you were getting to.

> around is the CEs problem.)

There are ways to work around this, of course. One variant used by
netlink/Linux is to add new fields at the end (side that ignores them
sees only as much as the old size was). This scheme requires strict
ordering of fields. i.e if old scheme was f1,f2; then new scheme cant be
f1,f3,f2 (rather f1,f2,f3).

New sender, old receiver:
f1,f2,f3 --> receiver sees f1,f2 and ignores f3

old sender, new receiver
f1,f2  --> f2,f2 - receiver is backward compatible

> Thus, I think we end up ruling out extending an index by adding fields.

Refer to scheme i described above. I think the class versioning or maybe
the key versioning ought to be bumped up and discovery of
forward/backward compatibility should happen around capability discovery
should any change of the sort above happen.

> This would need the multi-field key declaration and probably leads to the

To sumarise: The main outstanding issue is you want to stick to some
simple scheme for keys predefined in the LFB template;
while both  Weiming and myself has thus far expressed one that is of
generic and part of the subpath construct. Both have merits.

I am gonna wait to hear what Weiming has to say.
My goal at this point is to make progress so we can get this out of the
way since it is the major show stopper for protocol completion.

> supportable.  But that is separate from the underlying question you wer

Yes this is the way i see the L3 tables arranged too. That was a bad
example. My goal was to show a scenario where a new key filed shows up.

cheers,
jamal

---

From: Weiming Wang <[email-masked]>
Date: Tue, 23 Nov 2004 23:41:51 +0800

Joel,

----- Original Message -----
From: "Joel M. Halpern" <[email-masked]>

> farr: array, variable, id = 1

From my limited viewpoint, I see this key definition is only trying to move the
work of the protocol to the model team. I suppose you were trying to say that
the farr array is composed of one element with the 'sst' structure type and you
hope to only alow the s1 in the sst structure as a searching key. As a result,
what from my viewpoint of  the first part of definition is something like:

    farr: array, variable, id=1
            f1: sst, id=1

Then the second part you wanted to express as key=s1 actually in my view is not
a 'thing' of element. It's actually something like to assign a subpath. What you
are going to do is to assign a key with a subpath. Then comes the question is
can this kind of key=subpath expression be allowed in the arry element field
definition? My answer is NO.  I suppose what you  meant actually means :

    farr: array, variable, id=1, key=subpath
            f1: sst, id=1

Then, if you have two allowed keys in the array, you will have to express it
like:

    farr: array, variable, id=1, key=subpath1,  key=subpath2, ( or
key=subpath1&subpath2, etc)
            f1: sst, id=1

(A minute note here,  the key=s1 subpath  you referred here actually in my view
should be a subpath of 'f1.s1' rather than 's1'. Just consider if the array has
two subfields as f1(sst type) and f2(still sst type), then your key =s1 means
nothing).

Note that, where the key is expressed as a property(attribute) of the array
rather than an element field.

Conclusion: your scheme of using a limited key in fact has just moved the
'subpath' issue from protocol layer to model XML layer. you are just trying to
use some specific elements in the XML to express the subpaths, therefore the
generic grammar for the protocol format as :

        PATH-DATA := MainPath [IndexTLV] [SubPath-Value]+ [Data]
still keeps the same.

Now let's compare the merits and demerits for the two scheme:

1. Obviously, the keys defined subpaths are a subset of the explicit subpath
expression. It limits the searching power. Maybe you may say that's what we want
for simplicity cause, but I don't see. My question is, does using such way to
limit the searching power  really saves network processor resourses?  I don't
see even a little. I just think they are the same in the resourse take, not to
mention that the  FE searching engine for CE does not need to work at line
speed.

2. On contrary, the pay for the key is with a much more comlex XML
expression(you have to define the idea of 'path' also in model), the reward is
mainly a limit to searching engine and maybe with a small save of bits in the
subpath expression.

3. Key by XML mode may also result in a version compatibility problem as Jamal
pointed out, and limit the extension ability.

Cheers,
Weiming

P.S. One more thing I have just thought of is, actually in some cases, the key
even does not save bit very much. Consider N field elements f1, f2,  and fN,
that we allowed as keys and we also allow any kind of logical searching for the
elements like  f1, f1&f2, f1&f3, ... f2, f2&f3,... f1&f2&f3, ...... we will then
have to define 2 to the power N of KEYs!!!   Along with the techniques step
forward, can we say 10 elements are definitely impossible?

---

From: "Joel M. Halpern" <[email-masked]>
Date: Tue, 23 Nov 2004 11:44:20 -0500

I don't care whether the key declaration is on the array line or on the
description of the content of the array.
In order to keep the syntax simple, if we are going to support keys that
are elements of structs insides structs, or keys which are collections of
elements, I was assigning a single value to that key in order to avoid
trying to carry collections of key path material.
This is easy to do if one assumes that keying must be declared with the
class definition, and indeed makes no sense if you assume that the CE can
use any keying which it knows to be suitable.

The argument for content indexing was based on what was natural for the FE
to support.  If that is the goal, then the CE needs to know (probably from
the schema) what sorts of content indexing make sense.  Thus, for this
problem, key declaration in the class definition makes sense.  I have
agreed to go along with including this capability in the protocol and model.

I can see no argument for supporting arbitrary searching by the CE.  The CE
is going to need to have a representation of the LFB information.  If the
CE wants to create interesting keys so it can find things in its own
tables, that is the CEs business.  It is not the job of the FE to provide
such capabilities.  Remember that the FE may be a simple control processor
manipulating FPGA (or even ASIC) tables.  It is not necessarily an NPU,
much less a general purpose processor.
I would argue that supporting general search capabilities is far afield
from what ForCES needs.

Yours,
Joel M. Halpern

---

From: Jamal Hadi Salim <[email-masked]>
Date: Tue, 23 Nov 2004 22:22:35 -0500

Folks,

Syntax aside on how to the key is represented. (Actually i agree with
Weiming that a key is definable as a sub-path, but thats a side issue).

I think the differences now boil to whether we want to restrict the
keys. Joel makes a compelling case why we do want that below.
It is also true that there will be well known content keys per LFB and
that these will be known at definition time.

The compromise:
It seems to me we need to define the key(s) in the xml. The defined key
is the minimal an LFB at the FE is expected to allow for content lookup
ex  the L3 lookup of prefix/mask/nhid.
If we dont do so we would need some discovery to figure out what the
mythical FPGA implementing an LFB does as a minimal. And this from a
first glance appears like it would add a _lot_ of complexity to the
protocol (as well as the model).

Having said that: for the "power" LFB i think we should allow more
powerful content expressions that are outside the scope of the model.
This should be done with minimal impact on the grammar representation
of the path-data. If it is impacting i think we will not grossly miss
this feature in the first incarnation of the protocol. We could always
revisit it after implementation experience.

Thoughts?

cheers,
jamal