# How to Place Connectionless Servers in ATM Networks - FH Aachen

код для вставкиHow to Place Connectionless Servers in ATM Networks Marko Schuba, Peter Reichl schuba@i4.informatik.rwth-aachen.de, reichl@i4.informatik.rwth-aachen.de Department of Computer Science 4, Aachen University of Technology 52056 Aachen, Germany Abstract 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]. 09/1 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. IWU IWU IWU LAN B-ISDN LAN B-ISDN LAN IWU IWU IWU LAN LAN IWU IWU LAN LAN LAN 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. B-ISDN LAN B-ISDN LAN IWU IWU CLS CLS IWU LAN IWU CLS CLS IWU IWU LAN LAN IWU CLS LAN Figure 2. The direct approach and a virtual overlay network 09/2 CLS IWU LAN LAN 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]: 1. 2. 3. 4. 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 CLSs. 1. Note that in this simple model the delay therefore is assumed to be load independent. 09/3 w v (a) (b) (c) (d) 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) := = 1 nв‹…( n в€’1) в‹… в€‘ delay CLS (v, w ) v , w в€€V , v в‰ w в€‘ [d (v, CLS(v)) + d (CLS(v), CLS(w)) + d (CLS(w), w)] 1 nв‹…( n в€’1) в‹… = 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 пЈ° пЈ» = 1 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). 09/4 пЈ« пЈ¶ 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 quality. 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. 09/5 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 ) LО± 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. P(v,w) 1 0 0 d(v,w)/L 1 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 LО± пЈі 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. 09/6 Figure 5 shows the probability distribution and a graph produced by the revised method. P(v,w) 1 0 d(v,w)/L 0 1 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. 09/7 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. 1,4 F(m) 1,3 1,2 1,1 1 0,9 0 5 10 15 20 m 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 400 300 200 100 0 0 5 10 15 20 m Figure 8. Number of PVCs needed in a network of size 20 09/8 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. 0,007 0,006 0,005 0,004 0,003 0,002 0,001 0 OptExt SA 0 5 10 15 20 m 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. 1,4 1,3 F(m) 1,2 1,1 1 0,9 0 10 20 30 40 50 60 70 80 m Figure 10. Simulation results using Simulated Annealing (100 nodes) 09/9 90 100 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. References [1] 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 [2] Newman P., вЂњATM Local Area NetworksвЂќ, IEEE Communications Magazine, vol. 32, no. 3, pp 86-98, March 1994 [3] Vickers B. J., Suda T., вЂњConnectionless Service for Public ATM NetworksвЂќ, IEEE Communications Magazine, vol. 32, no. 8, pp 34-42, August 1994 [4] ITU-T recommendation I.211, 1993 [5] ITU-T recommendation I.364, 1993 [6] 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 [7] 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 [8] Kaempke T., вЂњSimulated Annealing: Use of a New Tool in Bin PackingвЂќ, Annals of Operations Research, no. 16, pp 327-332, 1988 [9] 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 09/10

1/--страниц