Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2005-02-22
2005-02-22
Pham, Chi (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S401000
Reexamination Certificate
active
06859455
ABSTRACT:
A method and apparatus are provided for building a searchable multi-dimensional index tree that indexes a plurality of data objects. In one aspect of the invention, the index tree divides dataspace into three subspaces and indexes the data objects using a single dimension. If too many data objects map to the same point in that dimension, the dimension is switched to a new dimension of the data object and the data object is indexed using the new dimension. A split node having a split value is used to keep track of the indexing. In another aspect of the invention, the index tree divides dataspace into two subspaces, and equal bits are used in the split nodes to track the content of the data objects in the subspaces. If too many data objects sharing the same key within the same dimension map to a single point, then the dimension is switched to a new dimension and the data objects are indexed using the new dimension. Also disclosed is the multi-dimensional index tree itself as well as a router that uses the multi-dimensional index tree of the present invention to provide packet classification functions.
REFERENCES:
patent: 4464650 (1984-08-01), Eastman et al.
patent: 5758024 (1998-05-01), Alleva
patent: 5761652 (1998-06-01), Wu et al.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5806065 (1998-09-01), Lomet
patent: 5812853 (1998-09-01), Carroll et al.
patent: 6614789 (2003-09-01), Yazdani et al.
A. Brodnik, S. Carlsson, M. Degermark, and S. Pink,Small Forwarding Tables for Fast Routing Lookups, Proceeding of ACM SIGCOMM Conference 1997, pp. 3-14, Sep. 14-18, 1997, Cannes, France.
G. Karlsson and S. Nilsson,Fast address lookup for Internet routers, Proceedings of IEEE Broadband Communications 98, Apr. 1998 (12 pages).
V. Srinivasan and G. Varghese,Fast Address Lookups using Controlled Prefix Expansion, Proceedings of ACM Sigmetrics, Sep. 1998 (37 pages).
B. Plattner, J. Turner, G. Varghese, and M. Waldvogel,Scalable High Speed IP Routing Lookups, Proceedings of ACM SIGCOMM Conference 1997, pp. 25-36, Sep. 14-18, 1997, Cannes, France.
T.V. Lakshman and D. Stiliadis,High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching, Proceedings of ACM SIGCOMM Conference 1998, pp. 203-214, Aug. 31-Sep. 4, 1998, Vancouver, B.C., Canada.
D. Decasper, Z. Dittia, G. Parulkar, and B. Plattner,Router Plugins: A Modular and Extensible Software Framework for Modern High Performance Integrated Services Routers, Washington University Technical Report WUCS-98-08, 27 pages, Feb. 1998, St. Louis, MO.
P. Gupta, S. Lin, and N. McKeown,Routing Lookups in Hardware at Memory Access Speeds, IEEE Infocom vol. 3, pp. 1240-1247, Apr. 1998, San Francisco, CA.
B. Lampson, V. Srinivasan and G. Varghese,IP Lookups using Multiway and Multicolumn Search, IEEE Infocom '98, 25 pages, Apr. 1998, San Francisco, CA.
K. Sklower,A Tree-Based Routing Table for Berkeley Unix, Proceedings of the USENIX Winter 1991 Technical Conference, pp. 93-104, Jan. 1991, Dallas, TX.
J. Turner,Design and Analysis of Switching Systems, Washington University, St. Louis, MO, Jan. 1999.
Min Paul Seungkyu
Yazdani Nasser
George Keith M.
Pham Chi
Thompson & Coburn LLP
LandOfFree
Method and apparatus for building and using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for building and using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for building and using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3447061