Title:
Liquid Schedule Searching Strategies for the Optimization of Collective Network Communications

Authors:
Emin Gabrielyan, Roger D. Hersch
{Emin.Gabrielyan,RD.Hersch}@epfl.ch


Affiliation:
École Polytechnique Fédérale de Lausanne


Abstract:
For collective communications, the upper limit of a network’s capacity is its liquid throughput. The liquid throughput corresponds to the flow of a liquid in an equivalent network of pipes. However, in communication networks, the aggregate throughput of a collective communication pattern (traffic) scheduled according to straight forward topology unaware techniques may be several times lower than the maximal potential throughput of the network. In most of the cut-through, wormhole and wavelength division optical networks, there is a loss of performance due to congestions between simultaneous transfers sharing a common link resource. We propose to schedule the transfers of a traffic according to a schedule yielding the liquid throughput. Such a schedule, called liquid schedule, relies on the knowledge of the underlying network topology and ensures an optimal utilization of all bottleneck links. To build a liquid schedule, we partition the traffic into time frames comprising mutually non-congesting transfers keeping all bottleneck links occupied all the time. The search for mutually non-congesting transfers utilizing all bottleneck links is of exponential complexity. We present an efficient algorithm which non-redundantly traverses the search space and limits the search to only those sets of transfers, which are non-congesting and utilize all bottleneck links. We further propose a liquid schedule construction technique, which efficiently reduces the search space without affecting the solution space.


Published:
in PCC'04 - The 2004 International Multiconference in Computer Science & Computer Engineering - Conference on Pervasive Computing and Communications - Monte Carlo Resort, Las Vegas, Nevada, USA, June 21-24, 2004 - pp. 834-848 by CSREA Press - Volume II ISBN: 1-932415-39-4, Set ISBN: 1-932415-40-8