Dense mode coding scheme

Details Dense mode coding scheme Dense mode coding scheme

2008-01-04

2009-12-15

Sam, Phirin (Department: 2419)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S256000

Reexamination Certificate

active

07633960

ABSTRACT:
A lookup table for searching for a longest prefix match for a key is disclosed. The lookup table provides a match for a key in a single search cycle. The number of matches stored in the lookup table is maximized by storing each match in only one location in the lookup table. The binary tree is divided into a plurality of levels and each level has a plurality of subtrees. A subtree descriptor stored for a subtree includes a field for each node in the subtree. The state of the field indicates whether an entry for the node is stored in the table. The bit vector allows indexing of the single match stored for the key.

REFERENCES:
patent: 6266706 (2001-07-01), Brodnik et al.
patent: 6691218 (2004-02-01), Brown
patent: 6973494 (2005-12-01), Weisser et al.
patent: 6985960 (2006-01-01), Takashima et al.
patent: 7016351 (2006-03-01), Farinacci et al.
patent: 7106732 (2006-09-01), Brown
patent: 7346009 (2008-03-01), Brown et al.
patent: 7352739 (2008-04-01), Rangarajan et al.
patent: 2003/0189930 (2003-10-01), Terrell et al.
patent: WO 99/14906 (1999-03-01), None
P. Gupta, et al., “Lookups In Hardware at Memory Access Speeds,” IEEE, pp. 1240-1247, 1998.
Ruiz-Sanchez, Miguel,A., et al., “Survey and Taxonomy of IP Address Lookup Algorithms,” IEEE Network, pp. 8-23, 2001.
Degermark, M., et al., “Small Forwarding Tables for Fast Routing Lookups,” Department of Computer Science and Electrical Engineering, Lulea University of Technology, S-971 Lulea, Sweden, pp. 3-14.

Affiliated with

Also associated with

Rating

Dense mode coding scheme does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dense mode coding scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dense mode coding scheme will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4131684