Combined input output queued (CIOQ) architecture such as crossbar with speedup has recently been proposed to build a large capacity switch for broadband integrated services networks. It was shown that, for a speedup factor of 2, a CIOQ switch can achieve 100% throughput with a simple maximal matching algorithm. Achieving 100% throughput, however, is not sufficient for per-connection quality of service (QoS) guarantee. In [2],[3], it is proved that a CIOQ switch with a speedup factor of 2 can exactly emulate an output queued (OQ) switch if stable matching is adopted. Unfortunately, the complexity of currently known algorithms makes stable matching impractical for high-speed switches. In this paper, we propose a new matching algorithm called the least cushion first/most urgent first (LCF/MUF) algorithm and formally prove that a CIOQ switch with a speedup factor of 2 can exactly emulate an OQ switch which adopts any service discipline for cell transmission. A potential implementation of our proposed matching algorithm for strict priority service discipline is also presented.

In this paper, we present a traffic scheduling algorithm, called the Delay-Bound Monotonic with Average Rate Reservation (DM/ARR), which generates minimum output burstiness streams. We assume that connection i is policed by the leaky bucket algorithm with parameters (σi,ρi) where σi is the bucket size (or burstiness) and ρi is the leaky rate. Compared with the totally isolated scheme where connection i is allocated a bandwidth ri=max{σi/di,ρi} (di is the delay bound requirement of connection i), the DM/ARR algorithm has a better performance in the sense that it has a larger admission region. We prove that, among all possible scheduling algorithms that satisfy the delay bound requirements of established connections, DM/ARR results in the minimum output burstiness. This is important because a smaller burstiness implies a smoother traffic and thus the receiver (or next switch node in a multihop network) can handle it more easily. Numerical results show that the admission region of the DM/ARR algorithm is close to that of the earliest deadline first algorithm. A packetized version is studied for ATM networks.