Coordinated content distribution over network

• US 10,263,884 B2
• Filed: 03/04/2017
• Issued: 04/16/2019
• Est. Priority Date: 03/04/2017
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Kota, Preeti, Zaydman, Oleg, Cao, Yanping, Kapadia, Pratik
• Primary Examiner(s): Atkins, George C
• Application Number:
  US15/449,927
• Publication Number:
  US 20180254977A1
• Time in Patent Office: 773 Days
• Field of Search: None
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A coordinated multi-cast content distribution process is used to distribute content, e.g., files, from a source node of a network to target nodes of the network. A minimum spanning tree is identified for the network based on costs of edges connecting the nodes. The minimum spanning tree includes the source node and all target nodes; the minimum spanning tree distinguishes leaf target nodes from non-leaf target nodes. Content parts are moved along the spanning tree in an iterative process in which, for each iteration, the highest-cost leaf nodes are identified and content parts are moved toward the identified leaf nodes. This process reduces avoids network congestion and reduces the total bandwidth consumption required to supply the content to all target nodes.

Claims

1. An iterative multicast content distribution process in which a source node of a network is to multicast content divided into a plurality of segments to target nodes of the network via edges of the network, the target nodes including leaf target nodes and repeater target nodes, the leaf target nodes being different from the repeater target nodes, the process comprising:

assigning edge costs to the leaf target nodes;

scheduling distribution to the leaf target nodes and to the repeater target nodes based on the edge costs of the leaf target nodes;

transferring a first segment of the multicast content to a target node based on the scheduling;

dynamically adjusting the edge costs of the leaf target nodes to reflect changes to a distribution state, the dynamic adjusting including adjusting the edge cost of a leaf target node in response to content being received by a repeater target node; and

transferring a second segment of the multicast content to a target node based on the adjusting;

wherein each target node receives content directly from either the source node or a repeater target node, wherein each repeater target node copies received content and sends copied content either to a leaf target node or to another repeater target node;

wherein an edge cost of a respective leaf target node is correlated with the cost of distributing all segments to the respective leaf target node;

wherein adjustments to the edge cost of a respective leaf target node are made to make node edge cost correlate with the cost of distributing remaining segments to the respective leaf target node.

2. The multi-cast content distribution process of claim 1 wherein repeater nodes are used to reduce distribution cost to a node.

3. The multi-cast content distribution process of claim 1 wherein a distribution path to a node is established.

4. The multi-cast content distribution process of claim 3 wherein the distribution path is re-established to reflect changes to distribution state or topology.

5. The multi-cast content distribution process of claim 3 wherein the distribution path is based on a graph.

6. The multi-cast content distribution process of claim 5 wherein the distribution cost of the graph may be smaller than connecting a leaf target node directly to the source node.

7. The multi-cast content distribution process of claim 1 wherein transfers toward nodes with higher rank are scheduled before nodes with lower edge costs.

8. The multi-cast content distribution process of claim 1 wherein transfers are scheduled along distribution paths to leaf target nodes.

9. The multi-cast content distribution process of claim 6 wherein the leaf target node is no longer scheduled once it reaches capacity.

10. The multicast content distribution process of claim 6 wherein a plurality of transfers are scheduled along the distribution path in a single iteration.

11. The multi-cast content distribution process of claim 6 wherein transfers further away from the publisher are scheduled before transfers closer to the source node.

12. A system comprising non-transitory media encoded with code that, when executed by a processor, implements an iterative multicast content distribution process in which a source node of a network is to multicast content divided into a plurality of segments to target nodes of the network via edges of the network, the target nodes including leaf target nodes and repeater target nodes, the leaf target nodes being different from the repeater target nodes, the process comprising:

assigning edge costs to the leaf target nodes;

scheduling distribution to the leaf target nodes and to the repeater target nodes based on the edge costs of the leaf target nodes;

transferring a first segment of the multicast content to a target node based on the scheduling;

dynamically adjusting the edge costs of the leaf target nodes to reflect changes to a distribution state, the dynamic adjusting including adjusting the edge cost of a leaf target node in response to content being received by a repeater target node; and

transferring a second segment of the multicast content to a target node based on the adjusting;

wherein each target node receives content directly from either the source node or a repeater target node, wherein each repeater target node copies received content and sends copied content either to a leaf target node or to another repeater target node;

wherein an edge cost of a respective leaf target node is correlated with the cost of distributing all segments to the respective leaf target node;

wherein adjustments to the edge cost of a respective leaf target node are made to make node edge cost correlate with the cost of distributing remaining segments to the respective leaf target node.

13. The system of claim 12 wherein repeater nodes are used to reduce distribution cost to a node.

14. The system of claim 12 wherein a distribution path to a node is established.

15. The system of claim 14 wherein the distribution path is re-established to reflect changes to distribution state or topology.

16. The system of claim 14 wherein the distribution path is based on a graph.

17. The system of claim 16 wherein the distribution cost of the graph may be smaller than connecting a leaf target node directly to the source node.

18. The system of claim 12 wherein transfers toward nodes with higher rank are scheduled before nodes with lower edge costs.

19. The system of claim 12 wherein transfers are scheduled along distribution paths to leaf target nodes.

20. The system of claim 17 wherein the leaf target node is no longer scheduled once it reaches capacity.

21. The system of claim 17 wherein a plurality of transfers are scheduled along the distribution path in a single iteration.