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     

The Tera project: a hybrid queueing ATM switch architecture for LAN

The Tera ATM LAN project at Carnegie Mellon University addresses the interconnection of hundreds of workstations in the Electrical and Computer Engineering Department via an ATM-based network. The Tera network architecture consists of switched Ethernet clusters that are interconnected using an ATM network. This paper presents the Tera network architecture, including an Ethernet/ATM network interface, the Tera ATM switch, and its performance analysis. The Tera switch architecture for asynchronous transfer mode (ATM) local area networks (LAN's) incorporates a scalable nonblocking switching element with hybrid queueing discipline. The hybrid queueing strategy includes a global first-in first-out (FIFO) queue that is shared by all switch inputs and dedicated output queues with small speedup. Due to hybrid queueing, switch performance is comparable to output queueing switches. The shared input queue design is scalable since it is based on a Banyan network and N FIFO memories. The Tera switch incorporates an optimal throughput multicast stage that is also based on a Banyan network. Switch performance is evaluated using queueing analysis and simulation under various traffic patterns     

Omega network-based ATM switch with neural network-controlledbypass queueing and multiplexing

Multistage interconnection networks (MINs) have long been studied for use in switching networks. Since they have a unique path between source and destination and the intermediate nodes of the paths are shared, internal blocking can cause very poor throughput. This paper proposes a high throughput ATM switch consisting of an Omega network with a new form of input queues called bypass queues. We also improve the switch throughput by partitioning the Input buffers into disjoint buffer sets and multiplexing several sets of nonblocking cells within a time slot, assuming that the routing switch operates only a couple of times faster than the transmission rate. A neural network model is presented as a controller for cell scheduling and multiplexing in the switch. Our simulation results under uniform traffic show that the proposed approach achieves almost 100% of potential switch throughput     

PR-banyan: a packet switch with a pseudorandomizer for nonuniformtraffic

Buffered banyan networks are highly vulnerable to nonuniform traffic, due to the path sharing as well as the existence of only a single path per network input-output pair. Improving on an earlier packet distribution network which is a banyan network itself, a single-stage packet-scattering hardware, called the pseudo-randomizer (PR), is proposed. The PR-banyan, the PR followed by a buffered banyan, is analyzed under nonuniform traffic, and is shown to be highly effective under nonuniform traffic. The analytic results are shown to match the simulation results very closely     

The deflection self-routing Banyan network: A large-scale ATMswitch using the fully adaptive self-routing and its performanceanalyses

Because the Internet traffic, that will be the major traffic of broadband integrated services digital networks, is bursty when cells are being switched within the multistage switching network, it has a higher possibility that multiple cells arriving simultaneously at a switching element through different incoming links may have to be forwarded along the same outgoing link. We propose a high-performance large-scale ATM switch dealing with such link contention problem. It is a new unbuffered augmented Banyan network using fully adaptive self-routing control: the deflection self-routing Banyan network. To utilize all the links of the network as alternate paths, we employ the deflection-routing algorithm in each switching element, such that cells failing to get selected for the intended link are sent along different links, in the hope that they later return, or detour the contended link and continue their journey to the destination. Cells are never dropped within the switching network, whereas the switch has no multiple cell buffers. The proposed routing is as simple as that of the generic Banyan network, and all the switch elements (SEs) have a uniform structure. To design the proposed network and its self-routing, we use the topological properties that all the SEs of the Banyan network are arranged in a regular pattern topologically. We formulate and prove these properties through an algebraic formalism. We also ran a performance analysis to provide quantitative comparison against the Banyan network and the replicated Banyan networks. As a result, we show that the new network has a far better performance and scalability than the other networks     

The knockout switch under nonuniform traffic

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     

Dimensioning an ATM switch based on a three-stage Clos interconnection network

ATM (asynchronous transfer mode) is a new technique for transmitting voice, data and video. The performance of atm networks will depend on switch structure. Performance analysis of an atm switch based on a three-stage Clos network is presented. In this paper two types of switches are studied: a switch with input queues in the switching elements and a switch with output queues. This study is at the cell level and intends to dimension the switch. First, the traffic is supposed to be uniform, cells arrive on each input according to a geometric arrival process, they are uniformly directed over all the network outputs. An analytic model is proposed for both input and output queues in the switching elements. A study of the saturation throughput is proposed for input buffer switching elements. This work proves the influence of buffer dimensioning on the different stages of the switch. Dissymmetric switching elements are shown to be better than symmetric ones. A model is then designed for nonuniform traffic patterns and output buffers. Two types of non-uniform traffic are presented: single source to single destination (sssd) and multi-hot spots traffic (mhs). Discrete event simulations are used to validate the different models.     

Rerouting network: a high-performance self-routing switch forB-ISDN

A high-performance self-routing switch is proposed for ATM (asynchronous transfer mode) switch systems. Switching performance is enhanced by a rerouting algorithm applied to a particular multistage interconnection algorithm. The interconnection algorithm offers many access points to the output and resolves output contention by layering buffers at each switching stage. The author analyzes switching performance and shows that this switch can be easily engineered to have high throughput and low cell loss probability by increasing the number of switching stages. The author also illustrates that the number of switching stages required for a given cell loss probability shows gradual growth with increasing switch size. Analysis shows that the proposed switch is robust even with respect to nonuniform traffic     

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     

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     

Wrap-around type switch for ATM

Proposes a new wrap-around type switch structure based on omega networks. Their uniform interconnection pattern and symmetrical structure helps design a so-called wrap-around switch, The new switch deploys a self-routing mechanism between the input and the output ports. Another characteristic of the switch is the packet filters which are located right in front of the switch elements (SEs). This filtering operation greatly reduces the traffic in the switch fabric by allowing the incoming cells to reach their destination ports without going further in the network     

DIRSMIN: a fault-tolerant switch for B-ISDN applications usingdilated reduced-stage MIN

We have developed and analyzed a dilated high-performance fault-tolerant fast packet multistage interconnection network (MIN). This new switch, (d,d')-DIRSMIN, uses dilation to improve performance and fault-tolerance of a network. The links at the input and output stages of the dilated banyan-based MIN are rearranged to create multiple routes for each source-destination pair in the network, after removing the first stage in the network. These multiple paths are link- and node-disjoint. This new MIN can provide low packet-loss probability and high reliability with very little hardware overhead, compared to d-dilated banyan networks (BN). Fault tolerance at low latency is achieved by transmitting multiple copies of each input-packet simultaneously using different routes. A multiple-priority scheme allows alternate paths to be explored simultaneously, which results in higher throughput and reliability under both fault-free and faulty conditions. This guarantees that high throughput is maintained even in the presence of a fault. Throughput is analyzed using analytic and simulation methods; this new design has considerably higher performance in the presence of a permanent faulty switching-element (SE) or link, in comparison to dilated networks. Under non-faulty conditions, both analytic and simulation results show that a (d,d)-DIRSMIN performs better than the original dilated BN with the same SE complexity. We analyze the network reliability and show that the new design has superior reliability compared to competing proposals. In particular, this new design is considerably better than the SEN+, the best known thus far     

Enhanced hop-limited handoff scheme for linear broadband cellularnetworks

An enhanced handoff scheme for ATM-based cellular networks in linear environments is proposed. Some regularly spaced cells are assigned as rerouting cells. If a handoff call comes to a rerouting cell, its traffic path is rerouted to a PVC between the cell and the ATM switch. If a handoff call comes to an ordinary cell, its traffic path is simply elongated by a PVC between the new cell and its previous cell. The path efficiency is improved     

A buffer management scheme for the SCOQ switch under nonuniformtraffic loading

The SCOQ switch is a Batcher-banyan based high performance fast packet switch with shared concentration and output queueing, with a maximum of L(相似文献   

Performances of the Data Vortex switch architecture under nonuniform and bursty traffic

The Data Vortex switch architecture has been proposed as a scalable low-latency interconnection fabric for optical packet switches. This self-routed hierarchical architecture employs synchronous timing and distributed traffic-control signaling to eliminate optical buffering and to reduce the required routing logic, greatly facilitating a photonic implementation. In previous work, we have shown the efficient scalability of the architecture under uniform and random traffic conditions while maintaining high throughput and low-latency performance. This paper reports on the performance of the Data Vortex architecture under nonuniform and bursty traffic conditions. The results show that the switch architecture performs well under modest nonuniform traffic, but an excessive degree of nonuniformity will severely limit the scalability. As long as a modest degree of asymmetry between the number of input and output ports is provided, the Data Vortex switch is shown to handle very bursty traffic with little performance degradation.     

A high-performance switch fabric for integrated circuit and packet switching

This paper describes an architecture for a high-performance switching fabric that can accommodate circuit-switched and packet-switched traffic in a unified manner. The switch fabric is self-routeing and uses fixed-length minipackets within the switching fabric for all types of connections. Its kernel architecture is based on a routeing topology with individual connection paths from all inputs to all outputs and with FIFO queuing at each output. Owing to the disjoint connection paths, there is no internal blocking, and because of output queueing, output port blocking is prevented to a great extent. The uniformity in architecture allows construction of any size fabric from a single basic module which could be realized on a single chip. Larger-size configurations can be realized either as single-stage or multistage configuration. The second part of this paper discusses performance aspects and gives results and dimensioning guidelines for both circuit-switched and packet-switched traffic.     

A fast packet switch for the integrated services backbone network

With the projected growth in demand for bandwidth and telecommunication services will come the requirement for a multiservice backbone network of far greater efficiency, capacity, and flexibility than ISDN (integrated-services digital network) is able to satisfy. This class of network has been termed the broadband ISDN, and the design of the switching nodes of such a network is the subject of much research. The author investigates one possible solution. The design and performance, for multiservice traffic, is presented for a fast packet switch based on a nonbuffered, multistage interconnection network. It is shown that for an implementation in current CMOS technology, operating at 50 MHz, switches with a total traffic capacity of up to 150 Gb/s can be constructed. Furthermore, if the reserved service traffic load is limited on each input port to a maximum of 80% of switch port saturation, then a maximum delay across the switch of on the order of 100 μs can be guaranteed, for 99% of the reserved service traffic, regardless of the unreserved service traffic load     

An efficient algorithm for the link allocation problem on ATM-basedpersonal communication networks

The personal communication network (PCN) is an emerging wireless network that promises many new services for the telecommunication industry. The proliferation of demands for extending wireless services to integrated services which supports the transmission of data and multimedia information has resulted in the need for broadband wireless systems that are able to provide service capabilities similar to those of wireline networks. The ATM cell-relay paradigm is one possible approach to provide broadband wireless transmission with PCNs using the ATM switching networks for interconnection of PCN cells. In an ATM-based PCN, the communication path between a pair of mobile terminals might be elongated due to the mobility of the terminals. The link allocation problem is that of allocating backbone links among ATM switches to reduce the effects of terminal mobility on the performance of ATM-based PCNs. Huang and Wang (1997) have shown that this problem is NP-complete. In this paper, we propose a new efficient heuristic algorithm for the link allocation problem. One novel feature of our algorithm is that we are able to derive sufficient conditions under which our algorithm is able to guarantee optimal solutions. Our empirical study shows that the average lengths of communication paths obtained by our algorithm are shorter than those obtained by Huang and Wang's algorithm. In addition, the number of successfully established paths obtained by our algorithm is significantly more than that obtained by the aforementioned     

基于ATM的MPLS流量工程研究

研究了基于ATM的MPLS,重点研究和分析了具体实现MPLS流量工程的ATM流控措施、使用约束路由的标记分发协议、路由协议,为MPLS流量工程的具体实施提供了参考。同时研究了MPLS多协议标记交换技术融合IP路由技术、ATM的QoS（Quality of Service）及交换技术,使得流量工程模式可以部署在基于IP的网络,其中包括ATM网上承载IP业务的模式。     

A fast parallel-tree switch architecture for ATM networks

In this paper we present a novel fast packet switch architecture based on Banyan interconnection networks, called parallel-tree Banyan switch fabric (PTBSF). It consists of parallel Banyans (multiple outlets) arranged in a tree topology. The packets enter at the topmost Banyan. Internal conflicts are eliminated by using a conflict-free 3 × 4 switching element which distributes conflicting cells over different Banyans. Thus, cell loss may occur only at the lowest Banyan. Increasing the number of Banyans leads to a noticeable decrease in cell loss rate. The switch can be engineered to provide arbitrarily high throughput and low cell loss rate without the use of input buffering or cell pre-processing. The performance of the switch is evaluated analytically under uniform traffic load and by simulation, under a variety of asynchronous transfer mode (ATM) traffic loads. Compared to other proposed architectures, the switch exhibited stable and excellent performance with respect to cell loss and switching delay for all studied conditions as required by ATM traffic sources. The advantages of PTBSF are modularity, regularity, self-routing, low processing overhead, high throughput and robustness, under a variety of ATM traffic conditions. © 1998 John Wiley & Sons, Ltd.