Transcript Wireless Routing Protocols

Wireless Routing
Protocols
Matt Cleveland
Mobile network types


Infrastructured network is a network, such as
this campus, with fixed and wired gateways
Ad-hoc network, has no fixed routers, all nodes
are capable of movement and all may function
as routers (emergency search and rescue
operations, conventions where people wish to
quickly share information, and data acquisition in
inhospitable terrain)
Ad-Hoc Network types

Table driven
Ad-Hoc Network types

On-demand
Table-Driven Protocols




Have consistent overview of the network
Table contains routing information to every other
node in the network
Typically broadcasts a specified beacon “hello”
to network at fixed intervals of time and updates
its connection table accordingly
Destination Sequence Distance Vector (DSDV),
Wireless Routing Protocol (WRP), and Clusterhead Gateway Switch Routing (CGSR) are
common protocols using this technique
Destination Sequence Distance
Vector (DSDV)
Routing table contains list to all available
destinations, number of hops required to
reach each destination, and the sequence
number (last updated)
 Periodically transmit updated table
information to neighboring machines, or in
the event of a change, do so as well

Destination Sequence Distance
Vector (DSDV)
Full dump – transmit entire contents of
routing table to neighbors
 Incremental update – transmits only
pertinent table updates to neighbors
 Full dump occur in rapidly-changing
network where incremental updates are
used in relatively stable networks to avoid
extra traffic

Wireless Routing Protocol (WRP)



Each node contains a Distance table, a Routing
table, a Link-Cost table, and a MessageRetransmission list
Distance table contains distance between the
node and a given node y from each of current
node’s neighbors
Routing table contains list of distances between
the node and a given node y from given node x,
along with the predecessors and successors of x
Wireless Routing Protocol (WRP)
Link-Cost table contains the cost of
connecting to each of the node’s
neighbors, along with information
regarding timeouts
 Message Retransmission List has
information regarding which nodes need to
be resent information (like stop-N-wait)

Clusterhead Gateway Switch
Routing (CGSR) protocol
Is based on the DSDV protocol
 Nodes are combined into clusters with a
specified cluster-head
 Nodes that lie in overlapping clusters are
designated as Gateway nodes

Clusterhead Gateway Switch
Routing (CGSR) diagram
Clusterhead Gateway Switch
Routing (CGSR)
Requested packets are transmitted to
cluster-head, then transmitted to the
gateway node
 Receiving end does this in reverse order
 Nodes contain table of paths to other
nodes on network using DSDV algorithm

Advantages of Table-Driven Protocol

Having up-to-date list of all possible
connections to devices on network
Disadvantages of Table-Driven Protocols
Continuous table updating may be
redundant and unnecessary (wastes CPU
and battery, which are extremely limited
commodities in a mobile device)
 Tables updating causes unnecessary
network overhead in many instances

On-Demand routing protocols
When path is needed to given source,
must wait until path is discovered
 AODV, DSR, and ABR are common
protocols using this strategy

Ad-Hoc On Demand Vector Routing
(AODV)
To find path to destination, source
broadcasts a request packet
 Packet is rebroadcast by neighbors and
neighbors’ neighbors until it either reaches
the destination or finds a node with recent
routing information regarding the
destination
 Request is returned, and each node in
path appends its routing information in the
request

Ad-Hoc On Demand Vector Routing
(AODV)
Dynamic Source Routing (DSR)
Nodes contain path routes in cache, which
are updated when new information is
discovered
 When a message is sent, a node checks
its cache to see if the destination is known,
if so, message is sent, otherwise a request
is broadcast to neighbors asking for path

Associativity-Based Routing (ABR)
Routes are selected based on degree of
association stability of given nodes.
 Nodes periodically generate beacons to
acknowledge is alive.
 Beacon is received and nodes are
updated with node’s information (degree of
association stability).

Associativity-Based Routing (ABR)

1.
Has three phases
Route Discovery –
Broadcasts query: sends request for path to
destination node, nodes with information
respond, appending their information
(associativity) on the query for a full path
b) The path to the destination with the best
associativity is chosen
a)
Associativity-Based Routing (ABR)
2.
Route reconstruction – prompted by moving or
new nodes, which causes change in
associativity
a)
b)
c)
d)
3.
Partial route discovery
Invalid route erasure
Valid route updates
New route discovery
Route Deletion – when a path is found to be no
longer valid, a route delete (RD) broadcast is
sent to other nodes so that they can update
their information
Advantages of On-Demand Protocols
Only have to determine routing path when
necessary
 Highly dynamic and adaptable, doesn’t
rely on a stable network

Disadvantages of On-Demand Protocols

Takes longer to discover routing path than
it does to look it up on an IP table
Bibliography

http://www.computingunplugged.com/issues/issue200407/00001326
001.html

http://citeseer.ist.psu.edu/cache/papers/cs/16265/http:zSzzSzusers.
ece.gatech.eduzSz~cktohzSzroyer-ck.pdf/royer99review.pdf

http://www.cse.ohio-state.edu/~jain/cis78899/ftp/adhoc_routing/index.html