Parallel routing algorithms in Benes-Clos networks

A new parallel algorithm for route assignments in Benes-Clos (1962, 1953) networks is studied. Most known sequential route assignment algorithms, such as the looping algorithm, are designed for circuit switching systems where the switching configuration can be rearranged at relatively low speed. In packet switching systems, switch fabrics must be able to provide internally conflict-free paths simultaneously, and accommodate packets requesting connections in real time as they arrive at the inputs. In this paper, we develop a parallel routing algorithm for Benes networks by solving a set of Boolean equations which are derived from the connection requests and the symmetric structure of the networks. Our approach can handle partial permutations easily. The time complexity of our algorithm is O(log/sup 2/ N), where N is the network size. We also extend the algorithm and show that it can be applied to the Clos networks if the number of central modules is M=2/sup m/, where m is a positive integer. The time complexity is O(log N/spl times/log M) in this case.     

FMAC: a highly flexible multiple-access protocol for wirelesscommunications systems

Due to the limited bandwidth of wireless networks, an efficient medium-access control protocol is essential to meet the growing demand of wireless access. Most multiple-access protocols require contentions (collisions) in the process of acquiring the transmission medium. While collisions cannot be avoided, successive collisions that consist of the same group of active stations are totally unnecessary. Successive collisions not only waste bandwidth, but also raise the concern of saturation in the channel. In this paper, we solve the problem of repetitive contentions involving the same set of stations by using the theory of finite projective planes. Due to the property of single-point intersection for an arbitrary pair of sets in the finite projective plane, we can minimize the number of unnecessary collisions. Protocol finite projective plane-based medium access control (FMAC) is highly flexible and has many features including adaptation for a mobile environment, support for priority assignment and handoffs in cellular networks, and extension of asynchronous transfer mode (ATM) services to mobile users. A performance evaluation shows that the throughput of the system is higher than that of slotted ALOHA. By dynamically adjusting the retransmission probability and the order of the finite projective plane, protocol FMAC can be stabilized     

INQIRE: a software approach to monitoring QoS in ATM networks

Unlike traditional best-effort packet networks, ATM networks support a wide range of services by providing a specified QoS on each ATM connection. Currently, QoS can be measured with specialized high-speed testing equipment but their complexity and cost prevent them from wide field use. This article describes the INQIRE project approach based on software for enabling common personal computers (with an ATM network interface card) to function as QoS monitoring stations at the edges of an ATM network. The main objective is to develop a low-cost, off-the-shelf alternative to broadband testing equipment. An INQIRE station, consisting of a PC running the INQIRE application, can actively probe any selected connection and collect sample measurements of the QoS. The monitoring approach is intended to be non-intrusive and work with any ATM network without requiring any modifications to existing ATM switch equipment or interruptions to active services     

A time optimal wavelength rerouting algorithm for dynamic trafficin WDM networks

In this paper, we consider wavelength rerouting in wavelength routed wavelength division multiplexed (WDM) networks with circuit switching, wherein lightpaths between source-destination pairs are dynamically established and released in response to a random pattern of arriving connection requests and connection holding times. The wavelength continuity constraint imposed by WDM networks leads to poor blocking performance. Wavelength rerouting is a viable and cost effective mechanism that ran improve the blocking performance by rearranging certain existing lightpaths to accommodate a new request. Recently, a rerouting scheme called “parallel move-to-vacant wavelength retuning (MTV-WR)” with many attractive features such as shorter disruption period and simple switching control, and a polynomial time rerouting algorithm, for this scheme, to minimize the weighted number of rerouted lightpaths have been proposed. This paper presents a time optimal rerouting algorithm for wavelength-routed WDM networks with parallel MTV-WR rerouting scheme. The algorithm requires only O(N²W) time units to minimize the weighted number of existing lightpaths to be rerouted, where N is the number of nodes in the network and W is the number of wavelength channels available on a fiber link. Our algorithm is an improvement over the earlier algorithm proposed in that it requires O(N³W+N²W²) time units, which is not time optimal. The simulation results show that our algorithm improves the blocking performance considerably and only very few lightpaths are required to be rerouted per rerouting. It is also established through simulation that our algorithm is faster than the earlier rerouting algorithm by measuring the time required for processing connection requests for different networks     

Survey of switching techniques in high-speed networks and their performance

One of the most promising approaches for high speed networks for integrated service applications is fast packet switching, or ATM (asynchronous transfer mode). ATM can be characterized by very high speed transmission links and simple, hard-wired protocols within a network. To match the transmission speed of the network links, and to minimize the overhead due to the processing of network protocols, the switching of cells is done in hardware switching fabrics in ATM networks. A number of designs have been proposed for implementing ATM switches. Although many differences exist among the proposals, the vast majority of them are based on self-routeing multistage interconnection networks. This is because of the desirable features of multi-stage interconnection networks such as self-routeing capability and suitability for VLSI implementation. Existing ATM switch architectures can be classified into two major classes: blocking switches, where blockings of cells may occur within a switch when more than one cell contends for the same internal link, and non-blocking switches, where no internal blocking occurs. A large number of techniques have also been proposed to improve the performance of blocking and non-blocking switches. In this paper, we present an extensive survey of the existing proposals for ATM switch architectures, focusing on their performance issues.     

Design of a non-blocking shared-memory copy network for ATM

The design of a copy network is presented for use in an ATM (asynchronous transfer mode) switch supporting BISDN (broadband integrated services digital network) traffic. Inherent traffic characteristics of BISDN services require ATM switches to handle bursty traffic with multicast connections. In typical ATM switch designs a copy network is used to replicate multicast cells before being forwarded to a point-to-point routeing network. In such designs, a single multicast cell enters the switch and is replicated once for each multicast connection. Each copy is forwarded to the routeing network with a unique destination address and is routed to the appropriate output port. Non-blocking copy networks permit multiple cells to be multicasted at once, up to the number of outputs of the copy network. Another critical feature of ATM switch design is the location of buffers for the temporary storage of transmitted cells. Buffering is required when multiple cells require a common switch resource for transmission. Typically, one cell is granted the resource and is transmitted while the remaining cells are buffered. Current switch designs associate discrete buffers with individual switch resources. Discrete buffering is not efficient for bursty traffic as traffic bursts can overflow individual switch buffers and result in dropped cells, while other buffers are under-used. A new non-blocking copy network is presented in this paper with a shared-memory input buffer. Blocked cells from any switch input are stored in a single shared input buffer. The copy network consists of three banyan networks and shared-memory queues. The design is scalable for large numbers of inputs due to low hardware complexity, O (N log₂ N), and distributed operation and control. It is shown in a simulation study that a switch incorporating the shared-memory copy network has increased throughput and lower buffer requirements to maintain low packet loss probability when compared to a switch with a discrete buffer copy network.     

Evaluation of pipelined dilated banyan switch architectures for ATMnetworks

In the pipeline banyan (PB), the reservation cycle in the control plane is made several times faster than payload transmission in data plane. This enables pipelining multiple banyans. It is observed that the ratio of throughput to switching delay (service rate) is relatively low in the PB due to the banyan. For this, we present a scalable pipelined asynchronous transfer mode (ATM) switch architecture employing a family of dilated banyan (DB) networks together with their complexity analysis and performance. A DB can be engineered between two extremes: (1) a low-cost banyan with internal and external conflicts, or (2) a high-cost conflict-free fully connected network with multiple outlets. Between the two extremes lies a family of DBs having different switching delays and throughputs. Increasing the dilation degree reduces path conflicts, which produces noticeable increase in service rate due to increase in throughput and decrease in path delay. Compared to PB, the pipelined dilated banyan (PDB) requires smaller number of data planes for the same throughput, or provides higher throughput for a given number of data planes. Simulation of PDB is carded out under uniform traffic and simulated ATM traffic. We study the switch performance while varying the load, buffer size, and number of data planes. To analyze the robustness of the switch, we show that performance is not degradable under ATM traffic with temporal and spatial burstiness generated using the on-off model. The PDB is scalable with respect to service rate and can be engineered with respect to: (1) cell loss rate; (2) hardware resources; (3) size of buffers; (4) switching delays; and (5) delay incurred to higher priority traffic. The PDB can deliver up to 3.5 times the service rate of the PB with only linear increase in hardware cost     

A new charging scheme for ATM based on QoS

This paper describes a new approach to charging for ATM called the ‘quality of service (QoS)‐based charging scheme’. In this scheme, traffic resources are distributed among buffers established to support combinations of ATM transfer capabilities and qualities of service. The buffers are dimensioned according to M/D/1/K and ND/D/1 queuing analysis to determine the buffer efficiency and quality of service requirements. This dimensioning provides the basis for fixing the price per unit of resource and time. The actual resource used by a connection is based on the volume of cells transmitted or peak cell rate allocation in combination with traffic shapers if appropriate. Shapers are also dimensioned using the quality of service parameters. Since the buffer efficiency is dependent on the quality of service requirements, customers of ATM networks buy quality of service. The actual price of a connection is also related to the amount of the resource purchased as well as the time of the day at which a connection is made, and the geographical location of the destination switch. The QoS‐based charging scheme meets the requirements of customers and of network operators. Its performance compares very favourably with that of a number of well‐known existing ATM charging schemes. Copyright © 2002 John Wiley & Sons, Ltd.     

SDRAM: a SD channel-based multicast scheme on ATM networks for multimedia transmissions

Multicast delivery has become more and more important in modern multimedia applications. VoD and videoconferences are two examples. Multimedia integrates texts, audios, videos and still images in a variety of applications. The data in this media can be time critical in terms of maximum delay and delay jitter. In order to satisfy all these applications, the network needs to have an efficient multicasting mechanism using the true capability of ATM networks. In the native solution, a separate connection can be set up from the source to each group node, also called full connectivity. The full connectivity needs O(N/sup 2/) connections, where N is the number of nodes in a group. Instead, we can have one tree spanning all the participants. Multicast using a single shared tree has become the trend. In this paper, we propose a bi-directional multipoint-to-multipoint multicast scheme, a SD channel-based Multicast with Round-robin Access (SDRAM), for ATM networks, which uses a single tree for a multicast group consisting of multiple participants that are either senders, receivers, or a mix of both. We first discuss why the resequencer model will not be suitable for multimedia traffic, then propose the SDRAM scheme to solve the problems, and finally compare our scheme with the resequencer model through simulation. Results show the mean queuing delays and mean inter-PDU delays of our scheme are not sensitive to mean PDU size while the mean queuing delays and mean inter-PDU delays of the resequencer scheme are very sensitive to mean PDU size.     

Blocking and nonblocking multirate Clos switching networks

This paper investigates in detail the blocking and nonblocking behavior of multirate Clos switching networks at the connection/virtual connection level. The results are applicable to multirate circuit and fast-packet switching systems. Necessary and sufficient nonblocking conditions are derived analytically. Based on the results, an optimal bandwidth partitioning scheme is proposed to reduce switch complexity while maintaining the nonblocking property. The blocking behavior of blocking switches supporting multicast connections is investigated by means of simulation. We propose a novel simulation model that filters out external blocking events without distorting the bandwidth and fanout (for multicasting) distributions of connection requests. In this way, the internal blocking statistics that truly reflect the switch performance can be gathered and studied. Among many simulation results, we have shown that for point-to-multipoint connections, a heuristic routing policy that attempts to build a narrow multicast tree can have relatively low blocking probabilities compared with other routing policies. In addition, when small blocking probability can be tolerated, our results indicate that situations with many large-fanout connection requests do not necessarily require a switch architecture of higher complexity compared to that with only point-to-point requests     

Optical crossconnects of reduced complexity for WDM networks withbidirectional symmetry

One promising approach to provisioning and restoration in long-haul wavelength-division-multiplexing (WDM) networks is to deploy a mesh of optical crossconnects that operate on individual wavelengths. As wavelength-count and traffic demand rapidly increase, however, this approach will likely require high-port-count optical crossconnects that severely strain the capabilities of known device technologies. Thus, it is critical to devise ways to build large crossconnects from a small number of constituent switches, each with reduced port count. We present a general means of accomplishing this for networks, such as current long-haul networks, that demonstrate bidirectional symmetry. We describe a broad class of symmetry-exploiting architectures that yield N×N crossconnects, both rearrangeably nonblocking and strictly nonblocking, using constituent switch fabrics no larger than N/2×N/2. By exploiting connection-symmetry, these architectures reduce the number of such N/2×N/2 fabrics by 30%-50% compared with corresponding fully connected three-stage Benes and Clos switch structures     

The Effects of Management Traffic on the Local Call Processing Performance of ATM Switches Using Queue Network Models and Jackson's Theorem

This paper considers a TMN‐based management system for the management of public ATM switching networks using a four‐level hierarchical structure consisting of one network management system, several element management systems, and several agent‐ATM switch pairs. Using Jackson's queuing model, we analyze the effects of one TMN command on the performance of the component ATM switch in processing local calls. The TMN command considered is the permanent virtual call connection. We analyze four performance measures of ATM switches—utilization, mean queue length and mean waiting time for the processor directly interfacing with the subscriber lines and trunks, and the call setup delay of the ATM switch—and compare the results with those from Jackson's queuing model.     

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     

The bypass queue in fast packet switching

The telecommunications networks of the future are likely to be packet switched networks consisting of wide bandwidth optical fiber transmission media, and large, highly parallel, self-routing switches. Recent considerations of switch architectures have focused on internally nonblocking networks with packet buffering at the switch outputs. These have optimal throughput and delay performance. The author considers a switch architecture consisting of parallel plans of low-speed internally blocking switch networks, in conjunction with input and output buffering. This architecture is desirable from the viewpoint of modularity and hardware cost, especially for large switches. Although this architecture is suboptimal, the throughput shortfall may be overcome by adding extra switch planes. A form of input queuing called bypass queuing can improve the throughput of the switch and thereby reduce the number of switch planes required. An input port controller is described which distributes packets to all switch planes according to the bypass policy, while preserving packet order for virtual circuits. Some simulation results for switch throughput are presented     

A 100-Gb/s throughput ATM switch MCM with a 320-channel paralleloptical I/O interface

For an ATM switch system, we have developed a 100-Gb/s input/output (I/O) throughput optical I/O interface ATM switch multichip module (MCM) that has 320-ch optical I/O ports. This MCM is fabricated using ceramic (MCM-C) technology and very-small highly-parallel O/E and E/O optical converters. It uses 0.25-μm complementary metal oxide semiconductors (CMOS) ATM switch large scale integrations (LSIs) and has a total I/O throughput of up to 160 Gb/s. A prototype module with total I/O throughput of 100 Gb/s has been partially assembled using eight optical I/O interface blocks, each composed of a 40-ch O/E converter and a 40-ch E/O converter; the data rate per channel is from dc to 700 Mb/s. Using this module we developed an optical I/O interface ATM switch system and confirmed the operation of the optical interface     

SYN‐Guard: An effective counter for SYN flooding attack in software‐defined networking

In software‐defined networking (SDN), TCP SYN flooding attack is considered as one of the most effective attacks to perform control plane and target server saturation. In this attack, an attacker generates a large number of malicious SYN requests, and because of the absence of the forwarding rules, the data plane switches have to forward these SYN messages to the controller. This excessive forwarding causes congestion over the communication channel between a data plane and control plane, and it also exhausts computational resources at both the planes. In this paper, we propose a novel countermeasure called SYN‐Guard to detect and prevent SYN flooding in SDN networks. We fully implement SYN‐Guard on the SDN controller to validate the incoming TCP connection requests. The controller installs forwarding rules for the SYN requests that successfully clear the validation test of SYN‐Guard. The host of the fake SYN request is detected, and SYN‐Guard prevents it from sending any further SYN requests to the data plane switch. The performance evaluation done using the simulation results shows that SYN‐Guard exhibits low side effect for genuine TCP requests, and when compared with standard SDN and state‐of‐art proposals, it reduces the average response time up to 21% during an ongoing SYN flooding attack.     

An evolvable ATM-based video network design supporting multipleaccess network technologies

This article describes an overall video network architecture with primary focus on the ATM subnetwork. The ATM subnetwork provides efficient switching capability for providing constant bit rate and variable bit rate video communication services. The ATM subnetwork can support multiple access networks like hybrid fiber coax (HFC), asymmetric digital subscriber line (ADSL), and fiber to the curb (FTTC). A broadband network controller is presented as the external controller for the ATM subnetwork which performs the functions of the session/network manager and the ATM-based connection management. The initial deployment of video is likely to be permanent virtual connection (PVC)-based, so a dynamic PVC-based scenario is described. The ATM switch architecture presented here has been optimized to support video applications. An evolution to the switched virtual connection environment and support of multiple services over the ATM subnetwork is also addressed. Traffic management schemes are discussed which provide the negotiated quality of service to the connections     

Connection Admission Control in ATM Networks Based on the Foreground and Background Neural Networks

ＣｏｎｎｅｃｔｉｏｎＡｄｍｉｓｓｉｏｎＣｏｎｔｒｏｌｉｎＡＴＭＮｅｔｗｏｒｋｓＢａｓｅｄｏｎｔｈｅＦｏｒｅｇｒｏｕｎｄａｎｄＢａｃｋｇｒｏｕｎｄＮｅｕｒａｌＮｅｔｗｏｒｋｓ￥ＭａＸｕｄｏｎｇ；ＬｕｅｅＴｉｎｇｊｉｅａｎｄＬｉａｎｇＸｉｏｎｇｊｉａｎ（...     

PERFORMANCE ANALYSIS OF A PARALLEL BANYAN ATM SWITCH

Asynchronous transfer mode (ATM) switches can be constructed by connecting multiple banyan networks in parallel. To utilize the capacity of the parallel banyan networks fully, it is crucial to allow up to L cells from each input to be switched, and up to L cells to be received by each output simultaneously, where L is the total number of parallel banyan networks. This is possible if the switch operates in L overlapping phases and one banyan network is used to switch cells in each phase. Although a couple of such designs have been proposed and simulated, there is a lack of suitable models for such switches to be analysed mathematically. In this paper, two approximate analyses of a parallel banyan ATM switch are described. A comparison of the analytical and simulation results show that the analyses give reasonably accurate results. © 1997 by John Wiley & Sons, Ltd.     

Functionality at the edge: designing scalable multiservice ATMnetworks

ATM offers the capability of consolidating multiple services onto a common backbone network, thereby reducing network management complexity, improving utilization, and lowering cost. As ATM networks grow, a virtual path connection (VPC) network core is often provisioned to reduce the number of connections to provide scalability for network management and performance. Provisioning a VPC network core raises a number of issues, especially related to the performance of bursty non-real-time connections. This article discusses these issues and how the functionality of ATM can best address them. It is shown that employing low-loss flow-controlled ABR VPCs to carry non-real-time traffic can provide significant gains in terms of performance as well as improved throughput for a given amount of buffering in the network core. The flow-controlled VPC enables the complexities of virtual channel connection- (VCC)-level congestion control, fairness, and isolation to be pushed to the network edge where lower speeds allow this functionality to be performed more cost effectively