Routing protocols review Open Shortest Path First

www.ietdl.org

IE

d

Published in IET Networks Received on 20th December 2012 Revised on 16th July 2013 Accepted on 21st August 2013 doi: 10.1049/iet-net.2012.0226

T Netw., 2014, Vol. 3, Iss. 2, pp. 143–149 oi: 10.1049/iet-net.2012.0226

ISSN 2047-4954

Preventive start-time optimisation of open shortest path first link weights for hose model Ravindra Sandaruwan Ranaweera1, Islam Mohammad Kamrul1,2, Eiji Oki1

1 Department of Communication Engineering and Informatics, The University of Electro-Communications, Tokyo, Japan

2 Computer Science and Engineering Department, University of Asia Pacific, Dhaka, Bangladesh

E-mail: [email protected]

Abstract: Optimising link weights in an open shortest path first network is a challenging traffic engineering problem to reduce network congestion. Most of the previous studies have focused on the application of start-time optimisation (SO) and run-time optimisation on both pipe and hose models of link weight optimisation. In a more recent study, an efficient policy, preventive start-time optimisation (PSO), has been introduced for link weight optimisation. However, no studies have been reported on the application of PSO to the hose model where the exact traffic demand between each source and destination node pair does not need to be specified. A PSO policy for the hose model to optimise the link weights against link failures is proposed. The proposed scheme employs a heuristic algorithm to determine a suitable set of link weights to reduce worst-case congestion for any single link failure. It efficiently selects the worst-case performance traffic matrix and reduces the worst-case congestion ratio as compared with a brute-force scheme which is computationally expensive when searching the link weight space against all the possible traffic matrices and topologies created by single link failures. The numerical results show that the proposed scheme is more effective in the reduction of worst-case congestion ratio than the scheme utilising SO.

1 Introduction

Emerging Internet applications such as voice-over-Internet protocol (VoIP), teleconferences and multi-party games are adversely affected if rerouting of the data packets occurs because of failures caused by optical fibre cuts, maintenance windows, router reboots, and so on [1–3]. Present traffic engineering methods, which are used to optimise link weights, need to recalculate a set of optimal link weights if network failures such as link failures occur. Open shortest path first (OSPF) [4] is widely used as a

link-state-based interior gateway protocol (IGP) for Internet protocol (IP) networks. OSPF gathers link state information from the available routers and constructs a topology graph of the network. To route packets, the OSPF computes the shortest path tree for each router. The OSPF also requires weights for each link in the network in order to determine the shortest paths. Each router in the network sends link state messages containing link weights to all the other routers in the same network so that each router can compute the routing table to store routing data. If the link weights are not suitable, network traffic may concentrate to one link and may increase the congestion ratio of the network. Determining a set of optimal link weights means determining the optimal routing based on the shortest path routing. The general objective of optimal routing is to distribute the traffic using the available network resources in order to avoid network congestion. Start-time optimisation (SO) determines a set of optimal

link weights only when the network topology and traffic

matrix are given at the beginning of network operation. However, the SO is not able to cope with the network topology changes caused by network failures, such as link failures. Whenever a link failure occurs, each router needs to reroute the data packets in order not to lose any packets, which may lead to unexpected network congestion. The SO considers the link weight assignment problem as a static problem and does not consider dynamic network topology changes at run time. Thus, link failures are considered to be one of the main challenges faced by network operators because link failures occur on a daily basis in large IP backbones [5]. To overcome the weakness of SO, run-time optimisation

(RO) is introduced. RO computes a new optimal set of link weights whenever the network topology is changed. It can be said that the RO provides the best routing performance against link failures. However, updating link weights in any case may not be practical for two reasons. The first reason is that changing link weights frequently causes network instability. To recompute the shortest paths to all the other routers, the updated link weights should be flooded to all the routers in the network. As a result, the performance of transport control protocol (TCP) connections may be degraded because of the arrival of packets in disorder [6]. The network will take a longer time to achieve stability if the link weights are updated often, because packets are sent back and forth between the routers because of frequent updates to the routing table. The second reason lies in the short-lived nature of most link failures. As mentioned in [5], 80% of the link failures in their tested networks last

143 & The Institution of Engineering and Technology 2014

www.ietdl.org

less than 10 min, and 50% of the link failures last less than one minute. Also, it shows that 70% of the link failures that last less than 10 min are single link failures. Based on the two reasons above, updating link weights is considered to be impractical. Kamrul et al. [7–9] introduced a link weight optimisation

policy called preventive start-time optimisation (PSO) where the traffic matrix is exactly known. This traffic model is called a pipe model. The pipe model requires the specification of the bandwidth requirement between any two nodes known as the traffic matrix of the network. However, it is difficult for the network operators to measure or predict the actual traffic requirement from each node to all the other nodes. How to implement the PSO when the traffic matrix is not exactly known is not discussed in [7–9]. Since the prediction of the actual traffic requirement as

required in the pipe model is difficult, it is, therefore considered to be easier for the network operators to specify the traffic as just the total ingress and egress traffic (i.e. the amount of traffic that can be sent to and received from the backbone network) at each node. The traffic model that has achieved this specification is called a hose model. Chu and Lea formulated the general routing problem of the hose model and presented an algorithm for solving the link weight searching problem in [10]. The hose model presents some challenging problems for traffic engineering, as the hose model only needs to specify the total ingress bandwidth requirement and the total egress bandwidth requirement at each node. Chu and Lea [10] presented an algorithm to minimise the weight changes caused by link failures. As explained before, even one link weight change may cause network instability. The PSO policy in [7] has been applied only to the pipe

model, where the traffic matrix is given and all the possible single link failure scenarios are considered. In [10], the traffic matrices are specified by the hose model and link failure is not considered to obtain an optimal link weight set. To apply the PSO policy to the hose model, it is necessary to consider both traffic matrices specified by the hose model and all the possible single link failure scenarios simultaneously. Formulating a mathematical model to solve this problem is possible, where the formulation is described in Section 2, but solving it in practical time range is a challenge. A straightforward approach to find a suitable link weight set is to search the link weight space with regard to all the traffic matrices and the link failure topologies created by single link failure. Naturally, this method considers a larger number of candidates and results in longer computation time. The computation time complexity of this method is O xL

T ( )

, where x is the upper limit of the link weights, L is the number of links in the network and T is the number of traffic matrices. A question arises: Is it possible to calculate a suitable link

weight set for the hose model based on PSO efficiently? To answer this question, this paper proposes an OSPF link weight optimisation scheme that shows how to apply the PSO policy to the hose model. The proposed scheme considers the worst-case traffic matrix and one link failure topology and tries to decrease the congestion ratio by changing link weights. To differentiate the previous work on the pipe model, we call the previous scheme PSO-P and the proposed one PSO-H. PSO-H relaxes the limitation of PSO-P, which can only be used when the traffic matrix is known (as in the pipe model). This paper introduces a heuristic algorithm to obtain a suitable link weight set that

144 & The Institution of Engineering and Technology 2014

reduces the worst-case congestion by using tabu search (TS) [11] and an efficient objective function in the optimisation process to reduce the computation time. Numerical results via simulations support the fact that the PSO-H effectively reduces the worst-case network congestion ratio, as compared with that of SO. The rest of this paper is organised as follows. Section 2

presents the definitions used in this study. Section 3 explains the proposed algorithm while numerical results are shown in Section 4. Finally, Section 5 shows the conclusion of this research.

2 Definitions

The network is described as a directed graph G(V, E), where V is the set of nodes and E is the set of links. v ∈ V, where v = 1, 2, …, N, indicates an individual node and e, where e = 1, 2, …, L, indicates a bidirectional individual link. N is the number of nodes and L is the number of links in the network. As described in [5], the probability of concurrent multiple link failures is much less than that of single link failures. Therefore we consider only single link failure in the network. F is the set of link failure indices l, where l = 0, 1, 2, …, L and F = E ∪ {0}. The number of elements in F is |F| = L + 1. l = 0 indicates no link failure and l( ≠ 0) indicates the failure of link e = l( ≠ 0) because of link failure. Gl denotes G that has no link e = l( ≠ 0) because of link failure. G0 = G as l = 0 indicates no link failure. ce is the capacity of link e ∈ E. The traffic volume on link e is denoted as ue. W = {we} is the link weight matrix of network G, where we is the weight of link e. Let {1, …, wmax} be the set of possible link weights. x

e ij is the portion

of traffic from node i ∈ V to j ∈ V routed through link e. Note that routing and xeij are determined if link weights are

known since an OSPF-based backbone uses the shortest path routing. xeij(W) is used to represent the load distribution variables under link weight set W. Let ai and bi represent the maximum amount of ingress and egress traffic allowed to enter and leave the network at node i, respectively. Given the ingress and egress traffic constraints specified by H = [(a1, b1), …, (an, bn)], there are many traffic matrices that satisfy the constraints imposed by H. A traffic matrix T = {dij}, where dij represents the traffic rate from node i to node j, is called a valid traffic matrix if it does not violate the constraints imposed by H. Let D̃ be the set of all valid Ts. The network congestion ratio r, which refers to the

maximum value of all link utilisation rates in the network is defined as

r = max e[E

ue ce

(1)

where 0 ≤ r ≤ 1. Under the condition that routing is not changed, traffic volume (1 − r/r)dij is the highest traffic volume that can be added to the existing traffic volume of dij for any pair of source node i and destination node j such that the traffic volume passing through any link e does not exceed ce. After adding (1 − r/r)dij to dij, the total traffic volume becomes (1/r)dij. Therefore the updated network congestion ratio becomes 1, which is the upper limit. Maximising the additional traffic volume of (1 − r/r)dij is equivalent to minimising r [12, 13]. The target of this research is to find the most appropriate set

of link weights, Wmin, for network G that minimises the worst-case network congestion ratio over link failure index

IET Netw., 2014, Vol. 3, Iss. 2, pp. 143–149 doi: 10.1049/iet-net.2012.0226

Fig. 2 Example of the proposed scheme after one link weight change

www.ietdl.org

l ∈ F and traffic matrices T [ D̃. Wmin is defined by

Wmin = arg min W[w

max Gl[G̃

max T[D̃

r Gl, T, W ( )

(2)

The traffic matrix T [ D̃ that maximises the congestion ratio against all the single link failure scenarios of Gl [ G̃ is searched followed by the finding of the link weight set that minimises the worst-case congestion ratio.

3 Proposed scheme

3.1 Procedure

The proposed scheme is divided into three stages:

† Stage 1: Generating traffic matrices. † Stage 2: Searching for an optimal link weight set that reduces the worst-case congestion ratio against all the possible single link failure scenarios. † Stage 3: Choosing a link weight set that provides the minimum congestion ratio.

At Stage 1, we generate the traffic matrices that lead to the maximum load appearing on each link e ∈ E in the allowable traffic bound (ai, bi). At Stage 2, we calculate the congestion ratios for all the

traffic matrices against single link failure and find which link failure topology gives the maximum congestion ratio. As shown in Fig. 1, for the first traffic matrix T1, G1 maximises the congestion ratio; for the second traffic matrix T2, G0 maximises the congestion ratio, and so on. Within all of the traffic matrices against single link failure topologies, the traffic matrix that maximises the congestion ratio is chosen. In the example shown in Fig. 1, the second traffic matrix T2 is chosen. Then, we try to reduce that congestion ratio by changing the link weight of the most congested link (w3 in the example). The same topology after one link weight change (link weight set W2) is shown in Fig. 2. At Stage 3, the improvement of the new link weight set is

evaluated. If the link weight set is accepted, the algorithm terminates. If not, it returns to Stage 1.

3.2 Overview of TS

The proposed scheme employs the TS methodology [11]. TS is used for solving optimisation problems in applied sciences,

Fig. 1 Example of the proposed scheme

IET Netw., 2014, Vol. 3, Iss. 2, pp. 143–149 doi: 10.1049/iet-net.2012.0226

business and engineering. There are several studies that use TS, such as [6, 14, 15], and that have verified the usefulness of TS. TS is based on an iterative procedure. It has been applied to a wide range of problems such as job scheduling, graph colouring and network planning. TS is considered as an alternative to techniques such as guided local search and simulated annealing.

3.3 PSO for hose model

The description of PSO-H, which is a TS-based link weight optimisation scheme, is as follows: Stage 1: Generating traffic matrices

† Step 1: Set initial link weights At first, the link weights are generated randomly. Once the

link weights are known, the shortest paths and routing xeij(W) are determined.

† Step 2: Generate traffic matrices For each link e, the following linear programming

formulation is used to find the worst-case traffic matrix Te

that leads to the maximum load appearing on each link e.

max ∑ ij

xeij(W)dij (3a)

s.t ∑ j[V

dij ≤ ai, i [ V (3b)

∑ I[V

dij ≤ bj, j [ V (3c)

dij ≥ 0, i, j [ V (3d)

The traffic matrix Te that achieves the maximum link utilisation for each link e will be added to the set D̃ if it is not in D̃ already. The updated set D̃ produced at Stage 1 is used to search for

new link weights that reduce an objective function. The objective function considerably affects the efficiency of the algorithm. Let r̃ denote the congestion ratio for set D̃. Let rT be the maximum link utilisation ratio for a specific traffic matrix T. Therefore r̃ = maxT[D̃ rT

{ } . Although our goal is

145 & The Institution of Engineering and Technology 2014

www.ietdl.org

to minimise r̃, we find that r̃ is not a suitable objective function in the optimisation process because changing a link weight reduces one rT but also often increases a different rT. This means that the improvement of r̃ cannot be achieved in any iteration. A better objective function, as used in [10], should include

rT for all traffic matrices in D̃. The sum of individual cost function φ(rT) of rT is chosen as the objective function F(D̃) of the proposed scheme. F(D̃) is defined as

F D̃, Gl ( )

|for given weights= max Gl[G̃

∑ T[D̃

f rT ( )

(4)

where φ(rT) increases with rT. Inspired by [10], we adopted the following convex piecewise linear cost function for φ(rT).

f rT ( )

=

rT, 0 ≤ rT , 1

3

3rT − 2

3 ,

1

3 ≤ rT ,

2

3

10rT − 16

3 ,

2

3 ≤ rT ,

9

10

70rT − 178

3 ,

9

10 ≤ rT , 1

500rT − 1468

3 , 1 ≤ rT ,

11

10

5000rT − 16318

3 ,

11

10 ≤ rT , 1

⎛ ⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝

(5)

In [10], it is stated that they have tried different convex objective functions and they all have similar performances in terms of network congestion ratio minimisation. Thus, the proposed scheme also uses the same convex objective function. Stage 2: Searching for an optimal link weight set

† Step 1: Initialise Variable Fmin, which is used to store the value of the

objective function, is set to infinite. The repetition counter Ic, used to stop the oscillation of the objective function, is also set to zero.

† Step 2: Choose a traffic matrix At first, the repetition counter Ic is checked. If it is greater

than the allowed repetition number, go to Step 1 of Stage 3. If not, the traffic matrix Tmax that maximises the cost function defined in (5) against all the single link failure instances is selected.

† Step 3: Find the most congested link By using the traffic matrix Tmax, which was selected in Step

2 of Stage 2, the most congested link, econg, in the network against single link failures is selected.

† Step 4: Update the link weight The link weight of the most congested link, selected in the

previous step is increased by the minimum value that changes at least one route passing through the link for all single link failure scenarios. Therefore the congestion of the most congested link is decreased. The updated link weight set is

146 & The Institution of Engineering and Technology 2014

inserted into the tabu list. If the updated link weight exceeds the upper limit of the feasible link weight, go to Step 1 of Stage 3.

† Step 5: Evaluate the objective function For the updated traffic distribution obtained in Step 4 of

Stage 2, the objective function of (4) is calculated and compared with that of the old weight set. If the value of (4) for the new weight set is greater than that of the old weight set, repetition counter Ic is reset to zero and the new weight set is set as Wmin and go to Step 2 of Stage 2. Otherwise, repetition counter Ic is increased by one and go to Step 2 of Stage 2. Stage 3: Choosing an optimal link weight set

† Step 1: The congestion ratio r for Wmin is calculated and, if r differs from r̃ by a predefined ε, the algorithm terminates. If not, go to Step 2 of Stage 1 and start from the calculation of traffic matrices. Wmin is an optimal link weight set for the given network against single link failure scenarios.

Since the traffic matrices play an important role in the effectiveness of the proposed method, we randomly use a significantly large number of independent initial link weight sets. The link weight set that gives the minimum congestion ratio against single link failure is selected as an optimal link weight set. The pseudo code of PSO-H is described below, see Fig. 3.

4 Performance evaluation

This study compares the performance of PSO-H with that of SO via simulations. Network congestion ratio r is the performance measure of the evaluation. The simulation models that we used are described as follows. To determine the basic characteristics of the proposed scheme, six sample networks are used as shown in Fig. 4. Networks 1–3 mirror the typical backbone networks used to evaluate the routing performance in both [7, 10]. Network 4 is the Abilene network [16] and Network 5 is the National Science Foundation network [17]. Network 6 is a random network generated using the BRITE topology generator [18] and Waxman’s probability model was used to create it. Table 1 summarises the basic characteristics of the sample networks used. The link capacities of the sample networks were randomly generated with uniform distribution in the range of (10Uc, 100Uc), where Uc [Gbit/s] is given a constant integer value. The maximum link weight, wmax, is set at 100. We confirmed that wmax > 0 provides the same results as wmax = 100 in our examined networks. The values of ai and bi are set to the sum of link capacities of the links connected to node i. Cmax is set to 100, as it needs to exceed the maximum number of links in our examined networks [7]. The simulation program is coded in C language on a Linux computer with 4GB of RAM and an AMD Phenom II X6 processor. The linear programming problem in (3a)–(3d) is solved using the IBM ILOG CPLEX Optimisation Studio 12.4. Let r(l) be denoted as the network congestion ratio for link

failure index l ∈ F. To normalise the calculated network congestion ratios of the sample networks, the congestion ratio of SO without any link failure is used. The normalised network congestion ratio of SO is denoted as rSO(l), the normalised congestion ratio of RO is denoted as rRO(l) and

IET Netw., 2014, Vol. 3, Iss. 2, pp. 143–149 doi: 10.1049/iet-net.2012.0226

Fig. 3 Pseudo code of PSO-H

Fig. 4 Sample networks

Table 1 Characteristics of the sample networks

Network No. of nodes

Average node degree

No. of links (bidirectional)

1 6 3.67 11 2 12 4.00 24 3 15 3.73 28 4 11 2.54 14 5 14 3.00 21 6 20 3.70 37

www.ietdl.org

the normalised congestion ratio of PSO-H is denoted as rPSO– H(l). The worst-case network congestion ratios, maxl∈FrSO(l),

maxl∈FrRO(l) and maxl∈FrPSO-H(l) for the sample networks presented in Fig. 4 for all single link failure scenarios are calculated as shown in Table 2. For the worst-case network

IET Netw., 2014, Vol. 3, Iss. 2, pp. 143–149 doi: 10.1049/iet-net.2012.0226

congestion ratio for single link failure, the following relationship is observed

max l[F

rRO(l) ≤ max l[F

rPSO−H(l) ≤ max l[F

rSO(l) (6)

This indicates that the proposed scheme, PSO-H is able to reduce the worst-case network congestion ratio as compared with SO. It also avoids the run-time link weight changes, which would cause network instability. As expected, RO gives the optimal performance when a link failure occurs even though RO may lead to network instability. The achieved reduction rate of the worst-case congestion ratio, α, is defined as

a = maxl[F rSO(l) − maxl[F rPSO-H(l) maxl[F rSO(l)

(7)

α is also shown in Table 2. The normalised congestion ratios with no link failure are

shown in Table 3. For the case of no link failure

rRO(0) = rSO(0) ≤ rPSO-H(0) (8)

is observed. When there is no link failure, the congestion ratio of the link weight set obtained using PSO-H may be higher than that of SO or RO. This is because the objective of PSO-H is to reduce the worst-case network congestion ratio when link failure occurs. β is the deviation between

147 & The Institution of Engineering and Technology 2014

Table 2 Comparison of worst-case network congestion ratios for single link failure scenarios

Network maxl∈F rSO(l) maxl∈F rRO(l) maxl∈F rPSO-H(l) α

1 1.80 1.10 1.10 0.39 2 1.70 1.30 1.60 0.06 3 2.50 1.40 1.50 0.40 4 1.90 1.10 1.20 0.37 5 1.45 1.00 1.00 0.31 6 3.00 1.90 2.00 0.33

Table 3 Comparison of network congestion ratios with no link failure

Network rSO(0)( = rRO(0)) rPSO-H(0) β

1 1.00 1.00 0.00 2 1.00 1.20 0.20 3 1.00 1.13 0.13 4 1.00 1.48 0.48 5 1.00 1.03 0.03 6 1.00 1.50 0.50

Fig. 5 α’s dependency on number of nodes and adjacency nodes

www.ietdl.org

rPSO-H(0) and rSO(0). β is defined as

b = rPSO-H(0) − rSO(0) rSO(0)

(9)

β is also shown in Table 3. When there is no link failure, β is the ‘penalty’ that PSO-H has to ‘pay’ to reduce the worst-case network congestion. To understand the relationship between the worst-case

congestion ratio and network topology, several random network topologies are used. These random networks are generated using the BRITE [18] Internet topology generator by changing the number of nodes N and the number of adjacency nodes m of the network. Waxman’s probability model is used for interconnecting the nodes of the topology, which is given by

P(u, v) = A exp − d BL

( ) (10)

where 0 < A, B ≤ 1, d is the Euclidean distance from node u to node v and L is the maximum distance between any two nodes. A and B are set to 0.15 and 0.2, respectively. The number of nodes N is set to 8, 10 and 15 and the number of adjacency nodes m is set to 3, 4, 5 and 6. The characteristics of the generated random network topologies are shown in Table 4.

Table 4 Characteristics of the random sample networks

N m Average node degree No. of links (bidirectional)

8 3 4.50 18 8 4 4.75 19 8 5 3.50 14 8 6 3.00 12 10 3 5.60 28 10 4 6.00 30 10 5 6.40 32 10 6 4.80 24 15 3 6.00 45 15 4 7.20 54 15 5 8.53 64 15 6 8.93 67

148 & The Institution of Engineering and Technology 2014

The dependency of α on N and m is shown in Fig. 5. This result shows that α is increasing with N when m is higher (m = 5,6). It means that the difference between the worst-case congestion ratios of SO and PSO-H is increasing. This may

Fig. 6 β’s dependency on number of nodes and adjacency nodes

IET Netw., 2014, Vol. 3, Iss. 2, pp. 143–149 doi: 10.1049/iet-net.2012.0226

Table 5 Comparison of worst-case congestion ratios with different link weight setting schemes

Network Proposed scheme IPC scheme min-hop scheme

1 1.00 1.32 2.00 2 1.00 1.91 1.62 3 1.00 2.43 3.50 4 1.00 3.23 1.12 5 1.00 2.03 2.40 6 1.00 2.61 2.75

www.ietdl.org

relate to the fact that routing flexibility is increased as N and m become higher. Fig. 6 shows the dependency of β against N and m. Fig. 6

indicates that PSO-H is able to achieve the same result as SO for no link failure when the network becomes larger. This may occur because there is a wider number of routes to choose from when the network is larger. To show the effectiveness of the proposed scheme, the

worst-case congestion ratios of the proposed scheme are compared with those of the two following link weight setting schemes. One is a scheme in which a link weight is inversely proportional to its capacity [19]. We call it the IPC scheme. The other scheme is the one in which all the link weights are set to one. As a result, minimum-hop routing is achieved. We call it the min-hop scheme. Table 5 shows the worst-case congestion ratios of the three schemes, which are normalised by that of the proposed scheme. Table 5 indicates that the proposed scheme reduces the worst-case congestion ratio, compared with the IPC scheme and the min-hop scheme. This is because the proposed scheme determines link weights considering any single link failure so as to minimise the worst-case congestion ratio. The numerical results via simulation show that the PSO-H

finds a suitable link weight set to reduce the worst-case network congestion in most cases. It has to pay a penalty of β for no link failure scenario. However, if the network administrators want to reduce the worst-case network congestion ratio for single link failure, PSO-H is a better choice. It is observed that the PSO-H outperforms the SO for larger networks.

5 Conclusions

This paper proposed PSO-H, a preventive start-time optimisation scheme for the hose model inspired by [7]. PSO-H determines a set of link weights that minimises the worst-case network congestion ratio for single link failure scenarios. The proposed scheme overcomes the limitation that the PSO-P can be used only under the condition that the traffic matrix is known. The main objective of this study is to find a link weight set that minimises the worst-case congestion ratio for all the possible single link failure scenarios efficiently. This work introduced a heuristic search algorithm for solving the link weight searching problem based on TS. The effectiveness of the PSO-H was demonstrated through comparison with major link weight optimisation policies, SO and RO. PSO-H only considers single link failure since the

probability of multiple link failures is much less than that of single link failure [5]. The proposed scheme can be applied easily to multiple link failures including shared risk link group (SRLG) failures with extra computation time.

IET Netw., 2014, Vol. 3, Iss. 2, pp. 143–149 doi: 10.1049/iet-net.2012.0226

6 Acknowledgments

This work was supported in part by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Scientific Research (C) 23500081, and the Support Center for Advanced Telecommunications Technology Research (SCAT)

7 References

1 Oki, E., Matsuura, N., Shiomoto, K., Yamanaka, N.: ‘A disjoint path selection scheme with shared risk link groups in GMPLS networks’, IEEE Commun. Lett., 2002, 6, (9), pp. 406–408

2 Tsai, C., Jan, R., Wang, K.: ‘Optimal redundancy allocation for high availability routers’, Int. J. Commun. Syst., 2010, 23, (12), pp. 1581–1599

3 Yahaya, C., Abd Latif, M.S., Mohamed, A.B.: ‘A review of routing strategies for optical burst switched networks’, Int. J. Commun. Syst., 2013, 26, (3), pp. 315–336

4 Moy, J.: ‘OSPF version 2’. IETF RFC 1247, Jul. 1991 5 Iannaccone, G., Chuah, C., Mortier, R., Bhattacharyya, S., Diot, C.:

‘Analysis of link failures in a large IP backbone’. Proc. Second ACM SIGCOM Internet Measurement Workshop, November 2002

6 Fortz, B., Thorup, M.: ‘Optimizing OSPF/IS-IS weights in a changing world’, IEEE J. Sel. Areas Commun., 2002, 20, (4), pp. 756–767

7 Kamrul, I.M., Oki, E.: ‘Optimization of OSPF link weight to minimize worst-case network congestion against single-link failure’. IEEE Int. Conf. Communications, June 2011, pp. 1–5

8 Kamrul, I.M., Oki, E.: ‘PSO: preventive start-time optimization of OSPF link weights to counter network failure’, IEEE Commun. Lett., 2010, 14, (6), pp. 581–583

9 Kamrul, I.M., Oki, E.: ‘Optimization of OSPF link weights to counter network failure’, IEICE Trans. Commun., 2011, E94B, (7), pp. 1964–1972

10 Chu, J., Lea, C.: ‘Optimal link weights for IP-based networks supporting hose-model VPNs’, IEEE/ACM Trans. Netw., 2009, 17, (3), pp. 778–788

11 Glover, F., Laguna, M.: ‘Tabu search’ (Kluwer Academic Publishers, Amsterdam, 1997)

12 Oki, E., Iwaki, A.: ‘F-TPR: Fine two-phase IP routing scheme over shortest paths for hose model’, IEEE Commun. Lett., 2009, 13, (4), pp. 277–279

13 Oki, E., Iwaki, A.: ‘Load-balanced IP routing scheme based on shortest paths in Hose model’, IEEE Trans. Commun., 2010, 58, (7), pp. 2088–2096

14 Fortz, B., Rexford, J., Thorup, M.: ‘Traffic engineering with traditional IP protocols’, IEEE Commun. Mag., 2002, 40, (10), pp. 118–124

15 Nucci, A., Taft, N.: ‘IGP link weight assignment for operational Tier-1 backbones’, IEEE/ACM Trans. Netw., 2007, 15, (4), pp. 789–802

16 ‘The Internet2 Network’, online, http://www.internet2.edu/network/, November 2012

17 Ramaswami, R., Sivarajan, K.N.: ‘Design of logical topologies for wavelength-routed optical networks’, IEEE J. Sel. Areas Commun., 1996, 14, (5), pp. 840–851

18 http://www.cs.bu.edu/brite/, December 2012 19 Cisco: ‘Configuring OSPF’, online, http://www.cisco.com, November

2012

149 & The Institution of Engineering and Technology 2014

Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.