Wide-sense non-blocking multicast ATM switches

Non-blocking multicast ATM switches can simplify the call admission control process and increase the utilisation level of external links. The condition for wide-sense non-blocking multicast ATM switches is derived and the routing algorithm is proposed. The required number of middle switches for the wide-sense non-blocking multicast switch is significantly less than that of the strictly non-blocking multicast switch     

The single-queue switch: a building block for switches withprogrammable scheduling

We introduce a new approach to ATM switching. We propose an ATM switch architecture which uses only a single shift-register-type buffering element to store and queue cells, and within the same (physical) queue, switches the cells by organizing them in logical queues destined for different output lines. The buffer is also a sequencer which allows flexible ordering of the cells in each logical queue to achieve any appropriate scheduling algorithm. This switch is proposed for use as the building block of large-stale multistage ATM switches because of low hardware complexity and flexibility in providing (per-VC) scheduling among the cells. The switch can also be used as scheduler/controller for RAM-based switches. The single-queue switch implements output queueing and performs full buffer sharing. The hardware complexity is low. The number of input and output lines can vary independently without affecting the switch core. The size of the buffering space can be increased simply by cascading the buffering elements     

A Shared Buffer Memory ATM Access Switch

１ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅＡｓｙｎｃｈｒｏｎｏｕｓＴｒａｎｓｆｅｒＭｏｄｅ（ＡＴＭ）ｉｓｃｏｎｓｉｄｅｒｅｄａｐｒｏｍｉｓｉｎｇｔｅｃｈｎｉｑｕｅｔｏｔｒａｎｓｆｅｒａｎｄｓｗｉｔｃｈｖａｒｉｏｕｓｋｉｎｄｓｏｆｍｅｄｉａ，ｓｕｃｈａｓｔｅｌｅ...     

Design of wide-sense nonblocking multicast ATM switches

Nonblocking multicast asynchronous transfer mode (ATM) switches can simplify the call admission control process and increase the external links' utilization. We derive the wide-sense nonblocking condition for multicast ATM switches based on a general Clos network. We also propose a routing algorithm to achieve wide-sense nonblocking. It is illustrated by an example that the number of required middle stages in our switch is significantly less than that of strictly nonblocking multicast switches     

Congestion control in asynchronous, high-speed wormhole routingnetworks

High-speed networks use lightweight protocols and a simple switch architecture for achieving higher speeds. A lightweight switching technique for local area and campus environments is wormhole routing, in which the head of a packet (worm), upon arriving at an intermediate switch, is immediately forwarded to the next switch on the path. Thus, the packet, like a worm, may stretch across several intermediate switches and links. Wormhole routing networks provide low latency. However, they are particularly prone to congestion, thus requiring careful flow control. The authors consider high-speed, asynchronous, unslotted wormhole routing networks. For such networks, two different flow control mechanisms are compared and contrasted, namely, backpressure flow control and deflection routing (with local input rate control). With backpressure, in order to maintain deadlock-free routing, either up/down routing or shortest path routing with virtual channels is assumed. With deflection routing, to avoid livelocks, worm alignment (delayed deflection) is performed at the switches. It is shown via simulation that the throughput performance of the two schemes is comparable (except for up/down routing). The authors also discuss the tradeoffs with respect to the complexity of hardware, routing protocols and buffer requirements. The authors further examine the role of input rate control at the hosts to overcome unbounded delays typical of deflection routing, and show it is possible to achieve lower average number of hops and transit delays by employing suitable input rate control policies     

Designing a practical ATM LAN

The adaptor cards and driver software for workstations and local asynchronous transfer mode (ATM) switches and switch control software used in an ATM local area network (LAN) system are discussed. It is shown that the ATM hardware and software components together provide services that are essential for ATM to be considered a realistic alternative to current shared-media LANs. These services include: completely transparent support for the TCP/IP protocol suite, an application programming interface for full access to the underlying ATM capabilities, support for AAL5, AAL3/4, and the null AAL, both connection-oriented and connectionless service, dynamic connection establishment or switched virtual circuits, resource reservation of guaranteed bandwidth and quality of service, full-bandwidth multicast and broadcast, virtual path and channel routing among multiple switches, automatic configuration and failure recovery, dynamic address assignment and internetwork address resolution, and network management via the simple network management protocol (SNMP)     

Cell loss analysis and design trade-offs of nonblocking ATMswitches with nonuniform traffic

In practical ATM switch design, a proper dimensioning of buffer sizes and a cost effective selection of speed-up factor should be considered to guarantee a specified cell loss requirement for a given traffic. Although a larger speed-up factor provides better throughput for the switch, increasing the speed-up factor involves greater complexity and cost. Hence, it may not be cost effective to increase the speed-up factor for 100% throughput. Moreover, with a given buffer budget, an increase in the speed-up factor beyond a certain value only adds to the cell loss. The paper addresses design trade-offs existing between finite input/output buffer sizes and speed-up factor in a nonblocking ATM switch. Another important issue is the adverse effect on cell loss performance caused by nonuniform traffic (different traffic intensity and unevenly distributed routing). The paper analyzes cell loss performance of ATM switches with nonuniform traffic, and examines the effect of each nonuniform traffic parameter. The authors also provide an algorithm for effective buffer sharing that alleviates the performance degradation caused by traffic nonuniformity     

A 622-Mb/s 8×8 ATM switch chip set with shared multibufferarchitecture

An asynchronous transfer mode (ATM) switch chip set, which employs a shared multibuffer architecture, and its control method are described. This switch architecture features multiple-buffer memories located between two crosspoint switches. By controlling the input-side crosspoint switch so as to equalize the number of stored ATM cells in each buffer memory, these buffer memories can be treated as a single large shared buffer memory. Thus, buffers are used efficiently and the cell loss ratio is reduced to a minimum. Furthermore, no multiplexing or demultiplexing is required to store and restore the ATM cells by virtue of parallel access to the buffer memories via the crosspoint switches. Access time for the buffer memory is thus greatly reduced. This feature enables high-speed switch operation. A three-VLSI chip set using 0.8-μm BiCMOS process technology has been developed. Four aligner LSIs, nine bit-sliced buffer-switch LSIs, and one control LSI are combined to create a 622-Mb/s 8×8 ATM switching system that operates at 78 MHz. In the switch fabric, 155-Mb/s ATM cells can also be switched on the 622-Mb/s port using time-division multiplexing     

Path switching-a quasi-static routing scheme for large-scale ATMpacket switches

A quasi-static routing scheme called path switching for large-scale ATM packet switch systems is proposed. Previously the Clos network has been used as the model for many large-scale ATM switch architectures, in which the most difficult issue is path and bandwidth assignment for each connection request. The static routing scheme, such as multirate circuit switching, does not fully exploit the statistical multiplexing gain. In contrast, the dynamic routing scheme, such as straight matching, requires slot-by-slot computation of route assignment. Path switching is a compromise of these two routing schemes. It uses a predetermined periodical connection pattern in the central stage, look-ahead selection in the input stage, and output queueing in the last stage. The scheduling of path switching consists of capacity assignment and route assignment. The capacity assignment is constrained by the quality of service of connection requests. The route assignment is based on the timespace interleaving of the coloring of bipartite multigraphs. We show that path switching can handle multirate and multimedia traffic effectively in the Clos network     

The UniMIN switch architecture for large-scale ATM switches

A general expansion architecture is proposed that can be used in building large-scale switches using any type of asynchronous transfer mode (ATM) switch. The proposed universal multistage interconnection network (UniMIN) switch is composed of a buffered distribution network (DN) and a column of output switch modules (OSMs), which can be any type of ATM switch. ATM cells are routed to their destination using a two-level routing strategy. The DN provides each incoming cell with a self-routing path to the destined OSM, which is the switch module containing the destination output port. Further routing to the destined output port is performed by the destination OSM. Use of the channel grouping technique yields excellent delay/throughput performance in the DN, and the virtual FIFO concept is used for implementing the output buffers of the distribution module without internal speedup. We also propose a “fair virtual FIFO” to provide fairness between input links while preserving cell sequence. The distribution network is composed of one kind of distribution module which has the same size as the OSM, regardless of the overall switch size N. This gives good modular scalability in the UniMIN switch. Performance analysis for uniform traffic and hot-spot traffic shows that a negligible delay and cell loss ratio in the DN can be achieved with a small buffer size, and that DN yields robust performance even with hot-spot traffic. In addition, a fairness property of the proposed fair virtual FIFO is shown by a simulation study     

ATM网络最小最大信元丢失率路由规划

本文基于ＡＴＭ网络交换节点,建立其数学模型,以链路最大信元丢失率最小为目标,对ＡＴＭ网络由选择作数学规划,并进行计算机模拟。结果表明,对于简单的拓扑结构,最小最大信元丢失率的路由策略和最短路径策略效果类似;对于复杂的拓扑结构,由于链路信元丢失率判别较大,应先计算出各条链路的最大信元丢失率,然后例整个路由上的信元丢失率最小进行选路。     

Design and implementation of Abacus switch: a scalable multicastATM switch

Describes a new architecture for a multicast ATM switch scalable from a few tens to a few thousands of input ports. The switch, called the Abacus switch, has a nonblocking switch fabric followed by small switch modules at the output ports. It has buffers at input and output ports. Cell replication, cell routing, output contention resolution, and cell addressing are all performed in a distributed way so that it can be scaled up to thousands of input and output ports. A novel algorithm has been proposed to resolve output port contention while achieving input buffers sharing, fairness among the input ports, and call splitting for multicasting. The channel-grouping mechanism is also adopted in the switch to reduce the hardware complexity and improve the switch's throughput, while the cell sequence integrity is preserved. The switch can also handle multiple priority traffic by routing cells according to their priority levels. The performance study of the Abacus switch in throughput, average cell delay, and cell loss rate is presented. A key ASIC chip for building the Abacus switch, called the ARC (ATM routing and concentration) chip, contains a two-dimensional array (32×32) of switch elements that are arranged in a crossbar structure. It provides the flexibility of configuring the chip into different group sizes to accommodate different ATM switch sizes. The ARC chip has been designed and fabricated using 0.8 μm CMOS technology and tested to operate correctly at 240 MHz     

A growable packet (ATM) switch architecture: design principles andapplication

The problem of designing a large high-performance, broadband packet of ATM (asynchronous transfer mode) switch is discussed. Ways to construct arbitrarily large switches out of modest-size packet switches without sacrificing overall delay/throughput performance are presented. A growable switch architecture is presented that is based on three key principles: a generalized knockout principle exploits the statistical behaviour of packet arrivals and thereby reduces the interconnect complexity, output queuing yields the best possible delay/throughput performance, and distributed intelligence in routing packets through the interconnect fabric eliminates internal path conflicts. Features of the architecture include the guarantee of first-in-first-out packet sequence, broadcast and multicast capabilities, and compatibility with variable-length packets, which avoids the need for packet-size standardization. As a broadband ISDN example, a 2048×2048 configuration with building blocks of 42×16 packet switch modules and 128×128 interconnect modules, both of which fall within existing hardware capabilities, is presented     

Generalized quality-of-service routing with resource allocation

We present a general framework for the problem of quality-of-service (QoS) routing with resource allocation for data networks. The framework represents the QoS parameters as functions rather than static metrics. The formulation incorporates the hardware/software implementation and its relation to the allocated resources into a single framework. The proposed formulation allows intelligent adaptation of QoS parameters and allocated resources during a path search, rather than decoupling the path search process from resource allocation. We present a dynamic programming algorithm that, under certain conditions, finds an optimal path between a source and destination node and computes the amount of resources needed at each node so that the end-to-end QoS requirements are satisfied. We present jitter and data droppage analyzes of various rate-based service disciplines and use the dynamic programming algorithm to solve the problem of QoS routing with resource allocation for networks that employ these service disciplines.     

Performance analysis of the ATM shuffleout switch under arbitrarynonuniform traffic patterns

Shuffleout is a blocking multistage asynchronous transfer mode (ATM) switch using shortest path routing with deflection, in which output queues are connected to all the stages. This paper describes a model for the performance evaluation of the shuffleout switch under arbitrary nonuniform traffic patterns. The analytical model that has been developed computes the load distribution on each interstage link by properly taking into account the switch inlet on which the packet has been received and the switch outlet the packet is addressing. Such a model allows the computation not only of the average load per stage but also its distribution over the different links belonging to the interstage pattern for each switch input/output pair. Different classes of nonuniform traffic patterns have been identified and for each of them the traffic performance of the switch is evaluated by thus emphasizing the evaluation of the network unfairness     

Sorting-based routing algorithms of a photonic ATM cell switch:HiPower

HiPower is a photonic ATM switch having a two-layered structure, consisting of an electrical control layer and an optical transport layer, realized by a detouring hypercube interconnection network structure. Four sorting-based routing algorithms suitable for high-speed hardware control of HiPower are proposed. They are evaluated by computer simulations in terms of delay and cell loss in the switch under uniform traffic distribution. The simulation results suggest that all four methods are acceptable in their traffic characteristics and that the DD method, in which the cell nearest to its destination is given the highest priority in routing, seems to be the most attractive from the hardware implementation viewpoint. It is also confirmed that subpriority sorting based on the number of detourings reduces the delay variance. Simulation results proving that the detouring hypercube network is a practical and powerful architecture for a two-layered ATM cell switch, thus, the HiPower providing high throughput, are given     

Design and performance of Multinet switch: a multistage ATM switcharchitecture with partially shared buffers

A new ATM switch architecture is presented. Our proposed Multinet switch is a self-routing multistage switch with partially shared internal buffers capable of achieving 100% throughput under uniform traffic. Although it provides incoming ATM cells with multiple paths, the cell sequence is maintained throughout the switch fabric thus eliminating the out-of-order cell sequence problem. Cells contending for the same output addresses are buffered internally according to a partially shared queueing discipline. In a partially shared queueing scheme, buffers are partially shared to accommodate bursty traffic and to limit the performance degradation that may occur in a completely shared system where a small number of calls may hog the entire buffer space unfairly. Although the hardware complexity in terms of number of crosspoints is similar to that of input queueing switches, the Multinet switch has throughput and delay performance similar to output queueing switches     

SXmin: a self-routing high-performance ATM packet switch based ongroup-knockout principle

We propose SXmin: a self-routing, group-knockout principle based asynchronous transfer mode (ATM) packet switch which provides comparable delay-throughput performance and packet loss probabilities at significantly reduced hardware requirements compared to earlier switches. The M×N SXmin consists of an N×N Batcher sorter followed by log₂N-1 stages of sort-expander (SX) modules arranged in the form of a complete binary tree. Each SX module consists of a column of 2×2 switches with a wraparound-unshuffle input-output interconnection. This enables the hierarchical utilization of the group-knockout principle to expand the number of inputs by a small factor at each stage, resulting in a significant reduction in overall hardware complexity. Routing at each switch is controlled by a single bit. However, in case of contention, a dual bit resolution algorithm is used locally which drops excess packets in a predetermined manner while ensuring global randomness of packet loss over the entire switching network. There are no internal buffers at the individual stages and therefore the internal delay is constant and proportional to the number of stages. The use of simple hardware components and regular interconnections in the SX modules makes the network suitable for optical implementation     

Reducing cell loss in banyan based ATM switching fabrics

In this paper, we propose a new technique for reducing cell loss in multi‐banyan‐based ATM switching fabrics. We propose a switch architecture that uses incremental path reservation based on previously established connections. Path reservation is carried out sequentially within each banyan but multiple banyan planes can be concurrently reserved. We use a conflict resolution approach according to which banyans make concurrent reservation offers of conflict‐free paths to head of the line cells waiting in input buffers. A reservation offer from a given banyan is allocated to the cell whose source‐to‐destination path uses the largest number of partially allocated switching elements which are shared with previously reserved paths. Paths are incrementally clustered within each banyan. This approach leaves the largest number of free switching elements for subsequent reservations which has the effect of reducing the potential of future conflicts and improves throughput. We present a pipelined switch architecture based on the above concept of path‐clustering which we call path‐clustering banyan switching fabric (PCBSF). An efficient hardware that implements PCBSF is presented together with its theoretical basis. The performance and robustness of PCBSF are evaluated under simulated uniform traffic and ATM traffic. We also compare the cell loss rate of PCBSF to that of other pipelined banyan switches by varying the switch size, input buffer size, and traffic pattern. Copyright © 2001 John Wiley & Sons, Ltd.     

Hardware implementation of fair queuing algorithms for asynchronoustransfer mode networks

Providing quality-of-service guarantees in both cell- and packet-based networks requires the use of a scheduling algorithm in the switches and network interfaces. These algorithms need to be implemented in hardware in a high-speed switch. The authors present a number of approaches to implement scheduling algorithms in hardware. They begin by presenting a general methodology for the design of timestamp-based fair queuing algorithms that provide the same bounds on end-to-end delay and fairness as those of weighted fair queuing, yet have efficient hardware implementations. Based on this general methodology, the authors describe two specific algorithms, frame-based fair queuing and starting potential-based fair queuing, and discuss illustrative implementations in hardware. These algorithms may be used in both cell switches and packet switches with variable-size packets. A methodology for combining a traffic shaper with this class of fair queuing schedulers is also presented for use in network interface devices, such as an ATM segmentation and reassembly device