Spelling suggestions: "subject:"load balancing"" "subject:"load alancing""
1 |
Stochastic scheduling in networksDacre, Marcus James January 1999 (has links)
No description available.
|
2 |
Visibility-based microcells for dynamic load balancing in MMO gamesSUMILA, ALEXEI 29 September 2011 (has links)
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
|
3 |
Improved Prediction-based Dynamic Load Balancing Systems for HLA-Based Distributed SimulationsAlkharboush, Raed January 2015 (has links)
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.
|
4 |
A resource aware distributed LSI algorithm for scalable information retrievalLiu, Yang January 2011 (has links)
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.
|
5 |
Using Grid Network between VISIR LaboratoriesMehraban, Mehrdad January 2015 (has links)
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.
|
6 |
Generation and properties of random graphs and analysis of randomized algorithmsGao, Pu January 2010 (has links)
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.
|
7 |
Generation and properties of random graphs and analysis of randomized algorithmsGao, Pu January 2010 (has links)
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.
|
8 |
On the Design and Implementation of Load Balancing for CDPthread-based SystemsChou, Yu-chieh 02 September 2009 (has links)
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.
|
9 |
On Load Balancing and Routing in Peer-to-peer SystemsGiakkoupis, George 15 July 2009 (has links)
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.
|
10 |
On Load Balancing and Routing in Peer-to-peer SystemsGiakkoupis, George 15 July 2009 (has links)
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.
|
Page generated in 0.0829 seconds