Maintaining flow isolation in work-conserving flow aggregation

In order to improve the scalability of scheduling protocols with bounded end-to-end delay, much effort has focused on reducing the amount of per-flow state at routers. One technique to reduce this state is flow aggregation, in which multiple individual flows are aggregated into a single aggregate flow. In addition to reducing per-flow state, flow aggregation has the advantage of a per-hop delay that is inversely proportional to the rate of the aggregate flow, while in the case of no aggregation, the per-hop delay is inversely proportional to the (smaller) rate of the individual flow. Flow aggregation in general is non-work-conserving. Recently, a work-conserving flow aggregation technique has been proposed. However, it has the disadvantage that the end-to-end delay of an individual flow is related to the burstiness of other flows sharing its aggregate flow. Here, we show how work-conserving flow aggregation may be performed without this drawback, that is, the end-to-end delay of an individual flow is independent of the burstiness of other flows.