Network topology determining method and apparatus, and system

Patent metadata

Field	Value
Publication number	US-11929905-B2
Application number	US-202117337694-A
Country	US
Kind code	B2
Filing date	Jun 3, 2021
Priority date	Dec 27, 2018
Publication date	Mar 12, 2024
Grant date	Mar 12, 2024

Abstract

A network topology determining apparatus includes: an obtaining module, configured to obtain a connection relationship between a plurality of network elements in a network and a network grade of each network element, where the network grade is used to indicate an importance degree of the network element in the network; a first determining module, configured to determine a plurality of subnets based on the connection relationship between the plurality of network elements and the network grade of each network element; a second determining module, configured to determine location information of each network element in a descending order of the network grades of the network elements in the network based on a connection relationship between network elements in each subnet; and an establishment module, configured to establish a network topology based on the connection relationship between the plurality of network elements and the location information of each network element.

First claim

What is claimed is:

1. A network topology determining apparatus, comprising: at least one processor; and a memory, wherein the memory is configured to store a program, and wherein the program, when executed by the at least one processor, causes the network topology determining apparatus to:
obtain a connection relationship between a plurality of network elements that are comprised in a network and a network grade of each network element, wherein the network grade is used to indicate an importance degree of the network element in the network;
determine a plurality of subnets based on the connection relationship between the plurality of network elements and the network grade of each network element;
automatically determine location information of each network element in a descending order of network grades of the plurality of network elements in the network based on a connection relationship between network elements in each subnet;
establish a network topology based on the connection relationship between the plurality of network elements and the location information of each network element; and
generating a graph representing the network based on the network topology, wherein the graph displays how the plurality of network elements are interconnected in the network,
wherein to automatically determine the location information of each network element, the program, when executed by the at least one processor, further causes the network topology determining apparatus to:
sequence a plurality of core network elements that are comprised in a core subnet of the network, to obtain a first network element queue, wherein the plurality of core network elements comprises network elements of a highest network grade in the plurality of network elements;
obtain a first spacing between every two adjacent core network elements in the first network element queue; and
determine location information of each core network element based on the first spacing and a total quantity of the core network elements in the first network element queue.

2. The apparatus according to claim 1 , wherein the plurality of core network elements are arranged on a boundary of a first graph; and when determining the location information of each core network element based on the first spacing and the total quantity of the core network elements, the program, when executed by the at least one processor, further causes the network topology determining apparatus to:
determine a first fixed-length parameter of the first graph based on the total quantity of the core network elements, wherein the first fixed-length parameter is used to indicate a geometric feature satisfied by points on the first graph; and
sequentially determine location information of all core network elements in the first network element queue in order of positions in the first network element queue, wherein the sequentially determining location information is performed based on the first fixed-length parameter and the first spacing.

3. The apparatus according to claim 1 , wherein when obtaining the first spacing between every two adjacent core network elements in the first network element queue, the program, when executed by the at least one processor, further causes the network topology determining apparatus to:
determine the first spacing based on a first total quantity of connected network elements between the two adjacent core network elements.

4. The apparatus according to claim 3 , wherein the first spacing is represented by a first included angle formed by lines connecting a specified point and the two adjacent core network elements; and when determining the first spacing based on the first total quantity of connected network elements between the two adjacent core network elements, the program, when executed by the at least one processor, further causes the network topology determining apparatus to:
determine a first total quantity proportion of the first total quantity in a second total quantity, wherein the second total quantity is a total quantity of connected network elements of all the core network elements; and
determine a product of the first total quantity proportion and 360 degrees as the first included angle.

5. The apparatus according to claim 1 , wherein the program, when executed by the at least one processor, further causes the network topology determining apparatus to:
classify a plurality of secondary network elements in a secondary subnet into a plurality of first network element groups based on the connection relationship between the network elements, wherein the secondary network elements are network elements directly connected to the core network elements in the plurality of network elements, and the core network elements are the network elements of the highest network grade in the plurality of network elements;
sequence at least one secondary network element in each first network element group to obtain a second network element queue;
sequence the plurality of first network element groups to obtain a network element group queue;
determine a layout width of each first network element group based on a third total quantity of connected network elements of all secondary network elements in each first network element group;
determine a layout start location of any first network element group based on the layout width of each first network element group and a position of the any first network element group in the network element group queue; and
determine location information of each secondary network element based on the layout width, the layout start location, a total group quantity of the plurality of first network element groups, the second network element queue, the network element group queue, and a total quantity of secondary network elements in each first network element group.

6. The apparatus according to claim 5 , wherein the plurality of secondary network elements are arranged on a boundary of at least one second graph; and when determining the location information of each secondary network element based on the layout width, the layout start location, the total group quantity of the plurality of first network element groups, the second network element queue, the network element group queue, and the total quantity of secondary network elements in each first network element group, the program, when executed by the at least one processor, further causes the network topology determining apparatus to:
determine, based on a position of the first network element group in which each secondary network element is located in the network element group queue, a second graph on which each secondary network element is located;
determine a second fixed-length parameter of each second graph based on the total quantity of secondary network elements and the total group quantity of the first network element groups, wherein the second fixed-length parameter is used to indicate a geometric feature satisfied by points on the corresponding second graph; and
determine the location information of the secondary network element based on a position of each secondary network element in the second network element queue, the second fixed-length parameter corresponding to the secondary network element, the layout width, the layout start location, and the total quantity of secondary network elements in the first network element group in which each secondary network element is located.

7. The apparatus according to claim 5 , wherein the layout width of each first network element group is represented by a second included angle formed by lines connecting a specified point and two secondary network elements on an outermost side of the first network element group; and when determining the layout width of each first network element group based on

Assignees

• Huawei Tech Co Ltd

Inventors

• Huang Hualin
• Chen Zhenguang
• Wang Bo
• Yan Lu
• Yang Yi
• Fu Yaojun

Classifications

• H04L45/02 Primary

  Topology update or discovery · CPC title

• H04L12/42

  Loop networks · CPC title

• H04L43/045

  for graphical visualisation of monitoring data · CPC title

• H04W40/246

  Connectivity information discovery · CPC title