# Smart-RED: A Novel Congestion Control Mechanism for High Throughput and Low Queuing Delay

Authors: Armir Bujari; Andrea Marin; Claudio E. Palazzi; Sabina Rossi
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## 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.


---

## Body

## 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: (1) when TCP connections are greedy, i.e., all of them need the highest available bandwidth, and (2) when the UDP traffic is constant or changes slowly in time. When condition (1) is violated, SAP-LAW unnecessarily allocates portions of bandwidth to TCP connections causing a reduction of the AP utilization, while when condition (2) 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 (minth) is exceeded. The introduction of the minimum threshold reduces the effects of the violation of condition (1). The application of the ECN/RED when the queue length is greater than another threshold maxth>minth ensures that the AP is never congested (and hence the problems of the violation of condition (2) 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 Section2, 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: minth and maxth. It accepts all the packets when the queue length ql at the access point is less than the minimum threshold minth. When ql is between the minimum and the maximum thresholds, each arriving packet is marked with a probability p, which is a function depending on ql. If ql is greater than or equal to the maximum threshold maxth, 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] is(1)maxTCPtraffict=C-UDPtraffict#TCPflowst,where UDPtraffic(t) is the amount of bandwidth occupied by the real-time applications at time t, C is the capacity of the bottleneck link, and #TCPflows(t) is the number of TCP connections at time t. 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 ofN objects belonging to distinct classes. The state of an object is represented by a pair (c,i), where c∈Γ is the class of the object and i∈Ec={1,…,Sc} is its internal state. Objects can interact with the environment and change their state.LetXnN(t) be the state of the n-th object at time slot t, and let K(c,i),(c,j)N(t) be the probability that an object of class c goes from state i to state j during the time slot t.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 byR→N(t)∈Rd, where d 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 theoccupancy measure, M→N(t), a vector whose components Mc,iN(t) represent the proportion of objects that are in state (c,i) at time t, i.e.,(2)Mc,iNt=1N∑n=1N1XnNt=c,i, where 1x=(c,i) is the indicator function. If we condition on the object class, we have that the proportion of class c objects in state i at time t is (1/pc)Mc,iN(t), where pc=∑i=1ScMc,i(t).To govern the system dynamics, we assume that there is a deterministic continuous functiong that, given the states of the memory and of the occupancy vector, updates the state of the memory:(3)R→Nt+1=gR→Nt,M→Nt+1.In conclusion,∀n we have(4)PXnNt+1=c,j∣R→Nt=r→,XnNt=c,i=Kc,i,c,jNr→.K(c,i),(c,j)N is the transition probability from state (c,i) to state (c,j) and it depends on the memory state. Therefore we assume K(c,i),(c,j)N(r→)≥0 and ∑j=1ScK(c,i),(c,j)N(r→)=1 for all 1≤i≤Sc.According to [10], we assume the following.Assumption 2.
∀ c ∈ Γ , ∀ i , j ∈ E c, and for N→∞, K(c,i),(c,j)N(r→) converges uniformly in r→ to some K(c,i),(c,j)(r→), which is a continuous function of r→.A sufficient condition for this assumption to be satisfied is that the transition matrixKN(r→) does not depend on the number of objects N and that is continuous on r→, 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 measureM→N(0) and memory R→N(0) converge almost surely to deterministic limits μ→(0), ρ→(0) and for t≥0,(5)μ→t+1=μ→tKρ→t(6)ρ→t+1=gρ→t,μ→t+1.Then for any fixed time t, almost surely(7)limN→∞=μ→t,limN→∞R¯Nt=ρ→t.


## 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 thresholdsminth and maxth and behaves as SAP-LAW when the queue length is between minth and maxth; i.e., the advertised window is computed using (1). When the queue length is lower than minth or greater than maxth, 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 Algorithm1.Algorithm 1:Smart-RED Algorithm.
( 1 )   for  each arriving packet  do ( 2 )  if  ql<minth  then ( 3 ) accept that packet ( 4 )  else if  minth≤ql<maxth  then ( 5 )  set  rwnd= (C-UDPtraffic)/#TCPflows ( 6 )  else if  maxth≤ql  then ( 7 ) mark that packet ( 8 )  end if ( 9 )   end for


## 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 p and the UDP sources denoted by u. 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 Np and Nu denote the number of objects associated with TCP and UDP flows, respectively, and N=Np+Nu, while pp=Np/N and pu=Nu/n 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 Ip states, ranging from 1 to Ip. When the window is in state i∈[1,…,Ip], then the sender can transmit sp(i)∈N packets in a time slot. sp is a monotonically increasing function and, henceforth, we assume that it has the form sp(i)=αi for some α∈N+.Each TCP agent state encodes the state of its sending window and the number of packets that have still to be sent denoted bys∈[1,…,sp(Ip)+1], where Ip+1 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 Mp,i,sN(t), where p denotes the TCP class, i the state of the window, and s the backlog of the packets. The proportion of TCP connections in state (i,s) at time t is then pp-1Mp,i,sN(t).(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 Iu states ranging from 1 to Iu. When an UDP agent is in state i∈[1,…,Iu] it sends su(i)∈N packets in a time slot. The occupancy measure for UDP agents is denoted by Mu,iN(t) and the proportion of UDP agents in state i at time t is then pu-1Mu,iN(t).(c) Modelling the State of the Memory.We assume the bottleneck to have a capacity of C 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 Y of the round trip time; i.e., ξ(t)=y(SuN(t-Y),…SuN(t-1)), where ξ(t) denotes the intensity of the UDP traffic estimated at time t. Thus, the memory R→N(t)=(RcN(t),RpN(t),R→uN(t)) is a pair of real numbers (rc,rp) followed by a vector of reals r→u where rc denotes the normalised queue length at the bottleneck (counting both TCP and UDP packets) at a given time slot, while rp is the normalised queue length at the previous time slot and r→u=(ru0,…,ruY) denotes the normalized counting of the arrived UDP packets at the latest (Y+1)>1 time slots. We will denote by r→ a possible element of R→N(t). The dynamic of the memory is specified by the following equations:(8)RcNt+1=max⁡RcNt+SpNt+1+SuNt+1-C,0,RpNt+1=RcNt,RuiNt+1=Rui-1Nt,1≤i≤Y,Ru0Nt+1=SuNt+1.SpN(t+1) and SuN(t+1) 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 (9)SuNt=∑iIusuiMu,iNt.On the other hand, the traffic generated by the TCP agents is more complicated and follows the rules specified in Section 4:(10)SpNt=∑i=1Ip∑s=1spIp+1Mp,i,st+1·mins,sphR→uNt·1RuNt≥minth+Mp,i,st+1min⁡spi,s·1RuNt<minth 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 h is defined as follows:(11)hr→u=arg⁡maxj⁡spj,spj≤C-y~r→u1pp∨j=1,and y~(r→u)=y(ru1,…,ruY).(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:(12)τs′=w1-ws′-11s′≤spIp+1-wspIp1s′=SpIp+1(13)Kp,i,s,p,i+1,s′r→=1-qrpspi·1i<Ip,s>spi,rp<minthτs′+1-qrpmins,sphR→uNt·1i<Ip,s>mins,sphR→uNt,rp≥minthτs′(14)Kp,i,s,p,1,s′r→=1s≤spiτs′(15)Kp,Ip,s,p,Ip,s′=1-qrpspIp1s>spi,rp<minthτs′+1-qrpmins,sphR→uNt·1s>mins,sphR→uNt,rp≥minthτs′(16)Kp,i,s,p,di,s′=1-1-qrpspi·1s>spi,rp<minthτs′+1-1-qrpmin⁡s,sphR→uNt·1s>min⁡s,sphR→uNt,rp≥minthτs′Function h(r→u) is defined in (11), while Function τ is the density function of a truncated geometric random variable, where the probability mass of outcomes greater than sp(Ip) is concentrated in the last state, sp(Ip)+1 (see [29]). Function d(i) is used to model the destination state in case of a marked packet. As in [9] we have d(i)=⌊i/2⌋ (and the number of packets sent sp(i) is proportional to i). Equation (13) controls the transition from state i to i+1 of a TCP window. Equation (14) defines the transition to the window size 1 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 q(RpN(t)) is specified in the following equation:(17)qRpNt=0ifRpNt<maxth1ifRpNt≥maxth(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(18)Ku,i,u,jr→=κu,i,u,j,1≤i,j≤Iuκ(u,i),(u,j)∈[0,1] and for all i∈[1,Iu] we have(19)∑j=1Iuκu,i,u,j=1.We are now in position to give the most important result of this section, i.e., the mean field model corresponding to the limit forN→∞ of the described probabilistic model.Proposition 4.
IfM→N(0) and RN(0) converge almost surely to μ→(0) and ρ→(0), respectively, and ∀i=1,…,Ip it holds that Mp,i,sN(0)/∑s′=1sp(Ip)+1Mp,i,s′ converge almost surely to τ(s), as N→∞, then for any finite horizon t we have that (20)limN→∞∑s=1spIp+1Mp,i,sNt=μ~p,itlimN→∞Mu,iNt=μu,itlimN→∞R→Nt=ρ→t almost surely, where μ~p,i(t), μu,i(t), and ρ(t) are defined by the Iteration system for Smart-RED model with TCP connections as follows:(21)μ~p,1t+1=∑j:dj=11-1-qρptmin⁡spj,sphρ→utμ~jt1-wminspj,sphρ→ut.1ρpt≥minth+∑j:dj=11-1-qρptspjμ~jt1-wspj.1ρpt<minth+∑j=1Ipμ~p,jt1-1-wminspj,sphρ→ut.1ρpt≥minth+μ~p,jt1-1-wspj.1ρpt<minthμ~p,it+1=∑j:dj=i1-1-qρptmin⁡spj,sphρ→utμ~jt1-wminspj,sphρ→ut.1ρpt≥minth+∑j:dj=i1-1-qρptspjμ~jt1-wspj.1ρpt<minth+1-qρptminspi-1,sphρ→utμ~p,i-1t1-wminspi-1,sphρ→ut.1ρpt≥minth+1-qρptspi-1μ~p,i-1t1-wspi-1.1ρpt<minth1<i<Ipμ~p,Ipt+1=1-qρptminspIp-1,sphρ→utμ~p,Ip-1t1-wminspIp-1,sphρ→ut.1ρpt≥minth+1-qρptspIp-1μ~p,Ip-1t1-wspIp-1.1ρpt<minth+1-qρptminspIp,sphρ→utμ~p,Ipt1-wminspIp,sphρ→ut.1ρpt≥minth+1-qρptspIpμ~p,Ipt1-wspIp.1ρpt<minthμu,it+1=∑j=1Iuκu,j,u,iμu,jtσpt+1=∑i=1Ipμ~p,it+11-1-wspiw.1ρpt<minth+μ~p,it+11-1-wminspi,sphρ→ctw.1ρpt≥minthσut+1=∑i=1Iuμu,it+1suiρct+1=maxρct+σpt+1+σut+1-C,0ρpt+1=ρctρuc+1t+1=ρuct,0≤c<Yρu0t+1=σut+1


### 5.2. Model for ECN/RED

We previously defined a model for ECN/RED following the principles described in this paper in [29]. In order to keep the paper self-contained we briefly discuss how it is possible to derive the model of [29] from the one proposed here. First, we desire our Smart-RED to work only in the ECN/RED policy. We can achieve this by setting minth=maxth=∞. Moreover, since we do not observe the history of UDP packets we have to evict the vector R→uN(t) from the memory state R→N(t). Finally, we need to update the packet marking function as follows [6, 7, 30]:(22)qRpNt=1-exp-γRpNt


### 5.3. Model for SAP-LAW

Analogously of what we have done for the ECN/RED, we can derive the model for SAP-LAW as special case of that proposed for Smart-RED. In fact, we can just setminth=0 and maxth=∞ in order to force Smart-RED to work exactly as if it were a SAP-LAW protocol.


## 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 p and the UDP sources denoted by u. 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 Np and Nu denote the number of objects associated with TCP and UDP flows, respectively, and N=Np+Nu, while pp=Np/N and pu=Nu/n 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 Ip states, ranging from 1 to Ip. When the window is in state i∈[1,…,Ip], then the sender can transmit sp(i)∈N packets in a time slot. sp is a monotonically increasing function and, henceforth, we assume that it has the form sp(i)=αi for some α∈N+.Each TCP agent state encodes the state of its sending window and the number of packets that have still to be sent denoted bys∈[1,…,sp(Ip)+1], where Ip+1 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 Mp,i,sN(t), where p denotes the TCP class, i the state of the window, and s the backlog of the packets. The proportion of TCP connections in state (i,s) at time t is then pp-1Mp,i,sN(t).(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 Iu states ranging from 1 to Iu. When an UDP agent is in state i∈[1,…,Iu] it sends su(i)∈N packets in a time slot. The occupancy measure for UDP agents is denoted by Mu,iN(t) and the proportion of UDP agents in state i at time t is then pu-1Mu,iN(t).(c) Modelling the State of the Memory.We assume the bottleneck to have a capacity of C 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 Y of the round trip time; i.e., ξ(t)=y(SuN(t-Y),…SuN(t-1)), where ξ(t) denotes the intensity of the UDP traffic estimated at time t. Thus, the memory R→N(t)=(RcN(t),RpN(t),R→uN(t)) is a pair of real numbers (rc,rp) followed by a vector of reals r→u where rc denotes the normalised queue length at the bottleneck (counting both TCP and UDP packets) at a given time slot, while rp is the normalised queue length at the previous time slot and r→u=(ru0,…,ruY) denotes the normalized counting of the arrived UDP packets at the latest (Y+1)>1 time slots. We will denote by r→ a possible element of R→N(t). The dynamic of the memory is specified by the following equations:(8)RcNt+1=max⁡RcNt+SpNt+1+SuNt+1-C,0,RpNt+1=RcNt,RuiNt+1=Rui-1Nt,1≤i≤Y,Ru0Nt+1=SuNt+1.SpN(t+1) and SuN(t+1) 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 (9)SuNt=∑iIusuiMu,iNt.On the other hand, the traffic generated by the TCP agents is more complicated and follows the rules specified in Section 4:(10)SpNt=∑i=1Ip∑s=1spIp+1Mp,i,st+1·mins,sphR→uNt·1RuNt≥minth+Mp,i,st+1min⁡spi,s·1RuNt<minth 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 h is defined as follows:(11)hr→u=arg⁡maxj⁡spj,spj≤C-y~r→u1pp∨j=1,and y~(r→u)=y(ru1,…,ruY).(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:(12)τs′=w1-ws′-11s′≤spIp+1-wspIp1s′=SpIp+1(13)Kp,i,s,p,i+1,s′r→=1-qrpspi·1i<Ip,s>spi,rp<minthτs′+1-qrpmins,sphR→uNt·1i<Ip,s>mins,sphR→uNt,rp≥minthτs′(14)Kp,i,s,p,1,s′r→=1s≤spiτs′(15)Kp,Ip,s,p,Ip,s′=1-qrpspIp1s>spi,rp<minthτs′+1-qrpmins,sphR→uNt·1s>mins,sphR→uNt,rp≥minthτs′(16)Kp,i,s,p,di,s′=1-1-qrpspi·1s>spi,rp<minthτs′+1-1-qrpmin⁡s,sphR→uNt·1s>min⁡s,sphR→uNt,rp≥minthτs′Function h(r→u) is defined in (11), while Function τ is the density function of a truncated geometric random variable, where the probability mass of outcomes greater than sp(Ip) is concentrated in the last state, sp(Ip)+1 (see [29]). Function d(i) is used to model the destination state in case of a marked packet. As in [9] we have d(i)=⌊i/2⌋ (and the number of packets sent sp(i) is proportional to i). Equation (13) controls the transition from state i to i+1 of a TCP window. Equation (14) defines the transition to the window size 1 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 q(RpN(t)) is specified in the following equation:(17)qRpNt=0ifRpNt<maxth1ifRpNt≥maxth(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(18)Ku,i,u,jr→=κu,i,u,j,1≤i,j≤Iuκ(u,i),(u,j)∈[0,1] and for all i∈[1,Iu] we have(19)∑j=1Iuκu,i,u,j=1.We are now in position to give the most important result of this section, i.e., the mean field model corresponding to the limit forN→∞ of the described probabilistic model.Proposition 4.
IfM→N(0) and RN(0) converge almost surely to μ→(0) and ρ→(0), respectively, and ∀i=1,…,Ip it holds that Mp,i,sN(0)/∑s′=1sp(Ip)+1Mp,i,s′ converge almost surely to τ(s), as N→∞, then for any finite horizon t we have that (20)limN→∞∑s=1spIp+1Mp,i,sNt=μ~p,itlimN→∞Mu,iNt=μu,itlimN→∞R→Nt=ρ→t almost surely, where μ~p,i(t), μu,i(t), and ρ(t) are defined by the Iteration system for Smart-RED model with TCP connections as follows:(21)μ~p,1t+1=∑j:dj=11-1-qρptmin⁡spj,sphρ→utμ~jt1-wminspj,sphρ→ut.1ρpt≥minth+∑j:dj=11-1-qρptspjμ~jt1-wspj.1ρpt<minth+∑j=1Ipμ~p,jt1-1-wminspj,sphρ→ut.1ρpt≥minth+μ~p,jt1-1-wspj.1ρpt<minthμ~p,it+1=∑j:dj=i1-1-qρptmin⁡spj,sphρ→utμ~jt1-wminspj,sphρ→ut.1ρpt≥minth+∑j:dj=i1-1-qρptspjμ~jt1-wspj.1ρpt<minth+1-qρptminspi-1,sphρ→utμ~p,i-1t1-wminspi-1,sphρ→ut.1ρpt≥minth+1-qρptspi-1μ~p,i-1t1-wspi-1.1ρpt<minth1<i<Ipμ~p,Ipt+1=1-qρptminspIp-1,sphρ→utμ~p,Ip-1t1-wminspIp-1,sphρ→ut.1ρpt≥minth+1-qρptspIp-1μ~p,Ip-1t1-wspIp-1.1ρpt<minth+1-qρptminspIp,sphρ→utμ~p,Ipt1-wminspIp,sphρ→ut.1ρpt≥minth+1-qρptspIpμ~p,Ipt1-wspIp.1ρpt<minthμu,it+1=∑j=1Iuκu,j,u,iμu,jtσpt+1=∑i=1Ipμ~p,it+11-1-wspiw.1ρpt<minth+μ~p,it+11-1-wminspi,sphρ→ctw.1ρpt≥minthσut+1=∑i=1Iuμu,it+1suiρct+1=maxρct+σpt+1+σut+1-C,0ρpt+1=ρctρuc+1t+1=ρuct,0≤c<Yρu0t+1=σut+1


## 5.2. Model for ECN/RED

We previously defined a model for ECN/RED following the principles described in this paper in [29]. In order to keep the paper self-contained we briefly discuss how it is possible to derive the model of [29] from the one proposed here. First, we desire our Smart-RED to work only in the ECN/RED policy. We can achieve this by setting minth=maxth=∞. Moreover, since we do not observe the history of UDP packets we have to evict the vector R→uN(t) from the memory state R→N(t). Finally, we need to update the packet marking function as follows [6, 7, 30]:(22)qRpNt=1-exp-γRpNt


## 5.3. Model for SAP-LAW

Analogously of what we have done for the ECN/RED, we can derive the model for SAP-LAW as special case of that proposed for Smart-RED. In fact, we can just setminth=0 and maxth=∞ in order to force Smart-RED to work exactly as if it were a SAP-LAW protocol.


## 6. Performance Evaluation

In this section, we evaluate the performance of Smart-RED with ECN/RED and SAP-LAW. A mean field model is implemented to compare the three different protocols with respect to the following performance indices: expected queue lengthQ (expressed in normalized number of packets at the AP) and throughput T (expressed in normalized sent packets per time slot). To this end, we consider different scenarios. All the mean field simulations performed in the following sections share the following set of parameters unless differently specified: Ip=100, Iu=15, C=500, sp(i)=10i, minth=30, maxth=1500, pu=0.3, pp=0.7, and γ=5E-6.We point out that these modelling and simulation approaches have been previously validated by means of simulations performed in NS2 [29].


### 6.1. Instability of SAP-LAW

We assume that each TCP connection sends an expected number of packetsw(ω)-1=1032ω. UDP traffic is bursty; i.e., all the UDP transmissions are synchronised and they have a periodicity of 15 time slots, with a peak traffic of 5E3, 13E3, and 5E3 in consecutive time slots. Under this scenario, for all the values of ω>0, the SAP-LAW is instable so we compare the performances of Smart-RED with ECN/RED which are shown in Figure 2. We observe that Smart-RED, similarly to ECN/RED, is stable although the queue lengths for both the protocols tend to be high. Smart-RED has also a better throughput and a better average queue length under greedy TCP connections.Figure 2
Comparison of ECN/RED and Smart-RED under heavily bursty UDP traffic.


### 6.2. Comparison of the Protocols under Slightly Bursty UDP Traffic

In this experiment we have the same setting of Section6.1 but the UDP is less bursty; i.e., the peak traffic is 1E3, 3E3, and 1E3 in consecutive time slots. The results of the simulations are shown in Figure 3. Notice that Smart-RED improves the throughput of the SAP-LAW for both greedy and nongreedy TCP connections. In case of nongreedy TCP connections it mitigates the issues of SAP-LAW while maintaining a better performance than the ECN/RED in case of greedy TCP. On the other hand, the improvement of the throughput with respect to the SAP-LAW is paid with a greater expected queue length.Figure 3
Comparison of ECN/RED and Smart-RED under lightly bursty UDP traffic.


### 6.3. Comparison of the Protocols under Smooth UDP Traffic

Smooth UDP traffic is the ideal scenario for SAP-LAW. In this case we consider the same definition of a UDP agent given in the previous section, but the agents are not synchronised. In mean field regime, this leads to a smooth UDP traffic. The simulation results are shown in Figure4. In this case, Smart-RED shows the highest throughput. With respect to ECN/RED it also maintains a lower queue length, while it pays the gain in terms of throughput with respect to the SAP-LAW with a longer expected queue.Figure 4
Comparison of ECN/RED under smooth UDP traffic.


## 6.1. Instability of SAP-LAW

We assume that each TCP connection sends an expected number of packetsw(ω)-1=1032ω. UDP traffic is bursty; i.e., all the UDP transmissions are synchronised and they have a periodicity of 15 time slots, with a peak traffic of 5E3, 13E3, and 5E3 in consecutive time slots. Under this scenario, for all the values of ω>0, the SAP-LAW is instable so we compare the performances of Smart-RED with ECN/RED which are shown in Figure 2. We observe that Smart-RED, similarly to ECN/RED, is stable although the queue lengths for both the protocols tend to be high. Smart-RED has also a better throughput and a better average queue length under greedy TCP connections.Figure 2
Comparison of ECN/RED and Smart-RED under heavily bursty UDP traffic.


## 6.2. Comparison of the Protocols under Slightly Bursty UDP Traffic

In this experiment we have the same setting of Section6.1 but the UDP is less bursty; i.e., the peak traffic is 1E3, 3E3, and 1E3 in consecutive time slots. The results of the simulations are shown in Figure 3. Notice that Smart-RED improves the throughput of the SAP-LAW for both greedy and nongreedy TCP connections. In case of nongreedy TCP connections it mitigates the issues of SAP-LAW while maintaining a better performance than the ECN/RED in case of greedy TCP. On the other hand, the improvement of the throughput with respect to the SAP-LAW is paid with a greater expected queue length.Figure 3
Comparison of ECN/RED and Smart-RED under lightly bursty UDP traffic.


## 6.3. Comparison of the Protocols under Smooth UDP Traffic

Smooth UDP traffic is the ideal scenario for SAP-LAW. In this case we consider the same definition of a UDP agent given in the previous section, but the agents are not synchronised. In mean field regime, this leads to a smooth UDP traffic. The simulation results are shown in Figure4. In this case, Smart-RED shows the highest throughput. With respect to ECN/RED it also maintains a lower queue length, while it pays the gain in terms of throughput with respect to the SAP-LAW with a longer expected queue.Figure 4
Comparison of ECN/RED under smooth UDP traffic.


## 7. Conclusion

In this paper we have proposed a novel algorithm, named Smart-RED, employed to avoid congestion at a shared AP. To this aim, we combined the features of the well-known ECN/RED with those of the more recent SAP-LAW. The latter shows the best performances when UDP traffic varies slowly in time and the TCP connections need the maximum available bandwidth. We showed that when these conditions are violated, SAP-LAW may be unable to prevent congestion occurring at the AP. Similarly to ECN/RED, Smart-RED is unconditionally stable provided that the UDP traffic does not flood the AP.We showed that in case of heavy burstiness of the UDP traffic, Smart-RED reacts better than ECN/RED (while SAP-LAW is not applicable). On the other hand, in case of greedy TCP and smooth UDP traffic, SAP-LAW remains the best choice even if Smart-RED performs better than ECN/RED. Notice that Smart-RED works exactly as SAP-LAW if the lowest threshold is set to0 and the higher is set to ∞. Therefore, a self-adjusting policy of the thresholds based on the traffic measurements could be studied.In conclusion, Smart-RED exploits the idea of SAP-LAW but eliminates the problem of the possible instability and reduces the throughput sufferance in case of TCP connections with different transmission needs. On the other hand, Smart-RED pays these achievements with longer expected waiting times in the ideal work scenarios of ECN/RED or SAP-LAW.



---

*Source: 6941248-2019-04-04.xml*