H παρούσα ερευνητική εργασία αφορά την εκτίμηση της απόδοσης πολυβάθμιων διασυνδεδεμένων δικτύων μεταγωγής. Για την εκτίμηση της απόδοσης αναπτύχθηκαν προσεγγιστικά αναλυτικά μοντέλα τα οποία και παρουσιάζονται στην εργασία αυτή. Πιο συγκεκριμένα: 1. Παρουσιάζεται μια πρωτότυπη ολοκληρωμένη μεθοδολογία εύρεσης της απόδοσης αυτό-δρομολογούμενων απλών πολυβάθμιων διασυνδεδεμένων δικτύων (πχ κλασσικά δίκτυα banyan) τα οποία συγκροτούνται από συμμετρικά στοιχειώδη συστήματα μεταγωγής (πχ 2x2 Switch Element). Το μοντέλο που δημιουργήθηκε βασίστηκε στην λειτουργία και την συμπεριφορά μιας τυχαίας μνήμης (ουράς) ενός στοιχειώδους συστήματος μεταγωγής. Βασιζόμενοι στην ανάλυση, η οποία συμπεριλαμβάνει έναν επαναληπτικό αλγόριθμο ο οποίος συγκλίνει σε πολύ λίγες επαναλήψεις, υπολογίζουμε την Χρησιμοποίηση των ουρών του συστήματος. Στην συνεχεία προσδιορίζουμε τους λοιπούς δείκτες απόδοσης. 2. Παρουσιάζεται διαδικασία εκτίμησης της απόδοσης πολυβάθμιων διασυνδεδεμένων δικτύων μεταγωγής, τα οποία έχουν την ικανότητα να εξυπηρετούν φορτίο με δύο οι περισσότερες προτεραιότητες. Προτάθηκε ένα στοιχειώδες σύστημα μεταγωγής (SE- Switch Element) το οποίο διαθέτει παράλληλες μνήμες σε κάθε είσοδο, μία για κάθε υποστηριζόμενη προτεραιότητα φορτίου, και το οποίο μοντελοποιήθηκε με την βοήθεια ουρών. Βασιζόμενοι στην ανάλυση του μοντέλου αυτού και με την βοήθεια σχετικού επαναληπτικού αλγορίθμου ο οποίος συγκλίνει με λίγες επαναλήψεις, υπολογίστηκαν με ακρίβεια όλοι οι δείκτες απόδοσης. 3. Επιπρόσθετα, αναπτύσσεται μια ακόμη πρωτότυπη αναλυτική προσέγγιση η οποία παρέχει την εκτίμηση της απόδοσης πολυβάθμιων διασυνδεδεμένων δικτύων μεταγωγής με ένα ή περισσότερα επίπεδα τα οποία εφαρμόζουν ως τεχνική εκπομπής πακέτων την τεχνική ‘full multicast’, όταν τα δίκτυα αυτά εξυπηρετούν φορτίο απλής και πολλαπλής εκπομπής (multicast). Δημιουργήθηκε σχετικό μοντέλο για την μελέτη των δικτύων αυτών. Απεδείχθη ότι τα διασυνδεδεμένα δίκτυα τα οποία διαθέτουν περιορισμένο αριθμό επιπέδων, υποστηρίζουν με εξαιρετική αποτελεσματικότητα φορτίο απλής και πολλαπλής εκπομπής (multicast). 4. Αναπτύσσεται και άλλη αναλυτική μελέτη η οποία παρέχει την εκτίμηση της απόδοσης πολυβάθμιων διασυνδεδεμένων δικτύων μεταγωγής με ένα ή περισσότερα επίπεδα τα οποία όμως εφαρμόζουν ως τεχνική εκπομπής πακέτων την τεχνική ‘partial multicast’. 5. Παρουσιάζεται αναλυτική προσέγγιση απόδοσης η οποία αφορά αυτο-δρομολoγούμενα πολυβάθμια συστήματα με περιορισμένα επίπεδα τα οποία όμως εφαρμόζουν ταυτόχρονα δύο διαφορετικές πολιτικές εκπομπής πακέτων, μία σε κάθε τμήμα τους. Και πάλι ακολουθώντας παρόμοια διαδικασία προσδιορίστηκαν όλοι οι δείκτες απόδοσης των πολυβάθμιων δικτύων αυτών 6. Για διευκόλυνση των μελετητών, ορίστηκε ένας γενικός συντελεστής απόδοσης (CPF) του συστήματος ο οποίος εκφράζει την γενική απόδοση μιας πολυβάθμιας συσκευής μεταγωγής πακέτων, λαμβάνοντας υπ όψιν όλους τους ανεξάρτητους δείκτες, με βάση συγκεκριμένα κριτήρια. Αξιοσημείωτο είναι ότι όλες οι αναλυτικές μέθοδοι παρέχουν αναλυτικά αποτελέσματα για όλα τα ενδιάμεσα στάδια. Όλα τα αποτελέσματα τα οποία προέκυψαν από εφαρμογή των αναλυτικών μεθόδων επιβεβαιώθηκαν με προσομοιώσεις που δημιουργήθηκαν γι αυτό τον σκοπό. Επίσης τα αποτελέσματα τα οποία ελήφθησαν από τις αναλυτικές μεθόδους, συγκρίθηκαν με αποτελέσματα από παλαιότερες εργασίες. Η σύγκριση αναδεικνύει την μεγαλύτερη ακρίβεια και ταχύτητα των αναλυτικών μεθόδων που παρουσιάζονται στην παρούσα εργασία έναντι όλων των παλαιοτέρων ερευνητικών τεχνικών. Εξετάζοντας τις σχετική ερευνητική βιβλιογραφία καθίσταται πρόδηλο ότι υπάρχει ανεπάρκεια αναλυτικών μελετών οι οποίες να καλύπτουν θέματα εκτίμησης απόδοσης συγχρόνων δικτύων μεταγωγής, όπως πχ είναι τα πολυεπίπεδα δίκτυα. Οι παραπάνω αναλυτικές προσεγγίσεις αναμένεται να είναι ένα χρήσιμο εργαλείο για τους σχεδιαστές και κατασκευαστές δικτυακών συστημάτων στην προσπάθειά τους να πετύχουν κατασκευή δικτύων με καλύτερη ποιότητα εξυπηρέτησης (QoS). / This research work concerns the performance evaluation of multistage, interconnected switching networks. To assess the performance, approximated analytical models are developed and presented. In particular: 1. A novel integrated methodology for assessing the performance of simple, self-routing, multistage, interconnected networks (e.g. banyan networks), which are formed by symmetrical switch elements, is presented. The model that is created is based on the function and behaviour of a random simple multistage switch system in a memory level (queue). Based on analysis, which includes a repetitive algorithm that converges within a small number of iterations, the queue's’ utilisation is estimated. Subsequently, other performance indicators are determined. 2. A performance evaluation process for multistage interconnection networks, which has the ability to service traffic with two or more classes of priorities, is presented. Particularly, a new switch element which has parallel memories in each entry is proposed to ensure effective servicing of multi-priority traffic. This switch element has one memory for each supported class of priority, and is modelled by means of queues. Based on the analysis provided by this model, and in conjunction with the application of a repetitive algorithm which converges with few iterations, all performance indicators were precisely calculated. 3. In addition, a novel analytical approach was developed that provides a performance evaluation of multistage interconnection networks that have one or more levels which apply the packet transmission ‘full multicast’ method when these networks serve unicast and multicast traffic. A relevant study model for those networks was created. It appears that the interconnected networks which have a limited number of levels lend excellent support with effective unicast and multicast traffic. 4. The study provides a performance evaluation of multistage interconnection networks with one or more levels, and uses a technical transmission packet technique for multicast traffic, the ‘partial multicast’ operation. 5. Also is presented an analytical approach that estimates a performance evaluation of self-routing, multistage interconnection networks (which have a limited number of levels) that apply two different transmission packet techniques in each segment. By application of a similar procedure, all the performance indicators of multistage networks are identified. 6. To assist designers, a compound performance factor (CPF) is defined which expresses the overall performance evaluation of multistage interconnection network devices (taking into account all the individual performance factors, according to a specific set of criteria). It is noteworthy that all of the analytical methods provide detailed results for all intermediate stages. All of the results obtained by application of analytical methods are confirmed by simulations. The results garnered by analytical methods are also compared with the results from previous work. The comparison highlights the greater accuracy and speed that these analytical methods have over older research techniques. Examination of the relevant research literature makes it evident that there is an insufficient number of analytical studies which cover the performance evaluation issue relating to modern switched networks; for example, multi-layered networks. This gap in the field of research is completed by this work. These analytical approaches will be useful tools for designers and manufacturers of network systems in their efforts to provide better quality of service (QoS).

Στη σύγχρονη εποχή, η ανάπτυξη των ετερογενών και κατανεμημένων περιβαλλόντων, όπως τα περιβάλλοντα πλέγματος, καθιστά εφικτή την επίλυση υπολογιστικά εντατικών προβλημάτων με αξιόπιστο και οικονομικό τρόπο. Το Πλέγμα Υπολογιστών είναι μια αναπτυσσόμενη υποδομή που παρέχει πρόσβαση σε υπολογιστική ισχύ και αποθηκευτικό χώρο κατανεμημένα σε όλο τον κόσμο. Εισήχθη για να ικανοποιήσει την ανάγκη για εφαρμογές που απαιτούν μεγάλο αριθμό υπολογισμών καθώς και την επικοινωνία των ατόμων που τις εκτελούν. Ένα πρόβλημα που μπορεί να εκμεταλλευτεί τα πλεονεκτήματα του Πλέγματος είναι το πρόβλημα χρονοπρογραμματισμού πληρωμάτων. Το συγκεκριμένο πρόβλημα είναι πολύπλοκο και χρονοβόρο εξαιτίας των πολλών περιορισμών που συνδέονται με αυτό. Στην παρούσα διπλωματική εργασία παρουσιάζεται με λεπτομέρεια η δομή και ο τρόπος λειτουργίας και εξυπηρέτησης χρηστών του Πλέγματος. Επίσης, καταγράφουμε τη μεθοδολογία και τον τρόπο υποβολής εργασιών στο Πλέγμα από τη σκοπιά του χρήστη. Επικεντρώνουμε το ενδιαφέρον μας στην αποδοτική επίλυση του προβλήματος χρονοπρογραμματισμού ανθρωπίνων πόρων, συγκεκριμένα του νοσηλευτικού προσωπικού ενός νοσοκομείου, με χρήση παράλληλης επεξεργασίας σε περιβάλλον δικτύου υπολογιστών. / -

There are a number of known architectural patterns for TCP/IP server design. I present a survey of design choices based on some of the most common of these patterns. I have demonstrated, with working code samples, that most of these architectural patterns are readily portable between UNIX and Windows NT platforms without necessarily incurring significant performance penalties. / Computing / M. Sc. (Computer Science)

Dans les pays développés tels que le Canada ou la France, la population est vieillissante et le nombre de personnes atteintes de déficiences cognitives augmente en conséquence. Ces troubles ont des conséquences sur les activités de la vie quotidienne pour les personnes qui en souffrent. Selon l’autonomie de ces personnes et la sévérité de leur déficience, un hébergement en centre spécialisé peut être envisagé. Ces centres spécialisés représentent souvent un coût financier énorme tant pour la personne que pour la société. Afin de limiter ces coûts, une solution alternative a émergé : les habitats domotiques. Ce sont des habitats dans lesquels un ensemble de technologies permet de pallier aux déficiences des personnes et de leur donner une autonomie accrue. L’activité de préparation d’un repas est une activité complexe qui peut présenter des risques variés pour des personnes atteintes de déficiences. Ces personnes vivent rarement seules, il faut tenir compte qu’un public varié puisse bénéficier du système. Ces habitats sont généralement déjà équipés d’appareils, il devient nécessaire pour le système de pouvoir s’adapter à ces appareils existants. L’objectif de ces travaux est la réalisation d’un prototype permettant d’assurer la sécurité lors de l’activité de la préparation d’un repas par des personnes atteintes de la maladie d’Alzheimer et ses aidants (professionnels ou naturels). Ce prototype doit s’adapter au profil des usagers, de son environnement et du matériel sur lequel il est déployé. Pour ce faire, le système, basé sur un système multi agent, applique des règles de sécurité qui se personnalisent par le biais du profil médical des usagers. Nos travaux ont été menés au sein de deux laboratoires, qui chacun, disposent d’appareils de cuisine différents dans leurs habitats intelligents pour la santé. Le système a pu être testé dans ces deux environnements, son adaptation vis-à-vis d’une clientèle variée et pour plusieurs risques de sécurité à travers des scénarios d’usage. Les résultats de ces expérimentations ont permis de montrer que le prototype répond bien aux objectifs visés. / In developed countries such as Canada or France, the population is ageing and the number of people with disabilities increases. Those disabilities have an impact on their activities of daily living. According to the severity of the disability and the independance of those people, a placement in a specialized institution can be considered. Those institutions often represent huge financial costs for the people as for society. In order to reduce those costs, smart homes are an alternative solution. Smart homes make it possible for people to compensate their disabilities and increase their independance through a set of technologies. Preparing a meal is a complex activity can present various risks for those people. These people rarely live alone, and it must be taken into account that a varied public can use the system. Homes are usually already equipped with appliances, it is necessary for the system to adapt itself to these devices. This work aims the implementation of a prototype ensuring the safety of people with Alzheimer during meal preparation and their caregivers (natural or professional). The prototype must adapt itself to the user’s profiles, its environment and the appliances on which it is deployed. In order to do this, the system, based on a multi agent system, applies safety rules that are customizable through the users’ medical profiles. This work is carried out in two laboratories, each with distinct kitchen appliances in their smart home. The system had been tested in both environments, its adaptation towards different users and for several safety rules through use cases. The results of these experiments showed that the prototype meets the objectives.

Les réseaux mobiles opportunistes (ou OppNets, pour Opportunistic Networks) constituent une solution séduisante pour compléter les réseaux fixes d’infrastructure, voire compenser leur absence dans des zones sinistrées ou défavorisées. Les recherches menées ces dernières années ont principalement visé à permettre les transmissions dans les OppNets, mais ceci ne peut être qu’un premier pas vers une réelle exploitation de tels environnements contraints. L’informatique opportuniste (Opportunistic Computing) dépasse le cadre des seules transmissions, et introduit un nouveau paradigme d’exécution de tâches collaboratives dans de tels environnements. Dans ce domaine qu’est l’informatique opportuniste, la conception, la mise en œuvre et le déploiement d’applications distribuées sont des objectifs majeurs. Une application pour OppNet doit pouvoir fonctionner et assurer un niveau de service satisfaisant, tout en supportant les diverses contraintes propres aux OppNets, telles qu’une connectivité fluctuante, un partitionnement chronique du réseau, de longs délais de transmissions, de fréquents échecs de transmission, et des équipements hétérogènes offrant des ressources limitées. La complexité et le coût du développement d’applications pour OppNets peuvent être réduits de manière significative en utilisant des modèles de programmation appropriés. De tels modèles peuvent être fournis par des systèmes intergiciels capables de supporter de manière transparente les contraintes évoquées plus haut. Le travail rapporté dans ce mémoire a porté sur l’étude des contraintes inhérentes aux OppNets, et sur la proposition de solutions appropriées. Parmi les modèles de programmation usuels, certains ont été identifiés comme pouvant être utilisés dans le cadre des OppNets. Sur la base de ces divers modèles de programmation, des systèmes intergiciels opportunistes ont été mis en oeuvre. Ces systèmes supportent respectivement le modèle de messagerie distribuée (sur la base de files d’attentes et de "topics"), le modèle du tuple-space, et la résolution de consensus. Des implémentations complètes ont été réalisées, et le code source est distribué sous licence GPL (GNU General Public License). Ces systèmes ont été évalués par le biais d’expérimentations menées en conditions réelles et par simulation. / Opportunistic networks (OppNets) constitute an appealing solution to complement fixed network infrastructures –or make up for the lack thereof– in challenged areas. Researches in the last few years have mostly addressed the problem of supporting networking in OppNets, yet this can only be a first step towards getting real benefit from these networks. Opportunistic computing goes beyond the concept of opportunistic networking, and provides a new paradigm to enable collaborative computing tasks in such environments. In the realm of opportunistic computing, properly designing, implementing and deploying distributed applications are important tasks. An OppNet-dedicated application must be able to operate and maintain an acceptable level of service while addressing the many problems that can occur in these networks, such as disconnections, partitioning, long transmission delays, transmission failures, resource constraints, frequent changes in topology, and heterogeneous devices. Much of the complexity and cost of building OppNet-dedicated applications can be alleviated by the use of high-level programming models. Such models can be supported by middleware systems capable of transparently addressing all the above-mentioned problems. The work reported in this dissertation focused on providing insight into the fundamental problems posed by OppNets, so as to analyze and solve the problems faced by application developers while dealing with these environments. The research focused on identifying well-known high-level programming models that can be satisfactorily implemented for OppNets, and that can prove useful for application developers. In order to demonstrate the feasibility of application development for OppNets, while assessing the benefits brought about by carefully designed middleware systems, a couple of such systems have been designed, implemented, and evaluated as part of this work. These middleware systems respectively support distributed messaging (through message queues and topics), the tuple-space model, and consensus solving in OppNets. They are supplemented with fully-functional implementations, that can be used in real settings, and that are all distributed under the terms of the GNU General Public License (GPL). Real-life experiments and simulations have been realized so as to evaluate the effectiveness and efficiency of these systems in real conditions.

Le développement des systèmes massivement parallèles de type manycores permet d'obtenir une très grande puissance de calcul à bas coût énergétique. Cependant, l'exploitation des performances de ces architectures dépend de l'efficacité de programmation des applications. Parmi les différents paradigmes de programmation existants, celui à mémoire partagée est caractérisé par une approche intuitive dans laquelle tous les acteurs disposent d'un accès à un espace d'adressage global. Ce modèle repose sur l'efficacité du système à gérer les accès aux données partagées. Le système définit les règles de gestion des synchronisations et de stockage de données qui sont prises en charge par les protocoles de cohérence. Dans le cadre de cette thèse nous avons montré qu'il n'y a pas un unique protocole adapté aux différents contextes d'application et d'exécution. Nous considérons que le choix d'un protocole adapté doit prendre en compte les caractéristiques de l'application ainsi que des objectifs donnés pour une exécution. Nous nous intéressons dans ces travaux de thèse au choix des protocoles de cohérence en vue d'améliorer les performances du système. Nous proposons une plate-forme de compilation pour le choix et le paramétrage d'une combinaison de protocoles de cohérence pour une même application. Cette plate- forme est constituée de plusieurs briques. La principale brique développée dans cette thèse offre un moteur d'optimisation pour la configuration des protocoles de cohérence. Le moteur d'optimisation, inspiré d'une approche évolutionniste multi-objectifs (i.e. Fast Pareto Genetic Algorithm), permet d'instancier les protocoles de cohérence affectés à une application. L'avantage de cette technique est un coût de configuration faible permettant d'adopter une granularité très fine de gestion de la cohérence, qui peut aller jusqu'à associer un protocole par accès. La prise de décision sur les protocoles adaptés à une application est orientée par le mode de performance choisi par l'utilisateur (par exemple, l'économie d'énergie). Le modèle de décision proposé est basé sur la caractérisation des accès aux données partagées selon différentes métriques (par exemple: la fréquence d'accès, les motifs d'accès à la mémoire, etc). Les travaux de thèse traitent également des techniques de gestion de données dans la mémoire sur puce. Nous proposons deux protocoles basés sur le principe de coopération entre les caches répartis du système: Un protocole de glissement des données ainsi qu'un protocole inspiré du modèle physique du masse-ressort. / Manycores architectures consist of hundreds to thousands of embedded cores, distributed memories and a dedicated network on a single chip. In this context, and because of the scale of the processor, providing a shared memory system has to rely on efficient hardware and software mechanisms and data consistency protocols. Numerous works explored consistency mechanisms designed for highly parallel architectures. They lead to the conclusion that there won't exist one protocol that fits to all applications and hardware contexts. In order to deal with consistency issues for this kind of architectures, we propose in this work a multi-protocol compilation toolchain, in which shared data of the application can be managed by different protocols. Protocols are chosen and configured at compile time, following the application behaviour and the targeted architecture specifications. The application behaviour is characterized with a static analysis process that helps to guide the protocols assignment to each data access. The platform offers a protocol library where each protocol is characterized by one or more parameters. The range of possible values of each parameter depends on some constraints mainly related to the targeted platform. The protocols configuration relies on a genetic-based engine that allows to instantiate each protocol with appropriate parameters values according to multiple performance objectives. In order to evaluate the quality of each proposed solution, we use different evaluation models. We first use a traffic analytical model which gives some NoC communication statistics but no timing information. Therefore, we propose two cycle- based evaluation models that provide more accurate performance metrics while taking into account contention effect due to the consistency protocols communications.We also propose a cooperative cache consistency protocol improving the cache miss rate by sliding data to less stressed neighbours. An extension of this protocol is proposed in order to dynamically define the sliding radius assigned to each data migration. This extension is based on the mass-spring physical model. Experimental validation of different contributions uses the sliding based protocols versus a four-state directory-based protocol.

La multiplication du nombre d'objets, qui ont vocation à être connectés à Internet (e.g., smartphones, capteurs), et la croissance des échanges de données effectués par des individus en situation de mobilité ont conduit, et conduiront encore, à une augmentation significative du trafic de données dans les réseaux, et en particulier dans les réseaux cellulaires. Les récents progrès réalisés au niveau de la couche physique pour accroître les débits dans ces réseaux pourraient s'avérer insuffisants dans le futur avec l'émergence d'un Internet des objets. Il nous semble dès lors intéressant d'étudier des architectures réseau alternatives ou complémentaires. Les réseaux hybrides à connectivité intermittente (RHCI), qui sont constitués d'une infrastructure et de parties formées par des objets fixes ou mobiles communiquant en mode ad hoc, font partie de ces architectures qui méritent d'être étudiées. Dans cette thèse, nous étudions les bénéfices que pourrait apporter l'utilisation des techniques des réseaux pair-à-pair et des communications opportunistes dans les RHCI. Nous proposons une architecture pair-à-pair décentralisée et non structurée qui permet d'assurer les communications entre des objets dans des RHCI de grande taille via différents modes de communication. Un prototype de plateforme, baptisé Nephila a été développé, pour évaluer cette approche en simulation. / The number of devices that are likely to get connected to the Internet (e.g., smartphones, sensors), and the amount of data produced by people using these devices grow continuously, especially in cellular networks. Latest developments performed on the physical layer to increase the networks' bandwidth might be insufficient in the future, because of the emergence of the Internet of things. Therefore, it seems to be interesting to study new or complementary network architectures. Intermittently-Connected Hybrid Networks (ICHN), which are composed both of an infrastructure part and of parts formed by mobile device communicating using ad hoc mode, are examples of those architectures that deserve to be studied. In this thesis, we study benefits that peer-to-peer mechanisms and opportunistic networking techniques could bring to ICHN. We propose a decentralized unstructured peer-to-peer overlay architecture that supports communications between devices in wide ICHNs. A prototype named Nephila has been developed to evaluate this approach in simulation.

L’informatique multi-nuages s’est imposée comme un paradigme de choix pour créer des applications distribuées à large échelle s’exécutant à des emplacements géographiques répartis. L’informatique multi-nuages consiste en l’utilisation de multiples environnements de nuages indépendants qui ne nécessitent pas d’accord a priori entre les fournisseurs de nuage ou un tiers. Toutefois, ces applications conçues pour un environnement multi-nuages doivent faire face à de véritables défis en terme d’architecture, de modèle et de technologies. L’utilisation de l’informatique multi-nuages se heurte à l’hétérogénéité et à la complexité des offres de nuage. Ainsi, l’informatique multi-nuages doit faire face aux défis de la portabilité, de l’approvisionnement, de l’élasticité et de la haute disponibilité que nous identifions dans cette thèse.Dans ce travail de thèse, nous proposons un modèle d’applications nommé soCloud qui adresse ces quatre défis. C’est un modèle basé sur le standard SCA du consortium OASIS pour concevoir de manière simple et cohérente des applications distribuées à large échelle pour un environnement multi-nuages. Un nouveau langage dédié d’élasticité a été proposé pour exprimer efficacement l’élasticité d’applications multi-nuages par l’abstraction. Nous proposons aussi une plateforme multi-nuages soCloud conçue pour déployer, exécuter et gérer des applications réparties à travers plusieurs nuages. Le modèle d’applications soCloud a été utilisé pour la mise en œuvre de trois applications distribuées déployées dans un environnement multi-nuages. Quant à la plateforme soCloud, elle a été implantée, déployée et expérimentée sur dix nuages. / Multi-cloud computing has established itself as a paradigm of choice for creating very large scale world wide distributed applications. Multi-cloud computing is the usage of multiple, independent cloud environments, which assumed no priori agreement between cloud providers or third party. However, these applications, designed for multi-cloud envi-ronments, have to face real challenges in term of design, architecture, and technology. The possibility of using multi-cloud faces the heterogeneity and complexity of cloud solutions.Thus, multi-cloud computing has to face several challenges such as portability, provisioning, elasticity, and high availability we have identified in this thesis. In this thesis, we propose soCloud both amodel and a platformthat tackle these four chal-lenges. This model is based on the OASIS Service Component Architecture (SCA) standard to design distributed large scale applications for multi-cloud environments. Anew language is proposed to effectively express the elasticity of multi-cloud applications through abstrac-tion. The multi-cloud platform is designed to deploy and manage distributed applications across multi-clouds. The soCloud model is illustrated on three distributed applications deployed in multi-cloud environments. The soCloud platform has been implemented, deployed and experi-mented on top of ten existing cloud providers.These experiments are used to validate the novelty of the contributed solutions. With our contributions, we aim to provide a simple and effective way to design, deploy, run, and manage distributed applications for a multi-cloud environment by proposing a model and platform.

Cette thèse est consacrée au problème d'ordonnancement de tâches qui consiste à minimiser la somme de l'énergie consommée et le temps d'attente pondéré total, et l'aborde de deux différents points de vue : centralisé et décentralisé. Pour l'approche décentralisée, nous avons défini deux types de jeux qui diffèrent dans les actions proposées aux joueurs et avons cherché des moyens de facturer l'énergie consommée aux utilisateurs pour les inciter à adopter un bon comportement. Concrètement nous nous intéressons à l'existence d'équilibres de Nash purs, au temps de convergence vers ces équilibres, et au rapport entre l'énergie consommée et le montant des factures. Pour l'approche centralisée, nous avons réduit le problème de minimisation à un problème d'ordonnancement plus classique avec une fonction de pénalité de retard polynomiale concave, pour lequel peu résultats ont été connus. Après avoir établi un état de l'art sur la famille de problèmes d'ordonnancement pour plusieurs fonctions de pénalité élémentaires et montré qu'une technique de preuve de NP-complétude classique échoue ici, nous nous sommes intéressés à sa résolution exacte. Pour améliorer les performances de l'algorithme A* dans ce contexte, nous avons montré des résultats de règles de dominance. Concrètement, nous avons cherché à déterminer les conditions sous lesquelles une solution optimale devrait ordonnancer une paire de tâches dans un certain ordre. Ces résultats sont appuyés par une étude expérimentale qui évalue l'impact pratique de ces nouvelles règles, par rapport aux règles existantes. / This thesis focuses on a job scheduling problem with the goal of minimizing the sum of energy consumption and the weighted flow time from two different approaches: centralized and decentralized. In the decentralized setting, we defined two games which differ in the strategies players can choose from and designed cost sharing mechanisms, charging the consumed energy to the users in order to incentive a socially desirable behavior. More precisely we were interested in the existence of pure Nash equilibria, in the convergence time, and the ratio between the consumed energy and the total charged amount. On the other side, for the centralized approach, we reduced the minimization problem to a classical scheduling problem with a polynomial concave penalty function, for which little results were known. We established a state of the art for a family of scheduling problems of this form with different penalty functions and showed that a classical NP-completeness proof technique fails here. Finally we addressed the exact resolution of the problem using the algorithm A*. In this context, we showed new order dominance rules. More precisely, we characterized the conditions under which any optimal solution must schedule a job pair in a certain order. In addition we carried out a computational experience to evaluate the practical impact of these new rules compared to the existing ones.

Cette thèse porte sur la résolution exacte et heuristique de plusieurs problèmes ayant des applications dans le domaine de l'Informatique dématérialisé (cloud computing). L'Informatique dématérialisée est un domaine en plein extension qui consiste à mutualiser les machines/serveurs en définissant des machines virtuelles représentant des fractions des machines/serveurs. Il est nécessaire d'apporter des solutions algorithmiques performantes en termes de temps de calcul et de qualité des solutions. Dans cette thèse, nous nous sommes intéressés dans un premier temps au problème d'ordonnancement sur plusieurs machines (les machines virtuelles) avec contraintes de précédence, c.-à-d., que certaines tâches ne peuvent s'exécuter que si d'autres sont déjà finies. Ces contraintes représentent une subdivision des tâches en sous tâches pouvant s'exécuter sur plusieurs machines virtuelles. Nous avons proposé plusieurs algorithmes génétiques permettant de trouver rapidement une bonne solution réalisable. Nous les avons comparés avec les meilleurs algorithmes génétiques de la littérature et avons défini les types d'instances où les solutions trouvées sont meilleures avec notre algorithme. Dans un deuxième temps, nous avons modélisé ce problème à l'aide de la programmation linéaire en nombres entiers permettant de résoudre à l'optimum les plus petites instances. Nous avons proposé de nouvelles inégalités valides permettant d'améliorer les performances de notre modèle. Nous avons aussi comparé cette modélisation avec plusieurs formulations trouvées dans la littérature. Dans un troisième temps, nous avons analysé de manière approfondie la sous-structure du sous-graphe d'intervalle ne possédant pas de clique de taille donnée. Nous avons étudié le polytope associé à cette sous-structure et nous avons montré que les facettes que nous avons trouvées sont valides pour le problème d'ordonnancement sur plusieurs machines avec contraintes de précédence mais elles le sont aussi pour tout problème d'ordonnancement sur plusieurs machines. Nous avons étendu la modélisation permettant de résoudre le précédent problème afin de résoudre le problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches, c.-à-d., que certaines tâches ne peuvent s'exécuter en même temps que d'autres. Ces contraintes représentent le partage de ressources critiques ne pouvant pas être utilisées par plusieurs tâches. Nous avons proposé des algorithmes de séparation afin d'insérer de manière dynamique nos facettes dans la résolution du problème puis avons développé un algorithme de type Branch-and-Cut. Nous avons analysé les résultats obtenus afin de déterminer les inégalités les plus intéressantes afin de résoudre ce problème. Enfin dans le dernier chapitre, nous nous sommes intéressés au problème d'ordonnancement d'atelier généralisé ainsi que la version plus classique d'ordonnancement d'atelier (open shop). En effet, le problème d'ordonnancement d'atelier généralisé est aussi un cas particulier du problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches. Nous avons proposé une formulation à l'aide de la programmation mathématique pour résoudre ces deux problèmes et nous avons proposé plusieurs familles d'inégalités valides permettant d'améliorer les performances de notre algorithme. Nous avons aussi pu utiliser les contraintes définies précédemment afin d'améliorer les performances pour le problème d'ordonnancement d'atelier généralisé. Nous avons fini par tester notre modèle amélioré sur les instances classiques de la littérature pour le problème d'ordonnancement d'atelier. Nous obtenons de bons résultats permettant d'être plus rapide sur certaines instances / The Cloud Computing appears as a strong concept to share costs and resources related to the use of end-users. As a consequence, several related models exist and are widely used (IaaS, PaaS, SaaS. . .). In this context, our research focused on the design of new methodologies and algorithms to optimize performances using the scheduling and combinatorial theories. We were interested in the performance optimization of a Cloud Computing environment where the resources are heterogeneous (operators, machines, processors...) but limited. Several scheduling problems have been addressed in this thesis. Our objective was to build advanced algorithms by taking into account all these additional specificities of such an environment and by ensuring the performance of solutions. Generally, the scheduling function consists in organizing activities in a specific system imposing some rules to respect. The scheduling problems are essential in the management of projects, but also for a wide set of real systems (telecommunication, computer science, transportation, production...). More generally, solving a scheduling problem can be reduced to the organization and the synchronization of a set of activities (jobs or tasks) by exploiting the available capacities (resources). This execution has to respect different technical rules (constraints) and to provide the maximum of effectiveness (according to a set of criteria). Most of these problems belong to the NP-Hard problems class for which the majority of computer scientists do not expect the existence of a polynomial exact algorithm unless P=NP. Thus, the study of these problems is particularly interesting at the scientific level in addition to their high practical relevance. In particular, we aimed to build new efficient combinatorial methods for solving parallel-machine scheduling problems where resources have different speeds and tasks are linked by precedence constraints. In our work we studied two methodological approaches to solve the problem under the consideration : exact and meta-heuristic methods. We studied three scheduling problems, where the problem of task scheduling in cloud environment can be generalized as unrelated parallel machines, and open shop scheduling problem with different constraints. For solving the problem of unrelated parallel machines with precedence constraints, we proposed a novel genetic-based task scheduling algorithms in order to minimize maximum completion time (makespan). These algorithms combined the genetic algorithm approach with different techniques and batching rules such as list scheduling (LS) and earliest completion time (ECT). We reviewed, evaluated and compared the proposed algorithms against one of the well-known genetic algorithms available in the literature, which has been proposed for the task scheduling problem on heterogeneous computing systems. Moreover, this comparison has been extended to an existing greedy search method, and to an exact formulation based on basic integer linear programming. The proposed genetic algorithms show a good performance dominating the evaluated methods in terms of problems' sizes and time complexity for large benchmark sets of instances. We also extended three existing mathematical formulations to derive an exact solution for this problem. These mathematical formulations were validated and compared to each other by extensive computational experiments. Moreover, we proposed an integer linear programming formulations for solving unrelated parallel machine scheduling with precedence/disjunctive constraints, this model based on the intervaland m-clique free graphs with an exponential number of constraints. We developed a Branch-and-Cut algorithm, where the separation problems are based on graph algorithms. [...]