초록 ▼

A computer network has links for carrying data among computers, including one or more client computers. Packet loss rates are determined for the client computers and, a system of equations is set up expressing the relationship between the loss rates at the client computers and the loss rates at the

A computer network has links for carrying data among computers, including one or more client computers. Packet loss rates are determined for the client computers and, a system of equations is set up expressing the relationship between the loss rates at the client computers and the loss rates at the links. The system of equations is then solved using one or more linear programming techniques, and optimized by making an effort to find the most parsimonious solution.

대표청구항 ▼

We claim: 1. A method for determining which of a plurality of links of a computer network are lossy, the network comprising a plurality of clients that communicate with a server over one or more of the plurality of links, the method comprising: establishing a system of equations that describes the

We claim: 1. A method for determining which of a plurality of links of a computer network are lossy, the network comprising a plurality of clients that communicate with a server over one or more of the plurality of links, the method comprising: establishing a system of equations that describes the relationship between the packet loss rates at the links and the packet loss rates at the clients; setting up constraints on the possible solutions to the system of equations; linearizing the constraints; deriving an objective function that represents both an aggregation of the packet loss rates for the plurality of links and an aggregate slack in the constraints, wherein the objective function comprises ΣiLi+Σj|SJ|, wherein Li=log(1/(1-li)) and li is the loss rate of link i of the plurality of links and wherein Sj is a slack variable representing the extent to which the constraint can be violated; calculating loss rates that solve the system of equations and give a minimum possible value for the function; and storing the calculated loss rates in a memory. 2. A computer-readable storage medium encoded with computer-executable instructions for performing the method of claim 1. 3. The method of claim 1 wherein each of the equations in the system expresses a product of success rates of links that form a path between the server and a particular client, wherein the product is the success rate of the particular client. 4. The method of claim 1 wherein one of the constraints is expressible as 1-ΠiεTj (1-li) =pj, and wherein Tj is the set of links on a path from the server to the client Cj, li is the loss rate of link i, and pj is the end-to-end loss rate between the server and the client Cj. 5. The method of claim 4 wherein linearizing the constraints includes applying a log-transformation on each of the constraints so it becomes expressible as ΣiεT Li =Pj, where Li=log(1/(1/-li) and Pj=log(1/(1-pj). 6. The method of claim 1 wherein each of the plurality of clients communicates with the server over a subset of the plurality of links. 7. The method of claim 1 wherein the objective function further comprises a slack variable representing the extent to which each of the constraints may be violated in calculating the minimum possible value of the function. 8. The method of claim 1, wherein the objective function comprises w ΣiLi,+Σj|Sj|, wherein w represents a relative importance of a parsimonious solution. 9. In a computer network comprising a plurality of links and a plurality of end nodes, a method for determining which one or more links of the plurality of links are lossy, wherein each link has a loss rate representing a rate at which data packets are lost on the link, and a success rate representing a rate at which packets are successfully transmitted over the link, the method comprising: establishing constraints relating the loss rates of the links and packet loss rates at the end nodes; introducing slack variables allowing the constraints to be violated to an extent; optimizing a function by minimizing (1) an aggregation of the loss rates of the links and (2) an aggregation of the slack variables, wherein the function is expressible in terms comprising ΣiLi+Σj|SJ|, wherein Li=log(1/(1-li) and liis the loss rate of link i of the plurality of links and wherein Sj is a slack variable representing the extent to which the constraints can be violated; identifying from the optimization any links that violate a threshold value for loss rates or success rates; and storing the identified links in a memory. 10. The method of claim 9 wherein the function comprises a sum of a logarithm of an inverse of the success rates of the plurality of links. 11. The method of claim 10 wherein the function also comprises an aggregate slack in the set of constraints. 12. A computer-readable storage medium encoded with computer-executable instructions for performing the method of claim 9. 13. The method of claim 9 wherein at least one of the constraints is expressed as 1-ΠiεTj (1-li)=pj, and wherein Tj is the set of links on the path between nodes, li is the loss rate of link i, and pj is the end-to-end loss rate between the nodes. 14. The method of claim 13, further comprising converting the constraint into a linear constraint that is expressible as ΣiεTj Li=Pj, where Li=log(1/(1-li)) and Pj=log(1/(1-pj)). 15. The method of claim 14, wherein the function is expressible in terms comprising wΣiLi, +Σj|SJ|, wherein w represents a relative importance of a parsimonious solution. 16. On a computer network comprising a plurality of links, each of the plurality of links having associated therewith a rate of loss for data attempting to pass through the link, a method for identifying a lossy link, comprising: modeling the network connections among nodes on the network so as to define loss rates for each connection and infer loss rates for each of the links comprising the connection; identifying which links in the connections have inferred loss rates that exceed a predetermined rate, wherein the modeling of the network connections includes choosing the loss rate for each of the plurality of links so as to minimize a function comprising a summation over all of the links of the logarithm of the inverse of success rates for the plurality of links, and wherein the function also comprises an aggregate slack in a set of constraints, wherein the function is expressible in terms comprising ΣiLi+Σj|SJ|, wherein Li=log(1/(1-li)) and li is the loss rate of link i of the plurality of links and wherein Sj is a slack variable representing the extent to which the constraints can be violated; and storing the identified links in a memory. 17. A computer-readable storage medium encoded with computer executable instructions for performing the method of claim 16. 18. The method of claim 16 wherein the function is expressible in terms comprising wΣiLi+Σj|SJ|,wherein w the relative importance of finding a parsimonious solution. 19. In a computer network having a plurality of links connecting a server to client computers and carrying data traffic between the server and client computers, a system for determining which of the plurality of links are lossy, the system comprising: a model comprising (1) constraints relating packet loss rates at the links and packet loss rates at the clients, (2) slack variables relaxing the constraints, and, (3) a function representing both an aggregation of the packet loss rates for the plurality of links and an aggregation of the slack variables, wherein the function is expressible in terms comprising ΣiLi+Σj|SJ|, wherein Li=log(1/(1-li)) and li is the loss rate of link i of the plurality of links and wherein Sj is a slack variable representing the extent to which the constraints can be violated; means for solving the model by finding a minimum value for the function, which thereby yields loss rates for the links in the network; and means responsive to the yielded loss rates for identifying lossy links and storing the identified lossy links in a memory. 20. The system of claim 19 wherein the model resides at the server. 21. The system of claim 20 wherein the means for solving and identifying is the server computer executing an analysis program. 22. The method of claim 1, wherein the method is performed without injecting test data into the computer network. 23. The method of claim 9, wherein the method is performed without injecting test data into the computer network.