Systems and methods for partitioning end-to-end performance effects using network tomography
View Patent ↗Systems and methods are presented for partitioning end-to-end performance effects using network tomography. In one embodiment, a method for partitioning end-to-end performance effects within a network is presented. The method includes determining a network topology between at least two test points, obtaining an unrelated approximation of edge effects between the test points, measuring end-to-end performance data between the test points corresponding to a target application, regularizing an estimate of edge effects for the target application using the unrelated approximation of edge effects, and computing the estimate of edge effects for the target application to partition the end-to-end effects.
1. A method for partitioning end-to-end performance effects within a network, comprising:
determining a network topology between at least two test points;
obtaining an unrelated approximation of edge effects between the test points;
measuring end-to-end performance data between the test points corresponding to a target application;
regularizing an estimate of edge effects for the target application using the unrelated approximation of edge effects; and
computing the estimate of edge effects for the target application to partition the end-to-end effects.
2. The method according to claim 1 , further comprising:
collecting traceroute data between the at least two test points;
utilizing the traceroute data to determine an end-to-end routing matrix and the unrelated approximation of edge effects; and
performing a constrained optimization of a first mathematical model which relates the estimate of edge effects for the target application with the end-to-end routing matrix and the end-to-end performance data.
3. The method according to claim 2 , wherein the constrained optimization of the first mathematical model includes a non-negative least squares algorithm.
4. The method according to claim 1 , wherein the obtaining the unrelated approximation further comprises:
collecting traceroute data between the at least two test points;
determining a partial path routing matrix based upon the traceroute data;
determining intermediate round trip times based upon the traceroute data;
performing isotonic regression on the intermediate round trip times to obtain a non-decreasing sequence;
computing edge effects by subtraction of successive results of the non-decreasing sequence; and
combining the edge effects of values which correspond to a same edge to remove redundant measurements.
5. The method according to claim 4 , wherein the performing isotonic regression further comprises:
monotonically smoothing the intermediate round trip times using a pool adjacent violators algorithm.
6. The method according to claim 4 , wherein the combining further comprises:
computing an average or a median value to combine the redundant measurements.
7. The method according to claim 1 , wherein the obtaining the unrelated approximation of edge effects further comprises:
collecting traceroute data between the at least two test points;
determining a partial path routing matrix using the traceroute data;
determining intermediate round trip times using the traceroute data; and
computing the unrelated approximation of edge effects based upon the partial path routing matrix and the intermediate round trip times.
8. The method according to claim 7 , wherein the computing the unrelated approximation of edge effects further comprises:
performing a constrained optimization of a second mathematical model which relates the unrelated approximation of edge effects with the partial path routing matrix and the intermediate round trip times.
9. The method according to claim 8 , wherein the second mathematical model is
{circumflex over (β)} TR arg min β>0 ∥z−Tβ∥ 2
where
{circumflex over (β)} TR is a vector representing the unrelated approximation of edge effects,
z is a vector of the intermediate round trip times,
T is the partial path routing matrix, and
β is an unknown vector representing non-negative edge estimates.
10. The method according to claim 8 , wherein the constrained optimization includes a non-negative least squares algorithm.
11. The method according to claim 2 , wherein the first mathematical model is
{circumflex over (β)} penalized =arg minβ> 0 ∥y−Rβ∥ 2 +λ∥β−{circumflex over (β)} 0 ∥ 2
where
{circumflex over (β)} penalized is a vector representing the estimate of edge effects for the target application,
{circumflex over (β)} 0 is a vector representing the unrelated approximation of edge effects,
y is a vector representing the measured end-to-end performance data for the target application,
R is the end-to-end routing matrix,
λ is a scalar regularization parameter, and
β is an unknown vector representing non-negative edge estimates for the target application.
12. The method according to claim 11 , wherein the regularization parameter is between 0.00001 and 0.001.
13. The method according to claim 1 , wherein the determining a network topology further comprises:
collecting traceroute data between the at least two points;
reducing the traceroute data to determine edges which comprise at least one path between the at least two points; and
creating an end-to-end routing matrix based upon the reduced traceroute data.
14. The method according to claim 1 , wherein the application includes Voice over Internet Protocol (VoIP) Telephony.
15. The method according to claim 2 , further comprising:
determining the selection of test points based upon a computation of rank of the end-to-end routing matrix.
16. The method according to claim 2 , further comprising:
determining fractional packet loss for each TTL value based upon the traceroute data to produce a loss vector;
performing isotonic regression on the loss vector; and
computing a logarithmic transformation on the isotonically regressed loss vector.
17. The method according to claim 1 , wherein the method is used to determine the performance of a network based upon effects of nodes.
18. A method for determining an unrelated approximation of edge effects within a network, comprising:
collecting traceroute data between at least two test points;
determining a partial path routing matrix based upon the traceroute data;
determining intermediate round trip times based upon the traceroute data;
performing isotonic regression on the intermediate round trip times to obtain a non-decreasing sequence;
computing edge effects by subtraction of successive results of the non-decreasing sequence; and
combining the edge effects of values which correspond to a same edge to remove redundant measurements.
19. The method according to claim 18 , wherein the performing isotonic regression further comprises:
monotonically smoothing the traceroute data using a pool adjacent violators algorithm.
20. The method according to claim 18 , wherein the combining further comprises:
computing an average or a median value to combine the duplicate measurements.
21. A method for partitioning end-to-end effects within a network, comprising:
collecting traceroute data between the at least two test points;
determining an end-to-end routing matrix between at least two test points using the traceroute data;
obtaining an unrelated approximation of edge effects between the test points using the traceroute data;
measuring end-to-end performance data between the test points corresponding to a target application; and
computing an estimate of edge effects for the target application by utilizing the unrelated approximation of the edge effects as a regularization term.
22. The method according to claim 21 , wherein the obtaining the unrelated approximation further comprises:
monotonically smoothing the traceroute data using a pool adjacent violators algorithm; and
combining the smoothed traceroute data to remove duplicate measurements resulting from edges appearing multiple times within a path between the test points.
23. The method according to claim 22 , wherein the combining further comprises:
computing an average or a median value to combine the duplicate measurements.
24. The method according to claim 21 , wherein the obtaining the unrelated approximation of edge effects further comprises:
determining a partial path routing matrix using the traceroute data;
determining intermediate round trip times using the traceroute data; and
computing the unrelated approximation of edge effects based upon the partial path routing matrix and the intermediate round trip times.
25. An apparatus for partitioning end-to-end performance effects within a network, comprising:
a memory storing a set of instructions; and
a processor executing the stored set of instructions for
determining a network topology between at least two test points,
obtaining an unrelated approximation of edge effects between the test points,
measuring end-to-end performance data between the test points corresponding to a target application,
regularizing an estimate of edge effects for the target application using the unrelated approximation of edge effects, and
computing the estimate of edge effects for the target application to partition the end-to-end effects.