LINK SELECTION IN AN OVERLAY NETWORK

1 . An overlay network system comprising:

a plurality point-of-presence (POP) devices;

each POP comprising a path finding component and corresponding telemetry component, agent component, and routing daemon;

each telemetry component generating latency measurements for the POP on which it is disposed;

a centralized billboard service providing border gateway protocol (BGP) announcements and point-of-presence (POP) peering decisions to each of the agent components; and

on each of the POPs, the path finding component and corresponding telemetry component, agent component, and routing daemon cooperating to transform the BGP announcements, peering decisions, and latency measurements into routing tables and link selections for packet streams routed through the POPs.

2 . The system of claim 1 , further comprising a graph service configured to generate routing path updates to the billboard service.

3 . The system of claim 2 , wherein the graph service receives the telemetry measurements from the telemetry components.

4 . The system of claim 2 , further comprising:

the graph service generating a plurality of profiles; and

the path finding components utilizing the profiles to determine how the telemetry latency measurements should be weighted for selection of links between the POPs.

5 . The system of claim 4 , wherein a first type of the profiles emphasizes selection of lower latency links over lower jitter or loss links, and a second type of the profiles emphasizes the selection of the lower jitter or loss links over the lower latency links.

6 . The system of claim 5 , wherein a third type of the profiles emphasizes selection of links comprising a best combination of latency, jitter, and packet loss such that the links comprise low latency with acceptable jitter or loss.

7 . The system of claim 5 , wherein one or more of the profiles imposes geographical constraints on selection of the links by the path finding components.

8 . The system of claim 1 , wherein the agent components each independently poll the billboard service for the BGP announcements and peering decisions at regular intervals.

9 . The system of claim 8 , wherein the agents generate control templates for the routing daemons based on the BGP state information and peering decisions and apply the templates to the routing daemons.

10 . The system of claim 9 , wherein the control templates are configuration files.

11 . The system of claim 8 , wherein, in the event the billboard service becomes unresponsive to the polling by the agent components, the routing daemons continue to execute as routers utilizing the last polling updates received from the billboard service.

12 . The system of claim 1 , the billboard service implementing a traffic drain to enable a shifting of network traffic away from particular ones of the POP devices.

13 . The system of claim 12 , wherein the traffic drain comprises:

a command to shift all inbound traffic away from a particular one of the POP devices;

a command to shift all inbound traffic away from a specific peer device of a particular one of the POP devices;

a command to shift a specific type of inbound traffic away from a particular one of the POP devices; and

a command to shift a specific type of inbound traffic away from a specific peer device of a particular one of the POP devices.

14 . The system of claim 1 , wherein the path finding services make egress link selections between the POPs.

15 . The system of claim 1 , wherein each of the routing daemons comprises multiple independent routing tables, each synchronized to a kernel routing table of the POP on which the routing daemon is disposed.

16 . The system of claim 15 , further comprising filters that control which routes are synchronized to the kernel routing tables.

17 . The system of claim 1 , wherein the routing daemons are Bird routers.

18 . The system of claim 1 , wherein one or more of the telemetry components and the path finding components are configured to:

(i) maintain a loss count for a packet flow;

(ii) for each data packet sequence number (seq_i):

(a) on condition that a previous sequence number (seq_i−1) is present, then measure passive-round-trip-time[seq_i]=timestamp_value[seq_i]-timestamp_value[seq_i−1];

(b) on condition that the previous sequence number (seq_i−1) is missing, increment a loss counter for the packet flow.

19 . A method comprising:

determining a new weight for a current link for traffic between network devices for a combination of traffic dimensions;

setting current best dimensions for the current link to the combination of traffic dimensions;

setting a current best weight for the current link to the new weight on condition that there is no current best weight for the combination of dimensions;

setting the current best weight to the new weight and updating the current best dimensions on condition that the new weight is better than the current best weight;

making no changes to the current best weight or current best dimensions on condition that the new weight is worse than the current best weight and the combination of dimensions for the new weight do not match a combination of dimensions used to calculate the current best weight; and

selecting a new link to be the current link for the traffic between the network devices on condition that the new weight is worse than the current best weight, and the dimensions of the new weight and the current best weight match.

20 . A method comprising:

maintaining a loss count for a packet flow;

for each data packet sequence number (seq_i):

measuring passive-round-trip-time[seq_i]=timestamp_value[seq_i]-timestamp_value[seq_i−1] on condition that a previous sequence number (seq_i−1) is present; and

incrementing a loss counter for the packet flow on condition that the previous sequence number (seq_i−1) is missing.