A Genetic Algorithm for the Weight Setting Problem in OSPF Routing

With the growth of the Internet, Internet Service Providers (ISPs) try to meet the increasing traffic demand with new technology and improved utilization of existing resources. Routing of data packets can affect network utilization. Packets are sent along network paths from source to destination following a protocol. Open Shortest Path First (OSPF) is the most commonly used intra-domain Internet routing protocol (IRP). Traffic flow is routed along shortest paths, splitting flow at nodes with several outgoing links on a shortest path to the destination IP address. Link weights are assigned by the network operator. A path length is the sum of the weights of the links in the path. The OSPF weight setting (OSPFWS) problem seeks a set of weights that optimizes network performance. We study the problem of optimizing OSPF weights, given a set of projected demands, with the objective of minimizing network congestion. The weight assignment problem is NP-hard. We present a genetic algorithm (GA) to solve the OSPFWS problem. We compare our results with the best known and commonly used heuristics for OSPF weight setting, as well as with a lower bound of the optimal multi-commodity flow routing, which is a linear programming relaxation of the OSPFWS problem. Computational experiments are made on the AT&T Worldnet backbone with projected demands, and on twelve instances of synthetic networks.     

On optimal placement of relay nodes for reliable connectivity in wireless sensor networks

The paper addresses the relay node placement problem in two-tiered wireless sensor networks. Given a set of sensor nodes in Euclidean plane, our objective is to place minimum number of relay nodes to forward data packets from sensor nodes to the sink, such that: 1) the network is connected, 2) the network is 2-connected. For case one, we propose a (6+ε)-approximation algorithm for any ε > 0 with polynomial running time when ε is fixed. For case two, we propose two approximation algorithms with (24+ε) and (6/T+12+ε), respectively, where T is the ratio of the number of relay nodes placed in case one to the number of sensors. We further extend the results to the cases where communication radiuses of sensor nodes and relay nodes are different from each other.     

Efficient algorithms for shared backup allocation in networks with partial information

We study efficient algorithms for establishing reliable connections with bandwidth guarantees in communication networks. In the normal mode of operation, each connection uses a primary path to deliver packets from the source to the destination. To ensure continuous operation in the event of an edge failure, each connection uses a set of backup bridges, each bridge protecting a portion of the primary path. To meet the bandwidth requirement of the connection, a certain amount of bandwidth must be allocated the edges of the primary path, as well as on the backup edges. In this paper, we focus on minimizing the amount of required backup allocation by sharing backup bandwidth among different connections. We consider efficient sharing schemes that require only partial information about the current state of the network. Specifically, the only information available for each edge is the total amount of primary allocation and the cost of allocating backup bandwidth on this edge. We consider the problem of finding a minimum cost backup allocation together with a set of bridges for a given primary path. We prove that this problem is NP-hard and present an approximation algorithm whose performance is within of the optimum, where n is the number of edges in the primary path. We also consider the problem of finding both a primary path and backup allocation of minimal total cost. A preliminary version of this paper appears in the Proceedings of 13th Annual European Symposium on Algorithms - ESA 2005, Mallorca, Spain. J. (Seffi) Naor: This research is supported in part by a foundational and strategical research grant from the Israeli Ministry of Science, and by a US-Israel BSF Grant 2002276.     

Using branch-and-price approach to solve the directed network design problem with relays

We present node-arc and arc-path formulations, and develop a branch-and-price approach for the directed network design problem with relays (DNDR). The DNDR problem can be used to model many network design problems in transportation, service, and telecommunication system, where relay points are necessary. The DNDR problem consists of introducing a subset of arcs and locating relays on a subset of nodes such that in the resulting network, the total cost (arc cost plus relay cost) is minimized, and there exists a directed path linking the origin and destination of each commodity, in which the distances between the origin and the first relay, any two consecutive relays, and the last relay and the destination do not exceed a predefined distance limit. With the node-arc formulation, we can directly solve small DNDR instances using mixed integer programming solver. With the arc-path formulation, we design a branch-and-price approach, which is a variant of branch-and-bound with bounds provided by solving linear programs using column generation at each node of the branch-and-bound tree. We design two methods to efficiently price out columns and present computational results on a set of 290 generated instances. Results demonstrate that our proposed branch-and-price approach is a computationally efficient procedure for solving the DNDR problem.     

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.     

The P-Hub maximal covering problem and extensions for gradual decay functions

The p-hub maximal covering problem aims to find the best locations for hubs so as to maximize demands within a coverage distance with a predetermined number of hubs. Classically, the problem is defined in the framework of binary coverage only; an origin–destination pair is covered if the cost (time, etc.) is lower than the critical value, and not covered at all if the cost is greater than the critical value. In this paper, we extend the definition of coverage, introducing “partial coverage”, which changes with distance. We present new and efficient mixed-integer programming models that are also valid for partial coverage for single and multiple allocations. We present and discuss the computational results with different data sets.     

Transport schemes for topology-transparent scheduling

Transport protocols provide reliable, end-to-end communication between a source and a destination in a network. The Transmission Control Protocol (TCP) uses backward error correction, where the destination explicitly returns feedback to the source. Forward error correction (FEC) can also be used for transport; here the source includes enough redundancy in the encoding symbols to allow the destination to decode the message. In this paper, we compare the performance of two transport schemes, TCP and LT, a scheme based on rateless FEC codes, in a wireless ad hoc network when topology-transparent scheduling is used for channel access. These schedules are derived from cover-free families, a type of combinatorial design. They provide a mechanism to guarantee collision-free communication between any two nodes provided that each of the N nodes of the network has at most a specified number D of active (transmitting) neighbours. We find that LT outperforms TCP in more strenuous network conditions. To Frank Hwang on the occasion of his sixty-fifth birthday.     

Bounded information dissemination in multi-channel wireless networks

More and more wireless networks and devices now operate on multiple channels, which poses the question: How to use multiple channels to speed up communication? In this paper, we answer this question for the case of wireless ad-hoc networks where information dissemination is a primitive operation. Specifically, we propose a randomized distributed algorithm for information dissemination that is very near the optimal. The general information dissemination problem is to deliver \(k\) information packets, stored initially in \(k\) different nodes (the packet holders), to all the nodes in the network, and the objective is to minimize the time needed. With an eye toward the reality, we assume a model where the packet holders are determined by an adversary, and neither the number \(k\) nor the identities of packet holders are known to the nodes in advance. Not knowing the value of \(k\) sets this problem apart from broadcasting and all-to-all communication (gossiping). We study the information dissemination problem in single-hop networks with bounded-size messages. We present a randomized algorithm which can disseminate all packets in \(O(k(\frac{1}{\mathcal {F}}+\frac{1}{\mathcal {P}})+\log ^2n)\) rounds with high probability, where \(\mathcal {F}\) is the number of available channels and \(\mathcal {P}\) is the bound on the number of packets a message can carry. Compared with the lower bound \(\varOmega (k(\frac{1}{\mathcal {F}}+\frac{1}{\mathcal {P}}))\), the given algorithm is very close to the asymptotical optimal except for an additive factor. Our result provides the first solid evidence that multiple channels can indeed substantially speed up information dissemination, which also breaks the \(\varOmega (k)\) lower bound that holds for single-channel networks (even if \(\mathcal {P}\) is infinity).     

Reliability evaluation of a multicast over coded packet networks

Network coding is a generalization of conventional routing methods that allows a network node to code information flows before forwarding them. While it has been theoretically proved that network coding can achieve maximum network throughput, theoretical results usually do not consider the stochastic nature in information processing and transmission, especially when the capacity of each arc becomes stochastic due to failure, attacks, or maintenance. Hence, the reliability measurement of network coding becomes an important issue to evaluate the performance of the network under various system settings. In this paper, we present analytical expressions to measure the reliability of multicast communications in coded networks, where network coding is most promising. We define the probability that a multicast rate can be transmitted through a coded packet network under a total transmission cost constraint as the reliability metric. To do this, we first introduce an exact mathematical formulation to construct multicast connections over coded packet networks under a limited transmission cost. We then propose an algorithm based on minimal paths to calculate the reliability measurement of multicast connections and analyze the complexity of the algorithm. Our results show that the reliability of multicast routing with network coding improved significantly compared to the case of multicast routing without network coding.     

Route vs. Segment: An Experiment on Real‐Time Travel Information in Congestible Networks

We report the results of an experimental study of route choice in congestible networks with a common origin and common destination. In one condition, in each round of play network users independently committed themselves at the origin to a three‐segment route; in the other condition, they chose route segments sequentially at each network junction upon receiving en route information. At the end of each round, players received ex‐post complete information about the distribution of the route choices. Although the complexity of the network defies analysis by common users, traffic patterns in both conditions converged rapidly to the equilibrium solution. We account for the observed results by a Markov adaptive learning model postulating regret minimization and inertia. We find that subjects' learning behavior was similar across conditions, except that they exhibited more inertia in the condition with en route information.     

On the online multi-agent O–D <Emphasis Type="Italic">k</Emphasis>-Canadian Traveler Problem

In this article, we present new results on the online multi-agent O–D k-Canadian Traveler Problem, in which there are multiple agents and an input graph with a given source node O and a destination node D together with edge costs such that at most k edges are blocked. The blocked edges are not known a priori and are not recoverable. All of the agents are initially located at O. The objective is to find an online strategy such that at least one of the agents finds a route from the initial location O to a given destination D with minimum total cost. We focus on the case where communication among the agents is limited in the sense that some travelers can both send and receive information while the others can only receive information. We formalize the definition of agents’ intelligence by specifying three levels. We introduce two online strategies which utilize higher levels of agents’ intelligence to provide updated lower bounds to this problem. We show that one of our strategies is optimal in both cases with complete and limited communication in the special case of O–D edge-disjoint graphs and highest level of agents’ intelligence.     

Scheduling Packets with Values and Deadlines in Size-Bounded Buffers

Motivated by providing quality-of-service differentiated services in the Internet, we consider buffer management algorithms for network switches. We study a multi-buffer model. A network switch consists of multiple size-bounded buffers such that at any time, the number of packets residing in each individual buffer cannot exceed its capacity. Packets arrive at the network switch over time; they have values, deadlines, and designated buffers. In each time step, at most one pending packet is allowed to be sent and this packet can be from any buffer. The objective is to maximize the total value of the packets sent by their respective deadlines. A 9.82-competitive online algorithm (Azar and Levy in Lect Notes Comput Sci 4059:5–16 2006) and a 4.73-competitive online algorithm (Li in Lect Notes Comput Sci 5564:265–278, 2009) have been provided for this model, but no offline algorithms have yet been described. In this paper, we study the offline setting of the multi-buffer model. Our contributions include a few optimal offline algorithms for some variants of the model. Each variant has its unique and interesting algorithmic feature.     

Minimum power assignment in wireless ad hoc networks with spanner property

Power assignment for wireless ad hoc networks is to assign a power for each wireless node such that the induced communication graph has some required properties. Recently research efforts have focused on finding the minimum power assignment to guarantee the connectivity or fault-tolerance of the network. In this paper, we study a new problem of finding the power assignment such that the induced communication graph is a spanner for the original communication graph when all nodes have the maximum power. Here, a spanner means that the length of the shortest path in the induced communication graph is at most a constant times of the length of the shortest path in the original communication graph. Polynomial time algorithm is given to minimize the maximum assigned power with spanner property. The algorithm also works for any other property that can be tested in polynomial time and is monotone. We then give a polynomial time approximation method to minimize the total transmission radius of all nodes. Finally, we propose two heuristics and conduct extensive simulations to study their performance when we aim to minimize the total assigned power of all nodes. The author is partially supported by NSF CCR-0311174.     

An online distributed gossiping protocol for mobile networks

Gossiping in a communication network has long been studied as a combinatorial optimization problem in graphs under many different objective functions and communication models. In this paper, we propose a new online distributed gossiping protocol in the multicasting communication environment, where each node knows only its immediate neighbors. We show that the protocol can tolerate multiple node and link faults, mobility of nodes in the network (as long as the network remains connected) and it is more efficient than the a recently proposed protocol. The research reported in this paper is supported by NSF grant # ANI-0218495.     

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.     

Decision Support System of Truck Routing and Refueling: A Dual‐Objective Approach

The variable‐route vehicle‐refueling problem (VRVRP) is a variant of the network‐flow problem which seeks, for a vehicle traveling from origin s to destination d, both the route and the refueling policy (sequence of fuel stations to use between s and d) that jointly minimize the fuel cost of operating the vehicle. Commercial‐grade decision support systems that solve the VRVRP are widely used by motor carriers, but they provide heuristic solutions only. Exact methods are available from the academic side, but because they focus on minimizing costs, they tend to cut fuel costs in exchange for increased vehicle miles (which can increase fuel consumptions and pollutants emission). We propose a new approach to the VRVRP that allows carriers to jointly seek the two possibly conflicting goals; minimizing fuel cost and vehicle miles. Computational testing shows that our approach (i) outperforms the commercial software products in both goals, and (ii) finds solutions that require significantly less vehicle miles than those given by the exact method proposed in the academic literature, without incurring unacceptable increases in fuel cost.     

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.     

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.     

The k-Canadian Travelers Problem with communication

This paper studies a variation of the online k-Canadian Traveler Problem (k-CTP), in which there are multiple travelers who can communicate with each other, to share real-time blockage information of the edges. We study two different communication levels for the problem, complete communication (where all travelers can receive and send blockage information with each other) and limited communication (where only some travelers can both receive and send information while the others can only receive information). The objective is that at least one traveler finds a feasible route from the origin to the destination with as small cost as possible. We give lower bounds on the competitive ratio for both the two communication levels. Considering the urban traffic environment, we propose the Retrace-Alternating strategy and Greedy strategy for both the two communication levels, and prove that increasing the number of travelers with complete communication ability may not always improve the competitive ratio of online strategies.     

Communicating with the Public About Marauding Terrorist Firearms Attacks: Results from a Survey Experiment on Factors Influencing Intention to “Run,Hide, Tell” in the United Kingdom and Denmark

Effective risk communication is an integral part of responding to terrorism, but until recently, there has been very little pre‐event communication in a European context to provide advice to the public on how to protect themselves during an attack. Following terrorist attacks involving mass shootings in Paris, France, in November 2015, the U.K. National Police Chiefs’ Council released a Stay Safe film and leaflet that advises the public to “run,” “hide,” and “tell” in the event of a firearms or weapons attack. However, other countries, including Denmark, do not provide preparedness information of this kind, in large part because of concern about scaring the public. In this survey experiment, 3,003 U.K. and Danish participants were randomly assigned to one of three conditions: no information, a leaflet intervention, and a film intervention to examine the impact of “Run, Hide, Tell” advice on perceptions about terrorism, the security services, and intended responses to a hypothetical terrorist firearms attack. Results demonstrate important benefits of pre‐event communication in relation to enhancing trust, encouraging protective health behaviors, and discouraging potentially dangerous actions. However, these findings also suggest that future communications should address perceived response costs and target specific problem behaviors. Cross‐national similarities in response suggest this advice is suitable for adaptation in other countries.