Optimising communications

• US 8,289,949 B2
• Filed: 02/19/2010
• Issued: 10/16/2012
• Est. Priority Date: 04/14/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Skype S.Ã R.L. (Microsoft Corporation)
• Inventors: Hiie, Magnus, Heinla, Ahti, Keskküla, Silver
• Primary Examiner(s): Ho, Chuong T
• Application Number:
  US12/660,063
• Publication Number:
  US 20100260191A1
• Time in Patent Office: 970 Days
• Field of Search: 370/351, 370/400, 709/241, 709/240, 709/242, 709/231
• US Class Current: 370/351
• 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 two or more 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 two or more consuming end-user nodes, the utility function being dependent on route and defining a quantitative measure of end-user benefit that would be derived from the stream at a respective consuming end-user node if the stream is consumed by the respective consuming end-user node;

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

selecting one of the plurality of possible combinations of routes for said stream based on the overall utility values of the plurality of possible combinations of routes; and

routing the stream to the two or more consuming end-user nodes via the selected combination of 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 two or more consuming end-user nodes; and

for each of said plurality of possible combinations of routes, the utility function for each of the two or more 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 an 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 a 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 properties relating to the consumption of the stream 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, further comprising receiving information from each of said two or more end-user nodes 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 receiving said information comprises receiving one or more user-signalled parameters from each of said two or more end-user nodes, the utility function for each of said two or more end-user nodes being a function of the respective parameters.

12. The method of claim 10, wherein the receiving said information comprises receiving from each of said two or more end-user nodes an indication of a form of its respective utility function, and wherein the using 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 of routes transmitting the stream from alternative sources.

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

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

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

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

18. The method of claim 1, wherein the determining said overall utility value comprises taking one of a sum or a product of the utility functions of each of said two or more consuming end-user nodes.

19. The method of claim 1, wherein the selecting the one of the plurality of possible combinations of routes comprises selecting the one of the plurality of possible combinations of routes based on a comparison of the overall utility values of the possible combinations of routes.

20. The method of claim 1, further comprising determining said plurality of possible combinations of routes by eliminating one or more other possible combinations of routes ruled out by constraints on one or more of:

uplink bandwidth, downlink bandwidth, processing resources of one or more of the two or more 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 eliminating comprises eliminating the one or more other possible combinations of routes based at least in part on 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 two or more 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 further comprises:

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

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 two or more consuming end-user nodes; and

in addition to selecting the one of the plurality of possible combinations of routes, selecting one of the plurality of possible versions of the stream for each of the two or more consuming end-user nodes based on the overall utility values of the plurality of possible combinations of routes;

wherein said routing further comprises routing the respective selected versions of the stream to the consuming two or more end-user nodes via the selected combination of routes.

26. A method according to claim 1, wherein at least one of the two or more consuming 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 two or more 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 derived from a respective one or more of the plurality of said streams at a respective consuming end-user node if the respective one or more of the plurality of said streams is consumed by the respective consuming end-user node;

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 two or more consuming end-user nodes;

selecting one of the plurality of possible combinations of routes for said streams based on the overall utility values of the plurality of possible combinations of routes; and

routing the streams to the two or more consuming end-user nodes via the selected combination of routes.

27. The method of claim 26, wherein said at least one of the two or more consuming end-user nodes is a consumer of one of said streams and a relay of another stream.

28. The method of claim 26, wherein said at least one of the two or more consuming end-user nodes is a consumer of a plurality of said streams.

29. The method of claim 1, wherein:

said plurality of possible combinations of routes additionally include a route to a gateway node providing access to an additional 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 additional 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 additional network; and

the utility of the gateway node is included in determining the overall utility of each of said plurality of possible combinations of routes.

30. A client program product for routing a data stream to end-user nodes of a network, the client 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 two or more 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 two or more consuming end-user nodes, the utility function being dependent on route and defining a quantitative measure of end-user benefit that would be derived from the stream at a respective consuming end-user node if the stream is consumed by the respective consuming end-user node;

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

select one of the plurality of possible combinations of routes for said stream based on the overall utility values of the plurality of possible combinations of routes; and

route the stream to the two or more consuming end-user nodes via the selected combination of 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-two or more 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 two or more consuming end-user nodes, the utility function being dependent on route and defining a quantitative measure of end-user benefit that would be derived from the stream at a respective consuming end-user node if the stream is consumed by the respective consuming end-user node;

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

select one of the plurality of possible combinations of routes for said stream based on the overall utility values of the plurality of possible combinations of routes; and

wherein the transceiver is configured to route the stream to the two or more consuming end-user nodes via the selected combination of routes.