Transcript Systems Optimization in Mobility Management

Systems Optimization for Mobility
Management
Ashutosh Dutta
Electrical Engineering Department
Columbia University
March xx, 2010
Outline
•
•
•
•
•
Motivation
Vision
Key Contributions
Sample results
Conclusions and Future work
Motivation
• Cellular mobility typically involves handoff across
homogeneous access technology
– Optimization techniques are carefully engineered to improve
the handoff performance
• IP-based mobility involves movement across access
technologies, administrative domains, at multiple
layers and involve interaction between multiple
protocols
– Mechanisms and design principles for optimized handover
are poorly understood
– Currently there are ad hoc solutions for IP mobility
optimization, not engineering practice
– No formal methodology to systematically discover or
evaluate mobility optimizations
– No methodology for systematic evaluation or prediction of
"run-time" cost/benefit tradeoffs
Mobility Illustration in IP-based 4G network
Administrative
Domain A
Administrative
Domain B
Authorization
Agent
Registration
Agent
Authorization
Agent
Authentication
Agent
Authentication
Agent
Configuration
Agent
Signaling
Proxy
N1
Registration
Agent
Configuration
Agent
N2
N1
Backbone
IPch
Signaling
Proxy
L3 PoA
Corresponding
Host
L2 PoA
207.3.232.10
A
L2 PoA
L3 PoA
L3 PoA
L2 PoA
N2
128.59.11.8
L2 PoA
B
C
D
L3 PoA
128.59.10.7
Mobile
Host
N1- Network 1 (802.11)
N2- Network 2 ( CDMA/GPRS)
L2 PoA
207.3.232.10
L2 PoA
802.11
802.11
207.3.240.10
128.59.9.6
802.11
Handoff Delay
~ 18 s
CDMA
18 Seconds media interruption
802.11
802.11
4 Seconds media interruption
900 ms
media interruption
What is the vision?
• IP-based mobility needs to provide handoff
performance comparable to cellular mobility
• In order to transition ad hoc optimization
approaches to engineering best practice we need
the following:
– Framework or model that can analyze the mobility event
in a systematic way, can verify and predict the
performance under systems resource constraints
– A set of fundamental design principles to optimize
handoff components across layers
– A set of well defined methodologies to verify the
optimization techniques for mobility in an IP-based
network
My Key Contribution
1.
2.
3.
4.
Identification of the fundamental properties that are rebound
during handover event and systematic analysis of the
operations that are intrinsic to handover
Modeling of the handover process that allows performance
predictions to be made for both an un-optimized handover
and for specific optimization methodologies under systems
resource constraints and data dependency
Development of series of optimization techniques based on
fundamental rules of optimization that could be applied to link,
network, and application layers and preserve the user
experience by optimizing the handover related delay and
packet loss
Proof-of-concept of these handoff optimization techniques by
building experimental systems and comparing these results
with model-based prediction
Systems analysis of handoff
components
System decomposition of handover process
Mobility
Event
P1
P2
Network
discovery &
selection
P11
Channel
discovery
P13
P3
Network
attachment
P12
Subnet
discovery
P21
L2
association
Server
discovery
P4
Configuration
P5
Security
association
P6
Media
reroute
Binding
update
P31
Identifier
acquisition
P23
Domain
advertisement
P22
Router
solicitation
P33
Address
Resolution
P32
Duplicate
Address
Detection
P41
Authentication
P53
Identifier
mapping
P42
Key
derivation
P51
Identifier
update
P62
P61
Tunneling
P54
Binding
cache
Forwarding
P63
Buffering
P64
P52
Identifier
Verification
Bi-casting/
Multicasting
Handover: Distributed operation across multiple layers
Security
Association
p42
Discovery
Binding
Update
p52
Media
Rerouting
p54
p61
Attachment Configuration
CN
p13
Server
(Proxy,
/HA)
p23
p12
L3
PoA
p22
p31
p21
p11
p31 p32
p41
p42
p41
L2
PoA
p11
p12 p13
p21
p22
p23
p31
p32
MN
Time
p33
p52
p53 p54
p42
p32 p33
p31
p51
p41 p42
p42
p61
p63p64
p62
p51
p61 p62
p51
p51
p52
p61
Functional Matrix of Mobility Event
Mobility/
Function
Access
Type
Network
Discovery
Resource
Discovery
Triggering
Technique
Detection
Technique
Configuratio
n
Key
exchange/
Authenticati
on
Encryption
Binding
Update
Media
Rerouting
GSM
TDMA
BCCH
FCCH
Channel
Strength
SCH
TMSI
SRES/A3
DES
MSC
Contld.
Anchor
WCDMA
CDMA
PILOT
SYNC
Channel
Channel
Strength
Frequency
TMSI
SRES/A3
AES
Network
Control
Anchor
IS-95
CDMA
PILOT
SYNC
channel
Channel
Strength
RTC
TMSI
DiffieHellman
AKA
Kasumi
MSC
Contld.
Anchor
MSC
CDMA
1XEVDO
EVDO
PILOT
Channel
SYNC
Channel
Channel
Strength
RTC
TMSI
DiffieHellman/
CAVE
AES
MSC
PDSN/MSC
802.11
CSMA/
CA
Beacon
11R
11R
802.21
SNR at
Mobile
Scanning.
Channel
Number,
SSID
SSID,
Channel
number
Layer 2
authenticat
e
802.1X
EAP
WEP/WPA
802.11i
Associate
IAPP
Cell IP
Any
Gateway
beacon
Mobile
msmt.
AP
beacon
ID
GW Beacon
MAC
Address
AP
address
IPSec
IPSec
Route
Update
Intermediat
ey
Router
MIPv4
Any
ICMP
Router
adv.
FA adv.
ICMP
Router
Adv.
FA adv.
L2
triggering
FA adv
FA-CoA
Co-CoA
IKE/PANA
AAA
IPSec
MIP
Registrat
ion
FA
RFA
HA
MIPv6
Any
Stateless
Proactive
CARD
802.21
11R
Router
Adv.
Router
Prefix
CoA
IKE/PANA
AAA
IPSEC
MIP
update
MIP RO
CH
MAP
HA
Handoff Analysis of Mobile IPv6
nAR
pAR
MN
HA
CN
Data
L2 Handoff
Discovery
Authentication
nAP
Beacon
AAA
Probe Request
Probe Response
Open Authentication
EAP-OL
L2
Security
Association
L3 Handoff
Movement
Detect
Layer 3
configuration
Address
uniqueness
EAP-TLS
EAP Success
L2 Association
4-way handshake
Router Solicitation (Rtr Sol)
Router Advertisement (Rtr Adv)
Neighbor Solicitation (NS)
Neighbor Advertisement (NA)
BU
BAck
HoTI
CoTI
HoT
HoT
CoT
BU
BAck
Data Traffic at nPoA
Route Optimization
HoTI
[MN-HoA:CN] [Data]
Return Routability
Binding Update
[MN-CoA:CN] [MN-HoA:CN] [Data Tunneling]
Proposed optimization techniques
for handoff components
Proposed optimization techniques for respective handoff
components
Handoff
components
Fundamental
principles
My proposed
optimization
techniques
Key
advantages
My
publications
Related
work
Discovery
- Proactive
discovery
- Caching
neighboring
network elements
and parameters
Application layer
proactive discovery of
network and resources
- Access
independent
- Eliminates
layer 2 scanning
delay
1. ACM Mobiquitous
2005
2. IEEE Broadnets 2006
3. IEEE 802.21 (2005)
• Selective scanning for
802.11 (Shin et al.)
• Periodic scanning
(Montavont et al.)
• Search in parallel with
data (Velayos et al.)
Detection of
network
attachment
- Cross layer event
triggers
- Policy-based
approach based on
-Link layer event triggers to
expedite network detection
or loss of network
- Use of cross layer
information and policy to
limit the binding update
-Speed up the
execution of upper
layer operations
- Avoids the unnecessary binding
update overhead
- Policy-based
approach
1. IEEE WTC 2006
2. Springer Journal 2007
3. IEEE 802.21 (2005)
4. IEEE Wireless
Communication Magazine
5. IEEE MILCOM
Teraoka et al.
Politis et al.
Carli et al.
Lee et al.
Zeadaly et al.
- Router assisted
Duplicate Address
Detection
- Client does not
perform DAD
1. IEEE Sarnoff 2005
2. 2007 Springer
Journal on Wireless
Personal Communication
Optimistic DAD
Passive DAD
Rapid Commit RFC 4039
- Proactive IP address
acquisition
- Network layer
configuration delay
is avoided
mobile’s movement
and type of
application
Configuration
-Network assisted
duplicate address
detection
- Reduction of
signaling between
mobile and server
- Caching of
network identifier
address
Proposed optimization techniques for respective handoff
components (contd.)
Handoff
components
Fundamental
principles
My proposed
optimization
techniques
Key
advantages
Binding Update
Limit the binding
update traversal
distance
- Anchor assisted
hierarchical binding
update for network layer
and application layer
mobility protocol
- Reduction in
global signaling
overhead
- Proactive
binding update
- Eliminates the
binding update delay
completely
- Limit binding update
delay based on cross
layer triggers (e.g., layer
2 and application layer)
- Mobility
optimization based
on mobility pattern
and application
- Increases
throughput by 50 %
Infrastructurebased single host
mobility
Multi-layer
Mobility
- Policy-based
approach based on
mobile’s movement and
type of application
- Cross layer triggers
My
publications
1. IEEE PIMRC 2004
2. ACM MC2R
3. IEEE MILCOM
2005
4. IEEE Wireless
Communication
Magazine 2003
5. IEEE Wireless
Magazine 2008
1. IEEE MILCOM
2002, 2003
2. IEEE Wireless
Communication
magazine
3. Wiley journal on
Computer
communication
Related
work
MIP-RR
RFC 4857
HMIPv6 RFC 4140
Proposed optimization techniques for respective handoff
components (contd.)
Handoff
components
Fundamental
principles
My proposed
optimization
techniques
Key
advantages
Binding update
(contd.)
- Retransmission of
binding update
- Simultaneous
binding update
- Forwarding or
caching of binding
update
- Location Proxy
- Binding update Proxy
Eliminates
vulnerability interval
- Soft handoff approach
- Timer-based
retransmission
- Can be
implemented easily
- Simultaneous bindings
- Receiver and sender
assisted approaches
-No significant
increase in handoff
latency
- Limit the signaling
exchange between
authenticator and
mobile for key
generation
- Network layer assisted
pre-authentication
- Access
independent
- Enables preauthentication
across
administrative
domains
- Avoid re-keying
process
- Maintain security
association using an
Anchor agent
- Minimal
infrastructure
change
- Works with any
mobility protocol
Simultaneous
mobility
Layer 3 security
association
My
publications
Related
work
1.IEEE MILCOM
2. IEEE Wireless
Communication
Magazine
3. Wiley Journal on
Computer
Communication
Tilak and Ghazaleh
Dreibholz et al.
1. ACM Mobiquitous
2005,
2. ACM Mobiquitous
2007
3. IRTF MOBOPTS
2005
4. IEEE WCM
magazine
2008
5. HOKEY WG
6. ACM MC2R 2005
7. ACM WMASH
2004
802.11i
802.11r
Context transfer
(e.g., Bargh et al.)
Forte el al.
Miu et al.
Bahl et al.
Rodriguez et al.
(context transfer)
Proposed optimization techniques for respective handoff
components
Handoff
components
Media
re-routing
Fundamental
principles
My proposed
optimization
techniques
Key
advantages
- Position media
redirection entity
closer to the mobile
- Transient redirection of in-flight
data from previous network
- Reduces the packet
loss during handoff by
60%
- Maintain direct
path between
communicating
hosts for packet
delivery
- Small group multicasting
- Works well for
multiple number of
neighboring networks
- Edge network buffering
- Dynamic buffering
adjusts the buffer size
based on handoff delay
and reduces packet
loss to zero
-Packet interceptor to change the
source and destination address of
the end nodes
-40 % latency
improvement for small
packets
-- Only application layer
changes in the MN and
CN
- Proactive JOIN
- Proxy assisted Leave
- JOIN during registration
- No tunnel overhead
-Application layer
triggering
- Suitable for intradomain mobility
Unicast
Multicast
-Reduction in
“JOIN” latency
-Reduction in
“Leave” latency
- Hierarchical
multicast approach
My
publications
Related
work
1. IEEE Wireless
Communication
Magazine 2003
2. IEEE PIMRC 2006
3. IEEE Wireless
Communication
Magazine 2008
4. IEEE WCNC 2007
FMIPv6
Malki et al.
Moore et al.
Krishnamurty et
al.
RFC 3775
Wu et al.
SIP
1. NOSSDAV 99
2. ICC 2001
3.IEEE Communication
Magazine, 2004
Wu et al.
McAuley et al.
Lin et al.
Modeling Mobility
Why Mobility Model ?
• Optimization techniques of a mobility event can be designed
based on precedence relations amongst events and
concurrent, conflicts or resource sharing type operations
• Need a framework and model
– to analyze and schedule handoff processes for systems optimization
– to conduct trade-off analysis between systems resources and
performance metrics
• Specific expected results
– Determine the maximum parallelism possible between handoff primitives
– Determine handoff delays based on the execution of primitive operations
under constraints of limits on parallelism and constraints on the use of
shared resources
– A methodology to verify the systems performance of a specific
optimization technique
– A methodology that can help design the optimal path of sequence of
execution of events
Specifics of IP-mobility model
• Mobility event exhibits concurrent, sequential, conflicts
or resource sharing behavior similar to a Flexible
Manufacturing Systems (FMS)
• Handoff-related processes can be modeled as
Discrete Event Dynamic Systems (DEDS) that span
across layers and include multiple protocols
• I use Deterministic Timed Transition Petri Net
(DTTPN) to evaluate and predict the performance of
the system that demonstrates parallelism, optimistic or
speculative operations
Modeling Steps
• Determine data dependency of mobility
events
• Analyze the resource consumption for
handoff components
• DEDS Modeling of various handoff
components
• Systems performance for handoff events
• Scheduling of handoff functions
• Verification of behavioral properties e.g.,
deadlock
Dependency analysis of mobility events
Handoff Process
P11 – Channel Discovery
P12 – Subnet discovery
Precedence
Relationship
P00
P21,P22
P13 – Server discovery
P12
P21- Layer 2 association
P11
P22- Router solicitation
P23- Domain advertisement
P21, P12
P13
P31 – Identifier acquisition
P23,P12
P32 – Duplicate address
Detection
P33 – Address resolution
P41 – Authentication
P42 – Key Derivation
P51 – Identifier update
P31
P52 – Identifier verification
P53 – Identifier mapping
P31
P51
P54 – Binding cache
P61 – Tunneling
P53
P51
P62 – Forwarding
P63 – Buffering
P64 – Multicasting/Bicasting
P51, P53
P62, P51
P51
P32, P31
P13
P41
P31,P52
Data it depends on
Signal-to-Noise Ratio value
Layer 2 beacon ID
L3 router advertisement
Subnet address
Default router address
Channel number
MAC address
Authentication key
Layer 2 binding
Server configuration
Router advertisement
Default gateway
Subnet address
Server address
ARP
Router advertisement
New identifier
Address of authenticator
PMK (Pairwise Master Key)
L3 Address
Uniqueness of L3 address
Completion of COTI
Updated MN address
at CN and HA
New Care-of-address mapping
Tunnel end-point address
Identifier address
New address of the mobile
New identifier acquisition
New identifier acquisition
Resource usage per mobility events
Sub
transitions
Sub-operations
Resource Consumption
Bytes
exchanged
CPU samples Power
(nano
joules)
t00
t01
t11
t12
t13
t21
t22
t23
t31
t32
t33
t41
t42
t43
t51
Layer 2 un-reachability test
Layer 3 unreachability
Discover layer 2 channel
Discover layer 3 subnet
Discover server
Layer 2 association
Router solicitation
Domain advertisement
Identifier acquisition
Duplicate address detection
Address resolution
Layer 2 open authentication
Layer 2 EAP
Four-way handshake
Master key derivation (PMK)
43
86
109
110
126
99
70
226
1426
164
60
94
2842
504
0
5
3
3
4
5
2
4
4
5
6
3
3
6
4
10
51600
103200
130800
132000
540000
118800
84000
271200
1711200
196800
72000
112800
3410400
604800
0
t52
t61
t62
t63
t64
t71
t72
t81
t82
t83
t91
t92
Session key derivation (PTK)
Identifier update
Identifier verification
Identifier mapping
Binding cache
Fast binding update
Local caching
Tunneling
Forwarding
Buffering
Local id mapping
Multicasting/bicasting
0
204
148
0
0
110
0
60
100
120
40
192
6
4
6
8
3
3
6
2
2
3
4
2
0
422400
177600
0
0
132000
0
72000
120000
144000
48000
230400
L2 beacon adv
L2 Active Scanning
Types of resources
CPU
L2 Association
Open Authentication
EAPOL
4-Way handshake
Bandwidth
Router Solicitation
Router Advertisement
DHCP
DAD
Battery
Binding Update
COTI
0%
20%
40%
60%
80%
Percentage of resources usage
100%
L3 unreachability
Server Discovery
L2 unreachability
Sample Petri Net Primitives
P1
t1
t2
P3
P1
t1
a. Sequential
p1
b. Conflict
t1
p2
d. Data dependency
c. Concurrent
p1
t1
P3
p2
t1
p1
t2
p2
t2
p1
t1
t2
t2
p2
e. Merging
t3
p1
p2
f. Confusion
p3
g. Mutual exclusive
i. Cyclic
h. Priority
Capturing sequence of handoff operations in Timed Petri Nets
Pa
Pb
tc
pa starts before pb
ta
Pa
Pb
pa meets pb
tc
tb
ta
ta
Pa
tc
tb
pa overlaps pb
Pb
tc
tc
tb
Pa
pa during pb
Pb
tc
ta
ta
Pa
pa starts pb
tb
Pb
tb
tb
tc
pa
pa finishes pb
pb
ta
pa
pb
pa starts with pb
tb
tc
ta
Petri Net Approach to Systems
Modeling in IP-based Handoff
Network
Attached
Network
Discovered
Disconnected
Mobile Node
Configured
t2
P1
P0
t3
P2
t1
P3
2
PB
t0
t4
PM
P7
t9
P5B
PP
t7
t8
Connected
P8
01/06/2009
t5
P6
Identifier
Updated
t6
P5A
Security
Association
Established
HICSS-42
P4
Mobile Node
Authenticated
26
Hierarchical Representation- Handoff Subprocesses
Network
Resource
Discovery
Subnet
discovery
t02
Channel
Discovery
Duplicate
Address
Detection
Server
discovery
p02
t03
t01
t2
P1
t1
Network
Discovered
t22
Network
Attached
t12
t11
P11
p23
Identifier
acquisition
t3
P2
t13
P12
HICSS-42
P3
Mobile
Configured
P13
Router
Domain
L2
solicitation
Advertisement
association
01/06/2009
t23
p03
t21
Address
resolution
p22
p21
p01
P0
Configuration
Process
Network
Detection
Process
27
Places of Petri Net model for IP-based
mobility
Places
Description
P0
Mobile node is in disconnected state
P1
Network and resources discovered
P2
Target network selected
P3
Mobile node is configured and registered
P4
Mobile node is authenticated
P5A, P5B
Security association is established
P6
Binding update is complete
P7
Intra-domain binding update is complete
P8
Mobile is connected state
PB
Bandwidth resources
PM
Memory resources
PP
CPU resources
28
Transitions for Petri Net Model for IPbased mobility
Transition
Description
t0
Mobile node gets disconnect trigger
t1
Mobile node discovers the network and resources at the
new PoA
t2
Mobile node selects the network
t3
Mobile node goes through configuration and registration
t4
Mobile node goes through authentication process
t5
Mobile node goes through key derivation and security
association process
t6
Mobile node goes through binding update process
t7
Mobile node goes through hierarchical binding update
t8
Data gets redirected to the mobile node
t9
Data gets redirected to the mobile node
29
Verification of handover systems
performance using Petri net
1. Cycle time of Deterministic Timed Petri net
– Minimum cycle time (C) is an indicator of maximum
performance
– Determines which specific sequence of transition during a
handover provides minimum handover delay
2. Floyd algorithm
– S matrix is formed out of token loading matrix, transition
matrix and distance matrix
– Inspection of the diagonal elements of matrix “S” indicates
whether systems meets the required performance
3. Resource Time Product (RTP)
4. Performance evaluation using MATLAB-based
Petri net Tools
– Coverability Tree, Incidence matrix help determine system
behavior
Configuration Example (DHCP)
Server
Mobile
DHCP Discover
DHCP Offer
Processing
Identifier
Acquisition
DHCP Request
DHCP ACK
Waits for
an answer
to check
address
Processing
ARPING (anybody
has this address)
Processing
Duplicate
Address
Detection
Assigns
address
Updates ARP Cache
Address
Resolution
Configuration Process
Mobile
Authenticated
Duplicate
Address
Detection
Identifier
Acquisition
p1
p0
2
t2
t1
Address
Resolution
p3
t3
2
3
2
1
2
3
p4
(Resource Battery
Power)
p5
(Resource
Bandwidth PB)
p6
(Resource CPU PP)
Configured
Sub-process - 1
(Identifier Acquisition)
P1
t1
Client is
in process of
getting IP
address
t2
Initial Client
Sends
Discover
Message
p4
(Resource battery)
P2
Client is
checking the
address
Server
Offers
Address
p5
(Resource
Bandwidth)
P3
Client
Waits for the
address
P4
t3
Client
Requests
Address
t4
Server
Acknowledges
p6
(Resource Processing power)
Sub-process - 2
Duplicate Address Detection
t1
P2
P1
t2
Initial Client
Sends
ARP/Neighbor
Discovery
Client
Listen for
ARP response
3
3
1
(Resource Battery
Power)
P3
t3
Client
confirms
the address
1
2
2
(Resource PB)
(Resource PP)
Sub-process 3IP Address Resolution (IP Address-MAC mapping)
t1
P1
Idle
3
Send
ARP
Broadcast
2
3
(Resource Battery)
Network
Processing
ARP
P2
t2
Maps
IP address
to MAC
2
(Resource PB)
(Resource PP)
Reachability Analysis
(Configuration)
M0= [1003430]T
t1 fires
M1= [0102120]T
t2 fires
M2= [0010220]T
t3 fires
M3= [0003431]T
Incidence Matrix Analysis
(Configuration)
Input Matrix D- =
Output matrix D+=
Incidence
matrix D = D+ -
D- =
Matrix equation-based approach
(Configuration)
µ’ = µ+x.D
Given a sequence σ = t1t2t3 translates to a firing vector
f(σ) = (1,1,1), one can determine the marking µ’ as
µ’ = (1, 0,0,3,4,3,0) +(1,1,1).
µ’ = (1,0,0,3,4,3,0) + (-1,0,0,0,0,0,1)
µ’ = (0,0,0,3,4,31)
Thus, µ’ is reachable from the initial marking with a
sequence of transition t1,t2,t3 that corresponds to (1,1,1)
Discovery Process
Disconnect
Trigger
L3 subnet
discovery
Scanning
p6
p0
p1
2
Server
discovery
t2
t11
1
Resources
discovered
p2
2
t13
2
3
p3
(Resource PM)
p4
(Resource PB)
Discovery Process
p5
(Resource PP)
Attachment Process
Channel
available
Layer 2
association
Router
Solicitation
p1
p0
t2
t1
Domain
advertisement
p6
p2
Mobile
connected
t3
2
p3
(Resource battery)
p4
(Resource PB)
Network Attachment
p5
(Resource PP)
Authentication Process
Open
Auth
WEP
Key
EAP
p5
p0
p1
t1
Mobile
Authenticated
t2
2
3
2
2
p2
(Resource Battery
PM)
2
p3
(Resource Bandwidth
PB)
p4
(Resource
Processing Power
PP)
Discovery, Attachment, Authentication,Configuration,
L3 subnet
discovery
Disconnect scanning
Trigger
Server
discovery
P1
Network
Discovery
p0
Network
Attachment
t2
t1
Channel
available
Probing
p6
p4
Router
Solicitation
Configuration
Server
Discovered
p11
p7
t4
P2
Domain
discovered
P3
p9
t6
t23
Identifier
Acquisition
t7
p10
Duplicate
Address
Detection
t8
p15
t11
EAP
Open
Auth
Authentication
p8
Domain
advertisement
t5
p5
WEP
Key
t3
p12
t9
Address
Resolution
Mobile
Configured
t10
p13
p14
L3 subnet
discovery
scanning
Disconnect
Trigger
Server
discovery
P1
Network
Discovery
p0
t2
t1
Channel
available
Probing
p4
Router
Solicitation
Domain
advertisement
p6
Network
Attachment
P2
t5
p5
WEP
Key
p15
t11
t23
EAP
Open
Auth
Authentication
Domain
discovered
p7
t4
P3
p8
Configuration
t3
Server
Discovered
p9
t6
Identifier
Acquisition
Duplicate
Address
Detection
t8
p11
p10
t7
p12
Address
Resolution
Mobile
Configured
t10
t9
p13
p14
Petri net model across layers (x)
Media redirection
State
BU performed
Layer 4
Event
Application
Layer
Forwarding
Leave layer 3
Layer
transition
authenticated
Enter layer 3
L3 address
acquisition
L3 discovery
Location
DAD
Layer 3
Event
Enter layer 2
L3 authentication
performed
buffering
configuration
Leave layer 2
Layer 3
L2 authentication
performed
Authenticated
discovery
Layer 2
Scanning is performed
SNR goes below
a threshold
Leave mobility
event
Connected
Extraneous
action
Network
Selected
Layer 2
Event
Disconnected
Enter Mobility Event
Event
transition
System evaluation
Experimental and model-based
Experimental systems based on optimization principles
Proof-of-concept of Experimental Systems I have verified
Types
Of
scheduling
Relevant
Optimization
Principles
Sequential
Maintain direct
path between CH
and MH
Limit binding
update between
CH and MH
SIPbased
Fast
handoff
Predictive
Optimized
handoff
In IMS
Muti-layer
Mobility
Fast
Handoff
For
Multicast
X
x
X
Proactive
authentication
X
Proactive
identifier
configuration
X
Proactive
binding update
x
Dynamic Buffering
x
Target
System
P
E
R
F
O
R
M
A
N
C
E
X
X
Simultaneous
discovery of Layer
2 and
Layer 3 point of
attachment
Simultaneous
Mobility
x
Proactive network
discovery
Proactive Security
association
(context transfer)
Parallel
Media
Independent
Preauthentication
x
Maintain Security
association
between endpoints
Anchor-based
forwarding
Mobile
VPN
&
x
x
x
R
E
S
O
U
R
C
E
S
System Evaluation: Media Independent Preauthentication – Architecture
Network 4
AR
Information
Server
CN
INTERNET
Network 3
MN-CA key
Network 2
Current
Network 1
AR
TN
AP1
AP1 Coverage Area
Mobile
MN-CA key
AR
AR
AA
AA
CA
AP2
CTN
CA
AP3
AP 2 & 3 Coverage Area
CTN – Candidate Target Networks
TN – Target Network
Media Independent Pre-authentication Mechanism
1. DATA[CN<->A(X)]
2. DATA [CN<->A(Y)]
over proactive handover
tunnel [AR<->A(X)]
Home
Network
Information
Server
CN
Proactive
discovery
3. DATA[CN<->A(Y)]
MN-CA key MN-AR key
Pre
configuration AA
BU
CA
AR
Data in new
domain
Tunneled Data
Buffer
Module
Domain X
Domain Y
Proactive handover
pre-authentication
tunneling end
procedure
L2 handoff
procedure
Data in old
domain
Key Optimization Techniques
Applied:
HA
MN
• Proactive discovery of networksA(X)
and network elements
• Proactive authentication
• Pre-configuration by caching IP address
• Proactive binding update
• Buffering and copy-forwarding techniques
MN
A(Y)
CN: Correspondent Node
MN: Mobile Node
AA: Authentication Agent
CA: Configuration Agent
AR: Access Router
Experimental results Post-authentication vs. Pre-authentication
Types
Of
Authentication
Post-authentication
(Sequential)
Network Layer
Assisted layer 2
(Proactive discovery and
Pre-authentication)
Handoff
Operation
Non
Roaming
Roaming
Non
Roaming
Roaming
Tscan
460 ms
460 ms
0
0
Tauth
61 ms
599 ms
177 ms
831 ms
TConf
(2 AP)
0
0
16 ms
17 ms
Tassoc
+ 4 Way
handshake
18 ms
17 ms
15 ms
17 ms
Total
539 ms
1076 ms
208 ms
865 ms
Time affecting
handover
539 ms
1076 ms
15 ms
17 ms
Results (I) Proactive vs. non-optimized – Intra-technology
Mobility Type
MIPv6
SIP Mobility
802.11
Handoff
Parameters
Bufferin
g
Disabled
+ RO
Disabled
Buffering
Enabled
+ RO
Disabled
Buffering
Disabled
+ RO
Enabled
Buffering
Enabled
+ RO
Enabled
Buffering
Disabled
Buffering
Enabled
L2 handoff
(ms)
4.00
4.0
4.00
4.00
4.00
4.00
L3 handoff
(ms)
1.00
1.00
1.00
1.00
1.00
1.00
Avg. packet
loss
1.3
0
0.7
0
1.50
0
Avg. interpacket
interval (ms)
16.00
16.00
16.00
16.00
16.00
16.00
Avg. interpacket
arrival time
during
handover
(ms)
21
45
21
67
21
29.00
Avg. packet
jitter (ms)
n/a
29.00
n/a
51.00
n/a
13.00
Buffering
period (ms)
n/a
50.00
n/a
50.00
n/a
20.00
Avg.
Buffered
Packets
n/a
2.00
n/a
3.00
n/a
3.00
Detailed Results: Proactive Handoff
4 s 802.11
• non-optimized
– About 200 packets loss, ~ 4 s during
handover
• Includes standard delay due to layer 2, IP
address acquisition, Re-Invite,
Authentication/Authorization
• Media Independent Pre-auth
handoff
802.11
– No packet
pre-authentication, pre802.11loss during
configuration and pro-active handoff before
L2 handoff
– Zero packet loss with buffering, 5 ms delay
during handoff
• Includes delay due to layer 2, update to
delete the tunnel on the router
• reduced the layer 2 delay in hostap
Driver
• L2 delay depends upon driver and chipset
Mobile Initiated Handoff – Heterogeneous handover
MN
MPA Client
MN
MIHF
Legend
VoIP Through
Mobile Node (MN)
Wi-Fi interface
ParameterReport
and Link Down
Subscription
Threshold
Configuration
Link Going Down
Threshold 1
Information
Service Query
Response
1. Subscribe Request to event:
Link Parameter Report
confirm
2. Configure Threshold Request:
Wi-Fi Signal Levels: thr1, thr2, thr3
confirm
3. Link Parameter Report
Indication (Threshold 1)
4. Get Info Request
Message Types
MIH Commands
EV-DO interface
MIH Link Events
MPA Signaling
Target Network: CDMA
MPA
Server
Information
Server
IS
MIHF
IS
MIH
User
6. Get Info Request
5. MIH Message: Get Info Request (SPRQL query)
8. MIH Message: Get Info Response (RDF query response)
9. Get Info Confirm
7. Get Info Response
Link Going Down
Threshold 2
EV-DO Link Up
10. Link Parameter Report
Indication (Threshold 2)
11. Link Action Request:
EV-DO, Link Power Up
confirm
MPA Proactive HO
12. MPA: Pre-authentication, Pre-configuration, Proactive HO Tunnel
Link Going Down
Threshold 2
13. Link Parameter Report
Indication (Threshold 3)
MPA HO Complete
14. MPA: Layer 2 HO
15. Link Action Request:
Wi-Fi, Link Power Down
Wi-Fi Link Down
confirm
Network Initiated Handoff – Heterogeneous handover
Mobile Node (MN)
MN
MPA Client
MN
MIHF
3. Link Parameter Report Indication
4. Get Info Request (SPRQL query)
Info Service
Query/Response
Net HO Candidate
Response
Get Info Response (RDF query response)
Net HO Candidate
Indication
5. Net HO Candidate Request
6. Link Action Request:
EV-DO, Link Power Up
confirm
7.Response
MPA HO
Complete
Wi-Fi Link Down
Response
8. N2N HO Query Resources Request
Response
N2N HO Query
Resources
MPA Proactive HO
Information
Server
Response
2. Configure Threshold Request:
Wi-Fi Signal Levels: thr1
Response
Link Going Down
EV-DO Link Up
MPA
Server
1. Subscribe Req.:Link Parameter Rep
Link Parameter Rep
Subscription &
Threshold
Configuration
Net HO Candidate
Request
Target PoS:CDMA
Serving
PoS:
WiFi
9. MPA: Pre-authentication, Pre-configuration, Proactive HO Tunnel
10. MPA: actual HO
11. Link Action Request:
Wi-Fi, Link Power Down
confirm
802.11 – 802.11
Home
Network
CN
DHCP
server
Pre-configuration
Pre-authentication
pAR
L3 PoA
Internet
Network
D
PANA
server
Buffering
module
Proactive
Handover
AP1
Tunnel
Network B
L2 PoA
MN
MN
Media
interruption
4s
CN
Provide
handover
services to MN
via tunneled
traffic
EV-DO Network
X.X.X.X/Y
(Global IP)
MPA Server
10.10.40.52/24
Tunneling
nAR
module
L3 PoA
AP0
(L2 PoA)
Network A
802.11
HA (MIP)
AAA
Core
Network
Network C
802.11 – CDMA
Sample Application:
skype
802.21 Info
Server can be
used in EV-DO
to WiFi
Handover
10.10.30.52/24
IS
Pre-Auth
TunnelBuffer
MIH Query for
WiFi access
availability
MN Traffic= IP-IP: X.X.X.X/10.10.40.21
MN
MN Traffic= IP-IP: X.X.X.X/
Verizon PPP
Local IP1: Verizon PPP (via EV-DO)
Local IP0: 10.10.40.21
802.21 capable
device.
Sample Application: skype
Wifi
AP
802.11
802.11
CDMA
Handoff Delay
~ 18 s
a. MIP-based Non-optimized handoff
a. Non-optimized handoff
802.11
CDMA
c. MPA and 802.21 assisted optimized
handoff
802.11
b. MPA assisted optimized
handoff
A. Comparison of optimized and nonoptimized homogeneous handoff
Handoff Delay
16 s
CDMA
b. SIP-based Non-optimized handoff
B. Comparison of optimized and non-optimized heterogeneous
handoff
Petri net model for
Sample Optimization Techniques
Results from Petri net modeling
• Using MATLAB analyze Timed Petri net-based
mobility models and verify optimization techniques
–
–
–
–
–
–
–
Optimized security association
Hierarchical binding update
Redirection of in-flight data
Optimized configuration
Multi-interface mobility
Simultaneous mobility
Multicast mobility
• Prediction of handover performance under
different handoff schedules
– Sequential, parallel, proactive
• Verification of system behavior
– Deadlocks in the system
• Concurrent system
VPN mobility (without HA)
i-HA
CN
VPN-GW
Tunnel1
data
MN
Tunnel2
Double tunneled data
Handoff
IKE Key exchange
Context establishment
New VPN tunnel creation
Tunnel/Detunnel
New data
New data on double tunnel
VPN mobility with home agent (x-HA)
CN
i-HA
VPN-GW
Tunnel1
Triple tunneled
Tunnel2
x-HA
MN
Tunnel3
data
X-MIP
Reg
Handoff
X-MIP
reply
New MIP
Tunnel
creation
Tunnel/de-tunnel
Triple tunneled
data
Mobile VPN resource analysis
Tasks
VPN
Mobility
without
x-HA
VPN mobility
with HA
Resources Needed
Battery
Power
Bandwidth
Processing
Power
IKE
2
3
1
Security context
1
1
2
New VPN Tunnel
creation
1
1
2
Tunnel/de-tunnel ops
1
2
2
External MIP update
1
1
1
New MIP Tunnel
creation
1
1
1
Tunnel/de-tunnel ops
1
3
3
VPN mobility (without HA)
Mobile
Reconfigured
Security
Context
established
IKE
Exchange
p0
p1
t1
2
t2
3
(Battery Power)
Tunnel/
De-tunnel
operation
p2
2
p4
(Resource Bandwidth
PB)
p6
Mobile
Gets data
3
2
p3
Tunnel
creation
p5
(Resource
Processing Power
PP)
VPN mobility (with xHA)
New
Tunnel
creation
Identifier
Update
Mobile
re-configured
Tunnel/de-tunnel
operations
p6
p1
p0
p2
t1
t2
p5
2
3
p3
(Battery Power)
p4
(Resource Bandwidth
PB)
p5
(Resource
Processing Power
PP)
Mobile
Gets data
Hierarchical binding update
Visited SIP
Registrar
MH
Forwarding
Agent
Media before handoff
Handoff
(Binding Update)
Re-INVITE
IP2
(New Address)
Register (Fast Binding Update)
SIP-CGI (3)
Tunneled in-flight data
ACK
OK
New traffic from CH
Forward
traffic
(IP1:p1 ---> IP2:p1)
CH
Petri net model: Hierarchical binding update
Global
Binding
Update
Mobile
configured
t1
Identifier
Verification
Identifier
Mapping
t2
t3
Global
Data
forwarding
t4
3
PM
p11
t8
p13
PB
PP
p12
t5
t6
t7
Packet
reordering
Fast
Binding
Update
Local
Tunnel
setup
Local
Forwarding
Mobile gets
Transient data
Hierarchical binding update
MN
SA1
MA1
SA2
SA3
MA2
HA
CN
Data
SA2 Adv
Inter-domain
handoff
LCoA and
RCoA
Configuration
Local Binding Update (LBU)
Local Binding Acknowledgement (LBacK)
MN-MA Tunnel
Global BU
Global ACK
Tunnel
Data
Data
Intra-domain
hnadoff
LCoA
Configuration
SA3 Adv
LBU
Local Binding
Update
LBacK
MN- MA Tunnel (New)l
Tunneled Data
Data
De-capsulation/
Encapsulation
at MA
Pteri net model: Hierarchical binding update
Local
configuration
MN-MA
Tunnel creation
Local
Binding
Update
HA-MA
Tunneling
Mobile
Global
authenticated configuration
Global
Binding
Update
De-capsulation/
Encapsulation
at MA
MA-MN
Tunneling
MA-HA
Tunnel
creation
a. Inter-domain handoff
Local
configuration
Mobile
authenticated
Local
Binding
Update
MN-MA
MA
Tunnel creation Tunneling
b. Intra-domain handoff
De-capsulation/
at the mobile
Mobile
Receives
Data
Duplicate Address Detection Optimization
Mobile
Node
RA
DHCP
Server
Router
DHCP Discover
Update ARP
cache
Multicast announcement
DHCP Offer
DHCP Request
Multicast announcement
DHCP ACK
Mobile
Assigns
address
(a)
DAD Optimization
Identifier
Acquisition
P1
Address
resolution
Mobile
configured
P0
P4
Mobile
Authenticated
Battery
power
P5
P6
Bandwidth
Duplicate
Address
Detection
Processing
Power
P2
P3
Multi-interface mobility
• Key Points to elaborate
– Precedence relationship and resource constraints
affect the way handoff takes place between the
access networks
– As an example, each access network has different
characteristics and resource constraints
• CDMA network has bandwidth resource constraints
• 802.11 network maybe limited to CPU power constraints
• Authentication procedures is different in two different
networks
– The model has the ability to predict the handoff
performance when the mobile hands off between two
different access networks with certain resource
constraints
Resource usage and timing operation
(CDMA vs. 802.11)
Operations
Resources in 802.11
Battery
Power
(nJ)
Operations in CDMA
Bytes
transferred
CPU
(cycles)
Battery
Power
(nJ)
Bytes
transferred
Timing
CPU
Processing
(tokens)
802.11
CDMA
414000
345
12
196800
328
9
745
422
Layer 2
Authentication
4126800
3439
29
1392000
232
14
106
200
Configuration
2257200
1881
22
5454000
909
12
510
850
Security
Association
940800
784
10
4752000
792
10
640
4500
Binding
Update
422400
352
18
2160000
360
18
168
599
Discovery
Bandwidth Resource is different in 802.11 and CDMA
(Mobile is connected when both are connected)
802.11 and CDMA interfaces come up in parallel
(mobile is in connected state only when both the interfaces are
active)
802.11 and CDMA – parallel
(If any one interface is active then the mobile is in connected state
802.11-CDMA – make-before-break
802.11 – CDMA Break-before-make
Coverability Tree
Disconnect
Trigger
L3 subnet
discovery
Scanning
p0
p1
t1
2
1
Resources
Server
discovered
discovery
p2
t2
p6
t3
2
2
3
p3
(Resource: Bandwidth)
p4
(Resource: Battery power)
p5
(Resource: CPU cycles )
Channel
available
Layer 2
association
p1
p0
Mobile
connected
Domain
advertisement
Router
Solicitation
t2
t1
p2
p6
t3
2
p3
(Resource: Bandwidth)
p4
(Resource: Battery Power)
p5
(Resource: CPU Cycles)
Open
Auth
WEP
Key
p0
EAP
p1
t1
Mobile
Authenticated
p5
t2
2
3
2
2
p2
(Resource: Bandwidth)
2
p3
(Resource: Battery power)
p4
(Resource: CPU cycles)
Duplicate
Address
Detection
Identifier
Mobile
Authenticated Acquisition
p0
p1
t1
Address
Resolution
p2
t2
t3
2
1
1
2
3
p3
(Resource: Bandwidth)
p4
(Resource: Battery Power)
p5
(Resource: CPU cycles)
Mobile
Configured
p6
Scheduling
(Sequential/Parallel/Proactive)
Sequential Operations (Discovery and Authentication
PB
Bandwidth
Resources
1 token
Mobile
Disconnected
P1
P0
Mobile
authenticated
Network
Discovered
Connected
P2
t2
P4
t3
t1 scanning
t4
t5
Authentication 4-way
Handshake Association
Disconnection
CPU
resources
P3
PP
PM
Power
Resources
MATLAB model for sequential operations
PA
Concurrent
Operations (Discovery
and Authentication)
Resources
Network b/w
2
2
t1
P01
P1
Connected
Network
Discovered
Scanning
P0
Association
t3
P3
4-way
handshake
complete
Mobile
Authenticated
P02
t2
P2
Authentication
CPU
4-way
Handshake
Operation
Memory
PB
t4
MATLAB modeling for concurrent operations
Verification from Petri Net modeling
using Cycle Time-based approach
Optimization
Schedule
Relevant
loop in Petri Net
Di
N
i
Max
Di/Ni
Transition
Operation
Time
t1
Disconnection
Trigger
5 ms
t2
Scanning
400 ms
t3
Authentication
50 ms
t4
4-way handshake
10 ms
t5
Association
5 ms
Minimum
Cycle Time
Sequential
p0t1p1t2p2t3p3t4p
4t5p0
470
1
470
Concurrent
p0t1p01t2p1t3p3t4
p0
420
1
420
P1t1P2t4P3t5P1
17
Proactive
1
17
Network discovery and authentication Process – Proactive Scheduling
Current Network
Target Network
Preauthentication
t12
PA2
P12
PA1
PB1
t13
AP
Key
installation
PD
Association
Dis
connected
P11
Network
discovery t11
P1
Connected
t5
t4
P3
P2
t1
4-way
Handshake
(SA)
PC
Sequential operation (Flyod Algorithm)
Token loading matrix
Distance matrix
Transition Time matrix
S Matrix
Proactive operation (Floyd algorithm)
Token loading matrix
Distance matrix
Transition Time matrix
S matrix
Deadlock analysis for handoff events
• Verification allows one to find out
– If any specific sequence of transitions/operations
lead to any deadlock
– If one specific state during handoff operation is
attainable from any other state by following a
specific sequence of transitions
– Whether the coverability tree is reversible
• The system comes back to the original state
• Methodology
– Reachability analysis
– Incidence Matrix-based equations
Untimed Concurrent (Resource
deadlock) – (MATLAB)
Deadlock avoidance for concurrent operations
(by adding resources)
Simultaneous Mobility (No deadlock)
Simultaneous Mobility
(Deadlock due to incomplete binding update)
Simultaneous Mobility (Deadlock avoidance)
(By use of retransmission techniques)
Conclusions
• This thesis contributes to the general theory of
optimized handover
– It addresses the need for a formal systems model that can
characterize a mobility event, associated optimization
methodologies and can provide handoff performance
predictions
• Developed Petri net models for handoff that can
– analyze the behavioral properties (e.g., deadlock)
– validate systems performance of any type of handoff optimization
– define handoff schedule to obtain a specific systems performance
• Developed optimization techniques across several
layers and verified these techniques by applying
these to several experimental case studies
• Based on the results derived a set of fundamental
principles of systems optimization for handoff that
include protocol design methodologies and
guidelines that will enable deployment of right set of
mobility protocols and optimization techniques
Future Work
• Current Petri net model can be enhanced to study
mobility in ad hoc networks
• Enhancement to generate automatic schedule of
handoff operations given a set of resource
constraints, performance objectives and dependence
graph
• Ability to design a customized mobility protocol that
will define its own set of elementary operations for
each of the desired handoff functions
• Future models should consider resource utilization
among the network components (e.g., Access point,
router, server) in a distributed fashion
• I envision specification of the functional components
of mobility protocols and tools that search for context
specific optimizations, such as caching, proactive
feature and cross layer techniques
Backup slides
(detailed results, mechanisms etc.)
Handoff Statistics
•
•
Handoff rate depends upon the following parameters
– Average cell size
– Mobile’s speed (e.g., vehicular, pedestrian)
– Average call duration
– Cell capacity
Example
Micro-cellular campus environment: A user is subjected to 8 to 10 handoffs
per day
Macro-cellular environment: A regular commuter in USA is subjected to an
average of 2 to 6 handoffs per day
• Average one-way commute is 16 miles
• Cell site coverage varies from 5 miles to 15 miles
• In a heavily dense area cell sizes are small to accommodate capacity
•
Percentage of Handoff related signaling
–
–
–
–
–
–
Handoff related signaling amounts to about 2% of the total data traffic that a user is
subjected to
Average user spends 700 minutes/month for voice = 23 minutes/day = 13*60*23 kbits/day =
2 Mbytes/day
Data usage - 90 Mbytes/month = 3 Mbytes/day
Thus, total data and voice should be about 5 Mbytes
Handoff related signaling messages – 70 kbytes/per day (MIPv6) , 100 Kbytes/day SIP
Handoff related signaling amounts to about 2% of the total traffic
Signal
RTP Data
Lost RTP Data
Timing sequence for MPA (proactive handoff)
Tunneled packet
MN
Network 1
MN
CN
DHCP
R2
Network 3
Network 2
RTP
IP0
DHCP
PANA
Tunnel
Setup
PANA (ACK)
DHCP(IP1)
RTP
RTP
SIP Re_INVITE (IP1)
56.359
OK (tunneled)
BU
No
Packets
lost
During BU
56.478
OK
RTP packets
Spaced ~16-20
ms
RTP
56.582
ACK
First Tunneled Data
RTP (39835)
56.722
RTP (42568)
12.498
Handoff
Decision
12.504
IWCONFIG
(IOCTL)
12.585
PANA Trigger to delete tunnel
PANA Response
12.509
12.513
12.529
12.593
RTP (42569)
RTP (42570)
RTP (42573)
Lost packet (in the tunnel)
JOIN
(12.600)
X
Lost packet (in the tunnel)
X
Lost packet (in the tunnel)
12.653 X
First packet in new network (non-tunneled)
IP1
(Auth/Assoc, ifconfig, route,)
JOIN (ACK) (19.610)
L2 handoff
+ local L3
Configuration
RTP (42574)
12.613
Tunnel
Deleted
in PAA
12.674
12.633
RTP (42575)
RTP (42576)
RTP (42577)
Review of Research Progress
Time
Line
Work
Progress
at the proposal
Status
at the defense
Identification of handoff components
Completed
Completed
Design and proof of concept mobility
optimization for handoff components
Completed
Completed
Systems prototype verification of
optimization methodologies
Completed
Completed
Initial IP-mobility systems modeling
Completed
Completed
July
2008
Complete the validation of up to 4
optimization techniques using Petri net
models
Working
Completed
September
2008
Develop methodology for minimizing
handoff using Petri net
Working
Completed
November
2008
Tradeoff design of proactive handoff
scheme
Working
Completed
December
2008
Thesis writing
Completed
March 2009
Thesis defense
Present
Mobility systems modeling using Timed Petri net
Problem
• Mechanisms and design principles for
optimized handover are poorly
understood
• No formal methodology to
systematically discover or evaluate
mobility optimizations
Approach
• Identification of the fundamental
properties that are rebound during
handover event
• Systematic analysis of the primitive
handover operations
• Modeling of the handover process that
allows performance predictions to be
made for both an un-optimized
handover and for specific optimization
techniques under systems resource
constraints
Connected
Results
• Timed Petri net-based mobility models
for handoff processes using MATLAB P0
and Time Net Tools
• Verification of optimization techniques
• Prediction of handover performance
under some resource constraints (e.g.,
battery, CPU and network bandwidth)
Network
Resource
Discovery
Subnet
discovery
Duplicate
Address
Detection
Server
discovery
p02
t02
Channel
Discovery
Configuration
Process
t23
p23
p03
t21
p01
t01
t1
Network
Discovered
Network
Attached
t2
P1
P0
t22
p21
t03
t12
t11
Identifier
acquisition
t3
P2
P12
P3
Mobile
Configured
t13
P11
Address
resolution
p22
P13
Router
Domain
L2
association solicitation Advertisement
Network
Detection
Process
Figure 1: Timed Petri net modeling for handoff
PA
Resources
Network b/w
2
2
t1
P01
P1
Network
Discovered
Scanning
Association
t3
P3
4-way
handshake
complete
Mobile
Authenticated
t2
P02
t4
P2
Authentication
CPU
4-way
Handshake
Operation
Memory
PB
Figure 2: Concurrent handoff operations
Resource Usage –Configuration
Functions
Configuration
Tasks
Resources Needed (Equivalent
Tokens)
Battery
Power
Bandwidth
CPU
cycles
Identifier Acquisition
1
1
1
Duplicate Address
Detection
3
3
1
Address resolution
3
2
1
Relevant Petri net representation to capture handoff
primitives
P1
P1
t1
t2
P3
t1
t2
b. Conflict
a. Sequential
p1
p1
t1
t1
p2
t2
p2
d. Data dependency
c. Concurrent
p1
p1
t1
t2
P3
p2
t1
p2
t2
t3
e. Merging
f. Confusion
p1
p2
p3
g. Mutual exclusive
Techniques applied
for mobility modeling
h. Priority
Modeling IP Mobility in Petri Net
t02
Subnet
discovery
p02
Network
Discovered
Network
Resource
Discovery
t03
Scanning
Network
Selection
Detection
Process
t013
p01
p03
t04
Disconnected
t01
P1
P0
t1
Configuration
Process
Network
Attached
t2
Mobile
Configured
t3
P2
P3
2
Resource 3
t0
t4
Resource 1
P7
Buffering
Redirection
t9
Authentication
Process
Resource 2
t8
Intra-domain
Binding update
t7
Connected
P8
t5
t6
P6
Updated
Media
Forwarding
Binding
Update
P5
Security
Association
Established
P4
Security
Association
Process
Authenticated
Data dependency analysis of handoff components
Handoff Process
Depends on data
from
Set of Data it depends on
(Not a complete list)
P11 - Channel discovery
P00
Channel broadcast
P12 – Subnet discovery
P21,P22
L2 beacon ID, L 3 Router advertisement
P13 – Server discovery
P12
Subnet address, Default router address
P21 – L2 association
P11
Channel number, MAC address, Auth Key
P22 – Router Solicitation
P21, P12
Layer 2 binding
P23 – Domain Advertisement
P13
Server configuration, Router advertisement
P31 – Identifier Acquisition
P23, P12
Default gateway, Subnet address, server
address
P32 – Duplicate Address Detection
P31
ARP, Layer 3 connectivity
P33 – Address Resolution
P32, P31
New Identifier
P41 - Authentication
P13, P22
Discovery of auth server
P42 – Key derivation
P41
Availability of PMK, Layer 2 and Layer 3
association
P51 – Identifier update
P31, P52
Layer 3 address, Verification of L3 address
P52 – Identifier verification
-
P53 – Identifier mapping
P51
HA, CN gets the new address (Identifier)
P54 – Binding Cache
-
Completion of identifier update
P61 – Tunneling
P51
End-point addresses (router), identifier address
P62 - Forwarding
P51, P53
New address of the mobile
P63 - Buffering
P62, P51
New Identifier acquisition
P64 – Multicasting/bicasting
P51
New identifier acquisition
Hierarchical Petri Net modeling using Timenet
Discovery
(Mobile IPv6)
Configuration
Authentication
Security Association
Binding
Update
Media
Re-routing
Why Petri net
• Petri nets can exactly model non-product form
features such as priorities, synchronization,
forking, blocking
• Can be used as both logical and quantitative
models
• Forms the foundation for formal analysis
models
• Strong analysis methods
Formal approach to mobility
systems modeling
Problem:
• Mechanisms and design
principles for optimized handover
are poorly understood
• No formal methodology to
systematically discover or evaluate
mobility optimizations
Approach:
• Framework or model that can
analyze the mobility event in a
systematic way, can verify and
predict the performance under
systems resource constraints
Formal approach to mobility systems modeling
Problem
• Mechanisms and design principles for
optimized handover are poorly
understood
• No formal methodology to
systematically discover or evaluate
mobility optimizations
Approach
• Identification of the fundamental
properties that are rebound during
handover event
• Systematic analysis of the primitive
handover operations
• Modeling of the handover process that
allows performance predictions to be
made for both an un-optimized
handover and for specific optimization
techniques under systems resource
constraints
Results
• Timed Petri net-based mobility models
for handoff processes using MATLAB
and Time Net tools to
• Verification of these models
• Prediction of handover performance
under specific resource constraints
(e.g., battery, CPU and network
bandwidth)
Network
Resource
Discovery
Subnet
discovery
Duplicate
Address
Detection
Server
discovery
p02
t02
Channel
Discovery
t03
t01
t2
P1
t1
Network
Discovered
t22
t23
p23
p03
t21
Network
Attached
t12
t11
P11
Identifier
acquisition
t3
P2
P3
Mobile
Configured
t13
P12
Address
resolution
p22
p21
p01
P0
Configuration
Process
P13
Router
Domain
L2
association solicitation Advertisement
Network
Detection
Process
Handover Scenarios
802.11 (provider X) to
CDMA (provider Y)
Inter-subnet
802.11b (provider X) to
802.11n (provider Y)
A-2
A-1
Inter-tech & Inter-tech &
Inter-domain Intra-domain
A-3
802.11 (provider X) to
CDMA (provider X)
A-4
Intra-tech & Intra-tech &
Inter-domain Intra-domain
802.11b (provider X) to
802.11n (provider X)
B-1
Intra-tech & Intra-domain
Intra-subnet
B-2
Inter-tech & Intra-domain
802.11 (provider X) to
CDMA (provider X)
Functional characteristics between CDMA and 802.11 networks
Mobility/
Function
Access
Type
Network
Discovery
Resource
Discovery
Triggering
Technique
Detection
Technique
Configuratio
n
Key
exchange/
Authenticatio
n
Encryption
Binding
Update
Media
Rerouting
CDMA
1XEVDO
EVDO
PILOT
Channel
SYNC
Channel
Channel
Strength
RTC
TMSI
DiffieHellman/
CAVE
AES
MSC
PDSN/MSC
802.11
CSMA/
CA
Beacon
11R
11R
802.21
SNR at
Mobile
Scanning.
Channel
Number,
SSID
SSID,
Channel
number
Layer 2
authenticate
802.1X
EAP
WEP/WPA
802.11i
Associate
IAPP
How to make the model useful for a realistic
deployment
• How do the resource constraints and access
characteristics affect the handover behavior during
handover between heterogeneous access
networks
• Single interface case
– Between 802.11 networks
• Break-before-make case
• Using virtual interface
• Multiple interface case
– Between 802.11 and CDMA network
• Two cases
– Make-before-break
– Break-before-make
Remote IS
Query/Response
Remote MIH Event
MIH Indication
MIH Users
IS
Query/Response
MIH Event
MIH Command
MIH Users
Remote IS Query/Response
MIH Function
Remote Command
MIH Function
Lower Layers
Local Entity
Remote Link
Command
Link Command
Link Event
Remote Event
Lower Layers
Remote Entity