M.Sc Thesis

M.Sc StudentPismenny Boris
SubjectMarket Driven Queueing
DepartmentDepartment of Computer Science
Supervisors PROF. Assaf Schuster
DR. Orna Agmon Ben-Yehud


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.