Mobile Computing
Unit IV – Network Layer
ROUTING
Routing is the act of moving information across the network
from a source to a destination. It is also referred as the process of choosing
a path over which the packets are sent. The routing process usually directs
forwarding on the basis of routing tables which maintain a record of the routes
to various network destinations.
At least one intermediate
node within the internetwork is encountered
during the transfer of information.
Basically two activities are involved in this concept: determining optimal routing
paths and transferring the packets through an internetwork. The
transferring
of packets through an
internetwork is called as
packet switching which
is straight forward,
and the path determination could be very complex.
Routing protocols
use several metrics as a standard measurement to calculate the best
path for routing the packets to its destination that could be : number of hops,
which are used by the routing
algorithm to determine
the optimal
path for the packet to its
destination. The process of path determination is that,
routing algorithms find out and maintain routing tables, which contain the total route information for
the packet. The information of route varies from one routing algorithm to another. The routing tables are filled with entries in the routing table are
ip-address
prefix
and the next hop.
Routing is mainly classified into static routing and dynamic routing. 1. Static routing refers to the routing strategy being stated manually or statically, in the router. Static routing maintains a routing table usually written by a networks administrator. The routing
table doesn‘t depend on the state of the network status, i.e., whether the destination is active or not.
2. Dynamic routing refers
to the routing strategy that is being learnt
by
an interior or
exterior routing protocol. This routing primarily depends on the state of the network i.e.,
the routing table is affected by the activeness of the destination.
Routing in Mobile Ad-hoc Networks
Mobile Ad-hoc networks are
self-organizing and
self-configuring
multihop
wireless networks, where the structure of the network changes dynamically. This is mainly due to the mobility of the nodes. Nodes in these
networks utilize the same random access wireless channel, cooperating in an intimate manner to engaging themselves in multihop
forwarding. The node in the network not only acts as hosts but also as routers that route
data to / from
other
nodes
in
network.
In mobile
ad-hoc networks
there is no infrastructure support as is the case with wireless networks, and since a destination node might be out of range of a source node transferring packets; so there is need of a routing
procedure. This is always ready to find a path so as to forward the packets appropriately between the source and the destination.
In infrastructure networks, within a cell, a base station can reach all mobile nodes without routing via broadcast in common wireless networks. In the case of ad-hoc
networks, each node must be able to forward data for other nodes. This creates additional
problems along with the problems
of
dynamic topology
which is unpredictable connectivity changes.
Problems in routing with
Mobile Ad
hoc
Networks
i) Asymmetric links: Most of the wired networks rely on the symmetric links which are always fixed. But this is not a case with ad-hoc networks as the nodes are mobile
and
constantly changing their position
within network
ii) Routing
Overhead:
In wireless
ad hoc
networks, nodes
often
change their location within network. So, some stale
routes are generated in the routing table
which leads to unnecessary routing
overhead.
iii) Interference: This is the major problem with mobile ad-hoc networks as links come and
go depending on the transmission characteristics, one transmission
might interfere with another one and node might overhear transmissions of other
nodes and can corrupt
the total transmission.
iv) Dynamic Topology: Since the topology is not constant; so the mobile node might move or medium characteristics might change. In ad-hoc networks, routing tables
must somehow reflect these changes in topology and routing algorithms have to
be adapted. For example in a fixed network routing table updating takes place for
every 30sec.
This updating frequency might be very low for ad-hoc networks.
Classification of Routing Protocols
FSR
– Fish Eye State Routing ;FSLS –
Fuzzy Sighted Link state;
OLSR
– Optimized Link State Routing; DSR
– Dynamic Source Routing
TBRPF –
Topology broadcast based on Reverse – Path Forwarding
AODV
– Ad hoc On Demand Distance Vector; HSR
– Hierarchical State Routing
CGSR
– Cluster Gateway Switch Rouing; ZRP
– Zone Routing Protocol
LANMAR
– Landmark Ad hoc Routing; GeoCast –
Geographic Addressing and Routing
LAR
– Location Aided Routing Protocol; GPSR
– Greedy Perimeter Stateless Routing
DREAM
– Distance Routing Effect Algorithm for mobility
DESTINATION
SEQUENCED DISTANCE VECTOR (DSDV)
DSDV was one of the first
proactive routing protocols available for Ad Hoc networks. It was developed by
C. Perkins in 1994, 5 years before the informational RFC of the MANET group. It
has not been standardised by any regulation authorities but is still a
reference.
Algorithm
·
DSDV
is based on the Bellman-Ford algorithm.
·
With
DSDV, each routing table will contain all available destinations, with the
associated next hop, the associated metric (numbers of hops), and a sequence
number originated by the destination node.
·
Tables are updated in the topology per exchange
between nodes.
·
Each node will broadcast to its neighbors entries
in its table. This exchange of entries can be made by dumping the whole routing
table, or by performing an incremental update, that means exchanging just
recently updated routes.
·
Nodes who receive this data can then update their
tables if they received a better route, or a new one.
·
Updates are performed on a regular basis, and are
instantly scheduled if a new event is detected in the topology.
·
If there are frequent changes in topology, full
table exchange will be preferred whereas in a stable topology, incremental
updates will cause less traffic.
·
The route selection is performed on the metric
and sequence number criteria. The sequence number is a time indication sent by
the destination node. It allows the table update process, as if two identical
routes are known, the one with the best sequence number is kept and used, while
the other is destroyed (considered as a stale entry).
Illustration
Let
us consider the two following topologies (figure 1 and figure 2). At t=0, the
network is organized as shows figure 1. We suppose at this time the network is
stable, each node has a correct routing table of all destinations.
fig 1
fig 7.2
At
this stage, the following events are detected, and actions are taken:
·
On
node C: Link with G is broken, the route entry is deleted, and updates are sent
to node D.
·
On
node A and F: A new link is detected, the new entry is added to the routing
table and updates are sent to neighbors.
·
On
node G: Two new links are detected (to A and F), and one is broken (to C), the
routing table is updated and a full dump is sent to neighbors (as the routing
table is entirely changed, a full dump equals an incremental update).
Advantages
·
DSDV was one of the early algorithms available. It is
quite suitable for creating ad hoc networks with small number of nodes. Since
no formal specification of this algorithm is present there is no commercial
implementation of this algorithm.
·
DSDV guarantees for loop free path.
Disadvantages
·
DSDV requires a regular update of its routing tables,
which uses up battery power and a small amount of bandwidth even when the
network is idle.
·
Whenever the topology of the network changes, a new
sequence number is necessary before the network re-converges; thus, DSDV is not
suitable for highly dynamic networks.
DYNAMIC SOURCE ROUTING (DSR)
·
The Dynamic Source Routing protocol (DSR) is a
simple and efficient routing protocol designed specifically for use in
multi-hop wireless ad hoc networks of mobile nodes.
·
DSR allows the network to be completely
self-organizing and self-configuring, without the need for any existing network
infrastructure or administration.
·
It is a reactive protocol and all aspects of the
protocol operate entirely on-demand basis.
·
It works on the concept of source routing.
Source routing is a routing technique in which the sender of a packet
determines the complete sequence of nodes through which, the packets are
forwarded.
·
The advantage of source routing is :
intermediate nodes do not need to maintain up to date routing information in
order to route the packets they forward.
·
The protocol is composed of the two main
mechanisms of "Route Discovery" and "Route Maintenance".
·
DSR requires each node to maintain a route –
cache of all known self – to – destination pairs. If a node has a packet to
send, it attempts to use this cache to deliver the packet.
·
If the destination does not exist in the cache,
then a route discovery phase is initiated to discover a route to destination,
by sending a route request.
·
This request includes the destination address,
source address and a unique identification number.
·
If a route is available from the route – cache,
but is not valid any more, a route maintenance procedure may be initiated.
·
A node processes the route request packet only
if it has not previously processes the packet and its address is not present in
the route cache.
·
A route reply is generated by the destination or
by any of the intermediate nodes when it knows about how to reach the
destination.
Example
In the following example, the route discovery procedure is
shown where S1 is the source node and S7 is the destination node.
Advantages and Disadvantages:
DSR uses a reactive
approach which
eliminates
the
need
to
periodically
flood
the
network with table update messages which are required in a table-driven approach. The intermediate nodes
also utilize the route cache information efficiently to
reduce the control overhead.
The disadvantage of DSR is that the route maintenance mechanism does not locally
repair a broken
down link. The connection setup delay is higher than in table-driven protocols. Even though
the
protocol
performs well in
static
and low-mobility environments,
the
performance degrades rapidly with
increasing mobility. Also,
considerable routing
overhead
is
involved
due
to
the source-routing
mechanism employed
in DSR. This routing overhead
is directly proportional to the path length.
AD
HOC ON-DEMAND DISTANCE VECTOR (AODV)
AODV was proposed to standardization
by the RFC 3561 in July 2003. It was designed by the same people who designed
DSDV. AODV is a distance vector routing protocol, which means routing decisions
will be taken depending on the number of hops to destination. A particularity
of this network is to support both multicast and unicast routing.
Algorithm
·
The
AODV algorithm is inspired from the Bellman-Ford algorithm like DSDV.
·
The
principle change is to be On Demand.
·
The
node will be silent while it does not have data to send. Then, if the upper
layer is requesting a route for a packet, a “ROUTE REQUEST” packet will be sent
to the direct neighbourhood. If a neighbour has a route corresponding to the
request, a packet “ROUTE REPLY” will be returned.
·
Otherwise,
each neighbour will forward the “ROUTE REQUEST” to their own neighbourhood,
except for the originator and increment the hop value in the packet data.
·
They
also use this packet for building a reverse route entry (to the originator).
This process occurs until a route has been found.
·
Another part of this algorithm is the route maintenance.
·
While
a neighbour is no longer available, if it was a hop for a route, this route is
not valid anymore.
·
AODV
uses “HELLO” packets on a regular basis to check if they are active neighbours.
Active neighbours are the ones used during a previous route discovery process.
If there is no response to the “HELLO” packet sent to a node, then, the
originator deletes all associated routes in its routing table. “HELLO” packets
are similar to ping requests. While transmitting, if a link is broken (a
station did not receive acknowledgment from the layer 2), a “ROUTE ERROR”
packet is unicast to all previous forwarders and to the sender of the packet.
Illustration
fig 1
In the example illustrated by
figure 1, A needs to send a packet to I. A “ROUTE REQUEST” packet will be
generated and sent to B and D (a). B and D add A in their routing table, as a
reverse route, and forward the “ROUTE REQUEST” packet to their neighbours (b).
B and D ignored the packet they exchanged each others (as duplicates). The
forwarding process continues while no route is known (c). Once I receives the
“ROUTE REQUEST” from G (d), it generates the “ROUTE REPLY” packet and sends it
to the node it received from. Duplicate packets continue to be ignored while
the “ROUTE REPLY” packet goes on the shortest way to A, using previously
established reverse routes (e and f).
The
reverse routes created by the other nodes that have not been used for the
“ROUTE REPLY” are deleted after a delay. G and D will add the route to I once
they receive the “ROUTE REPLY” packet.
Characteristics
of AODV
Ø Unicast,
Broadcast,
and Multicast communication.
Ø On-demand route establishment with small delay.
Ø
Multicast trees connecting group members maintained for lifetime of multicast
group.
Ø Link
breakages
in active routes efficiently repaired.
Ø All routes are loop-free through
use
of sequence numbers.
Ø Use
of Sequence numbers
to track accuracy of information.
Ø Only keeps track
of next hop for a route instead of the
entire route.
Ø Use
of periodic HELLO messages to track
neighbors.
Advantages and Disadvantages
The main advantage
of this protocol is that routes are established on demand and destination
sequence numbers are used to find the latest route to the destination. The
connection setup delay is lower.
One of the
disadvantages of this protocol is that intermediate nodes can lead to
inconsistent routes if the source sequence number is very old and the
intermediate nodes have a higher but not the latest destination sequence
number, thereby having stale entries. Also multiple RouteReply packets in
response to a single RouteRequest packet can lead to heavy control overhead.
Another disadvantage
of AODV is that the periodic beaconing leads to unnecessary bandwidth
consumption
ZONE
ROUTING PROTOCOL (ZRP)
- The
Zone Routing Protocol (ZRP) was introduced in 1997 by Haas and Pearlman.
- It
is either a proactive or reactive protocol. It is a hybrid routing protocol.
- It
combines the advantages from proactive and reactive routing.
- It
takes the advantage of pro-active discovery within a node's local
neighbourhood (Intrazone
Routing Protocol (IARP)), and using a reactive protocol for
communication between these neighbourhoods (Interzone
Routing Protocol(IERP)).
- The
Broadcast
Resolution Protocol (BRP) is responsible for the forwarding
of a route request.
- ZRP
divides its network in different zones.
- Each node may be within multiple
overlapping zones, and each zone may be of a different size.
- The
size of a zone is not determined by geographical measurement. It is given
by a radius of length, where the number of hops is the perimeter of the
zone. Each node has its own zone.
Example
- radius=2-Hop;
E, D, B, J, E and H are border-nodes
Illustration
- Before constructing a zone and
determine bordernodes , a node needs to know about its local neighbors.
- A node may use the media access
control (MAC) protocols to learn about its direct neighbors. It also may
require a Neighbor Discovery
Protocol (NDP).
- ZRP does not strictly specify the
protocol used but allows for local independent implementations.
- NDP relies on the transmission of hello
messages by each node.
- When the node, for example node A,
gets a response from a node B which has received the
"Hello"-messages, the node A notice that it has a direct
point-to-point connection with that node B.
- The NDP selects nodes on various criteria,
e.g.:
1.
signal
strength
2.
frequency/delay
of beacons.
- Once the local routing
information has been collected, the node periodically broadcasts discovery
messages in order to keep its map of neighbours up to date.
- Sometimes the MAC layer of the
nodes does not allow for such a NDP. Then the Intrazone Routing Protocol
must provide the possibility of direct neighbour discovery. This protocol
is responsible for determining the routes to the peripheral nodes and is
commonly a pro-active protocol.
Components of ZRP
- The Zone Routing Protocol consists of several
components, which only together provide the full routing benefit to ZRP
- Even though the hybrid nature
of the ZRP seems to indicate that it is a hierarchical protocol, it is
important to point out that the ZRP is in fact a flat protocol.
- ZRP is more efficiency for large networks
ZRP Components /
Architecture
Advantage
- Less
control overhead as in a proactive protocol or an on demand protocol
Disadvantages
- Short
latency for finding new routes
ON DEMAND MULTICAST ROUTING PROTOCOL (ODMR)
- On- Demand Multicast routing
protocol is a mesh architecture protocol, i.e, it has multiple paths from
the sender to the receivers and uses a forwarding group concept.
- It applies on-demand procedures to
dynamically build route and maintain multicast group membership.
- By maintaining a mesh instead of a
tree, the drawbacks of multicast trees in ad hoc networks like frequent
tree reconfiguration and non-shortest path in a shared tree are avoided.
- In ODMRP, group membership and
multicast routes are established by the source on
demand when a multicast source has
packets to send, but no route to the multicast group, it broadcasts a
Join-Query control packets to the entire network.
- This
control packet is periodically broadcast to refresh the membership information
and updates routes.
- When
the Join-Query packet reaches a multicast receiver, it creates and
broadcasts Join-Reply to its neighbours. When it has been received by the
node, it checks if the next hop own id.
- If
it is does, the node realizes that it is on the path to the source and
becomes the part of the forwarding group by setting the FG_FLAG
(Forwarding Group flag).
- When
receiving a multicast data packet, a node forwards it only when it is not
a duplicate, hence minimizing traffic overhead. Because the nodes maintain
soft state, finding the optimal flooding interval is critical to ODMRP performance.
- ODMRP
uses location and movement information to predict the duration of time
that routes will remain valid. With the predicted time of route disconnection,
a “join data” packet is flooded when route breaks of ongoing data sessions
are imminent.
- It
reveals that ODMRP is better suited for ad hoc networks in terms of
bandwidth utilization.
Example
Consider the source node ‘S’. It will flood the JOIN_DATA
packets to all other nodes in the
network. When a host node receives first JOIN_DATA packet it will
rebroadcast it to form a reverse path with the previous host. Each host in the
network acts as multicast receiver. It receives JOIN_DATA packet and replies in
turn with a JOIN_TABLE packet to the upstream to establish reverse paths.
The
process repeats until source host ‘S’ is reached. The method of packet
forwarding is for Figure (a) is shown in Figure (b). As the JOIN_TABLE is
received a host has to build a multicast table so as to facilitate future
packet forwarding. For example the host B receives the R1’s
JOIN_TABLE which is shown in the diagram.
It
will add R1 as its next hop step. Assume B receives R2’s
JOIN_TABLE. Now it will add R2 as its next hop step. A simple final
multicast table for each host is shown in the Figure (c) in propagation of data
packets.
Advantages
- Low channel and
storage overhead
- Usage of
up-to-date shortest routes
- Robustness to
host mobility
- Maintenance and
exploitation of multiple redundant paths
- Exploitation of
the broadcast nature of the wireless environment
- Unicast routing
capability
Disadvantages
No comments:
Post a Comment