Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2007-07-12
2010-12-14
Moore, Jr., Michael J (Department: 2467)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S389000, C711S216000
Reexamination Certificate
active
07852851
ABSTRACT:
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.
REFERENCES:
patent: 6442617 (2002-08-01), Lowe et al.
patent: 6611832 (2003-08-01), van Lunteren
patent: 6690667 (2004-02-01), Warren
patent: 6735670 (2004-05-01), Bronstein et al.
patent: 7437354 (2008-10-01), Venkatachary et al.
patent: 7483430 (2009-01-01), Yuan et al.
patent: 7565343 (2009-07-01), Watanabe
patent: 2002/0069232 (2002-06-01), Direen et al.
patent: 2003/0050762 (2003-03-01), Hatley
patent: 2005/0108617 (2005-05-01), Lappin, Jr.
patent: 2005/0195832 (2005-09-01), Dharmapurikar et al.
patent: 2006/0179071 (2006-08-01), Panigrahy et al.
patent: 2006/0200581 (2006-09-01), Cadambi et al.
patent: 2007/0150795 (2007-06-01), King et al.
Broadcom Corporation
McAndrews Held & Malloy Ltd.
Moore, Jr. Michael J
LandOfFree
Method and system for hash table based routing via a prefix... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for hash table based routing via a prefix..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for hash table based routing via a prefix... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4175564