INTERNET DRAFT P. Mutaf
C. Castelluccia
Date: September, 2001 INRIA
DPAC: Dynamic Paging Area Configuration
<draft-mutaf-dpac-00.txt>
Status of This Memo
This document is an Internet-Draft and is in full conformance
with all provisions of Section 10 of RFC 2026.
Distribution of this memo is unlimited.
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as
reference material or to cite them other than as ``work in
progress.''
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
This document defines dynamic paging area configuration extensions
to IP paging. The motivation is three fold: First, paging areas
are auto-configured, hence human effort is minimized. Second,
paging area shapes adapt to host mobility characteristics, hence
more efficient. Third, paging area sizes are variable, allowing
future optimization.
Dynamic paging area configuration can be regarded as the major
advantage of having L3 paging areas.
Mutaf, Castelluccia Expires February, 2001 [Page 1]
INTERNET DRAFT DPAC September 2001
Table of contents
1.0 Introduction .................................................. 2
2.0 Paging area model ............................................. 2
3.0 Dynamic paging area configuration ............................. 3
3.1 Sampling ................................................... 3
3.2 Paging area composition .................................... 4
4.0 Convergence of paging areas ................................... 4
5.0 Model of operation with relevance to DMHA protocol ............ 5
6.0 How to support DPAC in current DMHA protocol proposals? ....... 6
7.0 Picking the paging area size .................................. 6
8.0 Security considerations ....................................... 7
9.0 Conclusion .................................................... 7
References ........................................................ 7
Authors' Addresses ................................................ 8
1.0 Introduction
The DMHA (Dormant Mode Host Alerting) protocol offers IP paging
services to dormant mode capable Internet hosts in order to reduce
power and bandwidth consumption [PROB][REQ].
The flexibility of IP paging allows dynamic paging area configuration.
Manual paging area configuration is difficult, prone to human error
and not necessarily well adapted to user movement. This document
defines extensions for Dynamic Paging Area Configuration (DPAC) for
flexibility of administration and better paging performance.
DPAC aims to be scalable, low-cost and adaptive: Paging areas
should be available to millions of hosts regardless of their points
of attachment in a cellular system comprising millions of cells
(scalable). Furthermore, the cost of paging area configuration on
mobile host operation and bandwith consumption should be negligible
(low-cost). Finally, paging area shapes should adapt to hosts'
mobility characteristics in order to efficiently reduce the rate of
registrations. In addition, paging area shapes should adapt to the
changes in the cellular topology, e.g., the addition of a new
cell (adaptive).
2.0 Paging area model
A dynamically configured paging area is a list of network prefixes
(i.e. cells). The size of a paging area is the size of that list,
hence the number of cells. These paging areas have the following
properties:
+ Per-cell: There is a paging area corresponding (relative)
to each cell. Naturally, paging areas overlap.
+ Loadable: A host requests the network a pre-configured
paging area relative to its current cell.
+ Host-centered: A mobile host which obtains a new paging area
is initially at the center of that paging area.
Mutaf, Castelluccia Expires February, 2001 [Page 2]
INTERNET DRAFT DPAC September 2001
3.0 Dynamic paging area configuration
3.1 Sampling
A Cellular Sampling Agent (CSA) is a new function responsable for
collecting samples sent by mobile hosts moving in its domain.
A sample is an ordered pair of adjacent cells. Samples are generated
randomly by mobile hosts. Upon location registration, a mobile host
sends a sample to its current CSA with a very small probability
(e.g. 1%, 2%) so that sampling has no impact on power consumption
on mobile hosts nor bandwith consumption.
The identity of the host which sends a given sample has no
importance. This way DPAC captures the aggregated movement
characteristics which are more or less common to each individual
host. This sampling policy is at the heart of DPAC scalability.
Then, the collected samples give the "aggregated host direction
probabilities" in each cell of a CSA domain. In a given cell A, the
probability of a given direction is the probability of moving to a
corresponding cell in the neighborhood. For example, the samples
[A|B], [A|C], [A|D], [A|B], ... will help extract the direction
probabilities in cell A. This is illustrated in Figure 1.
+ +
/ \ / \
/ \ / \
+ + +
| G | B |
+ + +
/ \ / \ / \
/ \ / \ / \
+ + + +
| F | A | C |
+ + + +
\ / \ / \ /
\ / \ / \ /
+ + +
| E | D |
+ + +
\ / \ /
\ / \ /
+ +
Figure 1. Six possible directions that hosts may take in
cell A (where P(B) + P(C) + P(D) + P(E) + P(F) + P(G) = 1)
For example, on a two-way highway the direction probabilities
will be approximately 0.5 and 0.5 in each cell along that highway.
Mutaf, Castelluccia Expires February, 2001 [Page 3]
INTERNET DRAFT DPAC September 2001
3.2 Paging area composition
A paging area PA relative to a given cell A and of a given size S,
can be composed as follows:
PA={A}; \\initially the paging area contains
\\only one cell.
i=1;
while (i<S){
add to PA, the cell which \\this cell is computed
would be most probably visited \\using the movement
upon leaving PA; \\direction
\\probabilities.
i++;
}
This way, the shape of PA adapts to the aggregated host mobility
pattern around the cell A.
Using the algorithm described above, the CSA can configure a paging
area relative to each cell in its domain. The paging area size can
be fixed by the operator. However, by configuring large paging areas,
it is possible to choose smaller paging areas later.
For example, let
PA={A,B,C,D,E,F,G,H,I,J,K} (S=11)
a paging area relative to cell A, configured as above. Then, by
preserving the same order, one can pick smaller paging areas such
as:
PA' ={A,B,C,D,E,F} (S=6)
PA" ={A,B,C} (S=3)
where PA, PA' and PA" are concentric paging areas relative to a
same cell A and they have all an optimal shape.
See Section 7 for the motivations behind paging area size
flexibility.
4.0 Convergence of paging areas
How much time will take the convergence of paging areas? Assume
the following parameters:
#users/cell = 25 (uniformly distributed)
#registrations / host / hour = 1 (on the average)
Sampling rate = 2% (i.e. 1 sample / 50 registrations)
Then assuming that one needs on the average 50 samples/cell,
then the CSA will have enough information for composing the
Mutaf, Castelluccia Expires February, 2001 [Page 4]
INTERNET DRAFT DPAC September 2001
paging areas relative to each cell in its domain, in:
50
-------------------- = 100 hours (~5 days)
25 x 1 x 0.02 / hour
In the same manner, if the sampling rate is 1%, the convergence of
paging areas will take ~9 days (which is still in the acceptable
region). This is a promising prediction although we make weak
assumptions. In practice both number of users and registration
rates are higher. On the other hand, the number of samples that is
needed for convergence, depends on hosts' mobility characteristics.
For example, along a one-way highway where all mobiles move in the same
direction, 1 sample/cell will be enough. However, when host mobility
pattern is less predictable (in urban areas for example), more samples
will be needed.
The convergence speed is self-tuning. As mentioned above, samples
are sent upon location registrations. Therefore, initially (when
there is no configured paging areas), hosts will send location
registrations frequently (hence, sampling frequency will be high).
Then, as the paging areas converge, the rate of registrations
hence, sampling frequency will gradually decrease.
5.0 Model of operation with relevance to the DMHA protocol
Dynamically configured paging areas have to be communicated to
mobile hosts. Then, the DMHA protocol should operate as follows:
1. Whenever a host crosses the boundaries of a paging area,
it requests its current paging agent a paging area relative
to its current cell along with its registration message,
2. The paging agent sends this information to the requesting
host along with an acknowledgement message,
3. The host remains dormant while moving in the paging area,
4. When a packet destined for the dormant host arrives,
the paging agent pages the host in its most recent paging area.
Secondly, paging has to be carried out in a SMG (Small Group
Multicast) style [SGM]. In this scheme, all destination cell
addresses forming a paging area are initially carried in a page
packet header. Then, the addresses are split by intervening
routers forwarding the packet to two or more interfaces. This is
illustrated in Figure 2.
Mutaf, Castelluccia Expires February, 2001 [Page 5]
INTERNET DRAFT DPAC September 2001
B
+----------->
A,B,C,D / A
paging agent ----------+ +---->
R1\ A,C,D / C
+---------+ +--->
R2\ C,D /
+------+
R3\ D
+--->
Figure 2. Illustration of paging a DMH
on a paging area comprising the nets A,B,C,D.
6.0 How to support DPAC in current DMHA protocol proposals?
In MIPv6HP [HP] dormant mode state is hold by a MAP [HMIP]. MAPs
can be augmented with CSA functionality for sampling and paging
area composition. The MAP will be responsable for sampling and
composing the paging areas relative to the cells in its domain.
Samples can be sent along with dormant mode registrations (in a
Binding Update sub-option). Paging area request and reply messages
can be also defined as Binding Update sub-options.
In LH-DMHA [LH], the last contacted access router holds the dormant
mode state. The CSA function can be implemented on a MAP or a
dedicated machine. Then, LH-DMHA can be augmented with a message
exchange between the CSA and each access router in its domain. In
this case, the CSA will configure paging areas as described above
and send each access router in its domain the paging area relative
to the cell served by that access router. The access router will
cache this information, and periodically (once per week for example)
update it by requesting the CSA a new one in order to adapt to some
changes in paging area shape. Paging area request and reply
messages can be defined in TLV formatted LH-DMHA messages.
7.0 Picking the paging area size
Manual configuration of paging area sizes is considered
difficult. A cellular operator faces an impossible decision:
1. If I choose large paging areas, then I'll increase the
cost of paging,
2. If I choose small paging areas, then I'll increase the rate
of registrations and battery consumption.
What do to? In current systems, cellular operators choose fixed
paging area sizes. This is by no means optimal.
DPAC will support adaptive schemes with per-host and time-varying
paging area sizes (picked by each individual host) [ADAPT]. This
scheme minimizes the costs of location tracking and provides better
Mutaf, Castelluccia Expires February, 2001 [Page 6]
INTERNET DRAFT DPAC September 2001
power savings. The idea is quite simple: If a host moves slowly,
then the paging area for that host can be small since the cost of
registrations will be small. On the other hand, if a host rarely
receives incoming sessions, the paging area for that host can be
large since the cost of paging will be small.
If the DMHA protocol is DPAC compatible (as described in Section 5),
a host can request its paging agent a paging area of a personally
defined size which adapts well to its mobility and incoming
session rate characteristics. This way paging area sizes can be
also auto-configured.
8.0 Security considerations
Security issues with relevance to paging area auto-configuration,
are not discussed in this document.
9.0 Conclusion
The flexibility of IP paging allows dynamic paging area configuration.
With auto-configured, adaptive paging area shapes and flexible paging
area sizes, this can be regarded as the major advantage of having
L3 paging areas. In this document we proposed dynamic paging area
configuration extensions to IP paging.
References
[PROB] J. Kempf, "Dormant Mode Host Alerting ("IP Paging")
Problem Statement", RFC 3132, June 2001.
[REQ] J. Kempf, et al., "Requirements and Functional Architecture
for an IP Host Alerting Protocol", RFC 3154, August 2001.
[SGM] R. Boivie, et al., "Small Group Multicast",
draft-boivie-sgm-02.txt, February 2001, Work in Progress.
[HMIP] H. Soliman, et al. "Hierarchical MIPv6 Mobility Management",
draft-ietf-mobileip-hmipv6-04.txt, July 2001, Work in Progress.
[LH] Y. Ohba, et al., "LH-DMHA - Last Hop DMHA (Dormant Mode Host
Alerting) Protocol", draft-ohba-seamoby-last-hop-dmha-01.txt,
August 2001, Work in Progress.
[RP] B. Sarikaya, et al., "Mobile IPv6 Hierarchical Paging",
draft-sarikaya-mobileip-mipv6hp-00.txt, July 2001, Work in
Progress.
[ADAPT] C. Castelluccia, "Extending Mobile IP with Adaptive
Individual Paging: A Performance Analysis", ACM Mobile
Computing and Communications Review (MC2R), April 2001.
Mutaf, Castelluccia Expires February, 2001 [Page 7]
INTERNET DRAFT DPAC September 2001
Authors' Addresses
Pars Mutaf
INRIA Rhone-Alpes
655 avenue de l'Europe
38330 Montbonnot Saint-Martin
FRANCE
email: pars.mutaf@inria.fr
phone: +33 4 76 61 55 07
fax: +33 4 76 61 52 52
Claude Castelluccia
INRIA Rhone-Alpes
655 avenue de l'Europe
38330 Montbonnot Saint-Martin
FRANCE
email: claude.castelluccia@inria.fr
phone: +33 4 76 61 52 15
fax: +33 4 76 61 52 52
Mutaf, Castelluccia Expires February, 2001 [Page 8]
INTERNET DRAFT DPAC September 2001