Mesh Forwarding Table

From OLPC
Jump to: navigation, search
  This page is monitored by the OLPC team.

Introduction

The Mesh is a dynamic configuration through which two laptops can communicate with each other through a dynamically updated path. This path can be direct(single hop) if the two laptops are close to each other. However, when this is not the case, it includes several hops. When a new laptop enters the Mesh it configures itself in the network using a routing protocol. Eventually it builds up a forwarding table, which determines the path to each individual laptop in the Mesh.

In order to forward a packet to a specific destination, the laptop checks the forwarding table and sends the packet through the correct direction. In fact the complete routing is transparent to the interface. The table only includes the next hop to the path. For example if the path from xoA to xoB is

xoA---------xo1----------xo2-----------xo3----------xoB

the forwarding table of xoA will only link xoB to xo1. Each possible xoA's destination(like xoB or xo3) is paired with its corresponding first hop of the path. The first hop must always be a neighbor to xoA. In the next hop the packets check the new forwarding table and send the packet accordingly. The routing protocol belongs to the Layer 2 interface, and therefore includes the MAC addresses of the laptops.

Accessing the Forwarding Tables

The Marvell WLAN Linux Driver used in the laptops provides several ioctl calls to examine the Mesh configuration. The most useful command is iwpriv which focuses on the forwarding table. By applying iwpriv eth0 or iwpriv msh0 we have access to several commands, the most interesting of which are

iwpriv msh0 fwt_list n          # gives the n-th entry of the forwarding table 
iwpriv msh0 fwt_list_neigh n    # gives the n-th entry of the neighbor table
iwpriv msh0 fwt_reset           # resets both tables

The parameters eth0 and msh0 indicate the interface you need to examine. Note that one can examine the interfaces through ifconfig/iwconfig. In both cases you have the same MAC address and iwpriv gives the same tables, so one may use either. It is unfortunate that using the above commands you only have access to a single entry defined by parameter n. To examine the whole table one must execute the fwt_list[_neigh] commands for all desired values of n. Each single entry is displayed as

iwpriv msh0 fwt_list n

     output is a string of the following form:

          da ra valid metric dir rate ssn dsn hopcount ttl expiration sleepmode snr precursor

     where the different fields are:

          da		-- DA MAC address (in the form "00:11:22:33:44:55")
          ra		-- RA MAC address (in the form "00:11:22:33:44:55")
          valid		-- whether the route is valid (0 if not valid)
          metric		-- route metric (cost: smaller-metric routes are preferred)
          dir		-- direction (1 for direct, 0 for reverse)
          rate		-- data rate used for transmission to the RA
          ssn		-- Source Sequence Number (time at the RA for reverse routes)
          dsn		-- Destination Sequence Number (time at the DA for direct routes)
          hopcount	-- hop count (currently unused)
          ttl		-- TTL (only used in reverse entries)
          expiration	-- entry expiration 
          sleepmode	-- RA's sleep mode (currently unused)
          snr		-- SNR in the link to RA (currently unused)
          precursor	-- predecessor in direct routes
iwpriv ethX msh0 list_neigh n

     output is a string of the following form:

          ra sleepmode snr references

     where the different fields are:
          ra		-- RA MAC address (in the form "00:11:22:33:44:55")
          sleepmode	-- RA's sleep mode (currently unused)
          snr		-- SNR in the link to RA (currently unused)
          references	-- RA's reference counter

If the entry number requested is beyond the length of the table then you receive a null error message

Forwarding Table Characteristics

The forwarding table updates by adding additional lines not by replacing previous ones. An entry however can be removed when it expires. The starting expiration time may be checked though

iwpriv msh0 fwt_time            # in ms(or chip ticks)

When a new path for a specific destination becomes available it is updated in the forwarding list, and this is usually long before the previous entry for the same destination has expired. Subsequently, most entries are not up to date.

The neighbor table is similar to the forwarding table, but only includes a list of the neighbors, which also represent the first hops for all other destinations. These neighbors are also included in the forwarding table but of course destination and first hop are the same.

How to get viewable results

In order to view the complete forwarding table or neighbor table, a linux script is available check for all entry indexes. The script can be executed to an XO from a USB stick. To access the stick do

ls /media                        # list of connected USB sticks: useful to see the stick's name
cd /media/[name of your stick]/  # access the USB stick folder

Make sure the script is named in the proper case. It can be executed as

bash mesh.sh param1 [param2]
    
    options for param1:
        
         table      -- forwarding table
         neigh      -- neighbor table

    options for param2(optional):

         reset      -- resets the current table before displaying the table

When not using reset mode the script will show the current table and terminate right after. However, when using the reset mode the tables are completely cleared, and the script waits for each entry to show up. It will run indefinitely and can be stopped at any time with Ctrl^c. Usually the forwading table will rebuilt itself in less than a minute. The neighbor table, which is technically easier to fill, requires a few seconds. A typical view of a neighbor table is

    neighbor addr

0 00:11:22:33:44:01 slp 0 snr 39 ref 3
1 00:11:22:33:44:03 slp 0 snr 49 ref 0
2 00:11:22:33:44:10 slp 0 snr 60 ref 2
3 00:11:22:33:44:04 slp 0 snr 53 ref 3
...

A typical view of a forwarding table is

      dest addr       neighbor addr

0 00:11:22:33:44:f1 00:11:22:33:44:01 data ...
2 00:11:22:33:44:ba 00:11:22:33:44:01 data ...
3 00:11:22:33:44:70 00:11:22:33:44:04 data ...
...

Translate MAC address to XO name

It is desirable to view the OX names instead of their correspondig MAC address. Then it is easy to observe in the lab how the Mesh really works. For this purpose a table is required which links each MAC address with its corresponding name (A01, B02 etc). An excel file will be available in Google Docs for testers to update any additional pair of MAC and name.

Testing the MPP configuration

An interesting configuration of the mesh is the Under a Tree model. In that case there is no access point to provide infrastructure for the mesh. This can be examined with a few(5 to 10) XO's that none has access to any AP. In fact you can force a laptop into this and skip connecting to any available mesh or access point. One of the laptops can turn on the MPP cabability and create mesh. This can be implemented in the lab by using channel 6 or 11. The other XO's will connect to this mesh and their tables will be observed as they are updated.