Elsevier

Ad Hoc Networks

Volume 94, November 2019, 101949
Ad Hoc Networks

Towards scalable Community Networks topologies

https://doi.org/10.1016/j.adhoc.2019.101949Get rights and content

Abstract

Community Networks (CNs) are grassroots bottom-up initiatives that build local infrastructures, normally using Wi-Fi technology, to bring broadband networking in areas with inadequate offer of traditional infrastructures such as ADSL, FTTx or wide-band cellular (LTE, 5G). Albeit they normally operate as access networks to the Internet, CNs are ad-hoc networks that evolve based on local requirements and constraints, often including additional local services on top of Internet access. These networks grow in highly decentralized manner that radically deviates from the top-down network planning practiced in commercial mobile networks, depending, on the one hand, on the willingness of people to participate, and, on the other hand, on the feasibility of wireless links connecting the houses of potential participants with each other.

In this paper, we present a novel methodology and its implementation into an automated tool, which enables the exercise of (light) centralized control to the dynamic and otherwise spontaneous CN growth process. The goal of the methodology is influencing the choices to connect a new node to the CN so that it can grow with more balance and to a larger size. Input to our methodology are open source resources about the physical terrain of the CN deployment area, such as Open Street Map and very detailed (less than 1 m resolution) LIDAR-based data about buildings layout and height, as well as technical descriptions and pricing data about off-the-shelf networking devices that are made available by manufacturers. Data related to demographics can be easily added to refine the environment description. With these data at hand, the tool can estimate the technical and economic feasibility of adding new nodes to the CN and actively assist new CN users in selecting proper equipment and CN node(s) to connect with to improve the CN scalability.

We test our methodology in four different areas representing standard territorial characterization categories: urban, suburban, intermediate, and rural. In all four cases our tool shows that CNs scale to much larger size using the assisted, network-aware methodology when compared with de facto practices. Results also show that the CNs deployed with the assisted methodology are more balanced and have a lower per-node cost for the same per-node guaranteed bandwidth. Moreover, this is achieved with fewer devices per node, which means that the network is cheaper to build and easier to maintain.

Introduction

Community Networks (CNs) are grassroots bottom up networks often built as 802.11-based Wireless Mesh Networks (WMNs). CNs are flourishing in Europe and grow in many different environments worldwide, their “preferred” ecosystem being areas where, whatever the reason, standard telecommunication infrastructures do not work properly. Often, these are areas of “market failure,” i.e., areas where commercial operators deem it non-profitable to invest in1. CNs also flourish in places with fervent cultural life, where people share strong community links and/or social/political ideals, and invest into a local infrastructure that can bestow on the community much more than the standard Internet in terms of digital divide reduction, rich and non-commercial services, and local economy support. It is now acknowledged that, even if they sometimes fail, CNs form an integral part of the global Internet. As such, they should be nurtured by the regulatory system and policy makers, because when they have success, they serve as a catalyst for the socio-economic development and well being of their region2.

A CN is typically launched thanks to the initiative of a small group of people, whose motives may range all the way from enthusiasm about technology and do-it-yourself practices to social activism and political causes [2]. The group members invest personal resources (effort, time, money) to set up a first small set of network nodes that ensure connectivity to the rest of the Internet or can support the provision of local services. This initial burst of activity normally gives rise to a network of a few nodes and a topology that is mainly determined by the location of the group members’ homes. Over a second longer phase, the network grows thanks to the addition of nodes by people who join the network and become members of the community. The network growth during this second phase is a distributed process with a strong crowdsourcing flavor that clearly distinguishes it from the top-down planning practised in conventional communication networks. The existing network nodes that become points of network attachment for new nodes that join the CN are typically determined locally and heuristically, depending on the node geo-location, the CN coverage in the area, as well as the availability and cost of proper hardware devices. Since the cost of the added node is normally sustained by the new CN member, the decision tends to be myopic and “greedy,” in that it only seeks to reduce the cost the new member incurs.

These local decisions, however, do shape the process of network evolution. They determine the main global properties of the resulting network topology, such as the average length of the shortest paths to the Internet gateway(s), the robustness of the network to topology failures, as well as the distribution of its overall capacity and traffic load across its nodes and links. Hence, they strongly influence the network performance and dictate the overall cost of the developed infrastructure.

The empirical analysis of CN topologies that evolve guided by fully decentralized decisions, without any central coordination or intervention, has provided evidence of pathologies and emergent risks. These include high dependence (in terms of connectivity and routing functionality) on a single or a few nodes, which may turn to single points of failure for the CN (if, for some reason, their owners lose interest in the CN or move to another place), and large differences in routes and speeds connecting end users to the Internet [3], [4], [5].

A key question arising in this context is whether it is possible to intervene in the CN growth process in order to steer its topology towards patterns that better serve its robustness and sustainability. Note that this question is distinctly different than the one faced by commercial network operators who plan their network as a top-down process. The CN infrastructure develops sequentially, in response to the time series of “join” events by end users, and there is no control over these events, i.e., where new nodes are to be installed. The remaining issue, then, is to what extent one can influence how these nodes are added, i.e., how they connect to the CN. This can only be obtained by influencing or constraining the local choices of the new users when they set up their own nodes.

The first contribution of our work consists in showing that simple algorithms can drive these local decisions and lead to drastic network performance improvements. We formulate the problem mapping it to the max-min fair routing problem (e.g.,  [6], [7]) and propose a greedy heuristic to solve it. We show that this greedy heuristic, bringing a network-wide view into the CN evolution process, helps the CN scale up to several hundreds of nodes and 2–3 times the size it would grow when the addition of the nodes is driven only by the new member’s cost minimization.

The second contribution of this work, which serves as an enabler for the first contribution, is a tool that can simulate and assess growth strategies of a CN exploiting (very) detailed topological descriptions of the CN deployment area and economic and technological constraints to set up the CN nodes. The topological description leverages open source data from OpenStreetMap3 and LIDAR-based estimates of building heights with an horizontal and vertical precision better than 1 m, and feed appropriate propagation models to infer the availability and quality of wireless links between pairs of CN nodes. Results with this tool are obtained for four areas with different population density and topological features, which are representative of four classes of the regions’ territorial characterization of the OECD (Organization for Economic Co-operation and Development).4

The source code of this tool is published as an open source project and it is available on-line.5 We highlight that the tool can be used in two main different ways. The first one, hinted above, as planning tool to help the management of a CN taking informed and rational decisions on the network expansion. The second one, maybe even more interesting, and in line with how we use it in this paper, is as a feasibility analyzer: Given an area or region, what is the potential to build a CN? And what is the probability that the CN can grow up to a sustainable dimension?

Section snippets

Background and system model

The deployment of CNs is a participatory and evolutionary process. The network grows over time as new users join the Community Network and new nodes are added to existing ones.

Controlling the CN growth process

Consider the onset a CN beginning at time t0, when the first CN nodes are set up by the CNO. Among the present nodes there is a gateway g. We would like to track the evolution of the CN up to the time T, when the CNO terminates the CN growth process because the minimum per-node bandwidth Rmin toward the Internet falls below a given threshold, say Rthr, for a fraction of nodes p.

A CN planning tool

So fare we have described what a tool to help in the development and deployment of CNs may work, but we need to describe the tool and understand how link selection strategies can be integrated in this tool. As we mentioned, the tool can be used to assist in the deployment of CNs, simply using it with the real flow of join requests, or can be used as an emulator trying to understand if a CN is feasible given an area of potential interest. Clearly, CNs may take months or years to grow, so that

Design choices, empirical validation and qualitative analysis

To test and validate our tool we use Open Data from four areas in the Tuscany region, in Italy. There are three good reasons for this choice: first, topological data are available for these areas; second, some of the authors are natives of this region easing the access and interpretation of data that are often available in the local language; and third, the familiarity with the area helps to correctly interpret the results.

To facilitate the extension of this analysis to areas outside Italy with

Quantitative evaluation

Having set the metrics interpretation and validated the tool comparing its results with an existing network, we now perform a quantitative evaluation of the CN growth potential for the four area categories (urban, suburban, intermediate, rural) and both link selection strategies. As a free parameter to compare different “requirements” we use Rthr ranging from 1 to 5 Mbit/s; the stopping condition is 10% of the nodes below Rthr. Each point in the plots corresponds to the average of 10 runs and

Related work

Our work combines elements from two, originally distinct, operations: network planning and topology control. The first one is a longer-term centralized process that is carried out top-down and concerns primarily node placement in static networks. The latter is carried out over shorter time intervals and is more relevant to ad-hoc networks dynamic networks. It involves the control of the transmit power of nodes in order to achieve certain performance objectives such as energy savings or

Conclusions and directions for further work

Planning a bottom-up initiative like a Community Network is an oxymoron, yet even grassroots enterprises need a road map and a bit of design. With this paper we have proposed a tool that can be used to model and control the growth of CNs based on the local geographic constraints and additional economic parameters.

This work presents two key contributions. For the first time, the way Community Networks grow has been modeled as an (implicit) stochastic graph evolution with realistic constraints 

Declaration of interests

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Dr. Leonardo Maccari is an Associate Professor at the Department of Environment and Computer Science and Statistics, University of Venice Ca' Foscari, Italy. He received a Master from the Faculty of Computer Science Engineering from the University of Florence in November 2004 and a Ph.D. from the same institution in 2010. He has been involved in several research projects financed by the Italian Ministry of research (PROFILES Project), the EU FP6/7 programme (CRUISE NoE, NI2S3 Strep) the

References (34)

  • J. Kleinberg et al.

    Fairness in routing and load balancing

    J. Comput. Syst. Sci.

    (2001)
  • K. Jain et al.

    Impact of interference on multi-hop wireless network performance

    Proceedings of the International Conference on Mobile Computing and Networking (MobiCom)

    (2003)
  • C. Barz et al.

    OLSRv2 for community networks: using directional airtime metric with external radios

    Comput. Netw.

    (2015)
  • C. Sommer et al.

    How shadowing hurts vehicular communications and how dynamic beaconing can help

    IEEE/ACM Trans. Mob. Comput.

    (2015)
  • A. Raniwala et al.

    Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks

    SIGMOBILE Mob. Comput. Commun. Rev.

    (2004)
  • A. Neumann et al.

    Enabling individually entrusted routing security for open and decentralized community networks

    Ad Hoc Netw.

    (2018)
  • L. Maccari et al.

    Improving routing convergence with centrality: theory and implementation of pop-Routing

    IEEE/ACM Trans. Netw.

    (2018)
  • Cited by (7)

    • GENIND: An industrial network topology generator

      2023, Alexandria Engineering Journal
    • On the Properties of Next Generation Wireless Backhaul

      2023, IEEE Transactions on Network Science and Engineering
    • A Realistic Open-Data-based Cost Model for Wireless Backhaul Networks in Rural Areas

      2022, Proceedings of the 2022 18th International Conference of Network and Service Management: Intelligent Management of Disruptive Network Technologies and Services, CNSM 2022
    • WIP: Analysis of feasible topologies for backhaul mesh networks

      2021, Proceedings - 2021 IEEE 22nd International Symposium on a World of Wireless, Mobile and Multimedia Networks, WoWMoM 2021
    • NPART+: Improving Wireless Network Topology Generators with Data from the Real World

      2020, 2020 Mediterranean Communication and Computer Networking Conference, MedComNet 2020
    View all citing articles on Scopus

    Dr. Leonardo Maccari is an Associate Professor at the Department of Environment and Computer Science and Statistics, University of Venice Ca' Foscari, Italy. He received a Master from the Faculty of Computer Science Engineering from the University of Florence in November 2004 and a Ph.D. from the same institution in 2010. He has been involved in several research projects financed by the Italian Ministry of research (PROFILES Project), the EU FP6/7 programme (CRUISE NoE, NI2S3 Strep) the European Defense Department (ESSOR project) and private companies (Telecom Italia, Selex Communications, Siemens). He received a Marie Curie COFUND grant for the PAF-FPE project for the period 2011–2014. He is the Technical Coordinator of the netCommons H2020 project on behalf of the University of Trento. He is an IEEE member and co-authored about 40 publications in refereed conferences, journals and book chapters, he participated in the TPC of several conferences (IEEE Globecom, IEEE ICC, IFIP Networking among them). He has extensive experience in research and development of techniques for wireless mesh networks, and their direct application to real networks, he is also among the authors of three patents.

    Gabriele Gemmi is a Master student at the University of Trento. He received his Bachelor degree in Computer Science at the University of Florence in 2017 with a thesis regarding optimizations on link state routing protocols. His interest are focused on bottom-up networks and more generally in any initiative whose aim is to decentralize control or power.

    Renato Lo Cigno is Associate Professor at the Department of Computer Science and Telecommunications (DISI) of the University of Trento, Italy, where he leads the Advanced Networks Systems research group in computer and communication networks. He received a degree in Electronic Engineering with a specialization in Telecommunications from Politecnico di Torino in 1988, the same institution where he worked until 2002. In 1998/9, he was with the CS Dep., UCLA, as a Visiting Scholar. Renato Lo Cigno has been General Chair of IEEE Int. Conf. on Peer-to-Peer Computing, TPC Chair of IEEE VNC, and General Chair and TPC Chair of ACM WMASH and IEEE WONS in different years. He has served in many TPCs of IEEE and ACM conferences, including INFOCOM, GLOBECOM, ICC, MSWiM, VNC, and CoNext, and has been Area Editor for Computer Networks and is currently Editor for IEEE/ACM Transactions on Networking. He has been guest editor for Special Issues of Elsevier Computer Networks and Computer Communications, and Springer LNCS. His current research interests are in performance evaluation of wired and wireless networks, modeling and simulation techniques, congestion control, P2P networks and networked systems in general, with specific attention toward applications and sustainable solutions. Vehicular networks, with a hype on safety and cooperative driving applications, are a special niche in his interests. Renato Lo Cigno is senior member of IEEE and ACM and has co-authored around 200 papers in international, peer reviewed journals and conferences.

    Dr. Merkouris Karaliopoulos is a Senior Research Associate at the Athens University of Economics and Business, in Greece. He obtained the Diploma in Electrical and Computer Engineering from the Aristotelian University of Thessaloniki, Greece, in 1998, and the Ph.D. degree in Electronic Engineering from the University of Surrey, UK, in 2004. He has been a Postdoctoral researcher at Computer Science Department of University of North Carolina at Chapel Hill (2005- 2006), and a Senior Researcher and Lecturer at the Department of Information Technology and Electrical Engineering, in ETH Zurich (2007–2010). Prior to joining AUEB, he was a Marie-Curie Fellow at the Department of Informatics and Telecommunications, University of Athens from 2010 to 2012 and a Researcher with the Center of Research and Technology Hellas (CERTH) from 2013 to 2015. His research interests lie in the broader area of wireless and mobile social networks, focusing, among others, on mobile crowdsensing and collective awareness platforms. He has worked in several EC collaborative R&D projects holding both research and technical coordination roles.

    Dr. Leandro Navarro is an Associate Professor at the Department of Computer Architecture of Universitat Politécnica de Catalunya (UPC) in Barcelona, Spain, which he joined in 1988, after receiving his graduate degree on Telecommunication Engineering from UPC and his Ph.D. from UPC in 1992. His research interests include the design of scalable and cooperative Internet services and applications. He coordinates the CNDS (Computer Networks and Distributed Systems) research group and the Erasmus Mundus Joint Doctorate in Distributed Computing. He is co-chair of the IRTF Global Access to the Internet for All (GAIA) WG and vice-chair of the executive board of the Association for Progressive Communications (APC.org). He has coordinated the CONFINE FIRE IP project (2011–2015) that developed Community-Lab.net a European-wide tested for Community Networks.

    This work was financed partially by the European Commission, H2020-ICT-2015 Programme, Grant Number 688768 “netCommons” (Network Infrastructure as Commons). The research work of M. Karaliopoulos received funding from the Hellenic Foundation for Research and Innovation (HFRI) and the Hellenic General Secretariat for Research and Technology (GSRT), under grant agreement No 892.

    View full text