Cette thèse porte sur l'efficacité des algorithmes distribués de partage des ressources et des algorithmes de découvert de chemin en ligne. Dans la première partie de la thèse, nous analysons un jeu dans lequel les utilisateurs paient pour utiliser une ressource partagée. La ressource allouée à un utilisateur est directement proportionnel à son paiement. Chaque utilisateur veut minimiser son paiement en assurant une certaine qualité de service. Ce problème est modélisé comme un jeu non-coopératif de partage des ressources. A cause du manque des expressions analytiques de la discipline de file d'attente sous-jacente, nous pouvons résoudre le jeu que sous certaines hypothèses. Pour le cas général, nous développons une approximation basée sur un résultat fort trafic et nous validons la précision de l'approximation numériquement.Dans la deuxième partie, nous étudions l'efficacité des jeux de balance de charge, c'est à dire, nous comparons la perte de performance de routage non coopératif décentralisé avec un routage centralisé. Nous montrons que le PoA est une mesure très pessimiste car il est atteint que dans des cas pathologiques. Dans la plupart des scénarios, les implémentations distribués de balance de charge effectuent presque aussi bien que la mise en œuvre centralisée optimale.Dans la dernière partie de la thèse, nous analysons problème de découverte chemin optimal dans les graphes complets. En ce problème, les valeurs des arêtes sont inconnues, mais peuvent être interrogés. Pour une fonction donnée qui est appliquée à des chemins, l'objectif est de trouver un meilleur chemin de valeur à partir d'une source vers une destination donnée interrogation le plus petit nombre de bords. Nous vous proposons le rapport de requête en tant que mesure de l'efficacité des algorithmes qui permettent de résoudre ce problème. Nous prouvons une limite inférieure pour ne importe quel algorithme qui résout ce problème et nous avons proposé un algorithme avec un rapport de requête strictement inférieure à 2. / This thesis deals with the efficiency of distributed resource sharing algorithms and of online path discovery algorithms. In the first part of the thesis, we analyse a game in which users pay for using a shared resource. The allocated resource to a user is directly proportional to its payment. Each user wants to minimize its payment while ensuring a certain quality of service. This problem is modelled as a non-cooperative resource-sharing game. Due to lack of analytical expressions for the underlying queuing discipline, we are able to give the solution of the game only under some assumptions. For the general case, we develop an approximation based on a heavy-traffic result and we validate the accuracy of the approximation numerically. In the second part, we study the efficiency of load balancing games, i.e., we compare the loss in performance of noncooperative decentralized routing with a centralized routing. We show that the PoA is very pessimistic measure since it is achieved in only pathological cases. In most scenarios, distributed implementations of load-balancing perform nearly as well as the optimal centralized implementation. In the last part of the thesis, we analyse the optimal path discovery problem in complete graphs. In this problem, the values of the edges are unknown but can be queried. For a given function that is applied to paths, the goal is to find a best value path from a source to a given destination querying the least number of edges. We propose the query ratio as efficiency measure of algorithms that solve this problem. We prove a lower-bound for any algorithm that solves this problem and we proposed an algorithm with query ratio strictly less than 2.

As more online services are migrated from monolithic systems into decoupled distributed micro services, the need for efficient internal load balancing solutions increases. Today, there exists two main approaches for load balancing internal traffic between micro services. One approach uses either a central or sidecar proxy to load balance queries over all available server endpoints. The other approach lets client themselves decide which of all available endpoints to send queries to. This study investigates a new approach called lookaside load balancing. This approach consists of a load balancer that uses the control plane to gather a list of service endpoints and their current load. The load balancer can then dynamically provide clients with a subset of suitable endpoints they connect to directly. The endpoint distribution is controlled by a lookaside load balancing algorithm. This study presents such an algorithm that works by changing the endpoint assignment in order to keep current load between an upper and lower bound. In order to compare each of these three load balancing approaches, a test environment in Kubernetes is constructed and modeled to be similar to a real service mesh. With this test environment, we perform four experiments. The first experiment aims at finding suitable settings for the lookaside load balancing algorithm as well as a baseline load configuration for clients and servers. The second experiments evaluates the underlying network infrastructure to test for possible bias in latency measurements. The final two experiments evaluate each load balancing approach in both high and low load scenarios. Results show that lookaside load balancing can achieve similar performance as client-side load balancing in terms of latency and load distribution, but with a smaller CPU and memory footprint. When load is high and uneven, or when compute resource usage should be minimized, the centralized proxy approach is better. With regards to traffic flow control and failure resilience, we can show that lookaside load balancing is better than client-side load balancing. We draw the conclusion that lookaside load balancing can be an alternative approach to client-side load balancing as well as proxy load balancing for some scenarios. / Då fler online tjänster flyttas från monolitsystem till uppdelade distribuerade mikrotjänster, ökas behovet av intern lastbalansering. Idag existerar det två huvudsakliga tillvägagångssätt för intern lastbalansering mellan interna mikrotjänster. Ett sätt använder sig antingen utav en central- eller sido-proxy for att lastbalansera trafik över alla tillgängliga serverinstanser. Det andra sättet låter klienter själva välja vilken utav alla serverinstanser att skicka trafik till. Denna studie undersöker ett nytt tillvägagångssätt kallat extern lastbalansering. Detta tillvägagångssätt består av en lastbalanserare som använder kontrollplanet för att hämta en lista av alla serverinstanser och deras aktuella last. Lastbalanseraren kan då dynamiskt tillsätta en delmängd av alla serverinstanser till klienter och låta dom skapa direktkopplingar. Tillsättningen av serverinstanser kontrolleras av en extern lastbalanseringsalgoritm. Denna studie presenterar en sådan algoritm som fungerar genom att ändra på tillsättningen av serverinstanser för att kunna hålla lasten mellan en övre och lägre gräns. För att kunna jämföra dessa tre tillvägagångssätt för lastbalansering konstrueras och modelleras en testmiljö i Kubernetes till att vara lik ett riktigt service mesh. Med denna testmiljö utför vi fyra experiment. Det första experimentet har som syfte att hitta passande inställningar till den externa lastbalanseringsalgoritmen, samt att hitta en baskonfiguration för last hos klienter or servrar. Det andra experimentet evaluerar den underliggande nätverksinfrastrukturen för att testa efter potentiell partiskhet i latensmätningar. De sista två experimenten evaluerar varje tillvägagångssätt av lastbalansering i både scenarier med hög och låg belastning. Resultaten visar att extern lastbalansering kan uppnå liknande prestanda som klientlastbalansering avseende latens och lastdistribution, men med lägre CPU- och minnesanvändning. När belastningen är hög och ojämn, eller när beräkningsresurserna borde minimeras, är den centraliserade proxy-metoden bättre. Med hänsyn till kontroll över trafikflöde och resistans till systemfel kan vi visa att extern lastbalansering är bättre än klientlastbalansering. Vi drar slutsatsen att extern lastbalansering kan vara ett alternativ till klientlastbalansering samt proxylastbalansering i vissa fall.

No / In the telecommunication networks the introduction of Next Generation Wireless Networks (NGWN) has been described as the most significant change in wireless communication. The convergence of different access networks in NGWN allows generalized mobility, consistency and ubiquitous provision of services to mobile users. The general target of NGWN is to transport different types of information like voice, data, and other media like video in packets form like IP. The NGWNs offer significant savings in costs to the operators along with new and interesting services to the consumers. Major challenges in NGWN are efficient resource utilization, maintaining service quality, reliability and the security. This paper proposes a solution for seamless load aware Radio Access Technology (RAT) selection based on interworking of different RATs in NGWN. In this paper novel load balancing algorithms have been proposed which have been simulated on the target network architecture for TCP data services. The IEEE 802.21 Media Independent Handover (MIH) is utilized in load balancing specifically for mobility management, which enable low handover latency by reducing the target network detection time. The proposed method considers the network type, signal strength, data rate and network load as primary decision parameters for RAT selection process and consists of two different algorithms, one located in the mobile terminal and the other at the network side. The network architecture, the proposed load balancing framework and RAT selection algorithms were simulated using NS2. Different attributes like load distribution in the wireless networks and average throughput to evaluate the effects of load balancing in considered scenarios.

No / The ever increasing user QoS demands and emergence of new user applications make job of network operators and manufacturers more challenging for efficiently optimisation and managing radio resources in radio the radio resources pools of different wireless networks. A group of strategies or mechanisms which are collectively responsible for efficient utilisation of radio resources available within the Radio Access Technologies (RAT) are termed as Radio Resource Management (RRM). The traditional RRM strategies are implemented independently in each RAT, as each RRM strategy considers attributes of a particular access technology. Therefore traditional RRM strategies are not suitable for heterogeneous wireless networks. Common Radio Resource Management (CRRM) or joint radio resource management (JRRM) strategies are proposed for coordinating radio resource management between multiple RATs in an improved manner. In this paper a fuzzy algorithm based CRRM strategy is presented to efficiently utilise the available radio resources in heterogeneous wireless networks. The proposed CRRM strategy balances the load in heterogeneous wireless networks and avoids the unwanted congestion situation. The results such as load distribution, packet drop rate and average throughput at mobile nodes are used to demonstrate the benefits of load balancing in heterogeneous wireless networks using proposed strategy.

Heterogeneous wireless networking technologies such as satellite, UMTS, WiMax and WLAN are being used to provide network access for both voice and data services. In big cities, the densely populated areas like town centres, shopping centres and train stations may have coverage of multiple wireless networks. Traditional Radio Access Technology (RAT) selection algorithms are mainly based on the 'Always Best Connected' paradigm whereby the mobile nodes are always directed towards the available network which has the strongest and fastest link. Hence a large number of mobile users may be connected to the more common UMTS while the other networks like WiMax and WLAN would be underutilised, thereby creating an unbalanced load across these different wireless networks. This high variation among the load across different co-located networks may cause congestion on overloaded network leading to high call blocking and call dropping probabilities. This can be alleviated by moving mobile users from heavily loaded networks to least loaded networks. This thesis presents a novel framework for load balancing in heterogeneous wireless networks incorporating the IEEE 802.21 Media Independent Handover (MIH). The framework comprises of novel load-aware RAT selection techniques and novel network load balancing mechanism. Three new different load balancing algorithms i.e. baseline, fuzzy and neural-fuzzy algorithms have also been presented in this thesis that are used by the framework for efficient load balancing across the different co-located wireless networks. A simulation model developed in NS2 validates the performance of the proposed load balancing framework. Different attributes like load distribution in all wireless networks, handover latencies, packet drops, throughput at mobile nodes and network utilization have been observed to evaluate the effects of load balancing using different scenarios. The simulation results indicate that with load balancing the performance efficiency improves as the overloaded situation is avoided by load balancing.

Os atuais sistemas de HPC tem realizado simulações mais complexas possíveis, produzindo benefícios para diversas áreas de pesquisa. Para atender à crescente demanda de processamento dessas simulações, novos equipamentos estão sendo projetados, visando à escala exaflops. Um grande desafio para a construção destes sistemas é a potência que eles vão demandar, onde perspectivas atuais alcançam GigaWatts. Para resolver este problema, esta tese apresenta uma abordagem para aumentar a eficiência energética usando recursos de HPC, objetivando reduzir os efeitos do desequilíbrio de carga e economizar energia. Nós desenvolvemos uma estratégia baseada no consumo de energia, chamada ENERGYLB, que considera características da plataforma, irregularidade e dinamicidade de carga das aplicações para melhorar a eficiência energética. Nossa estratégia leva em conta carga computacional atual e a frequência de clock dos cores, para decidir entre chamar uma estratégia de balanceamento de carga que reduz o desequilíbrio de carga migrando tarefas, ou usar técnicas de DVFS par ajustar as frequências de clock dos cores de acordo com suas cargas computacionais ponderadas. Como as diferentes arquiteturas de processador podem apresentam dois níveis de granularidade de DVFS, DVFS-por-chip ou DVFS-por-core, nós criamos dois diferentes algoritmos para a nossa estratégia. O primeiro, FG-ENERGYLB, permite um controle fino da frequência dos cores em sistemas que possuem algumas dezenas de cores e implementam DVFS-por-core. Por outro lado, CG-ENERGYLB é adequado para plataformas de HPC composto de vários processadores multicore que não permitem tal refinado controle, ou seja, que só executam DVFS-por-chip. Ambas as abordagens exploram desbalanceamentos residuais em aplicações interativas e combinam balanceamento de carga dinâmico com técnicas de DVFS. Assim, eles reduzem a frequência de clock dos cores com menor carga computacional os quais apresentam algum desequilíbrio residual mesmo após as tarefas serem remapeadas. Nós avaliamos a aplicabilidade das nossas abordagens utilizando o ambiente de programação paralela CHARM++ sobre benchmarks e aplicações reais. Resultados experimentais presentaram melhorias no consumo de energia e na demanda potência sobre algoritmos do estado-da-arte. A economia de energia com ENERGYLB usado sozinho foi de até 25% com nosso algoritmo FG-ENERGYLB, e de até 27% com nosso algoritmo CG-ENERGYLB. No entanto, os desequilíbrios residuais ainda estavam presentes após as serem tarefas remapeadas. Neste caso, quando as nossas abordagens foram empregadas em conjunto com outros balanceadores de carga, uma melhoria na economia de energia de até 56% é obtida com FG-ENERGYLB e de até 36% com CG-ENERGYLB. Estas economias foram obtidas através da exploração do desbalanceamento residual em aplicações interativas. Combinando balanceamento de carga dinâmico com DVFS nossa estratégia é capaz de reduzir a demanda de potência média dos sistemas paralelos, reduzir a migração de tarefas entre os recursos disponíveis, e manter o custo de balanceamento de carga baixo. / Current HPC systems have made more complex simulations feasible, yielding benefits to several research areas. To meet the increasing processing demands of these simulations, new equipment is being designed, aiming at the exaflops scale. A major challenge for building these systems is the power that they will require, which current perspectives reach the GigaWatts. To address this problem, this thesis presents an approach to increase the energy efficiency using of HPC resources, aiming to reduce the effects of load imbalance to save energy. We developed an energy-aware strategy, called ENERGYLB, which considers platform characteristics, and the load irregularity and dynamicity of the applications to improve the energy efficiency. Our strategy takes into account the current computational load and clock frequency, to decide whether to call a load balancing strategy that reduces load imbalance by migrating tasks, or use Dynamic Voltage and Frequency Scaling (DVFS) technique to adjust the clock frequencies of the cores according to their weighted loads. As different processor architectures can feature two levels of DVFS granularity, per-chip DVFS or per-core DVFS, we created two different algorithms for our strategy. The first one, FG-ENERGYLB, allows a fine control of the clock frequency of cores in systems that have few tens of cores and feature per-core DVFS control. On the other hand, CGENERGYLB is suitable for HPC platforms composed of several multicore processors that do not allow such a fine-grained control, i.e., that only perform per-chip DVFS. Both approaches exploit residual imbalances on iterative applications and combine dynamic load balancing with DVFS techniques. Thus, they reduce the clock frequency of underloaded computing cores, which experience some residual imbalance even after tasks are remapped. We evaluate the applicability of our approaches using the CHARM++ parallel programming system over benchmarks and real world applications. Experimental results present improvements in energy consumption and power demand over state-of-the-art algorithms. The energy savings with ENERGYLB used alone were up to 25%with our FG-ENERGYLB algorithm, and up to 27%with our CG-ENERGYLB algorithm. Nevertheless, residual imbalances were still present after tasks were remapped. In this case, when our approaches were employed together with these load balancers, an improvement in energy savings of up to 56% is achieved with FG-ENERGYLB and up to 36% with CG-ENERGYLB. These savings were obtained by exploiting residual imbalances on iterative applications. By combining dynamic load balancing with the DVFS technique, our approach is able to reduce the average power demand of parallel systems, reduce the task migration among the available resources, and keep load balancing overheads low.

A crescente disponibilizaÃÃo de serviÃos atravÃs da Internet vem impondo uma demanda cada vez maior por recursos de processamento no lado servidor favorecendo a utilizaÃÃo dos Clusters de Computadores e das Grades Computacionais. Em paralelo, a engenharia de software traz novos paradigmas, como a OrientaÃÃo a ServiÃos, que impÃem novos desafios a serem tratados pelos fornecedores de serviÃos. A convergÃncia destes fatores deu origem as Arquiteturas de Grades Computacionais Orientadas a ServiÃos. Neste trabalho à apresentada uma proposta de arquitetura em grades computacionais orientada a serviÃos, denominada GDSAC (Grid â DiffServ Admission Control), que trata de aspectos ligados à QoS (Quality of Service) e a diferenciaÃÃo de serviÃos. A arquitetura G-DSAC à uma extensÃo da arquitetura WS-DSAC (Web Servers â DiffServ AdmissionControl). Està extensÃo compreende a concepÃÃo de uma soluÃÃo voltada para grades computacionais que à capaz de garantir os SLAs (Service Level Agreements) estabelecidos com os consumidores de serviÃos utilizando de forma otimizada os recursos de processamento disponibilizados na grade. A soluÃÃo permite ainda a diferenciaÃÃo de serviÃos no que diz respeito aos tempos de resposta oferecidos aos clientes, usuÃrios finais e serviÃos consumidores. A nova arquitetura introduz um bloco de funcionalidades em uma plataforma de grade computacional orientada a serviÃos formada por multclusters. Esse bloco permite a publicaÃÃo e localizaÃÃo de serviÃos, autenticaÃÃo e classificaÃÃo de requisiÃÃes e o escalonamento das mesmas dentro da grade de acordo com a classe de serviÃo a qual pertencem. Foi tambÃm implementado um protÃtipo que permitiu a realizaÃÃo de experimentos em uma plataforma real de testes visando avaliar a capacidade da soluÃÃo em atingir os objetivos por ela proposto

No description available.

With the rapid growth of data and computational needs, distributed systems and computational Grids are gaining more and more attention. Grids are playing an important and growing role in today networks. The huge amount of computations a Grid can fulfill in a specificc time cannot be done by the best super computers. However, Grid performance can still be improved by making sure all the resources available in the Grid are utilized by a good load balancing algorithm. The purpose of such algorithms is to make sure all nodes are equally involved in Grid computations. This research proposes two new distributed swarm intelligence inspired load balancing algorithms. One is based on ant colony optimization and is called AntZ, the other one is based on particle swarm optimization and is called ParticleZ. Distributed load balancing does not incorporate a single point of failure in the system. In the AntZ algorithm, an ant is invoked in response to submitting a job to the Grid and this ant surfs the network to find the best resource to deliver the job to. In the ParticleZ algorithm, each node plays a role as a particle and moves toward other particles by sharing its workload among them. We will be simulating our proposed approaches using a Grid simulation toolkit (GridSim) dedicated to Grid simulations. The performance of the algorithms will be evaluated using several performance criteria (e.g. makespan and load balancing level). A comparison of our proposed approaches with a classical approach called State Broadcast Algorithm and two random approaches will also be provided. Experimental results show the proposed algorithms (AntZ and ParticleZ) can perform very well in a Grid environment. In particular, the use of particle swarm optimization, which has not been addressed in the literature, can yield better performance results in many scenarios than the ant colony approach.

With the rapid growth of data and computational needs, distributed systems and computational Grids are gaining more and more attention. Grids are playing an important and growing role in today networks. The huge amount of computations a Grid can fulfill in a specificc time cannot be done by the best super computers. However, Grid performance can still be improved by making sure all the resources available in the Grid are utilized by a good load balancing algorithm. The purpose of such algorithms is to make sure all nodes are equally involved in Grid computations. This research proposes two new distributed swarm intelligence inspired load balancing algorithms. One is based on ant colony optimization and is called AntZ, the other one is based on particle swarm optimization and is called ParticleZ. Distributed load balancing does not incorporate a single point of failure in the system. In the AntZ algorithm, an ant is invoked in response to submitting a job to the Grid and this ant surfs the network to find the best resource to deliver the job to. In the ParticleZ algorithm, each node plays a role as a particle and moves toward other particles by sharing its workload among them. We will be simulating our proposed approaches using a Grid simulation toolkit (GridSim) dedicated to Grid simulations. The performance of the algorithms will be evaluated using several performance criteria (e.g. makespan and load balancing level). A comparison of our proposed approaches with a classical approach called State Broadcast Algorithm and two random approaches will also be provided. Experimental results show the proposed algorithms (AntZ and ParticleZ) can perform very well in a Grid environment. In particular, the use of particle swarm optimization, which has not been addressed in the literature, can yield better performance results in many scenarios than the ant colony approach.