Multi-path routing

• US 10,044,604 B1
• Filed: 09/22/2015
• Issued: 08/07/2018
• Est. Priority Date: 09/22/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Burns, Nathan Lee, Wang, Bin, Heath, Scott Wright
• Primary Examiner(s): Pham, Chi H
• Assistant Examiner(s): Rivas, Raul
• Application Number:
  US14/861,934
• Time in Patent Office: 1,050 Days
• Field of Search: None
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

Abstract

Systems and methods are provided for dynamically routing packets using multi-flow and multi-path multiplexing connections. A first computing device and second computing device communicate via a plurality of data flows, which may be routed across various network paths. Each flow is defined by a set of network addresses, a set of ports, and a protocol specification, such as UDP. The second device sends information to the first device regarding the various data flows. The first device may send probing packets to facilitate collecting data flow information. Information may include latency, packet loss, and other values. Based on the information received, the first device may select or prioritize data flows to mitigate congestion, and address performance criteria. The first device may also transmit information regarding selected data flows to other devices, allowing the other devices to utilize a selected data flow even if they lack multiplexing capability.

Claims

1. A method for managing real time communications comprising:

establishing, by a client device, a first plurality of user datagram protocol (“

UDP”

) flows with a source device, wherein each UDP flow of the first plurality of UDP flows is defined by a set of network addresses, a transmission port, and a protocol specification, and wherein each UDP flow of the first plurality of UDP flows is associated with a different network path;

transmitting, by the client device, at least one probing packet along the first plurality of UDP flows;

receiving, by the client device, information from the source device, the information responsive to receipt of the transmitted probing packet;

generating, by the client device, a first prioritized plurality of UDP flows based, at least in part, on the first plurality of UDP flows and the information from the source device;

selecting, by the client device, a first UDP flow and an associated first network path from the first prioritized plurality of UDP flows;

transmitting, by the client device;

data communications utilizing the first UDP flow and the first network path;

establishing, by the source device, a second plurality of UDP flows with the client device, wherein each UDP flow of the second plurality of UDP flows is defined by a set of network addresses, a transmission port and a protocol specification, and wherein each UDP flow of the second plurality of UDP flows is associated with a different network path;

transmitting, by the source device, at least one probing packet along each of the second plurality of UDP flows;

receiving, by the source device, information from the client device, the information responsive to receipt of the transmitted probing packet;

generating, by the source device, a second prioritized plurality of UDP flows based, at least in part, on the second plurality of UDP flows and the information from the source device;

selecting, by the source device, a second UDP flow and an associated second network path from the second prioritized plurality of UDP flows;

transmitting, by the source device, data communications utilizing the second UDP flow and the second network path;

determining, by the client device, that the data communications utilizing the first UDP flow and the first network path have satisfied a criterion;

in response to the determination,

transmitting, by the client device, at least one additional probing packet along the first plurality of established UDP flows;

receiving, by the client device, additional information from the source device, the additional information responsive to receipt of the at least one additional probing packet;

updating, by the client device, the first prioritized plurality of UDP flows based, at least in part, on the additional information;

selecting, by the client device, an updated UDP flow and an associated updated network path from the first prioritized plurality of UDP flows; and

transmitting, by the client device, data communications utilizing the updated UDP flow and the updated network path.

2. The method as recited in claim 1, wherein determining that the data communications utilizing the first UDP flow and the first network path have satisfied the criterion comprises determining that a threshold time has expired.

3. The method as recited in claim 1, wherein determining that the data communications utilizing the first UDP flow and the first network path have satisfied the criterion comprises determining that a threshold amount of data has been transmitted.

4. The method as recited in claim 1, wherein the probing packet includes an identifier.

5. The method as recited in claim 1, wherein the client device includes at least one browser application for transmitting data communications utilizing the first UDP flow.

6. A system comprising:

a computing device comprising one or more processors configured with processor-executable instructions to perform operations comprising;

transmitting at least one data communication along a plurality of established user datagram protocol (“

UDP”

) flows, wherein each of the plurality of established UDP flows is associated with a different network path;

receiving information from a target device, the information responsive to the processing of the data communication by the target device;

selecting a UDP flow and associated network path from the plurality of established UDP flows based on the information;

utilizing the selected UDP flow and network path to send additional data communication between a client device and the target device; and

in response to determining that the additional data communication between the client device and the target device have satisfied a criterion;

transmitting at least one additional data communication along the plurality of established UDP flows;

receiving additional information from the target device, the additional information responsive to processing of the additional data communication by the target device; and

selecting an updated UDP flow from the plurality of established UDP flows based on the additional information.

7. The system as recited in claim 6, wherein the operations further comprise establishing the plurality of established UDP flows with the target device.

8. The system as recited in claim 6, wherein the plurality of established UDP flows comprises a set of network addresses, a transmission port, and a specified protocol.

9. The system as recited in claim 6, wherein the operations further comprise prioritizing the plurality of established UDP flows based, at least in part, on the information from the target device.

10. The system as recited in claim 6, wherein the operations further comprise transmitting additional data communications via the selected UDP flow.

11. The system as recited in claim 6, wherein determining that the additional data communication between the client device and the target device have satisfied a criterion comprises determining that an event has occurred.

12. The system as recited in claim 11, wherein the event corresponds to an expiration of a threshold amount of time.

13. The system as recited in claim 11, wherein the event corresponds to exceeding a threshold amount of data transmitted via the selected UDP flow.

14. The system as recited in claim 6, wherein the operations further comprise:

transmitting at least one data communication along a second plurality of established UDP flows;

receiving information from the computing device, the information from the computing device responsive to the processing of the data communication by the computing device; and

selecting a UDP flow from the second plurality of established UDP flows based on the information from the computing device.

15. A system comprising:

a computing device comprising one or more processors configured with processor-executable instructions to perform operations comprising;

transmitting at least one data communication via a plurality of data flows, wherein each data flow of the plurality of data flows is defined by a set of network addresses, a transmission port, and a protocol specification, and wherein each data flow of the plurality of data flows is associated with a different network path;

receiving information from a target device, the information responsive to the processing of the data communication by the target device and associated with measurements of latencies of the data flows;

selecting a data flow from the plurality of data flows based on the received information; and

in response to determining that data communications via the selected data flow satisfy a criterion;

transmitting at least one additional data communication along a plurality of established data flows;

receiving additional information from the target device, the additional information responsive to the processing of the at least one additional data communication by the target device; and

selecting an updated data flow from the plurality of data flows based on the additional information.

16. The system as recited in claim 15, wherein the operations further comprise establishing the plurality of data flows with the target device.

17. The system as recited in claim 15, wherein the protocol specification corresponds to a user datagram protocol.

18. The system as recited in claim 15, wherein the operations further comprise prioritizing the plurality of data flows based, at least in part, on the information from the target device.

19. The system as recited in claim 15, wherein the operations further comprise transmitting additional data communications via the selected data flow.

20. The system as recited in claim 15, wherein determining that data communications via the selected data flow satisfy a criterion comprises determining that a refresh event has occurred.

21. The system as recited in claim 20, wherein the refresh event corresponds to an expiration of a threshold amount of time.

22. The system as recited in claim 20, wherein the refresh event corresponds to exceeding a threshold amount of data transmitted via the selected data flow.

23. The system as recited in claim 15, wherein the operations further comprise:

transmitting at least one data communication along a plurality of established data flows, wherein each of the established data flows is associated with a different network path;

receiving information from the computing device, the information responsive to the processing of the data communication by the computing device; and

selecting a UDP flow from the plurality of established data flows based on the information from the computing device.