CN111695223B - Network topology layout method and system - Google Patents
Network topology layout method and system Download PDFInfo
- Publication number
- CN111695223B CN111695223B CN202010527898.3A CN202010527898A CN111695223B CN 111695223 B CN111695223 B CN 111695223B CN 202010527898 A CN202010527898 A CN 202010527898A CN 111695223 B CN111695223 B CN 111695223B
- Authority
- CN
- China
- Prior art keywords
- network
- node
- chain
- sub
- tree
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 28
- 238000013467 fragmentation Methods 0.000 claims abstract description 11
- 238000006062 fragmentation reaction Methods 0.000 claims abstract description 11
- 239000010410 layer Substances 0.000 claims description 58
- 239000012792 core layer Substances 0.000 claims description 22
- 230000002776 aggregation Effects 0.000 claims description 11
- 238000004220 aggregation Methods 0.000 claims description 11
- 238000012545 processing Methods 0.000 claims description 6
- 230000011218 segmentation Effects 0.000 claims description 3
- 230000008569 process Effects 0.000 description 3
- 238000013528 artificial neural network Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 239000013598 vector Substances 0.000 description 2
- 230000009471 action Effects 0.000 description 1
- 238000007792 addition Methods 0.000 description 1
- 238000013459 approach Methods 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 230000002860 competitive effect Effects 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 239000012634 fragment Substances 0.000 description 1
- 238000013507 mapping Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000006467 substitution reaction Methods 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/10—Geometric CAD
- G06F30/18—Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Geometry (AREA)
- Theoretical Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Analysis (AREA)
- Computational Mathematics (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Computer Hardware Design (AREA)
- Evolutionary Computation (AREA)
- General Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The invention discloses a network topology layout method, which divides a network into a plurality of block networks in a fragmentation way, respectively carries out topology layout on a ring-shaped sub-network and a chain/tree-shaped sub-network in each block network, divides the hierarchy based on the service characteristics of network elements, determines the position information of each network element of each hierarchy of the ring-shaped sub-network according to a force-oriented algorithm, carries out layer-by-layer layout and constructs the network topology of the ring-shaped sub-network; and determining the positions of the nodes on the chains of the chain/tree sub-networks by taking the root node of each chain/tree sub-network as an initial position based on a force guiding algorithm, and constructing the network topology of each chain/tree sub-network by layer layout. Correspondingly, the invention also discloses a network topology layout system. By the method and the device, the stable network topology can be rapidly acquired.
Description
Technical Field
The present invention relates to the field of communications technologies, and in particular, to a network topology layout method and system.
Background
The network topology is the physical layout of the various network elements interconnected by a transmission medium. The network topology is usually obtained from the connection of the network elements in the network. In the network topology, the logical relationship between network element devices, the logical relationship between connection devices, the topological relationship between ports, and the like may be displayed in the form of graphics. In a network topology, these network element devices, connection devices, ports, etc. are collectively referred to as nodes. The position of a node in the network topology is determined by the topological structure of the network where the node is located, the hierarchical relationship of the node in the network and the like. The positions of the nodes are arranged according to the logical relationship among the nodes, so that the whole network topological graph is consistent with the actual topological structure of the network, and a user can manage and maintain the whole network system.
In the prior art, the following methods are mainly used for the common network topology layout: random placement, combinatorial placement based on individual grids, node force directed network placement, neural network placement.
In the technical scheme of random layout, the layout is based on a simple network structure, the technical scheme defines the network by using simple structures such as a linear structure, a rectangular structure, an oval structure, a tree structure and the like, the network is arranged and distributed according to the shape structure, and a simple network topological graph is obtained.
The technical scheme of the combined layout based on the simple grids divides the integral complex network into a plurality of regional networks, adopts the simple layout and divide and conquer in a single grid, and then forms the integral network topological layout according to the relationship among the networks. The technical scheme improves the adaptability of the traditional simple layout algorithm to a complex network, but has poor effect on the network layout of complex relationships.
In the technical scheme of the network topology layout based on the node force guidance, each node is configured with a physical attribute, a mutual repulsion force is calculated among the nodes along with the change of the distance, meanwhile, each connecting line is also configured with a physical attribute, and two ends of each connecting line have certain attraction force. Thus, each node is constantly moving under the action of the attractive and repulsive forces until the two forces reach a force equilibrium and reach a steady state. The technical scheme has a good effect on a simple network, but when the number of nodes is large or the network structure is complex, a plurality of nodes are difficult to balance, the connection lines have a crossing problem, and the technical scheme has strong dependence on the initial node position.
In the technical scheme based on the neural network layout, the key is to assign a relevant two-dimensional vector for nodes in the network so as to set the layout position. Based on the minimum principle of the number of edge intersections, the spatial position approach principle of adjacent points and the minimum principle of regions, the node mapping vectors are adjusted through continuous competitive learning among the nodes, and therefore the final network topology layout is formed. The solution is more efficient than the force directing arrangement. But the layout reasonableness and the aesthetic degree are not good enough, and the problem of the dependence on the initial node position in the force guiding technical scheme is not solved.
There is not a good technical solution for 5G network topology layout in the prior art. Due to the complex structure of the 5G network, the technical solutions have the same or similar limitations when applied to the topology layout of the 5G network, and the technical solutions of the two are not suitable for the large-scale network such as the 5G network. According to the technical scheme of the node force-oriented network layout, when the number of nodes and the number of connections are more, the algorithm is not converged, the time consumption of the process of obtaining the network topology is long, meanwhile, when an energy model is established, the initial position of the node needs to be specified, and the obtained network topology structure has uncertainty, so that the technical scheme is not suitable for a 5G complex network structure.
Disclosure of Invention
In view of this, the present invention provides a method and a system for network topology layout, which can perform network topology layout on a complex network quickly and effectively.
In order to achieve the above object, the present invention provides a network topology layout method, including:
s1, based on the connection relation among network elements forming a network, segmenting the network and dividing the network into a plurality of block networks;
s2, in each block network, acquiring all chain/tree sub-networks and all ring sub-networks, and determining a root node of each chain/tree sub-network;
s3, according to the network hierarchy of the network elements in each ring-shaped sub-network, determining position information of the network elements of each hierarchy based on a force-directed algorithm according to the sequence from high to low of the network hierarchy, and constructing the network topology of each ring-shaped sub-network;
and S4, determining position information for each level network element on the chain of the chain/tree-shaped sub-network based on a force guide algorithm by taking the root node of each chain/tree-shaped sub-network as an initial position, and constructing the network topology of each chain/tree-shaped sub-network.
Preferably, the step S1 includes simplifying the composed network, and the simplifying step includes:
combining all links between any two nodes in the network into one link, selecting the highest bandwidth of all the links as the link bandwidth of the link, and setting the link coefficient of the link based on the link bandwidth;
and obtaining an undirected graph G = < V, E > corresponding to the network according to the link of each node, wherein V represents the combination of nodes in the network, and E represents the link between the nodes.
Preferably, the step S1 includes:
n sets S1 and S2 \8230 \ 8230Sn are created according to the undirected graph, all links are traversed, if head and tail nodes connected by a current link Ei do not belong to the same set, two sets where the head and tail nodes are located are merged into a set Si, and the nodes in the set Si and corresponding links form a block network;
and by analogy, traversing all links in the undirected graph to obtain a plurality of block networks.
Preferably, the step S1 further includes:
determining the number of nodes and the number of links in each block network according to the divided block networks;
determining the size of each block network according to the number of nodes and the number of links in each block network;
and determining the coordinates, the length and the width of the upper left corner of each block network according to the size of each block network, and determining the position of each block network in the network topology.
Preferably, the step S1 further includes:
and (3) slicing according to the rectangle, and calculating the size of the block network based on the following formula:
wherein, L is the width of the rectangle, H is the height of the network element, n is the number of the network elements, and m is the number of the links.
Preferably, the step S2 includes:
inquiring nodes Vi with the node degree smaller than or equal to 1 in a node set V in the current block network undirected graph;
if the query is successful, the node Vi is moved out of the set V, the node Vi is placed into the node set V1, and the link Ei corresponding to the node Vi is removed from the link set E and is moved into the link set E1;
subtracting 1 from the node degree of the node associated with the node Vi, and repeating the steps until all the node numbers are traversed to form a chain/tree set G1= < V1, E1>;
in the chain/tree set G1, if the head node or the tail node of the link En is not in the V1 set, marking the node En as a root node, and adding the node into the V1;
and (4) carrying out fragmentation processing on the chain/tree set to obtain a plurality of independent chain/tree sub-networks.
Preferably, the step S2 further includes:
inquiring nodes with the node degree greater than 1 and corresponding links in a node set V in the current block network undirected graph to form a ring set;
and carrying out fragmentation processing on the ring set to obtain a plurality of independent ring sub-networks.
Preferably, the step S3 includes:
the network hierarchy comprises a core layer network, an aggregation layer network and an access layer network;
traversing the network elements of the core layer and corresponding links, acquiring a first group of network elements with a minimum link coefficient of K in the network elements of the core layer, and determining coordinate positions of all the network elements in the first group of network elements based on a force-oriented layout;
acquiring a second group of network elements with a link coefficient of K +1 in the core layer network element, and determining coordinate positions of all network elements in the second group of network elements based on force guide layout;
repeating the steps until the coordinate positions of all the core layer network elements are confirmed;
and repeating the steps to sequentially confirm the coordinate position of the network element of the convergence layer and the coordinate position of the network element of the access layer.
Preferably, the step S4 includes:
acquiring a central point P of a current block network and a root node of a current chain/tree sub-network;
calculating the hierarchy of each node on the chain of the chain/tree sub-network by taking the root node as a circle center, wherein the hierarchy C of the root node is 0, and the hierarchy of each node is the hop number from the root node;
setting the front node of the root node as a midpoint P, and setting the front node of each node on the chain of other chain/tree sub-networks as a previous hop node away from the root node;
acquiring a network element with a level C of 1, determining all network elements with the level C of 1 within a range of 90-180 degrees by taking an extension line of a connecting line of a C-1 layer node and a front node thereof as a center and a preset radius length as a radius, and determining position coordinates of all network elements based on force guide layout;
repeating the steps based on the position of the network element with the level 1, and determining the position coordinates of all the network elements with the level 2;
and determining the position coordinates of all network elements of each level on the chain of the chain/tree-shaped sub-network by the same method, and finishing the topological layout of the chain/tree-shaped sub-network.
To achieve the above object, the present invention provides a network topology layout system, which comprises:
the network segmentation module is used for segmenting the network and dividing the network into a plurality of block networks based on the connection relation among network elements forming the network;
the sub-network module is used for acquiring all chain/tree sub-networks and all ring sub-networks in each block network and determining a root node of each chain/tree sub-network;
the ring sub-network module is used for determining meta-position information of the network elements of each level based on a force guiding algorithm according to the network levels of the network elements in each ring sub-network and the sequence from high to low of the network levels, and constructing the network topology of each ring sub-network;
and the chain sub-network module is used for determining position information of each level network element on the chain of the chain/tree sub-network based on a force guiding algorithm by taking the root node of each chain/tree sub-network as an initial position, and constructing the network topology of each chain/tree sub-network.
Compared with the prior art, the invention provides a network topology layout method and a system, which bring the following beneficial effects: the network is divided into the plurality of block networks in a fragmentation mode, and network topology layout is carried out based on each block network, so that the range of single layout is reduced, the number of nodes of the single layout is reduced, and the speed of the network topology layout is improved; for the network topology layout of the ring-shaped subnet, the network layout is carried out aiming at the network elements of each level through layer-by-layer layout, and the force-oriented algorithm only calculates the position information of the network elements newly added into the level each time, so that the convergence speed of the network topology is high, and the network topology conforms to the complexity of the existing 5G network; aiming at the network topology layout of a chain/tree subnet, according to the hierarchical relation of nodes on a chain, determining position information of network elements of each hierarchy based on a force-directed algorithm, determining the initial position of the network element of the hierarchy added each time, determining the initial position, enabling the network to reach stress balance quickly, effectively improving the efficiency of the network topology layout, and obtaining stable network topology; the technical scheme is combined with the characteristics of the 5G bearing network and accords with the topological layout of the 5G network.
Drawings
Fig. 1 is a flow chart illustrating a network topology layout method according to an embodiment of the present invention.
Fig. 2 is a system block diagram of a network topology placement system in accordance with an embodiment of the present invention.
Detailed Description
The present invention will be described in detail with reference to the specific embodiments shown in the drawings, which are not intended to limit the present invention, and structural, methodological, or functional changes made by those skilled in the art according to the specific embodiments are included in the scope of the present invention.
In an embodiment of the present invention shown in fig. 1, the present invention provides a network topology layout method, where the method includes:
s1, based on the connection relation among network elements forming a network, segmenting the network and dividing the network into a plurality of block networks;
s2, in each block network, acquiring all chain/tree sub-networks and all ring sub-networks, and determining a root node of each chain/tree sub-network;
s3, according to the network hierarchy of the network elements in each ring-shaped sub-network, determining position information of the network elements of each hierarchy based on a force-directed algorithm according to the sequence from high to low of the network hierarchy, and constructing the network topology of each ring-shaped sub-network;
and S4, determining position information for each level network element on the chain of the chain/tree sub-network by taking the root node of each chain/tree sub-network as an initial position based on a force direction algorithm, and constructing the network topology of each chain/tree sub-network.
As described in the background, the network structure of the 5G network is complicated. According to the technical scheme based on the traditional force-oriented layout, when the number of nodes and the number of connections are more, the algorithm is not converged, the time consumption of the process of obtaining the network topology is long, and meanwhile, when an energy model is established, the initial positions of the nodes need to be specified in advance, so that the obtained network topology structure has uncertainty. The invention divides the network into a plurality of block networks in a fragmentation way, and respectively carries out topology layout on a ring sub-network and a chain/tree sub-network in each block network. According to the network hierarchy of the network elements in each ring-shaped sub-network, determining the position information of each network element in each hierarchy based on a force guidance algorithm, laying layer by layer, and constructing the network topology of the ring-shaped sub-network; and determining the positions of the nodes on the chains of the chain/tree-shaped sub-networks by taking the root node of each chain/tree-shaped sub-network as an initial position based on a force guiding algorithm, and laying layer by layer to construct the network topology of each chain/tree-shaped sub-network. Compared with the existing topology technical scheme, the method can quickly converge, determine the initial position of the network element and acquire the stable network topology.
The connection relationship between the network elements and the network hierarchy of each network element in the network are usually determined according to the deployment requirements of the network. The network hierarchy is generally classified in the network according to the importance of the network elements in the whole network topology, and the network hierarchy is used for reflecting the importance degree of the network elements in the network. For more convenient implementation of the present invention, the network formed is first simplified, the simplification comprising: combining all links between any two nodes in the network into a link, selecting the highest bandwidth of all the links as the link bandwidth of the link, namely the link bandwidth of the link between the two nodes, and setting the link coefficient of the link based on the link bandwidth; and obtaining an undirected graph G = < V, E > corresponding to the network according to the link of each node. A node in a network refers to each network element device that constitutes the network. A link between two nodes refers to a link of two network element devices. The link coefficient represents a link bandwidth weight of the link, and the weight range is usually set to 1 to 5. In general, the smaller the link coefficient, the higher its link bandwidth. An undirected graph is a graph with edges having no direction, and is generally represented by an undirected graph G = < V, E >, wherein V represents a combination of nodes in a component network, and E represents a link connection between nodes.
Based on the connection relation among network elements forming the network, the network is segmented and divided into a plurality of block networks, and the number of nodes and the number of links in each block network are determined. Based on network connectivity, the formed network is partitioned into a plurality of block networks, so that the block network to which each node in the network belongs is determined, namely, the network elements belong to the same block network is determined. Specifically, n sets S1 and S2 \8230arecreated according to the undirected graph, wherein \8230Sn, sn, the nodes Vi are judged to belong to which set Si respectively, all links are traversed, if head and tail nodes connected by the current link Ei do not belong to the same set, the two sets where the head and tail nodes are located are merged into the set Si, and the nodes in the set Si and the corresponding links form a block network; and repeating the steps, traversing all links in the undirected graph to obtain a plurality of block networks, and completing the fragmentation of the formed networks. Determining the number of nodes and the number of links in each block network according to the divided block networks; determining the size of each block network according to the number of nodes and the number of links in each block network; and determining the coordinates, the length and the width of the upper left corner of each block network according to the size of each block network, and determining the position of each block network in the network topology. And (3) slicing according to the rectangle, and calculating the size of the block network based on the following formula:
wherein, L is the width of the rectangle, H is the height of the network element, n is the number of the network elements, and m is the number of the links. And the formed network is segmented based on network connectivity, so that the number of nodes in single layout is reduced, and the efficiency of network topology layout is improved.
In each block network, all chain/tree sub-networks are obtained, all ring sub-networks are obtained, and a root node of each chain/tree sub-network is determined. A ring subnetwork refers to a ring network formed by the network passing from a start ring network element through links through one or more network elements to an end ring network element. A chain/tree subnetwork refers to a network of network elements connected in a chain or tree. Specifically, a node Vi with a node degree smaller than or equal to 1 is queried in a node set V in the current block network undirected graph, where the node degree refers to the number of all links of the node, and if the query is successful, the node Vi is removed from the set V and placed in the node set V1, and correspondingly, a link Ei corresponding to the node Vi is removed from a link set E and moved into the link set E1; subtracting 1 from the node degree of the node associated with the node Vi, repeating the steps until all the node numbers are traversed to form a chain/tree set G1= < V1, E1>, in the chain/tree set G1, if the head node or the tail node of the link En is not in the V1 set, marking the head node or the tail node as a root node, and adding the node into the V1; the chain/tree set is subjected to fragmentation processing to obtain a plurality of separate chain/tree sub-networks; and querying nodes with the node degree larger than 1 and corresponding links in a node set V in the current block network undirected graph to form a ring set, and performing fragmentation processing on the ring set to obtain a plurality of independent ring sub-networks. Based on the implementation steps, a chain/tree sub-network and a ring sub-network in the block network are obtained.
And according to the network hierarchy of the network elements in each ring sub-network, determining the position information of each network element of each hierarchy in the sequence from high to low of the network hierarchy and based on a force guiding algorithm, and constructing the network topology of each ring sub-network. The network hierarchy is used to reflect the importance of network elements in the network. The network hierarchy includes a core layer network, an aggregation layer network, and an access layer network. The layering is based on the network layer level and the link coefficient of the network element. And gradually laying out the network topology layer by layer based on the layering. Specifically, first, traverse the network element of the core layer and the corresponding link; obtaining a first group of network elements with the minimum link coefficient of K in the core layer network elements, determining the coordinate positions of all network elements in the first group of network elements based on the force guiding layout, obtaining a second group of network elements with the link coefficient of K +1 in the core layer network elements, determining the coordinate positions of all network elements in the second group of network elements based on the force guiding layout, and so on until the coordinate positions of all the core layer network elements are determined; and repeating the steps to sequentially confirm the coordinate position of the network element of the aggregation layer and the coordinate position of the network element of the access layer. According to the technical scheme, network topology layout is carried out based on a network hierarchy and a link coefficient hierarchy, firstly, network element coordinates with the minimum link coefficient of a core layer network element are confirmed, network elements of a core layer network are added layer by layer based on the link coefficient hierarchy, the network elements of the core layer network are completed through layout, then, aggregation layer network elements are added into the topology, and the coordinate positions of the aggregation layer network elements are determined layer by layer based on force guide layout. And adding network elements of the access layer network to adjust the network topology again, and gradually distributing the network topology layer by layer. In the network topology layout process, if the entire coordinates are unbalanced in the grid, the coordinates will be shifted as a whole, so that the graph is located at the center of the grid. The core network ring is connected with the aggregation network ring, the aggregation layer network ring is connected with the network ring, and the ring bandwidth converges layer by layer. And (4) locking the layer-by-layer layout layer by layer coordinate position, and only calculating the position of a newly added network element in each force-oriented layout so as to accelerate the convergence speed.
And determining the positions of the nodes on the chains of the chain/tree-shaped sub-networks by taking the root node of each chain/tree-shaped sub-network as an initial position based on a force guiding algorithm, and constructing the network topology of each chain/tree-shaped sub-network. In the above steps, the root node of each chain/tree-like sub-network has been determined. Specifically, a central point P of a current block network and a root node of a current chain/tree sub-network are obtained; calculating the hierarchy of each node on the chain of the chain/tree-shaped sub-network by taking the root node as the center of a circle, wherein the hierarchy C of the root node is 0, and the hierarchy of each node is the hop number from the root node; setting the front node of the root node as a midpoint P, and setting the front node of each node on the chain of other chain/tree sub-networks as a previous hop node away from the root node; the method comprises the steps of obtaining a network element with a level C of 1, determining all network elements with the level C of 1 within a range of 90-180 degrees by taking an extension line of a connecting line of a C-1 layer node and a front node thereof as a center and a preset radius length as a radius, and determining position coordinates of all the network elements based on force guiding layout to enable the network elements of the level to be laid out in a sector area. And repeating the steps based on the position of the network element with the level 1, determining the position coordinates of all the network elements with the level 2, and determining the position coordinates of all the network elements of each level on the chain of the chain/tree-shaped sub-network by analogy, thereby completing the topology layout of a chain/tree. According to the technical scheme, the center of a block network is used as a circle center, the hop number from a root node is used as a hierarchy, topological layout is carried out layer by layer outwards, and after all the layout of a layer of network elements is finished, the positions of the network elements are adjusted based on force guiding layout. And calculating the initial position of the next layer based on the current position of the network element, and so on to complete a chain/tree topology layout. Based on the technical scheme, when a new network element is added, the initial position of the added network element is determined according to the chain/tree hierarchical relation, and the force guiding layout is utilized to enable the topological network to quickly reach stress balance and quickly converge.
In an embodiment of the present invention shown in fig. 2, the present invention provides a network topology layout system, which includes:
the network segmentation module 20 is configured to segment a network and divide the network into a plurality of block networks based on a connection relationship between network elements constituting the network;
a sub-network module 21, configured to obtain all chain/tree sub-networks and all ring sub-networks in each block network, and determine a root node of each chain/tree sub-network;
a ring sub-network module 22, configured to determine, for each level of network elements, meta-position information based on a force steering algorithm according to a network level of the network elements in each ring sub-network and from a high level to a low level of the network level, and construct a network topology of each ring sub-network;
a chain sub-network module 23, configured to determine, with the root node of each chain/tree sub-network as an initial position, position information for each level network element on the chain of the chain/tree sub-network based on a force-steering algorithm, and construct a network topology of each chain/tree sub-network.
Based on the connection relation among network elements forming the network, the fragmentation module fragments the network and divides the network into a plurality of block networks, and the number of nodes and the number of links in each block network are determined. Based on network connectivity, the formed network is segmented and divided into a plurality of block networks, so that the block network to which each node in the network belongs is determined, namely, the network elements belong to the same block network is determined.
In each block network, the sub-network module acquires all chain/tree sub-networks and all ring sub-networks, and determines the root node of each chain/tree sub-network to obtain the chain/tree sub-networks and the ring sub-networks in the block network.
And the ring sub-network module determines the position information of each network element of each level according to the network level of the network elements in each ring sub-network from high to low and based on a force guidance algorithm, and constructs the network topology of each ring sub-network, wherein the network level comprises a core layer network, an aggregation layer network and an access layer network. The layering is based on the network layer level and the link coefficient of the network element. And performing network topology layout based on a network hierarchy and a link coefficient hierarchy, firstly confirming the network element coordinate with the minimum link coefficient of the core layer network element, adding the network elements of the core layer network layer by layer based on the link coefficient hierarchy, completing the network element of the core layer network by layout, then adding the aggregation layer network element into the topology, and determining the coordinate position of the aggregation layer network element layer by layer based on force-oriented layout. And adding network elements of the access layer network, adjusting the network topology again, and carrying out network topology layout layer by layer.
And the chain sub-network module takes the root node of each chain/tree sub-network as an initial position, determines the positions of the nodes on the chains of the chain/tree sub-networks based on a force guidance algorithm, and constructs the network topology of each chain/tree sub-network. And taking the center of the block network as a circle center and hop numbers away from the root node as a hierarchy, carrying out topological layout layer by layer, and after the layout of all the network elements of one layer is finished, adjusting the positions of the network elements based on force-directed layout. And calculating the initial position of the next layer based on the current position of the network element, and so on to complete a chain/tree topology layout. Based on the technical scheme, when a new network element is added each time, the initial position of the added network element is determined according to the chain/tree hierarchical relation, and the force guide layout is utilized to enable the topological network to quickly reach stress balance and to quickly converge.
Although the preferred embodiments of the present invention have been disclosed for illustrative purposes, those skilled in the art will appreciate that various modifications, additions and substitutions are possible, without departing from the scope and spirit of the invention as disclosed in the accompanying claims.
Claims (10)
1. A method for topology deployment of a network, the method comprising:
s1, based on the connection relation among network elements forming a network, segmenting the network and dividing the network into a plurality of block networks;
s2, acquiring all chain/tree sub-networks and all ring sub-networks in each block network, and determining a root node of each chain/tree sub-network;
s3, according to the network hierarchy of the network elements in each ring-shaped sub-network, determining meta-position information of the network elements of each hierarchy based on a force-oriented algorithm according to the sequence from high to low of the network hierarchy, and constructing the network topology of each ring-shaped sub-network;
and S4, determining position information for each level network element on the chain of the chain/tree-shaped sub-network based on a force guide algorithm by taking the root node of each chain/tree-shaped sub-network as an initial position, and constructing the network topology of each chain/tree-shaped sub-network.
2. The method for topological layout of a network according to claim 1, wherein said step S1 comprises a simplification of said composed network, said simplification step comprising:
combining all links between any two nodes in the network into one link, selecting the highest bandwidth of all the links as the link bandwidth of the link, and setting the link coefficient of the link based on the link bandwidth;
and obtaining an undirected graph G = < V, E > corresponding to the network according to the link of each node, wherein V represents the combination of nodes in the network, and E represents the link between the nodes.
3. The network topology placement method according to claim 2, characterized in that said step S1 comprises: n sets S1 and S2 \8230 \ 8230Sn are created according to the undirected graph, all links are traversed, if head and tail nodes connected by a current link Ei do not belong to the same set, two sets where the head and tail nodes are located are merged into a set Si, and the nodes in the set Si and corresponding links form a block network;
and in the same way, traversing all the links in the undirected graph to obtain a plurality of block networks.
4. The network topology placement method according to claim 3, characterized in that said step S1 further comprises:
determining the number of nodes and the number of links in each block network according to the divided block networks;
determining the size of each block network according to the number of nodes and the number of links in each block network;
and determining the coordinates, the length and the width of the upper left corner of each block network according to the size of each block network, and determining the position of each block network in the network topology.
5. The network topology placement method according to claim 4, characterized in that said step S1 further comprises:
and (3) slicing according to the rectangle, and calculating the size of the block network based on the following formula:
wherein, L is the width of the rectangle, H is the height of the network element, n is the number of the network elements, and m is the number of the links.
6. The network topology placement method according to claim 2, characterized in that said step S2 comprises: inquiring nodes Vi with the node degree smaller than or equal to 1 in a node set V in the current block network undirected graph;
if the query is successful, the node Vi is moved out of the set V, the node Vi is placed into the node set V1, and the link Ei corresponding to the node Vi is removed from the link set E and moved into the link set E1;
subtracting 1 from the node degree of the node associated with the node Vi, and repeating the steps until all the node numbers are traversed to form a chain/tree set G1= < V1, E1>;
in the chain/tree set G1, if the head node or the tail node of the link En is not in the V1 set, marking the head node or the tail node as a root node, and adding the node into the V1;
and (4) carrying out fragmentation processing on the chain/tree set to obtain a plurality of independent chain/tree sub-networks.
7. The network topology arrangement method according to claim 6, characterized in that said step S2 further comprises:
inquiring nodes with the node degree greater than 1 and corresponding links in a node set V in the current block network undirected graph to form a ring set;
and carrying out fragmentation processing on the ring set to obtain a plurality of independent ring sub-networks.
8. The network topology arrangement method according to claim 7, characterized in that said step S3 comprises: the network hierarchy comprises a core layer network, an aggregation layer network and an access layer network;
traversing the network elements of the core layer and corresponding links, acquiring a first group of network elements with a minimum link coefficient of K in the core layer network elements, and determining coordinate positions of all the network elements in the first group of network elements based on a force guide layout;
acquiring a second group of network elements with a link coefficient of K +1 in the core layer network element, and determining the coordinate positions of all network elements in the second group of network elements based on the force guide layout;
repeating the steps until the coordinate positions of all the core layer network elements are confirmed;
and repeating the steps to sequentially confirm the coordinate position of the network element of the convergence layer and the coordinate position of the network element of the access layer.
9. The network topology arrangement method according to claim 8, characterized in that said step S4 comprises: acquiring a central point P of a current block network and a root node of a current chain/tree sub-network;
calculating the hierarchy of each node on the chain of the chain/tree-shaped sub-network by taking the root node as the center of a circle, wherein the hierarchy C of the root node is 0, and the hierarchy of each node is the hop number from the root node;
setting the front node of the root node as a central point P, and setting the front node of each node on the chain of other chain/tree sub-networks as a previous hop node away from the root node;
acquiring a network element with a hierarchy C of 1, determining all network elements with the hierarchy C of 1 in a range of 90-180 degrees by taking an extension line of a connecting line of a node of a C-1 layer and a front node thereof as a center and a preset radius length as a radius, and determining position coordinates of all network elements based on force guide layout;
repeating the steps based on the position of the network element with the level 1, and determining the position coordinates of all the network elements with the level 2;
and by analogy, the position coordinates of all network elements of each level on the chain of the chain/tree sub-network are determined, and the topology layout of the chain/tree sub-network is completed.
10. A network topology placement system, the system comprising:
the network segmentation module is used for segmenting the network and dividing the network into a plurality of block networks based on the connection relation among all network elements forming the network;
the sub-network module is used for acquiring all chain/tree sub-networks and all ring sub-networks in each block network and determining a root node of each chain/tree sub-network;
the ring sub-network module is used for determining meta-position information of the network elements of each level based on a force guidance algorithm according to the network levels of the network elements in each ring sub-network and the sequence from high to low of the network levels, and constructing the network topology of each ring sub-network;
and the chain sub-network module is used for determining position information of each level network element on the chain of the chain/tree sub-network based on a force-oriented algorithm by taking the root node of each chain/tree sub-network as an initial position, and constructing the network topology of each chain/tree sub-network.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010527898.3A CN111695223B (en) | 2020-06-11 | 2020-06-11 | Network topology layout method and system |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010527898.3A CN111695223B (en) | 2020-06-11 | 2020-06-11 | Network topology layout method and system |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN111695223A CN111695223A (en) | 2020-09-22 |
| CN111695223B true CN111695223B (en) | 2023-03-03 |
Family
ID=72480163
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202010527898.3A Active CN111695223B (en) | 2020-06-11 | 2020-06-11 | Network topology layout method and system |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN111695223B (en) |
Families Citing this family (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112398224B (en) * | 2020-11-12 | 2022-09-27 | 山东鲁软数字科技有限公司 | Method and system for overall layout of ring network model in distribution ring network diagram |
| CN112685865B (en) * | 2021-01-06 | 2022-04-29 | 烽火通信科技股份有限公司 | Multi-topology model merging method, device, equipment and storage medium |
| CN112910689B (en) * | 2021-01-18 | 2022-05-17 | Ut斯达康通讯有限公司 | Clock network topology construction method and system |
| CN113190939B (en) * | 2021-03-22 | 2022-09-06 | 桂林航天工业学院 | A topology analysis and simplification method for large sparse and complex networks based on polygon coefficients |
| CN115811740A (en) * | 2021-09-15 | 2023-03-17 | 中国移动通信集团河南有限公司 | Slice packet network SPN topology layout method and device and readable storage medium |
| CN113904941B (en) * | 2021-09-24 | 2023-11-03 | 绿盟科技集团股份有限公司 | Method, system and electronic device for generating topological graph |
| CN114140555A (en) * | 2021-12-08 | 2022-03-04 | 安天科技集团股份有限公司 | Topological graph layout method, device, equipment and storage medium with ring network structure |
| CN114520810B (en) * | 2022-01-27 | 2024-06-14 | 浪潮工业互联网股份有限公司 | Block data transmission method, equipment and medium based on block chain |
| CN114554399B (en) | 2022-04-25 | 2022-07-29 | 汉朔科技股份有限公司 | Synchronous network construction method, price tag system, computer device and storage medium |
| CN114742178B (en) * | 2022-06-10 | 2022-11-08 | 航天亮丽电气有限责任公司 | Method for non-invasive pressure plate state monitoring through MEMS six-axis sensor |
| CN115225511B (en) * | 2022-07-12 | 2024-05-14 | 浪潮通信信息系统有限公司 | IPRAN topology networking ring and chain series connection method and device |
| CN116055334B (en) * | 2023-01-13 | 2024-04-19 | 中国联合网络通信集团有限公司 | A network layout method, device, electronic device and storage medium |
Citations (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2004208297A (en) * | 2002-12-20 | 2004-07-22 | Hewlett-Packard Development Co Lp | System and method for rapid selection of device in tree topology network |
| WO2010060288A1 (en) * | 2008-11-03 | 2010-06-03 | 华为技术有限公司 | Network topology method, device and system |
| WO2012162946A1 (en) * | 2011-08-16 | 2012-12-06 | 华为技术有限公司 | Message processing method and system |
| CN103500237A (en) * | 2013-07-03 | 2014-01-08 | 国家电网公司 | Automatic image forming method for power distribution network based on logic layout |
| CN103532741A (en) * | 2013-09-27 | 2014-01-22 | 瑞斯康达科技发展股份有限公司 | Access level network topology management method and system |
| CN103580897A (en) * | 2012-07-31 | 2014-02-12 | 华为技术有限公司 | Method and device for generating network topological graph |
| CN105550202A (en) * | 2015-12-02 | 2016-05-04 | 成都科来软件有限公司 | Graphic display method and system based on network access relation |
| CN106685716A (en) * | 2016-12-29 | 2017-05-17 | 平安科技（深圳）有限公司 | Network topology adaptive data visualization method and device |
| WO2018145520A1 (en) * | 2017-02-09 | 2018-08-16 | 中兴通讯股份有限公司 | Subnet division method and device |
| CN109167686A (en) * | 2018-08-28 | 2019-01-08 | 中国科学院电子学研究所苏州研究院 | A kind of layout based on multilayer complex network topologies and show method |
| CN109962811A (en) * | 2019-01-07 | 2019-07-02 | 西南科技大学 | An Incremental Steady-State Layout Method for Time-Varying Network Data |
| CN110011890A (en) * | 2019-03-18 | 2019-07-12 | 彥辰科技有限公司 | A kind of building method of distribution ring tree both scatternets |
| CN111046516A (en) * | 2019-06-06 | 2020-04-21 | 哈尔滨安天科技集团股份有限公司 | Three-dimensional layout method and device for complex network topology and storage equipment |
| CN111149330A (en) * | 2017-09-22 | 2020-05-12 | 华为技术有限公司 | Topology-Aware Controller Association in Software-Defined Networking |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8145850B2 (en) * | 2009-06-22 | 2012-03-27 | Hewlett-Packard Development Company, L.P. | Method and system for visualizing a storage area network |
| US9960992B2 (en) * | 2011-09-01 | 2018-05-01 | Itxc Ip Holdings S.A.R.L. | Systems and methods for routing data in a network |
-
2020
- 2020-06-11 CN CN202010527898.3A patent/CN111695223B/en active Active
Patent Citations (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2004208297A (en) * | 2002-12-20 | 2004-07-22 | Hewlett-Packard Development Co Lp | System and method for rapid selection of device in tree topology network |
| WO2010060288A1 (en) * | 2008-11-03 | 2010-06-03 | 华为技术有限公司 | Network topology method, device and system |
| WO2012162946A1 (en) * | 2011-08-16 | 2012-12-06 | 华为技术有限公司 | Message processing method and system |
| CN103580897A (en) * | 2012-07-31 | 2014-02-12 | 华为技术有限公司 | Method and device for generating network topological graph |
| CN103500237A (en) * | 2013-07-03 | 2014-01-08 | 国家电网公司 | Automatic image forming method for power distribution network based on logic layout |
| CN103532741A (en) * | 2013-09-27 | 2014-01-22 | 瑞斯康达科技发展股份有限公司 | Access level network topology management method and system |
| CN105550202A (en) * | 2015-12-02 | 2016-05-04 | 成都科来软件有限公司 | Graphic display method and system based on network access relation |
| CN106685716A (en) * | 2016-12-29 | 2017-05-17 | 平安科技（深圳）有限公司 | Network topology adaptive data visualization method and device |
| WO2018145520A1 (en) * | 2017-02-09 | 2018-08-16 | 中兴通讯股份有限公司 | Subnet division method and device |
| CN111149330A (en) * | 2017-09-22 | 2020-05-12 | 华为技术有限公司 | Topology-Aware Controller Association in Software-Defined Networking |
| CN109167686A (en) * | 2018-08-28 | 2019-01-08 | 中国科学院电子学研究所苏州研究院 | A kind of layout based on multilayer complex network topologies and show method |
| CN109962811A (en) * | 2019-01-07 | 2019-07-02 | 西南科技大学 | An Incremental Steady-State Layout Method for Time-Varying Network Data |
| CN110011890A (en) * | 2019-03-18 | 2019-07-12 | 彥辰科技有限公司 | A kind of building method of distribution ring tree both scatternets |
| CN111046516A (en) * | 2019-06-06 | 2020-04-21 | 哈尔滨安天科技集团股份有限公司 | Three-dimensional layout method and device for complex network topology and storage equipment |
Non-Patent Citations (3)
| Title |
|---|
| 《An Improved Network Topology Auto-layout Solution Based on Force-Directed Placement》;Gao Yuan.etc;《2009 Ninth International Conference on Hybrid Intelligent Systems》;全文 * |
| 具有层次结构且规模可扩展的多目标路由算法;史美林等;《通信学报》;全文 * |
| 网络拓扑布局技术研究;陈昌娜等;《信息通信》(第10期);全文 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN111695223A (en) | 2020-09-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN111695223B (en) | Network topology layout method and system | |
| CN109842520B (en) | Method, device and system for determining network topology | |
| EP2348678B1 (en) | Network topology method, device and system | |
| CN105046363B (en) | A kind of region distribution system single-line diagram layout and optimization method | |
| CN103837154A (en) | Path planning method and system | |
| CN112291734A (en) | Method for optimizing coverage of mobile sensor network area | |
| CN108600022A (en) | Dynamic network layout accelerating method | |
| CN115865785A (en) | VANET clustering routing method based on k-means clustering | |
| CN107241273B (en) | A kind of communications ring network structure setting method based on genetic algorithm | |
| CN109600756B (en) | Physical cell identification and distribution method based on maximum degree priority dyeing algorithm | |
| CN112383422A (en) | Network topology optimization method for accelerating convergence speed of consistency distributed algorithm | |
| CN112910689B (en) | Clock network topology construction method and system | |
| CN117516562A (en) | Road network processing method and related device | |
| CN110062400A (en) | The node linear method of random two-dimensional and three-dimension sensor network topology belt restraining | |
| CN116597116A (en) | Single tree refinement automatic reconstruction method universal for laser point cloud | |
| CN105678840A (en) | Rapid generation custom road implement method on the basis of three-dimensional terrain software system | |
| Kato et al. | An alife approach to modeling virtual cities | |
| CN109840937A (en) | A kind of 3D point cloud paths planning method based on space quaternary tree | |
| CN106326492A (en) | Space vector data generating method and device | |
| CN114124716B (en) | Balanced domain division method for software defined network | |
| CN117197392A (en) | Digital twinning-based regional division model dynamic rapid generation method, device and medium | |
| CN110034957A (en) | A kind of space vector and the smallest power optical fiber backbone network are the same as starting point service path planing method | |
| CN118884974B (en) | A multi-target UAV patrol path planning method | |
| CN116684273B (en) | An automatic planning method and system for mobile communication network structure based on particle swarm | |
| Zhonghua et al. | Research on network simplification by edge bundling |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |