3/2-approximations to maximum weight matching scheduling algorithms for networks of input-queued switches

摘要

It is well known that maximum weight matching algorithms guarantee the stability of input-queued switches, but are impractical due to their high computational complexity. In this paper, we investigate the application of matching algorithms that approximate maximum weight matching algorithms to scheduling problems. We show that while having a low computational complexity, they guarantee the stability of input queued switches when they are deployed with a moderate speedup. Recent research has shown that scheduling algorithms that stabilize individual switches do not necessarily guarantee the stability of networks of input-queued switches. We apply recent results on networks of input-queued switches and show that the approximation algorithms proposed in this paper stabilize both single switches and networks of input-queued switches. Finally, we show that the improve-matching algorithm stabilizes networks of switches when it is deployed with a speedup of 3/2 + /spl isin/.