On-demand overlay routing for computer-based communication networks

• US 6,778,502 B2
• Filed: 07/27/2001
• Issued: 08/17/2004
• Est. Priority Date: 06/18/1999
• Status: Expired due to Term

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Savvis, Inc. (Lumen Technologies, Inc.)
• Inventors: Ricciulli, Livio
• Primary Examiner(s): MARCELO, MELVIN C
• Application Number:
  US09/916,628
• Publication Number:
  US 20020018449A1
• Time in Patent Office: 1,117 Days
• Field of Search: 370/238, 370/248, 370/252
• 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 of sending a packet from a source to a destination on a communications network by employing one or more existing communications protocols on the communications network, the method comprising:

finding that the cost of data transmission along a default path from the source to the destination is greater than the cost of data transmission along an alternate path from the source to destination using one or more nodes not on the default path, wherein the default path is derived by the one or more existing communications protocols of the communications network; and

changing a destination address in a destination field of the packet from that specified by the one or more existing communications protocols, in a maimer that causes the packet to travel through along the alternate path, bypassing the default path, while being transmitted on the communications network using the existing communications protocols.

2. The method of claim 1, further comprising specifying the address of the destination in the packet.

3. The method of claim 2, wherein the address of the destination is specified by encapsulating the packet.

4. The method of claim 1, wherein changing the destination address comprises changing the destination address in the destination field of the packet from that of the destination to that of a node on the alternate path.

5. The method of claim 1, wherein the destination address of the destination field of the packet is changed at multiple points along the alternate path to identify successive downstream nodes on the alternative path.

6. The method of claim 1, wherein the existing communications protocol is IP and the IP destination address of the packet is changed.

7. The method of claim 1, wherein nodes of the alternate path comprise a subset of all nodes on an overlay network that resides on top of the communications network.

8. The method of claim 7, further comprising identifying the alternate path among the nodes of the overlay network.

9. The method of claim 7, wherein the overlay network includes a set of computer systems co-located at Internet sites.

10. The method of claim 9, wherein the Internet sites are ISP locations.

11. The method of claim 9, wherein the computer systems are PCs.

12. The method of claim 1, further comprising notifying nodes of the alternate path that they are on the alternate path.

13. The method of claim 1, wherein the cost of data transmission along at least one of the default and the alternate paths is determined from one or more metrics selected from the following group:

delay, bandwidth, jitter, loss, security.

14. An apparatus comprising hardware configured to perform a method of sending a packet from a source to a destination on a communications network by employing one or more existing communications protocols on the communications network, the apparatus being configured to perform the following:

finding that the cost of data transmission along a default path from the source to the destination is greater than the cost of data transmission along an alternate path from the source to destination using one or more nodes not on the default path, wherein the default path is derived by the one or more existing communications protocols of the communications network; and

changing a destination address in a destination field of the packet from that specified by the one or more existing communications protocols, in a manner that causes the packet to travel through along the alternate path, bypassing the default path, while being transmitted on the communications network using the existing communications protocols.

15. The apparatus of claim 14, further configured to specify the address of the destination in the in the packet.

16. The apparatus of claim 15, wherein apparatus is configured to specify the address of the destination by encapsulating the packet.

17. The apparatus of claim 14, wherein changing the destination address comprises changing the destination address in the destination field of the packet from that of the destination to that of a node on the alternate path.

18. The apparatus of claim 14, wherein the existing communications protocol is IP and wherein the apparatus is configured to change the IP destination address.

19. The apparatus of claim 14, further configured to identify the alternate path among the nodes of an overlay network.

20. The apparatus of claim 14, wherein the apparatus is a computer system co-located at an Internet site.

21. The apparatus of claim 20, wherein the Internet site is an ISP location.

22. The apparatus of claim 14, further configured to notify nodes of the alternate path that they are on the alternate path.

23. The apparatus of claim 14, wherein the cost of data transmission along at least one of the default and the alternate paths is determined from one or more metrics selected from the following group:

delay, bandwidth, jitter, loss, security.

24. The apparatus of claim 14, wherein the cost of data transmission along at least one of the default and the alternate paths is determined by a node on the alternate path and wherein the apparatus is configured to receive said cost from said node.

25. The apparatus of claim 14, wherein the apparatus is configured to serve as at least one of an intermediate node or a client.

26. An apparatus comprising one or more software modules for performing a method of sending a packet from a source to a destination on a communications network by employing one or more existing communications protocols on the communications network, the software-implemented method comprising:

finding that the cost of data transmission along a default path from the source to the destination is greater than the cost of data transmission along an alternate path from the source to destination using one or more nodes not on the default path, wherein the default path is derived by the one or more existing communications protocols of the communications network; and

changing a destination address in a destination field of the packet from that specified by the one or more existing communications protocols, in a manner that causes the packet to travel through along the alternate path, bypassing the default path, while being transmitted on the communications network using the existing communications protocols.

27. The apparatus of claim 26, the software specifies, when executing, the address of the destination in the in the packet.

28. The apparatus of claim 27, wherein the software specifies, when executing, the address of the destination by encapsulating the packet.

29. The apparatus of claim 26, wherein changing the destination address comprises changing the destination address in the destination field of the packet from that of the destination to that of a node on the alternate path.

30. The apparatus of claim 26, wherein the existing communications protocol is IP and wherein the software changes the IP destination address, when executing.

31. The apparatus of claim 26, wherein the software comprises a component for identifying the alternate path among the nodes of an overlay network, when executing.

32. The apparatus of claim 26, wherein the apparatus is a computer system co-located at an Internet site.

33. The apparatus of claim 26, software comprises a component to notify nodes of the alternate path that they are on the alternate path.

34. A method for selecting a route in a network, the method comprising:

receiving data associated with a request for content at a first intermediate server, the data transmitted from an end user to the first intermediate server;

identifying a first cost of transmission along a default route from the first intermediate server to a content server, the default route determined using one or more existing Internet Protocol routing mechanisms;

identifying a second cost of transmission along an alternate route from the first intermediate server to the content server, the alternate route including a second intermediate server not in the default route, wherein the second intermediate server is part of an overlay network;

determining an optimal route based at least in part on the first cost and the second cost, wherein the first cost and the second cost are determined using network communication performance metrics; and

transmitting data associated with the request for content along the optimal route.

35. The method of claim 34, wherein network communication performance metrics are obtained periodically.

36. The method of claim 35, wherein the cost of transmission is determined using one or more network communication performance metrics selected from the following group:

delay, bandwidth, jitter, loss, security.

37. The method of claim 34, wherein the alternate route comprises one or more overlay nodes.

38. The method of claim 37, wherein the one or more overlay nodes define a virtual topology.