Subject: [NEXTEL-1] Getting A Mesh Network To Work In The Real World Takes Some Work

From: [email-masked]
Date: Sat, 30 Aug 2003 13:09:47 -0400

Getting A Mesh Network To Work In The Real World Takes Some Work

Contributed by mmasnick on Fri, Aug 29 2003

People have been talking about mesh networking for a while, and there have been
plenty of laboratory demonstrations that show how it works, but when brought out
into the real world, all sorts of problems occur. Now, those problems are finally
starting to get addressed. While experiments are being done on real world mesh
networks all over the place, here's an interesting report looking at a specific
mesh network call "Roofnet" being put together and tested by students at MIT.
They're using WiFi, of course, but have discovered all sorts of interesting
challenges that no one predicted. Nodes that are closer to each other in terms of
distances aren't always the best ones to communicate with each other and different
WiFi equipment (both access points and cards) seem to vary drastically in how far
and how fast they can send a signal (even when advertised to have the same range).
Furthermore, the network is constantly changing, and sometimes you'll be able to
send data one way, but not back via the same path. Also, the typical "ping" used
to judge whether or not a node can find another node is often inadequate in
determining whether or not the two nodes can actually send any real data back and
forth. They're working on all of these issues at MIT, which could help solve the
"last mile" problem of high speed internet access - and also make it easier for
"mobile hotspots" to work. If they can figure out how to get mesh networks to
work, then imagine having a WiFi access point in every car, and being able to have
the signal bounce from moving car to moving car until it finds a fixed connection.

www.techdirt.com

=====================================================================================

Networking From the Rooftop
MIT researchers are developing new routing
strategies for a wireless network that hops
data in the roofs of the city.

By Erico Guizzo
August 29, 2003

A few weeks ago, MIT graduate student Shan Sinha canceled his broadband Internet
service. Now his Net connection comes through the chimney. From a computer in the
living room of his Cambridge, MA, apartment, a few blocks from the MIT campus, a
cable goes into the fireplace up to the roof, where it is attached to an antenna.
From there, data packets hop to
another roof-mounted antenna at a nearby student’s apartment. That way, from roof
to roof in multiple hops, Sinha’s data packets finally reach a gateway—a computer
connected to the fixed Internet—at MIT’s computer science building. “We can’t use
the fireplace,” he says, “but that’s the cost of free Internet.”

Sinha’s “chimney connection” is part of MIT’s Roofnet, a project to create a
self-organizing wireless network in which an amorphous, unmanaged collection of
cheap Linux computers equipped with Wi-Fi cards collaborate to efficiently route
data packets. Each computer and roof-mounted antenna at students’ apartments and
MIT buildings is a node on the network and the arrangement in which they are
connected to each other—the topology of the network—is constantly changing.  “We
want to understand how a whole bunch of computers with short-range radios can
self-configure a network, forming order out of chaos,” says computer science
professor Robert Morris, who coordinates the project. The network has now more
than 30 nodes in a 4-square kilometer area surrounding the MIT campus.  “We hope
to reach a hundred nodes within a few months,” he says.

Research groups at universities such as Carnegie Mellon, Rice, UCLA, and the
University of Illinois at Urbana-Champaign, and at companies such as Nokia, Intel,
and Microsoft are developing similar systems. In each case, data packets are
routed through geographically dispersed and wirelessly connected nodes that can be
fixed in a building or moving with a user or vehicle. Applications of these
so-called multi-hop mesh networks include systems to connect people carrying PDAs,
tanks on a battlefield, or a large number of sensors in a factory plant. And
community mesh networks such as Roofnet, which are much cheaper to deploy than DSL
or cable hookups, are a promising way to overcome the “last mile” barrier and
bring high-speed Internet access to a large number of people, especially those who
live in rural areas or other places where the infrastructure for wired broadband
access is not available.

Community-owned wireless networks have appeared in several places in New York, San
Francisco, Seattle, London, and other cities. These networks usually consist of a
few interconnected base stations—known as wireless access points—located in
windows and rooftops providing Internet connectivity in public spaces. The new
generation of mesh networks such as Roofnet cover wider areas and are much more
dynamic in the way they route data. Their nodes are not permanently connected;
instead, they constantly revaluate the existing links and form new ones. As a
result, data follows much more tortuous paths to reach the fixed Internet. And
with tens or hundreds of nodes—some of them joining and leaving the network in a
random fashion and thus constantly changing its topology—a difficult problem
arises: how should data in these multi-hop wireless nets be routed? What paths in
this labyrinth of rooftop and window antennas optimize the flow of packets?

Distance Matters

Most of the routing protocols now being proposed by mesh network researchers
borrow the shortest-path strategy used in the fixed Internet.  These protocols try
to find the route with the fewest number of intermediate nodes between sender and
destination. For the wired Internet—with its nearly static topology and reliable
links—this scheme has been working pretty well: our e-mails hop from router to
router and reach the other side of the world in a few seconds.

But it turns out that this shortest-path strategy might not be adequate for
sending packets through the air. In a wireless network, according to the MIT
group, distance matters: the longer the signal has to travel, the more it will
degrade.  Moreover, the link quality between nodes varies unpredictably due to
such transient phenomena as trucks driving by, moisture in the air, or a pigeon
sitting on the antenna. The result is a considerable amount of packet loss,
transmission errors, and connections that simply appear and disappear throughout
the day. A routing protocol that minimizes the number of hops ends up choosing
longer distances for each hop—and therefore sending data over low-quality wireless
links.

The MIT group realized that new routing strategies were necessary when they
deployed an initial version of Roofnet last spring. They tried to implement some
of the proposed routing protocols discussed by the Internet Engineering Task
Force, the organization governing the Internet's technical standards. But while
these protocols work well in theory—and are generally tested in computer
simulations or small-scale, laboratory networks—they don’t take into account many
unpredictable factors involved in radio communication. The protocols usually
assume, for example, that when one node can detect one nearby, it can communicate
well with its neighbor. But that turns out not always to be true.  The MIT
researchers and other groups have found that many times two nodes can “hear” each
other by exchanging small probe packets, but when they try to send real data,
communication collapses due to inadequate bandwidth. Morris and his group decided
that the best way to develop robust wireless routing protocols was to test them
with a real network, real users, and real traffic.

Other mesh network researchers say the MIT work represents an important advance
for debugging these routing schemes. “Their work is grounded in real system
building,” says Victor Bahl, a senior researcher who leads the networking group at
Microsoft Research in Redmond, WA. “The insight that you get out of building
things is a lot more than you’ll ever get if you just simulate things.”
Demonstrating that such networking is viable in a real, large-scale
implementation, he says, is a crucial step toward attracting more industry
attention to the technology's potential.

Deploying such a network became possible because Wi-Fi technology has gotten so
cheap. A few years ago, Morris says, the price of the wireless cards would have
made the project prohibitively expensive. Each Roofnet node uses an 802.11b
wireless networking card installed on a cheap PC running Linux and the routing
software. A coaxial cable connects the wireless card to an omnidirectional
antenna. The user then connects the PC to the Roofnet node.  The total cost of the
equipment for each node is $685.

To deploy the network quickly, the MIT group distributes free self-installation
kits to students who want to participate in the project. For these students,
getting the Roofnet node running is part of the fun. “Our antenna was put up by a
friend of mine who does rock climbing,” says graduate student Roshan Baliga, who
lives in a two-story building with no easy roof access. “He scaled the side of the
apartment to get to the roof, installed the antenna, and then rappelled down.”
MIT students are happy to participate in the project, especially because they can
save some money. “We compared a broadband cable connection to Roofnet and couldn’t
tell the difference, so we cancelled the cable,” says MIT senior Walt Lin, who
installed the antenna on his sloped roof.

The Road Ahead

With students surfing the Web, downloading music files, and working on problem
sets on remote servers, the network is running with real traffic.  Now Morris and
the four graduate students working with him full time on the project can test
different routing strategies that better adapt to the hostile wireless
environment.

Their idea to cope with the unpredictable environmental disruptions is to figure
out not just whether two nodes can hear each other, but also measure how well they
can communicate. Instead of finding the shortest path between two nodes, their
protocols try to find the best path—the one in which data packets won’t get stuck
or corrupted along the way. This requires a constant monitoring of the links.
Roughly once per second, each node sends out a small “hello” broadcast packet. All
the other nodes record whether they receive this probe, keeping a history of the
last 10 probes. So if, say, node A has sent out 10 probes and node B received 8
and node C received 4, then the routing software knows that the path A-B is better
than path A-C. Also, every 15 seconds, every node sends a broadcast message that
lists the nodes it knows how to reach—and the link quality for each associated
path. That way, all nodes have a complete, continually updated, routing map of the
entire network—and know the optimal routes for reaching one another.

In building Roofnet, the MIT researchers found many things they didn’t expect.

For example, the range of the 802.11b cards and antennas vary considerably.
“We’re now skeptical about what manufacturers say,” says John Bicket, one of the
grad students working on the project. “We found nodes that couldn’t talk across
the street, but others could talk half a kilometer apart.” The cause might be
local environmental conditions or even multiple reflections of the same signal
that cancel themselves out. Another surprising phenomenon is the lack of symmetry
in the link transmission quality: it is not uncommon for node A to be able to send
data to node B easily, while node B can’t reciprocate. Such anomalies complicate
the development of routing schemes.

By debugging and fine-tuning their routing schemes, the MIT researchers hope they
will be able to use them in even more complicated systems. One such situation
would be when nodes are not static in rooftops, but moving at different speeds in
all directions—a scenario not far in the future, as more and more people carry
personal digital assistants and cars are beginning to be equipped with computers.
“It’s a matter of tuning the protocol so that it can handle mobility,” says Sanjit
Biswas, another student involved in the project.

Ultimately, Morris says the group plans to release the Roofnet routing software as
a freely dowloadable open source program. That means that anyone with a computer
and a Wi-Fi card would be able to install the routing software and become a node
in the network. Other people in other areas could also download the software and
create their own rooftop community networks.
Of course, many problems still need to be addressed. First, MIT can’t provide
Internet access to non-MIT affiliates; the network would therefore eventually have
to find other gateways to the fixed Internet. But that raises another complicated
issue: most Internet service providers don’t want their users sharing their
bandwidth. Also, the community networking technology needs to guarantee a certain
level of security and privacy. With users literally sending their data through the
air, via other people's nodes, some sort of encryption will probably be necessary
to avoid eavesdropping. It is also necessary to guarantee a fair, balanced used of
the system, to avoid that a single user sucks all the bandwidth and clogs the
network. Finally, the system needs to be robust enough to resist some more
pragmatic problems—such as when snow forms in the antennas.
When the day comes, what will happen? Again, the MIT group wants to learn by
doing. “We’ll see,” says Morris.

http://www.technologyreview.com/articles/wo_guizzo082903.asp?p=0

------------------------ Yahoo! Groups Sponsor ---------------------~-->
Buy Ink Cartridges or Refill Kits for Your HP, Epson, Canon or Lexmark
Printer at Myinks.com. Free s/h on orders $50 or more to the US & Canada. http://www.c1tracking.com/l.asp?cid=5511
http://us.click.yahoo.com/l.m7sD/LIdGAA/qnsNAA/61FxlB/TM
---------------------------------------------------------------------~->

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/