US Patent No: 6,018,524

Number of patents in Portfolio can not be more than 2000

Scalable high speed IP routing lookups

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
UNIVERSITY OF WASHINGTONSEATTLE, WA1512

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Turner, Jonathan St. Louis, MO 35 572
Varghese, George St. Louis, MO 44 2450
Waldvogel, Marcel Winterthur, CH 21 797

Cited Art Landscape

Patent Info (Count) # Cites Year
 
HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P. (1)
* 5,651,002 Internetworking device with enhanced packet header translation and memory 205 1995
 
Sperry Corporation (1)
* 4,464,650 Apparatus and method for compressing data signals and restoring the compressed data signals 217 1981
 
ENTERASYS NETWORKS, INC. (1)
* 5,781,772 Compressed prefix matching database searching 150 1995
 
WALKER, TONY (1)
* 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 150 1994
 
CARNEGIE MELLON UNIVERSITY (1)
* 5,440,546 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] (6)
* 2003/0204,493 String search scheme in a distributed architecture 0 2002
* 2005/0018,683 IP address storage technique for longest prefix match 15 2003
* 2005/0190,713 Mobile node, mobile agent and network system 1 2005
* 2009/0046,635 MOBILE NODE, MOBILE AGENT AND NETWORK SYSTEM 1 2008
8,335,780 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)
* 7,433,871 Efficient ipv4/ipv6 best matching prefix method and apparatus 6 2003
* 2005/0171,959 Efficient ipv4/ipv6 best matching prefix method and apparatus 81 2003
 
CHEN, WEN-SHYEN ERIC (1)
* 6,658,482 Method for speeding up internet protocol address lookups with efficient use of memory 48 1999
 
HEWLETT PACKARD ENTERPRISE DEVELOPMENT LP (2)
* 6,256,307 Local area network receive filter 32 1998
* 6,763,348 Method and apparatus for searching databases employing a trie search structure 1 2000
 
SYNIVERSE ICX CORPORATION (9)
* 9,143,477 Address recognition database 0 2004
8,001,272 Obtaining a valid international destination address 3 2004
7,774,502 Determining an international destination address 2 2004
* 2005/0086,378 Address recognition database 2 2004
* 2005/0055,461 Determining an international destination address 4 2004
7,774,503 Universal address recognition for text-capable communication devices 1 2006
* 2006/0174,038 Universal address recognition for text-capable communication devices 0 2006
8,571,065 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)
6,985,483 Methods and systems for fast packet forwarding 16 2001
* 2003/0091,043 Methods and systems for fast packet forwarding 8 2001
 
Juniper Networks, Inc. (1)
* 8,046,492 Offset independent filtering 0 2007
 
SAMSUNG ELECTRONICS CO., LTD. (4)
* 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
* 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
7,031,320 Apparatus and method for performing high-speed IP route lookup and managing routing/forwarding tables 43 2001
* 2002/0118,682 Apparatus and method for performing high-speed IP route lookup and managing routing/forwarding tables 16 2001
 
NOKIA TECHNOLOGIES OY (1)
6,633,548 Method and apparatus for ternary content addressable memory (TCAM) table management 24 2001
 
HITACHI, LTD. (9)
* 6,172,986 Mobile node, mobile agent and network system 109 1998
6,868,089 Mobile node, mobile agent-and network system 2 2000
6,888,845 Mobile node, mobile agent and network system 4 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 4 2004
* 2004/0205,211 Server, terminal control device and terminal authentication method 21 2004
7,453,905 Mobile node, mobile agent and network system 2 2005
7,643,447 Mobile node, mobile agent and network system 19 2008
 
ORACLE AMERICA, INC. (8)
* 6,526,055 Method and apparatus for longest prefix address lookup 51 1998
* 7,127,704 Interactive software engineering tool with support for embedded lexical contexts 56 2001
* 2002/0100,016 Interactive software engineering tool with support for embedded lexical contexts 6 2001
7,117,479 Language-sensitive whitespace adjustment in a software engineering tool 1 2001
* 2003/0066,058 Language-sensitive whitespace adjustment in a software engineering tool 3 2001
7,386,834 Undo/redo technique for token-oriented representation of program code 8 2002
* 7,339,930 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 1 2002
 
Pluris, Inc. (2)
* 6,421,342 Packet forwarding apparatus and method using pipelined node address processing 58 1998
* 6,804,241 Packet forwarding apparatus and method using pipelined node address processing 9 2002
 
AT&T INTELLECTUAL PROPERTY I, L.P. (3)
9,065,726 Methods and apparatus to utilize route parameter sets for exchanging routes in a communication network 0 2010
* 2015/0149,653 METHOD AND APPARATUS FOR DISTRIBUTING MEDIA CONTENT 0 2013
9,300,575 Methods and apparatus to utilize route parameter sets for exchanging routes in a communication network 0 2015
 
FUTUREWEI TECHNOLOGIES, INC. (6)
6,522,632 Apparatus and method for efficient prefix search 44 1998
* 6,430,527 Prefix search circuitry and method 58 1998
7,130,847 Prefix search method 10 2003
7,668,890 Prefix search circuitry and method 1 2006
* 2007/0038,626 Prefix search circuitry and method 11 2006
* 8,923,298 Optimized trie-based address lookup 0 2012
 
NEC CORPORATION (3)
* 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 4 2000
* 7,272,140 Address retrieval apparatus 1 2003
* 2004/0136,407 Address retrieval apparatus 1 2003
 
MICROSOFT TECHNOLOGY LICENSING, LLC (9)
* 6,385,649 Routers and methods for optimal routing table compression 50 1998
* 6,266,665 Indexing and searching across multiple sorted arrays 9 1998
* 2002/0143,918 Internet protocol (IP) address proximity detection and application to peer provider location 29 2001
7,322,023 Computer programming language statement building and information tool with non obstructing passive assist window 22 2001
* 2002/0095,658 Computer programming language statement building and information tool 41 2001
* 7,543,278 System and method for making a user interface element visible 4 2004
* 2006/0085,764 System and method for making a user interface element visible 6 2004
7,814,461 Computer programming language statement building and information tool 2 2006
* 2007/0006,142 Computer programming language statement building and information tool 2 2006
 
TUT SYSTEMS, INC. (1)
6,680,916 Method for using a balanced tree as a base for a routing table 4 2002
 
BROADCOM CORPORATION (30)
* 2002/0089,937 Packet matching method and system 73 2001
* 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 22 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 4 2003
7,634,500 Multiple string searching using content addressable memory 12 2003
* 7,571,156 Network device, storage medium and methods for incrementally updating a forwarding database 38 2004
* 7,372,917 Digital algorithm for on-line ACPR optimization in polar RF transmitters 9 2004
* 7,230,840 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
* 7,072,885 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
* 7,606,231 Pipeline architecture for a network device 2 2005
7,694,068 Re-entrant processing in a content addressable memory 10 2005
7,783,654 Multiple string searching using content addressable memory 15 2006
7,917,486 Optimizing search trees by increasing failure size parameter 3 2007
7,860,849 Optimizing search trees by increasing success size parameter 7 2007
7,676,444 Iterative compare operations using next success size bitmap 3 2007
7,636,717 Method and apparatus for optimizing string search operations 21 2007
7,440,304 Multiple string searching using ternary content addressable memory 20 2007
7,933,282 Packet classification device for storing groups of rules 12 2007
7,904,642 Method for combining and storing access control lists 11 2007
7,889,727 Switching circuit implementing variable string matching 3 2008
* 2008/0212,581 Switching Circuit Implementing Variable String Matching 14 2008
* 7,978,709 Packet matching method and system 4 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
* 2009/0012,958 MULTIPLE STRING SEARCHING USING TERNARY CONTENT ADDRESSABLE MEMORY 10 2008
8,566,337 Pipeline architecture for a network device 0 2009
8,438,330 Updating cam arrays using prefix length distribution prediction 0 2011
9,032,142 System and method for storing integer ranges in a memory 0 2012
8,943,268 Ternary content addressable memory (TCAM) storage system 2 2012
 
APPLIED INVENTION, LLC (4)
8,275,804 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 1 2009
* 8,131,781 Anti-item for deletion of content in a distributed datastore 0 2011
8,719,313 Distributed data store with a designated master to ensure consistency 0 2012
 
UNIVERSITY OF FLORIDA RESEARCH FOUNDATION, INC. (7)
7,523,218 O(log n) dynamic router tables for prefixes and ranges 6 2003
* 7,509,300 Dynamic IP router tables using highest-priority matching 10 2003
* 2004/0105,422 Dynamic IP router tables using highest-priority matching 18 2003
* 7,444,318 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
7,990,979 Recursively partitioned static IP router tables 0 2007
 
MINERAL LASSEN LLC (2)
* 6,956,858 Network routing table and packet routing method 60 2001
* 2002/0080,798 Network routing table and packet routing method 8 2001
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (2)
6,792,423 Hybrid longest prefix match and fixed match searches 23 2000
* 2003/0149,791 System and method for routing data by a server 42 2002
 
HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P. (3)
* 6,396,842 Method of searching using longest match based Randix Search Trie with variable length keys and having prefix capability 38 1998
6,549,521 Methods of managing dynamic decision trees 15 1999
* 6,320,848 Methods of altering dynamic decision trees 37 1999
 
LUCENT TECHNOLOGIES INC. (2)
* 7,039,641 Modular packet classification 42 2001
* 2002/0023,089 Modular packet classification 33 2001
 
CISCO TECHNOLOGY, INC. (53)
6,889,181 Network flow switching and flow data export 22 1997
6,512,766 Enhanced internet packet routing lookup 17 1997
* 6,853,638 Route/service processor scalability via flow-based distribution of traffic 10 1998
* 6,308,219 Routing table lookup implemented using M-trie having nodes duplicated in multiple memory banks 57 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 35 2000
6,990,099 Multiple parallel packet routing lookup 4 2001
6,775,737 Method and apparatus for allocating and using range identifiers as input values to content-addressable memories 55 2001
6,970,971 Method and apparatus for mapping prefixes and values of a hierarchical space to other representations 16 2002
* 6,961,808 Method and apparatus for implementing and using multiple virtual portions of physical associative memories 14 2002
7,899,067 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 10 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 4 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 7 2002
7,382,787 Packet routing and switching device 55 2002
7,069,372 Processor having systolic array pipeline for processing data packets 26 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 1 2002
7,349,415 Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match 21 2002
7,313,666 Methods and apparatus for longest common prefix based caching 23 2002
7,352,739 Method and apparatus for storing tree data structures among and within multiple memory channels 23 2003
8,270,401 Packet routing and switching device 32 2003
7,710,991 Scalable packet routing and switching device and method 6 2003
7,525,904 Redundant packet routing and switching device and method 8 2003
* 7,453,883 Method for compressing route data in a router 11 2003
7,450,438 Crossbar apparatus for a forwarding table memory in a router 6 2003
7,415,472 Comparison tree data structures of particular use in performing lookup operations 15 2003
* 2004/0230,583 Comparison tree data structures of particular use in performing lookup operations 3 2003
7,325,059 Bounded index extensible hash-based IPv6 address lookup method 16 2003
* 2004/0230,696 Bounded index extensible hash-based IPv6 address lookup method 8 2003
7,415,463 Programming tree data structures and handling collisions while performing lookup operations 19 2003
* 2004/0254,909 Programming routes and access control lists in comparison tree data structures and their use such as in performing lookup operations 30 2003
7,536,476 Method for performing tree based ACL lookups 22 2003
7,478,109 Identification of a longest matching prefix based on a search of intervals corresponding to the prefixes 12 2004
7,693,061 Data networking 4 2004
* 2006/0171,316 Data networking 16 2004
7,480,255 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 9 2004
7,260,518 Network flow switching and flow data report 33 2004
* 7,586,895 Performing extended lookups on MAC-based tables including level 3 multicast group destination addresses 6 2005
* 2006/0221,960 Performing extended lookups on mac-based tables 44 2005
7,889,712 Methods and apparatus for providing loop free routing tables 5 2005
7,418,536 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 2 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 1 2007
7,613,134 Method and apparatus for storing tree data structures among and within multiple memory channels 21 2008
* 2008/0181,139 Method And Apparatus For Storing Tree Data Structures Among And Within Multiple Memory Channels 63 2008
7,852,852 Method for compressing route data in a router 5 2008
* 2009/0046,724 METHOD FOR COMPRESSING ROUTE DATA IN A ROUTER 4 2008
8,270,399 Crossbar apparatus for a forwarding table memory in a router 1 2008
* 8,687,621 Dynamically right-sizing prefixes for network and application performance 0 2009
* 2010/0309,795 DYNAMICALLY RIGHT-SIZING PREFIXES FOR NETWORK AND APPLICATION PERFORMANCE 1 2009
9,094,237 Packet routing and switching device 0 2012
 
ALCATEL LUCENT (2)
7,433,355 Filter based longest prefix match algorithm 9 2004
* 2005/0175,010 Filter based longest prefix match algorithm 27 2004
 
University of Washington (3)
6,560,610 Data structure using a tree bitmap and method for rapid classification of data in a database 157 1999
* 6,728,732 Data structure using a tree bitmap and method for rapid classification of data in a database 18 2003
7,249,149 Tree bitmap data structures and their use in performing lookup operations 13 2004
 
FUJITSU LIMITED (1)
* 6,546,391 High-speed lookup method and high-speed lookup apparatus 46 1999
 
SUN MICROSYSTEMS, INC. (3)
* 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 11 2003
 
RPX CLEARINGHOUSE LLC (4)
6,990,070 Method and apparatus for adjusting packet transmission volume from a source 68 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 1 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 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
 
Broad Web Corporation (1)
* 6,963,924 IP routing lookup scheme and system for multi-gigabit switching routers 22 1999
 
TENSILICA, INC. (4)
* 6,888,838 Fast IP route lookup with configurable processor and compressed routing table 23 2001
* 7,274,697 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 6 2001
7,227,842 Fast IP packet classification with configurable processor 61 2002
 
INTEL CORPORATION (6)
* 6,493,698 String search scheme in a distributed architecture 24 1999
* 7,111,071 Longest prefix match for IP routers 29 2000
7,293,020 String search scheme in a distributed architecture 4 2002
* 7,039,018 Technique to improve network routing using best-match and exact-match techniques 21 2002
7,917,509 String search scheme in a distributed architecture 0 2007
8,321,440 String search scheme in a distributed architecture 1 2011
 
INTELLECTUAL DISCOVERY, INC. (2)
6,925,503 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 1 2001
 
AUDIOCODES, INC. (2)
7,272,746 Redundancy scheme for network processing systems 17 2003
* 2005/0050,171 Redundancy scheme for network processing systems 6 2003
 
ALCATEL (3)
* 2005/0114,393 Dynamic forwarding method using binary search 4 2003
* 7,289,979 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 27 2004
 
STMICROELECTRONICS S.A. (1)
* 7,570,644 Routing method for a telecommunications network and router for implementing said method 2 2003
 
WIND RIVER SYSTEMS, INC. (2)
* 7,860,106 System and method for routing table computation and analysis 1 2006
* 2007/0189,284 System and method for routing table computation and analysis 22 2006
 
TRANSDERMAL BIOTECHNOLOGY, INC. (1)
* 2004/0197,391 Stable topical drug delivery compositions 35 2003
 
NORTEL NETWORKS LIMITED (2)
* 6,173,384 Method of searching for a data element in a data structure 63 1998
* 6,820,120 Routing of data packets in heterogeneous networks 11 2000
* Cited By Examiner