We study the online bicriteria load balancing problem in this paper. We choose a system of distributed homogeneous file servers located in a cluster as the scenario and propose an online approximate solution for balancing their loads and required storage spaces upon placements and deletions. By placement (resp. deletion), we mean to insert a document into (resp. remove a document from) a server system. The main technique is to keep two global quantities large enough. To the best of our knowledge, the technique is novel, and the result is the first one, in the literature. Our result works for any sequences of document placements and deletions. For each deletion, a limited number of documents are reallocated. The load and storage space bounds are 1.5 to 4 times those in the best existing result for sole placements. We refer sole placements to those placement algorithms that do not allow any reallocation and replication. The time complexity, for each operation, is O(logMN), where M is the number of servers, and N is the number of existing documents in the servers, plus the reallocation cost for document deletion. The price for handling document deletion is almost totally reflected by the reallocation cost, and the higher bounds of load and storage spaces, while the O(logN) additive term in the time complexity serves as the remainder.

We study the online bicriteria load balancing problem in this paper. We choose a system of distributed homogeneous file servers located in a cluster as the scenario and propose three online approximate solutions for balancing their loads and required storage spaces upon placements. We first revisit the best existing solution for simple placement (i.e., without replication and reallocation), and rewrite it in our first algorithm by imposing some flexibilities. Our second algorithm is to apply document replication. The upper bound of load is significantly reduced, without sacrificing that of the storage space. This upper bound contains at least one special case which can never be outperformed by any online simple placement algorithms. Lastly, we show that there exists an online algorithm which allows very little document reallocation, but gives an upper bound result on the load and storage space, which is never reachable by any online algorithms for simple placement. The time complexities of the first two algorithms are in O(log M), and the last algorithm runs in O(log MN) time, where M is the number of servers, and N is the number of existing documents.

We study the bicriteria load balancing problem on two independent parameters under the allowance of object reallocation. The scenario is a system of M distributed file servers located in a cluster, and we propose three online approximate algorithms for balancing their loads and required storage spaces during document placement. The first algorithm is for heterogeneous servers. Each server has its individual tradeoff of load and storage space under the same rule of selection. The other two algorithms are for homogeneous servers. The second algorithm combines the idea of the first one and the best existing solution for homogeneous servers. Using document reallocation, we obtain a smooth tradeoff curve of the upper bounds of load and storage space. The last one bounds the load and storage space of each server by less than three times of their trivial lower bounds, respectively; and more importantly, for each server, the value of at least one parameter is far from its worst case. The time complexities of these three algorithms are O(log M) plus the cost of document reallocation.

Abstract The Grid is a new type of resource sharing infrastructure. Due to software and hardware limitations, the service that a certain Grid can offer is finite, and so is the number of users it can accommodate. If the number of users is too small, much of the planned resources would be wasted. On the other hand, excessive loading due to too many users could substantially reduce the benefit enjoyed by each user and also the efficiency of the Grid service. Therefore, there are two main problems for Grid design. (1) How many users should the Grid serve so that each user can receive the maximum benefit? (2) To a certain group of users, how much resources should be invested so that the construction and maintenance of the Grid become viable? Based on the economic theory of clubs, this paper gives a quantitative analysis of the quasi‐optimal number of users and amount of each resource by regarding Grid services and resources as club goods. Based on our assumptions on the system model, we deduce two preliminary results and verify them by experiments using GridFTP. These two results allow the users to run randomized algorithms to achieve better system performance. Copyright © 2006 John Wiley & Sons, Ltd.

We study the p-median problem which is one of the classical problems in location theory. For p = 2 and on a two-dimensional mesh, we give an O(m/sup 2/ + q log q)-time approximation algorithm for solving the problem with worst-case ratio 1.5 + /spl delta/ on the communication cost, where m is the number of rows of the mesh containing demand points, n the number of columns containing demand points, m /spl ges/ n,q the number of demand points, and /spl delta/ is some positive constant which can be as small as needed.

We study approximate algorithms for placing a set of documents into M distributed Web servers in this paper. We define the load of a server to be the summation of loads induced by all documents stored. The size of a server is defined in a similar manner. We propose five algorithms. Algorithm 1 balances the loads and sizes of the servers by limiting the loads to k/sub l/ and the sizes to k/sub s/ times their optimal values, where 1/k/sub l/-1 + 1/k/sub n/-1. This result improves the bounds on load and size of servers in (L.C. Chen et al., 2001). Algorithm 2 further reduces the load bound on each server by using partial document replication, and algorithm 3 by sorting. Algorithm 4 employs both partial replication and sorting. Last, without using sorting and replication, we give algorithm 5 for the dynamic placement at the cost of a factor Q(log M) in the time-complexity.

Mobility of hosts increases the system flexibility, but also costs some problems in management. In our model, we consider an (ad hoc) arbitrary wireless backbone with some mobile hosts, which we call mobile agents. A mobile agent can visit every node in the backbone. It can store data in any nodes, invoke processes for computation and waiting for messages. The output of computation, messages, and the stored data is sent back to the home of the mobile agent upon request or whenever the node needs the space for other purpose. We give protocols (1) for the mobile agents to store its data to a foreign node, and (2) for a node to collect some buffer space occupied by other mobile agent(s), and (3) for the a node to collect the data stored outside by its mobile agent.

We study the p-median problem which is one the classical problems in location theory. For p = 2 and on a two-dimensional mesh, we give an O(mn 2 p)-time algorithm for solving the problem, where, assuming that m n, m is the number of rows of the mesh containing demand points, n the number of columns containing demand points, and p the number of demand points. 1 Introduction The mesh (and its variant, the torus) is a popular topology for processor interconnection in parallel computers. It has practical advantages such as low degree and perfectly compact layout when compared to other well-known topologies, for example the hypercube. A notable example of parallel computers based on the mesh topology is the iWarp system [4]. Dally has shown that low-dimensional networks have lower latency and higher hot-spot throughput than high-dimensional networks [2]. In this paper, we study the problem of finding a 2-median set in a two-dimensional mesh. The p-median problem is a well-known problem ...

Interval routing is a space-efficient method for point-to-point networks. It is based on labeling the edges of a network with intervals of vertex numbers (called interval labels). An M-label scheme allows up to M labels to be attached on an edge. For arbitrary graphs of size m, n the number of vertices, the problem is to determine the minimum RP necessary for achieving optimality in the length of the longest routing path. The longest routing path resulted from a labeling is an important indicator of the performance of any algorithm that runs on the network. We prove that there exists a graph with D=/spl Omega/(n/sup 1/3/) such that if M/spl les/n/18D-O(/spl radic/n/D) the longest path is no shorter than D+/spl Theta/(D//spl radic/M). As a result, for any M-label 1RS, if the longest path is to be shorter than D+/spl Theta/(D//spl radic/M), at least M=/spl Theta/(n/D) labels per edge would be necessary.

Interval routing is a space-efficient routing method for computer networks. The method is said to be optimal if it can generate optimal routing paths for any source-destination node pair. A path is optimal if it is a shortest path between the two nodes involved. A seminal result in the area, however, has pointed out that ‘the interval routing algorithm cannot be optimal in networks with arbitrary topology’. The statement is correct but the lower bound on the longest routing path that was derived is not. We give the counterproof in this paper and the corrected bound.

Interval routing is a space-efficient routing method for point-to-point communication networks. The method has drawn considerable attention in recent years because of its being incorporated into the design of a commercially available routing chip. The method is based on proper labeling of edges of the graph with intervals. An optimal labeling would result in routing of messages through the shortest paths. Optimal labelings have existed for regular as well as some of the common topologies, but not for arbitrary graphs. In fact, it has already been shown that it is impossible to find optimal labelings for arbitrary graphs. In this paper, we prove a 7 D/4 - 1 lower bound for interval routing in arbitrary graphs, where D is the diameter—i.e., the best any interval labeling scheme could do is to produce a longest path having a length of at least 7 D/4 - 1. © 1997 John Wiley & Sons, Inc.