Distributed management of competitive access to common resources using algorithmic game theory

Abstract

The Internet is today an inextricable part of daily personal, educational and business activity, turning any problems in its operation or availability into a significant interruption of these activities and their users. The resources offered by the Internet (capacity, coverage) are continuously increasing but at the same time the users and their demands are increasing at an even larger pace. If measures for the efficient and fair management of the network resources are not taken, the Internet will cease to be able to support new users and applications with high quality. Internet users operate in an independent manner, by creating data flows (sending and receiving network packets) which satisfy their demands. Each user prefers for his needs to be served in the best possible way but the resources of the network are shared and finite, making it often impossible to provide the best service to everyone. This leads to users competing amongst themselves for access to the network resources and its services. Whenever the demands placed on the services by the users exceed the capacity of the services, a means of selecting which users and to which degree they will be served is required. In the case of the Internet, the resources are network capacity, the demands of the users are requests for transferring network packets and the functionality of selecting which users are served and how they are served is generally referred to as Quality of Service (QoS). One feature of the Internet which significantly affects the possible solutions to providing QoS is its decentralized structure: there exists no central authority which is responsible for the whole operation of the network and which could centrally perform the resource allocation. Instead, resources are allocated locally at each network node to the users which access it. In this work, we address the issue of managing competitive access to common resources through the use of algorithmic game theory. This approach is validated by the competitive, selfish and independent nature of the users. Additionally, in the case of QoS provision for the Internet, our solutions have to be distributed in order to be applicable. Specifically, we start by proposing the Prince mechanism for distributing network flow throughput in a (MaxMin-resembling) fair manner. We then propose an efficient data structure and algorithm set for implementing Prince on a network router queue. We continue by providing the theoretical description and first simple experimental implementation of PacketEconomy, a network economy where each flow is modelled as a population of rational network packets, and these packets can self-regulate their access to network resources by mutually trading their positions in router queues. This theoretical model is then adapted to the OMNET++ simulator and via thorough experimentation we present the validation of the efficacy of our solution in a realistic context. Applying the same principles of game-theoretic analysis to realistic service provision problems, we also study an Internet-based VoIP service access problem in the context of the prevention of SPIT (SPam over Internet Telephony).

Το Διαδίκτυο σήμερα αποτελεί αναπόσπαστο μέρος καθημερινής ιδιωτικής, εκπαιδευτικής και επιχειρηματικής δραστηριότητας, με αποτέλεσμα προβλήματα στη λειτουργία του να προκαλούν σημαντικές διαταραχές σε αυτές τις δραστηριότητες και να επηρεάζονται οι χρήστες του. Οι πόροι που διαθέτει το Διαδίκτυο (χωρητικότητα, συνδέσεις) αυξάνονται διαρκώς αλλά ταυτόχρονα, με μεγαλύτερο ρυθμό, αυξάνονται οι χρήστες του και οι απαιτήσεις των εφαρμογών τις οποίες καλείται να υποστηρίξει. Αν δεν ληφθούν μέτρα για την αποδοτική διαχείριση και την δίκαιη κατανομή των πόρων δικτύου, το Διαδίκτυο θα πάψει να έχει την δυνατότητα να υποστηρίζει νέους χρήστες και εφαρμογές και να διασφαλίζει υψηλή ποιότητα παροχής υπηρεσιών. Οι χρήστες του Διαδικτύου λειτουργώντας ανεξάρτητα ο ένας από τον άλλο δημιουργούν ροές δεδομένων (στέλνοντας και λαμβάνοντας πακέτα δεδομένων) οι οποίες χρησιμοποιούν τους κοινόχρηστους και πεπερασμένους πόρους του Διαδικτύου. Καθώς κάθε χρήστης προτιμά την καλύτερη δυνατή εξυπηρέτηση για τις ροές του και καθώς η χωρητικότητα του δικτύου επιτρέπει συχνά μόνο ένα υποσύνολο των πακέτων να εξυπηρετηθούν, δημιουργείται ανταγωνισμός κατά την πρόσβαση στους κοινόχρηστους πόρους. Καθώς δεν υπάρχει κάποια κεντρική αρχή που να είναι υπεύθυνη για την ανάθεση πρόσβασης στους πόρους του δικτύου, η πρόσβαση ανατίθεται με αποκεντρωμένο τρόπο σε κάθε δρομολογητή. Οι χρήστες του δικτύου μπορούν να υποβάλουν ένα αυθαίρετο πλήθος από πακέτα ανά πάσα στιγμή στο δίκτυο και ο κάθε δρομολογητής αποφασίζει πόσα και ποια θα δεχθεί και πως θα τα εξυπηρετήσει. Η έλλειψη συντονισμού μεταξύ των ανεξάρτητων ροών οδηγεί το Διαδίκτυο να εμφανίζει μια "άναρχη" μορφή λειτουργίας και δημιουργεί προβλήματα τα οποία μπορούν να αντιμετωπιστούν με έννοιες και εργαλεία από την αλγοριθμική θεωρία παιγνίων. Πιο συγκεκριμένα, ο στόχος είναι να βρεθούν οι προϋποθέσεις και ο τρόπος επίτευξης δίκαιης, αποδοτικής και υπολογιστικά εφικτής (tractable) αποκεντρωμένης διαχείρισης πόρων σε δίκτυα υπολογιστών. Στα παιγνιοθεωρητικά μοντέλα αυτό που ενδιαφέρει συνήθως είναι να διερευνηθεί ποιες είναι οι καταστάσεις ισορροπίας του συστήματος. Μια από τις πιο σημαντικές κατηγορίες καταστάσεων ισορροπίας είναι οι ισορροπία Nash (Nash Equilibrium). Στην ισορροπία Nash κανένας παίκτης/χρήστης δεν έχει κίνητρο να αλλάξει τη στρατηγική του οπότε από τη στιγμή που θα επιτευχθεί αυτή η ισορροπία το σύστημα σταθεροποιείται σε αυτή την κατάσταση. Είναι συχνά επιθυμητό ένα παίγνιο να τείνει προς μια τέτοια ισορροπία αλλά έχει αποδειχθεί πως η υπολογιστική πολυπλοκότητα εύρεσης των Ισορροπιών Nash ακόμα και σε απλά μοντέλα είναι PPAD-complete, κάνοντάς τις ενδεχομένως δύσκολο να επιτευχθούν. Επιπλέον, η έρευνα στο χώρο στην συντριπτική της πλειοψηφία έχει ασχοληθεί με θεωρητικά μοντέλα δικτυακών παιγνίων τα οποία απέχουν σημαντικά από την δομή και την λειτουργία των πραγματικών δικτύων. Για τους παραπάνω λόγους καθίσταται σημαντική η μελέτη αυτών των μοντέλων όχι μόνο θεωρητικά αλλά και πειραματικά, ώστε να αποδειχθεί η πρακτική υλοποιησιμότητα του μοντέλου και η ρεαλιστική μελέτη των επιδόσεων και των χαρακτηριστικών του. Η παρούσα διδακτορική έρευνα περιλαμβάνει τη διερεύνηση των τρόπων αξιοποίησης της αλγοριθμικής θεωρίας παιγνίων για την κατασκευή αποκεντρωμένων μηχανισμών διαχείρισης πρόσβασης σε πόρους δικτύου. Βασική αρχή της έρευνας είναι ότι η δημιουργία κατάλληλων αλγορίθμων διαχείρισης των πόρων, τέτοιων που να δίνουν κίνητρο στους χρήστες να ρυθμίζουν σωστά τις ροές δεδομένων τους, οδηγούν στα επιθυμητά αποτελέσματα για όλους τους χρήστες. Χωρίς τα κατάλληλα κίνητρα οι χρήστες, συμπεριφερόμενοι εγωιστικά, κάνουν κατάχρηση των κοινών πόρων και ζημιώνουν και τρίτους χρήστες. Στόχος είναι η σχεδίαση, υλοποίηση και μελέτη της συμπεριφοράς τέτοιων αλγορίθμων σε θεωρητικό και πειραματικό επίπεδο.