A survey of modern high-performance switching techniques
---
paper_title: Asynchronous Transfer Mode: Solution for Broadband Isdn

paper_content:

A resource for the design or installation of ISDN that covers transfer mode, ATM switching, broadband transmission, broadband subscriber premises networks--including MANs (metropolitan area networks)--and broadband terminals. Explains and evaluates the advantages and disadvantages of alternative solutions for each topic.
---
paper_title: Processor-memory interconnections for multiprocessors

paper_content:

A new class of interconnection networks is proposed for processor to memory communication in multiprocessing systems. These networks allow a direct link between any processor to any memory module. The cost of these networks is considerably less than that of full crossbars. Moreover, the design and control of these networks is simple. The proposed networks and the full crossbars are analyzed with respect to the bandwidth and the cost.
---
paper_title: Technology advances in wideband packet switching

paper_content:

The authors examine some recent technology advances in the evolution of wideband packet technology (WPT). These advances include contention resolution in WPT switch fabrics, GaAs implementation of WPT switch fabric, and packet processing in trunk interfaces. It is concluded that WPT architectures are ideally suited for aggressive incorporation in advanced VLSI technology particularly for the implementation of the core of a large self-routing multistage interconnection network and for implementation of the distributed packet processing functions of the trunk interfaces. >
---
paper_title: Performance of a broadcast packet switch

paper_content:

The results of a simulation study undertaken to evaluate a high-performance packet-switching fabric supporting point-to-point and multipoint communications are presented. This switching fabric contains several components, each based on conventional binary routing networks. The most novel element is the copy network, which performs the packet replication needed for multipoint connections. Results characterizing the performance of the copy network are presented. Several architectural alternatives for conventional binary routing networks are also evaluated. For example, the performance gains obtainable by using cut-through switching in the context of binary routing networks with small buffers are quantified. One surprising result is that networks constructed from nodes with more then two input and output ports can perform less well than those constructed from binary nodes. This result is quantified and explained. >
---
paper_title: Buffering concepts for ATM switching networks

paper_content:

The authors study various buffering strategies for switch fabrics of the Banyan type, where the buffers are located in the individual switching elements. The influence of the different strategies on the performance of the network has been evaluated under equivalent conditions to allow a comparison of the results, and the packet loss probability for networks constructed of switching elements with input buffers has been analyzed. The investigations indicate that significant performance improvements can be achieved by applying advanced buffering concepts. The choice of the best buffering strategy depends on the size of the switching elements as well as on economic and technological constraints. >
---
paper_title: A study of non-blocking switching networks

paper_content:

This paper describes a method of designing arrays of crosspoints for use in telephone switching systems in which it will always be possible to establish a connection from an idle inlet to an idle outlet regardless of the number of calls served by the system.
---
paper_title: Banyan networks for partitioning multiprocessor systems

paper_content:

This paper describes a class of partitioning networks, called banyans, whose cost function grows more slowly than that of the crossbar and whose fan-out requirements are independent of network size. Such networks can economically partition the resources of large modular systems into a wide variety of subsystems. Any possible partition can be realized by paralleling several networks or by multiplexing a single network in a manner to be described later. Results will be given indicating that a cost/performance advantage over the crossbar can be obtained for large systems and that the crossbar can, in fact, be considered a non-optimal special case of a banyan network. Inherent fail-soft capability and the existence of rapid control algorithms which can be largely performed by distributed logic within the network are also important attributes of banyans. This paper presents fundamental properties and preliminary simulation results of banyan partitioning networks. A more detailed treatment, including proofs of theoretical properties, is reserved for reference (5).
---
paper_title: Analysis and Simulation of Buffered Delta Networks

paper_content:

Delta networks are a class of multistage interconnection networks with gate complexity less than crossbar switches that are easy to control, and which include several networks that have been proposed in the literature as special cases. Buffered delta networks have queues of packets between the stages of the network. This paper presents analytic and simulation results for the performance of delta networks in a packet communication environment. The performance of buffered delta networks is compared with unbuffered delta networks and crossbar switches. It is demonstrated that buffering produces considerable improvement in the performance of these networks, making their performance comparable to that of crossbar switches.
---
paper_title: The Performance of Multistage Interconnection Networks for Multiprocessors

paper_content:

This paper studies the performance of unbuffered and buffered, packet-switching, multistage interconnection networks. We begin by reviewing the definition of banyan networks and introducing some generalizations of them. We then present an asymptotic analysis of the performance of unbuffered banyan networks, thereby solving a problem left open by Patel. We analyze the performance of the unbuffered generalized banyan networks, and compare networks with approximately equivalent hardware complexity. Finally, we analyze the performance of buffered banyan networks and again compare networks with approximately equivalent hardware complexity.
---
paper_title: Optimal rearrangeable multistage connecting networks

paper_content:

A rearrangeable connecting network is one whose permitted states realize every assignment of inlets to outlets — that is, one in which it is possible to rearrange existing calls so as to put in any new call. In the effort to provide adequate telephone service with efficient networks it is of interest to be able to select rearrangeable networks (from suitable classes) having a minimum number of crosspoints. This problem is fully resolved for the class of connecting networks built of stages of identical square switches arranged symmetrically around a center stage: roughly, the optimal network should have as many stages as possible, with switches that are as small as possible, the largest switches being in the center stage; the cost (in crosspoints per inlet) of an optimal network of N inlets and N outlets is nearly twice the sum of the prime divisors of N, while the number of its stages is 2×−1, where x is the number of prime divisors of N, in each case counted according to their multiplicity. By using a large number of stages, these designs achieve a far greater combinatorial efficiency than has been attained heretofore.
---
paper_title: A Broadband Packet Switch for Integrated Transport

paper_content:

This paper gives a broadband (total throughput approaching 1 terabit/s) self-routing packet switch design for providing flexible multiple bit-rate broadband services for an end-to-end fiber network. The switch fabric for the slotted broadband packet switch delivers exactly one packet to each output port from one of the input ports which request packet delivery to that output port. The denied requests would try again during the next slot. We discover an effective scheme, implemented by CMOS VLSI with manageable complexity, for performing this function. First, each input port sends a request for a port destination through a Batcher Sorting network, which sorts the request destinations in ascending order so that we may easily purge all but one request for the same destination. The winning request acknowledges its originating port from the output of the Batcher network, with the acknowledgment routed through a Batcher-banyan selfrouting switch. The acknowledged input port then sends the full packet through the same Batcher-banyan switch without any conflict. Unacknowledged ports buffer the blocked packet for reentry in the next cycle. We also give several variations for significantly improved performance. We then study switch performance based on some rudimentary protocols for traffic control. For the basic scheme, we analyze the throughput-delay characteristics for random traffic, modeled by random output port requests and a binomial distribution of packet arrival. We demonstrate with a buffer size of around 20 packets, we can achieve a 50 percent loading with almost no buffer overflow. Maximum throughput of switch is 58 percent. Next, we investigate the performance of the switch in the presence of periodic broadband traffic. We then apply circuit switching techniques and packet priority for high bit-rate services in our packet switch environment. We improve the throughput per port to close to 100 percent by means of parallel switch fabric, while maintaining the periodic nature of the traffic.
---
paper_title: Technology advances in wideband packet switching

paper_content:

The authors examine some recent technology advances in the evolution of wideband packet technology (WPT). These advances include contention resolution in WPT switch fabrics, GaAs implementation of WPT switch fabric, and packet processing in trunk interfaces. It is concluded that WPT architectures are ideally suited for aggressive incorporation in advanced VLSI technology particularly for the implementation of the core of a large self-routing multistage interconnection network and for implementation of the distributed packet processing functions of the trunk interfaces. >
---
paper_title: Theory of periodic contention and its application to packet switching

paper_content:

The following model of a packet switch is considered: at each clock tick, the switch attempts to route the head-of-line packet at the buffer of every input port to its destination port. Each output port can receive only one packet at a time, but there may be packets from multiple inputs destined for common output. The switch first selects exactly one packet for each requested output and then routes all selected packets through a self-route interconnection network such as the Batcher-Banyan network. Based on the traffic assumption of periodic packet streams, the necessary and sufficient clock rate is determined in order for the switch to be nonblocking. This result has turned out to be quite different from analyses based on the assumption of random traffic. >
---
paper_title: The knockout switch under nonuniform traffic

paper_content:

The knockout switch is a nonblocking, high-performance switch suitable for broadband packet switching. It allows packet losses, but the probability of a packet loss can be kept extremely small in a cost-effective way. The performance of the knockout switch was analyzed under uniform traffic. In this paper, we present a new, more general analytic model of the knockout switch, which enables us to evaluate the knockout switch under nonuniform traffic. The new model also incorporates the effects of a concentrator and a shared buffer on the packet loss probability. Numerical results for nonuniform traffic patterns of interest are presented. >
---
paper_title: Queueing in space-division packet switching

paper_content:

The authors study the performance of four different approaches for providing the queuing necessary to smooth fluctuations in packet arrivals to a space-division packet switch. They are (1) input queueing, where a separate first-in, first-out (FIFO) buffer is provided at each input to switch; (2) input smoothing, where a frame of b packets is stored at each of the N input lines to the switch and simultaneously launched into a switch fabric of size Nb*Nb; (3) output queuing, where packets are queued in a separate FIFO buffer located at each output of the switch; and (4) completely shared buffering, where all queuing is done at the outputs and all buffers are completely shared among all the output lines. >
---
paper_title: A Knockout Switch for Variable-Length Packets

paper_content:

The Knockout Switch is a new packet switch architecture recently proposed for high-speed local and metropolitan area networks, multiprocessor interconnects, and local or toll switches for integrated traffic loads. We describe an approach to extend the original Knockout Switch to work with variable-length packets. This new architecture employs an input broadcast bus arrangement to achieve complete interconnection of the inputs and outputs. Consequently, there is no congestion in the switch fabric other than the unavoidable conflict of multiple simultaneous packets destined for the same output. It is with this output contention that the Knockout principle is fully utilized to efficiently concentrate and store contending packets while maintaining the first-in first-out discipline of the packet sequence; and yet the fabric speed required is no more than the input/output line speeds, Under these design goals, no switch can yield better delay/ throughout performance. These are the most important attributes that have been preserved in the current proposal from the original Knockout Switch. For an N \times N switch configuration, the variable-length packet Knockout Switch consists of N input broadcast buses, and an N:L concentrator ( L \ll N ) and a shared buffer for each output. The design of each subsystem is discussed with emphasis on possible VLSI realization. Using today's technology, we should be able to implement the proposed switch with both input/output lines and internal hardware operating at 50 Mbits/s. The dimension of the switch ( N \times N ) can grow modularly from say 32 × 32 to 1024 × 1024, rendering a total throughput in the range of tens of gigabits per second. Future upgrading of the line interfaces to much higher speed without modification to the internal switch hardware is also possible with a modest restriction on the minimum length of new packets.
---
paper_title: Experimental broadband ATM switching system

paper_content:

The authors describe an ATM (asynchronous transfer mode) switching architecture based on a self-routing principle and an experimental system constructed by connecting self-routing modules in a three-stage link configuration. The architecture is called multistage self-routing (MSSR). It is confirmed that MSSR switching can deal with various media such as voice, data, and video. >
---
paper_title: Queueing in space-division packet switching

paper_content:

The authors study the performance of four different approaches for providing the queuing necessary to smooth fluctuations in packet arrivals to a space-division packet switch. They are (1) input queueing, where a separate first-in, first-out (FIFO) buffer is provided at each input to switch; (2) input smoothing, where a frame of b packets is stored at each of the N input lines to the switch and simultaneously launched into a switch fabric of size Nb*Nb; (3) output queuing, where packets are queued in a separate FIFO buffer located at each output of the switch; and (4) completely shared buffering, where all queuing is done at the outputs and all buffers are completely shared among all the output lines. >
---
paper_title: Integrated Services Packet Network Using Bus Matrix Switch

paper_content:

For several years, Fujitsu has been researching and developing high-speed packet switching networks, the result being an integrated multimedia information networks architecture. This architecture has already been applied to LAN systems and can now be applied to wide area corporate networks thanks to the new developments described in this paper. The most important technology-the bus matrix switch-provides a quantum leap in processing capacity up to several Gbit/s (few millions of packets every second), while keeping a very low switching delay. The performance evaluation based on our prototype models is also considered in detail. For example, a voice delay of less than 20 ms is obtained for five-hop communication. The new technologies will greatly improve for computer networks and will also enable basic and broadband ISDN.
---
paper_title: New models and algorithms for future networks

paper_content:

In future networks, transmission and switching capacity will dominate processing capacity. The authors investigate the way in which distributed algorithms should be changed in order to operate efficiently in this new environment. They introduce a class of new models for distributed algorithms which make explicit the difference between switching and processing. Based on these new models they define new message and time complexity measures which, they believe, capture the costs in many high-speed networks more accurately then traditional measures. In order to explore the consequences of the new models, they examine three problems in distributed computation. For the problem of maintaining network topology they devise a broadcast algorithm which takes O(n) messages and O(log n) time for a single broadcast in the new measure. For the problem of leader election they present a simple algorithm that uses O(n) messages and O(n) time. The third problem, distributed computation of a "globally sensitive" function, demonstrates some important features and tradeoffs in the new models and emphasizes and differences with the traditional network model. The results of the present paper influenced later research, as well as the design of IBM Networking Broadband Services (NBBS). >
---
paper_title: Network for block switching of data

paper_content:

This paper describes a possible sort of data network for the transmission of addressed blocks of data between data terminals. The network consists of a number of closed rings or loops around which data blocks circulate. Data terminals on local loops can read data into empty blocks and read data addressed to them from full blocks. Buffered devices transfer data between local and regional loops and between regional loops and a national loop. Loops so interconnected need not be synchronized; they need not even operate at the same bit rate. Provisions are made for a “busy” signal, for special loops to carry heavy traffic between particular local loops, and for alternate routing.
---
paper_title: Synchronous Composite Packet Switching-A Switching Architecture for Broadband ISDN

paper_content:

A new switching architecture for broadband ISDN, "Synchronous Composite Packet Switching (SCPS)," is proposed and evaluated. It efficiently integrates circuit and packet switching functions on a single switching system and accommodates very high speed-up to several tens of Mbit/s-communication services, such as very high speed bursts of data, still picture, and motion video, as well as 64 kbit/s or less voice and data services. The SCPS system comprises plural switch modules and plural Very high speed synchronous loops. In the SCPS system, messages on plural circuit switched channels are assembled into quasi-packets, called "composite packets," and switched synchronously between switch modules, maintaining complete time transparency and short absolute delay time. A system parameter design to obtain high system efficiency and appropriate system modularity is explained, and an example for a very large capacity transit switch of 4 Gbit/s throughput is presented. System implementation problems to realize the SCPS principle, such as efficient implementation of the composite packet assembling and loop transmission functions, are investigated and an experimental system constructed for circuit switching part is presented. The most remarkable characteristic of the SCPS is that it efficiently integrates 64 \times n kbit/s circuit switching with packet switching. Moreover, the SCPS system retains compatibility with existing networks and the possibiliy of evolution toward a future broadband ISDN. On the basis of the above investigations and experimental system construction, the authors conclude that the SCPS is one of the most practical switching architectures for the coming broadband ISDN era.
---
paper_title: Multicast and broadcast services in a knockout packet switch

paper_content:

The knockout switch is a packet-switch architecture recently proposed for high-performance packet networks. In addition to providing point-to-point connections among user pairs, a packet network must often support multicast and broadcast capabilities. Multicast connections differ from point-to-point connections in that each packet is addressed to a number of destinations. Two specific approaches using the knockout switch to provide a practical and efficient means for multicast services under both light and heavy traffic conditions are proposed. The first involves packet duplication and is more suitable for light traffic loads. The second uses a fast address comparison technique and is capable of handling larger loads. In both cases, the knockout principle is utilized to yield the best delay-throughput performance, guarantee the first-in first-out packet sequence, and provide for a simple, modular implementation. >
---
paper_title: Buffering concepts for ATM switching networks

paper_content:

The authors study various buffering strategies for switch fabrics of the Banyan type, where the buffers are located in the individual switching elements. The influence of the different strategies on the performance of the network has been evaluated under equivalent conditions to allow a comparison of the results, and the packet loss probability for networks constructed of switching elements with input buffers has been analyzed. The investigations indicate that significant performance improvements can be achieved by applying advanced buffering concepts. The choice of the best buffering strategy depends on the size of the switching elements as well as on economic and technological constraints. >
---

Title: A Survey of Modern High-Performance Switching Techniques

Section 1: INTRODUCTION
Description 1: Introduce the topic and the need for high-performance switching techniques in modern telecommunications.

Section 2: The Technology
Description 2: Discuss the historical development and basic principles of high-speed switching technology.

Section 3: Performance Evaluation
Description 3: Explain the methods for evaluating the performance of switching fabrics, including statistical models and simulation.

Section 4: Overview
Description 4: Give an overview of the structure of the book and its different parts.

Section 5: BANYAN AND BUFFERED BANYAN-BASED FABRICS
Description 5: Describe banyan and buffered banyan-based switch fabrics, including their origins, features, and performance.

Section 6: SORT-BANYAN-BASED FABRICS
Description 6: Explain sort-banyan-based switch fabrics, focusing on their internal non-blocking properties and specific implementations.

Section 7: QUEUEING
Description 7: Detail the architecture and advantages of switch fabrics that use output queueing for optimal performance.

Section 8: CROSSBAR-BASED SWITCH FABRICS
Description 8: Discuss crossbar-based switch fabrics, their simplicity, internal non-blocking properties, and different queueing approaches.

Section 9: TIME DIVISION FABRICS WITH COMMON PACKET MEMORY
Description 9: Describe switch fabrics that use a common memory for all connection paths and their operational similarities to conventional TDM circuit switches.

Section 10: FABRICS WITH SHARED MEDIUM
Description 10: Explain switch fabric architectures based on shared medium, such as buses or rings, used as switching mechanisms.

Section 11: SUMMARY
Description 11: Summarize the key concepts discussed in the paper and categorize the different high-performance switching architectures.