| TR#: | MSC-2017-22 |
| Class: | MSC |
| Title: | Market Driven Queueing |
| Authors: | Boris Pismenny |
| Supervisors: | Assaf Schuster and Orna Agmon Ben-Yehuda |
| MSC-2017-22.pdf | |
| 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. |
| Copyright | The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2017/MSC/MSC-2017-22), 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