Interior-Node-Disjoint Multi-Tree Topology Formation

• US 20090034434A1
• Filed: 11/19/2007
• Published: 02/05/2009
• 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: HUANG, Zhe, TSANG, Danny Hin-Kowk
• Granted Patent: US 8,279,766 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• 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 multistreaming peer-to-peer network, comprising:

a plurality of nodes connected in a peer-to-peer architecture, through connecting links which have balanced reserved bandwidths;

multiple stream trees defined on said nodes,

singly containing less than all nodes for a single stream, and

jointly containing all nodes for all streams;

wherein each said stream tree includes both leaf nodes and interior nodes;

and wherein a node can be an interior node of one tree, but cannot be an interior node of any two said trees at the same time.

2. The network of claim 1, wherein when a new peer joins, it utilizes a walker procedure to find said connecting links.

3. The network of claim 1, wherein said reserved bandwidths are balanced because node with higher link capacity has a higher probability to become parent node when a new peer joins.

4. The network of claim 1, wherein ones of said stream trees are controlled by a control plane.

5. The network of claim 1, wherein each said interior node is permitted to distribute respective stream carried on the respective corresponding tree.

6. The network of claim 1, wherein each said node is an interior node of exactly one tree.

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

a peer-to-peer network comprising at least one peer connecting to either a media source or other peers for downloading said content, through connecting links which are balanced to be Link-Level-Homogeneous;

at least one tree comprising at least one said peer, wherein some ones of said peers are interior nodes of exactly one of said trees, but no said peer is an interior node of more than one said tree simultaneously; and

a bootstrap server maintaining and providing information on said trees and their member peers.

8. The architecture of claim 7, wherein said connecting links for said new peer are determined in dependence of link capacity of nodes, such that nodes with higher link capacity are more likely to be selected as end point of connecting link for next new peer.

9. The architecture of claim 7, wherein said connecting links are determined by a central controller.

10. The architecture of claim 7, wherein additions and deletions of nodes of said trees are controlled by a unique control plane.

11. The architecture of claim 7, wherein said link capacity of a node depends on the number of child nodes connected to it.

12. The architecture of claim 7, wherein a structured ID format is used to represent parent-child relationship of nodes in said trees.

13. The architecture of claim 7, wherein said trees are rebuilt when a node departs by adding nodes in disconnected subtrees back in with the limitation that none of said nodes in disconnected subtrees can be selected as a parent node.

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

when an added node joins a peer-to-peer network in which multiple substream trees carry separate components of a single high-bandwidth stream,

connecting said added node to different interior nodes as sources for each of said substream trees,

subject to the requirement that no node can be an interior node of any two substream trees which carry components of the same high-bandwidth stream.

15. The method of claim 14, wherein said connecting action utilizes a bootstrap server.

16. The method of claim 14, wherein said connecting action utilizes a bootstrap server to locate a control plane that manages interior nodes of a said respective tree.

17. The method of claim 14, wherein said connecting action utilizes a walker procedure on a control plane.

18. The method of claim 14, wherein said connecting action selects interior nodes also in dependence of available capacity thereof.

19. The method of claim 14, wherein said connecting action selects interior nodes also in dependence of available processing power thereof.

20-40. -40. (canceled)