| 
Overview
Background
Mobile ad hoc 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
ad hoc network. Within the ad hoc network, each node
acts as a router and forwards packets on behalf of
others.
Discovering links and building paths across the mobile
ad hoc 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:
- Link discovery
- Routing
- 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 Route Advertisements"
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 in which 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 LSPs.
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 ad hoc 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 set up 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. The "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 LSPs 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 main 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.
For more information,
please contact Kevin H. Grace using the employee directory.
|
