IEN 178                                                April 1981
     
     
     
     
     
     
     
               ADDRESSING PROBLEMS IN MULTI-NETWORK SYSTEMS
     
                             Carl A. Sunshine
     
                     University of Southern California
                      Information Sciences Institute
                            4676 Admiralty Way
                         Marina del Rey, CA 90291
     
     
     
     
     
     
     
     Abstract
     
             To allow uers in different  networks  to communicate with
        each other,  development  of powerful  yet  practical  naming,
        addressing,   and  routing  facilities  is  essential.   Basic
        procedures for multi-network systems under control of a single
        organization  have begun  to be used,  but a large set of more
        sophisticated  goals  remain  to  be  addressed.   This  paper
        describes  several  of these more advanced  problems including
        extendability,   multihoming,   network  partitioning,  mobile
        hosts, shared access, local site connections, gateway routing,
        and overcoming differences in heterogeneous systems.
     
     
     
     
     
     
     
     
     
     
     Note:
     
             There are three figures  associated  with  this  document
        which  may be obtained from the author by sending a message to
        <SUNSHINE@ISIF>.

                               -1-
     
     
     Introduction
     
             The interconnection  of multiple  computer networks makes
     
        it possible  for ever wider communities  of computer users and
     
        applications  to interact  with each other.   A basic  set  of
     
        problems   that  must  be   solved   in   accomplishing   such
     
        interconnections  concerns  providing  naming, addressing, and
     
        routing   procedures  that  are  general  and  convenient  yet
     
        practical.   These problems  are particularly  difficult  when
     
        networks of different designs and/or operating under different
     
        authorities must be interconnected.
     
             Current  multi-network  systems are fairly small (tens of
     
        networks maximum) and largely designed by and under control of
     
        a single  organization.   (We shall  call  this  "homogeneous"
     
        internetworking.)    Basic  interconnection  is  supported  by
     
        simple hierarchical addressing and routing procedures employed
     
        uniformly throughout the system [1,4,10,13].  Interconnections
     
        of    different     multi-network    systems    (heterogeneous
     
        internetworking)  are just beginning to be made, largely by ad
     
        hoc means.
     
             Thus,  while some of the basic problems have been solved,
     
        a large set of secondary problems will soon be upon us.  These
     
        include problems of scale (current methods are impractical for
     
        systems  with hundreds  or thousands  of networks); supporting
     
        more sophisticated  functions  such  as  multihoming,  network

                               -2-
     
     
        partitioning,  mobile hosts, and shared access; and overcoming
     
        the different procedures in heterogeneous systems.
     
             This  paper  describes   several   of  these  interesting
     
        problems,  and discusses potential solutions.  The emphasis is
     
        on developing  a feel for the range of problems  and solutions
     
        rather  than on  detailed  or  formal  treatment  of  any  one
     
        problem.  In many cases it will be clear that further research
     
        is needed  to clarify  the problems or to develop and evaluate
     
        better solutions.
     
     
     Hierarchical Methods
     
             A basic approach  to  addressing  and  routing  in  large
     
        systems  is to use hierarchical methods.  These methods can be
     
        applied  at various  levels  (e.g.,  within networks and among
     
        networks).   We give a brief summary  of the basic  principles
     
        involved since these form the background for many of the other
     
        problems.
     
             As the number  of subscribers  or  "hosts"  in  a  single
     
        network  increases, it becomes desirable to introduce a number
     
        of switches,  each serving  a  subset  of  the  hosts.   These
     
        switches  must maintain  routing  tables  which give the  best
     
        outgoing  link (or set of links)  for  any  destination.   The
     
        tables  are used to forward  incoming  packets properly toward
     
        their destination.   In datagram  networks, a routing decision
     
        based on final destination  is made for every packet, while in
     
        virtual  circuit  nets only the initial  call  request  packet

                               -3-
     
     
        requires  the full routing  decision  (subsequent packets of a
     
        call are forwarded over fixed routes kept in other tables).
     
             If every switch  maintained routing information for every
     
        destination individually, the routing tables would become very
     
        large.   A standard  approach  is  to  introduce  hierarchical
     
        addressing, where each host is assigned a particular port on a
     
        particular  switch, and hence addresses take the form <switch,
     
        port>.   Then routing  may  also  be  done  hierarchically  by
     
        sending  all packets  destined to a given switch over the same
     
        route, ignoring the "low order" portion of the address.  Hence
     
        each switch  need only  maintain  routes  to  other  switches,
     
        greatly  reducing  the number  of different  destinations, and
     
        hence entries, in the routing tables.
     
             Note that hierarchical  routing  is one major  motivation
     
        for  introducing   hierarchical   addresses,   but  these  two
     
        techniques  do not necessarily  go together  as we  shall  see
     
        below.  Another reason for hierarchical addresses is simply to
     
        distribute  the authority  for assigning  addresses  within  a
     
        large system [14].
     
             The same techniques  may  be  extended  to  multi-network
     
        systems by adding another level to the addressing hierarchy so
     
        that addresses  take  the  form  <net,  switch,  port>.   With
     
        hierarchical   routing,   packets  are  first  routed  to  the
     
        destination  network,  ignoring the rest of their address, and
     
        then routed  within  the final network as above.  This form of

                               -4-
     
     
        hierarchical  addressing has been adopted by the public packet
     
        switching  networks  in CCITT  Recommendation  X.121,  and  it
     
        appears  that most public  networks intend to use hierarchical
     
        routing as well [13,19].
     
             The reduction  of routing  table  size  that  accompanies
     
        hierarchical  routing has its price.  The resulting routes may
     
        not always  be optimal.   If there  are two ways  to  reach  a
     
        remote  network  (as is often the case), one may be better for
     
        some hosts within  that network and the other for other hosts.
     
        But there  is by design  no way to determine this from a local
     
        routing  table which carries  a single  entry for  the  entire
     
        remote  network.   An even more serious  consequence of strict
     
        hierarchical routing is discussed in the next section.
     
             To avoid these problems,  routing  decisions may based on
     
        more of the address  where desirable  [5,14].  For example, an
     
        internetwork routing table could be augmented with entries for
     
        individual   switches  receiving  high  traffic  in  a  remote
     
        network,  while other switches in that network were covered by
     
        a single  network  level entry.   This leads  to  a  selective
     
        increase  in the size of  routing  tables,  and  requires  the
     
        ability  to search  the tables for variable length portions of
     
        addresses and to update tables with varying levels of detail.
     
     
     Network Partitions
     
             A network  is said to be partitioned  when  enough  links
     
        and/or  switches fail so that two or more subsets of its hosts

                               -5-
     
     
        are formed  which cannot  communicate  with each other.  In an
     
        isolated  network  there is no remedy for this situation until
     
        sufficient  repairs  are made to restore connectivity.  But if
     
        the partitioned  net is part of a multi-network  system, there
     
        may be paths  through  other  nets  which  could  connect  the
     
        partitions.   Unfortunately,  these paths are not used  within
     
        the strictly  hierarchical routing procedures described above.
     
        And even if a  "local"  packet  were  sent  to  a  neighboring
     
        network by a switch, it would likely be routed right back into
     
        the same paritition by the other network.
     
             This last point indicates another difficulty.  Traffic in
     
        a remote  network  destined  for the partitioned  net will  be
     
        routed  into one or the other partition  without consideration
     
        of its within-network  switch.   (Remember that other networks
     
        see a single  best route  to  this  network  considered  as  a
     
        whole.)   For  some  destinations,  this  will  be  the  wrong
     
        partition  and the destination will be unreachable by internal
     
        routes,  leading to failure to deliver packets routed that way
     
        from remote nets [14,16].
     
             One solution  to this problem  is to configure the system
     
        with sufficient  robustness that partitions occur very rarely,
     
        and to simply  tolerate  the above delivery problems when they
     
        occur.   This may be satisfactory for commercial systems where
     
        loads and outages are fairly predictable.
     
             In  military   systems  where  numerous  disruptions  are

                               -6-
     
     
        anticipated,  some means  of  forcing  use  of  any  available
     
        connectivity  is desirable  [3].  One approach is to treat the
     
        number  of networks as dynamic, and turn a partitioned network
     
        into  two  networks,   each  of  which   can  be  an  explicit
     
        destination.  This requires rather complex methods of updating
     
        each network's  view of the overall  topology, and promulgates
     
        knowledge  of a partition in one network to all other networks
     
        [8].   Another  approach  might be to return  a special  error
     
        message to the neighboring router forcing it to choose another
     
        entry    point    to     the     failed     network.      This
     
        backup-and-try-alternate  method has been implemented for call
     
        setup in Telenet [19].
     
     
     "Fast Track" Routing
     
             It is not  only  in  case  of  catastrophic  events  like
     
        partitioning  that use of external  routes  between two points
     
        within  the same region  may be desirable.   If  two  networks
     
        cover   the   same   geographical    area,   for   example   a
     
        store-and-forward  ground  net and a broadcast  satellite net,
     
        performance  for some types of  traffic  may  be  improved  by
     
        exiting  the ground  net near the source,  going  through  the
     
        satellite  net,  and returning  to the  ground  net  near  the
     
        destination.    File  transfer  traffic  might  obtain  higher
     
        throughput in this fashion, for example.
     
             To accomplish this, it is once again necessary to violate
     
        hierarchical  routing.   Either the network level routing must

                               -7-
     
     
        distinguish  between destinations best reached directly within
     
        the network  and those  best reached  by going outside, or the
     
        within-network  level must be made to view paths through other
     
        networks  as a special kind of internal link that is available
     
        [9].   But in the latter  case,  the network level path status
     
        information  must be brought  into the  internal  link  status
     
        maintenance procedures, probably a messy business.
     
     
     Multihoming
     
             A subscriber  may want to have multiple  connections to a
     
        communication  system  for reliability or performance reasons.
     
        In the simplest  case,  several independent physical lines may
     
        be  managed  as  one  logical  data  link  to  obtain  greater
     
        reliability,  higher  throughput,  or lower cost (due  to  the
     
        idiosyncracies  of carrier  tariffs).   Several such multiline
     
        procedures  have been developed,  for example in Transpac, and
     
        in X.75.   The subscriber  still  has a single address, and no
     
        further complications are involved.
     
             In order to protect against node failures as well as line
     
        failures,  lines to different  switches must be used.  In this
     
        case the user has two  (or  more)  different  addresses.   The
     
        multiple  addresses  may  be  at  any  level  in  the  address
     
        hierarchy:  (e.g. two addresses within a network, or connected
     
        to two different  nets).   Multiple  lines  may  also  provide
     
        better performance by connecting directly to highly used areas

                               -8-
     
     
        of the  system  and  thus  avoiding  extra  hops  through  the
     
        network.
     
             In order  to obtain  these  benefits,  the ability to use
     
        both addresses  and to select  the optimal address must exist.
     
        This may be accomplished  by the source  explicitly  selecting
     
        one address.   But this requires the source to know that there
     
        are multiple  addresses for a given destination, to select the
     
        best address  for performance,  and to switch  to an alternate
     
        after a failure.   These admittedly  weighty  burdens could be
     
        aided by a remote directory/routing service.
     
             Alternatively,   the  packet  could  carry  the  multiple
     
        addresses explicitly, allowing each switch to pick the best of
     
        the best routes  for each address.   This of  course  adds  to
     
        packet length and routing processing load.
     
             Instead  of carrying  the multiple  addresses, the packet
     
        might carry the name (or "logical address") of the destination
     
        [14],  leaving  it for the switches  to lookup  and select the
     
        best  address   at  each  point.   This  would  reduce  packet
     
        complexity,  but increase  the switch  processing demands even
     
        further.
     
             Thus we have a spectrum  from high source  effort to high
     
        network  effort  in making  use  of  multiple  addresses.   In
     
        datagram  nets it is probably  impractical  to require complex
     
        processing  of the address  on every packet,  so  more  source
     
        effort  will probably  be required.  In virtual circuit nets a

                               -9-
     
     
        greater  amount  of effort  can be expended  by the net on the
     
        call setup request.   Some public  nets are already  providing
     
        call forwarding  facilities where a call to one inoperative or
     
        busy address  will automatically  be forwarded to an alternate
     
        address.
     
             There  are problems  at the destination  as well  as  the
     
        source.    To  obtain   the  benefits   of  multihoming,   the
     
        destination   must  be  willing   to  accept  traffic  on  all
     
        addresses.   In virtual  circuit  nets,  all the traffic for a
     
        given  call must flow over the same line,  so a failure during
     
        the call cannot  be recovered  by using an alternate  address.
     
        The call must be cleared with possible loss of data, and a new
     
        one requested.
     
             Even in some datagram  nets,  higher  level protocols are
     
        sensitive  to the addresses of the local and remote hosts [3].
     
        The source  address is used to demultiplex incoming packets to
     
        the proper  "connection," and packets coming from an alternate
     
        address  from that used to establish  the connection would not
     
        be recognized  properly.   To avoid this problem, the (single)
     
        name of the source could be used in the connection tables, but
     
        this would have to be carried  in the packet.   Alternatively,
     
        the multiple  remote  addresses could be stored as part of the
     
        connection table so that a packet specifying any one as source
     
        would match properly.   These multiple addresses would have to
     
        be supplied as part of the connection establishment, and might

                              -10-
     
     
        be profitably  used in sending traffic if the original address
     
        failed.
     
     
     Mobile Hosts
     
             Mobile  hosts represent  a special  case of the  multiple
     
        address  problem.   Of course all hosts are technically mobile
     
        in the sense that they occasionally  change  their address due
     
        to reconfiguration  and movement within the user organization,
     
        or modifications  to the network  topology.   Hence  directory
     
        information  to associate  the name of a host with its current
     
        address  is available  in most systems,  either locally or via
     
        some remote server.
     
             However,   the  problem  of  changing  addresses  becomes
     
        qualitatively  different  when the host is expected  to change
     
        its network  attachment point frequently, even in the midst of
     
        previously  established  connections.  Special dynamic routing
     
        and addressing procedures have been developed for ground based
     
        mobile  hosts communicating  via packet  radio within a single
     
        network  [6].   As distances are increased and this technology
     
        is transferred  to airplanes,  crossing network boundaries may
     
        also be anticipated.
     
             One method  for  "tracking"  mobile  hosts  would  be  to
     
        maintain  a specialized  database  of their current  locations
     
        (perhaps  replicated  for  reliability),  as  is  done  within
     
        individual  packet  radio nets (by the "station").  The mobile
     
        hosts would send updates to this database as needed, and users

                              -11-
     
     
        wishing  to establish  communication  could query the database
     
        much as any other directory  service.  However, they should be
     
        prepared  to receive  frequent address change notifications in
     
        the course  of a  connection,  either  from  the  mobile  host
     
        itself,  alternate  relay points,  or the  database.   Further
     
        details of such a scheme may be found in [18].
     
             Assuming traffic reaches them, destinations must still be
     
        "desensitized" from the particular source address as discussed
     
        above,  since  this will change.  But there is no fixed set of
     
        alternates  to exchange at connection setup time in this case,
     
        so packets  probably  must carry a unique identifier (name) of
     
        the source  as well as its current  address.   For reliability
     
        purposes,  they should  probably  also carry the name  of  the
     
        destination  in case it  is  no  longer  associated  with  the
     
        address they reach.
     
             Mobile hosts may have multiple addresses at one moment as
     
        well as at different  times  (e.g.,  an  aircraft  may  be  in
     
        contact  with two radio nets).   Thus it becomes apparent that
     
        problems  can interact  with each other, making solutions more
     
        difficult.
     
     
     Sharing Network Access
     
             The opposite  problem  to one host having  several access
     
        lines  to the net is several  hosts  sharing  a single  access
     
        line.   This may be desirable  where the number  of  physiscal
     
        interfaces  or ports  to the network is limited, or to share a

                              -12-
     
     
        long access  line among nearby  subscribers.   Public networks
     
        provide  multidrop interfaces for terminal traffic (X.28), but
     
        not for packet mode traffic (X.25).  For packet level devices,
     
        the alternative  to providing  a fixed and  hence  inefficient
     
        frequency  or time division  multiplexor  must be some sort of
     
        "intelligent"  multiplexor  functioning at the packet level of
     
        network access protocols.
     
             Broadcast   networks  (e.g.,  Ethernets  and  ring  nets)
     
        inherently provide this capability since every interface hears
     
        all traffic.   Each interface  is  responsible  for  accepting
     
        appropriate  traffic,  and can sometimes  be set to  intercept
     
        traffic for multiple addresses.
     
             Another  approach is to use a higher level of protocol to
     
        provide  the necessary  demultiplexing.   The  Arpanet  access
     
        (Host-IMP)  protocol does not allow for shared interfaces, and
     
        the limitation  of 4 host interfaces  on the original IMPs has
     
        proved  troublesome in some cases.  The Internet Protocol (IP)
     
        is the next level above particular network access protocols in
     
        the ARPA hierarchy  [10,11].   IP addresses  are  sufficiently
     
        long to support  multiple "logical" hosts at the same physical
     
        host port on the Arpanet.   The Host-IMP  header indicates the
     
        same physical  host address  for all  such  packets,  and  the
     
        higher  level IP module  at the destination  demultiplexes the
     
        packets to the correct logical host.  An independent device to
     
        perform  this function  has  been developed based on PDP-11/03

                              -13-
     
     
        hardware.   This "port expander"  effectively  turns each  IMP
     
        port into 4-8 ports for hosts that use the  Internet  Protocol
     
        [7].
     
     
     Networks vs. Gateways as Switches
     
             In most models  of  hierarchical  routing,  networks  are
     
        assumed  to function  as "super-switches,"  just as  switching
     
        nodes do within  one network.   This view would  be  literally
     
        true if there  were a single  internet  switching node in each
     
        net to which all incoming  traffic from other nets was routed,
     
        and which then forwarded  the traffic to another network or to
     
        a  local   host.    Figure  X  shows  a  small  example  of  a
     
        multi-network    system   and   a   routing   table   at   one
     
        network/switch.   The routing table gives the cost in internet
     
        hops and the best neighbor  net to use  to  reach  each  other
     
        network in the system.
     
             For  efficiency,  this  internet  switching  function  is
     
        usually  distributed  to processors  called "gateways" serving
     
        each of the internet links.  Instead of being sent through the
     
        net to some central  point, the internet traffic can be routed
     
        immediately  at its entry point to the best exit point (either
     
        another  gateway or the destination host).  Figure Y shows the
     
        same internet  system  with  internet  links  labeled,  and  a
     
        routing  table at the gateway  located  on one incoming  link.
     
        Since  the gateway  must send packets  across  its  net  to  a

                              -14-
     
     
        particular outgoing link, the routing table now shows the name
     
        of this next link rather than the next net.
     
             Another  step in  this  progression  leads  to  a  single
     
        gateway  located  in the "middle" of each internet link rather
     
        than two separate  processors  in each net.  The gateways take
     
        on  the  identity   of  their  internet   link(s).    In  this
     
        configuration,  it is more realistic to count the network hops
     
        as the cost fucntion  rather  than the internet  links.  Hence
     
        each gateway  is maintaining  a  distance  (in  network  hops)
     
        between  gateways,  and a best next gateway  to use  for  each
     
        destination.    In  this  model,  the  gateways  may  be  more
     
        realistically  viewed as the switching nodes, and the networks
     
        as the links connecting them.  This is essentially the dual of
     
        the earlier  model as shown in Figure Z.  But the destinations
     
        in the routing table are networks, not gateways, making this a
     
        curious  sort of hybrid  scheme.  Hence it is not clear how to
     
        apply the "link state"  type of  routing  procedures  used  in
     
        single  networks  (e.g.,  the Arpanet)  to this  multi-network
     
        configuration with gateways as switching nodes.
     
     
     Local Site Connections
     
             Many sites  start  with a  single  host  connected  to  a
     
        long-haul  net.   As the site develops,  a few more hosts  are
     
        connected,  also directly  to the long-haul  switch.   As even
     
        more hosts  want to join the net at that site, problems result
     
        from costly  or inefficient  use of network access procedures.

                              -15-
     
     
        Some sort of port expander  or intelligent multiplexor devices
     
        as discussed above become attractive.
     
             This addresses  the network  connection  problem, but not
     
        the local traffic requirements which are also growing, and may
     
        easily  exceed traffic to remote sites.  The network switch is
     
        handling  a lot of traffic that never goes any further through
     
        the net.   In some cases  the port expanders may be capable of
     
        local switching, forming a rudimentary local net.
     
             To handle  local traffic  more efficiently,  an  explicit
     
        local  net may be desirable.   A question  then arises  as  to
     
        whether this net should be "known" to the rest of the internet
     
        system,  and connected  to it via  one  or  more  full-fledged
     
        gateways,  or whether it should be "invisible" at the internet
     
        level with its  hosts  appearing  as  if  they  were  directly
     
        connected  to the long-haul  net.   In the first  case,  local
     
        hosts have internet  addresses on an explicit local net, while
     
        in the second they have addresses on the long-haul net.
     
             The explicit  local net approach  has certain  advantages
     
        stemming  from the explicit  identification  of the  group  of
     
        hosts  at a site as a network.  If the site is connectected to
     
        two or more other nets,  then the internet  routing mechansims
     
        will automatically  choose  the best path to the local  hosts,
     
        which have only a single address (on their local net).
     
             However,  this participation  at the internet  level  can
     
        also be a problem.   As the number  of sites  with local  nets

                              -16-
     
     
        increases,  so will the number  of nets and hence  the size of
     
        the routing  tables  and updates  which must be propagated all
     
        over the internet  system.   If the growth continues at a site
     
        so that there are several  local  nets  connected  by  "local"
     
        gateways,  should  all of these nets and the local topology be
     
        known throughout  the internet system?  At some point treating
     
        local  nets on a par with long-haul  or backbone  nets  breaks
     
        down.
     
             The invisible  local net approach,  on  the  other  hand,
     
        avoids  problems  of proliferating  networks  at the  internet
     
        level.   Many port expander  or local distribution systems can
     
        perform   an  internal   switching   function,  relieving  the
     
        long-haul  net switch  of handling  local traffic.   But sites
     
        with connections  to two  or  more  nets  will  have  multiple
     
        addresses  for their hosts (one for each net the hosts  appear
     
        "directly" connected to), and this causes some difficulties as
     
        discussed above under Multihoming.
     
             The best solution  to this tradeoff is not clear.  Adding
     
        an additional  level to the  addressing  hierarchy  may  be  a
     
        temporary solution, but it, too, will become strained in time.
     
        This suggests  allowing  a variable  number  of levels  in the
     
        addressing   hierarchy,   adding   new  levels  as  complexity
     
        increases  in some area.  But this imposes a rigid ordering of
     
        levels  and hence  routing,  while  in  reality  "higher"  and
     
        "lower"  may depend  on the viewpoint  of the  user.   Further

                              -17-
     
     
        research  is needed on how internet systems may grow and still
     
        maintain efficient addressing and routing procedures.
     
     
     Multiple Domains
     
             Most of the previous  discussion  has  assumed  a  single
     
        compatible  "domain"  in which network  addressing and routing
     
        procedures  are carried  out uniformly.   In the real world we
     
        have already  seen the growth  of several  large domains  with
     
        different    conventions,    including    public,    mainframe
     
        manufacturer,  Defense  Department, and local networks.  It is
     
        unrealistic  and perhaps  impossible that these diverse groups
     
        will ever adopt  a single  addressing  scheme, so we must live
     
        with the problem  of  multiple  domains  for  the  foreseeable
     
        future.
     
             One approach  is to assume  that one domain will make use
     
        of  another   merely  as  transport  medium  between  its  own
     
        homogeneous components.  The used system appears merely as one
     
        of several types of media that the using system can employ via
     
        appropriate access protocols.  The using system's packets will
     
        be "encapsulated"  in the used system's  protocols.  Of course
     
        the  two  domains  can  make  use  of  each  other,  achieving
     
        coexistence,   if  not  complete  interoperation,  by  "mutual
     
        encapsulation" [15].
     
             To achieve  full interoperability  between  heterogeneous
     
        systems,  each system  must recognize  the hosts on the other.

                              -18-
     
     
        Two basic choices are possible for crossing domain boundaries:
     
        mapping and source routing.
     
             In the mapping  approach,  each domain  provides a set of
     
        otherwise   unused   internal   addresses  which  it  maps  to
     
        particular  addresses  in other domains.  Traffic addressed to
     
        one of these "pseudo-addresses"  is routed  to an interface or
     
        gateway  to the appropriate  other domain,  at which point the
     
        pseudo-address  is converted  into an  address  in  the  other
     
        domain.   In the simplest  case,  this requires only bilateral
     
        agreements between domains, but it may also be extended across
     
        intermediaries with further collaboration.
     
             A disadvantage  of this approach  is that the  number  of
     
        external  addresses  available  is limited  to those for which
     
        mappings   have  been  previously   defined   and   installed.
     
        Typically   only  a  small  fraction  of  remote  parties  are
     
        supported.   Another  disadvantage  is that the same party has
     
        different  addresses  in different  domains--the  directory of
     
        names  to addresses  has many entries  for each name,  one for
     
        each domain  supporting  that party.   The major advantage  is
     
        that for those names supported,  the users may address  remote
     
        parties  in exactly  the same fashion  as local  ones, with no
     
        additional procedures.
     
             In source routing [14,17,5], the source specifies a route
     
        to reach  the  destination  consisting  of  the  addresses  of
     
        successive  inter-domain  gateways,  and ending with the final

                              -19-
     
     
        destination.   Each address in this list is interpreted within
     
        a domain  where it is meaningful, and then removed so that the
     
        next address is available in the next domain transitted.
     
             Using this method,  the full range of remote  parties  is
     
        accessable,  and the inter-domain  gateways  do  not  have  to
     
        maintain   any  predefined   mappings   or   perform   address
     
        conversions.   The burden  is shifted to the source which must
     
        know enough  about the overall topology and address formats to
     
        construct a successful source route.  Of course packet headers
     
        become  bigger,  and packet processing increases to accomodate
     
        the variable  length source routes.  Once again, the "address"
     
        of a given  party varies from one domain to another, but it is
     
        now possible  to combine  this information--if  the  directory
     
        gives  the source  route  to X from  domain  A,  and a user in
     
        domain B knows a route to domain A, he can concatenate them to
     
        get a route  to X from  B (although  it may not be an  optimal
     
        route).
     
             It is often  useful to collect a return route at the same
     
        time the source  route is being  consumed.   This  allows  the
     
        destination  to reply.   In general  the return  route is  not
     
        simply  the inverse of the source route.  The return addresses
     
        are  added  as  the  packet  enters  each  domain,  while  the
     
        successive  destination  addresses  are removed  as the packet
     
        exits each domain (see [17] for a detailed example).
     
             The  "network   independent"   transport   protocol   [2]

                              -20-
     
     
        developed  by the British  PSS Users Forum is one of the first
     
        to explicitly deal with the problem of multiple domains.  They
     
        suggest  essentially  a source  routing  mechanism.  There are
     
        additional  provisions  for translating  explicitly identified
     
        address  information  transmitted  as data between  end users.
     
        The protocol  assumes  a route setup procedure as part of call
     
        establishment so that the source route need only be carried in
     
        the call request packet.
     
             The public networks have also provided for a limited form
     
        of source  routing  in the Call User Data field  of X.25  call
     
        request  packets.   This field may be used by the  destination
     
        DTE as additional  address information for subsequent steps in
     
        a call.   This mechanism was used to allow international calls
     
        between   Canadian   and  US  public   networks   before   the
     
        hierarchical  X.121 numbering  plan was put into effect  [12].
     
        The Call User Data field is also beginning to be used in an ad
     
        hoc fashion  to  provide  addressing  within  various  private
     
        and/or local nets connected to public nets.
     
             The Arpa Internet Protocol also supports a source routing
     
        option,  but addresses within the route are all expected to be
     
        IP format addresses [11].
     
     
     Conclusions
     
             We have identified  a number  of problems  that  must  be
     
        considered  in going beyond  the simple network interconection
     
        techniques  that are in use today.   The significance of these

                              -21-
     
     
        problems  is just beginning  to  be  widely  percieved.   Some
     
        preliminary solutions have been proposed, but little practical
     
        experience exists.  Much work remains to be done in clarifying
     
        the problems, and in developing and evaluating solutions.
     
     
     Acknowledgements
     
             Many of the concepts  presented  in this paper have  been
     
        discussed  over several  years as part of  the  ARPA  Internet
     
        project.   Much of the credit  for developing  and  clarifying
     
        these  ideas  belongs  to my colleagues  at ISI and the  other
     
        sites engaged in this project.
     
     
     References
     
        Note:  Several  of the references  listed  below are  Internet
        Experiment  Notes,  unpublished  memos written  for  the  ARPA
        Internet project.
     
        [1]  D. R. Boggs, J. F. Shoch, E. A. Taft, and R. M. Metcalfe,
             "Pup:  An  Internetwork  Architecture,"  IEEE  Trans.  on
             Communications 28, 4, April 1980, pp. 612-623.
     
        [2]  British Post Office PSS User Forum, A Network Independent
             Transport Service, February 1980.
     
        [3]  V.  G. Cerf, Internet Addressing and Naming in a Tactical
             Environment, Internet Experiment Note 110, August 1979.
     
        [4]  V.  G. Cerf and P. T. Kirstein, "Issues in Packet-Network
             Interconnection,"  Proc.  IEEE 66, 11, November 1978, pp.
             1386-1408.
     
        [5]  D.  D.  Clark and D. Cohen, A Proposal for Addressing and
             Routing  in the Internet,  Internet  Experiment  Note 46,
             June 1978.
     
        [6]  R.  E.  Kahn,  S.  A. Gronemeyer, J. Burchfiel, and R. C.
             Kunzelman,  "Advances  in Packet Radio Technology," Proc.
             IEEE 66, 11, November 1978, pp. 1468-1496.

                              -22-
     
     
        [7]  H.  A.  Nelson, J. E. Mathis, and J. M. Lieb, The ARPANET
             IMP Port Expander, SRI Report 1080-140-1, November 1980.
     
        [8]  R.  Perlman, Flying Packet Radios and Network Partitions,
             Internet Experiment Note 146, June 1980.
     
        [9]  R.  Perlman,  Utilizing  Internet  Routes  as Expressways
             Through  Slow Nets,  Internet  Experiment  Note 147, June
             1980.
     
        [10] J.  B.  Postel,  "Internetwork Protocol Approaches," IEEE
             Trans. on Communications 28, 4, April 1980, pp. 604-611.
     
        [11] J.  B.  Postel,  C.  A. Sunshine, and D. Cohen, "The ARPA
             Internet Protocol," to appear in Computer Networks, 1981.
     
        [12] A.  M.  Rybczynski,  D.  F.  Weir,  and I. M. Cunningham,
             "Datapac  Internetworking  for  International  Services,"
             Proc. 4th Int. Conf. on Computer Communication, September
             1978, pp. 47-56.
     
        [13] A. M. Rybczinski, J. D. Palframan, and A. Thomas, "Design
             of the Datapac  X.75 Internetworking  Capability,"  Proc.
             5th Int.  Conf.  on Computer Communication, October 1980,
             pp. 735-740.
     
        [14] J.  F.  Shoch,  "Inter-Network  Naming,  Addressing,  and
             Routing,"  Proc.  17th IEEE Computer  Society Int. Conf.,
             September 1978, pp. 72-79.
     
        [15]  J.   F.  Shoch,  D.  Cohen,  and  E.  A.  Taft,  "Mutual
             Encapsulation  of Internetwork  Protocols,"  to appear in
             Computer Networks, 1981.
     
        [16] C.  A.  Sunshine, "Interconnection of Computer Networks,"
             Computer Networks 1, 3, January 1977, pp. 175-195.
     
        [17] C.  A.  Sunshine,  "Source Routing in Computer Networks,"
             ACM SIGCOMM  Computer  Communication  Rev.  7, 1, January
             1977, pp. 29-33.
     
        [18] C.  A. Sunshine and J. B. Postel, Addressing Mobile Hosts
             in the ARPA  Internet  Environment,  Internet  Experiment
             Note 135, March 1980.
     
        [19] D.  F. Weir, J. B. Holmblad, and A. C. Rothberg, "An X.75
             Based Network  Architecture,"  Proc.  5th Int.  Conf.  on
             Computer Communication, October 1980, pp. 741-750.