US Patent No: 6,018,524
Number of patents in Portfolio can not be more than 2000
Scalable high speed IP routing lookups
Stats
-
Jan 25, 2000
Issued date -
Sep 9, 1997
filing date -
08/926,370
serial no -
In Force
status
Importance
Loading Importance Indicators...
Overall
|
US Family Size
|
International Coverage
|
|
Patent Longevity
|
Forward Citations
|
Abstract
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...
First Claim
Related Publications
Loading Related Publications...
- 15 United States
- 10 France
- 8 Japan
- 7 China
- 5 Korea
- 2 Other
Patent Owner(s)
| Patent Owner | Address | Total Patents |
|---|---|---|
| WASHINGTON UNIVERSITY | ST LOUIS, MO | 670 |
International Classification(s)
- [Classification Symbol]
- [Patents Count]
Inventor(s)
| Inventor Name | Address | # of filed Patents | Total Citations |
|---|---|---|---|
| Turner, Jonathan | Berlin, DE | 29 | 367 |
| Varghese, George | San Diego, CA | 44 | 1834 |
| Waldvogel, Marcel | Stein am Rhein, CH | 29 | 557 |
Cited Art
| Patent Info | (Count) | # Cites | Year |
|---|---|---|---|
|
|
|||
| 5,440,546 Packet switch | 31 | 1993 | |
|
|
|||
| 5,781,772 Compressed prefix matching database searching | 122 | 1995 | |
|
|
|||
| 5,651,002 Internetworking device with enhanced packet header translation and memory | 176 | 1995 | |
|
|
|||
| 4,464,650 Apparatus and method for compressing data signals and restoring the compressed data signals | 184 | 1981 | |
|
|
|||
| 5,613,069 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 | 114 | 1994 | |
Patent Citation Ranking
Forward Cites
| Patent Info | (Count) | # Cites | Year |
|---|---|---|---|
|
|
|||
| 6,889,181 Network flow switching and flow data export | 15 | 1997 | |
| 6,512,766 Enhanced internet packet routing lookup | 15 | 1997 | |
| 6,853,638 Route/service processor scalability via flow-based distribution of traffic | 5 | 1998 | |
| 6,308,219 Routing table lookup implemented using M-trie having nodes duplicated in multiple memory banks | 49 | 1998 | |
| 6,985,964 Network processor system including a central processor and at least one peripheral processor | 17 | 1999 | |
| 6,725,326 Techniques for efficient memory management for longest prefix match problems | 24 | 2000 | |
| 6,990,099 Multiple parallel packet routing lookup | 3 | 2001 | |
| 6,775,737 Method and apparatus for allocating and using range identifiers as input values to content-addressable memories | 39 | 2001 | |
| 6,970,971 Method and apparatus for mapping prefixes and values of a hierarchical space to other representations | 11 | 2002 | |
| 6,961,808 Method and apparatus for implementing and using multiple virtual portions of physical associative memories | 13 | 2002 | |
| 7,899,067 Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match | 1 | 2002 | |
| 7,558,775 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 | 1 | 2002 | |
| 7,299,317 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 | 4 | 2002 | |
| 7,382,787 Packet routing and switching device | 31 | 2002 | |
| 7,069,372 Processor having systolic array pipeline for processing data packets | 19 | 2002 | |
| 7,441,074 Methods and apparatus for distributing entries among lookup units and selectively enabling less than all of the lookup units when performing a lookup operation | 0 | 2002 | |
| 7,349,415 Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match | 11 | 2002 | |
| 7,313,666 Methods and apparatus for longest common prefix based caching | 11 | 2002 | |
| 7,352,739 Method and apparatus for storing tree data structures among and within multiple memory channels | 5 | 2003 | |
| 8,270,401 Packet routing and switching device | 0 | 2003 | |
| 7,710,991 Scalable packet routing and switching device and method | 3 | 2003 | |
| 7,525,904 Redundant packet routing and switching device and method | 5 | 2003 | |
| 7,453,883 Method for compressing route data in a router | 6 | 2003 | |
| 7,450,438 Crossbar apparatus for a forwarding table memory in a router | 5 | 2003 | |
| 7,415,472 Comparison tree data structures of particular use in performing lookup operations | 6 | 2003 | |
| 7,325,059 Bounded index extensible hash-based IPv6 address lookup method | 9 | 2003 | |
| 7,415,463 Programming tree data structures and handling collisions while performing lookup operations | 8 | 2003 | |
| 7,536,476 Method for performing tree based ACL lookups | 5 | 2003 | |
| 7,478,109 Identification of a longest matching prefix based on a search of intervals corresponding to the prefixes | 8 | 2004 | |
| 7,693,061 Data networking | 1 | 2004 | |
| 7,480,255 Data structure identifying for multiple addresses the reverse path forwarding information for a common intermediate node and its use | 2 | 2004 | |
| 7,260,518 Network flow switching and flow data report | 14 | 2004 | |
| 7,586,895 Performing extended lookups on MAC-based tables including level 3 multicast group destination addresses | 2 | 2005 | |
| 7,889,712 Methods and apparatus for providing loop free routing tables | 2 | 2005 | |
| 7,418,536 Processor having systolic array pipeline for processing data packets | 11 | 2006 | |
| 7,860,967 Network processor system including a central processor and at least one peripheral processor | 0 | 2006 | |
| 7,996,520 Behavioral classification of communication sessions using active session initiation | 0 | 2007 | |
| 7,613,134 Method and apparatus for storing tree data structures among and within multiple memory channels | 2 | 2008 | |
| 7,852,852 Method for compressing route data in a router | 1 | 2008 | |
| 8,270,399 Crossbar apparatus for a forwarding table memory in a router | 0 | 2008 | |
|
|
|||
| 7,426,518 System and method for efficiently searching a forwarding database that is split into a bounded number of sub-databases having a bounded size | 14 | 2003 | |
| 7,634,500 Multiple string searching using content addressable memory | 6 | 2003 | |
| 7,571,156 Network device, storage medium and methods for incrementally updating a forwarding database | 16 | 2004 | |
| 7,230,840 Content addressable memory with configurable class-based storage partition | 2 | 2004 | |
| 7,694,068 Re-entrant processing in a content addressable memory | 4 | 2005 | |
| 7,783,654 Multiple string searching using content addressable memory | 4 | 2006 | |
| 7,917,486 Optimizing search trees by increasing failure size parameter | 1 | 2007 | |
| 7,860,849 Optimizing search trees by increasing success size parameter | 0 | 2007 | |
| 7,676,444 Iterative compare operations using next success size bitmap | 1 | 2007 | |
| 7,636,717 Method and apparatus for optimizing string search operations | 5 | 2007 | |
| 7,440,304 Multiple string searching using ternary content addressable memory | 11 | 2007 | |
| 7,933,282 Packet classification device for storing groups of rules | 1 | 2007 | |
| 7,904,642 Method for combining and storing access control lists | 1 | 2007 | |
| 7,889,727 Switching circuit implementing variable string matching | 0 | 2008 | |
| 7,978,709 Packet matching method and system | 0 | 2008 | |
| 8,073,856 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 | |
| 7,969,758 Multiple string searching using ternary content addressable memory | 0 | 2008 | |
| 8,438,330 Updating cam arrays using prefix length distribution prediction | 0 | 2011 | |
|
|
|||
| 6,172,986 Mobile node, mobile agent and network system | 100 | 1998 | |
| 6,868,089 Mobile node, mobile agent-and network system | 2 | 2000 | |
| 6,888,845 Mobile node, mobile agent and network system | 3 | 2002 | |
| 6,785,293 Mobile node, mobile agent and network system | 0 | 2002 | |
| 6,724,775 Mobile node, mobile agent and network system | 2 | 2002 | |
| 7,805,605 Server, terminal control device and terminal authentication method | 2 | 2004 | |
| 7,453,905 Mobile node, mobile agent and network system | 0 | 2005 | |
| 7,643,447 Mobile node, mobile agent and network system | 17 | 2008 | |
|
|
|||
| 6,493,698 String search scheme in a distributed architecture | 12 | 1999 | |
| 7,111,071 Longest prefix match for IP routers | 24 | 2000 | |
| 7,293,020 String search scheme in a distributed architecture | 3 | 2002 | |
| 7,039,018 Technique to improve network routing using best-match and exact-match techniques | 10 | 2002 | |
| 7,917,509 String search scheme in a distributed architecture | 0 | 2007 | |
| 8,321,440 String search scheme in a distributed architecture | 2011 | ||
|
|
|||
| 6,256,307 Local area network receive filter | 17 | 1998 | |
| 6,396,842 Method of searching using longest match based Randix Search Trie with variable length keys and having prefix capability | 35 | 1998 | |
| 6,549,521 Methods of managing dynamic decision trees | 7 | 1999 | |
| 6,320,848 Methods of altering dynamic decision trees | 31 | 1999 | |
| 6,763,348 Method and apparatus for searching databases employing a trie search structure | 1 | 2000 | |
|
|
|||
| 6,385,649 Routers and methods for optimal routing table compression | 43 | 1998 | |
| 6,266,665 Indexing and searching across multiple sorted arrays | 8 | 1998 | |
| 7,322,023 Computer programming language statement building and information tool with non obstructing passive assist window | 15 | 2001 | |
| 7,543,278 System and method for making a user interface element visible | 1 | 2004 | |
| 7,814,461 Computer programming language statement building and information tool | 1 | 2006 | |
|
|
|||
| 6,526,055 Method and apparatus for longest prefix address lookup | 49 | 1998 | |
| 7,127,704 Interactive software engineering tool with support for embedded lexical contexts | 42 | 2001 | |
| 7,117,479 Language-sensitive whitespace adjustment in a software engineering tool | 0 | 2001 | |
| 7,386,834 Undo/redo technique for token-oriented representation of program code | 4 | 2002 | |
| 7,339,930 Method and apparatus for performing an address lookup using a multi-bit trie with backtracking | 2 | 2002 | |
|
|
|||
| 6,522,632 Apparatus and method for efficient prefix search | 37 | 1998 | |
| 6,430,527 Prefix search circuitry and method | 53 | 1998 | |
| 7,130,847 Prefix search method | 6 | 2003 | |
| 7,668,890 Prefix search circuitry and method | 1 | 2006 | |
|
|
|||
| 7,523,218 O(log n) dynamic router tables for prefixes and ranges | 4 | 2003 | |
| 7,509,300 Dynamic IP router tables using highest-priority matching | 1 | 2003 | |
| 7,444,318 Prefix partitioning methods for dynamic router tables | 3 | 2003 | |
| 7,990,979 Recursively partitioned static IP router tables | 0 | 2007 | |
|
|
|||
| 7,372,917 Digital algorithm for on-line ACPR optimization in polar RF transmitters | 5 | 2004 | |
| 7,072,885 Method and apparatus for performing a binary search on an expanded tree | 4 | 2004 | |
| 7,606,231 Pipeline architecture for a network device | 1 | 2005 | |
|
|
|||
| 6,990,070 Method and apparatus for adjusting packet transmission volume from a source | 41 | 1999 | |
| 6,993,025 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 | 1999 | |
| 7,324,519 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 | 2005 | |
|
|
|||
| 8,001,272 Obtaining a valid international destination address | 1 | 2004 | |
| 7,774,502 Determining an international destination address | 1 | 2004 | |
| 7,774,503 Universal address recognition for text-capable communication devices | 0 | 2006 | |
|
|
|||
| 6,888,838 Fast IP route lookup with configurable processor and compressed routing table | 17 | 2001 | |
| 7,274,697 Fast IP route lookup with 16/K and 16/Kc compressed data structures | 3 | 2001 | |
| 7,227,842 Fast IP packet classification with configurable processor | 43 | 2002 | |
|
|
|||
| 6,560,610 Data structure using a tree bitmap and method for rapid classification of data in a database | 72 | 1999 | |
| 6,728,732 Data structure using a tree bitmap and method for rapid classification of data in a database | 11 | 2003 | |
| 7,249,149 Tree bitmap data structures and their use in performing lookup operations | 4 | 2004 | |
|
|
|||
| 8,275,804 Distributed data store with a designated master to ensure consistency | 0 | 2009 | |
| 8,131,781 Anti-item for deletion of content in a distributed datastore | 0 | 2011 | |
|
|
|||
| 6,792,423 Hybrid longest prefix match and fixed match searches | 11 | 2000 | |
| 6,925,503 Method and system for performing a longest prefix match search | 1 | 2001 | |
|
|
|||
| 6,788,695 System and method capable of carrying out high-speed IP routing by the use of a binary tree comprising a reduced number of nodes | 3 | 2000 | |
| 7,272,140 Address retrieval apparatus | 1 | 2003 | |
|
|
|||
| 6,173,384 Method of searching for a data element in a data structure | 54 | 1998 | |
| 6,820,120 Routing of data packets in heterogeneous networks | 9 | 2000 | |
|
|
|||
| 6,421,342 Packet forwarding apparatus and method using pipelined node address processing | 54 | 1998 | |
| 6,804,241 Packet forwarding apparatus and method using pipelined node address processing | 7 | 2002 | |
|
|
|||
| 6,967,959 Method for forming a database to route a data packet and method for routing and a router using the method thereof | 1 | 2001 | |
| 7,031,320 Apparatus and method for performing high-speed IP route lookup and managing routing/forwarding tables | 30 | 2001 | |
|
|
|||
| 7,289,979 Parallel asymmetric binary search on lengths | 16 | 2003 | |
|
|
|||
| 7,433,355 Filter based longest prefix match algorithm | 5 | 2004 | |
|
|
|||
| 7,272,746 Redundancy scheme for network processing systems | 12 | 2003 | |
|
|
|||
| 6,963,924 IP routing lookup scheme and system for multi-gigabit switching routers | 16 | 1999 | |
|
|
|||
| 6,658,482 Method for speeding up internet protocol address lookups with efficient use of memory | 38 | 1999 | |
|
|
|||
| 6,546,391 High-speed lookup method and high-speed lookup apparatus | 40 | 1999 | |
|
|
|||
| 8,046,492 Offset independent filtering | 0 | 2007 | |
|
|
|||
| 7,039,641 Modular packet classification | 27 | 2001 | |
|
|
|||
| 6,956,858 Network routing table and packet routing method | 51 | 2001 | |
|
|
|||
| 6,633,548 Method and apparatus for ternary content addressable memory (TCAM) table management | 16 | 2001 | |
|
|
|||
| 6,985,483 Methods and systems for fast packet forwarding | 12 | 2001 | |
|
|
|||
| 7,570,644 Routing method for a telecommunications network and router for implementing said method | 2 | 2003 | |
|
|
|||
| 7,433,871 Efficient ipv4/ipv6 best matching prefix method and apparatus | 3 | 2003 | |
|
|
|||
| 6,680,916 Method for using a balanced tree as a base for a routing table | 4 | 2002 | |
|
|
|||
| 7,860,106 System and method for routing table computation and analysis | 0 | 2006 | |
|
|
|||
| 8,335,780 Scalable high speed relational processor for databases and networks | 0 | 2009 | |
Maintenance Fees
| Fee | Large entity fee | small entity fee | micro entity fee | due date |
|---|
| Fee | Large entity fee | small entity fee | micro entity fee |
|---|---|---|---|
| Surcharge after expiration - Late payment is unavoidable | $700.00 | $350.00 | $175.00 |
| Surcharge after expiration - Late payment is unintentional | $1,640.00 | $820.00 | $410.00 |