We present Policy Graph Abstraction (PGA) that graphically expresses network policies and service chain requirements, just as simple as drawing whiteboard diagrams. Different users independently draw policy graphs that can constrain each other. PGA graph clearly captures user intents and invariants and thus facilitates automatic composition of overlapping policies into a coherent policy.

Software Defined Networking (SDN) and cloud automation enable a large number of diverse parties (network operators, application admins, tenants/end-users) and control programs (SDN Apps, network services) to generate network policies independently and dynamically. Yet existing policy abstractions and frameworks do not support natural expression and automatic composition of high-level policies from diverse sources. We tackle the open problem of automatic, correct and fast composition of multiple independently specified network policies. We first develop a high-level Policy Graph Abstraction (PGA) that allows network policies to be expressed simply and independently, and leverage the graph structure to detect and resolve policy conflicts efficiently. Besides supporting ACL policies, PGA also models and composes service chaining policies, i.e., the sequence of middleboxes to be traversed, by merging multiple service chain requirements into conflict-free composed chains. Our system validation using a large enterprise network policy dataset demonstrates practical composition times even for very large inputs, with only sub-millisecond runtime latencies.

Resource conflicts are inevitable on any shared infrastructure. In Software-Defined Networks (SDNs), different controller modules with diverse objectives may be installed on the SDN controller. Each module independently generates resource requests that may conflict with the objectives of a different module. For example, a controller module for maintaining high availability may want resource allocations that require too much core network bandwidth and thus conflict with another module that aims to minimize core bandwidth usage. In such a situation, it is imperative to identify and install resource allocations that achieve network wide global objectives that may not be known to individual modules, e.g., high availability with acceptable bandwidth usage. This problem has received only limited attention, with most prior work focused on detecting, avoiding, and resolving rule-level conflicts in the context of OpenFlow.

We present a long term and large scale study of the experience of mobile users through two popular but contrasting applications in the wild. To conduct this study, we implemented a measurement framework and library, called Insight, which has been deployed on these two applications that are available through Apple's App Store and Google's Android Market. One of them, Parallel Kingdom (PK), is a popular massively multiplayer online role-playing game (MMORPG) which has over a million unique users distributed more than 120 countries. The other application, StudyBlue (SB), is an educational application with over 160,000 unique users. Our study spans most of the life of the PK game (more than 3 years) while our deployment with SB has been running for over a year now. We use Insight to collect diverse information about network behavior, application usage and footprints, platform statistics, user actions, and various factors affecting application revenues.

Geographically distributed storage is an important method of ensuring high data availability in cloud computing and storage systems. With the increasing demand for moving file systems to the cloud, current methods of providing such enterprise-grade resiliency are very inefficient. For example, replication based methods incur large storage cost though they provide low access latencies. While erasure coded schemes reduce storage cost, they are associated with large access latencies and high bandwidth cost. In this paper, we propose a novel scheme named CAROM, an ensemble of replication and erasure codes, to provide resiliency in cloud file systems with high efficiency. While maintaining the same consistency semantics seen in today's cloud file systems, CAROM provides the benefit of low bandwidth cost, low storage cost, and low access latencies. We perform a large-scale evaluation using real-world file system traces and demonstrate that CAROM outperforms replication based schemes in storage cost by up to 60% and erasure coded schemes in bandwidth cost by up to 43%, while maintaining low access latencies close to those in replication based schemes.

Ternary Content-Addressable Memories (TCAMs) has become the industrial standard for high-throughput packet classification. However, one major drawback of TCAMs is their high power consumption, which is becoming critical with the boom of data centers, the growing classifiers and the deployment of IPv6. In this paper, we propose a practical and efficient solution which introduces a smart pre-classifier to reduce power consumption of TCAMs for multi-dimensional packet classification. We reduce the dimension of the problem through the pre-classifier which pre-classifies a packet on two header fields, source and destination IP addresses. We then return to the high dimension problem where only a small portion of a TCAM is activated and searched for a given packet. The smart pre-classifier is built in a way such that a given packet matches at most one entry in the pre-classifier, which make commodity TCAMs sufficient to implement the pre-classifier. Furthermore, each rule is stored only once in one of the TCAM blocks, which avoids rule replication. The presented solution uses commodity TCAMs, and the proposed algorithms are easy to implement. Our scheme achieves a median power reduction of 91% and an average power reduction of 88% on real and synthetic classifiers respectively.

We present a software-based solution to the multi-dimensional packet classification problem which can operate at high line speeds, e.g., in excess of 10 Gbps, using high-end multi-core desktop platforms available today. Our solution, called Storm, leverages a common notion that a subset of rules are likely to be popular over short durations of time. By iden-tifying a suitable set of popular rules one can significantly speed up existing software-based classification algorithms. A key aspect of our design is in partitioning processor resources into various relevant tasks, such as continuously computing the popular rules based on a sampled subset of traffic, fast classification for traffic that matches popular rules, dealing with packets that do not match the most popular rules, and traffic sampling. Our results show that by using a single 8-core Xeon processor desktop platform, it is possible to sustain classification rates of more than 15 Gbps for rep-resentative rule sets of size in excess of 5-dimensional 9000 rules, with no packet losses. This performance is signifi-cantly superior to a 8-way implementation of a state-of-the-art packet classification software system running on the same 8-core machine. Therefore, we believe that our design of packet classification functions can be a useful classification building block for RouteBricks-style designs, where a core router might be constructed as a mesh of regular desktop machines.

A new multiple access control scheme for wireless ad hoc networks and WLANs is proposed. This scheme uses explicit denial of channel requests and a busy tone to improve channel throughput. Performance analysis shows significant improvement when the network is under heavy traffic load.