Method and system for identifying lossy links in a computer network

• US 7,346,679 B2
• Filed: 01/31/2003
• Issued: 03/18/2008
• Est. Priority Date: 08/30/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Padmanabhan, Venkata N., Qiu, Lili
• Primary Examiner(s): Maung; Zarni
• Application Number:
  US10/356,059
• Publication Number:
  US 20040044764A1
• Time in Patent Office: 1,873 Days
• Field of Search: 709/224, 370/236.1, 379/112.1, 714/47
• US Class Current: 709/224
• CPC Class Codes: H04L 12/2854 Wide area networks, e.g. public data networks

Abstract

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, based on the loss rates, a number of possible sets of solutions for the loss rates at each of the links are generated. The sets of possible solutions are subjected to a statistical analysis. Based on the results of the analysis, a determination is made regarding which of the links are excessively lossy.

Claims

1. A method for identifying lossy links in a computer network tree, the computer network tree having a plurality of links, the method comprising:

(a) choosing a loss rate for a link of the plurality of links, the loss rate either being dictated by loss rates chosen for other links of the plurality of links, or being chosen from a range of numbers between, and including, zero and the minimum loss rate observed at one or more end nodes of the computer network tree, the link being along a path in the computer network tree to the end nodes;

(b) calculating a residual loss rate for one or more end nodes;

(c) repeating steps (a) and (b) for each link down the computer network tree by using the calculated residual loss rate from the previous link as the upper limit for the range of numbers, until a loss rate for each link has been either chosen at random or dictated by the loss rates of other links;

(d) conducting a statistical analysis using the loss rate for each link; and

(e) determining which of the links of the plurality of links are lossy based on the statistical analysis.

2. A computer-readable medium having stored thereon computer-executable instructions for performing the method of claim 1.

3. The method of claim 1, further comprising:

(f) repeating steps (a), (b) and (c) over a number of iterations, wherein step (d) comprises averaging the loss rates for each link over the number of iterations.