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.     

A heuristic technique for generating minimal path and cutsets of a general network

Reliability evaluation techniques employ a variety of tools for system modeling and calculation of reliability indices. Amongst the most popular tools are network-based algorithms founded on the concept of minimal paths and minimal cutsets. This paper presents a heuristic programming technique for deducing minimal paths of a network. In this technique, only minimal paths are immediately generated without explicitly determining whether or not a path is minimal. This technique has been implemented on a digital computer to generate a minimal path matrix, which is in turn utilized to generate minimal cutsets of the network. In terms of computational speed, the results obtained compare well with existing algorithms. The technique requires minimum memory storage and minimum user-defined data to represent the topology of a network and follows a modular design strategy. Use of the algorithm is illustrated by examples.     

Calculating reliability of the recursively definable networks

The number of arithmetic operations required to determine the network reliability was estimated. Internet-like networks were considered by way of example. For the networks with edges of low and high reliability, the asymptotic formulas were derived. The calculations were based on approximating reliability by the sum of probabilities of operability of all acyclic paths or the sum of probabilities of failure of all network sections that are minimal in set-theoretical inclusion.     

Applying an evolutionary algorithm to telecommunication networkdesign

This paper deals with the application of evolutionary computation to telecommunication network design. Design of a two-layer network is considered, where the upper-layer (UL) network uses resources of the lower-layer (LL) network. UL links determine demands for the LL and are implemented using LL paths (admissible paths). Within a fixed LL network topology, given the demands and admissible paths, we aim to find the LL link capacities for implementing the UL links, minimizing the cost of the LL. Robust design issues are also taken into consideration, allowing for failure of a certain part of the LL and postulating that, after some re-allocation in the LL, demands are still realized to an assumed extent. An algorithm based on an evolutionary technique is introduced, with problem-specific genetic operators to improve computing efficiency. A theoretical study of properties of the operators is made and several experiments are performed to tune the parameters of the algorithm. Finally, its performance is compared with other design techniques, including integer programming     

Reliability Evaluation for an Information Network With Node Failure Under Cost Constraint

The quality of service is an important index to measure the performance of an information system. This paper constructs a stochastic-flow network to model the information system. In this network, each node and arc having a designated capacity will have different lower levels due to various partial and complete failures. The studied problem is to evaluate the possibility that a given amount of multicommodity can be sent through an information network under the cost constraint. Such a possibility, which is named the mission reliability, is an appropriate performance index to measure the quality level. The terminology "flow" represents the quantity of data transmitted via such a network, and "demand" represents the required data from clients. Based on the properties of minimal paths, a simple algorithm is first proposed to generate all lower boundary points for the demand; then, the mission reliability can be calculated in terms of such points. The lower boundary point for the demand is a minimal vector, which represents the capacity of each component (arc or node), such that the demand can be fulfilled. Extending the stochastic-flow network to the node failure case, another algorithm is proposed to calculate the mission reliability     

饱和非时齐泊松失效过程下网络系统连边交互机理分析

给定由若干连边和节点组成的网络系统,为了有效、经济地提升整个网络的可靠性,一些耦合的2条连边关于整个网络失效的交互机理需要加以分析.首先,采用饱和非时齐泊松过程刻画连边的失效过程,基于组合计数的思想,导出2条连边处于4种不同状态的概率公式,并结合2条连边的联合D-谱,发展联合失效重要度的计算公式,用于分析2条连边关于网络失效的交互机理.理论分析表明,当时间t趋于0或趋于无穷大时,2条连边的交互效果越来越微弱.然后,由于精确的计算联合失效重要度的值是NP-难问题,设计蒙特卡洛近似算法求其值.最后,提供一个路网的算例,其数值结果表明,所提出联合失效重要度计算方法能够有效地阐释2条连边关于网络失效的交互机理.     

A new algorithm to compute vertex cutsets in a graph

A new efficient algorithm has been presented in this paper to compute all the vertex cutsets between two specified vertices in a given symmetric graph. The algorithm has been developed into two distinct phases, i.e. in the first phase all the proper flow paths between the two specified vertices are generated, and in the second phase the vertex cutsets are determined from the information of the proper flow paths. The proposed algorithm seems to be economical in terms of computation time and it offers easy programmability on a digital computer.     

Backup path set selection in ad hoc wireless network using link expiration time

Topological changes in mobile ad hoc networks frequently render routing paths unusable. Such recurrent path failures have detrimental effects on quality of service. A suitable technique for eliminating this problem is to use multiple backup paths between the source and the destination in the network. Most of the proposed on-demand routing protocols however, build and rely on single route for each data session. Whenever there is a link disconnection on the active route, the routing protocol must perform a path recovery process. This paper proposes an effective and efficient protocol for backup and disjoint path set in an ad hoc wireless network. This protocol converges into a highly reliable path set very fast with no message exchange overhead. The paths selection according to this algorithm is beneficial for mobile ad hoc networks, since it produces a set of backup paths with much higher reliability. Simulations are conducted to evaluate the performance of our algorithm in terms of route numbers in the path set and its reliability. In order to acquire link reliability estimates, we use link expiration time (LET) between each two nodes.In another experiment, we save the LET of entire links in the ad hoc network during a specific time period, then use them as a data base for predicting the probability of proper operation of links.Links reliability obtains from LET. Prediction is done by using a multi-layer perceptron (MLP) network which is trained with error back-propagation error algorithm. Experimental results show that the MLP net can be a good choice to predict the reliability of the links between the mobile nodes with more accuracy.     

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

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

无线通讯网络可靠度的计算

文章提出了几个保持可靠度不变的将边可靠、结点不可靠的无向网络化简以及转化成有向网络的原则,并将这些原则与已有的不交和或容斥原理方法相结合给出了一个新的计算无线通讯网络（Radio Communication Network,简称RCN）两终端可靠度的有效算法。由于文章所给的化简与转化使RCN中指定两结点之间的路径数大大减少,因此该文算法使其可靠度的计算得到很大简化。     

大型网络的SKT可靠性的分散计算法

提出了一种基于分解法的计算大型网络从源点到特定节点集K(即SKT)可靠性的算法。按照一定的分解规则将大型网络划分为若干较小规模的子网络，从而最终将枚举原网络的K树这一复杂问题转化为计算这些子网络的最小路。对求得的K树进行不交化运算，最终得到网络的SKT可靠性。     

Shortest distance and reliability of probabilistic networks

When the “length” of a link is not deterministic and is governed by a stochastic process, the “shortest” path between two points in the network is not necessarily always composed of the same links and depends on the state of the network. For example, in communication and transportation networks, the travel time on a link is not deterministic and the fastest path between two points is not fixed. This paper presents an algorithm to compute the expected shortest travel time between two nodes in the network when the travel time on each link has a given independent discrete probability distribution. The algorithm assumes the knowledge of all the paths between two nodes and methods to determine the paths are referenced.In reliability (i.e. the probability that two given points are connected by a path) computations, associated with each link is a probability of “failure” and a probability of “success”. Since “failure” implies infinite travel time, the algorithm simultaneously computes reliability. The paper also discusses the algorithm's capability to simultaneously compute some other performance measures which are useful in the analysis of emergency services operating on a network.     

一种新的自由曲面高斯图分解算法

将高斯图分解成单类型区域是进行自由曲面的形状分析与控制研究中把握自由曲面整体形状的关键算法之一。本文提出了一种新的自由曲面高斯图分解算法，该算法通过引入二阶导数改进了现存高斯图外边界计算算法，实现了对高斯全图的最小闭域分割。理论分析及实验结果均表明，该算法不但可行，而且具有更好的鲁棒性。     

基于改进的不交化最小路集的网络系统可靠性算法

本文根据不交化布尔代数及BDD原理提出了一种简化的求解不交化最小路集的改进算法。对最小路集的路长进行排序,按最小路集的不同路长分两种方法不交化:对于长度为n-1的最小路集,在保持原有弧不变外,将网络图中其余未包含在该条最小路内的弧取逆加入,直接获得不交化运算结果;其余最小路集采用BDD方法进行不交化。最后的实例计算表明,改进的算法有较小的分枝树、较高的计算效率和精度,为大型网络系统的可靠性分析提供了一种新的途径。     

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.     

Two-commodity reliability evaluation of a stochastic-flow network with varying capacity weight in terms of minimal paths

A real-life manufacturing system can be modeled as a stochastic-flow network in which nodes stand for the machine stations, and arcs stand for the shipping media. In terms of minimal paths (MPs), this paper presents a stochastic-flow network model with four characteristics: (1) both nodes and arcs have multiple possible capacities, and may fail; (2) each component (arc/node) has both capacity and cost attributes; (3) two-commodity are proceeded; and (4) the capacity weight varies with arcs, nodes, and types of commodity. We study the possibility of two-commodity to be transmitted through this network simultaneously under the budget constraint. Such a possibility is named as the system reliability. The MPs play the role of media to describe the relationship among flow assignments and capacity vectors. Subsequently, a simple algorithm, in terms of MPs, is proposed to evaluate the system reliability. From the capacity management and decision making viewpoints, managers may adopt the system reliability as a performance index to measure the system capacity and finally to determine if it meets the customers’ orders or not.     

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.     

An exact end-to-end blocking probability algorithm for multicast networks

We consider the calculation of blocking probabilities in multicast trees with dynamic membership. We extend the work by Karvo et al., where an approximate algorithm based on the reduced load approximation (RLA) was given to calculate end-to-end blocking for infinite sized user populations in multicast networks. The new algorithm for calculating end-to-end call blocking exactly for an arbitrary sized user population is based on the known blocking probability algorithm in hierarchical multiservice access networks, where link occupancy distributions are alternately convolved and truncated. We show that the algorithm can be applied to multicast trees embedded in a network with an arbitrary topology carrying also non-multicast traffic. The resource sharing of multicast connections, however, requires the modification of the algorithm by introducing a new type of convolution, the OR-convolution. In addition, we discuss several different user population models for which the algorithm is applicable.     

Two Heuristics for Calculating a Shared Risk Link Group Disjoint Set of Paths of Min-Sum Cost

A shared risk link group (SRLG) is a set of links which share a common risk of failure. Routing protocols in Generalized MultiProtocol Label Switching, using distributed SRLG information, can calculate paths avoiding certain SRLGs. For single SRLG failure an end-to-end SRLG-disjoint path pair can be calculated, but to ensure connection in the event of multiple SRLG failures a set with more than two end-to-end SRLG-disjoint paths should be used. Two heuristic, the Conflicting SRLG-Exclusion Min Sum (CoSE-MS) and the Iterative Modified Suurballes’s Heuristic (IMSH), for calculating node and SRLG-disjoint path pairs, which use the Modified Suurballes’s Heuristic, are reviewed and new versions (CoSE-MScd and IMSHd) are proposed, which may improve the number of obtained optimal solutions. Moreover two new heuristics are proposed: kCoSE-MScd and kIMSHd, to calculate a set of \(k\) node and SRLG-disjoint paths, seeking to minimize its total cost. To the best of our knowledge these heuristics are a first proposal for seeking a set of \(k\, (k>2)\) node and SRLG-disjoint paths of minimal additive cost. The performance of the proposed heuristics is evaluated using a real network structure, where SRLGs were randomly defined. The number of solutions found, the percentage of optimal solutions and the relative error of the sub-optimal solutions are presented. Also the CPU time for solving the problem in a path computation element is reported.     

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.