148,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Serie: Performability Engineering Series
- Sprache: Englisch
This book presents novel and efficient tools, techniques and approaches for reliability evaluation, reliability analysis, and design of reliable communication networks using graph theoretic concepts. In recent years, human beings have become largely dependent on communication networks, such as computer communication networks, telecommunication networks, mobile switching networks etc., for their day-to-day activities. In today's world, humans and critical machines depend on these communication networks to work properly. Failure of these communication networks can result in situations where people may find themselves isolated, helpless and exposed to hazards. It is a fact that every component or system can fail and its failure probability increases with size and complexity. The main objective of this book is to devize approaches for reliability modeling and evaluation of such complex networks. Such evaluation helps to understand which network can give us better reliability by their design. New designs of fault-tolerant interconnection network layouts are proposed, which are capable of providing high reliability through path redundancy and fault tolerance through reduction of common elements in paths. This book covers the reliability evaluation of various network topologies considering multiple reliability performance parameters (two terminal reliability, broadcast reliability, all terminal reliability, and multiple sources to multiple destinations reliability).
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 271
Veröffentlichungsjahr: 2020
Ähnliche
Scrivener Publishing100 Cummings Center, Suite 541JBeverly, MA 01915-6106
Performability Engineering SeriesSeries Editors: Krishna B. Misra ([email protected])
Scope: A true performance of a product, or system, or service must be judged over the entire life cycle activities connected with design, manufacture, use and disposal in relation to the economics of maximization of dependability, and minimizing its impact on the environment. The concept of performability allows us to take a holistic assessment of performance and provides an aggregate attribute that reflects an entire engineering effort of a product, system, or service designer in achieving dependability and sustainability. Performance should not just be indicative of achieving quality, reliability, maintainability and safety for a product, system, or service, but achieving sustainability as well. The conventional perspective of dependability ignores the environmental impact considerations that accompany the development of products, systems, and services.
However, any industrial activity in creating a product, system, or service is always associated with certain environmental impacts that follow at each phase of development. These considerations have become all the more necessary in the 21st century as the world resources continue to become scarce and the cost of materials and energy keep rising. It is not difficult to visualize that by employing the strategy of dematerialization, minimum energy and minimum waste, while maximizing the yield and developing economically viable and safe processes (clean production and disposal at the end of the life. This is basically the goal of performability effect on the environment during production and disposal at the end of the life. This is basically the goal of performability engineering.
It may be observed that the above-mentioned performance attributes are interrelated and should not be considered in isolation for optimization of performance. Each book in the series should endeavor to include most, if not all, of the attributes of this web of interrelationship and have the objective to help create optimal and sustainable products, systems, and services.
Publishers at ScrivenerMartin Scrivener ([email protected])Phillip Carmical ([email protected])
Interconnection Network Reliability Evaluation
Multistage Layouts
Neeraj Kumar Goyal
Indian Institute of Technology Kharagpur, India
and
S. Rajkumar
Adama Science and Technology University, Ethiopia
This edition first published 2020 by John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA and Scrivener Publishing LLC, 100 Cummings Center, Suite 541J, Beverly, MA 01915, USA© 2020 Scrivener Publishing LLCFor more information about Scrivener publications please visit www.scrivenerpublishing.com.
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.
Wiley Global Headquarters111 River Street, Hoboken, NJ 07030, USA
For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.
Limit of Liability/Disclaimer of WarrantyWhile the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials, or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read.
Library of Congress Cataloging-in-Publication Data
ISBN 978-1-119-62058-7
Cover image: Pixabay.ComCover design by Russell Richardson
Series Editor Preface
The Figure given below represents the concept of performability as introduced by the editor in 2005 and reflects a holistic view of designing, producing, using, and disposing products, systems or services, which will satisfy not only the basic operational requirements to the best possible extent with minimum cost, but are also sustainable. Sustainability aspect of products, systems and services includes that they consume minimum material and energy in their production, use and disposal and produce minimum waste in order to create minimum environmental impact which is of prime importance and requirement in the 21st Century. In other words, it should represent the holistic performance.
In fact, the concept of performability and sustainable development are closely interlinked. To promote the concept to wider section of engineering community, consisting of planners, designers, manufacturers, researchers, technologists and users, the Editor published the first book on performability engineering in 2008 [1]. The book consisted of 76 chapters with 100 contributors and touching on all aspects of performability with the Editor himself contributing 15 chapters. The response to this book has been overwhelming with more than 495,445 chapter downloads to the end of 2019. A German company, ResearchGate, which keeps track of chapters, books etc., read by people the world over, reports that the main chapters authored by the Editor himself had the following statistics as of June 04, 2020:
Title of the Chapter
Chapter #
Total Reads
Quality Engineering and Management, pp. 157-170.
Chapter 12
18813
Reliability Engineering: A Perspective, pp. 253-288.
Chapter 19
8324
Risk Analysis and Management: An Introduction, pp. 661-674. (Safety)
Chapter 41
1602
Maintenance Engineering and Maintainability: An Introduction, pp. 747-764.
Chapter 46
7477
Sustainability: Motivation and Pathways for Implementation, pp. 835-848.
Chapter 51
377
This indicates the interest evinced by readers the world over in the subject of performability engineering. Encouraged by this interest, Scrivener Publishing LLC undertook the publication of a series of books in the area of performability engineering with Prof. Krishna B. Misra and Prof. John Andrews of Nottingham University, UK as Series Editors in 2014, and it is matter of satisfaction that as many as 10 books have been published under this series so far. The books published under this series have solicited good number of citations in spite of the fact that much time has not elapsed after their publication.
As an Editor of this series, I solicit manuscript of books from academicians, engineers and researchers in any area of Performability Engineering. For details, please contact the Series Editor.
[1] Misra, Krishna B. (Editor), Handbook of Performability Engineering, Springer, London, 2008.
Preface
Network reliability evaluation for complex communication networks is a time-consuming task. Complex networks such as computer communication networks, telecommunication networks, transport networks, etc. are an integral part of our daily life. Complex networks interconnect multiple processing units in distributed systems. Performance of such networks can be measured by evaluating the reliability index, which represents the probability that the network operates satisfactorily for a given period of time when used under stated operating conditions. A network designer has to choose suitable fault-tolerant and highly reliable network architecture to avoid performance degradation and carry out multiple communication tasks concurrently.
Parallel computers with multiple processors have emerged to meet energy-efficient performance demands of current and future challenging computing applications. These multiprocessor systems need interconnection networks for connecting processors and memory modules. Advances in parallel and distributed computing have made interconnection networks a potential networking alternative to meet the growing demands of high-performance computing applications. These networks need to perform continuously without repair for long periods of time. Therefore, these need to be reliable and fault-tolerant as these networks are quite complex and big in size. Failure of its components should not lead to complete network failure as it may be catastrophic.
The main objective of this book is to device approaches for reliability modeling and evaluation of such complex networks. Such evaluation helps to understand which network can give us better reliability by their design. New designs of fault-tolerant interconnection network layouts are proposed, which are capable of providing high reliability through path redundancy and fault tolerance through reduction of common elements in paths. This book covers the reliability evaluation of various network topologies considering multiple reliability performance parameters (two terminal reliability, broadcast reliability, all terminal reliability, and multiple sources to multiple destinations reliability).
For decades, work on network reliability evaluation has been going on. Our S.C. School of Quality and Reliability, earlier known as Reliability Engineering Centre, has significantly contributed to this area of research during the 1980s and onwards. The school has been involved in developing models for reliability evaluation of complex networks but static and ad hoc. The authors of this paper have significant contributions in this area.
Interconnection networks pose another challenge to reliability evaluation due to their complex and large architectures. There are very few in this area. This subject matter has not been much addressed in easy-to-follow book materials. This book tries to bring the aspects of latest research conducted at S.C. School of Quality and Reliability to have better reach to audiences. This is the first edition of the book, so there are many improvements possible. The authors can be provided with feedback to improve the contents of the book in the possible next edition.
This book first introduces the basic concepts of network reliability and the popular interconnection network architectures in the first two chapters. Then it discusses approaches used for reliability evaluation of such a network in Chapters 3, 4, and 5. Some new novel architectures providing better reliability and fault tolerance while being cost effective are presented in Chapter 6.
The authors would like to thank everyone (faculty, students, and staff) from S.C. School of Quality and Reliability, IIT Kharagpur, India, for their encouragement, suggestions, and support while carrying this analysis. We would also like to thank Prof. K.B. Mishra and Martin Scrivener for their guidance and support in writing this book.
Dr. Neeraj Kumar Goyal and Dr. S. Rajkumar
August 2020
1Introduction
1.1 Introduction
In recent years’ human beings have become largely dependent on communication networks, such as computer communication networks, telecommunication networks, mobile switching networks etc., for their day-to-day activities [1]. In today’s world, humans and critical machines depend on these communication networks to work properly. Failure of these communication networks can result in situations where people may find themselves isolated, helpless and exposed to hazards. It is fact that every component or system can fail and its failure probability increases with size and complexity.
Therefore, it is essential to compute and assure the reliability of these networks, which are growing and becoming complex. Reliability modeling and computation is necessary for reliability and safety assurance of these networks [2]. It also helps to identify weak links. These weak links can be improved cost effectively using reliability design techniques. Recent developments in communication hardware industry has resulted in increasingly reliable and non-repairable (need to be replaced when got bad 1) network components. However new designs involve new components, which tend to be less reliable. A good network design [3] involving fault tolerance and redundancies can deliver better system reliability at lesser cost. This allows new designs to be released faster and works reliably even when components are not mature enough from reliability point of view.
The computation of reliability measures [4] for a large and complex communication network, up to the desired level of accuracy, is time consuming, complex and costly. It has not been realistic to model and compute the reliability of real-life communication networks, which are quite large, using desktop computer due to large execution time and high memory requirements. Such computations are usually performed on high-end processors for critical systems only. Reliability professionals and researchers have carried out a lot of research and developed techniques to minimize these efforts and develop a practical tool for all the communication network designers [4–6].
This book presents novel and efficient tools, techniques and approaches for reliability evaluation, reliability analysis, and design of reliable communication networks using graph theoretic concepts.
1.2 Network Reliability Measures
Earlier attempts to measure network reliability belong to two distinct classes: deterministic and probabilistic [1, 2]. The deterministic measures assumed that the network is subjected to a destructive force with complete knowledge of the network topology. The reliability is measured in terms of the least amount of damage required to make the network inoperative.
Deterministic measures thus provide simple bounds on the reliability of the network, since they are often measured for the network’s worst-case environment. For example, in the terminal pair reliability problem, two deterministic measures of reliability are:
The minimum number of edges that must be destroyed or removed to disrupt the communication between the specified nodes (s and t), which is simply the number of edges in a minimum cardinality cutset, and
The minimum number of nodes that must be destroyed or removed to disrupt the communication between the specified nodes (s and t).
Both of these measures are computable in polynomial time. However, one of the main problems with deterministic measures is these give rise to some counter intuitive notions of network reliability. For example, consider the networks shown in Figure 1.1. According to second deterministic measure of the graph’s reliability, the graphs of Figure 1.1 (a) and Figure 1.1 (b) are equally reliable since both of these require minimum three nodes to be destroyed for breaking the s-f node connectivity.
Figure 1.1 Example networks for deterministic reliability measurement.
However intuitively one can easily find out that graph (a) is the more reliable among the two. The same problem arises when the cardinality of a minimum (s, t)-cut set is used as a measure of unreliability. Consider the graphs shown in Figure 1.2. Both graphs (a) and (b) have a minimum cardinality for (s, t) cut of size one, which implies both networks are equally reliable.
This clearly shows that deterministic measures of reliability are insufficient to correctly relate network components used in network layout with network reliability. Moreover, failure of network components is probabilistic in nature therefore only probabilistic measures can define system reliability appropriately.
Figure 1.2 Another set of example networks for deterministic reliability measurement.
Therefore, for evaluating reliability of a network using probabilistic measures, one can associate a statistical probability of failure/ success with each component of the network in order to obtain a statistical measure of overall unreliability/reliability of the network. This notion supports an accepted definition of reliability as the probability that a system or device is operational under stated environment for a given mission time. To avoid conflicts that arise with various levels of operation within a network’s hierarchy, only the topology of the network is considered. This allows a network to be modeled by a graph where the nodes of the graph represent the communication centers and communication links are represented by its edges.
1.3 The Probabilistic Graph Model
Communication networks are generally modeled using network graph [3]. The network graph G (V,E) consists of a set V of n number of nodes (or vertices) and a set E of l number of edges (or links). For reliability evaluation, probabilistic graph is used which takes these sets V and E of nodes and links as random variables. In probabilistic graph of communication networks, nodes represent the computers/ switches/transceivers/routers and edges represent various types of communication links connecting these nodes. For reliability analysis, graphical models of networks are considered to be simple, efficient and effective.
Probabilistic graph models are developed and presented in this book. Depending on the state (working or failed) of nodes (or vertices) and/or links (or edges), the network can be considered either working or failed. A general assumption of statistical independence among nodes and links failures is followed throughout. It implies that the probability of a link or node being operational is not dependent of the states of the other links or nodes in the network. The inherent assumption here is that the link failures are caused by random events which affect all network components individually.
However, this assumption may not be completely correct while modeling a real communication network as more than one component in a particular area may fail due to natural causes such as a major storm or an earthquake. In such cases, dependency analysis and common cause failure modelling can be used over the analysis performed with assumption of statistical independence. This assumption is often made because of difficulties in obtaining information about the dependencies of link failures and increased modeling and computational rigor. In fact, such dependencies may not be known. Thus, without the assumption of statistical independence the problem becomes much more difficult to solve.
Depending on the connectivity objective of nodes [4–6], the network reliability evaluation problem can be sub-divided into following different cases:
Two terminal or terminal pair reliability (TPR) problems: The most common communication operation is to send messages from a source node
s
to a terminal node
t
. The terminal pair reliability of a network is defined as the probability of having at least one operational path between the nodes
s
and
t
. In case of directed networks, it is usually called (s,t) connectedness.
Global or all terminal reliability (ATR) problems: The all terminal reliability of a network is defined as the probability that for every node pair (Ni,Nj) there exist an operational path to connect them; or equivalently, the probability that there exist a working spanning tree. In the directed case, all terminal reliability is the probability that the directed graph contains at least a spanning tree rooted at the source node
s
.
K-terminal reliability (KTR) problems: The k-terminal reliability ensures that a specified set of k-nodes of the network are able to communicate with each other and it is defined as the probability that a path exists between every pair of nodes belonging to the specified set of k nodes of the network.
Generally, communication network performance is defined not only by the connectivity between nodes but also by the minimum capacity it can transfer between the nodes. The reliability measure considering both capacity and connectivity, as essential performance criterion, is known as capacity related reliability (CRR). It is defined as the probability that required amount of flow is transferred from source node s to terminal node t. Evaluation of above network reliability measures (indices) has attracted a lot of attention from researchers and many approaches have been developed so far. Next section presents a brief summary of these approaches.
1.4 Approaches for Network Reliability Evaluation
Misra and Rao [4] developed signal flow graphs: a development recognized as a significant step forward in the evaluation of network reliability. After this, a number of algorithms, techniques and approaches have been suggested in the literature. In fact, today, the use of graph theory has become inseparable from network reliability evaluation. Available literature on reliability evaluation of communication networks, considering only connectivity as performance criterion, can broadly be classified into two paradigms, viz.:
Path sets or Cut sets approaches (POC) paradigm:These use pathsets or cutsets as the starting point for TPR problems, spanning trees for ATR problems and k-trees (k-minimal cutsets) for KTR problems. In this book, the terms path sets and trees are represented by a single term path sets as approaches used for generating them are similar. From the context, whether it is pathset or spanning tree or k-tree can easily be understood. For example, when the context is TPR problem then it is pathset, when context is ATR it is spanning tree and when the context is KTR it is k-tree.
