EXHIBIT G

Declaration of Richard M. Chen in Support of Microsoft Corporation’s Motion for Summary 

Judgment of Patent Ineligibility

Case 6:20-cv-00461-ADA Document 139-4 Filed 04/19/22 Page 1 of 13
US00827.4902B2 

(12) United States Patent (10) Patent No.: US 8.274,902 B2 

Bu et al. (45) Date of Patent: Sep. 25, 2012 

(54) ESTIMATION METHOD FOR LOSS RATES IN (56) References Cited 

APACKETIZED NETWORK 

U.S. PATENT DOCUMENTS 

(75) Inventors: Tian Bu, Basking Ridge, NJ (US); Jin 6,978,223 B2 * 12/2005 Milliken ....................... TO2, 182 

285,500 Al 12/2006 Booth, III et al. Cao, Edison, NJ (US) 

(73) Assignee: Alcatel Lucent, Paris (FR) 

(*) Notice: Subject to any disclaimer, the term of this 

patent is extended or adjusted under 35 

U.S.C. 154(b) by 90 days. 

(21) Appl. No.: 12/462.965 

(22) Filed: Aug. 12, 2009 

(65) Prior Publication Data 

US 2011 FOO38269 A1 Feb. 17, 2011 

(51) Int. Cl. 

H04 IAI6 (2006.01) 

(52) U.S. Cl. ......................... 370/248: 370/252: 709/224 

(58) Field of Classification Search .................. 370/252, 

370/328, 248,242; 709/223, 224 

See application file for complete search history. 

OBTAN: 

7,319,668 B2* 

7,548,558 B2* 

1/2008 Kobayashi .................... 370,231 

6/2009 Rakib et al. .... ... 370/466 

2003/0048750 A1* 3/2003 Kobayashi. 370,229 

2004/0114576 A1* 6/2004 Itoh et al. ...................... 370,352 

2004.0143672 A1* 7/2004 Padmanabham et al. ..... TO9,231 

2008/0233951 A1* 9, 2008 Uchida et al. ................. 455,425 

2010/0165862 A1* 7/2010 Nylander et al. ...... 370.252 

2010/0220665 A1 9, 2010 Govindan et al. ............. 370,329 

FOREIGN PATENT DOCUMENTS 

WO WOO2,39673 A1 5, 2002 

WO PCT/US2010/044095 

* cited by examiner 

11, 2010 

Primary Examiner — Andrew Lee 

(74) Attorney, Agent, or Firm — M. I. Finston 

(57) ABSTRACT 

A method is provided, according to which data are collected 

on downstream packet losses at a single point in a network. 

From from the collected data, packet loss rates are estimated on at least two subnetworks downstream of the collection 

point. The respective subnetworks may differ by one or more 

links. 

6 Claims, 7 Drawing Sheets 

- END-TO-END LOSS RATES F, F, 

o PAIR-LOSS RATE Fis 

o PAIR RATESW FOR ALL OUTER NODE PAIRS 

110 

120 

130 

140 

SELECTINNERNODEn 

SELECT OUTER NODEs n,n. 

COMPUTE LOSS RATE for FROMROOTNODE noTO 

INNER NODEn USING DATA OBTAINED INSTEP 110 

 

Case 6:20-cv-00461-ADA Document 139-4 Filed 04/19/22 Page 2 of 13
U.S. Patent Sep. 25, 2012 Sheet 1 of 7 US 8,274.902 B2 

10 

GGSN)- 20 

(SGSN)-30 (SGSN) (SGSN)-30 

Ric Ric-40 NcNC-40 Ric Ric-40 

BSBSBSBS-50 BSBSBSBS-50 BSBSBSBS-50 

FIG. 1 

PRIOR ART 

 

Case 6:20-cv-00461-ADA Document 139-4 Filed 04/19/22 Page 3 of 13
U.S. Patent Sep. 25, 2012 Sheet 2 of 7 US 8,274,902 B2 

70 

40 

BSBSBSBS-50 

 

Case 6:20-cv-00461-ADA Document 139-4 Filed 04/19/22 Page 4 of 13
U.S. Patent Sep. 25, 2012 Sheet 3 of 7 US 8,274,902 B2 

no 

O 

l 

n 

O O 

l2 

n2 C O O C O O O O O 

ls | \ls 

O O O O in 3 O On 5 O O O C C C O O. O. O. O. O. 

l \l 

O O O O O O 

n 4 O 

Il6 

FIG 3 

Case 6:20-cv-00461-ADA Document 139-4 Filed 04/19/22 Page 5 of 13
U.S. Patent Sep. 25, 2012 Sheet 4 of 7 US 8,274.902 B2 

OBTAN: 

END-TO-END LOSS RATES F, F, 

o PAIR-LOSS RATE Fis 

o PAIR RATESW FOR ALL OUTER NODE PAIRS 

110 

120 SELECTINNER NODEn 

1,30 SELECT OUTER NODEs n,n. 

COMPUTE LOSS RATEf FROMROOTNODE noTO 101 INNER NODEn USING DATAOBTAINED INSTEP 110 

FIG. 4 

 

Case 6:20-cv-00461-ADA Document 139-4 Filed 04/19/22 Page 6 of 13
U.S. Patent Sep. 25, 2012 Sheet 5 Of 7 US 8,274,902 B2 

no 

O 

l 

Il 

O O O 

l2 

n2 O O O O C O O C C 

ls | \ls 

O O O O Il3 O On 5 O O O C C C O. O. O. O. O. O. 

l \l 

O O O O O O 

n 4 O 

l6 

FIG. 6 

Case 6:20-cv-00461-ADA Document 139-4 Filed 04/19/22 Page 7 of 13
U.S. Patent Sep. 25, 2012 Sheet 6 of 7 US 8,274,902 B2 

210 SELECT INTERMEDIATE NODEs in n 

COMPUTE LOSS RATES fo AND for USING ALGORITHM 1 

COMPUTE f = (fo-fo)/(1-fo) 

220 

230 

FIG. 6 

 

 

 

 

 

 

Case 6:20-cv-00461-ADA Document 139-4 Filed 04/19/22 Page 8 of 13
U.S. Patent Sep. 25, 2012 Sheet 7 Of 7 US 8,274,902 B2 

flo 

l 

I 

C 

l 

2 C 

ls is 

o o O O nag Qns c) d did O O O. C. C. 

l, ls 

17 in C i5 

Case 6:20-cv-00461-ADA Document 139-4 Filed 04/19/22 Page 9 of 13
US 8,274,902 B2 

1. 

ESTMATION METHOD FOR LOSS RATES IN 

A PACKETIZED NETWORK 

FIELD OF THE INVENTION 

The invention relates to methods for monitoring the per 

formance of networks, and more particularly to the determi 

nation of packet loss rates. 

ART BACKGROUND 

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 quan 

tifying the loss rate attributable to buffer overflow at a node of 

the network, the network operator may be able to apply poli 

cies 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 applica 

tions, and video and other applications, each of which has 

different bandwidth requirements and different delivery 

modes. This competition is exacerbated by the limited band 

width 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. Par 

ticular 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. 

SUMMARY OF THE INVENTION 

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 per 

formed 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. 

10 

15 

25 

30 

35 

40 

45 

50 

55 

60 

65 

2 

BRIEF DESCRIPTION OF THE DRAWING 

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. 

DETAILED DESCRIPTION 

Schematically illustrated in FIG. 1 is a portion of a typical 

wireless communication network having a GPRS core net 

work. 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 mul 

tiple 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 communica 

tion 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 instruc 

tions, or a special-purpose machine operating under the con 

trol 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 intermedi 

ate 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 imple 

mentations 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 

Case 6:20-cv-00461-ADA Document 139-4 Filed 04/19/22 Page 10 of 13
US 8,274,902 B2 

3 

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 away that each base station serves at 

least two equivalent nodes. Although Such an approach does 

not yield loss rates on individual airlinks, it will often provide 

useful information about loss rates as averaged over popula 

tions of air links. 

In FIG.3, the root node is labeled no. We refer to the leaves 

of the tree graph, such as nodes n and n, as “end nodes. We 

refer to all nodes between the root and the end nodes as 

“intermediate nodes.” Examples of intermediate nodes are 

nodes n2 ns, and ns. 

One important observation we have made is that informa 

tion 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 observa 

tion 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 8. The value of 8 may be specified by the operator, or it may be determined adap 

tively. 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 8 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 net 

works is the end-to-end packet loss rate F, from a root node no 

to an end node n, Given two distinct end nodes n,n another often-measurable quantify is the probability Fis that a 

packet destined for n, and a packet destined for n, 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., of all packet pairs (counted over a suitable 

averaging period) transmitted from the root node that are 

5 

10 

15 

25 

30 

35 

40 

45 

50 

55 

60 

65 

4 

destined for a given pair of end nodes n, n. That is, for all end 

nodes n, n, izj, let N, represent the total count, over the averaging period, of packet pairs destined for (n, n). Then in 

general, W., N/XN, 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 overall 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 for from a root 

node no to a selected intermediate noden. Thus, for example, Algorithm 1 might be applied to estimate the loss rate from 

the root node to node n of FIG. 3, i.e., the loss rate over the 

path that is the concatenation of paths land 1. 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 n2 of FIG. 3 is a branch 

point of the tree graph. One branch goes to node n3 and from 

there has two sub-branches, one of which terminates at end 

node na. The other branch goes to node n5 and then termi 

nates at end node nó. 

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, na and no qualify as outer 

nodes (relative to selected inner node n2). Turning now to FIG.4, the first step 110 of the procedure is 

to obtain from measurements: The end-to-end loss rate F. 

from the root node no to each possible outer node n, the 

pair-loss rate F.s from the root node no to each possible pair of Outer nodes n, n, and the pair fractions W for all 

possible pairs n, n, 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. In the example of FIG. 3, node n is selected as the inner 

node. 

The next step 130 is to select two end nodes n, n, which qualify as outer nodes. The next step 140 is to compute an 

estimate of the packet loss rate for from the root node no to the 

selected inner node n, 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 is estimated 

from the end-to-end loss rates F, the pair fractions W, and 

F4,6:8: We will now describe a procedure, referred to here as 

Algorithm 2, for estimating the packet loss rate on a path P. 

from a selected intermediate node n, to a selected intermedi 

ate node n, lying below n, in the tree graph. In order for the 

selected intermediate nodes n, and n to be eligible for appli cation 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 under 

Case 6:20-cv-00461-ADA Document 139-4 Filed 04/19/22 Page 11 of 13
US 8,274,902 B2 

5 

stand 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 from node n1 to node n3. With 

reference to FIG. 5, this path may be described as the concat 

enation of links 1 and 1. 

Turning now to FIG. 6, the first step 210 of the procedure is 

to select the intermediate nodes n, n. In the example of FIG. 

5, as noted, the selected intermediate nodes are n1, m3. 

The next step 220 is to compute the loss rates fo, and fo, using Algorithm 1. In the example of FIG. 5, the computed 

loss rates are f, i.e., the loss rate on link 1, and fo, i.e., the 

loss rate on the path that is the concatenation of links 1,12, and 

ls. 

The next step 230 is to compute the loss rate f between the 

selected intermediate nodes from the rates obtained in step 

220. In the example of FIG. 5, the loss rate f is the loss rate 

on the path that is the concatenation of links 12, and 1. 

It will be evident from FIG. 5, that step 230 may be thought 

of as decomposing a three-level path n0-to-n1-to n3 into a 

pair of two-level paths no-to-n1 and no-to-n3, 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 (fo-fo)/(1-fo). In the 

example of FIG. 5, the computation is f (fo-fc)/(1-f). 

In applying the formula, negative values off 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 no to end node n. 

The end-to-end loss rate from no to n is measurable. Con 

sequently, foa is taken as F. 

The end-to-end loss rate f from no to the intermediate 

node n is computed by Algorithm 1 using the measured 

values of the end-to-end loss rates from the root node no to 

nodes n and n, and the measured value of the pair-loss prob ability Fa7s. Then Algorithm 2 is used to compute the loss 

rate f on link 1. 

Algorithm 1 is then used to compute the loss rate for from 

no to intermediate node n2 using the measured values of the 

end-to-end loss rates from the root node no to nodes n and no 

and the measured value of the pair-loss probability Facts. 

Algorithm 2 is then used to compute the loss ratef, on link 1, 

using the determined values off and f. 

Algorithm 1 is then used to compute the loss rate Fol from 

no to n using the measured values of the end-to-end loss rates 

from no to n and a further nodens (not identified in the figure) and the measured value of the pair-loss probability Fass. 

Algorithm 2 is then used to compute the loss rate f onlink12 

from fi and f. 

The loss rate from no to n, i.e., the loss rate on link 1, is set 

to rate f, which has been computed using Algorithm 1. 

Mathematical Details 

Let n be a selected inner node, and let n, and n, be corre sponding outer nodes. Let f be the packet loss rate from the 

root node no to node n, and let f, and f, be the respective packet loss rates from n to n, and from n to n. Under the assumptions that the two packets in a packet pair will expe 

rience 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-FF fo(1-fo)(1-fif) 

10 

15 

25 

35 

40 

45 

50 

55 

60 

65 

and hence that 

iFi iFi 

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

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

Fair = X WiFi, 

iFi 

where the sum is taken over all possible pairs of outer nodes. 

Since f cannot be greater than F, it follows that 

sXEW, (F, - F. F.) = fok (1 -i ( -X iFi wife) iFi 

X (Fair - Wii FiFi) is for (1 - fok) 

iFi 

It follows that f has lower and upper bounds as expressed 

1- ). Wii F, F, i-Fi 

2 

Fair - X WiFi Fi 

1 - 1-4- 

s fok 

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 them 

selves; that is, a packet goes to a branchi with probability w. 

and thus that 

Under the above assumption, 

XWF, iFi (), fly-X, if) 

Hence, it may be sufficient to track the individual packet 

fractions w, rather than the pair fractions W to get a useful approximation of the upper and lower bounds. 

Now define the average end-to-end loss rate F, to the 

leaves, by 

F = Xw F, i 

the Sum being taken over all leaves, i.e., end nodes, that are 

possible outer nodes. Hence, 

 

Case 6:20-cv-00461-ADA Document 139-4 Filed 04/19/22 Page 12 of 13
US 8,274,902 B2 

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 

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

follows the approximation 

which yields approximate lower and upper bounds according 

to the expression, 

Fair - Fi 

1-1-4-1. 

2 s foks s3 - 

1- W1-4(Fi-Fi) - 2 

As noted above, a computational simplification can be 

achieved in the event there are many leafbranches by group ing 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 

10 

15 

25 

30 

35 

40 

45 

50 

8 

approach is applied, the Summations are taken over all pos sible 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 miti 

gates the inaccuracies that might occur in determinations of 

end-to-end loss rates when too few packets are destined for 

Some end nodes. 

What is claimed is: 

1. A method, comprising: collecting data on downstream packet losses at a single 

collection point in a network that branches, downstream 

of the collection point, toward a plurality of end nodes 

and that includes nodes intermediate the collection point 

and at least some of the end nodes, wherein the data 

describe downstream end-to-end packet loss between 

the collection point and two or more end nodes on dif 

ferent branches of the network; and 

from the collected data, estimating a packet loss rate on at 

least one path that begins or ends on an intermediate 

node and that includes or begins or ends on an interme 

diate node that is a branch point of the network. 

2. The method of claim 1, wherein the data collection is 

performed by a dedicated hardware monitoring device. 

3. The method of claim 1, wherein the data collection is 

performed by a dedicated hardware monitoring device 

deployed on the first link below the GPRS Support Node 

(GGSN) of a GPRS core network. 

4. The method of claim 1, wherein the collected data relate 

to packet losses on the portion of a GPRS core network 

extending from the collection point to a plurality of base 

stations. 

5. The method of claim 1, wherein the collected data relate 

to packet losses on the portion of a GPRS core network 

extending from the collection point to a plurality of mobile 

stations. 

6. A monitoring device, comprising: 

an input for collecting data on downstream packet losses at 

a single collection point in a network that branches, 

downstream of the collection point, toward a plurality of 

end nodes and that includes nodes intermediate the col 

lection point and at least some of the end nodes, wherein 

the data describe downstream end-to-end packet loss 

between the collection point and two or more end nodes 

on different branches of the network; and 

a circuit configured to compute from the collected data an 

estimate of a packet loss rate on at least one path that 

begins or ends on an intermediate node and that includes 

or begins or ends on an intermediate node that is a branch 

point of the network. 

k k k k k 

Case 6:20-cv-00461-ADA Document 139-4 Filed 04/19/22 Page 13 of 13