Maximum likelihood estimationSlide 2Properties of estimatorsProperties of MLENetwork TomographySlide 6Slide 7Slide 8Why end-to-endNaive Approach: INaive Approach: IISlide 12Slide 13Slide 14Slide 15Naive Approach: IIIBottom LineMINC (Multicast Inference of Network Characteristics)Slide 19Slide 20Slide 21Slide 22Multicast-based Loss EstimatorLoss Estimation on Simple Binary TreeGeneral Loss Estimator & PropertiesStatistical Properties of Loss EstimatorImpact of Model ViolationMINC: Simulation ResultsMINC: Experimental ResultsValidating MINC on a real networkMINC: Mbone ResultsTopology InferenceGeneral Approach to Topology InferenceBLTP AlgorithmExampleSlide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Theoretical ResultResultsIssues and Challenges1Maximum likelihood estimationExample: X1,…,Xn – i.i.d. random variables with probability pX(x|θ) = P(X=x) where θ is a parameterlikelihood function L(θ|x) where x=(x1,…,xn) is set of observationsmaximum likelihood estimate maximizer of L(θ|x)niiXxpxL1)|()|()(ˆx2typically easier to work with log-likelihood function, C(θ|x) = log L(θ|x)3Properties of estimatorsestimator is unbiased if is asymptotically unbiased if as n→∞)(ˆx)](ˆ[ xE)(ˆx)](ˆ[ xE4Properties of MLEasymptotically unbiased, i.e.,asymptotically optimal, i.e., has minimum variance as n→∞invariance principle, i.e., if is MLE for θ then is MLE for any function τ(θ) nx as)(ˆ)(ˆx)(ˆx))(ˆ( x5Network TomographyGoal: obtain detailed picture of a network/internet from end-to-end viewsinfer topology /connectivity6Network TomographyGoal: obtain detailed picture of a network/internet from end-to-end viewsinfer link-levellossdelayavailable bandwidth. . .7Brain Tomographyunknown objectcounting &projectionMaximumlikelihood estimateperforminferenceinverse function problemdata statistical model brain model8Network Tomographyrouting &countingdataqueuing behaviorbinomialperforminferenceinverse function problem9Why end-to-endno participation by network neededmeasurement probes regular packetsno administrative access neededinference across multiple domainsno cooperation requiredmonitor service level agreements reconfigurable applicationsvideo, audio, reliable multicast10Naive Approach: IM1M2D0D1D2Di - one way delayD0 +D1= M1D0 +D2= M22 equations, 3 unknowns {Di} not identifiable11D’0D’2D’1Naive Approach: IID0D1D2D0 + D1D0 +D2bidirectional tree12Naive Approach: IID’0D’2D’1D0D1D2D0 + D1D0 +D2D’2+ D1bidirectional tree13Naive Approach: IID’2+ D1D’1+D2D’0D’2D’1D0D1D2D0 + D1D0 +D2bidirectional tree14D’0D’2D’1Naive Approach: IID’0 +D’1D’0 +D’2D’2+ D1D’1+D2D0D1D2D0 + D1D0 +D2bidirectional tree15Naive Approach: IIbidirectional treeD’0D’2D’1D’0 +D’1D’0 +D’2D’2+ D1D’1+D2D0D1D2D0 + D1D0 +D2not linearly independent! (not identifiable)6 equations, 6 unknowns16Naive Approach: IIIRound trip link delays:ABCR1RAB = R0 + R1RAC = R0 + R2RBC = R1 + R2Linear independence! (identifiable)true for general treescan infer some link delays within general graphR2R017Bottom Linesimilar approach for lossesyields round trip and one way metrics for subset of linksapproximations for other links18MINC (Multicast Inference of Network Characteristics)multicast probescopies made as needed within networkreceiverssourcereceivers observe correlated performanceexploit correlation to get link behaviorloss ratesdelaysa1a2a319multicast probescopies made as needed within networkMINC (Multicast Inference of Network Characteristics)receivers observe correlated performanceexploit correlation to get link behaviorloss ratesdelaysα1α2α320MINC (Multicast Inference of Network Characteristics)receivers observe correlated performanceexploit correlation to get link behaviorloss ratesdelaysα1α2α3xmulticast probescopies made as needed within network21MINC (Multicast Inference of Network Characteristics)receivers observe correlated performanceexploit correlation to get link behaviorloss ratesdelaysα1α2α3xmulticast probescopies made as needed within network22MINC (Multicast Inference of Network Characteristics)      estimates of α1, α2, α3receivers observe correlated performanceexploit correlation to get link behaviorloss ratesdelaysα1α2α3multicast probescopies made as needed within network23Multicast-based Loss Estimatortree model known logical mcast topologytree T = (V,L) = (nodes, links)source multicasts probes from root nodeset R  V of receiver nodes at leavesloss modelprobe traverses link k with probability loss independent between links, probesdatamulticast n probes from sourcedata Y={Y(j,i), j  R, i=1,2,…,n} •Y(j,i) = 1 if probe i reaches receiver j, 0 otherwisegoalestimate set of link probabilities  = {k : k V} from data YProbe sourcekk24Loss Estimation on Simple Binary Treeeach probe has one of 4 potential outcomes at leaves(Y(2),Y(3))  { (1,1), (1,0), (0,1), (0,0) }calculate outcomes’ theoretical probabilitiesin terms of link probabilities {1, 2, 3} measure outcome frequenciesequatesolve for {123}, yielding estimateskey stepsidentification of set of externally measurable outcomesknowing probabilities of outcomes  knowing internal link probabilities2 312310SourceReceivers1011113011111211011110111ˆˆˆˆ,ˆˆˆˆ,ˆ)ˆˆ)(ˆˆ(ˆppppppppppp,ˆ,ˆ,ˆ,ˆ00011011pppp,,,,00011011pppp pp withˆ25General Loss Estimator & PropertiesCan be done, details see R. Cáceres, N.G. Duffield, J. Horowitz, D. Towsley, ``Multicast-Based Inference of Network-Internal Loss Characteristics,'' IEEE Transactions on Information Theory, 1999 Probe sourcekreceivers R(k)descended from k26Statistical Properties of Loss Estimatormodel is identifiabledistinct parameters { k }  distinct distributions of losses seen at leaves Maximum Likelihood Estimatorstrongly consistent (converges to true value)asymptotically normal (MLE efficient [ minimum asymptotic variance])kkknn