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

all claims..

Related Publications

Loading Related Publications... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
UNIVERSITY OF WASHINGTONSEATTLE, WA1884

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Turner, Jonathan Berlin, DE 37 472
Varghese, George San Diego, CA 54 2096
Waldvogel, Marcel Stein am Rhein, CH 31 658

Cited Art Landscape

Patent Info (Count) # Cites Year
 
CARNEGIE MELLON UNIVERSITY (1)
5,440,546 Packet switch 31 1993
 
ENTERASYS NETWORKS, INC. (1)
5,781,772 Compressed prefix matching database searching 142 1995
 
HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P. (1)
5,651,002 Internetworking device with enhanced packet header translation and memory 194 1995
 
Sperry Corporation (1)
4,464,650 Apparatus and method for compressing data signals and restoring the compressed data signals 200 1981
 
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 133 1994

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
CISCO TECHNOLOGY, INC. (41)
6,889,181 Network flow switching and flow data export 21 1997
6,512,766 Enhanced internet packet routing lookup 17 1997
6,853,638 Route/service processor scalability via flow-based distribution of traffic 7 1998
6,308,219 Routing table lookup implemented using M-trie having nodes duplicated in multiple memory banks 54 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 30 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 49 2001
6,970,971 Method and apparatus for mapping prefixes and values of a hierarchical space to other representations 13 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 3 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 3 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 33 2002
7,069,372 Processor having systolic array pipeline for processing data packets 23 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 18 2002
7,313,666 Methods and apparatus for longest common prefix based caching 18 2002
7,352,739 Method and apparatus for storing tree data structures among and within multiple memory channels 16 2003
8,270,401 Packet routing and switching device 5 2003
7,710,991 Scalable packet routing and switching device and method 4 2003
7,525,904 Redundant packet routing and switching device and method 6 2003
7,453,883 Method for compressing route data in a router 7 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 7 2003
7,325,059 Bounded index extensible hash-based IPv6 address lookup method 11 2003
7,415,463 Programming tree data structures and handling collisions while performing lookup operations 9 2003
7,536,476 Method for performing tree based ACL lookups 12 2003
7,478,109 Identification of a longest matching prefix based on a search of intervals corresponding to the prefixes 10 2004
7,693,061 Data networking 3 2004
7,480,255 Data structure identifying for multiple addresses the reverse path forwarding information for a common intermediate node and its use 6 2004
7,260,518 Network flow switching and flow data report 25 2004
7,586,895 Performing extended lookups on MAC-based tables including level 3 multicast group destination addresses 5 2005
7,889,712 Methods and apparatus for providing loop free routing tables 3 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 14 2008
7,852,852 Method for compressing route data in a router 2 2008
8,270,399 Crossbar apparatus for a forwarding table memory in a router 0 2008
8,687,621 Dynamically right-sizing prefixes for network and application performance 0 2009
 
NETLOGIC MICROSYSTEMS, INC. (18)
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 18 2003
7,634,500 Multiple string searching using content addressable memory 9 2003
7,571,156 Network device, storage medium and methods for incrementally updating a forwarding database 19 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 8 2005
7,783,654 Multiple string searching using content addressable memory 8 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 1 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 9 2007
7,440,304 Multiple string searching using ternary content addressable memory 16 2007
7,933,282 Packet classification device for storing groups of rules 9 2007
7,904,642 Method for combining and storing access control lists 5 2007
7,889,727 Switching circuit implementing variable string matching 3 2008
7,978,709 Packet matching method and system 2 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
 
HITACHI, LTD. (8)
6,172,986 Mobile node, mobile agent and network system 107 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 3 2004
7,453,905 Mobile node, mobile agent and network system 1 2005
7,643,447 Mobile node, mobile agent and network system 18 2008
 
INTEL CORPORATION (6)
6,493,698 String search scheme in a distributed architecture 18 1999
7,111,071 Longest prefix match for IP routers 26 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 20 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
 
HEWLETT-PACKARD DEVELOPMENT COMPANY, L.P. (5)
6,256,307 Local area network receive filter 28 1998
6,396,842 Method of searching using longest match based Randix Search Trie with variable length keys and having prefix capability 37 1998
6,549,521 Methods of managing dynamic decision trees 12 1999
6,320,848 Methods of altering dynamic decision trees 34 1999
6,763,348 Method and apparatus for searching databases employing a trie search structure 1 2000
 
MICROSOFT CORPORATION (5)
6,385,649 Routers and methods for optimal routing table compression 48 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 18 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 2 2006
 
SUN MICROSYSTEMS, INC. (5)
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 45 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 7 2002
7,339,930 Method and apparatus for performing an address lookup using a multi-bit trie with backtracking 2 2002
 
BROADCOM CORPORATION (4)
7,372,917 Digital algorithm for on-line ACPR optimization in polar RF transmitters 7 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 2 2005
8,566,337 Pipeline architecture for a network device 0 2009
 
FUTUREWEI TECHNOLOGIES, INC. (4)
6,522,632 Apparatus and method for efficient prefix search 40 1998
6,430,527 Prefix search circuitry and method 55 1998
7,130,847 Prefix search method 9 2003
7,668,890 Prefix search circuitry and method 1 2006
 
SYNIVERSE ICX CORPORATION (4)
8,001,272 Obtaining a valid international destination address 3 2004
7,774,502 Determining an international destination address 2 2004
7,774,503 Universal address recognition for text-capable communication devices 1 2006
8,571,065 Method and apparatus for assigning a virtual address to and text-messaging to multiple text-capable destination entities 0 2008
 
UNIVERSITY OF FLORIDA RESEARCH FOUNDATION, INC. (4)
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 3 2003
7,444,318 Prefix partitioning methods for dynamic router tables 4 2003
7,990,979 Recursively partitioned static IP router tables 0 2007
 
APPLIED MINDS, LLC (3)
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
8,719,313 Distributed data store with a designated master to ensure consistency 0 2012
 
TENSILICA, INC. (3)
6,888,838 Fast IP route lookup with configurable processor and compressed routing table 19 2001
7,274,697 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 53 2002
 
UNIVERSITY OF WASHINGTON (3)
6,560,610 Data structure using a tree bitmap and method for rapid classification of data in a database 108 1999
6,728,732 Data structure using a tree bitmap and method for rapid classification of data in a database 13 2003
7,249,149 Tree bitmap data structures and their use in performing lookup operations 11 2004
 
BOCKSTAR TECHNOLOGIES LLC (2)
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 1 2005
 
NEC CORPORATION (2)
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
 
NORTEL NETWORKS LIMITED (2)
6,173,384 Method of searching for a data element in a data structure 61 1998
6,820,120 Routing of data packets in heterogeneous networks 10 2000
 
Pluris, Inc. (2)
6,421,342 Packet forwarding apparatus and method using pipelined node address processing 55 1998
6,804,241 Packet forwarding apparatus and method using pipelined node address processing 8 2002
 
SAMSUNG ELECTRONICS CO., LTD. (2)
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 36 2001
 
ALCATEL (1)
7,289,979 Parallel asymmetric binary search on lengths 16 2003
 
ALCATEL LUCENT (1)
7,433,355 Filter based longest prefix match algorithm 6 2004
 
AUDIOCODES, INC. (1)
7,272,746 Redundancy scheme for network processing systems 16 2003
 
BROADWEB CORPORATION (1)
6,963,924 IP routing lookup scheme and system for multi-gigabit switching routers 18 1999
 
CHEN, WEN-SHYEN ERIC (1)
6,658,482 Method for speeding up internet protocol address lookups with efficient use of memory 44 1999
 
FUJITSU LIMITED (1)
6,546,391 High-speed lookup method and high-speed lookup apparatus 41 1999
 
INTELLECTUAL DISCOVERY, INC. (1)
6,925,503 Method and system for performing a longest prefix match search 1 2001
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (1)
6,792,423 Hybrid longest prefix match and fixed match searches 14 2000
 
JUNIPER NETWORKS, INC. (1)
8,046,492 Offset independent filtering 0 2007
 
LUCENT TECHNOLOGIES INC. (1)
7,039,641 Modular packet classification 29 2001
 
MATRKS NETWORKING LIMITED LIABILITY COMPANY (1)
6,956,858 Network routing table and packet routing method 55 2001
 
NOKIA CORPORATION (1)
6,633,548 Method and apparatus for ternary content addressable memory (TCAM) table management 19 2001
 
NORTH CAROLINA STATE UNIVERSITY (1)
6,985,483 Methods and systems for fast packet forwarding 15 2001
 
ROCKSTAR CONSORTIUM US LP (1)
6,990,070 Method and apparatus for adjusting packet transmission volume from a source 60 1999
 
STMICROELECTRONICS S.A. (1)
7,570,644 Routing method for a telecommunications network and router for implementing said method 2 2003
 
TRANSWITCH CORPORATION (1)
7,433,871 Efficient ipv4/ipv6 best matching prefix method and apparatus 4 2003
 
TUT SYSTEMS, INC. (1)
6,680,916 Method for using a balanced tree as a base for a routing table 4 2002
 
WIND RIVER SYSTEMS, INC. (1)
7,860,106 System and method for routing table computation and analysis 1 2006
 
Other [Check patent profile for assignment information] (1)
8,335,780 Scalable high speed relational processor for databases and networks 0 2009