Connected and digital electricity substations based on IEC–61850 standards enable novel applications. On the other hand, such connectivity also creates an extended attack surface. Therefore, Intrusion Detection Systems (IDSs) have become an essential component of safeguarding substations from malicious activities. However, in contrast to traditional information technology systems, there is a serious lack of realistic data for training, testing, and evaluating IDSs in smart grid scenarios. Many existing substation IDSs rely on datasets from other contexts or on proprietary datasets that do not allow reproducibility, validation, or performance comparison with competing algorithms. To address this issue, we propose the Efficacious Reproducer Engine for Network Operations (ERENO) synthetic traffic generation framework based on the IEC–61850 standard specifications. As an additional contribution, and as a proof-of-concept, we create and make available a suite of realistic IEC–61850 datasets that model 8 use cases, namely traffic for 7 common attacks and one for normal network traffic. Based on those datasets, we further evaluate how enriched features combining raw data from the substation can significantly improve intrusion detection performance. Our results suggest that it can improve F1-Score up to 47.22% for masquerade attacks.

Mobile devices’ popularization has brought several new applications to communication networks. As we move into an increasingly denser scenario, problems such as collisions between transmissions and unbalanced load become more pronounced. Moreover, while station-based handoff is inefficient to reduce these issues, network-wide handover decisions might provide better network resource management. This paper proposes LEAF, an access point virtualization solution based on Software Defined Networking to enable station (STA) handover conducted by the network, based on a global scope. Unlike other solutions in the literature, our proposal fully supports multichannel migrations through the IEEE 802.11h Channel Switch Announcement without restricting the channel utilization by the access points. To demonstrate the feasibility of such an approach, we present experimental data regarding the behavior of several different devices in face of this mechanism. We also evaluate our complete virtualization solution, which reveals that the handoff of STAs did not lead to significant packet losses or delays in STAs’ connections, while providing a foundation to improve network’s self-management and flexibility, allowing association control and load balancing tasks to be executed on top of our solution.

The fifteen papers in this special section focus on real-time systems. They present state-of-the-art work in theory, design, analysis, implementation, and evaluation of real-time systems. All the papers address some form of real-time requirements such as deadlines, response times or delays/latency and consider not only hard real-time systems but also time-sensitive systems in general. Following an open call for papers, authors from all over the globe sent 53 submissions on a broad range of topics. The review committee of top experts worldwide conducted rigorous professional reviews. Each paper at least 3 reviews in the first round. Approximately 50 reviews were performed in the second round to evaluate the revised submissions.

Private blockchain platforms tend to apply deterministic consensus mechanisms as a more efficient alternative to the proof-based consensus. Deterministic mechanisms tolerate two types of failures, Byzantine, and Crash-Fault. Byzantine-Fault tolerant consensus assumes restrictive assumptions of time and number of failures to guarantee the validity, while the termination depends on node message broadcasting. Crash-Fault tolerant consensus mechanisms induce lower overhead and faster termination than Byzantine-Fault tolerant mechanisms at the cost of not tolerating malicious behaviors. This paper explores different overlay topologies to assess a lightweight consensus mechanism based on vicinity voting with reliable message broadcasting. The paper proposes different ways to compose the consensus quorum according to the vicinity models. Vicinity models applied in the overlay network allow for relaxing the trade-off between agreement and termination. Analytical and experimental results for different physical topologies show that certain vicinity models guarantee higher number of nodes reached at the time of reaching the consensus threshold (higher than 90% of all nodes) with a lower cost at the exchange of lower fault tolerance. Other models induce a lower agreement while increase fault tolerance (higher than 50%).

Advances in deep vision techniques and the ubiquity of smart cameras will drive the next generation of video analytics. However, video analytics applications consume vast amounts of energy as deep learning techniques are power-hungry. In this article, we focus on a parking video analytics platform and propose RL-CamSleep, a deep reinforcement learning-based technique, to actuate the cameras to reduce the energy footprint while retaining the system’s utility. Our key insight is that many video-analytics applications do not need to be always operational, and we can design policies to activate video analytics only when necessary. We design two modes of operation for the reinforcement learning (RL) controller: (i) cloud-based mode and (ii) grid-isolated solar-powered mode. In the cloud-based mode, the controller runs on the cloud to control the cameras, whereas, in the solar-powered mode, the RL controller is constrained by the energy produced by solar. We evaluate our approach on a city-scale parking dataset having 76 streets spread across a city. Our analysis shows RL-CamSleep can learn an adaptive policy that reduces the average energy consumption by 76% and achieves an average accuracy of 98%. For the grid-isolated mode, RL-CamSleep outperforms other baseline techniques demonstrating the need for adaptive policy in energy-constrained environments.

With billions of the Internet of Things (IoT) world-wide, the proliferation of IoT technologies will increase the global energy footprint. To date, much of the focus has been on addressing privacy exposure with approaches that remove sensitive information and, at the same time, ensure that users still derive utility from the data. In this paper, we bring the energy aspects of privatizers into the modeling and analysis of utility-privacy (UP) tradeoffs in IoT. We present a framework that enables users to examine (a) the energy cost of privatizing data, (b) the effect on the utility of the data, and (c) the privacy achieved. We evaluate our model with audio and image data and show that we can reduce energy consumption while retaining the user's chosen UP tradeoff point.

Cyber-Physical Systems (CPS) are the basis for the world’s critical infrastructure and, thus, have the potential to significantly impact human lives in the near future. In recent years, there has been an increasing demand for connectivity in CPS, which has brought to attention the issue of cybersecurity. Aside from traditional information systems threats, CPS face new challenges due to the heterogeneity of devices and protocols, as well as its strong reliability requirements. In this work, we provide a brief overview of the CPS architecture and applications and describe the security challenges in the three CPS layers of perception, transmission, and application. Besides, we discuss how feature selection (FS) may improve intrusion detection performance. In particular, we evaluate how metaheuristic approaches can improve classification performance in CPS perception, transmission, and application layers. Our results reveal that (i) Greedy Randomized Adaptive Search Procedure (GRASP) outperforms traditional filter-based methods, and (ii) using the proposed enhanced approaches in GRASP construction and local search phases can enhance the average F1-Score of five classifier algorithms.

No abstract available.

The Smart Grid is a high availability system that requires fault recovery protocols to minimize downtime. In addition, recovery, in most cases, must be made within certain temporal constraints. The IEC 62493-3 standard defines the Parallel Redundancy Protocol (PRP) and High-availability Seamless Redundancy (HSR) as protocols for dealing with link layer communication failures in electrical substations. There are variations that perform the same functionality handling packets at the IP layer, such as iPRP. Those protocols promise zero-time recovery by proactively sending duplicate packets across distinct and independent paths. In this paper, those fault recovery protocols are analyzed by means of simulations. Our results show that, in realistic setups, recovery time is never actually zero and that, under certain conditions, this time can exceed the temporal requirements that some protection applications demand for proper operation.

Wireless control systems (WCSs) have gained much attention lately, due to their easy deployment and flexibility compared to wired control systems. However, this comes at the cost of possibly increased network delay and packet losses, that can significantly impact the control system performance, and possibly its stability. Such problems become even more relevant if the network is shared among different control systems, and thus becomes a scarce resource, like in Industrial Internet of Things applications. In this paper, we describe how to assign packet priorities dynamically when there are many physical systems sharing a given network, aiming at minimizing the performance degradation of the WCS. Towards that, we present a network model including both delay and packet losses, both of which are very important for the control system performance. Our solution is evaluated over two different use cases to show the generality of the approach: the WCS for a set of inverted pendula, and the WCS for small modular reactors in a nuclear power plant. The results show that the proposed approach allows for a more stable performance even in presence of highly nonlinear systems, sensitive to time-varying delays, as well as in presence of high network interference.

Many server applications achieve only a fraction of their theoretical peak performance due to bottlenecks in the shared caches, instruction execution units, I/O or memory bandwidth, even though the remaining resources may be underutilized. It is very hard for developers and runtime systems to ensure that all these critical resources are fully exploited by a single application. An attractive technique for increasing server system utilization is to colocate multiple applications on the same server. When applications share critical resources, however, these applications may adversely affect each other, due to contention on the shared resources. In this paper, we show that server efficiency can be improved by modeling the expected performance degradation of colocated applications from measured hardware performance counters, and exploiting such a model to determine an optimized mix of colocated applications. This paper presents a novel resource management approach and makes the following contributions: (1) a new machine learning model to predict the performance degradation of colocated applications from hardware counters and (2) an intelligent scheduling scheme deployed on an existing resource manager to enable application co-scheduling with minimum performance degradation. Our results show that our approach achieves performance improvements of 15 % (avg) and 26 % (max) compared to the standard policy commonly used by existing job managers.

We have implemented an opensource prototype system called Occam1 to define, conduct, and share artifacts as executable content. Occam is a platform to create, run and share experiments. It allows users to contribute their own artifacts, which can be composed with other artifacts and used in workflows to define and conduct experiments. Workflows are directed acyclic graphs that describe the data flow within experiments. The execution of the experiment is automated by Occam, according to the workflow that describes it. Occam preserves provenance information and allows the inspection of the source code, configuration parameters, and datasets used in experiments; more importantly, it allows access to all this information from simply clicking on (the PDF-embedded) plots/results. In fact, with appropriate support in a digital library, we have implemented a mechanism in which clicking on a plot in a published article takes the user to the experiment setup in Occam. This strict approach to executable content preservation imposes little overhead on developers, but it greatly improves the preservation, reuse, and extensibility of software experiments. Consequently, Occam improves science by creating a tool and process that embodies the scientific method.

Cooperating mobile robots are real-time systems that often require mutual synchronisation, either to carry out cooperative sensing and actuation, or to improve the quality of wireless communications. Concerning this last aspect, a common technique to improve the communication channel is to eliminate access collisions by allocating predefined disjoint time slots to robots, in a circular list, which is known as Time Division Multiple Access (TDMA). This technique typically requires a global clock to identify each slot. However, this method is not robust with respect to asynchronous transmissions generated by external or joining nodes. Consequently, this work proposes a global TDMA protocol that allows for real-time and guaranteed delivery of messages within deadlines, given its predictable schedule, and that: i) applies to dynamic mesh networks of cooperating mobile robots; ii) synchronises slots in a relative fashion using locally perceived delays of message exchanges that are globalised throughout the network, thus not relying on a global clock; and iii) tolerates external traffic and asynchronous joining robots using underneath standard ad-hoc wireless RF technologies that provide CSMA-type arbitration. We describe our protocol and prove that under common operating conditions all robots eventually reach synchronisation. We also propose a heuristic for the few cases that were not covered by the previous proof, which always led to consensus under extensive simulation testing. To the best of our knowledge, this is the first guaranteed clockless synchronisation approach for ad-hoc networks of mobile robots that works over commodity wireless protocols.

Control systems using sensors and wireless networks are becoming more prevalent, due to its ease of deployment: no wires and longer battery life. However, network delays and packet losses can degrade control system performance, which leads us to find the optimal network configuration to minimize that impact. Another main difficulty of having wireless networks for control systems is caused by interference and noise that produce time-varying fault patterns, which motivates us to do network reconfiguration at run time. To solve these two issues, we propose a network reconfiguration framework with offline and online components that considers time-correlated link failures. We are conducting a case study to wirelessly control a nonlinear primary heat exchanger system in a small modular nuclear reactor of a nuclear power plant.

Wireless control systems are gaining a lot of attention, due to its easy deployment comparing to wired control systems recently. Real-time wireless networks have been proposed to give preference to high-priority tasks and keep timeliness of packet delivery. In control systems, however, network delay influences significantly the control system performance, whose applications have dynamic characteristics. Motivated by the observation, we propose a dynamic network scheduling solution to minimize the error in control applications in a system, by considering the application behavior and changing its priority based on dynamic conditions. We plan to conduct a case study based on a nuclear power plant to analyze the interaction between cross-layer real-time network scheduling and control.

This paper describes Concurrent Migration of Multiple Pages (CMMP), a new hardware-software mechanism for managing hybrid main memory (DRAM+PCM). CMMP migrates multiple pages concurrently without significantly affecting the memory bandwidth available to applications. CMMP provides a simple interface for the OS to observe memory access patterns. CMMP reduces PCM-to-DRAM transfer bandwidth by copying blocks on-demand. It also reduces DRAM-to-PCM bandwidth by suppressing the transfer of untouched blocks back to PCM. Compared to a state-of-the-art page migration approach for hybrid memory, CMMP improves performance by 14% and reduces energy consumption by 29% on average.

One of the main challenges in data center systems is operating under certain Quality of Service (QoS) while minimizing power consumption. Increasingly, data centers are adopting heterogeneous server architectures with different power-performance trade-offs. This requires careful understanding of the application behavior across multiple architectures at runtime so as to enable meeting specified power and performance requirements. In this work, we present and evaluate REPP-H (Runtime Estimation of Performance and Power on Heterogeneous data centers). REPP-H leverages hardware performance counters available on all major server architectures to ensure a highly responsive power capping mechanism and delivering a minimum performance in a single step. We experimentally show that REPP-H can successfully estimate power and performance of several single-threaded and multiprogrammed workloads. The average errors on ARM, AMD and Intel architectures are, respectively, 7.1%, 9.0%, 7.1% when predicting performance, and 6.0%, 6.5%, 8.1% when predicting power on those heterogeneous servers.

In a multicore system, many applications share the last-level cache (LLC) and memory bandwidth. These resources need to be carefully managed in a coordinated way to maximize performance. DRAM is still the technology of choice in most systems. However, as traditional DRAM technology faces energy, reliability, and scalability challenges, nonvolatile memory (NVM) technologies are gaining traction. While DRAM is read/write symmetric (a read operation has comparable latency and energy consumption as a write operation), many NVM technologies (such as Phase-Change Memory, PCM) experience read/write asymmetry: write operations are typically much slower and more power hungry than read operations. Whether the memory’s characteristics are symmetric or asymmetric influences the way shared resources are managed. We propose two symmetry-agnostic schemes to manage a shared LLC through way partitioning and memory through bandwidth allocation. The proposals work well for both symmetric and asymmetric memory. First, an exhaustive search is proposed to find the best combination of a cache way partition and bandwidth allocation. Second, an approximate scheme, derived from a theoretical model, is proposed without the overhead of exhaustive search. Simulation results show that the approximate scheme improves weighted speedup by at least 14% on average (regardless of the memory symmetry) over a state-of-the-art way partitioning and memory bandwidth allocation. Simulation results also show that the approximate scheme achieves comparable weighted speedup as a state-of-the-art multiple resource management scheme, XChange, for symmetric memory, and outperforms it by an average of 10% for asymmetric memory.

For memory-intensiv e workloads with large memory footprints, superpages are effective to avoid address translation overhead, which can be a critical performance bottleneck. A superpage is a large virtual memory page that is mapped to an equivalently-sized amount of contiguous physical memory pages. Superpage mapping assumes physical memory does not contain retired pages, which is an important technique to improve memory resilience: the OS avoids allocating physical pages that have detected errors. Retired pages create unusable "holes" in the physical memory. We show that even a small percentage of retired pages makes it very difficult to find enough contiguous memory to form superpages. To address this problem, we propose GTSM, or gap-tolerant sequential mapping, that allows superpages to be formed even in the presence of retired physical pages. A new page table format is also proposed to support GTSM. This format has similar storage efficiency as traditional superpaging to hold address translations in the last-level cache. To further compress the page table and improve cache hit rates for address translation in large memory footprint workloads, we also propose an extended format that reduces the page table size by 50%. In comparison to an ideal memory without any retired physical pages, we show that our technique, with retired pages, achieves nearly 96.8% of the performance of traditional 2MB superpaging.

Heterogeneous multicore architectures have the potential to improve energy efficiency by integrating power-efficient wimpy cores with high-performing brawny cores. However, it is an open question as how to deliver energy reduction while ensuring the quality of service (QoS) of latency-sensitive web-services running on such heterogeneous multicores in warehouse-scale computers (WSCs). In this work, we first investigate the implications of heterogeneous multicores in WSCs and show that directly adopting heterogeneous multicores without re-designing the software stack to provide QoS management leads to significant QoS violations. We then present Octopus-Man, a novel QoS-aware task management solution that dynamically maps latency-sensitive tasks to the least power-hungry processing resources that are sufficient to meet the QoS requirements. Using carefully-designed feedback-control mechanisms, Octopus-Man addresses critical challenges that emerge due to uncertainties in workload fluctuations and adaptation dynamics in a real system. Our evaluation using web-search and memcached running on a real-system Intel heterogeneous prototype demonstrates that Octopus-Man improves energy efficiency by up to 41% (CPU power) and up to 15% (system power) over an all-brawny WSC design while adhering to specified QoS targets.

The size of main memory in modern computers is approaching energy and scalability limits. Combining DRAM and non-volatile memory (NVM) has been proposed to increase capacity and reliability, and to decrease energy consumption. Software-managed hybrid memory is a promising way to incorporate NVM in main memory due to its architectural simplicity. However, there are significant performance issues caused by interference due to data migration between DRAM and NVM and a lack of effective migration policies. To aid in the development of migration policies and hardware mechanisms for incorporating NVM in main memory, we propose new analysis and simulation techniques to understand the behavior of software-managed hybrid memory. These techniques allow us to characterize the overhead experienced by requests in the memory hierarchy and identify the factors that limit performance in software-managed hybrid memory. Using our techniques, we show that queuing delays at the NVM banks and NVM bus are the main limiting factors, and that there is significant potential to improve performance with better migration policies.

The Social Internet of Things is a new paradigm that merges the Internet of Things with Social Networks. We propose a paradigm for how to model interactions between devices and humans, and among devices themselves to support sharable value-added applications throughout the device life cycle (e.g., Configuration, operation, preventive diagnosis), as well as to achieve common goals and recommendations. To realize this paradigm we propose a novel architecture and implementation to enable new Internet of Things applications based on emerging types of social relationships. We develop the semantic models for the Social Internet of Things including device types and their capabilities, users and their relationships, and rules leveraging such models. We demonstrate our concept by building a real system called Socialite that integrates various devices from different manufacturers with different functional interfaces and explicitly represents the relationships among active participants (devices as well as users) in our system.

The current trend to move from homogeneous to heterogeneous multicore systems provides compelling opportunities for achieving performance and energy efficiency goals. Running multiple threads in multicore systems poses challenges on meeting limited shared resources, such as memory bandwidth. We propose an optimization approach that includes an Integer Linear Programming (ILP) optimization model and a scheme to dynamically determine thread-to-core assignment. We present simulation analysis that shows energy savings and performance gains for a variety of workloads compared to state-of-the-art schemes. We implemented and evaluated a prototype of our thread assignment approach at user level, leveraging Linux scheduling and performance-monitoring capabilities.

Software Transactional Memory (STM) is a synchronization method proposed as an alternative to lockbased synchronization. It provides a higher-level abstraction that is easier to program, and that enables software composition. Transactions are defined by programmers, but the runtime system is responsible for detecting conflicts and avoiding race conditions. Phase Change Memory (PCM) is a new technology that is being developed to replace Dynamic Random Access Memories (DRAMs) in large datacenters. PCM write operations are much more expensive than reads in both energy and time. In this paper, we analyze performance, energy consumption, and write patterns in software transactional memories (STMs) to determine the potential of optimization for PCM scenarios. As the write operations are more expensive both in time and energy in PCMs, benchmarks from the STAMP suite were instrumented to count bits swapped due to store instructions, and experiments were executed using TinySTM. Our results showed a pattern of few bits being flipped for each memory write, and performance was inversely proportional to the number of writes. For most benchmarks, there was a small increase in energy consumption with more threads, which may be explained by the timid contention manager used by TinySTM.

Phase-Change Memory (PCM) has emerged as a promising low-power candidate to replace DRAM in main memory. Hybrid memory architecture comprised of a large PCM and a small DRAM is a popular solution to mitigate undesirable characteristics of PCM writes. Because PCM writes are much slower than reads, writebacks from the last-level cache consume a large portion of memory bandwidth, and thus, impact performance. Effectively utilizing shared resources, such as the last-level cache and the memory bandwidth, is crucial to achieving high performance for multi-core systems. Although existing memory bandwidth allocation schemes improve system performance, no current approach uses writeback information to partition bandwidth for hybrid memory. We use a writeback-aware analytic model to derive the allocation strategy for bandwidth partitioning of phase-change memory. From the derivation of the model, Writeback-aware Bandwidth Partitioning (WBP) is proposed as a new runtime mechanism to partition PCM service cycles among applications. WBP uses a partitioning weight to indicate the importance of writebacks (in addition to LLC misses) to bandwidth allocation. A companion Dynamic Weight Adjustment (DWA) scheme dynamically selects the partitioning weight to maximize system performance. Simulation results show that WBP and DWA improve performance by 24.9% (weighted speedup) over bandwidth partitioning schemes that do not take writebacks into consideration in a 8-core system.

Given the wide variety of performance demands for various workloads, the trend in embedded systems is shifting from homogeneous to heterogeneous processors, which have been shown to yield performance and energy saving benefits. A typical heterogeneous processor has cores with different performance and power characteristics, that is, high performance and power hungry (“big”) cores, and low power and performance (“small”) cores. In order to satisfy the memory bandwidth and computation demands of various threads, it is important (albeit challenging) to map threads to cores. Such assignment should take into account that threads could potentially be harmful to each other in the usage of shared resources (e.g., cache, memory). We propose a scheme for dynamic energy-efficient assignment of threads to big/small cores, DIO-E (Distributed Intensity Online-Energy), which is an enhancement of the previously proposed DIO. In contrast to DIO, we take into account both CPU and memory demands of threads to characterize the performance of threads when co-running on the same core at run-time. Our results show that DIO-E improves the energy-delay-squared product (ED2) by 9% (average) over DIO, running on a performance-asymmetric multicore system. Both DIO and DIO-E show about 50% improvement in ED2over a state-of-the-art solution.

Write bandwidth is an inherent performance bottleneck for Phase Change Memory (PCM) for two reasons. First, PCM cells have long programming time, and second, only a limited number of PCM cells can be programmed concurrently due to programming current and write circuit constraints,

Given that power is one of the biggest concerns of embedded systems, many devices have replaced DRAM with non-volatile Phase Change Memories (PCM). Some applications need to adhere to strict timing constraints and thus their temporal behavior must be analyzed before deploying them. Moreover, modern systems typically contain multiple cores, causing an application to incur significant delays due to the contention for the shared bus and shared main memory (PCM in this work). One of the challenges in the timing analysis for PCM main memories is the high discrepancy between read and write latencies and the high contention among cores. Finding an upper bound on these delays is non-trivial mainly because (i) memory requests may be issued by co-executing applications at random times, (ii) it is difficult to determine apriori which applications will be concurrently executing, and (iii) the type of requests applications will issue. This work proposes a method to derive upper bounds on the increase in execution time of applications executing on such PCM-based multicores. It considers the contention on the shared memory and focuses on dealing with the asymmetric read and write latencies of PCM-based memories, while taking into account the specific policy applied to schedule requests by the memory controller.

The Elastic Mixed-Criticality (E-MC) task model and an Early-Release EDF (ER-EDF) scheduling algorithm have been studied to address the service interruption problem for low-criticality tasks in uniprocessor systems. In this paper, focusing on multicore systems, we first investigate the schedulability of E-MC tasks under partitioned-EDF (P-EDF) by considering various task-to-core mapping heuristics. Then, with and without task migrations being considered, we study both global and local early-release schemes. Compared to the state-of-the-art Global EDF-VD scheduler, the superior performance of the proposed schemes in terms of improving the service levels of low-criticality tasks is confirmed through extensive simulations.

Limited PCM write bandwidth is a critical obstacle to achieve good performance from hybrid DRAM/PCM memory systems. The write bandwidth is severely restricted in PCM devices, which harms application performance. Indeed, as we show, it is more important to reduce PCM write traffic than to reduce PCM read latency for application performance. To reduce the number of PCM writes, we propose a DRAM cache organization that employs compression. A new delta compression technique for modified data is used to achieve a large compression ratio. Our approach can selectively and predictively apply compression to improve its efficiency and performance. Our approach is designed to facilitate adoption in existing main memory compression frameworks. We describe an instance of how to incorporate delta compression in IBM's MXT memory compression architecture when used for DRAM cache in a hybrid main memory. For fourteen representative memory-intensive workloads, on average, our delta compression technique reduces the number of PCM writes by 54.3%, and improves IPC performance by 24.4%.

In Collaborative WSNs, sensing devices are owned and operated by different stakeholders with incentive to preserve the confidentiality of their individual sensors readings while contributing to statistics computed by the group. In this paper, we present and analyze a new protocol that allows for con

Many promising congestion control protocols use explicit feedback from the network to achieve high performance. These protocols often use congestion signals whose computation requires an estimate of link capacity. Such estimates are not available in networks where capacity varies over time. This paper studies the impact of inaccurate capacity estimates on the performance of congestion control protocols over variable capacity links. As a case study, we focus on 802.11 WLANs. We show that such estimates can lead to either under-utilization or unfairness and network overload. Using a model, we characterize the available capacity of a node in a 802.11 WLAN and then study a method for capacity estimation. Using simulations, we show that the method leads to high utilization and fairness over shared, multi-access networks.

The recent trend of ubiquitous access to embedded physical devices over the Internet as well as increasing penetration of wireless protocols such as ZigBee has raised attention to smart homes. These systems consist of sensors, devices and smart appliances that can be monitored and controlled remotely by human users and cloud services. However, the lack of a de facto communication standard for smart homes creates a barrier against the interoperability of devices from different vendors. We address this challenge by proposing a holistic, extensible software architecture that seamlessly integrates heterogeneous protocol- and vendor-specific devices and services, while making these services securely available over the Internet. Our architecture is developed on top of the OSGi framework and incorporates a semantic model of a smart home system. As a result, we achieve semantic interoperability - the ability to integrate new applications and drivers into the deployed system during runtime. Furthermore, we integrate a new access control model for specific smart home scenarios. As a proof of our concept, we demonstrate the seamless semantic discovery of home devices at runtime by integrating several protocols including X10, Insteon, ZigBee and UPnP into a real test. Using smart phones and cloud services together with our home gateway implementation, we further demonstrate the ease of integration of new applications and drivers.

The current trend to move from homogeneous to heterogeneous multi-core systems promises further performance and energy-efficiency benefits. A typical future heterogeneous multi-core system includes two distinct types of cores, such as high performance sophisticated ("large'') cores and simple low-power ("small'') cores. In those heterogeneous platforms, execution phases of application threads that are CPU-intensive can take best advantage of large cores, whereas I/O or memory intensive execution phases are best suited and assigned to small cores. However, it is crucial that the assignment of threads to cores satisfy both the computational and memory bandwidth constraints of the threads. We propose an optimization approach to determine and apply the most energy efficient assignment of threads with soft real-time performance and memory bandwidth constraints in a multi-core system. Our approach includes an ILP (Integer Linear Programming) optimization model and a scheme to dynamically change thread-to-core assignment, since thread execution phases may change over time. In comparison to state-of-art dynamic thread assignment schemes, we show energy savings and performance gains for a variety of workloads, while respecting thread performance and memory bandwidth requirements.

Phase-Change Memory (PCM) has emerged as a promising low-power main memory candidate to replace DRAM. The main problems of PCM are that writes are much slower and more power hungry than reads, write bandwidth is much lower than read bandwidth, and limited write endurance. Adding an extra layer of cache, which is logically the last-level cache (LLC), can mitigate the drawbacks of PCM. However, writebacks from the LLC might (a) overwhelm the limited PCM write bandwidth and stall the application, (b) shorten lifetime, and (c) increase energy consumption. Cache partitioning and replacement schemes are important to achieve high throughput for multi-core systems. However, we noted that no existing partitioning and replacement policy takes into account the writeback information. This paper proposes two writeback-aware schemes to manage the LLC for PCM main memory systems. Writeback-aware Cache Partitioning (WCP) is a runtime mechanism that partitions a shared LLC among multiple applications. Unlike past partitioning schemes, our scheme considers the reduction in cache misses as well as writebacks. Write Queue Balancing (WQB) replacement policy manages the cache partition of each application intelligently so that the writebacks are distributed evenly among PCM write queues. In this way, applications rarely stall due to unbalanced PCM write traffic among write queues. Our evaluation shows that WCP and WQB result in, on average, 21% improvement in throughput, 49% reduction in PCM writes, and 14% reduction in energy over a state-of-the-art cache partitioning scheme.

This paper proposes and evaluates an approach for power and performance management in virtualized server clusters. The major goal of our approach is to reduce power consumption in the cluster while meeting performance requirements. The contributions of this paper are: (1) a simple but effective way of modeling power consumption and capacity of servers even under heterogeneous and changing workloads, and (2) an optimization strategy based on a mixed integer programming model for achieving improvements on power-efficiency while providing performance guarantees in the virtualized cluster. In the optimization model, we address application workload balancing and the often ignored switching costs due to frequent and undesirable turning servers on/off and VM relocations. We show the effectiveness of the approach applied to a server cluster test bed. Our experiments show that our approach conserves about 50% of the energy required by a system designed for peak workload scenario, with little impact on the applications' performance goals. Also, by using prediction in our optimization strategy, further QoS improvement was achieved.

In trust negotiation approaches to authorization, previously unacquainted entities establish trust in one another gradually via the bilateral and iterative exchange of policies and digital credentials. Although this affords resource providers with an expressive means of access control for open systems, the trust negotiation process incurs non-trivial computational and communications costs. In this paper, we propose Receipt-Mode Trust Negotiation (RMTN) as a means of mitigating the performance penalties on servers that use trust negotiation. RMTN provides a means of off-loading the majority of the trust negotiation process to delegated receipt-generating helper servers. RMTN ensures that helpers produce correct trust negotiation protocol receipts, and that the helpers are incapable of impersonating the resource server outside of the RMTN protocol. We describe an initial implementation of our RMTN protocol on a Linux testbed, discuss the security of this protocol, and present experimental results indicating that the receipt-mode protocol does indeed enhance the performance of resource servers that rely on trust negotiation approaches to authorization.

Non-volatile memories, such as Flash and Phase-Change Memory, are replacing other memory and storage technologies. Although these new technologies have desirable energy and scalability properties, they are prone to wear-out due to excessive write operations. Because wear-out is an important phenomenon, a number of endurance management schemes have been proposed. There is a trade-off between what techniques to use, depending on the range of bit cell lifetime within a device. This range in cell durability arises from effects due to process variation. In this paper, we describe modeling techniques to analyze trade-offs for endurance management based on the anticipated distribution of cell lifetime. This analysis considers two general endurance strategies (physical capacity degradation and physical sparing) under four distributions of cell lifetime (constant, linear, normal, and bimodal). The modeling techniques can be used to determine how much redundancy is needed when a sparing endurance strategy is adopted. With the correct choice of technique, the device lifetime can be doubled.

Phase Change Memory (PCM) is an emerging technology that has been recently considered as a cost-effective and energy-efficient alternative to traditional DRAM main memory. Due to the high energy consumption of writes and limited number of write cycles, reducing the number of writes to PCM can result in considerable energy savings and endurance improvement. In this paper, we introduce the concept of useless write-backs, which occur when a dirty cache line that belongs to a dead memory region is evicted from the cache (a dead region is a memory location that is not used again by a program). Since the evicted data is not used again, the write-back can be safely avoided to improve endurance and energy consumption. This paper presents a limit study on the improvement that passing information to the memory system about useless writebacks has on the endurance and energy consumption of systems based on PCM main memory. We developed algorithms to measure the number of useless write-backs to PCM for three different types of memory regions and we present an energy model to determine the maximum energy savings that could potentially be achieved through such a scheme. Our results show that avoiding useless write-backs can save up to 19.8% of energy and improve endurance by up to 26.2%.

Time Division Multiple Access (TDMA) communication protocols in wireless sensor networks provide collision-free communication that increases energy-efficiency while maintaining deterministic packet latencies. The TDMA-ASAP[1] protocol proposed stealing neighbor's slots when networks are running at low-duty cycles to reduce the potentially large latencies of the TDMA cycle size. In this paper, we further reduce the end-to-end latencies by intelligently spreading slots across the TDMA cycle and by enhancing the stealing opportunities in the schedule, stealing slots scheduled for downstream (control) and upstream (data) messages. We also provide a practical time synchronization algorithm that operates within the TDMA schedule. In order to evaluate our new schemes, we carried out both simulation studies to show scalability and a test bed implementation of Fire Fly wireless sensor nodes to show feasibility. Our schemes provide higher peak throughput (nearly 2x) as compared to a common low-power-listen contention-based (LPL-CSMA) protocol and improves the average packet latency by as much as 5x as compared to existing TDMA protocols without slot-stealing and up to 2x as compared to TDMA-ASAP.

Multi-core processors are effective for reducing energy consumption in computer systems, since modern multi- core chips allow for power management of individual cores. However, multiple cores impose higher demand on the memory subsystem, which is extremely power hungry. In addition to the small steps towards managing power in DRAMs, Phase-Change Memory (PCM) has emerged as a low-power alternative that is especially helpful for energy-aware embedded real-time systems. However, there are three drawbacks to PCM: its high latency, high energy consumption when writing, and low endurance. In real-time systems, the impact of PCM's high access latency is of special interest, as it has a negative effect on the number of deadlines that are met by the system. In this paper, we examine the memory subsystem and add a real-time scheduler for prioritizing requests at the bottleneck resource, the PCM controller. Adding support for external priorities, we use rate monotonic (RM) and earliest deadline first (EDF) prioritization at the PCM and show that it does reduce the number of deadline misses, but not sufficiently. We examine two additional schemes for prioritizing PCM requests (critical read boosting and read over write). We show that the scheduler of the PCM controller has a significant influence on the percentage of missed deadlines: critical read boosting and read over write can reduce the percentage of missed deadlines by 80% in the best case with negligible energy overhead.

In this paper, we report on our experience with the application of validated models to assess performance, reliability, and adaptability of a complex mission critical system that is being developed to dynamically monitor and control the position of an oil-drilling platform. We present real-time modeling results that show that all tasks are schedulable. We performed stochastic analysis of the distribution of tasks execution time as a function of the number of system interfaces. We report on the variability of task execution times for the expected system configurations. In addition, we have executed a system library for an important task inside the performance model simulator. We report on the measured algorithm convergence as a function of the number of vessel thrusters. We have also studied the system architecture adaptability by comparing the documented system architecture and the implemented source code. We report on the adaptability findings and the recommendations we were able to provide to the system's architect. Finally, we have developed models of hardware and software reliability. We report on hardware reliability results based on the evaluation of the system architecture. As a topic for future work, we report on an approach that we recommend be applied to evaluate the system under study software reliability.

poster Share on Privacy and robustness for data aggregation in wireless sensor networks Authors: Marian Kamal Iskander University of Pittsburgh, Pittsburgh, PA, USA University of Pittsburgh, Pittsburgh, PA, USAView Profile , Adam J. Lee University of Pittsburgh, Pittsburgh, PA, USA University of Pittsburgh, Pittsburgh, PA, USAView Profile , Daniel Moss é University of Pittsburgh, Pittsburgh, PA, USA University of Pittsburgh, Pittsburgh, PA, USAView Profile Authors Info & Claims CCS '10: Proceedings of the 17th ACM conference on Computer and communications securityOctober 2010Pages 699–701https://doi.org/10.1145/1866307.1866402Published:04 October 2010Publication History 1citation472DownloadsMetricsTotal Citations1Total Downloads472Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The introduction of Phase-Change Memory (PCM) as a main memory technology has great potential to achieve a large energy reduction. PCM has desirable energy and scalability properties, but its use for main memory also poses challenges such as limited write endurance with at most 107writes per bit cell before failure. This paper describes techniques to enhance the lifetime of PCM when used for main memory. Our techniques are (a) writeback minimization with new cache replacement policies, (b) avoidance of unnecessary writes, which write only the bit cells that are actually changed, and (c) endurance management with a novel PCM-aware swap algorithm for wear-leveling. A failure detection algorithm is also incorporated to improve the reliability of PCM. With these approaches, the lifetime of a PCM main memory is increased from just a few days to over 8 years.

We present in this paper our experience with applying a new architecture review process that uses a globally distributed review team to assess architecture risk of a complex mission critical system. The new architecture review process uses aspects of the checklist-based architecture review process and the operational scenario-based architecture review process. We present the architecture review process approach, a summary of the architecture under review and the detailed analysis of the most important operational scenarios. We conclude by presenting a summary of the lessons we learned using the new process.

Dynamic RAM (DRAM) has been the best technology for main memory for over thirty years. In embedded space applications, radiation hardened DRAM is needed because gamma rays cause transient errors; such rad-hard memories are extremely expensive and power hungry, leading to lower life (or increased battery weight) for satellite and other devices operating in space. Despite these problems, DRAM has been the technology of choice because it has better performance and it scales well. New, more energy efficient, non-volatile, scalable, radiation resistant memory technologies are now available, namely phase-change memory (PCM), making the DRAM choice much less compelling. However, current approaches require changes to PCM device internal circuitry, the operating system and/or the CPU cache-memory organization/interface. This paper presents a new, practical, detailed architecture, called PMMA, to effectively use PCM for main memory in next-generation embedded space systems. We designed PMMA avoiding changes to commodity PCM devices, the operating system, and the existing CPU cache-memory interface, enabling plug-in replacement of a conventional DRAM main memory by one constructed with PMMA. Our architecture incorporates novel mechanisms to address PCM’s limitations including expensive write operations, asymmetric read/write latency, and limited endurance. In our evaluation we show that PMMA achieves a 60% improvement in energy-delay over a conventional DRAM main memory.

Performing QoS (Quality of Service) control in large computing systems requires an on line metric that is representative of the real state of the system. The Tardiness Quantile Metric (TQM) introduced earlier allows control of QoS by measuring efficiently how close to the specified QoS the system is, assuming specific distributions. In this paper we generalize this idea and propose the Generalized Tardiness Quantile Metric (GTQM). By using an online convergent sequential process, defined from a Markov chain, we derive quantile estimations that do not depend on the shape of the workload probability distribution. We then use GTQM to keep QoS controlled in a fine grain manner, saving energy in soft real-time web clusters. To evaluate the new metric, we show practical results in a real web cluster running Linux, Apache, and MySQL, with our QoS control and for both a deterministic workload and an e-commerce workload. The results show that the GTQM method has excellent workload prediction capabilities, which immediately translates in more accurate QoS control, allowing for slower speeds and larger energy savings than the state-of-the-art in soft real-time web cluster systems.

The goal of Wireless Sensor Networks is to extract useful global information from individual sensor readings, which are typically collected and aggregated over a spanning tree. However, the spanning tree structure is not robust against communication errors; a low-quality (i.e., high-error-rate) wireless link close to the tree root may result in a high rate of global information loss. Therefore, many schemes have been proposed to achieve fault-tolerant aggregation. Intuitively, using timely link-quality information, which is gathered by continuous monitoring and error-rate measurement of network links, improves the performance of fault-tolerant aggregation schemes. In this paper, we show that this intuition is not always true. In particular, we show that using link-quality information in an intuitive but wrong way results in degraded performance in some schemes, and therefore, care should be taken in using link-quality information. We also show that some schemes make better usage of link-quality information than others, and some schemes are more robust to errors in link-quality estimation than others. We support our findings by an extensive simulation study, and we focus on the (more general) class of fault-tolerant duplicate-sensitive aggregation schemes.

TDMA has been proposed as a MAC protocol for wireless sensor networks (WSNs) due to its efficiency in high WSN load. However, TDMA is plagued with shortcomings; we present modifications to TDMA that will allow for the same efficiency of TDMA, while allowing the network to conserve energy during times of low load (when there is no activity being detected). Recognizing that aggregation plays an essential role in WSNs, TDMA-ASAP adds to TDMA: (a) transmission parallelism based on a level-by-level localized graph-coloring, (b) appropriate sleeping between transmissions ("napping"), (c) judicious and controlled TDMA slot stealing to avoid empty slots to be unused and (d) intelligent scheduling/ordering transmissions. Our results show that TDMA-ASAP's unique combination of TDMA, slot-stealing, napping, and message aggregation significantly outperforms other hybrid WSN MAC algorithms and has a performance that is close to optimal in terms of energy consumption and overall delay.

Denial-of-service (DoS) attacks remain a challenging problem in the Internet. By making resources unavailable to intended legitimate clients, DoS attacks have resulted in significant loss of time and money for many organizations, thus, many DoS defense mechanisms have been proposed. In this paper we propose live baiting, a novel approach for detecting the identities of DoS attackers. Live baiting leverages group-testing theory, which aims at discovering defective members in a population using the minimum number of dasiadasiatestspsilapsila. This leverage allows live baiting to detect attackers using low state overhead without requiring models of legitimate requests nor anomalous behavior. The amount of state needed by live baiting is in the order of number of attackers not number of clients. This saving allows live baiting to scale to large services with millions of clients. We analyzed the coverage, effectiveness (detection time, false positive and false negative probabilities), and efficiency (memory, message overhead, and computational complexity) of our approach. We validated our analysis using NS-2 simulations modeled after real Web traces.

In wireless sensor networks (WSN) node failures are typically detected using a heartbeat application, where a neighbor detects a failed node when it misses successive short messages (ldquoheartbeatsrdquo) that should have been sent by the failed node. However, wireless links are usually lossy, hence, to distinguish node failures from intermittent link failures, the threshold on the number of missed heartbeats is usually set to a large number, incurring in a long delay for declaring a node dead. In this paper we present ldquoGroupBeatrdquo an accurate node failure detection system for WSN and propose the ldquoCommunication By Signalingrdquo scheme as an energy-efficient low-overhead implementation of GroupBeat.

Multi-radio (multi-interface, multi-channel) 802.11 and sensor networks have been proposed to increase network capacity and to reduce energy consumption, to name only a few of their applications. They are vulnerable, however, to jamming attacks, in which attackers block communication by radio int

Jamming is a serious security problem in wireless networks. Recently, software-based channel hopping has received attention as a jamming countermeasure. In particular, proactive, or periodic, channel hopping has been studied more extensively than reactive hopping. In this paper, we address the question of which of the two defense strategies, namely proactive and reactive channel-hopping, provides better jamming resiliency than the other? in the context of single-and multi-radio wireless devices. In the single-radio context, we develop theoretical models to analyze the blocking probability for combinations of defense and attack strategies. In the multi-radio setting, we formulate the jamming problem as a max-min game and show through simulation that the game outcome depends on the payoff function. Our results show that reactive defense provides better jamming tolerance than proactive when considering communication availability. However, both reactive and proactive defenses have almost the same performance when energy efficiency is considered as a performance metric.

Operating system extensions have been shown to be beneficial to implement custom kernel functionality. In most implementations, the extensions are made by an administrator with kernel loadable modules. An alternative approach is to provide a run-time system within the operating system itself that can execute user kernel extensions. In this paper, we describe such an approach,where a lightweight Java virtual machine is embedded within the kernel for flexible extension of kernel network I/O. For this purpose, we first implemented a compact Java Virtual Machine with a Just-In-Time compiler on the Intel IA32 instruction set architecture at the user space. Then, the virtual machine was embedded onto the FreeBSDoperating system kernel. We evaluate the system to validate the model, with systematic benchmarking.

In this paper we study the soft real-time web cluster architecture needed to support e-commerce and related applications. Our testbed is based on an industry standard, which defines a set of Web interactions and database transactions with their deadlines, for generating real workload and bench-marking e-commerce applications. In these soft real-time systems, the quality of service (QoS) is usually defined as the fraction of requests that meet the deadlines. When this QoS is measured directly, regardless of whether the request missed the deadline by an epsilon amount of time or by a large difference, the result is always the same. For this reason, only counting the number of missed requests in a period avoids the observation of the real state of the system. Our contributions are theoretical propositions of how to control the QoS, not measuring the QoS directly, but based on the probability distribution of the tardiness in the completion time of the requests. We call this new QoS metric tardiness quantile metric (TQM). The proposed method provides fine-grained control over the QoS so that we can make a closer examination of the relation between QoS and energy efficiency. We validate the theoretical results showing experiments in a multi-tiered e-commerce web cluster implemented using only open-source software solutions.

Today's CPUs consume a significant amount of power and generate a high amount of heat, requiring an active cooling system to support reliable operations. In case of cooling system failures, these CPUs can reduce clock speed to prevent damage due to overheating. Unfortunately, when these CPUs are used in a real-time system, a clock control based on frequency-throttling can cause missed deadlines. In this paper, we first develop and validate a system-wide thermal model that can account for various thermal fault types such as failure of a CPU fan, faults in the case fan and air-conditioning malfunctions. Then we validate the thermal model through experimentation and measurements in AMD Linux boxes. Our soft real-time power-aware load-distribution algorithm for data centers incorporates a thermal model to minimize the number of missed deadlines that can be caused by thermal faults. We implemented the algorithm in a webserver farm simulator to test the efficacy of thermal-aware load-balancing. Our results show that the new algorithm helps keep CPU temperatures within the desired thermal envelope, even in the presence of thermal faults. When thermal faults occur, our algorithm improves the QoS, at the expense of higher energy consumption.

This paper deals with energy-aware real-time system scheduling using dynamic voltage scaling (DVS) for energy-constrained embedded systems that execute variable and unpredictable workloads. The goal is to design DVS schemes to minimize the expected energy consumption of the whole system while meeting the deadlines of the tasks. Researchers have attempted to take advantage of stochastic information about workloads to achieve better energy savings, and accordingly, various stochastic DVS schemes have been proposed. However, the existing stochastic DVS schemes are based on much simplified power models that assume unrestricted continuous frequency, well-defined power/frequency relation, and no speed change overhead. When these schemes are used in practice, they need to be patched in order to comply with realistic power models. Experiments show that some of such DVS schemes perform even worse than certain non-stochastic DVS schemes. Furthermore, even for stochastic schemes that were shown experimentally to outperform non-stochastic schemes, it is not clear how well they perform compared to the optimal solution, which is yet to be found. In this work, we provide a unified practical approach for obtaining optimal (or provably close to optimal) stochastic inter-task, intra-task, and hybrid DVS schemes under realistic power models in which the processor only provides a set of discrete speeds, no assumption is made on power/frequency relation, and speed change overhead is considered. We also evaluate the existing DVS schemes by comparing them with our DVS schemes.

Wireless sensor networks represent an extremely fast-growing emerging technology, but still suffer from several limitations. The state of the art in sensor networks focuses on optimizing the existing protocols to address the two main challenges affecting the sensors: failures and energy consumption. Our contributions in this paper include: analyzing most relevant protocols that attempt to address these two problems, presenting methods to achieve local reconstruction for a sensor network that uses multi-path routing and proposing a new protocol, called LSynD, an extension of the Tributaries and Deltas approach. LSynD achieves a faster, more localized and energy efficient reconstruction than its predecessor protocols by creating multiple adaptive multi-path routing regions

Embedded systems serve an emerging and diverse set of applications. As a result, more computational and storage capabilities are added to accommodate ever more demanding applications. Unfortunately, adding more resources typically comes on the expense of higher energy costs. New chip design with Multiple Clock Domains (MCD) opens the opportunity for fine-grain power management within theprocessor chip. When used with dynamic voltage scaling (DVS), we can control the voltage and power of each domain independently. A significant power and energy improvement has been shown when using MCD design in comparison to managing a single voltage domain for the whole chip, as in traditional chips with global DVS.

Streaming applications have become increasingly important and widespread, and they will be running on soon- to-be-prevalent chip multiprocessors (CMPs). We address the problem of energy-aware scheduling of streaming applications, which are represented by task graphs, on a CMP using on/off and dynamic voltage scaling (DVS) on a per-processor basis. The goal is to minimize the energy consumption of streaming applications while satisfying two typical quality-of-service (QoS) requirements, namely, throughput and response time. To the best of our knowledge, this paper is the first work to tackle this problem. We make a key observation: the trade-off between static power and dynamic power should play a critical role in both parallel processing and pipelining that are used to reduce energy consumption in the scheduling process. Based on this observation, we propose two scheduling algorithms, Scheduling 1D and Scheduling 2D, for linear and general task graphs, respectively. The proposed algorithms exploit the difference between the two QoS requirements and perform processor allocation, task mapping and task speed scheduling simultaneously. Experimental results show that the proposed algorithms can achieve significant energy savings (e.g., 24% on average for 70 nm technology) over the baseline that only considers the response time requirement.

Main memory has become one of the largest contributors to overall energy consumption and offers many opportunities for power/energy reduction. In this paper, we propose a Power-Aware Cached-DRAM (PA-CDRAM) organization that integrates a moderately sized cache directly into a memory chip. We use this near-memory cache to turn a memory bank off immediately after it is accessed to reduce power consumption.We modify the operation and structure of cached DRAM (CDRAM) with the goal of reducing energy consumption while retaining the performance advantage for which CDRAM was originally proposed. In this paper, we describe our PA-CDRAM organization and show how to incorporate it into Rambus memory. We evaluate the approach using a cycle accurate processor and memory simulator. Our results show that PA-CDRAM achieves up to 84% (28% on average) improvement in the energy-delay product and up to 76% (19% on average) savings in energy when compared to a time-out power management technique.

Many real-time systems, such as battery-operated embedded devices, are energy constrained. A common problem for these systems is how to reduce energy consumption in the system as much as possible while still meeting the deadlines; a commonly used power management mechanism by these systems is dynamic voltage scaling (DVS). Usually, the workloads executed by these systems are variable and, more often than not, unpredictable. Because of the unpredictability of the workloads, one cannot guarantee to minimize the energy consumption in the system. However, if the variability of the workloads can be captured by the probability distribution of the computational requirement of each task in the system, it is possible to achieve the goal of minimizing the expected energy consumption in the system. In this paper, we investigate DVS schemes that aim at minimizing expected energy consumption for frame-based hard real-time systems. Our investigation considers various DVS strategies (i.e., intra-task DVS, inter-task DVS, and hybrid DVS) and both an ideal system model (i.e., assuming unrestricted continuous frequency, well-defined power-frequency relation, and no speed change overhead) and a realistic system model (i.e., the processor provides a set of discrete speeds, no assumption is made on power-frequency relation, and speed change overhead is considered). The highlights of the investigation are two practical DVS schemes: Practical PACE (PPACE) for a single task and Practical Inter-Task DVS (PITDVS2) for general frame-based systems. Evaluation results show that our proposed schemes outperform and achieve significant energy savings over existing schemes.

Natural or man-made disasters can partition networks while threatening human lives. Because conventional mobile ad-hoc networks (MANETs) cannot route messages across partitions, they may not adequately support relief efforts. To forward messages across partitions, delay-tolerant networks (DTNs) exploit in-network storage and mobility. Many previous DTN routing protocols either opportunistically use, but do not modify, nodes' mobility, or require dedicated mobile gateways. This paper contributes a cross-layer DTN routing approach based on the observation that application-layer orders from a MANET's leader also control workers' mobility and ability to forward messages. Our approach attempts to minimize deadline misses and energy consumption by scheduling worker tasks considering both application- and network-layer needs. Simulations demonstrate performance benefits of our approach in a variety of scenarios.

In wireless mobile adhoc networks (MANETs) channel and energy capacities are scarce resources, a lot of energy-efficient routing protocols for MANETs have been previously proposed to take into consideration the nodes’ residual energies when establishing routes between source-destination pairs. In this paper we are not trying to introduce a new routing algorithm to be added to the already proposed stack of energy-efficient protocols, but rather, we identify a problem in cost-based energy-efficient routing for MANETs, we call this problem "Flooding Waves". We show that the "Flooding Waves" is a serious problem in dense networks, to the extent that the excessive energy overhead consumed in these waves can outweigh the gain achieved by energy-efficient path selection. We propose the "Delayed-Forwarding" as a solution for this problem. We provide both a simulation analysis and a simple theoretical framework to validate and support this solution.

Web-database systems are nowadays an integral part of everybody’s life, with applications ranging from monitoring/ trading stock portfolios, to personalized blog aggregation and news services, to personalized weather tracking services. For most of these services to be successful (and their users to be kept satisfied), two criteria need to be met: user requests must be answered in a timely fashion and using fresh data. This paper presents a framework to balance both requirements from the users’ perspective. Toward this, we propose a user satisfaction metric to measure the overall effectiveness of the Web-database system. We also provide a set of algorithms to dynamically optimize this metric, through query admission control and update frequency modulation. Finally, we present extensive experimental results which compare our proposed algorithms to the current state of the art and show that we outperform competitors under various workloads (generated based on real traces) and user requirements.

By violating MAC-layer protocols, the jamming attack aims at blocking successful communication among wireless nodes. Wireless sensor networks (WSNs) are highly vulnerable to jamming because of reliance on shared wireless medium, constrained per-sensor resources, and high risk of sensor compromise. Moreover, base stations of WSNs are single points of failure and, thus, attractive jamming targets. To tackle base-station jamming, replication of base stations as well as jamming evasion, by relocation to unjammed locations, have been proposed. In this paper, we propose Honeybees, an energy-aware defense framework against base-station jamming attack in WSNs. Honeybees efficiently combines replication and evasion to allow WSNs to continue delivering data for a long time during a jamming attack. We present three defense strategies: reactive, proactive, and hybrid, in the context of multi-hop WSN deployment. Through simulation, we show the interaction of these strategies with different attack tactics as well as the effect of system and attack parameters. We found that our honeybees framework struck an energy-efficient balance between replication and evasion that outperformed both separate mechanisms. Specifically, hybrid honeybees outperformed replication and evasion at low and intermediate number of attackers and gracefully degraded to high attack intensity

The Denial-of-Service (DoS) attack remains a challenging problem in the current Internet. In a DoS defense mechanism, a honeypot acts as a decoy within a pool of servers, whereby any packet received by the honeypot is most likely an attack packet. We have previously proposed the roaming honeypots scheme to enhance this mechanism by camouflaging the honey-pots within the server pool, thereby making their locations highly unpredictable. In roaming honeypots, each server acts as a honeypot for some periods of time, or honeypot epochs, the duration of which is determined by a pseudo-random schedule shared among servers and legitimate clients. In this paper, we propose a honeypot back-propagation scheme to trace back attack sources when attacks occur. Based on this scheme, the reception of a packet by a roaming honeypot triggers the activation of a DAG of honeypot sessions rooted at the honeypot under attack towards attack sources. The formation of this tree is achieved in a hierarchical fashion: first at the autonomous system (AS) level and then at the router level within an AS if needed. The proposed scheme supports incremental deployment and provides deployment incentives for ISPs. Through ns-2 simulations, we show how the proposed scheme enhances the performance of a vanilla Pushback defense by obtaining accurate attack signatures and acting promptly once an attack is detected

Sensor networks opened new opportunities to monitor the environment. In order to retrieve the desired data, sensors are usually organized into a hierarchy and synchronize when transmitting the data towards the base station. Many scheduling schemes have been proposed with the goal of allowing sensors to sleep as much as possible and ultimately save energy. In this paper, we propose two new scheduling algorithms that assign predefined slots to each sensor. These algorithms are distributed, need very little global information and do not need knowledge about the location of sensors or the network topology. As others, we also assume that loose clock synchronization is available. The experimental results confirm our expectations. They show a significant reduction in the average time awake per node of at least three times compared to more traditional routing protocols like TAG

In wireless sensor networks (WSNs), the users' objective is to extract useful global information by collecting individual sensor readings. Conventionally, this is done using in-network aggregation on a spanning tree from sensors to data sink. However, the spanning tree structure is not robust against communication errors; when a packet is lost, so is a complete subtree of values. Multipath routing can mask some of these errors, but on the other hand, may aggregate individual sensor values multiple times. This may produce erroneous results when dealing with duplicate-sensitive aggregates, such as SUM, COUNT, and AVERAGE. In this paper, we present and analyze two new fault tolerant schemes for duplicate-sensitive aggregation in WSNs: (1) cascaded ridesharing and (2) diffused ridesharing. These schemes use the available path redundancy in the WSN to deliver a correct aggregate result to the data sink. Compared to state-of-the-art, our schemes deliver results with lower root mean square (RMS) error and consume much less energy and bandwidth. RideSharing can consume as much as 50% less resources than hash-based schemes, such as SKETCHES and synopsis diffusion, while achieving lower RMS for reasonable link error rates

Managing energy consumption has become vitally important to battery-operated portable and embedded systems. Dynamic voltage scaling (DVS) reduces the processor's dynamic power consumption quadratically at the expense of linearly decreasing the performance. When reducing energy with DVS for real-time systems, one must consider the performance penalty to ensure that deadlines can be met. In this paper, we introduce a novel collaborative approach between the compiler and the operating system (OS) to reduce energy consumption. We use the compiler to annotate an application's source code with path-dependent information called power-management hints (PMHs). This fine-grained information captures the temporal behavior of the application, which varies by executing different paths. During program execution, the OS periodically changes the processor's frequency and voltage based on the temporal information provided by the PMHs. These speed adaptation points are called power-management points (PMPs). We evaluate our scheme using three embedded applications: a video decoder, automatic target recognition, and a sub-band tuner. Our scheme shows an energy reduction of up to 57% over no power-management and up to 32% over a static power-management scheme. We compare our scheme to other schemes that solely utilize PMPs for power-management and show experimentally that our scheme achieves more energy savings. We also analyze the advantages and disadvantages of our approach relative to another compiler-directed scheme.

We study the problem of minimizing energy consumption in real-time embedded systems that execute variable workloads and are equipped with processors having dynamic voltage scaling (DVS) capabilities. This problem is about how to decide tasks' running speeds (speed schedule) before they are scheduled to execute. In this paper, we show that it is possible to incorporate the dynamic behavior of the tasks into the speed schedule to, along with the dynamic slack reclamation technique, minimize the expected (total) energy consumption in the system.

Output of network file servers exhibits bursty traffic patterns, and this sometimes contends with control traffic. An example is contention between data traffic and write acknowledgments on a loaded server. In such a situation, we can improve the write performance by prioritizing write acknowledgments at the network interface of the server. To validate this scheme, we conducted an empirical study of the prioritization of write acknowledgments. Systematic experiments revealed that the proposed scheme can improve write latency and throughput of loaded servers without influencing read performance. The results suggested that the technique is widely applicable to systems where transactions are a mixture of read and write requests, and especially if the degree of concurrency is high.

Flooding is commonly used in reactive ad hoc routing protocols. Although simple and effective, flooding may incur excessive overhead. In order to reduce unnecessary rebroadcasts, probabilistic gossiping schemes have been proposed. These schemes, however, do not usually adapt the probability of forwarding to time-varying features of the network. To address this shortcoming, four new heuristics to adapt forwarding probability to coverage area and/or topology information are proposed. We show through simulations that the proposed schemes can reduce the number of routing requests by up to 35% compared with existing schemes, while delivering approximately the same amount of data packets.

Main memory has become one of the largest contributors to overall energy consumption and offers many opportunities for power/energy reduction. In this paper, we propose a power-aware cached-DRAM (PA-CDRAM) organization that integrates a moderately sized cache directly into a memory module. We use this near-memory cache to turn a memory bank off immediately after it is accessed to reduce power consumption. We modify the structure of cached DRAM (CDRAM) with the goal of reducing energy consumption while retaining the performance advantage for which CDRAM was originally proposed. We evaluate the approach using a cycle accurate processor and memory simulator. Our results show that PACDRAM achieves up to 84% (28% on average) improvement in the energy-delay product and up to 76% (19% on average) savings in energy when compared to a time-out power management technique.

There have been increasing demands for proper monitoring and control in end-host systems, mainly for security and QoS purposes. Nevertheless, existing technologies are insufficient as primitives for end-host security. For example, Berkeley packet filter (BPF), the most popular monitoring infrastructure for many Unix systems, is intended for packet capturing at physical interfaces, and thus, not appropriate for monitoring of applications, which is sometimes critical for system security. This paper presents a simple solution to the problem, utilizing hierarchical virtual network interface (VIF) mechanism. VIF is a new OS abstraction that can be hierarchically structured and attached to OS entities to control their network I/O. We extend VIFs to allow filtering and monitoring of their traffic, and show that it has desirable properties for end-host monitoring and control of traffic. We present our prototype implementation on FreeBSD, and evaluate it qualitatively and quantitatively. Demonstrated advantages include: i) ability to monitor terminating entities at arbitrary granularity, ii) a single consistent framework for both network security and network quality of service, iii) OS independence, iv) efficiency as a control primitive, v) compatibility with BPF interface and its applications, and vi) flexibility for future functional expansion.

Software for resource constrained embedded devices is often implemented in the Java programming language because the Java compiler and virtual machine provide enhanced safety, portability, and the potential for run-time optimization. It is important to verify that a software application executes correctly in the environment in which it will normally execute, even if this environment is an embedded one that severely constrains memory resources. Testing can be used to isolate defects within and establish a confidence in the correctness of a Java application that executes in a resource constrained environment. However, executing test suites with a Java virtual machine (JVM) that uses dynamic compilation to create native code bodies can introduce significant testing time overheads if memory resources are highly constrained. This paper describes an approach that uses adaptive code unloading to ensure that it is feasible to perform testing in the actual memory constrained execution environment. The experiments demonstrate that code unloading can reduce both the test suite execution time by 34% and the code size of the test suite and application under test by 78% while maintaining the overall size of the JVM.

Abstract Power conservation has become a key design issue for many sys-tems, including clusters deployed for embedded systems, where

In wireless adhoc networks, channel and energy capacities are scarce resources. However, the design of the IEEE 802.11 DCF protocol leads to an inefficient utilization of these resources. We introduce BLAM, a new battery level aware MAC protocol, which is developed from an energy-efficiency point of view to extend the useful lifetime of an adhoc network. We modify the IEEE 802.11 DCF protocol to enable BLAM to tune the random deferring time for fresh and collided data packets dynamically, based on the node's energy. We show that BLAM can achieve an increase of 15% in network lifetime and an increase of about 35% in the total number of received packets.

In current embedded systems, one of the major concerns is energy conservation. The dynamic voltage-scheduling (DVS) framework, which involves dynamically adjusting the voltage and frequency of the CPU, has become a well studied technique. It has been shown that if a task's computational requirement is only known probabilistically, there is no constant optimal speed for the task and the expected energy consumption is minimized by gradually increasing speed as the task progresses citelorchsmith. It is possible to find the optimal speed schedule if we assume continuous speed and a well defined power function, which are assumptions that do not hold in practice. In this paper, we study the problem from a practical point of view, that is, we study the case of discrete speeds and make no restriction on the form of the power functions. Furthermore, we take into account processor idle power and speed change overhead, which were ignored in previous similar studies. We present a fully polynomial time approximation scheme (FPTAS), which has performance guarantees and usually obtains solutions very close to the optimal solution in practice. Our evaluation shows that our algorithm performs very well and generally obtains solutions within 0.1.

The slack time in real-time systems can be used by recovery schemes to increase system reliability as well as by frequency and voltage scaling techniques to save energy. Moreover, the rate of transient faults (i.e., soft errors caused, for example, by cosmic ray radiations) also depends on system operating frequency and supply voltage. Thus, there is an interesting trade-off between system reliability and energy consumption. This work first investigates the effects of frequency and voltage scaling on the fault rate and proposes two fault rate models based on previously published data. Then, the effects of energy management on reliability are studied. Our analysis results show that, energy management through frequency and voltage scaling could dramatically reduce system reliability, and ignoring the effects of energy management on the fault rate is too optimistic and may lead to unsatisfied system reliability.

Honeypots have been proposed to act as traps for malicious attackers. However, because of their deployment at fixed (thus detectable) locations and on machines other than the ones they are supposed to protect, honeypots can be avoided by sophisticated attacks. We propose roaming honeypots, a mechanism that allows the locations of honeypots to be unpredictable, continuously changing, and disguised within a server pool. A (continuously changing) subset of the servers is active and providing service, while the rest of the server pool is idle and acting as honeypots. We utilize our roaming honeypots scheme to mitigate the effects of service-level DoS attacks, in which many attack machines acquire service from a victim server at a high rate, against back-end servers of private services. The roaming honeypots scheme detects and filters attack traffic from outside a firewall (external attacks), and also mitigates attacks from behind a firewall (internal attacks) by dropping all connections when a server switches from acting as a honeypot into being active. Through ns-2 simulations, we show the effectiveness of our roaming honeypots scheme. In particular, against external attacks, our roaming honeypots scheme provides service response time that is independent of attack load for a fixed number of attack machines.

In this paper we address the issue of controlling transmission power in power-aware ad hoc networks. Previous work that minimizes the transmission power does not consider both the energy consumed in collision resolution and the energy disbursed to overcome the interference resulting from neighboring nodes. We investigate the basic transmission power control for the 802.11 MAC protocols in which the control frames and the data frames can be transmitted at different power levels. A collision model together with an interference model of a uniformly distributed network is constructed. Based on these models, the end-to-end network throughput and the total energy consumption of the network are examined. For a network with a given node density, our results show the optimal transmission power for control messages and for data messages that will yield maximum throughput and minimum energy consumption per message.

Wireless networks have a constraint on their functional lifetime. This is due to the limited energy capacity of batteries powering the wireless nodes. For extending the lifetime of such battery-operated networks, we present a scheme for dynamically selecting the transmission rate for each node in the network. The transmission rate is based on the available energy budget in each node's battery. The goal is to increase the network capability of delivering more packets. The rate selection for each node is subject to satisfying a QoS timing constraint on the packet delivery time. Through adaptively varying each node's rate, we extended the lifetime 10 times on average more transmitting at a maximum rate and delivered on average 7.5 times more data packets. When compared with a scheme that transmits data at a lower rates independent of the battery levels, our scheme delivers up to 12% more packets for the same available total energy.

We address power-aware scheduling of periodic tasks to reduce CPU energy consumption in hard real-time systems through dynamic voltage scaling. Our intertask voltage scheduling solution includes three components: 1) a static (offline) solution to compute the optimal speed, assuming worst-case workload for each arrival, 2) an online speed reduction mechanism to reclaim energy by adapting to the actual workload, and 3) an online, adaptive and speculative speed adjustment mechanism to anticipate early completions of future executions by using the average-case workload information. All these solutions still guarantee that all deadlines are met. Our simulation results show that our reclaiming algorithm alone outperforms other recently proposed intertask voltage scheduling schemes. Our speculative techniques are shown to provide additional gains, approaching the theoretical lower-bound by a margin of 10 percent.

We describe how to exploit the scheduling slack in a real-time system to reduce energy consumption and achieve fault tolerance at the same time. During failure-free operation, a task takes checkpoints to enable recovery from failure. Additionally, the system exploits the slack to conserve energy by reducing the processor speed. If a task fails, it will restart from a saved checkpoint and execute at maximum speed to guarantee that the deadlines are met. We show that the number of checkpoints and their placements interact in subtle ways with the power management policy. We study two checkpoint placement policies for aperiodic tasks and analytically derive the optimal number of checkpoints to conserve energy under each. This optimal number allows the CPU speed to be slowed down to the level that yields minimum energy consumption, while still guaranteeing recoverability of tasks under each checkpointing policy. The results show that traditional periodic checkpointing is not the best policy for the combined purpose of conserving energy and guaranteeing recovery. Instead, better energy savings are possible through a nonuniform distribution of checkpoints that takes into account the energy consumption and reliability factors. Depending on the amount of slack and the checkpointing overhead, energy can be reduced by up to 68 percent under nonuniform checkpointing. We also demonstrate the applicability of these checkpoint placement policies to periodic tasks.

In the recent past, with the advent of more powerful networks, computations have become more distributed in nature and control of network resources has become essential for operating systems (OS). Nevertheless, proposed primitives for network control at end-host OS are designed without an OS design perspective and have been in disagreement with existing OS constructs, causing a variety of problems. We propose a new OS service for network control, namely, hierarchical virtualization of network interface. The virtual network interface is hierarchically structured and attached to various OS constructs, such as threads, processes, and sockets, for the control of their network I/O. We show that our proposed mechanism provides the following properties: 1) flexible control granularity, 2) resource protection, 3) reasonable abstraction and application programming interface (API), and 4) various types of packet scheduling and control in a single framework, such as work-conserving and nonwork-conserving, in accordance with existing OS mechanisms. For a proof of concept, we present an implementation on a PC-Unix, using the file system abstraction, and carry out systematic profiling. The system exhibited the expected control behavior, that is, good responsiveness to the control commands while keeping the performance penalty small.

In this paper, we propose a novel scheduling framework for a dynamic real-time environment with energy constraints. This framework dynamically adjusts the CPU voltage/frequency so that no task in the system misses its deadline and the total energy savings of the system are maximized. In this paper, we consider only realistic, discrete-level speeds.Each task in the system consumes a certain amount of energy, which depends on a speed chosen for execution. The process of selecting speeds for execution while maximizing the energy savings of the system requires the exploration of a large number of combinations, which is too time consuming to be computed online. Thus, we propose an integrated heuristic methodology, which executes an optimization procedure in a low computation time. This scheme allows the scheduler to handle power-aware real-time tasks with low cost while maximizing the use of the available resources and without jeopardizing the temporal constraints of the system. Simulation results show that our heuristic methodology is able to generate power-aware scheduling solutions with near-optimal performance.

Power aware computing has become popular, recently and many techniques have been proposed to manage processor energy consumption for traditional real-time applications. In this paper, we are concerned mainly with the AND/OR model of real-time applications that have different execution paths consisting of different tasks. The contribution of this paper is twofold. First, we propose a greedy slack stealing algorithm to deal with applications represented by AND/OR graphs and prove its correctness in terms of meeting the timing constraints. Then, using statistical information about the applications, we propose a few variations of speculative scheduling algorithms that intend to save energy by reducing the number of speed changes (and, thus, the overhead) while ensuring that the application meets its timing constraints. Some practical issues are also considered, such as shared memory access contention and idle energy consumption. The performance of the algorithms is analyzed with respect to processor energy savings. The results surprisingly show that the greedy slack stealing scheme is better than some speculative schemes and that the greedy scheme is good enough when a reasonable minimal speed exists in the system or when there are only a few (four to six) voltage/speed levels.

This paper tries to tackle the problem of providing retrofitting network QoS in clustered configurations. For this purpose, we designed a QoS manager which runs on each of the internal cluster nodes and controls network I/O of local interface cooperating with peer managers on other nodes towards a certain QoS policy. First, we show the design of control framework, contending that an end-host manager-based mechanism is a desirable approach, which utilizes an end-host oriented network control primitive, Netnice. Second, for flexibility of configuration, we propose object-oriented modeling of the QoS manager with event-handler based configuration mechanism, and show the design of an object-oriented configuration language that allow simple and flexible definition of QoS policies. Lastly, results from two simple experiments with a Web server cluster are analyzed.

In the context of battery-powered real-time systems three constraints need to be addressed: energy; deadlines; and task rewards. Many future real-time systems will count on different software versions, each with different rewards, time and energy requirements, to achieve a variety of QoS-aware tradeoffs. We propose a solution that allows the device to run the most valuable task versions while still meeting all deadlines and without depleting the energy. Assuming that the battery is rechargeable, we also propose: (a) a static solution that maximizes the system value assuming a worst-case scenario (i.e., worst-case task execution times); and (b) a dynamic scheme that takes advantage of the extra energy in the system when worst-case scenarios do not happen. Three dynamic policies are shown to make better use of the recharging energy while improving the system value.

The Pfair algorithms are optimal for independent periodic real-time tasks executing on a multiple-resource system. However, they incur a high scheduling overhead by making scheduling decisions in every time unit to enforce proportional progress for each task. In this paper, we will propose a novel scheduling algorithm, boundary fair (BF), which makes scheduling decisions and enforces fairness to tasks only at period boundaries. The BF algorithm is also optimal in the sense that it achieves 100% system utilization. Moreover, by making scheduling decisions at period boundaries, BF effectively reduces the number of scheduling points. Theoretically, the BF algorithm has the same complexity as that of the Pfair algorithms. But, in practice, it could reduce the number of scheduling points dramatically (e.g., up to 75% in our experiments) and thus reduce the overall scheduling overhead, which is especially important for online scheduling.

Rate-monotonic scheduling (RMS) is a widely used real-time scheduling technique. This paper proposes RBound, a new admission control for RMS. RBound has two interesting properties. First, it achieves high processor utilization under certain conditions. We show how to obtain these conditions in a multiprocessor environment and propose a multiprocessor scheduling algorithm that achieves a near optimal processor utilization. Second, the framework developed for RBound remains close to the original RMS framework (that is, task dispatching is still done via a fixed-priority scheme based on the task periods). In particular, we show how RBound can be used to guarantee a timely recovery in the presence of faults and still achieve high processor utilization. We also show how RBound can be used to increase the processor utilization when aperiodic tasks are serviced by a priority exchange server or a deferrable server.

The need for supporting dynamic real-time environments where changes in workloads occur frequently requires a scheduling framework that: (1) explicitly addresses overload conditions, (2) allows the system to achieve graceful degradation while guaranteeing the deadlines of the most critical tasks in the system, and (3) supports an efficient runtime selection mechanism capable of determining the load to be shed from the system to handle the overload. In this paper, we propose a novel scheduling framework for a real-time environment that experiences dynamic workload changes. This framework is capable of adjusting the system workload in incremental steps under overloaded conditions such that the most critical tasks in the system are always scheduled and the total value of the system is maximized. Each task has an assigned criticality value and consists of two parts, a mandatory part and an optional part. A timely answer is available after the mandatory part completes execution and its value may be improved by executing the entire optional part. The process of selecting tasks (mandatory or optional parts) to discard while maximizing the value of the system requires the exploration of a potentially large number of combinations. Since an optimal solution is too time-consuming to be computed online, an approximate algorithm is executed incrementally whenever the processor would otherwise be idle, progressively refining the quality of the solution. This scheme allows the scheduler to handle overloads with low cost while maximizing the use of the available resources and without jeopardizing the temporal constraints of the most critical tasks in the system. Simulation results show that few stages of the algorithm need to be executed for achieving a performance with near-optimal results.

New technologies have brought about a proliferation of embedded systems, which vary from control systems to sensor networks to personal digital assistants. Many of the portable embedded devices run several applications, which typically have three constraints that need to be addressed: energy , deadline , and reward . However, many of these portable devices do not have powerful enough CPUs and batteries to run all applications within their deadlines. An optimal scheme would allow the device to run the most applications, each using the most amount of CPU cycles possible, without depleting the energy source while still meeting all deadlines. In this paper we propose a solution to this problem; to our knowledge, this is the first solution that combines the three constraints mentioned above. We devise two algorithms, an optimal algorithm for homogeneous applications (with respect to power consumption) and a heuristic iterative algorithm that can also accommodate heterogeneous applications (i.e., those with different power consumption functions). We show by simulation that our iterative algorithm is fast and within 1% of the optimal.

Real-time systems (RTS) are those whose correctness depends on satisfying the required functional as well as the required temporal properties. Due to the criticality of such systems, recovery from faults is an essential part of a RTS. In many systems, such as those supporting space applications, single event upsets (SEUs) are the prevalent type of faults; SEUs are transient faults and affect a single task at a time. We present a scheme to guarantee that the execution of real-time tasks can tolerate SEUs and intermittent faults assuming any queue-based scheduling technique. Three algorithms are presented to solve the problem of adding fault tolerance to a queue of real-time tasks by reserving sufficient slack in a schedule so that recovery can be carried out before the task deadline without compromising guarantees given to other tasks. The first algorithm is a dynamic programming optimal solution, the second is a linear-time heuristic for scheduling dynamic tasks, and the third algorithm comprises extensions to address queues with gaps between tasks (gaps are caused by precedence, resource, or timing constraints). We show through simulations that the heuristics closely approximate the optimal algorithm. Finally, we describe the implementation of the modified admission control algorithm, non-preemptive scheduler, and recovery mechanism in the FT-RT-Mach operating system.

Power aware computing has become popular recently and many techniques have been proposed to manage the energy consumption for traditional real-time applications. We have previously proposed (2001) two greedy slack sharing scheduling algorithms for such applications on multi-processor systems. In this paper, we are concerned mainly with real-time applications that have different execution paths consisting of different number of tasks. The AND/OR graph model is used to represent the application data dependence and control flow. The contribution of this paper is twofold. First, we extend our greedy slack sharing algorithm for traditional applications to deal with applications represented by AND/OR graphs. Then, using the statistical information about the applications, we propose a few variations of speculative scheduling algorithms that intend to save energy by reducing the number of speed changes (and thus the overhead) while ensuring that the applications meet the timing constraints. The performance of the algorithms is analyzed with respect to energy savings. The results obtained show that the greedy scheme is better than some speculative schemes and that the greedy scheme is good enough when a reasonable minimal speed exists in the system.

Several routing protocols for mobile ad hoc networks work efficiently only in bidirectional networks. Unidirectional links may exist in a real network due to variations in transmission power of different nodes, noise or other signal propagation phenomena, and heterogeneity in the transmission hardware of nodes in the network. We introduce a sub-layer called sub routing layer, SRL, between the network and the MAC layer to provide a bidirectional abstraction of the unidirectional network to the routing protocols. We present a scalable and efficient way to provide this abstraction by finding and maintaining multi-hop reverse routes to each unidirectional link. We simulate SRL and a modified version of AODV (ad hoc on demand distance vector) that uses SRL to route packets in a unidirectional network. We observed that with SRL, the packet delivery of AODV in unidirectional networks increases substantially. Further our simulations indicate that reverse routes are often only a few hops long and hence the overhead of using SRL is very low.

Duplex and triple modular redundancy (TMR) systems are used when a high-level of reliability is desired. Real-time systems for autonomous critical missions need such degrees of reliability, but energy consumption becomes a dominant concern when these systems are built from high-performance processors that consume a large budget of electrical power for operation and cooling. Examples where energy consumption and real time are of paramount importance include reliable computers onboard mobile vehicles, such as the Mars Rover, satellites, and other autonomous vehicles. At first inspection, a duplex system uses about two thirds of the components that a TMR system does, leading one to conclude that duplex systems are more energy-efficient. This paper shows that this is not always the case. We present an analysis of the energy efficiency of duplex and TMR systems when used to tolerate transient failures. With no power management deployed, the analysis supports the intuitive impression about the relative superiority of duplex systems in energy consumption. The analysis shows, however that the gap in energy consumption between the two types of systems diminishes with proper power management. We introduce the concept of an optimistic TMR system that offers the same reliability and performance as the traditional one, but at a fraction of the energy consumption budget. Optimistic TMR systems are competitive with respect to energy consumption when compared with a power-aware duplex system, can even exceed it in some situations, and have the added bonus of providing tolerance to permanent faults.

Typical real-time scheduling theory has addressed deadline and energy constraints as well as deadline and reward constraints simultaneously in the past. However we believe that embedded devices with varying applications typically have three constraints that need to be addressed: energy, deadline, and reward. These constraints play important roles in the next generation of embedded devices, since they provide users with a variety of QoS-aware trade-offs. An optimal scheme would allow the device to run the most critical and valuable applications, without depleting the energy source while still meeting all deadlines. In this paper we propose a solution to this problem for typical control systems, such as frame-based task sets. We devise two algorithms that closely approximate the optimal solution while taking only a fraction of the runtime of an optimal solution.

In this paper, we provide an efficient solution for periodic real-time tasks with (potentially) different power consumption characteristics. We show that a task T/sub i/ can run at a constant speed S/sub i/ at every instance without hurting optimality. We sketch an O(n/sup 2/ log n) algorithm to compute the optimal S/sub i/ values. We also prove that the EDF (Earliest Deadline First) scheduling policy can be used to obtain a feasible schedule with these optimal speed values.

In this paper we address power-aware scheduling of periodic hard real-time tasks using dynamic voltage scaling. Our solution includes three parts: (a) a static (off-line) solution to compute the optimal speed, assuming worst-case workload for each arrival, (b) an on-line speed reduction mechanism to reclaim energy by adapting to the actual workload, and (c) an online, adaptive and speculative speed adjustment mechanism to anticipate early completions of future executions by using the average-case workload information. All these solutions still guarantee that all deadlines are met. Our simulation results show that the reclaiming algorithm saves a striking 50% of the energy, over the static algorithm. Further our speculative techniques allow for an additional approximately 20% savings over the reclaiming algorithm. In this study, we also establish that solving an instance of the static power-aware scheduling problem is equivalent to solving an instance of the reward-based scheduling problem [1, 4] with concave reward functions.

Reward-based scheduling refers to the problem in which there is a reward associated with the execution of a task. In our framework, each real-time task comprises a mandatory and an optional part. The mandatory part must complete before the task's deadline, while a nondecreasing reward function is associated with the execution of the optional part, which can be interrupted at any time. Imprecise computation and Increased-Reward-with-Increased-Service models fall within the scope of this-framework. In this paper, we address the reward-based scheduling problem for periodic tasks. An optimal schedule is one where mandatory-parts complete in a timely manner and the weighted average reward is maximized. For linear and concave reward functions, which are most common, we 1) show the existence of an optimal schedule where the optional service time of a task is constant at every instance and 2) show how to efficiently compute this service time. We also prove the optimality of Rate Monotonic Scheduling (with harmonic periods), Earliest Deadline First, and Least Laxity First policies for the case of uniprocessors when used with the optimal service times we computed. Moreover, we extend our result by showing that any policy which can fully utilize all the processors is also optimal for the multiprocessor periodic reward-based scheduling. To show-that our optimal solution is pushing the limits of reward-based scheduling, we further prove that, when the reward functions are convex, the problem becomes NP-Hard. Our static optimal solution, besides providing considerable reward improvements over the previous suboptimal strategies, also has a major practical benefit. Run-time overhead is eliminated and existing scheduling disciplines may be used without modification with the computed optimal service times.

The imprecise computation (IC) model is a general scheduling framework that is capable of expressing the precision vs. timeliness tradeoff involved in many current real-time applications. In that model, each task comprises mandatory and optional parts. While allowing greater scheduling flexibility, the mandatory parts in the IC model still have hard deadlines, and hence they must be completed before the task's deadline, even in the presence of faults. In this paper, we address fault-tolerant (FT) scheduling issues for IC tasks. First, we propose two recovery schemes, namely immediate recovery and delayed recovery. These schemes can be readily applied to provide fault tolerance to the mandatory parts by scheduling the optional parts appropriately for recovery operations. After deriving the necessary and sufficient conditions for both schemes, we consider the FT-optimality problem, i.e. generating a schedule which is FT and whose reward is maximum among all possible FT schedules. For immediate recovery, we present and prove the correctness of an efficient FT-optimal scheduling algorithm. For delayed recovery, we show that the FT-optimality problem is NP-hard, and thus is intractable.

In many real-time communication applications, predictable and guaranteed timeliness is one of the critical components of the quality of service (QoS) requirements. In this paper, we propose a new real-time message model with both rate requirements and distance constraints. Two algorithms are presented to schedule dynamic real-time message streams in a TDMA (time division multiple access) frame based on different scheduling policies by making greedy choices or optimization choices. The performance of the two algorithms is evaluated and compared in terms of time complexity, acceptance ratio and scheduling jitter via simulation.

In this paper, we present "netnice", a mechanism that allows processes to throttle their own network bandwidth consumption. As the name suggests, it is inspired by the Unix "nice" command in that it allows users and administrators to limit the network resources used by individual processes in order to avoid impacting the performance of other processes. In the paper, to address the problem of transient performance deterioration in local area network (LAN) environments, we propose a bandwidth limitation primitive that works within a host's kernel, called netnice. We also show several uses of netnice. Through experimentation in a small LAN of FreeBSD machines, we show how netnice allows for higher degree of controllability in bandwidth management.

Proposes a novel scheduling framework for a real-time environment that experiences dynamic changes. This framework is capable of adjusting the system workload in incremental steps under overloaded conditions such that the most critical tasks in the system are always scheduled and the total value of the system is maximized. Each task has an assigned criticality value and consists of two parts: a mandatory part and an optional part. A timely answer is available after the mandatory part completes execution and its value may be improved by executing the entire optional part. Optional parts can be discarded in overloaded conditions. The process of selecting optional parts to discard while maximizing the value of the system requires the exploration of a potentially large number of combinations. Since this process is too time-consuming to be computed online, an approximate algorithm is executed incrementally whenever the processor would otherwise be idle, progressively refining the quality of the solution. This criterion allows the scheduler to handle overloads with low cost while maximizing the use of the available resources and without jeopardizing the temporal constraints of the most critical tasks in the system. Simulation results show that few stages of the algorithm need to be executed to achieve a performance with near-optimal results.

This paper proposes a Versatile Network Architecture (V-NET) to support flexible delay guarantees for applications in real-time networks. Applications communicate over the V-NET by using end-to-end network connections which support real-time and reliability characteristics tailored to meet the application's specified requirements. V-NET differs from other proposed architectures in that, in addition to addressing the issue of quality of service (QoS) feasibility for a wide spectrum of real-time applications, it also provides a mechanism to determine a network state dependent range of feasible delay values at each switching node along the routing path. These delay ranges can be used to assign per-node delays that reflect the resource availability of the node, thereby reducing the likelihood of bottlenecks along the routing path. The V-NET delay guarantees are provided for a variety of packet scheduling algorithms and traffic policing mechanisms. This flexibility is an important design consideration as a real-time network architecture must accommodate existing and future multimedia applications, with hard-, soft-, and non-real-time traffic. The performance evaluation results demonstrate the efficiency of this scheme in handling different traffic scenarios and QoS requirements. We have shown that it is possible, and indeed efficient, to determine an upper-bound on the delay of real-time traffic, when using our per-node delay assignment policies.

Real-time systems are being increasingly used in several applications which are time-critical in nature. Fault tolerance is an essential requirement of such systems, due to the catastrophic consequences of not tolerating faults. In this paper, we study a scheme that guarantees the timely recovery from multiple faults within hard real-time constraints in uniprocessor systems. Assuming earliest-deadline-first scheduling (EDF) for aperiodic preemptive tasks, we develop a necessary and sufficient feasibility-check algorithm for fault-tolerant scheduling with complexity O(n/sup 2/-/spl kappa/), where n is the number of tasks to be scheduled and /spl kappa/ is the maximum number of faults to be tolerated.

Many real-time multiprocessor scheduling techniques have been proposed to guarantee the timely execution of periodic preemptive real-time tasks. However timeliness is usually only guaranteed in the absence of faults, which may be unacceptable for some critical systems. We therefore address the problem of multiprocessor scheduling for preemptive real-time tasks so that the timeliness of the system can be guaranteed even in the presence of faults. This work focuses on global scheduling where tasks can migrate across processors. We consider two varieties of global multiprocessor scheduling: in the frame-based model, an aperiodic task set is scheduled to create a template (frame), and that schedule may be executed periodically. In the periodic model, each task in the set has a separate period, and is executed with no explicitly predetermined schedule. For each model, we show how to guarantee timely execution and recovery in the general case. We also propose solutions that improve upon this general case when all tasks require the same amount of time to recover from a fault.

Systems with timing constraints have become pervasive in several disciplines, such as real-time artificial intelligence, operating systems, operations research, and local area networks. Most of the work in real-time system scheduling deals with admission control algorithms to guarantee that accepted tasks will meet their deadlines. In this paper, we compare the different algorithms, and suggest a novel algorithm that subsumes the previous ones with respect to schedulability in the case where the system may suffer from transient overloads and where tasks have precedence constraints among them. We show how our algorithm works in allocating time to competing reasoning modules in dynamic environments.

Reward-based scheduling refers to the problem in which there is a reward associated with the execution of a task. In our framework, each real-time task comprises a mandatory and an optional part, with which a nondecreasing reward function is associated. Imprecise Computation and Increased-Reward-with-Increased-Service models fall within the scope of this framework. In this paper we address the reward-based scheduling problem for periodic tasks. For linear and concave reward functions we show: (a) the existence of an optimal schedule where the optional service time of a task is constant at every instance and (b) how to efficiently compute this service time. We also prove that RMS-h (RMS with harmonic periods), EDF and LLF policies are optimal when used with the optimal service times we computed, and that the problem becomes NP-Hard, when the reward functions are convex. Further, our solution eliminates run-time overhead, and makes possible the use of existing scheduling disciplines.

We are developing a teaching package that can be used in a college course that would fill a gap among current science majors and teach senior-level undergraduate students theory and practice of real-time operating systems, including their requirements, characteristics, internals, and specification. This course has two components: (1) a theoretical part, and (2) a practical hands-on implementation component achieved with DORITOS (Distributed Object-Based Real-time InsTructional Operating System) as the implementation environment. DORITOS' design is based on UC-Berkeley's NACHOS. The DORITOS package will be distributed with DKaffe (a modified version of Kaffe JVM) and a basic system which allows students to run simple threads.In this paper, we focus on the practical, hands-on system that allows students to learn the internals of a Real-time Operating Systems (RTOS). Throughout the term, assignments require students to use and modify DORITOS to implement real-time elements as well as to analyze the performance of implemented algorithms.

Clusters of workstations, connected by a fast network, are emerging as a viable architecture for building high-throughput fault-tolerant servers. This type of architecture is more scalable and more cost-effective than a tightly coupled multiprocessor and may achieve as good a throughput. Two of the most important issues that a designer of such clustered servers must consider in order for the system to meet its fault-tolerance and throughput goals are the load-balancing scheme and the fault-tolerance scheme that the system will use. This paper explores several combinations of such fault-tolerance and load-balancing schemes and compares their impact on the maximum throughout achievable by the system, and on its survivability. In particular, we show that a fault-tolerance scheme may have an effect on the throughput of the system, while a load-balancing scheme may affect the ability of the system to override failures. We study the scalability of the different schemes under different loads and failure conditions. Our simulations take into consideration the overhead of each scheme, the network contention, and the resource loads.

Even though real-time systems have the stringent constraint of completing tasks before their deadlines, many existing real-time operating systems do not implement fault tolerance capabilities. In this paper we summarize fault tolerant real-time scheduling policy for dynamic tasks with ready times and deadlines. Our focus in this paper is the implementation, which includes fault-tolerant scheduling, re-scheduling, and recovery mechanisms in the FT-RT-Mach operating system, a fault-tolerant version of RT-Mach. A real-time train control application is then implemented using the FT-RT-Mach operating system. Copyright © 1999 John Wiley & Sons, Ltd.

The authors study GRMS, a global scheduling scheme for rate monotonic tasks on a multiprocessor. Several admission control algorithms for GRMS are presented, both for hard and soft real-time tasks. The average performance of these admission control algorithms is compared with the performance of known partitioning schemes. The result of these comparisons outlines some situations where one scheme is preferable over the other. Partitioning schemes are better suited for hard real-time systems, while a global scheme is preferable for soft real-time systems.

Multicast service is an important part of any modern routing architecture. Motivations for many-to-many multicast include general unpredictability of membership in many real applications; simplicity of the rendezvous for the application programmer; and low cost to end systems and switches in terms of state to maintain for the delivery tree. Shared trees have an even greater advantage over source based trees in the latter respect. Shared trees (as in the CBT model for Internet) are supported in the form of a single logical VC per multicast group (i.e., multipoint-to-multipoint VC or mp-mp VC) in the ATM networks. CRAM, SEAM and SPAM have been previously proposed for supporting mp-mp VC. The work in this paper does a performance comparison of these three schemes, with respect to buffer requirements, end-to-end delay, packet jitter and traffic overhead. Our evaluation is carried out through extensive simulations with different topologies and sender traffic types.

The desire to switch ATM cells at high speed and forward data packets in a connectionless (CL) manner poses a challenging architectural difficulty that has not yet been satisfactorily resolved. This difficulty is mainly due to lack of a packet concept in ATM switches-a packet is a level-3 abstraction, totally hidden from the switch. The switch-borne router (SBR) is a proposed switch/router architecture that makes it possible to switch CL packets at very high speed using ATM technology. This paper introduces the SBR and compares its performance with other forwarding methods using a simulator. Compared to other methods, the SBR allows for a significantly smaller number of open/close VC operations per second, has less buffering requirement, and achieves higher throughput. The same results hold using a real-life Internet packet trace as well as using traffic drawn from a synthetic workload generator.

Many distributed multimedia applications involve data delivery from a source to multiple destinations, the participating nodes forming a multicast group. In the naive solution, separate connections can be established from each source to other group members. However a tree can be established for each source with the participants as the leaf nodes or just have one tree spanning all the participants. In this paper, we introduce the data forwarding model to support such shared multicast trees over the ATM networks called SPAM (a Simple Protocol for ATM Multicast). The authors work allow the wide area multicast protocols (like CBT and PIM) to be supported in ATM networks. Further, SPAM improves the error detection and allows for leaf initiated join of UNI 4.0.

The purpose of this paper is twofold: we first present a novel architecture for real-time active vision systems, and then enhance the architecture with a unified approach to fault tolerance. Our system is designed modularly in order to enable the flexible addition of hardware and software redundancy and also to allow reconfiguration when and where needed. This gives us the ability to handle faults in the context of active vision.

Clusters of workstations, connected by a fast network, are emerging as a viable architecture for building high-throughput fault-tolerant servers. This type of architecture is more scalable and more cost-effective than a tightly coupled multiprocessor and may achieve as good a throughput. We explore several combinations of fault tolerance (FT) and load-balancing (LB) schemes, and compare their impact on the maximum throughput achievable by the system, and on its survivability. In particular, we show that the FT scheme has an effect on the throughput of the system, while the LB scheme affects the ability of the system to override failures. We study the scalability of the different schemes under different loads and failure conditions. Our simulations take into consideration the overhead of each scheme, the network contention, and the resource loads.

Real time systems are being increasingly used in several applications which are time critical in nature. Fault tolerance is an important requirement of such systems, due to the catastrophic consequences of not tolerating faults. We study a scheme that provides fault tolerance through scheduling in real time multiprocessor systems. We schedule multiple copies of dynamic, aperiodic, nonpreemptive tasks in the system, and use two techniques that we call deallocation and overloading to achieve high acceptance ratio (percentage of arriving tasks scheduled by the system). The paper compares the performance of our scheme with that of other fault tolerant scheduling schemes, and determines how much each of deallocation and overloading affects the acceptance ratio of tasks. The paper also provides a technique that can help real time system designers determine the number of processors required to provide fault tolerance in dynamic systems. Lastly, a formal model is developed for the analysis of systems with uniform tasks.

The generation of a real-time schedule from a task precedence graph is complex and time consuming. In order to improve the efficiency of generating schedules, we propose a scheduling algorithm based upon the compact task graph (CTG) representation. In addition to precedence constraints, a CTG explicitly expresses the potential for interleaving the execution of tasks on a single processor and overlapping the execution of task on multiple processors. The CTG is compact since it expresses the potential for overlapping and interleaving without the generation of smaller tasks. If a task cannot be scheduled to meet its deadline through interleaving and overlapping, then selected tasks are split into smaller tasks which increases the feasibility, and hence the complexity, of scheduling the task. Thus, in effect our approach increases the complexity of scheduling a usual task graph only if it is essential. Our results demonstrate that a significant reduction in the time of scheduling is achieved using CTGs and our algorithms that exploit the CTGs. We also show how CTGs can be used for distributed on-line scheduling.

The active vision paradigm couples perception and action at several different levels. The effective use of active vision in complex robotic tasks requires that these levels operate both independently and cooperatively, reliably and in real-time. In this paper, we present a system for real-time active vision with fault tolerance. The system provides a vocabulary of active vision routines along with the means for composing the routines into continuously running perception-action processes. A novel architecture which enables the integration of the perceptive capabilities of real-time active vision with the active capabilities of other robotic devices is presented. We then enhance the architecture with a unified approach to fault tolerance and present results from experiments and simulations.

We present a scheme to guarantee that the execution of real-time tasks can tolerate transient and intermittent faults assuming any queue-based scheduling technique. The scheme is based on reserving sufficient slack: in a schedule such that a task can be re-executed before its deadline without compromising guarantees given to other tasks. Only enough slack is reserved in the schedule to guarantee fault tolerance if at most one fault occurs within a time interval. This results in increased schedulability and a very low percentage of deadline misses even if no restriction is placed on the fault separation. We provide two algorithms to solve the problem of adding fault tolerance to a queue of real-time tasks. The first is a dynamic programming optimal solution and the second is a greedy heuristic which closely approximates the optimal.

A model is given for developing application with fault-tolerance requirements and real-time constraints. Applications in this model are specified using computation graphs, in which vertices represent tasks and arcs represent precedence constraints. Tasks are replicated to provide required fault tolerance and ensure that a real-time application will meet its deadlines despite failures. The authors develop an analytical model to calculate the probability of successful execution of applications with task replications. They propose an efficient algorithm for the analysis of applications that are composed of subgraphs, each of which has a single source and a single sink. The results of the analysis can be used with information from allocation/scheduling to develop applications with desired timing and fault-tolerance requirements.>

Operating systems prototypes are becoming more attractive and more widespread because the more laborious and detailed work can be overlooked. The pseudo-implementation permits verification of principles, enhancing the studies of system properties through quick feedback. The authors present their experience in prototyping MARUTI, a distributed fault tolerant real-time operating system on top of UNIX. They report the actual implementation experience in developing the first version of such a prototype. They start by giving some motivation and background on prototyping, and describing the model they used. In the next section, they summarize the design of MARUTI. They describe their strategy of implementing objects as UNIX processes and the language extensions required. They report experience in creating the real-time operating system prototype. And present some future research topics.>

An allocation scheme is proposed that accomplishes the hard real-time goal of guaranteeing a deadline satisfaction in case the job is accepted. In addition, the scheme supports fault-tolerance objectives in both damage containment and resiliency requirements. It does this in cooperation with a schedulability verification mechanism and with an object architecture in which for each object there exists a calendar that maintains the time of its execution. The scheme can be used for reallocation while increasing the resiliency.>