Current Research Projects
Controller Scalability in Software-Defined Networking
Our HyperFlow project was one of the first solutions that introduced the idea of a logically centralized, yet physically distributed controller for SDN, a major paradigm shift from the centralized controller model.
Following that line of work, we designed Kandoo a distributed controller designed for a data center environment. By focusing on network control applications requiring local state, and a hierarchical structure of network controllers we were able to create a scalable control platform.
Beehive is our latest distributed controller platform with an emphasis on simplifying the process of programming network controllers. It introduces a simple programming model that can be used to transforms a centralized network application into a distributed control system, while preserving the application’s intended behavior. In other words, network control applications are as simple as centralized applications to develop and implement for control application developers, yet the system automatically takes care of the boilerplates of the underlying distributing control system, thus hiding most of the complexities from network application developers.
Beehive is highly resilient to failures, provides a runtime instrumentation that allows debugging network applications, and dynamically migrates (live) control applications to optimize the control plane. It is capable of optimizing control applications after a failure or a change in the workload.
Reducing Flow Table Occupancy in SDN Switches
We present a new approach to minimize flow table occupancy based on the insight gained from the knapsack model analysis. Our solution expedites rule evictions by forecasting the TCP flow termination from RST/FIN packets and delays rule installation by incubating non-TCP flows. It reduces average flow table occupancy between 16%–62% in various networks with less than 1.5% reduction in hit ratio.
Explicit Rate Allocation in Data Center Networks
In this project, we use quantization of flow demands and rates by mapping continuous range of flow rates to a fixed number of bins. We show that, when used as a centralized solution for rate allocation in a software-defined network, such techniques can significantly speed up max-min fair rate allocation (reducing the run-time by 90−96%). Clearly, such quantization comes at the expense of flow rate distortions. Our experimental evaluation of three different quantization schemes shows that such distortions are small, and can be negligible compared to intrinsic errors in measuring rates in current solutions.
OpenTCP: Rethinking Congestion Control in Data Centers
We have deployed and tested OpenTCP in a data center environment and showed it can lead to significant improvements in TCP performance (e.g. 59% reduction in flow completion times, with a negligible overhead).
Buffer Sizing in Internet Routers
In 2005, Appenzeller et al. challenged this rule-of-thumb and showed that for a backbone network, the buffer size can be divided by sqrt(N) without sacrificing throughput, where N is the number of flows sharing the bottleneck.
Continuing that work, we showed how buffers in the backbone can be significantly reduced even more, to as little as a few dozen packets, if we are willing to sacrifice a small amount of link capacity. We argue that if the TCP sources are not overly bursty, then fewer than twenty packet buffers are sufficient for high throughput.
Traffic Classification in the Internet
In this project, we present CUTE, an automatic traffic classification scheme using a set of weighted terms to tackle both of these problems. CUTE relies on matching term sets which is considerably faster than regular expression matchings. Moreover, using term sets increases the hit rate as it can be used to classify partial or slightly modified flows and makes it possible to classify traffic only using the first few bytes of the flows. Replacing regular expressions with a set of terms might introduce errors in classification. However, our theoretical analysis shows that under conditions which hold in real protocols, by using appropriate weights for extracted terms, we can find a reasonably small bound for the error probability. We have evaluated CUTE using two large sets of packets traces collected from two large ISPs within two continents. Our experimental evaluation shows that using the weight function used in CUTE leads in very high accuracy and recall rates, even when only the first 50 bytes of each flow are used. Finally, CUTE is capable of labeing 60% of incomplete flows which other DPI techniques consider unknown.
Past Research Projects
DRILL: Micro Load Balancing for Data Center Networks
We present DRILL, a datacenter fabric for Clos networks which performs micro load balancing to distribute load as evenly as possible on microsecond timescales. DRILL employs per-packet decisions at each switch based on local queue occupancies and randomized algorithms to distribute load. Our design addresses the resulting key challenges of packet reordering and topological asymmetry. In simulations with a detailed switch hardware model and realistic workloads, DRILL outperforms recent edge-based load balancers, particularly under heavy load. Under 80% load, for example, it achieves 1.3-1.4× lower mean flow completion time than recent proposals, primarily due to shorter upstream queues.
Spam Detection in Internet Telephony
In this project, we study individual and network-wide characteristics of communications in a phone network with the objective of identifying "SPITters". We collect and analyze the data from one of the largest phone providers in North America. We consider phone communication as an indicator of social ties and propose a new technique, Loose Tie Detection (LTD) to identify outliers based on social ties. Second, we introduce Enhanced Progressive Multi Grey-Leveling (EPMG), which identifies outliers based on call density and reciprocity (i.e., how often a call in one direction can be associated with a call in the opposite direction). Finally, we propose SymRank, an adaptation of the PageRank algorithm that computes the reputation of subscribers based on both incoming and outgoing calls.
Complementing this work, we have also designed a system to direct any suspicious calls to a verification system. We have developed two new alternative ways to design CAPTCHAs in which the user says the answer instead of typing it with (a) output stimuli provided visually (SeeSay) or (b) auditorily (HearSay). Our user study results show that SeeSay CAPTCHA requires less time to be solved and users prefer it over current text-based CAPTCHA methods. This
Lockr: Privacy in Online Social Networks
We present the design of an access control scheme that makes sharing personal content easy. We have deployed this scheme on BitTorrent and Flickr, two popular systems for sharing content online. Our scheme is based on a simple insight -- we must decouple content delivery and sharing from managing social networking information. Our scheme lets people manage their social networks themselves (e.g., through their personal address books) while letting Web sites and Internet systems deliver content. For this, we introduce two new concepts -- social attestations and social access control lists (ACLs). At a high-level, a social attestation is a small piece of meta-data issued by one person to another encapsulating a social relationship. The recipient can use this attestation to prove the social relationship to any online site or to any other user. People exchange these attestations once while reusing them to gain access to their friends' personal content scattered across different sites and systems.
More information: Please visit the Lockr web page.
Volcano Routing Scheme
Routing in mobile ad-hoc networks is hard because the topology can change very rapidly. By the time new paths are discovered, the network can change again -- and in extreme cases, packets circulate endlessly and the system is unstable. Most attempts to solve this problem have required that the topology changes slowly. We propose a routing algorithm called Volcano Routing Scheme (VRS) which will route packets successfully, even if the topology changes very rapidly. VRS doesn't need to discover routes, or exchange routing information; it simply balances the load locally between adjacent pairs of nodes. We show that under some loose conditions on network topology changes, VRS keeps the system stable. Simulations also suggest that VRS is stable for various models of mobility, different communication patterns, and different amounts of flow in the network. Interestingly, we prove that when the network topology is static, packets follow the shortest path.
Another approach to alliviate the impact of topology changes in communication networks is multi-path routing. Multi-path routing has been studied thoroughly in the context of wired networks. It has been shown that using multiple paths to route messages between any source-destination pair of nodes (instead of using a single path) balances the load more evenly throughout the network. The common belief is that the same is true for ad hoc networks, i.e., multi-path routing balances the load significantly better than single-path routing. We show that this is not necessarily the case. We introduce a new model for evaluating the load balance under multi-path routing, when the paths chosen are the first K shortest paths (for a pre-specified K). Using this model, we show that unless we use a very large number of paths (which is very costly and therefore infeasible) the load distribution is almost the same as single shortest path routing. This is in contrary to the previous existing results which assume that multi-path routing distributes the load uniformly.
Packet Switching vs. Cell Switching
The problem of packet scheduling was first considered by Marsan et al. They showed that under any admissible Bernoulli IID (independent and identically distributed) arrival traffic, a simple modification of the Maximum Weight Matching (MWM) algorithm achieves 100% throughput. In this work, we first show that no work-conserving (i.e., maximal) packet-based algorithm is stable for arbitrary admissible arrival processes. Thus, the results of Marsan et al. are strongly dependent on the arrival distribution. We also propose a new class of waiting algorithms. We show that the waiting-MWM algorithm is stable for any admissible traffic using the fluid limit technique. The algorithms presented in this work are distribution independent or universal. The algorithms and proof methods may be useful in the context of other scheduling problems.
Interval Routing Scheme
When studying interval routing schemes, there are two main problems to be considered: a) Which classes of networks do support a specific routing scheme? b) Assuming that a given network supports IRS, how good are the paths traversed by messages? The first problem is known as the characterization problem and has been studied for several types of IRS. In this work, we study the characterization problem for various schemes in which the labels assigned to the vertices are d-ary integer tuples (d-dimensional IRS) and the label assigned to each link of the network is a list of d 1-dimensional intervals. This is known as Multi-dimensional IRS (MIRS) and is an extension of the the original IRS.
We completely characterize the class of network which support MIRS for linear (which has no cyclic intervals) and strict (which has no intervals assigned to a link at a node v containing the label of v) MIRS. In real networks usually the costs of links may vary over time (dynamic cost links). We also give a complete characterization for the class of networks which support a certain type of MIRS which routes all messages on shortest paths in a network with dynamic cost links. The main criterion used to measure the quality of routing (the second problem) is the length of routing paths. In this work we also investigate this problem for MIRS and prove two lower bounds on the length of the longest routing path. These are the only known general results for MIRS. Finally, we study the relationship between various types of MIRS and the problem of drawing a hyper-graph. Using some of our results we prove a tight bound on the number of dimensions of the space needed to draw a hyper-graph.