Peer-to-peer collaborative streaming among mobile terminals

Systems and methods for collaborative streaming among mobile terminals. Periodically, the mobile terminals may pull a portion of the data stream from a content provider coupled thereto over a primary channel and distribute the pulled data to neighboring mobile terminals, possibly including other mobile terminals pulling portions of the data stream from the content provider and passive mobile terminals that are only receiving pulled data. By transferring data over the secondary channel, the cost to any one terminal to receive the data stream is reduced.

BACKGROUND AND SUMMARY OF THE INVENTIONS

The present application relates to data streaming techniques, and more particularly to peer-to-peer (P2P) collaborative streaming of content between mobile terminals of an ad-hoc network.

BACKGROUND

Mobile Streaming Systems

In recent years, the use of wireless networks to distribute content within a service area thereof has become increasingly common. For example, a mobile terminal within range of a base station of a third generation (3G) cellular network is capable of “pulling content” from a remote server, for example, a media server, residing at or coupled to the base station. While some content is freely disseminated, more typically, the user of the mobile terminal is charged a fee for the content streamed thereto. As many such fees are based upon the amount of data streamed to the mobile terminal, the streaming of large amounts of content can prove quite costly to the user.

Limitations on the capacity of the 3G cellular network to distribute content also serve to maintain the high cost of multimedia streaming services. For example, a 3G cellular network typically has a limited number of channels which may be used by the mobile terminals to pull content. As the resources available to dedicate to multimedia streaming services are relatively fixed and cannot be readily expanded to meet a rising demand for such services, multimedia streaming services are not scalable and, as a result, remain costly regardless of the demand therefor. Other limitations have also served to discourage widespread usage of multimedia streaming services. For example, in order to receive a data stream, a mobile terminal must be within range of the base station or other transmitter of the content stream. As a result, loss of a portion of the data stream may result if the mobile terminal temporarily leaves the coverage area or otherwise loses the signal from the base station.

Integrated cellular and ad-hoc relaying (“iCAR”) systems have contemplated the use of a secondary channel for transporting data. However, iCAR systems focus on relaying data from the mobile terminal to the base station and provide little guidance with respect to streaming data from the base station to the mobile terminal. Moreover, as the relay points utilized by iCAR systems are stationary and reliable, there is no need for iCAR systems to address a number of fault issues that arise when a mobile terminal moves out of range or otherwise loses the signal of the base station. The Swarming Protocol for vehicular Ad-hoc Wireless Networks (“SPAWN”) has contemplated the use of an ad-hoc network for the delivery of content in vehicular networks. However, since SPAWN utilizes a gossip mechanism to exchange information between users, undesirable exchange overhead is introduced into point-to-point communications.

Finally, a Cooperating ad-hoc environment to support messaging (“CHUM”) network shares multimedia data among mobile devices in an ad-hoc manner. However, as a CHUM network seeks to minimize the streaming cost of the entire ad-hoc network, it chooses one peer, generally referred to as a proxy, to pull multimedia data from the content provider. In turn, the proxy uses a tree topology structure to forward the multimedia data to all of the other peers of the ad-hoc network. As a result, in order to determine the tree path to be used to distribute content, each peer must collect information from its neighbors. Furthermore, to ensure that each peer incurs a fair share of the cost of streaming data from the content provider, a CHUM network employs a mechanism which enables peers to take turns acting as proxy. For this reason, CHUM networks require that a proxy scheduling queue for storing the order of the next proxy be maintained.

The present application provides new methods for collaborative streaming of content between peers—mobile terminals that are nodes of an ad-hoc meshed network. In various embodiments, certain mobile terminals (or “pullers”) within range of a base station randomly select a portion of the content to pull over the cellular channel. The pullers then share the content with neighboring mobile terminals with which the pullers have established links over free secondary channels. In order to fairly share the cost of streaming content, the mobile terminals take turns pulling content over the cellular channel.

In one class of embodiments, dynamic broadcast scope is used, with rules which limit rebroadcasting of locally superfluous video descriptions. To accomplish this, in a preferred implementation, the mobile terminal collects information from the neighboring mobile terminals.

The disclosed inventions, in various embodiments, can provide some or all of the following advantages, among others:Provides a scalable and cost-effective P2P collaborative streaming process which distributes multimedia content without the high streaming costs and system scalability issues associated with traditional mobile streaming networks.Enables mobile terminals to pull down portions of a multimedia data stream for sharing with neighboring mobile terminals.Uses free secondary wireless channels such as WiFi and Bluetooth to form an ad-hoc network over which the pulled portions of the multimedia data stream may be distributed.Provides good video quality and better utilization of wireless channel.Achieves fairness in streaming cost sharing by having the mobile terminals take turns pulling multimedia data.Handles network dynamics in the presence of users joining leaving or transmission failing.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

The numerous innovative teachings of the present application will be described with particular reference to the presently preferred embodiment (by way of example, and not of limitation).

A system100for collaborative streaming among mobiles (COSMOS) will now be described in greater with respect toFIG. 1. In the embodiment disclosed herein, the COSMOS system100is comprised of a first (or “primary”) network102and a second (or “secondary”) network107. Preferably, the primary network102is the Internet and the secondary network107is either a Wi-Fi network conforming to IEEE 802.1.1 or a Bluetooth network. As will be more fully described below, the COSMOS system100enables the transfer of data, hereinafter referred to as “content,” between (a) mobile terminals wirelessly coupled to the primary network102and other mobile terminals wirelessly coupled to the primary network102and (b) mobile terminals wirelessly coupled to the primary network102and mobile terminals that are not wirelessly coupled to the primary network102.

The primary network102is comprised of a wide variety of interconnected computing devices such as personal computers (PCs) and servers. While a large scale network such as the Internet includes a multitude of computing devices, for ease of illustration,FIG. 1shows only a single such device104. As disclosed herein, the device104is a content provider, for example, a media server, configured for downloading content, for example, streaming video, to requesting devices. Of course, it is fully contemplated that the device104may instead be any one of a wide array of devices capable of transferring data to a selected target device. The primary network102further includes one or more wireless access points (WAPs) such as base stations. As before, while a large scale network such as the Internet102may include a multitude of WAPs of a variety of types, for ease of illustration,FIG. 1shows only a first base station106A, a second base station106B and a third base station106G. As disclosed herein, a base station or other type of WAP is an access point at which a device such as a mobile terminal may wirelessly access the Internet. Variously, a WAP may be a public WAP accessible to all members of the public without charge or a private WAP, typically maintained by an Internet Service Provider (ISP) who limits access to the Internet through the private WAP to customers who have paid a fee to the ISP. In the embodiment disclosed herein, each of the first, second and third base stations106A,106B and106G are maintained by ISPs.

The secondary network107is comprised of any number of mobile terminals capable of establishing (a) a direct or indirect connection with the primary network106and/or a selected component thereof; and (b) a direct or indirect connection with other mobile terminals forming part of the secondary network107. While it is contemplated that the secondary network107will typically include a large number of mobile terminals, for ease of illustration,FIG. 1shows but five such mobile terminals—first mobile terminal108A, second mobile terminal108B, third mobile terminal108G, fourth mobile terminal108D and fifth mobile terminal108E. In accordance with the embodiment illustrated inFIG. 1, the first, second and sixth mobile terminals108A,108B and108F are mobile telephones while the third, fourth and fifth mobile terminals108G,108D and108E are personal digital assistants (PDAs) In further accordance with the embodiment illustrated inFIG. 1, various ones of the mobile terminals have established primary channels between themselves and the ISP base stations of the primary network102, thereby enabling the mobile terminals to become coupled to selected devices of the primary network102. For example, inFIG. 1, the first mobile terminal108A is coupled to the content provider104through the first ISP base station106A, the third mobile terminal108C is coupled to the content provider104through the second ISP base station106B and the fifth mobile terminal108E is coupled to the content provider104through the third ISP base station106C.

In further accordance with the embodiment illustrated, inFIG. 1, various ones of the mobile terminals have established wireless channels between themselves and certain others of the mobile terminals forming part of the secondary network104. For example, inFIG. 1, mobile terminal108A is coupled to the mobile terminal108C by secondary wireless channel110AC, mobile terminal108B is coupled to mobile terminal108C by secondary wireless channel110BC; mobile terminal108C is coupled to mobile terminals108A,10813,108D and108E by secondary wireless channels110AC,110BC,110CD and110CE, respectively; mobile terminal108D is coupled to mobile terminals108C and108E by secondary wireless channels110CD and110DE, respectively; mobile terminal108E is coupled to mobile terminals108C,108D and108F by secondary wireless channels110CE,110DE and110EF, respectively; and mobile terminal108F is coupled to mobile terminal108E by secondary wireless channel110EF.

It should be clearly understood that membership in the secondary network107is fluid in that mobile terminals may periodically “drop out” or “join” the secondary network107. To “drop out” of the secondary network107, the link or links coupling that mobile terminal to all other mobile terminals of the secondary network107must be severed, for example, by moving out-of-range, powering-down, switching to another channel or the like. Conversely, to “join” the secondary network107, a mobile terminal must establish a link with at least one mobile terminal of the secondary network107, for example, by moving into broadcast range, powering-up, switching to a channel on which the mobile terminals are broadcasting or the like. Importantly, however, a mobile terminal may be a member of the secondary network107without establishing a connection with any of the mobile terminals106A-C through which the primary network102may be accessed.

As will be more fully described below, the COSMOS system100and an associate method of distributing content, periodically referenced herein as “collaborative streaming”, enables mobile terminals that are members of the secondary network to receive a multimedia data stream in its entirety without the need to download the desired data stream in its entirety. To do so, mobile terminals that are within range of a base station pull content from a remotely located server accessible through the base station and distribute the pulled content to mobile terminals with which a secondary communication channel has been established.

Video Distribution

Terminology

In the description that follows, the foregoing notation is employed:N is a mobile terminal;N(u) is the set of all mobile terminals neighboring a mobile terminal N;d is a video description;S(u,d) is the set of all mobile terminals neighboring the mobile terminalN that are served a video description d by the mobile terminal N;W(u,d) is the set of neighbors of mobile terminal N that are not served the video description d by the mobile terminal N; andU(x) is a function that returns a number somewhere between 0 and x.

Video Distribution with Fixed Broadcast Scope

In one embodiment, the COSMOS system100employs a fixed broadcast scope protocol, in accordance with this protocol, after pulling a video description d from the content provider104, mobile terminal N distributes a data packet containing the pulled video description d to its peers, typically, the set of mobile terminals N(u) neighboring the mobile terminal N. Each mobile terminal forming part of N(u)1checks a Time-To-Live (TTL) field of the data packet received thereby, decrements the value of the TTL field by one and, if the value of the TTL is still greater than one, rebroadcasts the data packet containing the video description d to a next set of neighboring mobile terminals N(u)2. Rebroadcasting would continue in this manner by each set of mobile terminals N(u)xuntil the value of TTL is decremented to zero, at which time, no further rebroadcasting of the video description d is conducted.

Returning momentarily toFIG. 1, an example of the use of a fixed broadcast scope when streaming a video description will be briefly described. Assuming that the TTL value for all of the data packets pulled from the content provider104is one, mobile terminals108A,10813and108D pull different video descriptions from the content provider104. As S=1, each pulled video description is broadcasted one hop from the corresponding puller. In other words, the video description pulled down by the mobile terminal108A is rebroadcast to the mobile terminal108C; the video description pulled down by the mobile terminal108C is rebroadcast to the mobile terminals108A,10813,1081) and108E; and the video description pulled down by the mobile terminal108E is rebroadcast to the mobile terminals108C,108D and108F. Thus, while mobile terminals108A,108C and108E each paid for one video description, they received two, three and two descriptions, respectively. Furthermore, mobile terminals108B,108D and108F did not pay for any video descriptions but received one, two and one video description, respectively.

Video Distribution with Dynamic Broadcast Scope

The suitability of using a fixed broadcast scope for distribution of video descriptions in accordance with the techniques disclosed herein depends on the density of mobile terminals in the secondary network107. More specifically, when the density of mobile terminals is high, the use of a fixed broadcast scope results in the distribution of a large number of redundant video descriptions, thereby causing an unnecessary consumption of available channel bandwidth. Conversely, when the density of mobile terminals is low, the need for repeated pulls of video descriptions may result in increased streaming costs. It is contemplated, therefore, that a distributed broadcast algorithm having a dynamic broadcast scope would efficiently distribute video descriptions among peers having different mobile terminal densities without wasting the channel bandwidth.

Broadly speaking, the use of a dynamic broadcast scope for distribution of video descriptions involves limiting the extent to which a mobile terminal rebroadcast a video description to neighboring mobile terminals based upon the other video descriptions being provided to those mobile terminals. For example, in one application thereof a mobile terminal will not rebroadcast a video description if a number of neighboring mobile terminals are receiving that video description from a different mobile terminal. In order to determine whether to rebroadcast a video description, however, the mobile terminal must collect information from the neighboring mobile terminals.

Turning now toFIG. 2, beacon packet200containing information which enables a mobile terminal to determine whether to rebroadcast a video description to neighboring mobile terminals will now be described in greater detail. The beacon packet200includes a 32-bit header202, the first 16-bits of which are used to identify the mobile terminal originating the beacon packet200and the second 16-bits of which are unused/reserved for future use. The beacon packet200further includes N 32-bit data entries, each of which includes a first 16-bit field and a second 16-bit field, which collectively identify all of the video descriptions received by the mobile terminal and the originating location of each of the received video descriptions. More specifically, each data entry204-1through204-N includes a first field204-1athrough204-1Na that identifies a video description received by the mobile terminal and a second field204-1bthrough204-1Nb that identifies the neighboring mobile terminal which distributed the identified video description to the mobile terminal.

In accordance with the dynamic broadcast scope technique disclosed herein, each mobile terminal will intermittently transmit beacon packets to neighboring mobile terminals, typically, mobile terminals within one hop of the transmitting mobile terminal. The (<Received_Description_Index>, <Upstream_Node_ID>) pair contained in each data block204-1through204-N informs the receiving mobile terminal of the video descriptions that has been received by the neighboring transmitting mobile terminal. In this regard, it is noted that, as a mobile terminal has only one upstream node for a received video description, each entry in the beacon packet is unique.

Referring next toFIG. 2B, an example of the format of the data packet250used to transport a video description to neighboring mobile terminals will now be described in greater detail. As may now be seen, each data packet250includes a first, Puller_Node_ID, field252; a second, Upstream_Node_ID, field254; a third, Time_to_Live, field256; a fourth, Number_of_Neighbors, field258; a fifth. Description_Index, field260; a sixth, Switch, field262; a seventh, RPT, field264; an eighth, Sequence_Number, field266and the video description268. From the Description_Index and Upstream_Node_ID fields260and254, a mobile terminal which of its neighbors is broadcasting the data packet250. In the event that the mobile terminal receives the same video description from multiple neighbors, the ID of the neighboring mobile terminal having the earliest arrival time is placed in the Upstream_Node_ID field254.

It should be noted that the upstream node for a data packet such as the data packet250is either a source node that previously pulled the corresponding video description from the content provider104or an intermediate rebroadcasting node. If the node is the source node and has some neighbors, previously identified from the beacon packet200, the node determines whether or not to rebroadcast the received data packet in accordance with the following:

Presuming that it is the first time that non-pulling node u has received a data packet250containing the video description d. If more than a certain fraction of the nodes neighboring node u have already received the video description d from nodes other than node u, the non-pulling node u does not rebroadcast the received data packet250containing the video description d. For example, the non-pulling node u evaluates the percentage X of the potential beneficiaries that can be served by node u in accordance with Equation (1), below.
χ=|S(u,d)UW(u,d)|/|N(u)|  (1)
If the number χ of potential beneficiaries that can be served by the node u is less than threshold value XTh, then the node u does not rebroadcast the data packet. There are two extreme cases of the value XThthat need to be considered. More specifically, if XTh=0, the system will work similar to a COSMOS system with a fixed broadcast scope and wireless medium contention may occur if the network is too dense. On the other hand, if XTh=1, then only pullers broadcast descriptions and there are no rebroadcasts. As a result, the setting, of XThis a trade-off between wireless medium traffic and streaming costs. In this regard, it should be noted that, as their values continuously change due to network dynamics, N(u), S(u,d) and W(u,d) may all be moving ng averages.

To avoid collisions when rebroadcasting a video packet, a node will delay the rebroadcast for a period of time. To maximize the number of nodes benefited by any particular rebroadcast, nodes with larger χ's rebroadcast their video packets first. Accordingly, the rebroadcast delay TDfor a node is:
TD=U(ρ×(1−χ))  (2)
where ρ is the maximum rebroadcast delay in the system. Thusly, upon receiving a data packet, a node suppresses its rebroadcast: schedule of the received video description for delay period TD.

A maximum limit S on the broadcast: scope of a packet limits the source-to-peer (S2P) delay of the secondary network107. For fixed broadcast scope distributions of video descriptions. TTL is initially set to S and decremented by one for each hop. The nodes are then permitted to rebroadcast a video description only if TTL is greater than zero and χ≧XTh. For example, returning momentarily toFIG. 1, if S is set to 2 and XThis set to 0.5, the mobile terminals108A,108C and108E pull video descriptions dA, dCand dE, respectively. When a peer receives a video description, χ is evaluated to determine whether to the received video description should be rebroadcast. For example, the mobile terminal108C receives the video description dAin the first broadcast from puller A. From beacon messages, the mobile terminal108C determines that neighboring mobile terminals10813,108D and108E are not receiving the video description from any peer. Accordingly, χ=0.75 for the mobile terminal108C. As the value of χ (0.75) is greater than the value of XTh(0.5), the mobile terminal108C rebroadcasts the video description dA.

However, when the mobile terminal108D receives the video description dCfrom neighboring mobile terminal108C, it determines that the mobile terminal C is the puller and that mobile terminal108E is already receiving the video description dC from the mobile terminal198D. The mobile terminal1081) evaluates χ=0 and discards the rebroadcast operation to save wireless channel bandwidth. Thusly, the mobile terminals108A,108C and108E are pullers paying for one video description and enjoying three video descriptions while the mobile terminals108B,108D and108F are passive receives enjoying three, three and one video description, respectively.

Cost Sharing and Group Dynamics

As previously set forth, as mobile terminals randomly select video descriptions to pull from the content provider, it is entirely possible that two mobiles will pull and broadcast the same video description to each other. Although this type of redundancy reduces the likelihood of failure, any such advantages are outweighed by the increased streaming cost and reduced bandwidth that results. Accordingly, it would be beneficial for one of the mobile terminals to instead pull another description, thereby improving video quality and bandwidth utilization. As it is beneficial to more terminals, it is generally preferred that the mobile terminal with more neighboring mobile terminals broadcast the pulled video description. The value of the Number_of_Neighbors field258in the data packet250containing the video description to be broadcast by the respective terminals is used to resolve which pulling terminal should broadcast the video description. En the event of a tie, the pulling terminal with the largest value in the Puller_Node_ID field252will broadcast the video description. The peers without the full video descriptions would randomly choose any of its missing descriptions to pull. If the peer finds that all of the video descriptions are already available from neighboring terminals over the secondary broadcast channel, the terminal would become a passive receiver.

As the number of terminals in the secondary network107increases, some of the terminals may no longer need to pull any video descriptions and may instead become passive receivers that only receive video descriptions from other terminals. As this may result in unequal sharing of the cost of acquiring the video stream, the protocol employed in the secondary network107of the COSMOS system100has a mechanism which results in the pulling terminals and the passive terminals exchanging their roles when a pulling terminal has been downloading video data for some time.

A certain time TS seconds before a pulling terminal would like to stop pulling video descriptions, the pulling terminal sets the switch flag262. The pulling terminal then advising the other terminals of its intention to stop pulling by setting RPT (residual pull-time) to TS. The packet is broadcast within scope S. A passive terminal that receives the video packet with the switch flag262set starts a random timer with U(TS). If, by the expiration of U(TS), the passive terminal has not received the corresponding video description from the terminals neighboring the passive terminal, it becomes a puller of the video description by broadcast the description it pulls. In other words, the passive terminal with the earliest timer becomes the pulling terminal which replaces the formerly pulling terminal.

Before a pulling terminal leaves the secondary network107, it notifies neighboring terminals so that they can contend to pull the video description for sharing. The departing pulling terminal sets the switch flag262of the video packet250and sets RPT to 0. Upon receiving the data packet250, the neighboring terminals start a random timer of value U(Ĺ) where L is some constant. What results is similar to the role switching mechanism.

The COSMOS system100is robust to peer failure since some descriptions may be duplicated. If a pulling terminal fails, the same description can be supplied by other neighboring terminals. Neighboring terminals can buffer and order the video packets received according to their Description_Index and Sequence_Number fields260and266of the data packet. By doing so, duplicate packets can be identified and removed. If a peer finds that some of its video descriptions have been missing for a time, for example, as a result of a terminal failure, the terminal may begin pulling and sharing the video descriptions after a certain random timer L+U(Ĺ) where L and L are constants.

A simulation may be used to compare the relative performance of the COSMOS and CHUM networks. In this simulation, peers were randomly placed in a 100 unit by 100 unit area with each peer having a power range of 15 units. Peers enter the system at a Poisson arrival rate of λ requests/unit time Normalizing the time such that μ=1 request/unit time and presuming that a peer does not fail beforehand, each peer remains in the system for a mean time of 1/μ. A peer may fail with a rate of f/(μ+f). Therefore, at stead state, the average number of peers in the system is N=λ/(μ+f) and the probability that a peer will fail is f/(μ+f).

In the description that follows, the bandwidth is normalized such that a full stream of a video clip has a bandwidth of 1. For both the protocols employed in the COSMOS and CHUM network, an MDC of D descriptions with D≧1 was utilized so that each video description has a bandwidth less than that of the full stream. To account for MJDC coding inefficiency, each video description was considered to have a bandwidth (1+δ)/D, where δ is a bandwidth dilation factor. An event-driven simulation was implemented to study the system and all data was taken at steady state. Finally, pulling time and transmission time were assumed to be zero.

Metrics

A series of performance metrics enable the evaluation of the performance of both the COSMOS protocol with a fixed broadcast scope and the COSMOS protocol with a dynamic broadcast scope in distributing video descriptions to mobile terminals using a secondary broadcast channel. These performance metrics include (1) Receiving Channel Traffic; (2) Total Channel Traffic; (3) Delay; (4) Cost; (5) Cost Fairness; (6) Video Bitrate; and (7) Bitrate Fluctuation. As will be more fully described below, each of these performance metrics were evaluated for a node i where Tiis the system time for the node i, t is an instant in the lifetime of node i in the system and Nexis the number of nodes examined.

Receiving Channel Traffic

The term “Receiving Channel Traffic” (RCT) refers to the bandwidth required for a node to receive data for a node through the secondary broadcast channel and may be determined from the following relationship:
RCT=Σi∫TiVi(t)dt/ΣiTi
where Vi(t) is the bandwidth that node i receives at time t.

Total Channel Traffic

The term “Total Channel Traffic” (TCT) refers to the bandwidth required for the node and in may be determined from the following relationship:
TCT=Σi∫TiBi(t)dt/ΣiTi
where Bi(t) is the sum of bandwidth that node I broadcasts and receives at time t.

Delay

The term “Average Delay” (DAV) refers to the minimum number of broadcasts which must occur before a node receives a particular video description and may be determined from the following relationship:
Dav=Σi∫TiHi(t)dt/ΣiTi
where Hi(t) is the maximum delay of all of the video descriptions received by node i at time t.

The term “Average Cost” (CAV) refers to the streaming cost per unit time for all nodes and may be determined from the following relationship:
CAV=Σi∫TiPi(t)dt/ΣiTi
where Pi(t) is the total bandwidth of the video descriptions pulled by node i at time t.

Cost Fairness

The term “Cost Fairness” (CF) refers to the streaming cost per unit time for node i and may be determined from the following relationship:
CF=∫TiPi(t)dt/Ti
Jain's fairness index may be used to further define cost fairness in accordance with the following:
CF=(ΣiCi)2/NexΣiCi2

Video Bitrate

The term “Video Bitrate” (VB) refers to the effective video description bandwidth received per unit time for node i and may be determined from the following relationship:
VB=Σi∫TiPi(t)dt/ΣiTi
where Ri(t) is the effective description bandwidth that node i receives at time t.

Bitrate Fluctuation

The term “Bitrate Fluctuation” (BF) refers to the coefficient of variation σRi/μRifor node i and may be determined from the following relationship:
BF=Σi(σRi/μRi)/Nex

Experiments

Two cases, the first being D=1 and the second being D=2 shall be considered in the foregoing experiments. Further, unless otherwise stated, the baseline parameters for the foregoing experiments are as follows:

S=2; and

Referring next toFIG. 3, channel traffic as a function of the average number of peers for a secondary network, for example, the secondary network107, employing the COSMOS distributed broadcast protocol with both a fixed broadcast scope and a dynamic broadcast scope will now be described in greater detail. As may now be seen,FIG. 3confirms that, as the total number of nodes neighboring the distributing a video description increases, both the total and receiving traffic rises much more quickly when a fixed broadcast scope is employed in conjunction with the COSMOS protocol. A review ofFIG. 3further confirms that receiving and total traffic tend to increase at roughly the same rate and that the available bandwidth is consumed by broadcasting of received packets.

Importantly,FIG. 3clearly shows that the channel traffic for a secondary network employing the COSMOS distributed broadcast protocol with a fixed broadcast scope, an unnecessary number of broadcast operations are conducted when there are a large number of mobile terminals in close proximity to one another. As the density of the mobile terminals in the secondary network increases, an increasing number of the terminals will rebroadcast increasing numbers of duplicate video descriptions that were previously broadcast, thereby unnecessarily wasting considerable amounts of bandwidth and increasing the likelihood of contention between the mobile terminals. In contrast, when a dynamic broadcast scope is employed with the used in conjunction with the COSMOS distributed broadcast protocol, a mobile terminal is more likely to broadcast a video description when greater numbers of the neighboring mobile terminals are not served by other mobile terminals. As a result, many unnecessary rebroadcasts are avoided and more bandwidth remains available for other uses.

Referring next toFIG. 4, channel traffic as a function of broadcast threshold for a secondary network employing the COSMOS distributed broadcast protocol with dynamic broadcast scope will now be described in greater detail.FIG. 4establishes that channel traffic decreases as broadcast threshold increases. When the broadcast threshold is zero, the COSMOS distributed broadcast protocol with dynamic broadcast scope becomes increasingly similar to that: of a fixed broadcast scope. As before, channel traffic is high due to unnecessary rebroadcasts of video descriptions. In contrast, when the broadcast threshold is one, only pullers broadcast descriptions and there are no description rebroadcasts. As a result, the channel traffic is low.

In addition, we can deduce the bandwidth requirement of a peer from the figures. Let B W be the actual bandwidth of a video clip. Since the bandwidth of a full stream video clip is normalized to 1 in the simulation, the real bandwidth requirement of a peer equals to (Total Channel Traffic×BW). As the COSMOS scheme with a fixed broadcast scope has channel contention problems, we leave out the results of this scheme and consider the COSMOS scheme with dynamic broadcast scope for the following experiments.

FIG. 5compares the performance of COSMOS with CHUM in terms of delay as N increases. Clearly, COSMOS has a much lower delay. In COSMOS, the video packets are broadcasted within the scope S and hence delay is limited. For CHUM, the video data is forwarded until it reaches leaf nodes of the forwarding tree. Accordingly, COSMOS has a better delay performance than CHUM.

When the CHUM network is small, its average tree height and the average delay increases with N. Nevertheless, average delay drops slightly beyond a certain value. This is because when the area becomes very crowded, the average path length (in terms of number of hops) to puller would not increase any further or even reduce due to shortest path routing. As a result, the delay of CHUM decreases when we take average over all users.

Furthermore, the number of video descriptions D would affect the delay performance. This is because a node receives video descriptions from different pullers. The node may have different distances (in terms of number of hops) to the pullers. Since we consider the maximum delay of all descriptions received, more descriptions would lead to a higher resultant delay. As a result, the average delay increases with the number of video descriptions.

The average costs for COSMOS and CHUM are plotted inFIG. 6. As the inefficiency of MDC is significant for the cellular bandwidth pulled and affects the streaming cost, we also consider bandwidth dilation with a dilation factor δ 1-% for the schemes with the number of video descriptions D=2. In general, the average cost increases by about 10% when compared to the schemes without bandwidth dilation.

When the number of users increases, more peers collaborate to pull video data and the cost is shared among them. At any instant of time, there is one peer pulling each video description in a CHUM network and it does not have duplicate packets. In contrast, as COSMOS is a mesh approach to distributing multimedia data, some pullers may download replicate packets simultaneously. Consequently, the average cost of CHUM drops much faster than that of COSMOS as N increases.

FIG. 7shows the average cost of COSMOS against broadcast threshold XTH. The steaming cost increases with the broadcast threshold XTH. When XTH=1, only pullers broadcast video descriptions and there is no video description rebroadcast. Accordingly, it works similar to COSMOS with a broadcast scope S=1. More pullers are required and, as a result, higher stream costs are incurred. Conversely, for XTH=0, the system works like the COSMOS scheme with a fixed broadcast scope. Pullers broadcast descriptions which cover the nodes S=2 hops away from the pullers. Therefore, both the number of pullers and the streaming costs are reduced.

However, since only one peer pulls a video description in the CHUM network at the same time, the cost is distributed to only a few peers. Some peers may not have a chance to contribute and pull anything before leaving the system. As a result, the cost: charged to peers are inconsistent.FIG. 8shows a histogram which illustrates the cost distribution in the CHUM network. During the simulation period, the streaming cost is only distributed to a few peers. Most of the peers need to pay for a very low cost only, or do not even need to pay, while only a small proportion of peers pay for most of the streaming cost of the entire system. On the contrary, in the COSMOS system, many peers collaboratively pull video descriptions simultaneously. As a result, the streaming cost can be distributed among more peers, thereby attaining a greater degree of fairness. This result may be seen by reference to the histogram for cost distribution in the COSMOS network shown inFIG. 9.

Furthermore, with different average number of peers, we compare the fairness in cost sharing between CHUM and COSMOS. This is illustrated inFIG. 10. Jain's fairness index, which has a value between 0 and 1, is used as an indicator for cost fairness. The larger the fairness index is, the fairer the streaming cost is distributed. As the cellular streaming cost is more biased towards a few hosts, CHUM has a lower fairness when compared to COSMOS. Moreover, the fairness in cost sharing changes with the number of video descriptions. When there are more video descriptions in the system, more pullers are required to pull a full set of descriptions from the content provider. Therefore, more peers contribute to pulling different video descriptions and the streaming cost can be distributed to a larger number of users. As a result, the fairness in cost sharing increases with the number of video descriptions D.

Despite our protocol to reduce video description duplication in the network, certain unavoidable video description redundancies remain. This is, in fact, an advantage as it leads to higher failure tolerance. Furthermore, the use of MDC minimizes the stream disruption when peer fails. The neighbors of the failure peer would experience the loss of one video description instead of the entire video clip as in CHUM. Hence, the video bitrates of peers can be kept rather steady. In CHUM, one a peer fails, some downstream nodes may suffer discontinuity, a condition which adversely affects bitrate.

FIGS. 11,12,13and14plot four video bitrate profiles of peers in CHUM and COSMOS. The video bitrate obtained thereby is the effective bitrate received for video de+coding. The figures show that there are some bitrate drops which are due to peer departures and peer failures. A peer leaving causes a smaller gap while a peer failure results in a bigger gap. In general, CHUM peers have more bitrate drops during their system times. There is only one puller for each description. Due to a peer leave or failure, its downstream nodes cannot receive video data and they suffer some loss of video data. In contrast, for COSMOS systems, there are fewer bitrate drops because the video data delivery is based on mesh topology instead of tree topology as in CHUM. Video description duplication reduces the effect of peer leaves and failures. Even though other nodes sometimes cannot supply duplicate video descriptions, the peer experiences the loss of only one video description. Especially, COSMOS scheme with D=2 can bear the loss of a video description. This is because the loss does not affect the continuity of the video since a usable quality is maintained whenever any video description is correctly received. Hence MDC would provide better failure resilience to the system.

We show inFIG. 17the average bitrate received per node. Clearly, COSMOS achieves higher video bitrate than CHUM. This is because there is only one source (puller) for each video description, in a CHUM network, while COSMOS is a mesh network with multiple pullers. COSMOS peers may achieve duplicate video descriptions and this reduces the effect of peer leaves and failures. Hence, higher effective video bitrate can be achieved. For COSMOS system, as the bandwidth of each video description is defined as 1/D, the number of descriptions received equals (D×Video Bitrate). Furthermore, we show inFIG. 17the bitrate variation as failure rate f increases. CHUM suffers from a larger bitrate fluctuation. The bitrate for COSMOS is steadier due to inheritance redundancy and MDC.

According to various disclosed embodiments there is provided: a method for streaming data among terminals, comprising: pulling a portion of a data stream over a primary channel; determining which nearby terminals require said pulled portion of said data stream; and distributing, over a second channel, said pulled portion of said data stream to said neighboring terminal requiring said pulled portion of said data stream.

According to various disclosed embodiments there is provided: a method for streaming data among terminals, comprising: in multiple user terminals, at about the same time, pulling respective portions of a data stream through a primary wireless channel; and in ones of said user terminals, finding ones of said terminals which require said pulled portion of said data stream and are within a common peer-to-peer network; and distributing, over a second wireless channel, said pulled portion of said data stream to terminals which require it.

According to various disclosed embodiments there is provided: a system for streaming data, comprising: a content provider; a first terminal coupled to said content: provider over a first network; and at least: one neighboring terminal coupled to said first terminal over a second network, and therethrough to said content provider; said first terminal being configured to (a) intermittently pull portions of a data stream from said content: provider over said first network, and (b) broadcast said pulled portions of said data stream to said at least one neighboring terminal over said second network.

According to various disclosed embodiments there is provided: a wireless network, comprising: a content provider; a first sub-network of at least one mobile terminal; and a second sub-network of at least one mobile terminal; each mobile terminal of said first sub-network coupled to said content provider and at least one other mobile terminal of either said first sub-network or said second sub-network; each mobile terminal of said second sub-network coupled to at least one mobile terminal of said first sub-network; each mobile terminal of said first sub-network configured to randomly pull video descriptions from said content provider and distribute said pulled video descriptions to said at least one mobile terminal coupled thereto; and each mobile terminal of said second sub-network configured to receive video descriptions from said at least mobile terminal of said first sub-network coupled thereto.

Modifications and Variations

As will be recognized by those skilled in the art, the innovative concepts described in the present application can be modified and varied over a tremendous range of applications, and accordingly the scope of patented subject matter is not limited by any of the specific exemplary teachings given. The variations indicated above are just a few examples; following are some additional examples, but many others are possible.

For example, in the preferred embodiment, all of the nodes of the secondary network116are mobile devices, specifically, a combination of mobile telephones and PDAs, but alternately any other mobile device capable of receiving data over the secondary network116such as portable televisions (TVs), digital video device (DVD) players and notebook, laptop or tablet computers may be a node of the secondary network116. Further, while, in the preferred embodiment, all of the nodes of the secondary network116are mobile devices, alternately one or more of the nodes may be a device such as a desktop computer that is not designed for movement while in normal use.

Further, in the preferred embodiment, the content provider104is a media server coupled to the ISP base stations106A,106B and106C over the primary network102. Alternately, the content provider104may be a storage facility or any other type of device or system capable of delivering data to the ISP base stations106A,10613and106C in either a unilateral manner or upon receipt of a request therefor. Moreover, the content providers may be integrated into the ISP base stations106A,106B and106C themselves while the data transfers may be accomplished over either direct or indirect couplings between the devices.

Still further, the communications channel between the mobile terminals and the base stations was described as a “cellular” channel a term periodically associated by some with certain types of voice communication systems and/or protocols. However, it should be clearly understood the foregoing embodiment was provided, purely by way of example and it is fully contemplated, however, that a wide variety of other types of wireless communication techniques and/or protocols, including, but not limited to, satellite-based systems, voice over internet protocol (VOIP) systems, personal communication systems (PCS), global system for mobile communications (GSM), time division multiple access (TDMA) and/or code division multiple access (CDMA) may be used in its stead. If desired, the primary and secondary networks102and107may even employ wireline systems, for example, optical or plain-old-telephone (POT) systems. Likewise, the mere reference of the secondary channel as being either an IEEE 802.11 or a Bluetooth channel should not be interpreted as limiting the present disclosure to those particular channels. Instead, it is fully contemplated that the secondary channel may be any communication channel, preferably one that avoids interfering with the channel employed by the pulling terminals during the acquisition of data from the content provider.

Of course a wide variety of data security architectures can be used to protect copyright owners' rights in peer-to-peer networks. For example, the data being streamed may not be the original, image data, but instead may have been transformed so that a decryption process is required for comfortable viewing.