Input-queued switching architectures are becoming an attractive alternative for designing very high speed switches owing to its scalability. Tremendous efforts have been made to overcome the throughput problem caused by contentions occurred at the input and output sides of the switches. However, no QoS guarantees can be provided by the current input-queued switch design. In this paper, a frame based scheduling algorithm, referred to as store-sort-and-forward (SSF), is proposed to provide QoS guarantees for input-queued switches without requiring speedup. SSF uses a framing strategy in which the time axis is divided into constant-length frames, each made up of an integer multiple of time slots. Cells arrived during a frame are first held in the input buffers, and are then "sorted-and-transmitted" within the next frame. A bandwidth allocation strategy and a cell admission policy are adopted to regulate the traffic to conform to the (r,T) traffic model. A strict sense 100% throughput is proved to be achievable by rearranging the cell transmission orders in each input buffer, and a sorting algorithm is proposed to order the cell transmission. The SSF algorithm guarantees bounded end-to-end delay and delay jitter. It is proved that a perfect matching can be achieved within N(ln N+O(1)) effective moves.

The input-queued switching architecture is becoming the alternative architecture for high speed switches owing to its scalability. Tremendous amount of effort has been made to overcome the throughput problem caused by head of line blocking and the contentions occurred at input and output sides of a switch. Existing algorithms only aim at improving throughput but inadvertently ignore undesired effects on the traffic shape and quality of service features such as delay and fairness. In this paper a new algorithm, referred to as longest normalized queue first, is introduced to improve upon existing algorithms in terms of delay, fairness and burstiness. The proposed algorithm is proven to be stable for all admissible traffic patterns. Simulation results confirm that the algorithm can smooth the traffic shape, and provide good delay property as well as fair service.

The routing and signaling protocols for supporting multipoint-to-multipoint connections in ATM networks have been presented earlier. VP-merge and VC-merge techniques have been proposed as the likely candidates for resolving the sender identification problem associated with these connections. The additional buffer requirements in the VC-merge mechanism and the excessive rise of VPI/VCI space in the VP-merge mechanism have been the main reasons for concern about their effective utility. We propose improvements to the traditional VC-merge technique to minimize the need for additional buffers at intermediate merge points. Aptly named dynamic multiple VC-merge (DMVC), fixed multiple VC-merge (FMVC) and selective multiple VC-merge (SMVC), these mechanisms define a generic scheme for merging the data from multiple senders onto one or more outgoing links. By appropriately choosing the number of connection identifiers per connection, these schemes lead to a large reduction in the buffer requirements and an effective utilization of the VPI/VCI space. Based on extensive simulations, we show that by using two connection identifiers per connection, there is an 80% reduction in buffer requirements for DMVC and FMVC when compared to the buffer required for traditional VC-merge.