On demand peer-to-peer video streaming with multiple description coding

• US 20060190615A1
• Filed: 01/23/2006
• Published: 08/24/2006
• Est. Priority Date: 01/21/2005
• Status: Active Grant

• Current Assignee: Polytechnic University (New York University)
• Original Assignee: Polytechnic University (New York University)
• Inventors: Panwar, Shivendra S., Ross, Keith W., Wang, Yao
• Granted Patent: US 7,633,887 B2
• Time in Patent Office: Days
• US Class Current: 709/231
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 65/70 Media network packetisation
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1048 Departure or maintenance mechanisms
• CPC Class Codes: H04L 67/1085 involving dynamic management of active down- or uploading connections
• CPC Class Codes: H04N 21/2668 Creating a channel for a dedicated end-user group, e.g. insertion of targeted commercials based on end-user profiles information retrieval from the Internet by querying with filtering and personalisation G06F16/9535; arrangements for replacing or switching information during the broadcast H04H20/10; push services over packet-switching network H04L12/1859; adaptation of message content in packet-switching networks H04L51/063
• 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/482 End-user interface for program selection broadcast systems using EPGs H04H60/72
• 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
• CPC Class Codes: H04N 21/6473 Monitoring network processes errors for recovering from a failure of a protocol instance or entity H04L69/40
• CPC Class Codes: H04N 21/64792 Controlling the complexity of the content stream, e.g. by dropping packets intermediate media network packet handling H04L65/765; proxy provisioning conversion or adaptation for reducing the amount or size of exchanged application data H04L67/5651; negotiation of resources in wireless networks H04W28/16
• CPC Class Codes: H04N 21/8405 represented by keywords

Abstract

A peer-to-peer novel video streaming scheme is described in which each peer stores and streams videos to the requesting client peers. Each video is encoded into multiple descriptions and each description is placed on a different node. If a serving peer disconnects in the middle of a streaming session, the system searches for a replacement peer that stores the same video description and has sufficient uplink bandwidth. Employing multiple description coding in a peer-to-peer based network improves the robustness of the distributed streaming content in the event a serving peer is lost. Video quality can be maintained in the presence of server peers being lost. The video codec design and network policies have a significant effect on the streamed video quality. The system performance generally improves as the number of descriptions M for the video increases, which implies that a higher video quality can be obtained with the same network loading.

Claims

1. A computer-implemented method for provisioning nodes in a peer-to-peer video streaming network, the method comprising:

a) accepting a maximum distortion constraint for a video;

b) accepting information of available server peers in the peer-to-peer video streaming network;

c) determining, for the video, both (1) video sub-streams, and (2) server peers on which to store the video sub-streams using both the accepted maximum distortion constraint and the accepted information of available server peers; and

d) transmitting the determined video sub-streams to the server peers on which it was determined to store the video sub-streams.

2. The computer-implemented method of claim 1 wherein the accepted information of available server peers includes an uplink bandwidth between each of the server peers and a transport network portion of the peer-to-peer video streaming network.

3. The computer-implemented method of claim 1 wherein the act of determining, for the video, both (1) video sub-streams, and (2) server peers on which to store the video sub-streams using both the accepted maximum distortion constraint and the accepted information of available server peers includes maximizing an acceptance probability of a video session subject to the video session meeting the maximum distortion constraint.

4. The computer-implemented method of claim 1 wherein the maximum distortion constraint is denoted as d_max, M denotes a number of descriptions of the video, r denotes a bit rate of each description, and Q denotes a number of ongoing video sessions, with each session consisting of a multiple sub-streams, and

wherein the act of determining, for the video, both (1) video sub-streams, and (2) server peers on which to store the video sub-streams using both the accepted maximum distortion constraint and the accepted information of available server peers includes

i) calculating

$P$

(m,M;

r,Q)={P⁡

(X=Qm/S),m=0,1,…

⁢

 

,M-1∑

l=MNS/Q⁢

P⁡

(X=Ql/S),m=M

for m=1, . . . ,M;

ii) calculating, from P(m, M;

r, Q), m=1, . . . ,M, the optimal multiple description-forward error connection partition (R₁, R₂, . . . , R_M) and a corresponding average distortion D(M, r, Q) using

$\min <br><br>\text{\hspace{1em}<br><br>}<br><br>D<br><br>\left(R_1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},R_M\right)<br><br>s.t<br><br>\underset{m=1}{\overset{M}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_m<br><br>R_m=\mathrm{Mr}$$\mathrm{where}$${\mathrm{\alpha <br><br>}}_m=\frac{M}{m<br><br>\left(m+1\right)},m=1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},M-1$$\mathrm{and}$${\mathrm{\alpha <br><br>}}_M=1;<br><br>$

iii) determining a triple (M, r, Q) to be feasible if D(M,r,Q)≦

d_max;

and

iv) setting M to M_max where M_max is largest number of descriptions determined to be feasible.

5. The computer-implemented method of claim 1 wherein the determined video sub-streams are multiple description-forward error correction partitions.

6. For use in a peer-to-peer video serving network including a plurality of peer nodes, each peer node being capable of acting as at least one of a client peer and a server peer, a computer-implemented method comprising:

a) accepting and storing peer information of the peer-to-peer video serving network;

b) accepting a video file for serving to a requesting client peer of the peer-to-peer video serving network;

c) provisioning server peers of the peer-to-peer video serving network to serve sub-streams of the video file;

d) accepting a request for the movie from a client peer of the peer-to-peer video serving network;

e) identifying server peers provisioned to serve sub-streams of the video file;

f) establishing a peer-to-peer session between the requesting client peer and the identified server peers;

g) serving, with each of the identified server peers, a sub-stream of the video file to the requesting client peer;

h) receiving, at the requesting client peer, the served sub-streams;

i) assembling, at the requesting client peer, a video from the received served sub-streams; and

j) storing or rendering the assembled video at the requesting client peer.

7. The computer-implemented method of claim 6 further comprising:

k) determining whether the assembled video meets or can meet a quality threshold;

l) if it is determined that the assembled video does not or cannot meet the quality threshold, establishing at least one new session with at least one alternative server peer; and

m) serving, with each of the at least one alternative server peers, a sub-stream of the video file to the requesting client peer.

8. The computer-implemented method of claim 6 wherein the act of identifying server peers provisioned to serve sub-streams of the video file is performed by a node other than the requesting server peer, and

wherein the act of establishing the peer-to-peer session between the requesting client peer and the identified server peers is initiated by a node other than the requesting client peer.

9. The computer-implemented method of claim 6 wherein the act of identifying server peers provisioned to serve sub-streams of the video file is performed by a node other than the requesting server peer, and

wherein the act of establishing the peer-to-peer session between the requesting client peer and the identified server peers is initiated by the requesting client peer.

10. A management facility for use in a peer-to-peer video serving network including a plurality of peer nodes, each peer node being capable of acting as at least one of a client peer and a server peer, the management facility comprising:

a) means for accepting a maximum distortion constraint for a video;

b) means for accepting information of available server peers in the peer-to-peer video streaming network;

c) means for determining, for the video, both (1) video sub-streams, and (2) server peers on which to store the video sub-streams using both the accepted maximum distortion constraint and the accepted information of available server peers; and

d) means for transmitting the determined video sub-streams to the server peers on which it was determined to store the video sub-streams to provision them to serve sub-streams of the video file.

11. The management facility of claim 10 wherein the means for determining, for the video, both (1) video sub-streams, and (2) server peers on which to store the video sub-streams using both the accepted maximum distortion constraint and the accepted information of available server peers include means for maximizing an acceptance probability of a video session subject to the video session meeting the maximum distortion constraint.

12. The management facility of claim 10 wherein the maximum distortion constraint is denoted as d_max, M denotes a number of descriptions of the video, r denotes a bit rate of each description, and Q denotes a number of ongoing video sessions, with each session consisting of a multiple sub-streams, and

wherein the means for determining, for the video, both (1) video sub-streams, and (2) server peers on which to store the video sub-streams using both the accepted maximum distortion constraint and the accepted information of available server peers include

i) means for calculating

$P$

(m,M;

r,Q)={P⁡

(X=Qm/S),m=0,1,…

⁢

 

,M-1∑

l=MNS/Q⁢

P⁡

(X=Ql/S),m=M

for m=1, . . . ,M;

ii) means for calculating, from P(m, M;

r, Q), m=1, . . . ,M, the optimal multiple description-forward error connection partition (R₁, R₂, . . . , R_M) and a corresponding average distortion D(M, r, Q) using

$\min <br><br>\text{\hspace{1em}<br><br>}<br><br>D<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(R_1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},R_M\right)$$s.t<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{m=1}{\overset{M}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_m<br><br>R_m=\mathrm{Mr}$$\mathrm{where}$${\mathrm{\alpha <br><br>}}_m=\frac{M}{m<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(m+1\right)},m=1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},M-1$$\mathrm{and}<br><br>\text{\hspace{1em}<br><br>}$${\mathrm{\alpha <br><br>}}_M=1;<br><br>\mathrm{and}$

iii) means for determining a triple (M, r, Q) to be feasible if D(M, r, Q)≦

d_max; and

iv) means for setting M to M_max where M_max is largest number of descriptions determined to be feasible.

13. The management facility of claim 10 wherein the determined video sub-streams are multiple description-forward error correction partitions.

14. The management facility of claim 10 further comprising:

e) means for accepting a request for the movie from a client peer of the peer-to-peer video serving network;

e) means for identifying server peers provisioned to serve sub-streams of the video file; and

f) means for facilitating the establishment a peer-to-peer session between the requesting client peer and the identified server peers.

15. The management facility of claim 14 wherein the means for facilitating the establishment of a peer-to-peer session between the requesting client peer and the identified server peers includes establishing, with the management facility, a session between the requesting client peer and the identified server peers.

16. The management facility of claim 14 wherein the means for facilitating the establishment of a peer-to-peer session between the requesting client peer and the identified server peers includes providing an identification of the identified server peers to the requesting client peer to enable the requesting client peer to establish a session between itself and each of the identified server peers.

17. The management facility of claim 14 further comprising:

g) means for identifying at least one alternative server peers provisioned to serve at least one of the sub-streams of the video file in the event of video degradation; and

h) means for facilitating the establishment a peer-to-peer session between the requesting client peer and each of the at least one identified alternative server peers.

18. The management facility of claim 17 wherein the means for facilitating the establishment of a peer-to-peer session between the requesting client peer and the identified at least one alternative server peers includes establishing, with the management facility, a session between the requesting client peer and the identified at least one alternative server peers.

19. The management facility of claim 17 wherein the means for facilitating the establishment of a peer-to-peer session between the requesting client peer and the identified at least one alternative server peers includes providing an identification of the identified at least one alternative server peers to the requesting client peer to enable the requesting client peer to establish a session between itself and each of the identified at least one alternative server peers.

20. The management facility of claim 10 wherein at least some of the peers have asymmetric connections with a transport network portion of the peer-to-peer video serving network such that a bandwidth of an upstream connection is less than the bandwidth of a downstream connection.

21. The management facility of claim 10 further comprising:

e) storage means for storing a directory of server peers and sub-streams stored on the server peers.

22. The management facility of claim 21 wherein the directory further includes state information of the server peers.

23. The management facility of claim 22 wherein the state information includes connectivity of the server to a transport network portion of the peer-to-peer video serving network.

24. The management facility of claim 22 wherein the state information includes available storage of the server peer.

25. The management facility of claim 22 wherein the state information includes upstream bandwidth of the server peer to a transport network portion of the peer-to-peer video serving network.