Reliability and fault-tolerance in multistage interconnection networks

Reliability and fault-tolerance issues are important in the study of interconnection networks used in large multiprocessor systems because of the large number of components involved. In this paper we study these issues with respect to multistage networks which are typically built forN inputs andN outputs using 2 × 2 switching elements and log₂ N stages. In such networks, the failure of a switching element or connecting link destroys the communication capability between one or more pair(s) of source and destination terminals. Many techniques exist for designing multistage networks that tolerate switch and/or link failures without losing connectivity. Several approaches for achieving fault-tolerance in multistage interconnection networks are described in this paper. The techniques vary from providing redundant components in the network to making multiple passes through the faulty network. Quantitative measures are introduced for analysis of the reliability of these networks in terms of the component reliabilities. Several examples are given to illustrate the techniques. This research is supported by thensf Presidential Young Investigator Award No.dci-8452003, a grant from AT&T Information Systems, and a grant fromtrw.     

CONFIGURING BOTH BACKBONE AND LOGICAL NETWORKS OF A RECONFIGURABLE NETWORK WITH LINK FAILURES ALLOWED

This paper considers a problem of configuring both backbone and logical networks in a reconfigurable circuit-switched network where links are subject to failures. The objective is to design feasible backbone and logical networks at least cost where the cost includes backbone link capacity expansion cost, lost-call traffic penalty, and hop cost (nodal processing cost). The problem is formulated as a zero-one non-linear mixed integer programming problem, for which a solution procedure is developed by use of a Lagrangean relaxation technique and heuristic methods exploited for improving the lower and upper bounds of any intermediate solution. The solution procedure is tested for its effectiveness with various numerical examples.     

Optimized Evaluation of Mobile Base Station by Modern Topological Invariants

Due to a tremendous increase in mobile traffic, mobile operators have started to restructure their networks to offload their traffic. New research directions will lead to fundamental changes in the design of future Fifth-generation (5G) cellular networks. For the formal reason, the study solves the physical network of the mobile base station for the prediction of the best characteristics to develop an enhanced network with the help of graph theory. Any number that can be uniquely calculated by a graph is known as a graph invariant. During the last two decades, innumerable numerical graph invariants have been portrayed and used for correlation analysis. In any case, no efficient assessment has been embraced to choose, how much these invariants are connected with a network graph. This paper will talk about two unique variations of the hexagonal graph with great capability of forecasting in the field of optimized mobile base station topology in setting with physical networks. Since K-banhatti sombor invariants (KBSO) and Contrharmonic-quadratic invariants (CQIs) are newly introduced and have various expectation characteristics for various variations of hexagonal graphs or networks. As the hexagonal networks are used in mobile base stations in layered, forms called honeycomb. The review settled the topology of a hexagon of two distinct sorts with two invariants KBSO and CQIs and their reduced forms. The deduced outcomes can be utilized for the modeling of mobile cellular networks, multiprocessors interconnections, microchips, chemical compound synthesis and memory interconnection networks. The results find sharp upper bounds and lower bounds of the honeycomb network to utilize the Mobile base station network (MBSN) for the high load of traffic and minimal traffic also.     

Sliding-banyan network performance analysis

The sliding-banyan (SB) network employs an interleaved multistage shuffle-exchange topology, implemented with a three-dimensional free-space interconnection architecture that connects a multichip backplane to itself. Surface-normal emitters and detectors, which compose the stages' input-output, are spatially multiplexed within the same chip location, along with electronic control and switching resources. A simple deflection self-routing scheme minimizes internal contention, providing efficient use of switching and interconnection resources. The blocking performance of the SB is quantified through simulations based on realistic nonuniform traffic patterns. Results show that the SB architecture requires significantly fewer resources than other self-routing banyan-based networks. The multistage-switching and interconnection-resource requirements are close to the theoretical minimum for nonblocking networks, and the SB's distributed self-routing control resources grow only approximately linearly with the number of nodes, providing good scalability.     

完全二叉树到冒泡排序网络的嵌入

冒泡排序网络是由凯莱图模型设计出来的重要的互连网络.这个网络由于它的简单,点对称性和可缩结构而受到极大关注.二叉树是并行通信模式中应用十分普遍的结构.设G和H是两个给定的网络,它们可分别由两简单无向图表示,从G到H的嵌入是存在G到H的同态映射使得对G中的任何一条边,它的象是H中一条路.把二叉树嵌入到另一网络中,这样可以应用已知的二叉树的性质去研究另一网络,反过来可以用另一网络模拟二叉树.在本文中我们主要考虑完全二叉树,同根完全二叉树和双根完全二叉树能以膨胀数1嵌入到冒泡排序网络中,同时给出了这三种完全二叉树嵌入冒泡排序网络的具体构造方法.     

Exact algorithm for delay-constrained capacitated minimum spanning tree network

The delay-constrained capacitated minimum spanning tree (DC-CMST) problem of finding several broadcast trees from a source node is discussed. While the traditional CMST problem deals with only the traffic capacity constraint served by a port of the source node, and delay-constrained minimum spanning tree (DCMST) considers only the maximum end-end delay constraint, the DC-CMST problem deals with both the mean network delay and traffic capacity constraints. The DC-CMST problem consists of finding a set of minimum cost spanning trees to link end-nodes to a source node satisfying the traffic requirements at end-nodes and the required mean delay of the network. In the DC-CMST problem, the objective function is to minimise the total link cost. A dynamic programming-based three-phase algorithm that solves the DC-CMST problem is proposed. In the first phase, the algorithm generates feasible solutions to satisfy the traffic capacity constraint. It finds the CMSTs in the second phase, and allocates the optimal link capacities to satisfy the mean delay constraint in the third phase. Performance evaluation shows that the proposed algorithm has good efficiency for any network with less than 30 nodes and light traffic. The proposed algorithm can be applied to any network regardless of its configuration, and used for the topological design of local networks and for efficient routing algorithms capable of constructing least cost broadcast trees.     

An Efficient Algorithm for Global Path Optimization in MPLS Networks

This paper proposes an algorithm to solve the optimization of label switched paths (LSPs) in multiprotocol label switching (MPLS) networks. The underlying optimization problem in this task is the well-known unsplittable multicommodity flow problem equipped with practically relevant objective functions and specialized with hard technical requirements.The proposed heuristic algorithm is based on network flow theory. It incorporates iterative shortest path search and performs adaptive edge weight adjustments in order to successfully satisfy all the required traffic demands and to maximize user-defined objectives. The robust algorithm facilitates the incorporation of several strategic and optimization objectives and the fulfillment of certain hard technical requirements of the target problem domain as well. Novel features of the approach include a new adaptive path allocation/deallocation strategy based on the identification of bottleneck links, demand ordering and preprocessing phases, and a systematic path allocation control method.The efficiency of the method is empirically shown on randomly generated networks with practical sizes and topologies, and on a real-world IP (Internet Protocol) backbone network. The algorithm is able to successfully solve difficult problem instances comprising very large instances with 1000 nodes, 3500 edges and 999000 traffic demands. The computational tests demonstrate that the proposed approach can be efficiently applied to solve problem instances that embed MPLS specific hard technical requirements. Furthermore, it is shown that our algorithm offers significantly better performance than the straightforward adaptations of existing methods that were developed for related network optimization problems. Namely, our algorithm produces acceptable results quicker, it can solve problems that were not previously solvable, and it yields better results than the alternative methods. The extensive empirical tests demonstrate the combinatorial properties of the target problem and the performance aspects of the algorithm and its components as well.     

Exact topology discovery algorithm for the capacity and delay constrained loop network

We have developed an exact model and algorithm for the delay-constrained minimum cost loop problem (DC-MCLP) of finding broadcast loops from a source node. While the traditional minimum cost loop problem (MCLP) deals with only the traffic capacity constraint served by a port of source node, the DC-MCLP deals with the mean network delay and traffic capacity constraints simultaneously. The DC-MCLP consists of finding a set of minimum cost loops to link end-user nodes to a source node satisfying the traffic requirements at end-nodes and the required mean delay of the network. In the DC-MCLP, the objective function is to minimise the total link cost. We have formulated the DC-MCLP and proposed an exact algorithm for its solution. The proposed algorithm is composed of two phases: in the first phase, it generates feasible paths to satisfy the traffic capacity constraint; in the second phase it finds the exact loop topology through matching and allocating optimal link capacity to satisfy the mean delay constraint. In addition, we have derived several properties including the memory and time complexity of the proposed algorithm. Performance evaluation shows that the proposed algorithm has good efficiency for networks with less than thirty nodes and light traffic. Our proposed algorithm can be applied to find the broadcast loops for real-time multimedia traffic     

A Parallel Strategy for the Logical‐probabilistic Calculus‐based Method to Calculate Two‐terminal Reliability

The theory of network reliability has been applied to many complicated network structures, such as computer and communication networks, piping systems, electricity networks, and traffic networks. The theory is used to evaluate the operational performance of networks that can be modeled by probabilistic graphs. Although evaluating network reliability is an Non‐deterministic Polynomial‐time hard problem, numerous solutions have been proposed. However, most of them are based on sequential computing, which under‐utilizes the benefits of multi‐core processor architectures. This paper addresses this limitation by proposing an efficient strategy for calculating the two‐terminal (terminal‐pair) reliability of a binary‐state network that uses parallel computing. Existing methods are analyzed. Then, an efficient method for calculating terminal‐pair reliability based on logical‐probabilistic calculus is proposed. Finally, a parallel version of the proposed algorithm is developed. This is the first study to implement an algorithm for estimating terminal‐pair reliability in parallel on multi‐core processor architectures. The experimental results show that the proposed algorithm and its parallel version outperform an existing sequential algorithm in terms of execution time. Copyright © 2015 John Wiley & Sons, Ltd.     

Reliability analysis of shuffle-exchange network systems

Shuffle-exchange networks (SENs) have been widely considered as practical interconnection systems due to their size of its switching elements (SEs) and uncomplicated configuration. SEN is a network among a large class of topologically equivalent multistage interconnection networks (MINs) that includes omega, indirect binary n-cube, baseline, and generalized cube. In this paper, SEN with additional stages that provide more redundant paths are analyzed. A common network topology with a 2×2 basic building block in a SEN and its variants in terms of extra-stages is investigated. As an illustration, three types of SENs are compared: SEN, SEN with an additional stage (SEN+), and SEN with two additional stages (SEN+2). Finally, three measures of reliability: terminal, broadcast, and network reliability for the three SEN systems are analyzed.     

All-optical stage of an omega network

All-optical multistage interconnection networks are desirable for overcoming the limitations of optical signal regeneration in switching systems. We present a new implementation of the perfect-shuffle interconnection pattern that is coupled with an all-optical switching element, forming a complete stage of a multistage network. Switching is performed with birefringent calcite crystals and a ferroelectric liquid-crystal device, while interconnection is achieved with a space-semivariant imaging configuration. Cascading the layout allows this system to be used to construct an all-optical multistage interconnection network. An experimental demonstration of the stage is presented.     

A network-wide exact optimization approach for multiobjective routing with path protection in multiservice multiprotocol label switching networks

A multiobjective routing model for multiprotocol label switching networks with multiple service types and path protection is presented in this article. The routing problem is formulated as a biobjective integer program, where the considered objectives are formulated according to a network-wide optimization approach, i.e. the objective functions of the route optimization problem depend explicitly on all traffic flows in the network. A disjoint path pair is considered for each traffic trunk, which guarantees protection to the associated connection. A link-path formulation is proposed for the problem, in which a set of possible pairs of paths is devised in advance for each traffic trunk. An exact method (based on the classical constraint method for solving multiobjective problems) is developed for solving the formulated problem. An extensive experimental study, with results on network performance measures in various randomly generated networks, is also presented and discussed.     

Optical binary de Bruijn networks for massively parallel computing: design methodology and feasibility study

The interconnection network structure can be the deciding and limiting factor in the cost and the performance of parallel computers. One of the most popular point-to-point interconnection networks for parallel computers today is the hypercube. The regularity, logarithmic diameter, symmetry, high connectivity, fault tolerance, simple routing, and reconfigurability (easy embedding of other network topologies) of the hypercube make it a very attractive choice for parallel computers. Unfortunately the hypercube possesses a major drawback, which is the complexity of its node structure: the number of links per node increases as the network grows in size. As an alternative to the hypercube, the binary de Bruijn (BdB) network has recently received much attention. The BdB not only provides a logarithmic diameter, fault tolerance, and simple routing but also requires fewer links than the hypercube for the same network size. Additionally, a major advantage of the BdB network is a constant node degree: the number of edges per node is independent of the network size. This makes it very desirable for large-scale parallel systems. However, because of its asymmetrical nature and global connectivity, it poses a major challenge for VLSI technology. Optics, owing to its three-dimensional and globalconnectivity nature, seems to be very suitable for implementing BdB networks. We present an implementation methodology for optical BdB networks. The distinctive feature of the proposed implementation methodology is partitionability of the network into a few primitive operations that can be implemented efficiently. We further show feasibility of the presented design methodology by proposing an optical implementation of the BdB network.     

Optimization and simulation of traffic flows in the case of evacuating urban areas

In cases where urban areas need to be evacuated, a large number of vehicles must be routed through narrow street networks effectively. This paper combines two aspects of this problem. On the one hand, the traffic flows must be routed through the road network in such a way that e.g. the time required to get all out is as small as possible. Hence, we have to solve an optimization problem to find out which roads shall be used in what direction. On the other hand, even if routes are defined, traffic flows are dynamic in nature and phenomena related to the traffic jam are to be examined by simulation. By defining an optimization-based simulation procedure, we get a heuristic for the overall problem. As an example we compute and simulate an evacuation plan for a neighborhood in the city of Duisburg, Germany, to demonstrate the applicability of our approach to real-world sized problems.     

Analysis of routing protocols and interference-limited communication in large wireless networks via continuum modeling

The evaluation and assessment of the design of large wireless networks is an important problem in numerous applications. Direct simulation is a traditional approach for studying such networks but is severely limited in its utility as the size of the network increases. This necessitates other means for studying large networks, one of which is the modeling of large networks with continuum models. In this paper, we introduce nonlinear partial differential equations whose solutions approximate the expected behavior of large networks governed by probabilistic communication rules. The relative speed at which solutions can be obtained from the continuum models allows for the investigation of routing protocols and communication limitations due to interference—a feat that is not feasible via simulation methods. Specifically, we investigate the effects of a directed diffusion routing protocol and explore communication limitations in an interference-sensitive network. Network design studies using the approximating continuum models are then presented.     

Short messages

This paper has three purposes. The first one is to explain to a general audience what is involved in retrieving a web page or performing some other complex network transaction, and what can make it slow, and why the problem of slowness is likely to get worse as networked applications become more complex. The second is to describe, to those who program networked applications, certain facts that we have learnt from modelling communication networks, notably the fact of heavy-tailed distributions in traffic, which may allow more efficient applications to be written. The third is to describe to network modellers an interesting class of problems relating to algorithm design for communication networks.     

Configuring wide area computer networks

Summary Modern computer networks consist of wide area backbone networks which serve as major highways to transfer large volumes of communication traffic between access points, and local access networks which feed traffic between the backbone network and end user nodes. The topological design of wide area computer communication networks consists of selecting a set of locations for network control processors (NCPs) placement, deciding on backbone links and their capacities to connect the NCPs, linking end user nodes to the NCPs and selecting routes for routing messages between communicating end user pairs. This paper presents some of the problems faced by network designers starting from the capacity assignment problem, moving to routing and capacity assignment, followed by the topological design and capacity assignment problem; the last problem presented is the topological design and capacity expansion over time. The problems are complex combinatorial optimization problems, which require developing new solution procedures. The paper presents the problems and discusses models and solution procedures. The paper concludes with a discussion and directions for further research.This research was partially supported by a Dean's grant for faculty research at the Owen Graduate School of Management, Vanderbilt University, Nashville, TN 37203, USA.     

Interconnected logistic networks and protocols: simulation-based efficiency assessment

Logistic networks intensely use means of transportation and storage facilities to deliver goods. However, these logistic networks are still poorly interconnected and this fragmentation is responsible for a lack of consolidation and thus efficiency. To cope with the seeming contradiction of just-in-time deliveries and challenging emissions targets, a major improvement in supply networks is sought here. This new organisation is based on the universal interconnection of logistics services, namely a Physical Internet where goods travel in modular containers for the sake of interconnection in open networks. If from a logical point of view, merging container flows should improve efficiency, no demonstration of its potential has been carried out prior to the here reported research. To reach this potentiality assessment goal, we model the asynchronous shipment and creation of containers within an interconnected network of services, find the best path routing for each container and minimise the use of transportations means. To carry out the demonstration and assess the associated stakes, we use a set of actual flows from the fast-moving consumer goods sector in France. Various transportation protocols and scenarios are tested, revealing encouraging results for efficiency indicators such as CO₂ emissions, cost, lead time, delivery travel time, and so forth. As this is a first work in the field of flows transportation, the simulation model and experiment exposes many further research avenues.     

Simulating Timescale Dynamics of Network Traffic Using Homogeneous Modeling

Simulating and understanding traffic dynamics in large networks are difficult and challenging due to the complexity of such networks and the limitations inherent in simulation modeling. Typically, simulation models used to study traffic dynamics include substantial detail representing protocol mechanisms across several layers of functionality. Such models must be restricted in space and time in order to be computationally tractable. We propose an alternative simulation approach that uses homogeneous modeling with an increased level of abstraction, in order to explore networks at larger space-time scales than otherwise feasible and to develop intuition and insight about the space-time dynamics of large networks. To illustrate the utility of our approach, we examine some current understandings of the timescale dynamics of network traffic, and we discuss some speculative results obtained with homogeneous modeling. Using a wavelet-based technique, we show correlation structures, and changes in correlation structures, of network traffic under variations in traffic sources, transport mechanisms, and network structure. Our simulation results justify further investigation of our approach, which might benefit from cross-verifications against more detailed simulation models.     

A New Fuzzy Controlled Antenna Network Proposal for Small Satellite Applications

This research contributes to small satellite system development based on electromagnetic modeling and an integrated meta-materials antenna networks design for multimedia transmission contents. It includes an adaptive nonsingular mode tracking control design for small satellites systems using fuzzy waveless antenna networks. By analyzing and modeling based on electromagnetic methods, propagation properties of guided waves from metallic structures with simple or complex forms charge partially or entirely by anisotropic materials such as metamaterials. We propose a system control rule to omit uncertainties, including the inevitable approximation errors resulting from the finite number of fuzzy signal power value basis functions in antenna networks. Moreover, both the stability and the tracking performance of the closed-loop robotic system are experimentally validated. The research lies within the scope of the improvement of speed, effectiveness, and precision of numerical methods applied to electro-magnetic modeling with complex structures, essentially rectangular metallic waveguides filled with isotropic or anisotropic metamaterials. Three axes of our research are presented: waveguides, filters, and antennas. The proposed controller does not require prior knowledge about the dynamics of the fuzzy system controller for antenna networks or the offline learning phase. In addition, this work contributes to solving the problem of non-visibility stations to ensure data transmission in wireless networks. The proposed solution maximizes inter-connection by using a fuzzy controlled antenna network, and the novelty guarantees non-limited interconnection in wireless networks compared to traditional methods.