Input polling arbitration mechanism for a gigabit packet switch

Two head of line (HOL) packet arbitration mechanisms in an input buffered gigabit packet switch are proposed. These mechanisms have significant advantages in simple implementation while their performances still remain at acceptable levels     

Output-queued switch emulation by fabrics with limited memory

The output-queued (OQ) switch is often considered an ideal packet switching architecture for providing quality-of-service guarantees. Unfortunately, the high-speed memory requirements of the OQ switch prevent its use for large-scale devices. A previous result indicates that a crossbar switch fabric combined with lower speed input and output memory and two times speedup can exactly emulate an OQ switch; however, the complexity of the proposed centralized scheduling algorithms prevents scalability. This paper examines switch fabrics with limited memory and their ability to exactly emulate an OQ switch. The switch architecture of interest contains input queueing, fabric queueing, flow-control between the limited fabric buffers and the inputs, and output queueing. We present sufficient conditions that enable this combined input/fabric/output-queued switch with two times speedup to emulate a broad class of scheduling algorithms operating an OQ switch. Novel scheduling algorithms are then presented for the scalable buffered crossbar fabric. It is demonstrated that the addition of a small amount of memory at the crosspoints allows for distributed scheduling and significantly reduces scheduling complexity when compared with the memoryless crossbar fabric. We argue that a buffered crossbar system performing OQ switch emulation is feasible for OQ switch schedulers such as first-in-first-out, strict priority and earliest deadline first, and provides an attractive alternative to both crossbar switch fabrics and to the OQ switch architecture.     

Nonuniform traffic analysis on a nonblocking space-division packetswitch

The nonuniform traffic performance on a nonblocking space division packet switch is studied. When an output link is simultaneously contended by multiple input packets, only one can succeed, and the rest will be buffered in the queues associated with each input link. given the condition that the traffic on each output is not dominated by individual inputs, this study indicates that the output contention involved by packets at the head of input queues can be viewed as an independent phase-type process for a sufficiently large size of the switch. Therefore, each input queue can be modeled by an independent Geom/PH/1 queueing process. Once the relative input traffic intensities and their output address assignment functions are defined, a general formulation can be developed for the maximum throughput of the switch in saturation. The result indicates under what condition the input queue will saturate. A general solution technique for the evaluation of the queue length distribution is proposed. The numerical study based on this analysis agrees well with simulation results     

Queueing analysis of scheduling policies in copy networks ofspace-based multicast packet switches

Space-based multicast switches use copy networks to generate the copies requested by the input packets. In this paper our interest is in the multicast switch proposed by Lee (1988). The order in which the copy requests of the input ports are served is determined by the copy scheduling policy and this plays a major part in defining the performance characteristics of a multicast switch. In any slot, the sum of the number of copies requested by the active inputs of the copy network may exceed the number of output ports and some of the copy requests may need to be dropped or buffered. We first propose an exact model to calculate the overflow probabilities in an unbuffered Lee's copy network. Our exact results improve upon the Chernoff bounds on the overflow probability given by Lee by a factor of more than 10. Next, we consider buffered inputs and propose queueing models for the copy network for three scheduling policies: cyclic service of the input ports with and without fanout splitting of copy requests and acyclic service without fanout splitting. These queueing models obtain the average delay experienced by the copy requests. We also obtain the sustainable throughput of a copy network, the maximum load that can be applied to all the input ports without causing an unstable queue at any of the inputs, for the scheduling policies mentioned above     

New nodal design for high throughput data vortex optical interconnection network

This paper proposes a new three input nodal structure within the data vortex packet switched interconnection network. With additional optical switches, the modified architecture allows for two input packets in addition to a buffered packet to be processed simultaneously within a routing node. A much higher degree of parallel processing is allowed in comparison to previously proposed enhanced buffer node with two input processing or the original network node with single input processing. Unlike the previous contention prevention mechanism, the new network operates by introducing the packet blocking within the node if no exit path is available. This eliminates the traffic control signaling and the strict timing alignment associated with the routing paths which simplifies the overall network implementation. This study shows that both data throughput and the latency performance are improved significantly within the new network. The study compares the three input node with the two input node as well as the original single input data vortex node. Due to additional switch count and nodal cost, networks that support the same I/O ports and of the same cost are compared for a fair comparison. The limitation introduced by the blocking rate is also addressed. The study has shown that under reasonable traffic and network condition, the blocking rate can be kept very low without introducing complex controls and management for dropped packets. As previous architectures require operation under saturation point, the proposed architecture should also operate at reasonable level of network redundancy to avoid excessive packet drop. This study provides guidance and criteria on the proposed three input network design and operation for feasible applications. The proposed network provides an attractive alternative to the previous architectures for higher throughput and lower latency performance.     

Congestion control in interconnected LANs

The reasons why congestion control is more difficult in interconnected local area networks (LANs) than in conventional packet nets are examined. The flow and congestion control mechanisms that can be used in an interconnected LAN environment are reviewed. The focus is on congestion control (that is, prevention of internal congestion); however some of the proposed schemes require the interaction of flow and congestion control. The schemes considered are dropping packets; input buffer limit, i.e. a limit on the number of input packets (i.e. packets from local hosts) that can be buffered in the packet switch; the use of choke packets, in which, whenever a bridge or router experiences congestion, it returns to the source a choke packet containing the header of the packet traveling in the congested direction and the source, on receiving the choke packet, declares the destination congested, and slows (or stops altogether, for a period of time) traffic to that destination; backpressure, which is the regulation of flow along a virtual connection; and congestion prevention, whereby a voice or video connection is accepted only if there is enough bandwidth (in a statistical sense) in the network to support it     

Exhaustive Output Arbitration of Input Buffered Switch with Buffered Crossbar

We propose a new arbitration method for an input buffered switch with a buffered crossbar. In the proposed method, an exhaustive polling method is used to decrease the synchronization. Using an approximate analysis, we explain how the proposed method improves the switch performance. Also, using computer simulations, we show the proposed method outperforms the previous methods under burst traffic.     

Round-robin selection with adaptable-size frame in a combined input-crosspoint buffered switch

As an alternative to input-buffered switches, combined input-crosspoint buffered switches relax arbitration timing and provide high-performance switching for packet switches with high-speed ports. It has been shown that these switches, with one-cell crosspoint buffer and round-robin (RR) arbitration at input and output ports, provide 100% throughput under uniform traffic. However, under admissible traffic patterns with nonuniform distributions, only weight-based selection schemes are reported to provide high throughput. We propose an RR based arbitration scheme for a combined input-crosspoint buffered packet switch that provides nearly 100% throughput for several admissible traffic patterns, including uniform and unbalanced traffic, using one-cell crosspoint buffers. The presented scheme uses adaptable-size frames, so that the frame size adapts to the traffic pattern.     

SCOQ: a fast packet switch with shared concentration and outputqueueing

A space-division, nonblocking packet switch with data concentration and output buffering is proposed. The performance of the switch is evaluated with respect to packet loss probability, the first and second moments of the equilibrium queue length and waiting time, throughput, and buffer overflow probability. Numerical results indicate that the switch exhibits very good delay-throughput performance over a wide range of input traffic. The switch compares favorably with some previously proposed switches in terms of fewer basic building elements used to attain the same degree of output buffering     

FB-banyans and FB-delta networks: Fault-tolerant networks for broadband packet switching

Many fast packet switches for the broadband integrated services digital network (BISDN) in the literature are based on banyan networks. Although banyan networks possess nice properties such as a simple control and a low hardware cost, they are unique-path networks. Since there is a unique path from an input to an output in a banyan network, a single component failure may disrupt services of some nodes connected to such a network. Moreover, banyan networks are also blocking networks; packets can be lost within the networks. To reduce the packet loss, buffered banyan networks can be used. In an earlier work we have proposed the addition of backward links to otherwise unidirectional banyan networks to create B-banyans (and B-delta networks). Backward links not only function as implicit buffers for blocked packets, but also provide multiple paths for each input-output connection. However, the multiple paths in B-banyans may not be disjoint. In this paper, we enhance B-banyans and B-delta networks in such a way that the resulting networks can provide disjoint multiple paths for each input-output pair. The existence of disjoint multiple paths has a significant effect on the network fault-tolerance. The new networks, called FB-banyans and FB-delta networks, are k fault-tolerant, where k is the number of backward links per switch and is less than the switch size. They are also robust to more than k faults, depending on the locations of faults. The maximal fault-tolerance is achieved when k is the switch size minus 1. The performance of the new networks is analysed and compared to that of other networks of interest. FB-banyans and FB-delta networks can be used as a switch fabric for fast packet switches to provide performance comparable to that of buffered banyan networks and good fault tolerance.     

Performance evaluation of input and output queueing techniques inATM switching systems

Modeling alternatives for a fast packet switching system are analyzed. A nonblocking switch fabric that runs at the same speed as the input/output links is considered. The performance of the considered approaches are derived by theoretical analysis and computer simulations. Performance comparison between input queueing approaches with different selection policies are presented. Novel input and output queueing techniques are also proposed. In particular it is shown that, depending on the implementation, the input queueing approach studied in this paper achieves the same performance as the optimum (output) queueing alternative, without resorting to a faster packet switch fabric     

可行的基于CIOQ的并行分组交换结构

针对传统并行分组交换结构存在的平面可扩展性问题,提出一种可行的分布式并行分组交换PDPPS(practical distributed parallel packet switch)。在端口数为N和中间层平面数为K的情况下,PDPPS的复用器中只需要维护大小为NK的高速缓存,就能保证每条流按序输出。理论分析和仿真结果表明,PDPPS的性能优于使用OQ(output queuing)结构作为中间层平面的分布式并行分组交换结构VIQ PPS(virtual input queuing parallel packet switch),略微低于集中式PPS和IOQ PPS(in-order queuing parallel packet switch)。但相对于集中式PPS,PDPPS使用了更为通用且易于实现的CIOQ(combined input and output queuing)作为中间层平面;相对于IOQ PPS,PDPPS使用了分布式调度算法,从而消除了系统的通信开销,并且PDPPS极大地降低了所需的高速缓存数量。     

A comparison of optical buffering technologies

We describe the practical and fundamental limitations of the more prominent optical buffering approaches. The architectural implementation and needs of an optical packet switch are used as a foundation for the study. We also present initial results for a buffered, all-optical, 40 Gb/s packet switch.     

Resequencing Worst-Case Analysis for Parallel Buffered Packet Switches

This paper considers a general parallel buffered packet switch (PBPS) architecture which is based on multiple packet switches operating independently and in parallel. A load-balancing mechanism is used at each input to distribute the traffic to the parallel switches. The buffer structure of each of the parallel packet switches is based on either a dedicated, a shared, or a buffered-crosspoint output-queued architecture. As in such PBPS multipath switches, packets may get out of order when they travel independently in parallel through these switches, a resequencing mechanism is necessary at the output side. This paper addresses the issue of evaluating the minimum resequence-queue size required for a deadlock-free lossless operation. An analytical method is presented for the exact evaluation of the worst-case resequencing delay and the worst-case resequence-queue size. The results obtained reveal their relation, and demonstrate the impact of the various system parameters on resequencing     

多级交换中支持包保序的交换结构及调度算法

现有单级交换结构在其规模的有效扩展方面存在瓶颈。该文提出了一种新的中间级带缓存的高可扩展多级交换结构,并建立了该结构的排队论模型。针对交换网络内部的信元乱序问题,该文基于上述结构提出一种新的包保序算法,该算法通过严格同步输入级和中间级调度指针,能够简单有效地实现信元保序。理论分析结果表明,该结构能够获得100%的吞吐量且实现代价较小。仿真实验表明,该算法不仅能够获得较为理想的高吞吐量,并且在高负载强度下的平均时延性能优势明显。     

Scheduling scheme using Look-ahead Buffer and Loop-back Buffer in Two-stage variable optical packet switch

Programmable variable delay lines have been developed, so as to delay packets in variable durations by combining several lengths of Fiber Delay Lines (FDLs) in optical packet switch. In practice, Two-stage variable optical packet switch with this programmable variable delay lines has been proposed. This switch has two buffers. The one is the programmable variable delay lines (Look-ahead Buffer). The other is the fixed FDLs that re-input a packet from the output to the input (Loop-back Buffer). The switch can foresee following packets and avoid contentions effectively by using two buffers. However, existing studies only focus on the Look-ahead Buffer. Intelligent usage of the Loop-back Buffer is actually out of concern. This paper proposes a sophisticated scheduling method in the Two-stage switch. The proposed method controls both the Look-ahead Buffer and the Loop-back Buffer cooperatively and improves the utilization of the switching process. The proposed method uses the Loop-back Buffer adaptively and distributes traffics in time and space domain. The effectiveness of the proposed method is evaluated through extended simulation experiments and basic hardware design.     

Packet loss in a bufferless optical WDM switch employing sharedtunable wavelength converters

We propose an architecture for a bufferless packet optical switch employing the wavelength dimension for contention resolution. The optical packet switch is equipped with tunable wavelength converters shared among the input lines. An analytical model Is proposed in order to determine the number of converters needed to satisfy prefixed packet loss probability constraints. This analytical model very accurately fits with simulations results. A sensitivity analysis of the required number of converters as a function of the main system parameters (number of input and output lines, number of wavelengths, …) and traffic parameters has been carried out. Making use of the introduced dimensioning procedure we have observed that the proposed architecture allows a saving in terms of employed number of converters with respect to the other architectures proposed in literature. Such a saving can reach about 95% of the number of converters     

Nonblocking copy networks for multicast packet switching

In addition to handling point-to-point connections, a broadband packet network should be able to provide multipoint communications that are required by a wide range of applications. The essential component to enhance the connection capability of a packet network is a multicast packet switch, capable of packet replications and switching, which is usually a serial combinations of a copy network and a point-to-point switch. The copy network replicates input packets from various sources simultaneously, after which copies of broadcast packets are routed to their final destination by the switch. A nonblocking, self-routing copy network with constant latency is proposed. Packet replications are accomplished by an encoding process and a decoding process. The encoding process transforms the set of copy numbers, specified in the headers of incoming packets, into a set of monotone address intervals which form new packet headers. The decoding process performs the packet replication according to the Boolean interval splitting algorithm through the broadcast banyan network, the decision making is based on a two-bit header information. This yields minimum complexity in the switch nodes     

The performance analysis and implementation of an input accessscheme in a high-speed packet switch

The performance analysis of an input access scheme in a high-speed packet switch for broadband ISDN is presented. In this switch, each input port maintains a separate queue for each of the outputs, thus n ² input queues in an (n×n) switch. Using synchronous operation, at most one packet per input and output will be transferred in any slot. We derive lower and upper bounds for the throughput which show close to optimal performance. The bounds are very tight and approach to unity for switch sizes on the order of a hundred under any traffic load, which is a significant result by itself. Then the mean packet delay is derived and its variance is bounded. A neural network implementation of this input access scheme is given. The energy function of the network, its optimized parameters and the connection matrix are determined. Simulation results of the neural network fall between the theoretical throughput bounds     

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