Subject: Re: Table model and config operators in ForCES rev. 2

From: Jamal Hadi Salim <[email-masked]>
Date: Sun, 3 Oct 2004 11:36:17 -0400

Steve/Zsolt

On Mon, 2004-09-20 at 13:42, Steven Blake wrote:
> After some discussions between the model and protocol design teams,
> Zsolt Haraszti and I took the to-do to put together a proposal on how
> LFB tables could be modeled and managed in the protocol.

Finally got to peruse the doc over a large coffee.
A few things:
1) In reference to the approach from Joel (that i posted a while back),
an index is part of the path. You seem to have separated it. It actually
does seem to make sense to do so for two reasons:
a) an index is a dynamic runtime notation as opposed to a "static" class
time definition.
b) facilitates the block operations by having it separate.

I am not sure if you had this in mind - thought id mention it.

2) You seem to preclude using the index as part of an entry definition.
I think thats a legit usage.

3) Indices should be reusable when elements dissapear.

4) associative addressing/keying

Hrm. I reread this twice and something is still bothering me.
It does have an implicit "search" built in. First you search for _all_
references of the key and then operate on them.
We have not talked about putting a search message on the protocol
because it hasnt made any sense (so far maybe).
Now you could also be meaning an atomic search_and_operate in which case
that implies offloading the search to the FE. Not sure how wise that is.
When do you see this as valuable?
Wouldnt it just make sense for the CE to keep track of the state and
infact such queries - if they need to be the sent to the FE (in the case
the CE cant resolve them) - should first be translated into a proper
path with proper indices (probably block indexing) then sent?

5) I am not sure i agree that INS and DEL are the only two operations
needed. As an example:
You could just instantiate a row without updating its values. And later
update its values. So an ADD which is what you may be refering to as an
INS is infact the two operations:
an atomic CREATE (gives default values of say all 0s)+UPDATE (enter new
values. An UPDATE could happen at any point to say update a cell.

I think this specific subject is larger than just table items - so i
will punt for now (but hope you would remove that assertion you have).

cheers,
jamal

---

From: Steven Blake <[email-masked]>
Date: Mon, 4 Oct 2004 17:33:19 -0400

> I am not sure if you had this in mind - thought id mention it.

That is exactly what we had in mind.

> I think thats a legit usage.

We don't intend to preclude having the index as part of the entry
definition.  If the index is defined as part of an entry in the class
model, then the INS command (not INS_IDX) would be used to insert the
entry.

I'm not sure what you think is a legit usage: allowing the index as part
of an entry, or not?

> 3) Indices should be reusable when elements dissapear.

Agreed.

> references of the key and then operate on them.

Not always.  For example, if the associative addressing operation is
'exact match', you wouldn't expect to match more than one entry.

> because it hasnt made any sense (so far maybe).

Actually, associate addressing was on the agenda of the last conference
call.

> When do you see this as valuable?

The example most often mentioned is searching for an IP prefix entry
by prefix value, rather than by index (so you wouldn't have to maintain
the indices allocated to each FE for a particular prefix table).

> path with proper indices (probably block indexing) then sent?

It's a question of how much state you have to and want to mirror on the
CE.  Strictly speaking, associative addressing is not mandatory, because
you could always maintain copies of each and every table on the CE.
There are some potential efficiency gains to be had if you support it,
and the proponents should have the burden of quantifying them.

> values. An UPDATE could happen at any point to say update a cell.

In the vernacular of the proposal, INS == ADD, SET == UPDATE.  The
assumption underlying this is that the entries already exist, so you
don't have to create individual rows, for instance, you just have to set
them to non-default values (default usually zero and inactive, but
specified in the class definition).

With INS_IDX and DEL_IDX only, you could maintain complete
synchronization of state between the CE and FE.  Of course nobody is
proposing to limit the operation set to only these two.

> will punt for now (but hope you would remove that assertion you have).

Did my comment clarify the situation?

Regards,

// Steve

---

From: Jamal Hadi Salim <[email-masked]>
Date: Tue, 5 Oct 2004 11:14:11 -0400

> I'm not sure what you think is a legit usage: allowing the index as part

Allowing it as part of a table entry in addition to it being a path
defining entity.

> 'exact match', you wouldn't expect to match more than one entry.

It would still necessitate a search of some form which would be a _lot_
more complex than that of a simple index.
In your text you do refer to the associative piece as a "search" key;
- the index is more of a path identifier.

> Actually, associate addressing was on the agenda of the last conference

I know - I am just trying to replace it in context now that you have
put it in text.

> the indices allocated to each FE for a particular prefix table).

The search by prefix as a datapath operation is understandable.

In a management perspective though (as in the case of a CE asking a FE
to reference an entry in a table), does it not make sense to maintain
indices even if they dont make sense from a datapath perspective?

> and the proponents should have the burden of quantifying them.

If you assume that CE and FE states would be in sync - a valid
assumption i believe - then i see the efficiency as having more state at
the CE.
I am not sure now which side Joel was on, but could you hint one value
on doing it at the FE with a search key?

> Did my comment clarify the situation?

It does.
I think its easier to look at what you specified as requirements
then we (the protocol team) would discuss how best to meet those
requirements.

cheers,
jamal

---

From: "Joel M. Halpern" <[email-masked]>
Date: Tue, 5 Oct 2004 11:23:04 -0400

I tend to think that all we need is simply indexed tables from a management
perspective.  All "searching" would then be the responsibility of the CE,
using the tables it has.  I think that will keep the protocol simpler and
keep the FE simpler in most cases.  In a few cases where the FE natural
implementation is a memory associative structure (hash or tree), this would
be somewhat more effort for the FE to support.  (Note that real CAMs are
actually a case where the index method works find, since those naturally
have real indexes for management, while supporting context lookups for data
plane.)

Yours,
Joel

---

From: "Joel M. Halpern" <[email-masked]>
Date: Wed, 6 Oct 2004 14:22:47 -0400

Aren't INS_IDX! and SET! identical operations?

Allowing value based indexing to match multiple entries seems a
mistake.  It makes "key" not a key.  It seems to me that if we are going to
allow associative access at all, it should only be to identified key fields
and only when those fields are actually sufficiently unique keys.

Yours,
Joel M. Halpern

At 01:42 PM 9/20/2004 -0400, you wrote:
>LFB tables could be modeled and managed in the protocol.  The attached
>file is what we came up with.
>
>Please review and send comments to the list.
>
>
>Regards,
>
>// Steve

---

From: Zsolt Haraszti <[email-masked]>
Date: Thu, 7 Oct 2004 00:46:44 -0400

> Aren't INS_IDX! and SET! identical operations?

Yes, they are; one can be eliminated.  My mistake.

> and only when those fields are actually sufficiently unique keys.

I tend to agree.

/zsolt

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