Research

My research interests are broadly in distributed systems and networks. My Ph.D. research is mainly focused on P2P networks: In a nutshell, I recognize functionalities frequently needed by various P2P applications, and aim to provide them via a common substrate that is efficient, scalable, and robust. The first part of this endeavor was the Swaplinks algorithm that provides distributed heterogeneous random graph construction and random peer selection. The second part is concerned with finding nearby peers in P2P systems.

I have also worked on network rate estimation, fair P2P resource-sharing, and real-time services in ad-hoc wireless networks.

Finding the nearest peer in P2P systems: A fundamentally hard problem?

Finding the nearest peer, in terms of latency, is an important problem in many Internet applications. In this paper, we argue that solutions that only examine inter-peer latencies as part of their operation will find it infeasible, in certain cases, to discover the nearest peer in P2P systems. The difficulty arises out of the way the last hop is typically laid out in the Internet, where a single PoP (point of presence) belonging to an ISP provides connectivity to numerous client networks. This setup leads to a large number of peers being at about the same latency from one another, which, we argue, presents a serious obstacle when a peer tries to discover another peer residing in the same network as itself. We use large-scale measurements over Internet hosts to show that this is a real concern. Paper currently under submission.

Random graph construction and peer selection in P2P networks

All P2P applications need a graph to communicate over, and many (like file-sharing applications, overlay multicast, etc.) also need the basic functionality of periodically selecting random peers from the entire P2P system. Moreover, both of these facets, namely graph construction and peer selection, have implications on the amount of load imposed on each peer, in terms of bandwidth, or CPU load for example. A fundamental fact in the area of P2P systems is that peers are heterogeneous, i.e., load-bearing capacity differs widely from peer to peer; accordingly, any algorithm providing these features should ensure that the eventual load imposed respects node capacities.

We designed and implemented the Swaplinks unstructured algorithm for heterogeneous graph construction and peer selection. In Swaplinks, each peer's degree, its probability of selection, and the load imposed on it are all directly proportional to its capacity. In the first part of this work, we evaluated several unstructured schemes (some variations on existing approaches, and some novel) for heterogeneous graph construction and peer selection using simulations, and identified the Swaplinks algorithm as the most attractive. In addition to exhibiting the properties mentioned above, it has just a single tuning parameter (the desired node-degree at each peer), and thus very simple to deploy. This work was published at Infocom 2006.

Next, we implemented the Swaplinks algorithm, and examined the question of whether the problem of heterogeneous selection is better solved by an unstructured approach, or by a structured approach. We compared candidate techniques from each domain, Swaplinks from the unstructured domain, and KRB (an adapted Karger-Ruhl approach implemented over Bamboo) from the structured domain, and concluded that the unstructured approach (Swaplinks) is the superior random selection technique. Swaplinks results in more accurate heterogeneous selection, especially in the face of churn, and is much simpler than KRB to configure. This work was published at the 2007 Usenix Technical Conference.

In more recent work, we eliminated the single tuning parameter in Swaplinks to realize a completely parameter-free random selection primitive. Nodes use distributed computations to get an approximate view of the global capacity distribution, and thus have sufficient information to compute their desired degrees on their own. This work appeared at the IPTPS 2008 workshop.

On Heterogeneous Overlay Construction and Random Node Selection in Unstructured P2P Networks [PDF]
Vivek Vishnumurthy and Paul Francis
Infocom 2006, Barcelona, Spain

A Comparison of Structured and Unstructured P2P Approaches to Heterogeneous Random Peer Selection [PDF]
Vivek Vishnumurthy and Paul Francis
Usenix Annual Technical Conference, 2007, Santa Clara, California

A Parameter-Free Load Balancing Mechanism For P2P Networks. [PDF]
Tyler Steele, Vivek Vishnumurthy, and Paul Francis
IPTPS 2008, St. Petersburg, Florida.
Efficient rate estimation in networks (Summer Internship at Lucent Bell Labs, Holmdel, NJ; Supervisors: Murali Kodialam, T. V. Lakshman)

We look at the problem of rate estimation: given a packet stream and a property of interest, we wish to determine the proportion of packets that satisfy the property. The definition of the property could need one to perform a deep inspection of the packet payload to determine if the packet satisfies the property, so it is desirable to minimize the number of property tests. We count coincidences, i.e., the number of successive packets that satisfy the property, instead of naive counting of packets that satisfy the property, and show that this reduces the number of tests needed in the general case. This work was published at Infocom 2006.

Content Based Rate Estimation using Lazy Membership Testing [PDF]
Fang Hao, Murali Kodialam, T. V. Lakshman, Vivek Vishnumurthy, and Hui Zhang
Infocom 2006, Barcelona, Spain
 

Fair resource sharing in P2P systems (With Prof. Emin Gun Sirer)

We have designed KARMA, a completely distributed virtual economy that targets the freeloader problem in resource-sharing P2P systems. Nodes here exchange resources for units of virtual currency, and have accounts indicating how much credit they have left. Each node has, as its bank-set, a set of random peers that maintains the node's account status. Any transaction now will go through the bank-sets of the two involved peers, and credit is transferred from the resource-consumer's account to the resource-user's account. Freeloaders quickly run out of credit to pay for resources, thus incentivizing all nodes to actively involve in resource-sharing.

KARMA: A Secure Economic Framework for P2P Resource Sharing [PDF]
Vivek Vishnumurthy, Sangeeth Chandrakumar and Emin Gun Sirer
Workshop on the Economics of Peer-to-Peer Systems 2003, Berkeley, California
 

Differentiated Real-time services in ad-hoc wireless networks (B. Tech. final year project at IIT-Madras)

We use long range beacons on an additional low-bandwidth channel to predict and reduce call breaks in ad-hoc wireless networks. We also enable differentiated handling of calls based on their relative importance -– calls belonging to a more “important” class are dropped with less likelihood than are calls belonging to less important classes.

A Novel Out-of-band Signaling Mechanism for Enhanced Real-time Support in Tactical Ad hoc Wireless Networks
Vivek Vishnumurthy, Sandeep Tata, B. S. Manoj, and C. Siva Ram Murthy
In Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), 2004.