Convergence,stability and robustness analysis of the OFEX controller for high-speed networks

Jungang LIU,O liver W.W.YANG

School of Electrical Engineering and Computer Science,University of Ottawa,Ottawa K1N 6N5,Canada

1 Introduction

Internet traffic control has been an important subject since the early stage of the Internet such as TCP[1,2]that can throttle the source sending rate and effectively relieve the network congestion.Based on the NUM(network utilization maximization)theory[3],the existing congestion control mechanism s were categorized into the primal algorithm s and the dual algorithm s[4].

In view of the types of the feedback signals,w e can classify the dual algorithm s further into the relatively explicit algorithm s and the fully exp licit algorithms,and their definitions have been provided in[5].The existing NUM-based traffic controllers(e.g.,[6–8])fall under the category of the relatively explicit control algorithm s,in which sources ad just the sending rate according to cumulative link prices,i.e.,a congestion signal that is a summation of the congestion signals over all links along a flow path.Therefore,for the same source payment,the multi-bottlenecked users in the relatively exp licit controllers obtain a smaller share of the network bandwidth and encounter a longer convergence time.Besides,the existing relatively explicit algorithm s have performance problems in the presence of dynamic bandwidth because they have assumed fixed link bandwidth in their controller designs.As such,these algorithm s cannot adapt them selves to the varied network conditions and thus resulting in poor performances.In addition,these algorithm s quite often incur large queue sizes upon congestion because they just do the match between the incoming data rate and link bandwidth without any consideration of the queue size.

To remedy the above issues,an OFEX(Optimal and Fully EXplicit)rate controller has been proposed[5].The OFEX controller uses the allowed sending rate of the links as the congestion signal,and thus it is a fully exp licit rate controller.Furthermore,it feeds back the congestion signal from the most congested link along a data path and can therefore overcome the drawback of the relatively explicit rate controllers that penalize the multi-bottlenecked users in term s of throughput and convergence performance.

The reason that the OFEX controller outperform s the relatively explicit controllers in multi-bottlenecked networks can be simply illustrated with Fig.1,where we assume a 3-bottleneck network(i.e.,Routers 1–3).Each source(si,i=1,2,...)obtains a portion of bandwidth to transmit data by paying a price to the routers en route.We assume sourcess1,s2ands3send their data to their respective destination nodesr1,r2andr3,which are the nodes attached to the right side of Router 3.In this network,Router 2 is supposed to be the most congested node in the network,i.e.,it has the most expensive link pricep2per unit bandwidth,while Router 1 and Router 3 are less congested with link pricesp1andp3,respectively.Takings1as an example,we assume it would like to pay a price ofw1.For the relatively explicit controllers,the throughput thats1can obtain from the network isw1/(p1+p2+p3),where the denominator is the cumulative congestion signal.However,for the OFEX controller,the throughput ofs1isw1/p2because it only cares about the most congested router along its data path.Obviously,s1can obtain more bandwidth from the network with the OFEX controller than with the relatively explicit controllers.As a matter of fact,such a multi-bottleneck issue demonstrated above has already been considered in implicit congestion control protocols such as TCP with correcting measures[9].Our study in this paper for fully explicit congestion control algorithm s nowadays(as candidates of next generation high-speed networks)is based on the same consideration because there is no inherent reason that the long flows passing through multiple bottlenecks should suffer from low throughput[9].

Fig.1 A 3-bottleneck network.

Apart from addressing the above multiple bottleneck issue,the OFEX controller is also designed to handle the problem s arising from link bandwidth dynamics[10–12].Hence,the new scheme is m ore practical when it comes to the real-world dynamic networks.To do so,the OFEX controller has introduced the instantaneous queue sizeq(t)into its model as a remedial measure.The rational is that when the link bandwidthclsuddenly shrinks,q(t)has to build up due to the decreased link output capability.Therefore,the queue dynamics can provide immediate information to sources which are accordingly supposed to decrease their sending rate as a result of the shrunk bandwidth.In addition,the introduction ofq(t)in the OFEX controller also significantly reduces queue size when incoming data rate to a link matches its bandwidth,which significantly alleviates excessive queue length(which may result in delay and packet loss)and avoids queue length fluctuations(which causes inefficiency in bandwidth utilization).Although the traditional controllers(such as XCP and RCP)have alleviated such an issue by considering persistent or instantaneous queue size in their models,our controller has better stability performance in the presence of heavy traffic or bandwidth variations because it does not have to rely on a fixed link capacity design and is not restricted by design parameters(such as α and β in XCP and RCP).This will be discussed further after com paring with the XCP in the performance evaluation section later on.

In this paper,we would present more merits of the OFEX controller by investigating the following three aspects:the convergence property,the stability in the presence of time delay,and the robustness property.For the convergence analysis,we are performing link-wise optimization as opposed to network-wise optimization.First,we will take a reasonable assumption on the bandwidth price that will allow us to prove with a lemma that the objective function of the dual problem of the OFEX controller is strongly convex.Then we will propose the other lemma based on a Lipschitz continuity condition for a preparative purpose.Finally,we will prove that the OFEX controller algorithm is able to converge to its equilibrium point under certain conditions on step size.

We would also show the stability of our rate-based algorithm formulated under NUM.This would address some instability problem s not captured in the existing NUM-based window-based algorithm s(e.g.,[8])especially in the presence of time-delay.To prove system stability of the controller with time delay,we will resort to the linearization technique and employ the Nyquist criterion to obtain the sufficient and necessary conditions for the system to be locally stable.Robustness is demonstrated via an analysis of how the optimal revenue of a link reacts to the dynamics of link bandwidth.Finally,the performance of the OFEX controller for the above three properties will be demonstrated via OPNET simulation.

The rest of the paper is organized as follow s.After we make a concise summary of the operation and modeling of the OFEX controller and provide the optimization algorithm in Section 2,the convergence analysis is conducted in Section3.Section4 proves the stability of the OFEX control system with time delay.Section 5 show s the robustness analysis with respect to link bandwidth dynamics.The performance evaluation is done in Section6.We conclude this paper with Section 7.

2 OFEX controller modelling and algorithm s

We summarize below the formulation and the algorithm of the OFEX controller while introducing the notations and symbols to be used later on.Interested readers can find the design details in[5].

We represent a network by a graphG=(S,L)withS=s1,s2,...,si,...representing a set of sources andL=l1,l2,...,li,...representing a set of links in all routers of a network.For simplicity,we om it the subscript of an element inSorLin order to use it to denote any element in the set.For example,we may uselto represent any link in setL.A linkl,l∈L,at a router has a bandwidth capacityclto accommodate a set of passing flows originated from a set of sources.

Each sources∈Sl(t)deposits a flow weight Ψs(i.e.,a payment)in the Flow_weight field of the packet header.To support our new flow scheme,we use another field called the Req_rate to record the allow ed sending rate of the core or edge routers.Each flowscan obtain a proportional bandwidth to transmit data with a rate ofThis bandwidth is obtained via the following link-wise optimization problem(PP)the OFEX controller is based on.

PP:

Equation(1)is the objective function representing the maxim um benefit that linklm ay obtain from all passing flows.As such,the functionis a social welfare function that linklwould like to use.We selectas the social welfare function not only because of its mathematical property(i.e.,increasing,strictly concave and twice continuously differentiable overthat would allow us to guarantee the convergence and link-wise proportional fairness of the optimization problem,but also because it allows the incorporation of a“price”(designated by the parameter Ψs)that sourcesis willing to“pay”for linkl.The parameterclis the nominal bandwidth.The variableq(t)is the instantaneous queue size which can be accurately measured and monitored.The constant γ is a threshold parameter forq(t).As seen from(2),for a given bandwidthcl,the choice of γ will reciprocally affect the feasible value ofq(t)which in turn may affect other performances such as system response.In addition,we require γ＞0 to reflect the bandwidth shrinkage from the nominal valueclwhen interferences occur.Equation(2)is a constraint stipulating that the total incoming data rateto linkl,l∈L,cannot exceed the expected link bandwidthclwhenq(t)is emptied.The equation also ensures the convexity of the PP because it is still an affine function(having a formx1(t)+x2(t)+...+xn(t)≤c)[13]after movingq(t)to the left hand side.Finally,the constraint(3)requires the source data rate to be positive,which means a flow is always allotted a portion of the bandwidth once admitted to linkl.We define the weight vector asas the data rate vector of all flow s in linkl,l∈L.Please note that the model in equation(1)to(3)has omitted the time delay,which will be included in the analysis in Section 4 for the controller stability.In fact,our simulation in Section6 will further verify the controller performance with varying time delay(where varying queueing delay is one component due to the dynamics of the instantaneous queue size),and demonstrate that our controller is stable.

Based on the primal problem modeled in(1)–(3),the Lagrange dual problem(DP)of the PP is[5]:

DP:

where λlis the Lagrange multiplier,and interpreted as“the unit bandwidth price”in our scheme.Here,Ω(λl)is the dual function given by

Due to the strong duality between the primal problem PP and the Lagrange dual problem DP,solving PP can be done by solving DP using a gradient descent method[5].This is an iterative method with

where[a]+=m ax(0,a),and δ is a constant step size with δ＞0.The optimal data rate that each passing flow can obtain from linkl,l∈L,is

Based on the above solution,in each link the OFEX controller allocates the bandwidth proportionally fair.When it com es to multiple bottlenecks,“The OFEX algorithm”below illustrates how the OFEX exercises the max-m in fairness by responding the most congested link only.If the data paths are congested the same degree,it means that every path has the same data rate,which is still optimal according to our model.

Algorithm 1(The OFEX algorithm)

Each router uses the above algorithm to compute a new allowed sending rate.Then the new sending rate is compared with the rate already existed in the Req_rate field of a passing packet.If the passing packet has a higher value,the Req_rate field in the packet header will be replaced by the new sending rate.Otherwise,it remains unchanged.Thus the value of the Req_rate field in a packet after arriving at the receiver reflects the allowed sending rate of the most congested router along the data path.The receiver then sends this value(exp licit congestion signal)back to the source via an ACK(AC-Knowledgment)packet,and the source uses it to update its current sending rate.

3 Convergence analysis

Before we prove our control algorithm can converge to equilibrium at a geometric rate,we shall first state an assumption and two lemmas to facilitate our arguments and proof later on.

Assumption 1The unit bandwidth price λlsatisfies 0＜ Λlm≤ λl≤ ΛlM＜ ∞where Λlmand ΛlMare the minimum and maximum bandwidth price of linkl.

Rem ark 1The purpose of this assumption is to facilitate the proof of our theorem later which requires λlto be not less than zero nor to be infinite.It can be any large number so long as it is finite.This assumption is reasonable when it comes to the real-world bandwidth price.Note the lower bound Λlmmakes λlstays as a non-zero parameter in the denominator of(8).

Lemma1The objective function Ω(λl)in(4)is strongly convex.

ProofΩ(λl)is strongly convex if only if there existsm＞0 such that the second derivative Ω′′(λl)≥m[14,Page 677].To show this,we obtain the first derivative of Ω(λl)as

To derive Ω′′(λl),we p lug(8)into(9)to obtain

Differentiate(10),we obtain

Fig.2 The second derivative Ω′′(λl).

Lemma 2The first derivative Ω′(λl)of the objective function is Lipschitz continuous with the Lipschitz constantLc=Ω′′(Λlm).

ProofIf there exists someLc＞0 such that the curvature of Ω(λl)is no m ore thanLc,the proof is completed[14,Page 48].Next we shall check the existence ofLc＞0.

Because Λ(λl)is twice differentiable,the Lagrange Mean Value Theorem[14,Page 667]allows us to w rite,for any givenj,k＞0,

Thus,

Since|Ω′′(ξ)|is upper bounded by Ω′′(Λlm),

According to the Lipschitz Continuity condition[14,Page 47],(14)show s the curvature of Ω(λl)is no more than Ω′′(Λlm),i.e.,there exists a Lipschitz constantLc=Ω′′(Λlm)＞0,which yields the desired result.□

or

ProofUsing the descent lemma[14,Page 667],we can obtain

Since(15)can be written asCombining the last two term s of the right hand side,we obtain

Subtracting a constant,say Ω＊,from both sides of(16),

Using the strong convexity of from Lemma1,we would have

wheremis the parameter discussed in Lemma1.If we assumeLcδ ＜2,we can rewrite(17)as

After rearrangement,w e have

This inequality can be applied recursively on itself to generate

By assuming 0＜α＜1 and using the condition of

converges to Ω＊in(21),ask→ ∞,i.e.,the objective function Ω(λl)reaches its optimal value Ω＊,and the unit bandwidth price reaches an optimumAccordingly,the optimal data ratefollow s with(8).Hence,the system reaches the equilibriumSolving(22),for convergence the step size should satisfyorThe proof is completed.□

Rem ark 2From(21),we have the following observations:

3)If the initial value ofis chosen such thatis closer to Ω＊,the convergence time is going to be short.The only difficulty in a practical implementation is that one usually does not know w hat Ω＊is in advance.Fortunately,routers usually run forever once started,and do not need frequent re-starting and initialization.Therefore,the convergence time due to the choice ofat the starting stage should not be a concern.

4 Stability with time delay

In the previous section,a discrete-time version of the OFEX algorithm was proved to be able to converge to its optimal equilibrium under certain conditions in a link.In this section,we shall consider the system stability in an end-to-end single-bottleneck network with time delay.As known,when there is a time delay(i.e.,with RTT(round trip time))in network congestion control algorithm s,general global stability is hard to obtain[16].In this section,the local stability of the OFEX algorithm around the equilibrium in the presence of the time delay will be analyzed.

To do so,we shall first define differential equations for the OFEX algorithm,and then linearize them around the local equilibrium point.Finally,we will transform them to the frequency domain and em ploy the Nyquist stability criterion to derive sufficient and necessary conditions for the system to be locally stable.

From(7),the unit link price λlcan be defined and used to update itself according to the following differential equation:

which reflects the change of the unit link price without time delay.with the consideration of a time delay τ,(23)becomes

This is because the exp licit data rateonly takes effect after one RTT of τ seconds.To see this,we first observe that the variableis the allowed sending rate(i.e.,Req_rate)calculated by linkland recorded in the header of a packet on its way to the destination.When the packet arrives at its destination,is piggybacked in an ACK packet to the source.The source then extractsand uses it to update the data sending rate accordingly.When the data with the new sending rate reaches linkl,it has been exactly one RTT τ since the neww as issued.The link price λlis then updated according to the new incoming rate from sources.Note that w e cannot guarantee every path to have the same upper limit of time delay because the RTT can be affected due to distance,queueing delay and processing delay of a path.Since the allow ed source sending ratehas to be matched to the price the sourcespays(i.e.,Ψs),the update ofby linklcan be defined with the follow ing differential equation:

The second termon the right-hand side of(25)is the product of the data rate(in bps)authorized to sourcesand the unit bandwidth price of linkl(e.g.,in dollars/bps),and represents the total amount that the link needs to collect.The update ofin(25)eventually matchesto the payment Ψs.

We introduceandwhereandare the local equilibrium points ofandq(t)respectively.Among them,the time delay withBy puttingandin(24),we have Δ˙λl(t)=and after rearrangement,w e have

Similarly,to linearize(25),w e havewhich can be rewritten asAt equilibrium,equals Ψs,and these two term s cancel out.Also,the termcan be dropped when bothand Δλl(t)are small.Thus,w e have

Based on(27),the follow ing equation represents the aggregate differential equations of the allowed sending rate of all the sources using link l.

and

Fig.3 show s the OFEX closed-loop control system with time delay based on(29)and(30).The open-loop transfer function is

Fig.3 The OFEX closed-loop control system.

Note that the other input γδq(t)is set to zero in order to find the transfer functionG(s)between the output Δyl(t)and the input[17].Letandthen

To apply the Nyquist criterion,we substituteswith jw,

RewritingG(jw)in its Cartesian form of Re+j Im,

Note we have omitted another solutionw=0 because of the non-zero requirement of denominator in(35).Substituting(36)into the real part of(35),and let the real part be greater than−1 to have the crossover point on the right of(−1,0)to ensure stability,w e have

After rearranging(37),and factoring on both sides,we obtain

To establish(38),we have

The second inequality in(39)is always satisfied because RTT(i.e.,τ)is always greater than zero in this physical world,while the first inequality of(39)is true if

which is the sufficient condition for the OFEX control system with time delay to be locally stable.

Next,let us show by contradiction that the condition(40)is also a necessary condition that the system is stable.That is,w e assume that(40)is not the necessary condition required for as table system,which means that another stability condition can exist when the crossover point is on the left of the(−1,0)in a stable system.Recall that in order to meet the Nyquist stability criteria[17],the open-loop transfer function(33)must have the number of polesNon the left-half-p lane(with real parts less than 0)equal to the number of counter-clockwise encirclement of(−1,0)by the Nyquist plot.If they are not equal,the contradiction assumption fails and our proof is complete.

Before checking on this,we rewrite(33)as follow s:

Since the time delay τ is always positive in practice,the transfer function does not have any poles with negative real part.Therefore,the system is impossible to be stable when it has crossover point on the left of(−1,0).In summary of the contradictions discussed above,if the system is stable,the condition(40)must be satisfied.Therefore,(40)is also the necessary condition.

Fig.4 and Fig.5 separately show a Nyquist plot and Bode diagram of the OFEX control system withK1=30,K2=1000 and the time delay τ=0.3 s.The phase m argin is about 135°,and the system is stable.

Fig.4 The Nyquist plot.

Fig.5 The Bode diagram.

5 Robustness

A robust control system in general should maintain certain desired performance features despite the presence of significant system uncertainty such as parameter changes or disturbances[17].O f the different mathematical definitions,we adopt the notion based on the convex optimization theory[13],and define robustness to be the sensitivity of the OFEX controller to obtain maxim um revenue in the presence of disturbances in link bandwidth.After defining the parameters in the disturbed system in Section 5.1,we shall show that the optimal value of the OFEX controller is upper-bounded in the presence of the disturbances in bandwidthclin Section 5.2,and then analyze the local sensitivity in Section5.3.In particular,since the strong duality holds between the primal problem PP and the Lagrangian dual problem DP,our sensitivity analysis shows how the optimal link price λ＊is related to the disturbances oncl.

5.1 The perturbed system m odel

Our perturbed network model arises from the original problem PP in Section 2 w here all flow s are contending in a router for a finite bandwidthclthat can fluctuate as in shared Ethernet or IEEE 802.11.Our starting point is equation(2)where we replace−γq(t)byw(t).The variablew(t)is non-positive(i.e.,w(t)≤0 asq(t)cannot be negative.This fact will be adhered to throughout this paper.Consequently,our disturbed network model becomes

RPP(Revised primal problem):

We represent the optimal revenue of the disturbed system with Π＊(w),and see how Π＊(w)would vary with respect to the disturbancesw(t).Accordingly,Π＊(0)is the optimal revenue that a link can obtain when the system has no disturbance(i.e.,w(t)=0).

5.2 Upper bound and sensitivity

The following proposition will allow us to obtain an upper bound of the optimal revenue Π＊(w)of the OFEX controller uponcldisturbances.

Theorem 2Suppose λ＊is the optimal unit link price of the unperturbed system(i.e.,w henw(t)=0),the following inequality holds for any bandwidth decrease oncl:

ProofIt is obvious thatby the strong duality of the PP and DP[13].We also haveby the definition of the dual function.Therefore,

Rearranging(46),we have

We can now make the following immediate robustness interpretations.From inequality(44)with the aid of Fig.6,where the affine functionis a straight line tangential to Π＊(w)atw(t)=0 in order to represent the upper bound.

1)If the optimal link price λ＊is large and the bandwidth is decreasing(i.e.,w(t)＜0),the optimal revenue Π＊(w)that a link can collect would decrease drastically.As seen from Fig.6,the concavity of the function whenw(t)＜0implies a steeper slope than the slope(price)λ＊of the affine function.

2)Similarly,if the optimal link price λ＊is small,the optimal revenue Π＊(w)that the link can collect would decrease a little bit.

3)Sincew(t)is non-positive in the OFEX controller,we are not going to interpret the casew(t)＞0 in detail.In such case,briefly,independent of the optimal link price λ＊(large or small),the optimal revenue Π＊(w)that the link can collect may not increase too much.This is because for an inequality as(44),any increase of the right-hand side does not guarantee an increase on the left-hand side.Note that Π＊(w)=Π＊(0)+λ＊w(t)is the special case w hen the revenue does not change.

Fig.6 Interpretation of inequality(44).

5.3 Local robustness analysis

If we assume that Π＊(w)is differentiable atw=0,then Fig.6 depicts that the optimal dual variable λ＊,i.e.,the optimal unit link price,is related to the gradient of.Sim p ly put,

Therefore,the optimal link price is exactly the local sensitivity measured by the change of the optimal link revenue with respect to the bandwidth variations aroundw(t)=0.Equation(48)also gives us the following quantitative interpretations about the variations of Π＊(w)aroundw(t)=0.These interpretations can also be seen from Fig.6,where λ＊is the slope of Π＊(w)nearw(t)=0.

1)If the link variationw(t)is small and negative,there will be a decrease in Π＊(0)of about−λ＊w(t).

2)If both the link variationw(t)and λ＊are very sm all,they can be ignored and the optimal revenue is Π＊(0).

3)If the link price λ＊is large,any variation ofw(t)may have a big impact on the maximum revenue of Π＊(0).That is,the link may lose a lot of revenue even if the bandwidth decreases a bit.

4)Sincew(t)is non-positive in the OFEX controller,we are not going to interpret the case thatw(t)is small and positive.

5.4 Discussion

Since the OFEX controller is formulated to maximize the link revenue so that each passing flow can obtain a portion of bandwidth,the effect of the link bandwidth variations is a concern to the incentives with which a link would like to relay data for sources.Using the convex theoretic,we have discussed how the link optimal revenue may be affected as bandwidth varies with respect to the link price λ＊.In particular,when λ＊is big,the band width shrinkage may lead to a big loss in the link optimal revenue.Equation(41)implies that the passing flow s have decreased their sending rateas a response to the bandwidth reduction so that the maximum value(i.e.,the optimal revenue Π＊(w)ofdecreases accordingly.This is the desired robustness performance that the OFEX controller is designed for.

6 Performance evaluation

The performance and capability of our OFEX controller are evaluated through a series of experiments.Section6.1 describes a single-bottleneck network to be simulated in this paper.Please note that the evaluation of the OFEX controller in multi-bottlenecked networks have been done in[5]to demonstrate the desired performance,and therefore omitted here.Section 6.2 show s the convergence of our controller which optimally allocates the link bandwidth to the passing flows in proportionally fair.Section 6.3 show s the robustness of the OFEX controller under bandwidth variations.Finally,in Section6.4 the superiority of the OFEX controller on stability is presented in a comparison with other controllers.

6.1 Sim u lated network

6.1.1 Network topology

The single network topology in Fig.7 is used to investigate the controller behavior in the m ost congested router.We choose Router 1 as the only bottleneck in the network,whereas Router 2 is configured to have sufficiently high service rate to process the arrived traffic so that congestion will never happen there.Such a topology/configuration has already been the subject of m any analyses,e.g.,[18–20].

For the end users,there areM=N=11 source-destination subnet/group pairs which form the source-destination data flow s in the network,and they run var-ious Internet applications such as the long-lived FTP,short-lived HTTP,or the unresponsive UDP(User datagram protocol)-like flows(also called uncontrolled FTP[19]).At any one particular instance,some sources are active sending traffic to their corresponding destinations.Since the link bandwidth we want to simulate have a magnitude of Giga bits per second,we use 20 flows in each subnet to generate enough traffic to produce congestion.

The flow configuration is summarized in Table1 along with the RTPD(round trip propagation delay)of each flow.There are five FTP subnets and five HTTP subnets.There is also one UDP flow that will require some dedicated but constant bandwidth when running.The RTPD includes the forward path propagation delay and the feedback propagation delay,but does not include the queueing delay,which is determined by the instantaneous queue size in the experiments.As seen,the RTPD takes on different values for the flow s in the different groups.The destinations produce reverse traffic by piggybacking the ACK information to the sources.

Table 1 Sources characteristics.

The buffer capacityBin Router1 is set roughly equal to the BDP(bandwidth-delay product).Therefore,Bmay be different in different experiments below due to various bandwidth settings.The buffer size of Router 2 is made big enough so as never to drop packets.All the FTP packets have the same size of 1024 bytes[19]while the HTTP packet size is uniformly distributed in[800,1300]byte[21].

In order to show the robustness of our controller,our experiments would mainly focus on the testing of the 100 long-lived FTP sources,unless otherwise stated.The 100 sporadic short-lived HTTP flows just act as the disturbance to the FTP traffic and their transfer size follow s the real web traffic scenario by using a Pareto distribution[22]to generate the HTTP transfer size with an average 30 packets[20].The arrivals of HTTP flows follow a think time[22]which is uniformly distributed in[0.1,30]s.One of the HTTP session examples is show n in Fig.8.The uncontrolled FTP flow keeps its window size at 100 packets and operates at an almost constant rate as shown in Figs.9 and 10.

Fig.8 HTTP sessions example.

Fig.9 Uncontrolled FTP:window size.

Fig.10 Uncontrolled FTP:throughput.

The system stability can be verified for the OFEX rate control system in the sense that whether equation(40)is satisfied.Section 6.2 will show a stability verification example for the OFEX control system.

6.1.2 Other settings and performance measures

All experiments were conducted using OPNET Modeler 11.5[23]on an Intel Core TM 2 Quad platform with 2.40GHz processor.Simulated time is set according to the specific experiment scenario,and the simulation time depends on bottleneck bandwidth and the simulated time.A typical simulation run can usually take a few hours.For example,in order to observe the router and source performance before and after band width changes in Section 6.3,we used a simulated time of 120 s as com pared to the 60 s used in optimal rate allocation experiment in Section6.2,and the simulation takes about 6 hours.

The controller is evaluated by the following performance measures.

1)Instantaneous source throughput is defined to be the average number of bits successfully sent out by a source averaged over per second.A bit is considered successfully sent if it is part of a packet that is successfully sent out[23].Later we will use throughput and sending rate interchangeably for sources.

2)Instantaneous queue size is the length of the bottleneck buffer queue(measured in packets)seen by a packet departure[24].

3)Utilization is a percentage which is the ratio between the current actual throughput in the bottleneck and the maximum service rate of the bottleneck.

Since the behavior and performance of the sources within each FTP subnet/group are quite similar,we shall show the results of one source from each group in the following experiments for brevity reason.Also,since the HTTP and UDP traffics(as shown in Figs.8 and 9)are negligible com pared with the big shares of the FTP flows in a link,their effect on the overall performance has been observed to be minimal and therefore the discussion on their performance will be omitted in general.

6.2 Convergence with optimal rate allocation

In this section,we show the convergence performance how the OFEX controller allocates the link capacity to each passing flow in proportionally fair manner.The experiment is conducted under a bottleneck bandwidth of 5G bps with a buffer sizeB=120000 packets.We set the payment for flow s in FTP groups 1 to 5 to be 36621.1,14648.4,24414.1,19531.24 and 9765.6,respectively.In addition,w e setγ=1 and δ=0.01 as illustrated in“The OFEX algorithm”.Note that the selection of the parametersγ and δ is based on our numerous experiments and performance trade off.Due to space limit,these experiments are not presented.

Fig.11 shows the allowed source sending rate allocated by the link to the passing flow s.As shown,all flows transmit their data with a constant data rate after they reach the steady state.For example,the flows in FTP group 1(as represented by flow 5)spend about 3.4s on the transient stage and then stabilize their throughput at 88.34M bps.Similar observations can also be made to the sources in other FTP groups.Specifically,the allowed sending rates of the flows from FTP groups 2 to 5 at steady state are 35.26M bps,59.51M bps,47.22M bps and 23.70M bps,respectively.It is also interesting to see that their throughputs are proportional to their payments.For example,the flow s in group 1 has made the biggest payment(i.e.,36621.1),and obtained the biggest share of the bandwidth(i.e.,88.34M bps).Likewise,the flow s in group 5(as represented by flow 85)pay the least,and obtain the least.

Fig.11 Optimal rate allocation.

To show the link bandwidth of 5Gbps is actually allocated among the flow s proportionally fair and thus optimal,we carry out some simple calculations as follows.First we add all the payments of the flows up(in FTP group 1–5),which is 2.1＊106(obtained from(36621.1+14648.4+24414.1+19531.24+9765.6)＊20).The portion of bandwidth a flow obtains is the ratio of its payment to the total price of 2.1＊106 in the link multiplied by the link bandwidth 5Gbps.Thus,5Gbps×(36621.1/2.1＊106)=87.21Mbps is the allowed sending rate for a flow in group 1.Similarly one can obtain the theoretical sending rates of the flow s in groups 2–5 to be 34.88Mbps,58.14Mbps,46.51Mbps and 23.25Mbps,respectively.As seen,they closely match the experimentally obtained data rates of the last para-graph.Therefore,the algorithm illustrated in“The OFEX algorithm”realizes the optimal rate allocation mechanism(i.e.,proportional fairness)as originally designed for our controller.

Fig.12 show s the link utilization reaches 100%(i.e.,the link bandwidth of 5Gbps has been fully utilized)after it converges to the steady state.Note that the first 4 seconds in Fig.12 is the initial startup stage of our simulation for the flows to increase their sending rate gradually to use up the link capacity.

Fig.12 Link utilization.

Fig.13 depicts the instantaneous queue size.It shows a gradual increase at the beginning followed by an overshoot but eventually it settles at the near-zero buffer level(i.e.,¯q≈0).This means the OFEX controller tries to vacate the queue and thus making the queueing delay as small as possible.This advantage is the result of including the instantaneous queue sizeq(t)in our model discussed in Section2.Later on,when we make the comparison with the relatively explicit controller,one may notice that the relatively explicit controller tends to maintain a big queue size due to the lack of consideration on queue occupancy in their model.

Fig.13 Instantaneous queue size.

Fig.14 show s the aggregate in coming traffic to the link operates around 5Gbps with some oscillations at the beginning after the router starts.By com paring Fig.12 with Fig.14,one can verify that the incoming traffic and the outgoing link capacity strike equal at the steady state in that they are both operating at 5Gbps w hen the system settles.Fig.15 show s the link price decreases from the initial(i.e.,10)to the equilibrium point(i.e.,λ¯l=3.83)when the system reaches the steady state.

We can also use this experiment to verify the theoretical analysis of the system stability with time delay conducted in Section 4.As defined in Section 4,K1=¯λlandK2=δ(cl−γ¯q).Therefore,when the system is stable in this experiment,we haveK1=¯λl=3.83,andK2=δ(cl−γ¯q)=0.01＊(5＊109−1＊0)=5＊107.Also,as defined in Table 1,the average RTPD is 160m s(i.e.,0.16 s),which is obtained by dividing the sum of all the RTPDs by the total number of flow s.Note that RTT τ＞0.16s if queueing delay is included.For convenience,we use the average RTPD to approximate τ because the queue size as show n Fig.12 is very close to zero.In order to verify the stability condition imposed by(40),one can putK1,K2and τ into(40)now.It is not hard to findK1/K2=7.66＊10−6＜ τ/2=0.08s,i.e.,the parameters of the experiment satisfy the theoretical stability requirement,which in turn speaks to the stability of the system as shown from Fig.11 to Fig.15.The same approach can also be used to verify the system stability in other experiments.

Fig.14 Aggregate incoming traffic of a link.

Fig.15 Link price.

6.3 Robustness to link bandwidth changes

The purpose of the experiments is to test the robustness of the OFEX controller upon the sudden network changes,i.e.,link bandwidth variations,which can take p lace either in a multi-access network due to traffic contention or interferences such as those found in shared Ethernet or IEEE 802.11.In this section,w e will show how the OFEX controller is capable of dealing with such disruptive network dynamics.The experiment is conducted under a bottleneck bandwidth varying between 5～8Gbps.We setandB=192000 packets.The w eight Ψ in the flow s from FTP groups 1–5 are 46386.72,19531.25,30517.58,24414.02 and 12207.03,respectively.To create bandwidth changes,the initial bandwidth of 6Gbps is increased to 8Gbps att=40s first.Then two consecutive decreases follow:one from 8Gbps to 6.25Gbps att=60 s and the second from 6.25Gbps to 5Gbps att=80 s.Finally,we increase the link bandwidth the second time from 5Gbps to 7Gbps att=100s before end of our simulation.with respect to their previous levels,these four variations represent a change of 33.33%,21.88%,20%and 40%in link bandwidth,respectively.For example,when the bandwidth increase from 6Gbps to 8Gbps att=40s,the change is(8Gbps–6Gbps)/6Gbps=33.33%with respect to 6Gbps.

Fig.16 com pares the target bandwidth and the actual bandwidth utilized.Generally,the actual link bandwidth well follow s the change of the target bandwidth.After the link utilization reaches the steady state att=3s,it stabilizes at the target bandwidth of 6Gbps in the first 40 seconds.In the follow ing,w e shall m ake observations w hen the bandwidth increases(att=40s andt=100 s),and when the bandwidth decreases(att=60s andt=80s).

Fig.16 bandwidth variations.

When the bandwidth suddenly jumps to 8Gbps att=40s,the actually utilized bandwidth reaches its target within 1 second,and stays there before the bandwidth decreases att=60s.A similar trend can be observed for the second bandwidth increase when it jumps to 7Gbps from 5Gbps att=100 s.The only difference is that it stabilizes at the current target bandwidth before the simulation terminates att=120s.Upon the first bandwidth decrease att=60s,as seen in Fig.16,the actual bandwidth utilization goes down to the target bandwidth in 1 second.The second bandwidth decrease from 6.25Gbps to 5Gbps att=80 s presents the similar trend.

In summary,our controller can well utilize the available bandwidth and make it match the ever-changing link capacity thus demonstrating its robustness to high speed bandwidth dynamics.

Fig.17 depicts the instantaneous queue size.When the controller first starts,the queue size shows a buildup of maximum 6200 packets in the first 10 seconds,and then drops back to nearly zero.When the bandwidth decreases from 8Gbps to 6.25Gbps att=60 s,the queue length sharply rises to 38090 packets in response to the bandwidth loss(i.e.,1.75Gbps),but it returns to zero in 3 seconds.The second queue increase happens att=80s due to the second bandwidth downsizing from 6.25Gbps to 5Gbps,and this time the queue length rises to 45030 packets after a bandwidth loss of 1.25Gbps,but it also returns to zero quickly.As noticed,in both bandwidth decrease cases,the queue size increase is far below the buffer size of 192000 packets(which was designed according to the network BDP),and thus there is no any packet loss.It is interesting to see that there is no queue size change when bandwidth increases att=40s ort=100s.In such moments,the link outgoing capability suddenly becomes larger while the incoming traffic still stays as before.The queue size is supposed to decrease,however,it is already at a near-zero level as shown in Fig.17 and it has no space to decrease.

Fig.17 Instantaneous queue size.

Fig.18 shows the source dynamics upon bandwidth variations.As shown,after the controller reaches the steady state in the first 3 seconds,the sources can adjust their sending rates as expected each time the link bandwidth changes.

Let us first examine flow s from FTP group 1(rep-resented by flow 7)in Fig.17.When the link bandwidth rises from 6Gbps to 8Gbps att=40s,the flows increase their sending rates from 101.82Mbps to 135.41Mbps in 1 second and then stabilizes at that level.When responding to the decrease of the link bandwidth from 8Gbps to 5Gbps att=60s,the flows decrease their sending rates from 135.41Mbps to about 106.80Mbps in 1.5 seconds.When the bandwidth downsizes again att=80s,the sending rate of the flow s decreases to about 85.75Mbps this time and then stays there.When the bandwidth increases the second time att=100s from 5Gbps to 7Gbps,they increase their sending rate to averagely 119.97Mbps.The flow s in other groups(represented by flow s 27,47,67 and 87)demonstrate similar behaviors upon bandwidth variations.The only difference is that they operate at a lower throughput due to the fact that they pay a lower price to the router.Their steady share of the bandwidth in each time segment of different link bandwidth can be explained by the proportional fairness as discussed in Section6.2.However,the RM(Revenue Management)[25]concept can be used to exp lain the changes att=40,60,80 and 100s as will be discussed with Fig.19.

Fig.18 The source dynamics.

Fig.19 Link price.

Fig.19 show s how the unit link bandwidth price(represented by the Lagrange multiplier)varies with respect to the bandwidth change in the router.After the controller starts,the unit link price converges to 3.72 after 4 seconds and remains at this level.When the bandwidth increases from 6Gbps to 8Gbps att=40s,the unit link price goes down to 2.79 in 0.5 seconds because of the presence of m ore available bandwidth.Then,when the bandwidth begins to shrink from 8Gbps to 6.25Gbps att=60s,the unit link price goes up to 3.58 in 1 second to reflect the shortage of some available bandwidth.The same observation is also applicable to the second bandwidth shrinkage aftert=80 s,where the unit link price increases to 4.47 and stabilizes there.Finally,the price decreases to 3.19 att=100 s when the bandwidth increases to 7Gbps from 5Gbps.

According to equation(8)in Section 2,it is readily seen the changes of the source sending rate(as shown in Fig.18)well reflects the above evolution of the unit link bandwidth price(as shown in Fig.19)because equation(8)shows how these two variables are related.

6.4 Stability comparison with other controllers

The comparison of the OFEX controller with the relatively explicit controllers on improving the performances of the multi-bottlenecked users and queueing has been demonstrated in[5].In this section,we shall experimentally illustrate another merit of the OFEX controller:its stable capability to tackle the link bandwidth dynamics(e.g.,in the contention-based multi-access network)which the existing NUM-based relatively exp licit controllers fail.This is because the OFEX controller introduces the instantaneous queue sizeq(t)in the system model as a remedial measure to counter such an impact.The interested reader can read the references listed in[5]for the theoretical analysis of the relatively explicit controllers.Due to space limit,we do not put them here.

To show the improved stability performance of the OFEX controller in dynamic link bandwidth conditions over the relatively explicit controllers,we set up a 1Gbps link in Router 1.To produce the link bandwidth dynamics,the link bandwidth will be reduced to 880Mbps att=40s,and then to 675Mbps att=60s.Again,this is one comm on scenario in contention-based networks.Finally,the bandwidth will recover to 1Gbps att=80s.The parameters of the OFEX controller are δ=0.05,and γ=1.The weights Ψ in the flows from FTP groups 1–5 are 12207.03,4882.81,9765.62,7324.22 and 2441.4,respectively.

To com pare with the relatively exp licit controller,w e use the same parameters and configuration as with the OFEX controller except for the parameter which it does not have.We also com pare with the XCP controller[20]because it also has problem s upon dynamic bandwidth due to the limitations of their controller parameters(i.e.,α=0.4,and β=0.226asset in[20]).The two controllers have the same buffer sizeB=24000 packets and the same configuration from Table 1 as the OFEX controller.

Figs.20–22 demonstrates the source sending rate dynamics of the three controllers upon changes of the link bandwidth.Fig.20 is the source behavior of the relatively explicit controller.After the transient in the first few seconds,its source sending rate stabilizes at 131Mbps.When the bandwidth decreases att=40s,its sending rate decreases and stabilizes to 102Mbps.However,the second bandwidth reduction att=60s makes the relatively explicit controller render unstable behavior because its sending rate starts to oscillate.When the link bandwidth goes back to the original value att=80s,its sending rate shows recovery,i.e.,increases to the previous 132Mbps,but still has some small fluctuations.Note that the controller can stabilize in the first two occasions,but not after.The reason could be due to the queue built up in the relatively exp licit controller.As will be seen in Fig.23 below,because the relatively exp licit controller has no queue control measure,its queue size builds up quickly after the first link bandwidth reduction att=40 s.After the second bandwidth reduction att=60 s,its queue size has become unstable,so has the queueing delay.As known,the queueing delay is part of the RTT,and unstable RTT could cause the source sending rate unstable.

Fig.20 The relatively explicit controller.

Fig.21 The XCP controller.

Fig.22 The OFEX controller.

The source behavior in the XCP controller depicted in Fig.21 show s the same behavior as with the relatively exp licit controller in the first 40s.However,it becomes unstable beyondt=40s with m any oscillations throughout the rest of simulation.

In contrast,Fig.22 demonstrates the OFEX controller has a good stability performance all the time irrespective of bandwidth dynamics.When the bandwidth shrinks att=40s and 60 s,or when the bandwidth recovers att=80 s,there are hardly any fluctuations.In summary,the introduction ofq(t)in the OFEX controller model has greatly improves its stability against the link bandwidth dynamics,and makes it outperform its counterparts.

Figs.23–25 shows the instantaneous queue sizeq(t)of the three controllers.Fig.23 show s that the relatively exp licit controller has a queue length of 1000 packets after the router is started.When the bandwidth undergoes the first reduction att=40s,its queue size increases sharp ly to almost 16000 packets and then stays there stably until the second bandwidth reduction att=60 s.After the second bandwidth reduction betweent=60s andt=80s,the queue size of the relatively exp licit controller behaves oscillated untilt=88s after the bandwidth recovers to the original capacity.

Fig.23 The relatively exp licit controller.

Fig.24 depicts the queue size of the XCP controller.It keeps a near zero level queue size after the transient in the first 12 seconds.Like the relatively explicit controller,the queue size of the XCP controller sharp ly rises to 23000 packets after the first bandwidth shrink and then stays there but with slight oscillations untilt=80s when the link bandwidth begins to recover.Unlike the relatively exp licit controller,the XCP controller cannot settle down to its original queue level aftert=80 s;instead it keeps on going up and down.

In contrast,the queue size of the OFEX controller depicted in Fig.25 show s better performance than both the relatively exp licit controller and the XCP controller.The OFEX controller renders a near zero queue size after the router is started in the first 8 seconds.Upon the first bandwidth shrink att=40 s,the queue size of the OFEX controller produces a sudden rise(i.e.,close to 6000 packets)but quickly goes back to the near zero level.The second bandwidth shrink att=60s produces the similar trend and the difference is that the queue rises a little higher(about 1000 packets)than the first time.One can see that the OFEX controller keeps its queue size at the near zero level most of the time except those two sudden rises discussed just now,and thus keeping the queueing delay always the smallest.

In summary,along with other experiments whose results are not shown here due to space limitation,the OFEX controller show s a much better performance in its queue size due to the introduction of the instantaneous queue sizeq(t)in its model,and thus significantly improving the queueing delay performance in term s of magnitude as well as smoothness.

Please note,although the XCP controller also considers the queue size in its controller model,the parameter of its queue size is set to be 0.226,which we think it is not big enough to vacate the queue upon link dynamics.That is why it still renders big queue size in Fig.24.However,to increase this parameter(e.g.,bigger than 0.226)may not solve the problem because a big value m ay result in instability of the XCP controller,as analyzed and proved in[20].

7 Conclusions

We have theoretically proved that the OFEX controller can converge to the equilibrium at least as fast as a geometric series.Based on the Nyquist criterion,we have obtained the sufficient and necessary conditions that the OFEX control system with time delay is able to maintain its local stability.Tim e-varying features were considered in our model and the OFEX controller significantly improves the performance against link bandwidth dynamics in contention-based networks.To see how the link bandwidth uncertainty may affect the optimal benefit of a link,the robustness analysis of the OFEX controller is conducted based on the convex theoretic.The performance evaluation using the OPNET modeler has been conducted and showed the effectiveness and superiority of the OFEX controller.The computational complexity is one issue of the OFEX controller that we have observed,and its analysis is left for future work.

References

[1]V.Jacobson.Congestion avoidance and control.Computer Communication Review,1988,18(4):314–329.

[2]V.Jacobson.Modified TCP congestion avoidance algorithm.end2end-interest m ailing list,1990:ftp://ftp.isi.edu/end2end/end2end-interest-1990.m ail.

[3]F.P.Kelly,A.K.Maulloo,D.K.H.Tan.Rate control for communication networks:shadow prices,proportional fairness and stability.Journal of the Operational Research Society,1998,49(3):237–252.

[4]F.P.Kelly,G.Raina.Explicit congestion control:charging,fairness and admission management.Next-Generation Internet Architectures and Protocols,Cam bridge:Cam bridge University Press,2010.

[5]J.Liu,O.W.W.Yang.An optimal and fully explicit rate controller for the high-speed networks.IEEE International Conference on Communications,Budapest,IEEE,2013:3759–3763.

[6]S.Auhuraliya,S.Low.Optimization flow control with Newton-like algorithm.Telecommucation System s,2000,15(3/4):345–358.

[7]X.Lin,N.B.Shroff.Utility maximization for communication networks with multi-path routing.IEEE Transactions on AutomaticControl,2006,51(5):766–781.

[8]K.Ma,R.Mazumdar,J.Luo.On the performance of primal/dual schemes for congestion control in networks with dynamic flows.IEEE Conference on Computer Communications(INFOCOM),Phoenix:IEEE,2008:326–330.

[9]S.Floyd.Connections with multiple congested gateways in packet-switched networks–Part 1:One-way traffic.Computer Communication Review,1991,21(5):30–47.

[10]Y.Zhang,T.R.Henderson.An implementation and experimental study of the explicit control protocol(XCP).IEEE Conference on Computer Communications(INFOCOM),Miami:IEEE,2005:1037–1048.

[11]F.Abrantes,J.Araujo,M.Ricardo.Explicit congestion control algorithms for time varying capacity media.IEEE Transactions on Mobile Computing,2011,10(1):81–93.

[12]F.Abrantes,M.Ricardo.XCP for shared-access multi-rate media.Computer Communication Review,2006,36(3):29–38.

[13]S.Boyd,L.Vandenberghe.Convex Optimization.Cambridge:Cam bridge University Press,2004.

[14]D.P.Bertsekas.Nonlinear Programming.2nd ed.Nashua:Athena Scientific,1999.

[15]Z.Xiao,F.Lin.Variable step-size LMS algorithm based on modified secant integral function.Proceedings of the 4th International Conference on Electronics,Communications and Networks,Beijing:CRC Press,2014:1737–1758.

[16]R.Srikant.The Mathematics of Internet Congestion Control.Basel:Birkhauser,2004.

[17]R.C.Dorf,R.H.Bishop.Modern Control System.11th ed.Upper Saddle River:Pearson Prentice Hall,2008.

[18]N.Dukkipati,N.McKeown,A.G.Fraser.RCP-AC congestion control to make flows complete quickly in any environment.IEEE Conference on Computer Communications(INFOCOM),Barcelona:IEEE,2006:3002–3006.

[19]Y.Hong,O.W.W.Yang.Design of adaptive PI rate controller for best-effort traffic in the Internet based on phase margin.IEEE Transactions on Parallel and Distributed System s,2007,18(4):550–561.

[20]D.Katabi,M.Handley,C.Rohrs.Congestion control for high bandwidth-delay product networks.Computer Communication Review,2002,32(4):89–102.

[21]Y.Zhang,D.Leonard,D.Loguinov.JetMax:scalable max-min congestion control for high-speed heterogeneous networks.IEEE Conference on Computer Communications(INFOCOM),Barcelona:IEEE,2006:1204–1216.

[22]M.E.Crovella,A.Bestavros.Self-similarity in world w ide web traffic:Evidence and possible causes.IEEE/ACM Transactions on Networking,1997,5(6):835–846.

[23]OPNET Technologies Inc.OPNET Modeler Manuals.OPNET version 11.5.2005.

[24]D.Gross,J.Shortle,J.M.Thompson,et al.Fundamentals of Queueing Theory.4th ed.New York:John W iley&Sons,2008.

[25]M.Muller-Bungart.Revenue Management with Flexible Products.New York:Springer,2007.