Η διπλωματική εργασία αυτή εκπονήθηκε στο Εργαστήριο της Ερευνητικής Ομάδας Αλληλεπίδρασης Ανθρώπου – Υπολογιστή του Τμήματος Ηλεκτρολόγων Μηχανικών και Τεχνολογίας Υπολογιστών υπό την επίβλεψη του καθ. Ν.Αβούρη. Στόχος της εργασίας είναι η σχεδίαση και ανάπτυξη μίας φορητής εφαρμογής – χωροευαίσθητου παιχνιδιού, με τη χρήση τεχνολογιών επαυξημένης πραγματικότητας. Ο χρήστης της εφαρμογής θα μπορεί να περιηγείται στον χώρο που ορίζει το παιχνίδι και να αλληλεπιδρά με πραγματικά αντικείμενα του χώρου αυτού, με σκοπό τη μάθηση και την ψυχαγωγία. Ο χώρος στον οποίο αναφέρεται η διπλωματική εργασία, είναι η πλατεία Γεωργίου Α’ στην Πάτρα. / This thesis was conducted at the Laboratory of Human Interaction Research Group - Computer Department of Electrical and Computer Engineering under the supervision of Prof. N.Avouris . The goal of this project is the design and development of a pervasive, location-based game, using augmented reality technologies . The user can navigate through the gamespace and interact with real-world objects, in order to learn and enjoy . The selected area, to which the thesis refers, is George the 1st Square, in Patras .

Ανέκαθεν, η ανάγκη του ανθρώπου για πληροφορία ήτανε μια από αυτές που φρόντιζε να ικανοποιήσει όσο το δυνατόν πληρέστερα. Η πληροφορία είναι σε όλες τις περιπτώσεις ένα πολύτιμο εργαλείο στην λήψη αποφάσεων και οι άνθρωποι γρήγορα αντιλήφθηκαν την σημασία της, ειδικότερα μάλιστα στην σύγχρονη εποχή στην οποία μέσω της επιστήμης της Πληροφορικής δόθηκε η δυνατότητα σε μεγάλο μέρος του κοινού να έχει πρόσβαση σε τεράστιο όγκο δεδομένων, τα οποία μέσω της σωστής επεξεργασίας μετατρέπονται σε πληροφορία. Αυτό που πλέον αποτελεί πρόκληση, η οποία μας καλεί σαν επιστήμονες της Πληροφορικής να αντιμετωπίσουμε, είναι η εύρεση και στην συνέχεια η εφαρμογή καινούργιων μεθόδων γρήγορης και ανέξοδης συλλογής, αποδοτικής αποθήκευσης και εποικοδομητικής ανάλυσης δεδομένων, έτσι ώστε να γίνουν πληροφορία ποιοτική, πλούσια και με σημαντική χρηστική αξία. Στις μέρες μας, η ανάπτυξη του κλάδου τόσο των κατανεμημένων συστημάτων όσο και του διαδικτύου, μας έχουνε δώσει την δυνατότητα να χρησιμοποιούνται χαμηλοί σε απαιτήσεις υπολογιστικοί πόροι για να επεξεργάζονται παράλληλα μεγάλο όγκο δεδομένων. Ο κλάδος της Πληροφορικής που ασχολείται εκτενώς με αυτά τα συστήματα είναι τα ομότιμα συστήματα ή αλλιώς p2p συστήματα και ο κατανεμημένος υπολογισμός. Η παρούσα διπλωματική εργασία έχει ως στόχο να βρίσκει σε κατανεμημένο περιβάλλον σημεία στις δύο διαστάσεις. Ορίζεται, δηλαδή, ένας χώρος από κ – διαστάσεις που είναι το πλέγμα (grid), στον οποίο ο χρήστης προσπαθεί να εντοπίσει σημεία που τον ενδιαφέρουν δημιουργώντας έτσι ερωτήματα εύρους. Το σύστημα θα ψάχνει να βρει το αποτέλεσμα στο ερώτημα αυτό για να καταλήξει σε ποιο από τα άλλα ορθογώνια τμήματα του πλέγματος εμπλέκεται και στην συνέχεια αυτά (τα τμήματα) θα επιστρέφονται. Πιο συγκεκριμένα, το πλέγμα μας χωρίζεται σε τετράγωνες περιοχές και κάθε κόμβος του κατανεμημένου δικτύου αναλαμβάνει να φιλοξενήσει τα σημεία της κάθε τετράγωνης περιοχής. Όλοι αυτοί οι κόμβοι οργανώνονται σε ένα hadoop cluster και τα δεδομένα εισάγονται στην κατανεμημένη βάση δεδομένων HBase που βασίζεται στην αρχιτεκτονική του BigTable της Google File System. Ο τρόπος που οργανώνονται τα δεδομένα στην HBase είναι κατανεμημένος και γίνεται χρήση των B+ -δέντρων. Η χρησιμότητα των B+ -δέντρων σε συνδυασμό με το κατανεμημένο πλαίσιο εργασίας του Hadoop, έγκειται στο γεγονός ότι με την χρήση των απαραίτητων εργαλείων τόσο της HBase όσο και του Hadoop FS, μπορούμε να γνωρίζουμε σε ποιόν κόμβο του hadoop cluster είναι αποθηκευμένοι οι ζητούμενοι κόμβοι του B+ -δέντρου και έτσι να επιτυγχάνεται η γρήγορη ανάκτηση των αποτελεσμάτων σε ένα ερώτημα εύρους. Η διάρθρωση της εργασίας έχει ως εξής: Στο πρώτο κεφάλαιο γίνεται μια εισαγωγή στις έννοιες του κατανεμημένου υπολογισμού πάνω σε κατανεμημένα περιβάλλοντα. Στο δεύτερο γίνεται μια αναφορά στα ομότιμα δίκτυα (p2p) και πιο συγκεκριμένα αναλύεται το δίκτυο επικάλυψης του BATON που έχει δενδρική δομή όμοια με αυτή του Β+ -δέντρου. Στο τρίτο κεφάλαιο αναφέρεται μια υλοποίηση δεικτοδότησης και απάντησης σε ερωτήματα εύρους στο Νέφος Υπολογιστών με χρήση βασικών δομών δεδομένων B+ -δέντρου. Επίσης, η ART Autonomous Range Tree δομή παρουσιάζεται η οποία μπορεί να υποστηρίξει ερωτήματα εύρους σε τόσο ευρείας κλίμακας σε μη κεντρικοποιημένα περιβάλλοντα και μπορεί να κλιμακώνεται σε σχέση με τον αριθμό των κόμβων, καθώς και με βάση τα στοιχεία που είναι αποθηκευμένα. Η ART δομή ξεπερνά τις πιο δημοφιλείς μη κεντρικοποιημένες δομές, συμπεριλαμβανομένου του Chord (και μερικοί από τους διαδόχους του), του ΒΑΤΟΝ (και τον διάδοχό του) και των Skip-Graphs. Στο τέταρτο και πέμπτο κεφάλαιο, αντίστοιχα, γίνεται μια αναφορά στα βασικότερα σημεία της αρχιτεκτονικής και της λειτουργίας του Hadoop Framework και της HBase. Στο έκτο κεφάλαιο, βρίσκεται η περιγραφή της υλοποίησης της παρούσης διπλωματικής εργασίας μαζί με τους αλγορίθμους και τον τρόπο λειτουργίας τους. Στο επόμενο γίνεται η αξιολόγηση των πειραματικών αποτελεσμάτων της παρούσης διπλωματικής εργασίας καθώς, και το τι συμπεράσματα προκύπτουν μέσα από την αξιολόγηση. Τέλος, στο τελευταίο και όγδοο κεφάλαιο γίνεται η αποτίμηση της διπλωματικής εργασίας, καθώς αναφέρονται τα βασικά της μέρη, όπως επίσης και πιθανές προεκτάσεις που θα βελτίωναν την απόδοση του συστήματος. / Traditionally, the human need for information was one of those seeking to satisfy as much as possible. Information is in every way a valuable tool in decision making and people quickly realized its importance, especially in modern times, when the Information Technology gave the public access to the vast volume of data, which can be further processed into information. What seems to be now a challenge that IT specialists have to face is finding and implementing new methods of fast and inexpensive data collection, efficient storing of data and constructive data analysis, in order to turn them into quality, rich and useful information. Nowadays, the devel-opment of both the field of distributed systems and the Internet gave us the possibility of using computational resources with low requirements for simultaneous processing of large amounts of data. The IT field that deals extensively with these systems are peer-to-peer systems (p2p) and distributed computing. The present dissertation aims at finding points in a distributed environment in the two-dimensional space. A space of k – dimensions is defined, i.e. the grid, in which the user tries to identify points of interest creating range queries. The system will search to find the result in this question to come up with the rectangular section of the grid that is involved and then these sections will be returned. More specifically, the grid is divided into square areas, and each node of the distributed network will accommodate points of each square area. All these nodes are organized into a hadoop cluster and the data is imported into the HBase distributed database based on BigTable architecture of the Google File System. In HBase data is organized in a distributed way and B+ -trees are used. The utility of B+ -trees in conjunction with the distributed framework of Hadoop lies on the fact that using the necessary tools of both HBase and Hadoop FS we can know in which hadoop cluster node the requested B+ -tree nodes are stored and thus achieve fast results retrieval in a range query. The structure of the project is as follows: The first chapter is an introduction to the concepts of distributed computing over distributed environments. The second is a reference to peer-to-peer networks (p2p) and more specifically the BATON overlay network, which has a tree structure similar to that of the B+ -tree, is analyzed. The third chapter deals with an indexation and answering implementation on range queries in the Computer Cloud using B+ -tree basic data structures. Also, ART Autonomous Range Tree structure is presented which can support range queries in such large-scale decentralized environments and can scale in terms of the number of nodes as well as in terms of the data items stored. ART outperforms the most popular decentralized structures, including Chord (and some of its successors), BATON (and its successor) and Skip-Graphs. In the fourth and fifth chapter respectively a reference is made to the main points of Hadoop Framework and HBase architecture and operation. The sixth chapter is the description of the implementation of this dissertation together with the algorithms and how they operate. The next chapter is the evaluation of the experimental results of this dissertation and of the conclusions that derive from the evaluation. Finally, the eighth and last chapter is an overview of the dissertation, mentioning its basic parts, as well as possible extensions that would improve the system performance.

Η έννοια των δικτύων εμφανίζεται πολύ συχνά με διάφορες μορφές. Δίκτυο μπορούμε να θεωρήσουμε ένα σύνολο υπολογιστών που συνδέονται μεταξύ τους υπακούοντας σε κάποιο πρωτόκολλο επικοινωνίας αλλά και μια ομάδα ανθρώ- πων που συνδέονται μέσω κάποιας κοινωνικής σχέσης, ενός εργασιακού χώρου αλλά και ως χρήστες ενός forum ή μίας πλατφόρμας κοινωνικής δικτύωσης. Σε οποιαδήποτε περίπτωση, ένα δίκτυο μπορεί να αναπαρασταθεί με τη μορφή ενός γράφηματος, όπου οι κόμβοι αναπαριστούν τα άτομα/υπολογιστές και οι ακμές τη μεταξύ τους σχέση ανάλογα με το πρόβλημα. Στα πλαίσια ενός τέτοιου δικτύου μας ενδιαφέρει η συμπεριφορά των κόμβων στην περίπτωση που συμβεί ένα γεγονός που αλλάζει την κατάστασή τους. Στην περίπτωση που αναφερόμαστε σε μία κοινωνική ομάδα ή μία πόλη, αυτό το φαι- νόμενο μπορεί να είναι το ξέσπασμα μίας επιδημίας που εξαπλώνεται στο δίκτυο αλλά και μίας είδησης/φήμης, όπου ενημερώνεται το δίκτυο. Στην πρώτη περί- πτωση, μας ενδιαφέρει να περιορίσουμε την επιδημία, αλλάζοντας τοπολογικά το δίκτυο ενώ στη δεύτερη περίπτωση, είναι επιθυμητό να διευκολύνουμε την εξά- πλωση της είδησης, έτσι ώστε να ενημερωθούν όσο το δυνατόν, περισσότεροι κόμβοι(χρήστες). Η συμπεριφορά του δικτύου σε ένα τέτοιο φαινόμενο, μπορεί να προσομοιωθεί από ένα δυναμικό σύστημα. Με τον όρο δυναμικό σύστημα αναφερόμαστε σε ένα σύστημα που έχει ένα σύνολο καταστάσεων, όπου κάθε κατάσταση, προκύπτει σε συνάρτηση με την προηγούμενη. Παραδείγματα εφαρμογής ενός δυναμικού συστήματος σε δίκτυο, εμφανίζονται σε διάφορους τομείς όπως στην οικολογία, τη διάχυση πληροφορίας, το viral marketing, την επιδημιολογία. Τα δυναμικά συστήματα που προσομοιώνουν τη συμπεριφορά του δικτύου σε τέτοια φαινόμενα, χρησιμοποιούν επιδημιολογικά μοντέλα για να περιγρά- ψουν τις δυνατές καταστάσεις στις οποίες μπορεί να περιέλθει ένας κόμβος. Στη συγκεκριμένη εργασία, χρησιμοποιήσαμε το μοντέλο SIS (Susceptible-Infected-Susceptible) [8].Το μοντέλο SIS δηλώνει ότι ένας κόμβος μπορεί να είναι είτε επιρρεπής στο να ασθενήσει (susceptible) είτε ασθενής (infected). Αυτό σημαί- νει πως ένας κόμβος δεν θεραπεύεται ποτέ πλήρως αλλά υπάρχει πιθανότητα να ασθενήσει πάλι. Με βάση τη βιβλιογραφία, σε ένα τέτοιο δυναμικό σύστημα, αναζητούμε κά- ποια σημεία (fixed points) στα οποία το σύστημα θα ισορροπεί. Υπάρχουν σημεία τα οποία είναι σημεία ισορροπίας αλλά δεν είναι σταθερά. Σε αυτά τα σημεία, το σύστημα μπορεί στιγμιαία να ισορροπήσει αλλά ξεφεύγει πολύ εύκολα από αυτό. Αναζητούμε συνεπώς, σταθερά σημεία ισορροπίας, τα λεγόμενα stable fixed points. Έχει αποδειχτεί [6] ότι μπορούμε σε αυτά στα σημεία να καθορίσουμε τις απαραίτητες συνθήκες για να είναι σταθερά, περιορίζοντας τη μέγιστη ιδιοτιμή του μητρώου γειτνίασης που περιγράφει το δίκτυο. Ορίζονται δηλαδή κατώφλια (thresholds) κατά περίπτωση, που περιορίζουν την μέγιστη ιδιοτιμή του δικτύου με τέτοιο τρόπο ώστε το σύστημα, να βρίσκεται σε κατάσταση ισορροπίας. Στην πε- ρίπτωση που αναφερόμαστε στο φαινόμενο της επιδημίας, στόχος είναι στο αντί- στοιχο σημείο ισορροπίας η μέγιστη ιδιοτιμή να είναι κάτω του κατωφλίου, έτσι ώστε να εξασφαλίσουμε τον περιορισμό εξάπλωσης της επιδημίας στο δίκτυο. Στην περίπτωση που αναφερόμαστε σε μία είδηση ή ένα ανταγωνιστικό προϊόν, η μέγιστη ιδιοτιμή θέλουμε να είναι άνω του αντίστοιχου κατωφλίου έτσι ώστε να έχουμε εξάπλωση στο δίκτυο. Επομένως ανάλογα με την περίπτωση, αντιμε- τωπίζουμε διαφορετικά τα κατώφλια που υπολογίζονται για το αντίστοιχο σημείο ισορροπίας. Στα πλαίσια της μεταπτυχιακής εργασίας, χρησιμοποιήσαμε το μοντέλο SIS για να περιγράψουμε το φαινόμενο όπου ένας ιός εξαπλώνεται σε ένα δίκτυο όπου οι κόμβοι του δικτύου, έχουν διαφορετική ευαισθησία απέναντί του. Πραγματο- ποιήσαμε μαθηματική περιγραφή του μοντέλου, ορίζοντας τα απαραίτητα κατώ- φλια έτσι ώστε το σύστημα να ισορροπεί ανάλογα με το σημείο ισορροπίας αλλά και το είδος του γραφήματος. Επίσης, πραγματοποιήσαμε προσομοίωση του μο- ντέλου σε συνθετικά γραφήματα (κλίκα, αυθαίρετο γράφημα κ.α), επαληθεύοντας τη συμπεριφορά που υποδεικνύει το μαθηματικό μοντέλο. / Which is the appropriate answer about the definition of a network? One could answer that a group of people who share a relationship (colleagues, students etc) could be referred to, as a network. Another possible definition, is a computer network. Consequently, it is obvious that the idea of a network can be found in various ways in our daily life. In the same terms, suppose we have one competing idea/product or a virus that propagates over a multiple profile social (or other) network. Can we predict what proportion of the network will actually get ”infected” (e.g., spread the idea or buy the competing product), when the nodes of the network appear to have different sensitivity based on their profile? For example, if there are two profiles A, B in a network and the nodes of profile A and profile B are susceptible to a highly spreading virus with probabilities βA and βB respectively, what percentage of both profiles will actually get infected from the virus in the end? The behavior of such a network, can be simulated using dynamical systems theory. We consider a dynamical system as a system with a set of possible states where each future state, is computed based on the previous state. Dynamical System Applications, can be found in many fields such as viral marketing, ecology, information diffusion and virus propagation. In order to simulate the rumor or virus which is spreading across the network, one has to use virus propagation models. The selection of the appropriate model, depends on the special attributes and characteristics of the spreading rumor/virus and it should cover all the possible states in which a node in the network can be (sick, healthy,susceptible, informed, not informed etc). According to Dynamical Systems Theory, we are looking for possible fixed points where the system is in equilibrium. In particular, we would require each fixed point to be a stable attractor and not lead the system far away from the equilibrium point due to opposing forces (stable fixed points). It has been proven that limiting the leading eigenvalue of the adjacency matrix of the graph, is the only condition required, in order for the system to be in equilibrium state, in the corresponding fixed point. In this paper, we assume an SIS propagation model [8] which is applied on a heterogeneous network. That is, we assume that there is no fair game using the terminology of [14, 3]. In the SIS model, each node can be either in a susceptible (S) state or in the infected state (I) and as result there is no permanent immunity and every node can get infected multiple times.Since this is the first theoretical treatment of heterogeneous environments for virus propagation, we choose to work in the simple model of SIS and not in other models. Suppose that we are given a social network and a rumor that spreads over it, where the nodes of the network represent people with high/low sensitivity to the rumor and the links represent the association of the nodes, how will the rumor propagate over the network? That is, can we determine whether all members of the network will reproduce the rumor to their neighbors and ”infect” them or the rumor will spread in a small group in the network and die out quickly? Similarly, which is the tipping point where such a rumor or infectious virus will take off? It would be very helpful if we could find the specific point when the ”virus” spreads all over the network and an epidemic occurs. Finally, what is the case when the nodes have different endurance/sensitivity to the ”virus” and have temporary or permanent immunity? Our basic assumption and innovation when compared to all previous approaches is that there is no fair-play and nodes have different profile against the virus. That is, the network is heterogeneous with respect to the virus, which means that nodes have different sensitivity to it. This is one of our main contributions in comparison with previous results where all nodes appear to have the same behavior towards the virus and the same model parameters. The propagation model which is followed, resembles the SIS (no immunity like flu) model where nodes are either susceptible or infected but with modifications. All nodes can get infected from one another, despite the difference of their profiles. We prove and present the tipping point where the virus is about to spread all over the network or the rumor ”infect” every member of the network and result in a ”viral” phenomenon. Our main contribution, is that we provide answers for the questions above, for special topologies such as the clique as well as arbitrary graphs of high or low connectivity. In particular, to the best of our knowledge, we are the first to provide theoretical and experimental findings on the propagation of a virus over a heterogeneous network. We prove that in the case of two profiles, if one profile has high sensitivity to the virus and the other one has low sensitivity, actually nodes from both profiles will get infected proportionally in the case where the network is a clique. For arbitrary networks, we prove necessary conditions for the virus to die out allowing for multiple profiles (not just two), while at the same time we give directions to prove other interesting cases. The problem has many applications in the field of viral marketing, medicine, ecology and other.

Στην διδακτορική διατριβή αναπτύξαμε μοντέλα για την ασυνήθη δικτυακή κυκλοφορία βασισμένη σε χαρακτηριστικά της TCP/IP επικοινωνίας ανάμεσα σε υπολογιστικά συστήματα, αλλά και στην συμπεριφορά συστημάτων και χρηστών κάτω από επιθέσεις ιών και δικτυακών σκουληκιών. Για την ανάπτυξη συνδυάσαμε το μαθηματικό φορμαλισμό πάνω σε πραγματικά χαρακτηριστικά που εντοπίσαμε πως υπάρχουν σχεδόν σε όλες τις προσπάθειες επίθεσης προς υπολογιστικά και δικτυακά συστήματα από προσπάθειες επιτιθέμενων, αλλά και με αυτοματοποιημένα συστήματα μετάδοσης ιών. Υλοποιήσαμε ένα πραγματικό κατανεμημένο σύστημα έγκαιρης και έγκυρης προειδοποίησης και λήψης άμεσων μέτρων για την προστασία δικτύων υπολογιστών από τη διάδοση των ιών και από τις διαρκώς εξελισσόμενες επιθέσεις των hackers. Τέλος η αυξανόμενη παρουσία δυνατοτήτων για fast worms μας παρακίνησε να μοντελοποιήσουμε την συμπεριφορά ιών που μεταδίδονται μέσα από τα κοινωνικά δίκτυα που σχηματίζονται από τον κατάλογο που έχουν οι χρήστες για γνωστούς και φίλους σε e-mail και Instant Messaging. Προτείνουμε λοιπόν δύο μοντέλα: ένα μοντέλο που περιγράφει την συμπεριφορά fast worms βασισμένα σε κοινωνικά δίκτυα στηριζόμενοι στο μαθηματικό μοντέλο σε Constraint Satisfaction Problems (CSP), αλλά και ένα μοντέλο για τη μετάδοση ιών και την εξουδετέρωσή τους, που λαμβάνει υπόψη την δικτυακή κίνηση και την λειτουργία των εξυπηρετητών βασισμένοι στο M/M/1 μοντέλο ουρών. Στην διατριβή προτείνουμε ένα είδος διαδραστικότητας ανάμεσα στους antivirus Agents και τους ιούς και αναλύουμε ένα μαθηματικό μοντέλο για την διάδοση πληθυσμού ιών και antivirus βασισμένα σε θεωρίες ουρών. / In this PhD Thesis we developed models for the abnormal network traffic based on TCP/IP communication protocol of computer systems, and the behavior of systems and users under viruses and worms attacks. For the development we combined mathematical formalism on real attributes that characterize almost all attacking efforts of hackers, virus and worms against computers and networking systems. Our main goal was based upon the theoretic models we proposed, to provide a useful tool to deal with intrusions. Thus we developed a Software Tool for Distributed Intrusion Detection in Computer Networks. Based on an improved model we produced a real time distributed detection system for early warning administrators of worm and virus propagation and hackers’ attacks. Also in this work we propose a discrete worm rapid propagation model based on social networks that are built using the address book of e-mail and instant messaging clients using the mathematic formalism of Constraint Satisfaction Problems (CSP). The address book, which reflects the acquaintance profiles of people, is used as a “hit-list”, to which the worm can send itself in order to spread fast. We also model user reaction against infected email as well as the rate at which antivirus software is installed. We then propose a worm propagation formulation based on a token propagation algorithm, further analyzed with a use of a system of continuous differential equations, as dictated by Wormald’s theorem on approximating “well-behaving” random processes with deterministic functions. Finally in this work we present a virus propagation and elimination model that takes into account the traffic and server characteristics of the network computers. This model partitions the network nodes into perimeter and non-perimeter nodes. Incoming/outgoing traffic of the network passes through the perimeter of the network, where the perimeter is defined as the set of the servers which are connected directly to the internet. All network nodes are assumed to process tasks based on the M/M/1 queuing model. We study burst intrusions (e.g. Denial of Service Attacks) at the network perimeter and we propose a kind of interaction between these agents that results using the formalism of distribution of network tasks for Jackson open networks of queues.

Οι συστάδες υπολογιστών αποτελούν μία σύγχρονη ευρέως χρησιμοποιούμενη και ιδιαίτερα ανταγωνιστική αρχιτεκτονική για την υλοποίηση υπολογιστικών συστημάτων υψηλών επιδόσεων με χαμηλό κόστος. Παράλληλα, η ευρεία εμπορική διάθεση πολυεπεξεργαστικών συστημάτων μικρής κλίμακας, επιτρέπει τον συνδυασμό τους σε υβριδικά σχήματα συστάδων πολυεπεξεργαστών. Παρά την ευελιξία που παρέχεται στη σχεδίαση τους, η απαίτηση για χρήση κατανεμημένων μοντέλων προγραμματισμού αυξάνει σημαντικά την πολυπλοκότητα της ανάπτυξης εφαρμογών. Μία εναλλακτική προσέγγιση αποτελούν τα συστήματα κοινής ιδεατής μνήμης. Τα συστήματα κοινής ιδεατής μνήμης παρέχουν στις εφαρμογές, που εκτελούνται σε διαφορετικούς κόμβους της συστάδας, πρόσβαση σε έναν διαμοιραζόμενο χώρο διευθύνσεων αποκρύπτοντας την υποκείμενη κατανεμημένη αρχιτεκτονική. Βασικότερο περιορισμό της πλειονότητας των υπαρχόντων υλοποιήσεων αποτελεί η απουσία υποστήριξης πολυνηματισμού. Το χαρακτηριστικό αυτό έχει ως άμεση συνέπεια τη χαμηλή χρησιμοποίηση των σύγχρονων πολυεπεξεργαστικών υπολογιστικών μονάδων, καθώς ούτε η εφαρμογή αλλά ούτε και οι μηχανισμοί που εξασφαλίζουν τη συνέπεια της κοινής μνήμης εκτελούνται παράλληλα. Στα πλαίσια της παρούσας μεταπτυχιακής εργασίας παρουσιάζεται η σχεδίαση και η υλοποίηση μίας πλατφόρμας κοινής ιδεατής μνήμης χρησιμοποιώντας μηχανισμούς υλοποιημένους αποκλειστικά σε λογισμικό. Το προτεινόμενο σύστημα στοχεύει στην αποδοτικότερη χρησιμοποίηση των πόρων των πολυεπεξεργαστικών μονάδων της συστάδας, υποστηρίζοντας την πολυνηματική εκτέλεση της εφαρμογής σε κάθε κόμβο. Τόσο το πρωτόκολλο συνέπειας της κατανεμημένης μνήμης, όσο και το υποσύστημα επικοινωνίας, επανασχεδιάστηκαν ώστε να χρησιμοποιούν πολλαπλά νήματα εκτέλεσης. Επιπλέον παρουσιάζονται και αξιολογούνται εναλλακτικοί ιεραρχικοί αλγόριθμοι συγχρονισμού που επιτρέπουν την αποδοτικότερη χρήση της υβριδικής οργάνωσης των συστάδων. / Software Distributed Shared Memory (SDSM) systems provide an abstraction layer of shared memory semantics on top of a distributed set of computational nodes. The use of small-scale Symmetric Multiprocessor (SMP) nodes has the potential for bridging the performance-cost gap between the low-end SMPs and high-end Distributed Shared Memory (DSM) systems, using a hybrid software and hardware coherency model presented in this thesis. We present the design and discuss the main architectural choices involved in our implementation of a multithreaded SDSM system. Our implementation was developed on top of Pthreads and the TCP/IP network protocol, employing a simple yet efficient design. Finally, we evaluate and analyze the performance of the multithreading SDSM platform, using a wide set of benchmark applications.

Η σχεδίαση μικροεπεξεργαστών είναι μια πολύπλοκη και σύνθετη διαδικασία, η οποία δυσκολεύει όσο οι τεχνολογικές εξελίξεις προχωράνε. Οι μελετητές της απόδοσης των μικροεπεξεργαστών, για να μελετήσουν την απόδοση ενός συστήματος καταλήγουν στη χρησιμοποίηση πλήρους προσομοίωσης, καάτι που είναι εξαιρετικά πολύπλοκο και χρονοβόρο. Σε αυτή την εργασία παρουσιάζεται ένα αναλυτικό μοντέλο που μοντελοποιεί τις επιδόσεις του επεξεργαστή με βάση το πρόγραμμα που εκτελεί και τα δομικά του χαρακτηριστικά. Το μοντέλο αυτό βασίζεται πάνω σε έναν εκτός σειράς υπερβαθμωτό επεξεργαστή. Η μοντελοποίηση βασίζεται στο γεγονός ότι ένας υπερβαθμωτός επεξεργαστής ο οποίος είναι ισορροπημένος διατηρεί σταθερή την απόδοση του εκτός αν συναντήσει ανασχετικά γεγονότα, όπως αποτυχία πρόσβασης στην κρυφή μνήμη ή λάθος στην πρόβλεψη διακλάδωσης. Τα δεδομένα του προγράμματος συλλέγονται κατά την εκτέλεση του προγράμματος με τη χρήση ενός εργαλείου παρεμβολής κώδικα σε εκτελέσιμο αρχείο, το οποίο ονομάζεται DIOTA. Παρουσιάζεται το μοντέλο σταθερής απόδοσης και μετριέται ο αντίκτυπος του κάθε ανασχετικού γεγονότος ξεχωριστά. / Microprocessor design is a complex and difficult process which day by day is getting more difficult as technology advances. Designers, in order to study the efficiency of a microprocessor tend to use full cycle simulation, which is extremely complex and time-consuming. In this thesis, an analytical model is presented, which is modelling the perfonmance of a proccessor in account with the executable and processor's functional characteristics. The model is based on an out of order superscalar processor. The modelling is based on the fact that a balanced superscalar processor is maintaining a steady performance rate, unless a disruptive miss event happens, such as a data cache miss or a branch misprediction. The data from the executable are gathered by using a binary rewriting tool, called DIOTA. The steady state model is being presented, and the impact of each miss event is measured.

Η εργασία που αναπτύσσεται έχει ως αντικείμενο το φως - σκιά. Στα πλαίσια αυτής δημιουργήθηκε ένα Project, που περιλαμβάνει δραστηριότητες σχετικές με τα φαινόμενο του φωτός ως αυτόνομη φυσική οντότητα και το σχηματισμό των σκιών. Σκοπός της έρευνας είναι να διδαχθούν τα παιδιά προσχολικής ηλικίας, με τη χρήση του υπολογιστή, την έννοια του φωτός και το φαινόμενο του σχηματισμού των σκιών. Αρχικά, δημιουργήθηκε ένα σενάριο που τα παιδιά δραματοποίησαν και το οποίο στη συνέχεια παρουσιάστηκε με powerpoint, ώστε να εισαχθούν στο θέμα. Η καταγραφή των ιδεών των παιδιών, πριν τη διδακτική παρέμβαση, έγινε με το πρόγραμμα ζωγραφικής “drawing for children” και με επιλεγμένες ερωτήσεις του κλειστού λογισμικού “I love science”. Έπειτα από συζήτηση, τα νήπια αναζήτησαν πληροφορίες στο internet, μέσω της μηχανής αναζήτησης google, από την ηλεκτρονική εγκυκλοπαίδεια “encarta kids” και το κλειστό λογισμικό «Εξερευνώ την επιστήμη». Για τη διδακτική παρέμβαση έγινε χρήση του κλειστού λογισμικού “I love science”, του λογισμικού από το διαδίκτυο “light and dark” και του λογισμικού “light and shadows”. Τέλος, η αξιολόγηση της διδακτικής παρέμβασης έγινε με το ανοιχτό λογισμικό “kidspiration” και το κλειστό λογισμικό “I love science”. Σκοπός των δραστηριοτήτων, που πραγματοποιήθηκαν με τα παραπάνω λογισμικά, ήταν να εξακριβωθεί η επιρροή της διδασκαλίας με τη βοήθεια του Η/Υ στα παιδιά της προσχολικής ηλικίας. Για τον σχεδιασμό των δραστηριοτήτων αυτών χρησιμοποιήθηκε η μέθοδος του στόχου- εμποδίου, που σε συνδυασμό με τη βιβλιογραφική έρευνα, έδωσε χρήσιμες κατευθύνσεις για την οργάνωση διδακτικών παρεμβάσεων στο θέμα φως-σκιά. Με τη μέθοδο αυτή προσαρμόστηκε το αντικείμενο διδασκαλίας στις γνωστικές δυσκολίες και τις ιδιαιτερότητες των παιδιών της προσχολικής ηλικίας. Η σύγκριση προελέγχων και μετα- ελέγχων τόσο για το φαινόμενο του φωτός όσο και της σκιάς έδειξε πως, οι διδακτικές παρεμβάσεις με τη χρήση του υπολογιστή είναι επιτυχείς, τόσο για τα νήπια, όσο και για τα προνήπια. Τέλος, διαπιστώθηκε ότι τα παιδιά ανταποκρίθηκαν σε όλες τις δραστηριότητες που αναπτύχθηκαν με τη βοήθεια του υπολογιστή, έχοντας καλλιεργήσει σημαντικές δεξιότητες επικοινωνίας και μεταξύ τους συνεργασίας, με αποτέλεσμα να μη στηρίζονται αποκλειστικά στις γνώσεις και τις επιταγές του εκπαιδευτικού. / The main subject of this project is “light and shadow”.This project includes activities that are relevant with the phenomenon of light as a natural individual entity and the phenomenon of formation of shadows.. Purpose of this research was for the kids to be taught ,using the computer, the significance of light and also the phenomenon of formation of shadows. At first, to enter the children to the theme, a script created, where they acted and which, continously is presented with powerpoint. The recording of the children’s ideas, before the teaching intervetion, is done with a drawing program “drawing for children” and with selected questions of the software “I love science. After discussion, the children looked for information in the internet, through the search machine, google, from the electronic encyclopedia “encarta kids” and the software “Exploring science”. The software “I love science”, the network software “light and dark” and the software “light and shadows”, are used for the teaching intervetion. Finally,the software “kidspiration” and the software “I love science” were used to evaluate the teaching methods. The purpose of the activities, that the above softwares created, was to verifuy the influence of teaching science to preschool children, using computers. In order to design these activities was used the method of goal-barrier, that combined to the bibliographic research, gave useful directions to organise teaching methods for the light-shadow concept. Using this method, the teaching object adjusted to the cognitive difficulties and particularities of preschool children. The comparison of pre-tests and post-tests showed for both, the phenomenon of light and shadow that,the teaching methods using the computer were succesful, for all the children.Finally, the results showed that, all the children responded positevely to the activities that were designed with the help of computers, having developed important communication and cooperation skills, in order not to depend on teachers.

Στην παρούσα διατριβή προτείνονται μέθοδοι διαχείρισης των κοινόχρηστων πόρων σε υπολογιστικά συστήματα όπου πολλαπλοί επεξεργαστές μοιράζονται το ίδιο ολοκληρωμένο (Chip Multiprocessors – CMPs). Ενώ μέχρι πρόσφατα ο σχεδιασμός ενός υπολογιστικού συστήματος στόχευε στην ικανοποίηση των απαιτήσεων μόνο μίας εφαρμογής ανά χρονική περίοδο, τώρα πια απαιτείται και η εξισορρόπηση των απαιτήσεων διαφορετικών εφαρμογών που ανταγωνίζονται για την κατοχή των ίδιων πόρων. Σε πολλές περιπτώσεις, όμως, αυτό δεν αρκεί από μόνο του. Ακόμη και αν επιτευχθεί κάποιος ιδανικός διαμοιρασμός του πόρου, αν δεν βελτιστοποιηθεί ο τρόπος με τον οποίο χρησιμοποιούν οι επεξεργαστές τον κοινόχρηστο πόρο, δεν θα καταφέρει να εξυπηρετήσει ικανοποιητικά το αυξημένο φορτίο. Για να αντιμετωπιστούν τα προβλήματα που πηγάζουν από τον διαμοιρασμό των κοινόχρηστων πόρων, στην παρούσα εργασία προτείνονται τρεις εναλλακτικοί μηχανισμοί διαχείρισης. Η πρώτη μεθοδολογία εισάγει μία νέα θεωρητική μοντελοποίηση του διαμοιρασμού της κρυφής μνήμης, η οποία μπορεί να χρησιμοποιηθεί παράλληλα με την εκτέλεση των προγραμμάτων που διαμοιράζονται την κρυφή μνήμη. Η μεθοδολογία αξιοποιεί στην συνέχεια αυτήν την μοντελοποίηση, για να ελέγξει τον διαμοιρασμό της κρυφής μνήμης και να επιτύχει δικαιοσύνη στο πως κατανέμεται ο χώρος της κρυφής μνήμης μεταξύ των επεξεργαστών. Η δεύτερη μεθοδολογία παρουσιάζει μία νέα τεχνική για την πρόβλεψη της τοπικότητας των προσπελάσεων της κρυφής μνήμης. Καθώς η τοπικότητα είναι η βασική παράμετρος που καθορίζει την χρησιμότητα των δεδομένων της κρυφής μνήμης, χρησιμοποιώντας αυτήν την τεχνική πρόβλεψης μπορούν να οδηγηθούν μηχανισμοί διαχείρισης που βελτιώνουν την αξιοποίηση του χώρου της κρυφής μνήμης. Στα πλαίσια της μεθοδολογίας παρουσιάζουμε έναν τέτοιο μηχανισμό, ο οποίος στοχεύει στην ελαχιστοποίηση των αστοχιών της κρυφής μνήμης μέσω μίας νέας πολιτικής αντικατάστασης. Η τελευταία μεθοδολογία που παρουσιάζεται είναι μία μεθοδολογία για την μείωση της κατανάλωσης ενέργειας της ουράς εντολών, που είναι μία από τις πιο ενεργειακά απαιτητικές δομές του επεξεργαστή. Στα πλαίσια της μεθοδολογίας, δείχνεται ότι το κλειδί για την αποδοτική μείωση της κατανάλωσης ενέργειας της ουράς εντολών βρίσκεται στην αλληλεπίδραση της με το υποσύστημα μνήμης. Με βάση αυτό το συμπέρασμα, παρουσιάζουμε έναν νέο μηχανισμό δυναμικής διαχείρισης του μεγέθους της ουράς εντολών, ο οποίος συνδυάζει επιθετική μείωση της κατανάλωσης ενέργειας του επεξεργαστή με διατήρηση της υψηλής απόδοσής του. / This dissertation proposes methodologies for the management of shared resources in chip multi-processors (CMP). Until recently, the design of a computing system had to satisfy the computational and storage needs of a single program during each time period. Now instead, the designer has to balance the, perhaps conflicting, needs of multiple programs competing for the same resources. But, in many cases, even this is not enough. Even if we could invent a perfect way to manage sharing, without optimizing the way that each processor uses the shared resource, the resource could not deal efficiently with the increased load. In order to handle the negative effects of resource sharing, this dissertation proposes three management mechanisms. The first one introduces a novel theoretical model of the sharing of the shared cache, which can be used at run-time. Furthermore, out methodology uses the model to control sharing and to achieve a sense of justice in the way the cache is shared among the processors. Our second methodology presents a new technique for predicting the locality of cache accesses. Since locality determines, almost entirely, the usefulness of cache data, our technique can be used to drive any management mechanism which strives to improve the efficiency of the cache. As part of our methodology, we present such a mechanism, a new cache replacement policy which tries to minimize cache misses by near-optimal replacement decisions. The last methodology presented in this dissertation, targets the energy consumption of the processor. To that end, our methodology shows that the key to reducing the power consumption of the Issue Queue, without disproportional performance degradation, lies at the interaction of the Issue Queue with the memory subsystem: as long as the management of the Issue Queue doesn’t reduce the utilization of the memory subsystem, the effects of the management on the processor’s performance will be minimal. Based on this conclusion, we introduce a new mechanism for dynamically resizing the Issue Queue, which achieves aggressive downsizing and energy savings with almost no performance degradation.

Στην παρούσα διπλωματική εργασία μελετάται έλεγχος της λειτουργίας ενός πλήθους διαφορετικών τεχνολογιών δικτύου, όπως το Ψηφιακό Δίκτυο Ενοποιημένων Υπηρεσιών (Integrated Services Digital Network, ISDN), ο ψηφιακός βρόχος συνδρομητή (Digital Subscriber Loop), οι τεχνολογίες SHDSL,VDSL κ.α. Αφότου έγινε μια εκτενής περιγραφή των περισσότερων τύπων δικτύων και διεξοδική μελέτη των λειτουργιών τους, προσδιορίστηκαν οι τεχνολογίες δικτύου που είναι εφικτό να μελετηθούν στα πλαίσια ενός εργαστηριακού μαθήματος. Για την επίτευξη του στόχου αυτού δη-μιουργήθηκαν μια σειρά εργαστηριακών ασκήσεων που βοηθούν στην κατανόηση τόσο των συγκεκριμένων τεχνολογιών (και των μεταξύ τους διαφορών) όσο και των πολυάριθμων ελέγχων που είναι δυνατό να διεξαχθούν για την παρακολούθηση και συντήρηση των συγκεκριμένων δικτύων. Εν κατακλείδι η εργασία αποτελεί ένα χρήσιμο εργαλείο για τη μελέτη των πιο σημαντικών τεχνολογιών δικτύου. / This diploma thesis examines the monitoring of the functions, of many network technologies such as the Integrated Services Digital Network (ISDN), the Digital Subscriber Loop (DSL), the SHDSL, VDSL technologies and more. After an extensive reference of the most network types and a comprehensive study of their functions, it has been determined which of those is possible to be examined as a part of lab course. In order for this goal to be achieved, it has been created a set of laboratory exercises that help in the understanding of these network technologies, the differences between them and the multiple tests that can be conducted for the monitoring and maintenance of those networks. In conclusion this diploma thesis is useful tool in the study of the most important network technologies.

Το κάτωθι κείμενο πραγματεύεται το φαινόμενο της εξάπλωσης αυτοαναπαραγόμενων αυτομάτων σε δίκτυα. Αρχικά προβαίνουμε σε μια εισαγωγή στα αυτοαναπαραγόμενα προγράμματα και στο περιβάλλον στο οποίο εξαπλώνονται και εν συνεχεία εμβαθύνουμε στον τρόπο με τον οποίο προσεγγίζουμε το φαινόμενο. Μελετάμε μεθόδους ανίχνευσης με χρήση φίλτρων Kalman και εντροπίας. Τέλος, ασχολούμαστε με μια σειρά παιγνίων και σεναρίων με σκοπό την ανάδειξη συγκεκριμένων πλευρών του όλου προβλήματος και την τροπή που παίρνει στις μέρες μας. Εν κατακλείδι, η παρούσα διπλωματική εργασία τονίζει βασικές ιδιότητες που χαρακτηρίζουν την διάδοση και εισάγει νέες βοηθητικές έννοιες και μοντέλα, με στόχο την κατανόηση και τον ενστερνισμό του πνεύματος των εξελίξεων στα σύγχρονα worms και viruses. / The text below considers the phenomenon of propagation of self replicating automata. We begin with an introduction to self replicating programs and to the environment in which they propagate and then we delve and explain the ways of approaching the phenomenon. We study detection methods via the use of Kalman filters and estimation of entropy. Finally, a series of games and scenarios are introduced and studied, in order to enlighten certain aspects of the problem and its current direction. In conclusion, this diploma thesis marks basic properties of the propagation and introduces auxiliary concepts and new models, having as a goal the comprehension and the adoption of the spirit of evolution of modern worms and viruses.