CN100349418C

CN100349418C - Method for creating tree structure of communication devices

Info

Publication number: CN100349418C
Application number: CNB200410101703XA
Authority: CN
Inventors: 曾虎; 叶智明
Original assignee: Huawei Technologies Co Ltd
Current assignee: Huawei Technologies Service Co Ltd
Priority date: 2004-12-22
Filing date: 2004-12-22
Publication date: 2007-11-14
Anticipated expiration: 2024-12-22
Also published as: CN1798055A

Abstract

The present invention relates to a method for creating a tree structure for a communication device. The method mainly comprises the following steps: firstly, the father node information, the located hierarchical information and the node information of each node which respectively corresponds to each functional blocks included in a signal board of a transmission device for each synchronous digital hierarchy SDH are obtained, and are used as node description information; then, each node is calculated and processed according to the father node information, the located hierarchical information and the node information of each node, and a tree structure of a channel image of the signal board of the transmission device for each SDH is generated. Because the present invention adopts the node description information that contains more information, compared with the time efficiency of the prior art, the generating algorithm of the tree structure provided by the present invention based on the node description information is more greatly improved.

Description

Generate the method for tree structure of communication devices

Technical field

The present invention relates to network communications technology field, relate in particular to a kind of method that generates tree structure of communication devices.

Background technology

In SDH (Synchronous Digital Hierarchy) transmission network, each veneer of SDH transmission equipment all for being made up of various functional blocks, embodies with hierarchical relationship between each functional block on the network element, forms a tree.In transmission network management system, need show with tree figure intuitively and hierarchical relationship between each functional block carry out daily maintenance management thereby be convenient to the webmaster attendant.

For obtaining described tree, at first need adopt corresponding mode to describe described tree in the webmaster side, then, can calculate according to corresponding description content and obtain corresponding tree.

A kind of SDH transmission equipment veneer passage figure tree describing mode that adopts is as follows at present:

When describing the hierarchical relationship (father and son) of described tree, be to identify by in child node, increasing the father node object.As shown in Figure 1, tree T be by node N1, N2, N3 ... the tree that .Nn forms; Its relationships between nodes is described as: (0, N1), (N1, N2), (N1, N3), (N1, N4), (N2, N5), (N3, N6), (N3, N7) ..., (Nm, Nn).

When concerning between employing aforesaid way description node, can cause some extra repetition search operations in order to generate corresponding tree, therefore, the efficient that generates tree is lower.For example, by in the descriptor (N1, N4) information is merely able to know that its father node is N1, is arranged in which level of tree and then can't directly obtains in the sequential scheduling information with one deck about node N4, obtain if desired, then need further to carry out the repetition search operation.

Owing in generating the computational process of tree, lack some information of spanning tree algorithm needs, as information such as node place levels etc.Therefore, will to cause generating according to it efficient of tree of needs lower for the form described of above-mentioned relationships between nodes.

At present, the another kind of SDH transmission equipment veneer passage figure tree describing mode of employing is as follows:

When describing the hierarchical relationship (father and son) of tree structure, identify by in father node, increasing direct child node tabulation (child node that does not comprise child node) object.Still as shown in Figure 1, tree T be by node N1, N2, N3 ... the tree that .Nn forms, relationship description is between node corresponding: (N1, N2, N3, N4), (N2, N5), (N3, N6, N7), (N4, N8, N9) ..., (Nn).

When concerning between this mode description node, can generate needed tree by the method for top-down traversal.But there is the infull problem of information equally in this method, for example, searches node place level, and relatively requires great effort when searching the father node of node, therefore, still has when generating needed tree the problem that efficient is lower in this method.

Summary of the invention

In view of above-mentioned existing in prior technology problem, the purpose of this invention is to provide a kind of method that generates tree structure of communication devices, by changing the form that concerns between description node, effectively improved the efficient that generates corresponding tree.

The objective of the invention is to be achieved through the following technical solutions:

The invention provides a kind of method that generates tree structure of communication devices, comprising:

A, adopt the breadth First traversal method, the father node information of each node of the functional block correspondence that obtaining communication equipment comprises, the hierarchical information at place, and nodal information, and determine first node and last node in each level according to above-mentioned each information;

B, the father node information according to described each node, the hierarchical information at place, nodal information, and first node in each level and last nodal information are handled respectively successively to the node in each layer, generate the tree of communication equipment.

Among the present invention, when described communication equipment was Synchronous Digital Hierarchy SDH transmission equipment veneer, described steps A further comprised:

Adopt the breadth First traversal method to travel through each node that each SDH transmission equipment veneer comprises, obtain the hierarchical information at corresponding father node information, place, and nodal information.

Described nodal information comprises: the numbering of node types and node.

Described step B further comprises:

B1, determine current processing node, and generate node instance;

B2, according to the father node information of described each node, hierarchical information and each level node index at place, obtain the information of all child nodes of current processing node;

B3, described all child node information are added to the child node of current processing node.

Described node instance comprises node status information, and described state information comprises:

Wrapped state, professional load indication, passage user mode, cleared alarm number not, and information is counted in alarm unconfirmed.

Described step B1 also comprises:

When beginning to generate tree, at first root node is defined as current processing node.

Described step B2 also comprises:

Obtain the information of all nodes of following one deck of current processing node place level;

Travel through the information of described node, and determine the information of all child nodes of current processing node according to the father node information of described each node.

Described step B3 also comprises:

B31, judge whether described child node is leaf node, if, execution in step B32 then, otherwise, execution in step B33;

Step B32, judge whether to exist current processing node,, then determine next current processing node if exist, execution in step B1, otherwise, finish this process;

Step B33, described child node are set to current processing node, and execution in step B1.

As seen from the above technical solution provided by the invention, after the present invention adopts said method, the time efficiency that the rise time efficient of passage figure functional block tree and two kinds of trees of the prior art generate is more as shown in table 1, and numerical value unit is ms (millisecond) in the table:

Scale of the project	Prior art (one)	Prior art two	The present invention	Improve percentage
Scale of the project	Prior art (one)	Prior art two	The present invention	Improve percentage	50 node balance trees	321	297	203
100 node balance trees	578	493	360	9％	50 node balance trees	321	297	203
100 node balance trees	578	493	360	9％	500 node balance trees	986	898	600	33％

As can be seen from Table 1, because the present invention adopted the more comprehensive node descriptor of content, therefore, feasiblely the present invention is based on tree generating algorithm that described node descriptor provides and bigger raising is arranged than the time efficiency of prior art.

Description of drawings

Fig. 1 is the tree schematic diagram;

Fig. 2 is the flow chart of method of the present invention.

Embodiment

Core of the present invention is by changing the describing mode of node relationships, the information that is each node comprises the hierarchical information and the nodal information at his father's nodal information, place, thereby makes that the processing procedure that generates SDH transmission equipment veneer passage figure tree based on this is more simple and convenient.

The specific implementation of the method for the invention specifically may further comprise the steps as shown in Figure 2:

Step 21: adopt the breadth First traversal method to travel through each node of each functional block correspondence that each Synchronous Digital Hierarchy SDH transmission equipment veneer comprises, obtain the father node information of each node, the hierarchical information at place, and nodal information, and be called sequence node;

Concrete each information of node can be described in the following ways:

Node Node (i) be expressed as (Pi, Li, Ni);

Wherein:

Ni be (Ti, Bi), 0=＜i＜=n-1, n are number of nodes;

Pi is the father node numbering of i node (being functional block);

Li is the level number at i functional block place, and the level of tree number can be from 0 open numbering;

Ni is the information of i functional block itself;

Ti is the type of i functional block;

Bi is the serial number of i functional block, respectively is numbered the numbering of same type of functionality interblock;

The sequence node that each nodal information of all trees that obtain is formed is:

T＝{Node(0)、Node(1)、......、Node(n-1)}；

With Fig. 1 is example, and each node serial number of tree is followed successively by 0 to 10 by N1 to N11, and corresponding sequence node then is:

{(-1，0，(1，1))、(0，1，(2，1))、(0，1，(2，2))、(0，1，(2，3))、(1，2，(3，1))、(2，2，(4，1))、(2，2，(4，2))、(3，2，(5，1))、(3，2，(5，2))、(5，3，(6，1))、(6，3，(7，1))}。

Step 22: travel through the hierarchical information at described each node father node information, place, and nodal information, determine first node and last node in each level, be called the node layer index;

Still as shown in Figure 1, the node layer index of acquisition is:

{(0，0)，(1，3)，(4，8)，(9，9)，(10，10)}；

The generation processing that with different levels employing recursive fashion is carried out tree be convenient in described node layer index.

Step 23: according to father node information, the hierarchical information at place, the nodal information of described each node, and the information of first node in each level and last node, be that the node layer index carries out computing to each node successively, generate tree;

The processing procedure of described step 23 further comprises:

Step 231: determine current processing node, and generate node instance;

Described node instance comprises node status information, and described state information comprises: wrapped state, professional load indication, passage user mode, cleared alarm number not, and information is counted in alarm unconfirmed;

In this step, when just beginning to generate the computing of tree, then need at first root node afterwards, just can in processing procedure, to determine corresponding current processing node as current processing node.

Step 232:, obtain the information of all nodes of next level of current processing node place level according to the father node information of described each node, hierarchical information and each level node layer index at place;

Step 233: travel through the information of described node, and determine the information of all child nodes of current processing node according to the father node information of described each node;

Step 234: travel through all child nodes of current processing node, be added to the child node of current processing node;

Step 235: judge whether each child node is leaf node, if then execution in step 236, otherwise, execution in step 237;

Step 236: judge whether to exist current processing node,, then determine next current processing node if exist, execution in step 231, otherwise, execution in step 238, promptly process finishes.

Step 237: described child node is set to current processing node, and execution in step 231.

With Fig. 1 is example, is numbered 2 node (0,1, (2,2)) with processing node and for example said process is described:

Because of node serial number is that 2 node is that the N1 node is positioned at the 1st layer (each layer numbering is since 0), thus its down one deck be the 2nd layer, the index that first node of the 2nd layer determining according to the node layer index and last node are determined is (4,8), therefore, search child node in need be in this scope, determine that according to the father node information in this scope corresponding child node has two (2,2, (4,1)), (2,2, (4,2)), to node (2,2, (4,1)), judge to also have child node (5,3, (6,1)), be added to the child node of numbering 2 node, and recurrence handles (2,2, (4,1)).

The above; only for the preferable embodiment of the present invention, but protection scope of the present invention is not limited thereto, and anyly is familiar with those skilled in the art in the technical scope that the present invention discloses; the variation that can expect easily or replacement all should be encompassed within protection scope of the present invention.Therefore, protection scope of the present invention should be as the criterion with the protection range of claims.

Claims

1. A method for generating a tree structure of a communication device, comprising:

A. Adopt the breadth-first traversal method to obtain the parent node information, layer information, and node information of each node corresponding to each functional block included in the communication device, and determine the first node and node in each layer according to the information. the last node;

B. According to the parent node information of each node, the layer information where it is located, the node information, and the first node and last node information in each layer, the nodes in each layer are respectively processed sequentially to generate a communication device tree structure.

2. The method for generating a tree structure of communication equipment according to claim 1, wherein when said communication equipment is a synchronous digital sequence SDH transmission equipment single board, said step A further comprises:

A breadth-first traversal method is used to traverse each node included in each SDH transmission equipment board, and obtain corresponding parent node information, layer information, and node information.

3. The method for generating a tree structure of a communication device according to claim 1 or 2, wherein the node information includes:

The type of node and the number of the node.

4. The method for generating a tree structure of a communication device according to claim 3, wherein said step B further comprises:

B1. Determine the current processing node and generate a node instance;

B2. Obtain information of all child nodes of the current processing node according to the parent node information of each node, the layer information where it is located, and the node indexes of each layer;

B3. Add all the child node information as child nodes of the current processing node.

5. The method for generating a tree structure of a communication device according to claim 4, wherein the node instance includes node status information, and the status information includes:

Loopback status, service loading indication, channel usage status, number of uncleared alarms, and number of unacknowledged alarms.

6. The method for generating a communication device tree structure according to claim 4, characterized in that said step B1 further comprises:

When starting to generate a tree structure, first determine the root node as the current processing node.

7. The method for generating a tree structure of a communication device according to claim 4, wherein said step B2 further comprises:

Obtain the information of all nodes in the next layer of the current processing node;

The information of the nodes is traversed, and the information of all child nodes of the current processing node is determined according to the information of the parent nodes of each node.

8. The method for generating a tree structure of a communication device according to claim 4, wherein said step B3 further comprises:

Step B31, judging whether the child node is a leaf node, if yes, then execute step B32, otherwise, execute step B33;

Step B32, judging whether there is a current processing node, if yes, then determine the next current processing node, and execute step B1, otherwise, end the process;

Step B33. Set the child node as the current processing node, and execute step B1.