System and method for increasing the speed of distributed single and multi-commodity flow using second order methods

• US 6,377,544 B1
• Filed: 08/20/1998
• Issued: 04/23/2002
• Est. Priority Date: 08/20/1998
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Suel, Torsten, Muthukrishnan, Shanmugavelayut
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Tran, Maikhanh
• Application Number:
  US09/136,819
• Time in Patent Office: 1,342 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232-233, 370/235, 370/252-253, 370/412-414, 370/477
• US Class Current: 370/229
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/38 Flow based routing

Abstract

A system and method for increasing the speed of flow of a quantity of data or of a plurality of data types through a communication system. The communication system comprises a plurality of switches including a source and a sink, each of the switches connected to a neighboring switch by a communication link having a capacity, each of the links having a pair of queue buffers, and one queue buffer of each pair of queue buffers is located at each switch connected by a link. For a single data type, a flow is computed for each link as a function of a last previous amount of flow across the same link. In the multi-data type case, a weighted queue difference is computed as a function of a last previous amount of flow between the same pair of queues and an amount of flow f_i of said data type i is routed across each said link such that Σ_1≦i≦Kf_i (Δ′_i(e)−f_i) is maximized. In other embodiments of the invention, the system and method resolves the contention between different data types for the capacity of a communication link with and without a normalization factor, and adjusts flow so as not to exceed the capacity of a communication link or the amount of a data available to be routed by the sending queue buffer.

Claims

1. A method for directing the flow of a quantity of data through a communication system, said communication system comprising a plurality of switches including a source and a sink, each of said plurality of switches connected to a neighboring switch by a communication link having a capacity, each said link having a pair of queue buffers, one queue buffer of each said pair of queue buffers located at each said switch connected by said link, said method comprising:

(a) adding a flow of said data at said source;

(b) in each said switch, partitioning evenly among said queue buffers of said switch an amount of flow at said switch;

(c) computing an amount of flow to be routed across each said link as a function of a difference between the amount of data in each of said pair of queue buffers, and as a function of a previous amount of flow between said pair of queue buffers;

(d) routing an amount of flow of said data across each said link;

(e) removing said data from said sink; and

(f) repeating steps (a)-(e).

2. The method of claim 1, wherein said step of computing an amount of flow to be routed across each said link further comprises computing f=(β

)(Δ

(e)/2)+(β

−

1)(f′

), wherein f is said amount of flow to be routed between said pair of queues, Δ

(e) is a difference in the amounts of said data between said pair of queues,f′

is a previous amount of flow between said pair of queues, and β

is a numerical value.

3. The method of claim 2, wherein β

is a numerical value between 1.0 and 2.0.

4. The method of claim 2, wherein β

is varied as a function of time.

5. The method of claim 2, wherein β

is varied as a function of the number of iterations which have been performed by said switch.

6. The method of claim 1, further comprising, after said computing step, the step of adjusting said flow so as not to exceed said capacity of said link.

7. The method of claim 1, further comprising , after said computing step, the step of adjusting said flow so as not to exceed said amount of said data available to be routed by said queue buffer.

8. A method for directing the flow of a plurality of types of data through a communication system, said communication system comprising a plurality of switches including a source and a sink, each of said plurality of switches connected to a neighboring switch by a communication link having a capacity, each said link having a pair of queue buffers, one queue buffer of each said pair of queue buffers located at each said switch connected by said link, said method comprising:

(a) for each of said plurality of data type, adding an amount of flow of said data type at said source;

(b) in each said switch, partitioning evenly among said queue buffers of said switch an amount of flow of said data type at said switch;

(c) computing a weighted queue difference between said queue buffer of said switch and said queue buffer of each said neighboring switch, as a function of a difference between an amount of said data type in said queue buffer of said switch and an amount in said queue buffer of said neighboring switch, and as a function of a previous amount of flow routed between said pair of queue buffers;

(d) routing an amount of flow of each said data type across each said link, said routed amount of flow computed as a function of said weighted queue difference;

(e) removing said data type from said sink; and

(f) repeating steps (a)-(e).

9. The method of claim 8, wherein said weighted queue difference is Δ

_i′

(e)=(β

)(Δ

(e))+(2.0)(β

−

1)(f′

), wherein f′

is a last previous amount of flow between said pair of queue buffers, β

(e) is a difference in the amounts of said data type between said pair of queues, and β

is a value between 1.0 and 2.0.

10. The method of claim 8, wherein said products to be summed are further multiplied by a normalization factor, d_i⁻

2, wherein d_i is a demand of data type i.

11. The method of claim 8, further comprising, after said computing step, the step of adjusting said weighted queue difference if half of said weighted queue difference is greater than an amount of said data type available to be routed by said queue buffer.

12. The method of claim 8, further comprising, after said computing step, the step of adjusting said weighted queue difference so as not to exceed said capacity of said link.

13. The method of claim 8, wherein said amount of flow of each said data type to be routed across each said link is further computed such that the summation of the product of said flows multiplied by the difference between said weighted queue difference and said amount of flow is maximized.

14. The method of claim 8, further comprising resolving contentions between said plurality of data types for said capacity of said links by finding a marginal contribution factor, said marginal contribution factor corresponding to the derivative of each said flow of said data types, said marginal contribution factor comprising the smallest value at which the sum of said corresponding flows of said data types does not exceed said capacity of said links.

15. The method of claim 8, wherein said amounts of flow of each said data type i to be routed are such that Σ

<sub>1≦

i≦

K</sub>f_i(Δ

′

_i(e)−

f_i) is maximized, wherein K is the number of data types, f_i is said amount of each said data type to be routed and Δ

′

_i(e) is said weighted queue difference.

16. The method of claim 15, wherein said amounts of flow of each said data type i to be routed such that Σ

<sub>1≦

i≦

K</sub>f_i(Δ

′

_i(e)−

f_i) is maximized is further computed by performing the steps of;

(a) sorting the values of Δ

_i′

(e)d_i<sup>−

2</sup> for which Δ

′

(e)>

0;

(b) finding a set S⁺ of said commodities for which;

1) if i belongs to the set S⁺ and j does not belong to the set S⁺, then Δ

_i′

(e)d_i<sup>−

2</sup>>

Δ

_j′

(e)d_j<sup>−

2</sup>, and $2)<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{i\in <br><br>S^{+}}{\sum <br><br>}<br><br>\left[{\mathrm{\Delta <br><br>}}_i^{\mathrm{\prime <br><br>}}<br><br>\left(e\right)-{\mathrm{sd}}_i^2\right]/2)\le <br><br>c<br><br>\left(e\right),\mathrm{where}<br><br>\text{\hspace{1em}<br><br>}<br><br>s=\underset{i\in <br><br>S^{+}}{\min }<br><br>{\mathrm{\Delta <br><br>}}_i^{\mathrm{\prime <br><br>}}<br><br>\left(e\right)/d_i^2;<br><br>$

(c) computing s by setting s=max(0,[Σ

<sub>i∈

S+</sub>Δ

′

_i(e)−

2c(e)]/[Σ

<sub>i∈

S+</sub>d_i²]); and

(d) calculating flow value f_i by computing f_i=max(0,(Δ

_i′

(e)−

sd_i²)/2).

17. A system for directing the flow of a quantity of data through a communication system, said communication system comprising a plurality of switches including a source and a sink, each of said plurality of switches connected to a neighboring switch by a communication link having a capacity, each said link having a pair of queue buffers, one queue buffer of each said pair of queue buffers located at each said switch connected by said link, said system comprising:

(a) a data divider, located at each of said switches and configured to partition evenly among said queue buffers of said switch an amount of flow at said switch; and

(b) a processor located at each of said switches and configured to compute an amount of flow to be routed across each said link as a function of a difference between the amount of data in each of said pair of queue buffers, and as a function of a previous amount of flow between said pair of queue buffers, said processor causing said amount of data flow across each said link.

18. The system of claim 17, wherein said switch is further configured for computing an amount of flow f to be routed between said pair of queues across each said link, f=(β

)(Δ

(e)/2)+(β

−

1)(f′

), wherein Δ

(e) is a difference in the amounts of said data between said pair of queues, f′

is a last previous amount of flow between said pair of queues, and β

is a numerical value.

19. The system of claim 18, wherein β

is a numerical value between 1.0 and 2.0.

20. The system of claim 18, wherein β

is varied as a function of time.

21. The system of claim 18, wherein β

is varied as a function of the number of iterations which have been performed by said switch.

22. The system of claim 17, wherein said switch is further configured for adjusting said flow so as not to exceed said capacity of said link.

23. The system of claim 17, wherein said switch is further configured for adjusting said flow so as not to exceed said amount of said data available to be routed by said queue buffer.

24. A system for directing the flow of a plurality of types of data through a communication system, said communication system comprising a plurality of switches including a source and a sink, each of said plurality of switches connected to a neighboring switch by a communication link having a capacity, each said link having a pair of queue buffers, one queue buffer of each said pair of queue buffers located at each said switch connected by said link, said system comprising:

(a) a data divider, located at each of said switches, and configured to partition evenly among said queue buffers of said switches an amount of flow of said data type at said switch; and

(b) a processor, located at each of said switches, and configured to compute a weighted queue difference between said queue buffer of said switch and said queue buffer of each said neighboring switch, as a function of a difference between an amount of said data type in said queue buffer of said switch and an amount in said queue buffer of said neighboring switch, and as a function of a previous amount of flow routed between said pair of queue buffers, said processor causing said amount of flow of said data type to be routed across each said link, said routed amount of flow computed as a function of said weighted queue difference.

25. The system of claim 24, wherein said switch is further configured to compute said weighted queue difference as Δ

_i′

(e)=(β

)(Δ

(e))+(2.0)(β

−

1)(f′

), wherein f′

is a last previous amount of flow between said pair of queue buffers, Δ

(e) is a difference in the amounts of said data type between said pair of queues, and β

is a value between 1.0 and 2.0.

26. The system of claim 24, wherein said products to be summed are further multiplied by a normalization factor, d_i⁻

2, wherein d_i is a demand of data type i.

27. The system of claim 24, wherein said switch is further configured, after said computing step, to adjust said weighted queue difference if half of said weighted queue difference is greater than an amount of said data type available to be routed by said queue buffer.

28. The system of claim 24, wherein said switch is further configured, after said computing step, to adjust said weighted queue difference so as not to exceed said capacity of said link.

29. The system of claim 24, wherein said amount of flow of each said data type to be routed across each said link is further computed such that the summation of the product of said flows multiplied by the difference between said weighted queue difference and said amount of flow is maximized.

30. The system of claim 24, wherein said switches are further configured to resolve contentions between said plurality of data types for said capacity of said links by finding a marginal contribution factor, said marginal contribution factor corresponding to the derivative of each said flow of said data types, said marginal contribution factor comprising the smallest value at which the sum of said corresponding flows of said data types does not exceed said capacity of said links.

31. The system of claim 24, wherein said amounts of flow of each said data type i to be routed are such that Σ

<sub>1≦

i≦

K</sub>f_i(Δ

′

_i(e)−

f_i) is maximized, wherein K is the number of data types, f_i is said amount of each said data type to be routed and Δ

′

_i(e) is said weighted queue difference.

32. The system of claim 31, wherein, in order to calculate said amounts of flow of each said data type i to be routed such that Σ

<sub>1≦

i≦

K</sub>f_i(Δ

′

_i(e)−

f_i) is maximized, said switch is further comprises;

(a) a sorting unit so as to sort the values of Δ

_i′

(e)d_i<sup>−

2</sup> for which Δ

_i′

(e)>

0;

(b) a calculator unit so as to find a set S⁺ of said commodities for which;

1) if i belongs to the set S⁺ and j does not belong to the set S⁺, then Δ

_i′

(e)d_i<sup>−

2</sup>>

Δ

_j′

(e)d_j<sup>−

2</sup>, and $2)<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{i\in <br><br>S^{+}}{\sum <br><br>}<br><br>\left[{\mathrm{\Delta <br><br>}}_i^{\mathrm{\prime <br><br>}}<br><br>\left(e\right)-{\mathrm{sd}}_i^2\right]/2)\le <br><br>c<br><br>\left(e\right),\mathrm{where}<br><br>\text{\hspace{1em}<br><br>}<br><br>s=\underset{i\in <br><br>S^{+}}{\min }<br><br>{\mathrm{\Delta <br><br>}}_i^{\mathrm{\prime <br><br>}}<br><br>\left(e\right)/d_i^2;<br><br>$

(c) a computer unit so as to compute s by setting s max (0,[Σ

<sub>i∈

S+</sub>Δ

′

_i(e)−

2c(e)]/[Σ

<sub>i∈

S+</sub>d_i²]); and

(d) a calculating unit for calculating flow value f_i by computing f_i=max (0,[Δ

_i′

(e)−

sd_i²]/2).

33. In a communication system for directing the flow of a quantity of data through a plurality of switches, each switch having a queue buffer coupled to a corresponding queue buffer of a neighboring switch, a method for operating each of said switches comprising the steps of:

(a) partitioning evenly among said queue buffers of said switch an amount of flow at said switch;

(b) computing an amount of flow to be routed from said switch to a neighboring switch as a function of a difference between the amount of data in said queue buffers of said switches, and as a function of a previous amount of flow between said queue buffers; and

(c) routing said computed amount of flow from said switch to a neighboring switch.

34. The method of claim 33, wherein said step of computing an amount of flow comprises computing f=(β

)(Δ

(e)/2)+(β

−

1)(f′

), wherein f is said amount of flow to be routed between said switch and said neighboring switch, Δ

(e) is a difference in the amounts of said data between said pair of queues, f′

is a previous amount of flow between said pair of queues, and β

is a numerical value.

35. The method of claim 34, wherein β

is a numerical value between 1.0 and 2.0.

36. The method of claim 34, wherein β

is varied as a function of time.

37. The method of claim 34, wherein β

is varied as a function of the number of iterations which have been performed by said switch.

38. In a communication system for directing the flow of a plurality of types of data through a plurality of switches each switch having a queue buffer coupled to a corresponding queue buffer of a neighboring switch, a method for operating each of said switches comprising the steps of:

(a) partitioning evenly among said queue buffers of said switch an amount of flow at said switch;

(b) computing a weighted queue difference between said queue buffer of said switch and said corresponding queue of a neighboring switch as a function of a difference between an amount of said data type in said queue buffer of said switch and an amount in said queue buffer of said neighboring switch, and as a function of a previous amount of flow routed between said pair of queue buffers; and

(c) routing an amount of flow of each said data type from said switch to said neighboring switch said routed amount of flow computed as a function of said weighted queue difference.

39. The method of claim 38, wherein said weighted queue difference is Δ

_i′

(e)=(β

)(Δ

(e))+(2.0)(β

−

1)(f′

), wherein f′

is a last previous amount of flow between said pair of queue buffers, Δ

(e) is a difference in the amounts of said data type between said pair of queues, and β

is a value between 1.0 and 2.0.

40. The method of claim 38, further comprising the step of summing said data types and further multiplying said summed products by a normalization factor, d_i⁻

2, wherein d_i is a demand of data type i.

41. The method of claim 38, further comprising, after said computing step, the step of adjusting said weighted queue difference if half of said weighted queue difference is greater than an amount of said data type available to be routed by said queue buffer.

42. The method of claim 38, wherein said amounts of flow of each said data type i to be routed are such that Σ

<sub>1≦

i≦

K</sub>f_i(Δ

_i′

(e)−

f_i) is maximized, wherein K is the number of data types, f_i is said amount of each said data type to be routed and Δ

′

_i(e) is said weighted queue difference.

43. The method of claim 42, wherein said amounts of flow of each said data type i to be routed such that Σ

<sub>1≦

i≦

K</sub>f_i(Δ

′

_i(e)−

f_i) is maximized is further computed by performing the steps of;

(a) sorting the values of Δ

_i′

(e)d_i<sup>−

2</sup> for which Δ

_i′

(e)>

0;

(b) finding a set S⁺ of said commodities for which;

1) if i belongs to the set S⁺ and j does not belong to the set S⁺, then Δ

_i′

(e)d_i<sup>−

2</sup>>

Δ

_j′

(e)d_j<sup>−

2</sup>, and $2)<br><br>\text{\hspace{1em}<br><br>}<br><br>\underset{i\in <br><br>S^{+}}{\sum <br><br>}<br><br>\left[{\mathrm{\Delta <br><br>}}_i^{\mathrm{\prime <br><br>}}<br><br>\left(e\right)-{\mathrm{sd}}_i^2\right]/2)\le <br><br>c<br><br>\left(e\right),\mathrm{where}<br><br>\text{\hspace{1em}<br><br>}<br><br>s=\underset{i\in <br><br>S^{+}}{\min }<br><br>{\mathrm{\Delta <br><br>}}_i^{\mathrm{\prime <br><br>}}<br><br>\left(e\right)/d_i^2;<br><br>$

(c) computing s by setting s=max (0,[Σ

<sub>i∈

S+</sub>Δ

′

_i(e)−

2c(e)]/[Σ

<sub>i∈

S+</sub>d_i²]); and

(d) calculating flow value f_i by computing f_i=max (0,(Δ

_i′

(e)−

sd_i²)/2).