Enhanced Birkhoff-von Neumann decomposition algorithm for input queued switches

J. Li, N. Ansari

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


The enhanced Birkhoff-von Neumann decomposition (EBVND) algorithm, a new class of scheduling arbitrators for input queued (IQ) crossbar switches that is based on the Birkhoff-von Neumann decomposition algorithm, is introduced. Theoretical analysis shows that the performance of EBVND is better than the Birkhoff-von Neumann decomposition algorithm in terms of throughput and cell delay, and can also provide rate and cell delay guarantees. Also, the weighted rate filling algorithm (WRFA), a new algorithm that can be ueed to construct doubly stochastic matrices from doubly substochastic matrices with less complexity and better fairness, is proposed. The wave front Birkhoff-von Neumann decomposition (WFBVND) algorithm and its simplified version WFBVND with logN iterations (WFBVND-logN), the special cases of EBVND, are also introduced and evaluated. Simulations show that the WFBVND and WFBVND-logN algorithms have much lower average cell delay as compared to the Birkhoff-von Neumann decomposition algorithm.

Original languageEnglish (US)
Pages (from-to)339-342
Number of pages4
JournalIEE Proceedings: Communications
Issue number6
StatePublished - Dec 2001

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering


Dive into the research topics of 'Enhanced Birkhoff-von Neumann decomposition algorithm for input queued switches'. Together they form a unique fingerprint.

Cite this