Θεωρία ισοδύναμης χωρητικότητας για μοντελοποίηση εξυπηρετητών μεταβλητού ρυθμού και εφαρμογές σε ασύρματα δίκτυα ΙΕΕΕ 802.11

Abstract

Many demanding network applications rely on stochastic Quality of Service (QoS) guarantees. The provision of such guarantees has motivated the application of the theory of Effective Bandwidth and Effective Capacity to the calculation and enforcement of delay-related QoS. However, up to now this application has only been justified on the basis of heuristic arguments when the queue is served at a variable rate. The thesis fills this gap, by formally establishing that the Effective Bandwidth/Capacity theory may be applied for asymptotically correct calculation and/or enforcement of delay tail-probabilities in systems with variable rate servers. In particular, the heuristically suggested linkage between the exponential decay rates of the buffer content and delay probability tails through the server's Effective Capacity function is formally shown to apply. Due to the prevalence of wireless networking, systems with time-varying servers are becoming all the more important. Indeed, a wireless station can be regarded as a time-varying data server, due to rate fluctuations at the physical or at the medium access control layer. In this context, the thesis proceeds with an application of the general results to ΙEEE 802.11 WLANs. In doing so, the thesis first establishes that an IEEE 802.11 mobile station can be regarded as a Semi-Markovian data server of the On/Off type, with known distributions for the On and Off periods, and subsequently derives the Effective Capacity function of this On/Off server. The general results can then be used for computing buffer overflow and delay violation probabilities in IEEE 802.11 WLANs, and for employing simple traffic control policies to enforce related QoS guarantees. Finally, the thesis illustrates the usage of the Effective Capacity function of the IEEE 802.11 stations as a design tool: Towards this end, the form of the said function highlights certain parameters of the backoff window distributions, which, if appropriately tailored, may lead to higher Effective Capacity values, hence to better delay-related (or loss-related) performance.

Πολλές απαιτητικές δικτυακές εφαρμογές επιζητούν στοχαστικές εγγυήσεις ποιότητας υπηρεσίας. Το γεγονός αυτό ώθησε στην εφαρμογή της θεωρίας του Ισοδύναμου Εύρους Ζώνης και της Ισοδύναμης Χωρητικότητας για τον υπολογισμό ή/και τη διασφάλιση χρονικών εγγυήσεων ποιότητας υπηρεσίας. Ωστόσο, μέχρι σήμερα αυτή η εφαρμογή σε συστήματα αναμονής με χρονικά μεταβαλλόμενο ρυθμό εξυπηρέτησης επικαλούνταν μόνο ευριστικά επιχειρήματα. Η παρούσα διατριβή καλύπτει αυτό το κενό, θεμελιώνοντας αυστηρά τη χρήση της θεωρίας του Ισοδύναμου Εύρους Ζώνης και της Ισοδύναμης Χωρητικότητας για τον ασυμπτωτικά ακριβή υπολογισμό ή/και τη διασφάλιση της πιθανότητας η καθυστέρηση να υπερβεί ένα δοσμένο κατώφλι σε συστήματα αναμονής με μεταβαλλόμενο ρυθμό εξυπηρέτησης. Ειδικότερα, η διατριβή αποδεικνύει αυστηρά την ευρέως χρησιμοποιούμενη ευριστική σχέση μεταξύ των εκθετικών ρυθμών φθίσης των πιθανοτήτων υπέρβασης του περιεχομένου ενός ταμιευτήρα και των πιθανοτήτων υπέρβασης της καθυστέρησης σε αυτόν. Η μελέτη των συστημάτων αναμονής με χρονικά μεταβαλλόμενους εξυπηρετητές καθίσταται ολοένα και πιο σημαντική στις μέρες μας, λόγω της εξάπλωσης της ασύρματης δικτύωσης. Ακολουθώντας αυτήν τη συλλογιστική, η διατριβή εφαρμόζει τα γενικά αποτελέσματα της θεωρίας του Ισοδύναμου Εύρους Ζώνης και της Ισοδύναμης Χωρητικότητας στο πρότυπο ασύρματης τοπικής δικτύωσης ΙΕΕΕ 802.11. Προς αυτήν την κατεύθυνση, η διατριβή αποδεικνύει ότι ένα τερματικό ΙΕΕΕ 802.11 μπορεί να μοντελοποιηθεί ως ένας Ημί-Μαρκοβιανός εξυπηρετητής δεδομένων του τύπου On/Off, με γνωστές κατανομές για τις περιόδους On και Off, και στη συνέχεια υπολογίζει τη συνάρτηση Ισοδύναμης Χωρητικότητας αυτού του εξυπηρετητή On/Off. Τα παραχθέντα γενικά αποτελέσματα χρησιμοποιούνται για την εκτίμηση της πιθανότητας υπερχείλισης του ταμιευτήρα MAC ΙΕΕΕ 802.11, καθώς και της πιθανότητας η καθυστέρηση σε αυτόν να παραβιάσει ένα δοσμένο χρονικό όριο. Τα γενικά αποτελέσματα επιπλέον οδηγούν στη δημιουργία απλών πολιτικών ελέγχου κίνησης, προκειμένου να επιβληθούν οι σχετικές εγγυήσεις ποιότητας υπηρεσίας. Τελειώνοντας, η διατριβή παρουσιάζει τη χρήση της συνάρτησης Ισοδύναμης Χωρητικότητας των τερματικών ΙΕΕΕ 802.11 ως εργαλείου σχεδιασμού: Η μορφή της εν λόγω συνάρτησης υποδεικνύει συγκεκριμένες παραμέτρους των κατανομών οπισθοχώρησης, οι οποίες, εάν τροποποιηθούν καταλλήλως, οδηγούν σε μεγαλύτερες τιμές Ισοδύναμης Χωρητικότητας. Συνεπώς, σε καλύτερη επίδοση καθυστέρησης και σε καλύτερη επίδοση απωλειών πακέτων.