`
`
`
`Continuous, transparent network access for portable users
`A Mobile Networking System based on
`Internet Protocol
`
`
`
`CHARLES E. PERKINS, PRAVIN BHAGWAT
`
`existing wired networks. This transceiver is required for wire-
`less communications, and it provides the reference point by
`which the location of the MH is known.
`We have implemented our scheme on a set of IBM PS/2
`Madel 80s running AIX version 1.2. In this article, we present
`an overview of our scheme and provide some details of our
`current implementation. The details providedin this article
`along with [7, 8] can serve as a guide for interested readers who
`wouldlike to add mobile networking featuresto their network
`testbeds.
`
`The Mobility Problem
`T same address space and inter-operate using a commonset
`
`he Internetis a large collection of networks that share the
`
`nthe last twoyears,we havewit-
`nessed two major changes in computer technology.First, portable
`computers as powerful as some desktop workstations in terms
`of computing power, memory, display, and disk storage are
`beginning to appear. Second, with the availahility ofwireless adapter
`cards, users of laptop computers are no longer required to
`remain confined within the wired LAN premises to get net-
`workaccess. Users of portable computers would like to carry
`their laptops with them whenever they move from one place to
`another and yet maintain transparent network access through
`the wireless link. By transparent network access we mean the
`ability of a mobile user to set up and maintain network connec-
`tivity despite migration from one network to another. This
`movement maypossibly introduce a momentary pausein the oper-
`ation, butit should not require reinitialization ofnetwork sessions.
`The existing set of network protocols do not meetthis requirement
`since theywere designed underthe assumption ofa stationarynet-
`ofprotocols, specifically IP and TCP[5,6], but including
`work topology in which hosts do not changetheir location over
`numerousothers.It is desirable that the integration ofmobile com-
`time.
`puters within the existing Internet be completely transparent to
`the transport and higherlayers so that users of mobile comput-
`The probiem of providing continuous network connectivity
`ers can continue to run existing applications. Any acceptable
`to mobile computershas received considerable attention [1-4],
`especially in the context of networks based on the Transmis-
`solution for mobility should interoperate with the existing
`sion Control Protocol/Internet Protocol (TCP/IP) [5, 6] suite
`intrastructure and not require any modifications to existing
`host or router software. However, this goal is not easy to
`of protocols. The proposed solutions either require changes to
`achieve in practice, The way in which the goal may be met
`the existing network architecture [3] or introduce new encapsu-
`lation protocols [1, 4] to handle this problem. In contrast, our
`dependsin large part upon the precise nature of the assump-
`approach, whichis based on the use of a natural model and an
`tions made aboutexisting hosts and protocol implementations.
`An Internet address can be thought ofas consisting oftwoparts,
`existing IP option, does not introduce any new protocol and
`the networkidentifier and the host identifier. All hostsresiding on
`achieves optimal routing [7, 8]. The solution is transparent to
`transport and higher layers, and does not require any changes
`a (sub)net are required to have the same (sub)net address.
`to stationary hosts and routers.
`Within a (sub)net, all attached hosts have a unique host ID.
`Our modelis natural, because we coordinate a collection of
`The routing infrastructure uses the network part of the address
`mobile hosts (MHs) as a new IP network. Aswith any IP net-
`to route the packet to the correct network. Historically, an
`work, we route packets to the MHs by using a router. Our
`Internet address served the purpose of a unique host identifier,
`but the location information wasalso effectively embedded in
`router is special because once it receives a packet, it does spe-
`it. When a host moved to a new network, it would acquire a
`cial things to ensurc its safe delivery to its destination (the
`new address. Since the transport layer and network applica-
`MBH). However, this special operation is invisible to existing
`hosts and routers, so all the routing difference due to move-
`tions assumethat network addresses do not change during the life-
`mentofthe hosts canbe hidden and effected by mechanisms under
`time of a connection, the dynamic assignment of new addresses
`the control of our special entities. The other part of our model,
`cannot be done without affecting them. To provide application
`whichis a very natural part of a physical wircless data commu-
`transparency, it is desirable to devise a method by which hosts
`nications system, ts the transceiver (access point), which col-
`retain their home addresses and continuetu receive packets despite
`their migration from one network to another.
`lects wireless packets froma MHfordelivery to existing hosts along
`
`32
`
`1070-9916/94/$04.00 © 1994 IEEE
`
`JEEE Personal Communications ° First Quarter 1994
`
`Authorizedlicensed uselimited to: Reprints Desk. Downloaded on March 23,2022 at 22:23:31 UTC from IEEE Xplore. Restrictions apply.
`
`4
`
`SAMSUNG 1032
`
`1
`
`SAMSUNG 1032
`
`
`
`The System
`| n this section,we will describe thebasiccnti-
`
`ties in our system and point out why the prob-
`lem solution becomes more natural when the
`model includes the appropriate entities, thus
`making implementation and administration of
`the overall system easier.
`Model Definitions and Assumptions
`Our system involves the participation of three
`types of entities, the MH, mobile access station
`(MAS), and mobile router (MR). The network-
`ing architecture that we assumeis thatof a set of
`MASsconnected through a wired backbone. An
`MASsupportsat least onc wircless interface and
`
`emmmmanmnenensicl ny acceptable solutionfor mobility
`Should interoperate with the existing infrastructure and not
`require any modifications to existing host or router software.
`However, this goal is not easy to achieve in practice.
`
`
`
`by the remote host to send a reply back to the
`source along an optimal path. In the rest of this
`article, we first present an overview of our scheme
`and then describe our implementation.
`
`Overthelast two years several proposals have
`been madeto addressthis problem [1, 3, 4]. The
`scheme proposed byIoannidis [1, 9] relies on a
`group of cooperating mobile support routers
`(MSRs), which advertise reachability to the same
`(sub)net. Each MH, regardless of its location
`within a campus, is always reachable via one of
`the MSRs. Whena host sends a packet to a MH,
`it first gets delivered to the MSRclosest tothe source
`hast. This MSR encapsulates the packet and
`deliversit to the target MSR,whichstrips the encap-
`sulation header and relays the original packet to
`the MH. This approachis optimized to work
`within a campus environment and requires addi-
`tional features before it can be extended to sup-
`port wide-area mobility.
`In Sony’s proposal [3], a MH is assigned a new
`temporary address when it is attached to a new
`network. The mapping between the home address
`and the temporary address of a MI] is kept in an
`address mapping table (AMT),whichis maintained
`at the routers. Packets transmitted to the home
`address of the MH get intercepted by some router
`that holds an AMTentry for the MH. An address
`conversion is performed by the router before the
`packets are forwardedto the physical location ofthe
`MH. This method requires modifications to
`routers and host software and has problems
`interoperating with the existing hosts unless so-
`called conversion gateways are uscd.
`Another proposal to support MHsis from
`Matsushita [4]. This methodis also based on the
`functions as a gateway between the wired and
`wireless sides of the network. Dueto the limited
`encapsulation approach. A MH is assigned a
`temporary address whenit visits a new network.
`range of wireless transceivers, a MH can set upa
`The packets destined to the home addressof the
`dircct link-layer connection with an MASonlywith-
`inalimited geographical region around it. This region
`MH areintercepted by a packet-forwarding serv-
`er (PFS). The PFS encapsulates the packet and
`is referred to as an MAS’s celj. The geographical
`area covered by a cell is a function of the medium
`forwardsit using the temporary address of the
`target MH. The problem with this methodis that
`used for wireless communication. The range of
`infraredcells is typicallylimited to about 20ft, while
`routing is always suboptimal unless the software
`onall stationary hosts is modified.
`that of radio frequency cells could be significantly
`Wehave abstracted out particular functions
`larger.
`necessary for a mobilc nctworking solution and
`Within one campus or administrative domain
`built our system to use just those functions. Iden-
`there could be multiple (sub)networks reserved
`tifying the minimalset of features allowed us to
`for MHs. Each (sub)network has a separate
`work toward a solution with few encumbrances
`router, the MR. Unlike other routers, an MRis
`not required to have an interface corresponding
`stemming from our model. Our model was naturally
`to the wireless (sub)netit serves. Ifan MR hasawire-
`suggested by the idea of segregating the MHs
`into their own distinct network. This new net-
`less interface, it can also function as an MAS,
`The association between an MH andits current MAS
`workis a logical or mobile network, not a net-
`is kept in a location directory (LD) maintained at
`work correspondingto a particular extentof wire.
`the MR.
`Once we decided to use this model, and thus
`agreed to create a router for the mobile network, we
`An MH retainsits address regardless of the
`MAScellitis in. It can start sessions with other hosts
`only needed to design the way packets are deliv-
`ered from the router to the MH. This was done
`(both mobile and stationary) and move into other
`naturally enough by designing the mechanism for
`MAScells without disrupting any active sessions.
`packets to find their way to the current location
`The movementof an MH is completelytrans-
`of the MHasdefined byits connection to its cur-
`parent to the running applications, except pos-
`sibly for a momentary pause that may occur
`rent accesspoint. Since anywireless MH hasto have
`a transceiver to connect up with, we already had
`while the cell switch takes place. An MH can
`teside in the cell of only one MASat any given
`the last necessary functional piece of our model
`and then set about the task of making the neces-
`time. Evenif cells of two MASsspatially overlap,
`an MHroutesits outgoing packcts through only
`sary changes to the network protocol implemen-
`one of them. An MAScan have multiple MHsin
`tation in the access points and the single other agent,
`its cell.
`whichis the router for our new network.
`Ourapproach [7,8] is based on the use of an exist-
`Weuse the term “correspondent host” (CH)
`to refer to the host communicating with an MH.
`ing IP option and therefore does not require any
`In the following discussion, a stationarycorre-
`changesto the existing hosts and routers. The key
`idea is that cach packetoriginating from a MH
`spondenthostis also referred to as a “stationary
`contains enough routing information to be used
`
`host” (SH).
`
`TEFF Personal Communications ° First Quarter 1994
`
`33
`
`Authorized licensed uselimited ta: Reprints Desk. Downloaded on March 23,2022 at 22:23:31 UTC from IEEE Xplore. Restrictions apply.
`
`2
`
`2
`
`
`
`
`
`Figure 1. 4H to SH.
`
`
` a
`
`
`
`Figure 3.MH to MH (same cell).
`
`Implications of Our Model
`
`m Figur
`
`MHsto receive dynamically assigned IP address-
`es,which would eliminate even the last usual require-
`ment for operationwithin an IP network. The means
`by which an IP address is allocated would also
`haveto allow the MH toknow which mobile network
`it is residing on.
`
`As a result of the way in which we have framed
`the problem,solutions occur more naturally with-
`in the visible design space. We basically propose that
`the movement of MHscan be enabled by solving
`a simply stated routing problem. Namely, we can
`achieve our goals by finding a way to route pack-
`ets between the MR and MAS.
`Since the MHsare considered to be on their
`own network, we can provide for ever-larger
`numbers of MHs by adding more mobile net-
`works. When an MR,for capacily reasons, cannot
`route any more packets to the MHsonits net-
`works, a new MRcanbe placedinto service for
`new mobile networks. There doesnothave tobe any
`special relationship betwecn the MRsfor differ-
`ent mobile networks. Likewise, there need not be
`any relationship between the MRsand any MASs.
`As we will indicate, the MAScan deliver packets
`to any MH within its cell regardless of what
`mobile network that host resides on. In fact, in
`our design, the MASsarefairly passive devices,exist-
`ing only to serve whichever MHs comeits way,
`and needing coordination with no other MASsin the
`system or anyother entity. Thus, one can hope
`for an eventual implementation of MASs that
`costs very little in hardware — perhaps looking
`like a smoke detector mounted somewhere within
`a room.
`
`Control Functions
`Aside from the routing functions just mentioned, we
`have some other simply stated functions that are
`required, First, a MH needs to know whenit has
`entered acell. We modelthis process ofcell discovery
`as a client/server interaction, with the MAS
`advertising its service just by announcingits IP
`address for use by the MH. The MHacceptsser-
`vice just by picking out one of the servers (MASs)
`in its area to send packets through.
`Alocation update functionis also needed to allow
`the MR to know where all of its MHs are. We
`mode]this as another simple client/server trans-
`action, this time again with the MH asclient. The
`client contacts its location directory server (con-
`veniently located at the MR) with new updates as
`necessary — that is, whenever the MH decides to
`accept service from another MAS.Thus, the MH
`As aresult of the lack of interdependence between
`is largely in control ofits fate. The MASsinteract
`neither with the MH nor cach other, and do not
`the model entities, our system is very casy to
`provide any handoff services,
`administer. MASs, MRs, and certainly MHs can
`Last, we provide a simplistic method by which
`be added as needed.It is also possible to allow
`
`
`IEEE Personal Communications ° First Quarter 1994
`
`Authorized licensed uselimited ta: Reprints Desk. Downloaded on March 23,2022 at 22:23:31 UTC from IEEE Xplore. Restrictions apply.
`
`3
`
`3
`
`
`
`
`
`
`
`the MASs know which MHs are in their cells.
`This could be done bya link-level interaction, but
`for our purposes it has been sufficient to allow
`the MRto provide location updates to whichever
`MASsare affected whenever an MH moves. If
`this information was not madeavailable, an MAS
`would mistakenly transmit a packetintoits wire-
`less range wheneverit received one, even if the
`desired MH had moved out to a new cell at some
`time in the past. We prefer instead for the MAS
`to forward the packet back to the MRforfurther
`processing.
`Simplest Possible Operation
`Suppose for the momentthat we had a working
`method by which packets could be delivered from
`an MRto the current location (MAS) of an MH.
`Suppose also that the control functions men-
`tioned above were operational. Then,withjust these
`fewelements, we canalready build aworking system
`to allow MHsfree movement between MAScells.
`The problem is that all packets destined for the
`MHs haveto go outof their way, because they
`needto visit the MR before they can be delivered
`to the current MAS. Packets from an MH to an
`existing host (CH) do not experience this prob-
`lem. Thus, this routing phenomenonis called
`“triangle routing,” with the MR, MAS, and CH
`labeling the vertices of the triangle. Thus, if we
`devise a methodfor delivering packets between
`the MR and the current MAS, our remaining
`problem will be to find ways of eliminating this
`triangle routing, which can represent a big loss of
`routing efficiency. It turns out that this is possible
`to do in a fairly elegant way, as long as data pack-
`ets can carry along current routing information
`with them.
`
`Overview of the Scheme
`
`O ur schemeisbasedontheuseofIP’s loose
`
`source route (LSR) option. The LSR
`option provides a means for the source
`host to supply partial routing information to be
`used by routers in forwarding the datagram to
`the destination. A source can specify a list of
`routers to bevisited in the specified sequence before
`the datagramis delivered to the final destination.
`According to the host requirements document
`[10], return traffic to the originator of the LSRed
`packetis also sent with the LSR option by revers-
`ing the route taken by the incoming packets. We
`use this technique to achieve optimal routing
`between an MH and a CH.Thereare four possi-
`ble communication scenarios depending on
`whether the CHis stationary or mobile and,if the
`CH is mobile, whether or not the MH and the
`CHarein the same ccll. We consider each case
`separately and show how optimal routes are con-
`structed in each scenario.
`
`that if the LSR option is not used in the reply
`packets, these packetswill get delivered to the router
`(MR) for the MH’s (sub)network (subsequently
`called the wireless subnet). The MR would even-
`tually forward these packets to the MH; however,
`the complete path followed by thereply packetswould
`not be optimalin this case.
`Stationary Host to Mobile Host
`An SH need not be aware of the current location
`of the MH whenit initiates a session. If it is not
`aware, the packet sent from the SH (are 1, Fig, 2)
`arrives at the MR,which advertizes reachability
`to the wireless subnet. The MR,using the infor-
`mation in its LD,inserts the LSR option inthis pack-
`et, which causes this packet to be delivered to the
`MHvia the current MASserving the MH (arcs 2
`and3, Fig. 2).
`
`semen! ur schemeis based on the use ofIP’s
`loose source route (LSR) option. The LSR option provides
`a meansfor the source host to supply partial routing infor-
`mation to be used by routers in forwarding the datagram to
`the destination.
`
`When areplyto this packetis sent, the MH revers-
`es the LSR and sends the packet back to the SH
`via the MAS(ares 4 and 5, Fig. 2). Once the SIT
`receives a source-routed packet, it can send sub-
`sequent packets to the MH along the optimal
`path by reversing the incoming LSR.
`
`Mobile Host to Mobile Host Within
`the Same Cell
`
`An MHdoes not keep track of other MHsresid-
`ing in the current MAS’scell. It always uses the
`current MASasits default gateway for all outgo-
`ing traffic. When an MH initiates a session with
`another MH,it sends alt packets to the MASjust
`as it would do if it were to send those packets to
`an SH. Since the MAS keepsa list of all MHs
`residing in its cell, it can forward those packets
`to the destination MH. If the wireless link-layer
`technology supports direct MH-to-MH commu-
`nication, the MAScan also send an ICMP[11]
`redirect message to the source MHso thatit can
`directly communicate to the destination MH
`rather than source-routing its traffic through the
`MAS. Figure 3 illustrates MH-to-MH communi-
`cation within the samecell.
`
`Mobile Host to Mobile Host in
`Different Cells
`
`An MH does not inspect the destination IP
`address to determine whetherthe destination host
`is an SH or MH.Consequently, it always starts off
`Mobile Host to Stationary Host
`by sending packets with the LSR option. By normal
`An MH,while communicating with an SH, issues
`routing mechanisms, these packets are forwarded
`to the MR associated with the destination MH
`packets with the LSR option which specifies that
`packets should be routed via the MASserving the
`(ares L and 2, Fig. 4). The MR extends the existing
`LSR option by inserting the address of the the
`MH (arcs 1 and 2, Fig. 1). The SH sends reply
`MAS presently serving the destination MH,and then
`packets with the LSR option containing the
`reversed route. These packetsarefirst delivered
`forwards the packet. Normal! routing procedure
`tothe MAS, which forwards them ta the MH.Notice
`ensures that these packets get delivered to the
`
`
`IEEE Personal Communications © First Quarter 1994
`
`35
`
`Authorized licensed uselimited to: Reprints Desk. Downloaded on March 23,2022 at 22:23:31 UTC from IEEE Xplore. Restrictions apply.
`
`4
`
`4
`
`
`
`
`
`Destination IP Address
`
`Pointer
`
`Address 2
`
`
`
`Address 1
`
`Figure 5. An IP headerwith the LSR option.
`
`MASserving the destination MH,followed by the
`destination MH (arcs 3 and 4,Fig. 4). Notice that the
`LSR optionlist of the incoming packet contains
`the addresses of two MASs, one serving the
`source MH and onethe destination MH. The
`reply packets are sent by reversing the incoming
`LSR, which follows the optimal path (arcs5, 6,
`and 7, Fig. 4). Once the source MH receives a
`packet back from the destination MH,it can also
`send the subsequent packets along the optimalpath.
`
`Implementation
`VVserere ona setofTBM PS/2 Model 80s
`
`e have implemented the aforementioned
`
`running AIX version 1.2. Each of these
`machinesis equipped with an infrared (IR) wire-
`less adapter card supporting a data transfer rate up
`to 1 Mb/s. The range of an IR transceiveris limited
`to about 20 ft. This adapter card uses an Ether-
`net chip. From the perspective of the device driv-
`er, a wireless interface behaves muchlike an Ethernet
`interface, since both use a carrier sense multiple
`access (CSMA)protocol. The only difference is that
`the wireless adapter card does not supportcolli-
`sion detection (CD). This shortcoming, however,
`did not affect us much because most of our exper-
`iments were limited to a small cell population.
`The basicidea of IP’s LSR option is to enable any
`data packet to include routing information so
`that a particular packet would follow a routing
`path possibly different than the path taken by
`normal data packets. This is done by including, in
`IP’s option datafields, the necessary addresses of
`the desired intermediate routers, along with some
`ancillary fields to manage the consumption of the
`routing data (Fig. 5). These fields indicate first,
`the numberof intermediate routing nodes, and
`second, the next desired intermediate router in
`the list. When one of the intermediate nodesis
`reached, the next intermediate routing point is taken
`out of the list and placed in the destination field
`of the IP header; then the intermediate router copies
`the IP address of its own outgoing interface into
`the IP optionsdata, andfinally incrementsthe point-
`er past its own address. This causesthefinal des-
`tination to have a natural reverse path through
`the intermediate routing agents.
`There are actually two different kinds of IP
`source-routing options. We use LSR because
`
`36
`
`we only wantto include the relevant MAS address-
`es in our source routes. The other variety ofIP source
`routing is called “strict source route.” When
`using this option, every intermediate routing
`node mustbe included in the IP option data.
`These two source-routing options are distin-
`guishedby the use of different IP option numbers.
`Our existing implementation consists of
`approximately 800 lines of kernel code and 1500
`lines of user code. It can be thoughtofas consist-
`ing of two parts, the packet routing part and the
`location information managementpart. Actions
`related to packet routing are performed in the
`kerncl. To avoid creating new data structures,
`location information is stored implicitly in the
`kernel routing table. This approach has some
`obvious advantages. First, minimal kernel modifi-
`cations are needed to route packets to/from
`MHs. Secondly, with a little modification, the
`existing route command can be used to manipu-
`late the location information. In the following
`sections, we first describe how packets are routed
`among various components and how location
`information is managed, and then outline the
`processing required at each component.
`Packet Routing
`For each MHthat has an address on the wireless
`(subnet served by an MR,a host route is maintained
`by the MR.The currentlocation information of
`the MH(ie., the address of the MASserving the
`MH) is kept in the gateway field of the routing
`table entry. This routing table entry is distin-
`guished from other entries by the presence of a
`new flag called RTF_MOBIL.F.Since the MR
`advertizes reachability to the range of addresses
`on the mobile (sub)net, an IP packet destined to
`an MHisfirst routed to the MR for further deliv-
`ery. At the MR,one of the host routes with an
`RTF_MOBILEflag is chosen to route this pack-
`et. The MR knows how to interpret
`the
`RTF_MOBILEflag, which specifies that the MR
`should insert the LSR option in this packet (by
`using the MASasthe intermediate hop) before
`forwarding it. Duc to the inserted LSR option,
`this packet is delivered lo the MAScurrently
`serving the destination MH. The LSR option is
`processed here,and, finally, the packet is deliv-
`
`ered to the MH.
`
`WFigure 6. Kernelprocessing at the MH.
`
`IEBEPersonal Communications * First Quarter 1994
`
`Authorized licensed uselimited ta: Reprints Desk. Downloaded on March 23,2022 at 22:23:31 UTC from IEEE Xplore. Restrictions apply.
`
`5
`
`5
`
`
`
`
`
`After an MH has determined thecell to whichit
`belongs,it is required to notify its MR aboutits
`currentlocation. This is accomplished by sending
`an mh2mr message to the MR.
`Unlike cell discovery, which is performed by a
`user-level process, LSR optioninsertion isperformed
`in the MH kernel (Fig. 6). The transport layer
`(TCP or UDP) running at an MH passes packets
`to the IP layer for further delivery. The IP layer
`at the MH is required to modify this packet
`before passing it on to the network interface. If
`the outgoing packet does not contain any LSR,
`then conceptually the MH mustinsert the LSR
`option and specify the MASasthe only intermediate
`routcr. In somecases, the packet passed by the
`transpor! layer already contains the LSR option.
`This option is formed by reversing the route con-
`tained in the LSR option of an incoming packet.
`An existing LSR option in an outgoing packet has
`already been extended by the MR to include the
`local MASas a required intermediate router for
`the source route. This model of operation con-
`
`summmmmmmmsalal ur existing implementation consists of
`approximately 800 lines of kernel code and 1500 lines of
`user code. It can be thought ofas consisting of two parts,
`the packet routing part and the location information man-
`agementpart.
`
`formsto the description given in [12]. However, since
`in most current implementationsall routing is
`done on the basis of the destination address, the
`actual operation is somewhat different (Figs. 7
`and 8). The only routine that needs modification
`is ip_output(). The changes are described below:
`
`}
`
`if ( pkt does nct nave LSR opticn)
`insert LSR option in pkt;
`first address in option list =
`pkt.destination;
`pkt.destination = MAS address;
`} else
`/* option already exists by
`TCP route reversal */
`it ( pkt.destination != MAS address
`pkt .destination = MAS address;
`
`An MASperformsthe forwarding function
`between the wired and the wireless interface.It
`keeps ahost route corresponding to each MHresid-
`ing in its cell. Thus, an IP packet whichis des-
`tined to one of the MHsinits cell is delivered to
`the MH bythe MAS.
`Processing of packets originating from MHsis
`relatively simpler. An MH always keeps a default
`route to the MAScurrently servingit. This rout-
`ing table entry also has the RTF_MOBILEflag
`set, meaning that the LSR option should be used
`onal] outgoing packets. Packets originating from an
`MHare source-routedvia the current MASand deliv-
`ered to the final destination by the normalrout-
`ing mechanism. The reply packets use the reverse
`route and are delivered back to the MH by the
`optimalroute.
`Location Information Propagation
`We now describe how the location information,
`which is implicitly maintained by routing table
`entries at the MR, MAS, and MH, is updated
`when an MHswitchescells.
`A server program (beacon_snd) running on
`the MASperiodically broadcasts beacons on the
`wireless interface. These beacon packets contain
`the IP address of the MAS. An MH,uponenter-
`ing the MAS’scell, receives these beacons and
`sets up the MASas its default router. At the
`sametime, the MH also sends an mh2:r message
`to its MR. This message contains the newloca-
`tion information of the MH and a timestamp. A
`server (mr_serv) running at the MRreceivesthis
`message, uses the location information con-
`tained in it to update its routing table, and noti-
`fies the previous MASserving the MII aboutits
`migration by sendingit a delete_host_route mes-
`sage. The previous MAS, upon receiving this
`message, deletes the host route corresponding to
`the migrated MH.
`All messages are exchanged using User Data-
`gram Protocol (UDP) packets. The message
`exchange protocolis very simple and completely
`implemented by user-level processes running at
`the MH, MR,and MAS.
`
`Processing at the Mobile Host
`The software running on an MHprimarily per-
`forms two functions: cell discovery and insertion
`of the LSR optionin all outgoing IP packets.
`The purposeof the cell discovery operationis
`to send a notification and supply the address of
`the MASto the network layer whenever an MH per-
`forms a cell switch. It is desirable that the cell dis-
`covery feature be supported by thelink layer.
`However, due to lack of such support, a user-
`level process (beac_rev) performsthis operation
`at an MH.It continuously monitors beacon pack-
`cts that are broadcast by MASs, and changesthe
`default route at the MH whenevera cell switch
`occurs.If the cells of two or morc MASsspatially
`overlap, the MH maypotentially receive beacons
`from multiple MASs.Thecell discoverymechanism
`should avoid rapid cell switching by the MH in
`this scenario. In our implementation,if beacons
`Processing at the Mobile Access Station
`from the current MAScontinue to arrive at regu-
`lar intervals, beacons from other MASs are
`The primary function of an MASis to provide an
`ignored. The MH switches to another MAScell
`access point through which an MH,regardless of
`its address, can attach itself to the network. To
`(i.e., changes its default route) if it does not
`forward packets to MHs, an MASshould keep a
`receive any beacon from the current MASfor3 s.
`
`Suppose a packet from a CH arrives at the
`MHandthus has an LSR option. Suppose also
`that before a reply is sent, the MH switches to
`another MAScell. The destination address con-
`tained in the reply packetwill be that of the pre-
`vious MAS. Since the MH hasalready left the
`previous MAScell, it is necessary to modify the
`destination address of this packet to the address
`of the current MAS.After this packet reaches the
`CH,the subsequent packetsoriginating from the
`CH will follow the reverse route and arrive at the
`MHvia the current MAS. Thus, no interruption
`in the active transport-layer session would be
`observed.
`
`TEEFEPersonal Communications ° First Quarter 1994
`
`37
`
`Authorized licensed uselimited ta: Reprints Desk. Downloaded on March 23,2022 at 22:23:31 UTC from IEEE Xplore. Restrictions apply.
`
`6
`
`6
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Wligure 8. LSR reversal by an MH.
`
`host route corresponding ta each MH that resides
`in its cell. The host route is installed by the MAS
`kernel as soon asthefirst packet (c.g., ARP pack-
`et) is received from the MH.Beyondthis point,
`the existing ip_forward() codeis able to forward
`packets to the MH via the wireless interface.
`When an MH moves out of the MAScell, the
`corresponding host routeat the MAS should be delet-
`ed; otherwise, the MAS would continueto trans-
`mit packets to the MH, which no longerexists in
`its cell, As mentioned carlicr, a server process
`(mas_serv) running on the MAS performs the
`deletion of the host route when it receives a
`delete_host_route message from the MR.
`After an MH moves outof the MAScell, the
`packets addressed to it maystill arrive at the
`MAS. These packets could be directly forwarded
`to the MAScurrently serving the migrated MH.
`This, however, would require the MASto main-
`tain forwarding pointersfor all MHs even after
`they migrate outofits cell, thereby unnecessarily
`increasing the protocol complexity and memory
`overhead, We wanted to design a system in which
`there was no need for any information exchange
`among MASs. Therefore, packets that cannot be
`delivered by the MASare returned to the MR
`associated with the destination MH. Note that
`the MAS need not know the address of the MR
`for this purpose. The MASonly forwards this
`packet on to the wired side of the network. The
`normal routing mechanism automatically delivers
`this packet to the MR,since it is the router to the
`MH’s homesubnet.It is necessary to mark these
`returned packets from the MASso that the MR
`can distinguish them from otherpackets. Since there
`is no extra space available in the packet where
`this marking can be incorporated, we