Almost all routers use TCAM to speed up table lookup. Due to the need of performing...

Transcribed Image Text:

Almost all routers use TCAM to speed up table lookup. Due to the need of performing maximum sequencing matching, we need to organize the prefix entries in the lookup table according to their lengths (shortest one at the top). Assume we have a TCAM which can hold 256 prefix entries. The current occupancy looks like the one shown in the figure below. The lengths of all prefixes in the network range from 10 to 20. To simplify the discussion, assume there are 10 prefixes of each length group at the moment. (a) Now suppose we want to add one more prefix with length 11 to the lookup table. Obviously we need to re-arrange the locations of some entries in the table. What is the minimum number of entries we need to rearrange? (b) Rearrangement takes time. Can you suggest a simple way to store prefixes in the table so that we can significantly reduce the number of re- arranged entries when we need to add one entry to the table. Prefixes (length 10) (10 entries) Prefixes (length 11) (10 entries) : Prefixes (length 20) (10 entries) Empty Entries : Almost all routers use TCAM to speed up table lookup. Due to the need of performing maximum sequencing matching, we need to organize the prefix entries in the lookup table according to their lengths (shortest one at the top). Assume we have a TCAM which can hold 256 prefix entries. The current occupancy looks like the one shown in the figure below. The lengths of all prefixes in the network range from 10 to 20. To simplify the discussion, assume there are 10 prefixes of each length group at the moment. (a) Now suppose we want to add one more prefix with length 11 to the lookup table. Obviously we need to re-arrange the locations of some entries in the table. What is the minimum number of entries we need to rearrange? (b) Rearrangement takes time. Can you suggest a simple way to store prefixes in the table so that we can significantly reduce the number of re- arranged entries when we need to add one entry to the table. Prefixes (length 10) (10 entries) Prefixes (length 11) (10 entries) : Prefixes (length 20) (10 entries) Empty Entries :