Mechanism to reduce lookup latency in a pipelined hardware...

Details Mechanism to reduce lookup latency in a pipelined hardware... Mechanism to reduce lookup latency in a pipelined hardware...

2011-04-12

2011-04-12

Ngo, Ricky (Department: 2464)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S465000

Reexamination Certificate

active

07924839

ABSTRACT:
A series of hardware pipeline units each processing a stride during prefix search operations on a multi-bit trie includes, within at least one pipeline unit other than the last pipeline unit, a mechanism for retiring search results from the respective pipeline unit rather than passing the search results through the remaining pipeline units. Early retirement may be triggered by either the absence of subsequent strides to be processed or completion (a miss or end node match) of the search, together with an absence of active search operations in subsequent pipeline units. The early retirement mechanism may be included in those pipeline units corresponding to a last stride for a maximum prefix length shorter than the pipeline (e.g., 20 or 32 bits rather than 64 bits), in pipeline units selected on some other basis, or in every pipeline unit. Worst-case and/or average latency for prefix search operations is reduced.

REFERENCES:
patent: 5471593 (1995-11-01), Branigin
patent: 6079006 (2000-06-01), Pickett
patent: 6209020 (2001-03-01), Angle et al.
patent: 6430527 (2002-08-01), Waters et al.
patent: 6560610 (2003-05-01), Eatherton et al.
patent: 6691124 (2004-02-01), Gupta et al.
patent: 6711153 (2004-03-01), Hebb et al.
patent: 6728732 (2004-04-01), Eatherton et al.
patent: 6731644 (2004-05-01), Epps et al.
patent: 6772268 (2004-08-01), Kristiansen et al.
patent: 6839830 (2005-01-01), Liu
patent: 6880064 (2005-04-01), Brown
patent: 6891834 (2005-05-01), Dally et al.
patent: 7099881 (2006-08-01), Richardson et al.
patent: 7171490 (2007-01-01), Basu et al.
patent: 2002/0146009 (2002-10-01), Gupta et al.
patent: 2002/0147721 (2002-10-01), Gupta et al.
patent: 2003/0236968 (2003-12-01), Basu et al.

Affiliated with

Also associated with

Rating

Mechanism to reduce lookup latency in a pipelined hardware... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Mechanism to reduce lookup latency in a pipelined hardware..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mechanism to reduce lookup latency in a pipelined hardware... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2718090