Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 1 of 13
`Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 1 of 13
`
`
`
`EXHIBIT A
`
`EXHIBIT A
`
`

`

`US00827.4902B2
`
`(12) United States Patent
`Bu et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8.274,902 B2
`Sep. 25, 2012
`
`(54) ESTIMATION METHOD FOR LOSS RATES IN
`APACKETIZED NETWORK
`
`(75) Inventors: Tian Bu, Basking Ridge, NJ (US); Jin
`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.
`(2006.01)
`H04 IAI6
`(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.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`6,978,223 B2 * 12/2005 Milliken ....................... TO2, 182
`285,500 Al
`12/2006 Booth, III et al.
`1/2008 Kobayashi .................... 370,231
`7,319,668 B2*
`7,548,558 B2*
`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
`WOO2,39673 A1
`5, 2002
`WO
`WO PCT/US2010/044095
`11, 2010
`* cited by examiner
`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
`
`
`
`110
`
`OBTAN:
`- END-TO-END LOSS RATES F, F,
`o PAIR-LOSS RATE Fis
`o PAIR RATESW FOR ALL OUTER NODE PAIRS
`
`120
`
`SELECTINNERNODEn
`
`Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 2 of 13
`
`130
`
`SELECT OUTER NODEs n,n.
`
`140
`
`COMPUTE LOSS RATE for FROMROOTNODE noTO
`INNER NODEn USING DATA OBTAINED INSTEP 110
`
`

`

`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
`
`
`
`Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 3 of 13
`
`FIG. 1
`PRIOR ART
`
`

`

`U.S. Patent
`
`Sep. 25, 2012
`
`Sheet 2 of 7
`
`US 8,274,902 B2
`
`70
`
`40
`
`BSBSBSBS-50
`
`Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 4 of 13
`
`
`
`

`

`U.S. Patent
`
`Sep. 25, 2012
`
`Sheet 3 of 7
`
`US 8,274,902 B2
`
`no
`O
`
`O
`
`O
`
`C
`
`O
`
`O
`
`O
`
`O
`
`O
`
`n
`
`C
`
`O
`
`l
`
`l2
`
`n2
`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
`n 4 O
`Il6
`
`O O
`
`O O
`
`FIG 3
`
`Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 5 of 13
`
`

`

`U.S. Patent
`
`Sep. 25, 2012
`
`Sheet 4 of 7
`
`US 8,274.902 B2
`
`
`
`110
`
`120
`
`1,30
`
`OBTAN:
`END-TO-END LOSS RATES F, F,
`o PAIR-LOSS RATE Fis
`o PAIR RATESW FOR ALL OUTER NODE PAIRS
`
`SELECTINNER NODEn
`
`SELECT OUTER NODEs n,n.
`
`COMPUTE LOSS RATEf FROMROOTNODE noTO
`101 INNER NODEn USING DATAOBTAINED INSTEP 110
`
`Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 6 of 13
`
`FIG. 4
`
`

`

`U.S. Patent
`
`Sep. 25, 2012
`
`Sheet 5 Of 7
`
`US 8,274,902 B2
`
`no
`O
`
`O
`
`O
`
`O
`
`C
`
`O
`
`O
`
`C
`
`C
`
`Il
`O
`
`O
`
`O
`
`l
`
`l2
`
`n2
`O
`
`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
`n 4 O
`l6
`
`O O
`
`O O
`
`FIG. 6
`
`Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 7 of 13
`
`

`

`U.S. Patent
`
`Sep. 25, 2012
`
`Sheet 6 of 7
`
`US 8,274,902 B2
`
`210
`
`
`
`220
`
`
`
`230
`
`SELECT INTERMEDIATE NODEs in n
`
`
`
`
`
`
`
`COMPUTE LOSS RATES fo AND for USING ALGORITHM 1
`
`
`
`COMPUTE f = (fo-fo)/(1-fo)
`
`FIG. 6
`
`Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 8 of 13
`
`

`

`U.S. Patent
`
`Sep. 25, 2012
`
`Sheet 7 Of 7
`
`US 8,274,902 B2
`
`flo
`
`l
`
`I
`
`l
`
`C
`
`2
`is
`ls
`o o O O nag Qns c) d did
`l,
`
`ls
`C
`i5
`
`17 in
`
`Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 9 of 13
`
`C
`
`O O O. C.
`
`C.
`
`

`

`1.
`ESTMATION METHOD FOR LOSS RATES IN
`A PACKETIZED NETWORK
`
`US 8,274,902 B2
`
`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
`
`10
`
`15
`
`25
`
`30
`
`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
`45
`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.
`
`35
`
`40
`
`SUMMARY OF THE INVENTION
`
`50
`
`Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 10 of 13
`
`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.
`
`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
`
`

`

`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
`25
`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
`
`55
`
`Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 11 of 13
`
`45
`
`50
`
`60
`
`65
`
`US 8,274,902 B2
`
`5
`
`10
`
`15
`
`30
`
`35
`
`40
`
`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
`
`

`

`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
`35
`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
`
`Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 12 of 13
`
`F-FF fo(1-fo)(1-fif)
`
`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 wife)
`
`iFi
`
`iFi
`
`X (Fair - Wii FiFi) is for (1 - fok)
`iFi
`
`It follows that f has lower and upper bounds as expressed
`
`Fair - X WiFi Fi
`1 - 1-4-
`1- ). Wii F, F,
`i-Fi
`2
`
`
`
`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,
`
`10
`
`15
`
`25
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`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
`
`10
`
`i
`
`will be small. If the sum is taken as negligibly small, there
`follows the approximation
`
`15
`
`which yields approximate lower and upper bounds according
`to the expression,
`
`Fair - Fi
`1-1-4-1.
`2
`
`1- W1-4(Fi-Fi)
`s foks
`2
`s3 - -
`
`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
`
`Case 6:20-cv-00465 Document 1-1 Filed 06/02/20 Page 13 of 13
`
`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
`
`