System and method for erasure coding of streaming media

• US 20060069800A1
• Filed: 09/28/2004
• Published: 03/30/2006
• Est. Priority Date: 09/03/2004
• Status: Abandoned Application

• Current Assignee: Rovi Technologies Corporation (Adeia Inc.)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Jin
• Application Number:
  US10/951,481
• Publication Number:
  US 20060069800A1
• Time in Patent Office: Days
• US Class Current: 709/232
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053
• CPC Class Codes: H04L 67/108 characterised by resources being split in blocks or fragments
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

A “PeerStreamer” provides receiver-driven peer-to-peer (P2P) media streaming for loosely coupled P2P networks. Peers in the network perform only simple operations, may cache all or part of the streaming media, do not collaborate with other peers, may be unreliable, and may drop offline or come online during any given streaming session. Clients in the network operate in real-time to coordinate peers, stream media from multiple peers, perform load balancing, handle online/offline states of peers, and perform decoding and rendering the streaming media. In one embodiment, the PeerStreamer uses high rate erasure resilient coding to allow multiple serving peers to hold partial media without conflict, such that clients simply retrieve fixed numbers of erasure coded blocks regardless of where and what specific blocks are retrieved. In another embodiment, the PeerStreamer uses embedded coded media to vary streaming bitrates according to available serving bandwidths and client queue status.

Claims

1. A computer-readable medium having computer executable instructions for providing client-driven multimedia streaming in a peer-to-peer (P2P) network, said computer executable instructions comprising:

separating an encoded media file into a media header with one or more data packets, and a media body comprising n data packets;

separating each data packet into at least one data units;

separating each data unit into k original data blocks;

erasure encoding the k original data blocks of each data unit to generate from 1 to k erasure coded data blocks for each of a plurality of arbitrary serving peers in a cluster of serving peers, and storing the resultant erasure coded data blocks on those serving peers;

for each data unit, using a client computer to retrieve a total of a number (k′

) of erasure coded data blocks from arbitrary serving peers in the cluster, where k′

is greater than or equal to k;

using the client computer to reconstruct each data unit from the k′

retrieved erasure coded data blocks;

using the client computer to retrieve the media header from one of the serving peers; and

using the client computer to reconstruct the data packets of the media body from the reconstructed data units.

5. The computer-readable medium of claim 1 wherein each serving peer in the cluster of available serving peers is assigned a fixed erasure coding key space.

6. The computer-readable medium of claim 5 wherein the fixed erasure coding key space assigned to each serving peer in the cluster of available serving peers is determined by a server computer.

7. The computer-readable medium of claim 5 wherein the fixed erasure coding key space assigned to each serving peer in the cluster of available serving peers is determined by having each serving peer randomly generate its own set of erasure coding keys.

8. The computer-readable medium of claim 5 wherein prior to retrieving any erasure coded data blocks, the client computer invalidates one or more of the duplicated keys of the serving peers, such that no requests of erasure coded data blocks of the same key will be made to more than one available serving peer sharing the same erasure coding key.

9. The computer-readable medium of claim 1 wherein client requests for retrieval of each erasure coded data block include an ID of each corresponding data unit, a start erasure coded data block index of the corresponding data unit, and the number of erasure coded data blocks to be retrieved for the corresponding data unit.

10. The computer-readable medium of claim 1 further comprising providing real-time client-based decoding of the reconstructed data packets to provide streaming media transmission to the client from one or more of the serving peers.

11. The computer-readable medium of claim 1 further comprising providing buffered client-based decoding of the reconstructed data packets to provide streaming media transmission to the client from one or more of the serving peers, and wherein the buffer is used to provide the client with sufficient time to respond to network packet loss and jitter.

12. The computer-readable medium of claim 1 further comprising using the client computer for retrieving a list of the serving peers in the cluster of available serving peers prior to retrieving any erasure coded data blocks.

13. The computer-readable medium of claim 12 wherein retrieving the list of the serving peers comprises any of retrieving the list from one of the serving peers, retrieving the list from a server computer, and performing a distributed hash table (DHT) lookup to identify the serving peers.

14. The computer-readable medium of claim 12 further comprising retrieving an availability vector for each serving peer in the list of serving peers, and wherein the availability vector includes at least an identification of the erasure coding key space and the number of erasure coded data blocks for each data unit for the corresponding serving peer.

15. The computer-readable medium of claim 1 wherein the list of the serving peers is periodically updated during the streaming media transmission to the client.

16. The computer-readable medium of claim 1 wherein communications between the client and each serving peer, including client transmission requests and serving peer transmissions, is accomplished using a TCP communications protocol.

17. The computer-readable medium of claim 1 wherein communications between the client and each serving peer use an automatic repeat request (ARQ) protocol to retransmit lost or delayed packets.

18. The computer-readable medium of claim 1 wherein the encoded media file is embedded coded.

19. The computer-readable medium of claim 1 further comprising determining a serving bandwidth of each serving peer, and wherein the number of erasure coded data blocks that are generated and stored on each serving peer is proportional to the corresponding serving bandwidth, and is inversely proportional to the media bitrate, subject to a maximum of k blocks, so that each serving peer is not required to hold more coded data blocks than it is capable of serving.

20. The computer-readable medium of claim 19 wherein the number of erasure coded data blocks to be retrieved from each serving peer is determined by the client computer as a function of the availability vector of the serving peer, which contains the number of erasure coded data blocks held by the serving peer, and each serving peers serving bandwidth, so that each serving peer is not requested to provide more erasure coded data units than it holds.

47. The computer-readable medium of claim 1 wherein the each data packet is embedded coded, and each data unit has a corresponding bitrate.

48. The computer-readable medium of claim 47 further comprising determining a serving bandwidth of each serving peer, and wherein the number of erasure coded data blocks that are generated and stored on each serving peer is proportional to the corresponding serving bandwidth, and is inverse proportional to the bitrate of the data unit, subject to a maximum of k blocks, so that each serving peer is not required to hold more coded data blocks than it is capable of serving.

21. (canceled)

2. The computer-readable medium of claim 1 wherein a maximum distance separable (MDS) erasure code is used, so that k′

is equal to k.

3. The computer-readable medium of claim 2 wherein erasure coding the data units comprises using a Reed-Solomon erasure code, which is an MDS erasure code to generate the 1 to k erasure coded data blocks for each data unit.

4. The computer-readable medium of claim 3 wherein using the client computer to reconstruct each data unit from the k retrieved erasure coded data blocks comprises performing Reed-Solomon erasure decoding operations on each set of k retrieved erasure coded data blocks to reconstruct each data unit.

22. (canceled)

23. The method of claim 21 wherein distributing subsets of erasure coded data blocks of the encoded media file comprises:

separating a media body of the encoded media file into n data packets;

separating each data packet into one or more data units;

separating each data unit into k original data blocks; and

erasure coding the k original data blocks of each data unit to generate 1 to k erasure coded data blocks for each data unit.

24. The method of claim 23 wherein arbitrarily distributing subsets of erasure coded data blocks to the available serving peers comprises arbitrarily storing between 1 and k of the erasure coded data blocks of each data unit on each of the available serving peers.

25. The method of claim 21 wherein decoding each packet received in response to the data block transmission requests comprises using the client computer to:

reconstruct each data unit from the retrieved erasure coded data blocks;

reconstruct the data packets of the media body from the reconstructed data units; and

assembling the reconstructed data units to provide a decoded version of the encoded media file.

26. The method of claim 23 wherein erasure coding the k original data blocks comprises using a Reed-Solomon erasure code to generate the 1 to k erasure coded data blocks for each data unit.

27. The method of claim 21 wherein each available serving peer is assigned a fixed erasure coding key space.

28. The method of claim 27 wherein the fixed erasure coding key space assigned to each available serving peer is determined by a server computer.

29. The method of claim 27 wherein each serving peer randomly generates its own fixed erasure coding key space.

30. The method of claim 27 wherein the client computer invalidates one or more of any duplicated keys in the serving peers, such that no requests for erasure coded data blocks of the same key will be made to more than one available serving peer.

31. The method of claim 21 wherein the decoding and rendering of each packet on the client computer is at least partially buffered.

32. The method of claim 21 further comprising determining a serving bandwidth of each serving peer that is available for serving the client computer.

33. The method of claim 32 wherein arbitrarily distributing subsets of erasure coded data blocks to each serving peer further comprises distributing a number of erasure coded data blocks to each serving peer that is proportional to the serving bandwidth of each serving peer.

34. The method of claim 32 wherein the specific number of erasure coded data blocks requested to be transmitted from specific serving peers is proportional to the serving bandwidth of those serving peers.

21-1. A method for streaming media to one or more clients in a peer-to peer (P2P) network, comprising using a computing device to:

arbitrarily distribute subsets of erasure coded data blocks generated from data packets of an encoded media file to each of a plurality available serving peers;

on each serving peer, determine an availability vector which defines exact subsets of erasure coded data blocks held by the corresponding serving peer;

provide a list of the available serving peers to a client computer following a client request;

on the client computer, use the list of available serving peers provided to download the availability vector for each listed serving peer, and to further download a media header of the encoded media file from one or more of the serving peers;

on the client computer, request transmission of a specific number of erasure coded data blocks for each data packet from one or more specific serving peers based on a client computer analysis of the availability vectors and on the list of available serving peers; and

decode and render each packet received in response to the data block transmission requests to provide real-time streaming media playback on the client computer.

22-2. The method of claim 21 wherein the availability vectors contains at least an identification of the erasure coding key space, and the number of erasure coded blocks for each data packet held.

35. A system for providing coordinated receiver-driven media streaming to one or more clients from one or more non-cooperating peers, comprising:

separating an encoded media file into a media header with one or more data packets, and a media body comprising n data packets and storing the media header on one or more available serving peers;

separating each data packet into one or more data units;

separating each data unit into k original data blocks;

for each available serving peer, erasure coding the k original data blocks of each data packet to generate 1 to k erasure coded data blocks for each data unit, and storing the 1 to k erasure coded data blocks on each of the corresponding serving peers;

on each serving peer, determine an availability vector which defines at least an identification of an erasure coding key space and the number of erasure coded data blocks for each data packet held by the corresponding serving peer;

providing a list of the available serving peers to a client computer in response to a client request;

on the client computer, retrieving the media header from one of the serving peers;

on the client computer, downloading the availability vector for each listed serving peer;

on the client computer, downloading the media header from one of the serving peers;

on the client computer, using the availability vectors for requesting downloads of a total of k′

erasure coded data blocks for each data unit from a set of one or more of the available serving peers, where k′

is greater than or equal to k;

using the client computer to reconstruct each data unit from the k′

downloaded erasure coded data blocks; and

using the client computer to reconstruct the data packets of the media body from the reconstructed data units.

36. The system of claim 35 further comprising providing real-time client-based decoding of the reconstructed data packets to provide streaming media transmission to the client from one or more of the serving peers.

37. The system of claim 35 further comprising providing buffered client-based decoding of the reconstructed data packets for providing the client with sufficient time to automatically respond to network packet loss and jitter.

38. The system of claim 35 wherein erasure coding the m data units comprises using a Reed-Solomon erasure code to generate the k erasure coded data blocks for each data unit.

39. The system of claim 36 wherein using the client computer to reconstruct each data unit from the k retrieved erasure coded data blocks comprises performing Reed-Solomon erasure decoding operations on each set of k retrieved erasure coded data blocks to reconstruct each data unit.

40. The system of claim 35 wherein each available serving peer is assigned a fixed erasure coding key space.

41. The system of claim 40 wherein the fixed erasure coding key space assigned to each available serving peer is automatically determined by a server computer.

42. The system of claim 40 wherein the fixed erasure coding key space assigned to each available serving peer is determined by having each serving peer randomly generate its own erasure coding key.

43. The system of claim 40 wherein the client computer invalidates one or more keys of the available serving peers having a duplicate key in the erasure coding key space.

44. The system of claim 35 wherein the fixed wherein the client requested downloads of the erasure coded data blocks include an ID of each corresponding data unit, a start block index of the corresponding data unit, and the number of erasure coded data blocks to be retrieved for the corresponding data unit.

45. The system of claim 35 wherein the number, 1 to k, of erasure coded data blocks on each of the corresponding serving peers is proportional to a serving bandwidth of each serving peer.

46. The system of claim 35 wherein the number k′

of each requested download of k′

of erasure coded data blocks is proportional to a serving bandwidth of each serving peer.