DATA-DRIVEN NETWORK PATH SELECTION

• US 20170347308A1
• Filed: 05/31/2016
• Published: 11/30/2017
• Est. Priority Date: 05/31/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Chou, Philip Andrew, Padmanabhan, Venkata N., Das, Rajdeep, Ananthanarayanan, Ganesh, Jiang, Junchen
• Granted Patent: US 10,045,276 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04W 24/10 Scheduling measurement reports ; Arrangements for measurement reports
• CPC Class Codes: H04W 28/0231 based on communication conditions dynamic wireless traffic scheduling definition based on channel quality criteria H04W72/54
• CPC Class Codes: H04W 40/18 based on predicted events

Abstract

Techniques for determining network paths for voice calls include analyzing network path measurements of the network paths to determine historical network performance data for the network paths, and identifying a group of top-k network paths based on those network paths having better network performance data other network paths. A particular network path may be selected using various techniques, such as selecting the network path with the best historical network performance, selecting a network path by applying a multi-armed bandit algorithm to select the path from the group of top-k network paths, or selecting a network path at random. The selected network path may be used to by a source-destination pair of computing devices for a voice call, and a record of that voice call may be used to update network performance information for the particular network path.

Claims

1. A system comprising:

one or more processors; and

memory communicatively coupled to the one or more processors and storing one or more modules that, when executed by the one or more processors, cause the system to perform operations comprising;

receiving, from a source computing device, a request to transmit, via one or more networks, a call from the source computing device to a destination computing device;

analyzing, based at least in part on one or more network performance factors, network path measurements for a first plurality of network paths through one or more networks and between the source computing device and the destination computing device to determine network performance data for the first plurality of network paths;

determining, based at least in part on the network performance data for the first plurality of network paths, network performance data for a second plurality of network paths, the second plurality of network paths including the first plurality of network paths;

identifying, based at least in part on the network performance data, a network path from the second plurality of network paths to use for transmitting the call; and

outputting, to the source computing device, an indication of the network path identified for transmitting the call.

2. The system of claim 1, wherein the one or more network performance factors comprise at least one of:

round trip time using a particular network path;

data loss for a particular network path;

or

a measure of jitter in a signal caused by traversing a particular network path.

3. The system of claim 1, wherein determining the network performance data for the second plurality of network paths comprises:

selecting, based at least in part on the first plurality of network paths, one or more network models to model the one or more networks;

identifying, based at least in part on the one or more network models and the network path measurements, segment specific network performance data for segments of the first plurality of network paths;

determining, based at least in part on the one or more network models and the segments, additional network paths through the one or more networks; and

determining additional network performance data for the additional network paths.

4. The system of claim 1, wherein identifying the network path from the second plurality of network paths comprises:

identifying a group of network paths from the second plurality of network paths based at least in part on respective network performance data for each network path in the group of network paths relative to other network paths in the second plurality of network paths; and

selecting the network path from the group of network paths based at least in part on the network path having a highest network performance in the group of network paths.

5. The system of claim 1, wherein identifying the network path from the second plurality of network paths comprises:

identifying a group of network paths from the second plurality of network paths based at least in part on respective network performance data for each network path in the group of network paths relative to other network paths in the second plurality of network paths; and

selecting the network path from the group of network paths by applying a multi-armed bandit algorithm to the group of network paths.

6. The system of claim 1, wherein identifying the network path from the second plurality of network paths comprises:

identifying a group of network paths from the second plurality of network paths based at least in part on respective network performance data for each network path in the group of network paths relative to other network paths in the second plurality of network paths; and

selecting the network path randomly from the other network paths in the second plurality of network paths.

7. One or more computer-storage media storing computer-executable instructions that, when executed by one or more processors, configure the one or more processors to perform operations comprising:

analyzing, based at least in part on one or more network performance factors, records of voice communications made using a first plurality of network paths through one or more networks for a particular source-destination pair to determine network performance data for the first plurality of network paths;

identifying a network path from the first plurality of network paths or a second plurality of network paths based at least in part on network performance data of the network path relative to the network performance data of the first plurality of network paths and network performance data for the second plurality of network paths;

outputting an indication of the network path to a computing device.

8. The one or more computer-storage media of claim 7, the operations further comprising:

identifying, based at least in part on the network performance data for the first plurality of network paths, segment specific network performance data for segments of the first plurality of network paths;

selecting, based at least in part on the first plurality of network paths, one or more network models to model the one or more networks for the particular source-destination pair; and

determining, based at least in part on the one or more models and the segment specific network performance data for the segments of the first plurality of network paths, network performance data for the second plurality of network paths.

9. The one or more computer-storage media of claim 7, wherein identifying the network path comprises:

identifying a group of network paths from at least one of the first plurality of network paths or the second plurality of network paths based at least in part on respective network performance data for each network path in the group of network paths relative to network performance data of other network paths in the first plurality of network paths and the second plurality of network paths; and

selecting the network path from the group of network paths based at least in part on the network path having a highest network performance in the group of network paths.

10. The one or more computer-storage media of claim 7, wherein identifying the network path comprises:

identifying a group of network paths from at least one of the first plurality of network paths or the second plurality of network paths based at least in part on respective network performance data for each network path in the group of network paths relative to network performance data of other network paths in the first plurality of network paths and the second plurality of network paths; and

selecting the network path from the group of network paths by applying a multi-armed bandit algorithm to the group of network paths.

11. The one or more computer-storage media of claim 7, wherein identifying the network path comprises:

identifying a group of network paths from at least one of the first plurality of network paths or the second plurality of network paths based at least in part on respective network performance data for each network path in the group of network paths relative to network performance data of other network paths in the first plurality of network paths and the second plurality of network paths; and

selecting the network path randomly from the other network paths in the first plurality of network paths and the second plurality of network paths.

12. The one or more computer-storage media of claim 7, wherein the one or more network performance factors comprise at least one of:

an amount of time for a signal to be sent, using a particular network path, from a source computing device to a destination computing device of the source-destination pair plus an amount of time for an acknowledgment of the signal to be sent, using the particular network path, from the destination computing device to the source computing device;

a rate at which packets of a signal traversing a particular network path are lost with respect to at least one of time or an amount of packets sent in the signal;

or

a measure of jitter in a signal caused by traversing a particular network path.

13. The one or more computer-storage media of claim 7, wherein analyzing records of voice communications comprises:

identifying a source computing device and a destination computing device of the source-destination pair; and

identifying the first plurality of network paths based at least in part on the first plurality of network paths traversing a route between the source computing device and the destination computing device of the source-destination pair.

14. The one or more computer-storage media of claim 7, wherein identifying the network path from the first plurality of network paths or the second plurality of network paths comprises:

determining a first number of voice communications being relayed through a first network of the one or more networks, the first network comprising one or more relays;

determining whether the first number of voice communications exceeds a predefined cost threshold associated with the first network; and

in response to determining that the first number of voice communications does not exceed the predefined cost threshold, selecting the network path, the network path comprising a communication path through the first network.

15. A computer-implemented method comprising:

sending, via one or more network interfaces and to a controller server, a request to perform voice communication with a destination computing device via one or more networks;

receiving, from the controller server and via the one or more network interfaces, a message comprising an indication of one or more network paths between the computing device and the destination computing device and through the one or more networks, the message further comprising previous network performance data associated with each of the one or more network paths;

selecting, by one or more processors, a network path from the one or more network paths based at least in part on a respective previous network performance of the network path; and

sending, via the one or more network interfaces, a voice communication to the destination computing device using the network path.

16. The computer-implemented method of claim 15, wherein the message further comprises a suggested order to choose from the one or more network paths for performing the voice communication;

and

wherein selecting the network path from the one or more network paths is based at least in part on the suggested order.

17. The computer-implemented method of claim 15, wherein selecting the network path from the one or more network paths comprises:

identifying a group of network paths from the one or more network paths based at least in part on the previous network performance data of the group of network paths being higher than the previous network performance data for others of the one or more network paths; and

selecting the network path from the group of network paths based at least in part on the network path having a best previous network performance in the group of network paths.

18. The computer-implemented method of claim 15, wherein selecting the network path from the one or more network paths comprises:

identifying a group of network paths from the one or more network paths based at least in part on the previous network performance data of the group of network paths being higher than the previous network performance data for others of the one or more network paths; and

selecting the network path from the group of network paths by applying a multi-armed bandit algorithm to the group of network paths.

19. The computer-implemented method of claim 15, wherein selecting the network path from the one or more network paths comprises:

identifying a group of network paths from the one or more network paths based at least in part on the previous network performance data of the group of network paths being higher than the previous network performance data for the remaining network paths of the one or more network paths; and

selecting the network path randomly from the remaining network paths.

20. The computer-implemented method of claim 15, the operations further comprising sending a record of the voice communication performed using the network path to the controller server, the record including network performance information.