Multiconnected Network Synthesis Algorithm

Introduction
I personally have not come across the “official” algorithm for synthesizing multiply connected networks either on the Internet or in the process of studying at a technical university. There are more likely methods of building multiply connected networks than registered and patented algorithms. For those who have never encountered such a task, I want to note that it mainly arises in the process of modeling and designing telecommunication networks of various scales. Whether or not to realize a project obtained in the process of such modeling in practice depends primarily on its goals. If this is a term paper of students specializing in telecommunications, then the recommendations described below are quite applicable to them. Organizations involved in the design of networks of national or at least urban scales use their practical methods for building multiply connected networks,

Algorithm
In Donetsk National Technical University, in the specialty of TCS (Telecommunication Systems and Networks), as part of the Network Theory course, the following sequence (algorithm) of building a multiply connected network is taught:

0) The distance matrix (L) between the terminal objects of the network (on in practice, for example, routers can act as them). The matrix is ​​square, where each element (Lij = Lji) is equal to the distance (meters, kilometers) between the ith and jth nodes. Lii = Ljj = 0 - distance from the current node to itself. Based on this matrix and choosing an information transfer medium (let it be cable communication lines), we can build a cost matrix (C) by multiplying distances by a conditional or real unit of cost per meter or kilometer of cable.

1) We construct a matrix of basic topology (Cb). It is proposed to use one of these options as basic topologies - the optimal ring, the minimum spanning tree, and the star. To construct a matrix of the basic topology for each of these options, there are algorithms that are not addressed in this article. We will only say that the principle of constructing these topologies is the same - the minimum distance between nodes within a given topology is different each in its basic properties. For an optimal ring, such a property is the existence of two different paths between nodes, which ensures duplication, for a star it means the presence of a central node through which all information flows pass, for a minimal spanning tree, the absence of closed paths (loops) in the topology.

2) The actual construction of a multiply connected network by introducing additional branches into the matrix of the basic topology in accordance with any limiting criteria, upon reaching which the multiply connected network is considered to be built. As such criteria, the number of intermediate nodes (Kij) on the path between the two selected nodes i and j is chosen (in other words, the “number of retries”) and the cost of introducing the branch into the network. Thus, by setting some restriction on the parameter K, and by choosing the minimum elements from the matrix (C) at each step of this algorithm, we gradually obtain a multiply connected network occupying an intermediate, but not optimal (!) Place, compared to a fully connected network and a network of basic topology in cost and the number of retries of information between two nodes.

Proposed improvement of the algorithm described above The
improvement is at first glance simple. - In the second paragraph of the method described above, it is proposed to choose from the matrix (C) at each step of the algorithm not the minimum value (Сinputable = Сijmin), but to enter the node corresponding to the criterion minimum ((Сij / Cmin) + (Wmax / Wij) into the multiply connected network where Сij is the element of the matrix (C) checked for compliance with the criterion, Cmin is the minimum element of the cost matrix (C) at this step of the algorithm, Wij is the value indicating the change in the number of retries (parameter K) compared to the state of the network before entering the branch Сij, Wmax - the maximum possible change in the parameter W for the current its network status.
To implement this improvement, at each step of the algorithm, the current state of the network is recalculated, to construct a matrix W that reflects the change in the parameter K for all elements of the network when a Cij element is introduced into it, from which then the elements Wij and Wmax are taken. The steps of the algorithm are divided into substeps, the number of which will depend on the size of the network.

This is just a general description of the proposed method. The software implementation includes the construction of many other intermediate matrices and the application of algorithms not specified in the article, for example, Floyd's algorithm.
This method of building a multiply connected network allows you to get, if not the optimal network according to the criteria of cost and the number of intermediate nodes, then the comparatively better one - that's for sure. The disadvantage of this method is the complexity of the calculations compared to the first option, without a software implementation it is extremely difficult to apply even for networks with a relatively small number of nodes.

Text licensed under Creative Commons Attribution-Share Alike

Also popular now: