[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03

Network Working Group                                        W A Simpson
Internet Draft                                                Daydreamer
expires in six months                                      December 1993

                        SIPP Neighbor Discovery

Status of this Memo

   This memo is the product of the SIPP Working Group of the Internet
   Engineering Task Force (IETF).  Comments on this memo should be
   submitted to the sipp@sunroof.eng.sun.com mailing list.

   Distribution of this memo is unlimited.

   This document is an Internet Draft.  Internet Drafts are working
   documents of the Internet Engineering Task Force (IETF), its Areas,
   and its Working Groups.  Note that other groups may also distribute
   working documents as Internet Drafts.

   Internet Drafts are draft documents valid for a maximum of six
   months.  Internet Drafts may be updated, replaced, or obsoleted by
   other documents at any time.  It is not appropriate to use Internet
   Drafts as reference material or to cite them other than as a
   ``working draft'' or ``work in progress.''

   Please check the 1id-abstracts.txt listing contained in the
   internet-drafts Shadow Directories on nic.ddn.mil, ds.internic.net,
   nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the
   current status of any Internet Draft.


   This document discusses the identification and location of adjacent
   SIPP nodes.

Simpson                  expires in six months                  [Page i]

DRAFT                    SIPP Discovery Design             December 1993

1.  Goals

   Historically, the methods for determination of the next-hop media
   address evolved separately from those for location of neighbors or
   auto-configuration of systems.  With the advent of SIPP, the old
   techniques must be re-implemented, usually due to larger field sizes.

   Unfortunately, older implementations frequently did not take proper
   care in differentiating existing variable field lengths, version
   numbers, and new types of messages.  None of the current protocols
   are readily extensible.  While some have the ability to change in
   simple terms, such as larger addresses, none were designed to add new
   kinds of information to be carried in the same packet.

   Therefore, the techniques used for SIPP are required to be
   distinguishable from previous IP versions.  This is an opportunity to
   design a uniform and coherent method for accomplishing these goals.

   Find Neighbors

      Each SIPP node needs to determine the availability of other SIPP
      nodes as demand for communication occurs.

      Each SIPP host needs to detect the presence of available SIPP


      A redirect is used when a packet could be sent more directly to
      the SIPP next-hop, or to indicate that another SIPP router should
      be used for forwarding specific packets.

   Resolve Media Address

      Each SIPP node which desires to send to another SIPP node needs to
      know the appropriate media address, when the link is not a point
      to point link.  It is more efficient to learn this in the same
      transaction as the neighbor is found or traffic is redirected.

   Learn Prefix

      When prefix-routing is in use, it is necessary to determine the
      prefix(es) for a local subnet.  Local prefixes and multiple
      providers are supported.

   Change Prefix

      When a prefix changes, it is necessary to update the nodes.

Simpson                  expires in six months                  [Page 1]

DRAFT                    SIPP Discovery Design             December 1993


      The same mechanisms which support wired identification and
      location are used to provide mobile beaconing and roaming within

2.  Criteria

   Through prior experience, the following criteria were established, in
   order of relative importance.  It is understood that many of these
   criteria require various tradeoffs.

   Multicast support

      All SIPP systems are required to support multicast techniques.

      There are numerous advantages to using multicast for the new
      messages.  In particular, when compared to broadcast, reduced
      overhead for processing messages which are not ultimately intended
      for the local system.

      This is the primary technique for distinguishing the new messages.
      Older systems will discard SIPP multicast messages at the link

      Not all media supports multicast.  Since multicast is directly
      supported by the SIPP header, this technique will work even when
      using link-layer broadcast, or link-layer unicast to each
      recipient.  Older systems should discard SIPP headers at the
      network layer.

   Reduced net traffic

      Currently, separate packets are sent for media address resolution,
      router discovery, and the Hello protocols for the various routing
      algorithms.  Since much of the same information is contained in
      each of these packets, it would be helpful to combine the
      functions in a single packet where possible.

      This is particularly important in broadcast mobile environments,
      due to the time for setup of transmission, the increased per frame
      overhead for contention resolution, and forward error correction.

   Low storage overhead

      It is desirable that systems require as little storage overhead as
      possible.  In particular, mobile nodes often have significantly

Simpson                  expires in six months                  [Page 2]

DRAFT                    SIPP Discovery Design             December 1993

      reduced processing power and memory.

      A host should only retain information for those hosts with which
      it is directly communicating.

      There must be sufficient storage in a host for information about
      at least one router.  In addition, storage is required for at
      least one location of each service (such as a domain name server)
      which is used.

      A router may require more processing power and memory.
      Participation in routing protocols requires the knowledge of every
      neighboring router.

      When prefix-routing is in use, it is not necessary for a router to
      determine the location of a host until traffic for the host
      arrives.  If prefix-routing is not used, particularly in mobile
      environments, the location of each reachable host must be


      The connection procedures for a configuring a new system are
      reduced to the minimal set of "plug it in, turn on the power, and

      -  Each node is assigned an identifier, usually within the number
         space assigned to the local subnet.

      -  The node discovers the routers attached to the local subnet, so
         that it can exchange packets with remote systems.

      -  The node discovers the location of servers that it needs for
         configuration, loading, dumping, printing, and other services.

      -  If desired, each node is assigned a name within the local
         domain.  The name, and the associated identifiers, can be
         registered in the local domain name server.

      In evaluating previous experience with autoconfiguration
      procedures, the following constraints were determined:

      1)    Using the 48-bit IEEE-802 number to identify one node within
            a local subnetwork that is not designed to accomodate more
            than a few hundred systems is considerable overkill.

            However, it may be worthwhile to use an IEEE-802 number
            during initial configuration, until a globally routable

Simpson                  expires in six months                  [Page 3]

DRAFT                    SIPP Discovery Design             December 1993

            identifier can be assigned.

      2)    Random identifier assignments are to be avoided.  They do
            not scale well to large networks, are difficult to track and
            manage, and lead to administrative confusion.

            Relying on broadcast collision resolution procedures for
            avoiding duplicate assignments results in conflicts when
            nodes occupy partitioned subnets, or are frequently powered
            down or taken off-line.

      3)    Changes of identifiers should be transparent to the human
            users.  In particular, renumbering for changes of providers,
            and assignment of alias identifiers as a mobile node moves,
            should be automatic.

      4)    Users should not be concerned with routing prefixes, or the
            routing methods extant on the local network.  When used,
            such prefixes should be automatically determined, and
            dynamic changes should propagate automatically.

      5)    It is important to allow users to choose a node name which
            is memorable and comfortable to them.  The name should be
            automatically registered, and changes to the associated
            identifers should be maintained automatically.

      This design provides initial self-identification and propagation
      of changes in identification.  Other aspects of configuration,
      such as loading the operating system and environment, and
      additional facilities and servers for registration, are outside
      the scope of neighbor discovery.


      As mentioned repeatedly above, mobility is an important
      consideration when evaluating these criteria.

      When identification is dynamically changing while moving, other
      nodes must be notified of the changes.

      In addition, the "half link" problem has to be considered.  This
      occurs when node J can hear node K, but K cannot hear J.  If there
      is a path from J to a router which K can hear, completing the
      circuit, communication can still occur.

      Only basic support for mobility is provided.  Other aspects of
      mobility, such as registration and caching, are outside the scope
      of neighbor discovery.

Simpson                  expires in six months                  [Page 4]

DRAFT                    SIPP Discovery Design             December 1993

   Black hole detection

      In determining whether the next-hop node is still available, there
      is a basic tradeoff between frequent queries and resources used.
      This design trades fewer queries against more information within
      each query and response.

      Explicit holding times are used to limit the exposure to black
      holes.  The times may be dynamically shortened by the responsible
      node when a resource is critical, or when the node is actively

   Media independence

      There are many instances where node discovery is accomplished
      differently over different media, such as point-to-point versus
      broadcast versus Public Data Networks.  This design places the
      neighbor discovery above the network layer, where it enjoys
      greater independence.

      There are difficulties with carrying media addresses within
      packets, especially in the presence of multi-media bridges.
      Rather than allowing translation by bridges in the path, this
      design exercizes control at the destination node, and requires all
      such media addresses to be in canonical form.

   Optimal route determination

      This is essentially a superset of next-hop discovery, combined
      with resource reservation and possible policy considerations, and
      the ability to redirect traffic under changing conditions.  This
      is not well supported in any of the past protocols.

      The design encompasses media level redirects between multiple
      logical subnets on the same physical media, and provides for the
      absence of logical subnetting information when visiting mobile
      hosts continue to use their native identifiers.

      To balance system overhead against network traffic, this design
      attempts to adapt to a continuum of machine capabilities.  Dumb
      hosts may simply send packets to a default router, and be
      redirected to the correct next-hop by the more capable routers.
      Smarter hosts learn sufficient information to make informed


      This design reduces the number of packet types which must be

Simpson                  expires in six months                  [Page 5]

DRAFT                    SIPP Discovery Design             December 1993

      supported in a pure SIPP node, and reduces the number of nodes
      which recognize and respond to each type.  The packets are
      designed with 32 and 64 bit boundaries for efficient processing.

Simpson                  expires in six months                  [Page 6]

DRAFT                    SIPP Discovery Design             December 1993

3.  Historic Methods


   The most common next-hop resolution protocol, the Address Resolution
   Protocol (ARP), is done at the link level rather than the network
   level.  It requires an additional two media packets at the beginning
   of each connection.  A Request is sent, a Reply is received, and then
   the first datagram can be sent to the next-hop.  This causes a
   significant amount of traffic, and considerable latency in
   establishing a connection, particularly when multiple hops need to
   use ARP.

   ARP is simple, and has low storage overhead.

   ARP is deemed inadequate because it is a broadcast rather than a
   multicast technique, is frequently media dependent, is not easily
   extensible for auto-configuration or mobility support, and it does
   not directly support black-hole detection.

ICMP Router Discovery

   The ICMP Router Discovery messages provide some of the desired
   features.  Each router sends Hellos on a periodic basis.  After
   determining that a destination is not on the local media, a host can
   send packets directly to a "preferred" router, which forwards the
   packet to the correct destination.  If a better next-hop is known,
   the router sends a redirect to the host.

   This can reduce the traffic from 3 to 2 packets at the beginning of a
   connection.  Unfortunately, the technique is not widely implemented
   in the current generation of protocols.

   It does not provide a comprehensive solution to auto-configuration,
   mobility, black-hole detection, or media independence.

ES-IS Hellos

   The ISO solution (ES-IS) addresses some of these problems.  Each host
   and router sends Hellos on a periodic basis.  Every node must
   remember all of the media addresses for the other systems on the
   local network.

   However, the traffic overhead of many packets sent by every node on a
   regular basis eliminates it from consideration.  Also, it requires a
   large amount of storage overhead in each node.

Simpson                  expires in six months                  [Page 7]

DRAFT                    SIPP Discovery Design             December 1993

Media Multicast

   The first packet destined for an unknown node might be sent to the
   all-systems multicast, or to a media multicast based on a hash
   function of the destination.  The appropriate node would accept the
   packet, and send a redirect indicating the appropriate media address
   to be used for future packets.

   This reduces the traffic from 3 to 2 packets at the beginning of a
   connection, and eliminates the latency of ARP, as the probe packet
   sent is also the data packet.  This also eliminates the queuing of
   datagrams waiting for the ARP reply.

   However, the destination identifier in the network header will be
   unicast, while the media address will be multicast.

   If this method were used exclusively, routers would be required to
   listen to all multicasts, and recognize those packets destined beyond
   the local link.

   Multi-homed hosts also require the capability to decide which link to
   use, and are not supportable using this technique alone.

   This method is not extensible to include other information useful in
   mobile environments, resource reservation, and policy routing.

Simpson                  expires in six months                  [Page 8]

DRAFT                    SIPP Discovery Design             December 1993

4.  Solution Overview

   This design is a combination of the best features of the preceding

4.1.  Packets

   This solution describes two packets, not much different from those
   already deployed.  These familiar forms are re-packaged to join
   common functions into the same packet to reduce traffic, and are
   designed to be more extensible in the future.

   In order to foster media independence, the packets are part of ICMP,
   which allows the protocols to be used over broadcast, multicast,
   partial-mesh, and point-to-point media.  This is similar to the
   positioning of ES-IS.

4.1.1.  Solicitations

   The Where-Are-You solicitation is used to find other nodes, and
   associated resources and services.  Router solicitations are sent
   when a node interface is initialized.  Specific solicitations are
   sent when one node is ready to communicate with another particular

4.1.2.  Advertisements

   The I-Am-Here advertisement is the answer to the Where-Are-You
   solicitation.  Advertisements are also sent on a periodic basis to
   indicate special resources and services.  Periodic advertisements
   from a few commonly requested nodes result in less traffic than
   repeated solicitations from many nodes.

4.1.3.  LifeTime

   A lifetime is associated with each node location, specifying the
   maximum length of time that the location is to be considered valid in
   the absence of further information.  The lifetime is set when a
   solicitation is sent, or when an advertisement is received.

   This prevents the sending of repeated solicitations, and limits
   exposure to black holes.  This ensures that other nodes eventually
   forget about nodes that become unreachable, whether that is because
   the node has failed, or it no longer provides the advertised service.

Simpson                  expires in six months                  [Page 9]

DRAFT                    SIPP Discovery Design             December 1993

4.1.4.  Extensions

   Each message contains "optional" extensions, designed to allow
   flexibility and extensibility.

   One of the common extensions is the media address.  Each message
   contains enough information to return a reply directly to the sender,
   without additional location traffic.  By carrying media addresses
   within the advertisements and redirect packets, a further ARP-like
   query/response can be avoided entirely.  This reduces traffic, and
   further prevents black-holes when forwarding tables are not updated
   due to packet loss.

   Another common extension is a list of the routers which have been
   heard.  This allows routers to build a map of the paths between
   routers, and between routers and hosts.  This is designed to be used
   by most commonly deployed routing protocols.  This also solves the
   "half link" problem, when used together with the well-known link-
   state class of routing protocols.

4.2.  Router Discovery

   Routers advertise their locations periodically.  The number of
   routers are usually fewer than the number of hosts.

   When a router is present, a host learns whether the local media uses
   prefix routing.  The host sends datagrams directly to its preferred
   router for all destinations which it cannot determine to be on the
   local media.  The router issues a redirect when another router would
   be more appropriate or the destination is directly accessible on the
   local media.

   When most of the traffic is between nodes that are not on the same
   local media, this is very efficient.  When most of the traffic is
   between hosts on the local media (client-server), the extra redirect
   packets will be rare.

4.3.  Host Discovery

   When a host or router needs the location of a target host on the
   local media, it sends a media multicast solicitation for the location
   of the host, followed by a media multicast of the original data
   packet.  The target node issues an advertisement which indicates its
   current reachability.

   When most of the traffic is between hosts on the local media

Simpson                  expires in six months                 [Page 10]

DRAFT                    SIPP Discovery Design             December 1993

   (client-server), the extra solicitation and advertisement packets
   will be rare.

Simpson                  expires in six months                 [Page 11]

DRAFT                    SIPP Discovery Design             December 1993

5.  Sending Datagrams

   The internetwork layer chooses the next hop for each datagram sent.
   If the destination is on the local media, the datagram is sent
   directly to the destination.  Otherwise, it has to be sent to a

5.1.  Local/Remote Decision

   To decide if the destination is on the local media, the following
   algorithm MUST be used:

   (a)   For a multicast destination, simply pass the datagram to the
         link layer for any indicated interface(s).

   (b)   A list of routing-prefixes is maintained for each interface.
         This prefix MAY be configured, or learned from Router
         Advertisements.  The prefix size is the number of valid bits in
         the prefix.

   (c)   If an interface prefix exactly matches the destination prefix
         extracted by the same prefix size, then the destination is on
         the corresponding local media, and the datagram is to be
         transmitted directly to the destination.

   (d)   If there are no matches, and no Router Advertisements have been
         heard, then the destination is on the local media.  The
         datagram is multicast on all interfaces.

   (e)   If there are no matches, and one or more Router Advertisements
         have been heard, then the destination is accessible only
         through a router.  Selection of a router is described in "SIPP
         Router Discovery" [$].

   The host MUST operate correctly in a minimal network environment.
   For example, if the host insists on finding at least one router to
   initialize, the host will be unable to operate on an isolated

5.2.  Media Address Determination

   When the media address for a destination is unknown, the following
   procedure is used:

   (a)   For a multi-homed host, the datagram is duplicated on all

Simpson                  expires in six months                 [Page 12]

DRAFT                    SIPP Discovery Design             December 1993

   (b)   If an interface has no broadcast capability (a point-to-point
         link), and the peer entity is unknown, the datagram is sent on
         the interface.

   (c)   If an interface has no broadcast capability (an X.25 or Frame-
         Relay link), the datagram is duplicated on each virtual circuit
         for which there is no known peer entity, as if they were each a
         separate point-to-point interface on a multi-homed host.

   (d)   If an interface has no multicast capability, the datagram is
         sent as a link-layer broadcast.  The SIPP Destination is

   (e)   For an interface with multicast capability, the datagram is
         sent as a link-layer multicast.  The multicast address used is
         the exclusive-or of every octet of the SIPP Destination, added
         to the selected-systems multicast.  The SIPP Destination is

   (f)   Immediately following the datagram, when there is no entry in
         the route cache, a Where-Are-You solicitation is sent,
         utilizing the same SIPP Destination as the datagram.

   (g)   When there is an entry in the route cache, for an unknown media
         address, no further solicitations are sent until the cache
         entry expires.

   On receipt of a unicast datagram from a broadcast or multicast media
   address, the datagram is silently discarded if the SIPP Destination
   does not match any SIPP identifying-address of the node.

   On receipt of a Where-Are-You solicitation, the target node sends a
   multicast I-Am-Here advertisement to the all-systems multicast.

   On receipt of a multicast I-Am-Here advertisement, all nodes which
   have a route cache entry for the SIPP Source update the cache entry
   with the current LifeTime and media address.

5.3.  Route Cache

   To efficiently route a series of datagrams to the same destination,
   the source host MUST keep a "route cache" of mappings to
   destinations.  A host uses the following basic algorithm on this
   cache to route a datagram:

   (a)   If the cache contains information for a particular destination,
         the interface and media address are used to send the datagram.

Simpson                  expires in six months                 [Page 13]

DRAFT                    SIPP Discovery Design             December 1993

         This entry might point directly to the destination, or to a
         router which handles the destination.

   (b)   If the cache contains no information for a particular
         destination, a determination is made whether the destination is
         on the local media.

   (c)   When the destination is determined to be accessible through a
         router, the cache entry for the router is used to send the
         datagram.  The router cache entry might be duplicated, or a
         system of pointers could be used.  In any case, the cache entry
         for the destination MUST have the same LifeTime as the cache
         entry for the router.

   (d)   When the destination is determined to be on the local media,
         the media address is solicited.  A new cache entry is made,
         with a limited LifeTime, to inhibit sending of repeated

   Each route cache entry needs to include the following items.

   (1)  LifeTime
   (2)  Next-hop interface (for a multi-homed host)
   (3)  Next-hop media address
   (4)  Destination SIPP identifying-address
   (5)  Destination prefix size
   (6)  Source SIPP identifying-address (for a multi-homed host)
   (7)  Flow number

   Field (4) MAY be the full SIPP identifying-address of the
   destination, or only the destination network number.  This is
   determined by the prefix size in (5).

   Field (7) SHOULD be included.

      Each route cache entry defines the endpoints of an internetwork
      path.  Although the connecting path may change dynamically in an
      arbitrary way, the transmission characteristics of the path tend
      to remain approximately constant over a time period longer than a
      single typical host-host transport connection.  Therefore, a route
      cache entry is a natural place to cache data on the properties of
      the path.

      Examples of such properties might be the maximum unfragmented
      datagram size, or the average round-trip delay measured by a
      transport protocol.  This data will generally be both gathered and
      used by a higher layer protocol (that is, by TCP, or by an

Simpson                  expires in six months                 [Page 14]

DRAFT                    SIPP Discovery Design             December 1993

      application using UDP).  Experiments are currently in progress on
      caching path properties in this manner.

      There is no consensus on whether the route cache should be keyed
      on destination host addresses alone, or allow both host and
      network addresses.  Those who favor the use of only host addresses
      argue that:

      (1)   Redirect messages will generally result in entries keyed on
            destination host addresses.  The simplest and most general
            scheme would be to use host addresses always.

      (2)   The IP layer may not always know the prefix size for a
            network address in a complex subnetted environment.

      (3)   The use of only host addresses allows the destination
            address to be used as a pure 64-bit number, which may allow
            the Internet architecture to be more easily extended in the
            future without any change to the hosts.

      The opposing view is that allowing a mixture of destination hosts
      and networks in the route cache:

      (1)   Saves memory space.

      (2)   Leads to a simpler data structure, easily combining the
            cache with the tables of default and static routes.

      (3)   Provides a more useful place to cache path properties.

   The cache needs to be large enough to include entries for the maximum
   number of destination hosts that may be in use at one time.

   A route cache entry may also include control information used to
   choose an entry for replacement.  This might take the form of a
   "recently used" bit, a use count, or a last-used timestamp, for
   example.  It is recommended that it include the time of last
   modification of the entry, for diagnostic purposes.

   An implementation may wish to reduce the overhead of scanning the
   route cache for every datagram to be transmitted.  This may be
   accomplished with a hash table to speed the lookup, or by giving a
   connection-oriented transport protocol a "hint" or temporary handle
   on the appropriate cache entry, to be passed to the IP layer with
   each subsequent datagram.

   Although we have described the route cache, the lists of default

Simpson                  expires in six months                 [Page 15]

DRAFT                    SIPP Discovery Design             December 1993

   routers, and a table of static routes as conceptually distinct, in
   practice they may be combined into a single "routing table" data

5.4.  Configuration

   Default routers and preference levels MUST NOT be configured
   manually.  Instead, "SIPP Router Discovery" [$] MUST be used.

   The routing-prefix(es) for an interface SHOULD NOT be configured
   manually.  When a node is multi-homed, the node discovery multicast
   MUST be sent on all interfaces which have not discovered the presence
   of a router.

Simpson                  expires in six months                 [Page 16]

DRAFT                    SIPP Discovery Design             December 1993

Security Considerations





   The document was initially composed of quotations from the RFC-1122
   Host Requirements, and selections of text contributed by Fred Baker
   (ACC), Dino Farinacci (Cisco), Christian Huitema (INRIA), Frank
   Kastenholz (FTP Software), Tony Li (Cisco), Dave Piscitello
   (Bellcore), and Garrett Wollman (UVM?).

Simpson                  expires in six months                 [Page 17]

DRAFT                    SIPP Discovery Design             December 1993

Chair's Address

   The working group can be contacted via the current chairs:

      Stephen Deering                 Paul Francis
      3333 Coyote Hill Road           445 South St. 2L-281
      Palo Alto, CA  94304            Morristown, NJ  07960

      415-812-4839                    201-829-4484

      Deering@PARC.Xerox.com          francis@thumper.bellcore.com

      Robert M Hinden
      2550 Garcia Avenue
      Mountain View, CA  94043-1100



Author's Address

   Questions about this memo can also be directed to:

      William Allen Simpson
      Computer Systems Consulting Services
      1384 Fontaine
      Madison Heights, Michigan  48071


Simpson                  expires in six months                 [Page 18]

DRAFT                    SIPP Discovery Design             December 1993

                           Table of Contents

     1.     Goals .................................................    1

     2.     Criteria ..............................................    2

     3.     Historic Methods ......................................    7

     4.     Solution Overview .....................................    9
        4.1       Packets .........................................    9
           4.1.1  Solicitations ...................................    9
           4.1.2  Advertisements ..................................    9
           4.1.3  LifeTime ........................................    9
           4.1.4  Extensions ......................................   10
        4.2       Router Discovery ................................   10
        4.3       Host Discovery ..................................   10

     5.     Sending Datagrams .....................................   12
        5.1       Local/Remote Decision ...........................   12
        5.2       Media Address Determination .....................   12
        5.3       Route Cache .....................................   13
        5.4       Configuration ...................................   16

     SECURITY CONSIDERATIONS ......................................   17

     REFERENCES ...................................................   17

     ACKNOWLEDGEMENTS .............................................   17

     CHAIR'S ADDRESS ..............................................   18

     AUTHOR'S ADDRESS .............................................   18

Html markup produced by rfcmarkup 1.129c, available from https://tools.ietf.org/tools/rfcmarkup/