Abstract

We consider the scenario in which several TCP connections share the same access point (AP) and a congestion avoidance/control mechanism is adopted with the aim of assigning the available bandwidth to the clients with a certain fairness. When UDP traffic with real-time requirements is present, the problem becomes even more challenging. Very well-known congestion avoidance mechanisms are the Random Early Detection (RED) and the Explicit Congestion Notification (ECN). More recently, the Smart Access Point with Limited Advertised Window (SAP-LAW) has been proposed. Its main idea is that of computing the maximum TCP rate for each connection at the bottleneck, taking into account the UDP traffic to keep a low queue size combined with a reasonable bandwidth utilization. In this paper, we propose a new congestion control mechanism, namely, Smart-RED, inspired by SAP-LAW heuristic formula. We study its performance by using mean field models and compare the behaviours of ECN/RED, SAP-LAW, and Smart-RED under different scenarios. We show that while Smart-RED maintains some of the desirable properties of the SAP-LAW, it solves the problems it may have in case of bursty UDP traffic or TCP connections with very different needs of bandwidth.

1. Introduction

Nowadays, the use of a single access point (AP) to retrieve Internet contents both with and without real-time requirements is a widespread scenario. In this context, the AP bandwidth must be assigned to the set of clients according to some principles which are not always easy to satisfy given the well-known problems connected with priority labeling of the Internet traffic (see, e.g., [1]). The TCP congestion control has been used to regulate the connection sending rates in presence of a bottleneck such as an AP [2–5]. The goal is to provide a fair assignment of the bandwidth to each TCP flow sharing the bottleneck. This can be achieved at the AP by implementing classic algorithms such as the Random Early Detection (RED) [6] and the Explicit Congestion Notification (ECN) [7]. These approaches are based on a random selection of the packets enqueued at the AP which are marked and discarded (RED) or an explicit notification with a request to slow down that is sent to the sender (ECN). In both cases, the TCP reacts by reducing its congestion window size (assuming a packet loss in case of RED). ECN/RED has been widely studied in the literature (see, e.g., [8–11]) and shown effective in regulating the TCP traffic. Nevertheless, ECN/RED takes into account only the TCP traffic and ignores the UDP since the latter, at the transport layer, does not provide any mechanism for regulating the transmission rate. In [12] the authors show that, in some cases, greedy TCP connections may occupy great part of the AP bandwidth and this directly penalizes the performance of UDP traffic whose packets have to wait in the queue. Unfortunately, if queueing time is usually not a big issue for TCP traffic (e.g., file downloading) it represents a serious problem for UDP communications which are often not delay tolerant. This problem is further exacerbated in absence of buffer management techniques in routers [13–15]. At the access tier, the IEEE 802.11e standard was proposed to allow different classes of traffic to provide different QoS levels especially in terms of achieved throughput. Unfortunately, it does not guarantee low per-packet delays and the problem of having the traffic properly marked without risk of errors or cheating still remains along with several other problems jeopardizing its deployability [16, 17].

Instead, in [12] the authors proposed the Smart Access Point with Limited Advertising Window (SAP-LAW) which exploits the flux control mechanism of regular TCP implementations. The algorithm was then further refined in [18] to be used also in cloud systems. In practice, the AP hijacks the acknowledgement packets by changing the advertising window size to a computed size which allows a queue length near to zero. The size is simply computed as the AP’s TCP capacity, i.e., the difference between its total capacity and an estimation of the instantaneous UDP traffic, divided by the number of active TCP connections. This approach has been shown to be effective under two conditions: when TCP connections are greedy, i.e., all of them need the highest available bandwidth, and when the UDP traffic is constant or changes slowly in time. When condition is violated, SAP-LAW unnecessarily allocates portions of bandwidth to TCP connections causing a reduction of the AP utilization, while when condition is violated the protocol may fail to keep a short queue length. Indeed, since SAP-LAW never considers the queue length in its decision-making algorithm (it is based only on the estimation of the instantaneous UDP traffic), a bursty UDP traffic may cause the congestion of the AP as we discuss later on in Section 2.

In this paper, we combine ECN/RED and SAP-LAW in a new protocol called Smart-RED which aims at solving the drawbacks of SAP-LAW. In Smart-RED the SAP-LAW algorithm is activated only when a threshold () is exceeded. The introduction of the minimum threshold reduces the effects of the violation of condition . The application of the ECN/RED when the queue length is greater than another threshold ensures that the AP is never congested (and hence the problems of the violation of condition are overcome). In order to compare the performance of the protocols, we assume a large number of TCP connections and agents employing UDP transmissions, all going through a common AP in order to access the Internet. We show that the model converges to a mean field regime, allowing us to perform an efficient deterministic simulation of the system and a consequent computation of the performance indices.

A large number of papers have studied the performance of TCP and ECN; see [8, 19–21] as a not exhaustive list, but the main focus is on the behavior of a single TCP connection under various scenarios. Other works focused on the specific TCP versions installed by default in the Linux and Windows operating systems and developed models studying their performance [22–24]. More similar to the analysis carried out here are those proposed in [9, 25, 26] where the authors consider the overall system performance in the mean field limit for ECN/RED. The theoretical results proposed in [9] are then extended in [10]. Starting from these two papers we extend the considered model in several directions, as discussed later on, and we propose new ones for SAP-LAW and Smart-RED. Mean field theory (see, e.g., [10, 27, 28]) is an important approach used to study large stochastic models with a deterministic approximation thus overcoming the well-known problem of the state space explosion.

In [29] we propose a mean field model for TCP and UDP traffic handled by ECN/RED or SAP-LAW. With respect to this work, in this paper we introduce a new congestion control mechanism that combines the two previous protocols and compare their performance under different scenarios. While the modelling technique that we use in this paper is close to that of [29], the model that we derive is a nontrivial generalisation of the previous ones. As a consequence, the models for ECN/RED and SAP-LAW presented in [29] can be obtained as different instantiations of the parameters of the model presented in this paper. The results presented in Section 6 are related to the comparison of the performance of the new protocol Smart-RED with ECN/RED and SAP-LAW.

In Section 2, we review the salient features of the congestion control mechanism of TCP protocols and those of ECN, RED, and SAP-LAW algorithms, respectively. In the same section, we discuss some issues associated with the latter protocol. In Section 3 we explain the theoretical background, introduce the notation, and enunciate the mean field theorem that is used to prove the convergence of the models. Next, in Section 4, we describe the Smart-RED novel approach. In Section 5, we develop the models for RED, SAP-LAW, and Smart-RED used in Section 6 to compare the protocols under different scenarios. Finally, in Section 7 we give some final remarks and conclude our paper.

2. TCP and Congestion Control

In this section, we briefly review the congestion control mechanism implemented by the ECN/RED and SAP-LAW algorithms.

(a) ECN/RED. Let us consider a set of clients equipped with a TCP implementation sharing an Internet connection via a wireless access point. ECN and RED are used in conjunction as congestion avoidance mechanism working at the access point in order to regulate the TCP window sizes with the aim of preventing congestion at the AP. In this paper we consider TCP connections over a ECN/RED AP as done in [9, 10]. ECN/RED works with two thresholds: and . It accepts all the packets when the queue length at the access point is less than the minimum threshold . When is between the minimum and the maximum thresholds, each arriving packet is marked with a probability , which is a function depending on . If is greater than or equal to the maximum threshold , all the incoming packets will be marked. Either all the marked packets are dropped or a notification of congestion is sent to the client depending on whether the RED is used in conjunction with ECN. Notice that ECN/RED exploits only the TCP congestion control protocol and it does not regulate the UDP traffic.

(b) SAP-LAW. SAP-LAW is a solution proposed in [12] with the specific aim of addressing the problems caused by the simultaneous presence of both TCP and UDP-based applications. The basic idea is to find a trade-off between throughput and time delay. This is achieved by dynamically modifying the TCP sending rate in order to avoid congestion while guaranteeing a high utilization of the bandwidth. The key factor is to determine the upper bound for the TCP sending rate as a function of the amount of UDP traffic. In this way, we are always sure to reserve enough bandwidth for the real-time application activities. The general formula proposed by Palazzi et al. [12] iswhere is the amount of bandwidth occupied by the real-time applications at time , is the capacity of the bottleneck link, and is the number of TCP connections at time . SAP-LAW regulates the TCP sending rate by taking into account both the TCP and the UDP traffic. The approach provides an optimal solution when TCP connections are trying to utilize the highest possible bandwidth and when UDP traffic is smooth. However, two major issues arise: first, when UDP traffic is bursty, SAP-LAW may not be able to avoid congestion (see Proposition 1) and second, it allocates the same bandwidth to TCP connections with low and high bandwidth requirements, which might lead to a low utilization of the channel.

Proposition 1. When the peaks of the sending rates of UDP agents are periodically higher than the AP capacity, then SAP-LAW fails in preventing congestion.

Intuitively, the proof is based on the fact that when SAP-LAW realizes the presence of a peak of UDP traffic, it reduces the TCP sending rate only for the duration of the burst. As a consequence, immediately after, it allows an aggressive behaviour of the TCP connections. If the sending rate during the peak is higher than the AP capacity, the consequence is that the queue which is left at that time slot is not consumed.

3. Theoretical Background

Mean field theory is widely used in many research domains, including Physics, Epidemiology, and Computer Science. The main idea behind this analysis technique is that the interaction of many objects whose behaviour is stochastic tends to become deterministic, at least from the prospective of an observer that does not distinguish the identity of a single object but knows the fraction of them that is in a certain state at a certain time. In this paper, we refer to the mean field results proposed by Le Boudec et al. in [10].

Let us consider a system consisting of objects belonging to distinct classes. The state of an object is represented by a pair , where is the class of the object and is its internal state. Objects can interact with the environment and change their state.

Let be the state of the -th object at time slot , and let be the probability that an object of class goes from state to state during the time slot .

The peculiarity of this approach to mean field is that the model has a memory which may affect the behaviour of the objects. We represent this memory by , where is some fixed integer. As stated before, in the mean field analysis, the observer cannot see the state of a single object, but it is able to see the fraction of objects that are in certain state. For this reason, we introduce the occupancy measure, , a vector whose components represent the proportion of objects that are in state at time , i.e., where is the indicator function. If we condition on the object class, we have that the proportion of class objects in state at time is , where .

To govern the system dynamics, we assume that there is a deterministic continuous function that, given the states of the memory and of the occupancy vector, updates the state of the memory:

In conclusion, we have is the transition probability from state to state and it depends on the memory state. Therefore we assume and for all .

According to [10], we assume the following.

Assumption 2. , and for , converges uniformly in to some , which is a continuous function of .

A sufficient condition for this assumption to be satisfied is that the transition matrix does not depend on the number of objects and that is continuous on , which is always the case in our examples. We conclude this section by presenting Theorem 1 of [10]. The theorem will be widely used in the modelling sections of this paper and is a formalisation of what has been informally described at the beginning of this section.

Theorem 3. Assume that the initial occupancy measure and memory converge almost surely to deterministic limits , and for ,Then for any fixed time , almost surely

4. Smart-RED: A Novel Approach

In this section, we describe the algorithm that we propose for the congestion control problem at the AP: Smart-RED. This is based on a combination of ECN/RED and SAP-LAW. In contrast with the SAP-LAW, but similarly to ECN/RED, Smart-RED is unconditionally stable. However, it resorts to the SAP-LAW flux control approach only when the queue length is greater than a given threshold. Smart-RED works with two thresholds and and behaves as SAP-LAW when the queue length is between and ; i.e., the advertised window is computed using (1). When the queue length is lower than or greater than , the Smart-RED algorithm behaves as RED (see Figure 1).

Figure 1 

Smart-RED: regions of application of ECN/RED and SAP-LAW control policies.

Smart-RED works as described in Algorithm 1.

5. Models for Smart-RED, ECN/RED, and SAP-LAW

Smart-RED combines the ECN/RED and the SAP-LAW techniques to overcome the drawbacks of these two approaches to the problem of congestion control. In this section we propose three different models for ECN/RED, SAP-LAW, and Smart-RED, respectively, in order to study their performance in the following scenarios.(i)We consider the UDP traffic which may be either bursty or smooth.(ii)We regulate the life cycle of TCP connections in order to be able to study the behaviour of the three protocols according to the bandwidth needs of the TCP connections.

The proposed models are showed to converge to a mean field regime and then they are studied; i.e., we assume that the number of TCP connections and UDP transmissions are very high (tend to be infinite). Henceforth, we will simply talk of a mean field model to refer to a modelling technique that converges to a mean field regime.

5.1. Modelling Smart-RED with UDP Traffic and TCP Connections

The Smart-RED mean field model is derived from that of ECN/RED presented in [29] by applying the SAP-LAW formula to update the memory of the system. We work in a discrete time setting [9, 10, 29] and consider two classes of objects: the TCP flows which will be denoted by and the UDP sources denoted by . We need to distinguish these two types of objects since TCP transmissions have a mechanism to control the transmission rate, while UDP do not. Let and denote the number of objects associated with TCP and UDP flows, respectively, and , while and denote the fraction of TCP and UDP objects, respectively.

(a) Modelling of TCP State. TCP flows use the window mechanisms to control their transmission speed. In particular, each transmitting agent maintains a sending window to store the packets that have not been acknowledged by the receiver yet. The size of these windows determines the transmission speed. In our model, the window of TCP flows can have states, ranging from to . When the window is in state , then the sender can transmit packets in a time slot. is a monotonically increasing function and, henceforth, we assume that it has the form for some .

Each TCP agent state encodes the state of its sending window and the number of packets that have still to be sent denoted by , where denotes the fact that the sender cannot fit all its queue of packets in one time slot. This compact way of storing the remaining packets to be sent takes advantage of the assumption that the TCP flows have geometric distributed sizes. For TCP objects, we have that the occupancy vector components are , where denotes the TCP class, the state of the window, and the backlog of the packets. The proportion of TCP connections in state at time is then .

(b) Modelling the UDP State. UDP flows do not have any window to regulate their transmission rate. We imagine that each application that interacts with our bottleneck is in a state that demands some transmission rate. For each UDP agent we introduce states ranging from to . When an UDP agent is in state it sends packets in a time slot. The occupancy measure for UDP agents is denoted by and the proportion of UDP agents in state at time is then .

(c) Modelling the State of the Memory. We assume the bottleneck to have a capacity of packets for time slot for each object (TCP or UDP) that interacts with it. The memory must allow us to estimate the UDP traffic intensity in the latest interval of time. Therefore, we assume the time interval that we use to estimate the instantaneous arrival rate for the UDP packets to be equal to a multiple of the round trip time; i.e., , where denotes the intensity of the UDP traffic estimated at time . Thus, the memory is a pair of real numbers followed by a vector of reals where denotes the normalised queue length at the bottleneck (counting both TCP and UDP packets) at a given time slot, while is the normalised queue length at the previous time slot and denotes the normalized counting of the arrived UDP packets at the latest time slots. We will denote by a possible element of . The dynamic of the memory is specified by the following equations: and are the total traffic generated by TCP and UDP agents, respectively. The traffic generated by UDP agents is rather simple and can be derived as On the other hand, the traffic generated by the TCP agents is more complicated and follows the rules specified in Section 4: We note that we use the memory to know the UDP traffic at the previous slot and hence to decide the bandwidth available within the minimum and maximum thresholds. Function is defined as follows:and .

(d) Modelling the Change of State of TCP Agents. The state transition matrix for each TCP object in the Smart-RED model is defined as follows:Function is defined in (11), while Function is the density function of a truncated geometric random variable, where the probability mass of outcomes greater than is concentrated in the last state, (see [29]). Function is used to model the destination state in case of a marked packet. As in [9] we have (and the number of packets sent is proportional to ). Equation (13) controls the transition from state to of a TCP window. Equation (14) defines the transition to the window size when a TCP connection ends its transmission and a new one is begun. Equation (15) considers the case in which the window size is at its maximum and remains there (but with a possibly different amount of remaining packets to send). Finally, (16) models the case in which a window reduces its size because a packet waiting for acknowledgement goes in time out due to the marking of ECN/RED. Function is specified in the following equation:

(e) Modelling the Change of State of UDP Agents. The probabilistic description of the behaviour of the agents modelling UDP flows is rather simple since it does not depend on external factors encoded in the memory. Recall that UDP does not have an internal congestion or flow control mechanisms. Thus, we have and for all we have

We are now in position to give the most important result of this section, i.e., the mean field model corresponding to the limit for of the described probabilistic model.

Proposition 4. If and converge almost surely to and , respectively, and it holds that converge almost surely to , as , then for any finite horizon we have that almost surely, where , , and are defined by the Iteration system for Smart-RED model with TCP connections as follows: