Network Routing Modifications For Distribution Of Data

• US 20140280708A1
• Filed: 03/15/2013
• Published: 09/18/2014
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Maltz, David A., Harper, David T. III, Burger, Douglas Christopher
• Granted Patent: US 9,363,303 B2
• Time in Patent Office: Days
• US Class Current: 709/217
• 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 a source computing device comprising the data and 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 both a first copy of the data, directed to the first intended destination computing device, and a second copy of the data, directed to the second intended destination computing device, 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 network segment; and

generating a store-and-forward routing comprising;

transmission of a copy of the data from the source computing device, through the identified expensive network segment, to the identified intermediate computing device;

storage of the transmitted copy of the data on the intermediate computing device;

forking, at the intermediate computing device, of the copy of the data into multiple copies of the data; and

transmission of each of the forked multiple 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;

fork the transmitted copy of the data into the multiple copies of the data; and

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

4. The method of claim 1, further comprising comparing, prior to the generating the store-and-forward routing, a first amount of time, indicative of transmission of multiple copies of the data across the identified expensive network segment, to a second amount of time, indicative of transmission of a single copy of the data across the identified expensive network segment, storage of the single copy of the data on the identified intermediate computing device, and forking of the single copy of the data on the intermediate computing device;

and only performing the generating if the comparison reveals that the first amount of time is greater than the second amount of time

5. 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.

6. 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.

7. The method of claim 1, wherein the generating comprises:

specifying the utilization of a first protocol for the transmission of the copy of the data from the source computing device, through the identified expensive network segment, to the identified intermediate computing device; and

specifying the utilization of a second protocol, differing from the first protocol, for the transmission of each of the forked multiple copies of the data from the intermediate computing device to the multiple ones of the at least two intended destination computing devices.

8. 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 the network segment.

9. 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 both a first copy of the data, directed to the first intended destination computing device, and a second copy of the data, directed to the second intended destination computing device, would be transmitted, separately, along the identified expensive network segment; and

one or more computer-readable media comprising computer-executable instructions performing 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 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 network segment; and

generating a store-and-forward routing comprising;

transmission of a copy of the data from the source computing device, through the identified expensive network segment, to the identified intermediate computing device;

storage of the transmitted copy of the data on the intermediate computing device;

forking, at the intermediate computing device, of the copy of the data into multiple copies of the data; and

transmission of each of the forked multiple copies of the data from the intermediate computing device to multiple ones of the at least two intended destination computing devices.

10. The system of claim 9, 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.

11. The system of claim 9, wherein the one or more computer-readable media are part of the source computing device, the at least two destination computing devices and the identified intermediate computing device.

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

13. The system of claim 9, further comprising the identified intermediate computing device, 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;

fork the transmitted copy of the data into the multiple copies of the data; and

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

14. The system of claim 9, wherein the one or more computer-readable media comprise further computer-executable instructions for comparing, prior to the generating the store-and-forward routing, a first amount of time, indicative of transmission of multiple copies of the data across the identified expensive network segment, to a second amount of time, indicative of transmission of a single copy of the data across the identified expensive network segment, storage of the single copy of the data on the identified intermediate computing device, and forking of the single copy of the data on the intermediate computing device;

and wherein further the computer-executable instructions for the generating are conditionally executed only if execution of the computer-executable instruction for the comparing reveals that the first amount of time is greater than the second amount of time.

15. The system of claim 9, 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.

16. The system of claim 9, 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.

17. The system of claim 9, wherein the computer-executable instructions for generating comprise computer-executable instructions for:

specifying the utilization of a first protocol for the transmission of the copy of the data from the source computing device, through the identified expensive network segment, to the identified intermediate computing device; and

specifying the utilization of a second protocol, differing from the first protocol, for the transmission of each of the forked multiple copies of the data from the intermediate computing device to the multiple ones of the at least two intended destination computing devices.

18. The system of claim 9, 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.

19. One or more computer-readable media comprising computer-executable instructions for distributing data to multiple computing devices, the computer-executable instructions directed to steps comprising:

identifying a source computing device comprising the data and 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 both a first copy of the data, directed to the first intended destination computing device, and a second copy of the data, directed to the second intended destination computing device, 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 network segment; and

generating a store-and-forward routing comprising;

transmission of a copy of the data from the source computing device, through the identified expensive network segment, to the identified intermediate computing device;

storage of the transmitted copy of the data on the intermediate computing device;

forking, at the intermediate computing device, of the copy of the data into multiple copies of the data; and

transmission of each of the forked multiple copies of the data from the intermediate computing device to multiple ones of the at least two intended destination computing devices.

20. The computer-readable media of claim 19, wherein the identified intermediate computing device is one of the at least two intended destination computing devices.