Hybrid Peer-to-Peer Streaming with Server Assistance

BACKGROUND

0001Streaming media technology enables real-time or on-demand access to audio, video and multimedia content via a network. Streaming over networks has become a reality with the development of efficient media compression methods, high throughput storage systems, and broadband networking technology. Attractive applications built on top of real-time media streaming service (e.g., entertainment video-on demand, digital library, and on-line news service) are also available. However, there are still many challenges towards building cost-effective, robust and scalable multimedia streaming systems.

0002Various system architectures are currently used to provide streaming media solutions. In a client-server system, distribution of content is managed centrally. The content files reside on a centrally organized server system and the client connects directly with the server to download a file. On the other hand, a Peer-to-Peer (P2P) network offers a decentralized network of peer computers. The peer computers form an overlay network and share resources such as content files, storage, processing capacity, and bandwidth. In comparison, Content Distribution Network (CDN) systems are mid-way between a client-server system and a P2P network. A CDN replicates the content from the place of origin to replica servers or proxies that are scattered over the network. A request from a client to a CDN is served from a replica server or proxy close to where the request originated rather than from a central server.

SUMMARY

0003Implementation of hybrid peer-to-peer streaming with server assistance is described. In one implementation, in a streaming session, a media source is selected from amongst a plurality of media sources for retrieval of streaming media content. The selection might be based, for example, on an amount of the streaming media content received at respective time units. In one scenario, if the amount received at a time unit is less than a target amount, the streaming media content is retrieved from at least one streaming media server. Conversely, if the amount received at a time unit is more than the target amount, the streaming media content is retrieved from at least one peer-to-peer network. In another embodiment, a playback buffer is monitored to determine an amount of streaming media content at the respective time units. The media source is then selected based on the amount of the streaming media content in the playback buffer.

0004This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.

BRIEF DESCRIPTION OF THE CONTENTS

0005The detailed description is described with reference to the accompanying figures. In the figures, the left-most digit of a reference number identifies the figure in which the reference number first appears. The use of the same reference numbers in different figures indicates similar or identical items.

0006<figref idref="DRAWINGS">FIG. 1</figref> illustrates an exemplary environment in which hybrid peer-to-peer streaming with server assistance may be implemented.

0007<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram illustrating an exemplary computing device for implementing hybrid streaming.

0008<figref idref="DRAWINGS">FIG. 3</figref> illustrates data flow in hybrid streaming in an exemplary implementation.

0009<figref idref="DRAWINGS">FIG. 4</figref> illustrates one exemplary approach to filling up a playback buffer with streaming media from different sources.

0010<figref idref="DRAWINGS">FIG. 5</figref> illustrates another exemplary approach to filling up a playback buffer with streaming media from different sources.

0011<figref idref="DRAWINGS">FIG. 6</figref> is a flow diagram illustrating an exemplary process for hybrid streaming.

0012<figref idref="DRAWINGS">FIG. 7</figref> is a flow diagram illustrating an exemplary process for filling up a playback buffer with streaming media from different sources, where the buffer is filled in the same temporal direction.

0013<figref idref="DRAWINGS">FIG. 8</figref> is a flow diagram illustrating another exemplary process for filling up of a playback buffer with streaming media from different sources, where the buffer is filled in different temporal directions.

0014<figref idref="DRAWINGS">FIG. 9</figref> shows a comparison between an optimal policy and a simulation of hybrid streaming according to one approach of filling up a playback buffer

0015<figref idref="DRAWINGS">FIG. 10</figref> shows a comparison between an optimal policy and a simulation of hybrid streaming according to another approach of filling up a playback buffer.

DETAILED DESCRIPTION

0016This disclosure is directed to techniques for streaming media over a network, such as the Internet. More particularly, the techniques involve a hybrid approach of retrieving media from more than one source—peer-to-peer, streaming media servers, web servers, etc.—depending upon various factors.

0017The source(s) from which media is retrieved during a streaming session are selected based on factors such as a status of a playback buffer from which the media is played back, compliance with an optimization policy, and so forth. The optimization policy may further be defined in various ways, such as maintaining a given Quality of Service (QoS) at minimum cost of service, minimizing an amount of streaming media content retrieved from a SM server at a given QoS, or the like. In an exemplary implementation, hybrid streaming may be realized by contacting and retrieving the media from one or more sources in order to comply with a given optimization policy or a desired status of the playback buffer.

0018Multiple and varied implementations and embodiments are described below. In the following section, an exemplary environment that is suitable for practicing various implementations is discussed. After this discussion, representative implementations of systems, devices, and processes for implementing the hybrid streaming techniques are described.

0019Exemplary Environment

0020<figref idref="DRAWINGS">FIG. 1</figref> shows an exemplary environment <b>100</b> that is suitable for implementing hybrid peer-to-peer streaming with server assistance. For discussion purposes, environment <b>100</b> includes at least one computing device <b>102</b> linked to one or more streaming media (SM) servers <b>104</b> and one or more Peer-to-Peer (P2P) networks <b>106</b> through a network <b>108</b>. The computing device <b>102</b> may further have access to one or more web servers, such as web server <b>110</b>, through the network <b>108</b>.

0021The computing device <b>102</b> may be implemented as any of a variety of conventional computing devices, including, for example, a server, a desktop PC, a notebook or portable computer, a workstation, a mainframe computer, a mobile computing device, an entertainment device, a game console, a set-top box, a DVD player, an Internet appliance, etc. that are configurable to receive streaming media content.

0022The network <b>108</b> may be a wireless or a wired network, or a combination thereof. The network <b>108</b> can be a collection of individual networks, interconnected with each other and functioning as a single large network (e.g., the Internet or an intranet). Examples of such individual networks include, but are not limited to, Local Area Networks (LANs), Wide Area Networks (WANs), and Metropolitan Area Networks (MANs). Further, the individual networks may be wireless or wired networks, or a combination thereof.

0023In one configuration, the computing device <b>102</b> includes a streaming control module <b>112</b> to implement hybrid streaming. The term “streaming” is used to indicate that data (streaming media content) is provided over the network <b>108</b> to the computing device <b>102</b> and that playback of the content can begin prior to the data being delivered in its entirety. The term “hybrid streaming” is used to indicate that the computing device <b>102</b> may receive various parts of a streaming file from one or more media sources, such as a SM server <b>104</b>, a P2P network <b>106</b>, and a web server <b>110</b>. The streaming control module <b>112</b> coordinates the hybrid streaming by selecting the one or more media sources from which streaming media content is to be retrieved.

0024In one implementation, during a streaming session, the computing device <b>102</b> receives streaming media content over the network <b>108</b> from one or more media sources such as a SM server <b>104</b>, a P2P network <b>106</b> and a web server <b>110</b>. The streaming session is divided into time units and the media source(s) from which the streaming media content (data) is retrieved at a time unit is selected by the streaming control module <b>112</b>. The streaming control module <b>112</b> may select one or more media source(s) for data retrieval at every time unit, at pre-decided time units, or at random time units. The time units may be measured in different ways, including in temporal fashion (i.e. every second of media) or as a specified number of frames (e.g., every frame or every N frames). The streaming control module <b>112</b> determines whether the streaming media content received at respective time units is less than a threshold or target amount. The determination may be made, for example, by monitoring an amount of data available for playback at a time unit. Based on this determination, the streaming control module <b>112</b> selects an appropriate source (e.g., SM server <b>104</b>, P2P network <b>106</b>, web server <b>110</b>) to retrieve the streaming media content for a respective time unit.

0025As a more specific example, the streaming control module <b>112</b> may make source decisions in an effort to ensure QoS while exploiting the resources of the P2P network. Thus, the streaming control module <b>112</b> may initially retrieve streaming data from the P2P network <b>106</b>. In the event that the throughput from the P2P network <b>106</b> is not sufficient for continuous playback, the streaming control module <b>112</b> retrieves data from the SM server <b>104</b>. The SM server <b>104</b> is capable of streaming at a fixed bit rate or a variable bit rate.

0026Further, the streaming control module <b>112</b> may select the media source(s) based on an optimization policy, such as maintaining a given Quality of Service (QoS) at minimum cost of service, minimizing an amount of streaming media content retrieved from a SM server at a given QoS, or other like policies. Exemplary working of the streaming control module <b>112</b> is described in detail with reference to <figref idref="DRAWINGS">FIG. 2</figref>.

0027<figref idref="DRAWINGS">FIG. 2</figref> illustrates various components of an exemplary computing device <b>102</b> suitable for implementing hybrid streaming in more detail. The computing device <b>102</b> can include, but is not limited to, a processor <b>202</b>, a memory <b>204</b>, Input/Output (I/O) devices <b>206</b> (e.g., keyboard and mouse), and a system bus <b>208</b> that operatively couples various components including processor <b>202</b> to memory <b>204</b>.

0028System bus <b>208</b> represents any of the several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, such architectures can include an Industry Standard Architecture (ISA) bus, a Micro Channel Architecture (MCA) bus, an Enhanced ISA (EISA) bus, a Video Electronics Standards Association (VESA) local bus, a Peripheral Component Interconnects (PCI) bus also known as a Mezzanine bus, a PCI Express bus, a Universal Serial Bus (USB), a Secure Digital (SD) bus, or an IEEE 1394 (i.e., FireWire) bus.

0029Memory <b>204</b> includes computer-readable media in the form of volatile memory, such as Random Access Memory (RAM) and/or non-volatile memory, such as Read Only Memory (ROM) or flash RAM. Memory <b>204</b> typically includes data and/or program modules for implementing hybrid streaming that are immediately accessible to and/or presently operated on by processor <b>202</b>. In one embodiment, the memory <b>204</b> includes a streaming control module <b>112</b>, a network interface <b>210</b>, a first buffer <b>212</b>, a second buffer <b>214</b>, a third or playback buffer <b>216</b>, and other applications <b>218</b>. The first and second buffers <b>212</b> and <b>214</b> store media (streaming media content) streamed from different sources <b>1</b> and <b>2</b>, respectively. In other implementations, the memory <b>204</b> may have additional buffers corresponding to additional media sources in the event that streaming media is received from more than two sources during a streaming session. Thus, the memory <b>204</b> may further have buffer <b>3</b>, buffer <b>4</b>, buffer <b>5</b>, and so on for corresponding media source <b>3</b>, media source <b>4</b>, media source <b>5</b>, and so forth. The third or playback buffer <b>216</b> stores the media in a form suitable for playback. For example, the media received from two or more media source(s) or buffers may be combined or merged and stored in the playback buffer <b>216</b> as a continuous block of data available for playback.

0030Though <figref idref="DRAWINGS">FIG. 2</figref> shows the streaming control module <b>112</b> as residing on the computing device <b>102</b>, it will be understood that the streaming control module <b>112</b> need not be hosted on the computing device <b>102</b>. For example, the streaming control module <b>112</b> could also be hosted on a storage medium communicatively coupled to the computing device <b>102</b>. This includes the possibility of the streaming control module <b>112</b> being hosted in whole, or in part, on the computing device <b>102</b>. Moreover, the media received during the streaming session may be played back on the computing device <b>102</b>, or on another device, such as a TV. In this manner, the streaming control module <b>112</b> may reside on the same device used to play back the media or on a separate device from the play back device.

0031The network interface <b>210</b> may enable the computing device <b>102</b> to send and receive commands and media content from the media sources linked to the network <b>108</b>. For example, the network interface <b>210</b> may be used by the computing device <b>102</b> to receive streaming media content from one or more of the SM server <b>104</b>, the P2P network <b>106</b> and the web server <b>110</b> over the network <b>108</b>.

0032In one implementation, during a streaming session divided into time units, the streaming control module <b>112</b> makes a decision at a time unit as to which media source(s) to contact and receive data from for the duration of at least that time unit. The decision may be based on an optimization policy, such as maintaining a given Quality of Service (QoS) at minimum cost of service or minimizing an amount of streaming media content retrieved from a SM server at a given QoS.

0033For example, to minimize the amount of streaming media content retrieved from the SM server <b>104</b> at a given QoS, the streaming control module <b>112</b> monitors an amount of streaming media content in the playback buffer <b>216</b>. If the amount of streaming media content in the playback buffer at a time unit is less than a target amount, the streaming control module retrieves data for the time unit from a SM server <b>104</b>. On the other hand, if the amount of streaming media content in the playback buffer at a time unit is more than the target amount, the streaming control module retrieves data for the time unit from a P2P network <b>106</b>. The target amount may be determined based on one or more of a playback rate from the playback buffer, or on the optimization policy, etc.

0034In one implementation, the playback buffer <b>216</b> may receive streaming media content directly from selected media source(s) such as a SM server <b>104</b>, a P2P network <b>106</b>, or a web server <b>110</b>. In another implementation, the playback buffer <b>216</b> may receive streaming media content from one or more of the first buffer <b>212</b> and the second buffer <b>214</b>, which in turn receive streaming media content from respective media sources, i.e., media source <b>1</b> and media source <b>2</b>. Media source <b>1</b> and media source <b>2</b> may be one or more of the SM server <b>104</b>, P2P network <b>106</b>, or web server <b>110</b>. The playback buffer <b>216</b> may further receive data from additional buffers corresponding to additional media sources such as media source <b>3</b>, media source <b>4</b>, and so forth.

0035Generally, program modules executed on the components of computing device <b>102</b> include routines, programs, objects, components, data structures, etc., for performing particular tasks or implementing particular abstract data types. These program modules and the like may be executed as a native code or may be downloaded and executed such as in a virtual machine or other just-in-time compilation execution environments. Typically, the functionality of the program modules may be combined or distributed as desired in various implementations.

0036An implementation of these modules and techniques may be stored on or transmitted across some form of computer-readable media. Computer-readable media can be any available media that can be accessed by a computer. By way of example, and not limitation, computer-readable media may comprise computer storage media that includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules, or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium, which can be used to store the desired information and which can be accessed by a computer.

0037Exemplary Data Flow in Hybrid Streaming

0038In one exemplary implementation of hybrid streaming, the streaming control module <b>112</b> selects one or more media source(s) from which to retrieve data during a streaming session. The data retrieved from the selected media source(s) may be directly received by the playback buffer <b>216</b> or by one or more of the first buffer <b>212</b>, the second buffer <b>214</b>, and so forth. Where intermediate buffers are used, the first buffer <b>212</b>, the second buffer <b>214</b>, and so forth in turn send the data to the playback buffer <b>216</b>.

0039<figref idref="DRAWINGS">FIG. 3</figref> illustrates an exemplary scenario in which the playback buffer <b>216</b> receives data from a first buffer <b>212</b> and a second buffer <b>214</b>. For illustration purposes, the first buffer <b>212</b> and the second buffer <b>214</b> are shown to receive data from at least one P2P network <b>106</b> and at least one SM server <b>104</b> respectively. It will be understood, however, that the first buffer <b>212</b> and the second buffer <b>214</b> may receive data from any of the SM server <b>104</b>, the P2P network <b>106</b>, or the web server <b>110</b>.

0040In one implementation, the streaming control module <b>112</b> coordinates flow of data from the first buffer <b>212</b> and the second buffer <b>214</b> to the playback buffer <b>216</b> in accordance with an optimization policy. As an example optimization policy, the streaming control module <b>112</b> may employ a tiered approach in which two threshold values, i.e. a lower bound and an upper bound, are employed in determining from which source to retrieve the media. The streaming control module <b>112</b> assigns a high priority to one of the first buffer <b>212</b> or the second buffer <b>214</b> at a time unit based on the amount of data in the playback buffer <b>216</b> at that time unit. In one scenario, when the amount of data in the playback buffer <b>216</b> is below the lower bound, both the first buffer <b>212</b> and the second buffer <b>214</b> send data to the playback buffer <b>216</b>. When the amount of data in the playback buffer <b>216</b> is between the lower bound and the upper bound, the high priority buffer sends data to the playback buffer <b>216</b>. Then, when the amount of data in the playback buffer <b>216</b> is above the upper bound, neither buffer sends data to the playback buffer <b>216</b>.

0041Further, the streaming control module <b>112</b> may also regulate throughputs of the first buffer <b>212</b> and the second buffer <b>214</b>, thereby regulating an amount of data retrieved from the selected media source(s). For example, when rate of consumption of data (playback) from the playback buffer <b>216</b> slows down, there is less empty space in the playback buffer <b>216</b>. Therefore, the rate of incoming data to the playback buffer <b>216</b> may be reduced by throttling back the throughputs of the first buffer <b>212</b> and the second buffer <b>214</b>. Additionally, when the throughputs of the first buffer <b>212</b> and the second buffer <b>214</b> are throttled, the rate of incoming data from the P2P network <b>106</b> and the SM server <b>104</b> may also be throttled. Thus, the streaming control module <b>112</b> may also regulate the throughputs of the P2P network <b>106</b> and the SM server <b>104</b> when streaming data to the computing device <b>102</b>.

0042In <figref idref="DRAWINGS">FIG. 3</figref>, the regulation of an amount of data in the playback buffer <b>216</b> and throughputs of the P2P network <b>106</b> and the SM server <b>104</b> have been described in the context of using intermediate buffers <b>212</b> and <b>214</b>. However, it will be understood that the amount of data in the playback buffer <b>216</b> and throughputs of the P2P network <b>106</b> and the SM server <b>104</b> can be regulated in a similar manner even in a case where the playback buffer <b>216</b> receives data directly from the P2P network <b>106</b> and the SM server <b>104</b> or from other selected media source(s), rather than via intermediate buffers <b>212</b> and <b>214</b>.

0043As noted above, the streaming control module <b>112</b> may make the decision as to which media source(s) to select and receive data from based on an optimization policy. As one example, suppose the optimization policy is denoted by A, which is the complete set of all decisions (actions) over the entire streaming session, such that A={a(k)|0≦k&lt;N}, where k is a time unit at which a decision a(k) is taken and N is a total number of time units in the entire streaming session (where each unit corresponds to a second, frame, etc.). For example, a scenario where the streaming control module <b>112</b> requests data from the SM server <b>104</b> may be represented as a(k)=1, while a(k)=0 may represent a scenario where the streaming control module <b>112</b> requests data from the P2P network <b>106</b>. In such a case, the total data requested from the SM server <b>104</b> may be computed as:

0000<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><mi>W</mi><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>N</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><mrow><mi>a</mi><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>r</mi><mi>w</mi></msub><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

0000where r_w(k) is throughput from the SM server <b>104</b>.

0044In an exemplary implementation of hybrid streaming, the streaming media content (data) may be received from either the P2P network <b>106</b> or the SM server <b>104</b> or both based on minimizing an amount of streaming media content retrieved from the SM server <b>104</b> at a given quality of service (QoS). In this exemplary implementation, an optimization policy A* corresponds to minimizing load on the SM server <b>104</b> during a streaming session while maintaining the given QoS. At the beginning of a time unit k(0≦k&lt;N), the streaming control module <b>112</b> takes a decision whether to contact and request data from the P2P network <b>106</b> or the SM server <b>104</b> or both. The streaming control module <b>112</b> may take this decision at every time unit or at pre-decided time units or at random time units during the streaming session.

0045In one case, the streaming control module <b>112</b> may retrieve data from the P2P network <b>106</b> alone and thus, there is no load on the SM server <b>104</b>. In such a case, throughput r_p(k) of the P2P network <b>106</b> might be less than a media bit rate r_mand result in the playback buffer <b>216</b> shrinking, or the throughput r_p(k) might be enough to sustain the given QoS.

0046Alternatively, the streaming control module <b>112</b> may retrieve data from either or both of the P2P network <b>106</b> and the SM server <b>104</b>. In this case, let throughput from the SM server <b>104</b> be denoted by r_w(k) and throughput from the P2P network <b>106</b> be denoted by r′_p(k). Total incoming throughput r_w(k)+r′_p(k) is capped by download link capacity r_cof the computing device and is enough to sustain the given QoS. Let a(k) denote the decision (action) that the streaming control module <b>112</b> takes at a time unit k. A scenario where the streaming control module <b>112</b> requests data from the SM server <b>104</b> may be represented as a(k)=1, while a scenario where the streaming control module <b>112</b> requests data from the P2P network <b>106</b> may be represented as a(k)=0. A status of the playback buffer at time k may be denoted as t_b(k). Then, the state transition or status of the playback buffer at time (k+1) can be summarized as:

0000<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>t</mi><mi>b</mi></msub><mo></mo><mrow><mo>(</mo><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mi /><mo></mo><mrow><mrow><mrow><msub><mi>t</mi><mi>b</mi></msub><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><mo>+</mo><mfrac><mrow><mrow><msub><mi>r</mi><mi>w</mi></msub><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><mo>+</mo><mrow><msubsup><mi>r</mi><mi>p</mi><mi>′</mi></msubsup><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow></mrow><msub><mi>r</mi><mi>m</mi></msub></mfrac><mo>-</mo><mn>1</mn></mrow><mo>,</mo></mrow></mrow></mtd><mtd><mrow><mrow><mi>a</mi><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><mo>=</mo><mn>1</mn></mrow></mtd></mtr><mtr><mtd><mrow><mi /><mo></mo><mrow><mrow><mrow><msub><mi>t</mi><mi>b</mi></msub><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><mo>+</mo><mfrac><mrow><msub><mi>r</mi><mi>p</mi></msub><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><msub><mi>r</mi><mi>m</mi></msub></mfrac><mo>-</mo><mn>1</mn></mrow><mo>,</mo></mrow></mrow></mtd><mtd><mrow><mrow><mi>a</mi><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><mo>=</mo><mn>0</mn></mrow></mtd></mtr></mtable></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

0047To comply with optimization policy A*, the total amount of data retrieved from the SM server <b>104</b>, computed as

0000<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mrow><mrow><mi>W</mi><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>N</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><mrow><mi>a</mi><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><mo></mo><mrow><msub><mi>r</mi><mi>w</mi></msub><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow></mrow></mrow></mrow><mo>,</mo></mrow></math></maths>

0000is to be minimized. Further, to maintain the given QoS, the playback buffer <b>216</b> may not be allowed to underflow, i.e. t_b(k)≧0 for all k's. Also, the playback buffer <b>216</b> may have an upper bound T_b, which confines t_b(k)≦T_bfor all k's. Therefore, the optimization policy A*={a*(k) 0≦k&lt;N} may be defined by:

0000<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><mi>min</mi><mo></mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo></mo><mi>W</mi></mrow><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>N</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><mrow><mi>a</mi><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><mo></mo><msub><mi>r</mi><mi>w</mi></msub></mrow></mrow></mrow><mo></mo><mstyle><mtext></mtext></mstyle><mo></mo><mrow><mrow><mi>such</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mi>that</mi><mo></mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo></mo><mn>0</mn></mrow><mo>≤</mo><mrow><msub><mi>t</mi><mi>b</mi></msub><mo></mo><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></mrow><mo>≤</mo><mrow><msub><mi>T</mi><mi>b</mi></msub><mo></mo><mrow><mo>(</mo><mrow><mn>0</mn><mo>≤</mo><mi>k</mi><mo>&lt;</mo><mi>N</mi></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>3</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

0048To comply with optimization policy A*, data is retrieved from either or both of the SM server <b>104</b> and the P2P network <b>106</b>. There are multiple ways to fill the playback buffer according to the optimization policy. Two possible scenarios are described below with reference to <figref idref="DRAWINGS">FIGS. 4 and 5</figref>.

0049<figref idref="DRAWINGS">FIG. 4</figref> illustrates a first scenario <b>400</b> to filling up the playback buffer <b>216</b> with streaming media from different sources according to an optimization policy. In this scenario, the buffer is filled in the same temporal direction in a streaming session. As shown in <figref idref="DRAWINGS">FIG. 4</figref>, the streaming session may be divided into multiple time units (periods) T_p. During a period if throughput from P2P network is not sufficient to sustain a threshold (target) amount of data t_din the playback buffer <b>216</b>, the streaming control module <b>112</b> streams a continuous fraction of data directly from the SM server <b>104</b> and then acquires the rest of the data from the P2P network <b>106</b>. Given the period length T_p, a minimum amount of content to be streamed from the SM server <b>104</b>, denoted by t_w, may be computed, as described below.

0050At the beginning of a period, the playback buffer <b>216</b> may already have t_dworth of content (in terms of media time). As shown in <figref idref="DRAWINGS">FIG. 4</figref>, the period may be divided into three stages at times t=t_dand t=t_d+t_wand t=T_p. Also, the third stage (t_d+t_w)≦t&lt;T_pmay be further sub-divided into three periods denoted by t_I, t_IIand t_III. Data may be retrieved during the durations t_I, t_IIand t_IIIwith or without any parallel processing such as playing back data from other parts of the playback buffer <b>216</b> or receiving data in other portions of the playback buffer <b>216</b>.

0051In the first stage (0≦t&lt;t_d), the computing device <b>102</b> consumes data from the playback buffer <b>216</b> and requests data from the P2P network in the meanwhile. An amount of data t_Iobtained from the P2P network <b>106</b> in this stage may therefore be computed to be:

0000<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>t</mi><mi>I</mi></msub><mo>=</mo><mrow><msub><mi>t</mi><mi>d</mi></msub><mo></mo><mfrac><msub><mi>r</mi><mi>p</mi></msub><msub><mi>r</mi><mi>m</mi></msub></mfrac></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>4</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

0000where r_pdenotes throughput from the P2P network and r_mdenotes media bit rate.

0052During the second stage (t_d≦t≦t_d+t_w) the streaming control module <b>112</b> streams and plays back data directly from the SM server <b>104</b>. In case residual bandwidth is available, the streaming control module <b>112</b> also acquires data from the P2P network <b>106</b>. The throughput of the P2P network <b>106</b> would then be capped by the link capacity (r_c) and would change to r′_p, where r′_p=min(r_c−r_m,r_p). The data retrieved from the P2P network <b>106</b> in this stage, t_II, may therefore be computed as shown below:

0000<maths id="MATH-US-00006" num="00006"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>t</mi><mi>II</mi></msub><mo>=</mo><mrow><msub><mi>t</mi><mi>w</mi></msub><mo></mo><mfrac><msubsup><mi>r</mi><mi>p</mi><mi>′</mi></msubsup><msub><mi>r</mi><mi>m</mi></msub></mfrac></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>5</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

0053The third stage begins at t=t_d+t_w, when the streaming control module <b>112</b> stops streaming from the SM server <b>104</b> and starts playing out buffered data. The playback buffer <b>216</b> would have data sufficient for playback for duration equal to t_I+t_IIat the beginning of this stage. The streaming control module <b>112</b> continues to acquire data from the P2P network <b>106</b> while consuming data from the playback buffer <b>216</b>. An additional time in the third stage for which the streaming control module <b>112</b> would continue to acquire data from the P2P network <b>106</b> is denoted by t_III. The throughput from the P2P network <b>106</b> would resume to r_p, as streaming from the SM server <b>104</b> would have stopped. The third period t_IIIof the third stage may therefore be computed by:

0000<maths id="MATH-US-00007" num="00007"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><mrow><mo>(</mo><mrow><msub><mi>t</mi><mi>I</mi></msub><mo>+</mo><msub><mi>t</mi><mi>II</mi></msub><mo>+</mo><msub><mi>t</mi><mi>III</mi></msub></mrow><mo>)</mo></mrow><mo></mo><mfrac><msub><mi>r</mi><mi>p</mi></msub><msub><mi>r</mi><mi>m</mi></msub></mfrac></mrow><mo>-</mo><msub><mi>t</mi><mi>III</mi></msub></mrow><mo>≥</mo><msubsup><mi>t</mi><mi>d</mi><mi>′</mi></msubsup></mrow></mtd><mtd><mrow><mo>(</mo><mn>6</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

0000Further, as shown in <figref idref="DRAWINGS">FIG. 3</figref>, the time period T_pmay be given by:

0000<br /><i>t</i>_d<i>+t</i>_w<i>+t</i>_I<i>+t</i>_II<i>=t</i>_III<i>=T</i>_p  (7)

0000Solving Eq. (4)-(7), minimum amount of content to be streamed from the SM server <b>104</b>, or t_w, can be computed to be:

0000<br /><i>t</i>_w(<i>r</i>_m<i>−r</i>_p<i>+r</i>_p)≧<i>T</i>_p(<i>r</i>_m<i>−r</i>_p)+(<i>t</i>_d<i>−t</i>_d)<i>r</i>_m  (8)

0000Therefore, the minimum amount of streaming media content to be streamed from the SM server <b>104</b> (denoted by t_w) and a point in the streaming media content (t_d+t_w) at which the streaming control module <b>112</b> stops acquiring data from the SM server <b>104</b> and starts acquiring data from the P2P network <b>106</b> may be computed.

0054<figref idref="DRAWINGS">FIG. 5</figref> shows a second scenario <b>500</b> for complying with the optimization policy A* (i.e., minimizing the load on the SM server <b>104</b> during a streaming session while maintaining the given QoS). Here, data is retrieved from either or both of the SM server <b>104</b> and the P2P network <b>106</b>, but the data fills out the media stream held in the playback buffer <b>216</b> from opposite time directions. As shown in <figref idref="DRAWINGS">FIG. 5</figref>, the streaming session may be divided into multiple time units (periods) T_p. During a period, if throughput from P2P network is not enough to sustain a threshold (target) amount of data t_din the playback buffer, the streaming control module <b>112</b> streams a continuous fraction of data directly from the SM server <b>104</b> and acquires rest of the data from the P2P network <b>106</b>.

0055At the beginning of a period, the playback buffer <b>216</b> may already have td worth of content. So an amount of data that can be retrieved while playing through this buffer may be computed as:

0000<br /><i>T</i>_d<i>=t</i>_d(<i>r</i>_p<i>+r</i>_w)/<i>r</i>_m  (9)

0000where r_p, r_wand r_mare throughput of the P2P network <b>106</b>, throughput of the SM server <b>104</b>, and media bit rate. Let T′_pbe the smaller value between Td and the period length T_p, so that T′_pcan be represented as T′_p=min(T_d,T_p). The streaming control module <b>112</b> starts downloading simultaneously from the SM server <b>104</b> and the P2P network <b>106</b> in opposite directions from time position t_dand t_d+T′_p, respectively, as shown in <figref idref="DRAWINGS">FIG. 5</figref>. Since r_p+r_w>r_m, the data that is retrieved from the SM server <b>104</b> and the data that is retrieved from the P2P network <b>106</b> meets in time less than t_d. Then, the streaming control module <b>112</b> stops acquiring data from the SM server <b>104</b>. Further, if T′_p<T_p, the streaming control module <b>112</b> continues to request data from the P2P network <b>106</b> after time position t_d+T′_pin time sequential direction. After td, the streaming control module <b>112</b> consumes the new buffer built in this period, while continuing to request data from the P2P network <b>106</b>.

0056Though <figref idref="DRAWINGS">FIG. 4</figref> and <figref idref="DRAWINGS">FIG. 5</figref> have been described with reference to hybrid streaming from a P2P network and a SM server in accordance with an optimization policy A*, it will be understood that similar computations and methods may be used to implement hybrid streaming from any selection of media source(s) in compliance with any optimization policy Â.

0057There can be situations during streaming when there is no data in the playback buffer <b>216</b>. In such a scenario, the playback buffer <b>216</b> may be grown to a stage so that there is at least a threshold amount of data in the playback buffer <b>216</b>. Then, the data in the playback buffer <b>216</b> can sustain for a period of playback during which, the streaming control module <b>112</b> can retrieve further data. Such situations can occur at start-up, or when a user seeks to play from a new position, or if a new media file is pre-loaded before the end of an old one, or when a user starts a video file without following a playlist, etc.

0058In one implementation, to grow the data in the playback buffer <b>216</b> from no data to a threshold amount, an initial delay of reasonable time may be given during which the streaming control module <b>112</b> retrieves data from at least one of the media sources. The media source(s) may be selected by the streaming control module <b>112</b> based on throughputs of the media sources and on the optimization policy. In an exemplary implementation of hybrid streaming, the media source(s) may be selected from either the P2P network <b>110</b> or the SM server <b>104</b> or both based on minimizing an amount of streaming media content retrieved from the SM server <b>104</b> at a given quality of service (QoS). In such a case, as an initial delay is acceptable, data retrieval from the P2P network <b>106</b> may be given a greater priority. Thus, if the throughput of the P2P network <b>106</b> is sufficient to grow the playback buffer <b>216</b>, the streaming control module <b>112</b> may retrieve data only from the P2P network <b>106</b>. On the other hand, if the throughput of the P2P network <b>106</b> is not sufficient to grow the playback buffer <b>216</b>, the streaming control module <b>112</b> may retrieve data from at least the SM server <b>104</b>, with or without simultaneous data retrieval from the P2P network <b>106</b>. Further, if the streaming control module <b>112</b> retrieves data from both the SM server <b>104</b> and the P2P network <b>106</b>, the retrieval may be in a same time direction as explained earlier with reference to <figref idref="DRAWINGS">FIG. 4</figref>, or in different time directions as explained earlier with reference to <figref idref="DRAWINGS">FIG. 5</figref>.

0059In another implementation, to grow the data in the playback buffer <b>216</b> from no data to a threshold amount, it may not be desirable to have an initial delay. In such a case, data retrieval from the SM server <b>104</b> may be given a greater priority. The streaming control module <b>112</b> may retrieve data simultaneously from the P2P network <b>106</b> also based on residual bandwidth available. Further, if the streaming control module <b>112</b> retrieves data from both the SM server <b>104</b> and the P2P network <b>106</b>, the retrieval may be in a same time direction as explained earlier with reference to <figref idref="DRAWINGS">FIG. 4</figref>, or in different time directions as explained earlier with reference to <figref idref="DRAWINGS">FIG. 5</figref>.

0060Exemplary Processes

0061<figref idref="DRAWINGS">FIG. 6</figref> illustrates an exemplary process <b>600</b> for implementing hybrid streaming. The process <b>600</b> (as well as other processes described below) is illustrated as a collection of blocks in a logical flow graph, which represents a sequence of operations that can be implemented in hardware, software, or a combination thereof. In the context of software, the blocks represent computer instructions that, when executed by one or more processors, perform the recited operations. For discussion purposes, the process <b>600</b> (as well as other processes described below) is described with reference to environment <b>100</b> shown in <figref idref="DRAWINGS">FIG. 1</figref> and computing device <b>102</b> shown in <figref idref="DRAWINGS">FIG. 2</figref>. In an exemplary implementation of process <b>600</b> (as well as other processes described below), the hybrid streaming is implemented to conform to an optimization policy A* that corresponds to minimizing load on the SM server <b>104</b> during a streaming session while maintaining a given QoS. It will be apparent to a person ordinarily skilled in the art that environment <b>100</b>, computing device <b>102</b> and optimization policy A* are described for exemplary purposes and the process <b>600</b> (as well as other processes described below) may be implemented in other environments, systems or network architectures to comply with other optimization policies.

0062The process <b>600</b> monitors a status of the playback buffer <b>216</b> and selects one or more media source(s) from which to retrieve data during a streaming session. The streaming session is preferably divided into many time units. At block <b>602</b>, the streaming control module <b>112</b> determines whether an amount of data in the playback buffer <b>216</b> is less than a threshold amount. The threshold amount may be determined based, for example, on a playback rate from the playback buffer, an optimization policy, or other factors. The optimization policy may be defined in various ways, such as maintaining a given Quality of Service (QoS) at minimum cost of service, or minimizing an amount of streaming media content retrieved from a SM server at a given QoS, or so forth.

0063If the amount of data in the playback buffer <b>216</b> is determined to be less than the threshold amount (i.e. the “yes” branch from block <b>602</b>), data is retrieved from the SM server <b>104</b> for at least one time unit (block <b>604</b>). Additionally, data may also be retrieved simultaneously from the P2P network <b>106</b> if residual bandwidth is available. Alternatively, if the amount of data in the playback buffer <b>216</b> is determined to be more than the threshold amount (i.e. the “no” branch from block <b>602</b>), data for at least the time unit is retrieved from at least one P2P network <b>106</b> (block <b>606</b>).

0064In cases where the streaming control module <b>112</b> retrieves data simultaneously from both the SM server <b>104</b> and the P2P network <b>106</b>, the streaming control module <b>112</b> may retrieve the data and fill the playback buffer <b>216</b> with data arranged in the same time direction or in opposite time directions. A scenario in which data is retrieved in a same time direction is described below with reference to <figref idref="DRAWINGS">FIG. 7</figref>. Another scenario in which data is retrieved in opposite time directions is described later with reference to <figref idref="DRAWINGS">FIG. 8</figref>.

0065At block <b>608</b>, the retrieved data is received in the playback buffer <b>216</b>. At block <b>610</b>, data in the playback buffer <b>216</b> is played back. While the data is played back from the playback buffer <b>216</b>, data is also simultaneously received in the playback buffer from at least one of the SM server <b>104</b> and the P2P network <b>106</b>. To select which media source(s) to retrieve data from, actions illustrated as blocks <b>602</b> to <b>608</b> are repeated. The operation may be repeated at every time unit, at pre-decided time units, or at random time units.

0066<figref idref="DRAWINGS">FIG. 7</figref> illustrates a process <b>700</b> for retrieving data from one or more of the SM server <b>104</b> and the P2P network <b>106</b> and filling the playback buffer <b>216</b> in a same time direction. For discussion purposes, this process <b>700</b> will be described with additional reference to elements of <figref idref="DRAWINGS">FIG. 4</figref>. At block <b>702</b>, the streaming control module <b>112</b> determines whether an amount of data in the playback buffer <b>216</b> is less than a threshold amount t_d. The threshold amount t_dmay be determined based on a playback rate from the playback buffer, an optimization policy, and/or other factors or considerations. The optimization policy may be defined in various ways. Possible policies might be maintaining a given Quality of Service (QoS) at minimum cost of service or minimizing an amount of streaming media content retrieved from a SM server at a given QoS.

0067If the amount of data in the playback buffer <b>216</b> is more than the threshold amount (i.e. the “no” branch from block <b>702</b>), data is retrieved from at least one P2P network <b>106</b> for at least one time unit (block <b>704</b>). Alternatively, if the amount of data is less than the threshold amount (i.e. the “yes” branch from block <b>702</b>), a computation is made to determine an amount of data, in terms of media time and denoted t_w, to be retrieved from the SM server <b>104</b> (block <b>704</b>). One exemplary computation to find the amount of data t_wcan be made using equation (8) above, as explained earlier with reference to <figref idref="DRAWINGS">FIG. 4</figref>.

0068At block <b>708</b>, retrieval of data t_wfrom the SM server <b>104</b> is started. At block <b>710</b>, the streaming control module <b>112</b> determines whether residual bandwidth is available. At block <b>712</b>, if residual bandwidth is not available (i.e. the “no” branch from block <b>710</b>), retrieval of data t_wfrom the SM server <b>104</b> continues until finished. Alternatively, at block <b>714</b>, assuming residual bandwidth is available (i.e. the “yes” branch from block <b>710</b>), data is retrieved simultaneously from the P2P network <b>106</b> while retrieval of data t_wfrom the SM server <b>104</b> is finished. The data retrieval from the P2P network <b>106</b> at block <b>714</b> is started from a point (t_d+t_w) in the streaming media content. At block <b>716</b>, data reverts to being retrieved from the P2P network <b>106</b>.

0069At block <b>718</b>, the retrieved data is received in the playback buffer <b>216</b>. At block <b>720</b>, data in the playback buffer <b>216</b> is played back. While the data is played back from the playback buffer <b>216</b>, data is also simultaneously received in the playback buffer from at least one of the SM server <b>104</b> and the P2P network <b>106</b>. To select which media source(s) to retrieve data from, actions illustrated as blocks <b>702</b> to <b>718</b> are repeated. The operation may be repeated at every time unit, at pre-decided time units, or at random time units.

0070<figref idref="DRAWINGS">FIG. 8</figref> illustrates a process <b>800</b> for retrieving data from one or more of the SM server <b>104</b> and the P2P network <b>106</b> and filling the playback buffer <b>216</b> from different time direction. For discussion purposes, this process <b>800</b> will be described with additional reference to elements of <figref idref="DRAWINGS">FIG. 5</figref>. At block <b>802</b>, the streaming control module <b>112</b> determines whether an amount of data in the playback buffer <b>216</b> is less than a threshold amount t_d. If the amount of data in the playback buffer <b>216</b> is determined to be more than the threshold amount (i.e. the “no” branch from block <b>802</b>), data is retrieved from at least one P2P network <b>106</b> for at least one time unit (block <b>804</b>). Alternatively, if the amount of data in the playback buffer <b>216</b> is determined to be less than the threshold amount (i.e. the “yes” branch from block <b>802</b>), data is retrieved simultaneously from the SM server <b>104</b> and the P2P network <b>106</b> and used to fill the playback buffer in opposite time directions. For example, with reference to <figref idref="DRAWINGS">FIG. 5</figref>, data is retrieved from the SM server <b>104</b> in forward direction from a point t_din the streaming media content, and from the P2P network <b>106</b> in backward direction from end of the time unit. In this case, the amount of data t_wretrieved from the SM server may not be pre-computed. Instead, retrieval from the SM server is stopped when data from the two retrievals (i.e. from the SM server <b>104</b> and the P2P network <b>106</b>) meet.

0071At block <b>810</b>, the retrieved data is received in the playback buffer <b>216</b>. At block <b>812</b>, data in the playback buffer <b>216</b> is played back. While the data is played back from the playback buffer <b>216</b>, data is also simultaneously received in the playback buffer from at least one of the SM server <b>104</b> and the P2P network <b>106</b>. To select which media source(s) to retrieve data from, the actions illustrated as blocks <b>802</b> to <b>810</b> are repeated. The operation may be repeated at every time unit, at pre-decided time units, or at random time units.

0072Exemplary Simulation Results

0073<figref idref="DRAWINGS">FIG. 9</figref> shows a performance comparison between a simulation for process described in <figref idref="DRAWINGS">FIG. 7</figref> and an optimal policy A* under various choices of period length T_p. Every point is an average of 10 samples. In the simulation, the media bit rate is set to 1 Mbps and incoming link capacity is set to 1.5 Mbps. Throughput of the P2P network <b>106</b> is set to vary between 250 Kbps and the link capacity. After each variation, the P2P network <b>106</b> stays constant for an amount of time. The amount of time follows an exponential distribution with a mean value of 10 seconds. Maximum playback buffer is set to 300 seconds.

0074<figref idref="DRAWINGS">FIG. 10</figref> shows a performance comparison between a simulation for process described in <figref idref="DRAWINGS">FIG. 8</figref> and an optimal policy A* under various choices of period length T_punder similar conditions as used for the simulation results shown in <figref idref="DRAWINGS">FIG. 9</figref>.

CONCLUSION

0075Although the invention has been described in language specific to structural features and/or methodological acts, it is to be understood that the invention defined in the appended claims is not necessarily limited to the specific features or acts described. Rather, the specific features and acts are disclosed as exemplary forms of implementing the claimed invention.