Network routing modifications for distribution of data

• US 9,363,303 B2
• Filed: 03/15/2013
• Issued: 06/07/2016
• 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., Harper, David T. III, Burger, Douglas Christopher
• Primary Examiner(s): Moise, Emmanuel L
• Assistant Examiner(s): ABU ROUMI, MAHRAN Y
• Application Number:
  US13/831,733
• Publication Number:
  US 20140280708A1
• Time in Patent Office: 1,180 Days
• Field of Search: 709/223
• US Class Current: 1/1
• 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 more efficiently distributing data to multiple computing devices by reducing a number of copies of the data transmitted through an identified network segment, 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;

receiving information indicative of difficulty in transmitting data through network segments;

identifying, based on the received information, at least one network segment through which a reduced quantity of data is to be transmitted, the identified network segment being 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 network segment;

selecting an intermediate computing device that is across the identified network segment from the source computing device, wherein the data transmitted from the source computing device to the selected intermediate computing device would be transmitted along the identified network segment, but data transmitted from the selected intermediate computing device to multiple ones of the at least two intended destination computing devices would avoid transmission along the identified network segment;

determining a first amount of time, indicative of transmission of multiple copies of the data across the identified network segment;

determining a second amount of time, indicative of transmission of a single copy of the data through the identified network segment to the selected intermediate computing device, storage of the transmitted single copy of the data on the selected intermediate computing device, and forking of the single copy of the data on the intermediate computing device; and

triggering, based on the first amount of time and the second amount of time, a generating of a store-and-forward routing comprising;

the transmission of the single copy of the data from the source computing device, through the identified network segment, to the selected intermediate computing device, the storage of the transmitted single copy of the data on the selected intermediate computing device, the forking, at the intermediate computing device, of the single 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 selected computing device, that is utilized as the intermediate computing device in the generated store-and-forward routing, is one of the at least two intended destination computing devices.

3. The method of claim 1, wherein the selected computing device, that is utilized as the intermediate computing device in the generated store-and-forward routing, is not one of the at least two intended destination computing devices, the method further comprising conscripting the intermediate computing device to:

temporarily store the transmitted data;

fork the transmitted 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, wherein packets of the data transmitted to the 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 generating comprises:

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

specifying the utilization of a second set of protocol settings, differing from the first set of protocol settings, 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.

7. The method of claim 1, wherein the received expense information comprises congestion information obtained from previous transmission of data over the network segment.

8. A system for more efficiently distributing data to multiple computing devices by reducing a number of copies of the data transmitted through an identified network segment, 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;

the identified 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 network segment; and

one or more computer-readable storage media comprising computer-executable instructions directed to steps comprising;

receiving information indicative of difficulty in transmitting data through network segments;

selecting an intermediate computing device that is across the identified network segment from the source computing device, wherein the data transmitted from the source computing device to the selected intermediate computing device would be transmitted along the identified network segment, but data transmitted from the selected intermediate computing device to multiple ones of the at least two intended destination computing devices would avoid transmission along the identified network segment;

determining a first amount of time, indicative of transmission of multiple copies of the data across the identified network segment;

determining a second amount of time, indicative of transmission of a single copy of the data through the identified network segment to the selected intermediate computing device, storage of the transmitted single copy of the data on the selected intermediate computing device, and forking of the single copy of the data on the intermediate computing device; and

triggering, based on the first amount of time and the second amount of time, a generating of a store-and-forward routing comprising;

the transmission of the single copy of the data from the source computing device, through the identified network segment, to the selected intermediate computing device, the storage of the transmitted single copy of the data on the selected intermediate computing device, the forking, at the intermediate computing device, of the single 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.

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 selected computing device that is utilized as the intermediate computing device in the generated store-and-forward routing, the controller device comprising the one or more computer-readable storage media.

10. The system of claim 8, wherein the one or more computer-readable storage media are part of the source computing device, the at least two destination computing devices and the selected computing device that is utilized as the intermediate computing device in the generated store-and-forward routing.

11. The system of claim 8, wherein the selected computing device, that is utilized as the intermediate computing device in the generated store-and-forward routing, is one of the at least two intended destination computing devices.

12. The system of claim 8, further comprising the selected computing device, that is utilized as the intermediate computing device in the generated store-and-forward routing, wherein the one or more computer-readable storage media comprise further computer-executable instructions for conscripting the intermediate computing device to:

temporarily store the transmitted data;

fork the transmitted 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.

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

14. The system of claim 8, wherein the one or more computer-readable storage 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.

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

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

specifying the utilization of a second set of protocol settings, differing from the first set of protocol settings, 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.

16. The system of claim 8, wherein the received expense information comprises congestion information obtained from previous transmission of data over the network segment.

17. A computing device comprising:

one or more processing units; and

one or more computer-readable storage media comprising computer-executable instructions for more efficiently distributing data to multiple computing devices by reducing a number of copies of the data transmitted through an identified network segment, the computer-executable instructions, when executed by the one or more processing units, causing the computing device to;

identify a source computing device comprising the data and at least two intended destination computing devices to which copies of the data will be distributed;

receive information indicative of difficulty in transmitting data through network segments;

identify, based on the received information, at least one network segment through which a reduced quantity of data is to be transmitted, the identified network segment being 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 network segment;

select an intermediate computing device that is across the identified network segment from the source computing device, wherein the data transmitted from the source computing device to the selected intermediate computing device would be transmitted along the identified network segment, but data transmitted from the selected intermediate computing device to multiple ones of the at least two intended destination computing devices would avoid transmission along the identified network segment;

determine a first amount of time, indicative of transmission of multiple copies of the data across the identified network segment;

determine a second amount of time, indicative of transmission of a single copy of the data through the identified network segment to the selected intermediate computing device, storage of the transmitted single copy of the data on the selected intermediate computing device, and forking of the single copy of the data on the intermediate computing device; and

trigger, based on the first amount of time and the second amount of time, a generating of a store-and-forward routing comprising;

the transmission of the single copy of the data from the source computing device, through the identified network segment, to the selected intermediate computing device, the storage of the transmitted single copy of the data on the selected intermediate computing device, the forking, at the intermediate computing device, of the single 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.

18. The computing device of claim 17, wherein the selected computing device, that is utilized as the intermediate computing device in the generated store-and-forward routing, is one of the at least two intended destination computing devices.

19. The computing device of claim 17, wherein the selected computing device, that is utilized as the intermediate computing device in the generated store-and-forward routing, is not one of the at least two intended destination computing devices;

and wherein further the computer-readable media comprise further computer-executable instructions which, when executed by the one or more processing units, causing the computing device to conscript the intermediate computing device to;

temporarily store the transmitted data;

fork the transmitted 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.

20. The computing device of claim 17, wherein the received expense information comprises congestion information obtained from previous transmission of data over the network segment.