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

From: Jamal Hadi Salim <[email-masked]>
Date: Tue, 10 Aug 2004 23:35:51 -0400

I have CCed the list.

I like the approach - should clean up a lot of section 5.

The only issue i have is in defining the table as:

----
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.
=====

That would be one type of table (another would be a hash table in which
a bucket at subscript 10 may have entries that could be refered to as
index 3 and 7). Is there any good reason to restrict it to this (array)?
XML semantics require it?

Another issue i have is on the issue of deleting. You refer to the index
as non-immutable. In ASIC where memory is preserved anyways, this may be
a non-issue (but even there aging is important). Garbage collection
is important in s/ware even if you have a bounded upper limit.
Is this also maybe related to the XML modeling?

Having said all that - i think you have well laid out the commands
that will cover either an array approach or a hash table etc.

Lets rediscuss if there are some XML related issues.

cheers,
jamal

On Tue, 2004-08-10 at 17:00, Zsolt Haraszti wrote:
> Hi Protocol/Model Teams,
> (BTW, I am not sure the above CC list cover everyone.)
>
> 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).