Design of Optical Rearrangeable Nonblocking MINs Under Various Crosstalk Constraints

Optical interconnection networks suffer from the intrinsic crosstalk problem that should be overcome to make them work properly. Vertical stacking of optical banyan networks is a novel scheme for constructing nonblocking optical multistage interconnection networks (MINs). Rearrangeable nonblocking optical MINs are feasible since they have lower complexity than their strictly nonblocking counterparts. In this paper, we determine the sufficient condition for these MINs to be rearrangeable nonblocking under various crosstalk constraints. We show how the crosstalk constraint affects the design of rearrangeable nonblocking MINs and demonstrate that these networks can tolerate a stricter crosstalk constraint without increasing their hardware complexity significantly. The results in the paper will be useful in designing optical MINs with reasonable hardware cost and crosstalk level.     

Behaviour of circuit-switched multistage networks in presence of memory hot spot

Addresses the important problem of evaluating the performance of tightly coupled multiprocessor systems under memory hot spot traffic by presenting an interference analysis of multistage interconnection networks (MINs) for such systems. It is shown that the tree saturation effect does not occur in nonblocking circuit-switched MINs.<>     

A survey of multistage interconnection networks in fast packet switches

This paper comprises a broad survey of multistage interconnection networks (MINs), which are incorporated into the underlying fabric of fast packet switches for use in broadband ATM networks. A general classification of MINs based on network functionality and blocking characteristics in the context of fast packet switches is presented in order to emphasize the fundamental principles which differentiate the network architectures. For each class of network, important theoretical results are given and the underlying design principles are explained with the best known explicit examples. Special emphasis is given to the implementation complexities and control strategies of individual approaches.     

Performance evaluation for single‐ and semi‐layer multistage interconnection networks servicing multicast traffic by full multicast operation

Here a novel analytical method for performance prediction estimation of single‐ and multi‐layer multistage interconnection networks (MINs) under multicast environments is presented. The ‘Cell Replication While Routing’ is used as a packet routing technique and the ‘full multicast’ mode as transmission policy is employed in all the MINs under study. This model is developed for single‐layer MINs and is extended and applied to special types of multi‐layer MINs, called semi‐layer MINs, which support mixed traffic patterns such as unicast and multicast in uniform traffic conditions. The results confirm the significant performance saturation of single‐layer MINs and the improvement of corresponding performance indicators by semi‐layer MINs. The proposed analytical framework is anticipated to be a very useful tool in evaluating the performance of semi‐layer MINs in designing more efficient QoS networks. Copyright © 2010 John Wiley & Sons, Ltd.     

Reliability analysis of interconnection networks using hierarchicalcomposition

Based on the nature of the upper- and lower-bound block diagram models of multistage interconnection networks (MINs), a series system consisting of independent subsystems is considered. To model the reliability of such a system with online repair and imperfect coverage, the usual approach is to construct and solve a large, overall Markov model. A two-level hierarchical model is instead proposed in which each subsystem is modeled as a Markov chain and the system reliability is then modeled as a series system of independent Markov components. This technique is extended to compute the instantaneous availability of the system with imperfect coverage and online repair. Extensions to allow for transient faults and phase-type repair time distributions are straightforward. It should be possible to apply this approach to other fault-tolerant MINs and to any system that can be modeled as a series system where each subsystem has a parallel-redundant structure     

The selective extra stage butterfly

Multistage interconnection networks (MINs) have been used extensively as communication networks in parallel machines due to their high bandwidth, low diameter and constant degree switches. The fault-tolerance of multistage networks can be improved by simply adding extra stages to the network. A novel method of attaching the extra stages in MINs so that they are used in the absence of faults but not necessarily by all messages is suggested. Messages can adaptively select the shortest path to their destination or use one of the longer paths going through the extra stages. Performance results for the method (obtained through simulation), using various traffic loads both in the presence and absence of faults, are presented     

Fault-tolerant multicasting in MINs for ATM switches

This article proposes a fault-tolerant multicast routing algorithm in multistage interconnection networks (MINs) for ATM switch architectures. It employs both region and cube encoding schemes as the header encoding scheme. A multicast packet can be routed to its destinations in only two phases through the MIN having a single faulty element     

A new model for the performance evaluation of synchronous circuitswitched multistage interconnection networks

Patel (1981) proposed a probabilistic approach to analyze the performance of synchronous multistage interconnection networks (MINs) based on a uniform reference model and the assumption of independent requests. Patel's model and analytical results have been widely adopted by numerous researchers as a basis to investigate various aspects of MINs. We study in detail the effects of the independence assumption on the accuracy of system performance and point out the factors which cause an inaccuracy. A new queueing model is then proposed and is shown to be very accurate. Since only six states are needed, independent of the size of MINs, this new model is very efficient computationally     

A machine learning assisted optical multistage interconnection network: Performance analysis and hardware demonstration

Integration of the machine learning (ML) technique in all-optical networks can enhance the effectiveness of resource utilization, quality of service assurances, and scalability in optical networks. All-optical multistage interconnection networks (MINs) are implicitly designed to withstand the increasing high-volume traffic demands at data centers. However, the contention resolution mechanism in MINs becomes a bottleneck in handling such data traffic. In this paper, a select list of ML algorithms replaces the traditional electronic signal processing methods used to resolve contention in MIN. The suitability of these algorithms in improving the performance of the entire network is assessed in terms of injection rate, average latency, and latency distribution. Our findings showed that the ML module is recommended for improving the performance of the network. The improved performance and traffic grooming capabilities of the module are also validated by using a hardware testbed.     

A novel scheme to improve fault-tolerant capabilities of multistage interconnection networks

In this paper, we propose a novel augmenting and partitioning scheme for constructing multistage interconnection networks (MINs) with improved fault-tolerant capabilities. We first propose a partitioning scheme to construct and analyze partitioned MINs (PMINs). A simulation method is developed, based on the stuck-at fault model, to evaluate dynamic full access (DFA) and average number of passes in PMINs. We then propose an augmenting scheme to construct augmented partitioned MINs (APMINs) with further enhanced fault-tolerant capabilities. Simulation analysis of APMINs, based on the switch level fault model, showed that the proposed scheme significantly improves the fault-tolerant capability of MINs. Finally, the effectiveness of the proposed scheme is evaluated with respect to cost, DFA, locality, and average path length. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multistage network with globally controlled switching stages and its implementation using optical multi-interconnection modules

Plane-to-plane guided-wave-based interconnection modules are proposed as building blocks for scalable optoelectronic multistage interconnection networks (MINs). This approach leads naturally to a MIN paradigm based not on cascading switching stages containing several size-reduced crossbars, as in the shuffle-exchange (SE) networks, but on cascading permutation-reduced crossbars instead, one per stage. The interest of such an architecture lies in the control simplicity and scalability potential. Transparent circuit switching for permutation routing is possible in such an unbuffered "globally switched" multistage interconnection network (GSMIN). Preliminary experiments using fiber-based interconnection modules are presented. Performance analysis and simulation of a buffered GSMIN is also studied for packet routing purposes.     

Dependent and multimode failures in reliability evaluation ofextra-stage shuffle-exchange MINs

Previous reliability evaluations for multistage interconnection networks (MINs) assumed that “all failures are statistically-independent and that no degraded operational modes exist for switches”, though these assumptions are not realistic. For example, researchers have described instances of statistically-dependent failures, or fault side-effects, in some MINs. This paper presents efficient algorithms for terminal, broadcast, and K-terminal reliability evaluation of the shuffle-exchange network with an extra stage (SENE), a redundant-path MIN, under assumptions that allow statistical-dependence between failures and degraded operational modes for switches. A modified shock-model incorporates failure statistical-dependency and multiple operational modes into the reliability evaluation. For an N×N SENE, the reliability algorithms and their run-times are: terminal and broadcast →O(log(N)), and K-terminal→O(|K|·log(N))     

Reliability evaluation of multistage interconnection networks with multi-state elements

This paper presents a graph-theoretic method for the reliability evaluation of multistage interconnection networks with multistate elements. For the purpose of analysis, the generalized cube (GC), a unique-path MIN and an extra-stage cube (ESC), a fault-tolerant variation of GC, are considered. An algorithm is presented to evaluate three reliability measures, i.e. terminal reliability (TR), broadcast reliability (BR) and network reliability (NR) of MINs for different reliability values of links and switches. The proposed method is found to be simple and computationally efficient compared to the existing techniques, and therefore can be applied for reliability evaluation of other large interconnection networks used in parallel computing systems.     

Reliability and performance evaluation of four tree multistage interconnection network

Reliability and performance of a multiprocessor system depend heavily upon the design of its interconnection network. This paper presents a comprehensive treatment to analyse a four tree network, a new class of irregular multistage interconnection networks (MIN), for reliability and performance. The results obtained are compared with the augmented shuffle exchange network (ASEN), a network with low link and switch complexity and having significantly improved reliability and performance amongst the regular type of MINs. The reliability results, both optimistic and pessimistic, are better than for the ASEN as well as for most of the other networks. The performance analysis in the circuit switched environment shows that the probability of accepting the requests is significantly improved and there is negligible degradation in performance with increasing network size.     

Optical multistage interconnection networks: new challenges andapproaches

Optical interconnections for communication networks and multiprocessor systems have been studied extensively. A basic element of optical switching networks is a directional coupler with two inputs and two outputs or switching elements (SEs). Depending on the control voltage applied to it, an input optical signal is coupled to either of the two outputs, setting the SE to either the straight or cross state. A class of topologies that can be used to construct optical networks is multistage interconnection networks, which interconnect their inputs and outputs via several stages of SEs. Although optical MINs hold great promise and have demonstrated advantages over their electronic counterparts, they also introduce new challenges such as how to deal with the unique problem of avoiding crosstalk in the SEs. In this article we survey the research carried out, including major challenges encountered and approaches taken, on optical MINs     

Method of obtaining algorithms for nonblocking two-dimensional optical multistage interconnection networks

A mapping rule is described which enables an algorithm for controlling a conventional perfect shuffle multistage network to be converted into one which can configure a two-dimensional network suitable for a hybrid optoelectronic switching system.<>     

Reliability enhancement by time and space redundancy in multistageinterconnection networks

The authors present the dynamic full access (DFA) properties of fault tolerant multistage interconnection networks (MINs) which have multiple connections to the inputs and outputs, and thus potentially no hardcore. When full access is lost due to multiple faults, but DFA exists, multiple pass routing could be utilized to achieve graceful degradation. Some efficiency conditions for the existence of DFA in a broad class of fault tolerant MINs are derived. The reliability of four multiple path MINs under DFA is studied. The metrics used are the probability of existence of DFA and the mean time to failure. One particular network (the MD-Omega), which uses a minimum amount of hardware redundancy to provide two connections from each source to the MIN and to each destination from the MIN, shows the most gain in reliability when time redundancy is used. The MD-Omega network has a 2×2 switch as its basic element, but is almost as reliable as another fault tolerant MIN, the ASEN, which uses a 3×3 element, when multiple pass routing is used     

Banyan网输入输出排队的神经网络调度及其实现

Ｂａｎｙａｎ网是一种多级互联网络，它广泛地应用在ＡＴＭ交换结构中．Ｂａｎｙａｎ网输入排队的神经网络调度方法已有文章提出，但其硬件实现比较复杂．本文提出了一种Ｂａｎｙａｎ网输入输出排队的神经网络调度方法，它的硬件实现容易．计算机模拟结果表明，该调度方法是非常有效的．在此，还给出了该系统的硬件实现方法．     

Performance analysis of single-buffered multistage interconnectionnetworks

A new model for the performance evaluation of single-buffered multistage interconnection networks (MINs) is proposed. Previous models proposed in solving this problem are either not accurate enough or only applicable to a special case where the switching elements (SEs) are 2×2 crossbars. This new model allows the analysis of a MIN with SEs of arbitrary sizes (i.e., a×a) and, through extensive simulations, has been shown to be very accurate. Since only three states are required at each stage of a MIN, this model is efficient computationally