Method and apparatus for packet classification using a forest of hash tables data structure Number:7,394,809 from the United States Patent and Trademark Office (PTO) owispatent A packet classifier having a forest of hash tables data structure. The forest of hash tables data structure includes a number of hash tables, each hash table having a bit mask corresponding to an equivalent set of rules. Each hash table includes a number of entries, wherein an entry of a hash table may correspond to a rule. One or more of the hash tables may include a marker in one entry, wherein the marker identifies another one of the hash tables. The hash table identified by the marker is a descendant of the hash table in which the marker is placed.<H classification, structure, Method, and, appa, 7394809.html, Patent, pto, 7394809

Title: Method and apparatus for packet classification using a forest of hash tables data structure

Abstract: A packet classifier having a forest of hash tables data structure. The forest of hash tables data structure includes a number of hash tables, each hash table having a bit mask corresponding to an equivalent set of rules. Each hash table includes a number of entries, wherein an entry of a hash table may correspond to a rule. One or more of the hash tables may include a marker in one entry, wherein the marker identifies another one of the hash tables. The hash table identified by the marker is a descendant of the hash table in which the marker is placed.

Patent Number: 7,394,809 Issued on 07/01/2008 to Kumar, et al.

Inventors: Kumar; Alok (Santa Clara, CA), Yavatkar; Raj (Portland, OR)
Assignee: Intel Corporation (Santa Clara, CA)

Appl. No.: 10/404,202

Filed: March 31, 2003

Current U.S. Class: 370/392

Current International Class: H04L 12/28 (20060101)

References Cited [Referenced By]

U.S. Patent Documents


5615341	March 1997	Agrawal et al.
5920900	July 1999	Poole et al.
5951651	September 1999	Lakshman et al.
5995971	November 1999	Douceur et al.
6115802	September 2000	Tock et al.
6141749	October 2000	Coss et al.
6147976	November 2000	Shand et al.
6182228	January 2001	Boden et al.
6212184	April 2001	Venkatachary et al.
6289013	September 2001	Lakshman et al.
6301669	October 2001	Boden et al.
6341130	January 2002	Lakshman et al.
7031314	April 2006	Craig et al.
7039641	May 2006	Woo
7133400	November 2006	Henderson et al.
2001/0000193	April 2001	Boden et al.
2002/0023080	February 2002	Uga et al.
2002/0118682	August 2002	Choe
2002/0152209	October 2002	Merugu et al.
2002/0191605	December 2002	Lunteren et al.
2003/0014525	January 2003	DeLima et al.
2003/0018591	January 2003	Komisky
2003/0048785	March 2003	Calvignac et al.

Foreign Patent Documents


0 742 524	Nov., 1996	EP
WO 00/08817	Feb., 2000	WO

Other References

Chao, Next Generation Routers, IEEE, pp. 1518-1558, Sep. 2002. cited by examiner .
Milind M. Buddhikot et al., "Space Decomposition Techniques for Fast Layer-4 Switching," Proceedings of Conference on Protocols for High Speed Networks, Aug. 1999, pp. 25-41. cited by other .
Pankaj Gupta et al., "Packet Classification Using Hierarchical Intelligent Cuttings," Proc. Hot Interconnects VII, Aug. 1999, Stanford./This paper is also available in: IEEE Micro, Jan./Feb. 2000, pp. 34-41, vol. 20, No. 1. cited by other .
T.V. Lakshman et al., "High-Speed Policy-Based Packet Forwarding Using Efficient Multi-Dimensional Range Matching," Proceedings of ACM Sigcomm, Sep. 1998, pp. 191-202. cited by other .
V. Srinivasan et al., "Fast and Scalable Layer Four Switching," Proceedings of ACM Sigcomm, Sep. 1998, pp. 203-214. cited by other .
V. Srinivasan et al., "Packet Classification Using Tuple Space Search," Proceedings of ACM Sigcomm, Sep. 1999, pp. 135-146. cited by other .
V. Srinivasan et al., "Packet Classification Using Tuple Space Search," Computer Communication Review, Association for Computing Machinery, Oct. 1999, pp. 135-160, vol. 29, No. 4, XP: 000852194 Department of Computer Science, Washington University in St. Louis, USA. cited by other.

Primary Examiner: Duong; Frank
Attorney, Agent or Firm: Caven & Aghevli LLC

Claims

What is claimed is:

1. A data structure stored on a computer accessible medium comprising: a first bit mask; a number of entries, each entry including a key formed using the first bit mask; and hash tables representing a root node, wherein at least one of the entries includes a marker, the marker identifying a hash table having a second bit mask, wherein the second bit mask is a descendant of the first bit mask, wherein the marker identifies an array of descriptors, one of the descriptors identifying the hash table having the second bit mask.

2. The data structure of claim 1, further comprising: a rule identifier associated with one of the entries, the rule identifier identifying a rule associated with the key of the one entry.

3. The data structure of claim 2, further comprising: a priority class associated with the one entry, the priority class identifying a priority of the associated rule.

4. The data structure of claim 1, wherein each of the other descriptors are to identify a hash table having a bit mask that is a descendant of the first bit mask.

5. An apparatus comprising: a processing system; and a memory coupled with the processing system, the memory having a data structure stored therein, the data structure including a first bit mask, and a number of entries, each entry including a key formed using the first bit mask, wherein at least one of the entries includes a marker, the marker identifying a hash table having a second bit mask, wherein the second bit mask is a descendant of the first bit mask, wherein the marker of the data structure identifies an array of descriptors, one of the descriptors identifying the hash table having the second bit mask.

6. The apparatus of claim 5, wherein the data structure further comprises: a rule identifier associated with one of the entries, the rule identifier identifying a rule associated with the key of the one entry.

7. The apparatus of claim 6, wherein the data structure further comprises: a priority class associated with the one entry, the priority class identifying a priority of the associated rule.

8. The apparatus of claim 5, wherein each of the other descriptors are to identify a hash table having a bit mask that is a descendant of the first bit mask.

9. The apparatus of claim 5, wherein the memory comprises a dynamic random access memory.

10. The apparatus of claim 5, wherein the processing system includes a number of processing engines.

11. The apparatus of claim 5, wherein the processing system and the memory are located on a single integrated circuit device.

12. A data structure stored on a computer accessible medium comprising: a number of hash tables, each hash table including a bit mask and a number of entries, each entry including a key formed using the bit mask, at least one of the hash tables representing a root node; and a number of markers, each marker associated with one of the entries of one of the hash tables, the marker of an entry of a hash table identifying another hash table that is a descendant of that hash table, wherein the marker of the entry of the hash table identifies an array of descriptors.

13. The data structure of claim 12, wherein an entry of one of the hash tables is associated with a rule, the entry of the one hash table including a rule identifier for the rule.

14. The data structure of claim 13, wherein the entry of the one hash table further includes a priority associated with the rule.

15. The data structure of claim 12, wherein each of the descriptors are to identify one hash table that is a descendent of that hash table.

16. An apparatus comprising: a processing system; and a memory coupled with the processing system, the memory having a data structure stored therein, the data structure including a number of hash tables, each hash table including a bit mask and a number of entries, each entry including a key formed using the bit mask, at least one of the hash tables representing a root node; and a number of markers, each marker associated with one of the entries of one of the hash tables, the marker of an entry of a hash table identifying another hash table that is a descendant of that hash table, wherein the marker of the entry of the hash table identifies an array of descriptors.

17. The apparatus of claim 16, wherein an entry of one of the hash tables is associated with a rule, the entry of the one hash table including a rule identifier for the rule.

18. The apparatus of claim 17, wherein the entry of the one hash table further includes a priority associated with the rule.

19. The apparatus of claim 16, wherein each of the descriptors is to identify one hash table that is a descendent of that hash table.

20. The apparatus of claim 16, wherein the memory comprises a dynamic random access memory.

21. The apparatus of claim 16, wherein the processing system includes a number of processing engines.

22. The apparatus of claim 16, wherein the processing system and the memory are located on a single integrated circuit device.

23. A method comprising: selecting from a number of hash tables a hash table having a bit mask corresponding to a bit mask of a rule; adding an entry for the rule to the selected hash table; if the selected hash table has an ancestor hash table that is a root node, placing a marker in the root ancestor hash table, the marker identifying the selected hash table; and creating a search string based upon the rule and a bit mask of the root ancestor hash table.

24. The method of claim 23, wherein the added entry includes a key corresponding to the rule.

25. The method of claim 24, further comprising placing a rule identifier in the added entry, the rule identifier identifying the rule.

26. The method of claim 25, further comprising placing in the added entry a priority associated with the rule.

27. The method of claim 23, further comprising: comparing the search string with each of a number of entries of the root ancestor hash table to determine whether one of the entries has a key matching the search string.

28. The method of claim 27, further comprising: if none of the entries of the root ancestor hash table has a key matching the search string, adding a new entry to the root ancestor hash table; and placing a key in the new entry, the key corresponding to the search string; wherein the marker identifying the selected hash table is placed in the new entry of the root ancestor hash table.

29. The method of claim 27, wherein an entry of the root ancestor hash table has a key matching the search string, the method further comprising: placing the marker identifying the selected hash table in the matching entry of the root ancestor hash table if a threshold number of markers will not be exceeded at the matching entry.

30. The method of claim 29, wherein placement of the marker in the matching entry of the root ancestor hash table will exceed the threshold number of markers, the method further comprising: accessing an existing marker in the matching entry of the root ancestor hash table; and placing the marker in a hash table identified by the existing marker, wherein the identified hash table is an ancestor to the selected hash table.

31. The method of claim 30, wherein the act of placing the marker in the hash table identified by the existing marker comprises: creating a search string based upon the rule and a bit mask of the hash table identified by the existing marker; and comparing the search string with each of a number of entries of the hash table identified by the existing maker, wherein the marker is placed in one of the entries having a key matching the search string.

32. The method of claim 29, wherein placement of the marker in the matching entry of the root ancestor hash table will exceed the threshold number of markers, the method further comprising: overriding the threshold number of markers; and placing the marker identifying the selected hash table in the matching entry of the root ancestor hash table.

33. The method of claim 29, wherein the threshold number of markers is one.

34. The method of claim 23, wherein the bit mask of the selected hash table and the bit mask of the rule each comprise a tuple of dimension X.

35. The method of claim 34, wherein the dimension X comprises a number in a range of from 2 to 5.

36. An apparatus comprising: a memory system having stored thereon a set of instructions; and a processing system coupled with the memory system, wherein the set of instructions, when executed on the processing system, causes the processing system to select from a number of hash tables a hash table having a bit mask corresponding to a bit mask of a rule; add an entry for the rule to the selected hash table; and if the selected hash table has an ancestor hash table that is a root node, place a marker in the root ancestor hash table, the marker identifying the selected hash table, wherein execution of the set of instructions farther causes the processing system to create a search string based upon the rule and a bit mask of the root ancestor hash table.

37. The apparatus of claim 36, wherein the added entry includes a key corresponding to the rule.

38. The apparatus of claim 37, wherein execution of the set of instructions further causes the processing system to place a rule identifier in the added entry, the rule identifier identifying the rule.

39. The apparatus of claim 38, wherein execution of the set of instructions further causes the processing system to place in the added entry a priority associated with the rule.

40. The apparatus of claim 36, wherein execution of the set of instructions further causes the processing system to compare the search string with each of a number of entries of the root ancestor hash table to determine whether one of the entries has a key matching the search string.

41. The apparatus of claim 40, wherein execution of the set of instructions further causes the processing system to: if none of the entries of the root ancestor hash table has a key matching the search string, add a new entry to the root ancestor hash table; and place a key in the new entry, the key corresponding to the search string; wherein the-marker identifying the selected hash table is placed in the new entry of the root ancestor hash table.

42. The apparatus of claim 40, wherein an entry of the root ancestor hash table has a key matching the search string and wherein execution of the set of instructions further causes the processing system to: place the marker identifying the selected hash table in the matching entry of the root ancestor hash table if a threshold number of markers will not be exceeded at the matching entry.

43. The apparatus of claim 42, wherein placement of the marker in the matching entry of the root ancestor hash table will exceed the threshold number of markers and wherein execution of the set of instructions further causes the processing system to: access an existing marker in the matching entry of the root ancestor hash table; and place the marker in a hash table identified by the existing marker, wherein the identified hash table is an ancestor to the selected hash table.

44. The apparatus of claim 43, wherein execution of the set of instructions further causes the processing system, when placing the marker in the hash table identified by the existing marker, to: create a search string based upon the rule and a bit mask of the hash table identified by the existing marker; and compare the search string with each of a number of entries of the hash table identified by the existing maker, wherein the marker is placed in one of the entries having a key matching the search string.

45. The apparatus of claim 42, wherein placement of the marker in the matching entry of the root ancestor hash table will exceed the threshold number of markers and wherein execution of the set of instructions further causes the processing system to: override the threshold number of markers; and place the marker identifying the selected hash table in the matching entry of the root ancestor hash table.

46. The apparatus of claim 42, wherein the threshold number of markers is one.

47. The apparatus of claim 36, wherein the bit mask of the selected hash table and the bit mask of the rule each comprise a tuple of dimension X.

48. The apparatus of claim 47, wherein the dimension X comprises a number in a range of from 2 to 5.

49. An article of manufacture comprising: a computer accessible medium providing content that, when accessed by a computer, causes the computer to: select from a number of hash tables a hash table having a bit mask corresponding to a bit mask of a rule; add an entry for the rule to the selected hash table; and if the selected hash table has an ancestor hash table that is a root node, place a marker in the root ancestor hash table, the marker identifying the selected hash table, wherein the content, when accessed, further causes the computer to create a search string based upon the rule and a bit mask of the root ancestor hash table.

50. The article of manufacture of claim 49, wherein the added entry includes a key corresponding to the rule.

51. The article of manufacture of claim 50, wherein the content, when accessed, further causes the computer to place a rule identifier in the added entry, the rule identifier identifying the rule.

52. The article of manufacture of claim 51, wherein the content, when accessed, further causes the computer to place in the added entry a priority associated with the rule.

53. The article of manufacture of claim 49, wherein the content, when accessed, further causes the computer to compare the search string with each of a number of entries of the root ancestor hash table to determine whether one of the entries has a key matching the search string.

54. The article of manufacture of claim 53, wherein the content, when accessed, further causes the computer to: if none of the entries of the root ancestor hash table has a key matching the search string, add a new entry to the root ancestor hash table; and place a key in the new entry, the key corresponding to the search string; wherein the marker identifying the selected hash table is placed in the new entry of the root ancestor hash table.

55. The article of manufacture of claim 53, wherein an entry of the root ancestor hash table has a key matching the search string and wherein the content, when accessed, further causes the computer to: place the marker identifying the selected hash table in the matching entry of the root ancestor hash table if a threshold number of markers will not be exceeded at the matching entry.

56. The article of manufacture of claim 55, wherein placement of the marker in the matching entry of the root ancestor hash table will exceed the threshold number of markers and wherein the content, when accessed, further causes the computer to: access an existing marker in the matching entry of the root ancestor hash table; and place the marker in a hash table identified by the existing marker, wherein the identified hash table is an ancestor to the selected hash table.

57. The article of manufacture of claim 56, wherein the content, when accessed, further causes the computer, when placing the marker in the hash table identified by the existing marker, to: create a search string based upon the rule and a bit mask of the hash table identified by the existing marker; and compare the search string with each of a number of entries of the hash table identified by the existing maker, wherein the marker is placed in one of the entries having a key matching the search string.

58. The article of manufacture of claim 55, wherein placement of the, marker in the matching entry of the root ancestor hash table will exceed the threshold number of markers and wherein the content, when accessed, further causes the computer to: override the threshold number of markers; and place the marker identifying the selected hash table in the matching entry of the root ancestor hash table.

59. The article of manufacture of claim 55, wherein the threshold number of markers is one.

60. The article of manufacture of claim 49, wherein the bit mask of the selected hash table and the bit mask of the rule each comprise a tuple of dimension X.

61. The article of manufacture of claim 60, wherein the dimension X comprises a number in a range of from 2 to 5.

Description

FIELD OF THE INVENTION

The invention relates generally to computer networking and, more particularly, to a method and apparatus for classifying packets.

BACKGROUND OF THE INVENTION

Traditionally, packet routing in computer networks was based solely on the destination address of a packet. This routing technique essentially provided "best effort" delivery, and all traffic going to the same address was treated identically. However, packet routing based on destination address alone is insufficient to meet growing demands for greater bandwidth, enhanced security, and increased flexibility and service differentiation. To meet these objectives, equipment vendors and service providers are providing more discriminating forms of routing, including firewalls, quality of service (QoS) based routing, and bandwidth and/or resource reservation.

Generally, a firewall comprises any component, or combination of components, capable of blocking certain classes of traffic (e.g., "unwanted" or "suspicious" traffic). Firewalls are often utilized in corporate networks and other enterprise networks, and the firewall is usually implemented at the entry and/or exit points--i.e., the "trust boundary"--of the network. A typical firewall includes a series of packet filters that are designed to carry out a desired security policy.

Network service providers may have a wide array of customers, each requiring different services, service priorities, and pricing. To provide differentiated services to a number of different customers--or, more generally, to provide preferential treatment to certain classes of network traffic--service providers have implemented a variety of mechanisms, including QoS based routing and bandwidth/resource reservation. The goal of QoS based routing is to provide service differentiation for a number of different customers and/or traffic types. QoS based routing may include, for example, routing based upon class of service, special queuing procedures (e.g., per-flow queuing), and fair scheduling methods. Integrally tied with QoS routing is bandwidth or resource reservation. Bandwidth reservation generally includes reserving a specified bandwidth for certain types of traffic. For example, bandwidth reservation may be applied to traffic between two points, or bandwidth reservation may be applied to traffic relating to a certain application (e.g., multimedia, video, etc.).

To implement the above-described routing methodologies (e.g., firewalls, QoS routing, bandwidth reservation) that provide more discriminating routing of network traffic, as well as to perform other policy-based packet forwarding techniques, it is necessary to classify packets. Generally, packet classification comprises distinguishing between packets belonging to different flows or between packets associated with different traffic types. As used herein, a "flow" is a series of packets that share at least some common header characteristics (e.g., packets flowing between two specific addresses). A packet is usually classified based upon one or more fields in the packet's header. One or more filters, or "rules," are applied to this header information to determine which flow the packet corresponds with or what type of traffic the packet is associated with.

A number of methods--both hardware and software implementations--for performing packet classification based upon header data are known in the art. However, packet classification is often the bottleneck in routers, especially those routers supporting high speed links (e.g., gigabit capacity), as packet classification techniques struggle to keep pace with advances in link speeds. Further, some conventional packet classification schemes lack the ability to efficiently handle a large number of classification filters (or rules) and may also have large memory requirements.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a schematic diagram illustrating an embodiment of a network having a router.

FIG. 2 is a schematic diagram illustrating an embodiment of the router shown in FIG. 1.

FIG. 3 is a schematic diagram illustrating an embodiment of a processing device shown in FIG. 2.

FIG. 4 is a schematic diagram illustrating the makeup of an exemplary packet.

FIG. 5 is a schematic diagram illustrating an embodiment of the packet classifier shown in FIG. 2.

FIG. 6 is a schematic diagram illustrating an embodiment of a rule, as shown in FIG. 5.

FIG. 7A is a schematic diagram illustrating another embodiment of a rule.

FIG. 7B is a schematic diagram illustrating an embodiment of the rule shown in FIG. 7A, including a bit mask and value set.

FIGS. 7C-7I are schematic diagrams illustrating a further embodiment of the rule shown in FIG. 7A, including a bit mask and value set.

FIG. 8 is a schematic diagram illustrating yet another embodiment of the rule shown in FIG. 7A, including a bit mask and value set.

FIG. 9 is a schematic diagram illustrating an embodiment of a hash table, as shown in FIG. 5.

FIGS. 10A-10C present schematic diagrams, each of the diagrams illustrating an embodiment of a rule and the corresponding bit mask and value set.

FIG. 11 is a schematic diagram illustrating the ancestor-descendant relationships for the rules shown in FIG. 10A.

FIG. 12 is a block diagram illustrating an embodiment of a method of constructing a forest of hash tables data structure.

FIGS. 13A-13F are schematic diagrams, each illustrating a hash table assembled using the method of FIG. 12, as applied to the rules shown in FIGS. 10A-10C.

FIG. 14 is a schematic diagram illustrating the forest of hash tables data structure shown in FIGS. 13A-13F.

FIG. 15A is a block diagram illustrating an embodiment of a method of searching a forest of hash tables data structure.

FIG. 15B is a block diagram illustrating another embodiment of the method of searching a forest of hash tables data structure.

DETAILED DESCRIPTION OF THE INVENTION

Embodiments of a packet classifier are disclosed herein. The disclosed embodiments of the packet classifier are described below in the context of a router implementing a firewall. However, it should be understood that the disclosed embodiments are not so limited in application and, further, that the embodiments of a packet, classifier described in the following text and figures are generally applicable to any device, system, and/or circumstance where classification of packets or other communications is needed.

Illustrated in FIG. 1 is an embodiment of a network 100. The network 100 includes a router 200 providing a firewall 201. The router 200 (and firewall 201) may implement a specified security policy, QoS routing, and/or resource reservation, as well as any other desired policy-based routing scheme. To discriminate between packets belonging to different flows and/or between packets associated with different traffic types, the router 200 also includes a packet classifier 500, which includes a set of rules, or filters, designed to implement the desired routing scheme. Embodiments of the packet classifier 500 are described below in greater detail. The router 200 (as well as firewall 201 and packet classifier 500) may be implemented on any suitable computing system or device (or combination of devices), and one embodiment of the router 200 is described below with respect to FIG. 2 and the accompanying text.

The router 200 is coupled via a plurality of links 130--including links 130a, 130b, . . . , 130n--with a number of nodes 110 and/or a number of subnets 120. A node 110 comprises any addressable device. For example, a node 110 may comprise a computer system or other computing device, such as a server, a desktop computer, a laptop computer, or a hand-held computing device (e.g., a personal digital assistant or PDA). A subnet 120 may comprise a collection of other nodes, and a subnet 120 may also include other routers or switches. Each of the links 130a-n may be established over any suitable medium,--e.g., wireless, copper wire, fiber optic, or a combination thereof--using any suitable protocol--e.g., TCP/IP (Transmission Control Protocol/Internet Protocol), HTTP (Hyper-Text Transmission Protocol), as well as others.

The network 100 may comprise any type of network, such as a Local Area Network (LAN), a Metropolitan Area Network (MAN), a Wide Area Network (WAN), a Wireless LAN (WLAN), or other network. The router 200 also couples the network 100 with another network (or networks) 5, such as, by way of example, the Internet and/or another LAN, MAN, LAN, or WLAN. Router 200 may be coupled with the other network 5 via any suitable medium, including a wireless, copper wire, and/or fiber optic connection using any suitable protocol (e.g., TCP/IP, HTTP, etc.).

It should be understood that the network 100 shown in FIG. 1 is intended to represent an exemplary embodiment of such a system and, further, that the network 100 may have any suitable configuration. For example, the network 100 may include additional nodes 110, subnets 120, and/or other devices (e.g., switches, routers, hubs, etc.), which have been omitted from FIG. 1 for ease of understanding. Further, it should be understood that the network 100 may not include all of the components illustrated in FIG. 1.

In one embodiment, the router 200 comprises any suitable computer system, and the packet classifier 500 comprises a software application that may be implemented or executed on this computer system. An embodiment of such a computer system is illustrated in FIG. 2.

Referring to FIG. 2, the computer system 200 includes a bus 205 to which various components are coupled. Bus 205 is intended to represent a collection of one or more buses--e.g., a system bus, a Peripheral Component Interface (PCI) bus, a Small Computer System Interface (SCSI) bus, etc. that interconnect the components of computer system 200. Representation of these buses as a single bus 205 is provided for ease of understanding, and it should be understood that the computer system 200 is not so limited. Those of ordinary skill in the art will appreciate that the computer system 200 may have any suitable bus architecture and may include any number and combination of buses.

Coupled with bus 205 is a processing device (or devices) 300. The processing device 300 may comprise any suitable processing device or system, including a microprocessor, a network processor, an application specific integrated circuit (ASIC), or a field programmable gate array (FPGA), or similar device. An embodiment of the processing device 300 is illustrated below in FIG. 3 and the accompanying text.

Computer system 200 also includes system memory 210 coupled with bus 205, the system memory 210-comprising, for example, any suitable type of random access memory (e.g., dynamic random access memory, or DRAM). During operation of computer system 200 an operating system 214, the packet classifier 500, as well as other programs 218 may be resident in the system memory 210. Computer system 200 may further include a read-only memory (ROM) 220 coupled with the bus 205. During operation, the ROM 220 may store temporary instructions and variables for processing device 300, and ROM 220 may also have resident thereon a system BIOS (Basic Input/Output System). The computer system 200 may also include a storage device 230 coupled with the bus 205. The storage device 230 comprises any suitable non-volatile memory, such as, for example, a hard disk drive. The packet classifier 500, as well as operating system 214 and other programs 218 (e.g., a software implementation of firewall 201), may be stored in the storage device 230. Further, a device 240 for accessing removable storage media (e.g., a floppy disk drive or a CD ROM drive) may be coupled with bus 205.

The computer system 200 may include one or more input devices 250 coupled with the bus 205. Common input devices 250 include keyboards, pointing devices such as a mouse, and scanners or other data entry devices. One or more output devices 260 may also be coupled with the bus 205. Common output devices 260 include video monitors, printing devices, and audio output devices (e.g.; a sound card and speakers).

Computer system 200 further comprises a network interface 270 coupled with bus 205. The network interface 270 comprises any suitable hardware, software, or combination of hardware and software capable of coupling the computer system 200.with the network (or networks) 5. The computer system 200 also includes a link interface 280. Link interface 280 comprises any suitable hardware, software, or combination of hardware and software capable of coupling the computer system 200 with each of the links 130a-n.

It should be understood that the computer system 200 illustrated in FIG. 2 is intended to represent an exemplary embodiment of such a computer system and, further, that this computer system may include many additional components, which have been omitted for clarity and ease of understanding. By way of example, the computer system 200 may include a DMA (direct memory access) controller, a chip set associated with the processing device 300, additional memory (e.g., a cache memory), as well as additional signal lines and buses. Also, it should be understood that the computer system 200 may not include all of the components shown in FIG. 2.

In one embodiment, the packet classifier 500 comprises a set of instructions (i.e., a software application) run on a computer system--e.g., the computer system 200 of FIG. 2 or other suitable computing device. The set of instructions may be stored locally in storage device 230 or, alternatively, the instructions may be stored in a remote storage device (not shown in figures) and accessed via network 100 (or from another network 5). During operation, the set of instructions may be executed on processing device 300, wherein the instructions (or a portion thereof) may be resident in system memory 210.

In another embodiment, the packet classifier 500 comprises a set of instructions stored on a machine accessible medium, such as, for example, a magnetic media (e.g., a floppy disk or magnetic tape), an optically accessible disk (e.g., a CD-ROM disk), a flash memory device, etc. To run packet classifier 500 on, for example, computer system 200, the device 240 for accessing removable storage media may access the instructions on the machine accessible medium, and the instructions may then be executed in processing device 300. In this embodiment, the instructions (or a portion thereof) may again be downloaded to system memory 210.

In another embodiment, the packet classifier 500 is implemented in hardware or a combination of hardware and software (e.g., firmware). For example, the packet classifier 500 may be implemented in an ASIC, an FPGA, or other similar device that has been programmed in accordance with the disclosed embodiments.

As previously noted, an embodiment of processing device 300 is illustrated in FIG. 3 and the accompanying text. It should be understood, however, that the processing device 300 shown in FIG. 3 is but one embodiment of a processing device upon which the disclosed embodiments of a packet classifier 500 may be implemented. Those of ordinary skill in the art will appreciate that the disclosed embodiments of packet classifier 500 may be implemented on many other types of processing systems and/or processor architectures.

Turning now to FIG. 3, the processing device 300 includes a local bus 305 to which various functional units are coupled. Bus 305 is intended to represent a collection of one or more on-chip buses that interconnect the various functional units of processing device 300. Representation of these local buses as a single bus 305 is provided for ease of understanding, and it should be understood that the processing device 300 is not so limited. Those of ordinary skill in the art will appreciate that the processing device 300 may have any suitable bus architecture and may include any number and combination of buses.

A core 310 and a number of processing engines 320 (e.g., processing engines 320a, 320b, . . . , 320k) are coupled with the local bus 305. In one embodiment, the core 310 comprises a general purpose processing system, which may execute operating system 214. Core 310 may also control operation of processing device 300 and perform a variety of management functions, such as dispensing instructions to the processing engines 320 for execution. Each of the processing engines 320a-k comprises any suitable processing system, and each may include an arithmetic and logic unit (ALU), a controller, and a number of registers (for storing data during read/write operations). Also, in one embodiment, each processing engine 320a-k provides for multiple threads of execution (e.g., four).

Also coupled with the local bus 305 is an on-chip memory subsystem 330. Although depicted as a single unit, it should be understood that the on-chip memory subsystem 330 may--and, in practice, likely does--comprise a number of distinct memory units and/or memory types. For example, such on-chip memory may include SDRAM (synchronous dynamic random access memory), SRAM (static random access memory), and/or flash memory (e.g., FlashROM). It should be understood that, in addition to on-chip memory, the processing device 300 may be coupled with off-chip memory (e.g., ROM 220, off-chip cache memory, etc.).

Processing device 300 further includes a bus interface 340 coupled with local bus 305. Bus interface 340 provides an interface with other components of computer system 200, including bus 205. For simplicity, bus interface 340 is depicted as a single functional unit; however, it should be understood that, in practice, the processing device 300 may include multiple bus interfaces. For example, the processing device 300 may includes a PCI bus interface, an IX (Internet Exchange) bus interface, as well as others, and the bus interface 340 is intended to represent a collection of one or more such interfaces.

It should be understood that the embodiment of processing device 300 illustrated and described with respect to FIG. 3 is but one example of a processing device that may find use with the disclosed embodiments of a packet classifier and, further, that the processing device 300 may have other components in addition to those shown in FIG. 3, which components have been omitted for clarity and ease of understanding. For example, the processing device 300 may include other functional units (e.g., an instruction decoder unit, an address translation unit, etc.), a thermal management system, clock circuitry, additional memory, and registers. Also, it should be understood that a processing device may not include all of the elements shown in FIG. 3.

Referring now to FIG. 4, illustrated is an example of a packet 400, as may be received at router 200 (e.g., from other networks 5). The packet includes a header 410 and a payload (or data) 450. The header 410 includes a number of fields, including fields 420a, 420b,. . ., 420n. Generally, the fields 420a-n contain identifying information about the packet 400. By way of example, the header 410 may include the protocol 420i (e.g., TCP), a source IP address 420k, a destination address 420j, a source port 420m, and a destination port 420n. Each of the source and destination addresses 420k, 420i may include thirty-two (32) bits, each of the source and destination ports 420m, 420n sixteen (16) bits, and the protocol 420i eight (8) bits. It will be appreciated by those of ordinary skill in the art that these are but a few examples of the types of information that may be contained in the header of a packet and, further, that packet header 410 may contain any other information, as required by the specific hardware and/or application at hand.

Illustrated in FIG. 5 is an embodiment of packet classifier 500. The packet classifier 500 includes a rule database 510, a hash table data structure 520, and a search agent 530. Packet classifier 500 also stores a list of hash tables to search 540 and a "best" matched rule 550. In one embodiment, the packet classifier 500 shown in FIG. 5 is implemented in software (either a set of instructions stored in computer system 200 or a set of instructions read from a machine-accessible medium). In another embodiment, however, the packet classifier 500 of FIG. 5 may be implemented in hardware or a combination of hardware and software.

Rule database 510 includes a number of rules 600, including rules 600a, 600b, . . . , 600y. The collection of rules 600a-y is designed to implement a desired policy-based routing scheme (e.g., a firewall, QoS routing, and/or resource reservation, etc.), as described above. Various embodiments of a rule 600 are illustrated in FIGS. 6 through 8. The hash table data structure 520 (also referred to herein as a "forest of hash tables") includes a number of hash tables 900, including hash tables 900a, 900b, . . . , 900j. An embodiment of a hash table 900 is shown and described below with respect to FIG. 9. Within the hash table data structure 520, the rules. 600 are organized into a number of "equivalent sets" of rules, wherein each equivalent set (defined below) is represented by one of the hash tables 900. The forest of hash tables data structure 520 is described below in greater detail, and an embodiment of a method of constructing the hash table data structure is presented below in FIG. 12 and the accompanying text.

Search agent 530 provides packet classifier 500 with the ability to search the hash table data structure 520. More specifically, search agent 530 can identify one or more rules 600 that are to be applied to an incoming packet based upon information (e.g., header data) contained in the packet. Embodiments of a method of searching the hash table data structure 520 are presented below in FIGS. 15A and, 5B and the accompanying text. The list of hash tables to search 540 is a dynamic list identifying those hash tables 900 of hash table data structure 520 that need to be searched for any received packet. The "best" matched rule 550, which is also dynamically updated throughout the search process, stores a rule identified by search agent 530 that is to be applied to a received packet. In one embodiment, the rule stored as the "best" matched rule 550 corresponds to the highest priority rule. However, it should be understood that selection of the "best" matched rule may be based on any suitable criteria.

Turning to FIG. 6, an embodiment of a rule 600 is illustrated. Generally, the rule 600 specifies a set of criteria that suggests a particular flow to which a packet satisfying the criteria belongs. The rule 600 includes a number of components, including components 602a, 602b, . . . , 602x. In one embodiment, each component 602a-x corresponds to a field in the header of a packet. However, in other embodiments, the components 602a-x of a rule 600 may include other information, such as application header fields, link identification information, time-of-day, etc. A packet "matches" the rule if, for each component 602a-x, the corresponding field in the header matches that component. A component 602a-x may comprise a regular expression on the corresponding header field or, alternatively, a mask or character/number specification applied to the corresponding header field. It should be noted here that, generally, any regular expression on a header field may be expanded to one or more masks. A mask or character/number specification may be in the form of an exact match (e.g., destination port=80) or a range specification (e.g., destination port.ltoreq.1023). A rule may contain any suitable number of components 602a-x, and the number X of fields in a rule is referred to herein as the dimension. Also, a rule 600 has an associated action 604 (e.g., accept, block, etc.) that is to be applied to any packet matching that rule.

Each rule 600 may be represented by a bit mask 610 and a value set 620. The bit mask 610 is a bit array having bits set (e.g., a "1-bit") for those bits that the rule 600 "cares for," whereas those bits that the rule does "not care for" are not set (e.g., a "0-bit"). The value set 620 is a bit array that contains, at those bits set in the bit mask 610 (i.e., at those bits the rules cares for), the actual value of these bits, respectively, in the rule. At those bits of value set 620 corresponding to bits that are not set (e.g., a "0-bit") in the bit mask 610, the value set 620 contains a "0-bit". Any group of two or more rules is said to be "equivalent" if they have the same bit mask (although they may not have the same value set), and a group of equivalent rules comprises an "equivalent set." As will be explained in greater detail below, the bit mask 610 and value set 620 of each rule 600 facilitate organization of the rules 600 into the hash table data structure 520--each hash table 900 including an equivalent set of rules--and also provides a mechanism for indexing into the hash table data structure during the search process.

Referring to FIG. 7A, an embodiment of a rule is illustrated. The rule 700 includes five components--i.e., the rule's dimension is five--including a source address 702a, a destination address 702b, a protocol 702c, a source port 702d, and a destination port 702e, as well as an action 704. The combination of these packet header fields is sometimes referred to as a "5-tuple." Of course, it should be understood that FIG. 7A presents but one example of a rule and, further, that a rule may include any suitable number and type of header fields (i.e., the rule may be of any dimension).

Illustrated in FIG. 7B is an example of the rule shown in FIG. 7A. The rule specifies a source address 702a equal to "*", a destination address 702b equal to "255.128.*.*", a protocol 702c equal to "TCP", a source port 702d equal to "80", and a destination port 702e that is ".ltoreq.1023", where the character "*" represents a "wild card" (i.e., any value can match the wild card). The action 704 is "block" (i.e., any packet satisfying the rule is not allowed). The bit mask 710 and value set 720 for this example are also shown in FIG. 7B. The bit mask 710 includes a portion 712a corresponding to the source address, a portion 712b corresponding to the destination address, a portion 712c corresponding to the protocol, a portion 712d corresponding to the source port, and a portion 712e corresponding to the destination port. Note that where an exact match is required in the rule 700, the bit mask 710 includes a "1-bit". However, where an exact match is not required--e.g., where a wild card "*" is present--the bit mask includes a "0-bit", as the rule does "not care for" these bits.

The value set 720 includes a portion 722a corresponding to the source address, a portion 722b corresponding to the destination address, a portion 722c corresponding to the protocol, a portion 722d corresponding to the source port, and a portion 722e corresponding to the destination port. At those bits in the value set 720 corresponding to the bits that have been set (e.g., a "1-bit") in the bit mask 710, the value set 720 includes actual values from the rule (e.g., the source port 80 is specified in binary notation as "0000000001010000"). To assist the reader, in FIG. 7B (as well as FIGS. 7D-7I, 8, and 10A-10C), shading is used to identify those bits in value set 720 that correspond to a "0-bit" in the bit mask 710 (or, in other words, to identify those bits in value set 720 that the rule does "not care for").

In FIG. 7B, the destination port specification of ".ltoreq.1023" can be expressed in binary notation as "000000**********". However, not all ranges are amenable to expression by a single mask, and this concept is illustrated in FIGS. 7C through FIG. 7I. Referring to FIG. 7C, the rule 700 now includes a destination port specification of ">1023" (all other parameters being equal to those shown in FIG. 7B). The range expression ">1023" cannot be represented by a single character string or "prefix". However, this expression can be broken down into a set of prefixes. More specifically, the range of ">1023" can be delineated by the following series of prefixes: "000001**********"; "00001***********"; "0001************"; "001 *************"; "01**************"; and "1***************" Accordingly, the rule 700 specified in FIG. 7C can be expanded into six different rules, one for each of the six distinct prefixes comprising the range specification ">1023". This is shown in FIGS. 7D through 7I, which illustrates the expansion of the rule 700 of FIG. 7C into six different bit mask and value set specifications. In each of FIGS. 7D through 7I, only the portion 712e and the portion 722e corresponding to the destination port of the bit mask 710 and value set 720, respectively, are illustrated (as all other components are the same as that shown in FIG. 7B). In FIGS. 7D through 7I, shading is again used in the value sets 720 to distinguish those bits the rule does "not care for" (i.e., those bits corresponding to a "0-bit" in the bit mask 710) from those bits the rule does "care for" (i.e., those bits corresponding to a "1-bit" in the bit mask 710). It should be noted here that, in general, a range of N-bits can be broken down into a maximum of 2N prefixes.

Another example of the 5-tuple rule shown in FIG. 7A is illustrated in FIG. 8. The rule 800 includes a source address equal to "*", a destination address equal to "128.128.*.*", a protocol equal to "TCP", a source port equal to "21", and a destination port that is ".ltoreq.1023". The action 804 for rule 800 is "block". The bit mask 810 for rule 800 has a portion 812a corresponding to the source address, a portion 812b corresponding to the destination address, a portion 812c corresponding to the protocol, a portion 812d corresponding to the source port, and a portion 812e corresponding to the destination port. Likewise, the value set 820 has a portion 822a corresponding to the source address, a portion 822b corresponding to the destination address, a portion 822c corresponding to the protocol, a portion 822d corresponding to the source port, and a portion 822e corresponding to the destination port (shading again being used in the value set, as described above). Note that rule 800 is different than rule 700, as the destination address and source port specifications are not the same. However, the bit mask 810 of rule 800 is identical to the bit mask 710 of rule 700 in FIG. 7B--i.e., these two rules are "equivalent." Two such equivalent rules can be referenced by the same hash table 900, and an embodiment of such a bash table is shown in FIG. 9.

Turning now to FIG. 9, the illustrated hash table 900 includes a bit mask 910, which is the bit mask for all rules in the equivalent set of rules represented by this hash table. Hash table 900 also includes a number of entries 930, including entries 930a, 930b, . . . , 930r. Generally, each of the entries 930a-r corresponds to one of the rules 600; however, an entry 930 may be entered in the hash table 900 simply to provide a marker to another hash table, as will be explained below.

In one embodiment, each of the entries 930a-r includes a key 932, a priority 934, a rule identifier 936, and one or more markers 938 (i.e., entry 930a includes key 932a, priority 934a, rule identifier 936a, and marker(s) 938a, and so on). It should be understood, however, that FIG. 9 presents but one example of the make-up of a hash table and, further, that the entry 930 of hash table 900 may include other information. For example, an entry 930 may include a pointer for chaining in the event of collisions, as well as other information.

As will be explained below, if a rule has a bit mask matching the bit mask 910 of a hash table 900, the search agent 530 will compare the rule against each entry 930 in this hash table to look for a match, and it is the key 932 of each entry 930 that is used in this comparison. Essentially, the keys 932 provide a mechanism for indexing and retrieving rules within the hash table data structure 520. The priority 634 gives the priority of a rule corresponding to an entry 630, and the rule identifier 636 identifies the corresponding rule (e.g., a memory location or other identifier of the rule in rule database 510).

As noted above, one or more markers 938 may also be present in each entry 930 of hash table 900. When searching the hash table data structure 520 for a rule corresponding to a received packet, if there is a match between this packet an en entry 930 of the hash table, the marker (or markers) 938 of that entry is used to identify other hash tables that need to be searched. These additional hash tables that are to be searched are "descendants" of the hash table, which hash table is an "ancestor" to all it's descendants, as will be explained in greater detail below. Generally, a marker 938 comprises a pointer to a memory location of the other hash table. However, in another embodiment, a marker 938 identifies a memory location of an array of hash table descriptors 940 (i.e., entry 930b has a corresponding array of descriptors 940b, and so on). The array of descriptors 940 includes a number of descriptors, each identifying a memory location of another hash table. An entry 930 of hash table 900 may include any desired number of markers 938. In one embodiment, a threshold number of markers is set for the entries of the hash tables, such that markers can be "pushed" lower down into the forest of hash tables data structure (although, in some instances, a marker may still be placed in an entry even though the threshold is exceeded). The use of a threshold to determine at what level to enter a marker in the forest of hash tables data structure is explained in greater detail below.

Referring now to FIG. 10A, a number of rules are shown, including rules 1000a (Rule A), 1000b (Rule B), 1000c (Rule C), 1000d (Rule D), 1000e (Rule e), and 1000f (Rule F). The bit mask and value set for each rule are also shown in FIG. 10A (i.e., rule 1000a includes bit mask 1010a and value set 1020a, and so on). In FIG. 10A (and FIGS. 10B and 10C), shading is again used in the value sets to distinguish those bits that a rule does "not care for" (i.e., those bits corresponding to a "0-bit" in the bit mask) from those bits the rule does "care for" (i.e., those bits corresponding to a "1-bit" in the bit mask).

Each of the rules 1000a-f specifies a source address and a destination port--i.e., each of the rules 1000a-f has a dimension of two (2). The rules 1000a-f of FIG. 10A (as well as rules 1000g-r of FIGS. 10B and 10C) are used herein to present a simple example illustrating the disclosed embodiments of a packet classifier 500. However, it should be understood that the disclosed embodiments of the packet classifier may be applied to rules of any dimension (e.g., a dimension of five, as shown in FIGS. 6 through 7I, as well as other dimensions).

A first rule is a "descendant" of a second rule if the second rule--i.e., the "ancestor" of the first rule--has a bit mask comprising a subset of the first rule's bit mask. The bit mask of the second rule is a subset of the bit mask of the first rule if the second rule's bit mask includes at least one set bit (e.g., a "1-bit") in common with the first rule's bit mask. For example, referring to FIG. 10A, rule 1000b (Rule B) is a descendant of rule 1000a (Rule A) and, likewise, Rule A is an ancestor to Rule B. A rule may have a plurality of descendants, and a rule may also have multiple ancestors. Further, a rule may have both an ancestor (or ancestors) and a descendant (or descendants). This ancestor-descendant relationship for rules 1000a-f is shown in FIG. 11. As illustrated in this figure, Rule F is a descendant of each of Rules A, B, C, D, and E. Rules B and C, while each is an ancestor to Rule F, are descendants of Rule A, whereas Rule B is also an ancestor of Rule C. Rule E, while being an ancestor to rule F, is also a descendant of Rule D. Rules A and D, which have no ancestors, are referred to herein as "root nodes" (or "root hash tables").

Shown in FIG. 12 is an embodiment of a method 1200 for constructing a forest of hash tables data structure (e.g., hash table data structure 520 of FIG. 5). The method of FIG. 12 is illustrated and described below with respect to rules 1000a through 1000f (i.e., Rules A through F) of FIG. 10A, as well as rules 1000g through 1000r (i.e., Rules G through R) of FIGS. 10B and 10C, and the hash tables of FIGS. 13A through 13F (i.e., Hash Tables A through F). Thus, in the example described below, the rule database 510 initially includes Rules A through R. Also, the threshold number o