Transcript Document

Lecture 09 Location Management
第9讲 移动位置管理
§9.1
§9.2
§9.3
§9.4
LM Basics
LM in Cellular Networks
LM in Ad Hoc Networks
Mobile IP
LBS App.
What’s It?
 Location is useful
Location Management
Localization
Module
Geographic
Information
System
Communication: call forwarding , data forwarding
Location based services
 Location is?
Geographical coordinate
Cell ID
IP addr…
A special kind of data value in a mobile data management system.
A data item whose value changes with respect to time.
 Location management.
The maintenance of the binding between the logical identifier and
physical location of the user.
Key Issues in Location Management
 A mobile user creates uncertainty of his/her exact location.
 How to know the current location?
From localization/positioning system
 Where to store the location information?
Location database
 What to do for new location?
Location update
 Who to maintain and provide location information?
Location server, with cooperation from clients
Location Services
 Location services are provided by a location server.
 Location server manages a location database, which holds
user location.
It receives user position updates and stores into the location
database.
 Location database (also called moving object database)
contains location information about mobile users.
Mobile users or moving objects have their identity.
Current user locations are stored in multiple databases or
replicated databases.
 Location information is queried by different agency at
different places to achieve their functionality, e.g.
location-based services.
Locating Moving Objects
 Moving objects:
Mobile devices, Mobile users, Mobile software
 Two extremes to find their current location:
Store everywhere: Cost of location update is very high.
Full replication of location
Allow search to be performed locally (fast).
Search everywhere: No cost of update
No location information is stored anywhere.
Searching is performed on demand everywhere (expensive).
 One should balance between search and update costs.
Perform location update to certain key places
Search within some area
Availability
Locating Moving Objects
At all sites
At selected sites
(e.g., at frequently calling cells)
The whole
network
Nowhere
Exact
location
Never
update
Always update
(at each movement)
Locating Moving Objects
 Three design issues:
Where: availability
At all sites, at selected (frequently visited) sites or at no site.
When: occurrence
Stored location is always updated, updated periodically, or never
updated.
What: precision
Exact location, within a set of possible locations, or any location
within network.
 Two basic operations:
Paging
Search initiated by system to find the mobile unit.
Server broadcasts a search message and target replies via uplink
channel.
Update
Impose an upper bound on the location uncertainty.
Mobile unit sends update message via uplink channel.
Cost of Location Management
 Cost of Location Management System (LMS) includes
Number of database updates
Number of messages, size of messages and distance the messages
need to travel.
 Major parameters
Relative frequency of the move.
Call operations of each user.
 Call to Mobility Ratio (CMR):
the number of calls made to a user during a period / the number of
location updates generated by the user.
High CMR “always update”
Low CMR “paging” is better.
Paging
 To locate a mobile user by querying/searching
Look up the location database if it is accurate.
 Simultaneous paging
To page simultaneously in the cells where the user may be located.
Short response time
 Sequential paging
Paging cells in the order of descending probability
Low paging cost
 A hierarchical solution
Group related or neighboring cells within the area served by the
Message Service Center (MSC) into location areas.
Simultaneous in one area, sequential among areas
Location Update
 Observation:
it is not necessary to always update, since an object is likely
to be near its last location.
The vicinity of the last update information gives the most
probable location of the mobile user.
 Static scheme vs. Dynamic scheme
Predefined update occurrence
Dynamic decided update occurrence
Location Update
 Static update scheme: global information is needed.
Group cells into location areas as before.
All location areas contain non-overlapping groups of cells.
Mobile user sends update when it crosses a location area
boundary.
Advantage: low update cost.
Disadvantage: accuracy is only to location area.
Selection of designated reporting cells.
Mobile user must send in updates when they enter some
designated cells.
Advantage: optimal set of reporting cells can be computed.
Disadvantage: determining the optimal set is expensive.
Location Update
 Dynamic update scheme:
update based on local information and initiated by client,
i.e., the place where the update takes place is dynamic,
as determined by client.
Distance-based
Update when the Euclidean distance (or Manhattan distance) to
the previously updated location exceeds a threshold.
Movement-based
Update when the number of cell boundaries crossed since last
reporting reaches a threshold.
Time-based
Update when the time to the previous update exceeds a
threshold (i.e., periodic updates).
§9.2 LM in Cellular Networks
 General scheme
 Location Management Architecture
Two-tier.
Hierarchical
Centralized
 Techniques for Efficiency
Caching
Replication
Forwarding pointer
Location Management in GSM
 The Mobility Management layer (MM) is built on top of the
Radio Resources Management (RR) layer.
MM handles the functions due to mobility of subscriber and
authentication and security aspects.
 A mobile phone that is powered on is informed of an
incoming call by a paging message sent over the PAGCH
channel of a cell.
 Paging vs. update:
Page each cell in the network for each call
Costly paging, suitable for few call but much movement
Page exactly one cell but requires the mobile phone to send updates
each time it changes cell:
Costly update, suitable for many calls but little movement
Location Management in GSM

Compromised solution used
in GSM is to group cells into
location areas.
A location area is a
collection of adjacent cells.




Update required only when
moving between location
areas.
To search, mobile units are
paged in the cells of their
current location area.
HLR: home location register
VLR: visitor location register
AuC- Authentication Center
EIR – Equipment Identity Register
Location Management in GSM
 HLR (Home Location Register)
Maintains the current location of a user as part of the user’s profile.
At a network location pre-specified for each user U (the home zone).
When U moves from zone A to zone B, the HLR for U is updated.
To locate a user U, the HLR for U is queried to get U’s current
location.
 VLR (Visitor Location Register)
Holds information about a visiting user who moves out of its home zone.
VLR contains a copy of the profile of a visiting user V.
(To reduce the expensive querying cost at remote HLR)
When V moves from zone A to zone B,
Entry for V will be removed from the VLR at zone A and
The corresponding entry will be inserted to the VLR at zone B.
Location Update in GSM
 When mobile phone moves to a new location area:
Location update msg is sent to new MSC/VLR via base
station.
If mobile phone is authorized in the new MSC/VLR, it
determines the subscriber’s HLR from the mobile
identification number.
HLR sends reg. ack. msg to new MSC/VLR and
sends reg. cancellation msg to old MSC/VLR to cancel
its VLR entry
 Periodic location updating
After the updating time period, if the mobile phone has
not registered, it is then deregistered.
Call Delivery in GSM
 Calling phone sends call initiation signal to MSC via a base
station.
 MSC determines address of HLR of called phone and sends it
a location req. msg.
 HLR sends a route req. msg to the MSC/VLR currently
serving the phone.
 MSC/VLR allocates a temporary local directory number to
the called phone and replies HLR with this number.
 HLR forwards this info. to the MSC of calling phone.
 The MSC of calling phone requests a call setup to the MSC of
called phone.
MSC 1
MSC 2
VLR
USER
VLR
A
INFO
HLR
USER
VLR
HLR
HLR
To other
MSCs
A
CURR
LOC
MSC2
Fixed Network
VLR
VLR
A
INFO
HLR
Change from MSC2 to MSC3
on second movement
USER
MSC 3
INFO
Location Management in GSM


IMSI: international mobile subscriber identity
TMSI: temporary mobile subscriber identity
Location Management in 3G
 Besides HLR and VLR, there is GLR
 Gateway Location Register:
Between HLR and VLR, like the agent in the CAS model.
GLR contains roamer’s profile and location information.
GLR can interact with multiple VLR in the visitor network.
 GLR handles location update from VLR by behaving like HLR.
 Local location update: at GLR
Location Management Architecture
 Two-tier.
Only HLR and VLR.
HLR contains actual location of user.
To search, contact VLR first. If not found, ask HLR.
 Hierarchical.
Inserts multiple layers between HLR and VLR.
HLR contains actual location of user (direct or indirect).
To search, contact leaf. If not found, traverse up the tree.
 Centralized database.
A single location database containing all location info.
Two-Tier Scheme
MSC
MSC
HLR
HLR
VLR
VLR
MSC
VLR
MSC
VLR
Two-Tier Scheme
 Advantage:
Simple architecture and management.
A maximum of 2 operations for each lookup.
Only 3 operations for each update.
 Disadvantage:
Does not support locality.
Searching in nearby locations is impossible.
Always need to register with HLR at a possibly far distance
upon a move, even if the move is just to a neighboring cell.
Home Location Register is permanent.
Resettlement is not supported: users who had moved to new
region permanently still contact old HLR.
Does not scale well to larger distributed systems since HLR is
always contacted.
Hierarchical Scheme
pointer scheme
X
1

Y 16
location scheme

X
4
8
Y 16 3
2
X
5
9 10 12 13 14
X 12
Y 16 6
7
15 16 17 18 19 20
Y 16
To avoid contacting remote HLR and
to serve neighboring search, multiple
registers are used.
A hierarchy of location databases is
maintained.
Internal node contains information
about user registered in the set of
zones in its subtree.
Leaf node contains actual location of
objects in its coverage.
Internal node contains information
about users registered and their
location, which are covered by the
children nodes.
Two types of schemes:
Pointers to lower level database (e.g.,
find X via pointers to 12).
Actual location of each object (find
Y directly at 16).
Hierarchical Scheme
X
1

Y 16

X
4
2 LCA(8,12)
X
5
LCA(19,16)
Y 16 3
Y 16 6
7



8
9 10 12 13 14
X 12
15 16 17 18 19 20
Y 16

Let LCA(i, j) denote the least common
ancestor of nodes i and j.
To search for object Y which is
currently at node i (i.e., 16) initiated by
a user at node j (e.g., 19).
Go up the tree from j until LCA(i, j) is
reached, where Y is found, with its
actual location at 16.
To lookup for object X at node i (i.e.,
12) initiated by a user at node j (e.g., 8).
Go up the tree from j to LCA(i, j) is
reached, where X is found.
Follow the pointer for X until X is really
found at 12.
Hierarchical Scheme

Databases along path i, …, LCA(i, j), …, j
are to be updated.
17
X
1
Y 16
Entries for X from i to the node just below
LCA(i, j) are deleted.
Entries for X are created from the node just
below LCA(i, j) to j, each pointing to the
proper child.
Entries for X at LCA(i, j) is updated to
point to the proper child.
17
X
Y 16 3
2
For example X moves from 12 to 14.

17
4
8
With pointer, to update X from i to j:
X
5
9 10 12 13 14
X
Y 16 6
7
15 16 17 18 19 20
Y
With location, to update Y from i to j:
Databases from i to LCA(i, j) and from
root to j are to be updated.
Entries for X from i to the node just below
LCA(i, j) are deleted.
Entries for X are created from the node just
below LCA(i, j) to point to j.
Entries for X from root to LCA(i, j) are
updated to point to j.
For example Y moves from 16 to 17.
Hierarchical Scheme
 Advantage
Mobile object is not bound to HLR.
Locality of moves and lookups is possible.
It is fast to search for a user nearby.
 Disadvantage
Seemingly increased number of communication messages.
Increased load and storage requirements for intermediate
databases.
Intermediate databases store location information (actual location
or a pointer) for all objects covered by its children.
Root database stores location information for ALL objects.
Centralized Database




To simplify location query and update, a centralized database can be
assumed to contain the location of all objects.
Centralized database solution is often adopted for simplicity if the
object moves continuously, reporting its location.
Recall in previous schemes, location of object is only accurate up to the
cell.
A spatial database is often used to store an object location for fast
querying, with additional features for moving objects.
Additional operations supported include nearest neighbor search (find the
closest gas station), range query (find restaurants within 5 minutes drive),
and k-nearest neighbors.

Recall that in the centralized database, there could be numerous objects.
Cost of full scan is prohibitive and update is expensive.
Specially designed databases are needed for that purpose.
Centralized Database
 To reduce update cost, object movement can be predicted.
Predicting object movement, then an object that does not deviate
from its predicted location does not need to send in an update.
 Trade off can be made with respect to the frequency of
updates for lower accuracy.
Send an update only when distance, movement, or time elapsed
exceed certain threshold.
 Group-based approach:
A group of objects that stay close to one another can have their
aggregated location reported together via the group leader.
 Safe-region approach:
As long as an object stays within its safe region, no update is
needed, since server knows that object is within that safe region.
Size of safe region may be adjusted dynamically according to
actual query need (an object seldom interested should update
location less).
Centralized Database
 Time-based, movement-based and combined updating example.
a
h
b
c
d
g
f
e
Centralized Database
 Distance-based example.
a
b
4
5
5
g
c
3
7
h
2
2
d
8
5
3
6
f
e
Location
a
b
c
d
c
b
d
g
f
e
f
g
d
b
a
Distancebased (D=3)
a
b
-
d
-
b
d
g
f
e
f
g
d
b
a
Distancebased (D=4)
a
b
-
-
-
-
-
g
f
e
f
g
d
-
a
Distancebased (D=6)
a
-
c
-
-
-
-
g
-
e
f
-
d
-
a
Centralized Database
 Group-based example with 3 groups.
There are algorithms to form and maintain the group membership.
Techniques for Efficiency
 One may perform caching of location of moving object to
reduce need to send in query.
Cache the moving object location (e.g. callee’s location) at the caller
site.
This is effective with large CMR.
 One may extend caching into replication with multiple copies
of the location.
Replicate location of a moving object at its frequent callers.
This is also effective with large CMR.
 Forwarding pointers is used to reduce updates to VLR and
HLR.
Do not update VLR and HLR.
Just leave a forwarding pointer from old VLR to new VLR.
This is effective with small CMR.
Caching
 To locate a user U, the cache at the VLR of caller’s zone
is queried first, before contacting U ’s HLR.
 In two-tier scheme, caching enhances VLR and HLR.
If user U at L1 is called by user A at L2. VLR at L1contains U.
Cache at L2 can then indicate that U is at L1.
Subsequent calls originated from L2 can directly contact U
without having to look for U’s HLR.
 Two caching schemes:
Eager caching: when a user is moved to a new location, all cache
entries for this user’s location are updated.
Lazy caching: a move operation does not automatically translate
to a cache update.
With lazy caching, during a lookup, either user is still in
indicated location (cache hit) or has moved out (cache miss).
Replication
 One can create copies about this information at selected
sites (e.g., at hubs).
Improve lookup response time.
Reduce network load during lookup.
Generate additional overhead during location update.
 Replication should be made judiciously for high CMR.
More precisely, if Local CMR (LCMRi,j), i.e., number of lookups
for user X in zone i from zone j during a period / number of location
updates of X is greater than a threshold  ( = cost of update / cost
saving with local lookup).
 Replication may also be performed to indicate the
approximate user location (e.g., current partition).
Replication
X
5
1
4
X


2

(1)? 6
8
3





7
9

(2, 3) are in working set. 
Y (at 6) queries X (at 1).
6 is added to working set
if inequality is true.

Now X moves to 5.
The working set (2, 3, 6)
needs updating.
Working set replication is applicable to twotier scheme.
For each user X, replicas are kept at frequent
callers of X. This is called the working set of X.
Ensure that for all j, LCMRi,j for X in zone i
from zone j  cost of update / cost saving with
local lookup.
When a call to X is made from zone k:
If k is in working set, no update is needed.
If k is not in working set but the above
inequality holds for k, k is added to the set.
When X moves, the inequality is evaluated for
each member k in the working set of X:
If it does not hold for k, k is removed.
Performance is affected by CMR.
Forwarding Pointers

VLR…|HLR-X




X moves from i to k.
Instead of changing
HLR for X, setup
forwarding pointer at
i to k.
Now X moves to n
again, and forwarding
pointer is added to k.
-X
|HLR…
VLR
…i…
i-X|HLR
VLR
i…|HLRi
i
VLRkk-X
-X|HLR
VLR
|HLRkk……
VLRn-X|HLRn…



Invalidation to caching and replication
can be expensive, with low CMR (e.g.,
CMR < 0.5).
One can provide forwarding pointers
to point to the potential current location
(ProbLoc). This reduces
communication overhead and query
load at remote HLR.
In two-tier scheme, when X moves
from i to k, a pointer is added at VLR
at i to point to VLR at k without
informing HLR.
During lookup if no information on X
is found at current VLR, HLR of X is
queried for proper VLR and follow the
forwarding pointers.
Chain of pointers should not exceed a
length of K. Typical value of K < 5.
Forwarding Pointers

X moves from 12 to 15 without
forwarding.
LCA(12,15)
1
X
X
4
8
2
X
X
5
9 10 12 13 14
X
X
6
3
7
15 16 17 18 19 20
 Forwarding pointers can be
used also in hierarchical
scheme.
 Recall how a location update
is done: entries along path
from old cell to LCA then new
cell, plus those coming from
root need to be updated.
 Use similar idea as bypass
pointers in caching, create
forwarding pointers to point to
new location.
Forwarding Pointers

Example that X moves from 12 to 15 with pointer and location schemes.
X
X
4
8
X 12 1
1
X
5
9 10 12 13 14
X
6
3
X 12 2
3
2
4
7
15 16 17 18 19 20
8
6
X 12 5

9 10 12 13 14
X 12
X 15
7
15 16 17 18 19 20
X 15
Pointer Purging

There is a need to purge the forwarding pointers.
Save storage.
Avoid storing stale information.
Improve lookup efficiency by compressing forwarding chain.



User X moves from 11 to 18 to 26 then to 14.
Pointers in 11, 18, 26 can be purged.
Pointers in interior nodes leading to these nodes can be purged.
Other Issues

Concurrency control
Location and pointer updates occur asynchronously. It is possible that a
user has moved but a caller follows the old pointer down (and cannot
reach the user).
Transactions for update are too expensive (lock too many entries).

Recovery
Nodes may crash, and information should be restored upon node
recovery. This demands periodic checkpointing of information at HLR
and paging for mobile users by VLR.

Precision, currency and performance tradeoff
Finer location granularity within cell is possible, with more frequent
reporting from client. Both translate into higher update cost.
Server can keep a predication of the client location/trajectory, and client
detects whether it is within allowable distance from the predication.
Update/paging is only sent when deviation is too large.

Service discovery
Services provided by a host are similar to its location, i.e., can be
registered with service (location) database for lookup. In mobile
computing, host providing services may move. Calls (e.g., remote
procedure calls) need to be routed to the moving host.
§9.3 LM in Ad Hoc Networks
 Location in Mobile Ad Hoc Networks
Used as basic of routing protocol
Location based services (LBS)
Location dependent applications
E.g. data collection
 Major Issues
Distributed location data storage
Distributed query
Failure resilience
Scalability
Categorization of LM in Ad Hoc Networks
 Proactive LM: periodically exchange location information
Some-for-some
Some-for-all
All-for-some
Home region based
Quorum node based
All-for-all
Location dissemination
 Reactive LM: discover location on demand
Host Region based Approach




Similar to HLR/VLR in cellular networks
Region: a rectangle or a circle area
Nodes  Region  location server
Location initialization
Broadcast or mapping function
 Trigger of update
timer-based (i.e., periodic updates),
distance-based (i.e., moved more than a threshold)
predictive distance-based
Threshold of difference between predication and actual location
 Location update
Send update to nodes in home region
Via a geographical forwarding protocol
Problems?
Quorum-based Approach
 Quorum?
The minimum number of votes that a distributed
transaction has to obtain in order to be allowed to
perform an operation – Wikipedia
 Quorum for location management
Update: to what nodes to send location update
Query: to what nodes to query location information
There must be intersection between the nodes get the
update and the nodes be queried.
Please Give a naive example of quorum.
Uniform Quorum System (UQS)
 Quorum construction
A subset of the network nodes are chosen that best serve
as the network's virtual backbone
Quorums are then defined as subsets of the VB nodes,
such that any two quorums intersect.
 Location update
Sends new location information to the nearest VB node
The VB node forward the update to a quorum of nodes
 Location query
Similar to update
Column/Row Quorum
 A node's column
All the nodes to the north and south of the node's
current location
The thickness of the column can be configured
 A node’s row
Similar to column, but in west and east direction
 Update
To the column nodes
 Query
To the row nodes
Column/Row Quorum
 The void region problem: special mechanism to
address it.
Grid Location Service (GLS)
 The set of location servers is determined by a
predefined geographic grid and the ordering of node id.
 Key issues
Location server selection,
Location query request, and
Location server update
Location Server Selection in GLS
 Hierarchical grids
Order-1
Order-2
Order-3
Location Server Selection in GLS
 A node x
choose three
servers in each
grid order
 The node that
has the least ID
greater than x
in that order
square.
Location Query Request in GLS
 Query request is forwarded to a node with ID the least
greater than or equal to the destination ID, within the
order-2 and then higher square
using geographic forwarding
Location Server Update in GLS
 When a node moves a given threshold, it must send an
update packet to all of its location servers.
 To avoid excessive update traffic, the update frequency
is calculated using a threshold distance and the location
servers' square order
Location query failures when?
How to handle it?
Doubling Circles
 Similar to GLS
 Arranges the network into circles of increasing size
centered on a node's location;
 The radius of each subsequent circle is one meter
larger than the radius of the previous circle.
Location Info. Dissemination Approach
 LEAP, Legend Exchange and Augmentation Protocol
 Two location tables
Local table at each node
Legend, token like table
 Two messages
Hello: exchange location info. between neighbors
Legend: traverse the network
With list of locations collected
To collect location info.
To disseminate location info.
Reactive LM
 A location table at each node
 To locate a node
Check the location table, then
Ask neighbors in a specific scope (with TTL), then
Flood request packet in the entire network.
§9.4 Mobile IP
 IP assumes end hosts are in fixed physical locations
What happens if we move a host between networks?
 IP addresses enable IP routing algorithms to get
packets to the correct network
Each IP address has network part and host part
This keeps host specific information out of routers
DHCP is used to get packets to end hosts in networks
This still assumes a fixed end host
 What if a user wants to roam between networks?
IP Routing Breaks Under Mobility
.50
.52
.53
router
137.30.2.*
.200
router
139.20.3.*
Why this hierarchical approach? Answer: Scalability!
Millions of network addresses, billions of hosts!

Mobile IP Basics
 To allow a mobile host to move about without
changing its permanent IP address
 Standards
Mobile IPv4: IETF RFC 5944, IETF RFC 4721
Mobile IPv6: RFC 6275
Mobile IP Entities
 Mobile Node (MN)
The entity that may change its point of attachment from network to
network in the Internet
Detects it has moved and registers with “best” FA
Assigned a permanent IP called its home address to which other
hosts send packets regardless of MN’s location
Since this IP doesn’t change it can be used by long-lived applications
as MN’s location changes
 Home Agent (HA)
This is router with additional functionality
Located on home network of MN
Does mobility binding of MN’s IP with its COA
Forwards packets to appropriate network when MN is away
Does this through encapsulation
Mobile IP Entities
 Foreign Agent (FA)
Another router with enhanced functionality
If MN is away from HA the it uses an FA to send/receive data
to/from HA
Advertises itself periodically
Forward’s MN’s registration request
Decapsulates messages for delivery to MN
 Care-of-address (COA)
Address which identifies MN’s current location
Sent by FA to HA when MN attaches
Usually the IP address of the FA
 Correspondent Node (CN)
End host to which MN is corresponding (eg. a web server)
Mobile IP Operations
1.
2.
3.
4.
5.
MN travels to a foreign network and gets a new CoA.
MN performs a binding update to HA (new CoA registered ).
A CN wants to contact the MN. HA intercepts packets.
The HA then tunnels all packets to the MN
MN answers the CN
Mobile IP Support Services
 Agent Discovery
To determine where a MN is
 Registration
To registers MN’s COA with its HA
 Tunneling
To tunnel the data between CN and MN
Agent/Location Discovery
 Each mobile node is responsible for ongoing
discovery process.
Must determine if it is attached to its home network or a
foreign network.
 FA
Periodically broadcasts the ICMP Router Discovery
Protocol (IRDP) message
 MN
Listens for agent advertisement messages.
…
Compares the network portion of the router's IP address
with the network portion of the home address.
Agent Advertisement
Agent Advertisement
IRDP :
Type
Code
9 = Agent Advertisement, 10 = Agent Solicitation
0 = Advertising Agent is a fully capable router. 16 = only a Mobile IP agent
Num Addrs
The number of router addresses advertised in this message
Addr Entry Size
The number of 32-bit words of information per each router address
The maximum number of seconds that the router addresses may be
considered valid.
The sending router's IP address (es) on the i = 1..Num Addrs interface from
which this message is sent.
The preferability of each Router Address[i]
Lifetime
Router Address[i]
Preference Level[i]
Mobility Adv. Ext. :
Type
16 (Mobility Advertisement Extension)
Length
6+4*#COAs (6 = the sequence number, Registration Lifetime, Flags, and
Reserved fields + another 4 bytes per each COA)
Sequence Number
The count of Agent Adv. messages sent since the agent was initialized.
Registration Lifetime
The longest lifetime in seconds that the Registration Request will be
accepted by this agent. 0xffff = infinity.
Agent Solicitation
 Foreign agents are expected to issue agent
advertisement messages periodically.
 „If a mobile node needs the agent information
immediately, it can issue an ICMP router solicitation
message.
 …
Any agent receiving this message will then issue an
agent advertisement.
Care-of Addresses
 The address to forward data between MN and CN/HA
 Two choices
The address of the FA
Foreign agent delivers packets forwarded from home agent to
mobile host
Co-located address
IP address obtained by the MN on the foreign network
Temporary IP address obtained through an Internet service, e.g. DHCP
…
May be owned by the mobile node as a long-term address for roaming
Home agent tunnels packets directly to the temporary IP address
 Regardless, care-of address must be registered with home
agent
Move Detection
 How can a MN detect it has moved away?
 Algorithms to detect move:
Use of lifetime field
a mobile node uses the lifetime field as a timer for agent
advertisements.
…
Use of network prefix
a mobile node checks if any newly received agent
advertisement messages are on the same network as the
node's current care-of address.
Registration
 Via UDP, port 434
Registration Messages
Registration Procedure Security
 Mobile IP is designed to resist attacks:
A node pretending to be a foreign agent sends a
registration request to a home agent to divert the mobile
node’s traffic to itself.
…
An agent replays an old registration messages to cut the
mobile node from the network.
 The registration request and reply contain an
authentication extension
Fields = type, length, security parameter index (SPI),
authenticator
Registration Procedure Security
A random number (64 bits) for
avoid replay attacks
Type
31 = Mobile-Home, 33 = Mobile-Foreign, 34 = Foreign-Home
Length
4 plus the number of bytes in the Authenticator
Security parameter
index (SPI)
Identifies the Security Association (SA) for datagrams between two
nodes. SPI selects the authentication algorithm and secret keys either
shared or public to compute the Authenticator
Authenticator
A code used to authenticate the message. (variable length)
Default is 128-byte keyed MD5
Tables Maintained on Routers
 Mobility Binding Table
Maintained on HA of MN
 Visitor List
Maintained on FA
IP Tunneling
 HA intercepts all packets destined for MN
This is simple unless sending application is on or near the same
network as the MN
HA masquerades as MN
 HA forwards these packets to FA
IP tunneling
 FA decapsulates packets addressed to MN and forwards them
via hardware address
MN can perform FA functions if co-CoA is used
 Bidirectional communications require tunneling in each
direction
IP Tunneling
IP-in-IP Tunneling
Not support IP fragmentation
Path MTU discovery must be enabled
Generic Routing Encapsulation (GRE)
Routing Inefficiency
Mobile host and correspondent host
might even be on the same network!!
correspondent host
home agent
Route Optimizations
 Possible Solution:
Home agent sends current care-of address to
correspondent host
Correspondent host caches care-of address
Future packets tunneled directly to care-of address
 But!
An instance of the cache consistency problem arises...
Cached CoA becomes stale when the mobile host moves
Potential security issues with providing CoA to CN
Possible Route Optimization
Other Mobile IP Problems
 Single HA model is fragile
Possible solution – have multiple HA
 Frequent reports to HA if MN is moving
Possible solution – support of FA clustering
 Security
Connection hijacking, snooping…
 Many open research questions
Mobility in IPv6
 Route Optimization is a fundamental part of Mobile IPv6
Mobile IPv4 it is an optional set of extensions that may not
be supported by all nodes
 Foreign Agents are not needed in Mobile IPv6
MNs can function in any location without the services of any
special router in that location
 Security
Nodes are expected to employ strong authentication and
encryption
 Other details…
A Summary





Concept of location management
Key issues in LM
LM in cellular networks
LM in ad hoc networks
LM via MIP