System and method for increasing the speed of distributed single and multi-commodity flow using second order methods
First Claim
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).
5 Assignments
0 Petitions
Accused Products
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 fi of said data type i is routed across each said link such that Σ1≦i≦Kfi (Δ′i(e)−fi) 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.
-
Citations
43 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). - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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). - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16)
(a) sorting the values of Δ
i′
(e)di−
2 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)di−
2>
Δ
j′
(e)dj−
2, and(c) computing s by setting s=max(0,[Σ
i∈
S+Δ
′
i(e)−
2c(e)]/[Σ
i∈
S+di2]); and
(d) calculating flow value fi by computing fi=max(0,(Δ
i′
(e)−
sdi2)/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. - View Dependent Claims (18, 19, 20, 21, 22, 23)
-
-
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. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32)
(a) a sorting unit so as to sort the values of Δ
i′
(e)di−
2 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)di−
2>
Δ
j′
(e)dj−
2, and(c) a computer unit so as to compute s by setting s max (0,[Σ
i∈
S+Δ
′
i(e)−
2c(e)]/[Σ
i∈
S+di2]); and
(d) a calculating unit for calculating flow value fi by computing fi=max (0,[Δ
i′
(e)−
sdi2]/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. - View Dependent Claims (34, 35, 36, 37)
-
-
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. - View Dependent Claims (39, 40, 41, 42, 43)
(a) sorting the values of Δ
i′
(e)di−
2 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)di−
2>
Δ
j′
(e)dj−
2, and(c) computing s by setting s=max (0,[Σ
i∈
S+Δ
′
i(e)−
2c(e)]/[Σ
i∈
S+di2]); and
(d) calculating flow value fi by computing fi=max (0,(Δ
i′
(e)−
sdi2)/2).
-
Specification