WIXLIB

2network. The rate control at individual sources is based onthe “prices” fed back from all the links in the data paths. Thecomputation of the “price” is in turn based on the sendingrate information fed back from all the sources using this link.Since only a relaxation of the original optimization problemis solved, it is not proven that the algorithm converges to theoptimal traffic allocation. The same formulation is used inthe work by La, et al. [16] where the algorithm provided isproven to converge to the optimum rate allocation in the singlecongested link case (low traffic networks).Low [19] uses a technique which converts a constrainedproblem into a non-constrained dual problem. This reformulation results in a similar distributed control scheme to theone presented in [15]. Iterative algorithms were also proposedand their convergence is proven for the single-path case. Asimilar approach is taken by Sarkar, et al. [25] to address theoptimization-based multi-rate multicast. A distributed controlscheme is proposed and it degenerates to the one in [19] whenthere is only one path in the multicast tree.An interesting work on dynamic multi-path routing whichbears some common features with the present work was givenby Su and de Veciana [27]. The authors considered dispersiverouting of the packets in a given flow to multiple pathsbased on the information obtained from the routing link stateupdates. An attempt was made to achieve optimal dynamicmulti-path dispersion. An asymptotic result for a simple multilink network was obtained, which provides insights on thedevelopment of three dynamic multi-path routing schemes.One of the scheme leads to high network utilization suggestingthat it is a robust dynamic multi-path routing scheme.B. A New Approach to Decentralized TEMost of the existing optimization-based algorithms mentioned in the previous section are based on the Lagrangianapproach, which is not viable for problems with a large numberof constraints; e.g., see [13]. Each resource constraint resultsin a Lagrangian multiplier (or “price”) which needs to beperiodically updated and distributed to the sending sources.In turn, the source also needs to periodically inform the linksalong the path of its updated rate. Recently, it has beenshown [1], [9], [10], [14] that the price at each link can becalculated using the aggregated flow rate at that link insteadof the flow rates from individual sources. This eliminatesthe need for the sources to periodically inform the linksof their sending rates, reducing the control traffic overhead.However, as value added services (such as multiple CoSs orvirtual private networks) are introduced, the more constraintsthe control law should take into account and, therefore, thegreater the number of “prices” that has to be computed. Thisresults in a large overhead, regardless of where these pricesare estimated. This might be the reason why, up until now, onehas not seen an implementation where a significant number ofvalue added services is offered.In parallel with our research effort, Kar et al. [12] havedeveloped a technique which also leads to optimal trafficallocation using only binary feedback from the congestednodes. However, the approach presented addresses the caseneither of multiple paths nor of multiple CoSs.To appear in IEEE/ACM TRANSACTIONS ON NETWORKINGIn view of the importance of traffic engineering in thepresence of multiple CoSs in the next generation IP Internet,in this paper, we introduce a new approach to tackle thisproblem. This approach has its basis on nonlinear controltheory. The proposed technique enables optimal distributedTE in a multiple-path and multiple-CoS network. It allowsingress nodes to independently adjust their CoS-based trafficsending rates or/and redistribute traffic load among multiplepaths, solely based on binary feedback information from thecongested nodes. The proposed technique can be applied toany utility function that can be represented as a sum of concaveterms. The technique can be used for TE with multiple CoSs;e.g., minimum rate guarantee, and/or maximum allowed rate,and assured CoSs, as proposed in this paper.This new approach is potentially very useful for optimal TEin a differentiated services enabled MPLS network where CoSbased TE is desirable [18]. The assured CoS is particularlyuseful for network resource optimization when the edge nodescoincide with the boundary nodes of an administrative domain.In this case, the gross traffic volume of a given CoS that canbe injected into the domain is normally a given value basedon the service level agreement between service providers. Theadministrative domain should not throttle the traffic as long asgross traffic volume does not exceed the negotiated maximumvolume. Hence, the only means for the administrative domainto optimize its resource utilization is to do load balancing, notrate adaptation.This paper also provides a way to address a critical issue:Oscillation. The results in [17] are generalized, giving rise toa much larger set of adaptive control laws. Members of thisset can be chosen in such a way as to attenuate the adverseeffects of delays and quantization.C. Sliding ModesAs mentioned above, the approach has its basis in nonlinearcontrol theory. More specifically, we use results from thetheory of Sliding Mode Control (also known as VariableStructure Control). Sliding Mode Control has been widelyused in the control of nonlinear systems both in the presenceand absence of uncertainty; for an introduction on the useof Sliding Modes in control systems; e.g., see [26]. Manysuccessful applications of this theory have been documented,from the control of robotic manipulators to the control ofunderwater vehicles.Of particular interest to the problem addressed in thispaper is the use of Sliding Mode theory in mathematicalprogramming. The results in [13], [28] indicate that SlidingMode theory can be a powerful tool for optimizing convexfunctions subject to a large number of convex constraints.Motivated by these results, in this paper, we develop a classof adaptive control laws that converge to the optimal network resource allocation. These adaptive control laws allowdistributed multi-path flow rate adaptation and load balancingat individual sources. The only information required is binaryfeedback from each congested node in the path. We also showthat the same technique can be applied to assured servicetraffic with given target rates (AS), traffic with minimum

LAGOA et al. ADAPTIVE CONTROL ALGORITHMS FOR DECENTRALIZED OPTIMAL TRAFFIC ENGINEERING IN THE INTERNETrate guarantee (MRGS) and/or upper bound allowed rates(MRGUBS/UBRS).D. The SequelThe remainder of this paper is organized as follows. InSection II, we introduce the notation that is used throughoutthe paper and provide an exact statement of the problem to besolved. Section III is dedicated to the presentation of the familyof decentralized control laws. In Section V, we provide someinsight on how to design the control parameters in order toaddress some of the problems that one encounters in a practicalimplementation. Examples of application of the proposed approach are presented in Section VI. Conclusions and directionsfor future research are given in Section VII. Finally, a proofof the main results is provided in the Appendix.II. P ROBLEM S TATEMENTBefore presenting the main results, let us first introduce thenotation that is used throughout this paper.A. NotationIn our model, the traffic flows are assumed to be describedby a fluid flow model and the only resource considered islink bandwidth. In the remainder of this paper we will use theterms call, session and flow interchangeably.Consider a computer network where calls with differentservice requirements are present. We divide these calls intotypes. Types are aggregate of calls that, from the point a viewof the traffic engineering algorithm, can be treated as a unit;i.e., these are calls with the same ingress and egress nodes andthe service requirements are to be applied to the aggregate,not the individual calls. One can have call types with justone call. Moreover, one can have different call types with thesame ingress/egress node pair. We assume that each call typemight have several paths available. The objective is to findthe allocation of the resources that leads to the maximizationof a given utility function subject to the network resourceconstraints and CoS requirements.More precisely, consider a computer network whose set oflinks is denoted by L , with cardinality card (L ) equal to itsnumber of links. Let cl be the capacity of link l L , n be thenumber of types of calls, ni be the number of paths availablefor calls of type i and Li, j be the set of links used by calls oftype i taking path j. Given calls of type i, let xi, j be the totaldata rate of calls of type i using path j. Also, let.xi [xi,1 , xi,2 , . . . , xi,ni ]T Rnidenote the vector containing the data rates allocated to thedifferent paths taken by calls of type i and T. x xT1 , xT2 , . . . , xTn Rn1 n2 ··· nnthe vector containing all the data rates allocated to differentcall types and respective paths. Now, a link l L is saidto be congested if the aggregated data rate of the calls usingthe link reaches its capacity cl . Given this, define bi, j (x) asthe number of congested links along the j-th path of calls oftype i. Finally, let u(x) be the unit step function; i.e., u(x) 1if x 0 and u(x) 0 otherwise.3B. Problem StatementThe results in this paper aim at solving the problem ofmaximizing utility functions of the formnni 1i 1.U(x) fi (xi ) fi (xi,1 , xi,2 , . . . , xi,ni ) ,subject to the network constraints and CoS requirements,where fi (·), i 1, 2, . . . , n , are differentiable increasing concave functions.We assume that five categories of CoSs share the network:Calls of type i, i 1, 2, . . . , s1 , are assumed, without loss ofgenerality, to be of Assured Service (AS) CoS category. ByAS we mean that a target rate for the call should be guaranteedin average sense. More precisely, assuming that the target ratefor xi is Λi , the objective is to allocate the data rates in sucha way thatni xi, j Λi ,j 1for all i 1, 2, . . . , s1 . Calls of type i, i s1 1, s1 2, . . . , s2 ,are assumed to be of the Minimum Rate Guaranteed Servicecategory (MRGS). More precisely, this type of calls shouldsatisfy the following requirementni xi, j θi ,j 1for some θi 0 and all i s1 1, s1 2, . . . , s2 .Calls of type i, i s2 1, s2 2, . . . , s3 , belong to the UpperBounded Rate Service (UBRS) category; i.e., there is an upperbound on the maximum bandwidth that can be used. Moreprecisely, traffic should be allocated in such a way that callsof type i satisfyni xi, j Θi ,j 1for some Θi 0 and all i s2 1, s2 2, . . . , s3 .Next, calls of type i, i s3 1, s3 2, . . . , s4 , are defined tobe of the CoS category consisting traffic with both a MinimumService Guarantee and an Upper Bounded Rate (MRGUBS);i.e., traffic should be allocated so thatθi ni xi, j Θi ,j 1for some θi 0, Θi 0 and all i s3 1, s3 2, . . . , s4 .Finally, calls of type i, i s4 1, s4 2, . . . , n are assumedto be of the Best Effort (BE) class. Calls of this class do nothave any further service requirements.Given this, the problem of optimal resource allocation canbe formulated as the following optimization problem:max U(x)xsubject to the network capacity constraints i, j : l Li, jxi, j cl 0;l L,the AS requirementsni xi, j Λi ;j 1i 1, 2, . . . , s1 ,

4To appear in IEEE/ACM TRANSACTIONS ON NETWORKINGthe MRGS requirementsni xi, j θi ;i s1 1, s1 2, . . . , s2 ,j 1For i s2 1, s2 2, . . . , s3 (UBRS calls), let"# fiM Mẋi, j zi, j (t, x) α bi, j (x) βi ri (xi ) δi, j u( xi, j ) , xi, j xiwherethe UBRS requirementsni xi, j Θi ;i s2 1, s2 2, . . . , s3 ,j 1riM (xi ) the MRGUBS requirementsθi ni xi, j Θi ;i s3 1, s3 2, . . . , s4j 1and all data rates are nonnegativexi, j 0; 0 ifIII. FAMILY OF D ECENTRALIZED C ONTROL L AWSIn this section we present the main result of this paper: Afamily of decentralized control laws which converge to themaximum of the given utility function subject to the networklink capacity constraints and AS requirements. Before statingthe main result, we describe the form of the control laws usedin this paper.A. The Family of Control LawsDefine the following family of control laws: For i 1, 2, . . . , s1 (AS calls), let"# fiẋi, j zi, j (t, x) α bi, j (x) βi ri (xi ) δi, j u( xi, j ) , xi, j xiwhereri (xi ) 1 if 1 ifni xi, j Λij 1ni xi, j Λi 0 if j 1 1 ifni xi, j θij 1ni xi, j θij 1.j 1ni xi, j Θi.j 1βiM riM (xi ) δi, j u( xi, j )where again 0 if rim (xi ) 1 ifni xi, j θij 1ni xi, j θi; riM (xi ) j 1 1 if 0 if#,ni xi, j Θij 1ni xi, j Θi.j 1For i s4 1, s4 2, . . . , n (BE calls), let#" fi α bi, j (x) δi, j u( xi, j ) .ẋi, j zi, j (t, x) xi, j xiIn the equations above zi, j (t, x), α , βi , βim , βiM and δi, j aredesign parameters and bi, j is (as defined in the previoussection) the number of congested links encountered by callsof type i taking path j. Note that the laws above can beconsidered to be similar to the TCP congestion control lawsused in today’s Internet in the following sense: The datarate is increased until congestion occurs. Once congestion isdetected, the data rates are decreased. This continues until anequilibrium is achieved.Actually, the TCP congestion protocol is very close to aparticular case of the control laws above. To see this, assumeeach type of calls has just one path available. Furthermore,assume that the data rates are bounded away from zero andthat the utility function that one wants to maximize isn.For i s1 1, s1 2, . . . , s2 (MRGS calls), let#" fim mẋi, j zi, j (t, x) α bi, j (x) βi ri (xi ) δi, j u( xi, j ) , xi, j xiwhereni xi, j ΘiFor i s3 1, s3 2, . . . , s4 (MRGUBS calls), let" fi α bi, j (x) βim rim (xi ) ẋi, j zi, j (t, x) xi, j xii 1, 2, . . . , n; j 1, 2, . . . , ni .Obviously, the optimization problem above is a convexproblem; i.e., maximizing a concave function over a convexset. If global information is available then algo

University of Texas at Arlington. Email: hche@cse.uta.edu a connection-oriented network such as Multi-Protocol Label Switching (MPLS) and Asynchronous Transfer Mode (ATM) networks, a widely used approach is to set up multiple paths between an ingress-egress node pair and distribute traffic