notes.splitbrain.org

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Prophet Address Allocation ======

Prophet ((Hongbo Zhou, Lionel M. Ni, and Matt W. Mutka, "Prophet Address Allocation for Large Scale MANETs", Ad Hoc Networks Journal, Vol. 1, Issue 4, pp 423-434, November 2003 [[http://www.cse.msu.edu/~zhouhon1/doc/science.pdf|pdf]])) is an collision avoidance algorithm for automatic IP assignments in [[MANET]]s and was proposed by [[http://www.cse.msu.edu/~zhouhon1/|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 [[http://www.cse.msu.edu/~zhouhon1/doc/science.pdf|proposal]].


===== Implementation =====

I did a prototype implementation for my thesis. You can {{manet:prophet.tgz|download the code}}.

You need [[http://www.tcpdump.org/|libpcap]] and [[http://www.packetfactory.net/projects/libnet/|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!


==== Communication ====

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)://

^  Harwaretype                   ^^  Protocoltype  ^
^  HW Addrlen.  ^  Prot. Addrlen  ^  Opcode        ^
^  Sender HW Address                             ^^^
^  Sender HW Addr. ^^  Sender IP Addr              ^
^  Sender IP Addr. ^^  Receiver HW Addr            ^
^  Receiver HW Address                           ^^^
^  Receiver IP Address                           ^^^
|  Network ID (4 Byte)                           |||
|  State index (4 Byte)                          |||
|  State (32 Byte)                               |||

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


==== Address Calculation ====

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:

<code c>
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]++;
</code>