QoS provisioning in Queueing Systems: a perturbation analysis of stochastic fluid models approach

Abstract

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

Motivated by the problem of Quality of Service (QoS) provisioning in communication networks, this Ph.D. Thesis aims to provide a framework for dynamically controlling network parameters such that the QoS requirements are met. For the analysis, a Stochastic Fluid Model (SFM) is adopted and the sensitivity estimators of various metrics (e.g. Workload, Loss Probability and Throughput) with respect to the parameter of interest (buffer size, arrival process) are derived using Infinitesimal Perturbation Analysis (IPA) technique; in each case, the estimator's unbiasedness is also shown. Subsequently, the sensitivity estimators are evaluated based on information obtained from the sample path of the “real” Discrete Event System (DES). The estimators’ advantages are: (i) unbiasedness (ii) ability to estimate directly (iii) ease of implementation and (iv) model independence. Hence, one can use these estimators together with stochastic approximation techniques in order to maintain the system at an optimum or near optimum point despite any changes network conditions. The contribution of this Thesis is that it provides the means for optimization and control in queueing systems that are widely used today in various areas such as communications, manufacturing and transportation systems with emphasis given in communication networks’ applications. Using the SFM/IPA framework, sensitivity estimators of several performance measures are derived with respect to a control parameter for communication systems with complex dynamics (e.g. feedback or systems, multiclass systems and systems with tightly coupled dynamics). Moreover, novel distributed cooperation schemes between neighboring nodes are proposed. Finally, a special case of SFM is proposed which better approximates the behavior of the DES attenuating the bias that is introduced due to the transition between the SFM to the DES.