Simulated evolution and simulated annealing algorithms for solving multi-objective open shortest path first weight setting problem

Optimal utilization of resources in present-day communication networks is a challenging task. Routing plays an important role in achieving optimal resource utilization. The open shortest path first (OSPF) routing protocol is widely used for routing packets from a source node to a destination node. This protocol assigns weights (or costs) to the links of a network. These weights are used to determine the shortest path between all sources to all destination nodes. Assignment of these weights to the links is classified as an NP-hard problem. This paper formulates the OSPF weight setting problem as a multi-objective optimization problem, with maximum utilization, number of congested links, and number of unused links as the optimization objectives. Since the objectives are conflicting in nature, an efficient approach is needed to balance the trade-off between these objectives. Fuzzy logic has been shown to efficiently solve multi-objective optimization problems. A fuzzy cost function for the OSPF weight setting problem is developed in this paper based on the Unified And-OR (UAO) operator. Two iterative heuristics, namely, simulated annealing (SA) and simulated evolution (SimE) have been implemented to solve the multi-objective OSPF weight setting problem using a fuzzy cost function. Results are compared with that found using other cost functions proposed in the literature (Sqalli et al. in Network Operations and Management Symposium, NOMS, 2006). Results suggest that, overall, the fuzzy cost function performs better than existing cost functions, with respect to both SA and SimE. Furthermore, SimE shows superior performance compared to SA. In addition, a comparison of SimE with NSGA-II shows that, overall, SimE demonstrates slightly better performance in terms of quality of solutions.     

A biased random‐key genetic algorithm for OSPF and DEFT routing to minimize network congestion

Interior gateway routing protocols like Open Shortest Path First (OSPF) and Distributed Exponentially Weighted Flow Splitting (DEFT) send flow through forward links toward the destination node. OSPF routes only on shortest‐weight paths, whereas DEFT sends flow on all forward links, but with an exponential penalty on longer paths. Finding suitable weights for these protocols is known as the weight setting problem (WSP). In this paper, we present a biased random‐key genetic algorithm for WSP using both protocols. The algorithm uses dynamic flow and dynamic shortest path computations. We report computational experiments that show that DEFT achieves less network congestion when compared with OSPF, while, however, yielding larger delays.     

Efficient techniques and tools for intra‐domain traffic engineering

Intra‐domain routing protocols are based on Shortest Path First (SPF) routing, where shortest paths are calculated between each pair of nodes (routers) using pre‐assigned link weights, also referred to as link metric. These link weights can be modified by network administrators in accordance with the routing policies of the network operator. The operator's objective is usually to minimize traffic congestion or minimize total routing costs subject to the traffic demands and the protocol constraints. However, determining a link weight combination that meets a network operator's objectives is a difficult task. In this paper, we study the link weight optimization problem in intra‐domain networks. This problem is proved to be NP‐hard with hard protocol constraints, e.g., a flow is evenly distributed along the shortest paths between its origin and destination nodes. We present two fast heuristic approaches to generate efficient link metrics for intra‐domain routing. Some promising experimental results are reported.     

Distributed routing in packet-switching networks by counterpropagation network

Routing is a problem of considerable importance in a packet-switching network, because it allows both optimization of the transmission speeds available and minimization of the time required to deliver information. In classical centralized routing algorithms, each packet reaches its destination along the shortest path, although some network bandwidth is lost through overheads. By contrast, distributed routing algorithms usually limit the overloading of transmission links, but they cannot guarantee optimization of the paths between source and destination nodes on account of the mainly local vision they have of the problem. The aim of the authors is to reconcile the two advantages of classical routing strategies mentioned above through the use of neural networks. The approach proposed here is one in which the routing strategy guarantees the delivery of information along almost optimal paths, but distributes calculation to the various switching nodes. The article assesses the performance of this approach in terms of both routing paths and efficiency in bandwidth use, through comparison with classical approaches.     

A fuzzy particle swarm optimization algorithm for computer communication network topology design

Particle swarm optimization (PSO) is a powerful optimization technique that has been applied to solve a number of complex optimization problems. One such optimization problem is topology design of distributed local area networks (DLANs). The problem is defined as a multi-objective optimization problem requiring simultaneous optimization of monetary cost, average network delay, hop count between communicating nodes, and reliability under a set of constraints. This paper presents a multi-objective particle swarm optimization algorithm to efficiently solve the DLAN topology design problem. Fuzzy logic is incorporated in the PSO algorithm to handle the multi-objective nature of the problem. Specifically, a recently proposed fuzzy aggregation operator, namely the unified And-Or operator (Khan and Engelbrecht in Inf. Sci. 177: 2692–2711, 2007), is used to aggregate the objectives. The proposed fuzzy PSO (FPSO) algorithm is empirically evaluated through a preliminary sensitivity analysis of the PSO parameters. FPSO is also compared with fuzzy simulated annealing and fuzzy ant colony optimization algorithms. Results suggest that the fuzzy PSO is a suitable algorithm for solving the DLAN topology design problem.     

Algorithms for multicast connection under multi-path routing model

Given a source node and a set of destination nodes in a network, multicast routing problem is usually treated as Steiner tree problem. Unlike this well-known tree based routing model, multicast routing under multi-path model is to find a set of paths rooted at the source node such that in each path at most a fixed number of destination nodes can be designated to receive the data and every destination node must be designated in a path to receive the data. The cost of routing is the total costs of paths found. In this paper we study how to construct a multicast routing of minimal cost under multi-path model. We propose two approximation algorithms for this NP-complete problem with guaranteed performance ratios.     

Loop-free constrained path computation for hop-by-hop QoS routing

We present the distributed multi-constrained routing (DMR) protocol for the computation of constrained paths for QoS routing in computer networks. DMR exploits distance vectors to construct a logical shortest multipath (LSM) for each destination with regard to a given optimization metric, from which a set of non-dominated paths are locally derived at each node. As such DMR is able to find feasible paths as well as optimize the utilization of routing resources.DMR operates in line with the hop-by-hop, connectionless routing model assumed in the IP Internet, and maintains instantaneous loop freedom. Nodes running DMR need not maintain a global view of network state (topology and resource information), and routing updates are sent only to neighboring nodes. This is in sharp contrast with all previous approaches that rely on complete or partial network state for constrained path computation, which incurs excessive communication overhead in large networks and is hard to achieve in practice.     

Energy-aware IP traffic engineering with shortest path routing

Internet energy consumption is rapidly becoming a critical issue due to the exponential traffic growth and the rapid expansion of communication infrastructures worldwide. We address the problem of energy-aware intra-domain traffic engineering in networks operated with a shortest path routing protocol. We consider the problem of switching off (putting in sleep mode) network elements (links and routers) and of adjusting the link weights so as to minimize the energy consumption as well as a network congestion measure. To tackle this multi-objective optimization problem with priority (first minimize the energy consumption and then the network congestion), we propose a Mixed Integer Linear Programming based algorithm for Energy-aware Weights Optimization (MILP-EWO). Our heuristic exploits the Interior Gateway Protocol Weight Optimization (IGP-WO) algorithm for optimizing the OSPF link weights so as to minimize the total cost of link utilization. The computational results obtained for eight real network topologies and different types of traffic matrices show that it is possible to switch off a substantial number of nodes and links during low and moderate traffic periods, while guaranteeing that network congestion is low enough to ensure service quality. The proposed approach is also validated on two networks of emulated Linux routers.     

一种链路不相交的多约束QoS路由算法

针对波分复用技术中的网络路由问题,提出一种满足多个QoS约束的基于链路保护机制的路由算法,该算法通过图论的有关性质得到满足带宽、时延2个QoS约束条件的源与目标节点对间的所有路径及其最短链路不相交相似路径,从而使高实时性网络得到更好的优化。     

Fault-tolerant routing in mesh architectures

It is important for a distributed computing system to be able to route messages around whatever faulty links or nodes may be present. We present a fault-tolerant routing algorithm that assures the delivery of every message as long as there is a path between its source and destination. The algorithm works on many common mesh architectures such as the torus and hexagonal mesh. The proposed scheme can also detect the nonexistence of a path between a pair of nodes in a finite amount of time. Moreover, the scheme requires each node in the system to know only the state (faulty or not) of each of its own links. The performance of the routing scheme is simulated for both square and hexagonal meshes while varying the physical distribution of faulty components. It is shown that a shortest path between the source and destination of each message is taken with a high probability, and, if a path exists, it is usually found very quickly     

基于NPV广义超立方体最佳容错路由算法

在网络可靠性研究中,设计较好的容错路由策略、尽可能多地记录系统中最优通路信息,一直是一项重要的研究工作.超立方体系统的容错路由算法分为可回溯算法和无回溯算法.一般说来,可回溯算法的优点是容错能力强:只要消息的源节点和目的节点有通路,该算法就能够找到把消息传递到目的地的路径;其缺点是在很多情况下传递路径不能按实际存在的最短路径传递.其代表是深度优先搜索(DFS)算法.无回溯算法是近几年人们比较关注的算法.该算法通过记录各邻接节点的故障信息,给路由算法以启发信息,使消息尽可能按实际存在的最短路径传递.这些算法的共同缺点是只能计算出Hamming距离不超过n的路由.在n维超立方体系统连通图中,如果系统存在大量的故障,不少节点对之间的最短路径大于n,因此,这些算法的容错能力差.提出了一个实例说明采用上述算法将遗失60%的路由信息.另外,由于超立方体的结构严格,实际中的真正超立方体系统不多.事实上,不少的网络系统可转换为具有大量错误节点和错误边的超立方体系统.因此,研究能适应具有大量错误节点和错误边的超立方体系统的容错路由算法是一个很有实际价值的工作.研究探讨了:(1) 定义广义超立方体系统;(2) 在超立方体系统中提出了节点通路向量(NPV)概念及其计算规则;(3) 提出了中转点技术,使得求NPV的计算复杂度降低到O(n);(4) 提出了基于NPV的广义超立方体系统最佳容错路由算法(OFTRS),该算法是一种分布式的和基于相邻节点信息的算法.由于NPV记录了超立方体系统全部最优通路和次最优通路的信息,在具有大量故障的情况下,它不会遗漏任何一条最优通路和次最优通路信息,从而实现了高效的容错路由.在这一点上,它优于其他算法.     

Interface split routing for finer-grained traffic engineering

Legacy IP routing restricts the efficacy of traffic engineering solutions. This restriction stems from the constraint that traffic at a node must be uniformly split across all next-hop nodes corresponding to equal cost shortest path to a destination. Proposals that alleviate this constraint either completely overhaul legacy IP routing, or introduce complex control and/or forwarding plane components. This additional complexity departs from the elegant simplicity of legacy routing protocols where statically optimized link weights embed all traffic engineering semantics.

We present Interface Split Routing (ISR), which retains the basic forwarding and control mechanism of legacy IP routing. Furthermore, a set of link weights embed all traffic engineering semantics in ISR. However, ISR makes possible finer-grained traffic engineering by configuring independent sets of next-hops to a destination at each incoming interface. This lends itself well to modern router architectures where each incoming interface has its own forwarding table. Consequently, at the aggregated node level, traffic to a particular destination may be non-uniformly distributed across next-hop nodes. Hence, ISR allows additional flexibility in routing traffic as compared to default IP routing while retaining its simplicity. We conduct simulation studies on representative ISP topologies to compare ISR with traditional link-weight-optimized routing. ISR reduces the difference between optimal routing and weight-optimized routing by 50%.     

A novel paths algebra-based strategy to flexibly solve the link mapping stage of VNE problems

One of the main challenges of network virtualization is the virtual network embedding problem (VNE) that consists of mapping virtual network demands in physical network resources. VNE can be decomposed into two stages: virtual node and virtual link mapping. In the first stage, each virtual node is mapped to a suitable node in the physical network whereas the second stage is in charge of mapping the links connecting virtual nodes to paths in the physical network that suit the virtual network demands.In this paper we propose the utilization of a mathematical multi-constraint routing framework called “paths algebra” to solve the virtual link mapping stage. Paths algebra provides the flexibility to introduce an unlimited number of linear and non-linear constraints and metrics to the problem while finding all the eligible paths in the physical network to perform the virtual link mapping resulting in better and more flexible embeddings.     

Solving shortest path problem using particle swarm optimization

This paper presents the investigations on the application of particle swarm optimization (PSO) to solve shortest path (SP) routing problems. A modified priority-based encoding incorporating a heuristic operator for reducing the possibility of loop-formation in the path construction process is proposed for particle representation in PSO. Simulation experiments have been carried out on different network topologies for networks consisting of 15–70 nodes. It is noted that the proposed PSO-based approach can find the optimal path with good success rates and also can find closer sub-optimal paths with high certainty for all the tested networks. It is observed that the performance of the proposed algorithm surpasses those of recently reported genetic algorithm based approaches for this problem.     

The performance of a hybrid routing intelligent algorithm in a mobile ad hoc network

End-to-end delay, power consumption, and communication cost are some of the most important metrics in a mobile ad hoc network (MANET) when routing from a source to a destination. Recent approaches using the swarm intelligence (SI) technique proved that the local interaction of several simple agents to meet a global goal has a significant impact on MANET routing. In this work, a hybrid routing intelligent algorithm that has an ant colony optimisation (ACO) algorithm and particle swarm optimisation (PSO) is used to improve the various metrics in MANET routing. The ACO algorithm uses mobile agents as ants to identify the most feasible and best path in a network. Additionally, the ACO algorithm helps to locate paths between two nodes in a network and provides input to the PSO technique, which is a metaheuristic approach in SI. The PSO finds the best solution for a particle’s position and velocity and minimises cost, power, and end-to-end delay. This hybrid routing intelligent algorithm has an improved performance when compared with the simple ACO algorithm in terms of delay, power consumption, and communication cost.     

An Integer Programming Algorithm for Routing Optimization in IP Networks

Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination.     

最小割多路径路由算法

在最小割理论基础上提出了最小割多路径(min-cut multi-path,简称MCMP)路由算法,为流量请求选取少量关键路径,并在这些路径间均衡流量,在获得方法易实现性的同时能够有效地控制网络瓶颈链路拥塞通过实际流量数据在北美和欧洲骨干网络中的实验,对比常用的OSPF(open shortest path first)路由算法和模型中的多路径路由算法,MCMP路由算法可降低拥塞链路负载分别达到41％和20％以上.     

基于模糊的多目标粒子群优化算法及应用

粒子群优化算法的思想来源于人工生命和进化计算理论,由于其容易理解、易于实现,在很多领域得到了应用.由于传统的粒子群优化算法无法对多目标优化问题进行求解,因此文中利用模糊理论中的隶属度函数和给定的最优解评估选取原则,提出了一种适合求解约束型多目标优化问题的模糊粒子群算法(FPSO).模糊粒子群算法很好地解决了汽车零部件可靠性稳健优化设计的求解问题,仿真结果证明,该算法可行而有效,同时也拓展了粒子群算法的应用领域.     

Power-aware localized routing in wireless networks

A cost aware metric for wireless networks based on remaining battery power at nodes was proposed for shortest-cost routing algorithms, assuming constant transmission power. Power-aware metrics, where transmission power depends on distance between nodes and corresponding shortest power algorithms were also proposed. We define a power-cost metric based on the combination of both node's lifetime and distance-based power metrics. We investigate some properties of power adjusted transmissions and show that, if additional nodes can be placed at desired locations between two nodes at distance d, the transmission power can be made linear in d as opposed to d^α dependence for α ⩾ 2. This provides basis for power, cost, and power-cost localized routing algorithms where nodes make routing decisions solely on the basis, of location of their neighbors and destination. The power-aware routing algorithm attempts to minimize the total power needed to route a message between a source and a destination. The cost-aware routing algorithm is aimed at extending the battery's worst-case lifetime at each node. The combined power-cost localized routing algorithm attempts to minimize the total power needed and to avoid nodes with a short battery's remaining lifetime. We prove that the proposed localized power, cost, and power-cost efficient routing algorithms are loop-free and show their efficiency by experiments     

Dual paths node-disjoint routing for data salvation in mobile ad hoc

The operational patterns of multifarious backup strategies on AODV-based (Ad-hoc On-Demand Vector) routing protocols are elaborated in this article. To have a broader picture on relevant routing protocols together, variants of AODV-based backup routing protocols are formulated by corresponding algorithms, and also each of them are simulated to obtain the necessary performance metrics for comparisons in terms of packet delivery ratio, average latency delay, and the normalized routing load. Then to make the process of data salvation more efficiently in case of link failure, we explore the possibility of combining the AODV backup routing strategy and on-demand node-disjoint multipath routing protocols. This article proposes an improved approach named DPNR (Dual Paths Node-disjoint Routing) for data salvation, a routing protocol that maintains the only two shortest backup paths in the source and destination nodes. The DPNR scheme can alleviate the redundancy-frames overhead during the process of data salvation by the neighboring intermediate nodes. Our simulation results have demonstrated that DPNR scheme delivers good data delivery performance while restricting the impacts of transmission collision and channel contention. The mathematical rationale for our proposed approach is stated as well.