Multi-path routing

• US 9,860,159 B1
• Filed: 09/22/2015
• Issued: 01/02/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): Scheibel, Robert C
• Application Number:
  US14/861,940
• Time in Patent Office: 833 Days
• Field of Search: None
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• 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 first client device, a plurality of user datagram protocol (“

UDP”

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

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

receiving, by the first client device, information from the source device, the information responsive to receipt of the at least one probing packet along each of the plurality of UDP flows;

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

selecting, by the first client device, a UDP flow from the prioritized plurality of UDP flows;

transmitting, by the first client device, information that identifies the selected UDP flow;

obtaining, by a plurality of additional client devices, the transmitted information that identifies the selected UDP flow, wherein the plurality of additional client devices do not determine a selected UDP flow; and

transmitting, by the plurality of additional client devices, data communications via the selected UDP flow.

2. The method as recited in claim 1 further comprising:

determining, by the first client device, that an event has occurred;

in response to the determination,

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

receiving, by the first client device, information from the source device, the information responsive to the receipt of the at least one additional transmitted probing packet along each of the plurality of UDP flows;

re-prioritizing, by the first client device, the plurality of UDP flows based, at least in part, on the information from the source device; and

selecting, by the first client device, an updated UDP flow from the prioritized plurality of UDP flows.

3. The method as recited in claim 2 further comprising transmitting, by the first client device, the selected updated UDP flow to the plurality of additional client devices.

4. The method as recited in claim 2, wherein the event corresponds to a threshold amount of time that has expired.

5. The method as recited in claim 2, wherein the event corresponds to a threshold amount of data that has been transmitted.

6. A system comprising:

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

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

UDP”

) flows;

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

dynamically select a UDP flow from the plurality of established UDP flows based on the received information; and

transmit information that identifies the selected UDP flow to one or more additional computing devices, wherein the one or more additional computing devices are configured to select a UDP flow based at least in part on the transmitted information.

7. The system as recited in claim 6, wherein the first computing device is further configured with processor-executable instructions to establish the plurality of UDP flows with a target device.

8. The system as recited in claim 6, wherein each of the plurality of 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 first computing device is further configured to prioritize the plurality of UDP flows based, at least in part, on the information from the target device.

10. The system as recited in claim 6, wherein the first computing device is further configured with processor-executable instructions to transmit the information from the target device to the one or more additional computing devices.

11. The system as recited in claim 6, wherein the first computing device is further configured with processor-executable instructions to transmit the selected UDP flow to a publication service.

12. The system as recited in claim 6, wherein the first computing device is further configured with processor-executable instructions to:

determine an event has occurred;

in response to the determination,

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

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

select an updated UDP flow from the plurality of UDP flows based on the received information; and

transmit the updated UDP flow.

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

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

15. A system comprising:

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

transmit at least one data communication along a plurality of established data flows, wherein each flow is defined by a set of network addresses, a transmission port and a protocol specification;

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

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

transmit information that identifies the selected data flow for distribution to a plurality of additional computing devices associated with the first computing device, wherein the plurality of additional computing devices are not configured to independently select a data flow.

16. The system as recited in claim 15, wherein the first computing device is further configured with processor-executable instructions to establish 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 first computing device is further configured with processor-executable instructions to transmit the selected data flows to the plurality of additional computing devices.

19. The system as recited in claim 15, wherein the first computing device is further configured with processor-executable instructions to transmit the selected data flows to a publication service.

20. The system as recited in claim 15, wherein the first computing device is further configured with processor-executable instructions to:

determine a refresh event has occurred;

in response to the determination,

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

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

select an updated data flow from the plurality of data flows based on the additional information; and

transmit the selected updated data flow.

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

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