Optimising communications

• US 20100260191A1
• Filed: 02/19/2010
• Published: 10/14/2010
• Est. Priority Date: 04/14/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Skype Limited (Microsoft Corporation)
• Inventors: Keskkula, Silver, Heinla, Ahti, Hiie, Magnus
• Granted Patent: US 8,289,949 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• 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

Abstract

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

Claims

1. A method of routing a data stream to end-user nodes of a network, the method comprising:

for each of a plurality of possible combinations of routes of said stream to a plurality of consuming end-user nodes, including at least one possible combination routing via one or more relaying nodes, evaluating a utility function for each of said consuming end-user nodes, the utility function being dependent on route and defining a quantitative measure of end-user benefit that would be experienced at the respective end-user node by consumption of the stream;

for each of said plurality of possible combinations of 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;

selecting a preferred combination of routes for said stream based on the overall utility values of the different possible combinations; and

routing the stream to the consuming end-user nodes via the selected routes.

2. The method of claim 1, wherein said one or more relaying nodes are end-user nodes.

3. The method according to claim 1, wherein:

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

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

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

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

5. The method according to claim 3, wherein said one or more transport properties at least comprise a delay, and the estimation of the delay is based on a measure of at least one of:

geographical proximity of end-user nodes involved in the respective route, and a connectivity of one or more relaying end-user nodes involved in the respective route.

6. The method according to claim 1, wherein the utility function is dependent on one or more properties of the stream as transmitted from source.

7. The method according to claim 6, wherein said one or more properties of the stream as transmitted comprise at least one of:

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

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

9. The method according to claim 8, 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.

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

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

12. The method of claim 10 wherein the receipt of said information comprises receiving from each end-user 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.

13. The method of claim 1, wherein said possible combinations of routes include at least two combinations transmitting the same stream from alternative source.

14. The method of claim 1, wherein said possible combinations include at least one combination routing the stream from one relaying end-user node to a plurality of said consuming end-user nodes

15. The method of claim 1, wherein said possible combinations include at least one combination routing the stream from one relaying end-user node to another relaying end-user node.

16. The method of claim 1, wherein said possible combinations include a plurality of combinations routing via one or more relaying end-user nodes.

17. The method of claim 1, wherein said possible combinations include at least one combination dividing the stream along parallel routes to one of said consuming end-user nodes.

18. The 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 nodes.

19. The method of claim 1, wherein the selection of said preferred combination is based on a comparison of the overall utility values of the different possible combinations.

20. The method of claim 1, comprising determining said plurality of possible combinations of routes from a greater number of combinations of 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 nodes involved in one or more of the routes, and connectivity due to firewalls.

21. The method of claim 20, wherein the stream comprises an indication of minimum performance requirements for the stream, and said elimination is performed by reference to the minimum performance requirements indicated in the stream.

22. The method of claim 1, wherein 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 the stream.

23. The method of claim 2, wherein at least one of said one or more relaying end-user nodes is one of said consuming end-user nodes

24. The method of claim 2, wherein at least one of said one-or more relaying end-user nodes is not a consumer of the stream it relays.

25. The method according to claim 1, wherein the method comprises:

for each of said plurality of possible combinations, evaluating the utility function for each of a plurality of possible versions of the stream, each being a different quality version of the same content, and the utility function being dependent on the version;

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

in addition to selecting the routes, selecting a preferred version of the stream for each of the consuming end-user nodes 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 nodes via the selected routes.

26. A method according to claim 1 of distributing a plurality of data streams amongst end-user nodes of the network, wherein at least one of the end-user nodes is a consumer and/or relay of each of a plurality of said streams, the method comprising:

for each of a plurality of possible combinations of routes of said streams to the consuming end-user nodes, including at least one possible combination routing via one or more relaying end-user nodes, evaluating a utility function for each of said consuming end-user nodes, the utility function defining a quantitative measure of end-user benefit that would be experienced at the respective end-user node by consumption of the respective one or more streams;

for each of said plurality of possible combinations of routes, determining an overall utility value based on the evaluation of the utility functions of each of said plurality of consuming end-user nodes;

selecting a preferred combination of routes for said streams based on the overall utility values of the different possible combinations; and

routing the streams to the consuming end-user nodes via the selected routes.

27. The method of claim 26, wherein said at least one end-user node is a consumer of one of said streams and a relay of another.

28. The method of claim 26, wherein said at least one end-user node is a consumer of a plurality of said streams.

29. The method of claim 1, wherein:

said possible combinations of routes additionally include a route to a gateway node providing access to another network; and

the method further comprises, for each of the plurality of possible combinations of routes, additionally evaluating a utility function for a gateway node to the other network, the utility function being dependent on route and defining a quantitative measure of end-user benefit that would be experienced by an end-user of said other network; and

the utility of the gateway is included in determining the overall utility of each possible combination.

30. A client program product for routing a data stream to end-user nodes of a network, the program comprising code which when executed on an end-user node of the network will operate in conjunction with like client programs executed on other end-user nodes of the network to:

for each of a plurality of possible combinations of routes of said stream to a plurality of consuming end-user nodes, including at least one possible combination routing via one or more relaying nodes, evaluate a utility function for each of said consuming end-user nodes, the utility function being dependent on route and defining a quantitative measure of end-user benefit that would be experienced at the respective end-user node by consumption of the stream;

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

select a preferred combination of routes for said stream based on the overall utility values of the different possible combinations; and

route the stream to the consuming end-user nodes via the selected routes.

31. A communication system for transmitting a data stream to end-user nodes of a network, the communication system comprising 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 routes of said stream to a plurality of consuming end-user nodes, including at least one possible combination routing via one or more relaying nodes, evaluate a utility function for each of said consuming end-user nodes, the utility function being dependent on route and defining a quantitative measure of end-user benefit that would be experienced at the respective end-user node by consumption of the stream;

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

select a preferred combination of routes for said stream based on the overall utility values of the different possible combinations; and

wherein the transceiver is configured to route the stream to the consuming end-user nodes via the selected routes.