تجزیه و تحلیل عملکرد از مکانیسم های AIMD در طول یک مسیر مارکوفی چندحالته

We analyze the performance of an Additive Increase Multiplicative Decrease (AIMD)-like flow control mechanism. The transmission rate is considered to increase linearly in time until the receipt of a congestion notification, when the transmission rate is multiplicatively decreased. AIMD captures the steady state behavior of TCP in the absence of timeouts and in the absence of maximum window size limitation. We introduce a general fluid model based on a multi-state Markov chain for the moments at which the congestion is detected. With this model, we are able to account for correlation and burstiness in congestion moments. Furthermore, we specify several simple versions of our general model and then we identify their parameters from real TCP traces.

We present a framework to study the performance of Additive Increase Multiplicative Decrease (AIMD) type flow control mechanisms. This is the kind of control used by TCP, the widely used transport protocol of the Internet [26]. However, we anticipate that our results will also be applicable for other flow control mechanisms (e.g., the ABR mechanism in ATM networks). We employ a fluid approach [1], [2], [4], [5] and [6] to model the controlled flow. Our model studies a general window-based fluid AIMD mechanism. Our model applies to the TCP protocol when the window size is large enough so that the packet nature of TCP is effectively diluted. The transmission rate of the source is assumed to grow linearly at a rate α. In the case of TCP where the flow is controlled via a congestion window, the transmission rate at any instant is equal to the window size divided by the Round Trip Time (RTT) of the connection. The growth of the transmission rate continues until the source receives a notification of congestion from the network or until the maximum window size is reached. In the case of TCP, the congestion is inferred from the loss of packets. It is an implicit notification compared to the explicit notification used by other flow control protocols as the ABR service in ATM or the ECN proposal in the Internet. We call the moment at which the source reduces its transmission rate a loss event. Upon detection of a loss, the transmission rate is scaled down by a (possibly random) factor a ∈ [0, 1]. The scaling factor depends on many factors. In the case of TCP, it depends on the version used, on the number of packet losses in the congestion period and on the way by which the loss is detected (e.g., duplicate ACKs or Timeout [26]). The Reno version of TCP divides its window by two for every packet loss [12]. The Newreno and SACK versions do not divide their windows by more than two in a RTT, regardless of the number of packet losses during the RTT [12]. We adopt an end-to-end approach for modeling the AIMD congestion control mechanism [8]. The end-to-end approach considers the network as a black box whose output is the process of loss events. The physical characteristics of the network (topology, capacity, etc.) and the parameters of the traffic of other users are all summarized by the process of loss events that we shall consider in our analysis. The opposite of the end-to-end approach is the network specific approach [8] which considers directly the characteristics of the network when modeling the AIMD type protocols (e.g., [3], [10] and [21] for TCP). The advantage of the end-to-end approach is that it can be applied to all networks resulting in the same loss process as that considered by the model. It is clear that the more general the loss process is, the larger the number of networks the model is able to cover. The process of loss events can be seen as a point process, where the appearance of a point corresponds to the appearance of a congestion signal, interpreted as a loss in the context of TCP, causing a reduction in the transmission rate. Different models have been proposed to study the performance of an AIMD mechanism using the end-to-end approach [6], [11], [23] and [20], but these models make in general simple assumptions on the loss process, as periodic, Poisson, iid, etc. These assumptions may not hold on some Internet paths where losses are clustered or when the rate of the loss process changes following some underlying Markov chain. Our aim in this paper is to consider such paths. For example in Fig. 1, one can observe a scenario where the moments of transmission rate reduction are clustered together. This figure corresponds to the window size evolution of a New Reno [12] TCP connection running between two sites at the technology park Sophia Antipolis in south of France. Full-size image (30 K) Fig. 1. TCP window evolution. Figure options Here we would like to explicitly mention that our model provides a framework for analyzing AIMD type flow control mechanisms in general and in particular the AIMD behavior of TCP congestion avoidance phase. We are not claiming to model other features of TCP protocol. In our analysis we only take the loss events from the real TCP connection, and shall employ this real loss process to construct our AIMD mechanism against which we compare our model. Remark 1. Note that Fig. 1 shows, in addition to the slow oscillations in the congestion window caused by the congestion control algorithms of TCP, some quick oscillations. These quick oscillations are caused by the burstiness of TCP. Indeed, we measure the congestion window as the number of packets transmitted by the source and not yet acknowledged (packets in the pipe). But, this number presents quick oscillations due to the arrival in bursts of ACKs and consequently, the transmission in bursts of packets. These quick oscillations can be absorbed by modifying the operating system and reading the content of the variable describing the congestion window of TCP. Normally in the analysis of AIMD mechanisms it is assumed that the window is divided by a constant factor upon congestion detection (e.g., by a factor of two in the case of TCP), but we see in Fig. 1 a more severe reduction due to multiple consecutive divisions of the congestion window by two. When a congestion appears, the network continues dropping packets over multiple round-trip times resulting in these multiple consecutive divisions of the congestion window. In a previous paper [1], we presented a two-state Markovian model to account for such a burstiness of losses. In that paper, we considered a lossy path with two states Good and Bad together with potential loss events. The transmission rate may be reduced upon potential losses. A potential loss can transform into a real loss with probability pG in the Good state and with probability pB in the Bad state (pG ⩽ pB). The time between potential loss events is assumed to be independently and identically distributed. Our main contribution in [1] was to show that the throughput of the flow control mechanism increases with the increase in burstiness of losses when keeping the average loss rate unchanged. We validated the model via simulations, but did not provide any algorithm for the identification of its parameters from real traces. We would like to highlight here that by burstiness of losses, we mean loss events that appear close to each other, and not packets that are lost in bursts. It is known that TCP congestion control suffers when packets are lost in bursts [12]. A loss event in our model can be the result of one or more packet losses. It is an event that results in a reduction of the congestion window. The factor by which the window is reduced can model the number of lost events due to network congestion (or due to some other phenomenon, e.g., noise in wireless networks). The present work is an extension of our previous work [1] to a multi-state Markovian case. Being motivated by some experimental results (e.g., Fig. 1), we allow the path of the connection to be described by more than two states. The need for more than two states for describing the path is also motivated by modeling results from [25] and [28] on mobile satellite channels, where it was shown that one needs typically at least four states. In [1], the scaling factor a is a random variable equal to either 0.5 (the potential loss becomes a real loss) or 1 (a potential loss is not transformed into a real loss). Here, we propose to study the scaling factor with a general distribution that depends on the state of the path. We present then some applications of our general model. These applications can be seen as different ways to infer the parameters of the general model from a real TCP trace. In particular, we provide a method for the parameter identification of our (two-state) model in [1]. A comparison among the different applications is provided to see which one is the most efficient in predicting TCP performance. In the following section, we overview related works on AIMD modeling in general and on TCP modeling in particular. In Section 3, we present our general multi-state multi-reduction model for the AIMD mechanism. This general model is analyzed in Section 4. In Section 5, we provide several particular cases of the general model as well as their application to TCP modeling. We finally conclude in Section 6.

We considered in this paper a multi-state Markov model to describe the loss process experienced by a flow control mechanism that has a linear window increase between losses, and a multiplicative window decrease upon a loss event. The modeling of some channels using a Markov chain with more than two states have long been advocated, see e.g. [25] and [28]. Using an approach based on Laplace–Stieltjes Transform, we derived explicit expressions for the two first moments of the transmission rate of the mechanism just prior to losses, as well as the two first moments of the transmission rate at arbitrary time. The first moment of the transmission rate of the flow-control mechanism at an arbitrary time is often the measure of its throughput. We note that the expression for the second moment of the transmission rate at arbitrary time (call it the second moment of the throughput) could be useful in designing TCP friendly protocols for real time applications [13]. In these applications, other parameters of the linear increase and multiplicative decrease are chosen so as to maintain the same throughput (as a function of the loss process and of the round-trip time) as the original TCP protocol. (The latter requirement on the throughput stems from fairness arguments.) Such applications (e.g., interactive voice or video transmissions) typically require a smaller variance of the transmission rate than the one of the original TCP in order to ensure a reasonable quality of service. In [2] we have succeeded in analyzing non Markovian models for loss events [2], and obtained similar performance measures using a completely different approach (that relies on some covariance functions of the inter-loss times). The approach proposed here, in contrast, leads to formulae that involve only a finite and small number of easily computable parameters. In addition, we proposed here methods for the identification of such parameters.