Originally, all destinations were looked up in the RIB. Perhaps the first step in speeding routers was to have a separate RIB and FIB in main memory, with the FIB, typically with fewer entries than the RIB, being organized for fast destination lookup. In contrast, the RIB was optimized for efficient updating by routing protocols. Early uniprocessing routers usually organized the FIB as a
hash table, while the RIB might be a
linked list. Depending on the implementation, the FIB might have fewer entries than the RIB, or the same number. When routers started to have separate forwarding processors, these processors usually had far less memory than the main processor, such that the forwarding processor could hold only the most frequently used routes. On the early Cisco AGS+ and 7000, for example, the forwarding processor cache could hold approximately 1000 route entries. In an enterprise, this would often work quite well, because there were fewer than 1000 server or other popular destination subnets. Such a cache, however, was far too small for general Internet routing. Different router designs behaved in different ways when a destination was not in the cache.
Cache miss issues A
cache miss condition might result in the packet being sent back to the main processor, to be looked up in a
slow path that had access to the full routing table. Depending on the router design, a cache miss might cause an update to the fast hardware cache or the fast cache in main memory. In some designs, it was most efficient to invalidate the fast cache for a cache miss, send the packet that caused the cache miss through the main processor, and then repopulate the cache with a new table that included the destination that caused the miss. This approach is similar to an
operating system with
virtual memory, which keeps the most recently used information in physical memory. As memory costs went down and performance needs went up, FIBs emerged that had the same number of route entries as in the RIB, but arranged for fast lookup rather than fast update. Whenever a RIB entry changed, the router changed the corresponding FIB entry.
FIB design alternatives High-performance FIBs achieve their speed with implementation-specific combinations of specialized algorithms and hardware.
Software Various
search algorithms have been used for FIB lookup. While well-known general-purpose data structures were first used, such as
hash tables, specialized algorithms, optimized for IP addresses, emerged. They include: •
Binary tree •
Radix tree • Four-way trie •
Patricia tree A
multicore CPU architecture is commonly used to implement high-performance networking systems. These platforms facilitate the use of a
software architecture in which the high-performance packet processing is performed within a
fast path environment on dedicated cores, in order to maximize system throughput. A run-to-completion model minimizes OS overhead and latency.
Hardware Various forms of fast RAM and, eventually, basic
content-addressable memory (CAM) were used to speed lookup. CAM, while useful in layer 2 switches that needed to look up a relatively small number of fixed-length
MAC addresses, had limited utility with IP addresses having variable-length routing prefixes (see
Classless Inter-Domain Routing). Ternary CAM (CAM), while expensive, lends itself to variable-length prefix lookups. One of the challenges of forwarder lookup design is to minimize the amount of specialized memory needed, and, increasingly, to minimize the power consumed by memory. ==Distributed forwarding==