The approach taken in olsrd

OLSR is not designed to route huge networks. So the tables in OLSR will hold a relatively small amount of entries. A MANET consisting of more than 500 nodes is not very likely to be routed as one OLSR domain, so as the tables in olsrd usually registers at maximum one entry per node, some sort of hashing scheme based on the identifier of nodes will pay off here.

Olsrd uses a hash based on the main IP address of a node to index the node in a statically allocated array. Every element in this array is the root element in a double-linked list. The structure is illustrated in fig. 6.7. The elements in the lists are not ordered and the size if the hash-array is set by the constant HASHSIZE defined in src/hashing.h. This size must be as big as the largest possible hash derived from an IP address using the hash function olsr_hashing also defined in src/hashing.h.

Figure: The olsrd generic data index. A static list of indexes that is used for hashing, where each entry is the root element in a double-linked list.

The hashing function is currently very trivial. In IP addresses, the lower bits are expected to be the most unique part. This is definitely the case if, for example, most IP addresses in a dataset are part of the same subnet. Therefore, when creating hashes from IP addresses, it is natural to utilize the lower bits of the address. The hash generated for an IP address in olsrd is simply the lower 5 bits of the address. This gives a hash list-size of 32. This value can easily be updated to be more suitable for larger amounts of data.

Using statically allocated root elements makes traversing and inserting elements easier, as one never has to check for empty lists. No data is ever stored in the root elements, they are only used as references to the start, and the end, of the list. To lookup an element, given an IP address, the following steps must me taken:

1. Find the hash of the IP address:

   hash = olsr_hashing(IP)

2. Traverse the list from the root element at index = hash in the table:

   for(element = table[hash]->next; 
       element != &table[hash]; 
       element = element->next)
   

3. Check for a match:

   if(element->IP == IP)

To insert an element the following steps are required:

1. Set the new elements next pointer to be the root elements next element:

   new_element->next = root.next

2. Set the root elements next elements previous pointer to be the new element:

   root.next->prev = new_element

3. Set the root elements next pointer to be the new element:

   root.next = new_element

4. Set the new elements previous pointer to be the root element:

   new_element->prev = &root

These four steps are available through the macro QUEUE_ELEMENT defined in src/olsr.h.

Removing an element is very easy and requires no knowledge about anything but the element to be removed:

1. Set the previous elements next pointer to be this elements next pointer:

   entry_to_delete->prev->next = entry_to_delete->next

2. Set the next elements previous pointer to be this elements previous pointer:

   entry_to_delete->next->prev = entry_to_delete->prev

3. The entry is now dequeued and can be deleted:

   delete(entry_to_delete)

The removal operation is available through the DEQUEUE_ELEMENT macro defined in src/olsr.h.

As seen in these examples, the use of statically allocated root elements prevents the situation where a list goes empty. Due to this, one never has to check for empty pointers or pointers to oneself when removing elements.