Chapter 5: Tables and Other Data Structures | Designing Embedded Communications Software

Earlier chapters specified that communications software modules use several tables for their operation. One of the functions of control plane software is building tables for data plane operations. This chapter details some of the tables and other data structures typically used in communications systems and discusses the related design aspects. While the term “table” implies a data structure involving contiguous memory, this chapter uses the term to also signify data structures with multiple entries, each of the same base type.

5.1 Tables

Tables are used for storing information referenced by the communications system. In a router, a forwarding table is used by the forwarding software/hardware to forward packets. In a frame relay switch, a connection table can provide the switch map from one Permanent Virtual Circuit (PVC) to another. Global configuration and port-related configuration for a device can be stored in tables. The key issues with tables are:

Tables are referenced for both reading and writing. So, both storage and access methods should be optimized for frequent references.
Tables can be stored in different parts of memory depending upon their application. For example, forwarding tables can be located in fast SRAM (Static Random Access Memory), while other tables such as configuration and statistics are stored in slower DRAM (Dynamic Random Access Memory).
Tables can also be organized according to the access method. For example, an IP forwarding table can be organized in the form of a PATRICIA tree. This structure is commonly used to optimize the access of the entries using the variable-length IP address prefix as an index into the table. A MAC filtering/forwarding table used in a Layer 2 switch often uses a hashing mechanism to store and access the entries. Hashing yields a fixed-length index into the table and is commonly performed by a bit-level operation on the six-byte destination MAC address in a frame.

5.1.1 Using Tables for Management

Configuration, control, status, and statistics information are four different types of management information that can be represented via tables.

Configuration—refers to the read–write (or read-only) information used to set the parameters and boundaries for the operation. For example, a password is a configuration parameter.
Control—indicates read–write information used to change the behavior of the communications software module. For example, enabling or disabling a protocol is treated as control.
Status—specifies read-only information that provides details about the current state of operation. For example, the operational status of an interface is considered a status variable.
Statistics—refers to read-only information that the module counts or monitors. For example, a variable that counts the number of packets received by the module is a statistics variable.

In the following discussion, the term “Configuration variables” represents both Configuration and Control variables.

The following sections outline some tables (using illustrative data structures) with information about their allocation, organization, and use.

Management Table Example

Management variables are often defined in a Management Information Base (MIB) which is specified by a body like the IETF. RFC 1213, specified by the IETF, defines an MIB for managing the configuration, control, status, and statistics of a system implementing IP forwarding. The MIB structure defined in this RFC is also known as MIB-II. A system implementing MIB-II can be managed by an external SNMP manager which understands the same MIB.

There are two types of configuration variables —standalone variables and those variables which are part of a table. In MIB-II, the variable ipForwarding indicates a variable which can be used to enable or disable IP forwarding. Standalone variables are also known as scalar variables or just scalars. The second type of variable is used to construct the elements of a table. These are the fields (or columns) of a table with multiple entries (or rows).

The segment in Listing 5.1 extracted from MIB-II details the IP address information for an interface. The table under consideration is the ipAddr Table. The ipAddrEntry is a row in the ipAddrTable. Each element of the SEQUENCE in ipAddrEntry represents an element in the address entry.

Listing 5.1: Management information base.

        ipAddrEntry OBJECT-TYPE               SYNTAX  IpAddrEntry               ACCESS  not-accessible               STATUS  mandatory               DESCRIPTION                       "The addressing information for one of this                       entity's IP addresses."               INDEX   { ipAdEntAddr }               ::= { ipAddrTable 1 }           IpAddrEntry ::=               SEQUENCE {                   ipAdEntAddr                       IpAddress,      // IP address of interface                   ipAdEntIfIndex                       INTEGER,        //Interface Identifier                   ipAdEntNetMask                       IpAddress,      //Net mask for interface                   ipAdEntBcastAddr                       INTEGER,        //Broadcast address used on interface                   ipAdEntReasmMaxSize                       INTEGER (0..65535) //Max Size of reassembled IP                                           //packet               }

The prefix “ipAdEnt" is used for all the fields of the table. The index to the table is the IP address as specified by ipAdEntAddr. The index will uniquely differentiate the various elements of the table. A tabular representation of the address table, with some entries, is shown in Table 5.1.

Table 5.1: Address table.
Addr	IfIndex	NetMask	BcastAddr	ReasmMaxSize
10.0.0.1	1	255.0.0.0	10.255.255.255	15000
20.0.0.1	2	255.0.0.0	20.255.255.255	18000
30.0.0.1	3	255.0.0.0	30.255.255.255	15000
40.0.0.1	4	255.0.0.0	40.255.255.255	11800

The Addr field is the IP address for the specific interface (identified by an ifIndex). The NetMask, BcastAddr and ReasmMaxSize are configurable fields in a table entry. These variables are also known as "Read–Write" variables as opposed to "Read Only" variables, which cannot be configured by the manager.

The developer can use these definitions for data structures required for the protocol. This can be done via grouping the scalar variables according to configuration, status, and statistics functions, providing a useful segmentation.

Note that the implementation may not follow the exact segmentation and variable set, i.e., the data structures may not be the same as the MIB definition. In the example above, an IP address table implementation may not be a separate table but be a part of an interface or port table. To the SNMP manager, the implementation is transparent, as long as the access and information are returned for the MIB table variables requested.

SNMP MIB tables should be used for completeness. When implementing data structures and their corresponding entries, always use the SNMP MIB tables as a checklist so that none of the variables are missed.