Transcript Multicast Routing Algos

Multicast in Mobile
Ad-Hoc Networks
Routing and Reliability
Outline of the Talk
•
•
•
•
•
•
•
Characteristics of Ad-Hoc Networks
Issues in Multicast Routing
AODV
Tree-based Multicast Routing
MCEDAR
Reliability Issues
Our Work in Progress
Characteristics of Ad-Hoc Networks
• All mobile platforms(nodes) are capable of motion
• All the nodes have routing functionality. There is
no need for centralized infrastructure for
communication.
• Each node is equipped with wireless transmitters /
receivers
• The node may be directly connected to a fixed
network on a foreign subnet, or be connected via a
wireless link, dial-up line, etc.
Salient features of MANETS
• Dynamic Topologies : Nodes move arbitrarily, and
links can be uni as well as bidirectional.
• Bandwidth Constrained links : Significant lower
capacity of wireless links. Congestion is the norm
rather than the exception.
• Energy Constrained Operation : All the nodes rely
on some exhaustible source for their energy.
• Limited Physical Security : More prone to
spoofing, DoS attacks, eavesdropping, etc.
A Future Internetwork
Base Station
Fixed Network
Ad Hoc Network Switch
Mobile Host
Wired Link
Wireless Link
Ad Hoc Network
An Ad Hoc Network : Our View
• A Graph with ‘n’ nodes
• A node can move in any direction with any
speed
• Connectivity is defined on the basis of
power considerations and land features,
implies frequently changing connectivity,
neighborhood of the nodes in the graph.
Issues in Multicast Routing
• Information stored : We want to store as less state
as possible in the hosts.
• Messages Exchanged : Because the networks are
bandwidth constrained, we would like as less
exchange of state as possible between the nodes.
• Active Adaptability : We would like the nodes to
adapt themselves to mobility, power
considerations, environment, etc.
• Local Effect of Link Breakages
Multicast Routing Algorithms
Some of them :
 AODV (Ad Hoc On Demand Distance
Vector) Routing
 Tree – based Algorithms
 MCEDAR (Multicast Core-Extraction
Distributed Ad Hoc Routing)
AODV
• Initially developed as a reactive, unicast
routing protocol.
• Elegantly adapts to a Multicast routing
protocol.
• Based on building a Multicast Routing Tree
on demand.
• The current version assumes bidirectional
links.
AODV : Unicast Route Discovery
Source
• Source broadcasts route request.
(RREQ)
• Node can reply to RREQ :
 If it is destination
 It has a fresh route to destination
• Nodes create reverse route entry
• Record Source IP
address/Broadcast ID to prevent
multiple processing
Destination
Route Propagation
AODV : Forward Path Setup
• Destination or Intermediate
Node with route to
destination unicasts RREP
back to source.
• Nodes along path create
forward route to destination
• Source begins sending data
when it receives the first
RREP.
Source
Destination
AODV : Local Connectivity Management
• Nodes must periodically hear from their active
neighbors to know that they are still within range
• Every time it hears the broadcast, it updates the
lifetime
• If it does not broadcast within hello_interval, it
broadcasts a hello packet.
• Failure to hear from neighbor within
(1 + allowed_hello_loss)*hello_lifetime
indicates loss of link.
AODV : Multicast Overview
• Utilizes same RREQ/RREP message cycle
• Shared tree composed of group members and
connecting nodes is formed
• Dynamic Group Membership
• Group Leader :
• Maintains and distributes group sequence number
• Is not a central point of failure.
• Multicast Group Members are also routers of the
Multicast Tree.
AODV : Multicast Routing Tables
•
•
•
•
•
•
Multicast Group IP Address
Multicast Group Leader IP Address
Multicast Group Sequence Number
Hop Count to Multicast Leader
Next Hops
Lifetime
AODV : Multicast Route Discovery
• Source node sends RREQ
• Sets ‘J’ flag if joining
• If no reply recd try
rebroadcast RREQ
rreq_retries additional times
• If still no reply, then become
the group leader
• Nodes receiving RREQ set up
reverse route entries.
Source
Multicast Group Members
Multicast Tree Members
Non-Members
Multicast Group Leader
AODV : Route Reply Generation
• Only members of multicast tree
can respond to join request
• Any node with route to multicast
tree can reply to non-join request
• RREP generated and unicast back
to the source
• RREP has address of group
member and distance from
closest tree member
• Nodes forwarding RREP update
RT and MRT entries.
Source
Multicast Group Members
Multicast Tree Members
Non-Members
Multicast Group Leader
AODV : Route Activation
• Source waits rte_disc_tmo
• Notes route with largest seq#
and smallest hopcnt to nearest
tree member
• After rte_disc_tmo, unicast
MACT (Multicast Activation)
to selected next hop.
• Node receiving MACT
enables MRT entry for source
• Unicasts own MACT if not
member of tree.
Multicast Tree
Source
Multicast Group Members
Multicast Tree Members
Non-Members
Multicast Group Leader
AODV : Leaving the Group
• Node may revoke its member status at
any time
• Unicast MACT with ‘P’(prune) flag set
to next hop
• If node is a leaf and not a group member,
prunes self
AODV : Link Breakages
• Node downstream of the break initiates
repair
• Broadcast RREQ with Multicast Group hop
count field and small TTL
• Accept RREPs as before
AODV : Reconnecting Partitioned Trees
• New partition detected by differing Group Leader
Information
• Any member whose Group Leader has lower IP
address initiates repair
• Unicasts RREQ with ‘R’(Repair) flag set to the
other Group Leader
• The other Group Leader does not give permission
to any other node to initiate repair unless this fails.
Group Hello Messages
• First member of group becomes the Group Leader
• Maintains, disseminates the Group Sequence Number
• Broadcasts Group Hello every group_hello_interval
seconds
•
•
•
•
Multicast Group IP address
Multicast Group leader IP address
Current Group Sequence Number
Hopcount
• Used by multicast tree members to update current distance
to Group Leader
AODV : Simulation
• Used Glomosim
• Each node chooses destination, speed
• Carrier Sensing performed before every
transmission
• Simulated length of time : 300 seconds
• Data Rate : 1 Mbit/sec
• Data packet size : 64 bytes
• Transmission Radius : 10 m
AODV : Performance
Goodput Ratio as a
function of Speed
100
98
Multicast 85m x
85m
Multicast 50m x
50m
96
94
Unicast 50m x
50m
92
0.8
0.4
90
0
Goodput Ratio (%)
• 50m x 50m Multicast
slightly reduced
Goodput Ratio
• 85m x 85m Multicast
has high rate of group
merges and partitions.
Speed(m/s)
Multicast Routing Algorithms
Some of them :
 AODV (Ad Hoc On Demand Distance
Vector) Routing
 Tree – based Routing Algorithms
 MCEDAR (Multicast Core-Extraction
Distributed Ad Hoc Routing)
Per-Source Multicast
• A Proactive Protocol
• Extension of DVMRP for fixed networks
• DVMRP :
• Each sender selectively “floods” multicast packets
to all nodes within a specified range
• They use reverse shortest path forwarding scheme
• Periodically non-member leaf nodes and nodes
without any downstream members send prune
messages
• They become alive again after a timeout.
Per Source Multicast
Problems of DVMRP in Ad-Hoc Networks :
• Leaf Node Detection
• Flooding for Grafting/Pruning
• Reverse Path Forwarding does not work due
to mobility.
• Scalability ??? Very poor!!!
Shared Tree Multicast
•
•
•
•
•
Another Proactive Protocol
Based on the concept of a rendezvous point (RP)
Sender Messages send multicast packets to the RP.
Join requests are also sent to the RP
Multicast packets are forwarded to receiver
members along the multicast forwarding tree,
either in the unicast mode or multicast mode.
Multicast Routing Algorithms
Some of them :
 AODV (Ad Hoc On Demand Distance
Vector) Routing
 Tree – based Routing Algorithms
 MCEDAR (Multicast Core-Extraction
Distributed Ad Hoc Routing)
Ad-hoc routing using CEDAR
• Core: subset of nodes in network involved in route
computation and management, with tunnels
between them.
• Core Broadcast: an efficient broadcast mechanism
among core nodes using O(V) messages
• Increase/Decrease waves: the state propagation
mechanism in CEDAR
• Route Computation: approximation to shortest
widest path.
• Core
CEDAR components in
MCEDAR
– Only core nodes become part of the multicast mesh
• Core Broadcast
– for joining the multicast mesh
– for data forwarding on the mesh
M
M
Ad-hoc network
M
Core Graph
Multicast Mesh
(subgraph of Core)
MCEDAR Characteristics
• Robustness of a mesh
• Efficiency of a tree based forwarding
protocol.
• Involves only a subset of nodes (core nodes)
in multicast route management
• Independent of the underlying unicast
routing protocol.
MCEDAR - Two aspects
• Route Management
– the multicast infrastructure
– joins
– leaves
• Data forwarding
MCEDAR : The Multicast Infrastructure
• A mesh of core nodes
• A non-core node requests its dominator (a
core node in its one hop neighborhood)
to become a member on its behalf.
• Senders and receivers are not distinguished
• Has a robustness factor of R
MCEDAR : Joining a Group
• Joining core nodes send Join Request using Core
broadcast
• Members with a lesser JoinID reply with Join-ACK
• On the reverse (Join-ACK) path, each node accepts
upto R acks.
– Upto R paths to the mesh.
• Each member has a JoinID and non members have a
joinID of -INF
• Members (including intermediate core nodes), keep
track of parents and children
MCEDAR : Joins (contd.)
• Mesh is essentially a DAG where the JoinIDs
increase as we go down the DAG
• On accepting a Join-ACK
JoinID <- MAX(JoinID, ID in ACK + 1)
• MAX allows a node to distinguish between set
of ancestors and descendants
Illustration (R=2)
1
3
2
4
3
Join -INF
ACK
3
4
Join
ACK-INF
6
Join
-INF
ACK
4
Core node
5
Multicast member
Join
ACK-INF
5
6
New member
Multicast mesh link
MCEDAR : Leaving a Group
• A node can leave if
– A member becomes a non-core node, OR
– It has no members attached to it AND it does not
have any children
• Send a leave message to each of its parents
• Set JoinID to -INF
MCEDAR : Data Forwarding
• Forward data on all mesh links except on the
link from which it came from
• Core broadcast mechanism used for data
forwarding on the multicast mesh
– Use overheard RTS/CTS packets to optimize data
forwarding
MCEDAR : Link Failures/Partitions
• A member does a new join only if it loses
connection with all parents
• Only members of lesser JoinID respond
– avoids joining back with the descendants
– if no response for time Tpartition then a partition is
assumed.
Conclusions
• MCEDAR
– Provides robustness of a mesh based mechanism.
– Provides efficiency of a tree based forwarding
protocol.
– Involves only few nodes in multicast route
management.
• No results available yet, so cannot predict
performance.
Multicast Routing : Our Views
• The Tree based Algorithms are :
• Too costly w.r.t. messages exchanged
• Shared Tree depends on the correct functioning of a
single node
• Both these algorithms are not at all scalable
• Hence neither algorithm is useful.
Multicast Routing : Our Views
• AODV has :
• Less overhead because it is a reactive protocol
• Not as good as it can be, because again most of the
traffic is directed towards the Multicast Group
Leader
• Another improvement could be to incorporate a
mesh-like routing infrastructure
• The results of AODV do not give any result
on scalability.
Multicast Routing : Our Views
• MCEDAR, we believe :
• Is good in that it has distributed computation.
• But again, your performance depends on the
performance of your core nodes, is that acceptable??
• Shouldn’t power awareness be a feature of routing
protocols too??
• Is it necessary to have some central control for good
performance??
Reliability
Different Aspects
• QoS guarantees
• Eventual Delivery
• Consistency Properties
• All group members deliver all the messages
with a high probability
Reliability : Previous Work
• Pagani et al. in 1997
• Reliable Multicast :
• Validity and Agreement : at least once delivery
• Integrity : Message m is delivered only if m has been
multicast by a group member
• Termination : Integrity, validity and termination are
guaranteed for m within a finite time
Reliability : Pagani et al
• These guarantees hold only as long as there
is :
• Eventual Subsidence : For each m, eventually no
more messages are generated regarding m
• Liveness : Each mobile is connected for at least a
given time to its clusterhead
• Clusterhead Stability : A node chosen as the
clusterhead remains as one for at least a given
duration.
Reliability : Pagani et al
Drawbacks :
• No performance results were given
• Is dependent on the underlying multicast protocol
• Based on ack-mechanism, so scalability is an
issue, since much more failures
• The conditions are difficult to maintain in the
mobile environment
• Can we really provide strong guarantees ??
Reliability : Previous work
• Viswanath et al, 1999
• Reliability
• Robustness and efficiency specifically for high
speed ad hoc networks
• No preset speed constraints
• No direction constraints
• Environment has high mobility and frequent outages
Reliability : Viswanath et al
• Adaptive Flooding as their technique
• Routes stored as states become stale soon
• So resort to techniques where minimum state
stored in the routers
• Simulation Environment :
• 50 nodes places in a 1000m x 1000m field
• Each node sends 25 packets/sec
• Packet Loss : ratio of unique packets not sent to
packets sent
• Overhead : Number of duplicate packets received
Reliability : Viswanath et al
Reliability : Viswanath et al
Reliability : Our views
• Flooding is valid only for very high speed
AHNs
• Pagani’s work requires too many
restrictions to hold
• Can we have probabilistic guarantees of
delivery ??
Reliability : Our Work in Progress
• We are designing a gossip protocol on top
of AODV
• Our protocol does not add any significant
overhead to AODV, in messages and even
the algorithm.
• How will this effect performance and
reliability??? Simulations going on!!
Future Work
• Develop Power Aware Algorithms..
• Have a theoretical model for our
environment, and prove its properties
• How do these algorithms perform in
reality??
• In what environment will these mobiles
operate?? Are the current algorithms suited
for it??
Questions ??