Wifi Highway - could this work?

Eugen Leitl eugen@leitl.org
Fri, 3 Jan 2003 16:28:59 +0100 (CET)


On Thu, 2 Jan 2003, Jeff Barr wrote:

> So, here's the big idea. What if I WiFi-equipped my car and a bunch of 
> other commuters did likewise? Would it be possible to dynamically form 
> a network from all of these cars and have car-to-car connectivity? Imagine
> some kind of cheap subscription service to pay for wired-to-WiFi bandwidth
> at some convenient choke points. Sponsorship could also be used.

You've just stumbled upon another reason why current protocols suck. You 
might be able to link up to static WiFi spots as you drive through the 
cell, but getting the routing right in a sea of dynamic nodes won't happen 
without geographic routing, which won't happen without realtime 
localizers, which basically forces digital pulse radio down your throat, 
whether you want it, or no.

Meanwhile, you should check out efforts like 

	<http://www.mitre.org/tech_transfer/mobilemesh/>

Providing Solutions For Mobile Adhoc Networking 
# Background
# Protocols
# Software
# Requirements
# Download
# License
# Documentation
# Mail List
Background
Mobile adhoc networking allows users to exchange information in a wireless 
environment without the need for a fixed infrastructure. Each user (or 
node), equipped with one or more radios, is free to roam about while 
communicating with others. The path between any pair of users can traverse 
multiple wireless links and the radios themselves can be heterogeneous, 
thus enabling an assortment of different types of links to be part of the 
same adhoc network.

The mobility of the nodes results in a network whose topology is dynamic.  
The job of the network is to discover the links between the mobile nodes 
and to build paths so that any user can communicate with any other user, 
as long as each has a link to the adhoc network. Within the adhoc network, 
each node acts as a router and forwards packets on behalf of others.

Discovering links and building paths across the mobile adhoc network are 
challenging problems. As part of our Mobile Mesh research project, we have 
developed a suite of non-proprietary protocols  and Open Source software 
tools that we believe provide robust, scalable, and efficient solutions.
Protocols
We have developed three separate protocols, each addressing a specific 
function, namely:

   1. link discovery
   2. routing
   3. border discovery

An aesthetically pleasing aspect of these protocols is that they each 
contain only a single message type. This form of simplicity, we believe, 
will enable others to easily understand and implement the protocols. Also, 
by keeping each function separate, we enable flexibility and 
extensibility. For example, if a radio is able to discover links at the 
link layer, then there's no need to run our link discovery protocol, yet 
we will still want to utilize the routing protocol.

    Link Discovery
    Our Mobile Mesh Link Discovery Protocol (MMLDP) is based upon a 
traditional "Hello" protocol. Each interface running the protocol 
periodically broadcasts a Hello message containing its interface address 
and the addresses of the interfaces that it has heard Hello messages from 
in the previous period. This is sufficient for a node's interface to 
discover all links incident to it as well as bidirectional links.
    Routing
    Our Mobile Mesh Routing Protocol (MMRP) is based upon the link state 
approach and allows us to build least cost paths between any source and 
destination.   Each "Link State Packet" (LSP) contains various information 
including a unique router id and a list of lists that contains each local 
interface address and a list of the neighbor interface addresses which 
have links to it and their corresponding costs. Also in the LSP are a list 
of "External RouteAdvertisements" which enable the node to advertise 
routes into the mobile cloud. One use of this is to allow routers that 
have a wired connection to a fixed network to advertise a default route 
for the mobile nodes. Thus, we provide a mechanism for allowing mobile 
nodes to gain external connectivity. Also, this mechanism can be used by a 
wireless router to advertise a route for a collection of hosts which are 
directly connected to it.

    To enhance scalability, we perform a technique called fish-eye routing 
where the resolution of a node's map of the network is a function of 
distance. This enables us to decrease the overhead associated with the 
flooding of LSP's.
    Border Discovery
    Our Mobile Mesh Border Discovery Protocol (MMBDP) is a novel mechanism 
that enables flow existing outside the mobile cloud to be utilized Other 
approaches to mobile adhoc networking ignore this possibility. If two or 
more nodes in the mobile cloud each have a connection into a fixed network 
(let's call these nodes "border" routers), then the opportunity exists for 
mobile nodes to communicate with other mobile nodes across the fixed 
network. This is accomplished by setting up tunnels between the "border" 
routers across the fixed network. Our border discovery protocol enables a 
"border" router to discover other "border" routers and then setup tunnels 
with them. We believe the ability to leverage flow across fixed networks 
is an important capability that will someday be commonplace.

Software
The Mobile Mesh software includes separate Linux based programs that 
implement each of the above protocols.

    * mmdiscover - Performs link discovery on an individual IP interface
    * mmrp - Speaks the Mobile Mesh Routing Protocol and computes least 
cost routes
    * mmborder - Discovers other border routers and automatically sets up 
tunnels to utilize collateral flow

These tools are loosely coupled and communicate with each other through 
Unix sockets. This software architecture enables any piece to be easily 
swapped out and replaced, just as long as it speaks the right messages 
across the Unix socket. Our goal was to build flexible and extensible 
pieces so that they could evolve independently of each other. This is a 
key requirement for building future-proof networks.

No set of tools would be complete without a visualization tool and Mobile 
Mesh has one. "mmrpviz"graphically displays all nodes, their interfaces, 
and links in the network. Links can optionally be labeled with their costs 
and nodes can be labeled with various useful information from LSP's like 
sequence number and age. Newly discovered links are drawn in green, links 
that have recently broken are drawn in red. A screenshot is available 
here.The visualization tool has proved quite valuable in our development 
of the routing protocol and we think it will benefit others as well. When 
you wonder why your mobile router can't communicate with another, the 
visualization tool let's you know where the links in the network really 
are.
Requirements
The Mobile Mesh software was developed for a Linux  2.2.X kernel. It's 
quite possible that it may run under 2.3.X kernels as well, but, the 
author has not tested this. The Mobile Mesh software is comprised of user 
space code and does not contain any kernel modules or modifications.

The Mobile Mesh tools require additional software packages:

    * mmborder requires  iproute2
    * mmrpviz requires GraphViz

Download
The latest version as well as archived versions of the source code is 
available here.
License
Mobile Mesh is covered by this license agreement.
Documentation
The Mobile Mesh protocols are documented in the following Internet Drafts:

    * Mobile Mesh Link Discovery Protocol [txt]
    * Mobile Mesh Routing Protocol [txt]
    * Mobile Mesh Border Discovery Protocol [txt]

The Mobile Mesh distribution contains man pages of the various software 
tools:

    * mmdiscover  [pdf]
    * mmrp [pdf]
    * mmborder [pdf]
    * mmrpviz [pdf] and related mmtodot [pdf]

Also, a brief FAQ is available here.
Mail List
A Mobile Mesh mail list exists for users and developers to discuss issues 
related to the software distribution. The discussion includes questions 
about using the software, bug reports, and announcements of updates to the 
distribution. To subscribe to the discussion, send an email to 
listserv@mitre.org with a body containing the line "subscribe 
mobilemesh-list YourFirstName YourLastName".  To unsubscribe, send an 
email to listserv@mitre.org with a body containing the line "unsubscribe 
mobilemesh-list YourFirstName YourLastName". After subscribing , you may 
post emails to the discussion by sending them to 
mobilemesh-list@lists.mitre.org.

Last update: 11 October 2000