IEN 135                                                      C. Sunshine
                                                               J. Postel
                                                                 USC-ISI
                                                              March 1980

        ADDRESSING MOBILE HOSTS IN THE ARPA INTERNET ENVIRONMENT

INTRODUCTION

The packet radio network system has been designed from the start with
the idea that hosts could be mobile within a packet radio network.  This
is accomplished by allowing a dynamic binding of host names to the
packet radios that are supporting them, and a dynamic construction of
routes to packet radios as the topology of the network changes.  Hosts
in other types of networks may also be mobile to the extent supported by
those local nets, since the local net portion of an internet address is
left to each local net to interpret as it wishes.  (Hosts on the
original ARPANET are not movable in the sense we mean here because the
net interprets the local net address as a physical IMP interface.)

We would also like to allow hosts to move between networks in the
internet system without perturbing protocols above the internet layer.
The particular application we have in mind is a flying packet radio
moving among different packet radio nets, but other types of mobile
hosts may be imagined.

With the current understanding of internet addressing, allowing hosts to
move between nets appears to be a more difficult problem than allowing
mobile hosts within one net.  In particular, the network portion of an
internet address is interpreted as specifying the "real" network in
which the host must be found.  Hence a host moving to a new network
would have to take on a new internet address, causing problems for
higher level protocols (e.g. TCP) that use the internet address for
identifying what conversation or connection a message belongs to.

To solve this problem, we may try to change the higher level protocols   |
(for example by introducing some "reconnection" or multi-addressing      |
functions), or we may try to change the use of the network identifier at |
the internet level.  This note presents one useful looking possibility   |
in the second area.  The problem of supporting mobile hosts is also      |
related to the problems of multi-homed hosts and network partitioning    |
which we shall return to at the end of this note.                        |

PROPOSED SOLUTION

Our solution is based on 1) extending the interpretation of network
addresses to include "virtual" nets, and 2) use of source routing.

We propose to reserve a set of network identifiers in the internet       |
address space for "virtual" networks which do not correspond to any      |
physical network, but rather to a "community of interest" in which       |



Sunshine & Postel                                               [Page 1]


IEN 135                                                       March 1980
Addressing Mobile Hosts



"local" names can be uniquely assigned.  In particular, there would be   |
one network identifier for airborne packet radios (e.g. ABPR).  The      |
local portion of the internet address for each airborne packet radio     |
would be a unique (for airborne packet radios) 24-bit number.            |

Rather than interpreting the network address in the usual fashion for    |
internet routing, delivery of messages to airborne hosts would require   |
the use of a two-part source route in the following way.  The first part |
would be a normal internet address of a "forwarder," hopefully within    |
the net that the airborne host is currently attached to.  When the       |
message reached this forwarder, it would see the airborne virtual net    |
address in the final part of the source route.  This would cause it to   |
look up in a dynamically maintained table of attached mobile hosts what  |
the proper local address and/or route was to the specified mobile host,  |
and to forward the message accordingly.  Gateways would NOT include      |
virtual nets in the normal internet routing tables, or be able to route  |
packets to such nets directly (unless they were also forwarders).        |

The first feature to note about this scheme is that the ultimate
destination address is a new virtual type internet address that remains
unchanged no matter what net the host is attached to.  This allows
higher level protocols to remain unchanged in their mapping of addresses
to connections.

The second feature to note is that this freedom for higher level
protocols has its price at the internet level.  We now require 1) the
use of source routing, 2) the maintenance of local address mappings by
forwarders, and 3) the determination of an appropriate forwarder for a
given mobile host.  The second item is exactly the sort of work
currently done by the station in a packet radio net, and we expect this
could be extended to deal with internet format addresses rather easily.
If not the station itself, then the gateway to a packet radio net might
perform this function.

The third item seems to require some form of dynamic global data base
that maintains the location of mobile hosts.  When queried with a mobile
host name, it returns the internet address of an appropriate forwarder
to use in constructing a source route to the mobile host.  Of course
this information must be updated as hosts move.  This database may be
centralized, or include several backup servers, or even be distributed
(e.g. among the gateways and/or forwarders which comprise a single
virtual server much like the PSATs in the WBC net).

When a host enters a new net (or comes up), it must notify the forwarder |
in that net of its existence (PRs now make a similar notification when   |
the come up in a PR net).  Either the forwarder or the host must also    |



Sunshine & Postel                                               [Page 2]


IEN 135                                                       March 1980
Addressing Mobile Hosts



notify the global database.  For greater efficiency, the source of any   |
existing connections and the forwarder in the old net could also be      |
notified.  Without these extra notifications, the old forwarder could    |
only notify the source that the host was no longer accessible through    |
his local net, and the source would in turn have to query the global     |
database for the new forwarder address.  This scheme should also work if |
hosts on both sides of a conversation are mobile and move                |
simultaneously, although their change notices to each other may not get  |
delivered, forcing them both to requery the database.                    |

ROUTING MESSAGES

This proposal requires a new kind of routing message carrying the name
of a mobile host and the current forwarder (or forwarders) to use to
reach it.  Such a message could serve either as a query (empty route
portion); as an update to the global database, forwarders, and internet
hosts; as a response to explicit queries to the database; or as an ACK
to a current update (by repeating it).

Such a message fits conveniently within the current "gateway-gateway"
protocol defined in IEN 109 [1].  There is already a similar type
message in this protocol called "Redirect Message."  We propose adding a
new message type called "Mobile Routing" as follows:

      Type: 11 (decimal) for Mobile Routing

       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      | Gateway Type  |   Operation   |  Route Count  |    unused     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    Mobile Internet Address                    |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                  Forwarder Internet Address                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      /                                                               /
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                  Forwarder Internet Address                   |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |       Internet Header + 64 bits of Original Data Packet       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

         Gateway Type: 11

         Operation: 0 = Query
                    1 = Update
                    2 = Route Change Advisory



Sunshine & Postel                                               [Page 3]


IEN 135                                                       March 1980
Addressing Mobile Hosts



                    3 = Acknowledge
                    4 = Query Response

         Route Count: number of forwarder internet addresses included

         Mobile Internet Address: 32 bit internet address, typically
         ABPR.xyz

         Forwarder Internet Address: 32 bit internet address

         Reference: present only for Op = 2 (route change advisory).
                    Internet Header plus 64 bits of data from
                    datagram causing this reply.

      Query messages will have a zero route count.

      Updates are used to update the global database or forwarder tables
      when a host moves to a new net.

      Route Change Advisories are sent by a forwarder (or a mobile
      destination) in response to the arrival of an internet datagram
      that cannot (or soon will not be able to) be routed that way
      anymore.  They include 64 bits of what is assumed to be the port
      information from the higher level protocol in case the source
      needs this to lookup the correct connection.

      Acknowledge datagrams are the responses to Updates so that the
      sender of the Update knows it has been correctly received.  They
      should repeat all the information in the original Update, simply
      changing the OP from 1 to 3.

      Query Response is the answer to the Query datagram.

It is quite possible that a simple generalization of this message type
could support general source route lookup from a routing database, but
it is not our intention to pursue this avenue at this time.

The procedures for handling mobile hosts may also make use of the
existing "Host Unreachable" message type.  Packets reaching an incorrect
forwarder that cannot supply a new route to a mobile host (using the
Route Change Advisory above) must return a simple Host Unreachable
message, causing the source to query the global database.  If the reply
to this query is the same forwarder, then the mobile host is truly
unreachable.  The source may wish to wait a short time and requery the
database on the hope that the mobile host is in process of moving to a
new net.



Sunshine & Postel                                               [Page 4]


IEN 135                                                       March 1980
Addressing Mobile Hosts



RELATION TO OTHER PROBLEMS

As stated in the introduction, there is some relation between the        |
problems of mobile hosts and of dual-homed (on two networks) hosts.  In  |
particular, one could consider dual-homed hosts as mobile, and go        |
through the same route lookup and source routing procedures in           |
communicating with them.  The dual-homed host itself could act as a      |
degenerate sort of forwarder, receiving messages on either of its        |
interface addresses, and "forwarding" them internally to its virtual net |
address.  Presumably updates to the routing database would be made only  |
when an interface  went down or up.  Dual-homed hosts would enjoy the    |
same benefits of no changes to higher level protocols while messages     |
could arrive over either interface.  However, the extra cost of route    |
lookup, source routing, and assignment of a nework number, may not be    |
justified for normal operation, and higher level procedures should still |
be considered in this area.                                              |

There is also some relation to the network partition problem as follows.
When a network partitions, we can treat the partitions as subnetworks,
and the original host addresses as virtual network addresses where we
don't know what (sub)network the host is located in.  Some dynamic
mapping of host address to correct subnet must be performed, as in the
mobile host case.  However, this situation requires the dynamic creation
and deletion of new (sub)networks in the routing database, and hence
goes beyond what we have proposed for mobile hosts.  We do not believe
it is desirable to try and extend our proposal to cover this situation
as well.

A simpler solution to the partitioning problem follows the spirit of
querying a database when things go wrong.  Suppose there were another
database listing networks and all the gateways attached to each net
(whether up or down).  This database would change slowly only as new
equipment was added to the internet system.  Further suppose that the
gateways and internet routing are totally unaware of network partitions,
except that gateways to partitioned nets find out when they cannot reach
some host on their own net.  In this case, the gateway would return a
Host Unreachable (through me) advisory message to the source.  The
source could then query the global database to get a list of all
gateways to the destination net, and construct explicit source routes to
the destination going through each of these gateways, trying each one in
turn until it succeeded.  The only difficulty in this scheme is that
gateways should distinguish between hosts completely unreachable (so no
rerouting will work) and those in a different partition.

This scheme assumes that there are few gateways to most nets (e.g. 2-4)
and that partitions are a relatively rare event so that simple-minded



Sunshine & Postel                                               [Page 5]


IEN 135                                                       March 1980
Addressing Mobile Hosts



polling is an adequate mechanism.  Compared to the approach suggested in
IEN 120 [2], it requires some simple additional work at the source ONLY
when partitions occur, but frees the gateways of all concern about
partitions.  Given that partitions are a rare event, we think that a
high level of effort by the gateways to make partitions "invisible" to
the sources (even when no partitions exist) is not justified.  Both the
scheme proposed here and the one in IEN 120 operate solely within the
internet routing level and have no effect on higher level protocols.

SUMMARY

We have proposed a mechanism for allowing hosts to move between networks
in the ARPA internet system without requiring any changes to protocols
above the internet level.  The mechanism involves
   1) the definition of a "virtual" net for mobile hosts,
   2) the use of "forwarders" in each local net that can support
      mobile hosts (much like the stations in packet radio nets), and
   3) the use and maintenance of a global database giving the current
      network location of mobile hosts.

We believe these three items are feasible with a modest amount of work
because
   1) is essentially an administrative matter,
   2) is essentially already performed by stations on packet radio
      nets, and
   3) is similar to the name server function already implemented
      experimentally.

We have also proposed a simple scheme for handling network partitioning
based on trying explicit source routes to each gateway to the
destination net when normal internet routing fails.

This proposal should be considered simply as outlining a promising
approach.  Before elaborating further details, we would like your help
in evaluating the overall ideas.  Comments to the authors are highly
desired.

REFERENCES

[1]  Strazisar, V., "How To Build a Gateway", IEN 109, Bolt Beranek and
     Newman Inc., August 1979.

[2]  Perlman, R., "Internet Routing and the Network Partition Problem",
     IEN 120, Bolt Beranek and Newman Inc., October 1979.





Sunshine & Postel                                               [Page 6]