[olsr-dev] Re: auto ip address assignment

(spam-protected) (spam-protected)
Sat Apr 22 18:57:12 CEST 2006

Self-configuring networks

PS: see what-a-mesh firmware of rop in amsterdam an Paris, which has already
auto configure...e

“Adapt or perish, now as ever, is nature’s inexorable
– H. G. Wells (1866 - 1946)

Mobile ad-hoc networks should be self-configuring. 
This means that nodes who are to participate in a
MANET should not need extensive knowledge of network parameters prior to
joining the network. This
should include automatic configuration of IP addresses. Although IP address
auto-configuration is not explicitly
mentioned in RFC2501, many ad-hoc networks would benefit from some generic
auto configuration
scheme. Not only to provide automatic IP address allocation, but also to
detect more basic abilities of the
MANET such as the routing protocol utilized.
In this chapter a proposed IP auto-configuration protocol for use in MANETs
using a pro-active routing
protocol, is presented. An implementation of the protocol has been made for
olsrd. The protocol itself is to
be released as an Internet draft.
12.1 Background
Any node in an IP network needs a valid IP address to be able to participate
in routing and regular data
communication. It is the IP address that uniquely identifies the node as an
endpoint in network communication.
There are several ways to acquire an IP address. For wired networks, the two
most common ways are
either static configuration, or by the use of the Dynamic Host Configuration
Protocol(DHCP)[30]. A static
configuration can simply be that the node has been given a valid address by
a system administrator and will
always use this address. For a network with many nodes, this is not
scalable. The DHCP framework is
based upon a client-server model. This architecture leads to a single point
of failure. If the DHCP server is
out of reach the service is not available. DHCP clients also uses broadcasts
to emit requests. For a MANET,
both these factors are troublesome. MANETs should favor distributed
operation as opposed to centralized
designs as those used in DHCP. Broadcasting in a MANET will not reach all
nodes in the network unless
special broadcast extensions or other mechanisms are used. So DHCP is not a
well suited solution for IP
address auto configuration in MANETS.
12.2 Duplicate address detection
The work [49] is the most recent work in the subject of auto-configuration
in MANETs. This work describes
a mechanism for Duplicate Address Detection (DAD), but does not specify how
to acquire an IP address in
the first place. In [49] DAD is divided into strong DAD and weak DAD.

When a new node enters a MANET, it uses Strong DAD to check if its chosen
address is already in use.
This means that some sort of request message must be flooded throughout the
MANET. If a node is already
using, or possibly know of a node using, the requested IP address, then a
response message is sent back to
the originator of the request. This response message states that there is an
address conflict.
Weak DADs purpose is to detect address duplication during MANET routing.
Some mechanism must be
present to dynamically detect the existence of duplicate IP addresses used
in the network. This mechanism
could also be used to detect merging of networks. A network merge detection
should cause some special
action to be taken as there might be lots of address duplicates.
12.3 Pro-Active Auto-config
Pro-Active Auto-config(PAA) is a proposed IP address allocation protocol
including strong DAD, for use
in MANETs. The protocol can be used with both IPv4 and IPv6. PAA takes
advantage of the fact that
nodes that are already members of a MANET domain, running a pro-active
routing protocol, already has
a relatively complete understanding of the topology. Such nodes are
therefore well suited to allocate an IP
address that is probably currently not used by any nodes in the network. PAA
also does strong DAD to
ensure that no other node is currently configured, or in the process of
configuring itself, with a duplicate
address. This is done by flooding the network using the underlying routing
PAA provides a node with the ability to automatically configure itself with
an unique address and join
a MANET. This configuration takes place without the node having any prior
knowledge of the network
12.3.1 Basic operation
As outlined in figure 12.1, PAA consists of three software components. An
unconfigured node runs the
PAA-client to allocate an unused IP address. The PAA-client communicates
with one (or more) PAAservers
running on already configured nodes. These servers communicate with the
routing daemons running
on their local hosts. All communication between PAA-clients and PAA-servers
is done using the link-local
address space when using IPv4 and fe80:: when using IPv6. DAD
flooding is done using
the flooding mechanism offered by the routing protocol in addition to
link-local traffic.
PAA packets uses the 64-bit header illustrated in figure 12.2, and all
traffic is carried using UDP.

Two main approaches can be taken when requesting an IP address from nodes in
a MANET. They are here
referred to as the proxy solution and the broadcast solution.
If using the proxy solution, the unconfigured node elects one configured
node that operates on behalf of it
for the entire configuration session. In PAA this can be done, but the
implementation on which this chapter
is based, uses another approach. The main idea in the implementation of PAA,
is that an unconfigured node
is to be able be mobile while doing configuration. Because of this no proxy
is used for configuration.
A node communicates with any configured nodes that are in communication
range. Data is broadcasted
from the unconfigured node and back from configured nodes. Because of this,
this approach is called
the broadcast solution. No state is kept in the configured nodes regarding
configuration sessions. An
unconfigured node can be mobile and use different configured nodes for
different parts of the configuration
Both approaches have their pros and cons. The broadcast solution gives the
advantage of mobility, but the
proxy approach could provide a more robust DAD. If using a proxy, address
conflict messages in strong
DAD, can be unicasted back to the proxy node. When using the broadcast
solution all such traffic is
flooded throughout the MANET. Some specific scenarios where a node loses
connectivity and does not
receive conflicting messages could also be avoided when using the proxy
solution, but new such problematic
scenarios could be generated for the proxy solution as well.
An example of a configuration session
Figure 12.8 illustrates a configuration session where a new node joins the
MANET. In this example, no
address conflicts are detected. If using IPv4 the unconfigured host
configures itself with a random linklocal
address, if using IPv6 the link-local address automatically assigned to the
used interface is used. The
PAA-client then broadcasts(IPv4) or multicasts(IPv6) an Address
Request(figure 12.4). Since the IPv4 linklocal
address is generated using random numbers, conflicts can occur. Because of
this, an identifier that the
PAA-client generates based on the interfaces MAC address, is used for host
identification. This identifier is
also used when using IPv6, since all return traffic is also multicasted back
to the client from the server.
The Address Request message might contain a preferred address that the
unconfigured host wishes to use

if available. When using IPv4 this is a regular IP address, when using IPv6
this is the MAC address of the
interface on which PAA is running. Note that an IPv6 Address Request still
contains a 128 bits preferred
address field to allow for possible future changes and to maintain a
consistent IPv4/IPv6 packet design. A
PAA-server receiving this request forwards it to the PAA-plugin. When using
IPv4 the PAA-plugin checks
if the preferred IP address is available, if the address is not available or
if no preferred address was received,
it acquires a random available address. An available address is defined as
an IP address that the configured
node has not heard mentioned in any OLSR control traffic for a given time.
If using IPv6, the client has to
submit its MAC address in the request message. The server then forwards the
request to the PAA-plugin that
generates an address based on the MAC. The address is made up of a prefix
from some predefined net-range
and the MAC address. This address is then checked against the IP cache pool.
If a conflict is discovered
multiple “backup” net-ranges could be used to create an address
based on the MAC. The allocated address
is then sent back to the requesting host in an Address response
message(figure 12.5).
The requester is now to perform strong DAD. This is done by broadcasting or
multicasting a Address Test
message (figure 12.6) link-local. All PAA-servers receiving this message is
to flood it through the MANET
using MPR flooding. This is done by encapsulating the message in an OLSR
message and sending it as a
regular OLSR message. The PAA-server must confirm that it has received the
message from the requester
by replying with a Test Confirm message. If a requester does not receive
such a confirmation message,
the emitted Address Test is not considered flooded and another Address Test
message is broadcasted or
multicasted immediately.
An OLSR daemon extended with a PAA-plugin that receives an Address Test
message, is to forward this
link-local if the node has received a Forward Request (figure 12.3) within a
given time interval. Any node
in the process of configuration, broadcasts or multicasts such forward
request messages regularly. This is to
make sure configured nodes within transmission range of any unconfigured
host will forward all received
Address Test messages link-local.
If a node in the process of configuration, receives an Address Test
originating from another unconfigured
node and this message contains the address the local node has been offered,
it is considered an address
conflict. This is because some other node (the sender of the Address Test
message) is in the process
of configuring itself with the same address the local node was offered. The
node will then restart the
configuration process by sending a new Address Request.

12.4 Implementation
The Pro-Active Auto-configuration solution is implemented for use with
olsrd. Parts of the protocol is
currently patent pending [14] by Thales Communications AS, and therefore the
source code is not publicly
available as of yet.
In the following sections we will look into the PAA server, PAA client and
the olsrd plugin in detail.
12.4.1 PAA client
When an unconfigured node starts the PAA service, it is started in client
mode. A flow diagram describing
the IPv4 PAA-client operation is illustrated in figure 12.9. The first thing
the IPv4 client does, is to generate
a random link-local address. It will then configure an “alias”
interface with this address. Such alias
interfaces is the way one can configure an interface with multiple IPv4
addresses on GNU/Linux systems.
If PAA is set to run on eth0, the alias interface will be eth0:0. This
interface will be used by both the PAAclient
and later the PAA-server. Due to the binding of sockets to devices as
explained in section 6.2.3, olsrd
cannot run on alias interfaces. Therefore the PAA-client/server uses an
alias interface leaving the “real”
interface to olsrd. The IPv6 client uses the link-local address
automatically assigned to the interface PAA
uses. IPv6 allows for several IP addresses to be set for the same interface,
so there is no need to set up an
alias interface.
The PAA-client must periodically broadcast or multicast a Forward Request
message link-local to let already
configured neighbors know that they should forward all received PAA control
messages link-local.
In the implementation this message generation is done in a thread of its own
emitting a Forward Request
every 2 seconds.
The client must generate an identifier that it will use to identify itself
in PAA traffic since link-local address
conflicts might occur. In the implementation, this ID is the lower 32-bits
of theMAC address of the interface
on which PAA runs. This diminishes the uniqueness of the ID, but the chance
of two WLAN interfaces
using the same last 32-bits in their MAC addresses is relatively small. The
first six bytes of the MAC
address are the “Organizational Unique Identifier”, while the
lower six bytes are the actual factory serial
number. One can however still risk an ID crash if two interfaces by
different makes that share the last 4
bytes in their Organizational ID, with the same serial number were to meet.
But in general, there is a much
smaller chance for this happening than the upper 32-bits matching, which in
many cases only would require
having two interfaces bought from the same stock.
To receive a free IP address, an Address Request message is broadcasted or
multicasted link-local. A node
signs this request with its ID. Any neighbor that is already a configured
member of the MANET routing
domain and out of quarantine time, as explained later, will answer with an
offered address if an address
could be allocated. If no replies are received, the PAA-client can
optionally configure its interface with
a random address within a pre-defined address space and start the routing
daemon, thus starting its own
Upon receiving the first Address Response carrying the correct ID, the
requester will generate an Address
Test message and broadcast or multicast it link-local to all neighbors. Any
other Address Response message
received for the same request is silently discarded. Any configured node
that receives the Address Test
message, sends an Address Test Response confirmation message so that the
PAA-client can be sure that the
test-message is flooded. If no Address Test Response is received by the
PAA-client, a new Address Test is
sent. This is repeated until at least one Address Test Response is received.
The PAA-client then waits for a given interval to receive a possibly
conflicting Address Test message sent
by other nodes. If this interval times out without any conflicting Address
Test messages received, another
Address Test message is broadcasted or multicasted. If another time interval
passes without the node
receiving any conflicting Address Test messages the address is considered
valid and DAD is considered
complete. If a conflicting message is received, the configuration process is
When a unique IP is allocated the PAA-client will configure the interface to
use with the address and
Forward Request messages will no longer be sent. The thread generating these
is terminated. When the

interface is configured, olsrd is started. The PAA-client must take care to
ensure that the routing daemon
will run on the correct interface. PAA is also responsible for terminating
the routing-protocol process when
it is terminated itself. When the routing-daemon is started, the PAA-client
will put itself in server mode.
12.4.2 PAA server
The basic operations of the PAA-server is illustrated in figure 12.10.
The first thing PAA does when going from client- to server-mode is to
connect to the routing-daemon via a
TCP socket to the loopback device 

Echte DSL-Flatrate dauerhaft für 0,- Euro*!
"Feel free" mit GMX DSL! http://www.gmx.net/de/go/dsl

More information about the Olsr-dev mailing list