System and method for efficient wide area network routing

• US 20030079005A1
• Filed: 05/29/2001
• Published: 04/24/2003
• Est. Priority Date: 05/29/2001
• Status: Abandoned Application

• Current Assignee: 61C Networks Incorporated
• Original Assignee: 61C Networks Incorporated
• Inventors: Myers, Andrew C., Rochberg, David A., Placeway, Paul W.
• Application Number:
  US09/866,932
• Publication Number:
  US 20030079005A1
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/22 Alternate routing

Abstract

An overlay on a wide area network is disclosed. The wide area network includes at least one backbone network, and the overlay includes a processor coupled to the backbone network. The processor furthermore contains instructions which, when executed, cause the processor to optimize real time performance of data delivery from the processor to another processor on the wide area network. A method of optimizing at least two routes in a wide area network is also provided. The method includes optimizing a first route based on a first characteristic and optimizing a second route based on a second characteristic.

Claims

1. An overlay on a wide area network, wherein the wide area network includes at least one backbone network, comprising a processor coupled to the backbone network, wherein said processor contains instructions which, when executed by said processor, cause said processor to optimize real time performance of data delivery from the processor to another processor on the wide area network.

2. A method of selecting an optimum route from a first processor to a second processor in a wide area network and of selecting an optimum route from a third processor to a fourth processor in the wide area network, comprising:

selecting a first characteristic to be optimized in the route between the first processor and the second processor;

measuring the characteristic on a first route coupling the first processor to the second processor;

measuring the characteristic on a second route coupling the first processor to the second processor;

selecting from the first route and the second route, the route having the best performance based on the first characteristic;

selecting a second characteristic to be optimized in the route between the third processor and the fourth processor;

measuring the characteristic on a third route coupling the third processor to the fourth processor;

measuring the characteristic on a fourth route coupling the third processor to the fourth processor; and

selecting from the third route and the fourth route, the route having the best performance based on the second characteristic.

3. A method of optimizing at least two routes in a wide area network, comprising

optimizing a first route based on a first characteristic;

and

optimizing a second route based on a second characteristic.

4. The method of claim 3, wherein the characteristic is a performance criterion.

5. The method of claim 4, wherein the performance criterion is throughput and throughput is to be maximized.

6. The method of claim 4, wherein the performance criterion is latency and latency is to be minimized.

7. The method of claim 4, wherein the performance criterion is variation in throughput and variation in throughput is to be minimized.

8. The method of claim 4, wherein the performance criterion is variation in latency and variation in latency is to be minimized.

9. The method of claim 4, wherein the performance criterion is cost and cost is to be minimized.

10. The method of claim 4, wherein the performance criterion is network hop count and network hop count is to be minimized.

11. The method of claim 4, wherein the performance criterion is processor hop count and processor hop count is to be minimized.

12. The method of claim 3, wherein the characteristic is a combination of at least two performance criteria.

13. A method for coupling nodes of an overlay network on a wide area network, wherein the wide area network includes a plurality of component networks, comprising:

coupling a node to a first local area network near a first peering point of the first component network;

coupling a node to a second local area network near a first peering point of the second component network;

coupling a node to the first local area network near a second peering point of the first component network; and

coupling a node to a stub network.

14. A method for finding a route having optimum throughput on a computer network, comprising:

determining a size of a message sent along the route;

determining a delay time required to pass a small amount of data along the route;

determining a duration of time required to pass the message along the route; and

calculating throughput of the route from message size, delay time, and duration.

15. The method of claim 14, wherein determining a delay time, further comprises:

measuring a delay time for a plurality of data passes along the route;

calculating a mean absolute underestimated error for the plurality of delay time measurements; and

selecting a delay time that minimizes the mean absolute underestimated error.

16. The method of claim 14, wherein determining throughput, further comprises:

measuring a throughput for a plurality of data passes along the route; and

averaging the plurality of measured throughputs while weighting recent measurements more than earlier measurements.

17. A method of selecting an optimum route from a first processor to a second processor in a wide area network, comprising:

selecting a first characteristic to be optimized in the route between the first processor and the second processor;

measuring the characteristic on a first route coupling the first processor to the second processor;

measuring the characteristic on a second route coupling the first processor to the second processor;

selecting from the first route and the second route, the route having the best performance based on the first characteristic;

selecting a second characteristic to be optimized in the route between the first processor and the second processor;

measuring the characteristic on the first route coupling the first processor to the second processor;

measuring the characteristic on the second route coupling the first processor to the second processor; and

selecting from the first route and the second route, the route having the best performance based on the second characteristic.