Routing complexity of faulty networks

One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This article investigates how big the failure probability can be, before the capability to efficiently find a path in the network is lost. Our main results show tight upper and lower bounds for the failure probability, which permits routing both for the hypercube and for the d‐dimensional mesh. We use tools from percolation theory to show that in the d‐dimensional mesh, once a giant component appears—efficient routing is possible. A different behavior is observed when the hypercube is considered. In the hypercube there is a range of failure probabilities in which short paths exist with high probability, yet finding them must involve querying essentially the entire network. Thus the routing complexity of the hypercube shows an asymptotic phase transition. The critical probability with respect to routing complexity lies in a different location than that of the critical probability with respect to connectivity. Finally we show that an oracle access to links (as opposed to local routing) may reduce significantly the complexity of the routing problem. We demonstrate this fact by providing tight upper and lower bounds for the complexity of routing in the random graph G_n,p. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Branch-and-price-and-cut algorithms for solving the reliable <Emphasis Type="Italic">h</Emphasis>-paths problem

We examine a routing problem in which network arcs fail according to independent failure probabilities. The reliable h-path routing problem seeks to find a minimum-cost set of h ≥ 2 arc-independent paths from a common origin to a common destination, such that the probability that at least one path remains operational is sufficiently large. For the formulation in which variables are used to represent the amount of flow on each arc, the reliability constraint induces a nonconvex feasible region, even when the integer variable restrictions are relaxed. Prior arc-based models and algorithms tailored for the case in which h = 2 do not extend well to the general h-path problem. Thus, we propose two alternative integer programming formulations for the h-path problem in which the variables correspond to origin-destination paths. Accordingly, we develop two branch-and-price-and-cut algorithms for solving these new formulations, and provide computational results to demonstrate the efficiency of these algorithms.     

Packet routing and job-shop scheduling inO(congestion+dilation) steps

In this paper, we prove that there exists a schedule for routing any set of packets with edge-simple paths, on any network, inO(c+d) steps, wherec is the congestion of the paths in the network, andd is the length of the longest path. The result has applications to packet routing in parallel machines, network emulations, and job-shop scheduling.This research was conducted while the authors were at MIT. Support was provided by the Defense Advanced Research Projects Agency under Contract N00014-87-K-825, the Office of Naval Research under Contract N00014-86-K-0593, the Air Force under Contract OSR-86-0076, and the Army under Contract DAAL-03-86-K-0171. Tom Leighton is supported by an NSF Presidential Young Investigator Award with matching funds provided by IBM.     

Spare routing problem with p minimal paths for time-based stochastic flow networks

A time-based stochastic flow network (TBSFN), in which each arc has several possible capacities/states and a lead time, is addressed to discuss the system reliability of spare routing for a computer network. The minimum transmission time to send a given amount of data through a single minimal path is uncertain. Although the transmission time will be shortened even if the data are sent through p (p > 1) disjoint minimal paths simultaneously, it is still variable in a TBSFN. This paper is concerned with evaluating the probability that a specified amount of data can be sent through p minimal paths simultaneously within a time threshold. Such a probability is named the system reliability, which can be treated as a performance index for measuring the transmission ability. We present an efficient methodology to assess the system reliability. Furthermore, a spare routing for boosting the system reliability is established in advance to indicate the main and spare p minimal paths. Subsequently, the system reliability of the spare routing can be computed easily, which shows the contribution of the spare design. From the viewpoint of decision support, we may conduct the sensitive analysis to find out the most important arc which will increase/decrease the system reliability most significantly.     

Finding Optimal Routings in Hamming Graphs

A routing R in a graph consists of a simple path p_uvfromu to v for each ordered pair of distinct vertices (u, v). We will call R optimal if all the paths p_uvare shortest paths and if edges of the graph occur equally often in the paths of R. In 1994, Solé gave a sufficient condition involving the automorphism group for a graph to have an optimal routing in this sense. Graphs which satisfy Solé’s condition are called orbital regular graphs. It is often difficult to determine whether or not a given graph is orbital regular. In this paper, we give a necessary and sufficient condition for a Hamming graph to be orbital regular with respect to a certain natural subgroup of automorphisms.     

Optimal paths in bi-attribute networks with fractional cost functions

An important routing problem is to determine an optimal path through a multi-attribute network which minimizes a cost function of path attributes. In this paper, we study an optimal path problem in a bi-attribute network where the cost function for path evaluation is fractional. The problem can be equivalently formulated as the “bi-attribute rational path problem” which is known to be NP-complete. We develop an exact approach to find an optimal simple path through the network when arc attributes are non-negative. The approach uses some path preference structures and elimination techniques to discard, from further consideration, those (partial) paths that cannot be parts of an optimal path. Our extensive computational results demonstrate that the proposed method can find optimal paths for large networks in very attractive times.     

满足路径约束的最优路算法

满足路径约束的最优路问题已被证明是NP-hard问题。本针对源点到宿点满足两个QoS(服务质量)度量的路由问题，给出一种保证时延的最小费用路由启发式算法。这个算法的优点是计算较简单、占用内存小、时间短。算法的复杂度是多项式的，表明算法是有效的。     

Strategic absentmindedness in finitely repeated games

In this paper we consider finitely repeated games in which players can unilaterally commit to behave in an absentminded way in some stages of the repeated game. We prove that the standard conditions for folk theorems can be substantially relaxed when players are able to make this kind of compromises, both in the Nash and in the subgame perfect case. We also analyze the relation of our model with the repeated games with unilateral commitments studied, for instance, in García-Jurado et al. (Int. Game Theory Rev. 2:129–139, 2000). Authors acknowledge the financial support of Ministerio de Educaci ón y Ciencia, FEDER and Fundación Séneca de la Región de Murcia through projects SEJ2005-07637-C02-02, ECO2008-03484-C02-02, MTM2005-09184-C02-02, MTM2008-06778-C02-01 and 08716/PI/08.     

A New Multiobjective Dynamic Routing Method for Multiservice Networks: Modelling and Performance

There are potential advantages in formulating the routing problems in modern multiservice networks as multiple objective problems. This paper presents a novel hierarchical bi-level multiobjective dynamic routing model for multiservice networks. It is based on a bi-objective shortest path algorithm, with dynamically adapted soft-constraints, to compute alternative paths for each node pair and on a heuristic to synchronously select alternative routing plans for the network in a dynamic alternative routing context. It is a routing method which periodically changes alternative paths as a function of periodic updates of certain QoS related parameters obtained from real-time measurements. The performance of the proposed routing method is compared with two reference dynamic routing methods namely RTNR and DAR by means of a discrete-event simulator.A previous short version of this work was presented at INOC’03 (International Network Optimisation Conference). Work partially supported by programme POSI of the III EC programme cosponsored by FEDER and national funds.     

A model for two coupled turbulent fluids Part III: Numerical approximation by finite elements

Summary. This paper introduces a scheme for the numerical solution of a model for two turbulent flows with coupling at an interface. We consider a variational formulation of the coupled model, where the turbulent kinetic energy equation is formulated by transposition. We prove the convergence of the approximation to this formulation for 2D flows by piecewise affine triangular elements. Our main contribution is to prove that the standard Galerkin - finite element approximation of the Laplace equation approximates in L² norm its solution by transposition, for data with low smoothness. We include some numerical tests for simple geometries that exhibit the behaviour predicted by our analysis.Mathematics Subject Classification (2000): 65 N30, 76M10Revised version received March 24, 2003This research was partially supported by Spanish Government REN2000-1162-C02-01 and REN2000-1168-C02-01 grants     

Waiting time based routing policies to parallel queues with percentiles objectives

We develop a method to obtain near-optimal routing policies to parallel queues with decisions based on customers’ wait and performance objectives which include percentiles of the waiting time. We formulate and explicitly derive a value function where the waiting time is used as a decision variable. This allows us to apply a one-step policy improvement method to obtain an efficient routing solution. Numerical illustrations reveal that classical monotone policies are not always optimal.     

Finite element analysis of pressure formulation of the elastoacoustic problem

In this paper we analyze the non symmetric pressure/displacement formulation of the elastoacoustic vibration problem and show its equivalence with the (symmetric) stiffness coupling formulation. We introduce discretizations for these problems based on Lagrangian finite elements. We show that both formulations are also equivalent at discrete level and prove optimal error estimates for eigenfunctions and eigenvalues. Both formulations are rewritten such as to be solved with a standard Matlab eigensolver. We report numerical results comparing the efficiency of the methods over some test examples. Partially supported by Xunta de Galicia (Spain) through grant No. PGIDT00-PXI20701PR and by MCYT Research Project DPI2001-1613-C02-02Partially supported by Xunta de Galicia (Spain) through grant No. PGIDT00-PXI20701PR and by MCYT Research Project DPI2001-1613-C02-02Partially supported by FONDAP in Applied Mathematics (Chile) and by MCYT Research Projects DPI2001-1613-C02-02 and BFM2001-3261-C02-02Partially supported by FONDECYT (Chile) through grant No. 1.990.346 and FONDAP in Applied Mathematics (Chile)Mathematics Subject Classification (1991):65N30     

A Sharp Form of the Cramér–Wold Theorem

The Cramér–Wold theorem states that a Borel probability measure P on ℝ ^d is uniquely determined by its one-dimensional projections. We prove a sharp form of this result, addressing the problem of how large a subset of these projections is really needed to determine P. We also consider extensions of our results to measures on a separable Hilbert space. First author partially supported by the Spanish Ministerio de Ciencia y Tecnología, grant BFM2002-04430-C02-02. Second author partially supported by Instituto de Cooperación Iberoamericana, Programa de Cooperación Interuniversitaria AL-E 2003. Third author partially supported by grants from NSERC and the Canada research chairs program.     

A stabilized space-time discretization for the primitive equations in oceanography

Summary. In this work we introduce and analyze a space-time discretization for the Primitive Equations of the Ocean. We use a reduced formulation of these equations which only includes the (3D) horizontal velocity and the (2D) surface pressure (cf.[19,20]). We use a semi-implicit Backward Euler scheme for the time discretization. The spatial discretization in each time step is carried out through a Penalty Stabilized Method. This allows to circumvent the use of pairs of spaces satisfying the inf-sup condition, thus attempting a large saving of degrees of freedom. We prove stability estimates, from which we deduce weak convergence in two steps : first in space to a semi-discretisation in time, and then in time to the continuous problem. Finally, we show a numerical test in a real-life application. Specifically, we simulate the wind-driven circulation in the Leman lake.Mathematics Subject Classification (2000): 65N30, 76M10, 86A05Revised version received July 1, 2002Research partially supported by Spanish Government Research Projects: MAR97-1055-C02-02, REN2000-1162-C02-01 MAR and REN2000-1168-C02-01 MAR     

On the Hardness of Equal Shortest Path Routing

In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities.In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. We also prove that despite their weakness, our approximation and exact algorithms are, in a sense, the best possible.     

The Geodesic Problem in Quasimetric Spaces

In this article, we study the geodesic problem in a generalized metric space, in which the distance function satisfies a relaxed triangle inequality d(x,y)≤σ(d(x,z)+d(z,y)) for some constant σ≥1, rather than the usual triangle inequality. Such a space is called a quasimetric space. We show that many well-known results in metric spaces (e.g. Ascoli-Arzelà theorem) still hold in quasimetric spaces. Moreover, we explore conditions under which a quasimetric will induce an intrinsic metric. As an example, we introduce a family of quasimetrics on the space of atomic probability measures. The associated intrinsic metrics induced by these quasimetrics coincide with the d _α metric studied early in the study of branching structures arisen in ramified optimal transportation. An optimal transport path between two atomic probability measures typically has a “tree shaped” branching structure. Here, we show that these optimal transport paths turn out to be geodesics in these intrinsic metric spaces. This work is supported by an NSF grant DMS-0710714.     

Applying reproducing kernels to the evaluation and approximation of the simple and time-dependent imaginary time harmonic oscillator path integrals

Reproduction of kernel Hilbert spaces offers an attractive setting for imaginary time path integrals, since they allow to naturally define a probability on the space of paths, which is equal to the probability associated with the paths in Feynman's path integral formulation. This study shows that if the propagator is Gaussian, its variance equals the squared norm of a linear functional on the space of paths. This can be used to rederive the harmonic oscillator propagator, as well as to offer a finite-dimensional perturbative approximation scheme for the time-dependent oscillator wave function and its ground state energy, and its bound error. The error is related to the rate of decay of the Fourier coefficients of the time-dependent part of the potential. When the rate of decay increases beyond a certain threshold, the error in the approximation over a subspace of dimension n is of order (1/n ³).     

The Median of the Number of Simple Paths on Three Vertices in the Random Graph

We study the asymptotic behavior of the random variable equal to the number of simple paths on three vertices in the binomial random graph in which the edge probability equals the threshold probability of the appearance of such paths. We prove that, for any fixed nonnegative integer b and a sufficiently large number n of vertices of the graph, the probability that the number of simple paths on three vertices in the given random graph is b decreases with n. As a consequence of this result, we obtain the median of the number of simple paths on three vertices for sufficiently large n.

     

Arriving on Time

This research proposes a procedure for identifying dynamic routing policies in stochastic transportation networks. It addresses the problem of maximizing the probability of arriving on time. Given a current location (node), the goal is to identify the next node to visit so that the probability of arriving at the destination by time t or sooner is maximized, given the probability density functions for the link travel times. The Bellman principle of optimality is applied to formulate the mathematical model of this problem. The unknown functions describing the maximum probability of arriving on time are estimated accurately for a few sample networks by using the Picard method of successive approximations. The maximum probabilities can be evaluated without enumerating the network paths. The Laplace transform and its numerical inversion are introduced to reduce the computational cost of evaluating the convolution integrals that result from the successive approximation procedure. We are grateful to the colleagues who responded to this work with questions and comments during the Transportation Science Section session on Urban Transportation Planning Models II at the 2002 Meeting of the Institute for Operations Research and Management Science (INFORMS) in San José, California.