Transcript Example 4: Mobile Multicast (MoM) Protocol

Multi-Variate Analysis of Mobility
Models for Network Protocol
Performance Evaluation
Carey Williamson
Nayden Markatchev
{carey,nayden}@cpsc.ucalgary.ca
University of Calgary
Preamble and Motivation
• Consider mobile host movement in an
arbitrary internetwork
• Can disconnect from one network at any
time, move to another location, and
reconnect, while maintaining same identity
• See IETF Mobile IP
B
C
A
Example: Three different “home networks”, each with
their own (stationary) router or base station (A, B, C).
Small circles and triangles represent mobile hosts.
Triangles belong to multicast group G, while circles do not.
B
C
A
Observation 1: Mobile hosts can move anywhere anytime.
B
C
A
B
C
A
B
C
A
B
C
A
Mobile Host (MH) registers with Foreign Agent (FA) at the
visited network, and with its Home Agent (HA) as well
to enable packet forwarding (via tunneling).
Packet from
CH to MH
B
C
A
B
C
A
Packet from Packet from
CH to MH
HA to FA
Basics of IETF Mobile IP packet forwarding
B
C
A
Observation 2: Similar rules apply for mobile hosts
that are members of multicast groups.
B
C
A
B
C
A
Packet from
MS to G
B
C
A
B
C
A
Packet from
HA to FA
Packet from
MS to MH
Can be done using unicast “bidirectional tunneling”.
B
C
A
Observation 3: This can be inefficient if multiple group
members are away at the same location.
B
C
A
B
C
A
Packet from
MS to G
B
C
A
B
Packet from
HA to FA
Packet from
MS to MH2
C
A
Packet from
HA to FA
Packet from
MS to MH
B
C
A
Packet from
HA to FA
Packet from
MS to G
More efficient solution is to tunnel the multicast itself.
B
C
A
Observation 4: Inefficiency still exists if multiple HA’s
have group members away at the same location.
B
C
A
B
C
A
B
C
A
Packet from
MS to G
B
C
A
B
C
A
Packet from
HA to FA
Packet from
MS to G
This is called the “tunnel convergence problem”.
B
C
A
Packet from
HA to FA
Packet from
MS to G
The solution in the MoM (Mobile Multicast) protocol is to
select a Designated Multicast Service Provider (DMSP)
to forward multicast packets to G at a certain network.
Multicast group
DMSP (HA)
Mobile Host
Observation 5: The general
case can be very messy!
The performance of MoM
(or any other protocol)
depends on group size and
on MOBILITY PATTERNS.
Multi-Variate Analysis of Mobility
Models for Network Protocol
Performance Evaluation
Carey Williamson
Nayden Markatchev
{carey,nayden}@cpsc.ucalgary.ca
University of Calgary
Motivation
• The performance of a mobility support protocol
is highly sensitive to user mobility patterns.
• Very little is known about mobile user behaviors
in operational networks.
• Most simulation studies evaluating protocol
performance use simple models of user mobility.
(e.g., “random walk”)
Overview of this Research
• Proposes a more general suite of mobility models
• Models are classified along two orthogonal axes:
degree of correlation (I/C) and degree of skewness (U/N):
–
–
–
–
Independent Uniform (IU)
Independent Non-Uniform (IN)
Correlated Uniform (CU)
Correlated Non-Uniform (CN)
• Uses the MoM protocol as a case study for the models.
• Impacts of mobility model parameters assessed using the
Analysis of Variance (ANOVA) statistical technique.
Background and Related Work
• Mobile Computing and Mobile IP.
– IETF Mobile IP protocol
• Mobile Host (MH)
• Foreign Agent (FA)
• Home Agent (HA)
• The model works but multicast support is
inefficient. (tunnel convergence problem)
Therefore…
Background and Related Work(2)
• New protocols, such as the MoM (Mobile
Multicast) protocol, are proposed to deal
with this issue.
• MoM uses the Home Agent for delivery of
multicast datagrams to mobile users, and
achieves scalability through a Designated
Multicast Service Provider (DMSP) for
each multicast group on a foreign network.
Basic Mobility Model in MoM
New Mobility Models
• To broaden the range of mobility patterns considered,
we introduce two new model parameters
• Correlation
– The tendency for certain hosts to move in patterns
that are related either geographically (i.e., location) or
temporally (i.e., time).
• Skewness
– Some destinations are more popular than others.
• The combination of those two factors leads to four
different mobility models: CU, CN, IU, IN.
Mobility Model Parameters
• Homing Probability - HOMING_PROB (0.5)
• Mean Residency Time (60 time units) and Mean
Travel Time (6 time units).
• Skewness
– Degree of skewness – k >= 0.
• Correlation (i.e., follow the leader)
– FRACTION_FOLLOWERS (% of mobile hosts)
– FOLLOW_PROBABILITY (per-move by a follower)
Model Validation
Experimental Parameters
Experimental Design
• Simulations are used to assess the performance
impacts of multicast group size, network size,
number of mobile hosts, and host mobility model.
• Simulations run for 26,000 time units, of which
the first 6,000 time units are for warm up.
• Only one multicast group is simulated.
Performance Metrics
• DMSP forwarding overhead per HA.
• Number of DMSP handoffs.
• The average number of foreign networks
visited by mobile multicast group members
(per HA).
MoM Performance
MoM Performance (zoom)
Line A - Average number of group members away.
Line B - Average number of different foreign networks at
which the away group members reside.
Line C- DMSP forwarding overhead.
Impact of Mobility Model on
Number of Foreign LANs Visited
Analysis of Variance (ANOVA)
• ANOVA is a statistical technique to analyze multi-variate
data and figure out which factor is “most important”.
• The method separates the total variation of the
performance index into components associated with
possible source of variation.
• Tabular analysis: row effect vs. column effect.
• F-test values determine the level of factors influence.
• Multiple independent replications of experiments are used
to identify the interaction effects between different factors.
DMSP Overhead per HA
(3 replications)
10 LANS, 10 Hosts per LAN
Multicast group size = 100
Note: lower is better.
CN is best case.
IU is worst case.
ANOVA Results:
DMSP overhead per HA
•
•
•
•
Correlation factor - 67.0%
Skewness factor - 28.5%
Interaction - 2.25%
Error - 2.22%
DMSP Handoffs
(3 replications)
ANOVA Results:
DMSP Handoffs
Correlation factor - SSA/SST = 349,515/399,980 = 87.4%
Skewness factor - SSB/SST = 6.2%
Interaction - SS(A+B)/SST = 0.4%
Error - SSE/SST = 6.0%
The P value indicates the statistical significance of each value.
Average Foreign LANs Visited (per HA)
(3 replications)
ANOVA Results:
Foreign LANs Visited (per HA)
Number of Hosts per LAN - 58.0%
Number of LANs - 31.3%
Interaction - 10.7%
Error - 0.003%
Effect of Correlation Parameters
on LANs Visited (3 replications)
ANOVA Results:
Impact of Correlation Parameters
• FRACTION_FOLLOWERS accounts for
34.2% of the total variation.
• FOLLOW_PROBABILITY accounts for
35.9% of the total variation.
• Interaction effects account for 29.2%.
• Errors contribute 0.7%.
Effect of Skewness Parameters
on LANs Visited (3 replications)
ANOVA Results:
Effect of Skewness
• Correlation factor contributes 57.6% of the
total variation.
• Skewness contributes 33.9% of total
variation.
• The interaction effect accounts for 8.0%.
• The effect of errors is 0.6%.
Summary and Conclusions
• The proposed suite of models (IU, IN, CU, CN)
represents a broad set of possible behaviors for
mobile users.
• The choice of mobility model can have a
significant effect on protocol performance.
• The degree of correlation between mobile hosts
has a greater impact than the degree of skewness.
• For the MoM protocol, the Independent Uniform
(IU) model is actually the worst case stress test.
Future Work
• Extending the correlation models to include
dynamic multicast group membership.
• Applying our mobility models to routing in
ad hoc wireless networks
• Applying our mobility models to the
evaluation of the rekeying protocols for
secure multicast groups.