Network tomography from aggregate loss reports

July 13, 2017 | Autor: Thierry Turletti | Categoría: Technology, Performance Evaluation, Mathematical Sciences, Network monitoring, Real Time, Network Tomography
Share Embed


Descripción

Network Tomography from Aggregate Loss Reports N.G. Duffield a , V. Arya c , R. Bellino b , T. Friedman b , J. Horowitz d , D. Towsley d , T. Turletti c a AT&T b U.

Labs–Research, Florham Park, NJ, USA

P. & M. Curie, Laboratoire LiP6-CNRS, Paris, France c INRIA, d University

Sophia Antipolis, France

of Massachusetts, Amherst, MA, USA

Abstract Multicast applications and network monitors can potentially benefit from the ability to infer the loss rates along links within a multicast tree. Estimators, known generically by minc, or multicast inference of network characteristics, have been developed to provide this ability. They consider multicast data packets to be probes, and conduct inference based upon reports of which probes reached each receiver. In practice, gathering reports from receivers in real time is a non-trivial task that presents scaling problems as the number of receivers increases. Prior work has led to an extension of the RTP data transport protocol to permit receivers to report per-probe information in packets known as RTCP XR packets. This paper demonstrates how minc inference can, in fact, be conducted using only a default RTP packet format known as RTCP RR. RTCP RR packets contain summary information rather than per-probe information. They thus offer bandwidth savings, although this comes at the expense of an increase in estimator convergence time. Furthermore, this technique can be used by the observer of any standard RTP session, whereas estimation based upon per-probe information is only possible when a session explicitly employs the extended reporting format. Key words: End-to-End Measurement, Moment Estimator, Multicast, RTCP, Loss Inference, MINC

1

Introduction

Loss Inference from Multicast Probes. Minc (Multicast-Based Inference of Network Internal Characteristics) is a tomography tool that can infer the Preprint submitted to Elsevier Science

2 October 2005

internal characteristics of a network from end-to-end multicast measurements. Minc can infer characteristics such as loss rates and delay distributions of internal network links [3,6] and the topology itself [4]. To infer loss rates, the source injects a stream of probe packets into the multicast tree. For each probe, each receiver reports whether it received the probe (1) or not (0). Based on the binary feedbacks collected from all receivers, per link loss rates in the multicast tree are inferred. RTCP Extensions for Loss Reporting. Dedicated infrastructures to perform large scale multicast measurements are generally complex to deploy. To facilitate the measurement process, authors of [2] proposed an architecture that allows existing multicast sessions to perform impromptu minc measurements. In this architecture, multicast sessions that employ the RTP data transport protocol [8] to transfer their data and which are effectively already probing the network, can opt to report the per packet binary feedback needed for minc inference by piggybacking these feedbacks on the existing RTP control packets, known as RTCP packets. In an RTP multicast session, receivers multicast RTCP packets back to the group. Thus any host that listens to RTCP reports can perform loss inference. The IETF proposed standard RFC 3611, RTP Control Protocol Extended Reports (RTCP XR) [5], provides a format called Loss RLE Report Blocks especially for such piggybacked feedback. One drawback to per packet feedback is that the increase in reporting bandwidth that arises as the number of receivers increases cannot be fully compensated for by the built-in RTCP scaling mechanism of less frequent reporting. The receiver that waits longer to report its information has more information to report, an amount that has increased linearly with time if the source has been emitting at a constant average rate. RTCP bandwidth can easily exceed the 5% of data bandwidth that RTP by default sets aside for reporting purposes. To overcome this scaling obstacle, the authors of [2] proposed a report thinning mechanism whereby receivers coordinate to report on one in every two probes, or one in every four, or in general one in every 2T , where T is an integer chosen to achieve the desired scaling properties. This mechanism was incorporated into the RTCP XR Loss RLE Report Blocks. Contribution. The RTCP XR format allows multicast sessions that choose to do so to conduct minc inference. This paper goes a step further, and demonstrates how minc inference abilities can be extended to RTP sessions that only employ the default RTCP packets. The principal finding is that the summary information that these packets contain, namely the cumulative number of packets lost and extended highest sequence number received fields of the Receiver Report packets, is sufficient to infer loss rates. Furthermore, Receiver Report based inference can be conducted by any observer of an RTP multicast session, whereas Extended Report based inference requires that the XR packet format be employed. However, a full comparison of the bandwidth/accuracy 2

trade-offs of the two methods is beyond the scope of this paper. Outline. Section 2 sets out the basic terminology for multicast tree and probes. Section 3 recapitulates the basic minc estimator. Section 4 describes our model for the content and statistics of RTCP reports. Section 5 describes our new moment estimator which estimates the loss rate on the common portion of the path from a multicast source to two receivers. We establish the crucial statistical property of consistency: the estimator converges to the true value as the number of probes grows. Section 6 proposes schemes for combining a number of two receiver moment estimators to yield estimators for the loss rate of all links in a logical multicast tree. Section 7 calculates the estimator variance in a special case that all receiver reports are aligned (i.e. report on the same sets of probes). The experimental evaluation is reported in Section 8. In model based simulations on model and real topologies, we find typical estimation accuracy of a few percent. We model the effect to RTCP dynamics; we find that the variance estimate of Section 7 performs well. We conclude with proposal for further work in Section 9.

2

Tree Model and Probe Process

Multicast Tree Model. Let T = (V, L) denote the logical multicast tree from a given source, consisting of the set of nodes V , including the source and receivers, and the set of links L. A link is an ordered pair (j, k) ∈ V × V denoting a link from node j to node k. The set of children of a node j is denoted by dj (i.e. dj = {k ∈ V : (j, k) ∈ L}). U = V \ {0} is the set of all non-root nodes. For each node j ∈ U there is a unique node k = f (j), the parent of j, such that (k, j) ∈ L. We shall define f n (k) recursively by f n (k) = f (f n−1 (k)), with f 0 (k) = k. We say that j is a descendant of k, and write j ≺ k, if k = f n (j) for some integer n > 0. j ∨ k denotes the closest common ancestor of nodes j and k, i.e., the unique node ` such that j, k ≺ `, with no other node `0 ≺ ` with this property. R is the set of leaves of T . Probe Model. We now describe the loss model in more detail. Probe packets are sent down the tree from a source at the root node 0. Each probe that arrives at node k results in a copy being sent to every child of k. We model the passage of probes down the tree by a stochastic process X = (Xk )k∈V where each Xk takes a value in {0, 1}; Xk = 1 signifies that a probe packet reaches node k, and 0 that it does not. The packets are generated at the source, so X0 = 1. For all other k ∈ V , the value of Xk is determined as follows. If Xk = 0 then Xj = 0 for the children j of k (and hence for all descendants of k). Conditioned on Xk = 1, then {Xj : j ∈ dk } are independent random variables, with the transmission probability for the probe to reach k from f (k) Q being αk := Pr[Xk = 1 | Xf (k) = 1]. Ak = jºk αj is the probability that a 3

probe reaches k from the root 0. x denotes 1 − x.

3

The MINC Loss Estimator

Measurements and Data. Consider an experiment in which n probes are dispatched from the root 0. Each probe i = 1, . . . , n gives rise to an independent realization X (i) of the probe process X. The outcome from probe i (i) (i) is the set of receiver measurements XR = (Xk )k∈R ∈ Ω := {0, 1}#R . The standard minc loss estimator is a maximum likelihood estimator for the link probabilities α = {αk : k ∈ U }, based on outcomes from the n probes. Two Leaf Tree. We briefly describe a simple case, and then the general maximum likelihood estimator. Consider a tree with two leaf nodes (R = {1, 2}) having a common parent c which is the only child of the root node 0. The possible outcomes are the set Ω = {11, 10, 01, 00}. Each outcome x ∈ Ω has a probability px = Prα [XR = x] that can be written in terms of the link probabilities: p11 = αc α1 α2 , p10 = αc α1 α2 and p01 = αc α1 α2 , with p00 = 1 − p11 − p10 − p01 . In fact, this relationship is invertible, α can be expressed in terms of the pij ’s as α1 =

p11 , p11 + p01

α2 =

p11 , p11 + p10

αc =

(p11 + p10 )(p11 + p01 ) p11

(1)

b of α results from replacing in For the two leaf topology the minc estimator α (1) the pij by the corresponding empirical probabilities pbij , i.e., the proportions of the n probes giving rise to outcome XR = ij.

General Tree. The above construction is specific to the two leaf tree, and it is not clear how it should be generalized to arbitrary trees. A systematic approach uses the log-likelihood for the outcomes which can be written as (1)

(n)

L(α) = log Prα [(XR , . . . , XR )] = n

X

pbx log px .

(2)

x∈Ω

The Maximum Likelihood Estimator (MLE) of α, namely, arg maxα L(α), was determined in [3], where its detailed form can be found. Here we summarize the general thrust be saying that the true probabilities Ak are the roots of polynomial equations involving the px . For computation, the MLE is obtained by inserting instead the measured frequencies pbx . The MLE possesses two useful properties: it is consistent (it converges to the true value as the number of probes grows) and it is efficient (it has minimal asymptotic variance). 4

4

Model for RTCP Reports

Reports and Blocks. Consider a multicast session in which one host (the source) sends a stream of probe packets into the group. The other hosts in the group form the receiver set R. Each receiver r ∈ R generates RTCP reports which are multicast back into the group. Consider the sequence of reports received from all receivers r ∈ R by some listening host in the network, for example another multicast group member. Suppose there are ir + 1 RTCP reports received from receiver r; we denote the reports by {ρir : i = 0, 1, ..., ir }. We regard each report as the pair ρir = (cir , eir ) where cir is the cumulative number of packets lost, and eir is the extended sequence number received. We assume that for each r ∈ R, the reports ρir have been put in increasing order of eir , counter roll-over having been resolved. We use the term blocks to describe the contiguous sets of sequence numbers of probes reported. For each r ∈ R and i ∈ Ir := {1, ..., ir }, define Sri = {eri−1 + 1, ..., eir − 1, eir } and Yri = #Sri − (cir − ci−1 r )

(3)

Thus Sri is the block of sequence numbers of packets that contributed to report ρir but not report ρri−1 . The number of such reports sir = #Sri = eir − eri−1 is called the block size. Yri is the number of those packets in the block Sri that reached receiver r; we call these the block counts. The definitions automatically take account of loss of RTCP packets, in the sense that if an one or more RTCP packets are lost in succession, the block formed by the next receipt of an RTCP packet is correspondingly longer. Statistical Model of Block Sizes and Counts. Recall that the set of probes is represented by independent copies {X (i) }i=1,...n of the process X. P Thus the block counts are modeled by Yri = j∈Sri Xr(j) . In the actual operation of RTCP, the block sizes may depend on block counts. In one scenario, reports are dispatched roughly periodically, with the extended highest sequence number being simply that of the last packet received during each period. Hence the loss of a set probe packets at the end of a period results in a lower extended highest sequence number than if the set had been received. In our terminology, the block size is reduced due to probe loss. We will set aside these complexities in making an initial statistical model of the reports. We regard the set of blocks and their sizes as a fixed set, e.g., as measured during a single experiment. The distribution of received packets, and hence of the block counts, is determined according to the loss model of Section 2, independently of the block sizes. In the small loss rate regime of primary interest to this paper, this independent model is not expected to be 5

too unrealistic. This is because for the small loss rates, any dependence of block sizes on the pattern of received packets will be small since lost packets are infrequent. However, for small block sizes this effect need not be negligible; we will return to this matter more when we report the experiments in Section 8.

5

Moment Estimator for Two Receivers

In distinction with the standard minc loss estimator, the MLE for estimating link probabilities from aggregate reports is difficult to compute directly. An iterative technique, the EM algorithm, can be used to provide an approximation to the MLE, subject to certain conditions. Instead, we seek a moment estimator of the link probabilities. In general, moment estimators do not possess the minimal variance properties of an MLE. However, our moment estimator is directly computable from the aggregate reports. We now construct a moment based estimator of the transmission probabilities Ak from root to node k. We introduce some further notation. For k, l ∈ R, ij and i ∈ Ik , j ∈ Il , define the block intersection Skl = Ski ∩ Slj be the set of sequence numbers (if any) that belong to both of the blocks Ski and Slj . Let Ikl = {(i, j) ∈ Ik × Il : Ski ∩ Slj 6= ∅ denote the set of ordered pairs of overlapping blocks. We have already defined the block sizes sik = #Ski ; we also ij define the block intersection sizes sij kl = #Skl . Fix k, l ∈ R and set c = k ∨ l. Let Bk = Ak /Ac denote the cumulative transmission probability from c to k, and similarly for l. E[Yki ] = sik Ac Bk , while E[Yki Ylj ] =

X

(x)

(y)

ij i j 2 E[Xk Xl ] = sij kl Ac Bk Bl + (sk sl − skl )Ac Bk Bl

(4)

x∈Ski ,y∈Slj

Hence when sij kl > 0, µ

A−1 c = 1+

E[Yki Ylj ] sik sjl j −1 i sij E[Y ]E[Y kl k l ]



(5)

This suggests we form the following estimator of Ac : Abkl = (1 + Un Vn − Wn )−1

(6) 6

where P (i,j)∈Ikl

Un = P

Yki Ylj

(i,j)∈Ikl

sij kl

P

P

P

i j sik j∈Il sjl (i,j)∈Ikl sk sl , Vn = P , W = (7) P n j ij iP j∈Il Yl i∈Ik Yk (i,j)∈Ikl skl i∈Ik

Theorem 1 Assume that as the number of probes n → ∞: (i) #Ik → ∞ for all k ∈ R, i.e., the number of RTCP reports received from each receiver is not bounded. (ii) The sik are uniformly bounded above by some s for all k ∈ R and i ∈ Ik . Then for each j, k ∈ R, Abkl is a consistent estimator of Aj∨l as n → ∞ Proof: We adapt a proof of the strong law of large numbers (SLLN) for independent random variables; see [10]. For z = (i, j) ∈ I12 , write Hz = Y1i Y2j − E[Y1i Y2j ]. Since si1 , sjs ≤ s, each Hz is independent of all but at most P 3s − 4 other Hz0 . We decompose E( z Hz )4 as follows, all sums being over distinct members of I12 : X

E(

z

Hz )4 =

X z

EHz4 +

+

X x,y,z

X y,z

E[Hy2 Hz2 ] +

E[Hx2 Hy Hz ] +

X y,z

X

E[Hy3 Hz ]

(8)

E[Hw Hx Hy Hz ]

(9)

w,x,y,z

Note that each E[Hy2 Hz2 ] is uniformly bounded, and hence the second term 2 in the sum is bounded above by a1 #I12 for some a1 > 0. Each term of the last three sums is zero unless each Hp occurring in a given term is dependent on at least one other Hq in that term. The total number of such terms is 3 bounded above by 3(3s−4) P #I12 and the expectation of each term is uniformly bounded. Writing Gn =

(ij)∈I12

P

(Y1i Y2j −E[Y1i Y2j ])

(i,j)∈I12

sij kl

, then there exists a2 such that

P

P

−2 E[G4n ] ≤ a2 #I12 . Now #I12 ≥ n/s, so E( n≥1 G4n ) < ∞ and hence n≥1 G4n < ∞ almost surely, and finally Gn → 0 almost surely. The difference between A−1 can be written as Gn Vn + (1 − A2c B1 B2 Vn )(1 − A−1 c and the RHS of (6) c − P P Wn ). By the SLLN, i∈Ij Yji / i∈Ij sij converges almost surely to Ac Bj > 0 for j = 1, 2, and hence Vn converges almost surely to (A2 B1 B2 )−1 . Hence Gn Vn and 1 − A2c B1 B2 Vn → 0 almost surely. Wn is bounded above since P P ij 2 i j (i,j)∈I12 skl ≥ #I12 . The result follows. 2 (i,j)∈I12 sk sl ≤ s #I12 while

6

Moment Based Estimator for General Trees

In extending the moments based estimator to general trees we settle two issues: (i) how to extend the moment based estimator to nodes having more than two 7

children; and (ii) how to recover estimates of the link probabilities αk from those of the path probabilities Ak . Concerning the first point, there are a number of potential approaches. • General Analog: Construct the direct analog of (6) for arbitrary number of receivers. While philosophically appealing, it is computationally complex, requiring the computation of the set of intersecting blocks over multiple leaves, a computation whose complexity increases with the number of leaves. • Convex Combination : For each node j ∈ V let Qj = {(k, l) ⊂ R×R : k∨l = j} denote the set of receiver pairs (k, l) whose closest common ancestor is j. For each (k, l) ∈ Qj , Abkl is a consistent estimator of Aj . Hence so is any P P convex combination (k,l)∈Qj λkl Abkl where λkl ∈ [0, 1] and (k,l)∈Qj λkl = 1. The question remains which combination to take. Possibilities include: – Uniform Combination : λkl = 1/#Qj – Minimum Variance Combination: λkl minimizes estimator variance. This approach does suffer from complexity due to increasing size of Qj for j nearer the tree root. • Random Selection: A representative (k, l) ∈ Qj is chosen at random, and the estimator Abkl is used. It remains to recover the link probabilities from the path probabilities. We denote by Abj , the estimator of Aj that results from the method of choice in the list above. Then the corresponding link estimators are formed by taking b /A b b bk = A quotients α k f (k) . Since the Ak are consistent, so are the αk .

7

Estimation Variance

In this section we compute, to first order in link loss rates, the variance for estimating the loss rate on the common path portion to two receivers. For relative simplicity, we do this in the special case of perfectly aligned uniform blocks, i.e., Ski are equal to some S i for all receivers k ∈ R, and sik = s for some s and all i and k. In later sections we will compare experimentally the estimation variance in this special case with that in the general case. Consider the two-leaf binary subtree with leaves {1, 2} and branch point c = 1 ∨ 2. Using (5) we can write Ac = Fs (E[Y1 ], E[Y2 ], E[Y1 Y2 ]),

for

Fs (x, y, z) =

1 (10) 1 + s(z/xy − 1)

The corresponding moment estimator from the block variables {Y i }i∈I is Abc = Fs (#I −1

X i∈I

Y1i , #I −1

X

Y2i , #I −1

i∈I

X i∈I

8

Y1i Y2i )

(11)

Consider inference from n probes in total, from measurements over blocks √ of size s; i.e. #I = n/s. By the δ-method (see e.g. [7]), n · (Abc − Ac ) is asymptotically normally distributed, as n → ∞ with mean 0 and variance σs2 = sFs0 · Cs Fs0 where Fs0 is the vector of partial derivatives: Fs0 = Fs0 (E[Y1 ], E[Y2 ], E[Y1 Y2 ]) = Fs0 (sE[X1 ], sE[X2 ], sE[X1 X2 ] + s(s − 1)E[X1 ]E[X2 ]) = Fs0 (sAc B1 , sAc B2 , sAc B1 B2 + s(s − 1)A2c B1 B2 ) Ã ! 1 + (s − 1)Ac 1 + (s − 1)Ac −1 = , , sB1 sB2 sB1 B2

(12) (13) (14) (15)

and Cs is the covariance matrix amongst the three quantities Y1 , Y2 and Y1 Y2 . The computation is elementary but long-winded, we summarize the result: Theorem 2 Consider a tree with two receivers {1, 2}, branch point c = 1 ∨ 2 and set Bi = Ai /Ac . With perfectly overlapping equal size blocks of size s, the asymptotic variance of Abc has the following form, to leading order in the loss rates, where kAk = max{Ac , B 1 , B 2 }: ³

´

σs2 = Ac + O(kAk2 ) + s B 1 B 2 + Ac (B 1 + B 2 ) + O(kAk3 )

(16)

The most interesting feature of (16) is that estimator variance is independent of block size to leading order in the loss rate. This indicates that, at least in the idealization of perfectly aligned blocks, changes in block size may not greatly impact estimator accuracy. However, once the block size is of the order of the reciprocal of the loss rates, the two terms in (16) are of comparable size, and we expect the variance to exhibit dependence on the block size. For finitely many probes n, (16) yield the approximation: Var(Abc ) ≈ σs2 /n

8

(17)

Experiments

We evaluated the moment estimator through model-based simulations. In these simulations, losses on links in the logical multicast tree are created using a time-invariant Bernoulli process. We simulate the passage of probes through the multicast tree and subsequently generate the receiver loss reports which are used to perform loss inference. Alignment. In the experiments, receiver loss reports were generated in one of two ways: (a) Perfect Alignment, and (b) Imperfect Alignment. These are illustrated in Figure 1. Perfect alignment represents the idealization described 9

(3,1)

(6,1)

(2,0) k

k Source

1 2 X 4 5 6 7 ...

c

(6,1)

Source

1 2 X 4 5 6 7 ...

c

1 2 3 4 X 6 7 ...

1 2 3 4 X 6 7 ... l

l Loss reports sent

(3,0)

Loss reports sent (4,0)

(6,1)

Packets received

Packets received

(a) Perfect alignment

(b) Imperfect alignment

Fig. 1. Difference between perfect and imperfect alignment. In (a) receivers use block size of 3. In (b) receiver k uses block size of 3 and l uses block size of 5. Reports are of the form (sequence number, cumulative losses).

in Section 7 in which all receivers report with a constant block size w, with block alignment to start at probe sequence numbers 0, w, 2w etc. The report is sent irrespective of whether the last probe in the block is received or lost. Block size w = 1 reduces to the standard minc loss estimator. This scheme is mainly of theoretical interest since in practice a receiver can not know if the wth probe is lost until it receives a probe with higher sequence number. However, the perfect alignment case is particularly amenable to analysis (see e.g. Section 7), so it is interesting to compare the simulation results with that of more realistic configurations of loss reports. A more realistic such arrangement is Imperfect Alignment. Here, receivers mimic the standard RTCP protocol to provide the summary loss reports. Thus the blocks of probes for which different receivers report may not be perfectly aligned. In practice, receivers of a multicast session collaboratively maintain the aggregate RTCP feedback bandwidth below a certain level of data bandwidth. To simulate this, we choose a constant b and set the block size w of each receiver uniformly at random between b/2 and 3b/2. Thus, although the block sizes used by each receiver are different, for R receivers the expected aggregate feedback bandwidth will be proportional to R/b times the data bandwidth. To simulate different start times, each receiver reports only on packets whose sequence number exceeds a initial value drawn uniformly at random from [1, . . . , 50]. Report dispatch mimics a RTCP timeout. When a receiver uses block size w, after every w probes it reports the highest sequence number received and the cumulative number of packets lost until that sequence number. Thus block size is correlated to the probe loss pattern, in distinction with the model of Section 4. However, as discussed at the end of that section, the correlation is small when the probe loss rate is small and the block size w large. We shall explore the potential impact of such correlations in our experiments. 10

1(MINC) 2 4 8 16 32 64 128

Mean Relative Error

0.04

0.04

0.03

0.02

0.01

0.03

0.02

0.01

0

0 1

2

3

4

5 6 7 Probes (1000s)

0.1

8

9

10

1

2

3

4

5 6 7 Probes (1000s)

0.1

median Relative Error

Relative Error

2 4 8 16 32 64 128

0.05

Mean Relative Error

0.05

0.08 0.06 0.04 0.02

8

9

10

128

256

median

0.08 0.06 0.04 0.02

0

0 0.5

1

2

4

8 16 Block Size

32

64

128

256

(a) Perfect Alignment

1

2

4

8

16 32 Block Size

64

(b) Imperfect Alignment

Fig. 2. Relative Error of the shared path for 2-receiver tree. (median for 10K probes)

Estimator Combination. Following Section 6, we combine appropriate moment estimators of the transmission rates Ak from source to a node k. For binary trees, we estimate by averaging over all appropriate receiver pairs. For trees with arbitrary degree, we estimate the passage probability using a random pair of receivers at each node. Link Loss Rates and Randomization. Link loss rates are chosen at random uniformly between 1% and 10%. Each experiment in a given topology is repeated 100 times. Except where noted, each repeat uses new random link loss rates, and new random receiver pairs for estimator combination. Accuracy Measures. To assess the accuracy of inferred passage rates, we compute the relative error of a link and the combined relative error of a tree. The relative error of a link which terminates at node k, is defined as REk = b k )/αk |. The combined relative error of a tree T is defined as CRET = |(αk − α P (1/#L) k∈V −0 REk , where #L is the number of links in the tree. Two Receiver Trees: Dependence on Block Size. We first study the behavior of the estimator for two receiver trees using perfect and imperfect alignment. In Figure 2, we plot the relative error of the shared link between 11

two receivers. The relative error is averaged over 100 experiments. The median of relative error along with its 5th and 95th percentiles is shown for 10, 000 probes. For imperfect alignment, the block size displayed in the legend is the constant b which was used to to set the block size, as described in the above paragraphs about alignment. We now comment on the qualitative features of Figure 2. For perfect alignment we observe (i) decrease in relative error with increasing number of probes; (ii) increase in relative error with block size. Both of these features are expected from Section 7. For imperfect alignment, the relative error for very small block sizes (up to 8) shows high relative error, even when the number of probes increase. We attribute this to violation of the modeled independence between probe loss and block size, which is expected to be more evident for small block sizes, as discussed in Section 4. However, for larger block sizes (32 and greater) the relative errors are similar for perfect and imperfect alignment, indicating that the simpler perfect alignment model provides a reasonable prediction of estimation error in this case. Two Receiver Trees: Accuracy of Variance Approximation. This motivates gaining a better understanding of the variance approximation (17). Figure 3 displays the standard error for estimating the loss rate on the common portion of the path to two receivers. The standard error is calculated over 100 experiments using a fixed link loss rate (1% on the left, 10% on the right) using perfect alignment of uniform block size (1 in the top row, 10 in the middle row, 100 in the bottom row). Also displayed is the first order analytic approximation from Section 7. The approximation appears reasonably close for all parameters considered. Impact of Report Loss. Next we study the impact of report loss on the quality of inference. Since reports contain cumulative information, report loss only has the effect of increasing the size of some blocks. As a secondary effect the rate of convergence is expected to decrease, since a small number of longer blocks are available for inference. In our experiments we consider a 16-receiver complete binary tree and conduct experiments with imperfect alignment. In Figure 4(a) we plot the CRE averaged over 100 experiments when no receiver reports are lost. In Figure 4(b), we show the CRE when receiver reports are lost at a uniform loss rate of 1%. The largest effect is seen for larger block sizes: with report loss the mean CRE is roughly doubled for 10,000 probes at block size 128. Impact of Multicast Group Joins and Leaves. In practice, as receivers join and leave, they change the block sizes which are used to generate summary reports in order to control the aggregate RTCP feedback bandwidth. It is important to determine whether the natural dynamics of the block size during 12

0.0035 0.003

data model

0.01

0.0025

Standard Deviation

Standard Deviation

0.012

data model

0.002 0.0015 0.001

0.008 0.006 0.004 0.002

0.0005 0

0 1

2

3

4

5 6 7 Probes (1000s)

8

9

10

1

(a) Loss=1%; Block=1 0.004

3

4

5 6 7 Probes (1000s)

8

9

10

9

10

9

10

(b) Loss=10%; Block=1 0.025

data model

0.0035

2

data model

Standard Deviation

Standard Deviation

0.02 0.003 0.0025 0.002 0.0015

0.015

0.01

0.001 0.005 0.0005 0

0 1

2

3

4

5 6 7 Probes (1000s)

8

9

10

1

(c) Loss=1%; Block=10 0.007

4

5 6 7 Probes (1000s)

0.07

8

data model

0.06

0.005

Standard Deviation

Standard Deviation

3

(d) Loss=10%; Block=10

data model

0.006

2

0.004 0.003 0.002 0.001

0.05 0.04 0.03 0.02 0.01

0

0 1

2

3

4

5 6 7 Probes (1000s)

8

9

10

(e) Loss=1%; Block=100

1

2

3

4

5 6 7 Probes (1000s)

8

(f) Loss=10%; Block=100

Fig. 3. Estimation variance for perfect alignment: empirical from data, and first order model

13

0.08

0.08 16 32 64 128

0.07

16 32 64 128

0.07

0.06

0.06 Mean CRE

Mean CRE

0.05 0.04

0.05

0.04

0.03 0.03

0.02

0.02

0.01 0

0.01

0.09 0.08 0.07 0.06 0.05 0.04 0.03 0.02 0.01 0

2

3

4

5 6 7 Probes (1000s)

8

9

10

1

median CRE

CRE

1

8

16

32 64 Block Size

128

256

(a) No Reports lost

0.09 0.08 0.07 0.06 0.05 0.04 0.03 0.02 0.01 0

2

3

4

5 6 7 Probes (1000s)

8

9

10

median

8

16

32 64 Block Size

128

256

(b) Report loss rate = 1%

Fig. 4. Impact of report loss, 16-receiver complete binary tree. (median for 10K probes)

an RTCP session interferes with the ability to perform inference over short time scales. We study the effect of this process on the inference procedure using the following experiment. We assume the existence of a stable set of receivers which are part of a large multicast tree. These receivers perform loss inference for links within their subtree. When receivers in other parts of the tree join and leave, these receivers increase or decrease their block size to control the RTCP bandwidth. In our experiment we consider a binary subtree of 16-receivers, regarded as a subtree of some larger tree encompassing the whole multicast group. 10,000 probes are sent, and reports use imperfect alignment. Receivers start reporting with a block size of 16. After 3, 000 probes, they change their block size to 48 to simulate a join elsewhere in the full tree. After 7, 000 probes, the block size is changed to 32 to simulate leave elsewhere in the full tree. The loss inference is done over reports on successive sets of 2,000 probes; Figure 5(a) shows the corresponding CRE. The CRE at 4, 000 and 8, 000 probes displays higher variance because of the change in block size due to join and leave operations. The figure shows that even by restricting inference to collections of 2, 000 probes (i.e. within the timescale of block size changes), we are still able to perform inference to an median accuracy of about 10%. 14

0.16

0.16 median

0.14

0.14

0.12

0.12

0.1

0.1 CRE

CRE

median

0.08

0.08

0.06

0.06

0.04

0.04

0.02

0.02

0

0 2000

4000 6000 8000 Probes (1000s)

1000

2000

(a) Without EWMA

4000 6000 8000 Probes (1000s)

1000

(b) With EWMA, x = 1/16

Fig. 5. Impact of join-leave, 16-receiver complete binary tree

Fig 5(b) shows the same results if a running exponentially weighted average of estimated passage rates is maintained. In this case, after every 2000 probes, the passage rate is updated as αki+1 = xαk + (1 − x)αki , where αk is the passage rate estimated using feedbacks of previous 2, 000 probes. We use x = 1/16. In this case, due to exponential smoothing, the CRE shows less variance. Inference on Larger Trees. Finally, we study the performance of the moment estimator on trees of arbitrary degree. For this, we considered the publicly available router level map of the AT&T network produced by Rocketfuel [9]. This contains 731 nodes joined by 2253 links. We chose random nodes as source and receivers and cut 100 32-receiver shortest path multicast trees. Hop-count metric was used to calculate the shortest path trees. Subsequently, we extracted the logical multicast trees and used them for model-based simulations with link loss rates as before. In these set of trees, the degrees of nodes varied from 2 to 6 and the maximum depth was 6. Figure 6 shows the CRE for the experiment with imperfect alignment when estimation is done using random pair of receivers at each node. The typical inference accuracy is a few percent.

9

Conclusions and Further Work

In this paper, we developed a moment estimator for minc loss inference using only summary information contained in standard RTCP packets. We tested the moment estimator using model-based simulations. Our experiments demonstrated the behavior of the moment estimator under typical conditions 15

0.08 16 32 64 128

0.07 0.06

Mean CRE

0.05 0.04 0.03 CRE

0.02 0.01 0 1

2

3

4

5 6 7 Probes (1000s)

8

9

10

(a) Mean CRE

0.09 0.08 0.07 0.06 0.05 0.04 0.03 0.02 0.01 0

median

8

16

32 64 Block Size

128

256

(b) Median CRE (10k probes)

Fig. 6. Experiments with arbitrary 32 receiver trees (Estimation using random pair)

such as report loss, block size change due to group joins and leaves, and in large multicast trees of arbitrary degree. For link loss rates varying between 1% and 10%, when no reports are lost, the moment estimator is able to infer link loss rates with an error of about 2% for 10,000 probes. With a report loss of 1%, the error in estimation stays below about 6%. Our two models (perfect and imperfect alignment) showed similar estimation error for large block sizes, at least in the two leaf tree. The empirical variance for perfect alignment agreed well with an analytical approximation for small loss rates. We now discuss future work. On the theoretical side, we wish to extend the analysis of the imperfect overlap model to include the effects of correlation between block size and packet loss. We also wish to explore a one step iterative modification of the moment estimator. Under certain conditions, such modification are efficient: they have the same asymptotic variance as the MLE. On the experimental side, we wish to compare the performance trade-offs in bandwidth and accuracy for the moment estimator, with that of the estimator based on the extended RTCP reports of [2] and the recently proposed estimator of [1]. All such studies should be evaluated under a wider variety of topologies, probe and report loss rates. A network level simulation of the type performed in [2] can be used to evaluate estimator performance under an emulation of RTCP, and hence capture a realistic representation of those features (correlation of block size with loss probes, imperfect overlap, response to group joins and leaves) which this paper has only represented through simple models. 16

References [1] Vijay Arya, Thierry Turletti, Timur Friedman, R´emy Bellino, and N. G. Duffield. Low Feedback MINC Loss Tomography. In IEEE INFOCOM Student Workshop, March 2005. [2] R. Caceres, N.G. Duffield, and T. Friedman. Impromptu measurement infrastructures using RTP. In IEEE INFOCOM, June 2002. [3] R. Caceres, N.G. Duffield, J. Horowitz, and D. Towsley. Multicast-based inference of network-internal loss characteristics. IEEE Transactions on Information Theory, 45(7):2462–2480, 1999. [4] N.G. Duffield, J. Horowitz, F. Lo Presti, and D. Towsley. Multicast topology inference from measured end-to-end loss. IEEE Transactions in Information Theory, 48:26–45, 2002. [5] T. Friedman (ed.), R. Caceres (ed.), A. Clark (ed.), K. Almeroth, R. G. Cole, N. Duffield, K. Hedayat, K. Sarac, and M. Westerlund. RTP control protocol extended reports (RTCP XR). RFC 3611, Internet Engineering Task Force, November 2003. [6] F. Lo Presti, N.G. Duffield, J. Horowitz, and D. Towsley. Multicast-based inference of network-internal delay distributions. IEEE/ACM Trans. Netw., 10(6):761–775, 2002. [7] Michael J Schervish. Theory of Statistics. Springer, 1995. [8] H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson. RFC 1889: RTP: A transport protocol for real-time applications, Jan 1996. [9] Neil Spring, Ratul Mahajan, and David Wetherall. Measuring ISP topologies with rocketfuel. In SIGCOMM, pages 133–145, 2002. [10] David Williams. Probability with Martingales. Cambridge University Press, 1991.

17

Lihat lebih banyak...

Comentarios

Copyright © 2017 DATOSPDF Inc.