Method and system for hash table based routing via a prefix transformation
Aspects of a method and system for hash table based routing via prefix transformation are provided. Aspects of the invention may enable translating one or more network addresses as a coefficient set of a polynomial, and routing data in a network based on a quotient and a remainder derived from the coefficient set. In this regard, the quotient and the remainder may be calculated via modulo 2 division of the polynomial by a primitive generator polynomial. In one example, the remainder may be calculated with the aid of a remainder table. The primitive generator polynomial may be x 16 +x 8 +x 6 +x 5 +x 4 +x 2 +1. Additionally, entries in one or more hash tables may comprise a calculated quotient and may be indexed by a calculated remainder. In this manner, the hash tables may be accessed to determine a longest prefix match for the one or more network addresses. The hash tables may comprise 2 deg(g(x)) sets, where deg(g(x)) is the degree of the primitive generator polynomial. Accordingly, the hash tables may be set associative and multiple entries may be indexed by the same remainder. Furthermore, entries in the hash tables may comprise a next hop address utilized in routing network traffic.
1. A method for processing data, the method comprising:
translating a network address as a plurality of coefficient sets of a corresponding plurality of polynomials;
deriving a plurality of quotient and remainder pairs from said plurality of coefficient sets;
accessing, in parallel, a plurality of hash tables;
determining a longest prefix match for said network address based on which of said hash tables return at least one match for at least one of said quotient and remainder pairs; and
routing data in a network based on said longest prefix match.
2. The method according to claim 1 , comprising deriving said plurality of quotient and remainder pairs via modulo 2 division of said plurality of polynomials by a primitive generator polynomial.
3. The method according to claim 2 , wherein said primitive generator polynomial comprises the polynomial x 16 +x 8 +x 6 +x 5 +x 4 +x 2 +1.
4. The method according to claim 1 , wherein said plurality of hash-tables are set-associative.
5. The method according to claim 1 , wherein each entry in said plurality of hash tables comprises a quotient, when said quotient is greater than 0.
6. The method according to claim 1 , wherein each entry in said plurality of hash tables comprises a next hop address.
7. The method according to claim 1 , wherein each of said plurality of hash tables comprises 2 deg(g(x)) sets, where deg(g(x)) is the degree of said primitive generator polynomial.
8. The method according to claim 1 , wherein multiple entries of each of said plurality of hash tables share a common index.
9. The method according to claim 1 , wherein a remainder of one or more of said quotient and remainder pairs is calculated utilizing a remainder table.
10. 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 machine for causing the machine to perform steps comprising:
translating a network address as a plurality of coefficient sets of a corresponding plurality of polynomials;
deriving a plurality of quotient and remainder pairs from said plurality of coefficient sets;
accessing, in parallel, a plurality of hash tables;
determining a longest prefix match for said network address based on which of said hash tables return at least one match for at least one of said quotient and remainder pairs; and
routing data in a network based on said longest prefix match.
11. The non-transitory computer readable medium according to claim 10 , wherein said at least one code section comprises code that enables deriving said plurality of quotient and remainder pairs via modulo 2 division of said plurality of polynomials by a primitive generator polynomial.
12. The non-transitory computer readable medium according to claim 11 , wherein said primitive generator polynomial comprises the polynomial x 16 +x 8 +x 6 +x 5 +x 4 +x 2 +1.
13. The non-transitory computer readable medium according to claim 10 , wherein said plurality of hash-tables are set-associative.
14. The non-transitory computer readable medium according to claim 10 , wherein each entry in said plurality of hash tables comprises a quotient, when said quotient is greater than 0.
15. The non-transitory computer readable medium according to claim 10 , wherein each entry in said plurality of hash tables comprises a next hop address.
16. The non-transitory computer readable medium according to claim 10 , wherein each of said plurality of hash tables comprises 2 deg(g(x)) sets, where deg(g(x)) is the degree of said primitive generator polynomial.
17. The non-transitory computer readable medium according to claim 10 , wherein multiple entries of each of said plurality of hash tables share a common index.
18. The non-transitory computer readable medium according to claim 10 , wherein a remainder of one or more of said quotient and remainder pairs is calculated utilizing a remainder table.
19. A system for data processing, the system comprising:
one or more processors that are operable to:
translate a network address as a plurality of coefficient sets of a corresponding plurality of polynomials;
derive a plurality of quotient and remainder pairs from said plurality of coefficient sets;
access, in parallel, a plurality of hash tables;
determine a longest prefix match for said network address based on which of said hash tables return at least one match for at least one of said quotient and remainder pairs; and
route data in a network based on said longest prefix match.
20. The system according to claim 19 , wherein said one or more processors enable deriving said plurality of quotient and remainder pairs via modulo 2 division of said plurality of polynomials by a primitive generator polynomial.
21. The system according to claim 20 , wherein said primitive generator polynomial comprises the polynomial x 16 +x 8 +x 6 +x 5 +x 4 +x 2 +1.
22. The system according to claim 19 , wherein said plurality of hash-tables are set-associative.
23. The system according to claim 19 , wherein each entry in said plurality of hash tables comprises a quotient, when said quotient is greater than 0.
24. The system according to claim 19 , wherein each entry in said plurality of hash tables comprises a next hop address.
25. The system according to claim 19 , wherein each of said plurality of hash tables comprises 2 deg(g(x)) sets, where deg(g(x)) is the degree of said primitive generator polynomial.
26. The system according to claim 19 , wherein multiple entries of each of said plurality of hash tables share a common index.
27. The system according to claim 19 , wherein a remainder of each of said quotient and remainder pairs is calculated utilizing a remainder table.