Abstract
The open shortest path first (OSPF) routing protocol is a well-known approach for routing packets from a source node to a destination node. The protocol assigns weights (or costs) to the links of a network. These weights are used to determine the shortest paths between all sources to all destination nodes. Assignment of these weights to the links is classified as an NP-hard problem. The aim behind the solution to the OSPF weight setting problem is to obtain optimized routing paths to enhance the utilization of the network. This paper formulates the above problem as a multi-objective optimization problem. The optimization metrics are maximum utilization, number of congested links, and number of unused links. These metrics are conflicting in nature, which motivates the use of fuzzy logic to be employed as a tool to aggregate these metrics into a scalar cost function. This scalar cost function is then optimized using a fuzzy particle swarm optimization (FPSO) algorithm developed in this paper. A modified variant of the proposed PSO, namely, fuzzy evolutionary PSO (FEPSO), is also developed. FEPSO incorporates the characteristics of the simulated evolution heuristic into FPSO. Experimentation is done using 12 test cases reported in literature. These test cases consist of 50 and 100 nodes, with the number of arcs ranging from 148 to 503. Empirical results have been obtained and analyzed for different values of FPSO parameters. Results also suggest that FEPSO outperformed FPSO in terms of quality of solution by achieving improvements between 7 and 31 %. Furthermore, comparison of FEPSO with various other algorithms such as Pareto-dominance PSO, weighted aggregation PSO, NSGA-II, simulated evolution, and simulated annealing algorithms revealed that FEPSO performed better than all of them by achieving best results for two or all three objectives.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Introduction
The use of web based applications has resulted in rapid increase of internet traffic [1]. Efficient utilization of network resources, such as network bandwidth, is essential to deal with this high volume of traffic. The main objective of network traffic engineering is efficient mapping of traffic on the available network resources to prevent traffic imbalance, if it exists [2].
Routers serve as the main interconnection points of the internet and forward data packets between source and destination nodes via multiple paths. These paths exist between a given source and destination pair. The internet is huge and very complex and is divided into autonomous systems (AS) for managing its complexity. An AS represents a collection of networks under the control of one single entity or organization with a specific routing policy. These policies are determined by a class of routing protocols, namely, interior gateway protocols (IGPs) [3]. Routing across ASs is performed by another class of protocols, namely, exterior gateway protocols (EGPs) [3].
Open shortest path first (OSPF) [3] is an IGP and has received notable attention by researchers for efficient traffic engineering since OSPF is considered the best backbone routing protocol used in the internet [4, 5]. The protocol has shown remarkable performance through significant reduction in maximum utilization over pure shortest path routing [6]. OSPF is based on Dijkstra’s algorithm [7], which determines a shortest path between a source and destination pair. Each link in the network is given a measurable entity called a link weight or OSPF weight. The cost of a path between a given source and destination pair is found by the summation of OSPF weights on the links in that path. The path with minimal cost is labelled as the shortest path.
This paper considers the open shortest path first weight setting (OSPFWS) problem, classified as an NP-hard problem [8]. The OSPFWS problem requires a set of weights to be determined, so as to efficiently utilize network resources. The objectives of this problem are to minimize maximum utilization, minimize the number of congested links, and to minimize the number of unused links. These objectives conflict with each other, i.e. if one objective is improved, at least one of the other objectives may deteriorate. To address this NP-hard problem with conflicting objectives, this paper proposes to apply a fuzzy particle swarm optimization (FPSO) algorithm. The paper also proposes a hybrid PSO, namely, fuzzy evolutionary PSO, where characteristics of simulated evolution algorithm [9] are combined with the fuzzy PSO. The performance of these two variants is empirically assessed and compared.
The rest of the paper is organized as follows: Section 2 provides the necessary background and related work on the OSPFWS problem. Section 3 provides the formal definition of the OSPFWS problem. A brief discussion on fuzzy logic and the Unified And-OR operator is given in Section 4. Section 5 describes the formulation of a fuzzy logic based objective function for the OSPFWS problem. Section 6 presents the proposed fuzzy PSO algorithm, and a variant of the fuzzy PSO, the fuzzy evolutionary PSO, is proposed and discussed in Section 7. The experimental methodology is described in Section 8. Results are provided and discussed in Section 9. A comparative analysis of the fuzzy evolutionary PSO with other algorithms, namely, Pareto-dominance PSO, weighted aggregation PSO, NSGA-II, simulated evolution, and simulated annealing is provided in Section 10. The paper is concluded in Section 11. Finally, the symbols and terminology used in this paper are given in Appendix A. Some additional results related to the analysis of swarm size (discussed in Section 9) are provided in Appendix B.
2 Literature review
Notable research in optimizing OSPF weights has been reported in the literature [2, 4, 6, 10–28]. The pioneering work on the OPSF weight setting problem was done by Fortz and Thorup [8, 10, 29] who used maximum utilization as the optimization objective. The term “maximum utilization” refers to the maximum of all utilization values over all the links in the network. A cost function based on utilization ranges was first formulated by Fortz and Thorup [2], who applied tabu search [30] to minimize “maximum utilization”.
The cost function of Fortz and Thorup was formally defined as
subject to the constraints:
where Φ is the cost function, Φ a is the cost associated with arc a, l a is the total traffic load on arc a, \(f^{(s,t)}_{a}\) represents traffic flow from node s to t over arc a, N defines the set of nodes, and A represents the set of arcs. Equation (2) indicates that the total load (traffic) on arc a is equal to the sum of the traffic load on arc a and the traffic load on all incoming arcs to arc a. The constraint in (3) implies that the traffic flow from node s to t over arc a can be greater than or equal to zero.
In (1), Φ a represents piecewise linear functions, with Φ a (0)=0 and a derivative, \( {\Phi }_{a}^{\prime }(l_{a})\) given by
The above function indicates that the utilization (which represents the load to capacity ratio) of a link is acceptable within 100 % of the link’s capacity. According to the function in (4), links with utilization levels less than or equal to 1 (or 100 %) have a low cost, proportional to the level of utilization. These values are 1, 3, 10, or 70. Furthermore, links exceeding 100 % utilization are assigned high costs of 500 and 5000. For example, if utilization is less than one third of a link’s capacity, then a cost of 1 is assigned. For utilization between 1/3 and 2/3 of a link’s capacity, a cost of 3 is assigned, and so on. On the other hand, if the utilization of a link is beyond 1 (which indicates that the number of incoming packets to a link exceed the maximum capacity of the link) then such an over-utilization is not desirable, since it will result in packet loss. Therefore, the cost assigned to the links beyond 100 % utilization is much higher (i.e. 500 for utilization of equal to or more than 100 % but less than 110 %, and 5000 for more than 110 %). Note that as per (4), a link with utilization greater than 100 % and less than 110 % is still preferable compared to a link with utilization greater than 110 %. Fortz and Thorup employed a dynamic shortest path algorithm [31–33] to obtain multiple equidistant shortest paths between a source-destination pair. By this mechanism, traffic load was distributed equally across the links.
Subsequent to the work of Fortz and Thorup, many other researchers attempted to solve the OSPF weight setting problem with different algorithms and different objective functions. Ramakrishnan and Rodrigues [12] proposed a local search procedure using the same cost function as that of Fortz and Thorup. The main difference between the two approaches was that for a heavily used link, Rodrigues and Ramakrishnan’s technique increases the link metric (i.e. the OSPF weight assigned to a link). Ericsson et al. [13] developed a genetic algorithm [34] to solve the OSPFWS problem also using the cost function by Fortz and Thorup. Kandula et al. [6] compared the performance of three OSPF weight optimizers while considering maximum link utilization as the optimization objective. Bhagat [4] also assumed link utilization as weights and used a genetic algorithm for OSPF weight setting while using the cost model of Fortz and Thorup with a minor modification. Abo Ghazala et al. [35] performed a survey of various algorithms applied to the OSPFWS problem, and also proposed a technique based on iterative local search, while considering link utilization as the optimization objective. The underlying cost function was the same as proposed by Fortz and Thorup. In a subsequent research article, Aboghazala et al. [15] assumed maximization of unused bandwidth as the optimization objective and employed simulated annealing and hybrid genetic algorithms for weight optimization. Parmar et al. [16] formulated the OSPF weight setting problem as mixed-integer linear programming problem and developed a branch-and-cut algorithm while assuming minimization of network congestion as the optimization objective. Pioro et al. [22] considered the maximum load on any link in the network as the measure of congestion and proposed two heuristic approaches for weight setting. Srivastava et al. [17] also considered minimization of maximum load on any link and proposed heuristic algorithms based on Lagrangian relaxation to determine feasible solutions for the weight setting problem. Buriol et al. [18] extended the genetic algorithm proposed in [13] to a memetic algorithm by adding a local search procedure while using the same cost function as that of Fortz and Thorup. Bley [19, 20] proposed unsplittable shortest path routing (UPSR) and claimed that the proposed approach can be applied to other routing schemes such as OSPF, while considering minimization of maximum congestion over all arcs. Zagozdzon et al. [14] proposed a two-phase algorithm for resolving the OSPF weight setting problem while considering the residual capacity as the optimization objective. This residual capacity resulted from setting the link weights proportional to the inverse of their capacity. Reis et al. [36] proposed a memetic algorithm for weight setting in OSPF and DEFT algorithms while considering minimization of total link utilization. Lin and Gen [21] proposed a priority-based genetic algorithm for shortest path routing in OSPF. Their results indicated that the proposed GA could be used for weight setting in OSPF and other routing algorithms. Retvari et al. [23, 24] studied the OSPF weight setting problem considering maximization of network throughput and proposed some algorithms that could efficiently optimize the link weights. Nucci et al. [25] proposed a Tabu-search heuristic for choosing link weights that takes into account both service level agreement (SLA) requirements and link failures with the objective of optimization link utilizations. Shirmali et al. [26] devised an approach based on Nash bargaining and decomposition. It was claimed that the proposed approach could be easily modified to yield a mechanism for setting link weights for ISPs using OSPF in a way similar to that of Fortz and Thorup. Riedl [27] presented an algorithm based on simulated annealing to optimize link metrics in OSPF networks. The algorithm took into account the original routing configuration and allowed tradeoff considerations between routing optimality and adaptation impact. Lee et al. [28] modelled the optimal link weight assignment problem as an integer linear programming problem while considering minimization of sum of energy consumption of all links.
It is noteworthy of mentioning that, generally, the aforementioned approaches considered a single objective in the optimization process. For example, the cost function proposed by Fortz and Thorup (1) on which many subsequent attempts were based [4, 12, 13, 18, 26, 35, 37] considered minimization of maximum link utilization. Other researchers [6, 17, 22] also assumed minimization of maximum link utilization. Other objectives considered in the optimization process were maximization of unused link bandwidth [15], minimization of network congestion [16, 19, 20], residual capacity of link [14], minimization of total link utilization [36], maximization of network throughput [23, 24], and minimization of sum of energy consumption of all links [28]. Exceptions from these single-objectives optimization approaches were Nucci et al. [25] where link failure and link no-failure states were used as the optimization objectives, and Sqalli et al. [11, 38] who used minimization of maximum link utilization as well as minimization of congested links as the optimization objectives while using a simulated annealing (SA) algorithm [39].
A cost function developed by Sqalli et al. [11, 38] evolved from the earlier work by Fortz and Thorup. The reason for using the cost function of Fortz and Thorup was that the function was employed in many studies as mentioned above. One novel aspect of the work of Sqalli et al. was the addition of another optimization objective (i.e. minimization of congested link) on top of minimization of maximum link utilization. This resulted in better distribution of traffic in the network since this is one fundamental requirement of network traffic engineering. The function employed by Sqalli et al. is defined as
where MU is the maximum utilization of the network. S e t C A defines the set of congested links, E represents the total number of links in the network, c a refers to the capacity of link a, and l a is the total traffic on link a.
The second term of (5) after the plus sign defines the extra load on the network. This extra load is found by taking all the congested links, divided by the total number of links present in the network to normalize the entire function. For an uncongested network, the term after the plus sign results in a zero. Thus, (5) results in minimization of maximum utilization provided that there is no congestion in the network. If congestion exists, then the function results in the minimization of maximum utilization as well as the minimization of the number of congested links. Sqalli et al. concluded that the cost function in (5) results in more efficient minimization of the number of congested links compared to the cost function of Fortz and Thorup [2]. Furthermore, Sqalli et al. discovered that the results for maximum utilization with their method were comparable to those obtained by the approach of Fortz and Thorup. Using the cost function of (5), Sqalli et al. applied the simulated evolution (SimE) algorithm [40] to the OSPFWS problem and compared the results with the results of SA [38]. Tabu search using the cost function of Sqalli et al. [11] has also been applied to the OSPFWS problem [41].
A limitation of the cost function of Fortz and Thorup is that it minimizes “maximum utilization” only. This may lead to the existence of links which are either congested or unused. The cost function proposed by Sqalli et al. (5) was aimed at simultaneous optimization of maximum utilization and the number of congested links, without any consideration of unused links. It is, therefore, not guaranteed that optimizing maximum utilization and number of congested links would implicitly optimize the number of unused links as well. This observation points to the fact that to have a more stable traffic flow, traffic from congested links should be shifted to unused links. Therefore, in order to overcome this issue, Mohiuddin et al. [42] proposed a fuzzy logic based cost function that addresses the simultaneous optimization of maximum utilization, number of congested links, and number of unused links through fuzzy logic based aggregation. Mohiuddin et al. used their fuzzy cost function with three iterative heuristics, namely, simulated evolution, simulated annealing, and NGSA-II, and performed a mutual comparison of the three algorithms.
3 Open shortest part first weight setting problem definition
This section provides the details of the OSPFWS problem. More specifically, the section provides a formal definition of the OSPFWS problem, followed by a discussion of the calculation of traffic load on links.
3.1 Open shortest path first weight setting problem
The OSPFWS problem is formulated as follows. Given a network topology and predicted traffic demands, find a set of OSPF weights that optimizes network performance. More precisely, given a directed network G=(N,A), a demand matrix D, and capacity C a for each arc a∈A, determine a positive integer weight q a ∈[1,q m a x ] for each arc a∈A such that the objective function or cost function Φ is minimized. The maximum value of this weight, q m a x , is a user-defined upper limit. Fortz and Thorup [29] discovered that a small set of weight values significantly reduces the overhead of the algorithm. By experimentation, they set w m a x to 20. The chosen weights on arcs determine the shortest paths, which in turn completely determine the routing of traffic flow, the loads on the arcs, and the value of the cost function. The quality of OSPF routing is highly dependent on the selection of weights. Figure 1 shows a topology with weights assigned to each arc. These weights are in the range [1,20]. A solution for this topology can be (18,1,7,15,3,17,14,19,13,18,4,16,16). The weights are arranged through a breadth-first traversal of the graph. For example, for node A, the weights on the outgoing links are 18 and 1. For node B, the weights on outgoing links are 7 and 15, and so on.
For the purposes of this paper, three objectives are considered. These objectives are maximum utilization, number of congested links, and number of unused links, all of which need to be minimized simultaneously. Minimizing maximum utilization will lead to better distribution of network traffic across all the links such that congestion can be avoided and the network can be utilized well as per its capacity [8]. Network administrators desire less congested links. However, if a network is highly congested, then the preference is to reduce the congestion by at least minimizing the total number of congested links. For example, assume a network with 50 congested links and 20 unused links. It would be preferred to accommodate the traffic of the 50 congested links additionally on the 20 unused links. This indicates that minimizing the number of unused links also affects the performance of the network. This positive effect on the performance is due to traffic distribution across the links of the networks which depends on the routing paths established [42]. Therefore, a new solution might create new routing paths such that traffic on congested links may be distributed on unused links.
3.2 Traffic load calculation
This section provides details of the steps to calculate arc (or link) loads. Given a weight setting {w a } a∈A , the arc loads l a are calculated in five steps. For all demand pairs d s t ∈D, consider one destination t at a time and compute partial arc loads \({l_{a}^{t}}~\forall ~t \in \bar {N} \subseteq N\), where \( \bar {N} \) is the set of destination nodes. The steps are as follows:
-
1.
Compute the shortest distances \({d_{u}^{t}}\) from each node u∈N to t, using Dijkstra’s shortest path algorithm [7]. Dijkstra’s algorithm usually computes the distances away from source s, but since it is required to compute the distance to the sink node t, the algorithm is applied on the graph obtained by reversing all arcs in G.
-
2.
Compute the set A t of arcs on shortest paths to t as,
$$A^{t} = \{(u,v) \in A: {d_{u}^{t}} - {d_{v}^{t}} = w_{(u,v)}\} $$ -
3.
For each node u, let \( {\delta _{u}^{t}}\) denote its outdegree in G t=(N,A t), i.e.,
$${\delta_{u}^{t}} = \mid \{ v \in N : (u,v) \in A_{t} \} \mid $$If \({\delta _{u}^{t}} >1\), then traffic flow is split at node u to balance the load.
-
4.
The partial loads \({l_{a}^{t}}\) are computed as follows:
-
(a)
Nodes v∈N are visited in order of decreasing distance \({d_{v}^{t}}\) to t.
-
(b)
When visiting a node v, for all (v,w)∈A t, set
$$l_{(v,w)}^{t} = 1/[{\delta_{v}^{t}}(d_{vt} + {\sum}_{(u,v)\in A^{t}} l_{(u,v)}^{t})]$$
-
(a)
-
5.
The arc load l a is now summed from the partial loads as:
$$l_{a}={\sum}_{t\in \bar{N}} {l_{a}^{t}} $$
4 Fuzzy logic and aggregation operators
In general terms, a crisp set X is defined as a collection of objects x∈X, where each object can either belong to the set or not. However, in many practical situations, certain objects do not fulfil this “crisp” membership requirement. In such situations, a need arises for another set theory which could deal with uncertain data. One possible approach is fuzzy set theory (FST), which aims to represent vague information.
The basis of the theory of fuzzy sets [43, 44] is multi-valued logic wherein a statement can be partly false and partly true at the same time. Formally, a fuzzy set is characterized by a membership function, μ, in the range [0,1]. The membership function provides a measure of the degree of presence for every element in the set [45]. A value of μ=1 indicates that the statement is true, while μ=0 indicates that the statement is false.
Similar to crisp sets, set operations such as union, intersection, and complement are also defined on fuzzy sets. A number of operators exist for fuzzy union and fuzzy intersection. Fuzzy intersection operators are referred to as t-norm operators while fuzzy union operators are known as s-norm operators. Generally, the t-norm is implemented using “min” and the s-norm using “max”. However, in the formulation of multi-criteria decision functions, the simple AND (pure “min” function) and simple OR (pure “max” function) does not work well, due to the fact that the simple AND or OR operations consider the effect of only one objective while neglecting the effects of other objectives. This deficiency of the simple AND and simple OR operators resulted in the development of a number of “soft-AND” and “soft-OR” operators, such as the Werners operator [46], Einstein’s operator [46], Hamacher’s operator [47], Frank’s operator [48], Weber’s operator [49], Dubois and Prade’s operator [50], and the Unified And-Or operator [51], among others. These operators allow easy adjustment of the degree of “anding” and “oring” embedded in the aggregation.
Khan and Engelbrecht showed that the Unified And-Or (UAO) operator [51] satisfies the monotonicity, symmetry, and idempotency conditions. One important characteristic of the UAO operator is that a single equation is used to adjust the degree of “anding” and “oring”. Yet, the operator is capable of behaving either as the soft-AND or the soft-OR operator. This is in contrast to other aggregation operators listed above, which use separate equations for AND and OR functions. The behavior of ANDing and ORing of UAO is controlled by a variable, ν≥ 0, whose value decides whether the function behaves as AND or OR. The operator is defined as:
where a represents the membership value of μ A (i.e. a = μ A ), b represents the membership value of μ B (i.e. b = μ B ), and f(a,b) represents the value of the overall objective function (i.e. f(a,b) = μ A B ). I ∗ represents the AND operation using the UAO operator, and I ⋆ denotes the OR operation using the UAO operator. For more details of the UAO operator, the interested reader is referred to Khan and Engelbrecht [51].
5 Fuzzy logic approach for the open shortest path first weight setting problem
Although the approach has been previously proposed and explained in Mohiuddin et al. [42], it is again summarized below for the sake of completeness. Details can be found in Mohiuddin et al. [42].
The solution to the OSPFWS problem is to assign a set of weights to network links. The best solution is one which optimizes the network resources efficiently. The design objectives of the OSPFWS problem include maximum utilization (MU), number of congested links (NOC) and number of unused links (NUL). These objectives individually on their own do not provide adequate information for deciding the quality of a solution. The conflicting nature of these objectives further amplifies the complexity of the problem. With this complexity, a mechanism is required to find a solution that provides the best tradeoff covering all the objectives. Fuzzy logic is one approach that can conveniently and efficiently handle the tradeoff issues between multiple objectives.
The rest of this section details the employment of fuzzy logic for combining the three conflicting objectives into a single overall objective. This overall objective assesses the quality of a solution in terms of membership of a given set of weights. A set of weights providing efficient utilization of network resources consists of low MU, low NOC and low NUL.
To formulate the overall objective function, the values of individual objectives need to be determined first, through membership functions. This needs the formulation of membership functions for each individual objective. This process is described below.
To define the membership function of maximum utilization, two extreme values, the minimum and maximum, are determined first. These values could be found mathematically or from prior knowledge. Figure 2 shows the membership function of the objective to be optimized (maximum utilization in this case). Point ‘A’ refers to minimum MU (MinMU) and point ‘B’ refers to maximum MU (MaxMU). The membership value for MU, μ M U , is determined as follows:
The membership function for NOC, μ N O C , is defined in a similar way. In Fig. 2, point ‘A’ then refers to minimum NOC (MinNOC) and ‘B’ refers to maximum NOC (MaxNOC). The membership function of NOC is defined as follows:
Finally, the membership function for NUL, μ N U L , is defined as
where minimum (MinNUL) and maximum (MaxNUL) values correspond to ‘A’ and ‘B’, respectively in Fig. 2.
A good solution to the OSPFWS problem is one that is characterized by a low MU, low NOC, and low NUL. In fuzzy logic, this can be stated by the following fuzzy rule:
- Rule 1::
-
IF a solution X has low MU AND low NOC AND low NUL THEN it is a good solution.
The words ‘low MU’, ‘low NOC’ and ‘low NUL’ are linguistic values, each defining a fuzzy subset of solutions. Using the UAO operator [51], the above fuzzy rule reduces to the following equation.
where μ(x) is the membership value for solution x in the fuzzy set “good OSPF Weight set” and ν is a constant in the range [0,1]. Moreover, μ i for i={1,2,3} represents the membership values of solution x in the fuzzy sets low MU, low NOC, and low NUL respectively. The solution which results in the maximum value for (10) is reported as the best solution.
As an example, consider an arbitrary solution S 1, having μ M U =0.19, μ N O C =0.2, and μ N U L =0.17. Also assume that ν=0.5. Then, (10) results in a value of 0.152. Similarly, consider μ M U =0.22, μ N O C =0.23, and μ N U L =0.009 associated with another arbitrary solution S 2. Again assume that ν=0.5. Then, (10) evaluates to 0.164. Thus, solution S 2 is better than solution S 1 in terms of quality. Equation (10) is employed as a fuzzy cost function for solving the OSPFWS problem using the fuzzy PSO and the fuzzy PSO with simulated evolution algorithms. In this paper, the fuzzy cost function is denoted as FuzzyCF.
6 Fuzzy particle swarm optimization for the open shortest path first weight setting problem
The fuzzy PSO (FPSO) algorithm navigates the search space by maintaining a swarm of candidate solutions, with each candidate solution referred to as a particle. Each particle explores new positions in the search space through its own history, and from the experience of other particles. With respect to the OSPFWS problem, each particle reaches a new candidate solution by changing a few weights on the links of the network. As with the basic PSO [52], the guidance in changing these weights is provided by the particle‘s current position, its own best position so far, and the global best position obtained so far by the entire algorithm. Each step of the proposed FPSO algorithm is discussed in the following subsections in detail.
6.1 Particle position and velocity representation
The standard PSO uses floating-point vectors to represent positions and velocities. For the OSPFWS problem, this study uses a set representation for particles. Therefore, for an arbitrary network with nodes from a to q, each particle position is defined as a set,
where w a b is the weight assigned to the link between any two nodes a and b in the network. A constant, W, is also defined as the number of weights in the solution, i.e. |X i (t)| = W. The velocity of particle i is represented as
which represents a sequence of replacement operators where the weight of link (a,b) is replaced with a new value, \(w^{\prime }_{ab}\), and |V i (t)| gives the total number of changes to particle i.
Example 1
Consider the topology given in Fig. 1. Note that the total number of links is 14. The assigned weights in this figure represent a possible configuration at time t, whereas the configuration represents a solution (i.e. a particle). A solution for this topology can be (18,1,7,15,3,17,5,14,19,13,18,4,16,16). This current solution is represented as
Also assume that at time t, V i (t)={(19⇔18) A B ,(2⇔1) A F ,(4⇔7) B C ,(12⇔15) B D ,(4⇔3) C E ,(15⇔17) C F ,(6⇔5) D A ,(12⇔14) E A ,(13⇔19) E G ,(10⇔13) F B ,(11⇔18) F D ,(9⇔4) F G ,(17⇔16) G B ,(17⇔16) G D } where the symbol “ ⇔” represents a replacement of weights on the links. That is, the above solution, X i (t), was obtained when weight 19 on link AB was replaced with a weight of 18, weight 2 on link AF was replaced with a weight of 1, and so on. The solution X i (t) is then updated in subsequent steps as discussed in the following subsections.
6.2 Velocity update
The velocity of particle i is updated using
where P i (t) represents the particle’s own best position, and P g (t) represents the global best position.
In (11), the operator ⊗ is implemented as follows: The number of elements to be selected is determined as ⌊w×|V i (t)| ⌋, where 0<w<1. Then, the result is the above number of elements randomly selected from V i (t). The same approach is applicable to other terms where the operator ⊗ is used.
The operator ⊘ is implemented as a ‘replacement’ operator. For example, the weights in X i (t) are replaced with the weights in P i (t).
The term c 1 r 1(t)⊗[P i (t)⊘X i (t)] is implemented by randomly sampling ⌊c 1 r 1(t)×|P i (t)⊘X i (t)| ⌋ elements from the set P i (t)⊘X i (t), as follows:
where |P i (t)⊘X i (t)| represents the cardinality of the set. The result of (12) indicates the number of elements that are randomly selected from the set P i (t)⊘X i (t); c 2 r 2(t)⊗[P g (t)⊘X i (t)] has the same meaning.
The operator ⊕ implements the set addition (union) operator. V m a x is used to limit the number of elements selected from a set.
Example 2
Continuing with Example 1, assume the following parameter values:
w=0.5, V m a x =2, c 1 = c 2=0.5, r 1=0.52 (randomly generated), r 2=0.75 (randomly generated). Further assume that the best goodness so far for particle i was generated by the following position as
Also assume that the best solution so far generated by the entire swarm was achieved by:
The inertia weight, w, determines the number of replacements that will be randomly selected from V i (t) (mentioned in Example 1 above). Since w=0.5, and |V i (t)| = 14, the number of randomly selected replacements is 0.5×|V i (t)| = 7. Thus, any seven replacements from the set V i (t) can be taken randomly. Consider that those replacements are {(2⇔1) A F ,(4⇔7) B C ,(4⇔3) C E ,(6⇔5) D A ,(12⇔14) E A ,(13⇔19) E G ,(10⇔13) F B }.
The difference between the particle’s current position and its own best position, P i (t)⊘X i (t), is calculated by replacing each link in X i (t) with the link in the corresponding position in P i (t) as:
P i (t)⊘X i (t)={(18⇔18) A B ,(1⇔12) A F ,(7⇔7) B C ,(15⇔15) B D ,(3⇔3) C E ,(17⇔16) C F ,(5⇔5) D A ,(14⇔13) E A ,(19⇔19) E G ,(13⇔13) F B ,(18⇔8) F D ,(4⇔4) F G ,(16⇔12) G B ,(16⇔16) G D }.
Therefore, c 1×r 1⊗(P i (t)⊘X i (t))=0.5×0.52×|P i (t)⊘X i (t)|. Since the cardinality of P i (t)⊘X i (t) is 5, this implies that 0.5×0.52⊗|P i (t)⊘X i (t)|=1.3=1. This means that any one of the five elements in P i (t)⊘X i (t) is randomly chosen. Assume that c 1×r 1⊗(P i (t)⊘X i (t)) = {(18⇔8) F D }.
Similarly,
P g (t)⊘X i (t) = {(18⇔18) A B ,(1⇔2) A F ,(7⇔7) B C ,(15⇔15) B D ,(3⇔3) C E ,(17⇔15) C F ,(5⇔5) D A ,(14⇔13) E A ,(19⇔19) E G ,(13⇔13) F B ,(18⇔9) F D ,(4⇔4) F G ,(16⇔1) G B ,(16⇔16) G D }.
The cardinality of the above set is 5, since replacements involving new and old weights having the same value are ignored. Therefore, 0.5×0.75⊗(P g (t)⊘X i (t))=0.5×0.75×5 = 1.3 = 1 replacement. Assume {(17⇔15) C F } is randomly chosen.
Substituting the above calculations in (11) gives V i (t+1) containing three elements, i.e.
V i (t+1) = {(2⇔1) A F ,(4⇔7) B C ,(4⇔3) C E ,(6⇔5) D A ,(12⇔14) E A ,(13⇔19) E G ,(10⇔13) F B ,(18⇔8) F D ,(17⇔15) C F }
Since V m a x = 2, only two replacements from V i (t+1) are randomly chosen. Assume that ((18⇔8) F D and (17⇔15) C F are chosen. Then,
V i (t+1) = {(18⇔8) F D ,(17⇔15) C F }
6.3 Particle position update
The position X i (t) of a particle i is updated using
where \(\biguplus \) is a special operator that updates the links in X i (t) on the basis of weight replacements in V i (t+1), to get the new position X i (t+1).
Example 3
Consider Example 2, for which
Thus, in the new solution, weight 18 on link FD is replaced by 8 and weight 17 on link CF is replaced by 15.
6.4 Fitness evaluation
Each iteration performs a few weight replacements. Because of weight changes, the routes within the network will change. The next step is to calculate the traffic on each link as a result of the new routes. Finally, the cost of the new solution is computed using (10) as discussed in Section 5.
7 Fuzzy evolutionary particle swarm optimization algorithm for open shortest path first weight setting problem
In addition to the fuzzy PSO algorithm for OSPFWS (described in Section 6), a hybrid variant of the fuzzy PSO using the simulated evolution (SimE) algorithm is presented in this section. This hybrid variant is referred to as fuzzy evolutionary PSO (FEPSO). Section 7.1 presents a brief discussion on SimE. This is followed by a discussion on FEPSO in Section 7.2.
7.1 Simulated evolution algorithm
Simulated evolution (SimE) is a search strategy proposed by Kling and Banerjee [9, 53, 54]. Throughout the search, SimE maintains a single solution which is perturbed to generate a new solution. Each solution is comprised of a set of individuals, known as elements. SimE iteratively executes three steps:
-
The evaluation step, which calculates the goodness of each element of the solution. The goodness of an element quantifies the nearness of the element with respect to its optimal value, and is a value in the range [0,1]. The optimal value is problem specific and is determined theoretically or through some empirical analysis. A higher value of goodness indicates that the element is near to its optimal value.
-
The selection step, in which a subset of elements are selected based on their goodness and removed from the current solution. The lower the goodness of a particular element, the higher its selection probability. A bias parameter B in the range [-1, 1] is used to control the number of elements selected. A negative value of B increases the number of elements selected in each iteration, thus favoring exploration. This may result in a high quality solution but at the expense of higher computational time. A positive value of B inflates the goodness of an element, thus reducing the number of elements being selected for reallocation. This may result in reduced execution time, but at the risk of premature convergence to sub-optimal (or local optimal) solution.
-
The allocation step, in which the selected elements are allocated to new positions, with the intention of improving the existing solution. Each element selected in the selection step is removed from the solution and trial allocations are performed. The goodness of the solution resulting from each trial allocation is calculated, and the allocation which results in the highest goodness of the solution is accepted. This process of allocation and goodness calculations is repeated for each selected element. At the end of the allocation step, a new solution is obtained.
Further details about the SimE algorithm can be found in [9, 53, 54].
7.2 Fuzzy evolutionary particle swarm optimization
Particles of the fuzzy PSO algorithm proposed in Section 6 perform weight replacements. These replacements involve replacing an old weights with a new weights on the links. Furthermore, the total number of performed replacements is limited by the parameter V m a x . It is possible that, for a link i, a replacement may remove a weight (to be replaced with another weight) which might already be the optimum (or near-optimum) weight for that link. Note that this replacement is done ‘blindly’. That is, the value of the new weight is chosen randomly. If these blind replacements continue for other links having optimum weights, then it will take a significant amount of time for the algorithm to converge. Rather than having a blind replacement, it would be more appropriate to replace a weight based on its quality. A weight with low quality will have a high probability of being removed from its current position, and vice versa. The question is how to measure the quality of a weight. This can be answered by incorporating the evaluation and selection phases of the SimE algorithm into the FPSO algorithm, as discussed below.
Recall from Section 7.1 that a solution in SimE is comprised of elements. For the OSPFWS problem, elements are the link weights, whose goodness need to be evaluated. In this paper, the function defined by Sqalli et al. [38] is employed to evaluate the goodness of a weight, as given below:
where u i j represents the utilization on link connecting nodes i and j, and MU refers to the maximum utilization. The evaluation is performed for all current weights which are part of the set V i (t+1) as defined by (11).
Once the goodness of each existing weight in V i (t+1) is evaluated, the selection phase chooses the weights that would be replaced with new weights. This selection is done probabilistically based on the quality of existing weights in V i (t+1). A random number R a n d o m in the range [0,1] is generated. If R a n d o m ≤ 1−g i j + B, then the existing weight is selected for replacement, otherwise no replacement is done. In the above expression, g i j refers to the goodness of current weight on the link connecting nodes i and j, and B is the selection bias. Figure 3 provides the pseudo-code of the selection function for FEPSO. The selection process is illustrated by the following example.
Example 4
In Example 2, V i (t+1) was found as follows:
V i (t+1) = {(2⇔1) A F ,(4⇔7) B C ,(4⇔3) C E ,(6⇔5) D A ,(12⇔14) E A ,(13⇔19) E G ,(10⇔13) F B ,(18⇔8) F D ,(17⇔15) C F }
Since V m a x = 2, only two replacements from V i (t+1) were randomly chosen in FPSO. However, in FEPSO, the replacements will be done based on the goodness of weights. Assume that (4⇔3) C E , (10⇔13) F B and (17⇔15) C F were selected based on the selection procedure. However, since V m a x = 2, only two replacements will be selected randomly out of the three. So, a possible result could be
V i (t+1) = {(10⇔13) F B and (17⇔15) C F }
Although the proposed hybridization between PSO and SimE seems promising in generating high quality results, the approach also has some negative aspects. One major complexity is associated with tuning of another parameter, namely, bias B, on top of tuning of various parameters associated with the PSO algorithm. This adds extra effort and time to find the best combination out of many possible combinations of all design parameters. Another issue is that the complexity of the code increases, thus increasing the execution time. A single iteration of FEPSO will take more time than a single iteration of FPSO. In a broader perspective and with consideration of applying the proposed hybrid algorithm to other optimization problems, it can be argued that the proposed hybridization will allow faster convergence of FEPSO to an optimal or sub-optimal solution as compared to FPSO. However, this is not always guaranteed and can only be established after thorough experimentation and analysis.
8 Experimental methodology
This paper uses test cases from [2] which have been used by many other researchers as discussed in Section 2. Table 1 summarizes the characteristics of the test cases. For each test case, the table lists its network type, the number of nodes (N), and the number of arcs or edges (a). The 2-level hierarchical networks are generated using the GT-ITM generator [55], based on the model of Calvert [56] and Zegura [57]. In hierarchical networks, local access arcs have capacities equal to 200, while long distance arcs have capacities equal to 1000. In Random networks and Waxman networks, capacities are set at 1000 for all arcs. Fortz and Thorup generated the demands to force some nodes to be more active senders or receivers than others, thus modelling hot spots on the network. More specifically, higher demands were assigned to closely located node pairs. Further details can be found in [8].
Experiments were done with different combinations of PSO parameters for each test case. Thirty independent runs were executed for each parameter setup, and the average of the best solutions found in each run was reported, with the associated standard deviation. Furthermore, results were validated for statistical significance through non-parametric testing. For this purpose, the Wilcoxon’s rank-sum test was used with confidence level set at 95 %. After experimenting with different values, it was found that 100 iterations were reasonable to observe the trends. Therefore, each run was executed for 100 iterations.
9 Results and discussion
The proposed PSO algorithm was evaluated with respect to all the PSO parameters. These parameters are the swarm size, acceleration coefficients c 1 and c 2, inertia weight w, and velocity clamping V m a x . Table 2 lists all the parameter combinations used. The following parameters were used as default: swarm size =40, V m a x =15, w=0.72, and c 1 = c 2 = 1.49. The values c 1 = c 2 = 1.49 (along with w=0.72) were specifically selected, since they are frequently used in the literature due to the fact that they enhance the probability of convergence [58].
9.1 Effect of Swarm Size
The effect of swarm size was investigated with 20, 40, 60, 80, and 100 particles, as listed in Table 2. Other parameter values were kept at the defaults. Figures 4 and 5 provide a graphical representation of the effect of varying the swarm size on the quality of solutions obtained for test cases with 50 nodes and 100 nodes, respectively (detailed results are presented in Appendix B). It is observed from the figures that for all test cases, increasing the number of particles enhanced the quality of solution. More specifically, the highest average overall goodness was obtained with the highest swarm size consisting of 100 particles, while the lowest average overall goodness was obtained with the minimum value of swarm size, i.e. 20 particles. Furthermore, the figures show a logarithmic decrease in the gains in quality with increase in swarm size. A validation with Wilcoxon’s test with 95 % significance level for the average overall goodness obtained with different swarm sizes was also performed for the results reported in Tables 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 and 25 (refer to Appendix B). The hypothesis testing was done to check whether the average goodness value obtained with 100 particles was statistically significantly better than those obtained with other swarm sizes. The results confirmed that a swarm size of 100 gave the best results for all test cases.
Another important observation from Tables 14 to 25 is that, for most test cases, swarms of 80 and 100 particles resulted in no significant difference with respect to solution quality. This happened for the test cases h100N280a, h100N360a, h50N212a, r100N503a, r50N228a, r50N245a, w50N169a, and w50N230a. The test case w50N169a was an exception, where swarm sizes 60, 80, and 100 particles resulted in the same quality of solutions. Therefore, the smaller swarm size was preferred over larger swarm size due to lower computational cost.
Diversity is defined as a measure of the average distance of each particle from the center of the mass. Diversity is calculated at each iteration during the execution of the algorithm [59]. The effect of increase in swarm size on diversity was also studied. The purpose was to observe whether bigger swarm sizes reduced the possibility of getting trapped in local minima (preventing premature convergence), thus resulting in solutions of higher quality. As an example, Fig. 6 shows the diversity plots for different number of particles for the test case w100N476a. The figure suggests that the algorithm did not converge immediately after initialization for all the swarms. Diversity increased until around iteration number 50. The reduction in diversity is seen when the algorithm started converging. Swarms with 20 particles maintained diversity at a higher level compared to other swarm sizes, and quickly converged at around iteration 225. This is followed by swarms with 40 and 60 particles, which converged nearly at the same time, at around iteration number 326. Followed by this, swarm with 80 particles converged at iteration 380. Finally, the swarm with 100 particles converged last, after 400 iterations.
9.2 Effect of acceleration coefficients
The impact of the acceleration coefficients on the algorithm’s performance was also evaluated. Table 3 gives the average overall goodness for different combinations of acceleration coefficients, as given in Table 2. Other algorithm parameters were kept as their defaults.
As observed in Table 3, a dominant trend was that the best results were obtained when the value of c 1 was much higher than that of c 2. That is, for seven out of twelve test cases, the best overall goodness was obtained when c 1 = 3.0 and c 2 = 0.5. Furthermore, there were two other test cases (r100N403a and w100N391a) where the best overall goodness was obtained with c 1 = 1.4 and c 2 = 0.7. These results indicate that in general, the algorithm resulted in highest overall goodness values when the cognitive component dominated the social component. There were only three test cases (h100N280a, h100N360a and w50N169a) which deviated from the above trend.
The above observations are further supported by the results given in Table 4 which gives the percentage improvements in terms of the best and worst overall goodness values. The results show that the level of improvements achieved ranged between 2.61% and 11.74%. In most instances, the average overall goodness was around 4% or above. Statistical validation with the Wilcoxon’s test proved that in a majority of the cases, the improvements were statistically significant (highlighted in boldface). It is clear from these results that for eight test cases, best overall goodness values were obtained when the value of c 1 was greater than c 2. There were three exceptions, namely, h100N280a, w50N169a, and h100N360 (highlighted in asterisk) which deviated from the above trend. Furthermore, improvements in one test case (r50N245a) turned out to be statistically insignificant. In view of the above results and discussion, it can be fairly concluded that higher quality results produced by PSO were governed by the cognitive component.
9.3 Effect of inertia weight
The effect of the inertia weight was assessed with respect to the five values listed in Table 2. Other algorithm parameters were kept at their defaults. Table 5 gives the average overall goodness for the different values of the inertia weight. It is observed from this table that, in general, higher values of the inertia weight (w = 0.85 and w = 0.99) tend to show better results than the tried smaller values.
In order to validate the above observations, statistical testing was done and results are shown in Table 6. This table shows the percentage improvements obtained when results with two different inertia weights were compared. Although the results show improvements in terms of percentages, statistical testing revealed that in general, improvements were statistically insignificant. Only few improvements were significant which are highlighted in boldface. Based on these observations, it can be confidently claimed that with respect to the five values tried, the inertia weight did not have a notable impact on the output results produced by the algorithm.
9.4 Effect of velocity clamping
The effect of velocity clamping was also investigated. Apart from the default value of V m a x = 15, other values of velocity clamping 5, 10, and 20, were tried as listed in Table 2. Other algorithm parameters were kept as defaults. The inspiration for taking the aforementioned values of V m a x comes from the concept of mutation rates in genetic algorithms. Note that the function of V m a x in PSO and mutation in GA is somewhat similar; both parameters control the level of perturbation in the solution. Although the mutation rate is problem specific, a number of studies [59–63] have used the mutation rate of up to 20 %. Therefore, the motivation for choosing the given range of V m a x is the above observation. For the problem in hand, since the size of the solution string varies between 148 and 503 (corresponding to the number of edges on which the weights are varied), the values of V m a x ranging from 5 to 20 correspond to perturbation rates of 1 % to around 12 %.
Table 7 shows the average overall goodness for the four values of V m a x investigated. It is observed from the table that V m a x = 5 produced the highest values of average overall goodness for almost all test cases, with the exception of r100N403a, where V m a x = 10 produced the highest value of average overall goodness. Another deviation from the trend was the case w100N391a where both V m a x = 5 and V m a x = 10 produced the same level of average overall goodness.
The best performance of V m a x = 5 was further confirmed by statistical testing which showed that the results produced by V m a x = 5 were indeed significant for all test cases when compared with V m a x = 15 and V m a x = 20, as depicted in Table 8. Furthermore, when compared with V m a x = 10, the results produced by V m a x = 5 were statistically significant for 9 out of the 12 test cases. The above observations and analysis clearly indicate that V m a x = 5 resulted in the highest quality of solutions compared to the other values of V m a x tested.
It is obvious from the above discussion and analysis that V m a x had a significant impact on the quality of final solutions produced by the proposed PSO algorithm. The results also indicate that better overall goodness values were obtained when velocity clamping was kept low. This can be attributed to the fact that, with larger values of V m a x , the algorithm was biased towards exploration which rather resulted in more randomized search. A lower value of V m a x was therefore able to better balance exploration and exploitation.
9.5 Comparison of Fuzzy Particle Swarm Optimization and Fuzzy Evolutionary Particle Swarm Optimization
Table 9 summarizes the comparison of the proposed fuzzy PSO and the fuzzy evolutionary PSO. The table shows the results of the best parameter combination for FPSO and the corresponding results for FEPSO for the same parameter combination. Thirty runs were executed for each test case and results were statistically validated through Wilcoxon’s rank-sum test. The execution time (not the number of iterations) for both versions was also kept the same. It is clearly observed from the table that the improvements achieved by FESPO were statistically significant for all test cases, with the exception of h100N280a (for which FEPSO had a slightly inferior performance with degradation of 0.91% in the average overall goodness). However, statistical analysis suggested that this deteriorated result was not significant. Therefore, it can be confidently claimed that FEPSO outperformed FPSO in terms of quality of the average overall goodness.
The superior performance of FEPSO can be attributed to its design. Recall from Section 7.2 that an existing solution is perturbed by performing moves as governed by (11). These moves result in randomly replacing existing weights on links with new weights. It is quite possible that some of these moves may result in removing a near-optimum (or even optimum) weight from a certain link and introducing an unsuitable weight. In order to avoid this from happening, the concept of “intelligent” move was introduced in FEPSO, which allows the algorithm to converge in less amount of time, or alternatively speaking, producing higher quality results when executed for the same amount of time as that of FPSO.
10 Comparison of fuzzy evolutionary particle swarm optimization with other algorithms
Since fuzzy evolutionary PSO algorithm (FEPSO) performed better than fuzzy PSO (FPSO) algorithm, it was compared with other iterative heuristics, namely, Pareto-dominance PSO (PDPSO) [64], PSO with weighted aggregation (WAPSO) [65], non-dominated sorting genetic algorithm II (NSGA-II)[42, 66], simulated evolution (SimE)[40, 42], and simulated annealing (SA) [39, 42]. PDPSO and WAPSO were adapted for the underlying problem, whereas NSGA-II, SimE, and SA have already been applied to the same problem by Mohiuddin et al. [42]. Details of implementation and comparative analysis of NSGA-II, SimE, and SA can be found in Mohiuddin et al. [42]. Thirty runs were made for each test cases for each algorithm, and average results and standard deviations were reported. All algorithms were run for the same amount of time for fair comparisons.
Tables 10, 11, and 12 present the results obtained for FEPSO, PDPSO, WAPSO, NSGA-II, SimE, and SA for the three objectives, respectively. Since the multi-objective assessment approach for the algorithms is not the same, the overall objective function that shows the combined effect of all three objectives cannot be directly used for comparison. Therefore, each objective was evaluated individually. Table 10 indicates that for the maximum utilization objective, FEPSO obtained the best results for four test cases (h100N360a, r100N503a, r50N245a, w50N230a). For two test cases (r100N403a and r50N228a), both FEPSO and SimE produced the best results. For four cases (h100N280a, h40N212a, w100N391a, and w100N476a), SimE generated the best (minimum) values. For two test cases (h50N148a and w50N169a), SA obtained the best results. As for the objective of number of congested links, the results in Table 11 indicate that FEPSO obtained the best results for nine test cases. The exception was three test cases of h100N280a, h50N148a, and w50N169a where SimE, SA, and NSGA-II were able to achieve the best values, respectively. Finally for the objective of number of unused links, the results in Table 12 indicate that FEPSO was able to achieve optimum values (i.e., no link was left unused) in all test cases, with the exception of r50N245a. However, it should also be noted that there are many instances where other algorithms also achieved the optimum levels.
Although the discussion above provides a fair picture of the performance of FEPSO with respect to individual objectives, an overall view of FEPSO‘s performance is desired. Table 13 accumulates the results with regard to the three objectives and displays the best and worst achievers for each objective. The results given in Table 13 are based on results of Tables 10, 11, and 12. The table signifies that in five cases (h100N360a, r100N403a, r100N503a, r50N228a, and w50N230a), FEPSO achieved the best results for all three objectives, while there are four cases (h50N212a, r50N245a, w100N391a, and w100N476a) where FEPSO was dominant through achievement of best results in two objectives. In contrast, algorithms used for comparison with FEPSO achieved best results mostly in only one objective. There are some exceptions where other algorithms achieved best results in two objectives, but achieved worst results in the third objective, which, to some extent, negatively affects their best achievement in two objectives. Such instances are h100N280a, where SimE gets best results for MU and NOC objectives, but shows worst results for the NUL objective. Another example is h50N148a where NSGA-II shows the same trends as that of SimE. There is only one test case of w50N169a where NSGA-II achieved the best results for two objectives (NOC and NUL) but did not achieve worst results for the MU objective. Note that in all results, there is only one instance where FEPSO showed the worst performance (NOC for h100N280a). Based on the above discussion and observations, it can be fairly claimed that, overall, FEPSO showed the best performance compared to all other algorithms considered.
The overall better performance of FEPSO lies in its design, which combines the strong searching capabilities of PSO, augmented by the simulated evolution algorithm which allows a more intelligent local search capability. In contrast to this hybrid design of FEPSO, both SimE and SA lack efficient traversing of the whole search space, since both of them are local search algorithms after all. Furthermore, when compared with NSGA-II, PDPSO, and WAPSO, again the intelligent local search capability of FEPSO allowed it to outperform the three algorithms.
11 Conclusion
This paper proposed and investigated a multi-objective particle swarm optimization algorithm to efficiently solve the open shortest path first weight setting problem. Three optimization objectives, namely, maximum utilization, number of congested links, and number of unused links were considered in the optimization process. These conflicting objectives were aggregated into a scalar optimization function using the unified and-or fuzzy aggregation operator. The performance of the proposed algorithm was analyzed with regard to different algorithm parameters including swarm size, acceleration coefficients, inertia weight, and velocity clamping. Results revealed that swarm size, acceleration coefficients, and velocity clamping have a significant effect on the quality of results, but the algorithm was insensitive to variation in the inertia weight. Furthermore, a modified version of the fuzzy PSO, namely, fuzzy evolutionary PSO, was also proposed which incorporated characteristics of the simulated evolution algorithm. A comparison among the basic and modified versions of the PSO revealed that the fuzzy evolutionary PSO was able to produce results of higher quality compared to its basic counterpart. Furthermore, a comparison of fuzzy evolutionary PSO with Pareto-dominance PSO, weighted aggregation PSO, NSGA-II, simulated evolution, and simulated annealing algorithms revealed that the fuzzy evolutionary PSO outperformed the other five algorithms.
References
Coffman KG, Odlyzko AM (2001) Internet Growth: Is there a Moore’s Law for data Traffic? Handbook of Massive Data Sets, pp 47–93
Fortz B, Thorup M (2000) Internet traffic engineering by optimizing OSPF weights. IEEE Conference on Computer Communications(INFOCOM), pp 519–528
Kurose JF, Ross KW (2002) Computer Networking: A top-down approach featuring the internet prentice hall series
Bhagat NH (2013) A new hybrid approach to OSPF weight setting problem. Int J Recent Innov Trends Comput Commun 1(5):443–450
Bizri F, Sanso B (2008) Corouting: an IP hybrid routing approach. In: Fourth international conference on networking and services, pp 46–52
Kandula S, Katabi D, Davie B, Charny A (2005) Walking the tightrope responsive yet stable traffic engineering. In: ACM 2005 Conference on applications, technologies, architectures, and protocols for computer communications, pp 253–264
Dijkstra EW (1959) A node on two problems in connection of graphs. Numerical Mathematics
Fortz B, Thorup M (2000) Increasing internet capacity using local search. Technical Report IS-MG
Kling R, Banerjee P (1990) Optimization by simulated evolution with applications to standard cell placement. In: Proceedings of 27th Design Automation Conference, pp 20–25
Fortz B, Thorup M (2006) Optimizing OSPF/IS-IS weights in a changing world. IEEE J Sel Areas Commun 20(4):756–767
Sqalli MH, Sait SM, Mohiuddin MA (2006) An enhanced estimator to multi objective OSPF weight setting problem. Network Operations and Management Symposium, NOMS
Rodrigues M, Ramakrishnan KG (2002) Optimal routing in data networks. Bell Labs Tech J 6(1):117–138
Ericsson M, Resende MGC, Pardalos PM (2002) A Genetic Algorithm for the Weight Setting Problem in OSPF Routing. J. Combinatorial Optimisation conference
Zagozdzon M, Dzida M, Pioro M (2007) Traffic flow optimization in networks with combined OSPF/MPLS routing. In: IEEE 15Th international conference on advanced computing and communications, pp 131–137
Abo Ghazala A, El Sayed A (2009) Open Shortest Path First Weight Setting (OSPFWS) solving algorithms comparison and new method for updating weights. Int J Comput Sci Netw Secur 9(5):191–197
Parmar A, Ahmed S, Sokol J (2006) An integer programming approach to the OSPF weight setting problem NSF Technical Report no DMI-0457066
Srivastava S, Agarwal G, Medhi D, Pioro M (2005) Determining feasible link weight systems under various objectives for OSPF networks. IEEE Trans Netw Serv Manag 2(1)
Buriol L, Resende M, Rebeiro C, Thorup M (2002) TA Memetic algorithm for OSPF routing. In: 6Th INFORMS telecom, pp 187–188
Bley A (2005) On the approximability of the minimum congestion unsplittable shortest path routing problem. In: Integer programming and combinatorial optimization (IPCO 2005), lecture notes in computer science LNCS, pp 97–210
Bley A (2009) Approximability of unsplittable shortest path routing problems. Networks 54(1):23–46
Lin L, Gen M (2009) Priority-Based Genetic Algorithm for Shortest Path Routing Problem in OSPF. Intell Evol Syst, Stud in Comput Intell 187:91–104
Pioro M, Szentsi A, Harmatos J, Juttner A, Gajownicczek P, Kozdrowski S (2002) On open shortest path first related network optimization problems. Perform Eval 48(4):201–223
Retvari G, Cinkler T (2004) Practical ospf traffic engineering. IEEE Commun Lett 8:689–691
Retvari G, Biro J, Cinkler T (2006) On improving the accuracy of OSPF traffic engineering. In: NETWORKING 2006, Lecture notes in computer science (LNCS), vol 3976, pp 51–62
Nucci A, Bhattacharyya S, Taft N, Diot C (2007) Igp link weight assignment for operational tier-1 backbones. IEEE/ACM Trans Networking 15(4):789–802
Shrimali G, Akella A, Mutapcic A (2010) Cooperative interdomain traffic engineering using nash bargaining and decomposition. IEEE/ACM Trans Networking 18(2):341–352
Riedl A (2003) Optimized routing adaptation in IP networks utilizing OSPF and MPLS. In: IEEE International conference on communications, pp 1754–1758
Lee S, Po-Kai T, Chen A (2012) Link weight assignment and loop-free routing table update for link state routing protocols in energy-aware internet. Futur Gener Comput Syst 28:437–445
Fortz B, Rexford J, Thorup M (2002) Traffic engineering with tradional IP routing protocols. IEEE Commun Mag:118–124
Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers
Frigioni D, loffreda M, Nanni U, Pasqualone G (1998) Experimental analysis of dynamic algorithms for the single source shortest paths problem. ACM journal of experimental algorithms
Ramalingam G, Reps T (1996) An incremental algorithm for a generalization of the shortest path problem. Journal of Algorithms, 267–305
Fortz B Combinatorial Optimization and Telecommunications. http://www.poms.ucl.ac.be/staff/bf/en/COCom-5.pdf
Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor
Abo Ghazala A, El Sayed A, Mousa M (2008) A survey for open shortest path first weight setting (OSPFWS) problem. The 2nd International Conference on Information Security and Assurance (ISA2008), pp 24–26
Reis R, Ritt M, Buriol L, Resende M (2007) A memetic algorithm for the weight setting problem in DEFT. In: COMCEV 2007, pp 1–6
Abo Ghazala A, El Sayed A, Mousa M (2008) A new approach for open shortest path weight setting (OSPFWS) problem. Convergence and Hybrid Information Technology, pp 188–193
Sait SM, Sqalli MH, Mohiuddin MA (2006) Engineering evolutionary algorithm to solve multi objective OSPF weight setting problem. Australian Conference on Artificial Intelligence, pp 950–955
Laarhoven P, Aarts E (1987) Simulated Annealing: Theory and applications. Kluwer, Norwell
Kling R, Banerjee P (1991) Empirical and theoretical studies of the simulated evolution method applied to standard cell placement. IEEE Trans Comput-Aided Design 10(10):1303–1315
Houssaini Sqalli M, Mohammed Sait S, Asadullah S (2008) Minimizing the number of congested links in OSPF routing. ATNAC
Mohiuddin M, Khan SA, Engelbrecht AP (2014) Simulated evolution and simulated annealing algorithms for solving multi-objective open shortest path first weight setting problem. Appl Intell, Springer 40(3):1–20
Zadeh LA (1965) Fuzzy sets. Inf Control 8:338–353
Zadeh LA (1975) The Concept of a Linguistic Variable and its Application to Approximate Reasoning. Inf Sci 8:199–249
Zadeh LA (1973) Outline of a new approach to the analysis of complex systems and decision processes. IEEE Trans Syst Man Cybern 3(1):28–44
Li H, Yen V (1995) Fuzzy sets and fuzzy decision-making. CRC Press, USA
Hamacher H (1978) Ueber Logische Verknupfungen Unschalfer Aussagen und deren Zugehoerige Bewertungs-funktione. Prog Cybern Syst Res 3:276–288
Frank M (1979) On the simultaneous associativity of F(x,y) and x + y−F(x,y). Aequationes Math 19:194–226
Weber S (1983) A general concept of fuzzy connectives, negations and implications based on t-Norms and t-Conorms. Fuzzy Sets & Systems 11:115–134
Dubois D, Prade H (1979) Operations in fuzzy-valued logic. Inf Control 43:224–240
Khan SA, Engelbrecht AP (2007) A new fuzzy operator and its application to topology design of distributed local area networks. Inf Sci 177(12):2692–2711
Kennedy J, Eberhart RC (1995) Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks, pp 1942–1948
Kling R, Banerjee P (1991) Empirical and theoretical studies of the simulated evolution method applied to standard cell placement. IEEE Transactions on Computer-Aided Design, pp 1303–1305
Kling R, ESP P. Banerjee. (1989) Placement by simulated evolution. IEEE Transactions on Computer-Aided Design, pp 245–255
Zegura EW (1996) GT-ITM: Georgia Tech Internetwork Topology Models (software). http://www.cc.gatech.edu/faq/Ellen.Zegura/gt-itm/gt-itm.tar.gz
Calvert K, Doar M, Zegura EW (1997) Modeling internet toplogy. IEEE Commun Mag 35:160–163
Zegura EW, Calvert KL, bhattacharjee S (1996) How to model an internetwork. 15th IEE Conference on Computer Communications (INFOCOM), pp 594–602
van den Bergh F (2001) An analysis of particle swarm optimizers. PhD Thesis, University of Pretoria
Khan SA, Engelbrecht AP (2012) A fuzzy particle swarm optimization algorithm for computer communication network topology design. Appl Intell 36:161–177
Cho H, Wang B, Roychowdhury S (1998) Automatic rule generation for fuzzy controllers using genetic algorithms a study on representation scheme and mutation rate. In: IEEE World congress on computational intelligence, pp 1290–1295
Haupt R (2000) Optimum population size and mutation rate for a simple real genetic algorithm that optimizes array factors. In: IEEE Antennas and propagation society international symposium, pp 1034–1037
Lim M, Rahardja S, Gwee B (1996) A GA paradigm for learning fuzzy rules. Fuzzy Sets Syst 82:177–186
Liska J, Melsheimer SS (1994) Complete design of fuzzy login system using genetic algorithms. In: 3Rd IEEE international conference on fuzzy systems, pp 1377– 1382
Alvarez-Benitez J, Everson R, Fieldsend J (2005) A MOPSO Algorithm Based Exclusively on Pareto Dominance Concepts. In: 3rd International Conference on Evolutionary Multi-criterion Optimization, Lecture Notes in Computer Science (LNCS), vol 3410, pp 459–473
Parsopoulos K, Vrahatis M (2002) Particle swarm optimization method in multiobjective problems. In: ACM Symposium on applied computing, pp 603–607
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
The authors declare that they have no conflict of interest. This article does not contain any studies with human participants or animals performed by any of the authors. Informed consent was obtained from all individual participants included in the study.
Appendices
Appendix A
1.1 Nomenclature
- G :
-
Graph
- N :
-
Set of nodes
- n :
-
A single element in set N
- A :
-
Set of arcs
- A t :
-
Set of arcs representing shortest paths from all sources to destination node t
- a :
-
A single element in set A. It can also be represented as (i,j)
- s :
-
Source node
- v :
-
Intermediate node
- t :
-
Destination node
- D :
-
Demand matrix
- D :
-
[s,t] An element in the demand matrix that specifies the demand from source node s to destination node t; It can also be specified as d s t
- w i j :
-
Weight on arc (i,j); if a=(i,j), then it can also be represented as w a
- c i j :
-
Capacity on arc (i,j); if a=(i,j), then it can also be represented as c a
- Φ:
-
Cost function
- Φ i,j :
-
Cost associated with arc (i,j); if a=(i,j), then it can also be represented as Φ a
- \({\delta _{u}^{t}}\) :
-
Outdegree of node u when destination node is t
- δ +(u):
-
Outdegree of node u
- δ −(u):
-
Indegree of node u
- \({l_{a}^{t}}\) :
-
Load on arc a when destination node is t
- l a :
-
Total traffic load on arc a
- \(f^{(s,t)}_{a}\) :
-
Traffic flow from node s to t over arc a
- S e t C A :
-
Set of congested arcs
Terminology
-
1.
A single element in the set N is called a “Node”. It is represented as n.
-
2.
A single element in the set A is called an “Arc” or “Link”. It is represented as a.
-
3.
A set G=(N,A) is a graph defined as a finite nonempty set N of nodes and a collection A of pairs of distinct nodes from N.
-
4.
A “directed graph” or “digraph” G=(N,A) is a finite nonempty set N of nodes and a collection A of ordered pairs of distinct nodes from N; each ordered pair of nodes in A is called a “directed arc”.
-
5.
A digraph is “strongly connected” if for each pair of nodes i and j there is a directed path (i = n 1,n 2,...,n l = j) from i to j. A given graph G must be strongly connected for this problem.
-
6.
A “demand matrix” is a matrix that specifies the traffic flow between s and t, for each pair (s,t)∈N×N.
-
7.
(n 1,n 2,...,n l ) is a “directed walk” in a digraph G if (n i ,n i+1) is a directed arc in G for 1≤i≤l−1.
-
8.
A “directed path” is a directed walk with no repeated nodes.
-
9.
Given any directed path p=(i,j,k,...,l,m), the “length” of p is defined as w i j + w j k +... + w l m .
-
10.
The “outdegree” of a node u is a set of arcs leaving node u i.e., {(u,v):(u,v)∈A}.
-
11.
The “indegree” of a node u is a set of arcs entering node u i.e., {(v,u):(v,u)∈A}.
-
12.
The input to the problem will be a graph G, a demand matrix D, and capacities of each arc.
-
13.
The term MU refers to the maximum utilization. It is the highest load/capacity ratio of the network.
-
14.
The term NOC refers to the number of congested links.
-
15.
The term NUL refers to the number of unused links.
-
16.
The term E refers to the total number of links in the network.
Appendix B
Tables 14 to 25 provide the quality of solutions obtained with respect to the associated swarm size for all test cases. Column 1 represents the number of particles in the swarm. Column 2 represents the average overall goodness using the UAO operator. Column 3 represents the percentage difference between the average overall goodness of the corresponding number of particles and the highest average overall goodness (given in asterisk) of the solutions. Note that the swarm size resulting in the highest average overall goodness is taken as the reference, and the difference for other swarm sizes is calculated with respect to the reference value. The differences were also statistically tested using Wilcoxon’s rank sum test.
Rights and permissions
About this article
Cite this article
Mohiuddin, M.A., Khan, S.A. & Engelbrecht, A.P. Fuzzy particle swarm optimization algorithms for the open shortest path first weight setting problem. Appl Intell 45, 598–621 (2016). https://doi.org/10.1007/s10489-016-0776-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-016-0776-0