Optimising communications

• US 8,873,568 B2
• Filed: 09/14/2012
• Issued: 10/28/2014
• 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, Andersen, Soren Vang, Heinla, Ahti, Keskkula, Silver
• Primary Examiner(s): Nooristany, Sulaiman
• Application Number:
  US13/618,583
• Publication Number:
  US 20130016728A1
• Time in Patent Office: 774 Days
• Field of Search: None
• US Class Current: 370/400
• CPC Class Codes: H04L 12/1822 Conducting the conference, e.g. admission, detection, selection or grouping of participants, correlating users to one or more conference sessions, prioritising transmission
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/243 using M+N parallel active paths
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1053 with pre-configuration of logical or physical connections with a determined number of other peers
• CPC Class Codes: H04L 67/1074 for supporting data block transmission mechanisms file transfer H04L67/06

Abstract

A method, system and program for routing a data stream amongst a plurality of network nodes including at least a plurality of end-user nodes. The method comprises: establishing a plurality of routes for the stream to a plurality of consuming end-user nodes, including at least one route via one or more relaying nodes; at each of a plurality of optimising nodes, executing an optimization algorithm to determine a respective routing modification by evaluating a routing criterion with respect to a collection of end-user nodes which share information with the respective optimising node and determining a change in the routing criterion that would result from one or more potential routing modifications. The different optimising nodes'"'"' collections of end-user nodes are at least partially coincident such that each optimising node can determine a different routing modification with respect to at least some of the same end-user nodes.

Claims

1. A method of routing a data stream among a plurality of network nodes including at least a plurality of end-user nodes, the method comprising:

obtaining the data stream at an optimising node included in routes established for said data stream to a plurality of consuming end-user nodes formed by connections amongst a group of end-user nodes;

executing an optimisation algorithm at the optimizing node to determine routing modifications with respect to a sub-group of the group of end-user nodes by;

evaluating a routing criterion with respect to a collection of end-user nodes within a respective said sub-group which share information with the optimising node, the routing criterion based upon an overall utility value that quantitatively estimates end-user benefit derived from consumption of the stream by the plurality of end-user nodes;

applying one or more routing modifications to modify the routes based on the evaluation of the routing criterion with respect to the sub-group; and

transmitting the data stream to the consuming end-user nodes via the routes as modified.

2. The method as recited in claim 1, wherein the data stream comprises at least one of an audio stream or a video stream.

3. The method as recited in claim 1, wherein the data stream comprises at video call.

4. A method as recited in claim 1, wherein the data stream comprises at voice call.

5. A method as recited in claim 1, wherein the optimising node comprises a relay node included in one of said routes between a source of the data stream and at least one of the plurality of consuming end-user nodes.

6. A method as recited in claim 1, wherein the optimising node comprises one of the plurality of consuming end-user nodes.

7. A method as recited in claim 1, wherein the optimising node comprises a source of the data stream.

8. A method as recited in claim 1, wherein said overall utility value is computed as a combination of factors that affect utility including one or more of stream properties, transport properties, or consumption properties.

9. A method as recited in claim 1, wherein evaluating the routing criterion comprises:

determining changes in the routing criterion with respect to the collection of end-user nodes within the sub-group for potential routing modifications; and

selecting at least one of the potential routing modifications as preferred based on the determined changes.

10. A method as recited in claim 1, wherein evaluating routing criterion comprises computing utility values for multiple potential routes based on utility values assigned to end-user nodes in the multiple potential routes.

11. A method of routing a data stream among a plurality of nodes in a peer-to-peer network, the method comprising:

ascertaining a plurality of potential routes for communication of the data stream to one or more endpoints through the plurality of nodes;

selecting a routing for the data stream using the plurality of potential routes by evaluating routing criterion with respect to a sub-group of said plurality of nodes within a designated number of connections between a source of the data stream and the one or more endpoints, including;

computing utility values for each of the plurality of potential routes using a combination of factors that affect utility including one or more of stream properties, transport properties, or consumption properties; and

deriving scores to quantify end-user benefit for each of the plurality of potential routes based on the utility values; and

causing communication of at least a portion of the data stream to the one or more endpoints nodes via the selected routing.

12. A method as recited in claim 11, wherein:

the data stream contains both an audio stream and video stream; and

selecting the routing comprises selecting different routes for the audio stream and the video stream.

13. A method as recited in claim 11, wherein the plurality of potential routes includes at least one route through one or more relaying nodes.

14. A method as recited in claim 11, wherein the plurality of potential routes includes routes originating from multiple different sources available for the data stream.

15. A method as recited in claim 11, wherein selecting a routing comprises:

communicating a routing proposal to recipient nodes of the plurality of nodes in the peer-to-peer network based on the evaluating; and

obtaining feedback from the recipient nodes regarding the proposal, the selected routing determined at least in part based on the feedback that is obtained.

16. A computing device configured to operate as a node in a peer-to-peer network comprising:

a processing unit;

a storage device storing a client application that, when executed via the processing unit, performs operations for routing a data stream among a plurality of nodes in the peer-to-peer network including;

ascertaining a plurality of potential routes for communication of the data stream to one or more endpoints through the plurality of nodes;

selecting one or more routes from the plurality of potential routes by evaluating routing criterion with respect to a sub-group of said plurality of nodes within a designated number of connections between the computing device and the one or more endpoints, including;

computing utility values for the plurality of potential routes based on one or more of stream properties, transport properties, or consumption properties that affect utility; and

scoring the plurality of potential routes based on the utility values to quantify end-user benefit derived from consumption of the data stream; and

routing the data stream to the one or more endpoints nodes via the one or more selected routes.

17. A computing device as recited in claim 16, wherein

the data stream contains both an audio stream and video stream;

and

selecting the one or more routes comprises selecting different routes for the audio stream and the video stream.

18. A computing device as recited in claim 16, wherein evaluating the routing criterion further comprises ruling out one or more possible routes due to resource constraints prior to computing the utility values.

19. A computing device as recited in claim 16, wherein the plurality of potential routes includes routes originating from multiple different sources available for the data stream.

20. A computing device as recited in claim 16, wherein selecting a routing comprises:

communicating a routing proposal to other nodes of the plurality of nodes in the peer-to-peer network based on the evaluating; and

obtaining feedback from the other nodes regarding the proposal, the one or more selected routes determined at least in part based on the feedback that is obtained.