Network packet classification

[0002] The present invention is directed to the field of computer networking, and more particularly, to the field of network packet processing.

[0003] In computer networks, information can be transmitted between two connected computer systems, herein termed the “source” and “destination” computer systems. A particular pair of computer systems exchanging information are said to be engaged in a “session.”

[0004] Many protocols are available for formatting and transmitting this information, such as Transmission Control Protocol (“TCP”), defined in Internet Requests for Comment 675, 761, and 793, currently available at ftp://ftp.isi.edu/in-notes/rfc675.txt, ftp://ftp.isi.edu/in-notes/rfc761.txt, and ftp://ftp.isi.edu/innotes/rfc793.txt, respectively; and User Datagram Protocol (“UDP”), defined in Internet RFC 768, currently available at ftp://ftp.isi.edu/in-notes/rfc768.txt.

[0005] Protocols such as TCP and UDP generally specify dividing a body of information to be transmitted into a number of pieces, called “packets,” attaching to each packet a “header” containing additional information about the packet, and sending these packets from the source computer system to the destination computer system. Both of the above protocols specify including in each packet header a numerical network address of the source computer system and the destination computer system. They additionally each specify including in each packet header a “port number” for each the source and destination computer system that allows these computer systems to differentiate between packets arriving for different purposes.

[0006] In many cases, it is useful to track packets based on the particular network session that they are part of. Packet classification of this sort may be used, for example, to perform packet filtering—determining, for packets addressed to a protected computer system, which to forward to the protected computer system and which to discard. Such classification may also be used to selectively perform packet modification, such as reformatting packet contents, or to perform network traffic analysis. Unfortunately, existing approaches to classifying packets to identify the network sessions to which they belong each have significant disadvantages. Accordingly, a new, more effective approach to classifying packets to identify the network sessions to which they belong would have considerable utility.

[0007] FIG. 1 is a high-level block diagram of the general-purpose computer system upon which the facility preferably executes.

[0008] FIG. 2 is a flow diagram showing the steps preferably performed by the packet filtering facility for each packet received.

[0009] FIG. 3 is a flow diagram showing the steps performed by the hash function.

[0010] FIGS. 4A, 4B, and 4C are data structure diagrams showing the processing of an outbound packet.

[0011] FIGS. 5A and 5B are data structure diagrams showing the processing of an authorized inbound packet.

[0012] FIGS. 6A and 6B are data structure diagrams showing the processing of an end-of-session, or “FIN” packet.

[0013] FIGS. 7A and 7B are data structure diagrams showing the processing of an inbound packet whose authorization record has expired.

[0014] The present invention provides an approach to classifying network packets. In a preferred embodiment, a packet is classified based on the sum of its source address, source port number, destination address, and destination port In particular, a packet is classified by assigning it a hash value equal to the modulo remainder of the above sum over a constant value. Classifying packets using this hashing function both provides an excellent hashing distribution and groups together packets exchanged in different directions in the same network session.

[0015] In one preferred embodiment, this packet classification scheme is utilized in a software facility for network packet filtering (“the facility”). The facility operates in a computer system or other device that protects a group of protected computer systems from unauthorized packets. The computer system upon which the facility executes receives the packets addressed to the protected computer system (“inbound packets”) and the packets sent from the protected computer system (“outbound packets”), and determines whether to forward them to their destination. In that connection, the facility maintains a hash table, into which it indexes with the hash values of the packets it receives. When an outbound packet is received, it is treated as an indication that future corresponding inbound packets should be forwarded, until an end-of-session packet is received or a timeout period elapses. In that connection, authorization records are stored in the hash table identifying inbound packets that are to be forwarded rather than discarded.

[0016] In various alternative embodiments of the packet filtering facility, different levels of information are stored to identify authorized packets. In one preferred embodiment, each bucket of the hash table may contains a list of authorization records. Each authorization record contains information identifying a network session and representing the authority to forward packets that are part of the network session. In certain further preferred embodiments, such records contain an expiration time after which such authorization expires, and/or a specific identification of the end of the session whose packets are authorized.

[0017] The packet classification scheme of the present invention is further adapted to use in other network administration applications, including network traffic analysis, such as network traffic modeling, or network packet processing, such as reformatting or translating data contained in certain network packets.

[0018] FIG. 1 is a high-level block diagram of the computer system upon which the facility preferably executes. The computer system 100 contains one or more central processing units (CPUs) 110, input/output devices 120, and a computer memory (memory) 130. Among the input/output devices is a storage device 121, such as a hard disk drive, and a computer-readable media drive 122, which can be used to install software products, including components of the facility, which are provided on a computer-readable medium, such as a CD-ROM. The input/output devices also include a network connection 123, through which the computer system 100 may communicate with other connected computer systems, and through which the facility receives network packets for filtering. The memory 130 preferably contains the packet filtering facility 131, as well as a hashing function 132 and a packet filtering hash table 133 used by the facility. While the facility is preferably implemented on a computer system configured as described above, those skilled in the art will recognize that it may also be implemented on computer systems having different configurations. In particular, the facility may be implemented in a dedicated network security device, a dedicated network analysis device, a router, or other types of specialized network hardware.

[0019] FIG. 2 is a flow diagram showing the steps preferably performed by the packet filtering facility for each packet received. In step 201, the facility invokes the hash function in order to produce a hash result value for the received packet based upon its source address, source port number, target address, and target port number.

[0020] FIG. 3 is a flow diagram showing the steps performed by the hash function. In step 301, the hash function converts the source address, source port number, destination address, and destination port number for the current message each to host byte order, if necessary. Version 4 of the Internet Protocol standard (“IPv4”) specifies that numerical network addresses in an IP network (“IP addresses”) are unsigned 32-bit integers, made up of 48-bit bytes that are transmitted in order from the most significant byte to the least significant byte. This ordering is called “network standard byte order.” (In version 6, or IPv6, IP addresses are unsigned 128-bit integers having the same bit ordering.) An example of a version 4 IP address is shown on line (1):

[0021] 10000000 00001010 00000010 00011110  (1)

[0022] IP addresses are often expressed in what is called “dotted decimal notation,” in which the bytes are shown as decimal integers separated by decimal points. Accordingly, the IP address shown on line (1) may be expressed as:

[0023] 128.10.2.30  (2)

[0024] By performing the act of storing a transmitted IP address in memory by storing the first and highest-order byte at an initial memory location, and each successively lower-order byte at the next higher memory location, a computer system preserves the byte ordering, called “Big Endian” shown on line (1). Some computer systems internally represent integers using this Big Endian byte ordering. On these computer systems, IP addresses can be stored in memory as described above and immediately operated upon as 32-bit integer values. Other computer systems, however, use different byte orderings to represent integers. For example, some computer systems use Little Endian byte ordering, in which the lowest-order byte is stored in the lowest memory location and each successively higher-order byte is stored at the next higher memory location. Networked computer systems that use byte ordering schemes other than Big Endian generally have functions for converting between Big Endian network standard byte order and their internal order, called “host order.” For example, on a computer system using Little Endian byte ordering, the Unix function ntohl( ) converts the value on line (1) in Big Endian network standard byte order to the representation on line (3) in Little Endian host order:

[0025] 00011110 00000010 000001010 10000000  (3)

[0026] The Unix function ntohl() converts long 4-byte integers from network standard byte order to host order, while the Unix function ntohs() converts short 2-byte integers from network standard byte order to host order. ntohs() may be used in the same manner to convert port numbers, which are 2-byte integers, from network standard byte order to host order. Accordingly, in step 301, the hash function preferably uses the ntohl() and ntohs() functions to convert the addresses and port numbers, respectively, of the message to host byte order.

[0027] In step 302, the facility sums the source address, source port number, destination address, and destination port number. In step 303, the facility determines the modulo remainder of the sum over the hash table size. The hash table size is preferably chosen to be a value that is not a power of 2 and that further is a prime number. The table size is preferably based on the expected number of simultaneous sessions for which the packet filtering facility is expected to filter packets. For example, for about 500 simultaneous sessions, a table size of 2047 is preferably chosen. After step 303, the function returns the modulo remainder determined in step 303 as the hash result value. To summarize, hashing function can be expressed mathematically as:

[0028] (ntohs(source address)+ntohs(source port number)+ntohl(destination address)+ntohs(destination port number)) mod (table size)  (4)

[0029] Returning to FIG. 2, in step 202, if the FIN flag is set in the packet, indicating that the packet marks the end of its session, then the facility continues at step 212, else the facility continues at step 203. In step 203, if the packet is from a protected node, then the facility continues in step 204 to process the packet as an outbound packet, else the facility continues in step 208 to process the packet as an inbound packet. In one preferred embodiment, the facility performs the determination of step 203 by determining whether the source address and source port number of the packet correspond to a list of network nodes for which the facility is assigned to filter packets. In an alternative preferred embodiment, the determination of step 203 is performed by determining whether the packet was received via a network connection to protected nodes, or via a separate network connection to unprotected nodes.

[0030] In step 204, if the list of authorization records for the bucket for the outbound packet's hash result contains an authorization record for the converse of this packet—that is, an inbound packet that is part of the same session as the received outbound packet—then the facility continues in step 205, else the facility continues in step 206. In step 205, the facility updates the expiration time for the preexisting authentication record for the converse of this packet. After step 205, the facility continues in step 207. In step 206, the facility adds an authorization record for the converse of the packet to the list of authorization records for the bucket for the packet's hash result. In step 207, the facility forwards the packet to its destination address and port number. After step 207, these steps conclude.

[0031] In step 208, in order to process the inbound packet, if the list of authorization records for the bucket for the packet's hash result contains an authorization record for the packet, then the facility continues in step 209, else the facility continues in step 211. In step 209, if the authorization record for the packet is expired, that is, if the current time is later than the expiration time for the authorization record, then the facility continues in step 210, else the facility continues in step 207 to forward the packet. In step 210, the facility removes the authorization record for the packet from the list for the bucket for the packet's hash result. Then, in step 211, the facility discards the packet. After step 211, these steps conclude.

[0032] In step 212, because a FIN packet has been received, the facility removes from the list of authorization records for the bucket for the packet's hash result any authorization record for the packet or its converse. In step 213, if the packet is from a protected node, then the facility continues in step 207 to forward the packet, else the facility continues in step 208 to process the inbound packet.

[0033] In a further preferred embodiment, steps 204 and 208 involve traversing part or all of the list for the bucket for the hash result. During such traversal, the facility preferably identifies and removes any authorization records in the list that have expired.

[0034] FIGS. 4A-7B show examples of the operation of the facility. FIGS. 4A, 4B, and 4C are data structure diagrams showing the processing of an outbound packet. The diagrams show a representation of the outbound packet 410; the hash function 420; the hash table buckets, such as buckets 431-438; and the lists of authorization records associated with each nonempty bucket, such as the list containing authorization record 441 associated with bucket 434, the list containing authorization record 442 associated with bucket 435, and the list containing authorization record 443 associated with bucket 436. Each authorization record in a list is an authorization to forward inbound packets, and contains the source address and port number and destination address and port number of the authorized inbound packets, as well as an expiration time at which the authorization expires. For example, authorization record 441 represents an authorization to forward inbound packets having source address 29.132.15.1, source port number 80, destination address 208.152.24.130, and destination port number 1501. This authorization expires at time 12:00:52.129. Such an inbound packet would have a hash value of 1250, the hash value of bucket 434. Because of the symmetry of the hash function with respect to source node information and destination node information, outbound packets for the same session will also have hash result 1250. Finally, the data structure diagram includes an indication 460 that the current time is 12:02:26.131.

[0035] When outbound packet 410 is received and the hash function applied, the hash result of 1250, is obtained as follows:

[0036] (source address+source port number+destination address+destination port number) mod (table size)=(3449297025+1502+495193937+80) mod 2047=3944492464 mod 2047=1250

[0037] FIG. 4B shows that, because outbound packet 410 has hash result 1250, a new authorization record 444 is added to the list of authorization records for bucket 434 for hash value 1250. FIG. 4B further indicates that packet 410, because it is an outbound packet, is forwarded to its destination.

[0038] FIG. 4C shows the optional garbage collection feature of the facility. In determining whether the list of authorization records for hash value 1250 already contains an authorization record for inbound packets that are part of the same session as outbound packet 410, one embodiment of the facility preferably checks each traversed authorization record to determine whether its expiration time has passed. Because the expiration time of authorization record 441, 12:00:52.129, is earlier than current time 460, 12:02:26.131, FIG. 4C shows that the facility has removed authorization record 441 from the list of authorization records for hash value 1250.

[0039] FIGS. 5A and 5B are data structure diagrams showing the processing of an authorized inbound packet. FIG. 5A shows inbound packet 510 which has source address 29.132.151.1, source port number 80, destination address 208.152.24.129, and destination port number 1502. In order to determine whether to forward the packet, the facility determines whether a hash table contains an authorization record for such an inbound packet. The facility subjects the inbound packet 510 to the hash function to yield hash result 1250. It then searches the list of authorization records for hash result 1250 to determine whether the list contains an unexpired authorization record for this packet. The facility finds authorization record 444, which specifies the same source address and port number and destination address and port number as inbound packet 510. Further, the authorization record is unexpired as its expiration time, 12:02:27.131, is later than the current time 560, 12:02.26.437. For this reason, FIG. 5B shows that the facility forwards the inbound packet in accordance with the unexpired authorization record.

[0040] FIGS. 6A and 6B are data structure diagrams showing the processing of an end-of-session, or “FIN” packet. The FIN packet 610 hashes to hash result 1824. The facility searches in the list of authorization records for hash result 1824 for an authorization record matching packet 610 or its converse. In doing so, the facility identifies authorization record 643 and, though this authorization record has not yet expired, FIG. 6B shows that the facility removes authorization record 643 in response to the FIN packet. FIG. 6B further shows that the facility forwards the outbound FIN packet to its destination.

[0041] FIGS. 7A and 7B are data structure diagrams showing the processing of an inbound packet whose authorization record has expired. When the facility applies the hashing function to inbound packet 710 it obtains a hash result of 1250. The facility searches the list of authorization records for hash result 1250, and identifies authorization record 741 as matching the inbound packet 710. Because the expiration time of authorization record 741, 12:02:27.131, is earlier than the current time 760, 12:02:28.220, FIG. 7B shows that the facility removes authorization record 741 and discards inbound packet 710.

[0042] While this invention has been shown and described with reference to preferred embodiments, it will be understood by those skilled in the art that various changes or modifications in form and detail may be made without departing from the scope of the invention. For example, other hashing functions that combine the source address and part number and destination address and part number, or a different combination of packet header values, may be used. Also, the hash function may be straightforwardly used for any application that involves classifying network products. Further, while the hash function is discussed above with respect to messages conforming to Internet protocols such as TCP and UDP, those skilled in the art will recognize that the hash function may be straightforwardly applied to packets, or other units of data transmission, conforming to other network protocols.