Hashing algorithm for network receive filtering

Details Hashing algorithm for network receive filtering Hashing algorithm for network receive filtering

2011-07-19

2011-07-19

Bates, Kevin (Department: 2456)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

C370S395320, C370S392000

Reexamination Certificate

active

07984180

ABSTRACT:
Roughly described, a network interface device is assigned a maximum extent-of-search. A hash function is applied to the header information of each incoming packet, to generate a hash code for the packet. The hash code designates a particular subset of the table within which the particular header information should be found, and an iterative search is made within that subset. If the search locates a matching entry before the search limit is exceeded, then the incoming data packet is delivered to the receive queue identified in the matching entry. But if the search reaches the search limit before a matching entry is located, then device delivers the packet to a default queue, such as a kernel queue, in the host computer system. The kernel is then responsible for delivering the packet to the correct endpoint.

REFERENCES:
patent: 5682341 (1997-10-01), Kim et al.
patent: 5740467 (1998-04-01), Chmielecki, Jr. et al.
patent: 5914938 (1999-06-01), Brady et al.
patent: 6334162 (2001-12-01), Garrett et al.
patent: 6397316 (2002-05-01), Fesas, Jr.
patent: 6424650 (2002-07-01), Yang et al.
patent: 6510164 (2003-01-01), Ramaswamy et al.
patent: 6526066 (2003-02-01), Weaver
patent: 6597661 (2003-07-01), Bonn
patent: 6675163 (2004-01-01), Bass et al.
patent: 6683865 (2004-01-01), Garcia-Luna-Aceves et al.
patent: 6798777 (2004-09-01), Ferguson et al.
patent: 6880089 (2005-04-01), Bommareddy et al.
patent: 6888797 (2005-05-01), Cao et al.
patent: 6909713 (2005-06-01), Magnussen et al.
patent: 6959297 (2005-10-01), Oh et al.
patent: 7068652 (2006-06-01), Lin et al.
patent: 7133400 (2006-11-01), Henderson et al.
patent: 7260565 (2007-08-01), Lee et al.
patent: 7304992 (2007-12-01), Relan
patent: 7397797 (2008-07-01), Alfieri et al.
patent: 7478426 (2009-01-01), Corl et al.
patent: 7480302 (2009-01-01), Choi
patent: 7573880 (2009-08-01), Kaxiras et al.
patent: 7689485 (2010-03-01), Kanekar et al.
patent: 2002/0023089 (2002-02-01), Woo
patent: 2002/0152209 (2002-10-01), Merugu et al.
patent: 2002/0198981 (2002-12-01), Corl et al.
patent: 2003/0043805 (2003-03-01), Graham et al.
patent: 2003/0081615 (2003-05-01), Kohn et al.
patent: WO 2005/104453 (2005-11-01), None
Microsoft Corp., Microsoft Windows, “Scalable Networking with RSS”, WinHEC 2005 Update, Apr. 19, 2005.
Compaq Computer Corp., Intel Corp, Microsoft Corp., “Virtual Interface Architecture Specification”, Version 1.0, Dec. 16, 1997.
Pratt et al., “Arsenic: A User-Accessible Gigabit Ethernet Interface”, University of Cambridge, England, Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM-01), pp. 67-76, Apr. 2001.
Wartik et al, “Information Retrieval Data Structures & Algorithms”, Hashing Algorithms, Chapter 13, Software Productivity Consortium, Virginia Polytechnic Institute and State University, Prentice-Hall, Inc., Upper Saddle River, New Jersey, 1992.
Mansley, “Engineering a User-Level TCP for the CLAN Network”, Laboratory for Communication Engineering, University of Cambridge, Cambridge, England Proceedings of the ACM SIGCOMM 2003 Workshops, Aug. 2003.
Information Sciences Institute, University of Southern California, Marina del Rey, CA, “Transmission Control Protocol”, Darpa Internet Program Protocol Specification, pp. 1-84, Sep. 1981 (rfc0793.TCP.txt).
J. Postel, “User Datagram Protocol”, Isi Aug. 28, 1980, pp. 1-3 (rfc0768.UDP.txt).
Riddoch, David et al.; “Distributed Computing With the CLAM Network”; Laboratory for Communications Engineering, Cambridge, England; SIGCOMM 2002, 13 pages.
Mansley, Kieran; “Engineering a User-Level TCP for the CLAN Network”; Laboratory for Communication Engineering, University of Cambridge, Cambridge, England; AGM SIGCOMM Aug. 2003 Workshops, 228-236.
Pratt, Ian et al.; “Arsenic: A User-Accessible Gigabit Ethernet Interface”; Computer Laboratory, University of Cambridge, England; UK Engineering and Physical Sciences Research Councel (EPSRC), Apr. 2001, 11 pages.
Dixon JT et al., “Tuning TCP and UDP Demultiplexing,” Georgia Institute of Technology, CC Technical Report GIT-CC-09-09, 1998, 36 pp.
International Preliminary Report on Patentability, Chapter I, mailed May 2, 2008 in PCT/GB2006/003828.
Gordon E. Moore; Electronics, vol. 38, No. 8, pp. 114-117, Apr. 19, 1965.
Jack B. Dennis and Earl C. Van Horn; Communications of the ACM, vol. 9, No. 3, pp. 143-155, Mar. 1966.
Marvin Zelkowitz; Communications of the ACM, vol. 14, No. 6, p. 417-418, Jun. 1971.
J. Carver Hill; Communications of the ACM, vol. 16, No. 6, p. 350-351, Jun. 1973.
F.F. Kuo; ACM Computer Communication Review, vol. 4 No. 1, Jan. 1974.
Vinton Cerf, Robert Kahn; IEEE Transactions on Communications, vol. COM-22, No. 5, pp. 637-648, May 1974.
V. Cerf, et al.; ACM Computer Communication Review, vol. 6 No. 1, p. 1-18, Jan. 1976.
Robert M. Metcalfe and David R. Boggs; Communications of the ACM, vol. 19, Issue 7, pp. 395-404, Jul. 1976.
P. Kermani and L. Kleinrock; Computer Networks, vol. 3, No. 4, pp. 267-286, Sep. 1979.
John M. McQuillan, et al.; Proceedings of the 6th Data Communications Symposium, p. 63, Nov. 1979.
Andrew D. Birrell, et al.; Communications of the ACM, vol. 25, Issue 4, pp. 260-274, Apr. 1982.
Ian M. Leslie, et al.; ACM Computer Communication Review, vol. 14, No. 2, pp. 2-9, Jun. 1984.
John Nagle; ACM Computer Communication Review, vol. 14, No. 4, p. 11-17, Oct. 1984.
Robert M. Brandriff, et al.; ACM Computer Communication Review, vol. 15, No. 4, Sep. 1985.
C. Kline; ACM Computer Communication Review, vol. 17, No. 5, Aug. 1987.
Christopher A. Kent, Jeffrey C. Mogul; ACM Computer Communication Review, vol. 17, No. 5, pp. 390-401, Oct. 1987.
Gary S. Delp, et al.; ACM Computer Communication Review, vol. 18, No. 4, p. 165-174, Aug. 1988.
David R. Boggs, et al.; ACM Computer Communication Review, vol. 18, No. 4, p. 222-234, Aug. 1988.
H. Kanakia and D. Cheriton; ACM Computer Communication Review, vol. 18, No. 4, p. 175-187, Aug. 1988.
V. Jacobson; ACM Computer Communication Review, vol. 18, No. 4, p. 314-329, Aug. 1988.
David D. Clark; ACM Computer Communication Review, vol. 18, No. 4, pp. 106-114, Aug. 1988.
Paul V. Mockapetris, Kevin J. Dunlap; ACM Computer Communication Review, vol. 18, No. 4, pp. 123-133, Aug. 1988.
Margaret L. Simmons and Harvey J. Wasserman; Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p. 288-295, Orlando, Florida, Nov. 12, 1988.
David A. Borman; ACM Computer Communication Review, vol. 19, No. 2, p. 11-15, Apr. 1989.
R. Braden, et al.; ACM Computer Communication Review, vol. 19, No. 2, p. 86-94, Apr. 1989.
David D. Clark, et al.; IEEE Communications Magazine, vol. 27, No. 6, pp. 23-29, Jun. 1989.
David R. Cheriton; ACM Computer Communication Review, vol. 19, No. 4, p. 158-169, Sep. 1989.
Derek Robert McAuley; PhD Thesis, University of Cambridge, Sep. 1989.
Craig Partridge; ACM Computer Communication Review, vol. 20, No. 1, p. 44-53, Jan. 1990.
D. D. Clark and D. L. Tennenhouse; ACM Computer Communication Review, vol. 20, No. 4, pp. 200-208, Sep. 1990.
Eric C. Cooper, et al.; ACM Computer Communication Review, vol. 20, No. 4, p. 135-144, Sep. 1990.
Bruce S. Davie; ACM Computer Communication Review, vol. 21, No. 4, Sep. 1991.
C. Brendan S. Traw, et al.; ACM Computer Communication Review, vol. 21, No. 4, p. 317-325, Sep. 1991.
Ian Leslie and Derek R. McAuley; ACM Computer Communication Review, vol. 21, No. 4, p. 327, Sep. 1991.
Mark Hayter, Derek McAuley; ACM Operating Systems Review, vol. 25, Issue 4, p. 14-21, Oct. 1991.
Gregory G. Finn; ACM Computer Communication Review, vol. 21, No. 5, p. 18-29, Oct. 1991.
Greg Chesson; Proceedings of the Third International Conference on High Speed Networking, Nov. 1991.
Michael J. Dixon; University of Cambridge Computer Laboratory Technical Report No. 245, Jan. 1992.
Danny Cohen, Gregory Finn, Robert Felderman, Annette DeSchon; Made available by authors, Jan. 10, 1992.
Gene Tsudik; ACM Computer Communication Review, vol. 22, No. 5, pp.

Affiliated with

Also associated with

Rating

Hashing algorithm for network receive filtering does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hashing algorithm for network receive filtering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hashing algorithm for network receive filtering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2679221