Network routing method and apparatus
The present invention discloses a network routing method and apparatus. In the network routing method, for multiple selectable paths corresponding to current service, an average utilization rate of links of a whole network is calculated according to a bandwidth utilization rate of each link before bearing the current service and the number of the links in the whole network, wherein each of the selectable paths includes at least one link; for each link in each of the selectable paths, a bandwidth utilization rate of each link after bearing the current service is calculated; for each link in each of the selectable paths, a link balanced weight for each link is set according to the bandwidth utilization rate of said link after bearing the current service and the average utilization rate of the links of the whole network; and the link balanced weight of each link included in each of the selectable paths is accumulated respectively to obtain accumulated loads, and a path with the minimum accumulated load is selected as a bearing path for bearing the current service. The technical solution according to the present invention can improve the efficiency and realize the balanced load among the links of the whole network.
1. A network routing method, comprising:
for multiple selectable paths corresponding to current service, calculating an average utilization rate of links of a whole network according to a bandwidth utilization rate of each link before bearing the current service and the number of the links in the whole network, wherein each of the selectable paths includes at least one link;
for each link in each of the selectable paths, calculating a bandwidth utilization rate of each link after bearing the current service;
for each link in each of the selectable paths, setting a link balanced weight for each link according to the bandwidth utilization rate of said link after bearing the current service and the average utilization rate of the links of the whole network; and
accumulating the link balanced weight of each link included in each of the selectable paths respectively to obtain accumulated loads, and selecting a path with the minimum accumulated load as a bearing path for bearing the current service.
2. The method according to claim 1 , wherein the bandwidth utilization rate of the link after bearing the current service is calculated according to the following formula:
U
ij
=
{
[
1
(
R
ij
b
)
/
C
ij
]
×
100
b
≤
R
ij
MAX_VALUE
b
>
R
ij
wherein U ij represents the bandwidth utilization rate of the link after bearing the current service; R ij represents a residual bandwidth of the link; C ij represents the maximum bandwidth of the link; b represents a bandwidth requested by the current service; MAX_VALUE represents a predetermined fixed value, wherein R ij , C ij , b and MAX_VALUE are all nonnegative numbers, and MAX_VALUE is an integer more than 100.
3. The method according to claim 1 , wherein the average utilization rate of the links of the whole network is calculated according to the following formula:
U
_
=
[
∑
(
i
,
j
∈
E
)
(
1
R
ij
/
C
ij
)
×
100
]
/
m
wherein Ū represents the average utilization rate of the links of the whole network, m represents the number of the links in the whole network, R ij represents a residual bandwidth of a link, and C ij represents the maximum bandwidth of the link.
4. The method according to claim 3 , wherein the link balanced weight is set according to the following formula:
W
ij
=
{
W
0
(
U
ij
≤
U
0
)
aU
ij
(
U
ij
>
U
0
,
and
U
ij
≤
U
_
)
bU
ij
(
U
ij
>
U
0
,
and
U
ij
>
U
_
)
MAX_VALUE
(
U
ij
>
100
)
wherein W ij represents the link balanced weight, U 0 represents an initial threshold of the link bandwidth utilization rate of a link bearing the current service, W 0 represents a predetermined initial value of the link balanced weight, U 0 , W 0 , a and b are all nonnegative numbers, and a >W 0 /U 0 and b>a.
5. The method according to claim 1 , wherein if the current service is the first service accessed after a network is initialized, the average utilization rate of the links of the whole network is 0.
6. A network routing apparatus, comprising:
a first calculation unit, adapted to calculate an average utilization rate of links of a whole network according to a bandwidth utilization rate of each link before bearing current service of multiple selectable paths corresponding to the current service and the number of the links;
a second calculation unit, adapted to calculate a bandwidth utilization rate of each link after bearing the current service;
a third calculation unit, adapted to calculate a link balanced weight for each link according to the bandwidth utilization rate of the link after bearing the current service and the average utilization rate of the links of the whole network;
an accumulator, adapted to accumulate the link balanced weight of each link included in each of the selectable paths to obtain accumulated loads; and
a path selection unit, adapted to select a path with the minimum accumulated load as a bearing path for bearing the current service.
7. The apparatus according to claim 6 , wherein the first calculation unit comprises:
a first operator, adapted to calculate and output the bandwidth utilization rate of the link before bearing the current service according to a residual bandwidth R ij of the link and the maximum bandwidth C ij of the link;
a weight unit, connected with the first operator, adapted to accumulate the output of the first operator and output the accumulated result; and
a divider, connected with the weight unit, adapted to perform a division operation on the output of the weight unit and the number of the links included in the multiple selectable paths, and take the output result of the division operation as the average utilization rate Ū of the links of the whole network.
8. The apparatus according to claim 6 , wherein the second calculation unit comprises:
a first comparator, adapted to compare a bandwidth b requested by the current service with the residual bandwidth R ij of the link;
a second operator, connected with the first comparator, adapted to perform an calculation according to the residual bandwidth R ij of the link, the bandwidth b requested by the current service and the maximum bandwidth C ij of the link when the output of the first comparator is b≦R ij , so as to obtain the bandwidth utilization rate of the link after bearing the current service;
a first value assignment unit, connected with the first comparator, adapted to take a predetermined fixed value MAX_VALUE as the bandwidth utilization rate of the link after bearing the current service when the output of the first comparator is b>R ij ; and
a dispatch unit, adapted to dispatch the second operator and the first value assignment unit according to the output of the first comparator.
9. The apparatus according to claim 8 , wherein the third calculation unit comprises:
a second comparator, adapted to respectively compare a current link bandwidth utilization rate U ij with a predetermined initial threshold of the link bandwidth utilization rate U 0 , the average utilization rate Ū of the links of the whole network, or a value 100;
a multiplier, connected with the second comparator and adapted to perform a multiplication operation on a value of a or the b and the current link bandwidth utilization rate U ij according to the output of the second comparator, and take the output result as the link balanced weight; and
a second value assignment unit, connected with the second comparator and adapted to output the result of the second comparator, output an initial threshold W 0 of the link balanced weight or the MAX_VALUE, and take the output result of the multiplier, or the W 0 , or the MAX-VALUE as the link balanced weight W ij .
10. The method according to claim 2 , wherein the average utilization rate of the links of the whole network is calculated according to the following formula:
U
_
=
[
∑
(
i
,
j
∈
E
)
(
1
R
ij
/
C
ij
)
×
100
]
/
m
wherein Ū represents the average utilization rate of the links of the whole network, m represents the number of the links in the whole network, R ij represents a residual bandwidth of a link, and C ij represents the maximum bandwidth of the link.
11. The method according to claim 10 , wherein the link balanced weight is set according to the following formula:
W
ij
=
{
W
0
(
U
ij
≤
U
0
)
aU
ij
(
U
ij
>
U
0
,
and
U
ij
≤
U
_
)
bU
ij
(
U
ij
>
U
0
,
and
U
ij
>
U
_
)
MAX_VALUE
(
U
ij
>
100
)
wherein W ij represents the link balanced weight, U 0 represents an initial threshold of the link bandwidth utilization rate of a link bearing the current service, W 0 represents a predetermined initial value of the link balanced weight, U 0 , W 0 , a and b are all nonnegative numbers, and a>W 0 /U 0 and b>a.
12. The apparatus according to claim 7 , wherein the second calculation unit comprises:
a first comparator, adapted to compare a bandwidth b requested by the current service with the residual bandwidth R ij of the link;
a second operator, connected with the first comparator, adapted to perform an calculation according to the residual bandwidth R ij of the link, the bandwidth b requested by the current service and the maximum bandwidth C ij of the link when the output of the first comparator is b≦R ij , so as to obtain the bandwidth utilization rate of the link after bearing the current service;
a first value assignment unit, connected with the first comparator, adapted to take a predetermined fixed value MAX_VALUE as the bandwidth utilization rate of the link after bearing the current service when the output of the first comparator is b>R ij ; and
a dispatch unit, adapted to dispatch the second operator and the first value assignment unit according to the output of the first comparator.
13. The apparatus according to claim 12 , wherein the third calculation unit comprises:
a second comparator, adapted to respectively compare a current link bandwidth utilization rate U ij with a predetermined initial threshold of the link bandwidth utilization rate U 0 , the average utilization rate Ū of the links of the whole network, or a value 100;
a multiplier, connected with the second comparator and adapted to perform a multiplication operation on a value of a or the b and the current link bandwidth utilization rate U ij according to the output of the second comparator, and take the output result as the link balanced weight; and
a second value assignment unit, connected with the second comparator and adapted to output the result of the second comparator, output an initial threshold W 0 of the link balanced weight or the MAX_VALUE, and take the output result of the multiplier, or the W 0 , or the MAX-VALUE as the link balanced weight W ij .