Multi-path routing

Patent metadata

Field	Value
Publication number	US-10623306-B2
Application number	US-201816056360-A
Country	US
Kind code	B2
Filing date	Aug 6, 2018
Priority date	Sep 22, 2015
Publication date	Apr 14, 2020
Grant date	Apr 14, 2020

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 computer-implemented method 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 associated with a different network path, and 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;
transmitting, by the client device, at least one probing packet along each UDP flow of the first plurality of UDP flows;
receiving, by the client device, information from the source device, the information responsive to receipt of the transmitted at least one probing packet along at least one UDP flow of the first plurality of UDP flows;
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 from the first prioritized plurality of UDP flows;
transmitting, by the client device, data communications utilizing the first UDP flow and the network path associated with the first UDP flow;
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 associated with a different network path, and 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;
transmitting, by the source device, at least one probing packet along each UDP flow of the second plurality of established UDP flows;
receiving, by the source device, information from the client device, the information responsive to the receipt of the transmitted at least one probing packet along at least one UDP flow of the second plurality of UDP flows;
generating, by the source device, a second prioritized plurality of UDP flows based, at least in part, on the information from the client device;
selecting, by the source device, a second UDP flow from the second prioritized plurality of UDP flows; and
transmitting, by the source device, data communications utilizing the second UDP flow and the associated network path.

2. The computer-implemented method of claim 1 further comprising:
in response to determining that a refresh event has occurred:
transmitting, by the client device, at least one additional probing packet along each UDP flow of the first plurality of UDP flows;
receiving, by the client device, additional information from the source device, the additional information responsive to receipt of the transmitted at least one additional probing packet along at least one UDP flow of the first plurality of UDP flows;
updating, by the client device, the first prioritized plurality of UDP flows based, at least in part, on the additional information from the source device;
selecting, by the client device, an updated UDP flow from the first prioritized plurality of UDP flows; and
transmitting, by the client device, data communications utilizing the updated UDP flow and the network path associated with the updated UDP flow.

3. The computer-implemented method of claim 2 , wherein determining that the refresh event has occurred comprises determining, by the client device, that a threshold amount of time has elapsed since the client device transmitted the at least one probing packet.

4. The computer-implemented method of claim 2 , wherein determining that the refresh event has occurred comprises determining, by the client device, that a threshold amount of data communications has been transmitted utilizing the first UDP flow.

5. The computer-implemented method of claim 2 , wherein determining that the refresh event has occurred comprises determining, by the client device, that a threshold number of failure events have occurred since the client device began transmitting data communications utilizing the first UDP flow.

6. The computer-implemented method of claim 1 further comprising publishing, by the client device, information regarding the first prioritized plurality of UDP flows to a network traffic management service.

7. A system comprising:
a first computing device comprising one or more processors configured with processor-executable instructions to perform operations including:
establishing a first user datagram protocol (“UDP”) flow associated with a first network path, wherein the first UDP flow is defined by a first set of network addresses, a first transmission port, and a first protocol specification;
establishing a second UDP flow associated with a second network path, wherein the second UDP flow is defined by a second set of network addresses, a second transmission port, and a second protocol specification;
transmitting a first probing packet along the first UDP flow associated with the first network path;
transmitting a second probing packet along the second UDP flow associated with the second network path;
receiving information from a target device, the information responsive to processing at least one probing packet by the target device;
generating a prioritization of the first and second UDP flows based, at least in part, on the information responsive to processing the at least one probing packet;
selecting a UDP flow from among the first and second UDP flows based at least in part on the prioritization; and
transmitting data communications along the selected UDP flow and the associated network path.

8. The system of claim 7 , wherein the one or more processors are configured with processor-executable instructions to perform further operations including establishing the first and second UDP flows with the target device.

9. The system of claim 7 , wherein the one or more processors are configured with processor-executable instructions to perform further operations to generate the prioritization of the first and second UDP flows based at least in part on one or more of a length of the data communication, a type of the data communication, a security protocol, a reliability of the first UDP flow, or a reliability of the second UDP flow.

10. The system of claim 7 , wherein the first and second UDP flows are selected from a plurality of UDP flows based at least in part on a latency of each of the first and second UDP flows.

11. The system of claim 10 , wherein the latency of the first UDP flow is determined based at least in part on a current latency and one or more previously measured latencies.

12. The system of claim 7 , wherein the first probing packet includes one or more of a packet identifier, computing device identifier, or communication type identifier.

13. A system comprising:
a computing device comprising one or more processors configured with processor-executable instructions to perform operations including:
establishing a first data flow associated with a first network path, wherein the first data flow is defined by a first set of network addresses, a first transmission port, and a first protocol specification;
establishing a second data flow associated with a second network path, wherein the second data flow is defined by a second set of network addresses, a second transmission port, and a second protocol specification;
transmitting a first probing packet via the first data flow;
transmitting a second probing packet via the second data flow;
receiving information from a target device, the information responsive to the processing of at least one probing packet by the target device and associated with measurements of latency;
generating a prioritization of the first and second

Assignees

• Amazon Tech Inc

Inventors

• Burns Nathan Lee
• Wang Bin
• Heath Scott Wright

Classifications

• H04L47/805

  QOS or priority aware · CPC title

• H04L43/12

  Network monitoring probes · CPC title

• H04L47/12

  Avoiding congestion; Recovering from congestion · CPC title

• H04L45/24 Primary

  Multipath · CPC title

• H04L43/10

  Active monitoring, e.g. heartbeat, ping or trace-route · CPC title