Abstract: 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. View full abstract»
Abstract: Scheduling recurring task sets that allow some instances of the tasks to be skipped produces holes in the schedule which are nonuniformly distributed. Similarly, when the recurring tasks are not strictly periodic but are sporadic, there is extra processor bandwidth arising because of irregular job arrivals. The additional computation capacity that results from skips or sporadic tasks can be reclaimed to service aperiodic task requests efficiently and quickly. We present techniques for improving the response times of aperiodic tasks by identifying nonuniformly distributed spare capacity—because of skips or sporadic tasks—in the schedule and adding such extra capacity to the capacity queue of a BASH server. These gaps can account for a significant portion of aperiodic capacity, and their reclamation results in considerable improvement to aperiodic response times. We present two schemes: NCLB-CBS, which performs well in periodic real-time environments with firm tasks, and NCLB-CUS, which can be deployed when the basic task set to schedule is sporadic. Evaluation via simulations and implementation suggests that performance improvements for aperiodic tasks can be obtained with limited additional overhead.
Abstract: 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.
Abstract: 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.
Abstract: 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.
Abstract: 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%.
Abstract: 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.
Abstract: 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.
Abstract: 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.
Abstract: 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.
Abstract: 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.
Abstract: We target an interesting problem of simultaneous optimization of lifetime and source-to-sink delay in wireless sensor networks, and present a fuzzy multiobjective online routing algorithm. For a routing request, the proposed routing algorithm finds a path that offers a good balance between the two routing objectives, namely maximizing the network lifetime and minimizing the source-to-sink delay. Fuzzy membership functions and rules are used for designing the cost function for each of the optimization objective and the multiobjective cost aggregation function, respectively. It is shown that the use of fuzzy logic offers a flexible mean of controlling the tradeoff between the two objectives. A set of simulation results were obtained, using numerous topologies and under various parameters, to indicate that the proposed multiobjective routing scheme is able to achieve good lifetime values while maintaining reasonably short end-to-end delay values.
Abstract: We address the maximum lifetime routing problem in wireless sensor networks, and present an online multipath routing algorithm. The proposed algorithm strives to maximize the network lifetime metric by distributing the source-to-sink traffic for a given routing request along a set of paths. Fuzzy membership function is used for designing the edge weight function. Simulation results obtained under a variety of network scenarios show that the proposed multipath scheme is able to achieve better lifetime results than those obtained by its predecessor single-path fuzzy routing scheme as well as by another well-known online routing scheme, namely the Online Maximum Lifetime heuristic.
Abstract: 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.
Abstract: 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.
Abstract: The report of the President’s Council of Advisors on Science and Technology (PCAST) has placed CPS on the top of the priority list for federal research investment [6]. This article first reviews some of the challenges and promises of CPS, followed by an articulation of some specific challenges and promises that are more closely related to the Sensor Networks, Ubiquitous and Trustworthy Computing Conference.
Abstract: The convergence of computers and the physical world is the theme for next generation networking research. This trend callsfor 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.
Abstract: The allocation of computation and communicationresources 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 realtime 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, weaddress 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 todemonstrate the efficiency and efficacy of our proposed solutions.
Abstract: 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.
Abstract: The rapid need for high bandwidth and low latency communication in distributed real-time systems is driving system architects towards high-speed switches developed for high volume data transfer on the Internet. These switches employ complex scheduling algorithms for transferring data cells from the input line to the output line. From a real-time systems perspective, it is necessary to understand the behavior of these switching algorithms and obtain worst-case delay bounds for message transfer across these switches. Many researchers have derived average-case delay bounds for switching algorithms but mission-critical systems require guarantees for the worst-case. In this context, we derive upper bounds on cell delays across commonly available switches. Our bounds provide a starting point for research in this direction. Moreover, we use the delay bounds to construct low-cost networks of switches given a set of processors and their real-time communication requirements. Experiments with the heuristic algorithm that we propose for network design have produced encouraging results. Importantly, the algorithm is independent of the delay analysis technique and better techniques can be incorporated trivially. By addressing the network design problem, we hope to transform the system architecting process from a manual, ad-hoc operation to a simple and automated step that will result in better designs and cost savings.
Abstract: The heterogeneous multiprocessor task partitioning with replication problem involves determining a mapping of recurring tasks upon a set consisting of different processing units in such a way that all tasks meet their timing constraints and no two replicas of the same task are assigned to the same processing unit. The replication requirement improves the resilience of the real-time system to a finite number of processor failures. This problem is NP-hard in the strong sense. We develop a Fully Polynomial-Time Approximation Scheme (FPTAS) for this problem.
Abstract: 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. View full abstract»
Abstract: 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. View full abstract»
