programming approach provides the upper and lower

OPTIMIZATION OF ATM LEASED LINE NETWORKS FROM USER'S
VIEWPOINT
Satoru Ohta, NTT Optical Network Systems Laboratories
1-1 Hikari-No-Oka, Yokosuka-shi, 239-0847, Japane-mail: satoshi@exa.onlab.ntt.co.jp
The notable feature of the ATM leased line service is the freedom of virtual path bandwidth setting. Users cantake advantage of this feature by optimizing their network to minimize the charge. However, such optimization isdifficult because of the nonlinearity caused by statistical multiplexing. To tackle this difficulty, this paper
examines the integer programming approach with piecewise linear approximation and the iterative improvement
approach. It is shown that the former is valuable in evaluating the solution accuracy of the latter. The
computational time and the solution accuracy of these approaches are evaluated through computer experiments.

1. INTRODUCTION
The Asynchronous Transfer Mode (ATM) technology
is now sufficiently matured and is being introduced in
the real world. Namely, several ATM communication
services are presently available for network users. Oneof these services is the ATM leased line service thatprovides a permanent virtual path between user sites [1,2].
For users, the essential advantage of this service isthe freedom permitted in selecting the bandwidth. A
user can select an arbitrary bandwidth as needed andpay for just that bandwidth. By contrast, a user mustselect a predefined bandwidth in Synchronous Transfer
Mode (STM) services, and usually must purchase a larger
bandwidth than optimum. To take full advantage of thisATM feature, a user has to optimize the bandwidth ofvirtual paths so as to minimize the total charge.
Some literature have treated the optimization of ATM
networks [3-5]. These studies, however, treat the problemof minimizing the network operator's investment cost
[4, 5] or maximizing the operator's revenue [3]. There
have been no detailed studies on network optimizationfrom the user's viewpoint.
This paper focuses on the optimization of the user's
network based on the ATM leased line service. The
objective function is the total charge. The offered traffic
is bursty and is multiplexed statistically on a virtualpath.
Because of the statistical multiplexing
characteristic, the problem is a difficult nonlinear nonconvex optimization problem. To tackle this problem,the paper examines two approaches. One is the integer
programming approach with piecewise linear
approximation, while the other is the iterative
improvement approach. Although neither method always
yields the strict optimum, this paper shows that the integer
programming approach provides the upper and lower

bounds for the exact minimum charge, and the solution
accuracy is evaluated through their difference. Thesebounds are also useful in assessing the accuracy of theiterative improvement approach. Finally, the paper
presents computational results to evaluate the accuracy
and computational time of each approach.
2. PROBLEM
Suppose that a user is building his/her private network
using the ATM leased line service. The user has threeor more sites, each of which is equipped with an ATM
router and an ATM switch. The service is provided by
CBR (Continuous Bit Rate) virtual paths. For thissituation, the problem is described as follows.
[Problem Definition] Which pairs of sites should beconnected by virtual paths and how large should be thebandwidth of each virtual path to achieve acceptable
service quality with the minimum charge (Fig. 1)?
User Site

User Site?

Virtual Path
?
?

?
?

User Site?

User Site
ATM Switch

ATM RouterFig. 1. Problem explanation.
We assume the following points throughout the paper.
• An arbitrary bandwidth can be assigned to a virtualpath.
• Traffic demands are statistically multiplexed on a virtualpath.
• Traffic parameters of demands are known for all pairsof user sites.
• A virtual path can be set between any pair of usersites.
• Traffic can transit the ATM routers or switches at any
user site.
• Traffic is shaped by the traffic shaper of an ATM
switch at each user site as shown in Fig. 2. Thus, nocells are lost by the UPC (Usage Parameter Control)mechanism within the operator’s network because thepeak rate is held to the specified value at the user site.
ATM Switch
SwitchBuffer

ATM Router

VP

Traffic Shaper

Fig. 2. Traffic shaping and buffering.

3. FORMULATION
For the problem identified in Section 2, the set ofuser sites is V={1,2,..., n}. Let E = {1, 2, ..., m} be theset of site pairs, between which a virtual path can be set
up. Later, the virtual path set up between source
destination pair i (i E ) is simply called “virtual pathi ”. Denote the source and the sink of virtual path i (iE) as a(i) and b(i) (a(i), b(i) V), respectively. Let theset of traffic demands be D = {1, 2, ..., l}. Also, define
the source and sink of demand p (pD) as A(p) andB(p) (A(p), B(p) V), respectively.
To formulate the problem, let us introduce decisionvariable fi, p . The value of fi, p is 1 if the demand p (pD) goes through the virtual path i (iE) and 0
otherwise. The bandwidth C i required for virtual path i
is a function of variables fi,1 ,..., fi, l . Since the charge forvirtual path i is in turn the function of Ci , it is expressed
as Zi (Ci ( fi,1 ,..., fi, l )) . Using these notations, the problem
is formulated as follows.
P: minimize

Zi (Ci ( fi,1 ,..., fi, l )),(1)

1, if s = A( p)fi, p = 1, if s = B( p),i {i | b ( i ) = s}0, otherwise
for s V , p D.

(2)

i E

subject tofi, pi {i | a ( i ) = s}Here, eq. (2) is the flow conservation equation [6].
Obviously, this is a multi-commodity least-cost flow
problem. In eq. (1), Ci and Z are nonlinear functions offi, p. Moreover, these functions are not convex becauseof the characteristic of statistical multiplexing. Reference[7] described a method for solving a multi-commodity
minimum cost flow problem with such an objectivefunction. However, this method yields only a local
minimum solution and does not guarantee that theobtained solution is close to the exact solution. Thus, itis necessary to establish a new method such that theobtained solution is assured to be close to the strict
minimum.
3.1. Equivalent Capacity
As assumed in Section 2, user traffic is statisticallymultiplexed onto virtual paths and shaped by traffic
shapers. This means that cells are queued at the buffer
of a traffic shaper. If the buffer overflows, cells may belost and thus the quality of service may degrade to an
unsatisfactory level. To avoid such quality degradation,
the virtual path bandwidth must be appropriately
determined from the traffic parameters and the qualityof service criteria using the equivalent capacity (oreffective bandwidth) concept [8-10].
Several equivalent capacity formulas have been
proposed for different mathematical models of traffic
sources. Among these formulations, this study employs
the method of Ref. [8], proposed for the two state Markov
source and the buffer overflow probability criteria. The
advantages of this formula are:
• The method is applicable to a wide range of trafficmodels [8].
• The formula is relatively simple and thus easy to betreated by the piecewise linear approach.
From the equivalent capacity formula, the bandwidthof a virtual path i is expressed using variables fi, p as
follows .
Ci = minm p fi, p +cˆ p fi, p ,
p D

p D

p fi, p

, (3)

p D

where mp is the mean rate, p is the standard deviationof the rate, and ĉ p is the equivalent capacity of the
Fluid-Flow approximation of the traffic demand p.
In eq. (3), the first argument of the minimum function
is referred to as the “Fluid-Flow” equivalent capacity,while the second argument is referred to as the“Stationary” equivalent capacity. Value ĉ p is derived
from parameters such as the peak rate, the mean burst

period, and the utilization of the source, the buffer size
and the buffer overflow probability. The constantisalso computed from the buffer overflow probability.
3.2. Charge
This study assumes a simple charge model. First,
the charge of virtual path i is assumed to be proportional
to the distance from a(i) to b(i). Additionally, the charge
consists of a part that is independent of the bandwidthand a part that is proportional to the bandwidth. The
former is zero if the virtual path is not set up. Thus, thecharge model of virtual path i, Z i , is written by the next
equation.
Zi =di (Ci + X ), if vitual path exists,0,
otherwise(4)

where C i is the bandwidth defined in eq.(3), and X is aconstant.
4.

4.1. Bounds for the Strict Optimum
To solve the problem, this study first employs theinteger programming approach with the piecewise linear
approximation. This approach is advantageous since ityields the exact solution for the approximated problem.
Moreover, since integer programming technology has
progressed greatly in recent years, it is now possible totake use high performance software [11]. The mostimportant point is that the approach provides the upperand lower bounds for the objective function value of theexact solution. Therefore, it becomes possible to knowwhether the approximated solution is sufficiently close
to the exact solution or not by comparing it to the upperand lower bounds.
Before deriving the bounds, let us introduce some
additional notations. Suppose that the nonlinear function
Zi (Ci ( fi,1 ,..., fi, l )) is approximated by a piecewise linear
function Zi * (Ci ( fi,1 ,..., fi, l )) . Let P* be the problem
generated from P by replacing Zi (Ci ( fi,1 ,..., fi, l )) with
Zi * (Ci ( fi,1 ,..., fi, l )) . Let zopt and ẑopt be the objectivefunction values of the exact solutions for P and P* .
If it is possible to select the piecewise linear function
such thatZi* (Ci ( fi,1 ,..., fi, l )),(5)

for any virtual path i and any values of fi,1 ,..., fi, l , thefollowing theorems are derived.
[Theorem 1]
If eq. (6) holds, thenzˆopt ,

(6)

(Proof) Let fi,op be the value of fi, p that yields the strict
optimum of P. The set of fi,op is a feasible solution for
P* , because P and P* have the same constraint
conditions. From eq.(5), the relation
Zi (Ci ( fi,o1 ,..., fi,ol ))i E

Zi* (Ci ( fi,o1 ,..., fi,ol ))

(7)

i E

holds, and its left hand is zopt . Meanwhile, the righthand is the objective function value of a feasible solution
for P* and not less than ẑopt . This concludes eq. (6).
[Theorem 2]
Let fi*, p be the value of fi, p that yields the strict
optimum of P* . Let z * denote the value obtained bysubstituting fi*, p for fi, p in the objective function of P.
Then, if eq.(5) holds,z*

PIECEWISE LINEAR INTEGERPROGRAMMING

Zi (Ci ( fi,1 ,..., fi, l ))zopt

zopt .

(8)(Proof) The set of fi*, p is a feasible solution for P. The
objective function value of this feasible solution is z *and is not less than the strict optimum. This proves eq.
(8).
The upper bound z* is easily computed from fi*, pobtained by solving P* . Thus, the solution accuracy isimmediately known from z * and ẑopt if P* is solved.
4.2. Formulation to Integer Programming Problem
Two nonlinear functions in eq. (3) must be addressed
for the conversion from P to P* . These functions are
the minimum function and the square root function.
To express the minimum function with linear
equations, this study employs a “parallel path” approachshown in Fig. 3(a). Suppose that there can be one of
two virtual paths between a pair of sites. The bandwidthof one virtual path VPi,0 is specified by the Fluid-Flowequivalent capacity while that of the other path VPi,1 is
specified by the Stationary equivalent capacity. Then,consider the problem of minimizing the total path chargeof the network where at most one of these two paths canbe set up between two sites. For this problem, if theobjective function is correctly minimized, the virtual pathwith less bandwidth is selected from the parallel paths.
Thus, the original configuration is completely equivalent
to the parallel path configuration. In the parallel pathconfiguration, the bandwidths do not include theminimum function any more.
The square root included in the bandwidth of VPi,1 isapproximated by lines between two adjacent points on
the curve y = x as shown in Fig. 4. In Fig. 4, thepoints are labeled as (vk , wk ) (1 k K ) and the line
between (v k – 1, wk – 1) and (v k , w k ) is labeled as lk . The
approximated piecewise linear function is not larger than
the square root function between (v 0, w 0) and (v K, w K).
Therefore, the piecewise linear approximation satisfies
eq. (5), and thus it is possible to evaluate the upper andlower bounds derived by Theorems 1 and 2.

VPi, 0 : Fluid-Flow Equivalent Capacity
VPi, 1 : Stationary Equivalent Capacity(a)VPi, 0 : Fluid-Flow Equivalent Capacity
VPi, 1 : l1
VPi, 2 : l2.
..

VPi, K : lK
VPi, k : Stationary Equivalent Capacity - Line lk(b)Fig. 3. Parallel path approach for the integer
programming formulation.

Then, from eqs. (3) and (9), the k-th path associatedwith line lk has the bandwidth C i,k defined by,(m + a ) f + b y , 1 k K (10)Ci, k =

p

k

2
p

i, p

k i, kp D

The value of 0-1 variable yi, k is 1 if VPi, k exists and0 otherwise. Then, if constraints are added to select at
most one path among these K parallel paths, and if theobjective function is successfully minimized, then thevirtual path charge is exactly the same as that of thepiecewise linear function shown in Fig. 4.
By paralleling a virtual path in this way, the bandwidthis now expressed by linear equations. The cost function
shown in eq. (4) can be also expressed by linear equations
with the addition of some integer variables. Thus, theproblem is formulated into a linear integer programming
problem, which can be solved by generic optimization
software. For the formulation, let us use variable fi, p, k
(i E, p D, 0 k K ) that takes value 1 if demandp goes through path VPi,k and value 0 otherwise. Thenthe problem is formulated as:

minimizes p, k fi, p, k +dii Ep D, 0 k K

tk yi, k
0 k K

,
(11)

subject to

w3

K

l1

y

y= x

l2

yi, k

l3

w2

fi, p, kyi, k , for ifi, p, kw1w0

i {i | a ( i ) = s}
0 k K

v0 v1

v2

1, for i

E,

(12)

y=0

v3

E, p

D, 0 k K ,(13)
1, if s = A( p)fi, p, k = –1, if s = B( p) ,i {i | b ( i ) = s}0, otherwise
0 k K

for s V , p

x

D,

(14)

where s p, k and tk are constants defined as follows.
Fig. 4. Picewise linear approximation of thesquare root function.
As shown in Fig. 4, line lk is not larger than any
other line lj (k j) in the interval [vk – 1, vk ]. This suggests
the parallel path scheme is again applied. Namely, VPi,1in Fig. 3 (a) is further divided into a set of parallelpaths, each of which has a bandwidth associated with aline lk ( 1 k K ) as shown in Fig. 3 (b). The pathassociated with line lk ( 1 k K ) is labeled as VPi, kwhile the path associated with the Fluid-Flow equivalentcapacity is labeled as VPi,0 . Let line lk be expressed as,
y = ak x + bk

(9)s p, k =

tk =

mp +

X+

ak
cˆ p ,

2
p,

1 k K
.
k=0

bk , 1 k K
.
k=0
X

(15)

(16)

5. ITERATIVE IMPROVEMENT
Although the integer programming approach has
advantages, its computation time may not be practicalfor a large size problem. For such a problem, it isnecessary to establish a fast heuristic optimization
method. As such a method, this study investigates thefollowing iterative improvement method.

6. COMPUTATIONAL RESULTS
The solution accuracy and computational time of thedescribed methods were evaluated through computer
simulation. Figure 5 shows the computational timeagainst the problem size for both methods. In the figure,the computational time is the average for five randomly
generated problems for each number of sites. A problem
was generated as follows. Each site was chosen randomly
from the cities of Japan, and the distances between sites
were those between the cities. For each pair of twosites, data bursts are generated by a two-state Markov
source. Each source generates bursts according to theparameters shown in Table 1. Because the utilization
parameter was determined randomly for each source,
the mean rate between two sites was also random. The
table shows the buffer size of a switch and the buffer
overflow probability as well. In the charge of eq. (4),the constant X was 10, while the unit of bandwidth was
Mbits/s. For the integer programming approach, thenumber of piecewise linear intervals K was 3. Figure 5
shows that the computational time is much less andincreases much slower against the problem size for theiterative improvement approach. Nevertheless, the figure
also implies that the integer programming approach isapplicable to small problems.
Next, solution accuracy was tested for 13 site
problems. With the integer programming approach, thedifferences between the upper and lower bounds were
5% to 8% of the lower bounds for 10 randomly generated
problems and K = 3. Figure 6 shows that the distributionof the relative difference between the upper bounds
obtained by the integer programming approach and thesolution obtained by the iterative improvement approach.
The figure also displays how the initial solutions of theiterative improvement approach are distributed. As
shown in the figure, the solutions are as good as thoseoffered by the integer programming approach and thus
close to the exact optimum. However, the initial solutionsof the iterative improvement approach are not as goodas the final solutions. This result suggests that theminimum spanning tree is not a very good heuristic andan improvement step is indispensable to obtain a goodsolution.

Table 1. Parameter values for the traffic sources
and the switch buffers.

Computational Time (Relative Value)(Definition)
N: the current solution network.
S: the set of virtual paths included in N.
T: the set of virtual paths not included in N.
Step 1) Make an initial solution using a minimum spanning
tree [6] based on the physical distances among sites.
Step 2) Repeat A and B until the solution shows nofurther improvement.
A. Exchange stepFor every combination of i (iS) and j (jT),
construct network Nij by deleting i from N and adding
j to N. If N ij is connected, assign traffic demands
along the shortest routes. Next, compute the virtual
path bandwidths and the network charge. Select N ij
with the minimum charge, N min. If the charge of N min
is less than that of N, replace N with Nmin .
B. Addition stepFor every j (j T), construct network N j by adding j
to N. Assign traffic demands along the shortest routes.
Next, compute the virtual path bandwidths and the
network charge. Select N j with the minimum charge,
Nmin . If the charge of N min is less than that of N,
replace N with N min.

Burst Peak Rate

10 Mbits/s

Average Burst Period

30 msec

Source Utilization

Uniform Distribution
in [0, 0.1]

Buffer Size

1 Mbits

Buffer Overflow
Probability

10

10000

-5

Integer
Programming

1000
100
10

Iterative
Improvement

1
0.1
5

10

20

Number of Sites

Fig. 5 Computational time.

50Frequency

10
Initial Solution

8(Minimum Spanning Tree)

[4]

6
4
2
1

2

3

4

5

0<

1<

2<

3<

4<

[5]
0

0

Range of Relative Difference to theUpper Bound (%)

Fig. 6 The distribution of the difference between
the approximate solution by the iterative
improvement approach and the upperbound of the exact solution.

7. CONCLUSION
This paper described the problem of optimizing theuser's network to minimize the charge for the ATM leased
line service. The problem was formulated using theequivalent capacity of Ref. [8] to construct a networkwith sufficiently good service quality. As optimizing
methods, the paper investigated the piecewise linear
integer programming approach and the iterative
improvement approach. The integer programming
approach was shown to be advantageous in the pointthat the upper and lower bounds of the exact solution
are easily derived and thus the solution accuracy iseffectively evaluated. Computation results show that theiterative improvement approach is much faster and yields
solutions that are as good as those of the integer
programming approach. Thus, the iterative improvement
approach is a practical choice for the optimization
problem of the user ATM network. Nevertheless, theinteger programming approach is still significant in
confirming the solution accuracy of the iterative
improvement approach or other heuristic approaches.
ACKNOWLEDGMENTS
The author wishes to thank Dr. Ko-ichi Sano and Dr.
Katsushi Iwashita.
REFERENCES[1] T. Aoyama, et al., “ATM VP-based broadband
networks for multimedia services,” IEEE
Communications Magazine, 31, 4, pp. 30-39, 1992.
[2] http://www.nttls.co.jp/senyo/what/whats10. html.
[3] D. Mitra et al., “ATM network design andoptimization: a multirate loss network framework,”

[6]
[7]

IEEE/ACM Trans. Networking, 4, 4, pp. 531-543,
Aug. 1996.
U. Mocci et al., “Robust design of virtual path
networks in ATM multiservice environments,” inProc. NETWORKS'96, Sydney, Australia, pp. 425430, 1996.
C.-C. Shyur et al., “ATM VP-based broadband
transport network planning,” in Proc.
NETWORKS'96, Sydney, Australia, pp. 437-441,
1996.
R. E. Tarjan, Data structures and network
algorithms, SIAM, 1983.
J. B. Yaged, “Minimum cost routing for static
network models,” Networks, 1, pp. 139-172, 1971.

[8]
application to bandwidth allocation in high-speed
networks,” IEEE J. Select. Areas Commun., SAC-9,
7, pp. 968-981, Sept. 1991.
[9] A. I. Elwalid and D. Mitra, “Effective bandwidthof general Markovian traffic sources and admission
control of high speed networks,” IEEE/ACM Trans.
Networking, 1, 3, pp. 329-343, June 1993.
[10] I. Norros, “On the use of fractional Brownian motionin the theory of connectionless networks,” IEEE J.
Select. Areas Commun., SAC-13, 6, pp. 953-962,
Aug. 1995.
[11]
Optimization software
guide, SIAM, 1993.