INTERNET-DRAFT R. Jain, Expires: July 2000 T. Raleigh Telcordia Technologies (formerly Bellcore) M. Bereschinsky, C. Graff US Army CECOM February 2000 Mobile IP with Location Registers (MIP-LR) Status of this Memo This document is only intended to provide information for the Internet community. It does not aim to specify an Internet standard. Distribution of this memo is unlimited. 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 is intended only to provide information to the Internet community. The Mobile IP (MIP) protocol for IP version 4 provides continuous Internet connectivity to mobile hosts, without requiring any changes to existing routers and higher-layer applications. This Mobile IP-LR [Page 1] Expiration Date May 2000 Nov. 1999 document describes an alternative protocol, Mobile IP with Location Registers (MIP-LR), where the sender first queries a database, called a Location Register, to obtain the recipients current location. MIP-LR is designed for operation in tactical military environments, enterprise environments or within logical administrative domains, as it requires a sending host to be aware which hosts implement the MIP-LR protocol. MIP-LR gives up the transparency of MIP for several benefits in the areas of survivability, performance and interoperability. MIP-LR improves survivability for situations where the mobile's home network is particularly vulnerable (e.g. in the forward area of a battlefield), by allowing location registers to be placed and replicated outside the home network. This document describes how replicated location registers can be managed by Translation Server or Quorum schemes. In terms of performance, MIP-LR avoids triangle routing and tunneling, and reduces the load on the home network as well as the home agents. MIP-LR provides improved interoperability with protocols such as RSVP for providing QoS guarantees. Finally, MIP-LR is interoperable with MIP, such that hosts which implement only MIP can continue to operate as expected (provided the provisions required by MIP, such as Home and Foreign Agents, are appropriately provided) without gaining any of the benefits of MIP-LR. We have developed a working version of the MIP-LR protocol running on Linux hosts. Table of Contents 1. INTRODUCTION 2 1.1 MOBILE IP 3 1.2 SURVIVABILITY 4 1.3 PERFORMANCE 5 1.4 INTEROPERABILITY 6 2. MOBILE IP WITH LOCATION REGISTERS 7 2.1 MIP-LR OPERATION 8 2.1.1 Subnet discovery 8 2.1.2 Registration 8 2.1.3 Packet delivery 8 2.1.4 Cache maintenance 9 2.1.5 Determining hosts which speak MIP-LR 9 2.2 OBTAINING THE HLR ADDRESS 10 2.3 DISCUSSION OF MIP-LR DESIGN 11 2.3.1 Interoperability with MIP 11 2.3.2 Survivability of VLRs 12 2.3.3 Eliminating VLRs 12 3. MANAGING MULTIPLE HLRs 13 3.1 TRANSLATION SERVERS 13 Mobile IP-LR [Page 2] Expiration Date May 2000 Nov. 1999 3.1.1 Single Translation Server 14 3.1.2 Multiple Translation Servers 17 3.2 QUORUM CONSENSUS 18 4. REMARKS 21 5. SECURITY CONSIDERATIONS 22 6. ACKNOWLEDGMENTS 22 7. AUTHORS' ADDRESSES 22 1. Introduction This document is intended only to provide information to the Internet community. It provides a protocol similar in many respects to Mobile IP, but provides certain attractive features for particular types of networks. Since Mobile IP has already been approved for the standards track this draft is submitted for informational purposes only. We have developed a running version of the proposed protocol on Linux hosts. The document describes the Mobile IP with Location Registers (MIP-LR) protocol that is designed to provide mobile hosts with continuous Internet access. MIP-LR is designed specifically for closed domains, rather than the Internet at large, and thus makes design trade-offs different from those made by Mobile IP. In particular, it gives up the transparency of Mobile IP for improved survivability, performance, and interoperability with RSVP. It can also interoperate with MIP. MIP-LR addresses the following four limitations of MIP: 1. Home Agent Location. The mobile's Home Agent must be located in its home network. 2. Home Agent Vulnerability. There is no scheme to allow multiple, geographically distributed Home Agents located outside the Home Network to serve the user. 3. Triangle Routing. All packets destined to the mobile host must traverse its home network. 4. Tunneling. Packets destined to the mobile must be tunneled (typically by being encapsulated inside another IP packet) enroute. The first two limitations inhibit survivability, particularly in a military scenario where the mobile's home network may be in a vulnerable forward area. The second two limitations imply a performance penalty and also inhibit interoperability with other protocols like RSVP which rely on inspecting the original IP packet header. Mobile IP-LR [Page 3] Expiration Date May 2000 Nov. 1999 MIP-LR uses a set of databases, called Location Registers, to maintain the current Care-Of Address (COA) of the mobile host. When a mobile host moves from one subnet to another, it registers its current COA with a database called a Home Location Register (HLR). When a correspondent host has a packet to send, it first queries the HLR to obtain the mobile host's COA, and then sends packets directly to the mobile host. Observe that the mapping from the mobile host's permanent IP address to its COA is done by the IP layer at the correspondent host and is transparent to higher-layer protocols; the reverse mapping is done at the mobile. The correspondent host caches the mobile host's COA to avoid querying the HLR for every subsequent packet destined for the mobile host. The mobile host maintains a list of correspondent host's with which it is in active communication and informs them if it moves to a different subnet (as is done in Mobile IP for IPv6). This document is organized as follows. The rest of this section briefly describes MIP and motivates the need for MIP-LR by describing some of the limitations of MIP in more detail. In sec. 2 we describe MIP-LR. In sec. 3 we discuss how the survivability of MIP-LR can be enhanced further by using replicated mobility databases, and present two schemes for managing the replicated databases. Finally, in sec. 4 we end with brief remarks. 1.1 Mobile IP The operation of the Mobile IP protocol (MIP) [1] for supporting continuous Internet connectivity for mobile hosts (MH) can be summarized as follows. An MH is always identified by the IP address it has when in its home network, called its home address. The home network contains an entity (typically, a router) called the Home Agent (HA) that maintains information about the mobile host's current location. When a mobile host is visiting a foreign network mobility support is provided by a Foreign Agent (FA) in the foreign subnet. A mobile host discovers whether it is in the home or a foreign network either because it receives agent advertisement messages broadcast periodically on the local subnet by the Home and Foreign Agents or because they respond to agent solicitation messages the mobile host broadcasts. In its home network, the mobile host operates without mobility services. In a foreign network, the mobile host uses the Foreign Agents address as a Care-of Address (COA), or obtains a COA by some external means such as the Dynamic Host Configuration Protocol (DHCP) [2], in which case it is called a co-located COA. The mobile host registers the mapping from its home address to its COA (called a mobility binding) by sending a registration request to the Home Agent via the Foreign Agent. Mobile IP-LR [Page 4] Expiration Date May 2000 Nov. 1999 Any Correspondent Host (CH) wishing to communicate with the MH need not be aware the mobile host has moved; it simply sends IP packets addressed to the mobile host's home address. These packets are routed via normal IP routing to the mobile host's home network, where they are intercepted by the HA (e.g. by means of a proxy ARP mechanism). The latter tunnels the packet (typically, encapsulates each such packet in another IP packet which contains the mobile host's COA as the destination address) to the mobile host's new location. If the COA is the FAs address the FA detunnels (decapsulates) the packet and delivers the original packet to the mobile host. Otherwise, if it is a co-located COA, the mobile host decapsulates the packet itself. Note that packets from the mobile host to the correspondent host need not necessarily be tunneled; the mobile host can simply send them directly to the correspondent host. 1.2 Survivability Both MIP (as well as MIP with Route Optimization, MIP-RO, summarized below) suffer from some limitations when it comes to the fault-tolerance of a critical element of the protocols, namely the Home Agent. The first is the requirement that the Home Agent must reside in the home network of the mobile host so that it can intercept IP packets (delivered by normal IP routing to the home network) destined for the mobile host while the latter is visiting a foreign network. In MIP, after the mobile host registers, the Home Agent sends out a gratuitous ARP to update the ARP cache entries of all hosts on the home network, mapping the mobile host's IP address to the Home Agent's link-layer address, and subsequently begins using proxy ARP to reply to ARP requests for the mobile host's IP address with it's (the Home Agent's) own link-layer address. A packet destined for the mobile host from anywhere in the Internet reaches the gateway on the mobile host's home network by usual IP routing, and then reaches the Home Agent because of the gratuitous and proxy ARPs. If the Home Agent is not located in the home network, gratuitous and proxy ARP can still be used within the Home Agent's subnet to allow the Home Agent to intercept packets originated from hosts within the home network which are destined for the mobile host. However, normal IP routing will not deliver packets from the rest of the Internet to the Home Agent, but only to the gateway on the mobile host's home network. Unless normal IP routing is modified or the usual intent and semantics of the routing protocols are modified it seems difficult to overcome this limitation in MIP and In situations where the home network is vulnerable to failure this becomes a serious problem. For example, consider mobile devices being used by military personnel in a battle zone. The home network of a Mobile IP-LR [Page 5] Expiration Date May 2000 Nov. 1999 particular user would be his or her company or platoon, but requiring the Home Agent to be in the home network would place the HA at a highly vulnerable location. Instead, it is essential that it be possible to place the Home Agent at a secure distant location. Similar considerations arise for other scenarios (e.g. disaster relief). The second limitation of MIP and MIP-RO is that it is not possible at present to replicate the Home Agent at various locations distributed throughout the network (and outside the home network) in order to achieve survivability. 1.3 Performance A well-known problem with MIP is that it uses triangle routing, i.e., packets from the correspondent host to the mobile host must in general travel via three (sub)networks: the correspondent host's subnet, the home agents subnet, and the subnet where the mobile host is currently located. Triangle routing incurs potentially significant overheads in the delay and network resources consumed for communication with mobile hosts. Triangle routing also places significant load on the home network and the Home Agent for processing every packet destined for the mobile host (and if co-located COAs are not used, on the Foreign Agent). An extension to the basic MIP protocol called Route Optimization (MIP-RO) [3] avoids triangle routing. It can be summarized as follows. When the Home Agent intercepts an IP packet destined for the mobile host it informs the sender, i.e., the correspondent host, of the mobile host's current COA. This is called a binding update message, and it also contains a Lifetime field indicating for how long the binding is valid. The correspondent host caches this information and sends subsequent packets by tunneling them directly to the mobile host's COA. The correspondent host issues binding requests to the Home Agent to refresh the binding before the Lifetime expires. When the MH moves to a new subnet the outdated mobility binding maintained at the correspondent host is updated as follows. The mobile registers with the new Foreign Agent, which not only forwards the registration to the Home Agent but also informs the old Foreign Agent. If the old Foreign Agent receives a packet from a correspondent host destined for the mobile host it issues a binding warning message to the Home Agent, which in turn issues a binding update message to the correspondent host; in addition, the old Foreign Agent can (optionally) tunnel the packet to the mobile host's new COA. A problem with MIP-RO is that packets sent by the correspondent host still use the triangle route until the correspondent host receives the Mobile IP-LR [Page 6] Expiration Date May 2000 Nov. 1999 binding update message. In addition, the bandwidth and protocol overhead associated with tunneling of packets is still present. Finally, as we discuss below, interoperability issues arise when MIP-RO is used in conjunction with other protocols that rely on examining IP headers of data packets for their operation. 1.4 Interoperability Consider the scenario where a protocol such as RSVP [4] is used to provide Quality-of-Service guarantees for communications between correspondent and mobile hosts. The RSVP protocol provides a mechanism for reserving resources along the path from a source host to a destination host so that subsequent data packets are guaranteed to have certain bandwidth available and meet certain delay bounds. The operation of RSVP can be summarized as follows. The source host sends an initial signaling packet (called a Path message) to record the route taken to the destination. The destination node determines the network resources needed to meet the desired QoS, and replies with a resource reservation packet (a Resv message) which travels, in reverse, exactly the route taken by the Path message, and as it does so, reserves bandwidth and processing resources at the routers along the reverse path. Subsequent data packets sent by the correspondent host thus enjoy guaranteed bandwidth and resources. RSVP also supports data packet filtering, enabling a receiver to specify in the Resv message which packets may utilize the reserved resources (e.g. only packets from a given sender IP address and port.) Problems arise when RSVP is used in conjunction with MIP or MIP-RO. Firstly, routers will not be able to recognize a Path message encapsulated while being tunneled, and thus will not record the information required for reservations to be effected by the resource reservation message. Thus the portion of the route where tunneling is used is viewed as a non-RSVP cloud, i.e., a network which does not support RSVP. The second problem is that routers along the tunneled portion of the route will not be able to implement data packet filtering, thus defeating one of the major beneficial features of RSVP [5]. While in MIP the tunneled portion of the route is from the HA to the mobile host (or the FA if co-located COAs are not used), in MIP-RO tunneling is used for the entire direct route from the CH to the mobile be reserved along the triangle route from the correspondent host to the mobile host. With MIP-RO, since RSVP issues Path messages periodically (in order to overcome the effects of routing changes, etc., that may take place in a fixed network), eventually resources will be reserved along the direct route to the mobile host. However, this also raises some Mobile IP-LR [Page 7] Expiration Date May 2000 Nov. 1999 issues. How soon the direct route to the mobile host is used now depends not only on the binding update delay but also the frequency at which Path messages are sent. RSVP has a local repair facility which allows the routing process at the CH to inform RSVP that a routing change has taken place, thus triggering the immediate transmission of a Path message without waiting for the Path refresh timer to expire. However, local repair is currently not a requirement of RSVP, and if a host does not implement it the Path message will be sent only when the timer expires (typically it may have a period of the order of 30 seconds.) In any case, unnecessary delay and resource consumption will still result, and the QoS guarantees desired may not be achieved since packets sent along the triangle route receive different treatment than those sent directly. MIP-RO. 2. Mobile IP with Location Registers In this section we will first describe the operation of MIP-LR assuming there is only a single HLR serving the mobile host; later we will describe the extensions for survivability. The basic flavor of MIP-LR is conveyed in the following diagram. +-----+ | HLR | | | +-------+ +-----+ | VLR | 2) Correspondent /|\ | | host queries | +-------+ mobile's HLR | /|\ 1) Mobile node for mobile's | | receives current IP \|/ \|/ advertisements address. +----+ +--------+ from VLR, |host| =======> | mobile | and registers +----+ | node | with HLR +--------+ 3) Host sends packets directly to mobile To motivate the description of MIP-LR, consider the major functions performed by the Home and Foreign Agents in MIP and MIP-RO: Mobile IP-LR [Page 8] Expiration Date May 2000 Nov. 1999 1. Agent and network discovery: Home and Foreign agents broadcast (or multicast) agent advertisements and respond to solicitations. This enables the mobile host to determine whether it is in its home or a foreign network. 2. Database maintenance: The Home Agent maintains the mapping from the mobile host's IP address to its COA. The Foreign Agent maintains the reverse mapping and/or the mapping from the mobile host's IP address to its link-layer (hardware) address in the foreign network. 3. Tunneling. The Home and Foreign agents encapsulate (and decapsulate) packets and forward them appropriately. 4. COA allocation. The Foreign Agent assigns a COA to the mobile host (if co-located COAs are not used.) In MIP-LR we eliminate the tunneling function. In addition, the database mapping the mobile host's IP address to its COA is maintained by an entity we call the Home Location Register (HLR), by analogy with cellular systems, since it is queried in a manner analogous to how the HLR is queried in cellular systems to determine the mobile host's location. As we will see shortly, unlike the Home Agent, it need not necessarily be located in the home network. In keeping with the cellular analogy, the Foreign Agent is re-named the Visitor Location Register (VLR). 2.1 MIP-LR operation 2.1.1 Subnet discovery Subnet discovery in MIP-LR is carried out as in MIP, using agent advertisements and solicitations by the HLR and VLR. 2.1.2 Registration The location of a mobile host is always registered at the HLR. When the mobile is at home the HLR simply maintains the identity mapping. When the mobile host moves to a foreign network it obtains a COA for that subnet, as for MIP. 2.1.3 Packet delivery A Correspondent Host wishing to send a packet to the mobile host for the first time must first discover the IP address of the mobile host's HLR (we will describe this process below, but for the moment note that Mobile IP-LR [Page 9] Expiration Date May 2000 Nov. 1999 it needs to be carried out relatively infrequently.) The correspondent host then issues a query to the HLR, which returns the mobile host's COA as well as the remaining registration Lifetime. The correspondent host then directly sends the packet to the mobile host's COA. The IP layer at the correspondent host thus hides the mapping from the mobile host's IP address to its COA from higher layers protocols (e.g. TCP) and the IP layer at the mobile host does the same for the reverse mapping. The correspondent host caches the mobile host's COA and uses the cached binding for subsequent packets destined to the mobile host. The correspondent host must refresh its binding cache by querying the HLR again before the mobile host's remaining registration Lifetime expires. 2.1.4 Cache maintenance The mobile host maintains a list of correspondent hosts that have sent messages to it during the current registration Lifetime. When the mobile host moves to a new subnet it informs these hosts of its new COA in the new subnet by means of a Binding Update message. This mechanism for updating the cache at correspondent hosts is similar to that defined for Mobile IP in IPv6 [6]. We refer to this as eager caching and omit further details here. Packets from the correspondent host which are in flight, i.e., after the mobile has moved but before the binding update has reached the correspondent, may reach the old subnet and be lost. However, MIP-LR allows the use of a mechanism similar to that in MIP-RO, where the VLR in the old subnet is notified when the mobile has registered at the new subnet, and the old VLR can forward packets to the new VLR. Unlike MIP-RO, the old VLR need not send a binding warning to the HLR in this case. 2.1.5 Determining hosts which speak MIP-LR In MIP and MIP-RO the correspondent host does not take any special action when communicating with mobile hosts. MIP-LR sacrifices this transparency for improved survivability, performance, and interoperability with RSVP. Thus in MIP-LR the correspondent host must issue a query to the HLR to discover the mobile's current address. In principle, this query could be sent for all hosts, fixed and mobility-capable, that a correspondent host wishes to communicate with. For certain specialized enterprise environments, (e.g. military battlefield environments) where the substantial majority of hosts are mobility-capable this may be reasonable. However, this would not be efficient in the situation where most hosts are fixed. In that case, the correspondent host must be able to discover, before launching the Mobile IP-LR [Page 10] Expiration Date May 2000 Nov. 1999 query to the HLR, whether the destination host is fixed or is mobility-capable. In addition, if the destination host is mobility-capable, the correspondent host must discover whether it implements MIP-LR. Since the latter requirement subsumes the former, it is sufficient for the correspondent host to discover which hosts speak MIP-LR. Different possible approaches to doing this are: 1. Address space partitioning. Certain address ranges in the enterprise system are known to belong to mobility-capable hosts. An example of address space partitioning is in the public telephone system (e.g. 800 numbers.) While this is not useful in general, for closed networks where a system administrator has control over a private IP address space this might be feasible. 2. An off-line discovery mechanism, e.g. a notification or directory scheme. Correspondent hosts within the enterprise system are periodically notified, or periodically discover by querying a directory, which hosts are mobility-capable and implement MIP-LR. For a given host this information only changes when its status changes, i.e., it is first introduced into the system or when it is upgraded from being a fixed to a mobility-capable host. Thus the period for obtaining this information is dependent upon the characteristics of the network installation, but typically would be of the order of hours or even days. During the interval after a mobility-capable host changes status but before this information has been obtained by the other hosts in the system, it can still receive packets, although less efficiently, as follows. The mobility-capable host registers with the HLR as per MIP-LR. A correspondent host that erroneously believes this mobility-capable host is fixed sends the packet to the destinations permanent IP address without querying the HLR. If the destination host is in its home network, the packet is delivered correctly. Otherwise, if the host has moved, an ICMP message indicating that the host is unreachable will be returned to the correspondent; at that point the correspondent queries the HLR and obtains the destinations COA and subsequently communicates with the host using MIP-LR. 2.2 Obtaining the HLR address In this section we discuss how the correspondent host obtains the address of the mobile host's HLR. As we shall see, this is related to the issues of HLR survivability, and later we present two alternative schemes for obtaining the HLR address as well as maintaining HLR survivability. If the HLR serving the mobile host was located in the Mobile IP-LR [Page 11] Expiration Date May 2000 Nov. 1999 mobile's network, the following approach could be used. The correspondent host uses the mobile host's permanent IP address to issue the query. If the mobile host is at home, the mobile responds with the identity mapping. If the mobile is away from away from home and has registered, the query will be trapped by the HLR, e.g. by using a link-layer mechanism such as issuing a proxy and gratuitous ARP message mapping the mobile host's permanent IP address to the HLRs link-layer address. The HLR will respond to the query with the mobile host's COA. However, for survivability the HLR may not be located in the mobile's home network. In that case, two possibilities arise: that a single HLR suffices, or multiple HLRs are required. In a small system it might be possible that a single HLR suffices to support all the mobile hosts in the system. In that case every correspondent host may be configured with the address of the HLR; to improve survivability, the HLR can be implemented on a commercial hot-standby fault-tolerant platform. In general, however, multiple HLRs may be required to distribute the workload, to reduce the network communication cost of contacting the HLR, and to obtain survivability, by scattering the HLRs throughout the network. In section 3 we suggest two possible approaches for maintaining the multiple HLRs. 2.3 Discussion of MIP-LR Design In this section we briefly discuss some of the design implications and alternatives for MIP-LR. 2.3.1 Interoperability with MIP Although MIP-LR is designed for closed enterprise environments, it can interoperate with hosts outside the environment using MIP as follows. Packets from correspondent hosts outside the system are trapped at the border gateways. The border gateway (or a host attached to the gateway) searches its cache or queries the HLR to obtain the mobile's COA and tunnels the packet to the mobile. To interoperate in this fashion the mobile must have the ability to decapsulate packets. This method of interoperability is similar to what is carried out by Network Address Translators (NAT) to permit multiple local IP addresses on a closed subnet to share a limited pool of globally unique IP addresses for communication. MIP-LR can interoperate with hosts using MIP, even inside the closed network, as follows. There is a Home Agent in the mobile's home network, as required by MIP, which can also act as an HLR. Mobiles obtain co-located COAs from DHCP servers as permitted by MIP, and register with the Home Agent in addition to the HLRs. Packets addressed to the mobile host's permanent address are delivered to its home network and tunneled to the mobile as for MIP. We omit further Mobile IP-LR [Page 12] Expiration Date May 2000 Nov. 1999 details for brevity. Note that hosts which speak only MIP in a mixed environments where both protocols interoperate do not suffer any additional penalties. One could imagine a subset of hosts in the closed environment which have been configured to use MIP-LR, and these nodes would then obtain additional benefits. 2.3.2 Survivability of VLRs We have focused on survivability of HLRs. Survivability of VLRs is obviously equally important. However, this can be ensured by existing methods for ensuring survivability of a computer connected to a local IP subnet, and numerous protocols have been developed for this. Ensuring VLR (or Foreign Agent) survivability itself does not impinge directly on the central protocol functions of message routing performed by MIP-LR (or MIP, for that matter). 2.3.3 Eliminating VLRs An alternative design for MIP-LR is one where the VLR or Foreign Agent is eliminated. The advantage of this approach is that there is no Foreign Agent function necessary in every subnet capable of supporting mobile hosts. Many of the mechanisms and arguments for eliminating Foreign Agents and using co-located COAs have been presented previously in the MoquitoNet system [7]. Here we consider some specific to MIP-LR. As mentioned previously, in MIP and MIP-RO the Foreign Agent detunnels (typically by decapsulating) packets tunneled to the mobile host, can allocate a COA, and performs functions for the mobile to discover the subnet it is in (agent advertisement and response to solicitations). With no Foreign Agents we can separate these functions and deal with them as follows. Since there is no tunneling, no decapsulation is required. Allocation of COA can be handled by existing methods to perform dynamic address allocation, e.g. DHCP. And for subnet discovery we place a simple Advertisement Agent (AA) in each subnet (which may in fact be the subnet router, appropriately-configured). Eliminating the VLR or Foreign Agent helps to improve the survivability of the mobility management scheme, especially for subnets that may be particularly vulnerable to failure (e.g. platoons in the forward area of a battlefield.) Although an Advertisement Agent is still introduced specifically to support mobility, note that it's functions are much simpler than those of a Foreign Agent, so that recovery is far simpler if an Advertisement Agent fails. Mobile IP-LR [Page 13] Expiration Date May 2000 Nov. 1999 To provide survivability of VLRs or Foreign Agents, multiple hosts in the subnet would have to be able to serve in that role and perform all the functions outlined above. In contrast, for survivability of Advertisement Agents, a host serving as a backup need only be able to issue broadcasts specifying the identity of its subnet and respond to solicitation messages. An additional issue that arises then is that of IP address usage. We have discussed these issues in [17]. 3. Managing Multiple HLRs So far we have discussed that survivability of the HLR in MIP-LR is enhanced by being able to place the HLR outside the home network when the latter is vulnerable. We now turn our attention to the situation where multiple HLRs are introduced for survivability reasons (and possibly to improve performance and reduce network resource consumption.) With multiple HLRs, a method is required for maintaining them. We present two alternative methods in this section. 3.1 Translation Servers We introduce databases, called Translation Servers (TS), which store the mapping from a host's IP address to the IP address of the HLR serving that host. Since this information does not change frequently, a correspondent host can cache the response for relatively long periods of time. In the context of this approach we consider the situation where there are layers of vulnerability in the network. For example, consider a military scenario where host machines belong to various levels of the military hierarchy (brigade, platoon, squad, etc.) There are more hosts at the lower levels of the hierarchy than at higher levels and typically they are more mobile. In addition, hosts as well as links at the lower levels are more vulnerable to attack, failure, and destruction. As discussed previously, if a host is at a low level in the hierarchy, it is desirable to place its HLR outside the home network; however, the further away the HLR is placed, the greater the cost of mobile host registration (and, in general, of packet delivery to mobile hosts). We thus assume that HLRs are placed at locations that are less vulnerable than those of individual hosts, and TS are placed at higher levels in the hierarchy which, for our purposes, can be regarded as being essentially secure. (Again, for fault-tolerance, the TS may be implemented on hot-standby platforms.) Mobile IP-LR [Page 14] Expiration Date May 2000 Nov. 1999 Introducing TS provides a useful indirection step that allows for flexibility in managing and assigning mobile hosts to HLRs. Thus, given that HLRs are less vulnerable than hosts but still not secure, HLRs will fail from time to time. In addition, HLRs may become overloaded; or as a host moves the communication cost and delay to communicate with its HLR may increase to an unacceptable level; or it may be desirable to assign the mobile host to an HLR which is located close to the majority of its correspondent hosts. Thus for a variety of reasons we assume that it will be desirable to be able to change the HLR serving a given mobile host. Maintaining the mapping from a mobile host's IP address to its HLRs IP address in a TS provides a convenient mechanism for dynamically reassigning mobile hosts to HLRs. Notice that the mobile host itself need not know its own HLRs address; the mobile can discover it dynamically by querying the TS also. 3.1.1 Single Translation Server For the moment, assume that a single TS suffices for the entire system, and its address is known to all hosts. Then the mobile host performs registration using the procedure given in pseudo-code below, where r > 0 is the number of HLRs the mobile host must register at for survivability. Note that the same procedure is used when the mobile registers because it has moved or because its current registration Lifetime is about to expire. Registration requests and responses use datagrams to avoid the overhead of connection setup but are retransmitted when timeouts occur to provide a degree of reliability. register(r){ Registration_state = TRYING; /* HLR_list is list of HLRs MH is currently assigned to. */ /* MH.IP is this mobile hostĘs permanent IP address. */ /* The second argument of query_TS specifies known HLRs */ /* and third argument specifies total number of HLRs */ /* desired. */ if (length(HLR_list) < r) HLR_list = query_TS(MH.IP, HLR_list, r); Pending_HLR = HLR_List; while (Registration_state != SUCCESS){ Retries = 0; while (Retries++ < MAX_RETRY){ Issue timestamped registration request for all Pending_HLR if (ACK received from all Pending_HLRs before timeout){ Registration_state = SUCCESS; return; Mobile IP-LR [Page 15] Expiration Date May 2000 Nov. 1999 } else if (ACK received from some HLRs before timeout){ Registration_state = PARTIAL_SUCCESS; Update Pending_HLR list } } /* One or more of the r HLRs has failed */ /* TS returns other HLRs and updates its own records */ Pending_HLR = query_TS(MH.IP, HLR_List, Pending_HLR, r); Update HLR_List } } In the register procedure the choice of the number of HLRs at which the mobile must register (i.e., r) can be left to the mobile, or it can be left to the TS with the mobile providing a hint in its query request (i.e., query_TS()) based upon its current requirements. The choice of which particular HLRs serve the mobile host is left to the TS. This is because we assume that the TS will have better knowledge of the availability of HLRs in the system than the mobile, and may assign mobile hosts to HLRs based on a variety of criteria, e.g. proximity, load balancing, etc. (The design of this assignment algorithm is outside the scope of the present document.) If one of the r HLRs has failed since the last registration by the mobile host, the registration request sent by the mobile host to that HLR fails. In that case the mobile requests another HLR from the TS and attempts to register there. The TS returns a new HLR and updates its own records. Note that after at least one registration request succeeds (i.e., state PARTIAL_SUCCESS is reached) the mobile may choose to allow other activities (e.g., initiating communication with other correspondent hosts) to continue in parallel with the registration process. This is so that if (one or more) HLRs have failed the mobile is not blocked until registration is complete at all r HLRs. find(MH.IP, r){ if (COA with unexpired Lifetime for this MH exists in Binding Cache) return (COA); Pending_HLR = null; if (HLR_List for this MH does not exist in HLR_List cache) HLR_list = query_TS(MH.IP, Pending_HLR, r); Phase = 0; while (Phase++ < MAX_PHASE){ /* Choose some HLR(s) to query */ Pending_HLR = select(HLR_list); Mobile IP-LR [Page 16] Expiration Date May 2000 Nov. 1999 Retries = 0; while (Retries++ < MAX_RETRY){ Issue binding request to all Pending_HLR if (reply received from any pending HLRs before timeout){ Put COA & Lifetime with latest timestamp in Binding Cache Update HLR_List in HLR_List cache if necessary return (COA); } /* Pending HLRs have all failed. Retry by some */ /* policy, e.g. Binary Exponential Expansion */ Pending_HLR = retrypolicy(Phase, Retries, r); } /* All HLR(s) in HLR_List have failed. */ /* Query TS for m alternates using some retry policy */ m = retrypolicy(Phase, Retries, r); HLR_list = query_TS(MH.IP, Pending_HLR, m); Pending_HLR = null; } return (FAIL); } A correspondent host wishing to contact the mobile host carries out the find() procedure. The correspondent obtains a list of r HLRs serving the mobile from the TS. (The number as well as the identity of HLRs which the TS actually returns could be left up to the TS.) This list is maintained in a cache, called the HLR_List cache, separate from the Binding Cache which keeps the mobile's COA. The correspondent selects and queries a subset of the HLRs assigned to the mobile, and uses the COA with the latest timestamp. If a choice is available the correspondent selects an HLR to query using any criterion it chooses (proximity, randomly, etc.) Since the mobile host always registers at all the HLRs it is assigned to, the strategy where the correspondent host chooses only one HLR out of the HLRs returned by the TS is called a Write-all-Read-any strategy. Note that essentially the same procedure is used whether the correspondent is trying to contact the mobile for the first time, trying to contact the mobile for the first time after the Lifetime of the cached mobility binding (mapping the mobile host's IP address to its COA) has expired, or it is trying to refresh its cached mobility binding before the current Lifetime of the binding expires. The number of HLRs requested by the correspondent, as well as the strategy it uses to query the HLRs, reflects a balance between latency Mobile IP-LR [Page 17] Expiration Date May 2000 Nov. 1999 and resource consumption. If latency is to be minimized, the correspondent requests all the HLRs serving the mobile (r is set to a special value ALL) and queries all of them in parallel; to minimize resource consumption, the correspondent queries one HLR at a time. We suggest the following Binary Exponential Expansion policy as a compromise: the correspondent host requests the addresses of all HLRs (r = ALL), and at each retry (Retries is incremented), it queries 2**Retries HLRs in parallel. There are race conditions present in the protocol when failures occur, so that for short intervals the HLRs assigned to a mobile may contain inconsistent information and the correspondent may obtain incorrect results. Similar situations occur in MIP and MIP-RO also, even without replication of location information. The costs of using more complex protocols to avoid this do not seem justified, particularly in a mobile wireless environment where the underlying communication links are expensive and may not be well-behaved. Our approach is to simplify the protocols and rely upon retransmissions and retries at the correspondent host instead. To summarize, the scheme presented in this section: (1) assumes the existence of a TS with an address known by all hosts in the system; (2) for the HLRs assigned to a given mobile host, a Write-all-Read-any protocol is used; (3) in case of HLR failure, the mobile requests alternative HLRs from the TS, and other activities at the mobile can continue; (3) in case of HLR failure, the correspondent uses a Binary Exponential Expansion policy. 3.1.2 Multiple Translation Servers Multiple TS would only be required to provide additional survivability, reduce the latency of TS queries by distributing load, or to reduce the bandwidth consumption due to TS queries by scattering them throughout the network. For most closed network scenarios a single (fault-tolerant) TS probably suffices. This is because we assume the TS is in a secure location and the load on the TS is likely to be low. A mobile host contacts a TS only: (1) the first time it is installed, if it is not pre-configured with its list of HLRs; (2) if HLR failures occur and replacements are required. A correspondent host contacts a TS only: (1) when sending a packet to a mobile for the very first time; (2) if the mobility binding for a host it wishes to contact has expired or been deleted from the cache and the list of HLRs serving the mobile has expired or been deleted from the HLR_List cache; (3) if HLR failures occur and alternate HLRs are required. Thus the TS workload will be high only if: (1) cache sizes at mobiles or correspondent hosts are very small, or (2) there are many mobile Mobile IP-LR [Page 18] Expiration Date May 2000 Nov. 1999 hosts who are contacted by correspondent hosts for the first time or after long intervals, or (3) if there are frequent HLR failures. We propose the following scheme if multiple TS are required in the system. Each host in the system knows the addresses of all the t TS in the system, and in addition has a hash function f which maps a mobile host's IP address to one or more integers j, where 0 < j < (t + 1), and TSaddr(j) is the IP address of a TS serving the mobile. When the set of HLRs serving a mobile host is to be updated (for load balancing, failure recovery, addition of new HLRs, etc.) then all the TS serving the mobile are updated. However, to find the set of HLRs serving the user, only one of the TSs need be queried; since TS queries are likely to be much more frequent than updates, the scheme makes the query process less expensive than update. Note that with this scheme changing the set of set of HLRs serving a mobile does not require changing any information (the TS addresses or the hash function f) at any host. This information is only modified if the set of TSs is changed (an infrequent operation) or more TSs are added to support increased workload (an even more infrequent operation). Even in that case, modifying the hash function itself can be avoided, using a technique based on dynamic hashing [9,10] as follows. (For ease of exposition in the following we assume that although there are multiple TS, each mobile is only served by a single TS; extension to the case where a mobile is served by multiple TS is straightforward.) Let f return a large number of bits, and we use k of them (e.g. the least significant k bits) as an index into Tsaddr, the table of TS addresses. Now suppose a particular TS, TS(j), is overloaded and a new TS is to be added. At TS(j), the hash function f is applied to the address of each mobile served by that TS, except now instead of using k bits returned from f, we use (k + 1) bits. The extra bit returned by f is examined; if it is zero the record for that mobile (mapping the mobile's IP address to the list of its serving HLRs) is moved to the new TS; otherwise, it remains in the old TS. Once all the records in TS(j) have been thus processed, the address of the new TS is broadcast to all hosts in the system and each host increments k; the new TS can now be used to offload queries and updates to TS(j). Observe that this scheme does not require modifying the HLRs, or any of the TSs that is not overloaded, or any modification to the software in any host, making it highly suitable for on-line system upgrade. 3.2 Quorum Consensus In this section we present an alternative scheme for maintaining Mobile IP-LR [Page 19] Expiration Date May 2000 Nov. 1999 multiple HLRs that does not use Translation Servers. Instead, it is assumed that every host in the system knows the address of all HLRs in the system, and a quorum consensus method is used. Quorum consensus has been previously proposed as method of maintaining replicas in distributed database systems [9] We first describe a basic Quorum Consensus (QC) algorithm to introduce quorums. The Basic QC Algorithm. In Basic QC, we define a Read Threshold (RT) value and a Write Threshold (WT) value such that h < RT + WT < (2h + 1) and h/2 < WT < (h + 1), where h is the total number of HLRs. A mobile host must ensure that it registers its COA, along with a timestamp, with any WT number of HLRs; a correspondent host must read any RT number of HLRs and use the value with the latest timestamp. The conditions on WT and RT ensure that the set of HLRs written by the mobile host (the write quorum) always intersects with the set of HLRs read by the correspondent host (the read quorum.) The identities of the HLRs in the read and write quorums do not matter for QC to maintain the mobile's COA correctly. The mobile and correspondent hosts can thus use any suitable criterion (randomization, proximity, etc.) to select them. Note that randomization provides load-balancing and keeping the identities of the quorum members arbitrary enhances survivability. 0 / \ 1___2 / \ / \ 3___4___5 / \ / \ / \ 6___7___8___9 / \ / \ / \ / \ 10__11__12___13__14 Figure 1: Example of the Triangle Lattice (TL) System for d = 5 [12] Also observe that the QC algorithm can be implemented within the general framework of the routines register() and find() described in Section 3.1.1, since it basically replaces the query_TS() routine. In particular, the Binding Cache and the HLR_List cache are still maintained. We omit further details due to lack of space. Quorum algorithms are evaluated using several criteria [11], the most important being quorum size, defined as the size of the smallest quorum in the system, since that determines the cost (in terms of bandwidth consumption or message complexity) of accessing the members of the quorum. The cost of failures is the additional number of processors Mobile IP-LR [Page 20] Expiration Date May 2000 Nov. 1999 that must be contacted in order to establish a quorum when failures occur. In the case of the Basic QC algorithm, the quorum size is O(h) and the cost of a failure is O(1). Many variations of quorum algorithms have been designed to improve the performance of quorum systems. We use a class of quorum systems called a planar quorum, and specifically a Triangular Lattice (TL) [12] and develop an optimized version of TL called Optimistic TL (OTL) suitable for our application. We first describe the basic TL system using an example (see Figure 1). In the TL algorithm the processors in the system (in our case, the HLRs) are assumed to be at the vertices of a virtual triangle lattice. A quorum consists of a minimal path connecting two of the sides of the triangle, and a second minimal path connecting the first minimal path to the third side. For example, in Figure 6 the set {1, 4, 8, 9, 12} is a quorum. It is straightforward to see that any two quorums intersect. It is easy to show that quorum size for TL equals d, the length of a side of the triangle. The cost of a failure is O(1); in fact it is 6, since at most 6 processors have to be contacted to find an alternate processor from amongst those surrounding the failed processor. Optimistic TL algorithm. An issue with most quorum systems, including TL, is that a relatively large number of processors must be contacted even when there are no failures. For our application, in the case of Basic QC O(h) HLRs must be contacted; TL reduces this to O(h). In the case of registrations, this is acceptable since the timing and extent of failures cannot be predicted; for queries, however, it is desirable to reduce the number of HLRs contacted without increasing the latency of obtaining the mobile's COA. Unlike general quorum applications (mutual exclusion, replica control, etc.), where the reader and writer of a quorum generally do not communicate directly, in our application the reverse is true: the quorum system is designed to enable them to communicate. We exploit the special nature of our application to develop Optimistic TL (OTL) which consists of two simple optimizations to TL: 1. The first time a correspondent host searches for a mobile, it must contact all the HLRs in the quorum. However, as a result of this query the correspondent becomes aware of the set of HLRs, S, |S| > 0, that lies at the intersection of the read and write quorums, namely, the HLR(s) with the latest value of the mobile's COA. For subsequent queries, the correspondent contacts only one of the intersecting HLRs, say H in S. If there is no response within the timeout period when the Mobile IP-LR [Page 21] Expiration Date May 2000 Nov. 1999 correspondent queries H, the correspondent infers that H has failed or is no longer part of the mobile's write quorum. The correspondent then queries one of the HLRs in S-H if |S-H| > 0, or the 6 HLRs adjacent to the failed node otherwise. 2. In MIP-LR (as in Mobile IP for IPv6 [6]) the mobile maintains a list, Active_CH, of correspondent hosts with which it is in active communication, i.e., hosts with which it has exchanged a packet within the current registration Lifetime. The mobile adds to each entry in this list a single bit, First, which is set when the correspondent host is added to the list. When the mobile changes registration areas it sends binding updates to all correspondent hosts on the Active_CH list as usual. In addition, for hosts with First set, the mobile includes in the binding update message the indices of the HLRs in its current quorum, thus informing the correspondent of its entire quorum, and resets First. (If the mobile refreshes its registration before it has moved, it also sends its quorum list to the hosts with First set, and resets First.) 4. Remarks Our contributions in this document are as follows. We present the design of a protocol, MIP-LR, that provides enhanced survivability over basic Mobile IP and Mobile IP with Route Optimization by: 1. allowing HLRs to be placed outside the home network, and hence outside subnets that may be especially vulnerable to failure. 2. Allowing HLRs to be replicated outside the Home Network. MIP-LR also provides improved performance over MIP by avoiding triangle routing and encapsulation of data packets, and better interoperability with protocols such as RSVP which attempt to provide QoS guarantees. We note that given the basic framework of using location registers for MIP, the ideas behind the numerous variations of PCS and cellular location register schemes which aim to make them more efficient (by forwarding [13], profile replication [14], local anchoring [15], hierarchical organization [16] and other methods) can be applied and leveraged for IP networks, although obviously some modifications may be required in the details. Finally, we observe that the techniques presented for maintaining multiple HLRs (Translation Servers and Optimistic Triangle Lattice Quorum) can be applied to PCS and cellular schemes and potentially other areas. Mobile IP-LR [Page 22] Expiration Date May 2000 Nov. 1999 5. Security considerations Security issues are not discussed in this document. 6. Acknowledgments We thank Tony McAuley, Archan Misra, Sue Thompson, and Danny Yang of Bellcore, Li Fung Chang of AT&T, as well as Mitesh Patel of U. S. Army CECOM for their comments and many useful discussions. 7. Authors' addresses Ravi Jain Telcordia Technologies (formerly Bellcore) 445 South Street Morristown, NJ 07960 Phone (973) 829-3178 Email: rjain@telcordia.com Thomas Raleigh Telcordia Technologies (formerly Bellcore) 445 South Street Morristown, NJ 07960 Phone (973) 829-4321 Email: tom@telcordia.com Michael Bereschinsky US Army CECOM Fort Monmouth, NJ Phone (732) 427-2634 E-mail: bereschi@doim6.monmouth.army.mil Charles Graff US Army CECOM Fort Monmouth, NJ Phone (732) 427-4456 E-mail: graff@doim6.monmouth.army.mil Mobile IP-LR [Page 23] Expiration Date May 2000 Nov. 1999 REFERENCES [1] Perkins, C., (ed.), IP Mobility Support, RfC 2002, Oct. 1996. [2] Droms, R., Dynamic Host Configuration Protocol, Internet RfC 1541, Oct. 1993. [3] Johnson, D. B., and C. Perkins (eds.), Route Optimization in Mobile IP, Internet Draft, draft-ietf-mobileip-optim-06.txt, Nov. 1997. [4] Braden, R., et al, Resource ReSerVation Protocol (RSVP) -- Version 1 Functional Specification, Internet draft, draft-ietf-rsvp-spec-16.txt, June 1997. [5] Zhang, L., S. Deering, D. Estrin, S. Shenker and D. Zappala, RSVP: A New Resource ReSerVation Protocol, IEEE Network, Sep. 1993. [6] Perkins, C., and D. Johnson, Mobility support in IPv6, Proc. Mobicom '96, 27-37, Nov. 1996. [7] Mary Baker et al., Mobility Support in MosquitoNet, Proc. MobiCom '95, Nov. 1995. [8] Jain, R., T. Raleigh, C. Graff and M. Bereschinsky, Mobile Internet Access and QoS Guarantees using Mobile IP and RSVP with Location Registers, Proc. ICC '98, June 1998. [9] Bernstein, P., Hadzilocas and Goodman, Distributed Databases, Addison-Wesley, 1988. [10] Jain, R., S. Rajagoplan, and L. F. Chang, Phone number portability for PCS systems with ATM backbones using distributed dynamic hashing, IEEE J. Sel. Areas Comm., 96-105, Jan. 1997. [11] Naor, M. and A. Wool, The load, capacity and availability of quorum systems, Proc. IEEE Symp. Foundations of Computer Science, 214-225, 1994. [12] Bazzi, R., Planar Quorums, Proc. Tenth Intl. Workshop on Distributed Alg., Springer-Verlag, Oct. 1996. [13] Jain, R., and Y. -B. Lin, An auxiliary user location strategy employing forwarding pointers to reduce network impacts of PCS, ACM Wireless Networks, 1995. Mobile IP-LR [Page 24] Expiration Date May 2000 Nov. 1999 [14] Jannink, J., D. Lam, N. Shivakumar, J. Widom, D. C. Cox, Efficient and flexible location management techniques for wireless communication systems, Proc. ACM MobiCom 96, Nov. 1996. [15] Ho, J. S. M., and I. F. Akyildiz, Local anchor scheme for reducing location tracking costs in PCNs, Proc. ACM MobiCom 95, Nov. 1995. [16] Wang, J. Z., A fully distributed location registration strategy for universal personal communications, IEEE J. Sel. Areas. Comm., Aug. 1993. [17] Jain, R., T. Raleigh, D. Yang, L. F. Chang, C. Graff, M. Bereschinsky and M. Patel, Mobile IP with Location Registers: Improving performance, availability and interoperability, Proc. IEEE Infocom, Mar. 1999.