Analytical evaluation of PHM convergence
2006
The parallel hierarchical matching (PHM) algorithm is a distributed maximal size matching scheduler for virtual output-queued switches. In a previous letter, we formulated an upper bound on the maximum number of iterations PHM requires to achieve a maximal size matching in any traffic scenario. In this letter, we follow an analytical approach to find the average number of iterations for PHM to achieve a maximal size matching under diverse traffic models. The estimated number of iterations is O(log 2 N), as in the case of iSLIP-like algorithms
Keywords:
- Scheduling (computing)
- Computational complexity theory
- Iterative method
- Mathematical optimization
- Parallel algorithm
- Distributed algorithm
- Real-time computing
- Upper and lower bounds
- Control theory
- Queueing theory
- Computer science
- Hierarchical control system
- Convergence (routing)
- Theoretical computer science
- Algorithm
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
7
References
2
Citations
NaN
KQI