FRACTEL

Announcements

  • Senior Programmer required: pdf, html

People and Sponsors

  • Faculty: Bhaskaran Raman, Kameswari Chebrolu, Purushottam Kulkarni
  • Current students: Vishal Sevani
  • Past students: Lokendra Kumar Singh, Pulkit Gupta, Ashutosh Dhekne, Nirav Uchat, Rahul Jain, Rahul Mittal
  • Sponsor: This work is supported by TICET, a collaboration between Tata TeleServices Limited (TTSL) and IIT Bombay.

Motivation and Background

  • Mesh networks based on IEEE 802.11 are a cost-effective option for providing Internet connectivity to rural regions, especially in developing countries.
  • FRACTEL (wiFi-based Rural data ACcess and TELephony) seeks to use a combination of:
    • Long-distance links: a few km to few tens of km, and
    • Local-access links: shorter distance links, up to about 500 m
      to achieve this.
  • The long-distance links extend connectivity from a point of wired connectivity, called the landline to a specific point in each village.
  • The local-access links extend connectivity from this point, which we term the local-gateway, to multiple nearby locations. Such nearby locations may include individual buildings such as a school, health centre, community centre, residential houses, etc.; it may also include nearby villages.
  • An example deployment setting, with reference to the Ashwini network, is shown in the figure below.
    Long-Distance Network (LDN) and Local-Access Networks (LACNs) in Ashwini

Goals

  • In such a setting, we wish to support a variety of applications: http/ftp, as well as voice, video-based real-time applications.
  • The Ashwini project has already demonstrated a need for such support: applications like remote education, tele-medicine, agricultural lessons, etc. based on video-conferencing are the cornerstone of Ashwini.
  • To support such applications, we need to provide adequate performance, with the Quality-of-Service (QoS) necessary for voice/video.
  • We seek to address the challenge of providing this for a large network, consisting of say, a few hundred nodes within a district: most districts in India are within 20-30 km in radial length.

Research Themes

Research in FRACTEL is centered around the following topics.

  • Link Abstraction
    QoS requires predictable performance; and the presence/absence of the link abstraction is a significant aspect in this regard. The state-of-the-art in mesh network measurement (Roofnet) indicates that multi-path induced packet error rates mean the absence of the link abstraction. Does this hold in FRACTEL's envisioned deployment settings? What is the behaviour for 802.11 a/g/n?
  • TDMA-based MAC
    While there has been significant research in the domain of TDMA-based multi-hop mesh networks, there are no implementations of the same. FRACTEL seeks to identify and address the system-level challenges in the deployment of a scalable TDMA-based mesh network.
  • Mesh Network Management
    Much research is needed in terms of network management and fault/performance diagnosis. Such research has received some attention in the domain of enterprise WiFi deployments, but very little has been done so far in terms of mesh network management.
  • Power savings
    WiFi mesh networks typically do not consider power optimization as one of their goals. However, this is important in FRACTEL since the nodes may be running off batteries. We seek to explore power optimization mechanisms by switching off network nodes when not in operation, and switching them on dynamically.

Publications

  • Vishal Sevani, Bhaskaran Raman, “SIR Based Interference Modeling For Wireless Mesh Networks: A Detailed Measurement Study”, The Fourth International Conference on COMmunication Systems and NETworkS (COMSNETS), Bangalore, India, January 2012. details
  • Bhaskaran Raman, Rahul Jain, “SIR-Based Interference-Maps for TDMA-Based Outdoor Mesh Networks”, Invited paper, LANMAN 2010, New York, 05-07 May 2010. details
  • Pulkit Gupta, Bharat Jain, Bhaskaran Raman, Purushottam Kulkarni, “Link-level Measurements of Outdoor 802.11g Links”, The 4th IEEE International Workshop on Wireless Mesh Networks (WiMesh 2009), A workshop in SECON 2009, Jun 2009, Rome, Italy. details
  • Ashutosh Dhekne, Nirav Uchat, Bhaskaran Raman, “Implementation and Evaluation of a TDMA MAC for WiFi-based Rural Mesh Networks”, 3rd ACM Workshop on Networked Systems for Developing Regions (NSDR'09), a workshop in SOSP'09, Big Sky, Montana, USA, 11 Oct 2009.
    Abstract: WiFi mesh networks with outdoor links have become an attractive option to provide cost-effective broadband connectivity to rural areas, especially in developing regions. It is well understood that a TDMA-based approach is necessary to provide good performance over such networks. While preliminary prototypes of TDMA-based MAC protocols have been developed, there is no implementation-based validation/evaluation in multi-hop settings. In this work, we describe the elements of a multi-hop MAC implementation based on the open-source MADWIFI driver. We also present an evaluation, with a detailed accounting of the various overheads, on a 4-hop (5-node) path. We show that our implementation has no system overheads, achieves good throughput, and low delay/jitter.
    Paper: 2009-fractel-mac-impl-nsdr09.pdf, NSDR'09 presentation: 2009-fractel-mac-impl-nsdr09-pres.pdf
  • “On the Feasibility of the Link Abstraction in Wireless Mesh Networks”, Bhaskaran Raman, Kameswari Chebrolu, Dattatraya Gokhale, and Sayandeep Sen, Accepted for publication, IEEE Transactions on Networking.
    Extended version of the INFOCOM 2008 paper
    Abstract: Outdoor community mesh networks based on 802.11 have seen tremendous growth in the recent past. The current understanding is that wireless link performance in these settings in inherently unpredictable, due to multipath delay spread. Consequently, researchers have focused on developing intelligent routing techniques to achieve the best possible performance. In this paper, we are specifically interested in mesh networks in rural locations. We first present detailed measurements to show that the PHY layer in these settings is indeed stable and predictable. There is a strong correlation between the error rate and the received signal strength. We show that interference, and not multipath fading, is the primary cause of unpredictable performance. This is in sharp contrast with current widespread knowledge from prior studies. Furthermore, we corroborate our view with a fresh analysis of data presented in these prior studies. While our initial measurements focus on 802.11b, we then use two different PHY technologies as well, operating in the 2.4~GHz ISM band: 802.11g and 802.15.4. These show similar results too. Based on our results, we argue that outdoor rural mesh networks can indeed be built with the link abstraction being valid. This has several design implications, including at the MAC and routing layers, and opens up a fresh perspective on a wide range of technical issues in this domain.
    Publication
  • “TDMA Scheduling in Long-Distance WiFi Networks”, Debmalya Panigrahi and Bhaskaran Raman, The 26th Annual Conference on Computer Communications, IEEE INFOCOM 2009 Mini-Conference, April 2009. [Mini-Conference: top 19.7%-26.6% of INFOCOM 2009 submissions].
    Abstract: In the last few years, long-distance WiFi networks have been used to provide Internet connectivity in rural areas. The strong requirement to support real-time applications in these settings leads us to consider TDMA link scheduling. In this paper, we consider the FRACTEL architecture for long-distance mesh networks. We propose a novel angular interference model, which is not only practical, but also makes the problem of TDMA scheduling tractable. We then consider delay-bounded scheduling and present an algorithm which uses at most 1/3rd more time-slots than the optimal number of slots required without the delay bound. Our evaluation on various network topologies shows that the algorithm is practical, and more efficient in practice than its worst-case bound.
    Publication
  • “On the Feasibility of the Link Abstraction in (Rural) Mesh Networks”, Dattatraya Gokhale, Sayandeep Sen, Kameswari Chebrolu, and Bhaskaran Raman, The 25th Annual Conference on Computer Communications (IEEE INFOCOM), Phoenix, Arizona (USA), April 2008. [Acceptance rate: 20.5%].
    Selected as one of the 'Top Three Outstanding Papers' at IEEE INFOCOM 2008
    Extended version published in IEEE Transactions on Networking
    Abstract: Outdoor community mesh networks based on 802.11 have seen tremendous growth in the recent past. The current understanding is that wireless link performance in these settings in inherently unpredictable, due to multipath delay spread. Consequently, researchers have focused on developing intelligent routing techniques to achieve the best possible performance. In this paper, we are specifically interested in mesh networks in rural locations. We first present detailed measurements to show that the PHY layer in these settings is indeed stable and predictable. There is a strong correlation between the error rate and the received signal strength. We show that interference, and not multipath fading, is the primary cause of unpredictable performance. This is in sharp contrast with current widespread knowledge from prior studies. Furthermore, we corroborate our view with a fresh analysis of data presented in these prior studies. Based on our results, we argue that outdoor rural mesh networks can indeed be built with the link abstraction being valid. This has several design implications, and opens up a fresh perspective on a wide range of technical issues in this domain.
    Publication, Presentation (conf. version), Presentation (longer version)
  • “FRACTEL: A Fresh Perspective on (Rural) Mesh Networks”, Kameswari Chebrolu and Bhaskaran Raman, ACM SIGCOMM Workshop on Networked Systems for Developing Regions (NSDR'07), A Workshop in SIGCOMM 2007, Aug 2007, Kyoto, Japan. [Acceptance rate: 21.3%].
    Abstract: The use of commodity 802.11 hardware to provide network connectivity to rural regions is an appealing proposition. In this paper, we consider such networks, with a combination of long-distance and short-distance links. In such a setting, we offer a fresh perspective on a variety of technical issues in multi-hop mesh networks. To support QoS for voice, video-based real-time applications, the use of a TDMA-based MAC is appropriate. In this context, we argue that existing approaches to TDMA scheduling and channel allocation are either inapplicable, or are too general and hence complicated. We apply extensive domain knowledge in designing a solution applicable in our context. We also suggest appropriate implementation strategies for the TDMA MAC, capable of scaling to large networks. In all of the above topics, we articulate open technical issues wherever applicable.
    Paper, Presentation, Presentation (longer version)

Research Issues: Ongoing and Future Topics

Link scheduling in the long-distance network

Description: Here we seek to simplify the problem of TDMA link scheduling in a FRACTEL setting, since the consideration of generic mesh networks is known to be hard.

Status: Ongoing work, Debmalya Panigrahi & Manveer Singh Chawla

Time synchronization, schedule dissemination

Description: Here we are exploring system level issues in implementing a TDMA style MAC protocol. Once we have a TDMA schedule, how do we go about implementing it? Significant challenges are in terms of achieving multi-hop synchronization, and schedule dissemination from a central location.

Status: Ongoing work, Gaurav Chhawchharia (MTech student, IITK) & Sharad Jaiswal (Alcatel-Lucent)

Finding out the interference map in a mesh network

Description: To get a TDMA schedule in a mesh network, a primary input is that if which links are interfering with one another. Such information is also necessary for any network management. Our goal here is to come up with efficient mechanisms for determining the interference map.

Status: Ongoing work, Pradeep Gopaluni (MTech student, IITK) & Sharad Jaiswal (Alcatel-Lucent)

Link performance diagnosis

Description: Here we focus on a single wireless link in the network. We first need to determine if it is indeed performing as expected. Next, if it is not performing as expected, we need to diagnose the possible cause.

Status: Dheeraj Golccha Jain has a partial algorithm for such diagnosis, for 802.11b; Aparna Kailasam is working on porting the implementation to MADWIFI.

Future scope: Deployment experience is required to evaluate the algorithm. The question of whether a similar algorithm will work for 802.11 a/g in practice, is open.

Performance trade-offs in schedule dissemination

Description: Schedule dissemination has inherent trade-offs between the overhead involved and any delays in conveying a new schedule. How does this trade-off pan-out in the context of TCP & video applications?

Future scope: Potentially an MTech thesis, or part of PhD work

Video multicast in FRACTEL

Description: Multicast is a much desired feature in FRACTEL: one-to-many video conferencing applications have a lot of demand in rural deployments (one expert in conversation with several students/clients). Multicast TDMA scheduling is known to be even more complex than unicast scheduling. How does this issue pan out in a FRACTEL deployment?

Future scope: MTech thesis, or part of PhD work

Network management, Dynamic interference adaptation

Description: When do we do root cause diagnosis in a FRACTEL network? What exactly is defined as a network problem which needs to be diagnosed? And how do we do the diagnosis? If the diagnosis says that interference is the problem, then how do we go about fixing it? What is the mechanism in the case of internal interference? External interference?

Future scope: One or more MTech theses, or part of PhD work

Power optimization in the mesh network

Description: Suppose nodes in the network are turned off by default. How do we power them on-demand? How can we leverage Wake-on-WLAN for such a mechanism? Wake-on-WLAN is not selective on which node(s) it wakes up. How can we achieve such selectivity? How can we optimize the cost of the hardware (additional 802.15.4 node, additional RF splitter) in deploying such a solution?

Future scope: One or more MTech theses, or part of PhD work

802.11 a/g/n measurement study

Description: Thus far there has been no careful performance study of outdoor 802.11 a/g/n links. It is essential to understand their performance; this will be input to any network performance diagnosis algorithm.

Future scope: Semester R&D project (Nithin Kumar Dara)