Method of data request scheduling in peer-to-peer sharing networks

• US 7,991,906 B2
• Filed: 12/09/2008
• Issued: 08/02/2011
• Est. Priority Date: 12/09/2008
• Status: Active Grant

• Current Assignee: Hong Kong Applied Science And Technology Research Institute Co., Ltd.
• Original Assignee: Hong Kong Applied Science And Technology Research Institute Co., Ltd.
• Inventors: Lam, Tak Wing, Chen, Liang Qiao, Ng, Chun Yin, Wu, Kang Heng
• Primary Examiner(s): Maung; Zarni
• Application Number:
  US12/331,360
• Publication Number:
  US 20100146138A1
• Time in Patent Office: 966 Days
• Field of Search: 709/205, 709223-225, 709/229, 709231-236, 709/250
• US Class Current: 709/231
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/108 characterised by resources being split in blocks or fragments
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests

Abstract

Systems and methods are provided for scheduling data requests for streaming media data in a Peer-to-Peer (P2P) network. A method is provided to increase a peer'"'"'s contribution to the whole P2P network by partitioning the data chunks to request into several regions according to their relative time urgency, and data requests are scheduled in an effort to maintain availability of data in each region to a corresponding predefined target amount.

Claims

1. A method comprising:

logically dividing streaming media content to be played by a peer in a peer-to-peer (P2P) network into a plurality of time-ordered data chunks;

partitioning a buffer map on the peer into a plurality of time-urgency ordered regions;

defining, for each of the regions, a respective target fullness amount;

populating the buffer map with information that identifies at least a plurality of to-be-played data chunks of the streaming media content;

populating the buffer map with information that indicates which of the plurality of to-be-played data chunks are available at the peer;

assigning each the plurality of to-be-played data chunks to one of the plurality of time-urgency ordered regions of the buffer map according to relative time urgency of the plurality of to-be-played data chunks; and

determining a schedule for requesting one or more of the to-be-played data chunks from one or more neighboring peers based at least in part on the buffer map and the defined target fullness amounts of the regions.

2. The method of claim 1 wherein said determining the schedule comprises:

determining, for each of the time-urgency ordered regions, an amount of the region'"'"'s assigned to-be-played data chunks that are available at the peer;

determining, for each of the time-turgency ordered regions, whether the determined amount of available to-be-played data chunks of the region satisfies the respective target fullness amount defined for the region; and

when determined that the amount of available to-be-played data chunks of a region does not satisfy the region'"'"'s target fullness amount, then scheduling a request of at least one of the unavailable to-be-played data chunks of that region from a neighboring peer.

3. The method of claim 2 wherein said scheduling a request of at least one of the unavailable to-be-played data chunks of that region from a neighboring peer comprises:

selecting an unavailable to-be-played data chunk of that region to be requested from a neighboring peer.

4. The method of claim 3 wherein said selecting comprises randomly selecting from all unavailable to-be-played data chunks of that region said unavailable to-be-played data chunk to be requested from a neighboring peer.

5. The method of claim 3 wherein said selecting is not required to select a most time urgent one of unavailable to-be-played data chunks of that region.

6. The method of claim 3 wherein said scheduling a request of at least one of the unavailable to-be-played data chunks of that region from a neighboring peer further comprises:

determining one or more neighboring peers at which the selected unavailable to-be-played data chunk is available.

7. The method of claim 6 wherein said determining said one or more neighboring peers comprises:

periodically receiving at said peer respective buffer maps for neighboring peers; and

determining from said received buffer maps said one or more neighboring peers at which the selected unavailable to-be-played data chunk is available.

8. The method of claim 6 further comprising:

selecting one of said one or more neighboring peers at which the selected unavailable to-be-played data chunk is available from which to request the unavailable to-be-played data chunk.

9. The method of claim 8 wherein said selecting said one of said one or more neighboring peers comprises:

randomly selecting said one of said one or more neighboring peers.

10. The method of claim 1 wherein defining, for each of the regions, said respective target fullness amount comprises:

defining a first target fullness amount for a first of said regions;

defining a second target fullness amount for a second of said regions;

wherein said first of said regions has greater time-urgency than said second of said regions, and wherein said first target fullness amount is greater than said second target fullness amount.

11. The method of claim 10 wherein said first of said regions has greater time-urgency because it is assigned ones of said plurality of to-be-played data chunks that are to be played before ones of said plurality of to-be-played data chunks that are assigned to said second of said regions.

12. The method of claim 1 wherein defining, for each of the regions, said respective target fullness amount comprises:

defining a different target fullness amount for each of the regions in relation to the relative time urgency of each of the regions.

13. The method of claim 1 wherein said target fullness amount defined for one of the regions specifies an amount of to-be-played data chunks assigned to said one of the regions that are desired to be available at the peer.

14. The method of claim 13 wherein a data chunk is available at the peer once all data packets of the data chunk have been received at the peer.

15. The method of claim 1 wherein each of said plurality of time-ordered data chunks comprises a predefined length of playback time of the streaming media content.

16. The method of claim 1 wherein the streaming media content comprises live streaming media content.

17. A method comprising:

logically dividing streaming media content to be played by a peer in a peer-to-peer (P2P) network into a plurality of time-ordered data chunks;

partitioning a buffer map on the peer into a plurality of time-urgency ordered regions;

defining, for each of the regions, a respective target fullness amount;

populating the buffer map with information that identifies at least a plurality of to-be-played data chunks of the streaming media content;

populating the buffer map with information that indicates which of the plurality of to-be-played data chunks are available at the peer;

assigning each the plurality of to-be-played data chunks to one of the plurality of time-urgency ordered regions of the buffer map according to relative time urgency of the plurality of to-be-played data chunks;

for each of the time-urgency ordered regions, determining whether an amount of available to-be-played data chunks therein satisfies the region'"'"'s corresponding target fullness amount; and

when determined that the amount of available to-be-played data chunks in one of the time-urgency ordered regions does not satisfy the region'"'"'s corresponding target fullness amount, selecting an unavailable to-be-played data chunk from the one of the time-urgency ordered regions for requesting from a neighboring peer.

18. The method of claim 17 wherein said selecting said unavailable to-be-played data chunk comprises randomly selecting from all unavailable to-be-played data chunks of said one of the time-urgency ordered regions said unavailable to-be-played data chunk to be requested from a neighboring peer.

19. The method of claim 17 wherein said selecting is not required to select a most time urgent one of unavailable to-be-played data chunks of said one of the time-urgency ordered regions.

20. The method of claim 17 wherein defining, for each of the regions, said respective target fullness amount comprises:

defining a different target fullness amount for each of the regions in relation to the relative time urgency of each of the regions.

21. The method of claim 17 wherein said target fullness amount defined for one of the regions specifies an amount of to-be-played data chunks assigned to said one of the regions that are desired to be available at the peer.

22. The method of claim 21 wherein a data chunk is available at the peer once all data packets of the data chunk have been received at the peer.

23. The method of claim 17 wherein the streaming media content comprises live streaming media content.

24. A system comprising:

a peer communicatively coupled to one or more other peers via a peer-to-peer (P2P) network said peer comprising;

a player for rendering streaming content;

a buffer for buffering streaming content for playing by the player;

a buffer map that includes

a) information identifying at least a plurality of to-be-played time-ordered data chunks of the streaming media content, and

b) a bitmap indicating which of the plurality of to-be-played data chunks are available at the peer;

wherein the buffer map is partitioned into a plurality of time-urgency ordered regions, and each the plurality of to-be-played data chunks is assigned to one of the plurality of time-urgency ordered regions of the buffer map according to relative time urgency of the plurality of to-be-played data chunks;

a scheduler for requesting one or more of the to-be-played data chunks from one or more neighboring peers based at least in part on the buffer map and target fullness amounts predefined for the plurality of time-urgency ordered regions.

25. The system of claim 24 wherein said scheduler is configured to:

determine, for each of the time-urgency ordered regions, an amount of the region'"'"'s assigned to-be-played data chunks that are available at the peer;

determine, for each of the time-urgency ordered regions, whether the determined amount of available to-be-played data chunks of the region satisfies a respective target fullness amount defined for the region; and

when determined that the amount of available to-be-played data chunks of a region does not satisfy the region'"'"'s target fullness amount, schedule a request of at least one of the unavailable to-be-played data chunks of that region from a neighboring peer.