Multi-party cooperative peer-to-peer video streaming

This application claims the benefit, under 35 U.S.C.§365 of International Application PCT/US2006/028105, filed 20 Jul. 2006, which was published in accordance with PCT Article 21(2) on 24 Jan. 2008, in English.

The present invention relates generally to networking and specifically to a peer-to-peer (P2P) network for video content streaming.

Peer-to-Peer (P2P) networking has been proposed to support video content streaming service over the Internet. Each peer is implemented with both client and server functionality. The peers receive and cache the content, and stream the content to other peers. Due to the contribution from peers, the system, as a whole, can support more users than the traditional client-server service model.

In the current Internet, a large number of peers use ADSL or High-speed cable modems that have asymmetric upload/download bandwidth. The download bandwidth is typically much larger than the upload bandwidth. Therefore, although peers may have sufficient bandwidth to receive the streaming content, their upload bandwidth is not large enough to support other peers. The asymmetric bandwidth problem greatly affects the effectiveness of P2P video content streaming service.

Some prior art attempts to provide streaming service from multiple sources. Some prior art performs workload adjustment at the packet level. Other prior art schemes model the connections/links between peers as a Markov chain. Still other prior art schemes employ a probabilistic approach to solve the dynamic sub-stream adjustment problem.

The present invention provides a mechanism that allows a set of users (denoted as the sending peers herein) to collaboratively provide the streaming service to another user (denoted as the receiving peer) even if the individual sending peer's upload bandwidth is insufficient to stream the content to the receiving peer. The method and apparatus of the present invention solve the asymmetric bandwidth problem encountered in peer-to-peer video streaming service. As used herein peers include nodes, video playback devices, personal digital assistants (PDAs), computers including laptop computers, and any other devices capable of sending and receiving content in a per-to-peer network.

The present invention is a multi-party cooperative P2P streaming method that enables the peers with asymmetric bandwidth to cooperatively contribute bandwidth. The thrust of the present invention is to allow multiple sending peers to collaboratively stream the content to the receiving peer such that the aggregate upload bandwidth of sending peers is larger than the required streaming bandwidth, hence solving the asymmetric bandwidth problem.

A multi-party cooperative streaming method and apparatus are described including partitioning packets of a stream of content into sub-streams, allocating sub-streams for transmission evenly among the sending peers, issuing a command for the sending peers to simultaneously begin transmission of the sub-streams to a receiving peer and adjusting the number of sub-streams transmitted by the sending peers periodically.

A method and apparatus for transmitting data are described including partitioning a stream of data into a plurality of sub-streams, establishing an allocation of the plurality of sub-streams among a plurality of sending devices, enabling the plurality of sending devices to simultaneously begin transmitting the plurality of sub-streams in accordance with the allocation and adjusting the allocation.

The present invention is best understood from the following detailed description when read in conjunction with the accompanying drawings. The drawings include the following figures briefly described below where like-numbers on the figures represent similar elements:

FIG. 1 is a block diagram of an architecture of a sending peer in accordance with the present invention.

FIG. 2 is a block diagram of an architecture of a receiving peer in accordance with the present invention.

FIG. 3 is a flowchart of a method of the present invention.

FIG. 4 is an exemplary state diagram of a Minimum-Weight-Perfect-Matching scheme of the present invention.

The present invention allows a set of peers (sending) to collaboratively provide video content streaming service to another peer (receiving) even if the individual sending/forwarding peer's upload bandwidth is insufficient to individually stream the content to the receiving peer. The method and apparatus of the present invention solves the asymmetric bandwidth problem encountered in P2P video content streaming. The present invention pro-actively probes the upload bandwidth and constantly tries to optimize the video streaming quality.

More specifically, the present invention partitions the packets into sub-streams. Since a sub-stream is a collection of packets, it effectively reduces the signaling overhead, and simplifies the dynamic workload adjustment strategy. Further, the method and apparatus of the present invention actively probe the available bandwidth by injecting more traffic over certain paths. The present invention reacts more quickly to the changing network environment, which is critical in P2P network setting. The present invention formulates the dynamic sub-stream adjustment problem as a Minimum-Weight-Perfect-Matching problem.

Let {s i }, i=1, 2, . . . ,N, denote a set of N sending peers that have the content to stream to the destination/receiving peer, d. It is assumed that the N sending peers having the desired content have been identified by other means. The streaming video content is stored at the sending nodes as a collection of packets of equal size. Each of the identified sending nodes has a copy of the content. The packets have sequence numbers indicating their position in the video content stream. The video content stream is divided into M equal rate sub-streams. Each sub-stream has one packet out of every M packets. In the following, an apparatus is described that allows N peers to collectively send M sub-streams to d. Assume that the receiving peer d has the sufficient download bandwidth to receive the entire stream at rate r, while the sending peers, s i 's upload bandwidth is limited and may be less than the streaming rate r. The number of sub-streams, M, is chosen to be greater than the number of sending peers, N. The architecture of the sending and receiving peers, respectively is described first. Later the Minimum-Weight-Perfect-Matching (MWPM) based algorithm that dynamically adjusts the number of sub-streams carried by each sending peer so as to optimize the perceived streaming quality at the receiving peer is described.

As shown in FIG. 1 , a sending peer includes three components: a control message listener 105 , a sub-stream information database 110 and a data pump 115 . The control message listener 105 constantly monitors the incoming control message(s) from the receiving peer. When a control message arrives, the sending peer updates the sub-stream information database 110 accordingly. The control message is a triplet (action, sub_stream_id, time_offset). There are two types of actions that can be performed: add and delete. The control message listener 105 inserts the (sub_stream_id, time_offset) pair into the sub-stream information database 110 if the action is added, and deletes the entry in the sub-stream information database 110 with sub_stream_id if the action is deleted. The data pump 115 is responsible for sending/transmitting the sub-streams based on the sub-stream information database 110 .

As shown in FIG. 2 , the receiving peer has three types of components: a data receiver 205 , a streaming coordinator 210 and a control message sender 215 . One data receiver 205 is dedicated to receiving the data from one sending peer. The data receiver 205 receives the sub-streams sent from a corresponding sending peer and collects the streaming quality metric of the associated sub-streams. The streaming quality metric is defined to be the percentage of packets that arrived on time. The streaming coordinator 210 orchestrates the streaming from multiple sending peers in order to optimize the perceived the quality, i.e., the percentage of packets that arrive on time, at the receiving peer side. The control message sender 215 creates the control message(s) based on the input from the streaming coordinator 210 and sends the control message(s) to the targeted sending peers.

The streaming coordinator 210 monitors the streaming quality of sending peers, and dynamically adjusts the number of sub-streams assigned to each sending peer so as to optimize the overall streaming quality. FIG. 3 depicts a flowchart of the workflow of the streaming coordinator 210 , which consists of two phases—the initialization phase 305 and the dynamic adjustment phase 325 . The method used by the streaming coordinator 210 dynamically allocates the sub-streams to the sending peers in order to optimize the streaming quality by adapting to the fluctuating available bandwidth.

Since the available upstream bandwidth from sending peer s i to receiving peer, d, is unknown, in the initialization phase the streaming coordinator 210 evenly distributes the sub-streaming among all sending peers at 310 . The number of sub-streams carried by different sending peers may differ by one due to round-up error. The streaming coordinator 210 informs the sending peers of the set of sub-streams that they are requested to send/transmit at 315 . The streaming coordinator 210 then issues a command to the sending peers to start the streaming simultaneously at 320 .

In the dynamic adjustment phase 325 , the streaming coordinator 210 periodically adjusts the number of sub-streams carried/transmitted by each sending peers. This allows the sending peers to carry/transmit the number of substreams that correctly reflects their respective available upload bandwidth and hence optimizes the aggregate transmission quality of the video.

The streaming coordinator 210 monitors the transmission quality of the sending peers at 330 . The sending peers are sorted in the descending order of transmission quality. The method of the present invention swaps/exchanges m sub-streams between peers with good transmission quality and peers with poor transmission quality. The value of m is a configuration parameter and should be smaller than N/2. The top m ranked sending peers are denoted as strong sending peers; and the bottom m ranked sending peers are denoted as weak sending peers. By moving some of the workload from the weak peers to the strong peers, the aggregate transmission quality is maximized.

An epoch is a time interval over which the number of sub-streams each peer transmits is adjusted. The length of an epoch is a configuration parameter, which should be chosen small enough to swiftly capture the connection bandwidth change, and long enough to avoid unnecessary overhead introduced in the dynamic adjustment process. The epoch is for example 5 seconds. The dynamic adjustment process within an epoch includes two steps:try-out step and dynamic adjustment step. During the try-out step, the strong peers are asked to carry/transmit one more sub-stream for a short period of time and the transmission quality for each strong peer (with one more sub-stream than before) is measured and recorded at 335 . During the dynamic adjustment step 340 of the dynamic adjustment phase, the sub-streams are moved from the weak peers to the strong peers. At most one sub-stream can be moved away from a weak peer and at most one extra sub-stream can be carried by a strong peer. The rational behind this is to make the adjustment process stable and smooth.

In an embodiment, a Minimum-Weight-Perfect-Matching (MWPM) based dynamic sub-stream adjustment maximizes the transmission quality perceived by the receiving peer. Let {q i s } i=1 M and {{tilde over (q)} i s } i=1 M be the transmission quality of i-th strong peer before and after carrying one more sub-stream respectively, and {q i w } i=1 M be the transmission quality of j-th weak peer. It is assumed that the transmission quality of weak peers does not change as a result of carrying one less sub-stream. To illustrate the problem, consider the example in FIG. 4 that has three strong peers and three weak peers. A link between a strong peer and a weak peer represents a potential sub-stream change from the weak peer to the strong peer. The weight associated with the link denotes the gain of such exchange, specifically w ij denotes the link weight between i-th strong peer and j-th weak peer. Thus,

w ij = [ ( n i s + 1 N ⁢ q ~ i s + n j w - 1 N ⁢ q j w ) - ( n i s N ⁢ q i s + n j w N ⁢ q j w ) ] + , ( 1 )

where n i s denotes the number of sub-streams carried by i-th strong sending peer and n j w denotes the number of sub-streams carried by j-th weak sending peer.

The first term within the square brackets of equation (1) is the aggregate transmission quality of strong and weak peer after switching one sub-stream from the weak peer to the strong peer. The second term is the aggregate transmission quality before the sub-stream exchange. Since no sub-stream exchange occurs, if no transmission improvement can be achieved, [•] + is used to denote that the weight is non-negative. In case the weight is equal to zero, no sub-stream exchange is implied. The optimal sub-stream adjustment is equivalent to finding a perfect matching in the bi-partite graph that maximizes the sum of weights. A bi-partite graph is an undirected graph G=(V,E) in which V can be partitioned into two sets V1 and V2 such that (u,v) in E implies either u in V1 and v in V2 or u in V2 and v in V1. That is, all edges go between the two sets V1 and V2. This problem can be solved using the Minimum-Weight-Perfect-Matching algorithm of the present invention.

As the sub-stream adjustment continues, some sending peers can end up carrying no sub-streams. Such sending peers are called idle sending peers. One way to deal with such idle sending peers is to simply exclude them from the sending peer pool. Another way is to select an idle sending peer with a certain probability as strong peer and assign the idle sending peer one sub-stream to carry. The same algorithm described above is then applied. The rational is to give these idle sending peers a chance to contribute, in case their upload bandwidth has improved significantly since the last time interval (epoch).

In the above discussion, the link outage condition was not considered. In this situation, a link is broken and the connection between a sending peer and the receiving peer is lost. Such a condition is handled by setting up a threshold and actively excluding the un-connected (or badly connected) peers from the sending peer pool. For instance, the value of threshold can be set to δ. If a sending peer's transmission quality is lower than the threshold, it is removed from the sending peer pool and its sub-streams will be evenly distributed to the strong peers selected in the previous time interval (epoch).

It is to be understood that the present invention may be implemented in various forms of hardware, software, firmware, special purpose processors, or a combination thereof. Preferably, the present invention is implemented as a combination of hardware and software. Moreover, the software is preferably implemented as an application program tangibly embodied on a program storage device. The application program may be uploaded to, and executed by, a machine comprising any suitable architecture. Preferably, the machine is implemented on a computer platform having hardware such as one or more central processing units (CPU), a random access memory (RAM), and input/output (I/O) interface(s). The computer platform also includes an operating system and microinstruction code. The various processes and functions described herein may either be part of the microinstruction code or part of the application program (or a combination thereof), which is executed via the operating system. In addition, various other peripheral devices may be connected to the computer platform such as an additional data storage device and a printing device.

It is to be further understood that, because some of the constituent system components and method steps depicted in the accompanying figures are preferably implemented in software, the actual connections between the system components (or the process steps) may differ depending upon the manner in which the present invention is programmed. Given the teachings herein, one of ordinary skill in the related art will be able to contemplate these and similar implementations or configurations of the present invention.