Towards scalable Community Networks topologies☆
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)
- et al.
Maxmin fair routing in connection-oriented networks
Proceedings of the Euro-Parallel and Distributed Systems Conference (Euro-Par)
(1998) - H. Rogge, E. Baccelli, Request for comments 7797: directional airtime metric based on packet sequence numbers for...
- et al.
Evaluation of mesh routing protocols for wireless community networks
Comput. Netw.
(2015) - UK Office of Communications, OFCOM, Achieving decent broadband connectivity for everyone. Technical advice to UK...
- et al.
A cone-based distributed topology-control algorithm for wireless multi-hop networks
IEEE/ACM Trans. Netw.
(2005) Trends in Telecommunication Reform 2008: Six Degrees of Sharing
Technical Report
(2009)- et al.
Community networks and sustainability: a survey of perceptions, practices, and proposed solutions
IEEE Commun. Surv. Tutor.
(2018) - et al.
Topology patterns of a community network: Guifi.net
Proceedings of the IEEE Conference on Wireless and Mobile Computing, Networking and Communications (WiMob)
(2012) - et al.
A week in the life of three large wireless community networks
Ad Hoc Netw.
(2015) Detecting and mitigating points of failure in community networks: a graph-based approach
IEEE/ACM Trans. Comput. Soc. Syst.
(2019)
Fairness in routing and load balancing
J. Comput. Syst. Sci.
Impact of interference on multi-hop wireless network performance
Proceedings of the International Conference on Mobile Computing and Networking (MobiCom)
OLSRv2 for community networks: using directional airtime metric with external radios
Comput. Netw.
How shadowing hurts vehicular communications and how dynamic beaconing can help
IEEE/ACM Trans. Mob. Comput.
Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks
SIGMOBILE Mob. Comput. Commun. Rev.
Enabling individually entrusted routing security for open and decentralized community networks
Ad Hoc Netw.
Improving routing convergence with centrality: theory and implementation of pop-Routing
IEEE/ACM Trans. Netw.
Cited by (7)
GENIND: An industrial network topology generator
2023, Alexandria Engineering JournalToward Smart Community Networks
2023, IEEE NetworkOn the Properties of Next Generation Wireless Backhaul
2023, IEEE Transactions on Network Science and EngineeringA 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 2022WIP: 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 2021NPART+: Improving Wireless Network Topology Generators with Data from the Real World
2020, 2020 Mediterranean Communication and Computer Networking Conference, MedComNet 2020
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.