Browse Prior Art Database

APPARATUS AND FAST SEARCH ALGORITHMS FOR EFFICIENT NETWORK PACKET ROUTING

IP.com Disclosure Number: IPCOM000009825D
Original Publication Date: 2000-May-01
Included in the Prior Art Database: 2002-Sep-20
Document File: 2 page(s) / 106K

Publishing Venue

Motorola

Related People

Anil Gupta: AUTHOR

Abstract

Internet (IP) address lookup is a major bottleneck in high-performance routers and switches. With Internet growth, the problem is compounded because of routing lookup table sizes, increased traf fic, higher speed link and migration of 128-bit IPv6 addresses. This paper describes an algorithm for building IP lookup tables for efficient and fast searching (10Ox faster than today's state of the art router) using network addressing field decomposition and horizontal pointers.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 50% of the total text.

MOTOROLA

Technical Developments

APPARATUS AND FAST SEARCH ALGORITHMS FOR EFFICIENT NETWORK PACKET ROUTING

by Anil Gupta

ABSTRACT

Internet (IP) address lookup is a major bottleneck in high-performance routers and switches. With Internet growth, the problem is compounded because of routing lookup table sizes, increased traf fic, higher speed link and migration of 128-bit IPv6 addresses. This paper describes an algorithm for building IP lookup tables for efficient and fast searching (10Ox faster than today's state of the art router) using network addressing field decomposition and horizontal pointers.

This lookup table requires no sorting, moving, copying, or binary tree balancing. It is a highly parallel and pipelined search that provides extremely high throughput. Latency is also very low and is solely a function of the number of tables to be searched.

This in turn is a function of the bit width of the search values and the number of entries to be contained in the tables. Finally, table maintenance (i.e.

new entry additions and/or entry deletions) can be performed in the background without disruption of the pipelined foreground entry lookup tasks.

PROBLEMS ENCOUNTERED BY THE CONVENTIONAL LOOKUP TABLE

. Direct Look-up - For wide record size, becomes too large to implement

. Content Addressable Memory (Cache like) - Complex control logic -Large number of ASIC required (too expensive)

. Binary Search - Requires that entries in the table must be arranged in sequential fashion (processor over head)

Motorola. Inc. 2000

. Index Sequential Search - Requires that entries in the table must be arranged in sequential fashion (processor overhead) - Table management is too complex

THE PROBLEMS SOLVED BY PROPOSED ALGORITHM AND LOOKUP TABLE

. Bandwidth efficient lookup - Through pipeline architecture and parallelism - Multiple requests process concurrently

. No processing overhead - No ordering of entries is required, unlike other approaches - No memory allocation/de-allocation for free spaces

. Record partitioning algorithms with nested table management - Embedded link list, No external memory required for table management - May optionally search only on partial record

THEORY OF OPERATION

As a packet arrives into routers, destination address from the network header is extracted and broken into slices as depicted in Figure 1. These slices are used to generate a table. Placing the lookup tables in a sequential arrangement creates this invention. T...