Space Efficient Fair Queuing by Stochastic Memory Multiplexing

Yehuda Afek, Tel Aviv University

We present a new buffer sharing and scheduling mechanism that implements Round-Robin. The mechanism uses simple hardware while consuming a modest amount of space. The mechanism may be used to share buffer space between the queues of back-logged flows at an output port of either an ATM switch (fixed size messages) or for IP switching (variable size messages).

Our claim is that there is a tradeoff between the complexity of buffer management and the buffer space utilization. At the extremes of this tradeoff are the two common and basic approaches for buffer space management, the {\em static} approach (one large queue per session) and the {\em dynamic} approach (linked list shared memory). We suggest a new approach that may strike an attractive balance between the two extremes. The approach, called Stochastic Memory Multiplexing (SMM), multiplexes the buffer space between flows. The hardware requirements of it are close to those of the static approach. Simulations and analysis show that it efficiently utilizes buffer space.

If time will permit, I will also talk about our new simple and efficient flow control algorithm for either ATM switches or TCP Routers.

(Joint work with Yishay Mansour and Zvi Ostfeld)