Subject: Re: [issue6] Summary of Path

From: Weiming Wang <[email-masked]>
Date: Sun, 21 Nov 2004 13:51:55 +0800

Jamal,

Pls allow me to transfer the discussion to forces list according to the demand
from David.

----- Original Message -----
From: "Jamal Hadi Salim" <[email-masked]>

> Weiming,
>
> On Thu, 2004-11-18 at 07:10, Wang,Weiming wrote:
> > Jamal and Joel,
> >
> > In reply to Joel, I should say the compromise may not be necessary, for it
seems
> > we all tend to think indices and IDs will be interleaved under the condition
> > that we should use indices. Pls allow me to try to propose a path scheme(I
hope
> > not too messy) as below:
> >
> >         PathTLV:= Index|FieldID <Index|RangeMark|FieldID>+
> >
> > Then,
> > 1) path = FieldID1 Index1 Field2 --- for single index case
>
> I dont follow: Why do you need all that to say get a simple top level
> attribute?
[Weiming]sorry, I don't follow well your remarks here. This is a case for index,
though not the simplist one. A more general one may be :
    path = FieldID Index
To get a top level attribute, the simplest path is: path = FieldID . Note that
the first element in the path is always a FieldID which represent the
AttributeID.

> > 2) path = FieldID1 Index1 Index2 Index3 Field2 --- for listed indices case
> > 3) path = FieldID1 Index1 RangeMark Index2 Field2 --- for block index1 to
index2
> > case
> > 4) path = FieldId1 Index1 Index2 RangeMark Index3 Field2 --- for list and
> > combined block indices cases
> > Where the length is controlled by the TLV length.
> > Based on this path TLV, and with Jamal's scheme in mind, I see the OpTLV
format
> > as below:
> >
> >         OpTLV:= MainPathTLV [SubPathTLV VALUE]+ [DataTLV]
> >
> > MainPathTLV and SubPathTLV all have uniform formats as a PathTLV.
> >
> > Points a little different from Jamal's are:
> > 1. IDcount removed, instead using PathTLV's length to control
>
> I have to think about it - it should probably be able to remove it. What
> happened to the flags?
[Weiming]When we include the block description inside the path and use TLV for
subpaths(key), I haven't seen any need for flags till now.
>
> > 2. Key is replaced by Subpath, which allows more general multiple level IDs.
>
> I am not sure i followed this.
> Can you reproduce the use cases i showed?
[Weiming]Ok, let me use following example

foo3, type structure, ID=5
{
    s1, type u32, ID=1
    s2, type structure, ID=2
    {
        g1, type u32, ID=1
        g2, type u32, ID=2
    }
 }

The operation is: Modify s1 to 100 and g1 to 200.
Then, the OpTLV structure is:
    OpTLV= MainPathTLV SubPathTLV1 Value1 SubPathTLV2 Value2

    MainPath = 5
    SubPath1 = 1(s1)
    Value1 = 100
    SubPath2 = 2.1 (s2.g1)
    Value2 = 200
What I mean is, the Key in your proposal seems only with one ID, which will make
it difficult to express things like s2.g1 above. As a result, if you can expand
the Key to multiple IDs, we may say the same thing.

>
> > 3. block operation is included in the PathTLV, where indices appear.
>
> Same comment as above
[Weiming]Reviewing your proposal on block operation, I think you are proposing
two ways, one is using Key and the other is using Block TLV. What I proposed
above with multiple indices included in the whole path actually only meet your
Block TLV. I can reshow your example which as:

table2: type array, ID = 4
 elements are:
 j1, type u32, ID = 1
 j2, type u32, ID = 2

Then, to get entry 0-2 of table2, the MainPathTLV is:
    MainPath = 4.0.RangeMark.2

One more thing is, I'm just considering there might be some cases(though rare)
there are more than one level of indices, something like:
FieldID1.Index1.FieldID2.Index2 . In this case, one specific BlockTLV maybe not
enough to express the two Indices.

Regarding the operations like you proposed in the example 4) as:
4) Block operations
To set entry 0-2 of table2
path = 4,
DATA_TLV, Length = 4+3*(4+8)
Values:
 0, j1value,j2value
 1, j1value,j2value
 2, j1value,j2value

I think this is actually Key(your name)/Subpath(my name) based, which should
better be expressed as:
OpTLV = MainPath(4) SubPath(0) Value1 SupPath(1) Value2 SubPath(2) Value3

>
> > 4. Data part should be a TLV, or else there will be a parse problem.
> >
> It is a TLV as proposed earlier.
[Weiming]I also suppose the Value associated with Key/SubPath is a TLV.
>
> Start with the use cases i used and show how you achieve the connection
> if possible.
[Weiming]Ok, I'll try to introduce a txt file for all the examples.
>
> you can ignore the key based example or include it if it will help to
> see the value easier.
>
> cheers,
> jamal
>

Cheers,
Weiming

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sun, 21 Nov 2004 01:31:21 -0500

I am not sure I see the value in separating the path and subpath.
Why not just use two occurrences of OpTLV, each with path and value.  That is
T = Set, L = Whatever
    PathTLV content = 5.1
    ValueTLV content = 100
T = Set, l = whatever
    PathTLV content = 5.2.1
    ValueTLV content = 200

Yes, this costs a few more bytes.  But it makes the parsing and context
really clean.
And when there is indexing, one gets
T = operation, L = whatever
    PathTLV, content = field IDs
    one or more Index TLVs, to apply to the path
    ValueTLV

We could get more complex if desired, folding the index TLVs into the path
TLV (with the path TLV having a leading portion that was an ID count) but
that seems to be more trouble than it is worth.

Yours,
Joel

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sun, 21 Nov 2004 09:50:57 -0500

> subpaths(key), I haven't seen any need for flags till now.

Flags are still needed. Ex: how do you say F_EXCL otherwise?
There is only one set of flags needed per message is my view (as opposed
to one per path).

> the Key to multiple IDs, we may say the same thing.

I did in the last email.

I think the main difference we have is:
a) What the paths and subpaths mean.
I described two subpaths: a content/key based one and a block based one.
I cant think of any other ones needed.

I think semantically, it is cleaner to split them as above (because you
can extend the BNF easily in the future).

This is our MAIN difference. My opinion is even if you can come up with
a generic case that covers all use cases, we should avoid it.

b) the paths + subpaths in my description are just "helpers" to get to
the main piece of data. You seem to be using them to condense as much
data as you can. As an example: I would have split the above example
into two sets and not one as you have shown.

IMO, where the _only need_  of subpaths is for constructs that describe
the data that is being looked for beyond a simple path value, example:
content based: "table 1 for all rows with foo1 = 10"; in such a case,
you need a mainpath to table1 and a content description of "foo1=10" to
be used as a subpath (but that subpath will contain both a path and
data).

Somehow in the grammar you need to say the subpath is only a further
description (even if it contains data, that datum is for further
description). The best way to achive this is to have the clearly
distinct types as i have shown (with BLOCK_* and KEY_INFO).

>     MainPath = 4.0.RangeMark.2

What is rangemark?

> enough to express the two Indices.

Then we need to have paths also within block descriptions.

> OpTLV = MainPath(4) SubPath(0) Value1 SupPath(1) Value2 SubPath(2) Value3

Assuming Valuex = { j1value,j2value}, then we are saying the same thing.
The difference is what i described above.

> [Weiming]I also suppose the Value associated with Key/SubPath is a TLV.

I think this is where we may need to weigh the efficiency factor:
If you are dumping 100K table entries (not unusual), is this really
worth it?

> [Weiming]Ok, I'll try to introduce a txt file for all the examples.

Please also include all the examples i included in my text. This way i
can update my text as well.

cheers,
jamal

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sun, 21 Nov 2004 09:54:12 -0500

> Yes, this costs a few more bytes.  But it makes the parsing and context

So far what you describe above is what we have agreed on for simplicty
sake.

> that seems to be more trouble than it is worth.

You seem to be avoiding to mix fieldIDs and indices - whats your
reasoning?

cheers,
jamal

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sun, 21 Nov 2004 10:23:38 -0500

My reasoning on separating the indices from the fieldIDs is based on the
assumption that folks still want content addressing.  If we have content
addressing (or blocks / ranges) then each index is a complex piece of
information.  Pulling that structure out of the path keeps the fieldID
sequence simple and easy to parse.  Given that each index has to have an
index-kind (which field are you indexing by) and an encoded value (possibly
variable length even), the index references end up looking like at least a
length-value pair.   And if indexes may be range as well, we have a full TLV.

Yours,
Joel

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sun, 21 Nov 2004 12:14:33 -0500

On Sun, 2004-11-21 at 10:23, Joel M. Halpern wrote:
> assumption that folks still want content addressing.

Indeed a requirement that must be addressed.

> If we have content

All content based addressing is resolvable via fieldIDs+data combo and
the block extensions via indice collections. And of course you could
have complex setups with a mix of both.
An additional requirement is to be able to operate on whole or large
chunks of tables efficiently.
I am worried about beautifaction getting prioritized over efficiency.
Whats the difference between what you suggest and what Weiming is saying
then?

cheers,
jamal

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sun, 21 Nov 2004 15:49:14 -0500

If I have understood Weiming properly, then I can paraphrase the splits a bit.
In his proposal, there is a base path, and then a sub-path.  The subpath
can contain feidl IDs and subscript values.  Multiple sub-paths can occur
with the same base path.  Data elements are associated with their most
immediately preceding subpath.

I am proposing a split where there is a single path element with all the
relevant field IDs, in order.  For places in the path where selection is
being performed, there would be an indication of which field (subscript or
content) is being used.  This is followed by the correct number of
selection values (subscripts, field values, or ranges).  This is then
followed by any necessary data value for the actual target.  (One could
look at this as a sequence of data values, but the selection values have a
very different semantic from the value to be set or the result being returned.)

 From an analytic perspective, I would actually like to include the
selection values in the path information.  However, when I try to construct
the information it gets more complex than the consistency value justifies.

Yours,
Joel

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sun, 21 Nov 2004 17:06:37 -0500

Joel,

The more i look at this the more i am uncertain of whom amongst the two
of you is closer to what i was saying. This is actually a good thing ;->
It means from  black box we are approaching the same thing. i.e

PATH-DATA := Main-path [subpath*] [data]

1) Theres a main basic path which may constitute a few initial field Ids
and maybe even a subscript or two which may take you say to a table.
You seem to say even this should be broken into field IDs + subscript.

2) Theres a further optional one or more subpaths

a) which in my opinion and yours is a further filter refinement of whats
needed (you call these path selectors) - but not according to Weiming
(where it is used to condense more data), unless i misunderstood.
Filter/subpath describes further what within the path is being
referenced. There could be zero or more such constructs.

b) You and I both seem to require they explicitly be identified as you
say as "subscripts, field values, or ranges" - Weiming wants them as
generic.
c) Where Weiming and myself agree seems to be the encapsulation of
further data in  said filter (eg foo1=10) - we deviate from you
slightly.

3) Theres data in which case all 3 agree.

So we need to make progress on #2. #1 is resolvable.

cheers,
jamal

---

From: "Wang,Weiming" <[email-masked]>
Date: Mon, 22 Nov 2004 10:58:04 +0800

Joel,

I don't think single path can meet all requirements for operations. Let me take
another example that is originally from Jamal's:

 j3, type u32, ID=3

Then, the operation is : delete(or get ) all entries with j1=100, and j2=200
(note j3 is not cared).
Obviously, using single path as:
T=Del, L=Whatever
    PathTLV content =4.1
    ValueTLV content=100
T=Del, L=Whatever
    PathTLV content =4.2
    ValueTLV content=200
This actually menas to delete all entries with j1=100 (j2 and j3 not cared), and
then delete all entries with j2=200 (j1,j3 not cared).

Instead, by using  subpaths as below, it can be correctly expressed:
T=Del, L=Whatever
    MainPathTLV content =4
    SubPathTLV content = 1
    ValueTLV content=100
     SubPathTLV content =2
    ValueTLV content=200

As a result, subpaths are necessary. And moreover, if we need to express things
like j1=100 or j2=200 (OR operation) logical operators may also needed, but as a
default one, we can take all sequentially listed operations as AND operations.

Cheers,
Weiming

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

---

From: "Wang,Weiming" <[email-masked]>
Date: Mon, 22 Nov 2004 11:53:12 +0800

Jamal,

You'v made a good summary on our approaches.
We do need faster pace for the protocol work, therefore, with some compromises,
I suppose the following format:

    PATH-DATA := MainPath [IndexTLV] [SubPath-Value]+ [Data]

Where,
    MainPath and SubPath only include FieldIDs. All Indices are treated by the
IndexTLV that also include BLock operations.

I think this format is close to Jamal's and also that I can live with, where
SubPaths are included. The reason for my compromise to separate fieldIDs from
Index is, I finally tend to Joel that the combined field and index makes the
structure very complex, though one limit to such separation is, I think, it
limits the index operations to only one level, i.e., paths like
fieldID1.Index1.fieldID2.Index2 will not be supported then. I can live with
this, because after some consideration, I think this multiple level of index
case is really very rare.

Regarding my another thought on the scope of usage of Subpath, I can also
compromise to limit the subpath mainly for content addressing, that is, not for
the data encoding and so as to allow the encoding of Data with chained pure data
rather than with ID and Data, but I will keep an eye on its practicability along
with our protocol and model progress.

Any thoughts?

Cheers,
Weiming

----- Original Message -----
From: "Jamal Hadi Salim" <[email-masked]>

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sun, 21 Nov 2004 23:04:45 -0500

Weiming,

I think we are approaching the Hz frequency of a good hum.
Lets hear what Joel has to say then maybe you can rewrite the text i
sent to close on this? i.e show all the use cases and more important
introduce new ones.
Are there several types of index tlvs or one generic one?

cheers,
jamal

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sun, 21 Nov 2004 23:11:28 -0500

Actually, I would simplify this somewhat.

Keying must be explicitly declared in the LFB (are structure)
declaration.  And key fields must be unique.
Therefore, if we want j1 and j2 to be used togther as a key, we will need a
struct (called j-key, for example) which contains j1 and j2.  Then the
declaration is

table2: type array, variable, id=4
    structure array-content
      jk, id=1, type = j-key, content_key
      j3, id = 2, type = u32
    end structure
type structure j-key
     j1, id = 1, type = u32
     j2, id=2, type = u32
endtype

And when doing a content reference one specifies that the content key is
jk, and the value for the key is 100,200.
This does not allow the CE to pick any arbitrary field for keying.  That
way, the FE is not required to be able to support arbitrary searches.  It
is only required to support searching by keys which are defined to be
unique.  In fact, it is required to enforce the uniqueness.

Yours,
Joel

---

From: "Wang,Weiming" <[email-masked]>
Date: Mon, 22 Nov 2004 12:13:35 +0800

Jamal,

----- Original Message -----
> sent to close on this? i.e show all the use cases and more important
Ok, I'l try to make it in a few days after Joel's response.

> Are there several types of index tlvs or one generic one?
The little difference from your blockTLV is, even with one index element, we
should use it. I can live with list, range, count TLVs, but more I consider is
they may be mixed to supply more power.

Cheers,
Weiming
> > > > If I have understood Weiming properly, then I can paraphrase the splits
a
> > bit.

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sun, 21 Nov 2004 23:20:09 -0500

I am confused.
Content addressing is a form of indexing.  I would put the values needed
for content addressing in the Index TLV.
This leaves me confused about what goes in the SubPath.  I think we do not
need the subpath.

Elaborating on my previous example:
table2: type array, variable, id=4
    structure array-content
      jk, id=1, type = j-key, content_key
      j3, id = 2, type = u32
    end structure
type structure j-key
     j1, id = 1, type = u32
     j2, id=2, type = u32
endtype

To set the j3 field, using the j1/j2 pair as a content key, one would send
4.1.3 as the path indicating that one wants to get, from table 2 (field ID
4), via the jk key (field id 1), the j3 field (field id 3).
The key TLV would contain the data representation for a j-key structure.  I
hope that will turn out to be 2 32 bit integers, but it is whatever data
encoding we decide on.
If one is doing a set, then the request will include a data tlv for the
value j3 is to be set to.  Similarly, a get response will include a value
tlv with the j3 value.

Note that all field identifiers occur in the path.
(There is a separate debate as to whether the data encoding should include
redundant type and field identifiers.  That is separate from this question.)

Yours,
Joel

At 11:04 PM 11/21/2004, Jamal Hadi Salim wrote:
> > > > If I have understood Weiming properly, then I can paraphrase the
> splits a
> > bit.

---

From: "Wang,Weiming" <[email-masked]>
Date: Mon, 22 Nov 2004 12:45:01 +0800

Joel,

I have to say what you proposed for a specific key for content searching really
makes things complex rather simple. Some questions with your j-key as:

1. What then if I only need to delete entries with j1=100? (note that I don't
care what j2 is)
2. Then  you mean we can not do operations like delete entries with j3=300 ?

Cheers,
Weiming

---

From: "Wang,Weiming" <[email-masked]>
Date: Mon, 22 Nov 2004 13:02:55 +0800

Joel,

One more thing is, it's even impossible to use a specific structure for a search
key. Consider a table attribute originally with strucutre as:

table2: type array, ID = 4
elements are:
  j1, type u32, ID = 1
  j2, type structure, ID = 2
        {
            k1, type u32, ID=1
            k2, type u32, ID=2
        }
  j3, type u32, ID=3

Now we consider to allow  j1 and j2.k1 as searching keys, how then to define the
specific key structure?

I confess that we may have a  field property to indicate if the field can be
allowed as key or not, just like to indicate if the field is read only or not.

Cheers,
Weiming

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 22 Nov 2004 00:08:11 -0500

The simple answer is, as defined, you can't.

The basic concept is that all keys must be declared, and all keys must be
unique.
The FE is not a database engine.  It's primary job is maintaining LFBs, not
searching tables.  In order to keep the table search complexity bounded, we
need to be very explicit about keys.

The FE needs to know whether j1 is unique by itself as a key, or the
combination of j1 and j2 is the key.  If the combination is what the LFB
designer declares as a key, then the CE can not use just j1 as a key.

If the LFB designer wants to allow j3 to be used as a key, then the LFB
declaration or type declaration also declares j3 to be a key, and the
values of j3 must be unique in ay given table.

To put it differently, content addressing is an optimization we are
allowing by which the LFB designer can indicate that certain things have
the necessary properties to be used as keys, and that the LFB designer is
accepting the tradeoff that some FE implementations may have to do more
work (and some may have to do little or no work) to support such keying.

The rough consensus of the working group was to allow limitted, declared,
unique, content addressing.  So we are trying to do so.

Yours,
Joel

---

From: "Wang,Weiming" <[email-masked]>
Date: Mon, 22 Nov 2004 13:34:58 +0800

Joel,

> designer declares as a key, then the CE can not use just j1 as a key.
I agree that the searching engine for FE may not be very powerful, but I think
your structure of key has unnecessarily limited the very limited searching even
more.
Let's think the LFB be a classifier, the table is a rule base, and j1 is a
matching tuple of source IP address and the j2 is another mathcing tuple of
DestinationIP address. By allowing the two tuples be keys for searching,
according to your propose, we then don't allow j1 with source IP address as
searching key anymore?

Cheers,
Weiming

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 22 Nov 2004 06:55:49 -0500

It is true that the definition I gave is limitting.  It represented a
compromise.
Allowing the CE to pick which things are keys, and not requiring keys to be
unique, adds a lot of implementation complexity.

My personal opinion is that we do not need content keys in the protocol (as
distinct from content matching in the data plane, which is what a
classifier does, for example.)

We can make this arbitrarily complex.  But it does not buy us a lot.

Yours,
Joel

---

From: Jamal Hadi Salim <[email-masked]>
Date: Mon, 22 Nov 2004 08:00:26 -0500

Joel,

Adding a "key declaration" in an LFB definition doesnt make it less
complex. Just look at the j-key you introduced - you ended changing the
initial structuring to accomodate it.

It is true that at the moment known LFBs have quiet well known keys and
probably in the range of 1-2 with an AND relation
(ex: prefix = X AND mask = Y); however, do we really want to restrict
things to "well known" at definition time? Why should i go back and
redefine the xml just so i can say "prefix = X AND mask = Y AND NHid=Z"
sometime down the road?
I actually dont see how restricting the keys to definition time makes
the grammar any simpler. If you can show this i would be more
indifferent.

cheers,
jamal