Analytical evaluation of PHM convergence

Author

Gonzalez-Castano, F.J. ; Lopez-Bravo, C. ; Asorey-Cacheda, R. ; Rodriguez-Hernandez, P.S. ; Pousada-Carballo, J.M.

Author_Institution

Dept. de Ingenieria Telematica, Vigo Univ.

Volume

54

Issue

9

fYear

2006

Firstpage

1547

Lastpage

1553

Abstract

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₂N), as in the case of iSLIP-like algorithms

Keywords

computational complexity; packet switching; parallel algorithms; queueing theory; scheduling; telecommunication traffic; distributed maximal size matching scheduler; maximal size matching algorithm; parallel hierarchical matching convergence; traffic scenario; virtual output-queued switches; Application specific integrated circuits; Computational efficiency; Computational modeling; Convergence; Delay; Prognostics and health management; Scheduling algorithm; Switches; Traffic control; Upper bound; Parallel hierarchical matching (PHM); scheduling; virtual output-queued (VOQ);

fLanguage

English

Journal_Title

Communications, IEEE Transactions on

Publisher

ieee

ISSN

0090-6778

Type

jour

DOI

10.1109/TCOMM.2006.881205

Filename

1703811