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]
mirror server hosted at Truenetwork, Russian Federation.