Neeraj Kumar Goyal - Interconnection Network Reliability Evaluation

1 Cover

2 Title Page

3 Copyright Page 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 LLC For 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 Headquarters 111 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 Warranty While 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.Com Cover design by Russell Richardson

4 Series Editor Preface

5 Preface

6 1 Introduction 1.1 Introduction 1.2 Network Reliability Measures 1.3 The Probabilistic Graph Model 1.4 Approaches for Network Reliability Evaluation 1.5 Motivation and Summary

7 2 Interconnection Networks2.1 Interconnection Networks Classification 2.2 Multistage Interconnection Networks (MINs) 2.3 Research Issues in MIN Design 2.4 Some Existing MINs Implementations 2.5 Review of Topological Fault Tolerance 2.6 MIN Topological Review on Disjoint Paths 2.7 Hardware Cost Analysis 2.8 Observations 2.9 Summary

8 3 MIN Reliability Evaluation Techniques3.1 Reliability Performance Criterion 3.2 Approaches for Reliability Evaluation 3.3 Observations

9 4 Terminal Reliability Analysis of MIN Layouts 4.1 Chaturvedi and Misra Approach 4.2 Reliability Analysis of Multistage Interconnection Networks 4.3 Summary

10 5 Comprehensive MIN Reliability Paradigms Evaluation5.1 Introduction 5.2 Reliability Evaluation Approach 5.3 Reliability Evaluation Using MVI Techniques 5.4 Summary

11 6 Dynamic Tolerant and Reliable Four Disjoint MIN Layouts 6.1 Topological Design Considerations 6.2 Proposed 4-Disjoint Multistage Interconnection Network (4DMIN) Layout 6.3 Reliability Analysis and Comparison of MINs 6.4 Reliable Interconnection Network (RIN) Layout 6.5 Reliability Analysis and Comparison of MINs 6.6 Summary

12 References

13 Index

14 Also of Interest

15 End User License Agreement

1 Chapter 2Table 2.1 Dynamic networks topological features.Table 2.2 Multistage interconnection networks topology comparison.

2 Chapter 3Table 3.1 Possible permutation of switching element states for an 8×8 SEN...Table 3.2 Terminal reliability expression of 8×8 gamma networks.

3 Chapter 4Table 4.1 Adjacency matrix.Table 4.2 Steps to enumerate path sets for the network of Figure 4.1.Table 4.3 Adjacency matrix for the network in Figure 4.2.Table 4.4 Steps to enumerate path sets for the network of Figure 4.2.Table 4.5 Terminal reliability of 8×8SEN and SEN+.Table 4.6 Terminal reliability of 8×8 SEN+2.Table 4.7 Broadcast reliability of 8×8 SEN [Three Methods].Table 4.8 Broadcast reliability of 8×8 SEN+.Table 4.9 Broadcast reliability of 8×8SEN+2.Table 4.10 Adjacency matrix for the network in Figure 4.5.Table 4.11 Terminal reliability expression of 8×8 gamma networks.Table 4.12 Terminal reliability expression of 8×8CGIN 0 3.Table 4.13 Multistage interconnection networks terminal reliability evalu...

4 Chapter 5Table 5.1 Connection matrix (CM).Table 5.2 Complete Tie-set in formatted form after application of PTA.Table 5.3 Intermediate matrices in PTA.Table 5.4 Complete execution flow of PTA.Table 5.5 Paths obtained from Table 5.2 after application of PRA.Table 5.6 Connection matrix for the network in Figure 5.2.Table 5.7 Paths obtained from Table 5.2 after application of PRA.Table 5.8 Paths obtained after application of PRA.Table 5.9 Paths obtained after application of PRA for ATR evaluation.Table 5.10 Paths obtained after application of PRA.Table 5.11 Paths obtained after application of PRA.Table 5.12 Multistage interconnection networks broadcast reliability eval...Table 5.13 Multistage interconnection networks all terminal reliability e...Table 5.14 Multi Source (S) Multi Terminal (T) Reliability Evaluation (Node R...Table 5.15 Multi Source (S) Multi Terminal (T) Reliability Evaluation (No...

5 Chapter 6Table 6.1 Total number of paths for every tag for 8×8 4DMIN-1.Table 6.2 Total number of alternative paths for every tag in 8×8 MINs.Table 6.3 Number of disjoint paths for every tag in 8×8 MINs.Table 6.4 Size of crossbar switches of various MIN architectures for N=8.Table 6.5 Terminal reliability expression of 8×8 4DMIN.Table 6.6 Terminal reliability of the gamma network for the tag value-0.Table 6.7 Terminal reliability of the gamma network for the tag value-1.Table 6.8 Terminal reliability of the gamma network for the tag value-2.Table 6.9 Terminal reliability of the gamma network for the tag value-3.Table 6.10 Terminal reliability of the gamma network for the tag value-4.Table 6.11 Terminal reliability of the gamma network for the tag value-5.Table 6.12 Terminal reliability of the gamma network for the tag value-6.Table 6.13 Terminal reliability of the gamma network for the tag value- 7.Table 6.14 Multistageinterconnection networks terminal reliability evalua...

1 Chapter 1Figure 1.1 Example networks for deterministic reliability measurement.Figure 1.2 Another set of example networks for deterministic reliability m...

2 Chapter 2Figure 2.1 General topology of multistage interconnection network (MIN).Figure 2.2 Key research issues of multistage interconnection networks.Figure 2.3 MIN general characteristics classification.Figure 2.4 Taxonomy of MIN topology.Figure 2.5 Network showing one disjoint path and two redundant paths for S...Figure 2.6 Network showing two disjoint paths and three redundant paths fo...Figure 2.7 8×8 SEN showing single disjoint path for S-D node pair (0, 7)....Figure 2.8 8×8 SEN+ showing two disjoint paths for S-D node pair (0, 4).Figure 2.9 b nxb nDelta network.Figure 2.10 8×8 Omega network showing one disjoint path for S-D node pair ...Figure 2.11 8×8 Butterfly network showing one disjoint path for S-D node p.