[Search] [pdf|bibtex] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01                                                         
INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000
Internet Engineering Task Force                  R. Ramjee / T. La Porta
INTERNET-DRAFT                                          Lucent Bell Labs
draft-ietf-mobileip-paging-hawaii-01.txt                           L. Li
7 Jul 2000                                            Cornell University
Expires:  7 Jan 2001

                   Paging support for IP mobility

Status of this memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   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 extensions to the HAWAII IP micro-mobility
   protocol to enable paging.  Paging facilitates efficient power
   management at the mobile host by allowing the host to update the
   network less frequently at the cost of providing the network with
   only approximate location information.  The protocol extensions
   described here provide a means for the network to determine the exact
   location of a mobile host before delivering packets destined to the
   mobile host.
















Ramjee/La Porta/Li                 Expires 7 Jan 01             [Page 1]


INTERNET-DRAFT  Paging support for IP mobility                7 Jul 2000



Contents

1  Changes from version 00                                             3

2  Introduction                                                        3
   2.1  Goals  . . . . . . . . . . . . . . . . . . . . .  . . . . . .  4
   2.2  Assumptions  . . . . . . . . . . . . . . . . . .  . . . . . .  4
   2.3  Terminology  . . . . . . . . . . . . . . . . . .  . . . . . .  5
   2.4  Protocol Overview  . . . . . . . . . . . . . . . .  . . . . .  6
        2.4.1 State Synchronization  . . . . . . . . . . . . .  . . .  8
        2.4.2 Application of IP Multicasting Protocol  . . . . .  . .  9
        2.4.3 Distributed Paging  . . . . . . . . . . . . . . . . . . 10
        2.4.4 Soft-State  . . . . . . . . . . . . . . . . . . . . . . 10
        2.4.5 Stale Paging Entry  . . . . . . . . . . . . . . . . . . 10
   2.5  Protocol Correctness  . . . . . . . . . . . . . . . . . . . . 11

3  Detailed Protocol Operation                                        11
   3.1  Message Formats  . . . . . . . . . . . . . . . . . . . .  . . 12
   3.2  Mobile Host Processing . . . . . . . . . . . . . . . . .  . . 14
   3.3  Base Station/Router Processing  . . . . . . . . . . . . . . . 15

4  Design Implications                                                18
   4.1  Scalability   . . . . . . . . . . . . . . . . . . . . . . . . 18
   4.2  Ease of Network Management  . . . . . . . . . . . . . . . . . 18
   4.3  Reliability   . . . . . . . . . . . . . . . . . . . . . . . . 19

5  Paging with Mobile-IP                                              19
   5.1  HA Paging   . . . . . . . . . . . . . . . . . . . . . . . . . 19
   5.2  FA Paging   . . . . . . . .   . . . . . . . . . . . . . . . . 20

6  Security                                                           20






















Ramjee/La Porta/Li                 Expires 7 Jan 01             [Page 2]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



   1   Changes from version 00


     o Changed the HAWAII paging algorithm so that paging load can be
       shared between routers and base stations based on a tunable
       parameter.
     o Added discussion on HA and FA paging.



   2   Introduction


   Mobile-IP is the current standard for supporting macro-mobility in IP
   networks [4].  Recently there have been several proposals such as
   Cellular IP [6] and HAWAII [5] for supporting micro-mobility.  While
   these solutions enable support for high mobility users in wide-area
   wireless networks, they assume that the mobile host updates the
   network on every handoff.  This enables the network to know the exact
   location of the host, i.e., the current base station for delivering
   packets to the mobile host.
   On the other hand, current wide area wireless data solutions such as
   General Packet Radio Service (GPRS) [1] allow the mobile host to
   operate in two distinct states - an active state where the network
   knows the location of the mobile host's current base station, and a
   standby state where the network knows only the approximate location
   of the user, such as a set of base stations on which the mobile host
   resides.  One of the motivations for defining the standby state is
   for reducing the host's battery power consumption by allowing the
   mobile host to only notify the network when it moves out of a set of
   base stations.  If data packets for a mobile host in standby state
   arrive into the wireless access network, the network "pages" the
   mobile host in this set of base stations to determine the mobile
   host's current base station before delivering the data packets.  In
   the GPRS network, this paging functionality is performed in a
   centralized fashion by a Serving GPRS Service Node (SGSN) and can be
   considered as a link layer function.
   We envision the next generation wireless access network as a pure
   IP-based network, where base stations will be IP addressable
   entities.  We believe mobility, as well as the paging functionality,
   should be handled at the network (IP) layer.  This enables the
   deployment of a homogeneous, IP-based wireless access network that is
   independent of the different wireless interfaces.  Wireless link
   specific processing is relegated only to the base stations.  Thus, we
   propose extensions to the IP layer software running in routers/base
   stations in the access network to support paging.
   Note that HAWAII [5] is a domain-based approach for supporting
   mobility that maintains the mobile host's IP address unchanged across




Ramjee/La Porta/Li                 Expires 7 Jan 01             [Page 3]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



   mobility within the domain.  Since a typical HAWAII domain will cover
   one or more paging areas, extending HAWAII to implement paging seems
   a logical choice.  HAWAII uses specialized path setup schemes which
   install host-based forwarding entries in specific routers to support
   intra-domain micro-mobility.  In this framework, adding paging
   functionality to HAWAII involves augmenting the HAWAII forwarding
   functionality with paging.  Thus, we extend the HAWAII protocol with
   paging functionality.



   2.1   Goals

   We have the following design goals:

     o Achieve efficient power consumption at the mobile host by
       limiting the location update traffic and using paging to locate
       the mobile host when necessary.

     o Perform paging in a scalable fashion.  This involves pushing the
       paging functionality closer to the base station.

     o Perform paging in a distributed fashion.  This involves being
       able to page from any base station/router in the access network.
       This eliminates single points of failure for enhanced
       reliability.

     o Support for different types of paging areas such as fixed,
       hierarchical, and user-defined paging areas.



   2.2   Assumptions

   We assume that HAWAII operates as the micro-mobility protocol in the
   access portion of the wireless network.  We propose extensions to
   HAWAII to support paging functionality.  In Section 5, we discuss how
   paging functionality can be applied to a basic Mobile-IP network,
   albeit without some of the scalability and reliability advantages
   that paging with HAWAII provides.

   We also assume that there is link-level paging support on the
   wireless link.  This entails that a mobile host is able to detect
   paging requests and identify its current paging area.  There are
   several ways in which this may be implemented.  A typical solution,
   used in current cellular networks, is to have the base stations send
   paging requests on separate paging channels and send beacons with
   base station and paging area identities periodically on a broadcast
   channel.  A mobile client monitoring these paging and broadcast
   channels can then detect paging requests and changes in paging area.
   Another solution is to let the mobile host query the base station by
   sending link layer point to point messages.


Ramjee/La Porta/Li                 Expires 7 Jan 01             [Page 4]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



   Note that the paging functionality proposed in this draft is
   necessary only if updating the network on every handoff of the mobile
   host is expensive, for example, in terms of signaling load or battery
   power consumption; mobile devices for which this is not an issue or
   for devices that use wireless link protocols such as WaveLAN which
   have no link-level paging support can simply utilize the basic HAWAII
   proposal without the paging extension described in this draft.



   2.3   Terminology

   Domain

     A division of the wireless access network.  It consists of one or
     more routers and multiple base stations.  It will appear as a
     subnet to routers external to the domain.

   Domain Root Router

     The gateway router into a domain is called the domain root router.

   Active State

     In active state, the mobile host updates the network on every
     handoff.  Thus, the network tracks the current base station of the
     mobile host.

   Standby State

     In standby state, the mobile host reduces battery power
     consumption by listening to only selective broadcast channels.
     Furthermore, the mobile host updates the network of its location
     only when it crosses a set of base stations, known as the paging
     area.

   Paging Area

     The granularity to which the mobile user is tracked in standby
     state.  It consists of a set of base stations, typically defined
     by a network administrator.  In this draft, we identify these base
     stations by a IP Multicast Group Address (MGA).

   Routing Entry

     A routing entry in the base stations and routers in the domain
     specifies where to forward a packet for a given mobile host.  It
     is established by the HAWAII protocol.  A routing entry for a
     mobile host is present in selected routers/base stations when the
     mobile host is in active state.



Ramjee/La Porta/Li                 Expires 7 Jan 01             [Page 5]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



   Paging Entry

     A paging entry in the base stations and routers in the domain
     specifies which set of base stations to page for a given mobile
     host.  It is established by the HAWAII protocol.  A paging entry
     for a mobile host is present in selected routers/base stations
     when the mobile host is in active or standby state.



   2.4   Protocol Overview

   In this section, we present the protocol design for the paging
   functionality within the HAWAII framework.  We believe that mobile
   devices would mostly operate in standby state, with brief periods in
   active state.  In the standby state, the mobile host conserves
   significant battery power.  The mobile host can switch to active
   state immediately after receiving notification from the network that
   data packets are destined for it.

   Like today's cellular networks, it is not desirable for the mobile
   host to update its location every time the mobile host moves to a
   different base station.  Therefore the network is not able to
   maintain exact location information for the mobile host and instead
   maintains only approximate location information.  Location
   information can be maintained in one place in the network such as the
   domain root router (DRR). However, such a centralized approach
   introduces a single point of failure and results in scalability
   concerns.  Therefore we favor a distributed approach.  On the other
   hand, maintaining paging information in every element in the access
   network is also not desirable.  This would require flooding the
   location information to the entire HAWAII domain, which wastes
   bandwidth and processing resources.  Thus, our solution endeavors to
   maintain the location information for a given mobile host only in
   selective routers and base stations.

   The approximate location information can be represented by a set of
   base stations called the Paging Area (PA). We do not assume any
   specific way of defining PAs.  Our goal is to support fixed,
   hierarchical, and even personalized PAs.  In order to efficiently
   search the PA for the mobile host, we exploit the use of IP multicast
   routing protocol for distributing paging request to a set of base
   stations.

   In order to manage router and link failures gracefully, we use
   soft-state mechanisms for maintaining paging state.  We now
   illustrate the basic mechanism for paging using a simple tree-based
   topology for the case when packets arrive at the domain root router
   from some external host for a mobile host that is in standby state.




Ramjee/La Porta/Li                 Expires 7 Jan 01             [Page 6]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



   Selected routing and paging entries denoted by the letters R and P
   are shown adjacent to the routers in Figure 1.  These entries are
   prepended with a message number label indicating which message was
   responsible for establishing the entry.  The letters A,B, and C
   denote the different interfaces.  Let us assume that the mobile host
   powered up at the old base station and established routing and paging
   entries as denoted by label (0).  Also, let the paging area be
   configured to consist of the two base stations, OLD BS and NEW BS,
   assigned to a multicast group address (MGA) of 239.0.0.1.  The
   multicast routing protocols would build a multicast tree with the OLD
   BS and NEW BS as the leafs and Router 1 as a node in the tree (the
   corresponding multicast routing entries are shown with a suffix M in
   the figure).  At this time, packets arriving for the mobile host at
   router 0 will get delivered to the mobile host through the OLD BS
   using the routing entries just established.


                                   | @
   (0)R,P:1.1.1.1->B,239.0.0.1     | @ 2
   (1)P  :1.1.1.1->B,239.0.0.1 ------v--
                               |   A   |
                               |       |
                               |   B   |
                               --------- ROUTER 0
                                   | @
                                   | @ 2
                                   | @
                               ------v-- ROUTER 1
   (0)M  :239.0.0.1->B,C       |   A   |
   (0)R,P:1.1.1.1->B,239.0.0.1 |       | (5)R,P:1.1.1.1->C,239.0.0.1
   (1)P  :1.1.1.1->B,239.0.0.1 | B   C |
                               ---------<$$$$$$$
                             * /      @ \ *    $
                          3 * /        @ \ * 3 $ 5
                  OLD BS   * /       6  @ \ *  $  NEW BS
                         --v--          @ --v--
   (0)M:239.0.0.1->A    /  A  \        @ /  A  \   (0)M:239.0.0.1->A
   (0)R,P:1.1.1.1->B,  |       |      @ |       |   (0)R:Default->A
           239.0.0.1    \  B  /      @   \  B  /   (4)R,P:1.1.1.1->B,
   (1)P  :1.1.1.1->B,    -----       @ $$>-----             239.0.0.1
           239.0.0.1       *         @ $ 4   *
                       3 * * *       @ $   * * * 3
                       * * * * *     @ $ * * * * *
                                    -v--
   M:Multicast entry        MOBILE /    \       @: data packets
   R:Routing entry          HOST   \    /       *: page request
   P:Paging entry                   ----        $: page response






Ramjee/La Porta/Li                 Expires 7 Jan 01             [Page 7]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



                                IP:1.1.1.1


                      Figure 1: Illustration of paging in HAWAII


   Now, let label (1) denote the timeout event where the mobile host and
   the routers in the network enter the standby state because of lack of
   refreshes from the mobile host.  At this time, the routing entries
   for the mobile host are timed out in the routers and the base
   stations and only the paging entries remain.  Furthermore, let the
   mobile host now move to NEW BS. Note that the network is unaware of
   this movement since the host is in standby state.

   Consider data packets arriving for the mobile host at router 0 (label
   2).  Router 0 would look up its HAWAII entries and find that a paging
   entry exists for the host.  Since the router does not have any
   entries for MGA 239.0.0.1, it simply forwards the packet along
   interface B to Router 1.  Router 1 looks up the paging entry for the
   mobile host and finds that the MGA 239.0.01 multicast routing entry
   exists and has two interfaces associated with it.  Assuming that
   Router 1 is lightly loaded, it buffers the data packets for the
   mobile host and initiates a paging request (label 3).

   The mobile host responds to the paging request to the new base
   station (label 4) which adds routing and paging entries for the host
   and sends a paging response to the initiator of paging request,
   Router 1.  On receiving message 5, Router 1 updates its routing and
   paging entries for the host.  It then forwards the buffered data
   packets to the mobile host (label 6).

   Note that Router 0 would only be updated later by a paging refresh
   message from Router 1 (until then it will continue forwarding packets
   for the mobile host correctly to Router 0 since it is not part of the
   multicast tree for MGA 239.0.0.1).


   2.4.1 State Synchronization

   As mentioned earlier, the mobile host operates in two states, active
   and standby.  This can be modeled by a state machine with three
   states:  active, standby and null, with null representing a powered
   off mobile host.  Base stations and routers in the access network
   need to implement an analogous state machine so that the mobile host
   is paged in standby state and packets are delivered directly to the
   mobile host in active state.  The state of the network must reflect
   the state of the mobile host.  If the mobile host is in standby
   state, the state of the mobile host in the network also needs to be
   in standby state so that paging can be initiated; otherwise, if the
   mobile host's state in the base station/routers is in active state,



Ramjee/La Porta/Li                 Expires 7 Jan 01             [Page 8]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



   the mobile host will not be paged, which may result in packets being
   misrouted to the wrong base station.  Note that, even if the network
   is in standby state with respect to a mobile host that is in active
   state, packets will still get delivered correctly; however, this
   would result in an unnecessary page.

   Thus, we would like the network to go into standby state for the
   mobile host exactly when, or just before, the mobile host goes into
   standby state.  Similarly, it is preferable for the network to go
   into null state only after the mobile host goes into null state.
   Although this synchronization is not tight, it guarantees that the
   mobile host will be reachable as long as it is powered up.


                  Table 1: Router operation
   -----------------------------------------------------------------
   Routing Paging State         Operation
   entry   entry
   -----------------------------------------------------------------
   Yes     Yes    Active  Regular forwarding
   Yes     No     Active  No paging support (basic HAWAII)
   No      Yes    Standby Paging processing (details: see Figure 5)
   No      No     Null    Forward if default route exists, else drop
   -----------------------------------------------------------------


   We distinguish two types of entries in the network components such as
   base stations/routers for maintaining the mobile host's state
   machine:  a routing entry and a paging entry.  The operation of the
   router or base station with respect to these entries is shown in
   Table 1.


   2.4.2 Application of IP Multicasting Protocol

   We need to maintain the current PA for each mobile host and
   distribute paging requests to the base stations in the PA. Instead of
   unicasting the paging request to the set of base stations in the PA,
   IP multicast is used to distribute the paging request.  Thus, each PA
   in a given domain is configured with a multicast group address and
   each base station in a given PA joins that multicast group.  Since
   the multicast group is within the HAWAII domain, we use the range of
   addresses that are allocated for administratively scoped IP
   Multicast [2].

   Fixed or hierarchical PAs can be statically configured with different
   multicast group addresses.  In order to support user-defined paging
   areas, base stations may have to join multicast groups in a dynamic
   fashion.  This is a subject for further study.




Ramjee/La Porta/Li                 Expires 7 Jan 01             [Page 9]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



   2.4.3 Distributed Paging

   The HAWAII paging entry for each mobile host is maintained at a base
   station and each router on the path from the base station to the
   Domain Root Router.  Every router/base station is capable of
   initiating paging by buffering incoming packets and sending a paging
   request to the multicast group.  However, the paging processing rules
   (discussed later) ensure that only one node in the network initiates
   paging for a particular mobile host at a given time.  We also ensure
   that paging is initiated from routers with the up-to-date paging
   entries for the mobile host by enforcing that paging is initiated
   only if packets arrives from the interface to the DRR. In order to
   push the paging load further down towards the base stations, the
   router that has multiple interfaces for the PA's MGA initiates the
   paging.  If no such router exists, the packet will eventually reach a
   base station, which will then assume the paging responsibility.


   2.4.4 Soft-State

   The notion of ``soft-state'' refers to state established within
   routers that needs to be periodically refreshed; otherwise, it is
   removed automatically when a preset timer associated with that state
   expires.  In addition to maintain routing information as soft state,
   the HAWAII paging entries within the routers are also maintained as
   soft-state.  This increases the robustness of the protocol to router
   and link failures.

   Our protocol uses four types of control messages:  requests,
   responses, updates, and refreshes, to query, establish and maintain
   the paging soft-state.  Paging request messages are triggered inside
   the network for locating the mobile user, which then responds with a
   paging response.  Paging updates are sent by the mobile host during
   the crossing of a paging area in standby state.  These messages are
   explicitly acknowledged by the recipient.  Paging refresh messages
   are sent periodically by mobile hosts.  Aggregate paging refresh
   messages are sent periodically by base stations and routers in a
   hop-by-hop manner to the router upstream of the mobile hosts.  As we
   shall see in the following sections, paging messages are sent to only
   selected routers in the domain, resulting in very little overhead
   associated with maintaining soft-state.


   2.4.5 Stale Paging Entry

   The protocol ensures that the latest (up-to-date) paging entries are
   maintained along the path from the DRR to one base station in the PA.
   Thus, packets arriving for the mobile host from outside the domain





Ramjee/La Porta/Li                 Expires 7 Jan 01            [Page 10]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



   will be correctly delivered.  However, stale paging entries may exist
   in internal routers for several reasons such as outdated refresh
   messages, topology or routing changes, etc.  In order to avoid paging
   using stale paging entries for packets originating inside the domain
   and destined for a mobile host in standby state, these packets will
   first be forwarded along the default route to the DRR. The DRR always
   has the latest paging entry and forwards the packet along the path to
   a base station.  These packets will then trigger paging from a router
   with the latest paging entry and deliver it to the mobile host.



   2.5   Protocol Correctness

   Our paging protocol maintains the following invariants.

    1. Latest paging entries are maintained for each mobile host along
       the path from DRR to one base station in PA.

    2. Paging is initiated from routers with paging entry for the
       mobile host only if packets arrive from the interface to the
       DRR.

    3. Response to a paging request is sent to the paging initiator in
       a hop-by-hop manner from the mobile host's current base station.
       This sets up routing and paging entries along the path from the
       mobile host to the paging initiator.

    4. State of the base station/routers with the mobile host is
       ``synchronized'' in the sense that its routing entries time out
       before a mobile host goes into standby and its paging entries
       exist as long as the mobile host is not powered off.

   These invariants guarantee the correctness of the paging protocol.
   Invariant 4 ensures that a mobile host's paging entry and not its
   routing entry is used when the mobile host is in the standby state.
   Invariants 1 and 2 imply that the router/ base station initiating the
   paging has the latest (up-to-date) paging entry.  Invariant 3
   guarantees that the routing path is set up after paging for packet
   delivery to the mobile host.



   3   Detailed Protocol Operation


   In this section, we describe the protocol processing details of
   paging for HAWAII. We assume that the HAWAII update message (type 1)
   is extended to include the multicast group address (MGA)
   corresponding to the PA. We now describe four new message types and
   their respective formats in the HAWAII protocol corresponding to the
   paging request, update, response, and refresh messages.  We then


Ramjee/La Porta/Li                 Expires 7 Jan 01            [Page 11]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



   present the processing at the mobile host and finally, the protocol
   processing at the base stations/routers.



   3.1   Message Formats

   The format for the paging request is shown below.  It is initiated by
   a router or base station satisfying invariant 2 in Section 2.5.


    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |Version| Type  |     Seq No    |        Scheme                 +
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Mobile Host Address                         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Paging Initiator  Address                   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | Extensions ...
    +-+-+-+-+-+-+-+-


      Version                     1
      Type                        5 (paging request)
      Scheme                      1 (fixed PA)
      Seq No                      Sequence number of paging request
      Mobile host Address         Home address or Care-of address
      Paging Initiator Address    Router/base station initiating paging


   The format of paging update and response messages sent by base
   station/routers is shown next.  Paging updates (type 6) are sent
   hop-by-hop to the DRR when the mobile host crosses a paging area.
   Paging responses (type 7) are sent hop-by-hop to the initiator of the
   paging request in response.


     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |Version| Type  |   Reason      |          Scheme               +
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Mobile Host Address                         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |           Metric              |    Routing Lifetime           |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Old Base Station                            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   New Base Station                            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                  MGA for current PA                           |


Ramjee/La Porta/Li                 Expires 7 Jan 01            [Page 12]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                                |
    +                      Timestamp                                 +
    |                                                                |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | Extensions ...
    +-+-+-+-+-+-+-+-



   Version                 1
   Type                    6 (paging update), 7 (paging response)
   Scheme                  1 (fixed PA)
   Mobile host Address     Home address or Care-of address
   Metric                  Distance to the mobile host in hops
   Routing Lifetime        Soft state timer value
   Old Base Station        Old Base Station IP address for Type 2
                           0.0.0.0 for Type 1 (power up)
   MGA for current PA      intra-domain MGA for host's current PA
   Timestamp               Timestamp formatted as in
                           Network Time Protocol [3].
   Extensions              Authentication field
                           Wireless link specific fields, for study


   The format for a paging refresh message is shown next.  The message
   could contain multiple entries as part of an aggregate refresh when
   sent by base stations and routers to their upstream router.  The
   maximum message size is constrained to 4KB.


     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |Version|  Type |     Reason    |             Size              +
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Mobile Host Address[1]                      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                          MGA[1]                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    +                        Timestamp[1]                           +
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                 ...
                                 ...
                                 ...
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                   Mobile Host Address[N]                      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+




Ramjee/La Porta/Li                 Expires 7 Jan 01            [Page 13]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



    |                            MGA[N]                             |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    +                        Timestamp[N]                           +
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | Extensions ...
    +-+-+-+-+-+-+-+-

   Version                 1
   Type                    8 (paging refresh)
   Size                    Number of mobile host entries
   Reason                  0 (normal)
                           1 (triggered refresh due to failure)
   Mobile host Address     Host-entry address
   Timestamp               Host-entry timestamp
   Extensions              Authentication field



   3.2   Mobile Host Processing

   Figure 2 shows the state diagram at the mobile host for maintaining
   the ACTIVE, STANDBY, and NULL states.  The mobile host can transmit
   and receive data only in ACTIVE state.  In order to transit into
   ACTIVE state, either the mobile host sends a regular HAWAII
   registration or the mobile host responds to a paging request.  While
   in ACTIVE state, the mobile host sends HAWAII registrations at least
   once every Tactive time units.  The mobile host goes into STANDBY
   from ACTIVE state when the mobile host is idle for time Tactive.
   While in STANDBY state, the mobile hosts sends paging refresh
   messages at least once every Tstandby time units or paging update
   messages when it crosses a PA.



                        Startup: send
              ++++++++  power up update  ++++++++  ____  Timeout:
             +        +---------------> +        +/    | resend power up
             +  NULL0 +                 + NULL1  +     |   update
             +        + <---------------+        + <--/
              ++++++++  Give up resends  ++++++++
        Power  ^   ----------------------|  | ^
        down   |  | Get ack                 | |
               |  | w/ active    Get ack    | | Crossing PA:
   Every       |  |              w/ standby | | send paging update







Ramjee/La Porta/Li                 Expires 7 Jan 01            [Page 14]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



   Tactive,    |  |                         | |
   send routing|  v    Idle for             v |
   refresh  +++++++++  time Tactive     ++++++++++   ____ Every
     |----\+         +---------------> +          +/    | Tstandby,
     |     + ACTIVE  +                 + STANDBY  +     | send paging
      \--> +         + <---------------+          + <--/  refresh
            +++++++++  Paging response  ++++++++++
                       or routing update


                Figure 2: Client State Diagram


   Thus two timers, Tactive and Tstandby, control the idle time for
   transitions between the ACTIVE to STANDBY and STANDBY to NULL states
   respectively.  These timers will be configured based on usage
   patterns and battery power consumption statistics for wide-area
   wireless data devices.  Default values for these timers in HAWAII are
   30 seconds and 30 minutes respectively.



   3.3   Base Station/Router Processing

   The processing of power up update message is similar to processing
   basic HAWAII power up update message in [5].  While basic HAWAII
   power up update messages establish only routing entries, in this
   case, we extend it so that both routing and paging entries with the
   multicast group address (MGA) are established.

   The pseudo-code for processing paging update message is shown in
   Figure 3.  Paging update messages are sent along the ``default''
   route.  They are sent when the mobile host crosses a PA. The
   processing is similar to the processing of a power up update message.
   The only difference is that this message only sets up paging entries.
   Note that the notation of the paging entry is similar to the one used
   in explaining Figure 1.  It consists of the mobile host address (MH
   IP ADDRESS), the multicast group address (MGA), and the forwarding
   interface.


   --------------------------------------------------------------------
   Figure 3: HAWAII paging update message processing
   --------------------------------------------------------------------
   1. Receive the message from neighbor on Interface A
        Message contains  {MH IP ADDRESS,MGA, TIMESTAMP}
   2. If TIMESTAMP is greater than current paging entry timestamp then
   3. If I am the Domain Root Router
          Add/Update paging entry to be
            (MH IP ADDRESS -> MGA, Interface A)
          set timer Tstandby


Ramjee/La Porta/Li                 Expires 7 Jan 01            [Page 15]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



          Generate an acknowledgement
       else
          Add/Update paging entry to be
            (MH IP ADDRESS -> MGA, Interface A)
          set timer Tstandby
          Forward paging update to upstream neighbor along default route
       endif
      endif
   --------------------------------------------------------------------


   The pseudo-code for packet forwarding in HAWAII with paging support
   is shown in Figure 4.  As in basic HAWAII, if a routing entry exists,
   packets are forwarded using the entry.  If the routing entry does not
   exist but a paging entry exists, paging is initiated only when the
   packet arrives on the interface from the DRR and the node has not
   received a refresh from its downstream neighbor due to failure or the
   node is a lightly loaded router such that outstanding page requests
   are below a threshold value T or the node is a base station.
   Otherwise it is forwarded to the DRR. This helps push the burden of
   paging towards the base station, thereby reducing the load at the
   DRR.


   --------------------------------------------------------------------
   Figure 4: HAWAII packet forwarding processing in the BS and router
   --------------------------------------------------------------------
   If (there is no routing entry for MH IP address)
      If (paging table has an entry for MH)  // has paging entry
         Entry contains {MH IP address -> MGA, Interface A}
         Let Interface B be the interface of the default route
         if (packet is from Interface B or I am the Domain root Router)
            if ((no refresh on Interface A) /* Failure */
                or (outstanding page requests < T)/*lightly loaded?*/
                or (I am a base station))  /* Initiate Paging */
               buffer the packet
               send a paging request message to the MGA
               increase the retry counter and set timer for paging retry
            else
               route the packet to interface A
            endif
         else
            forward the packet along the default route to DRR
         endif
      else  // no routing or paging entries
         If (I am not the Domain Root Router)
            forward the packet along the default route to DRR
         else





Ramjee/La Porta/Li                 Expires 7 Jan 01            [Page 16]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



            discard the packet
         endif
      endif
   else  // has routing entry
      route the packet using the routing entry
   endif
   --------------------------------------------------------------------


   The pseudo-code for processing a paging response message is shown in
   Figure 5.  The paging response is sent to the initiator of the paging
   request.  It is sent hop-by-hop and routing entries are set up along
   the way.


   --------------------------------------------------------------------
   Figure 5: HAWAII paging response processing for fixed paging area
   --------------------------------------------------------------------
   1. Receive the message from neighbor on Interface A
        Message contains  {MH IP ADDRESS,MGA, TIMESTAMP}
   2. If TIMESTAMP is greater than current paging entry timestamp then
   3.  If I am the paging initiator
         Look up pending paging response for this MH
         Add/Update routing entry to be {MH IP ADDRESS -> Interface A},
         set timer Tactive
         Generate an acknowledgement
       else
         Add/Update routing entry to be {MH IP ADDRESS -> Interface A}
         set timer Tactive
         Forward the paging response packet towards paging initiator
       endif
     endif
   --------------------------------------------------------------------


   The soft-state paging refresh messages are sent independently by each
   of the nodes on a hop by hop basis.  The mobile host refreshes the
   base station at least every Tstandby seconds in the STANDBY state.
   The base stations and routers send HAWAII routing and paging
   refreshes to their upstream routers (determined based on their
   default route to the domain root router) every TR1 and TR2 seconds
   respectively.  We require that TR1 and TR2 be more frequent than
   Tactive and Tstandby in order for the protocol to be robust across
   message losses.  Also, typically Tstandby would be much longer than
   TR2 in order to conserve the limited wireless bandwidth.  When the
   refresh message is received, the expiry timer corresponding to the
   refresh entry is updated.  The processing of the paging refresh
   message is very similar to the processing of the routing refresh
   message in HAWAII [5].




Ramjee/La Porta/Li                 Expires 7 Jan 01            [Page 17]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



   4   Design Implications


   In this section, we illustrate the advantages of our protocol for
   paging by studying the implications on scalability, ease of network
   management and reliability.



   4.1   Scalability

   Paging entries for a given mobile host are only present along one
   path from a base station to the DRR. The closer a router is to the
   DRR, more paging entries and more refresh/update messages it will
   process.  On the other hand, the farther a router is from the DRR,
   the probability of paging being initiated is higher.  This is because
   of the rule that the router initiating a paging should be on the
   multicast tree for the given paging area and have at least two
   branches; since paging areas are typically localized, such a router
   would be closer to the paging area and farther from the DRR. Thus,
   the protocol distributes the processing load due to paging among the
   different routers in the domain.  Given that HAWAII is shown to be
   scalable in [5] for large-sized domains, we believe that the addition
   of paging functionality will not impact the scalability of HAWAII
   adversely.



   4.2   Ease of Network Management

   In today's cellular network, every update with respect to location
   management needs to be propagated to the Mobile Switching Center
   (MSC) or the Serving GPRS Service Node (SGSN). In HAWAII, if a new
   base station is installed due to a cell split, the base station just
   creates/joins the appropriate multicast group.  If the base station
   changes to use a different algorithm to determine the PA, the base
   station can just regroup into different PAs, and then join the
   corresponding multicast groups.  These changes are transparent to
   other routers in the domain; the multicast routing protocol will
   automatically compute the new multicast tree for each of the PAs.
   Furthermore, by having a pure IP-based solution for mobility
   management, the routers in the wireless access network are shielded
   from details specific to the wireless interface.  On the other hand,
   the use of specialized components such as the MSCs or the SGSNs for
   each wireless link protocols implies that each of these components
   must be managed in a separate manner, thereby increasing the cost and
   complexity of deployment.






Ramjee/La Porta/Li                 Expires 7 Jan 01            [Page 18]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



   4.3   Reliability

   Paging can be initiated by any router/base station along the path to
   the DRR. Therefore unlike a centralized approach, there is no single
   point of failure with respect to paging.

   Link and router failures are handled through the soft-state refresh
   mechanism in HAWAII. The HAWAII daemon running at each router would
   detect these failures and update its default route/paging entry.
   This will trigger an immediate soft-state routing and paging refresh
   messages for all its host entries to a new uplink router.  This will
   result in further propagation of soft-state refresh messages until a
   router that has pre-existing entries for the affected mobile hosts is
   notified (this will be the domain root router in the worst case).



   5   Paging with Mobile-IP


   So far, we considered how paging support can be added to HAWAII.
   Paging support can also be added to basic Mobile-IP using a similar
   approach.  However, some of the scalability and reliability
   advantages of paging with HAWAII may no longer be possible.



   5.1   HA paging

   HA paging is performed in a centralized manner at the home agent.
   When a mobile host registers with its home agent, it sends the
   identity of its current PA. When a packet destined for a mobile host
   in standby state arrives at the HA, the HA buffers the packet and
   contacts all the base stations in the PA. The base stations
   subsequently page over the air.  The mobile host then registers its
   current location with the HA, which delivers the buffered packet as
   well as subsequent packets.

   One drawback with this approach is that the HA needs to be informed
   of the addresses of the base stations in the PA. Since the base
   stations and the HA can belong to different administrative domains,
   the PA information could be considered confidential and may not be
   available.  The use of globally visible multicast group address to
   represent the PA is one possible solution but global multicast has
   its own scalability concerns.

   The HA paging approach is similar to the centralized paging
   implementations in current wide-area cellular networks; in GPRS,
   paging is performed at the Serving GPRS Service Node (SGSN), while in
   CDMA, it is implemented at the Mobile Switching Center (MSC). The
   main difference is that cellular paging is always performed inside



Ramjee/La Porta/Li                 Expires 7 Jan 01             [Page 19]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



   the visiting network rather than from the home network as in HA
   paging, thus avoiding the confidentiality issues of HA paging.



   5.2   FA paging

   In FA paging, paging is initiated at the mobile host's last attached
   FA (base station).  When a packet destined for a mobile host in
   standby state arrives at the HA, the HA tunnels the packet to the FA
   as in basic Mobile IP. Thus, the HA is unaware of the fact that the
   mobile host is in standby state and needs to be paged.  The FA
   buffers the packet and multicasts a page message to the base stations
   in the PA. The base stations subsequently page over the air.  The
   mobile host then registers its new location (FA) with the HA and also
   simultaneously informs the previous FA so that the buffered packet
   can be forwarded.  If the mobile host happened to remain at its
   previous base station, the latter two messages are avoided.

   One issue with this approach that needs to be addressed is the impact
   of foreign agent failures.  In HA paging, HA failure would leave the
   mobile host disconnected.  In FA paging, in addition, even in the
   presence of an end-to-end path to the mobile host, the failure of the
   previous foreign agent could result in the mobile host being
   unreachable indefinitely (since the previous FA is the paging
   initiator).  One way to avoid this is to allow the HA to monitor the
   different FA's in the paging area but then this rises confidentiality
   concerns; therefore, some form of failure recovery protocol amongst
   the different FA's in a PA need to be implemented.



   6   Security


   This protocol has been defined as an extension to the HAWAII
   protocol [5].  The security model of the HAWAII protocol directly
   applies for the messages from the mobile host.  Regarding the paging
   messages which are generated and processed only from within a given
   administrative domain, simple mechanisms such as password protection
   should suffice.












Ramjee/La Porta/Li                 Expires 7 Jan 01            [Page 20]


INTERNET-DRAFT          Paging support for IP mobility        7 Jul 2000



References

  [1] Digital cellular telecommunication system, General Packet Radio
      Service, Service description - Stage 2, GSM 03.60 Version 6.0,
      ETSI, 1998.

  [2] D. Meyer, ``Administratively Scoped IP Multicast,'' Request for
      Comment 2365, July 1998.

  [3] D. Mills, "Network Time Protocol (Version 3):  Specification,
      Implementation and Analysis", RFC 1305, Mar 1992.

  [4] C.E. Perkins, ``IP Mobility Support,'' Request for Comments 2002,
      Oct 1996.

  [5] R. Ramjee, T. La Porta, S. Thuel, K. Varadhan, L. Salgarelli,
      ``IP micro-mobility support using HAWAII,'' Internet Draft, Work
      in Progress, June 1999.

  [6] A. Valko, A. Campbell, and J. Gomez, ``Cellular IP,'' Internet
      Draft, Work in Progress, November 1998.



Authors' Addresses

R. Ramjee, T. La Porta
Bell Labs, Lucent Technologies,
101 Crawfords Corner Road,
Holmdel, NJ 07733 (USA)
Phone: 732-949-3306
Fax:   732-949-4513
Email: {ramjee,tlp}@bell-labs.com


L. Li
Department of Computer Science,
Cornell University
Email: lili@cs.cornell.edu














Ramjee/La Porta/Li                 Expires 7 Jan 01            [Page 21]