Spectrum and storage capacity management using network economics and optimization methods

Abstract

The last few years we are witnessing an unprecedented growth in user demand for high speed communication and ubiquitous network access. Moreover novel communication paradigms and applications create an ever increasing volume of data traffic that must be transported in a timely and cost efficient fashion. This impressive transformation of communication networks poses new challenges for their design and management that cannot be addressed with traditional methods of resource over provisioning and technology upgrading. At the same time nowadays it is clear that critical and valuable network resources such as spectrum and in network storage are either underutilized or not adequately exploited. These observations indicate that there is still much space for improvement and call for innovative approaches in network design and network resource management. In this thesis we propose market based mechanisms and optimization methods in order to increase utilization of critical network resources and improve the performance of networks in terms of data transfer capability. These mechanisms are of paramount importance for contemporary networks which are often plagued by the lack of coordination and the egotistic behavior of their constituent nodes. First we focus on spectrum management a resource that is scarce and at the same time remains underutilized in large extent. A prominent proposed solution for this problem is the reform of spectrum allocation policy and the deployment of dynamic spectrum (DS) markets. In these markets spectrum will be freely traded as a commodity and very often hierarchical structures among the interacting entities will emerge. We study these multilayer markets and propose a mechanism that increases the allocative efficiency of spectrum. We consider the representative scenario that arises when a governmental agency sells spectrum channels to Primary Operators (POs) who subsequently resell them to Secondary Operators (SOs) through auctions in monopolistic markets. We show that this hierarchical scheme does not ensure a socially efficient spectrum allocation which is aimed by the agency due to lack of coordination among the entities in different layers and the selfish revenue maximizing strategy of POs. In order to reconcile these opposing objectives we propose a pricing based incentive mechanism which aligns the actions of the POs with the objective of the agency and thus leads to system performance improvement in terms of social welfare. The suggested mechanism constitutes a method for regulation which is proved to be of crucial importance for the emerging hierarchical spectrum markets. Next we relax the assumption of monopolistic markets and analyze the competition of wireless services providers over a common pool of users. We show that lack of information about the actual network capacity and egotistic strategies of operators may induce revenue reduction for the latter or efficiency loss for the market. We assume that users have a reservation utility or equivalently an alternative option to satisfy their communication needs. The operators must satisfy these minimum requirements in order to attract clients. We model the interaction of users as an evolutionary game and the competition among the operators as a non cooperative pricing game. We prove that the equilibriums of both games depend on the reservation utility and the amount of spectrum the operators have at their disposal. Accordingly we consider the scenario where a regulating agency is able to intervene in the market by tuning these parameters. Different regulators may have different objectives and criteria. We adopt a mechanism design perspective analyze the various possible regulation methods and discuss their requirements implications and impact on the welfare of the market and the revenue of the operators. Apart from the hierarchical spectrum allocation through monopolistic or oligopolistic markets another crucial aspect of these dynamic spectrum management schemes is that they aim to facilitate spectrum exchange among different entities in the same layer. For example each secondary operator may lease or even exchange its channels to other operators. Similarly users will be able to exchange bandwidth in order to satisfy their dynamic needs. In this setting each entity is both a resource provider and a resource consumer. Moreover these two roles are intertwined since they both presume the consumption of the entity’s scarce spectrum resource. We model this problem and propose a dynamic pricing scheme that clears the market and ensures the maximization of social Welfare. Through the adoption of proper pricing and allocation rules selfish behavior is deterred and the actual needs of the market entities are revealed and satisfied. Market based network management methods provide incentives to network entities for increasing network resource utilization. Equally important for improving network performance is the exploitation of resources which until now have not been incorporated in the network design. A prominent example is in network storage a resource that nowadays is very cheap compared to bandwidth and available at large scale. We advocate that storage can be used to improve the data transfer capability of dynamic networks i.e. networks with time varying link capacities and we identify the conditions under which this improvement is realizable. The basic idea is to temporarily store data at nodes when network conditions (e.g. link capacities) are not favorable for data transmission. We use the technique of time expanded graphs in order to map the dynamic networks to equivalent static networks. First we introduce a method that increases the mm cut of the network by adding storage to certain nodes. Next we propose the conjunction of storage control with routing. We define the max flow problem in the time expanded graph and solve it by using a distributed algorithm. The solution constitutes the optimal joint storage control and routing (JSR) policy. Finally we discuss the importance of available information about current and future network state on performance of the proposed algorithms.

Τα τελευταία χρόνια παρατηρούμε μια πρωτόγνωρη αύξηση της απαίτησης των χρηστών για αδιάλειπτη και συνεχή πρόσβαση σε υψηλής ταχύτητας δίκτυα επικοινωνιών. Ταυτόχρονα νέες μέθοδοι επικοινωνίας και νέες εφαρμογές παράγουν έναν τεράστιο όγκο δεδομένων τα οποία πρέπει να μεταφερθούν στον προορισμό τους εγκαίρως και με το μικρότερο δυνατό κόστος. Η εντυπωσιακή αυτή μετάλλαξη των δικτύων επικοινωνίας θέτει νέες προκλήσεις στη σχεδίαση και διαχείριση τους οι οποίες δε δύναται να αντιμετωπιστούν με τις παραδοσιακές μεθόδους αύξησης των πόρων τους και αναβάθμισης της τεχνολογίας τους. Ταυτόχρονα σήμερα είναι εμφανές ότι βασικοί πόροι όπως το ηλεκτρομαγνητικό φάσμα και οι αποθηκευτικοί χώροι σε κόμβους δικτύων δεν αξιοποιούνται κατάλληλα και επαρκώς. Οι διαπιστώσεις αυτές οδηγούν στο συμπέρασμα ότι υπάρχουν σημαντικά περιθώρια για βελτίωση της λειτουργίας των δικτύων και καθιστούν επιτακτική την ανάγκη για νέες και πρωτοποριακές μεθόδους σχεδίασης και διαχείρισης τους. Στην παρούσα διατριβή μελετάμε και προτείνουμε μηχανισμούς βασισμένους στην οικονομική θεωρία καθώς και μεθόδους βελτιστοποίησης προκειμένου να επιτευχθεί η καλύτερη αξιοποίηση των πόρων των δικτύων και να αυξηθεί η απόδοση τους. Οι εν λόγω μηχανισμοί είναι ιδιαίτερα σημαντικοί για τα σύγχρονα δίκτυα επικοινωνιών η λειτουργία των οποίων συχνά δυσχεραίνεται λόγω της έλλειψης συντονισμού και της εγωιστικής συμπεριφοράς των κόμβων τους. Αρχικά μελετάμε τη διαχείριση ηλεκτρομαγνητικού φάσματος που αποτελεί έναν πόρο μη επαρκώς αξιοποιημένο πάρα τη συνεχώς αυξανόμενη ζήτηση για αυτόν. Αναλύουμε και προτείνουμε μηχανισμούς διαχείρισης φάσματος σε ιεραρχικές πολύ επίπεδες αγορές οι οποίες αναμένεται να κυριαρχήσουν στο μέλλον συμφωνά με τις πρόσφατες προταθείσες πολιτικές διαχείρισης φάσματος. Συγκεκριμένα μελετάμε τη διαδικασία κατά την οποία ένας κρατικός οργανισμός πουλάει συχνότητες ηλεκτρομαγνητικού φάσματος σε εμπορικούς παρόχους ασυρμάτων υπηρεσιών (Primary Operators) και οι οποίοι με τη σειρά τους μεταπουλάνε μέσω δημοπρασιών σε μονοπωλιακές αγορές μέρος αυτού του φάσματος σε δευτερεύοντες παρόχους (Secondary Operators). Αποδεικνύουμε ότι αυτή η ιεραρχική ανάθεση του φάσματος δεν εξασφαλίζει τη βέλτιστη δυνατή αξιοποίησή του λόγω της έλλειψης συντονισμού μεταξύ των οντοτήτων στα διαφορετικά επίπεδα καθώς και της προσπάθειας των πρωτευόντων παροχέων να μεγιστοποιήσουν το κέρδος τους. Για την επίλυση αυτού του προβλήματος προτείνουμε έναν μηχανισμό ο οποίος βασίζεται στην κοστολόγηση και επιτυγχάνει την αύξηση της χρήσης του φάσματος και την επακόλουθη βελτίωση της λειτουργίας των υπόψη δικτύων. Ένα βασικό δομικό στοιχείο του προτεινόμενου μηχανισμού είναι μία νέα τεχνική δημοπρασιών η οποία επιτυγχάνει τη στάθμιση του κέρδους και της αποδοτικότητας κατά την ανάθεση των πόρων από το δημοπράτη στους υποψήφιους αγοραστές. Ακολούθως μελετάμε αγορές ασυρμάτων υπηρεσιών στις οποίες οι πάροχοι ανταγωνίζονται για να ελκύσουν χρήστες-πελάτες. Πολύ συχνά οι αγορές αυτές οδηγούν σε μη αποδοτική και επωφελή εξυπηρέτηση των χρηστών άλλα και σε μειωμένο κέρδος για τους ίδιους τους παρόχους θεωρούμε ότι οι χρήστες έχουν συγκεκριμένες ελάχιστες απαιτήσεις ή ισοδύναμα εναλλακτικούς τρόπους για να καλύψουν τις επικοινωνιακές τους απαιτήσεις. Οι πάροχοι οφείλουν να καλύψουν αυτές τις ελάχιστες απαιτήσεις προκειμένου να είναι ανταγωνιστικοί και επιλέξιμοι από τους χρήστες. Μοντελοποιούμε και αναλύουμε την αλληλεπίδραση των χρηστών μέσω της θεωρίας εξελικτικών παιγνίων και τον ανταγωνισμό των παρόχων μέσω ενός μη συνεργατικού παιγνίου. Τα σημεία ισορροπίας των δυο αυτών παιγνίων εξαρτώνται από τις ελάχιστες απαιτήσεις των χρηστών καθώς και το φάσμα που διαθέτουν οι πάροχοι. Εκφράζουμε το συνολικό όφελος των χρηστών αλλά και το κέρδος των παροχών ως συναρτήσεις αυτών των δυο παραμέτρων. Στη συνέχεια εξετάζουμε πιθανές μεθόδους με τις οποίες μια ρυθμιστική αρχή δύναται να παρεμβαίνει και να επηρεάζει τα σημεία ισορροπίας της συγκεκριμένης αγοράς. Ανάλογα με τον απώτερο στόχο της ρυθμιστικής αρχής απαιτούνται διαφορετικές τεχνικές παρέμβασης οι οποίες οδηγούν και σε διαφορετικά νέα σημεία ισορροπίας. Ένα άλλο βασικό χαρακτηριστικό των προτεινόμενων μεθόδων διαχείρισης φάσματος πέρα από την ιεραρχική ανάθεση του είναι η δυνατότητα των παρόχων ή ακόμα και των ίδιων των χρηστών που βρίσκονται στο ίδιο επίπεδο να ανταλλάσσουν φάσμα ή να άλληλο εξυπηρετούνται προωθώντας τα δεδομένα τους. Σε αυτές τις αγορές κάθε κόμβος διαδραματίζει ταυτόχρονα και το ρολό του πωλητή αλλά και του πελάτη (πάροχος και χρήστης). Επιπρόσθετα οι δυο αυτοί ρόλοι είναι αλληλένδετοι δεδομένου ότι σχετίζονται με τη κατανάλωση του ίδιου πόρου ήτοι του φάσματος του δικτύου. Σε αυτό το πλαίσιο προτείνουμε ένα μηχανισμό που βασίζεται στις διπλές δημοπρασίες και εξασφαλίζει τη μεγιστοποίηση του οφέλους από τη λειτουργία των εν λόγω αγορών. Με την εφαρμογή κατάλληλων μεθόδων κοστολόγησης και ανάθεσης του φάσματος οι εγωιστικές συμπεριφορές των κόμβων αποτρέπονται και αποκαλύπτονται οι πραγματικές τους απαιτήσεις. Ο προτεινόμενος μηχανισμός δύναται να υλοποιηθεί με κατανεμημένο τρόπο το οποίο αποτελεί μία εξαιρετικά χρήσιμη ιδιότητα για τα σύγχρονα δίκτυα επικοινωνίας. Οι προαναφερθείσες μέθοδοι διαχείρισης δικτυακών πόρων και συγκεκριμένα του φάσματος παρέχουν τα απαιτούμενα κίνητρα για την ορθή και πλήρη εκμετάλλευσή τους. Εξίσου σημαντική για τη βελτίωση της λειτουργίας των δικτύων είναι και η αξιοποίηση πόρων που μέχρι σήμερα δεν έχουν ενταχθεί στη σχεδίαση των δικτύων. Ένα προεξέχων παράδειγμα είναι η αξιοποίηση των αποθηκευτικών πόρων των δικτύων οι οποίοι είναι ιδιαίτερα φθηνοί συγκρινόμενοι με το φάσμα και τη χωρητικότητα των επικοινωνιακών γραμμών και με ελάχιστες απαιτήσεις σε χώρο και κατανάλωση ισχύος. Σε αυτή την εργασία υποστηρίζουμε ότι η αξιοποίηση αποθηκευτικών χωρών στους κόμβους δύναται να αυξήσει τη διαμεταγωγική ικανότητα των δικτύων επικοινωνιών και προσδιορίζουμε τις συνθήκες υπό τις οποίες αυτή η αύξηση είναι εφικτή. Εισάγουμε μια μεθοδολογία η οποία προσδιορίζει σε ποιους ακριβώς κόμβους ενός δικτύου απαιτείται να προστεθεί χωρητικότητα αποθήκευσης. Επιπλέον προτείνουμε τεχνικές κοινής διαχείρισης των αποθηκευτικών χωρών και δρομολόγησης δεδομένων σε αυτά τα δίκτυα οι οποίες εξασφαλίζουν τη μεγιστοποίηση της ροής δεδομένων. Ακολούθως εξετάζουμε το πρόβλημα ταυτόχρονης μεταφοράς διαφορετικού τύπου δεδομένων όπως για παράδειγμα διαφορετικών αρχείων και την παράδοσή τους στους αντίστοιχους προορισμούς τους με τη μικρότερη δυνατή συνολική καθυστέρηση. Εξαιτίας των συχνά περιορισμένων δικτυακών πόρων απαιτείται η ιεράρχηση των δεδομένων - αρχείων ανάλογα με την προτεραιότητά τους και η σχεδίαση πολιτικών αποθήκευσης - δρομολόγησης που εξασφαλίζουν την εξυπηρέτηση τους κατά αντιστοιχία.