Databases key to efficient NPU routing classification

Different application databases require significantly different resources for the device storing the databases. These requirements include the depth of array allocated to the application, size of data (that is, the width of the key) and type of search desired, as well as frequency of access, insertions and deletions.

Although multiple databases simplify the support of multiple services, they further complicate the classification task. A router has the added responsibility of looking at multiple databases when determining whether or not to forward the packet, bill it and which level of quality-of-service to deliver.

Techniques to access multiple databases for search, classification and management tasks are evolving to keep pace with the proliferation of databases. Some coprocessors support the emerging reality of managing multiple databases by providing control in hardware instead of software.

To increase performance, the coprocessor device instruction includes a field for selecting a database, enabling dynamic database selection on each operation of the coprocessor. This provides a significant savings in application management and network processing to address different applications.

However, dynamic database management in software dramatically streamlines multiple database searches. That's because it allows for per-instruction selection of the appropriate database without requiring specialized bit manipulation of the key by the network processor.

There are structures within some IP coprocessors that narrow the search to the appropriate database to conserve power consumption and speed access to the data. This refined selection function removes potential overhead when creating the selection key. The result is faster database selection and increased functionality with better utilization of entries.

This next-generation dynamic database management also helps streamline important database maintenance activities. There are three basic categories for databases: exact match, longest prefix match and access control list. Each requires different driver capabilities to meet its unique maintenance needs.

Exact match databases require an exact match with the stored data to register a hit. Used for Layer 2 MAC tables and static address access lists, exact match databases have update rates on the order of hundreds per second.

Learning — creating and updating entries to the database — and aging capabilities are used to update entries in an exact match database. During learning, new entries are added to any available empty location in the database. Fast IP coprocessors rely on a next-free-address register that contains the address of the next empty location. Any writes or deletions to the database will require an update of that register.

Aging is used to remove stale entries and free more space as the network topology changes over time. The data plane must track activity for each entry. However, since the exact timing of aging is noncritical, it is done in the background by the control plane.

Longest prefix match (LPM) database maintenance is used for a forwarding information base (FIB), which updates at a rate of about 100 per second, with the updates coming from administration information being exchanged between routers. In worst-case route flap conditions, the rate can be as high as 5,000 a second. The LPM database stores data by category (specifically, the length of the subnet mask).

There are only a few entries for each of the prefixes on the ends, but prefix length 24 has almost 100,000 entries. As a result, the prefix distribution in the database is nonlinear, and the prefix groups must be allocated relative to the size of the number of entries in the prefix grouping.

Critical additions

A crucial task is adding new information to the LPM database. The control plane must determine to which prefix category new additions belong and then secure a free location in the search engine for the entry. Some search engine vendors offer costly hardware-based solutions for LPM database maintenance. However, they significantly add to device cost and complexity by as much as 30 percent.

A host processor of 300 Mips can handle this operation in software in less than 1 percent processing bandwidth. Thus, an alternate approach is to implement LPM maintenance in software. Not only is this method cost-effective, but more importantly it offers greater flexibility in database maintenance as more services and addresses are added.

The FIB can be broken into weight classes corresponding to each prefix. Therefore, an update will be a simple write to a free entry in the weight class of the target prefix. If the weight class segment is full, then the software driver for the IP coprocessor follows these steps:

• Locate the nearest weight class with a free entry.
• Move the free entry to the top or bottom of the source weight class where the free entry currently resides by copying the contents of the entry at the boundary to the free entry.
• Move the boundary of the weight class so as to "transfer" the free entry to the adjacent weight class. Then move the contents of the occupied location at the top or bottom to the top or the bottom of the source weight class.
• Continue transfer or "shuffle" the free location in this manner until it reaches desired weight class where it is needed.
• The final step is to write the new entry into the target weight class.
• Typically, the FIB is kept in a shadow copy in the host DRAM and only writes are done to the search engine. Therefore, the worst case number of writes is equal to half the number of prefixes and the typical case will be only three or four.

A classifier or policy database is composed of a set of rules or policies. Maintenance for the access control logic database is quite different from that for LPM and exact match databases. With access control logic all entries are manually entered, typically by the IT manager, and are updated quite infrequently. In fact, it is considered a near-static database with very low dynamic update rates — on the order of one change per second. Consequently, database maintenance is not a pressing concern.

As services become a major differentiator for service carriers, classification and forwarding are becoming much more complex tasks and more databases are required to support these services. Some IP coprocessors provide next-generation capabilities that are designed to support the high-performance, policy-based requirements for future applications that will undoubtedly have numerous databases running at OC-192 and OC-768 line rates.

See related chart