Subject: Re: [issue6] Summary of Path

From: "Wang,Weiming" <[email-masked]>
Date: Tue, 4 Jan 2005 20:30:32 +0800

Hi,

Happy New Year!

Incidentally this may be the first post for 2005 :)

While I agree the path-data issue may become an important issue for further
protocol issue resolution, I just find that we may not in a very efficient way
to deal with it. Recalling the argument we'v had, I have a feeling that to
resolve this issue quickly we may need the model team to proceed one step ahead,
that is,  to define at least one LFB(e.g., a LPF IPv4 LFB) with all its
attributes presented, based on the model defined schema for LFBs. Let's think
that if we have such an LFB, I suppose it will be much easier for the protocol
team to proceed with its encoding as well as the path-data PDU for protocol.

Best regards,
Weiming

----- Original Message -----
From: "Khosravi, Hormuzd M" <[email-masked]>
Subject: Re: [issue6] Summary of Path

Jamal, Joel, Weiming,

Firstly, v. sorry about my late response on this issue.
I went thru this thread, but it wasn't clear to me what the final
summary was or which email I should respond to. I think this is a very
important issue so if one of you could summarize this and point out the
outstanding aspects, etc., it would make it easy for myself and others
to comment on this. Even if you could point me to one of your previous
emails that has this, it would be good.

Sorry for the trouble, but I would hate to respond with an inaccurate
idea about where this issue currently stands.

Thanks
Hormuzd

---

From: Jamal Hadi Salim <[email-masked]>
Date: Wed, 5 Jan 2005 11:16:28 -0500

> Incidentally this may be the first post for 2005 :)

And this is the third ;->

> to deal with it.

We need to make progress. If progress requires that we go with some
basic stuff initially, then thats the path we should take. It seems very
apparent that using basic indexing is very simple and no complaints
whatsoever about it. Block paths was the next simple thing. Keying and
interleaving with above is so far the outstanding issue. 
I believe were approaching closure before you got busy.
So if you have time now, please lets go back to where we left off.
Otherwise we need to put a time limit on this so we can move on. Chairs
please chip in here.

>  Recalling the argument we'v had, I have a feeling that to
> attributes presented, based on the model defined schema for LFBs.

Something like IPV4 LFB would be too complicated (because it needs
dependencies on other LFBs and in itself doesnt serve the purpose of
describing things we are stuck on). 
But you propose a good idea: Lets define an LFB that has all the needed
roadblocks to move forward. We already have the NOOP LFB for the basics.
I added basic events to it (attached - you need the LFB.xsd i mod'ed to
validate it). Joel, take a look at the events bits and tell me if we are
still synced.
NOOP is sufficient for a simple LFB definition. We should define a
second LFB, ComplexNOOP. This will have all the twists you can think of
(content reference, attribute sharing, multilevel tables). Interop
should mandate that these two LFBs are involved.
 
>  Let's think

Refer to comments above.

cheers,
jamal

---

From: "Wang,Weiming" <[email-masked]>
Date: Sat, 8 Jan 2005 12:45:08 +0800

Hi Jamal,

----- Original Message -----
From: "Jamal Hadi Salim" <[email-masked]>
Subject: Re: [issue6] Summary of Path
> Otherwise we need to put a time limit on this so we can move on. Chairs
[Weiming]I'm sorry I didn't reply too often laterly, but I think I'v clearly
expressed my views regarding things like the Key that Joel proposed.  To repeat
my views,
1. the Key is actually a kind of things to substitute a subpath with another ID,
like
        keyValue=f1.g1.h2, keyID=1
Therefore it's a kind of duplicating for IDs, if the subpath is something like a
purely a f1, then the key becomes
        keyValue=f1, keyID=1
Therefore, my thinking is it's really a duplicating work.
2. If we want to really limit the search field for an attribute, I think we can
just use things like a property of  'Search-allowed' or 'Search-denied', instead
of defining another key.
3. I even thought to use attribute property to limit the search is unnecessary,
it just leads to too much implementation oriented, which limits the progress.
Actually, the protocol can deal with it just by responses, i.e., doing
unsupported searching will lead to an error response by the protocol.

Another problem with the Key propose is, it's just a kind of initial thinking. I
think Joel or the model team should give more details on what it really looks
like. I don't think it's very efficient for the protocol team to discuss the
ideas that the model team itself is still not very clear. That's why I strongly
suppose a quite complete LFB definition be presented, with which ideas of things
like index, key, path can be clearly described. To speak of this, I have to say,
along with the more discussions, I just find that we (including Jamal, Joel, and
me) seem to have even differences on the basis of the definitions like paths,
index, and key also. For example, I think a path is a PDU that is defined by
protocol, while I see Jamal's NOOP LFB, it seems defined there, i.e., the
individual LFBs define individual Paths, and the Path itself is an LFB
attribute? This is far from I thought. I also have doubt on the index. My very
original thought was that we can use an attribute of 'index' for indexing,
therefore we don't have index in the protocol. Then, Joel proposed that the
index should be by protocol instead of the LFB attribute, so I tried to go in
this way. Along with the discussions we have,  I find it maybe not really so. It
seems sometimes you think it is a pure index used by protocol, sometime it is
defined by LFB. All this makes me believe that a relatively perfect LFB
attribute definition from model team is very helpful for our further discussion.
Of coarse, in the process to form such a LFB, we'l be very pleased to join to
discuss. Jamal  presented a good start with the NOOP LFB, I suppose.

Thank you.

Weiming

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sat, 8 Jan 2005 00:24:57 -0500

There are a couple of specific aspects that I think it may help to spell out.

1) Remember that the fileds may be defined in a data type that is 
imported.  That is, an array may be defined as having as content a 
structure of type "IP-information" which in turn has a field of type "IP 
address prefix".  It seems clear to me that the structure definition can 
not include the indiciation as to whether IP address prefix is a key in 
some array, since the structure is used in many places.
2) I believe that the FE implementation needs the information as to what 
keys are likely to be used by the CE>  The model is the only thing that can 
give this guidance.
3) While the FE can return errors, the CE is helped by knowing what kinds 
of indexing are likely to work.  While this can be done with capabilities, 
I have several concerns with that
3a) representing the legal keys as capabilities just gets messy
3b) I think that CE implementors will be helped by knowing what keying the 
FE will support.  Interoperability requires some common core set.  If FE 
implementors get to chose, multi-vendor CEs will just use that core 
set.  Hence, if we want this keying to be used and usable, we need to 
define what will be supported.  The model is the right place to do that.

Given that we are going to define keying in the model, there are several 
possible approaches.  Zsolt and I have batted a couple back and forth, but 
I doubt if we have found them all.  I actually don't like any of these ideas.
a) the key-id approach I suggested
b) have a key TLV consist of a sequence of path-fragment / value pairs, 
(similar to what I think Weiming is proposing) with a restriction that only 
those combinations which have been declared to be keys may be used.
c) restrict keying to path identifiable fields, and restrict it to being 
used only with full array element references at the end of the path.  Then 
use a flag associated with the path to indicate that content keying is 
being used, and the last part of the path references the key.

I think that the exact mechanism is less important than the questions of 
whether the keying must be pre-declared in the model, and whether key 
elements must be unique.
If we can agree on those two questions, we can sketch enough protocol to 
keep moving.

Yours,
Joel M. Halpern

---

From: Jamal Hadi Salim <[email-masked]>
Date: Sun, 9 Jan 2005 23:21:34 -0500

> There are a couple of specific aspects that I think it may help to spell out.
[..]
> If we can agree on those two questions, we can sketch enough protocol to 

The predeclared keys are a good hint to the CE, but without capabilities
(which i also have strong distate for in this case) the backup is to for
the FE to reject a requested content operation. In other words, I do
think that it is practical to say have a ASIC vendor implementing the
some LFB not supporting any content searches.
So given that, the only value to predeclaring is giving a good hint to
the CE. I think its still a good thing to have and we should add it.

Heres where i think the two biggest discrepancies so far are and that
need to be resolved:

1) interleaving of path-data-path-data ..
So far Joel and myself have been saying you have
path [pathfilter] [data]
This is for simplicty reasons (and that a path leads to data)

Weiming is asking for:
path pathfilter data pathfilter data ...

subpath is what is refered as a pathfilter above (content or block
refinement of the path).

When you look at what you end up dumping in say a table that has colums
pointing to another table; then you can see that we would end up doing
what Weiming is asking for.
The examples i presented around November infact showed this.

The problem with Weiming's approach is the overhead in the case of large
quantities of data (either dumping from FE or setting to the FE). You 
end up with a lot of nested TLVs. And thats not efficient packing of
data (consider 100K L3 table with each entry chewing an extra 8 bytes of
overhead and requiring two extra TLV levels)

Compromise: I think we should allow the path-data-path-data interleaving
but also allow a "cooked" mode bulk/batched operation for efficiency
purposes

2) for the keys:
i) Weiming asking for equality notation. Example foo1=10 all the way to 
"foo1<10", "foo1 is in the range of 1,10" etc
Joel unhappy with this...

My opinion for compromise: 
I think it will be easier to just enforce to "=" sign only. The block
notations should allow for lists and ranges
(I am not sure i see it for field IDs).

ii) Weiming asking for multiple keys with logical operators example:
"foo1=10" OR "foo2=200" AND "foo3=14" 

My opinion for compromise: I think we should allow for multiple keys but
restrict logical operation to AND only. Infact the AND is implicit in
the fact you have a series of key operations.

It should be noted that what Weiming is asking for is more flexible and
future proof; however, as Joel has pointed out numerous times we should
try a much as we can to leave the intelligence to the CE and not turn
the FE into a database engine. 
[As an example the CE should be able to resolve all entries that have
"foo1=10 OR foo2=100" and then make an exact request to the FE what
paths are being targeted].
To chip in my opinion: As we learn more from experience we could add
more features - but for now, lets cut down to just the basics.

If people are in agreement i can redo my earlier text with the above
suggested changes and bounce it on the list.

Weiming/Joel - lets hear from you.

cheers,
jamal

---

From: "Wang,Weiming" <[email-masked]>
Date: Mon, 10 Jan 2005 22:43:32 +0800

Hi Jamal, Joel as well,

----- Original Message -----
From: "Jamal Hadi Salim" <[email-masked]>
Subject: Re: [issue6] Summary of Path
> This is for simplicty reasons (and that a path leads to data)
This is an important item, you shouldn't have simplified it :). And I'm not sure
if Joel also thinks so.
> subpath is what is refered as a pathfilter above (content or block
If we can reach agreement on the path-data-path-data ...mode, I think it's also
a good progress,and also complies with my thougt partially. I just thought that
Joel might be insisting on the format as Op-path-data,Op-path-data,....

My further thought is, in the path-data-path-data mode, actually the paths have
lots field in duplicating. For instance, the same Attribute ID will always be
there in all paths. As a result, one of the reason for my suggest for a Mainpath
and Subpath is  for the efficiency.

> what Weiming is asking for.
I'm not very sure what you mean here. I just thought the two are the same in
basic functions, with the latter giving more bits saved.

> overhead and requiring two extra TLV levels)
I'm afraid the things are reversed a little :), or you are talking about other
thing than the subpath. I guess you are talking about how data are encoded, i.e,
to use a packed data (D1-D2-D3-...), or to use a format with
ID1-D1-ID2-D2-ID3-D3-.... Yes, I suggested this before, but I think it is
another issue from the subpath we are discussing. One remark for the latter data
format is, the ID there does not need to use TLV to present, a pure ID is
enough, I think.

Cheers,
Weiming

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 10 Jan 2005 09:49:33 -0500

I look at it the opposite way.
Thinking about the CE software design, the only time I would build a CE 
that used content addressing is when I know that the FE will support it.
There will always be a mandatory to support indexing method for every 
array.  (Otherwise, interoperability is gone.)
As such, optional, may work if you try it, methods are simply a waste of 
effort.

Personally, the longer this discussion goes on, the more I am inclined to 
conclude that the whole idea of content addressing is a bad idea.  It 
complicates the FE, complicates the CE, and complicates the protocol.

Yours,
Joel M. Halpern

---

From: Jamal Hadi Salim <[email-masked]>
Date: Mon, 10 Jan 2005 10:24:36 -0500

> This is an important item, you shouldn't have simplified it :). And I'm not sure

Sorry, I was assuming path-data-path-data is preceeded by op.
To be precise op-mainpath-subpath-data-subpath-data-subpath...

> Joel might be insisting on the format as Op-path-data,Op-path-data,....

Joels view(matching mine) is op-mainpath-subpath-data.

> and Subpath is  for the efficiency.

its op-mainpath-subpath-data-subpath-data-subpath. I think i should put
together the text so we can be sure we are talking about the same thing.

> basic functions, with the latter giving more bits saved.

It could be a misunderstanding of your scheme. Let me put together some
text and see if we are saying the same thing.

> thing than the subpath. 

If you dump table1 in the example i posted you could end up having data
that looks like:

table1subscriptx,t1value, t2value, j1value,j2value   

This is needed for efficiency reasons. Note t2value is infact
index/subscript for table2 but residing in table1. 

> I guess you are talking about how data are encoded, i.e,

I think that the dumped data should not look any different from data
that is sent to the FE to set for example - this is the puritism
approach. In such a case you would need to have separation of Data and
path into different TLVs - which is where conflict comes in i.e
cleanliness and efficiency conflict.

Heres a basic first attempt at BNF that would satisfy what you are
asking for:

OPER_TLV : = <PATH-DATA>
PATH-DATA := <PATH> [DATAINFO]
PATH := flags IDcount <IDs> 
DATAINFO:= [SUBPATH]  [DATARAW]
SUBPATH := <[KEYINFO]+ | [BLKINFO]| [INDINFO]> 
DATARAW := somedata [DATAINFO]

cheers,
jamal

---

From: Jamal Hadi Salim <[email-masked]>
Date: Mon, 10 Jan 2005 10:33:01 -0500

> array.  (Otherwise, interoperability is gone.)

Indexing doesnt require any forwarding path support - content searches
on an FE only make sense (IMO) when the forwarding path supports it.

> As such, optional, may work if you try it, methods are simply a waste of 

So lets pick the L3 LFB. It is possible CAM implementations of such an
LFB will allow search by prefix while others wont. When creating an L3
LFB however it makes sense to define the prefix as a search key.

> complicates the FE, complicates the CE, and complicates the protocol.

I agree - however, consensus seems to be leaning towards allowing
content keys at least. Minimal requirements met towards that goal is
fine. 

cheers,
jamla

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 10 Jan 2005 10:39:30 -0500

Yes, if we are going to have content addressing, something like what Jamal 
provided is what I was envisioning as well.
There are obviously many details to be filled in, but they depend in large 
part on some of the other issues we are discussing.

Yours,
Joel M. Halpern

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 10 Jan 2005 10:49:17 -0500

Using the L3 Next-Hop-Selection LFB as a case to consider, I see two 
reasonable choices.  Either we simply use indexing all the time, and do not 
make use of the ability for some implementations to easily address 
information by the IP address & prefix-length, or else we mandate that all 
implementations support such addressing, even those that do not have 
hardware support.

Yours,
Joel

---

From: Jamal Hadi Salim <[email-masked]>
Date: Mon, 10 Jan 2005 11:06:59 -0500

At the expense of getting shot: I think Indexing should be mandatory and
content keying optional. It is clear that the CE can convert from
content to indexing if armed with all the info on how tables are
populated in the FE. 
My only concern is some of the FEs that may only understand content
keying and run on some dumb FE (Steve had some convincing arguement in
this direction a while back).

cheers,
jamal

---

From: "Wang,Weiming" <[email-masked]>
Date: Tue, 11 Jan 2005 12:30:46 +0800

This has mostly complied with what I thought. I'm glad we reach this point.

To use key or not is another issue.

The only different point I thought is the feasibility to put all field IDs in
the mainpath for all possible cases, with subpath only deals with indexes.
Content searching is one case that needs to have fieldIDs in the subpath. Joel
tries to use key to avoid such case, but I think a key is still a kind of
fieldID. I can think of other cases where fieldIDs in subpaths are needed. The
following is one:

Thinking we have an LFB with following  attribute:

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
        g3, tyep u32, ID=3
    }
 }
also thinking we have already set the values for this attribute. Now, we need to
modify some value in it, say to modify the s1, g1, and g2. Note that I don't
want to modify the s2 and the g3(if I want to modify all the values, that
becomes another case, where I only need to use a simple path-data to represent
it).

With mainpath and subpath, I think the format should be like:
Mainpath(Foo3) subpath( s1) value subpath(s2.g1) value subpath(s2.g2) value

I actually talked about this before with Joel. I think Joel asked that in this
case, he would rather use three separate path-data to do so, that is,

path(Foo3.s1) value
path(Foo3.s2.g1) value
path(Foo3.s2.g2) value

If the above path-values are in one OpTLV, I can more or less live with it, but
still think the mainpath and subpath mode is better than this. I supposed Joel
asked the path-values be in different OpTLVs, which I'm hard to accept. I think
such operation is originally atomic, to separate them into different OpTLVs is
not reasonable enough.

Want to hear what others think about it.

cheers,
weiming

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 10 Jan 2005 23:58:21 -0500

There is some argument based on protocol efficiency for combining them.  I 
can live with that.

However, for clarity I wish to note that atomicity is not a reason for 
combining them.  The atomicity issue should be dealt with explicitly (as 
the protocol team as already indicated they will do).  It should not be a 
side-effect of grouping things into TLVs.

Yours,
Joel M. Halpern

---

From: Jamal Hadi Salim <[email-masked]>
Date: Tue, 11 Jan 2005 08:12:10 -0500

It should be noted that the grammar of attached document will have to be
modified to:
OPER_TLV : = <PATH-DATA>+
instead of:
OPER_TLV : = <PATH-DATA>

to meet what Weiming is looking for. Weiming if you can think of a way
to change that grammar to met that desire, please do so. Try to avoid
large impact on the BNF if you can (otherwise i have to change all the
use cases ;->)
The atomicity indicators at the moment reside on the main header flags.

Ok, folks - dont wanna sound like a lawyer, but here it is in scribe,
sign on, modify etc. 

cheers,
jamal

---

From: Robert Haas <[email-masked]>
Date: Tue, 11 Jan 2005 15:04:44 +0100

Weiming, all,

>Want to hear what others think about it.
I find the three separate path-data simpler and clearer. Such path-data 
can be aggregated under the same OpTLV, or they can be in separate 
OpTLVs. The protocol should support both cases.

>>>DATARAW := somedata [DATAINFO]
I'd like some description of  KEYINFO. Or better, an example of how this 
actually looks like for a content-based search key in a simple array. I 
am worried the devil is again in the details.

Regarding the need to support content-based search at all: Joel rightly 
expressed concern about too much sophistication. I also think most of 
the management operations should be handled at the CE, except in the 
case of obvious protocol-efficiency gains.

For instance, the CE is able to convert a content-based access into one 
(or more) index-based access(es), as the CE is supposed to keep track of 
what the FE stores. But block operations should not be split into a 
sequence of operations by the CE, even though the CE is very well able 
to do it too.

Index-based accesses are the lowest-common denominator, and 
content-based accesses are an option that each LFB may or may not 
support, with arbitrary or pre-specified keys (or even key 
combinations). Requiring SQL-engine-like capability in an FE would kill 
the spec, I think.

Note that even though the FE must have a (hopefully efficient) 
implementation to retrieve/set an entry from/into its data structs based 
on (ForCES) index, it does not mean at all that the FE uses an indexed 
array for the data struct used for datapath lookup. Probably this was 
obvious to everyone here.

Regards,
-Robert

---

From: Jamal Hadi Salim <[email-masked]>
Date: Tue, 11 Jan 2005 11:58:55 -0500

After proof reading, heres an updated version. If you have invested time
reading the original version then take a look at the diff also attached.

cheers,
jamal
--- data_path2.txt	2005/01/11 16:30:37	1.2
+++ data_path2.txt	2005/01/11 16:55:00
@@ -24,15 +24,15 @@
 A possible path-data layout. 
 ----------------------------
 
-OPER_TLV : = <PATH-DATA>
+OPER TLV : = <PATH-DATA>
 PATH-DATA := <PATH> [DATAINFO]
 PATH := flags IDcount <IDs> 
-DATAINFO:= [SELECTOR]  [DATARAW]
+DATAINFO TLV := [SELECTOR]  [DATARAW]
 SELECTOR :=  [BLKINFO] [KEYINFO]+ | [INDINFO]> 
 DATARAW := somedata [DATAINFO]
-INDINFO := index | fieldID
-KEYINFO := KEYID KEY_DATA
-BLKINFO := [BLK_RANGE_INDEX] | [BLK_LIST_INDEX] | [BLK_CNT_INDEX]
+INDINFO TLV := index | fieldID
+KEYINFO TLV := KEYID KEY_DATA
+BLKINFO TLV := [BLK_RANGE_INDEX] | [BLK_LIST_INDEX] | [BLK_CNT_INDEX]
 
 -> IDs := a series of 32bit IDs (whose count is given by IDcount)
 defining the main path. These IDs could be field IDs (staticaly defined
@@ -45,11 +45,24 @@
 The path information in the SELECTOR indicates what information is being 
 used for selection.
 -> DATAINFO: = Optional variable sized data dependent on PATH
-and applied operations.
+and applied operations. As an example a GET or DEL may not have data.
 -> DATARAW contains the data whose path is selected. This may
 recursively contain DATAINFO such that we can have a series
 of "path data subpath data subpath data ..."
 
+NOTE! NOTE!
+-----------
+The DATARAW "somedata" is LFB dependent.
+It is assumed that the recepient by virtue of knowing the LFB
+can decode the data.
+In the simple LFB used in this doc, the fields in the two tables
+are all of fixed size. It would need some TLV to explain variable
+sized entries such as strings. 
+TBD: Should we leave this upto the LFB specific to worry about 
+the encoding/decoding. If yes, how does the LFB definition describe
+this? If no, should we add this to the grammar? If yes, how?
+
+
 flags
 -----
 
@@ -88,7 +101,7 @@
 here for the moment.
 
 1) BLK_RANGE_INDEX TLV
-T = BLK_INDEX_RANGE, length of 4+8
+T = BLK_RANGE_INDEX, length of 4+8
     start // "a"
     end // "b" 
 
@@ -144,15 +157,20 @@
 that allow for this). It should also be noted that the majority of the
 popular LFBs such as the L3 LFB will have a single unique key (such
 as the IPV4 prefix).
+[Additional note: In the case the forwarding path actually does everything
+with index based tables, then doing a check of "j1=1 AND j2=10"
+is valid; however, j2 and j1 are not really "keys" if we use
+proper terminology ;->]
 Again, it should be emphasized that keying information is low level
 detail that can be "resolved" at the CE without enforcing it on the
 FE.
 
-RAWDATA:
--------
+DATAINFO:
+---------
 
-The RAWDATA TLV will contain the raw data and may
-optionaly contain a DATAINFO TLV.
+The DATAINFO TLV will contain the RAWDATA which may
+optionaly contain a DATAINFO TLV (to allow for recursive interleaving
+of path-data).
 
 USE CASES
 ---------
@@ -163,17 +181,16 @@
 
 foo2, type u32, ID = 2
 
-table2: type array, ID = 4
-	elements are: 
-	j1, type u32, ID = 1
-	j2, type u32, ID = 2
-	j3, type u32, ID = 5
-
 table1: type array, ID = 3
 	elements are:
 	t1, type u32, ID = 1
 	t2, type u32, ID = 2  // index into table 2
 
+table2: type array, ID = 4
+	elements are: 
+	j1, type u32, ID = 1
+	j2, type u32, ID = 2
+
 1) To get foo1
 Path: IDCount = 1, IDs = 1
 
@@ -185,16 +202,22 @@
 Path: IDCount = 1, IDs = 2
 RAWDATA TLV: L = 4+4, V=10
 
+Result:
+Depends on whether we asked for a simple
+success/ACK back or full details
+
 3) To dump table2 (get)
 
+Assuming numentries defines the number of entries.
+
 Path = IDCount = 1, IDs=4
 
 Result:
 Path = IDCount = 1, IDs=4
 BLK_INDEX_RANGE TLV
     start = 0
-    end = numentries2-1
-RAWDATA TLV: L = XXX, V=
+    end = numentries-1
+DATAINFO TLV: L = XXX, V=
     a series of j1value,j2value  entries (numentries2 in total)
 
 4) Block operations
@@ -202,21 +225,22 @@
 now)
 
 Path = IDCount = 1, IDs=4
-BLK_INDEX_RANGE TLV
+BLK_RANGE_INDEX TLV
     start = 0
     end = 2
-RAWDATA TLV: L = XXX, V=
+DATAINFO TLV: L = XXX, V=
     a series of j1value,j2value  entries (3 in total)
 
 5) Block operations (with holes)
 To set entry 0,2 of table2 (I am going to ignore error conditions for
 now)
 Path = IDCount = 1,  IDs=4
-BLK_LIST_RANGE TLV
+BLK_LIST_INDEX TLV
     0,2
-RAWDATA TLV, Length = XXX, V =
+DATAINFO TLV, Length = XXX, V =
     two j1value,j2value  entries 
 
+
 6) Getting rows
 To get first entry of table2
 Path = IDCount = 2,  IDs=4.0
@@ -226,7 +250,11 @@
 Result:
 Path = IDCount = 1, IDs=4
 INDINFO TLV, value = subscript/index of row 0
-RAWDATA TLV, V= j1value,j2value 
+DATAINFO TLV, V= j1value,j2value 
+
+Another valid response is:
+Path = IDCount = 2,  IDs=4.0
+DATAINFO TLV, V= j1value,j2value 
 
 7) to get entry 0-2 of table2 using BLK operations
 
@@ -243,7 +271,7 @@
 T = BLK_INDEX_RANGE, length of 4+8
     start = 0
     end = 2
-RAWDATA TLV, Length = XXXX
+DATAINFO TLV, Length = XXXX
 Values:
 	j1value,j2value
 	j1value,j2value
@@ -262,7 +290,7 @@
 T = BLK_CNT_INDEX, length of 4+8
     start = 0
     count = 3
-RAWDATA TLV, Length = 4+2*(4+8)
+DATAINFO TLV, Length = 4+2*(4+8)
 Values:
 	j1value,j2value
 	j1value,j2value
@@ -280,7 +308,7 @@
 Path = IDCount = 1, IDs=4
 T = BLK_CNT_INDEX, L = XXX
 		V: 0,1,2
-RAWDATA TLV, Length = XXXX
+DATAINFO TLV, Length = XXXX
 Values:
 	j1value,j2value
 	j1value,j2value
@@ -296,7 +324,7 @@
 T = BLK_LIST_INDEX, L = XXX
 Values: 3, 5, 15, ...
 
-RAWDATA TLV, Length = XXXX
+DATAINFO TLV, Length = XXXX
 Values:
 t1value, t2value, j1value,j2value   
 .
@@ -321,7 +349,7 @@
 Path = IDCount = 1, IDs=4
 T = BLK_LIST_INDEX, L = XXX
 	Values: 9, 16, 22
-RAWDATA TLV, Length = XXXX
+DATAINFO TLV, Length = XXXX
 Values:
 	j1value,j2value
 	j1value,j2value
@@ -342,19 +370,24 @@
 Path = IDCount = 1, IDs=4
 T = BLK_LIST_INDEX, L = XXX
 	Values: 16, 36,95
-RAWDATA TLV, Length = XXXX
+DATAINFO TLV, Length = XXXX
 Values:
 	j1value,j2value
 	j1value,j2value
 	j1value,j2value
 
+TBD:  What to do when we request the next 10 entries but theres
+only 5? What about when the highest index available is 5?
+Need to enumerate all possible error paths
+
 TODO:
-----
 
 - more refinement of flags for atomicity etc
 - column and cell access in a table use cases
 - Provide a more complex use case example (where a table cell points
-to a whole table)
+to a whole table). Essentially this is no different from the
+variable sized string problem pointed to in the BNF (while describing
+"somedata").
 
 $Log: data_path2.txt,v $
 Revision 1.2  2005/01/11 16:30:37  hadi

---

From: [email-masked]
Date: Thu, 13 Jan 2005 15:36:44 -0500

On 10 jan 2005, at 09.49, Joel M. Halpern wrote:

> Personally, the longer this discussion goes on, the more I am inclined 
> to conclude that the whole idea of content addressing is a bad idea.  
> It complicates the FE, complicates the CE, and complicates the 
> protocol.
>

I tend to agree with this.

a.

---

From: "Wang,Weiming" <[email-masked]>
Date: Sun, 16 Jan 2005 18:15:34 +0800

Hi Joel,

Along with the discussions, I have an impression that we may have some basic
difference on the designe criteria for the protocol. I suppose you may more tend
to make it  more like a  SNMP, that is, a simple, one by one operation based,
and looks beautiful in the PDU. While I may have quite different thought in mind
for it. I think, alghouth SNMP is a good prioneer worthy ForCES learning, there
are basic difference between them. SNMP is for management while ForCES is for
controlling. ForCES is somewhat a real-time system, which generically requires
more complexity to ensure its feasibility and efficiency, therefore, I don't
think it's very practical for ForCES to cut the complexity to acquire the
simplicity.  I agree with Jamal's thought that for ForCES beauty is the second
we only need to consider, the first we should consider is its feasibility.  As a
result, the criteria in my mind for the protocol is, to meet the requirements is
the first, to have an efficient PDU to save bits is the second, because I have
always worried about the link resources that link CE and FE, the third is the
simplicity.

Talking about this, I have to say again that the idea of 'index' is really
another thing that still bother me some. As you may also worry a little, the
management of 'index' (as well as the index holes), that will in the end be a
big extra burden for CE and FE. I'v been trying to find some router design
instances (including ASIC based design), but still haven't found one that uses
index to manage routing tables. I see the Cisco IOS, the linux Netfilter also do
not use any index for such management. I'm not sure if you could show some more
experiences on it. I also strongly ask other guys on the list  to show some
experiences with the use of index for routing table management. That will be
much helpful for our confidence.

Thank you.
Weiming

---

From: Weiming Wang <[email-masked]>
Date: Tue, 18 Jan 2005 23:23:26 +0800

Joel, Robert, and Jamal,

Firstly, Jamal, I appreciate your efforts, but just could you give me a little
bit more time for more discussions on the fundamentals, before we can perfectly
settle the PDU?

From Joel's original proposal on Index and Robert's comments as below, I think
the key goes to the state as "if an CE can maintain a copy of any tables in
FE?". I confess that CE can do this well for routing tables in FE, but I just
worry about some other tables that FE may actually change the contents of the
tables. I can think of these tables as some tables for capabilities, for
statistics, and even for some events. Obviously, CE will not be able to have a
copy in advance before querying them. This also leads to the difficulties for
the use the idea index for them.  Therefore, my compromise is,  even if we
choose INDEX, it should not be a MUST for all kinds of tables.

For content-based searching, I have to say again that, when we observe it from
the mechanical point of view, index is also a kind of content searching, that
is, the content is the index(note we will never expect a sequential index).
Therefore, I don't think it makes sense much to discuss if an FE need a content
searching mechanism or not, instead, we may just need to discuss in which dgree
FE should support such search.

When we have the thought that not all tables are always applicable with Index,
I'm afraid to include content-based searching expression in the protocol is
unavoidable, unless we assume and make a provisioning that it is only allowed to
access a whole table, instead of entries in the table.

Yours,
Weiming

---

From: "Joel M. Halpern" <[email-masked]>
Date: Tue, 18 Jan 2005 10:53:03 -0500

>I certainly agree that being forced to fetch (or worse update) entire 
>tables would be a very bad choice.

However, I have not yet seen a convincing case for either
1) a situation where indices are not supportable
2) a situation where arbitrary keying is needed.  Here arbitrary refers to 
either of non-unique keys or keys that are not declared by the LFB class 
definition.

I have seen some interesting arguments for limitted content keying to 
reflect cases where it is known a priori that it will be helpful to many FE 
implementations if the CE uses the content keys.

Note here that we are discussing the structure of information, not the 
content.  The fact that the FE will modify statistical information does not 
appear to be relevant.
And capability information MUST have a known access structure, so that the 
CE can traverse and utilize the information.  I prefer to make that 
structure a simple index.

Yes, you can declare the indexing is a form of content addressing.  It is a 
form of content addressing with unique, pre-declared keys.
Given that for interoperability, the CE must have a table access method 
that it supports that it knows all FEs will support, simple indexxing is a 
very good way to meet that constrain.  We could require that every table 
have a declared mandatory to support addressing mechanism.  Which means 
that as LFB definitions are created we introduce the potential to further 
complicate both FEs and CEs.  WIthout adding much advantage.

Note that even CAMs actually have an internal index, and that the index is 
actual usable, knowable, and sometimes necessary.  So I am unpersuaded that 
there is any case where the CE can not easily have enough information to 
use indices, or where it is a major difficulty for the FE to use 
indices.  As long as the content addressing was simple, I am willing to 
recognize the groups desire to have the mechanism even if I am not 
persuaded of the value.
However, arbitrary keying, selected by the CE at run time simply does not 
seem to me to meet this.  There is no reason to turn the FE into a search 
engine.  Much less one that can return multiple matches on arbitrary fields.

Yours,
Joel M. Halpern

> > >If the above path-values are in one OpTLV, I can more or less live 
> with it,
>but
> > >such operation is originally atomic, to separate them into different 
> OpTLVs
>is
> > >not reasonable enough.
> > >

---

From: Robert Haas <[email-masked]>
Date: Thu, 20 Jan 2005 15:09:54 +0100

Weiming,

>choose INDEX, it should not be a MUST for all kinds of tables.
I think it should be a MUST for all tables to support index-based 
access. Content-based search keys are optional: your example of 
FE-dynamically-created content shows that a simple content-based search 
key would suffice. Note that subsequent accesses may then use the index.

>FE should support such search.
The main difference is that the index is unique among all entries in a 
table, as opposed to the content-search key. So the index can be used to 
refer to a precise unique entry in a table, whereas a content-search key 
cannot. Remember that the index is an _artificial_ addition introduced 
by ForCES, whereas the _content_ is there in any case.

>access a whole table, instead of entries in the table.
The current path-data text posted by Jamal captures the basic 
content-search key, with the possiblity to AND multiple keys. If 
experience shows that this is not sufficient, we can later on extend 
this with a new TLV. For now I think it is acceptable to move forward 
with this.

Regards,
-Robert

>>>I actually talked about this before with Joel. I think Joel asked that in
>>>      
>>>
>this
>  
>
>>>If the above path-values are in one OpTLV, I can more or less live with it,
>>>      
>>>
>but
>  
>
>>>still think the mainpath and subpath mode is better than this. I supposed
>>>      
>>>
>Joel
>  
>
>>>asked the path-values be in different OpTLVs, which I'm hard to accept. I
>>>      
>>>
>think
>  
>
>>>such operation is originally atomic, to separate them into different OpTLVs
>>>      
>>>
>is
>  
>
>>>not reasonable enough.
>>>

-- 
Dr. Robert R. Haas
IBM Zurich Research Laboratory
Säumerstrasse 4
CH-8803 Rüschlikon/Switzerland
phone +41-1-724-8698  fax +41-1-724-8578  http://www.zurich.ibm.com/~rha

---

From: "Wang,Weiming" <[email-masked]>
Date: Sat, 22 Jan 2005 16:21:33 +0800

Joel, and Robert as well,

----- Original Message -----
From: "Joel M. Halpern" <[email-masked]>
Subject: Re: [issue6] Summary of Path

> 1) a situation where indices are not supportable
That's one of the arguing point. Althought I cannot give a very clear look of
the difficulty when indexapplied to tables that are originated from FE,  I see
the potentials for the difficulty. I can't see it very clear because the XML
definitions for LFBs have still not yet been presented(That's one reason I
suggeted for the fast work on it).
The potential difficulty comes like in this way, a table, althought whose
structure is defined by ForCES and can be accessed by CE,  whose entries are not
added by CE, instead, should by FE during run time. In this case, I presumed the
index for the entires should be generated by CE, but obviously it leads to some
difficulty. Now I want to focus our arguements based on this  as:
1. Are you absolutely sure there will be no such tables for ForCES?
2. If isn't, then how can we deal with it if an index is MUST for all tables?

> either of non-unique keys or keys that are not declared by the LFB class
Let's try to think of two kinds of LFBs: LPF LFB and Classifer LFB.

The rule attribute for an LPF LFB may include the fields as: the Prefix with its
Mask, the Nexthop. Then, which one do you think more preferable as Keys? I just
see they are all needed as searching keys. I think it's well known that if all
fields should be keys, there is no meaning to define keys anymore.

Then the Classifier LFB, the rule attribute for which may include fields as:
MatchField1, MatchField2, ... MatchFieldN, OutputPort. Usually any MatchField
has no privileges over others. I just see that, if we allow for one MatchField
as a searching key, we have no reason for others as keys. As a result, this also
leads to non unique keys.

Unless we have actual experiences with XML LFBs, I think it's too early to say a
limited key is meaningful.

Cheers,
Weiming

---

From: "Joel M. Halpern" <[email-masked]>
Date: Sat, 22 Jan 2005 10:23:22 -0500

There certainly may be tables which, for some FEs, are generated by the 
FE.  In some FEs they may even be such that the CE can not modify them.  I 
doubt that there will be any LFB classes where the class assumes that is 
always the case.
Even in such cases, the FE can assign indices to the entries in a dense 
fashion.  Remember that even CAMs are actually arrays (a sequence of memory 
entries) under the covers.  Even if the FE implementation chooses to use 
complex tree structures to represent something, there are still well known 
algorithms for assigning and using indices in such structures.  Possibly 
this is a failure of my imagination, but I really can not imagine a 
situation in which the FE can not support indexed access.

Note that performing arbitrary searches is a lot more logic than 
maintaining indexing information.  So any FE that can support arbitrary 
searches can easily support indexes.

With regard to the question of where arbitrary keying is needed, the 
question turns on the view of the operation.  From my perspective, content 
keying is potentially useful if it makes a CEs job easier.  The first thing 
that affects my view is the previous paragraph.  If basic indexing can not 
be counted on, then there is indeed a complex issue about what can be 
counted on.  Given that we define the keys (if we allow them) it follows 
that we can reasonably require uniqueness for them.  We structure the LFB 
definition so that fields which are keys are naturally unique.  (For 
example, for a longest prefix match LFB which uses IP address & prefix 
length keying, multiple next-hops would be represented as a table within 
the selected entry, rather than representing them as multiple entries with 
the same key.  Note this does not mean that the real hardware implements it 
as a two level table, but rather that the FE can manage the information 
exchange.)  Remember that the LFB definition is an abstraction of the 
structure intended to allow many different actual implementations.
In order for content keying to be useful to the CE, the CE programmer has 
to know, for any given LFB class, what things make sense to use.  Thus, 
arbitrary keying only makes sense if we expect the CE to behave very 
differently (use completely different keying) for different FEs.  While 
obviously there are variations in CE response based on FE capabilities, the 
idea is that most things will work the same way.  Otherwise, we have not 
achieved multi-vendor interoperability.

Yours,
Joel M. Halpern