Dynamic link state routing protocol

• US 10,554,538 B2
• Filed: 09/12/2017
• Issued: 02/04/2020
• Est. Priority Date: 09/12/2017
• Status: Active Grant

• Current Assignee: ADARA Networks, Inc.
• Original Assignee: ADARA Networks, Inc.
• Inventors: Spohn, Marcelo, Gangi, Raghu
• Primary Examiner(s): Weidner, Timothy J
• Application Number:
  US15/702,583
• Publication Number:
  US 20190081884A1
• Time in Patent Office: 875 Days
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 43/0858 One way delays
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/103 with adaptive polling, i.e. dynamically adapting the polling rate
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 43/20 the monitoring system or the monitored elements being virtualised, abstracted or software-defined entities, e.g. SDN or NFV
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838

Abstract

A router and methods for routing packets in a network are described. The router and methods are implemented with a dynamic link state routing protocol (DLSP). The router dynamically computes a best path from one or more paths by periodically probing links of peer nodes to determine link metrics associated with a link. The one or more link metrics include a link bandwidth to a peer node and a link latency to the peer node. Further, the router can dynamically recalculate the one or more link metrics associated with the link every 10 seconds. The router can also monitor one or more link state changes based on the one or more link metrics, wherein the link state changes are monitored every 60 second. The router can further determine a single link metric based on the link bandwidth to the peer node and the link latency to the peer node.

Claims

1. A method for routing packets on a network, comprising:

dynamically computing a best path from one or more paths by periodically probing links of peer nodes to determine one or more link metrics associated with a link, wherein the one or more link metrics include a link bandwidth to a peer node and a link latency to the peer node, wherein the best path from the one or more paths is dynamically computed using the link bandwidth to the peer node and the link latency to the peer node;

receiving a request to authenticate and encrypt one or more packets transmitted along the link, wherein the one or more packets are transmitted from a first node to a second node;

authenticating and encrypting the one or more packets based on an index and a shared key located in the one or more packets, wherein the index and the shared key are both periodically changed, and wherein the one or more packets are not authenticated and encrypted when the request is not authorized; and

opening the link for routing the one or more packets between the first node and the second node, wherein the link is associated with the one or more paths in the network.

2. The method of claim 1, wherein the link bandwidth to the peer node further includes at least one of a maximum bandwidth and an available bandwidth.

3. The method of claim 1, wherein the one or more link metrics further include at least one of an error rate, a load ratio, a path cost, and a path hop.

4. The method of claim 1, wherein the link latency further includes at least one of a ping transmission, a synchronization transmission, and a running average time between nodes.

5. The method of claim 4, wherein the ping transmission further comprises measuring a first timestamp indicating when an initial packet is transmitted to a peer node;

and measuring a second timestamp indicating when the initial packet is received by the peer node.

6. The method of claim 5, wherein the running average time between the nodes is determined by adding the first timestamp and the second timestamp, and then dividing the added first and second timestamps in half.

7. The method of claim 4, wherein the synchronization transmission further comprises

dynamically computing a one-way latency to the peer node by sending out a single latency probe that has a first timestamp;

determining a second timestamp of an incoming packet from the peer node, wherein the peer node sends the incoming packet in response to the single latency probe; and

determining the one-way latency to the peer node based on the first timestamp and the second timestamp.

8. The method of claim 1, wherein each of the peer nodes includes at least one of a kernel, a ring buffer, and a forwarding engine.

9. The method of claim 8, wherein the forwarding engine receives one or more notifications including a total number of available paths, a plurality of reachable networks, and one or more router addresses associated with one or more incoming packets.

10. The method of claim 1, wherein each of the peer nodes includes one or more information tables, and wherein the one or more information tables include at least one of an interface table, a load distribution table, and an anchor table.

11. The method of claim 1, wherein each of the peer nodes includes one or more configurable policies, including a priority-based policy, a path latency policy, a path bandwidth policy, a path bandwidth and latency policy, and a path capacity policy.

12. The method of claim 1, wherein each of the peer nodes is associated with at least one or more sessions used to transmit packets between nodes.

13. The method of claim 12, wherein each of the sessions is mapped to a given path based on one or more session policies.

14. The method of claim 13, wherein the one or more session policies further comprise using a full bandwidth prior to sending the packets in the session;

selecting a least congested path to transmit the packets in the session;

sending one more additional packets over an expected flow;

determining whether a congestion threshold is reached; and

mapping a second session for a second-best path when the threshold is reached.

15. The method of claim 12, wherein each session is embedded with information that frequently changes the index and the shared key in a predetermined time interval, and wherein the embedded information synchronizes each of the nodes in the session by identifying an authorized shared key from a plurality of shared keys based on an index timestamp.

16. The method of claim 1, wherein an initial long packet train is used to determine the best path, and wherein the long packet train establishes the best path based on an inter-packet gap time between the nodes and a total number of packets received by the nodes.

17. A method for routing packets on a network, comprising:

dynamically computing a best path from one or more paths by periodically probing links of peer nodes to determine one or more link metrics associated with a link, wherein the one or more link metrics include a link bandwidth to a peer node and a link latency to the peer node, wherein the best path from the one or more paths is dynamically computed using the link bandwidth to the peer node and the link latency to the peer node

dynamically recalculating the one or more link metrics associated with the link every 10 seconds;

monitoring one or more link state changes based on the one or more link metrics, wherein the link state changes are monitored every 60 seconds; and

determining a single link metric based on the link bandwidth to the peer node and the link latency to the peer node.

18. A router for routing packets on a multipath network, comprising:

a memory; and

a processing unit coupled to the memory, wherein the processing unit;

determines one or more links associated with one or more paths, wherein each of the one or more links transmits one or more packets between peer nodes;

dynamically computes a best path from the one or more paths by periodically probing the one or more links of the peer nodes; and

determines one or more link metrics associated with each of the one or more probed links, wherein the one or more link metrics include a link bandwidth to a peer node and a link latency to the peer node, wherein the best path from the one or more paths is dynamically computed using the link bandwidth to the peer node and the link latency to the peer node, wherein a request is received to authenticate and encrypt one or more packets transmitted along the link, wherein the one or more packets are transmitted from a first node to a second node;

the one or more packets are authenticated and encrypted based on an index and a shared key located in the one or more packets, wherein the index and the shared key are both periodically changed, and wherein the one or more packets are not authenticated and encrypted when the request is not authorized; and

the link for routing the one or more packets is opened between the first node and the second node, wherein the link is associated with the one or more paths in the network.

19. The router of claim 18, wherein the link bandwidth to the peer node further includes at least one of a maximum bandwidth and an available bandwidth.

20. The router of claim 18, wherein the one or more link metrics further include at least one of an error rate, a load ratio, a path cost, and a path hop.

21. The router of claim 18, wherein the link latency further includes at least one of a ping transmission, a synchronization transmission, and a running average time between nodes.

22. The router of claim 21, wherein the ping transmission further comprises measuring a first timestamp indicating when an initial packet is transmitted to a peer node;

and measuring a second timestamp indicating when the initial packet is received by the peer node.

23. The router of claim 22, wherein the running average time between the nodes is determined by adding the first timestamp and the second timestamp, and then dividing the added first and second timestamps in half.

24. The router of claim 21, wherein the synchronization transmission further comprises:

a one-way latency to the peer node that is dynamically computed by sending out a single latency probe that has a first timestamp;

a second timestamp of an incoming packet that is determined from the peer node, wherein the peer node sends the incoming packet in response to the single latency probe; and

the one-way latency to the peer node is determined based on the first timestamp and the second timestamp.

25. The router of claim 18, wherein each of the peer nodes includes at least one of a kernel, a ring buffer, and a forwarding engine.

26. The router of claim 25, wherein the forwarding engine receives one or more notifications including a total number of available paths, a plurality of reachable networks, and one or more router addresses associated with one or more incoming packets.

27. The router of claim 18, wherein each of the peer nodes includes one or more information tables, and wherein the one or more information tables include at least one of an interface table, a load distribution table, and an anchor table.

28. The router of claim 18, wherein each of the peer nodes includes one or more configurable policies, including a priority-based policy, a path latency policy, a path bandwidth policy, a path bandwidth and latency policy, and a path capacity policy.

29. The router of claim 18, wherein each of the peer nodes is associated with at least one or more sessions used to transmit packets between nodes.

30. The router of claim 29, wherein each of the sessions is mapped to a given path based on one or more session policies.

31. The router of claim 30, wherein the one or more session policies further comprise using a full bandwidth prior to sending the packets in the session;

selecting a least congested path to transmit the packets in the session;

sending one more additional packets over an expected flow;

determining whether a congestion threshold is reached; and

mapping a second session for a second-best path when the threshold is reached.

32. The router of claim 29, wherein each session is embedded with information that frequently changes the index and the shared key in a predetermined time interval, and wherein the embedded information synchronizes each of the nodes in the session by identifying an authorized shared key from a plurality of shared keys based on an index timestamp.

33. The router of claim 18, wherein an initial long packet train is used to determine the best path, and wherein the long packet train establishes the best path based on an inter-packet gap time between the nodes and a total number of packets received by the nodes.

34. A router for routing packets on a multipath network, comprising:

a memory; and

a processing unit coupled to the memory, wherein the processing unit;

determines one or more links associated with one or more paths, wherein each of the one or more links transmits one or more packets between peer nodes;

dynamically computes a best path from the one or more paths by periodically probing the one or more links of the peer nodes; and

determines one or more link metrics associated with each of the one or more probed links, wherein the one or more link metrics include a link bandwidth to a peer node and a link latency to the peer node, wherein the best path from the one or more paths is dynamically computed using the link bandwidth to the peer node and the link latency to the peer node, wherein

the one or more link metrics associated with the link are dynamically recalculated every 10 seconds;

one or more link state changes are monitored based on the one or more link metrics, wherein the link state changes are monitored every 60 seconds; and

a single link metric is determined based on the link bandwidth to the peer node and the link latency to the peer node.

35. A method for routing packets on a multipath network, comprising:

determining one or more links associated with one or more paths, wherein each of the one or more links transmits one or more packets between peer nodes;

dynamically computing a best path from the one or more paths by periodically probing the one or more links of the peer nodes; and

determining one or more link metrics associated with each of the one or more probed links, wherein the one or more link metrics include a link bandwidth to a peer node and a link latency to the peer node, wherein the best path from the one or more paths is dynamically computed using the link bandwidth to the peer node and the link latency to the peer node,

receiving a request to authenticate and encrypt one or more packets transmitted along the link, wherein the one or more packets are transmitted from a first node to a second node;

authenticating and encrypting the one or more packets based on an index and a shared key located in the one or more packets, wherein the index and the shared key are both periodically changed, and wherein the one or more packets are not authenticated and encrypted when the request is not authorized; and

opening the link for routing the one or more packets between the first node and the second node, wherein the link is associated with the one or more paths in the network.

36. The method of claim 35, wherein the link bandwidth to the peer node further includes at least one of a maximum bandwidth and an available bandwidth;

and wherein the one or more link metrics further include at least one of an error rate, a load ratio, a path cost, and a path hop.

37. A method for routing packets on a multipath network, comprising:

determining one or more links associated with one or more paths, wherein each of the one or more links transmits one or more packets between peer nodes;

dynamically computing a best path from the one or more paths by periodically probing the one or more links of the peer nodes; and

determining one or more link metrics associated with each of the one or more probed links, wherein the one or more link metrics include a link bandwidth to a peer node and a link latency to the peer node, wherein the best path from the one or more paths is dynamically computed using the link bandwidth to the peer node and the link latency to the peer node;

dynamically recalculating the one or more link metrics associated with the link every 10 seconds;

monitoring one or more link state changes based on the one or more link metrics, wherein the link state changes are monitored every 60 seconds; and

determining a single link metric based on the link bandwidth to the peer node and the link latency to the peer node.