Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Market Driven Queuing
event speaker icon
Boris Pismenny (M.Sc. Thesis Seminar)
event date icon
Monday, 05.12.2016, 15:30
event location icon
Taub 301
event speaker icon
Advisor: Prof. Assaf Schuster and Dr. Orna Agmon Ben-Yehuda
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.