Reducing or minimizing delays in peer-to-peer communications such as peer-to-peer video streaming
View Patent ↗A new P2P streaming method and apparatus disseminates video chunks to all peers with the minimum (or at least reduced) delay. After obtaining a new video chunk, a peer keeps transmitting (uploading) that video chunk to other peers until all peers receive it. The approach quickly increases the aggregate bandwidth that can be utilized to transmit a video chunk. For example, the aggregate peer bandwidth used to transmit a video chunk can double every time slot. For a homogeneous P2P streaming system with N peers, a time slot is defined as a unit of the single chunk transmission delay between two peers. Using the P2P streaming method, a video chunk can be disseminated to all peers within 1+log 2 N time slots.
1. A method for streaming data chunks in a peer-to-peer streaming system having N peers, the method comprising:
a) during a first time slot,
1) sending a first data chunk from a server to a first of the N peers, and
2) receiving the first data chunk with the first of the N peers;
b) during a second time slot,
1) sending a second data chunk from the server to a second of the N peers,
2) receiving the second data chunk with the second of the N peers, and
3) sending the first data chunk from the first of the N peers to a third of the N peers, and
4) receiving the first data chunk with the third of the N peers; and
c) during additional time slots following the first and second time slots, sending and receiving further data chunks such that all data chunks of a data stream can be disseminated to all of the N peers in 1+log 2 N time slots.
2. The method of claim 1 wherein the server serves at least two different data chunks to at least two different ones of the N peers.
3. A method for streaming data chunks in a peer-to-peer streaming system having N peers, the method comprising:
a) during a first time slot,
1) sending a first data chunk from a server to a first of the N peers, and
2) receiving the first data chunk with the first of the N peers;
b) during a second time slot,
1) sending a second data chunk from the server to a second of the N peers,
2) receiving the second data chunk with the second of the N peers, and
3) sending the first data chunk from the first of the N peers to a third of the N peers, and
4) receiving the first data chunk with the third of the N peers; and
c) during a j th time slot, where j is at least 3,
1) sending an i th data chunk from a number M of peers having the i th data chunk to M other peers, and
2) receiving with the M other peers, the i th data chunk,
whereby aggregate peer bandwidth used to transmit any of the first, second, or i th data chunk doubles with each of a plurality of time slots after it is first sent from the server.
4. The method of claim 3 further comprising:
d) during a (j+1) th time slot,
1) sending an (i+1) th data chunk from M peers having the (i+1) th data chunk to M other peers,
2) receiving with the M other peers, the (i+1) th data chunk,
3) sending an i th data chunk from 2M peers having the i th data chunk to 2M other peers, and
4) receiving with the 2M other peers, the i th data chunk.
5. The method of claim 1 further comprising:
classifying each of the N peers into a hierarchy according to respective offered upload capacities of the N peers, such that peers classified at the first level of the hierarchy have higher offered upload capacities than peers classified at any lower level of the hierarchy,
wherein the first of the N peers and the second of the N peers are classified in the first level of the hierarchy.
6. The method of claim 5 wherein the server only sends data chunks to those of the N peers classified in the first level of the hierarchy.
7. The method of claim 5 wherein peers classified at one level of the hierarchy only send data chunks to peers classified at a next lower level of the hierarchy.
8. The method of claim 7 wherein the peers classified at the next lower level of the hierarchy only receive data chunks from peers classified at the one level of the hierarchy.
9. The method of claim 5 wherein at least some of the N peers have no offered upload capability and the at least some of the N peers are classified in a lowest level of the hierarchy.
10. A method for streaming data chunks in a peer-to-peer streaming system having N peers, the method comprising:
a) during a first time slot,
1) sending a first data chunk from a server to a first of the N peers, and
2) receiving the first data chunk with the first of the N peers;
b) during a second time slot,
1) sending a second data chunk from the server to a second of the N peers,
2) receiving the second data chunk with the second of the N peers, and
3) sending the first data chunk from the first of the N peers to a third of the N peers, and
4) receiving the first data chunk with the third of the N peers; and
c) during a j th time slot, where j is at least 3,
1) sending an i th data chunk from a number M of peers having the i th data chunk to M other peers, and
2) receiving with the M other peers, the i th data chunk,
whereby the number of peers used to transmit any of the first, second, or i th data chunk doubles with each of a plurality of time slots after it is first sent from the server.
11. The method of claim 10 further comprising:
d) during a (j+1) th time slot,
1) sending an (i+1) th data chunk from M peers having the (i+1) th data chunk to M other peers,
2) receiving with the M other peers, the (i+1) th data chunk,
3) sending an i th data chunk from 2M peers having the i th data chunk to 2M other peers, and
4) receiving with the 2M other peers, the i th data chunk.