вход по аккаунту


How to Place Connectionless Servers in ATM Networks - FH Aachen

код для вставки
How to Place Connectionless Servers
in ATM Networks
Marko Schuba, Peter Reichl,
Department of Computer Science 4, Aachen University of Technology
52056 Aachen, Germany
Using connectionless servers (CLS) is one way to provide connectionless services in ATM
networks. Number and location of these CLSs must be carefully selected because of their
significant influence on the performance of the connectionless data traffic. In this paper a
method is presented that is able to propose a minimum CLS set necessary to achieve a certain performance in arbitrary ATM networks. For that purpose ATM networks are modeled
as graphs and the performance of CLS sets is evaluated by mean delay computation. In
small networks the optimal CLS set is determined by enumeration of all possible sets. As
this approach is not feasible for large networks, Simulated Annealing is used to approximate the optimal solution. The suitability of Simulated Annealing is examined in Monte
Carlo simulations on random graphs.
1 Introduction
Most of today’s local area networks (Ethernet, Token Ring, FDDI etc.) are connectionless. In
the near future these existing LANs will be interconnected by high capacity wide-area networks based on the Asynchronous Transfer Mode (ATM) [1]. Because ATM is connection-oriented, interoperability must be provided through the use of connectionless services in ATM [2].
Besides such services are desirable as some applications prefer connectionless communication.
Several approaches have been proposed to realize connectionless service in ATM [3]. One of
them is the use of connectionless servers (CLS). CLSs (interconnected by ATM virtual circuits) form a connectionless overlay network on top of ATM (section 2). This paper presents an
approach that improves the performance of this overlay network via selection of suitable CLS
sets. To this end a model for ATM networks and a method for the evaluation of CLS configurations are developed (section 3). Number and location of CLSs needed for an acceptable mean
delay of cells are determined by different optimization methods that are presented in section 4.
These methods are tested and compared on graphs produced by a random graph generator
developed in section 5. From the results (section 6) appropriate CLS set sizes can be derived.
Additionally Simulated Annealing is suggested as strategy for finding a near-optimal location
of these CLSs in large networks. The paper ends with a few concluding remarks (section 7).
2 Connectionless Service in ATM Networks
The ITU proposes two ways to provide connectionless service in ATM networks: the indirect
and the direct approach [4][5].
The indirect approach uses a full mesh of virtual circuits (VC) between the interworking units
(IWU) of an ATM network (Figure 1). These IWUs form the interface between the ATM network and connectionless local area networks. A datagram arriving from a local area network at
an IWU is transported to the IWU connected to the destination LAN. This method does not
require any modifications inside the ATM network because all work is done in the IWUs. The
virtual channel between a pair of IWUs can be either (semi-)permanent (PVC), i.e. the connection exists all the time, or switched (SVC), i.e. the connection is built on demand. Both techniques have their disadvantages. The number of PVCs and the bandwidth allocation involved
may be very high in the case of large networks. PVCs may also be underutilized in times of
low traffic. Using SVCs the delay in sending a datagram is increased by the time necessary for
establishing the connection. In both cases there exist links which are heavily used (e.g. links
from an IWU to the next ATM switch), whereas other links may never be used to transport connectionless data. Therefore increasing connectionless data traffic may lead to congestion.
Figure 1. The indirect approach and the VCs between IWUs
The direct approach can be used to reduce the number of PVCs. Connectionless data traffic is
directly supported by the ATM network via connectionless servers. A CLS is an ATM switch
with an extension to maintain PVCs (SVCs) and to make routing decisions depending on the
information a cell contains. This extension can be either realized outside the ATM switch
(stand-alone) or integrated into the switch [3].
Every IWU is directly connected to a CLS. The CLSs among themselves are interconnected
e.g. by a full mesh or any other (arbitrary) topology of VCs. Together these connections form a
virtual connectionless network on top of ATM. Datagrams (fragmented in cells) are routed
from a source IWU via a series of CLSs to the destination IWU. The main advantage of this
approach is the low number of VCs needed. In the indirect approach two cells which travel
from one IWU to two different destination IWUs would need two separate VCs even if the
cells use the same links most of the time. Because the direct approach divides such an IWUIWU path in several “parts” (IWU-CLS, CLS-CLS, ..., CLS-IWU), cells which use identical
paths/links can be multiplexed on a common VC. This results in a better utilization of the allocated resources. Figure 2 shows a network with CLSs.
Figure 2. The direct approach and a virtual overlay network
As extending ATM switches to CLSs implies a trade-off between costs and performance gains,
the following important parameters have to be determined when using the direct approach [6]:
number of ATM switches which should be extended to CLSs,
location of these CLSs,
connectivity of the CLSs,
bandwidth allocation of VCs in the overlay network.
Up to now there have been some proposals (e.g. [3]) which unfortunately do not go into performance details. In this paper the first two parameters will be optimized with regard to mean cell
delay of connectionless traffic.
3 Location Problem for CLSs
An ATM Network can be modeled as a graph G = (V, E), where the nodes V represent ATM
switches and the edges E represent ATM links [7]. The following assumptions are made for the
network model:
• In a given network the distance d: V × V → R0+ between two nodes is defined in the following way:
For every node v: d(v, v) = 0.
If an edge exists between two nodes v, w в€€ V, d(v, w) is given by the Euclidean distance
between v and w.
The distance d(v, w) between two nodes v, w в€€ V, which are not directly connected by an
edge, is defined as the sum of distances of the edges forming the shortest path between v
and w.
• Connectionless traffic can enter and leave the network at every node, i.e. every node can be
seen as directly connected to an IWU. This implies that IWUs themselves are not modeled.
The probability P(v, w) that an arriving datagram enters the network at node v and leaves at
node w is identical в€Ђ v, w в€€ V (uniform distribution).
• The delay of a cell passing a PVC established between two nodes v, w ∈ V is proportional to
the distance d(v, w)1.
• Every node can be viewed as potential CLS.
• If a set C ⊆ V is chosen to be a set of CLSs, these CLSs are interconnected by a full mesh of
PVCs. PVCs are also established between every node v ∉ C and its nearest connectionless
server CLS(v). Together these PVCs form the overlay connectionless network.
• A cell entering a network at node v with destination w (v, w ∈ V, v ≠w) is routed on a path
consisting of three PVCs: (v, CLS(v)), (CLS(v), CLS(w)) and (CLS(w), w).
Figure 3 gives an example for establishing PVCs and routing cells after a selection of three
1. Note that in this simple model the delay therefore is assumed to be load independent.
Figure 3. (a) ATM network model, (b) selection of three CLSs,
(c) the virtual overlay network (PVCs), (d) real route of a cell from v to w
Now suppose C and G are given. For an efficient computation2 of the mean cell delay D(C)
some more variables are necessary:
CLS(v) := arg min( d (v, w)), в€Ђ v в€€ V, is the CLS with minimal distance to v,
w в€€C
delayCLS(v, w) := d(v, CLS(v)) + d(CLS(v), CLS(w)) + d(CLS(w)), в€Ђ v, w в€€ V, v в‰ w,
is the delay of a cell routed from v to w in the overlay network,
dom(v) := |{w в€€ V | CLS(w) = v}|, в€Ђ v в€€ C,
is the number of nodes w for which v is the nearest CLS,
n := |V|,
is the number of nodes in G and
m := |C|,
is the number of CLS to be selected.
D(C) can be computed using the following formula (converted for computation):
D(C) :=
nв‹…( n в€’1)
∑ delay
(v, w )
v , w в€€V , v в‰ w
∑ [d (v, CLS(v)) + d (CLS(v), CLS(w)) + d (CLS(w), w)]
nв‹…( n в€’1)
nв‹…( n в€’1)
⋅ (n − 1) ⋅ ∑ d (v, CLS(v)) + ∑ d (CLS(v), CLS( w )) + (n − 1) ⋅ ∑ d ( w, CLS( w ))
v , w в€€V , v в‰ w
w в€€V
v в€€V
nв‹…( n в€’1)
⋅ 2 ⋅ (n − 1) ⋅ ∑ d (v, CLS(v)) + ∑ [dom(v) ⋅ dom( w ) ⋅ d (v, w )]
v в€€V
v , w в€€C
v , w в€€V , v в‰ w
The problem is to find a set C of CLSs, |C| = m, that optimizes D(C) for a given graph G (CLS
Location Problem). If the value of m is fix, C obviously satisfies the following condition:
2. Efficiency is important, because D(C) has to be computed for every CLS set examined in the optimization
methods of chapter 4 (e.g. there are about 200.000 possible CLS sets of size 10 in a graph of size 20).
C = arg min  2 ⋅ (n − 1) ⋅ ∑ d (v, CLS(v)) + ∑ [dom(v) ⋅ dom( w ) ⋅ d (v, w )]
W вЉ† V , W = mпЈ­
v в€€V
v , w в€€W
If the number of CLSs is not limited (m arbitrary), obviously C = V is optimal because every
datagram is routed on the shortest path to its destination. Because CLS extension of all ATM
switches leads to high costs, this trivial solution is not desirable. Therefore optimization methods are needed that compute minimal CLS sets of a given size m and w.r.t. a required delay
4 Optimization Methods
A first (naive) approach to find an optimal set C of size m is to test every set of that size and to
compare the results (Enumeration). For small network models this method may be acceptable.
With increasing network size Enumeration soon reaches its limit, because the number of possible solutions grows exponentially (and the computation time needed would be too long even
for strategic decisions like CLS placement). Nevertheless this approach can be used to verify
the quality of other algorithms in small networks.
A simple heuristic for the CLS Location Problem in large networks can be developed by examining the case m = 1. If only one CLS has to be selected, it is optimal to choose a node v1 with
minimum mean delay to all other nodes. To extend this solution to m > 1 it can be repeated, i.e.
the next node v2 to become CLS is selected from the remaining n-1 nodes by comparing the
mean delay D({v1, v2}) for all possible v2. This heuristic will be called “Optimal Extension
Heuristic” in the rest of the paper.
Simulated Annealing3 (SA) is a simple heuristic which has been
designed to find solutions close to the optimum within a reasonable computing time [8][9].
Like many other local search heuristics SA chooses an initial solution and tries to improve it by
comparing it to a neighbor solution. If a better solution is found it is used as new initial solution, and the procedure is repeated. Most local search algorithms have the disadvantage that
they may get trapped in a local optimum, i.e. the values of all neighbor solutions are worse, but
the global optimum is not reached. To be able to leave such a local optimum SA sometimes
accepts a worse solution which may lead to the global optimum.
Simulated Annealing is used to improve the solution found by the Optimal Extension Heuristic. This is even sensible if the solution is already quite good, because SA is a simple heuristic
and might find a better solution very fast. Note that solutions of SA never can be worse than
solutions of the Optimal Extension Heuristic if these are taken as initial solutions.
5 Network Models
To become independent from specific network topologies, the methods of section 4 are tested
on graphs produced by a random graph generator. The generator used is an extension of a random graph generator proposed by Waxman [10]. Waxman distributes n nodes randomly over a
3. The idea of SA has been adopted from physical annealing. To find a low energy state when a melted substance
is frozen, the temperature is lowered slowly (especially near the freezing point). A fast freezing would result in
a metastable, locally optimal structure.
rectangular (integer) coordinate grid. For each pair of nodes the Euclidean distance d is computed. Two nodes v and w are connected by an edge with probability
P(v, w ) = ОІ в‹… exp
в€’ d (v, w )
where L is the maximum possible distance between two nodes, 0 < α ≤ 1 and 0 < β ≤ 1. Compared to real networks (clusters with a dense mesh of connections and few long connections
between these clusters) Waxman’s generator either produces too much long edges or too few
short edges. It also does not guarantee that the resulting graph is connected. Figure 4 illustrates
the probability distribution P(v, w) and gives an example of a typical graph generated by Waxman’s formula. The parameter values were derived from several tests.
Figure 4. Graph produced by Waxman’s generator (β = 0.9, α = 0.1).
To improve the generator, the edge probability is set to
пЈ± (1 в€’ y)
1 − x ⋅ d (v, w ) L , if 0 ≤ d (v, w) L < x
P(v, w) = пЈІ
в€’ d (v, w )
пЈґОІ в‹… exp
, if x ≤ d (v, w ) L ≤ 1
where 0 < x ≤ 1 and 0 < y ≤ 1. So if the value of the normalized distance d(v, w)/L lies between
0 and x, the probability corresponds to a straight line determined by x and y. An increasing
value of y increases the number of short edges whereas x defines up to which length edges are
“short”. Wide area connections are computed with Waxman’s formula. Nevertheless a resulting
graph may still not be connected. To connect all components of the graph the following method
is used:
1. Choose two components randomly.
Select a random number r of connections to be added4 (1 ≤ r ≤ R). R depends on the
size of the smaller component.
Connect the two components with the r shortest possible edges.
2. If there is more than one component left, go to 1.
4. If there would be only one new edge, the resulting graph would form a tree of connected components.
Figure 5 shows the probability distribution and a graph produced by the revised method.
Figure 5. Graph generated by the extension of Waxman’s formula in
combination with interconnection (ОІ = 1, О± = 0.1, x = 0.2, y = 0.5).
6 Results
The random graph generator and the optimization methods were implemented using a tool
called LEDA, a collection of efficient data types and algorithms for graphs [11]. Figure 6
shows an example graph of size 20 and the proposed CLS sets of size 8 and 10.
Optimal Extension Heuristic
Simulated Annealing
8 CLSs
10 CLSs
Figure 6. Example random graph with the solutions (8 and 10 CLSs) found by different methods
In both cases Simulated Annealing extends the non-optimal solution of the Optimal Extension
Heuristic to the optimum found by Enumeration.
To evaluate the quality of CLS sets of size m a measure is needed. As stated earlier, every cell
is routed on the shortest possible path to its destination, if m = n CLSs are used. I.e. the mean
delay of a CLS set of size n delivers a lower delay bound for all other CLS sets of that graph.
So each CLS set of size m can be evaluated by a factor F(m), which means that the (lower
bound) mean delay D(V) increases by factor F(m), if m instead of n CLSs are used.
Using this evaluation measure a general comparison of the methods was performed in Monte
Carlo simulations on random graphs. In each simulation run a CLS set, its mean delay and
F(m) were computed for 1 ≤ m ≤ n.
Figure 7 shows the simulation results of 30 simulation runs (Enumeration, n = 20) together
with 95% confidence intervals.
Figure 7. Simulation results Enumeration (20 nodes)
Even if only one CLS is used the mean delay of cells is less than 1.4 times the delay of the
lower bound (20 CLSs used). The value decreases very fast with increasing CLS set size.
Using five nodes the mean delay is only about 10% larger than the lower bound. If these results
are compared to the costs, e.g. installing costs or costs associated with the number of PVCs
needed (Figure 8), it becomes clear that the number of CLSs used must be restricted. So using
five CLSs in a network of 20 nodes seems to be reasonable.
number of PVCs
Figure 8. Number of PVCs needed in a network of size 20
difference to F(m)
The results of Simulated Annealing and Optimum Extension Heuristic are shown separately
(Figure 9), because they are both very close to the optimum.
Figure 9. Simulation results of Simulated Annealing and Optimal Extension Heuristic
compared to Enumeration
It can be seen that the results of the Optimal Extension Heuristic are very good and can be even
improved by Simulated Annealing. For SA the difference to F(m) (computed by Enumeration)
is nearly always less than 0.002.
Because SA nearly reached the optimum (Enumeration) in small networks, one can assume
that it will yield reasonable results in large networks, too. Figure 10 shows the results of 30
simulation runs with graphs of size 100 together with 95% confidence intervals.
Figure 10. Simulation results using Simulated Annealing (100 nodes)
The curve closely resembles the results of Enumeration in Figure 7. This leads one to suppose
that these results are again close to the optimum. Thus in an ATM network with 100 switches
only about 10% of these switches need to be extended to get suitable delay values.
7 Conclusions
Provision of connectionless service functions will be an important feature of ATM networks. In
the direct approach proposed by the ITU connectionless servers will be used. This paper presented methods for an optimal placement of these CLSs. Because the exact solution is too
complex to compute for large networks, a heuristic was introduced. Monte Carlo simulations
showed that the heuristic Simulated Annealing is almost as good as the exact method. As a
result it was proposed that in small networks about a quarter, in larger networks about 10% of
all ATM switches should be extended. If these switches are selected with SA, the mean cell
delay will be suitable. Future research will focus on the interconnection of CLSs, the placement of CLSs to optimize load balance and the comparison to other approaches like the indirect one. Additionally the developed methods will be tested on problems concerning multicast
delivery of datagrams or cells, e.g. optimal placement of multicast servers.
Siu K.-Y., Jain R., “A Brief Overview of ATM: Protocol Layers, LAN Emulation, and Traffic
Management”, Computer Communication Review, vol. 25, no. 2, pp 6-20, April 95
Newman P., “ATM Local Area Networks”, IEEE Communications Magazine, vol. 32, no. 3, pp
86-98, March 1994
Vickers B. J., Suda T., “Connectionless Service for Public ATM Networks”, IEEE Communications Magazine, vol. 32, no. 8, pp 34-42, August 1994
ITU-T recommendation I.211, 1993
ITU-T recommendation I.364, 1993
Crocetti P., Fratta L., Gerla M., Marsiglia M. A., “SMDS multicast support in ATM networks”,
Computer Networks and ISDN Systems, no. 27, pp 117-132, 1994
Kadirire J., Knight G., “Comparison of Dynamic Multicast Routing Algorithms for Wide-Area
Packet Switched (Asynchronous Transfer Mode) Networks”, Proceedings of IEEE INFOCOM
1995, vol. 1, pp 212-219, 1995
Kaempke T., “Simulated Annealing: Use of a New Tool in Bin Packing”, Annals of Operations
Research, no. 16, pp 327-332, 1988
Eglese R. W., “Simulated Annealing: A tool for Operational Research”, European Journal of
Operational Research, no. 46, pp 271-281, North Holland, 1990
[10] Waxman B. M., “Routing of Multipoint Connections”, IEEE Journal on Selected Areas in Communications, vol. 6, no. 9, pp 1617-1622, December 1988
[11] Mehlhorn K., Naeher S., “LEDA: A Platform for Combinatorial and Geometric Computing”,
Communications of the ACM, vol. 38, no. 1, pp 96-102, January 1995
Без категории
Размер файла
55 Кб
Пожаловаться на содержимое документа