Liquid schedule searching strategies for the optimization of collective network communications
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.
lsssftoocnc.pdf
openaccess
229.61 KB
Adobe PDF
1c5e113d85c58ba78d9f2176ba188c34