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

✍ Scribed by A. Gourgy; T. Szymanski; D. Down

• Book ID: 126603733
• Publisher: IEEE
• Year: 2009
• Tongue: English
• Weight: 828 KB
• Volume: 17
• Category: Article
• ISSN: 1063-6692
• DOI: 10.1109/TNET.2009.2014948

✦ Synopsis

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.