Ongoing Research Projects
Architecting Citywide Wi-Fi
Many major cities around the world are considering building infrastructure for ubiquitous Wi-Fi access throughout their cities. However, this is an expensive proposition, and can cost as much as $150,000 per square mile (2007 estimates). However, most cities already have an existing, dense infrastructure of private Wi-Fi Access Points (APs), connected to broadband back-haul links. The only problem is that hosts who own an AP would not want to open up their internet connection to strange guests, who may download illegal content or launch attacks on random websites. Similarly, guests could be compromised by hosts in subtle ways.
Our solution removes these latent trust dependencies by separating the responsibility of sharing an connection to the public internet from the act of sharing a Wi-Fi AP. The hosts share their Wi-Fi, but only provide access to the guest's home. Guests access the public Internet by tunneling through their home broadband connection. Using tunneling as a primitive, our solution makes the guests, rather than the hosts, responsible for their actions on the Internet, and also allows the creation of secure connections that render them safe from being hacked by malicious hosts.
Delivering the long-tail of rich-media user-generated content
Rich-media content such as videos need to be served from close to the users, and may require replication using specialised content delivery networks (CDNs) such as Akamai. YouTube blog claims that over 24 hours worth of video is being uploaded every minute onto their servers. At such scales, the global replication demanded by traditional CDNs becomes expensive. User-generated content is especially difficult because there is a long tail of content, each of which is not popular enough to be replicated globally, but together the long tail may get sufficient accesses to be worth replicating. Furthermore, even the energy to store the content can become prohibitive - For example, merely storing one day's uploads for an hour on disks which are switched on and ready to serve content can consume as much energy as an entire household in Scotland does over a quarter year.
Our solution is based on our measurements which show that accesses to the unpopular content in the long tail are largely localised in some part of the social network, whereas popular content generates non-viral accesses with interest popping up simultaneously in different parts of the social network. Exploiting this pattern, we have proposed Buzztraq, a system that partially replicates content based on where the friends of previous users are. SpinThrift is a system that migrates data in an array of disks so that the popular content is on only a few disks, at the head of the array. The rest of the disks can be put in low-power mode, saving energy.
Buzztraq: Predicting geographical access patterns of social cascades using social networks—[PDF]
Nishanth Sastry, Eiko Yoneki and Jon Crowcroft
Eurosys Social Network Systems Workshop, 2009.
Talk: .key, .pdf
SpinThrift: Saving energy in viral workloads—[PDF]
Nishanth Sastry and Jon Crowcroft
SIGCOMM Green Networking Workshop, 2010.
Talk: (To appear).
Data Delivery Properties of Human Contact Networks
The Pocket Switched Network is a form of delay tolerant network that constructs data paths over time, using human social contacts for making intermediate hops. Several heuristics-based algorithms have been proposed for finding routes in such networks. However, the performance of any routing algorithm on such a network would largely depend on the efficiency of the human contact process in creating paths. Our work is driven by a simple question, which has surprisingly not been studied until now: How efficient can a group of N people be, in supporting NxN connectivity amongst themselves?
Unexpectedly, our results show that human contacts are not very efficient at the macroscopic level: Some social contacts happen too frequently to be useful for data exchange, and it turns out that rare social contacts are crucial for connectivity. Furthermore, connectivity is highly unequal---when the network connects a large fraction of nodes, it is because a large subset of nodes achieve 100% connectivity among themselves, with much lesser success for other nodes.
However, we also find significant variations in performance over time windows of similar duration and show how to identify "good" windows. The human contact network also exhibits a remarkable resilience to path failures: In two different failure modes, where a large number of paths between a sender and destination fail, we show that the distribution of delivery times can be still quite close to that found by flooding over all paths without path failures.
Data Delivery Properties of Human Contact Networks—[pre-print]
Nishanth Sastry, D. Manjunath, Karen Sollins and Jon Crowcroft
IEEE Transactions on Mobile Computing (to appear)
A related work (mostly Pan's idea), looks at how we can use community structure derived from online social networks to route on pocket switched networks.
Real world routing using virtual world information—[PDF]
Pan Hui and Nishanth Sastry
2009 IEEE SocialCom Workshop on Leveraging Social Patterns for Security, Privacy and Network Architectures (SP4SPNA09) Talk: .key, .pdf
CYRF: A Unified Framework for window-based congestion control
TCP flows adjust flow rate to available bandwidth by increasing and decreasing their window sizes. It is a classical result that a set of flows using TCP's increase-decrease policy converge to a fair share of the bottleneck link bandwidth. However, TCP's policies are not suitable for many applications such as video streaming, which require smoother changes to sending rate than allowed by TCP.
This work (my Master's thesis) showed how to use a large class of monotonically non-decreasing functions to achieve fairness. Applications can choose how to respond to congestion function by choosing their own response function (CYRF=Choose Your Response Function). By appropriately choosing a combination of functions for increase and decrease, a CYRF flow can be made "TCP-friendly", to co-exist with legacy TCP flows.
The main result is best understood by an example: Consider two flows with windows of size 8 and 10. If an application of the increase policy must result in a fair window size of 11 for both, the smaller flow must change (increase) by a larger amount. Similarly, if a decrease must result in a fair window size of 7, the smaller flow must decrease by a smaller amount (1, rather than 3), or equivalently, change by a larger signed amount (-1, which is greater than -3). Thus, to move towards a fair allocation, the signed change in the window size must always be greater for the flow with the smaller window. The main theorem shows that it is sufficient for the signed change as a proportion of the current window size to be greater.
CYRF: A Theory of Window-based Unicast Congestion Control—[PDF]
Nishanth Sastry and Simon S. Lam
IEEE/ACM Transactions on Networks 13(2): 330--342 (2005).