LRMA: An ATM Scheduler Algorithm with Extra Implementation Effectiveness

J. Tsiligaridis and R. Acharya (USA)


Scheduler, SFQ, ATM scheduler


Various packet-scheduling policies have been invented in order to emulate the Generalized Processor Sharing (GPS) policy. Several algorithms of the Fair Queueing discipline have been created to reduce the complexity caused by the virtual times' computation. For the sake of avoiding the sorting operation, a new algorithm called Left and Right Move Algorithm (LRMA) is proposed. The LRMA with O(1) complexity, can be considered as an implementation tool for maintaining the priority, that is the basic parameter for the sorted-priority algorithms. The LRMA can also work as frame-based server for ATM networks, avoiding the use of virtual times and servicing queues in a fashion similar to the Round Robin (RR). Working in this way, it can diminish queuing delay from the burden flows and speed up the service of the activated flows, avoiding "empty times" with the use of the scheduler table. Our algorithm with the jump mechanism outweighs the calendar queue for both the initialization step and the dequeue operation and improves the RR schedulers performance when not all of the flows are activated. Simulation experiments are provided. Finally, the usefulness, the efficient and easy implementation, makes LRMA, amenable to several parts of the network (switches, routers, gateways).

Important Links:

Go Back