Performance evaluation of randomized algorithms for input-queued switch scheduling
S. Subahar, S. Valarmathy, D. Sharmila, S. S. Arumugam · 2005
The paper presents the most up-to-date randomized algorithm for evaluating the performance of the efficient randomized algorithms for input-queued switch scheduling. Six techniques of randomized algorithm as random-I,II,III,IV,Laura,Serena have been implemented and their performance have been evaluated. The first four techniques gives throughput up to 81%, but they experience long delays when packets are matched. So to overcome the above problem, the technique named 'Laura' has been implemented and proven that the technique achieves a throughput up to 90%. Simulation shows that it provides delays close to that of MWM and out performs all other known low complexity scheduling algorithms. 'Laura' needs an external source of randomness to obtain random matchings each time, which can cause some implementation difficulties. To avoid this problem, an enhanced version of Laura called 'Serena' has been proposed which exploits the randomness present in the arrivals process to determine good random matchings and achieves a throughput of 100%. Fortuitously, this improves performance, because the arrivals are precisely what increase the weight of edges, using them leads to better schedule.