Browse Prior Art Database

ALGORITHM AND ARCHITECTURE FOR LONGEST PREFIX MATCH ON IP ADDRESSES

IP.com Disclosure Number: IPCOM000247555D
Publication Date: 2016-Sep-16

Publishing Venue

The IP.com Prior Art Database

Related People

Sarang Dharmapurikar: AUTHOR [+5]

Abstract

Routing a packet involves looking up the destination Internet Protocol (IP) address of the packet in an address table and performing the longest prefix match on the destination address against a prefix table with a large number of entries at a very high speed. Once the match is found, the corresponding information is used to forward the packet. Presented herein is an algorithm and architecture to store the address prefix table in a memory efficient way and look it up at a very high speed.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 20% of the total text.

Page 01 of 14

ALGORITHM AND ARCHITECTURE FOR LONGEST PREFIX MATCH ON IP ADDRESSES

AUTHORS:

Sarang Dharmapurikar

  Kevin Chu
Ganlin Wu
Alex Seibulescu

Francis Matus

CISCO SYSTEMS, INC.

ABSTRACT

    Routing a packet involves looking up the destination Internet Protocol (IP) address of the packet in an address table and performing the longest prefix match on the destination address against a prefix table with a large number of entries at a very high speed. Once the match is found, the corresponding information is used to forward the packet. Presented herein is an algorithm and architecture to store the address prefix table in a memory efficient way and look it up at a very high speed.

DETAILED DESCRIPTION

     The algorithm and architecture presented herein stores the address prefix table in a memory efficient way and achieves very high speed look ups. The entire address prefix table is split into multiple memory tiles. Each tile keeps the prefixes of only a certain range of prefix lengths. For example, one of the tiles might be responsible for matching the prefixes of length between 24 to 27 and some other tile might be responsible for matching prefixes of length between 28 and 31 and so on. The same range of prefix lengths can be assigned to multiple memory tiles. Also, it is not necessary to have non-overlapping prefix length ranges. Two memory tiles can have overlapping prefix

Copyright 2016 Cisco Systems, Inc.

1


Page 02 of 14

lengths e.g. a tile handling 24 to 27 and another tile handling 26 to 29. However, it is preferable to have them configured to handle non-overlapping ranges for easier management. This architecture is illustrated in FIG. 1 below.

FIG. 1

    The destination IP address in the packet is looked up in all the memory tiles. In case of multiple matches, the longest matching prefix information is used. In the case, if we get the longest prefix match in multiple memory tiles then it is a programming error. However, the information corresponding to the first longest matching prefix from the left is selected.

    A combination of hash lookup and Trie lookup are used to get the longest prefix match within a memory tile. FIG. 2 below illustrates the steps involved in the algorithm. For the illustration, an IPv4 lookup is used first. The details of the IPv6 lookup are described below.

Copyright 2016 Cisco Systems, Inc.

2


Page 03 of 14

FIG. 2

    If a memory tile is used for prefix length range [x:y] then the x is its base length. The memory tile keeps a register to unmask most significant x bits of the packet IP address and mask the remaining bits. For example, if the memory tile is responsible for matching prefixes of lengths between 24 to 27, then the base mask register unmasks the most significant 24 bits of the address and masks the least significant 8 bits. The value after applying the mask is used as a key to a hash function. (Step 1)

    The hash function returns a value which is used as an index into the memory tile. This location is read from the memor...