Subject: [Fwd: Table model and config operators in ForCES (WAS: [Forces-protocol] RE: Protocol/model discussion?)]

From: Zsolt Haraszti <[email-masked]>
Date: Tue, 10 Aug 2004 21:43:36 -0400

OK, here it is.  My apologies to everyone who missed our
previous discussions so far (including Alan; I guess we just
wanted him to focus on his newborn baby;)

Listening to the conversation on the above topic made me
to sketch out a tentative model for the "table" as well
as enumerate some potential operators that one can define
for table entry management.  I tried to accommodate most of
the comments/suggestions/issues I heard.  Please take a look.
Don't chop my head off if you don't like something.  What I think
is a good plan to go forward:
Step 1: Lets discuss and agree on the table semantics (Sections 2 & 3)
Step 2: (After Step 1) Lets agree on the set of operators (at the
        semantical level) we want to support.
Step 3: (After Step 2) One set of designers can go ahead and draft how
        these operators will be mapped to protocol commands (TLVs)
Step 4: (After Step 1) I can put the necessary extensions into the XML
        schema.

Tables in the ForCES Model
==========================

1  The Definition of a Table
----------------------------

A table (also called array) is a conceptual model of an  ordered  list
of data elements (entries) of identical type, where the  type  can  be
any of the ForCES-supported data types, including atomic and  compound
types. Note that since compound types include arrays and structs,  the
entries in an array can be or can include other arrays, respectively.

Each element in the array is uniquely identified by its  index,  where
index is an unsigned integer. The generic index type in ForCES is  the
32-bit unsigned integer, but an array can narrow  down  the  allowable
indices by specifying an allowed index range, denoted here as  min_idx
and max_idx.  If  the  index  range  is  not  specified,  the  default
allowable range is between 0 and 2^32-1,  both  inclusive  (min_idx=0,
max_idx=2^32-1).

In addition to addressing elements by the index, arrays can define  an
optional search key and use the search key for addressing. The  search
key can be defined as the entire element or --if the element is  of  a
struct type-- one specific field of the struct.  For  example,  an  IP
prefix table will contain an array of prefix entry structs having  the
following fields: IP prefix (ip_prefix), next-hop  identifier  (nhid),
and a set of counters (counters).  The  ip_prefix  itself  will  be  a
struct of two 32-bit values, an IPv4 address and  a  prefix  mask  (or
prefix length). A very useful search key for such an IP  prefix  table
would be the ip_prefix. Defining the ip_prefix as a search  key  would
allow insert and  delete  operations  using  the  ip_prefix  as  table
element address.

The most prevalent addressing technique is expected to be index based.

In the ForCES model the index has a permanent,  immutable  association
to the element, i.e., it is created when the element is created and it
does not change as other elements are manipulated in  the  array.  The
only operation that can change the index of an existing element is the
(block-)move operation, which is regarded as an  in-FE  short-cut  for
the more expensive (block-)delete and (block)-create operations.

As the index is immutable, tables do not  compact;  thus  we  need  to
discuss the notion of unused elements. When  an  array  is  originally
created, by default all of its elements (i.e., the  allowed  range  of
indices) are unused. The table gets populated by the  INSERT  (one  of
its flavors, see below) operation. Since many flavors of INSERT  allow
the CE to explicitly specify the index of the newly created entry  and
since the table does not compact after any of the  DELETE  operations,
the table may be  partially  filled  with  unused  and  used  elements
interspersing each other.

In addition to the index range restrictions discussed above, the array
may also specify the maximum number of (used) elements in  the  array,
denoted here as max_size. Note that this value  may  be  smaller  than
what is implied by the allowed range. The default value of max_size is
max_idx-min_idx+1. If specified, max_size cannot be greater  than  the
current max_idx-min_idx+1.

The schema will allow the optional definition of default  content  for
the table. If the default content is specified, the FE will  intialize
the table when the table is created (i.e., when the  LFB  instance  is
created or when a new table inside an LFB  instance  is  created.  The
schema will support full and partial initialization (including  sparse
population).

2  Table definition information
-------------------------------

The following information will be  provided  for  all  tables  in  the
LFB/FE model:

   type of the array elements

The  following  are  additional  optional  information  that  can   be
statically provided in the LFB specifications for each table:

   information          type                    default value
   -----------          ----                    -------------
   hard_min_idx         uint32                  0
   hard_max_idx         uint32                  2^32-1
   hard_max_size        uint32                  2^32
   search_key_enabled   boolean                 false
   search_key           int32(struct field id)  0 (refers to the struct
                                                field if entries are
                                                structs)

In addition, real-time FE-level and per-LFB-instance soft  limits  can
be specified either in the FE LFB  or  in  the  actual  LFB  instance,
respectively:

   information          type                    default value
   -----------          ----                    -------------
   soft_min_idx         uint32                  hard_min_idx
   soft_max_idx         uint32                  hard_max_idx
   soft_max_size        uint32                  hard_max_size

(Note that most of the above information  are  not  reflected  in  the
current working draft of the XML schema.)

3  Table management operations
------------------------------

Following  is  an  itemized  list  of  tentative  *conceptual*   table
operations. How these will be mapped to what protocol operators is not
discussed here. First the WG needs to settle on what  operations  will
be supported and then it  can  flesh  out  the  actual  operators  and
associated encoding.

LFB instance creation is not discussed here. Table creation (in  cases
where the table is embedded in another table) is not  discussed  here.
We assume that when  the  table  is  created,  all  the  above  listed
associated information is initialized. In  addition,  if  the  default
content is specified for the table,  the  initial  table  entries  are
created.

All operations require LFB ID (type+instance),  and  attribute  ID  as
mandatory  parameters.  If  the  table  is  buried  under  some  other
attribute, unambiguous path information to  the  table  must  also  be
provided. These are not shown below, but should be implied.

All range and max_size checking are applied to all insert and move
operations.

Notation:
        table           refers to the table addressed by above
                        parameters (i.e., the target of the operator)
        idx             is the index provided to the operator (where
                        applicable)
        idx'            is an index generated by the operator (FE)
        idx_f           is the index of the first used element in table
        idx_l           is the index of the last used element in table
        *               Operator is crucial (others are value add
                        features)

Operation       Parameters      Semantics
---------       ----------      ---------

Index based operators:

*INS_AT_IDX     idx, <entry>    table[idx] = <entry> if table[idx] is
                                unused, error otherwise.
                                Returns: success indicator.

SET_AT_IDX      idx, <entry>    table[idx] = <entry> irregardless if
                                the entry is used or not (creating it
                                if it wasn't used yet).
                                Returns: success indicator.

INS_BEFORE      idx, <entry>    If table[idx] is used, find unused
                                idx'<idx so that there are no used
                                entries between idx' and idx, and then
                                table[idx']=<entry>.
                                Return idx' on success.  If table[idx]
                                is not used or if idx' cannot be
                                found, report error.
                                Returns: idx' and success indicator.

INS_AFTER       idx, <entry>    Similar to the INS_BEFORE
                                Returns: idx' and success indicator.

INS_AT_FRONT    <entry>         Try to find idx' such that idx'<idx_f.
                                If found, return idx', otherwise report
                                failure.
                                Returns: idx' and success indicator.

INS_AT_TAIL     <entry>         Try to find idx' so that idx'>idx_l.
                                If found, return idx', otherwise report
                                failure.
                                Returns: idx and success indicator.

INS_BLOCK       <indices>,      Tricky semantics.  To be fleshed out
                <entries>       later.

*DEL_AT_IDX     idx             If table[idx] is used, free it and
                                indicate success.  Error otherwise.
                                Returns: success indicator.

DEL_AT_IDX!     idx             Set table[idx] unused.
                                Returns: success indicator.

DEL_BLOCK!      idx1, idx2      Repeat DEL_IDX! for each idx in
                                [idx1, idx2]
                                Returns: success indicator.

MOVE            idx1, idx2      Verifies that table[idx1] is used and
                                table[idx2] is not.  Then makes
                                table[idx2]=table[idx1] and makes
                                table[idx1] unused.

Key based operators:

INS_BY_KEY      <key>,<entry>   If <key> is not yet in table, find
                                appropriate idx' where new entry can
                                be added.  Create new entry by
                                table[idx']=<entry>. Report error
                                if an entry with <key> exists already.
                                Returns: idx' and success indicator.

SET_BY_KEY      <key>,<entry>   Similar to INS_BY_KEY, but it does not
                                report error if an entry with <key>
                                exists already; it simply overwrites
                                entry.
                                Returns: idx' and success indicator.

DEL_BY_KEY      <key>,<entry>   Locates table[idx'] with key <key>
                                and removes its (making it unused).
                                Returns: success indicator.

In  addition,   reading   and   manipulating   most   of   the   table
meta-information mentioned in Section 2 needs to be supported. (TBF).

Manipulating the sub-content of a given existing  table  entry  (e.g.,
setting a field of a struct table entry) is not in the scope  of  this
analysis.

Note that  technically  INS_AT_IDX  and  DEL_IDX  are  the  two  basic
operators  that  are  absolutely  needed,  all  other  operators   are
convenience operators, i.e.,

- they either allow the CE be more state-less, or
- improve performance by minimizing protocol load.

Note that not reporting error on an  operation  is  not  the  same  as
ignoring an error report by the  CE  (consider the effect  on  batched
requests  and atomic operations).
--
Zsolt Haraszti                Phone:  +1 919-765-0027/2017
Modular Networks              Mobile:      +1 919-522-2337
                              Email:  [email-masked]

---

From: "Khosravi, Hormuzd M" <[email-masked]>
Date: Wed, 11 Aug 2004 14:58:59 -0700

Zsolt,

Thanks for taking the effort to put this text together in a very
comprehensive way.

I do have a few comments...

I like the notion of using a search key for addressing entries in the
table array. This is very common, as Steve pointed out an example of a
Prefix table. I don't think that indexes are needed for all tables, they
may be needed in some tables...depending on the LFB table. Another thing
that comes to mind if we go with using indexes is that we might land up
having to maintain lots of state on the CE for this, which is a bad
thing. We should keep the protocol and CE as stateless as possible.

I don't see why operations like Move should be exposed at the protocol
level, this to me is more like the functionality of the FE
implementation.

Regarding the Operations that have been defined (based on indexes),
again I feel like they are a lot more than what is needed (ADD, DEL,
UPDATE, DEL ALL). Same point regarding keeping lots of state on the CE
to maintain this info, comes to mind. The operations, the way they are
defined, seem like they are exposing some of the intelligence of the
data model into the protocol. The protocol should just have enough
intelligence to know whether it is adding or deleting a block of data
(or a sub-table). Whether the data should be inserted at a certain point
in a table, that info should be part of the data itself. For e.g., the
data entry could be <id>, <foo>, <soo>. The protocol will carry this in
a message such as ADD with data as -><id1>, <foo1>, <soo1>, <id2>,
<foo2>, <soo2>... (I am not showing all the details of the message here,
they are same format as what Jamal had sent out after discussions with
you guys)

That's all for now. Let me know what you guys think, if this makes sense
or not. I am glad you put this text together, it really helps get us all
on the same page.

regards
Hormuzd 

-----Original Message-----
From: Forwarding and Control Element Separation
[mailto:[email-masked]] On Behalf Of Zsolt Haraszti

Notation:

Index based operators:

Key based operators:

---

From: Zsolt Haraszti <[email-masked]>
Date: Tue, 17 Aug 2004 10:30:52 -0400

Hi Hormuzd,

Sorry for my sloppy response.  See my comments below.

On Mon, 2004-08-16 at 19:06, Khosravi, Hormuzd M wrote:
> Hi Zsolt
>
> I never received a reply to my email below, so I was wondering why.
> I guess you might be busy with the start-up but just wanted to confirm
> the reason.
>
Yeah, it is a bit busy lately...

> Let me know your thoughts,
>
> Thanks
> Hormuzd
>
> [mailto:[email-masked]] On Behalf Of Khosravi, Hormuzd M
> Sent: Wednesday, August 11, 2004 2:59 PM
> To: [email-masked]
> Subject: Re: [FORCES] [Fwd: Table model and config operators in ForCES
> (WAS: [Forces-protocol] RE: Protocol/model discussion?)]
>
> Zsolt,
>

Indices fulfill two roles:
- imply entry ordering
- reference for incremental table management
For tables where neither of these are needed, you don't really need
the index.  For example: a set-type attribute (where the order does
not matter) and you never need to remove an element, and you can
use the "append" operation (INS_AT_TAIL in the list below).

Regarding key-based addressing, my opinion is that in some cases
it is juts plain natural to use them, and it makes both the CE's
and FE's life easier.  The LPM example is the best I know.  Not having
keys would force both parties to maintain an index association table
that would otherwise be unnecessary.

> level, this to me is more like the functionality of the FE

Suppose you added some element already to your table and you have
the following elements (indices) used: 0, 1, 2, 3, 4, 5 are all used.
Assume that you need to insert three new elements to the front of
the table.  What do you do?  Since the index in the described model
is sticky, you need to make some room for the new entries by moving
the existing elements up.  That is what the move operation can help
you with.

> UPDATE, DEL ALL).

This is kind of an exhaustive list.  Strictly speaking you can get
away with the above subset.

>  Same point regarding keeping lots of state on the CE
> to maintain this info, comes to mind.
Some of the other "convenience" commands actually help avoiding state
in the CE instead of adding more load.

> The operations, the way they are
> in a table, that info should be part of the data itself.

I did not in any way said that this is what the protocol header must
support.  I tried to emphasize that the first step is defining the
semantics (and that is what I tried) and the second is to decide
what information goes into what TLV.  I agree that, e.g., a good
subset of the listed operations can be supported by the same 'ADD'
directive and carry the various sub-case selectors encoded in the index
value.  I just did not want to make the two design steps in one.

/zsolt
PS I will be out of reach till late evening today.

>  For e.g., the

---

From: "Khosravi, Hormuzd M" <[email-masked]>
Date: Tue, 24 Aug 2004 15:01:19 -0700

Zsolt,

Thanks for your response. Pls see my comments below... 

-----Original Message-----

[HK] I agree.

Suppose you added some element already to your table and you have
the following elements (indices) used: 0, 1, 2, 3, 4, 5 are all used.
Assume that you need to insert three new elements to the front of
the table.  What do you do?  Since the index in the described model
is sticky, you need to make some room for the new entries by moving
the existing elements up.  That is what the move operation can help
you with.
[HK] Move can help here but is not necessary. I could do the same using
an ADD operation with indices 0,1,2, this could be interpreted in the
same way. (An Update would overwrite the entries)

This is kind of an exhaustive list.  Strictly speaking you can get
away with the above subset.
[HK] Then lets keep it simple unless there are good reasons to have the
entire list of operations.

Some of the other "convenience" commands actually help avoiding state
in the CE instead of adding more load.
[HK] Could you give an example here ? I am missing something...

[HK] Ok, this sounds good to me. Thanks for the clarifications.

Regards
Hormuzd