Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2011-08-02
2011-08-02
Shah, Chirag (Department: 2477)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S408000
Reexamination Certificate
active
07990979
ABSTRACT:
A recursively partitioned static router-table, the data structure incorporating a first-level partition including subtries and an auxiliary trie. A node of the subtrie includes a path Q(N) from the root R of a trie T to a root N of the subtrie, a stride s for a next-level partition, a mask that characterizes a next-level perfect hash function, and a pointer to the hash table for the next-level partition. At least one of the trie T, the first-level partition, the auxiliary trie, and the next-level partition is represented by a base structure selected from the group consisting of MBT and HSST.
REFERENCES:
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6563823 (2003-05-01), Przygienda et al.
patent: 6614789 (2003-09-01), Yazdani et al.
patent: 6658482 (2003-12-01), Chen et al.
patent: 6798777 (2004-09-01), Ferguson et al.
patent: 6859455 (2005-02-01), Yazdani et al.
patent: 6867991 (2005-03-01), Tezcan et al.
patent: 6975631 (2005-12-01), Kastenholz
patent: 7430560 (2008-09-01), Mittal
patent: 7478109 (2009-01-01), Panigrahy et al.
patent: 2004/0111440 (2004-06-01), Richardson et al.
patent: 2004/0141509 (2004-07-01), Sahni et al.
patent: 2004/0230696 (2004-11-01), Barach et al.
patent: 2004/0258061 (2004-12-01), Sahni et al.
patent: 2005/0157712 (2005-07-01), Rangarajan et al.
patent: 2006/0020638 (2006-01-01), Shadmon
patent: 2007/0067201 (2007-03-01), Malewicz
patent: 2007/0121632 (2007-05-01), Zabarski
patent: WO 99/26163 (1999-05-01), None
patent: WO 03/063427 (2003-07-01), None
Srinivasan et al. “Fast Address Lookups Using Controlled Prefix Expansion” Feb. 1999.
Tzeng, N.-F., “Routing Table Partitioning for Speedy Packet Lookups in Scalable Routers”, IEEE Transactions on Parallel and Distributed Systems, May 2006, vol. 17, No. 5, pp. 481-494.
Pao, D., Liu, C., Wu, L., and Chan, K.S., “Efficient Hardware Architecture for Fast IP Address Lookup”, IEE Proceedings, Computers and Digital Techniques, Jan. 2003, vol. 150, No. 1, pp. 43-52.
Degermark, M., Brodnik, A., Carlsson, S., and Pink., S., “Small Forwarding Fables for Fast Fouting Lookups”, Proceedings of SIGCOMM, 1997, pp. 3-14.
Eatherton, W., Varghese, G., and Dittia, Z., “Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates”, ACM SIGCOMM Computer Communication Review, Apr. 2004, vol. 34, No. 2, pp. 97-122.
Lampson, B., Srinivasan, V., and Varghese, G., “IP Lookups Using Multiway and Multicolumn Search”, INFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, Mar. 29-Apr. 2, 1998, vol. 3, pp. 1248-1256.
Lu, H., Kim, K.S., and Sahni, S., “Prefix and Interval-Partitioned Dynamic IP Router-Tables”, IEEE Transaction on Computers, May 2005, vol. 54, No. 5, pp. 545-557.
Van Lunteren, J., “Searching Very Large Routing Tables in Fast SRAM”, IEEE Tenth International Conference on Computer Communications and Networks, Proceedings, 2001, pp. 4-11.
Van Lunteren, J., “Searching Very Large Routing Tables in Wide Embedded Memory”, IEEE Global Telecommunications Conference, GLOBECOM, 2001, vol. 3, pp. 1615-1619.
Nilsson, S. and Karlsson, G., “Fast Address Lookup for Internet Routers”, IEEE Broadband Communications, 1998.
Ruiz-Sanchez, M.A., Biersack, E.W., and Dabbous, W., “Survey and Taxonomy of IP Address Lookup Algorithms”, IEEE Network, Mar./Apr. 2001, pp. 8-23.
Sahni, S., and Kim, K.S., “Efficient Construction of Multibit Tries for IP Lookup”, IEEE/ACM Transactions on Networking, Aug. 2003, vol. 11, No. 4, pp. 650-662.
Sahni, S., Kim, K.S., and Lu, H., “Data Structures for One-Dimensional Packet Classification Using Most-Specific-rule Matching”, IEEE, Proceeding of International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '02), 2002, pp. 1-12.
Song, H. Turner, J. and Lockwood, J., “Shape Shifting Tries for Faster IP Route Lookup”, Proceedings of 13thIEEE International Conference on Network Protocols (ICNP '05), 2005.
Srinivasan, V. and Varghese, G., “Fast Address Lookups using Controlled Prefix Expansion”, ACM Transactions on Computer Systems, Feb. 1999, vol. 17, No. 1, pp. 1-40.
Sun, X. and Zhao, Y.Q., “An On-Chip IP Address Lookup Algorithm”, IEEE Transaction on Computers, Jul. 2005, vol. 54, No. 7, pp. 873-885.
Wang, M. Deering, S. Hain, T. and Dunn, L., “Non-Random Generator for IPv6 Tables”, 12thAnnual IEEE Symposium on High Performance Interconnects, 2004, pp. 35-40.
Akhbarizadeh, M.J., and Nourani, M. “Hardware-Based IP Routing Using Partitioned Lookup Table”, IEEE/ACM Transactions on Networking, Aug. 2005, vol. 13, No. 4, pp. 769-781.
Lu, H., Kim, K.S., and Sahni, S., “Prefix and Interval-Partitioned Router-Tables”, IEEE Communication Society Globecom, 2004, pp. 1590-1594.
Song, Y. and Aboelela, E., “A Parallel IP-Address Forwarding Approach Based on Partitioned Lookup Table Techniques”, Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN'04).
Tzeng, N.F., “Hardware-Assisted Design for Fast Packet Forwarding in Parallel Routers”, Proceedings of the 2003 International Conference on Parallel Processing (ICCP'03).
Nourani, M. and Akhbarizadeh, M., “A Fully Scalable IP Forwarding Engine Based on Partitioned Lookup Table”, IEEE Global Telecommunications Conference 2002, GLOBECOM '02, Nov. 2002, vol. 3, pp. 2333-2337.
Akhbarizadeh, M.J., and Nourani, M. “An IP Packet Forwarding Technique Based on Partitioned Lookup Table”, IEEE International Conference on Communications ICC, 2002, vol. 4, pp. 2263-2267.
Chau, T. and Wong, K.C., “Pattern Discovery by Residual Analysis and Recursive Partitioning”, IEEE Transactions on Knowledge and Data Engineering, Nov./Dec. 1999, vol. 11, No. 6, pp. 833-852.
Lu Wencheng
Sahni Sartaj Kumar
Saliwanchik Lloyd & Eisenschenk
Shah Chirag
University of Florida Research Foundation Inc.
Van Jenkey
LandOfFree
Recursively partitioned static IP 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 Recursively partitioned static IP router tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Recursively partitioned static IP router tables will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2746320