Computer Networks and ISDN Systems 26 (1993) 357-369 357 North-Holland Providing continuous network access to mobile hosts using TCP/IP Charles Perkins IBM T.J. Watson Research Center, Hawthorne, NY 10532, USA Abstract We present a solution to the problem of providing continuous network access for mobile hosts using the Internet Protocol (IP). Using IP's Loose Source Route option, mobile hosts are able to communicate with their correspondent hosts via an optimal route, no matter how often their location changes. Our solution is fault tolerant, scales well, is easy to administer, is invisible to applications running either on mobile hosts or their servers, and requires no changes to existing systems. Our solution will handle movement between connected networks (e.g., different buildings) without noticeable degradation of performance (except, of course, when the mobile user is out of range of any cell). We show also how our solution adapts to the use of encapsulation. We expect to enable mobility of computers in general, including wired computers. Keywords: Mobile hosts; Network access; TCP/IP; Loose Source Route (LSR) Introduction Recently a great interest has developed in providing computer users with the ability to move their computers from place to place. This trend is accelerating as computers become small and lightweight enough so that they may be easily packed along with one's other travel necessities. In addition, battery power allows one to use a computer in many more settings, without regard to the availability of electric outlets--for in- stance, outdoors or in an airplane. Now there is also a trend to provide computers with wireless communications facilities, so that data might be transferred from a portable computer to other data processing facilities with no need for cum- bersome wiring and much less regard for one's current location. However, attaining the ideal of seamless and constant contact with other systems, even when physically possible, creates new re- quirements that existing operating systems and network protocols were not originally designed to Correspondence to: Ch. Perkins, IBM T.J. Watson Research Center, Hawthorne, NY 10532, USA. E-mail: perk@watson. ibm.com. meet. Only recently has there been sufficient computing power and resources packaged in a lightweight system to create the widespread de- sire for computer builders to attain this ideal. A good example of existing network protocols is provided by the Internet protocol suite 2, including TCP/IP. The Transport Control Proto- col (TCP) provides a number of useful services to application programs, presenting the appearance of a reliable data channel. The Internet Protocol (IP) 11 is used by TCP (and other protocols) to perform the actual delivery and routing of data packets from one computer to another. We have developed a solution that enables mobile comput- ers, using IP, to roam from one area to another, subject to very few restrictions other than the obvious need for wireless equipment to be lo- cated close enough to communicate with the mo- bile computer. Once a building has been equipped with enough wireless transceivers to cover all the likely places a computer might be used, and the transceivers are connected so that they can com- municate with the rest of the building's comput- ing resources, computers using this solution will present to the user the appearance of a network connection which is even more useful and conve- 0169-7552/93/$06.00 © 1993 - Elsevier Science Publishers B.V. All rights reserved
`
`

`

`358 Ch. Perkins / Continuous network access to mobile hosts nient than the wired network connections in com- mon use today. TCP/IP-based applications will work just as if there were a direct, wired connec- tion to the building's networks. Indeed, we claim that among the requirements for any realistic solution enabling network access to mobile com- puters is exactly such "application transparency". We foresee the time when such mobile computers will outnumber today's fixed, statically located computers. In the next section, definitions are given and the relations between them discussed. We show why existing IP implementations are insufficient to enable seamless mobile computing, and intro- duce the concept of a virtual network for mobile computers. The following section outlines a very simple but workable solution for wireless IP net- working, and points to the need for further im- provements. Then there is a brief review of "source routing", which is an option within IP useful for making some of the improvements. We then detail our implementation using "loose source routing". After our implementation is de- scribed, we will attempt to point out some of the difficulties that are caused by the fact that many existing implementations of IP's loose source routing are defective. We then describe changes to our solution that allow us to keep most of the benefits but also to work in situations where existing host systems do not permit the use of loose source routing, or where such existing sys- tems cause the expected benefits to disappear. Comparisons with other approaches are pre- sented, along with a re-interpretation of our ap- proach in the light of a more generalized ap- proach we developed based on this work. Lastly, some possibilities for future work are described. Definitions To begin with, let's settle on some particular terminology. A mobile computer will be referred to as a Mobile Host, MH for short. For the purposes of this paper, MHs will be presumed to be in communication with wireless equipment which is connected to some wired network in- stalled in a building. This is not universally true! For one thing, it is perfectly reasonable to imag- ine that users of a collection of MHs might have a need to communicate between themselves inde- pendent of any other computers. The communi- cation requirements of such MHs could be met by techniques which have been called "ad-hoc networking", but we will not consider such tech- niques in this paper. Besides that, computers can be considered "mobile" even without any data communication, or with wired data communica- tions. For example, a user might wish to discon- nect from an office Ethernet connection and re- connect via a telephone link shortly after. The methods described in this paper can, at best, be only imperfectly adapted to meet such needs. Accepting these limitations, let's define the re- gion throughout which a particular transceiver (assumed to be wired into the building's network) can detect transmissions from a MH to be that transceiver's "cell", and call such a transceiver which defines the cell a "Mobile Access Station", MAS for short. These agents have also been referred to elsewhere as base stations. The model of mobility we wish to enable, then, is that of a MH roaming through connected, adjacent, or overlapping ceils defined by the placement of MASs in a building; and, the MASs are supposed to be connected to the other data processing Charles Perkins is involved with developing mobile computer systems at IBM T.J. Watson Research Center, in Hawthorne, NY. His previous projects involved developing multiprocessor operating systems using Mach. Before coming to IBM, he worked on multiprocessor systems and user interface technology at Tektronix, in Beaverton, OR. Charles holds a M.A. in mathematics, and a M.E.E. degree from Rice University.
`
`

`

`Ch. Perkins / Continuous network access to mobile hosts facilities available within an enterprise via a stan- dard network of IP routers and IP addressable computers. If the enterprise has only a single network, then all the IP hosts in the enterprise will be addressable via IP addresses on the single net- work. This situation admits a particularly simple solution to the problem of enabling mobility. One could merely ensure that the MHs also have IP addresses on the same network as the other en- terprise network resources, and require the MASs to perform a "bridging" function between the wireless domains of their ceils, and the existing single wired network. This "bridging" function can be performed using the "Spanning Tree" bridging tree algorithm as described in 10. How- ever, such a solution is not immediately applica- ble to enabling mobility for MHs roaming be- tween MASs located on multiple networks. In- deed, MASs may be addressed in seemingly arbi- trary ways so that the mobile users would rarely be aware of which network the closest MAS might be on. So let's consider the case where the available cells are on different networks (e.g., different floors). In addition, let's assume that the MH users want to be able to keep all their TCP applications active even while moving between ceils on different networks. This is very likely to be the case; even when the users "lose touch" momentarily, they would be quite irritated if all their application windows disappeared or had to be reinitialized. However, for enterprises not wishing to offer such convenience, there is a very simple solution for mobility. That is, users can be required to re-initialize their computer each time they move to a new cell; part of the re-initializa- tion would assign a newly allocated network (IP) address to the user. One can also construct hy- brid schemes; for instance, a system can be de- signed with MASs serving as "bridges" to the networks they are attached to, and users be warned that their sessions or windows will re- quire re-initialization if they move from one net- work to another (but not as long as they stay on the same network). Existing IP network applications operate un- der the assumption that the client or server's IP address does not change throughout the life of the network connection (or, "session"). To allow a mobile host, then, to roam between cells on different networks strongly indicates that the MHs ( Router Ne, ,,rk2 Network I ~ ~ Mobile Access Station .,,~, MH Fig. 1. Internetwork mobility. 359 could not use IP addresses associated with the MASs controlling the cells, because then the ap- plications running on them would have to be reinitialized each time a MH moved, contrary to our goals. We instead allow the MHs to have IP addresses associated with a new, but physically far different, network, called a "mobile network" (also known as a "virtual network"). If this new network has a physical realization at all, it seems fairly difficult to pin it down. But, at least we have overcome the static association of our MHs with any particular wired network address; our new problem is delivering packets to a MH which is not located on the existing wired networks known to the enterprise routers. The first step in solving this problem is to build a router for our mobile network, called the Mobile Router (MR for short), even though the actual computer im- plementing the Mobile Router function may be far from mobile itself. This Mobile Router may be located anywhere on the existing wired net- work, and (like any IP router) advertises reacha- bility to its particular network. Packets destined to the mobile network (i.e., to a MH) will (in the absence of further information) be sent first to the MR for further processing (see Fig. 1). Thus, we must make sure that packets destined to a MH can be safely transported from the MR to whichever MAS happens to be currently serving the desired MH. A simple implementation With just these few concepts, a workable im- plementation can be already described. Packets issued by a MH are detected by the MAS's wire- less transceiver and routed onto the wired net- work to their final destination by normal IP rout- ing mechanisms, assuming for now that the desti-
`
`

`

`360 Ch. Perkins / Continuous network access to mobile hosts nation is a traditional IP host. Packets targeted for our MH are routed to the MR for further delivery. Clearly, the MR must know where the MH is currently located, so we must design a method by which the MR can receive location updates each time the MH moves. Next, we re- quire a method by which the packet can be deliv- ered from the MR to the MAS currently serving the MH (two will be mentioned), and code must run within the MAS which allows it to forward the packet along to the MH (i.e., the destination) when the packet is received from the MR. The way in which the packet is delivered from the MR to the MAS deserves special attention, because if its true destination causes normal IP routing to be performed the packet will just arrive back at the MR. The methods of removing the packet delivery from the realm of normal IP routing are described later. In our solution, either the MAS or the MH could deliver location updates to the MR. The MH will always be, by virtue of its IP address, associated with a particular MR; therefore, we assign the MH the responsibility of informing its MR of its new location. This means that in our system the MASs can provide packet forwarding services for MHs on any of several different mo- bile subnets. Of course, part of this process is the determination that a MH has entered a new cell. We call this process "cell discovery", and merely require that one of its results is to notify the network layer within the MH of a wired network address of the MAS. Cell discovery has been the subject of much discussion, and we have catego- rized this process as properly belonging to a link-layer protocol. This makes sense because, after all, entering a cell can be modeled very well as the process of "creating" a link to the MAS, or (equivalently) as allocating some of the channel capacity of the MAS. Various schemes can use registration, security, and/or scheduling algo- rithms as part of the cell discovery process. It is our contention that we cannot cleanly specify a cell-discovery protocol in the abstract at this time, until much more is known and commonly ac- cepted about the nature of wireless "links". Some important characteristics are that they are irregu- larly shaped, possibly overlapping, and offer un- even wireless detection over their area of influ- ence-all of which characteristics are usually quite unimportant for traditional wired links. Most current approaches for enabling mobility specify the existence of some sort of periodic "beacon" emanating from the MAS. Our "link- layer" assumes that the beacon contains the wired IP address of the MAS. This amounts to a route advertisement, and one can hope that eventually such advertisements occur only on demand; peri- odic beacons can have the effect of requiring the MH to continually process packets, possibly negating any carefully designed power saving fea- tures. Once cell discovery has occurred, the MH can select the MAS as its "default" router, and send its outgoing packets to the M_AS, in a natural way. Indeed, we were able to effect cell switches for our MH by typing "route add default < MAS-address > " commands at the user shell prompt on our MH! The "route" command is the command available to the user which adds route table entries for use by the kernel's IP routing mechanisms. To do this automatically requires a server program waiting at a port for the IP ad- dress of a MAS; when one arrives (say, from the MAS's beacon-sending program), the server can issue exactly the same route command and wait for another cell switch. We also programmed our MH server to send the new route data (i.e., the location update) to the MR. In fact, the MR can view its MH-location data as a set of host routes to the MHs it routes packets for. That is, the MR keeps track of exactly this information: if a packet is destined to a MH, that packet must be deliv- ered next to the MAS currently serving the desti- nation MH. Again, the delivery must occur in a way not subject to "normal" IP routing tech- niques. When the MR gets a new location update for a MH, the MR updates its host route for that MH. Consider now the action of the MAS. It is built to transfer packets from its wireless transceiver onto (one of) its wired network(s). It does this just as any IP router would do it. It will also receive (via special mechanisms) packets from the MR destined to one of the MHs in its ceil. A workable system might simply require the MAS to always deliver packets into its cell whenever it gets them (say, from a MR). This system would never allow the MAS to detect the absence of a MH from its cell unless the detection occurred at, say, the link layer. We then modified the MAS operation in two ways. First, the MAS creates a
`
`

`

`Ch. Perkins / Continuous network access to mobile hosts 361 host route to a MH when it receives a (non- broadcast) packet from the MH at its wireless transceiver. Second, we caused the MR to send a "delete host route" message to its previously-re- corded MAS when the MR receives a location update from the MH. Thus, we avoided the need for any interaction between different MASs. In- deed, the MAS exerts very little control over the MHs or the MR in our model. In our system, the MAS and the MR offer their services, and the MH accepts them as needed. Registrations and the like do not enter at all into our operation, and no new protocol is required, except possibly for the essentially private means used to trans- port from the MR to a MAS those packets des- tined for a MH located in the MAS's cell. To deliver the location updates, we used a trivial client/server protocol; the update could instead be delivered to the MR by simply issuing a source-routed ping 11,12 from the MH. Source routing will be reviewed extensively in the next section. We hoped to simplify the operation of the MAS as much as possible, and in particular to eliminate the need for communication between MASs. In this way we hope to enable the con- struction of MAS hardware that is as inexpensive as possible, an important consideration if we are to encourage the widespread deployment of mo- bile computers. First, however, we point out the essential asymmetry in the foregoing simple system. Al- though it works quite well as described for small numbers of networks, it introduces a phe- nomenon called "triangle routing" (Fig. 2). Even though the MH's packets to a traditional host are delivered as well as always by normal IP routing mechanisms, packets to a MH will always be routed through a possibly distant MR, even if the MH and the traditional host are neighbors. Thus, even though our first implementation was satis- factory in our environment, we knew that many customers would prefer much better routing per- ~ ~ Coffespondenl Host I I Mobde Access Station M}H Mobile Host Fig. 2. Mobile networking entities, showing triangle routing. formance. To obtain this performance in an ele- gant way, we made use of IP's "loose source routing" option, and that will be described now. Loose Source Routing (LSR) "Source routing" refers to the options 2,11 within IP which allow packets to carry along with them their own routing information. This under- utilized feature is perfect for our application; we desire that those packets destined for a MH would contain the address of a preferred router --namely the MAS currently serving the MH. The IP addresses of the preferred routers (for us, the MASs) are stored in the IP header along with an offset specifying the next step along the way. When the packet is delivered to one of the inter- mediate routers, that router increments the off- set, effectively exposing the address of the next intermediary router. In addition, the router re- places the IP address by which it was reached with the IP address of the network interface by which it expects to reach the next intermediate router along the way. In this way, a viable route is built up for return packets from the eventual destination. Indeed, the IP source route options specify that any return traffic to the originator of a source routed packet MUST use the specified return route, and that the return packet must also specify the appropriate IP source route op- tion. There are actually two such options: "loose source routing", and "strict source routing". Strict source routing requires that the source route contain every intermediate router; if a router along the way is not directly connected to the next intermediate point, an error indication is returned. Loose source routing (LSR), on the other hand, allows each intermediate router to deliver the packet to the next stop along the way by any available means. This is what we want. After all specified routers in a loose-source-route list are visited, the packet is delivered to its destination by normal IP routing mechanisms. Refer to Fig. 3 for a schematic look at the packet layout for the 1P LSR option. Let's see how an easy modification of our previous design can make use of LSR to elimi- nate almost all "triangle routing". Suppose the MH issues a packet with the LSR option, and the
`
`

`

`362 Ch. Perkins / Continuous network access to mobile hosts 0 8 16 24 Type=31 Length I Offset ~ IP Address of First Intermediate Router IP Address of Second Intermediate Router Fig. 3. IP's Loose Source Route option layout. address of the MAS as the only intermediate router. Then, when the packet is received at its correspondent host (CH), the CH will route the packet back directly to the appropriate MAS without going through the MR. If a CH initiates traffic targeted to the MH, the first packet will go through the MR, but the MH will return packets to the initiator with the LSR option and address of the MAS. So, the CH will send its second packet back directly to the correct cell (i.e., the MAS serving the correct cell). Upon receipt of the CH's first packet, the MR can insert the LSR option along with the address of the MAS cur- rently serving the destination MH. In this way, we are able to remove the packet transmission from MR to MAS out of the realm of normal IP packet forwarding, which was one of our design requirements outlined above; before discovering this use of LSR, we had instead 8 specified that the MR encapsulate packets using the address of the MAS. LSR has solved almost all of our prob- lems, it seems. It even allows optimal traffic be- tween two MHs in different cells. For such dual MH traffic, each packet will contain two MAS addresses as the loose source route, and again standard IP option processing should do the trick, routing the packet from one cell directly to the other. However, it turns out that reality intrudes; LSR sadly can introduce a new set of installation-dependent problems. These will be described later. Our implementation with LSR In this section, we will detail our current im- plementation using Loose Source Routing, and mention problems we have discovered along the way. Our basic equipment is a number of PS/2 model 80s, running AIX version 1.2. Clearly, these systems are far from mobile. However, they are equipped with an infrared wireless adapter and transceiver so we could actually proceed with our mobility experiments, if not conveniently or "real- istically". The infrared adapters have available bandwidth of about 1 MHz, substantially less than common wired network adapters such as Ethernet or Token Ring. Our infrared adapter uses an Ethernet chip for the necessary framing and carrier access functions; we view the infrared medium as a CSMA/CA medium, where we have substituted CA (Collision Avoidance) for CD (Collision Detection) which is commonly used with Ethernet network media. Collision detection is impossible with our infrared adapters, because the transceiver has the light source and detectors only an inch from each other, and the source drowns out any other signal which might be col- liding with it in the cell. The construction of a suitable set of link-layer algorithms is an ongoing process, and no discus- sion of this very interesting problem will be pre- sented here. Suffice it to say that the absence of collision detection presents the protocol designer with a very challenging set of design options, mostly unsatisfactory. Non-CSMA techniques have also been proposed (e.g., 7); each has its own unresolved problems. We hope the tech- niques presented in this paper will be viewed as equally applicable to all the various physical me- dia (e.g., infrared, radio-frequency) as well as the link layer protocols designed for them. For this discussion, the only relevant link-layer algorithm is the beaconing, and we discovered that we could perform beacon transmission and reception nicely enough for our purposes by writing user-level programs to do it--in other words, this link-layer function is performed entirely outside the kernel. In this way we were able to more efficiently experiment with changing parameters and packet layouts without having to recompile our AIX kernel each time. This is a serious benefit when one's kernel build environment is running on older, slower machines. We can best describe our overall system imple- mentation by first outlining the code segments running on MHs, MASs, and MRs. The interac- tions of these three agents has been specified in a draft RFC 14, which represented an offer of our LSR implementation as a draft standard for sup- porting IP mobility. The title of the draft RFC was unfortunately selected before it was realized
`
`

`

`Ch. Perkins / Continuous network access to mobile hosts 363 that Paul Tsuchiya had selected a similar name for an unrelated proposal. No code modifications are necessary on existing hosts, although certain bug fixes (as outlined later) would be advanta- geous for optimal packet routing. Each of our three agents makes updates to their kernel rout- ing tables when needed by accepting "route" commands from user-level servers. Since our sys- tem relies on IP's LSR option, we instituted a new route flag, stored (as are the previous ones) in kernel route-table entries. Our new flag speci- fies that if a route entry is utilized, the outgoing packet should have the LSR option activated (and of course the appropriate router inserted into the option data field). For instance, when the MH utilizes its default route (i.e., through its current MAS) the MH kernel specifies the LSR option because the route command which set up the default route through the MAS also specified that the default route should be marked by the RT - LSR flag. We also created a new flag argu- ment to the route command for just this purpose. Each MAS executes a user-level beacon pro- gram that sends out, once a second, the MAS's wired IP address. The MHs execute a corre- sponding beacon receiving program that waits for the MAS's beacons and decides whether or not to perform a cell switch whenever it receives one. Usually, of course, the beacon has come from the same MAS as it did last time, and the MH does nothing. However, if the MH sees a different MAS address, it then sends a location update to the MR. This location update is sent via the User Datagram Protocol (UDP) 13, because we can not really be sure that any acknowledgment would be returned before another cell switch occurs. However, if an acknowledgment is not received, a timer expires and a new location update is issued. The MH timestamps its location updates to de- fend against out-of-sequence deliveries by the rest of the network. This simple location update algorithm is performed by a separate user level program than the program performing the bea- con reception, although in a real product system both functions would likely be built into the oper- ating-system kernel or the network-protocol de- vice driver. The MR runs only a single user level program, which awaits location updates. When an update is received, if the new MAS differs from any previ- ously reported (and non-null!) MAS, the MR notifies the old MAS that the MH is no longer there. We also built a system in which the MH itself notified the old MAS of its change in loca- tion, but we decided it would be better not to burden the MH with this extra duty since the MR was never busy anyway. The MR also returns an acknowledgment when it processes a MH's loca- tion update; it checks the timestamp each time to make sure that stale but just-delivered updates are not applied to its internal routing tables. In our lab implementation, the MAS's beacon sending program runs in user mode. We also run another user program on the MAS to receive notifications of cell switches from the MR. This user program issues a "route delete" command upon receipt of such a notification, which means that the previous MAS will delete its cell route to the MH and route subsequent packets for the MH back to the MR. We were quite satisfied with the performance of our system, and in addition found it much easier to debug, by putting the cell-discovery and location update functions into programs running outside the kernel. There were also several func- tions that had to be executed within the kernel, dealing with the insertion and deletion of loose source route entries. When a CH sends a non- source-routed packet to a MH, the packet goes to the MR, which then has to deliver it to the MAS (see Fig. 2). As mentioned above, the MR does this by inserting a loose source route with the IP address of the MAS serving the MH's current cell. Such incoming packets can legally contain an existing loose source route, for instance if the originating system was itself a MH. Thus, the MR must insert the MAS's address at the current offset of any existing loose source route. When source-routed packets arrive at a MAS, and the MAS believes that the destination MH is still in its cell, the MAS can just deliver the packet to the MH. It is also possible for the MAS to strip out its loose source route entry before delivering it. This is important when comparing the LSR implementation to any analogous solu- tion using encapsulation. Let's briefly outline the flow of packets corre- sponding to the following different operational scenarios: (1) The MH sends a packet. This is simple. The MH sends it with the LSR option, and the MAS merely routes it onto the wired network, or back
`
`

`

`364 Ch. Perkins / Continuous network access to mobile hosts into its cell in the less common case when the destination is itself a MH in the same cell as the originating MH. (2) A CH answers during an established session with a MH. This is also simple, since the CH has a source route back to the MH and only has to obey standard IP source-route mechanisms. (3) A CH originates a packet to a MH (as opposed to merely answering). In this case, the packet will go to the MR which will insert a MAS's IP address in a loose source route, and forward the packet along using source-route IP mechanisms. Notice that the next packet from the CH to the MH should have the MAS in its source-route option field, by the normal action of the MH. (4) A MH discovers it is in a new cell. First the MH sends a location update to the MR. Then the MR updates its kernel route table, with a host route through the new MAS, specifying our new "LSR" flag in the route entry. Next the MR notifies the old MAS to delete its outdated route for the MH, and sends an acknowledgment to the MH. This describes most of the interesting opera- tional details needed to perform mobile network- ing using LSR. See Fig. 4 for a representative look at some LSR packets as they are issued by various entities in our implementation. It is im- portant to note that Unix kernels actually swap the next router in the loose source route with the IP header destination, until the loose source route is exhausted at which time the real destination IP address is replaced into the header. There are some other less interesting details, such as the need to allow the MH to use a default route to a a) ~-~-- 34 I~CH I DATA... Ib) - 31415~MAS I DATA... CMAS == MAS'sCelllPaddress C) - WMAS ~ MAS's Wired IP addeess 131411 M. I DATA. MH 345 DATA... IP header IP options packet payload dest a) As issued by the MH into a cell b) As relayed by the MAS onto the building network c) As returned by a CH d) As delivered by the MAS into the MH's cell Fig. 4. Loose Source Route packets at various stages of delivery. network (defined by the wired IP address of the MAS) on which the MH's kernel believes it has no operational interfaces. This is more a conse- quence of our particular implementation (i.e., one particular hack) than any basic difficulty. There is currently a proposal under consideration to allow such routes; we certainly support this proposal, having observed no ill effects from it. Other details regarding the operation of ARP will be omitted. However, some more work was needed to overcome the fact that existing imple- mentations of LSR are wrong, as will be de- scribed in the next section. Problems encountered with LSR One of the