Analysis

Experimental evidence alone is insufficient to allow us to make strong statements about Nice's non-interference properties for general network topologies, background flow workloads, and foreground flow workloads. We therefore analyze it formally to bound the reduction in throughput that Nice imposes on foreground flows. Our primary result is that under a simplified network model, for long transfers, the reduction in the throughput of Reno flows is asymptotically bounded by a factor that falls exponentially with the maximum queue length of the bottleneck router irrespective of the number of Nice flows present.

Theoretical analysis of network protocols, of course, has limits. In general, as one abstracts away details to gain tractability or generality, one risks omitting important behaviors. Most significantly, our formal analysis assumes a simplified fluid approximation and synchronous network model, as described below. Also, our formal analysis holds for long background flows, which are the target workload of our abstraction. But it also assumes long foreground Reno flows, which are clearly not the only cross-traffic of interest. Finally, in our analysis, we abstract detection by assuming that at the end of each RTT epoch, a Nice sender accurately estimates the queue length during the previous epoch. Although these assumptions are restrictive, the insights gained in the analysis lead us to expect the protocol to work well under more general circumstances. The analysis has also guided our design, allowing us to include features that are necessary for noninterference while excluding those that are not. Our experience with the prototype has supported the benefit of using theoretical analysis to guide our design: we encountered few surprises and required no topology or workload-dependent tuning during our experimental effort.

Figure 1: Nice Queue Dynamics

We use a simplified fluid approximation model of the network to help us model the interaction of multiple flows using separate congestion control algorithms. This model assumes infinitely small packets. We simplify the network itself to a source, destination, and a single bottleneck, namely a router that performs drop-tail queuing as shown in Figure 1. Let $\mu$ denote the service rate of the queue and $B$ the buffer capacity at the queue. Let $\tau$ be the round-trip delay of packets between the source and destination excluding all queuing delays. We consider a fixed number of connections, $m$ following Reno and $l$ following Nice, each of which has one continuously backlogged flow between a source and a destination. Let $t$ be the Nice threshold and $q_t=t\cdot B$ be the corresponding queue size that triggers multiplicative backoff for Nice flows. The connections are homogeneous, i.e. they experience the same propagation delay $\tau$. Moreover, the connections are synchronized so that in the case of buffer overflow, all connections simultaneously detect a loss and multiply their window sizes by $\gamma$. Models assuming flow synchronization have been used in previous analyses  [6]. We model only the congestion avoidance phase to analyze the steady-state behavior.

We obtain a bound on the reduction in the throughput of Reno flows due to the presence of Nice flows by analyzing the dynamics of the bottleneck queue. We achieve this goal by dividing the duration of the flows into periods. In each period we bound the decrease in the number of Reno packets processed by the router due to interfering Nice packets. In the following we give an outline of this analysis. The complete analysis with detailed proofs appears in the our technical report [49].

Let $W_r(t)$ and $W_n(t)$ denote respectively the total number of outstanding Reno and Nice packets in the network at time $t$. $W(t)$, the total window size, is $W_r(t) + W_n(t)$. We trace these window sizes across periods. The end of a period and the beginning of the next is marked by a packet loss, at which time each flow reduces its window size by a factor of $\gamma$. $W(t) = \mu\tau + B$ just before a loss and $W(t) = (\mu\tau + B) \cdot \gamma$ just after. Let $t_0$ be the beginning of one such period after a loss. Consider the case when $W(t_0) = (\mu\tau + B)\gamma < \mu\tau$ and $m > l$. For ease of analysis we assume that the ``Vegas $\beta$'' parameter for the Nice flows is $0$, i.e. the Nice flows additively decrease upon observing round-trip times greater than $\tau$. The window dynamics in any period can be split into three intervals as described below.

Additive Increase, Additive Increase: In this interval $[t_0, t_1]$ both Reno and Nice flows increase linearly. $W(t)$ increases from $W(t_0)$ to $W(t_1) = \mu\tau$, at which point the queue starts building.

Additive Increase, Additive Decrease: This interval $[t_1,t_2]$ is marked by additive increase of $W_r$, but additive decrease of $W_n$ as the `` $\textit{Diff} > \beta$" rule triggers the underlying Vegas controls for the Nice flows. The end of this interval is marked by $W(t_2) = \mu\tau + q_t$.

Additive Increase, Multiplicative Decrease: In this interval $[t_2, t_3]$, $W_n(t)$ multiplicatively decreases in response to observing queue lengths above $q_t$. However, the rate of decrease of $W_n(t)$ is bounded by the rate of increase of $W_r(t)$, as any faster a decrease will cause the queue size to drop below $q_t$. At the end of this interval $W(t_3) = \mu\tau + B$. At this point, each flow decreases its window size by a factor of $\gamma$, thereby entering into the next period.

In order to quantify the interference experienced by Reno flows because of the presence of Nice flows, we formulate differential equations to represent the variation of the queue size in a period. We then show that the values of $W_r$ and $W_n$ at the beginning of periods stabilize after several losses, so that the length of a period converges to a fixed value. It is then straightforward to compute the total amount of Reno flow sent out in a period. We show in the technical report [49] that the interference $I$, defined as the fractional loss in throughput experienced by Reno flows because of the presence of Nice flows, is given as follows.

Theorem 1: The interference $I$ is given by

$$I \leq \frac {4m\cdot e^{(-\frac {B(1-t)\gamma} {m})}} {(\mu\tau + B)\gamma}$$ (1)

The derivation of $I$ indicates that all three design features of Nice are fundamentally important for reducing interference. The interference falls exponentially with $B(1-t)$ or $B-q_t$, which reflects the time that Nice has to multiplicatively back off before packet losses occur. Intuitively, multiplicative decrease allows any number of Nice flows to get out of the way of additively increasing demand flows. The dependence on the ratio $\frac {B} {m}$ suggests that as the number of demand flows approaches the maximum queue size the non-interference property starts to break down. This breakdown is not surprising as each flow barely gets to maintain one packet in the queue and TCP Reno is known to behave anomalously under such circumstances  [35]. In a well designed network, when $B\gg m$, it can be seen that the dependence on the threshold $t$ is weak, i.e. interference is small when $t$ is, and careful tuning of the exact value of $t$ in this region is unnecessary. Our full analysis shows that the above bound on $I$ holds even for the case when $m \ll l$. Allowing window sizes to multiplicatively decrease below one is crucial in this proof.