基于自适应遗传算法的OSPF链路权重优化

在综合考虑链路利用率、链路流量与剩余带宽的基础上,提出了OSPF链路权重优化目标函数,建立了优化数学模型,并设计了自适应遗传算法对其进行求解。实验结果显示提出的优化目标函数在满足给定流量要求的前提下,可以减少链路上的总流量;在网络流量较大时,能够均衡网络内负载分布,提高网络总吞吐量。     

最小割多路径路由算法

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

Parallel Algorithms for Dynamic Shortest Path Problems

The development of intelligent transportation systems (ITS) and the resulting need for the solution of a variety of dynamic traffic network models and management problems require faster‐than‐real‐time computation of shortest path problems in dynamic networks. Recently, a sequential algorithm was developed to compute shortest paths in discrete time dynamic networks from all nodes and all departure times to one destination node. The algorithm is known as algorithm DOT and has an optimal worst‐case running‐time complexity. This implies that no algorithm with a better worst‐case computational complexity can be discovered. Consequently, in order to derive algorithms to solve all‐to‐one shortest path problems in dynamic networks, one would need to explore avenues other than the design of sequential solution algorithms only. The use of commercially‐available high‐performance computing platforms to develop parallel implementations of sequential algorithms is an example of such avenue. This paper reports on the design, implementation, and computational testing of parallel dynamic shortest path algorithms. We develop two shared‐memory and two message‐passing dynamic shortest path algorithm implementations, which are derived from algorithm DOT using the following parallelization strategies: decomposition by destination and decomposition by transportation network topology. The algorithms are coded using two types of parallel computing environments: a message‐passing environment based on the parallel virtual machine (PVM) library and a multi‐threading environment based on the SUN Microsystems Multi‐Threads (MT) library. We also develop a time‐based parallel version of algorithm DOT for the case of minimum time paths in FIFO networks, and a theoretical parallelization of algorithm DOT on an ‘ideal’ theoretical parallel machine. Performances of the implementations are analyzed and evaluated using large transportation networks, and two types of parallel computing platforms: a distributed network of Unix workstations and a SUN shared‐memory machine containing eight processors. Satisfactory speed‐ups in the running time of sequential algorithms are achieved, in particular for shared‐memory machines. Numerical results indicate that shared‐memory computers constitute the most appropriate type of parallel computing platforms for the computation of dynamic shortest paths for real‐time ITS applications.     

Better Alternatives to OSPF Routing

The current standard for intra-domain network routing, Open Shortest Path First (OSPF), suffers from a number of problems-the tunable parameters (the weights) are hard to optimize, the chosen paths are not robust under changes in traffic or network state, and some network links are over-used at the expense of others. We present prototypical scenarios that illustrate these problems. Then we propose several variants of a protocol to eliminate or alleviate them and demonstrate the improvements in performance under those scenarios. We also prove that these protocols never perform significantly worse than OSPF and show that for at least a limited class of network topologies, it is possible to find efficiently the optimal weight settings. Some of the problems with OSPF are well known; indeed, there are several routing protocols that perform better than OSPF in routing quality (i.e., in terms of congestion, delay, etc.). OSPF’s popularity persists in part because of its efficiency with respect to several resource bounds. In contrast, many competing protocols that provide routing superior to OSPF are computationally prohibitive. Motivated by this consideration, we designed our protocols not only to achieve better routing quality than OSPF, but also to use resources in amount comparable with OSPF with respect to offline broadcast communication, size of and time to compute routing tables, packet delivery latency, and packet header structure and size.     

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.     

Fuzzy particle swarm optimization algorithms for the open shortest path first weight setting problem

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.     

Fault-tolerant routing over shortest node-disjoint paths in hypercubes

This paper presented a routing algorithm that finds n disjoint shortest paths from the source node s to target node d in the n-dimensional hypercube. Fault-tolerant routing over all shortest node-disjoint paths has been investigated to overcome the failure encountered during routing in hypercube networks. In this paper, we proposed an efficient approach to provide fault-tolerant routing which has been investigated on hypercube networks. The proposed approach is based on all shortest node-disjoint paths concept in order to find a fault-free shortest path among several paths provided. The proposed algorithm is a simple uniform distributed algorithm that can tolerate a large number of process failures, while delivering all n messages over optimal-length disjoint paths. However, no distributed algorithm uses acknowledgement messages (acks) for fault tolerance. So, for dealing the faults, acknowledgement messages (acks) are included in the proposed algorithm for routing messages over node-disjoint paths in a hypercube network.     

Providing QoS in OSPF based best effort network using load sensitive routing

In an open shortest path first (OSPF) based best effort network, when a packet experiences congestion, the routing subsystem cannot send it through an alternate path. Thus, it fails to provide desired quality of service (QoS) during congestion. In order to provide QoS we have reported three different load sensitive routing (LSR) protocols in [A. Sahoo, An OSPF based load-sensitive QoS routing algorithm using alternate paths, in: IEEE International Conference on Computer Communication Networks, October 2002; A. Tiwari, A. Sahoo, Providing QoS support in OSPF based best effort network, in: IEEE International Conference on Networks, November 2005; A. Tiwari, A. Sahoo, A local coefficient based load sensitive routing protocol for providing QoS, in: IEEE International Conference on Parallel and Distributed Systems, July 2006]. The LSR protocol forwards packets through alternate paths in case of congestion. The number of alternate paths at any node depends on the value of operating parameter or coefficient used for alternate path calculation. Though the basic protocol in these cases was the same, the methods of choosing operating parameter were different. We referred to these three methods as LSR [A. Sahoo, An OSPF based load-sensitive QoS routing algorithm using alternate paths, in: IEEE International Conference on Computer Communication Networks, October 2002], E-LSR [A. Tiwari, A. Sahoo, Providing QoS support in OSPF based best effort network, in: IEEE International Conference on Networks, November 2005] and L-LSR [A. Tiwari, A. Sahoo, A local coefficient based load sensitive routing protocol for providing QoS, in: IEEE International Conference on Parallel and Distributed Systems, July 2006] coefficient methods. In this paper, we present the LSR protocol along with the three coefficient calculation methods pointing out the reason for going from one method to the next. The main strength of our LSR protocol is that it provides loop free alternate paths in the event of congestion and can interwork with routers running vanilla OSPF protocol. We show through simulation that the LSR protocol based on any of the three different coefficient calculation methods performs much better than OSPF and that out of the three methods proposed by us, L-LSR performs the best.     

A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs

In this paper we give a fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks. Given an error parameter such that , our algorithm maintains approximate all-pairs shortest paths in an undirected planar graph G with nonnegative edge lengths. The approximate paths are guaranteed to be accurate to within a 1+ factor. The time bounds for both query and update for our algorithm is O( ^-1 n ^2/3 log ² n log D) , where n is the number of nodes in G and D is the sum of its edge lengths. The time bound for the queries is worst case, while that for the additions is amortized. Our approximation algorithm is based upon a novel technique for approximately representing all-pairs shortest paths among a selected subset of the nodes by a sparse substitute graph. Received January 1995; revised February 1997.     

On open shortest path first related network optimisation problems

The paper deals with flow allocation problems in IP networks using open shortest path first (OSPF) routing. Its main purpose is to discuss and propose methods for finding settlements of OSPF link weight system realising the assumed demand pattern for the given network resources (links capacities). Such settlements can result in a significantly better network performance, as compared with the simplified weight setting heuristics typically used nowadays. Although the configuration of the link weight system is primarily done in the network planning phase, still additional re-optimisations are feasible, and in fact essential, in order to cope with major changes in traffic conditions and with major resources’ failures and rearrangements.

The paper formulates a relevant OSPF routing optimisation problem, proves its NP-completeness, and discusses possible heuristic approaches and related optimisation methods for solving it. Two basic approaches are considered (the direct approach and the two-phase approach) and the resulting optimisation algorithms are presented. The considerations are illustrated with numerical results.     

OSPF在按需电路上配置的研究与应用

OSPF是个链接状态路由协议,在同一层的区域内与其它所有路由器交换链接状态公告（LSA）信息。OSPF的LSA中包含连接的接口、使用的metric及其它的变量信息。OSPF路由器积累链接状态信息,并使用SPF算法来计算到各节点的最短路径。OSPF不但已成为目前Internet广域网和Intranet企业网采用最多、应用最广泛的路由协议之一,而且在综合业务数字网（ISDN）、X.25交换式虚电路（SVC）和拨号线路等应用广泛,故OSPF在按需电路上的配置成为目前极为关注的问题。     

基于Floyd算法的多重最短路问题的改进算法

路径分析是网络分析最基本的问题,其核心是对最短路径的求解。Floyd算法是一种求取最短路的经典算法。分析发现,两点间可能存在多条权重相同的最短路径,而这一点Floyd算法没有涉及。以无向联通图为研究对象,设计了基于Floyd求解多重等价最短路算法,并分析计算了一个实际算例。计算结果表明,基于Floyd的多重等价最短路算法可以有效解决多重等价最短路问题。     

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.     

量子密钥分发网络端端密钥协商最优路径选择算法

针对量子密钥分发(QKD)网络端端密钥协商路径选择问题,设计了一种基于改进Dijkstra算法的端端密钥协商最优路径选择算法。首先,基于有效路径策略,剔除网络中的失效链路;然后,基于最短路径策略,通过改进Dijkstra算法,得到密钥消耗最少的多条最短路径;最后,基于最优路径策略,从多条最短路径中选择一条网络服务效率最高的最优路径。分析结果表明,该算法很好地解决了最优路径不唯一、最优路径非最短、最优路径非最优等问题,可以降低QKD网络端端密钥协商时密钥消耗量,提高网络服务效率。     

网络最短路问题的改进算法

本文着重研究著名的Dijkstra网络最短路算法的实现效率，提出算法实现的若干技巧，大大提高了Dijkstra最短路算法的适用性和时间空间效率。     

动态容量网络中的最小最大时间流问题

动态(时间依赖的)容量网络与传统静态网络相比更具现实意义,在交通网络、物流网络和通信网络中都有着广泛的应用。在时间依赖网络最短路算法的基础上,研究具有实际背景的动态容量网络的最小最大时间流问题,给出求动态容量网络的最小最大时间流的多项式算法和算法的应用实例,其时间复杂度为O(mMv)。     

基于优化链路权值的域内路由保护方案

目前,互联网部署的域内链路状态路由协议,如开放最短路径优先(Open Shortest Path First,OSPF)和中间系统到中间系统(Intermediate System-to-Intermediate System,IS-IS),采用被动恢复方案应对网络故障。随着网络的发展,大量的实时应用部署在互联网上,OSPF的收敛时间无法满足这些实时应用对收敛时间的需求。因此,学术界和工业界提出采用路由保护方案来应对网路中出现的故障。然而,已有的路由保护方案存在两个方面的问题:1)默认路径和备份路径的交叉度较高,如LFA；2)为了计算两条交叉度低的路径,对默认路径加以限制,即默认路径不采用最短路径,如Color Tree。为了解决上述两个问题,首先将上述问题归结为整数规划模型,接着利用启发式方法计算近似最优解,最后在实际网络和模拟网络中对所提算法进行了大量实验。实验结果表明,所提算法可以降低默认路径和备份路径的交叉度,极大地提高网络的可用性。     

一种基于OSPF扩展的预计算QoS路由算法研究

在一个MPLS域,LSPs的建立需要QoS路由协议分发QoS相关的信息和执行QoS路径选择,但是传统的OSPF不支持QoS路由。本文提出并详细讨论了一种0SPF-QoSR路由机制,它是对OSPF路由协议的扩展,基于网络的动态可用带宽资源和流的QoS请求来决定流的QoS LSPs。仿真证明,该机制在丢包率、链路利用率、延时方面的性能优于只考虑最短路径的OSPF。     

改进蚂蚁算法在网络流量平衡中的研究

在分析了当前蚂蚁算法实现网络流量负载重配置的基础上,提出了新的网络链路资源分配策略及改进算法,利用蚂蚁具有找到最短路径及不同种类蚂蚁互相排斥的这一天然特性,很容易在最短路由和链路负载之间取得折中。仿真结果表明,改进的蚂蚁算法对业务请求越是频繁的情况,其负载平衡度和业务到达率越优于其他算法。     

所有最短路径的求解算法

本文提出了一种求所有最短路径的算法,能高效地求出一个顶点到其它各顶点的所有最短路径。此外,我们用C语言设计的相应程序验证了此算法。