TNETX15AE Datasheet, PDF (38/78 Pages) Texas Instruments – ADDRESS-LOOKUP DEVICE

TNETX15AE
ADDRESS-LOOKUP DEVICE
SPWS041A – AUGUST 1997 – REVISED OCTOBER 1997
PRINCIPLES OF OPERATION
operating logic arbitration (continued)
INIT
Decreasing
Priority
LKUP
DEL
ADD
REG
FIND
AGE
Figure 4. Logic-Operation Priorities
One logic operation can interrupt a lower-priority logic operation to acquire the bus. For example, an LKUP
operation interrupts an ADD operation.
For the case of ADD and DEL (with the same priority), the arbiter grants the bus to the first logic operation that
requests it. It then grants an uninterruptable bus (unless by a LKUP) to that logic operation until that logic
operation is completed. If both ADD and DEL request the bus at the same time, the bus is granted to ADD. This
ensures that ADD is not interrupted by a DEL operation and vice versa. This hierarchy explains why a host
request for access to RAM completes with some variability — there may be higher-priority operations accessing
RAM at that instant.
lookup algorithm
The TNETX15AE device uses a table-based lookup algorithm to provide deterministic lookups with less than
2⁴⁸ memory words. The tables are hierarchical and are linked to the lower tables by threads. Each table can
thread to several different tables in the hierarchy. The lowest table in the hierarchy (leaf) does not point to
anything and contains information about the address to be matched.
Each level in the hierarchy is assigned to a specific range of bits in the address. The bits in the range are used
as an offset within the table at each level. If a thread exists at that offset, the TNETX15AE follows that thread.
The TNETX15AE matches an address when it finds a complete thread to a leaf. The thread structure is shown
in Figure 5.
The first level (root level) has only one table from which it can branch out to 2^N possible tables. N is the number
of bits compared at a given time. Each additional table in the hierarchy branches down to 2^N other possible
tables. The second level contains 2^N table and 2^2N threads. The third level contains 2^2N tables and 2^3N threads,
and so on.
Because of this exponential growth, the threads and the amount of possible paths at each level soon overtake
the number of addresses required. If this growth were to go unchecked with an N of 5, the third level would
contain 1,024 tables and 32,768 threads. If only 1024 addresses are required, there are more tables allocated
than needed, and most contain NULL pointers.
38
• POST OFFICE BOX 655303 DALLAS, TEXAS 75265