Due to a poor understanding of the interactions among transmitters, wireless networks using carrier sense multiple access with collision avoidance (CSMA/CA) have been commonly stigmatized as unpredictable in nature. Even elementary questions regarding the throughput limitations of these networks cannot be answered in general. In this paper, we investigate the behavior of wireless CSMA/CA networks to understand how the transmissions of a particular node affect the medium access, and ultimately the throughput, of other nodes in the network. We introduce a theory which accurately models the behavior of these networks and show that, contrary to popular belief, their performance is predictable and can be described by a system of equations. Using the proposed theory, we provide the analytical expressions necessary to fully characterize the capacity region of any wireless CSMA/CA network. We show that this region is nonconvex in general and agnostic to the probability distributions of all network parameters, depending only on their expected values. Our theory is also shown to extend naturally to time division multiple access (TDMA) networks and to predict how the network responds to infeasible input rates.

The rapid growth of server virtualization has ignited a wide adoption of software-based virtual switches, with significant interest in speeding up their performance. In a similar trend, software-defined networking (SDN), with its strong reliance on rule-based flow classification, has also created renewed interest in multi-dimensional packet classification. However, despite these recent advances, the performance of current software-based packet classifiers is still limited, mostly by the low parallelism of general-purpose CPUs. In this paper, we explore how to accelerate packet classification using the high parallelism and latency-hiding capabilities of graphic processing units (GPUs). We implement GPU-accelerated versions for both linear and tuple search, currently deployed in virtual switches, and also introduce a novel algorithm called Bloom search. These algorithms are integrated with high-speed packet I/O to build GSwitch, a GPU-accelerated software switch, and also to extend Open vSwitch. Our experimental evaluation indicates that, under realistic rule sets, GSwitch is at least 7 × faster than an equally-priced CPU classifier. We also show that our GPU-accelerated Open vSwitch outperforms the classic Open vSwitch implementation by a factor of 10, on average.

Internet users are interested in content regardless of its location; however, the current client/server architecture still requires requests to be directed to a specific server. Information-centric networking (ICN) is a recent vein that relaxes this requirement through the use of name-based forwarding, where forwarding decisions are based on content names instead of IP addresses. Despite previous name-based forwarding strategies have been proposed, almost none have actually built a content router. To fill this gap, in this paper we design and prototype a content router called Caesar for high-speed forwarding on content names. Caesar introduces several innovative features, including (i) a longest-prefix matching algorithm based on a novel data structure called prefix Bloom filter; (ii) an incremental design which allows for easy integration with existing protocols and network equipment;(iii) a forwarding scheme where multiple line cards collaborate in a distributed fashion; and (iv) support for offloading packet processing to graphics processing units (GPUs). We build Caesar as an enterprise router, and show that every line card sustains up to 10 Gbps using a forwarding table with more than 10 million content prefixes. Distributed forwarding allows the forwarding table to grow even further, and to scale linearly with the number of line cards at the cost of only a few microseconds in the packet processing latency. GPU offloading, in turn, trades off a few milliseconds of latency for a large speedup in the forwarding rate.

The rapid growth of server virtualization has ignited a wide adoption of software-based virtual switches, with significant interest in speeding up their performance. In a similar trend, software-defined networking (SDN), with its strong reliance on rule-based flow classification, has also created renewed interest in multi-dimensional packet classification. However, despite these recent advances, the performance of current software-based packet classifiers is still limited, mostly by the low parallelism of general-purpose CPUs. In this paper, we explore how to accelerate packet classification using the high parallelism and latency-hiding capabilities of graphic processing units (GPUs). We implement GPU-accelerated versions for both linear and tuple search, currently deployed in virtual switches, and also introduce a novel algorithm called Bloom search. These algorithms are integrated with high-speed packet I/O to build GSwitch, a GPU-accelerated software switch. Our experimental evaluation shows that GSwitch is at least 7x faster than an equally-priced CPU classifier and is able to reach 10 Gbps with minimum-sized packets and a rule set containing 128K OpenFlow entries with 512 different wildcard patterns.

Contemporary wireless multihop networks operate much below their capacity due to the poor coordination among transmitting nodes. In this paper, we present XPRESS, a cross-layer backpressure architecture designed to reach the capacity of wireless multihop networks. Instead of a collection of poorly coordinated wireless routers, XPRESS turns a mesh network into a wireless switch. Transmissions over the network are scheduled using a throughput-optimal backpressure algorithm. Realizing this theoretical concept entails several challenges, which we identify and address with a cross-layer design and implementation on top of our wireless hardware platform. In contrast to previous work, we implement and evaluate backpressure scheduling over a TDMA MAC protocol, as it was originally proposed in theory. Our experiments in an indoor testbed show that XPRESS can yield up to 128% throughput gains over 802.11.

Due to a poor understanding of the interactions among transmitters, wireless multihop networks have commonly been stigmatized as unpredictable in nature. Even elementary questions regarding the throughput limitations of these networks cannot be answered in general. In this paper we investigate the behavior of wireless multihop networks using carrier sense multiple access with collision avoidance (CSMA/CA). Our goal is to understand how the transmissions of a particular node affect the medium access, and ultimately the throughput, of other nodes in the network. We introduce a theory which accurately models the behavior of these networks and show that, contrary to popular belief, their performance is easily predictable and can be described by a system of equations. Using the proposed theory, we provide the analytical expressions necessary to fully characterize the capacity region of any wireless CSMA/CA multihop network. We show that this region is nonconvex in general and entirely agnostic to the probability distributions of all network parameters, depending only on their expected values.

In this paper we present a new routing paradigm for wireless multihop networks. In plasma routing, each packet is delivered over the best available path to one of the gateways. The choice of the path and gateway for each packet is not made beforehand by the source node, but rather on-the-fly by the mesh routers as the packet traverses the network. We propose a distributed routing algorithm to jointly optimize the transmission rate and the set of gateways each node should use. A load balancing technique is also proposed to disperse the network traffic among multiple gateways. We validate our proposal with simulations and show that plasma routing outperforms the state-of-the-art multirate anypath routing paradigm, with a 98% throughput gain and a 2.2x delay decrease. Finally, we also show that the load can be evenly distributed among gateways with a similar routing cost, resulting in a further 63% throughput gain.

In this paper, we present a new routing paradigm that generalizes opportunistic routing for wireless multihop networks. In multirate anypath routing, each node uses both a set of next-hops and a selected transmission rate to reach a destination. Using this rate, a packet is broadcast to the nodes in the set, and one of them forwards the packet on to the destination. To date, there is no theory capable of jointly optimizing both the set of next-hops and the transmission rate used by each node. We solve this by introducing two polynomial-time routing algorithms and provide the proof of their optimality. The proposed algorithms have roughly the same running time as regular shortest-path algorithms and are therefore suitable for deployment in routing protocols. We conducted measurements in an 802.11b testbed network, and our trace-driven analysis shows that multirate anypath routing is on average 80% better than 11-Mbps anypath routing, with a factor of 6.4 improvement in the best case. If the rate is fixed at 1 Mbps instead, performance improves by a factor of 5.4 on average.

The Bloom filter is a space-efficient data structure often employed in distributed applications to save bandwidth during data exchange. These savings, however, come at the cost of errors in the shared data, which are usually assumed low enough to not disrupt the application. We argue that this assumption does not hold in a more hostile environment, such as the Internet, where attackers can send a carefully crafted Bloom filter in order to break the application. In this paper, we propose the concatenated Bloom filter (CBF), a robust Bloom filter that prevents the attacker from interfering on the shared information, protecting the application data while still providing space efficiency. Instead of using a single large filter, the CBF concatenates small subfilters to improve both the filter robustness and capacity. We propose three CBF variants and provide analytical results that show the efficacy of the CBF for different scenarios. We also evaluate the performance of our filter in an IP traceback application and simulation results confirm the effectiveness of the proposed mechanism in the face of attackers.

Anonymity is one of the main motivations for conducting denial-of-service attacks. Currently, there is no mechanism to either identify the true source of an IP packet or to prove its authenticity. In this paper we propose a stateless IP traceback technique that identifies the origin network of each individual packet. We show that the proposed traceback system is the only one that scales with the number of attackers and also satisfies practical requirements, such as no state stored at routers and a header overhead (25 bits) that can be allocated in IPv4 header. The proposed system exploits the customer-provider hierarchy of the Internet at autonomous system (AS) level and introduces the idea of checkpoints, which are the two most important nodes in an AS-level path. Simulation results using a real-world topology trace show that the proposed system narrows the source of an attack packet down to less than two candidate ASes on average. In addition, considering a partial deployment scenario, we show that the proposed system is able to successfully trace more than 90% of the attacks if only 8% of the ASes (i.e., just the core ASes) implement the system. The achieved success rate is quite better than using the classical hop-by-hop path reconstruction.

Contemporary wireless multi-hop networks operate much below their capacity due to the poor coordination among transmitting nodes. In this paper we present XPRESS, a cross-layer backpressure architecture designed to reach the full capacity of wireless multi-hop networks. Instead of a collection of poorly coordinated wireless routers, XPRESS turns a mesh network into a wireless switch. Transmissions over the network are scheduled using a throughput-optimal backpressure algorithm. Realizing this theoretical concept entails several challenges, which we identify and address with a cross-layer design and implementation on top of our wireless hardware platform. In contrast to previous work, we implement and evaluate backpressure scheduling over a TDMA MAC protocol, as it was originally proposed in theory. Our experiments in an indoor testbed show that XPRESS can yield up to 128% throughput gains over 802.11.

In this paper, we propose a human-based model which builds a trust relationship between nodes in an ad hoc network. The trust is based on previous individual experiences and on the recommendations of others. We present the Recommendation Exchange Protocol (REP) which allows nodes to exchange recommendations about their neighbors. Our proposal does not require disseminating the trust information over the entire network. Instead, nodes only need to keep and exchange trust information about nodes within the radio range. Without the need for a global trust knowledge, our proposal scales well for large networks while still reducing the number of exchanged messages and therefore the energy consumption. In addition, we mitigate the effect of colluding attacks composed of liars in the network. A key concept we introduce is the relationship maturity, which allows nodes to improve the efficiency of the proposed model for mobile scenarios. We show the correctness of our model in a single-hop network through simulations. We also extend the analysis to mobile multihop networks, showing the benefits of the maturity relationship concept. We evaluate the impact of malicious nodes that send false recommendations to degrade the efficiency of the trust model. At last, we analyze the performance of the REP protocol and show its scalability. We show that our implementation of REP can significantly reduce the number messages.

In this paper, we present a new routing paradigm that generalizes opportunistic routing in wireless mesh networks. In multirate anypath routing, each node uses both a set of next hops and a selected transmission rate to reach a destination. Using this rate, a packet is broadcast to the nodes in the set and one of them forwards the packet on to the destination. To date, there is no theory capable of jointly optimizing both the set of next hops and the transmission rate used by each node. We bridge this gap by introducing a polynomial-time algorithm to this problem and provide the proof of its optimality. The proposed algorithm runs in the same running time as regular shortest-path algorithms and is therefore suitable for deployment in link-state routing protocols. We conducted experiments in a 802.11b testbed network, and our results show that multirate anypath routing performs on average 80% and up to 6.4 times better than anypath routing with a fixed rate of 11 Mbps. If the rate is fixed at 1 Mbps instead, performance improves by up to one order of magnitude.

Slander attacks represent a significant danger to distributed reputation systems. Malicious nodes may collude to lie about the reputation of a particular neighbor and cause serious damage to the overall trust evaluation system. This paper presents and analyzes a trust model robust to slander attacks in ad hoc networks. We provide nodes with a mechanism to build a trust relationship with its neighbors. The proposed model considers the recommendation of trustworthy neighbors and the previous experiences of the node itself. The interactions are limited to direct neighbors in order to scale on mobile networks. The results show the impact of slander attacks to our trust model. We analyze how the main parameters affect the trust evaluation process under a lying collusion attack. We show that our trust model tolerate almost 40% of liars.

This paper analyzes a trust model for mobile ad hoc networks. We provide nodes with a mechanism to build a trust relationship with its neighbors. The proposed model considers the recommendation of trustworthy neighbors and the experience of the node itself. The interactions are limited to direct neighbors in order to scale on mobile networks. The results show the efficiency and the trade-off of our model in the presence of mobility. We also analyze the advantages of considering the relationship maturity, i.e. for how long nodes know each other, to evaluate the trust level. The maturity parameter can decrease the trust level error up to 50%.

The current Internet architecture allows malicious nodes to disguise their origin during denial-of-service attacks with IP spoofing. A well-known solution to identify these nodes is IP traceback. In this paper, we introduce and analyze a lightweight single-packet IP traceback system that does not store any data in the network core. The proposed system relies on a novel data structure called Generalized Bloom Filter, which is tamper resistant. In addition, an efficient improved path reconstruction procedure is introduced and evaluated. Analytical and simulation results are presented to show the effectiveness of the proposed scheme. The simulations are performed in an Internet-based scenario and the results show that the proposed system locates the real attack path with high accuracy.