ASSIGNING RULES TO DATA UNITS
BACKGROUND
[0001] A computer network generally refers to a group of interconnected wired
and/or wireless devices such as, for example, laptops, mobile phones, servers, fax machines, printers, etc. The networked computers may often transfer data in the form of packets from one device to another device. A network device may be configured with one or more rules and the rules may be assigned to the data units based on flow identifiers such as source and destination port numbers and source and destination IP addresses.
BRIEF DESCRIPTION OF THE DRAWINGS
[0002] The invention described herein is illustrated by way of example and not by
way of limitation in the accompanying figures. For simplicity and clarity of illustration, elements illustrated in the figures are not necessarily drawn to scale. For example, the dimensions of some elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference labels have been repeated among the figures to indicate corresponding or analogous elements.
[0003] FIG. 1 illustrates an embodiment of a network environment.
[0004] FIG. 2 illustrates an embodiment of a network device of FIG. 1
[OOBE] FIG. 3 illustrates an embodiment of a processor of the network device.
[0006] FIG. 4 illustrates an embodiment of the processor 250 comprising logical
blocks that may assign rules to the packets using a bitmap based rule matching.
[0007] FIG. 5 depicts a flow-chart that illustrates an embodiment of the processor
250 assigning rules to the data units based on bitmap lookup.
[0008] FIG. 6 depicts a flow identifier layout 600 comprising cells, with each cell
representing one or more source and destination flow identifiers.
[0009] FIG. 7 depicts an embodiment of the processor 250 generating a bitmap.
[0010] FIG. 8 depicts an embodiment of the bitmap.
[0011] FIG. 9 illustrates an embodiment of the processor 250 that assigns the
rules to the data units, while operating in a regular processing path.
[0012] FIG. 10 illustrates an embodiment of the processor 250 that assigns the
rules to the data units, while operating in a specialized processing path.
[0013] FIG. 11 depicts a table of nodes that the processor 250 may traverse to
assign the rules to data units, while operating in a specialized processing path.
DETAILED DESCRIPTION
[0014] The following description describes a system and a network device that
may assign rules to data units, for example, received over a network path. In the following description, numerous specific details such as logic implementations, resource partitioning/sharing/duplication implementations, types and interrelationships of system components, and logic partitioning/integration choices are set forth in order to provide a more thorough understanding of the present invention. It will be appreciated, however, by one skilled in the art that the invention may be practiced without such specific details. In other instances, control structures, gate level circuits, and full software instruction sequences have not been shown in detail in order not to obscure the invention. Those of ordinary
skill in the art, with the included descriptions, will be able to implement appropriate functionality without undue experimentation.
[0015] References in the specification to "one embodiment", "an embodiment", "an
example embodiment", etc., indicate that the embodiment described may include a particular feature, structure, or characteristic, but every embodiment may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to effect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described.
[0016] Embodiments of the invention may be implemented in hardware, firmware,
software, or any combination thereof. Embodiments of the invention may also be implemented as instructions stored on a machine-readable medium, which may be read and executed by one or more processors. A machine-readable medium may include any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computing device). For example, a machine-readable medium may include read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; electrical, optical, acoustical or other forms of propagated signals (e.g., carrier waves, infrared signals, digital signals, etc.), and others. Further, firmware, software, routines, instructions may be described herein as performing certain actions. However, it should be appreciated that such descriptions are merely for convenience and that such actions in fact result from computing devices,
processors, controllers, or other devices executing the firmware, software, routines, instructions, etc.
[0017] An embodiment of a network environment 100 is illustrated in FIG. 1. The
network environment 100 may comprise one or more clients such as a client 110-A and a client 110-B, a router 142 and a router 144, a network 150, and a server 190.
[0018] The client 110-A and 110-B may comprise a desktop computer system, a
laptop computer system, a personal digital assistant, a mobile phone, or any such computing system. In one embodiment, the client 110-A may generate one or more data units such as packets, which comprise flow identifiers. In one embodiment, the flow identifiers may represent entities such as the port addresses and IP addresses that enable transfer of data units between a source system and a destination system.
[0019] In one embodiment, the client 110-A may send a data unit to the server
190. The data unit may comprise, for example, port A1 as a source port address and port S1 as a destination port address. Also, the client 110-B may receive a packet from the server 190 and the packet may comprise Sm as the source port address and port Bk as the destination port address. In one embodiment, the client 110-A and client 110-B may be coupled to an intermediate network device such as the router 142 via a local area network (LAN) to send and receive the packets. The client 110-A and client 110-B may, for example, support protocols such as hyper text transfer protocol (HTTP), file transfer protocols (FTP), and TCP/IP.
[0020] The server 190 may comprise a computer system capable of receiving the
packets from the router 144 and sending responses to destination system via the
router 144. In one embodiment, the server 190 may send and receive packets, to the router 144, over the ports S1 to Sm. In one embodiment, the server 190 may receive packets from the client 110-A over the port S1. The server 190 may send packets, to the client 110-B, over the port Sm. The server 190 may comprise, for example, a web server, a transaction server, a database server, and such other servers.
[0021] The network 150 may comprise one or more network devices such as a
switch or a router, which may receive the packets, process the packets, and send the packets to an appropriate network device. The network 150 may enable transfer of packets between the client 110-A, 110-B, and the server 190. The network devices of the network 150 may be configured to support various protocols such as TCP/IP.
[0022] The routers 142 and 144 may enable transfer of packets between the client
110-A, client 110-B, and the server 190 via the network 150. In one embodiment, the router 142 may receive packets from the client 110-A, process the packets before sending the packets to the network 150. In one embodiment, the router 142 may determine a rule that may be assigned to the data units based on a bitmap lookup. In one embodiment, the router 142 may be configured with rules that may in turn be assigned to the packets based on the source and destination flow identifiers of the packets. In one embodiment, the rules may be based on ranges of source and destination flow identifiers of the packets.
[0023] For example, a network administration may configure the router 142 with a
rule such as "do not allow packets to be sent onward if the packet comprises a source port identifier in the range (A1-A32) and a destination port identifier in the
range (S1-S32)". In one embodiment, the router 142 may determine whether the
source and destination port identifiers of the received packet fall within the range specified in the rule and may assign an appropriate rule to the packet based on bitmap based rule matching. In one embodiment, the router 142 may generate a flow identifier layout and then generate a bitmap based on the cells covered by a set of overlapping rules. Such a rule matching may be performed while dealing with packets generated by a security, billing, quality of service (QoS) and such other application
[0024] In one embodiment, the router 142 may generate a flow identifiers layout
that may comprise one or more cells and each cell may represent a set of source and destination flow identifiers. The router 142 may identify one or more connected regions that represent a region, on the flow identifiers layout, comprising a set of overlapping rules. For example, if rules R2 and R3 overlap on the rule R1, the connected region may be defined as a region formed by the boundary of all the overlapping rules R1-R3. In one embodiment, the connected region may cover one or more cells either completely or partially and such cells may be referred to as 'mask cells'. In one embodiment, the router 142 may determine whether a cell is a mask cell and may include the cell into the bitmap if the cell is a mask cell. The router 142 may further populate the bitmap by determining the control bit status, which represents whether the mask cell is completely or partially covered and appropriate rules or metadata for each mask cell based on the status of the control bit.
[0025] In one embodiment, the router 142 may simply perform a bitmap based rule
matching to determine and assign an appropriate rule to a packet. Such an approach may reduce the processing cycles consumed as compared to such task
being performed using a software approach to perform range matching of rules.
Also, the bitmap lookup based approach for determining a matching rule may avoid the usage of content addressable memories (CAM) to determine a matching rule. Avoiding a CAM for performing such tasks may save power as the CAMs consume substantial amounts of power.
[0026] An embodiment of the router 142 is illustrated in Fig. 2. The router 142
may comprise a network interface 210, a processor 250, and a memory 280. The router 142 may receive one or more packets from client 110-A and/or 110-B and may determine, for example, the rule that may be assigned to the packet based on the bitmap look-up before sending the packets onward.
[0027] The network interface 210 may transfer one or more packets between the
client 110, the network 150 and the router 142. For example, the network interface 210 may receive the packets from the client 110-A and send the packets to the processor 250 for further processing. Also, the network interface 210 may receive packets from the processor 250 and send it to an adjacent network device for further processing. The network interface 210 may provide physical, electrical, and protocol interfaces to transfer packets between the client 110 and the network 150.
[0028] The memory 280 may store packets and packet related information that
may be used by the processor 250 to process the packets. In one embodiment, the memory 280 may store packet metadata, bitmap, look-up tables, data structures and such other parameters that enable the processor 250 to process the packets. In one embodiment, the memory 280 may comprise a dynamic random access memory (DRAM) and a static random access memory (SRAM).
[0029] The processor 250 may receive one or more packets from the network
interface 210, process the packets, and send the packets to the network interface
210. In one embodiment, the processor 250 may process the packets, for example, by assigning a rule, performing header processing, performing packet validation and IP lookup, determining the output port and such other processing before sending the packet to the network interface 210. In one embodiment, the processor 250 may comprise Intel® IXP2400 network processor.
[0030] In one embodiment, the processor 250 may generate the flow identifier
layout by representing a sub-range of source ports and destination ports by a single cell. The flow identifier layout may thus comprise multiple cells. In one embodiment, the processor 250 may generate a bitmap based on the flow identifier layout and the overlapping rules that may cover the mask cells. The bitmap may comprise a list of mask cells covered completely or partially by a connected region. The processor 250 may assign a rule to an incoming packet by performing a bitmap based rule matching. Representing a sub-range of source and destination flow identifiers by a single cell and using a control bit to represent whether a cell is a mask cell may reduce the memory requirements.
[0031] An embodiment of the processor 250 is illustrated in Fig. 3. The processor
250 may comprise programmable processing units (PPUs) 310-1 to 310-N, a scratch pad 320, a memory 330, a programmable control unit 350, and a control engine 370.
[0032] The memory 330 may store a bitmap generated by the programmable
control unit 350 and data structures that may be used by the programmable processing units 310-1 to 310-N and the programmable control unit 350 to assign an appropriate rule to the packets. In one embodiment, the memory 330 may comprise a dynamic random access memory (DRAM) and a static random access
memory (SRAM).
[0033] The scratch pad 320 may store, for example, a buffer handler and such
other data corresponding to each packet in a pre-specified memory location that may be exchanged between two programmable processing units. In one embodiment, the scratch pad 320 may store information corresponding to a packet Px, in a memory location Lxyz, wherein x represents the packet identifier, y represents the sinking programmable processing unit and z represents the sourcing programmable processing unit. For example, a memory location L012 may store information corresponding to a packet PO written by the programmable processing unit 310-1 and read by the programmable processing unit 310-2.
[0034] The control engine 370 may configure the processor 250, initiate
applications, terminate applications and perform such other management functions. The control engine 370 may support user interfaces such as a graphical user interface (GUI) for receiving and displaying information from a user. In one embodiment, the control engine 370 may receive one or more rules that may be provided by, for example, a network administrator and configure the processor 250 based on the rules.
[0035] The programmable processing units 310-1 to 310-N may co-operatively
operate to perform packet processing. Each programmable processing unit 310-1 to 310-N may comprise one or more sub-programmable processing units. The sub-programmable processing units may perform packet processing in parallel, for example, to maintain the line rate at which the packets arrive. A group of sub-programmable processing units may perform a logical function, which may be referred to as a microblock. In one embodiment, the sub-programmable processing units may exchange data using a scratch pad memory 320. The
programmable processing units 310-1 to 310-N may support logic blocks and each logic block may perform a sub-task to, collectively, complete a task.
[0036] In one embodiment, the programmable processing units 310-1 to 310-N
may receive a packet, extract the flow identifiers from the packet, and determine a mask cell in the flow identifiers layout, which comprises the flow identifiers extracted from the packet. In one embodiment, the cell may be deemed to be a mask cell if the cell is covered either partially or completely by a connected region. In one embodiment, the programmable processing units 310-1 to 310-N may lookup a bit-map and assign a rule to the packet if a control bit corresponding to the mask cell equals a first level and may send the packet as an exception to the programmable control unit 350 if the control bit equals a second level. In one embodiment, the programmable processing units 310-1 to 310-N may, also, generate metadata and pass the metadata values to the programmable control unit 350.
[0036] The programmable control unit 350 may handle protocol messages,
configure and update tables and data sets that may be used by the programmable processing units 310-1 to 310-N. In one embodiment, the programmable control unit 350 may generate the flow identifiers layout and then generate a bitmap based on the mask cells and the rules associated with the mask cells. In one embodiment, the programmable control unit 350 may assign rules to packets sent as an exception based on the metadata of such packets. In one embodiment, the metadata may comprise, for example, a connected region identifier and projections of a sub-region comprising the mask cell on the horizontal and vertical axes of the flow identifier layout.
[0038] In one embodiment, the programmable control unit 350 while generating
the bitmap may identify the mask cells, which are either completely or partially covered by the connected region. In one embodiment, the programmable control unit 350 may identify a first set and a second set of mask cells that are completely covered by the connected region and a third set of mask cells that are partially covered the connected region. In one embodiment, the programmable control unit 350 may identify the first set of mask cells that are completely covered by a highest priority rule and may assign a first level L1 to the control bit of the first set of mask cells. In one embodiment, the programmable control unit 350 may identify the second set of mask cells that are partially covered by a highest priority rule and may assign a second level to the control bit of the second set of mask cells. In one embodiment, the programmable control unit 350 may identify the third set of mask cells, which are partially covered by the connected region and may assign a second level to the control bit of the third set mask cells.
[0039] An embodiment of the processor 250 comprising logical blocks that may
assign rules to the packets using a bitmap based rule matching is depicted in FIG. 4. The programmable processing units 310-1 to 310-N may support logic blocks such as a receive 410, a flow classify 420, a forward 440, and a transmit 460. The logic blocks 410, 420, 440, and 460 may form a regular processing path 450. The programmable control unit 350 may support a logic block that may perform the operations of the specialized processing path 480.
[0040] The receive 410 may receive a packet and extract the source and
destination flow identifiers. The receive 410 may store, for example, the flow identifiers in a scratch pad 320.
[0041] The flow classify 420 may poll the scratch pad 320, read the flow identifiers
stored by the receive 410, and determine a cell in the flow identifier layout, which matches the extracted source and destination flow identifier combination. The flow classify 420 may perform a lookup of the bitmap to check the control bit of the mask cell. The flow classify 420 may assign the rule associated with the mask cell to the packet if the control bit equals a first level. In one embodiment, the mask cell may belong to the first set of mask cells if the control bit equals the first value. The flow classify 420 may store a first valid signal in the scratch pad 320. The forward 440 may read the first valid signal from the scratch pad 320 and may determine the next network device to which the packet may be forwarded. The transmit 460 may transmit the packet onward after reading the first valid signal from the scratch pad 320.
[0042] The flow classify 420 may send the packet as an exception to the
specialized processing path 480 if the control bit associated with the mask cell equals the second level L2. In one embodiment, the flow classify 420 may determine the metadata associated with the mask cell and may send the metadata to the specialized processing path 480. The flow classify 420 may store a second valid signal in the scratch pad 320. The second valid signal may comprise the metadata as well. The flow classify 420 may send metadata comprising projections of the sub-regions, on the axes of the flow identifiers layout, that comprise the mask cell and the connected region identifier that covers the mask cell.
[0043] The specialized processing path 480 may populate the data structures, in
the bitmap, generated for storing the metadata after reading the second valid
signal. In one embodiment, the specialized processing path 480 may use the
metadata information, sent by the regular processing path 450, to unambiguously determine the rule that may be assigned to the packet.
[0044] An embodiment of the processor 250 assigning rules to the data units
received over a network path is depicted in the flow chart of FIG. 5. In block 510, the programmable control unit 350 supporting the specialized processing path 480 may generate cells to form a flow identifier layout with each cell representing, for example, a non-overlapping sub-range of source and destination flow identifiers.
[0045] In one embodiment, each cell may be two-dimensional, with the horizontal
dimension representing the sub-range of the source flow identifiers and the vertical dimension representing the sub-range of the destination flow identifiers. The programmable control unit 350 may generate non-overlapping cells such that the linear arrangement of cells may form a flow identifier layout representing an entire range of source port and destination port identifiers.
[0046] In block 520, the programmable control unit 350 may identify mask cells,
among the cells in the flow identifier layout. In one embodiment, the connected region may represent a group of cells that are covered either completely or partially within the boundary formed by a set of overlapping rules, with each rule assigned to a sub-range of the source and destination identifiers. In one embodiment, the connected region comprises all cells covered either completely or partially, at least, by one rule of the one or more overlapping rules.
[0047] In block 530, the programmable control unit 350 may generate a bitmap by
assigning the first value L1 to the control bit of a first set of mask cells that are completely covered by a highest priority rule and a second value to the control bit of a second set of mask cells that are partially covered by a highest priority rule
and a third set of mask cells partially covered by the connect region. The bitmap
may comprise a rule associated with the first set of mask cells and metadata associated with the second set of cells and the third set of cells.
[0048] In block 540, the programmable processing block 310-1 supporting the
receive 410 may receive a packet and extract the flow identifiers of the packet.
[0049] In block 550, the programmable processing block 310-2 supporting the flow
classify 420 may identify the mask cell that comprise the flow identifiers of the packet.
[0050] In block 560, the programmable processing block 310-2 supporting the flow
classify 420 may check if the control bit of the mask cell equals a first level and causes control to pass to block 570 if the condition is not true and to block 580 otherwise.
[0051] In block 570, the programmable control unit 350, supporting the specialized
processing path 480, may process the packet and assign an appropriate rule to the packet based on the metadata received.
[0052] In block 580, the programmable processing block 310-2 supporting the flow
classify 420 may process the packet and assign a rule associated with one of the first set of mask cells.
[0053] An embodiment of a flow identifier layout 600 representing a pre-
determined range of flow identifiers by one or more cells is depicted in FIG. 6. The flow identifier layout 600 comprises a horizontal axis 610 and a vertical axis 620. In one embodiment, the horizontal axis 610 may represent a pre-determined range of source port identifiers and the vertical axis 620 may represent a predetermined range of destination port identifiers. However, in other embodiments, the horizontal axis 610 and vertical axis 620 may, respectively, represent other
flow identifiers such as source and destination IP addresses.
[0054] For example, the pre-determined range of source flow identifiers and the
destination flow identifiers represented on the layout 600 may, respectively, equal 0-2048. The layout 600 may comprise 64 cells arranged in the form of 8 rows with each row comprising 8 cells and each cell representing 256 source and 256 destination flow identifiers. The cell 601-1 may represent a sub-range (0-256) of the source and the destination port identifiers. However, the number of cells may be increased or decreased to represent the same pre-determined range. Such an increase or decrease in the number of cells may cause a change in the memory requirements.
[OO55] A rule, as described above, may be applicable to a sub-range of source
and destination ports. For example, a rule R2 may be applicable to a sub-range (256-818) of source ports and sub-range (818 to 1152) of destination ports identifiers. The rule R2 may, thus, cover cells 604-2, 604-3, 604-4, 605-2, 605-3, and 605-4, which may be covered either completely or partially by a connected region CR1 comprising the rule R2. The rule R1 may cover, either partially or completely, the cells 603-3 to 603-7, 604-3 to 604-7,605-3 to 605-7, and 606-3 to 606-7 and the rule R3 may cover, either partially or completely, the cells 606-4 to 606-6, 607-4 to 607-6, and 608-4 to 608-6. The rule R4 may cover, either partially or completely, the cells 604-6 to 604-8 and 605-6 to 605-8. However, the rules R2, R3, and R4 overlap on rule R1.
[0056] A connected region CR1 may comprise cells, within a boundary marked by
indices (A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, and P), which covers the rules R1-R4. The connected region CR1 covers cells {(603-3 to 603-7), (604-2 to 604-8), (605-2 to 605-8), (606-3 to 606-7), (607-4 to 607-6), and (608-4 to 608-6)}. In
one embodiment, the flow identifiers layout 600 is shown comprising only one
connected region CR1. However, the layout 600 may comprise more than one connected regions. In one embodiment, if two or more connected regions comprise a common cell, the programmable control unit 350 may unambiguously associate such a common cell to one of the connected region.
[0057] Also, the programmable processing units 310-1 to 310-N may determine
the projections HP681 to HP688 on the horizontal axis 610 and the projections VP661 to VP666 on the vertical axis 620 of sub-regions of the connected region CR1. In one embodiment, each sub-region may be formed either by a start vertex or an end vertex of each region representing a rule. Also, the area between the end vertex of one region and a start vertex of the other region may form a sub-region as well. For example, the projection of sub-region PABO on the horizontal axis 610 may equal HP681 and HP682 and the projection of the sub-region PABO on the vertical axis 620 may equal VP662 and VP663.
[0058] The sub-regions NCRS, SRDT, TEUV, VUFW, WGHM, LIJK, NOLM,
PAJK, BXYI, XCHY, and DEFG may have horizontal and vertical projections (HP682, HP683, VP661, and VP665), (HP683, HP684, VP661, and VP665), (HP684, HP685, VP661, and VP666), (HP685, HP686, VP661, and VP666), (HP686, HP687, VP661, and VP665), (HP687, HP688, VP662, and VP663), (HP682, HP687, VP661 and VP662), (HP681, HP688, VP662, VP663), (HP682, HP687, VP663, and VP664), (HP682, HP687, VP664, and VP665), and (HP684, HP686, VP665, and VP666) respectively.
[0059] An embodiment of the processor 250 generating a bitmap is depicted in
FIG. 7. In one embodiment, the programmable control unit 350 of the processor 250 may generate a bitmap. In block 710, the programmable control unit 350 may
generate a list of mask cells, for example, 604-4, 604-7, 605-5, and 607-5, that is covered either completely or partially by the connected region CR1.
[0060] In block 730, the programmable control unit 350 may initiate a loop
comprising blocks 740-790 for each mask cell.
[0061] In block 740, the programmable control unit 350 may determine whether
the rule covers the mask cell completely and control passes to block 750 if the condition is true and to block 780 otherwise.
[0062] In block 750, the programmable control unit 350 may determine whether
the highest priority rule completely covers the mask cell and control passes to block 780 if the condition is not true and to block 770 otherwise.
[0063] In block 770, the programmable control unit 350 may assign the highest
priority rule to the mask cell. In one embodiment, the programmable control unit 350 may store the identifier of the highest priority rule associated with the mask cell. In block 775, the programmable control unit 350 may set the control bit of the mask cell to the first value L1 as the mask cell is completely covered by the highest priority rule.
[0064] In block 780, the programmable control unit 350 may set data structures to
receive the metadata and store the meta-data in a memory location associated with the mask cell. In one embodiment, the programmable processing units 310-1 to 310-N may pass metadata values to the data structures after determining that the mask cell is either partially covered by the highest priority rule and/or covered the connected region CR1.
[0065] In block 790, the programmable control unit 350 may set the control bit of
the mask cell to a second level L2.
[0066] An embodiment of a bitmap 800 is depicted in FIG. 8. In one embodiment,
the bitmap 800 is shown comprising three columns: a cell identifier cell ID810, a control bit 820, and rule ID/metadata 830 to store the identifier of the mask cell, a first level L1 or a second level L2, and a rule ID or meta-data respectively.
[0067] Row 850-1 is shown comprising 607-5, L1, and R3 in columns 810, 820,
and 830 respectively. The entries 607-5, L1, and R3 indicate that the cell 607-5 is a mask cell belonging to the first set of mask cells, and the mask cell 607-5 is assigned a rule R3. In one embodiment, a packet comprising a source and destination flow identifier matching with that of the mask cell 607-5 may be assigned a rule R3. Row 850-2 is shown comprising 605-5, L1 and rule R1, which indicates that the cell 605-5 belongs to the first set of cells and is assigned a rule R1. In one embodiment, a packet comprising a source and destination flow identifier matching with that of the mask cell 605-5 may be assigned a rule R1.
[0068] Row 850-3 is shown comprising 604-4, L2, and (CR1; HP682; VP661) in
columns 810, 820, and 830 respectively. The entries 604-4, L2, and (CR1; HP682; VP661) indicate that the cell 604-4 is a mask cell belonging to the second set of mask cells and may be sent as an exception to the programmable control unit 350 along with the metadata (CR1; HP682; VP661). For example, the mask cell 604-4 is covered partially by the rules R1 and R2. If the rule R2 has highest priority compared to the rule R1, the programmable processing units 310-1 and 310-2 may not determine, unambiguously, the rule that may be assigned to a packet comprising flow identifiers represented by the mask cell 604-4. For example, a packet may comprise a source flow identifier and a destination flow identifier matching the sub-range of the flow identifiers represented by the mask
cell 604-4. However, the programmable processing units 310-1 to 310-N may not
determine the exact location within the mask cell 604-4 and may thus not determine, unambiguously, the rule that may be assigned to the packet. The control bit of the mask cell 604-4 may thus be set to the second level. The programmable processing units 310-1 to 310-N may send the packet as an exception to the programmable control unit 350 along with the metadata.
[0069] Row 850-N is shown comprising 604-7, L2, and (CR1, HP686 and VP661).
The programmable processing units 310 may not determine, unambiguously, the rule that may be assigned to a packet comprising flow identifiers represented by a mask cell that is partially covered by the connected region. The flow identifiers of the packet may be within the connected region or outside the connected region and due to such an ambiguity the packet may be sent as an exception. The programmable control unit 350 has thus set the control bit to the second level 12. The metadata HP686 represents the horizontal projection of the start vertex of the first sub-region, along the horizontal axis 610, which comprises the mask cell 604-7. The metadata VP661 represents the vertical projection of the start vertex of the first sub-region, along the vertical axis, which comprises the mask cell 604-7. As can be seen, the first sub-region along the horizontal axis 610, which includes the mask cell 604-7, is WGHM and the first sub-region along the vertical axis 620, which includes the mask cell 604-7, is NOLM.
[0070] An embodiment of the processor 250 that may assign the rules to the data
units, while operating in a regular processing path 450 is illustrated in FIG. 9. In one embodiment, the programmable processing units 310-1 to 310-N may support the regular processing path 450. In block 910, the programmable processing unit 310-1 receives one or more packets.
[0071] In block 920, the programmable processing unit 310-1 may extract the flow
identifiers of one or more packets. For example, the programmable processing unit 310-1 may extract the flow identifiers such as source port X65 and destination port Y68 from a packet P1 and source port X85 and destination port Y18 from a packet P2.
[0072] In block 930, the programmable processing unit 310-2 may determine the
mask cell based on the flow identifiers. The programmable processing unit 310-2 may determine that 607-5 is the mask cell comprising port identifiers (X65, Y68) of the packet P1. The programmable processing unit 310-2 may determine that 604-7 is the mask cell comprising port identifiers (X85, Y18) of the packet P2.
[0073] In block 940, the programmable processing unit 310-2 may check the
control bit of the mask cell. In one embodiment, the programmable processing unit 310-2 may check if the control bit 820 equals L1.
[0074] In block 950, the programmable processing unit 310-2 may determine
whether the control bit 820 equals L1 and control passes to block 960 if the condition is true and to block 990 otherwise. The programmable processing unit 310-2 may cause control to pass to block 960 in the case of the packet P1 and to block 980 in the case of the packet P2.
[0075] In block 960, the programmable processing unit 310-2 may apply the rule
indicated in rule ID/metadata 830 to the packet PL The programmable processing unit 310-2 may, thus, assign rule R3 to the packet PL
[0076] In block 970, the programmable processing units 310-3 and 310-N may
send the packet onward.
[0077] In block 980, the programmable processing unit 310-2 may determine the
metadata. In one embodiment, the metadata may comprise an identifier of the
connected region of which the mask cell 604-7 is a part of and the horizontal and vertical projections of the first sub-region along the horizontal and the vertical axes that comprise the mask cell 604-7.
[0078] In block 990, the programmable processing unit 310-2 may pass the meta-
data to the programmable control unit 350 and may send the packet P2 as an exception packet to the specialized processing path 480.
[0079] An embodiment of the processor 250 that assigns a rule to the data units,
while operating in a specialized processing path 480 is illustrated in FIG. 10. In block 1010, the programmable control unit 350 may receive the exception packet and the metadata as well. The programmable control unit 350 may receive the packet P2 and may determine the rule that may be assigned to the packet P2. The programmable control unit 350 may retrieve the metadata (CR1, HP686, and V661) from the bitmap 800.
[0080] In block 1015, the programmable control unit 350 may generate a list of
source nodes (Ls) and a list of destination nodes (Ld) based on the meta-data. In one embodiment, the programmable control unit 350 may determine the matching sub-regions, the rule covering the matching sub-regions, and the port range each of the matching regions may cover.
[0081] In block 1020, the programmable control unit 350 may traverse the list (Ls)
of source nodes to determine if there exists match between the source port identifier of the packet P2 and the port identifiers of the nodes.
[0082] In block 1025, the programmable control unit 350 may check with each
node if it comprises a source port identifier that matches the source port of the packet. The programmable control unit 350 may continue to check the sub-

sequent nodes if a match is not found and control passes to block 1025 on finding
a match.
[0083] In block 1030, the programmable control unit 350 may extract a set (U) of
rules defined for the node that comprises a port identifier, which matches with the
port identifier of the packet.
[0084] In block 1035, the programmable control unit 350 may traverse the list (Ld)
of destination nodes to determine if there exists match between the destination
port identifier of the packet P2 and the port identifiers of the nodes.
[0085] In block 1040, the programmable control unit 350 may check with each
node if it comprises a destination port identifier that matches the destination port
of the packet. The programmable control unit 350 may continue to check the subsequent nodes if a match is not found and control passes to block 1050 on finding
a match.
[0086] In block 1050, the programmable control unit 350 may extract a set (V) of
rules defined for the node that comprises a destination port identifier, which
matches with the destination port identifier of the packet.
[0087] In block 1060, the programmable control unit 350 may determine a union
(W) of sets U and V. In one embodiment, the union set W may comprise a list of
rules that may be common to the set U and V.
[0088] In block 1070, the programmable control unit 350 may check whether the
union set W comprises a single rule and control passes to block 1075 if the
condition is not true and to block 1090 otherwise.
[0089] In block 1075, the programmable control unit 350 may determine a rule,
which assigned highest priority. In block 1080, the programmable control unit 350
may assign the rule with the highest priority to the packet P2.
[0090] In block 1090, the programmable control unit 350 may assign the rule, in
the union set W, to the packet P2. In block 1095, the programmable control unit 350 may send the packet P2 onward.
[0091] An embodiment of a list of nodes traversed by the programmable control
unit 350 to determine the rule to be assigned to a packet is depicted in FIG. 11. The list 1100 may comprise three columns: a sub-region 1110, a matching rule 1120, and port range 1130. The rows 1151 to 1155 comprise values for each sub-region along the vertical axis 620 and the rows 1161-1167 comprise values for each sub-region along the horizontal axis 610.
[0092] The row 1151 is shown comprising VP661-VP662, R1, and Y2-Y3, which
correspond to the sub-region 1110, matching rule 1120, and the port range 1130 respectively. For example, the sub-region VP661-VP662 may refer to the sub-region NOLM and the rule assigned to the sub-region NOLM equals R1. The port range covered by the sub-region NOLM may equal Y20-Y30. Similarly, the rows 1152, 1153, 1154, and 1155 may comprise {(VP662-VP663), (R1, R2, R4), (Y31-Y40)}, {(VP663-VP664), (R1), (Y41-Y50)}, {(VP664-VP665), (R1, R3), (Y51-Y60)}, and {(VP665-VP666), (R3), (Y61-Y70)} respectively.
[0093] The row 1161 is shown comprising HP681-VP682, R2, and X30-X40, which
correspond to the sub-region 1110, matching rule 1120, and the port range 1130 respectively- For example, the projections HP681-HP682 may refer to the sub-region PABO and the rule assigned to PABO equals R2. The port range covered by PABO may equal X30-X40. Likewise, the rows 1162-1166 may comprise {(HP682-HP683), (R1.R2), (X41-X50)}, {(HP683-HP684), (R1), (X51-X60)}, {(HP684-HP685), (R1.R3), (X61-X70)}, {(HP685-VP686), (R1,R3,R4), (X71-X80)},
and {(HP686-VP687), (R4), (X81-X90)} respectively.
[0094] In one embodiment, the programmable control unit 350 may use data
structures such as pointers to traverse the nodes both along the vertical and the horizontal axis. The programmable control unit 350, as described above, receives meta-data from the regular processing path 450 and based on the meta-data traverses the nodes. The programmable control unit 350 may traverse the nodes along the vertical axis 620 until a node comprising a destination port identifier that matches the destination port identifier of the packet P2 is found.
[0095] In the above example, the programmable control unit 350 may traverse the
nodes corresponding to the sub-region NOLM and may determine that sub-region NOLM comprises the destination port identifier Y28 of the packet P2. The rule, which corresponds to the sub-region NOLM equals R3. Thus, the programmable control unit 350 may generate, as depicted in block 1030 of FIG. 10, a set U = {R3}. The programmable control unit 350 may then traverse the nodes representing the sub-regions (PABO, NCRS, SRDT, TEUV, VUFW, and WGHM) along the horizontal axis 610.
[0096] The programmable control unit 350 may stop traversing the nodes after
determining that the sub-region WGHM comprises the source port identifier X85 of the packet P2. Thus, the programmable control unit 350 may generate, as depicted in block 1050 of FIG. 10, a set V = {R1 and R3}. The programmable control unit 350 may then determine, as depicted in block 1060 of FIG. 10, the union set W = {R3}, which is the union of the sets U and V. As the union set W comprises only one rule R3, the programmable control unit 350 may assign the rule R3 to the packet P2.
[0097] Certain features of the invention have been described with reference to
example embodiments. However, the description is not intended to be construed
in a limiting sense. Various modifications of the example embodiments, as well as other embodiments of the invention, which are apparent to persons skilled in the art to which the invention pertains are deemed to lie within the spirit and scope of the invention.

What is claimed is:
1. A processor to process data units comprising
a programmable control unit to generate a bitmap comprising a first set of mask cells and a second set and a third set of mask cells, wherein the first set of mask cells are completely covered by a first highest priority rule, the second set of mask cells are partially covered by a second highest priority rule, and the third set of mask cells are partially covered by a connected region formed by a set of overlapping rules,
a plurality of programmable processing units to assign a first rule to a first data unit if the first set of mask cells comprise a first cell, which comprises flow identifiers of the first data unit and to send the first data unit and metadata values to the programmable control unit otherwise, wherein the metadata values identify the position of the first cell in the connected region, and
the programmable control unit to assign a second rule to the first data unit based on metadata values associated with the first cell.
2. The processor of claim 1, wherein the bitmap comprises a control bit
equaling a first value associated with the first set of cells and a control bit equaling
a second value associated with the second and the third set of cells.
3. The processor of claim 1, wherein the bitmap is generated based on a
flow identifiers layout comprising one or more covered regions formed by a
plurality of set of overlapping rules.
4. The processor of claim 3, wherein the flow identifiers layout comprise a
plurality of cells each representing a sub-range of the flow identifiers, wherein the
plurality of cells together represent a range of flow identifiers of the flow identifiers layout.
5. The processor of claim 4, wherein each of the plurality of cells represent
a set of a source flow identifiers and a set of destination flow identifiers.
6. The processor of claim 1, wherein the first rule is a rule of highest
priority among the rules that are associated with the first cell.
7. The processor of claim 1, wherein the plurality of programmable
processing units,
extract the flow identifiers of the first data unit,
assign the first rule associated with the first cell if the control bit associated with the first cell, comprising the flow identifiers of the first data unit, equals the first value,
generate the metadata value based on a position of the position of the first cell within the covered region, and
send the first data unit and the metadata to the programmable control unit.
8. The processor of claim 7, wherein the metadata value comprises an
identifier of the connected region comprising the first cell and a horizontal and
vertical projection of the partially covered portion of the first cell, wherein the
horizontal projection and the vertical projection, respectively, represent the
projection of the start vertex of the second cell on the horizontal axis of the flow
identifiers layout and the projection of the bottom vertex of the first cell on the
vertical axis of the flow identifiers layout.
9. The processor of claim 1, wherein the programmable control unit
identifies the second rule associated with the position of the first cell, wherein the
position of the first cell is identified based on the horizontal and the vertical projection.
10. The processor of claim 9, wherein the horizontal projection of the start
vertex represents a lower bound source flow identifier of the sub-range of the flow
identifiers of the first cell and the vertical projection of the bottom vertex
represents a lower bound destination flow identifier of the sub-range of the flow
identifiers of the first cell.
11. A method of processing data units comprising
generating a bitmap comprising a first set of mask cells and a second set and a third set of mask cells, wherein the first set of mask cells are completely covered by a first highest priority rule, the second set of mask cells are partially covered by a second highest priority rule, and the third set of mask cells are partially covered by a connected region formed by a set of overlapping rules,
assigning a first rule to a first data unit if the first set of mask cells comprise a first cell, which comprises flow identifiers of the first data unit and to send the first data unit and metadata values to the programmable control unit otherwise, wherein the metadata values identify the position of the first cell in the connected region, and
assigning a second rule to the first data unit based on metadata values associated with the first cell.
12. The method of claim 11, wherein the bitmap comprises a control bit
equaling a first value associated with the first set of cells and a control bit equaling
a second value associated with the second and the third set of cells.
13. The method of claim 11, wherein the bitmap is generated based on a
flow identifiers layout comprising one or more covered regions formed by a
plurality of set of overlapping rules.
14. The method of claim 13, wherein the flow identifiers layout comprise a
plurality of cells each representing a sub-range of the flow identifiers, wherein the
plurality of cells together represent a range of flow identifiers of the flow identifiers
layout.
15. The method of claim 14, wherein each of the plurality of cells represent
a set of a source flow identifiers and a set of destination flow identifiers.
16. The method of claim 11, wherein the first rule is a rule of highest
priority among the rules that are associated with the first cell.
17. The method of claim 11 comprises,
extracting the flow identifiers of the first data unit,
assigning the first rule associated with the first cell if the control bit associated with the first cell, comprising the flow identifiers of the first data unit, equals the first value,
generating the metadata value based on a position of the position of the first cell within the connected region, and
sending the first data unit and the metadata to the programmable control unit.
18. The method of claim 17, wherein the metadata value comprises an
identifier of the connected region comprising the first cell and a horizontal and
vertical projection of the partially covered portion of the first cell, wherein the
horizontal projection and the vertical projection, respectively, represent the
projection of the start vertex of the second cell on the horizontal axis of the flow
identifiers layout and the projection of the bottom vertex of the first cell on the vertical axis of the flow identifiers layout.
19. The method of claim 11 comprises identifying the second rule
associated with the position of the first cell, wherein the position of the first cell is
identified based on the horizontal and the vertical projection.
20. The method of claim 19, wherein the horizontal projection of the start
vertex represents a lower bound source flow identifier of the sub-range of the flow
identifiers of the first cell and the vertical projection of the bottom vertex
represents a lower bound destination flow identifier of the sub-range of the flow
identifiers of the first cell.
21. A machine-readable medium comprising a plurality of instructions that
in response to being executed result in a processor
to generate a bitmap comprising a first set of mask cells and a second set and a third set of mask cells, wherein the first set of mask cells are completely covered by a first highest priority rule, the second set of mask cells are partially covered by a second highest priority rule, and the third set of mask cells are partially covered by a connected region formed by a set of overlapping rules,
to assign a first rule to a first data unit if the first set of mask cells comprise a first cell, which comprises flow identifiers of the first data unit and to send the first data unit and metadata values to the programmable control unit otherwise, wherein the metadata values identify the position of the first cell in the connected region, and
to assign a second rule to the first data unit based on metadata values associated with the first cell.
22. The machine-readable medium of claim 21, wherein the bitmap
comprises a control bit equaling a first value associated with the first set of cells
and a control bit equaling a second value associated with the second and the third
set of cells.
23. The machine-readable medium of claim 21, wherein the bitmap is
generated based on a flow identifiers layout comprising one or more covered
regions formed by a plurality of set of overlapping rules.
24. The machine-readable medium of claim 23, wherein the flow identifiers
layout comprise a plurality of cells each representing a sub-range of the flow
identifiers, wherein the plurality of cells together represent a range of flow
identifiers of the flow identifiers layout.
25. The machine-readable medium of claim 24, wherein each of the
plurality of cells represent a set of a source flow identifiers and a set of destination
flow identifiers.
26. The machine-readable medium of claim 21, wherein assigning the rule
comprises,
extracting the flow identifiers of the first data unit,
assigning the first rule associated with the first cell if the control bit associated with the first cell, comprising the flow identifiers of the first data unit, equals the first value,
generating the metadata value based on a position of the position of the first cell within the connected region, and
sending the first data unit and the metadata to the programmable control unit.
27. The machine-readable medium of claim 21, wherein assigning the rule
comprises identifying the second rule associated with the position of the first cell,
wherein the position of the first cell is identified based on the horizontal and the
vertical projection.
28. A network device comprising
a network interface to transfer data units,
a memory to store a bitmap, and
a processor to generate a bitmap comprising a first set of mask cells and a second set and a third set of mask cells, wherein the first set of mask cells are completely covered by a first highest priority rule, the second set of mask cells are partially covered by a second highest priority rule, and the third set of mask cells are partially covered by a connected region formed by a set of overlapping rules, to assign a first rule to a first data unit, in a first path, if the first set of mask cells comprise a first cell, which comprises flow identifiers of the first data unit and to send the first data unit and metadata values to a second path otherwise, wherein the metadata values identify the position of the first cell in the connected region, and to assign a second rule to the first data unit based on metadata values associated with the first cell.
29. The network device of claim 28 is a router.
30. The network device of claim 29, wherein the router supports a firewall
application, which determines the rule that is to be assigned to the data unit.