Routing and Open Shortest Path First Protocol

Get Complete Project Material File(s) Now! »

Introduction

The Internet has become an integral part of our lives. Internet users demand un- interrupted and smooth functioning of various applications. One important element of this smooth functioning is to ensure that data loss should be minimized, if not totally eliminated. This demands utilization of network resources such as network bandwidth and the number of available links at their best, or rather, at optimal lev- els. The challenge lies in how such optimal levels can be achieved. For example, if the flow of data is optimally mapped or distributed onto the available network resources, then the data packets will not be dropped, thus achieving optimal performance with respect to data flow. This concern about optimal utilization of network resources is the primary focus of the ideas and methods presented in this work. Optimization is a significant topic of research in various research domains including science, medicine, engineering, business, and humanities. In many of these disciplines, optimization simply refers to “doing better”. However, in the context of this thesis, optimization refers to a process of providing the best possible (optimal) solution to an NP-hard problem under the constraint of a limited computational budget. The specific problem considered herein is known as the open shortest path first weight setting (OSPFWS) problem, which is classified as an NP-hard problem [47]. The OSPFWS problem is related to the open shortest path first (OSPF) routing protocol [119], which is widely used in Internet Protocol (IP) networks. In this thesis, the terms “network” and “graph” are used interchangeably and these terms represent a communication network. The term “link” is used under the context of the term “network” and the term “arc” or “edge” is used under the context of the term “graph”. In the context of the OSPFWS problem, a node represents a network router and an edge represents a network link. The focus of this thesis is on adapting and applying a number of optimization techniques and their variants to the OSPFWS optimization problem, modelled as a multi-objective optimization problem. These sub-objectives have to be simultaneously optimized, namely to minimize “maximum utilization”, to minimize the number of congested links, and to minimize the number of unused links. In the context of the OSPFWS problem, the ratio of load on the link to the capacity of the link is referred to as the “utilization” of that link. The maximum utilization value amongst all the network links is termed as “maximum utilization”. Note that these objectives are in conflict with one another, because minimizing one objective may increase or decrease the other two objectives and vice versa. An optimal solution is thus required, which provides a balance among the objectives. This thesis applies various optimization techniques, including SA [91], SimE [93], and PSO [78] to solve the multi-objective OSPFWS problem. This chapter provides the motivation of the thesis followed by objectives and methodology adopted in the thesis. The contributions of this thesis are then summa- rized. The organization of the thesis is discussed in the last section of this chapter.

Motivation

In practice, network administrators often aim to use network resources efficiently. Routing is an important factor in enhancing the efficiency of a network. OSPF routing is widely used by large organizations, both as an open standard and a mature protocol. It is also supported by most vendors of routing hardware and software. The OSPF routing protocol assigns a weight to each link, where a weight represents a numeric integer value. The weights are then used to find the shortest paths for each destination node from other nodes. The OSPF routing protocol does not take the capacities of the links into consideration when these shortest paths are determined. Consequently, some links are left unused while others become congested depending on traffic demands. To balance the distribution of traffic demands onto the existing network links is therefore a challenge. In its simplest form, the OSPFWS problem can be described as finding a weight setting that leads to an efficient distribution of traffic demands onto the network. There are different mechanisms that guide the setting of these weights. Cisco sets the default weights of links as inversely proportional to the links’ capacities [45]. However, Cisco does not take traffic demands into consideration, which may result in congested or unutilized links. Thus, Cisco’s policy of assigning weights may not always be optimum. Another possibility is to assign the unity weight to all the links. However, this will lead to inefficient utilization of the links. This inefficiency will happen because links with less capacity might be used frequently to obtain the shortest paths between source and destination nodes. Contrary to this, higher capacity links might not be selected for shortest paths and thus might not be used at all. As the size of a network grows (which depends on the number of nodes and links), the solution space for the OSPFWS problem grows exponentially. Under such circumstances, intelligent heuristics are good candidates to be explored for better performance. The reason for being good candidates is that the intelligent heuristics explore the promising regions of the search space, instead of the whole search space. Literature has shown that well-established heuristics, such as SA, SimE, and PSO, have been successfully applied to several NP-hard problems similar to the OSPFWS problem [6, 71, 102, 104, 106, 109, 148, 157, 163, 164, 167, 170]. In addition, research has revealed that hybridization of heuristics has generally shown to be more efficient and effective [90, 129, 161, 168, 176, 177] on other problems. This particular aspect provides the motivation to develop hybrid heuristics for the OSPFWS problem. The motivation for the research work undertaken in this study therefore stems from the complexity of the problem, utilizing nature-inspired algorithms to optimize the OSPF weights, and designing hybrid versions of the algorithms specifically to solve the multi- objective OSPFWS problem. The OSPFWS problem is a multi-objective problem, where the objectives are in conflict with one another. Minimizing one objective may increase or decrease the other two objectives and vice versa. A great deal of research has been dedicated to address issues related to multi-objective optimization [28, 69, 87, 117, 148]. Amongst many other approaches [18, 22, 27, 54, 55, 63, 74, 113, 122, 179], fuzzy logic [180, 181] has been used as an approach to solve multi-objective optimization problems. Therefore, the motivation also arises to utilize fuzzy logic in the above algorithms to address the conflicting multi-objective nature of the OSPFWS problem.

Optimization and Optimization

Approaches This chapter provides a brief overview of optimization and concepts used in the the- sis. The chapter covers both single-objective and multi-objective optimization, with emphasis on the latter. Since fuzzy logic is used to develop the multi-objective func- tion, the necessary concepts of fuzzy logic are reviewed. The chapter also includes the details of iterative heuristics, with a focus on those used in this thesis. It ends with the discussion of MOO performance measures. The outline of the chapter is as follows: Section 2.1 provides a brief discussion of optimization. This section also discusses scalarized and non-dominance based approaches for solving MOO problems. Fuzzy logic is discussed in Section 2.2. Op- timization algorithms used in this thesis are discussed in Section 2.3. Section 2.4 discusses MOO performance measures used in this thesis to evaluate the performance of MOO algorithms. 2.1 Optimization Optimization is the process of modifying a system such that some features of the system work more efficiently or use fewer resources. The main idea of optimization is to determine a solution that represents the values of a set of parameters in such a way that the objective function is maximized or minimized, subject to certain constraints [7]. A solution is a feasible solution if it satisfies all the design constraints. Thus the optimal solution is the best solution amongst all available feasible solutions. Many real-world problems are optimization problems. Disciplines such as engi- neering, science, medicine, and business employ optimization algorithms on problems such as structural design, resource allocation, and planning. With respect to constraints, there are three kinds of optimization problems: un- constrained, boundary constrained and constrained. Unconstrained problems do not have any type of predefined conditions or restrictions on the values that can be as- signed to variables of the problem. Boundary constrained problems are also uncon- strained problems with an exception. The values that can be assigned to decision variables are constrained to be in a certain range. Contrary to this, constrained where gm and hm are the inequality and equality constraints, and ng and nh are respectively the number of inequality and equality constraints. A next level of categorization of optimization problems are based on the number of objectives. If only one objective is to be optimized, then the problem is referred to as a single objective optimization (SOO) problem. Contrary to this, a multi-objective optimization problem has more than one objective. In some cases of multiple objec- tives, optimizing one objective automatically optimizes the others. Such problems are considered as SOO problems. Contrary to this, for some problems optimizing one objective degrades at least one other objective. MOO algorithms have been developed to solve optimization problems with such conflicting objectives. A MOO algorithm has to find solutions that provide a trade-off between conflicting objectives. The set of solutions that achieve such a balance is referred to as the Pareto front [151]. Mathematically, a MOO problem is defined as follows: where no is the number of objectives and nx is the number of decision variables. The boundary constraints are represented by x ∈ [xmin, xmax] nx . There are at least two conflicting objective functions (i.e. no ≥ 2). Here, x = (x1, x2, …, xnx ) is called the vector of decision variables. In multi-objective optimization, vectors are regarded as optimal if their components can not be improved without deterioration of any one of the other components [113]. This is referred to as Pareto optimality. The output of a multi-objective optimization algorithm is a set of optimal solutions known as Pareto-optimal solutions. Pareto-optimal solutions are also known as non-dominated, non-inferior, or Pareto-efficient. A non Pareto-optimal solution is a solution where one optimization criterion can be improved without degrading any others. One way to solve a multi-objective optimization problem is to scalarize multiple objectives into a single-objective function and then to optimize this single-objective function. Thus each candidate solution to the problem during the search will be evaluated using this scalarized single-objective function. The second way is to handle individual objectives separately and judge the candidate solution using the domi- nance relation. The following sub-sections discuss a number of popular approaches to scalarize a MOO problem. The section also discusses the dominance based approach. Lexicographic Ordering Lexicographic ordering ranks the objectives in order of their importance [22]. The decision maker assigns the importance to various objectives. The optimum solution, x ∗ , is then obtained by optimizing the objective functions individually in order of their importance. The solution found by the current objective is fed into the next objective. The subscripts of the objectives denote the objective function number as well as the priority of the objective. Therefore, f1(x) and fno (x) represent the most and least important objective functions, respectively. Consequently, the first problem is formulated as follows: Goal Programming Goal programming [18, 74] is one of the first methods exclusively developed for MOO [113]. The ideal values of the objectives are defined as targets. These ideal values could be maximum or minimum attainable values depending on the type of objec- tive. These targets are then incorporated into the optimization problem [22]. The decision-maker specifies the ideal values Tk (k = 1, …, no) of the objectives. Absolute deviations from these target values are minimized as much as possible [113]. For a maximization problem, goals are of the form fk(x) ≥ Tk. The simplest form of goal programming [35] is formulated as follows: Fuzzy Logic and Multi-objective Optimization In addition to the aforementioned multi-objective aggregation techniques, fuzzy logic has also been used for multi-objective optimization. A number of studies have re- ported the use of fuzzy logic for MOO applications in a variety of domains [20, 76, 127, 130]. Since one of the focuses of this thesis is on fuzzy logic, an overview of fuzzy logic is provided in this section. The theory of fuzzy sets [180, 181] is based on multi-valued logic wherein a state- ment can be partly true and partly false at the same time. Fuzzy logic expresses the degree of truthfulness of a statement by a membership function, μ, in the range [0,1]. A value of μ = 1 indicates that the statement is true, whereas μ = 0 indicates that the statement is false. One distinction between fuzzy logic and binary logic is that the latter allows a statement to be only completely false or completely true, which is not the case with fuzzy logic. Fuzzy logic approaches to MOO replace the vector-based objective function with a fuzzy scalar function [155]. This approach is useful to determine solutions for the problems with uncertainties. For example, if the target is to optimize the utilization of network, then the terms such as “low utilization” or “high utilization” are uncertain. Such uncertain situations can be formulated in optimization algorithms to optimize multiple objectives of the problem. A framework for reflecting such uncertainties is conveniently provided by fuzzy logic, thus giving a strong motivation for considering a fuzzy logic approach to MOO problems. Most MOO problems, many of which are also combinatorial optimization problems are constrained or unconstrained. These problems have been shown to be NP-hard in nature [155]. To solve these NP-hard problems, heuristics are employed, which are based on human knowledge acquired through experience and understanding of problems. Such human knowledge can be expressed in natural language of fuzzy logic. The fuzzy logic includes numerical information (examples like traffic flow on each link and delay on each link) and linguistic information (examples like maximum utilization of network and non-congestion). This natural language representation of the problem further supports the use of fuzzy logic for solving MOO problems. The outline of subsequent sub-sections is as follows: Section 2.2.1 discusses fuzzy sets. A brief discussion of fuzzy reasoning is presented in Section 2.2.2. Section 2.2.3 defines the linguistic variable. Fuzzy rules and fuzzy logic systems are discussed in Sections 2.2.4 and 2.2.5 respectively. Lastly, some commonly used fuzzy operators are described in Section 2.2.6.

Fuzzy Set Theory

A crisp set, C, is usually defined as a set of elements or objects, c ∈ C, that can be finite, countable, or uncountable. Each element either belongs to a set or not. However, for most practical problems, objects do not have crisp (1 or 0) membership to sets. Fuzzy set theory (FST) aims to represent uncertain information, such as “low utilization” or “high utilization”. Such vague information is difficult to represent in classical (crisp) set theory. A fuzzy set is characterized by a membership function which provides a measure of the degree that each element belongs to the fuzzy set [112, 185]. A fuzzy set, Y , of a universe of discourse, C, is defined as Y = {(c, μY (c))| ∀ c ∈ C}, where μY (c) is a membership function of c with respect to fuzzy set Y . Figure 2.1 shows an example of a membership function. Set operations such as union, intersection, and complement, which are used in crisp sets, are also defined on fuzzy sets. A number of operators exist to represent fuzzy union and fuzzy intersection. Fuzzy union operators are known as s-norm op- erators. The s-norm operators are commonly known as “ORing” functions since they implement the OR operation between the membership functions under consideration. In terms of their mathematical properties, an s-norm operator satisfies the commu- tativity, monotonicity, associativity, and μY S {0} = μY properties. Some examples of s-norm operators are given below (where Y and Z are fuzzy sets of universe of discourse, C) [112]: …

Contents :

• List of Tables
• List of Figures
• 1 Introduction
  • 1.1 Motivation
  • 1.2 Objectives
  • 1.3 Methodology
  • 1.4 Contributions
  • 1.5 Organization of Thesis
• 2 Optimization and Optimization Approaches
  • 2.1 Optimization
    • 2.1.1 Weighted Sum Method
    • 2.1.2 ε-Constraint Method
    • 2.1.3 Lexicographic Ordering
    • 2.1.4 Goal Programming
    • 2.1.5 Dominance-based Approach
  • 2.2 Fuzzy Logic and Multi-objective Optimization
    • 2.2.1 Fuzzy Set Theory
    • 2.2.2 Fuzzy Reasoning
    • 2.2.3 Linguistic Variables
    • 2.2.4 Fuzzy Rules
    • 2.2.5 Fuzzy Logic System
    • 2.2.6 Common Fuzzy Operators
  • 2.3 Optimization Algorithms
    • 2.3.1 Simulated Annealing
    • 2.3.2 Simulated Evolution
    • 2.3.3 Genetic Algorithms
    • 2.3.4 Non-dominating sorting genetic algorithm II
    • 2.3.5 Particle Swarm Optimization
  • 2.4 MOO performance measures
  • 2.5 Conclusion
• 3 Routing and Open Shortest Path First Protocol
  • 3.1 Routing in Computer Networks
  • 3.2 Routing Information Protocol
  • 3.3 Open Shortest Path First Routing Protocol
  • 3.4 Literature review of the OSPF weight setting problem
  • 3.5 Conclusion
  • 4 Open Shortest Path First Weight Setting Problem
• 4.1 Formal description of OSPFWS Problem
  • 4.1.1 Traffic Load Calculation
  • 4.2 Fuzzy Logic Cost Function for the OSPFWS Problem
  • 4.3 Details of Test Cases
  • 4.4 Conclusion
• 5 Fuzzy Simulated Annealing Algorithm for the OSPFWS Problem
  • 5.1 Fuzzy Simulated Annealing Algorithm
  • 5.2 Solutions Archiving in FSA
  • 5.3 Experimental setup
  • 5.3.1 Comparison of SqalliCF and FuzzyCF using SA
  • 5.4 Conclusion
• 6 Fuzzy Simulated Evolution Algorithm for the OSPFWS Problem
  • 6.1 Fuzzy Simulated Evolution Algorithm
  • 6.2 Experimental setup
  • 6.3 Results and Discussion
  • 6.4 Conclusion
• 7 Particle Swarm Optimization Algorithm Variants and NSGA-II for
  • the OSPFWS Problem
  • 7.1 Fuzzy Particle Swarm Optimization Algorithm
    • 7.1.1 Particle Position and Velocity Representation
    • 7.1.2 Velocity Update
    • 7.1.3 Particle Position Update
    • 7.1.4 Control Parameter Tuning for Fuzzy Particle Swarm Optimization
  • 7.2 Fuzzy Evolutionary Particle Swarm Optimization Algorithm
    • 7.2.1 Control Parameter Tuning for Fuzzy Evolutionary Particle Swarm Optimization
  • 7.3 Weighted Aggregation Particle Swarm Optimization Algorithm
    • 7.3.1 Control Parameter Tuning for Weighted Aggregation Particle Swarm Optimization
  • 7.4 Pareto-dominance Particle Swarm Optimization Algorithm
    • 7.4.1 Control Parameter Tuning for Pareto-dominance Particle Swarm Optimization
  • 7.5 Non-dominating Sorting Genetic Algorithm II
    • 7.5.1 Control Parameter Tuning for Non-dominating Sorting Genetic
  • Algorithm II
  • 7.6 Conclusion
• 8 Empirical Comparison of the Algorithms
  • 8.1 Experimental Setup
  • 8.2 Comparison of Simulated Annealing and Simulated Evolution Algorithms
  • 8.3 Comparison of Fuzzy Particle Swarm Optimization and Fuzzy Evolutionary Particle Swarm Optimization
  • 8.4 Comparison of all the algorithms with respect to diversity
  • 8.5 Comparison of all the algorithms with respect to MOO performance measures
  • 8.6 Conclusion
• 9 Conclusion
  • 9.1 Summary
  • 9.2 Future Research
  • Bibliography
  • Appendix

GET THE COMPLETE PROJECT