No description available.

Massively multiplayer games allow hundreds of players to play and interact with each other simultaneously. Due to the increasing need to provide a greater degree of interaction to more players, load balancing is critical on the servers that host the game. A common approach is to divide the world into microcells (small regions of the game terrain) and to allocate the microcells dynamically across multiple servers. We describe a visibility--based technique that guides the creation of microcells and their dynamic allocation. This technique is designed to reduce the amount of cross--server communication, in the hope of providing better load balancing than other load--balancing strategies. We hypothesize that reduction in expensive cross-server traffic will reduce the overall load on the system. We employ horizon counts map to create visibility based microcells, in order to emphasize primary occluders in the terrain. In our testing we consider traffic over a given quality of service threshold as the primary metric for minimization. As result of our testing we find that dynamic load balancing produces significant improvement in the frequency of quality of service failures. We find that our visibility-based micro cells do not outperform basic rectangular microcells discussed in earlier research. We also find that cross-server traffic makes up a much smaller portion of overall message load than we had anticipated, reducing the potential overall benefit from cross server message optimisation. / Thesis (Master, Computing) -- Queen's University, 2011-09-28 14:15:32.173

Due to the dependency of High-Level Architecture (HLA)-Based simulations on the resources of distributed environments, simulations can face load imbalances and can suffer from low performance in terms of execution time. HLA is a framework that simplifies the implementation of distributed simulations; it also has been built with dedicated resources in mind. As technology is nowadays shifting towards shared environments, the following two weaknesses have become apparent in HLA: managing federates and reacting towards load imbalances on shared resources. Moreover, a number of dynamic load management systems have been designed in order to provide a solution to enable a balanced simulation environment on shared resources. These solutions use specific techniques depending on simulation characteristics or load aspects to perform the balancing task. Load prediction is one of such techniques that improves load redistribution heuristics by preventing load imbalances. In this thesis, a number of enhancements for a prediction technique are presented, and their efficiency are compared. The proposed enhancements solve the observed problems with Holt’s implementations on dynamic load balancing systems for HLA-Based distributed simulations and provide better forecasting. As a result, these enhancements provide better predictions for the load oscillations of the shared resources. Furthermore, a number of federate migration decision-making approaches are introduced to add more intelligence into the process of migrating federates. The approaches aim to solve a dependency problem in the prediction-based load balancing system on the prediction model, thus making similar systems adapt to any future system improvements.

Latent Semantic Indexing (LSI) is one of the popular techniques in the information retrieval fields. Different from the traditional information retrieval techniques, LSI is not based on the keyword matching simply. It uses statistics and algebraic computations. Based on Singular Value Decomposition (SVD), the higher dimensional matrix is converted to a lower dimensional approximate matrix, of which the noises could be filtered. And also the issues of synonymy and polysemy in the traditional techniques can be overcome based on the investigations of the terms related with the documents. However, it is notable that LSI suffers a scalability issue due to the computing complexity of SVD. This thesis presents a resource aware distributed LSI algorithm MR-LSI which can solve the scalability issue using Hadoop framework based on the distributed computing model MapReduce. It also solves the overhead issue caused by the involved clustering algorithm. The evaluations indicate that MR-LSI can gain significant enhancement compared to the other strategies on processing large scale of documents. One remarkable advantage of Hadoop is that it supports heterogeneous computing environments so that the issue of unbalanced load among nodes is highlighted. Therefore, a load balancing algorithm based on genetic algorithm for balancing load in static environment is proposed. The results show that it can improve the performance of a cluster according to heterogeneity levels. Considering dynamic Hadoop environments, a dynamic load balancing strategy with varying window size has been proposed. The algorithm works depending on data selecting decision and modeling Hadoop parameters and working mechanisms. Employing improved genetic algorithm for achieving optimized scheduler, the algorithm enhances the performance of a cluster with certain heterogeneity levels.

VISIR “Virtual Instrument Systems in Reality” is a remote laboratory that empowers students and researchers to design, implement, and measure on electronic circuits remotely. Users are able to connect to this system regardless of their location and use traditional lab resources online via JavaScript and HTML5 enabled web browser. The VISIR project is deployed to seven universities around the globe including Blekinge Institute of Technology (BTH) in Sweden. In this thesis work, the main aim is to introduce load-balancing Scenarios in VISIR network in order to enable and improve load balancing, stability, and scalability in this system. The participant universities will be connected in a grid topology, and they exchange capabilities, features, and data repository in order to share workload and resources. For this purpose, the behavior of VISIR network nodes were studied and simplified as simple servers. According to the VISIR characteristics, infrastructure, and requirement a set of design paradigms and guidelines were defined for selecting suitable load balancing mechanism to be used in VISIR system. Four different load-balancing methods described, were selected for comparison in an experimental setup. Moreover, an experimental test bed with utilizing virtual Linux machines was modeled, and chosen scenarios were implemented and tested under different circumstances i.e. various number of servers and clients.

We study a new method of generating random $d$-regular graphs by repeatedly applying an operation called pegging. The pegging algorithm, which applies the pegging operation in each step, is a method of generating large random regular graphs beginning with small ones. We prove that the limiting joint distribution of the numbers of short cycles in the resulting graph is independent Poisson. We use the coupling method to bound the total variation distance between the joint distribution of short cycle counts and its limit and thereby show that $O(\epsilon^{-1})$ is an upper bound of the $\eps$-mixing time. The coupling involves two different, though quite similar, Markov chains that are not time-homogeneous. We also show that the $\epsilon$-mixing time is not $o(\epsilon^{-1})$. This demonstrates that the upper bound is essentially tight. We study also the connectivity of random $d$-regular graphs generated by the pegging algorithm. We show that these graphs are asymptotically almost surely $d$-connected for any even constant $d\ge 4$. The problem of orientation of random hypergraphs is motivated by the classical load balancing problem. Let $h>w>0$ be two fixed integers. Let $\orH$ be a hypergraph whose hyperedges are uniformly of size $h$. To {\em $w$-orient} a hyperedge, we assign exactly $w$ of its vertices positive signs with respect to this hyperedge, and the rest negative. A $(w,k)$-orientation of $\orH$ consists of a $w$-orientation of all hyperedges of $\orH$, such that each vertex receives at most $k$ positive signs from its incident hyperedges. When $k$ is large enough, we determine the threshold of the existence of a $(w,k)$-orientation of a random hypergraph. The $(w,k)$-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The other topic we discuss is computing the probability of induced subgraphs in a random regular graph. Let $0<s<n$ and $H$ be a graph on $s$ vertices. For any $S\subset [n]$ with $|S|=s$, we compute the probability that the subgraph of $\mathcal{G}_{n,d}$ induced by $S$ is $H$. The result holds for any $d=o(n^{1/3})$ and is further extended to $\mathcal{G}_{n,{\bf d}}$, the probability space of random graphs with given degree sequence $\bf d$. This result provides a basic tool for studying properties, for instance the existence or the counts, of certain types of induced subgraphs.

We study a new method of generating random $d$-regular graphs by repeatedly applying an operation called pegging. The pegging algorithm, which applies the pegging operation in each step, is a method of generating large random regular graphs beginning with small ones. We prove that the limiting joint distribution of the numbers of short cycles in the resulting graph is independent Poisson. We use the coupling method to bound the total variation distance between the joint distribution of short cycle counts and its limit and thereby show that $O(\epsilon^{-1})$ is an upper bound of the $\eps$-mixing time. The coupling involves two different, though quite similar, Markov chains that are not time-homogeneous. We also show that the $\epsilon$-mixing time is not $o(\epsilon^{-1})$. This demonstrates that the upper bound is essentially tight. We study also the connectivity of random $d$-regular graphs generated by the pegging algorithm. We show that these graphs are asymptotically almost surely $d$-connected for any even constant $d\ge 4$. The problem of orientation of random hypergraphs is motivated by the classical load balancing problem. Let $h>w>0$ be two fixed integers. Let $\orH$ be a hypergraph whose hyperedges are uniformly of size $h$. To {\em $w$-orient} a hyperedge, we assign exactly $w$ of its vertices positive signs with respect to this hyperedge, and the rest negative. A $(w,k)$-orientation of $\orH$ consists of a $w$-orientation of all hyperedges of $\orH$, such that each vertex receives at most $k$ positive signs from its incident hyperedges. When $k$ is large enough, we determine the threshold of the existence of a $(w,k)$-orientation of a random hypergraph. The $(w,k)$-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. The other topic we discuss is computing the probability of induced subgraphs in a random regular graph. Let $0<s<n$ and $H$ be a graph on $s$ vertices. For any $S\subset [n]$ with $|S|=s$, we compute the probability that the subgraph of $\mathcal{G}_{n,d}$ induced by $S$ is $H$. The result holds for any $d=o(n^{1/3})$ and is further extended to $\mathcal{G}_{n,{\bf d}}$, the probability space of random graphs with given degree sequence $\bf d$. This result provides a basic tool for studying properties, for instance the existence or the counts, of certain types of induced subgraphs.

In this thesis, we first propose a modified version of the CDPthread to eliminate the restriction on the number of execution engines supported¡Xby dynamically instead of statically allocating the execution engines to a process. Then, we describe a method to balance the workload among nodes under the control of the modified CDPthread to improve its performance. The proposed method keeps track of the workload of each node and decides to which node the next job is to be assigned. More precisely, the number of jobs assigned to each node is proportional to, but not limited to, the number of cores in each node. Our experimental results show that with a small loss of performance compared to the original CDPthread, which uses a static method for allocating the execution engines to a process, the modified CDPthread with load balancing outperforms the modified CDPthread without load balancing by about 25 to 45 percent in terms of the computation time. Moreover, the modified CDPthread can now handle as many threads as necessary.

A peer-to-peer (P2P) system is a networked system characterized by the lack of centralized control, in which all or most communication is symmetric. Also, a P2P system is supposed to handle frequent arrivals and departures of nodes, and is expected to scale to very large network sizes. These requirements make the design of P2P systems particularly challenging. We investigate two central issues pertaining to the design of P2P systems: load balancing and routing. In the first part of this thesis, we study the problem of load balancing in the context of Distributed Hash Tables (DHTs). Briefly, a DHT is a giant hash table that is maintained in a P2P fashion: Keys are mapped to a hash space I --- typically the interval [0,1), which is partitioned into blocks among the nodes, and each node stores the keys that are mapped to its block. Based on the position of their blocks in I, the nodes also set up connections among themselves, forming a routing network, which facilitates efficient key location. Typically, in a DHT it is desirable that the nodes' blocks are roughly of equal size, since this usually implies a balanced distribution of the load of storing keys among nodes, and it also simplifies the design of the routing network. We propose and analyze a simple distributed scheme for partitioning I, inspired by the multiple random choices paradigm. This scheme guarantees that, with high probability, the ratio between the largest and smallest blocks remains bounded by a small constant. It is also message efficient, and the arrival or departure of a node perturbs the current partition of I minimally. A unique feature of this scheme is that it tolerates adversarial arrivals and departures of nodes. In the second part of the thesis, we investigate the complexity of a natural decentralized routing protocol, in a broad family of randomized networks. The network family and routing protocol in question are inspired by a framework proposed by Kleinberg to model small-world phenomena in social networks, and they capture many designs that have been proposed for P2P systems. For this model we establish a general lower bound on the expected message complexity of routing, in terms of the average node degree. This lower bound almost matches the corresponding known upper bound.

A peer-to-peer (P2P) system is a networked system characterized by the lack of centralized control, in which all or most communication is symmetric. Also, a P2P system is supposed to handle frequent arrivals and departures of nodes, and is expected to scale to very large network sizes. These requirements make the design of P2P systems particularly challenging. We investigate two central issues pertaining to the design of P2P systems: load balancing and routing. In the first part of this thesis, we study the problem of load balancing in the context of Distributed Hash Tables (DHTs). Briefly, a DHT is a giant hash table that is maintained in a P2P fashion: Keys are mapped to a hash space I --- typically the interval [0,1), which is partitioned into blocks among the nodes, and each node stores the keys that are mapped to its block. Based on the position of their blocks in I, the nodes also set up connections among themselves, forming a routing network, which facilitates efficient key location. Typically, in a DHT it is desirable that the nodes' blocks are roughly of equal size, since this usually implies a balanced distribution of the load of storing keys among nodes, and it also simplifies the design of the routing network. We propose and analyze a simple distributed scheme for partitioning I, inspired by the multiple random choices paradigm. This scheme guarantees that, with high probability, the ratio between the largest and smallest blocks remains bounded by a small constant. It is also message efficient, and the arrival or departure of a node perturbs the current partition of I minimally. A unique feature of this scheme is that it tolerates adversarial arrivals and departures of nodes. In the second part of the thesis, we investigate the complexity of a natural decentralized routing protocol, in a broad family of randomized networks. The network family and routing protocol in question are inspired by a framework proposed by Kleinberg to model small-world phenomena in social networks, and they capture many designs that have been proposed for P2P systems. For this model we establish a general lower bound on the expected message complexity of routing, in terms of the average node degree. This lower bound almost matches the corresponding known upper bound.