Fog computing is a distributed computing paradigm that brings data processing from remote cloud data centers into the vicinity of the edge of the network. The computation is performed closer to the source of the data, and thus it decreases the time unpredictability of cloud computing that stems from (i) the computation in shared multi-tenant remote data centers, and (ii) long distance data transfers between the source of the data and the data centers. The computation in fog computing provides fast response times and enables latency sensitive applications. However, industrial systems require time-bounded response times, also denoted as RT. The correctness of such systems depends not only on the logical results of the computations but also on the physical time instant at which these results are produced. Time-bounded responses in fog computing are attributed to two main aspects: computation and communication.    In this thesis, we explore both aspects targeting soft RT applications in fog computing in which the usefulness of the produced computational results degrades with real-time requirements violations. With regards to the computation, we provide a systematic literature survey on a novel lightweight RT container-based virtualization that ensures spatial and temporal isolation of co-located applications. Subsequently, we utilize a mechanism enabling RT container-based virtualization and propose a solution for orchestrating RT containers in a distributed environment. Concerning the communication aspect, we propose a solution for a dynamic bandwidth distribution in virtualized networks.

In modern processor architectures, caches are widely used to shorten the gap between the processor speed and memory access time. However, caches are time unpredictable, especially the shared L2 cache used by different cores on multicore processors. Thus, it can significantly increase the complexity of worst-case execution time (WCET) analysis, which is crucial for real-time systems. This dissertation designs several time-predictable scratchpad memory (SPM) based architectures for both VLIW (Very Long InstructionWord) based single-core and multicore processors. First, this dissertation proposes a time predictable two-level SPM based architecture for VLIW based single-core processors, and an ILP (Integer Linear Programming) based static memory objects allocation algorithm is extended to support the multi-level SPMs without harming the time predictability of SPMs. Second, several SPM based architectures for VLIW based multicore processors are designed. To support these architectures, the dynamic memory objects allocation based partition, the static memory objects allocation based partition and the static memory objects allocation based priority L2 SPM strategy are proposed, which retain the characteristic of time predictability. Also, both the WCET and worst-case energy consumption (WCEC) of our SPM based single-core and multicore architectures are completely evaluated in this dissertation. Last, to exploit the load/store latencies that are statically known in this architecture, we study a SPM-aware scheduling method to improve the performance. Our experimental results indicate the strengths and weaknesses of each proposed architecture and allocation method, which offers interesting memory design options to enable real-time computing. The strength of the two-level architecture is its superior performance compared to the one-level architecture, while the strength of the one-level architecture is its simple implementation. Also, the two-level architecture with separated L1 SPM for each core better fits for the data-intensive real-time applications, which not only retains good performance but also achieves a higher bandwidth by accessing both instruction and data SPM at the same time. Compared to the static based strategies, the dynamic allocation based partition L2 SPM strategy offers the better performance on each core because of the reuse of SPM space at the run-time, but has much higher complexity. In addition, the experimental results show that the timing and energy performance of our proposed SPM based architectures are superior to the similar cache based and hybrid architectures. Meanwhile, our architectures can ensure time predictability which is desirable for the real-time systems.

<p>Distributed real-time systems are notoriously difficult to correctly design and construct [Pam as 1985]. The fundamental principles of concurrency, deadline driven scheduling, and reaction to external stimuli which underlie such systems are inherently complex. This difficulty is further exacerbated when applications based on these principles are distributed over a network. Academic instruction in this domain is challenging: while theoretical issues can be taught with traditional "pencil and paper" techniques, real-time programming skills require experience that can be best provided by a laboratory. To this end, the Computer Science Department at Virginia Tech created and built a laboratory, known as the Reactive Systems Laboratory (RSL), specifically designed to provide these practical experiences. This paper documents the decisions, designs, and equipment used to build this laboratory. Additionally, the low-level software systems required to operate the RSL are discussed. Finally, future directions for the laboratory are considered and some conclusions are drawn based on usage to-date.</p> / Master of Science

Indiana University-Purdue University Indianapolis (IUPUI) / This thesis demonstrates a novel idea on how components in a distributed real-time & embedded (DRE) system can choose from different data interchange formats at run-time. It also quantitatively evaluates three binary data interchange protocols used in distributed real-time & embedded (DRE) systems: the Common Data Representation (CDR), which collects data "as-is" into a buffer; Binary JSON (BSON), which enables "on the fly" discovery of elements in a message; and FIX Adapted for Streaming (FAST), which is a binary compression algorithm popularly used for data exchange in financial stock market domain. We compare these three data exchange formats to determine if it is possible to minimize the data usage without compromising CPU processing times, data throughput, and data latency. The lack of such a study has made protocols such as CDR popular based on the assumption that collecting data "as-is" will consume less processing time and send with high throughput. We perform the study in the context of an Open Source Architecture for Software Instrumentation of Systems (OASIS). To perform our study, we modified its existing data interchange framework to flexibly and seamlessly integrate either format, and let the components choose a format at run-time. The experiments from our study shows that as data size increases, the throughput of CDR, BSON, and FAST decreases by 96.16%, 97.23%, and 84.41%, respectively. The increase in packaging and un-packaging times are 1985.12% and 1642.28% for FAST, compared to 3158.96% and 2312.50% for CDR, and 5077.98% and 3686.48% for BSON.

<p> Many safety-critical software applications are hard real-time systems. They have stringent timing requirements that have to be met. We present descriptions of timing behaviors that include precise definitions as well as analysis of how functional timing requirements (FTRs) interact with performance timing requirements (PTRs), and how these concepts can be used by software designers. The definitions explicitly show how to specify timing requirements with tolerances on time durations. </p> <p> This thesis shows the importance of specifying both FTRs and PTRs, by revealing the fact that their interaction directly determines the final implementability of real-time systems. By studying this interaction under three environmental assumptions, we find that the implementability results of the timing properties are different in each environment, but they are closely related. The results allow us to predict the system's implementability without developing or verifying the actual implementation. This also shows that we can sometimes significantly reduce the sampling frequency on the target platform, and still implement the timing requirement correctly. </p> <p> We present a component-based approach to formalizing common timing requirements and provide a pre-verified implementation of one of these requirements. The verification is performed using the theorem proving tool PVS. This allows domain experts to specify the tolerance in each individual timing requirement precisely. The pre-verified implementation of a timing requirement is demonstrated by applying the method in two examples. These examples show that both the design and verification effort are reduced significantly using a pre-verified template. </p> <p> A primary focus of this thesis is on how to include tolerances on timing durations in the specification, implementation and verification of timing behaviors in hard real-time applications. </p> / Thesis / Doctor of Philosophy (PhD)

No description available.

No description available.

Utility Accrual (UA) scheduling is a method of dynamic real-time scheduling that is designed to respond to overload conditions by producing a feasible schedule that heuristically maximizes a pre-defined metric of utility. Whereas utility accrual schedulers have traditionally focused on CPU overload, this dissertation explores memory overload conditions during which the aggregate memory demand exceeds a system's available memory bandwidth. Real-time systems are typically implemented in C or other languages that use explicit dynamic memory management. Taking advantage of modern type-safe languages, such as Java, necessitates the use of garbage collection (GC). The timeliness requirements of real-time systems, however, impose specific demands on the garbage collector. Garbage collection introduces a significant source of unpredictability in the execution timeline of a task because it unexpectedly interjects pauses of arbitrary length, at arbitrary points in time, with an arbitrary frequency. To construct a feasible schedule, a real-time scheduler must have the ability to predict the collector's activities and plan for them accordingly. We have devised CADUS (Collector-Aware Dynamic Utility Scheduler), a utility accrual algorithm that tightly links CPU scheduling with the memory requirements -and the corresponding garbage collection activities - of real-time tasks. By constructing and storing memory time allocation profiles, we address the problem of GC activation strategy. We estimate GC latency by using a real-time collector and modeling its behavior. We project GC frequency by planning, at schedule construction time, the memory bandwidth available to the collector. CADUS can point the collector's activities to any specific task in the system. The runtime system provides this ability by maintaining separate logical heaps for all tasks. We demonstrate the viability of CADUS through extensive simulation studies. We evaluated the behavior of CADUS under a wide range of CPU and memory load conditions and utility distributions. We compared its performance against an existing GC-unaware UA scheduler and found that CADUS consistently outperformed its GC-unaware counterpart. We investigated and identified the reasons for the superior performance of CADUS and quantified our results. Most significantly, we found that in an overloaded dynamic soft real-time system, a scheduler's preemption decisions have a highly significant impact on GC latency. A dynamic real-time scheduler therefore must predict the impact of its preemption decisions on GC latency in order to construct time-feasible schedules. / Ph. D.

While increasing number of vehicles on urban roadways create uncontrolled congestion, connectivity among vehicles, traffic lights and other road-side units provide abundant data that paves avenues for novel smart traffic control mechanisms to mitigate traffic congestion and delays. However, increasingly complex vehicular applications have outpaced the computational capabilities of on-board processing units, therefore requiring novel offloading schemes onto additional resources located by the road-side. Adding connectivity and other computational resources on legacy traffic infrastructure may also introduce security vulnerabilities. To ensure that the timeliness and resource constraints of the vehicles using the roadways as well as the applications being deployed on the traffic infrastructure are met, the transportation systems needs to be more predictable. This dissertation discusses three areas that focus on improving the predictability and performance of the connected traffic infrastructure. Firstly, a holistic traffic control strategy is presented that ensures predictable traffic flow by minimizing traffic delays, accounting for unexpected traffic conditions and ensuring timely emergency vehicle traversal through an urban road network. Secondly, a vehicular edge resource management strategy is discussed that incorporates connected traffic lights data to meet timeliness requirements of the vehicular applications. Finally, security vulnerabilities in existing traffic controllers are studied and countermeasures are provided to ensure predictable traffic flow while thwarting attacks on the traffic infrastructure. / Doctor of Philosophy / Exponentially increasing vehicles especially in urban areas create pollution, delays and uncontrolled traffic congestion. However, improved traffic infrastructure brings connectivity among the vehicles, traffic lights, road-side detectors and other equipment, which can be leveraged to design new and advanced traffic control techniques. The initial work in this dissertation provides a traffic control technique that (i) reduces traffic wait times for the vehicles in urban areas, (ii) ensures safe and quick movements of emergency vehicles even through crowded areas, and (iii) ensures that the traffic keeps moving even under unexpected lane closures or roadblocks. As technology advances, connected vehicles are becoming increasingly automated. This allows the car manufacturers to design novel in-vehicle features where the passengers can now stream media-rich content, play augmented reality (AR)-based games and/or get high definition information about the surroundings on their car's display, while the car is driven through the urban traffic. This is made possible by providing additional computing resources along the road-side that the vehicles can utilize wirelessly to ensure passenger's comfort and improved experience of in-vehicle features. In this dissertation, a technique is provided to manage the computational resources which will allow vehicles (and its passengers) to use multiple features simultaneously. As the traffic infrastructure becomes increasingly inter-connected, it also allows malicious actors to exploit vulnerabilities such as modifying traffic lights, interfering with road-side sensors, etc. This can lead to increased traffic wait times and eventually bring down the traffic network. In the final work, one such vulnerability in traffic infrastructure is studied and mitigating measures are provided so that the traffic keeps moving even when an attack is detected. In all, this dissertation aims to improve safety, security and overall experience of the drivers, passengers and the pedestrians using the connected traffic infrastructure.

Real-time channels are established between a source and a destination to guarantee in-time delivery of real-time messages in multi-hop networks. In this thesis, we propose two schemes to establish real-time channels for soft real-time applications whose timeliness properties are characterized using Jensen's Time Utility Functions (TUFs) that are non-increasing. The two algorithms are (1) Localized Decision for Utility accrual Channel Establishment (LocDUCE) and (2) Global Decision for Utility accrual Channel Establishment (GloDUCE). Since finding a feasible path optimizing multiple constraints is an NP-Complete problem, these schemes heuristically attempt to maximize the system-wide accrued utility. The channel establishment algorithms assume the existence of a utility-aware packet scheduling algorithm at the interfaces. The route selection is based on delay estimation performed at the source, destination, and all routers in the path, from source to destination. We simulate the algorithms, measure and compare their performance with open shortest path first (OSPF). Our simulation experiments show that for most of the cases considered LocDUCE and GloDUCE perform better than OSPF. We also implement the schemes in a proof-of-concept style routing module and measure the performance of the schemes and compare them to OSPF. Our experiments on the implementation follow the same trend as the simulation study and show that LocDUCE and GloDUCE have a distinct advantage over OSPF and accrue higher system-wide utility. These schemes also react better to variation in the loading of the links. Among the two proposed approaches, we observe that GloDUCE performs better than LocDUCE under conditions of increased downstream link loads. / Master of Science