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

Simple and Smoothed Fair Round Robin Scheduling Algorithm

作　　者：郭子荣[1,2] 曾华燊[1] 窦军[1] 

机构地区：[1]西南交通大学信息科学与技术学院,成都610031 [2]包头铁道职业技术学院,包头014060

出　　处：《计算机科学》2016年第1期122-127,共6页Computer Science

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

关 键 词：平滑公平轮转调度 QOS保证 端到端时延 时隙分配 

分 类 号：TN91[电子电信—通信与信息系统]