Optimal probing for unicast network delay tomography
View Patent ↗Systems and methods are disclosed to probe a network includes generating a set of probing pairs from a network topology for unicast network delay tomography; probing the network using monitoring hosts in the network; and determining network performance from the probing results.
1. A computer implemented method to probe a network, comprising:
a. generating a set of probing pairs from a network topology for unicast network delay tomography;
b. probing the network using monitoring hosts in the network;
c. determining network performance from the probing results; and
d. determining an observed information matrix (OIM) J,
wherein the OIM comprises determining
J
l
′
,
d
′
,
l
″
,
d
″
(
o
r
1
,
o
r
2
)
=
AL
-
D
l
′
,
d
′
D
l
″
,
d
″
L
2
and
J
(
o
r
1
,
o
r
2
)
=
(
J
l
′
,
d
′
,
l
″
,
d
″
(
o
r
1
,
o
r
2
)
)
as a matrix defining contributions to the OIM made by a pair of observations (o r 1 , o r 2 ), where (l′, d′) comprises a row index and (l″, d″) comprises a column index,
L is a likelihood function for a single pair of observations (o r 1 , o r 2 )
where the determination of D l*,d* , A comes from:
P ( D l* =d*,o r 1 ,o r 2 )= D l*,d* θ l*,d*
and
P ( D l′ =d′,D l″ =d″,o r 1 ,o r 2 )= Aθ l′,d′ θ l″,d″ for l′≠l″.
2. The method of claim 1 , comprising receiving network performance data and applying the network performance data to generate the set of probing host pairs.
3. The method of claim 1 , comprising determining a covariance matrix of a maximum likelihood estimator (MLE) for unicast network delay tomography to determine estimation accuracy.
4. The method of claim 1 , comprising determining a covariance matrix I −1 as an inverse of
I
=
∑
(
r
1
,
r
2
)
ω
(
r
1
,
r
2
)
(
r
1
,
r
2
)
where ω(r 1 , r 2 ) is the number of probing pair (r 1 ,r 2 ).
5. The method of claim 1 , comprising determining an optimal probing pair as an optimal experimental design problem.
6. The method of claim 5 , comprising determining the covariance matrix I −1 that corresponds to the most accurate estimation.
7. The method of claim 6 , comprising obtaining an optimal set of probing pairs using semi-definite programming (SDP).
8. The method of claim 7 , comprising obtaining an optimal set of probing pairs by selecting an optimal criteria from one of: E-Optimality to minimize the maximum eigenvalue of I −1 ; A-Optimality to minimize the trace of I −1 ; and D-Optimality to minimize the determinant of I −1 .
9. The method of claim 6 , comprising obtaining an optimal set of probing pairs using a greedy process.
10. The method of claim 1 , comprising designing a maximum likelihood estimator (MLE) with a minimum sum of variances by selecting an optimal set of monitoring probe pairs.
11. The method of claim 1 , comprising deriving a covariance matrix as the inverse of the Fisher information matrix for an observed information matrix on the network topology.
12. The method of claim 11 , comprising determining the observed information matrix using an upward-downward process.
13. The method of claim 1 , comprising probing different pairs of monitoring hosts to improve the estimation accuracy.
14. A system to probe a network, comprising
a. a sender computer and a plurality of receiver computers; and
b. a probe coupled to the sender and receiver computers, the probe generating a set of probing pairs from a topology a network for unicast network delay tomography and probing the network using monitoring hosts in the network;
with network performance from the probing results and an observed information matrix (OIM) J being determined, said OIM comprises determining
J
l
′
,
d
′
,
l
″
,
d
″
(
o
r
1
,
o
r
2
)
=
AL
-
D
l
′
,
d
′
D
l
″
,
d
″
L
2
and
J
(
o
r
1
,
o
r
2
)
=
(
J
l
′
,
d
′
,
l
″
,
d
″
(
o
r
1
,
o
r
2
)
)
as a matrix defining contributions to the OIM made by a pair of observations (o r 1 , o r 2 ) where (l′, d′) comprises a row index and (l″, d″) comprises a column index,
L is a likelihood function for a single pair of observations (o r 1 , o r 2 )
where the determination of D l*,d* ,A comes from:
P ( D l* =d*,o r 1 ,o r 2 )= D l*,d* θ l*,d*
and
P ( D l′ =d′,D l″ =d″,o r 1 ,o r 2 )= Aθ l′,d′ θ l″,d″ for l′≠l″.
15. The system of claim 14 , wherein the sender computer determines a covariance matrix of a maximum likelihood estimator (MLE) for unicast network delay tomography to determine estimation accuracy.
16. The system of claim 14 , wherein the sender computer determines a covariance matrix I −1 as an inverse of
I
=
∑
(
r
1
,
r
2
)
ω
(
r
1
,
r
2
)
(
r
1
,
r
2
)
where ω(r 1 , r 2 ) is the number of probing pair (r 1 ,r 2 ).
17. The system of claim 16 , wherein the sender computer determines the covariance matrix I −1 that corresponds to the most accurate estimation.
18. The system of claim 17 , wherein the sender computer determines an optimal probing pair as an optimal experimental design problem.
19. The system of claim 14 , wherein the sender computer determines an optimal set of probing pairs using semi-definite programming (SDP).
20. The system of claim 19 , wherein the sender computer determines an optimal set of probing pairs by selecting an optimal criteria from one of: E-Optimality to minimize the maximum eigenvalue of covariance matrix I −1 ; A-Optimality to minimize the trace of covariance matrix I −1 ; and D-Optimality to minimize the determinant of covariance matrix I −1 .