The general concept about problems of telecommunication networks synthesis and analysis

All problems appearing by telecommunication networks construction and maintenance can be divided into two classes: problems of synthesis and problems of analysis.

«Synthesis» according to the translation from Greek means «union, composition».

The problem of network synthesis arises at a new network constructing, and at existing networks reconstructing and developing. This problem has technical and economic nature because more often the solution, optimal for a number of economic parameters such as minimum capital investment, is found.

At network synthesis location of network points is usually assumed as given one. The communication lines configuration (topology) can vary at economic parameters optimization. It allows to use expenses for communication lines as a target criterion of the optimum network synthesis. The restrictions on exceptional separate geographical routes in the organization of the communication between points, for example, if they cross the water or mountain obstacles can be made on the lines configuration.

The problems of choosing optimal network topology, optimal number and switching nodes location etc. can refer to the particular problems of synthesis.

Analysis problems are topical for existing (the synthesized) network. These problems include the problems of a finding optimal ways for the information messages transmission, set ways with a given transient determination, network capacity estimations, probability of the path connection between points determination etc.

Also the questions of calculating characteristics and parameters as networks on the whole, and also its separate elements are considered in the class of analysis problems. The quality of service on the network, reliability and survivability parameters refer to such characteristics.

To solve a specific problem of telecommunication network synthesis or analysis, it is necessary to formalize this problem, i.e. to write down it in the form of scheme: what is given, what is necessary to define and under which restrictions.

Formalization can be executed in verbal form (such form is called verbal model of a problem) or in the form of the mathematical model presenting a problem in terms of this or that theory (for example, graph theory, theories of optimal decisions, etc.)

Formalization implementing requires not only the given problem understanding, but also choosing the matching model of the object (telecommunication network). The modeling (simplified) representation of synthesis or analysis object allows to identify and to represent the most significant elements of object and connection between them from the point of view of existing problem, without distracting on details.

For modeling representation of telecommunication networks graph models are mostly used. The mathematical model representing dependence between required parameters and independent variables in problem in the form of mathematical functions can be built on the basis of object model and its parameters (quantity of points and network lines, distances between points, nodes capacity and network lines, cost parameters, etc.).

Mathematical models of optimization where the purpose of problem solution is written in the form of so-called criterion function for which it is necessary to find an extremum ( minimum ormaximum) are used more often in the problems of telecommunication networks synthesis and analysis. The imposed limits, specifying in which borders required parameters values to be changed, can be made on the incoming parameters.

D e f i n i t i o n. The problems, where the extremum (the minimum or maximum) of some criterion function, representing an optimization of the problem solution, is found, are called extreme.

Specific feature of extreme problems of telecommunication networks synthesis and analysis is their big dimensions. The formulation of these problems in terms of graph and network models allowed us to obtain a series of effective, from the point of view of computing complexity overcoming, methods and algorithms for their solving oriented to computer applying. A series of such algorithms are considered below.

T he algorithm is understood as the procedure, providing the optimal solution of a problem, performance of which can be entrusted to the computer. They differ such algorithms as the exact and approximate, so-called heuristic.

Exact algorithms always guarantee finding the optimal solution (criterion function global optimum). For example, the algorithm of exhaustive search of all possible solutions with choosing the best of them, is exact algorithm.

However, the exact algorithms, as a rule, are quite time-consuming from the computation point of view. Therefore, in practice, they often use more simple algorithms providing quick solutions obtaining with acceptable accuracy for practice. Such algorithms are constructed using rational, from the point of view of human logic, rules of calculations performing. These rules are called heuristics and, as practice shows, allow to obtain the solution, close to the optimal one. For example, the problem of determining the closed contour with a minimal length, which provides by-path of all network points, can be solved by complete searching of all possible contours with choosing among them the minimal length contour, i.e. exact algorithm. It is known, that for a network containing n points, the quantity of possible contours is n!,obtaining of which for the network of n > 30 size, represents considerable difficulties. However, heuristics usage: «on each step one moves only to the nearest point» provides reception of the acceptable solution for a time necessary for only one contour constructing.

Heuristic algorithms are used also in those cases when it is impossible to build an exact algorithm because of the mathematical model complexity of the problem (its nonlinearity, discreteness and etc.).