Scalable high speed IP routing lookups

Number of patents in Portfolio can not be more than 2000

United States of America Patent

PATENT NO 6018524
SERIAL NO

08926370

Stats

ATTORNEY / AGENT: (SPONSORED)

Importance

Loading Importance Indicators... loading....

Abstract

See full text

A method and apparatus for an exponentially faster technique than is presently utilized in routers for looking-up destination addresses and matching them to a prefix in order to determine an output data link for routing of the data message to a destination. The basic algorithm includes arranging the prefix and corresponding output data link information in sub-databases arranged by prefix length and then using a multi-step prefix length binary search algorithm to sort through the sub-databases to determine a best matching prefix for routing of the data packet. Various refinements of the basic algorithm are disclosed to further enhance the search time including adding markers representative of sub-database entries having a longer prefix length and also various searching methodologies to minimize the number of searching steps including rope searching in various formats. Thus, methodologies are disclosed for building the sub-databases, as appropriate to implement the corresponding novel search routines and perform the novel search routines themselves, and the router which implements all of the foregoing. Many of the inventive features disclosed herein are applicable to other routing DPJ protocols such as OSI Routing, call routing and telephone DPJ networks, and string matching problems.

Loading the Abstract Image... loading....

First Claim

See full text

Family

Loading Family data... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
WASHINGTON UNIVERSITYST LOUIS, MO248

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Turner, Jonathan St. Louis, MO 35 639
Varghese, George St. Louis, MO 45 2760
Waldvogel, Marcel Winterthur, CH 21 879

Cited Art Landscape

Patent Info (Count) # Cites Year
 
HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P. (1)
* 5651002 Internetworking device with enhanced packet header translation and memory 213 1995
 
Sperry Corporation (1)
* 4464650 Apparatus and method for compressing data signals and restoring the compressed data signals 232 1981
 
ENTERASYS NETWORKS, INC. (1)
* 5781772 Compressed prefix matching database searching 158 1995
 
WALKER, TONY (1)
* 5613069 Non-blocking packet switching network with dynamic routing codes having incoming packets diverted and temporarily stored in processor inputs when network ouput is not available 157 1994
 
CARNEGIE MELLON UNIVERSITY (1)
* 5440546 Packet switch 31 1993
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
Other [Check patent profile for assignment information] (8)
* 2003/0204,493 String search scheme in a distributed architecture 0 2002
* 2005/0157,712 Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match 72 2002
* 2005/0018,683 IP address storage technique for longest prefix match 19 2003
* 2005/0190,713 Mobile node, mobile agent and network system 1 2005
* 2006/0117,088 Network processor system 2 2006
* 2009/0046,635 MOBILE NODE, MOBILE AGENT AND NETWORK SYSTEM 1 2008
8335780 Scalable high speed relational processor for databases and networks 0 2009
* 2009/0265,320 SCALABLE HIGH SPEED RELATIONAL PROCESSOR FOR DATABASES AND NETWORKS 3 2009
 
TRANSWITCH CORPORATION (2)
* 7433871 Efficient ipv4/ipv6 best matching prefix method and apparatus 6 2003
* 2005/0171,959 Efficient ipv4/ipv6 best matching prefix method and apparatus 113 2003
 
CHEN, WEN-SHYEN ERIC (1)
* 6658482 Method for speeding up internet protocol address lookups with efficient use of memory 51 1999
 
HEWLETT PACKARD ENTERPRISE DEVELOPMENT LP (2)
* 6256307 Local area network receive filter 34 1998
* 6763348 Method and apparatus for searching databases employing a trie search structure 1 2000
 
SYNIVERSE ICX CORPORATION (9)
* 9143477 Address recognition database 0 2004
8001272 Obtaining a valid international destination address 4 2004
7774502 Determining an international destination address 5 2004
* 2005/0086,378 Address recognition database 2 2004
* 2005/0055,461 Determining an international destination address 5 2004
7774503 Universal address recognition for text-capable communication devices 2 2006
* 2006/0174,038 Universal address recognition for text-capable communication devices 0 2006
8571065 Method and apparatus for assigning a virtual address to and text-messaging to multiple text-capable destination entities 0 2008
* 2008/0273,535 METHOD AND APPARATUS FOR ASSIGNING A VIRTUAL ADDRESS TO AND TEXT-MESSAGING TO MULTIPLE TEXT-CAPABLE DESTINATION ENTITIES 0 2008
 
NORTH CAROLINA STATE UNIVERSITY (2)
6985483 Methods and systems for fast packet forwarding 17 2001
* 2003/0091,043 Methods and systems for fast packet forwarding 10 2001
 
JUNIPER NETWORKS, INC. (1)
* 8046492 Offset independent filtering 0 2007
 
SAMSUNG ELECTRONICS CO., LTD. (4)
* 6967959 Method for forming a database to route a data packet and method for routing and a router using the method thereof 1 2001
* 2003/0041,169 Method for forming a database to route a data packet and method for routing and a router using the method thereof 0 2001
7031320 Apparatus and method for performing high-speed IP route lookup and managing routing/forwarding tables 44 2001
* 2002/0118,682 Apparatus and method for performing high-speed IP route lookup and managing routing/forwarding tables 21 2001
 
NOKIA TECHNOLOGIES OY (1)
6633548 Method and apparatus for ternary content addressable memory (TCAM) table management 25 2001
 
HITACHI, LTD. (9)
* 6172986 Mobile node, mobile agent and network system 112 1998
6868089 Mobile node, mobile agent-and network system 2 2000
6888845 Mobile node, mobile agent and network system 4 2002
6785293 Mobile node, mobile agent and network system 0 2002
6724775 Mobile node, mobile agent and network system 2 2002
* 7805605 Server, terminal control device and terminal authentication method 6 2004
* 2004/0205,211 Server, terminal control device and terminal authentication method 24 2004
7453905 Mobile node, mobile agent and network system 2 2005
7643447 Mobile node, mobile agent and network system 19 2008
 
ORACLE AMERICA, INC. (8)
* 6526055 Method and apparatus for longest prefix address lookup 51 1998
* 7127704 Interactive software engineering tool with support for embedded lexical contexts 64 2001
* 2002/0100,016 Interactive software engineering tool with support for embedded lexical contexts 12 2001
7117479 Language-sensitive whitespace adjustment in a software engineering tool 3 2001
* 2003/0066,058 Language-sensitive whitespace adjustment in a software engineering tool 3 2001
7386834 Undo/redo technique for token-oriented representation of program code 8 2002
* 7339930 Method and apparatus for performing an address lookup using a multi-bit trie with backtracking 3 2002
* 2004/0100,960 Method and apparatus for performing an address lookup using a multi-bit trie with backtracking 2 2002
 
AT&T INTELLECTUAL PROPERTY I, L.P. (7)
9065726 Methods and apparatus to utilize route parameter sets for exchanging routes in a communication network 1 2010
* 9407676 Method and apparatus for distributing media content 0 2013
* 2015/0149,653 METHOD AND APPARATUS FOR DISTRIBUTING MEDIA CONTENT 1 2013
9300575 Methods and apparatus to utilize route parameter sets for exchanging routes in a communication network 1 2015
9584398 Methods and apparatus to utilize route parameter sets for exchanging routes in a communication network 0 2016
9509849 System and methods for enhanced multimedia in VoIP networks 0 2016
9781272 System and methods for enhanced multimedia in VoIP networks 0 2016
 
NEC CORPORATION (1)
* 6788695 System and method capable of carrying out high-speed IP routing by the use of a binary tree comprising a reduced number of nodes 4 2000
 
FUTUREWEI TECHNOLOGIES, INC. (7)
6522632 Apparatus and method for efficient prefix search 45 1998
* 6430527 Prefix search circuitry and method 59 1998
7130847 Prefix search method 10 2003
7668890 Prefix search circuitry and method 1 2006
* 2007/0038,626 Prefix search circuitry and method 11 2006
* 8923298 Optimized trie-based address lookup 0 2012
* 9680747 Internet protocol and Ethernet lookup via a unified hashed trie 0 2013
 
MICROSOFT TECHNOLOGY LICENSING, LLC (9)
* 6385649 Routers and methods for optimal routing table compression 54 1998
* 6266665 Indexing and searching across multiple sorted arrays 10 1998
* 2002/0143,918 Internet protocol (IP) address proximity detection and application to peer provider location 32 2001
7322023 Computer programming language statement building and information tool with non obstructing passive assist window 43 2001
* 2002/0095,658 Computer programming language statement building and information tool 75 2001
* 7543278 System and method for making a user interface element visible 7 2004
* 2006/0085,764 System and method for making a user interface element visible 10 2004
7814461 Computer programming language statement building and information tool 2 2006
* 2007/0006,142 Computer programming language statement building and information tool 2 2006
 
WASHINGTON UNIVERSITY (1)
* 6728732 Data structure using a tree bitmap and method for rapid classification of data in a database 24 2003
 
TUT SYSTEMS, INC. (1)
6680916 Method for using a balanced tree as a base for a routing table 4 2002
 
APPLIED INVENTION, LLC (4)
8275804 Distributed data store with a designated master to ensure consistency 0 2009
* 2010/0070,473 Distributed Data Store with a Designated Master to Ensure Consistency 2 2009
* 8131781 Anti-item for deletion of content in a distributed datastore 0 2011
8719313 Distributed data store with a designated master to ensure consistency 0 2012
 
UNIVERSITY OF FLORIDA RESEARCH FOUNDATION, INC. (7)
7523218 O(log n) dynamic router tables for prefixes and ranges 8 2003
* 7509300 Dynamic IP router tables using highest-priority matching 15 2003
* 2004/0105,422 Dynamic IP router tables using highest-priority matching 19 2003
* 7444318 Prefix partitioning methods for dynamic router tables 5 2003
* 2004/0258,061 Prefix partitioning methods for dynamic router tables 2 2003
* 2004/0141,509 Partitioning methods for dynamic router tables 6 2003
7990979 Recursively partitioned static IP router tables 6 2007
 
MINERAL LASSEN LLC (2)
* 6956858 Network routing table and packet routing method 67 2001
* 2002/0080,798 Network routing table and packet routing method 11 2001
 
AVAGO TECHNOLOGIES GENERAL IP (SINGAPORE) PTE. LTD. (30)
* 2002/0089,937 Packet matching method and system 76 2001
* 7426518 System and method for efficiently searching a forwarding database that is split into a bounded number of sub-databases having a bounded size 23 2003
* 2004/0193,619 System and method for efficiently searching a forwarding database that is split into a bounded number of sub-databases having a bounded size 10 2003
7634500 Multiple string searching using content addressable memory 12 2003
* 7571156 Network device, storage medium and methods for incrementally updating a forwarding database 50 2004
* 7372917 Digital algorithm for on-line ACPR optimization in polar RF transmitters 9 2004
* 7230840 Content addressable memory with configurable class-based storage partition 3 2004
* 2005/0063,241 Content addressable memory with configurable class-based storage partition 4 2004
* 7072885 Method and apparatus for performing a binary search on an expanded tree 4 2004
* 2005/0071,501 Method and apparatus for performing a binary search on an expanded tree 0 2004
* 7606231 Pipeline architecture for a network device 2 2005
7694068 Re-entrant processing in a content addressable memory 11 2005
7783654 Multiple string searching using content addressable memory 16 2006
7917486 Optimizing search trees by increasing failure size parameter 3 2007
7860849 Optimizing search trees by increasing success size parameter 9 2007
7676444 Iterative compare operations using next success size bitmap 5 2007
7636717 Method and apparatus for optimizing string search operations 29 2007
7440304 Multiple string searching using ternary content addressable memory 26 2007
7933282 Packet classification device for storing groups of rules 17 2007
7904642 Method for combining and storing access control lists 14 2007
7889727 Switching circuit implementing variable string matching 3 2008
* 2008/0212,581 Switching Circuit Implementing Variable String Matching 14 2008
* 7978709 Packet matching method and system 5 2008
* 8073856 System and method for efficiently searching a forwarding database that is split into a bounded number of sub-databases having a bounded size 0 2008
7969758 Multiple string searching using ternary content addressable memory 0 2008
* 2009/0012,958 MULTIPLE STRING SEARCHING USING TERNARY CONTENT ADDRESSABLE MEMORY 11 2008
8566337 Pipeline architecture for a network device 1 2009
8438330 Updating cam arrays using prefix length distribution prediction 0 2011
9032142 System and method for storing integer ranges in a memory 0 2012
8943268 Ternary content addressable memory (TCAM) storage system 2 2012
 
RAKUTEN, INC. (2)
* 7272140 Address retrieval apparatus 1 2003
* 2004/0136,407 Address retrieval apparatus 2 2003
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (2)
6792423 Hybrid longest prefix match and fixed match searches 30 2000
* 2003/0149,791 System and method for routing data by a server 44 2002
 
HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P. (3)
* 6396842 Method of searching using longest match based Randix Search Trie with variable length keys and having prefix capability 39 1998
6549521 Methods of managing dynamic decision trees 16 1999
* 6320848 Methods of altering dynamic decision trees 39 1999
 
LUCENT TECHNOLOGIES INC. (2)
* 7039641 Modular packet classification 48 2001
* 2002/0023,089 Modular packet classification 50 2001
 
CISCO TECHNOLOGY, INC. (54)
6889181 Network flow switching and flow data export 28 1997
6512766 Enhanced internet packet routing lookup 17 1997
* 6853638 Route/service processor scalability via flow-based distribution of traffic 10 1998
* 6308219 Routing table lookup implemented using M-trie having nodes duplicated in multiple memory banks 57 1998
* 6985964 Network processor system including a central processor and at least one peripheral processor 17 1999
6725326 Techniques for efficient memory management for longest prefix match problems 44 2000
6990099 Multiple parallel packet routing lookup 5 2001
6775737 Method and apparatus for allocating and using range identifiers as input values to content-addressable memories 58 2001
6970971 Method and apparatus for mapping prefixes and values of a hierarchical space to other representations 17 2002
* 6961808 Method and apparatus for implementing and using multiple virtual portions of physical associative memories 14 2002
7899067 Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match 5 2002
* 2004/0008,634 Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match 13 2002
7558775 Methods and apparatus for maintaining sets of ranges typically using an associative memory and for using these ranges to identify a matching range based on a query point or query range and to maintain sorted elements for use such as in providing priority queue operations 6 2002
7299317 Assigning prefixes to associative memory classes based on a value of a last bit of each prefix and their use including but not limited to locating a prefix and for maintaining a Patricia tree data structure 10 2002
7382787 Packet routing and switching device 104 2002
7069372 Processor having systolic array pipeline for processing data packets 28 2002
7441074 Methods and apparatus for distributing entries among lookup units and selectively enabling less than all of the lookup units when performing a lookup operation 2 2002
7349415 Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match 23 2002
7313666 Methods and apparatus for longest common prefix based caching 28 2002
7352739 Method and apparatus for storing tree data structures among and within multiple memory channels 26 2003
8270401 Packet routing and switching device 69 2003
7710991 Scalable packet routing and switching device and method 8 2003
7525904 Redundant packet routing and switching device and method 10 2003
* 7453883 Method for compressing route data in a router 12 2003
7450438 Crossbar apparatus for a forwarding table memory in a router 7 2003
7415472 Comparison tree data structures of particular use in performing lookup operations 22 2003
* 2004/0230,583 Comparison tree data structures of particular use in performing lookup operations 5 2003
7325059 Bounded index extensible hash-based IPv6 address lookup method 33 2003
* 2004/0230,696 Bounded index extensible hash-based IPv6 address lookup method 9 2003
7415463 Programming tree data structures and handling collisions while performing lookup operations 21 2003
* 2004/0254,909 Programming routes and access control lists in comparison tree data structures and their use such as in performing lookup operations 44 2003
7536476 Method for performing tree based ACL lookups 31 2003
7478109 Identification of a longest matching prefix based on a search of intervals corresponding to the prefixes 14 2004
7693061 Data networking 5 2004
* 2006/0171,316 Data networking 19 2004
7480255 Data structure identifying for multiple addresses the reverse path forwarding information for a common intermediate node and its use 8 2004
* 2005/0265,328 Data structure identifying for multiple addresses the reverse path forwarding information for a common intermediate node and its use 10 2004
7260518 Network flow switching and flow data report 36 2004
* 7586895 Performing extended lookups on MAC-based tables including level 3 multicast group destination addresses 7 2005
* 2006/0221,960 Performing extended lookups on mac-based tables 81 2005
7889712 Methods and apparatus for providing loop free routing tables 5 2005
* 2006/0159,034 Method for providing loop free routing table in a router 15 2005
7418536 Processor having systolic array pipeline for processing data packets 12 2006
* 2006/0117,126 Processing unit for efficiently determining a packet's destination in a packet-switched network 3 2006
7860967 Network processor system including a central processor and at least one peripheral processor 0 2006
7996520 Behavioral classification of communication sessions using active session initiation 2 2007
7613134 Method and apparatus for storing tree data structures among and within multiple memory channels 24 2008
* 2008/0181,139 Method And Apparatus For Storing Tree Data Structures Among And Within Multiple Memory Channels 70 2008
7852852 Method for compressing route data in a router 5 2008
* 2009/0046,724 METHOD FOR COMPRESSING ROUTE DATA IN A ROUTER 4 2008
8270399 Crossbar apparatus for a forwarding table memory in a router 1 2008
* 8687621 Dynamically right-sizing prefixes for network and application performance 1 2009
* 2010/0309,795 DYNAMICALLY RIGHT-SIZING PREFIXES FOR NETWORK AND APPLICATION PERFORMANCE 3 2009
9094237 Packet routing and switching device 0 2012
 
ALCATEL LUCENT (2)
7433355 Filter based longest prefix match algorithm 10 2004
* 2005/0175,010 Filter based longest prefix match algorithm 34 2004
 
UNIVERSITY OF WASHINGTON (2)
6560610 Data structure using a tree bitmap and method for rapid classification of data in a database 192 1999
7249149 Tree bitmap data structures and their use in performing lookup operations 19 2004
 
FUJITSU LIMITED (1)
* 6546391 High-speed lookup method and high-speed lookup apparatus 47 1999
 
SUN MICROSYSTEMS, INC. (4)
* 2004/0003,374 Efficient computation of character offsets for token-oriented representation of program code 7 2002
* 2004/0003,373 Token-oriented representation of program code with support for textual editing thereof 7 2002
* 2004/0225,998 Undo/Redo technique with computed of line information in a token-oriented representation of program code 12 2003
* 2004/0225,997 Efficient computation of line information in a token-oriented representation of program code 5 2003
 
PARITY NETWORKS LLC (2)
* 6421342 Packet forwarding apparatus and method using pipelined node address processing 58 1998
* 6804241 Packet forwarding apparatus and method using pipelined node address processing 9 2002
 
RPX CLEARINGHOUSE LLC (4)
6990070 Method and apparatus for adjusting packet transmission volume from a source 70 1999
* 6993025 Method and apparatus for encoding a plurality of pre-defined codes into a search key and for locating a longest matching pre-defined code 1 1999
7324519 Method and apparatus for encoding a plurality of pre-defined codes into a search key and for locating a longest matching pre-defined code 2 2005
* 2005/0157,724 Method and apparatus for encoding a plurality of pre-defined codes into a search key and for locating a longest matching pre-defined code 0 2005
 
BROADWEB CORPORATION (1)
* 6963924 IP routing lookup scheme and system for multi-gigabit switching routers 23 1999
 
Tensilica, Inc. (4)
* 6888838 Fast IP route lookup with configurable processor and compressed routing table 25 2001
* 7274697 Fast IP route lookup with 16/K and 16/Kc compressed data structures 7 2001
* 2002/0172,203 Fast IP route lookup with 16/K and 16/Kc compressed data structures 10 2001
7227842 Fast IP packet classification with configurable processor 74 2002
 
INTEL CORPORATION (6)
* 6493698 String search scheme in a distributed architecture 33 1999
* 7111071 Longest prefix match for IP routers 33 2000
7293020 String search scheme in a distributed architecture 4 2002
* 7039018 Technique to improve network routing using best-match and exact-match techniques 21 2002
7917509 String search scheme in a distributed architecture 0 2007
8321440 String search scheme in a distributed architecture 1 2011
 
INTELLECTUAL DISCOVERY, INC. (2)
6925503 Method and system for performing a longest prefix match search 3 2001
* 2003/0023,581 Method and system for performing a longest prefix match search 2 2001
 
AUDIOCODES, INC. (2)
7272746 Redundancy scheme for network processing systems 17 2003
* 2005/0050,171 Redundancy scheme for network processing systems 7 2003
 
ALCATEL (3)
* 2005/0114,393 Dynamic forwarding method using binary search 4 2003
* 7289979 Parallel asymmetric binary search on lengths 17 2003
* 2005/0131,867 Parallel asymmetric binary search on lengths 19 2003
 
CISCO SYSTEMS ISRAEL LTD. (1)
* 2005/0195,743 Real time charging of pre-paid accounts 29 2004
 
STMicroelectronics S.A. (1)
* 7570644 Routing method for a telecommunications network and router for implementing said method 2 2003
 
WIND RIVER SYSTEMS, INC. (2)
* 7860106 System and method for routing table computation and analysis 2 2006
* 2007/0189,284 System and method for routing table computation and analysis 66 2006
 
Transdermal Biotechnology, Inc. (1)
* 2004/0197,391 Stable topical drug delivery compositions 64 2003
 
NORTEL NETWORKS LIMITED (2)
* 6173384 Method of searching for a data element in a data structure 63 1998
* 6820120 Routing of data packets in heterogeneous networks 11 2000
* Cited By Examiner