SYSTEMS AND METHODS FOR PROCESSING ACCESS CONTROL LISTS (ACLS) IN NETWORK SWITCHES USING REGULAR EXPRESSION MATCHING LOGIC

• US 20080186971A1
• Filed: 08/27/2007
• Published: 08/07/2008
• Est. Priority Date: 02/02/2007
• Status: Abandoned Application

• Current Assignee: LSI Corporation (Broadcom, Inc.)
• Original Assignee: Tarari, Inc. (Broadcom, Inc.)
• Inventors: Carmichael, Jeff, Smerdon, Gary
• Application Number:
  US11/845,696
• Publication Number:
  US 20080186971A1
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: A61P 1/04 for ulcers, gastritis or reflux esophagitis, e.g. antacids, inhibitors of acid secretion, mucosal protectants
• CPC Class Codes: A61P 13/12 of the kidneys
• CPC Class Codes: A61P 19/02 for joint disorders, e.g. arthritis, arthrosis
• CPC Class Codes: A61P 19/10 for osteoporosis
• CPC Class Codes: A61P 25/00 Drugs for disorders of the nervous system
• CPC Class Codes: A61P 27/02 Ophthalmic agents
• CPC Class Codes: A61P 27/12 for cataracts
• CPC Class Codes: A61P 3/00 Drugs for disorders of the metabolism of the blood or the extracellular fluid A61P7/00
• CPC Class Codes: A61P 3/04 Anorexiants; Antiobesity agents
• CPC Class Codes: A61P 3/06 Antihyperlipidemics
• CPC Class Codes: A61P 3/10 for hyperglycaemia, e.g. antidiabetics
• CPC Class Codes: A61P 7/02 Antithrombotic agents; Anticoagulants; Platelet aggregation inhibitors
• CPC Class Codes: A61P 9/00 Drugs for disorders of the cardiovascular system
• CPC Class Codes: A61P 9/04 Inotropic agents, i.e. stimulants of cardiac contraction; Drugs for heart failure
• CPC Class Codes: A61P 9/10 for treating ischaemic or atherosclerotic diseases, e.g. antianginal drugs, coronary vasodilators, drugs for myocardial infarction, retinopathy, cerebrovascula insufficiency, renal arteriosclerosis
• CPC Class Codes: A61P 9/12 Antihypertensives
• CPC Class Codes: C07D 217/08 with a hetero atom directly attached to the ring nitrogen atom
• CPC Class Codes: C07D 401/06 linked by a carbon chain containing only aliphatic carbon atoms
• CPC Class Codes: C07D 401/10 linked by a carbon chain containing aromatic rings
• CPC Class Codes: C07D 401/12 linked by a chain containing hetero atoms as chain links
• CPC Class Codes: C07D 401/14 : containing three or more hetero rings
• CPC Class Codes: C07D 409/14 : containing three or more hetero rings
• CPC Class Codes: C07D 413/10 : linked by a carbon chain containing aromatic rings
• CPC Class Codes: C07D 413/12 : linked by a chain containing hetero atoms as chain links
• CPC Class Codes: C07D 413/14 : containing three or more hetero rings
• CPC Class Codes: C07D 417/10 : linked by a carbon chain containing aromatic rings
• CPC Class Codes: C07D 487/04 : Ortho-condensed systems
• CPC Class Codes: C07D 495/04 : Ortho-condensed systems

Abstract

A network node, such as an Ethernet switch, is configured to monitor packet traffic using regular expressions corresponding to Access Control List (ACL) rules. In one embodiment, the regular expressions are expressed in the form of a state machine. In one embodiment, as packets are passed through the network node, an access control module accesses the packets and traverses the state machine according to certain qualification content of the packets in order to determine if respective packets should be permitted to pass through the network switch.

Claims

1. A method of selectively allowing data packets to flow through a network switch to respective recipients of the data packets, the method comprising:

receiving an access control list comprising a plurality of qualification patterns each associated with an action, the qualification patterns each indicating one or more packet characteristics;

converting the qualification patterns into corresponding regular expressions;

generating a state machine comprising a plurality of state transition instructions corresponding to the regular expressions, wherein the state machine comprises a plurality of terminal states corresponding with matches to respective regular expressions;

storing the state transition instructions in a memory that is accessible by a network switch;

receiving a plurality of packets; and

for each packet received by the network switch;

generating a packet fingerprint comprising an indication of one or more of the packet characteristics; and

traversing the state machine using the packet fingerprint in order to locate a matched regular expression that is matched by the packet fingerprint and, in response to locating the matched regular expression, executing the action associated with the matched regular expression.

2. The method of claim 1, wherein the packet characteristics comprise one or more of a source MAC address, destination MAC address, source IP address, destination IP address, source TCP port, destination TCP port, protocol, and packet payload.

3. The method of claim 1, wherein the state transition instructions associated with the terminal states comprise result action codes indicating the action associated with the respective matched regular expression.

4. The method of claim 3, wherein the result action codes comprise priorities indicating respective priorities of matched regular expressions.

5. The method of claim 1, wherein the actions comprise permit and deny passage of the packet through the network switch.

6. The method of claim 1, further comprising determining an order of a plurality of fields of the packet fingerprint based at least on a determined subset of most frequently accessed fields of the packet fingerprints in traversing the state machine.

7. A method of storing a state machine, the method comprising:

storing a state machine in a memory, the state machine comprising a plurality of states and transitions therebetween, the state machine comprising a plurality of branches, each having a terminal state, that are associated with matches of an input string to respective regular expressions;

selecting a predetermined number of states in each branch of the state machine for storage in a cache memory that has faster access and read times than the memory;

selecting one or more additional states of at least a first branch of the state machine in response to determining that the first branch comprises unselected states that are associated with each of a plurality of branches;

deselecting one or more states of at least a second branch of the state machine in response to determining that the second branch comprises selected states that are only associated with the second branch; and

storing the selected states of the state machine in the cache memory.

8. The method of claim 7, further comprising:

in response to accessing a last cached state of a third branch of the state machine, storing one or more additional states of the third branch in a buffer memory.

9. The method of claim 7, wherein state transition instructions associated with two or more states are retrieved from the memory in a single read cycle.

10. A compiler for generating a plurality of regular expressions corresponding to rules of an access control list, the rules comprising qualification patterns and associated actions, wherein the regular expressions are configured to match packets having qualification content that matches the qualification patterns of the access control list, the compiler comprising:

an input module adapted to receive an access control list; and

a conversion module adapted to convert the qualification patterns into regular expressions that locate the respective qualification patterns, the conversion module also adapted to generate match result codes associated with each regular expression, the match result codes indicating priorities of the respective qualification patterns and actions associated with the respective qualification patterns.

11. The compiler of claim 10, wherein the qualification content comprises content of at least one field of respective packets.

12. The compiler of claim 11, wherein the qualification content further comprises at least one payload byte of respective packets.

13. The compiler of claim 10, wherein the compiler is further configured to generate a state machine corresponding to the regular expressions, wherein the state machine is configured for at least partial storage on a network node such that the state machine is traversed at the network node based on the qualification content of received packets.

14. The compiler of claim 13, wherein respective actions indicated by qualification patterns are executed when a corresponding qualification content of a packet is received at the network node.

15. A method of monitoring passage of packets of a packet stream through a network node, the method comprising:

receiving a plurality of state transition instructions representing a state machine having a plurality of terminal states;

receiving a packet of the packet stream;

generating a packet fingerprint comprising an ordered representation of characteristics of the packet, the characteristics comprising one or more of a source MAC address, a destination MAC address, a source IP address, a destination IP address, a source TCP port, a destination TCP port, a protocol, and a payload of the packet;

traversing the state machine using the bits of the packet fingerprint;

selecting one terminal state of the state machine corresponding with a highest priority access control rule; and

determining an action associated with the selected terminal state.

16. The method of claim 15, wherein the packet fingerprint comprises

an action associated with each terminal state of the state machine reached in the traversing, the actions comprising (a) permit the packet to flow through the network node and (b) deny the packet passage through the network node.

17. The method of claim 15, wherein the packet fingerprint comprises:

6 bytes indicating a source MAC address of the packet, followed by 4 bytes indicating a source IP address of the packet, followed by 4 bytes indicating a source TCP port, followed by 6 bytes indicating a destination MAC address of the packet, followed by 4 bytes indicating a destination IP address of the packet, followed by 4 bytes indicating a destination TCP port of the packet, followed by 1 byte indicating a protocol of the packet.

18. The method of claim 15, wherein the packet fingerprint comprises 128 bits indicating a source address, 128 bits indicating a destination address, 4 bits indicating an IP version, 8 bits indicating a traffic class, 20 bits indicating a Quality of Service flow label, 16 bits indicating a payload length in bytes, 8 bits indicating a next header, and 8 bits indicating a hop limit.

19. A computerized system for monitoring packets that pass through a network node, the system comprising:

a memory storing a state machine, the state machine comprising a plurality of states and transitions therebetween, the state machine comprising a plurality of branches, each having a terminal state, that are associated with matches of an input string to respective regular expressions; and

means for selecting a subset of the plurality of states that are likely to be most frequently traversed by packets received by the network node.

20. The computerized system of claim 19, wherein the means for selecting comprises a processor configured to select only certain states for caching in a cache memory having access and read times that are faster than the memory.

21. The computerized system of claim 19, wherein a predetermined number of states of each branch of the state machine are selected for caching.

22. The computerized system of claim 19, wherein a respective state is selected for caching if at least a predetermined number of branches each comprise the respective state.