Research
Before industry, I spent six years doing research in distributed systems and networking, mostly on one question: how can a system understand an application from the outside and adapt to it automatically?
PhD, Northwestern University
-
Black Box Methods for Inferring Parallel Applications' Properties in Virtual Environments
PhD dissertation, Computer Science, Northwestern University 2002 – 2008
Defended March 2008. Advised by Prof. Peter Dinda.
Dissertation (PDF) Defense talk (PPT) Original proposal (DOC)
Abstract
Virtual machine based distributed computing greatly simplifies and enhances adaptive/autonomic computing by lowering the level of abstraction, benefiting both resource providers and users. We are developing Virtuoso, a middleware system for virtual machine shared-resource computing (e.g. grids) that provides numerous advantages and overcomes many obstacles a user faces in using shared resources for deploying distributed applications. A major hurdle for distributed applications to function in such an environment is locating, reserving/scheduling and dynamically adapting to the appropriate communication and computational resources so as to meet the applications' demands, limited by cost constraints. Resources can be very heterogeneous, especially in wide area or shared infrastructures, and their availability is also highly dynamic.
To achieve such automated adaptation, one must first learn about the various demands and properties of the distributed application running inside the VMs. My thesis is that it is feasible to infer the applications' demands and behavior, to a significant degree, without actually knowing much about the application or its operating system; I have investigated and demonstrated numerous novel techniques to infer many useful properties of parallel applications, in an automated fashion. Throughout my work I have used a black box approach to inference. Thus the results are applicable to existing, unmodified applications and operating systems and are widely applicable.
I show how to infer the communication behavior and the runtime topology of a parallel application. I also show how to infer very useful runtime properties of a parallel application such as its runtime performance. I have developed the algorithms to understand quantitatively the slowdown of an application under external load to find global bottlenecks at the resource and process level using time decomposition of the application's execution.
In addition, my dissertation also gives limited evidence and points to other work that shows that this inferred information can actually be used to benefit the application, without having any knowledge of the application/OS itself.
Research projects
-
Virtuoso: adaptive virtual machine computing
Years before cloud computing went mainstream, Virtuoso imagined ordering a cluster of virtual machines from a website and using it with one click. My part was automatic application inference: watching a distributed application's network traffic from outside the VMs, working out its communication topology and bandwidth needs, and then adapting the virtual network and VM placement to make it faster, with no changes to the application. This included traffic monitoring and inference in VNET, our layer-2 virtual overlay network, and became the core of my dissertation.
-
User comfort with resource borrowing
How much CPU, memory, and disk can background work (think SETI@home or Folding@home) borrow from someone's computer before they notice and get annoyed? We built a Windows client that created precisely controlled contention and recorded user feedback, and found that far more aggressive borrowing is possible than people assumed, not just in screensaver mode.
-
Sketch-based monitoring of high-speed networks
Algorithms for spotting heavy changes and anomalies in 10–20 Gbps traffic streams in real time, without offline analysis, built on the k-ary sketch data structure and a "reverse hashing" technique for recovering the culprit keys. This line of work grew from an IMC paper into INFOCOM and IEEE/ACM Transactions on Networking publications.
-
Keyword search and popularity in peer-to-peer networks
Magnolia, a DHT architecture designed for flexible keyword search with bounded performance, good load balance, and resilience in very large peer-to-peer networks with high churn, and Distributed Popularity Indices for ranking content across such networks. Presented as posters at NSDI 2005 and SIGCOMM 2005.
-
Gossip-based monitoring for peer-to-peer systems
An efficient monitoring service that spreads resource information across a P2P network using epidemic (gossip) protocols, so applications can use the network intelligently.
Publications
- Reversible Sketches: Enabling Monitoring and Analysis over High-speed Data Streams IEEE/ACM Transactions on Networking, 2007
- The User in Experimental Computer Systems Research Workshop on Experimental Computer Science (ExpCS), June 2007
- Free Network Measurement for Adaptive Virtualized Distributed Computing 20th International Parallel and Distributed Processing Symposium (IPDPS), April 2006. A poster appeared at ACM/IEEE SC 2005.
- Reverse Hashing for High-speed Network Monitoring: Algorithms, Evaluation, and Applications 25th IEEE Conference on Computer Communications (INFOCOM), April 2006
- Distributed Popularity Indices ACM SIGCOMM 2005 (poster)
- Increasing Application Performance in Virtual Environments through Run-time Inference and Adaptation 14th IEEE International Symposium on High Performance Distributed Computing (HPDC), 2005
- Magnolia: A Novel DHT Architecture for Keyword-based Searching 2nd Symposium on Networked Systems Design and Implementation (NSDI), 2005 (poster)
- Measuring and Understanding User Comfort with Resource Borrowing 13th IEEE International Symposium on High Performance Distributed Computing (HPDC), 2004
- Reverse Hashing for Sketch-based Change Detection ACM SIGCOMM Internet Measurement Conference (IMC), October 2004 (short paper)
- Inferring the Topology and Traffic Load of Parallel Programs Running in a Virtual Machine Environment 10th Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP), June 2004
- Dynamic Topology Adaptation of Virtual Networks of Virtual Machines 7th Workshop on Languages, Compilers, and Run-time Support for Scalable Systems (LCR), Houston, 2004
- QoS Aware Path Protection Schemes for MPLS Networks Presented at ICCC 2002 (slides)
Technical reports
- Free Network Measurement for Adaptive Virtualized Distributed Computing Technical Report NWU-CS-05-13, Northwestern University, June 2005. Also Technical Report WM-CS-2005-05, College of William and Mary.
- Reverse Hashing for Sketch-based Change Detection on High-speed Networks Technical Report NWU-CS-2004-45, Northwestern University, 2004
- A Framework and Toolkit for Understanding User Comfort with Resource Borrowing Technical Report NWU-CS-04-28, Northwestern University, February 2004
- Fast Resource Information Dissemination in a P2P Network Technical Report, Northwestern University, March 2003
Talks
- Black Box Methods for Inferring Parallel Applications' Properties in Virtual Environments
- Measuring and Understanding User Comfort with Resource Borrowing
- Reverse Hashing for Sketch-based Change Detection in High-speed Networks
- Dynamic Topology Adaptation of Virtual Networks of Virtual Machines
- Inferring the Topology and Traffic Load of Parallel Programs in a VM Environment
- Understanding User Comfort with Resource Borrowing
- Measuring ISP Topologies with Rocketfuel
- Maximum Likelihood Network Topology Identification
- Self-Similarity in Network Traffic
- Extensible Cluster-Based Network Services
- Behavioral Aspects of Text Editors
- Virtual Private Networks and Spawning Networks
- DNA Computing
- QoS Aware Path Protection Schemes for MPLS Networks
Patent
-
Methods and Systems for Automatic Inference and Adaptation of Virtualized Computing Environments
Systems that automatically infer what a distributed application running in virtual machines needs, and adapt the virtual environment, including network topology, routing, and VM placement, to improve its performance.
Research internships
-
Google
Engineering Intern 2006
AdSense: designed a new ad delivery algorithm and built a system for boosting ad relevance and click rates.
-
Intel Labs
Research Intern 2005 and 2006
Two internships across Intel's Pittsburgh (with CMU) and Cambridge, UK labs: distributed algorithms for particle-based modular robotics, including an OpenGL simulator for them, and algorithms and design for high-performance packet classification.
-
IBM Research
Research Intern Summer 2002
Tools for developing large-scale distributed applications for e-government, at IBM's lab in New Delhi. Project page and report
Before the PhD
-
QoS Aware Path Protection Schemes for MPLS Networks
B.Tech thesis, Computer Science and Engineering, IIT Delhi 1998 – 2002
A "segment-based" approach to protecting MPLS paths that guarantees QoS, such as delay, jitter, and bounded switch-over time, even after a failure, while using less bandwidth than existing schemes. Advised by Prof. B.N. Jain in the Advanced Networking Laboratory.
Received the Best B.Tech Project Award in the Computer Science department and the ICIM Stay Ahead Award for the best project in Information Technology and Computing Sciences.
Thesis report (PDF) Paper (PDF) Award presentation (PPT) Final presentation (PPT)
