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.

We examine high-throughput scheduling algorithms for buffered crossbar switch fabrics containing one buffer per crosspoint. We propose a scheduling system that uses longest queue first (LQF) scheduling for virtual output queues (VOQs) at the inputs and round-robin (RR) scheduling for the crosspoints. It is shown, through fluid model techniques, that this system achieves 100% throughput for input traffic that satisfies the strong law of large numbers and that produces a load /spl les/1/N for any input/output pair of an N/spl times/N switching fabric. Simulations indicate that 100% throughput may be attained for a much larger class of admissible loads.

Packet switching devices that rely on input buffering to prevent cell loss in the switch fabric must regulate the arrival pattern of data packets to the input links of the switch fabric. Frame-based bandwidth allocation can be used in cell-based switch fabrics to regulate the number of cells from a flow entering the fabric during a fixed-length frame of cell slots. We present a simple cell slot assignment algorithm for distributing each flow's cell slot allocations within a frame. The algorithm controls the inter-cell spacing for each flow and bounds fabric queues to a small number independent of the frame length. The simplicity of the algorithm supports per-frame changes in the allocated rates.

This paper examines required capacity in self-healing rings (SHRs) as a function of the protection scheme, spare bandwidth allocation, routing and the traffic demand pattern. Existing SONET bidirectional rings and proposals for B-ISDN bidirectional rings assume a fixed allocation of 50% of the available bandwidth for protection traffic. This paper presents a method of minimum spare bandwidth allocation on bidirectional rings which reduces the required capacity for both symmetric and asymmetric demand between node pairs. It is shown that a bidirectional ring with 1:1 path protection and minimum spare bandwidth allocation requires equal or less ring capacity than existing SONET SHRs for any traffic demand pattern.

In the past, the nonlinear effects of quantization in differential speech coders either were modeled as additive white Gaussian noise or were ignored in analysis and quantified experimentally. Describing functions are used to model the nonlinear quantizer effects of coarsely quantized difference signals found primarily in adaptive predictive coding (APC) systems. The analysis predicts marginal instabilities in APC encoders. The marginal instabilities result in ringing distortions in the reconstructed signal which, in the past, may have been attributed to pitch and spectral predictor mismatches. Adaptive order prediction is introduced, analyzed, and offered as a method for increasing the robustness of APC encoders.