Method and system for hash table based routing via table and prefix aggregation

Abstract

Aspects of a method and system for hash table based routing via table and prefix aggregation are provided. Aspects of the invention may enable aggregating prefixes of varying lengths into a single hash table, wherein each entry in the hash table comprises one or more encoded bits to uniquely identify said prefixes. Additionally, an entry in a hash table may be formatted based on a length of one or more representations of said prefixes in the entry. Aggregating prefixes into a hash table may comprise truncating the prefixes to a common length. In this regard, the encoded bits may indicate the length of the prefixes prior to and/or subsequent to truncation. Additionally, the encoded bits may represent bits removed from the prefix during truncation. In this regard, an encoded bit may represent a possible combination of removed bits and may be asserted when the removed bits are equal to that combination.

1. A method for data processing, the method comprising:
 performing by one or more processors or circuits in a network device:
 aggregating prefixes of varying lengths in a hash table, wherein each entry in said hash table comprises one or more encoded bits used to uniquely identify prefixes associated with said each entry; 
 routing data in a network utilizing said hash table, wherein one or more of: a number of fields in said each entry in said hash table, a size of one or more fields in said each entry in said hash table, and an ordering of fields in said each entry in said hash table is controlled based on a length of said prefixes associated with said each entry. 
 
 
     
     
       2. The method according to  claim 1 , wherein:
 said each entry in said hash table comprises a multi-purpose field; and 
 the format of said multi-purpose field for a particular entry is based on a length of one or more prefixes associated with said particular entry. 
 
     
     
       3. The method according to  claim 1 , wherein said aggregation comprises truncating said prefixes to a common length. 
     
     
       4. The method according to  claim 3  wherein said encoded bits indicate a length of said prefixes prior to said truncation. 
     
     
       5. The method according to  claim 3 , wherein said encoded bits indicate a length of said truncated prefixes. 
     
     
       6. The method according to  claim 3 , wherein said encoded bits indicate rounded-off bits removed during said truncation. 
     
     
       7. The method according to  claim 6 , wherein each of said encoded bits corresponds to a possible combination of said rounded-off bits and is asserted if a corresponding combination of rounded-off bits is represented. 
     
     
       8. The method according to  claim 3 , comprising:
 defining a set of ‘m’ prefix lengths, l 1 , . . . , l m , where ‘m’ is a positive integer greater than 1; and 
 truncating prefixes longer than or equal to l i  and shorter than l i+1  to length l i  , wherein l i  and l i+1  represent two consecutive lengths comprising said set, and ‘i’ is a positive integer greater than or equal to 1 and less than said integer ‘m’. 
 
     
     
       9. The method according to  claim 1  comprising:
 translating each of said prefixes as a coefficient set of a polynomial; and 
 calculating a remainder and a quotient resulting from a modulo 2 division of said polynomial by a generator polynomial. 
 
     
     
       10. The method according to  claim 9 , comprising representing said prefixes in said single hash table by storing said quotient in a memory location indexed by said remainder. 
     
     
       11. The method according to  claim 9 , comprising truncating each of said translated prefixes to a common length prior to said calculation of said quotient and said remainder. 
     
     
       12. The method according to  claim 1 , wherein said prefixes correspond to a network address portion of an IP address. 
     
     
       13. A non-transitory computer-readable medium having stored thereon, a computer program having at least one code section for processing data, the at least one code section being executable by a computer for causing the computer to perform steps comprising:
 aggregating prefixes of varying lengths in a hash table, wherein each entry in said hash table comprises one or more encoded bits used to uniquely identify prefixes associated with said each entry; 
 routing data in a network utilizing said hash table, wherein one or more of a number of fields in said each entry in said hash table, a size of one or more fields in said each entry in said hash table, and an ordering of fields in said each entry in said hash table is controlled based on a length of said prefixes associated with said each entry. 
 
     
     
       14. The non-transitory computer-readable medium according to  claim 13 , wherein:
 said each entry in said hash table comprises a multi-purpose field; and 
 the format of said multi-purpose field for a particular entry is based on a length of one or more prefixes associated with said particular entry. 
 
     
     
       15. The non-transitory computer-readable medium according to  claim 13 , wherein said aggregation comprises truncating said prefixes to a common length. 
     
     
       16. The non-transitory computer-readable medium according to  claim 15 , wherein said encoded bits indicate a length of said prefixes prior to said truncation. 
     
     
       17. The non-transitory computer-readable medium according to  claim 15 , wherein said encoded bits indicate a length of said truncated prefixes. 
     
     
       18. The non-transitory computer-readable medium according to  claim 15 , wherein said encoded bits indicate rounded-off bits removed during said truncation. 
     
     
       19. The non-transitory computer-readable medium according to  claim 18 , wherein each of said encoded bits corresponds to a possible combination of said rounded-off bits and is asserted if a corresponding combination of rounded-off bits is represented. 
     
     
       20. The non-transitory computer-readable medium according to  claim 15 , wherein said at least one code section comprises code that enables:
 defining a set of ‘m’ prefix lengths, l 1 , . . ., l m , where ‘m’ is a positive integer greater than 1; and 
 truncating prefixes longer than or equal to l i  and shorter than l i+1  to length l i  , wherein l i  and l i+1  represent two consecutive lengths comprising said set, and ‘i’ is a positive integer greater than or equal to 1 and less than said integer ‘m’. 
 
     
     
       21. The non-transitory computer-readable medium according to  claim 13  wherein said at least one code section comprises code that enables:
 translating each of said prefixes as a coefficient set of a polynomial; and 
 calculating a remainder and a quotient resulting from a modulo 2 division of said polynomial by a generator polynomial. 
 
     
     
       22. The non-transitory computer-readable medium according to  claim 21 , wherein said at least one code section comprises code that enables representing said prefixes in said single hash table by storing said quotient in a memory location indexed by said remainder. 
     
     
       23. The non-transitory computer-readable medium according to  claim 21 , wherein said at least one code section comprises code that enables truncating each of said translated prefixes to a common length prior to said calculation of said quotient and said remainder. 
     
     
       24. The non-transitory computer-readable medium according to  claim 13 , wherein said prefixes correspond to a network address portion of an IP address. 
     
     
       25. A system for data processing, the system comprising:
 one or more processors and/or circuits for use in a network device, wherein said one or more processors and/or circuits are operable to:
 aggregate prefixes of varying lengths in a hash table, wherein each entry in said hash table comprises one or more encoded bits used to uniquely identify prefixes associated with said each entry; 
 route data in a network utilizing said hash table, wherein one or more of a number of fields in said each entry in said hash table, a size of one or more fields in said each entry in said hash table, and an ordering of fields in said each entry in said hash table is controlled based on a length of said prefixes associated with said each entry. 
 
 
     
     
       26. The system according to  claim 25 , wherein:
 said each entry in said hash table comprises a multi-purpose field; and 
 the format of said multi-purpose field for a particular entry is based on a length of one or more representations of said prefixes associated with said particular entry. 
 
     
     
       27. The system according to  claim 25 , wherein said aggregation comprises truncating said prefixes to a common length. 
     
     
       28. The system according to  claim 25 , wherein said encoded bits indicate a length of said prefixes prior to said truncation. 
     
     
       29. The system according to  claim 28 , wherein said encoded bits indicate a length of said truncated prefixes. 
     
     
       30. The system according to  claim 28 , wherein said encoded bits indicate rounded-off bits removed during said truncation. 
     
     
       31. The system according to  claim 30 , wherein each of said encoded bits corresponds to a possible combination of said rounded-off bits and is asserted if a corresponding combination of rounded-off bits is represented. 
     
     
       32. The system according to  claim 28 , wherein said one or more processors are operable to:
 define a set of ‘m’ prefix lengths, l 1 , . . . , l m , where ‘m’ is a positive integer greater than 1; and 
 truncate prefixes longer than or equal to l i  and shorter than l i+1  to length l i  , wherein l i  and l i+1  represent two consecutive lengths comprising said set, and ‘i’ is a positive integer greater than or equal to 1 and less than said integer ‘m’. 
 
     
     
       33. The system according to  claim 25 , wherein said one or more processors are operable to:
 translate each of said prefixes as a coefficient set of a polynomial; and 
 calculate a remainder and a quotient resulting from a modulo 2 division of said polynomial by a generator polynomial. 
 
     
     
       34. The system according to  claim 33 , wherein said one or more processors are operable to represent said prefixes in said single hash table by storing said quotient in a memory location indexed by said remainder. 
     
     
       35. The system according to  claim 33 , wherein said one or more processors are operable to truncate each of said translated prefixes to a common length prior to said calculation of said quotient and said remainder. 
     
     
       36. The system according to  claim 25 , wherein said prefixes correspond to a network address portion of an IP address.