Collaborative speed determination in distributed systems
AssigneeMicrosoft Corporation
InventorsJohn R. Douceur, James W. Mickens, Thomas Moscibroda, Debmalya Panigrahi
Life of this patent
Estimating the term…
Abstract
The described implementations relate to collaborative speed determination in distributed systems. One method estimates upload speeds of a plurality of hosts. The method sends a first bandwidth probe from a first host to a second host. The method receives, at the first host, a second bandwidth probe sent from the second host. The method determines which of the first and second bandwidth probes was relatively slower. The method designates either of the first or second hosts that sent the relatively slower bandwidth probe as a loser and takes a speed of the bandwidth probe of the loser as a first estimate of the loser's upload speed.
Claims20
A method for estimating upload speeds of a plurality of hosts, the method comprising:
- sending a first bandwidth probe from a first host of the plurality of hosts to a second host of the plurality of hosts;
- receiving, at the first host, a second bandwidth probe sent from said second host;
- determining which of the first and second bandwidth probes was relatively slower;
- in a first instance when the first bandwidth probe was relatively slower than the second bandwidth probe, taking a speed of the first bandwidth probe as a first estimate of upload speed for the first host;
- and
- in a second instance when the first bandwidth probe was relatively faster than the second bandwidth probe:
- repeatedly exchanging, by the first host, one or more additional bandwidth probes with one or more additional hosts of the plurality of hosts until an individual one of the additional bandwidth probes sent from the first host to an individual one of the additional hosts is determined by the first host to be relatively slower than a corresponding one of the additional bandwidth probes received from the individual additional host, and
- taking a speed of the individual additional bandwidth probe sent from the first host that was determined to be relatively slower than the corresponding one of the additional bandwidth probes received from the individual additional host as the first estimate of upload speed for the first host.
One or more computer-readable storage devices comprising instructions which, when executed by one or more computing devices, cause the one or more computing devices to perform:
- sending a first bandwidth probe of a first host to a second host of a plurality of hosts;
- receiving, at the first host, a second bandwidth probe sent from said second host;
- determining which of the first and second bandwidth probes was relatively slower;
- designating either of the first or second hosts that sent the relatively slower bandwidth probe as a loser;
- designating the other of the first or second hosts that did not send the relatively slower bandwidth probe as a winner;
- taking a speed of the relatively slower bandwidth probe as a first estimate of upload speed for the loser;
- and
- exchanging additional bandwidth probes between the winner and a third host of the plurality of hosts to estimate the upload speed of the winner or the third host,
- wherein in exchanging the additional bandwidth probes, an additional winner and an additional loser is designated, and the speed of a relatively slower additional bandwidth probe that was sent by the additional loser is taken as an estimate of upload speed of the additional loser.
A system comprising:
- a speed determining mechanism configured to:
- cause a first host of a plurality of hosts to send a first bandwidth probe to a second host of the plurality of hosts;
- cause the first host to receive a second bandwidth probe sent from said second host;
- determine which of the first and second bandwidth probes was relatively slower;
- in a first instance when the first bandwidth probe was relatively slower than the second bandwidth probe, take a speed of the first bandwidth probe as a first estimate of upload speed of the first host;
- in a second instance when the first bandwidth probe was relatively faster than the second bandwidth probe
- cause the first host to repeatedly exchange one or more additional bandwidth probes with one or more additional hosts from the plurality of hosts until an individual one of the additional bandwidth probes sent from the first host to an individual one of the additional hosts is determined to be relatively slower than a corresponding one of the additional bandwidth probes received from the individual additional host, and
- take a speed of the individual additional bandwidth probe sent from the first host that was determined to be relatively slower than the corresponding one of the additional bandwidth probes received from the individual additional host as the first estimate of upload speed for the first host;
- and
- one or more processors configured to execute the speed determining mechanism.
Dependencies are inferred from the claim text.