Fast Routing Table Lookup Using CAMs
Anthony J. McAuley & Paul Francis1 Bellcore, 445 South Street, Morristown, NJ 07962-1910, USA ( )
2.2: The General Routing Table Lookup Function Array the input to the lookup function as being a simple address. However, the input can be both source and destination address, and other information that can collectively be called Quality-of-Service (QOS) information. QOS includes such implicit path information as low cost, low delay, high throughput, low error rate, and so on. This information is combined with the address for the lookup function. QOS information may also be explicit, such as an long-distance Inter-exchange Carrier (IEC) indication. In this ca, the QOS information may take priority over the addressing information altogether, for instance becau a switch is only concerned about getting the packet to the appropriate IEC. This priority effect also exists with hierarchically structured address. Here, one part of an address takes priority over another part in the routing decision.
For the remainder of this paper, we consider an address to potentially include both source and destination address and the QOS information described above. The way the address are assigned in a network affect the routing table lookup function; therefore we next look at three general address structures. This covers the full range of address types that one is likely to e in practice. In particular, it covers a wider range than previous work on hardware-assisted routing table lookup [1].
3 Three Types of Address
iiqhsyThis ction considers two addressing structures (flat and hierarchical) and two hierarchical address assignment algorithms (fixed-position and variable-position).
3.1: Flat Address
where we simply assign each destination a unique address chon anywhere from the address space. This is en, for example, in ethernet address and for local connection identifiers. This method has the advantage of simplicity; but is limited to small networks, where routing table size is manageable.
3.2: Fixed-position Hierarchical Address
system, greatly reduce routing table size. Figure 1 shows a small example, reprenting a subt of ven nodes (ovals) visible to a switch (not shown) with three levels of hierarchy. The telephone numbers are the standard US 10-digit code: where the “X” digit is a wild card, meaning that any digit matches that position. Table 1 shows the corresponding routing table. This routing table has
address with four different fields: one 10-digit, two 6-
婴儿学英语
lookup, then, is a special ca of the hierachical lookup function where the masks are all 1’s.2013专四真题
Unlike the above example, just becau two address are at some level i of the addressing hierarchy does not mean that they have the same mask (as it does with for instance telephone address in the USA). For instance, subnet numbers in IP address can fall on arbitrary bit boundaries [5]. Notice also that the 1’s in the mask need not be contiguous. Indeed, there are known address assignment algorithms that can efficiently utilize the address space by taking advantage of variable-position (and in some cas non-contiguous) masks. Examples of this are kampai addressing [6], and variable-position subnet number assignment [7].
3.3: Variable-position Hierarchical Address
in the example of Figure 1, with ven areas (ovals) and three levels of hierarchy, but employing variable-position address (numbers inside the ovals). An area has the same locality for routing as the example of Figure 1.
later in the paper. (The other major difference is that Array variable-position masks are not necessarily contiguous. However, this difference only affects software-driven routing table lookup, and so is not a factor in this paper.)
4 Routing Table Lookup
This ction briefly reviews the general approaches to the lookup, using RAM, binary-CAM and ternary-CAM.
4.1: RAM-bad Lookup
会计学考研学校排名•Write an entry into a specific address
• Read an entry by its address.
There are a number of (software) algorithms ud to perform the lookup function using standard Random Access Memory (RAM).
A RAM can be perform the lookup in a single cycle if the data being arched (i.e. the packet address) is ud as a direct index (RAM address) into memory. In this ca, the size of a RAM is det
英语培训班招生简章ermined by the size of the arch field. For example, with a 16-bit arch field the RAM size is 64K (216) words. The number of words stored in a RAM has no effect on this size and cost. Thus, if there were only 256 words, each with a 16-bit arch field, the RAM must still have 64K words. The size and cost of the RAM when ud as a direct index grows exponentially with the arch field. With current RAM technology trends, a 24 bit arch pattern is the practical limit of an economic RAM-bad arch engine.
A linear arch is the most efficient algorithm for table lookup, requiring only one entry per active address. If the entries in the routing table are arched in order of largest mask first, then the first match will be the best match. Of cour, the linear arch runs in time O(N), where N is the number of entries, and so can take considerable time.
A faster approach is to form a tree arch: using a binary tree, a patricia tree, a trie tree, and so on [8]. In general, the trees can push the arch time towards log N. In the ca of the binary and patricia trees, the log ba is 2. The log ba can be incread, thus reducing arch time, but for sparly populated address spaces, this can result in unacceptable memory requirements [1]. Furthermore, even this arch time may be excessive. For a high speed switch, the allotted arch time can be measured in a few tens of instructions or less.
Under good conditions, a hash function can execute the lookup function in constant time [8], only slightly slower than direct access. The worst ca arch time, however, can be considerably wor than that of the tree arches. The performance is a function of the size of the hash memory and the number of address that must be arched
in a given time window (after which a hashed entry will be
related information in full. This direct access is fast Array (requires a single CAM read) and has low complexity. However, becau the size of the CAM word is limited (by cost), the associated information must be relatively small, currently the maximum economic size is around 100 bits.
If the amount of associated information is large (e.g. becau a large lower layer encapsulation address is required, or becau multiple outputs are listed in the ca of multicast forwarding), the CAM word is unable to store the related information. It therefore stores a unique index. The index is read, just as with direct access; but now the index is ud as an address to read a RAM. This indirect access requires both a CAM read and a RAM read. Indirect access is therefore slightly slower and more complex than direct access; but allows more associated information. 4.3: Ternary-CAM-bad Lookup
as a binary-CAM; but, while a binary-CAM stores one of two states (0 and 1) in each memory location (i.e. in each bit of a word), a ternary-CAM stores one of three states in each memory location (and also allows the arch pattern to be one of the three states). We reprent the three states by: 0, 1, and X. A ternary-CAM stores a don’t care condition in the extra state (X), effectively allowing each word its own personal mask register. For hierarchical address, the ternary-CAM allows the address and mask information to be combined in a single ternary word.
We will introduce algorithms to perform lookup using a ternary-CAM in Section 6.
4.4: Cost Comparison
bit of a:
•Binary-CAM is ten times the cost of a RAM.•Ternary-CAM is twice the cost of a binary-CAM.
Since the entries in general routing tables tend to be sparly populated over the (network) address space, direct indexing of the packetAddress into RAM is prohibitive. Therefore, it is necessary to either u a slower, software-driven arch of RAM, or go to a hardware-bad approach such as CAM (or a hybrid). Often, the time of the software-driven RAM arch is unacceptable. With higher speeds, at some point it is necessary to go with the faster and well-bounded arch time of a CAM.
Thus, although approximately an order of magnitude more expensive in terms of hardware, CAM-lookup solutions can offer superior performance compared to even the most sophisticated RAM-bad arch algorithms (careful management of the scarce CAM resources can
help reduce costs - e Appendix A).
through all the masks until a match is found (or if all el fails there is a default—a mask with all 0’s).
美将释放转基因蚊子In each cycle at most one match can occur. This is becau masks only match things in the hierarchy at the level of the mask and below. Since the most specific (lowest in the hierarchy) mask is tried first, and since the routing table lookup quence ends with the first match, we can have only one match. For fixed-position hierarchical address, the worst ca number of cycles is twice the number of hierarchy levels plus -read (Mask write, CAM arch, Mask write, CAM arch,....CAM Read).
If a new entry needs to be loaded into the routing table, the system adds the entry into the next free location. If an old entry needs to be removed from the table, the system lectively deletes that entry.
经典电影Method B2 is slower and more complex than method B1; but is better with fixed-position hierarchical address. The number of cycles is bounded by the number of different masks, which for fixed-position hierarchical address is equal to the depth of the address hierarchy. (Note that the number of masks with variable-position hierarchical address can be much larger than the hierarchy depth, so this method may not be good for such address.) Since the address hierarchy tends to be shallow (the international telephone network address is only four levels), the number of cycles is small3.
乔布斯演讲中文字幕Unfortunately, the system must keep track of where it is, load the mask register with a different value each cycle, and check for completion. A faster, simpler alternative, if suitable hardware is available, is method B3.
5.3: B3 (Single-Cycle Multiple-Logical CAM) and data bus; so, if only a single arch cycle is allowed, all words must receive the same arch pattern. (A single logical CAM may be compod of more than one chip; but the same mask is applied uniformly to all words). A single logical binary-CAM cannot provide hierarchical addressing with a single arch-read cycle. This ction describes the u of multiple logical CAMs for hierarchical address lookup with a single arch-read cycle. This is particularly uful for fixed-position hierarchical addressing, such as exists in the current telephon
e numbering scheme.
When address are hierarchical, two problems prevent
sunshine
table lookup in one cycle with a single logical CAM: hierarchy depth, becau method B2 begins with the larger masks - and larger masks are for frequently ud: 1) nearby destinations that are low in the hierarchy, or 2) high access links that are higher in the hierarchy, but us more detailed information.
