Transcript ppt

Duplicate address detection and
autoconfiguration in OLSR
Saadi Boudjit; Cedric Adjih; Anis Laouiti; Paul Muhlethaler
Hipercom Project
National Institute in Computer science and Control
INRIA - France
Outline

OLSR Overview

Autoconfiguration

AutoConfiguration in IPv6

AutoConfiguration in Ad Hoc networks

DAD-MPR flooding algorithm and Autoconfiguration in OLSR

Conclusion
2
OLSR Overview


OLSR: Proactive
MPR flooding
Among the 1-hop neighbors of node m, only a
subset of nodes are selected as MPRs and
hence retransmit the messages of m.
3
OLSR Overview


Recently: RFC 3626 (IETF/MANET)
Link State protocol
-
Periodic messages
Neighbor sensing:
“HELLO” messages: list of neighbors
-
Topology discovery (Topology Control):
List of neighbors sent to the whole net (in “TC” messages)
- Routes:


Computed to all nodes
Routes computed independently of traffic
- OLSR Gateways:
Host and Network Association “HNA” messages
4
AutoConfiguration

What is the autoconfiguration ?



Automatic assignment of parameters which are necessary to a node to join a network (IP address for
example);
But also automatic reassignment of network parameters in case of conflict.
Why ad hoc networks need autoconfiguration ?

Manual configuration is impractical in large scale Manets;

User-friendliness is necessary for new emerging applications like wireless internet.
5
AutoConfiguration in IPv6

Automatic configuration
Two methods :


Stateless Address Autoconfiguration
Periodic broadcast of the network related information by the Router;
Stateful Address Autoconfiguration
Hosts rely on a DHCP server to acquire the network related information, necessary
to its configuration;
6
Stateless AutoConfiguration
IPv6 Router
IPv6 Address 2001:0660:1000::ID4
IPv6 Address 2001:0660:1000::ID2
“Neighbor Advertisement” Message
IPV6 LAN
MAC address MAC5
Link-local Address fe80::ID5
“Neighbor Sollicitation” Message
IPv6 Address 2001:0660:1000::ID3
“Neighbor Sollicitation “ Message
MAC address MAC1
Link-local Address fe80::ID1
Unique Address …
7
Stateless AutoConfiguration
IPv6 Router
IPv6 Address 2001:0660:1000::ID4
IPv6 Address 2001:0660:1000::ID2
“Router Advertisement” Message
Bit M
Prefix 2001:0660:1000
IPV6 LAN
“Router Sollicitation” Message ff02::2
IPv6 Address 2001:0660:1000::ID3
MAC address MAC1
Link-local Address fe80::ID1
IPv6 global unicast address 2001:0660:1000::ID1
8
Stateful AutoConfiguration
IPv6 Router
IPv6 Address 2001:0660:1000::ID4
IPv6 Address 2001:0660:1000::ID2
DHCP Server
IPv6 Address 2001:0660:1000::ID
IPV6 LAN
“DHCP Advertisement” Message containing its IPv6 address
IPv6 Address 2001:0660:1000::ID3
“DHCP Sollicitation” Message ff02::1:2
DHCP Client
MAC address MAC1
Link-local Address fe80::ID1
unique address…
9
Stateful AutoConfiguration
IPv6 Router
IPv6 Address 2001:0660:1000::ID4
IPv6 address 2001:0660:1000::ID2
DHCP Server
IPv6 Address 2001:0660:1000::ID
IPV6 LAN
“DHCP response” Message, extension=2001:0660:1000::
“DHCP request” Message, address extension
IPv6 address 2001:0660:1000::ID3
DHCP client
MAC address MAC1
Link-local address fe80::ID1
Unique address…
IPv6 global unicast address 2001:0660:1000::ID1
10
AutoConfiguration in Ad Hoc networks
More difficult in MANET environment than that in hardwired networks due to:

Instability of mobile nodes;

Openness of Ad Hoc networks;

Absence of a central administration.
11
AutoConfiguration in Ad Hoc networks
Scenario 1 : A mobile node joins and then leaves a MANET once.
A
B
MANET
- An unused IP address is allocated to a node on it’s arrival and becomes free on it’s
departure.
12
AutoConfiguration in Ad Hoc networks
Scenario 2 : Network partitions and merges
B
Partition 2
Partition 2
A
A
Partition 1
Partition 1
(a)
(b)
- If one or more configured nodes go out of others’ transmission range  The network
becomes partitioned;
- When these nodes approach each other, the partitions merge later  Possibility of
address conflict.
13
AutoConfiguration in Ad Hoc networks
Scenario 3 : Merger of two independent MANETS
A
B
MANET 1
MANET 2
- There may be some duplicate addresses in both of them  Some(or all) nodes in
one MANET may need to change their addresses.
14
AutoConfiguration in Ad Hoc networks
Solutions :
Several solutions have been proposed, which can be divided into the following three categories:
(1) Conflict-detection allocation algorithms;
(2) Conflict-free allocation algorithms;
(3) Best-effort allocation algorithms.
15
1- Conflict-detection allocation
Principle :
1- A new node chooses an IP address tentatively, and requests for approval from all the
configured nodes in the network;
2- If the conflict is found by veto from a node with the same IP address, the procedure is
repeated until there is no duplicate address.
Illustration: OLSR for IPv6 Networks
Saadi Boudjit, Pascale Minet, Cedric Adjih, Anis Laouiti
HIPERCOM Project, INRIA, France
16
2- Conflict-free allocation
Principle :
1- A node taking part in allocation assigns an unused IP address to a new node;
2- This is achieved by the assumption that the nodes taking part in allocation have disjoint
address pools. Thus they could be sure that the allocated addresses are different.
3- Every time when a mobile node joins, an address pool is divided into halves between it and a
configured node.
Illustration: DCDP(Dynamic Configuration and Distribution Protocol)
Sajal K.Das - University of Texas (USA)
Archan Misra, Subir Das, Anthony Mc Auley – Telcordia Technologies(USA)
17
3- Best-effort allocation
Principle :
1- The nodes responsible for allocation try to assign an unused IP address to a new node as far
as they know  The same free IP address in the global address pool could be assigned
to two or more new nodes arriving at almost the same time ;
2- The new node uses conflict detection to guarantee that it is a free IP address;
Illustration: DDHCP(Distributed Dynamic Host Configuration Protocol)
Sanket Nesargi, Ravi Prakash
18
4- Summary of DAD algorithms
Conflict-free allocation
algorithms
Conflict-detection
allocation algorithms
Best-effort allocation
algorithms
Active DAD algorithms
Passive DAD algorithms
Distribute additional control
information in the network to
prevent address duplication
Continuously monitor routing
protocol control traffic to
detect address duplicates
19
AutoConfiguration in OLSR
Our autoconfiguration mechanism is divided into two
parts:
1- Initial address assignment (2 ways)


The arriving node can perform a random selection in a well known
pool of addresses;
One of the neighbors selects the address on behalf of the arriving
node.
2- Duplicate Address Detection “Proactive DAD”:

Periodic broadcast of MAD messages;

MAD messages must reach all the nodes in the network.
20
AutoConfiguration in OLSR
1- Initial address assignment
HELLO
HELLO
HELLO
HELLO
HELLO
Temporary address
21
AutoConfiguration in OLSR
1- Initial address assignment
DR
MAD
MAD
MAD
UNIQUE ADDRESS CONFIRMATION
Unique address
22
AutoConfiguration in OLSR
2- Proactive DAD
After a node being configured, it must periodically broadcast MAD(Multiple Address
Declaration) messages containing:

An identifier of the node (Node ID);

The list of interface addresses of the node on which OLSR is running;
In order to perform DAD when a merge of two previously disconnected MANETs occur.
23
AutoConfiguration in OLSR
2- Proactive DAD
MAD
MAD
MAD
MAD
MAD
MAD
A configured node
MAD messages will reach all the nodes in the network
24
AutoConfiguration in OLSR
A node detects and address conflict if:

It receives a MAD message having the same address as its
own, but with a different identifier.
25
AutoConfiguration in OLSR
Possibilities for MAD diffusion:

Pure flooding

Drawbacks:



Not using the optimizations of the underlying routing protocol;
High bandwidth consumption
MPR flooding

Drawbacks:


MPR calculation is based on the assumption that there is no address
duplication in the neighborhood of a node.
Therefore, OLSR relaying optimization rules may not be sufficient to
ensure diffusion in some conflictual cases.
26
AutoConfiguration in OLSR
Illustration:
• Two conflicting nodes X1 and X2 in the
2-hop neighbors of node I;
• Node I could not calculate its MPR set
correctly;
• MAD messages of X1 and X2 can not be
propagated throughout the entire network;
• Consequently, nodes X1 and X2 will not
detect the address conflict.
27
AutoConfiguration in OLSR



New rules are added to the classical MPR flooding algorithm for MAD
message diffusion;
The set is called DAD-MPR flooding, for Duplicate Address Detecting
MPR flooding;
In the absence of packet loss, the DAD-MPR flooding algorithm will
allow a MAD message to reach all the nodes in the network.
28
DAD-MPR flooding algorithm
Rules added to the classical MPR flooding algorithm:
Rule1:

The MAD duplicate message detection will be based on the node
originator address, the message sequence number, plus the node
identifier;
Rule2:

If a given node N receives a MAD message from a neighbor M, it will
repeat this message if one of its 1-hop neighbors has the same address
as the one contained in the MAD message.

In this case the MAD TTL value must be set to 1 to avoid the
transmission of the MAD message beyond the conflicting nodes;
29
Proof of correctness
• We assume that there are only two nodes
in conflict ,A1 and A2, in the network and
they are d hops away from each other;
• We denote by Ni the set of nodes which are
exactly at distance i of A1 and d-i of A2 for
i є {1, …, d-1};
• Those sets contain nodes that are precisely
on a shortest path from A1 to A2;
• Hence several cases can occur, depending on
on the distance d,
30
Proof of correctness
• distance d = 1 , 2
• Nodes A1 and A2 are in the radio
range of each other, the conflict will
be detected by both nodes;
• Node B detects the conflict
and by applying the Rule2,
the nodes A1 and A2 will
receive the MAD messages
of each other;
31
Proof of correctness
• distance d = 3
• Nodes A1 and A2 calculate their MPR set
correctly. A1 chooses B as an MPR to reach
node C, and A2 chooses C as MPR to reach B;
• Nodes B and C don’t choose each other as MPR,
consequently, A1 MAD messages will never reach
A2, and A2 MAD messages will never reach A1;
• Node B detects that one of its 1-hop
neighbors, A1, has the same address as the one
contained in the MAD message originating from
node A2  using Rule2, node B relay the MAD
message of A2 to reach A1;
• By the same manner, MAD messages of A1 will
reach A2 and the conflict will be detected;
32
Proof of correctness
• distance d = 4
• Nodes A1 and A2 don’t have duplications
in their 1-hop and 2-hop neighbors,
 they calculate their MPR set properly;
• Nodes B and D don’t have duplications
in their 1-hop and 2-hop neighbors,
 they calculate their MPR set properly;
• The MAD messages of A1 and A2 will reach
all the intermediary nodes B, C, and D;
• Node C looks to the nodes A1 and A2 as a
single node, say A  C chooses only one
node between B and D as an MPR to cover A;
• Therefore, we are sure that one of the two
nodes (A1 and A2) receives the MAD
messages generated by the other node and
then detects the conflict.
33
Proof of correctness
• distance d ≥ 5
• Nodes A1 and A2 and all the intermediary
nodes don’t have duplications in their 1-hop
and 2-hop neighbors;
• Hence all the intermediary nodes calculate
their MPR set correctly;
• Using the classical MPR flooding algorithm,
the MAD messages of A1 and A2 will be
correctly propagated to the nodes A2 and A1
respectively;
34
Conclusion
- Proposed:
- changes to the classical MPR flooding algorithm
- Duplicate address detection algorithm
- relies on two procedures
- very well integrated with OLSR
- originality: proactive DAD
- low complexity
- Future work includes the adoption of:
- Refinements for address conflict resolution
- Handling the case of multiple conflicts
- Taking into account the case of nodes with multiple interfaces
- Considering implementation issues in more details
35
Questions ...............................??????
36