Path Discovery Mechanism

The XO's Path Discovery Mechanism (PDM) is based on HWMP which is part of the IEEE802.11s draft. Throughout this document, we will refer to this mechanism as XO's PDM or just PDM.

Reactive, Proactive and Hybrid

XO's PDM is a Reactive mechanism. This means that a Path will be discovered only if necessary, what contrasts with a Proactive protocol that exchange topology data constantly. Examples of a reactive protocol are the Ad-hoc On-Demand Distance Vector (AODV) and the Dynamic Source Routing Protocol (DSR). Popular proactive protocols are the Optimized Link State Routing Protocol (OLSR) and the Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV).

There seems to be a consensus that Reactive protocols have the disadvantage of a higher path acquisition when compared to Proactive protocols - that will compute paths in advance. On the other hand, computing paths in advance may mean a waste of network resources. Some of the paths may never be used and if the mesh cloud is highly mobile, pre-computed paths may be rendered obsolete even before used.

Some protocols try to address both disadvantages by proposing a Hybrid approach. This is the case of the Zone Routing Protocol (ZRP) and the Hybrid Wireless Mesh Protocol (HWMP). The latter was chosen to be implemented in the future IEEE802.11s standard. It is basically a reactive protocol augmented by a proactive mechanism designed to permits that a node announces itself as the root of a tree based topology. This mechanism is not implemented in the XO's PDM.

Link Layer and Network Layer

XO's PDM is a link layer based mechanism. Hence, the term Path should be preferred over Route and we should talk about Path Discovery, instead of Routing. The XO's PDM is totally implemented at the link layer (or layer two) as opposed to the more common approach that implements the routing functions at network layer (or layer three). This means that MAC addresses are used by the PDM, instead of IP addresses and a mesh cloud may appear as an Ethernet physical network to upper layers.

Although according to the OSI model, routing is to be implemented at the Network Layer, there are some advantages of implementing a Path Discovery mechanism at the Link Layer, the most obvious being the fact that this layer has direct access to radio/link parameters what is much more important in wireless than in wired networks. This also makes it easier to embed the path discovery mechanism in a SoC, like the Marvell 8388, used by the XOs.

A clear disadvantage is the fact that the layer two address space is non-hierarchical, what makes MAC-based forward tables not as scalable as IP routing tables. On the other hand, is important to recognize that layer two ad-hoc networks are not meant to scale to huge internetworks, but to provide bridging capabilities to tens of nodes.

WMNs, Sensor Networks and MANETs

Multihop wireless networks fall into many categories. Probably the most widespread of these categories is the Wireless Mesh Networks (WMN). A WMN is basically a collection of fixed nodes, most of the times consisting of regular access points running adapted software. Its main goal is to provide an inexpensive and easily deployable wireless backhaul that will connect distant LANs or WLANs.

Operational WMNs can be found around the world and are mostly based on traditional network layer routing. Some examples are the FunkFeuer Net in Austria, MIT’s RoofNet, VMesh, in Greece, UCSB’s MeshNet, CUWin in Urbana, ReMesh in Brazil and Microsoft Mesh among others.

A WMN is not necessarily an ad-hoc network, in the sense that it can benefit from ahead planning on the position of the nodes. Nonetheless, nothing prevents it from growing organically like the FunkFeuer Network, in Austria, or the Meraki Public Network in San Francisco.

Sensor networks are another increasingly important class of multihop wireless network. Its main goal is the consolidation of information collected from distributed nodes – the sensors – spread over a given area. The sensors might be mobile, like the collars attached to coyotes in UCSC’s CARNIVORE Project or to zebras in Princeton’s ZebraNet; or fixed, like the ones installed in floaters or tree tops to collect environmental data, like temperature or the incidence of light.

Independent of the application or the scale, one important characteristic of a Sensor Network is that the information travels to central nodes, where the researcher or a monitoring process analyze the data and infer its conclusions.

A third category of wireless mobile networks, and the one that we are most interested in, is the Mobile Ad-hoc Mobile Network, or MANET. These networks are designed to provide connectivity to mobile computing devices without the aid of an infrastructure. From now on, when we refer to a mesh, or to a mesh cloud, we are actually referring to a MANET formed by XOs.

Differently from a WMN, a MANET is a self-configuring network where there are no fixed routers. In a MANET, routers are free to move and the topology of the network can change dramatically and quickly. Traffic routing functions will be carried on by some or all of the participating nodes. Moreover, differently from a Sensors Network, there may be no clear concentration of traffic to a given node. Though some concentration may happen if one node offers an attractive service to the mesh cloud – like gateway provisions to the Internet – any two nodes might want to communicate.