Traffic Optimization in Mesh Networks

Background

OLPC is an organization which aims on developing a low-cost laptop – the “XO laptop” – for children to educate them. This laptop has Fedora 7 base environment and supports wireless networking with integrated 802.11b/g (2.4GHz) and 802.11s (Mesh) networking interfaces back up. It is capable of mesh operating when CPU is powered down.

Problem definition

In order to provide the required level of QoS of mesh networking it is needed to control overhead amount. The amount of control traffic grows with node number, route length or network dynamics increase. It is necessary to develop a routing overhead restricting technique with regard to dynamic changes of network parameters. Main goal is to implement such a solution on OLPC XO laptop.

Main ideas

Main idea lies in routing area restriction with optimization radius for each node. It helps to divide the whole networks into completely and less known areas. Internal routing takes place in node’s routing area which is completely known so internal routing is always optimal. External routing is made by edge nodes of the area which collect routing information from passing packets. Still such information can become out-of-date so external routing is just improved.

Route failure detection gets known rather quickly in this case. When a node cannot be reached the sender spreads this information in its routing area. Initial sender knows about route failure when its timer is over.

Another important idea is to select optimization radius dynamically.

Third is external defining of routing overhead.

Done work

As pre-work we have learned different ad-hoc routing types such as pro-active, reactive, flow oriented, adaptive and hybrid routing. We have also found out their industrial and open source implementations which are following routing protocols: AWDS, DSDV, AODV, MPRDV, SSR, PLBR, TORA, HRPLS, HSLS, ZRP and others.

The ideas of overhead control were checked theoretically with the help of overhead formulas. Different routing strategies were investigated. We found out that in large networks the developed strategy traffic is less than one in protocols like OSPF or protocols where nodes send messages periodically to remind about themselves.

Project timeline

2008 Summer: public presentation of our of solution ideas (conference proceedings or paper reports).
2008 Autumn: modules implementation for NS2 and simulations.
2008 Winter: some code contribution for XO laptops.
2009 Spring: defence of a master thesis at LETI.