System and Method for Assigning Paths for Data Flows Through a Wide-Area Network

• US 20140105023A1
• Filed: 12/13/2013
• Published: 04/17/2014
• Est. Priority Date: 08/13/2009
• Status: Abandoned Application

• Current Assignee: Google Inc. (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wu, Yuguang, Zhou, Junlan
• Application Number:
  US14/106,672
• Publication Number:
  US 20140105023A1
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/41 by acting on aggregated flows or links

Abstract

A method includes, receiving a plurality of data flows. A respective data flow includes a respective source address and a respective destination address. The method further includes generating, without regard to priorities associated with the plurality of data flows, an ordering of the plurality of data flows; and iteratively modifying, without regard to the priorities, the ordering of the plurality of data flows by applying a randomization algorithm to the plurality of data flows, until a cost associated with path assignments for the ordering of the plurality of data flows satisfies a predetermined condition. A respective path assignment for a respective data flow specifies a respective path from a respective source address to a respective destination address. The method also includes executing the data flows based on the path assignments for the ordering of the plurality of data flows having the cost that satisfies the predetermined condition.

Claims

1. A computer-implemented method for assigning paths for data flows through a wide-area network, comprising:

at a computer system including one or more processors and memory storing one or more programs, the one or more processors executing the one or more programs to perform the operations of;

receiving a plurality of data flows, wherein a respective data flow in the plurality of data flows and includes a respective source address and a respective destination address;

generating, without regard to priorities associated with the plurality of data flows, an ordering of the plurality of data flows;

iteratively modifying, without regard to the priorities, the ordering of the plurality of data flows by applying a randomization algorithm to the plurality of data flows, until a cost associated with path assignments for the ordering of the plurality of data flows satisfies a predetermined condition, wherein a respective path assignment for a respective data flow specifies a respective path from a respective source address to a respective destination address; and

executing the data flows based on the path assignments for the ordering of the plurality of data flows having the cost that satisfies the predetermined condition,

2. The method of claim 1, wherein the randomization technique is selected from one of:

a simulated annealing technique;

a genetic algorithm technique; and

a hill-climbing technique.

3. The method of claim 1, wherein the cost is calculated based on factors including one or more of:

a minimum remaining available bandwidth of any link in the network;

an average length of newly assigned paths; and

an average length of newly assigned paths and existing paths.

4. The method of claim 1, wherein the predetermined condition is selected from the group consisting of:

a predetermined number of iterations has been performed; and

a change in an improvement of the cost over a series of path assignments for the plurality of data flows is below a predetermined threshold.

5. The method of claim 1, wherein generating the ordering of the plurality of data flows includes generating a random ordering of the plurality of data flows.

6. The method of claim 1, wherein iteratively modifying the ordering of the plurality of data flows until the cost associated with path assignments for the ordering the plurality of data flows satisfies the predetermined condition includes:

performing the following operations until the cost associated with the path assignments for the ordering of the plurality of data flows satisfies the predetermined condition;

for each data flow in the ordering of the plurality of data flows, assigning a path from a source address of the data flow to a destination address of the data flow to produce a path assignment for the data flow, wherein the path assignments are made for the data flows in the order specified by the ordering of the plurality of data flows;

calculating the cost of the path assignments for the ordering of the plurality of data flows;

determining whether the cost of the path assignments for the ordering of the data flows satisfies the predetermined condition; and

if the cost of the path assignments for the ordering of the data flows does not satisfy the predetermined condition, modifying the ordering of the plurality of data flows.

7. The method of claim 6, wherein assigning the path from the source address of the data flow to the destination address of the data flow to produce the path assignment for the data flow includes:

determining a shortest path from the source address of the data flow to the destination address of the data flow based on an available bandwidth of the network;

assigning the shortest path as the path assignment for the data flow;

determining the bandwidth used for the shortest path; and

subtracting the bandwidth used for the shortest path from the available bandwidth of the network.

8. A computing system, comprising:

one or more processors;

memory; and

one or more programs stored in the memory, the one or more programs comprising instructions when executed cause the computing system to perform the operations of;

receiving a plurality of data flows, wherein a respective data flow in the plurality of data flows and includes a respective source address and a respective destination address;

generating, without regard to priorities associated with the plurality of data flows, an ordering of the plurality of data flows;

iteratively modifying, without regard to the priorities, the ordering of the plurality of data flows by applying a randomization algorithm to the plurality of data flows, until a cost associated with path assignments for the ordering of the plurality of data flows satisfies a predetermined condition, wherein a respective path assignment for a respective data flow specifies a respective path from a respective source address to a respective destination address; and

executing the data flows based on the path assignments for the ordering of the plurality of data flows having the cost that satisfies the predetermined condition

9. The system of claim 8, wherein the randomization technique is selected from one of:

a simulated annealing technique;

a genetic algorithm technique; and

a hill-climbing technique.

10. The system of claim 8, wherein the cost is calculated based on factors including one or more of:

a minimum remaining available bandwidth of any link in the network;

an average length of newly assigned paths; and

an average length of newly assigned paths and existing paths.

11. The system of claim 8, wherein the predetermined condition is selected from the group consisting of:

a predetermined number of iterations has been performed; and

a change in an improvement of the cost over a series of path assignments for the plurality of data flows is below a predetermined threshold.

12. The system of claim 8, wherein generating the ordering of the plurality of data flows includes generating a random ordering of the plurality of data flows.

13. The system of claim 8, wherein iteratively modifying the ordering of the plurality of data flows until the cost associated with path assignments for the ordering the plurality of data flows satisfies the predetermined condition includes:

performing the following operations until the cost associated with the path assignments for the ordering of the plurality of data flows satisfies the predetermined condition;

for each data flow in the ordering of the plurality of data flows, assigning a path from a source address of the data flow to a destination address of the data flow to produce a path assignment for the data flow, wherein the path assignments are made for the data flows in the order specified by the ordering of the plurality of data flows;

calculating the cost of the path assignments for the ordering of the plurality of data flows;

determining whether the cost of the path assignments for the ordering of the data flows satisfies the predetermined condition; and

if the cost of the path assignments for the ordering of the data flows does not satisfy the predetermined condition, modifying the ordering of the plurality of data flows.

14. The system of claim 8, wherein assigning the path from the source address of the data flow to the destination address of the data flow to produce the path assignment for the data flow includes:

determining a shortest path from the source address of the data flow to the destination address of the data flow based on an available bandwidth of the network;

assigning the shortest path as the path assignment for the data flow;

determining the bandwidth used for the shortest path; and

subtracting the bandwidth used for the shortest path from the available bandwidth of the network.

15. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computing system, the one or more programs comprising instructions which when executed cause the computing system to perform the operation of:

receiving a plurality of data flows, wherein a respective data flow in the plurality of data flows and includes a respective source address and a respective destination address;

generating, without regard to priorities associated with the plurality of data flows, an ordering of the plurality of data flows;

iteratively modifying, without regard to the priorities, the ordering of the plurality of data flows by applying a randomization algorithm to the plurality of data flows, until a cost associated with path assignments for the ordering of the plurality of data flows satisfies a predetermined condition, wherein a respective path assignment for a respective data flow specifies a respective path from a respective source address to a respective destination address; and

executing the data flows based on the path assignments for the ordering of the plurality of data flows having the cost that satisfies the predetermined condition,

16. The non-transitory computer readable storage medium of claim 15, wherein the randomization technique is selected from one of:

a simulated annealing technique;

a genetic algorithm technique; and

a hill-climbing technique.

17. The non-transitory computer readable storage medium of claim 15, wherein the cost is calculated based on factors including one or more of:

a minimum remaining available bandwidth of any link in the network;

an average length of newly assigned paths; and

an average length of newly assigned paths and existing paths.

18. The non-transitory computer readable storage medium of claim 15, wherein the predetermined condition is selected from the group consisting of:

a predetermined number of iterations has been performed; and

a change in an improvement of the cost over a series of path assignments for the plurality of data flows is below a predetermined threshold.

19. The non-transitory computer readable storage medium of claim 15, wherein generating the ordering of the plurality of data flows includes generating a random ordering of the plurality of data flows.

20. The non-transitory computer readable storage medium of claim 15, wherein assigning the path from the source address of the data flow to the destination address of the data flow to produce the path assignment for the data flow includes:

determining a shortest path from the source address of the data flow to the destination address of the data flow based on an available bandwidth of the network;

assigning the shortest path as the path assignment for the data flow;

determining the bandwidth used for the shortest path; and

subtracting the bandwidth used for the shortest path from the available bandwidth of the network.