  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.
