Updating cam arrays using prefix length distribution prediction

1. A method for ordering a plurality (P) of entries having various prefix lengths for storage in a number (T) of available storage locations in a content addressable memory (CAM) array according to the prefix lengths, the method comprising:

selecting a first number (N) of the entries, wherein N<P;

generating a distribution graph of the prefix lengths of the first N entries;

for each unique prefix length, allocating a corresponding subset of the T storage locations in the CAM array according to the distribution graph; and

storing all P entries in the corresponding allocated storage locations.

2. The method of claim 1 , wherein increasing numerical CAM storage location addresses correspond to entries having decreasing prefix lengths.

3. The method of claim 1 , wherein the number N is selected in response to a relationship between numbers of entries selected for generating the distribution graph and associated errors in predicting the prefix lengths of the remaining entries.

4. The method of claim 1 , wherein all entries having the same prefix length are stored in contiguous storage locations of the CAM array.

5. The method of claim 1 , wherein the distribution graph indicates how many of the first N entries have each of the prefix lengths.

6. The method of claim 1 , wherein the distribution graph predicts how many of the P entries have each of the prefix lengths.

7. The method of claim 1 , wherein the generating comprises:

identifying the prefix length of each of the first N entries;

for each of the identified prefix lengths, determining how many of the first N entries have the prefix length; and

calculating percentages of the first N entries that have each of the identified prefix lengths.

8. The method of claim 7 , wherein each percentage is expressed as PLD(i)=M(i)/N, where PLD(i) is the percentage of the N entries that have a prefix length of i, M(i) is the number of the first N entries that have the prefix length of i, and i is an integer greater than zero.

9. The method of claim 8 , wherein the allocating comprises:

for each unique prefix length, calculating the corresponding subset of the P storage locations as NH(i)=PLD(i)*T, where NH(i) is the number of storage locations allocated to store entries having a prefix length of i.

10. The method of claim 1 , wherein the selecting comprises:

storing the first N entries in a buffer that is separate from the CAM array.

11. A processor configured to order a plurality (P) of entries having various prefix lengths for storage in a number (T) of available storage locations in a content addressable memory (CAM) array according to the prefix lengths, the processor comprising:

means for selecting a first number (N) of the entries, wherein N<P;

means for generating a distribution graph of the prefix lengths of the first N entries;

for each unique prefix length, means for allocating a corresponding subset of the T storage locations in the CAM array according to the distribution graph; and

means for storing all P entries in the corresponding allocated storage locations.

12. The processor of claim 11 , wherein increasing numerical CAM storage location addresses correspond to entries having decreasing prefix lengths.

13. The processor of claim 11 , wherein all entries having the same prefix length are stored in contiguous storage locations of the CAM array.

14. The processor of claim 11 , wherein the number N is selected in response to a relationship between numbers of entries selected for generating the distribution graph and associated errors in predicting the prefix lengths of the remaining entries.

15. The processor of claim 11 , wherein the distribution graph indicates how many of the first N entries have each of the prefix lengths.

16. The processor of claim 11 , wherein the distribution graph predicts how many of the P entries have each of the prefix lengths.

17. The processor of claim 11 , wherein the means for generating comprises:

means for identifying the prefix length of each of the first N entries;

for each of the identified prefix lengths, means for determining how many of the first N entries have the prefix length; and

means for calculating percentages of the first N entries that have each of the identified prefix lengths.

18. The processor of claim 17 , wherein each percentage is expressed as PLD(i)=M(i)/N, where PLD(i) is the percentage of the N entries that have a prefix length of i, M(i) is the number of the first N entries that have the prefix length of i, and i is an integer greater than zero.

19. The processor of claim 18 , wherein the means for allocating calculates, for each unique prefix length, the corresponding subset of the P storage locations as NH(i)=PLD(i)*T, where NH(i) is the number of storage locations allocated to store entries having a prefix length of i.

20. The processor of claim 11 , wherein the means for selecting stores the first N entries in a buffer that is separate from the CAM array.

21. A system for storing a plurality (P) of entries according to their prefix lengths, comprising:

a data input to receive the plurality of entries;

a content addressable memory (CAM) array having a number (T) of storage locations, each for storing a corresponding one of the entries;

a buffer to store a first number (N) of the received entries, wherein N<P;

logic configured to generate a distribution graph of the prefix lengths of the first N entries, wherein the distribution graph indicates how many of the first N entries have each prefix length and predicts how many of the P entries have each prefix length; and

a processor configured to allocate, for each unique prefix length, a corresponding subset of the T storage locations in the CAM array for storing entries that have the unique prefix length.

22. The system of claim 21 , wherein increasing numerical CAM storage location addresses correspond to entries having decreasing prefix lengths.

23. The system of claim 21 , wherein all entries having the same prefix length are stored in contiguous storage locations of the CAM array.

24. The system of claim 21 , wherein the number N is selected in response to a relationship between numbers of entries selected for generating the distribution graph and associated errors in predicting the prefix lengths of the remaining entries.

25. The system of claim 21 , wherein the logic generates the distribution graph by:

identifying the prefix length of each of the first N entries;

for each of the identified prefix lengths, determining how many of the first N entries have the prefix length; and

calculating percentages of the first N entries that have each of the identified prefix lengths.

26. The system of claim 25 , wherein each percentage is expressed as PLD(i)=M(i)/N, where PLD(i) is the percentage of the N entries that have a prefix length of i, M(i) is the number of the first N entries that have the prefix length of i, and i is an integer greater than zero.

27. The system of claim 26 , wherein the processor calculates, for each unique prefix length, the corresponding subset of the P storage locations as NH(i)=PLD(i)*T, where NH(i) is the number of storage locations allocated to store entries having a prefix length of i.