Multi-path routing

Patent metadata

Field	Value
Publication number	US-9825846-B1
Application number	US-201514861895-A
Country	US
Kind code	B1
Filing date	Sep 22, 2015
Priority date	Sep 22, 2015
Publication date	Nov 21, 2017
Grant date	Nov 21, 2017

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.

First claim

What is claimed is:

1. A method for managing real time communications comprising:
establishing, by a set of gateway devices, a plurality of user datagram protocol (“UDP”) flows between a client device and a target device via network paths defined by the set of gateway devices, wherein each UDP flow is defined by a set of network addresses, a transmission port, and a protocol specification;
for the network paths defined by the set of gateway devices,
monitoring, by the set of gateway devices, transmission of at least one probing packet along each of the plurality of UDP flows;
receiving, by the set of gateway devices, information responsive to the receipt of the at least one probing packet along each of the plurality of UDP flows;
prioritizing, by the set of gateway devices, the plurality of UDP flows based, at least in part, on the information responsive to the receipt of the at least one probing packet along each of the plurality of UDP flows;
selecting, by the set of gateway devices, a UDP flow from the prioritized plurality of UDP flows; and
causing data communications between the client device and the target device to utilize the selected UDP flow.

2. The method of claim 1 further comprising:
determining, by the set of gateway devices, that a threshold time has expired;
in response to the determination, for the network paths defined by the set of gateway devices:
transmitting at least one probing packet along the plurality of established UDP flows;
receiving information responsive to receipt of the transmitted probing packet;
prioritizing the plurality of UDP flows based at least in part on the information responsive to the receipt of the transmitted probing packet;
selecting a UDP flow from the prioritized plurality of UDP flows; and
transmitting data communications utilizing the selected UDP flow.

3. The method as recited in claim 1 further comprising:
determining, by at least one gateway device of the set of gateway devices, that a threshold amount of data has been transmitted;
in response to the determination,
transmitting, by the set of gateway devices, at least one additional probing packet along the plurality of established UDP flows;
receiving, by the set of gateway devices, information responsive to receipt of the at least one additional probing packet;
re-prioritizing, by the set of gateway devices, the plurality of UDP flows based, at least in part, on the information responsive to the receipt of the at least one additional probing packet;
selecting, by the set of gateway devices, an updated UDP flow from the prioritized plurality of UDP flows; and
causing data communications between the client device and the target device to utilize the selected updated UDP flow.

4. The method as recited in claim 1 further comprising re-prioritizing the plurality of UDP flows based, at least in part, on updated network information.

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

6. A system comprising:
a first computing device comprising one or more processors configured with processor-executable instructions to perform operations comprising establishing real time communications with a second computing device; and
a set of intermediate computing devices in a network comprising one or more processors configured with processor-executable instructions to perform operations comprising:
monitor transmission of at least one data communication along each of a plurality of established user datagram protocol (“UDP”) flows between the first computing device and the second computing device;
receive information from at least one of the first computing device or the second computing device, the information responsive to the processing of the data communication; and
dynamically select a UDP flow from the plurality of UDP flows based on the received information, the selected UDP flow for transmitting real time communications between the first and second computing devices.

7. The system as recited in claim 6 , wherein the set of intermediate computing devices is further configured with processor-executable instructions to establish the plurality of UDP flows between the first and second computing devices.

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

9. The system as recited in claim 6 , wherein the set of intermediate computing devices is further configured to prioritize the plurality of UDP flows based, at least in part, on the information from at least one of the first computing device and the second computing device.

10. The system as recited in claim 6 , wherein the first computing device corresponds to a client device.

11. The system as recited in claim 6 , wherein the second computing device is one of a server device or a peer computing device.

12. The system as recited in claim 6 , wherein the set of intermediate computing devices 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 a plurality of established UDP flows;
receive information responsive to the processing of the additional data communication by at least one of the first computing device or the second computing device; and
select an updated UDP flow from the plurality of UDP flows based on the received information.

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. The system as recited in claim 12 , wherein the event corresponds to a determination of network packet loss.

16. The system as recited in claim 12 , wherein the set of intermediate computing devices is further configured to transmit a reservation of a selected UDP flow to a data flow service.

17. A system comprising:
a set of intermediate devices in a network comprising one or more processors configured with processor-executable instructions to perform operations comprising:
monitor transmission of 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 and wherein each flow defines a network path between two target computing devices;
receive information from a first target computing device of the two target computing devices, the information responsive to the processing of the data communication by the first target computing device; and
select a data flow from the established plurality of data flows based on the received information.

18. The system as recited in claim 17 , wherein the set of intermediate computing devices is further configured with processor-executable instructions to establish the plurality of data flows with the target computing device.

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

20. The system as recited in claim 17 , wherein the set of intermediate computing devices is further configured with processor-executable instructions to transmit additional data communications via the selected data flow.

21. The system as recited in

Assignees

• Amazon Tech Inc

Inventors

• Burns Nathan Lee
• Wang Bin
• Heath Scott Wright

Classifications

• H04L43/0829

  Packet loss · CPC title

• H04L45/24 Primary

  Multipath · CPC title

• H04L47/805

  QOS or priority aware · CPC title

• H04L69/16

  Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP] · CPC title

• H04L47/2458

  Modification of priorities while in transit · CPC title