Prefix partitioning methods for dynamic router tables

Details Prefix partitioning methods for dynamic router tables Prefix partitioning methods for dynamic router tables

2003-11-21

2008-10-28

Rao, Seema S. (Department: 2616)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

07444318

ABSTRACT:
A method is provided to improve the performance of dynamic router-table designs. Specifically, the invention relates to a method and system for partitioning prefixes at each node of a partitioning tree into 2s+1 partitions using the next s bits of the prefixes. Prefixes that have a length less than s are placed into partition −1, with the remaining prefixes falling into the remaining partitions that correspond to the value of their first s bits. Prefix partitioning may be controlled using either static rule tables or by dynamic rule tables. In one embodiment, binary tree on binary tree (BOB) data structures are applied to a partition of the present invention. In another embodiment, prefix binary tree on binary tree (PBOB) data structures are applied to a partition of the present invention. In a further embodiment, a dynamic longest-matching prefix binary tree on binary tree-table (LMPBOB) is applied to a partition of the present invention.

REFERENCES:
patent: 4251861 (1981-02-01), Mago
patent: 4833468 (1989-05-01), Larson et al.
patent: 5546390 (1996-08-01), Stone
patent: 5555405 (1996-09-01), Griesmer et al.
patent: 5701467 (1997-12-01), Freeston
patent: 5761440 (1998-06-01), De Marco et al.
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5909440 (1999-06-01), Ferguson et al.
patent: 5978795 (1999-11-01), Poutanen et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6021131 (2000-02-01), Even
patent: 6041053 (2000-03-01), Douceur et al.
patent: 6061712 (2000-05-01), Tzeng
patent: 6092072 (2000-07-01), Guha et al.
patent: 6157955 (2000-12-01), Narad et al.
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6266706 (2001-07-01), Brodnik et al.
patent: 6289013 (2001-09-01), Lakshman et al.
patent: 6335932 (2002-01-01), Kadambi et al.
patent: 6341130 (2002-01-01), Lakshman et al.
patent: 6353873 (2002-03-01), Melchior
patent: 6366582 (2002-04-01), Nishikado et al.
patent: 6392842 (2002-05-01), Boutaghou et al.
patent: 6522632 (2003-02-01), Waters et al.
patent: 6533370 (2003-04-01), Andreev et al.
patent: 6563823 (2003-05-01), Przygienda et al.
patent: 6581106 (2003-06-01), Crescenzi et al.
patent: 6611832 (2003-08-01), van Lunteren
patent: 6675157 (2004-01-01), Mitchell
patent: 6681218 (2004-01-01), Zou
patent: 6728705 (2004-04-01), Licon et al.
patent: 6944598 (2005-09-01), Cline
patent: 7113581 (2006-09-01), Benedyk et al.
patent: 2002/0009076 (2002-01-01), Engbersen et al.
patent: 2003/0123387 (2003-07-01), Jackson
patent: 2004/0141509 (2004-07-01), Sahni et al.
Degermark, Mikael, et al. (1997) “Small Forwarding Tables for Fast Routing Lookups”ACM SIGCOMM Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication. pp. 3-14.
Doeringer, W., G. Karjoth, and M. Nassehi (1996) “Routing on longest-matching prefixes”IEEE/ACM Transactions on Networking, 4(1): pp. 86-87.
Ergun, Funda, et al. (2001) “A Dynamic Lookup Scheme for Bursty Access Patterns”Proceedings of IEEE INFOCOMpp. 1-10.
Gupta, P. and N. McKeown (2000) “Dynamic algorithms with worst-case performance for packet classification”IFIP Networkingpp. 528-539.
Lampson, Butler, Venkatachary Srinivasan, and George Varghese (Jun. 1999) “IP Lookups Using Multiway and Multicolumn Search”IEEE/ACM Transactions on Networking vol. 7, No. 3, pp. 324-334.
Lu, H. and Sahni, S. (2003) “O (logn) dynamic router-tables for prefixes and ranges”IEEE Symposium on Computers and Communicationspp. 1-42.
Nilsson, Stefan and Gunnar Karlsson (1998) “Fast address lookup for Internet routers”Proceedings of IEEE Broadband Communications(enclosed copy pages numbered 9-18).
Ruiz-Sanchez, M., E. Biersack, and W. Dabbous (Mar./Apr. 2001) “Survey and taxonomy pf IP address lookup algorithms”IEEE Network, 15(2): pp. 8-23.
Sahni, Sartaj and Kun Suk Kim “Data Structures of IP Lookup with Bursty Access Patterns” www.cise.ufl.edu/-sahni (enclosed copy pages numbered 1-5).
Sahni, Sartaj and Kun Suk Kim (2001) “Efficient Construction of Fixed-Stride Multibit Tries for IP Lookup”Proceedings of 8thIEEE Workshop on Future Trends of Distributed Computing Systemspp. 178-184 (enclosed copy pages numbered 1-7).
Sahni, Sartaj and Kun Suk Kim (2002) “Efficient Construction of Variable-Stride Multibit Tries for IP Lookup”Proceedings of IEEE Symposium on Applications and the Internet(SAINT) pp. 220-229 (enclosed copy pages numbered 1-8).
Sahni, Sartaj and Kun Suk Kim (Jul. 2002) “O(log n) Dynamic Packet Routing” 7thIEEE Symposium on Computers and Communications. pp. 1-29.
Sahni, Sartaj, Kun Suk Kim, and Haibin Lu (May 2002) “Data Structures for One-Dimensional Packet Classification Using Most-Specific-Rule Matching”International Symposium on Parallel Architectures, Algorithms, and Networks(ISPAN) pp. 3-14 (enclosed copy pages numbered 1-12).
Sklower, Keith (1991) “A Tree-Based Packet Routing Table for Berkeley Unix”Proceedings of 1991 Winter USENIX Conferencepp. 93-99 (enclosed copy pages numbered 1-4).
Srinivasan, V. and G. Varghese (Feb. 1999) “Faster IP Lookups Using Controlled Prefix Expansion”ACM Transactions on Computer Systemsvol. 17, issue 1, pp. 1-40 (enclosed copy pages numbered 1-21).
Suri, S., G. Varghese, and P. Warkhede (2001) “Multiway range trees: Scalable IP lookup with fast updates”Proceedings of Globecom'01.
Waldvogel, Marcel et al. (1997) “Scalable High Speed IP Routing Lookups”Proceedings of the ACM SIGCOMM '97 Conference on Applications, technologies, architectures, and protocols for computer communication. pp. 25-36 (enclosed copy pages numbered 1-12).
Afek, Y. et al. (Dec. 14, 1999) “Routing with a Clue”ACM SIGCOMM, pp. 203-214 (enclosed copy pages No. 0-23).
Berg, M. Krevald and J. Snoeyink (1995) “Two- and Three-dimensional Point Location in Rectangular Sub-divisions”Journal of Algorithms. vol. 18, No. 2, pp. 256-277.
Chandranmenon, G. and Varghese, G. (1996) “Trading Packet Headers for Packet Processing”IEEE Transactions on Networking. vol. 4, No. 2, pp. 141-152 (enclosed copy pages numbered 1-13).
Cheung and McCanne. (1999) “Optimal Routing Table Design for IP Address Lookups under Memory Constraints,”IEEE INFOCOM. pp. 1437-1444.
Hari, A. et al. (2000) “Detecting and Resolving Packet Filter Conflicts”IEEE INFOCOM. pp. 1203-1212.
Macian, C. and R. Finthammer. (2001) “An Evaluation to the Key Design Criteria to Achieve High Update Rates in Packet Classifiers”IEEE Network. Nov./Dec. pp. 24-29 (enclosed copy pages numbered 1-10).
McAuley, A. and P. Francis.(1993) “Fast Routing Table Lookups Using CAMs”IEEE INFOCOM. vol. 3 Mar./Apr., pp. 1382-1391.
McCreight, E. (1985). “Priority Search Trees”SIAM Jr. on Computing. vol. 14, No. 1, pp. 257-276.
Newman, P. et al. (Jan. 1997) “IP Switching and Gigabit Routers”IEEE Broadband Communications Magizine. vol. 35, pp. 64-69 (enclosed copy pages numbered 1-8).
U.S. Appl. No. 10/426,423, filed Apr. 30, 2003 (Inventors: Santaj Kumar Sahni, Haibin Lu), application attached.
Office Action dated Dec. 12, 2007 in U.S. Appl. No. 10/426,423, filed Apr. 30, 2003.
Office Action dated Mar. 18, 2008 in U.S. Appl. No. 10/718,842, filed Nov. 21, 2003.

Affiliated with

Also associated with

Rating

Prefix partitioning methods for dynamic router tables does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Prefix partitioning methods for dynamic router tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prefix partitioning methods for dynamic router tables will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4011524