Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη της θεωρίας της Near Complete Decomposability (NCD) και η εφαρμογή της στην ανάλυση της απόδοσης ενός υπολογιστικού συστήματος, του οποίου η μοντελοποίηση με παραδοσιακές τεχνικές οδηγεί σε απαγορευτικά μεγάλο χώρο κατάστασης. Αρχικά, παραθέτουμε τα βασικά σημεία της θεωρίας όπως αυτή θεμελιώνεται μαθηματικά από τον Courtois στην κλασική του μονογραφία (Courtois, 1977), ενώ στη συνέχεια προβαίνουμε στη μοντελοποίηση ενός υποθετικού σταθμού εργασίας κάποιου πολυεπεξεργαστικού συστήματος, στο οποίο εκτελούνται ανά πάσα στιγμή το πολύ Κ έργα. Ο σταθμός εργασίας που μελετάμε διαθέτει buffer πεπερασμένου μεγέθους και είναι επιφορτισμένος με τη συγκέντρωση και το συνδυασμό των επιμέρους υποέργων κάθε έργου και την αποθήκευση του στη μνήμη. Οι κλασικές τεχνικές μοντελοποίησης του buffer οδηγούν σε ένα μοντέλο με πολύ μεγάλο χώρο κατάστασης. Ωστόσο εμείς μοντελοποιούμε μία συναθροιστική εκδοχή του αρχικού μοντέλου, η οποία υπό αρκετά ρεαλιστικές συνθήκες χαίρει της NCD ιδιότητας. Την ιδιότητα αυτή του μοντέλου μας τη δικαιολογούμε τόσο διαισθητικά, όσο και μαθηματικά. Επίσης, επιβεβαιώνουμε πως το NCD μοντέλο πετυχαίνει υψηλής ποιότητας εκτίμηση των πιθανοτήτων μόνιμης κατάστασης και μίας σειράς άλλων χρήσιμων μετρικών, με σημαντικά μικρότερο υπολογιστικό κόστος σε σχέση με το αρχικό μοντέλο, εκτελώντας μία σειρά μετρήσεων στο περιβάλλον Matlab. Παράλληλα, η αξιοποίηση του NCD μοντέλου αυξάνει σημαντικά την ικανότητά μας να ερμηνεύσουμε τη δυναμική συμπεριφορά του συστήματος καθώς αυτό οδεύει προς μια κατάσταση στατιστικής ισορροπίας. Τέλος, επιχειρούμε μία σειρά από “educated guesses” για πιθανές κλάσεις συστημάτων τα οποία θα μπορούσαν να αναλυθούν με μεθοδολογία αντίστοιχη με αυτήν που ακολουθήσαμε εμείς στο παρόν κείμενο. / The purpose of this diploma dissertation is, on one hand the brief study of the theory of Near Complete Decomposability (NCD), and on the other hand the application of NCD in the analysis of a system, the modeling of which leads to a prohibitively large state space. First, we point out the fundamental mathematical principles of NCD as established by Courtois in his classic monograph (Courtois, 1977). Then, we proceed to the modeling of a hypothetical service station (R) of a multiprocessing computer system, which executes at most K jobs simultaneously. R has a finite buffer and its duty is to combine the arriving tasks into a single job and store it to memory. The usual modeling techniques applied to this “task buffer”, lead to a model with extremely large state space. So, we construct a lumped model instead, which enjoys the property of NCD. We prove this, using intuitive arguments as well as mathematical ones. Then, we confirm that the NCD model achieves a reliable estimation of the steady state probability vector and other important metrics, with significantly reduced computational complexity in comparison with the initial model. Furthermore, the exploitation of the NCD model increases significantly our ability to understand the dynamics of our system and to interpret aspects of its transient behavior towards statistical equilibrium. Finally, we make a number of “educated guesses” about possible classes of systems that could be analyzed using the same kind of techniques we used in this dissertation.

Το θέμα της παρούσας μεταπτυχιακής διπλωματικής εργασίας είναι η εφαρμογή της θεωρίας των Σχεδόν Πλήρως Αναλυόμενων Στοχαστικών Συστημάτων (Nearly Completely Decomposable) σε μία σειρά προβλημάτων στα οποία παραδοσιακές προσεγγίσεις αποδεικνύονται ερμηνευτικά στείρες και υπολογιστικά κοστοβόρες. Στο πρώτο μέρος της διπλωματικής αφού κάνουμε μία διαισθητικού τύπου παρουσίαση της ιδέας της decomposability και συνοψίσουμε τα απαραίτητα στοιχεία του θεωρητικού υποβάθρου που χρησιμοποιούμε στα πλαίσια της εργασίας, παραθέτουμε τονπυρήνα της θεωρίας της decomposability, όπως αυτή θεμελιώνεται μαθηματικά από τον Courtois στην κλασική του μονογραφία. Τέλος, παραθέτουμε και μία υλοποίηση του KMS αλγορίθμου Συσσωμάτωσης/Αποσυσσωμάτωσης, για τη λύση NCD συστημάτων. Το δεύτερο μέρος του συγγράμματος, είναι αφιερωμένο στην εφαρμογή της NCD σε δύο ενδιαφέροντα προβλήματα εκτίμησης απόδοσης υπολογιστικών συστημάτων. Συγκεκριμένα, μελετούμε μία ιδιότυπη ουρά που εξυπηρετεί πελάτες διαφορετικών κλάσεων, με τις ανά κλάση αφίξεις να χαρακτηρίζονται από εναλλαγές μεταξύ περιόδων ηρεμίας και κινητικότητας και την εξυπηρέτηση να γίνεται σε δέσμες πελατών της ίδιας κλάσης. Το κίνητρο για τη μελέτη αυτής της ουράς εντοπίζεται στη bursty φύση της μεταγωγής πακέτων στα σύγχρονα δίκτυα αλλά και στους reassembly buffers των multicluster πολυεπεξεργαστικών συστημάτων. Η ανάλυση της ουράς με παραδοσιακές τεχνικές οδηγεί αναπόφευκτα σε μαρκοβιανή αλυσίδα πολύ μεγάλου χώρου κατάστασης. Εμείς, ξεκινάμε από το πλήρες στοχαστικό μητρώο και αφού διαμερίσουμε κατάλληλα το χώρο καταστάσεων, αποδεικνύουμε ικανές συνθήκες υπό τις οποίες το αρχικό σύστημα είναι δυνατόν να αναλυθεί σε πολλαπλά επίπεδα υποσυστημάτων, η αυτόνομη ανάλυση των οποίων δίνει μία πολύ καλή προσέγγιση της στάσιμης κατανομής του αρχικού συστήματος. Επίσης, παραθέτουμε και αποδεικνύουμε μία ικανή συνθήκη για μηδενικό σφάλμα προσέγγισης και την ερμηνεύουμε σε όρους προδιαγραφών του προβλήματος. Τέλος, θεωρούμε μία ειδική συμμετρική εκδοχή για την οποία καταφέρνουμε να δώσουμε μία κλειστή έκφραση της κατανομής πληρότητας της ουράς συναρτήσει της λύσης των υποσυστημάτων. Για να δείξουμε την απλοποίηση της ανάλυσης που επιφέρει η χρήση του NCD μοντέλου θεωρούμε ένα σενάριο για το οποίο προχωρούμε την ανάλυση σε βάθος και καταφέρνουμε να εξάγουμε χρήσιμες μετρικές στις οποίες, σε αντίθετη περίπτωση, θα ήταν ιδιαίτερα επίπονο να καταλήξει κανείς. Συγκεκριμένα, υπολογίζουμε την πιθανότητα blocking και δείχνουμε πως αυτή μειώνεται σχεδόν εκθετικά με το μέγεθος της ουράς. Βλέπουμε τελικά πως η εκμετάλλευση της NCD ιδιότητας από τη μία διευκολύνει την ανάλυση και από την άλλη παρέχει ανεκτίμητη διαίσθηση σχετικά με τη μεταβατική συμπεριφορά του συστήματος προς την κατάσταση στατιστικής ισορροπίας. Το δεύτερο μέρος της διπλωματικής κλείνει με τη μελέτη κριτηρίων υπό τα οποία, πολυεπεξεργαστικά συστήματα που χωρίζονται σε ομάδες ισχυρά αλληλεπιδρώντων επεξεργαστών, μπορούν να αναλυθούν με χρήση της θεωρίας NCD. Είναι γνωστό πως στα δίκτυα ουρών αναμονής συγκρίσιμων ρυθμών εξυπηρέτησης, η NCD του μητρώου πιθανοτήτων δρομολόγησης συνεπάγεται την NCD του δικτύου. Εμείς, θεωρούμε μία ειδική περίπτωση τέτοιων συστημάτων για την οποία δείχνουμε ένα, εύκολο να ελεγχθεί, κριτήριο για NCD. Τέλος, εξετάζουμε βαθύτερα το σφάλμα της προσέγγισης, και χρησιμοποιώντας ένα πρόσφατο αποτέλεσμα της θεωρίας των σχεδόν ασύζευκτων μαρκοβιανών αλυσίδων δίνουμε έναν επιπλέον ποιοτικό περιορισμό που πρέπει να ικανοποιούν τα εν λόγω συστήματα για να πάρει κανείς ικανοποιητική προσέγγιση από την ανάλυσή τους σε ανεξάρτητα block. Στο τρίτο μέρος της παρούσας εργασίας, εξετάζουμε την εφαρμογή της NCD στο πρόβλημα της κατάταξης ιστοσελίδων. Η πρόσφατη έρευνα έχει σχολιάσει την ειδική δομή του στοχαστικού μητρώου που προκύπτει από το γράφο του διαδικτύου· συγκεκριμένα, οι τοπολογικές ιδιότητες της αυτοoργάνωσης του Ιστού φαίνεται να παράγουν ένα στοχαστικό μητρώο με NCD δομή. Εμείς, αφού παραθέσουμε μία σύνοψη των μαθηματικών πίσω από τον αλγόριθμο PageRank, σχολιάζουμε και δικαιολογούμε διαισθητικά την NCD δομή του Ιστού αλλά και τη φύση των υποσυστημάτων. Τέλος, προτείνουμε έναν νέο αλγόριθμο κατάταξης με το όνομα NCDawareRank, o οποίος εκμεταλλεύεται την NCD ιδιότητα για να πετύχει ποιοτικότερο και ταχύτερο ranking. Μάλιστα, δίνουμε δύο εκδοχές του αλγορίθμου, μία σειριακή και μία παράλληλη, η οποία εκμεταλλεύεται την NCD του Ιστού και υπολογιστικά. Τα οφέλη που υπόσχεται ο NCDawareRank τα επιβεβαιώνουμε και πειραματικά εκτελώντας μία σειρά από πειράματα τόσο σε τεχνητά όσο και σε πραγματικά δεδομένα, αντιπαραβάλλοντας τα αποτελέσματα μας με αυτά του αλγορίθμου PageRank. O NCDawareRank φαίνεται μάλιστα να δίνει λύση σε ένα γνωστό πρόβλημα του PageRank: αυτό της μεροληψίας εναντίον νεοεισερχομένων σελίδων. Άλλο ένα, τέλος, παράπλευρο όφελος του αλγορίθμου NCDawareRank είναι αυτό της Levelwise κατάταξης, η οποία εκτός της σημασίας που έχει αφεαυτής, μπορεί να υποδείξει εξυπνότερο crawling ή ακόμα και αποδοτικότερα σχήματα ευρετηριοποίησης του Ιστού. Στο τέταρτο και τελευταίο μέρος της διπλωματικής εφαρμόζουμε την NCD στην εύρεση των στοχαστικά ευσταθών καταστάσεων μίας κατηγορίας εξελικτικών παιγνίων στα οποία εμφανίζονται πολυεπίπεδες στρατηγικές δυναμικές. Αφού παραθέσουμε κάποιες πρόσφατες παρατηρήσεις από τη βιβλιογραφία της οικονομετρίας σχετικά με την αξιοποίηση της NCD στην προσεγγιστική ανάλυσή τους, αποδεικνύουμε συνθήκες υπό τις οποίες είναι δυνατόν να πετύχει κανείς ακριβή ανάλυση. / The purpose of this master’s thesis is the application of the theory of Nearly Completelely Decomposable stochastic systems to a number of interesting problems for which tra- ditional techniques turn out to be both intuitively unappealing and computationally in- tractable. In the first part of this work, after introducing, the concept of decomposability in an intuitive way and summarizing the essential elements of the theoretical background that is necessary to follow the rest of the text, we present the fundamental mathematical principles of NCD as established by Courtois in his classic monograph. Finally, we give an implementation of the KMS iterative aggregation/disaggregation algorithm which is commonly used for the solution of NCD systems. The second part of the dissertation is devoted to the application of NCD to two inter- esting problems of Computer Systems Performance Evaluation. Specifically, we study an uncommon discrete time queue that serves customers from different classes, with the ar- rivals of each class characterized by alternating busy and idle periods. The service is done in batches of customers of the same class. The motivation behind the study of this queue, lies in the bursty nature of packet switching, as well as in the modern reassembly buffers of multicluster multiprocessor systems. The traditional analysis techniques of this queue inevitably lead to Markov chains with very large state space. We begin with the complete stochastic matrix and after careful partitioning of the state space, we give sufficient condi- tions under which the original system can be analysed through multi level decomposition into subsystems, the autonomous analysis of which results in a very good approximation to the stationary distribution of the original system. Furthermore, we present and prove a sufficient condition for an error-free approximation and we give an interpretation of this condition in terms of the specifications of the problem. Finally, we consider a special sym- metric version of the problem, for which we manage to derive a closed-form expression for the queue’s occupancy distribution as a function of the steady state probabilities of the subsystems. To demonstrate the simplification of the analysis brought by the NCD model, we con- sider a scenario in which we proceed to an in depth analysis and we manage to extract useful metrics the derivation of which, would be considerably harder without exploiting 13 Abstract 14 NCD. Specifically, we calculate the blocking probability and we show that it decreases almost exponentially with the size of the queue. From our analysis, it is clear that the exploitation of the NCD model increases significantly our ability to understand the dy- namics of our system and to interpret aspects of its transient behaviour towards statistical equilibrium. The second part of this work ends with the study of criteria under which multipro- cessing systems, that can be divided into groups of strongly interacting processors, can be analysed using the theory of NCD. It is known that in queueing networks with servers of comparable service rates, the NCD of the routing probability matrix implies the NCD of the network. We consider a special case of such systems and we derive an easy to check criterion for NCD. Finally, we look deeper into the error analysis of this approach, and using a recent result from the theory of nearly uncoupled Markov chains, we give an addi- tional qualitative constrain to be met by these systems in order to get a good approximation of their analysis into independent blocks. In the third part of this paper, we examine the application of NCD to the problem of ranking websites. Recent research has commented on the special structure of the stochastic matrix which corresponds to the web-graph. In particular, the topological properties of the Web seems to produce a NCD stochastic matrix. Here, after presenting briefly the mathe- matical basis of PageRank, we give a linear algebraic as well as an intuitive justification of the NCD Web structure and we discuss the nature of the subsystems. Finally, we propose a new ranking algorithm named NCDawareRank, which exploits NCD in order to achieve a fairer and faster ranking. Indeed, we give two versions of the algorithm, one serial and one parallel, in which we take advantage of the computational benefits of NCD as well. The advantages of NCDawareRank are then confirmed experimentally through a series of tests on both, artificial and real data. NCDawareRank seems to solve a known problem of PageRank: the bias against new websites. Finally, another side benefit of our algorithm is that it makes it easy to extract a level-wise ranking, which besides its importance in itself, may indicate smarter crawling or even more sophisticated and efficient indexing schemes of the Web. Finally, in the fourth part of this work we apply NCD to the problem of finding the stochastically stable states of a class of evolutionary games which involve multilevel strategic dynamics. After presenting some interesting recent results coming from the lit- erature of econometrics, we give conditions under which it is possible to get the exact stochastically stable states through the use of NCD.