Network packet classification

• US 6,597,661 B1
• Filed: 08/25/1999
• Issued: 07/22/2003
• Est. Priority Date: 08/25/1999
• Status: Expired due to Fees

• Current Assignee: WatchGuard Technologies Incorporated (Gladiator Corporation)
• Original Assignee: WatchGuard Technologies Incorporated (Gladiator Corporation)
• Inventors: Bonn, David Wayne
• Primary Examiner(s): Yao, Kwang Bin
• Application Number:
  US09/382,568
• Time in Patent Office: 1,427 Days
• Field of Search: 370/229, 370/230, 370/230.1, 370/235, 370/235.1, 370/252, 370/389, 370/392, 370/395.2, 370/395.32, 370/428, 370/429
• US Class Current: 370/235
• CPC Class Codes: H04L 63/0254 Stateful filtering
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

The present invention is directed to a facility for classifying network packets. The classified network packets each contain a source address, a source port number, a destination address, and a destination port number. The facility first sums the source address, the source port number, the destination address, and the destination port number contained by the packet. The facility then determines the modulo remainder of the sum over a constant predetermined value. The facility uses the determined modulo remainder to classify the packet into a class of packets predicted to relate to the same network session.

Claims

1. A method in a computer system for authorizing network packets sent from a source address and port number to a destination address and port number, the method utilizing a packet authorization data structure containing numbered buckets, comprising:

receiving a first packet sent from a trusted source address and port number;

generating an index key for the first packet by summing its source address, source port number, destination address, and destination port number, then determining the remainder when the sum is divided by a predetermined constant value;

to a bucket having as its number the index key generated for the first packet, adding a packet authorization record specifying the source address and port number and destination address and port number of the first packet, the added packet authorization record further specifying an expiration time for the packet authorization record;

forwarding the first packet to its destination address and port number;

receiving a second packet sent to a trusted destination address and port number;

generating an index key for the second packet by summing its source address, source port number, destination address, and destination port number, then determining the remainder when the sum is divided by the predetermined constant value;

in a bucket having as its number the index key generated for the second packet, identifying a packet authorization record specifying the source address and port number and destination address and port number of the second packet;

if the expiration time specified by the identified packet authorization record indicates that the identified packet authorization record has not yet expired, forwarding the second packet to its destination address and port number; and

if the expiration time specified by the identified packet authorization record indicates that the identified packet authorization record has expired, omitting to forward the second packet to its destination address and port number.

2. The method of claim 1, further comprising:

receiving a third packet sent to a trusted destination address and port number;

generating an index key for the third packet by summing its source address, source port number, destination address, and destination port number, then determining the remainder when the sum is divided by the predetermined constant value;

determining that a bucket having as its number the index key generated for the third packet contains no packet authorization record specifying the source address and port number and destination address and port number of the third packet; and

in response to determining that a bucket having as its number the index key generated for the third packet contains no packet authorization record specifying the source address and port number and destination address and port number of the third packet, omitting to forward the third packet to its destination address and port number.

3. The method of claim 1, further comprising:

at a time after receiving the first packet, receiving a third packet sent from the same trusted source address and port number as the first packet;

generating an index key for the third packet by summing its source address, source port number, destination address, and destination port number, then determining the remainder when the sum is divided by the predetermined constant value;

in a bucket having as its number the index key generated for the third packet, identifying a packet authorization record specifying the source address and port number and destination address and port number of the third packet; and

modifying the packet authorization record specifying the source address and port number and destination address and port number of the third packet to specify a later expiration time than it presently specifies.

4. The method of claim 1, further comprising:

if the expiration time specified by the identified packet authorization record indicates that the identified packet authorization record has expired, removing the identified packet authorization record from the bucket having as its number the index key generated for the first packet.

5. The method of claim 1 wherein the method further comprises, incident to the step of identifying a packet authorization record specifying the source address and port number and destination address and port number of the second packet:

identifying an expired packet authorization record in the identified bucket; and

in response to identifying an expired packet authorization record, removing the identified expired packet authorization record from the bucket having as its number the index key generated for the third packet.

6. A method in a computer system for classifying a network packet, the network packet containing a source address, a source port number, a destination address, and a destination port number, comprising:

summing the source address, source port number, destination address, and destination port number contained by the packet;

determining the modulo remainder of the sum over a constant predetermined value; and

classifying the packet based upon the modulo remainder.

7. The method of claim 6 wherein the method classifies the packet into a class of packets predicted to relate to the same network session.

8. The method of claim 6, further comprising, before summing, ensuring that the source address, source port number, destination address, and destination port number are each arranged in host byte order.

9. The method of claim 6 wherein the computer system has access to a packet information data structure having a plurality of numbered buckets, at least some of the buckets having a list of information items, the method further comprising:

identifying a bucket having the determined modulo remainder as its number; and

accessing an information item in the list of information items associated with the identified bucket corresponding to the network packet.

10. The method of claim 6 wherein the computer system has access to a packet information data structure having a plurality of numbered buckets, the method further comprising:

identifying a bucket having the determined modulo remainder as its number, the identified bucket having associated with it a packet history indication; and

updating the packet history indication associated with the identified bucket to reflect the network packet.

11. The method of claim 10 wherein the packet history indication associated with the identified bucket is a flag, and wherein the method updates the packet history indication associated with the identified bucket by setting the flag.

12. The method of claim 10 wherein the packet history indication associated with the identified bucket is a counter having a value, and wherein the method updates the packet history indication associated with the identified bucket by augmenting the value of the counter.

13. The method of claim 10 wherein the packet history indication associated with the identified bucket is a list of items, and wherein the method updates the packet history indication associated with the identified bucket by adding an item explicitly identifying the source address, source port number, destination address, and destination port number of the network packet.

14. The method of claim 10 wherein the packet history indication associated with the identified bucket is a list of items, and wherein the method updates the packet history indication associated with the identified bucket by modifying the contents of an item explicitly identifying the source address, source port number, destination address, and destination port number of the network packet.

15. The method of claim 10 wherein the packet history indication associated with the identified bucket is a list of items, and wherein the method updates the packet history indication associated with the identified bucket by removing from the list an item explicitly identifying the source address, source port number, destination address, and destination port number of the network packet.

16. The method of claim 6 wherein the computer system has access to a session information data structure having a plurality of numbered buckets, the method further comprising:

identifying a bucket having the determined modulo remainder as its number, the identified bucket having associated with it a list of session status items, each session status item identifying a network session by indicating both a network address and a port number for each of two session ends, each session status item further indicating status of the network session that it identifies;

identifying in the list of session status items associated with the identified bucket a session status item indicating network addresses and port numbers matching those of the packet; and

updating the status indication of the identified session status item to reflect transmission of the network packet.

17. The method of claim 6 wherein the computer system has access to a packet processing information data structure having a plurality of numbered slots, the method further comprising:

identifying a slot having the determined modulo remainder as its number, the identified slot having associated with it a list of packet processing items, each packet processing item identifying a class of packets and indicating a way in which to process packets of the identified class;

identifying in the list of packet processing items associated with the identified slot a packet processing item identifying a packet class containing the packet; and

processing the packet in accordance with the processing indication of the identified item.

18. The method of claim 17 wherein the identified packet processing item indicates a manner in which the contents of the packet are to be reformatted, and wherein the method processes the packet by reformatting the packet in the indicated manner.

19. The method of claim 17 wherein the identified packet processing item indicates a manner in which the contents of the packet are to be translated, and wherein the method processes the packet by translating the packet in the indicated manner.

20. The method of claim 6 wherein the computer system has access to a packet filtering data structure having a plurality of numbered slots, the method further comprising:

identifying a slot having the determined modulo remainder as its number, the identified slot having associated with it a list of packet filtering items, each packet filtering item identifying a class of packets and indicating a condition under which packets of the identified class are to be forwarded;

identifying in the list of packet filtering items associated with the identified slot a packet filtering item identifying a packet class containing the packet;

if the condition indicated by the identified item is satisfied, forwarding the packet; and

if the condition indicated by the identified item is not satisfied, omitting to forward the packet.

21. The method of claim 6 wherein the computer system has access to a network traffic analysis data structure having a plurality of numbered slots, the method further comprising:

identifying a slot having the determined modulo remainder as its number, the identified slot having associated with it a list of packet history items, each packet history item identifying a class of packets and containing information about foregoing packets within the identified class;

identifying in the list of packet history items associated with the identified slot a packet history item identifying a packet class containing the packet; and

updating the information contained by the identified item to reflect the transmission of the packet.

22. The method of claim 21 further comprising the steps of generating a model of network traffic using the contents of the network traffic analysis data structure.

23. A computer-readable medium whose contents cause a computer system to classify a network packet, the network packet containing a source address, a source port number, a destination address, and a destination port number, by:

mathematically combining the source address, source port number, destination address, and destination port number contained by the packet;

determining the modulo remainder of the sum over a constant predetermined value; and

classifying the packet into a class of packets predicted to relate to the same network session based upon the modulo remainder.

24. The computer-readable medium of claim 23 wherein the source address, source port number, destination address, and destination port number are mathematically combined using addition.

25. The computer-readable medium of claim 23 wherein the computer system has access to a packet information data structure having a plurality of numbered buckets, at least some of the buckets having a list of information items, and wherein the contents of the computer-readable medium further cause the computer system to:

identify a bucket having the determined modulo remainder as its number; and

access an information item in the list of information items associated with the identified bucket corresponding to the network packet.

26. The computer-readable medium of claim 23 wherein the computer system has access to a session information data structure having a plurality of numbered buckets, and wherein the contents of the computer-readable medium further cause the computer system to:

identify a bucket having the determined modulo remainder as its number, the identified bucket having associated with it a list of session status items, each session status item identifying a network session by indicating both a network address and a port number for each of two session ends, each session status item further indicating status of the network session that it identifies;

identify in the list of session status items associated with the identified bucket a session status item indicating network addresses and port numbers matching those of the packet; and

update the status indication of the identified session status item to reflect transmission of the network packet.

27. A computer system for classifying a network packet, the network packet containing a source address, a source port number, a destination address, and a destination port number, comprising:

an addition subsystem that sums the source address, source port number, destination address, and destination port number contained by the packet;

a modular arithmetic subsystem that determine the modulo remainder of the sum over a constant predetermined value; and

an classification subsystem that classifies the packet based upon the modulo remainder.

28. A memory containing a network session data structure for storing information relating to network sessions, each network session having two ends and a network address and port number for each end, comprising:

a plurality of n buckets, each bucket having a number between zero and n−

1 and being associated with a list of session information items that each relate to a network session having the property that m modulo n is the number of the bucket, wherein m is the sum of the network addresses and port numbers for both ends of the network session, and wherein m is an integer≧

1 and n is an integer≧

2,

such that a session information item relating to a particular network session having a first end with network address a and port number b and a second end with network address c and port number d may be found in the list associated with the bucket having number (a+b+c+d) mod n, wherein a, b, c, and d are integers≧

1.

29. The memory of 28 wherein the list associated with each bucket is nonempty.

30. The memory of 28 wherein n is not a power of two.