Available online at www.sciencedirect.com
%# ScienceDirect
Computer Communications 29 (2006) 3265-3276

www.elsevier.com/locate/comcom
Dynamic bandwidth reservation for label switched paths: An on-line predictive approach
T. Anjali a, C. Bruni b, D. Iacoviello b, C. Scoglio ^
a Department of Electrical and Computer Engineering, Illinois Institute of Technology, Chicago, USA b Department of Computer and Systems Science, University of Rome ''La Sapienza'', Via Eudossiana 18, 00184, Rome, Italy c Department of Electrical and Computer Engineering, Kansas State University, Manhattan, USA
Received 8 March 2005; received in revised form 2 May 2006; accepted 12 May 2006 Available online 8 June 2006
Abstract
Managing the bandwidth allocated to a Label Switched Path in MPLS networks plays a major role for provisioning of Quality of Service and efficient use of resources. In doing so, two main contrasting factors have to be considered: not only the bandwidth should be adapted to the traffic profile but also the effort for bandwidth renegotiation associated with a variation of the allocated bandwidth should be kept at low levels. In this context, we formulate a problem of optimal LSP bandwidth reservation as the one of minimizing a convex combination of the difference between the assigned bandwidth and the estimated future traffic, and of a measure of the frequency of bandwidth variations. The contribution of this paper is to propose a new method to reserve optimally the bandwidth of an LSP, avoiding an excess of bandwidth renegotiations on the basis of prediction of future traffic, assuming a simple birth-and-death model to describe the traffic dynamics. Whenever the prediction is inaccurate due to unpredictable variations in the characteristics of real traffic, a suitable ''emergency procedure'' is proposed, which performs a new traffic prediction and a consequent modified bandwidth reservation. Numerical results are presented which show the effectiveness of the method and the achieved performance, both for simulated and real data traffic. © 2006 Elsevier B.V. All rights reserved.
Keywords: Internet traffic measurement; Network control; Optimal bandwidth allocation; Filtering; Forecasting
1. Introduction
One major problem in the management of the current large networks is the complexity and the enormous amount of operations required to satisfy user demands while using resources efficiently. To reduce this complexity, DiffServ aware MPLS architecture can be adopted, where connections belonging to the same class from a source to a destination can be aggregated on a virtual tunnel called Label Switched Path (LSP) and treated in the network in the
q The work of C. Scoglio was supported by NSF under award number
0219829.
qq The work for this paper was initiated while T. Anjali and C. Scoglio were at the Broadband and Wireless Networking Laboratory, Georgia Institute of Technology, Atlanta. * Corresponding author. Tel.: +1 785 532 4646; fax: +1 785 532 1188. E-mail address: caterina@ksu.edu (C. Scoglio).
same way as a group. LSPs are characterized by a initial router (source), a final router (destination), the path over which the LSP is routed, and a given reserved bandwidth. In this paper, we consider the problem of the dynamic LSP bandwidth reservation, as a function of the traffic. Consider the traffic profile shown in Fig. 1. If the bandwidth assigned to the LSP is kept to a fixed value not less than the peak, a large amount of non-utilized bandwidth is wasted as illustrated by scheme 1 in the figure. On the other hand, if the LSP bandwidth reservation is fixed at a relatively lower value, possibly the mean, congestion occurs, with the consequent deterioration of the quality of service, when the actual traffic is above the reservation. This is illustrated by the scheme 2 in the figure. In other words, the LSP bandwidth should be adapted to the traffic profile, for example as shown in the scheme 3 of the figure. However, the renegotiation of the LSP bandwidth requires some predictive capability and a control effort which introduce a

Fig. 1. Traffic profile.
processing cost that has to be taken into account. Consequently, it is very critical to find a good balance between the conflicting goals of adapting the bandwidth of the LSP to the traffic profile and minimizing the management complexity.
The field of dynamic bandwidth reservation is not new, but the results available are limited due to the difficulty in modeling and characterizing the dynamic traffic profiles accurately. Several approaches have been proposed in the literature for this problem. The first application of dynamic bandwidth reservation is for Virtual Paths (VPs) in ATM networks [1-3]. These approaches are based on Markovian assumption for the traffic arrival process. Recently, in the same context, a similar problem has been considered in [4], where agents are used to assign the capacity to the VPs using a simple operational rule to determine the amount of bandwidth to be allocated. The problem is formulated by accounting for bandwidth utilization and connection processing constraints. After decomposing the problem at link level and approximating the link model, an optimal solution is obtained. However in this approach the processing rate of the network and its cost are treated as constraints and it is assumed that the agent knows the actual value of the active connections. Other results on the dynamic bandwidth reservation are in the field of network management to allocate bandwidth to aggregations of traffic flows [5-8]. Another approach for bandwidth allocation based on measurements is given in [9]. However, the analysis considers only the packet level and forecast is carried out without considering any flow or session at the application level. The third application is for LSP bandwidth reservation in MPLS networks [10]. Cisco MPLS AutoBandwidth allocator monitors the peak traffic through the LSP for a small time interval keeping track of the largest peak over a longer interval, and then re-adjusting the LSP bandwidth based upon the largest peak for that longer interval.
In this paper, we formulate the problem of optimal LSP bandwidth reservation assuming as cost function a convex combination of the difference between the assigned bandwidth and the predicted traffic and of a measure of the fre-
quency of bandwidth variations. In some special cases it is possible to know the amount of future traffic, for example when the traffic is generated by an on-demand preplanned service such as virtual dedicated lines or video on-demand. However in general, traffic is not known in advance and is very variable. Consequently, in order to assign the bandwidth to the LSP properly, it is important to predict the traffic profile for a limited future interval, on the base of noisy measurements performed in the past. Summarizing, in this paper we propose a new method to optimally reserve the LSP bandwidth, minimizing the risk of congestion and bandwidth wastage and at the same time the bandwidth variation cost. Traffic prediction is performed using the past traffic measurements and assuming a birth-and-death model for the traffic dynamics. At each decision instant, the proposed method calculates the optimal value of the capacity to be reserved for the future time interval, as well as the length of the same interval. At the end of each interval, a new optimal bandwidth reservation is calculated along with a new duration of validity.
Since the prediction can have a variable accuracy depending on the traffic characteristics, we have complemented our method with an ''emergency procedure''. If the bandwidth assigned to the LSP is lower than the carried traffic, but the traffic is ''elastic'' [11] and can tolerate delays, the optimal solution is still satisfactory. However, if the traffic is ''streaming'' and the bandwidth on the LSP is not enough, it is necessary to verify on-line the difference between the estimated traffic and the assigned bandwidth, and perform the ''emergency procedure'' when this difference is greater or less than suitable given thresholds.
Our proposed method allows the allocated bandwidth to follow the traffic profile closely, while reducing the renegotiation effort drastically. Furthermore, our method is characterized by few parameters, whose values have to be chosen by the network operator to obtain the desired behavior. Finally, the time to compute the solution is small enough to allow the on-line use of the method.
In Section 2, the dynamic stochastic model of the traffic and the related measurement equations are presented; also suitable algorithms for traffic filtering and prediction are
described. In Section 3, the optimal allocation problem is formulated as an iterative on-line problem, the existence of the optimal solution is proved and an analytical method to find the solution is provided; also the ''emergency procedure'' to recover from large prediction errors is described. Finally, in Section 4, the proposed method is tested and validated by considering simulated and real traffic traces and by comparing it with commonly used reservation procedures.
2. Modeling and estimating traffic on a label switched path
In this section we will recall some results which have been previously deduced [12] with reference to the problem of modeling the number of active connections on a telecommunication link and in particular on an LSP, as well as the one of filtering and forecasting the same quantity, by exploiting noisy measurements available in discrete times. Let x(t) 2 {0,1,2,N} denote the number of active connections at time t in a given communication link. A simple birth-and-death model for x(t) may be given as follows:
dx(t) = k(N — x{t))dt +[dv1 (t) — k(N — x(t))dt] — (jx(t)dt —[dv2 — ix(t)dt]
(1)
where v1 (t), v2 (t) are doubly stochastic independent Pois-son processes with rate k(N — x(t)) and fix(t), respectively, k and i being the birth and death rates assumed to be known, constant and non-negative. Initial condition x(t0) for Eq. (1) is assumed statistically known.
All connections are supposed to employ the same known bandwidth C. A bandwidth broker is naturally interested in knowing the total bandwidth requested Cx(t). To that purpose, at the discrete times ti, i = 0,1,a specific device yields a measurement y (ti)of Cx (ti) which is affected by an error n (ti):
y(ti) = Cx(t,)+ n(ti)   i = 0, 1, ...
(2)
The sequence {n(ti), i = 0,1,...} is assumed to be white. Each error sample n(ti) is such that y(ti) 2 {0,1,yM} where yM = CN. Besides, the same sequence is probabilistically characterized by the values qh(ti|k) defined as follows:
qh (ti\k)=P (y(ti)=h\x(ti)=k),
h 2{0, 1,      yM},   k 2{0, 1,      N}(3)
Denoting by pk(t|i) the probability that x(t)= k, given the values of y(tj), j=0,1,...,i, introducing the (N+1) -vector
p(t\i) = (j>0(t\i)P1(t\i)---PN (t\i))T
the following iterative equation can be deduced:
(t   ,., n =  Uh(i + 1) exp{Q(tm — ti)}p(ti\i) 1 1    1TUh(i + 1) exp{Q(t+1 — tl)}p(tl\i)
where 1T = (11 ■■■ 1)2 0N+1 and
Nk    —[(N — 1)k + i] 2f 0
0 (N — 1)k       —[(N — 2)k + 2f]   3fi
0
0 0
0
0
Uh(i + 1)= diag {qh(t+1\k)}
06k6N
2k   —[k +(N — Nfi
0 k —Nfl
and where the initial value p(t0|0) is assumed to be known.
The optimal estimate x (t\i) of x(t), t 2 (ti, ti+1] given the measurements y(tj), j=0,1,...,(i+1), can be obtained by minimizing the conditional variance of the estimate error, and, as far as the filtering is concerned, it results in
xx ti+1\i+1)=
LTUh(i + 1) exp{Q(ti+1 — ti)}p(ti\i) 1TUh(i + 1) exp{Q(ti+1 — ti)}p(ti\i)
(4)
where LT = (012 ■■■ N). Furthermore, for the corresponding conditional mean value of the estimate error, we have
r2 (ti+1\i + 1) =
MTUh (i + 1) exp{Q(ti+1 — t,)}p(t,\i) 1TUh(i + 1) exp{Q(ti+1 — ti)}p(t,\i) — X2(t+ \i + 1)
5)
where MT = (014 ■■■ N2). As far as the forecasting estimate is concerned, from Eq. (1) we have:
x(t\i)= exp{—(k + i)(t — ti)}x(ti\i)
+ ^ (1 — er(k+i)(t—ti)), t 2(t„ t+1] k + fi
and for the corresponding variance:
r2 (t\i)= e—2(k+i)(t—ti)r2(tl+ jf e—2(k+i)(t—u) [kN —(k — n)x(u\i)]du,   t 2(ti, ti+1]
(6)
(7)
Updating the estimation of x and of the related error variance by Eqs. (4) and (5) requires the computation of eQt. In order to avoid this effort, in [12] some approximated methods have been proposed; they assume that the distribution of x(ti) conditioned upon the observations y(tj), j =0,1,2,i and the distribution of y(ti) conditioned upon x(t{) are both uniquely defined by their mean value and variance. The most popular choice is to assume that both the above distributions are gaussian. This, of course, not only cancels the discrete character of x(ti) and y(ti), but also broadens their support (naturally positive and bounded) to the whole 01.
With this last assumption, Eqs. (4) and (5) give rise to the well-known Kalman-Bucy filter:
x(t+1\i + 1)= X(ti+1\i)+K(i + 1)\y(t,+1) — CX(t,+1\i)] (8) r2 (t+1 \i + 1) = [1 — CK (i + 1)]r2(tm\i)(9)
where the innovation gain K (i + 1) is given by
Q
K i+1)=
Cr2 ti+1\i)
C2r2(t,+1\i) + ^n(tl+1)
10)
and rn2 t +1 ) denotes the variance of n(ti+1). As far as the forecasting step is concerned, the expressions (6) and (7) still hold.
In the next section we will consider a problem ofoptimal bandwidthallocation, by exploitingthe results ofasuitable filtering and forecasting procedure. Note that the formulation and the solution of this problem is independent of the adopted filtering method; therefore in the following section we will not specify which one of the above filtering procedure will be considered. In Section 4 we will test and validate the proposed optimization procedure and in this case we will choose a particular estimation method.
3. A predictive on-line method for the optimal allocation of the bandwidth
In this section the problem of LSP bandwidth reservation is formulated as an on-line iterative control problem. On the basis of the prediction x(t\i) for the number of active connections obtained by using one of the filters described in the previous section, the optimal values of the bandwidth xi0 to be reserved and the interval A° of time for which this reservation is maintained need to be calculated. In the following, the existence of the optimal solution is proved and an analytical method to find this solution with a low computational effort is also provided. Finally, the ''emergency procedure'' is described. This latter action can be used when the difference between the estimated traffic and the assigned bandwidth is greater than a given threshold.
3.1. Problem formulation and solution
In order to formulate an optimization problem for the bandwidth allocation, we will assume that
x(t)= xi 2[0,N],   8t 2[ti, t+1 ) = [ti, ti + Ai), i = 0, 1, 2, ...
Furthermore we assume to have reasonable information about the future bandwidth requirement in an interval [ti, t{ + TJwith Ti suitably fixed.
In the subinterval [ti, ti + Ai) a possible solution for the allocation problem is identified by the couple of number (xi, Ai) and the admissible set is
Di = {(xn Ai)2 02 : x, 2[0,N], A 2[0, T,]}
The cost of the generic solution should take into account two different and opposite requirements. The first one is related to the interest of achieving a good fitting between the allocated bandwidth xi and the predicted requirement xx t\ ). A reasonable estimation for the future requirements is provided by the prediction given by Eq. (6).
The second requirement is related to the interest of minimizing the number of commutations for xi, that is of maximizing the length of each subinterval Ai.
A possible choice for the cost index is therefore
/ti+Ai (x(t\i)—xi)2dt —(1 — a) A,
where a 2 [0,1] is a weight factor, suitably fixed.
At this point, we can consider a sequence of optimization problems, consisting in the determination of the global minimum (x0, A0) for J over D,, which can be solved on-line at each instant ti, i = 0,1,2,...
We note that the generic problem admit a solution, being Di compact and J continuous over Di. Furthermore, it is useful to observe that no optimal solution exists for Ai = 0. In fact
J(x„ 0)=0   8x, 2[0, N]
while, assuming xt = x(ti\i) and A, = e, we have
J(x(ti\i), e) 6 ae max {[x(t\i)—x(ti\i)]2} — (1 — a)e
t2[ti,ti+e]
Taking (6) into account, it can be easily verified that the first term of the above inequality is o (e2). Then, for e >0 sufficiently small, we have
J(xc(ti\i), e) 6 (a — 1)e < 0
In order to search for the optimal solution, we can exploit the well-known Kuhn-Tucker Theorem [13,14] which yields the extremals of the problem. Defined the Lagrang-ian function
ti+Ai 2
L(x,, Ai, g)=a J'      (x(t\i)— xi) dt —(1 — a)Ai — g1x,
+ g1(xi — N)— g3 a, + g4(Ai — Ti)
where g = (g1g2g3g4)T is the vector of the Kuhn-Tucker multipliers, the necessary conditions for the minimum are
0L f ti+Ai
= — 2a /      (x(t\i)— xi)dt — g1 + g2 = 0
9xi
= a(x(ti + Ai\i)— x, ) —(1 — a) — g3 + g4 = 0
g1xi = 0
g2 xi — N)=0 g3Ai = 0 g4 Ai — Ti)=0
g, P 0,   i = 1,2,3,4
Solving the necessary conditions and taking into account the admissibility conditions and the above observation about the positivity of any possible optimal Ai, the following result holds.
Proposition 1. For each s > 0, denoting by
1    ti+s
1   ti+s
x(s)= -        x(u\i)du
11)
the set of the extremals of the problem is not empty and is constituted by the following solutions:
• the couples
(x(A*), A*),   VA*e(0, T,) :x(t,+Affi\i)
= x(A*)±^i^ (12)
• the couple (x(T,), T,) if
x(t, + Tl\i)e x(T,)- W1^, x(T,) + (13)
V    a V    a
Taking Eqs. (6) and (11) into account, with easy computation, Eqs. (12) and (13) can be, respectively, put in the form
the couples xi*, Ai*) with
kN     1 — e—(k+i)A A. . .
x* = --1—rz-r—~t—  xltAi)
i    k + i     (k + i)A*   V
for each Ai* 2 0, Ti) such that:
e—(k+i)A*(1 + (k + i)A*) — 1
kN k + fi
14)
= ±-
k + f )Ai
k+f
k + f )xx ti\i)—kN the couple xi*, Ti) with:
kN   1
xt =—--+
e—(k+i)Ti
k + i     (k + fi) T'
xx ti\ i)—
kN ' k +1
if
xx ti + Ti\i)2
1a
1a
(15)
16)
17)
By analyzing the above results, it is possible to give some conclusions about the number ofpossible extremals, candidates for optimal solution of the problem.
Proposition 2. The considered problem admits at most three extremal solutions.
In fact the couples given by Eqs. (14) and (15) are at most two. This statement follows by observing that condition (15) can be put in the form
e—(k+i)A*
where
r
1 ±\r\(k + i)A*
1 + (k + i)A*
18)
k +1
1a
(k + i)xc(ti\i) — kNV    a
Observing that right-hand side of Eq. (18) represents two equilateral hyperboles with vertices in (—1, ±|C|), with an easy geometrical study we have that, if |C| P 1, there is at most one solution corresponding to the lower sign of Eq. (18).If|C|<1, there are at most two solutions, each of which corresponds to one of the signs of Eq. (18). The couple xi* , Ti) with xi* given by (16) can produce the third extremal.
Obviously, in case of more than one extremal, the identification of the optimal solution requires a comparison of the values of the cost index in each of them.
3.2. Choice of Ti
The choice of the upper bound Ti for Ai can be made by exploiting the information about the quality of the forecast given by its variance (7). By substituting (6) into (7) we deduce
r2(t\i)=Ae—2(k+1)(t—ti) + Be—(k+i)(t—ti) +
kfN
(k +1)2,
t > t,   (19)
where:
A = r2(i\i)
B = k—1 k +1
We note that
k
1
xx ti\i)
Nk2
xx ti\i)
Nk(k — 1)
r2
(k +1)2
20)
lim r2(t\i) - „ — 2
Furthermore r2(t|i), as given by (19), turns out to be a monotonic function of t or exhibits at most one instant ~ in which its derivative vanishes
1    ,   /  2A
t = ti+--ln--
k + 1    V   B
Obviously this latter case verifies if — 2A > 1. We suggest to fix Tt such that r2(t|i) remains under a fixed fraction of the limit value rr2. In particular we chose Ti such that:
r2 (t, + Tl\i)=#r2(tl\i) + (1 — #)r2 for a suitably fixed # 2 (0,1).
(21)
Proposition 3. Eq. (21) admits a unique solution Tt > 0 for
i =1,2,... if the initial choice r (t0|0) is such that:
r2(t0\0) < r2
22)
In fact, if (22) holds, the behavior of (19) for i = 0 is mono-tonic increasing or with just one maximum. The Eq. (21) for tt = t0 and i = 0 admits a unique solution T0. The updating of r2(t0+ T0|0) = r2(t1|0) due to the processing of y(tt), leads to r2(t1|1) which is less than r2(t1|0) due to the improvement of the estimation introduced by the new information carried by the measurement itself. This fact is easily verified in the case of Kalman filtering; in fact, substituting (10) into (9) for ti +1 = t1 and i = 0, we have:
r2 (t1\1) — r2(t1\0) = —-
C2r4 t1\0)
C2r2(t1\0) + rnn(t1)
<0
Then, being r2 t1\0) < rr2, it follows that r2 t1\1) < rr2.At this point, repeating the same argument, Proposition 3 is proved.
a
In order to compute Ti in explicit form it is possible to
substitute (19) for t = ti + Ti and (20) into (21), thus
obtaining the equation
Ae—2 k+1)Ti + Be— k+1)Ti + D = 0 23)
where
D = ^N-2 — r2(t\i) (k + 1)2       UU
Solving (23) we have:
T. = -v^— ln-2A (24)
k + 1    —B ± VB2 — 4AC
which gives just one positive solution corresponding to one of the two signs.
3.3. A possible ''emergency procedure''
Obviously the procedure described in Section 3.1 gives a constant value xi to the number of active connections in the interval [ti, ti + A1) which turns out to be more or less accurate compared to the values of the actual active connections x(t) in the same interval. This difference, according to its sign, corresponds to a wasted bandwidth or to an insufficient bandwidth reservation. For elastic traffic, an insufficient bandwidth reservation can be generally tolerated. Minor tolerance can be accepted for streaming traffic and therefore an adjustment procedure can be useful in order to guarantee that the above difference is contained into prescribed limits. The control of the errors introduced by the optimal solution can be made by performing an on-line filtering during each interval [ti, ti + A1) with a fixed step d sufficiently small.
Let us define
'ij =   + jd, j = 1, ~2, ...
and assume to get measurements y(tij) in the same instants. We can calculate the filtering x(tijand assume this quantity in order to control the entity of the errors. We can introduce two positive thresholds m1 and m2 as allowed limits for both the kinds of errors
—m2 6 x(tj\ij)—x°i 6 m (25)
If Xj denotes the first possible instant in which one of the constraints (25) is violated, the suggested adjustment procedure is to assume:
ti+1 = xtij
This amounts to keep valid the optimal solution x° only in the interval [ti,Xij) and to solve a new optimization problem by exploiting the previous procedure starting from the instant xtij.
3.4. Sequential steps ofthe predictive optimization procedure
Finally, in order to summarize the proposed reservation procedure and for the reader convenience, let us report the sequential on-line list of operations which constitute the generic ith sub-problem of filtering-optimization-forecasting.
(1) By means of Eqs. (4) and (5) or (8) and (9) (or other possible filtering equations), starting from forecasting results xx ti\ i — 1 ) r2 ti\ i — 1 ) and by exploiting the measurement    y (t,),    compute    the    filtering    results
xx ti\i) r2 ti\i).
(2) By means of Eq. (24), compute Ti such that xx t\ i) is a reliable forecasting in the interval (ti, ti + Ti], on the basis of corresponding values of r2(t|i).
(3) By means of Eqs. (14)-(17), compute the extremal solutions { xi* Ai*)} for the ith optimization sub-problem; the number of extremals ranges from 1 to 3.
(4) By direct computation of the cost function J xi* Ai*) and subsequent comparison, find the optimal solution xi0 Ai0) of the ith optimization sub-problem, which certainly exists.
(5) Utilize the optimal solution xi0 in the subinterval [ti, ti+1) with ti+1 = ti + Ai0, provided that no emergency occurs. In the mean time, by means of Eqs. (6) and (7), compute the forecasting results xx ti+1\i) r2 ti+1\i).
(6) Go back to step 1 with i fi i +1.
(7) During step 5, successive measurements y(tij) are processed on-line, for tij 2[ti, ti + 1), in order to compute a current filtering x(tiJ\j) (more reliable than the forecasting x(tiJif a timeXij exists such that x(Xij\ij) differs from x0 more than a fixed threshold, actuate the emergency procedure, by putting ti+1 = xtij.
(8) If the emergency procedure is activated, go back to step 2 with x(t,+1\i + 1)= x(tij\ij), r2(t,+1\i + 1) = r2(tij\ij) and with i fi i +1.
4. Numerical results and performance evaluation
To obtain the following numerical results, the proposed method has been applied using the approximate Kalman-Bucy filter described by Eqs. (8)-(10). We adopt this filter because it provides a very good approximation ofthe exact filter (Eqs. (4) and (5)), while being less complex, as shown in our previous work [12].
We used the topology of Fig. 2 to apply the proposed method for simulated traffic. The traffic was generated between the various nodes of the network according to the birth-death model (Eqs. (1) and (2)). Variance of the noise added to the traffic was set at r2n = 0.3. We monitor the traffic on the link 6-13 in the network. The traffic on this link is an aggregate of the various sessions between different source-destination pairs in the network. We split the experiments in two sets, characterized by the given values for the model parameters k, 1. The various parameters for the eight performed experiments are given in the Table 1.
For both the sets of experiments, our method has been applied either without the ''emergency procedure'' varying
the value of parameters a, # (Experiments 1-4, 6 and 7) or with the ''emergency procedure'' for m1 = m2 = 2 (Experiments 5 and 8). The results are shown in Figs. 3-10.
We also used real traffic traces to verify the performance of the proposed bandwidth reservation method. The two

Fig. 2. Network topology.
Table 1
Simulated traffic parameters
Set    N	k	1	a		m1, m2	Experiment number	
1       30	0.025	0.05	0.3	0.3	-	1	
			0.3	0.7	-	2	
			0.7	0.3	-	3	
			0.7	0.7	-	4	
			0.3	0.3	2, 2	5	
2       50	0.04	0.09	0.3	0.3	-	6	
			0.7	0.7	-	7	
			0.3	0.3	2, 2	8	
Fig. 4. Experiment 2. Simulated data: traffic load and bandwidth reservation.

50    100    150   200   250   300   350   400   450   500
Time (min)
Fig. 5. Experiment 3. Simulated data: traffic load and bandwidth reservation.

Fig. 3. Experiment 1. Simulated data: traffic load and bandwidth reservation.

Fig. 6. Experiment 4. Simulated data: traffic load and bandwidth reservation.

Fig. 7. Experiment 5. Simulated data: traffic load and bandwidth reservation.

Fig. 10. Experiment 8. Simulated data: traffic load and bandwidth reservation.

Fig. 8. Experiment 6. Simulated data: traffic load and bandwidth reservation.

Fig. 9. Experiment 7. Simulated data: traffic load and bandwidth reservation.
sets of real traffic data were obtained from Abilene nodes in Kansas City and Houston on August 15, 2004. We have estimated N according to the standard estimation procedure for the maximum admissible value of a random variable [15]. The values of k and i were derived observing that the average inter-arrival time is N±i and the average inter-departure time is N^f. Parameters k and i have been estimated by evaluating the above times on the available historical data. The nature and the characteristics of the experiments and the results are similar to those performed and obtained with simulated data. Also for real data, we have applied the ''emergency procedure'' in two cases (Experiments 11 and 14). The parameters for the two sets of data are shown in Table 2. The time to compute the solution of the generic optimal reservation sub-problem, is small enough (less than 1 s) to allow the on-line use of the method. The obtained results are shown in Figs. 11-16.
To evaluate the performance of our method by the obtained results, the following indices have been taken into consideration:
• n/nT: the number n of bandwidth variations, corresponding to the number of optimization sub-problems solved on-line, as a fraction of the total number nT of considerate samples;
• E: the total square error of the optimal solution compared with the corresponding estimated number of active connections
Table 2
Experiments with real traffic traces
Set	N	k	1	a	#	m1, m2	Experiment number	
3	50	0.04	0.06	0.3	0.3	-	9	
				0.7	0.7	-	10	
				0.3	0.3	2, 2	11	
4	50	0.02	0.09	0.3	0.3	-	12	
				0.7	0.7	-	13	
				0.3	0.3	2, 2	14	

Fig. 11. Experiment 9. Real data: taflk load and bandwidth reservation.       Fig. 14. Experiment 12. Real data: traffic load and bandwidth reservation.

Fig. 12. Experiment 10. Real data: traffic load and bandwidth reservation.       Fig. 15. Experiment 13. Real data: traffic load and bandwidth reservation.

Fig. 13. Experiment 11. Real data: traffic load and bandwidth reservation.       Fig. 16. Experiment 14. Real data: traffic load and bandwidth reservation.

Fig. 14. Experiment 12. Real data: traffic load and bandwidth reservation.

Fig. 15. Experiment 13. Real data: traffic load and bandwidth reservation.

Fig. 16. Experiment 14. Real data: traffic load and bandwidth reservation.
E = £ (x(t,|i)-x0)
• a0: the mean duration of subintervals with constant bandwidth
1   n
a0 = Ay a00
n        '
• n: the number of ''emergency procedures'' performed during the experiment, in case this procedure is allowed.
The summary of the results of the experiments from the previous Tables 1 and 2 are shown in Table 3.
It is possible to observe the following properties of the system when the bandwidth is managed using our proposed method for both simulated and real data: profile but has a phase lag which is more evident in the case of variable traffic. To perform the comparison, we define a new metrics similar to E defined earlier. The new metric is epeak (emean) which represents the total square error of the peak (mean) reservation compared with the corresponding measured number of active connections. The results of the experiments are shown in Table 4 and in Figs. 17-20.
As can be seen from the Table 4, the performance of the proposed method is better both for the simulated and the real traffic. The value of the error metric E is higher for both the peak and mean based reservation schemes. The comparison was performed while keeping the number of renegotiations equal for all the three methods. This result is expected due to the inherent phase lag in the reservation achieved by the peak and mean schemes, as can be seen in Figs. 17-20.
(1) increasing k and i with all the other parameters kept fixed, the renegotiation cost increases (— increases and a0 decreases) and the fitting cost decreases (e decreases);
(2) increasing a, the renegotiation cost increases (nT increases and a0 decreases) and the fitting cost decreases (E decreases);
(3) increasing # the renegotiation cost increases (nT increases and a0 decreases) and the fitting cost decreases (E decreases);
(4) using the ''emergency procedure'', the renegotiation cost increases increases and a0 decreases) and the fitting cost decreases (e decreases).
To compare the performance of the proposed method with other widely used bandwidth reservation schemes, we have also implemented the peak and the mean dynamic bandwidth allocators for the same traffic profiles. The dynamic peak (mean) bandwidth reservation is achieved by measuring the peak (mean) of the traffic profile for a specific interval of time and then by reserving these resources in the next interval. In other words, the peak (mean) reservation does not correspond to the actual traffic
5. Conclusions
This paper presents a new method for the optimal dynamic bandwidth reservation for the LSPs in MPLS networks. The method includes the on-line processing of noisy measurements of the LSP traffic load in order to get filtering and forecasting of the same load. On the basis of this information, a sequence of optimization problems is solved on-line to find the best value of bandwidth reservation and the time duration in which this constant value holds. The minimized cost function in each step is a convex combination of the quadratic difference between the constant reserved bandwidth and the estimated traffic profile over
Table 4
Results of Comparison
Experiment number	Figure number	nE	Epeak	Emean	
15(5)	17	22	662	2667	1721	
16(8)	18	41	768	2434	2058	
17(11)	19	27	706	1728	906	
18 (14)	20	14	318	723	362	
2
Table 3
Results of experiments
Experiment number	Figure number	n/nT	E	A0	n	
1	3	22/500 = 0.044	2949	21	None	
2	4	46/500 = 0.092	1759	10.54	None	
3	5	32/500 = 0.064	1355	14.43	None	
4	6	52/500 = 0.104	1592	9.26	None	
5	7	53/500 = 0.106	662	18.49	41	
6	8	41/500 = 0.082	1737	11.63	None	
7	9	98/500 = 0.196	1083	4.9	None	
8	10	78/500 = 0.156	768	11.42	54	
9	11	27/500 = 0.108	1544	9.8	None	
10	12	64/500 = 0.256	1388	4.2	None	
11	13	54/500 = 0.216	706.3	9.7	37	
12	14	14/500 = 0.056	527.4	18.7	None	
13	15	27/500 = 0.108	290.9	18.7	None	
14	16	19/500 = 0.076	318.5	17.1	7	

Fig. 17. Experiment 15. Comparison with peak and mean based reservation schemes.

Fig. 18. Experiment 16. Comparison with peak and mean based reservation schemes.

Fig. 19. Experiment 17. Comparison with peak and mean based reservation schemes.

Fig. 20. Experiment 18. Comparison with peak and mean based reservation schemes.
a suitable time interval and the duration of this interval. The analytical solution of the optimal problem provides up to three possible candidates (extremals) at each decision instant. The global optimum can then be identified among these extremals by a direct on-line cost comparison. Thus, this method provides the optimal solution with a low computational effort. The ''emergency procedure'' of re-estimation and optimization is used when the difference between the reserved bandwidth and the estimated traffic is greater than a given threshold. This ''emergency procedure'' is employed to take into account the sudden and unpredictable variations in the stochastic properties of the traffic.
The proposed method has been widely tested and validated, both with simulated and real data. The impact of each of the procedure parameters (a, #, m1, m2) on the quality of the results has been analyzed in order to give useful indications to the network operator about the parameter selection. The proposed method has been shown to satisfy the needs for quality of service and cost reduction that are at the base of the problem formulation. In particular, it has been verified that optimal level of fitting between the traffic and the reserved bandwidth can be obtained both for simulated and real data, while reducing the renegotiation cost drastically (n << nT). In addition, the solution of the optimal reservation problem requires a short computational time allowing the on-line use of the method. This characteristic is achieved through the analytical determination of the closed form solution of the possible optimal candidates, avoiding the use of numerical methods that have a slow convergence. Finally, the validity of our method has been verified through a comparison with other commonly adopted methods of bandwidth reservation, such as peak and mean. It has been shown that for the same number of bandwidth renegotiations, the quadratic total error between the assigned bandwidth and the measured traffic is notably lower with our method, both for simulated and real data. The reason of the superiority of the proposed method compared
with the traditional ones is related to two innovative and relevant points. First, the bandwidth reservation is performed based on the prediction of the future traffic, while the traditional methods use only the past information for the traffic. Second, the bandwidth reservation in each future subinterval is selected using an optimal procedure taking into account both the cost of renegotiation and the cost of bandwidth over- or under-dimensioning.
References
[1] S. Ohta, K. Sato, Dynamic bandwidth control of the virtual path in an asynchronous transfer mode network, IEEE Transactions on Communications 40 (7) (1992) 1239-1247.
[2] C. Bruni, P.D. Andrea, U. Mocci, C. Scoglio, Optimal capacity management of virtual paths in ATM networks, in: Proceedings of IEEE GLOBECOM'94 San Francisco, USA, 1994, pp. 207-211.
[3] A. Orda, G. Pacifici, D.E. Pendarakis, An adaptive virtual path allocation policy for broadband networks, in: Proceedings of IEEE INFOCOM'96, San Francisco, USA, 1996, pp. 329-336.
[4] H. Levi, T. Mendelson, G. Goren, Dynamic allocation of resources to virtual path agents, IEEE/ACM Transactions on Networking 12 (4) (2004) 746-758.
[5] A. Terzis, L. Wang, J. Ogawa, L. Zhang, A two-tier resource management model for the internet, in: Proceedings of IEEE GLOBECOM'99, Rio de Janeiro, Brazil, 1999, pp. 1779-1791.
[6] T. Anjali, C. Scoglio, G. Uhl, A new scheme for traffic estimation and resource allocation for bandwidth brokers, Computer Networks 41 (6) (2003) 761-777.
[7] A. Adas, Supporting real-time VBR video using dynamic reservation based on linear prediction, in: Proceedings of IEEE INFOCOM'96, San Francisco, USA, 1996, pp. 1476-1483.
[8] S. Weber, G. de Veciana, Network design for rate adaptive media streams, in: Proceedings of IEEE INFOCOM'03, San Francisco, USA, 2003, pp. 2122-2132.
[9] B. Krithikaivasan, K. Deka, D. Medhi, Adaptive bandwidth provisioning envelope based on discrete temporal network measurements,
in: Proceedings of IEEE INFOCOM'04, Hong Kong, China, 2004,
pp. 1786-1796.
[10] <http://www.cisco.com/en/US/tech/tk436/tk428/technologies_white_ paper09186a00800a4454.shtml>, White paper: Cisco MPLS Auto-Bandwidth Allocator for MPLS Traffic Engineering, 2001.
[11] J.W. Roberts, Traffic theory and the internet, IEEE Communications Magazine 39 (1) (2001) 94-99.
[12] T. Anjali, C. Bruni, D. Iacoviello, G. Koch, C. Scoglio, Filtering and forecasting problems for aggregate traffic in internet links, Performance Evaluation Journal 58 (1) (2004) 25-42.
[13] J. Cea, M.K. Murthy, Lectures on Optimization: Theory and
Algorithms, Springer Verlag, New York, 1979. [14] D.P. Bertsekas, Nonlinear Programming, Athena Scientific, Belmont,
MA, 1999.
[15] S.L. Lauritzen, in: Extremal Families and Systems of Sufficient Statistics, Lecture Notes in Statistics, vol. 49, Springer Verlag, New
York, 1988.

T. Anjali received the (Integrated) M.Tech. degree in Electrical Engineering from the Indian Institute of Technology, Bombay, in 1998 and Ph.D. degree from Georgia Institute of Technology in May 2004. Currently, she is an Assistant Professor at the Electrical and Computer Engineering department at the Illinois Institute of Tecnology. Her research interests include design and management of MPLS and optical networks
C. Bruni was born in Rome (Italy) on March 6,1939. He received the degree in Electronic Engineering from the University of Rome ''La Sapienza'' in 1963 and the ''Libera Docenza'' in Automatic Control in 1969. He became Assistant Professor in 1966, Associate Professor in 1969 and Full Professor at the University of Ancona in 1975. Since 1977, he is a Full Professor of Optimal Control at the University of Rome ''La Sapienza''. From 1992 to 1998 he was Director of the Research Center for Biomedical System at the same University, where, since 1992, he also is Director of the Ph.D. Course in System Engineering. His research interests are in the area of modelling, identification and data analysis, optimal control and biomedical applications. In the same fields he is author or co-author of over 80 scientific papers or books.
D. Iacoviello was born in Rome, Italy, in 1968. She received the Laurea degree in Mathematics and the Ph.D. degree in Systems Science Engineering from the University of Rome ''La Sapienza'' in 1992 and
1998; from 1998 to 2001 she held a postdoctoral
position at the Department of Computer and Systems Science of the same University, where she is currently Assistant Professor. Her research interests are in 1D and 2D signal processing, estimation theory, optimal control and traffic estimation and resource allocation.
Caterina Scoglio received the Dr. Ing. degree in electronic  engineering  and  the  postgraduate degree in mathematical theory and methods for system analysis and control from the University of Rome ''La Sapienza,'' Italy, in 1987 and 1988, respectively. From 1987 to 2000, she was a Research Scientist with Fondazione Ugo Bor-doni, Rome. From 2000 to 2005, she was a Research Engineer with the Broadband and Wireless Networking Laboratory, Georgia Institute of Technology, Atlanta. Currently, she is an Associate Professor in the Electrical and Computer Engineering Department, Kansas State University, Manhattan. Her research interests include optimal design and management of next generation networks.