Transcript Slide 1

Estimating Network Internal Loss Behavior from End-to-End Multicast Measurements
EM for Link Loss Type 2: Gibbs
sampling
Sinem Coleri and Mustafa Ergen
University of California Berkeley
(csinem,ergen)@eecs.berkeley.edu
Loss Modeling: Type 1
Multi-cast Tomography
Motivation
• Tree structure
• Motivation for determining loss behavior of
links
• Useful for dynamic routing
• Useful for video coding
– Independent loss
characteristic at each
probe sampling
– Only at the leaves
• Basic idea:
– Decreases computation and communication
overhead
– Eliminates administrative problems such as
gaining access to internal nodes, introducing new
measurement mechanisms
– Estimating the loss
probability of each link by
exploiting the correlation
between the receiver traffic
characteristics sharing
common subpaths
• Motivation for using multicast traffic
– 2-state Markov Chain at
each link
• Xn,0=1 for all n
• If Xn,k=1
• then for j a child of k
• Xn,0=1 for all n
• If Xn,k=1
• then for j a child of k
• Traffic measurement
• Motivation for estimating link loss instead of
measuring
• Markov temporal
correlations
• No temporal correlation
– Root of the tree:source of
multi-cast probes
– Leaves of the tree: multi-cast
receivers
– Detects congestion, routing faults, anomalous
traffic
Loss Modeling: Type 2
– Xn,j=1 wp. P1,j if Xn-1,j=0
– Xn,j=0 wp. P0.j if Xn-1,j=1
– Xn,j=1 wp. j
– Xn,j=0 wp. (1- j)
• else for j a child of k
T=(V,L) logical tree
– Xn,j=0
EM for Link Loss Type 2:
Completely Factorized Variational
Approximation
• else for j a child of k
– Xn,j=0
P1,j
0
1
P0,j
– Efficiency due to packet duplication
EM for Link Loss Type 2: Structured
Variational Approximation
Estimation Based on Loss
Modeling Type 1: Direct Approach
Estimation Based on Loss
Model Type 1
•
• Outcome of probe is whether or not packets
received at the leaves, XR=(Xk) kR
• Probability mass function of XR for a single
outcome x and given set of link probabilities  =
(k)kV is p(x; )
• The log likelihood function for N independent
observations is
L( )  log p( x1 , x 2 ,...,x N ) 
N

log p( x n ; )
•
•
Based on the solution of likelihood equation dL/dk = 0, kV without any range
restriction on  to find its unique solution under some conditions and then proving
that this result converges to MLE estimate as the number of observations goes to
infinity
Let (k) be the set of outcomes x st. xj=1 for at least one receiver jR, which is a
descendant of k
Let k=P((k)) and the estimate of k given by
ˆk 
 pˆ ( x) where pˆ ( x) is the observed
proportion of times outcome x is obtained
x ( k )
•
Then the unique solution to likelihood eqn is given by
– Define (Ak) kV st.
• A0=1, Ak= k for kR and for all the other nodes, Ak is the soln of the
followingˆ equation
ˆ
1
k
Aˆ k

 (1  Aˆ )
j
jd ( k )
Estimation Based on Loss
Model Type 1: EM Algorithm
• Expected complete log likelihood is given by
E ( L( , x)) 
 
N
n 1
(i , j )L
jd (i )
E ( X n,i X n, j ) log(1, j )  E ( X n,i (1  X n, j )) log(1  1, j ) 
E ((1  X n,i )(1  X n, j )) log( 2, j )  E ((1  X n,i ) X n, j ) log(1   2, j )
• E-step
• Sum-product algorithm
• M step
• MLE estimate of  in the case of complete data
k
– For k V\{0}, k=Ak/Af(k) where f(k) is parent of k in the tree
n 1
ˆ j  ˆ1, j 


Estimation Based on Loss
Modeling Type 2: EM Algorithm
• M step
• MLE estimate of transition probabilities in the
case of complete data
E ((1  X ) X X
)


 E((1  X ) X )
E ( X (1  X ) X
)


 E( X X )
N
p1, j
N
n 1
E ( X n, f ( j ) )
n, j
n 1, j
n2
n, f ( j )
n, f ( j )
N
p0, j
n 1, j
n2
n, j
n, f ( j )
N
n 1, j
n2
N
E ( X n, j )
n 1
n 1, j
n2
N
n, f ( j )
P1,j
0
1
Converged Values of
Approximation Methods
P0,j
Gibbs
Estimation Based on Loss
Modeling Type 2: EM
Algorithm
Convergence of Direct
Estimation Based on Loss Type 1
q
n,1
•Convergence time increases
( X n,1 )qn,2 ( X n,2 )qn,3 ( X n,3 )
•EM and direct estimation behaves almost the same as the
number of samples increases
•EM is almost the clipped version of direct estimation for
small sample values
N
n,1
Conclusion
•Independent link loss assumption for different probes
• Structured variational
approximation(forest of trees)
q
0.55
0.45
0.43
0.65
0.39
0.6
0.82
0.29
0.73
0.64
0.26
0.79
0.6
0.64
•Estimating link loss behavior by multicast probes
n 1
Q({X n,1, X n,2 , X n,3} |  ) 
EM for Link Loss Type 1
Result of application of EM for link loss type 1 to a tree with
2-state Markov temporal correlations
• E-Step
• Gibbs sampling
• Completely factorized
variational approximation
N
Q({X n,1, X n,2 , X n,3} |  ) 
Comparison of Direct Estimation
and EM for Link Loss Type 1
p11=0.7
p10=0.6
p21=0.7
p20=0.6
p31=0.7
p30=0.6
p41=0.8
p40=0.2
p51=0.7
p50=0.6
p61=0.2
p60=0.8
p71=0.7
p70=0.6
Factorized Structured
0.56
0.56
0.44
0.46
0.43
0.57
0.71
0.57
0.31
0.72
0.69
0.3
0.94
0.95
0.07
0.09
0.65
0.73
0.67
0.63
0.27
0.23
0.78
0.82
0.69
0.67
0.56
0.59
•2-state Markov temporal dependence for subsequent probes
( X n,1 )qn,2 ( X n,2 | X n,1 )qn,3 ( X n,3 | X n,1 )
n1
All simulations are performed in MATLAB for 4-leaf tree
•Structured variational approximation better than
completely factorized variational approximation
•Structured variational sometimes better than Gibbs
sampling due to maybe not enough sampling for Gibbs