Method for intelligent multi-hop overlay routing

Patent metadata

Field	Value
Publication number	US-10666548-B2
Application number	US-201816126855-A
Country	US
Kind code	B2
Filing date	Sep 10, 2018
Priority date	Sep 10, 2018
Publication date	May 26, 2020
Grant date	May 26, 2020

Abstract

Systems and methods are presented herewith for selecting a preferred route for routing a packet from a first network node to a second network node. A set of possible routes is maintained, with each route having am associated weight value. A random subset of routes is then selected based on the weight values. Each route of the subset is then probed to determine its gain value. The preferred route is selected based on the gain values (e.g., by selecting the highest gain value). Then, all weight values are updated based on the respective gain values. The steps are periodically repeated. Then, whenever a packet needs to be routed, the route currently designated as preferred is used.

First claim

What is claimed is:

1. A method for identifying a preferred route for a packet from a first network node to a second network node, the method comprising:
(a) maintaining, by control circuitry, a set of possible routes from the first network node to the second network node, wherein each possible route has an associated weight value;
(b) randomly selecting by the control circuitry, a subset of routes from the set of possible routes based on the respective associated weight value of each possible route;
(c) determining, by the control circuitry, a gain value for each route of the subset of routes, wherein the determining comprises:
sending a probe packet from the first network node to the second network node via the respective route;
calculating a latency value based on a set of timestamps in the probe packet, wherein each timestamp in the set of timestamps corresponds to an arrival time of the probe packet at a respective hop along the respective route; and
determining the gain value for the respective route based on the calculated latency value;
(d) designating, by the control circuitry, a route of the subset of routes as a preferred route based on comparing the determined gain values;
(e) updating, by the control circuitry, each weight value associated with each respective probed route based on the respective determined gain value;
(f) periodically repeating operations (b)-(e) by the control circuitry;
(g) receiving, by the control circuitry, a request, at the first network node, at a given time, to route the packet to the second network node; and
(h) in response to receiving the request, routing, by the control circuitry, the packet along the route designated, at the given time, as the preferred route.

2. The method of claim 1 , further comprising:
including a last used route from the first network node to the second network node into the subset of routes; and
including an Internet Protocol (IP) route from the first network node to the second network node into the subset of routes.

3. The method of claim 1 , further comprising:
probing, by the control circuitry, each route from the subset of routes to determine a bandwidth value for each probed route; and
designating, by the control circuitry, a route of the subset of routes that has a highest bandwidth value as the preferred route.

4. The method of claim 3 , wherein determining the bandwidth value for each probed route comprises:
sending, by the control circuitry, two packets back-to-back from the first network node to the second network node via the particular probed route;
calculating, by the control circuitry a dispersion value by measuring a rate at which a first packet and a second packet of the two packets are received at the second network node; and
calculating, by the control circuitry, the bandwidth value based on the dispersion value.

5. The method of claim 1 , wherein routing the packet along the preferred route designated at the given time, as the preferred route, comprises:
modifying, by the control circuitry, the packet to include an overlay routing header; and
routing, by the control circuitry, the packed based on data of the overlay routing header.

6. The method of claim 5 , further comprising:
populating, by the control circuitry, the overlay routing header to include an address for each hop of the preferred route; and
routing, by the control circuitry, the packet to each address identified by the overlay routing header.

7. The method of claim 1 , further comprising:
initializing, by the control circuitry, each associated weight value for each possible route based on a length of the respective route; and
normalizing, by the control circuitry, the associated weight values.

8. The method of claim 1 , wherein updating each weight value associated with a particular probed route comprises:
calculating, by the control circuitry, a ratio value by dividing the determined gain of the particular probed route by the weight value associated with the particular probed route;
calculating, by the control circuitry, a natural exponent of the ratio value; and
multiplying, by the control circuitry, the natural exponent by the current weight value to calculate an updated weight value.

9. The method of claim 1 , wherein the first network node and the second network node are nodes of a software defined wide area network.

10. A system for identifying a preferred route for a packet from a first network node to a second network node, the system comprising:
storage circuitry for storing instructions for operating the system; and
communication circuitry configured to transmit and receive packets;
control circuitry configured to:
(a) maintain a set of possible routes from the first network node to the second network node, wherein each possible route has an associated weight value;
(b) randomly select a subset of routes from the set of possible routes based on the respective associated weight value of each possible route;
(c) determine a gain value for each route of the subset of routes, wherein to determine the gain value, the control circuitry is configured to:
send a probe packet from the first network node to the second network node via the respective route;
calculate a latency value based on a set of timestamps in the probe packet, wherein each timestamp in the set of timestamps corresponds to an arrival time of the probe packet at a respective hop along the respective route; and
determine the gain value for the respective route based on the calculated latency value;
(d) designate a route of the subset of routes as a preferred route based on comparing the determined gain values; and
(e) update each weight value associated with each respective probed route based on the respective determined gain value.

11. The system of claim 10 , wherein the control circuitry is further configured to:
include a last used route from the first network node to the second network node into the subset of routes; and
include an Internet Protocol (IP) route from the first network node to the second network node into the subset of routes.

12. The system of claim 10 , wherein the control circuitry is further configured to:
probe each route from the subset of routes to determine a bandwidth value for each probed route; and
designate a route of the subset of routes that has a highest bandwidth value as the preferred route.

13. The system of claim 12 , wherein to determine the bandwidth value for each probed route, the control circuitry is further configured to:
send two packets back-to-back from the first network node to the second network node via the particular probed route;
calculate a dispersion value by measuring the rate at which a first packet and a second packet of the two packets are received at the second network node; and
calculate the bandwidth value based on the dispersion value.

14. The system of claim 10 , wherein to route the packet along the preferred route designated, at the given time, as the preferred route, the control circuitry is further configured to:
modify the packet to include an overlay routing header; and
route the packed based on data of the overlay routing header.

15. The system of claim 14 , wherein the control circuitry is further configured to:
populate the overlay routing header to include an address for each hop of the preferred route; and
route the packet to each address identified by the overlay routing header.

16. The system of claim 10 , wherein the control circuitry is further configured to:
initialize each associated weight value for each possible route b

Assignees

• Extreme Networks Inc

Inventors

• Bernardi Giacomo
• Nispel Markus

Classifications

• H04L43/50

  Testing arrangements · CPC title

• H04L45/124 Primary

  using a combination of metrics · CPC title

• H04L43/0876

  Network utilisation, e.g. volume of load or congestion level · CPC title

• H04L43/0894

  Packet rate · CPC title

• H04L43/0852

  Delays · CPC title