Reserach Details

General In-kernel accelaration of distributed application

In-kernel-acceleration is one of the techniques that current client-server applications use to have improved performance. I worked at IBM T. J. Watson Research Center in the Adaptive Fast Path Architecture (AFPA) group on their In-kernel Application Acceleration project. My focus was to develop an in-kernel mechanism that would accelerate AFPA web server in delivering dynamic content. The AFPA architecture consists of three main components: in-kernel cache that serves the static content, a layer-7 router that distinguishes between requests for static and dynamic content and a proxy that distributes the requests for dynamic content to a set of back-end servers. Although the AFPA web server architecture shows great performance in serving static content, it performs poorly while serving dynamic content. This is because the AFPA proxy has to establish new connections to the back end servers for dynamic content requests. I developed a design where the AFPA server can efficiently deliver the dynamic content generated by some user level web-server (like IIS, Tux etc.) on the same machine. Since both the AFPA server and the user-level server are on the same machine, there is no need to make new connections for the requests for dynamic content. The user level server puts the generated dynamic content in a pre-allocated pinned memory shared between both the user space and the kernel, and the in-kernel accelerator efficiently serves the content to the clients in the way similar to the way that it does for the static content. The design has an efficient communication mechanism for the user-level server and the in-kernel AFPA. The architecture showed good initial results. I think this in-kernel acceleration can be made more generic than HTTP alone and usable for many other network applications. Having such a feature in a secure fashion would be helpful for supporting distributed applications, e.g., it would be useful for fast overlay network routing, application level multicasting and peer-to-peer computing. I have designed a generic module in Windows NT that can be plugged into any client-server network applications and can accelerate some network-related functions by performing them from the kernel. The module is still a work in progress. I would like to extend the module to support large-scale distributed systems where the host machines do not have any central control. The generic module will be a great building block for high performance distributed systems.

Related publications: please see the AFPA group web page.

Multi-Modal Network Protocols
Aditya Akella, Ashwin Bharambe, and Srinivasan Seshan.

Most network protocols are uni-modal: they employ a single set of algorithms that allows them to cope well only within a narrow range of operating conditions. This rigid design renders these protocols inefficient in the face of widely varying operating environments or in conditions different from the ones for which they are optimized. Such uni-modal protocols have great difficulty in the mobile computing world where the operating conditions, including number of nodes, computational capabilities and rate of mobility, are not fixed.

Consider, for example, routing in a network of ad-hoc nodes. Solutions like DSDV work well when the number of nodes is small. Unfortunately, such schemes scale poorly to larger population sizes. In such situations, more scalable algorithms that impose a structure on the network of ad-hoc nodes, in a manner similar to routing protocols in the Internet, provides better results. However, these scalable algorithms tend to incur high overheads in situations that DSDV handles well. Clearly, no single routing solution handles all situations that a node may encounter.

Motivated by such examples, this paper attempts to answer the following question: Is it possible to redesign the traditional protocols to take on very different operating modes when faced with different environments? We present a case for such multi-modal protocols in our paper. Specifically, we discuss multi-modal reliability and routing. We show the feasibility of designing multi-modal protocols by describing how these protocols can make operating mode decisions and switch modes without additional overhead.

Related publications

Aditya Akella, Ashwin Bharambe, Suman Nath and Srini Seshan.
CMU SCS Technical Report Number CMU-CS-02-170.

Reconfigurable Computing

With Suraj Sudhir and Seth Copen Goldstein

Some recent reconfigurable computers incorporate the idea of caching and swapping the reconfigurable function units (RFU) in their fabrics. In the configuration caching and swapping project at CMU, I did research on finding efficient replacement policy for RFUs. The cache replacement problem for RFUs is inherently different from that for conventional virtual memory pages, since RFUs are of different sizes, different load-times, and there is the option to not load them into the fabric if it is costly to load. Although this variable-size, variable-cost, optional caching problem looks very similar to the web caching problem, there are some unique features in reconfigurable computing that made web caching algorithms perform poorly. I found an efficient cache replacement policy which uses the sizes and load latencies of the RFUs as well as recent RFU usage history to determine which RFU to evict. This helps minimize the total load latency of all executed RFUs. I also devised a simple implementation of this heuristic in hardware. The heuristic was found to outperform the existing algorithms in this domain.

Related publications:

Multemedia Security
With Vanish Talwar and
Klara Nahrstedt

During my short stay at the University of Illinois at Urbana-Champaign, I was involved in the systems project RSVP-QoS. My responsibility was to develop a secure, scalable and efficient resource reservation protocol (RSVP) so that malicious users (routers) cannot compromise the RSVP message to reserve excess resources on the routers and launch a denial of service attack. The existing approach was to digitally sign the reservation messages on each of the intermediate trusted routers, thus preventing the compromised routers from changing any messages. However, this is a costly operation and not appropriate for real-time applications. It was also clear that digitally signing the message by the sender and asking the receiver to check it would not work either, since the intermediate routers might legally modify the reservation messages. I encountered a fundamental problem of network security: how to protect integrity, in end-to-end fashion, of an object that is mutable along the route path. I found a solution to the problem in this particular domain that exploits the way that RSVP messages are modified by the routers on the path. I observed that some of the crucial values in RSVP message should only be decreased by the routers on the path, and compromised routers must increase their values to maliciously reserve more resources. Based on this observation, I devised a protocol where intermediate routers maintain soft-state and only the edge routers need to digitally sign the message. The overall result was that the protocol could detect some attacks that the existing protocol could not. The protocol was more scalable and faster in detecting tampering of RSVP messages. I also developed a prototype deploying the protocol.

Related publications:

Vanish Talwar, Suman Kumar Nath, and Klara Nahrstedt.
Proc. of IEEE International Conference on Multimedia and Expo 2001 (ICME2001), Tokyo, Japan, August, 2001.

SPINDEX: Flexible Search Mechanisms in Scalable Peer-to-Peer Systems

With Bruce Maggs and Srinivasan Seshan

The core operation in most peer-to-peer systems is efficient location of objects. While many existing systems have developed clever mechanisms to support this operation, they are still limited to some constrained set of queries. Most systems (e.g., Chord, CAN, PAST) can find a node containing some object given a key constructed from the object's name or content (usually by hashing). A few service discovery systems (e.g., Secure Service Discovery System) support flexible XML queries in a predefined set schema. However, such systems have been deployed on a far smaller scale than the peer-to-peer systems. It is not clear how very large scale systems of this type can support more general query styles such as regular expressions. My research goal is to support a much richer and expressible query language (like SQL, or XQUERY) in large-scale Internet-based peer-to-peer systems. The problem is very challenging considering the mammoth size of the whole system and the unstructured nature of the objects. One possible way to approach the problem can be to have some structured meta-data associated with each object and apply distributed database techniques, properly adapted to support large scale peer-to-peer systems, so that SQL-like queries can be issued on the structured metadata. Finding an efficient way to look up objects based on their contents in peer-to-peer systems is even more challenging. The solution can easily be extended to include wide area service discovery problems.