29681392
Schedulability-oriented replication of periodic tasks in distributed real-time systems
We consider the schedulability-oriented replication problem of a set of periodic real-time tasks where each task can be decomposed into several modules and intermodule communications. The objective is to find an allocation in which there exists a feasible schedule for the given task set. In this paper, we adopt a communication model where the replication of modules is not for the sake of fault tolerance but for increasing the degree of schedulability. To solve the problem, we develop a replication technique and embed the technique in a simulated annealing algorithm. Experimental results show that such replication may lead to a higher degree of schedulability and obtain a feasible solution.
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.
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.
6666618
Low-Power Design for Real-Time Systems
Real-time Systems often are located in the special environments where the power consumption is a big concern. Upon presence of timing constraints, the low power design on the real-time systems has significant impact on the performance as well as the schedulability of the systems. The system developers are facing the challenges for reducing the power consumption and meeting the timing constraints in the real-time systems.This paper represents one of few attempts to address the issue of the low power design on real-time systems. We present two power reduction methods: one is at the software compilation level and the other at the operating system level. Given a real-time program, an inter-instruction power reduction technique is proposed to transform the program to another one with lower power consumption. In addition, a scheduling algorithm for real-time operating systems is proposed to reschedule real-time programs when the execution time of the programs is changed. Therefore, the proposed scheduling algorithm works together with the proposed power reduction technique to make sure all programs meet their deadlines and to improve the system schedulability. We also evaluate the performance of the proposed inter-instruction reduction method by comparing it with the cold scheduling algorithm and show that the proposed method outperforms the cold scheduling algorithm and reduces more energy power.
574471
Allocation and scheduling of real-time periodic tasks with relative timing constraints
Allocation problem has always been one of the fundamental issues of building the applications in real-time computing systems. For real-time applications, the allocation problem should directly address the issues of task and communication scheduling. In this context, the allocation of tasks has to fully utilize the available processors and the scheduling of tasks has to meet the specified timing constraints. Clearly, the execution of tasks under the allocation and schedule has to satisfy the precedence, resources, and other synchronization constraints among them. Recently, the timing requirements of the real-time systems emerge that the relative timing constraints are imposed on the consecutive executions of each task and the inter-task temporal relationships are specified across task periods. In this paper we consider the allocation and scheduling problem of the periodic tasks with such timing requirements. Given a set of periodic tasks, we consider the least common multiple (LCM) of the task periods. Each task is extended to several instances within the LCM. The scheduling window for each task instance is derived to satisfy the timing constraints. We develop a simulated annealing algorithm as the overall control algorithm. An example problem of the sanitized version of the Boeing 777 Aircraft Information Management System is solved by the algorithm. Experimental results show that the algorithm solves the problem in a reasonable time complexity.
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.
1344352
Quality meshing for polyhedra with small angles
We present an algorithm to compute a Delaunay mesh conforming to a polyhedron possibly with small input angles. The radius-edge ratio ofmost output tetrahedra are bounded by a constant, except possibly those that are provably close to small angles. Further, the mesh is graded, that is, edge lengths are at least a constant fraction of the local feature sizes at the edge endpoints. Unlike a previous algorithm, this algorithm is simple to implement as it avoids computing local feature sizes and protective zones explicitly. Our experimental results confirm our claims and show that few skinny tetrahedra remain.
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.
17584518
On beta-skeleton as a subgraph of the minimum weight triangulation
Abstract Given a set S of n points in the plane, a triangulation is a maximal set of non-intersecting edges connecting the points in S . The weight of the triangulation is the sum of the lengths of the edges. In this paper, we show that for β>1/ sin κ , the β -skeleton of S is a subgraph of a minimum weight triangulation of S , where κ= tan −1 (3/ 2 3 )≈ π /3.1 . There exists a four-point example such that the β -skeleton for β sin ( π /3) is not a subgraph of the minimum weight triangulation.
8458726
Approaching the largest β-skeleton within a minimum weight triangulation
Given a set S of n points in the plane, a triangulation is a maximal set of non-intersecting edges connecting the points in S. The weight of the triangulation is the sum of the lengths of the edges. The complexity of computing the minimum weight triangulation is currently unresolved. In this paper, we show that for ~ > 1/ sin K, the &skeleton of S is a subgraph of a minimum weight triangulation of S, where ~ = tan-1(3/m) N 7r/3.l. There exists a four point example such that the /3skeleton for ~ < 1/ sin(r/3) is not a subgraph of the minimum weight triangulation.
76461
Software Architecture-Based Adaptation for Pervasive Systems
An important requirement for pervasive computing systems is the ability to adapt at runtime to handle varying resources, user mobility, changing user needs, and system faults. In this paper we describe an approach in which dynamic adaptation is supported by the use of software architectural models to monitor an application and guide dynamic changes to it. The use of externalized models permits one to make reconfiguration decisions based on a global perspective of the running system, apply analytic models to determine correct repair strategies, and gauge the effectiveness of repair through continuous system monitoring. We illustrate the application of this idea to pervasive computing systems, focusing on the need to adapt based on performance-related criteria and models.