Interior-node-disjoint multi-tree topology formation

• US 8,279,766 B2
• Filed: 11/19/2007
• Issued: 10/02/2012
• Est. Priority Date: 07/31/2007
• Status: Active Grant

• Current Assignee: Hong Kong University of Science and Technology
• Original Assignee: Hong Kong University of Science and Technology
• Inventors: Tsang, Danny Hin-Kwok, Huang, Zhe
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): SHIVERS, ASHLEY L
• Application Number:
  US11/942,257
• Publication Number:
  US 20090034434A1
• Time in Patent Office: 1,779 Days
• Field of Search: None
• US Class Current: 370/252
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1048 Departure or maintenance mechanisms

Abstract

A novel decentralized protocol for constructing a tree-based P2P live video streaming network with the Interior-Node-Disjoint (IND) multi-tree structure with the special Link-Level-Homogeneous property. The IND multi-tree structure recycles the wasted uploading capacities of leaf nodes in the tree-based P2P networks. The IND multi-tree structure also enhances the robustness of the tree-based P2P networks. Moreover, the special Link-Level-Homogeneous property eliminates the bottlenecks in the video delivery paths by ensuring that each downloading link in the network has identical bandwidth reserved. This special designed architecture greatly improves the downloading performance.

Claims

1. A multi-streaming peer-to-peer network, comprising:

a set of nodes connected in a peer-to-peer architecture, through respective connecting links having a Link-Level Homogeneous property, wherein, as at least one node of the set of nodes joins the network, a connecting link has identical link capacity as all other connecting links, and wherein the identical link capacity is a data rate determined for a data source to stream data through the multi-streaming peer-to-peer network based in part on respective capacities of the set of nodes; and

multiple stream trees, each of which propagates at most only a single stream, wherein each stream tree includes both leaf nodes and interior nodes from among the set of nodes, and wherein a node of the set of nodes cannot simultaneously be an interior node of any two stream trees.

2. The network of claim 1, further comprising a set of control planes, each of which includes only interior nodes from the set of nodes, connected in a peer-to-peer architecture.

3. The network of claim 2, further comprising a parent selection component configured to determine respective topologies of the multiple stream trees in accordance with the Link-Level Homogeneous property.

4. The network of claim 3, wherein the parent selection component utilizes a walker procedure on at least one control plane to determine respective topologies of the multiple stream trees in accordance with the Link-Level Homogeneous property.

5. The network of claim 4, wherein the walker procedure is further configured to operate in a distributed manner and to select parent nodes for newly joined nodes as a function of identical link capacity and in accordance with the Link-Level Homogeneous property.

6. The network of claim 5, wherein said identical link capacity is a logical link capacity defined as an uploading capacity of the at least one node of the set of nodes divided by a fanout of the at least one node.

7. The network of claim 2, wherein a single control plane from the set of control planes is configured to include all interior nodes associated with a stream tree of the multiple stream trees and to exclude all leaf nodes associated with the stream tree.

8. A multi-stream peer-to-peer communications architecture, comprising:

a peer-to-peer network comprising a plurality of peers connecting to either a media source or other peers for downloading content through connecting links configured to converge to a Link-Level-Homogeneous state as new peers join the network, wherein the Link-Level Homogeneous state exists if connecting links have substantially identical link capacity determined for the media source or the other peers to stream data through the peer-to-peer network based in part on respective capacities of the plurality of peers; and

at least one tree comprising a set of peers, wherein a subset of peers are interior nodes of exactly one of the at least one tree, but no peer of the set of peers is an interior node of more than one of the at least one tree simultaneously.

9. The architecture of claim 8, wherein the connecting links for the new peers are determined in dependence of link capacity of nodes in the peer-to-peer network, such that nodes in the peer-to-peer network with higher link capacity are more likely to be selected as an end point of a connecting link for a next new peer.

10. The architecture of claim 8, wherein additions and deletions of nodes in the peer-to-peer network and the connecting links associated therewith of the at least one tree are controlled by a respective control plane for each of the at least one tree.

11. The architecture of claim 8, wherein a link capacity of a node in the peer-to-peer network depends on the number of child nodes connected to the node.

12. A method for adaptively building a peer-to-peer topology for high-bandwidth streaming, comprising:

receiving a request for joining an added node to a peer-to-peer network, in which multiple substream trees carry separate components of a single high-bandwidth stream; and

connecting the added node to different interior nodes based upon available resources of the different interior nodes that serve as sources for each of the multiple substream trees, subject to a requirement that no node is an interior node of any two substream trees that carry components of the single high-bandwidth stream, and further subject to a requirement to maintain Link-Level Homogeneity, in which link capacity per fanout is substantially equal for each logical link connecting any two nodes of the multiple substream trees, wherein the connecting includes determining a data rate for an application to stream data through the peer-to-peer topology, according to the capacity per fanout, based in part on respective capacities of peers in the peer-to-peer network.

13. The method of claim 12, further comprising employing a bootstrap server for locating multiple control planes for respectively managing interior nodes of respective multiple substream trees.

14. The method of claim 12, wherein the connecting the added node includes connecting the added node in a distributed manner by employing a walker procedure on a control plane.

15. The method of claim 12, further comprising selecting the different interior nodes as a function of logical link capacity in connection with the connecting the added node.

16. The method of claim 12, further comprising selecting the different interior nodes as a function of available central processing unit (CPU) power in connection with the connecting the added node.

17. The method of claim 12, further comprising configuring said multiple substream trees for carrying different substreams of a single video flow defined as the single high-bandwidth stream.

18. A method for multi-streaming over a peer-to-peer network, comprising:

receiving a request for downloading from a new peer;

connecting the new peer to respective nodes in each of a set of stream trees delivering multiple respective content streams;

selecting the respective nodes as a function of link capacity in accordance with a Link-Level Homogeneous property whereby connecting links comprise links having substantially identical link capacity, wherein the selecting includes determining a data rate for a data source to stream data through the peer-to-peer network, according to the substantially identical link capacity, based in part on respective capacities of peers in the peer-to-peer network; and

permitting the new peer to distribute only one content stream carried over a selected stream tree from the set of stream trees.

19. The method of claim 18, further comprising utilizing a walker procedure in a distributed manner for selecting the respective nodes as a function of link capacity.

20. The method of claim 19, further comprising employing the new peer for initiating the walker procedure for locating the respective nodes.

21. The method of claim 20, wherein selecting the respective nodes as a function of link capacity includes selecting a node with high link capacity relative to other nodes included in an associated stream tree.

22. The method of claim 18, further comprising defining a respective control plane for the set of stream trees.

23. The method of claim 22, wherein connecting the new peer is performed on the respective control planes.

24. A method of peer-to-peer multi-streaming, comprising:

receiving a request for access to a peer-to-peer network from a new peer;

connecting the new peer to respective nodes in each of multiple component stream trees to thereby receive multiple related content streams including selecting said respective nodes according to a Link-Level Homogeneous property in which connecting links for peers have a common link capacity, wherein the selecting includes determining a data rate for an application to stream data through the peer-to-peer network, according to the common link capacity, based in part on respective capacities of peers in the peer-to-peer network being fully utilized; and

managing said respective nodes such that said new peer is permitted to distribute only one of said multiple related content streams carried over a respective one of said multiple component stream trees wherein addition or deletion of nodes in a component stream tree is controlled by a respective control plane.

25. The method of claim 24, further comprising utilizing a walker procedure on the control planes for said connecting in a distributed fashion.

26. The method of claim 24, wherein said connecting includes selecting the respective nodes based upon a high link capacity among all nodes in a respective stream tree.

27. The method of claim 24, further comprising employing said respective control plane for managing permissions of content substream distribution of the respective nodes in a respective stream tree.

28. A method of distributing multi-streams over a multi-tree peer-to-peer network, comprising:

assigning streams to a respective tree under a respective unique control plane;

successively adding new peers as leaf nodes for downloading content, comprising;

requesting, from a bootstrap server, initial node information for multiple trees of the network;

launching a procedure, for respective initial nodes in a respective control plane, for locating respective parent nodes in dependence of link capacity, while maintaining Link-Level Homogeneity in which logical connecting links for nodes operate according to a uniform link capacity, wherein the maintaining Link-Level Homogeneity includes determining a data rate for a data source to stream data through the connecting links based in part on respective capacities of the set of nodes being fully utilized;

connecting a new peer to said respective parent nodes for multiple trees for streaming content; and

adding said new peer into said respective unique control plane, comprising requesting information from nodes contained in said respective unique control plane and establishing control connections to said nodes.

29. A multi-stream peer-to-peer communications architecture, comprising:

a peer-to-peer network comprising multiple peers connecting to either a media source or other peers for downloading content through connecting links that are balanced to be Link-Level-Homogeneous, wherein, as at least one peer of the multiple peers joins the peer-to-peer network, the connecting links are balanced based in part on a data rate determined for an application to stream data through the peer-to-peer network in consideration of respective capacities of the multiple peers being fully utilized;

at least one tree comprising said multiple peers, wherein a subset of said multiple peers are interior nodes of exactly one of said at least one tree; and

a management component that manages addition or deletion of a node in said at least one tree based upon at least one unique control plane and distributed knowledge, residing at respective nodes of the multiple peers, regarding connections to others nodes.

30. The architecture of claim 29, wherein said management component determines said connecting links in dependence of link capacity of nodes such that nodes with higher link capacity have a higher probability to be selected as an end point of a connecting link for a next new peer.

31. The architecture of claim 30, wherein said management component employs a walker procedure performed on a corresponding control plane in order to determine said connecting links.

32. The architecture of claim 31, wherein said management component identifies said link capacity of nodes based upon a number of connected child nodes.