Path Discovery Mechanism

This page is dedicated to the Path Discovery Mechanism currently (Jun 08) implemented in the XO.

It starts with an introduction, with some simple taxonomy mainly directed to those not familiar with the field of wireless ad-hoc networks. This introduction can be safely skipped by those already familiar with the topic.

We then proceed to a brief and simple introduction to the mechanics of the path discovery.

In the end, and throughout the document, we provide links to more detailed explanations of many aspects of the mechanism.

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

-- Ricardo Carrano

Introduction

Multihop wireless networks evolved to adapt to different uses and may be implemented in many distinct ways. Before we move on to the details of the XO's PDM, its important to understand what type of network we are using when a lot of XOs are put together.

A fundamental distinction must be clear from the very beginning: What is to be describe here is not a infrastructure network which is formed by stations (the XOs in this case) associated to Access Points and communicating through them. This page is dedicated to the Mesh Network that forms spontaneously when more than two XOs are tunned in the same channel and operates without any kind of infrastructure.

More precisely, this page is dedicated to explaining how XOs discover each other in order to communicate, i.e. to the Path Discovery Mechanism it uses.

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. HWMP is basically a reactive protocol augmented by a proactive mechanism designed to permit that a node announce 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, it 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 and ReMesh in Brazil, 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.

Sensors 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.

Brief description of the Path Discovery Mechanism

The path discovery mechanism currently implemented in the XO is based on HWMP, proposed in IEEE802.11s draft, which is in turn based on the AODV protocol. It is actually quite similar to what we may find in many reactive mechanisms.

The main idea is that when a node S has data to send to another node Dit will check its forwarding table for a valid (not expired) path to D. If there is none available, S will send out a PREQ (Path REQuest) cluster. The PREQ cluster consists of four frames, sent back-to-back transmitted at different data rates (54, 36, 11 and 1 Mbps). Each of these PREQ frames has a different associated cost.

Since there is no indication of the location of D, all nodes in the mesh cloud will retransmit the PREQ cluster, so there is guarantee (actually only a high probability) that D will receive at least one PREQ. This is normally called Network-Wide Broadcast, or Simple Flooding.

When an intermediary node receives a PREQ it should retransmit it at least one time. Every PREQ has an associated metric, which depends on the data rate at which its transmitted and also the previous PREQs that form the path.

Suppose a node I listens to the original PREQ cluster from S. If I is too distant from S or the link between them is marginal, there is a chance that I will not listen to all the four PREQs in the cluster. Let's say that I successfully decodes the PREQs transmitted at 11 and 1Mbps. What he has to do next is to retransmit the PREQ with the better metric, with updated costs. Check the metrics page for details.

Eventually a PREQ will reach D, which in turn shall respond with a PREP (Path RESPonse) frame that must reach S - when it does, a path between S and D is formed.

A more detailed description of the Path Discovery Mechanism can be found here.

Where to go from here

• For more detailed information on the Path Discovery Mechanism
• You probably want to know more about the metrics
• There is also a a page on the main differences to IEEE802.11s