Rate adaptation is a mechanism unspecified by the IEEE 802.11 standards, yet critical to the system performance by exploiting the multirate capability at the physical layer. In this paper, we conduct a systematic experimental study on rate adaptation over 802.11 wireless networks. Our key contributions are as follows: First, we present a critique on popular design guidelines adopted by many practical algorithms and we uncover their limitations. Our study reveals that these seemingly correct guidelines can be misleading in practice, thus incurring significant performance penalty in certain scenarios. Second, we study the short-term channel dynamics and explore how they guide rate adaptation. To this end, we design and implement a new History-Aware Robust Rate Adaptation Algorithm (HA-RRAA). HA-RRAA uses short-term loss ratio to opportunistically guide its rate change decisions, a cost-effective adaptive RTS filter to prevent collision losses from triggering rate decrease and an adaptive time window to limit transmissions at high loss rates. Our extensive experiments show that HA-RRAA outperforms popular algorithms in all tested scenarios, with goodput gains up to 51.9 percent in field trials.

The DNS Security Extensions (DNSSEC) are among the first attempts to deploy cryptographic protections in an Internet-scale operational system. DNSSEC applies well-established public key cryptography to ensure data integrity and origin authenticity in the DNS system. While the cryptographic design of DNSSEC is sound and seemingly simple, its development has taken the IETF over a decade and several protocol revisions, and even today its deployment is still in the early stage of rolling out. In this paper, we provide the first systematic examination of the design, deployment, and operational challenges encountered by DNSSEC over the years. Our study reveals a fundamental gap between cryptographic designs and operational Internet systems. To be deployed in the global Internet, a cryptographic protocol must possess several critical properties including scalability, flexibility, incremental deployability, and ability to function in face of imperfect operations. We believe that the insights gained from this study can offer valuable inputs to future cryptographic designs for other Internet-scale systems.

Stream processing is widely used by today's applications such as financial data analysis and disaster response. In distributed stream processing systems, machine fail-stop events are handled by either active standby or passive standby. However, existing high availability (HA) schemes have not sufficiently addressed the situation when a machine becomes temporarily unavailable due to data rate spikes, intensive analysis or job sharing, which happens frequently but lasts for short time. It is not clear how well active and passive standby fare against such transient unavailability. In this paper, we first critically examine the suitability of active and passive standby against transient unavailability in a real testbed environment. We find that both approaches have advantages and drawbacks, but neither is ideal to provide fast recovery at low overhead as required to handle transient unavailability. Based on the insights gained, we propose a novel hybrid HA method that switches between active and passive standby modes depending on the occurrence of failure events. It presents a desirable tradeoff that is different from existing HA approaches: low overhead during normal conditions and fast recovery upon transient or permanent failure events. We have implemented our hybrid method and compared it with existing HA designs with comprehensive evaluation. The results show that our hybrid method can reduce two-thirds of the recovery time compared to passive standby and 80% message overhead compared to active standby, allowing applications to enjoy uninterrupted processing without paying a high premium.

This paper studies MIMO based rate adaptation (RA) in 802.11n wireless networks. Our case study shows that existing RA algorithms offer much lower throughput than even a fixed-rate scheme. The fundamental problem is that, all such algorithms are MIMO oblivious; they do not consider the characteristics of diversity-oriented, single-stream mode and the spatial multiplexing driven, double-stream mode. We propose MiRA, a novel MIMO RA scheme that zigzags between intra- and inter-mode rate options. Our experiments show that MiRA consistently outperforms three representative RA algorithms, SampleRate, RRAA and Atheros MIMO RA, in static, mobility and collision settings.

Multipath streaming protocols have recently attracted much attention because they provide an effective means to provide high-quality streaming over the Internet. However, many existing schemes require a long start-up delay and thus are not suitable for interactive applications such as video conferencing and tele-presence. In this paper, we focus on real-time live streaming applications with stringent end-to-end latency requirement, say several hundreds of milliseconds. To address these challenges, we take a joint multipath and FEC approach that intelligently splits the FEC-encoded stream among multiple available paths. We develop an analytical model and use asymptotic analysis to derive closed-form, optimal load splitting solutions, which are surprisingly simple yet insightful. To our best knowledge, this is the first work that provides such closed-form optimal solutions. Based on the analytical insights, we have designed and implemented a novel encoded multipath streaming (EMS) scheme for real-time live streaming. EMS strives to continuously satisfy the application's QoS requirements by dynamically adjusting the load splitting decisions and the FEC settings. Our simulation results have shown that EMS can not only outperform the existing multipath streaming schemes, but also adapt to the dynamic loss and delay characteristics of the network with minimal overhead.

Federated systems have recently attracted much attention because they allow loosely coupled organizations to share resources for common benefits. However, discovering resources across administrative boundaries is challenging. Despite their willingness to share resources, many organizations prefer not to export their internal resource description to unfamiliar parties. While it is highly desirable to facilitate such voluntary sharing, the system also needs to resolve resource queries in an efficient manner. Unfortunately, none of the existing resource discovery designs, either hierarchical or DHT-based, can address these two challenges in the same time.In this paper, we present the design and evaluation of ROADS, a Replication Overlay Assisted resource Discovery Service for federated systems. In ROADS, the resource owners only export summaries, which are condensed representations of their resource records. These summaries are aggregated along a hierarchy and used to direct queries to appropriate resource owners. To improve its efficiency and resiliency, ROADS replicates the summaries using server overlays that enable "shortcuts'' in query forwarding. We have implemented ROADS and evaluated its performance through extensive analysis and experiments. The results show that ROADS outperforms a DHT-based design with 1-2 orders of magnitude less overhead in update messages and 50% less query forwarding time.

As mobile nodes roam in a wireless network, they continuously associate with different access points and perform handoff operations. However, frequent handoffs can potentially incur unacceptable delays and even interruptions for interactive applications. To alleviate these negative impacts, we present novel association control algorithms that can minimize the frequency of handoffs occurred to mobile devices. Specifically, we show that a greedy LookAhead algorithm is optimal in the offline setting, where the user's future mobility is known. Inspired by such optimality, we further propose two online algorithms, namely LookBack and Track, that operate without any future mobility information. Instead, they seek to predict the lifetime of an association using randomization and statistical approaches, respectively. We evaluate the performance of these algorithms using both analysis and trace-driven simulations. The results show that the simple LookBack algorithm has surprisingly a competitive ratio .of (log k + 2), where k is the maximum number of APs that a user can hear at any time, and the Track algorithm can achieve near-optimal performance in practical scenarios.

We consider a fundamental flow maximization problem that arises during the evaluation of multiple overlapping queries defined on a data stream, in a heterogenous parallel environment. Each query is a conjunction of boolean filters, and each filter could be shared across multiple queries. We are required to design an evaluation plan that evaluates filters against stream items in order to determine the set of queries satisfied by each item. The evaluation plan specifies for each item: (i) the subset of filters evaluated for this item and the order of their evaluations, and (ii) the processor on which each filter evaluation occurs. Our goal is to design an evaluation plan which maximizes the total throughput (flow) of the stream handled by the plan, without violating the processor capacities.

We consider the problem of evaluating multiple overlapping queries defined on data streams, where each query is a conjunction of multiple filters and each filter may be shared across multiple queries. Efficient support for overlapping queries is a critical issue in the emerging data stream systems, and this is particularly the case when filters are expensive in terms of their computational complexity and processing time. This problem generalizes other well-known problems such as pipelined filter ordering and set cover, and is not only NP-Hard but also hard to approximate within a factor of o(log n) from the optimum, where n is the number of queries. In this paper, we present two near-optimal approximation lgorithms with provably-good performance guarantees for the evaluation of overlapping queries. We present an edge-coverage based Greedy algorithm which achieves an approximation ratio of (1 + log(n) + log(α)), where n is the number of queries and α is the average number of filters in a query. We also present a randomized, fast and easily parallelizable Harmonic algorithm which achieves an approximation ratio of 2β, where β is the maximum number of filters in a query. We have implemented these algorithms in a prototype system, and evaluated their performance using extensive experiments in the context of multimedia stream analysis. The results show that our Greedy algorithm consistently outperforms other known algorithms under various settings and scales well as the numbers of queries and filters increase.

False data injection is a severe attack that compromised sensor nodes ("moles"1) can launch. These moles inject large amount of bogus traffic that can lead to application failures and exhausted network resources. Existing sensor network security proposals only passively mitigate the damage by filtering injected packets; they do not provide active means for fight back. This paper studies how to locate such moles within the framework of packet marking, when forwarding moles collude with source moles to manipulate the marks. Existing Internet traceback mechanisms do not assume compromised forwarding nodes and are easily defeated by manipulated marks. We propose a probabilistic nested marking (PNM) scheme that is secure against such colluding attacks. No matter how colluding moles manipulate the marks, PNM can always locate them one by one. We prove that nested marking is both sufficient and necessary to resist colluding attacks. PNM also has fast-traceback: within about 50 packets, it can track down a mole up to 20 hops away from the sink. This virtually prevents any effective data injection attack: moles will be caught before they have injected any meaningful amount of bogus traffic.

Security and privacy are two major concerns in supporting roaming users across administrative domains. In current practices, a roaming user often uses encrypted tunnels, e.g., Virtual Private Networks (VPNs), to protect the secrecy and privacy of her communications. However, due to its encrypted nature, the traffic flowing through these tunnels cannot be examined and regulated by the foreign network's firewall, which may lead the foreign network widely open to various attacks from the Internet. This threat can be alleviated if the users reveal their traffic to the foreign network or the foreign network reveals its firewall rules to the tunnel endpoints. However, neither approach is desirable in practice due to privacy concerns. In this paper, we propose a Cross-Domain Cooperative Firewall (CDCF) that allows two collaborative networks to enforce each other's firewall rules in an oblivious manner. In CDCF, when a roaming user establishes an encrypted tunnel between his home network and the foreign network, the tunnel endpoint (e.g., a VPN server) can regulate the traffic and enforce the foreign network's firewall rules, without knowing these rules. The key ingredients in CDCF are the distribution of firewall primitives across network domains, and the enabling technique of efficient oblivious membership verification. We have implemented CDCF and integrated it with the OpenVPN software, and evaluated its performance using extensive experiments. Our results show that CDCF can protect the foreign network from encrypted tunnel traffic with minimal overhead.

Smartphones have recently become increasingly popular because they provide "all-in-one" convenience by integrating traditional mobile phones with handheld computing devices. However, the flexibility of running third-party softwares also leaves the smartphones open to malicious viruses. In fact, hundreds of smartphone viruses have emerged in the past two years, which can quickly spread through various means such as SMS/MMS, Bluetooth and traditional IP-based applications. Our own implementations of two proof-of-concept viruses on Windows Mobile have confirmed the vulnerability of this popular smartphone platform.

In modern cellular networks, the channel quality is dynamic among users and also over time. The time-granularity for such dynamics is significantly diverse - either slow or fast compared to packet transmission time. Because of these issues most existing scheduling policies can not work consistently well. In this work, we propose a scheduling policy with performance relatively insensitive to the time-granularity of the dynamics of channel quality. Our policy is self-adaptive to the scale of channel variations by using an ensemble of proposed algorithms. The proposed scheduling policy is proved to have a worst-case performance bound in the existence of both slow and fast time-varying channels. Simulation results confirm that the policy better tolerates channel variations than other popular schemes such as EDF and the Greedy algorithm.

Data dissemination is an indispensible protocol component for the emerging large-scale sensor networks. In this paper, we propose a secure data dissemination protocol that enhances directed diffusion to operate in the presence of compromised sensors. Our proposed solution, secure diffusion, utilizes a novel security primitive called location-binding keys, and exploits the available end-to-end feedback loop in directed diffusion. In secure diffusion, sensor nodes use pairwise neighbor keys to establish secure gradients, and the sink uses location-binding keys to authenticate the received sensing data. By differentiating authentic data from fabricated ones, the sink can selectively reinforce data paths and assist intermediate nodes in local reinforcement decisions to combat compromised nodes. Our security analysis shows that, in the presence of compromised nodes, secure diffusion can ensure both high-quality delivery of authentic data and local containment of malicious traffic.

Rate adaptation is a mechanism unspecified by the 802.11 standards, yet critical to the system performance by exploiting the multi-rate capability at the physical layer.I n this paper, we conduct a systematic and experimental study on rate adaptation over 802.11 wireless networks. Our main contributions are two-fold. First, we critique five design guidelines adopted by most existing algorithms. Our study reveals that these seemingly correct guidelines can be misleading in practice, thus incur significant performance penalty in certain scenarios. The fundamental challenge is that rate adaptation must accurately estimate the channel condition despite the presence of various dynamics caused by fading, mobility and hidden terminals. Second, we design and implement a new Robust Rate Adaptation Algorithm (RRAA)that addresses the above challenge. RRAA uses short-term loss ratio to opportunistically guide its rate change decisions, and an adaptive RTS filter to prevent collision losses from triggering rate decrease. Our extensive experiments have shown that RRAA outperforms three well-known rate adaptation solutions (ARF, AARF, and SampleRate) in all tested scenarios, with throughput improvement up to 143%.

Protecting the network layer from malicious attacks is an important yet challenging security issue in mobile ad hoc networks. In this paper, we describe SCAN, a unified network-layer security solution for such networks that protects both routing and data forwarding operations through the same reactive approach. SCAN does not apply any cryptographic primitives on the routing messages. Instead, it protects the network by detecting and reacting to the malicious nodes. In SCAN, local neighboring nodes collaboratively monitor each other and sustain each other, while no single node is superior to the others. SCAN also adopts a novel credit strategy to decrease its overhead as time evolves. In essence, SCAN exploits localized collaboration and information cross-validation to protect the network in a self-organized manner. Through both analysis and simulation results, we demonstrate the effectiveness of SCAN even in a highly mobile and hostile environment.

Securing wireless networks poses unique research challenges. In this paper, we survey the state-of-the-art approaches to providing security for three popular wireless networking paradigms, namely, IEEE 802.11 based WLANs, third-generation cellular networks, and mobile ad hoc networks. We identify the security threats as well as examine the current solutions. We further summarize lessons learned, discuss open issues, and identify future research directions.

Node compromise poses severe security threats in wireless sensor networks. Unfortunately, existing security designs can address only a small, fixed threshold number of compromised nodes; the security protection completely breaks down when the threshold is exceeded. In this paper, we seek to overcome the threshold limitation and achieve resiliency against an increasing number of compromised nodes. To this end, we propose a novel location-based approach in which the secret keys are bound to geographic locations, and each node stores a few keys based on its own location. The location-binding property constrains the scope for which individual keys can be (mis)used, thus limiting the damages caused by a collection of compromised nodes. We illustrate this approach through the problem of report fabrication attacks, in which the compromised nodes forge non-existent events. We evaluate our design through extensive analysis, implementation and simulations, and demonstrate its graceful performance degradation in the presence of an increasing number of compromised nodes.

Hierarchical systems have been widely used to provide scalable distributed services in the Internet. Unfortunately, such a service hierarchy is vulnerable to DoS attacks. This paper presents HOURS that achieves DoS resilience in an open service hierarchy. HOURS ensures high degree of service accessibility for each surviving node by: 1) augmenting the service hierarchy with hierarchical overlay networks with rich connectivity; 2) making the connectivity of each overlay highly unpredictable; and 3) recovering the overlay when its normal operations are disrupted. We analyze an HOURS-protected open service hierarchy, and demonstrate its high degree of resilience to even large-scale, topology-aware DoS attacks.

This work seeks a better understanding of the relations between the better network service provided by QoS-oriented wireless packet scheduling and the actual benefits perceived by the multimedia applications that use them. Through extensive simulations driven by real (multimedia and wireless channel error) traces, we observe that in general, there is a performance gap between application perceived QoS and network QoS provided by the wireless fair packet scheduler. This gap tends to increase further as the channel error rate aggravates. The exact distribution of channel errors greatly affects the multimedia application performance, but its impact on network QoS is much smaller. We then present the solution, which is based on idealized weighted fair queuing (IWFQ) to further improve three popular multimedia applications' performance.