On-demand overlay routing for computer-based communication networks

• US 6,275,470 B1
• Filed: 06/18/1999
• Issued: 08/14/2001
• Est. Priority Date: 06/18/1999
• Status: Expired due to Term

• Current Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Original Assignee: Digital Impact Incorporated (Liberty Latin America Ltd.)
• Inventors: Ricciulli, Livio
• Primary Examiner(s): MARCELO, MELVIN C
• Application Number:
  US09/336,487
• Time in Patent Office: 788 Days
• Field of Search: 370/238, 370/248, 370/252, 370/253, 370/352-356, 370/400
• 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 for determining an optimized path for transmitting a message from a source to a destination within a packet-switched computer-based communications network, the method comprising the following steps:

a) in response to a request to transmit the message, measuring a cost from the source to the destination along a default path, the default path being derived by means of one or more existing routing mechanisms of the communications network;

b) measuring an alternative cost of transmitting the message from the source to the destination along at least one alternative path, the alternative path passing through one or more intermediate nodes not on the default path, wherein the intermediate nodes define a virtual topology on top of the computer-based communications network;

c) determining the optimized path by comparing the default cost and the alternative cost.

2. The method of claim 1, wherein the steps of the method are performed in real-time in response to the request to transmit the message, and in a manner requiring no explicit interaction with any human user.

3. The method of claim 1, wherein the message is dynamically generated in response to a previous request received by the source from the destination.

4. The method of claim 1, wherein step (b) of measuring an alternative cost is only performed in the event that the default cost exceeds a specified threshold cost.

5. The method of claim 1, further including the following steps:

d) transmitting the message from the source to a first one of the one or more intermediate nodes, and

e) transmitting the message from a last one of the one or more intermediate nodes to the destination,

whereby the message is transmitted from the source to the destination by way of the optimized path.

6. The method of claim 5, wherein the first intermediate node and the last intermediate node are one in the same.

7. The method of claim 5, wherein the first intermediate node and the last intermediate node are not one in the same.

8. The method of claim 5, wherein one or more existing routing mechanisms of the communications network are utilized to perform steps (d) and (e).

9. The method of claim 8, wherein step (d) further includes the step of modifying the message so as to address the message to the first intermediate node, and so as to encapsulate an address of the destination within the message.

10. The method of claim 8, wherein step (e) further includes, in the event that the message requests a reply message, the step of modifying source address information for the message so as to replace an identification of the source with an identification of the last intermediate node.

11. The method of claim 1, further including the step of storing information about the optimized path in storage accessible to the one or more intermediate nodes.

12. The method of claim 11, wherein the step of storing information about the optimized path further includes storing, for each of the one or more intermediate nodes on the optimized path, a next address for forwarding the message.

13. The method of claim 1, wherein step (b) includes measuring a set of alternative costs for transmitting the message from the source to the destination, each such alternative cost corresponding to one of a plurality of alternative paths, each such alternative path passing through one or more intermediate nodes not on the default path;

and wherein step (c) further includes comparing the default cost and the set of alternative costs.

14. The method of claim 13, further including the steps of:

determining a pruned topology representing potentially optimizing connections between the intermediate nodes for use in the alternative paths, and

using the pruned topology to generate the plurality of alternative paths.

15. The method of claim 1, wherein the communications network is characterized by one or more established communications protocols, and wherein the method is performed without requiring modification of the established communications protocols.

16. The method of claim 15, wherein the established communications protocols include one or more protocols selected from the following group:

{Internet Protocol, http, ftp SSL,TCP}.

17. The method of claim 1, wherein the packet-switched communications network has a static topology.

18. The method of claim 1, wherein the packet-switched communications network has a dynamic topology.

19. The method of claim 1, wherein the default cost and the alternative cost are derived from one or more metrics selected from the following group:

{delay, bandwidth, jitter, loss, security}.

20. The method of claim 1, wherein the one or more intermediate nodes comprise computer hardware.

21. The method of claim 1, wherein the one or more intermediate nodes comprise computer software.

22. The method of claim 1, wherein the one or more intermediate nodes are operable to transmit and receive data in conformance with the established communications protocols.

23. The method of claim 22, wherein the one or more intermediate nodes are further operable to transmit and receive in conformance with protocols other than the established communications protocols.

24. A method for determining an optimized path for transmitting a message from a source to a destination within a computer-based communications network having a static topology, the method comprising the following steps:

a) in response to a request to transmit the message, measuring a cost from the source to the destination along a default path, the default path being derived by means of one or more existing routing mechanisms of the communications network;

b) measuring an alternative cost of transmitting the message from the source to the destination along at least one alternative path, the alternative path passing through one or more intermediate nodes not on the default path, wherein the intermediate nodes define a virtual topology on top of the computer-based communications network;

c) determining the optimized path by comparing the default cost and the alternative cost.

25. The method of claim 24, wherein the communications network is connectionoriented.

26. An overlay network apparatus for determining an optimized path for transmitting a message from a source to a destination within a packet-switched computer-based communications network, the communications network being characterized by one or more established communications protocols, the apparatus comprising:

a) a set of one or more intermediate nodes, the intermediate nodes being operable to transmit and receive data in conformance with the established communications protocols;

b) alternate path discovery means, responsive to a request for transmitting the message from the source to the destination, operable to discover an alternate path between the source and the destination passing through one or more of the intermediate nodes not on a default path, the default path being derived by means of one or more existing routing mechanisms of the communications network, wherein the intermediate nodes define a virtual topology on top of the computer-based communications network; and

c) forwarding means for forwarding the message from the source to the destination by way of the alternative path, without requiring a modification of the established communications protocols.

27. An apparatus for conducting an electronic commerce transaction between a first party and a second party, the first and second party being respectively connected to a computer-based communications network by way of a first and second network node, the communications network being characterized by one or more established communications protocols, the apparatus comprising:

a) a set of one or more intermediate nodes, the intermediate nodes being operable to transmit and receive data in conformance with the established communications protocols;

b) alternate path discovery means, responsive to a request to transmit a communication from the first node to the second node as a part of the electronic commerce transaction, said alternate path discovery means being operable to discover an alternate path between the first node and the second node passing through one or more of the intermediate nodes not on a default path, the default path being derived by means of one or more existing routing mechanisms of the communications network, wherein the intermediate nodes define a virtual topology on top of the computer-based communications network; and

c) forwarding means for forwarding the message from the first node to the second node by way of the alternative path, without requiring a modification of the established communications protocols.

28. A method for exchanging a message and a reply between a source and a destination within a computer-based communications network, wherein the network includes one or more existing routing mechanisms for deriving a default path for communication between multiple points on the network, the method comprising the following steps:

a) identifying one or more intermediate nodes that are not on the default path for communication between the source and the destination, the default path being derived by means of one or more existing routing mechanisms of the communications network, wherein the intermediate nodes define a virtual topology on top of the computer-based communications network;

b) transmitting the message from the source to a first one of the one or more intermediate nodes,

c) transmitting the message from a last one of the one or more intermediate nodes to the destination, and modifying source address information for the message so as to replace an identification of the source with an identification of the last intermediate node,

d) receiving, at the last intermediate node, the reply from the destination

e) transmitting the reply from the first intermediate node to the source,

whereby the message and the reply are exchanged between the source and the destination by way of a non-default communication path.

29. The method of claim 28, wherein one or more existing routing mechanisms of the communications network are utilized to perform steps (b), (c), (d), and (e);

wherein step (b) further includes modifying the message so as to encapsulate an address of the destination within the message; and

wherein step (e) further includes modifying the reply so as to encapsulate an address of the source within the message.

30. The method of claim 28, wherein the message and the reply are part of an electronic commerce transaction.

31. The method of claim 28, wherein the reply is dynamically generated.