Back to search

Athens University Economics and Business (AUEB)

Performance analysis of distributed control algorithms in queueing systems

Abstract

dc:description

In this thesis we deal with the performance analysis of distributed control algorithms in two different areas where queues arise: a) wireless networks and b) ridesharing platforms.In the first part we consider the joint minimization of queueing cost and power consumption in a wireless network, over all power control policies at the transmitters. Approximately optimal policies are derived through a comparison to a single link system. The resulting policies are of a simple form: the total power consumed at any instant is a monotonic function of a linear combination of the queue backlogs at that instant, while the portions of power allocated to each transmitter are such that the resulting link speeds are proportional to the queue backlogs. What enables this sort of decomposition is the specific type of queueing cost considered and the fact that under the policy which minimizes this cost (under a fixed power budget), the system effectively becomes one-dimensional. As the structure of the optimal controls are known for this case, one can apply to optimize the performance of the“collapsed”one-dimensional system. Simulations show that the proposed policies offer significant performance gains as the average power approaches the lowest value for which stability is maintained. Moreover, these policies are shown to perform better than gradient projection -based power control schemes such as those resulting from network utility maximization. We apply these ideas in a CDMA (Code Division Multiple Access) wireless cell-based network and propose a concrete uplink power control scheme for low data packet queueing delay. The scheme can be seen as a simple extension to the Foschini-Miljanic algorithm which takes the transmit queue sizes at the mobile stations into account. The proposed scheme minimizes the draining time compared to all other policies with the same power consumption. This is because of resource pooling effects which arise when all queues empty at the same time. In its standard form the proposed scheme exploits resource pooling within a single cell and no communication is needed between cells. In an extension of the algorithm, resource pooling –and better performance– is achieved for the entire network by allowing limited messaging between the base stations of different cells. Simulations exhibit significant reductions in queueing delay compared to other power control schemes proposed in the literature, especially in the presence of slow fading. In the second part of the thesis, we study ridesharing platforms like Uber and Lyft. These platforms give monetary incentives to participating drivers, to share a ride with customers that also participate in the platform. When the supply of available drivers that exist in a certain location falls short of the demand for transport requested by the customers located at that location, the platforms increase the price for rides so as to counter the imbalance by attracting more available drivers and discouraging further passenger requests. In this setting, we study the effect that the type of information on which these dynamic prices are based on, has on the mobility patterns of available drivers and the resulting average pick-up delay. Based on a scalable discrete-time Markovian model for driver mobility and passenger queueing, we compare the performance of various policies which take into account such metrics as the number of the customers waiting in an area to be served and the ratio of the customers to drivers in an area. Simulation experiments show that customer queue and load information lead to superior performance compared to either prices calculated through tatonnement or driver behavior which do not take customer short-term demand fluctuations into account. Moreover, we find that dynamic information greatly reduces delay, a result which runs counter to recent findings in the literature which find that dynamic information does not increase the platform’s profits.

Degree

thesis:*
Grantor dc:publisher
Athens University Economics and Business (AUEB)
Year dc:date
2018

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Papafragkos, Spyridon
  • Παπαφράγκος, Σπυρίδων

Subjects

dc:subject × 12

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/42832

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Papafragkos, Spyridon; Παπαφράγκος, Σπυρίδων. Performance analysis of distributed control algorithms in queueing systems. Athens University Economics and Business (AUEB), 2018. http://hdl.handle.net/10442/hedi/42832