On-demand overlay routing for computer-based communication networks

• US 7,953,888 B2
• Filed: 07/30/2003
• Issued: 05/31/2011
• Est. Priority Date: 06/18/1999
• Status: Expired due to Fees

• Current Assignee: Sandpiper CDN, LLC (Theseus LF Asset Holdings, LLC)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Ricciulli, Livio
• Primary Examiner(s): Bates; Kevin
• Assistant Examiner(s): NGUYEN, MINH CHAU
• Application Number:
  US10/630,559
• Publication Number:
  US 20040022194A1
• Time in Patent Office: 2,862 Days
• Field of Search: 709/241, 709/239
• US Class Current: 709/239
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application
• CPC Class Codes: H04L 45/64 using an overlay routing layer

Abstract

Methods and apparatus are disclosed for dynamically discovering and utilizing an optimized network path through overlay routing for the transmission of data. A determination whether to use a default network path or to instead use an alternate data forwarding path through one or more overlay nodes is based on real-time measurement of costs associated with the alternative paths, in response to a user request for transmission of message data to a destination on the network. Cost metrics include delay, throughput, jitter, loss, and security. The system chooses the best path among the default forwarding path and the multiple alternate forwarding paths, and implements appropriate control actions to force data transmission along the chosen path. No modification of established network communication protocols is required.

Claims

1. A method for transmitting content in a communications network, the method comprising:

(A) configuring a table to cause content to be routed over a first path in said communications network;

(B) comparing an elapsed time relative to the transmission of content via the first path against a threshold amount of time;

(C) based at least in part on the comparing step (B), when said elapsed time relative to the transmission of content via the first path exceeds the threshold amount of time, querying at least one overlay software module for one or more costs associated with one or more alternate paths;

(D) comparing the one or more costs associated with the one or more alternate paths and a cost associated with the first path;

(E) based at least in part on the comparing step (D), selecting the first path or an alternate path as an optimal path based at least in part on which path is associated with a lower cost; and

(F) modifying the table to cause content to be routed over the optimal path in said communications network; and

wherein the communications network comprises the Internet and wherein communication among nodes of the first path uses at least an Internet protocol, and communication among nodes of the one or more alternate paths uses at least the Internet protocol.

2. A method as recited in claim 1, wherein the first path is an overlay forwarding path.

3. A method as recited in claim 1, wherein the modifying step (F) comprises:

designating a neighboring node in the optimal path as a next hop.

4. A method as recited in claim 1, wherein a first network comprises the first path and a second network comprises the one or more alternate paths.

5. A node in a communications network, the node comprising:

a first port operable to receive content destined for a destination node in the communications network;

one or more output ports operable to transmit content to at least a first path in said communications network and a second path in said communications network;

an overlay software module operable to determine a first cost associated with the first path and a second cost associated with the second path; and

a table configurable to cause content received at the first port to be selectively transmitted from the one or more output ports to either the first path or the second path in response to instructions derived from;

(A) an analysis of an amount of elapsed time during which the table has been configured such that content has been transmitted from the one or more output ports to a current path and (B) a comparison of the first cost and the second cost; and

wherein the current path comprises the first path and, wherein the table is modifiable to cause content to be routed from the one or more output ports to the second path if the amount of elapsed time exceeds the threshold amount of time and the first cost is greater than the second cost; and

wherein the communications network comprises the Internet and wherein communication among nodes of the first path uses at least an Internet protocol, and communication among nodes of the second path uses at least the Internet protocol.

6. A node as recited in claim 5, wherein the first path is an overlay forwarding path.

7. A node as recited in claim 5, wherein the current path comprises the first path and, wherein the table is operable to be modified to designate a neighboring node in the second path as a next hop.

8. A node as recited in claim 5, wherein a first network comprises the first path and a second network comprises the second path.

9. A method for transmitting content in a communications network, wherein a table entry is configured to cause content to be transmitted via a first path in said communications network, the method comprising:

(A) comparing an elapsed time associated with transmitting content via the first path with a threshold amount of time;

(B) modifying the table to cause content to be transmitted via a second path in said communications network as a result of the comparing step when;

(i) the elapsed time associated with transmitting content via the first path exceeds the threshold amount of time; and

(ii) a first cost associated with the first path is greater than a second cost associated with the second path, wherein at least the second cost is determined by querying an overlay software module; and

wherein the communications network comprises the Internet and wherein communication among nodes of the first path uses at least an Internet protocol, and communication among nodes of the second path uses at least the Internet protocol.

10. A method as recited in claim 9, wherein a first network comprises the first path and a second network comprises the second path.

11. A method for transmitting content in a communications network, the method comprising:

(A) configuring a table to cause content be routed to a first path in said communications network;

(B) comparing an elapsed time associated with transmitting content via the first path against a threshold amount of time;

(C) modifying the table to cause content to be routed to a second path in said communications network when the elapsed time exceeds the threshold amount of time;

(D) subsequent to the modifying step (C), comparing a first cost associated with transmitting content via the second path against a threshold cost;

(E) if the first cost exceeds the threshold cost, querying at least one overlay software module for one or more costs associated with one or more alternate paths;

(F) comparing the first cost and the one or more costs associated with one or more alternate paths;

(G) based at least in part on the comparing step (F), selecting the second path or an alternate path as an optimal path based at least in part on which path is associated with a lower cost, and

(H) modifying the table to cause content to be routed to the optimal path; and

wherein the communications network comprises the Internet and wherein communication among nodes of the second path uses at least an Internet protocol, and communication among nodes of the one or more alternate paths uses at least the Internet protocol.

12. A method as recited in claim 11, wherein the threshold cost is based at least in part on a maximum elapsed time.

13. A method as recited in claim 11, wherein the threshold cost is based at least in part on a delay metric.

14. A method as recited in claim 11, wherein the threshold cost is based at least in part on a performance metric.

15. A method as recited in claim 11, wherein a first network comprises the first path and a second network comprises the second path.

16. A method for transmitting content in a communications network, the method comprising:

(A) configuring a table to cause content to be routed via a first path in said communications network, said first path having been determined based at least in part on a first cost associated with transmitting content via the first path; and

(B) in response to an elapsed time relative to said configuring in step (A) exceeding a threshold time, querying at least one overlay software module for one or more costs associated with one or more alternate paths;

(C) comparing the one or more costs associated with the one or more alternate paths and a second cost associated with the first path;

(D) based at least in part on the comparing step (C), selecting the first path or an alternate path as an optimal path based at least in part on which path is associated with a lower cost; and

(E) modifying the table to cause content to be routed via the optimal path in said communications network; and

wherein the communications network comprises the Internet and wherein communication among nodes of the first path uses at least an Internet protocol, and communication among nodes of the one or more alternate paths uses at least the Internet protocol.

17. A method as recited in claim 16, wherein the second cost and the one or more costs associated with the one or more alternate paths are based at least in part on the then-current state of the network.

18. A method as recited in claim 16, wherein the first path comprises at least one overlay node.

19. A method as recited in claim 16, wherein the one or more alternate paths comprises at least one overlay node.

20. A method for transmitting content in a communications network, the method comprising:

(A) configuring a table to cause content to be routed to a first node, a first network comprising said first node; and

then, in response to an elapsed amount of time relative to the configuring step (A) exceeding a threshold time,

(B) querying at least one overlay software module for one or more costs associated with one or more alternate nodes;

(C) comparing the one or more costs associated with the one or more alternate nodes and a cost associated with the first node;

(D) based at least in part on the comparing step (C), selecting the first node or an alternate node as a next hop based at least in part on which node is associated with a lower cost; and

(E) modifying the table to cause content to be routed to the next hop,

wherein the communications network comprises the Internet and wherein communication among nodes on the first network uses at least an Internet protocol, and communication among the one or more alternate nodes uses at least the Internet protocol; and

wherein a first overlay path comprises the first node and wherein a second overlay path comprises the one or more alternate nodes.