To increase both the capacity and the processing speed for input-queued (IQ) switches, we proposed a fair scalable scheduling architecture (FSSA). By employing FSSA comprised of several cascaded sub-schedulers, a large-scale high performance switches or routers can be realized without the capacity limitation of monolithic device. In this paper, we present a fair scheduling algorithm named FSSA_DI based on an improved FSSA where a distributed iteration scheme is employed, the scheduler performance can be improved and the processing time can be reduced as well. Simulation results show that FSSA_DI achieves better performance on average delay and throughput under heavy loads compared to other existing algorithms. Moreover, a practical 64 64 FSSA using FSSA_DI algorithm is implemented by four Xilinx Vertex-4 FPGAs. Measurement results show that the data rates of our solution can be up to 800 Mbps and the tradeoff between performance and hardware complexity has been solved peacefully.

Proportional fair bandwidth allocation in packet switches is a fundamental issue to provide quality of service (QoS) support in IP networks. In input-queued switches, packet-mode scheduling delivers all the segments of a packet contiguously from the input port to the output port, thus greatly simplifying the design of packet reassembly modules and yielding performance advantage over cell-mode scheduling under certain conditions [1]. One of the important issues of packet-mode scheduling is how to achieve fair bandwidth allocation among flows with different packet sizes. This paper presents an algorithm called packet-mode fair scheduling (pFS) that guarantees each flow a bandwidth proportional to its reservation regardless of the packet size distribution and the system load. Simulations show that our approach achieves good fairness as well as high throughput and low packet delay. Compared to algorithms without fairness mechanism, pFS yields significant performance improvement in terms of average packet delay when the traffic is heterogeneous. A hardware implementation is presented to show that the proposed algorithm has low complexity and the computation can be completed in a single clock cycle, which makes pFS applicable to high-speed switches.

This letter proposes a combined input- and crosspoint-queued (CIC) switch in which virtual output queuing (VOQ) is used at each input port. This CIC switch has a large buffer at each input port and a small buffer at each crosspoint. It does not require high-speed memory access or high-speed internal cell transmission lines. Since the performance of the CIC switch depends on the scheduling algorithms, we propose new scheduling algorithms for the CIC switch. Numerical results show that the mean cell delay time performance of the CIC switch using the proposed scheduling algorithms is better than that of an input-queued ATM switch. In addition, the required buffer size for the CIC switch using the proposed scheduling algorithms is smaller than that for a crosspoint-queued ATM switch.

This paper proposes the iterative quasi-oldest-cell-first (i-QOCF) scheduling algorithm, a new scheduling algorithm for input-queued ATM switches with virtual output queuing (VOQ). In the i-QOCF scheduling algorithm, each input port and each output port maintains its own list. The length of the list can be N, 2 N, ..., B N, where B is the size of the separate queue for an output port at input ports, and N is the number of output ports. The list maintained by an input port contains the identifiers for those output ports to which that input port will send a cell. The list maintained by an output port contains the identifiers for input ports that have a cell destined for that output port. If we use a list whose length is B N, then the identifiers in the list appear in the oldest order, and i-QOCF gives preference to cells that have been waiting for the longest time. If we use a list whose length is less than B N, then the identifiers in the list appear in the quasi-oldest order, and i-QOCF gives preference to cells that have been waiting for the quasi-longest time. We determine the performance of i-QOCF in a comparison with i-OCF in terms of cell delay time. We find that an input-queued ATM switch with i-QOCF and VOQ can achieve 100% throughput for independent arrival processes. Under uniform traffic, 3-QOCF is enough to achieve convergence during one cell time. If we use 3-QOCF, the list length is 3 N, then its cell delay time is almost the same as that of 4-OCF (Oldest-Cell-First).

In this paper there suggested is a bifurcated (or multiple) input-queued ATM switch in which a buffer for each input port is divided into multiple (m) buffer blocks, i. e. , bifurcated buffers, for enhancement of the limited throughput of the ordinary input-queued switch using a single FIFO. As the contention/arbitration rule for the bifurcated input-queued switching scheme, free and restricted contention rules are come up with and discussed. The free rule allows an input port to switch up to m cells at the cost of internal speedup. With the restricted rule, on the other hand, an input port can switch no more than one cell in a time slot so that the switch operates at the same speed as the external link speed. The throughput bound for the bifurcated input-queued switch is analyzed for both rules through the generalization of the analysis by Karol et al. The throughput bound approaches to 1.0 as m becomes large enough, irrespective of the contention/arbitration rule.