[go: up one dir, main page]

WO2009068822A2 - Procede et dispositif de tri de paquets - Google Patents

Procede et dispositif de tri de paquets Download PDF

Info

Publication number
WO2009068822A2
WO2009068822A2 PCT/FR2008/052046 FR2008052046W WO2009068822A2 WO 2009068822 A2 WO2009068822 A2 WO 2009068822A2 FR 2008052046 W FR2008052046 W FR 2008052046W WO 2009068822 A2 WO2009068822 A2 WO 2009068822A2
Authority
WO
WIPO (PCT)
Prior art keywords
packet
value
data
sorting
graph
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/FR2008/052046
Other languages
English (en)
Other versions
WO2009068822A3 (fr
Inventor
Denis Valois
Cédric LLORENS
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Orange SA
Original Assignee
France Telecom SA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by France Telecom SA filed Critical France Telecom SA
Priority to US12/741,860 priority Critical patent/US20100262684A1/en
Priority to CN200880116478A priority patent/CN101861722A/zh
Publication of WO2009068822A2 publication Critical patent/WO2009068822A2/fr
Publication of WO2009068822A3 publication Critical patent/WO2009068822A3/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/02—Network architectures or network communication protocols for network security for separating internal from external traffic, e.g. firewalls
    • H04L63/0227—Filtering policies
    • H04L63/0263—Rule management
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L69/00—Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass
    • H04L69/22—Parsing or analysis of headers
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/02—Network architectures or network communication protocols for network security for separating internal from external traffic, e.g. firewalls
    • H04L63/0227—Filtering policies
    • H04L63/0236—Filtering by address, protocol, port number or service, e.g. IP-address or URL

Definitions

  • the invention relates to the field of telecommunications networks and in particular to a method and a device for sorting packets.
  • sorting is used in this document in its broadest sense: the sorting of a set of packets corresponds to the fact of distributing a set of packets into several groups or categories. Sorting does not involve scheduling.
  • Certain telecommunication network equipment incorporating routers or firewall type modules, implement network access control functions by means of ordered lists of rules, called “access control list” (ACL) or checklist. access according to the English terminology.
  • ACL access control list
  • Each of the rules of such a list includes a description of the frames - called pattern -, in terms of possible values for the header fields of that frame, and an associated processing, for example "pass” or “throw”.
  • the values contained in the header fields of this frame are compared with the values defined by the patterns defined in the rules of the list in order to determine what is the treatment to be performed for this frame.
  • the number of rules of an ACL can be very high, of the order of several hundreds or even thousands of rules. It is therefore extremely expensive in computing time to compare the header fields of a frame with each of the rules of an ACL.
  • bit-by-bit processing of the frames assumes the use of operations to mask the bytes of the frames to be processed, in order to access the different bits of data to be analyzed.
  • the use of a binary decision tree assumes the implementation of a bit test function for each node of the tree, which complicates the writing of a software implementing the automaton corresponding.
  • the construction of such a tree is tedious and very memory consuming as soon as the number of rules in the list increases.
  • this solution requires specific hardware to try to minimize performance issues.
  • One of the aims of the invention is to remedy the shortcomings and drawbacks of the state of the art and / or to make improvements thereto.
  • the object of the invention is, according to a first aspect, a method of sorting data packets according to an ordered list of at least one sorting rule, comprising a determination step for each data packet. to deal with an associated package category,
  • a said sorting rule defining, on the one hand, a criterion relating to at least one data field present in the packets to be sorted and, on the other hand, a category of packet intended to be associated with a packet whose said at least one field of data contains a value satisfying the criterion
  • the category associated with a packet is identified by a sort value determined in a predetermined number NB of iterations from an initial sorting value and as a function of NB data blocks of the packet to be processed,
  • all of said NB data blocks including the data field or fields used for defining the rules of said list, the size of said data blocks being chosen from a set of several block sizes,
  • an iteration comprising a step of determining a current sort value from the sorting value obtained at the previous iteration and the value contained in the ith data block, the order in which said data blocks are considered to be predetermined.
  • the processing time of a packet is reduced to the processing time of these NB data blocks.
  • the time required to determine the action associated with a packet is independent of the content of this packet.
  • the size of the blocks used to process a packet can be selected from different sizes, including block sizes greater than or equal to 2 bits. This means that the number of iterations needed to process a packet can be reduced to one packet iteration by choosing a sufficiently large block size. In addition, when the block size chosen is 8, 16 or 24 bits, it becomes unnecessary to apply bit masking operations to proceed with the processing of a packet. The processing time of a packet is reduced compared to known prior solutions.
  • the invention thus teaches that it is possible to implement packet sorting by processing these block packets in block, with any block size and in a predetermined number of iterations, which is a function of the block size chosen. . She teaches a method of processing sorting rules to implement such a technique of sorting packets.
  • a current sort value is determined by reading, in a table identified by the sorting value obtained at the iteration previous, of the sort value associated with the value of the i th data block of the packet concerned.
  • the processing time of a data packet is therefore equal to NB times the reading time of a value in a table. It is reduced to a minimum.
  • the method according to the invention comprises a step of generating from said list of an acyclic directed graph at NB depth levels, said graph being representative of a state machine, a said sorting value identifying a state of said automaton, said initial sorting value identifying the initial state of said automaton, the transition table of a state of level p-1 of the automaton, where p is an integer such that l ⁇ p ⁇ NB, being a function between the set of possible values of the f th data block and the set of p-level state identifiers.
  • the ordered list of rules used to sort the packets is transformed into a unit representation, in the form of a graph at NB depth levels, regardless of the number of rules in the list.
  • This graph represents a state machine which is the one implemented for the automated processing of the packets to be filtered. This results in a high efficiency of packet processing, since even when the number of rules in the list is high, the depth of the graph is limited to NB levels.
  • the method according to the invention further comprises a step of constructing a list degenerate graph at NB depth levels from each of the rules of said list, said acyclic oriented graph being obtained by meeting the Degenerate graphs constructed, a degenerate graph in list representing a state machine and NB transitions.
  • the method according to the invention comprises in which said meeting is an iterative process, each iteration comprising a step of obtaining a current graph by meeting a degenerate graph in list with the graph obtained at a time. previous iteration and a step of minimizing said current graph.
  • the method according to the invention comprises comprising a step of translating the criterion of each sorting rule of said list into a list of NB sets of data block values, such that a packet of data satisfies this criterion if and only if for each integer p such that l ⁇ p ⁇ NB, the value contained in the p th block of data of this packet is included in the p th set of values, the p th set of values comprising the value or values which a transition between the condition th and p th state of the automaton represented by the graph degenerate list obtained from the rule concerned.
  • Each of the rules of the ordered list of rules is thus simply translated into a degenerate graph into a list, by identifying the different sets of values respectively associated with the blocks of data to be processed. This results in a possible automation of the process of generating the degenerate graphs in associated list.
  • the invention also relates to a device for sorting data packets according to an ordered list of at least one sorting rule, comprising determination means for each data packet to be processed of an associated packet category.
  • a said sorting rule defining, on the one hand, a criterion relating to at least one data field present in the packets to be sorted and, on the other hand, a category of packet intended to be associated with a packet whose said at least one field of data contains a value satisfying the criterion
  • said means being designed to determine a sort value identifying the category associated with a packet in a predetermined number NB of iterations from an initial sorting value and as a function of NB data blocks of the packet to be processed, all of said NB data blocks including the data field or fields used for defining the rules of said list, the size of said data blocks being chosen from a set of several block sizes,
  • an iteration comprising a step of determining a current sort value from the sorting value obtained at the previous iteration and the value contained in the ith data block, the order in which said data blocks are considered to be predetermined.
  • said means are designed to determine, during the ith iteration, where i is an integer between 1 and NB, a current sort value is determined by reading, in a table identified by the sorting value obtained. at the previous iteration, of the value of sorting) associated with the value of the ith data block of the packet concerned.
  • the various steps of the method according to the invention are implemented by software or computer program, this software comprising software instructions intended to be executed by a data processor of a packet sorting device. and designed to control the execution of the different steps of this process.
  • the invention is also directed to a program that can be executed by a computer or a data processor, which program includes instructions for controlling the execution of the steps of a method as mentioned above.
  • This program can use any programming language, and be in the form of source code, object code, or intermediate code between source code and object code, such as in a partially compiled form, or in any other form desirable shape.
  • a hardware or firmware implementation is also possible.
  • the invention also relates to a data carrier readable by a computer or data processor, and comprising instructions of a program as mentioned above.
  • the information carrier may be any entity or device capable of storing the program.
  • the medium may comprise a means of storage, such as a ROM, for example a CD ROM or a microelectronic circuit ROM, or a magnetic recording means, for example a floppy disk or a hard disk.
  • the information medium may be a transmissible medium such as an electrical or optical signal, which may be conveyed via an electrical or optical cable, by radio or by other means.
  • the program according to the invention can be downloaded in particular on an Internet type network.
  • the information carrier may be an integrated circuit in which the program is incorporated, the circuit being adapted to execute or to be used in the execution of the method in question.
  • FIG. 1 schematically represents a data packet to be filtered according to the method according to the invention
  • FIG. 2 is a flowchart of an embodiment of a first phase of the method according to the invention.
  • FIG. 3 is a flow chart of an embodiment of a second phase of the method according to the invention.
  • FIG. 4 represents a list degenerate graph obtained from a sorting rule
  • FIGS. 5A to 5F represent different graphs obtained from an ordered list of rules at different stages of processing during the implementation of the method according to the invention
  • FIG. 6 is a curve illustrating the performances of the method according to the invention.
  • FIG. 7 represents a graph obtained from an ordered list of rules.
  • the invention is described in more detail in the case of its application to the sorting of data packets in the form of IP frames.
  • the invention is however applicable to any other format of data packets and whatever the communication protocol used for the transmission of these packets.
  • the packet 100 of data comprises, in its header, various data fields in FIG. according to the values of which the sorting of the frames is carried out according to an ordered list of rules, forming access control list.
  • These data fields are as follows:
  • a first field 100A comprising a protocol identifier making it possible to identify a protocol from a list of possible protocols, this list comprising, for example, Transmission Control Protocol (TCP), User Datagram Protocol (UDP), Internet Protocol (IP); this field is coded on a byte identified by the reference 101;
  • TCP Transmission Control Protocol
  • UDP User Datagram Protocol
  • IP Internet Protocol
  • a second field 100B comprising a source address, identifying a device transmitting the packet; this field is coded on 4 bytes identified respectively by references 102, 103, 104 and 105;
  • a third field 100C comprising a destination address, identifying an equipment destination of the packet; this field is coded on 4 bytes identified respectively by references 106, 107, 108 and 109; a fourth field 100D comprising a source communication port identifier, relative to the equipment transmitting the packet; this field is coded on 2 bytes identified respectively by the references 1 10 and 1 1 1;
  • a fifth field 100E comprising a destination communication port identifier, relative to the destination equipment of the packet; this field is coded on 2 bytes identified respectively by the references 1 12 and 1 13.
  • the size in number of bits of these different fields is variable: usually the first data field is coded on 8 bits (ie one byte), the second and third fields are each coded on 32 bits (ie 4 bytes), while the fourth and fifth fields are coded on 16 bits (ie 2 bytes).
  • the size of these data fields does not matter, the method according to the invention processing the header of a block-by-block packet, for example byte-by-byte, using a block size of data possibly different, and therefore independent, from the size of the data fields used to interpret the values contained in these blocks. Indeed, the method according to the invention implements an automated processing of the values taken by these different fields, this treatment does not require interpretation of these values.
  • the order in which these data fields are stored in a packet may be different, and therefore independent, of the order in which these data fields are processed by the method according to the invention.
  • the different data blocks of the header of a packet will be processed in order in which they are recorded in this packet, so as to make linear, and therefore fast, the reading of these data blocks for processing.
  • ACL Access Control List
  • Each of the rules of such a list defines a criterion for at least one of the header fields of a packet and an associated action, which action is to be applied to the packet - or to the data stream to which this packet belongs - whose or the values of the data field or fields concerned satisfy this criterion.
  • a rule defines a category of packet to assign to a packet or stream that satisfies the criterion defined by that rule.
  • Permit tcp anygt 1023 10.2.3.4 eq 80 log means that the "permit-log" category (meaning that the flow is allowed to pass through the equipment implementing packet sorting) is assigned to any data flow using the protocol "tcp", from any source address ('any'), from a source port that is strictly greater than 1023 and sent to the address
  • the packet category to which a packet is assigned also depends on the semantics used as well as the order in which the rules of a list of rules are scanned and tested for that packet.
  • the order of the list of rules defines whether this list is traversed starting with the first rule (order called “top-down" in the English terminology) or by the last rule (called order
  • rule list is traversed rule by rule until the processed packet checks the criterion defined by the current rule; we say in this case that we apply a so-called "first match” semantics according to the English terminology, in that it is the first rule for which there is verification of the criterion which defines the category to which this packet is affected;
  • the process according to the invention comprises two phases.
  • the first phase is the generation, from an ordered list of rules, of data representative of an acyclic oriented graph (DAG), modeling a finite state automaton (DFA).
  • DAG acyclic oriented graph
  • DFA finite state automaton
  • a graph is composed of nodes, represented here by rectangles, and arcs between these nodes, represented here by arrows.
  • Such a graph is used to schematically represent the behavior of a finite state machine, each state of the automaton being represented by a node of the graph, a transition between two states being represented by an arc between the corresponding nodes.
  • NB number of blocks of data of size SB to be processed x value contained in the ith block of data of a packet where i is an integer between 1 and NB V, set of possible values of the i th data block of a packet (O .. 2 SB -1)
  • Z state machine G oriented graph acyclic modeling the Z controller
  • the set of values indicated next to each arrow connecting two rectangles respectively representing a state indicates for which data block values a transition between these two states is possible. For example, between the state E (0, 0) and the state E (1, 1) a transition is possible for a block value of '6'. Between the state E (0, 0) and the state E (1, 2) a transition is possible for all the block values included in the set: [0 ... 5] u [7 ... 16 ] u [18 ... 255].
  • the choice, among the possible transitions, of the current transition to be used to change from a state of depth (p-1) to the next state of depth p is a function of invention, the value contained in the p- th data block of the processed data packet.
  • a deterministic automaton is constructed, that is to say an automaton for which the possible transitions from a state are unambiguously defined, that is to say that only one transition is possible for a data block value.
  • the constructed graph is an oriented graph (ie the transitions are made only in one direction, so one can not return to the initial state) and acyclic (ie the transitions between states do not allow to browse the graph in a loop, but only in the direction of the final states of the graph).
  • the graph used in the invention also has other properties: on the one hand, it comprises a single initial state; on the other hand the number of transitions to be made to reach one of the final states from this unique initial state is constant, regardless of the transitions made to traverse the graph.
  • the depth in the graph of a state is equal to the number of transitions required to reach that state from the initial state.
  • the initial state is at depth O, and the depth is increasing by one at each new transition.
  • Such a DAG graph is a minimization of a tree.
  • the invention shows that it is possible to construct such a graph to represent all the rules of an ordered list of rules, while taking into account the semantics used when applying the rules to a data packet.
  • the graph is traversed from the initial state, the transition used to pass from a state of level p- 1 to level p (where l ⁇ p ⁇ NB) being determined by the value contained in the p th data block of a packet.
  • This mode of the graph leads to one of the final states of the graph, the final state with which a category of packet is associated.
  • This category of packet serves for example to identify an action to be performed on the packet concerned: a memory zone in which to store the packet or the data stream to which the packet belongs, a particular treatment to be performed on the packet or the data stream to which belongs the package, etc. It is thus possible to treat in a differentiated manner the different packets or data streams received, on the basis of the identifier of the final state which resulted in the flow of the graph for the packet concerned.
  • an identifier E (p, q) is assigned to each of the states of the graph, where p is the level of depth at which this state is located in the graph and q an index to distinguish the different states located at a level of given depth.
  • the identifier of a state is a datum used in the invention as a sort value, since such an identifier is used to determine a category of packet to which the processed packet must be assigned .
  • the transition from one state to another, from a given state of depth p is a function of the value of the block x p of the packet to be processed.
  • the value contained in the block x p of the packet to be processed determines what is the next state, of level p + 1, in the path of the graph.
  • association function representing the transition table T E (P q) of a state E (p, q).
  • the set V p of the possible values for this block is the set of values 0 to 255.
  • an identifier whose value is indicative of a nonexistent transition for example a null value identifier is used in the transition table T E ( P q ).
  • transition table The function of a transition table being to allow the sorting of the packets to be processed, such a table is also named here sorting table.
  • the first phase of the method according to the invention corresponds to the generation, from an ordered list LR of NR rules, of an acyclic oriented graph, representative of a PLC allowing the sorting of packets.
  • This phase corresponds to the steps S200 to S260 represented on the flowchart of FIG. 2.
  • the block size SB to be used is selected from a set of possible values. It is preferably chosen greater than or equal to 2 bits and less than or equal to a maximum useful size equal to the sum of the sizes of the data fields used in the definition of the rules of the list LR. It is possible to choose a larger size, but this will be detrimental to the performance of the algorithm and will increase the total memory size necessary for the storage of the data used to represent the graph G.
  • the curve shown in FIG. 6 illustrates the influence of the choice of block size on the time and memory complexity of the graph construction algorithm.
  • the vertical axis represents the calculation time and the horizontal axis the amount of memory required.
  • the larger the block size the higher the amount of memory needed to build the graph, but the lower the build time of this graph.
  • block size SB is chosen to be equal to 8 bits, this value making it possible to obtain a good compromise between the quantity of memory used and the necessary calculation time.
  • 8-bit block size makes it possible to process the data byte by byte, which is adapted to the design of a computer data processor. Indeed, such a processor is designed to perform very quickly operations on bytes, or on data blocks of size multiple of 8.
  • a block size of less than 8 bits or not a multiple of 8 implies the use of bit masking functions when processing the data fields of the packet, which increases the time required for the packet. packet processing.
  • the header of a packet is processed byte byte and the number NB of blocks of data to be processed for each packet is therefore equal to 13.
  • step S200 The order in which the data blocks are processed is also predetermined and chosen in step S200. It is assumed here that the different data blocks of the header of a packet will be processed in the order in which they are recorded in this packet, so as to make linear, and hence fast, the reading of these data blocks by view of their treatment.
  • the set of NB data blocks to be processed comprises at least the set of data fields used for the definition of the rules.
  • this set of blocks corresponds exactly to all the fields considered.
  • the set of fields considered is not a multiple of this size of chosen block, it is necessary to choose a sufficient number of blocks for all the considered fields to be included in this set of blocks.
  • the total number of bits of the set of blocks is greater than the total number of bits of the fields considered, the bits of the data blocks corresponding to no field can then take any values.
  • the method is applicable also in this case, since it suffices to define adequately (see step S210) the sets of values associated with each block.
  • the block denoted Xi, of reference 101 corresponds to the field 100A (protocol);
  • references 1 10 to 1 1 1 correspond to the field 100D (source port);
  • references 1 12 to 13 correspond to the field 100E (destination port).
  • each rule R k of the list LR is translated into a list of NB sets of values encoded on a number of bits equal to at the block size chosen in step S200.
  • Each set of values is associated with a block of data to be processed and contains possible values for that block.
  • the data sets are such that a data packet satisfies the sorting criterion defined by the rule R k if and only if for each integer p such that l ⁇ p ⁇ NB the value contained in the p th data block of this packet is included in the same set of values.
  • the sorting rule R k expressed by the following expression:
  • 10.2.3.4 eq 80 log (R k ) means that the "permit-log" category (meaning that the stream is allowed to pass through the equipment implementing packet filtering) is assigned to any stream using the "tcp" protocol, from any source address ('any'), from a source port that is strictly greater than 1023 and sent to the address 10.2.3.4 on the destination port 80.
  • Data block Xi [6]
  • Data block X 2 [0 ... 255]
  • Data block X 6 [10]
  • Data block X 7 [2]
  • Data block X 11 [0 ... 255]
  • Data block X 12 [0]
  • the associated set is therefore the set of integer values from 0 to 255;
  • step S220 a list degenerate graph is constructed for each rule R k , from the list LR, from the sequence of NB sets of values obtained in step S210 for this rule.
  • This degenerate graph in list represents the rule R k .
  • This graph includes an initial state denoted E k (0,0) and NB other states denoted E k (p, 0) successively connected to each other, where p is an integer between 1 and NB identifying the depth of the state in the graph, depth whose value is determined from the initial state in increments of 1 at each transition to the next state.
  • This graph represents an automaton associated with the rule R k .
  • the degenerate list graph obtained from the rule R k given as an example above, is shown schematically in FIG. 4.
  • transition from a state E k (p, 0) to the following state E k (p + 1, 0) is defined by a transition table T E (p 0) associated with the state E k (p, 0), where for
  • This transition table T Ek (p 0) defines an association function between the set of possible values of the data block x p and the set of identifiers of the states of level p + 1 of the degenerate graph in list. the case of this degenerate graph in list, there exists a transition to the state E k (p + 1, 0) from the state E k (p, 0) only for the data block values included in the set of data block values associated with the block x p , this set having been determined in step S210.
  • the transition table T E (p 0) associated with the state E k (p, 0) therefore contains, for the data block values included in the set of data block values associated with the block X p , the identifier of the state E k (p + 1, 0) and for the other data block values, an identifier whose value is indicative of a nonexistent transition, for example an identifier of zero value.
  • the different degenerate graphs in the list are combined into a single graph G.
  • a simple union of the degenerate graphs of connecting all these graphs to the same initial state results in the construction of a graph representing an automaton which is non-deterministic in terms of meaning that several transitions are possible from the initial state.
  • the method according to the invention provides for combining these degenerate graphs so as to obtain a final graph representative of a deterministic automaton.
  • step S235 the first two degenerate graphs representative of the first two rules of the rule list to be processed are combined.
  • Step S250 is executed following step S235.
  • step S235 the degenerate list graph obtained from the next rule in the rule list is combined with the graph obtained in step S260 previous.
  • step S250 the graph obtained in the previous step S235 is minimized.
  • the process of minimizing a graph that is applied in the invention consists in merging two equivalent states into a single state, whenever two equivalent states are detected in the graph.
  • the process is applied successively to each level of depth, and independently level by level (states belonging to different levels of depth can not be equivalent).
  • the highest level of depth is first treated, i.e. by the final states because this significantly reduces the processing time required for minimization.
  • Two final states are equivalent if the actions associated with them are identical.
  • Two non-final states are equivalent if they have the same transition table, that is, they point to the same states for the same block values.
  • the merging of two states during the minimization process returns, in known manner, to delete one of the two states and to keep the other, then to point the states of next higher levels, which initially pointed to the deleted state, to the preserved state.
  • Such a merge operation does not require processing of the transition tables since they are identical.
  • step S260 is executed in which it is determined whether all the degenerate graphs in the list have been processed. If so, the first phase of the method according to the invention ends. Otherwise, step S235 is executed for the next list generated graph corresponding to the next rule in the rule list LR.
  • the graph obtained is that of figure 7.
  • most of the states have a simple transition table, since for all the values of the set [0 ... 255] a single state is possible: the one to which point the arrow starting from the rectangle representing this state.
  • transition tables For states for which several states are possible depending on the value of the block, the transition tables are as follows:
  • the data packet sorting process corresponds to the second phase of the method according to the invention. It is described with reference to FIG. 3. This phase consists in implementing an automaton Z whose graph G, obtained following the last execution of step S260, forms a representation. This process is implemented by a device, in the form of software or hardware, which simulates the transitions of the graph for each of the states of this graph G.
  • step S300 the initial current state of the device is the state identified by E (0, 0) constituted by the identifier of the initial state of the automaton Z, irrespective of the data packet. sorting.
  • the sorting process is then an iterative process, each of the subsequent steps S310 of the sorting process of simulating a transition from the current state to a new current state.
  • each of the steps S310 consists in determining the identifier of the new current state from the identifier of the current state.
  • the sorting process comprises exactly NB iterations, that is to say NB steps 310.
  • the time required to obtain the sort value (and therefore the category) to be assigned to this packet is constant, equal to the time required to perform NB read operations in a table.
  • the packet processing time is therefore very low and constant, in this case minimized because it reduces the reading of NB values, and therefore negligible compared to the processing time required to process a packet rule by rule.
  • the different values of the data blocks are processed successively, identically, regardless of the packet, regardless of the block of data to be processed.
  • an identifier whose value is indicative of a nonexistent transition for example an identifier of zero value
  • signaling of the error for example by display, recording in a file, with indication of the last state identifier to which the flow of the graph has resulted, application of a rule "by default ", execution of a default action or assignment to a default category.
  • the sorting process ends when the NB data block values x p , for 1 ⁇ p ⁇ NB, have been processed or when a null status identifier is found.
  • step S235 The process of joining two graphs implemented during the execution of step S235 is described in more detail below.
  • This process makes it possible to join the two graphs so as to obtain a single graph representative of a deterministic automaton.
  • Such a process is known from the state of the art and described for example in John E. Hopcroft's paper, Rajeev Motwani, Rotwani and Jeffrey D. Ullman, entitled “Introduction to Automata Theory, Languages and Computability", (Addison- Wesley Longman Publishing Co., Inc., Boston, MA, 2000).
  • this known process is adapted to take into account the semantics used in the exploitation and the definition of the list of rules to be processed.
  • FIGS. 5A-5F A simplified example of joining two graphs is described here with reference to FIGS. 5A-5F.
  • an access control list comprising the following two rules R A and R B , relating to the source address of a packet:
  • the transition from the state E A (3.0) to the state E A (4.0) is possible only when the value of the fourth byte of the source address is '1'; in other words the table of transition T E (30) associated with the state E A (3.0) defines an association function of the set [0 ... 255] in the set of state identifiers such as:
  • the transition from the state E 8 (0, 0) to the state E B (1, 0) is possible only when the value of the first byte of the source address is' 57 '; in other words, the transition table T E (00) associated with the state E B (0,0) defines an association function of the set [0 ... 255] in the set of identifiers d state such as:
  • the transition from the state E B (2.0) to the state E B (3.0) is possible whatever the value of the third byte of the source address; in other words, the transition table T E e (2fi) associated with the state E B (2.0) defines an association function of the set [0 ... 255] in the set of identifiers of state such as:
  • transition table T EB (X0) associated with the state E B (3.0) defines an association function of the set [0 ... 255] in the set of identifiers d state such as:
  • the state E (0, 0) is a non-deterministic state in that in the graph thus obtained, as represented in FIG. 5B, when in the state E (0,0) one is either in the state state E A (0, 0), ie in the state E B (0,0).
  • the state E (0,0) will be made deterministic by comparing and merging the two transition tables T E ⁇ m and T E ⁇ m , associated with the states E A (0,0) and E 8 (0, 0) to from which the state E (0, 0) has been created, into a new transition table T E (0> 0) . In this way, for each value of the first byte of the source address, only one transition will be possible and not two.
  • the process of merging two transition tables TA and TB into a transition table T is as follows: for each of the values v of the set [0 ... 255], the two state identifiers TA (v) are examined. and TB (v) defined by TA and TB respectively, and:
  • a new non-deterministic state E (1, 0) is thus created by merging the two states E A (1, 0) and E B (1, 0), which is illustrated in FIG. 5C.
  • transition tables T E ⁇ lfi) and T E s ⁇ m are merged into a transition table T (1, 0) associated with the state ⁇ (1, 0) such that:
  • the state associated with the first processed rule is preferred, i.e. the transition table TA.
  • the graph shown in FIG. 5F can be used to sort a packet according to the two rules R A and R B defined below, by using the sorting process described with reference to FIG.
  • the method according to the invention allows an efficient classification of the packets into different categories, in particular a minimum and constant time, independent of the number of rules or the packet. It can handle byte-by-byte data packets or any data block size that is appropriate given the data processor or data processing device being used. It applies to any list of rules defining sorting criteria relating to the values of the data fields to be processed.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Business, Economics & Management (AREA)
  • General Business, Economics & Management (AREA)
  • Computer Hardware Design (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

Procédé de tri de paquets de données au moyen d'une liste de contrôle d'accès (L) ordonnée d'au moins une règle (Rk) de tri, comprenant une étape de détermination pour chaque paquet de données à classifier d'une valeur (e) servant à identifier une catégorie de paquet, un paquet de données comprenant un ensemble d'un ou plusieurs champs de données en fonction des valeurs desquels est déterminée la valeur de tri affectée à ce paquet, une dite règle de tri (Rk) définissant d'une part un critère de tri relatif à au moins un dit champ de données et d'autre part une valeur de tri destinée à être affectée à un paquet pour lequel ledit au moins un dit champ de données a une valeur vérifiant ledit critère de tri, la valeur de tri déterminée pour un paquet est obtenue en un nombre NB d'itérations (310) à partir d'une valeur de tri initiale (e0) en traitant dans un ordre prédéterminé un ensemble de NB blocs de données incluant l'ensemble de champs de données du paquet concerné, la taille desdits blocs de données étant choisie parmi un ensemble de plusieurs valeurs possibles.

Description

Procédé et dispositif de tri de paquets
L'invention concerne le domaine des réseaux de télécommunications et en particulier un procédé et un dispositif de tri de paquets. Le terme "tri" est utilisé dans ce document dans son sens le plus large: le tri d'un ensemble de paquets correspond au fait de répartir un ensemble de paquets en plusieurs groupes ou catégories. L'action de trier n'implique pas d'ordonnancement.
Certains équipements de réseaux de télécommunication, intégrant des modules de type routeurs ou pare-feux, mettent en œuvre des fonctions de contrôle d'accès réseau au moyen de listes ordonnées de règles, appelées "access control list" (ACL) ou liste de contrôle d'accès selon la terminologie anglo-saxonne. Chacune des règles d'une telle liste comprend une description des trames - appelée patron -, en termes de valeurs possibles pour les champs d'en-tête de cette trame, et un traitement associé, par exemple "passage" ou "rejet". Ainsi lorsqu'une trame atteint l'équipement, les valeurs contenues dans les champs d'en-tête de cette trame sont comparées avec les valeurs définies par les patrons définis dans les règles de la liste afin de déterminer quel est le traitement à effectuer pour cette trame.
Le nombre de règles d'une ACL peut être très élevé, de l'ordre de plusieurs centaines voire plusieurs milliers de règles. Il est donc extrêmement coûteux en temps de calcul de comparer les champs d'en-tête d'une trame avec chacune des règles d'une ACL.
Le brevet US 6 651 096 décrit une solution à ce problème de temps de calcul consistant à construire un arbre de décision binaire à partir de la liste ordonnée de règles, utilisée pour du contrôle d'accès. Dans cette solution, le traitement des trames suppose le test bit à bit de différents champs d'en-tête d'une trame en fonction de l'arbre de décision binaire construit. En outre, cette solution requiert une technologie hardware spécifique dite CAM (Content Adressable Memory).
Or l'utilisation d'un traitement bit par bit des trames suppose d'utiliser des opérations de masquage des octets des trames à traiter, afin d'accéder aux différents bits de données à analyser. En outre, l'utilisation d'un arbre de décision binaire suppose la mise en œuvre d'une fonction de test de bit pour chaque nœud de l'arbre, ce qui complexifie l'écriture d'un logiciel mettant en œuvre l'automate correspondant. Enfin, la construction d'un tel arbre est fastidieuse et très consommatrice de mémoire dès que le nombre de règles de la liste augmente. En outre, cette solution requiert un Hardware spécifique pour tenter de minimiser les problèmes de performance. Un des buts de l'invention est de remédier à des insuffisances et inconvénients de l'état de la technique et/ou d'y apporter des améliorations.
Dans ce but, l'invention a pour objet, selon un premier aspect, un procédé de tri de paquets de données en fonction d'une liste ordonnée d'au moins une règle de tri, comprenant une étape de détermination pour chaque paquet de données à traiter d'une catégorie de paquet associée,
- une dite règle de tri définissant d'une part un critère relatif à au moins un champ de données présent dans les paquets à trier et d'autre part une catégorie de paquet destinée à être associée à un paquet dont ledit au moins un champ de données contient une valeur vérifiant ledit critère,
- la catégorie associée à un paquet est identifiée par une valeur de tri déterminée en un nombre prédéterminé NB d'itérations à partir d'une valeur de tri initiale et en fonction de NB blocs de données du paquet à traiter,
- l'ensemble desdits NB blocs de données incluant le ou les champs de données utilisés pour la définition des règles de ladite liste, la taille desdits blocs de données étant choisie parmi un ensemble de plusieurs tailles de bloc,
- une itération comprenant une étape de détermination d'une valeur de tri courante à partir de la valeur de tri obtenue à l'itération précédente et de la valeur contenue dans le ieme bloc de données, l'ordre dans lequel lesdits blocs de données sont considérés étant prédéterminé.
Grâce à l'invention, le temps de traitement d'un paquet est réduit au temps de traitement de ces NB blocs de données. En particulier, le temps nécessaire pour déterminer l'action associée à un paquet est indépendant du contenu de ce paquet.
En outre, la taille des blocs utilisés pour traiter un paquet peut être choisie parmi différentes tailles, notamment des tailles de bloc supérieures ou égales à 2 bits. Ce qui signifie que le nombre d'itérations nécessaires pour traiter un paquet peut être réduit jusqu'à une itération par paquet en choisissant une taille de bloc suffisamment élevée. Par ailleurs lorsque la taille de bloc choisie est 8, 16 ou 24 bits, il devient inutile d'appliquer des opérations de masquage de bit pour procéder au traitement d'un paquet. Le temps de traitement d'un paquet est donc réduit par rapport aux solutions antérieures connues.
L'invention enseigne ainsi qu'il est possible de mettre en œuvre un tri des paquets en traitant ces paquets bloc par bloc, avec un taille de bloc quelconque et en un nombre prédéterminé d'itérations, qui est fonction de la taille de bloc choisie. Elle enseigne une méthode de traitement des règles de tri permettant de mettre en œuvre une telle technique de tri de paquets.
Selon un mode de réalisation, lors de la ieme itération, où i est un entier tel que l ≤ i ≤ NB , une valeur de tri courante est déterminée par lecture, dans une table identifiée par la valeur de tri obtenue à l'itération précédente, de la valeur de tri associée à la valeur du ieme bloc de données du paquet concerné.
Aucune opération de test n'est nécessaire, mais uniquement une opération de lecture de valeur dans une table. Le temps de traitement d'un paquet de données est donc égal à NB fois le temps de lecture d'une valeur dans une table. Il est réduit au minimum.
Selon un mode de réalisation, le procédé selon l'invention comprend une étape de génération à partir de ladite liste d'un graphe orienté acyclique à NB niveaux de profondeur, ledit graphe étant représentatif d'un automate à états, une dite valeur de tri identifiant un état dudit automate, ladite valeur de tri initiale identifiant l'état initial dudit automate, la table de transition d'un état de niveau p-1 de l'automate, où p est un entier tel que l ≤ p ≤ NB , étant une fonction entre l'ensemble des valeurs possibles du peme bloc de données et l'ensemble des identifiants d'état de niveau p.
La liste ordonnée de règles servant au tri des paquets est transformée en une représentation unitaire, sous forme de graphe à NB niveaux de profondeur, et ce quel que soit le nombre de règles de la liste. Ce graphe représente un automate à état qui est celui mis en œuvre pour le traitement automatisé des paquets à filtrer. Il en résulte une grande efficacité de traitement des paquets, puisque même lorsque le nombre de règles de la liste est élevé, la profondeur du graphe est limitée à NB niveaux.
Selon un mode de réalisation, le procédé selon l'invention comprend en outre une étape de construction d'un graphe dégénéré en liste à NB niveaux de profondeur à partir de chacune des règles de ladite liste, ledit graphe orienté acyclique étant obtenu par réunion des graphes dégénérés construits, un graphe dégénéré en liste représentant un automate à états et NB transitions.
Chaque règle de la liste ordonnée de règle est ainsi prise en compte dans la génération du graphe orienté acyclique. Le processus de construction de ce graphe repose sur une technique de réunion de graphes qui peut aisément être mis en œuvre par programme. Selon un mode de réalisation, le procédé selon l'invention comprend dans lequel ladite réunion est un processus itératif, chaque itération comprenant une étape d'obtention d'un graphe courant par réunion d'un graphe dégénéré en liste avec le graphe obtenu à l'itération précédente et une étape de minimisation dudit graphe courant.
Le processus de construction du graphe orienté acyclique est de ce fait peu consommateur en mémoire, puisqu'une construction incrémentale de ce graphe est possible.
Selon un mode de réalisation, le procédé selon l'invention comprend comprenant une étape consistant à traduire le critère de chacune des règles de tri de ladite liste en une liste de NB ensembles de valeurs de bloc de données, de telle sorte qu'un paquet de données vérifie ce critère si et seulement si pour chaque entier p tel que l ≤ p ≤ NB , la valeur contenue dans le peme bloc de données de ce paquet est comprise dans le peme ensemble de valeurs, le peme ensemble de valeurs comprenant la ou les valeurs lesquelles une transition existe entre leeme état et le peme état de l'automate représenté par le graphe dégénéré en liste obtenu à partir de la règle concernée.
Chacune des règles de la liste ordonnée de règles est ainsi traduite simplement en un graphe dégénéré en liste, par identification des différents ensembles de valeurs associés respectivement aux blocs de données à traiter. Il en découle une automatisation possible du processus de génération des graphes dégénérés en liste associés.
L'invention a également pour objet un dispositif de tri de paquets de données en fonction d'une liste ordonnée d'au moins une règle de tri, comprenant des moyens de détermination pour chaque paquet de données à traiter d'une catégorie de paquet associée,
- une dite règle de tri définissant d'une part un critère relatif à au moins un champ de données présent dans les paquets à trier et d'autre part une catégorie de paquet destinée à être associée à un paquet dont ledit au moins un champ de données contient une valeur vérifiant ledit critère,
- lesdits moyens étant conçus pour déterminer une valeur de tri identifiant la catégorie associée à un paquet en un nombre prédéterminé NB d'itérations à partir d'une valeur de tri initiale et en fonction de NB blocs de données du paquet à traiter, - l'ensemble desdits NB blocs de données incluant le ou les champs de données utilisés pour la définition des règles de ladite liste, la taille desdits blocs de données étant choisie parmi un ensemble de plusieurs tailles de bloc,
- une itération comprenant une étape de détermination d'une valeur de tri courante à partir de la valeur de tri obtenue à l'itération précédente et de la valeur contenue dans le ieme bloc de données, l'ordre dans lequel lesdits blocs de données sont considérés étant prédéterminé.
Les avantages énoncés pour le procédé selon l'invention sont transposables directement au dispositif selon l'invention.
Selon un mode de réalisation, lesdits moyens sont conçus pour déterminer lors de la ieme itération, où i est un entier compris entre 1 et NB, une valeur de tri courante est déterminée par lecture, dans une table identifiée par la valeur de tri obtenue à l'itération précédente, de la valeur de tri) associée à la valeur du ieme bloc de données du paquet concerné.
Selon une implémentation préférée, les différentes étapes du procédé selon l'invention sont mises en œuvre par un logiciel ou programme d'ordinateur, ce logiciel comprenant des instructions logicielles destinées à être exécutées par un processeur de données d'un dispositif de tri de paquets et conçu pour commander l'exécution des différentes étapes de ce procédé.
En conséquence, l'invention vise aussi un programme, susceptible d'être exécuté par un ordinateur ou par un processeur de données, ce programme comportant des instructions pour commander l'exécution des étapes d'un procédé tel que mentionné ci- dessus.
Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. Une implémentation hardware ou firmware est également possible.
L'invention vise aussi un support d'informations lisible par un ordinateur ou processeur de données, et comportant des instructions d'un programme tel que mentionné ci-dessus.
Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy dise) ou un disque dur.
D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet.
Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question.
D'autres buts, caractéristiques et avantages de l'invention apparaîtront à travers la description qui va suivre, donnée uniquement à titre d'exemple non limitatif, et faite par référence aux dessins annexés dans lesquels: - la figure 1 représente de manière schématique un paquet de données destiné à être filtré selon le procédé selon l'invention;
- la figure 2 est un organigramme d'un mode de réalisation d'une première phase du procédé selon l'invention;
- la figure 3 est un organigramme d'un mode de réalisation d'une deuxième phase du procédé selon l'invention;
- la figure 4 représente un graphe dégénéré en liste obtenu à partir d'une règle de tri;
- les figures 5A à 5F représentent différents graphes obtenus à partir d'une liste ordonnée de règles à différents stades de traitement lors de la mise en œuvre du procédé selon l'invention;
- la figure 6 est une courbe illustrant les performances du procédé selon l'invention;
- la figure 7 représente un graphe obtenu à partir d'une liste ordonnée de règles.
L'invention est décrite plus en détail dans le cas de son application au tri de paquets de données sous forme de trames IP. L'invention est applicable toutefois à tout autre format de paquets de données et quel que soit le protocole de communication utilisé pour la transmission de ces paquets.
Dans le cas d'une trame IP, représentée schématiquement à la figure 1 , le paquet 100 de données comprend, dans son entête, différents champs de données en fonction des valeurs desquels le tri des trames est effectué conformément à une liste ordonnée de règles, formant liste de contrôle d'accès. Ces champs de données sont les suivants:
- un premier champ 100A comprenant un identifiant de protocole permettant d'identifier un protocole parmi une liste de protocoles possibles, cette liste comprenant par exemple les protocoles TCP (Transmission Control Protocol), UDP (User Datagram Protocol), IP (Internet Protocol); ce champ est codé sur un octet identifié par la référence 101 ;
- un deuxième champ 100B comprenant une adresse source, identifiant un équipement émetteur du paquet; ce champ est codé sur 4 octets identifiés respectivement par les références 102, 103, 104 et 105;
- un troisième champ 100C comprenant une adresse destination, identifiant un équipement destinataire du paquet; ce champ est codé sur 4 octets identifiés respectivement par les références 106, 107, 108 et 109; - un quatrième champ 100D comprenant un identifiant de port de communication source, relatif à l'équipement émetteur du paquet; ce champ est codé sur 2 octets identifiés respectivement par les références 1 10 et 1 1 1 ;
- un cinquième champ 100E comprenant un identifiant de port de communication destinataire, relatif à l'équipement destinataire du paquet; ce champ est codé sur 2 octets identifiés respectivement par les références 1 12 et 1 13.
La taille en nombre de bits de ces différents champs est variable: usuellement le premier champ de données est codé sur 8 bits (i.e. un octet), les deuxième et troisième champs sont codés chacun sur 32 bits (i.e. 4 octets), tandis que les quatrième et cinquième champs sont codés sur 16 bits (i.e. 2 octets). Comme cela apparaîtra ci-dessous, la taille de ces champs de données importe peu, le procédé selon l'invention traitant l'en-tête d'un paquet bloc par bloc, par exemple octet par octet, en utilisant une taille de bloc de données éventuellement différente, et donc indépendante, de la taille des champs de données utilisée pour interpréter les valeurs contenues dans ces blocs. En effet, le procédé selon l'invention met en œuvre un traitement automatisé des valeurs prises par ces différents champs, ce traitement ne nécessitant pas d'interprétation de ces valeurs.
En outre, l'ordre dans lequel ces champs de données sont enregistrés dans un paquet peut être différent, et est donc indépendant, de l'ordre dans lequel ces champs de données sont traités par le procédé selon l'invention. De préférence cependant, les différents blocs de données de l'en-tête d'un paquet seront traités dans l'ordre dans lequel ils sont enregistrés dans ce paquet, de manière à rendre linéaire, et donc rapide, la lecture de ces blocs de données en vue de leur traitement.
Les listes ordonnées de règle utilisées usuellement pour le filtrage de paquets IP sont connues sous la dénomination anglo-saxonne "Access Control List" (ACL).
Chacune des règles d'une telle liste définit un critère pour au moins un des champs d'entêté d'un paquet et une action associée, action qui est à appliquer au paquet - ou au flux de données auquel appartient ce paquet - dont la ou les valeurs du ou des champs de données concernés vérifient ce critère. En d'autres termes, une règle définit une catégorie de paquet à affecter à un paquet ou flux vérifiant le critère défini par cette règle.
Par exemple, la règle de tri codée par l'expression suivante:
Permit tcp anygt 1023 10.2.3.4 eq 80 log signifie que la catégorie "permit - log" (signifiant que le flux est autorisé à transiter dans l'équipement mettant en œuvre le tri de paquet) est affectée à tout flux de données utilisant le protocole "tcp", issu de n'importe quelle adresse source ('any'), à partir d'un port source supérieur strictement à 1023 et émis à destination de l'adresse
10.2.3.4 sur le port destination 80.
La catégorie de paquet à laquelle est affecté un paquet dépend également de la sémantique utilisée ainsi que l'ordre dans lequel les règles d'une liste de règles sont parcourues et testées pour ce paquet. L'ordre de parcours de la liste de règles définit si cette liste est parcourue en commençant par la première règle (ordre appelé "top- down" dans la terminologie anglo-saxonne) ou par la dernière règle (ordre appelé
"bottom-up" dans la terminologie anglo-saxonne). La sémantique détermine les conditions d'arrêt du processus de parcours de la liste :
- soit la liste de règles est parcourue règle par règle jusqu'à ce que le paquet traité vérifie le critère défini par la règle courante; on dit dans ce cas qu'on applique une sémantique dite de type "first match" selon la terminologie anglo-saxonne, en ce que c'est la première règle pour laquelle il y a vérification du critère qui définit la catégorie à laquelle ce paquet est affecté;
- soit la liste de règles est parcourue règle par règle pour déterminer la dernière règle dont le critère est vérifié par le paquet traité; on dit dans ce cas qu'on applique une sémantique dite de type "last match" selon la terminologie anglo-saxonne, en ce que c'est la dernière règle pour laquelle il y a vérification du critère qui définit la catégorie à laquelle ce paquet est affecté. Une sémantique dite de type "best match" (longest prefix) est également envisageable: elle consiste à parcourir toute la liste de règle et à sélectionner la règle optimale, c'est-à-dire celle pour laquelle le paquet vérifie le mieux le critère associé. Ce type de sémantique suppose de définir une méthode de calcul d'un paramètre constituant une mesure d'optimalité du test de vérification d'un critère et de déterminer pour quelle règle la valeur de ce paramètre est la plus élevée.
Pour remarque, l'utilisation de la sémantique "first match" et de l'ordre "top-down" pour le parcours d'une liste de règles produit le même résultat, en termes de catégorie de paquet, que l'utilisation de la sémantique "last match" et de l'ordre "bottom-up" pour le parcours de cette même liste.
De même, l'utilisation de la sémantique "last match" et de l'ordre "top-down" pour le parcours d'une liste de règles produit le même résultat, en termes de catégorie de paquet, que l'utilisation de la sémantique "first match" et de l'ordre "bottom-up" pour le parcours de cette même liste.
Le procédé selon l'invention comprend deux phases. La première phase correspond à la génération, à partir d'une liste ordonnée de règles, de données représentatives d'un graphe orienté acyclique (DAG), modélisant un automate à états finis (DFA). La deuxième phase du procédé selon l'invention consistant à trier les paquets par mise en œuvre d'un automate à états représenté par le graphe construit.
De manière connue, et comme illustré par exemple à la figure 7, un graphe, en tant que représentation, est composé de nœuds, représentés ici par des rectangles, et d'arcs entre ces nœuds, représentés ici par des flèches. Un tel graphe est utilisé pour représenter schématiquement le comportement d'un automate à états finis, chaque état de l'automate étant représenté par un nœud du graphe, une transition entre deux états étant représentée par un arc entre les nœuds correspondant. Afin de simplifier l'exposé, on parlera ici également d'états et de transitions s'agissant d'un graphe.
Les notations suivantes sont utilisées dans la suite du document: LR liste ordonnée de règles (ACL)
NR nombre de règles dans la liste LR
Rk keme règle de la liste LR, où k est un entier compris entre 1 et NR
SB taille d'un bloc de données d'un paquet
NB nombre de blocs de données de taille SB à traiter x, valeur contenue dans le ieme bloc de données d'un paquet où i est un entier compris entre 1 et NB V, ensemble des valeurs possibles du ième bloc de données d'un paquet (O .. 2SB-1 ) Z automate à états G graphe orienté acyclique modélisant l'automate Z
E(0, 0) identifiant de l'état initial de l'automate Z, cet état étant représenté par la racine du graphe G E(p, q) identifiant de l'état de l'automate Z, cet état étant représenté dans le graphe G par un nœud numéroté q et se situant à la profondeur p dans le graphe G
TE(P,q) table de transition dans l'automate Z de l'état E(p,q) e identifiant de l'état courant (valeur de tri courante)
Te table de transition dans l'automate Z de l'état e
Te(x,) valeur de tri associée à la valeur x, par la table de transition Te [a...b] ensemble des nombres entiers non négatif n tels que a ≤ n ≤ b
[a] singleton contenant l'entier non négatif a
Sur la figure 7, l'ensemble de valeurs indiqué à côté de chaque flèche reliant deux rectangles représentant respectivement un état, indique pour quelles valeurs de bloc de données une transition entre ces deux états est possible. Par exemple, entre l'état E(0, 0) et l'état E(1 ,1 ) une transition est possible pour une valeur de bloc de '6'. Entre l'état E(0, 0) et l'état E(1 ,2) une transition est possible pour toutes les valeurs de bloc comprises dans l'ensemble: [0...5] u[7...16] u[18...255] .
Comme cela sera décrit plus en détail plus loin, le choix, parmi les transitions possibles, de la transition courante à utiliser pour passer d'un état de profondeur (p-1 ) à l'état suivant de profondeur p est fonction, dans l'invention, de la valeur contenue dans le peme bloc de données du paquet de données traité. Dans le contexte de l'invention, on construit un automate déterministe, c'est-à-dire un automate pour lequel les transitions possibles à partir d'un état sont définies de manière non ambiguë, c'est- à-dire qu'une seule transition est possible pour une valeur de bloc de données.
Dans le contexte de l'invention, le graphe construit est un graphe orienté (i.e. les transitions se font uniquement dans un seul sens, on ne peut donc revenir à l'état initial) et acyclique (i.e. les transitions entre états ne permettent pas de parcourir le graphe en boucle, mais uniquement en direction des états finaux du graphe). Le graphe utilisé dans l'invention possède en outre d'autres propriétés: d'une part, il comporte un état initial unique; d'autre part le nombre de transitions à effectuer pour parvenir à un des états finaux à partir de cet état initial unique est constant, quelles que soient les transitions effectuées pour parcourir le graphe. De ce fait, la profondeur dans le graphe d'un état est égale au nombre de transitions nécessaires pour parvenir à cet état à partir de l'état initial. Par convention, l'état initial est à la profondeur O, et la profondeur est croissante d'une unité à chaque nouvelle transition. Un tel graphe DAG est une minimisation d'un arbre.
L'invention montre qu'il est possible de construire un tel graphe pour représenter toutes les règles d'une liste ordonnée de règle, et ce tout en prenant en compte la sémantique utilisée lors de l'application des règles à un paquet de données. Dans le procédé selon l'invention, pour chaque paquet de données à classifier, le graphe est parcouru à partir de l'état initial, la transition utilisée pour passer d'un état de niveau p- 1 au niveau p (où l ≤ p ≤ NB ) étant déterminée par la valeur contenue dans le peme bloc de données d'un paquet. Ce mode de parcours du graphe mène à un des états finaux du graphe, état final auquel est associée une catégorie de paquet.
Cette catégorie de paquet sert par exemple à identifier une action à effectuer sur le paquet concerné: une zone mémoire dans laquelle stocker le paquet ou le flux de données auquel appartient le paquet, un traitement particulier à effectuer sur le paquet ou le flux de données auquel appartient le paquet, etc. Il est ainsi possible de traiter de manière différenciée les différents paquets ou flux de données reçus, sur la base de l'identifiant de l'état final auquel à abouti le parcours du graphe pour le paquet concerné.
Par commodité, un identifiant E(p,q) est affecté à chacun des états du graphe, où p est le niveau de profondeur auquel se situe cet état dans le graphe et q un indice permettant de distinguer les différents états situés à un niveau de profondeur donné. Pour la mise en œuvre de l'invention, l'identifiant d'un état est une donnée utilisée dans l'invention comme valeur de tri, puisqu'un tel identifiant sert à déterminer une catégorie de paquet à laquelle le paquet traité doit être affectée.
La transition d'un état à un autre, à partir d'un état de profondeur p donnée, est fonction de la valeur du bloc xp du paquet à traiter. En d'autres termes, lors du parcours du graphe pour le traitement d'un paquet de données, à chaque niveau de profondeur p du graphe, quel que soit l'état courant à ce niveau de profondeur dans le graphe, la valeur contenue dans le bloc xp du paquet à traiter détermine quel est l'état suivant, de niveau p+1 , dans le parcours du graphe.
Il est donc possible de définir une fonction d'association, représentant la table de transition TE(P q) d'un état E(p,q). Cette fonction d'association est une fonction de l'ensemble Vp des valeurs possibles pour le peme bloc de données vers l'ensemble des identifiants Ep+1 des identifiants des états de niveau p+1 , qui à chaque valeur v de Vp associe un identifiant d'état e de l'ensemble des identifiants Ep+i tel que: e= TE(p q)(v)
Dans le cas où le bloc de données à traiter est un octet, l'ensemble Vp des valeurs possibles pour ce bloc est l'ensemble des valeurs 0 à 255. Dans la cas où aucune transition n'est possible ou définie pour une valeur de l'ensemble Vp de données, un identifiant dont la valeur est indicatrice d'une transition inexistante, par exemple un identifiant de valeur nulle est utilisé dans la table de transition TE(P q).
La fonction d'une table de transition étant de permettre le tri des paquets à traiter, une telle table est également nommée ici table de tri.
Génération d'un graphe orienté acvclique (DAG)
La première phase du procédé selon l'invention correspond à la génération, à partir d'une liste ordonnée LR de NR règles, d'un graphe orienté acyclique, représentatif d'un automate permettant le tri de paquets. Cette phase correspond aux étapes S200 à S260 représentées sur l'organigramme de la figure 2.
A l'étape S200, la taille de bloc SB à utiliser est choisie parmi un ensemble de valeurs possibles. Elle est choisie de préférence supérieure ou égale à 2 bits et inférieure ou égale à une taille maximale utile égale à la somme des tailles des champs de données utilisés dans la définition des règles de la liste LR. Il est possible de choisir une taille supérieure, mais ceci sera au détriment des performances de l'algorithme et augmentera la taille mémoire totale nécessaire pour le stockage des données servant à représenter le graphe G. Dans le cas d'un paquet IP, la taille maximale utile est de 13*8= 104 bits, puisque les champs d'entêté de paquet utilisés pour la définition des règles de tri sont codés sur 13 octets (protocole, adresse source, adresse destinataire, port source, port destinataire). D'autres champs peuvent éventuellement être ajoutés ou retirés suivant le contexte d'application.
La courbe représentée à la figure 6 illustre l'influence du choix de la taille de bloc sur la complexité en temps et en mémoire de l'algorithme de construction du graphe. Sur cette figure, l'axe vertical représente le temps de calcul et l'axe horizontal la quantité de mémoire nécessaire. Plus la taille de bloc est basse et proche de 1 bit, et plus la quantité de mémoire nécessaire à la construction du graphe est faible, mais plus le temps de construction de ce graphe est élevé. Inversement, plus la taille de bloc est élevée, et plus la quantité de mémoire nécessaire à la construction du graphe est élevée, mais plus le temps de construction de ce graphe est faible. En effet, avec une taille de bloc de SB=1 bit, le graphe G va comprendre 13*8= 104 niveaux de profondeur avec une table de transition à 21=2 entrées pour chaque état, alors qu'avec une taille de bloc de SB=104 bits, le graphe comprend un seul et unique niveau de profondeur à partir de l'état initial et une table de transition à 2104 entrées pour l'état initial.
Dans l'exemple décrit ci-dessous, on suppose que la taille de bloc SB est choisie égale à 8 bits, cette valeur permettant d'obtenir un bon compromis entre la quantité de mémoire utilisée et le temps de calcul nécessaire. En outre, une taille de bloc de 8 bits permet de traiter les données octet par octet, ce qui est adapté par rapport à la conception d'un processeur de données informatique. En effet un tel processeur est conçu pour effectuer très rapidement des opérations sur des octets, ou sur des blocs de données de taille multiple de 8.
Il faut noter ici qu'une taille de bloc inférieure à 8 bits ou qui ne serait pas un multiple de 8 implique l'utilisation de fonctions de masquage de bits lors du traitement des champs de données du paquet, ce qui augmente le temps nécessaire au traitement des paquets.
La taille de bloc étant choisie égale à 8 dans l'exemple décrit, l'en-tête d'un paquet est traitée octet par octet et le nombre NB de blocs de données à traiter pour chaque paquet est donc égal à 13.
L'ordre dans lequel les blocs de données sont traités est également prédéterminé et choisi à l'étape S200. On suppose ici que les différents blocs de données de l'entête d'un paquet seront traités dans l'ordre dans lequel ils sont enregistrés dans ce paquet, de manière à rendre linéaire, et donc rapide, la lecture de ces blocs de données en vue de leur traitement.
L'ensemble de NB blocs de données à traiter comprend au moins l'ensemble de champs de données utilisés pour la définition des règles. De préférence, cet ensemble de blocs correspond exactement à l'ensemble des champs considérés. Toutefois, lorsqu'on utilise une taille de bloc différente de 1 bit, par exemple une taille de bloc de 8 bits, et que l'ensemble des champs considérés n'est pas un multiple de cette taille de bloc choisie, il est nécessaire de choisir un nombre de blocs suffisant pour que l'ensemble des champs considérés soit inclus dans cet ensemble de blocs. Il y a donc des cas où le nombre total de bits de l'ensemble de blocs est supérieur au nombre total de bits des champs considérés, les bits des blocs de données ne correspondant à aucun champ pouvant alors prendre des valeurs quelconques. Cependant, le procédé est applicable également dans ce cas, puisqu'il suffit pour cela de définir de manière adéquate (voir étape S210) les ensembles de valeurs associés à chaque bloc.
Dans l'exemple décrit ici, illustré à la figure 1 , l'ensemble des NB=13 blocs de données 101 à 1 13 correspond exactement à l'ensemble des champs de données 100A à 100E.
Dans cet exemple:
- le bloc noté Xi, de référence 101 , correspond au champ 100A (protocole);
- les blocs notés x2 à x5, de références 102 à 105, correspondent au champ 100B (adresse source); - les blocs notés x6 à x9, de références 106 à 109, correspondent au champ 100C
(adresse destination);
- les blocs notés x10 à Xn, de références 1 10 à 1 1 1 correspondent au champ 100D (port source);
- les blocs notés x12 à Xi3, de références 1 12 à 1 13 correspondent au champ 100E (port destination).
A l'étape S210, chaque règle Rk de la liste LR, pour l ≤ k < NR où NR est le nombre de règles de la liste LR, est traduite en une liste de NB ensembles de valeurs codées sur un nombre de bits égal à la taille de bloc choisie à l'étape S200. Chaque ensemble de valeurs est associé à un bloc de données à traiter et contient des valeurs possibles pour ce bloc. Les ensembles de données sont tels qu'un paquet de données vérifie le critère de tri défini par la règle Rk si et seulement si pour chaque entier p tel que l ≤ p ≤ NB la valeur contenue dans le peme bloc de données de ce paquet est comprise dans le peme ensemble de valeurs. Par exemple, la règle de tri Rk exprimée par l'expression suivante:
Permit tcp any gt 1023 10.2.3.4 eq 80 log (Rk) signifie que la catégorie " permit - log" (signifiant que le flux est autorisé à transiter dans l'équipement mettant en œuvre le filtrage des paquets) est affectée à tout flux de données utilisant le protocole "tcp", issu de n'importe quelle adresse source ('any'), à partir d'un port source supérieur strictement à 1023 et émis à destination de l'adresse 10.2.3.4 sur le port destination 80.
Les NB=13 ensembles de valeurs associés à cette règle et à chacun des blocs de données sont donc :
Bloc de données Xi : [6] Bloc de données X2: [0...255]
Bloc de données x3: [0...255]
Bloc de données x4: [0...255]
Bloc de données x5: [0...255]
Bloc de données X6: [10] Bloc de données X7: [2]
Bloc de données x8: [3]
Bloc de données x9: [4]
Bloc de données X10: [4...255]
Bloc de données X11 : [0...255] Bloc de données X12: [0]
Bloc de données X13: [80]
En effet,
- pour le premier bloc X1, seule la valeur de bloc '6' est possible car cette valeur signifie que le protocole utilisé est TCP;
- pour les octets x2 à x5 toutes les valeurs sont possibles puisque n'importe quelle adresse source est possible; l'ensemble associé est donc l'ensemble des valeurs entières de 0 à 255;
- pour le bloc x6, seule la valeur de bloc '10' est possible du fait de la contrainte imposée sur le premier octet de l'adresse de destination, contrainte qui découle de celle définie dans la règle sur l'adresse de destination (=10.2.3.4);
- pour le bloc x7, seule la valeur de bloc '2' est possible du fait de la contrainte imposée sur le deuxième octet de l'adresse de destination (=10.2.3.4);
- pour le bloc x8, seule la valeur de bloc '3' est possible du fait de la contrainte imposée sur le troisième octet de l'adresse de destination (=10.2.3.4);
- pour le bloc x9, seule la valeur de bloc '4' est possible du fait de la contrainte imposée sur le quatrième octet de l'adresse de destination (=10.2.3.4);
- pour le bloc X10, seules les valeurs 4 à 255 sont possibles du fait de la contrainte imposée sur le premier octet du port source, contrainte qui découle de celle définie dans la règle sur le port source (>1023); - pour le bloc X11, toutes les valeurs sont possibles du fait de la contrainte imposée sur le deuxième octet du port source (>1023);
- pour le bloc x12, seule la valeur de bloc O' est possible du fait de la contrainte imposée sur le premier octet du port destination, contrainte qui découle de celle définie dans la règle sur le port destination (=80);
- pour le bloc x13, seule la valeur de bloc '80' est possible du fait de la contrainte imposée sur le deuxième octet du port destination (=80).
L'homme du métier généralisera aisément la manière de construire ces ensembles de valeurs possibles aux différents cas se présentant pour la définition d'une règle de tri.
A l'étape S220, un graphe dégénéré en liste est construit pour chaque règle Rk, de la liste LR, à partir de la séquence des NB ensembles de valeurs obtenue à l'étape S210 pour cette règle. Ce graphe dégénéré en liste représente la règle Rk. Ce graphe comprend un état initial noté Ek(0,0) et NB autres états notés Ek(p,0) reliés successivement l'un à l'autre, où p est un entier compris entre 1 et NB identifiant la profondeur de l'état dans le graphe, profondeur dont la valeur est déterminée à partir de l'état initial par incrément de 1 à chaque transition vers l'état suivant. Ce graphe représente un automate associé à la règle Rk.
Le graphe dégénéré en liste, obtenu à partir de la règle Rk donnée en exemple ci-dessus, est représenté de manière schématique à la figure 4.
Dans ce graphe dégénéré, la transition d'un état Ek(p,0) à l'état Ek(p+1 ,0) suivant est définie par une table de transition TE (p 0) associée à l'état Ek(p,0), où pour
\ < p < NB . Cette table de transition TEk(p 0) définit une fonction d'association entre l'ensemble des valeurs possibles du bloc de données xp et l'ensemble des identifiants des états de niveau p+1 du graphe dégénéré en liste.. Dans le cas de ce graphe dégénéré en liste, il n'existe une transition vers l'état Ek(p+1 ,0) à partir de l'état Ek(p,0) que pour les valeurs de bloc de données comprises dans l'ensemble de valeurs de bloc de données associé au bloc xp, cet ensemble ayant été déterminé à l'étape S210. La table de transition TE (p 0) associée à l'état Ek(p,0) contient donc pour les valeurs de bloc de données comprises dans l'ensemble de valeurs de bloc de données associé au bloc Xp, l'identifiant de l'état Ek(p+1 ,0) et pour les autres valeurs de bloc de données, un identifiant dont la valeur est indicatrice d'une transition inexistante, par exemple un identifiant de valeur nulle.
Dans le graphe dégénéré en liste représenté à la figure 4, représentant la règle Rk, les tables de transitions T "-EEk( ,p, m0) des états Ek(p,0), pour 0<p<!3, sont définies comme suit: r£t(0>0)(v) = 0
Figure imgf000018_0001
{Vve[0...255] TEk(l0)(v) = Ek(2,0) {Vve[0...255] 7^(^ = ^(3,0) {Vve[0...255] r£i(3>0)(v) = £t(4,0) {Vve[0...255] TEk(40)(v) = Ek(5,0) [Vve[0...9]u[11...255] r£t(5>0)(v) = 0 rJs.(S>o)αo) = £:t(6,θ) r,. (6>0)(v) = 0
r,. (7>0)(v) = 0
Figure imgf000018_0002
(8>0)(v) = 0
Figure imgf000018_0003
Vv<≡[0...3] r£t(90)(v)-0 Vve[4...255] r£t(9>0)(v) = £t(10,0)
Vve[0...255] r£t(10>0)(v) = £t(ll,0) Vve[1...255] TR Ek ( 0n-1m,0)( vv) = 0
£t(ll,0) (0)^^,(12,0)
Vv e [0...79]u[81...255] TR ....Jv) = 0
L£t(12,0) (80) = E, (13,0)
Lors des étapes S235 à S260 suivantes, il est procédé à la réunion des différents graphes dégénérés en liste en un graphe G unique. Une simple réunion des graphes dégénérés consistant à rattacher tous ces graphes à un même état initial, aboutit à la construction d'un graphe représentant un automate qui est non déterministe en ce sens que plusieurs transitions sont possibles à partir de l'état initial. Le procédé selon l'invention prévoit de réunir ces graphes dégénérés de manière à obtenir un graphe final représentatif d'un automate déterministe.
Le processus de réunion de ces graphes est itératif. Lors de la première itération, il est procédé lors de la première exécution de l'étape S235 à la réunion des deux premiers graphes dégénérés représentatifs des deux premières règles de la liste de règle à traiter. L'étape S250 est exécutée suite à l'étape S235.
Puis à chaque itération suivante, c'est-à-dire à chaque exécution de l'étape S235, le graphe dégénéré en liste obtenu à partir de la règle suivante dans la liste de règles est réuni avec le graphe obtenu à l'étape S260 précédente.
Le processus de réunion qui est utilisé dans l'invention est décrit plus en détail ci- dessous.
A l'étape S250, le graphe obtenu à l'étape S235 précédente est minimisé. Le processus de minimisation d'un graphe qui est appliqué dans l'invention consiste à fusionner en un état unique deux états équivalents, chaque fois que deux états équivalents sont détectés dans le graphe. Le processus est appliqué successivement à chacun des niveaux de profondeur, et indépendamment niveau par niveau (des états appartenant à des niveaux de profondeur différents ne pouvant être équivalents). De préférence, on commence par traiter le niveau de profondeur le plus élevé, i.e; par les états finaux car ceci permet de réduire significativement le temps de traitement nécessaire à la minimisation.
Deux états finaux sont équivalents si les actions qui leur sont respectivement associées sont identiques. Deux états non finaux sont équivalents s'ils ont une même table de transition, c'est-à-dire qu'ils pointent vers les mêmes états pour les mêmes valeurs de bloc.
La fusion de deux états lors du processus de minimisation revient, de manière connue, à supprimer un des deux états et à conserver l'autre, puis à faire pointer les états de niveaux immédiatement supérieur, qui pointaient initialement vers l'état supprimé, vers l'état conservé. Une telle opération de fusion ne nécessite pas de traitement des tables de transitions puisqu'elles sont identiques.
Le fait d'appliquer ce processus de minimisation après chaque étape S235 de réunion d'un graphe dégénéré en liste avec le graphe global permet de réduire la quantité de mémoire totale et le temps nécessaire à la construction du graphe. Toutefois il est également possible de ne procéder à cette minimisation sur le graphe final, lorsque tous les graphes dégénérés en liste ont été réunis en un même graphe, c'est-à-dire suite à la dernière exécution de l'étape S260.
Suite à l'étape S250, on exécute l'étape S260 lors de laquelle on détermine si tous les graphes dégénérés en liste ont été traités. Dans l'affirmative, la première phase du procédé selon l'invention se termine. Dans le cas contraire, on exécute l'étape S235 pour le graphe généré en liste suivant correspondant à la règle suivante dans la liste LR de règles.
Dans l'exemple de l'application du procédé selon l'invention à la liste de règles suivantes:
Permit tcp any 57.7.0.0 0.0.255.255 eq telnet Deny tcp any any Deny udp any any log
Permit udp host 1 .2.3.4 host 5.6.7.8 Permit ip any any log
le graphe obtenu est celui de la figure 7. Dans ce graphe la plupart des états ont une table de transition simple, puisque pour toutes les valeurs de l'ensemble [0...255] un seul état est possible: celui vers lequel point la flèche partant du rectangle représentant cet état.
Pour les états pour lesquels plusieurs états suivants sont possibles selon la valeur du bloc, les tables de transitions sont les suivantes:
Figure imgf000020_0001
[Vv e [0...56] u[58...255] TE(5X) (v) - E(6, 2) r£(51) (57) = £(6,l)
Vv e [0...6] u[8...255] TE(6 l) (v) = E(1, 2) TE(6 1) {1) = E{1Λ)
Vv e [1...255] r£(1U) (v) = E(12,2) r£(1U)(0) = E(i2,i) [Vv e [0...22] u[24...255] TE(l2 l) (v) = E(\3,2) [TE(ΑÏ) (23) = E(13, 1)
Les états finaux et leurs actions associées sont respectivement: E(13,0) action "permit - log" E(13,1 ) action "permit - nolog"
E(13,2) action "deny - log"
E(13,3) action "deny - nolog"
Tri des paquets de données Le processus de tri de paquet de données correspond à la deuxième phase du procédé selon l'invention. Il est décrit par référence à la figure 3. Cette phase consiste à mettre en œuvre un automate Z dont le graphe G, obtenu suite à la dernière exécution de l'étape S260, forme une représentation. Ce processus est mis en œuvre par un dispositif, sous forme de logiciel ou de hardware, qui simule les transitions du graphe pour chacun des états de ce graphe G.
A l'étape S300, l'état courant initial du dispositif est l'état identifié par E(0, 0) constituée par l'identifiant de l'état initial de l'automate Z, et ce quel que soit le paquet de données à trier. Le processus de tri est ensuite un processus itératif, chacune des étapes S310 ultérieures du processus de tri consistant à simuler une transition de l'état courant vers un nouvel état courant. En d'autres termes, chacune des étapes S310 consiste à déterminer l'identifiant du nouvel état courant à partir de l'identifiant de l'état courant.
Pour décrire le processus de tri, on utilise les notations ci-après. L'état courant de niveau p-1 , 1 ≤ p < NB , dans le graphe est identifié par la valeur de tri courante e telle que: e= E(p-1 ,q)
la table de transition de l'état courant e est notée: , q)
et le nouvel état courant lors de la mise en œuvre de l'automate Z est identifié par: e=Te(xp)= TE(p-i ,q)(xp) Le processus de tri comprend exactement NB itérations, c'est-à-dire NB étapes 310. L'itération p pour l ≤ p ≤ NB consiste à déterminer, à partir de la valeur de tri courante e et de la valeur xp du peme bloc de données, la nouvelle valeur de tri courante e telle que e= Te(xp). Cette valeur est obtenue par simple lecture de la valeur Te(xp) dans la table de transition Te associée à l'état e courant.
Il en résulte que quel que soit le nombre de règles de la liste de règle, quel que soit le paquet de données à traiter, le temps nécessaire pour obtenir la valeur de tri (et donc la catégorie) à affecter à ce paquet est constant, égal au temps nécessaire pour effectuer NB opérations de lecture dans une table. Le temps de traitement par paquet est donc très faible et constant, en l'occurrence minimisé car réduit à la lecture de NB valeurs, et donc négligeable par rapport au temps de traitement nécessaire pour traiter règle par règle un paquet. En particulier, il n'y a aucune opération arithmétique à effectuer sur les valeurs des blocs de données, ni même de test ou de comparaison. Enfin, les différentes valeurs des blocs de données sont traitées successivement, de manière identique, quel que soit le paquet, quel que soit le bloc de données à traiter.
Dans le cas où l'on obtient, lors de la mise en œuvre de l'automate Z, un identifiant dont la valeur est indicatrice d'une transition inexistante, par exemple un identifiant de valeur nulle, cela signifie qu'il n'y a aucune catégorie de paquet qui puisse être affectée au paquet ou flux de données traité. Dans une telle situation, un traitement particulier est prévu: signalisation de l'erreur, par exemple par affichage, enregistrement dans un fichier, avec indication de l'identifiant dernier état auquel a abouti le parcours du graphe, application d'une règle "par défaut", exécution d'une action par défaut ou encore affectation à une catégorie par défaut. Le processus de tri se termine lorsque les NB valeurs de blocs de données xp, pour 1 ≤ p < NB , ont été traités ou lorsqu'un identifiant d'état nul est trouvé.
Réunion de deux graphes
Le processus de réunion de deux graphes mis en œuvre lors de l'exécution de l'étape S235 est décrit plus en détail ci-dessous. Ce processus permet de réunir les deux graphes de manière à obtenir un graphe unique représentatif d'un automate déterministe. Un tel processus est connu de l'état de la technique et décrit par exemple dans le document de John E. Hopcroft, Rajeev Motwani, Rotwani et Jeffrey D. Ullman, intitulé "Introduction to Automata Theory, Languages and Computability", (Addison- Wesley Longman Publishing Co., Inc., Boston, MA, 2000). Dans l'invention, ce processus connu est adapté afin de prendre en compte la sémantique utilisée dans l'exploitation et la définition de la liste de règles à traiter.
Un exemple simplifié de réunion de deux graphes est décrit ici par référence aux figures 5A à 5F. Dans cet exemple on considère une liste de contrôle d'accès comprenant les deux règles RA et RB suivantes, relatives à l'adresse source d'un paquet:
57.7.2.1 permit (RA)
57.7.*.* deny (R8) Les graphes A et B, dégénérés en liste, obtenus respectivement à partir des règles RA et RB, sont représentés à la figure 5A.
Dans le graphe A, la transition de l'état EA(0,0) vers l'état EA(1 ,0) n'est possible que lorsque la valeur du premier octet de l'adresse source est '57'; en d'autres termes la table de transition r£ (0 0) associée à l'état EA(0,0) définit une fonction d'association de l'ensemble [0...255] dans l'ensemble des identifiants d'état telle que: = 0
Figure imgf000023_0001
De la même manière, dans le graphe A, la transition de l'état EA(1 ,0) vers l'état
EA(2,0) n'est possible que lorsque la valeur du deuxième octet de l'adresse source est '7'; en d'autres termes la table de transition TE (1 0) associée à l'état EA(1 ,0) définit une fonction d'association de l'ensemble [0...255] dans l'ensemble des identifiants d'état telle que : (V) = 0
Figure imgf000023_0002
De même, la transition de l'état EA(2,0) vers l'état EA(3,0) n'est possible que lorsque la valeur du troisième octet de l'adresse source est '2'; en d'autres termes la table de transition TE (2,0) associée à l'état EA(2,0) définit une fonction d'association de l'ensemble [0...255] dans l'ensemble des identifiants d'état telle que : Γ£A (2>0) (V) = 0
Figure imgf000023_0003
Enfin, la transition de l'état EA(3,0) vers l'état EA(4,0) n'est possible que lorsque la valeur du quatrième octet de l'adresse source est '1 '; en d'autres termes la table de transition TE (3 0) associée à l'état EA(3,0) définit une fonction d'association de l'ensemble [0...255] dans l'ensemble des identifiants d'état telle que :
[Vv e [0] u[2...255] Γ£A (3>0) (V) = 0
{TEA (X0) (1) = E A (4, 0)
En ce qui concerne le graphe B, la transition de l'état E8(0, 0) vers l'état EB(1 ,0) n'est possible que lorsque la valeur du premier octet de l'adresse source est '57'; en d'autres termes la table de transition TE (00) associée à l'état EB(0,0) définit une fonction d'association de l'ensemble [0...255] dans l'ensemble des identifiants d'état telle que :
JVv e [0...56] u[58...255] rw) (v) = 0 [TE1 (o,o) (57) = EB (1,0)
De la même manière, dans le graphe B, la transition de l'état EB(1 ,0) vers l'état EB(2,0) n'est possible que lorsque la valeur du deuxième octet de l'adresse source est V; en d'autres termes la table de transition TE (1 0) associée à l'état EB(1 ,0) définit une fonction d'association de l'ensemble [0...255] dans l'ensemble des identifiants d'état telle que : = 0
Figure imgf000024_0001
Dans le graphe B, la transition de l'état EB(2,0) vers l'état EB(3,0) est possible quelle que soit la valeur du troisième octet de l'adresse source; en d'autres termes la table de transition TE e (2fi) associée à l'état EB(2,0) définit une fonction d'association de l'ensemble [0...255] dans l'ensemble des identifiants d'état telle que :
Vv e [0...255] TEB (2 0) (V) = EB(3,0)
Enfin, la transition de l'état EB(3,0) vers l'état EB(4,0) est possible quelle que soit la valeur du quatrième octet de l'adresse source; en d'autres termes la table de transition TE B (X0) associée à l'état EB(3,0) définit une fonction d'association de l'ensemble [0...255] dans l'ensemble des identifiants d'état telle que :
Vv e [0...255] TEB (3 0) (V) = EB(4,0)
Les graphes A et B obtenus, correspondant aux tables de transition qui viennent d'être décrites, sont représentés à la figure 5A. Afin de réunir le graphe A et le graphe B, on crée un état non déterministe E(O, O) en fusionnant les deux états initiaux EA(0,0) et EB(0,0) des graphes A et B, et on utilisation la notation suivante pour modéliser cette opération: E(0,0)=< EA(0,0); EB(0,0)>
L'état E(0, 0) est un état non déterministe en ce que dans le graphe obtenu ainsi, tel que représenté à la figure 5B, lorsqu'on est dans l'état E(0,0) on est soit dans l'état EA(0, 0), soit dans l'état EB(0,0).
L'état E(0,0) va être rendu déterministe en comparant et fusionnant les deux tables de transitions TE Λm et TE^m , associées aux états EA(0,0) et E8(0, 0) à partir desquels a été créé l'état E(0, 0), en une nouvelle table de transition TE(0 >0) . De cette manière, pour chaque valeur du premier octet de l'adresse source, une seule transition sera possible et non deux. En particulier, dans l'exemple décrit, lorsque le premier octet de l'adresse source prend la valeur '57', il existe une ambiguïté sur l'état suivant, puisque les deux tables de transition TE (0 0) et TE (0 0) définisse pour cette valeur un identifiant d'état différent: EA(1 ,0) pour la première table et EB(1 ,0) pour la seconde.
Le processus de fusion de deux tables de transitions TA et TB en une table de transition T est le suivant: on examine pour chacune des valeurs v de l'ensemble [0...255] les deux identifiant d'état TA(v) et TB(v) définis par TA et TB respectivement, et :
- si TA(V)=O alors T(v)=TB(v)
- sinon si TB(v)=0 alors T(v)=TA(v)
- sinon on crée un nouvel état T(v), non déterministe, résultant de la fusion des états TA(v) et TB(v), noté T(v)=< TA(v), TB(v)>. Dans le cas des tables de transitions TE ΛOfi) et r£g (0 0) décrites ci-dessus, on obtient, par fusion de ces deux tables, une table de transition TE(o,o) associée à l'état E(0, 0) telle que:
Vv G [0...56] u[58...255] TE(0 >0) (v) = 0
| r£(0>0) (57) - EQ., 0) =< EA (1, 0), EB (1, 0) >
Un nouvel état non déterministe E(1 ,0) est ainsi créé par fusion des deux états EA(1 ,0) et EB(1 ,0), ce qui est illustré à la figure 5C.
Le processus de réunion des graphes A et B se poursuit en traitant successivement tous les états non déterministes créés lors du traitement du précédent niveau de profondeur du graphe, et ceci jusqu'à atteindre le dernier niveau de profondeur du graphe. Dans le cas de l'exemple décrit, après avoir créé au niveau de profondeur 1 l'état E(1, 0) =< EA(l,0),EB(l,0) > , on exécute les opérations suivantes:
- on fusionne les tables de transitions TE Δlfi) et TE s{m en une table de transition T(1 ,0) associée à l'état Ε(1 ,0) telle que:
[Vv e [0...6] u[8...255] r£(1>0) (v) = 0
| r£(1>0) (7) = E(2, o) =< E4 (2, o), EB (2, o) > on fusionne les tables de transitions TE (2 0) et TE (2 0) en une table de transition TΕ(2,o) associée au nouvel état Ε(2,0), représenté à la figure 5D, créé par fusion des deux états ΕA(2,0) et ΕB(2,0), telle que: fVv e [0...1] u[3...255] TE(2 >0) (v) = E(3, 1) = EB (3, 0)
{TE(2 0) (2) - E(3, 0) =< E4 (3, 0), EB (3, 0) > l'état ΕB(3,0) étant noté Ε(3,1 ) dans le graphe résultant, comme représenté à la figure 5Ε. L'état Ε(3,1 ) possède la même table de transition que l'état ΕB(3,0).
Lorsqu'on traite le dernier niveau de profondeur d'un graphe, le processus de fusion de deux tables de transitions TA et TB en une table de transition T est modifié et dépend de la sémantique utilisé.
Dans le cas d'une sémantique de type "first match", il s'effectue de la manière suivante:
- si TA(v) ≠ 0 alors T(v)=TA(v) - sinon T(v)=TB(v)
En d'autres termes, on privilégie l'état associé à la première règle traitée, i.e. la table de transition TA.
Dans le cas d'une sémantique de type "last match", il s'effectue de la manière suivante: - si TB(v) ≠ 0 alors T(v)=TB(v)
- sinon T(v)=TA(v)
En d'autres termes, on privilégie l'état associé à la dernière règle traitée, i.e. la table de transition TB.
Par ce processus de fusion de graphes et tables de transition, la sémantique définie pour une liste de règles est prise en compte lors de la détermination d'une catégorie à affecter à un paquet, et ce sans traitement ni opération supplémentaire par rapport au simple parcours du graphe et application des tables de transitions.
Dans le cas de l'exemple décrit, on suppose que l'on utilise une sémantique de type "first match". Après avoir créé, au niveau de profondeur 3, l'état E(3, 0) =< EA (3, 0), EB (3, 0) > , on fusionne donc les tables de transitions TE (3 0) et
TE j3 0) en une table de transition TΕ(3,o> associée à l'état Ε(3,0) telle que:
[Vv G [0] u[2...255] r£(3>0)(v) = £(4,1) = EB(4,0) \ TE(χo)(l) = E(4,O) = EA(4,O)
On conserve donc les états finaux ΕA(4,0) et ΕB(4,0) en tant qu'états finaux Ε(4,0) et Ε(4,1 ) du graphe, représenté à la figure 5F, résultant de la fusion des graphes A et B, l'état final Ε(4,0) étant associé à l'action 'permit' et l'état final Ε(4,0) étant associé à l'action 'deny'.
Le graphe représenté à la figure 5F est utilisable pour trier un paquet selon les deux règles RA et RB définies ci-dessous, par utilisation du processus de tri décrit par référence à la figure 3.
Le procédé selon l'invention permet une classification efficace des paquets en différentes catégories, notamment un temps minimal et constant, indépendant du nombre de règles ou du paquet. Il permet de traiter les paquets de données octet par octet ou avec n'importe quelle taille de bloc de données qui soit appropriée compte tenu du processeur de données ou du dispositif de traitement de données utilisé. II s'applique à toute liste de règles définissant des critères de tri relatifs aux valeurs des champs de données à traiter.

Claims

REVENDICATIONS
1 . Procédé de tri de paquets de données en fonction d'une liste (L) ordonnée d'au moins une règle de tri (Rk), comprenant une étape de détermination pour chaque paquet de données à traiter d'une catégorie de paquet associée, une dite règle de tri (Rk) définissant d'une part un critère relatif à au moins un champ de données présent dans les paquets à trier et d'autre part une catégorie de paquet destinée à être associée à un paquet dont ledit au moins un champ de données contient une valeur vérifiant ledit critère, le procédé étant caractérisé en ce que la catégorie associée à un paquet est identifiée par une valeur de tri déterminée en un nombre prédéterminé NB d'itérations à partir d'une valeur de tri initiale (e0) et en fonction de NB blocs de données du paquet à traiter, l'ensemble desdits NB blocs de données incluant le ou les champs de données utilisés pour la définition des règles de ladite liste, la taille desdits blocs de données étant choisie parmi un ensemble de plusieurs tailles de bloc, une itération comprenant une étape de détermination d'une valeur de tri courante (e) à partir de la valeur de tri obtenue à l'itération précédente et de la valeur (x,) contenue dans le ieme bloc de données, l'ordre dans lequel lesdits blocs de données sont considérés étant prédéterminé.
2. Procédé selon la revendication 1 la valeur de tri courante (e) est déterminée lors de ladite itération par application, à la valeur (x,) du ieme bloc de données du paquet concerné, d'une fonction (Te) d'association prédéterminée, identifiée par la valeur de tri (e) obtenue à l'itération précédente.
3. Procédé selon la revendication 1 ou 2, dans lequel la catégorie de paquet affectée à un paquet prend en compte une sémantique associée à ladite liste.
4. Procédé selon l'une quelconque des revendications précédentes, dans lequel lors de la ieme itération, où i est un entier tel que l ≤ i ≤ NB , une valeur de tri courante (e) est déterminée par lecture, dans une table (Te) identifiée par la valeur de tri (e) obtenue à l'itération précédente, de la valeur de tri (Te(xi)) associée à la valeur (x,) du ieme bloc de données du paquet concerné.
5. Procédé selon l'une quelconque des revendications précédentes, dans lequel la taille de bloc est choisie supérieure ou égale à 2 bits.
6. Procédé selon l'une quelconque des revendications précédentes, comprenant une étape de génération à partir de ladite liste (L) d'un graphe orienté acyclique (DAG) à NB niveaux de profondeur, ledit graphe étant représentatif d'un automate à états, une dite valeur de tri identifiant un état dudit automate, ladite valeur de tri initiale identifiant l'état initial dudit automate, la table de transition (TE(p-i q)) d'un état (E(p- 1 ,q)) de niveau p-1 de l'automate, où p est un entier tel que l ≤ p ≤ NB , étant une fonction entre l'ensemble des valeurs possibles du peme bloc de données et l'ensemble des identifiants d'état de niveau p.
7. Procédé selon la revendication 6, comprenant une étape de construction d'un graphe dégénéré en liste à NB niveaux de profondeur à partir de chacune des règles de ladite liste, ledit graphe orienté acyclique (DAG) étant obtenu par réunion des graphes dégénérés construits, un graphe dégénéré en liste représentant un automate à (NB+1 ) états et NB transitions.
8. Procédé selon la revendication 7 dans laquelle la réunion des graphes dégénérés est effectuée en prenant en compte une sémantique associée à ladite liste.
9. Procédé selon la revendication 7 ou 8, dans lequel ladite réunion est un processus itératif, chaque itération comprenant une étape d'obtention d'un graphe courant par réunion d'un graphe dégénéré en liste avec le graphe obtenu à l'itération précédente et une étape de minimisation dudit graphe courant.
10. Procédé selon l'une quelconque des revendications 7 à 9, comprenant une étape consistant à traduire le critère de chacune des règles de tri de ladite liste en une liste de NB ensembles de valeurs de bloc de données, de telle sorte qu'un paquet de données vérifie ce critère si et seulement si pour chaque entier p tel que 1 ≤ p < NB , la valeur contenue dans le peme bloc de données de ce paquet est comprise dans le peme ensemble de valeurs, le peme ensemble de valeurs comprenant la ou les valeurs lesquelles une transition existe entre le (p-1 )eme état et le peme état de l'automate représenté par le graphe dégénéré en liste obtenu à partir de la règle concernée.
1 1. Programme informatique comprenant des instructions de code de programme pour l'exécution des étapes du procédé selon l'une quelconque des revendications 1 à 10 lorsque ledit programme est exécuté par un processeur de données.
12. Support d'enregistrement lisible par un processeur de données sur lequel est enregistré un programme comprenant des instructions code de programme pour l'exécution des étapes d'un procédé selon l'une quelconque des revendications 1 à 10.
13. Dispositif de tri de paquets de données en fonction d'une liste (L) ordonnée d'au moins une règle de tri (Rk), comprenant des moyens de détermination pour chaque paquet de données à traiter d'une catégorie de paquet associée, une dite règle de tri (Rk) définissant d'une part un critère relatif à au moins un champ de données présent dans les paquets à trier et d'autre part une catégorie de paquet destinée à être associée à un paquet dont ledit au moins un champ de données contient une valeur vérifiant ledit critère, le dispositif étant caractérisé en ce que lesdits moyens sont conçus pour déterminer une valeur de tri identifiant la catégorie associée à un paquet en un nombre prédéterminé NB d'itérations à partir d'une valeur de tri initiale (e0) et en fonction de NB blocs de données du paquet à traiter, l'ensemble desdits NB blocs de données incluant le ou les champs de données utilisés pour la définition des règles de ladite liste, la taille desdits blocs de données étant choisie parmi un ensemble de plusieurs tailles de bloc, une itération comprenant une étape de détermination d'une valeur de tri courante (e) à partir de la valeur de tri obtenue à l'itération précédente et de la valeur (x,) contenue dans le ieme bloc de données, l'ordre dans lequel lesdits blocs de données sont considérés étant prédéterminé.
14. Dispositif selon la revendication 13, dans lequel lesdits moyens sont conçus pour déterminer lors de la ieme itération, où i est un entier compris entre 1 et NB, une valeur de tri courante (e) est déterminée par lecture, dans une table (Te) identifiée par la valeur de tri (e) obtenue à l'itération précédente, de la valeur de tri (Te(xi)) associée à la valeur (x,) du ieme bloc de données du paquet concerné.
15. Dispositif selon la revendication 13 ou 14 comprenant des moyens de mise en œuvre des étapes d'un procédé selon l'une quelconque des revendications 2, 3 ou 5 à 10.
PCT/FR2008/052046 2007-11-16 2008-11-13 Procede et dispositif de tri de paquets Ceased WO2009068822A2 (fr)

Priority Applications (2)

Application Number Priority Date Filing Date Title
US12/741,860 US20100262684A1 (en) 2007-11-16 2008-11-13 Method and device for packet classification
CN200880116478A CN101861722A (zh) 2007-11-16 2008-11-13 用于对分组进行归类的方法和装置

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0759124 2007-11-16
FR0759124 2007-11-16

Publications (2)

Publication Number Publication Date
WO2009068822A2 true WO2009068822A2 (fr) 2009-06-04
WO2009068822A3 WO2009068822A3 (fr) 2009-07-23

Family

ID=39539648

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2008/052046 Ceased WO2009068822A2 (fr) 2007-11-16 2008-11-13 Procede et dispositif de tri de paquets

Country Status (3)

Country Link
US (1) US20100262684A1 (fr)
CN (1) CN101861722A (fr)
WO (1) WO2009068822A2 (fr)

Families Citing this family (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2935058A1 (fr) * 2008-08-13 2010-02-19 Inst Nat Rech Inf Automat Outil de verification informatique
US8447849B2 (en) * 2010-11-09 2013-05-21 Cisco Technology, Inc. Negotiated parent joining in directed acyclic graphs (DAGS)
US10599697B2 (en) 2013-03-15 2020-03-24 Uda, Llc Automatic topic discovery in streams of unstructured data
US10698935B2 (en) 2013-03-15 2020-06-30 Uda, Llc Optimization for real-time, parallel execution of models for extracting high-value information from data streams
US9600550B2 (en) * 2013-03-15 2017-03-21 Uda, Llc Optimization for real-time, parallel execution of models for extracting high-value information from data streams
US10204026B2 (en) 2013-03-15 2019-02-12 Uda, Llc Realtime data stream cluster summarization and labeling system
US10430111B2 (en) 2013-03-15 2019-10-01 Uda, Llc Optimization for real-time, parallel execution of models for extracting high-value information from data streams
CN108574679B (zh) * 2017-03-13 2021-03-30 华为技术有限公司 处理分组的方法和网络设备
WO2019133928A1 (fr) 2017-12-30 2019-07-04 Uda, Llc Modèles hiérarchiques, parallèles pour extraire en temps réel des informations de valeur élevée à partir de flux de données et système et procédé de création associés
DE102018221346A1 (de) * 2018-12-10 2020-06-10 Robert Bosch Gmbh Verfahren und Vorrichtung zum Klassifizieren von Datenpaketen
CN110837642B (zh) * 2019-11-14 2023-10-13 腾讯科技（深圳）有限公司 恶意程序分类方法、装置、设备及存储介质
CN112598385A (zh) * 2020-12-24 2021-04-02 Oppo（重庆）智能科技有限公司 物料选配方法及装置、计算机可读介质和电子设备
US20220217120A1 (en) * 2021-01-04 2022-07-07 Fastly Inc. Minimization optimizations for web application firewalls
CN113507631B (zh) * 2021-09-07 2021-11-12 深圳佳力拓科技有限公司 一种提高信息安全的数字电视信号发送方法和装置

Family Cites Families (27)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
SE513828C2 (sv) * 1998-07-02 2000-11-13 Effnet Group Ab Brandväggsapparat och metod för att kontrollera nätverksdatapakettrafik mellan interna och externa nätverk
US6282317B1 (en) * 1998-12-31 2001-08-28 Eastman Kodak Company Method for automatic determination of main subjects in photographic images
US6651096B1 (en) * 1999-04-20 2003-11-18 Cisco Technology, Inc. Method and apparatus for organizing, storing and evaluating access control lists
US7072863B1 (en) * 1999-09-08 2006-07-04 C4Cast.Com, Inc. Forecasting using interpolation modeling
US20020075805A1 (en) * 2000-09-22 2002-06-20 Narad Networks, Inc. Broadband system with QOS based packet handling
US7164678B2 (en) * 2001-06-25 2007-01-16 Intel Corporation Control of processing order for received network packets
US7443401B2 (en) * 2001-10-18 2008-10-28 Microsoft Corporation Multiple-level graphics processing with animation interval generation
US6891976B2 (en) * 2002-03-12 2005-05-10 Intel Corporation Method to decode variable length codes with regular bit pattern prefixes
US7224185B2 (en) * 2002-08-05 2007-05-29 John Campbell System of finite state machines
US7554980B1 (en) * 2002-10-18 2009-06-30 Alcatel Lucent Packet classification using relevance scoring
US20040177139A1 (en) * 2003-03-03 2004-09-09 Schuba Christoph L. Method and apparatus for computing priorities between conflicting rules for network services
US7251651B2 (en) * 2003-05-28 2007-07-31 International Business Machines Corporation Packet classification
US7146361B2 (en) * 2003-05-30 2006-12-05 International Business Machines Corporation System, method and computer program product for performing unstructured information management and automatic text analysis, including a search operator functioning as a Weighted AND (WAND)
US8284752B2 (en) * 2003-10-15 2012-10-09 Qualcomm Incorporated Method, apparatus, and system for medium access control
US7644085B2 (en) * 2003-11-26 2010-01-05 Agere Systems Inc. Directed graph approach for constructing a tree representation of an access control list
US7606263B1 (en) * 2004-03-30 2009-10-20 Extreme Networks, Inc. Packet parser
US7325183B2 (en) * 2004-07-21 2008-01-29 Hewlett-Packard Development Company, L.P. Error correction code generation method and apparatus
US8126870B2 (en) * 2005-03-28 2012-02-28 Sybase, Inc. System and methodology for parallel query optimization using semantic-based partitioning
US7373475B2 (en) * 2005-06-21 2008-05-13 Intel Corporation Methods for optimizing memory unit usage to maximize packet throughput for multi-processor multi-threaded architectures
CN100421369C (zh) * 2005-06-21 2008-09-24 西南交通大学 复数旋转码的迭代大数逻辑译码方法
US7784094B2 (en) * 2005-06-30 2010-08-24 Intel Corporation Stateful packet content matching mechanisms
US7853205B2 (en) * 2005-11-02 2010-12-14 Texas Instruments Incorporated Methods for improving transmission efficiency of control channels in communication systems
JP2010504018A (ja) * 2006-09-15 2010-02-04 コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ 自動パケットタグ付け
US20080089333A1 (en) * 2006-10-17 2008-04-17 Kozat Ulas C Information delivery over time-varying network topologies
SE531947C2 (sv) * 2006-11-03 2009-09-15 Oricane Ab Förfarande, anordning och system för flerfältsklassificering i ett datakommunikationsnätverk
US7933282B1 (en) * 2007-02-08 2011-04-26 Netlogic Microsystems, Inc. Packet classification device for storing groups of rules
US7782859B2 (en) * 2007-05-07 2010-08-24 Cisco Technology, Inc. Enhanced packet classification

Also Published As

Publication number Publication date
CN101861722A (zh) 2010-10-13
WO2009068822A3 (fr) 2009-07-23
US20100262684A1 (en) 2010-10-14

Similar Documents

Publication Publication Date Title
WO2009068822A2 (fr) Procede et dispositif de tri de paquets
US11237897B2 (en) Detecting and responding to an anomaly in an event log
EP0639013B1 (fr) Procédé et dispositif d&#39;analyse d&#39;informations contenues dans des structures de données
FR2891075A1 (fr) Circuit de memoire pour automate de reconnaissance de caracteres de type aho-corasick et procede de memorisation de donnees dans un tel circuit
US10691942B2 (en) Unsupervised land use and land cover detection
EP1030493B1 (fr) Procédé pour associer des références d&#39;acheminement à des paquets de données au moyen d&#39;une mémoire TRIE, et dispositif de traitement de paquets appliquant ce procédé
WO2010065418A1 (fr) Recherche de données basée sur un graphique
WO2021152262A1 (fr) Procede de surveillance de donnees echangees sur un reseau et dispositif de detection d&#39;intrusions
FR2842970A1 (fr) Procede de reconnaissance et d&#39;analyse de protocoles dans des reseaux de donnees
CN108028807A (zh) 用于在线自动识别网络流量模型的方法和系统
CA2297276C (fr) Procede et dispositif de reception et pretraitement de messages
EP3818676A1 (fr) Identification de protocole d&#39;un flux de données
WO2021260312A1 (fr) Procédé d&#39;ordonnancement de tâches dans un système de traitement, dispositif d&#39;ordonnancement associé
WO2004051965A1 (fr) Procede et systeme informatique pour declencher une action sur des donnees de communications numerique
Khosravian et al. QoS-aware service composition based on context-free grammar and skyline in service function chaining using genetic algorithm
FR3116917A1 (fr) Procédé de détermination de classifieurs pour la détection d’attaques dans un réseau de communication, dispositif de détermination associé
EP2225853B1 (fr) Moniteur de système de communication par messages amélioré
WO2018104557A1 (fr) Procédé d&#39;émission d&#39;un message, procédé de réception, dispositif d&#39;émission, dispositif de réception et système de communication associés
WO2005052812A1 (fr) Dispositif de memoire de type trie avec mecanisme de compression
WO2010018313A1 (fr) Outil de vérification informatique
FR3084183A1 (fr) Procede et dispositif de detection d&#39;anomalie
FR2892847A1 (fr) Procede de memorisation de donnees dans un circuit de memoire pour automate de reconnaissance de caracteres de type aho-corasick et citcuit de memorisation correspondant.
WO2025224129A1 (fr) Procédé de gestion d&#39;un ensemble de règles de compression de paquets de données
Alouf Parameter estimation and performance analysis of several network applications
EP2153359A1 (fr) Procede de classification d&#39;un ensemble de documents electroniques

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 200880116478.3

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 08854269

Country of ref document: EP

Kind code of ref document: A2

WWE Wipo information: entry into national phase

Ref document number: 12741860

Country of ref document: US

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 08854269

Country of ref document: EP

Kind code of ref document: A2