Analytical evaluation of PHM convergence
Francisco Javier González-Castaño, Cristina López‐Bravo, Rafael Asorey-Cacheda, Pedro S. Rodríguez‐Hernández, J.M. Pousada-Carballo · IEEE Transactions on Communications · 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(log2N), as in the case of iSLIP-like algorithms