Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/9660
Title: Συστήματα αναμονής με επαναλαμβανόμενες αφίξεις πελατών : ανασκόπιση και μια εφαρμογή
Other Titles: Retrial queueing systems : a review and an application
Authors: Ζησιμοπούλου, Έλλη-Άρτεμις
Keywords: Ουρά επαναλαμβανόμενων αφίξεων
Μαρκοβιανή διαδικασία
Μέτρα απόδοσης
Μέθοδος συμπληρωματικής μεταβλητής
Μέθοδος υπεισερχόμενης Μαρκοβιανής αλυσίδας
Πινακοαναλυτικές μέθοδοι
Ψευδοδιαδικασία γεννήσεων-θανάτων
Αποτίμηση απόδοσης
Πρωτόκολλο ελέγχου μετάδοσης δεδομένων στο διαδίκτυο
Keywords (translated): Retrial queue
Markov process
Performance characteristics
Supplementary variable method
Embedded Markov chain method
Matrix-analytic methods
Quasi birth-death process
Performance evaluation
Transmission Control Protocol (TCP)
Abstract: Στην κλασσική θεωρία ουρών αναμονής, ένας πελάτης που φθάνοντας σε ένα σύστημα βρει όλους τους υπάλληλους μη-διαθέσιμους, είτε περιμένει σε μια ουρά για να εξυπηρετηθεί, είτε αναχωρεί άμεσα από αυτό. Στην πράξη όμως, ένα ποσοστό αυτών που αναχωρούν επιστρέφουν μετά από κάποιο χρονικό διάστημα. Αυτή η συμπεριφορά των πελατών δημιούργησε μια νέα κλάση συστημάτων αναμονής, αυτή των ουρών επαναλαμβανόμενων αφίξεων (retrial queues). Στα συστήματα αυτά, όταν ο πελάτης που εισέλθει στο σύστημα δεν βρει ελεύθερο κάποιον υπάλληλο, αναχωρεί προσωρινά από αυτό και επαναλαμβάνει την προσπάθεια του να βρει διαθέσιμο κάποιον υπάλληλο μετά από τυχαίο χρονικό διάστημα. Εφαρμογές αυτών των συστημάτων συναντώνται στην μελέτη της αποτίμησης απόδοσης σε τηλεφωνικά δίκτυα, ασύρματα δίκτυα, δίκτυα Η/Υ, στην βιομηχανία κ.α.. Στην παρούσα διατριβή, γίνεται μια ανασκόπιση των βασικών αποτελεσμάτων και μια πρώτη προσπάθεια μελέτης σε ερευνητικό επίπεδο ενός συστήματος επαναλαμβανόμενων αφίξεων στην αποτίμηση απόδοσης πρωτοκόλλων ελέγχου μετάδοσης δεδομένων στο διαδίκτυο. Στο πρώτο κεφάλαιο κάνουμε μια εισαγωγή στα retrial συστήματα εξυπηρέτησης, παραθέτοντας βασικές έννοιες και εφαρμογές αυτών. Στο δεύτερο κεφάλαιο μελετάμε λεπτομερώς τα βασικά Μ/Μ/1 και M/G/1 retrial συστήματα εξυπηρέτησης. Συγκεκριμένα, μελετάμε την από κοινού οριακή κατανομή του αριθμού των πελατών στην ουρά επαναλαμβανόμενων αφίξεων και στον χώρο εξυπηρέτησης και υπολογίζουμε τα κύρια μέτρα απόδοσης. Στο M/G/1 retrial σύστημα χρησιμοποιούμε την μέθοδο της συμπληρωματικής μεταβλητής (supplementary variable method) και της υπεισερχόμενης Μαρκοβιανής αλυσίδας (embedded Markov chain). Στο τρίτο κεφάλαιο, χρησιμοποιώντας τις ίδιες μεθοδολογίες, μελετάμε το M/G/1 retrial σύστημα εξυπηρέτησης με ομαδικές αφίξεις πελατών. Στο τέταρτο κεφάλαιο αναφέρουμε έναν διαφορετικό τρόπο μελέτης των συστημάτων αναμονής, τις πινακοαναλυτικές μεθόδους (Matrix-analytic methods) που αποτελούν σημαντικό εργαλείο ανάλυσης πολύπλοκων συστημάτων με αλγοριθμική προσέγγιση. Αυτές οι μέθοδοι παρουσιάζονται κατά την μελέτη QBD (Quasi Birth-Death process) διαδικασιών. Τέλος, στο πέμπτο κεφάλαιο παρουσιάζουμε ένα νέο μοντέλο ουράς επαναλαμβανόμενων αφίξεων με εφαρμογή στην αποτίμηση απόδοσης (performance evaluation) του πρωτοκόλλου ελέγχου μετάδοσης πακέτων δεδομένων στο διαδίκτυο (TCP: Transmission Control Protocol). Το σύστημα μελετάται με μια τριδιάστατη Μαρκοβιανή διαδικασία (QBD process) και με χρήση πινακοαναλυτικών μεθόδων υπολογίζουμε τα κύρια μέτρα απόδοσης του συστήματος. Με βάση αυτά τα μέτρα, υλοποιούμε ορισμένα αριθμητικά παραδείγματα, τα οποία δίνουν πληροφορίες για την όλη λειτουργία και συμπεριφορά του συστήματος.
Abstract (translated): In classical queueing theory, a customer arriving at a system where all the employees are non-available, can either wait in a queue to be served or can leave the system. In practice, however, a proportion of the customers that leave, often return after some time. This behaviour has created a new class of queueing systems, namely the retrial queues. In these systems, when an arriving customer does not find any free employee, he/she temporarily departs from it and repeats the attempt to find an available employee after some time. Applications of such systems are found in the study of performance evaluation in telephone networks, wireless networks, computer networks, in the industry etc. In this thesis, we provide an overview of the main results and we make a first attempt to study at a research level a retrial system for the performance evaluation of data transmission control protocols on the Internet. In the first chapter we introduce the retrial systems by presenting their basic concepts and applications. In the second chapter we make a detail presentation of the basic M/M/1 and M/G/1 retrial systems. Specifically, we study the joint limit distribution of the number of customers in the repeated arrivals queue and the service area and calculate the main performance characteristics. In the case of M/G/1 retrial system we use the supplementary variable and embedded Markov chain methods. In the third chapter, using the same methodology, we study the M/G/1 retrial system with batch arrivals. In the fourth chapter we describe a different way of studying the queueing systems, the Matrix-analytic methods. These methods constitute an important tool that provides an algorithmic approach in the analysis of complex systems. We present these methods in the context of Quasi Birth-Death (QBD) processes. Finally, in the fifth chapter we present a new model of retrial queues with application in the performance evaluation of the Transmission Control Protocol (TCP). We study this system using a three-dimensional Markov QBD process and we calculate the system's main performance characteristics using matrix-analytic methods. Based on these measures, we implement some numerical examples, which give information on the overall functioning and behaviour of the system.
Appears in Collections:Τμήμα Μαθηματικών (ΜΔΕ)



This item is licensed under a Creative Commons License Creative Commons