C08-mobile_routing.pdf

Network Protocols/ Mobile IP      

   

Motivation Data transfer Encapsulation Security IPv6 Problems Micro mobility support DHCP Ad-hoc networks Routing protocols

4/9/2018

8.1

Traditional Routing

A

routing protocol sets up a routing table in routers

 Routing

protocol is typically based on DistanceVector or Link-State algorithms

Routing and Mobility  Finding

 Issues 

a path from a source to a destination

Frequent route changes 

amount of data transferred between route changes may be much smaller than traditional networks

Route changes may be related to host movement  Low bandwidth links 



Goal of routing protocols

Decrease routing-related overhead  Find short routes  Find “stable” routes (despite mobility) 

Mobile IP Motivation (RFC 3220):  Traditional  

based on IP address; network prefix determines the subnet change of physical subnet implies  

change of IP address (conform to new subnet), or special routing table entries to forward packets to new subnet

 Changing   





entries in routing tables

does not scale with the number of mobile hosts and frequent changes in the location security problems

 Solution 

of IP address

DNS updates take to long time TCP connections break security problems

 Changing 

routing

requirements

retain same IP address, use same layer 2 protocols authentication of registration messages, …

8.5

Requirements to Mobile IP (RFC 3344, was: 3220, was: 2002) Transparency 

mobile end-systems keep IP address  Continuous service after link interruption  point of connection to the fixed network can be changed

Compatibility 

No changes to current hosts, OS, routers  mobile end-systems can communicate with fixed systems

Security 

authentication of all registration messages

Efficiency and scalability 

only few additional messages to mobile system (low bandwidth)  Global support for large number of mobile systems

4/9/2018

Mobile IP: Basic Idea S

MN

Home agent Router 1

Router 2

Router 3

Mobile IP: Basic Idea move Router 3

S

MN

Foreign agent Home agent Router 1

Router 2

Packets are tunneled using IP in IP

Question  How

does MN get access in the new network? (Foreign network) How does MN know about Foreign Agent?  (Advertisement)  How does MN ‘talk’ to the Foreign agent? 

 How

does MN inform the old network (home) of its new location? 

Registration with home agent through the foreign agent

 How

do the network and MN forward packets? (In each direction) 

Tunneling

8.9

4/9/2018

Terminology Mobile Node (MN) 

Laptop, PDA, etc.. that may move about

Home Agent (HA) 

Router in home network of the MN, helps in forwarding  registers current MN location, tunnels IP datagrams to COA

Foreign Agent (FA) 

Router in current foreign network of MN  forwards tunneled datagrams to the MN

Care-of Address (COA) 

address of the current tunnel end-point for the MN (at FA or MN)  can be chosen, e.g., via DHCP

Correspondent Node (CN) 

Node that wants to communicate with MN

Example network

8.10

4/9/2018

HA MN

router

mobile end-system

home network

Internet (physical home network for the MN)

FA

foreign network

router (current physical network for the MN)

CN end-system

router

Data transfer to the mobile system HA

2

MN

home network

3

receiver

Internet

FA

1

CN sender

foreign network

1. Sender sends to the IP address of MN, HA intercepts packet (proxy ARP) 2. HA tunnels packet to COA, here FA, by encapsulation 3. FA forwards the packetIITto the MN Bombay

Data transfer from the mobile system HA 1

home network

MN

sender Internet

FA

foreign network

1. Sender sends to the IP address of the receiver as usual, FA works as default router

CN receiver

Source: Schiller

Example There are two mobile hosts -> MH1 & MH2 And their Home Agents -> HA1 & HA2 MH1 is in its Home Network MH2 is in a Foreign Networks Suppose:  MH1 initiates data transfer with MH2. What is the path of the packets?  MH1 now moves to a Foreign network

Example (continued)

Encapsulation 10.100.5.2

10.8.13.5

Decapsulation 10.100.5.2

10.8.13.5

8.16

Example (continued)

4/9/2018

8.19

4/9/2018

Network integration Agent Advertisement 

HA and FA periodically send advertisement messages into their subnets



MN reads a COA from the FA advertisement messages

Registration (always limited lifetime!) 

MN signals COA to the HA via the FA, HA acknowledges



Messeges need to be secured by authentication

Advertisement  

HA advertises the MN IP address (as for fixed systems)

routers adjust their entries, (HA responsible for a long time)  All packets to MN are sent to HA

8.20

4/9/2018

Agent advertisement packet (RFC 1256 + mobility extension)

 B-

busy  H- home  F- foreign  M- minimal  G- generic

registration

set to zero ignored

Reverse tunneling

8.21

4/9/2018

Registration MN

FA

HA

MN

HA

t

MN has Co-located COA

t

MN has COA

8.22

Registration request S-HA to retain prior mobility bindings  B- MN to receive the broadcast packets from HA  D-decapsulation at tunnel endpoint  M-minimal  G- Generic  r- set to zero  T- reverse tunneling  x- set to zero 

4/9/2018

8.23

Registration reply

4/9/2018

8.24

4/9/2018

Tunneling and encapsulation A

tunnel establishes a virtual pipe for data packets between a tunnel entry and a tunnel endpoint.  Tunneling, i.e., sending a packet through a tunnel, is achieved by using encapsulation.  Encapsulation is the mechanism of taking a packet consisting of packet header and data and putting it into the data part of a new packet.  The reverse operation, taking a packet out of the data part of another packet, is called decapsulation.

8.25

Encapsulation original IP header

new IP header

outer header

original data

new data

inner header

original data

Encapsulation of one packet into another as payload 

e.g. IP-in-IP-encapsulation (mandatory, RFC 2003)  tunnel between HA and COA

4/9/2018

8.26

4/9/2018

IP-in-IP encapsulation Internet header length

Version Type of protocol

Inner header

complete encapsulated packet

8.27

4/9/2018

Minimal encapsulation  With

IP-in-IP encapsulation, several fields are

redundant (Not necessary).  An

optional encapsulation method for mobile

IP (Perkins, 1996c).  The

tunnel entry point and endpoint are

specified.

8.28

4/9/2018

Minimal encapsulation Internet header length

Version Type of protocol

Original sender address of CN

Inner header

complete encapsulated packet

4/9/2018

Generic routing encapsulation  Encapsulation

of packets of one protocol suite into the payload portion of a packet of another protocol suite (Hanks, 1994).  Packet of one protocol suite with the original packet header and data is taken and a new GRE header is prepended.

8.30

Generic routing encapsulation Strict source routing Sequence no checksum Routing fields key

  

Rec- recursion control Rsv- reserved set to zero Ver- version set to zero generic

4/9/2018

8.31

4/9/2018

Optimization of packet forwarding Triangular Routing  For eg: Japanese and a German meet at a conference on Hawaii. 

sender sends all packets via HA to MN  Triangular routes longer, higher latency and network load

“Solutions” 

HA informs a sender about the location of MN  sender learns current location of MN  direct tunneling to this location 

big security problems!

Change of FA 

packets on-the-fly during the change can be lost  new FA informs old FA to avoid packet loss  old FA forwards remaining packets to new FA 

Update also enables old FA to release resources for MN 8.10

8.32

4/9/2018

Optimized mobile IP protocol  Binding

request: Node that wants to know the current location of an MN can send a binding request to the HA.  Binding update: This message sent by the HA to CNs reveals the current location of an MN (fixed IP and COA).  Binding acknowledgement: If requested, a node returns this acknowledgement after receiving a binding update message.  Binding warning: Node decapsulates a packet for an MN, but it is not the current FA for this MN, this node sends a binding warning.

8.33

Request

4/9/2018

8.34

4/9/2018

Reverse tunneling  MN

can directly send its packets to the CN. Problems  Firewalls:   

intranet must pass through the firewall. Home firewalls rejects packet from MN (unless reverse tunneling) MN can no longer send packets back to home network

 Multi-cast:  MN in a foreign network cannot transmit multi-cast packets in a way that they emanate from its home network without a reverse tunnel.  TTL:  Mobile IP is no longer transparent if a user has to adjust the TTL while moving.

8.35

Reverse tunneling

4/9/2018

 Reverse

tunneling now creates a triangular routing problem in the reverse direction.  All packets from an MN to a CN go through the HA.  Reverse tunneling also raises several security issues 

For eg: tunnels starting in the private network of a company and reaching out into the internet could be hijacked and abused for sending packets through a firewall.

8.36

4/9/2018

Mobile IP and IPv6 Mobile IP was developed for IPv4, but IPv6 simplifies the protocols 

security is integrated, not add-on, authentication of registration included  COA can be assigned via auto-configuration (DHCPv6 is one candidate)  every node has address autoconfiguration 

no need for a separate FA, all routers perform router advertisement  MN can signal a sender directly the COA, without HA 

„soft“ hand-over, i.e. without packet loss supported 

MN sends the new COA to its old router  old router encapsulates all packets for MN, forwards them to new COA 

authentication is always granted

8.37

4/9/2018

IP Micro-mobility support Micro-mobility support: 

Efficient local handover inside foreign domain without involving a home agent



Reduces control traffic on backbone



Especially needed for route optimization

Example approaches: 

Cellular IP  HAWAII  Hierarchical Mobile IP (HMIP)

8.38

4/9/2018

Cellular IP  Operation: 

„CIP Nodes“ maintain routing entries (soft state) for MNs

Multiple entries possible  Routing entries updated based on update packets sent by MN

Internet Mobile IP



 CIP



Gateway:



Mobile IP tunnel endpoint



Initial registration processing

Other micromobility protocols 

HAWAII  Hierarchical Mobile IPv6 (HMIPv6)

CIP Gateway data/control packets from MN 1

BS

MN1

BS

BS

MN2

packets from MN2 to MN 1

Cellular IP

8.39

4/9/2018

 Advantages: 

Manageability: Cellular IP is mostly self-configuring, and integration of the CIPGW into a firewall would facilitate administration of mobility-related functionality.

 Disadvantages:

Efficiency: Additional network load is induced by forwarding packets on multiple paths.  Transparency: Changes to MNs are required.  Security: Routing tables are changed based on messages sent by mobile nodes. 

8.40

Hawaii 

1. 2. 3.

4.

Handoff-Aware Wireless Access Internet Infrastructure A mobile node obtains a colocated COA Registers with the HA when moving to another cell inside the foreign domain, the MN sends a registration request to the new base station as to a foreign agent Base station intercepts the registration request and sends out a handoff update message, which reconfigures all routers on the paths from the old and new base station to the so-called crossover router

4/9/2018

8.41

4/9/2018

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. 

 Disadvantages

Security: There are no provisions regarding the setup of IPSec tunnels.  Implementation: No private address support is possible because of colocated COAs. 

8.42

4/9/2018

Hierarchical mobile IPv6 (HMIPv6) 







Mobility anchor point (MAP), which is responsible for a certain domain and acts as a local HA. MAP receives all packets on behalf of the MN, encapsulates and forwards to MN (link COA). MN stays within MAP, globally visible COA (regional COA, RCOA) does not change. MAP domain’s boundaries are defined by the access routers (AR)

8.43

 MAP

4/9/2018

assists with local handovers and maps RCOA to LCOA.  MNs register their RCOA with the HA using a binding update.  When a MN moves locally it must only register its new LCOA with its MAP. RCOA stays unchanged.  For smooth handovers: MN can send a binding update to its former MAP

8.44

4/9/2018

Hierarchical mobile IPv6 (HMIPv6)  Advantages

Security: MNs can have (limited) location privacy because LCOAs can be hidden.  Efficiency: Direct routing between CNs sharing the same link is possible 

 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 of service attacks. Additional security functions might be necessary in MAPs 

8.45

4/9/2018

DHCP: Dynamic Host Configuration Protocol Main idea: E.g WPI has pool of IP addresses it can “lease” to hosts for short term use, claim back when done 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

Client/Server-Model 

the client sends via a MAC broadcast a request to the DHCP serve r (might DHCPDISCOVER be via a DHCP relay) DHCPDISCOVER server

client

relay

client

8.46

4/9/2018

DHCP - protocol mechanisms server (selected) client initialization

server (not selected) determine the configuration

DHCPDISCOVER

DHCPDISCOVER

DHCPOFFER

DHCPOFFER

determine the configuration

collection of replies

time

selection of configuration DHCPREQUEST DHCPREQUEST (reject) (options)

confirmation of configuration

DHCPACK initialization completed release DHCPRELEASE

delete context

8.47

4/9/2018

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

Big security problems! 

no authentication of DHCP information specified

8.48

4/9/2018

Mobile ad hoc networks Standard Mobile IP needs an infrastructure 

Home Agent/Foreign Agent in the fixed network  DNS, routing etc. not designed for mobility

Sometimes there is no infrastructure! 

remote areas, ad-hoc meetings, disaster areas  cost can also be argument against infrastructure!

Main topic: routing 

no default router available  every node should be able to forward

A

B

C

8.49

Solution: Wireless ad-hoc networks Network without infrastructure 

Use components of participants for networking

Examples 

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, TETRA police network, car-to-car networks…

Internet: MANET (Mobile Ad-hoc Networking) group

4/9/2018

8.50

4/9/2018

Mobile ad hoc networks Instant infrastructure: Unplanned meetings, spontaneous interpersonal communications  Disaster relief: Infrastructures typically break down in disaster areas. Hurricanes cut phone and power lines, floods destroy base stations, fires burn servers.  Remote areas: sometimes too expensive to set up an infrastructure in sparsely populated areas. adhoc networks or satellite infrastructures can be a solution.  Effectiveness: cellular networks exist, but an application sends only a small status information every other minute, a cheaper ad-hoc packetoriented network might be a better solution. 

8.51

4/9/2018

Manet: Mobile Ad-hoc Networking Mobile Router Manet Mobile Devices Mobile IP, DHCP Fixed Network Router

End system

8.20

8.52

4/9/2018

Problem No. 1: Routing 

Device mobility and varying channel quality  Asymmetric connections possible  Redundant links  Interference 

Highly dynamic network topology N7

N6 N7

N1

N1

N2 N3 N4

N3

N2

N4

N5 time = t1

N5 time = t2

good link weak link

N6

8.53

4/9/2018

Traditional routing algorithms Distance Vector 

periodic exchange of cost to everyone else, with neighbors  selection of shortest path if several paths available

Link State 

periodic notification of all routers about the current cost to neighbors  routers get a complete picture of the network, run Djikstra’s algorithm

Example 

ARPA packet radio network (1973), DV-Routing  every 7.5s exchange of routing tables including link quality  Receive packets, update tables

8.54

Problems of traditional routing algorithms Dynamic of the topology 

frequent changes of connections, connection quality, participants

Limited performance of mobile systems 

Periodic routing table updates need energy, sleep modes difficult  limited bandwidth further reduced due to routing info exchange  links can be asymmetric, directional transmission quality

4/9/2018

8.55

4/9/2018

Routing in ad-hoc networks THE big topic in many research projects 

Far > 50 different proposals exist  The most simplest one: Flooding!

Reasons 

Classical approaches from fixed networks fail 



Fast link quality changes, slow convergence, large overhead

Highly dynamic, low bandwidth, low computing power

Metrics for routing 

Minimize 



Number of hops, loss rate, delay, congestion, interference …

Maximal 

Stability of logical network, battery run-time, time of connectivity …

DSDV Protocol  DSDV

is Proactive (Table Driven)

Each node maintains routing information for all known destinations  Routing information must be updated periodically  Traffic overhead even if there is no change in network topology  Maintains routes which are never used 

DSDV Protocol  Keep

the simplicity of Distance Vector  Guarantee Loop Freeness 

New Table Entry for Destination Sequence Number

 Allow  

fast reaction to topology changes

Make immediate route advertisement on significant changes in routing table but wait with advertising of unstable routes (damping fluctuations)

DSDV (Table Entries) Destination A B C D

Next A B B B

Metric 0 1 3 4

Seq. Nr A-550 B-102 C-588 D-312

Install Time 001000 001200 001200 001200

Stable Data Ptr_A Ptr_B Ptr_C Ptr_D



Sequence number originated from destination. Ensures loop freeness.



Install Time when entry was made (used to delete stale entries from table)



Stable Data Pointer to a table holding information on how stable a route is. Used to damp fluctuations in network.

DSDV (Route Advertisements)  Advertise

to each neighbor own routing information   

Destination Address Metric = Number of Hops to Destination Destination Sequence Number

 Rules  

to set sequence number information

On each advertisement increase own destination sequence number (use only even numbers) If a node is no more reachable (timeout) increase sequence number of this node by 1 (odd sequence number) and set metric = 

DSDV (Route Selection)  Update

information is compared to own routing table 



1. Select route with higher destination sequence number (This ensure to use always newest information from destination) 2. Select the route with better metric when sequence numbers are equal.

DSDV (Tables)

A

1

Dest. Next Metric Seq A A 0 A-550 B B 1 B-100 C B 3 C-586

B

2

Dest. Next Metric Seq A A 1 A-550 B B 0 B-100 C C 2 C-588

C Dest. Next Metric Seq. A B 1 A-550 B B 2 B-100 C C 0 C-588

DSDV (Route Advertisement) B increases Seq.Nr from 100 -> 102 B broadcasts routing information to Neighbors A, C including destination sequence numbers (A, 1, A-500) (B, 0, B-102) (C, 1, C-588)

A

1

Dest. Next Metric Seq A A 0 A-550 B B 1 B-102 C B 2 C-588

(A, 1, A-500) (B, 0, B-102) (C, 1, C-588)

B

1

Dest. Next Metric Seq A A 1 A-550 B B 0 B-102 C C 1 C-588

C Dest. Next Metric Seq. A B 2 A-550 B B 1 B-102 C C 0 C-588

DSDV (New Node) 2. Insert entry for D with sequence number D-000 Then immediately broadcast own table

1. D broadcast for first time Send Sequence number D000 (D, 0, D-000)

A Dest. Next Metric Seq. A A 0 A-550 B B 1 B-104 C B 2 C-590

B Dest. Next Metric Seq. A A 1 A-550 B B 0 B-104 C C 1 C-590

C Dest. Next Metric Seq. A B 2 A-550 B B 1 B-104 C C 0 C-590 D D 1 D-000

D

DSDV (New Node cont.) 3. C increases its sequence number to C-592 then broadcasts its new table.

4. B gets this new information and updates its table…….

(A, 2, A-550) (B, 1, B-102) (C, 0, C-592) (D, 1, D-000)

……… ………

A Dest. Next Metric Seq. A A 0 A-550 B B 1 B-104 C B 2 C-590

B Dest. Next Metric Seq. A A 1 A-550 B B 0 B-102 C C 1 C-592 D C 2 D-000

(A, 2, A-550) (B, 1, B-102) (C, 0, C-592) (D, 1, D-000)

C Dest. Next Metric Seq. A B 2 A-550 B B 1 B-102 C C 0 C-592 D D 1 D-000

D

DSDV (no loops, no count to infinity) 2. B does its broadcast -> no affect on C (C knows

that B has stale information because C has higher seq. number for destination D)

1. Node C detects broken Link: -> Increase Seq. Nr. by 1

-> no loop -> no count to infinity (D, 2, D-100)

A Dest. Next Metric Seq. … … … D B 3 D-100

(only case where not the destination sets the sequence number -> odd number)

(D, 2, D-100)

B Dest.c Next Metric Seq. … … … D C 2 D-100

C Dest. Next Metric Seq. … … … D D  D-101

D

DSDV (Immediate Advertisement) 3. Immediate propagation B to A:

2. Immediate propagation C to B:

(update information has higher Seq. Nr. -> replace table entry)

(update information has higher Seq. Nr. -> replace table entry)

(D, , D-101)

A

B



D-101

C

D

C

Dest.c Next Metric Seq. … … … ... 2 D C 3 D-100 D

(only case where not the destination sets the sequence number -> odd number)

(D, , D-101)

B

Dest. Next Metric Seq. … … … ... B 4 D-100 3 D D

1. Node C detects broken Link: -> Increase Seq. Nr. by 1



D-101

Dest. Next Metric Seq. … … … B D-100 1 D D D

D



D-101

DSDV (Problem of Fluctuations) What are Fluctuations A P

Q



Entry for D in A: [D, Q, 14, D-100]



D makes Broadcast with Seq. Nr. D-102 A receives from P Update (D, 15, D-102) -> Entry for D in A: [D, P, 15, D-102] A must propagate this route immediately. A receives from Q Update (D, 14, D-102) -> Entry for D in A: [D, Q, 14, D-102] A must propagate this route immediately.



11 Hops

10 Hops

(D,0,D-102) D



This can happen every time D or any other node does its broadcast and lead to unnecessary route advertisements in the network, so called fluctuations.

DSDV (Damping Fluctuations) How to damp fluctuations A P



Record last and avg. Settling Time of every Route in a separate table. (Stable Data) Settling Time = Time between arrival of first route and the best route with a given seq. nr.



A still must update his routing table on the first arrival of a route with a newer seq. nr., but he can wait to advertising it. Time to wait is proposed to be 2*(avg. Settling Time).



Like this fluctuations in larger networks can be damped to avoid unececarry adverdisment, thus saving bandwith.

Q

11 Hops

10 Hops

D

Summary Advantages

Simple (almost like Distance Vector)  Loop free through destination seq. numbers  No latency caused by route discovery 

Disadvantages

No sleeping nodes  Overhead: most routing information never used 

Dynamic Source Routing (DSR) [Johnson+ 1996]



When node S wants to send a packet to node D, but does not know a route to D, node S initiates a route discovery



Source node S floods Route Request (RREQ)



Each node appends own identifier when forwarding RREQ

© 2001 Nitin Vaidya

Route Discovery in DSR Y

Z S

E F

B

C

M

L

J A

G H

D K I

N

Represents a node that has received RREQ for D from S

© 2001 Nitin Vaidya

Route Discovery in DSR Y

Broadcast transmission [S] S

Z E F

B

C

M

L

J A

G H

D K I

N

Represents transmission of RREQ [X,Y]

Represents list of identifiers appended to RREQ © 2001 Nitin Vaidya

Route Discovery in DSR

Y

Z S

E

[S,E] F

B

C

M

L

J [S,C]

A

G

H

D K I

N

• Node H receives packet RREQ from two neighbors: potential for collision © 2001 Nitin Vaidya

Route Discovery in DSR

Y

Z S

E F

B

[S,E,F]

C

M

L

J A

G H

D I

[S,C,G] K

N

• Node C receives RREQ from G and H, but does not forward it again, because node C has already forwarded RREQ once © 2001 Nitin Vaidya

Route Discovery in DSR

Y

Z S

E [S,E,F,J]

F

B

C

M

L

J A

G H

D K I

[S,C,G,K]

N

• Nodes J and K both broadcast RREQ to node D • Since nodes J and K are hidden from each other, their transmissions may collide © 2001 Nitin Vaidya

Route Discovery in DSR

Y

Z S

E

[S,E,F,J,M]

F

B

C

M

L

J A

G H

D K I

N

• Node D does not forward RREQ, because node D is the intended target of the route discovery

© 2001 Nitin Vaidya

Route Discovery in DSR 

Destination D on receiving the first RREQ, sends a Route Reply (RREP)



RREP is sent on a route obtained by reversing the route appended to received RREQ



RREP includes the route from S to D on which RREQ was received by node D

© 2001 Nitin Vaidya

Route Reply in DSR

Y

Z S

E

RREP [S,E,F,J,D] F

B

C

M

L

J A

G H

D K I

N

Represents RREP control message

© 2001 Nitin Vaidya

Route Reply in DSR 

Route Reply can be sent by reversing the route in Route Request (RREQ) only if links are guaranteed to be bi-directional 



To ensure this, RREQ should be forwarded only if it received on a link that is known to be bidirectional

If unidirectional (asymmetric) links are allowed, then RREP may need a route discovery for S from node D

Unless node D already knows a route to node S  If a route discovery is initiated by D for a route to S, then the Route Reply is piggybacked on the Route Request from D. 



If IEEE 802.11 MAC is used to send data, then links have to be bidirectional (since Ack is used)

© 2001 Nitin Vaidya

Dynamic Source Routing (DSR) 

Node S on receiving RREP, caches the route included in the RREP



When node S sends a data packet to D, the entire route is included in the packet header 



hence the name source routing

Intermediate nodes use the source route included in a packet to determine to whom a packet should be forwarded

© 2001 Nitin Vaidya

Data Delivery in DSR

Y

DATA [S,E,F,J,D] S

Z

E F

B

C

M

L

J A

G H

D K I

N

Packet header size grows with route length

© 2001 Nitin Vaidya

When to Perform a Route Discovery  When

node S wants to send data to node D, but does not know a valid route node D

© 2001 Nitin Vaidya

DSR Optimization: Route Caching      

Each node caches a new route it learns by any means When node S finds route [S,E,F,J,D] to node D, node S also learns route [S,E,F] to node F When node K receives Route Request [S,C,G] destined for node, node K learns route [K,G,C,S] to node S When node F forwards Route Reply RREP [S,E,F,J,D], node F learns route [F,J,D] to node D When node E forwards Data [S,E,F,J,D] it learns route [E,F,J,D] to node D A node may also learn a route when it overhears Data packets

© 2001 Nitin Vaidya

Use of Route Caching 

When node S learns that a route to node D is broken, it uses another route from its local cache, if such a route to D exists in its cache. Otherwise, node S initiates route discovery by sending a route request



Node X on receiving a Route Request for some node D can send a Route Reply if node X knows a route to node D



Use of route cache  

can speed up route discovery can reduce propagation of route requests

© 2001 Nitin Vaidya

Use of Route Caching [S,E,F,J,D]

[E,F,J,D]

S

[F,J,D],[F,E,S]

E

F

B

[J,F,E,S]

C

M

L

J [C,S]

A

G

H

[G,C,S]

D K

I

N Z

[P,Q,R] Represents cached route at a node (DSR maintains the cached routes in a tree format) © 2001 Nitin Vaidya

Dynamic Source Routing: Advantages 

Routes maintained only between nodes who need to communicate 

reduces overhead of route maintenance



Route caching can further reduce route discovery overhead



A single route discovery may yield many routes to the destination, due to intermediate nodes replying from local caches

© 2001 Nitin Vaidya

Dynamic Source Routing: Disadvantages 

Packet header size grows with route length due to source routing



Flood of route requests may potentially reach all nodes in the network



Care must be taken to avoid collisions between route requests propagated by neighboring nodes 



insertion of random delays before forwarding RREQ

Increased contention if too many route replies come back due to nodes replying using their local cache  

Route Reply Storm problem Reply storm may be eased by preventing a node from sending RREP if it hears another RREP with a shorter route © 2001 Nitin Vaidya

Dynamic Source Routing: Disadvantages 

An intermediate node may send Route Reply using a stale cached route, thus polluting other caches



This problem can be eased if some mechanism to purge (potentially) invalid cached routes is incorporated.



For some proposals for cache invalidation, see [Hu+ 2000]  

Static timeouts Adaptive timeouts based on link stability

© 2001 Nitin Vaidya

Cluster Gateway Switch Routing (CGSR) –

Nodes are grouped into clusters with one clusterhead in charge of nodes in a cluster

–

Distributed clusterhead selection algorithm is used to elect clusterheads

–

This algorithm needs to be invoked when a clusterhead moves away

–

Least Cluster Change (LCC) algorithm is introduced to avoid re-invoking election algorithm when the cluster membership update occurs

–

LCC algorithm allows the invocation of election algorithm when two clusterhead come into contact or when a node no longer be able to attach to any clusterheads

–

Uses DSDV as an underlying routing scheme

–

The route traffic follows: Source  Clusterhead  Gateway  Clusterhead  …….. Destination

Cluster Gateway Switch Routing (CGSR)

Cluster

Clusterhead

Gateway

Ordinary node

Cluster Gateway Switch Routing (CGSR)

–

Each node keeps a cluster member table which stores the destination clusterhead for each node in the network

–

Every node periodically broadcasts these cluster member tables using DSDV protocol

–

Nodes update their cluster member tables upon receiving these broadcasts

–

Each node also maintains a routing table that is used to determine the next hop towards the destination

–

When a packet is received, the node checks both cluster member and routing tables to determine the nearest clusterhead in the route to the destination

–

The node checks its routing table to determine the next hop node to reach clusterhead

–

Both cluster member and routing tables need to be updated

8.100

4/9/2018

Examples for interference based routing Routing based on assumptions about interference between signals Examples  



Least Interference Routing (LIR) Max-Min Residual Capacity Routing (MMRCR) Least Resistance Routing (LRR)

8.101

4/9/2018

A plethora of ad hoc routing protocols Flat 

proactive  FSLS – Fuzzy Sighted Link State  FSR – Fisheye State Routing  OLSR – Optimised Link State Routing Protocol  TBRPF – Topology Broadcast Based on Reverse Path Forwarding



reactive  

AODV – Ad hoc On demand Distance Vector DSR – Dynamic Source Routing

Hierarchical    

CGSR – Clusterhead-Gateway Switch Routing HSR – Hierarchical State Routing LANMAR – Landmark Ad Hoc Routing ZRP – Zone Routing Protocol

Geographic position assisted 

  

DREAM – Distance Routing Effect Algorithm for Mobility GeoCast – Geographic Addressing and Routing GPSR – Greedy Perimeter Stateless Routing LAR – Location-Aided Routing

8.30