论文标题
分层多资源公平排队用于数据包处理
Hierarchical Multi-resource Fair Queueing for Packet Processing
论文作者
论文摘要
各种Middlebox都在网络中泛滥成灾，以执行数据包处理功能，例如防火墙，代理，调度等。随着网络流量的爆炸和对多种类型的网络资源的需求，Middlebox为服务质量（QoS）提供保证为分组的流量提供的挑战从未更具挑战性。不幸的是，当前所有现有的公平排队算法都无法支持层次安排，这对于为多个服务类的分组流提供QoS保证是必不可少的。在本文中，我们提出了两种新的多资源公平排队算法，以支持层次调度，倒塌的层次主要资源资源公平排队（H-DRFQ崩溃）和Dove-Tailing H-DRFQ。尤其是，倒塌的H-DRFQ将分组流的层次结构转换为平坦的结构，以进行平坦的调度，而鸽子尾巴H-DRFQ则在原始层次结构上执行平坦的调度为兄弟姐妹节点。通过严格的理论分析，我们发现这两种算法都可以为单个流提供层次份额保证，而鸽子尾h-DRFQ中数据包延迟的上限小于折叠的H-DRFQ。我们在单击模块路由器上实现了提出的算法，并且实验结果验证了我们的分析结果。
Various middleboxes are ubiquitously deployed in networks to perform packet processing functions, such as firewalling, proxy, scheduling, etc., for the flows passing through them. With the explosion of network traffic and the demand for multiple types of network resources, it has never been more challenging for a middlebox to provide Quality-of-Service (QoS) guarantees to grouped flows. Unfortunately, all currently existing fair queueing algorithms fail in supporting hierarchical scheduling, which is necessary to provide QoS guarantee to the grouped flows of multiple service classes. In this paper, we present two new multi-resource fair queueing algorithms to support hierarchical scheduling, collapsed Hierarchical Dominant Resource Fair Queueing (collapsed H-DRFQ) and dove-tailing H-DRFQ. Particularly, collapsed H-DRFQ transforms the hierarchy of grouped flows into a flat structure for flat scheduling while dove-tailing H-DRFQ iteratively performs flat scheduling to sibling nodes on the original hierarchy. Through rigorous theoretical analysis, we find that both algorithms can provide hierarchical share guarantees to individual flows, while the upper bound of packet delay in dove-tailing H-DRFQ is smaller than that of collapsed H-DRFQ. We implement the proposed algorithms on Click modular router and the experimental results verify our analytical results.
