MAD Heuristics

While the architectural model of MAD is defined, it would be very useful to start testing heuristics that will define its behavior. This page is dedicated to the study of some of these heuristics.

Heuristics #1 - Density vs Multicast rate

General description: In a dense mesh cloud we should increase the multicast/broadcast rate.

Reasoning: Multicast rates represent a trade-off between coverage and airtime consumption. Lower rates will reach distant nodes but there is a risk of clogging the mesh cloud with long (in airtime terms) frames and its respective retransmissions. In a dense cloud there is higher probability that a nearby node will successfully decode a frame transmitted in a higher rate, not only because of the proximity but also because of the higher number of retransmissions.

Possible disadvantages: The downside of increasing the rate in a dense cloud would be the segregation of occasional distant nodes, that would have a diminished change of participating to the dense cloud. It would be useful to determine if and to what extent this distant node would truly experiment more difficulty when compared to the scenario where the dense cloud uses lower rates (and possibly congests the spectrum).

Detection mechanism: One possibility to determine the number of active neighbor nodes would be reading the forwarding table and counting the number of active reverse routes. The following code achieves this

#!/usr/bin/python
# Counting the number of non-expired reverse paths
# Ricardo Carrano (OLPC - May, 08)
import commands
i = 0
reverse_paths = 0
while True:
   s, o = commands.getstatusoutput('iwpriv msh0 fwt_list '+str(i))
   if o.endswith('(null)'): break
   t1, t2, ida, ra, valid, metric, dir, rate, ssn, dsn, hopcount, ttl, expiration, sleepmode, snr, precursor = o.split()
   if dir == "0":
      time = (commands.getoutput('iwpriv msh0 fwt_time')).split(':')[1]
      if int(time) < int(expiration): reverse_paths += 1
   i += 1
print reverse_paths 

The detection of other nodes could also be based on:

• the number of beacons heard over a certain interval
• the number of distinct source addresses or transmitter addresses detected over a certain interval

The problem with both mechanisms above is that they need to be implemented in the firmware.

Reaction mechanism: There is a private ioctl to get or set the mcast/bcast rate:

iwpriv msh0 mesh_get_bcastr
iwpriv msh0 mesh_get_bcastr <rate>

Note that the rate is provided in multiples of 512kbps. Thus, the current default value of 4 corresponds to 2Mbps.

Notes:

1. In the future, the "route expiration time" will almost certainly be adaptive and this will influence the number of active reverse paths, as taken from the code proposed in the detection mechanism. A possible solution for that is to use the route expiration time as a weighting factor for this heuristics. The route expiration time can be checked with 'iwpriv msh0 get_route_exp' and currently defaults to 10 seconds.

Heuristics #2 - Power vs Metrics

General description: If a node runs on battery, it should advertise worse metrics

Reasoning: The path discovery mechanism should privilege nodes that are connected to AC and active antennas (acting as standalone repeaters). This will help prolonging battery life.

Possible disadvantages: Care has to be taken to avoid adding more hops than necessary. One way to avoid that is to use add minor increments to the costs, so this would add as an untie mechanism (see Notes bellow) Tests with more aggressive increments can also be performed.

Detection mechanism: There must be a /proc file for that (I'll check)

Reaction mechanism: There is a private ioctl to get or set the costs associated to each preq:

iwpriv msh0 [???]
iwpriv msh0 [???]

Notes:

1. Current metrics are 13 28 46 64. I propose changing this to ... [add link here]