PROCESSING OF PACKETS IN A PACKET-SWITCHED COMMUNICATION NETWORK

Abstract

An apparatus and associated method for processing packets transmitted in a packet-switched communication network includes a sampling module that identifies amongst the received packets a plurality of samples distributed in a statistically uniform way amongst at least two non-overlapping sample sequences. Each sample sequence is then subjected to at least one identification rule, thereby identifying in the sample sequence at least one sub-sequence of samples fulfilling the at least one identification rule. The identification rule comprises a condition on the value of at least one identification field of the packets. Then, at least one parameter indicative of a behavior of the at least one sub-sequence of samples is provided.

Claims

1-12. (canceled)

13. A method for processing packets transmitted in a packet-switched communication network, said method comprising: a) identifying amongst said packets a plurality of samples distributed in a statistically uniform way amongst at least two sample sequences ; b) subjecting each sample sequence to at least one identification rule thereby identifying in said sample sequence at least one sub-sequence of samples fulfilling said at least one identification rule, said at least one identification rule comprising a condition on the value of at least one identification field of said packets; and c) providing at least one parameter indicative of a behaviour of said at least one sub-sequence of samples.

14. The method according to claim 13, wherein step a) includes identifying amongst the packets a plurality of samples distributed in a statistically uniform way amongst at least two non overlapping sample sequences.

15. The method according to claim 14, wherein at step a) said identifying is based on the values of a sampling signature calculated by applying a hash function to a predetermined mask of bits in each one of said packets, each one of said at least two sample sequences being associated with a respective possible value of said sampling signature.

16. The method according to claim 15, wherein at step a) said sampling signature is a portion of a hash calculated by applying said hash function to said predetermined mask of bits, a length of said portion being dynamically and retroactively adjusted.

17. The method according to claim 13, wherein step b) comprises subjecting at least one of said at least two sample sequences to a plurality of mutually exclusive identification rules, thereby providing a plurality of non-overlapping sub-sequence of samples.

18. The method according to claim 17, wherein said plurality of mutually exclusive identification rules are applied to said at least one of said sample sequences sequentially.

19. The method according to claim 13, wherein step b) comprises subjecting a first one of said at least two sample sequences to at least one first identification rule and subjecting a second one of said at least two sample sequences to at least one second identification rule, said at least one first identification rule and said at least one second identification rule being non mutually exclusive.

20. The method according to claim 13, wherein at step c) said at least one parameter comprises at least one cumulative parameter indicative of the behavior of said at least one sub-sequence of samples as a whole.

21. The method according to claim 13, wherein at step c) said at least one parameter comprises at least one individual performance parameter indicative of the behavior of a sample of said at least one sub-sequence.

22. An apparatus for a packet-switched communication network comprising: a sampling module configured to identify amongst received packets a plurality of samples distributed in a statistically uniform way amongst at least two sample sequences; at least two rule modules, each rule module being configured to subject a respective sample sequence to at least one identification rule thereby identifying in said sample sequence at least one sub-sequence of samples fulfilling said at least one identification rule, said at least one identification rule comprising a condition on the value of at least one identification field of said packets; and at least two analysis modules, each analysis module being configured to provide at least one parameter indicative of a behaviour of said at least one sub-sequence of samples identified in a respective sample sequence.

23. The apparatus according to claim 22, wherein the sampling module is configured to identify amongst received packets a plurality of samples distributed in a statistically uniform way amongst at least two non overlapping sample sequences.

24. A non-transitory computer-readable medium comprising instructions which that when executed by a computer, cause the computer to perform the steps of the method according to claim 13.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0047] The present invention will become clearer from the following detailed description, given by way of example and not of limitation, to be read with reference to the accompanying drawings, wherein:

[0048] FIG. 1 schematically shows an apparatus for a packet-switched communication network, configured to process the received packets according to an embodiment of the present invention;

[0049] FIG. 2 schematically shows the structure of a packet transmitted in a packet-switched communication network; and

[0050] FIG. 3 is a flow chart of the operation of the apparatus in FIG. 1, according to an embodiment of the present invention.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS OF THE INVENTION

[0051] FIG. 1 schematically shows an apparatus 100 for a packet-switched communication network, configured to process packets Pk transmitted through the network according to an embodiment of the present invention.

[0052] The apparatus 100 may be implemented within a node (e.g. a switch or a router) of the packet switched communication network. Alternatively, the apparatus 100 may be a stand-alone apparatus located at a node or on a link between two nodes of the packet-switched communications network. The apparatus 100 for example may be part of a management network configured to perform management tasks (including performance measurements) on the packet-switched communication network. In that case, the apparatus 100 basically is a measurement point of the management network and is preferably connected to a management server (not shown in the drawings) configured to cooperate with it (e.g. to gather performance parameters therefrom) for performing the management tasks.

[0053] Preferably, each packet Pk transmitted through the network comprises a header and a payload. The payload comprises user data. Preferably, the header comprises information for routing the packet Pk through the network. The header format depends on the protocol according to which the packets Pk are formatted.

[0054] By way of non limiting example, FIG. 2 shows the header H of a packet Pk formatted according to the known TCP (Transmission Control Protocol) over IPv4 (Internet Protocol Version 4). The header H comprises 40 bytes divided into 20 bytes for the IP header and 20 bytes for the TCP header. The TCP header in particular comprises the fields Source Port, Destination Port, Sequence Number, Acknowledge Number, Data Offset, RSV (reserved), Flags, Window Size, Checksum and Urgent Point.

[0055] Referring again to FIG. 1, the apparatus 100 preferably comprises a receiver RX, a sampling module SM, at least two rule modules RMk (k= 1, 2, ...) and at least two analysis module AMk (k= 1, 2, ...). All the modules of the apparatus 100 may be implemented by hardware, software or a combination thereof.

[0056] The receiver RX is preferably configured to receive a plurality of packets Pk transmitted through the packet-switched communication network.

[0057] The sampling module SM is preferably configured to identify amongst the received packets Pk a plurality of samples distributed in a statistically uniform way amongst at least two sample sequences. According to embodiments of the present invention, the at least two sequences of samples SSk (k= 1, 2, ...) are identified based on values of a sampling signature calculated by applying a hash function to a predetermined mask of bits in each received packet Pk. As it will be described in detail herein below, each sample sequence SSk is associated with a respective possible value Hk of the sampling signature (also termed herein below “sampling value”). Hence, if the sampling signature of a packet Pk is equal to the sampling value Hk associated with a certain sample sequence SSk (which will statistically happen for several received packets, due to collisions of the hash function), then the packet Pk is assigned to that sample sequence SSk.

[0058] Each rule module RMk (k=1, 2, ...) is preferably configured to receive a respective sample sequence SSk (k=1, 2) from the sampling module SM and to apply thereto at least one identification rule IRk.sup.nk (nk= 1, ...) comprising a condition on the value of at least one identification field of the packet Pk (preferably, the packet header). This allows identifying, in each sample sequence SSk, at least one sub-sequence of samples SSk.sup.nk (nk=1, ...) satisfying the condition expressed in the identification rule IRk.sup.nk (nk= 1, ...).

[0059] Each analysis module AMk (k= 1, 2, ...) is preferably configured to receive the at least one sub-sequence of samples SSk.sup.nk (nk=1, ...) identified in a respective sample sequence SSk (k=1, 2) and to provide, for each sample sub-sequence SSk.sup.nk, at least one parameter Pk.sup.nk (nk=1, ...) indicative of the behavior of the sample sub-sequence SSk.sup.nk. For example, an individual performance parameter (e.g. a timestamp) for each sample of the sub-sequence SSk.sup.nk and/or a cumulative performance parameter (e.g. a counter or a cumulative or average timestamp) for the sub-sequence SSk.sup.nk as a whole may be provided.

[0060] With reference to the flow chart of FIG. 3, the operation of the apparatus 100 according to an embodiment of the present invention will be described in detail.

[0061] As the measurement session begins, the receiver RX of the apparatus 100 preferably starts receiving the packets Pk (step 300).

[0062] For example, if the apparatus 100 is implemented at the receiving side of a node, the packets Pk are those received at one or more input ports of the node. If the apparatus 100 is implemented at the transmitting side of a node, the packets Pk are those transmitted by one or more output ports of the node. If instead the apparatus 100 is implemented on a link, the packets Pk are those transmitted along the link (in one direction or both, if the link is bidirectional).

[0063] If the apparatus 100 has a pass-through configuration (namely, the apparatus 100 is deployed on the path of real traffic transmitted in the packet-switched network), the packets Pk are the ones actually transmitted through the network. Otherwise, the packets Pk may be copies of the actually transmitted ones, for example generated by a mirroring technique.

[0064] As a packet Pk is received, the sampling module SM preferably calculates its sampling signature (step 301), by applying a predetermined hash function to a predetermined mask of bits in the packet Pk, preferably in the packet header.

[0065] The sampling signature calculated by the sampling module SM for the received packet Pk preferably has a statistically uniform distribution amongst its possible values, meaning that the probability that the sampling signature is equal to a certain value is the same for all its possible values. The sampling signature may be calculated e.g. as provided by T. Zseby et al. “Sampling and Filtering Techniques for IP Packet Selection”, RFC 5475, March 2009. For example, the hash function may be the known IPSX (IP Shift-XOR) or the known BOB hash function.

[0066] Preferably, the mask of bits to which the hash function is applied depends on the packet format, namely on the protocol according to which the packets Pk are formatted. In order to ensure a statistically uniform distribution of the sampling signature amongst its possible values - and hence of the packets Pk amongst the sequences of samples SSk (k= 1, 2, ...) - the hash function is preferably applied to a mask of bits whose values are as entropic as possible amongst the packets Pk, meaning that the probability that different packets Pk have the bits of the selected mask with the same values is as low as possible. It is therefore preferable avoiding bits of header fields whose values are always or often the same, such as for instance the TCP port field whose value is often 80. For the same reason, if the apparatus 100 is located at an intermediate node of a tunnel carrying the packets Pk, the tunnel header shall be avoided, since the packets Pk have all the same tunnel header.

[0067] If a consistent identification of the sequences of samples SSk (k= 1, 2, ...) at different apparatuses implemented in the network is desired, the hash function is preferably applied to a mask of bits whose values are invariant through the path of the packets Pk. This way, each apparatus applying the hash function to the mask of bits of a certain packet Pk will obtain the same sampling signature value for that packet. In this case it is therefore preferable avoiding bits of header fields whose values are changed at each node, such as for instance the TTL field and CheckSum of the IP header. If NAT (Network Address Translation) techniques are used, also the bits of the IP addresses shall be avoided.

[0068] For example, if the packets Pk are formatted according to the above mentioned TCP over IPv4 protocol, the mask of bits may comprise bits of one or more of the following fields: Identification, Flags, Fragment Offset, Source Address, Destination Address, Sequence Number and Total Length.

[0069] As it will be discussed in detail herein below, the sampling signature may be either the whole calculated hash or a portion thereof.

[0070] The sampling module SM then preferably compares the value of the calculated sampling signature with at least two predefined different sampling values Hk (k= 1, 2, ...), each sampling value being associated with a respective sample sequences SSk (k= 1, 2 ...) to be identified (step 302).

[0071] If the value of the calculated sampling signature is different from all the sampling values Hk (k= 1, 2, ...), then the sampling module SM preferably ignores the packet Pk and considers the next received packet Pk.

[0072] Otherwise, if the value of the calculated sampling signature is equal to one of the sampling values Hk (k= 1, 2, ...), the sampling module SM then preferably identifies the packet Pk as a sample of the sample sequence SSk associated with that sampling value (step 303). This way, by repeating steps 300-303 on each received packet Pk, the sampling module SM basically identifies amongst the received packets Pk at least two sample sequences SSk (k= 1, 2, ...). Within each sample sequence, all the samples have sampling signature equal to the sampling value Hk associated with that sequence. As the sampling values Hk are different for different sample sequences, each sample sequence will include only packets that are not included in the other sample sequence(s), accordingly the sample sequences will be mutually non overlapping.

[0073] It shall be noticed that, if several apparatuses similar to apparatus 100 are deployed on the path of the packets Pk and their sampling modules are all configured the same way (namely, same hash function, same mask of bits to which the hash function shall be applied and same sampling values Hk), all the apparatuses identify in the received packets Pk the same sample sequences (except possible packets losses or reception sequence errors involving the measurement samples).

[0074] Each sample sequence SSk (k= 1, 2, ...) identified by the sampling module SM is then forwarded to a respective rule module RMk (k= 1, 2, ...). Each rule module RMk preferably applies to the respective sample sequence SSk at least one identification rule IRk.sup.nk (nk= 1, ...) thereby identifying at least one sub-sequence of samples SSk.sup.nk (nk=1, ...) (step 304).

[0075] Each identification rule IRk.sup.nk preferably comprises at least one condition on the value of at least one identification field of the packets Pk, preferably of the packet header.

[0076] When a rule module RMk receives a sample of its sequence SSk from the sampling module SM, at step 304 it preferably applies thereto its identification rule(s) IRk.sup.nk. The rule module RMk concludes that a sample belongs to a sub-sequence SSk.sup.nk if the corresponding identification rule IRk.sup.nk is satisfied by the value(s) comprised in its relevant identification field(s).

[0077] In case a rule module RMk is configured to apply at least two identification rules IRk.sup.nk (nk= 1, 2, ...), such identification rules IRk.sup.nk are preferably mutually exclusive, so that the corresponding sample sub-sequences SSk.sup.nk are non overlapping. For example, the identification rules IRk.sup.nk applied by the rule module RMk may contain different, mutually exclusive conditions on the value(s) of a same identification field or combination of identification fields of the packet. This way, the identification rules IRk.sup.nk may be applied sequentially (e.g. according to the known ACL technique) by the rule module RMk.

[0078] On the other hand, the identification rule(s) applied by different rule modules RMk preferably pertain to different levels or dimensions of the traffic, so that they may be non mutually exclusive. For example, different rule modules RMk may apply identification rule(s) containing conditions on the value(s) of different identification fields or combinations of identification fields of the packet.

[0079] FIG. 1 shows an exemplary situation wherein the sampling module SM provides two sample sequences SS1 and SS2, identified based on two different values H1 and H2 of the sampling signature. As shown in FIG. 1, each sample sequence SS1, SS2 is sent to a respective rule module RA1, RA2.

[0080] The rule module RA1 applies e.g. 100 mutually exclusive identification rules IR1.sup.n1 (n1= 1, 2, ....100) on the value of the Source Address field, each identification rule being of the type Source Address = SAn1 (n1= 1, 2.... 100). This way, the rule module RA1 identifies 100 non overlapping sample sub-sequences SS1.sup.n1 (n1= 1, 2, ...100).

[0081] The rule module RA2 may instead apply e.g. 9 mutually exclusive identification rules IR2.sup.n2 (n2= 1, 2, ...9) on the value of the DSCP field, each identification rule being of the type DSCP = CoSn2 (n2= 1, 2.... 9). This way, the rule module RA2 identifies 9 non overlapping sample sub-sequences SS2.sup.n2 (n2= 1, 2, ...9).

[0082] Though the identification rules IR1.sup.n1 and IR2.sup.n2 are not mutually exclusive (a packet Pk may have both Source Address equal to anyone of the values SAn1 and at the same time DSCP field equal to anyone of the values CoSn2), nonetheless the sub-sequences SS1.sup.n1 (n1= 1, 2.... 100) do not overlap with the sub-sequences SS2.sup.n2 (n2= 1, 2, ...9), because the rule modules RA1, RA2 operate on non overlapping sample sequences SS1, SS2.

[0083] As another example (not depicted in the drawings), the rule module RA1 could apply a single identification rule IR1.sup.n1 (n1=1) e.g. on the value of the Source Address field, this identification rule being of the type Source Address = SA. This way, the rule module RA1 identifies a single sample sub-sequence SS1.sup.n1 (n1 =1).

[0084] he rule module RA2 could instead apply e.g. 100 mutually exclusive identification rules IR2.sup.n2 (n2= 1, 2, ...100) on the values of the Source Address field and Destination Address field, each identification rule being of the type Source Address = SA AND Destination Address = DAn2 (n2= 1, 2.... 100). This way, the rule module RA2 identifies 100 non overlapping sample sub-sequences SS2.sup.n2 (n2= 1, 2, ... 100).

[0085] Though the identification rules IR1.sup.n1 and IR2.sup.n2 are not mutually exclusive (each packet Pk whose Source Address fulfils the identification rule IR1.sup.n1 could also fulfil any of the identification rules IR2.sup.n2), nonetheless the sub-sequence SS1.sup.n1 does not overlap with the sub-sequences SS2.sup.n2 (n2= 1, 2, ...100), because also in this case the rule modules RA1, RA2 operate on non overlapping sample sequences SS1, SS2.

[0086] Referring again to the flow chart of FIG. 3, each analysis module AMk (k=1, 2, ...) preferably receives the at least one sub-sequence of samples SSk.sup.nk (nk=1, ...) identified in a respective sample sequence SSk (k=1, 2, ...) and provides, for each sample subsequence SSk.sup.nk , at least one parameter Pk.sup.nk (nk=1, ...) indicative of the behavior of the sample sub-sequence SSk.sup.nk (step 305).

[0087] For example, the parameter Pk.sup.nk provided for the sample subsequence SSk.sup.nk may comprise an individual performance parameter (e.g. a timestamp) for each sample of the sub-sequence SSk.sup.nk, and/or a cumulative performance parameter (e.g. a counter or a cumulative or average timestamp) for the sub-sequence SSk.sup.nk as a whole.

[0088] With reference to the exemplary implementation of FIG. 1, the analysis module AM1 preferably receives the sub-sequences SS1.sup.n1 (n1= 1, 2, ... 100) identified by the rule module RM1 in the sample sequence SS1, and provides at least one parameter P1.sup.n1 (n1= 1, 2, ... 100) for each sub-sequence SS1.sup.n1 (n1= 1, 2, ... 100).

[0089] Similarly, the analysis module AM2 preferably receives the sub-sequences SS2.sup.n2 (n2= 1, 2, ... 9) identified by the rule module RM2 in the sample sequence SS2, and provides at least one parameter P2.sup.n2 (n2= 1, 2, ... 9) for each sub-sequence SS2.sup.n2 (n2= 1, 2, ... 9).

[0090] Such parameters Pk.sup.nk (k=1, 2, ... and nk=1, ...) may then be sent e.g. to a management server (not shown in the drawings), either periodically or at the end of the measurement session. The management server will then use them for performing a statistical analysis of the behaviour (e.g. a performance measurement, such as a packet loss measurement, a delay measurement or a jitter measurement) of each sample sub-sequence SSk.sup.nk (k=1, 2, ... and nk=1, ...).

[0091] Therefore, an analysis of the behaviour of at least partially overlapping packet flows (e.g. a multilevel or multidimensional performance measurement) may be advantageously performed, by identifying amongst all the received packets Pk a number of sample sequences SSk (k=1, 2, ...) equal to the number of levels or dimensions to be investigated, and then by applying to each sample sequence SSk at least one identification rule IRk.sup.nk pertaining to a respective level or dimension.

[0092] This advantageously results in a reduced number of identification rules to be implemented. As described above, indeed, the mere application of the ACL technique to all the incoming packets for providing performance measurements in e.g. 2 dimensions of the traffic (per-client and per-CoS) would require the implementation of a list of MxZ identification rules (M being the number of mutually exclusive rules in the per-client dimension and Z being the number of mutually exclusive rules in the per-CoS dimension). According to the invention embodiment, instead, amongst all the incoming packets Pk two mutually non overlapping sample sequences SS1, SS2 (one for each dimension, namely client and CoS) are firstly identified based on 2 different values of the sampling signatures; then one sample sequence SS1 is subjected to M mutually exclusive identification rules IR1.sup.n1 (n1= 1, 2, ... M) in the per-client dimension and the other sample sequence SS2 is subjected to Z mutually exclusive identification rules IR2.sup.n2 (N2= 1, 2, ... Z) in the per-CoS dimension. This requires implementation of M+Z identification rules, which in general is much lower than MxZ. For example, if M=100 and Z=9, 109 identification rules are required instead of 900.

[0093] Furthermore, advantageously, no recombining or merging of the parameters Pk.sup.nk provided for the sub-sequences SSk.sup.nk is needed to provide an analysis of the traffic behavior at the desired level or in the desired dimension. By providing a sample sequence SSk for each level or dimension to be investigated, indeed, the parameter(s) Pk.sup.nk relating to the sub-sequence(s) SSk.sup.nk obtained from each sample sequence SSk already pertain to the desired level or dimension to be investigated. Hence, the parameter(s) Pk.sup.nk may be used directly for providing an analysis of the traffic behaviour (e.g. a performance measurement) at the desired level or dimension, without the need to carry out any additional merging or combination operation.

[0094] The method of the invention is accordingly very efficient from the computational point of view.

[0095] It shall be noticed that, since whether a packet Pk will be assigned to a certain sample sequence SSk depends on the value of its hashgenerated sampling signature, it is not possible to know a priori which packets Pk will be part of each sample sequence SSk. However, use of the hash-calculated sampling signature distributed in a statistically uniform way amongst its possible values guarantees that the packets Pk identified as samples are distributed in a statistically uniform way amongst the various sample sequences SSk and, therefore, that the composition of each sample sequence SSk statistically reflects the composition of the whole incoming traffic.

[0096] Hence, subjecting each sample sequence SSk to respective identification rule(s) IRk.sup.nk advantageously provides sample sub-sequences SSk.sup.nk whose behavior (e.g. in terms of performance, in particular packet loss, delay and jitter) statistically reflect that of corresponding packet flows and sub-flows which would be obtained by directly applying the same identification rule(s) to the whole incoming traffic. The parameters Pk.sup.nk provided for each sample subsubsequence SSk.sup.nk therefore statistically reflect the actual behaviour of the incoming traffic.

[0097] The method of the present invention is accordingly applicable not only to performance measurements but, more generally, also to any situation wherein a statistical analysis of the traffic is desired.

[0098] Though the embodiment described above provides for identifying the sample sequences based on the value of a hash-calculated sampling signature, this is not limiting. The sampling module SM may indeed distribute the packets amongst the sample sequences in a statistically uniform way by applying other techniques. For example, each time a packet is received the sampling module SM could generate a random number e.g. between 1 and 100, having a uniform probability density function. Then, if for example two sample sequences SS1, SS2 shall be identified, the sampling module SM may compare the random number with a threshold equal to 50. If the random number is lower than 50, the packet is assigned to the sample sequence SS1, otherwise it is assigned to the sample sequence SS2. The uniform density probability function of the random number ensures that the packets Pk are distributed between the sample sequences SS1, SS2 in a statistically uniform way. Differently from the hash-calculated sampling signature technique, the random number technique can not ensure that different apparatuses implemented on the path of the packets Pk perform a consistent identification of the sample sequences SS1, SS2. Hence, the random number technique may be applied when the statistical analysis of the traffic behaviour to be performed does not require combining or comparing parameters provided by different apparatuses.

[0099] According to a variant, the sampling module SM may also calculate an identification signature for each packet Pk identified as part of any sampling sequence SSk, as described by WO 2017/071779A1 in the name of the same Applicant. This allows to properly correlate performance parameters relating to a same sample and provided by different apparatuses, also in case of reception sequence errors involving samples of a same subsequence.

[0100] Further, as mentioned above, the sampling signature may be either the whole calculated hash or a portion thereof. In this latter case, the length of the hash portion used as sampling signature for the purpose of identifying the samples amongst the received packets Pk may be dynamically adjusted, as described by WO 2018/072828 A1 in the name of the sample Applicant. This allows controlling the number of samples by dynamically adapting the sampling rate to compensate possible fluctuations of the packet rate of the received packets Pk.