Name
Title | ||
|---|---|---|
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, complex- ity, variations, and performance. First, the concept of "pseudo- saturation" is introduced. Most, if not all, protocols do not prop- erly 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 conjunc- tion with any maxmin protocol to handle the nonzero MCR re- quirements without adding excessive complexity. Finally, simula- tions suggest that the complexity analysis is inadequate to gauge protocol performance. A new analysis based on protocol dy- namics is called for to understand the performance. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1109/INFCOM.1999.751469 | INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE |
Keywords | DocType | Volume |
asynchronous transfer mode,computational complexity,convergence of numerical methods,graph theory,minimax techniques,protocols,telecommunication traffic,ABR traffic,ATM networks,complexity analysis,complexity estimates,constraint precedence graph,convergence,maxmin problem,maxmin protocols,nonzero minimum cell rate,optimality condition,parallelization,performance,protocol dynamics,protocol performance,pseudo-saturated links,simulations,time complexity,variations | Conference | 2 |
ISSN | ISBN | Citations |
0743-166X | 0-7803-5417-6 | 9 |
PageRank | References | Authors |
0.94 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wei K. Tsai | 1 | 103 | 11.47 |
| Yuseok Kim | 2 | 9 | 0.94 |