Information Technology Reference
In-Depth Information
4 Modeling Results
In this section we evaluate and compare restoration times and network resource utili-
zation ratio obtained by both ILP and heuristic algorithm for the NSF network, shown
in Fig. 2 We also modeled the U.S. Long-Distance Network [7], shown in Fig. 3, but,
due to the size of the network, we applied only the heuristic algorithm.
26
0
25
3
5
8
9
27
14
2
22
23
10
13
13
11
1
10
8
12
6
4
24
4
7
16
14
5
1
11
2
9
19
3
6
17
7
12
20
18
15
21
Fig. 2.
NSF network
Fig. 3.
U.S. Long-Distance Network
For each of the examined network, in each experiment, 30 logical topologies were
generated. Each topology was determined by a graph having a fixed number of ran-
domly chosen source-destination pairs of nodes. After establishing connections in
each logical topology, single node failures were randomly generated. We assumed
equal channel capacity and the same number of channels available in each link. For
each connection we assumed protection against a single node failure, the distance
metrics and no resource optimization in channel capacity allocation. Each demand of
resource allocation was equal to the one channel capacity.
4.1 Accuracy of Heuristic Algorithm
We modeled the path protection in the NSF network to check the accuracy of our
heuristic algorithm. Network resource utilization ratio per connection obtained with
help of CPLEX program and our algorithm for 4-8 channels per link and 8 and 12
demands is shown in Table 1. Fig. 4 illustrates the rate of additional resource utiliza-
tion ratio, obtained with help of heuristic algorithm, compared to the optimal results
of CPLEX. Results prove that the heuristic algorithm is nearly as efficient as the op-
timal ILP approach. In particular, when increasing the number of available channels
per link, the results for the heuristic approach tend to differ very little from the
analogical ones for the ILP formulations.
Table 1.
Network resource utilization ratio per one connection
number of demands per logical topology 8 12
number of channels per link 4 5 6 7 8 4 5 6 7 8
(CPLEX) 3,62 2,90 2,42 2,07 1,81 3,58 2,88 2,42 2,07 1,82
resource utilization per
connection [%]
(heuristics) 3,70 2,93 2,44 2,09 1,83 3,72 2,97 2,45 2,09 1,83
(CPLEX) 0,13 0,10 0,08 0,07 0,01 0,11 0,07 0,05 0,04 0,04
95% confidence interval [%]
(heuristics) 0,15 0,12 0,09 0,07 0,01 0,14 0,09 0,06 0,05 0,04
