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]