The All-New Switch Book: The Complete Guide to LAN Switching Technology, Second Edition

2.3. Implementing the Bridge Address Table

Much of the performance of a bridge is dependent on the design of the address table and the table search algorithm. In this section, we look at some of the practical design issues facing bridge architects. Readers with no interest in product implementation can safely skip this entire section with no loss of continuity (even though this is really interesting stuff!).

2.3.1. Table Operations

There are three operations that need to be performed on the Bridge Address Table: Destination Address lookup, Source Address learning, and entry aging. As discussed in section 2.1.5, this is also the order of importance of the operations. The architecture and organization of the address table are intimately coupled to the search algorithm being used; they are designed as one. Considering the priority of operations, the table design should be optimized for fast, real-time lookup, at the expense of slower and/or more complex update and aging algorithms if need be.

As a counterexample of this approach, consider a design employing a linear search table (i.e., a non-ordered, simple linear list of address and port mappings). With this design, it is very easy to add new entries; new entries may be simply added to the end of the list in a single operation. However, the lookup algorithm requires (in the worst case) inspecting every entry in the table, a tedious and time-consuming operation. Thus, a linear organization is an example of poor Bridge Address Table ...