On-demand overlay routing for computer-based communication networks

• US 6,473,405 B2
• Filed: 06/25/2001
• Issued: 10/29/2002
• Est. Priority Date: 06/18/1999
• Status: Expired due to Term

• Current Assignee: Sandpiper CDN, LLC (Theseus LF Asset Holdings, LLC)
• Original Assignee: Digital Impact Incorporated (Liberty Latin America Ltd.)
• Inventors: Ricciulli, Livio
• Primary Examiner(s): MARCELO, MELVIN C
• Application Number:
  US09/888,966
• Publication Number:
  US 20010037409A1
• Time in Patent Office: 491 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 for selecting a path from a dynamic router to a destination, the method comprising:

selecting a default path for transmitting data from a dynamic router to a destination by using one or more existing routing mechanisms of a communications network;

receiving real-time traffic information, wherein receiving real-time traffic information is distinct from deriving paths using one or more existing routing mechanisms;

characterizing real-time traffic information to obtain a first cost associated with an alternative path for transmitting data to the destination;

providing an indication that a received packet having a source field and a destination field should be transmitted to the destination by using the alternative path when the first cost is less than a second cost associated the default path, wherein disregarding the selection of the default path allows the path from a dynamic router to the destination to be dynamically selected in a network where the destination field in the received packet is used by nodes in the default and alternative paths to forward the received packet toward the destination.

2. The method of claim 1, further comprising transmitting a data packet received at the dynamic router along the alternative path.

3. The method of claim 1, wherein the alternate path comprises an overlay node.

4. A computer readable medium comprising computer code for selecting a path from a dynamic router to a destination, the computer readable medium comprising:

computer code for selecting a default path for transmitting data from a dynamic router to a destination by using one or more existing routing mechanisms of a communications network;

computer code for receiving real-time traffic information, wherein receiving real-time traffic information is distinct from deriving paths using one or more existing routing mechanisms;

computer code for characterizing real-time traffic information to obtain a first cost associated with an alternative path for transmitting data to the destination;

computer code for providing an indication that a received packet having a source field and a destination field should be transmitted to the destination by using the alternative path when the first cost is less than a second cost associated the default path, wherein disregarding the selection of the default path allows the path from a dynamic router to the destination to be dynamically selected in a network where the destination field in the received packet is used by nodes in the default and alternative paths to forward the received packet toward the destination.

5. The computer readable medium of claim 4, further comprising computer code for transmitting a data packet received at the dynamic router along the alternative path.

6. The computer readable medium of claim 4, wherein the alternate path comprises an overlay node.

7. A method for transmitting data from a router to a destination, the method comprising:

designating a first neighboring router as the next hop for transmitting data from a router to a destination by one or more existing routing mechanisms of a communications network,

characterizing real-time traffic information to obtain a first cost associated with using a second neighboring router as the next hop to transmit data to the destination; and

designating the second neighboring router as the next hop for transmitting data to the destination when the first cost is less than the cost associated with using the first neighboring router as the next hop for transmitting data to the destination, wherein designating the second neighboring router allows transmission of a packet having a source field and a destination field to the destination using real-time traffic information in a network where the destination field in the received packet is used by nodes in the default and alternative paths to forward the received packet toward the destination.

8. The method of claim 7, wherein disregarding the designation of the first neighboring router as the next hop comprises ignoring a routing table entry associated with the destination.

9. The method of claim 7, wherein disregarding the designation of the first neighboring router as the next hop comprises modifying a routing table entry associated with the destination.

10. An apparatus for transmitting data from a router to a destination, the apparatus comprising:

means for designating a first neighboring router as the next hop for transmitting data from a router to a destination by using one or more existing routing mechanisms of a communications network,

means for characterizing real-time traffic information to obtain a first cost associated with using a second neighboring router as the next hop to transmit data to the destination; and

means for designating the second neighboring router as the next hop for transmitting data to the destination when the first cost is less than the cost associated with using the first neighboring router as the next hop for transmitting data to the destination, wherein designating the second neighboring router allows transmission of the packet to the destination using real-time traffic information in a network where the destination field in the received packet is used by nodes in the default and alternative paths to forward the received packet toward the destination.

11. The apparatus of claim 10, wherein disregarding the designation of the first neighboring router as the next hop comprises ignoring a routing table entry associated with the destination.

12. The apparatus of claim 10, wherein disregarding the designation of the first neighboring router as the next hop comprises modifying a routing table entry associated with the destination.