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 x16+x8+x6+x5+x4+x2+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 2deg(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.
展开▼
机译：提供了用于经由前缀变换的基于哈希表的路由的方法和系统的方面。本发明的各方面可以使得能够将一个或多个网络地址转换为多项式的系数集，并且基于从系数集导出的商和余数来路由网络中的数据。就这一点而言，商和余数可以通过由原始生成多项式对多项式进行模2除来计算。在一个示例中，可以借助于余数表来计算余数。基本生成多项式可以为x 16 + x 8 + x 6 + x 5 + x 4 + x 2 +1。另外，一个或多个哈希表中的条目可以包括计算出的商，并且可以由计算出的余数来索引。以这种方式，可以访问哈希表以确定一个或多个网络地址的最长前缀匹配。哈希表可以包含2个deg（g（x））集，其中deg（g（x））是原始生成多项式的次数。因此，可以将哈希表设置为关联的，并且可以通过相同的余数来索引多个条目。此外，哈希表中的条目可以包括在路由网络业务中使用的下一跳地址。
展开▼
