Performance analysis of distributed control algorithms in queueing systems

Abstract

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.

Στην διατριβή αυτή μελετάμε την ανάλυση επίδοσης κατανεμημένων αλγορίθμων ελέγχου σε δυο διαφορετικές περιοχές όπου προκύπτουν ουρές αναμονής: α) ασύρματα δίκτυα και β) πλατφόρμες κοινής χρήσης ιδιωτικών αυτοκινήτων. Στο πρώτο μέρος μελετάμε την από κοινού ελαχιστοποίηση του κόστους αναμονής και της κατανάλωσης ενέργειας σε ένα ασύρματο δίκτυο, πάνω από όλες τις πολιτικές ελέγχου ισχύος στους πομπούς. Προκύπτουν σχεδόν βέλτιστες πολιτικές μέσω μιας σύγκρισης με ένα ενιαίο σύστημα ζεύξης. Οι πολιτικές αυτές είναι της μορφής: η συνολική ισχύς που καταναλώνεται σε οποιαδήποτε στιγμή είναι μια μονότονη συνάρτηση ενός γραμμικού συνδυασμού του μεγέθους των ουρών εκείνη την στιγμή, ενώ ο διαμοιρασμός της ισχύος σε κάθε πομπό είναι τέτοιος ώστε οι ταχύτητες σύνδεσης που προκύπτουν να είναι ανάλογες του μεγέθους των ουρών. Αυτό που επιτρέπει αυτό το είδος αποσύνθεσης είναι ο συγκεκριμένος τύπος κόστους αναμονής που εξετάζεται καθώς και το γεγονός ότι κάτω από την πολιτική όπου ελαχιστοποιεί αυτό το κόστος (κάτω από ένα συγκεκριμένο προυπολογισμό ισχύος), το σύστημα γίνεται ουσιαστικά μονοδιάστατο. Καθώς η δομή του βέλτιστου ελέγχου είναι γνωστή για την περίπτωση αυτή, μπορεί κανείς να την εφαρμόσει για την βελτιστοποίηση της επίδοσης του μονοδίαστατου αυτού συστήματος. Προσομοιώσεις δείχνουν ότι προτεινόμενες πολιτικές προσφέρουν σημαντικά οφέλη επίδοσης καθώς η μέση ισχύς πλησιάζει την χαμηλότερη τιμή για την οποία διατηρείται η σταθερότητα. Επιπλέον, οι πολιτικές αυτές φαίνεται ότι αποδίδουν καλύτερα από σχήματα ελέγχου ισχύος με βάση την προβολή κλίσης, όπως εκείνες που προκύπτουν από την μεγιστοποίηση της χρησιμότητας του δικτύου. Εφαρμόζουμε αυτές τις ιδέες σε ένα κυψελωτό ασύρματο δίκτυο CDMA (διαίρεσης κώδικα πολλαπλής πρόσβασης) και προτείνουμε ένα συγκεκριμένο σχήμα ελέγχου ισχύος ανερχόμενης ζεύξης για πακέτα δεδομένων με μικρή καθυστέρηση στις ουρές αναμονής. Το σχήμα αυτό μπορεί να θεωρηθεί σαν μια επέκταση του αλγορίθμου των Foschini-Miljanic ο οποίος λαμβανει υπόψη τα μεγέθη των ουρών στις κινητές συσκευές. Το προτεινόμενο αυτό σχήμα ελαχιστοποιεί τον χρόνο αποστράγγισης συγκριτικά με οποιαδήποτε άλλη πολιτική με την ίδια κατανάλωση ενέργειας. Αυτό συμβαίνει εξαιτίας επίδρασης ενός φαινομένου που ονομάζεται συγκέντρωση πόρων που προκύπτει όταν όλες οι ουρές αδειάζουν την ίδια χρονική στιγμή. Στην τυποποιημένη μορφή του το προτεινόμενο σχήμα εκμεταλλεύεται την συγκέντρωση πόρων μέσα σε μια κυψέλη και δεν χρειάζεται περεταίρω επικοινωνία μεταξύ κυψελών. Σε μια επέκταση του αλγορίθμου η συγκέντρωση πόρων –και ακόμα καλύτερη επίδοση- επιτυγχάνεται για ολόκληρο το δίκτυο επιτρέποντας περιορισμένη επικοινωνία μέσω μηνυμάτων μεταξύ των σταθμών βάσης διαφορετικών κυψελών. Προσομοιώσεις παρουσιάζουν σημαντικές μειώσεις στην καθυστέρηση των ουρών αναμονής σε σύγκριση με άλλα σχήματα ελέγχου ισχύος που έχουν προταθεί στην βιβλιογραφία και ειδικά υπό την παρουσία αργής εξασθένησης σήματος. Στο δεύτερο μέρος της διατριβής, μελετάμε πλατφόρμες κοινής χρήσης ιδιωτικών αυτοκινήτων όπως για παράδειγμα η Uber και η Lyft. Τέοιες πλατφόρμες δίνουν οικονομικά κίνητρα στους οδηγούς που συμμετέχουν, για να μοιραστούν μια διαδρομή με πελάτες που κι εκείνοι με την σειρά τους συμμετέχουν στην πλατφόρμα. Όταν η προσφορά των διαθέσιμων οδηγών σε μια συγκεκριμένη τοποθεσία υπολείπεται της ζήτησης για μεταφορά πελατών στην ίδια τοποθεσία, οι πλατφόρμες αυξάνουν την τιμή για μεταφορά έτσι ώστε να αντιμετωμιστεί η ανισορροπία προσελκύοντας περισσότερους διαθέσιμους οδηγούς και ταυτόχρονα αποτρέποντας επιπλέον αιτήματα επιβατών. Κάτω από αυτές τις ρυθμίσεις, μελετάμε την επίδραση των τύπων της πληροφορίας επί των οποίων βασίζονται αυτές οι δυναμικές τιμές, που έχουν στα μοτίβα κινητικότητας των διαθέσιμων οδηγών και στη μέση καθυστέρηση του χρόνου που μεσολαβεί μέχρι ένας οδηγός να παραλάβει κάποιον πελάτη. Με βάση ένα βαθμωτό διακριτού-χρόνου Μαρκοβιανό μοντέλο για την κινητικότητα των οδηγών και την συσσώρευση των επιβατών σε ουρές αναμονής, συγκρίνουμε τις επιδόσεις διαφόρων πολιτικών που λαμβάνουν υπόψη μετρικές όπως ο αριθμός των πελατών που περιμένουν σε μια περιοχή να εξυπηρετηθούν ή η αναλογία των πελατών προς τους οδηγούς σε μια περιοχή. Πειράματα δείχνουν ότι η πληροφορία των πελατών σε μια ουρά και η αναλογία τους προς τους οδηγούς, οδηγούν σε ανώτερες επίδοσεις σε σύγκριση με τιμές που υπολογίζονται μέσω μηχανισμού δοκιμής και λάθους (tatonnement) ή συμεριφοράς των οδηγών οι οποίες δεν λαμβάνουν υπόψη βραχυπρόθεσμες διακυμάνσεις της ζήτησης. Επιπλέον, βρίσκουμε ότι ότι η δυναμική πληροφορία μειώνει σημαντικά την καθυστέρηση, ένα αποτέλεσμα που έρχεται σε αντίθεση με πρόσφατα ευρήματα στην βιβλιογραφία, όπου βρίσκουν πως η δυναμική πληροφορία δεν αυξάνει τα κέρδη της πλατφόρμας.