Achieving 100% Throughput in TCP/AQM Under Aggressive Packet Marking With Small Buffer

This article has been accepted for inclusion in a future issue of this joural.Content is final as presented,with the exception of pagination IEEE/ACM TRANSACTIONS ON NETWORKING Achieving 100%Throughput in TCP/AQM Under Aggressive Packet Marking With Small Buffer Do Young Eun,Member,IEEE,and Xinbing Wang,Member;IEEE Abstract-We consider a TCP/AQM system with large link ca- should change its transmission rate or window size in response pacity(NC)shared by many flows.The traditional rule-of-thumb to the congestion signal(packet drop,delay,or Explicit Conges- suggests that the buffer size be chosen in proportion to the number tion Notification (ECN)marks [1])from the network. of flows (N)for full link utilization,while recent research out- comes show that O(VN)buffer sizing is sufficient for high utiliza- As the number of flows and the size of link capacity in the net- tion and O(1)buffer sizing makes the system stable at the cost of work continue to grow,the analysis and design of such a large reduced link utilization.In this paper,we consider a system where TCP/AQM system are becoming increasingly difficult and in- the Active Queue Management (AOM)is scaled as O(N)with volved.Among other issues,the question of buffer sizing has a buffer of size O(NB)(0<a<B 0.5).By capturing recently received much attention in the literature [2-8.The randomness both in packet arrivals and in packet markings,we develop a doubly-stochastic model for a TCP/AOM system with question is:given the number of TCP flows(N)and the size of many flows.We prove that,under such a scale,the system always link capacity (NC),how do we choose the buffer size B(N)? performs well in the sense that the link utilization goes to 100% Under the linear buffer sizing B(N)=O(N),1 it is well known and the loss ratio decreases to zero as the system size N increases. that a"stable"system ensures the convergence of a normalized Our results assert that the system enjoys benefit of largeness with queue-length to a nonzero value(nonzero queueing delay)and no tradeoff between full link utilization,zero packet loss,and small buffer size,at least asymptotically.This is in stark contrast to ex- thus achieves 100%link utilization [9],[3],[10],[11],while isting results showing that there always exists a tradeoff between the square-root buffer sizing (B(N)=O(VN)turns out to full link utilization and the required buffer size.Extensive ns-2 be sufficient to achieve reasonably high link utilization when simulation results under various configurations also confirm our N is large [2].More recently,it has been suggested that a very theoretical findings.Our study illustrates that blind application of small buffer of size (B(N)=O(1))would be enough and in fluid modeling may result in strange results and exemplifies the importance of choosing a right modeling approach for different fact make the system stable at the cost of reduced link utiliza- scaling regimes tion [11],[5],[6],[8].Clearly,different objectives give rise to different guidelines on buffer sizing,and there exists a tradeoff Index Terms-Router buffer sizing,small buffer,stochastic mod- eling,transmission control protocol. between full link utilization and the amount of required buffer space. On the other hand,for the design of TCP/AOM schemes as- I.INTRODUCTION sociated with the chosen buffer size,the "fluid modeling"of TCP/AQM congestion control and its stability analysis have proven extremely powerful and versatile.Still,different scaling N THE current Internet,TCP congestion control is respon- regimes for AQM schemes and buffer sizes often lead to dif- sible for carrying about 90%of the bytes of total traffic gen- ferent types of fluid models.For example,when there are N erated in the network.Such a congestion control algorithm con- flows with capacity NC and linear scaling (O(N))is employed sists of a network and a source algorithm that are tightly coupled for the buffer size and AQM (e.g.,all the buffer thresholds for with each other.The network algorithm,or the Active Queue packet marking are O(N)),it has been shown that the system Management (AQM)usually acting on a router,detects an onset dynamics can be described by the normalized version of the of congestion and governs how to generate and update con- gestion signal based on the information collected at the router, system [12],[13]via the law-of-large-numbers type of argu- ments.In this case,several stability criteria have been obtained e.g.,input traffic rate,queue size,delay,etc.,and then notify in terms of parameters of the normalized system [14],[15],[10], the sender,hoping that the sender will react appropriately to where the packet marking is based on the normalized queue- help alleviate the congestion and to attain best network perfor- mance.On the other hand,the source algorithm that operates length and the stability of the system refers to the convergence of this normalized queue-length in the steady-state (thus resulting at the edge of the network (end-user).dictates how each sender in 100%link utilization).In contrast,when the buffer size and the scaling for AQM are both chosen as O(1),it turns out that Manuscript received November 22,2005:revised August 28.2006,and April the system is better modeled by explicitly capturing the random 3,2007:approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor R. Srikant.This work was supported in part by the National Science Foundation packet arrivals within each RTT (rate-based AQMs)[16],[11], through CAREER Award CNS-0545893. [5],[17],where the packet marking is based on the normalized D.Y.Eun is with the Department of Electrical and Computer Engineering, rate into the queue and the stability of the system now refers North Carolina State University.Raleigh,NC 27695-7911 USA (e-mail: dyeun@ncsu.edu). to the convergence of this normalized rate (which is less than X.Wang is with the Department of Electrical Engineering,Shanghai Jiaotong University,Shanghai 200240,China (e-mail:xwang8@sjtu.edu.cn). IThroughout this paper,we write f(z)=O(g(z))when 0< f() Digital Object Identifier 10.1109/TNET.2007.904000 imif。e品≤i sp-x语<o. 1063-6692/$25.00©2008EEE

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. IEEE/ACM TRANSACTIONS ON NETWORKING 1 Achieving 100% Throughput in TCP/AQM Under Aggressive Packet Marking With Small Buffer Do Young Eun, Member, IEEE, and Xinbing Wang, Member, IEEE Abstract—We consider a TCP/AQM system with large link ca￾pacity ( ) shared by many flows. The traditional rule-of-thumb suggests that the buffer size be chosen in proportion to the number of flows ( ) for full link utilization, while recent research out￾comes show that ( ) buffer sizing is sufficient for high utiliza￾tion and (1) buffer sizing makes the system stable at the cost of reduced link utilization. In this paper, we consider a system where the Active Queue Management (AQM) is scaled as ( ) with a buffer of size ( ) (0 0 5). By capturing randomness both in packet arrivals and in packet markings, we develop a doubly-stochastic model for a TCP/AQM system with many flows. We prove that, under such a scale, the system always performs well in the sense that the link utilization goes to 100% and the loss ratio decreases to zero as the system size increases. Our results assert that the system enjoys benefit of largeness with no tradeoff between full link utilization, zero packet loss, and small buffer size, at least asymptotically. This is in stark contrast to ex￾isting results showing that there always exists a tradeoff between full link utilization and the required buffer size. Extensive -2 simulation results under various configurations also confirm our theoretical findings. Our study illustrates that blind application of fluid modeling may result in strange results and exemplifies the importance of choosing a right modeling approach for different scaling regimes. Index Terms—Router buffer sizing, small buffer, stochastic mod￾eling, transmission control protocol. I. INTRODUCTION I N THE current Internet, TCP congestion control is respon￾sible for carrying about 90% of the bytes of total traffic gen￾erated in the network. Such a congestion control algorithm con￾sists of a network and a source algorithm that are tightly coupled with each other. The network algorithm, or the Active Queue Management (AQM) usually acting on a router, detects an onset of congestion and governs how to generate and update con￾gestion signal based on the information collected at the router, e.g., input traffic rate, queue size, delay, etc., and then notify the sender, hoping that the sender will react appropriately to help alleviate the congestion and to attain best network perfor￾mance. On the other hand, the source algorithm that operates at the edge of the network (end-user), dictates how each sender Manuscript received November 22, 2005; revised August 28, 2006, and April 3, 2007; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor R. Srikant. This work was supported in part by the National Science Foundation through CAREER Award CNS-0545893. D. Y. Eun is with the Department of Electrical and Computer Engineering, North Carolina State University, Raleigh, NC 27695-7911 USA (e-mail: dyeun@ncsu.edu). X. Wang is with the Department of Electrical Engineering, Shanghai Jiaotong University, Shanghai 200240, China (e-mail: xwang8@sjtu.edu.cn). Digital Object Identifier 10.1109/TNET.2007.904000 should change its transmission rate or window size in response to the congestion signal (packet drop, delay, or Explicit Conges￾tion Notification (ECN) marks [1]) from the network. As the number of flows and the size of link capacity in the net￾work continue to grow, the analysis and design of such a large TCP/AQM system are becoming increasingly difficult and in￾volved. Among other issues, the question of buffer sizing has recently received much attention in the literature [2]–[8]. The question is: given the number of TCP flows and the size of link capacity , how do we choose the buffer size ? Under the linear buffer sizing ,1 it is well known that a “stable” system ensures the convergence of a normalized queue-length to a nonzero value (nonzero queueing delay) and thus achieves 100% link utilization [9], [3], [10], [11], while the square-root buffer sizing turns out to be sufficient to achieve reasonably high link utilization when is large [2]. More recently, it has been suggested that a very small buffer of size would be enough and in fact make the system stable at the cost of reduced link utiliza￾tion [11], [5], [6], [8]. Clearly, different objectives give rise to different guidelines on buffer sizing, and there exists a tradeoff between full link utilization and the amount of required buffer space. On the other hand, for the design of TCP/AQM schemes as￾sociated with the chosen buffer size, the “fluid modeling” of TCP/AQM congestion control and its stability analysis have proven extremely powerful and versatile. Still, different scaling regimes for AQM schemes and buffer sizes often lead to dif￾ferent types of fluid models. For example, when there are flows with capacity NC and linear scaling is employed for the buffer size and AQM (e.g., all the buffer thresholds for packet marking are , it has been shown that the system dynamics can be described by the normalized version of the system [12], [13] via the law-of-large-numbers type of argu￾ments. In this case, several stability criteria have been obtained in terms of parameters of the normalized system [14], [15], [10], where the packet marking is based on the normalized queue￾length and the stability of the system refers to the convergence of this normalized queue-length in the steady-state (thus resulting in 100% link utilization). In contrast, when the buffer size and the scaling for AQM are both chosen as , it turns out that the system is better modeled by explicitly capturing the random packet arrivals within each RTT (rate-based AQMs) [16], [11], [5], [17], where the packet marking is based on the normalized rate into the queue and the stability of the system now refers to the convergence of this normalized rate (which is less than 1Throughout this paper, we write f(x) = O(g(x)) when 0 < lim inf  lim sup < 1. 1063-6692/$25.00 © 2008 IEEE

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination 2 IEEE/ACM TRANSACTIONS ON NETWORKING the normalized capacity,thus leading to a reduced link utiliza-some function p,where the superscript N in the marking func- tion).An"intermediate"scaling of O(N)with 0<<1 for tion p(x)means that there are N flows with capacity NC [18]. AQMs and the buffer size was also considered in [5].However,[10].[13],[19].[15].Note that the linear scaling means that the attention was paid mainly to the stability of the system,as packets are marked based on the normalized queue-length. opposed to the performance in terms of the link utilization and Under the drop-tail AQM policy with many flows,it the queue-length distribution in the steady-state. is shown [2]that one can do much better than this tradi- In this paper,we focus on TCP/AQM systems with ECN tional rule-of-thumb for buffer sizing.Empirical observa- marking under a"sub-square-root"scaling and investigate the tion reveals that when N is large,each user's window size system performance in terms of the link utilization and the Wii=1,2,...,N)becomes independent.By appealing queue-length distribution in the steady-state.Specifically,we to the Central Limit Theorem,their sum will behave like a scale the AQM and the buffer size as O(N)with 0<a<0.5 Gaussian random variable with mean equal to the size of the (more "aggressive"than O(vN))and analyze the system "pipe"(NC X RIT)and with standard deviation O(vN). behavior as N becomes large.By explicitly taking into account Hence,by choosing the buffer size on the order of VN to the randomness both in packet arrival time and the number of absorb typical fluctuations,one can still achieve high utilization packets itself,we develop a "doubly-stochastic"Markovian and thus save huge cost for buffers implemented in high-speed model in which the aggregate arrival to the queue is modeled core routers.Further,quite recently,far smaller buffer sizing of by a conditional Poisson process-a Poisson process with B(N)=O(1)has been proposed in [5],[6],[8],all of which stochastic rate where the stochastic rate is determined by the however result in a reduced link utilization (bounded away dynamics of random packet markings in the previous RTT.We from 1). then analyze this doubly-stochastic model under the proposed This observation leads us to pose the following question: scale in the steady-state and show that,as N increases:1)the can we do better than O(vN,i.e.,can we put buffers of size link utilization converges to 100%and 2)the queue-length ON)with BE(0,0.5)instead,while maintaining full link distribution is concentrated right on "target,"leading to zero utilization and low packet loss?The only available result in the loss probability.Thus our results show that the system enjoys literature using this range of scale is in [5],where it was sug- "benefit of largeness"under O(N)scale in that there is no gested that the system under O(N)(0<<1)scale would tradeoff between 100%link utilization,zero loss probability at promote instability for very large N(thus undesirable).Still,it the queue,and smaller buffer size,at least asymptotically.This lacks any performance investigation in terms of some possible is in sharp contrast to other existing results in the literature,tradeoff between the link utilization and the queue-length which all predict some tradeoffs between the buffer size and the behavior under such a scale link utilization.We also provide extensive simulation results under various settings to confirm all our theoretical findings. B.Aggressive Packet Marking The rest of the paper is organized as follows.In Section II,we first provide background on the issue of buffer sizing at routers In this paper,we explore any possibility of using buffer sizes and propose our scales for AQM and the buffer sizing.We also of O(N3)and AQM schemes with O(Na)scaling,where 0< illustrate the difficulty of finding a"right fluid model for the <B<0.5.By this scaling of TCP/AQM,we mean that the system under the aggressive scale.In Section III,we develop a buffer size is on the order of N3 (B(N)=O(N))and,for doubly-stochastic framework to capture the randomness both in AQM schemes,there exists a function p such that p(Nox)= packet marking and time of arrivals and describe our modeling p(x)for all N and >0(see Fig.1).Note that this can details.In Section IV,we prove our main results showing that be interpreted as a more aggressive marking than the case of all the performance metrics are not impaired under the proposed a=3=1 (linear scale)since the marking probability is much scale asymptotically.In Section V,we provide extensive ns-2 higher for the same queue-length.2 We note that difference in simulations to verify our findings.In Section VI,we illustrate marking scales simply means different parameter setup at the the importance of capturing the randomness in packet arrivals routers,which can be easily configured as desired.Moreover, under the aggressive scale and discuss existing results for the the scaling of marking functions,or AQM schemes in general, proposed scale.Finally,we conclude in Section VII. is directly related to the issues of network design over a long time scale.For example,if the number of connections (or cus- IⅡL.PRELIMINARIES tomers)were to increase by ten times,then a natural question to ask is:what percentages of additional capacities or buffer sizes A.Scaling Buffers and AOMs Inside a Network are needed at routers to provide the same level of performance to each user?Under the linear scale (=B=1),we would In TCP congestion control,one of the long-held rules-of- have to increase by 10 times the buffer size as well as all the thumb in network design is that the buffer size at bottleneck links should be proportional to the bandwidth-delay product [9]. parameters associated with the AQM.If our aggressive scale is [3].In a large network setting where there are N flows with to be used,the buffer size and the AQM parameters should be increased very little (e.g.,100.3 2 and 100.21.6 when link capacity NC,this rule-of-thumb suggests O(N)for buffer a=0.2and3=0.3. sizing.Associated with this buffer sizing is the linear scaling for AQM,in which the marking function p()[0,1],or Fig.I shows some examples of marking functions with the the probability of packet marking when the queue-length is r, scale of Na.Note that all the thresholds for the marking are on is scaled linearly,i.e.,for all N and p (Nx)=p(x)for 2Our scale is even more aggressive than the case of a =0.5

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 2 IEEE/ACM TRANSACTIONS ON NETWORKING the normalized capacity, thus leading to a reduced link utiliza￾tion). An “intermediate” scaling of with for AQMs and the buffer size was also considered in [5]. However, the attention was paid mainly to the stability of the system, as opposed to the performance in terms of the link utilization and the queue-length distribution in the steady-state. In this paper, we focus on TCP/AQM systems with ECN marking under a “sub-square-root” scaling and investigate the system performance in terms of the link utilization and the queue-length distribution in the steady-state. Specifically, we scale the AQM and the buffer size as with (more “aggressive” than and analyze the system behavior as becomes large. By explicitly taking into account the randomness both in packet arrival time and the number of packets itself, we develop a “doubly-stochastic” Markovian model in which the aggregate arrival to the queue is modeled by a conditional Poisson process—a Poisson process with stochastic rate where the stochastic rate is determined by the dynamics of random packet markings in the previous RTT. We then analyze this doubly-stochastic model under the proposed scale in the steady-state and show that, as increases: 1) the link utilization converges to 100% and 2) the queue-length distribution is concentrated right on “target,” leading to zero loss probability. Thus our results show that the system enjoys “benefit of largeness” under scale in that there is no tradeoff between 100% link utilization, zero loss probability at the queue, and smaller buffer size, at least asymptotically. This is in sharp contrast to other existing results in the literature, which all predict some tradeoffs between the buffer size and the link utilization. We also provide extensive simulation results under various settings to confirm all our theoretical findings. The rest of the paper is organized as follows. In Section II, we first provide background on the issue of buffer sizing at routers and propose our scales for AQM and the buffer sizing. We also illustrate the difficulty of finding a “right” fluid model for the system under the aggressive scale. In Section III, we develop a doubly-stochastic framework to capture the randomness both in packet marking and time of arrivals and describe our modeling details. In Section IV, we prove our main results showing that all the performance metrics are not impaired under the proposed scale asymptotically. In Section V, we provide extensive -2 simulations to verify our findings. In Section VI, we illustrate the importance of capturing the randomness in packet arrivals under the aggressive scale and discuss existing results for the proposed scale. Finally, we conclude in Section VII. II. PRELIMINARIES A. Scaling Buffers and AQMs Inside a Network In TCP congestion control, one of the long-held rules-of￾thumb in network design is that the buffer size at bottleneck links should be proportional to the bandwidth-delay product [9], [3]. In a large network setting where there are flows with link capacity , this rule-of-thumb suggests for buffer sizing. Associated with this buffer sizing is the linear scaling for AQM, in which the marking function , or the probability of packet marking when the queue-length is , is scaled linearly, i.e., for all and for some function , where the superscript in the marking func￾tion means that there are flows with capacity NC [18], [10], [13], [19], [15]. Note that the linear scaling means that packets are marked based on the normalized queue-length. Under the drop-tail AQM policy with many flows, it is shown [2] that one can do much better than this tradi￾tional rule-of-thumb for buffer sizing. Empirical observa￾tion reveals that when is large, each user’s window size becomes independent. By appealing to the Central Limit Theorem, their sum will behave like a Gaussian random variable with mean equal to the size of the “pipe” and with standard deviation . Hence, by choosing the buffer size on the order of to absorb typical fluctuations, one can still achieve high utilization and thus save huge cost for buffers implemented in high-speed core routers. Further, quite recently, far smaller buffer sizing of has been proposed in [5], [6], [8], all of which however result in a reduced link utilization (bounded away from 1). This observation leads us to pose the following question: can we do better than , i.e., can we put buffers of size with instead, while maintaining full link utilization and low packet loss? The only available result in the literature using this range of scale is in [5], where it was sug￾gested that the system under scale would promote instability for very large (thus undesirable). Still, it lacks any performance investigation in terms of some possible tradeoff between the link utilization and the queue-length behavior under such a scale. B. Aggressive Packet Marking In this paper, we explore any possibility of using buffer sizes of and AQM schemes with scaling, where . By this scaling of TCP/AQM, we mean that the buffer size is on the order of and, for AQM schemes, there exists a function such that for all and (see Fig. 1). Note that this can be interpreted as a more aggressive marking than the case of (linear scale) since the marking probability is much higher for the same queue-length.2 We note that difference in marking scales simply means different parameter setup at the routers, which can be easily configured as desired. Moreover, the scaling of marking functions, or AQM schemes in general, is directly related to the issues of network design over a long time scale. For example, if the number of connections (or cus￾tomers) were to increase by ten times, then a natural question to ask is: what percentages of additional capacities or buffer sizes are needed at routers to provide the same level of performance to each user? Under the linear scale , we would have to increase by 10 times the buffer size as well as all the parameters associated with the AQM. If our aggressive scale is to be used, the buffer size and the AQM parameters should be increased very little (e.g., and when and ). Fig. 1 shows some examples of marking functions with the scale of . Note that all the thresholds for the marking are on 2Our scale is even more aggressive than the case of  = 0:5

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination EUN AND WANG:ACHIEVING 100%THROUGHPUT IN TCP/AOM UNDER AGGRESSIVE PACKET MARKING WITH SMALL BUFFER Marking probability Marking probability queue-length [10],[15].[20,[211.Similarly,in 131,19]the Steady State Region Steady State Region authors derived a limiting system dynamics by considering 1 random packet markings under O()scale (but ignoring random packet arrivals within each RTT).On the other hand, under O(1)scale with constant buffer size,the resulting fluid models are usually of rate-based types,where the marking is 9maN“BN) based on the arrival rate (e.g.,an incoming packet is marked YN“ B(N) Queue size Qucue size with probability (A/C)B where packets arrive randomly with an average rate A and buffer size B)and the stability now (a) (b) refers to the convergence of the arrival rate,from which the Fig.1.Examples of marking functions with aggressive marking scale of No. steady-state queue-length distribution can be inferred [16],[11], (a)Linear marking:RED type.(b)Exponential marking:REM type. [5.Further,in 171,[22],[23],where all the system parameters are kept constant(not dependent on N),some appropriate fluid models were obtained by sending the 'weight'of the exponen- the order of N.Suppose that the system performs as desired in tial averaging for the queue-length to zero(or making it very the steady-state,3 i.e.,the queue-length will be O(N)with high small)and by making the exponentially averaged queue-length probability.Then,we expect that the system will achieve almost almost constant (separation of time-scales). 100%utilization while packet loss probability with a buffer of In this regard,it is now clear what went wrong in the afore- size O(N)(B>a)will be very small large N.Our ns-2 sim- mentioned arguments.Specifically,the stability criterion in [10] ulation results show that this is indeed the case(see Section V is not meant to be used for systems with O(N)scale,as it for details.)Since0<<B<0.5,this implies that we can in was originally derived for a system with O(N)scale.Similarly, fact do much better than O(VN)buffer sizing [2]while main- those in [17],[16],[11]are valid only under O(1)scale (or under taining all the good performance measures(full link utilization, a rate-based marking).Certainly,blind application of the fluid negligible delay,and low loss). model could lead to very strange results. For the system with O(N)scale,however,it is still unclear C.Deriving Fluid Models Under Aggressive Scales how to derive a"right"fluid model.This scale regime was dis- cussed in [5],where the authors considered "underload"and Suppose now that one wants to apply the existing stability "overload"situations separately and claimed that the system criterion in the literature to the system under the aggressive would be stable for moderate values of N,but tends to be un- scale.For example,according to [10].[15],[18],the criterion stable when N is very large (say,5000 or more).However,this for linear stability of the system with queue-based marking(ob- seems to conflict with the observation made in [2]and also our tained from the Nyquist criterion)becomes O(N)<,theoretical and simulation results later on in this paper showing where C is a system-independent constant.On the other hand, that the system performance gets better for larger N.(See more the stability of all rate-based marking systems assuming Poisson discussion on this in Section VI-B.)As an attempt to address type of packet arrivals requires that the slope of the marking this"grey area",in this paper,we instead construct a fully sto- function at the equilibrium be bounded,which then translates chastic model by taking the packet-level dynamics into account into the condition that the buffer size be bounded,i.e.,B()< and analyze its performance in the steady-state,thus bypassing n or at least O(1)scaling should be employed for AQM [16]. the difficulty of deriving a"right"fluid model for the system [11].Note that for any a E(0,0.5)and large N,none of these under the proposed aggressive scale. criteria is satisfied,and this leads to a conclusion that the system under the aggressive scale is always unstable,albeit all the good performance measures as numerically observed.This is an em- IⅡ.SYSTEM MODEL barrassing situation since an 'unstable'system still possesses all the good performance measures.So,one may ask:"What went A.A Doubly Stochastic Approach wrong?,""What causes this self-conflicting conclusion?" In this section,we develop our doubly-stochastic approach The above illustrates that one has to be very careful in to capture the randomness both in packet arrival instants and choosing a "right"fluid model (or approximation)of the random packet markings.Consider a single link shared by N system under consideration.In general,depending on the scale persistent flows,whose window sizes evolve according to the of the system or types of limiting regimes employed,one can AIMD rule.Let T be the round-trip-time delay (RTT)for all N derive different fluid models (or approximations)that effec- flows.We define W.N()to be the window size of flow i at the tively capture the dynamics of original stochastic systems and start of kth RTT,where the superscript M means that there are then discuss their stability.For example,under the linear scale O(N)for AQM and the buffer size,one can readily obtain N flows with capacity NC.Let wmax(Wmax >CT+1)be the maximum window size for all flows,i.e.,1<WN()<Wmax fluid models for the normalized arrival rate and queue-length, for all i and N.Then,each window size WN(:)evolves as where the marking is based on the normalized queue-length and follows: the stability here refers to the convergence of the normalized 3Here,the steady-state should be interpreted in a distributional sense,not as W(k+1) (WN(k)+1)Aumax,if no marking a constant queue-length. W(k)/2V1, otherwise

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. EUN AND WANG: ACHIEVING 100% THROUGHPUT IN TCP/AQM UNDER AGGRESSIVE PACKET MARKING WITH SMALL BUFFER 3 Fig. 1. Examples of marking functions with aggressive marking scale of N . (a) Linear marking: RED type. (b) Exponential marking: REM type. the order of . Suppose that the system performs as desired in the steady-state,3 i.e., the queue-length will be with high probability. Then, we expect that the system will achieve almost 100% utilization while packet loss probability with a buffer of size will be very small large . Our -2 sim￾ulation results show that this is indeed the case (see Section V for details.) Since , this implies that we can in fact do much better than buffer sizing [2] while main￾taining all the good performance measures (full link utilization, negligible delay, and low loss). C. Deriving Fluid Models Under Aggressive Scales Suppose now that one wants to apply the existing stability criterion in the literature to the system under the aggressive scale. For example, according to [10], [15], [18], the criterion for linear stability of the system with queue-based marking (ob￾tained from the Nyquist criterion) becomes , where is a system-independent constant. On the other hand, the stability of all rate-based marking systems assuming Poisson type of packet arrivals requires that the slope of the marking function at the equilibrium be bounded, which then translates into the condition that the buffer size be bounded, i.e., or at least scaling should be employed for AQM [16], [11]. Note that for any and large , none of these criteria is satisfied, and this leads to a conclusion that the system under the aggressive scale is always unstable, albeit all the good performance measures as numerically observed. This is an em￾barrassing situation since an ‘unstable’system still possesses all the good performance measures. So, one may ask: “What went wrong?,” “What causes this self-conflicting conclusion?” The above illustrates that one has to be very careful in choosing a “right” fluid model (or approximation) of the system under consideration. In general, depending on the scale of the system or types of limiting regimes employed, one can derive different fluid models (or approximations) that effec￾tively capture the dynamics of original stochastic systems and then discuss their stability. For example, under the linear scale for AQM and the buffer size, one can readily obtain fluid models for the normalized arrival rate and queue-length, where the marking is based on the normalized queue-length and the stability here refers to the convergence of the normalized 3Here, the steady-state should be interpreted in a distributional sense, not as a constant queue-length. queue-length [10], [15], [20], [21]. Similarly, in [13], [19] the authors derived a limiting system dynamics by considering random packet markings under scale (but ignoring random packet arrivals within each RTT). On the other hand, under scale with constant buffer size, the resulting fluid models are usually of rate-based types, where the marking is based on the arrival rate (e.g., an incoming packet is marked with probability where packets arrive randomly with an average rate and buffer size B) and the stability now refers to the convergence of the arrival rate, from which the steady-state queue-length distribution can be inferred [16], [11], [5]. Further, in [17], [22], [23], where all the system parameters are kept constant (not dependent on ), some appropriate fluid models were obtained by sending the ‘weight’ of the exponen￾tial averaging for the queue-length to zero (or making it very small) and by making the exponentially averaged queue-length almost constant (separation of time-scales). In this regard, it is now clear what went wrong in the afore￾mentioned arguments. Specifically, the stability criterion in [10] is not meant to be used for systems with scale, as it was originally derived for a system with scale. Similarly, those in [17], [16], [11] are valid only under scale (or under a rate-based marking). Certainly, blind application of the fluid model could lead to very strange results. For the system with scale, however, it is still unclear how to derive a “right” fluid model. This scale regime was dis￾cussed in [5], where the authors considered “underload” and “overload” situations separately and claimed that the system would be stable for moderate values of , but tends to be un￾stable when is very large (say, 5000 or more). However, this seems to conflict with the observation made in [2] and also our theoretical and simulation results later on in this paper showing that the system performance gets better for larger . (See more discussion on this in Section VI-B.) As an attempt to address this “grey area”, in this paper, we instead construct a fully sto￾chastic model by taking the packet-level dynamics into account and analyze its performance in the steady-state, thus bypassing the difficulty of deriving a “right” fluid model for the system under the proposed aggressive scale. III. SYSTEM MODEL A. A Doubly Stochastic Approach In this section, we develop our doubly-stochastic approach to capture the randomness both in packet arrival instants and random packet markings. Consider a single link shared by persistent flows, whose window sizes evolve according to the AIMD rule. Let be the round-trip-time delay (RTT) for all flows. We define to be the window size of flow at the start of th RTT, where the superscript means that there are flows with capacity NC. Let be the maximum window size for all flows, i.e., for all and . Then, each window size evolves as follows:

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination IEEE/ACM TRANSACTIONS ON NETWORKING Random marking Dst 1 conditional Poisson process with rate (w+w.W)/T Sre Dst 2 random ILI O(N) Dst N sre2 111 I11 packet NC (k) Random Arrival with arrivals Parameter:w(k) B(N) Fig.3.Model for the arrival process to the queue within each RTT. WN(k+1) 25 小 -RED1 RED1 Fig.2.Overview on our doubly stochastic approach. 20 -4-EXP EXP -RED2 10 RED2 10 where xAy :=minfr,y}and r Vy :=maxfz,y.We 5 define a set of window sizes for all N flows by WN():= (W(),W5(),..,WR(k) 00 500 1000 1500 00 500 10001500 The number of flows,N The number of flows,N Fig.2 illustrates our doubly-stochastic approach.Sup- 0.98 0.06 pose first that,at the start of the kth RTT,all the window RED1 sizes for N flows are given.i.e.,WN()=wN()where 0.96 0.05 EXP RED2 wN():=(wi(),...,w()).(Note here that we use 0.94 0.04 capital letters for random variables and lower case letters for 0.92 0.03 ◆-ARD1 their realizations.)Then each source i simply transmits w() 0.9 0.02 RED2 number of packets over each RTT onto the network at the 0.B8 500 1000 1500 0.01 500 10001500 source side.These packets traverse a number of links(upstream The number of flows,N The number of flows,N queues)being multiplexed with other flows,and suffer different amount of delay jitters.Thus,by the time they arrive to the Fig.4.Heterogeneous RTTs:Performance metrics with increasing number of flows (N)for fixed a =0.2. queue of interest deep inside the network,their arrival times become random.In other words,given WN(k)=wN(). the arrival to the queue of interest becomes a random process 0.06 RED1,a-0.2 RED2.002 with a set of parameters as a function of wN(),making the 0.98 月ED1.=03 0.05 4HED2=03 queue-length fluctuation also random. 0.96 Now,for a given realization of the queue-length fluctuation, 0.04 0.94 we can find the distribution on whether incoming packets are 0.03 marked or not from a specific marking function p(z).Thus,by 0.92 RED1,-0.2 taking expectation over all possible queue-length realizations, 0.9 RED2, 0.02 RED1,a=0.3 we can calculate the distribution on whether there is any marked 4·RED2,c=0.3 0.88 0.01 packet for flow 2,which in turn determines the distribution of 500 1000 1500 0 50010001500 the window size for (+1)th RTT duration,i.e.,WN(+1). The number of flows,N The number of flows,N Therefore,given WN()=wN(),it is possible to find the Fig.5.Heterogeneous RTTs:Performance comparison of REDI and RED2 distribution of WN(:+1)by capturing all the dynamics men- with increasing number of flows (N)for different o(o =0.2 and 0.3). tioned above,and as a consequence,there exists a Markovian structure between WN(:)and WN(:+1). under WN()=wN(),the Poisson assumption for the aggre- B.Model Description gate arrivals to the queue within one RTT is reasonable as long as packet arrivals from each flow are jittered independently at In this section,we describe our model in detail and construct a different upstream queues,due to the fact that the superposition Markov chain for WN().As before,at the start of the kth RTT, of independent point processes under a suitable scaling con- suppose that all the window sizes are known.Then,in order to verges weakly to a Poisson process [26],[27].These Poisson capture the random nature in packet arrivals,given W()= packet arrivals over small time scale(sub-second scale or RTT- w()fori=1,2,...,N,we assume that the actual aggregate level)have also been empirically observed in [28]-[31] packet arrivals to the queue within one RTT can be modeled by Remark:Note that a conditional Poisson process is not a a Poisson process with mean rate AN()given by Poisson process since the rate over one RTT is given by the sum of the random window sizes.In other words.the rate itself is a v(): (1) random process,making the arrival process doubly-stochastic. Similar doubly-stochastic approaches for TCP/AQM systems have been used in [171,[111.[8].However,results in [17],[11] See Fig.3 for illustration.Thus,the arrival process to the are not applicable to systems under the aggressive scale,and in queue of interest is modeled by a conditional Poisson process [8],the conditional Poisson process is used only to show that the (or doubly stochastic Poisson process)[24],[25].We note that,process is dominated by a standard Poisson process with some

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. 4 IEEE/ACM TRANSACTIONS ON NETWORKING Fig. 2. Overview on our doubly stochastic approach. where and . We define a set of window sizes for all flows by . Fig. 2 illustrates our doubly-stochastic approach. Sup￾pose first that, at the start of the RTT, all the window sizes for flows are given, i.e., where . (Note here that we use capital letters for random variables and lower case letters for their realizations.) Then each source simply transmits number of packets over each RTT onto the network at the source side. These packets traverse a number of links (upstream queues) being multiplexed with other flows, and suffer different amount of delay jitters. Thus, by the time they arrive to the queue of interest deep inside the network, their arrival times become random. In other words, given , the arrival to the queue of interest becomes a random process with a set of parameters as a function of , making the queue-length fluctuation also random. Now, for a given realization of the queue-length fluctuation, we can find the distribution on whether incoming packets are marked or not from a specific marking function . Thus, by taking expectation over all possible queue-length realizations, we can calculate the distribution on whether there is any marked packet for flow , which in turn determines the distribution of the window size for th RTT duration, i.e., . Therefore, given , it is possible to find the distribution of by capturing all the dynamics men￾tioned above, and as a consequence, there exists a Markovian structure between and . B. Model Description In this section, we describe our model in detail and construct a Markov chain for . As before, at the start of the th RTT, suppose that all the window sizes are known. Then, in order to capture the random nature in packet arrivals, given for , we assume that the actual aggregate packet arrivals to the queue within one RTT can be modeled by a Poisson process with mean rate given by (1) See Fig. 3 for illustration. Thus, the arrival process to the queue of interest is modeled by a conditional Poisson process (or doubly stochastic Poisson process) [24], [25]. We note that, Fig. 3. Model for the arrival process to the queue within each RTT. Fig. 4. Heterogeneous RTTs: Performance metrics with increasing number of flows (N) for fixed  = 0:2. Fig. 5. Heterogeneous RTTs: Performance comparison of RED1 and RED2 with increasing number of flows (N) for different ( = 0:2 and 0.3). under , the Poisson assumption for the aggre￾gate arrivals to the queue within one RTT is reasonable as long as packet arrivals from each flow are jittered independently at different upstream queues, due to the fact that the superposition of independent point processes under a suitable scaling con￾verges weakly to a Poisson process [26], [27]. These Poisson packet arrivals over small time scale (sub-second scale or RTT￾level) have also been empirically observed in [28]–[31] Remark: Note that a conditional Poisson process is not a Poisson process since the rate over one RTT is given by the sum of the random window sizes. In other words, the rate itself is a random process, making the arrival process doubly-stochastic. Similar doubly-stochastic approaches for TCP/AQM systems have been used in [17], [11], [8]. However, results in [17], [11] are not applicable to systems under the aggressive scale, and in [8], the conditional Poisson process is used only to show that the process is dominated by a standard Poisson process with some

This article has been accepted for inclusion in a future issue of this journal.Content is final as presented,with the exception of pagination EUN AND WANG:ACHIEVING 100%THROUGHPUT IN TCP/AOM UNDER AGGRESSIVE PACKET MARKING WITH SMALL BUFFER 5 10 Note that this assumption is very general and the base marking function p(z)can be any non-decreasing function with p(0)=0 h(N)=N,100%Correlation and p(oo)=1.See Fig.I for examples satisfying the above 10 assumptions. Within one RTT and given WN(k)=wN(k),since we as- 10 Ref. sume that the arrival is a Poisson process with mean rate AN(), RED1 EXP we can find the distribution of the queue-length during the kth -RED2 RTT by using any standard queueing model such as M/D/1 h(N)=1,Independent or M/G/1 as long as An()<NC.Further,we assume that if AN()>NC,all the incoming packets are marked.4 Now, 10 given WN(k)=wN (k)during kth RTT.let (be the random variable denoting the queue-length fluctuation due to the random arrival instants.From our formulation above,we see 10 0 200 400 600 800 1000 that)is distributed according to the steady-state queue- length distribution of the M/D/1 or M/G/1 if An(k)<NC The number of flows,N where An()is from (1).When AN()>NC,we can con- (a) veniently set =o since p()-1 from (3)and all 0.035 the incoming packets will be marked.Also,this implies that Gaussian distribution (1491,48.52) Marginal distribution of total window size ∑W吟（阁P<NCT+Nall the time,.incell the ows 0.03 will drop their rates by half once the sum of the window sizes goes beyond NCT. 0.025 Now,given WN(k)=wN(k)and given a realization of queue-length,each packet will be marked with probability 0.02 pN).Since flow i transmits w()packets,we see 0.015 that flow i receives no mark during the kth RTT with probability 0.01 mwE=-e{-产(Qw】} (4) 0.005 where F is the expectation over all possible realizations of the queue-length under WN()=wN(). 9301350140 145015001550160016501700 Given WN(k)=wN(k),suppose first AN()<NC.Then The number of packets the queue remains stable within that RTT (i.e.,utilization<1), and each packet will be marked independently of any other.We (b) thus expect that the events of flow i receiving at least one marked Fig.6.ah(N)=Var{∑wW/∑Ni Var(WN)as a function of packet are likely to be independent for different i,which implies N for different AOM schemes under a02(b)Histogram for aggregate independence of window sizes among different flows at the next window sizes from N flows under REDI,N 200,and a =0.2.(a)h(N). RTT. (b)PDF of aggregate window sizes. In the case of An()>NC,since all the flows will back off in the next RTT.the window sizes at the next RTT will not larger constant rate(in terms of the maximum window size of be independent.However,we will show that this event becomes each flow)and all the analysis was conducted via this standard rare for large Nin the sense that∑W'(≥VCT}一 Poisson process for the system under O(1)scale with constant 0 as N increases (see Lemma 1).Hence,for any case,we can buffer size.Instead,we focus on different scalings and attempt assume the following: to solve the constructed Markov chain for the doubly-stochastic Assumption 1:Given WN(k)=wN(k),the random vari- model (random arrivals and random packet markings)in the ables WN(+1)(i=1,2,...,N)are independent. steady-state with stationary distribution and derive the asymp- Indeed,our simulation results in Section V.C will also show totic performance results. that the window sizes for different flows are mostly independent As before,pN()here is the probability that a packet is even under our aggressive marking scale(see Fig.6).Further, marked when the queue-length is t.In particular,our marking Assumption 1 will be used only to construct a Markov chain for function p(z)of scale a E(0,1/2)will satisfy the following: the system and will never be used again once the system enters there exists a non-decreasing function p :R[0,1]such a steady-state. that,for all N and x Now,for any given N.[WN()>o forms an N-dimen- sional homogeneous Markov chain with its state space given by p(NOr)=p(x) (2) E:={1,2....,wmaxNns(N) (5) where This corresponds to an unstable queue with utilizationp>1.Thus,for large ()=0 and lim p()=1. (3) N,the queue-length will explode for any marking scale No (0<a<1/2) within that RTT and almost all packets will be marked

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination. EUN AND WANG: ACHIEVING 100% THROUGHPUT IN TCP/AQM UNDER AGGRESSIVE PACKET MARKING WITH SMALL BUFFER 5 Fig. 6. (a) h(N) = Varf W g= VarfW g as a function of N for different AQM schemes under  = 0:2; (b) Histogram for aggregate window sizes from N flows under RED1, N = 200, and  = 0:2. (a) h(N). (b) PDF of aggregate window sizes. larger constant rate (in terms of the maximum window size of each flow) and all the analysis was conducted via this standard Poisson process for the system under scale with constant buffer size. Instead, we focus on different scalings and attempt to solve the constructed Markov chain for the doubly-stochastic model (random arrivals and random packet markings) in the steady-state with stationary distribution and derive the asymp￾totic performance results. As before, here is the probability that a packet is marked when the queue-length is . In particular, our marking function of scale will satisfy the following: there exists a non-decreasing function such that, for all and (2) where (3) Note that this assumption is very general and the base marking function can be any non-decreasing function with and . See Fig. 1 for examples satisfying the above assumptions. Within one RTT and given , since we as￾sume that the arrival is a Poisson process with mean rate , we can find the distribution of the queue-length during the th RTT by using any standard queueing model such as or as long as . Further, we assume that if , all the incoming packets are marked.4 Now, given during th RTT, let be the random variable denoting the queue-length fluctuation due to the random arrival instants. From our formulation above, we see that is distributed according to the steady-state queue￾length distribution of the or if where is from (1). When , we can con￾veniently set since from (3) and all the incoming packets will be marked. Also, this implies that all the time, since all the flows will drop their rates by half once the sum of the window sizes goes beyond . Now, given and given a realization of queue-length, each packet will be marked with probability . Since flow transmits packets, we see that flow receives no mark during the th RTT with probability (4) where is the expectation over all possible realizations of the queue-length under . Given , suppose first . Then the queue remains stable within that RTT (i.e., utilization ), and each packet will be marked independently of any other. We thus expect that the events of flow receiving at least one marked packet are likely to be independent for different , which implies independence of window sizes among different flows at the next RTT. In the case of , since all the flows will back off in the next RTT, the window sizes at the next RTT will not be independent. However, we will show that this event becomes rare for large in the sense that as increases (see Lemma 1). Hence, for any case, we can assume the following: Assumption 1: Given , the random vari￾ables are independent. Indeed, our simulation results in Section V.C will also show that the window sizes for different flows are mostly independent even under our aggressive marking scale (see Fig. 6). Further, Assumption 1 will be used only to construct a Markov chain for the system and will never be used again once the system enters a steady-state. Now, for any given , forms an N-dimen￾sional homogeneous Markov chain with its state space given by (5) 4This corresponds to an unstable queue with utilization   1. Thus, for large N, the queue-length will explode for any marking scale N (0 << 1=2) within that RTT and almost all packets will be marked