RELATED APPUCATION

Benefit is claimed to Indian Provisional Application No. 1201/CHE/2012 titled "METHOD AND SYSTEM FOR DISTRIBUTED VIDEO STREAMING OF VIDEO IN A PEER-TO-PEER VIDEO SHARING ENVIRONMENT" by QuiKast Technologies Pvt. Ltd. filed on 28th March 2012, which is herein incorporated in its entirety by reference for all purposes.

FIELD OF THE INVENTION

The present invention relates to the field of media streaming systems, and more particularly relates to streaming of a media file in a distributed media streaming environment

BACKGROUND OF THE INVENTION

Improvements in computing technologies have changed the way people interact with one another as well as how people share information with one another. Such improvements include the introduction of peer-to-peer based file sharing protocols.
PdaMo-peer file sharing technologies are being rapidly adopted to distribute digital information. Peer-to-peer technology improved overall system reliability by allowing one or more peer computers to serve as a source of digital information (e.g., multi-media content) requested by another peer computer. Thus, the risk of not being able to obtain digital information due to a server being not operational (either due to the server itself, or one or more network connections) is mitigated.
A BitTorrent file distribution system is an example of peer-to-peer file sharing system. The BitTorrent file distribution system enables distribution of digital content (e.g., video file) by dividing the video file into number of pieces and allowing the pieces to be shared between peer computers in the peer-to-peer sharing network. However, the drawback of such a peer-to-peer file sharing system (e.g., BitTorrent) is that for most video container formats, the user of the recipient peer computer needs to wait till the entire video file gets downloaded on the recipient peer computer for watching the video file, thereby causing inconvenience to the user.

BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS

Figure 1A is a block diagram of a distributed media streaming system, according to one embodiment.

Figure 1B is a block diagram of a distributed media streaming system, according to another embodiment.

Figure 2 is a process flowchart illustrating an exemplary method of streaming of a media file to a recipient device in a distributed media streaming environment, according to one embodiment.

Figure 3 is a process flowchart illustrating an exemplary method of streaming of a media file to a recipient device in a distributed media streaming environment, according to another embodiment.

Figure 4 is a schematic representation depicting balancing of load across multiple donor devices while streaming a video file to a recipient device.

Figure 5 is a block diagram of a donor device, such as those shown in Figure 1, showing various components for implementing embodiments of the present subject matter.

Figure 6 is a block diagram of a recipient device, such as those shown in Figure 1, showing various components for implementing embodiments of the present subject matter.

The drawings described herein are for illustration purposes only and are not intended to limit the scope of the present disclosure in any way.

DETAILED DESCRIPTION OF THE INVENTION

The present invention provides a method and system for streaming of a media file in a distributed media streaming environment, in the following detailed description of the embodiments of the invention, reference is made to the accompanying drawings that form a part hereof, and in which are shown, by way of illustration, specific embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention, and it is to be understood that other embodiments may be utilized and that changes may be made without departing from the scope of the present invention. The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims.

Throughout the document, the term 'media' refers to 'video' and/or 'audio'.
Figure 1A is a block diagram of a distributed media streaming system 100, according to one embodiment. In Figure 1A, the. distributed media streaming system 100 includes a plurality of donor devices 102A-N, a file lookup server 104, and a recipient device 106 connected to each other via a network 108.
Consider that, the user of the recipient device 106 wishes to watch a particular media file (e.g., media file A) available with one or more of the donor devices 102A-N. in such case, the recipient device 106 sends a request for providing a list of donor devices capable of streaming the media file to the file lookup server 104 via the network 108. in some embodiments, the recipient device 106 sends a unique file signature (UFS) of the media file A in the request. The UFS is a piece of data that uniquely identifies a media file. The file lookup server 104, upon receiving request, identifies one or more of the donor devices 102A-N (say donor devices 102A-C) in which the media file A is available for sharing with the recipient device 106 based on the unique file signature. In some embodiments, the file lookup server 104 maintains a list of media files available with the donor devices 102A-N. In these embodiments, the file lookup server 104 determines whether the requested media file A is present in the list of media files available with the donor devices 102A-N. Accordingly, the file lookup server 104 sends a list of donor devices capable of streaming the media file A.

The recipient device 106 selects donor devices 102A-C from the received list and sends a request for streaming the media file A to each of the donor devices 102A-C. Accordingly, each of the donor devices 102A-C streams one or more fragments of the media file A to the recipient device 106. The number of fragments streamed by each of the donor devices 102A-C based on link parameters associated with respective communication link between the donor devices 102A-C and the recipient device 104 as will discussed in Figures 2 and 3.

Figure 1B is a block diagram of a distributed media streaming system 150, according to another embodiment The system 160 of Figure 1B is similar to the system 100 of Figure 1A, except the system 150 does not include a media-file look up server 104. In the system 150, the recipient device 106 sends a request for provide capability to stream the media file A to the donor devices 102A-N. In some embodiments, the recipient device 106 sends a unique file signature of the media file A in the request. Based on the request, each of the donor devices 102A-N confirms presence of the media file A based on the unique file signature and sends a response indicating whether it is capable of streaming the media fife A or not. Accordingly, the recipient device 106 identifies multiple donor devices 102A-C from the donor devices 102A-N based on the response and sends a request for streaming the media file A to each of the donor devices 102A-C. Accordingly, each of the donor devices 102A-C streams one or more fragments of the media file A to the recipient device 106. The number of fragments streamed by each of the donor devices 102A-C based on link parameters associated with respective communication link between the donor devices 102A-C and the recipient device 104 as will discussed in Figures 2 and 3.

Figure 2 is a process flowchart 200 illustrating an exemplary method of downloading a desired media file from multiple donor devices 102A-C, according to one embodiment At step 202, multiple donor devices capable of streaming a desired media file in a distributed manner are determined. As described above, the multiple donor devices 102A-C are determined by contacting the file lookup server 104. Alternatively, the multiple donor devices 102A-C are determined by contacting the plurality of donor devices 102A-N. At step 204, bandwidth and latency associated with a communication link with each of the donor devices 102A-C is calculated.

At step 206, a weight value is computed and assigned to each donor device based on the calculated bandwidth and latency on the respective communication link. For example, the weight value (W) for each donor device is computed as follows:

W = P/latency + Q*bandwidth, where, P and Q are application-specific coefficients. It can be noted that coefficients P and Q can vary and are adjusted dynamically to suit playback requirements in real time. For example, while buffering a media, the higher values of P can be chosen to put more weight on donor devices with lower latency. On the other hand, during regular playback with sufficient buffer levels, the weight of donor devices with higher bandwidth can be made higher by choosing higher values of Q.

At step 208, order of the donor devices 102A-C to serve fragments of the media file is determined based on the weight values using a weighted round-robin arbitration algorithm. For example, in the beginning, a donor device (e.g., the donor device 102A) having the highest weight value is identified from the donor devices 102A-C for streaming one or more fragments of the requested media file. At step 210, a request for streaming the one or more fragments is sent to the donor devices 102A-C according to the determined order. Accordingly, the donor devices 102A-C encode and stream the requested fragments) to the recipient device 106. At step 212, the one or more fragments are received and consequently played In order at the recipient device 106. At step 214, it is determined whether there are any fragments of the media file remaining to be streamed, if there are any fragments of the media file remaining to be streamed, then the process repeats the steps 204 to 214, else the process is terminated. It may so happen that, the donor device 102B may have highest weight value compared to the donor devices 102A and 102C. In such case, the donor device 102B is selected as a donor device for streaming one or more of the remaining fragments of the media file, at step 208.

Figure 3 is a process flowchart 300 illustrating an exemplary method of streaming of media file to the recipient device 106 in a distributed media streaming environment, according to one embodiment At step 302, a request for streaming a media file is received from the recipient device 106. For example, the request includes a unique file signature (UFS) of the desired media file, bandwidth and latency of respective communication link with the recipient device 106 and so on.
At step 304, the requested media file is fragmented into a plurality of fragments based on the request. At step 306, a weight value associated with each of the donor devices 1G2A-C is computed based on bandwidth and latency associated with a respective communication link with the recipient device 106. For example, the weight value (W) is computed using the following equation:

W = P/latency + Q*bandwidth, where, P and Q are coefficients. It can be noted that coefficients P and Q can vary and are adjusted dynamically to suit playback requirements in real time.

At step 308, the numbers of the fragments, which are to be streamed by each of the donor devices 102A-C, are determined based on the weight value [W] associated with each of the donor devices 102A-C. At step 310, order in which the fragments are to be streamed to the recipient device 106 by each of the donor devices 102A-C is negotiated among the donor devices 102A-C. In one exemplary implementation, the order in which the fragments are to be streamed is based on the fragment number. So, based on the fragment number, each of the donor devices 102A-C decides order in which one or more fragments are to be streamed. At step 312, the fragments associated with the requested media file are streamed in an agreed-upon order by the donor devices 102A-C so that the requested media file is played in continuous and smooth manner at the recipient device 106. In this manner, the desired media file is streamed to the recipient device 106 by the donor devices 102A-C without the need to download the media file at the recipient device 106. In other words, the desired media file is provided to the recipient device 106 by the donor devices 102A-C using distributed streaming technique.

Figure 4 is a schematic representation 400 depicting balancing of load across multiple donor devices while streaming a video file to the recipient device 106. In Figure 4, consider that P1, P2, and P3 are the donor devices 102A-C and P4 is the recipient device 106. P1, P2 and P3 have the video file of 60 seconds' duration and P4 wishes to watch the same video over the Internet The device P4 forwards the request for video file to the devices P1, P2, and P3 since the devices P1, P2 and P3 have the video file requested by the device P4.

Accordingly, each of devices P1, P2, and P3 fragments the video file into six fragments (f1, f2, f3, f4, f5, and f6) of 10 second duration and streams the fragments to the device P4 !n an order which is agreed upon among the devices P1, P2, and P3 based on different parameters like bandwidth, load and the video file characteristics.

Consider that, the device P1 has strong uplink, the device P2 has medium uplink and the device P3 has weak uplink. It might happen that the devices P1, P2, P3 through interaction among themselves agree upon on the following pattern of sourcing the video fragments - P1 to transmit fragments f1, f3 and f5, P2 to transmit the fragments f2 and f4, and P3 to transmit the fragment f6 to the recipient device 106. It can be noted that the order of transmission of fragments f1-f6 by P1, P2 and P3 is such that the video is played in a continuous and smooth manner at the device P4. Alternatively, the device P4 may send a request for streaming one or more fragments (e.g., f1 and f2) to the device, say P1, having highest weight value since the device P1 is having a strong uplink. Suddenly, if the P2 becomes stronger than P1, then the recipient device 106 recalculates the weight value and sends a request for streaming fragment (e.g., f4) to the device P2. Accordingly, the device P2 streams the fragment f4 to the recipient device 106. The process continues till all the fragments are streamed by the devices P1, P2 and P3 based on the request from the device P1.

Figure 5 is a block diagram of the donor device 102A, such as those shown in Figure 1, showing various components for implementing embodiments of the present subject matter. In Figure 5, the donor device 102A includes a processor 502, memory 504, a read only memory (ROM) 506, a communication interface 508, a bus 510, a display 512, an input device 514, and a cursor control 516.

The processor 502, as used herein, means any type of computational circuit, such as, but not limited to, a microprocessor, a microcontroller, a complex instruction set computing microprocessor, a reduced instruction set computing microprocessor, a very long instruction word microprocessor, an explicitly parallel instruction computing microprocessor, a graphics processor, a digital signal processor, or any other type of processing circuit. The processor 502 may also include embedded controllers, such as generic or programmable logic devices or arrays, application specific integrated circuits, single-chip computers, smart cards,
and the like.

The memory 504 may be volatile memory and non-volatile memory. For example, the memory 504 includes a distributed streaming module 518 for streaming one or more fragments of media file in a distributed manner, according to one or more embodiments described in Figures 1A to 3. A variety of computer-readable storage media may be stored in and accessed from the memory elements. Memory elements may include any suitable memory device(s) for storing data and machine-readable instructions, such as read only memory, random access memory, erasable programmable read only memory, electrically erasable programmable read only memory, hard drive, removable media drive for handling compact disks, digital video disks, diskettes, magnetic tape cartridges, memory cards, and the like.

Embodiments of the present subject matter may be implemented in conjunction with modules, including functions, procedures, data structures, and application programs, for performing tasks, or defining abstract data types or low-level hardware contexts. The distributed streaming module 518 may be stored in the form of machine-readable instructions on any of the above-mentioned storage media and may be executed by the processor 502. For example, a computer program may include machine-readable instructions capable of encoding and streaming one or more fragments of media file in a distributed manner, according to the teachings and herein described embodiments of the present subject matter. In one embodiment the computer program may be included on a compact disk-read only memory (CD-ROM) and loaded from the CD-ROM to a hard drive in the non-volatile memory.

The bus 510 acts as interconnect between various components of the donor device 102A. The components such as the ROM 506, the communication interface 508, display 512, the input device 514, and the cursor control 516 are well known to the person skilled in the art and hence the explanation is thereof omitted.

Figure 6 is a block diagram of the recipient device 104, such as those shown in Figure 1, showing various components for implementing embodiments of the present subject matter. In Figure 6, the recipient device 104 includes a processor 602, memory 604, a read only memory (ROM) 606, a communication interface 608, a bus 610, a display 612, an input device 614, and a cursor control 616.

The processor 602, as used herein, means any type of computational circuit, such as, but not limited to, a microprocessor, a microcontroller, a complex instruction set computing microprocessor, a reduced instruction set computing microprocessor, a very long instruction word microprocessor, an explicitly parallel instruction computing microprocessor, a graphics processor, a digital signal processor, or any other type of processing circuit. The processor 602 may also include embedded controllers, such as generic or programmable logic devices or arrays, application specific integrated circuits, single-chip computers, smart cards, and the like.

The memory 604 may be volatile memory and non-volatile memory. For example, the memory 604 includes a playback module 618 for downloading fragments of a media file from one or more donor devices in a distributed media streaming environment in a distributed manner and playing media corresponding to the fragments of media file, according to one or more embodiments described in Figures 1A to 3. A variety of computer-readable storage media may be stored in and accessed from the memory elements. Memory elements may include any suitable memory device(s) for storing data and machine-readable instructions, such as read only memory, random access memory, erasable programmable read only memory, electrically erasable programmable read only memory, hard drive, removable media drive for handling compact disks, digital video disks, diskettes, magnetic tape cartridges, memory cards, and the like.

Embodiments of the present subject matter may be implemented in conjunction with modules, including functions, procedures, data structures, and application programs, for performing tasks, or defining abstract data types or low-level hardware contexts. The playback module 618 may be stored in the form of machine-readable instructions on any of the above-mentioned storage media and may be executed by the processor 602. For example, a computer program may include machine-readable instructions capable of downloading fragments of a media file from one or more donor devices in a distributed media streaming environment in a distributed manner and playing media corresponding to the fragments of media file on the display 612, according to the teachings and herein described embodiments of the present subject matter. In one embodiment, the computer program may be included on a compact disk-read only memory (CD-ROM) and loaded from the CD-ROM to a hard drive in the non-volatile memory. processing circuit. The processor 602 may also include embedded controllers, such as generic or programmable logic devices or arrays, application specific integrated circuits, single-chip computers, smart cards, and the like.

The memory 604 may be volatile memory and non-volatile memory. For example, the memory 604 includes a playback module 618 for downloading fragments of a media file from one or more donor devices in a distributed media streaming environment in a distributed manner and playing media corresponding to the fragments of media file, according to one or more embodiments described in Figures 1A to 3. A variety of computer-readable storage media may be stored in and accessed from the memory elements. Memory elements may include any suitable memory device(s) for storing data and machine-readable instructions, such as read only memory, random access memory, erasable programmable read only memory, electrically erasable programmable read only memory, hard drive, removable media drive for handling compact disks, digital video disks, diskettes, magnetic tape cartridges, memory cards, and the like.

Embodiments of the present subject matter may be implemented in conjunction with modules, including functions, procedures, data structures, and application programs, for performing tasks, or defining abstract data types or low-level hardware contexts. The playback ifsodule 618 may be stored in the form of machine-readable instructions on any of the above-mentioned storage media and may be executed by the processor 602. For example, a computer program may include machine-readable instructions capable of downloading fragments of a media file from one or more donor devices in a distributed media streaming environment in a distributed manner and playing media corresponding to the fragments of media file on the display 612, according to the teachings and herein described embodiments of the present subject matter. In one embodiment, the computer program may be included on a compact disk-read only memory (CD-ROM) and loaded from the CD-ROM to a hard drive in the non-volatile memory.

The bus 610 acts as interconnect between various components of the recipient device 104. The components such as the ROM 606, the communication interface 608, display 612, the input device 614, and the cursor control 616 are well known to the person skilled in the art and hence the explanation is thereof omitted.

The present embodiments have been described with reference to specific example embodiments; it will be evident that various modifications and changes may be made to these embodiments without departing from the broader spirit and scope of the various embodiments. Furthermore, the various devices, modules, and the like described herein may be enabled and operated using hardware circuitry, for example, complementary metal oxide semiconductor based logic circuitry, firmware, software and/or any combination of hardware, firmware, and/or software embodied in a machine readable medium. For example, the various electrical structure and methods may be embodied using transistors, logic gates, and electrical circuits, such as application specific integrated circuit.

We Claim:

1. A method of downloading a media file in a distributed media streaming environment, comprising:

(a) determining multiple donor devices capable of streaming a desired media file in a distributed manner;

(b) assigning a weight value for each of the donor devices based on link parameters on a respective communication link with each donor device;

(c) determining order of the donor devices based on the weight values of the donor devices;

(d) sending a request for streaming one or more fragments of the media file to at least one of the donor devices according to the determined order so that the at least one of the donor devices streams the requested fragments of the media file; and

(e) repeating steps (b) to (d) till all fragments of the media file are streamed by the respective donor devices.

2. The method of claim 1, wherein determining multiple donor devices capable of streaming the desired media file comprises:

sending a request to provide capability to stream the desired media file to a plurality of donor inovices in the distributed media streaming environment;

receiving a response from each of the plurality of donor devices indicating whether said each donor device is capable of streaming fragments of the media file; and
determining multiple donor devices from the plurality of donor devices based on the response from said each donor device.

3. The method of claim 1, wherein determining multiple donor devices capable of streaming the desired media file comprises:

sending a request to provide a list of donor devices capable of streaming fragments of a desired media file to a file look-up server;

receiving a list of donor devices capable of streaming fragments of the media file in response to the request; and

identifying multiple donor devices from the received list of donor devices for streaming the desired media file.

4. The method of claim 1, wherein the link parameters comprises bandwidth and latency on the respective communication link.

5. The method of claim 4, wherein assigning the weight value for each of the donor devices based on the link parameters associated with the respective communication link with said each donor device comprises:

calculating bandwidth and latency associated with the communication link with each donor device; and

computing a weight value associated with each donor device based on the calculated bandwidth and latency on the respective communication link.

6. The method of claim 1, wherein sending the request for streaming one or more fragments of the media file to the at least one of the donor devices comprises:

identifying at least one of the donor devices having highest weight value; and

sending a request for streaming one or more fragments of the media file to the identified donor device.

7. The method of claim 1, wherein the request for streaming the one or more fragments to the identified donor device, the request comprises a fragment number and a unique file signature associated with the desired media file.

8. An apparatus comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises a distributed streaming module configured for:

(a) determining multiple donor devices capable of streaming a desired media file in a distributed manner;

(b) assigning a weight value for each of the donor devices based on link parameters on a respective communication link with each donor device;

(c) determining order of the donor devices based on the weight values of the donor devices;

(d) sending a request for streaming one or more fragments of the media file to at least one of the donor devices according to the determined order so that the at least one of the donor devices streams the requested fragments of the media file; and

(e) repeating steps (b) to (d) till all fragments of the media file are streamed by the respective donor devices.

9. The apparatus of claim 8, wherein in determining multiple donor devices capable of streaming the desired media file, the distributed streaming module is configured for.

sending a request to provide capability to stream the desired media file to a plurality of donor devices in the distributed media streaming environment;
receiving a response from each of the plurality of donor devices indicating whether said each donor device is capable of streaming fragments of the media file; and
determining multiple donor devices from the plurality of donor devices based on the response from said each donor device.

10. The apparatus of claim 8, wherein in determining multiple donor devices capable of streaming the desired media file, the distributed streaming module is configured for.

sending a request to provide a list of donor devices capable of streaming fragments of a desired media file to a file look-up server;

receiving a list of donor devices capable of streaming fragments of the media file in response to the request; and

identifying multiple donor devices from the received list of donor devices for streaming the desired media file.

11. The apparatus of claim 8, wherein the link parameters comprises bandwidth and latency on the respective communication link.

12. The apparatus of claim 8, wherein in assigning the weight value for each of the donor devices based on the link parameters associated with the respective communication link with said each donor device, the distributed streaming module configured for:

calculating bandwidth and latency associated with the communication link with each donor device; and

computing a weight value associated with each donor device based on the calculated bandwidth and latency on the respective communication link.

13. The apparatus of claim 8, wherein in sending the request for streaming one or more fragments of the media file to the at least one of the donor devices, the distributed streaming module is configured for:

identifying at least one of the donor devices having highest weight value; and sending a request for streaming one or more fragments of the media file to the identified donor device.

14. The apparatus of claim 8, wherein the request for streaming the one or more fragments to the identified donor device, the request comprises a fragment number and a unique file signature associated with the desired media file.

15. A method of streaming media in a distributed media streaming environment, comprising:

receiving a request for streaming a media file from a recipient device;
negotiating, with at least one donor device, number of fragments of the media file and order in which each of the fragments is to be streamed to the recipient device based on link parameters associated with a respective communication link with the recipient device; and

streaming one or more of the fragments of the media file in the negotiated order to the recipient device.

16. The method of claim 15, wherein the request for streaming the media file comprise a unique file signature of the media file, and link parameters associated with the respective communication link.

17. The method of claim 15, wherein negotiating the number of fragments of the module file and the order in which each of the fragments is to be streamed by the recieve device comprises:

computing a weight value associated with each of the donor devices based c bandwidth and latency associated with a respective communication link with the recipient device;

determining which of the fragments of the media file are to be streamed by each of the donor devices based on the weight value associated with each of the donor device and

negotiating order in which the fragments are to be streamed to the recipient device t each of the donor devices.

18. The method of claim 16, wherein the link parameters comprises latency an bandwidth associated with the respective communication link.

19. An apparatus comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises a playba< module configured for receiving a request for streaming a media file from a recipient device;

negotiating, with at least one donor device, number of fragments of the media in and order in which each of the fragments is to be streamed to the recipient dev based on link parameters associated with a respective communication link with the recipient device; and

streaming one or more of the fragments of the media file in the negotiated order to the recipient device.

20. The apparatus of claim 19, wherein the request for streaming the media file comprises a unique file signature of the media file, and link parameters associated with the respective communication link.

21. The apparatus of claim 19, wherein in negotiating the number of fragments of the media file and the order in which each of the fragments is to be streamed by the recipient device, the playback module is configured for:

computing a weight value associated with each of the donor devices based on bandwidth and latency associated with a respective communication link with the recipient device;

determining which of the fragments of the media file are to be streamed by each of the donor devices based on the weight value associated with each of the donor devices; and

negotiating order in which the fragments are to be streamed to the recipient device by eacfcs? &s donor devices.

22. The apparatus of claim 19, wherein the link parameters comprises latency and bandwidth associated with the respective communication link.