Topological layout of links for optimizing the s-t reliability in a computer communication system

Large-scale Computer Communication Networks (CCN) are coming into use primarily because of the economy achieved through resource sharing. A fundamental consideration in the design of a CCN is the reliability between any pair of nodes and the maximum permissible cost, these characteristics being largely dependent upon the topological layout of the links, their costs and reliabilities. In this paper, having the knowledge of the locations of the various computer centres (nodes), maximum permissible cost of installing the links and the possible position of links, an heuristic algorithm for obtaining an optimal network topology which gives the maximum s-t reliability is presented. The method is general and is easily computerizable.     

Nework topology for maximizing the terminal reliability in a Computer Communication Network

In the design of a Computer Communication Network (CCN), the reliability between any pair of nodes and the maximum permissible installation cost are of great importance. These characteristics are largely dependant upon the topological layout of the links, their costs and reliabilities. Having the knowledge of the topological layout of the various computer centres (nodes) and maximum permissible cost of installing the various links at their pre-assigned positions; in this paper an algorithm for obtaining an optimal network topology which gives the maximum s?t reliability is presented. The developed method is general and is computerized. The proposed method has an additional advantage that the system is not to be redesigned, if at a later stage the permissible cost is enhanced by budgetary provisions. An example illustrates the algorithm.     

Reliability optimization of computer-communication networks

The evaluation of the reliability of a given computer communication network is a NP-hard problem. Hence, the problem of assigning reliabilities to links of a fixed computer communication network topology to optimize the system reliability is also NP-hard. A heuristic method is developed to assign links to a given topology so that the system reliability of the network is near optimal. The method provides a way to assign reliability measures to the links of a network to increase overall reliability. It is based on the principle that the most reliable link should be assigned to the most vulnerable edge. The method computes an importance order for the edges of the network and uses the order to assign link reliabilities. If there are fewer than six links in a network, it can be shown that the method gives optimal assignment     

Optimal design improving a communication network reliability

Improvement of the reliability of a communication network is an optimal problem that finds some links to add to the network such that the reliability of the network reaches a given level and the total cost of these links is minimized. A decomposition method based on branch and bound is used for solving the problem. In order to speed up the solution procedure, an upper bound on system reliability in terms of node degrees is applied. Specially, when the threshold P_o is large enough, a new algorithm, the cut tree algorithm, can more effectively give the optimal solution.     

A novel steady‐state genetic algorithm approach to the reliability optimization design problem of computer networks

This paper introduces the development and implementation of a new methodology for optimizing reliability measures of a computer communication network within specified constraints. A genetic algorithm approach with specialized encoding, crossover, and mutation operators to design a layout topology optimizing source‐terminal computer communication network reliability is presented. In this work, we apply crossover at the gene level in conjunction with the regular chromosome‐level crossover operators that are usually applied on chromosomes or at boundaries of nodes. This approach provides us with a much better population mixture, and hence faster convergence and better reliability. Applying regular crossover and mutation operators on the population may generate infeasible chromosomes representing a network connection. This complicates fitness and cost calculations, since reliability and cost can only be calculated on links that actually exist. In this paper, a special crossover and mutation operator is applied in a way that will always ensure production of a feasible connected network topology. This results in a simplification of fitness calculations and produces a better population mixture that gives higher reliability rates at shorter convergence times. Copyright © 2008 John Wiley & Sons, Ltd.     

Genetic-algorithm-based reliability optimization for computernetwork expansion

This paper explains the development and implementation of a new methodology for expanding existing computer networks. Expansion is achieved by adding new communication links and computer nodes such that reliability measures of the network are optimized within specified constraints. A genetic algorithm-based computer network expansion methodology (GANE) is developed to optimize a specified objective function (reliability measure) under a given set of network constraints. This technique is very powerful because the same approach can be extended to solve different types of problems; the only modification required is the objective function evaluation module. The versatility of the genetic algorithm is illustrated by applying it to solve various network expansion problems (optimize diameter, average distance and computer network reliability for network expansion). The results are compared with the optimal solutions computed using an exhaustive search of complete solution space. The results demonstrate that GANE is very effective (in both accuracy and computation time) and applies to a wide range of problems, but it does not guarantee the optimal results for every problem     

A design technique for reliable networks under a nonuniform trafficdistribution

Many network-reliability analysis techniques define and compute a variety of reliability measures. Most techniques assume that network connectivity is the only determining factor in network reliability; and merely analyze an existing network structure but do not provide any methodology for reliable design. This paper presents a heuristic design algorithm to enhance the reliability of existing communication networks by modifying their topology. This algorithm improves the reliability of the least reliable node (reliability is the probability that messages transmitted from a given node reach their destination). To use this algorithm on large networks, a reliability analysis method is developed which determines approximate network reliability values in linear-time when an upper bound is placed upon the in-degree of all network nodes. The heuristic network design algorithm uses this approximate reliability analysis technique to place additional links. The goal of this link placement is to improve the reliability of the least-reliable node. The placement of additional links is a function of both the traffic distribution and the connectivity of the network. This process continues until either a desired level of network reliability is achieved or a maximum number of additional links has been added. A unique feature of this design strategy is that it has quadratic time-complexity when the maximum in-degree of all network nodes is limited     

On the reliability of links in a ring network

This paper analyzes the reliability of links in a computer network which is configured in a ring topology. It will be shown that the expression for reliability of elements connected in series is not adequate for computing the reliability of links in a ring network. Consequently, new expressions for computing such reliability for rings with and without back-up links are proposed. Furthermore, an optimal back-up links assignment which guarantees optimal links reliability is formulated.     

Reliability Indices for Topological Design of Computer Communication Networks

Incorporating network reliability parameter in the design of reliable computer communication networks makes the computations prohibitive. Interdependence among network topological parameters does not permit the design of a maximally reliable network using any one of the parameters and thus, there arises a real need for a composite reliability index which gives a more realistic assessment of network reliability. After discussing experimental results regarding the effects of various topological parameters on network reliability, we present two heuristic reliability indices which give a fair indication of overall reliability. A design procedure for reliable computer communication network based on local search technique incorporating these reliability indices is suggested. Having only one composite reliability index which is very simple to evaluate saves computation while designing maximally reliable computer networks as compared to the existing techniques based on several reliability measures.     

Optimal Design of Mixed-Media Packet-Switching Networks: Routing and Capacity Assignment

This paper considers a mixed-media packet-switched computer communication network which consists of a low-delay terrestrial store-and-forward subnet combined with a low-cost high-bandwidth satellite subnet. We show how to route traffic via ground and/or satellite links by means of static, deterministic procedures and assign capacities to channels subject to a given linear cost such that the network average delay is minimized. Two operational schemes for this network model are investigated: one is a scheme in which the satellite channel is used as a slotted ALOHA channel; the other is a new multiaccess scheme we propose in which whenever a channel collision occurs, retransmission of the involved packets will route through ground links to their destinations. The performance of both schemes is evaluated and compared in terms of cost and average packet delay tradeoffs for some examples. The results offer guidelines for the design and optimal utilization of mixed-media networks.     

A tutorial on using genetic algorithms for the design of network topology

The design of network topology is an important part of network design, since network topology is directly associated with network operational behavior, capacity, reliability, and cost. This paper is a tutorial paper concerned with illustrating how the optimization capabilities of genetic algorithms can be used to design suitable network topologies considering basic topology problems. Simple genetic algorithms have been developed for the topology problem of mesh networks, considering single node and single link failure tolerance. The algorithms are based on criteria of two important measures: minimizing the length of communication links; and minimizing traffic flow through these links for given traffic loads. The first measure contributes to minimizing the cost of cabling, while the second measure contributes to minimizing the cost of link capacity. The work provides a useful approach and tools to network students and professionals concerned with the topology design of backbone networks. The developed software is made available on the Internet. Copyright © 2006 John Wiley & Sons, Ltd.     

K-Terminal Network Reliability Measures With Binary Decision Diagrams

We present a network decomposition method using binary decision diagrams (BDD), a state-of-the-art data structure to encode, and manipulate Boolean functions, for computing the reliability of networks such as computer, communication, or power networks. We consider the K-terminal reliability measure R_K, which is defined as the probability that a subset K of nodes can communicate with each other, taking into account the possible failures of the network links. We present an exact algorithm for computing the if-terminal reliability of a network with perfect vertices in O(m^.F_max ^.2^Fmax.B_Fmax), where B_Fmax is the Bell number of the maximum boundary set of vertices F_max, and m is the number of network links. Several examples, and experiments show the effectiveness of this approach.     

军事通信网抗毁性能的神经网络方法研究

可靠性和时延性能是衡量军事通信网抗毁性能的两个重要指标。在研究通信网节点间的链路的可靠性和时延性能后 ,提出综合考虑可靠性和时延性能的代价函数 ,借助自组织竞争人工神经网络对其进行分析和仿真     

基于全终端可靠度的网络扩充问题的研究

分析了计算机通信主干网络的扩充设计问题,建立了一个在网络全终端可靠度约束下,使扩充网络所投入成本极小化的优化模型,利用混合遗传算法对其进行了优化求解。通过实例分析,能够得到较为满意的结果,表明文中的研究方法可以应用在实际网络中。     

Modification of cutsets for reliability evaluation of communication systems

A general and simple technique for the evaluation of symbolic reliability expression in the case of practical systems such as a communication system having fixed channel capacities of its various communicating links, a computer communication network allowing a fixed amount of data exchange amongst different terminals of various computer centres and a power distribution system having limited power ratings of its various power lines, is presented. A system is considered reliable only if it successfully transmits at least the required system capacity from the transmitter to the receiver station. In this method, the various branch sets are obtained which completely disrupt the communication path, i.e. ensure system failure. It is observed that these branch sets are not necessarily the cutsets in the usual graph theoretic sense. The unreliability expression is then determined by adopting an existing method for making various terms disjoint. Two typical examples are solved by this method. It is observed that the method is computationally fast and efficient.     

Power Allocation and Transmission Period Selection for Device-to-Device Communication as an Underlay to Cellular Networks

Efficient design of device-to-device (D2D) communication calls for D2D users to propose adaptive power allocation strategy and to establish reliable communication links while protecting the QoS of cellular communications. In this paper, we consider the D2D communication as an underlay to relay-assisted cellular networks. To maximize the ergodic capacity, we derive an optimal transmission power under an average power constraint. With the derived optimal transmission power, a transmission period selection strategy for D2D communication is firstly introduced to improve reliability. We derive the outage probability in closed forms and evaluate the ergodic capacity to show performances of the proposed system. Numerical results show that the D2D system can achieve high capacity gains by flexibly allocating transmission power based on channel state information and significantly enhance reliability by selecting a transmission period, while satisfying various QoS conditions for cellular communication.     

Reliability optimization of communication networks using simulated annealing

Two concepts of communication network reliability are considered. The first one, the ‘s-t’ reliability, is relevant for communication between a source station and a terminal station as in the case of a two way telephone communication. The second one, the overall reliability, is a measure of simultaneous connectedness among all stations in the network. An algorthm is presented which selects the optimal set of links that maximizes the overall reliability of the network subject to a cost restriction, given the allowable node-link incidences, the link costs and the link reliabilities. The algorithm employs a variaton of the simulated annealing approach coupled with a hierarchical strategy to achieve the gobal optimum. For complex networks, the present algorithm is advantageous over the traditional heuristic procedures. The solutions of two representative example network optimization problems are presented to illustrate the present algorithm. The potential utilization of parallel computing strategies in the present algorithm is also identified.     

MDP based link scheduling in wireless networks to maximize the reliability

This paper considers wireless networks where communication links are unstable and link interference is a challenge to design high performance scheduling algorithms. Wireless links are time varying and are modeled by Markov stochastic processes. The problem of designing an optimal link scheduling algorithm to maximize the expected reliability of the network is formulated into a Markov Decision Process first. The optimal solution can be obtained by the finite backward induction algorithm. However, the time complexity is very high. Thus, we develop an approximate link scheduling algorithm with an approximate ratio of \(2(N - 1)(r_{M}\Delta - r_{m} \delta ),\) where N is the number of decision epochs, r _M is the maximum link reliability, r _m is the minimum link reliability, Δ is the number of links in the largest maximal independent set and δ is the number of links in the smallest maximal independent set. Simulations are conducted in different scenarios under different network topologies.     

分布式环境中基于协商的虚拟网映射算法

网络虚拟化技术可以在共享的底层物理网络上为用户同时提供多种可定制的服务网络。目前的虚拟网映射算法比较依赖于集中式的管理节点,使其在可靠性和适用范围等方面存在诸多问题。为此,提出了一种分布式环境下的虚拟网映射算法,该算法通过多个节点之间的相互协商来完成虚拟网的映射,并且在降低通信开销和缩短虚拟链路的路径长度方面进行了相应改进。实验结果表明,该算法与同类型算法相比,在资源利用率和通信开销方面具有一定的优越性。     

Reliability-constrained dimensioning of transmission resources inpacket-switched networks

The author investigates the problem of dimensioning the transmission resources of a packet-switched communication network satisfying suitable reliability targets. The goal is a communication network providing a minimal transport capability in the presence of failures in network components. This goal is expressed in terms of availability functions to be satisfied by the reliability of communication links. The design procedure is based on the routing of each communication link on more than one transmission path, so that the availability of small shares of the communication link capacity can be increased. An analytic evaluation of the availability figures considered during the design phase is provided and the tools developed are used to compute an end-to-end reliability figure, which also takes into account the amount of user traffic