Queuing Systems

Slide11ΣΥΣΤΗΜΑΤΑ  ΑΝΑΜΟΝΗΣ Queuing  Systems ΣΥΣΤΗΜΑΤΑ  ΑΝΑΜΟΝΗΣ Queuing  Systems   Παραδείγματα χρήσης  ουρών Μ/Μ/ c/K  και αξιολόγησης συστημάτων αναμονής Β.  Μάγκλαρης   < maglaris@netmode.ntua.gr> Β.  Μάγκλαρης   < maglaris@netmode.ntua.gr> Σ.  Παπαβασιλείου   < papavass@mail.ntua.gr> Σ.  Παπαβασιλείου   < papavass@mail.ntua.gr> 5-6-2014 5-6-2014

Slide2Παράδειγμα (1) : Πιθανότητες καιεξισώσεις καταστάσεων ισορροπίας • 10 τερματικά τροφοδοτούν ένα δρομολογητή που εξυπηρετεί δεδομένα σε πακέτα των 1000  bits  κατά μέσο όρο. Η έξοδος του δρομολογητή είναι γραμμή των 10  Mbps (Megabits per sec).  Τα τερματικά θεωρούνται ανεξάρτητα και ισότιμα. • A)  Προσεγγίστε τον δρομολογητή σαν ουρά Μ/Μ/1. Βρείτε το μέσο όρο ροής των δεδομένων ανά τερματικό ώστε η γραμμή να έχει χρησιμοποίηση 50%. • Β) Αν ο δρομολογητής δεν δύναται να αποθηκεύει πάνω από 3 πακέτα (μαζί με το πακέτο υπό εξυπηρέτηση) και ο μέσος ρυθμός ροής πακέτων ανά τερματικό είναι 5 00   packets/sec,  βρείτε τα χαρακτηριστικά της ουράς. Υποθέστε  Poisson  διαδικασία άφιξης πακέτων και εκθετικά κατανεμημένους χρόνους εξυπηρέτησης πακέτων.

Slide3Λύση – Τμήμα ΑΧρησιμοποιείται μοντέλο Μ/Μ/1 Η ροή πακέτων ανά τερματικό είναι λ. Ζητούμενο: λ=?  pak/sec , Ο ρυθμός εξυπηρέτησης είναι: μ=(1 0000 kbits / sec ) /(1 kbits/pkt)   =  10 000 pkts/sec Η αθροιστική ροή πακέτων (από όλα τα τερματικά) στον δρομολογητή είναι: 10λ. Ο βαθμός χρησιμοποίησης είναι:   u= (10λ)/μ=0.5   (10λ)/10 000 =0.5   λ=5 00   pkts/sec 10λ 10λ 10λ μ μ 10λ μ μ 0 1 2 n -1 n n+1

Slide4Λύση – Τμήμα Β10λ 10λ 10λ μ μ μ 0 1 2 3 Χρησιμοποιείται μοντέλο Μ/Μ/1/3 λ=5 00   pkts/sec ,  μ=1 0000 pkts/sec 10λ P 0 =μ P 1  P 1 =(10 λ/μ) P 0   P 1 = 0.5P0 10λ P 1 =μ P 2  P 2 =(10 λ/μ) P 0 2     P 2 =0.25P0 10λ P 2 =μ P 3  P 3 =(10 λ/μ) P 0 3     P 3 =0.125P0 P 0 +P 1 +P 2 +P 3 =1   P 0 =8/15, P 1 =4/15, P 2 =2/15, P 3 =1/15 Ρυθμαπόδοση: γ=10λ(1- P bl ) =500*(14/15)=1400/3   pkts/sec (γ=μ(1- P 0 )) Μέσο μήκος ουράς:  E(n)=0*(8/15)+1*(4/15)+2*(2/15)+3*(1/15)=11/15 pkts Πιθανότητα απωλειών:  P bl =P 3 =1/15 Μέση Καθυστέρηση:  E( τ)= E(n)/ γ = ( 11/15 )/(14 00 /3)=11/70 00 sec

Slide5Παράδειγμα (2): Μοντελοποίηση -Σύγκριση Δύο υπολογιστές επικοινωνούν με μια   γραμμή  64 kbps (kbits/sec)  και υποστηρίζει  8  ροές .  Αν το μέσο μήκος πακέτου είναι   150  bytes,  ο ρυθμός άφιξης ανά ροή   είναι  4 packets/second  και ακολουθεί  Poisson κατανομή ,  και ο χρόνος εξυπηρέτησης πακέτου είναι εκθετικά κατανεμημένος: Είναι καλύτερα το δίκτυο να παρέχει σε κάθε ροή το δικό της αφιερωμένο ( dedicated ,   αποκλειστική πρόσβαση)  8 kbps  κανάλι, ή είναι προτιμότερο   όλες οι ροές να μοιράζονται όλη τη χωρητικότητα της γραμμής? Θεωρείστε ότι ο χρόνος καθυστέρησης του πακέτου είναι το πιο σημαντικό κριτήριο.

Slide6ΛύσηΑς θεωρήσουμε πρώτα το δίκτυο να παρέχει σε κάθε ροή το δικό της (αποκλειστική πρόσβαση)  dedicated 8 kbits/sec  κανάλι. Τότε κάθε υποσύστημα μπορεί να μοντελοποιηθεί σαν ένα ξεχωριστό  M/M/1  σύστημα με  =4 packets/sec  και ρυθμό εξυπηρέτησης  8 kbits/sec  ή ισοδύναμα Θεωρώντας την περίπτωση όπου οι ροές μοιράζονται όλη τη χωρητικότητα της γραμμής τότε συγχωνεύουμε όλες τις ροές και μοντελοποιούμε το σύστημα σαν  M/M/1  σύστημα :  με   =8*4=32 packets/second  και   ρυθμό εξυπηρέτησης 64 kbits/sec  ή ισοδύναμα Προτιμότερη είναι η δεύτερη λύση αφού μειώνει την καθυστέρηση σημαντικά

Slide7Μια τηλεφωνική εταιρεία εγκαθιστά σύνδεση μεταξύδύο πόλεων όπου η αναμενόμενη κίνηση ακολουθεί κατανομή  Poisson  με ρυθμό  30 calls/min.  Η διάρκεια των κλήσεων είναι ανεξάρτητες εκθετικά κατανεμημένες τυχαίες μεταβλητές με μέση τιμή  3 min. Πόσα κυκλώματα θα πρέπει να παρέχει η εταιρεία ώστε να εγγυηθεί ότι η πιθανότητα απόρριψης κλήσης ( blocking) ( επειδή όλα τα κυκλώματα είναι κατειλημμένα) είναι μικρότερη του  1% Παράδειγμα (3) :  Μοντελοποίηση Τηλεφωνικής Ζεύξης

Slide8Θεωρούμε ένα σύστημα M/M/m/m  όπου  m  είναι ο αριθμός κυκλωμάτων (γραμμών) που παρέχει η εταιρεία .  Πρέπει να βρούμε τον μικρότερο αριθμό  m  για τον οποίο   p m <0.01  όπου   p m Έχουμε      =   30 calls/min, 1/    =   3 min,  άρα ρ  =   /    =30  3   =   90   Erlangs. Με αντικατάσταση στην παραπάνω σχέση υπολογίζουμε την τιμή του  m. Λύση

Slide9Ένας δρομολογητής πακέτων  μπορεί να επεξεργάζεται πακέτα με μέσο ρυθμό  300 pkts/sec   (packets per second).  Τα πακέτα καταφθάνουν στον δρομολογητή κατά μέσο όρο με ρυθμό  200   pkts/sec.  Αν μοντελοποιήσουμε το σύστημα σαν   M/M/1 •   Μέσος  #  πακέτων στο σύστημα : N  = λ/(μ-λ)  = 200/(300-200) = 2 πακέτα •   Μέσος  #  πακέτων σε αναμονή : N Q  =  λ 2 /[μ(μ-λ)]  = 200 2 /([300(300-200)] = 1.33   πακέτα •   Μέσος χρόνος πακέτου στο σύστημα: Τ = 1/(μ-λ)  = 1/(300-200) = 0.01  sec  = Ν/λ  ( Νόμος  Little) •   Μέσος χρόνος αναμονής  ( στην ουρά ): W =  λ/[μ(μ-λ)]   = 2/300 = 0.0 0666 sec  = Ν Q /λ  ( Νόμος Little) •   Πιθανότητα να είναι ο εξυπηρετητής απασχολημένος ρ = λ/μ  =  2/3 •   Πιθανότητα το σύστημα να είναι άδειο P 0 =1 - ρ   =   0.333 Παράδειγμα (4): (α) Αξιολόγηση Δρομολογητή

Slide10Για να βελτιώσουμε την απόδοση τουσυστήματος έχουμε δύο επιλογές : • Να εγκαταστήσουμε ένα γρηγορότερο επεξεργαστή  ( αντικαθιστώντας τον παλαιό ) • Να εγκαταστήσουμε και έναν δεύτερο εξυπηρετητή ( b ) Βελτίωση Επίδοσης

Slide111η   Επιλογή Αντικατάσταση του υπάρχοντος εξυπηρετητή με άλλον γρηγορότερο  με ρυθμό      =   400   pkts/second Επαναπροσδιορισμός της απόδοσης του συστήματος Μ/Μ/1 με λ = 200 pkst/sec,  μ = 400  pkts/sec  και άπειρο μήκος ουράς 2η Επιλογή Έχουμε ένα σύστημα με δύο εξυπηρετητές ,  ο κάθε ένας με ρυθμό μ = 200 pkts/sec.  Η άφιξη των πακέτων γίνεται σε μία ουρά  (buffer)  με ρυθμό      = 200 pkts/second  και μετά δρομολογούνται  στον πρώτο εξυπηρετητή που είναι ελεύθερος.   Το σύστημα αυτό το μοντελοποιούμε σαν  M/M/2  με άπειρο μήκος ουράς Λύση

Slide122η  Επιλογή   M/M/m  ( m =2 ) Infinite buffer Finite # of servers (m) Prob. All servers are busy ρ’ = λ/μ  Erlangs,  ρ = ρ’/ m < 1 ΑΣΚΗΣΗ:  Ποίες είναι οι επιδόσεις (μέση καθυστέρηση) των δύο εναλλακτικών; Γιατί;

Slide13μηνύματα παραδίδονται σε ένα σύστημα αναμονής που αποτελείται απόδύο εξυπηρετητές και κοινό χώρο αναμονής. Η διαδικασία άφιξης των μηνυμάτων είναι  Poisson  (λ=1 πελάτης/ sec ) και οι χρόνοι εξυπηρέτησης μηνυμάτων είναι εκθετικά κατανεμημένοι. Για τον πρώτο εξυπηρετητή ο ρυθμός εξυπηρέτησης είναι: μ α   και για το δεύτερο είναι: μ β . Κάθε καινούριο μήνυμα εξυπηρετείται πάντα από τον πρώτο εξυπηρετητή, αν αυτός είναι ελεύθερος. Αν ο πρώτος εξυπηρετητής είναι απασχολημένος τότε το μήνυμα εξυπηρετείται από τον δεύτερο εξυπηρετητή. Αν και οι δύο εξυπηρετητές είναι απασχολημένοι το μήνυμα αποθηκεύεται στην ουρά. Βρείτε τις εργοδικές πιθανότητες καταστάσεως και τους βαθμούς χρησιμοποίησης των δυο εξυπηρετητών.   Παράδειγμα (5): Μοντελοποίηση- διάγραμμα καταστάσεων

Slide14ΑΣΚΗΣΗ 1• Θεωρήστε ένα σύστημα παρόμοιο με ένα Μ/Μ/1 με τη διαφορά ότι όταν το σύστημα αδειάζει η εξυπηρέτηση των πελατών αρχίζει όταν  k   πελάτες είναι παρόντες στο σύστημα   ( k  γνωστό). Όταν η εξυπηρέτηση ξεκινήσει συνεχίζει κανονικά μέχρι το σύστημα να αδειάσει ξανά. • Α) Σχεδιάστε το διάγραμμα καταστάσεων του συστήματος. • Β) Βρείτε τις εργοδικές πιθανότητες καταστάσεων του αριθμού πελατών στο σύστημα • Γ) Βρείτε το μέσο αριθμό πελατών στο σύστημα και τη μέση καθυστέρηση ανά πελάτη.

Slide15ΑΣΚΗΣΗ 2