Manuals just slow you down and make you feel stupid. The directions are too slow, too detailed, and use too much abstract, arcane or academic language -- like boot up instead of turn on the red switch in the back. ~Neil Fiore

MERAKI NETWORK Amitabh Banerjee(4th Yr –IT)

Overview

We can construct a wireless community network in two ways – either we construct a multi-hop network or through an access point as in Wi-Fi hotspots. But both have their problems. Construction of multi-hop network requires well-coordinated group with technical expertise while access points do not provide much coverage per wired connection as wired networks.
Meraki Network also known as Roofnet, is an ambitious plan for constructing a wireless community network that operates without much extensive planning or central management but still provides wide coverage and acceptable performance.

Introduction

Meraki Network, is a multi-hop 802.11b mesh network. The ultimate goal of Meraki is to build an ad-hoc network infrastructure capable of providing pervasive high-speed network access. It consists of many nodes. Each node is in radio range of a subset of the other nodes, and can communicate with the rest of the nodes via multi-hop forwarding. A few of the nodes act as gateways to the wired Internet. The network is self-configuring, robust in the face of Varying link conditions, and automatically finds highest throughput paths in the system. Roofnet performs well. The longest routes are four hops long. Typical latencies are dozens of milliseconds, even for long routes; typical throughputs are dozens to hundreds of kilobytes per second.

Architecture

The architecture, consisting of the following design decisions:

  • Unconstrained node placement, rather than a topology planned for coverage or performance. The network should work well even if the topology is determined solely by where participants happen to live.

  • Omni-directional antennas, rather than directional antennas used to form particular high-quality links. Users should be able to install an antenna without knowing in advance what nodes the antenna might talk to. Nodes should be able to route data through whatever neighbors they happen to find.

  • Multi-hop routing, rather than single-hop base stations or access points. Multi-hop routing can improve coverage and performance despite lack of planning and lack of specifically engineered links.

  • Optimization of routing for throughput in a slowly changing network with many links of intermediate quality, rather than for route repair in a mobile network.

Routing Protocol

Roofnet uses a new routing protocol called SrcRR. The main goal of SrcRR is to find high-throughput routes. The key challenges it faces are the intermediate quality of most links, asymmetric link loss rates, frequent changes in link loss rates, and frequent losses of routing protocol packets due to interference from hidden terminals. SrcRR's general design is inspired by DSR (Dynamic Source Routing). When a node $n_0$needs to find a route to a destination$n_d$, it broadcasts a query for$n_d$. Each node $n_i$that hears a query forwards the query, appending its own identifier to a source route in the packet. Each time $n_d$hears a query for itself; it sends a reply back to $n_0$along the source route accumulated in the query. Node $n_0$(and every node that sees the query or reply) adds all the links mentioned in the reply to a local link-state database, and uses Dijkstra's algorithm on that database to find the best route. When $n_0$sends data packets to $n_d$, it includes that route (i.e. the sequence of node identifiers) in each packet as a ``source route.''
The primary way in which SrcRR differs from DSR is that SrcRR uses the ETX metric to help it choose good routes. ETX continuously measures the loss rate in both directions between each node and its neighbors using periodic broadcasts. It assigns each link a metric that estimates the number of times a packet will have to be transmitted before it (and the corresponding 802.11 ACK) are successfully received; thus the best link metric is one. The ETX route metric is the sum of the link metrics; thus ETX penalizes both long routes and routes that include links with high forward or reverse loss rates.A node forwards a query if it has not seen the query before, or if the query's total route metric is better (lower) than the best instance of the query the node has yet seen. This increases the amount of query traffic, but decreases the algorithm's bias in favor of shortest hop count. Nodes also delay for a random period less than one second before

forwarding a query to avoid contention. When a node forwards a query, it includes the link ETX metric to whatever node it heard the query from; nodes store these metrics in their link-state databases, and use them to compute the route metric to minimize with Dijkstra's algorithm. While a source node is sending data along a route, SrcRR uses the following techniques to discover if the route has broken or declined in quality. First, when a node forwards a data packet, it updates the packet's source route to contain the latest ETX metric from the preceding node; if the routes in the two directions are the same; this suffices to keep both ends aware of the current route quality. Second, if the 802.11 card indicates that ten packets in a row have failed to elicit an 802.11-level ACK, the node will send the current link metric to the source. Third, if a node is passing data in one direction but sees no data in the other (i.e. the route is asymmetric or broken), it will periodically send the current link metric to the source. Fourth, if a source node sees a new metric for a link it is using, it re-runs Dijkstra's algorithm to ensure it is using the best known route. Finally, if a source node notices that the route it is using has a current route ETX metric more than twice as high (half as good) as the best it has seen since the last query, it will flood a new query.

Discussion

Meraki Network strives to lay the foundation for a useful and pervasive Internet service network that can grow organically with only loose or non-existent control. Ideally, such a network should be built out of cheap hardware so that large deployments are feasible, and the system should be able to compete in some dimension (if only ease of deployment) with available commercial service such as DSL or Cable. Thus, for ideological reasons, Meraki’s design stresses self-configuration and the avoidance of central mechanisms. Building the network provides an opportunity to test research designs by by exposing them to real radio propagation, a real user workload and the robustness requirements of a production network.