Technical Report MSC-2017-22

Title: Market Driven Queueing
Authors: Boris Pismenny
Supervisors: Assaf Schuster and Orna Agmon Ben-Yehuda
Abstract: Network providers must dynamically allocate scarce physical resources among their clients to maximize bene t. Network pricing is one way for providers to maximize client bene t 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 a ecting a ow create excess bandwidth that could be used by another ow. 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 bene ts of both. As a work-conserving algorithm, MDQ maximizes client bene t while improving utilization. Moreover, it requires only O(log(n)) processing time per packet for tra c scheduling, where n is the number of active ows. We analyze the properties of MDQ and evaluate it using simulation. Our simulation results show that MDQ improves clients' aggregate bene t 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2017
To the main CS technical reports page

Computer science department, Technion