Calculation of minimal capacity vectors through k minimal paths under budget and time constraints

Reducing the transmission time is an important issue for a flow network to transmit a given amount of data from the source to the sink. The quickest path problem thus arises to find a single path with minimum transmission time. More specifically, the capacity of each arc is assumed to be deterministic. However, in many real-life networks such as computer networks and telecommunication networks, the capacity of each arc is stochastic due to failure, maintenance, etc. Hence, the minimum transmission time is not a fixed number. Such a network is named a stochastic-flow network. In order to reduce the transmission time, the network allows the data to be transmitted through k minimal paths simultaneously. Including the cost attribute, this paper evaluates the probability that d units of data can be transmitted under both time threshold T and budget B. Such a probability is called the system reliability. An efficient algorithm is proposed to generate all of lower boundary points for (d, T, B), the minimal capacity vectors satisfying the demand, time, and budget requirements. The system reliability can then be computed in terms of such points. Moreover, the optimal combination of k minimal paths with highest system reliability can be obtained.     

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.     

Time version of the shortest path problem in a stochastic-flow network

Many studies on hardware framework and routing policy are devoted to reducing the transmission time for a flow network. A time version of the shortest path problem thus arises to find a quickest path, which sends a given amount of data from the unique source to the unique sink with minimum transmission time. More specifically, the capacity of each arc in the flow network is assumed to be deterministic. However, in many real-life networks, such as computer systems, telecommunication systems, etc., the capacity of each arc should be stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not a fixed number. We extend the quickest path problem to evaluating the probability that d$d$ units of data can be sent under the time constraint T$T$. Such a probability is named the system reliability. In particular, the data are transmitted through two minimal paths simultaneously in order to reduce the transmission time. A simple algorithm is proposed to generate all (d,T)$(d,T)$-MPs and the system reliability can then be computed in terms of (d,T)$(d,T)$-MPs. Moreover, the optimal pair of minimal paths with highest system reliability could be obtained.     

Reliability evaluation according to a routing scheme for multi-state computer networks under assured accuracy rate

In many real-time networks such as computer networks, each arc has stochastic capacity, lead time, and accuracy rate. Such a network is named a multi-state computer network (MSCN). Under the strict assumption that the capacity of each arc is deterministic, the quickest path (QP) problem is to find a path that sends a specific amount of data with minimum transmission time. From the viewpoint of internet quality, the transmission accuracy rate is one of critical performance indicators to assess internet network for system administrators and customers. Under both assured accuracy rate and time constraint, this paper extends the QP problem to discuss the flow assignment for a MSCN. An efficient algorithm is proposed to find the minimal capacity vector meeting such requirements. The system reliability, the probability to send \(d\) units of data through multiple minimal paths under both assured accuracy rate and time constraint, can subsequently be computed. Furthermore, two routing schemes with spare minimal paths are adopted to reinforce the system reliability. The enhanced system reliability according to the routing scheme is calculated as well. The computational complexity in both the worst case and average case are analyzed.     

On consecutive-k-out-of-n: F systems

First a brief survey of the consecutive-k-out-of-n: F system is given. Through the use of structure function and using network diagrams to represent the system, system reliability and algorithms for generating all the minimal path and cut sets are obtained. A lower bound and three upper bounds of the systems reliability are given.     

The influence of delivery times on repairable k-out-of-N systems with spares

The k-out-of-N structure is a popular type of redundancy in fault-tolerant systems with wide applications in computer and communication systems, and power transmission and distribution systems, among others, during the past several decades. In this paper, our interest is in such a reliability system with identical, repairable components having exponential life times, in which at least k out of N components are needed for the system to perform its functions. There is a single repairman who attends to failed components on a first-come-first-served basis. The repair times are assumed to be of phase type. The system has K spares which can be tapped to extend the lifetime of the system using a probabilistic rule. We assume that the delivery time of a spare is exponentially distributed and there could be multiple requests for spares at any given time. Our main goal is to study the influence of delivery times on the performance measures of the k-out-of-N reliability system. To that end, the system is analyzed using a finite quasi-birth-and-death process and some interesting results are obtained.     

Reliability and covariance estimation of weighted k-out-of-n multi-state systems

In the literature of reliability engineering, reliability of the weighted k-out-of-n system can be calculated using component reliability based on the structure function. The calculation usually assumes that the true component reliability is completely known. However, this is not the case in practical applications. Instead, component reliability has to be estimated using empirical sample data. Uncertainty arises during this estimation process and propagates to the system level. This paper studies the propagation mechanism of estimation uncertainty through the universal generating function method. Equations of the complete solution including the unbiased system reliability estimator and the corresponding unbiased covariance estimator are derived. This is a unified approach. It can be applied to weighted k-out-of-n systems with multi-state components, to weighted k-out-of-n systems with binary components, and to simple series and parallel systems. It may also serve as building blocks to derive estimators of system reliability and uncertainty measures for more complicated systems.     

Algorithms for the quickest path problem and the reliable quickest path problem

The quickest path problem consists of finding a path in a directed network to transmit a given amount of items from an origin node to a destination node with minimal transmission time, when the transmission time depends on both the traversal times of the arcs, or lead time, and the rates of flow along arcs, or capacity. In telecommunications networks, arcs often also have an associated operational probability of the transmission being fault free. The reliability of a path is defined as the product of the operational probabilities of its arcs. The reliability as well as the transmission time are of interest. In this paper, algorithms are proposed to solve the quickest path problem as well as the problem of identifying the quickest path whose reliability is not lower than a given threshold. The algorithms rely on both the properties of a network which turns the computation of a quickest path into the computation of a shortest path and the fact that the reliability of a path can be evaluated through the reliability of the ordered sequence of its arcs. Other constraints on resources consumed, on the number of arcs of the path, etc. can also be managed with the same algorithms.     

Generate upper boundary vectors meeting the demand and budget for a p-commodity network with unreliable nodes

The system capacity for a single-commodity flow network is the maximum flow from the source to the sink. This paper discusses the system capacity problem for a p-commodity limited-flow network with unreliable nodes. In such a network, arcs and nodes all have several possible capacities and may fail. Different types of commodity, which are transmitted through the same network simultaneously, competes the capacities of arcs and nodes. In particular, the consumed capacity by different types of commodity varies from arcs and nodes. We first define the system capacity as a vector and then a performance index, the probability that the upper bound of the system capacity is a given pattern subject to the budget constraint, is proposed. Such a performance index can be easily computed in terms of upper boundary vectors meeting the demand and budget. A simple algorithm based on minimal cuts is thus presented to generate all upper boundary vectors. The manager can apply this performance index to measure the system capacity level for a supply-demand system.     

Identifying large robust network clusters via new compact formulations of maximum k-club problems

Network robustness issues are crucial in a variety of application areas. In many situations, one of the key robustness requirements is the connectivity between each pair of nodes through a path that is short enough, which makes a network cluster more robust with respect to potential network component disruptions. A k-club, which by definition is a subgraph of a diameter of at most k, is a structure that addresses this requirement (assuming that k is small enough with respect to the size of the original network). We develop a new compact linear 0-1 programming formulation for finding maximum k-clubs that has substantially fewer entities compared to the previously known formulation (O(kn²) instead of O(n^k+1), which is important in the general case of k > 2) and is rather tight despite its compactness. Moreover, we introduce a new related concept referred to as an R-robust k-club (or, (k, R)-club), which naturally arises from the developed k-club formulations and extends the standard definition of a k-club by explicitly requiring that there must be at least R distinct paths of length at most k between all pairs of nodes. A compact formulation for the maximum R-robust k-club problem is also developed, and error and attack tolerance properties of the important special case of R-robust 2-clubs are investigated. Computational results are presented for multiple types of random graph instances.     

Computational experiments with a lazy version of a <Emphasis Type="Italic">K</Emphasis> quickest simple path ranking algorithm

The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission time of a given amount of data throughout a path, which involves both cost and capacity. The K-quickest simple paths problem generalises the latter, by looking for a given number K of simple paths in non-decreasing order of transmission time. Two categories of algorithms are known for ranking simple paths according to the transmission time. One is the adaptation of deviation algorithms for ranking shortest simple paths (Pascoal et al. in Comput. Oper. Res. 32(3):509–520, 2005; Rosen et al. in Comput. Oper. Res. 18(6):571–584, 1991), and another is based on ranking shortest simple paths in a sequence of networks with fixed capacity lower bounds (Chen in Inf. Process. Lett. 50:89–92, 1994), and afterwards selecting the K quickest ones. After reviewing the quickest path and the K-quickest simple paths problems we describe a recent algorithm for ranking quickest simple paths (Pascoal et al. in Ann. Oper. Res. 147(1):5–21, 2006). This is a lazy version of Chen’s algorithm, able to interchange the calculation of new simple paths and the output of each k-quickest simple path. Finally, the described algorithm is computationally compared to its former version, as well as to deviation algorithms.      

Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set P of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of P. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that P consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s₁ and s₂ to, respectively, a given vertex t₁, and each vertex of a given subset of vertices T₂.     

Multistate components assignment problem with optimal network reliability subject to assignment budget

The typical assignment problem for finding the optimal assignment of a set of components to a set of locations in a system has been widely studied in practical applications. However, this problem mainly focuses on maximizing the total profit or minimizing the total cost without considering component’s failure. In practice, each component should be multistate due to failure, partially failure, or maintenance. That is, each component has several capacities with a probability distribution and may fail. When a set of multistate components is assigned to a system, the system can be treated as a stochastic-flow network. The network reliability is the probability that d units of homogenous commodity can be transmitted through the network successfully. The multistate components assignment problem to maximize the network reliability is never discussed. Therefore, this paper focuses on solving this problem under an assignment budget constraint, in which each component has an assignment cost. The network reliability under a components assignment can be evaluated in terms of minimal paths and state-space decomposition. Subsequently an optimization method based on genetic algorithm is proposed. The experimental results show that the proposed algorithm can be executed in a reasonable time.     

Enumerating K best paths in length order in DAGs

We address the problem of finding the K best paths connecting a given pair of nodes in a directed acyclic graph (DAG) with arbitrary lengths. One of the main results in this paper is the proof that a tree representing the kth shortest path is obtained by an arc exchange in one of the previous (k − 1) trees (each of which contains a previous best path). An O(m + K(n + log K)) time and O(K + m) space algorithm is designed to explicitly determine the K shortest paths in a DAG with n nodes and m arcs. The algorithm runs in O(m + Kn) time using O(K + m) space in DAGs with integer length arcs. Empirical results confirming the superior performance of the algorithm to others found in the literature for randomly generated graphs are reported.     

New reliability bounds for coherent systems

In 1970, Esary and Proschan proposed simple formulae for the system reliability lower bound and system reliability upper bound. Their formulae of reliability bounds have been classic and have been incorporated into almost all recent textbooks on reliability. In this paper, we decompose a coherent system into several consecutive-k-out-of-n : F(G) systems, and then based upon their exact formulae for system reliabilities, we develop new formulae for both reliability lower bound and reliability upper bound for the coherent system. In addition, we show that the new proposed reliability bounds are superior to those of Esary and Proschan for all coherent systems when the minimal cut/path sets have elements in common. Numerical results are reported, compared and discussed for various systems.     

Reliability of a consecutive (r, s)-out-of-(m, n):F lattice system with conditions on the number of failed components in the system

A consecutive(r, s)-out-of-(m, n):F lattice system which is defined as a two-dimensional version of a consecutive k-out-of-n:F system is used as a reliability evaluation model for a sensor system, an X-ray diagnostic system, a pattern search system, etc. This system consists of m × n components arranged like an (m, n) matrix and fails iff the system has an (r, s) submatrix that contains all failed components. In this paper we deal a combined model of a k-out-of-mn:F and a consecutive (r, s)-out-of-(m, n):F lattice system. Namely, the system has one more condition of system down, that is the total number of failed components, in addition to that of a consecutive (r, s)-out-of-(m, n):F lattice system. We present a method to obtain reliability of the system. The proposed method obtains the reliability by using a combinatorial equation that does not depend on the system size. Some numerical examples are presented to show the relationship between component reliability and system reliability.     

The shortest path problem with forbidden paths

We consider a variant of the constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part of any feasible solution. Two solution approaches are proposed for this variant. The first uses Aho and Corasick's keyword matching algorithm to filter paths produced by a k-shortest paths algorithm. The second generalizes Martins' deviation path approach for the k-shortest paths problem by merging the original graph with a state graph derived from Aho and Corasick's algorithm. Like Martins' approach, the second method amounts to a polynomial reduction of the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows considering forbidden paths in more general shortest path problems such as the shortest path problem with resource constraints.     

Reliability Bounds for Multicriteria Systems

This paper deals with general structure functions, where arbitrary degrees of performance between perfect functioning and complete failure are allowed for each component and the n-component system itself. We make the assumption that the n-component system can be modelled as a structure function given by a mapping φ:L ⁿ →L ^k ₀, L and L₀ being two linearly ordered sets, so that the performance of the system is evaluated according to k single criteria. Global concepts of minimal path and minimal cut are discussed for these multicriteria systems; general reliability bounds based on them are deduced and compared with those given in previous papers.     

The shortest path problem with two objective functions

We present methods to find the shortest path in a network where each path is associated with two objectives. We describe how to obtain the nondominated paths and the extreme nondominated paths, and compare the expected complexity of the methods. An improvement in efficiency can be obtained when quasiconcave or quasiconvex utility functions are assumed. In the first case, we describe how to find the optimal extreme nondominated path and bounds for the optimal path value. Then the optimal path can be located by calculating the k-th shortest path. In the second case we suggest a branch and bound method to solve the problem.     

Semirings and path spaces

This paper develops a unified algebraic theory for a class of path problems such as that of finding the shortest or, more generally, the k shortest paths in a network; the enumeration of elemementary or simple paths in a graph. It differs from most earlier work in that the algebraic structure appended to a graph or a network of a path problem is not axiomatically given as a starting point of the theory, but is derived from a novel concept called a “path space”. This concept is shown to provide a coherent framework for the analysis of path problems, and hence the development of algebraic methods for solving them.