Transcript Part 2

Mobile Data Management
Instructor – Sanjay Madria
Lesson Title - Location Management
1
Personal Communication System (PCS)
A system where wired and wireless networks are integrated for
establishing communication.
PSTN
AC
HLR
VLR
MSC (MTSO)
MSC (MTSO)
BS
Wireless component
EIR
MS
MS
PSTN: Public Switched Network.
MSC: Mobile Switching Center. Also called MTSO
(Mobile Telephone Switching Office).
BS:
Base Station.
MS:
Mobile Station. Also called MU (MobileUnit)
or Mobile Host (MH).
HLR: Home Location Register.
VLR: Visitor Location Register.
EIR:
Equipment Identify Register.
AC:
Access Chanel.
2
Personal Communication System (PCS)
Wireless Components
MSC (MTSO)
BS
MS
MS
Wireless
component
Cell
3
Personal Communication System (PCS)
Mobile cells
The entire coverage area is a group of a number of cells.
The size of cell depends upon the power of the base
stations.
MSC
PSTN
4
Personal Communication System (PCS)
Problems with cellular structure
 How to maintain continuous communication
between two parties in the presence of
mobility?
Solution: Handoff
 How to maintain continuous communication
between two parties in the presence of mobility?
Solution: Roaming
 How to locate of a mobile unit in the entire
coverage area?
Solution: Location management
5
Personal Communication System (PCS)
Handoff
A process, which allows users to remain in touch, even
while breaking the connection with one BS and
establishing connection with another BS.
MSC
MSC
New BS Old BS
Old BS
MSC
MSC
Old BS
New BS
New BS
Old BS
New BS
6
Personal Communication System (PCS)
Handoff
To keep the conversation going, the Handoff
procedure should be completed while the MS (the bus) is
in the overlap region.
Cell overlap region
G
Old BS
New BS
7
Personal Communication System (PCS)
Roaming

Roaming is a facility, which allows a subscriber to
enjoy uninterrupted communication from anywhere in
the entire coverage space.

A mobile network coverage space may be
managed by a number of different service providers.
They must cooperate with each other to provide
roaming facility.

Roaming can be provided only if some
administrative and technical constraints are met.
8
Personal Communication System (PCS)
Roaming
Administrative constraints
 Billing.
 Subscription agreement.
 Call transfer charges.
 User profile and database sharing.
 Any other policy constraints.
9
Personal Communication System (PCS)
Roaming
Technical constraints
 Bandwidth
mismatch.
For example,
European 900MHz band may not be available
in other parts of the world.
 Integration of a new service provider into the
network. A roaming subscriber must be able
to detect this new provider.
 Service
providers must be able to
communicate with each other. Needs some
standard.
 Mobile station constraints.
10
Personal Communication System (PCS)
Roaming
Two
basic
operations
management are
 Registration
(Location
in
roaming
update):
The
process of informing the presence or
arrival of a MU to a cell.
 Location tracking: the process of locating
the desired MU.
11
Personal Communication System (PCS)
Roaming
Registration (Location update): There are six different
types of registration.
 Power-down registration. Done by the MU when it
intends to switch itself off.
 Power-up registration. Opposite to power-down
registration. When an MU is switched on, it
registers.
 Deregistration. A MU decides to acquire control
channel service on a different type of network
(public, private, or residential).
12
Personal Communication System (PCS)
Roaming
Registration (Location update): There are six different
types of registration.



New system/Location area registration: when the
location area of the MU changes, it sends a registration
message.
Periodic registration:
A MU may be instructed to
periodically register with the network.
Forced registration: A network may, under certain
circumstances, force all MUs to register.
13
Personal Communication System (PCS)
Registration
Two-Tier Scheme
HLR: Home Location Register

A HLR stores user profile and the
geographical location of each moving object at
a pre-specified location
 VLR: Visitor Location Register
A VLR stores user profile and the current
location who is a visitor to a different cell than
its home cell.
14
Personal Communication System (PCS)
Registration
Two-Tier Scheme steps. MU1 moves to cell 2.
Cell 1
Cell 2
MU1
MU1
15
Personal Communication System (PCS)
Registration
Steps
1.
MU1 moves to cell 2. The MSC of cell 2 launches a
registration query to its VLR 2.
2.
VLR2 sends a registration message containing MU’s
identity (MIN), which can be translated to HLR address.
3.
After registration, HLR sends an acknowledgment back
to VLR2.
4.
HLR sends a deregistration message to VLR1 (of cell 1)
to delete the record of MU1 (obsolete).
VLR1
acknowledges the cancellation.
16
Personal Communication System
(PCS)
Location tracking (MU2 wants to comm with MU1)
Steps
1.
VLR of cell 2 is searched for MU1’s profile.
2.
If it is not found, then HLR is searched.
3.
Once the location of MU1 is found, then the
information is sent to the base station of cell 1.
4.
Cell 1 establishes the communication.
17
Locating Objects in Mobile Computing
Location Management
Lookups and updates
Introduction
• Our target is objects capable of changing their
location
• We are interested in objects with identity
• We store user locations in multiple databases
(DBs)
• Main questions:
 How do we update data when user moves?
 How do we locate user in DBs when it is
required?
19
Locating Moving Objects
• Example of moving objects

mobile devices (cars, cellular phones, palmtops, etc)

mobile users (locate users independently of the device they are
currently using)

mobile software (e.g., mobile agents)
• How to find their location - Two extremes

Store their current location everywhere
 Search locally
 Cost of updates

Search everywhere
 No information is stored anywhere; search is expensive
 No cost of updates

Searching verses Update Cost
20
Availability – either at all sites or at
selective sites (frequently visited sites)
 Currency – Stored location is always
updated (it may not make sense if user
moves very frequently)
 Precision – Exact location verses set of
possible locations

21
Locating Moving Objects
the whole
network
Exact
location
Availability
• What (precision), where (availability) and when (currency)
to store
at all sites
At selective sites (e.g., at
frequent callers)
nowhere
Never
update
Always update (at each
movement)
22
Overview
• Database schemas
 Two-tier
 Hierarchical
• Replication:
 Working set replication
 Replication in hierarchical schema
• Forwarding pointers:
 Two-tier schema
 Hierarchical schema
23
Architectures of Location DBs
• Two-tier Schemes (similar to cellular phones)


Home Location Register (HLR): store the location of
each moving object at a pre-specified location for the
object
Visitor Location Register (VLR): also store the location
of each moving object at a register at the current region
• Hierarchical Schemes
 Maintain multiple registries
24
Two Tier Scheme
• HLR – Home Location Register is associated with
each mobile user, maintains current location of
the user as part of the user’s profile
• HLR is located at a network location pre-specified
for each user
• To locate X, X’s HLR is queried
• When X is moved to new zone, X’s HLR is
contacted and updated
• Disadvantages : Global move is expensive
25
Two-tier Location DBs
• Search
 Check the VLR at your current location
 If object not in, contact the object’s HLR
• Update
 Update the old (delete) and new VLR (insert)
 Update the HLR
26
Two-tier Schema- Enhancement
• User’s X profile is permanently stored in
Home Location Register (HLR)
VLR…|HLR-X
• Each site maintains Visitor Location
Register (VLR), stores info about users
not at their home location
• During lookup at VLRi:


VLRi is queried for X location
HLR of X is queried upon failure
• During move from i to k:
VLR
…
i-X|HLR
VLR
i…|HLRi
i…
VLRk-X|HLRk…



X’s HLR is updated
X’s profile is deleted from VLRi
X’s profile is added to VLRk
27
Two-tier Schema Cont.
VLR…|HLR-X
– Does not support locality

search in nearby locations
impossible, always need to reg.
with HA

possible distant HLR is always
contacted upon move
– Home Location register is permanent

resettlement is not supported

Does not scale well; Home
location is always contacted
VLR
…
i-X|HLR
VLR
i…|HLRi
i…
VLRk-X|HLRk…
+ Relatively simple
max 2 operations for lookup
3 operations for update
28
Standards
• EIA/TIA (Electronic Indus Asso.) and GSM(Global System
for mobile Comm.) – Use HLR and VLR
• Mobile-IP - Two IP addresses – Home address and Careof –Address (Current point of attachment)
• Care-of-address is either the address of FA or IP address
acquired by the node in the current network
• Mobile node registers its care of address with its home
address
29
Hierarchical Schema
X
X
4
8
5
9 10 12 13 14
X 12
Y 16
Y 16 3
2
X
1
Y 16 6
7
15 16 17 18 19 20
Y 16
• A hierarchy of location
databases is maintained
• Internal node maintains
information about user
registered in the set of zones in
its subtree
• Leaf node contains actual
location of objects in its
coverage
• Intermediate node contains
location information for all
objects covered by its children
in a form of:

Pointers to lower level DBs
or

Actual location of each object
30
Hierarchical Scheme
• LCA(I,j) – least common ancestor of nodes I and j
• Parameter that affect the performance of the most location
management scheme


Relative frequency of the move
Call operations of each user
• Call to mobility ratio (CMRi) = Ci/Ui
Where Ci is the expected number of calls to user Pi over a period T
and Ui the number of moves made by Pi over a period T
• LCMRij (local call to mobility ratio involves origin of calls)
= Cij/Ui
• For hierarchical scheme, LCMRij =  LCMRik where k is a
child of j; the call to mobility ratio for a user Pi and an
internal node j is the ratio of the number of calls to Pi
originated from any zone at J’s subtree to the number of
moves made by Pi
31
Lookup in Hierarchical Schema
X
X
4
8
1
2 LCA(8,12)
X
5
9 10 12 13 14
X 12
Y 16
LCA(19,16)
Y 16 3
Y 16 6
7
15 16 17 18 19 20
Y 16
• Whenever lookup for object X at
i is initiated at j:
• The tree is traversed from j
upwards to LCA(i,j)
Then
• Pointers are traversed
downwards from LCA(i,j) to i
• Location of X is found at i
(pointer case)
OR
• Location of X is found in LCA(i,j)
(actual location case)
• LCA(i,j) – Least Common
Ancestor of i and j
• Example: (j,i) = {(8,12), (19,16)}
32
Moving in Hierarchical Schema
• Whenever object X moves from
j to i:
• Pointers on the path
j,…,LCA(j,i),…i are altered
OR
• All databases on paths root,…,j
and root,…,i are updated with
new location of X
14
X
1
Y 16
14
X
Y 16 3
2
14
4
8
X
5
9 10 12 13 14
X
Y 16 6
7
15 16 17 18 19 20
Y
33
updates
• Pointer case - When user x moves from 15 to 18, the
entries at 18,7, 6, 3, 15 are updated ; x is deleted from the
database at 15 and 6, at 3 it is updated and are added at
18 and 7
• Actual location case – entries are updated at 0,
7,6,3,18,15
34
Evaluation of Hierarchical Schema
+ Mobile object is not bound to HLR
+ Advantage of locality moves and lookups is taken
– Increased number of operations
DB operations
Communication messages
– Increased load and storage requirements for DBs
Intermediate DBs store location information for all objects covered
by its children
Root DB stores location information for ALL objects
35
Partitions
• Avoid maintaining locations at all levels, reduce search
cost
• Partitions grouping zones for each user among which it
moves frequently
• Partition exploits locality
• Information whether a user is currently in the partition is
maintained at the LCA of all nodes in partition called
representative of the partition
• Representative does not know exact location
• Reduces overall search cost, increases update cost when
a user crosses partition, both representatives must be
informed
36
Locating Moving Objects
Partitions
P3
P1
P4
P2
User x
P5
User x
37
Overview
• Database schemas


Two-tier
Hierarchical
• Replication:


Working set replication
Replication in hierarchical schema
• Forwarding pointers:


Two-tier schema
Hierarchical schema
• Other topics
• Relation to KDE3 project
• Evaluation
38
Locating Moving Objects
• Caching
 cache the callee’s location at the caller side
(large Call to Mobility Ratio)
• Replication
 replicate the location of a moving object at its frequent
callers (large CMR)
• Forwarding Pointers
 do not update the VLR and the HLR, leave a forwarding
pointer from the old to the new VLR (small CMR)
 When and how forwarding pointers are purged?
39
Caching – Two Tier Scheme
• Current location of the callee may be reused by
subsequent calls originated from same region
• Every time a user x is called, its location is cached at the
VLR in the caller’s zone so it can be reused
• Caching is useful for those users who frequently receives
calls relative to the rate at which they relocate
• To locate a user, the cache at the VLR of the caller’s zone
is queries first, if found then query is launched to the
indicated zone without contacting the user’s HLR else
HLR is queried
40
Caching – Hierarchical scheme
• When a call is made from zone i to user x located at zone j, the search
traverse from i to LCA (i,j) and then down to j, Ack is returned back to i
from j
• Forward and Reverse bypass pointers

Forward bypass is an entry at an ancestor of i, say s, that points to
ancestor of j, say, t

Reverse is from t to s
• During the next call from zone i to user x, search will travel until s then
follow t via LCA (i,j) or via a shorter path
• In case of simple caching, s and t can be at the leaf while in level
caching, s and t belongs to any level and possibly to a different one.
• Placing a bypass at higher level node s makes this entry available to
all calls made in s’s subtree, but will travel long path to reach s
• Placing high node t will increase lookup cost, cache entry remains
valid as long as the user move’s inside t’s subtree
41
Cache Invalidation
• Eager caching – Every time a user is moved new location,
all cache entries for this user’s location are updated
• Location of the cache entries must be centrally known,
failure of central location can cause problem
• Lazy caching – a move operation does not mean updating
cache
• When look up, either the user is still in the indicated
location or it has moved out (cache miss)



Cache miss- HLR is contacted and then cache is updated
Cache update only on cache miss
Overhead – cache location must be visited first
• Saving of lazy caching over eager caching if hit ratio
threshold for a user in a zone must exceed the (cost of
lookup when there is a hit) / (the cost of lookup in noncaching scheme). Depends on querying HLR and VLR
42
Replication
• Location (profile) of selected users is replicated at
selected sites:



Enhances lookup response time
Reduces network load during lookup
Creates overhead during updates
• Replication is judicious if following holds:
  C i , j   U i



(1)
C i , j number of lookups for object i from location j during T
U i number of updates for i during T
 - savings per lookup;  - cost per update
• Additional parameters: service capacity of DBs, etc.
• Replication is possible at both caller and receiver locations
43
Working Set Replication
X
5
1
X
4
2
(1)? 6
• Applicable to two-tier schema
• Replicas are kept at frequent callers of X
– working set of X
• Equation holds for every member j of the
set:
(1)
  C x, j   U x
• Every time a call to X is made:

7
8
From a member of a set –
no updates required
From nonmember k of a set –
if (1) holds for k, k is added to the set
• Every time X moves:
3

9

(1) is evaluated for each member of X
working set
If (1) does not hold for member k, it is
removed from the set
44
Replication in Hierarchical Schema
• Takes advantage of locality in
movement
• Local Call to Mobility Ratio is
used to determine feasibility
2
1
+
1
LCMRi , j
3
2
•
+
4
8
+
+
6
5
9 10 12 13 14
Ci ,8 
…
 C i ,1 4
7
15 16 17 18 19 20

k
C i ,k
Ui
S max and S min are thresholds for
determining replication of nodes
• If LCMRi , j  S max , j is assigned a
replica
• If LCMRi , j  S min , j is not used for
replication
• If S min  LCMRi , j  S max , database
depends on topology of network
Ui
45
Overview
• Database schemas


Two-tier
Hierarchical
• Replication:


Working set replication
Replication in hierarchical schema
• Forwarding pointers:


Two-tier schema
Hierarchical schema
46
Forwarding Pointers (two-tier schema)
VLR…|HLR-X
VLR
-X
|HLR…
…i…
i-X|HLR
VLR
i…|HLRi
i
VLRkk-X
-X|HLR
VLR
|HLRkk……
VLRn-X|HLRn…
• Pointers could be used to reduce
communication overhead and query
load at the HLR
• When X moves from i to j a pointer
from VLR at i to VLR at j is added
• During lookup if no information on X
is found at current VLR, HLR of X is
queried and pointers are followed
• Chain of pointers is managed not to
exceed length K
• Useful for users receiving calls
infrequently and reallocate often
• It has been showed that cost
savings for K<5, C i ,k U i  0.5 are
20%-60%
47
Forwarding Pointers (hierarchical schema)
• Updating and lookup in
hierarchical schema lack
efficiency when LCA(i,j) is at
higher levels
• Consider schema with entries as
pointers to lower level DBs
• In simple forwarding a forwarding
pointer connects two leaf nodes
LCA(12,15)
1
X
1
X
X
2
X
2
Level forwarding
3
3
X

4
8
4
X
X
5
5
6
X
6
7
7
9 10 12 13 14 15 16 17 18 19 20
8 9 10 12 13 14 15 16 17 18 19 20
X X
X
Allows cheaper updates
• In level forwarding a forwarding
pointer connects two
intermediate nodes

Allows cheaper lookups
Simple forwarding
48