Description

The virtually unlimited bandwidth of optical fibers has caused tremendous increase in the speed of data transmission during the past decade, and hence stimulated high-demand Gigabit per Second (Gb/s) multimedia services such as distance learning and video conferencing that will undoubtfully be part of our lives in the new century. The Internet, together with its robust and reliable Internet Protocol (IP), is widely considered as the most reachable platform of next-generation information infrastructure. The challenge to the success of the Internet lies in the deployment of Terabits per Second (Tb/s) packet switches to meet the exponential growth of multimedia and Internet traffic while providing Quality-Of-Service (QoS) support. It has been shown that an output-buffered ATM switch architecture has the best delay/throughput performance for arbitrary traffic distributions. But the output-buffered switch is difficult to scale up to 100 GB/s with existing integrated circuit technology. Several approaches have been proposed to build a large-capacity. The first approach adopts Knockout principle and uses a memory less concentrator followed by output-buffered switch modules to build a large-capacity switch. This approach has relatively smaller hardware complexity and good delay/throughput performance for arbitrary traffic distributions. However, this approach has not been accepted by switch vendors because cell loss occurs in the switch fabric, due to the lack of routing bandwidth, rather than in the output buffers due to buffer overflow.

Head-Of-Line (HOL) Blocking in Input-Buffered Switches

 The second approach adopts a funnel concept, where incoming cells are concentrated through multi-stage buffers. Because of the multi-stage buffers, it becomes expensive to implement buffer management and scheduling in every stage to achieve satisfactory QoS requirement. Moreover, the number of buffers increases exponentially as the switch size increases. The third approach interconnects Small Switch Modules (SSMs) as building blocks in a multi-stage structure. Its performance is degraded due to the blocking of internal links between switch modules. Although the performance can be improved by speeding up the internal links or providing more interconnection links between modules, this approach has not been convinced to be capable of providing satisfactory performance for a large-capacity ATM switch. Moreover, there is an out-of-sequence problem due to different queuing delays among different routing paths. Thus, the switch requires Resequencing Buffers (RSQBs) at the output ports. To cope with the worst-case out-of-sequence, the RSQB size can be very large. The fourth approach is to use a high-performance arbiter for an input-buffered switch. Input-buffered switch architecture does not suffer from the memory speed constraint. But, it needs to resolve the problems of output port contention and performance degradation. The Head-Of-Line (HOL) blocking in input-buffered switches can be entirely eliminated by using the so-called Virtual Output Queuing (VOQ), where in each input buffer; a separate queue is maintained for each output port. HOL blocking is eliminated because no cell can be held up by a cell ahead of it that is destined for a different output port. With VOQ structure and a suitable scheduling scheme, it is possible to achieve a maximum throughput of 100% for uniform and non-uniform traffic. However, to achieve good delay performance, multiple iterations are required, which imposes a higher speed arbiter. The fifth approach is to use an input–output-buffered structure with internal speedup for the switch fabric. With an internal speedup of two, the average delay/throughput performance is close to that of an output-buffered switch. The challenge of building such switches with a large capacity is the high-speed arbitration. The Abacus switch is an input–output-buffered switch. Instead of using internal speedup, the Abacus switch uses multiple routing links for each output port to improve the delay/throughput performance. The Abacus switch employs several techniques to achieve a large capacity. However, because of the excessive routing delay in the switch fabric, the switch capacity is limited to some extent.

Buffered Multi-Stage Concentration Network

The capacity of the Abacus switch was limited due to excessive routing delay in the switch fabric. This can be resolved using a memoryless Multi-Stage Concentration Network (MMCN), which reduces the routing delay and increases the capacity of the Abacus switch. Another approach is a Buffered Multi-Stage Concentration Network (BMCN), which uses a funnel concept and an input-buffered Concentration Modules (CMs) to relax the memory speed constraint. A new priority assignment scheme is proposed for the input-buffered CM to maintain the cell sequence of a virtual connection. The third approach is to increase the window size for the input to send cells before the acknowledgement. If the input sends more than one cell before it receives the acknowledgement, there can be out-of-sequence cells for large switch size. Since maximum degree of out-of-sequence is bounded in the worst case, we can resequence cells at the output port although it introduces a fixed amount of cell transfer delay. This approach allows the arbitration cycle exceeding a cell slot and thus resequences cells at the output port. It is proved that the maximum degree of out-of-sequence is bounded in the worst case. It is also proposed to handle variable-length packets in the Abacus switch. To reserve cell sequence in a packet, we propose two cell scheduling schemes at the input buffers: packet interleaving where all cells belonging to the same packet are switched consecutively, and cell interleaving where cells from different inputs are switched and reassembled at the output.