Skip to content
 

Shortest Path First Routing: Djikstras Algorithm in C

Background

I took over a project consisting of PIC chips interfacing with basic 802.15.4 radio modules.  These modules had no routing or mesh networking abilities.  The only feature was the ability to send and receive to other modules that were within range.  When I first received the project the routing method was that every packet was broadcast to every other node, which in turn broadcast it to every other node, and so on.   There was a max hop count in the packet to limit resends.  This worked fine with a few modules but as the network grew the packet traffic went up almost exponentially.  After researching routing methods I decided on link-state SPF routing based on Djikstra’s algorithm.

Djikstra’s algorithm requires every node to maintain an entire ‘map’ of the network that consists of a list of every node and who those nodes can see.  This was implemented by having each node ping out, maintain a list of nodes it could see, and distributing this information every couple of minutes automatically or whenever a change was detected.  This method combined with Djikstra’s algorithm created a self-healing mesh network with efficient shortest-path routing.

The details on Djikstra’s algorithm are beyond the scope of this article.  The code is based off the pseudo code described on the wiki page.

Implementation

The one downside to link-state routing vs vector based is RAM usage goes up exponentially based on the size of the network.  I only had a couple KB of ram to work with and the required network size just happened to fit in the RAM.

In my implementation I was able to cram an entire link-state record into 2 bytes.  There were 6 bits for the module address, 2 bits for the role (multiple device roles), 6 bits for the age, and 2 bits for the distance metric.  Distance was mapped down to 2 bits as values 0-3 (treated as 1-4) based on the radio connection quality metric 0-255.

With a 2 byte link-state the RAM required is:

max-devices == n (( n * 2)+5) * n = bytes
max-devices == 10 ((10 * 2)+5) * 10 = 250 bytes
max-devices == 20 ((20 * 2)+5) * 20 = 900 bytes
max-devices == 40 ((40 * 2)+5) * 40 = 3400 bytes

In the example code below I have given each value its own variable for ease of reading the code which greatly expands the RAM usage.  This implementation only concerns itself with keeping an up to date list of the first hop address for every node on the network.

Link-state and Routing table entries:

#define MAX_DEVICES_ON_NETWORK 24

typedef struct _LINKSTATE_ENTRY
{
  int8 destAddr;
  int8 distanceMetric;
  int8 role; //for routing, not djikstra
  int8 age; //for routing, not djikstra
} LinkstateEntry;

typedef struct _ROUTING_ENTRY
{
  unsigned int8 devAddr; // address of the device
  unsigned int8 firstHop; // address of first hop
  unsigned int8 ageSeconds; //seconds since update
  unsigned int8 sequence; //last sequence number
  unsigned int8 visited; //for djikstra's algorithm
  unsigned int8 pathLength; //for djikstra's algorithm
  unsigned int8 prevNode; //djikstra
  unsigned int8 neighborCount; //number of linkstates for this node entry

  //list of reachable nodes
  LinkstateEntry linkStates[MAX_DEVICES_ON_NETWORK-1];
} RoutingEntry;

RoutingEntry routeIndex[MAX_DEVICES_ON_NETWORK-1];//local routing table
LinkstateEntry personalLinkstate[MAX_DEVICES_ON_NETWORK-1];//local node linkstate that gets distributed to everyone
unsigned int8 neighborCount = 0; // number of neighbors in local link state

Any time the link-state table for a node is updated, Djikstra’s algorithm is run to determine the first hop for all nodes. This implementation is not concerned with the path, just the first address on that path. This is a bit complicated. The first function below sets everything up. It calculates all the path lengths to each node, then for each node on the network calculates the first hop address. Whenever a device receives a packet with a delivery address other than itself, it merely references the routing table to see the first hop address for the destination and passes it on.  The routing table entry index value (routeIndex[x]) directly corresponds to a node radio address.

void Djikstra_Recalculate_Routes()
{
  int8 x;

  Djikstra_Recalculate(); //calculate all path lengths

  for( x = 0; x < MAX_DEVICES_ON_NETWORK-1; x++ )
  {
    if( routeIndex[x].devAddr ) //if device is in table
      FindFirstHop( routeIndex[x].devAddr );//find first hop for routing
  }
}

void Djikstra_Recalculate(  ) {
  unsigned int8 x;
  unsigned int8 addr;
  unsigned int8 tempAddr;
  unsigned int8 alt;
  unsigned int8 neighborAddr;

  for( x = 0; x < MAX_DEVICES_ON_NETWORK-1; x++ ) {
    if( routeIndex[x].devAddr != 0) // if device is in routing table
    {
      routeIndex[x].visited = 0; //mark as unvisited by the algorithm
      routeIndex[x].pathLength = 255; //mark path as infinite
      routeIndex[x].prevNode = 0;
    }
  }

  //reset all
  for( x = 0; x < neighborCount; x++ ) {
    addr = personalLinkstate[x].destAddr;

    if( !routeIndex[addr-1].devAddr ) //if we don't have a routing entry yet
      continue;

    routeIndex[addr-1].pathLength = personalLinkstate[x].distanceMetric;
    routeIndex[addr-1].prevNode = GetMyAddress();
  }
  tempAddr = Djikstra_GetShortestUnvisited();

  while( tempAddr ) {
    routeIndex[tempAddr-1].visited = 1;
    alt = routeIndex[tempAddr-1].pathLength;

    for( x = 0; x < routeIndex[tempAddr-1].neighborCount; x++ ) {
      if( NotInRoutingTable( routeIndex[tempAddr-1].linkStates[x].destAddr ))
        continue;
      neighborAddr = (routeIndex[tempAddr-1].linkStates[x].destAddr);
      if( (alt + (routeIndex[tempAddr-1].linkStates[x].distanceMetric)) < routeIndex[neighborAddr-1].pathLength )
      {
        routeIndex[neighborAddr-1].pathLength = alt + (routeIndex[tempAddr-1].linkStates[x].distanceMetric);
        routeIndex[neighborAddr-1].prevNode = tempAddr;
      }
    }
    tempAddr = Djikstra_GetShortestUnvisited();
  }
}

int8 Djikstra_GetShortestUnvisited() {
  int8 x;
  int8 curShortest = 255;
  int8 curShortestAddr;

  for( x=0; x < MAX_DEVICES_ON_NETWORK-1; x++) {
    if( ! routeIndex[x].devAddr )
      continue;

    if( !routeIndex[x].visited && routeIndex[x].pathLength
        && routeIndex[x].pathLength < curShortest ){
      curShortest = routeIndex[x].pathLength;
      curShortestAddr = routeIndex[x].devAddr;
    }
  }

  if( curShortest == 255 )
    return 0;
  else
    return curShortestAddr;
}

void FindFirstHop( int addr ) {
  unsigned int8 prevNode;
  unsigned int8 prev;

  prevNode = routeIndex[addr-1].prevNode;

  if( prevNode == GetMyAddress() ) {
    routeIndex[addr-1].firstHop = addr;
    return;
  }

  while( prevNode ) {
    prev = routeIndex[prevNode-1].prevNode;

    if( prev == GetMyAddress() ) {
      routeIndex[addr-1].firstHop = prevNode;
      break;
    }
    prevNode = prev;
  }
}

Conclusion

This is custom implementation of Djiktra’s algorithm actually in use for a packet routing system in a network of up to 24 devices.  The performance has been very good and I believe it could easily scale up to over a hundred devices (given enough RAM) on the 16MHz PICs.  The actual routing implementation includes a hop count field to limit the effect of a loop.  A loop could form if a device is removed from the network and the entire network is not in sync or if there was a radio signal strength anomaly.  There are probably better ways to handle that but our requirements have addition/removal of devices being rare.

Leave a Reply