Non-Intrusive Delay Differentiation

Modern packet-switched communication networks use resource sharing via statistical multiplexing, which requires routers to buffer packets temporarily when they cannot be forwarded immediately. Packet buffering mitigates the risk for packet loss, but contributes to network latency. The Non-Intrusive Delay Differentiation (NIDD) project seeks to offer applications a choice of different delay guarantees without side effects.

Example

The figures on the right show an example, in which the network is shared by a latency-sensitive flow (e.g. VOIP), and a throughput-sensitive flow. If the network uses FIFO scheduling, there is only one buffer length (e.g., 100ms): both flows have a maximum delay of 100ms.
If the network uses an NIDD scheduler, such as Delay-segemented FIFO (DSF), there are several buffer lengths to chose from (e.g., 1ms and 100ms): the latency-sensitive flow chooses the 1ms-delay lass and the throughput-sensitive flow chooses the 100ms-delay class. Note that, compared to the FIFO experiment, the throughput remains the same.

Context

The configuration of packet buffers and analysis of delay effects has been a central research topic for packet-switched communication networks. The existing literature on packet buffer configuration can be roughly divided into three areas: buffer sizing, active queue management, and multi-queue scheduling. The NIDD approach is fundamentally different. Its objective is providing multiple virtual FIFO queues with deterministic buffering/delay behaviour, but without impacting throughput when compared to single-queue FIFO scheduling. In other words, the link resource is freely shared, but delay targets are enforced through dynamic buffer sizing.

FIFO
(without NIDD)

Latency-sensitive flow:

Throughput-sensitive flow:

NIDD
(DSF scheduler)

Latency-sensitive flow:

Throughput-sensitive flow:

Properties of NIDD schedulers

With an NIDD scheduler, the choice between service classes is incentive-compatible, so that all classes can be freely accessed without admission control and/or traffic contracts. Furthermore, because an NIDD scheduler does not interfere with FIFO throughput, it satisfies even a strict interpretation of network neutrality.

Throughput Interference

The side effect of a scheduler is quantified as the throughput bias compared to a FIFO system. The thoughput interference index (TI²) formally captures this metric.

Reproduce our results

The simulation source code used for the DSF paper are provided as a complete archive (dsf.tgz). In order to reproduce each experimental result, we also provide detailed step-by-step instructions.

Publications

The NIDD approach is presented in three papers. The Incentive-Compatible Differentiated Scheduling (ICDS) paper introduces the basic concept and a proof of incentive-compatibility. The Virtually Isolated FIFO Queueing (VIFQ) paper introduces a low-complexity algorithm, which, unfortunately, has the caveat that low-rate, low-delay traffic can be starved. The Delay Segment FIFO (DSF) paper presents a bias-free algorithm with provably low TI².

Future Work

Recently, a lot of existing service differentiation research is revisited with a focus on data center networks, which have slightly different characteristics and objectives from public communication networks. It seems that NIDD scheduling should be an attractive modular building block for service differentiation in data center networks.

Existing TCP models that describe how TCP's goodput rate depends on the round-trip time (RTT) do not explicitly distinguish between the propagation delay and the buffering delay portion of the RTT. However, this distinction might be relevant when TCP flows do not symmetrically share packet buffers. Therefore, generalized TCP competition model might be needed to fully understand the impact of NIDD scheduling on TCP fairness. Similarly, recent TCP variations attempt to reduce the dependency of goodput rate on RTT.

Last not least, it is not clear whether DSF is the best possible NIDD scheduler. In light of future findings related to TCP rate control, better NIDD implementations might be possible.