One critical challenge of managing modern data center networks lies in that existing network protocols provide limited visibility on the internal routing and forwarding decisions made by the control plane, leading to difficulties on fast diagnosis and identification of root causes for performance bugs and anomalies. In this paper, we develop and evaluate a “debugging mode” for packet forwarding, where we demonstrate a possible design space by introducing a programmable header field into data packets used for diagnosis purposes. These headers can be manipulated by routers in intermediate hops to perform tracing and diagnosis operations, thereby providing much greater visibility on the control plane and data plane operations. To make this design scalable and feasible, we exploit the software APIs provided by the latest software-defined networking (SDN) technologies, where the network control plane is separated from the underlying data plane, so that we can reprogram the network forwarding functions dynamically. Compared to existing alternative approaches, our approach is adaptive and programmable, allowing dynamic and on-demand receiver-side decoding with extremely low overhead. We emphasize that as this “debugging mode” can be enabled and disabled by network managers as demanded, it introduces zero overhead to normal traffic if everything is operating as expected. Our evaluation results on a real SDN network testbed demonstrate the effectiveness of the proposed approaches.

As one of the most popular cloud services, data storage has attracted great attention in recent research efforts. Key-value (k-v) stores have emerged as a popular option for storing and querying billions of key-value pairs. So far, existing methods have been deterministic. Providing such accuracy, however, comes at the cost of memory and CPU time. In contrast, we present an approximate k-v storage for cloud-based systems that is more compact than existing methods. The tradeoff is that it may, theoretically, return errors. Its design is based on the probabilistic data structure called “bloom filter”, where we extend the classical bloom filter to support key-value operations. We call the resulting design as the kBF (key-value bloom filter). We further develop a distributed version of the kBF (d-kBF) for the unique requirements of cloud computing platforms, where multiple servers cooperate to handle a large volume of queries in a load-balancing manner. Finally, we apply the kBF to a practical problem of implementing a state machine to demonstrate how the kBF can be used as a building block for more complicated software infrastructures.

In many network applications, accurate traffic measurement is critical for bandwidth management with QoS requirements, and detecting security threats such as DoS (Denial of Service) attacks. In such cases, traffic is usually modeled as a collection of flows, which are identified based on certain features such as IP address pairs. One central problem is to identify those "heavy hitter" flows, which account for a large percentage of total traffic, e.g., at least 0.1% of the link capacity. However, the challenge for this goal is that keeping an individual counter for each flow is too slow, costly, and non-scalable. In this paper, we describe a novel data structure called the Probabilistic Bloom Filter (PBF), which extends the classical bloom filter into the probabilistic direction, so that it can effectively identify heavy hitters. We analyze the performance, tradeoffs, and capacity of this data structure. Our study also investigates how to calibrate this data structure's parameters. We also develop two extensions of the basic form of the PBF for more flexible application needs. We use real network traces collected on a Web query server and a backbone router to test the performance of the PBF, and demonstrate that this method can accurately keep track of all objects' frequencies, including websites and flows, so that heavy hitters can be identified with constant time computational complexity and low memory overhead.

Key-value (k-v) storage has been used as a crucial component for many network applications, such as social networks, online retailing, and cloud computing. Such storage usually provides support for operations on key-value pairs, and can be stored in memory to speed up responses to queries. So far, existing methods have been deterministic: they will faithfully return previously inserted key-value pairs. Providing such accuracy, however, comes at the cost of memory and CPU time. In contrast, in this paper, we present an approximate k-v storage that is more compact than existing methods. The tradeoff is that it may, theoretically, return a null value for a valid key with a low probability, or return a valid value for a key that was never inserted. Its design is based on the probabilistic data structure called the “Bloom Filter”, which was originally developed to test element membership in sets. In this paper, we extend the bloom filter concept to support key-value operations, and demonstrate that it still retains the compact nature of the original bloom filter. We call the resulting design as the kBF (key-value bloom filter), and systematically analyze its performance advantages and design tradeoffs. Finally, we apply the kBF to a practical problem of implementing a state machine in network intrusion detection to demonstrate how the kBF can be used as a building block for more complicated software infrastructures.