Modern data networks support highly heterogeneous traffic sources. It is therefore imperative to design network control policies that are inherently robust to burstiness in traffic. Ideally, the control policies should not adversely affect the stability and delay properties of one traffic flow, due to erratic or bursty behavior of another traffic flow in the network.
Maximum weight scheduling (MWS) is a well-known link scheduling algorithm that achieves the maximum throughput in communication networks. Loosely speaking, the algorithm schedules the set of feasible links with the maximum total queue length at that instant. However, when there is a mix of bursty and benign traffic, MWS tends to allocate most of the service to the bursty traffic flow, following the arrival of a large burst, which in turn leads to large delays for the benign flows. Thus, bursty flows in a network can ‘infect’ benign flows with large erratic delays.
The main contribution of this paper is in designing scheduling mechanisms that achieve maximum throughput, and yet provide a degree of robustness against the effect of bursty traffic in the network. Specifically, we discuss two scheduling algorithms. The first algorithm is based on adaptive CSMA (Carrier Sense Multiple Access), a recently-developed randomized algorithm that achieves the maximum throughput in a distributed fashion. The second algorithm is maximum weight scheduling with capped queue lengths. Unlike the traditional MWS, this algorithm schedules the set of links with the maximum sum of capped queue lengths, where the cap value is chosen to be sufficiently large.
To characterize the performance of the algorithms, we consider a simple queuing network consisting of two conflicting links. The traffic served by the first link is bursty, modeled by a heavy-tailed arrival process, while traffic at the second link is benign, modeled by a light-tailed arrival process. In this setting, previous work has shown that even the light-tailed traffic would experience heavy-tailed delays under MWS. In contrast, we demonstrate a threshold phenomenon in the relationship between the arrival rate of the light-tailed traffic and its queue backlog distribution. In particular, we show that with the adaptive CSMA algorithm, the light-tailed traffic experiences a light-tailed queue backlog, when its arrival rate is less than a certain threshold value. Intuitively, this implies that the benign traffic generally experiences predictable delays. For arrival rates above the threshold, the light-tailed traffic experiences a heavy-tailed queue backlog, implying that the delays experienced can be large and highly erratic. Our analysis also shows that this threshold value is approximately equal to half the server capacity.
Intuitively, all links in adaptive CSMA attempt to capture the channel with bounded aggressiveness. As a result, even when large bursts arrive at a link carrying heavy-tailed traffic, the link cannot take over the server by attempting to transmit with arbitrary aggressiveness. This has the effect of 'shielding' the light-tailed traffic from the large bursts, at least when the arrival rate is smaller than the threshold value. Furthermore, adaptive CSMA does not need any a priori information about traffic statistics.
Note that for general queuing networks with more than two links and any mix of heavy-tailed and light-tailed traffic, the 'shielding' effect still holds due to the bounded aggressiveness, although the threshold arrival rates may be different from the two-link network.
Motivated by the above properties of adaptive CSMA, we show a similar threshold behavior for max-weight scheduling with capped queue lengths.
This paper wins a Best Paper Award in WiOPT 2013 conference.