home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / rfc / 900s / rfc917.txt < prev    next >
Text File  |  1992-09-21  |  47KB  |  1,255 lines
  1.  
  2.  
  3. Network Working Group                                      Jeffrey Mogul
  4. Request for Comments: 917                    Computer Science Department
  5.                                                      Stanford University
  6.                                                             October 1984
  7.  
  8.                             INTERNET SUBNETS
  9.  
  10.  
  11. Status Of This Memo
  12.  
  13.    This RFC suggests a proposed protocol for the ARPA-Internet
  14.    community, and requests discussion and suggestions for improvements.
  15.    Distribution of this memo is unlimited.
  16.  
  17. Overview
  18.  
  19.    We discuss the utility of "subnets" of Internet networks, which are
  20.    logically visible sub-sections of a single Internet network.  For
  21.    administrative or technical reasons, many organizations have chosen
  22.    to divide one Internet network into several subnets, instead of
  23.    acquiring a set of Internet network numbers.
  24.  
  25.    We propose procedures for the use of subnets, and discuss approaches
  26.    to solving the problems that arise, particularly that of routing.
  27.  
  28. Acknowledgment
  29.  
  30.    This proposal is the result of discussion with several other people.
  31.    J. Noel Chiappa, Chris Kent, and Tim Mann, in particular, provided
  32.    important suggestions.
  33.  
  34. 1. Introduction
  35.  
  36.    The original view of the Internet universe was a two-level hierarchy:
  37.    the top level the catenet as a whole, and the level below it a
  38.    collection of "Internet Networks", each with its own Network Number.
  39.    (We do not mean that the Internet has a hierarchical topology, but
  40.    that the interpretation of addresses is hierarchical.)
  41.  
  42.    While this view has proved simple and powerful, a number of
  43.    organizations have found it inadequate and have added a third level
  44.    to the interpretation of Internet addresses.  In this view, a given
  45.    Internet Network might (or might not) be divided into a collection of
  46.    subnets.
  47.  
  48.    The original, two-level, view carries a strong presumption that, to a
  49.    host on an Internet network, that network may be viewed as a single
  50.    edge; to put it another way, the network may be treated as a "black
  51.    box" to which a set of hosts is connected.  This is true of the
  52.  
  53.  
  54.  
  55.  
  56. Mogul                                                           [Page 1]
  57.  
  58.  
  59.  
  60. RFC 917                                                     October 1984
  61. Internet Subnets
  62.  
  63.  
  64.    ARPANET, because the IMPs mask the use of specific links in that
  65.    network.  It is also true of most local area network (LAN)
  66.    technologies, such as Ethernet or ring networks.
  67.  
  68.    However, this presumption fails in many practical cases, because in
  69.    moderately large organizations (e.g., Universities or companies with
  70.    more than one building) it is often necessary to use more than one
  71.    LAN cable to cover a "local area".  For example, at this writing
  72.    there are eighteen such cables in use at Stanford University, with
  73.    more planned.
  74.  
  75.    There are several reasons why an organization might use more than one
  76.    cable to cover a campus:
  77.  
  78.       - Different technologies: Especially in a research environment,
  79.         there may be more than one kind of LAN in use; e.g., an
  80.         organization may have some equipment that supports Ethernet, and
  81.         some that supports a ring network.
  82.  
  83.       - Limits of technologies: Most LAN technologies impose limits,
  84.         based electrical parameters, on the number of hosts connected,
  85.         and on the total length of the cable.  It is easy to exceed
  86.         these limits, especially those on cable length.
  87.  
  88.       - Network congestion: It is possible for a small subset of the
  89.         hosts on a LAN to monopolize most of the bandwidth.  A common
  90.         solution to this problem is to divide the hosts into cliques of
  91.         high mutual communication, and put these cliques on separate
  92.         cables.
  93.  
  94.       - Point-to-Point links: Sometimes a "local area", such as a
  95.         university campus, is split into two locations too far apart to
  96.         connect using the preferred LAN technology.  In this case,
  97.         high-speed point-to-point links might connect several LANs.
  98.  
  99.    An organization that has been forced to use more than one LAN has
  100.    three choices for assigning Internet addresses:
  101.  
  102.       1. Acquire a distinct Internet network number for each cable.
  103.  
  104.       2. Use a single network number for the entire organization, but
  105.          assign host numbers without regard to which LAN a host is on.
  106.          (We will call this choice "transparent subnets".)
  107.  
  108.       3. Use a single network number, and partition the host address
  109.          space by assigning subnet numbers to the LANs. ("Explicit
  110.          subnets".)
  111.  
  112.  
  113. Mogul                                                           [Page 2]
  114.  
  115.  
  116.  
  117. RFC 917                                                     October 1984
  118. Internet Subnets
  119.  
  120.  
  121.    Each of these approaches has disadvantages.  The first, although not
  122.    requiring any new or modified protocols, does result in an explosion
  123.    in the size of Internet routing tables.  Information about the
  124.    internal details of local connectivity is propagated everywhere,
  125.    although it is of little or no use outside the local organization.
  126.    Especially as some current gateway implementations do not have much
  127.    space for routing tables, it would be nice to avoid this problem.
  128.  
  129.    The second approach requires some convention or protocol that makes
  130.    the collection of LANs appear to be a single Internet network.  For
  131.    example, this can be done on LANs where each Internet address is
  132.    translated to a hardware address using an Address Resolution Protocol
  133.    (ARP), by having the bridges between the LANs intercept ARP requests
  134.    for non-local targets.  However, it is not possible to do this for
  135.    all LAN technologies, especially those where ARP protocols are not
  136.    currently used, or if the LAN does not support broadcasts.  A more
  137.    fundamental problem is that bridges must discover which LAN a host is
  138.    on, perhaps by using a broadcast algorithm.  As the number of LANs
  139.    grows, the cost of broadcasting grows as well; also, the size of
  140.    translation caches required in the bridges grows with the total
  141.    number of hosts in the network.
  142.  
  143.    The third approach addresses the key problem: existing standards
  144.    assume that all hosts on an Internet local network are on a single
  145.    cable.  The solution is to explicitly support subnets.  This does
  146.    have a disadvantage, in that it is a modification of the Internet
  147.    Protocol, and thus requires changes to IP implementations already in
  148.    use (if these implementations are to be used on a subnetted network.)
  149.    However, we believe that these changes are relatively minor, and once
  150.    made, yield a simple and efficient solution to the problem.  Also,
  151.    the approach we take in this document is to avoid any changes that
  152.    would be incompatible with existing hosts on non-subnetted networks.
  153.  
  154.    Further, when appropriate design choices are made, it is possible for
  155.    hosts which believe they are on a non-subnetted network to be used on
  156.    a subnetted one, as will be explained later.  This is useful when it
  157.    is not possible to modify some of the hosts to support subnets
  158.    explicitly, or when a gradual transition is preferred.  Because of
  159.    this, there seems little reason to use the second approach listed
  160.    above.
  161.  
  162.    The rest of this document describes approaches to subnets of Internet
  163.    Networks.
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170. Mogul                                                           [Page 3]
  171.  
  172.  
  173.  
  174. RFC 917                                                     October 1984
  175. Internet Subnets
  176.  
  177.  
  178.    1.1. Terminology
  179.  
  180.       To avoid either ambiguity or prolixity, we will define a few
  181.       terms, which will be used in the following sections:
  182.  
  183.       Catenet
  184.  
  185.          The collection of connected Internet Networks
  186.  
  187.       Network
  188.  
  189.          A single Internet network (that may or may not be divided into
  190.          subnets.)
  191.  
  192.       Subnet
  193.  
  194.          A subnet of an Internet network.
  195.  
  196.       Network Number
  197.  
  198.          As in [8].
  199.  
  200.       Local Address
  201.  
  202.          The bits in an Internet address not used for the network
  203.          number; also known as "rest field".
  204.  
  205.       Subnet Number
  206.  
  207.          A number identifying a subnet within a network.
  208.  
  209.       Subnet Field
  210.  
  211.          The bit field in an Internet address used for the subnet
  212.          number.
  213.  
  214.       Host Field
  215.  
  216.          The bit field in an Internet address used for denoting a
  217.          specific host.
  218.  
  219.       Gateway
  220.  
  221.          A node connected to two or more administratively distinct
  222.          networks and/or subnets, to which hosts send datagrams to be
  223.          forwarded.
  224.  
  225.  
  226.  
  227. Mogul                                                           [Page 4]
  228.  
  229.  
  230.  
  231. RFC 917                                                     October 1984
  232. Internet Subnets
  233.  
  234.  
  235.       Bridge
  236.  
  237.          A node connected to two or more administratively
  238.          indistinguishable but physically distinct subnets, that
  239.          automatically forwards datagrams when necessary, but whose
  240.          existence is not know to other hosts.  Also called a "software
  241.          repeater".
  242.  
  243. 2. Standards for Subnet Addressing
  244.  
  245.    Following the division presented in [2], we observe that subnets are
  246.    fundamentally an issue of addressing.  In this section, we first
  247.    describe a proposal for interpretation of Internet Addressing to
  248.    support subnets.  We then discuss the interaction between this
  249.    address format and broadcasting; finally, we present a protocol for
  250.    discovering what address interpretation is in use on a given network.
  251.  
  252.    2.1. Interpretation of Internet Addresses
  253.  
  254.       Suppose that an organization has been assigned an Internet network
  255.       number, has further divided that network into a set of subnets,
  256.       and wants to assign host addresses: how should this be done?
  257.       Since there are minimal restrictions on the assignment of the
  258.       "local address" part of the Internet address, several approaches
  259.       have been proposed for representing the subnet number:
  260.  
  261.          1. Variable-width field: Any number of the bits of the local
  262.             address part are used for the subnet number; the size of
  263.             this field, although constant for a given network, varies
  264.             from network to network.  If the field width is zero, then
  265.             subnets are not in use.
  266.  
  267.          2. Fixed-width field: A specific number of bits (e.g., eight)
  268.             is used for the subnet number, if subnets are in use.
  269.  
  270.          3. Self-encoding variable-width field: Just as the width (i.e.,
  271.             class) of the network number field is encoded by its
  272.             high-order bits, the width of the subnet field is similarly
  273.             encoded.
  274.  
  275.          4. Self-encoding fixed-width field: A specific number of bits
  276.             is is used for the subnet number.  Subnets are in use if the
  277.             high-order bit of this field is one; otherwise, the entire
  278.             local address part is used for host number.
  279.  
  280.       Since there seems to be no advantage in doing otherwise, all these
  281.       schemes place the subnet field as the most significant field in
  282.  
  283.  
  284. Mogul                                                           [Page 5]
  285.  
  286.  
  287.  
  288. RFC 917                                                     October 1984
  289. Internet Subnets
  290.  
  291.  
  292.       the local address part.  Also, since the local address part of a
  293.       Class C address is so small, there is little reason to support
  294.       subnets of other than Class A and Class B networks.
  295.  
  296.       What criteria can we use to choose one of these four schemes?
  297.       First, do we want to use a self-encoding scheme; that is, should
  298.       it be possible to tell from examining an Internet address if it
  299.       refers to a subnetted network, without reference to any other
  300.       information?
  301.  
  302.       One advantage to self-encoding is that it allows one to determine
  303.       if a non-local network has been divided into subnets.  It is not
  304.       clear that this would be of any use.  The principle advantage,
  305.       however, is that no additional information is needed for an
  306.       implementation to determine if two addresses are on the same
  307.       subnet.  However, this can also be viewed as a disadvantage: it
  308.       may cause problems for non-subnetted networks which have existing
  309.       host numbers that use arbitrary bits in the local address part
  310.       <1>.  In other words, it is useful to be able control whether a
  311.       network is subnetted independently from the assignment of host
  312.       addresses.  Another disadvantage of any self-encoding scheme is
  313.       that it reduces the local address space by at least a factor of
  314.       two.
  315.  
  316.       If a self-encoding scheme is not used, it is clear that a
  317.       variable-width subnet field is appropriate.  Since there must in
  318.       any case be some per-network "flag" to indicate if subnets are in
  319.       use, the additional cost of using an integer (the subnet field
  320.       width) instead of a boolean is negligible.  The advantage of using
  321.       a variable-width subnet field is that it allows each organization
  322.       to choose the best way to allocate relatively scarce bits of local
  323.       address to subnet and host numbers.
  324.  
  325.       Our proposal, therefore, is that the Internet address be
  326.       interpreted as:
  327.  
  328.          <network-number><subnet-number><host-number>
  329.  
  330.       where the <network-number> field is as in [8], the <host-number>
  331.       field is at least one bit wide, and the width of the
  332.       <subnet-number> field is constant for a given network. No further
  333.       structure is required for the <subnet-number> or <host-number>
  334.       fields.  If the width of the <subnet-number> field is zero, then
  335.       the network is not subnetted (i.e., the interpretation of [8] is
  336.       used.)
  337.  
  338.  
  339.  
  340.  
  341. Mogul                                                           [Page 6]
  342.  
  343.  
  344.  
  345. RFC 917                                                     October 1984
  346. Internet Subnets
  347.  
  348.  
  349.       For example, on a Class A network with an eight bit wide subnet
  350.       field, an address is broken down like this:
  351.  
  352.                            1                   2                   3
  353.        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
  354.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  355.       |0|    NETWORK    |     SUBNET    |         Host number         |
  356.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  357.  
  358.       We expect that, for reasons of simplicity and efficient
  359.       implementation, that most organizations will choose a subnet field
  360.       width that is a multiple of eight bits.  However, an
  361.       implementation must be prepared to handle other possible widths.
  362.  
  363.       We reject the use of "recursive subnets", the division of the host
  364.       field into "sub-subnet" and host parts, because:
  365.  
  366.          - There is no obvious need for a four-level hierarchy.
  367.  
  368.          - The number of bits available in an IP address is not large
  369.            enough to make this useful in general.
  370.  
  371.          - The extra mechanism required is complex.
  372.  
  373.    2.2. Changes to Host Software to Support Subnets
  374.  
  375.       In most implementations of IP, there is  code in the module that
  376.       handles outgoing packet that does something like:
  377.  
  378.          IF ip_net_number(packet.ip_dest) = ip_net_number(my_ip_addr)
  379.              THEN
  380.                  send_packet_locally(packet, packet.ip_dest)
  381.              ELSE
  382.                  send_packet_locally(packet,
  383.                     gateway_to(ip_net_number(packet.ip_dest)))
  384.  
  385.       (If the code supports multiple connected networks, it will be more
  386.       complicated, but this is irrelevant to the current discussion.)
  387.  
  388.       To support subnets, it is necessary to store one more 32-bit
  389.       quantity, called my_ip_mask.  This is a bit-mask with bits set in
  390.       the fields corresponding to the IP network number, and additional
  391.       bits set corresponding to the subnet number field.  For example,
  392.       on a Class A network using an eight-bit wide subnet field, the
  393.       mask would be 255.255.0.0.
  394.  
  395.       The code then becomes:
  396.  
  397.  
  398. Mogul                                                           [Page 7]
  399.  
  400.  
  401.  
  402. RFC 917                                                     October 1984
  403. Internet Subnets
  404.  
  405.  
  406.          IF bitwise_and(packet.ip_dest, my_ip_mask)
  407.                           = bitwise_and(my_ip_addr, my_ip_mask)
  408.              THEN
  409.                  send_packet_locally(packet, packet.ip_dest)
  410.              ELSE
  411.                  send_packet_locally(packet,
  412.                     gateway_to(bitwise_and(packet.ip_dest, my_ip_mask)))
  413.  
  414.       Of course, part of the expression in the conditionally can be
  415.       pre-computed.
  416.  
  417.       It may or may not be necessary to modify the "gateway_to"
  418.       function, so that it performs comparisons in the same way.
  419.  
  420.       To support multiply-connected hosts, the code can be changed to
  421.       keep  the "my_ip_addr" and "my_ip_mask" quantities on a
  422.       per-interface basis; the expression in the conditional must then
  423.       be evaluated for each interface.
  424.  
  425.    2.3. Subnets and Broadcasting
  426.  
  427.       In the absence of subnets, there are only two kinds of broadcast
  428.       possible within the Internet Protocol <2>: broadcast to all hosts
  429.       on a specific network, or broadcast to all hosts on "this
  430.       network"; the latter is useful when a host does not know what
  431.       network it is on.
  432.  
  433.       When subnets are used, the situation becomes slightly more
  434.       complicated.  First, the possibility now exists of broadcasting to
  435.       a specific subnet.  Second, broadcasting to all the hosts on a
  436.       subnetted network requires additional mechanism; in [6] the use of
  437.       "Reverse Path Forwarding" [3] is proposed.  Finally, the
  438.       interpretation of a broadcast to "this network" is that it should
  439.       not be forwarded outside of the original subnet.
  440.  
  441.       Implementations must therefore recognize three kinds of broadcast
  442.       addresses, in addition to their own host addresses:
  443.  
  444.       This physical network
  445.  
  446.          A destination address of all ones (255.255.255.255) causes the
  447.          a datagram to be sent as a broadcast on the local physical
  448.          network; it must not be forwarded by any gateway.
  449.  
  450.  
  451.  
  452.  
  453.  
  454.  
  455. Mogul                                                           [Page 8]
  456.  
  457.  
  458.  
  459. RFC 917                                                     October 1984
  460. Internet Subnets
  461.  
  462.  
  463.       Specific network
  464.  
  465.          The destination address contains a valid network number; the
  466.          local address part is all ones (e.g., 36.255.255.255).
  467.  
  468.       Specific subnet
  469.  
  470.          The destination address contains a valid network number and a
  471.          valid subnet number; the host field is all ones (e.g.,
  472.          36.40.255.255).
  473.  
  474.       For further discussion of Internet broadcasting, see [6].
  475.  
  476.       One factor that may aid in deciding whether to use subnets is that
  477.       it is possible to broadcast to all hosts of a subnetted network
  478.       with a single operation at the originating host.  It is not
  479.       possible to broadcast, in one step, to the same set of hosts if
  480.       they are on distinct networks.
  481.  
  482.    2.4. Determining the Width of the Subnet Field
  483.  
  484.       How can a host (or gateway) determine what subnet field width is
  485.       in use on a network to which it is connected?  The problem is
  486.       analogous to several other "bootstrapping" problems for Internet
  487.       hosts: how a host determines its own address, and how it locates a
  488.       gateway on its local network.  In all three cases, there are two
  489.       basic solutions: "hardwired" information, and broadcast-based
  490.       protocols.
  491.  
  492.       "Hardwired" information is that available to a host in isolation
  493.       from a network.  It may be compiled-in, or (preferably) stored in
  494.       a disk file.  However, for the increasingly common case of a
  495.       diskless workstation that is bootloaded over a LAN, neither
  496.       hard-wired solution is satisfactory.  Instead, since most LAN
  497.       technology supports broadcasting, a better method is for the
  498.       newly-booted host to broadcast a request for the necessary
  499.       information.  For example, for the purpose of determining its
  500.       Internet address, a host may use the "Reverse Address Resolution
  501.       Protocol" [4].
  502.  
  503.       We propose to extend the ICMP protocol [9] by adding a new pair of
  504.       ICMP message types, "Address Format Request" and "Address Format
  505.       Reply", analogous to the "Information Request" and "Information
  506.       Reply" ICMP messages.  These are described in detail in
  507.       Appendix I.
  508.  
  509.       The intended use of these new ICMPs is that a host, when booting,
  510.  
  511.  
  512. Mogul                                                           [Page 9]
  513.  
  514.  
  515.  
  516. RFC 917                                                     October 1984
  517. Internet Subnets
  518.  
  519.  
  520.       broadcast an "Address Format Request" message <3>.  A gateway (or
  521.       a host acting in lieu of a gateway) that receives this message
  522.       responds with an "Address Format Reply".  If there is no
  523.       indication in the request which host sent it (i.e., the IP Source
  524.       Address is zero), the reply is broadcast as well.  The requesting
  525.       host will hear the response, and from it determine the width of
  526.       the subnet field.
  527.  
  528.       Since there is only one possible value that can be sent in an
  529.       "Address Format Reply" on any given LAN, there is no need for the
  530.       requesting host to match the responses it hears against the
  531.       request it sent; similarly, there is no problem if more than one
  532.       gateway responds.  We assume that hosts reboot infrequently, so
  533.       the broadcast load on a network from use of this protocol should
  534.       be small.
  535.  
  536.       If a host is connected to more than one LAN, it must use this
  537.       protocol on each, unless it can determine (from a response on one
  538.       of the LANs) that several of the LANs are part of the same
  539.       network, and thus must have the same subnet field width.
  540.  
  541.       One potential problem is what a host should do if it receives no
  542.       response to its "Address Format Request", even after a reasonable
  543.       number of tries.  Three interpretations can be placed on the
  544.       situation:
  545.  
  546.          1. The local net exists in (permanent) isolation from all other
  547.             nets.
  548.  
  549.          2. Subnets are not in use, and no host supports this ICMP
  550.             request.
  551.  
  552.          3. All gateways on the local net are (temporarily) down.
  553.  
  554.       The first and second situations imply that the subnet field width
  555.       is zero.  In the third situation, there is no way to determine
  556.       what the proper value is; the safest choice is thus zero.
  557.       Although this might later turn out to be wrong, it will not
  558.       prevent transmissions that would otherwise succeed.  It is
  559.       possible for a host to recover from a wrong choice: when a gateway
  560.       comes up, it should broadcast an "Address Format Reply"; when a
  561.       host receives such a message that disagrees with its guess, it
  562.       should adjust its data structures to conform to the received
  563.       value.  No host or gateway should send an "Address Format Reply"
  564.       based on a "guessed" value.
  565.  
  566.  
  567.  
  568.  
  569. Mogul                                                          [Page 10]
  570.  
  571.  
  572.  
  573. RFC 917                                                     October 1984
  574. Internet Subnets
  575.  
  576.  
  577.       Finally, note that no host is required to use this ICMP protocol
  578.       to discover the subnet field width; it is perfectly reasonable for
  579.       a host with non-volatile storage to use stored information.
  580.  
  581. 3. Subnet Routing Methods
  582.  
  583.    One problem that faces all Internet hosts is how to determine a route
  584.    to another host.  In the presence of subnets, this problem is only
  585.    slightly modified.
  586.  
  587.    The use of subnets means that there are two levels to the routing
  588.    process, instead of one.  If the destination host is on the same
  589.    network as the source host, the routing decision involves only the
  590.    subnet gateways between the hosts.  If the destination is on a
  591.    different network, then the routing decision requires the choice both
  592.    of a gateway out of the source host's network, and of a route within
  593.    the network to that gateway.
  594.  
  595.    Fortunately, many hosts can ignore this distinction (and, in fact,
  596.    ignore all routing choices) by using a "default" gateway as the
  597.    initial route to all destinations, and relying on ICMP Host Redirect
  598.    messages to define more appropriate routes.  However, this is not an
  599.    efficient method for a gateway or for a multi-homed host, since a
  600.    redirect may not make up for a poor initial choice of route.  Such
  601.    hosts should use a routing information exchange protocol, but that is
  602.    beyond the scope of this document; in any case, the problem arises
  603.    even when subnets are not used.
  604.  
  605.    The problem for a singly-connected host is thus to find at least one
  606.    neighbor gateway.  Again, there are basic two solutions to this: use
  607.    hard-wired information, or use broadcasts.  We believe that the
  608.    neighbor-gateway acquisition problem is the same with or without
  609.    subnets, and thus the choice of solution is not affected by the use
  610.    of subnets.
  611.  
  612.    However, one problem remains: a source host must determine if
  613.    datagram to a given destination address must be sent via a gateway,
  614.    or sent directly to the destination host.  In other words, is the
  615.    destination host on the same physical network as the source?  This
  616.    particular phase of the routing process is the only one that requires
  617.    an implementation to be explicitly aware of subnets; in fact, if
  618.    broadcasts are not used, it is the only place where an Internet
  619.    implementation must be modified to support subnets.
  620.  
  621.    Because of this, it is possible to use some existing implementations
  622.    without modification in the presence of subnets <4>.  For this to
  623.    work, such implementations must:
  624.  
  625.  
  626. Mogul                                                          [Page 11]
  627.  
  628.  
  629.  
  630. RFC 917                                                     October 1984
  631. Internet Subnets
  632.  
  633.  
  634.       - Be used only on singly-homed hosts, and not as a gateway.
  635.  
  636.       - Be used on a broadcast LAN.
  637.  
  638.       - Use an Address Resolution Protocol (ARP), such [7].
  639.  
  640.       - Not be required to maintain connections in the case of gateway
  641.         crashes.
  642.  
  643.    In this case, one can modify the ARP server module in a subnet
  644.    gateway so that when it receives an ARP request, it checks the target
  645.    Internet address to see if it is along the best route to the target.
  646.    If it is, it sends to the requesting host an ARP response indicating
  647.    its own hardware address.  The requesting host thus believes that it
  648.    knows the hardware address of the destination host, and sends packets
  649.    to that address.  In fact, the packets are received by the gateway,
  650.    and forwarded to the destination host by the usual means.
  651.  
  652.    This method requires some blurring of the layers in the gateways,
  653.    since the ARP server and the Internet routing table would normally
  654.    not have any contact.  In this respect, it is somewhat
  655.    unsatisfactory.  Still, it is fairly easy to implement, and does not
  656.    have significant performance costs.  One problem is that if the
  657.    original gateway crashes, there is no way for the source host to
  658.    choose an alternate route even if one exists; thus, a connection that
  659.    might otherwise have been maintained will be broken.
  660.  
  661.    One should not confuse this method of "ARP-based subnetting" with the
  662.    superficially similar use of ARP-based bridges.  ARP-based subnetting
  663.    is based on the ability of a gateway to examine an IP address and
  664.    deduce a route to the destination, based on explicit subnet topology.
  665.    In other words, a small part of the routing decision has been moved
  666.    from the source host into the gateway.  An ARP-based bridge, in
  667.    contrast, must somehow locate each host without any assistance from a
  668.    mapping between host address and topology.  Systems built out of
  669.    ARP-based bridges should not be referred to as "subnetted".
  670.  
  671.    N.B.: the use of ARP-based subnetting is complicated by the use of
  672.    broadcasts.  An ARP server [7] should never respond to a request
  673.    whose target is a broadcast address.  Such a request can only come
  674.    from a host that does not recognize the broadcast address as such,
  675.    and so honoring it would almost certainly lead to a forwarding loop.
  676.    If there are N such hosts on the physical network that do not
  677.    recognize this address as a broadcast, then a packet sent with a
  678.    Time-To-Live of T could potentially give rise to T**N spurious
  679.    re-broadcasts.
  680.  
  681.  
  682.  
  683. Mogul                                                          [Page 12]
  684.  
  685.  
  686.  
  687. RFC 917                                                     October 1984
  688. Internet Subnets
  689.  
  690.  
  691. 4. Case Studies
  692.  
  693.    In this section, we briefly sketch how subnets have been used by
  694.    several organizations.
  695.  
  696.    4.1. Stanford University
  697.  
  698.       At Stanford, subnets were introduced initially for historical
  699.       reasons.  Stanford had been using the Pup protocols [1] on a
  700.       collection of several Experimental Ethernets [5] since 1979,
  701.       several years before Internet protocols came into use.  There were
  702.       a number of Pup gateways in service, and all hosts and gateways
  703.       acquired and exchanged routing table information using a simple
  704.       broadcast protocol.
  705.  
  706.       When the Internet Protocol was introduced, the decision was made
  707.       to use an eight-bit wide subnet number; Internet subnet numbers
  708.       were chosen to match the Pup network number of a given Ethernet,
  709.       and the Pup host numbers (also eight bits) were used as the host
  710.       field of the Internet address.
  711.  
  712.       The Pup-only gateways were then modified to forward Internet
  713.       datagrams according to their Pup routing tables; they otherwise
  714.       had no understanding of Internet packets and in fact did not
  715.       adjust the Time-to-live field in the Internet header.  This seems
  716.       to be acceptable, since bugs that caused forwarding loops have not
  717.       appeared.  The Internet hosts that are multi-homed and thus can
  718.       serve as gateways do adjust the Time-to-live field; since all of
  719.       the currently also serve as Pup gateways, no additional routing
  720.       information exchange protocol was needed.
  721.  
  722.       Internet host implementations were modified to understand subnets
  723.       (in several different ways, but with identical effects).  Since
  724.       all already had Pup implementations, the Internet routing tables
  725.       were maintained by the same process that maintained the Pup
  726.       routing tables, simply translating the Pup network numbers into
  727.       Internet subnet numbers.
  728.  
  729.       When 10Mbit Ethernets were added, the gateways were modified to
  730.       use the ARP-based scheme described in an earlier section; this
  731.       allowed unmodified hosts to be used on the 10Mbit Ethernets.
  732.  
  733.       IP subnets have been in use since early 1982; currently, there are
  734.       about 330 hosts, 18 subnets, and a similar number of subnet
  735.       gateways in service.  Once the Pup-only gateways are converted to
  736.       be true Internet gateways, an Internet-based routing exchange
  737.       protocol will be introduced, and Pup will be phased out.
  738.  
  739.  
  740. Mogul                                                          [Page 13]
  741.  
  742.  
  743.  
  744. RFC 917                                                     October 1984
  745. Internet Subnets
  746.  
  747.  
  748.    4.2. MIT
  749.  
  750.       MIT was the first IP site to accumulate a large collection of
  751.       local network links.  Since this happened before network numbers
  752.       were divided into classes, to have assigned each link at MIT its
  753.       own IP network number would have used up a good portion of the
  754.       available address space.  MIT decided to use one IP network
  755.       number, and to manage the 24-bit "rest" field itself, by dividing
  756.       it into three 8-bit fields; "subnet", "reserved, must be zero",
  757.       and "host".   Since the CHAOS protocol already in use at MIT used
  758.       an 8-bit subnet number field, it was possible to assign each link
  759.       the same subnet number in both protocols.  The IP host field was
  760.       set to 8 bits since most available local net hardware at that
  761.       point used 8 bit addresses, as did the CHAOS protocol; it was felt
  762.       that reserving some bits for the future was wise.
  763.  
  764.       The initial plan was to use a dynamic routing protocol between the
  765.       IP subnet gateways; several such protocols have been mooted but
  766.       nobody has bothered to implement one; static routing tables are
  767.       still used.  It is likely that this change will finally be made
  768.       soon.
  769.  
  770.       To solve the problem that imported IP software always needed
  771.       modification to work in the subnetted environment, MIT searched
  772.       for a model of operation that led to the least change in host IP
  773.       software.  This led to a model where IP gateways send ICMP Host
  774.       Redirects rather than Network Redirects.  All internal MIT IP
  775.       gateways now do so.  With hosts that can maintain IP routing
  776.       tables for non-local communication on a per host basis, this hides
  777.       most of the subnet structure.  The "minimum adjustment" for host
  778.       software to work correctly in both subnetted and non-subnetted
  779.       environments is the bit-mask algorithm mentioned earlier.
  780.  
  781.       MIT has no immediate plans to move toward a single "approved"
  782.       protocol; this is due partly to the degree of local autonomy and
  783.       the amount of installed software, and partly to the lack of a
  784.       single prominent industry standard.  Rather, the approach taken
  785.       has been to provide a single set of physical links and packet
  786.       switches, and to layer several "virtual" protocol nets atop the
  787.       single set of links.  MIT has had some bad experiences with trying
  788.       to exchange routing information between protocols and wrap one
  789.       protocol in another; the general approach is to keep the protocols
  790.       strictly separated except for sharing the basic hardware.  Using
  791.       ARP to hide the subnet structure is not much in favor; it is felt
  792.       that this overloads the address resolution operation.  In a
  793.       complicated system (i.e. one with loops, and variant link speeds),
  794.  
  795.  
  796.  
  797. Mogul                                                          [Page 14]
  798.  
  799.  
  800.  
  801. RFC 917                                                     October 1984
  802. Internet Subnets
  803.  
  804.  
  805.       a more sophisticated information interchange will be needed
  806.       between gateways; making this an explicit mechanism (but one
  807.       insulated from the hosts) was felt to be best.
  808.  
  809.    4.3. Carnegie-Mellon University
  810.  
  811.       CMU uses a Class B network currently divided into 11 physical
  812.       subnets (two 3Mbit Experimental Ethernets, seven 10Mbit Ethernets,
  813.       and two ProNet rings.) Although host numbers are assigned so that
  814.       all addresses with a given third octet will be on the same subnet
  815.       (but not necessarily vice versa), this is essentially an
  816.       administrative convenience.  No software currently knows the
  817.       specifics of this allocation mechanism or depends on it to route
  818.       between cables.
  819.  
  820.       Instead, an ARP-based bridge scheme is used.  When a host
  821.       broadcasts an ARP request, all bridges which receive it cache the
  822.       original protocol address mapping and then forward the request
  823.       (after the appropriate adjustments) as an ARP broadcast request
  824.       onto each of their other connected cables.  When a bridge receives
  825.       a non-broadcast ARP reply with a target protocol address not its
  826.       own, it consults its ARP cache to determine the cable onto which
  827.       the reply should be forwarded.  The bridges thus attempt to
  828.       transparently extend the ARP protocol into a heterogenous
  829.       multi-cable environment.  They are therefore required to turn ARP
  830.       broadcasts on a single cable into ARP broadcasts on all other
  831.       connected cables even when they "know better".  This algorithm
  832.       works only in the absence of cycles in the network connectivity
  833.       graph (which is currently the case).  Work is underway to replace
  834.       this simple-minded algorithm with a protocol implemented among the
  835.       bridges, in support of redundant paths and to reduce the
  836.       collective broadcast load.  The intent is to retain the ARP base
  837.       and host transparency, if possible.
  838.  
  839.       Implementations supporting the 3Mbit Ethernet and 10Mb proNET ring
  840.       at CMU use RFC-826 ARP (instead of some wired-in mapping such as
  841.       simply using the 8-bit hardware address as the the fourth octet of
  842.       the IP address).
  843.  
  844.       Since there are currently no redundant paths between cables, the
  845.       issue of maintaining connections across bridge crashes is moot.
  846.       With about 150 IP-capable hosts on the net, the bridge caches are
  847.       still of reasonable size, and little bandwidth is devoted to ARP
  848.       broadcast forwarding.
  849.  
  850.       CMU's network is likely to grow from its relatively small,
  851.       singly-connected configuration centered within their CS/RI
  852.  
  853.  
  854. Mogul                                                          [Page 15]
  855.  
  856.  
  857.  
  858. RFC 917                                                     October 1984
  859. Internet Subnets
  860.  
  861.  
  862.       facility to a campus-wide intra-departmental configuration with
  863.       5000-10000 hosts and redundant connections between cables.  It is
  864.       possible that the ARP-based bridge scheme will not scale to this
  865.       size, and a system of explicit subnets may be required.  The
  866.       medium-term goal, however, is an environment into which unmodified
  867.       extant (especially 10Mb ethernet based) IP implementations can be
  868.       imported; the intent is to stay with a host-transparent (thus
  869.       ARP-based) routing mechanism as long as possible.  CMU is
  870.       concerned that even if subnets become part of the IP standard they
  871.       will not be widely implemented; this is the major obstacle to
  872.       their use at CMU.
  873.  
  874.  
  875.  
  876.  
  877.  
  878.  
  879.  
  880.  
  881.  
  882.  
  883.  
  884.  
  885.  
  886.  
  887.  
  888.  
  889.  
  890.  
  891.  
  892.  
  893.  
  894.  
  895.  
  896.  
  897.  
  898.  
  899.  
  900.  
  901.  
  902.  
  903.  
  904.  
  905.  
  906.  
  907.  
  908.  
  909.  
  910.  
  911. Mogul                                                          [Page 16]
  912.  
  913.  
  914.  
  915. RFC 917                                                     October 1984
  916. Internet Subnets
  917.  
  918.  
  919. I. Address Format ICMP
  920.  
  921.    Address Format Request or Address Format Reply
  922.  
  923.        0                   1                   2                   3
  924.        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
  925.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  926.       |     Type      |      Code     |          Checksum             |
  927.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  928.       |           Identifier          |       Sequence Number         |
  929.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  930.  
  931.       IP Fields:
  932.  
  933.          Addresses
  934.  
  935.             The address of the source in an address format request
  936.             message will be the destination of the address format reply
  937.             message.  To form an address format reply message, the
  938.             source address of the request becomes the destination
  939.             address of the reply, the source address of the reply is set
  940.             to the replier's address, the type code changed to A2, the
  941.             subnet field width inserted into the Code field, and the
  942.             checksum recomputed.  However, if the source address in the
  943.             request message is zero, then the destination address for
  944.             the reply message should denote a broadcast.
  945.  
  946.       ICMP Fields:
  947.  
  948.          Type
  949.  
  950.             A1 for address format request message
  951.  
  952.             A2 for address format reply message
  953.  
  954.          Code
  955.  
  956.             0 for address format request message
  957.  
  958.             Width of subnet field, in bits, for address format reply
  959.             message
  960.  
  961.          Checksum
  962.  
  963.             The checksum is the 16-bit one's complement of the one's
  964.  
  965.  
  966.  
  967.  
  968. Mogul                                                          [Page 17]
  969.  
  970.  
  971.  
  972. RFC 917                                                     October 1984
  973. Internet Subnets
  974.  
  975.  
  976.             complement sum of the ICMP message starting with the ICMP
  977.             Type.  For computing the checksum, the checksum field should
  978.             be zero.  This checksum may be replaced in the future.
  979.  
  980.          Identifier
  981.  
  982.             An identifier to aid in matching request and replies, may be
  983.             zero.
  984.  
  985.          Sequence Number
  986.  
  987.             A sequence number to aid in matching request and replies,
  988.             may be zero.
  989.  
  990.       Description
  991.  
  992.          A gateway receiving an address format request should return it
  993.          with the Code field set to the number of bits of Subnet number
  994.          in IP addresses for the network to which the datagram was
  995.          addressed.  If the request was broadcast, the destination
  996.          network is "this network".  The Subnet field width may be from
  997.          0 to (31 - N), where N is the width in bits of the IP net
  998.          number field (i.e., 8, 16, or 24).
  999.  
  1000.          If the requesting host does not know its own IP address, it may
  1001.          leave the source field zero; the reply should then be
  1002.          broadcast.  Since there is only one possible address format for
  1003.          a network, there is no need to match requests with replies.
  1004.          However, this approach should be avoided if at all possible,
  1005.          since it increases the superfluous broadcast load on the
  1006.          network.
  1007.  
  1008.             Type A1 may be received from a gateway or a host.
  1009.  
  1010.             Type A2 may be received from a gateway, or a host acting in
  1011.             lieu of a gateway.
  1012.  
  1013.  
  1014.  
  1015.  
  1016.  
  1017.  
  1018.  
  1019.  
  1020.  
  1021.  
  1022.  
  1023.  
  1024.  
  1025. Mogul                                                          [Page 18]
  1026.  
  1027.  
  1028.  
  1029. RFC 917                                                     October 1984
  1030. Internet Subnets
  1031.  
  1032.  
  1033. II. Examples
  1034.  
  1035.    For these examples, we assume that the requesting host has  address
  1036.    36.40.0.123, that there is a gateway at 36.40.0.62, and that on
  1037.    network 36.0.0.0, an 8-bit wide subnet field is in use.
  1038.  
  1039.    First, suppose that broadcasting is allowed, and that 36.40.0.123
  1040.    knows  its own address.  It sends the following datagram:
  1041.  
  1042.       Source address:          36.40.0.123
  1043.       Destination address:     36.255.255.255
  1044.       Protocol:                ICMP = 1
  1045.       Type:                    Address Format Request = A1
  1046.       Code:                    0
  1047.  
  1048.    36.40.0.62 will hear the datagram, and should respond with this
  1049.    datagram:
  1050.  
  1051.       Source address:          36.40.0.62
  1052.       Destination address:     36.40.0.123
  1053.       Protocol:                ICMP = 1
  1054.       Type:                    Address Format Reply = A2
  1055.       Code:                    8
  1056.  
  1057.    For the following examples, assume that address 255.255.255.255
  1058.    denotes "broadcast to this physical network", as described in [6].
  1059.  
  1060.    The previous example is inefficient, because it potentially
  1061.    broadcasts  the request on many subnets.  The most efficient method,
  1062.    and the one we recommend, is for a host to first discover its own
  1063.    address (perhaps  using the "Reverse ARP" protocol described in [4]),
  1064.    and then to send  the ICMP request to 255.255.255.255:
  1065.  
  1066.       Source address:          36.40.0.123
  1067.       Destination address:     255.255.255.255
  1068.       Protocol:                ICMP = 1
  1069.       Type:                    Address Format Request = A1
  1070.       Code:                    0
  1071.  
  1072.    The gateway can then respond directly to the requesting host.
  1073.  
  1074.    Suppose that 36.40.0.123 is a diskless workstation, and does not know
  1075.    even its own host number.  It could send the following datagram:
  1076.  
  1077.  
  1078.  
  1079.  
  1080.  
  1081.  
  1082. Mogul                                                          [Page 19]
  1083.  
  1084.  
  1085.  
  1086. RFC 917                                                     October 1984
  1087. Internet Subnets
  1088.  
  1089.  
  1090.       Source address:          0.0.0.0
  1091.       Destination address:     255.255.255.255
  1092.       Protocol:                ICMP = 1
  1093.       Type:                    Address Format Request = A1
  1094.       Code:                    0
  1095.  
  1096.    36.40.0.62 will hear the datagram, and should respond with this
  1097.    datagram:
  1098.  
  1099.       Source address:          36.40.0.62
  1100.       Destination address:     36.40.255.255
  1101.       Protocol:                ICMP = 1
  1102.       Type:                    Address Format Reply = A2
  1103.       Code:                    8
  1104.  
  1105.    Note that the gateway uses the narrowest possible broadcast to reply
  1106.    (i.e., sending the reply to 36.255.255.255 would mean that it is
  1107.    transmitted on many subnets, not just the one on which it is needed.)
  1108.    Even so, the overuse of broadcasts presents an unnecessary load to
  1109.    all hosts on the subnet, and so we recommend that use of the
  1110.    "anonymous" (0.0.0.0) source address be kept to a minimum.
  1111.  
  1112.    If  broadcasting is not allowed, we assume that hosts have wired-in
  1113.    information about neighbor gateways; thus, 36.40.0.123 might send
  1114.    this datagram:
  1115.  
  1116.       Source address:          36.40.0.123
  1117.       Destination address:     36.40.0.62
  1118.       Protocol:                ICMP = 1
  1119.       Type:                    Address Format Request = A1
  1120.       Code:                    0
  1121.  
  1122.    36.40.0.62 should respond exactly as in the previous case.
  1123.  
  1124.  
  1125.  
  1126.  
  1127.  
  1128.  
  1129.  
  1130.  
  1131.  
  1132.  
  1133.  
  1134.  
  1135.  
  1136.  
  1137.  
  1138.  
  1139. Mogul                                                          [Page 20]
  1140.  
  1141.  
  1142.  
  1143. RFC 917                                                     October 1984
  1144. Internet Subnets
  1145.  
  1146.  
  1147. Notes
  1148.  
  1149.    <1>  For example, some host have addresses assigned by concatenating
  1150.         their Class A network number with the low-order 24 bits of a
  1151.         48-bit Ethernet hardware address.
  1152.  
  1153.    <2>  Our discussion of Internet broadcasting is based on [6].
  1154.  
  1155.    <3>  If broadcasting is not supported, them presumably a host "knows"
  1156.         the address of a neighbor gateway, and should send the ICMP to
  1157.         that gateway.
  1158.  
  1159.    <4>  This is what was referred to earlier as the coexistence of
  1160.         transparent and explicit subnets on a single network.
  1161.  
  1162.  
  1163.  
  1164.  
  1165.  
  1166.  
  1167.  
  1168.  
  1169.  
  1170.  
  1171.  
  1172.  
  1173.  
  1174.  
  1175.  
  1176.  
  1177.  
  1178.  
  1179.  
  1180.  
  1181.  
  1182.  
  1183.  
  1184.  
  1185.  
  1186.  
  1187.  
  1188.  
  1189.  
  1190.  
  1191.  
  1192.  
  1193.  
  1194.  
  1195.  
  1196. Mogul                                                          [Page 21]
  1197.  
  1198.  
  1199.  
  1200. RFC 917                                                     October 1984
  1201. Internet Subnets
  1202.  
  1203.  
  1204. References
  1205.  
  1206.    1.  D.R. Boggs, J.F. Shoch, E.A. Taft, and R.M. Metcalfe. "Pup: An
  1207.        Internetwork Architecture."  IEEE Transactions on Communications
  1208.        COM-28, 4, pp612-624, April 1980.
  1209.  
  1210.    2.  David D. Clark.  Names, Addresses, Ports, and Routes.  RFC-814,
  1211.        MIT-LCS, July 1982.
  1212.  
  1213.    3.  Yogan K. Dalal and Robert M. Metcalfe. "Reverse Path Forwarding
  1214.        of Broadcast Packets."  Comm. ACM 21, 12, pp1040-1048, December
  1215.        1978.
  1216.  
  1217.    4.  Ross Finlayson, Timothy Mann, Jeffrey Mogul, Marvin Theimer. A
  1218.        Reverse Address Resolution Protocol. RFC-903, Stanford
  1219.        University, June 1984.
  1220.  
  1221.    5.  R.M. Metcalfe and D.R. Boggs. "Ethernet: Distributed Packet
  1222.        Switching for Local Computer Networks."  Comm. ACM 19, 7,
  1223.        pp395-404, July 1976.  Also CSL-75-7, Xerox Palo Alto Research
  1224.        Center, reprinted in CSL-80-2.
  1225.  
  1226.    6.  Jeffrey Mogul. Broadcasting Internet Datagrams. RFC-919, Stanford
  1227.        University, October 1984.
  1228.  
  1229.    7.  David Plummer. An Ethernet Address Resolution Protocol. RFC-826,
  1230.        Symbolics, September 1982.
  1231.  
  1232.    8.  Jon Postel. Internet Protocol. RFC-791, USC-ISI, September 1981.
  1233.  
  1234.    9.  Jon Postel. Internet Control Message Protocol. RFC-792, USC-ISI,
  1235.        September 1981.
  1236.  
  1237.  
  1238.  
  1239.  
  1240.  
  1241.  
  1242.  
  1243.  
  1244.  
  1245.  
  1246.  
  1247.  
  1248.  
  1249.  
  1250.  
  1251.  
  1252.  
  1253. Mogul                                                          [Page 22]
  1254.  
  1255.