基于VOQ的一种非均匀流量调度算法及其性能分析

Novel scheduling algorithm under non-uniform traffic based on VOQ and its performance analysis

为了提高数据通信的传输速率与可靠性,高速路由器采用了基于VOQ的交换架构及调度算法。首先对经典的FIRM(FCFS in Round-Robin Matching)算法进行分析,该算法在突发和非均匀业务时性能有很大的下降。针对这一缺陷,提出了lp-FIRM(Long Queues Priority FIRM)算法,此算法采用长队列有效机制,对VOQ队列长度超过阈值Lmax的队列首先进行循环匹配调度,再对长度小于阈值Lmax的队列进行循环匹配调度,并给出了lp-FIRM的算法描述,并与i SLIP、FIRM算法进行了比较。仿真结果表明,lp-FIRM算法与经典算法相比,在均匀业务下的性能类似,而在非均匀业务下性能有了很大提升。

In order to improve the rate and reliability of communication, high speed routers have adopted VOQ switch architecture and scheduling algorithms. In this paper, performance of classic FIRM（First Come First Serve in Round-Robin Matching） is analyzed, and it declines rapidly under burst or non-uniform traffic. To resolve the problem, an optimized algorithm named lp-FIRM is proposed. This algorithm schedules the input queue first when its length exceeds the Lmax value, and then schedules the other input queues. In this paper, the algorithm is described and compared with i SLIP and FIRM. Simulation results show that the performance of lp-FIRM is similar to classic scheduling algorithms under uniform traffic and higher under burst and non-uniform traffic.