LWMesh - Stack modifications

[fgargiulo]

First of all, hi. This post is intended for anyone who has ever used LWMesh and might help me with some advices, but specially for Alex, who has always answered my concerns and helped me along the development of my project mucho more than i ever expected.

During the last months I have been testing the AODV algorithm implemented in the LWMesh stack and I have found some specific issues related to the way a node generates and maintains its route entries.
I consider the stack is an excellent starting point and that it should be modified by the user to satisfy the requirements of a specific application. So, what I look for with this post is to know your opinion about each of the issues I encountered and if you consider that the solution adopted is adequate or there is something that I am missing that could generate even greater problems.

• Using the netSim simulator first and then debugging real hardware I could verify that sometimes, when a message is sent unicast through a node, the duplicate rejection screening generates a call to nwkRouteRemove(), causing the route to be eliminated and forcing a new route discovery.
  I understand that the duplicate rejection table is used for detection and prevention of the loops in the routes (ex, when using Native Routing algorithm), but is it possible that loops happends when routes are build based on AODV?
  What I could observed is that this situation occur when the transceiver automatically retransmit a frame when it was not acknowledge by the destination node; and so, as a result of the rediscovery and due to the nature of the AODV algorithm, after the route is removed, the whole network is flooded with NWK_COMMAND_ROUTE_REQUEST.
  To avoid this situation, I have modified the implementation of the function:
  
  

Code: [Select]

static bool nwkRxRejectDuplicate(NwkFrameHeader_t *header)
by adding

Code: [Select]

#ifndef NWK_ENABLE_ROUTE_DISCOVERY
#endif
in the next way

Code: [Select]



static bool nwkRxRejectDuplicate(NwkFrameHeader_t *header)
{
NwkDuplicateRejectionEntry_t *entry;
NwkDuplicateRejectionEntry_t *freeEntry = NULL;

for (uint32_t i = 0; i < NWK_DUPLICATE_REJECTION_TABLE_SIZE; i++) {
entry = &nwkRxDuplicateRejectionTable[i];

if (entry->ttl && header->nwkSrcAddr == entry->src) {
uint8_t diff = (int8_t)entry->seq - header->nwkSeq;

if (diff < 8) {
if (entry->mask & (1 << diff)) {
#ifdef NWK_ENABLE_ROUTING
#ifndef NWK_ENABLE_ROUTE_DISCOVERY
if (nwkIb.addr == header->macDstAddr) {
nwkRouteRemove(
header->nwkDstAddr,
header->nwkFcf.multicast);
}
#endif
#endif
return true;
}

entry->mask |= (1 << diff);
return false;
} else {
uint8_t shift = -(int8_t)diff;

entry->seq = header->nwkSeq;
entry->mask = (entry->mask << shift) | 1;
entry->ttl = DUPLICATE_REJECTION_TTL;
return false;
}
}

if (0 == entry->ttl) {
freeEntry = entry;
}
}

if (NULL == freeEntry) {
return true;
}

freeEntry->src = header->nwkSrcAddr;
freeEntry->seq = header->nwkSeq;
freeEntry->mask = 1;
freeEntry->ttl = DUPLICATE_REJECTION_TTL;

SYS_TimerStart(&nwkRxDuplicateRejectionTimer);

return false;
}


This way, a route only is removed when its score equals 0.

• With respect to the reduction of the score, I have noticed that it is done inside the function:
  

Code: [Select]

void nwkRouteFrameSent(NwkFrame_t *frame)
When the status returned by the physical layer is one of the following:

Code: [Select]

NWK_ERROR_STATUS       
NWK_OUT_OF_MEMORY_STATUS
NWK_NO_ACK_STATUS                   
NWK_NO_ROUTE_STATUS                   
NWK_PHY_CHANNEL_ACCESS_FAILURE_STATUS
NWK_PHY_NO_ACK_STATUS         

When a node could not send a message because of a channel access failure, does it mean that the route entry is incorrect and possibly a candidate to be removed? I do not understand why the score is decremented in this case.
Using netSim simulator I have observed that in big networks (composed of 1000 nodes), route discoveries are generated because the score is decremented for this reason and the new route found turns out to be the same one that was removed.
So, to avoid this situation, I have modified the implementation of the function:

Code: [Select]

void nwkRouteFrameSent(NwkFrame_t *frame)
adding the condition

Code: [Select]

else if (NWK_PHY_CHANNEL_ACCESS_FAILURE_STATUS != frame->tx.status)

in the next way:

Code: [Select]



void nwkRouteFrameSent(NwkFrame_t *frame)
{
NWK_RouteTableEntry_t *entry;

if (NWK_BROADCAST_ADDR == frame->header.nwkDstAddr) {
return;
}

entry = NWK_RouteFindEntry(frame->header.nwkDstAddr,
frame->header.nwkFcf.multicast);

if (NULL == entry || entry->fixed) {
return;
}

if (NWK_SUCCESS_STATUS == frame->tx.status) {
entry->score = g_nwkRouteDefaultScore;

if (NWK_ROUTE_MAX_RANK == ++entry->rank) {
nwkRouteNormalizeRanks();
}
} else if (NWK_PHY_CHANNEL_ACCESS_FAILURE_STATUS != frame->tx.status) {
        if (0 == --entry->score) {
NWK_RouteFreeEntry(entry);
}
}
}



• During the tests perfomed, I have implemented the OTA feature in a way in which when a node needs to download a new firmware it adopted the OTA client rol in which it requests blocks of the file to an OTA server node until the download finishes and, once complete, it switches to OTA server rol and sends the image to each of the neighboring nodes.
  To achieve this process, I use the properties provided by the stack to send "Link Local" messages and receive a "Network ACK" each time a message is received by the destination node.
  Link Local functionality works great, in the sense that the messages are not routed by neighboring nodes that are not the recipient of the message, but not the network ACK returned by the destination node of the message.
  
  I have noticed that even when the received message is indicated as"linkLocal", if the destination node of the message does not have the sender address inside its routing table, the "Network ACK" message fires a route discovery process. Is this intentionally left this way?
  
  To avoid the discovery process I have modify the function:
  

Code: [Select]

static void nwkRxSendAck(NwkFrame_t *frame)
by adding the condition:

Code: [Select]


if(frame->header.nwkFcf.linkLocal)
ack->tx.control = NWK_TX_CONTROL_DIRECT_LINK;

in the following way:

Code: [Select]


static void nwkRxSendAck(NwkFrame_t *frame)
{
NwkFrame_t *ack;
NwkCommandAck_t *command;

if (NULL == (ack = nwkFrameAlloc())) {
return;
}

nwkFrameCommandInit(ack);

ack->size += sizeof(NwkCommandAck_t);
ack->tx.confirm = NULL;

if(frame->header.nwkFcf.linkLocal)
ack->tx.control = NWK_TX_CONTROL_DIRECT_LINK;

ack->header.nwkFcf.security = frame->header.nwkFcf.security;
ack->header.nwkDstAddr = frame->header.nwkSrcAddr;

command = (NwkCommandAck_t *)ack->payload;
command->id = NWK_COMMAND_ACK;
command->control = nwkRxAckControl;
command->seq = frame->header.nwkSeq;

nwkTxFrame(ack);
}



• With regard to the possibility of the stack to set static entries in the routing table so that they can't be removed even if the destination node is no longer reachable, I have notice that in fact those entries are not affected by the score and are never deleted even when the command NWK_COMMAND_ROUTE_ERROR is received.
  However, when the node that has a static input is part of the process of discovering a route that is initiated by another neighbor node, upon receiving the command NWK_COMMAND_ROUTE_REPLY, it replaces (I think that involuntarily) the entry in the routing table, even though it is fixed. Is this intentionally done this way?
  
  To avoid this situation, I have modify the implementation of the function:
  

Code: [Select]

void nwkRouteUpdateEntry(uint16_t dst, uint8_t multicast, uint16_t nextHop, uint8_t lqi)
by adding the condition:

Code: [Select]

if (entry && entry->fixed) {
return;
}

in the next way:

Code: [Select]

void nwkRouteUpdateEntry(uint16_t dst, uint8_t multicast, uint16_t nextHop, uint8_t lqi)
{
NWK_RouteTableEntry_t *entry;

entry = NWK_RouteFindEntry(dst, multicast);

if (entry && entry->fixed) {
return;
} else if (NULL == entry) {
entry = NWK_RouteNewEntry();
}

entry->dstAddr = dst;
entry->nextHopAddr = nextHop;
entry->multicast = multicast;
entry->score = g_nwkRouteDefaultScore;
entry->rank = NWK_ROUTE_DEFAULT_RANK;
entry->lqi = lqi;
}



Thanks in advance for giving me support.

[ataradov]

First of all, I want to mention that being a hackable base for custom stacks was always the goal of LwMesh. I basically made it as a tool to help me supporting people with a need for a proprietary stack.

1. Loops are not possible with AODV, since they form after the discovery is done, and AODV does not optimize the routes. This is just a leftover, since AODV was added later.
2. The goal was to be overzealous with route removal. Just in case. If you want to further improve overall behavior on long routes, it would be beneficial to implement stack-level retries on each hop, and not just give up on a first try.
3. This ack behavior was not intentional. Depending on the circumstances, a better solution  may be to add unknown local devices to the routing table. This is a passive collection of information that later may save time doing active discovery.
4. Static routes should never be replaced, it is a bug.


I have a ton more ideas for what would have been LwMesh v2, but unfortunately I was never given time, and all development is pretty much stopped.

I was thinking about making a free alternative (that's why I made NetSim), but given how this industry progresses, that's a waste of time, and having to deal with FCC is a huge turn down.