一种简单的平滑公平轮转调度算法

根据通用处理器共享的公平排队思想,针对数据包或信元交换,提出了一种将数据流的预订速率作为时隙分配的权值来构建动态调度树的公平轮转调度算法。其主要思路是:当有新数据流到达时,将各数据流按其权值均匀分布到完全二叉树的叶子节点上,在每个时隙开始时轮转调度算法负责从叶子节点中依次取出数据流号,发送该数据流的信元,调度复杂度为O(1)。与其他经典的公平调度算法引比,所提出的公平轮转调度算法实现简单。理论分析和仿真结果都表明,这种简单的平滑公平轮转调度算法(SSFRR)具有良好的公平性,对源端为漏桶控制的数据流能够提供端到端的有界时延,且能够提供基于数据流的QoS保证。

Simple and Smoothed Fair Round Robin Scheduling Algorithm

A simple and smoothed fair round-robin(SSFRR) scheduling algorithm for packet or cell switching was proposed based on the idea of packet generalized processor sharing(GPS) service discipline.The algorithm uses the reserved rates of active flows as their weights to build scheduling tree for allocating slots.The basic idea of SSFRR is to distribute all flow IDs over the leaf nodes of a complete binary tree according to the weight of each flow by scanning the weight matrix when a new flow arrives.At each time slot,SSFRR visits next leaf node of the binary tree in sequence from left to right,takes out the flow ID from the current leaf node and schedules the cell of this flow.SSFRR scheduling algorithm has O(1) scheduling time complexity.Compared with other classical fairness round robin scheduler,SSFRR algorithm is simpler to implement.Analysis and simulation show that SSFRR scheduling algorithm has good fairness property,and can provide end-to-end delay bounds for those flows which are token-bucket regulated by sources.SSFRR can provide flow-based QoS guarantees.