Multiply-connected network synthesis algorithm

Introduction
I personally did not come across the “official” algorithm for synthesizing multiply-connected networks either on the Internet or in the process of training in 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 would like to note that it mainly arises in the process of modeling and designing telecommunication networks of various scales. To implement the project obtained in the course of such modeling in practice or not depends primarily on its goals. If this is a course work of students of specialties related to telecommunications, then the recommendations described below are quite applicable to them. Organizations involved in designing networks of national or at least urban scale use their practical methods of building multiply connected networks, however, it is possible that the information presented in the article will be useful for them.

Algorithm
In Donetsk National Technical University, the specialty TCS (Telecommunication Systems and Networks) in the framework of the course “Network Theory” teach the following sequence (algorithm) of building a multi-connected network:

0) As the source data there is a matrix of distances (L) between the end objects of the network (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 i-th and j-th node. Lii = Ljj = 0 - the distance from the current node to itself. On the basis of this matrix and choosing the medium of information transmission (let it be cable lines of communication) we can build a cost matrix (C) by multiplying the distances by a conventional or real unit cost of a meter or a kilometer of cable.

1) Build a base topology matrix (Cb). As a basic topology, it is proposed to use one of these options - the optimal ring, the minimum spanning tree, the star. For constructing the matrix of the basic topology for each of these options, there are different algorithms that are not affected in this article. Let us just say that the principle of constructing these topologies is the same - the minimum distance between nodes within a given topology, each with its own basic properties. For an optimal ring, such a property is the existence of two different paths between nodes, which provides duplication, for a star it is the presence of a central node through which all information flows pass, for a minimum spanning tree, there is no closed paths (loops) in the topology.
')
2) Actually building a multiply connected network by introducing additional branches into the matrix of the base topology in accordance with any limiting criteria, upon reaching which the multiply connected network is considered to be constructed. As such criteria, the number of intermediate nodes (Kij) on the path between the two selected nodes i and j are chosen (differently, the criterion can be called the “number of intersections”) and the cost of entering a branch into the network. Thus, by setting some limit on the parameter K, and by choosing from the matrix (C) the minimum elements at each step of the algorithm, we gradually get a multiply-connected network occupying an intermediate, but not optimal (!) Place compared to a fully connected network and a network of basic topology cost and number of receptions of information between two nodes. When the specified limit by criterion (K) is reached for all network nodes, the multiply-connected network is considered ready.

Proposed improvement of the algorithm described above
Improvement at first glance is 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 (C entered = ijmin), but enter the node meeting the criterion minimum ((Cij / Cmin) + (Wmax / Wij)) into a multiply connected network, where ij is the matrix element () that is checked for compliance with the criterion, Cmin is the minimum cost matrix element () at this step of the algorithm, Wij is the value showing the change in the number of hops (parameter K) compared to the network state before entering the Cij branch, Wmax - maximum possible change of 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 build the matrix W, which reflects the change in the parameter K for all network elements, by introducing into it the element Cij, from which the Wij and Wmax elements are then 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 a set of other intermediate matrices and the use of algorithms not specified in the article - for example, the Floyd algorithm.
This method of building a multiply-connected network allows you to get, if not the optimal network by the criteria of cost and number of intermediate nodes, then the comparatively best one is accurate. The disadvantage of this method is the computational complexity compared to the first option, without software implementation, it is extremely difficult to apply it even for networks with a relatively small number of nodes.

The text is distributed under the Creative Commons Attribution-Share Alike license