Backlog Analysis of Maximal Matching Switching with Speedup

In this paper we analyze the average backlog in a combined input-output queued switch using a maximal siz e matching scheduling algorithm. We compare this average backlog to the average backlog achieved by an op timal switch. We model the cell arrival process as independent and identically distributed between time s lots and uniformly distributed among input and output ports. For switches with many input and output port s, the backlog associated with maximal size matching with speedup $3$ is no more than $3\frac{1}{3}$ time s the backlog associated with an optimal switch. Moreover, this performance ratio rapidly approaches $2$ as speedup increases.