finalpaperjaumeabella.PDF

Distributed Algorithm for the Layout of VP-based ATM Networks

Jaume Abella, Guiomar Corral, Miquel Nicolau

La Salle Engineering, Ramon Llull University, Catalonia, EUROPE

Passeig Bonanova 8, 08022 Barcelona Tlf: +34 932 902 400, Fax: +34 932 902 416

E-mail: {jaumea,guiomar, miqueln}@salleURL.edu

Abstract

In this paper we propose a distributed algorithm for the
design of virtual networks based on a layout of virtual
paths (VP’s), on a given ATM network. We analyze the
different proposals found in the literature and propose a
possible solution based on economic models. We then
describe the algorithm and the simulation test-bed
implemented. Finally, results, conclusions and further
work are given.

1.  Introduction

The design and the configuration of real  communication
networks are becoming ever more relevant not only
because of the complexity in the emerging data-networks
but also because of the introduction of the Asynchronous
Transfer Mode (ATM) technology as well.

ATM networks are different from other  more
conventional data networks because of unique features
that allow them to support different types of services,
and to guarantee Quality of Service (QoS). For ATM
models and simulations, traditional statistics from traffic
characteristics and connections establishment patterns
are no longer valid. This makes the performance of
ATM networks tricky to measure with models and
simulations specifically in trying to measure blocking
problems and virtual paths bandwidth assignation for the
efficient utilization of existing and proposed
infrastructures.

This paper proposes a system to automatically
reconfigure virtual networks defined in an ATM
network. This system is based on a distributed algorithm
that assigns and maps the bandwidth of the necessary
VPs. This  algorithm is completely independent from
centralized management units. The reconfiguration must
be done every time it is defined, whatever the interval,
from hours to any number of days.

To obtain a feasible solution in a distributed
environment over ATM nodes, we must have the
algorithm design be scalable, the computation time be

short, the memory space be limited and network
performance be unaffected by overhead.

The remaining sections in this paper are as follows:
section 2 describes the different options that were
evaluated; section 3 focuses on the implemented
distributed algorithm; sections 4 and 5 explain
simulation environment and results. In conclusion, we
present suggestions for further work.

2.  Problem analysis

2.1  Precedents

Trying to design VP  networks can be compared to the
problem of distributing different services (i.e. VP
bandwidth) over a resources set (i.e. all network nodes
and links), where the main goals are as follows:

a)  The layout definition over the physical network,

determining the route for every VP.

b) The optimal allocation of the bandwidth of all VPs,

in order to minimize a given cost function.

c) The redundant resources reservation scheduling in

order to be node and link failure resistant.

Today, although there are a great number of related
papers, there are only a few, which tackle the problem in
its entirety, due to its complexity.

Almost all papers propose but a partial solution to the
problem, usually beginning with a certain VP topology
and then suggesting an algorithm to allocate the
bandwidth of all VPs [1], [2], [3], [4], [5], [6], [7], [8].
The main reason for this fact is that the first phase is a
NP-Complete problem [9], for which reason the design
of a global algorithm must be discarded.

All the options that suggest an integral solution deal not
only with the virtual network design but also with the
allocation of the bandwidth of all VPs [9], [10], [11].
They also analyze network robustness, scheduling
redundant VPs, which must exist to solve any failures,
[12] and [13].

According to their implementation, these algorithms can
be classified into  synchronous or  asynchronous and
centralized or distributed algorithms [14].

Synchronous algorithms update the VP network
configuration at call arrival times, and modify VP
capacity based on the new characteristics of the observed
load, but starting from an initial given VP configuration.
This is the scheme given in [15], [16] and [17]. On the
other hand, asynchronous algorithms maintain a fixed
VP configuration for a time period T upon the ending of
which a new configuration is recalculated. A load
estimator is usually needed in order to predict the next
network load. Examples of these asynchronous
algorithms are described in [5], [8], [14] and [18].

Algorithms can also be categorized as  centralized  or
distributed depending on how they are run. The former
are run in one location, usually at the manager’s site, and
require sending and receiving information from all
network nodes. Some centralized algorithms are exposed
in [9], [14], [15]. The latter are run in every network
node and information is passed along between them ([1],
[4] and [15]).

All the analyzed options have a common point: they use
the minimization of a cost function, in order to achieve
the optimal network configuration. Yet there are many
different ways to minimize this function. The main
minimizing methods are based on classical control
approach [7], lagrangian relaxation [10], [11], [13],
genetic algorithms [10], [19], convolution approach [3],
game theory [1], economic models [1], [20], [21], [22]
and heuristic approaches [6], [7], [9], [13], [15].

Most of these approaches require a centralized
algorithm, and there are only a few that can be
distributed, as game theory and economic models.
Because of their distributed nature, the latter has been
the option we have chosen to implement our algorithm.


2.2  Economic models

The Economic Model approach is based upon the
introduction of “money“ and “pricing” concepts to
simplify and decentralize the algorithms thus converting
possible resource distribution scenarios into simple
market models. By so doing, they unify the
heterogeneous nature of the different system resources
into a unique measurable quantity, which is “price”.
They also introduce some concepts, like “clients” who
“buy resources” in relation to their “wealth” and the
established “price”, and the “suppliers” which control

the “prices” in order to achieve a balance between
“supply” and “demand” [22].

We therefore face a completely decentralized scheme
where the re is no central node which controls the
resources. Instead, there are some distributed entities that
interact with each other to achieve the same goal: i.e.
maximize the whole of the “network’s revenue” by
means of maximizing their own “revenue”. This is
achieved by using a simple unit like the “price” of the
links’ bandwidth, as is described in the next section.

3.  Algorithm description.

The solution we have implemented, based on economic
models, uses the concept of price in order to control the
resource distribution between all the network users.

Because of its distributed implementation, the algorithm
becomes a local-search method. This is due to the fact
that access to the whole of the network’s traffic
information is not accessible from any single node alone,
and yet each one has enough data to act upon in order to
find an optimum within a given time span.

The algorithm starts with the communication needs of
the network users, including the logical topology  -
source, destination, bandwidth (BW) and QoS
parameters for every VP  - and the physical topology  -
nodes and links  -. The main target is to obtain the set of
routes that covers the QoS needs for all the VPs.

In this economical approach, the resource to sell is the
physical link bandwidth. Therefore, two different entities
are created in each network node: “consumers” and
“suppliers”. The “supplier” is the owner of all the links
that start in its node and deals with the regulation of their
“prices”. The “consumer” establishes the VPs, required
by the users accessing the network using this node,
according to the existing “prices” and the physical
topology given by the Private Network-Network
Interface (PNNI) [23].

The “consumers” choose, from all the routes that
guarantee the specified QoS, the “cheapest” route for
each VP, and reports to the corresponding “suppliers”.
After that, the “suppliers” evaluate the “prices” again
using a given pricing function, and make these “prices”
known all over the network.

So, the different elements to design this system are the
consumer  agents, the  supplier  agents and the  pricing
functions.

3.1  The consumer

The consumer starts with the logical topology defined by
the network administrator and the physical network.

The logical topology is the set of VPs that the consumer
has to establish from its node to the defined destination
along the network. For each VP the corresponding BW
and the QoS requirements (maximum Cell Transfer
Delay (maxCTD), maximum Cell Delay Variation
(maxCDV), Cell Lost Rate (CLR)) are defined. Due to
the fact that this is a distributed algorithm, at the
beginning the “consumer” doesn’t have information
about all the VPs to be established, only the ones it has
to establish.

The physical topology contains the information about all
the nodes and links of the network. This information is
given to every network node by the PNNI [23], so it is
not necessary to increase the memory space. Therefore
the topology discovery phase is avoided. One
simplification applied in this implementation is the
horizontal hierarchy used, because of the complexity of
using a peer-group hierarchy.

In order to satisfy the VP’s QoS, the consumer searches
at the beginning for the  k best routes for each VP that
guarantee its QoS restrictions. Then, on every iteration,
it chooses  the most economical route, trying to
maximize a given benefit function, and sends its BW
requirements to all the nodes in the VP-path.

When the consumers get the new “prices”, they work out
again the “cost” of every VP and select the ones that
overflow a  given upper-bound. These VPs will have to
change their route to a new more economical one, but
not all of them at the same time; so we have to introduce
a certain change -route probability  Prob

change

in order to

avoid instability problems. Also, prior to the change, the
“consumer” has to report to the old route “suppliers” for
them to free the reserved BW.

3.2 The supplier

The work for the supplier is to collect all the BW
requests and update the network prices. Once it has
received all the BW requests, it has to evaluate, for every
link, the amount of reserved BW and decide the new
prices with this value, using the pricing functions given,
before making them known all over the network.

3.3 The pricing functions

The behavior of consumers, suppliers, and so the
algorithm behavior, depends on the pricing functions
used. The consumers use the benefit function in order to
decide whether a rerouting process for the VP is
necessary or not. The suppliers use the pricing function
for the establishment of the link BW prices.

In an economic model, the benefit function must lead the
consumer to decrease its benefit as it uses more
resources (figure 1a), so it could be a simple step
function or a set of steps that let it decide the resource
amount to reserve according to their price (figure 1b, 1c)
[24].

In our case, the step function is used, due to the binary
consumer behavior, so it only has to decide whether or
not it has to change the VP-path according to the price.
There is no possibility for increasing or decreasing the
VP bandwidth. This one is known and is constant.

The supplier must deter the consumers from reserving
more bandwidth than is available at each physical link.

In this way, the bandwidth price must tend to infinity as
the maximum capacity of the link is reached (figure 2a),
being it possible to replace this value with a maximum
constant that will never be acceptable by the consumers
(figure 2b, 2c).

All these options have been analyzed on a simulation
platform.

Benefit

Price

(a)

(b)

(c)

Figure 1: Consumer benefits functions

Price

(a)

(b)

maxBW

Price

maxBW

MaxPrice

(c)

Price

maxBW

MaxPrice

MinPrice

Figure 2: Supplier pricing functions

4. Simulation test-bed

In this section, the simulation environment and the
simulation test-bed used are described.

The test-bed has been implemented using OPNET, the
simulation tool that allows the user to model, simulate
and analyze communication networks, protocols and
distributed systems [25].

The first simulation environment is a network of six
switches, partially connected by bi-directional links of
155 Mbps, with a certain CTD and CDV, and with the
physical topology shown in Figure 3. The different tests
use from 100 to 500 VPs, between the different source-
destination node pairs.

The platform used for the simulations is a WinNT
Workstation with a Pentium-II and 64 Mbytes RAM.

Many statistics from different simulations have been
taken in order to study this network behavior. Link price
evolution, utilization rate and network average price are
the most important results to be analyzed.

Link price is used to detect which links are more
saturated during algorithm execution. Utilization rate
shows how efficient the algorithm is in order to correctly
map all the VPs in nearly -congested situations. Finally,
bandwidth average price of all network links gives us an
idea about the global trading evolution to a final result.

Node 6

Node 1

Node 5

Node 2

Node 4

Node 3

Figure 3: Network physical topology

5.  Results

As said before, the algorithm has been simulated using a
test-bed set under different conditions of VP number and
link saturation. These different conditions allow us to
evaluate not only the algorithm convergence and
efficiency but also its cost.

5.1  Algorithm convergence and efficiency

Each node uses the BW mean price for all the network
links in order to  evaluate the algorithm convergence, and
then decide the moment the whole network has arrived
to a global solution. This measurement shows us how the
local search algorithm fluctuates until it arrives to the
final solution (figure 4).

0,2

0,4

0,6

0,8

1,2

100

Iterations

Price

Figure 4: Network links mean price evolution

Looking at fig.4, it could look like that during some
periods of time there is no mean price modification and,
consequently, no evolution to the final solution. But if
we take a look to the BW utilization we can see that this
is wrong.

In fig. 5 we can see that in each iteration there is really
an improvement of the network status, thus approaching
the final solution. Also, the consumer’s behavior is

reflected as expected: first, all the consumers try to
reserve BW over the core links of the networks, in order
to get the shortest path from the source to the
destination. That makes these links prices escalate to
high values at the beginning. After that, these prices
make consumers reroute their VPs over cheaper links.

100

120

140

160

x10 Iterations

% Utilization

Figure 5: Link bandwidth reservation evolution

The convergence rate depends on the Prob

change

we have

introduced for each consumer, defined as:

VPnumber

change

Prob

where K is a constant and VPnumber is the number of
VPs each consumer has to establish.

In order to achieve a good relationship between
convergence and system stability we have seen that for
constant K, best values are near 1. When K=1 the
consumers tend to change the layout of one VP on each
iteration, avoiding oscillating algorithm behaviors
(figure 6).

0,2

0,4

0,6

0,8

1,2

1,4

101

Iterations

Price

Figure 6: Oscillation price evolution

5.2  Algorithm cost

In order to estimate an algorithm’s computation-time
cost we use the term “iteration”, which represents the
whole process for the evaluation of the new prices and
the rerouting of the VP paths. Then, using  K values near
1, the system gets a solution in no more than 100
iterations.

This is a very acceptable cost in a distributed
asynchronous environment, where there is no need to
find a solution in real-time. On the other hand, the
network VP’s reconfiguration will take place in periods
of time from an interval of few hours to some days long

The memory cost is reduced by having only the local
information about the VPs that it has to establish in each
node. Additionally, each node uses the information
given by PNNI about the physical topology in order to
reduce the use of memory.

6.  Conclusions and further work

A distributed algorithm for the layout of VP-based ATM
Networks has been introduced in this paper. After a
complete analysis over previous papers we have chosen
an implementation based on economic models. So the
final algorithm is compliant with short computation
time, limited memory space and minimum network
overhead requirements. The algorithm needs less than
100 iterations in order to find a solution given a well-
balanced load.

Several questions regarding this work still exist. A
detailed analysis of the algorithm depending on
parameter  K and other parameters that could influence
its convergence remains an issue for further work.
According to the different VP configurations for every
period of time, a distributed algorithm to migrate from
one layout to the other must be designed. Finally, in case
the algorithm doesn’t find a solution in a reasonable
number of iterations, other actions should be undertaken,
like, for example, the selective discarding of services
determined by the assigned priorities.

References

[1] N.Aneroussis, A.Lazar, "An architecture for controling

Service Demand in ATM Networks based on Pricing
Agents". Department of Electrical Engineering and Center
for Telecomunications Research. Technical Report.

[2] R.Fabregat-Gesa, J.Sole-Pareta, J.L.Marzo-Lázaro y

J.Domingo-Pascual. “Adaptive Routing Based on Real-
Time Calculations using the Convolution Approach.”
Universitat de Girona. Escola Politècnica Superior. Girona,
Catalunya.

[3] R.Fabregat-Gesa, J.L.Marzo-Lázaro, J.Domingo-Pascual,

“Bandwidth Allocation Based on Real Time Calculatio ns
Using the Convolution Approach ”, GLOBECOM’94,
pp.788-793.

[4] A.Lazar, A.Orda, D. Pendarakis, “Virtual Path Allocation

in Multiuser Networks: A Noncooperative Approach ”,
Proceeding of the 1995 IEEE INFOCOM, Boston MA,
1995.

[5] D.Mitra, J.Morrison, “ATM Network Design and

Optimization: A Multirate Loss Network Framework ”,
IEEE Transactions on Networking, Vol.4, Nº4, Aug.1996

[6] A.Orda, G.Pacifici, D.Pendarakis, “An Adaptive Virtual

Path Allocation Policy for Broadband Networks”,
Department of Electrical Eng. Technion, Haifa 32000
Israel., IBM Research Division. T.J. Watson Research
Center. Yorktown Heights, New York 10598. USA.

[7] A.Pistillides, J.Lambert, D.Tipper, "Dynamic Bandwidth

Allocation in Broadband_ISDN using a Multilevel Optimal
Control Approach". IEEE Int.Conf. on Systems Eng.,
Kobe, Japan, Sept.1992.

[8] J.Fingerhut, S.Suri, J.Turner. “Designing Minimum Cost

Nonblocking Communication Networks”, Department of
Computer Science. Washington University. St. Louis,
USA.

[9] S.Ahn, R. Tsang, S. Tong and D.Du, “ Virtual Path Layout

Design on ATM Networks”, Proc. INFOCOM ’94, March
1994.

[10] D.Medhi, D.Tipper ”Some Approaches to Solving a

Multi-Hour Broadband Network Capacity Design Problem
with Single-Path Routing”. Department of Computer
Networking. University of Missouri-Kansas City,
Department of Information Science and
Telecommunications. University of Pittsburgh.

[11] D.Medhi, C.Lu. “Dimensioning and Computational

Results for Wide-Area Broadband Networks with Two-
level Dynamic Routing ”. IEICE Transactions on
Communications.

[12] K.Murakami, H.Kim., “Virtual Path Routing for

Survivable ATM Networks”. IEEE/ACM Transactions on
Networking. Vol.4, nº.1, Feb. 1996.

[13] C. Wu, S.Lee “A Generic Optimization Model for

Survivable VP Planning in ATM Networks”. Department of
Electrical Engineering, National Chung Cheng University,
Chiayi, Taiwan.

[14] N.Aneroussis, A. Lazar, “Virtual Path Control for ATM

Networks with Call level Quality of Service Guarantees”,
Proceedings of the 1996 INFOCOM, San Francisco, CA,
March 1996.

[15] O.Gerstel, A.Segall, “Dynamic maintenance of the

Virtual Path Layout”. LPCR Technical Report 9415,
Technion, January 1995.

[16] K.Sato, S.Ohta, I.Tokizawa, “Broadband ATM Networks

Architecture based on Virtual paths”, IEEE Transactions
on Communications, vol.38, pp-1212-1222, Aug.1990.

[17] S. Ohta, K. Sato “Dynamic Bandwidth Control of the

Virtual Path in an Asynchronous Transfer Mode Network”,
IEEE Transactions on Communications, Vol.40, nº7,
Jul.1992.

[18] J.Fingerhut, R.Jackson, S.Suri, J.Turner. ”Design of

Nonblocking ATM Networks”, Department of Computer
Science. Washington University. St. Louis, WUCS-
9603,1/96. USA.

[19] K.Tang, K.Ko, K.Man, S.Kwong, “Topology Design and

Bandwidth Allocation of Embedded ATM Networks Using
Genetic Algorithm”, IEEE Communications Letters, Vol.2,
nº.6, pg-171-173, Jun.1998.

[20] N.Anerousis, A.Lazar, “A Framework for Pricing Virtual

Circuit and Virtual Path Services in ATM Networks”.
AT&T Research, 600 Mountain Avenue, Murray Hill, NJ
07974-0636.

[21] J.Murphy, L.Murphy, “Bandwidth Allocation by Pricing

in ATM Networks”. Proc. of IFIP Broadband
Communications’94. Paris, France, March 1994.

[22] D.Ferguson, C.Nikolaou, J.Sairamesh, Y.Yemini,

“Economic Models for Allocating Resources in Computer
Systems”. IBM T.J. Watson Research Center, Hawthorne,
N.Y 10532.

[23] The ATM Forum, “Private Network -Network Interface,

Specification Version 1.0”, March 1996.

[24] L.Murphy, J.Murphy, “Feedback and Pricing in ATM

Networks”. Department of Computer Science and
Engineering, Auburn University, AL 36849, USA.

[25] MIL 3, “OPNET Modeler User Manual”, Release 4.0,

1998, http://www.mil3.com.