| Περίληψη |
Η ραγδαία ανάπτυξη του Διαδικτύου (Internet) τα τελευταία χρόνια συνεπάγεται τη συνεχώς αυξανόμενη ανάγκη για εύρος ζώνης τόσο στα σημεία πρόσβασης του τελικού χρήστη στο δίκτυο, όσο και στο δικτυακό κορμό. Λόγω ανταγωνισμού, οι πάροχοι των σταθερών δικτύων είναι αναγκασμένοι πλέον να προσφέρουν συμβόλαια για μικρές χρονικές κλίμακες σε ανταγωνιστικές τιμές, οι οποίες ταυτόχρονα να αντικατοπτρίζουν το φόρτο του δικτύου τους και τη ζήτηση της αγοράς για τις υπηρεσίες τους. Έτσι, υπάρχει ολοένα αυξανόμενο ενδιαφέρον για νέα δυναμικά συστήματα αγοραπωλησίας εύρους ζώνης καθώς και αποτελεσματικότερων τρόπων διαχείρισης και χρέωσης των δικτυακών πόρων. Παράλληλα, η αλματώδης ανάπτυξη των ασύρματων δικτύων, συμπεριλαμβανομένων των κυψελοειδών, και η αύξηση της ζήτησης των αντιστοίχων υπηρεσιών, έχει οδηγήσει σε ιδιαιτέρως έντονη ζήτηση για δέσμευση φάσματος σε συγκεκριμένες ζώνες συχνοτήτων, προκειμένου να καταστεί εφικτή η παροχή των υπηρεσιών 2ης (GSM), 2,5 (GPRS) και 3ης γενεάς (UMTS). Το διαθέσιμο φάσμα του ασυρμάτου δικτύου πρόσβασης (Radio Access Network) των δικτύων αυτών είναι εξαιρετικά περιορισμένο. Αντίθετα, οι νέες υπηρεσίες που θα εξυπηρετούνται από τα δίκτυα αυτά, έχουν σημαντικά υψηλότερες απαιτήσεις από τα δίκτυα 2ης γενεάς: Τα μηνύματα με πολυμεσικό περιεχόμενο (MMS) αντικαθιστούν τα σύντομα γραπτά μηνύματα (SMS), ενώ η μετάδοση φωνής συνυπάρχει με τη μετάδοση φωτογραφιών, αρχείων και video σε πολλαπλάσιους ρυθμούς μετάδοσης. Οι υπηρεσίες αυτές έχουν χρονική διάρκεια κατά πολλές τάξεις μεγέθους μεγαλύτερη από αυτή στην οποία δεσμεύει πόρους το δίκτυο (π.χ. τα UMTS frames έχουν διάρκεια 10 msec). Παράλληλα, η μελλοντική σύγκλιση των ανωτέρω τεχνολογιών με άλλες τεχνολογίες πρόσβασης και η δυνατότητα εξυπηρέτησης πολυμετάδοσης (multicast), κάνουν το τηλεπικοινωνιακό περιβάλλον ακόμα πιο δυναμικό. Από τα παραπάνω, γίνεται φανερό ότι είναι απαραίτητη η εφαρμογή μηχανισμών δέσμευσης πόρων και χρέωσης αυτών οι οποίοι να είναι κατάλληλοι για αυτό το δυναμικό τηλεπικοινωνιακό περιβάλλον. Ένας πολύ δημοφιλής τρόπος ανταλλαγής αγαθών για δυναμικές οικονομίες, ο οποίος βασίζεται στην έννοια του ανταγωνισμού, είναι οι δημοπρασίες (auctions). Οι δημοπρασίες εν γένει παρέχουν έναν απλό, ταχύ και διαφανή μηχανισμό καθορισμού των τιμών των διαφόρων αγαθών. Το πλέον χαρακτηριστικό και επιτυχημένο δείγμα εφαρμογής τέτοιου μηχανισμού αποτελεί η δημοπρασία τύπου FCC που χρησιμοποιήθηκε για την εκχώρηση ζωνών φάσματος σε εταιρείες κινητής τηλεφωνίας. Αντικείμενο της παρούσας διδακτορικής διατριβής αποτελεί η χρήση δημοπρασιών για την εκχώρηση δικτυακών πόρων.Αρχικά, πραγματοποιείται λεπτομερής μελέτη της δημοπρασίας τύπου FCC. Συγκεκριμένα, παρουσιάζονται οι βασικές στρατηγικές παικτών που εφαρμόσθηκαν στην πράξη σε δημοπρασίες τέτοιου τύπου. Στη βιβλιογραφία, για την περιγραφή των στρατηγικών των παικτών, χρησιμοποιούνται ασαφείς όροι οι οποίοι καθιστούν απαραίτητη την ύπαρξη μιας κοινής και αυστηρής γλώσσας για τον καθορισμό τέτοιων στρατηγικών. Γι’ αυτό το λόγο στην παρούσα διατριβή προτείνεται μια τέτοια «γλώσσα», μία κανονική LR(1) γραμματική. Η επιλογή αυτή εξασφαλίζει την αυστηρότητα και πληρότητα της περιγραφής και την αναγνωσιμότητα της στρατηγικής ακόμα και από απλά προγράμματα (αυτόματα). Παράλληλα, η εν λόγω δημοπρασία χαρακτηρίζεται από έλλειψη προδιαγεγραμμένου σημείου ισορροπίας Nash στο οποίο πρόκειται να καταλήξει. Επομένως, η προδιαγραφή μιας επιτυχημένης στρατηγικής είναι ιδιαίτερα σημαντική, γι’ αυτό προτείνεται και αποτιμάται μια τέτοια στρατηγική. Τέλος, έχει υλοποιηθεί και μια πλατφόρμα λογισμικού η οποία επιτρέπει τη διεξαγωγή τέτοιου τύπου δημοπρασιών για εκπαιδευτικούς λόγους ή για τη διερεύνηση της αποτελεσματικότητας των στρατηγικών κάτω από μια πλειάδα συνθηκών αγοράς. Επίσης, παρέχει λειτουργίες συστήματος στήριξης αποφάσεων σε παίκτες που συμμετέχουν στη δημοπρασία ως προς τις προσφορές οι οποίες πρέπει να υποβληθούν βάσει μιας προκαθορισμένης στρατηγικής. Το επίκαιρο πρόβλημα της δέσμευσης πόρων σε σταθερά δίκτυα γενικής τοπολογίας μέσω δημοπρασιών επίσης αποτελεί αντικείμενο μελέτης της παρούσας διατριβής. Συγκεκριμένα, παρουσιάζεται και αναλύεται ο μηχανισμός MIDAS ο οποίος είχε σε αρχική μορφή εισαχθεί σε προηγούμενη εργασία. Πρόκειται για ένα μηχανισμό δημοπράτησης του εύρους ζώνης δικτύων και βασίζεται στη διεξαγωγή ταυτόχρονων δημοπρασιών μειούμενης τιμής (δηλαδή Ολλανδικών δημοπρασιών) πολλαπλών μονάδων σε κάθε σύνδεσμο του δικτύου. Το εύρος ζώνης όλων των συνδέσμων ενός δικτύου δημοπρατείται περιοδικά και εκχωρείται στους νικητές της δημοπρασίας για μία συγκεκριμένη χρονική περίοδο. Πρωταρχικός σκοπός του μηχανισμού MIDAS είναι η εκχώρηση του εύρους ζώνης στους χρήστες του δικτύου που το αποτιμούν περισσότερο, δηλαδή η μεγιστοποίηση της κοινωνικής ευημερίας. Ο μηχανισμός παρέχει τα κατάλληλα κίνητρα στους παίκτες ώστε οι τελευταίοι να αποστέλλουν ειλικρινείς προσφορές (truthful bids). Δεδομένης αυτής της ιδιότητας συμβατότητας κινήτρων, στην παρούσα διατριβή αποδεικνύεται ότι ο μηχανισμός MIDAS αποδίδει το εύρος ζώνης βέλτιστα σε όλο το δίκτυο αν ο δημοπράτης διαθέτει πλήρη πληροφόρηση (full information) για τη ζήτηση. Εάν διαθέτει μερική πληροφόρηση, αποδεικνύεται ότι και πάλι η εκχώρηση του εύρους ζώνης γίνεται με τέτοιο τρόπο ώστε η τιμή της επαγόμενης κοινωνικής ευημερίας να είναι κοντά στη μέγιστη δυνατή. Επίσης, ο μηχανισμός μπορεί να επιτύχει μεγιστοποίηση των εσόδων του πωλητή, αν δεν πωληθεί ολόκληρη η διαθέσιμη ποσότητα εύρους ζώνης του δικτύου. Η πολυπλοκότητα του προβλήματος της ακριβώς βέλτιστης (ως προς τη μεγιστοποίηση της κοινωνικής ευημερίας) εκχώρησης του εύρους ζώνης είναι NP-hard. Το μέγιστο απαιτούμενο πλήθος βημάτων εκτέλεσης του εν λόγω μηχανισμού είναι μικρό και ανεξάρτητο του πλήθους των χρηστών και συνδέσμων του δικτύου. Με αυτόν τον τρόπο, ο μηχανισμός MIDAS αποτελεί μια γρήγορη σχεδόν βέλτιστη λύση σε ένα εν γένει πολύπλοκο (NP-hard) πρόβλημα βελτιστοποίησης.Η μεγάλη ανάπτυξη των ασύρματων κυψελοειδών δικτύων 3ης γενεάς σε συνδυασμό με την αυξανόμενη ανάγκη για ορθή και αποτελεσματική διαχείριση του περιορισμένου φάσματος του ασύρματου δικτύου πρόσβασης καθιστά ιδιαίτερα επίκαιρη τη μελέτη της εκχώρησης των πόρων μέσω δημοπρασιών. Στην παρούσα διατριβή προτείνεται ο μηχανισμός ATHENA: Πρόκειται για ένα μηχανισμό εκχώρησης πόρων για ένα δίκτυο 3ης γενεάς-UMTS με τέτοιο τρόπο ώστε οι δικτυακοί πόροι να μοιράζονται κατά οικονομικά βέλτιστο τρόπο ανάμεσα στους πελάτες και η χρέωση να αντικατοπτρίζει το φόρτο του δικτύου. Ο μηχανισμός ο οποίος προτείνεται αποτελείται από α) μια σειρά επαναλαμβανόμενων δημοπρασιών πολλαπλών μονάδων τύπου Generalized Vickrey Auction, μία για κάθε χρονοθυρίδα, και β) προκαθορισμένες συναρτήσεις αυτόματης υποβολής προσφορών στις ανωτέρω δημοπρασίες, οι οποίες επιλέγονται και παραμετροποιούνται από το χρήστη. Οι συναρτήσεις αυτές εκφράζουν τις προτιμήσεις χρηστών με απαίτηση για σταθερό ρυθμό μετάδοσης δεδομένων τύπου CBR όσον αφορά στις μορφές εκχώρησης των πόρων όταν η συνεπής εκχώρηση του ρυθμού αυτού δεν είναι εφικτή και λαμβάνουν υπ’ όψιν το ιστορικό της εκχώρησης πόρων στην παρούσα σύνοδο του χρήστη. Αυτό το γεγονός αποτελεί μια πρωτότυπη συμβολή της παρούσας διατριβής, η οποία μάλιστα έχει υιοθετηθεί εσχάτως και από άλλους ερευνητές. Η πειραματική αποτίμηση του μηχανισμού καταδεικνύει ότι ο μηχανισμός ATHENA έχει τη σημαντική ιδιότητα ότι η πλειονότητα των μορφών εκχώρησης των πόρων των χρηστών είτε είναι σχεδόν συνεπείς είτε περιλαμβάνουν εξαιρετικά περιορισμένες ποσότητες μονάδων πόρων για τις οποίες ο χρήστης χρεώνεται ελάχιστα. Ο μηχανισμός παρέχει τα ορθά κίνητρα στους παίκτες για τη χρήση του δικτύου. Ο μηχανισμός αποτιμάται τόσο θεωρητικά μέσω παιγνιοθεωρητικής ανάλυσης, όσο και πειραματικά μέσω λογισμικού που υλοποιήθηκε γι’ αυτόν το σκοπό. Επίσης, πραγματοποιείται η συγκριτική αποτίμηση του μηχανισμού με δύο διαδεδομένες μη οικονομικές πολιτικές εκχώρησης πόρων, τον αλγόριθμο κυκλικής εκχώρησης πόρων (Round Robin) και τον αλγόριθμο εξυπηρέτησης κατά σειρά άφιξης (First Come First Served) ως προς την ικανοποίηση των χρηστών από τις ληφθείσες υπηρεσίες. Η πειραματική αποτίμηση καταδεικνύει ότι ο προτεινόμενος μηχανισμός δημοπρασίας είναι σαφώς προτιμότερος τόσο από τον αλγόριθμο Round Robin ο οποίος συνεπάγεται πολλές ενδιάμεσες μορφές εκχώρησης πόρων, όσο και από τον FCFS λόγω της μεγάλης καθυστέρησης εισόδου στο δίκτυο και της χαμηλότερης επαγόμενης κοινωνικής ευημερίαςΠαράλληλα, πραγματοποιήθηκε ανάλυση μεταβατικών φαινομένων του μηχανισμού ATHENA και της συντελούμενης απόδοσης πόρων στους νικητές μέσω του ορισμού και της ανάλυσης ενός θεωρητικού υποδείγματος τυχαίου περιπάτου που αντιστοιχεί στην αυξομείωση της τιμής κατωφλιού της δημοπρασίας. Το υπόδειγμα χρησιμοποιείται για να αναλυθούν οι προκύπτουσες μορφές εκχώρησης πόρων για παίκτες των οποίων η οριακή χρησιμότητα και συνακόλουθα η αποστελλόμενη προσφορά στη δημοπρασία παραμένει σταθερή όσο ο παίκτης κερδίζει, ενώ μειώνεται εκθετικά με το χρόνο όταν η τιμή κατωφλιού της δημοπρασίας είναι μεγαλύτερη από αυτήν. Συγκεκριμένα, για έναν εν γένει ανταγωνιστικό παίκτη μελετώνται: α) Η πιθανότητα, δεδομένου του ότι έχασε σε κάποια δημοπρασία, να ξανακερδίσει κάποια στιγμή στο μέλλον, και β) το αναμενόμενο πλήθος των δημοπρασιών στις οποίες οι προσφορές του παίκτη δεν θα υπερβαίνουν την τιμή της δημοπρασίας. Χρησιμοποιώντας το υπόδειγμα αυτό, κάθε παίκτης της δημοπρασίας δύναται να εξετάσει την επίδραση της τιμής του παράγοντα εκθετικής μείωσης της συνάρτησης υποβολής προσφορών του στην αναμενόμενη ποιότητα υπηρεσίας. Τέλος καθορίζεται πώς μπορεί να επεκταθεί ο μηχανισμός ΑΤΗΕΝΑ ώστε να υποστηρίζει τη δημοπράτηση πόρων και για συνδέσεις πολυμετάδοσης. Συγκεκριμένα, εξετάζονται οι ιδιότητες του εν λόγω μηχανισμού όταν οι ανταγωνιζόμενες ροές δεν είναι μόνο ατομικές ροές χρηστών (unicast flows), αλλά παρέχεται και η δυνατότητα εξυπηρέτησης ροών πολυμετάδοσης (multicast flows), των οποίων εξετάζεται η επίδραση στην κοινωνική ευημερία και στα έσοδα του πωλητή. Η ανάλυση αυτή εστιάζει στην περίπτωση κατά την οποία οι συμμετέχοντες έχουν σημαντικές διαφορές ως προς το χρηματικό ποσό το οποίο είναι διατεθειμένοι να καταβάλλουν για την υπηρεσία (wealth asymmetry). Επίσης εξετάζεται η επίπτωση της πολυμετάδοσης στις μορφές εκχώρησης πόρων των χρηστών. Προκύπτει ότι η πολυμετάδοση βελτιώνει την κοινωνική ευημερία και σε πολλές περιπτώσεις και τα έσοδα. Συνοψίζοντας, η παρούσα διδακτορική διατριβή αποτελεί μία μελέτη δυνατότητας εφαρμογής οικονομικών μηχανισμών και ιδιαίτερα δημοπρασιών για την εκχώρηση των πόρων σταθερών και κυψελοειδών δικτύων στους ανταγωνιζόμενους χρήστες τους. Προτείνονται και μελετώνται οικονομικοί μηχανισμοί για διάφορα προβλήματα με θεωρητικό ενδιαφέρον αλλά και πρακτική σημασία. Μέσω θεωρητικής και πειραματικής αποτίμησης αποδεικνύεται ότι οι μηχανισμοί αυτοί αποτελούν ταχείς, αποδοτικές, και πρακτικά εφαρμόσιμες λύσεις.
The impressive growth of Internet over the past years has resulted in constantly increasing demand for bandwidth. This is evident both at the network edges, where users access the network and at the backbone. Due to competition, the network providers of these fixed topology networks now have to provide short-term and customized contracts, whose charge reflects the network load. Hence, there is increased interest in new dynamic bandwidth trading mechanisms and more efficient ways of managing and charging the network resources. Also, the large growth of wireless networks, including the cellular networks, combined with the increasing demand for services, has resulted in increasing demand for the reservation of spectrum; this spectrum is required in order for these networks to provide 2nd (GSM), 2,5 (GPRS) and 3rd (UMTS) generation services. The spectrum of the Radio Access Network is a scarce resource for these networks. At the same time, the 3G services are extremely more demanding than those of 2G networks: Multimedia messages (MMS) replace the short text messages (SMS), while voice calls must still be accommodated along with data (e.g. photo, video, file transfers) services of much higher data rates. Moreover, the duration of these services is orders of magnitude larger than that of the network slots where resources are allocated (e.g. the duration of a UMTS frame is 10 msec). Finaly, the future convergence of the aforementioned technologies with other mobile network technologies and the potential introduction of multicast services also contribute to the dynamic nature of the telecommunications environment. The aforementioned discussion suggests that new resource allocation and charging mechanisms are needed in this dynamic context. To this end, auctions appear to be the proper trading mechanism. Auctions are very popular in such dynamic economic environments, since they provide a simple, fast and transparent means of determining the price of goods. The most prominent and successful example of applying auctions is the FCC-type auction, which was used by the Federal Communications Commission of USA to allocate radio spectrum to wireless service providers. The subject of this Ph.D. thesis is the use of auctions for resource allocation in networks.Initially, a thorough study of the FCC-type auctions is conducted. In particular, the prominent bidding strategies that were observed in practice are presented. These strategies are described in the related bibliography in abstract and obscure terms. Therefore, a formal language for describing FCC-type auctions bidding strategies is needed. In this dissertation, such a “language”, namely an LR(1) grammar, is introduced. This approach leads to a simple yet formal and complete description of the bidding strategies: simple programs (automata) can parse and read such a strategy. Moreover, it is impossible to predict a unique Nash equilibrium for this auction. Therefore, prescribing a successful strategy is very important. Such a strategy is proposed and evaluated in the present dissertation. Finally, special software has been developed for running such auctions either for educational purposes or for investigating the effectiveness of various strategies under a variety of market conditions. Moreover, the software includes Decision Support functionality for bidders, i.e. provides suggestions on the bids that are best to be submitted in the auction, on the basis of user’s selection of a predefined bidding strategy. The problem of auction-based resource allocation in fixed networks of arbitrary topology is also analyzed in this dissertation. In particular, the MIDAS mechanism is presented and analyzed. This mechanism had been introduced in a previous work and is an auction mechanism used to allocate the bandwidth of networks to its users. It is based on conducting simultaneous multi-unit descending-price (i.e. Dutch) auctions, one per link. The bandwidth of all links is auctioned periodically and assigned to users for a certain predefined time period. The mechanism’s primary objective is allocating the bandwidth to the users who need it the most, i.e. social welfare maximization. The mechanism provides proper incentives to users to bid truthfully. Given this incentive compatibility property, it is proved in this dissertation that MIDAS allocates the network bandwidth efficiently if the auctioneer has full information on market demand. If only imperfect information is available, it is proved that the bandwidth is allocated in a way that the value of the attained social welfare is close to the maximum. Moreover, the mechanism can maximize the provider’s revenue, if less than the entire quantity of bandwidth is sold. The complexity of the problem of computing the optimal (with respect to social welfare maximization) bandwidth allocation is NP-hard. The maximum required number of the proposed auction’s execution is small and independent of the number of the network’s links and competing users. This way, MIDAS serves as a fast, practical and near-optimal solution to a generally NP-hard optimization problem.The growth of 3rd generation cellular networks, combined with the increased demand for rational and efficient management of the scarce radio spectrum motivate the use of auction-based network resource allocation in such networks. To this end, ATHENA mechanism is proposed in this dissertation: This is an auction-based mechanism that allocates the network resources efficiently among the competing users and for a respective charge that reflects the network load. This mechanism consists of: a) a series of multi-unit Generalized Vickrey Auctions, one per time-slot, and b) predefined bidding functions, that are selected and parameterized by the users. These functions express the preferences of users requiring a constant bit-rate with respect to the preferred resource allocation pattern when it is infeasible for the network to consistently allocate to them their desired rate throughout their service time. These functions are dependent on the history of resource allocations in the present service session. This constitutes an original contribution of this dissertation, which has been recently adopted by other researchers as well. The experimental assessment of the mechanism indicates that the ATHENA mechanism has an important property: The majority of the user resource allocation patterns are either almost perfectly consistent or consist of very limited resources for a very low charge. The mechanism provides proper incentives to users for the rational usage of the network. The mechanism is evaluated by game-theoretic analysis as well as by experimental assessment by means of special software that was developed for this purpose. Also, a comparison of the auction with two popular non-economic resource allocation algorithms, namely Round Robin and First Come First Served, is conducted, with respect to the user’s satisfaction from the service obtained. This experimental assessment indicates that the proposed mechanism is more preferable to the Round Robin, which results in many intermediate resource allocation patterns, and the FCFS, since the latter results in high delays for the users to receive service and low attained social welfare. Moreover, a random walk model was introduced for the purpose of transient analysis and study of the user attained resource allocation patterns in the ATHENA mechanism. . This model is used to describe the auction’s cut-off price fluctuations. It is used in order to analyze the resource allocation patterns a user attains in the auction, assuming that his marginal utility remains constant as long as he is winning at the auction, while it decreases exponentially in time when his bid is topped by the auction cut-off price. In particular, for a competitive user, the following quantities are studied: a) The probability that given the user lost in some auction, he will win again at some time in the future, and b) the expected number of auctions at which the user’s bid will remain below the auction cut-off price. Using this model, a bidder may investigate the effect that the exponential-discount factor of his bidding function has on the expected user-perceived quality of service. Finally, the extension of ΑΤΗΕΝΑ mechanism when multicast sessions are supported is also analyzed. In particular, the mechanism’s properties are examined when the competing flows are not only unicast, but multicast flows are served as well. The impact of multicast on social welfare and provider’s revenue is investigated. This study focuses to a setting where the competing users have significantly different willingness-to-pay for the service (wealth asymmetry). The impact of multicast in users’ resource allocation patterns is also examined. It is concluded that multicast improves the social welfare attained and in many cases the provider’s revenue as well. Concluding, this Ph.D. thesis analyzes the application of economic, and in particular, of auction mechanisms for resource allocation in both fixed and wireless networks. Economic mechanisms are proposed and evaluated for several problems of both theoretical interest and practical importance. It is proved by means of game-theoretic analysis and experimental assessment that these mechanisms are fast, efficient and practically applicable solutions to these problems.
|
