Method for Selecting and Configuring Network Supernodes

• US 20110128889A1
• Filed: 03/24/2010
• Published: 06/02/2011
• Est. Priority Date: 12/01/2009
• Status: Active Grant

• Current Assignee: Beijing University of Posts and Telecommunications
• Original Assignee: Beijing University of Posts and Telecommunications
• Inventors: Li, Wei, Wang, Chun, Wang, Jing, Xu, Tong, Cheng, Li, Wan, Li, Zhu, Xiaomin, Liao, Jianxin, Zhang, Lejian, Fan, Limin, Shen, Qiwei, Zhang, Lei
• Granted Patent: US 8,301,736 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 67/1051 Group master selection mechanisms
• CPC Class Codes: H04L 67/1093 Some peer nodes performing special functions

Abstract

A method for selecting and configuring network supernodes including the following operational steps: in a first set period T1, each node other than the control node in a network sends information on interactions between the node and other nodes to the control node regularly; and in a second set period T2, the control node divides the nodes into a plurality of node clusters according to the received information on interactions among the nodes, and selects supernodes from each node cluster, each node belonging uniquely to a node cluster. The supernode selection according to the invention takes into account both performance and resource conditions of itself and interactions with other nodes. Therefore, when implementing control over other nodes in the node cluster to which it belongs, the selected supernode can find the corresponding node in a short time and shorten the searching time and path, thereby improving the working efficiency. Meanwhile, parameters such as the acquiring period of node interaction information, and the division and adjustment periods of node clusters can be adjusted dynamically with the actual interaction conditions of the network.

Claims

1. A method for selecting and configuring network supernodes, comprising:

(1);

in a first set period T1, sending, by each node other than the control node in a network, information on interactions between the node and other nodes in the first set period to the control node regularly; and

(2);

in a second set period T2, dividing, by the control node, the nodes into a plurality of node clusters according to the received information on interactions among the nodes, and selecting supernodes from each node cluster;

wherein

each node belongs uniquely to a node cluster, and the second set period T2 is an integer number of multiples of the first set period T1.

2. The method according to claim 1, wherein in (2), the control node divides the nodes into a plurality of node clusters comprises:

encoding different division results for node clusters possibly formed in the network through lossless compression; and

selecting the division result that has the shortest encoding length as the optimal division result.

3. The method according to claim 1, wherein (2) comprises:

(21) making by the control node each node in the network be a respective node cluster independently to initially form a node cluster swarm S₀;

(22) calculating the cost value CS of the node cluster swarm S₀ according to the formula;

4. The method according to claim 3, wherein in the new node cluster swarm S_i corresponding to the minimum cost value selected in (26), close interactions take place among the nodes in the same node cluster, and little or even no interactions take place among the nodes in different node clusters;

and

once the control node finds the node cluster swarm S₀ corresponding to the minimum cost value from the node cluster division results as the optimal node cluster swarm, it indicates that all the non-control nodes have been divided in the optimal way according to the interactions among the nodes.

5. The method according to claim 3, wherein the performance of a node mentioned in (28) is indicated by at least one of the following parameters CPU frequency and memory capacity, transmission width, delay, online time, total traffic with other nodes per minute, average CPU utilization ratio and average memory utilization ratio during a predetermined period of time.

6. The method according to claim 3, wherein when calculating the number of interactions between a node and other nodes mentioned in (28), the number of control interactions between the node and the original supernodes is excluded.

7. The method according to claim 1, wherein durations of the two set periods T2 and T1 are adjusted dynamically separately according to actual conditions of the interactions among the nodes in the network to avoid an increase in traffic of the network when the periods are set too short and avoid that the interaction change among the nodes cannot be reflected in time when the periods are set too long.

8. The method according to claim 7, wherein durations of the two set periods T2 and T1 are adjusted dynamically based on shortest description principle, comprising:

dividing node clusters in two optimal node cluster swarms at adjacent points of time into dynamic groups to form different dynamic group swarms possibly;

taking the division result corresponding to the shortest binary encoding length as the optimal dynamic group swarm;

determining whether change tendencies of the node clusters in the dynamic groups of the optimal dynamic group swarm are consistent with each other at adjacent points of time;

if yes, it is indicated that the change is smaller and the two set periods T2 and T1 are prolonged properly, and otherwise, the two set periods T2 and T1 are shortened properly.

9. The method according to claim 7, wherein durations of the two set periods T2 and T1 are adjusted by the following steps:

A;

selecting by the control node two optimal node cluster swarms S01 and S02 at two adjacent points of time which differs from each other by only one of the second set period T2, respectively, wherein S01 is the optimal node cluster swarm at an earlier point of time and S02 is the optimal node cluster swarm at a later point of time;

B;

according to node overlap conditions of the two optimal node cluster swarms S01 and S02 at the adjacent points of time, dividing by the control node the node clusters included in the optimal node cluster swarms S01 and S02 into a plurality of dynamic groups based on the principle of shortest description, wherein each node cluster belonging uniquely to a dynamic group, and all the dynamic groups form the optimal dynamic group swarm; and

C;

calculating by the control node the average updating period of the optimal dynamic group swarm and updates the two set periods T2 and T1.

10. The method according to claim 9, wherein B comprises:

(B1) making, by the control node, each node cluster in the optimal node cluster swarms S01 and S02 be a respective dynamic group independently to initially form a dynamic group swarm D₀;

(B2) calculating the cost value CD of the dynamic group swarm D₀ according to the formula;

11. The method according to claim 9, wherein step C comprises:

(C1) selecting arbitrarily a dynamic group di from the optimal dynamic group swarm that is finally selected;

(C2) determining whether the dynamic group di is in a holding state according to node overlap conditions of node clusters at adjacent points of time included in the dynamic group di;

if yes, setting the updating period of the dynamic group di as 2×

T2, and otherwise, setting the updating period of the dynamic group di as T2;

(C3) determining whether all dynamic groups di have been selected from the optimal dynamic group swarm and whether the above operations have been performed thereon;

if yes, proceeding to (C4), and otherwise, selecting an unselected dynamic group di from the optimal dynamic group swarm and returning to (C2);

(C4) calculating the average updating period of the optimal dynamic group swarm from the updating periods of all the dynamic groups; and

(C5) adjusting values of the two set periods T1 and T2 according to the average updating period L of the optimal dynamic group swarm;

if L<

2×

T2, the period T2 is shortened; and

otherwise, the period T2 is lengthened; and

updating the first set period T1 according to the relationship between T2 and T1 that T2 is an integral multiple of T1.

12. The method according to claim 11, wherein determining whether the dynamic group di is in a holding state in (C2) comprises:

(C21) calculating the maximum number of overlapping nodes between the node clusters at the earlier point of time and those at the later point of time in the dynamic group di;

(C22) calculating a first ratio B1 of maximum number of overlapping nodes for the node clusters at the earlier point of time in the dynamic group di, wherein the first ratio B1 is a quotient obtained by dividing the maximum number of overlapping nodes by the total number of nodes in the node clusters at the earlier point of time in the dynamic group di;

(C23) calculating a second ratio B2 of maximum number of overlapping nodes for the node clusters at the later point of time in the dynamic group di, wherein the second ratio B2 is a quotient obtained by dividing the maximum number of overlapping nodes by the total number of nodes in the node clusters at the later point of time in the dynamic group di; and

(C24) determining to whether both of B1 and B2 are greater than a threshold;

if yes, it is indicated that the dynamic group di is in a holding state, and the updating period thereof is set to be 2×

T2, and otherwise, it is indicated that the dynamic group di is in a changing state, and the updating period thereof is set to be T2, wherein the threshold is a real number selected from an interval [0,1] as required by the system.

13. The method according to claim 11, wherein the period T2 is shortened in (C5), the period T2 is calculated based on the following formula:

T2=φ

×

T2, where φ

is a real number selected from an interval [0,1]; and

when the period T2 is lengthened, the period T2 is calculated based on the following formula;

T2=τ

×

T2, where τ

is a real number larger than 1.