Interior-Node-Disjoint Multi-Tree Topology Formation搭建中間點分離多樹拓撲結構
- Summary
- Tree structure plays an important role in topology. It appears in many designs in different areas such as data structure and computer networking etc. One of the implementations of tree topology is multi-tree forest. In the multi-tree forest, trees represent different categories and a single node in the forest might be attached to multiple trees according to different attaching rules. A set of trees is said to be interior-node- disjoint if each node is an interior node in only one tree, and a leaf node in the other trees. For an individual node in the interior-node-disjoint structure, it only adopts child nodes in one particular tree.
This invention presents a central controller algorithm and a random walk based topology formation algorithm, which create an interior-node-disjoint multi-tree structure according to user's specified attaching rules represented by target attaching probability for each individual tree. With the algorithms proposed, the multi-tree structure statistically can be controlled so that nodes are interior-node-disjoint and interconnected in a desired way. The random walk algorithm shows innovation in tree formation. A distributed random walk parent locating algorithm intelligently selects parent node for each node according to attaching probability. Number of child nodes for each node in the multi-tree forest is controlled so that the topology formed fulfills the desired topology.
- Technology Benefits
- 1. Optimal topology design specific to the P2P application in mind
2. Good load balance among heterogeneous peers
3. Simple and easy to implement algorithm
4. Cost-effective solution
- Technology Application
- - For use in Internet P2P applications
- Supplementary Information
- Patent Number: US8279766B2
Application Number: US2007942257A
Inventor: Tsang, Danny Hin-Kwok | Huang, Zhe
Priority Date: 31 Jul 2007
Priority Number: US8279766B2
Application Date: 19 Nov 2007
Publication Date: 2 Oct 2012
IPC Current: G08C001500 | H04L001228 | H04L001256
US Class: 370252 | 370254 | 3703952
Assignee Applicant: The Hong Kong University of Science & Technology
Title: Interior-node-disjoint multi-tree topology formation
Usefulness: Interior-node-disjoint multi-tree topology formation
Summary: Multi-streaming peer-to-peer architecture for downloading multimedia content such as bulk files, live or on-demand audio and video.
Novelty: Multi-streaming peer-to-peer architecture for downloading multimedia content e.g. bulk file, has stream tress with leaf nodes and interior nodes included such that only one interior node is included for a single tree
- Industry
- ICT/Telecom
- Sub Category
- Telecommunication
- Application Date
- 19 Nov 2007
- Application No.
- US 11/942257
- Patent Information
- US 8279766
- ID No.
- TTC.PA.326
- Country/Region
- Hong Kong
For more information, please click Here
