Spreader classification is an online traffic measurement function that has many important applications. In order to keep up with ever-higher line speed, the recent research trend is to implement such functions in fast but small on-die SRAM. However, the mismatch between the huge amount of Internet traffic to be monitored and limited on-die memory space presents a significant technical challenge. In this paper, we propose an Efficient Spreader Classification (ESC) scheme based on dynamic bit sharing, a compact information storage method. We design a maximum likelihood estimation method to extract per-source information from the compact storage and determine the heavy spreaders. Our new scheme ensures that false positive/negative ratios are bounded. Moreover, given an arbitrary set of bounds, we develop a systematic approach to determine the optimal system parameters that minimize the amount of memory needed to meet the bounds. Experiments based on a real Internet traffic trace demonstrate that the proposed spreader classification scheme reduces memory consumption by 3–20 times when compared to the best existing work. We also investigate a new multi-objective spreader classification problem and extend our classification scheme to solve it.

Similar to the revolutionary change that the barcode system brought to the retail industry, the RFID technologies are expected to revolutionize the warehouse and inventory management. After RFID tags are deployed to make the attached objects wirelessly identifiable, a natural next step is to invent new ways to benefit from this “infrastructure”. For example, sensors may be added to these tags to gather real-time information about the state of the objects or about the environment where these objects reside. This leads to the problem of designing efficient protocols to collect such information from the tags. It is a new problem that the existing work cannot solve well. In this paper, we first show that a straightforward polling solution will not be efficient. We then propose a single-hash information collection protocol that works much better than the polling solution. However, a wide gap still exists between the execution time of this protocol and a lower bound that we establish. Finally, we propose a multi-hash information collection protocol that further reduces the expected execution time to within 1.61 times the lower bound.

Scan detection is one of the most important functions in intrusion detection systems. In order to keep up with the ever-higher line speed, recent research trend is to implement scan detection in fast but small SRAM. This leads to a difficult technical challenge because the amount of traffic to be monitored is huge but the on-die memory space for performing such a monitoring task is very limited. We propose an efficient scan detection scheme based on dynamic bit sharing, which incorporates probabilistic sampling and bit sharing for compact information storage. We design a maximum likelihood estimation method to extract persource information from the shared bits in order to determine the scanners. Our new scheme ensures that the false positive/false negative ratios are bounded with high probability. Moreover, given an arbitrary set of bounds, we develop a systematic approach to determine the optimal system parameters that minimize the amount of memory needed to meet the bounds. Experiments based on a real Internet traffic trace demonstrate that the proposed scan detection scheme reduces memory consumption by three to twenty times when comparing with the best existing work.

We demonstrate that CSMA/CA networks, including IEEE 802.11 networks, exhibit severe fairness problem in many scenarios, where some hosts obtain most of the channel's bandwidth while others starve. Most existing solutions require nodes to overhear transmissions made by contending nodes and, based on the overheard information, adjust local rates to achieve fairness among all contending links. Their underlying assumption is that transmissions made by contending nodes can be overheard. However, this assumption holds only when the transmission range is equal to the interference range, which is not true in reality. As our study reveals, the overhearing-based solutions, as well as several nonoverhearing AIMD solutions, cannot achieve MAC-layer fairness in various settings. We propose a new rate control protocol, called Proportional Increase Synchronized multiplicative Decrease (PISD). Without relying on overhearing, it provides fairness in CSMA/CA networks, particularly IEEE 802.11 networks, by using only local information and performing localized operations. It combines several novel rate control mechanisms, including synchronized multiplicative decrease, proportional increase, and background transmission. We prove that PISD converges and achieves (weighted) fairness. We further introduce Queue Spreading (QS) to achieve MAC-layer fairness when there are multiple contention groups, in which case PISD will fail.

Contention among multiple nearby WLANs in urban areas may cause severe TCP unfairness, where some TCP flows can achieve very high throughput at the expense of starving others. This unfairness results from the fact that different physical nodes conveying TCP flows at a wireless bottleneck may have different channel observations and consequently they may provide inconsistent feedbacks to the TCP sources. Existing solutions to this problem try to synchronize channel observations of contending nodes by exchanging control messages among them. They rely on the assumption that these nodes are within each other''s transmission range, which however may not always hold. In this paper, we propose a new approach, called Wireless Probabilistic Drop (WPD), to improve TCP fairness without requiring direct communication among nodes. In WPD, when a node detects congestion, it probabilistically chooses to either drop some packets to resolve the congestion, or aggressively spread the congestion signal to other contending nodes. Each node makes the choice with a probability that is proportional to its flow rate. Henceforth, high-rate flows tend to perform rate reduction more often, and low-rate flows are more likely to increase their flow rates. Eventually, all flows passing the bottleneck are expected to get a fair share of the channel bandwidth. Extensive simulations in ns-2 demonstrate that WPD can significantly improve fairness among TCP flows across multiple contending WLANs.

RFID promises to revolutionize the inventory management in large warehouses, retail stores, hospitals, transportation systems, etc. Periodically reading the IDs of the tags is an important function to guard against administration error, vendor fraud and employee theft. Given the low-speed communication channel in which a RFID system operates, the reading throughput is one of the most important performance metrics. The current protocols have reached the physical throughput limit that can possibly be achieved based on their design methods. To break that limit, we have to apply fundamentally different approaches. This paper investigates how much throughput improvement the analog network coding can bring when it is integrated into the RFID protocols. The idea is to extract useful information from collision slots when multiple tags transmit their IDs simultaneously. Traditionally, those slots are discarded. With analog network coding, we show that a collision slot is almost as useful as a non-collision slot in which exactly one tag transmits. We propose the framed collision-aware tag identification protocol that optimally applies analog network coding to maximize the reading throughput, which is 51.1% ~ 70.6% higher than the best existing protocols.

Wireless LANs have been densely deployed in many urban areas. Contention among nearby WLANs is location-sensitive, which makes some hosts much more capable than others to obtain the channel for their transmissions. Another reality is that wireless hosts use different transmission rates to communicate with the access points due to attenuation of their signals. We show that location-sensitive contention aggravates the throughput anomaly caused by different transmission rates. It can cause throughput degradation and host starvation. This paper studies the intriguing interaction between location-sensitive contention and time fairness across contending WLANs. Achieving time fairness across multiple WLANs is a very difficult problem because the hosts may perceive very different channel conditions and they may not be able to communicate and coordinate their operations due to the disparity between the interference range and the transmission range. In this paper, we design a MAC-layer time fairness solution based on two novel techniques: channel occupancy adaptation, which applies AIMD on the channel occupancy of each flow, and queue spreading, which ensures that all hosts and only those hosts in a saturated channel detect congestion and reduce their channel occupancies in response. We show that these two techniques together approximate the generic adaptation algorithm for proportional fairness.

Sensor networks deployed in hostile areas are subject to node replication attacks, in which an adversary compromises a few sensors, extracts the security keys, and clones them in a large number of replicas, which are introduced into the network to perform insider attacks. Memory overhead, energy efficiency and detection probability are the main technical concerns for any replication detection protocol. The previous distributed solutions either require network-wide spontaneous change of pseudo-random numbers or incur significant memory and energy overhead to the sensors, especially in the central area of the deployment. In this paper, we propose four replication detection protocols that have high detection probability, low memory requirement, and balanced energy consumption. The new protocols use Bloom filters to compress the information stored at the sensors, and use two new techniques, called cell forwarding and cross forwarding, to improve detection probability, further reduce memory consumption, and in the mean time distribute the memory and energy overhead evenly across the whole network. Simulations show that the protocols can achieve nearly 100% detection probability with average memory reduction up to 91%.

A wireless mesh network (WMN) provides a flexible and low-cost solution for end users to connect to the Internet through its multi-hop infrastructure. For such a network to proliferate, a fundamental problem that must be solved is to ensure the fair allocation of network bandwidth to all participating parties. This paper proposes a cross-layer design for achieving end-to-end maxmin fairness in WMNs. At the network layer, it allocates maxmin shares of network capacity to end-to-end flows. At the MAC layer, it realizes the maxmin bandwidth allocation through a two-level packet scheduling algorithm. The proposed design is able to equalize the end-to-end bandwidth allocation to competing flows that share common bottlenecks, while fully utilizing the network capacity. Comparing with previous works, our solution has two advantages. It is based on the popular IEEE 802.11 DCF. It achieves far better fairness (or weighted fairness) among end-to-end flows.

In wireless sensor networks (WSNs), timeliness is one of the most challenging problems for critical applications. Caccamo et al. designed a collision-free real-time MAC protocol for sensor networks by adopting the "cellular structure" in traditional telecommunication networks. They assumed that sensors are organized into many rigid hexagon cells and a router node is at the center of each cell to transmit inter-cell packets. By exploiting FDMA and TDMA, transmission collisions are avoided and real-time guarantees are provided. However, we observe that for inter-cell communication, idle-slots caused by the TDMA-based scheduling will degrade the throughput and delay performance of the entire network, especially for some real applications in which data flows have traffic-direction partiality characteristics. In the worst case, five sixths of inter-cell bandwidth will be wasted. In this paper, we propose four idle-slot recycling algorithms to improve channel utilization. Simulation results show that our proposed algorithms can greatly increase network throughput and decrease packet transmission delay, while the collision-free and real-time qualities of Caccamo's protocol are still retained.