Patent Publication Number: US-11398979-B2

Title: Dynamic processing trees

Description:
FIELD OF THE INVENTION 
     The present invention is related generally to communication over computer networks, and specifically to the processing of communication packets. 
     BACKGROUND 
     A network interface controller (NIC) is a unit that manages communication between a computer (e.g., a server) and a computer network, such as a local area network (LAN) or switch fabric. A NIC directs packets from the network to their respective destinations in the computer, for example by placing a packet in a buffer of a destination application in a memory unit of the computer. The NIC further directs outgoing packets, for example by sending a packet to the network or to a loopback port. The directing of a packet to its destination, which is generally referred to as “steering,” includes ascertaining the destination of the packet and then forwarding the packet to its destination. 
     SUMMARY OF THE INVENTION 
     There is provided, in accordance with some embodiments of the present invention, a system including a memory and one or more processors configured to cooperatively carry out a process. The process includes receiving a plurality of rules for processing packets arriving at at least one packet-processing device, the rules being based on multiple parameters associated with the packets. The process further includes causing the packet-processing device to process multiple subsets of the packets using different respective sequences of packet-processing instructions, which are stored in the memory and implement the rules via different respective parameter-value-ascertaining orders for ascertaining respective values of the parameters for each of the packets. The process further includes, based on the processing of the subsets, computing respective scores for the sequences of packet-processing instructions. The process further includes, based on the scores, selecting one of the sequences of packet-processing instructions. The process further includes causing the packet-processing device to process the packets using the selected sequence of packet-processing instructions. 
     In some embodiments, the one or more processors include at least one Data Processing Unit (DPU) configured to carry out at least part of the process. 
     In some embodiments, at least one of the processors belongs to the packet-processing device. 
     In some embodiments, causing the packet-processing device to process the multiple subsets of the packets using the different respective sequences of packet-processing instructions includes iteratively performing a subprocess that includes, during each i th  iteration of the subprocess: 
     while the packet-processing device is using a first one of the sequences of packet-processing instructions S 1   i , writing a second one of the sequences of packet-processing instructions S 2   i  to the memory, and 
     subsequently to writing S 2   i  to the memory, causing the packet-processing device to use S 2   i  instead of S 1   i . 
     In some embodiments, the subprocess further includes, during each i th  iteration of the subprocess: 
     comparing the score for S 2   i  to the score for S 1   i , and 
     based on the comparing, selecting either S 1   i  or S 2   i  as the first one of the sequences of packet-processing instructions, S 1   i+1 , for a next iteration of the subprocess. 
     In some embodiments, causing the packet-processing device to process the multiple subsets of the packets using the different respective sequences of packet-processing instructions includes causing the packet-processing device to process the multiple subsets of the packets using the different respective sequences of packet-processing instructions by: 
     initializing a batch of N of the parameter-value-ascertaining orders, and 
     iteratively:
         causing the packet-processing device to use N of the sequences of packet-processing instructions that implement the rules via the N parameter-value-ascertaining orders in the batch, respectively,   based on the respective scores for the N sequences of packet-processing instructions, removing, from the batch, all but T of the N parameter-value-ascertaining orders,   deriving N-T of the parameter-value-ascertaining orders from the T parameter-value-ascertaining orders remaining in the batch, and   adding the derived parameter-value-ascertaining orders to the batch.       

     In some embodiments, deriving the N-T parameter-value-ascertaining orders includes deriving at least one of the N-T parameter-value-ascertaining orders by combining part of a first one of the T parameter-value-ascertaining orders with another part of a second one of the T parameter-value-ascertaining orders. 
     In some embodiments, deriving the N-T parameter-value-ascertaining orders includes deriving at least one of the N-T parameter-value-ascertaining orders by swapping respective positions of two of the parameters in one of the T parameter-value-ascertaining orders. 
     In some embodiments, the score for each of the sequences of packet-processing instructions is based on a number of the packets processed per unit time using the sequence. 
     In some embodiments, the score for each of the sequences of packet-processing instructions is based on an average number, per packet, of lookups in the sequence when using the sequence. 
     In some embodiments, the score for each of the sequences of packet-processing instructions is based on an average number, per packet, of cache hits or cache misses when using the sequence. 
     In some embodiments, the score for each of the sequences of packet-processing instructions is based on a number of memory entries that store the sequence. 
     There is further provided, in accordance with some embodiments of the present invention, a method including receiving a plurality of rules for processing packets arriving at at least one packet-processing device, the rules being based on multiple parameters associated with the packets. The method further includes causing the packet-processing device to process multiple subsets of the packets using different respective sequences of packet-processing instructions, which implement the rules via different respective parameter-value-ascertaining orders for ascertaining respective values of the parameters for each of the packets. The method further includes, based on the processing of the subsets, computing respective scores for the sequences of packet-processing instructions. The method further includes, based on the scores, selecting one of the sequences of packet-processing instructions. The method further includes causing the packet-processing device to process the packets using the selected sequence of packet-processing instructions. 
     The present invention will be more fully understood from the following detailed description of embodiments thereof, taken together with the drawings, in which: 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a schematic illustration of a computer system, in accordance with some embodiments of the present invention; 
         FIG. 2  is a schematic illustration of two different sequences of packet-processing instructions, in accordance with some embodiments of the present invention; 
         FIGS. 3-4  are flow diagrams for example algorithms for finding an optimal sequence of packet-processing instructions, in accordance with some embodiments of the present invention; 
         FIG. 5  is a flow diagram for an example algorithm for computing parameter-value-ascertaining orders, in accordance with some embodiments of the present invention; and 
         FIG. 6  is a flow diagram for an example algorithm for deriving a parameter-value-ascertaining order, in accordance with some embodiments of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
     Overview 
     A packet-processing device, such as a NIC, processes packets in accordance with rules that are based on parameters associated with the packets. For example, the rules may include specific instructions for modifying and/or forwarding a packet in the event that the header of the packet includes a specific source or destination address. 
     When implementing rules based on a small number of parameters, the parameter-value-ascertaining order in which the device ascertains the values of the parameters may be relatively unimportant. However, when implementing rules based on a larger number of parameters, the rate at which the packets are processed, the amount of memory consumption, and/or other factors may depend substantially on the parameter-value-ascertaining order, such that choosing a suboptimal parameter-value-ascertaining order may compromise the performance of the device. 
     To address this challenge, embodiments of the present invention cause the packet-processing device to try various parameter-value-ascertaining orders. For each parameter-value-ascertaining order, a score, which is based on metrics such as the number of packets processed per unit time, is computed. The parameter-value-ascertaining order having the highest score is then selected for use in future processing. 
     In many cases, the number of parameters is too large to allow trying every possible parameter-value-ascertaining order. For example, a typical set of rules may be based on 20 parameters, and hence may be implemented via 20! different parameter-value-ascertaining orders. Embodiments of the present invention therefore provide an efficient trial technique that allows the top-scoring parameter-value-ascertaining orders to “evolve” via score-boosting changes. Upon convergence of the highest score, the trial is terminated. 
     In the context of the present application, including the claims, the processing of a packet may include any suitable operation, including modifying, steering, or dropping the packet. 
     System Description 
     Reference is initially made to  FIG. 1 , which is a schematic illustration of a computer system  20 , in accordance with some embodiments of the present invention. 
     System  20  comprises a computer  34 , comprising a processor  38  and a memory  36 , comprising, for example, a random access memory (RAM). Processor  38  is configured to execute multiple processes on computer  34 . In some embodiments, these processes are executed on a plurality of virtual machines (VMs)  42 , which are managed by a hypervisor  40  or other virtualization software. Alternatively or additionally, the processes may be executed on multiple cores belonging to processor  38 . 
     System  20  further comprises a packet-processing device  22 , configured to process incoming packets, e.g., by steering these packets to computer  34 , and/or to process outgoing packets, e.g., by steering these packets from computer  34 . Packet-processing device  22  may be connected to computer  34  over any suitable communication interface  44 , such as a Peripheral Component Interconnect (PCI). In some embodiments, packet-processing device  22  comprises a network interface controller (NIC), comprising, for example, an InfiniBand host channel adapter (HCA) or a host bus adapter (HBA). Alternatively, packet-processing device  22  may comprise a network switch. Alternatively, the packet-processing device may comprise any computer configured to process packets by executing suitable software instructions. 
     Packet-processing device  22  comprises ports  24 , which may comprise, for example, at least one InfiniBand port, Ethernet port, and/or loopback port. Packet-processing device  22  further comprises a queue  26 , configured to store incoming packets received at ports  24  and/or outgoing packets destined for ports  24 . A processor  28  of the packet-processing device retrieves incoming packets from, and stores outgoing packets in, queue  26 . 
     Packet-processing device  22  further comprises a memory  30 , comprising, for example, a RAM. In some embodiments, memory  30  is configured to store one or more sequences  32  of packet-processing instructions, which may implement the same set of packet-processing rules in different ways, as further described below with reference to  FIG. 2 . 
     Subsequently to retrieving an incoming packet from the queue, processor  28  processes the packet in accordance with the packet-processing rules implemented by sequences  32 . Thus, for example, by following the instructions contained in one of the sequences, the processor may ascertain that the packet is destined for a particular process running on computer  34 , and then store the packet (typically via direct memory access (DMA) over communication interface  44 ) in a buffer in memory  36  used by the process. Similarly, based on one of sequences  32 , the processor may steer each outgoing packet (via queue  26 ) to the appropriate port  24 , such that the packet is communicated to its destination. 
     Typically, for embodiments in which multiple sequences of packet-processing instructions are stored simultaneously in memory  30 , memory  30  further stores a pointer  33 , which points to the first (or “root”) memory entry in the sequence that is currently in use. 
     In other embodiments, sequences  32  (and, typically, pointer  33 ) are stored in memory  36 , rather than memory  30 . In such embodiments, processor  28  typically accesses sequences  32  via DMA over communication interface  44 . The sequences may be stored in memory  36  by processor  38  (e.g., by hypervisor  40 ) or by processor  28 , typically via DMA over communication interface  44 . 
     Typically, packet-processing device  22  further comprises a cache memory (not shown), configured to store packet-processing instructions from sequences  32 . When attempting to read any particular packet-processing instruction, processor  28  first checks whether the instruction is stored in the cache. If yes—i.e., if the processor experiences a cache hit—the processor reads the instruction from the cache. Otherwise—i.e., if the processor experiences a cache miss—the processor reads the instruction from memory  30  or memory  36 . 
     The Sequences of Packet-Processing Instructions 
     For further details regarding sequences  32 , reference is now additionally made to  FIG. 2 , which is a schematic illustration of two different sequences of packet-processing instructions, in accordance with some embodiments of the present invention. 
     As noted above, each sequence  32  contains instructions for steering and/or otherwise processing packets arriving at packet-processing device  22 . The instructions are based on multiple parameters associated with the packets, such that two packets that differ from one another with respect to at least one of the parameters may be processed differently from one another. The parameters may include one or more fields contained in the headers of the packets, such as a layer-2, layer-3, or layer-4 source address or destination address (e.g., a source or destination Internet Protocol (IP) or media access control (MAC) address), or a Virtual Extensible Local Area Network (VXLAN) network identifier (VNI). Alternatively or additionally, the parameters may include one or more properties, such as the size, of the packets. Alternatively or additionally, one or more of the parameters may describe the manner in which the packets are communicated, such that, for example, packets received at different respective ports  24  are processed differently from one another. 
     Although multiple sequences  32  may implement the same rules, the sequences may differ from each other with respect to the parameter-value-ascertaining order in which the parameters are processed for each of the packets. 
     By way of illustration,  FIG. 2  shows two decision trees  46 , which implement a hypothetical set of rules in accordance with different respective parameter-value-ascertaining orders. In particular: 
     (i) Per a first decision tree  46   a , processor  28  ascertains the value of a first parameter P 1  before ascertaining the value of a second parameter P 2 . The parameter-value-ascertaining order implemented by first decision tree  46   a  may thus be written as {P 1 , P 2 , . . . }. 
     First decision tree  46   a  corresponds to a first sequence  32   a  of packet-processing instructions. When using first sequence  32   a  to process any given packet, processor  28  first ascertains the value of P 1  for the packet, per the root entry in first sequence  32   a . Subsequently, the processor looks up, in first sequence  32   a , another memory entry  48  corresponding to the value of P 1 . ( FIG. 2  shows entry  48  for a first value, or range or group of values, P 1   1 .) Subsequently, the processor executes any processing instructions  50 , such as instructions for modifying or forwarding the packet, stored in entry  48 . Next, the processor reads, from the entry, lookup instructions  51 , which include the address of a subsequent entry  52  corresponding to the value of P 2  for the packet. The processor then looks up the subsequent entry. ( FIG. 2  shows entry  52  for each of the values, or ranges or groups of values, P 2   1 , P 2   2 , and P 2   3 .) In this manner, the processor traverses the memory entries in sequence  32   a.    
     (ii) Per a second decision tree  46   b , the processor ascertains the value of P 2  before doing so for P 1 . The parameter-value-ascertaining order implemented by second decision tree  46   b  may thus be written as {P 2 , P 1 , . . . }. 
     Second decision tree  46   b  corresponds to a second sequence  32   b  of packet-processing instructions. When using second sequence  32   b  to process any given packet, processor  28  first ascertains the value of P 2  for the packet, per the root entry in second sequence  32   b . Subsequently, the processor looks up, in second sequence  32   b , the memory entry corresponding to the value of P 2 . ( FIG. 2  shows this entry for P 2   1 .) Subsequently, after executing any processing instructions  50  stored in the entry, the processor reads, from lookup instructions  51  of the entry, the address of the subsequent memory entry corresponding to the value of P 1  for the packet, and then looks up the subsequent entry. In this manner, the processor traverses sequence  32   b.    
     Sequences having different respective parameter-value-ascertaining orders may have different respective numbers of memory entries, and hence, may occupy different respective amounts of memory. For example, the portion of first decision tree  46   a  shown in  FIG. 2  corresponds to 16 memory entries in first sequence  32   a  (in addition to the root entry): four entries corresponding, respectively, to the four possible values (or ranges or sets of values) P 1   1 , P 1   2 , P 1   3 , and P 1   4  of P 1 , and another twelve entries for P 2 , including four entries corresponding to P 2   1 , four entries corresponding to P 2   2 , four entries corresponding to P 2   3 , and four entries corresponding to P 2   4 . On the other hand, the portion of second decision tree  46   b  shown in  FIG. 2  corresponds to only 15 memory entries in second sequence  32   b : three entries corresponding, respectively, to P 2   1 , P 2   2 , and P 2   3 , and another twelve entries for P 1 . 
     Moreover, by virtue of the different parameter-value-ascertaining orders, one sequence may facilitate faster and/or more effective processing than another sequence. 
     Hence, embodiments of the present invention provide techniques for causing the packet-processing device to process multiple subsets of packets using different respective sequences of instructions, which implement the rules via different respective parameter-value-ascertaining orders. Based on the processing of the subsets, respective scores are computed for the sequences of instructions, the score for each sequence being based on, for example, the number of memory entries that store the sequence and/or a normalized number of packets processed per unit time using the sequence. Based on the scores, one of the sequences of instructions (typically, the sequence having the highest score) is identified as the optimal sequence, and is therefore selected for future use. 
     In some embodiments, these techniques are performed by processor  38  (e.g., by hypervisor  40 ), typically by executing software. In particular, for each parameter-value-ascertaining order that is to be used, processor  38  writes, to memory  36 , the sequence of instructions implementing the rules in accordance with the parameter-value-ascertaining order. Processor  38  further modifies pointer  33  so as to cause the packet-processing device to use each new sequence of instructions written to the memory. 
     In other embodiments, these techniques are performed by processor  28 , typically by executing firmware. In particular, for each parameter-value-ascertaining order that is to be used, processor  28  writes, to memory  30  or memory  36 , the sequence of instructions implementing the rules in accordance with the parameter-value-ascertaining order, and modifies pointer  33  accordingly. 
     In yet other embodiments, these techniques are performed cooperatively by processor  28  and processor  38 . For example, for each parameter-value-ascertaining order, processor  38  may write a decision tree  46  implementing the order to memory  36 . Subsequently, processor  28  may read the decision tree from memory  36 , and then write, to memory  30  or memory  36 , the sequence of instructions corresponding to the decision tree. 
     (It is noted that a node in the decision tree may correspond to a set of multiple parameters, such that edges diverging from the node may correspond to different respective sets of parameter values. For example, one edge may correspond to the set of values {P 1   2 , P 1 }, while another edge may correspond to {P 1   1 , P 2   2 }. In contrast, each memory entry generally corresponds to a single parameter value.) 
     In some embodiments, system  20  comprises multiple packet-processing devices configured to use, simultaneously, different respective sequences of instructions implementing the same packet-processing rules. Advantageously, such embodiments may facilitate a faster identification of an optimal sequence of packet-processing instructions. 
     In such embodiments, the respective processors of the packet-processing devices may be cooperatively networked, such that the processors cooperatively perform the techniques described herein. Thus, for example, the processors may cooperatively compute multiple parameter-value-ascertaining orders and assign a different respective subset of the parameter-value-ascertaining orders to each of the processors, such that each processor writes to memory, and uses, a different respective group of sequences of packet-processing instructions. 
     Alternatively, in such embodiments, the computation of the parameter-value-ascertaining orders, the assignment of the parameter-value-ascertaining orders to the processors of the packet-processing devices, and, optionally, the writing of the sequences of packet-processing instructions to memory may be performed by processor  38  or by multiple, cooperatively-networked processors of different respective computers  34 . In the latter case, each packet-processing device may be connected to a different respective computer  34 . The cooperatively-networked processors may use the Message Passing Interface (MPI), or any other suitable communication protocol, to communicate with each other. 
     In some embodiments, the functionality of processor  38 , as described herein, is implemented solely in hardware, e.g., using one or more fixed-function or general-purpose integrated circuits, Application-Specific Integrated Circuits (ASICs), and/or Field-Programmable Gate Arrays (FPGAs). Typically, however, the functionality of processor  38  is implemented at least partly in software. For example, in some embodiments, processor  38  is embodied as a programmed processor comprising, for example, a central processing unit (CPU) and/or at least one other unit such as a Graphics Processing Unit (GPU) (e.g., an integrated GPU (iGPU)), a Data Processing Unit (DPU), or an Ethernet network adapter card. Program code, including software programs, and/or data may be loaded for execution and processing by the CPU and/or any of the other units listed above. The program code and/or data may be downloaded to the processor in electronic form, over a network, for example. Alternatively or additionally, the program code and/or data may be provided and/or stored on non-transitory tangible media, such as magnetic, optical, or electronic memory. Such program code and/or data, when provided to the processor, produce a machine or special-purpose computer, configured to perform the tasks described herein. 
     In some embodiments, the functionality of processor  28 , as described herein, is implemented solely in hardware, e.g., using one or more fixed-function or general-purpose integrated circuits, ASICs, and/or FPGAs. Typically, however, the functionality of processor  28  is implemented at least partly in firmware and/or higher-level software. For example, in some embodiments, processor  28  is embodied as a programmed processor comprising, for example, a CPU and/or at least one other unit such as a GPU (e.g., an iGPU) or a DPU. Program code, including software programs, and/or data are loaded for execution and processing by the CPU and/or any of the other units listed above. The program code and/or data may be downloaded to the processor in electronic form, over a network, for example. Alternatively or additionally, the program code and/or data may be provided and/or stored on non-transitory tangible media, such as magnetic, optical, or electronic memory. Such program code and/or data, when provided to the processor, produce a machine or special-purpose computer, configured to perform the tasks described herein. 
     Finding the Optimal Sequence of Packet-Processing Instructions 
     Reference is now made to  FIG. 3 , which is a flow diagram for an example algorithm  54  for finding an optimal sequence of packet-processing instructions, in accordance with some embodiments of the present invention. As described above with reference to  FIGS. 1-2 , algorithm  54  may be executed by processor  28  and/or processor  38 , referred to below simply as “the processor.” 
     Algorithm  54  begins with a rule-receiving step  56 , at which the processor receives a plurality of rules for processing packets arriving at the packet-processing device. The rules may be received directly from a user (e.g., a network administrator) via a suitable user interface, or loaded from a storage device, such as a hard drive or flash drive. 
     Subsequently to receiving the rules, the processor begins an iterative process. During each i th  iteration of the process, the processor, at a writing step  58 , writes a new sequence of instructions S 2   i  to memory  30  or memory  36  ( FIG. 1 ) while the packet-processing device is using the current sequence S 1   i . (S 2   i  differs from S 1   i  by virtue of implementing the rules via a different parameter-value-ascertaining order.) Subsequently to writing S 2   i  to the memory, the processor causes the packet-processing device to use S 2   i  instead of S 1   i  (i.e., the processor makes S 2   i  the current sequence), typically by setting pointer  33  ( FIG. 1 ) to (the root of) S 2   i  at a pointer-setting step  60 . 
     While the packet-processing device uses S 2   i , the processor collects data relating to the processing, e.g., by counting the number of processed packets and/or the number of lookups in the sequence of instructions. The processor also continually checks, at a first checking step  64 , whether sufficient data have been obtained for S 2   i . For example, the processor may ascertain whether S 2   i  has been used for at least a predefined threshold amount of time, and/or whether a predefined threshold number of packets have been processed using S 2   i . 
     Upon ascertaining that sufficient data have been obtained, the processor, at a metric-computing step  66 , computes one or more metrics for S 2   i . Typically, the metrics include one or more of: 
     (i) a metric based on a number of packets processed per unit time (e.g., per second) using the sequence, such as the metrics R/R MAX  and T/T MAX  defined below; 
     (ii) an average number, per packet, of lookups in the sequence when using the sequence; 
     (iii) an average number, per packet, of cache hits or cache misses when using the sequence; and 
     (iv) a metric based on a number of entries that store the sequence, such as the ratio Q defined below. (It is noted that this metric may be calculated even before sufficient data are obtained, such as during or immediately subsequently to the writing of the sequence of instructions.) 
     Subsequently to computing the metrics, the processor, at a score-computing step  68 , computes a score based on the metrics. For example, the score may equal (R/R MAX ×T/T MAX )/(L R ×L T ×C×Q), where: 
     (a) R is the number of received (incoming) packets processed per unit time; 
     (b) R MAX  is the hypothetical maximum number of received packets that may be processed per unit time, which may be computed based on the clock rate of the processor; 
     (c) T is the number of transmitted (outgoing) packets processed per unit time; 
     (d) T MAX  is the hypothetical maximum number of transmitted packets that may be processed per unit time, which may be computed as described above for R MAX ; 
     (e) L R  is the average number of lookups (or “hops”) per received packet; 
     (f) L T  is the average number of lookups per transmitted packet; 
     (g) C is the average number of cache misses per packet; and 
     (h) Q is the ratio of the number of memory entries storing the sequence of instructions to the number of nodes in the corresponding decision tree. (Normalizing the number of memory entries by the number of nodes facilitates comparing two sequences of packet-processing instructions to one another in the event that the packet-processing rules were modified after using the first sequence but before using the second sequence.) 
     Alternatively, the score may combine the metrics in any other suitable way, assigning any suitable weight to each metric. For embodiments in which a single metric (such as Q) is computed, the score may equal the metric. 
     Typically, the score is defined such that a higher score is indicative of better performance, and hence, the optimal sequence of instructions has the highest score, as in the case of the example above and as assumed below. Alternatively, the opposite convention may be used, such that the optimal sequence of instructions has the lowest score. For example, the score may equal (L R ×L T ×C×Q)/(R/R MAX ×T/T MAX ), which is the inverse of the expression above. 
     Subsequently to computing the score, the processor, at a score-comparing step  70 , compares the score for S 2   i  with the score for S 1   i  (the previous sequence of instructions). If the score for S 1   i  exceeds the score for S 2   i , the processor causes the packet-processing device to use S 1   i  again, typically by setting the pointer to S 1   i  at a pointer-reverting step  72 . The processor thus selects S 1   i  as S 1   i+1  for the next iteration of the process, i.e., the processor lets S 1   i+1 =S 1   i . Otherwise, the processor allows the packet-processing device to continue using S 2   i  thus effectively selecting S 2   i  as S 1   i+1  for the next iteration. 
     Subsequently to selecting one of the sequences, the processor, at a memory-freeing step  73 , frees the portion of the memory storing the lower-scoring (and hence unselected) sequence. In other words, if S 1   i+1 =S 1   i , the processor frees the portion of the memory storing S 2   i ; otherwise, the processor frees the portion of the memory storing S 1   i . 
     Next, the processor checks, at a second checking step  74 , whether any more sequences of instructions should be tried. For example, as further described below with reference to  FIG. 5 , each sequence of instructions written to the memory at writing step  58  may implement the rules via a different respective parameter-value-ascertaining order computed by another algorithm running in parallel to algorithm  54 . The processor may therefore check, at second checking step  74 , whether the other algorithm has provided any more parameter-value-ascertaining orders. 
     If the processor ascertains that at least one more sequence of instructions should be tried, the processor returns to writing step  58 , thus beginning the next iteration of the iterative process. Otherwise, algorithm  54  ends, with the packet-processing device using the optimal sequence of packet-processing instructions. (It is noted that this sequence is “optimal” only relative to the other sequences of instructions that were tried; another sequence of instructions, with an even higher score, may not have been tried.) 
     It is noted that during most of the performance of algorithm  54 , the memory stores two sequences of instructions: the sequence currently in use, and the current optimal sequence. 
     Reference is now made to  FIG. 4 , which is a flow diagram for another example algorithm  62  for finding an optimal sequence of packet-processing instructions, in accordance with some embodiments of the present invention. Algorithm  62  may be executed alternatively to algorithm  54  ( FIG. 3 ). During most of the performance of algorithm  62 , the memory stores three sequences of packet-processing instructions: the sequence currently in use, the current optimal sequence S O , and the upcoming sequence. 
     Per algorithm  62 , following the receipt of the rules at rule-receiving step  56 , the processor performs writing step  58 , thus writing a first sequence of instructions to memory. Subsequently, the processor causes the packet-processing device to use the first sequence by performing pointer-setting step  60 . 
     Subsequently, the processor begins an iterative process. Similarly to algorithm  54 , during each i th  iteration of the process, the processor, at writing step  58 , writes a new sequence S 2   i  of instructions to memory while the packet-processing device is using the current sequence S 1   i . However, in the case of algorithm  62 , S 2   i  is written to memory before the score is computed for S 1   i . Subsequently to computing the score for S 1   i , the processor performs memory-freeing step  73 . In particular, if the score for S 1   i  does not exceed that of S O , the processor frees the portion of the memory storing S 1   i ; otherwise, the processor frees the portion of the memory storing S O , and S 1   i  is designated as the new optimal sequence S O . 
     Subsequently, the processor checks, at a third checking step  78 , whether the current sequence of instructions is the last sequence to be tried. If yes, the algorithm ends, with the packet-processing device using S O . Otherwise, the processor causes the packet-processing device to use S 2   i , typically by setting the pointer to S 2   i  at pointer-setting step  60 . (In other words, S 1   i+1  is set to S 2   i ) The processor then performs second checking step  74 . If at least one more sequence of instructions is to be tried, the processor returns to writing step  58 , thus beginning the next iteration of the iterative process. Otherwise, the processor returns to first checking step  64 . 
     Optionally, in the event that queue  26  ( FIG. 1 ) contains a large number of packets at the end of an iteration (due to poor performance of the current sequence), the processor may cause the packet-processing device to use S 0  to clear the backlog in the queue, prior to the packet-processing device using the newest sequence of instructions. 
     In general, the processor is configured to modify each sequence of instructions stored in memory so as to implement any changes to the rules that occur while algorithm  54 , algorithm  62 , or any other trial algorithm for finding an optimal sequence of instructions is being executed. For example, in the case of algorithm  54 , each of S 1   i  and S 2   i  is modified. In the case of algorithm  62 , each of S 1   i , S 2   i , and S O  is modified. 
     In some embodiments, as the processor performs writing step  58 , the processor counts the number of entries written to memory. If the number of entries exceeds a threshold, such as a number that is 5%-15% greater than (i) the number of memory entries in the previous sequence of instructions that was tried, or (ii) the smallest number of memory entries in any sequence of instructions tried thus far, the processor aborts the writing, and instead writes another sequence of instructions to memory. 
     In general, a trial algorithm for finding an optimal sequence of instructions, such as algorithm  54  or algorithm  62 , may be executed at any suitable intervals. For example, the algorithm may be executed periodically, e.g., once per day. Alternatively or additionally, the algorithm may be executed in response to accumulated changes in the rules for processing the packets. For example, the processor may count the number of rules that have been added, removed, or modified since the last execution of the algorithm. In response to this count exceeding a predefined threshold, the processor may execute the algorithm. Alternatively or additionally, while using the optimal sequence, the processor may continue to track the score. In response to a deterioration in the score that passes a predefined threshold, the processor may execute the algorithm. 
     Computing the Parameter-Value-Ascertaining Orders 
     The various sequences of packet-processing instructions written to memory at writing step  58  differ from each other by virtue of implementing the packet-processing rules via different respective parameter-value-ascertaining orders. In general, any suitable algorithm may be used to compute these parameter-value-ascertaining orders. A flow diagram of one such example algorithm  80  is shown in  FIG. 5 , to which reference is now made. Algorithm  80  may be executed by the processor in parallel to algorithm  54  ( FIG. 3 ), algorithm  62  ( FIG. 4 ), or any other trial algorithm. 
     Algorithm  80  begins at a batch-initializing step  82 , at which the processor initializes a batch of N parameter-value-ascertaining orders, N typically being between 5 and 25. Typically, one of the N parameter-value-ascertaining orders is the current optimal parameter-value-ascertaining order, and the processor computes each of the other parameter-value-ascertaining orders by randomly ordering the set of parameters on which the rules are based. 
     Subsequently to initializing the batch, the processor begins an iterative process. In each iteration of this process, the processor causes the packet-processing device to use N sequences of instructions that implement the rules via the N parameter-value-ascertaining orders in the batch, respectively. Subsequently, based on the respective scores for the N sequences of instructions, the processor removes, from the batch, all but T of the N parameter-value-ascertaining orders, T typically being between 0.1N and 0.3N. Next, the processor derives N-T parameter-value-ascertaining orders from the T parameter-value-ascertaining orders remaining in the batch, and then adds the derived parameter-value-ascertaining orders to the batch. 
     More specifically, to cause the packet-processing device to use the N sequences of instructions, the processor typically places the parameter-value-ascertaining orders in a queue at a placing step  84 . (To avoid any confusion, it is noted that this queue is different from queue  26  shown in  FIG. 1 .) Subsequently, each time a sequence of instructions is to be written to memory (e.g., each time that writing step  58  of  FIGS. 3-4  is performed), the processor retrieves the parameter-value-ascertaining order from the head of the queue, and then writes the sequence of instructions so as to implement the rules via the retrieved parameter-value-ascertaining order. 
     For example, referring again to  FIG. 2 , the processor may place the parameter-value-ascertaining orders {P 1 , P 2 , . . . } and {P 2 , P 1 , . . . } in the queue. Subsequently (e.g., during the performance of writing step  58 ), the processor may retrieve {P 1 , P 2 , . . . } from the queue, and then write first sequence  32   a  so as to implement the rules via this parameter-value-ascertaining order. The processor may then retrieve {P 2 , P 1 , . . . } from the queue, and write second sequence  32   b.    
     Following the trial of all N sequences of instructions, the processor receives the respective scores for the sequences at a score-receiving step  86 . Subsequently, based on the scores, the processor checks, at a fourth checking step  88 , whether any more parameter-value-ascertaining orders should be tried. If yes, the processor proceeds to a removing step  90 , as further described below. Otherwise, the algorithm ends. 
     For example, at fourth checking step  88 , the processor may check whether the highest received score has increased over the past k iterations by more than a predefined threshold. In other words, using the notation H i  to indicate the highest score received during the i th  iteration, the processor may check whether H i  differs from H i-k  by more than a predefined threshold. If not, the algorithm ends; otherwise, the processor proceeds to removing step  90 . 
     At removing step  90 , the processor removes the N-T lowest-scoring parameter-value-ascertaining orders from the batch. Subsequently, at a deriving step  92 , the processor derives N-T parameter-value-ascertaining orders from the T top-scoring parameter-value-ascertaining orders remaining in the batch, as further described below. Next, at a batch-filling step  94 , the processor adds the derived parameter-value-ascertaining orders to the batch. The processor then returns to placing step  84 , thus beginning the next iteration of the iterative process. 
     In alternate embodiments, the processor executes a single algorithm implementing the functionality of both algorithm  80  and the trial algorithm. 
     Deriving the N-T Parameter-Value-Ascertaining Orders 
     In some embodiments, at deriving step  92 , at least one of the N-T parameter-value-ascertaining orders is derived by combining part of one of the T parameter-value-ascertaining orders with part of another one of the T parameter-value-ascertaining orders. In this regard, reference is now made to  FIG. 6 , which is a flow diagram for an example algorithm  92   a  for deriving a parameter-value-ascertaining order, in accordance with some embodiments of the present invention. 
     Algorithm  92   a  begins with a selecting step  96 , at which the processor selects two of the T top-scoring parameter-value-ascertaining orders. Typically, the two parameter-value-ascertaining orders are selected at random. 
     Following the selection of the two parameter-value-ascertaining orders, the processor, at a part-selecting step  98 , selects part of each selected parameter-value-ascertaining order, typically such that the total number of parameters in the selected parts is equal to the total number of parameters in a single parameter-value-ascertaining order. For example, using M to denote the number of parameters, the processor may select a suborder of size M/2 (or (M±1)/2, if M is odd) from each of the parameter-value-ascertaining orders. For example, given a first selected parameter-value-ascertaining order {P 1 , P 2 , P 5 , P 3 , P 4 } and a second selected parameter-value-ascertaining order {P 2 , P 1 , P 4 , P 3 , P 5 }, the processor may select {P 1 , P 2 , P 5 } from the first selected parameter-value-ascertaining order and {P 3 , P 5 } from the second selected parameter-value-ascertaining order. 
     Next, at a combining step  100 , the processor combines the selected parts so as to compute a new parameter-value-ascertaining order. For example, continuing the example above, the processor may compute the parameter-value-ascertaining order {P 1 , P 2 , P 5 , P 3 , P 5 } by combining {P 1 , P 2 , P 5 } with {P 3 , P 5 }. 
     Subsequently, the processor, at a fifth checking step  102 , checks whether any parameters are missing from the new parameter-value-ascertaining order. If yes, the processor, at a substituting step  104 , substitutes the missing parameters for any repeated parameters. For example, continuing the example above, the processor may substitute P 4  for one of the instances of P 5  in the new parameter-value-ascertaining order, thus computing {P 1 , P 2 , P 4 , P 3 , P 5 } or {P 1 , P 2 , P 5 , P 3 , P 4 }. (The substituted instance of P 5  may be chosen at random.) Subsequently, or if no parameters are missing, algorithm  92   a  ends. 
     Alternatively or additionally to combining parts of parameter-value-ascertaining orders, at least one of the N-T parameter-value-ascertaining orders may be derived by swapping respective positions of two of the parameters in one of the T parameter-value-ascertaining orders. (The two parameters are typically chosen at random.) For example, the parameter-value-ascertaining order {P 1 , P 3 , P 5 , P 2 , P 4 } may be computed by swapping the respective positions of P 2  and P 3  in {P 1 , P 2 , P 5 , P 3 , P 4 }. 
     It will be appreciated by persons skilled in the art that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of embodiments of the present invention includes both combinations and subcombinations of the various features described hereinabove, as well as variations and modifications thereof that are not in the prior art, which would occur to persons skilled in the art upon reading the foregoing description. Documents incorporated by reference in the present patent application are to be considered an integral part of the application except that to the extent any terms are defined in these incorporated documents in a manner that conflicts with the definitions made explicitly or implicitly in the present specification, only the definitions in the present specification should be considered.