No description available.

The Message Passing Interface (MPI) standard defines virtual topologies that can be applied to systems of cooperating processes. Among issues regarding a more convenient namespace this may be used to optimize the placement of MPI processes in order to reduce communication time. That means, the processes with their main communication paths represent a graph that has to be cost efficiently mapped onto the graph representing the actual communication network. In this context, this work analyses and compares state-of-the-art task mapping strategies with respect to running time and their quality of solutions to the MPI mapping problem. In particular, the focus is on generic strategies that can be used for arbitrary process/network topologies although, here, the topologies of interest are regular ones, where the number of processes is greater than the number of processors in the underlying physical network. Additionally, different measures of mapping quality are discussed and a close correspondence between the most appropriate, the weighted edge cut, and program execution time is shown. In order to investigate how mapping quality affects MPI program execution time, some mapping strategies have been incorporated into Open MPI. Finally, benchmark results prove that optimized process-to-processor mappings can improve program execution time by up to 60%, compared to the default mapping in many MPI implementations (linear mapping). The findings in this work can serve as reference not only for MPI implementors, but also for researchers investigating static process-to-processor mappings, in general.

In data intensive applications deployed in enterprise networks, especially applications utilizing peer-to-peer technology, locality is of high importance. Peers should aim to maximize data exchange with other peers where the connectivity is the best. In order to achieve this, locality information must be present which peers can base their decisions on. This information is not trivial to find as there is no readily available global knowledge of which nodes have good connectivity. Having each peer try other peers randomly until it finds good enough partners is costly and lowers the locality of the application until it converges. In this thesis a solution is presented which creates a logical topology of a peer-to-peer network, grouping peers into clusters based on their connectivity metrics. This can then be used to aid the peer-to-peer partner selection algorithm to allow for intelligent partner selection. A graph model of the system is created, where peers in the system are modelled as vertices and connections between peers are modelled as edges, with a weight in relation to the quality of the connection. The problem is then modelled as a weighted graph clustering problem which is a well-researched problem with a lot of published work tied to it. State-of-the-art graph community detection algorithms are researched, selected depending on factors such as performance and scalability, optimized for the current purpose and implemented. The results of running the algorithms on the streaming data are evaluated against known information. The results show that unsupervised graph community detection algorithm creates useful insights into networks connectivity structure and can be used in peer-to-peer contexts to find the best partners to exchange data with. / I dataintensiva applikationer i företagsnätverk, speciellt applikationer som använder sig av peer-to-peer teknologi, är lokalitet viktigt. Klienter bör försöka maximera datautbyte med andra klienter där nätverkskopplingen är som bäst. För att klienterna ska kunna göra sådana val måste information om vilka klienter som befinner sig vara vara tillgänglig som klienterna kan basera sina val på. Denna information är inte trivial att framställa då det inte finns någon färdig global information om vilka klienter som har bra uppkoppling med andra klienter och att låta varje klient prova sig fram blint tills de hittar de bästa partnerna är kostsamt och sänker applikationens lokalitet innan den konvergerar. I denna rapport presenteras en lösning som skapar en logisk vy över ett peer-to-peer nätverk, vilken grupperar klienter i kluster baserat på deras uppkopplingskvalitet. Denna vy kan sedan användas för att förbättra lokaliteten i peerto-peer applikationen. En grafmodell av systemet skapas, där klienter modelleras som hörn och kopplingar mellan klienter modelleras som kanter med en vikt i relation till uppkopplingskvaliteten. Problemet formuleras sedan som ett riktat grafklusterproblem vilket är ett väldokumenterat forskningsområde med mycket arbete publicerat kring. De mest framstående grafklusteralgoritmerna är sedan studerade, utvalda baserat på kravspecifikationer, optimerade för det aktuella problemet och implementerade. Resultaten som produceras av att algoritmerna körs på strömdata är evaluerade mot känd information. Resultaten visar att oövervakade grafklusteralgoritmer skapar användbar information kring nätverkens uppkopplingsstruktur och kan användas i peer-to-peerapplikationssammanhang för att hitta de bästa partnerna att utbyta data med.

The Message Passing Interface (MPI) standard defines virtual topologies that can be applied to systems of cooperating processes. Among issues regarding a more convenient namespace this may be used to optimize the placement of MPI processes in order to reduce communication time. That means, the processes with their main communication paths represent a graph that has to be cost efficiently mapped onto the graph representing the actual communication network. In this context, this work analyses and compares state-of-the-art task mapping strategies with respect to running time and their quality of solutions to the MPI mapping problem. In particular, the focus is on generic strategies that can be used for arbitrary process/network topologies although, here, the topologies of interest are regular ones, where the number of processes is greater than the number of processors in the underlying physical network. Additionally, different measures of mapping quality are discussed and a close correspondence between the most appropriate, the weighted edge cut, and program execution time is shown. In order to investigate how mapping quality affects MPI program execution time, some mapping strategies have been incorporated into Open MPI. Finally, benchmark results prove that optimized process-to-processor mappings can improve program execution time by up to 60%, compared to the default mapping in many MPI implementations (linear mapping). The findings in this work can serve as reference not only for MPI implementors, but also for researchers investigating static process-to-processor mappings, in general.

Το ερευνητικό αντικείμενο και ο στόχος της διδακτορικής διατριβής είναι η πρόταση μιας ολοκληρωμένης λύσης για την υποστήριξη τηλεπικοινωνιακών εφαρμογών σε ασύρματα δίκτυα τα οποία δεν στηρίζονται σε σταθερές δικτυακές υποδομές. Ένα τέτοιο δίκτυο, το οποίο αναφέρεται στη διεθνή βιβλιογραφία ως Mobile Ad-hoc Network (MANET), είναι ένα αυτο-οργανώσιμο αυτο-σχηματιζόμενο ασύρματο δίκτυο με διαδρομές πολλαπλών τμημάτων (multi-hop), όπου η δομή του δικτύου αλλάζει δυναμικά λόγω της κινητικότητας των κόμβων ή αλλαγές στην τοπολογία. Η αρχιτεκτονική που προτείνεται για την ικανοποίηση των τιθέμενων απαιτήσεων στηρίζεται στην ανάπτυξη ενός ολοκληρωμένου επικοινωνιακού αρχιτεκτονικού πλαισίου για MANET δίκτυα το οποίο περιλαμβάνει μηχανισμούς μείωσης της κατανάλωσης ενέργειας που οφείλεται σε επικοινωνιακές λειτουργίες, την ανάπτυξη ενός εξειδικευμένου πρωτοκόλλου δρομολόγησης, τροποποιήσεις του πρωτοκόλλου TCP στο επίπεδο μεταφοράς και την υλοποίηση ενός νέου πρωτόκολλου διαχείρισης δικτύου. Η απόδοση της προτεινόμενης επικοινωνιακής διαστρωμάτωσης είναι υψηλή σε περιβάλλον με μεγάλη κινητικότητα των κόμβων και δυναμική αλλαγή της τοπολογίας ενώ παράλληλα η κατανάλωση ενέργειας των κόμβων παραμένει σχετικά χαμηλή. Οι αλγόριθμοι και τα πρωτοκόλλα που παρουσιάζονται σχεδιάστηκαν και υλοποιήθηκαν λαμβάνοντας υπόψη τους περιορισμούς και τις απαιτήσεις ενός ενσωματωμένου συστήματος, ενώ η απόδοση και αξιοπιστία τους τεκμηριώνονται θεωρητικά και με εξομοιώσεις. / The research objective of this thesis is a complete solution so as to support the implementation of telecommunication applications in wireless networks that operate without the presence of fixed infrastructure. Such a network, cited as Mobile Ad-hoc Network (MANET) in international literature, is a self-organized, auto-configured wireless network with multi-hop routing paths where its structure is modified dynamically due to node mobility and topological changes. In order to meet the above requirements a new communication framework for MANET networks is presented, which consists of the adaptation of communication-related energy reduction techniques, development of a specialized routing protocol at the network layer, modifications of the TCP protocol at the transport layer and the implementation of a novel network management protocol. The performance of the proposed protocol stack is satisfactory in dynamic network topologies with increased node mobility, whereas the node energy consumption remains in low levels. The presented algorithms and protocols are designed and implemented considering the constraints and requirements of an embedded system, while their performance and reliability is proved theoretically and by simulation results.

Une maintenance prédictive efficace se base essentiellement sur la fiabilité des données de surveillance.Dans certains cas, la surveillance des systèmes industriels ne peut pas être assurée à l’aide de capteurs individuels ou filaires. Les Réseaux de Capteurs Sans Fil (RCSF) sont alors une alternative. Vu la nature de communication dans ces réseaux, la perte de données est très probable. Nous proposons un algorithme distribué pour la survie des données dans le réseau. Cet algorithme réduit le risque d’une perte totale des paquets de données et assure la continuité du fonctionnement du réseau. Nous avons aussi simulé de différentes topologies du réseau pour évaluer leur impact sur la complétude des données au niveau du nœud puits. Par la suite, nous avons proposé une démarche d’évaluation de l’état de santé de systèmes physiques basée sur l’algorithme des forêts aléatoires. Cette démarche repose sur deux phases : une phase hors ligne et une phase en ligne. Dans la phase hors ligne, l’algorithme des forêts aléatoires sélectionne les paramètres qui contiennent le plus d’information sur l’état du système. Ces paramètres sont utilisés pour construire les arbres décisionnels qui constituent la forêt. Dans la phase en ligne, l’algorithme évalue l’état actuel du système en utilisant les données capteurs pour parcourir les arbres construits. Chaque arbre dans la forêt fournit une décision, et la classe finale est le résultat d’un vote majoritaire sur l’ensemble de la forêt. Quand les capteurs commencent à tomber en panne, les données décrivant un indicateur de santé deviennent incomplètes ou perdues. En injectant de l’aléatoire dans la base d’apprentissage, l’algorithme aura des points de départ différents, et par la suite les arbres aussi. Ainsi, l’absence des mesures d’un indicateur de santé ne conduit pas nécessairement à l’interruption du processus de prédiction de l’état de santé. / An efficient predictive maintenance is based on the reliability of the monitoring data. In some cases, themonitoring activity cannot be ensured with individual or wired sensors. Wireless sensor networks (WSN) arethen an alternative. Considering the wireless communication, data loss becomes highly probable. Therefore,we study certain aspects of WSN reliability. We propose a distributed algorithm for network resiliency and datasurvival while optimizing energy consumption. This fault tolerant algorithm reduces the risks of data loss andensures the continuity of data transfer. We also simulated different network topologies in order to evaluate theirimpact on data completeness at the sink level. Thereafter, we propose an approach to evaluate the system’sstate of health using the random forests algorithm. In an offline phase, the random forest algorithm selects theparameters holding more information about the system’s health state. These parameters are used to constructthe decision trees that make the forest. By injecting the random aspect in the training set, the algorithm (thetrees) will have different starting points. In an online phase, the algorithm evaluates the current health stateusing the sensor data. Each tree will provide a decision, and the final class is the result of the majority voteof all trees. When sensors start to break down, the data describing a health indicator becomes incompleteor unavailable. Considering that the trees have different starting points, the absence of some data will notnecessarily result in the interruption of the prediction process.