Transcript Mobile IP

Chapter 8:
Mobile Network Layer
Introduction of Mobile IP
Background- The Problem with Old IPs:
Earlier internet protocol versions do not support
host mobility.
These were designed such that moving hosts were
not considered : a node’s point of attachment to
the network remains unchanged at all times and an
IP address identifies a particular network.
To support a mobile host with current methods,
reconfiguration is necessary any time a mobile
host moves.
Introduction of Mobile IP
This is an unacceptable solution as it is time
consuming and error prone.
Thus the rise of “Mobile IP”.
What is Mobile IP?
Mobile IP is an internet protocol designed to
support host mobility.
Its goal is to provide the ability of an host to stay
connected to the internet regardless of their
location.
Mobile IP is able to track a mobile host without
needing to change the mobile host’s long-term IP
address.
Mobile IP Features


Transparency
 mobile end-systems keep their IP address.
 continuation of communication after interruption
of link possible.
 point of connection to the fixed network can be
changed.
Compatibility
 no changes to current end-systems and routers
required.
 mobile end-systems can communicate with fixed
systems.
Mobile IP Features


Security
 authentication of all registration messages.
Efficiency and scalability
 only little additional messages to the mobile
system required (connection typically via a low
bandwidth radio link).
 world-wide support of a large number of mobile
systems in the whole Internet.
Terminology



Mobile Node (MN):
A host or router that may change its point of
attachment from one network or sub network to
another through the internet.
This entity is reassigned a fixed home address on a
home network, which other correspondent hosts will
use to address their packets to regardless of its
current location.
Terminology





Home Agent (HA):
A router that maintain a list of registered mobile
nodes in a visitor list.
It is used to forward mobile node-address packets to
the appropriate local network when the mobile
nodes are away from home.
After checking with the current mobility bindings
for a particular mobile node.
It encapsulated datagram and sends it to the mobile
host’s current temporary address when the mobile
node.
Terminology





Foreign Agent (FA):
A router that assists a locally reachable mobile node
that is away from its home network.
It delivers information between the mobile node and
the home agent.
Correspondent Node (CN):
This node sends the packets which are addressed to
the communication partner.
Terminology




Care-of-address (COA):
An address which identifies the mobile node’s
current location.
It can be viewed as the end of a tunnel directed
towards a mobile node.
It can be either assigned dynamically or associated
with its foreign agent.
Terminology
COA
home
network
router
FA
router
HA
Internet
CN
router
MN
foreign
network
Example network
HA
MN
router
home network
mobile end-system
Internet
(physical home network
for the MN)
FA
foreign
network
router
(current physical network
for the MN)
CN
end-system
router
IP Packet Delivery
3.
home
network
router
HA
router
FA
2.
4.
Internet
1.
CN
router
MN
foreign
network
IP Packet Delivery




Step 1: the CN wants to send an IP packet to the
MN. But CN does not know about the current
location of MN’s. here, MN is not a part of HA.
Step 2: a new header is put in front of the old IP
header showing the COA as new destination and HA
as source of the encapsulated packet.
Step 3:the foreign agent now decapsulates the packet
i.e. removes the additional header and forwards the
original packet with CN as source and MN as
destination to the MN.
Step 4:the MN sends the packet as usual with its
own fixed IP address as source and CN’s address as
destination.
Agent Discovery



One initial problem of an MN after moving is how
to find a agent.
How does the MN discover that its has moved?
For this purpose mobile IP describes two methods:
 Agent Advertisement
 Agent Solicitation
Agent Advertisement



HA and FA periodically send advertisement
messages into their physical subnets.
MN listens to these messages and detects, if it is in
the home or a foreign network (standard case for
home network).
MN reads a COA from the FA advertisement
messages.
Agent advertisement Packet
0
7 8
type
#addresses
15 16
23 24
checksum
lifetime
31
code
addr. size
router address 1
preference level 1
router address 2
preference level 2
...
type = 16
length = 6 + 4 * #COAs
R: registration required
type = 16
length
sequence number
B: busy, no more registrations
R B H F M G r T reserved
registration lifetime
H: home agent
COA 1
F: foreign agent
COA 2
M: minimal encapsulation
...
G: GRE encapsulation
r: =0, ignored (former Van Jacobson compression)
T: FA supports reverse tunneling
reserved: =0, ignored
Agent Solicitation



if no agent advertisement are present or the interarrival time is too high and the MN has not received
a COA by other reason.
So, the mobile node must send the Agent
Solicitations.
These solicitation messages do not flood the
network but basically an MN can search for an FA
endlessly sending out solicitation messages.
Registration


When the mobile node is away from home, it
registers its care-of-address with its home agent so
that home agent knows where to forward its
packets.
Depending on the network configuration the
mobile node could either register directly with its
home agent, or indirectly via the help of its foreign
agent.
Registration


In short, MN signals COA to the HA via the
FA, HA acknowledges via FA to MN.
These actions have to be secured by
authentication.
Registration
Other Network Registration
MN
FA
Same Network Registration
HA
MN
t
t
HA
Mobile IP registration request
0
7 8
type = 1
15 16
S B DMG r T x
home address
home agent
COA
identification
extensions . . .
S: simultaneous bindings
B: broadcast datagrams
D: decapsulation by MN
M mininal encapsulation
G: GRE encapsulation
r: =0, ignored
T: reverse tunneling requested
x: =0, ignored
23 24
lifetime
31
Mobile IP registration reply
0
7 8
type = 3
15 16
code
home address
home agent
31
lifetime
Example codes:
identification
registration successful
extensions . . .
0 registration accepted
1 registration accepted, but simultaneous mobility bindings unsupported
registration denied by FA
65 administratively prohibited
66 insufficient resources
67 mobile node failed authentication
68 home agent failed authentication
69 requested Lifetime too long
registration denied by HA
129 administratively prohibited
131 mobile node failed authentication
133 registration Identification mismatch
135 too many simultaneous mobility bindings
Tunneling



Tunneling refers to establishing of a pipe.
Pipe is a term used to specify a data stream
between two connected ends.
For e.g. when a mobile node is roaming in a
foreign network, the home agent must be able to
intercept all IP datagram packets sent to the
mobile node so that these datagrams can be
forwarded via tunneling.
Tunneling





There are two type of Tunnel:
Forward Tunnel:
A tunnel that shuttles packets towards the
mobile node. Its starts at the home agent, and
ends at the mobile node’s care-of-address.
Reverse Tunnel:
A tunnel that start at the mobile node’s care-ofaddress and terminates at the home agent.
Forward Tunneling
HA
2
MN
home network
Internet
receiver
3
FA
1
CN
sender
foreign
network
1. Sender sends to the IP address of MN,
HA intercepts packet.
2. HA tunnels packet to COA, here FA,
by encapsulation.
3. FA forwards the packet
to the MN.
Reverse Tunneling
HA
2
MN
home network
Internet
sender
1
FA
3
CN
receiver
foreign
network
1. MN sends to FA
2. FA tunnels packets to HA
by encapsulation
3. HA forwards the packet to the
receiver (standard case)
Mobile IP with reverse Tunneling


Router accept often only “topological correct“
addresses (firewall!)
 a packet from the MN encapsulated by the
FA is now topological correct
 furthermore multicast and TTL (Time to
Live) problems solved (TTL in the home
network correct, but MN is to far away from
the receiver)
Reverse tunneling does not solve
 problems with firewalls, the reverse tunnel
can be abused to circumvent security
mechanisms (tunnel hijacking)
Mobile IP with reverse Tunneling
optimization of data paths, i.e. packets will
be forwarded through the tunnel via the HA
to a sender (double triangular routing)
The standard is backwards compatible
 the extensions can be implemented easily and
cooperate with current implementations
without these extensions
 Agent Advertisements can carry requests for
reverse tunneling


Encapsulation






Encapsulation:
The process of enclosing an IP datagram within
another IP header which contains the care-ofaddress of the mobile node.
The IP datagram itself remains intact and untouched
throughout the enclosing process.
Decapsulation:
The process of stripping the outermost IP header of
incoming packets so that the enclosed datagram can
be accessed and delivered to the proper destination.
Decapsulation is the reverse process of
encapsulation.
Encapsulation Types



IP in IP Encapsulation
Minimal Encapsulation
Generic routing Encapsulation
IP in IP Encapsulation


To encapsulate an IP datagram using IP in IP
encapsulation, an outer IP header is inserted
before the datagram’s existing IP header.
There is tunnel between HA to COA.
IP in IP Encapsulation
ver.
IHL
DS (TOS)
length
IP identification
flags
fragment offset
TTL
IP-in-IP
IP checksum
IP address of HA
Care-of address COA
ver. IHL
DS (TOS)
length
IP identification
flags
fragment offset
TTL
lay. 4 prot.
IP checksum
IP address of CN
IP address of MN
TCP/UDP/ ... payload
Minimal Encapsulation

Minimal encapsulation (optional)
 avoids repetition of identical fields.
 e.g. TTL-time to live, version, DS-distributed
system (RFC (request for comment) 2474, old:
TOS-type of services).
 only applicable for non fragmented packets, no
space left for fragment identification.
Minimal Encapsulation
ver.
IHL
DS (TOS)
length
IP identification
flags
fragment offset
TTL
min. encap.
IP checksum
IP address of HA
care-of address COA
lay. 4 protoc. S reserved
IP checksum
IP address of MN
original sender IP address (if S=1)
TCP/UDP/ ... payload
Generic routing Encapsulation
In the most general case, a system has a packet
that needs to be encapsulated and delivered to
some destination.
We call this the payload packet.
The payload is first encapsulated in a GRE packet.
The resulting GRE packet can then be
encapsulated in some other protocol and then
forwarded.
Generic routing Encapsulation
We call this outer protocol the delivery protocol.
This specification is generally concerned with the
structure of the GRE header.
Generic routing Encapsulation
outer header
new header
RFC 1701
IHL
DS (TOS)
length
IP identification
flags
fragment offset
TTL
GRE
IP checksum
IP address of HA
Care-of address COA
C R K S s rec.
rsv.
ver.
protocol
checksum (optional)
offset (optional)
key (optional)
sequence number (optional)
routing (optional)
ver.
IHL
DS (TOS)
length
IP identification
flags
fragment offset
TTL
lay. 4 prot.
IP checksum
IP address of CN
IP address of MN
GRE
header
original
header
original data
original
header
original data
new data
ver.
TCP/UDP/ ... payload
RFC 2784 (updated by 2890)
C
reserved0
ver.
checksum (optional)
protocol
reserved1 (=0)
Optimization of packet forwarding


Problem: Triangular Routing
 sender sends all packets via HA to MN
 higher latency and network load
“Solutions”
 sender learns the current location of MN
 direct tunneling to this location
 HA informs a sender about the location of MN
 big security problems!
Optimization of packet forwarding

Change of FA
 packets on-the-fly during the change can be lost
 new FA informs old FA to avoid packet loss,
old FA now forwards remaining packets to new
FA
 this information also enables the old FA to
release resources for the MN
Optimization of packet forwarding
HA
CN
Data
Update
FAold
FAnew
Data
MN
Data
ACK
Data
Data
MN changes
location
Update
ACK
Data
Data
Warning
Registration
Data
Request
Update
ACK
Data
Data
t
Mobile IPv6
Mobile IP is the internet’s network-layer protocol.
Mobile IP provides best-effort, connectivity packet
delivery on behalf of transport-layer and higherlayer protocols.
There is different version of Internet Protocol.
In that IP version 6 the successor to today’s IP
version 4 protocol.
IPv6 protocol expands the available address space
for each packet and support of the internet security
protocol.
Problem with Mobile IP


Security
 authentication with FA problematic, for the FA
typically belongs to another organization
 no protocol for key management and key
distribution has been standardized in the
Internet
 patent and export restrictions
Firewalls
 typically mobile IP cannot be used together
with firewalls, special set-ups are needed (such
as reverse tunneling)
Problem with Mobile IP

QoS
 many new reservations in case of RSVP
 tunneling makes it hard to give a flow of
packets a special treatment needed for the QoS
IP Micro-Mobility Support
Mobile IP exhibits several problems regarding the
duration of handover and the scalability of the
registration procedure.
Assuming a large number of mobile devices
changing networks quite frequently a high load on
the home agents as well as on the network is
generated by registration and binding update
messages.
IP Micro-Mobility Support
IP micro-mobility protocols can complement
mobile IP by offering fast and almost seamless
handover control in limited geographical area.
The following three approaches to the solutions of
the micro-mobility problems.
Cellular IP
Hawaii
Hierarchical Mobile IPv6 (HMIPv6)
Cellular IP


Operation:
 “CIP Nodes” maintain routing entries for MNs
 Multiple entries possible
 Routing entries updated based on packets sent
by MN
CIP Gateway:
 Mobile IP tunnel endpoint
 Initial registration processing
Cellular IP

Security provisions:
 all CIP Nodes share
“network key”
 MN key: net key, IP addr
 MN gets key upon registration
Cellular IP
Internet
Mobile IP
CIP Gateway
data/control
packets
from MN 1
BS
MN1
BS
BS
MN2
packets from
MN2 to MN 1
Cellular IP
Advantage:
Manageability:
Cellular IP is mostly self-configuring and
integration of Cellular IP gateway (CIPGW) into a
firewall would facilitate administration of mobilityrelated functionality.
Cellular IP
Disadvantages:
Efficiency:
Additional network load is induced by forwarding
packets on multiple paths.
Transparency:
Changes to MNs are required.
Security:
Routing table are changed based on messages sent
by mobile node.
Additionally all system in the network can easily
obtain a copy of all packets destined for an MN.
HawaiiHandoff- Aware Wireless Access Internet
Infrastructure


Operation:
1
2
 MN obtains co-located COA and registers with HA.
 Handover: MN keeps COA, new BS answers Reg.
3
 Request and updates routers
4
 MN views BS as foreign agent
Security provisions:
 MN-FA authentication mandatory
 Challenge/Response Extensions mandatory
Hawaii
Internet
HA
Backbone
Router
Crossover
Router
4
BS
BS
Mobile IP
3
MN
2
Mobile IP
BS
MN
DHCP
Server
1
DHCP
Hawaii
Advantages:
Security:
Challenge-response extensions are mandatory.
In contrast to cellular IP routing changes are
always initiated by the foreign domain’s
infrastructure.
Transparency:
HAWAII is mostly transparent to mobile nodes.
Hawaii
Disadvantages:
Security:
There are no provision regarding the setup of
IPSec (IP security) tunnels.
Implementation:
No private address support is possible because of
co-located COAs.
Hierarchical Mobile IPv6 (HMIPv6)


Operation:
 Network contains mobility anchor point (MAP)
 mapping of regional COA (RCOA) to link
COA (LCOA)
 Upon handover, MN informs MAP only
 gets new LCOA, keeps RCOA
 HA is only contacted if MAP changes
Security provisions:
 no HMIP-specific security provisions
 binding updates should be authenticated
Hierarchical Mobile IPv6 (HMIPv6)
MAP-mobility anchor point
AR-Access router
RCOA- regional COA
LCOA- link COA
Internet
HA
RCOA
MAP
binding
update
AR
AR
LCOAnew LCOAold
MN
MN
Hierarchical Mobile IPv6 (HMIPv6)
Advantages:
Security:
MNs can have location privacy because LCOAs
can be hidden.
Efficiency:
Direct routing between CNs sharing the same link
is possible.
Hierarchical Mobile IPv6 (HMIPv6)
Disadvantages:
Transparency:
Additional infrastructure component (MAP).
security:
Routing tables are changed based on messages
sent by mobile nodes.
This requires strong authentication and protection
against denial or service attacks.
Additional security function might be necessary in
MAPs.
DHCP: Dynamic Host
Configuration Protocol

Application
 simplification of installation and maintenance
of networked computers.
 supplies systems with all necessary
information, such as IP address, DNS server
address, domain name, subnet mask, default
router etc.
 enables automatic integration of systems into
an Intranet or the Internet, can be used to
acquire a COA for Mobile IP.
DHCP: Dynamic Host
Configuration Protocol

Client/Server-Model
 the client sends via a MAC broadcast a request
to the DHCP server (might be via a DHCP
relay).
DHCPDISCOVER
DHCPDISCOVER
server
client
relay
client
DHCP - protocol mechanisms
client
initialization
server
(not selected)
determine the
configuration
DHCPDISCOVER
DHCPDISCOVER
DHCPOFFER
DHCPOFFER
server
(selected)
determine the
configuration
collection of replies
selection of configuration
DHCPREQUEST
(reject)
DHCPREQUEST
(options)
confirmation of
configuration
DHCPACK
initialization completed
release
DHCPRELEASE
delete context
DHCP characteristics



Server
 several servers can be configured for DHCP,
coordination not yet standardized (i.e., manual
configuration).
Renewal of configurations
 IP addresses have to be requested periodically,
simplified protocol.
Options
 available for routers, subnet mask, NTP
(network time protocol) timeserver, SLP
(service location protocol) directory, DNS
(domain name system)
Mobile Ad-hoc Network
Mobility support described in earlier section so far
relies on the existence of at least some
infrastructure.
Mobile IP requires, e.g., a home agent, tunnels and
default routers.
DHCP requires servers and broadcast capabilities
of the medium reaching all participants or relays
to servers.
Cellular phone networks require base stations,
infrastructure networks etc.
Mobile Ad-hoc Network
However, there are several situations where users
of a network cannot rely on an infrastructure, the
infrastructure is too expensive, or there is no
infrastructure at all.
In these situation ad hoc networks are the only
solution.
Solution: Wireless Ad-hoc
Network



Single-hop: All partners max. one hop
apart
 Bluetooth piconet, PDAs in a room,
gaming devices…
Multi-hop: Cover larger distances,
circumvent obstacles
 Bluetooth scatternet, car-to-car
networks…
Internet: MANET (Mobile Ad-hoc
Networking) group
Mobile Ad-hoc Network
Example for the use of ad hoc networks are:
Instant infrastructure:
Unplanned meetings, spontaneous interpersonal
communication etc. cannot rely on any
infrastructure.
Infrastructures need planning and administration.
It would take too long to set up this kind of
infrastructure therefore, ad hoc connectivity has to
be set up.
Mobile Ad-hoc Network
Disaster relief:
Infrastructures typically break down in disaster
areas.
Hurricanes cut phone and power lines, floods
destroy base stations, fires bum servers.
Thus, emergency teams can only rely on an
Infrastructures they can set up themselves.
No forward planning can be done and the setup
must be done extremely fast and reliably.
Mobile Ad-hoc Network
Remote area:
Even if Infrastructures could be planned ahead, it
is some times too expensive to set up an
Infrastructures in sparsely populated area.
Depending on the communication pattern ad hoc
networks or satellite Infrastructures can be a
solution.
Mobile Ad-hoc Network
Effectiveness:
Services of existing Infrastructures might be too
expensive for certain application.
If for example, only connection-oriented cellular
networks exist, but an application sends only a
small status information every other minute, a
cheaper ad hoc packet-oriented network might be
a better solution.
Furthermore, registration procedures might take
too long and communication overhead, so ad hoc
network can offer a better solution.
Manet: Mobile Ad-hoc Networking
Mobile
Router
Manet
Mobile
Devices
Mobile IP,
DHCP
Fixed
Network
Router
End system
Routing
While in wireless networks with infrastructure
support a base station always reaches all mobile
nodes, this is not always the case in an ad hoc
network.
A destination node might be out of range of a
source node transmitting packets.
Thus routing in needed to find a path between
source and destination and to forward the packets
appropriately.
Routing
In wireless networks using infrastructure cells
have been defined.
Within a cell, the base station can reach all mobile
nodes without routing via a broadcast.
In the case of ad hoc networks each node must be
able to forward data for other nodes.
Routing
In the next slide figure show at a certain time t1
the network topology might look as illustrated on
the left side of the figure.
Five nodes, N1 to N5 are connected depending on
current transmission characteristic between them.
In this snapshot of the network, N4 can receive N1
over a good link, but N1 receives N4 only via a
weak link.
Routing
Example of ad hoc network
N1
N1
N2
N3
N4
N3
N2
N4
N5
time = t1
N5
time = t2
good link
weak link
Routing
Thus links do not necessarily have the same
characteristics in both direction.
Reasons for this are e.g. different antenna
characteristics or transmit power.
N1 cannot receive N2 at all, N2 receives a signal
from N1.
This situation can change in the next snapshot at
t2 showns.
Routing
This very simple example already shows some
fundamental differences between wired networks
and ad hoc wireless networks related to routing.
Asymmetric links:
If node A receives a signal from node B this does
not tell anything about the quality of the
connection in the reverse direction.
B might receive nothing have a weak link or even
have a better link than the reverse direction.
Routing
Thus routing information collected for one
direction is of almost no use for the other
direction.
However, many routing algorithms for wired
networks rely on a symmetric scenario.
Routing
Redundant links:
Wired networks have redundant links to survive
link failures.
However, there is only some redundancy in wired
networks, which additionally is controlled by a
network administrator.
In ad hoc networks nobody controls redundancy
so there might be many redundant links up to the
extreme of a completely meshed topology.
Routing
Routing algorithms for wired networks can handle
some redundancy but a high redundancy can cause
a large computational overhead for routing table
updates.
Routing
Interference:
In wired networks links exist only where a wire
exists and connections are planned by network
administrators.
This is not the case for wireless ad hoc networks.
Links come and go depending on transmission
characteristics one transmission might interfere
with another one and nodes might overhear
transmissions of other nodes.
Routing
Interference thus creates new problems by
‘unplanned’ links between nodes: if two close-by
nodes forwarded two transmissions, they might
interfere and destroy each other.
Interference might also help routing on the other
hand.
A node can learn the topology with the help of
packets overheard.
Routing
Dynamic topology:
The greatest problem for routing arises form the
highly dynamic topology.
The mobile nodes might change frequently.
This result in frequent changes in topology, and
valid only for a short period of time.
In ad hoc networks routing tables must somehow
reflect these frequent change in topology and
routing algorithms have to be adapted.
Traditional Routing Algorithms


Distance Vector
 periodic exchange of messages with all
physical neighbors that contain information
about who can be reached at what distance.
 selection of the shortest path if several paths
available.
Link State
 periodic notification of all routers about the
current state of all physical links.
 router get a complete picture of the network.
Problems of traditional routing
algorithms


Dynamic of the topology
 frequent changes of connections, connection
quality, participants.
Limited performance of mobile systems
 periodic updates of routing tables need energy
without contributing to the transmission of user
data, sleep modes difficult to realize.
 limited bandwidth of the system is reduced even
more due to the exchange of routing information.
 links can be asymmetric, i.e., they can have a
direction dependent transmission quality.
Destination Sequence Distance Vector
(DSDV)
Destination sequence distance vector routing is an
enhancement to distance vector routing for ad hoc
networks.
Distance vector routing is used as RIP in wired
networks.
It performs extremely poorly with certain network
changes due to the count-to-infinity problem.
Each node exchanges its neighbor table
periodically with its neighbors.
Destination Sequence Distance Vector
The strategies to avoid this problem which are
used in fixed network do not help in the case of
wireless ad hoc networks, due to the rapidly
changing topology.
Effects might be the creation of loops or
unreachable regions within the network.
Destination Sequence Distance Vector
DSDV now adds two things to the distance vector
algorithm:
Sequence numbers:
Each rouging advertisement comes with a sequence number.
Within ad hoc networks advertisements may propagate
along many paths.
Sequence numbers help to apply the advertisements in
correct order.
This avoids loops that are likely with the unchanged
distance vector algorithm.
Destination Sequence Distance Vector
Damping:
Transient changes in topology that are of short
duration should not destabilize the routing
mechanisms.
Advertisements containing changes in the
topology currently stored are therefore not
disseminated further.
A node waits with dissemination if these changes
are most likely not yet stable.
Waiting time depends on the time between the
first and the best announcement of a path to a
certain destination.
Destination Sequence Distance Vector
The routing table for N1 in routing topic slide
figure as shown in table.
Destination
N1
Next Hop
N1
Metric
0
N2
N2
1
N3
N2
2
N4
N4
1
N5
N4
2
Fig: Part of a routing table for DSDV
Dynamic Source Routing
Imagine what happens in an ad hoc network
where nodes exchange packets from time to
time i.e. the network is only lightly loaded,
and DSDV or one of the traditional distance
vector or link state algorithms is used for
updating routing tables.
Although only some user data has to be
transmitted the nodes exchange routing
information to keep track of the topology.
Dynamic Source Routing
These algorithms maintain routes between all
nodes, although may be there is currently nod
data exchange at all.
This causes unnecessary traffic and prevents
nodes from saving battery power.
Dynamic Source Routing
Dynamic source routing therefore divides the task
of routing into two separate problems.
Route Discovery:
A node only tries to discover a route to a
destination if it has to send something to this
destination and there is currently no known route.
Dynamic Source Routing
Route Maintenance:
If a node is continuously sending packets via a
route, it has to make sure that the route is held
upright.
As soon as a node detects problems with the
current route, it has to find an alternative route.
Dynamic Source Routing
The basic principle of source routing is also used
in fixed networks, e.g. token rings.
Dynamic source routing eliminates all periodic
routing updates and works as follows.
If a node needs to discover a route, if broadcast a
route request with a unique identifier and the
destination address as parameters.
Dynamic Source Routing
Any node that receives a rout request does the
following:
 if the station is the receiver (i.e., has the
correct destination address) then return the
packet to the sender (path was collected in
the packet).
 if the packet has already been received
earlier (identified via ID) then discard the
packet.
 otherwise, append own address and
broadcast packet.
DSR: Route Discovery
Sending from C to O
P
C
B
R
Q
G
I
E
M
K
A
O
H
L
D
F
J
N
DSR: Route Discovery
Broadcast
P
R
[O,C,4711]
C
B
Q
G
[O,C,4711]
I
E
M
K
A
O
H
L
D
F
J
N
DSR: Route Discovery
P
R
[O,C/G,4711]
C
G
[O,C/B,4711]
B
[O,C/G,4711]
Q
I
E
M
K
A
O
[O,C/E,4711] H
L
D
F
J
N
DSR: Route Discovery
P
C
B
R
Q
G
[O,C/G/I,4711]
I
E
M
K
A
H
[O,C/B/A,4711]
O
[O,C/E/H,4711]
L
D
F
[O,C/B/D,4711]
(alternatively: [O,C/E/D,4711])
J
N
DSR: Route Discovery
P
C
B
R
Q
G
[O,C/G/I/K,4711]
I
E
M
K
A
O
H
L
D
F
N
J
[O,C/E/H/J,4711]
[O,C/B/D/F,4711]
DSR: Route Discovery
P
C
B
R
Q
G
[O,C/G/I/K/M,4711]
I
E
M
K
A
O
H
L
D
F
N
J
[O,C/E/H/J/L,4711]
(alternatively: [O,C/G/I/K/L,4711])
DSR: Route Discovery
P
C
B
R
Q
G
I
E
M
K
A
O
H
L
D
F
J
N
[O,C/E/H/J/L/N,4711]
DSR: Route Discovery
P
C
B
R
Q
G
Path: M, K, I, G
I
E
M
K
A
O
H
L
D
F
J
N
Dynamic Source Routing

Maintaining paths
 after sending a packet
 wait for a layer 2 acknowledgement (if
applicable).
 listen into the medium to detect if other
stations forward the packet (if possible).
 request an explicit acknowledgement.
 if a station encounters problems it can inform
the sender of a packet or look-up a new path
locally.
Alternative Metrics
The examples shown in this chapter always use
the number of hops as routing metric.
Although very simple, especially in wireless ad
hoc network, this is not always the best choice.
Even for fixed networks, e.g bandwidth can also
be factor for the routing metric.
Due to the varying link quality and the fact that
different transmissions can interfere, other metrics
can be more useful.
Alternative Metrics
Routing based on assumptions about interference
between signals.

N1
N2
R1
S1
N3
N4
N5
N6
R2
S2
neighbors
(i.e. within radio range)
N7
N8
N9
Alternative Metrics



Examples for interference based routing
Least Interference Routing (LIR)
 calculate the cost of a path based on the number
of stations that can receive a transmission
Max-Min Residual Capacity Routing (MMRCR)
 calculate the cost of a path based on a
probability function of successful transmissions
and interference
Least Resistance Routing (LRR)
 calculate the cost of a path based on
interference, jamming and other transmissions
Alternative Metrics





LIR is very simple to implement, only information
from direct neighbors is necessary.
Previous slide figure shows an ad hoc network
topology.
Sender S1 wants to send a packet to receiver R1.
Using the hop count as metric, S1 could choose
three different paths with three hops which is also
the minimum.
Here mention the cost of each nodes:
S1=3,N1=3,N2=4,N3=6,N4=5,R1=2
Dynamic Source Routing
C1=cost(S1,N3,N4,R1)=16,
C2=cost(S1,N3,N2,R1)=15,
C3=cost(S1,N1,N2,R1)=12
All three paths have the same number of hops, but
the last path has the lowest cost due to
interference.
Thus S1 chooses (S1,N1,N2,R1).
Overview of ah-hoc Routing protocols:
Flat ad-hoc routing
Flat ad-hoc routing protocol comprise those
protocols that do not set up hierarchies with
clusters of nodes.
Special nodes acting as the head of a cluster or
different routing algorithms inside or outside
certain regions.
All nodes in this approach play an equal role in
routing.
The addressing scheme is flat.
Overview of ah-hoc Routing protocols:
Flat ad-hoc routing
This category again falls into subcategories:
Proactive protocols: it is set up tables required for
routing regardless of any traffic that would require
routing functionality. The following protocols
supported to this group:
Fisheye state routing & Fuzzy sighted link
state: They making the update period dependent
on the distance to a certain hop.
Overview of ah-hoc Routing protocols:
Flat ad-hoc routing
Topology broadcast based on reverse path
forwarding &Optimized link state routing:
They try to reduce the traffic caused by link
state information dissemination.
Overview of ah-hoc Routing protocols:
Flat ad-hoc routing
Advantages:
They can give QOS guarantees related to
connection set-up, latency or other real time
requirements.
Disadvantages:
Their overheads in lightly loaded networks.
Overview of ah-hoc Routing protocols:
Flat ad-hoc routing
Reactive protocols: It is try to avoid this problem
by setting up a path between sender and receiver
only if a communication is waiting. The following
protocols supported to this group:
Dynamic source routing (DSR) & ad-hoc ondemand distance vector (AODV): AODA
acquires and maintains routes only on demand
link DSR nodes.
Overview of ah-hoc Routing protocols:
Flat ad-hoc routing
Advantages:
A clear advantage of on-demand protocols is
scalability as long as there is only light traffic and
low mobility.
Disadvantages:
These protocols also exhibit disadvatages.
Overview of ah-hoc Routing protocols:
Hierarchical ad-hoc routing
Algorithms such as DSDV,AODV and DSR only
work for a smaller number of nodes and depend
heavily on the mobility of nodes.
For larger networks, clustering of nodes and using
different routing algorithms between and within
clusters can be a scalable and efficient solution.
The motivation behind this approach is the locality
property meaning that if a cluster can be
established nodes typically remain within a
cluster, only some change clusters.
Overview of ah-hoc Routing protocols:
Hierarchical ad-hoc routing
If the topology within a cluster changes, only
nodes of the cluster have to be informed.
Nodes of other clusters only need to know how to
reach the cluster.
Clusters can be combined to form super clusters
etc, building up a larger hierarchy.
Using this approach one or more nodes can act as
cluster heads, representing a router for all traffic
to/from the cluster.
Overview of ah-hoc Routing protocols:
Hierarchical ad-hoc routing
All nodes within the cluster and all other cluster
heads use these as gateway for the cluster.
Different routing protocols may be used inside and
outside clusters:
Cluster head-Gateway Switch routing (CGSR):
it is a typical representative of hierarchical routing
algorithm based on distance vector (DV) routing.
Hierarchical state routing: it is base on link-state
principle. This applies the principle of clustering
recursively, creating multiple levels of clusters
and cluster of clusters etc.
Overview of ah-hoc Routing protocols:
Hierarchical ad-hoc routing
Zone routing protocol (ZRP): it is a hybrid
hierarchical routing protocol. Each node using
ZRP has predefined zone with the node as the
center. The zone comprises all other nodes within
a certain hop-limit. Proactive routing is applied
within the zone while no-demand routing is used
outside the zone.
Overview of ah-hoc Routing protocols:
Geographic-position-assisted
ad-hoc routing
If mobile nodes know their geographical position
this can be used for routing purposes.
This improves the overall performance of routing
algorithms if geographical proximity also means
radio proximity.
The following protocols supported to Geographicposition-assisted:
GeoCast: It allows messages to be sent to all
nodes in a specific region. It is based on
geographic information instead of logical number.
Overview of ah-hoc Routing protocols:
Geographic-position-assisted
ad-hoc routing
Location-aided routing: this protocol is similar
to Dynamic source routing (DSR) but limits rout
discovery to certain geographical regions.
Greedy perimeter stateless routing: It is based
on location information. This used only the
location information of neighbors that are
exchanged via periodic beacon messages or via
piggybacking in data packets.