Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-06-15
2001-02-06
Kulik, Paul V. (Department: 2777)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06185568
ABSTRACT:
BACKGROUND OF THE INVENTION
2. Field of the Invention
The field of the present invention is the classification of network communication packets processed in a network stack. More particularly, the invention presents a generalized packet classifier that may be used to classify network communication packets from different software components, such as drivers, that each may have different purposes for making the classification.
3. The Prior State of the Art
Over time, the usefulness and benefits of stand-alone computing devices, such as the ubiquitous personal computer, have been leveraged by allowing many of such computing devices to communicate one with another over a communications network. Network communication between computers allows many different kinds of applications to exist that are otherwise not possible with a stand-alone computing device. One of the more common and useful applications is simple messaging that many people use in order to communicate by electronic mail, also known as email.
For communicating over a network, information that is to be transported from one computer to another is divided into a number of network communication packets. These network communication packets (also known simply as “packets”) will eventually be transported across the physical communications network. In the PC environment, transmission is handled by a network interface card residing in the personal computer. Throughout this application, the PC environment will be assumed though the discussion and application of the concepts apply to many different network computing environments as will be appreciated by those skilled in the art.
The information originating at an application program running on a PC becomes packetized into network communication packets by passing through various software components before arriving at the network interface card for transmission on the physical communications network. The software components are typically layered drivers interconnected as appropriate to form what is known as the network stack.
Each driver or other processing component will process the data in succession as the original data is broken into successively different packetizing schemes from one level to the next down the network stack until the data is formed into packets that are transmitted by the network interface. The term “network communications packets” refers to any of the data packets used in the network protocol stack regardless of actual format. The original data is progressively packetized and formatted as it progresses down through the driver layers. For example, a TCP layer encapsulates the data in TCP packets, each of which may be further fragmented into multiple IP packets by an IP layer.
Typically, each driver has a particular function specified by a certain protocol or other constraint. For example, one driver may manage a network protocol such as the internet protocol (IP) while another may manage the actual network interface card. Such modularity allows a variety of different user configurations to be made without rewriting code. For example, the network protocol may be disassociated from any particular physical transmission system. In other words, by using interconnected drivers in the network stack, the same network protocol driver may be used with various physical interface drivers according to the particular physical configuration.
In order to send an email message from one computer to another, the text of the information is placed in a higher level protocol packet along with some packet header information and passed from the application into the network stack. Each element of the network stack may add additional header information and make processing decisions based on the information in the packet itself or any of the header information previously created by higher level drivers. Furthermore, packets at one level of the network stack may be broken down or recast into multiple packets at another level of the network stack. Eventually, all data will be packetized into packets suitable for transmission over the network interface.
Sending an email message may be viewed analogously to sending a letter by regular mail. The body of the message itself is created in both instances by the user. There are a number of processing steps for mailing a letter by regular mail before it is placed into the custody of the postal service (analogous to sending a packet over a communications network). An envelope must be procured, an address written on the envelope, and postage affixed to the envelope prior to placing the letter into the mail box. Each intermediate step may be thought of as header information (addressing, envelope, etc.) created by individual drivers processing an email message for delivery over a communications network between computers.
At the receiving end, packets are passed up the network stack. Each element of the network stack may remove a portion of the header information and make processing decisions based on the information in the packet itself or any of the header information not removed by lower level drivers. Furthermore, multiple packets at one level of the network stack may be combined into aggregate packets at another level of the network stack.
FIG. 1
shows an example of a network stack with an application program
20
at the highest level and a number of drivers at each successive level before reaching the network interface card
22
, namely, driver A
24
, driver B
26
, driver C
28
and driver D
30
. Each driver will perform processing in association with the packet before passing the packet on down to the next driver.
A packet is “classified” for certain processing in a given driver based on information about the packet that is contained in the headers or from information inside the data portion of the packet itself. Based on its classification, a packet will be processed by the driver differently and as shown in
FIG. 1
, a driver that needs to make a packet classification or make decisions based on information in the packet has a special portion of driver code called a packet classifier. In
FIG. 1
, driver A
24
will use packet classifier
32
, driver C
28
will use packet classifier
34
and driver D
30
will use packet classifier
36
. As mentioned previously, the packetization of the original data may be of a different format at each different driver. Note that driver B
26
will process packets in such a way that no packet classification is needed.
Each driver will perform different kinds of classification depending on the driver's purpose. In order to better appreciate the different classification scenarios, a number of different types of classification of network communication packets are now provided. The simplest form of classification involves comparing a certain value of a packet with a specific value. The classification being based upon matching a particular value is shown in the example of Table 1 below.
TABLE 1
Classification
Destination Address
0
11.22.33.44
1
11.22.55.66
2
11.22.77.88
3
11.23.34.45
4
11.23.45.67
5
12.34.56.78
Table 1 illustrates six different possible classifications for a packet based on a packet's exactly matching one of the destination addresses listed in the table. For example, a packet will be classified as belonging to classification 0 if and only if its destination address is “11.22.33.44”. Similarly, an exact match of the destination address field for a particular packet to be classified is necessary for each of the other five classifications.
Another form of classification that becomes slightly more complex involves comparing two or more fields from a packet to be classified with specific reference values that all must be matched in order to achieve a classification. This is shown below in the example of Table 2.
TABLE 2
Destination
Destination
Classification
Address
Port
0
11.22.33.44
1
1
11.22.33.44
2
2
11.22.33.44
3
3
11.22.55.66
1
4
11.22.55.66
2
5
11.22.55.66
3
Table 2 illustrates six different multiple-field classifications having a value for the destination address and the destinati
Bar Ofer
Bernet Yoram
Douceur John R.
Kulik Paul V.
Microsoft Corporation
Workman & Nydegger & Seeley
LandOfFree
Classifying data packets processed by drivers included in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Classifying data packets processed by drivers included in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classifying data packets processed by drivers included in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2567035