On Tracking the Behavior of an Output-Queued Switch Using an Input-Queued Switch

We address the problem of fair scheduling of packets in Internet routers with input-queued (IQ) switches and unity speedup. Scheduling in IQ switches is formulated as tracking the behavior of an output-queued (OQ) switch that provides optimal performance. We present the notion of “lag” as a performance metric that measures the difference between a packet's departure time in an IQ switch over that provided by an OQ switch. We prove that per-packet mean lag is bounded for a maximum weight-matching scheduling policy that uses lag values for its weights and derive a bound on the mean lag value using a Lyapunov function technique. Furthermore, we propose a simple heuristic tracking scheduling policy and evaluate its performance by simulation.