Optimising communications

• US 8,463,929 B2
• Filed: 02/19/2010
• Issued: 06/11/2013
• Est. Priority Date: 04/14/2009
• Status: Expired due to Fees

• Current Assignee: Skype S.Ã R.L. (Microsoft Corporation)
• Original Assignee: Skype S.Ã R.L. (Microsoft Corporation)
• Inventors: Hiie, Magnus, Heinla, Ahti, Keskkla, Silver
• Primary Examiner(s): BURGESS, BARBARA N
• Application Number:
  US12/660,142
• Publication Number:
  US 20100262709A1
• Time in Patent Office: 1,208 Days
• Field of Search: 709/203, 709/223, 709/224, 709/227, 709/231, 709/232, 709/233, 709/234, 709/238, 709/239, 709/240, 709/242
• US Class Current: 709/231
• CPC Class Codes: H04L 12/1827 Network arrangements for conference optimisation or adaptation
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/126 minimising geographical or physical path length
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/3065 for real time traffic
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 65/613 for the control of the source by the destination control signals issued by the client directed to the server or network components specially adapted for selective content distribution H04N21/637
• CPC Class Codes: H04L 65/756 adapting media to device capabilities

Abstract

A method, system and program for transmitting different quality versions of a stream to end-user nodes of a network. The method comprises: for each of a plurality of possible combinations of versions of the stream to different consuming end-user nodes, evaluating a utility function for each of those consuming end-user nodes, the utility function being dependent on the version and defining a quantitative measure of end-user benefit that would be experienced at the respective end-user node by consumption of the respective version; for each of said plurality of possible combinations of versions of the stream over said routes, determining an overall utility value based on the respective evaluation of the utility functions of each of said plurality of consuming end-user nodes; and selecting a preferred combination of versions of the stream over said routes based on the overall utility values of the different possible combinations.

Claims

1. A computer implemented method comprising:

for each of a plurality of possible combinations of versions of a stream including content to be transmitted over respective routes to consuming end-user computing nodes of a computer network, processing, by a computer processor, an evaluation of a utility function for each of said consuming end-user computing nodes, the utility function being dependent on the version and defining a quantitative measure of end-user benefit that would be experienced at a respective end-user computing node by consumption of a respective version of the stream when transmitted via the respective route, where each of the versions of the stream includes a different quality version of identical content;

for each of said plurality of possible combinations of versions of the stream for transmission over said respective routes, determining an overall utility value based on a respective evaluation of the utility functions of each of said plurality of consuming end-user computing nodes;

selecting, before the content is transmitted, a combination of versions of the stream for transmission over said respective routes based on the overall utility values of different possible combinations; and

transmitting the selected combination of versions of the stream via the respective routes to the respective consuming end-user computing nodes for consumption of the content thereat, the transmitting configured to transmit the selected combination of versions of the stream through at least one respective route comprising at least one relaying end-user computing node effective to cause the relaying end-user computing node to forward a version of the stream to at least one of said consuming end-user computing nodes.

2. The computer implemented method according to claim 1, wherein:

the computer implemented method comprises, for each of said plurality of possible combinations of versions of the stream over said respective routes, determining an estimate of one or more transport properties of the version of the stream over each respective route to each of the respective consuming end-user computing nodes; and

for each of said plurality of possible combinations of versions of the stream over said respective routes, the utility function for each of the consuming end-user computing nodes defines the measure of end-user benefit as a function of said one or more transport properties.

3. The computer implemented method according to claim 2, wherein said one or more transport properties comprise at least one of:

a packet-loss rate, a delay, a jitter, and an achievable bitrate.

4. The computer implemented method according to claim 1, wherein:

the utility function is dependent on one or more properties of the version of the stream as transmitted from a source.

5. The computer implemented method according to claim 4, wherein said one or more properties of the version of the stream as transmitted comprise at least one of:

an encoded bitrate, distortion, codec, video frame rate, video resolution, and audio sampling rate.

6. The computer implemented method of claim 1, wherein the utility function is dependent on the stream'"'"'s type.

7. The computer implemented method according to claim 1, wherein the utility function is dependent on one or more properties relating to the consumption of the stream.

8. The computer implemented method according to claim 7, wherein said one or more consumption-related properties comprise at least one of:

a video window size, a property of an audio output device, and a property of a video output device.

9. The computer implemented method of claim 1, comprising receiving information from each end-user computing node relating to the evaluation of its respective utility function, wherein the evaluation of the utility function comprises using said information in the evaluation.

10. The computer implemented method of claim 9, wherein the receipt of said information comprises receiving one or more user-signalled parameters from each end-user computing node, the utility function for each of the end-user computing nodes being a function of the respective parameters.

11. The computer implemented method of claim 9 wherein the receipt of said information comprises receiving from each end-user computing node an indication of the form of its respective utility function, and said use of the information comprises evaluating a utility function of the indicated form.

12. The computer implemented method according to claim 1, wherein the transmitting is further configured to transmit the selected combination of versions of the stream through a respective route comprising at least one relaying end-user computing node effective to cause the relaying end-user computing node to consume at least one version of the stream in addition to forwarding the version of the stream to the at least one of said consuming end-user computing nodes.

13. The computer implemented method according to claim 1, wherein the at least one relaying end-user computing node is not a consumer of the stream it relays.

14. The computer implemented method of claim 1, wherein the determination of said overall utility value comprises taking one of the sum and the product of the evaluated utility functions of each of said plurality of consuming end-user computing nodes.

15. The computer implemented method of claim 1, wherein the selection of said combination of versions of the stream is based on a comparison of the overall utility values of different possible combinations.

16. The computer implemented method of claim 1, comprising determining said plurality of possible combinations of versions from a greater number of combinations of versions of the stream over said respective routes, by first eliminating combinations ruled out by constraints on one or more of:

uplink bandwidth, downlink bandwidth, processing resources of one or more of the end-user computing nodes involved in one or more of the respective routes, and connectivity due to firewalls.

17. The computer implemented method of claim 16, wherein each version of the stream comprises an indication of minimum performance requirements for that version, and said elimination is performed by reference to the minimum performance requirements indicated in each version.

18. The computer implemented method of claim 1, wherein each version of the stream comprises an indication of minimum performance requirements for the stream, and the utility function is dependent on the minimum performance requirements indicated in each version.

19. The computer implemented method of claim 1, wherein each version of each stream comprises a stream ID identifying the content and a version ID identifying the version of that content.

20. The computer implemented method of claim 1, wherein said versions each comprise a different respective number of layers of a layered encoding scheme.

21. The computer implemented method according to claim 1, wherein the method comprises:

for each of said plurality of possible combinations of versions of the stream, evaluating the utility function for each of a plurality of possible combinations of routes to the plurality of consuming end-user computing nodes, the utility function being dependent on route;

for each of the plurality of possible combinations of the routes with each possible combination of versions of the stream over those routes, determining an overall utility value based on the evaluation of the utility functions of each of said plurality of consuming end-user computing nodes; and

in addition to selecting the versions of the stream, selecting a combination of routes based on the overall utility values of the different possible combinations;

wherein said routing comprises routing the respective selected versions of the stream to the consuming end-user computing nodes via the selected routes.

22. The computer implemented method of claim 21, wherein said plurality of possible combinations of routes include at least one possible combination routing via one or more relaying end-user computing nodes.

23. The computer implemented method according to claim 21 further comprising:

communicating one or more proposed modifications associated with the selected combination of routes to each node in the selected combination of routes;

responsive to receiving a confirmation of agreement to the one or more proposed modifications from each node in the selected combination of routes, establishing one or more connections associated with the one or more proposed modifications; and

responsive to receiving at least one disagreement to the one or more proposed modifications from a node in the selected combination of routes, establishing only one or more stages of connections associated with the one or proposed modifications, the one or more stages configured to include only nodes that responded in agreement to the one or more proposed modifications.

24. A client program product for transmitting selected versions of a stream including content to end-user computing nodes of a computer network, the client program including program comprising code embodied on at least one computer readable hardware storage device which when executed on computer processor of an end-user computing node of the computer network will operate in conjunction with like client programs executed on other end-user computing nodes of the computer network to:

for each of a plurality of possible combinations of versions of the stream to be transmitted over respective routes to consuming end-user computing nodes,

evaluate a utility function for each of said consuming end-user computing nodes, the utility function being dependent on the version and defining a quantitative measure of end-user benefit that would be experienced at a respective end-user computing node by consumption of respective version of the stream when transmitted via the respective route, where each of the versions of the stream includes a different quality version of identical content;

for each of said plurality of possible combinations of versions of the stream over said routes, determine an overall utility value based on a respective evaluation of the utility functions of each of said plurality of consuming end-user computing nodes;

select, before the content is transmitted, a combination of versions of the stream for transmission over said routes based on the overall utility values of different possible combinations; and

transmit the selected combination of versions of the stream via the respective routes to the respective consuming end-user computing nodes for consumption of the content thereat, wherein to transmit via the respective routes includes an ability to transmit over a route comprising at least one other end-user computing node configured as a relaying end-user computing node effective to cause the relaying end-user computing node to forward a version in the selected combination of versions of the stream to at least one of said consuming end-user computing nodes.

25. A computer implemented communication system, the computer implemented communication system comprising:

a computer processor configured to execute an optimiser; and

a transceiver operatively coupled to the optimiser;

wherein the optimiser is configured to;

for each of a plurality of possible combinations of versions of a stream including content to be transmitted over respective routes to consuming end-user computing nodes of a computer network, evaluate a utility function for each of said consuming end-user computing nodes, the utility function being dependent on the version and defining a quantitative measure of end-user benefit that would be experienced at a respective end user computing node by consumption of a respective version of the stream when transmitted via the respective route, where each of the versions of the stream includes a different quality version of identical content;

for each of said plurality of possible combinations of versions of the stream to be transmitted over said routes, determine an overall utility value based on a respective evaluation of the utility functions of each of said plurality of consuming end-user computing nodes; and

select, before the content is transmitted, a combination of versions of the stream over said routes based on the overall utility values of different possible combinations; and

the transceiver is configured to transmit the selected combination of versions of the stream via the respective routes to the respective consuming end-user computing nodes for consumption of the content thereat, wherein to transmit via the respective routes includes an ability to transmit over a route comprising at least one other end-user computing node configured as a relaying end-user computing node effective to cause the relaying end-user computing node to forward a version in the selected combination of versions of the stream to at least one of said consuming end-user computing nodes.