A WEIGHTED SCHEDULING ALGORITHM WITH o（N~2） COMPLEXITY FOR INPUT-BUFFERED QUEUE

Most Internet core routers use input queued switches. It is important to research on scheduling algorithms for input queued switches. Weighted scheduling algorithms have high performance but few of them have been used because they are too complex to be implemented in hardware. A new weighted algorithm, L2QF, is presented in this paper. This algorithm uses the ways of serial polling, selecting one output port for each input port in turn according to the length of virtual output queues. L2QF has the same performance as LQF, but its complexity is only o（N 2） . Because L2QF has the lowest complexity among all the LQF algorithms and can be executed within many iterations, it is readily to be implemented in hardware.