Partially ordered cams used in ternary hierarchical address searching/sorting

• US 6,289,414 B1
• Filed: 10/08/1998
• Issued: 09/11/2001
• Est. Priority Date: 10/08/1998
• Status: Expired due to Term

• Current Assignee: Round Rock Research LLC
• Original Assignee: Music Semiconductors, Inc.
• Inventors: Feldmeier, David, Arnold, Tyler
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): Anderson, Matthew D.
• Application Number:
  US09/168,445
• Time in Patent Office: 1,069 Days
• Field of Search: 711/108, 711/117, 711/202, 711/219, 710/65, 712/224
• US Class Current: 711/108
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: H04L 45/7453 using hashing

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.

Claims

1. 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.

2. The method of claim 1 wherein if a block is full when an entry is trying to be made into said full block, said method further comprises the step of locating the closest block having at least one free memory space, thereby defining a non-full block.

3. The method of claim 2 wherein said non-full block is located at higher CAM addresses, thereby defining blocks below said full block.

4. The method of claim 3 further comprising the steps of:

(a) moving the contents of said floor of said non-full block to said nxtfree of said non-full block;

(b) for every block between said non-full block and said full block, in decreasing CAM address order, sequentially moving the contents of said floor of the upper block to said floor of the next lower block so that said floor of said block directly below said full block is empty, thereby defining an empty location;

(c) incrementing said floor of each of said blocks below said full block to the next higher CAM address and incrementing said nxtfree of each of said blocks below said full block to the next higher CAM address; and

(d) moving the entry into said empty location.

5. The method of claim 2 wherein said non-full block is located at lower CAM addresses, thereby defining blocks above said full block.

6. The method of claim 5 further comprising the steps of:

(a) moving the contents of the CAM address location that is directly above said nxtfree of the block directly below said non-full block to the CAM address location that is directly above said floor of said block that is directly below said non-full block;

(b) for every block between said non-full block and said full block, in increasing CAM address order, sequentially moving the contents of the CAM address location that is directly above said nxtfree of the directly lower block and move said contents into the CAM address location directly above said floor of said lower block so that CAM address location directly above said floor of said full block is empty, thereby defining an empty location;

(c) decrementing said floor of each of said blocks above said full block to the next lower CAM address and decrementing said nxtfree of each of said blocks above said full block to the next lower CAM address; and

(d) moving the entry into said empty location which is defined as a new floor for said full block.

7. The method of claim 2 further comprising the step of deleting an entry from said CAM, said deleting step comprising:

(a) moving a last entry in a block into the CAM address location of said entry to be deleted; and

(b) decrementing said nxtfree of said block to CAM address location of said last entry.

8. The method of claim 6 further comprising the step of deleting an entry from said CAM, said deleting step comprising:

(a) moving a last entry in a block into the CAM address location of said entry to be deleted; and

(b) decrementing said nxtfree of said block to CAM address location of said last entry.

9. The method of claim 1 further including the step of searching the CAM for a single hierarchical network address entry having a mask, said single address entry searching comprising the steps of:

(a) logically ANDing the network address and its respective mask to form a first CAM entry portion;

(b) logically ANDing the one'"'"'s complement of the network address and its respective mask to form a second CAM entry portion;

(c) loading said first and second CAM entry portions into a first register of said CAM; and

(d) comparing said first and second CAM entry portions with said stored hierarchical addresses.

10. The method of claim 1 wherein said step of storing hierarchical addresses according to said block having a corresponding hierarchical mask comprises the insertion of each hierarchical address in said block in a non-sequential order.

11. The method of claim 7 further comprising the step of interleaving steps of said maintaining a sorted CAM between steps of a searching method of said CAM in order to maintain said sorted CAM with minimal loss in performance whenever said communication system is operating at full bandwidth.

12. The method of claim 8 further comprising the step of interleaving steps of said maintaining a sorted CAM between steps of a searching method of said CAM in order to maintain said sorted CAM with minimal loss in performance whenever said communication system is operating at full bandwidth.

13. The method of claim 1 wherein said communication system is a telecommunication system.

14. The method of claim 1 wherein said communication system is a data communication system.

15. The method of claim 1 wherein said communication system is a network system.

16. The method of claim 15 wherein said network system is the Internet Protocol (IP) network.

17. The method of claim 15 wherein said network comprises layer-3 switches.

18. The method of claim 15 wherein said network comprises asynchronous transfer mode (ATM) switches using E.164 addressing.

19. 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;

said CAM being a binary CAM; and

said CAM further comprising binary-encoding ternary (BET) conversion means for converting each ternary value in said ternary hierarchical address into a corresponding BET value to form said address entries, said each ternary value being represented by first and second bits of said corresponding BET value as follows;

20. The CAM of claim 19 wherein said first bit location and said second bit location are separated by a predetermined number of bit locations from each other.

21. The CAM of claim 20 wherein said predetermined number of bit locations is 32 based on 64-bit wide CAM entry size.

22. 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; and

wherein said BET conversion means generates a BET value comprising a first bit and a second bit for every ternary value of the ternary hierarchical address as follows;

23. The apparatus of claim 22 wherein said first bit location and said second bit location are separated by a predetermined number of bit locations from each other.

24. The apparatus of claim 23 wherein said predetermined number of bit locations is 32 based on 64-bit wide CAM entry size.

25. The apparatus of claim 24 wherein said communication system is a telecommunication system.

26. The apparatus of claim 24 wherein said communication system is a data communication system.

27. The apparatus of claim 24 wherein said communication system is a network system.

28. The apparatus of claim 27 wherein said network system is the Internet Protocol (IP) network.

29. The apparatus of claim 27 wherein said network comprises layer-3 switches.

30. The apparatus of claim 27 wherein said network comprises asynchronous transfer mode (ATM) switches using E.164 addressing.

31. 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;

wherein said step of obtaining communication system hierarchical addresses and associated masks comprises converting the ternary hierarchical addresses and associated address masks into binary-encoded ternary (BET) to form said address entries and wherein said CAM is a binary CAM; and

wherein each ternary hierarchical address and associated mask comprises a plurality of ternary values and wherein said step of converting the ternary hierarchical addresses and associated address masks into BET comprises the conversion of each of the ternary values into first and second binary-encoded ternary (BET) bits as follows;

32. The method of claim 31 wherein said step of storing said address entries in said binary CAM comprises storing said first bit in a first bit location in an upper location of said address entry location and wherein said second bit is stored in a second bit location in a lower portion of said address entry location.

33. The method of claim 32 wherein said first bit location and said second bit location are separated by a predetermined number of bit locations from each other.

34. The method of claim 33 wherein said predetermined number of bit locations is 32 based on 64-wide CAM entry size.