US 8,301,736 B2 · Method for selecting and configuring network supernodes

Abstract

A method for selecting and configuring network supernodes includes (i) in a first set period T1, each node, other than a control node in a network, regularly sending information on interactions between the node and other nodes to the control node; and (ii) in a second set period T2, the control node dividing 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, where each node belonging uniquely to a node cluster.

A method for selecting and configuring network supernodes, comprising:

(1) in a first set period T1, sending, by each node other than a 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;
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 S0,
(22) calculating the cost value CS of the node cluster swarm S0 according to the formula
CS
=
log
*
⁢
n
+
log
*
⁢
k
+
nH
⁡
(
p
)
+
∑
i
=
1
k
⁢
(
log
*
⁢

E
i

+

g
i

⁢
H
⁡
(
g
i
)
)
,
where n is the total number of nodes in the network, k is the number of node clusters in the node cluster swarm S0,log*n and log*k are binary encoding lengths of n and k, respectively, calculated according to the formula
log
*
⁢
x
=
∑
j
=
1
⁢
X
⁡
(
j
)
,
⁢
X
⁡
(
1
)
=
log
2
⁢
x
,
⁢
X
⁡
(
j
+
1
)
=
log
2
⁢
X
⁡
(
j
)
,
⁢
X
⁡
(
j
)
>
0
,
and j is a natural number, nH(p) is the binary encoding length of the node cluster to which each node belongs,
H
⁡
(
p
)
=
-
∑
i
=
1
k
⁢
p
i
⁢
log
2
⁢
p
i
,
⁢
p
i
=
n
i
n
,
ni is the number of nodes in the i-th node cluster gi in the node cluster swarm S0, and pi is a probability that a node belongs to the i-th node cluster gi,|Ei| is the number of pairs of nodes that have interactions with each other in the i-th node cluster gi in the node cluster swarm S0, the value of which depends on the statistics of the actual interaction information in the i-th node cluster gi, and log*|Ei| is the binary encoding length of |Ei|, and |gi|H(gi) is the shortest description of the i-th node cluster gi,

g
i

=
n
i
⁡
(
n
i
-
1
)
2
,
⁢
H
⁡
(
g
i
)
=
-
(
ρ
i
⁢
log
2
⁢
ρ
i
+
(
1
-
ρ
i
)
⁢
log
2
⁡
(
1
-
ρ
i
)
)
,
⁢
ρ
i
=

E
i


g
i

,
if ni=1, log*|Ei|+|gi|H(gi) is 0;
(23) storing the node cluster swarm S0 and the corresponding cost value CS as a node cluster division result,
(24) selecting two node clusters in which inter-cluster interactions take place among the nodes from the node cluster swarm S0, consolidating the two node clusters into a new node cluster to form a new node cluster swarm Si, and calculating the corresponding cost value CSi of the new node cluster swarm Si according to the above formula,
(25) selecting one by one all different new node cluster swarms possibly formed from the node cluster swarm S0 according to the principle of selecting two node clusters in which inter-cluster interactions take place among the nodes for consolidation, calculating the cost values thereof respectively, and selecting the new node cluster swarm corresponding to the minimum cost value to replace the node cluster swarm S0, wherein if there are multiple new node cluster swarms having the same minimum cost value, one of them is selected randomly to replace the node cluster swarm S0,
(26) determining whether a new node cluster swarm can be formed by consolidating node clusters in the node cluster swarm S0 according to the above selection principle after being replaced with the new node cluster swarm corresponding to the minimum cost value, if yes, returning to (23), and otherwise, proceeding to (27),
(27) storing the node cluster swarm S0 and the corresponding cost value CS as a node cluster division result, and
(28) finding by the control node the node cluster swarm S0 corresponding to the minimum cost value from the node cluster division results as the optimal node cluster swarm that is finally selected and selecting supernodes from each node cluster in the optimal node cluster swarm, wherein nodes that have more interactions with other nodes and better performance are selected as supernodes in each node cluster.

212 more elements

Description6,569 words

Summary1,401 words

#The present invention relates to the field of network communication technologies, and particularly to a method for selecting and configuring network supernodes.

#With the development of the Internet technologies, more and more applications have emerged over the Internet. To meet the requirements of the diversified applications, the network distribution technology based on the principle of Peer to Peer (P2P) network has been applied to a great extent. At present, in addition to ordinary network user computers acting as user nodes, control nodes and supernodes also need to be configured in a computer network based on the P2P technology. The control node functions to establish and carry out a control strategy, and control and manage the network through the supernodes. The supernode functions to particularly implement the management and control over the user nodes under the management of the control node.

#In general, the supernode is implemented by a user computer having abundant resources. Therefore, how to select a supernode from numerous user computers and configure the same has become a key task that influences the function of a computer network. The issue regarding how to select and configure a supernode also exists in wireless communication networks.

Brief description of the drawings6 figures

#FIG. 1 is a schematic diagram illustrating the structure of a computer network according to an embodiment of the present invention after supernodes are selected and configured;

#FIG. 2 is a flow chart illustrating the operations of a method for selecting and configuring supernodes according to the present invention;

#FIG. 3 is a flow chart illustrating the operations in which a control node divides nodes into node clusters in a set period and selects supernodes according to the method illustrated in FIG. 2;

Detailed description4,964 words

#The present invention is further described in detail hereinafter with reference to the accompanying drawings and embodiments so as to make the objects, solutions and advantages thereof more apparent.

#Referring to FIG. 1, there shows a schematic diagram illustrating the structure of a computer network according to an embodiment of the present invention after supernodes are selected and configured. Each user computer in the network acts as a node in the network and has a corresponding unique identification (ID), for example, U1, U2, U3, . . . , U16 in the figure. Each node is connected to a server acting as a control node (for example, Z1, Z2, Z3) via the network. The three control nodes Z1, Z2 and Z3 connected with one another divide the nodes into a number of node clusters according to the interactions among the nodes. Each node cluster consists of nodes that have close interactions with one another. The control node selects nodes that have more resources and more interactions with other nodes from each node cluster as supernodes, and the supernode implements control and management over other nodes in the node cluster to which it belongs.

#Referring to FIG. 2, there shows a flow chart illustrating the operations of a method for selecting and configuring supernodes according to the present invention, which includes the following operational steps.

Facts

Application

12/730,866Filed 24 Mar 2010

Priority

CN 2009 1 02500171 Dec 2009

Published

US 2011/0128889 A12 Jun 2011

Granted

30 Oct 2012

Term ends

20 Jan 2031

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 302 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification5 codes

H04L 41/0893
Configuration management of networks or network elements: assignment of logical groups to network elements
H04L 45/04
Topology update or discovery: interdomain routing, e.g. hierarchical routing
H04L 67/1051
Group management mechanisms: group master selection mechanisms
H04L 67/1093
Using cross-functional networking aspects: some peer nodes performing special functions

Timeline

1 Dec 2009Priority claimedCN 2009 1 0250017
24 Mar 2010Application filedUS 12/730,866
24 Mar 2010Assigned to Beijing University of Posts and Telecommunicationsassignment of assignor's interest
2 Jun 2011PublishedUS 2011/0128889 A1
30 Oct 2012GrantedUS 8,301,736 B2
12 Oct 2026TodayWithin its term
20 Jan 2031Term endsEstimated, includes 302 days of adjustment

Method for selecting and configuring network supernodes

Life of this patent

Method for selecting and configuring network supernodes

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims12

Description6,569 words

Drawings

Classification5 codes

Life of this patent

Description6,569 words