Partially-ordered cams used in ternary hierarchical address searching/sorting
First Claim
1. A content addressable memory (CAM) of a communications system utilizing ternary hierarchical addressing and associated address masks, said CAM comprising a plurality of address entries and associated address masks that are arranged in said CAM by mask number, with address entries having the highest mask number being located at address entry locations at the top of the CAM and address entries having the lowest mask number being located at address entry locations at the bottom of the CAM, said mask number being defined as the number of contiguous ones in an associated address mask.
1 Assignment
0 Petitions
Accused Products
Abstract
An apparatus and method that utilizes partial ordering of ternary hierarchical addresses and their associated masks entries in both binary and ternary content addressable memories (CAMs) for providing fast searches and while reducing address table size used in the processing of communication system (e.g., Internet Protocol (IP), layer-3 switches and ATM switches using E.164 addressing) addresses for identifying the source and destination of each digital packet data.
-
Citations
55 Claims
- 1. A content addressable memory (CAM) of a communications system utilizing ternary hierarchical addressing and associated address masks, said CAM comprising a plurality of address entries and associated address masks that are arranged in said CAM by mask number, with address entries having the highest mask number being located at address entry locations at the top of the CAM and address entries having the lowest mask number being located at address entry locations at the bottom of the CAM, said mask number being defined as the number of contiguous ones in an associated address mask.
-
13. An apparatus for storing a plurality of address entries and associated address masks in a communication system utilizing ternary hierarchical addressing and associated address masks, said apparatus comprising:
-
a binary CAM;
a binary-encoded ternary (BET) conversion means coupled to said binary CAM wherein said BET conversion means converts each ternary value into a corresponding BET value to form said address entries; and
wherein said plurality of address entries and associated address masks are arranged in said binary CAM by mask number, with address entries having the highest mask number being located at address entry locations at the top of the CAM and address entries having the lowest mask number being located at address entry locations at the bottom of the CAM, said mask number being defined as the number of contiguous ones in an associated address mask. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. A method for accelerating the routing of hierarchical addressing in a communication system which utilizes ternary hierarchical addressing and associated address masks, said method comprising the steps of:
-
(a) obtaining communication system hierarchical addresses and associated masks to form address entries; and
(b) storing said address entries in a content-addressable memory (CAM) by mask number wherein said mask number is defined as the number of contiguous ones in an associated address mask and wherein address entries having the highest mask number are stored in address entry locations at the top of the CAM and address entries having the lowest mask number being stored at address entry locations at the bottom of the CAM. - View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37)
-
-
38. A method for maintaining a sorted CAM to enable longest matches in a single search cycle when hierarchical addresses are added to, or deleted from, the CAM in a communication system utilizing hierarchical addresses and associated address masks, said method comprising the steps of:
-
(a) segmenting the CAM into blocks wherein each block corresponds to a single hierarchical mask and wherein said blocks are arranged in the CAM such that the highest hierarchical masks are located at the lowest CAM addresses and the lowest hierarchical masks are located at the highest CAM addresses;
(b) storing hierarchical addresses according to said block having a corresponding hierarchical mask; and
(c) tracking (1) the first address of each of said blocks (floor);
(2) the next free address of each of said blocks (nxtfree); and
(3) the size of each of said blocks. - View Dependent Claims (39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55)
-
Specification