US 10,320,708 B2Granted

Latency reduction with pre-moving of distributed data and adaptive allocating of compute operations

AssigneeMicrosoft Technology Licensing, LLC

InventorsParamvir Bahl, Ganesh Ananthanarayanan, Srikanth Kandula, Peter Bodik, Qifan Pu, Srinivasa Aditya Akella

Life of this patent

Estimating the term…

Loading patent…

Abstract

Latency in responding to queries directed to geographically distributed data can be reduced by allocating individual steps, of a multi-step compute operation requested by the query, among the geographically distributed computing devices so as to reduce the duration of shuffling of intermediate data among such devices, and, additionally, by pre-moving, prior to the receipt of the query, portions of the distributed data that are input to a first step of the multistep compute operation, to, again, reduce the duration of the exchange of intermediate data. The pre-moving of input data occurring, and the adaptive allocation of intermediate steps, are prioritized for high-value data sets. Additionally, a threshold increase in a quantity of data exchanged across network communications can be established to avoid incurring network communication usage without an attendant gain in latency reduction.

Claims20

Dependent claims

A method of reducing latency of a multi-step compute operation that is performed by geographically distributed computing devices on a set of geographically distributed data, the method comprising the steps of:

predicting a duration of a first data exchange between a first computing device at a first geographical location and a second computing device at a second geographical location, the first data exchange comprising:
the first computing device transmitting a first portion of a first subset of intermediate data to the second computing device;
and
the second computing device transmitting a first portion of a second subset of the intermediate data to the first computing device;
wherein the first portions of the first and second subsets of the intermediate data are based on a first allocation, of processing of a subsequent step of a multi-step compute operation, among the first and second computing devices;
predicting a duration of a second data exchange between the first and second computing devices, the second data exchange comprising:
the first computing device transmitting a second portion of the first subset of the intermediate data to the second computing device;
and
the second computing device transmitting a second portion of the second subset of the intermediate data to the first computing device;
wherein the second portions of the first and second subsets of the intermediate data are based on a second allocation, of the processing of the subsequent step of the multi-step compute operation, among the first and second computing devices, the second allocation differing from the first allocation;
and
allocating, among the first and second computing devices, the processing of the subsequent step of the multi-step compute operation in accordance with the second duration is less than the first duration;
wherein the allocating causes the first computing device to transmit the second portion of the first subset of the intermediate data to the second computing device and further causes the second computing device to transmit the second portion of the second subset of the intermediate data to the first computing device;
and
wherein processing of a prior step of the multi-step compute operation by the first and second computing devices resulted in the first computing device locally generating the first subset of the intermediate data and second computing device locally generating the second subset of the intermediate data.

12 more elements

A system comprising:

a first computing device in a first geographic location having locally accessible to it a first subset of intermediate data, the first subset of the intermediate data having been locally generated by the first computing device processing a prior step of a multi-step compute operation;
a second computing device in a second, different geographic location having locally accessible to it a second subset of the intermediate data, the second subset of the intermediate data having been locally generated by the second computing device processing the prior step of the multi-step compute operation;
a communicational connection between the first and second computing devices allowing data to be provided from the first computing device to the second computing device faster than data can be provided from the second computing device to the first computing device;
and
one or more computer-readable media comprising computer-executable instructions, which, when executed, cause a computing device to:
predict a duration of a first data exchange between the first and second computing devices, the first data exchange comprising:
the first computing device transmitting a first portion of the first subset of the intermediate data to the second computing device;
and
the second computing device transmitting a first portion of the second subset of the intermediate data to the first computing device;
wherein the first portions of the first and second subsets of the intermediate data are based on a first allocation, of processing of a subsequent step of the multistep compute operation, among the first and second computing devices;
predict a duration of a second data exchange between the first and second computing devices, the second data exchange comprising:
the first computing device transmitting a second portion of the first subset of the intermediate data to the second computing device;
and
the second computing device transmitting a second portion of the second subset of the intermediate data to the first computing device;
wherein the second portions of the first and second subsets of the intermediate data are based on a second allocation, of the processing of the subsequent step of the multi-step compute operation, among the first and second computing devices, the second allocation differing from the first allocation;
and
allocate processing of the subsequent step of the multi-step compute operation among the first and second computing devices in accordance with the second allocation if the second duration is less than the first duration;
wherein the allocating causes the first computing device to transmit the second portion of the first subset of the intermediate data to the second computing device and further causes the second computing device to transmit the second portion of the second subset of the intermediate data to the first computing device.

15 more elements

A computing device comprising:

one or more processing units;
and
one or more computer-readable storage media comprising computer-executable instructions, which, when executed by at least some of the one or more processing units, cause the computing device to:
predict a duration of a first data exchange between a first computing device in a first geographic location and a second computing device in a second, different geographic location, the first data exchange comprising:
the first computing device transmitting a first portion of a first subset of intermediate data to the second computing device;
and
the second computing device transmitting a first portion of a second subset of the intermediate data to the first computing device;
wherein the first portions of the first and second subsets of the intermediate data are based on a first allocation, of processing of a subsequent step of a multi- step compute operation, among the first and second computing devices;
predict a duration of a second data exchange between the first and second computing devices, the second data exchange comprising:
the first computing device transmitting a second portion of the first subset of the intermediate data to the second computing device;
and
the second computing device transmitting a second portion of the second subset of the intermediate data to the first computing device;
wherein the second portions of the first and second subsets of the intermediate data are based on a second allocation, of the processing of the subsequent step of the multi-step compute operation, among the first and second computing devices, the second allocation differing from the first allocation;
and
allocate, among the first and second computing devices, the processing of the subsequent step of the multi-step compute operation in accordance with the second allocation if the second duration is less than the first duration;
wherein the allocating causes the first computing device to transmit the second portion of the first subset of the intermediate data to the second computing device and further causes the second computing device to transmit the second portion of the second subset of the intermediate data to the first computing device;
and
wherein processing of a prior step of the multi-step compute operation by the first and second computing devices resulted in the first computing device locally generating the first subset of the intermediate data and second computing device locally generating the second subset of the intermediate data.

15 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/948,217Filed 20 Nov 2015
Published: US 2017/0149691 A125 May 2017
Granted: 11 Jun 2019
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

H04L 43/16
Arrangements for monitoring or testing data switching networks: threshold monitoring
H04L 41/147
Network analysis or design: for predicting network behaviour
H04L 43/0852
Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters: delays
H04L 47/83
Admission control; Resource allocation: based on usage prediction

Family

US 2017/0149691 A1Pre-grant publication · published 25 May 2017
US 10,320,708 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key