Optimising communications

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

• Current Assignee: Skype S.Ã R.L. (Microsoft Corporation)
• Original Assignee: Skype Limited (Microsoft Corporation)
• Inventors: Keskküla, Silver, Andersen, Soren Vang, Heinla, Ahti, Hiie, Magnus
• Granted Patent: US 8,289,979 B2
• Time in Patent Office: Days
• 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 optimisation 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 amongst a plurality of network nodes including at least a plurality of end-user nodes, the method comprising:

establishing a plurality of routes for said 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 optimisation 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, determining a change in the routing criterion that would result from one or more potential routing modifications, and determining whether any of said potential modifications is preferred based on the determined change, wherein 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; and

when one or more of said preferred modifications is found, modifying one or more of said routes accordingly, and transmitting the stream to the consuming end-user nodes via the routes as thus modified.

2. The method of claim 1, wherein said optimising nodes are end-user nodes.

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

4. The method of claim 3, wherein:

said establishment of a plurality of routes comprises establishing a set of connections amongst a group of end-user nodes, each end-user node of the group establishing a connection with at least one other of said group, so as to create said plurality of routes for said stream to a plurality of consuming end-user nodes of said group, including at least one route via one or more relaying end-user nodes of said group; and

each of said collections comprises only a sub-group of the group such that, at each of the plurality of optimising nodes, the determination of the respective routing modification is by;

evaluating the routing criterion with respect to only a sub-group of said group, and determining the change in the routing criterion with respect to the sub-group as would be affected by one or more potential routing modifications, wherein the different optimising nodes'"'"' sub-groups are at least partially coincident.

5. The method of claim 4, wherein at least two of the sub-groups contain some but not all of the same end-user nodes.

6. The method of claim 4, wherein said sub-group comprises the end-user nodes of said group within a specified number of successive connections from the respective optimising end-user node.

7. The method of claim 6, wherein said connections comprise a plurality of transport connections which create said routes.

8. The method of claim 7, wherein said connections comprise one or more additional connections not used to create routes for a stream.

9. The method of claim 4, comprising determining said set of connections by:

determining a plurality of transport connections between the end-user nodes in order to create said routes, and removing some of the transport connections from the set;

wherein said sub-group comprises the end-user nodes of said group within a specified number of successive ones of said set of connections from the respective optimising end-user node.

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

when one of said preferred modifications is found at an optimising node, communicating the preferred modification to others of said optimising nodes as a proposed modification;

at each of said other optimising nodes, using the respective optimisation algorithm to determine whether the proposed modification would be acceptable according a routing criterion evaluated only with respect to its own respective collection of end-user nodes; and

indicating an agreement or disagreement from said others of the optimising nodes in dependence on the respective evaluations;

wherein said modification is dependent on agreement of at least one of said other optimising end-user nodes.

11. The method of claim 10, wherein said determination of whether the proposed modification is acceptable comprises executing an algorithm at each of said other optimising nodes to:

evaluate a routing criterion with respect to its own respective collection of end-user nodes, determine a change in the routing criterion with respect to the respective collection as would be affected by the proposed modification, and determine whether the proposed modification would be acceptable based the determined change.

12. The method of claim 10, wherein the proposed modification comprises a plurality of successive routing stages, wherein a modification to a succeeding stage can be made without affecting the routing criterion evaluated with respect to its preceding stage;

and the method comprises;

at each of said other optimising nodes, using the respective algorithm to separately determine whether each successive stage of the proposed modification would be acceptable based on a routing criterion evaluated only with respect to its own respective collection of end-user nodes; and

for each of the stages, indicating an agreement or disagreement from said others of the optimising nodes in dependence on the respective evaluations;

wherein said modification is dependent on agreement of one or more of said other optimising nodes, such that each stage is modified only on the respective agreement of at least one of the other optimising nodes, and each succeeding stage is only modified on a further condition that its preceding stage is modified.

13. The method of claim 10, wherein the proposed modification comprises a plurality of independent parts, such that a modification according to any of the independent parts can be made without affecting the routing criterion evaluated with respect to any other of the independent parts;

and the method comprises;

at each of said other optimising nodes, using the respective algorithm to separately determine whether each independent part of the proposed modification would be acceptable according a routing criterion evaluated only with respect to its own respective collection of end-user nodes; and

for each of the independent parts, indicating an agreement or disagreement from said others of the optimising nodes in dependence on the respective evaluations;

wherein said modification is dependent on agreement of one or more of said other optimising nodes, such that each independent part is modified only on the respective agreement of at least one of the other optimising nodes.

14. The method of claim 6, wherein the specified number is two.

15. The method of claim 6, wherein the specified number is three.

16. The method of claim 1, wherein the optimisation algorithm is executed dynamically at each of said optimising nodes, so as to repeat said evaluation and determination throughout transmission of the stream.

17. The method of claim 1, wherein the stream comprises one of an audio stream and a video stream.

18. The method of claim 17, wherein said stream is a stream of a live multi-party video call or voice call.

19. The method of claim 2, wherein said optimising end-user nodes comprise one or more of said consuming end-user nodes.

20. The method of claim 19, wherein said optimising end-user nodes comprise all of the consuming end-user nodes of said stream.

21. The method of claim 1, wherein one or more of said optimising nodes comprises a source of said stream.

22. The method of claim 21, wherein said optimising nodes comprise all of a plurality of sources of said stream.

23. The method of claim 1, wherein said optimising nodes comprise one or more of said relaying nodes.

24. The method of claim 23, wherein said optimising nodes comprise all of the relaying nodes of said stream.

25. The method of claim 2, wherein at least one of said relaying end-user nodes is also a consuming end-user node

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

27. The method of claim 1, wherein said routing criterion is based on an overall utility of the respective collection of end-user nodes, utility being a quantitative estimate of end-user benefit derived from consumption of the stream.

28. A method of routing a plurality of data streams according to claim 1, comprising:

for each of said plurality of streams, 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 end-user nodes, wherein at least one of the end-user nodes is a consumer and/or relay of each of a plurality of said streams.

29. A program product for routing a data stream amongst a plurality of network nodes including at least a plurality of end-user nodes, wherein a plurality of routes are established for said stream to a plurality of consuming end-user nodes including at least one route via one or more relaying nodes, the program comprising code which when executed on an optimising node of the network will operate in conjunction with like programs executed on other such optimising nodes to perform the steps of:

at each of the plurality of optimising nodes, performing an optimisation 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, determining a change in the routing criterion that would result from one or more potential routing modifications, and determining whether any of said potential modifications is preferred based on the determined change, wherein the different optimising nodes'"'"' collections 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; and

when one or more of said preferred modifications is found, causing one or more of said routes to be modified accordingly, such that the stream is transmitted to the consuming end-user nodes via the routes as thus modified.

30. A communication system for routing a data stream amongst a plurality of network nodes including at least a plurality of end-user nodes, wherein a plurality of routes are established for said stream to a plurality of consuming end-user nodes including at least one route via one or more relaying nodes, the communication system comprising a plurality of optimising nodes of said network configured so as to:

at each of the plurality of optimising nodes, performing an optimisation 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, determining a change in the routing criterion that would result from one or more potential routing modifications, and determining whether any of said potential modifications is preferred based on the determined change, wherein the different optimising nodes'"'"' collections 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; and

when one or more of said preferred modifications is found, cause one or more of said routes to be modified accordingly, such that the stream is transmitted to the consuming end-user nodes via the routes as thus modified.

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

establishing a set of connections amongst a group of end-user nodes, each end-user node of the group establishing a connection with at least one other of said group, so as to create a plurality of routes for said stream to a plurality of consuming end-user nodes of said group, including at least one route via one or more relaying end-user nodes of said group;

at each of a plurality of optimising end-user nodes of said group, executing an optimisation algorithm to determine a respective routing modification by;

evaluating a routing criterion with respect to at least a respective sub-group of the end-user nodes, determining a change in the routing criterion that would result from one or more potential routing modifications, and determining whether any of said potential modifications is preferred based on the determined change; and

when one or more of said preferred modifications is found, modifying one or more of said routes accordingly, and transmitting the stream to the consuming end-user nodes via the routes as thus modified.