System and methods for packet filtering

Details System and methods for packet filtering System and methods for packet filtering

2004-12-30

2009-12-15

Wilson, Robert W (Department: 2475)

Multiplex communications

Network configuration determination

C370S255000, C370S256000, C370S389000

Reexamination Certificate

active

07633886

ABSTRACT:
A system for classifying data packets transmitted over a data communications network based upon a set of predetermined prefixes associated with destination addresses of the data packets is provided. The includes a data structure stored in an electronic memory. The data structure is a prefix-in-B-tree (PIBT) data structure and/or a range-in-B-tree (RIBT) data structure, the at least one data structure comprising a plurality of nodes based upon the set of predetermined prefixes. The system also includes a determination module for determining a match between one or more of the plurality of nodes and a destination address of a particular data packet.

REFERENCES:
patent: 4606002 (1986-08-01), Waisman et al.
patent: 4910669 (1990-03-01), Gorin et al.
patent: 5212587 (1993-05-01), Healey
patent: 5218696 (1993-06-01), Baird et al.
patent: 5265244 (1993-11-01), Ghosh et al.
patent: 5613105 (1997-03-01), Zbikowski et al.
patent: 5644763 (1997-07-01), Roy
patent: 5680566 (1997-10-01), Peng et al.
patent: 5752243 (1998-05-01), Reiter et al.
patent: 5758360 (1998-05-01), Zbikowski et al.
patent: 5893931 (1999-04-01), Peng et al.
patent: 5903888 (1999-05-01), Cohen et al.
patent: 6144957 (2000-11-01), Cohen et al.
patent: 6374232 (2002-04-01), Dageville et al.
patent: 6445709 (2002-09-01), Chiang
patent: 6526055 (2003-02-01), Perlman et al.
patent: 6591269 (2003-07-01), Ponnekanti
patent: 6788695 (2004-09-01), Nagasawa
patent: 7054315 (2006-05-01), Liao
patent: 7188211 (2007-03-01), Roth et al.
patent: 2003/0078923 (2003-04-01), Voss et al.
patent: 2003/0123397 (2003-07-01), Lee et al.
patent: 2005/0091443 (2005-04-01), Hershkovich et al.
patent: 0124097 (1984-11-01), None
patent: 0235525 (1987-09-01), None
patent: 1063827 (2000-12-01), None
patent: 02227735 (1990-09-01), None
patent: 04156624 (1992-05-01), None
patent: WO 03/042780 (2003-05-01), None
Degermark, M., et al., “Small Forwarding Tables for Fast Routing Lookups”, ACM SIGCOMM, pp. 3-14, 1997.
Ergun, F., et al., “A Dynamic Lookup Scheme for Bursty Access Patterns”, IEEE INFOCOM, 2001.
Gupta, P., et al., “Dynamic Algorithms With Worst-Case Performance for Packet Classification”, IFIP Networking, 2000.
Lampson, B., et al., “IP Lookups Using Multiway and Multicolumn Search”, IEEE INFOCOM 98, May 11, 1998.
Srinivasan, V., et al., “Faster IP Lookups Using Controlled Prefix Expansion”, ACM Trans. on Computer Systems, Nov. 5, 1997.
Nilsson, S., et al., “Fast Address Look-Up for Internet Routers”, IEEE Broadband Communications, 1998 and Proc. of Alg. and Exp., Feb. 1998.
Sahni, S., et al., “Efficient Construction of Fixed-Stride Multibit Tries for IP Lookup”,8th IEEE Workshop on Future Trends of Dist. Comp. Sys., 2001.
Sahni, S., et al., “Efficient Construction of Variable-Stride Multibit Tries for IP Lookup”, Proc. IEEE Sym. on Apps. & the Internet (SAINT), pp. 220-227, 2002.
Suri, S., et al., “Multiway Range Trees: Scalable IP Lookup With Fast Updates”, Globecom 2001.
Waldvogel, M., et al., “Scalable High Speed IP Routing Lookups”, ACM SIGCOMM, pp. 25-36, 1997.
Sahni, S., et al., “Data Structures for One-Dimensional Packet Classification Using Most-Specific-Rule Matching”, ISPAN, pp. 3-14, 2002.
Sahni, S., et al., “An O(log n) Dynamic Router-Table Design”, IEEE Sym. on Computers & Communications, 2002.
Lu, H., et al., “O(log n) Dynamic Router-Tables for Prefixes and Ranges”, IEEE Trans. on Computers, vol. 53, No. 10, pp. 1217-1230, Oct. 2004.
Doeringer, W., et al., “Routing on Longest-Matching Prefixes”, IEEE/ACM Transactions on Networking, vol. 4, No. 1, pp. 86-97, Feb 1996.
Ruiz-Sanchez, M., et al., “Survey & Taxonomy of IP Address Lookup Algorithms”, IEEE Network, vol. 15, No. 2, pp. 8-23, Mar./Apr. 2001.
Sklower, K., “A Tree-Based Routing Table for Berkeley Unix”, Tech. Report, UC Berkeley, 1993.

Affiliated with

Also associated with

Rating

System and methods for packet 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 System and methods for packet filtering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and methods for packet filtering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4135013