A method to evaluate the routing policy with two minimal paths within time threshold

Two attributes, the capacity and the lead time, are involved in the quickest path problem which finds a path with the minimum transmission time. The capacity of each edge is assumed to be deterministic in this problem. However, in many real-life networks such as computer, telecommunication, logistics networks, etc., each edge should be multistate due to failure, maintenance, etc. Such a network is named a multistate network. Hence, the minimum transmission time through a multistate network is not fixed. We evaluate the system reliability that a specified amount of data can be sent through a pair of minimal paths simultaneously within the time threshold. A solution procedure is first proposed to calculate it. In order to boost the system reliability, the network administrator decides the routing policy in advance to indicate the first and the second priority pairs of minimal paths. The second one will be responsible for the transmission duty if the first one fails. According to the routing policy, the system reliability can be subsequently computed. The case to transmit data through more than two minimal paths can be extended easily.     

Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network

From the point of view of quality management, it is an important issue to reduce the transmission time in the network. The quickest path problem is to find the path in the network to send a given amount of data from the source to the sink such that the transmission time is minimized. Traditionally, this problem assumed that the capacity of each arc in the network is deterministic. However, the capacity of each arc is stochastic due to failure, maintenance, etc. in many real-life networks. This paper proposes a simple algorithm to evaluate the probability that d units of data can be sent from the source to the sink through the stochastic-flow network within T units of time. Such a probability is called the system reliability. The proposed algorithm firstly generates all lower boundary points for (d,T) and the system reliability can then be computed in terms of such points.Scope and purposeThe shortest path problem is a well-known problem in operations research, computer science, etc. Chen and Chin have proposed a variant of the shortest path problem, termed the quickest path problem. It is to find a path in the network to send a given amount of data from the source to the sink with minimum transmission time. More specifically, the capacity of each arc in the network is assumed to be deterministic. However, in many real-life networks such as computer systems, telecommunication systems, etc., the capacity of each arc is 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. This paper proposes a simple algorithm to evaluate the probability that the specified amount of data can be sent from the source to the sink through the network within a given time. Such a probability is called the system reliability.     

Reliability evaluation of a multistate network subject to time constraint under routing policy

A multistate network is a stochastic network composed of multistate arcs in which each arc has several possible capacities and may fail due to failure, maintenance, etc. The quality of a multistate network depends on how to meet the customer's requirements and how to provide the service in time. The system reliability, the probability that a given amount of data can be transmitted through a pair of minimal paths (MPs) simultaneously under the time constraint, is a proper index to evaluate the quality of a multistate network. An efficient solution procedure is first proposed to calculate it. In order to further enhance the system reliability, the network administrator decides the routing policy in advance to indicate the first and the second priority pairs of MPs. The second priority pair of MPs takes charge of the transmission duty if the first fails. The system reliability under the routing policy can be subsequently evaluated.     

Assessment of spare reliability for multi-state computer networks within tolerable packet unreliability

From a quality of service viewpoint, the transmission packet unreliability and transmission time are both critical performance indicators in a computer system when assessing the Internet quality for supervisors and customers. A computer system is usually modelled as a network topology where each branch denotes a transmission medium and each vertex represents a station of servers. Almost every branch has multiple capacities/states due to failure, partial failure, maintenance, etc. This type of network is known as a multi-state computer network (MSCN). This paper proposes an efficient algorithm that computes the system reliability, i.e., the probability that a specified amount of data can be sent through k (k ≥ 2) disjoint minimal paths within both the tolerable packet unreliability and time threshold. Furthermore, two routing schemes are established in advance to indicate the main and spare minimal paths to increase the system reliability (referred to as spare reliability). Thus, the spare reliability can be readily computed according to the routing scheme.     

Computer network reliability optimization under double-resource assignments subject to a transmission budget

This paper discusses a double-resource assignment problem to maximize network reliability for a computer network. The resources are separated into two types: one is transmission line and another is transmission facility. In particular, each resource is multistate due to full failure, partial failure, or maintenance. Such a network assigned with multistate resources is usually modeled as a stochastic-flow network. Furthermore, each resource should have a transmission cost in reality. Hence, the network reliability is the probability that a specified demand is transmitted through the network successfully subject to a transmission budget. This paper devotes to find out the optimal double-resource assignment with maximal network reliability. An optimization algorithm combining the genetic algorithm, the minimal paths, and the Recursive Sum of Disjoint Products is developed to solve the proposed problem. The experimental results show that the proposed algorithm can be executed in a reasonable time.     

A method to evaluate routing policy through p minimal paths for stochastic case

In this paper, a stochastic-flow network is presented to model a computer network in which each arc has various possible capacities and may fail. In order to shorten the transmission time, the transmission protocol allowing the data to be sent through multiple minimal paths simultaneously is utilized for the computer network. However, the minimum transmission time to send a given amount of data is not fixed due to the property of stochastic capacity. Accordingly, the first addressed issue is to evaluate the probability that the network is able to send the data within a time constraint by adopting the transmission protocol. Such a probability is named as transmission reliability that is regarded as a performance indicator to measure the QoS for a computer network. Without knowing all minimal paths in advance, an efficient solution procedure is proposed to calculate transmission reliability. The experimental results of 35 random networks show that the proposed algorithm can be executed efficiently. Moreover, in order to increase transmission reliability, the network administrator decides the routing policy to designate the first and the second priority p minimal paths. The second addressed issue is to evaluate transmission reliability associated with the routing policy. A sort criterion is subsequently presented to find an ideal routing policy.     

Optimal routing policy of a stochastic-flow network

Under the assumption that each arc’s capacity of the network is deterministic, the quickest path problem is to find a path sending a given amount of data from the source to the sink such that the transmission time is minimized. However, in many real-life networks such as computer systems, telecommunication systems, etc., the capacity of each arc is stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not fixed. We try to evaluate the probability that d units of data can be sent through the stochastic-flow network within the time constraint according to a routing policy. Such a probability is named the system reliability, which is a performance index to measure the system quality. This paper mainly finds the optimal routing policy with highest system reliability. The solution procedure is presented to calculate the system reliability with respect to a routing policy. An efficient algorithm is subsequently proposed to derive the optimal routing policy.     

System reliability for a multistate flow network with multiple joint minimal paths under time constraint

The uncertainty of transmission time for a multistate flow network is the main issue when the quickest path problem is applied to such a network. A variant of quickest path problem focusing on the probability of complete transmission instead of finding the quickest path is studied in this paper. In transmission process, a congestion phenomenon may happen when there are joint arcs in minimal paths (MPs). That is, the some arcs are shared by some of MPs. Based on Monte Carlo Simulation, an algorithm is developed to assign the flows through MPs for evaluating the system reliability, the probability that the data can be sent within a time constraint. Experiments are performed to verify the approximate system reliability value obtained from the proposed algorithm is close to the real one. Furthermore, the experiments about CPU time of the algorithm and the characteristics of the variants of quickest path problem are also displayed.     

Optimal Pair of Minimal Paths Under Both Time and Budget Constraints

The quickest path (QP) problem is to find a path which sends a given amount of data from the source to the sink such that the transmission time is minimized. Two attributes are involved, namely, the capacity and the lead time. The capacity of each arc is assumed to be deterministic. However, in many real-life flow 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 modify the QP problem to a stochastic case. The new problem is to evaluate the probability that d units of data can be sent from the source to the sink under both time T and budget B constraints. Such a probability is named the system reliability. In particular, the data can be transmitted through two disjoint minimal paths (MPs) simultaneously. A simple algorithm is proposed to generate all (d, T, B)-QPs, and the system reliability can subsequently be computed. The optimal pair of MPs with highest system reliability could further be obtained.     

Routing policy of stochastic-flow networks under time threshold and budget constraint

The quickest path problem is to find a path which sends a given amount of data from the source to the sink such that the transmission time is minimized. More specifically, the capacity of each arc in the network is assumed to be deterministic. However, in many real-life networks such as computer systems, telecommunication systems, etc., the capacity of each arc is stochastic due to failure, maintenance, etc. Such a network is named as stochastic-flow network. Hence, the minimum transmission time is not a fixed number. The purpose of this paper is to provide a decision procedure for a stochastic-flow network under the time and budget constraints. We try to evaluate the probability that d units of data can be sent through the network under both time threshold and budget according to the routing policy. Such a probability is named the system reliability, which is a performance index to measure the system quality. An efficient algorithm is proposed to derive the optimal routing policy with highest system reliability. The sensitive analysis can be conducted to improve the most important component which increases the system reliability most significantly.     

双源单宿共享链路计算机网络的数据传输可靠性评估

在多态网络中, 数据可以通过不同路径来传输. 之前研究多集中于路径不相交之情形, 较少考虑路径含有共享链路情形. 本文考虑计算机网络两个源点通过各自的最小路集向各自宿点传输数据的情况, 其中, 不同的最小路集含有共享链路. 各源点产生一数据序列, 其产生数据的时间间隔随机分布, 不同时刻产生的数据量也随机分布. 时间间隔和数据量可通过Monte-Carlo模拟方法获得. 由于所有数据都通过共享链路进行传输, 数据需要竞争使用链路的优先权, 而这可能会导致冲突. 本文考虑路径连通情况下, 各数据在传输时间限制下成功传输的可靠度评估问题. 仿真结果显示冲突会延长数据的传输时间并由此影响网络可靠度. 本文研究结果为管理者调整时间间隔和数据量以达到理想的网络可靠度提供了参考.     

Restoration by path concatenation: fast recovery of MPLS paths

A new general theory about restoration of network paths is first introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a shortest path in a network after removing k edges is the concatenation of at most k+1 shortest paths in the original network. The theory is then combined with efficient path concatenation techniques in MPLS (multi-protocol label switching), to achieve powerful schemes for restoration in MPLS based networks. We thus transform MPLS into a flexible and robust method for forwarding packets in a network. Finally, the different schemes suggested are evaluated experimentally on three large networks (a large ISP, the AS graph of the Internet, and the full Internet topology). These experiments demonstrate that the restoration schemes perform well in actual topologies. Received: December 2001 / Accepted: July 2002 RID="*" ID="*" This research was supported by a grant from the Ministry of Science, Israel     

General-demand disjoint path covers in a graph with faulty elements

A k-disjoint path cover of a graph is a set of k internally vertex-disjoint paths which cover the vertex set with k paths and each of which runs between a source and a sink. Given that each source and sink v is associated with an integer-valued demand d(v)≥1, we are concerned with general-demand k-disjoint path cover in which every source and sink v is contained in the d(v) paths. In this paper, we present a reduction of a general-demand disjoint path cover problem to an unpaired many-to-many disjoint path cover problem, and obtain some results on disjoint path covers of restricted HL-graphs and proper interval graphs with faulty vertices and/or edges.     

Least possible time paths in stochastic, time-varying networks

In this paper, two computationally efficient algorithms are presented for determining the least possible time paths for all origins to a single destination in networks where the arc weights are discrete random variables whose probability distribution functions vary with time. The first algorithm determines the least possible time path from each node for each departure time interval, the least possible travel time and a lower bound on the associated probability of the occurrence of this travel time. The second algorithm determines up to k least possible time paths, the associated travel times and the corresponding probabilities of occurrence of the travel times (or a lower bound on this probability). No such efficient algorithms for determining least time paths in stochastic, time-varying networks exist in the literature.     

System reliability maximization for a computer network by finding the optimal two-class allocation subject to budget

In the real world, a computer/communication system is usually modeled as a capacitated-flow network since each transmission line (resp. facility) denoted by an edge (resp. node) has multiple capacities. System reliability is thus defined to be a probability that d units of data are transmitted successfully from a source node to a sink node. From the perspective of quality management, system reliability is a critical performance indicator of the computer network. This paper focuses on maximizing system reliability for the computer network by finding the optimal two-class allocation subject to a budget, in which the two-class allocation is to allocate exactly one transmission line (resp. facility) to each edge (resp. node). In addition, allocating transmission lines and facilities to the computer network involves an allocation cost where the cost for allocating a transmission line depends on its length. For solving the addressed problem, a genetic algorithm based method is proposed, in which system reliability is evaluated in terms of minimal paths and state-space decomposition. Several experimental results demonstrate that the proposed algorithm can be executed in a reasonable time and has better computational efficiency than several popular soft computing algorithms.     

基于无效状态空间的多状态网络可靠性评估

在应用d-最小割(路)集计算多状态网络可靠度精确值算法中,运用容斥原理求解d-最小割(路)集较为复杂。为此,提出一种不需d-最小割(路)集直接计算多状态网络可靠度精确值的算法。该算法按一定规则分割状态空间,在此基础上生成无效状态空间,通过迭代计算直接获得可靠度精确值,同时通过定义边的容量下界及剩余网络。实例分析结果表明,运用该算法可减少计算量,并能精确求解d-最小割(路)集。     

The 1-Fixed-Endpoint Path Cover Problem is Polynomial on Interval Graphs

We consider a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem, or kPC for short, on interval graphs. Given a graph G and a subset T\mathcal{T} of k vertices of V(G), a k-fixed-endpoint path cover of G with respect to T\mathcal{T} is a set of vertex-disjoint paths ℘ that covers the vertices of G such that the k vertices of T\mathcal{T} are all endpoints of the paths in ℘. The kPC problem is to find a k-fixed-endpoint path cover of G of minimum cardinality; note that, if T\mathcal{T} is empty the stated problem coincides with the classical path cover problem. In this paper, we study the 1-fixed-endpoint path cover problem on interval graphs, or 1PC for short, generalizing the 1HP problem which has been proved to be NP-complete even for small classes of graphs. Motivated by a work of Damaschke (Discrete Math. 112:49–64, 1993), where he left both 1HP and 2HP problems open for the class of interval graphs, we show that the 1PC problem can be solved in polynomial time on the class of interval graphs. We propose a polynomial-time algorithm for the problem, which also enables us to solve the 1HP problem on interval graphs within the same time and space complexity.     

Performance evaluation for a transportation system in stochastic case

In a single-commodity multistate flow network, the arc capacity is stochastic and thus the system capacity (i.e. the maximum flow from the source to the sink) is not a fixed number. This paper constructs a multicommodity multistate flow network with weighted capacity allocation to model a transportation system. Each arc with cost attribute has several possible capacities. The capacity weight, the consumed amount of arc capacity by per commodity, varies with the arcs and types of commodity. We define the system capacity as a demand vector d if the system fulfills at most d. The addressed problem in this work is to measure the service quality of a transportation system. We propose a performance index, the probability that the upper bound of the system capacity equals a demand vector d subject to the budget constraint. A simple algorithm based on minimal cuts is presented to generate all (d,B)-MC that are the maximal capacity vectors meeting exactly the demand d under the budget B. The proposed performance index can be subsequently evaluated in terms of such (d,B)-MC.