TY - GEN
T1 - Fair queueing for input-buffered switches with back pressure
AU - Li, Shizhao
AU - Chen, Jian Guo
AU - Ansari, Nirwan
N1 - Publisher Copyright:
© 1998 IEEE.
PY - 1998
Y1 - 1998
N2 - The output-buffered switching architecture, though is able to offer high throughput, guaranteed delay and fairness, is not practical owing to its lack of scalability, i.e., the memory size, speed, and control logic have to be scaled up proportionally to the number of input links, thus becoming infeasible for large switches. The commercial and research trend is to adopt architecture with input buffering which is scalable, but yields lower throughput and lacks the quality-of-service features such as delay bound and fairness. Although the problem of low throughput owing to head of line blocking in input-buffered switches can be resolved by adopting per-output-port queueing in each input port, the contention among input ports still limits the throughput. Existing schedulers designed for input-buffered switches attempt to improve throughput by imposing back pressure to the contending cells, and scheduling cells free of contention for transmission, at the expense of delay and fairness. In this paper, we modeled and analyzed the back pressure with independent Bernoulli traffic load, and showed that back pressure occurs with high probability under loaded traffic. We also derived the average queue length at the input buffer. To address the above issues in input-buffered switches, we proposed a new algorithm, referred to as min-max fair input queueing (MFIQ), which minimizes the additional delay caused by back pressure and at the same time provides fair service among competing sessions.
AB - The output-buffered switching architecture, though is able to offer high throughput, guaranteed delay and fairness, is not practical owing to its lack of scalability, i.e., the memory size, speed, and control logic have to be scaled up proportionally to the number of input links, thus becoming infeasible for large switches. The commercial and research trend is to adopt architecture with input buffering which is scalable, but yields lower throughput and lacks the quality-of-service features such as delay bound and fairness. Although the problem of low throughput owing to head of line blocking in input-buffered switches can be resolved by adopting per-output-port queueing in each input port, the contention among input ports still limits the throughput. Existing schedulers designed for input-buffered switches attempt to improve throughput by imposing back pressure to the contending cells, and scheduling cells free of contention for transmission, at the expense of delay and fairness. In this paper, we modeled and analyzed the back pressure with independent Bernoulli traffic load, and showed that back pressure occurs with high probability under loaded traffic. We also derived the average queue length at the input buffer. To address the above issues in input-buffered switches, we proposed a new algorithm, referred to as min-max fair input queueing (MFIQ), which minimizes the additional delay caused by back pressure and at the same time provides fair service among competing sessions.
KW - Back pressure
KW - Fair queueing
KW - Input-buffered switch
UR - http://www.scopus.com/inward/record.url?scp=85013585477&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85013585477&partnerID=8YFLogxK
U2 - 10.1109/ICATM.1998.688185
DO - 10.1109/ICATM.1998.688185
M3 - Conference contribution
AN - SCOPUS:85013585477
T3 - 1998 1st IEEE International Conference on ATM, ICATM 1998
SP - 252
EP - 259
BT - 1998 1st IEEE International Conference on ATM, ICATM 1998
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 1998 1st IEEE International Conference on ATM, ICATM 1998
Y2 - 22 June 1998 through 24 June 1998
ER -