Flexible and high-performance packet classification algorithm

Details Flexible and high-performance packet classification algorithm Flexible and high-performance packet classification algorithm

2000-10-23

2004-08-17

Robinson, Greta (Department: 2177)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06778984

ABSTRACT:

CROSS-REFERENCE TO RELATED APPLICATION
This application claims the priority benefit of Taiwan application serial no. 89105205, filed Mar. 22, 2000.
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to a method for searching a database with don't care fields. More particularly, the present invention relates to a flexible and high-performance packet classification algorithm capable of partitioning packets into sub-tables each having a different data field width and depth. The algorithm is particularly useful for internet router path table lookup and packet classification or serving as a general search engine for a network processor.
2. Description of Related Art
To provide a more flexible service, a router no longer simply performs a search in a routing table followed by redirecting an incoming packet to the next workstation. A current internet switch/router needs to have packet classification capability, the capacity to provide different service quality insurance (QoS) or the capacity to provide processing of data at different safety levels within a virtual private network. In addition, the ‘firewall’ that ensures network safety also relies on packet classification techniques for granting permission for entering or leaving a network. In other words, many new types of network services depend very much on packet classification.
To achieve high-quality packet classification, the capacity to resolve a packet header is very important. Using the TCP/IP standard as an example, if we decide to use application flow, the 104-bit header that includes an IP Source address (32 bits), an IP destination address (32 bits), a protocol (8 bits), a source port number (16 bits) and destination port number (16 bits) must refer to the rule database in order to determine how to process a packet. In general, the content included in most rule database would permit the network administrator to set up flexible rules for the so-called don't care fields.
For example, Table No. 1 lists some typical rules (‘X’ refers to a don't care field).
TABLE NO. 1
A typical packet classification table
Destination
Service
Source IP
Destination IP
Protocol
Source Port
Port
Quality
140.96.115.X
X.X.X.X
06(TCP)
80(HTTP)
X
High
140.96.114.X
140.96.116.X
X
X
X
Medium
X.X.X.X
X.X.X.X
X
X
X
Low
Due to the increasing importance of packet classification, a number of articles related to search algorithms have been published in international journals. For example, V. Srinivasan et al. (V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, “Fast and Scalable Layer
4
Switching.” ACM SIGCOMM' 98, Vancouver, British Columbia) have proposed a cross-product search method. T. V. Lakshman et al. (T. V. Lakshman and D. Stiliadis, “High-Speed Policy-Based Packet Forwarding Using Efficient Multi-dimension Range Matching.” ACM SIGCOMM' 98, Vancouver, British Columbia) have proposed using five memory banks to search 1024 rules. N. Mckeown et al. (N. Mckeown, “Packet Classification on Multiple Fields.’ Inforcomm 2000) has proposed a compress algorithmic method via rule property observation. However, all these conventional methods are low in performance or use vast quantities of storage in the worst case scenarios. Moreover, the conventional methods are unsuitable for other types of search (such as IP path table). Content addressable memory (CAM) (T. Pei and C. Zukowaki, “Put Routing Table in Silicon.” IEEE Network Magazine, pp. 42-50, January 1992) is also one of the techniques for resolving packet classification problems. Yet, the biggest drawback of using CAM is that the memory is quite expensive at present. Furthermore, special circuit design and layout technique must be used if CAM is used. Hence, CAM has still not been widely adopted.
SUMMARY OF THE INVENTION
Accordingly, one object of the present invention is to provide a flexible and high-performance packet classification algorithm that involves the conversion of original rule database into a rule mapping table format for storage. The rule mapping table is formed by dividing an input key into a plurality of sub-keys, and then sequentially comparing the ordering of each sub-key with the same sub-key field of each rule. Finally, the results of the comparison (‘1’ indicates a match while a ‘0’ indicates a mismatch) are stored in the rule mapping table through bit mapping.
According to this invention, if the input key has a width of W bits, each sub-key has G bits and the rule database has N rules, the rule mapping table has a size (S) given by the formula S=(W/G)×N×2
G
(bits) and the minimum amount of memory read out in each search (A) is given by the formula A=(W/G)×N (bits).
In addition, when grouping state of each sub-key is two, that is, having a width of two (G=2), the smallest rule mapping table can be obtained. Size of the smallest rule mapping table is given by the formula S=(W×N)×2 (bits) with a corresponding smallest amount of memory read out given by the formula A=(W×N)/2 (bits).
The method of searching the rule mapping table includes extracting every sub-key from the input key, reading out corresponding rule vectors in the rule mapping table using the sub-key values directly as indexes, and carrying out a AND-computation of the rule vectors. The resultant vector after computation is known as a conformed rule vector. If the conformed rule mapping is non-zero, the leftmost bit (assuming that the leftmost rule has the highest priority) representation is taken out to represent the search result. The search result is made to multiply with the size of associated data. Together with the starting address for holding associated data, a data storage address corresponding to the search result can be found.
This invention uses a plurality of search engines all working in parallel to process rule mapping table search operations. Each search engine processes a portion of the rule vector. Meanwhile, the assignments of sub-key fields to each search engine are achieved through an interleave matrix.
Furthermore, the rule mapping table can be dissected into a plurality of sub-tables such that the number of rules and rule width in each sub-table can be set. Each sub-table has an initial scan value register, a terminal scan value register and a register for recording the width of the sub-table. Each sub-table can even have a register for registering the initial address of memory for holding associated data and a register for registering size of storage location for the associated data.
This invention also provides a flexible and high-performance packet classification algorithm that support a plurality of rule databases or sub-tables. In addition, this invention permits the co-existence of a plurality of rule databases each having a different length and width in the same search engine. Therefore, the design can provide actual improvements (higher speed, smaller volume occupation) and flexibility (possible coexistent of different rule databases). Moreover, the invention not only can provide a dynamic setting of different rule width for sub-tables on physical memory units, but can also provide unlimited flexibility to the search algorithm. In brief, the search method of this invention can be used as a general-purpose search engine in the design of network processor or in any situation where rapid search is necessary. The search method can serve even as a replacement technology for CAM.
It is to be understood that both the foregoing general description and the following detailed description are exemplary, and are intended to provide further explanation of the invention as claimed.


REFERENCES:
patent: 6298340 (2001-10-01), Calvignac et al.
patent: 6449256 (2002-09-01), Varghese et al.
patent: 6463067 (2002-10-01), Hebb et al.
patent: 6600744 (2003-07-01), Carr et al.

Affiliated with

Also associated with

Rating

Flexible and high-performance packet classification algorithm does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Flexible and high-performance packet classification algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flexible and high-performance packet classification algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3350968