Packet classification search device and method

Details Packet classification search device and method Packet classification search device and method

2001-08-10

2004-04-06

Vu, Kim (Department: 2172)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

06718326

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a packet classification search device and method for performing packet transmission processing in a packet transmission device such as an IP (Internet Protocol) router or the like, which classify what type of processing to perform upon packets such as IP packets from information such as header information included in these packets; and in particular relates to a search technique for tables or the like which are searched when determining upon the processing to apply to the packets.
2. Description of the Related Art
In the past, in a packet transmission device such as an IP router or the like, a routing table has been searched based upon destination addresses which are included in the packet headers to determine the next route. The relationship between the destination address and the next route is stored in the routing table. With conventional networks such as the Internet, only simple transmission processing has been performed in this manner, using only the destination address. This point will now be explained in the following by giving a concrete structural example.
FIG. 19
shows how an IP packet or the like carrying data is transmitted, and in this figure the reference symbols
2
-
1
,
2
-
2
, and
2
-
3
denote networks which are connected to a router
1
, while
3
-
1
,
3
-
2
, and
3
-
3
denote signal lines which connect the router
1
and the networks
2
-
1
,
2
-
2
, and
2
-
3
, and the reference symbol
4
denotes an IP packet. Furthermore, the reference symbols
5
-
1
,
5
-
2
, . . .
5
-A are terminals which are present in the network
2
-
1
, the reference symbols
6
-
1
,
6
-
2
, . . .
6
-B are terminals which are present in the network
2
-
2
, and the reference symbols
7
-
1
,
7
-
2
. . .
7
-C are terminals which are present in the network
2
-
3
(where A, B, and C are any integers greater than or equal to 2).
Furthermore, as is customary, the network addresses in
FIG. 19
are separated by “.” characters into groups of 8 bits each of which is expressed in decimal, and the number after the “/” shows, in the IP address, how many bits from the most significant bit is to be taken as the network address.
The IP packet
4
contains the IP address of the terminal which is scheduled as its destination, and data. In the past, the router
1
has only searched for the destination IP address contained in the IP header of the IP packet
4
, and has decided based thereupon from which signal line to forward the IP packet.
However, in recent years, along with the expansion of the Internet, the conventional type of simple transmission processing using only the destination IP address has proved to be insufficient, and a higher degree of transmission control has become necessary. For example, in order to provide diversification of service upon a data network and in order to address problems of security, attention has focused upon packet classification which performs various procedures for QoS (Quality of Service) control or policy control by searching not only the destination IP addresses which are included in the IP headers of the packets, but also the source IP addresses or other information (such as the TCP (Transmission Control Protocol)/UDP (User Datagram Protocol), port number, or the like), and furthermore by searching not only the IP headers but also other header information within the packets, and by identifying the packets in more detail. Thus by packet classification is meant performing different processing for each flow of IP packets, in order to implement IP value added services such as QoS, VPN (Virtual Private Network), firewalls and the like.
The router classifies the packets in detail by packet classification, and may implement value added services by forwarding packets while allocating priority to them according to contract, or may implement discarding of packets from malicious users. In more concrete terms, it is possible to implement QoS control by performing priority control of the packets based upon the source addresses of their users and their TCP/UDP port numbers, in order to enhance the QoS of packet transmission of specified applications from specified users. Furthermore, if specified applications are to be prevented from communication and their packets are to be discarded, it is possible to implement policy control by filtering so as not to transmit packets which have the TCP/UDP port numbers which are allocated to these applications. A rule table (also termed a “policy table”) which will be described hereinafter is searched for rules required for this type of procedure.
Six representative ones of the various fields (field information in packet headers) for classifying packets are: destination address (DA), source address (SA), protocol identifier (PID), destination port number (DP), source port number (SP), and differentiated service code point (DSCP). And the combinations of information corresponding to these fields and actions with regard to the packets (forward at high priority, forward at medium priority, forward at low priority, denying etc.) are hereinafter termed rules (or policies), and these rules are mainly determined and set into the router by the network administrator.
FIG. 20
shows an example of rules for packet classification based upon the network structure of
FIG. 19
, and in this figure the reference symbol
10
denotes the rule table, while the reference symbols
11
,
12
,
13
, and
14
are rules. The rule table 10 is searched with a plurality of fields in the packet header as search keys, and it is used for determining the action to be applied to these packets. If these rules
11
through
14
are set into the router
1
of
FIG. 19
, when for example a packet using the UDP protocol and whose destination port number is 100 is forwarded from the terminal
5
-
1
of the network
2
-
1
to the terminal
7
-
1
of the network
2
-
3
, since all the fields (the destination address, the source address, the protocol, and the destination port number) of this packet agree with rule
11
(however, the “destination port number” of rule
11
is “don't care” and thus matches anything), therefore the router
1
performs the action described by the “Action” of rule
11
upon this packet. In other words, the router
1
forwards this packet with high priority.
FIG. 21
shows an example of the structure of an IP packet and the main header information. Although this IP packet is principally composed of a local network header
21
, an IP header
22
, an upper-layer header
23
(in the figure termed a TCP header), user data (in the figure termed TCP data), and a local network trailer
25
, a plurality of fields which are present in each header have the possibility of being used in packet classification.
Along with increase of the degree of attention given to packet classification, the requirement for more detailed classification of the packets has increased, and the number of fields in the header which are to be searched has also increased. Furthermore, in recent years, with the commencement of the introduction of the new IPv6 protocol, the destination IP address and the source IP address are both 128 bits long, so that the number of bits has greatly increased in comparison with the previous IPv4 protocol in which these addresses were 32 bits long. The increase in the number of fields and the increase in the number of search bits for packet classification due to the introduction of the IPv6 protocol have made it necessary in present conditions to search around 400 bits.
During the searching of the rule table, it is necessary to search through the rules (also termed entries) which are made up from this entire field information for the field which most closely resembles or agrees with the header information of the packet which is the subject. As one method for performing this type of search, the method of searching through the entire rule table from top to bottom may be considered. However, with this method, when the rules in the rule table become l

Affiliated with

Also associated with

Rating

Packet classification search device and method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Packet classification search device and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet classification search device and method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3263731