Re: [Fwd: [Forces-protocol] Presentation oftheoptionsforLFB-levelmulticast]

[Jamal Hadi Salim <hadi at znyx.com>]

On Sun, 2004-11-07 at 23:48, Wang,Weiming wrote:

> [Weiming]I'v seen the difference. What you refered here as content based
> searching actually in my slides still belongs to the index-based path. In your
> example of NOP attributes, you only have one level of table, when you put the
> second level of table (that is, the Datatable in the NOP LFB you mentioned,
> which sub field is another table), you will see that anything is based on what
> you mean content based searching (which actually isn't content based).  Pls read
> other part of my slides where I think content based searching is quite different
> thing, something like:
> 
> Path = {AttrID1.f1= = vf1} && {AttrID1.f1.g1 = = vg1}
> 
> where you can see the difference is, in this path, there is no index, instead
> there are values for terminal nodes. Do you think a path can include values? I
> think no, therefore, my opinion is that the path except the attribute ID part
> should be inside the 'Data' field.
> 
> Anyway, I think what you mean content based searching is different from what I
> mean, and you actually still have not mentioned content based searching in your
> example.
> 

I did not elaborate on content addressing, just listed it as a bullet of
"under discussion" mostly because we as a protocol team have not
disccussed it since we are stuck on this that i thought is a difference
all along - just like we have not discussed block operations for the
same reasons. 

As a reminder from the doc posted by Steve (Sep 20 if you want to review
thread of discussion which i think you participated in) which described
the different table operation requirements:

---
4.3  Associative (Key-Based) Operators

In the following operators the following additional notations are used:
<key>:   Refers to the identification of the key. Note that the same
         table may be addressable by more than one key.  Indirectly,
         the key refers to the field in the table entry that will
         be compared to the <key-val>.
<mode>   Search modes as described in section 2 (e.g., exact match,
         all that match prefix, longest prefix match, range, etc.)
<key-val>  Data to be compared to the entry fields that are used as
           key. What is provided in <key-val> depends on the <key>
           and also on <mode>.
--------

Note the key-val is the value to be compared. We have no difference in
nested tables, so the expression you supplied applies here quiet well to
access content.

I have attached this document.

I also posted another document to try and map this document to
protocol-speak that i worked on. That document (was posted 2-3 weeks ago
to the protocol team) is attached. We have not reached that discussion
point is the reason this document or suggested BNF is not seen on my
slides.

Weiming, to be honest i still dont see the difference. I am giving you
the benefit of doubt given past experience with you - I think the may be
a difference. All i am saying is i dont see it.

What i would like to ask the chairs at this point is to make some time
for your presentation if possible. I will try to rush through mine and
allocate maybe 5 minutes at the end for yours if they dont have time.
Let other people judge. It is too bad we dont have you physically here.

[What you are forcing me to do now is talk more about content based
access as well as have a nested table example - which i wasnt planning
to do. The reason i have to talk more about it now is in order for
people who have no clue what this is to make a comparison against your
slides]

cheers,
jamal

Tables in the ForCES Model                                20-September-2004
==========================

1  Table Definition and Indexing
--------------------------------

An LFB table 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  a
table can be or can include other tables, respectively. The conceptual
model of the table need not correspond closely with any implementation
construct: any implementation may choose to  use  an  array,  a  radix
tree, a hash table, a doubly linked list, etc.

Each element in the table may be uniquely identified by its associated
table index, where the index is an unsigned integer that  is  assigned
-- either by the FE or the CE, depending  on  operation  --  when  the
entry is inserted into or moved within the table. The index  value  is
not part of the table entry definition;  indices  are  a  property  of
every LFB table. The generic  index  type  in  ForCES  is  the  32-bit
unsigned integer, but a table 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). Table entries need not be packed  sequentially  (this
is implementation dependent), but will usually be packed densely.

The order of entries in a table is not meant to represent any form  of
precedence of entries. For LFB tables that contain elements  that  are
searched in the datapath in some  precedence  order,  that  precedence
order must be maintained by the CE, by appropriate specification of  a
precedence field defined in each element.

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 table. As the
index is immutable, tables do  not  compact,  i.e.,  they  can  become
sparsely populated (from the index point  of  view)  as  a  result  of
subsequent insert and delete operations.

In addition to the index range restrictions discussed above, the table
may also specify the maximum  number  of  elements,  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  Optional Associative Addressing
----------------------------------

In addition to addressing table entries by  index,  individual  tables
can define one or multiple optional search  keys  (in  the  LFB  class
model). A search key can be used by ForCES for associative  addressing
of table entries.

A search key can be defined as the entire element comprising the table
entry or -- if the element is of a struct type -- exactly one specific
field of the struct (including a sub-structure). A particular  element
may define more than one field that may be used  independently  as  an
associative search key.

For example, an IP prefix LFB will contain a  table  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 allows insert and delete operations using the ip_prefix  as
a table entry address. In addition, the nhid could also be defined  as
an alternative search key.

A variety of associate search operators may be  supported  by  ForCES,
including:

- Exact match
- Prefix:
  - Shortest Matching Prefix
  - Longest Matching Prefix
  - All Matching Prefixes
- Range:
  - Smallest Match in Range
  - Largest Match in Range
  - All Matches in Range

The particular operators supported for a particular search  key  in  a
particular element will be specified  in  the  appropriate  LFB  class
definition, and may also be limited by  a  LFB  instance  (as  an  LFB
capability).

Multiple entries in a table may contain the same value  for  a  search
key under the applied search  operation.  An  associative  search  may
therefore return more than one matching entry.

The most prevalent addressing technique is expected to be index based.
In cases where a table's entries are  accessed  in  the  dataplane  by
associative search (e.g., IP prefix LFB), it may  often  be  the  case
that it is most convenient for the CE to access the table entries  via
associate search as well.


3  Table Definition Information
-------------------------------

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

   type of the table 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)
   search_op*           uint32                  0 (a bit-mask of allowed
                                                operators)

* More than one key may be defined for the same table.

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
   search_key_enabled*  uint32                  0 (a bitmap of allowed
                                                search keys specified in
                                                the LFB class definition)
   search_op*           uint32                  0 (a bitmap of allowed
                                                operators, specified)

(Note that most of the above information  are  not  reflected  in  the
current working  draft  of  the  XML  schema,  but  --once  reasonable
consensus is gained in the group-- it will be included  in  a  revised
version.)


4  Table Operations
-------------------

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

Insert operations for both FE-assigned indices and CE-assigned indices
are supported.

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.

Manipulating the sub-content of a given existing  table  entry  (e.g.,
setting a field of  a  struct  table  entry)  is  not  regarded  as  a
table-specific operation, and hence we do not  discuss  them  here  in
detail.

Note that technically INS and DEL are the  only  two  basic  operators
that are  absolutely  needed,  all  other  operators  are  convenience
operators, i.e.,
- they either allow the CE to be more state-less, or
- improve performance by minimizing protocol load.

Note that not reporting an 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).

All operations require LFB ID (type+instance),  and  path  information
that identifies the table. This path information may be as  simple  as
an attribute ID (if the table is a top-level attribue of the LFB),  or
it can be a sequence of IDs (path) if the table is buried  under  some
other attribute.

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

Notation:
        table           refers to the table addressed by above path
        idx             is the index provided to the operator (where
                        applicable)
        idx'            is an index generated by the operator (FE)
        <path>          Path that unambigously identifies a table
        <data>          data to initialize or over-write table entry,
                        or obtained from table entry
        <key-val>       Data used in associative addressing in table.
                        It can be a full table entry or a field in
                        a struct-based table entry.


4.1  Atomic, Index-based Operations (INS, INS-IDX, DEL, SET, GET)

4.1.1  INS

Parameters: <path>, <data>
Returns:    success indicator, idx'
Insert with FE-originated  index.  Finds  an  unused  index  idx'  (if
available), creates new entry at idx', and intialize it with <data>.
If it cannot find an unused index without violating the index or size
constraints, it fails.

4.1.2  INS_IDX

Parameters: <path>, idx, <data>
Returns:    success indicator
Insert at CE-provided index. Check if provided index is unused. If  it
is, initialize it with <data>, otherwise indicate error.

4.1.3  INS_IDX!

Parameters: <path>, idx, <data>
Returns:    success indicator
This is an altered version of the previous  INS_IDX  in  that  if  the
index is already in use, it overwrites the  entry  with  the  provided
<data> (instead of reporting error).

4.1.4  DEL

Parameters: <path>, idx
Returns:    success indicator
If table[idx]  is  used,  delete  table  entry  (making  idx  unused),
otherwise report error.

4.1.5  DEL!

Parameters: <path>, idx
Returns:    success indicator
Delete table[idx] if it exists, do  nothing  otherwise  (never  report
error).

4.1.6  SET

Parameters: <path>, idx, <data>
Returns:    success indicator
If table[idx] exists, overwrite  its  content  with  provided  <data>,
report error otherwise.

4.1.7  SET!

Parameters: <path>, idx, <data>
Returns:    success indicator
If table[idx] exists, overwrite  its  content  with  provided  <data>,
create new entry with idx otherwise.

4.1.8  GET

Parameters: <path>, idx
Returns:    success indicator, <data>
If  table[idx]  exists,  return  with  its  content,  indicate   error
otherwise.

4.2  Index-based Block/Bulk Operations

These block/bulk operations are considered to save protocol overhead
when simultaneously dealing with a large number of table entries.

In the following <idx-data> will be able to capture any one of the
following things:
[a, b]:   index range, matching all entries with idx: a<=idx<=b
[a, N]:   N (used) entries starting from idx=a and progressing to increasing
            indices, skipping unused entries
[a, -N]:  N (used) entries starting from idx=a and progressing to lower
            indices
<all> :   All (used) entries in the table.
N     :   N entries anywhere (used only in the INS_BLK operation)

<data>* refers to the data to initialize/set the specified table entries,
or obtained from the specified table entries.

4.2.1  INS_BLK

Parameters: <path>, <idx-data>, <data>
Returns:    success indicator, <idx-data>
TBD

4.2.2  DEL_BLK

Parameters: <path>, <idx-data>
Returns:    success indicator
Delete all entries specified by <idx-data>.  TBD: how to handle errors?

4.2.3  SET_BLK

Parameters: <path>, <idx-data>, <data>*
Returns:    success indicator
Sets all elements specified by <idx-data> with the provided <data>*.
TBD: how to handle errors?

4.2.4  GET_BLK

Parameters: <path>, <idx-data>
Returns:    success indicator, <data>*
Obtains content of all entries specified by <idx-data>.


4.3  Associative (Key-Based) Operators

In the following operators the following additional notations are used:
<key>:          Refers to the identification of the key. Note that the same
                table may be addressable by more than one key.  Indirectly,
                the key refers to the field in the table entry that will
                be compared to the <key-val>.
<mode>          Search modes as described in section 2 (e.g., exact match,
                all that match prefix, longest prefix match, range, etc.)
<key-val>       Data to be compared to the entry fields that are used as
                key. What is provided in <key-val> depends on the <key>
                and also on <mode>.

4.3.1  GET_IDX_BY_KEY

Parameters: <path>, <key>, <mode>, <key-data>
Returns:    success indicator, <idx>*
Returns with the index of all entries identified by <key>, <mode>  and
<key-data>.

4.3.2  DEL_BY_KEY

Parameters: <path>, <key>, <mode>, <key-data>
Returns:    success indicator
Deletes all entries identified by the <key>, <mode>, and <key-data>.

4.3.3  SET_BY_KEY

Parameters: <path>, <key>, <mode>, <key-data>, <data>*
Returns:    success indicator
Overwrites all entries identified by  <key>, <mode>,  and  <key-data>.
TBD: Some restrictions on mode will apply.

4.3.4  GET_BY_KEY

Parameters: <path>, <key>, <mode>, <key-data>
Returns:    success indicator, [<idx>*], <data>*
Returns with the content (and optionally the  index)  of  all  entries
identified by the <key>, <mode>, and <key-data>.


5  Path Semantics
-----------------

Paths to tables or other  attribute  elements  are  represented  by  a
sequence of element identifiers, starting with the identifier  of  the
associated  LFB  attribute.  Path  identifiers  are  unsigned   32-bit
integers which are assigned to each element and sub-element of  a  LFB
class's attributes in the class definition.

As an example, imagine a class with an attribute a which is a table of
structures, each of which contains another table as the third element.
The path {a,b,c,d} would represent attribute a, table index  b,  table
element c, table index d.


6  Metadata Value Binding to Table Entries
------------------------------------------

The index of a LFB table entry can be used for two purposes: one is to
access the table entry via the ForCES protocol  (INS,  DEL,  SET,  GET
commands), the  other  is  to  access  the  entry's  contents  in  the
dataplane. This latter usage is achieved by using some metadata  value
associated with the packet as the lookup index in  the  table.  As  an
example, a CLASS_ID metadata item could be used to select a rate meter
entry in a table in a Rate Meter LFB.

The example above represents an implicit binding  between  a  metadata
item value and a table  entry.  Alternatively,  the  metadata  binding
could be defined explicitly,  by  specifying  a  field  in  the  table
element definition which is the metadata match  value.  The  value  of
this field must be unique  across  all  table  entries  to  ensure  an
unambiguous mapping to  incoming  metadata  values.  Usage  of  either
implicit or explicit metadata binding will be  specified  in  the  LFB
class definition.

The metadata value emitted by a LFB operation is configured by the CE.
In the case of implicit metadata binding, the CE can allow the  FE  to
determine the appropriate table entry index in the downstream LFB, and
can configure that  value  into  the  upstream  LFB,  or  the  CE  can
determine  the  metadata  value,  and  configure  the   upstream   and
downstream LFBs in any order.

This doc builds up on what was posted by Steve/Zsolt[1] to
try to map to protocol.
It by no means imposes a decision i.e tghis is merely here
as a discussion place holder with the a desire to speed things
up.

NOTE:
-----

A small reminder on layout:

main hdr (eg type = config)
     |
     |
     +--- T = LFBselect
     |        |
     |        +-- LFBCLASSID = 0x45 
     |        |
     |        |
     |        +-- LFBInstance = 0x1234
     |        |
     |        +-- T = ADD //operation
     |        |   |
     |        |   +--  // path target X
     |        |        // with data to be added
     |        |        // This is the discussion point 
     |        |
     |        +-- T = ADD //operation
     |        |   |
     |        |   +--  // path target Y
     |        |        // with data to be added
     |        |        // This is the discussion point 
     |        |
     |        |
     |        +-- T  = DEL //operation
     |        .   |
     |        .   +--  // path target Z
     |        .        // This is the discussion point 
     |            

1) There could be multiple operations on any instance
2) path-data comes after the operation.
3) there is only one path-data per operation.

A possible path-data layout. 
----------------------------

OPER_TLV : = <PATH-DATA>
PATH-DATA := flags IDcount <IDs> [BLOCK_OR_KEY_NOTATION] [DATA]

The operational TLV contains an opcode in the T part. Its V
contains the PATH-DATA.
Opcodes discussed so far:
* SET (create, modify or both depending on PATH-DATA flags}
* DEL (remove an existing entity specified by PATH-DATA }
* GET (Access a entity specified in PATH-DATA }
* EV_S (subscribe to an event defined in PATH-DATA }
* EV_U (unsubscribe to an event defined in PATH-DATA }

-> IDs := a series of 32bit IDs (whose size is given by IDcount)
defining the path.
-> flags are used to further refine the operation to be applied
on the ID_TLV.
-> BLOCK_OR_KEY_NOTATION := optional different BLOCK or KEY extension
defined in section 4.2 and 4.3 of [1]
-> DATA : = Optional variable sized data dependent on PATH
and applied operations (eg GET will not have DATA).

Some Clarification in relation to [1]:
-------------------------------------

[1] represents a requirement gathering/place holder.
This document is into details closer to implementation.

flags
-----

Derived from netlink and BSD route sockets to meet requirements
defined in [1]:

--> F_EXCL: 
The exclusive flag.
Donot replace the config attribute(s) if already exists -
Report back error instead.

A CREATE operation with this flag is equivalent to 
INS_IDX if index is passed and equivalent to  INS if index is 
not passed in the IDs.
A DEL with this flag is equivalent to DEL! in [1]. Without
this flag the equivalency is to DEL.

--> F_REPLACE: 
Replace existing matching config attribute(s) with passed 
data.  An index must be passed. In the case of key operations, a 
KEY must be passed.
A CREATE operation with this flag is equivalent to a SET
or a INS_IDX!.

Steve/Zsolt please double check that this is matching to your
doc.

A CREATE operation with F_EXCL|F_REPLACE is equivalent to SET!

** Other flags used for block operations mentioned in the BLOCK section.

BLOCK and KEY path selection
-----------------------------

The <all> variant described in [1] is not needed. To get access
to all of table contents, the IDs merely need to point to the table.
Therefore to access a range, the IDs field will contain the ID
leading to a table and an optional TLV will include the range
information.

- Additional flags needed:
1)F_BLOCK_ON, to indicate block selector embeded
2)F_KEY_ON, to indicate a key selector embeded
#1 and #2 are mutually exclusive.
3) F_REV_TRAVERSE, to indicate reverse progress in the access.
4) F_KEY_MODE (2 bits or more) to select the KEY mode in case #2 is
on.
5) F_BLOCK_MODE (1 bit); indicates count or range for second
parameter of BLOCK Notation.

In the case of block operations: 

Two modes exist. [a,b] or [a,N]
We introduce a block TLV

T = BLOCK_TLV
    start // "a"
    end // "b" or "N"

The flag F_BLOCK_ON will indicate the presence of this TLV.
F_BLOCK_MODE will indicate that "end" is an "a" or "N"
F_REV_TRAVERSE will indicate whether reverse or forward progress

In the case of the associative paths: 
the flag F_KEY_ON will indicate that we are using associative approach 
F_KEY_MODE will define the mode .

We introduce a KEY_INFO TLV.

T = BLOCK_TLV
    KEY
    KEY_DATA

The length of the TLV will help deducing the size of the KEY_DATA.

DATA:
-----
Not discussing the optional data right now; a lot of details
above need ironing out first.
DATA is complex twist when it comes with variable sized data.

$Log: path-data-oper.txt,v $
Revision 1.2  2004/10/16 14:03:25  hadi
incoporating feedback from Joel et al

Revision 1.1  2004/10/14 13:12:32  hadi
Initial revision

_______________________________________________
Forces-protocol mailing list
Forces-protocol at ietf.org
https://www1.ietf.org/mailman/listinfo/forces-protocol