分层分组公平排队算法

我们建议使用理想化的分层通用处理器共享（H-GPS）模型来同时支持保证的实时，速率自适应的步进和受控链路共享服务。我们设计了分层数据包公平队列（H-PFQ）算法，通过使用单级可变速率PFQ服务器作为基本构建块来近似H-GPS。通过以位为单位而不是以秒为单位计算系统虚拟时间和每包虚拟开始/结束时间，文献中的大多数PFQ算法可以被适当地定义为可变速率服务器。我们开发了分析可变速率和分层PFQ服务器的延迟和公平属性的技术。我们证明，为了提供与H-PFQ服务器的紧密延迟界限，单级PFQ服务器必须具有小的最坏情况公平指数（WFI）。我们提出了一种名为WF2Q +的newp PFQ算法，它是第一个具有以下三个属性的算法：1）在所有PFQ算法中提供最紧密的延迟约束; 2）在所有PFQ算法中具有最小的WFI; 3）具有相对低的渐近复杂度O（log N）。仿真结果用于评估H-WF2Q +，H-WFQ，H-SFQ和H-SCFQ的延迟和链路共享特性。