Method and device for peer arrangement in single substream upload P2P overlay networks

• US 8,713,194 B2
• Filed: 11/18/2011
• Issued: 04/29/2014
• Est. Priority Date: 11/18/2011
• Status: Active Grant

• Current Assignee: Hive Streaming Ab
• Original Assignee: Hive Streaming Ab
• Inventors: El-Beltagy, Mohammed, Naiem, Amgad, El-Ansary, Sameh
• Primary Examiner(s): WANG, LIANG CHE A
• Application Number:
  US13/299,981
• Publication Number:
  US 20130132602A1
• Time in Patent Office: 893 Days
• Field of Search: 709/201, 709/205, 709/226, 709/231
• US Class Current: 709/231
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1063 Discovery through centralising entities
• CPC Class Codes: H04L 67/1078 Resource delivery mechanisms
• CPC Class Codes: H04N 21/632 using a connection between clients on a wide area network, e.g. setting up a peer-to-peer communication via Internet for retrieving video segments from the hard-disk of other client devices broadcast-related systems characterised by transmission among terminal devices H04H60/80; distributed application using peer-to-peer [P2P] networks H04L67/104

Abstract

The present invention relates to a method of and a device for arranging a P2P overlay network comprising a streaming source and a plurality of peers arranged in distribution layers, the streaming source being arranged to divide data content to be streamed into a plurality of content sub-streams together forming the data content and to distribute the plurality of content sub-streams to the network peers.

Claims

1. A method of arranging a P2P overlay network comprising a streaming source and a plurality of peers arranged in distribution layers, the streaming source being arranged to divide data content to be streamed into a plurality of content sub-streams together forming the data content and to distribute the plurality of content sub-streams to the network peers, the method comprising:

determining in which one of the distribution layers an individual peer is to be arranged;

grouping the peers into a number of peer sets, each peer set being grouped to comprise peers from the same distribution layer and further being arranged to be responsible for distributing a respective content sub-stream; and

assigning to each peer set a task of distributing said respective content sub-stream to peers of other peer sets arranged in the same distribution layer and to peers arranged in an immediately subsequent distribution layer which further belongs to a peer set being responsible for the distributed respective content sub-stream.

2. The method of claim 1, further comprising:

instructing peers in the distribution layer being arranged closest to the streaming source to connect to the streaming source, and to at least another peer being arranged in the same distribution layer but belonging to another peer set, for downloading the content sub-streams.

3. The method of claim 1, further comprising:

instructing the streaming source to distribute the different content sub-streams in a substantially equal number to the distribution layer being arranged closest to the streaming source.

4. The method of claim 1, further comprising:

instructing the peers of each distribution layer to distribute the different content sub-streams in a substantially equal number.

5. The method of claim 1, wherein the determining in which one of the distribution layers an individual peer is to be arranged comprises:

determining for each distribution layer, starting from the layer hosting the streaming source, the maximum number of sub-streams that can be distributed to peers to be arranged in an individual distribution layer as the sum of the number of sub-streams that can be distributed from said individual distribution layer and the number of sub-streams that can be distributed from the immediately preceding distribution layer, and

arranging the peers in the distribution layers until all peers have been assigned to a respective distribution layer.

6. The method of claim 5, further comprising:

setting the maximum number of sub-streams that can be distributed to peers to be arranged in an individual distribution layer to be equal to the number of sub-streams that can be distributed from the immediately preceding distribution layer, in case said sum exceeds the number of sub-streams that can be distributed from the immediately preceding distribution layer.

7. The method of claim 1, further comprising:

instructing each peer in the respective peer set to download its respective content sub-stream from a peer in an immediately preceding distribution layer and to download remaining content sub-streams from peers of the other peer sets arranged in the same distribution layer.

8. The method of claim 1, wherein the instructing of each peer in the respective peer set to download the respective content sub-stream from a peer in an immediately preceding distribution layer and to download remaining content sub-streams from peers of the other peer sets arranged in the same distribution layer comprises:

determining, for each peer set in the immediately preceding distribution layer with respect to the instructed peer, the number of sub-streams that the respective peer set is capable of distributing; and

selecting said respective content sub-stream for download from the peer set having smallest determined distribution capability.

9. The method of claim 1, further comprising:

assigning to at least one selected peer a task of distributing the respective content sub-stream for which it is responsible to at least one peer arranged in an immediately subsequent distribution layer requiring said respective content sub-stream, but being responsible for a different sub-stream, in case the at least one selected peer has unutilized distribution capacity.

10. The method of claim 1, further comprising:

assigning to at least one selected peer a task of distributing at least one content sub-stream for which it is not responsible but has downloaded, to at least one peer arranged in the same distribution layer requiring the at least one content sub-stream, in case said at least one peer arranged in the same distribution layer otherwise would have to download the required content sub-stream from the streaming source.

11. The method according to claim 1, further comprising:

assigning a peer arranged in a particular distribution layer to a peer in an immediately preceding distribution layer by means of;

formulating a Linear Sum Assignment Problem (LSAP) based on a predetermined metric;

calculating an assignment value from the LSAP representing a quality measure of the predetermined metric for each possible assignment to peers in the immediately preceding distribution layer; and

selecting the peer in the immediately preceding distribution layer, to which the peer in said particular distribution layer is to be assigned, on the basis of the calculated quality measure.

12. The method according to claim 1, further comprising:

assigning a peer arranged in a particular distribution layer to another peer in the same particular distribution layer by means of;

formulating a Linear Sum Assignment Problem (LSAP) based on a predetermined metric;

calculating an assignment value from the LSAP representing a quality measure of the predetermined metric for each possible assignment to other peers in the same particular layer; and

selecting the other peer in the same particular distribution layer, to which the peer in the particular layer is to be assigned, on the basis of the calculated quality measure.

25. A computer program product comprising a non-transitory computer readable medium, the computer readable medium having computer program code embodied therein, the computer program code being configured perform the steps of the method recited in claim 1.

13. A device for arranging a P2P overlay network comprising a streaming source and a plurality of peers arranged in distribution layers, the streaming source being arranged to divide data content to be streamed into a plurality of content sub-streams together forming the data content and to distribute the plurality of content sub-streams to the network peers, the device comprising:

a processing unit being arranged to determine in which one of the distribution layers an individual peer is to be arranged;

group the peers into a number of peer sets, each peer set being grouped to comprise peers from the same distribution layer and further being arranged to be responsible for distributing a respective content sub-stream; and

assign to each peer set a task of distributing said respective content sub-stream to peers of other peer sets arranged in the same distribution layer and to peers arranged in an immediately subsequent distribution layer which further belongs to a peer set being responsible for the distributed respective content sub-stream.

14. The device of claim 13, said processing unit further being arranged to:

instruct peers in the distribution layer being arranged closest to the streaming source to connect to the streaming source, and to at least another peer being arranged in the same distribution layer but belonging to another peer set, for downloading the content sub-streams.

15. The device of claim 13, said processing unit further being arranged to:

instruct the streaming source to distribute the different content sub-streams in a substantially equal number to the distribution layer being arranged closest to the streaming source.

16. The device of claim 13, said processing unit further being arranged to:

instruct the peers of each distribution layer to distribute the different content sub-streams in a substantially equal number.

17. The device of claim 13, said processing unit further being arranged, when determining in which one of the distribution layers an individual peer is to be arranged, to:

determine for each distribution layer, starting from the layer hosting the streaming source, the maximum number of sub-streams that can be distributed to peers to be arranged in an individual distribution layer as the sum of the number of sub-streams that can be distributed from said individual distribution layer and the number of sub-streams that can be distributed from the immediately preceding distribution layer, and

arrange the peers in the distribution layers until all peers have been assigned to a respective distribution layer.

18. The device of claim 17, said processing unit further being arranged to:

set the maximum number of sub-streams that can be distributed to peers to be arranged in an individual distribution layer to be equal to the number of sub-streams that can be distributed from the immediately preceding distribution layer, in case said sum exceeds the number of sub-streams that can be distributed from the immediately preceding distribution layer.

19. The device of claim 13, said processing unit further being arranged to:

instruct each peer in the respective peer set to download its respective content sub-stream from a peer in an immediately preceding distribution layer and to download remaining content sub-streams from peers of the other peer sets arranged in the same distribution layer.

20. The device of claim 13, said processing unit further being arranged, when instructing each peer in the respective peer set to download the respective content sub-stream from a peer in an immediately preceding distribution layer and to download remaining content sub-streams from peers of the other peer sets arranged in the same distribution layer, to:

determine, for each peer set in the immediately preceding distribution layer with respect to the instructed peer, the number of sub-streams that the respective peer set is capable of distributing; and

select said respective content sub-stream for download from the peer set having smallest determined distribution capability.

21. The device of claim 13, said processing unit further being arranged to:

assign to at least one selected peer a task of distributing the respective content sub-stream for which it is responsible to at least one peer arranged in an immediately subsequent distribution layer requiring said respective content sub-stream, but being responsible for a different sub-stream, in case the at least one selected peer has unutilized distribution capacity.

22. The device of claim 13, said processing unit further being arranged to:

assign to at least one selected peer a task of distributing at least one content sub-stream for which it is not responsible but has downloaded, to at least one peer arranged in the same distribution layer requiring the at least one content sub-stream, in case said at least one peer arranged in the same distribution layer otherwise would have to download the required content sub-stream from the streaming source.

23. The device of claim 13, said processing unit further being arranged to:

assign a peer arranged in a particular distribution layer to a peer in an immediately preceding distribution layer by means of;

formulating a Linear Sum Assignment Problem (LSAP) based on a predetermined metric;

calculating an assignment value from the LSAP representing a quality measure of the predetermined metric for each possible assignment to peers in the immediately preceding distribution layer; and

selecting the peer in the immediately preceding distribution layer, to which the peer in said particular distribution layer is to be assigned, on the basis of the calculated quality measure.

24. The device of claim 13, said processing unit further being arranged to:

assign a peer arranged in a particular distribution layer to another peer in the same particular distribution layer by means of;

formulating a Linear Sum Assignment Problem (LSAP) based on a predetermined metric;

calculating an assignment value from the LSAP representing a quality measure of the predetermined metric for each possible assignment to other peers in the same particular layer; and

selecting the other peer in the same particular distribution layer, to which the peer in the particular layer is to be assigned, on the basis of the calculated quality measure.