TY - GEN
T1 - Input-queued switching with QoS guarantees
AU - Li, Shizhao
AU - Ansari, Nirwan
PY - 1999
Y1 - 1999
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0032623514&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032623514&partnerID=8YFLogxK
U2 - 10.1109/INFCOM.1999.751671
DO - 10.1109/INFCOM.1999.751671
M3 - Conference contribution
AN - SCOPUS:0032623514
SN - 0780354176
SN - 9780780354173
T3 - Proceedings - IEEE INFOCOM
SP - 1152
EP - 1159
BT - Proceedings - IEEE INFOCOM'99
T2 - 18th Annual Joint Conference of the IEEE Computer and Communications Societies: The Future is Now, IEEE INFOCOM'99
Y2 - 21 March 1991 through 25 March 1991
ER -