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 that unambigously identifies a table data to initialize or over-write table entry, or obtained from table entry 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: , 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 . If it cannot find an unused index without violating the index or size constraints, it fails. 4.1.2 INS_IDX Parameters: , idx, Returns: success indicator Insert at CE-provided index. Check if provided index is unused. If it is, initialize it with , otherwise indicate error. 4.1.3 INS_IDX! Parameters: , idx, 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 (instead of reporting error). 4.1.4 DEL Parameters: , idx Returns: success indicator If table[idx] is used, delete table entry (making idx unused), otherwise report error. 4.1.5 DEL! Parameters: , idx Returns: success indicator Delete table[idx] if it exists, do nothing otherwise (never report error). 4.1.6 SET Parameters: , idx, Returns: success indicator If table[idx] exists, overwrite its content with provided , report error otherwise. 4.1.7 SET! Parameters: , idx, Returns: success indicator If table[idx] exists, overwrite its content with provided , create new entry with idx otherwise. 4.1.8 GET Parameters: , idx Returns: success indicator, 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 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 (used) entries in the table. N : N entries anywhere (used only in the INS_BLK operation) * refers to the data to initialize/set the specified table entries, or obtained from the specified table entries. 4.2.1 INS_BLK Parameters: , , Returns: success indicator, TBD 4.2.2 DEL_BLK Parameters: , Returns: success indicator Delete all entries specified by . TBD: how to handle errors? 4.2.3 SET_BLK Parameters: , , * Returns: success indicator Sets all elements specified by with the provided *. TBD: how to handle errors? 4.2.4 GET_BLK Parameters: , Returns: success indicator, * Obtains content of all entries specified by . 4.3 Associative (Key-Based) Operators In the following operators the following additional notations are used: : 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 . Search modes as described in section 2 (e.g., exact match, all that match prefix, longest prefix match, range, etc.) Data to be compared to the entry fields that are used as key. What is provided in depends on the and also on . 4.3.1 GET_IDX_BY_KEY Parameters: , , , Returns: success indicator, * Returns with the index of all entries identified by , and . 4.3.2 DEL_BY_KEY Parameters: , , , Returns: success indicator Deletes all entries identified by the , , and . 4.3.3 SET_BY_KEY Parameters: , , , , * Returns: success indicator Overwrites all entries identified by , , and . TBD: Some restrictions on mode will apply. 4.3.4 GET_BY_KEY Parameters: , , , Returns: success indicator, [*], * Returns with the content (and optionally the index) of all entries identified by the , , and . 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.