It Network
Resume:
Random and Linear Address Allocation
for Mobile Ad Hoc Networks
Nakjung Choi, C.K. Toh, Yongho Seok, Dongkyun Kim and Yanghee Choi
School
of Computer Science and Engineering
Seoul National University, Seoul, Korea
Email: {fomula, yhseok, yhchoi}@mmlab.snu.ac.kr
Communication
Networks
Queen Mary University of London, London, UK
Email: **.****@******.***
Department
of Computer Engineering
Kyungpook National University, Daegu, Korea
Email: ********@***.**.**
In the current Internet, IP address con guration mechanisms
Abstract To join an IP network and communicate with
others, a node needs to be con gured either manually by an can generally be divided into two general categories: (a) glob-
administrator or automatically through a DHCP server. However, ally unique IP addressing and (b) local IP addressing. In the
the former method is impractical for large networks, while the
former case, every host is assigned a unique IP address, which
latter is infeasible in the case of a mobile ad hoc network due to
is valid network-wide. In the latter case, however, isolation
the mobility of the nodes. This paper introduces two distributed
is introduced, because addresses are of local signi cance only.
IP address auto-con guration mechanisms for mobile ad hoc
networks, namely (a) RADA (Random Address Allocation) and Mapping of the local address in the mobile ad hoc subnetwork
(b) LiA (Linear Allocation). RADA is based on random IP address to a global address then becomes necessary, in order to provide
selection, while LiA linearly assigns new addresses by utilizing
interoperability with the Internet. Table I lists the pros and cons
the current maximum IP address value. We have also introduced
of each of the above two methods.
an improved version of LiA, known as LiACR (Linear Allocation
with Collision Resolution), which reduces control overhead. Then,
we discuss extensions of these mechanisms capable of handling TABLE I
network partitioning and merging. Performance evaluations of
G LOBAL /L OCAL IP A DDRESS A SSIGNMENTS P ROS /C ONS
RADA, LiA and LiACR were conducted through simulation. The
PROS CONS
results related to address allocation time and control overhead
Simple to implement No IP address reuse
are presented and compared.
Globally (scalability)
Index Terms IP Address Auto-Con guration; Ad Hoc Ad-
Unique Little/no con icts Requires coordination of
dress Acquisition; Address Con icts; Resolution Schemes.
Addressing of addresses IP address assignment
among
I. I NTRODUCTION ad hoc sub-networks
Scalable Complext to implement
A mobile ad hoc network (MANET) [1] is a set of wireless No coordination of Needs NAT-like
mobile nodes forming a dynamic autonomous network with IP address assignment functionality for
no infrastructure. Nodes communicate with each other in a Local IP among private/public address
Addressing ad hoc sub-networks translation in gateway
multi-hop fashion, without the intervention of any centralized
Addresses reuse
access points or base stations.
among
So far, research in this area has focused primarily on the ad hoc sub-networks
issue of ad hoc routing. For example, the specialized routing
protocols, DSR, ABR, AODV, and TORA were proposed
for mobile ad hoc networks, because existing wired routing In general, new addresses can be either pre-con gured,
protocols do not function well in an environment which has dynamically assigned using DHCP or dynamically assigned
a dynamically changing topology. Also, most ad hoc routing using auto-con guration methods. In this paper, we introduce
protocols still continue to use IP addressing. two new methods of auto-con guring IP addresses in a mo-
bile ad hoc sub-network. Our paper is organized as follows.
This work was supported in part by the Brain Korea 21 project of Ministry
Section II introduces current standardization works related to
of Education and in part by the National Research Laboratory project of
IP address auto-con guration. In section III, we describe our
Ministry of Science and Technology, 2005, Korea.
proposed methods, namely (a) RADA, (b) LiA, and (c) LiACR. chooses its agent among the address-con gured nodes in the
The performance evaluation of these methods via simulation is network, and its agent requests address allocation for all the
presented in section IV. We then conclude this work in section nodes in the network. After all agreements, its local IP address
V. is allocated to the node. However, address allocation time
may become longer depending on the number of the failures
II. R ELATED W ORK till getting all agreements and ACK implosion may occur.
The goal of the IETF Zero Con guration Networking (Zero- [8] suggested the address collision-free allocation scheme,
conf ) Working Group is to make networking possible in places Prophet Address Allocation, which utilized the function gen-
where manual con guration and administration is impractical erating disjoint integer sequences. Although Prophet is able
or impossible. The mandate of Zeroconf includes issues such to reduce address allocation time, it is very dif cult to devise
as interface con guration, name-to-address translation, service such a function satisfying the mathematical constraints in the
discovery, automatic allocation of multicast address and secu- distributed environment. Besides, the probability of address
rity. con ict is not zero because the number of IP addresses is not
Automatic con guration of IP hosts [2] includes IP interface in nity. Therefore, the assistance such as duplicate address
con guration. IP interface con guration is a very important detection is needed to avoid address con ict.
function, since it enables packet ow in a communication
III. A D H OC IP A DDRESSES AUTO -C ONFIGURATION
node. An IP interface con guration protocol must possess the
following characteristics:
We propose two methods which allow for ad hoc IP address
Be capable of discovering whether an IP address is
auto-con guration. The main difference between these two
currently in use. methods concerns the process of candidate IP address selection
Resolve IP address con icts in a timely manner and on
and con rmation. Since there is no automatic or global infor-
an ongoing basis. mation exchange mechanism in a mobile ad hoc network, the
Allocate addresses in a way that minimizes the probabil-
use of either broadcasting or scope- ooding cannot be avoided.
ity of con icts arising. This is the price which has to be paid when auto-con guration
Note that an IP address auto-con guration mechanism in a is used.
mobile ad hoc sub-network must also possess these features.
In IPv6, Stateless Address Autocon guration [3] describes A. Proposed Random Address Allocation (RADA) Method
a mechanism that allows a node to generate a link-local
1) RADA Principle of Operation: When a mobile host is
IP address automatically. In IPv4, the dynamic con guration
powered on, it rst randomly picks an IP address in the range
of link-local IPv4 addresses [4] describes how a node may
First PERM ADDR 65,355 from its pre-con gured subnet.
automatically con gure an interface by giving it an address
The host then tries to use this IP address as its local IP address
within the 169.254/161 pre x that is valid for communication
(i.e., its permanent IP address). In order to do so, it randomly
with other devices connected to the same physical or logical
picks another IP address in the range 1 (First PERM ADDR-
link. Address collision detection is also supported in this
1) from its pre-con gured subnet. This temporary IP address
mechanism. Upon receiving a con icting ARP packet, a node
is then used by the node to process and acquire the permanent
may elect to immediately assign itself a new link-local IPv4
address that it preciously picked. Once the address request
address. This speci cation is intended for use with small
process is nished, the temporary IP address is released.
fully-connected ad hoc networks consisting of a single link
Initially, a host needs to broadcast an Address Query (AQ)
containing only a few nodes. While these link-local addressing
packet to the subnet. The format of the AQ packet is shown
proposals are only suitable for use in single-hop networks,
in Fig. 1. The AGE eld is initially set to zero. The host also
they are not directly applicable to multi-hop mobile ad hoc
sets an AQ-timeout timer and awaits for any Address Reply
networks. Herein lies the motivation for our work.
(AR) packets.
Recently, several address auto-con guration mechanisms in
mobile ad hoc networks have been proposed. In [5] and [6], TYPE (AQ) AGE
a server node manages address list in the network and has Originator s Temporary IP Address
an authority for address allocation in spite of different server Requested IP Address
names. These schemes are easy to resolve address con icts
Fig. 1. AQ Packet Format
in the case of network merging because a server node has
all information of ip addresses used in the network. However,
When a host receives an AQ packet, it rst checks its AQ
if many nodes frequently move into or out the network, a
Seen Table, to see if the packet has been processed before.
server node may be overloaded and down, resulting in the
If it has already seen this AQ, it discards the AQ packet. If
network failure. [7] proposed an agent-based address auto-
not, it inserts the AQ in its AQ Seen Table. Each entry in
con guration protocol, MANETconf, which utilized the dis-
the AQ Seen Table should be given an associated time-to-live
tributed agreement concept. A new node joining the network
attribute, which identi es the new AQ packet. The host then
1 The checks if its own address matches that in the AQ packet. If so,
IPv4 pre x 169.254/16 is registered with the IANA for this purpose.
it then compares the AQ AGE value with its own IP Address Address Timer in order to increment its AGE counter. For a
Timer. This yields three possible cases: 24-bit AGE eld, it is capable of counting up to 4,660 hours.
RADA cannot guarantee address uniqueness without the
If the host s non-zero timer is greater than the AQ
presence of Address Con ict Resolution Protocol (ACRP).
packet s AGE eld, it keeps its IP address and sends an
ACRP periodically broadcasts AQ packets to check for po-
Address Reply (AR) to ask the AQ originator to drop its
tential address con icts. An ACRP timer is set up so that a
request.
host broadcasts an AQ every ACRP period. The AQ which is
If the host s timer is less than the AGE of the AQ packet,
broadcasted contains the host s IP address and address timer
it drops its own IP address and initiates an AQ for a new
value (AGE eld). Checks on these elds help to identify
IP address.
con icts.
2
If the host s timer and the AGE are both zeros, neither
When a host receives an AQ revealing an address con ict, it
of them can use the IP address. The host sends an AR to
compares the AQ packet s AGE values with its own IP address
the originator, in order to notify it of the address con ict.
timer. If the host s timer is longer than AQ AGE, it drops its
It also drops its current IP address and initiates a new
own IP address and proceeds to rebid for a new address.
AQ for itself.
Generally, if the host s own IP address does not match the
B. Proposed Linear Allocation (LiA) Method
requested IP address contained in the AQ, the host broadcasts,
i.e., propagates the AQ packet. 1) LiA Principle of Operation: In Linear Allocation (LiA),
If a host receives an AQ with a con icting address and when a host is powered on or joins a mobile ad hoc subnet-
needs to send an AQ packet for itself, it includes its current work, it waits for some beacon from the network. If it receives
IP Address Timer value as the AGE in the AR that it sends to no beacon within some time period, it concludes that it is the
the originator. The host needs to keep this AGE information in initial node of the network. It then selects the rst IP address
memory, in order to avoid the occurrence of a self-dropping in the usable IP address pool as its IP address. If other nodes
situation when it receives the same AR again. The AR packet exist, a new node joining the network will receive some beacon
noti es the AQ originator of the address con ict. The AR which contains the maximum IP address used in the network
packet format is shown in Fig. 2. (Max.IP) within a speci c period. The node selects a candidate
IP address equal to Max.IP + 1.
TYPE (AR) AGE LiA is similar to RADA, with some exceptions concerning
Requested IP Address
candidate IP address selection and the resolution of address
con icts. Instead of AQ and AR, LiA uses three types of
Fig. 2. AR Packet Format
control messages which have a common format, as shown in
Fig. 3.
When the host which initially sent the AQ receives an AR
packet indicating that there is an address con ict there are
TYPE AGE
three possible cases: Requested IP Address
Identification
If the AGE value in the AR packet is greater than its own
IP Address Timer, the host recognizes that the address has
Fig. 3. The common format of control messages in LiA
already been allocated. The host then repeats the address
request process again, i.e., it initiates an AQ.
The control messages can be classi ed into BEACON,
It is possible that the host already sent the AR packet
ANNOUNCE and WINNER messages according to the type
but that it receives the same AR packet again from its
eld, and the role of the AGE eld is the same as that of
neighbors. In this case the AGE values will be identical,
RADA. The Identi cation eld represents the unique identity
the host just discards the AR packet.
of each node (i.e., its MAC address).
If the AR packet s AGE value is less than either the
BEACON If the type eld is set to zero, this control
current AQ AGE value in its memory or its IP Address
message becomes a BEACON message. The node that has
Timer (i.e., the host did not send any AQs recently), it
the maximum IP address used in the network, periodically
indicates an address con ict. In this case, the host should
broadcasts a BEACON message which includes its IP
perform ACRP immediately.
address in the Requested IP Address eld. In this way,
When a host sends an AQ, it sets an AQ timeout timer. If
a new node joining the network can acquire information
it does not receive any AR packets within the AQ timeout
about the IP addresses used in the network.
period, it rebroadcasts the AQ again. This process is repeated
ANNOUNCE If the type eld is set to one, this
until the number of the retries reaches the pre-con gured value
control message becomes an ANNOUNCE message. After
of AQ RETRIES (it is proposed to be 3) or an AR is received.
a new node selects its IP address candidate, it broadcasts
If no AR is received after the permitted reattempts, the host
an ANNOUNCE message which includes its IP address
takes the Requested IP Address as its own. It then starts its IP
candidate in the Requested IP Address eld. This control
2 Recall message is needed to know whether the same IP address
initially that both timer and AGE values were set to zero.
candidate is chosen by several nodes at the nearly same then starts a con rm timer and enters into detection phase. If
time or not. a new node receives other control messages, (i.e., an announce
WINNER If the type eld is set to two, this control and a winner) with an identical IP address before its con rm
message is a WINNER message. When two or more timer expires, address con ict is detected. When address
nodes want to use the same IP address, they contend con ict occurs during the detection phase, new nodes enter
with each others. After some time, one becomes the into the resolution phase. The resolution scheme determining
winner and the others become the losers through address one winner and some losers based on nodes IDs belongs to
con ict resolution process. Then, a WINNER message, the resolution phase.
which means that the competed IP address is allocated, 2) Proposed Linear Allocation with Collision Resolution
is broadcast by the winner and address con ict resolution (LiACR) Method: To overcome a weak point in LiA, we pro-
process is re-initiated among the losers. pose an enhanced version of LiA, known as Linear Allocation
with Collision Resolution (LiACR). Recall that in LiA, if a
Each node maintains three variables for address allocation:
node sending an announce message receives control messages
(a) Candidate IP, (b) Allocated IP and (c) Max.IP. A node
with the identical IP address it may re-initiate the address
stores the candidate for its local IP address to Candidate IP
acquisition process immediately. In LiACR, however, a node
and sets Allocated IP after the usage of its local IP address
sending an announce message should wait for a pre-de ned
is admitted. The maximum IP address used in the network
period, S, and collect other announce messages. With IP
known to the node is stored in Max.IP.
address information collected during this period it checks if its
In Fig. 4, the operation of LiA is shown in detail. New node
ID is the smallest or not. If so, it becomes the the winner and
rst sets Candidate IP to UNALLOC and starts the timer set
to 5.0 propagation delay. If the node receives no beacon broadcasts a winner message, and then uses its Candidate IP
address as its local IP address. Otherwise, it becomes the loser
message before the timer expires, it becomes the initial node
and increases its Candidate IP by its precedence value based
of the network. It sets Allocated IP to the rst IP address
on its ID not one. The losers broadcast announce messages
available in Address Pool and periodically broadcasts a beacon
and reset their timer depending on their precedence. If they
message for any node arriving in the future. On the other hand,
receive no control messages before their timer expires, they
if the node receives a beacon message, it selects Candidate IP
can determine their local IP addresses. In the case of other
equal to Max.IP included in the beacon message + 1. Then
address con icts, this process is repeated until all of the nodes
it broadcasts an announce message including its IP address
have obtained their IP addresses.
information to approve Candidate IP for the use of Allocated
For example, suppose that nodes A, B and C enter into
IP. If any control message is not received, Allocated IP is set to
the network simultaneously, and that node A has the highest
Candidate IP and beacon messages are periodically broadcast.
precedence, while node C has the lowest precedence. Three
On receiving other announce message, if its Candidate IP is
nodes receive a beacon message and broadcast announce
equal to the Requested IP Address in the received announce
messages at the nearly the same time. After period S, each
message and its identi er is less than the Identi cation in the
node is aware of every other node that is requesting the
received announce message, it sends a winner message and
same IP address as itself. Based on their precedence, node
continues to wait for any control message before the timer
A becomes the winner and broadcasts an winner message.
expires. Otherwise, it unsets its Candidate IP and wait for
If there are no con icts during period S, node A can use
a beacon message again. On receiving a winner message, if
its Candidate IP address as its local IP address. Node B
its Candidate IP is equal to the Requested IP Address in the
increases its candidate IP by one, while node C increases its
received winner message and its identi er is less than the
Candidate IP by two. After node A acquires its IP address,
Identi cation in the received winner message, it continues
nodes B and C broadcast announce messages. Therefore,
to wait for any control message before the timer expires.
after timeout depending on their precedence, nodes B and C
Otherwise, it re-attempt the address acquisition process.
determine their IP addresses. Through LiACR, nodes A, B and
After a new node sets its Allocated IP, it periodically broad-
C can acquire their IP addresses with the decreased number
casts a beacon message to inform its IP address information to
of control messages.
other nodes. Other beacon messages including an IP address
greater than its Allocated IP mean that the node possesses LiACR is devised to reduce control message overhead. With-
the maximum IP address used in the network no more. If out any performance degradation, LiACR can reduce control
the difference between its Allocated IP and the Requested IP overhead even when several nodes enter into the network
Address in the received beacon message is greater than one, simultaneously.
it re-initiates the address acquisition process to avoid address
C. Network Partitioning and Merging
con ict. Otherwise, it updates Max.IP and broadcasts a beacon
In the case of RADA, network partitioning and merging are
message no more.
In LiA, the ACRP procedure has two phases: (a) detection not regarded as special network events, so no more operations
phase, and (b) resolution phase. A new node joining the are needed. Instead, ACRP just recognizes these situations
network selects its IP address candidate and broadcasts an as duplicated addresses and resolves address con icts due to
announce message to con rm the usage of its IP address. It network merging. In detail, if two network partitions merge,
Start
Max.IP = Candidate IP
= UNALLOC
Recv BEACON ?
No
Yes
Max.IP = BEACON.IP
Candidate IP = Max.IP + 1
Max.IP = Candidate IP = Send ANNOUNCE
The first IP in Address Pool
No
Recv Control?
Allocated IP Yes
= Candidate IP
Candidate IP No
== Control.IP ?
Send BEACON
Yes
No
Recv BEACON ? No No
Max.IP = BEACON.IP Recv ANNOUNCE ? Recv WINNER ?
Yes Yes
Yes Yes
No Allocated IP No Allocated IP
== BEACON.IP >= BEACON.IP? myID >= No myID >= No
05.dvi
Contact this candidate