Show simple item record

dc.contributor.authorFatourou, Panagiotaen
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorSpirakis, Paul G.en
dc.creatorFatourou, Panagiotaen
dc.creatorMavronicolas, Mariosen
dc.creatorSpirakis, Paul G.en
dc.description.abstractTwo important performance parameters of distributed, rate-based flow control algorithms are their locality and convergence complexity. The former is characterized by the amount of global knowledge that is available to their scheduling mechanisms, while the latter is defined as the number of update operations performed on rates of individual sessions until max-min fairness is reached. Optimistic algorithms allow any session to intermediately receive a rate larger than its max-min fair rateen
dc.description.abstractbottleneck algorithms finalize the rate of a session only if it is restricted by a certain, highly congested link of the network. In this work, we present a comprehensive collection of lower and upper bounds on convergence complexity, under varying degrees of locality, for optimistic, bottleneck, rate-based flow control algorithms. Say that an algorithm is oblivious if its scheduling mechanism uses no information of either the session rates or the network topology. We present a novel, combinatorial construction of a capacitated network, which we use to establish a fundamental lower bound of dn/4 + n/2 on the convergence complexity of any oblivious algorithm, where n is the number of sessions laid out on a network, and d. the session dependency, is a measure of topological dependencies among sessions. Moreover, we devise a novel simulation proof to establish that, perhaps surprisingly, the lower bound of dn/4 + n/2 on convergence complexity still holds for any partially oblivious algorithm, in which the scheduling mechanism is allowed to use information about session rates, but is otherwise unaware of network topology. On the positive side, we prove that the lower bounds for oblivious and partially oblivious algorithms are both tight. We do so by presenting optimal oblivious algorithms, which converge after dn/2 + n/2 update operations are performed in the worst case. To complete the picture, we show that linear convergence complexity can indeed be achieved if information about both session rates and network topology is available to schedulers. We present a counterexample, nonoblivious algorithm, which converges within an optimal number of n update operations. Our results imply a surprising convergence complexity collapse of oblivious and partially oblivious algorithms, and a convergence complexity separation between (partially) oblivious and nonoblivious algorithms for optimistic, bottleneck rate-based flow control. © 2005 Society for Industrial and Applied Mathematics.en
dc.sourceSIAM Journal on Computingen
dc.subjectKnowledge based systemsen
dc.subjectDistributed computer systemsen
dc.subjectComputational complexityen
dc.subjectLower boundsen
dc.subjectConvergence of numerical methodsen
dc.subjectDistributed algorithmsen
dc.subjectMax-min fairnessen
dc.subjectBottleneck algorithmsen
dc.subjectConvergence complexityen
dc.subjectOblivious, partially oblivious, and nonoblivious algorithmsen
dc.subjectRate-based flow controlen
dc.titleEfficiency of oblivious versus nonoblivious schedulers for optimistic, rate-based flow controlen
dc.description.endingpage1252 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.source.abbreviationSIAM J Computen
dc.contributor.orcidSpirakis, Paul G. [0000-0001-5396-3749]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record