Scalable Routing in a City-Scale Wi-Fi Network for Disaster Recovery

Ziqian Liu*, Om Chabra*, James Lynch, Chenning Li, Manya Ghobadi, and Hari Balakrishnan MIT CSAIL · 2025

Read Scalable Routing in a City-Scale Wi-Fi Network for Disaster Recovery by Ziqian Liu*, Om Chabra*, James Lynch, Chenning Li, Manya Ghobadi, and Hari Balakrishnan MIT CSAIL (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-06406.txt.

Introduction

Ziqian Liu and co-authors build a city scale mesh network in a 2025 paper. When disaster cuts wide area links, phones and Wi-Fi boxes still dot a city. Their system, MapMesh, links those fixed access points and moving devices into one network that routes packets among themselves and to any node that still reaches the internet, such as by satellite.

The core advance is a routing method that scales to millions of nodes, far past past mesh designs. It exploits map data on buildings, now widely available at scale, to predict which links can work. That map sense lets the protocol pick paths that dodge blocked lines of sight.

Catalog record

CREATORZiqian Liu*, Om Chabra*, James Lynch, Chenning Li, Manya Ghobadi, and Hari Balakrishnan MIT CSAIL
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-06406

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Scalable Routing in a City-Scale Wi-Fi Network for Disaster Recovery Ziqian Liu*, Om Chabra*, James Lynch, Chenning Li, Manya Ghobadi, and Hari Balakrishnan MIT CSAIL Abstract . In this paper, we present a new city-scale decentralized mesh network system suited for disaster recovery and emergencies. When wide-area connectivity is unavailable or significantly degraded, our system, MapMesh, enables static access points and mobile devices equipped with Wi-Fi in a city to route packets via each other for intra-city connectivity and to/from any nodes that might have Internet access, e.g., via satellite. The chief contribution of our work is a new routing protocol that scales to millions of nodes, a significant improvement over prior work on wireless mesh and mobile ad hoc networks. Our approach uses detailed information about buildings from widely available maps—data that was unavailable at scale over a decade ago, but is widely available now—to compute paths in a scalable way. 1. Introduction † † *Equal contribution This paper describes a wireless routing protocol that scales well to many millions of Wi-Fi devices, both static and mobile, in a dense urban environment. We show that by using accurate geospatial maps of buildings in urban areas—information now available for most urban areas around the world—we can route packets for millions of devices in over 650,000 buildings in an urban area such as New York while storing only a few hundred routing entries. To our knowledge, and in our simulation results, we show that these results are orders of magnitude more scalable than prior methods developed in the long line of research on mobile and wireless mesh networks to date (§ 2 ). Before describing how we achieve these results and justifying the underlying assumptions, the natural question in the reader’s mind is likely to be “why does this matter?” and “isn’t this already a solved problem?” We will address the second question at length in the next section—remarking here only that no prior work has demonstrated scalability to over a few thousand nodes—and focus instead on the first question to motivate this paper. As noted in a recent HotNets paper ( 43 ) , the Internet has become extremely centralized both at the network and application layers thanks to Internet Service Provider consolidation, extensive amounts of physical co-location, and cloud computing as the primary way to deploy application software. As a result, our networks and applications are vulnerable to disasters both natural and human, and attacks both digital and physical. When a disaster strikes, access to the broader Internet may be fully or partially destroyed or may be severely hampered. Entire regions may lose connectivity, or only a small fraction of nodes may have connectivity via technologies such as satellite networks. In all these cases, if it were possible to provide communication capabilities within a region , one could support in-region applications such as status updates, messaging, simple financial transactions and commerce, regional emergency and safety services, and connectivity to nodes equipped with Internet access. This network would provide lower bandwidth than usual but could be adequate for these applications during times of duress. The HotNets paper mentioned above made the case for such decentralized fallback networks (DFNs). This paper is inspired by that vision. We develop a complete solution for a city-scale DFN that uses Wi-Fi devices to achieve connectivity. Unlike in the HotNets paper, we support not only Wi-Fi access points (APs) but also mobile devices such as smartphones in the system. And while the HotNets paper showed how maps could be used, the solution there had excessive transmission overhead (each successful packet required 15-20 \times as many transmissions as in an optimal unicast scheme, and in addition required hundreds of bytes of packet header to send even small payloads. In short, it was unscalable, left numerous key details open, and did not demonstrate any definitive results. The primary focus of this paper is on scalable wireless routing for DFN applications. To achieve scalability, our proposed scheme eliminates all probe, control, and routing messages between devices. It aggressively uses map data, which is now easily available to route packets between devices by developing a way to route packets across a sequence of buildings to go from any source to the destination. Devices need to know which building they are in, but bootstrap all other knowledge by overhearing other packet broadcasts during operation. The reason why this approach works is because the vast majority of Wi-Fi devices are in or near buildings most of the time (e.g., Wi-Fi access points and most people). 1 1 1 This network design does not support users who are not close to a building at this time. We show how to compute good paths between buildings, how to compress these paths using waypoints that encode turns and departures from linear paths, how to structure a simple grid-based building addressing scheme in any urban area, and how to suppress transmissions to avoid the high overheads in prior work. Because of our use of urban maps of buildings, we call our system MapMesh. We have implemented MapMesh on a small campus testbed and in ns-3 and have conducted several simulations across several cities in the world. Our key contributions and findings are: • To our knowledge, MapMesh is the first building map-based routing scheme for wireless and mobile device networks. • We have simulated MapMesh in 60 cities across 40 countries and 6 continents. The number of devices varies from 762 (Vatican City) to 909,010 (New York City) with an average one-way packet loss rate varying from 0 to 80%. We achieve a delivery success rate between 20 to 95 percentage points higher than multiple versions of GPSR, the best prior scheme for scalable ad hoc routing. • In terms of required memory, we find that in cities with hundreds of thousands of buildings, we require a routing table size of a few hundred to a few thousand entries (a few kilobytes). • When we consider packet transmission (bandwidth) overheads, MapMesh is between 3 \times and 7 \times superior to prior schemes because it uses no routing messages during its operation. This work does not raise ethical issues. 2. Related Work Prior work on ad hoc and wireless mesh routing spans many dozens of papers ( 31 , 4 , 29 , 33 , 73 , 9 , 48 , 65 , 3 , 12 , 44 , 24 ) , and may be broadly classified into two categories: topological routing , which send different forms of control packets to determine routes, and geographic routing , which rely on out-of-band location information ( 59 ) . Topological routing. A network is topological if nodes has no information other than a non-physical address. For these networks, since no other information is given, nodes rely on sending control packets between each other to gain information about the network. A source needs to send some form of a destination discovery packet to first locate the destination and then use the information gathered from these control packets to determine where to forward packets. Topological schemes fall into one of two categories: proactive and reactive . In proactive protocols ( 53 , 69 , 5 , 32 , 23 ,

Read the complete text