Transcript 3-2-1_adhoc-multicas..

Outline
• Wireless introduction
• Wireless cellular (GSM, CDMA, UMTS)
• Wireless LANs, MAC layer
• Wireless Ad hoc networks
– routing: proactive routing, on-demand
routing, scalable routing, geo-routing
– wireless Ad hoc multicast
– TCP in ad hoc networks
– QoS, adaptive voice/video apps
• Sensor networks
Multicast ad hoc networks
• Multicast in ad hoc nets
– Review of Multicasting in wired networks
– Tree based wireless multicast
– Mesh based wireless multicast – ODMRP
– Performance comparison
• Scalable multicast
– M-LANMAR
– Backbone
• Reliable, congestion controlled multicast
– RALM, RALM with M-LANMAR
Wired IP Multicast is dead!
• Wired IP multicast is far from wide deployment
– Router upgrade, state scalability, access control,
pricing ...
– Data and non real time video multicast is now
being replaced by web downloading
• Internet “real time multicast” (eg, video
conference, games, etc) is using “overlays”
– Multicast routing and addressing managed by an
“overlay” at the application (ie, Host) level; Hosts
connected by virtual links (tunnels).
– Several “overlay” topology design schemes (eg.,
Narada, Nice, etc)
– Tools to “probe” the tunnels for capacity, delay,
loss etc ( Over-probe project at UCLA)
Wireless Multicast: very much alive!
• Multicast service critical in ad hoc nets:
– Video, voice multicast is critical in collaborative,
team oriented, ad hoc operations
– Multicast (data + streaming) is the prevalent
traffic in most ad hoc wireless network apps
(eg, search and rescue; disaster recovery, etc)
• Broadcast advantage of wireless over wire
• Can we use web download or application
“overlays”?
– Conventional web servers non practical,
vulnerable, non real time in wireless scenarios
– Application level overlays do not work well in ad
hoc networks: difficult to maintain in the face of
mobility
Per-Source Tree Multicast



Like DVMRP (Distance Vector Multicast Routing Protocol) and
PIM-DM (Protocol Independent Multicast - Dense Mode) in
wired net
S2
S1
Each source supports
own separate tree
“Probing and Pruning”
tree maintenance
R2


Reverse Path Forwarding
“Fast Source” problem
R1
RP-based Shared Tree Multicast
 RP (Rendezvous Point)
- based “Shared” tree
 Similar to wired network
RP
CBT (Core Based Tree),
S1
PIM-SM (Sparse Mode)
 Tree maintenance:
soft state
 “off-center” RP
 Longer paths than shortest path tree
Shared Tree vs. Per-source Tree
Shared Tree:
 scalability
R3
 less sensitive to
fast source
 longer path
S1
 off center RP
Per-Source Tree:
 shortest path
 traffic distribution
R1
 no central node
 scalability problem
 fast source problem
R2
RP
R4
S2
M-AODV: a shared tree multicast scheme
• M-AODV: Multicast AODV
• A shared tree, with common root, is shared
by all sources and receivers
• A designated node, or simply the first source
or receiver that initializes the tree, becomes
the root R, ie, the leader of group G
• Initialization: application at R requests to join
group G; M-AODV network layer at R floods a
Route Request
• If no response is received to several floods,
node R becomes the leader of group G
M-AODV (cont)
• Periodically, say every 5 sec, the root node R
floods a GROUP HELLO message to inform
the network of the presence of group G
• A new member wishing to join G unicasts a
JOIN REQUEST to root R; R returns a ROUTE
REPLY, setting up the “forwarding tables” a
la AODV along the path.
• In the M-AODV tree, each node keeps track of
upstream and downstream neighbors
• A data packet is forwarded to all neighbors
but the node from which the packet was
received (unicast or broadcast may be used)
M-AODV Maintenance
• Link health is monitored:
– By exchanging periodic HELLO’s with neighbors
– By overhearing neighbors
• If upstream link to root R is broken, a node
will use “expanding ring” search to reconnect
• If local reconnect does not work, the end
nodes (sources/receivers) must reconnect.
• Summary:
– M-AODV keeps forwarding state like AODV, but it
is receiver (instead of sender) oriented
– M-AODV requires periodic HELLO messages (why
did AODV could do without them?)
– Repair is more complex than AODV (entire subtree
below..)
Wireless Tree Multicast Limitations in High Mobility
RP
• In a mobile situation, tree is fragile:
connectivity loss, multipath fading
• Need to refresh paths very frequently
• High control traffic overhead
Solution: Forwarding Group Multicast
Forwarding Group
FG
FG
FG
FG
FG
• All the nodes inside the “bubble” forward the
multicast packets via “restricted” flooding
• Multicast Tree replaced by Multicast “Mesh”
• Flooding redundancy overcomes displacements
& fading
• Forwarding Group nodes selected by tracing
shortest paths between multicast members
ODMRP (On Demand Multicast
Routing Protocol)
•
•
•
•
Forwarding Group Multicast concept
Tree replaced by Mesh
On-demand approach
Soft state
Forwarding Group Concept
• A set of nodes in charge of forwarding multicast
packets
• Supports shortest paths between any member
pairs
• Flooding helps overcome displacements and
channel fading
Mesh vs Tree Forwarding
• Richer connectivity among multicast members
• Unlike trees, frequent reconfigurations are not
needed
FG Maintenance (On-Demand Approach)
• A sender periodically floods ctrl msg when it has
data to send
• All intermediate nodes set up route to sender
(backward pointer)
• Receivers update Member Tables; periodically
broadcast Join Tables
• Nodes on path to sources set FG_Flag; FG nodes
broadcast Join Tables
Soft State Approach
• No explicit messages required to join/leave
multicast group (or FG)
• An entry of a receiver’s Member Table
expires if no Join Request is received from
that sender entry during MEM_TIMEOUT
• Nodes in the forwarding group are demoted
to non-forwarding nodes if not refreshed (no
Join Tables received) within FG_TIMEOUT
A Performance Comparison Study of
Ad Hoc Wireless Multicast Protocols
S.J. Lee, W. Su, J. Hsu, M. Gerla, and R. Bagrodia
Wireless Adaptive Mobility Laboratory
University of California, Los Angeles
http://www.cs.ucla.edu/NRL/wireless
Goal
• Compare mesh- and tree-based multicast
protocols
– Mesh-based: ODMRP, CAMP, Flooding
– Tree-based: AMRoute, AMRIS
• Evaluate sensitivity to the following
parameters:
– Mobility (ie, speed)
– Number of multicast sources
– Multicast group size
– Network traffic load
Simulation Environment
•
•
•
•
•
•
•
•
Written in PARSEC within GloMoSim Library
50 nodes placed in 1000m X 1000m space
Free space channel propagation model
Radio with capture ability
Radio propagation range: 250 m
Bandwidth: 2 Mb/s
MAC: IEEE 802.11 DCF
Underlying unicast : Wing Routing Prot (for
AMRoute & CAMP)
• Multicast members and sources are chosen
randomly with uniform probabilities
• Random mobility
Packet Delivery Ratio as a Function of
Mobility Speed
• 20 members
• 5 sources each
send 2 pkt/sec
• Mesh protocols
outperform tree
protocols
• Multiple routes
help overcome
fading and node
displacements
Packet Delivery Ratio as a Function
of # of Sources
• 20 members
• 1 m/sec of
mobility speed
• Total traffic load
of 10 pkt/sec
• Increasing the
number of sender
makes mesh
richer for ODMRP
and CAMP
Packet Delivery Ratio as a Function of
Multicast Group Size
• 5 sources each
send 2 pkt/sec
• 1 m/sec of
mobility speed
• Flooding and
ODMRP not
affected by group
size
• CAMP builds
massive mesh
with growth of
the members
Packet Delivery Ratio as a Function of
Network Load
• 20 members
and 5 sources
• no mobility
• AMRIS is the
most sensitive
to traffic load
due to large
beacon
transmissions
• Why? Flooding
is so good
Control Bytes Txed/Data Byte Delivered as
a Function of Speed
• 20 members
• 5 sources each
send 2 pkt/sec
• Data packet
header included
in overhead
• No updates
triggered by
mobility in
ODMRP and
Flooding
• Why? Flooding is
so good
Control Bytes Txed/Data Byte Delivered as a
Function of Number of Sources
• 20 members
• 1 m/sec of
mobility speed
• Total traffic load
of 10 pkt/sec
• ODMRP’s
overhead grows
with the number
of sources
because of persource mesh
Conclusions
 Tree schemes:
 Too fragile to mobility
 lower throughput in heavy load
 lower control O/H
 Meshed Based scheme (CAMP):
 Better than tree schemes (mesh more robust)
 Mesh requires increasing maintenance with mobility
ODMRP:
most robust to mobility & lower O/H
 Lessons learned:
Mesh-based protocols outperform treebased protocols
Multiple routes help overcome node
displacements and fading