Traffic engineering and congestion control for open shortest path first networks

Open shortest path first (OSPF) is the most widely used intra-domain Internet routing protocol. The OSPF protocol directs the Internet traffic along the shortest paths that are defined by the links weight. Traffic engineering is responsible for improving the network performance, for instance, the objective function that minimizes the maximal link utilization which is usually adopted to avoid the network congestion. This paper formulates the model of OSPF routing, and further evaluates the performance of different approaches. We also propose a heuristic algorithm to solve the routing problems by optimizing OSPF weights. Computational results indicated that the proposed algorithm could lead to good load balancing, and make efficient utilization of network resources.     

Reliable Ad Hoc Routing Based on Mobility Prediction

Reliability is a very important issue in Mobile Ad hoc NETworks (MANETs). Shortest paths are usually used to route packets in MANETs. However, a shortest path may fail quickly, because some of the wireless links along a shortest path may be broken shortly after the path is established due to mobility of mobile nodes. Rediscovering routes may result in substantial data loss and message exchange overhead. In this paper, we study reliable ad hoc routing in the urban environment. Specifically, we formulate and study two optimization problems. In the minimum Cost Duration-bounded Path (CDP) routing problem, we seek a minimum cost source to destination path with duration no less than a given threshold. In the maximum Duration Cost-bounded Path (DCP) routing problem, we seek a maximum duration source to destination path with cost no greater than a given threshold. We use a waypoint graph to model the working area of a MANET and present an offline algorithm to compute a duration prediction table for the given waypoint graph. An entry in the duration prediction table contains the guaranteed worst-case duration of the corresponding wireless link. We then present an efficient algorithm which computes a minimum cost duration-bounded path, using the information provided in the duration prediction table. We also present a heuristic algorithm for the DCP routing problem. In addition, we show that the proposed prediction and routing schemes can be easily applied for designing reliable ad hoc routing protocols. Simulation results show that our mobility prediction based routing algorithms lead to higher network throughput and longer average path duration, compared with the shortest path routing. This research was supported in part by ARO grant W911NF-04-1-0385 and NSF grant CCF-0431167. The information reported here does not reflect the position or the policy of the federal government.     

Distributed Decisions in Networks: Laboratory Study of Routing Splittable Flow

We study network games in which users choose routes in computerized networks susceptible to congestion. In the “unsplittable” condition, route choices are completely unregulated, players are symmetric, each player controls a single unit of flow and chooses a single origin–destination (O–D) path. In the “splittable” condition, which is the main focus of this study, route choices are partly regulated, players are asymmetric, each player controls multiple units of flow and chooses multiple O–D paths to distribute her fleet. In each condition, users choose routes in two types of network: a basic network with three parallel routes and an augmented network with five routes sharing joint links. We construct and subsequently test equilibrium solutions for each combination of condition and network type, and then propose a Markov revision protocol to account for the dynamics of play. In both conditions, route choice behavior approaches equilibrium and the Braess Paradox is clearly manifested.     

Minimum failure explanations for path vector routing changes

Path vector protocols in routing networks convey entire path information to each destination. When links fail, affected paths are replaced by new paths, and by observing the entire path information, one might hope to infer the failed links that caused these changes. However, inferring the exact topological changes behind observed routing changes may not be possible due to limited information, and the same changes may be explained by more than one set of candidate failures. In this paper, using a simple path vector routing model, we present the problem of finding the candidate set with minimum number of failures to explain observed route changes. We call this problem the minimum e-set problem and present algorithms for solving it optimally for certain cases. We also show that the minimum e-set problem is NP-complete in the general case. This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) under Contract No N66001-04-1-8926 and by National Science Fundation(NSF) under Contract No ANI-0221453. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the DARPA or NSF. Part of the work was done when Akash Nanavati was at DA-IICT, India     

Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios

We consider the design of a multicommodity flow network, in which point-to-point demands are routed across the network subject to link capacity restrictions. Such a design must build enough capacity and diverse routing paths through the network to ensure that feasible multicommodity flows continue to exist, even when components of the network fail. In this paper, we examine several methodologies to optimally design a minimum-cost survivable network that continues to support a multicommodity flow under any of a given set of failure scenarios, where each failure scenario consists of the simultaneous failure of multiple arcs. We begin by providing a single extensive form mixed-integer programming formulation for this problem, along with a Benders decomposition algorithm as an alternative to the extensive form approach. We next investigate strategies to improve the performance of the algorithm by augmenting the master problem with several valid inequalities such as cover constraints, connectivity constraints, and path constraints. For the smallest instances (eight nodes, 10 origin–destination pairs, and 10 failure scenarios), the Benders implementation consumes only 10% of the time required by the mixed-integer programming formulation, and our best augmentation strategy reduces the solution time by another 50%. For medium- and large-sized instances, the extensive form problem fails to terminate within 2 h on any instance, while our decomposition algorithms provide optimal solutions on all but two problem instances.     

Finding disjoint paths with related path costs

We consider routing in survivable networks that provide protection against node or link failures. In these networks resilience against failures is provided by routing connections on pairs of disjoint paths called primary and backup paths. The primary path of a connection carries its traffic under normal circumstances and in the eventuality of a network failure effecting the primary path the connection traffic (all or some portion of it) is rerouted over its backup path. In an online setting as connection requests arrive a pair of disjoint primary and backup paths of least total cost (under some link cost metric) are selected to route the connections. In many situations the cost metric used for the primary path differs from the cost metric used for the backup path. Also in many realistic settings these two cost metrics are related to each other. In this paper we study the problem of finding a pair of edge or node disjoint paths of least total cost where the cost of the primary path is the total cost of its links while the cost for the backup path is α times the sum of the cost of its links, for some given α < 1. We show that the problem is hard to approximate to within a factor for any positive . In addition we show that the problem is complete for a set of hard to approximate problems. On the positive side we show that a simple algorithm achieves an approximation ratio of for the problem.     

Flows with unit path capacities and related packing and covering problems

Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest. Starting from an LP formulation of the maximum s-t-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting (fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For the fractional problem we present an FPTAS that is based on solving the k shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting O(log?m)-approximation algorithm, where m is the number of arcs in the considered graph. For the multicommodity version of the problem there is an $O(\sqrt{m})Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest. Starting from an LP formulation of the maximum s-t-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting (fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For the fractional problem we present an FPTAS that is based on solving the k shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting O(log m)-approximation algorithm, where m is the number of arcs in the considered graph. For the multicommodity version of the problem there is an O(?m)O(\sqrt{m}) -approximation algorithm. We argue that this performance guarantee is best possible, unless P=NP.     

The shortest path improvement problems under Hamming distance

In this paper, we consider the shortest path improvement problems under Hamming distance (SPIH), where the weights of edges can be modified only within given intervals. Two models are considered: the general SPIH problem and the SPIH problem with a single pair of required vertices. For the first problem, we show that it is strongly NP-hard. For the second problem, we show that even if the network is a chain network, it is still NP-hard.This paper is dedicated to Dr. Yong He.     

The weighted link ring loading problem

In the weighted link ring loading problem, we are given an n-node undirected ring network. Each of its links is associated with a weight. Traffic demands are given for each pair of nodes in the ring. The load of a link is the sum of the flows routed through the link, and the weighted load of a link is the product of its weight and the smallest integer not less than its load. The objective of the problem is to find a routing scheme such that the maximum weighted load on the ring is minimized. In this paper we consider three variants: (i) demands may be split into two parts, and then each part is sent in a different direction; (ii) demands are allowed to be split into two parts but restricted to be integrally split; (iii) each demand must be entirely routed in either of the two directions, clockwise or counterclockwise. We first prove that the first variant is polynomially solvable. We then present a pseudo-polynomial time algorithm for the second one. Finally, for the third one, whose NP-hardness can be drawn from the result in the literature, we derive a polynomial-time approximation scheme (PTAS).     

Network Reconfiguration for Increasing Transportation System Resilience Under Extreme Events

Evacuating residents out of affected areas is an important strategy for mitigating the impact of natural disasters. However, the resulting abrupt increase in the travel demand during evacuation causes severe congestions across the transportation system, which thereby interrupts other commuters' regular activities. In this article, a bilevel mathematical optimization model is formulated to address this issue, and our research objective is to maximize the transportation system resilience and restore its performance through two network reconfiguration schemes: contraflow (also referred to as lane reversal) and crossing elimination at intersections. Mathematical models are developed to represent the two reconfiguration schemes and characterize the interactions between traffic operators and passengers. Specifically, traffic operators act as leaders to determine the optimal system reconfiguration to minimize the total travel time for all the users (both evacuees and regular commuters), while passengers act as followers by freely choosing the path with the minimum travel time, which eventually converges to a user equilibrium state. For each given network reconfiguration, the lower‐level problem is formulated as a traffic assignment problem (TAP) where each user tries to minimize his/her own travel time. To tackle the lower‐level optimization problem, a gradient projection method is leveraged to shift the flow from other nonshortest paths to the shortest path between each origin–destination pair, eventually converging to the user equilibrium traffic assignment. The upper‐level problem is formulated as a constrained discrete optimization problem, and a probabilistic solution discovery algorithm is used to obtain the near‐optimal solution. Two numerical examples are used to demonstrate the effectiveness of the proposed method in restoring the traffic system performance.     

Best routes selection in multimodal networks using multi-objective genetic algorithm

In this study, we propose a bi-level multi-objective Taguchi genetic algorithm for a multimodal routing problem with time windows. The mathematic model is constructed, which is featured by two optimal objectives, multiple available transportation manners and different demanded delivery times. After thoroughly analyzing the characteristics of the formulated model, a corresponding bi-level multi-objective Taguchi genetic algorithm is designed to find the Pareto-optimal front. At the upper level, a genetic multi-objective algorithm simultaneously searches the Pareto-optimal front and provides the most feasible routing path choices for the lower level. After generalizing the matrices of costs and time in a multimodal transportation network, the \(k\) -shortest path algorithm is applied to providing some potential feasible paths. A multi-objective genetic algorithm is proposed at the lower level to determine the local optimal combination of transportation manners for these potential feasible paths. To make the genetic algorithm more robust, sounder and faster, the Taguchi (orthogonal) experimental design method is adopted in generating the initial population and the crossover operator. The case study shows that the proposed algorithm can effectively find the Pareto-optimal front solutions and offer series of transportation routes with best combinations of transportation manners. The shipper can easily select the required shipping schemes with specified demands.     

Improving robustness of next-hop routing

A weakness of next-hop routing is that following a link or router failure there may be no routes between some source-destination pairs, or packets may get stuck in a routing loop as the protocol operates to establish new routes. In this article, we address these weaknesses by describing mechanisms to choose alternate next hops. Our first contribution is to model the scenario as the following tree augmentation problem. Consider a mixed graph where some edges are directed and some undirected. The directed edges form a spanning tree pointing towards the common destination node. Each directed edge represents the unique next hop in the routing protocol. Our goal is to direct the undirected edges so that the resulting graph remains acyclic and the number of nodes with outdegree two or more is maximized. These nodes represent those with alternative next hops in their routing paths. We show that tree augmentation is NP-hard in general and present a simple \(\frac{1}{2}\)-approximation algorithm. We also study 3 special cases. We give exact polynomial-time algorithms for when the input spanning tree consists of exactly 2 directed paths or when the input graph has bounded treewidth. For planar graphs, we present a polynomial-time approximation scheme when the input tree is a breadth-first search tree. To the best of our knowledge, tree augmentation has not been previously studied.     

Optimal weight allocation in rooted trees

Some apparently different VLSI circuit design optimization problems can be mapped to the problem of allocating weights (hardware circuits) to the nodes of a tree, such that their total sum (delay) along root-to-leaf paths, or their total product (amplification) along root-to-leaf paths, satisfy given demands (delays or amplifications, respectively) at the tree’s leaves. Node’s weight is shared by all the leaves of its emanating sub-tree. For both the sum and product constraints cases, \(O(n)\) weights allocation algorithms are presented, supplying the demands at the leaves, while the total sum of nodes’ weights (hardware cost) is minimized. When the assignment of the demands to leaves is not predetermined, it is shown that monotonic order of the demands at leaves is optimal for both cases.     

考虑交叉口影响的逆向路段选择优化

逆向车道作为提高路网整体通行能力的一种交通组织策略,已在疏散交通组织中得到了大量应用。以往关于逆向车道设置路段选择的研究,大多没有考虑交叉口影响。在拥挤的城市道路网中,这种忽略会导致过高的预期疏散通行能力估计。本文考虑交叉口影响,建立改进的最大流及其关键边模型,对疏散路网中逆向路段的选择进行优化。将交叉口分转向的通行能力表示为节点的方向性权重,将疏散路网抽象为方向性点权网络。定义该类网络中的最大流增流关键边,即一旦扩容会使网络最大流流值增加幅度最大的边。通过在方向性点权网络中寻找最大流增流关键边,得到考虑交叉口影响时疏散路网中对应的逆向车道设置路段。对经典最大流问题求解算法进行相应的改进,给出方向性点权网络中寻找最大流增流关键边的有效算法,并通过一个数值算例进行测试和仿真分析。结果表明,在考虑交叉口影响的情况下,得到的逆向车道设置路段更为合理,疏散时对其进行扩容能更有效地压缩总疏散时间。     

一种求解时变网络下多式联运最短路的算法

在运输过程中,往往不止有一种运输方式,可能同时有多种运输方式交叉,即可能多式联运的方式存在,不同的运输方式之间需要通过转运才可实现.同时,在运输过程中,成本、运输时间、风险等因素会随着时间的不同而变化.首先,将运输网络进行变形,然后给出了在时变网络条件下多式联运的最短路模型,设计了求解时变条件下多式联运的最短路的算法,利用此算法可以获得从起点到终点之间的最短路,并对算法的计算复杂性进行了分析.最后给出一个应用算例.     

Some inverse min-max network problems under weighted l1 and l∞ norms with bound constraints on changes

We consider some inverse min-max (or max-min) network problems. Such an inverse problem is to modify the weights with bound constraints so that a given feasible solution becomes an optimal solution of a min-max (or max-min) network problem, and the deviation of the weights, measured by the weighted l ₁ norm or weighted l _∞ norm, is minimum. In this paper, we present strongly polynomial time algorithms to solve the inverse min-max spanning tree problem and the inverse maximum capacity path problem.     

基于非概率可靠性的铁路应急设施选址-路径鲁棒优化

鉴于铁路应急设施选址研究中很难合理估计参数的概率分布或确定其隶属函数的问题,将选址-路径问题与区间非概率可靠性方法结合起来,以复杂网络理论为基础,提出网络节点区间权重的确定方法,同时考虑节点权重、边权及径权区间不确定性的共同作用,构建铁路应急设施选址节点加权网络。基于区间非概率可靠性理论及区间运算规则,提出路径的非概率可靠性度量及最优时间可靠度路径选择方法,建立节点权重、边权及径权均为区间数的非概率可靠性铁路应急设施选址-路径鲁棒优化模型,并给出了求解算法,确定了基于区间模型的铁路应急设施鲁棒选址的最优方案。算例表明,本文的优化方案能更好地保证救援的时间鲁棒性,能有效地规避不确定因素波动对设施选址的长期风险,具有很好的实际应用价值。     

Exact and heuristic algorithms for solving the generalized minimum filter placement problem

We consider a problem of placing route-based filters in a communication network to limit the number of forged address attacks to a prescribed level. Nodes in the network communicate by exchanging packets along arcs, and the originating node embeds the origin and destination addresses within each packet that it sends. In the absence of a validation mechanism, one node can send packets to another node using a forged origin address to launch an attack against that node. Route-based filters can be established at various nodes on the communication network to protect against these attacks. A route-based filter examines each packet arriving at a node, and determines whether or not the origin address could be legitimate, based on the arc on which the packet arrives, the routing information, and possibly the destination. The problem we consider seeks to find a minimum cardinality subset of nodes to filter so that the prescribed level of security is achieved. We formulate a mixed-integer programming model for the problem and derive valid inequalities for this model by identifying polynomially-solvable subgraphs of the communication network. We also present three heuristics for solving the filter placement problem and evaluate their performance against the optimal solution provided by the mixed-integer programming model. The authors gratefully acknowledge the comments of two anonymous referees, whose input led to an improved version of this paper. Dr. Smith gratefully acknowledges the support of the Office of Naval Research under Grant #N00014-03-1-0510 and the Defense Advanced Research Projects Agency under Grant #N66001-01-1-8925.     

On the fractionality of the path packing problem

Given an undirected graph G=(N,E), a subset T of its nodes and an undirected graph (T,S), G and (T,S) together are often called a network. A?collection of paths in G whose end-pairs lie in S is called an integer multiflow. When these paths are allowed to have fractional weight, under the constraint that the total weight of the paths traversing a single edge does not exceed 1, we have a fractional multiflow in G. The problems of finding the maximum weight of paths with end-pairs in S over all fractional multiflows in G is called the fractional path packing problem. In 1989, A. Karzanov had defined the fractionality of the fractional path packing problem for a class of networks {G,(T,S)} as the smallest natural D such that for any network from the class, the fractional path packing problem has a solution which becomes integer-valued when multiplied by D (see A.?Karzanov in Linear Algebra Appl. 114–115:293–328, 1989). He proved that the fractional path packing problem has infinite fractionality outside a very specific class of networks, and conjectured that within this class, the fractionality does not exceed 4. A.?Karzanov also proved that the fractionality of the path packing problem is at most 8 by studying the fractionality of the dual problem. Special cases of Karzanov’s conjecture were proved in or are implied by the works of L.R.?Ford and D.R.?Fulkerson, Y.?Dinitz, T.C.?Hu, B.V.?Cherkassky, L.?Lov?sz and H.?Hirai. We prove Karzanov’s conjecture by showing that the fractionality of the path packing problem is at most 4. Our proof is stand-alone and does not rely on Karzanov’s results.     

一种求解时变条件下有宵禁限制最短路的算法

在组合优化过程中,往往需要获得从起点到终点之间的最短路.由于道路、天气、交通条件等因素的影响,使得网络具有很强的时变特性.同时,对于网络中的节点往往有宵禁的限制.对时变条件下有宵禁限制并有到达时间限制的最短路进行了研究,建立了软、硬宵禁限制下的数学模型,给出并证明了时变条件下获得有宵禁限制最短路的最优条件,并设计了求解的多项式算法,通过此算法可以获得时变条件下有宵禁限制的最短路.同时,算法和模型还考虑了不同的起点出发时间,使路径决策者可以根据自身的情况,选择合适的出发时间和路径.最后给出了一个应用算例,分析了宵禁对于获得的最短路的影响.