Apparatus and method for efficient longest prefix match lookup

Details Apparatus and method for efficient longest prefix match lookup Apparatus and method for efficient longest prefix match lookup

2007-05-01

2007-05-01

Ferris, Derrick W. (Department: 2616)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

Reexamination Certificate

active

10167005

ABSTRACT:
A search engine improves search speed and reduces required memory for a longest prefix matching (LPM) router that routes packets using IP addresses. The search engine includes a first bit vector with set bits corresponding to address ranges. A set bit counter counts the set bits in the bit vector based on a first portion of the address of the a first packet. A first next hop table contains first pointers for each of the set bits. One of the first pointers is selected based on a number of set bits counted by the set bit counter. For longer addresses, the addresses are split into address portions. The search engine includes a trie data structure that has n levels. The n levels of the trie data structure include nodes representing non-overlapping address space.

REFERENCES:
patent: 6697363 (2004-02-01), Carr

Affiliated with

Also associated with

Rating

Apparatus and method for efficient longest prefix match lookup does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Apparatus and method for efficient longest prefix match lookup, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for efficient longest prefix match lookup will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3735781