Multi-hop matters: the state of wireless mesh networking
Multi-hop mesh networks, confined to university labs at the start of this decade, are now widely available from commercial vendors. These vendors tout a number of advantages for mesh technologies: lower costs of deployment, easier administration, better coverage, and lower power consumption. Mesh networking is now being used in an impressive range of applications, from large-scale institutional deployments to networks of tiny sensors.
Mesh networking is sometimes mentioned as a solution to the much-discussed "last mile" problem in US telecommunications policy. Unfortunately, the inherent capacity limits of the wireless medium means that mesh networks are unlikely to provide a serious alternative to fiber or coax broadband connections in this market. Mesh is a reasonable way to provide broadband to consumers in developing countries who might not otherwise be able to afford access at all. But in the developed world, mesh technologies are best viewed as a supplement to wired Internet connections and traditional single-hop access points.
To help us understand the state of technology, Ars talked to two experts on mesh networking: Sanjit Biswas, the CEO of mesh wireless startup Meraki Networks, and Jinyang Li, a computer science professor at NYU. Each did pioneering work on mesh networks at MIT earlier this decade, and both continue working on mesh networking technologies today.
Both identified the relative paucity of spectrum available for mesh networking applications as a major constraint on the technology's continued growth. Most mesh networks today operate on the same unlicensed bands used by WiFi and other consumer electronics devices. The amount of unlicensed spectrum available has increased with the deregulation of the 5GHz band, but the vast majority of the spectrum is locked up for other uses.
The evolution of mesh
Computer scientists have been studying mesh networks for a quarter century. In the 1980s, the military fundedresearch into self-configuring multi-hop wireless networks suitable for use on the battlefield, but a lack of affordable hardware limited researchers' ability to build working systems. In the 1990s, researchers began building and testing mesh networks. In one influential test in 1998, a team at Carnegie Mellon mounted computers and networking gear into five cars and drove them around campus. The car-mounted nodes were able to automatically adapt to changes in network topology, maintaining reliable connectivity among themselves and providing continuous connectivity between two fixed nodes at opposite ends of campus.
By the turn of the century, wireless networking gear had become cheap and powerful enough to allow more ambitious tests. One of the most famous is Roofnet, an experimental mesh network built by MIT researchers earlier this decade, and Meraki, the commercial spin-off that counts Google among its investors. Sanjit Biswas co-led the Roofnet team and co-founded its commercial spin-off Meraki.
In 2001, Biswas was a grad student at MIT exploring ways to provide wireless broadband access to residents near the MIT campus in Cambridge. An initial plan for a single large antenna was scrapped when it became clear that it would not provide sufficient range or throughput. Biswas and his fellow grad student John Bicket switched to a multi-hop design, with multiple nodes cooperating to cover a large area.
When fully operational, Roofnet covered about 5 square miles of Cambridge, MA, between the MIT and Harvard campuses. At its peak, it had almost 100 nodes, and Biswas estimates the network served thousands of MIT and Harvard students over its lifetime. Each Roofnet node was an ordinary PC with a WiFi card and antenna. Because the project relied on volunteers to deploy Roofnet nodes in their homes, the Roofnet team had no real control over the topology of the network.
"We had to understand what it takes to build a network that can survive a lot of failures," Biswas said. "People would move from their apartments, or trees would go up in the springtime, blocking the signal." The network's routing protocols had to be robust enough to handle a network with constantly-changing topology and disappearing nodes.
The Roofnet team found that traditional routing protocols designed for wired networks didn't work well in the wireless setting. For example, Biswas told Ars that before Roofnet started its research, "It was widely believed that wireless links either worked or they didn't." In reality, there is "a continuous range of packet-delivery rates, all the way from 0 to 100 percent." This means that nodes cannot assume that any reachable node is a reliable node. Instead, mesh routing protocols need to constantly monitor link reliability and avoid routes with high rates of dropped packets.
Mesh routing protocols also have to worry about interference issues that don't crop up in wired networks. This can be a serious obstacle to high throughput for single-radio mesh nodes, because it prevents adjacent nodes in a route from broadcasting simultaneously. The Roofnet team found that in mesh networks with a single radio per node, this means that a two-hop route has less than half the throughput of a single-hop route. Some recent mesh products deal with this problem by having two or three radios in each node. This allows adjacent nodes on a route to transmit on different frequencies, dramatically improving throughput.
Meraki
In 2006, with several years of experience running a full-scale mesh network under their belts, Biswas and Bicket founded Meraki to commercialize their technology. The firm attracted an early investment from Google, and closed a $20 million venture capital round in 2008.
The most lucrative segment of Meraki's mesh networking business is sales to large institutions. Leading hardware vendors such as Cisco have long sold gear designed to blanket a campus, apartment building, or office tower with WiFi coverage. But Biswas argues that the sophisticated meshing technology in its routers makes them easier to configure and manage than products offered by established vendors. Meraki's access points self-configure and then phone home to Meraki servers for further instructions; customers tweak their networks using a Web-based interface hosted on Meraki's servers.
At the low end of Meraki's product line are mesh nodes optimized for providing basic connectivity for areas that lack traditional wired connectivity. These products are popular internationally; Biswas touts customers in 143 countries worldwide. Mesh networks are especially appealing in nations that lack the resources to put extensive fiber or copper networks in the ground. In these areas, a mesh network can extend connectivity to homes and businesses that would not be able to access it in other ways. The XO laptop distributed by the One Laptop Per Child project uses mesh networking protocols for similar reasons.
For remote areas of developing nations, omnidirectional mesh networks must be paired with backhaul connections that use directional antennas for increased range. For example, Lakshminarayanan Subramanian, a computer science professor at NYU, has used WiFi and directional antennas to transmit 7-10 Mbps over a distance of 100 km. These links will never be as fast as a fiber connection, but for poor villages who otherwise wouldn't be able to afford an Internet connection, mesh networking is a boon.
Going the "last mile"
Mesh networks may provide a cheap way to get villages in the developing world online, but they do not seem likely to pose a serious threat to telecom incumbents in the developed world. One of Meraki's leading competitors, Tropos networks, focuses on public-sector clients such as police departments, public utilities, and municipalities wishing to build city-wide wireless networks. One case study on the Tropos website touts the experience of Chaska, MN, which hired Tropos in 2004 to build a municipal WiFi network for the city's 23,000 residents at a cost of $1.3 million.
Tropos says its 802.11 b/g-based network in Chaska offered "1+ Mbps" connectivity. Biswas says Meraki's newer 802.11n-based products boast typical speeds on the order of 10 Mbps. But with Verizon and Comcast already offering 50Mbps connections in some areas, mesh networking technology seems unlikely to be a serious threat to cable and telephone incumbents in the developed world.
Biswas told Ars that Meraki's low-end gear is primarily used in the United States to supplement traditional wired network connections. So, for example, a neighborhood association might deploy Meraki routers in parts of the neighborhood that are not one hop away from a wired access point, on the theory that relatively slow access is better than no access at all. But these small-scale applications are best thought of as a complement, rather than an alternative, to incumbent broadband providers.
Mesh and open standards
No wireless network can function without access to spectrum, and one of the most important factors promoting the growth of mesh networks... has been the growing availability of unlicensed spectrum.
So far, the commercially successful mesh products have tended to use proprietary mesh protocols. Meraki, for example, uses 802.11 for the lowest levels of its networking stack, but runs a homebrew mesh routing protocol on top of it. Biswas argued that this is a reflection of the primitive state of mesh networking protocols.
"We update our routing protocols almost on a quarterly basis to improve performance," he said. "It doesn't feel like it's come to the point where it's stabilized enough to have an interoperable standard."
One possible exception is the 802.11s standard, a WiFi variant which is now under consideration by an IEEE task force. Biswas predicted that 802.11s "will fit in really well to the lower end of the market where you're talking about a smaller number of devices and interoperability matters a lot more."
Biswas predicted that 802.11s-based devices were unlikely to work well for larger networks. "There's nothing that specifies 'here's how you deal with lossy links,'" he said. "It works well in a basic scenario, but when you start building networks with hundreds of devices, you start to run into a lot of scaling issues that 802.11s doesn't address."
Open mesh networks and the importance of incentives
All of the mesh networking applications we've discussed so far have been cases where a single organization owns and manages all the nodes in the mesh. A more ambitious goal is to build heterogenous mesh networks that are open to the general public.
To understand the challenge of building public mesh networks, Ars talked to Jinyang Li, a computer science professor at New York University who has been working on mesh networks for over a decade. Li and Biswas were colleagues when both were working on mesh networking technologies at MIT.
In a conversation with Ars, she pointed out that "the original vision of the mesh was that all of the nodes would cooperatively forward traffic for each other whenever there was a global benefit to doing so." The cell phone market seems like a place where this model could fit particularly well; short-range radio transmissions consume dramatically less power than long-range transmissions, so in principle cell phones could save energy by sending their packets to cell phone towers via multi-hop routes that include nearby cell phones.
In practice, this strategy has several major problems. Most obviously, achieving reliable routing with rapidly moving devices is difficult. A customer used to the reliability of single-hop wireless connections is unlikely to be interested in a network that could fail if the owner of a key node in the local mesh walks out of range. Moreover, cell phones that participate in mesh networks would have greater variability in battery life. The total battery life might improve on average, but this will be little consolation to a user who needs to make an urgent phone call and finds that his phone has run low on power because it forwarded too many packets earlier in the day.
Li pointed out that current mesh protocols don't give nodes incentives to forward one another's packets. This isn't a major problem in academic, corporate or government settings where all the nodes can be assumed to have the same owner. But in open, heterogenous networks, each user will be tempted to "cheat" by modifying his own device to take advantage of other nodes' forwarding services without reciprocating. "It's still an open question whether we'll be able to solve this incentive problem," Li told Ars.
A related concern is security. Users should worry about the security implications of entrusting their packets to random strangers. Things would get even more dicey if routing protocols were enhanced to add monetary incentive schemes such as micropayments; in that case, security flaws in mesh networks could allow unscrupulous mesh participants to generate bogus traffic in order to siphon money away from their neighbors.
Sensor networks
Li also pointed to another niche application for mesh networking: sensor networks. In sensor networks, a large number of tiny computers form an ad hoc network in order to relay data back to a centralized base station. Mesh networking techniques work well for sensor networks because two key design goals of such networks is often to minimize cost and energy consumption.
A company called Silver Spring Networks uses mesh networking techniques to automatically report utility meter readings. In this application, power consumption isn't a major issue, but low cost of deployment and high reliability are crucial. And the relatively low throughput of mesh networks isn't a serious problem, because the amount of data being transmitted is tiny.
Spectrum policy
No wireless network can function without access to spectrum, and one of the most important factors promoting the growth of mesh networks—and WiFi-based networks more generally—has been the growing availability of unlicensed spectrum. Biswas says that the amount of unlicensed spectrum available for use by Meraki products has increased from 80MHz to 300MHz since he started working on mesh networks. The recent opening of the 5GHz band gives mesh network vendors a new, less crowded swath of spectrum to work with.
Biswas told Ars that continued expansion of available spectrum would further improve the performance of mesh networks. He strongly endorsed recent proposals to allow unlicensed use of white space spectrum in the television bands. This spectrum has much better propagation characteristics than the 2.4GHz and 5GHz bands currently available: transmissions in the television bands are better able to pass through walls and other obstructions, which would improve coverage.
Biswas was less enthusiastic about the prospect of auctioning off more licensed spectrum. "The customer needs to go get the licensed spectrum, not the device vendor," he said. "Site licenses are expensive. We have customers that are community colleges; they're not going to be able to spend money on something like that."
Jinyang Li was more bullish on licensed spectrum. "If you look at city-wide deployment of a mesh network, the unlicensed band is both a blessing and kind of a curse," she said. "It's a blessing because you don't have to license the frequency band. But it's a curse because it's hard to guarantee quality. There could be ham radio operators blasting at high power, and there's nothing you can do about it."
Li suggested that opening up both more licensed and unlicensed bands could promote the development of mesh networking technologies.
Conclusion
Mesh networking is still a young technology. Engineers are still discovering new applications for it and learning how to squeeze maximum performance out of existing ones.
Mesh networking is best understood as a way to supplement and enhance other networking technologies rather than a replacement for them. The inherent limits of wireless transmission make it unlikely mesh networks will replace fiber and coax networks any time soon. Because mesh networks tend to rely on incumbent networks for backhaul, there doesn't seem to be much prospect that the growth of mesh networks will change the terms of the broadband policy debate.
But mesh networks do underscore the importance of spectrum reform. Whether you prefer unlicensed spectrum or flexible licensed spectrum, the growth of mesh technologies underscores the need for additional bandwidth for digital networks. Such allocation is being bitterly opposed by incumbent broadcasters, but as mesh networks mature, the argument for making more spectrum available grows stronger.
No comments:
Post a Comment