The Taub Faculty of Computer Science Events and Talks

Network providers must dynamically allocate scarce physical resources among their clients to maximize benefit. Network pricing is one way for providers to maximize client benefit by allowing them to share available bandwidth according to their willingness to pay for it. The resulting allocation grants additional bandwidth to those who need it the most, while decreasing the bandwidth of those who need it the least. Existing queueing algorithms use the results of pricing schemes as weights for sharing bandwidth, which can change only in response to a change in client willingness to pay. However, network congestion, jitter and failures affecting a flow create excess bandwidth that could be used by another flow. Queueing algorithms that can share the excess bandwidth are called work-conserving. Network pricing schemes traditionally ignore work conservation, by assuming that all clients are constantly backlogged. In this paper, we design and evaluate the Market Driven Queueing (MDQ) algorithm. By combining a queueing algorithm with a bandwidth pricing mechanism, MDQ provides the benefits of both. As a work-conserving algorithm, MDQ maximizes client benefit while improving utilization. Moreover, it requires only O(log(n)) processing time per packet, where n is the number of active flows. We analyse the properties of MDQ and evaluate it using simulation. Our simulation results show that MDQ improves clients’ aggregated benefit by up to 4x compared to state-of-the-art combinations of pricing and queueing algorithms. MDQ is also applicable to other scheduling problems such as distributed queues or I/O queue scheduling.