Serverless computing has become more popular and evolved to support more complex tasks than the original Function as a Service (FaaS) model. The design of serverless systems has advanced to accommodate application demands and offer flexibility. Careful characterization of modern serverless systems and understanding of current gaps are warranted. Publicly available datasets on workloads in select production serverless systems do not fully represent all offerings or capture traces at the required time resolution to identify changes in application-level request-response patterns.

Safety-critical domains, such as healthcare and autonomous vehicles, employ machine learning (ML), where mis-predictions can cause severe repercussions. Training datasets may contain faults, thereby compromising ML accuracy. Ensembles, where multiple ML models vote on predictions, are effective at maintaining predictive capability, and thus resilient against faulty training data because individual models focus on diverse input features. Nevertheless, ensemble diversity varies per input. Hence, weighted ensembles can bolster resilience by assigning unique weights to constituent models. While existing weighted ensembles focus on output-space diversity, we propose leveraging their feature-space diversity to better capture model independence and achieve greater resilience. Therefore, we present ReMlX, which applies explainable artificial intelligence to extract the feature-space diversity of ensemble models, and adjusts their weights to maximize resilience. Compared to its most competitive baseline, ReMlX is 12% more resilient but 15% slower than dynamic weighted ensembles based on stacking.

We consider uniprocessor job scheduling where jobs have deadlines and each job belongs to a job family. Each job family has an associated setup time or cold start delay, and when a job is scheduled, if the predecessor job does not belong to the same job family then this setup time needs to be included. We examine the scheduling problem when the objective is to minimize the number of tardy jobs, and the challenge of including the setup time for switching between job families results in poor performance of well-known policies such as earliest deadline first (EDF). We propose a near-optimal online scheduling policy for jobs with deadlines, on uniprocessor platforms. This problem arises in a variety of contexts including serverless computing and MLaaS (machine learning as a service) where a job request may need a suitable resource container to be provisioned if an earlier request was not of the same type. The general offline problem of job scheduling with job families and setup costs has previously been studied and shown to be NP-Hard. In an effort to improve our understanding of the online problem with the objective of maximizing the number of jobs that meet their deadlines, we focus on the case where all jobs have the same execution time. We show that even this special case is NP-Hard in the offline setting. The policy we propose, which requires job buffering, is nearly 1-competitive when each job has a reasonably large slack. We also propose a heuristic that performs well in many situations despite a weak competitive ratio.

From increasing rates of e-waste production to astonishing datacenter carbon emissions, the ecological effects of computing are staggering. Computer engineering and computer science students need to understand the social and environmental context of their work, and to develop practical skills required to build more sustainable solutions. Learning sustainable development skills is challenging in a traditional university classroom: meaningfully building these skills and mindsets requires holistic, student-centered approaches, including situative, experiential, and community-centered strategies. While educators and universities have begun to integrate sustainability into curricula, we propose another approach, building a community of learning through collaboration with students and the wider community. The eKitchen is a university-based community of practice, whose purpose is to give students opportunities to develop hands-on skills in electronic repair and sustainable computer engineering, reduce e-waste on campus, and advocate for sustainable computing through public outreach, workshops and community partnerships.

Addressing the global e-waste crisis and reducing the carbon produced during operation, and equally, manufacturing, of consumer and datacenter electronics necessitates not only incremental technical improvements, but more broadly, a paradigm shift towards slower and more sustainable computing practices. To contend with these issues, both computer engineers and the general public need a better understanding of how their personal use of computers and their work relate to their social and environmental contexts. We argue that teaching electronic and computer repair is a great place to begin these conversations, by giving students the opportunity to develop practical hands-on skills through experiential, situative learning, and then linking these concrete experiences to more abstract discussions of sustainable computing. We have developed and run a year long course for university students, and workshops aimed at K12 students, both of which center around teaching sustainable computing and hands-on skills through electronic and computer repair. We designed and evaluated this course material based on surveys and interviews with students, repair experts, and community members. In this poster, we present our curricula and course materials and explain the pedagogical theory and research that underpin our approach, as well as how we adapted our work for different student groups and course formats. We enumerate challenges that we encountered while implementing these lessons, and provide recommendations for other educators interested in teaching repair courses or workshops.

Today’s Internet of Things (IoT) devices can colocate multiple applications on a platform with hardware resource sharing. Such colocations allow for increasing the throughput of contemporary IoT applications, similar to the use of multi-tenancy in clouds. However, avoiding performance interference among colocated applications through virtualized performance isolation is expensive in IoT platforms due to resource limitations. Hence, on the one hand, colocated IoT applications without performance isolation contend for shared limited resources, which makes their performance variance discontinuous and a priori unknown. On the other hand, different combinations of colocated applications make the overall state space exceedingly large. All of these make such colocated routines challenging to predict, making it difficult to plan which applications to colocate on which platform. We propose Co - Approximator , a technique for systematically sampling an exponentially large colocated application state space and efficiently approximating it from only four available complete colocation samples. We demonstrate the performance of Co - Approximator with 17 standard benchmarks and three pipelined data processing applications on different IoT platforms, where on average, Co - Approximator reduces existing techniques’ approximation error from 61% to just 7%.

Application developers often need to employ a combination of software such as communication middleware and cloud-based services to deal with the challenges of heterogeneity and network dynamism in the edge-to-cloud continuum. Consequently, developers write extra glue code peripheral to the application's core business logic, to provide interoperability between interacting software frameworks. Each software framework comes with its own framework-specific API, and as technology evolves, the developer must keep up with the changing APIs by updating the glue code in their application. Thus, framework-specific APIs hinder interoperability and cause technology fragmentation. We propose a design of a middleware-based distributed operating system (OS) called OneOS to realize a computing paradigm that alleviates such interoperability challenges. OneOS provides a single system image of the distributed computing platform, and transparently provides interoperability between software components through the standard POSIX API. Using OneOS's domain-specific language, users can compose complex distributed applications from legacy POSIX programs. OneOS tolerates failures by adopting a distributed checkpoint-restore algorithm. We evaluate the performance of OneOS against an open-source IoT Platform, ThingsJS, using an IoT stream processing benchmark suite, and a video processing application. OneOS executes the programs about 3x faster than ThingsJS, reduces the code size by about 22%, and recovers the state of failed applications within 1 second upon detecting their failure.

Machine learning (ML) is applied in many safety-critical domains such as autonomous driving and medical diagnosis. Many ML applications in such domains require object detection, which includes both classification and localization, to provide additional context. To ensure high accuracy, state-of-the-art object detection (OD) systems require large quantities of correctly annotated images for training. However, creating such datasets is non-trivial, may involve significant human effort, and is hence inevitably prone to annotation faults. We evaluate the effect of such faults on OD applications. We present ODFI, which can inject five different types of common annotation faults into any COCO-formatted dataset. We then use ODFI to inject these faults into two road traffic and one medical X-ray imaging datasets. Finally, using these faulty datasets, we systematically evaluate and compare the efficacy of existing OD techniques that are designed to be robust against such faults. To do so, we introduce a new metric that evaluates the robustness of OD models in the presence of faults. We find that (1) single-stage detectors trained with faulty annotations perform better in scenes with more objects, (2) redundant bounding boxes have the least impact on robustness, and (3) ensembles have the highest overall robustness among the robust OD techniques considered.

How should we build applications for large-scale networked embedded systems -- now in the incarnation of the Internet of Things -- when we do not want to rely on the existence of a persistent connection to a remote data center? We present the design and implementation of a system, which we call Djenne, that can aggregate the computational power of the distributed devices because the increased capacity of these devices does allow for substantial work closer to the devices. The challenge that we overcome with Djenne is dependability: how can we cope with failures and the dynamics of wireless network links in such systems? Our design uses the actor model of computation and relies on replicated services to improve reliability and to create opportunities for parallelism that increase task throughput. The key innovations in our work are the use of adaptive mechanisms for rerouting data when system conditions change significantly as well as a holistic recovery approach when computations need to be repeated in the distributed system. Via experimental evaluation, we find that Djenne can improve throughput by 30% to 190% for different use cases while ensuring resilience in the face of intermittent failures.

Machine learning (ML) has been adopted in many safety-critical applications like automated driving and medical diagnosis. Incorrect decisions by ML models can lead to catastrophic consequences, such as vehicle crashes and inappropriate medical procedures, thereby endangering our lives. The correct behaviour of a ML model is contingent upon the availability of well-labelled training data. However, obtaining large and high-quality training datasets for safety-critical applications is difficult, often resulting in the use of faulty training data.We compare the efficacy of five different error mitigation techniques, derived from a survey of more than 200 related articles, which are designed to tolerate noisy/faulty training data. We experimentally find that the error mitigation capabilities of these techniques vary across datasets, ML models, and different kinds of faults. We further find that ensemble learning offers the highest resilience among all the techniques across different configurations, followed by label smoothing.

The need to understand job scheduling on devices with intermittent availability is of significant interest today because of the use of battery-powered devices - including electric vehicles - that rely on recharging intervals or energy harvesting. In some recent work by Islam and Nirjon, effective heuristics were proposed for scheduling recurring tasks with deadlines on such intermittently available devices. The broader computational complexity of job scheduling has not been explored in this setting where there is a relationship between job durations and energy consumption. We provide a richer understanding of this problem space. We consider two recharging approaches, one where the battery has to be fully charged during a recharging interval (sometimes considered better for extending battery lifetime) and another where the battery can be partially charged, and we study different scheduling objectives: minimizing the sum of completion times, minimizing the maximum tardiness, and minimizing the number of tardy jobs. We also consider four different relationships between job duration and energy consumption: (i) energy consumption is equal for all jobs irrespective of job length; (ii) job length is equal for all jobs irrespective of energy consumption; (iii) energy consumption is directly proportional to job length; and (iv) there is an arbitrary relationship between job length and energy consumption. In effect, we consider 24 different scheduling problems, and establish that most problems subject to a complete recharging requirement are NP-Hard but that most problems can be solved in polynomial time when partial recharging is permitted. Interestingly, we have been unable to resolve the computational complexity for the one case of minimizing the sum of completion times subject to partial recharging.

Machine learning is becoming more prevalent in safety-critical systems like autonomous vehicles and medical imaging. Faulty training data, where data is either misla-belled, missing, or duplicated, can increase the chance of misclassification, resulting in serious consequences. In this paper, we evaluate the resilience of ML ensembles against faulty training data, in order to understand how to build better ensembles. To support our evaluation, we develop a fault injection framework to systematically mutate training data, and introduce two diversity metrics that capture the distribution and entropy of predicted labels. Our experiments find that ensemble learning is more resilient than any individual model and that high accuracy neural networks are not necessarily more resilient to faulty training data. Further, we find that simple majority voting suffices in most cases for resilience in ML ensembles. Finally, we observe diminishing returns for resilience as we increase the number of models in an ensemble. These findings can help machine learning developers build ensembles that are both more resilient and more efficient.

We propose redundancy-based execution models to address the reliability and correctness of safety/time-critical applications, and in particular, mixed-criticality systems. In our models, every job has one or more (possibly identical) versions, and all versions of a job are to run isochronously on multiple parallel machines in a lockstep fashion. The redundant machines act as monitoring coprocessors, and the execution of a job is deemed successful as soon as one of its versions completes within its worst-case execution time estimate, at which point we may terminate all the other versions. Doing so e ectively increases the chance that a job completes successfully and thus provides timing guarantees in the form of increased predictability. We present several allocation and scheduling problems with varying levels of generality, with the objective of minimizing the maximum makespan across all processors.

Reliable, secure, private, and fast communication in vehicular networks is extremely challenging due to the highly mobile nature of these networks. Contact time between vehicles is very limited and topology is constantly changing. Trusted communication in vehicular networks is of crucial importance because without trust, all efforts for minimizing the delay or maximizing the reliability could be voided. In this paper, we propose a trust-based framework for a safe and reliable information dissemination in vehicular networks. The proposed framework consists of two modules such that the first one applies three security checks to make sure the message is trusted. It assigns a trust value to each road segment and one to each neighborhood, instead of each car. Thus, it scales up easily and is completely distributed. Once a message is evaluated and considered to be trustworthy, our method then in the second module looks for a safe path through which the message is forwarded. Our frameworks are application-centric; in particular, it is capable of preserving traffic requirements specified by each application. Experimental results demonstrate that this framework outperforms other well-known routing protocols since it routes the messages via trusted vehicles.

Extreme complimentary metal-oxide-semiconductor (CMOS) technology scaling is causing significant concerns in the reliability of computer systems. Intermittent hardware errors are non-deterministic bursts of errors that occur in the same physical location. Recent studies have found that 40% of the processor failures in real-world machines are due to intermittent hardware errors. A study of the effects of intermittent faults on programs is a critical step in building fault-tolerance techniques of reasonable accuracy and cost. In this work, we characterize the impact of intermittent hardware faults in programs using fault-injection campaigns in a microarchitectural processor simulator. We find that 80% of the non-benign intermittent hardware errors activate a hardware trap in the processor, and the remaining 20% cause silent data corruptions. We have also investigated the possibility of using the program state at failure time in software-based diagnosis techniques, and found that much of the erroneous data are intact and can be used to identify the source of the error.

Many mobile devices e.g., smart phones, PDAs, portable computers and wireless routers e.g., WiFi access points nowadays are equipped with ad hoc transmission mode. In a dense environment such as a college/office campus, this creates the possibility of forming a wireless mesh network WMN in which mobile users communicate with each other through multiple wireless hops. This allows mobile users to exchange share files over the free access WMN rather than a carrier frequency such as 3G and WiMax. We consider a peer-to-peer P2P content sharing setting in a WMN, wherein the mesh network operator over-provision a number of mesh routers in the network with additional storage capacity and P2P-aware devices that are programmed to cache and store P2P content. Those mesh routers act as caches and participants in P2P content sharing. The aim of this setting is to both reduce the cost of communications between peers within the WMN i.e., reduce bandwidth and energy that P2P traffic consumes in the network, and enhance the performance of P2P content sharing i.e., reduce the average P2P content download delay. Our main contribution in this paper is an optimum P2P content replication strategy at the participating mesh routers. In particular, we determine the optimum number of replicas for every P2P file such that the average access cost of all files in the network is minimized. We propose a centralized algorithm that enables the participating mesh routers to implement the optimal strategy. We further propose a distributed low cost algorithm for P2P content replication at the participating mesh routers, and show that the distributed algorithm mimics the optimal strategy very well. The analytical and simulation results show that our replication strategy significantly reduces the average overall cost of accessing P2P files in the WMN as compared with other commonly used replication strategies. Copyright © 2013 John Wiley & Sons, Ltd.

Intermittent hardware faults are hard to diagnose as they occur non-deterministically at the same location. Hardware-only diagnosis techniques incur significant power and area overheads. On the other hand, software-only diagnosis techniques have low power and area overheads, but have limited visibility into many micro-architectural structures and hence cannot diagnose faults in them. To overcome these limitations, we propose a hardware-software integrated framework for diagnosing intermittent faults. The hardware part of our framework, called SCRIBE continuously records the resource usage information of every instruction in the processor, and exposes it to the software layer. SCRIBE incurs a performance overhead of 12% and power overhead of 9%, on average. The software part of our framework is called SIED and uses backtracking from the program's crash dump to find the faulty micro-architectural resource. Our technique has an average accuracy of 84% in diagnosing the faulty resource, which in turn enables fine-grained deconfiguration with less than 2% performance loss after deconfiguration.

We describe the design of a PC-to-FPGA data streaming platform that enables hardware acceleration of gigabyte scale input data. Specifically, the acceleration is an FPGA implementation of the Dialign Algorithm, which performs both global and local alignment of query biological sequences against relatively larger reference strands of biological sequences. Earlier implementations of this algorithm could not be scaled to handle gigabyte-length reference sequences, nor megabyte-length query sequences, due to the inherent limitations of available memory and logic on single-FPGA platforms. We solve these issues via the design of an Ethernet channel to stream the reference sequence, and describe the novel use of SATA based Solid State Drives (SSDs) to time multiplex the FPGA logic into handling larger query sequences as well. In doing so, this paper also presents a general method to achieve gigabyte-depth FIFOs on commercially available FPGA development boards. This benefits data-intensive acceleration even outside of the bioinformatics application domain. Through the development of our acceleration logic and careful coupling of the required IO peripherals, we have successfully demonstrated a processing time of 28.61 minutes for a 200 base-pair query-sequence aligned against a 1 GB reference-sequence, a rate that is limited only by SATA 2 SDD write speeds. The present runtime offers a 38× speedup (18.36 hours down to 28.61 minutes) compared to standalone PC based processing.

Reliable, secure, private and fast communication in vehicular networks (VNets) is extremely challenging due to the highly mobile nature of these networks. Contact time between vehicles is very limited and topology is constantly changing. Trusted communication in VNets is of crucial importance because without trust, all efforts for minimizing the delay or maximizing the reliability could be voided. In this paper, we propose a trust-based framework for communication in VNets that is capable of accommodating traffic from different applications. Our scheme assigns a trust value to each road segment and one to each neighborhood, instead of each car. Thus it scales up easily and is completely distributed. Experimental results demonstrate that this framework outperforms other well-known routing protocols since it routes the messages via trusted vehicles.

Multiple-input multiple-output (MIMO) wireless communication systems can achieve higher throughput through interference alignment. For a small number of users, determining the maximum possible degrees of freedom as well as the feasibility of interference alignment in MIMO systems is well studied. However, the issues of scheduling in systems employing interference alignment and serving a large number of users have received little attention so far. In this paper, we study the problem of joint scheduling, interference alignment, and packet admission control in MIMO wireless systems with the goal of maximizing system throughput subject to stability constraints. We formulate a stochastic network optimization problem and propose a scheduling and interference alignment (SIA) algorithm. In each time slot, SIA schedules some users among many competing ones to transmit data, and determines encoding and decoding matrices for the selected users. Packet admission control is performed in each time slot. In addition, we propose a heuristic semi-distributed algorithm (SDSIA), which has a lower computational complexity than the SIA algorithm. Via simulation, we evaluate the performance of SIA and SDSIA for different algorithm parameters and different numbers of users. We also compare the performance of SDSIA with other approaches which do not simultaneously exploit interference alignment and scheduling and find that the combination of these two techniques increases the achievable data rate dramatically.

ABSTRACT Wireless mesh networks (WMNs) have emerged as a promising technology that provides low‐cost broadband access to the Internet for fixed and mobile wireless end users. An orthogonal evolution in computer networking has been the rise of peer‐to‐peer (P2P) applications such as P2P data sharing. It is of interest to enable effective P2P data sharing in this type of networks. Conventional P2P data sharing systems are not cognizant of the underlying network topology and therefore suffer from inefficiency. We argue for dual‐layer mesh network architecture with support from wireless mesh routers for P2P applications. The main contribution of this paper is P2PMesh: a topology‐aware system that provides combined architecture and efficient schemes for enabling efficient P2P data sharing in WMNs. The P2PMesh architecture utilizes three schemes: (i) an efficient content lookup that mitigates traffic load imbalance at mesh routers; (ii) an efficient establishment of download paths; and (iii) a data transfer protocol for multi‐hop wireless networks with limited capacity. We note here that the path establishment and data transfer schemes are specific to P2P traffic and that other traffic would use routes determined by the default routing protocol in the WMN. Simulation results suggest that P2PMesh has the potential to improve the performance of P2P applications in a wireless multi‐hop setting; specifically, we focused on data sharing, but other P2P applications can also be supported by this approach. Copyright © 2011 John Wiley & Sons, Ltd.

We consider the problem of energy consumption in sharing a viral file between peers over a wireless community network (e.g., students in campus). Wireless community networks such as Wireless Mesh Networks (WMNs) have been accepted as a new communication approach that enables users to share the network resources and reduce the cost of the Internet access. The common paradigm for sharing content between users in a community network is through the use of a centralized server. Another scheme is to exploit the upload capacity of peers who are interested in the same content (e.g., Peer-to-Peer (P2P) file sharing). In this paper, we consider a content distribution setting in a wireless mesh network wherein a number of infrastructure nodes (mesh routers) support the P2P content sharing and act as caches and participants. We model the performance of this content distribution scheme, and analytically compute the energy that is consumed in the network when a viral P2P object is shared between the peers in a WMN. We compare the energy consumption with the centralized server scheme using both numerical results and detailed simulations. The results shows significant reduction in energy consumption (more than an order of magnitude) when only few replicas of the object is cached at the infrastructure nodes.

Fair allocation of resources is an important consideration in the design of wireless networks. In this paper, we consider the setting of multihop wireless networks with multiple routing paths and develop an online flow control and scheduling algorithm for packet admission and link activation that achieves high aggregate throughput while providing different data flows with a fair share of network capacity. For fairness provisioning, we seek to maximize the minimum throughput provided to flows in the network. To cope with different degrees of data reliability among the different links in the network, we use different channel code rates as appropriate. While we expect performance improvement using channel coding and multipath routing, the main contribution of our work is a joint treatment of network stability, multipath routing and link-level reliability in meeting the overarching goal of maxmin fairness. We develop a decentralized, and hence practical, scheduling policy that addresses various concerns and demonstrate, via simulations, that it is competitive with respect to an optimal centralized rate allocator. We also evaluate the fairness provisioning under the proposed algorithm and show that channel coding improves the performance of the network significantly. Finally, we show through simulations that the proposed algorithm outperforms a class of existing approaches on fairness provisioning, which are developed based on utility maximization.

Supporting QoS for safety-critical applications for intelligent transportation systems accentuates the analytical modeling of delays in vehicular networks. Such analysis is, however, challenging due to the dynamics of such a network. We make progress by deriving lower- and upper-bounds for information dissemination delays in multi-hop vehicular networks using two different routing schemes. In particular, we determine the probability that a message m in a vehicular network will be delivered successfully to a participant at distance x from the source within t time units. Messages are broadcast at each hop after a MAC layer delay and nodes in the transmission neighborhood receive the message with some probability which represents the packet loss probability. Network density and inter-vehicle spacing are based on recent empirical studies of vehicular traffic. Simulation studies indicate that our model, and associated analysis, does capture the delay characteristics of vehicular networks. In addition, we observe a sharp threshold for message delivery in these networks, i.e., for a fixed distance x there exists a t* such that a message is delivered almost surely to a destination node that is at distance x from the source when the time allowed is greater than t* (And, it is almost surely not delivered if the time allotted is less than t*.) We believe that this is a promising step towards accurate characterization of communication delay in vehicular networks.

Wireless links are often unreliable and prone to transmission error due to varying channel conditions. These can degrade the performance in wireless networks, particularly for applications with tight quality-of-service requirements. A common remedy is to use channel coding where the transmitter node adds redundant bits to the transmitted packets in order to reduce the error probability at the receiver. However, this per-link solution can compromise the link data rate, leading to undesired end-to-end performance. In this paper, we show that this latter shortcoming can be mitigated if the end-to-end transmission rates and channel code rates are selected properly over multiple routing paths. We formulate the joint channel coding and end-to-end data rate allocation problem in multipath wireless networks as a network throughput maximization problem, which is non-convex. We tackle the non-convexity by using function approximation and iterative techniques from signomial programming. Simulation results confirm that by using channel coding jointly with multi-path routing, the end-to-end network performance can be improved significantly.

We consider a Peer-to-Peer (P2P) data sharing setting in wireless mesh networks (WMNs), wherein few mesh routers are provisioned with storage capacity and act as caches and participants in the P2P content sharing. Our contributions in this paper are optimum replication strategies for the P2P objects at the participating mesh routers to reduce the communication cost between peers within the WMN. We determine the optimum number of replicas for each object such that the average access cost of all objects in the network is minimized. We then propose a distributed algorithm for object replication and show that the distributed algorithm mimics the optimal strategy very well. The simulation results show that our strategy reduces the communication cost as compared to other commonly used strategies by a ratio of ≈20%.

Safety-critical applications form the main motivation for intelligent transportation systems. Studying the major concerns in such applications, i.e., delay and reliability, through mathematical analysis is extremely beneficial because it enables us to design optimized schemes. Such analysis is, however, challenging due to the dynamics of such a network. In this paper, we present a mathematical model that bounds the delay of emergency message dissemination in vehicular networks. We make some interesting observations from the presented model. First, the end-to-end reliability has a fairly fast transition over time which we formally prove this observation. The second observation from the analytical model confirms the fact that using the vehicle density on the road is a good metric for setting the right forwarding probability in vehicles. We exploit this conclusion and propose a completely distributed forwarding strategy. Simulation studies indicate that our model does capture the delay characteristics of vehicular networks. It also affirms the effectiveness of our warning dissemination scheme in terms of delay and single-hop reliability. We believe that this is a promising step towards accurate characterization of communication delay and reliability in vehicular networks.

Wireless Mesh Networks (WMNs) have been widely deployed as a new communication paradigm that can provide innovative services for a community (neighborhood, campus, etc.). WMNs are capable to provide both delay-sensitive services such as Voice over Internet Protocol (VoIP) and delay-insensitive services such as peer-to-peer file sharing. Network routing protocols in WMNs often employ the minimum-hops routing metric to provide Quality of Service (QoS) for the delay-sensitive traffic. However, this approach results in unbalanced traffic load at network mesh routers. In this paper, we propose the WMN-Balance: a content lookup algorithm for peer-to-peer file sharing over wireless mesh networks. The WMN-Balance enhances the content lookup routing on the overlay network, that involves mesh routers which support peer-to-peer file sharing, to mitigate the network unbalanced load.

Massively multicore processors, like, for example, Graphics Processing Units (GPUs), provide, at a comparable price, a one order of magnitude higher peak performance than traditional CPUs. This drop in the cost of computation, as any order-of-magnitude drop in the cost per unit of performance for a class of system components, triggers the opportunity to redesign systems and to explore new ways to engineer them to recalibrate the cost-to-performance relation.

Intermittent hardware faults are bursts of errors that last from a few CPU cycles to a few seconds. Recent studies have shown that intermittent fault rates are increasing due to technology scaling and are likely to be a significant concern in future systems. We study the impact of intermittent hardware faults in programs. A simulation-based fault-injection campaign shows that the majority of the intermittent faults lead to program crashes. We build a crash model and a program model that represents the data dependencies in a fault-free execution of the program. We then use this model to glean information about when the program crashes and the extent of fault propagation. Empirical validation of our model using fault-injection experiment shows that it predicts almost all actual crash-causing intermittent faults, and in 93% of the considered faults the prediction is accurate within 100 instructions. Further, the model is found to be more than two orders of magnitude faster than equivalent fault-injection experiments performed with a microprocessor simulator.

We examine optimal strategies for querying a sensor network when energy efficiency and data freshness need to be balanced. We use statistical information about the nature of events monitored by the sensor network to develop good query schedules. For Poisson event arrivals, we develop an optimal scheduling strategy that is actually a periodic querying policy. For hyper exponential distribution of event inter-arrival times, we discuss an optimal policy, and suggest sub optimal schemes because of the high computational cost imposed by the optimal scheme. We treat the sensor network like a black box that has (primarily energy) costs associated with various operations and suggest that this is indeed feasible, as a consequence the higher-level policies that we discuss for scheduling queries can be realized easily.

As real-time industrial control systems scale up, single real-time local area network (LAN) is no longer sufficient; instead, we need real-time switches to merge many real-time LANs into real-time wide area networks (WANs). However, nowadays commercially-off-the-shelf WAN switches are designed for best-effort Internet traffic rather than real-time traffic. To address this problem, we propose a real-time crossbar switch design that minimally modifies, and even simplifies the de facto industrial standard switch design of iSLIP. Specifically, we change the iSLIP request-grant-accept negotiation to deterministic grant. The switch runs periodically with an M cell-time clock-period. Every input port runs per-flow queueing, and every output port deterministically grants input port per-flow queues according to its own M cell-time clock-period schedule. The schedules are created offline. We prove that the global scheduling can be reduced to a preemptive open shop scheduling problem; as long as every input/output needs to send/fetch no more than M cells per M cell-time clock-period, all outputs schedules do not conflict; and the scheduling algorithm takes O(N4) time (N is the number of input/output ports). Such design serves real-time periodic/aperiodic traffic in a time-division multiple-access (TDMA) fashion. This simplifies analysis, provides isolation, and results in a close-form end-to-end delay bound. We implemented the proposed real-time switch using Xilinx field programmable gate arrays (FPGAs), and built a distributed control test bed upon the switched networks. Using the test bed, we carried out experiments to compare the implemented real-time switches and iSLIP switches. The results prove the necessity of using real-time switches for real-time industrial control.

Network coding has recently received increasing attention to improve performance and increase capacity in both wired and wireless communication networks. In this paper, we focus on inter-session network coding, where multiple unicast sessions jointly participate in network coding. Wireless links are often unreliable because of varying channel conditions. We consider multi-hop unicast sessions over unreliable links and propose a distributed end-to-end transmission rate adjustment mechanism to maximize the aggregate network utility by taking into account the wireless link reliability information. This includes an elaborate modeling of end-to-end reliability. Simulation results show that by taking into account the reliability information, we can increase the network throughput by up to 100% for some network topologies. We can also increase the aggregate network utility significantly for various choices of utility functions.

Wireless mesh networks are being widely deployed around the world as a mean to provide low-cost access to the Internet. The high capacity at mesh routers nodes allows applications such as real time multicast over WMNs. In light of the slow development of IP multicast and the rise of peer-to-peer communication, implementing multicast capability at the application layer is imminent. QoS support for application layer multicast over WMNs is challenging due to the architecture of the overlay networks, characteristics of the wireless medium, and end users limited bandwidth efficiency. We argue for ring-based overlay multicast scheme with support from wireless mesh routers for the multicast applications. We demonstrate, using extensive simulations, that this approach has excellent potential to improve the performance of the peer-to-peer multicast applications in a wireless setting; specifically we focus on many-to-many real time multimedia applications but other applications can also be supported by this approach.

Wireless mesh networks can provide scalable highspeed Internet access at a low cost. Fair channel access among different nodes in the wireless mesh network, however, is an important consideration that needs technological solutions before mesh networks can be widely deployed. Lack of fairness significantly decreases the throughput of nodes that are more than one hop away from mesh gateways. We propose an analytical model and use simulation studies to establish the existence of starvation in mesh networks even when we can ameliorate problems due to exposed terminals. Motivated by the inability of standard medium access control (MAC) protocols to limit starvation, we propose a modification to the MAC protocol to alleviate flow starvation. Our proposed algorithm improves the channel usage of short-term flows with nodes that are multiple hops from the gateway by a factor of 7 in some cases with a penalty of 20% reduction in total throughput across all nodes. Our proposed algorithm also has a better performance than two other schemes in terms of a higher fairness index.

We address the maximum lifetime routing problem in wireless sensor networks (WSNs) and propose two online routing algorithms based on fuzzy logic, namely fuzzy maximum lifetime algorithm and fuzzy multiobjective algorithm. The former attempts to maximize the WSN lifetime objective, whereas the latter strives to simultaneously optimize the lifetime as well as the energy consumption objectives. The distinguishing aspect of this work is the novel use of fuzzy membership functions and rules in the design of cost functions for the routing objectives considered in this work. A range of simulation results obtained under various network scenarios show that the proposed approach is superior to a number of other well-known online routing heuristics, both in terms of the obtained network lifetime as well as the average energy consumption.

Today, several data-storage systems allow applications to create and manage custom metadata to improve data search and navigability in large scale storage systems.

The convergence of computers and the physical world is the theme for next generation networking research. This trend calls for real-time network infrastructure, which requires a high-speed real-time WAN to serve as its backbone. However, commercially available high-speed WAN switches (routers) are designed for best-effort Internet traffic. A real-time switch design for the aforementioned networks is missing. We propose a real-time switch design using a crossbar switching fabric. The proposed switch can be implemented by making minimal modification, or even simplification, to the widely implemented iSLIP crossbar switch scheduler. Our real-time switch serves periodic and aperiodic traffic with real-time virtual machine tasks, which simplifies analysis, provides isolation, and facilitates future hierarchical scheduling and flow aggregation. Taking advantage of the fact that most industrial real-time network flows rarely change, our switch is better adapted to providing high bandwidths and low latencies.

The allocation of computation and communication resources in a manner that optimizes aggregate system performance is a crucial aspect of system management. Wireless sensor network poses new challenges due to the resource constraints and real-time requirements. Existing work has dealt with the real-time sampling rate assignment problem, under single processor case and network case with static routing environment. For wireless sensor networks, in order to achieve better overall network performance, routing should be considered together with the rate assignments of individual flows. In this paper, we address the problem of optimizing sampling rates with dynamic route selection for wireless sensor networks. We model the problem as a constrained optimization problem and solve it under the network utility maximization framework. Based on the primal-dual method and dual decomposition technique, we design a distributed algorithm that achieves the optimal global network utility considering both dynamic route decision and rate assignment. Extensive simulations have been conducted to demonstrate the efficiency and efficacy of our proposed solutions.

The problem of identifying suitable conditions for the schedulability of (nonpreemptive) recurring tasks with deadlines is of great importance to real-time systems. In this paper, motivated by the problem of scheduling radar dwells, we show that scheduling problems of this nature show a sharp threshold behavior with respect to system utilization. Sharp thresholds are associated with phase transitions: When the utilization of a task set is less than a critical value, it can be scheduled almost surely and, when the utilization increases beyond the critical level, almost no task set can be scheduled. We make connections to work on random graphs to prove the sharp threshold behavior in the scheduling problem of interest. Using extensive experiments, we determine the threshold for the radar dwell scheduling problem and use it for performance optimization. The connections to random graph theory suggest new ways for understanding the average-case behavior of scheduling policies. These results emphasize the ease with which performance can be controlled in a variety of real-time systems.

Fault tolerance is an important aspect in real-time computing. In real-time control systems, tasks could be faulty due to various reasons. Faulty tasks may compromise the performance and safety of the whole system and even cause disastrous consequences. In this paper, we describe On-demand real-time guard (ORTEGA), a new software fault tolerance architecture for real-time control systems. ORTEGA has high fault coverage and reliability. Compared with existing real-time fault tolerance architectures, such as Simplex, ORTEGA allows more efficient resource utilizations and enhances flexibility. These advantages are achieved through the on-demand detection and recovery of faulty tasks. ORTEGA is applicable to most industrial control applications where both efficient resource usage and high fault coverage are desired.

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.

Summary form only given. Safety-critical real-time systems are being designed using off-the-shelf components connected together to provide the different functions expected from the system. In such architectures, the communication backbone plays an important role in helping systems meet their timing constraints. Components are typically connected via buses, and often components are connected to more than one bus. We describe an approach to synthesizing routes such that all messages meet their deadlines in distributed systems built using bus-based networks when the traffic characteristics are known in advance. This work is the starting point for further work, which will allow network resources to be allocated dynamically when traffic patterns cannot be determined at design-time.

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.

Route selection is an important aspect of the design of real-time systems in which messages might have to travel over multiple hops to reach their destination and multiple paths exist between a source and a destination. The length of a route affects the ability to meet deadlines and greedy routing might leave certain messages with no feasible route. We consider bus-based networks on which periodic message transmissions need to be scheduled and present a technique for synthesizing routes such that all messages meet their deadlines. Our offline technique enables system designers to configure routes in a large-scale embedded system. In our solution, we allow message fragmentation and utilize multiple paths to satisfy the requirements of each message. The routing problem is NP-complete and our approximation algorithm is based on a linear programming formulation. In our methodology, we deal with both earliest deadline first and rate monotonic scheduling at each bus in the system. Apart from point-to-point messages, we discuss scheduling multicast messages to facilitate the publisher/subscriber model. Finally, we also mention some heuristics for online routing which might be of value in soft real-time systems.

This paper addresses the problem of scheduling real-time dwells in multi-function phase array radar systems. To keep track of targets, a radar system must meet its timing and energy constraints. We propose a new task model for radar dwells to accurately characterize their timing parameters. We develop an algorithm of transforming every dwell task as a semi-period task so the dwell task can meet its timing constraint and the interarrival times of the task will not be a constant. We also develop an enhanced template-based scheduling algorithm to schedule such tasks to meet the timing and energy constraints. Simulation results show that this algorithm can significantly improve the resource utilization.