Transcript ipl08-slide

PROXY-BASED HYBRID
CACHE MANAGEMENT IN
MOBILE IP SYSTEMS
Presented by: Jason Tilley, David
Keppel, Carson Nguyen
Written by: Weiping He, Ing-Ray Chen
AGENDA









Problem space
Proposed solution
System factors
System model
Network costs
Performance model
An example
Alternative schemes
Conclusion
PROBLEM DOMAIN




Proliferation of Mobile network Hosts
Frequently movement from one
coverage area to another
Mobile application often rely on remote
servers for application data
Need to increase efficiency of mobile
device traffic
CACHING AS A SOLUTION

Caching is often used solution



Reduces network traffic
Improves response time
Requires that application be informed
of changes to back-end data

Cache invalidation

Asynchronous or synchronous
HIGH LEVEL VIEW OF PROPOSED SOLUTION

Integrated approach to reduce traffic
caused by:




Mobility management
Cache consistency management
Query processing
Proxy


Gateway Foreign Agent
Asynchronous updates
SYSTEM INFRASTRUCTURE

Object is smaller than T



Fresh copy sent to Mobile Host
Avoids extra link up request
Object is larger than T


Invalidation report sent to proxy
Could avoid unnecessary transfer
CLIENT SIDE PROXY



Executes on Access Router
Performs Application and Network layer
functions
Gateway Foreign Agent as in MIP
Regional Registration protocol

Maintain location information of MH
MOBILITY

Move across subnet boundary within GFA


Obtains new Care of Address
Does not inform HA and CN of CoA change


Only proxy is informed
Move across regional boundary


Proxy moves to run on AR of first subnet in
new GFA area
Incurs cost


Transferring cache from one GFA to another
Notification of HA and CN of proxy address change
SERVICE AREA


Size is defined by number of subnet
Optimal size depends on:


MH runtime mobility
Service characteristics
CACHE MANAGEMENT

Buffer space for cache status



Stores invalidation reports and data
objects during disconnect
Forward reports and object otherwise
Reconciliation on MH reconnect
COST EFFECTS ON T

High value of T





Low value of T




Fresh copies generally sent
Proxy stores copies if MH is asleep
If MH cross regional boundary, high transfer cost
Query costs would be low
Mostly invalidation reports sent
Update and Transfer costs low
High query costs
Optimal value depends on regional area size
and mobility rate of MH
PETRI NET MODEL
GOALS


Optimize service area size and
threshold T dynamically
Minimize the overall network traffic
incurred due to



Mobility management
Cache management
Query processing
NETWORK COSTS

Query processing


Cache consistency maintenance


Server needs to send an invalidation report or a
fresh copy through the proxy
Mobility management cost


MH needs to forward a user query uplink to the
server to obtain a copy of the data object because
of cache miss
MH crosses a subnet boundary
Minimize the sum of these three types
of cost per time unit.
COSTS COMBINED INTO A FORMULA
 Ctotal – overall network traffic incurred per time unit
 Pwake – probability of the MH being awake (ωs/(ωs + ωw)
 λ q,j - query rate for the data object
 σ – MH mobility rate
 Cquery,j - average communication cost to service a query for
object j
 Cmobility – average communication cost to service a location
handoff
 Cupdate – average communication cost to forward an
invalidation report or a fresh copy for object j
PROBABILITY



PLT - the probability of a data object is
<= T, given by
PGT - the probability of a data object >
T, given by PGT = 1 – PLT
Average object size


<= T
>T
SPECIAL CASE

Object size is exponentially distributed
by
DERIVING CQUERY,J

Cquery,j


Let Ci,query,j be communication cost for
answering a query asking for object j while
MH is in state i
Cquery,j =

Consider 2 cases:


Size of object j < T -> cost is
Size of object j > T -> cost is
DERIVING CQUERY,J (CONT.)

Size of object j < T



Server will send a fresh copy instead of an
invalidation report when object j is
updated.
Query cost 0 for awake and sleep
Just-wake-up state, MH will need to see if
object j has been updated

Cost =
DERIVING CQUERY,J (CONT.)

Size of object j > T

Where:
DERIVING CMOBILITY



Let Ci,mobility – communication cost to
service a location handoff given that
the MH is in state i.
Cmobility =
With Ci,mobility given by
DERIVING CMOBILITY (CONT.)

nCT stands for number of packets for
context information which can be
estimated as
DERIVING CUPDATE
 Cupdate, j 
 (P
i
i  Ci , update, j )
where Pi is the probabilit y MH is in state i,
Ci , update, j is the cost to update object j in state i.
 Ci,update,j  PLT  Ci,update,j,LT  PGT  Ci,update,j,GT
 Ci,update,j,LT Cost to forward a fresh copy
 Ci,update,j,GT Cost to forward an invalidation report
DERIVING CUPDATE(CONT.)
 Object size < T
Ci , update, j , LT
if Sleep or Just - Wake - Up,
nD, j  

otherwise,
nD, j  (   F ( Xs )   )
 Object size > T
Ci , update, j , GT
if Sleep or Just - Wake - Up,


otherwise,
  F ( Xs )  
EXAMPLE
Fig. 3. Cost vs. threshold T .
EXAMPLE (CONT.)
T decreases
when λ increase.
Fig. 4. Optimal threshold T vs. λ.
EXAMPLE (CONT.)
K increases
as
λ
increases.
Fig. 5. Optimal K vs. λ.
ALTERNATIVE SCHEMES
 Push-based cache management scheme

Ctotal _
push
  q , j  Pwake  Cquery,
j , push
j
   Pwake  Cmobility, push 
u  C
j
update, j , push
j

Ci , query,
j , push 
Ci , query,
j , LT
0 if Sleep or Awake,


j
n
D, j 
 ( F ( Xs )   ) if Just - Wake - Up


s


j

ALTERNATIVE SCHEMES (CONT.)

Cmobility,push is the same as Cmobility
except nCT  nD  ndata  ( 1  Pwake)  1 where nD
is the average object size.

Cupdate, j , push  Ci , update, j , LT
ALTERNATIVE SCHEMES (CONT.)

Invalidation report based (IR-based)
cache management scheme.
 Ctotal _ IR 

q , j  Pwake  Cquery, j , IR
j

u  C
j
update, j , IR
j

Ci , query, j , IR  Ci , update, j , GT
   Pwake  Cmobility, IR
ALTERNATIVE SCHEMES (CONT.)

Cmobility,IR is the same as Cmobility except nCT  2(const)

Ci , update, j , IR  Ci , update, j , GT
ALTERNATIVE SCHEMES (CONT.)
Fig. 6. Performance comparison.
CONCLUSION



This paper suggests a novel hybrid cache
management scheme to minimize the overall
network traffic incurred by mobility management,
cache consistency management and query service.
Simulation results reveal that hybrid cache
management scheme outperforms pure push-based
and IR-based schemes.
Over a long time period, the network traffic
communication cost saving due to optimal selection
of the threshold T and service area would be
significant.
QUESTIONS