Header range check hash circuit

Details Header range check hash circuit Header range check hash circuit

2003-09-08

2008-03-18

Phan, Man U. (Department: 2619)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S235000, C370S389000, C709S224000, C709S242000

Reexamination Certificate

active

07346059

ABSTRACT:
A technique efficiently searches a hash table containing a plurality of “ranges.” In contrast with previous implementations, the technique performs fewer searches to locate one or more ranges stored in the hash table. To that end, the hash table is constructed so each hash-table entry is associated with a different linked list, and each linked-list entry stores, inter alia, “signature” information and at least one pair of values defining a range associated with the signature. The technique modifies the signature based on the results of one or more preliminary range checks. As a result, the signature's associated ranges are more evenly distributed among the hash table's linked lists. Thus, the linked lists are on average shorter in length, thereby enabling faster and more efficient range searches. According to an illustrative embodiment, the technique is applied to flow-based processing implemented in an intermediate network node, such as a router.

REFERENCES:
patent: 6212183 (2001-04-01), Wilford
patent: 6266705 (2001-07-01), Ullum et al.
patent: 6457058 (2002-09-01), Ullum et al.
patent: 6651099 (2003-11-01), Dietz et al.
patent: 6826561 (2004-11-01), Cao et al.
patent: 6965945 (2005-11-01), Lin et al.
patent: 7027446 (2006-04-01), Rosenfeld et al.
patent: 7072885 (2006-07-01), Cao et al.
patent: 2004/0230696 (2004-11-01), Barach et al.
patent: 2006/0059196 (2006-03-01), Sato et al.
Radia Perlman, Interconnections, Second Edition: Bridges, Routers, Switches, and Internetworking Protocols, Addison Wesley Longman, Inc., pp. 1-17, Jan. 2000.
Siegfried Loffler, Using Flows for Analysis and Measurement of Internet Traffic, Institute of Communication Networks and Computer Engineering (IND) of the University of Stuttgart, <siegfried.loeffler@rus.uni-stuttgart.de>, Aug. 1997.
Caspian Networks, Flow-Based Routing: Rationale and Benefits, pp. 1-25, Caspian Networks, Inc., 2003.
Kimberly C. Claffy, et al., A Parameterizable Methodology for Internet Traffic Flow Profiling, pp. 1-25.
Martin Hughes, et al., Memory Efficient Hashing Algorithm, U.S. Appl. No. 10/769,941, filed Feb. 2, 2004.

Affiliated with

Also associated with

Rating

Header range check hash circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Header range check hash circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Header range check hash circuit will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3963521