Datacenter clusters often run data-intensive jobs in parallel for improving resource utilization and cost efficiency. The performance of parallel jobs is often constrained by the cluster's hard-to-scale network bisection bandwidth. Various solutions have been proposed to address the issue, however, most of them do not consider inter-job data dependencies and schedule jobs independently from one another. In this work, we find that aggregating and co-locating the data and tasks of dependent jobs offer an extra opportunity for data locality improvement that can help to greatly enhance the performance of jobs. We propose and design Dawn, a dependency-aware network-adaptive scheduler that includes an online plan and an adaptive task scheduler. The online plan, taking job dependencies into consideration, determines where (i.e., preferred racks) to place tasks in order to proactively aggregate dependent data. The task scheduler, based on the output of online plan and dynamic network status, adaptively schedules tasks to co-locate with the dependent data in order to take advantage of data locality. We implement Dawn on Apache Yarn and evaluate it on physical and virtual clusters using various machine learning and query workloads. Results show that Dawn effectively improves cluster throughput by up to 73 and 38 percent compared to Fair Scheduler and ShuffleWatcher, respectively. Dawn not only significantly enhances the performance of jobs with dependency, but also works well for jobs without dependency.

Maintaining a common notion of time among communicating nodes in mobile multihop networks is crucial to the correctness of many distributed real-time applications such as target tracking, data fusion, and environmental monitoring. Achieving both synchronization accuracy and efficiency (in terms of communication and energy overheads) are important goals of a time synchronization mechanism. While these goals have been addressed by numerous approaches for stationary or homogeneous networks that rely on uniform clock drift models and synchronization accuracy requirements, these existing approaches are not optimal when applied in networks that are mobile or where synchronization accuracies and clock drift rates differ among nodes. This paper proposes a novel opportunistic and on-demand synchronization mechanism called Mobi-Sync, which has two important characteristics. First, it avoids network-wide flooding or frequent reconstructing of rigid structures that are often unavoidable in other approaches when applied to mobile networks. Second, it (re-)synchronizes nodes only when necessary, thereby customizing the synchronization interval to each node's specified accuracy requirement. Our results demonstrate that Mobi-Sync satisfies the nodes' synchronization requirements in mobile networks, while significantly reducing the synchronization overhead compared to existing solutions.

We consider wireless real-time systems that execute computationally-intensive applications and must transmit packets over the network in a timely manner. Existing methods do not consider the importance (i.e., urgency) of a packet as perceived by end users in conjunction with energy consumption, real-time task deadlines, and packet deadlines, inadvertently causing packet priority inversion during transmissions and possibly starvation of some streams. We present an online holistic scheduling framework that explicitly considers packet importance to select packets to transmit and guarantee their deadline requirements using both packet and energy-aware job assignment and scheduling. Our framework is applicable to wireless real-time systems equipped with either a single processor or a multicore system. Based on extensive simulations, we show that our proposed method allows for timely transmissions of the most important packets, which helps to control packet urgency, while saving processor(s) energy.

Reservation-based (as opposed to contention-based) channel access in WLANs provides predictable and deterministic transmission and is therefore able to provide timeliness guarantees for wireless and embedded real-time applications. Also, reservation-based channel access is energy-efficient since a wireless adaptor is powered on only during its exclusive channel access times. While scheduling for Quality of Service at the central authority (e.g., base station) has received extensive attention, the problem of determining the actual resource requirements of an individual node in a wireless real-time system has been largely ignored. This work aims at finding the minimum channel bandwidth reservation that meets the real-time constraints of all periodic streams of a given node. Keeping the bandwidth reservation of a node to a minimum leads to reduced energy and resource requirements and leaves more bandwidth for future reservations by other nodes. To obtain a solution to the minimum bandwidth reservation problem, we transform it to a generic uniprocessor task schedulability problem, which is then addressed using a generic algorithm. This algorithm works for a subclass of priority-driven packet scheduling policies, including three common ones: fixed-priority, EDF, and FIFO. Moreover, we then specialize the generic algorithm to these three policies according to their specific characteristics. Their computation complexities and bandwidth reservation efficiencies are evaluated and guidelines for choosing scheduling policies and stream parameters are presented.

Autonomous management of a multi-tier Internet service involves two critical and challenging tasks, one understanding its dynamic behavior when subjected to dynamic workload and second adaptive management of its resources to achieve performance guarantees. In this paper, we propose a statistical machine learning based approach to achieve session slowdown guarantees of a multi-tier Internet service. Session slowdown is the ratio of a session's total queueing delay to its total processing time. It is a compelling performance metric of session-based Internet services because it directly measures user-perceived relative performance. However, there is no analytical model for session slowdown on multi-tier servers. We first conduct training to learn the statistical regression models that quantitatively capture an Internet service's dynamic behavior as relationships between various service parameters. Then, we propose a dynamic resource provisioning approach that utilizes the learned regression models to efficiently achieve session slowdown guarantees under varying workloads. The approach is based on the combination of extensive offline training and online monitoring of the Internet service behavior. Experiments using the industry standard TPC-W benchmark demonstrate the effectiveness and efficiency of the regression based dynamic resource provisioning approach in meeting the session slowdown guarantees of a multi-tier e-commerce application.

Exclusive access to the wireless medium, e.g., as provided by bandwidth-reservation mechanisms, limits contention and therefore is capable of providing effective real-time support to periodic communications. Furthermore, to preserve energy, wireless cards can be powered down between periodic accesses without loss of data. However, packet schedulers must be aware of the limited communication opportunities to ensure that packets are transmitted before their deadlines, CPU schedulers must execute jobs such that the packets generated by these jobs are available for transmission in time, and DVS algorithms must choose processor speeds such that job execution and therefore packet generation are not unduly delayed. This paper proposes a co-scheduling approach to integrate CPU, network, and energy management for wireless real-time systems that rely on bandwidth reservations. Both simulation and experimentation indicate significant improvements in meeting packet deadlines (up to 40%) with only small increases in overall energy consumption (less than 10%) compared to the state of the art.

introduction Share on Introduction to the special issue on self-adaptive and self-organizing wireless networking systems Authors: Michael Lemmon Department of Electrical Engineering, University of Notre Dame, USA Department of Electrical Engineering, University of Notre Dame, USAView Profile , Christian Poellabauer Department of Computer Science and Engineering, University of Notre Dame, USA Department of Computer Science and Engineering, University of Notre Dame, USAView Profile , Liqiang Zhang Department of Computer and Information Sciences, Indiana University South Bend, USA Department of Computer and Information Sciences, Indiana University South Bend, USAView Profile , Xiaobo Zhou Department of Computer Science, University of Colorado at Colorado Springs, USA Department of Computer Science, University of Colorado at Colorado Springs, USAView Profile Authors Info & Claims ACM Transactions on Autonomous and Adaptive SystemsVolume 4Issue 3Article No.: 15pp 1–4https://doi.org/10.1145/1552297.1552298Published:24 July 2009Publication History 1citation361DownloadsMetricsTotal Citations1Total Downloads361Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Reservation-based channel access has been shown to be effective in providing Quality of Service (QoS) guarantees (e.g., timeliness) in wireless embedded real-time applications such as mobile media streaming and networked embedded control systems. While the QoS scheduling at the central authority (i.e., base station) has received extensive attention recently, the computation of resource requirements at each individual node has been widely ignored. An inappropriate resource requirement may lead to degraded support for real-time traffic and overprovisioning of scarce network resources. This work addresses this issue by presenting a strategy for nodes to determine minimal resource reservations that guarantee the real-time constraints of their network traffic. In addition, this paper examines the relationship between timeliness constraints of the traffic and resource requirements.

Rate adaptation is a common technique to exploit channel diversity in wireless networks. Despite the many rate adaptation algorithms proposed for 802.11 networks, the ARF (auto rate fallback) remains the most widely adopted scheme in commercial 802.11 products due to its simplicity. However, ARF suffers from some disadvantages. Our research effort revealed the rate avalanche effect that could significantly degrade the network performance of heavily loaded 802.11 networks. In this work, we propose RADAR (Rate-Alert DynAmic Rts/cts exchange) to judiciously exploit dynamic RTS/CTS exchange in multi-rate 802.11 networks. RADAR could effectively suppress the rate avalanche effect while at the same time minimizes the transmission overhead of RTS/CTS exchanges. Being fully compatible with current 802.11 standards, RADAR can be readily implemented in the NIC driver. Through extensive simulations using realistic channel propagation and reception models, we demonstrate that RADAR is a practical and efficient performance enhancement approach for multi-rate 802.11 networks.

Packet delay and bandwidth are two important metrics for measuring quality of service (QoS) of Internet services. While proportional delay differentiation (PDD) has been studied intensively in the context of differentiated services, few studies were conducted for per-class bandwidth differentiation. In this paper, we design and evaluate an efficient bandwidth differentiation approach. The DIBS (dual interval bandwidth scheduling) approach focuses on the short-term bandwidth differentiation of multiple classes because many Internet transactions take place in a small time frame. It does so based on the normalized instantaneous bandwidth, measured by the use of packet size and packet delay. It also proposes to use a look-back interval and a look-ahead interval to trade off differentiation accuracy and scheduling overhead. We implemented DIBS in the click modular software router. Extensive experiments have demonstrated its feasibility and effectiveness in achieving short-term bandwidth differentiation. Compared with the representative PDD algorithm WTP, DIBS can achieve better bandwidth differentiation when the inter-class packet size distributions are different. Compared with the representative weighted fair queueing algorithm PGPS, DIBS can achieve more accurate or comparable bandwidth differentiation at various workload situations, with better delay differentiation and lower cost.

The request-to-send/clear-to-send (RTS/CTS) exchange was defined as an optional mechanism in DCF (distributed coordination function) access method in IEEE 802.11 standard to deal with the hidden node problem. However, in most infrastructure-based WLANs, it is turned off with the belief that the benefit it brings might not even be able to pay off the transmission overhead it introduces. While this is often true for networks using fixed transmission rate, our investigation leads to the opposite conclusion when multiple transmission rates are exploited in WLANs. In particular, through extensive simulations using realistic channel propagation and reception models, we found out that in a heavily loaded multi-rate WLAN, a situation that we call rate avalanche often happens if RTS/CTS is turned off. The rate avalanche effect could significantly degrade the network performance even if no hidden node presents. Our investigation also reveals that, in the absence of effective and practical loss-differentiation mechanisms, simply turning on the RTS/CTS could dramatically enhance the network performance in most cases. Various scenarios/conditions are extensively examined to study their impact on the network performance for RTS/CTS on and off respectively. Our study provides some important insights about using the RTS/CTS exchange in mutlirate 802.11 WLANs.

As one of the fundamental issues in wireless sensor networks (WSNs), the sensor localization problem has recently received extensive attention. In this work, we investigate this problem from a novel perspective by treating it as a functional dual of target tracking. In traditional tracking problems, static location-aware sensors track and predict the position and/or velocity of a moving target. As a dual, we utilize a moving location assistant (LA) (with a global positioning system (GPS) or a predefined moving path) to help location-unaware sensors to accurately discover their positions. We call our proposed system Landscape. In Landscape, an LA (an aircraft, for example) periodically broadcasts its current location (we call it a beacon) while it moves around or through a sensor field. Each sensor collects the location beacons, measures the distance between itself and the LA based on the received signal strength (RSS), and individually calculates their locations via an Unscented Kalman Filter (UKF)-based algorithm. Landscape has several features that are favorable to WSNs, such as high scalability, no intersensor communication overhead, moderate computation cost, robustness to range errors and network connectivity, etc. Extensive simulations demonstrate that Landscape is an efficient sensor positioning scheme for outdoor sensor networks.

Packet delay and bandwidth are two important metrics for measuring quality of service (QoS) of Internet services. Traditionally, packet delay differentiation and fair bandwidth sharing are studied separately. In this paper, we first propose a generalized model for providing fair bandwidth sharing with delay differentiation, namely FBS-DD. It essentially aims to provide multi-dimensional proportional differentiation with respect to both QoS metrics at the same time. We design packet scheduling schemes that take both packet delay and packet size into considerations, without assuming admission control. Furthermore, we propose a control-theoretic buffer management scheme. The packet scheduling with buffer management approach provides delay and bandwidth differentiation in an integrated way, while existing approaches consider delay and loss rate differentiation as orthogonal issues. It enhances the flexibility of network resource management and multi-dimensional QoS provisioning. It is capable of self-adapting to varying workloads from different classes, which automatically builds a firewall around aggressive clients and hence protects network resources from saturation. Simulation results by the use of trace files demonstrate that the approach can provide predictable fair bandwidth sharing with delay differentiation at various situations. The control-theoretic buffer management scheme improves the controllability.

Despite the fact that sensor networks could often be deployed over three-dimensional (3D) terrains, most approaches on sensor localizations are designed and evaluated considering only two-dimensional (2D) applications. On the other hand, being the foundation of the most previous localization solutions, reliable and sufficient neighborhood-measurements are often hard to achieve for sensor nodes deployed in complex 3D terrains, which makes it difficult to extend those solutions into 3D applications. In the paper, we introduce a robust 3D localization solution called Landscape-3D, in which we treat the localization problem from a novel perspective by taking it as a functional dual of target tracking. Besides several nice features, such as high scalability, high accuracy, zero sensor-to-sensor communication overhead, low computation overhead, etc., one of the most important advantages of Landscape-3D is that it works totally independent of node densities and network topologies, which makes it robust to complex 3D environments. Our simulation model involves various 3D scenarios. Experimental results demonstrate that Landscape-3D is a robust localization approach for sensor networks deployed in complex 3D terrains

In this work, we consider the sensor localization problem from a novel perspective by treating it as a functional dual of target tracking. In traditional tracking problems, static location-aware sensors track and predict the position/speed of a moving target. As a dual, we utilize a moving location-assistant (LA) (with global positioning system (GPS) or pre-defined moving path) to help location-unaware sensors to accurately discover their positions. We call our proposed system Landscape. In Landscape, an LA (an aircraft, for example) periodically broadcasts its current location while it moves around or through a sensor field. Each sensor collects the location beacons, measures the distance between itself and the LA based on received signal strength (RSS), and individually calculates their locations via an unscented Kalman filter (UKF) based algorithm. Our contributions are at least twofold. (1) Landscape is a distributed scheme, it does not rely on measured distances among neighbors (as used by most current proposals), which makes it robust to topology and density; Landscape involves zero sensor-to-sensor communication overhead, and is highly scalable to network size. (2) By introducing UKF in sensor localization problem, we reap multiple benefits: our UKF-based algorithm nicely exploits the constraints increasingly added by the beacons; it elegantly solves the nonlinear problem with low computation cost and complexity; and most importantly, it efficiently reduces the effects of measurement errors, making Landscape robust to ranging errors. Extensive simulations and evaluations against the state-of-the-art systems show that Landscape is a high-performance sensor positioning scheme for outdoor sensor networks.

Currently deployed IEEE 802.11 WLANs work mostly with distributed coordination function (DCF) mode at the MAC layer, which does not provide QoS support. The upcoming IEEE standard 802.11e achieves service differentiation by assigning different channel access parameters (CAPs) to different traffic classes at the MAC layer. However, such relative differentiation does not yield QoS guarantee. In practice, appropriately selecting CAPs a priori is difficult. Time-varying traffic loads also make the use of fixed CAPs inefficient for both QoS support and channel utilization. We propose a novel architecture called HARMONICA, in which the access point dynamically selects the best CAPs for each traffic class to optimally match their QoS requirements. We present and discuss a simple admission control mechanism used by HARMONICA to avoid congestion. Our simulation results demonstrate that under an interference-free environment, HARMONICA can guarantee the QoS for all traffic classes while simultaneously achieving quasi-optimal channel utilization.

To achieve innovative network architectures capable of delivering high-speed data transfers to end users, considerable efforts have been invested in minimizing or eliminating the bottlenecks that exist in high-speed network environments. These bottlenecks exist primarily at two levels, namely, network data transmission to the end system and data delivery within the end system to the user. For wired networks, improvements in fiber optic technologies have shifted the bottleneck from the underlying physical network to the end system. However, wireless networks still face obstacles at both levels to achieving high, end-to-end performance data delivery, particularly at gigabit per second rates. We first present current wireless communication technologies aimed at delivering gigabit per second transmission rates to end systems. We then investigate the bottleneck at the end system by exploring experimentally the performance benefits of a network interface architecture designed to enable high-performance, low-latency applications using minimal host resources. We compare the performance of our network interface architecture with the traditional one, using commodity PCs connected by gigabit per second local area networks running protocols such as TCP/IP and UDP/IP. We argue that such a network interface architecture can eliminate the bottlenecks prevalent in current end systems and, consequently, enables users to reap the full benefits of the high-speed networks available today.

Abstract Currently deployed IEEE 802.11 WLANs work mostly with distributed coordination function (DCF) mode at the media access control (MAC) layer, which does not provide quality of service (QoS) support. The upcoming IEEE standard 802.11e achieves service differentiation by assigning different channel access parameters (CAPs) to different traffic classes at the MAC layer. However, such relative differentiation does not yield QoS guarantee. In practice, appropriately selecting CAPs a priori is difficult. Time‐varying traffic loads also make the use of fixed CAPs, inefficient for both QoS support and channel utilization. In this work, we propose a novel architecture called HARMONICA, in which the access point (AP) dynamically selects the best CAPs for each traffic class to optimally match their QoS requirements. We present and discuss a simple admission control (AC) mechanism used by HARMONICA to avoid congestion. Our simulation results demonstrate that under an interference‐free environment, HARMONICA can guarantee the QoS for all traffic classes while simultaneously achieving quasi‐optimal channel utilization. Copyright © 2004 John Wiley & Sons, Ltd.