Method and device for peer arrangement in streaming-constrained P2P overlay networks

• US 8,799,498 B2
• Filed: 11/18/2011
• Issued: 08/05/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
• Primary Examiner(s): WANG, LIANG CHE A
• Application Number:
  US13/299,957
• Publication Number:
  US 20130132601A1
• Time in Patent Office: 991 Days
• Field of Search: 709/201, 709/204, 709/231, 709/245
• US Class Current: 709/231
• CPC Class Codes: H04L 65/611 for multicast or broadcast systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 67/1078 Resource delivery mechanisms
• CPC Class Codes: H04L 67/1089 Hierarchical topologies
• CPC Class Codes: H04N 21/4788 communicating with other users, e.g. chatting arrangements for providing for computer conferences, e.g. chat rooms, to substation in data switching networks H04L12/1813; distributed application using peer-to-peer [P2P] networks H04L67/104
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments

Abstract

The present invention relates to a method of and a device for arranging a P2P overlay network comprising a streaming source arranged to stream data content and a plurality of peers arranged in distribution layers. The method comprises the step of arranging the peers in the distribution layers such that data content download requirements of peers in any one distribution layer does not exceed data content distribution capacity of an immediately preceding distribution layer. The method further comprises the step of selecting, when a first peer has capacity to distribute a data content stream to another peer in an immediately subsequent layer but is restricted from doing so, a second peer from a distribution layer subsequent to that of the first peer, which second peer is not being restricted from distributing the data content stream to said another peer.

Claims

1. A method of arranging a P2P overlay network comprising a streaming source arranged to stream data content and a plurality of peers arranged in distribution layers, the method comprising the steps of:

arranging the peers in the distribution layers such that data content download requirements of peers in any one distribution layer does not exceed data content distribution capacity of peers in an immediately preceding distribution layer;

selecting, when a first peer has capacity to distribute a data content stream to another peer in an immediately subsequent layer but is restricted from distributing the data content stream to said another peer, a second peer from a distribution layer subsequent to a distribution layer of the first peer, which second peer is not being restricted from distributing the data content stream to said another peer; and

switching positions of the first peer and the selected second peer in the overlay network.

2. The method of claim 1, wherein the step of selecting further comprises:

randomly selecting a second peer which is not restricted from distributing the data content stream to said another peer, which has sufficient capacity to distribute the data content stream uploading data content, and which is not restricted from receiving a data content stream from a peer that was distributing data content to the first peer.

3. The method of claim 1, further comprising the step of:

categorizing the peers into different categories, wherein peers of one category are restricted from communicating with peers of a different category.

4. The method of claim 3, wherein the peers are categorized into different network address translation (NAT) categories.

5. The method of claim 1, wherein the arranging of peers in distribution layers is undertaken for successive pairs of layers such that data content streaming between any two layers is taken into consideration starting from the layer immediately subsequent to the streaming source and ending at the layer immediately preceding the last distribution layer.

6. The method of claim 3, further comprising the step of:

determining, for the distribution layer in which the first peer is arranged, which category has peers with least fulfilled data content download requirements.

7. The method of claim 6, wherein the step of determining which category has peers with least fulfilled data content download requirements comprises:

calculating, for each peer in the category, the argument of the difference between number of required downloaded data sub-streams for fully rendering a data content streamed by the streaming source and the actual number of data sub-streams downloaded.

8. The method of claim 6, further comprising the step of:

determining which one of the peers in the category with the least fulfilled data content download requirement that has lowest upload capacity.

9. The method of claim 7, further comprising the step of:

determining, in the distribution layer immediately preceding that of the first peer, which categories have unutilized upload capacity and that further have capacity to upload the required number of data sub-streams such that a downloading peer in an immediately subsequent distribution layer is able to fully render a data content.

10. The method of claim 9, further comprising the step of:

identifying the second peer as the peer having the greatest upload capacity among peers located in distribution layers subsequent to the distribution layer of the first peer, which peers further are able to download the data content from a peer in the determined category having unutilized upload capacity, have available upload capacity, and belong to a category which is allowed to upload data content to first peer.

20. A computer program product comprising a memory having computer-executable components configured to cause a device to perform the steps recited in claim 1 when the computer-executable components are run on a processing unit included in the device.

11. A device for arranging a P2P overlay network comprising a streaming source arranged to stream data content and a plurality of peers arranged in distribution layers, the device comprising:

a processing unit being configured to

arrange the peers in the distribution layers such that data content download requirements of peers in any one distribution layer does not exceed data content distribution capacity of peers in an immediately preceding distribution layer;

select, when a first peer has capacity to distribute a data content stream to another peer in an immediately subsequent layer but is restricted from distributing the data content stream to said another peer, a second peer from a distribution layer subsequent to a distribution layer of the first peer, which second peer is not being restricted from distributing the data content stream to said another peer; and

switch positions of the first peer and the selected second peer in the overlay network.

12. The device of claim 11, wherein the processing unit further is configured to:

randomly select a second peer which is not restricted from distributing the data content stream to said another peer, which has sufficient capacity to distribute the data content stream uploading data content, and which is not restricted from receiving a data content stream from a peer that was distributing data content to the first peer.

13. The device of claim 11, wherein the processing unit further is configured to:

categorize the peers into different categories, wherein peers of one category are restricted from communicating with peers of a different category.

14. The device of claim 13, wherein the peers are categorized into different network address translation (NAT) categories.

15. The device of claim 13, wherein the processing unit further is configured to:

determine, for the distribution layer in which the first peer is arranged, which category has peers with least fulfilled data content download requirements.

16. The device of claim 15, wherein the processing unit is configured to, when determining which category has peers with least fulfilled data content download requirements:

calculate, for each peer in the category, the argument of the difference between number of required downloaded data sub-streams for fully rendering a data content streamed by the streaming source and the actual number of data sub-streams downloaded.

17. The device of claim 15, wherein the processing unit further is configured to:

determine which one of the peers in the category with the least fulfilled data content download requirement that has lowest upload capacity.

18. The device of claim 16, wherein the processing unit further is configured to:

determine, in the distribution layer immediately preceding that of the first peer, which categories have unutilized upload capacity and that further have capacity to upload the required number of data sub-streams such that a downloading peer in an immediately subsequent distribution layer is able to fully render a data content.

19. The device of claim 18, wherein the processing unit further is configured to:

identify the second peer as the peer having the greatest upload capacity among peers located in distribution layers subsequent to the distribution layer of the first peer, which peers further are able to download the data content from a peer in the determined category having unutilized upload capacity, have available upload capacity, and belong to a category which is allowed to upload data content to first peer.