Decoupled parallel hierarchical matching schedulers

作者：Gonzalez Castano F J^*; Lopez Bravo C; Rodelgo Lacruz M; Asorey Cacheda R

来源：International Journal of Communication Systems, 2007, 20(3): 365-384.

DOI：10.1002/dac.828

• packet switching
• packet scheduling
• VOQ
• Birkhoff-von Neumann

The load balanced Birkhoff-von Neumann switch is an elegant VOQ architecture with two outstanding characteristics: (i) it has a computattional cost of O(1) iterations and (ii) input controllers do not exchange information (as a result, it allows decoupled implementations with a low power density). The load balancing stage guarantees stability under a broad class of traffic patterns. It may alter packet sequence, but this can be solved with appropriate packet selection strategies.
The average packet delay caused by previous maximal size matching algorithms, such as iSLIP, RDSRR, or PHM is noticeably lower than that of a Birkhoff-von Neumann switch, especially for low and medium loads. However, they need tightly coupled VOQ controllers, which implies higher power density. For example, this makes difficult to apply those algorithms to optical switching architectures. Moreover, they require O(log(2) N) iterations to converge, and this computational cost may be unacceptable for the slot lengths in optical packet switches.
In this paper, we propose a family of decoupled Parallel Hierarchical Matching (PHM) VOQ controllers (DPHM). They outperform the Birkhoff-von Neumann scheduler, which can be viewed as a member of the family (in fact, the simplest one). DPHM schedulers have a computational cost of O(1) iterations and, unlike last generation maximal size matching algorithms, they allow a low input controller interconnection complexity (low power density switch implementation).

• 出版日期2007-3