Transcript NAT-Based Internet Connectivity for Multi-Homed On

NAT-Based Internet Connectivity for Multi-Homed
On-Demand Ad Hoc Networks
Paal Engelstad and Geir Egeland
University of Oslo (UniK) / Telenor R&D, 1331 Fornebu, Norway
Presented by: Paal Engelstad
http://www.unik.no/~paalee/PhD.htm
Motivation

Ad hoc networks need to access the fixed Internet
– Some nodes connected to external IP-networks may operate as gateways for
other MANET nodes

Previously proposed solutions:
– A gateway implementing Mobile IPv4 Foreign Agent (MIP-FA)
• Internet draft by Belding-Royer et al.
• MSc. Thesis on ”MIPMANET” by Alriksson and Jönsson, KTH, August 1999
– A gateway implementing a Network Address Translator (NAT)
• Uppsala University’s implementaton of AODV

NAT-based solutions have yet been poorly
documented in published material
2
Assume you know AODV...
Short re-cap:
 A Source Node discovers route to destination on demand
– It floods an RREQ to find a route to a destination
– The RREQ forms a return route on each node

The Destination node responds:
– It unicasts an RREP along the reverse route
– The RREP forms a forward route

Every node maintains its own destination sequence number
– Incremented before the flooding
– Ensures loop freedom


An intermediate node may reply to RREP on behalf of
Destination node if it has a valid route to the destination
With multiple RREPs, the routing protocol prefers
– RREPs with higher destination sequence numbers
– Fewest hops between source and destination
3
Background (1): MIP-FA
External Host

Overview
Internet
– A gateway with FA-support (MIPFA) which understands AODV
– A MANET node with MIPv4
support
– The MANET registers the
MIP-FA Gateway with its Home
Agent

Home Agent
Foreign Agent
Drawbacks:
– High complexity
– MIP and AODV makes
unsynchronized modifications to
routing table
– MIP requires global IPv4
addresses
Source Node
MANET
4
Background (2): NAT
External Host

Overview
Internet

Drawbacks
– The well-known drawbacks with the
use of NATs
– Dynamic change of gateways must be
solved by MIPv4

3
2
1
Advantages
– Less complex, easy to implement and
deploy
– Does not rely on MIPv4 deployment
and fixed IPv4 address
Network
Address Translator
4
Source Node
MANET
5
Route Discovery with Proxy RREP
F
F
External Host


Source Node (SN) broadcasts a
RREQ to establish route to External
Host (XH)
Gateway impersonates XH, by
sending a RREP on behalf of XH.
Internet
– Uses XHs IP address as Source IP
Address in RREP
– This is a “Proxy RREP”
F
F



Gateway
SN forwards packets to XH using the
route established by the Proxy RREP.
The gateway forwards the packet to
XH
How about the destination sequence
number in a ”Proxy RREP”?
6
Source Node
MANET
RREQ: Route Request
RREP: Route Reply
XH: External Host
NAT: Network Address Translation
Destination Seqence numbers in
Proxy RREP

MIP-FA Gateway (Belding-Royer et.al.):
– Source Node normally sets RREQ with
• Unknown Seqence Number bit = 1
• Destination Sequence Number = 0
– Gateway copies this into the ”Proxy RREP” (i.e. a zero destination sequence number)

AODV-UU NAT-solution:
– Use Gateway’s own destination sequence number (a hack)
– Require different IP address spaces
• To distinguish internal from external nodes
• Not acceptible or at least very limiting

We proposed a better NAT-solution with ”Proxy RREP”:
– Implementing the MIP-FA policy (above)
– Ensure that an Internal node never uses a zero destination sequence number
– Hence, a real RREP from an internal MANET node always have preference over a
Proxy RREP (i.e. no problem if gateway always send Proxy RREP...)
7
Proxy RREPs and Multi Homing
F
External Host

The Source Node (SN) broadcasts a
RREQ to establish route to the
external Host (XH)
F

Both gateways send a Proxy RREP
on behalf of the XH
F

The Source Node forwards packets to
XH using the route established by one
of the Proxy RREPs.
F

The “winning” gateway forwards the
packet to the XH
8
Internet
NAT
NAT
Source Node
MANET
RREQ: Route Request
RREP: Route Reply
XH: External Host
NAT: Network Address Translation
Race Conditions - a route needs to
be re-discovered
?
F
F
F
F
F
F
External Host


The Source Node (SN) broadcasts a
RREQ to establish route to the external
Host (XH)
Both gateways send a Proxy RREP on
behalf of the XH, GW1 wins

SN sends packets for XH via GW1.

After link break or route timeout, SN
broadcasts a new RREQ to re-establish
the route to XH


Both gateways send a Proxy RREP on
behalf of XH, but this time GW2 “wins”
SN sends subsequent packets for XH via
GW2, connection fails
9
Internet
GW1
(NAT)
GW2
(NAT)
Source Node
MANET
RREQ: Route Request
RREP: Route Reply
XH: External Host
GW: Gateway
Demonstrating Race Conditions
due to route re-discovery

Testbed experiment (i.e. lab implementation)
– Fewer nodes, more static
– Active Route Timeout (3 sec of AODV) triggers route re-discovery

Simulations
– Many nodes, more mobility, etc...
– Network dynamics (such as mobility) triggers route re-discovery

I will only go through the simulations if time permits...
10
Test bed experiment (1)

AODV-implementation by Uppsala
University
External Host
– IEEE 802.11
– Linux
– MAC-layer filtering

Internet
Packet Transmission Interval
– 1 sec:
• OK
– 4 sec: (e.g. interactive traffic, Telnet, etc...)
• Race conditions


Best performance: 11% probability of
(Telnet-) session breakage due to race
condition
Increased random max ”processing time”
(Tmax):
=> prob. -> 50%
11
GW1
(NAT)
GW2
(NAT)
Intermediate
Node
MANET
Source Node
Share of RREPs received
Test bed experiment (2)
11
Tmax [ms]
12
Simulation setup

Glomosim, with AODV module

IEEE 802.11, Two-Ray channel model

Traffic pattern: Constant Bit Rate (CBR), 1024 byte packets

50 nodes
– Radio Range 50m, 200mx200m square
– Radio Range 10m, 40mx40m square
13
Simulation #1
Testing Race Conditions due to Route Timeout:
– Static scenario, and varying Packet Transmission Interval (PTI):
– Race Conditons have a dramatic impact on performance when PTI
exceeds Active Route Timeout of AODV (of 3 sec.).
Variable Packet Transmission Interval
(with fixed route timeout, fixed terrain size and no mobility)
50 %
Session breakages/Data Packet

Range 10
25 %
0%
500
Range 50
1000
1500
2000
2500
3000
3500
4000
Packet Transmission Interval (ms)
14
4500
5000
Simulation #2
 Network
configurations/ topologies that leads to
bad performance?
– When gateways are an equal number of hops away from SN
– (i.e. on right hand side of figure...)
Distribution of different network configurations
(with fixed terrain size and no mobility)
50 %
Share of Network Configurations
45 %
40 %
35 %
30 %
Range 10m
25 %
Range 50m
20 %
15 %
10 %
5%
0%
0%
20 %
40 %
60 %
80 %
Session Breaks/Packet for different Network Configurations
15
Simulation #3
Testing effects of terrain size (i.e. of node density or of
”strength” of connectivity):
– Fully connected network: Probability of 50%
• Attributed to the ”ideal” model of Glomosim
– Problem decreases as terrain size increases, because probability that gateways
are an equal number of hops away, decreases.
Variable Terrain Size
(with fixed route timeout, 2Kbps CBR and no mobility)
60 %
Session breakages/Data Packet

50 %
40 %
Range 10
30 %
Range 50
20 %
10 %
0%
5
10 15 20 25 30 35 40 45 50 55 60 65 70 75 80
(50)
(100)
(150)
(200)
(250)
(300)
(350)
(400)
Size of Sides of Terrain Square (m)
16
Simulation #4

Testing Race Conditions due to link breaks, by adding mobility:
– Random Way Point (with zero rest-time and variable max velocity)
– PTI = 1 sec, i.e. safely below the Active Route Timeout of AODV
– See that problem increases rapidly to unacceptably high levels, even for relatively low
levels of mobility
Other non-deterministic effects (radio-fading, packet collisions, etc.)
occuring in a MANET, and is not easily caught by a simulation model
– This effecs will also accellerate the problems of Race Conditions
Variable Mobility
(with fixed route timeout, CBR 8 Kbps - i.e.1pkt/sec - and fixed terrain size)
50 %
45 %
Session breakages/Packet

40 %
35 %
30 %
25 %
Range 10
20 %
Range 50
15 %
10 %
5%
0%
0
(0)
1
(5)
2
(10)
3
(15)
4
(20)
5
(25)
6
(30)
Max Random Speed (m/sec)
17
7
(35)
8
(40)
Summary of results - I

Our work shows that race conditions due to Proxy RREPs can be
damaging in on-demand ad hoc networks
– For smaller networks (testbed)
– And for larger networks (simulations)

Race Conditions represents a non-negligible problem, especially
for
– Interactive applications where the packet transmission interval easily exceeds
the Active Route Timeout of AODV (testbed and simulations)
– Networks with certain level of dynamics and/or mobility (simulation)
18
Summary of results - II

In the paper we propose mechanisms to remove the race
conditions with “Proxy RREPs”:
– By making SNs aware of gateways
– Breakdown: When 2 SNs communicate with same XH over different gateways

Although results are targeted at NAT-based gateways, they also
have relevance to MIP-FA based solution
– We proposed a way to avoid race conditions with Proxy RREPs
– However, the problem remains due to ingress filtering

Conclusion: Using proxy RREPs is NOT the way to go!
– At least not for NAT-based gateways
19
Proposed working solution
External Host




SN discovers that XH is not present locally
after unsuccessful route establishment on
MANET
SN sets a “Gateway bit” in RREQ for XH
Gateways responds with a RREP
establishing route to the GW (i.e. no race
conditions will occur)
RREP contains extensions with
– XH’s destination IP address
– The functionality/capabilities of the gateway

SN tunnels traffic to selected GW
src=SN IP-payload
dst=XH
Inner IPheader
src=SN
src=SN IP-payload
dst=GW1 dst=XH
GW tunnels return traffic from XH to
SN
– This is necessary due to specifics in the
AODV specification
Intermediate Node
MANET
Source Node
RREQ: Route Request
RREP: Route Reply
XH: External Host
SN: Source Node
20
GW2
(NAT)
GW1
(NAT)
Outer IP- Inner IPheader
header
– GW decapsulates and forwards to XH

Internet
Questions?