This item is provided by the institution :

Repository :
E-Locus Institutional Repository
see the original item page
in the repository's web site and access all digital files if the item*

2000 (EN)
Ένας μηχανισμός δημοπρασίας για δέσμευση εύρους ζώνης σε μονοπάτια ενός δικτύου
An Auction Mechanism for Bandwidth Allocation Over Paths

Δραμιτινός, Μάνος Π (EL)
Dramitinos, Manos P (EN)

Η ζήτηση για εύρος ζώνης συνεχώς αυξάνει λόγω της ανάπτυξης του Διαδικτύου. Τα παραδοσιακά, μακροχρόνια, στατικά συμβόλαια εύρους ζώνης δεν είναι όμως πλέον δημοφιλή. Οι χρήστες τώρα απαιτούν βραχυχρόνια, μη τυποποιημένα και οικονομικά συμβόλαια. Προς αυτήν την κατεύθυνση, οι δημοπρασίες παρουσιάζονται ως ο πλέον κατάλληλος ανταλλακτικός μηχανισμός πώλησης. Πράγματι, όταν είναι κατάλληλα σχεδιασμένες, οι δημοπρασίες παρέχουν έναν ταχύ, απλό και δίκαιο τρόπο αγοραπωλησίας εύρους ζώνης σε διεσπαρμένους και ετερογενείς πληθυσμούς (όπως χρήστες διασυνδεόμενοι μέσω του Διαδικτύου) των οποίων η ζήτηση δεν είναι ακριβώς γνωστή, οδηγώντας σε ένα διαφανή τρόπο καθορισμού των τιμών ο οποίος συνοδεύεται από την δημιουργία σημαντικών εσόδων για τον πωλητή. Για την αγορά εύρους ζώνης σε ένα μονοπάτι του δικτύου, έχει μόνο νόημα για έναν χρήστη η δέσμευση του ίδιου ποσού σε όλους τους συνδέσμους που συναποτελούν το μονοπάτι του. Μια προσέγγιση που επιτυγχάνει αυτό είναι η διεξαγωγή συνδυαστικής δημοπρασίας. Είναι όμως γνωστό ότι η ανάδειξη των νικητών σε μια τέτοια δημοπρασία είναι γενικά εξαιρετικά πολύπλοκη και πιθανώς αποτελεί NP-complete πρόβλημα. Στην παρούσα εργασία έχει σχεδιασθεί, υλοποιηθεί και αποτιμηθεί ένας απλός, αλλά αποδοτικός μηχανισμός δημοπρασίας για τη δέσμευση εύρους ζώνης σε ένα δίκτυο. Αυτός αποτελείται από ταυτόχρονες Ολλανδικές δημοπρασίες πολλών μονάδων, (δηλαδή δημοπρασίες με μειούμενη τιμή), μία για κάθε σύνδεσμο του δικτύου. Προκειμένου ένας χρήστης να δεσμεύσει εύρος ζώνης σε ένα μονοπάτι, αρκεί η ταυτόχρονη αποστολή προσφοράς με την επιθυμητή ποσότητα σε όλες τις σχετικές δημοπρασίες. Ακολουθεί η άμεση απόδοση των πόρων στον χρήστη. Ο χρήστης πληρώνει για κάθε μονάδα εύρους ζώνης το άθροισμα των μοναδιαίων τιμών των συνδέσμων κατά την χρονική στιγμή αποστολής της προσφοράς του. Η στρατηγική χρήστη βασίζεται στην μοναδιαία τιμή εύρους ζώνης και τη διαθέσιμη χωρητικότητα ανά σύνδεσμο, οι οποίες αποστέλλονται ως ανάδραση στους παίκτες. Στα πλαίσια του μηχανισμού της παρούσας εργασίας, οι τιμές στους συνδέσμους μειώνονται με διαφορετικούς ρυθμούς, ακολουθώντας τέτοιους κανόνες ώστε οι τιμές αντανακλούν την εκπεφρασμένη ζήτηση για κάθε σύνδεσμο. Έτσι, οι πιο δημοφιλείς σύνδεσμοι είναι ακριβότεροι, το οποίο είναι δίκαιο από οικονομικής πλευράς και συντελεί στη σημαντική βελτίωση της κοινωνικής ευημερίας που αντιστοιχεί στην τελική απόδοση εύρους ζώνης. Τρεις πολιτικές μεταβολής τιμών έχουν αναπτυχθεί και αξιολογηθεί και πειραματικά, σε σχέση με την προκύπτουσα κοινωνική ευημερία. Αποδεικνύεται τόσο θεωρητικά όσο και με πειραματικά αποτελέσματα, ότι η εισαγωγή τέτοιων κανόνων είναι όντως αποδοτική, σε αντίθεση με την ομοιόμορφη πτώση των τιμών. Τέλος, το θέμα της ορθής χρέωσης εξετάζεται, με την εισαγωγή ενός κανόνα χρέωσης τύπου Vickrey, ο οποίος παρέχει το κίνητρο στους παίκτες να αποκαλύπτουν με ειλικρίνεια τις αξιολογήσεις τους σε διάφορες ενδιαφέρουσες περιπτώσεις. Παράλληλα με το θεωρητικό τμήμα της εργασίας, έχει αναπτυχθεί ειδικό λογισμικό το οποίο υλοποιεί τον αναπτυχθέντα μηχανισμό και επίσης άλλους δημοφιλείς μηχανισμούς. Στην εργασία αυτή παρουσιάζεται η αρχιτεκτονική του λογισμικού καθώς και επιλογές που αφορούν παραμέτρους των μηχανισμών ώστε η υλοποιημένη μορφή τους να παραμείνει θεωρητικά ορθή. (EL)
The demand for bandwidth contracts over networks has recently been growing very rapidly. However, traditional, long-term, static bandwidth contracts are no longer popular. Users now demand short-term, customized and affordable contracts. To this end, auctions appear to be the proper trading mechanism. Indeed, when appropriately designed, auctions can provide fast, simple and fair trading of bandwidth to populations of highly scattered and heterogeneous users (such as Internet-connected users) whose demand is not accurately known, thus resulting in transparent setting of prices and good revenues for the seller. When purchasing bandwidth over a path, it is only meaningful for a user to reserve the same amount in all links. One approach to guarantee this is to perform a combinatorial auction. However, it is well known that winner determination in this case can be complicated and possibly NP-complete. In the present thesis, a simple, yet efficient auction mechanism for allocating bandwidth on a network basis has been designed, implemented and evaluated. This mechanism consists of a set of simultaneous multi-unit Dutch (descending-price) auctions, one per link of the network. In order for a user to win bandwidth over a certain path, it suffices to simultaneously bid for the quantity desired at all relevant auctions. Thus, instant allocation is attained. The user then pays for each unit of bandwidth the sum of prices over the links of the path at the instant where the bid was submitted. User strategies can be based on the price per unit of bandwidth and the spare capacity of the various links, which are sent as feedback to users. An important feature of this approach is that prices at the various links drop at different rates, following rules specified so that prices reflect the demand exhibited so far for each link. Thus, more popular links are in general more expensive, which is fair from an economic point of view and may lead to improved social welfare. Three price-dropping policies have been developed, implemented and evaluated experimentally, in terms of the social welfare associated with the resulting allocation. It is argued, both theoretically and by means of experiments, that it is indeed efficient to introduce such rules rather than drop all prices at the same rate. Finally, the issue of incentive compatible pricing is addressed, by introducing a Vickrey-type pricing rule, which is incentive compatible in certain interesting cases. Besides the theoretical part of this thesis, special software has been developed that implements the mechanism designed and encapsulates some other popular auction mechanisms. These implementations have required certain modifications of the mechanisms as prescribed in theory, which were performed so that theoretical soundness of the mechanism is maintained. (EN)

Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης


Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης

*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)