2936245
On failure recoverability of client-server applications in mobile wireless environments
Analytical results for the Cdf of the failure recovery time for client-server applications in mobile wireless environments characterized by logging, and mobility handoff strategies for facilitating failure recovery are reported in the paper. The results can be applied to determine if a mobile application can satisfy its recoverability requirement upon a mobile host failure when operating under a set of parameter values characterizing the mobile application, the underlying client-server environment, and the logging & mobility handoff strategies adopted by the mobile application. Model parameters which affect the shape of the failure recovery time Cdf for two mobility handoff strategies, namely, Eager and Lazy, are identified, and their effects are analyzed, with numerical data and result interpretations given. A tradeoff analysis between the cost invested by these two mobility handoff strategies for maintaining the logging and checkpoint information before failure versus the return of investment in terms of improved failure recoverability is given, and the best checkpoint interval period that would yield the best return of investment for the eager mobility handoff strategy over the lazy strategy is identified.
21934561
Location and Configuration Management in Mobile-Switch ATM Networks
The features of two important application scenarios, supporting mobile switches with fixed end users and mobile switches with mobile users, are dramatically different from those of the traditional wired network structure. To exploit mobile switches, the location and configuration management of mobile switches is essential to handle the mobility and topology change of the wireless/mobile ATM network. In this paper we address the location management and configuration problems of mobile switches in an ATM network. We investigate several aspects of the location management problem including architecture to support switch mobility, mobile switch tracking, and mobile switch locating. We propose an approach that is based on the Private Network-Network Interface (PNNI) protocol. We extend the PNNI protocol to enable it to handle mobile switches. Moreover, we develop analytical models to determine the tracking and locating costs for mobile switches under the proposed scheme. The models illustrate the relation between total cost (tracking cost + locating cost) and peer group size. The models can be used to derive the optimal configuration for an ATM network with mobile switches.
10474032
Dynamic quota-based admission control with sub-rating in multimedia servers
Abstract. An admission control algorithm for a multimedia server is responsible for determining if a new request can be accepted without violating the Quality of Service (QoS) requirements of the existing requests in the system. A novel quota-based admission control algorithm with sub-rating for two priority classes of requests is proposed in this study. The server capacity is divided into three partitions based on the quota values: one for each class of requests and one common pool shared by two classes of requests. Reward and penalty are adopted in the proposed system model. High-priority requests are associated with higher values of reward as well as penalty than low-priority ones. Given the characteristics of the system workload, the proposed algorithm finds the best partitions, optimizing the system performance based on the objective function of the total reward minus the total penalty. The sub-rating mechanism will reduce the QoS requirements of several low- priority clients, by cutting out a small fraction of the assigned server capacity, to accept a new high- priority client and to achieve a higher net earning value. A stochastic Petri-Net model is used to find the optimal quota values and two approximation approaches are developed to find sub-optimal settings. The experiment results show that the proposed algorithm performs better than one without sub-rating mechanism, and that the sub-optimal solutions found by the proposed approximation approaches are very close to optimal ones. The approximation approaches enable the algorithm to dynamically adjust the quota values, based on the characteristics of the system workload, to achieve higher system performance.
14292166
A self-adjusting quality of service control scheme
We propose and analyze a self-adjusting Quality of Service (QoS) control scheme with the goal of optimizing the system reward as a result of servicing different priority clients with varying workload, QoS and reward/penalty requirements. Our scheme is based on resource partitioning and designated "degrade QoS areas" such that system resources are partitioned into priority areas each of which is reserved specifically to serve only clients in a corresponding class with no QoS degradation, plus one "degraded QoS area" into which all clients can be admitted with QoS adjustment being applied only to the lowest priority clients. We show that the best partition is dictated by the workload and the reward/penalty characteristics of clients in difference priority classes. The analysis results can be used by a QoS manager to optimize the system total rewawrd dynamically in response to changing workloads at run time. We demonstrate the validity of our scheme by means of simulation and comparing the proposed QoS self-adjusting scheme with those that do not use resource partitioning or designated degraded QoS area.
9588683
Performance evaluation of an admission control algorithm: dynamic threshold with negotiation
An admission control algorithm for a multimedia server is responsible for determining if a new request can be accepted without violating the QoS requirements of the existing requests in the system. Most admission control algorithms treat every request uniformly and hence optimize the system performance by maximizing the number of admitted and served requests. In practice, requests might have different levels of importance to the system. Requests offering high contribution or reward to the system performance deserve priority treatment. Failure of accepting a high-priority request would incur high penalty to the system.A novel threshold-based admission control algorithm with negotiation for two priority classes of requests is proposed in our previous study. The server capacity is divided into three partitions based on the threshold values: one for each class of requests and one common pool shared by two classes of requests. Reward and penalty are adopted in the proposed system model. High-priority requests are associated with higher values of reward as well as penalty than low-priority ones. In this paper, given the characteristics of the system workload, the proposed analytical models aim to finds the best partitions, optimizing the system performance based on the objective function of the total reward minus the total penalty. The negotiation mechanism reduces the QoS requirements of several low-priority clients, by cutting out a small fraction of the assigned server capacity, to accept a new high-priority client and to achieve a higher net earning value. Stochastic Petri-Net model is used to find the optimal threshold values and two analytical methods are developed to find sub-optimal settings. The experiment results show that the sub-optimal solutions found by the proposed analytical methods are very close to optimal ones. The methods enable the algorithm to dynamically adjust the threshold values, based on the characteristics of the system workload, to achieve higher system performance.
30645069
Backtrack Routing and Priority-Based Wavelength Assignment in WDM Networks
In this paper, we consider two key problems in the WDM networks: the wavelengh assignment and routing problems. The objective of the problems is to minimize the request blocking rate. We propose two priority-based methods for the wavelength assignment problem: static and dynamic strategies. Based on the priority of an incoming request, the proposed methods allocate a wavelength among the available wavelengths for the given priority. Analytic models and simulations are presented for the proposed wavelength assignment methods so as to analyse the link blocking rate. The simulation results show that the link blocking rate by the dynamic strategy is less than that by the assignment strategy. We also develop a routing algorithm that works together with the proposed wavelength assignment methods to reduce the overall blocking rates. The proposed routing method maintains a routing tree for a given connection request. Based on the routing tree, the algorithm finds a route with one available wavelength for each link along the route. We compare the proposed routing method with the fixed routing and fixed alternate routing algorithms. The experiments show that the proposed routing algorithm performs better than the fixed routing and the alternate routing methods.
206577228
Fast Trellis-Coded Color Quantization of Images
We examine color quantization of images using trellis-coded quantization (TCQ) in both the RGB domain and YUV domain. Together with a simple dithering scheme, an eight-bit trellis-coded color quantizer reproduces images that are visually indistinguishable from the 24-bit originals. It can be viewed as a predictive trellis-coded color quantization scheme. We also study trellis-coded vector quantization (TCVQ) for color quantization. Our proposed TCQ-based color quantization schemes are universal in the sense that no training or look-up table is needed. The complexity of TCQ is linear with respect to image size, making trellis-coded color quantization suitable for color printing, real-time interactive graphics and window-based display environment.
2549315
Quality meshing with weighted Delaunay refinement
Delaunay meshes with bounded circumradius to shortest edge length ratio have been proposed in the past for quality meshing. The only poor quality tetrahedra called slivers that can occur in such a mesh can be eliminated by the sliver exudation method. This method has been shown to work for periodic point sets, but not with boundaries. Recently a randomized point-placement strategy has been proposed to remove silvers while conforming to a given boundary. In this paper we present a deterministic algorithm for generating a weighted Delaunay mesh which respects the input boundary and has no poor quality tetrahedron including silvers. This success is achieved by combining the weight pumping method for sliver exudation and the Delaunay refinement method for boundary conformation. We show that an incremental weight pumping can be mixed seamlessly with vertex insertions in our weighted Delaunay refinement paradigm.
2640918
Iterated Weaker-than-Weak Dominance
We introduce a weakening of standard game-theoretic dominance conditions, called δ-dominance, which enables more aggressive pruning of candidate strategies at the cost of solution accuracy. Equilibria of a game obtained by eliminating a δ-dominated strategy are guaranteed to be approximate equilibria of the original game, with degree of approximation bounded by the dominance parameter, δ. We can apply elimination of δ-dominated strategies iteratively, but the δ for which a strategy may be eliminated depends on prior eliminations. We discuss implications of this order independence, and propose greedy heuristics for determining a sequence of eliminations to reduce the game as far as possible while keeping down costs. A case study analysis of an empirical 2-player game serves to illustrate the technique, and demonstrate the utility of weaker-than-weak dominance pruning.
8012254
Software architecture-based adaptation for Grid computing
Grid applications must increasingly self-adapt dynamically to changing environments. In most cases, adaptation has been implemented in an ad hoc fashion, on a per-application basis. This paper describes work which generalizes adaptation so that it can be used across applications by providing an adaptation framework. This framework uses a software architectural model of the system to analyze whether the application requires adaptation, and allows repairs to be written in the context of the architectural model and propagated to the running system. In this paper, we exemplify our framework by applying it to the domain of load-balancing a client-server system. We report on an experiment conducted using our framework, which illustrates that this approach maintains architectural requirements.
751641
Market-Based Resource Allocation for Information-Collection Scenarios
Dynamic decentralized resource allocation for information-collection can play a critical role in emergency scenarios. We explore two simplified scenarios for information-collection, and define market games for allocating resources to interdependent tasks. Experiments with a market game for disaster-response illustrate our general methodology for analyzing strategic interactions in such an environment.