Στην άσκηση αυτή θα υπολογισθεί το μέγιστο throughput που προκύπτει
με την χρήση input queueing σε ένα μεταγωγέα 3x3 όπου η κατανομή
προορισμού είναι ομοιόμορφη.
Eνας τέτοιος μεταγωγέας έχει 27 διαφορετικές
καταστάσεις (x_0,x_1,x_2) όπου x_i (με δυνατές τιμές (0,1,2))
είναι ο κόμβος εξόδου για τον οποίο προορίζεται το πακέτο
που είναι στην κορυφή της ουράς του κόμβου εισόδου i.
Ομως, κατ' αναλογία με την ανάλυση που έγινε για τον μεταγωγέα 2x2,
είναι δυνατόν να περιορισθεί η πολυπλοκότητα του προβλήματος
χάρις στην συμμετρία μεταξύ καταστάσεων
που έχουν το ίδιο πλήθος ιδίων προορισμών.
(Π.χ. οι καταστάσεις (0,0,1) και (2,1,2) θα πρέπει να εμφανίζονται
με την ίδια στάσιμη πιθανότητα, δηλαδή πιθανότητα σε slot m-->οο).
Με βάση την παρατήρηση αυτή να προτείνετε ένα νέο,
πιό περιορισμένο σύνολο καταστάσεων.
Κατόπιν, να αναλύσετε πώς εξελίσσονται οι πιθανότητες
των καταστάσεων αυτών από την χρονική στιγμή m-1 στην χρονική στιγμή m
και να γράψετε τις αντίστοιχες εξισώσεις.
Στη συνέχεια να υπολογίσετε τις οριακές τιμές των ανωτέρω πιθανοτήτων
γιά m-->οο.
Βάσει αυτών να υπολογίσετε την μέγιστη τιμή του throughput.
Να επαληθεύσετε ότι το αποτέλεσμά σας είναι το ίδιο
με αυτό του Table I στο άρθρο των Karol, Hluchyj, and Morgan.
7.2 Output Queue Size Distribution
Να υπολογίσετε την κατανομή του μεγέθους ουράς σε ένα μεταγωγέα
2x2 με output queueing, χρησιμοποιώντας την έκφραση της
αντίστοιχης χαρακτηριστικής συναρτήσεως Q(z), τύπος (7) του
άρθρου των Karol, Hluchyj and Morgan, και κάνοντας ανάπτυξη
σε δυναμοσειρά. Κατόπιν να εκτιμήσετε το απαιτούμενο μέγεθος
ενταμιευτή ανά έξοδο, ώστε η πιθανότητα απωλείας πακέτου
(packet loss probability) να μην υπερβαίνει τις τιμές
10^{-2},10^{-4}, 10^{-6}, 10^{-8}, όταν η διέλευση p
ισούται με 0.8 και 0.9. Να συγκρίνετε τα αποτελέσματά σας με αυτά
στις καμπύλες του Σχήματος 9 του άρθρου των Hluchyj and Karol.