Trends in highly scalable crossbar-based packet switch architecture

A combined input and crosspoint queued (CICQ) switch is receiving significant attention to be the next generation high speed packet switch for its scalability; however, a multi-cabinet implementation of a combined input and crosspoint queued (CICQ) switch unavoidably introduces a large round-trip time (RTT) latency between the line cards and switch fabric, resulting a large crosspoint (CP) buffer requirement. In this paper, virtual crosspoint queues (VCQs) that significantly reduces the CP buffer requirement of the CICQ switch is investigated. The VCQs unit resides inside the switch fabric, is dynamically shared among virtual output queues (VOQ) from the same source port, and is operated at the line rate, making the implementation practical. A threshold-based exhaustive round-robin (T-ERR) arbitration is employed to reduce buffer hogging at VCQ. The T-ERR at VCQ and CP arbiters serves packets residing in a longer queue more frequently than packet residing in a shorter queue. Consequently, the T-ERR, drastically increases the throughput of the CICQ switch with small CP buffers. A multi-cabinet implementation of CICQ switch do not support multicasting traffic well since a combination of small CP buffer in the switch fabric and a large RTT latency between the line cards and switch fabric results in non-work conservation of the intra-switch link. Deployment of multicast FIFO buffer between the input buffer and CP buffer shows a promise. With its ability to achieve high throughput independent of RTT and switch port size, the integration of the VCQ architecture and T-ERR scheduler to the CICQ switch is ideal for supporting ever-increasing Internet traffic that requires higher data rate, larger switch size, and efficient multicasting.     

A high-speed integrated services ATM/STM switch

A new, high-speed switch architecture which uses Asynchronous Transfer Mode (ATM) and Synchronous Transfer Moder (STM) to support integrated voice-data-video, multicasting, and virtual networking services is described. The switch employs autonomous processing units with local memory to store switching information and is built around a modified Banyan network with bit-parallel lines linking its node processors. The system is synchronous and time is slotted with slots organized into frames. Fixed-rate video and other real-time periodic traffic are handled via STM switching, while voice, data, datagrams, and other bursty traffic are ATM switched. Multicasting is realized by allocating dedicated STM bandwidth to real-time periodic sources and virtual ATM bandwidth to bursty sources. Virtual networking is achieved by putting an STM subnetwork into place over which authorized users communicate via ATM and/or STM. Analytic models to determine the switch's performance characteristics are developed and illustrated via examples. The results show that the switch has excellent delay vs. throughput performance for ATM traffic in the presence of STM traffic, and very low blocking-and-loss probability for STM circuit set-up requests in the presence of other traffic.     

TRUSS: a reliable, scalable server architecture

Traditional techniques that mainframes use to increase reliability -special hardware or custom software - are incompatible with commodity server requirements. The Total Reliability Using Scalable Servers (TRUSS) architecture, developed at Carnegie Mellon, aims to bring reliability to commodity servers. TRUSS features a distributed shared-memory (DSM) multiprocessor that incorporates computation and memory storage redundancy to detect and recover from any single point of transient or permanent failure. Because its underlying DSM architecture presents the familiar shared-memory programming model, TRUSS requires no changes to existing applications and only minor modifications to the operating system to support error recovery.     

Paradigm: a highly scalable shared-memory multicomputerarchitecture

Paradigm (parallel distributed global memory), a shared-memory multicomputer architecture that is being developed to show that one can build a large-scale machine using high-performance microprocessors, is discussed. The Paradigm architecture allows a parallel application program to execute any of its tasks on any processor in the machine, with all the tasks in a single address space. The focus is on novel design techniques that support scalability. The key performance issues are identified, and some results to date from this work and experience with the VMP architecture design on which it is based are summarized     

A core stateless bandwidth broker architecture for scalable support of guaranteed services

We present a novel bandwidth broker architecture for scalable support of guaranteed services that decouples the QoS control plane from the packet forwarding plane. More specifically, under this architecture, core routers do not maintain any QoS reservation states, whether per-flow or aggregate. Instead, the QoS reservation states are stored at and managed by a bandwidth broker. There are several advantages of such a bandwidth broker architecture. Among others, it avoids the problem of inconsistent QoS states faced by the conventional hop-by-hop, distributed admission control approach. Furthermore, it allows us to design efficient admission control algorithms without incurring any overhead at core routers. The proposed bandwidth broker architecture is designed based on a core stateless virtual time reference system developed recently. This virtual time reference system provides a unifying framework to characterize, in terms of their abilities to support delay guarantees, both the per-hop behaviors of core routers and the end-to-end properties of their concatenation. We focus on the design of efficient admission control algorithms under the proposed bandwidth broker architecture. We consider both per-flow end-to-end guaranteed delay services and class-based guaranteed delay services with flow aggregation. Using our bandwidth broker architecture, we demonstrate how admission control can be done on a per domain basis instead of on a "hop-by-hop" basis. Such an approach may significantly reduce the complexity of the admission control algorithms. In designing class-based admission control algorithms, we investigate the problem of dynamic flow aggregation in providing guaranteed delay services and devise a new apparatus to effectively circumvent this problem. We conduct detailed analyses to provide theoretical underpinning for our schemes as well as to establish their correctness. Simulations are also performed to demonstrate the efficacy of our schemes.     

Tiny Tera: a packet switch core

Describes Tiny Tera: a small, high-bandwidth, single-stage switch. Tiny Tera has 32 ports switching fixed-size packets, each operating at over 10 Gbps (approximately the Sonet OC-192e rate, a telecom standard for system interconnects). The switch distinguishes four classes of traffic and includes efficient support for multicasting. We aim to demonstrate that it is possible to use currently available CMOS technology to build this compact switch with an aggregate bandwidth of approximately 1 terabit per second and a central hub no larger than a can of soda. Such a switch could serve as a core for an ATM switch or an Internet router. Tiny Tera is an input-buffered switch, which makes it the highest bandwidth switch possible given a particular CMOS and memory technology. The switch consists of three logical elements: ports, a central crossbar switch, and a central scheduler. It queues packets at a port on entry and optionally prior to exit. The scheduler, which has a map of each port's queue occupancy, determines the crossbar configuration every packet time slot. Input queueing, parallelism, and tight integration are the keys to such a high-bandwidth switch. Input queueing reduces the memory bandwidth requirements: When a switch queues packets at the input, the buffer memories need run no faster than the line rate. Thus, there is no need for the speedup required in output-queued switches     

ATLAS I: implementing a single-chip ATM switch with backpressure

ATLAS I is a general-purpose, single-chip, gigabit asynchronous transfer mode (ATM) switch with advanced architectural features. To evaluate the architecture of ATLAS I, we analyzed the design complexity and silicon cost of the chip's individual functions. Our analysis suggests possible improvements     

MTCP: scalable TCP-like congestion control for reliable multicast

We present MTCP, a congestion control scheme for large-scale reliable multicast. Congestion control for reliable multicast is important, because of its wide applications in multimedia and collaborative computing, yet non-trivial, because of the potentially large number of receivers involved. Many schemes have been proposed to handle the recovery of lost packets in a scalable manner, but there is little work on the design and implementation of congestion control schemes for reliable multicast. We propose new techniques that can effectively handle instances of congestion occurring simultaneously at various parts of a multicast tree.Our protocol incorporates several novel features: (1) hierarchical congestion status reports that distribute the load of processing feedback from all receivers across the multicast group, (2) the relative time delay concept which overcomes the difficulty of estimating round-trip times in tree-based multicast environments, (3) window-based control that prevents the sender from transmitting faster than packets leave the bottleneck link on the multicast path through which the sender's traffic flows, (4) a retransmission window that regulates the flow of repair packets to prevent local recovery from causing congestion, and (5) a selective acknowledgment scheme that prevents independent (i.e., non-congestion-related) packet loss from reducing the sender's transmission rate. We have implemented MTCP both on UDP in SunOS 5.6 and on the simulator ns, and we have conducted extensive Internet experiments and simulation to test the scalability and inter-fairness properties of the protocol. The encouraging results we have obtained support our confidence that TCP-like congestion control for large-scale reliable multicast is within our grasp.     

Araneola: A scalable reliable multicast system for dynamic environments

This paper presents Araneola (Araneola means “little spider” in Latin.), a scalable reliable application-level multicast system for highly dynamic wide-area environments. Araneola supports multi-point to multi-point reliable communication in a fully distributed manner, while incurring constant load (in terms of message and space complexity) on each node. For a tunable parameter k≥3, Araneola constructs and dynamically maintains a basic overlay structure in which each node’s degree is either k or k+1, and roughly 90% of the nodes have degree k. Empirical evaluation shows that Araneola’s basic overlay achieves three important mathematical properties of k-regular random graphs (i.e., random graphs in which each node has exactly k neighbors) with N nodes: (i) its diameter grows logarithmically with N; (ii) it is generally k-connected; and (iii) it remains highly connected following random removal of linear-size subsets of edges or nodes. The overlay is constructed and maintained at a low cost: each join, leave, or failure is handled locally, and entails the sending of only about 3k messages in total, independent of N. Moreover, this cost decreases as the churn rate increases.The low degree of Araneola’s basic overlay structure allows for allocating plenty of additional bandwidth for specific application needs. In this paper, we give an example for such a need — communicating with nearby nodes; we enhance the basic overlay with additional links chosen according to geographic proximity and available bandwidth. We show that this approach, i.e., a combination of random and nearby links, reduces the number of physical hops messages traverse without hurting the overlay’s robustness, as compared with completely random Araneola overlays (in which all the links are random) with the same average node degree.Given Araneola’s overlay, we sketch out several message dissemination techniques that can be implemented on top of this overlay. We present a full implementation and evaluation of a gossip-based multicast scheme, with up to 10,000 nodes. We show that compared with a (non-overlay-based) gossip-based multicast protocol, gossiping over Araneola achieves substantial improvements in load, reliability, and latency.     

A scalable and reliable paradigm for media on demand

The authors describe a system for solving some of the conventional problems associated with traditional streaming protocols by using forward error correction codes to let multiple clients recover from different packet losses using the same redundant data     

Design of a fault-tolerant multichannel ATM switch for BISDN

One of the techniques to improve the throughput and the reliability of the ATM switch is to provide multiple channels for the cells destined to the same switching node. The performance advantages of multichannel switch architectures have been discussed in the literature (T.H. Cheng and D.G. Smith, Proc. ICC'91, pp. 1028–1032, A. Lin and J. Silvester, Proc. INFOCOM'90, pp. 803–810, A. Pattavina, IEEE J. Selected Areas Comm.SAC-6 (1988) 237–243 and L.T. Wu et al., 1988 International Zurich Seminar on Digital Communications, pp. 191–197). However, these switch architectures do not preserve the cell sequence thus requiring the end system to resequence the cells. In this paper, we introduce a multichannel ATM switch architecture that guarantees the cell sequence throughout the network when the channel grouping is used in the switching nodes. The switch consists of two modified banyan networks and a Batcher sorter (Batcher, AFIPS Proc. Spring Joint Comput. Conf., pp. 307–314, 1968). It is shown that the cell sequence will be preserved by providing a virtual FIFO queue within the switch architecture. The virtual FIFO queue is shared by all the input-output pairs so that the cell loss probability is significantly reduced. The switch has a distributed control and allows a large switch size without degrading the performance. Furthermore, a simple update of entries in the lookup table allows the fault-tolerant operation in the event of the link or node failure in the network. The performance analysis of the switch shows that the number of buffers and the average cell delay can be significantly reduced in the proposed switch while maintaining the required throughput and cell loss probability compared to the multichannel switches with dedicated buffers.     

Grid-based switch fabrics: a new approach in designing fault-tolerant ATM switches

ATM is the switching and multiplexing technology chosen to be used in the implementation of B-ISDN, because of its superiority in fast packet switching. However, the use of ATM switches with large number of input and output ports have been proven to be a bottleneck in wide area ATM networks. In this paper, we propose a new space-division grid-based ATM architecture with fault tolerant characteristics and minimal number of switching elements (SE's).     

Efficient and adaptive epidemic-style protocols for reliable and scalable multicast

Epidemic-style (gossip-based) techniques have recently emerged as a class of scalable and reliable protocols for peer-to-peer multicast dissemination in large process groups. However, popular implementations of epidemic-style dissemination suffer from two major drawbacks: 1) Network overhead: when deployed on a WAN-wide or VPN-wide scale, they generate a large number of packets that transit across the boundaries of multiple network domains (e.g., LANs, subnets, ASs), causing an overload on core network elements such as bridges, routers, and associated links. 2) Lack of adaptivity: they impose the same load on process group members and the network even under reduced failure rates (viz., packet losses, process failures). In this paper, we describe two protocols to address these problems: 1) a hierarchical gossiping protocol and 2) an adaptive dissemination framework (for multicasts) that allows use of any gossiping primitive within it. These protocols work within a virtual peer-to-peer hierarchy called the leaf box hierarchy. Processes can be allocated in a topologically aware manner to the leaf boxes of this structure, so that protocols 1 and 2 produce low traffic across domain boundaries in the network and induce minimal overhead when there are no failures.     

一种高可靠性嵌入式系统的主备切换设计

高可靠性作为通信设备向用户提供的产品保证正越来越受到重视，成为必不可少的条件之一，而主备切换是双机系统实现高可靠性的一种可行技术。文章主要从软件系统设计方面主备切换的具体实现方案，功能模块的划分以及相应的数据结构方面进行了综合讨论，为类似设计提供了参考。     

LinuxDirector: A connection director for scalable internet services

LinuxDirector is a connection director that supports load balancing among multiple Internet servers,which can be used to build scalable Internet services based on clusters of servers.LinuxDirector extends the TCP/IP stack of Linux Kernel to support three IP load balancing techniques,VS/NAT,VS/TUN and VS/DR.Four scheduling algorithms have been implemented to assign connections to different servers.Scalability is achieved by transparently adding or removing a node in the cluster.High availability is provided by detecting node or daemon failure and reconfiguring the system appropriately.This paper describes the design and implementation of LinuxDirector and presents serveral of its features including scalability,high availability and connection affinity.     

Design for a robust simple and highly reliable filestore

This note describes a robust, simple-to-implement filestore. The filestore provides facilities for creating named, dynamically allocated files which can be accessed via a block level interface (both randomly and sequentially). The design is particularly well-suited to the type of environment found on personal computers, word processors, and other stand alone systems where a high degree of resilience against hardware and software malfunction is required. It is ideally suited for use with floppy discs or any other cheap removable rotating medium, because of its high reliability and good performance, gained at the price of a slight reduction in available disc capacity.     

Towards highly available and scalable high performance clusters

In recent years, we have witnessed a growing interest in high performance computing (HPC) using a cluster of workstations. This growth made it affordable to individuals to have exclusive access to their own supercomputers. However, one of the challenges in a clustered environment is to keep system failure to the minimum and to achieve the highest possible level of system availability. High-Availability (HA) computing attempts to avoid the problems of unexpected failures through active redundancy and preemptive measures. Since the price of hardware components are significantly dropping, we propose to combine both HPC and HA concepts and layout the design of a HA-HPC cluster, considering all possible measures. In particular, we explore the hardware and the management layers of the HA-HPC cluster design, as well as a more focused study on the parallel-applications layer (i.e. FT-MPI implementations). Our findings show that combining HPC and HA architectures is feasible, in order to achieve HA cluster that is used for High Performance Computing.     

Correction to: Uniform and scalable sampling of highly configurable systems

Empirical Software Engineering - Testing Internet of Things (IoT) systems is challenging. This is not only because of the various aspects of IoT systems, such as software, hardware, and network...     

Computational aspects of a scalable high-order discontinuous Galerkin atmospheric dynamical core

A new atmospheric general circulation model (dynamical core) based on the discontinuous Galerkin (DG) method is developed. This model is conservative, high-order accurate and has been integrated into the NCAR’s high-order method modeling environment (HOMME) to leverage scalable parallel computing capability to thousands of processors. The computational domain for this 3-D hydrostatic model is a cubed-sphere with curvilinear coordinates; the governing equations are cast in flux-form. The horizontal DG discretization employs a high-order nodal basis set of orthogonal Lagrange-Legendre polynomials and fluxes of inter-element boundaries are approximated with Lax-Friedrichs numerical flux. The vertical discretization follows the 1-D vertical Lagrangian coordinates approach combined with the cell-integrated semi-Lagrangian conservative remapping procedure. Time integration follows the third-order strong stability preserving explicit Runge-Kutta scheme. The domain decomposition is applied through space-filling curve approach. To validate the 3-D DG model in HOMME framework, a baroclinic instability test is used and the results are compared with those from the established models. Parallel performance is evaluated on IBM Blue Gene/L supercomputers.