Patent ID: 8005975

Claim:
A method for scheduling the streaming of data chunks in a peer-to-peer streaming system having N peers, the method comprising, for each time slot: a) determining whether data chunk transmissions scheduled in previous time slots will have finished at the start of the current time slot; b) for each data chunk which will have finished transmission, 1) indicating that the source peer of the transmission is idle for the current time slot, and 2) indicating the data chunk which will have finished transmission as belonging to a buffered data chunk set of the destination peer of the transmission; c) determining a demand factor d k for a data chunk k that has been generated by the data source server, but has not been scheduled for uploading to all peers, wherein demand factor d k is proportional to a number of the N peers which will be without the data chunk k, and is inversely proportional to a number of the N peers which will have the data chunk; d) determining an expected workload for each peer to upload data chunks to peers without them using a sum of demand factors for any data chunks that the peer is buffering; e) for each of the data chunks that will not have been received by all of the N peers and starting with the oldest of these data chunks, 1) determining an idle peer with a lowest expected workload per offered upload capacity factor that has the data chunk; 2) defining the determined idle peer with the lowest expected workload per offered upload capacity factor that has the data chunk as a source peer for the data chunk, 3) determining a peer that does not yet have the data chunk, that does not have a scheduled delivery of the data chunk, and a lowest expected workload per offered upload capacity factor, 4) defining the determined peer that does not yet have the data chunk, that does not have a scheduled delivery of the data chunk, and a lowest expected workload per offered upload capacity factor as a destination peer for the data chunk, 5) scheduling having the source peer transmit the data chunk to the destination peer during the time slot by marking the source peer as being busy and marking the destination peer with a scheduled delivery of the data chunk, and 6) repeating (e)(1)-(e)(5) while there are peers missing the data chunk, until no source peer destination peer pair for the data chunk can be determined.