Method for routing and load balancing in communication networks
View Patent ↗The invention concerns a method of configuring the topology of a communication network comprising a plurality of nodes (i,j, . . . , N), the communication network being organized as a forest structure comprising trees and subtrees, wherein at least one node i maintains a periodic timer and an expiration of the timer of the node i triggers the steps of: searching, by the node i, a parent node; selecting, by the node i, a parent node using at least throughput and subtree size as selection criteria; and migrating the node i to the selected size as selection criteria; and migrating the node i to the selected parent node along with its subtree size. Preferably, the step of selecting a parent node by the node i comprises a sub-step of executing a function having as parameters respective subtree sizes of a node j before and after the migration of the node i to another node k.
1. A method of configuring the topology of a communication network of mesh network type comprising a plurality of nodes (i,j, . . . , N), said communication network being organized as a forest structure comprising trees and subtrees, at least one node i maintaining a periodic timer and an expiration of said timer of said node i triggering the steps of:
searching, by said node i, a parent node;
selecting, by said node i, the parent node using at least throughput and subtree size as selection criteria;
wherein an expiration of said timer of said node i also triggers the step of:
migrating said node i to the selected parent node along with its subtree size and, the step of selecting the parent node by said node i is performed by using a routing metric referred to as the Expected Throughput ETP defined as:
1
ETP
l
i
=
1
P
l
i
·
∑
j
∈
ℳ
1
{
l
i
Δ
l
j
}
R
l
j
(
1
)
M being the set of nodes, the indicator function 1 {l i Δl j } being one if links l i and l j contend with each other and zero otherwise P l i being the probability that a packet transmission on link l i is successful and R l j being the nominal bit rate of link l j .
2. The method of configuring the topology of a communication network of mesh network type according to claim 1 wherein the step of selecting the parent node by said node i comprises a sub-step of executing a function having as parameters respective subtree sizes of a node j before and after the migration of said node i to another node k.
3. The method of configuring the topology of a communication network of mesh network type according to claim 1 , comprising a step of, for each node k εS i , where S i is the set of candidate parent nodes of the node i, forming set H ik , which is the set of nodes that are affected if the node i migrates to node k.
4. The method of configuring the topology of a communication network of mesh network type according to claim 1 , comprising the step of computing the following quantity:
Δ
ik
=
∑
j
∈
ℋ
ik
{
T
j
′
2
ETP
l
j
′
-
T
j
2
ETP
l
j
}
,
where |T j | and |T′ j | are the respective subtree sizes, while ETP l j and ETP′ l i are the respective ETPs of node j before and after the migration of node i to node k.
5. The method of configuring the topology of a communication network of mesh network type according to claim 4 wherein a potential parent is F′ i , which results in a reduction of the function:
F′ i =argmin kεS i Δ ik .
6. The method of configuring the topology of a communication network of mesh network type according to claim 5 wherein the migration to F′ i is performed if F′ i ≠F i , where F i is the initial parent.
7. The method of configuring the topology of a communication network of mesh network type according to claim 1 wherein the computing steps that are necessary for the node i to select the parent node are distributed among different nodes.