Re-examining maxmin protocols: a fundamental study on convergence, complexity, variations, and performance

Abstract

This paper re-examines maxmin protocols for ABR traffic in ATM networks in four aspects: convergence, complexity, variations, and performance. First, the concept of "pseudo-saturation" is introduced. Most, if not all, protocols do not properly handle pseudo-saturated links, and as a result, there is no guarantee for convergence to true maxmin solutions. Second, the concept of "constraint precedence graph (CPG)" is introduced and is used to define the best possible time complexity of any maxmin protocol. The existing complexity estimates are overly conservative because they do not consider possible concurrent operations. In contrast, the CPG analysis explicitly accounts for parallelization. Third, the concept of "constraint" is generalized and this generalization is used to derive an optimality condition for the maxmin problem with nonzero minimum cell rate (MCR) requirements. This optimality condition can be used in conjunction with any maxmin protocol to handle the nonzero MCR requirements without adding excessive complexity. Finally, simulations suggest that the complexity analysis is inadequate to gauge protocol performance. A new analysis based on protocol dynamics is called for to understand the performance.