Fair queueing for input-buffered switches with back pressure

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.