Along with the advent of a high-end SoC with multiple CPU clusters and many GPUs, the automotive industry has a strong motivation to consolidate multi-domain applications on such a single SoC for wiring harness reduction and space/weight saving. For this, it is essential to bound their mutual interferences among CPU+GPU clusters on the system memory since advanced automotive applications use huge size code/data like autonomous driving and multi-screen infotainment. In order to guarantee memory bandwidth to each cluster, this paper proposes a cluster-level memory access regulation that aggregates the total memory access amount by each cluster (by all CPU cores and GPUs within the cluster) and throttles the cluster if it exceeds the given threshold. Then, we propose a few-shot measurement based optimal memory bandwidth allocation that can find a near optimal solution with only a few measurements, which is practically essential to save the system development cost. Our extensive experiments on a real SoC board say that our proposed techniques successfully regulate each cluster's memory bandwidth usage within ± 10 % margin of the allocated bandwidth. Also, our optimization can achieve a near-optimal utility with less than 0.6 % loss on average compared to the real optimal, with only a few measurements (mostly three measurements) instead of 25 measurements needed for the real optimal.

Low Earth Orbit (LEO) satellite communication has recently gained significant attention from the industry as it enables fast and seamless connectivity. However, as the number of satellites in LEO networks increases, making the network denser and more dynamic, a scalable routing algorithm is required to efficiently find paths. Many existing routing algorithms are primarily designed for small-scale networks or terrestrial IP networks and may not be suitable for large-scale LEO networks. To address this challenge, we propose an efficient routing algorithm that leverages the grid-like topology by clustering satellites into sub-mesh groups and selecting major routing directions. To accommodate the continuously changing and dynamic topology, we introduce an update period determination method based on a devised correlation metric. Simulation results demonstrate that the proposed algorithm efficiently discovers near-optimal paths in LEO networks designed with various distance-based cost metrics while significantly reducing computational overhead.

Adolescents and their parents hesitate to acknowledge mental health issues until symptoms severely worsen, making timely treatment challenging. Moreover, infrequent psychiatric consultations often fail to adjust treatments to the dynamic nature of mental health states. To address these issues, our paper proposes an AI-based mental health assessment framework for adolescent mental health through non-invasively collected data from daily digital activities on their mobile devices, including tablets and smartphones. For this, we collect fifteen different types of passive sensor data across three primary categories of activities: studying, smartphone using, and metaverse gaming. Additionally, each adolescent completes self-survey reports on eight different disorders which are used as labels. Then, feature extraction is conducted based on this dataset, which yields 1,523 features that could function as potential digital biomarkers of mental health conditions in adolescents. Utilizing these features, our algorithm named CAMP: Customizable Automated Machine learning Process incorporates simulated annealing for feature selection. This approach enables the construction of AI models for mental health assessment that are finely tuned to domain specific strategies. Our experiments show that our proposed framework can significantly improve models' performance.

The trend towards integration of distributed Electronic Control Units (ECUs) is becoming increasingly popular due to the high hardware costs and maintenance difficulties associated with traditional distributed ECUs. However, this integration can lead to mutual interference among multiple-domain applications that share hardware resources, particularly in Advanced Driver Assistance Systems (ADAS). This study aims to develop a profiling tool to analyze shared resource interference in integrated ECU. Existing profilers track resource usage at the core or process level. However, with the use of multi-core processors and multiple processes sharing resources, this study introduces an adaptive frequency cluster-level performance profiler (W-CMP) for profiling resource usage at the cluster level, where clusters represent sets of cores. To analyze the root causes, it is essential to maintain a consistent sampling time interval, referred to as the profiling window size. This resolves the imbalance issue encountered in profiling window sizes by conventional profilers. Furthermore, to mitigate the significant profiling overhead that can cause performance degradation, the study automates the exploration of the optimal profiling frequency. This is done by considering the application's overhead and ensuring profiling at the highest resolution that meets the application's performance requirements. As a result, a profiler operating at the cluster level with minimized overhead and accurate profiling window is constructed, enabling the analysis of shared resource interference for integrated ECU.

This paper presents methods to optimize the response time of ROS (Robot Operating System), a widely utilized open-source meta-operating system in robotic software development. Despite its popularity, ROS lacks real-time capabilities, making it unsuitable for real-time control and difficult to use in embedded systems. Recently, DAG (Directed Acyclic Graph) task scheduling algorithms have gained much attention, but they are challenging to apply in the current design of ROS. In this work, we analyze that there are three major challenges in ROS; (i) misalignment delay, (ii) message delivery mechanism using TCP/IP, and (iii) multiple overlapping instances of a single task. We first calculate the new response time bound considering misalignment delay and propose an optimization technique using it to solve the first problem. Furthermore, we address the remaining challenges by assigning priority to the nodes of the DAG and ksoftirqd processes. Our experiments using random tasks show significant improvement, outperforming the state-of-art methods. In addition, our methods are validated through testing autonomous driving software on embedded systems, proving their real-world applicability.

Designing or learning an autonomous driving policy is undoubtedly a challenging task as the policy has to maintain its safety in all corner cases. In order to secure safety in autonomous driving, the ability to detect hazardous situations, which can be seen as an out-of-distribution (OOD) detection problem, becomes crucial. However, conventional datasets often only contain expert driving demonstrations, although some non-expert or uncommon driving behavior data are needed to implement a safety guaranteed autonomous driving platform. To this end, we present a dataset called the R3 Driving Dataset, composed of driving data with different qualities. The dataset categorizes abnormal driving behaviors into eight categories and 369 different detailed situations. The situations include dangerous lane changes and near-collision situations. To further enlighten how these abnormal driving behaviors can be detected, we utilize different uncertainty estimation and anomaly detection methods for the proposed dataset. From the results of the proposed experiment, it can be inferred that by using both uncertainty estimation and anomaly detection, most of the abnormal cases in the proposed dataset can be discriminated. https://rllab-snu.github.io/projects/R3-Driving-Dataset/doc.html

NAND flash memory has a disadvantage in that additional work in the flash translation layer (FTL) is required for compatibility with the block interface. In particular, FTL should periodically perform garbage collection (GC) to reclaim free data blocks. Unfortunately, GC includes an expensive erase operation and can cause write amplification (WA), which writes more pages than the system requested. Therefore, it is essential to design a victim selection policy to reduce WA during GC. Greedy and Cost-Benefit (CB) are the most widely known victim selection policies. However, Greedy does not consider locality, and CB suffers computational overhead. This paper proposes Low Computational Cost-Benefit (LC-CB), a novel victim selection policy compensating for these shortcomings. Unlike the existing methods to improve CB, LC-CB changes the operation itself used in the victim selection metric to low computational. This paper describes the constraint required to make a victim selection policy with a low computational overhead and explains that LCCB can consider locality while satisfying these constraints. The experimental results show that our proposed policy can reduce time overhead by 70% compared to CB and reduce WA by up to 30% compared to Greedy.

This paper considers a cyber-physical system with a so-called “self-looping” node that repeats the inner-loop for physical situation awareness, i.e., more loops for more harsh physical situations. Regarding such a self-looping node, we observe the existence of physical errors that make the looping useless and eventually cause a critical failure. To prevent such a critical failure despite a physical error, this paper proposes a novel mechanism by introducing “time wall” and “safety backup”. The time wall limits the time budget for the self-looping node so as to switch to the safety backup while still meeting the deadline to prevent critical failure despite physical errors. Our experiments through both simulation and actual implementation show that the proposed mechanism gives a comparable accuracy with the existing methods in normal cases while completely preventing the critical failure in physical error cases.

A recent paper declares a ‘physical error’ to have occurred in an autonomous mobile CPS if it fails to pinpoint its location to within an acceptable degree of accuracy, and proposes an innovative approach for dealing with such physical errors without compromising safety properties. We further generalize the proposed approach to enhance its applicability to a wider range of conditions than is currently possible. We also show that some schedulability analysis that was derived in this recent paper for this approach is too optimistic, and present a fix to get rid of unwarranted optimism.

Scheduling algorithms are called “global” if they can migrate tasks between cores. Global scheduling algorithms are the de-facto standard practice for general purpose Operating Systems, to balance the workload between cores. However, the exact schedulability analysis of real-time applications for these algorithms is proven to be weakly NP-hard. Despite such a hardness, the research community keeps investigating the methods for an exact schedulability analysis for its relevance and to tightly estimate the execution requirements of real-time systems. Due to the NP-hardness, the available exact tests are very time and memory demanding even for sets of a few tasks. On another hand, the available sufficient tests are very pessimistic, despite consuming less resources. Motivated by these observations, we propose an exact schedulability test for constrained-deadline sporadic tasks under global multiprocessor fixed-priority scheduling scheduler, which is significantly faster and consumes less memory, compared to any other available exact test. To derive a faster test, we exploit the idea of a state-space pruning, aiming at reducing the number of feasible system states to be examined by the test. The resulted test is multiple orders of magnitude faster with respect to other state-of-the-art exact tests. Our C++ implementation is publicly available.

Targeting global EDF scheduling, this article proposes an optimal algorithm for parallelizing tasks with parallelization freedom. For this, we extend the interference-based sufficient schedulability analysis and derive monotonic increasing properties of both tolerance and interference for the schedulability. Leveraging those properties, we propose a one-way search–based optimal algorithm with polynomial time complexity. We present a formal proof of the optimality of the proposed algorithm. We first address the single-segment task model and then extend to the multi-segment task model. Our extensive experiments through both simulation and actual implementation show that our proposed approach can significantly improve the schedulability.

Real-time applications with high computational demand, e.g., autonomous driving, are emerging and their complex nature conforms to a DAG(directed acyclic graph) structure. We propose a conditionally optimal parallelization for real-time DAG tasks for global EDF, ensuring complete execution of all tasks within the deadline. To achieve this, we formalize a monotonic increasing property of both tolerance and interference to the parallelization option. Using such properties, we develop a unidirectional search algorithm that can assign parallelization options in polynomial time, which we formally prove the optimality. We observe significant improvement of schedulability through simulation experiment, and then in the following implementation experiment, we demonstrate that the algorithm is practically applicable for real-world use-cases.

Targeting global EDF scheduling, this paper proposes a conditionally optimal algorithm for parallelizing tasks with parallelization freedom. For this, we extend the interference-based sufficient schedulability analysis and derive monotonic increasing properties of both tolerance and interference for the schedulability. Leveraging those properties, we propose a one-way search based conditionally optimal algorithm with polynomial time complexity. Our extensive experiments through both simulation and actual implementation show that our proposed approach can significantly improve the schedulability up to 60 percent.

Recent parallel programming frameworks such as OpenCL and OpenMP allow us to enjoy the parallelization freedom for real-time tasks. The parallelization freedom creates the time versus density tradeoff problem in fluid scheduling, i.e., more parallelization reduces thread execution times but increases the density. By system-widely exercising this tradeoff, we propose optimal parameter tuning of real-time tasks aiming at maximizing the schedulability of multicore fluid scheduling. Our experimental study by both simulation and actual implementation shows that the proposed approach well balances the time and the density, and results in up to 80 percent improvement of the schedulability.

The current simulation tools used in the automotive industry do not correctly model timing behaviors of cyber-systems such as varying execution times and preemptions. Thus, they cannot correctly predict the real control performance. Motivated by this limitation, this paper proposes functionally and temporally correct simulation for the cyber-side of an automotive system. The key idea is to keep the data and time correctness only at physical interaction points and enjoy freedom of scheduling simulated jobs for all other cases. This way, the proposed approach significantly improves the real-time simulation capacity of the state-of-the-art simulation methods while keeping the functional and temporal correctness.

Past researches on multicore scheduling assume that a computational unit has already been parallelized into a prefixed number of threads. However, with recent technologies such as OpenCL, a computational unit can be parallelized in many different ways with runtime selectable numbers of threads. This paper proposes an optimal algorithm for parallelizing and scheduling a set of parallel tasks with multiple parallelization options on multiple CPU cores. The proposed algorithm is validated through both simulation and actual implementation. To the best of our knowledge, this is the first work addressing the problem of scheduling real-time tasks with multiple parallelization options on multiple CPU cores.

For advanced features of next generation vehicles, the real-time programs in automotive embedded systems are dramatically increasing. For such large volume program codes, this paper proposes a novel framework to use high-density and low-cost nonvolatile memory, i.e., NAND flash memory, as a low-cost means of storing and executing hard real-time programs. Regarding this, one challenge is that NAND flash memory allows only 2 KB page-based read operations not per-byte random accesses, which requires RAM as working storage for code executions. This paper proposes two solutions, i.e., partitioned RAM solution and shared RAM solution, that minimize the RAM size required to deterministically guarantee the deadlines of all the hard real-time tasks. The proposed solutions are verified with the actual real-time programs for unmanned autonomous driving. To the best of our knowledge, this is the first work that allows us to use NAND flash memory for hard real-time program executions with the minimal usage of RAM.

This paper proposes a novel technique called mRT-PLRU (Multitasking Real-Time constrained combination of Pinning and LRU), which forms a generic framework to use inexpensive nonvolatile NAND flash memory for storing and executing real-time programs in multitasking environments. In order to execute multiple real-time tasks stored in NAND flash memory with the minimal usage of expensive RAM, the mRT-PLRU is optimally configured in two steps. In the first step, the per-task analysis finds the function of RAM size versus execution time (and the corresponding optimal pinning/LRU combination) for each individual task. Using these functions for all the tasks as inputs, the second-step called a stochastic-analysis-in-loop optimization conducts an iterative convex optimization with the stochastic analysis for the probabilistic schedulability check. As a result, the optimization loop can optimally determine the RAM sizes for multiple tasks such that their deadlines are probabilistically guaranteed with the minimal size of total RAM. The usefulness of the developed technique is intensively verified through both simulation and actual implementation. Our experimental study shows that mRT-PLRU can save up to 80 percent of RAM required by the industry-common shadowing approach.

IEEE 802.15.4 is a global standard designed for emerging applications in low-rate wireless personal area networks (LR-WPANs). The standard provides nice features such as a beacon-enabled mode and guaranteed time slots for real-time data delivery. However, how to optimally operate those features is still an open issue. For the optimal operation of the features, this paper proposes a holistic optimization method that jointly optimizes three cross-related problems: (1) cluster-tree construction, (2) nodes' power configuration, and (3) duty-cycle scheduling. Our holistic optimization method finds the solution for the three problems such that all the real time packets can be delivered within their deadlines in the most energy-efficient way. Our simulation study shows that, comparing with existing methods, our holistic optimization can guarantee the on-time delivery of all real-time packets while significantly saving the energy and hence significantly increasing the network lifetime.

Emerging cyber-physical systems (CPSs) demand a new computing abstraction since the traditional ones have fundamental limitations in handling the para-functional also called physical requirements of CPSs such as timeliness, reliability, and evolvability. With the traditional computing abstractions such as processes, virtual memory, etc., multiple software (SW) components share hardware (HW) resources such as CPU and memory in a competitive manner causing unpredictable interferences in the para-functional properties. This problem becomes more serious along with the ever increasing scale and complexity of newly emerging cyber-physical systems. To fundamentally solve this problem, this paper proposes a HW resource componentizing approach that chops the capacity of a HW resource into smaller ones called HW components and dedicates a HW component to each SW component. With the dedicated HW component, each SW component can be guaranteed with the isolated para-functional properties regardless of surrounding SW components. This makes the system-wide issue of validating timeliness, reliability, and evolvability into the per-component validation issue. With this vision, this paper briefly presents a spatial/temporal-division scheduling algorithm that can be generally used for componentizing various HW resources including CPU, network, and RAM.

NAND flash memory has been widely used as a nonvolatile storage for storing data. However, it is challenging to execute program codes on NAND flash memory, since NAND flash memory only supports page-based reads, not byte-level random reads. This paper proposes an automated process to find the optimal paging strategy called RT-PLRU (Real-Time constrained combination of Pinning and LRU) that allows program codes stored in NAND flash memory to be executed satisfying real-time requirements with minimal usage of RAM. Moreover, the proposed process optimally configure the RT-PLRU in a developer-transparent way without giving any burden to the program developer. The developed technique is specifically applied to a media player program targeting a portable media player (PMP). To the best of our knowledge, this is the first effort to use NAND flash memory as a code storage for storing and executing real-time programs with minimal usage of RAM.

For advanced features of next generation vehicles, the real-time programs in automotive embedded systems are dramatically increasing. For such large volume program codes, this paper proposes a novel framework to use high-density and low-cost nonvolatile memory, i.e., NAND flash memory, as a low-cost mean of storing and executing hard real-time programs. Regarding this, one challenge is that NAND flash memory allows only 2KB page-based read operations not per-byte random access, which requires RAM as working storage for code executions. In order to minimize the expensive RAM requirements, the proposed framework optimally partitions the RAM for multiple hard real-time tasks and optimally determines the pinning/LRU combination for each RAM partition such that all task deadlines are deterministically guaranteed. The proposed framework is verified with the actual real-time programs for unmanned autonomous driving. To the best of our knowledge, this is the first work that allows us to use NAND flash memory for hard real-time program executions with the minimal usage of RAM.

As the software complexity drastically increases for multiresource real-time systems, industries have great needs for analytically validating real-time behaviors of their complex software systems. Possible candidates for such analytic validations are the end-to-end response time analysis techniques that can analytically find the worst-case response times of real-time transactions over multiple resources. The existing techniques, however, exhibit severe overestimation when real-time transactions visit the same resource multiple times, which we call a multiple visit problem. To address the problem, this paper proposes a novel analysis that completely changes its analysis viewpoint from classical per-job basis-aggregation of per-job response times-to per-resource basis-aggregation of per-resource total delays. Our experiments show that the proposed analysis can find significantly tighter bounds of end-to-end response times compared with the existing per-job-based analysis.

This paper proposes a novel technique called mRT-PLRU (multi-tasking real-time constrained combination of pinning and LRU), which forms a generic framework to use inexpensive nonvolatile NAND flash memory for storing and executing real-time programs in multi-tasking environments. In order to execute multiple real-time tasks stored in NAND flash memory with the minimal usage of expensive RAM, the mRT-PLRU is optimally configured in two steps. In the first step, the per-task analysis finds the function of RAM size vs. execution time for each individual task. Using these functions for all the tasks as inputs, the second-step called a stochastic-analysis-in-loop optimization conducts an iterative convex optimization with the stochastic-analysis for the probabilistic schedulability check. As a result, the optimization loop can optimally allocate RAM to multiple tasks such that their deadlines are probabilistically guaranteed with the minimal usage of RAM. Moreover, the mRT-PLRU is optimally configured in a developer-transparent way without giving any burden to the program developer, which is essential for the embedded system industry under a high pressure of time-to-market. The usefulness of the developed technique is intensively verified through both simulation and actual implementation. Our experimental study shows that mRT-PLRU can save up to 80% of RAM required by the industry-common shadowing approach.

This paper proposes a safe stochastic analysis for fixed-priority scheduling, which is applicable to a broader spectrum of periodic tasks than the ones analyzable by any of the existing techniques. The proposed analysis can find a safe upper-bound of deadline miss probability for periodic tasks with (1) arbitrary execution time distributions, (2) varying interrelease times with the period as the minimum, and (3) the maximum utilization factor Umaxthat can be greater than 1. One challenge for this is that the release times of tasks are not known a priori because we are not limiting the interrelease times of each task to a constant, i.e., the period. In such a situation, the relative phases of task instances at run time can be arbitrary. Thus, we need to consider all possible phase combinations among jobs to find the worst case deadline miss probability, which is not tractable. To handle this difficulty, we first derive the worst case phase combination for harmonic task sets. Then, we present a safe way to transform a nonharmonic task set to a harmonic task set such that the deadline miss probabilities obtained with the worst case phase combination for the transformed harmonic task set are guaranteed to be worse than those for the original nonharmonic task set with all possible phase combinations. Therefore, the worst case deadline miss probabilities of the transformed harmonic tasks can be used as safe upper-bounds of deadline miss probabilities of the original nonharmonic tasks. Through experiments, we show that the safe upper-bound computed by the proposed analysis is tight enough for practical uses.

NAND flash memory has been widely used as a non-volatile storage for storing data. However, it requires a large amount of SRAM for executing program codes stored in it since it only supports page-based reads, not byte-level random reads. This paper proposes a new paging mechanism called RT-PLRU (real-time constrained combination of pinning and LRU) that allows program codes stored in NAND flash memory to be executed satisfying real-time requirements with minimal usage of SRAM. Moreover, the RT-PLRU is optimally configured in a developer-transparent way without giving any burden to the program developer. The developed technique is specifically applied to a media player program targeting a PMP (portable medial player). To the best of our knowledge, this is the first effort to use NAND flash memory as a code storage for storing and executing real-time programs with minimal usage of SRAM.

As the elderly population increases, elderly care using inexpensive technological means is becoming critical. This paper presents our prototype system that provides real-time indoor tracking of elderly residents and their belongings, which is essential to assisting and securing their independent living. For high-fidelity real-time tracking, we propose novel scheduling algorithms. Our scheduling algorithms are designed by harmonizing both sensing and communication signals and leveraging location awareness and mobility consciousness in order to improve tracking accuracy while reducing the energy consumption. We performed extensive experiments through both simulation and actual implementation. Our experimental result says that our scheduling algorithms can provide real-time tracking of residents within a 20 cm error bound in the typical range of human mobility.

Reducing energy consumption is important for mobile embedded systems and one of its solutions is dynamic voltage scaling (DVS). In this paper, we examine how to achieve further energy saving for periodic real-time tasks with non-preemptible sections on EDF algorithm by using DVS. Previous algorithms use two speed levels to deal with run-time blocking situation. However, this paper proposes a multi-speed algorithm that exploits various speed levels depending on specific blocking situation to minimize energy consumption. Moreover, it also presents an enhanced multi-speed algorithm that further reduces the energy dissipation by dropping the speed level early and considering only remaining blocking time to compute a lower speed. We induced feasibility conditions for our algorithms and proved them. The experiments show that proposed algorithms achieve up to 70.8% energy saving compared to previous algorithms.

Recent computing applications such as videoconferencing and grid computing run their tasks on distributed computing resources connected through networks. For such applications, knowledge of the network status such as delay, jitter, and available bandwidth can help them select proper network resources to meet the Quality-of-Service (QoS) requirements. Also, the applications can dynamically change the resource selection if the current selection is found to experience poor performance. For such purposes, Internet Service Providers (ISPs) have started to instrument their networks with Network Measurement Infrastructures (NMIs) that run active measurement tasks periodically and/or on demand. However, one problem that most network engineers have overlooked is the measurement conflict problem, which happens when multiple active measurement tasks inject probing packets into the same network segment at the same time, resulting in misleading reports of network performance due to their combined effects. This paper proposes enhanced Earliest Deadline First (EDF) algorithms that allow "Concurrent Executions" to orchestrate offline/online measurement jobs in a conflict-free manner. The simulation study shows that our measurement scheduling mechanism can improve the schedulable utilization of offline measurement tasks up to 300 percent and the response time of on-demand jobs up to 50 percent. Further, we implement and deploy our scheduling mechanism in a real working NMI for monitoring the Internet2 Abilene network. As a case study, we show the utility of our algorithms in the widely used Network Weather Service (NWS).

As the elderly population increases, the elderly care using inexpensive technological means becomes critical. This paper proposes novel scheduling algorithms for real-time indoor tracking of elderly residents, which is essential to assist and secure their independent living. Our scheduling algorithms are designed by harmonizing both sensing and communication signals and leveraging location-awareness and mobility-consciousness, in order to improve the tracking accuracy while reducing the energy consumption. We performed extensive experiments through both simulation and actual implementation. Our experimental result says that our scheduling algorithms can provide real-time tracking of residents within 20 cm error bound in the typical range of human mobility

This paper proposes novel techniques for scheduling radar dwells in phased array radar systems. In order to handle complex physical characteristics such as dwell interleaving, transmitting duty cycle constraint, and energy constraint, we propose a notion of schedulability envelope. The schedulability envelope designed offline hides the details of complex radar dwell scheduling and provides a simple measure for the schedulability check. Using the schedulability envelope, the proposed technique can efficiently perform the admission control for dynamic target tracking tasks. The simulation results show that the proposed approach can significantly improve the system utilization by taking advantage of dwell interleaving while guaranteeing the schedulability and physical constraints.

In this paper, we present a novel packet delivery mechanism called Multi-Path and Multi-SPEED Routing Protocol (MMSPEED) for probabilistic QoS guarantee in wireless sensor networks. The QoS provisioning is performed in two quality domains, namely, timeliness and reliability. Multiple QoS levels are provided in the timeliness domain by guaranteeing multiple packet delivery speed options. In the reliability domain, various reliability requirements are supported by probabilistic multipath forwarding. These mechanisms for QoS provisioning are realized in a localized way without global network information by employing localized geographic packet forwarding augmented with dynamic compensation, which compensates for local decision inaccuracies as a packet travels towards its destination. This way, MMSPEED can guarantee end-to-end requirements in a localized way, which is desirable for scalability and adaptability to large scale dynamic sensor networks. Simulation results show that MMSPEED provides QoS differentiation in both reliability and timeliness domains and, as a result, significantly improves the effective capacity of a sensor network in terms of number of flows that meet both reliability and timeliness requirements up to 50 percent (12 flows versus 18 flows).

Scheduling periodic tasks that allow some instances to be skipped produces spare capacity in the schedule. Only a fraction of this spare capacity is uniformly distributed and can easily be reclaimed for servicing aperiodic requests. The remaining fraction of the spare capacity is non-uniformly distributed, and no existing technique has been able to reclaim it. We present a method for improving the response times of aperiodic tasks by identifying the non-uniform holes in the schedule and adding these holes as extra capacity to the capacity queue of the CASH mechanism. The non-uniform holes can account for a significant portion of spare capacity, and reclaiming this capacity results in considerable improvements to aperiodic response times.

In this paper, we present a novel packet delivery mechanism called multi-path and multi-speed routing protocol (MMSPEED) for probabilistic QoS guarantee in wireless sensor networks. The QoS provisioning is performed in two quality domains, namely, timeliness and reliability. Multiple QoS levels are provided in the timeliness domain by guaranteeing multiple packet delivery speed options. In the reliability domain, various reliability requirements are supported by probabilistic multipath forwarding. All these for QoS provisioning are realized in a localized way without global network information by employing localized geographic packet forwarding augmented with dynamic compensation, which compensates the local decision inaccuracy as a packet travels towards its destination. This way, MMSPEED can guarantee end-to-end requirements in a localized way, which is desirable for scalability and adaptability to large scale dynamic sensor networks. Simulation results show that MMSPEED provides QoS differentiation in both reliability and timeliness domains and, as a result, significantly improves the effective capacity of a sensor network in terms of number of flows that meet both reliability and timeliness requirements.

This paper addresses the problem of operating parameter assignment to multiple real-time tasks in a phased array radar system. The objective is to maximize the resulting system utility while ensuring the schedulability of all tasks with the assigned operating parameters. For this, we propose a novel framework by integrating the existing resource management framework called QRAM (QoS-based resource allocation model) with the notion of schedulability envelope. The schedulability envelope designed offline hides the complex details of phased array antenna scheduling and provides a linear formula as its quantitative abstraction. This abstraction allows QRAM to find the optimal resource assignment without concerning the details of complex scheduling. Our experimental results show that the proposed framework can achieve significantly improved system utility compared to the existing techniques.

Building real-time applications on 802.11 wireless networks is challenging because the medium access protocol is distributed and nodes contend for the channel nondeterministically. So far all attempts at providing real-time services in 802.11 require restrictive traffic assumptions such as periodicity. In this paper we describe distributed admission control, a modification to 802.11 that, when used with distributed prioritization, provides real-time guarantees for aperiodic packets. We show that barring external errors such as interference on the channel or incorrect priority scheduling this protocol guarantees deadlines will be met.

Monitoring network status such as end-to-end delay, jitter, and available bandwidth is important to support QoS-sensitive applications and timely detection of network anomalies like denial of service attacks. For this purpose, Internet service providers (ISPs) have started to instrument their networks with network measurement infrastructures (NMIs) that periodically run active measurement tasks using measurement servers located at strategic points in their networks. However, one problem that most network engineers have overlooked is the measurement conflict problem. Since active measurement tasks actively inject test packets to collect measurements along network paths, running multiple active measurements at the same time over the same path could result in misleading reports of network performance. We call this phenomenon a measurement conflict. Our recent observation of such measurement conflict motivates us to form a measurement task scheduling problem of meeting periodicity requirements, where real-time scheduling algorithms can play a role. The scheduling problem, however, is not exactly same as any of the existing scheduling problems in the realtime literature, because the problem involves multiple measurement servers running multiple measurement tasks whose conflict dependency propagates along the chains of paths. For this problem, we propose to use an EDF (earliest deadline first) heuristic but allowing "concurrent executions" if possible, to construct an offline schedule for a given measurement task set. Also, we propose a novel mechanism to flexibly use the offline schedule for minimizing the response time of dynamic on-demand measurement jobs. Further, we implement and deploy our scheduling algorithms in a real working NMI for monitoring Internet 2 Abilene network.

This paper proposes a novel task model in which its physical and temporal parameters are specified as time-parameterized functions and their values are finally determined at the actual dispatch time. This model is clearly differentiated from the classical task model where parameters are fixed at the job release time. The new model better suits sensing tasks in tracking applications, since the sensor parameters such as field-of-view and measurement duration can be properly adjusted at the actual sensing time. The new model, however, creates the cyclic dependency between task parameters and scheduling behavior, that is, the task parameters depend on scheduling behavior and the latter in turn depends on the former. This cyclic dependency makes the schedulability check even more difficult. We handle this difficulty by iterative convergence and probabilistic schedulability envelope, which provides an efficient online schedulability check. The experimental study shows that the new model significantly improves the effective capacity of tracking systems without losing track accuracy

In recent studies, using mobile elements (MEs) as mechanical carriers of data has been shown to be an effective way of prolonging sensor network life time and relaying information in partitioned networks. As the data generation rates of sensors may vary, some sensors need to be visited more frequently than others. In this paper, a partitioning-based algorithm is presented that schedules the movements of MEs in a sensor network such that there is no data loss due to buffer overflow. Simulation results show that the proposed Partitioning Based Scheduling (PBS) algorithm performs well in terms of reducing the minimum required ME speed to prevent data loss, providing high predictability in inter-visit durations, and minimizing the data loss rate for the cases when the ME is constrained to move slower than the minimum required ME speed.

This paper describes a stochastic analysis framework which computes the response time distribution and the deadline miss probability of individual tasks, even for systems with a maximum utilization greater than one. The framework is uniformly applied to fixed-priority and dynamic-priority systems and can handle, tasks with arbitrary relative deadlines and execution time distributions.

This paper addresses the search and track coordination problems of multiple shipboard radars. The proposed approach first exploits the physical characteristics of a single phased array radar to improve its effective capacity. Its effective capacity is abstracted by a closed-form equation called a schedulability envelope. Using the schedulability envelope for each radar, we deal with search and track coordination as a relative-load-balancing problem in a multiresource environment. The simulation results show that the proposed approach significantly improves the overall capacity of a multiship multiradar system.

Timing constraints for radar tasks are usually specified in terms of the minimum and maximum temporal distance between successive radar dwells. We utilize the idea of feasible intervals for dealing with the temporal distance constraints. In order to increase the freedom that the scheduler can offer a high-level resource manager, we introduce a technique for nesting and interleaving dwells online while accounting for the energy constraint that radar systems need to satisfy. Further, in radar systems, the task set changes frequently and we advocate the use of finite horizon scheduling in order to avoid the pessimism that is inherent in schedulers that assume a task executes forever. We also develop the notion of modular schedule update which allows portions of a schedule to be altered without affecting the entire schedule, thereby simplifying the scheduler. Through extensive simulations, we validate our claims of providing greater scheduling flexibility without compromising on performance when compared with earlier work based on templates constructed offline.

In many practical real-time applications, there is a given set of task frequencies (i.e., inverse of task periods) corresponding to predetermined QoS options that the applications can choose. For example, in audio applications, the typical choices of playback frequencies are for CD quality, radio quality, and phone quality. Similar configurations can be found in streaming video and in control applications. In such systems, applications dynamically arrive requesting one of the periods provided by the QoS manager. Thus, the accurate and efficient online schedulability test is essential for any task set whose periods are chosen from the QoS period set. For this purpose, we propose new utilization bounds as a function of given QoS periods. As long as there is a set of given periods that can be chosen by applications, the bounds developed can be used by the QoS manager to quickly determine the schedulability of dynamic applications.

This paper proposes novel techniques for scheduling radar dwells in phased array radar systems. In order to handle complex physical characteristics such as dwell interleaving, transmitting duty cycle constraint, and energy constraint, we propose a notion of schedulability envelope. The schedulability envelope designed offline hides the details of complex radar dwell scheduling and provides a simple measure for the schedulability check. Using the schedulability envelope, the proposed technique can efficiently perform the admission control for dynamic target tracking tasks. The simulation results show that the proposed approach can significantly improve the system utilization by taking advantage of dwell interleaving while guaranteeing the schedulability and physical constraints.

This paper describes a stochastic analysis method for general periodic real-time systems. The proposed method accurately computes the response time distribution of each task in the system, thus making it possible to determine the deadline miss probability of individual tasks, even for systems with maximum utilization factor greater than one. The method uniformly covers both fixed-priority scheduling (such as rate monotonic) as well as dynamic-priority scheduling (such as earliest deadline first) and can handle arbitrary relative deadlines and execution time distributions. The accuracy of the method is proven by comparing the results from the analysis with those obtained from simulations, as well as other methodologies in the literature.

Many application level qualities are functions of available computation resources. Recent studies have handled the computation resource allocation problem to maximize the overall application quality. However such QoS problem is fundamentally a multi-dimensional optimization problem that requires extensive computation. Therefore, online usage of optimization procedures may significantly reduce the computation resource available for applications. This raises the question of how to best use the optimization procedures for dynamic real-time task sets. This paper proposes a method called service classes configuration to address the QoS problem with dynamic arrival and departure of tasks. A simplified radar application is used as an illustrative example.

Cache memory is used in almost all computer systems today to bridge the ever increasing speed gap between the processor and main memory. However, its use in multitasking computer systems introduces additional preemption delay due to the reloading of memory blocks that are replaced during preemption. This cache-related preemption delay poses a serious problem in realtime computing systems where predictability is of utmost importance. We propose an enhanced technique for analyzing and thus bounding the cache-related preemption delay in fixed-priority preemptive scheduling focusing on instruction caching. The proposed technique improves upon previous techniques in two important ways. First, the technique takes into account the relationship between a preempted task and the set of tasks that execute during the preemption when calculating the cache-related preemption delay. Second, the technique considers the phasing of tasks to eliminate many infeasible task interactions. These two features are expressed as constraints of a linear programming problem whose solution gives a guaranteed upper bound on the cache-related preemption delay. This paper also compares the proposed technique with previous techniques using randomly generated task sets. The results show that the improvement on the worst-case response time prediction by the proposed technique over previous techniques ranges between 5 percent and 18 percent depending on the cache refill time when the task set utilization is 0.6. The results also show that as the cache refill time increases, the improvement increases, which indicates that accurate prediction of cache-related preemption delay by the proposed technique becomes increasingly important if the current trend of widening speed gap between the processor and main memory continues.

We propose a technique for analyzing cache-related preemption delays of tasks that cause unpredictable variation in task execution time in the context of fixed-priority preemptive scheduling. The proposed technique consists of two steps. The first step performs a per-task analysis to estimate cache-related preemption cost for each execution point in a given task. The second step computes the worst case response time of each task that includes the cache-related preemption delay using a response time equation and a linear programming technique. This step takes as its input the preemption cost information of tasks obtained in the first step. This paper also compares the proposed approach with previous approaches. The results show that the proposed approach gives a prediction of the worst case cache-related preemption delay that is up to 60 percent tighter than those obtained from the previous approaches.

We propose an enhanced technique for analyzing, and thus bounding cache related preemption delay in fixed priority preemptive scheduling focusing on instruction caching. The proposed technique improves upon previous techniques in two important ways. First, the technique takes into account the relationship between a preempted task and the set of tasks that execute during the preemption when calculating the cache related preemption delay. Second, the technique considers phasing of tasks to eliminate many infeasible task interactions. These two features are expressed as constraints of a linear programming problem whose solution gives a guaranteed upper bound on the cache related preemption delay. The paper also compares the proposed technique with previous techniques. The results show that the proposed technique gives up to 60% tighter prediction of the worst case response time than the previous techniques.

We propose a technique for analyzing cache-related preemption delays of tasks that cause unpredictable variation in task execution time in the context of fixed-priority preemptive scheduling. The proposed technique consists of two steps. The first step performs a per-task analysis to estimate cache-related preemption cost for each execution point in a given task from the number of useful cache blocks at the execution point. The second step computes the worst case response time of each task using a response time equation and a linear programming technique which takes as its input the preemption cost information of tasks obtained in the first step. Our experimental results show that the proposed technique gives a prediction of the worst case cache-related preemption delay that is up to 60% tighter than that obtained from previous approaches.