Unformatted text preview:

Proceedings of the jsr Conference on Decision & Control Phoenix, Arizona USA December 1999 ThMOZ 1320 Loss-based Inference of Multicast Network Topology R. C&ceres *, N.G. Duffield *, J. Horowitz 5, E Lo Presti *> 5, D. Towsley 5 * AT&T Labs-Research Abstract The use of multicast inference on end-to-end measurement has recently been proposed as a means to infer network in- ternal characteristics such as packet loss rate and network topology. In this paper we propose and evaluate new algo- rithms for multicast topology inference based on measure- ment of end-to-end loss. We compare their accuracy and comment on their computational complexity. 1 Introduction Inference of network-internal characteristics from the end- to-end behavior of multicast traffic has been proposed in recent papers. Probes are multicast from the source to re- ceivers; the record of which probes reached each receiver is used to infer internal loss probabilities. Probe loss is assumed to occur independently across links and between probes. In [ 1,2] the Maximum Likelihood Estimator (MLE) of link loss probabilities was determined for general logical multicast trees. It was shown that the estimator is reason- ably robust with respect to violations of this assumption, at least on the scale found in realistic network simulations. In a related paper [SI, the focus was to group multicast re- ceivers that share the same set of network bottlenecks from the source. This used the special case of the estimator for binary trees in [ 11 in order to estimate loss on the common portion of the path from the source to each receiver. An ex- tension of the binary approach to treat more general trees was also proposed. The contributions of the present paper are as follows: (i) We propose three algorithms for topology identification; these generalize the grouping algorithms of [5]. Two of these use binary grouping as an intermediate stage of iden- tification; the other uses the approach of [ 1, 21 to estimate the loss on the common portion the paths from the source 'This work was sponsored in part by the DARPA and the Air Force Research Laboratory under agreement F30602-98-2-0238, Ram6n Cbceres, Nick Duffield, Francesco Lopresti; AT&T Labs-Research, Rm. (B12.5, 8139, B130}, 180 Park Avenue, Florham Park, NJ 07932, USA. E-mail: {ramon,duffield,lopresti}@research.att.com Joseph Horowitz, Dept of Math. & Statistics, University of Massachusetts, Amherst. MA 01003-4515 USA; E-mail: joeh4math.umass. edu Don Towsley, Dept. of Computer Science, University of Massachusetts, Amherst, MA 01003-4610,USA; E-mail: towsley@cs .umass. edu 6-7803-5250-5/99/$10.00 Q 1999 IEEE 3065 5 University of Massachusetts to an arbitrary set of receivers (i.e. not necessarily a binary set). (ii) We propose an algorithm that uses the MLE from [ 11 di- rectly. In this approach, for each possible tree built upon the given set of receivers, the MLE for its link probabilities is found and the corresponding likelihood function is calcu- lated. The tree that maximizes the this likelihood function is selected as the estimator. We establish that the probability of selecting the actual tree converges to 1 as the number of probes grows to infinity. (iii) We compare the performance of the algorithms and dis- cuss the interactions between parameter choices and under- lying topology that determine their accuracy The use of end-to-end measurement has the advantage of not requiring cooperation from network management. The use of multicast probes has the advantage over unicast probes that the network load due to probes scales better for large trees. For a more detailed discussion of implementa- tional issues, the potential for deployment on emerging In- ternet measurement infrastructures, and a comparison with other approaches, we refer the reader to [ 11. 2 Description of the Loss Inference Methodology We identify the physical multicast tree as comprising actual network elements (the nodes) and the communication links than join them. The logical multicast tree comprises the branch points of the physical tree, and the logical links be- tween them. The logical links comprise one or more physi- cal links. Thus each node in the logical tree, except the leaf nodes and possibly the root, must have 2 or more children. We can construct the logical tree from the physical tree by deleting all links with one child and adjusting the links ac- cordingly by directly joining its parent and child. Let T = (V, L) denote a logical multicast tree with nodes V and links L. We identify one node, the root 0, to be the source of probes, and R c V to be the set of leaf nodes (identified as the set of receivers). The set of children of node j E V is denoted by d(j). Each node, k, apart from the root has a parent j = f(k) such that (j, IC) E L. We say j is descended from IC, and write j 4 k, if k = f"(j) for some n E N, where f" = f o fn-' and f' = f. a(S) will denote the +-least common ancestor of all nodes in V c S.We assume a Bernoulli loss model in which probes are in- dependent and each probe is successfully transmitted across the link (f(k), k) with probability ak. Thus the progress of each probe down the tree is described by an indepen- dent copy of a stochastic process X = (Xk)kEV as follows. Xk = 1 if the probe reaches node k E V and 0 otherwise. If xk = 0, then xj = 0,Vj E d(k). Otherwise, P[Xj = 1lXk = 11 = aj and P[xj = OlXr, = 11 = 1 - aj. we adopt the convention a0 = 1. Last, let a = (ai)iE~. We assume that 0 < ak < 1, b’k E v. Pa will denote the distribution of X under the link probabilities a. When a probe is sent down the tree from the root 0, we cannot observe the whole process X, but only the outcome (Xk)kcR E = (0, that indicates whether or not the probe reached each receiver. In [l] it was shown how the link probabilities can be inferred from the measured distri- bution of outcomes due to a set of independent probes when the topology T = (V, 15) is known. Let R(k) c R denote the set of receivers descended from a node k E V. Set Y(k) = max Xj, and y(k) = P[Y(k) = 13. (1) j’ER(k) Y (k) = 1 if a probe reaches at least one receiver descended from k. For j E V set A(j) = ajaf(j) . . .(YO, the probabil- ity that a probe reaches the node j. It can be shown that the A and the y satisfy (1 - y(k)/A(k)) = n (1 - 7(j)/A(k)). (2) j€W) It was shown in Lemma 1 of [ 11 that A( k) is the unique solu- tion to (2) in (y(k),


View Full Document
Download Loss-based Inference of Multicast Network Topology
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Loss-based Inference of Multicast Network Topology and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Loss-based Inference of Multicast Network Topology 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?