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.
Link DiscoveryOur 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.
RoutingOur 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 DiscoveryOur 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.
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.
The Mobile Mesh tools require additional software packages: