Subject: Re: Apology & Clarification on indexing

From: Jamal Hadi Salim <[email-masked]>
Date: Wed, 8 Dec 2004 22:43:28 -0500

Joel/Weiming,

Can we close on this? I think we were close and the break was good.

Thoughts?

cheers,
jamal

On Tue, 2004-11-23 at 22:22, Jamal Hadi Salim wrote:
> 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
>
> On Tue, 2004-11-23 at 11:44, Joel M. Halpern wrote:
> > 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
> >
> > At 10:41 AM 11/23/2004, Weiming Wang wrote:
> > >Joel,
> > >
> > >----- Original Message -----
> > >From: "Joel M. Halpern" <[email-masked]>
> > >
> > > > 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
> > >
> > > >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?