In mobile networks, the mobile core plays a crucial role in providing connectivity between mobile user devices and external packet data networks such as the Internet. Through the years, along with the dramatical changes in radio access networks, the mobile core has also been evolved from being a circuit-based analog telephony system in its first generation (1G) to become a purely packet-based network called the Evolved Packet Core (EPC) in the current generation (4G). In recent years, the explosion of mobile data traffic and devices and the advent of new services have led to the investigation of the next generation of mobile networks, i.e., 5G. A wide range of technologies has been proposed as candidates for the development of 5G. Among other technology candidates, Software Defined Networking (SDN) and Network Function Virtualization (NFV) have been widely considered to be key enablers for the network architecture of 5G, especially the mobile packet core (MPC) network. This thesis aims at identifying benefits and challenges of introducing SDN and NFV to re-achitect the current MPC network architecture towards 5G and addressing some of the challenges. To this end, we conduct a comprehensive literature review of the state-of-the-art work leveraging SDN and NFV to re-design the 4G EPC architecture. Through this survey work, several research questions for future work have been identified and we contribute to address two of them in this thesis. Firstly, since most of the current works focus on unicast services, we propose an SDN/NFV-based MPC architecture for providing multicast and broadcast services. Our numerical results show that the proposed architecture can reduce the total signaling cost compared to the traditional architecture. Secondly, we address the question regarding the scalability of the control plane. We take the Mobility Management Entity (MME) - one of the EPC key control plane entities - as a case study. In our work, the MME is deployed as a cluster of multiple virtual instances (vMMEs) and a front-end load balancer. We focus on investigating different approaches to achieve better load balancing among these vMMEs, which in turn improves scalability. Our experimental results suggest that carefully selected load balancing algorithms can significantly reduce the control plane latency. / In mobile networks, the mobile core plays a crucial role in providing connectivity between mobile user devices and external packet data networks such as the Internet. After more than three decades, the mobile core has been gradually evolved through four generations and is called the Evolved Packet Core (EPC) in the current generation (4G). In recent years, the explosion of mobile data traffic and devices and the advent of new services have led to the investigation of the next generation of mobile networks, i.e., 5G. Among other technology candidates, Software Defined Networking (SDN) and Network Function Virtualization (NFV) have been widely considered to be key enablers for the network architecture of 5G, especially the mobile packet core (MPC) network. This thesis aims at identifying benefits and challenges of introducing SDN and NFV to re-achitect the current MPC architecture towards 5G and addressing some of the challenges. To this end, we conduct a comprehensive survey of the existing SDN/NFV-based MPC architectures. Through this survey work, several research questions for future work have been identified and we contribute to address two of the research questions. Firstly, we propose an SDN/NFV-based MPC architecture for providing multicast and broadcast services. Secondly, we tackle the scalability problem of the Mobility Management Entity (MME) - one of the EPC key control plane entities. In particular, we investigate different approaches to achieve better load balancing among virtual MMEs in a virtual and distributed MME design, which in turn improves scalability. / HITS, 4707

Within the broad topical designation of “smart grid,” research in demand response, or demand-side management, focuses on investigating possibilities for electrically powered devices to adapt their power consumption patterns to better match the availability of intermittent renewable energy sources, especially wind. Devices such as battery chargers, heating and cooling systems, and computers can be controlled to change the time, duration, and magnitude of their power consumption while still meeting workload constraints such as deadlines and rate of throughput. This thesis presents a system by which a computer server, or multiple servers in a data center, can estimate the power imbalance on the electrical grid and use that information to dynamically change the power consumption as a service to the grid. Implementation on a testbed demonstrates the system with a hypothetical but realistic usage case scenario of an online video streaming service in which there are workloads with deadlines (high-priority) and workloads without deadlines (low-priority). The testbed is implemented with real servers, estimates the power imbalance from the grid frequency with real-time measurements of the live outlet, and uses a distributed, real-time algorithm to dynamically adjust the power consumption of the servers based on the frequency estimate and the throughput of video transcoder workloads. Analysis of the system explains and justifies multiple design choices, compares the significance of the system in relation to similar publications in the literature, and explores the potential impact of the system.

Community detection (or clustering) in large-scale graph is an important problem in graph mining. Communities reveal interesting characteristics of a network. Louvain is an efficient sequential algorithm but fails to scale emerging large-scale data. Developing distributed-memory parallel algorithms is challenging because of inter-process communication and load-balancing issues. In this work, we design a shared memory-based algorithm using OpenMP, which shows a 4-fold speedup but is limited to available physical cores. Our second algorithm is an MPI-based parallel algorithm that scales to a moderate number of processors. We also implement a hybrid algorithm combining both. Finally, we incorporate dynamic load-balancing in our final algorithm DPLAL (Distributed Parallel Louvain Algorithm with Load-balancing). DPLAL overcomes the performance bottleneck of the previous algorithms, shows around 12-fold speedup scaling to a larger number of processors. Overall, we present the challenges, our solutions, and the empirical performance of our algorithms for several large real-world networks.

L'équilibrage de charge est une étape importante conditionnant les performances des applications parallèles. Dans le cas où la charge varie au cours de la simulation, il est important de redistribuer régulièrement la charge entre les différents processeurs. Dans ce contexte, il peut s'avérer pertinent d'adapter le nombre de processeurs au cours d'une simulation afin d'obtenir une meilleure efficacité, ou de continuer l'exécution quand toute la mémoire des ressources courantes est utilisée. Contrairement au cas où le nombre de processeurs ne varie pas, le rééquilibrage dynamique avec un nombre variable de processeurs est un problème peu étudié que nous abordons ici.Cette thèse propose différentes méthodes basées sur le repartitionnement de graphe pour rééquilibrer la charge tout en changeant le nombre de processeurs. Nous appelons ce problème « repartitionnement M x N ». Ces méthodes se décomposent en deux grandes étapes. Dans un premier temps, nous étudions la phase de migration et nous construisons une « bonne » matrice de migration minimisant plusieurs critères objectifs comme le volume total de migration et le nombre total de messages échangés. Puis, dans un second temps, nous utilisons des heuristiques de partitionnement de graphe pour calculer une nouvelle distribution optimisant la migration en s'appuyant sur les résultats de l'étape précédente. En outre, nous proposons un algorithme de partitionnement k-aire direct permettant d'améliorer le partitionnement biaisé. Finalement, nous validons cette thèse par une étude expérimentale en comparant nos méthodes aux partitionneursactuels. / Load balancing is an important step conditioning the performance of parallel programs. If the workload varies drastically during the simulation, the load must be redistributed regularly among the processors. Dynamic load balancing is a well studied subject but most studies are limited to an initially fixed number of processors. Adjusting the number of processors at runtime allows to preserve the parallel code efficiency or to keep running the simulation when the memory of the current resources is exceeded.In this thesis, we propose some methods based on graph repartitioning in order to rebalance the load while changing the number of processors. We call this problem \M x N repartitioning". These methods are split in two main steps. Firstly, we study the migration phase and we build a \good" migration matrix minimizing several metrics like the migration volume or the number of exchanged messages. Secondly, we use graph partitioning heuristics to compute a new distribution optimizing the migration according to the previous step results. Besides, we propose a direct k-way partitioning algorithm that allows us to improve our biased partitioning. Finally, an experimental study validates our algorithms against state-of-the-art partitioning tools.

<p>Lattice Boltzmann-based (LB) simulations are well suited to the simulation of fluid flows in complex structures encountered in chemical engineering like porous media or structured packing used in distillation and reactive distillation columns. These simulations require large amounts of memory (around 10 gigabytes) and would require very long execution times (around 2 years) if executed on a single powerful desktop computer.</p> <p>The execution of LB simulations in a distributed way (for example, using cluster computing) can decrease the execution time and reduces the memory requirements for each computer. Dynamic Heterogeneous Clusters (DHC) is a class of clusters involving computers inter-connected by a local area network; these computers are potentially unreliable and do not share the same architecture, operating system, computational power, etc. However, DHCs are easy to setup and extend, and are made of affordable computers.</p> <p>The design and development of a software system which organizes large scale DHCs in an efficient, scalable and robust way for implementing very large scale LB simulations is challenging. In order to avoid that some computers are overloaded and slow down the overall execution, the heterogeneity of computational power should be taken into account. In addition, the failure of one or several computers during the execution of a simulation should not prevent its completion.</p> <p>In the context of this thesis, a simulation tool called LaBoGrid was designed. It uses existing static load balancing tools and implements an original dynamic load balancing method in order to distribute the simulation in a way that minimizes its execution time. In addition, a distributed and scalable fault-tolerance mechanism based on the regular saving of simulation's state is proposed. Finally, LaBoGrid is based on a distributed master-slave model that is robust and potentially scalable.</p> <br/> <p>Les simulations basées sur les méthodes de Lattice Boltzmann sont bien adaptées aux simulations d'écoulements de fluides à l'intérieur de structures complexes rencontrées en génie chimique, telles que les milieux poreux ou les empilements structurés utilisés dans des colonnes de distillation et de distillation réactive. Elles requièrent toutefois de grandes quantités de mémoire (environ 10 gigaoctets). Par ailleurs, leur exécution sur un seul ordinateur de bureau puissant nécessiterait un temps très long (environ deux ans).</p> <p>Il est possible de réduire à la fois le temps d'exécution et la quantité de mémoire requise par ordinateur en exécutant les simulations LB de manière distribuée, par exemple en utilisant un cluster. Un Cluster Hétérogène Dynamique (CHD) est une classe de clusters impliquant des ordinateurs qui sont interconnectés au moyen d'un réseau local, qui ne sont pas nécessairement fiables et qui ne partagent pas la même architecture, le même système d'exploitation, la même puissance de calcul, etc. En revanche, les CHD sont faciles à installer, à étendre et peu coûteux.</p> <p>Concevoir et développer un logiciel capable de gérer des CHD à grande échelle de façon efficace, extensible et robuste et capable d'effectuer des simulations LB à très grande échelle constitue un défi. L'hétérogénéité de la puissance de calcul doit être prise en compte afin d'éviter que certains ordinateurs soient débordés et ralentissent le temps global d'exécution. En outre, une panne d'un ou de plusieurs ordinateurs pendant l'exécution d'une simulation ne devrait pas empêcher son achèvement.</p> <p>Dans le contexte de cette thèse, un outil de simulation appelé LaBoGrid a été conçu. LaBoGrid utilise des outils existants de répartition statique de la charge et implémente une méthode originale de répartition dynamique de la charge, ce qui lui permet de distribuer une simulation LB de manière à minimiser son temps d'exécution. De plus, un mécanisme distribué et extensible de tolérance aux pannes, fondé sur une sauvegarde régulière de l'état de simulation, est proposé. Enfin, LaBoGrid se base sur un modèle distribué de type « maître-esclaves » qui est robuste et potentiellement extensible.</p>

The main objective of this thesis focuses on the design of an adaptive algorithm for admission control and content-aware load balancing for Web traffic. In order to set the context of this work, several reviews are included to introduce the reader in the background concepts of Web load balancing, admission control and the Internet traffic characteristics that may affect the good performance of a Web site. The admission control and load balancing algorithm described in this thesis manages the distribution of traffic to a Web cluster based on QoS requirements. The goal of the proposed scheduling algorithm is to avoid situations in which the system provides a lower performance than desired due to servers' congestion. This is achieved through the implementation of forecasting calculations. Obviously, the increase of the computational cost of the algorithm results in some overhead. This is the reason for designing an adaptive time slot scheduling that sets the execution times of the algorithm depending on the burstiness that is arriving to the system. Therefore, the predictive scheduling algorithm proposed includes an adaptive overhead control.Once defined the scheduling of the algorithm, we design the admission control module based on throughput predictions. The results obtained by several throughput predictors are compared and one of them is selected to be included in our algorithm. The utilisation level that the Web servers will have in the near future is also forecasted and reserved for each service depending on the Service Level Agreement (SLA). Our load balancing strategy is based on a classical policy. Hence, a comparison of several classical load balancing policies is also included in order to know which of them better fits our algorithm. A simulation model has been designed to obtain the results presented in this thesis.

No description available.

In this dissertation, routing protocols, load-balancing protocols, and efficient evaluation techniques for multi-hop mobile wireless networks are explored. With the advancements made in wireless communication and computer technologies, a new type of mobile wireless network, known as a mobile ad hoc network (MANET), has drawn constant attention. In recent years, several routing protocols for MANETs have been proposed. However, there still remains the need for mechanisms for better scalability support with respect to network size, traffic volume, and mobility. To address this issue, a new method for multi-hop routing in MANETs called Dynamic NIx-Vector Routing (DNVR) is proposed. DNVR has several distinct features compared to other existing on-demand routing protocols, which lead to more stable routes and better scalability. Currently, ad hoc routing protocols lack load-balancing capabilities. Therefore they often fail to provide good service quality, especially in the presence of a large volume of network traffic since the network load concentrates on some nodes, resulting in a highly congested environment. To address this issue, a novel load-balancing technique for ad hoc on-demand routing protocols is proposed. The new method is simple but very effective in achieving load balance and congestion alleviation. In addition, it operates in a completely distributed fashion. To evaluate and verify wireless network protocols effectively, especially to test their scalability properties, scalable and efficient network simulation methods are required. Usually simulation of such large-scale wireless networks needs a long execution time and requires a large amount of computing resources such as powerful CPUs and memory. Traditionally, to cope with this problem, parallel network simulation techniques with parallel computing capabilities have been considered. This dissertation explores a different type of method, which is efficient and can be achieved with a sequential simulation, as well as a parallel and distributed technique for large-scale mobile wireless networks.

As the distributed systems becomes popular, efficient load balancing systems taking better decisions must be designed. The most important reasons that necessitate load balancing in a distributed system are the heterogeneous hosts having different com- puting powers, external loads and the tasks running on different hosts but communi- cating with each other. In this thesis, a load balancing approach, called RALBANN, developed using graph partitioning and artificial neural networks (ANNs) is de- scribed. The aim of RALBANN is to integrate the successful load balancing deci- sions of graph partitioning algorithms with the efficient decision making mechanism of ANNs. The results showed that using ANNs to make efficient load balancing can be very beneficial. If trained enough, ANNs may load the balance as good as graph partitioning algorithms more efficiently.

Routing in sensor networks is a challenging issue due to inherent constraints such as power, memory, and CPU processing capabilities. In this thesis, we assume an All to All communication mode in an N × N grid sensor network. We explore routing algorithms which load balance the network without compromising the shortest paths constrain. We analyzed the Servetto method and studied two routing strategies, namely Horizontal-Vertical routing and Zigzag routing. The problem is divided into two scenarios, one being the static case (without failed nodes), and the other being the dynamic case (with failed nodes). In static network case, we derived mathematical formulae representing the maximum and minimum loads on a sensor grid, when specific routing strategies are employed. We show improvement in performance in load balancing of the grid by using Horizontal-Vertical method instead of the existing Servetto method. In the dynamic network scenario, we compare the performance of routing strategies with respect to probability of failure of nodes in the grid network. We derived the formulae for the success-ratio, in specific strategies, when nodes fail with a probability of p in a predefined source-destination pair communication. We show that the Servetto method does not perform well in both scenarios. In addition, Hybrid strategy proposed does not perform well compared to the studied strategies. We support the derived formulae and the performance of the routing strategies with extensive simulations.