| Compilation of access control lists -> Monitor Keywords |
|
|
  Compilation of access control listsRelated Patent Categories: Multiplex Communications, Data Flow Congestion Prevention Or ControlThe Patent Description & Claims data below is from USPTO Patent Application 20070041318. Brief Patent Description - Full Patent Description - Patent Application Claims
CROSS-REFERENCE TO RELATED APPLICATIONS [0001] The present invention is related to the following commonly assigned U.S. Patent Applications, the contents of which are hereby incorporated by reference: [0002] The present invention is related to the following commonly assigned U.S. Patent Applications, the contents of which are hereby incorporated by reference: [0003] Ser. No. 09/557,480 entitled Method for High Speed Packet Classification, by Andrew McRae filed Apr. 24, 2000 (McRael); [0004] Ser. No. 10/170,896 entitled, Incremental Compilation for Classification and Filtering Rules by Andrew McRae filed Jun. 13, 2002 (McRae2); and [0005] Ser. No. 10/072,824 entitled, Method For Classifying Packets Using Multi-Class Structures, by Liang Li et al filed Feb. 8, 2002 the contents of which are hereby incorporated by reference. FIELD OF THE INVENTION [0006] This invention relates to memory usage in a turboACL arrangement for classifying packets received by a network router. The invention relates generally to the classification and/or filtering of data packets, and more specifically to the high speed filtering and/or classification of data packets. More particularly it relates to the division of tables used in compiling the classification tables into noncontiguous blocks BACKGROUND INFORMATION [0007] In a communications network, there is a well-recognized need to classify information units, such as packets, that are passed between the various network devices in the network, e.g., routers and switches, in order to support a wide range of applications, such as security control, packet filtering, Class of Service (CoS) and Quality of Service (QoS). Often in such networks, these network devices use access control lists (ACLs) to, inter alia, classify packets for these applications. [0008] An ACL typically comprises an ordered list of access control entries (ACEs), i.e., rules, where each rule defines a pattern (criterion) that is compared with received packets. The pattern could specify a particular source or destination address, a protocol or some other field that is looked for in the packet. For example, the pattern might be defined to look for a specific protocol in the packet's header such as, the Transmission Control Protocol (TCP) or the Internet Protocol (IP). The pattern is used to determine if the rule applies to the packet. If the pattern is found in the packet, the rule is said to apply to the packet. [0009] Associated with each rule is an action that specifies the act to be taken if the rule applies. In its simplest form, this action may be to allow the matched packet to proceed towards its destination, i.e., "permit," or to stop the packet from proceeding any further, i.e., "deny." Conversely, if there is no match to any of the ACL's rules, the action may be to drop the packet, i.e., "a final deny." In a more sophisticated form, complex policies and filtering rules may be implemented in the ACL to determine the course of the data packet. [0010] Typically, a packet is classified by searching for the first rule in the ACL that applies to the packet. The number of rules involved and the amount of processing time needed to make this determination often depends on the approach taken. For example, one approach would be to run through the list of rules starting from the first rule in the list and continuing towards the last rule in the list until a matching rule, i.e., a rule that applies to the packet, is found. This approach is simple, but is not very efficient. For example, the time spent processing each packet may vary depending on the packet. Packets that meet the criteria associated with rules earlier in the list will be processed faster than packets that meet criteria associated with rules that are positioned farther down the list. [0011] One approach to obtaining an overall faster processing of packets is to predetermine the frequency of the matching of the various rules and to place the most selected rules at the top of the list. However, this method is highly dependent on the packet mix and is not very efficient should this mix change. Another approach is to implement a technique whereby packets are classified using a predetermined number of lookup operations such as described in McRael. [0012] McRael describes a technique whereby a packet's header is divided into sections. These sections are applied to a hierarchy of lookup tables that represent all possible combinations of matching rules for all values of the packet header sections to determine an outcome such as, e.g., a first matching rule that applies to the packet. These lookup tables must exist before a packet can be classified. Computing resources, such as processor time and memory, needed to generate these lookup tables depends in part on the number of rules in the ACL. Generally, as the number of rules in the ACL increases, the computing resources needed to build and hold the lookup tables increases. In systems where computing resources are limited, the number of rules that the technique can support may be limited due to the limited resources available. [0013] McRae2, discloses an arrangement in which successive lookup tables, after the first set of tables, are compiled at runtime in response to the characteristics of packets being classified. This materially reduces compilation time and also saves memory space corresponding to classification rules that are not needed for the packets entering the router. The arrangement described in McRael is often termed "TurboACL," as is the related arrangement described in McRae2. [0014] However, with the ever-increasing number of classification rules and the increasing diversity of packet characteristics, available memory space is still a problem. A table below the top level may require a very large block of contiguous memory locations. This may stall compilation because of a limitation of memory recourses. SUMMARY OF THE INVENTION [0015] The invention alleviates the memory space problem by dividing lower level tables into noncontiguous blocks, each of which may be located anywhere in the memory space. In the prior arrangements a pair of indexes was used to enter a location in a single contiguous table. Instead, we use one of the two indexes as a pointer to one of the blocks into which the table is divided and we use the other index to identify the entry within that block. [0016] The invention improves compilation speed of the table entries by the use of aggregate bit vectors and by alignment of bit vectors and aggregate bit vectors with cache boundaries. Each bit vector is divided into sections. Each section is represented by one bit in an "aggregate bit vector" (ABV). Each bit in the ABV is set if, and only if, at least one bit is set in the corresponding section of the bit vector. ABV usage reduces the number of memory reads made by the TurboACL algorithm. [0017] The invention handles Table overflow conditions and memory allocation failures gracefully. A table overflow condition is encountered when there is no free entry available in a lookup table for a new packet. In the prior arrangements the table overflow condition is handled by rebuilding the tables. TurboACL table rebuilding takes substantial CPU resources and frequent TurboACL table rebuilding has the potential to adversely affect functioning of the network device. To alleviate this problem, we pass all packets encountering a table overflow condition to an optimized packet classification path and allow rebuild of the tables only after a predefined period of time. The new optimized packet classification path for overflow traffic uses the TurboACL algorithm data structures and takes up classification of packets from any level in the TurboACL structure. BRIEF DESCRIPTION OF THE DRAWINGS [0018] The above and further advantages of the invention may be better understood by referring to the following description in conjunction with the accompanying drawings in which like reference numbers indicate identical or functionally similar elements: [0019] FIG. 1 is a schematic block diagram of a network that can be advantageously implemented with the present invention; Continue reading... Full patent description for Compilation of access control lists Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Compilation of access control lists patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Compilation of access control lists or other areas of interest. ### Previous Patent Application: Method and apparatus for restoring a network Next Patent Application: Method and system for generating an annotated network topology Industry Class: Multiplex communications ### FreshPatents.com Support Thank you for viewing the Compilation of access control lists patent info. IP-related news and info Results in 0.30706 seconds Other interesting Feshpatents.com categories: Canon USA , Celera Genomics , Cephalon, Inc. , Cingular Wireless , Clorox , Colgate-Palmolive , Corning , Cymer , |
||
