A Deterministic ParallelSchedulingAlgorithm forInput Queued CrossbarSwitches
Yanfeng Zheng, Shutao Sun · 2005
Input-queued (IQ)switcharchitectures have becomepredominant inhigh-speed switching forthepast decade. MaximumWeightMatching (MWM)algorithms are knowntoachieve 100%throughput underanyadmissible traffic. Unfortunately, MWM isimpractical foritshigh computational complexity O(A).Inthispaper, we study a newtypeofapproximate algorithm toMWM using local searchtechnique. Instead ofusingrandomized technique whichismainlyusedbytheexisting approximations, our algorithm runsina deterministic waywhichiseasytobe implemented by hardware. Itprovides 100% throughput underanyadmissible traffic andsimulation results showthat theproposed algorithm withonly3 iterations outperforms theexisting approximations toMWM. Keywords-Switching;virtual output queue;crossbar; scheduling