Network routing modifications for distribution of data

• US 9,647,932 B2
• Filed: 06/06/2016
• Issued: 05/09/2017
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Maltz, David A., Burger, Douglas Christopher, Harper, III, David T.
• Primary Examiner(s): ABU ROUMI, MAHRAN Y
• Application Number:
  US15/175,022
• Publication Number:
  US 20160294679A1
• Time in Patent Office: 337 Days
• Field of Search: 709223
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 49/252 Store and forward routing
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

The transmission of multiple copies of data to other computing devices is optimized by minimizing the number of copies of such data transmitted through an expensive portion of the network. A store-and-forward methodology is utilized to transmit only a single copy through the expensive portion and the data is subsequently forked into multiple copies directed to multiple destination computing devices. Computing devices that are not intended destinations can be conscripted as intermediate computing devices, if appropriate to minimize copies of the data transmitted through an expensive portion. Additionally, accommodation can be made for data that is intolerant of out-of-order delivery by utilizing adaptive protocols that avoid mechanisms that may result in out-of-order delivery for data intolerant of such and by utilizing packet sorting at data convergence points to reorder the data. Different protocol settings can be utilized to transmit data across different portions of the network.

Claims

1. A method of distributing data to multiple computing devices, the method comprising the steps of:

identifying (1) a source computing device comprising the data and (2) at least two intended destination computing devices to which copies of the data will be distributed;

identifying at least one expensive network segment that is part of both a first network path between the source computing device and a first of the at least two intended destination computing devices and a second network path between the source computing device and a second of the at least two intended destination computing devices, such that multiple copies of the data would be transmitted, separately, along the identified expensive network segment;

identifying an intermediate computing device such that data transmitted from the source computing device to the intermediate computing device would be transmitted along the identified expensive network segment, but data transmitted from the intermediate computing device to multiple ones of the at least two intended destination computing devices would avoid transmission along the identified expensive network segment;

utilizing the identification of the source computing device, the identification of the intermediate computing device, and the identification of the expensive network segment to generate a first portion of a store-and-forward routing providing for transmission, in accordance with a first network communication protocol specified by the store-and-forward routing, of a copy of the data from the source computing device to the intermediate computing device through the expensive network segment;

generating a second portion of the store-and-forward routing providing for storage of the transmitted copy of the data on the intermediate computing device; and

utilizing the identification of the intermediate computing device and the at least two intended destination computing devices to generate a third portion of the store-and-forward routing providing for transmission, in accordance with a second network communication protocol specified by the store-and-forward routing, of copies of the data from the intermediate computing device to multiple ones of the at least two intended destination computing devices.

2. The method of claim 1, wherein the identified intermediate computing device is one of the at least two intended destination computing devices.

3. The method of claim 1, wherein the identified intermediate computing device is not one of the at least two intended destination computing devices, the method further comprising conscripting the identified intermediate computing device to:

temporarily store the transmitted copy of the data; and

transmit the copies of the data to the multiple ones of the at least two intended destination computing devices.

4. The method of claim 1, wherein packets of the copy of the data transmitted to the identified intermediate computing device are sorted at the intermediate computing device to minimize out-of-order delivery.

5. The method of claim 1, further comprising determining if the data is tolerant of out-of-order delivery and only performing the generating if the data is tolerant of out-of-order delivery.

6. The method of claim 1, wherein the second protocol differs from the first protocol.

7. The method of claim 1, wherein the identifying the at least one expensive network segment is performed based upon information associated with data previously transmitted over that network segment.

8. A system for distributing data to multiple computing devices, the system comprising:

a source computing device comprising the data;

at least two intended destination computing devices to which copies of the data will be distributed;

an expensive network segment that is part of both a first network path between the source computing device and a first of the at least two intended destination computing device and a second network path between the source computing device and a second of the at least two intended destination computing devices, such that multiple copies of the data would be transmitted, separately, along the expensive network segment; and

one or more computer-readable media comprising computer-executable instructions which, when executed by a computing device, cause the computing device to perform steps comprising;

identifying an intermediate computing device such that data transmitted from the source computing device to the intermediate computing device would be transmitted along the expensive network segment, but data transmitted from the intermediate computing device to multiple ones of the at least two intended destination computing devices would avoid transmission along the expensive network segment;

utilizing an identification of the source computing device, the identification of the intermediate computing device, and an identification of the expensive network segment to generate a first portion of a store-and-forward routing providing for transmission, in accordance with a first network communication protocol specified by the store-and-forward routing, of a copy of the data from the source computing device to the intermediate computing device through the expensive network segment;

generating a second portion of the store-and-forward routing providing for storage of the transmitted copy of the data on the intermediate computing device; and

utilizing the identification of the intermediate computing device and an identification of the at least two intended destination computing devices to generate a third portion of the store-and-forward routing providing for transmission, in accordance with a second network communication protocol specified by the store-and-forward routing, of copies of the data from the intermediate computing device to multiple ones of the at least two intended destination computing devices.

9. The system of claim 8, further comprising a controller computing device, independent of the source computing device, the at least two destination computing devices and the identified intermediate computing device, the controller device comprising the one or more computer-readable media.

10. The system of claim 8, wherein the identified intermediate computing device is one of the at least two intended destination computing devices.

11. The system of claim 8, further comprising the identified intermediate computing device, differing from the at least two intended destination computing devices, wherein the one or more computer-readable media comprise further computer-executable instructions for conscripting the intermediate computing device to:

temporarily store the transmitted copy of the data; and

transmit the copies of the data to the multiple ones of the at least two intended destination computing devices.

12. The system of claim 8, wherein the intermediate computing device comprises computer-executable instructions for sorting packets of the copy of the data transmitted to the identified intermediate computing device to minimize out-of-order delivery.

13. The system of claim 8, wherein the one or more computer-readable media comprise further computer-executable instructions for determining if the data is tolerant of out-of-order delivery;

and the computer-executable instructions for the generating are conditionally executed only if the data is tolerant of out-of-order delivery.

14. The system of claim 8, wherein the second protocol differs from the first protocol.

15. The system of claim 8, wherein the one or more computer-readable media comprise further computer-executable instructions for identifying the expensive network segment based upon information associated with data previously transmitted over the expensive network segment.

16. One or more computer storage media comprising computer-executable instructions which, when executed by a computing device, cause the computing device to perform steps comprising:

identifying (1) a source computing device comprising the data and (2) at least two intended destination computing devices to which copies of the data will be distributed;

identifying at least one expensive network segment that is part of both a first network path between the source computing device and a first of the at least two intended destination computing device and a second network path between the source computing device and a second of the at least two intended destination computing devices, such that multiple copies of the data would be transmitted, separately, along the identified expensive network segment;

identifying an intermediate computing device such that data transmitted from the source computing device to the intermediate computing device would be transmitted along the identified expensive network segment, but data transmitted from the intermediate computing device to multiple ones of the at least two intended destination computing devices would avoid transmission along the identified expensive network segment;

utilizing the identification of the source computing device, the identification of the intermediate computing device, and the identification of the expensive network segment to generate a first portion of a store-and-forward routing providing for transmission, in accordance with a first network communication protocol specified by the store-and-forward routing, of a copy of the data from the source computing device to the intermediate computing device through the expensive network segment;

generating a second portion of the store-and-forward routing providing for storage of the transmitted copy of the data on the intermediate computing device; and

utilizing the identification of the intermediate computing device and the at least two intended destination computing devices to generate a third portion of the store-and-forward routing providing for transmission, in accordance with a second network communication protocol specified by the store-and-forward routing, of copies of the data from the intermediate computing device to multiple ones of the at least two intended destination computing devices.

17. The computer storage media of claim 16, wherein the identified intermediate computing device is one of the at least two intended destination computing devices.