Decoupled parallel hierarchical matching schedulers and their evaluation

The load balanced Birkhoff-von Neumann switch is an elegant VOQ architecture with two outstanding characteristics: (i) it has a computational cost of 0(1) iterations and (ii) there is no need for information exchange between input controllers (as a result, it admits decoupled implementations with a low power density). The load balancing stage guarantees stability under reasonable traffic assumptions. 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, WWFA or PHM is noticeably lower than that of a Birkhoff-von Neumann switch, specially for low and medium loads. However, they need tightly coupled VOQ controllers (which implies higher power density) and-perhaps even worse-they require 0(log27V) iterations to converge. This computational cost may be unacceptable for slot lengths attainable in optical packet switches. In this paper, we propose and evaluate a decoupled PHM VOQ controller (DPHM). It outperforms the Birkhoff-von Neumann scheduler, which can be viewed as a particular case of our proposal (in fact, the simplest one). DPHM has a computational cost of 0(1) iterations and, unlike last generation maximal size matching algorithms, it allows a low input controller interconnection complexity (low power density switch implementation).