Overlay network

• US 8,599,697 B2
• Filed: 05/30/2011
• Issued: 12/03/2013
• Est. Priority Date: 06/18/1999
• Status: Expired due to Term

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Ricciulli, Livio
• Primary Examiner(s): MARCELO, MELVIN C
• Application Number:
  US13/118,569
• Publication Number:
  US 20110228678A1
• Time in Patent Office: 918 Days
• Field of Search: 370/238, 370/248, 370/252, 709/239
• US Class Current: 370/238
• 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, operable in a network comprising a plurality of nodes, at least two of said plurality of nodes each having at least a corresponding overlay module, the method comprising:

by a first overlay module at a source device, querying the overlay modules at each of the plurality of nodes for costs associated with transmitting a message to each of the plurality of nodes;

comparing the costs associated with transmitting the message to each of the plurality of nodes to determine an optimal node to which to transmit the message; and

addressing the message to the optimal node thereby causing, at least in part, the source device to transmit the message to the optimal node.

2. A method as recited in claim 1, wherein the source device comprises a gateway node communicatively connected to a client computer that generated the message.

3. A method as recited in claim 2, wherein the source device comprises a router.

4. A method as recited in claim 1, wherein the source device is colocated with a client computer that generated the message.

5. A method as recited in claim 4, wherein the message is one of a plurality of messages comprising data packets, and wherein the querying, comparing and addressing acts are performed after a first plurality of messages have been transmitted to at least one of the plurality of nodes, the first plurality of messages not including the message.

6. A method as recited in claim 4, wherein the source device comprises a router.

7. A method as recited in claim 1, wherein the addressing act comprises inserting a network identifier of the optimal node into a header associated with the message.

8. A method as recited in claim 7, further comprising:

prior to the addressing act, configuring a table at the source device to include the identifier of the optimal node.

9. A method as recited in claim 1, wherein the message comprises a control packet.

10. A method as recited in claim 1, wherein the message comprises a data packet.

11. A method as recited in claim 1, wherein an overlay forwarding path comprises the optimal node.

12. A method as recited in claim 1, wherein the querying act comprises:

sending at least one test packet to each of the at least some of the plurality of overlay modules at the nodes; and

awaiting a reply responsive to each test packet sent to the at least some of the plurality of overlay modules at nodes.

13. A method as recited in claim 1, wherein each of the plurality of nodes comprises a router.

14. A method as recited in claim 1, wherein the message is intended for delivery to a server.

15. A method, operable in a network comprising a plurality of nodes represented by a network address, at least two of said plurality of nodes each having at least a corresponding overlay module, the method comprising:

by a first overlay module at a source device, querying the overlay modules at each of a plurality of nodes for costs associated with transmitting a message to each of the plurality of nodes;

comparing the costs associated with transmitting the message to each of the plurality of nodes to determine an optimal node to which to transmit the message; and

inserting a network identifier of the optimal node into a header associated with the message thereby causing, at least in part, the source device to transmit the message to the optimal node.

16. A method as recited in claim 15, wherein the source device comprises a gateway node communicatively connected to a client computer that generated the message.

17. A method as recited in claim 16, wherein the source device comprises a router.

18. A method as recited in claim 15, wherein the source device is colocated with a client computer that generated the message.

19. A method as recited in claim 18, wherein the message is one of a plurality of messages comprising data packets, and wherein the querying, comparing and addressing acts are performed after a first plurality of messages have been transmitted to at least one of the plurality of nodes, the first plurality of messages not including the message.

20. A method as recited in claim 15, wherein the network comprises the Internet and the network identifier comprises an Internet Protocol address.

21. A method as recited in claim 15, wherein the querying act comprises:

sending at least one test packet to each of the at least some of the plurality of overlay modules at the nodes; and

awaiting a reply responsive to each test packet sent to the at least some of the plurality of overlay modules at nodes.

22. A method as recited in claim 15, wherein each of the plurality of nodes comprises a router.

23. A method as recited in claim 15, wherein the message is intended for delivery to a server.

24. A method for selecting a transmission path from a plurality of transmission paths in a network, wherein each of the plurality of transmission paths comprises at least one of a plurality of nodes, and wherein at least one overlay module is located at each of the plurality of nodes, the method comprising:

by a first overlay module at a source device, querying the overlay modules at each of a plurality of nodes for costs associated with transmitting a message from the source device via each of the plurality of transmission paths;

comparing the costs associated with transmitting the message via each of the plurality of transmission paths to determine an optimal transmission path for transmission of the message; and

addressing the message to a node on the optimal path thereby causing, at least in part, the source device to transmit the message to the optimal transmission path.

25. A method as recited in claim 24, wherein the addressing act comprises inserting a network identifier of the node on the optimal path into a header associated with the message.

26. A method as recited in claim 24, wherein the source device comprises a gateway node communicatively connected to a client computer that generated the message.

27. A method as recited in claim 26, wherein the source device comprises a router.

28. A method as recited in claim 24, wherein the source device is colocated with a client computer that generated the message.

29. A method as recited in claim 28, wherein the message is one of a plurality of messages comprising data packets, and wherein the querying, comparing and addressing acts are performed after a first plurality of messages have been transmitted to a transmission path other than the optimal path, the first plurality of messages not including the message.

30. A method as recited in claim 25, wherein the network comprises the Internet and the network identifier comprises an Internet Protocol address.

31. A method as recited in claim 24, wherein the querying act comprises:

sending at least one test packet to each of the at least some of the plurality of overlay modules at the nodes; and

awaiting a reply responsive to each test packet sent to the at least some of the plurality of overlay modules at nodes.

32. A method as recited in claim 24, wherein each of the plurality of nodes comprises a router.

33. A method as recited in claim 24, wherein the message is intended for delivery to a server.

34. A method, operable in a network comprising a plurality of nodes, including a first node having a first overlay module and a second node having a second overlay module, the method comprising:

an overlay module at a source device querying the first overlay module for a first cost associated with transmitting a message on a first path comprising the first node;

the overlay module at the source device querying the second overlay module for a second cost associated with transmitting the message on a second path comprising the second node;

determining that the second path is the optimal path based at least in part on comparing the first cost and the second cost; and

addressing the message to the second node thereby causing, at least in part, the source device to transmit the message to the optimal path.

35. A method as recited in claim 34, wherein the addressing act comprises inserting a network identifier of the second node into a header associated with the message.

36. A method as recited in claim 35, wherein the first path is a default path and the second path is an alternate path.

37. A method as recited in claim 34, wherein the network comprises the Internet and the network identifier comprises an Internet Protocol address.

38. A method as recited in claim 37, wherein the first path is a default path and the second path is an alternate path.

39. A method as recited in claim 34, wherein the source device comprises a gateway node communicatively connected to a client computer that generated the message.

40. A method as recited in claim 39, wherein the source device comprises a router.

41. A method as recited in claim 34, wherein the source device is colocated with a client computer that generated the message.

42. A method as recited in claim 41, wherein the message is one of a plurality of messages comprising data packets, and wherein the querying, determining and addressing acts are performed after a first plurality of messages have been transmitted to the first path, the first plurality of messages not including the message.

43. A method, operable in a network comprising a plurality of nodes, wherein N nodes of said plurality of nodes each have a corresponding overlay module associated therewith, N>

=2, the method comprising;

an overlay module at a source device querying at least M overlay modules of said N nodes, where M<

=N, to ascertain at least M costs associated with transmitting a message from the source device to a destination device via each of at least M nodes;

determining an optimal node from said M nodes based at least in part on the M costs; and

addressing the message to the optimal node thereby causing, at least in part, the source device to transmit the message to the optimal node.

44. A method as recited in claim 43, wherein the addressing act comprises inserting a network identifier of the optimal node into a header associated with the message.

45. A method as recited in claim 44, wherein the network comprises the Internet and the network identifier comprises an Internet Protocol address.

46. An overlay network comprising:

at least one overlay module at each of a plurality of Internet nodes;

a first overlay module at a source device, wherein the first overlay module is operable to;

query the overlay modules at each of the plurality of Internet nodes for costs associated with transmitting a message to each of the plurality of Internet nodes; and

compare the costs associated with transmitting the message to each of the plurality of Internet nodes to determine an optimal Internet node to which to transmit the message; and

address the message to the optimal Internet node thereby causing, at least in part, the source device to transmit the message to the optimal Internet node.

47. An overlay network as recited in claim 46, wherein the first overlay module addresses message to the optimal Internet node by inserting a network identifier of the optimal Internet node into a header associated with the message.