RUS | UKR || Master's portal of DonNTU
Voropaeva Anna

Voropaeva Anna

Faculty of Computer information technologies and automatics
Speciality: Telecommunikation network/P>

Theme of master's work:

Research and optimization of transport technologies of mobile networks of the third generation

Scientific adviser: Bessarab Vladimir

About author

Introduction

Data and near-future multimedia communications will require high-capacity transmission systems realised through optical core/backbone networks. With the introduction of fibre-optic, high-speed, large-capacity networks, the optimal topology design of optical networks subject to service restoration and survivability requirements has become a crucial issue in network planning.
The synchronous digital hierarchy (SDH) has been one of the most important innovations in communications networks. The flexibility of operation allowed by SDH equipment such as add-drop multiplexers (ADMs) and synchronous digital crossconnect (SDxC), as well as self-healing architectures, has enabled innovative topologies to be introduced. Two mainstream SDH architectures are ring and mesh topologies [1, 2]. One major advantage of mesh networks is that they achieve the lowest redundancy in transmission capacity needed for 100% restorability. However, ring architectures may be preferred in practice because they are simpler in management, operation and administration, and faster in switching (50—150 ms). In addition, ring networks can be more economical than mesh networks [3].
The objective is to find the optimal sub-set of all rings so that the traffic delivered by the underlying network is maximised subject to a number of complex constraint conditions. Evolutionary computation (EC) methods are stochastic optimisation search algorithms which derive from Darwin’s Theory of Evolution: considering a population evolving in a particular environment, only the fittest individual will be able tore produce, whereas the less fit will die out due to environmental constraints. The descendants of the original population will inherit the qualities that better fit the environment. The EC methods mimic the natural evolution procedure and tend to move populations adaptively towards the optimum; thus they are natureinspired computation methods [4].
In order to find the optimal or near-optimal solution for this challenging network topology design problem, two EC methods are employed. These are a genetic algorithm [5] method and a novel ‘smart ring algorithm’ (SRA) based on the conventional evolutionary algorithm (EA) framework [6]. Experimental results show that this novel smart ring algorithm is superior to the GA in both computational time and quality of solution. Our SRA method is particularly attractive for relatively dense networks in which the set of all potential rings can be determined in a relatively short computational time. This is a combinatorial optimisation problem in which the smart ring algorithm is developed to select an optimal subset of rings.

Previous approaches

Mathematical methods
Linear programming and mathematical programming methods relying on an accurate mathematical model of the underlying problem are well-established. It is apparent that mathematics-based techniques can only be applied to problems where constraints and objective functions are linear; they cannot be employed to solve more complicated problems involving nonlinear functions. Also, most of the reported successes are for designing small-to-medium-sized networks, which have tens of nodes and a few hundred candidate rings. In general, linear programming and mathematical programming procedures tend to only work well for problems of small size and are normally slower than heuristic algorithms [11] of the type discussed below.
Heuristics
Practical optimal network ring design is a difficultproblem characterised by the requirement to compare a large number of potential solutions satisfying multiple nonlinear constraints; it is normally regarded as a combinatorial optimisation problem. Local search heuristic methods or approximation algorithms [12] have typically been employed to solve such problems. The former term refers to methods justified purely because empirically they are found to perform ‘fairly well’. The latter term is normally reserved for algorithms that produce solutions guaranteed to be within a certain distance of the optimum.
A number of general-purpose heuristic techniques that have been proven useful in practical ring network design are now described. These techniques do not guarantee finding an optimal solution, but aim to find reasonably good solutions in a relatively short time. A heuristic method is developed by Grover et al [13] to find a minimum-cost composite design for a transport network with multiple SONET self-healing rings. Experimental results from a real-world long-haul network design involving a total of 141 self-healing rings present solutions ranging from nearly optimal capacity efficiency to nearly optimal traffic capture, depending on the relative costs of transmission capacity and costs for ring-to-ring transition interfaces. In order to design a reliable ring-based network, Luss et al [14] adopt the following heuristic approaches. They firstly generate a large set of candidate rings and assign the cost of each ring based on the nodes covered by that ring and the traffic demands. They then select a (minimum cost) subset of the overall candidate rings such that each node is included on at least one ring. Finally, they choose a few additional rings in order to achieve the required connectivity among them. Computational results for realistic-size (e.g. 500 nodes) telecommunications networks are provided. A special algorithm is generated by Wuttisittikulkij and O’Mahony for designing a ring-based all-optical WDM network in two stages — firstly by ring selection and traffic distribution, and then wavelength allocation. The proposed algorithm can provide efficient and reliable multi-wavelength networks with multiple rings. Lardies et al address designing a WDM ring network with an arbitrary topology based on the routing of the inter-ring traffic and traffic balancing with wavelength assignment (TBWA), locally on individual rings. An efficient algorithm is demonstrated to find optimal solutions in a number of experiments subject to both symmetric and asymmetric traffic demands. Nagarajan and Raskina [7] consider the optimal cost stacked uni-directional path switched ring (UPSR) design problem to minimise the overall cost arising from three major equipment types — nodal add/drop multiplexer, express node, and fixed ring. Two approaches, the hybrid bin-packing and column generation heuristics, are implemented in numerical simulations. They can both generate design solutions within 10% of the cost’s lower bound on average; however, the second approach yields a slightly worse cost performance though it runs considerably faster than the first one.
Any heuristic is problem specific, and does not have formal procedures. A more formal and well-established method based on a global search genetic algorithm, in contrast with a local search procedure, is a metaheuristics which is able to explore and exploit large regions of the search space without being trapped in local optima, and so can lead to a sub-optimum or globally optimum solution. Recently, a growing number of researchers and practitioners have successfully adopted these techniques for solving large-scale ring network design problems.
White et al [10] propose a genetic algorithm with a novel, hybrid bit and permutation representation for designing a ring network. Its efficiency at searching large problem spaces is shown through a number of test problems by comparing with heuristic design methods. An intelligent computer aided design (CAD) tool is developed by Chlamtac et al [9] to support the specification, design, simulation and optimisation of optical communications networks. This tool can automatically produce an optimum design, which satisfies all design constraints, using mathematical programming techniques and intelligent search methods such as simulated annealing and genetic algorithms. The optimal number of transceivers for each network node in terms of the cost of the devices and the overall system performance has been obtained in the experimental results for designing packet-switching wavelength division multiplexing all-optical communications systems using a LAN/MAN ring topology. Following their previous work [10], Armony et al introduce a genetic algorithm for solving SONET ring tructure design problems. The effectiveness of the GA s shown by comparing it with existing integer programming schemes in a number of computational experiments. In designing a minimum-cost ring-based network topology, a genetic algorithm is implemented by Ombuki et al with a problem-oriented crossover operator used to generate feasible solutions. Experimental simulations suggest the effectiveness of the proposed GA. Cox and Sanchez model the multi-part dense wavelength division multiplexing (DWDM) network planning problem as a large-scale integer program and propose a genetic algorithm to solve it. By comparing mesh with ring architectures on several test problems, the conditions under which each is most advantageous are also illuminated. A genetic algorithm is utilised by Chen and Zheng [23] for ring networks in order to balance the traffic loads on ATM rings and minimise the overall capacity requirement of the rings. Computational studies demonstrate that the proposed GA outperforms other known algorithms.
A realistic ring-based SDH optical long-haul network design problem with large-scale and multiple nonlinear constraints is described in the next section. Genetic algorithms have been shown to be arguably one of the most effective and efficient ways of solving large-scale combinatorial optimisation problems in engineering fields, including telecommunications network design. Accordingly, we choose to compare our own approach with such a GA. The mechanism of the GA and a novel evolutionary algorithm called ‘smart ring algorithm’.
References
  1. Maeda M W: ‘Management and control of transparent optical networks’, IEEE JSAC, 16, No 7, pp 1061—1073 (1998).
  2. Miyao Y and Saito H: ‘Optimal design and evaluation of survivable WDM transport networks’, IEEE JSAC, 16, No 7, pp 1190—1198 (1998).
  3. Morley G D and Grover W D: ‘Current approaches in the design of ring-based optical networks’, Proceedings of the 1999 IEEE Conference on Electrical and Computer Engineering, Alberta, Canada (May 1999).
  4. Shackleton M and Marrow P (Eds): ‘Nature-inspired computation’, Special Issue of BT Technol J, 18, No 4, (October 2000).
  5. Goldberg D E: ‘Genetic Algorithms in Search, Optimization and Machine Learning’, Addison Wesley, Reading, MA (1989).
  6. Back T, Fogel D B and Michalewicz Z (Eds): ‘Handbook of Evolutionary Computation’, joint published by Institute of Physics Publishing and Oxford University Press (1997).
  7. Yizhi X, Qingji Z and Yufeng L: ‘Design of logical topologies for wavelength-routed ring network’, ICCT’98, International Conference on Communication Technology, Proceedings, Publishing House of Constr Mater, 1, p 5 (October 1998).
  8. Xiong Y Z, Zeng Q J, Cheng Y and Wu K: ‘Optimal design of wavelength-routed multi-fiber ring networks’, Journal of Shanghai Jiaotong University, 35, No1, pp 17—21 (January 2001).
  9. Grouz D L: ‘Designing radio-mobile access networks based on SDH ring structures’, Proceedings of Second International Workshop on the Design of Reliable Communication Networks, DRCN 2000, Herbert Utz Verlag, pp 135—40 (April 2000).
  10. Miyao Y and Saito H: ‘Optimal design of survivable photonic transport networks of interconnected WDM self-healing ring systems’, IEICE Transactions on Communications, E83-B, No 10, pp 2261—2269 (October 2000).
  11. Shiue W T: ‘High level synthesis for peak power minimization using ILP’, Proceedings 2000 International Conference on Application-Specific Systems, Architecture, and Processors, IEEE Computer Society, pp 103—112 (July 2000).
  12. Ball M and Magazine M: ‘The design and analysis of heuristics’, Networks, 11, pp 215—219 (1981).
  13. Grover W D, Slevinsky J B and MacGregor M H: ‘Optimized design of ring-based survivable networks’, Canadian Journal of Electrical and Computer Engineering, 20, No 3, pp 139—149 (August 1995).