Estimation method for loss rates in a packetized network

The invention relates to methods for monitoring the performance of networks, and more particularly to the determination of packet loss rates.

The performance of data networks is sensitive to the loss of packets. To be able to optimize the performance of a network, the operator needs to have information about packet losses on various links of the network. For example, one major reason for packet losses is buffer overflow. By identifying and quantifying the loss rate attributable to buffer overflow at a node of the network, the network operator may be able to apply policies that relieve the traffic load at the overloaded link or overloaded node of the network.

The danger of overloads that lead to packet loss has become especially acute in 3G and 4G wireless networks. One reason is that on such networks there is competition for network resources among data applications, voice applications, and video and other applications, each of which has different bandwidth requirements and different delivery modes. This competition is exacerbated by the limited bandwidth available for content delivery over the air interface, and by the high volume of signaling overhead that is typically required to enable wireless communication.

As a consequence, there is an especially great need to monitor packet losses in advanced wireless networks. Particular advantage would be gained by monitoring most or all links between, e.g., the GGSN of a GPRS-supported network such as a W-CDMA mobile telecommunications network and each of the base stations with which the GGSN is associated. To do this by conventional methods, however, would require a monitoring device to be deployed on each of the links that are to be monitored. Because advanced wireless networks, among others, may have hundreds, or even thousands, of such links, such a wide deployment of monitoring devices is not usually feasible.

Therefore, there remains a need for methods of monitoring packet losses that can be deployed from a limited number of locations on the network and still obtain information on the loss rates on many individual links.

We have discovered such a method. Our method involves collecting data on downstream packet losses at a single point in a network, and from the collected data, estimating packet loss rates on at least two subnetworks downstream of the collection point, wherein the subnetworks differ by at least one link.

In particular embodiments, the data collection is performed by a dedicated hardware monitoring device. In some embodiments, such a device is deployed on the first link below the GGSN (GPRS Support Node) of a GPRS core network.

In particular embodiments, the collected data relate to packet losses on the core network, or the portion thereof, extending from the monitoring point to a plurality of base stations, and in some embodiments even extending to the mobile stations supported by the base stations.

FIG. 1 is a simplified schematic diagram of a portion of a typical wireless communication network having a GPRS core network.

FIG. 2 is a view of a portion of the network of FIG. 1 , modified to show the inclusion of a tap for practicing the invention in an exemplary embodiment.

FIG. 3 is an example of a tree graph.

FIG. 4 is a flow chart of a procedure useful in implementing the invention, in an exemplary embodiment. FIGS. 3 and 4 should be read together.

FIG. 5 is a detail of the tree graph of FIG. 3 .

FIG. 6 is a flow chart of a procedure useful in implementing the invention, in an exemplary embodiment. FIGS. 5 and 6 should be read together.

FIG. 7 is a further view of the tree graph of FIG. 3 .

Schematically illustrated in FIG. 1 is a portion of a typical wireless communication network having a GPRS core network. Proceeding in a downstream direction, it will be seen that from the Internet 10 , there are links to GGSN 20 , from the GGSN there are links to multiple SGSNs (Serving GPRS Support Nodes) 30 , from each SGSN there are links to multiple RNCs (Radio Network Controllers) 40 , and from each RNC there are links to multiple base stations 50 . Each base station may be in contact with multiple mobile stations 60 .

It will be evident from FIG. 1 that from the GGSN down at least to the base stations, the various network elements form the nodes of a tree graph rooted at the GGSN, and the links from each element to the elements below it form the vertices of the tree graph.

Our method can be applied to any packetized communication network that may be represented by a tree graph. As noted above, wireless GPRS networks such as the network of FIG. 1 are one example where our method is especially useful. However, applications of our method are not limited to GPRS networks or to wireless networks.

Our method may be deployed on a computer or digital processor running at a network node such as the GGSN or other node of FIG. 1 , or it may be deployed on a dedicated machine. The machine on which it is deployed may be, e.g., a general-purpose machine operating under software instructions, or a special-purpose machine operating under the control of hardware or firmware.

In some embodiments, the machine on which the message is deployed will collect packet loss information by diverting a copy of packet traffic through a tap installed at an intermediate point on a link. For example, FIG. 2 shows a portion of the network of FIG. 1 , in which tap 70 has been added on the link between GGSN 20 and SGSN 80 , and monitoring device 90 receives copied and diverted packets from tap 70 . Monitoring devices that can gather information from diverted packets and have the necessary computational power to support implementations of our method are well known and need not be described here in detail.

In general, tap 70 may be situated at any point at or below the GGSN, because at such locations it will generally be able to obtain the network topology from signaling information. The monitoring device needs to know the topology of the tree network downstream of its location in order to be able to infer packet loss rates according to the method to be described.

We will now describe an illustrative embodiment of our method with reference to FIGS. 3 and 4 . FIG. 3 shows a generalized example of a tree graph having five levels. FIG. 4 is a flowchart of the steps of a procedure that we will refer to, below, as Algorithm 1.

Turning back to FIG. 3 , it should be noted that the number of levels in the tree graph is arbitrary and a five-level graph has been selected solely for purposes of illustration. In some practical applications, our method will be applied to networks whose tree graph has fewer than five levels. For example, the method may usefully be applied to the graph rooted at the GGSN of FIG. 1 . If the leaves of the graph are considered to be the mobile stations, the graph will have five levels, whereas if the leaves are considered to be base stations, the graph will have only four levels.

It should be noted in this regard that in at least some implementations, it will be desirable to include the mobile stations as the leaves of the graph, but the mobile stations may be so numerous that it is not computationally feasible to consider individual air-interface links. In such cases, it will be advantageous to group the mobile stations into lumped, equivalent nodes in such a way that each base station serves at least two equivalent nodes. Although such an approach does not yield loss rates on individual air links, it will often provide useful information about loss rates as averaged over populations of air links.

In FIG. 3 , the root node is labeled n 0 . We refer to the leaves of the tree graph, such as nodes n 4 and n 6 , as “end nodes.” We refer to all nodes between the root and the end nodes as “intermediate nodes.” Examples of intermediate nodes are nodes n 2 , n 3 , and n 5 .

One important observation we have made is that information collected at one link of the network, relating to losses of correlated pairs of packets, may be probative of loss rates on other, downstream links of the network. To put this observation into practice, we have defined a “pair” as two packets, destined for different end nodes, that were both transmitted from the root node within a time interval δ. The value of δ may be specified by the operator, or it may be determined adaptively. In many networks, there will be a high correlation between the losses of packets transmitted sufficiently close in time, not least because if one packet is dropped due to buffer overflow, a packet following a short time later is likely to meet the same fate. Although useful values for δ will depend on the properties of the specific network of interest, typical values in a W-CDMA network could lie in the range 50-100 ms.

There are currently available monitoring devices that can determine the packet loss rate, i.e., the fraction of packets that are lost over a suitable time-averaging interval, on the end-to-end path from the monitoring point to a network element that serves as a leaf node. One such device is the Alcatel-Lucent 9900 Wireless Network Guardian, which is available from Alcatel-Lucent Inc., having an office at 600 Mountain Avenue, Murray Hill, N.J. When such a device is situated, for example, at or just below the GGSN of a GPRS core network, it can readily measure the end-to-end packet loss rates between the GGSN and the mobile stations (individually or as grouped into equivalent nodes) served by the base stations associated with that GGSN.

Accordingly, one quantity that is measurable in many networks is the end-to-end packet loss rate F i from a root node n 0 to an end node n i . Given two distinct end nodes n i , n j , another often-measurable quantify is the probability F i,j;δ that a packet destined for n i and a packet destined for n j will both be lost, given that the two packets belong to a pair as defined above.

Another quantity that is measurable in many networks is the fraction W ij of all packet pairs (counted over a suitable averaging period) transmitted from the root node that are destined for a given pair of end nodes n i , n j . That is, for all end nodes n i , n j , i≠j, let N ij represent the total count, over the averaging period, of packet pairs destined for (n i , n j ). Then in general, W ij =N ij /ΣN lm , wherein the summation (i.e., over indices l, m) is taken over all pairs of distinct end nodes. For implementations of the method to be described below, the summation is taken only over all pairs of distinct outer nodes, which are defined below.

We will now describe a procedure, referred to herein as Algorithm 1, for estimating the packet loss rate f 0i from a root node n 0 to a selected intermediate node n j . Thus, for example, Algorithm 1 might be applied to estimate the loss rate from the root node to node n 2 of FIG. 3 , i.e., the loss rate over the path that is the concatenation of paths l 1 and l 2 . We refer to the selected intermediate node as the “inner node”. Those skilled in the art will understand that the precise process steps are subject to numerous variations, and as described are merely illustrative.

There is a criterion that an intermediate node must meet in order for it to be eligible as an inner node. To be eligible, the selected intermediate node must be a root node relative to at least two end nodes via distinct branches that intersect at the selected node. For example, node n 2 of FIG. 3 is a branch point of the tree graph. One branch goes to node n 3 and from there has two sub-branches, one of which terminates at end node n 4 . The other branch goes to node n 5 and then terminates at end node n 6 .

We also introduce here the concept of an outer node, which was mentioned above. Given a selected inner node, a pair of end nodes are outer nodes if: (1) the selected inner node is a root relative to the selected end nodes, and (2) at least two distinct branches intersect at the selected inner node, each of which terminates at a respective one of the selected end nodes. In the example of FIG. 3 , n 4 and n 6 qualify as outer nodes (relative to selected inner node n 2 ).

Turning now to FIG. 4 , the first step 110 of the procedure is to obtain from measurements: The end-to-end loss rate F p from the root node n 0 to each possible outer node n p , the pair-loss rate F p,p′;δ from the root node n 0 to each possible pair of outer nodes n p , n p′ , and the pair fractions W p,p′ for all possible pairs n p , n p′ of outer nodes. (As noted elsewhere in this description, in the event that there is a large number of possible outer nodes, computational economy can be achieved by artificially grouping pluralities of end nodes into lumped, equivalent nodes.)

The next step 120 of the procedure is to select an inner node n i . In the example of FIG. 3 , node n 2 is selected as the inner node.

The next step 130 is to select two end nodes n j , n k which qualify as outer nodes. The next step 140 is to compute an estimate of the packet loss rate f 0i from the root node n 0 to the selected inner node n i using the information obtained in step 110 . Formulas for making the computation are provided below. In the example of FIG. 3 , the loss rate f 02 is estimated from the end-to-end loss rates F p , the pair fractions W lm , and F 4,6;δ .

We will now describe a procedure, referred to here as Algorithm 2, for estimating the packet loss rate on a path P jk from a selected intermediate node n j to a selected intermediate node n k lying below n j in the tree graph. In order for the selected intermediate nodes n j and n k to be eligible for application of Algorithm 2, each of them must qualify as an inner node relative to at least one pair of outer nodes, as defined above in connection with Algorithm 1. Algorithm 2 will be described with reference to FIGS. 5 and 6 . FIG. 5 shows the tree graph of FIG.3 with further detail. FIG. 6 is a flowchart of the steps of Algorithm 2. Those skilled in the art will understand that the precise process steps are subject to numerous variations, and as described are merely illustrative.

In the example of FIG. 5 , the packet loss rate will be estimated on the path P 13 from node n 1 to node n 3 . With reference to FIG. 5 , this path may be described as the concatenation of links l 2 and l 3 .

Turning now to FIG. 6 , the first step 210 of the procedure is to select the intermediate nodes n j , n k . In the example of FIG. 5 , as noted, the selected intermediate nodes are n 1 , n 3 .

The next step 220 is to compute the loss rates f 0j and f 0k , using Algorithm 1. In the example of FIG. 5 , the computed loss rates are f 01 , i.e., the loss rate on link l 1 , and f 03 , i.e., the loss rate on the path that is the concatenation of links l 1 , l 2 , and l 3 .

The next step 230 is to compute the loss rate f jk between the selected intermediate nodes from the rates obtained in step 220 . In the example of FIG. 5 , the loss rate f 13 is the loss rate on the path that is the concatenation of links l 2 , and l 3 .

It will be evident from FIG. 5 , that step 230 may be thought of as decomposing a three-level path n 0 -to-n 1 -to n 3 into a pair of two-level paths n 0 -to-n 1 and n 0 -to-n 3 , in order to obtain the packet loss rate on the difference between the two paths resulting from the decomposition.

The formula used in step 230 is f jk =(f 0k −f 0j )/(1−f 0j ). In the example of FIG. 5 , the computation is f 13 =(f 03 −f 01 )/(1−f 01 ). In applying the formula, negative values of f jk are rounded up to zero.

By repeatedly applying Algorithms 1 and 2, it is readily achievable to estimate the packet loss rate on every qualifying link. A link is qualifying if (a) it terminates on an end node, or (b) it terminates on an eligible inner node.

For example, we will now describe with reference to FIG. 7 a procedure for estimating the packet loss rate on each link of a path from root node n 0 to end node n 4 .

The end-to-end loss rate from n 0 to n 4 is measurable. Consequently, f 04 is taken as F 4 .

The end-to-end loss rate f 03 from n 0 to the intermediate node n 3 is computed by Algorithm 1 using the measured values of the end-to-end loss rates from the root node n 0 to nodes n 4 and n 7 and the measured value of the pair-loss probability F 4,7;δ . Then Algorithm 2 is used to compute the loss rate f 34 on link l 4 .

Algorithm 1 is then used to compute the loss rate f 02 from n 0 to intermediate node n 2 using the measured values of the end-to-end loss rates from the root node n 0 to nodes n 4 and n 6 and the measured value of the pair-loss probability F 4,6;δ . Algorithm 2 is then used to compute the loss rate f 23 on link l 3 , using the determined values of f 02 and f 03 .

Algorithm 1 is then used to compute the loss rate F 01 from n 0 to n 1 using the measured values of the end-to-end loss rates from n 0 to n 4 and a further node n 8 (not identified in the figure) and the measured value of the pair-loss probability F 4,8; δ , Algorithm 2 is then used to compute the loss rate f 12 on link 1 2 from f 01 and f 02 .

The loss rate from n 0 to n 1 , i.e., the loss rate on link l 1 , is set to rate f 01 , which has been computed using Algorithm 1.

Mathematical Details

Let n k be a selected inner node, and let n i and n j be corresponding outer nodes. Let f 0k be the packet loss rate from the root node n 0 to node n k , and let f ki and f kj be the respective packet loss rates from n k to n i , and from n k to n j . Under the assumptions that the two packets in a packet pair will experience the same loss event, i.e., either both will succeed or both will fail to arrive, and that loss events on different links are independent, it can be shown that

F ij −F i F j =f 0k (1− f 0k )(1− f ki f kj )

and hence that

∑ i ≠ j ⁢ W ij ⁡ ( F ij - F i ⁢ F j ) = f 0 ⁢ ⁢ k ⁡ ( 1 - f 0 ⁢ ⁢ k ) ⁢ ( 1 - ∑ i ≠ j ⁢ W ij ⁢ f ki ⁢ f kj ) ,

the sum being taken over all possible pairs of outer nodes.

Now define the weighted average F pair of the probability that both packets of the pair will be lost by

F pair = ∑ i ≠ j ⁢ W ij ⁢ F ij ,

where the sum is taken over all possible pairs of outer nodes. Since f ki cannot be greater than F i , it follows that

It follows that f 0k has lower and upper bounds as expressed by

According to a useful approximation for simplifying the above formula, it is assumed that the occurrence of a packet pair for a given leaf pair is independent of the leaves themselves; that is, a packet goes to a branch i with probability w i , and thus that

Under the above assumption,

∑ i ≠ j ⁢ W ij ⁢ F i ⁢ F j ≅ 1 1 - ∑ i ⁢ w i 2 ⁢ ( ( ∑ i ⁢ w i ⁢ F i ) 2 - ∑ i ⁢ w i 2 ⁢ F i 2 ) .

Hence, it may be sufficient to track the individual packet fractions w i , rather than the pair fractions W ij , to get a useful approximation of the upper and lower bounds.

Now define the average end-to-end loss rate F L to the leaves, by

F L = ∑ i ⁢ w i ⁢ F i ,

the sum being taken over all leaves, i.e., end nodes, that are possible outer nodes. Hence,

∑ i ≠ j ⁢ W ij ⁢ F i ⁢ F j ≅ 1 1 - ∑ i ⁢ w i 2 ⁢ ( F L 2 - ∑ i ⁢ w i 2 ⁢ F i 2 )

using the preceding approximation. If there are many leaves but packet arrivals are sufficiently uniform among the leaves that none of them dominate, the sum

∑ i ⁢ w i 2

will be small. If the sum is taken as negligibly small, there follows the approximation

∑ i ≠ j ⁢ W ij ⁢ F i ⁢ F j ≅ F L 2 ,

which yields approximate lower and upper bounds according to the expression,

As noted above, a computational simplification can be achieved in the event there are many leaf branches by grouping the branches into a plurality of lumped pseudo-branches. This grouping is advantageously performed randomly. This can be done without a substantial loss in estimation efficiency. That is, the only information that is effaced by the grouping is that relating to packet pairs whose respective destinations fall into the same group. Therefore, provided there are, e.g., at least 10 groups, information on no more than 10% of the packet pairs will be lost.

As described above, the various summations involved in the computations for Algorithm 1 are carried out over all possible pairs of outer nodes. In an alternative approach for applying Algorithm 1, we do the following:

For a given inner node, consider each of its branches and all of the end nodes that terminate those branches. Group all end nodes that terminate a given branch into an artificial, lumped end node. By treating the lumped end nodes as single nodes, the portion of the tree graph extending from the given inner node to the lumped end nodes is transformed into a two-level tree with, typically, many branches, each branch terminated by one of the lumped end nodes. When this alternative approach is applied, the summations are taken over all possible pairs of the (distinct) lumped end nodes.

In at least some cases, the alternative approach described above may be advantageous both by reducing the amount of computation and by increasing accuracy. The reason is that there are fewer effective outer nodes over which to perform the summations, and the consolidation of outer nodes mitigates the inaccuracies that might occur in determinations of end-to-end loss rates when too few packets are destined for some end nodes.