Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2006-04-18
2006-04-18
Ton, Dang (Department: 2666)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
Reexamination Certificate
active
07031320
ABSTRACT:
A method for constructing routing/forwarding tables for an IP address lookup using a skip list. The method comprises dividing a prefix length range of an IP address in a preset method; creating a header node having a maximum level based on a number of clusters divided into the prefix length range, the header node pointing every node in the skip list; and creating subnodes by the number of the divided clusters, the subnodes each having the divided prefix length range as a key.
REFERENCES:
patent: 5671406 (1997-09-01), Lubbers et al.
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5796966 (1998-08-01), Simcoe et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6014659 (2000-01-01), Wilkinson, III et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6061712 (2000-05-01), Tzeng
patent: 6067574 (2000-05-01), Tzeng
patent: 2005/0182752 (2005-08-01), Rojer
Japanese Office Action in connection with Korean Patent Application No. 2001-7568, issued on Sep. 6, 2005.
IEEE INFORMCOM'01, vol. 3, pp1444-1453 to F. Ergun et al., entitledScalable High Speed IP Routing Lookups, published on Apr. 2001.
Keshav, S. and Sharma, R., Issues and Trends in Router Design, IEEE Communications Magazine, pp. 144-151, May, 1998.
Kumar, V. and Lakshman, T. and Stiliadis, D., Beyond Best Effort: Router Architectures for the Differentiated Services of Tomorrow's Internet, IEEE Communications Magazine, pp. 152-164,May,1998.
Chan, H., Alnuweiri, H. and Leung, V., A Framework for Optimizing the Cost and Performance of Next-Generation IP Routers, IEEE Journal of Selected Areas in Communications, vol. 17, No. 6, pp. 1013-1029, Jun. 1999.
Partridge, C. et al., A 50-Gb/s IP Router, IEEE/ACM Trans. on Networking, vol. 6, No. 3, pp. 237-248, 1998.
Metz, C., IP Routers: New Tool for Gigabit Networking, IEEE Internet Computing, pp. 14-18, Nov.-Dec., 1998.
Asthana, A., Delph, C., Jagadish, H., and Krzyanowski, P., “Towards a gigabit IP router”, J. High Speed Network, vol. 1, No. 4, pp. 281-288, 1992.
RFC 1518, An Architecture for IP Address Allocation with CIDR, Sep. 1993.
RFC 1517, Applicability Statement for the Implementation of Classless Inter-Domain Routing (CIDR), Sep. 1993.
Doeringer, W., Karjoth, G. and Nassehi, M., Routing on Longest-Matching Prefixes, IEEE/ACM Trans. on Networking, vol. 4, No. 1, pp. 86-97, Feb., 1996.
Degermark, M., Brodnik, A., Carlsson, S. and Pink, S., Small Forwarding Tables for Fast Routing Lookups, In Proceedings of ACM SIGCOMM '97, pp. 3-14, Cannes, France, 1997.
Srinivasan, V. and Varghese, G., Faster IP Lookups using Controlled Prefix Expansion, In Proceedings of ACM Sigmetrics '98 Conf., pp. 1-11, 1998.
Lampson, B., Srinivasan, V. and Varghese, G., IP Lookups using Multiway and Multicolumn Search, In IEEE Infocom, pp. 1248-1256, 1998.
Tzeng, H. and Pryzygienda, T., On Fast Address-Lookup Algorithms,IEEE Journal on Selected Areas in Communications, vol. 17, No. 6, pp. 1067-1082, Jun., 1999.
Waldvogel, M., Varghese, G., Turner, J. and Plattner, B., Scalable High Speed IP Routing Lookups, In Proceedings of ACM SIGCOMM '97, Cannes, France, pp. 25-37, 1997.
Waldvogel, M., Varghese, G., Turner, J. and Plattner, B., Scalable Best Matching Prefix Lookups, In Proceedings of PODC '98, Puerto Vallarta, p., 1998.
Kijkanjanarat, T. and Chao, H., Fast IP Lookups Using a Two-trie Data Structure, In Proceedings of Globecom'99, Global Telecommunication Conference 1999, vol. 2, pp. 1570-1575.
Nillson, S. and Karlsoson, G., IP-Addresses Lookup Using LC-Tries, IEEE Journal on Selected Areas in Communications, vol. 17, No. 16, pp. 1083-1092, 1999.
Crescenzi, P., Dardini, L. and Grossi, R., “IP Address Lookup Made Fast and Simple”, Technical Report TR-99-01, Dipartimento di Informatica, University a Di Pisa, 1999.
Gupta, P., Lin, S. and McKeown, N., Routing Lookups in Hardware at Memory Access Speeds, In Proceedings of IEEE INFOCOM '98 Conf., pp. 1240-1247, 1998.
McAuley, A. and Francis, P., Fast Routing Table Lookup Using CAMs, In Proceedings of IEEE INFOCOM '93, vol. 3, pp. 1382-1391, 1993.
Huang, N. and Zhao, S., A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers,IEEE Journal on Selected Areas in Communications, vol. 17, No. 6, pp. 1093-1104, Jun., 1999.
Pugh, W., Skip Lists: A Probabilistic Alternatives to Balanced Trees, CACM 33(6), pp. 668-676, 1990.
Sleator, D. and Tarjan, R., Self-Adjusting Binary Search Trees, JACM, vol. 32, No. 3, Jul. 1985.
IPMA (Internet Performance Measurement and Analysis), http:/
ic.merit.edu/ipma.
Cormen, T., Leiserson, C. and Rivest, R., Introduction to Aldorithms, McGraw-Hill, New York, Jun. 1990.
Bushnell , Esq. Robert E.
Samsung Electronics Co,. Ltd.
Ton Dang
LandOfFree
Apparatus and method for performing high-speed IP route... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for performing high-speed IP route..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for performing high-speed IP route... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3580943