Performance evaluation of rule grouping on a real-time expertsystem architecture

Uses a Markov process to model a real-time expert system architecture characterized by message passing and event-driven scheduling. The model is applied to the performance evaluation of rule grouping for real-time expert systems running on this architecture. An optimizing algorithm based on Kernighan-Lin heuristic graph partitioning for the real-time architecture is developed and a demonstration system based on the model and algorithm has been developed and tested on a portion of the advanced GPS receiver (AGR) and manned manoeuvring unit (MMU) knowledge bases     

Effect of parallel planning on system reliability of real-timeexpert systems

Real-time expert systems (RTXS) are expert systems embedded in process-control systems which must plan and execute control strategies in response to external events within a real-time constraint. This paper presents a method for estimating the reliability of uni-processor and multi-processor RTXS. The paper discusses why there are intrinsic faults in RTXS programs that must be considered in their reliability modeling. Then, it shows that for uni-processor RTXS, no single planning algorithm can avoid all types of intrinsic faults. Finally, it presents a multiprocessor architecture with parallel planning with the objective of reducing intrinsic faults of RTXS and improving the embedded system reliability. A robot control system illustrates the method     

Algorithms for supporting disconnected write operations for wireless Web access in mobile client-server environments

In a wireless mobile client-server environment, a mobile user may voluntarily disconnect itself from the Web server to save its battery life and avoid high communication prices. To allow Web pages to be updated while the mobile user is disconnected from the Web server, updates can be staged in the mobile host and propagated back to the Web server upon reconnection. In this paper, we analyze algorithms for supporting disconnected write operations for wireless Web access and develop a performance model to identify the optimal length of the disconnection period under which the cost of update propagation is minimized. The analysis result is particularly applicable to Web applications which allow wireless mobile users to modify Web contents while on the move. We show how the result can be applied to real-time Web applications such that the mobile user can determine the longest disconnection period such that it can still propagate updates to the server before the deadline so that a minimum communication cost is incurred.     

A reliability model for real-time rule-based expert systems

This paper uses two modeling tools to analyze the reliability of real-time expert systems: (1) a stochastic Petri net (SPN) for computing the conditional response time distribution given that a fixed number of expert system match-select-act cycles are executed, and (2) a simulation search tree for computing the distribution of expert system match-select-act cycles for formulating a control strategy in response to external events. By modeling the intrinsic match-select-act cycle of expert systems and associating rewards rates with markings of the SPN, the response time distribution for the expert system to reach a decision can be computed as a function of design parameters, thereby facilitating the assessment of reliability of expert systems in the presence of real-time constraints. The utility of the reliability model is illustrated with an expert system characterized by a set of design conditions under a real-time constraint. This reliability model allows the system designers to: (1) experiment with a range of selected parameter values; and (2) observe their effects on system reliability     

Adaptive per-user per-object cache consistency management for mobile data access in wireless mesh networks

We propose and analyze an adaptive per-user per-object cache consistency management (APPCCM) scheme for mobile data access in wireless mesh networks. APPCCM supports strong data consistency semantics through integrated cache consistency and mobility management. The objective of APPCCM is to minimize the overall network cost incurred due to data query/update processing, cache consistency management, and mobility management. In APPCCM, data objects can be adaptively cached at the mesh clients directly or at mesh routers dynamically selected by APPCCM. APPCCM is adaptive, per-user and per-object as the decision regarding where to cache a data object accessed by a mesh client is made dynamically, depending on the mesh client’s mobility and data query/update characteristics, and the network’s conditions. We develop analytical models for evaluating the performance of APPCCM and devise a computational procedure for dynamically calculating the overall network cost incurred. We demonstrate via both model-based analysis and simulation validation that APPCCM outperforms non-adaptive cache consistency management schemes that always cache data objects at the mesh client, or at the mesh client’s current serving mesh router for mobile data access in wireless mesh networks.     

Analyzing User-Perceived Dependability and Performance Characteristics of Voting Algorithms for Managing Replicated Data

User-perceived dependability and performance metrics are very different from conventional ones in that the dependability and performance properties must be assessed from the perspective of users accessing the system. In this paper, we develop techniques based on stochastic Petri nets (SPN) to analyze user-perceived dependability and performance properties of quorum-based algorithms for managing replicated data. A feature of the techniques developed in the paper is that no assumption is made regarding the interconnection topology, the number of replicas, or the quorum definition used by the replicated system, thus making it applicable to a wide class of quorum-based algorithms. We illustrate this technique by comparing conventional and user-perceived metrics in majority voting algorithms. Our analysis shows that when the user-perceiveness is taken into consideration, the effect of increasing the network connectivity and number of replicas on the availability and dependability properties perceived by users is very different from that under conventional metrics. Thus, unlike conventional metrics, user-perceived metrics allow a tradeoff to be exploited between the hardware invested, i.e., higher network connectivity and number of replicas, and the performance and dependability properties perceived by users.     

Admission Control Algorithms for Revenue Optimization with QoS Guarantees in Mobile Wireless Networks

We propose and analyze call admission control algorithms integrated with pricing for revenue optimization with QoS guarantees to serve multiple service classes in mobile wireless networks. Traditional admission control algorithms make acceptance decisions for new and handoff calls to satisfy certain QoS constraints such as the dropping probability of handoff calls and the blocking probability of new calls being lower than a pre-specified threshold. We analyze a class of partitioning and threshold-based admission control algorithms that make acceptance/rejection decisions not only to satisfy QoS requirements but also to optimize the revenue of the system by taking prices and arrival/departure information of service calls into account. We show that for a “charge-by-time” pricing scheme, there exist optimal resource allocation settings under which the partitioning and threshold-based admission control algorithms would produce the maximum revenue obtainable by the system without sacrificing QoS requirements. Further, we develop a new hybrid admission control algorithm which outperforms both partitioning and threshold-based admission control algorithms over a wide range of input parameters characterizing the operating environment and service workload conditions. Methods for utilizing of the analysis results for realtime admission control for revenue optimization with QoS guarantees are described with numerical data given to demonstrate the applicability.     

DMAP: integrated mobility and service management in mobile IPv6 systems

Mobile IPv6 (MIPv6) is a work in progress IETF standard for enabling mobility in IPv6 networks and is expected to have wide deployment. We investigate an integrated mobility and service management scheme based on MIPv6 with the goal to minimize the overall network signaling cost in MIPv6 systems for serving mobility and service management related operations. Our design extends IETF work-in-progress Hierarchical Mobile IPv6 (HMIPv6) with the notion of dynamic mobility anchor points (DMAPs) for each mobile node (MN) instead of static ones for all MNs. These DMAPs are access routers chosen by individual MNs to act as a regional router to reduce the signaling overhead for intra-regional movements. The DMAP domain size, i.e., the number of subnets covered by a DMAP, is based on the MN’s mobility and service characteristics. Under our DMAP protocol, a MN interacts with its home agent and application servers as in the MIPv6 protocol, but optimally determines when and where to launch a DMAP to minimize the network cost in serving the user’s mobility and service management operations. We demonstrate that our DMAP protocol for integrated mobility and service management yields significantly improved performance over basic MIPv6 and HMIPv6.     

Analysis and Comparison of Location Strategies for Reducing Registration Cost in PCS Networks

In mobile environments, a personal communication service (PCS) network must keep track of the location of each mobile user in order to correctly deliver calls. A basic scheme used in the standard IS-41 and GSM protocols is to always update the location of a mobile user whenever the mobile user moves to a new location. The problem with this approach is that the cost of location update operations is very high especially when the mobile user moves frequently. In recent years, various location management strategies for reducing the location update cost have been proposed. However, the performance issue of these proposed algorithms remains to be investigated. In this paper, we develop two Markov chains to analyze and compare the performance of two promising location update strategies, i.e., the two location algorithm (TLA) and the forwarding and resetting algorithm (FRA). By utilizing the Markov chain, we are able to quickly answer what-if questions regarding the performance of PCS networks under various workload conditions and also identify conditions under which one strategy can perform better than the others. Using the cost due to location update and search operations between two successive calls to a mobile user as a performance measure, we show that when the mobile user exhibits a high degree of locality and the mobile user's call-to-mobility ratio (CMR) is low, TLA can significantly outperform both FRA and IS-41. On the other hand, when CMR is high, FRA is the winner. Furthermore, unlike TLA which may perform worse than IS-41 at high CMR values, FRA at identified optimal conditions can always perform at least as good as IS-41, suggesting that FRA over TLA should be used as a generic scheme in reducing the location cost in the PCS network to cover all possible per-user CMR values.