Browse Prior Art Database

Filter and Routing Table Method for IP Forwarding

IP.com Disclosure Number: IPCOM000014454D
Original Publication Date: 2000-Jun-01
Included in the Prior Art Database: 2003-Jun-19
Document File: 4 page(s) / 96K

Publishing Venue

IBM

Abstract

Longest matching prefix search method

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 4

Filter and Routing Table Method for IP Forwarding

Longest matching prefix search method

An example of the longest matching prefix search method is shown in Figure 1. The example involves the following four prefixes that are searched for (in IP address notation) and corresponding search results (denoted as next hop pointers):
prefix next hop pointer
4.22.17/24 1
4.22.17.0/26 2
4.22.17.64/26 3
4.22.17.243/32 4

The search method involves several steps in which entries are processed that contain two flags, F1 and F2, which indicate the type of operations to be performed on the search key, i.e. the IP address. A test operation has to be performed if F1 equals 1. An index operation has to be performed if F2 equals 1. If none of the flags is set, the search operation is completed. It is also possible to have a differently coded set of bits in these entries to indicate the need for performing a test operation or index operation.

In the first step the initial entry shown at the left side of Figure 1 is processed. In this entry only flag F2 is set. According to the value of the count (CNT) field in this entry, the first 16 bits of the IP address are selected and used as an index into a table containing 2

  16=65536 entries at level 1, to which the pointer (PTR) field in the initial entry points to. The table entry at index 1046 (corresponding to IP addresses starting with 4.22/16) has both flags set and contains two fields labeled CNT1 and CNT2 that specify the number of bits to be used in a test and index operation. A test operation is now performed in which the next 8 bits (according to the CNT1 field) of the IP address are compared with a test value (TV) 17. When the test result is negative then the 'no match' entry is selected in the table at level 2 to which the PTR field points to. When the test result is positive then the next 2 bits (according to the CNT2 field) are used as an index into the 'match' part of the table at level 2. This continuous until an entry is reached in which both bit flags equal 0. The search result is then directly obtained from that entry, which can either be a next hop pointer (NHP) or an inva...