Prophet ¹⁾ is an collision avoidance algorithm for automatic IP assignments in MANETs and was proposed by Hongbo Zhou.

Prophet tries to avoid duplicate addresses by using a stateful function, which should create a large row of unique numbers starting from a single seed. For a detailed look on how it works have a look at the original proposal.

I did a prototype implementation for my thesis. You can download the code.

You need libpcap and libnet to compile the code. Some parts are linux specific and have to be changed when used on other platforms. This implementation does create a Network ID but does not periodically exchange it, so network merges are not detected!

To exchange information between clients before any IP addresses are available, my implementation uses modified ARP packages to send Prophet requests and replies. Prophet replies use an additional payload to transfer the state and the network ID.

example ARP package (blue) with additional Payload (white):

In difference to usual ARP packages this implementation uses different Opcodes. Prophet Requests use an Opcode of 55 and Replies use 56.

The implementation uses a prime factorization as suggested in the original proposal. The function is newip = ((ip + p1^s1 + p2^s2 + … + p8^s8) mod range) + 1. p1 to p8 are eight predefined prime numbers, s1 to s8 are the current state of the function (using an integer array with 8 fields) and range is the used address range: 16777215 for 10.0.0.0/8.

Here is the part of address calculation in the C code:

u_long ip;        // this is my address
u_long address=1; // holds the new address
int i = 0;
 
ip = libnet_get_ipaddr4(_libnet);
 
//calc new address
for(i=0; i<K; i++){
  address *= _prime[i]^_prophet.state[i];
  address %= RANGE;
}
address += ip;
address %= RANGE;
address += 1;
address += BASENET;
address  = ntohl(address); //convert byte order
 
//increase state at index_pos
_prophet.state[_prophet.index]++;