Exploring Mesh and Tree Based Multicast Routing Protocols for MANETs

Viswanath, Obraczka, and Tsudik

manet networking tree mesh routing multicast evaluation

@article{viswanath:ieee-mc2006,
  title={Exploring Mesh and Tree-Based Multicast Routing Protocols for {MANETs}},
  author={K. Viswanath and K. Obraczka and G. Tsudik},
  journal={{IEEE} Transactions on Mobile Computing},
  pages={28--42},
  year={2006},
  publisher={{IEEE} Computer Society}
}

Two basic dimensions of protocol design space

• Construction and maintenance mechanism, e.g. proactive vs reactive
• Network structure, e.g. tree vs mesh

Paper compares ODMRP (On Demand Multicast Routing Protocol) vs MAODV (Multicast Ad Hoc On-Demand Distance Vector), respectively representing mesh and tree approaches, and both reactive, vs flooding as a strawman

• Flooding has large overhead but best delivery rates
  • Caveat: Contention can cause it to backfire and suffer higher loss rates

Metrics used:

• Packet delivery ratio: Fraction of total number of packets received by all receivers over total number of packets transmitted times the number of receivers
• Routing overhead: Ratio of control bytes transmitted to number of data bytes received
• Group reliability: Ratio of number of packets received by each group member (100% delivery success) over the number of packets sent.

Scenario parameters:

• Mobility rates
• Number of receivers
• Number of senders
• Number of multicast groups
• Traffic load

Group reliability suffers greatly for all protocols as the number of senders increases

• As mobility starts increasing (velocity), performance gaps start increasing
  • ODMRP handles this better though due to its redundant routes, while MAODV's trees are continually breaking
  • MAODV starts with lowest routing overhead, but quickly picks up due to continual tree reconfigurations
• As traffic load, senders, or groups increases, flooding is worse and worse
  • Might be suitable for high reliability, low traffic groups for which it is not worth constructing and maintaining elaborate structures?

Paper discusses two variants on flooding:

• Scoped flooding, which tries to reduce redundant broadcasts
• Hyper flooding, which increases redundant broadcasts to increase reliability at cost of extra transmissions

Scoped flooding in this paper introduces a HELLO mechanism by which neighbors exchang neighbor lists

• Packets are not forwarded if recieved from a neighbor which has advertised a neighbor set subsuming the receiving node's neighbor set
• Some sloppyness introduced into subsumption check, e.g. an 85% overlap is considered sufficient
• Similar notions here as MPRs in SMF, OLSR

Hyper flooding introduced more redundant broadcasts in order to increase reliability

• Generates HELLO messages and keeps track of neighbors
• Data packets are stored in a local cache
• When a node receives data or HELLO messages from a previously unknown neighbor, the receiving node rebroadcasts its entire cash
• Nodes periodically purge cache (note: says cache is purged, not that messages time out...)
• In dense cases hyper flooding may be counter productive, causing many collisions and reduced reliability

Basic emergency scenario included in addition to random walking

• 2km^2 field, 75 nodes broken into several teams
  • Two helicopters moving at 0--50m/s by random waypoint
  • Vehicle team of 25 nodes moving at 5--15m/s
  • Vehicle team of 8 nodes moving at 5--15m/s
  • Team of ground personnel moving at 0--5m/s, pause times of 0--2s
• All teams cover well defined areas, with overlap to ensure connectivity
  • This causes some issues for protocols, as nodes are put into forwarding group or multicast tree while they are in overlap areas, and then move out of contact with the other team
• Both helicopters and 20 random nodes act as data sources
• Doesn't state who is receiving the data...

Hybrid proactive/reactive approaches may make a lot of sense in mixed network settings, e.g. where nodes need to maintain knowledge of a gateway to a fixed network

Conclusions

• All protocols studied degrade in packet delivery and group reliability as mobility and load increases
• Mesh based protocols (flood, ODMRP) fare better than tree based protocols (MAODV)
• Flooding is most reliable...
• MAODV has the least overhead
• Hyper flooding is most reliably in cases with high mobility, but has larger overhead
• No one routing protocol is likely to work best in all cases
  • Need to develop adaptive, integrated sysetm comprised of many protocols and the means to switch between them, both on the network and on the hosts

To follow up on:

• Zone Routing Protocol
• Lee, Su, Hsu, Gerla, Bagroda. "A Performance comparision study of ad hoc wireless multicast protocols." IEEE Infocom 2000.
  • Compared to this paper, looks at "lower mobility and traffic load scenarios and involving smaller sets of traffic sources."
• Yoon, Liu, Noble. "Random waypoint considered harmful." IEEE Infocom 2003.