Architecture and Evaluation of an Unplanned 802.11b Mesh Network
url show details
You need to log in to add tags and post comments.
| papers | collections | search | login | register | forgot password? |
|
| papers | collections | search | login | register | forgot password? |
|
This paper describes a wireless mesh network called Roofnet. The network has unplanned node placement,omni-directional and multi-hop routing, which allows the network to be more flexible in terms of deployment and helps to get a getter coverage.
In terms of hardware each node consists of a PC with an 802.11 card.
Roofnet nodes are self-configuring in terms of:
- Addresses: Each node has an address made of the low 24 bits of its
Ethernet address and the high 8 bits of an unused class-A IP address.
-Gateway and Internet Access: each node checks whether it can connect
to the Internet through its Ethernet port (it tries to connect to a
well-known server). If in fact it can, it will behave as a gateway for other Roofnet nodes. If not, the node connects to the Internet through Roofnet.
-Routing: Srcr (roofnet's routing protocol) tries to find the route with
highest throughput. Each node keeps a database of known link metrics
between pairs of nodes and uses Dijkstra to calculate the routes.
Nodes learn link metrics by using flood queries or through packets
that arrive (packets contain source-routes)
The metrics used for routing is the estimate amount of time it would take to send a packet along the route(ETT). Srcr chooses the routes with the lowest ETT.
Evaluation:
- The authors conclude that in multi-hop routes, the throughput is less than the
predicted value due to inter-hop collisions.Results show that the equation used by the
authors to calculate ETT will not deliver a good estimate of the throughput for routes
will several hops
- Most nodes communicate only with the Internet Gateway with the best metric, and nodes use routes
with fastest links,showing that Srcr works well with this network
- Latency is affected by 802.11 retransmissions and back-offs, and results
suggest that, although acceptable over a few hops, latency can present a
problem with more than 9 hops.
- The network needs a density of five nodes per km2 to achieve full connectivity , and Roofnet
can cover all nodes using less gateways than a single-hop architecture
- Results show that in terms of throughput to a gateway, multi-hop (used by Roofnet)
outperforms single-hop routing.
-The density of the networks helps to get better throughput since there are more routes to
choose from
Issues:
The authors used a "pseudo-IBSS" that omits 802.11 beacons as well as BSSID, as those would lead to partitions that make the usage of Roofnet unreliable.How to use Roofnet-like networks with standard 802.11 ?
With a bigger network, the number of collisions and interference caused by others will increase,
and some of the results (especially latency) will probably be worst. A large network with unconstrained node placement and omni-directional antennas may be harder to manage(self-configure)and have worst performance then Roofnet.
If the network spans over a large area and routes with several hops are necessary, results show
that the equation used by the authors will not deliver a good estimate of the throughput, each
will cause Srcr to not choose the best routes.
This paper describes the architecture of a wireless mesh network, Roofnet, and evaluates it performance.
Roofnet is aiming at providing high performance Internet access, with three design considerations:
1. for unplanned topology;
2. with omni-directional antennas;
3. using multi-hop routing protocols
Roofnet contains 37 nodes over 4 square kilometers of urban area.
The paper obtains the following conclusions for Roofnet:
1. It gets a median of 400 kbits/sec and an average of 627 kbits/sec for throughput between all pairs of nodes;
2. Throughput decreases with the increase of number of hops, also the latency grows(disproportional, is it exponential?)
3. Throughput also decreases with the increase of link distance, and most links between 500-1300 meters can get throughput of 500 kbits/sec;
4. The network could get full function with about five nodes per square kilometer;
5. The majority of nodes use many neighboring nodes rather than only one or two; also it is robust to the loss of links
6. It also compares the performance with the single-hop, directional links. Roofnet improves both coverage and throughput.
7. The paper also provides the statistics of 24 hours network usage.
Issues:
1. Is there any pow-law phenomenon in the data collected in this paper? e.g. figure 3. the throughput vs distance, would a straight line fit the data in log-log scale? Table 2, the latency with respect to the number of hops?
2. The author collects the real network usage and distribution packets according to different type, would that be different for the throughput for different types of transferring (short connections vs BitTorrent p2p file traffic)?
3. Some minor question: Table 1, the latency for 7 hops is a bit strange, lower than the 6 hops, is it noise or characteristic?
The paper implements a multi-hop routing distributed wireless network (with its design choices) and shows its properties, then concludes that it's a viable idea. However, as they suggest in section 3.7 and Miguel mentions, if there are a lot of nodes, the "inter-hop collisions" might become a major problem. But if there are too few nodes, then connectivity suffers. This seems like a major roadblock to making this popular.
More importantly, maybe I don't understand this area well, but what is the motivation for such a network? Is it so not everyone has to pay the ISPs, just a few people in the network?
Regarding the motivation of this work, even though there is a company trying to commercialize this technology (Meraki?), I don't know why it would be practical in the real world. If this technology is to be deployed mainly in urban areas, we already have good demographic and geographic information about the area, and then carefully coordinate the deployment. (Additionally, it might have to compete with broadband cellphone networks like WiMax.)
I enjoyed reading this paper, but still doubt its practicality.
"just 3% were BitTorrent" -- I wonder if this number would be somewhat higher today, or if the latency and bandwidth of the network discourage BitTorrent use.
It is very impressive that they were able to achieve good levels of connectivity and throughput despite all of their design decisions that they feared would substantially hurt performance. I especially found section 3.6 interesting, in which they compare Roofnet's multi-hop system to a hypothetical single-hop system. While multi-hop routing involves less planning and topology-specific considerations than single-hop, the results of this section strongly suggest that it actually improves performance. First, they show that for "optimally" chosen gateways multi-hop routing has higher throughput for any # of GW's than single-hop routing. Furthermore, for five or fewer gateways even randomly chosen multi-hop gateways provide better performance than single-hop gateways, although the single-hop performance is higher for larger numbers of gateways. Even though they consider various experimental modifications and randomizations throughout the paper, I do wonder whether their conclusions would generalize to other networks, since clearly the sample size of their experiments is not very large.
What I learned from this paper is, a wireless network can perform well without carefully planning, given the density of nodes is high enough. Most nodes get to Internet within one or two hops. I am not sure about the use of throughput between nodes to justify the performance since I guess most daily use might be the downloading or web browsing from Internet.
Regarding Jim's comment, 3% is the percentage of connections. The paper says 30% traffic is generated by BitTorrent.
I think the "unplanned" characteristic of the network mainly came from the contraint of their initial experiments that depend on voluntary nodes at random locations. In a real-business case where deployment location is under control, demographic and geographic information may be used to sophisticate deployment.
This paper focuses on community wireless networks, like networks of a small campus or a number of apartment buildings with the same owner.
To supplement Miguel's comment, the bit-rate selection algorithm described in Sec. 2.5 could adaptively choose the right bit rate to optimize the ETT. And here it is not a good idea to optimize the # of hops.
As an application, I also wonder how useful this is in practice, especially in a "typical" neighborhood environment. If the ISP wants to deploy their service wirelessly, then I would be concerned first and foremost about quality of service and bandwidth guarantees to my customer--which means I will probably not be deploying infrastructure in an ad-hoc way. With that being said, I think there are other applications in less-developed areas. The OLPC project (http://en.wikipedia.org/wiki/OLPC_XO-1#Wireless_mesh_networking), for example, uses wireless mesh networking to provide connectivity to a distributed number of nodes. Another issue I wondered about is the reliability aspect of this infrastructure. How can quality of service be addressed for those few nodes who share fewest neighbors, if indeed Roofnet is the first-class Internet provider?
I thought the paper made some reasonable design choices and evaluated them thoroughly. I particularly liked sections 3.6 and 3.7 which show the strength and limitation of multi-hop routing.
One statement that stood out was, "If roofnet were a single-hop network, 25 gateways would be required to cover all the nodes." Clearly, under the scenarios they choose, multi-hop routing is essential. As Eric pointed out in a previous comment, it is possible to think of places where such scenarios exist.
One question I wondered about was the possibility of multi-path routing. Does anyone know if this is (in)feasible in wireless settings? It would seem that multi-path routing would improve the robustness of such networks to failures.
Finally, in reply to Lei Li's comment on the power law, I don't think there is enough data to say anything for sure. log-log plots smooth out a lot of variation in the plot, which may or may not be noise. If there isn't enough data, I think it is very difficult to distinguish noise from the signal.
For example, this kind of network might be used in areas like desert, where unplaned mobile nodes are more useful.
This paper describes and evaluates roofnet, a wireless mesh network that requires little deployment and management effort. The ideas presented in this paper seem to be well-suited for wireless metropolitan area networks (such as http://seattlewireless.net/ or http://www.awmn.net/) or other non-structured self-configuring multi-hop networks( such as a network of OLPC laptops).
Issues/Questions:
- Although this architecture should work well using only omni-directional antennas, 3 roofnet-nodes use Yagi directional antennas and the authors provided no additional information about this. Would roofnet still perform well if these nodes also used omni-directional antennas?
- The latency, presented in Tables 1 and 3, does not always increase as the hop-count increases. I was expecting the latency to be a strictly increasing function of hop-count.
- How does 802.11s (used by OLPC) compare to the roofnet architecture?
Although this unplanned mesh network seems not to be suitable for commercial services, because this network doesn't require access points which, I take for grant, might be the major source of investment cost in providing community wireless network, this network might be a good candidate for the government to provide universal service of Internet access in rural areas.
Roofnet seems to create an interesting game:
As a user of Roofnet (say I also maintain an antenna), I can choose whether I want to purchase my own connection to the internet, and serve as a base, or simply connect to the internet through Roofnet. Obviously the performance of Roofnet works better when more people have direct connections to the internet (and cannot work if no one does!), but as an individual, by choosing to cancel my direct network connection, I may only incur a small loss (the general degradation of the network due to fewer landline connections), but accrue a large gain (I don't have to pay my internet bill anymore). This probably leads to bad outcomes...
So as an algorithmic question, it would be interesting to consider (according to some metric), given a Roofnet network, what is the optimal placement of landline connections among the nodes, and as a game theoretic question, what are the incentives needed to achieve this?
This seemed to be an interesting paper showing how using unplanned 802.11 network can be practical. I am not sure how it will be a problem with bigger networks. The density analysis shows that it would be useful to have more Roofnet nodes as they can make use of short high-quality links. Probably, it might be a problem beyond a threshold due to inter-hop interference? As long as the ratio of total number of gateways to total number of nodes and the placement of gateways isn't too bad, it seems to be an idea that can work, though I don't know how well it can compete with other existing technologies.
Yes, Meraki is a start-up by the Roofnet folks. I think it uses ExOR also.