Network Working Group W A Simpson Internet Draft Daydreamer expires in six months March 1994 SIPP Neighbor Discovery draft-ietf-sipp-discovery-04.txt Status of this Memo This document is a submission to the SIPP Working Group of the | Internet Engineering Task Force (IETF). Comments 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, | venera.isi.edu, nic.nordu.net, or munnari.oz.au to learn the current status of any Internet Draft. Abstract This document discusses the identification and location of adjacent SIPP nodes, including Router Discovery and Media Access Discovery. Simpson expires in six months [Page i] DRAFT SIPP Neighbor Discovery March 1994 1. Introduction 1.1. Goals Historically, the methods for determination of the next-hop media address evolved separately from those for location of neighbors or | self-identification of nodes. 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 routers. Redirect 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 node which sends to another node needs to know the | appropriate media address, when the link is not point-to-point. | It is more efficient to learn this in the same transaction as the neighbor is found or traffic is redirected. Learn Routing-Prefix | When prefix routing is in use, it is necessary to determine the | prefix(es) for a link. Multiple cluster-prefixes are supported. Simpson expires in six months [Page 1] DRAFT SIPP Neighbor Discovery March 1994 Change Routing-Prefix | When a cluster-prefix changes, it is necessary to update the node | identifying-addresses. Mobility The same mechanisms which support wired identification and location are used to provide mobile beaconing and roaming within clusters. 1.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 nodes 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 node. This is the primary technique for distinguishing the new messages. | Older nodes will discard unrecognized multicast messages at the | link-layer. 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 nodes will discard SIPP headers at the | internetwork-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 lower transmission rates, and the increased per frame | Simpson expires in six months [Page 2] DRAFT SIPP Neighbor Discovery March 1994 overhead for contention resolution and forward error correction. Low storage overhead It is desirable that nodes require as little storage overhead as | possible. In particular, mobile nodes often have significantly reduced processing power and memory. A host should only retain information for those nodes 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 retained. Auto-configuration The connection procedures for a configuring a new node are reduced | to the minimal set of "plug it in, turn on the power, and run". - Each node is assigned an identifier, usually within the number | space assigned to one or more links to which it is attached. - The node discovers the routers attached to each link, so that | it can exchange packets with remote nodes. - 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 | administrative domain. The name, and the associated identifiers, can be registered in the local domain name server. In evaluating previous experience with self-identification | procedures, the following constraints were determined: 1) Using the 48-bit IEEE-802 number to identify one node on a | Simpson expires in six months [Page 3] DRAFT SIPP Neighbor Discovery March 1994 link that is not designed to accomodate more than a few | hundred nodes is considerable overkill. Also, experience has shown that the IEEE-802 number is not always unique, as was originally intended. However, it may be worthwhile to use an IEEE-802 number during initial configuration, until a globally routable 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 links, 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 cluster-prefixes, or the | routing methods extant in the local administrative domain. 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. * Mobility 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. * Simpson expires in six months [Page 4] DRAFT SIPP Neighbor Discovery March 1994 Black hole detection In determining whether the next-hop node is still available, there is a basic tradeoff between frequent queries and resources used. | Reducing traffic requires 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 moving. Media independence There are many instances where neighbor discovery is accomplished | differently over different media, such as point-to-point versus broadcast versus Public Data Networks. Node discovery should be | above the internetwork-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, control | should be in the destination node. This 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 link-layer redirects between multiple | cluster-prefixes on the same physical media. It also provides for | the absence of cluster-prefix information when visiting mobile | hosts continue to use their native identifying-addresses. To balance storage overhead against link traffic, this design | attempts to adapt to a continuum of machine capabilities. Less | powerful 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 choices. Simplicity The design must reduce the number of packet types which must be | Simpson expires in six months [Page 5] DRAFT SIPP Neighbor Discovery March 1994 supported in a pure SIPP node, and reduce the number of nodes | which recognize and respond to each type. The packets must be | designed with 32 and 64 bit boundaries for efficient processing. 1.3. Historic Methods | ARP | The most common next-hop resolution protocol, the Address Resolution Protocol (ARP), is done at the link-layer rather than | the internetwork-layer. It requires an additional two link-layer | 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, adds latency, is frequently media dependent, | is not easily extensible for self-identification or mobility | support, and does not directly support black-hole detection. ICMP Router Discovery The ICMP Router Discovery messages provide some of the desired features. Each router advertises on a periodic basis. After | determining that a destination is not on an attached link, 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 self- | identification, 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 nodes on each | Simpson expires in six months [Page 6] DRAFT SIPP Neighbor Discovery March 1994 attached link. 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. Media Multicast The first packet destined for an unknown node might be sent to the | all-nodes 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 internetwork header will be unicast, while the media address will be multicast, which | could confuse some driver implementations. If this method were used exclusively, routers would be required to listen to all multicasts, and recognize those packets destined | beyond that link. Multi-homed hosts also require the capability to decide which link | to use, and are not supportable using this technique alone. Because the data packet is used for the probe, this method is not | extensible to include other information useful in mobile environments, resource reservation, and policy routing. Simpson expires in six months [Page 7] DRAFT SIPP Neighbor Discovery March 1994 2. Solution Overview This design is a combination of the best features of the preceding techniques. 2.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 links. This is similar to the positioning of ES-IS. 2.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 node. 2.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. 2.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 usually set when an advertisement is received. This Simpson expires in six months [Page 8] DRAFT SIPP Neighbor Discovery March 1994 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. This limits exposure to | black holes. | The lifetime is also set when a solicitation is sent, to prevent the | sending of repeated solicitations. 2.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. 2.2. Router Discovery | Before a node can send datagrams beyond its directly attached | link(s), it must discover the location of at least one operational | router on the link(s). This is accomplished through Where-Are-You and I-Am-Here messages. The messages also serve to construct a map of accessible hosts, to | discover partitions in the links, and to support mobile nodes. When any node initializes an interface, it sends a Where-Are-You Router Solicitation to prompt for immediate router advertisements, rather than waiting for the next periodic message to arrive. Each router periodically sends the I-Am-Here Router Advertisement from each of its interfaces. Nodes discover the location of their Simpson expires in six months [Page 9] DRAFT SIPP Neighbor Discovery March 1994 neighboring routers simply by listening for the advertisements. This eliminates the need for manual configuration of router addresses and is independent of any specific routing protocol. The advertisement messages do not constitute a routing protocol, although they might be used by a routing protocol to build a map of neighboring nodes. They enable nodes to discover the existence of neighboring routers, but not necessarily which router is best to reach a particular destination. If a node chooses a poor router for a particular destination, it should receive a redirect from that router. However, the advertisements often contain sufficient information to make a good choice of first-hop. This might be important for choosing among routers which are participating in a security group or policy-based routing. The number of routers are usually fewer than the number of hosts. The periodic router advertisements result in fewer messages than | would occur if every node sent repeated solicitations to discover the appropriate routers. When a router is present, a host sends datagrams directly to its | preferred router. The router issues a redirect when another router | would be more appropriate, or the destination is directly accessible | on that link. This is designed to put the primary routing burden on the routers, and allows annealing of partitioned links with no effort | by hosts. When most of the traffic is between nodes that are not on the same | link, this is very efficient. When most of the traffic is between hosts on the same link (client-server), the extra redirect packets | will be infrequent. 2.3. Host Discovery | When a host or router needs the location of a target host on the same | link, it sends a media multicast of the original data packet, followed by a media multicast solicitation for the location of the host. The target node issues an advertisement which indicates its current reachability. This removes the burden of maintaining a queue of datagrams waiting | media address information, and eliminates latency in forwarding. When most of the traffic is between hosts on the same link (client- | Simpson expires in six months [Page 10] DRAFT SIPP Neighbor Discovery March 1994 server), the extra solicitation and advertisement packets will be rare. 2.4. Mobility | In addition to their function over wired links, the Router Discovery | messages are used to provide beaconing in wireless mobile | environments. The messages themselves contain sufficient additional | information to select a foreign agent for service, and to solve the | "half link" problem. | Other aspects of mobility, such as registration and caching, are | discussed in a companion document. | 2.5. Auto-configuration | The Router Discovery messages are also used to determine the | cluster-prefix. | A SIPP local-use unicast address MAY be combined with a cluster | address learned from Router Advertisements to form a routable | address-sequence. | Also, propagation of changes in cluster-prefix are indicated in the | periodic Router Advertisements, allowing automatic changes in node | identification without user reconfiguration. | Other aspects of configuration, such as loading the operating system | and environment, and additional facilities and servers for | registration, are beyond the scope of this document. | Simpson expires in six months [Page 11] DRAFT SIPP Neighbor Discovery March 1994 3. Router Solicitation Every SIPP node MUST implement Router Solicitation. When any node starts up, it MUST send the Where-Are-You Router Solicitation to prompt the advertisement of neighboring routers. If (and only if) no advertisements from neighboring routers are forthcoming, the node MAY retransmit the Where-Are-You a small number of times, but then MUST desist from sending more solicitations. Any routers that subsequently start up, or that were not discovered because of packet loss or temporary link partitioning, are eventually discovered by reception of their periodic (unsolicited) advertisements. Links that suffer high packet loss rates or frequent partitioning are accommodated by increasing the rate of router advertisements, rather than increasing the number of solicitations that hosts are permitted to send. 3.1. Constants MAX_SOLICITATIONS 3 transmissions MAX_SOLICITATION_DELAY 1 second ROUTER_SOLICITATION_INTERVAL 3 seconds 3.2. Implementation Details The Router Solicitation is sent to the all-routers multicast, with the scope set to intra-link. | A SIPP node is required to transmit up to MAX_SOLICITATIONS Where- Are-You messages from any of its interfaces after any of the following events: - The interface is initialized at system startup time. - The interface is reinitialized after a temporary interface failure or after being temporarily disabled by system management. - A router has its forwarding capability turned off by system management. Simpson expires in six months [Page 12] DRAFT SIPP Neighbor Discovery March 1994 If a node chooses to send a solicitation after one of the above events, it should delay transmission for a random amount of time between 0 and MAX_SOLICITATION_DELAY. This serves to alleviate congestion when many nodes start up on a link at the same time, such as might happen after recovery from a power failure. It is recommended that nodes include some unique value (such as one of their interface or link-layer identifiers or addresses) in the seed used to initialize their pseudo-random number generators. Although the randomization range is specified in units of seconds, the actual randomly-chosen value should not be in units of whole seconds, but rather in units of the highest available timer resolution. The small number of retransmissions of a solicitation, which are permitted if no advertisement is received, should be sent at | intervals of ROUTER_SOLICITATION_INTERVAL seconds without further randomization. Upon receiving a valid Router Advertisement subsequent to one of the above events, the node MUST NOT send any solicitation on that interface (even if no solicitation has been sent yet) until the next time one of the above events occurs. 3.3. Validity Check | A non-router MUST silently discard any received Router Solicitation messages. A router MUST silently discard any received Router Solicitation messages that do not satisfy the following validity checks: - Version number is correct. - ICMP Checksum is correct. - ICMP length (derived from the payload length) is 16 or more octets. - For interfaces which are not point-to-point links, the Media- Access extension MUST be present. The SIPP Source may have any unicast value, including zero. If the identifying-address does not match one of the router's own identifying-addresses on the arrival interface, under the cluster- | prefix associated with that identifying-address, the sender may be Simpson expires in six months [Page 13] DRAFT SIPP Neighbor Discovery March 1994 considered a foreign node. The location of every reachable foreign node is maintained separately within the router. Simpson expires in six months [Page 14] DRAFT SIPP Neighbor Discovery March 1994 4. Sending Router Advertisements Every SIPP router MUST implement Router Advertisements. The router advertisements include such important information as a media address for the router, other cluster-prefixes directly | accessible through the router, services available through the router, and neighboring routers heard. Identifying-Addresses Each router advertisement includes one or more identifying-address fields. These indicate the identifying-addresses which are presently in use for the router. Prefix Size Each advertised identifying-address includes a prefix-size field. The value ranges from 0 to 62, and indicates the number of bits in the Identifier which define the cluster-prefix for the link. A | value of zero indicates an end-point identifying-address. When the value is not zero, the identifying-address may be used to | discern cluster-prefix mapping. If all advertised prefix-size values are zero, then prefix routing | is not in use on that link. Preference Each advertised identifying-address includes a preference field. This is used by a host to choose a default router for the first- hop, when the host has not yet been redirected or configured to use a specific router for a particular destination. The host is expected to choose from those routers that have the highest preference level for the best cluster-prefix match. When | there is no match, or prefix routing is not in use, the preference | value is used alone. An administrator can configure router preference levels to encourage or discourage the use of particular routers as the default first-hop. The use of separate preferences per cluster- | prefix allows the choice of different routers for each prefix, when there are multiple prefixes in use for the same link. This may be useful where multiple organizations share resources. The preference value is not the same as the "metric" used in many routing protocols. It is used only by hosts in determining the Simpson expires in six months [Page 15] DRAFT SIPP Neighbor Discovery March 1994 default first-hop, rather than by routers in choosing a link for transit traffic. The values are not additive. The range of values is smaller, and a higher value indicates a higher preference. It should be understood that preference levels learned from router advertisements do not affect any node's cached route entries. For example, if a node has been redirected to use a particular router to reach a specific destination, it continues to use that router for that destination, even if it discovers another router identifying-address with a higher preference level. Preference levels influence the choice of router only for a destination for which there is no cached or configured route, or whose cached route points to a router that is subsequently determined to be unreachable. 4.1. Constants MAX_INITIAL_ADVERTISEMENTS 3 transmissions MAX_INITIAL_ADVERT_INTERVAL 16 seconds MAX_RESPONSE_DELAY 2 seconds 4.2. Configuration A router MUST allow the following variables to be configured by system management. Default values are specified which make it unnecessary to re-configure these variables in most cases. For each interface: MaxAdvertisementInterval The maximum time (in seconds) allowed between sending router advertisements from the interface. Must be no less than 4 seconds and no greater than 1800 seconds. Default: 600 seconds MinAdvertisementInterval The minimum time (in seconds) allowed between sending unsolicited router advertisements from the interface. Must be no less than 1 Simpson expires in six months [Page 16] DRAFT SIPP Neighbor Discovery March 1994 second and no greater than MaxAdvertisementInterval. Default: 0.75 * MaxAdvertisementInterval AdvertisementLifetime The value (in seconds) to be placed in the Lifetime field of router advertisements sent from the interface. Must be no less than MaxAdvertisementInterval and no greater than 9000 seconds. Default: 3 * MaxAdvertisementInterval For each of the identifying-addresses of each interface: Advertise A flag indicating whether or not the identifying-address is to be advertised. Default: TRUE PreferenceLevel The preferability of the interface as a default router choice, relative to other router interfaces serving the same cluster- | prefix on the same link. Values are in the range 0 to 255. Higher values mean more preferable. The minimum value zero is reserved to indicate that the identifying-address, even though it may be advertised, is not to be used by neighboring hosts as a default router address. The maximum value 255 is reserved to indicate that the preference was locally configured, and not learned through advertisments. Default: 128 It is useful to configure an identifying-address with a preference level of zero (rather than simply setting its Advertise flag to FALSE) when advertisements are being used for "black hole" detection. In particular, a router that is to be used to reach only specific destinations could advertise a preference level of zero (so that neighboring hosts will not use it as a default router for reaching arbitrary destinations) and a non-zero lifetime (so that neighboring hosts that have been redirected or configured to use it can detect its failure by timing out the reception of its advertisements). It has been suggested that, when the preference level of an Simpson expires in six months [Page 17] DRAFT SIPP Neighbor Discovery March 1994 identifying-address has not been explicitly configured, a router could set it according to the metric of the router's "default route" (if it has one), rather than defaulting as suggested above. Thus, a router with a better metric for its default route would advertise a higher preference level for its identifying-address. (Note that routing metrics that are encoded such that "lower is better" would have to be inverted before being used as preference levels in router advertisement messages.) Such a strategy might reduce the amount of redirect traffic on some links by making it more likely that the host's first choice for reaching an arbitrary destination is also the best choice. On the other hand, redirect traffic is rarely a significant load on a link, and there are some cases where such a strategy would result in more redirect traffic (on links from which the most frequently chosen destinations are best reached via routers other than the one with the best default route). Also, since the routing algorithms learn of neighboring routers from the advertisements, and the default routes are learned from the routing algorithms, the calculated preference may be unstable from time to time. This document makes no recommendation concerning this issue, and implementors are free to try such a strategy, as long as they also support static configuration of preference levels as specified above. 4.3. Implementation Details The Router Advertisement is sent to the all-nodes multicast, with the scope set to intra-link. | The term "advertising interface" refers to any functioning and enabled interface that has at least one identifying-address whose configured Advertise flag is TRUE. From each advertising interface, the router MUST transmit periodic I-Am-Here messages. CONTROVERSIAL: A router MAY proxy for the identifers of other nodes, using the Other-Identifier extension. This SHOULD only be used when the router is translating to another internetwork protocol format. | The advertisements are not strictly periodic. The interval between subsequent transmissions is randomized to reduce the probability of synchronization with the advertisements from other routers on the same link. This is done by maintaining a separate transmission Simpson expires in six months [Page 18] DRAFT SIPP Neighbor Discovery March 1994 interval timer for each advertising interface. Each time an advertisement is sent from an interface, that interface's timer is reset to a uniformly-distributed random value between the configured MinAdvertisementInterval and MaxAdvertisementInterval. Expiration of the timer causes the next advertisement to be sent, and a new random value to be chosen. It is recommended that routers include some unique value (such as one of their interface or link-layer addresses) in the seed used to initialize their pseudo-random number generators. Although the randomization range is configured in units of seconds, the actual randomly-chosen values should not be in units of whole seconds, but rather in units of the highest available timer resolution. For the first few advertisements sent from an interface (up to MAX_INITIAL_ADVERTISEMENTS), if the randomly chosen interval is greater than MAX_INITIAL_ADVERT_INTERVAL, the timer should be set to MAX_INITIAL_ADVERT_INTERVAL instead. Using this smaller interval for the initial advertisements increases the likelihood of a router being discovered quickly when it first becomes available, in the presence of possible packet loss. An interface may become an advertising interface at times other than system startup, as a result of recovery from an interface failure or through actions of system management such as: - enabling the interface, if it had been administratively disabled and it has one or more identifying-addresses whose Advertise flag is TRUE, - enabling SIPP forwarding capability (changing the node from a host to a router), when the interface has one or more identifying- addresses whose Advertise flag is TRUE, - setting the Advertise flag of one or more of the interface's identifying-addresses to TRUE (or adding a new identifying-address with a TRUE Advertise flag), when previously the interface had no identifying-address whose Advertise flag was TRUE. In such cases, the router must commence transmission of periodic advertisements on the new advertising interface, limiting the first few advertisements to intervals no greater than MAX_INITIAL_ADVERT_INTERVAL. In the case of a host becoming a router, the node must also join the all-routers multicast group on all interfaces on which the router supports multicast (whether or not they are advertising interfaces). An interface MAY also cease to be an advertising interface, through Simpson expires in six months [Page 19] DRAFT SIPP Neighbor Discovery March 1994 actions of system management such as: - shutting down the node, | - administratively disabling the interface, - disabling SIPP forwarding capability (changing the node from a router to a host), - setting the Advertise flags of all of the interface's identifying-addresses to FALSE. In such cases, the router MUST transmit a final multicast advertisement on the interface, identical to its previous transmission, but with a Lifetime field of zero. In the case of a router becoming a host, the node must also depart from the all- | routers multicast group on all interfaces on which the router supports multicast (whether or not they had been advertising interfaces). When the Advertise flag of one or more of an interface's identifying-addresses are set to FALSE by system management, but there remain other identifying-addresses on that interface whose Advertise flags are TRUE, the router SHOULD send a single multicast advertisement containing only those identifying-addresses whose Advertise flags were set to FALSE, with a Lifetime field of zero. In addition to the periodic unsolicited advertisements, a router MUST send advertisements in response to valid Router Advertisements or Router Solicitations received on any of its advertising interfaces. If the advertisement or solicitation does not contain any System- Heard extension, and the time since the previous advertisement is greater than MAX_INITIAL_ADVERT_INTERVAL, the router MUST multicast an advertisement from that interface. Whenever these response advertisements are sent, the advertisement MUST be delayed for a small random interval not greater than MAX_RESPONSE_DELAY, in order to prevent synchronization with other responding routers, and to allow multiple closely-spaced solicitations to be answered with a single advertisement. The interface's interval timer is reset to a new random value, as with unsolicited advertisements. 4.4. Validity Check All nodes MUST silently discard any received Router Advertisement Simpson expires in six months [Page 20] DRAFT SIPP Neighbor Discovery March 1994 messages that do not satisfy the following validity checks: - Version is correct. - ICMP Checksum is correct. - ICMP length (derived from the payload length) is 16 or more octets. - At least one Routing-Information extension MUST be present. - For interfaces which are not point-to-point links, the Media- Access extension MUST be present. Simpson expires in six months [Page 21] DRAFT SIPP Neighbor Discovery March 1994 5. Processing Router Advertisements Each router saves the information contained in the advertisements, in | order to respond to future requests. Any other action on receipt of such messages by a router (for example, as part of a "peer discovery" process) is beyond the scope of this document. Each host saves the information contained in the advertisements, in | order to determine the next-hop when sending datagrams. Hop determination is elaborated in the "Sending Datagrams" chapter. 5.1. Configuration | 5.1.1. Router List | Host Requirements -- Communication Layers [1], Section 3.3.1.6, | specifies that each host must support a configurable list of default routers. The purpose of the router advertisement messages is to | eliminate the need to configure that list. | Each entry in the list contains (at least) the following configurable variables: RouterAddress An identifying-address of a default router. Default: (none) Prefix Size | Each identifying-address associated with a router includes a | prefix-size field. The value ranges from 0 to 62, and indicates | the number of bits in the identifying-address which define the | cluster-prefix for the link. A value of zero indicates an end- | point identifying-address. When the value is not zero, the | identifying-address may be used to discern cluster-prefix mapping. | If all associated prefix-size values are zero, then prefix routing | is not in use on that link. | Default: 0 | PreferenceLevel The preferability of the RouterAddress as a default router choice, Simpson expires in six months [Page 22] DRAFT SIPP Neighbor Discovery March 1994 relative to other router interfaces serving the same cluster- | prefix on the same link. Host Requirements does not specify how | this value is to be encoded. The values used here are defined as in Router Advertisements. Values are in the range 0 to 255. Higher values mean more preferable. The minimum value zero is reserved to indicate that the identifying-address, even though it may be advertised, is not to be used by neighboring hosts as a default router address. The maximum value 255 is reserved to indicate that the preference was locally configured, and not learned through advertisments. Default: 255 Default routers and preference levels SHOULD NOT be configured | manually. On links for which router discovery is administratively | disabled, it MAY continue to be necessary to configure the default | router list in each host. 5.1.2. Address List | Each node requires at least one identifying-address. | Each identifying-address is bound to one or more interfaces, as | described in [SIPP-ROAD]. | Each entry in the list contains (at least) the following configurable | variables: | Identifying-Address The identifying-address which is presently in use for the node. | Default: None | Prefix Size Each identifying-address associated with a link interface includes | a prefix-size field. The value ranges from 0 to 62, and indicates | the number of bits in the identifying-address which define the | cluster-prefix for the link. A value of zero indicates an end- | point identifying-address. When the value is not zero, the | identifying-address may be used to discern cluster-prefix mapping. | If all associated prefix-size values are zero, then prefix routing | is not in use on that link. | Simpson expires in six months [Page 23] DRAFT SIPP Neighbor Discovery March 1994 Default: 0 LifeTime | The value (in seconds) for the time that the identifying-address | is associated with an interface. | Default: 0 | The cluster-prefix(es) for a host interface SHOULD NOT be configured | manually. | The cluster-prefix(es) for a router interface SHOULD be configured | manually, until such time in the future that an automatic algorithm | is developed. | 5.2. Implementation Details To process an Router Advertisement, the node scans the list of | extensions in it. 5.2.1. Media-Access If a Media-Access extension is present, the router list is updated with the location information. The Media-Access extension MAY appear anywhere in the list of extensions, but is most likely at the | beginning or end. 5.2.2. Change-Identifier Change-Identifier extensions MUST preceed Routing-Information extensions. - If the prefix-size is zero, the identifying-address indicates the | change of a single node, without affecting other nodes on that | link. - If the prefix-size is not zero, the identifying-address indicates | the change of cluster-prefix for all nodes on that link. | - The identifying-address and prefix-size are compared against any | identifying-addresses defined for the node. If there is a match, | Simpson expires in six months [Page 24] DRAFT SIPP Neighbor Discovery March 1994 a new identifying-address is associated with the node. - If the new identifying-address is not already present in the | receiving interface list, a new entry is added to the list, | containing the identifying-address, prefix-size, and the Lifetime | value from the advertisement. - If the new identifying-address is already present in the receiving | interface list as a result of a previously-received advertisement, | its LifeTime is reset to the value in the newly-received | advertisement. - If the new identifying-address is already present in the receiving | interface list as a result of static configuration, no change is made. There is no LifeTime associated with a configured | identifying-address. The node MUST continue to accept datagrams destined for the old | identifying-address, until such time as all stimulus for maintaining the old identifying-address has expired. This implies that the node | will maintain a LifeTime for most sources of identifying-addresses, such as DNS records and dynamic configuration. 5.2.3. Routing-Information Routing-Information extensions MUST preceed Other-Identifier extensions. - If the prefix-size is not zero, the identifying-address and prefix-size are compared against any identifying-addresses defined | for the node. If there is a match, the identifying-address is | associated with the interface on which the message was received, | and the prefix-size is set to the advertised prefix-size. - If the identifying-address is not already present in the router list, a new entry is added to the list, containing the identifying-address along with its accompanying preference level, | and the Lifetime value from the advertisement. - If the identifying-address is already present in the router list as a result of a previously-received advertisement, its preference level is updated and its LifeTime is reset to the value in the | newly-received advertisement. - If the identifying-address is already present in the router list as a result of static configuration, no change is made to its Simpson expires in six months [Page 25] DRAFT SIPP Neighbor Discovery March 1994 preference level. There is no LifeTime associated with a | configured identifying-address. Note that any router identifying-address acquired from the "Gateway" subfield of the vendor extensions field of a BOOTP packet [11] are considered to be configured identifying-addresses; they are assigned the default preference level of 255, and they do | not have an associated LifeTime. Note further that any identifying-address found in the "giaddr" field of a BOOTP packet [3] identifies a BOOTP forwarder which is not necessarily a SIPP router; such an identifying-address should not be installed in the default router list. To limit the storage needed for the default router list, the host MAY choose not to store all of the router identifying-addresses discovered via advertisements. The host SHOULD discard those identifying-addresses with lower preference levels in favor of those with higher levels. It is desirable to retain more than one default router in the list; if the current choice of default router is discovered to be down, the host may immediately choose another default router without having to wait for the next advertisement to arrive. Any router identifying-address advertised with a preference level of zero is not to be used by the host as default router identifying- address. Such an identifying-address may be omitted from the default router list, unless its LifeTime is being used as a "black-hole" | detection mechanism. 5.2.4. Other-Identifier The Other-Identifier extension is used to indicate identifying- | addresses which have no effect on the interface cluster-prefix. - If the identifying-address is not already present in the router list, a new entry is added to the list, containing the identifying-address, the preference level set to zero, and the | Lifetime value from the advertisement. - If the identifying-address is already present in the router list as a result of a previously-received advertisement, and its preference level is zero, its LifeTime is reset to the value in | the newly-received advertisement. Simpson expires in six months [Page 26] DRAFT SIPP Neighbor Discovery March 1994 - If the identifying-address is already present in the router list as a result of static configuration, no change is made to its preference level. There is no LifeTime associated with a | configured identifying-address. To limit the storage needed for the default router list, the host MAY choose not to store all of the other identifying-addresses discovered via advertisements. The most preferred router is used for unknown identifying-addresses, and it will send a redirect when appropriate. 5.2.5. System-Heard The use of the System-Heard extension is described in a future Mobile | Discovery document. 5.2.6. Service-Information The use of the Service-Information extension is described in a future | Service Discovery document. Simpson expires in six months [Page 27] DRAFT SIPP Neighbor Discovery March 1994 6. Sending Datagrams The internetwork-layer chooses the next hop for each datagram sent. | If the destination can be readily determined to be on an attached | link, the datagram is sent directly to the destination. Otherwise, it is sent to a router. 6.1. Constants | GENERAL_SOLICITATION_INTERVAL 3 seconds | 6.2. Route Cache To efficiently route a series of datagrams to the same destination, | each node MUST keep a "route cache" of mappings to destinations. The | node 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. 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 an attached link. This is described in the "Local/Remote Decision" section which follows. (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 an attached link, | the media address is solicited. A new cache entry is made indicating an unknown media address, with a limited LifeTime, to inhibit sending of repeated solicitations. Each route cache entry needs to include the following items. Simpson expires in six months [Page 28] DRAFT SIPP Neighbor Discovery March 1994 (1) LifeTime (2) Next-hop interface (when a node is multi-homed) | (3) Next-hop media address (4) Destination SIPP identifying-address (5) Destination cluster-prefix size | (6) Source SIPP identifying-address (7) Flow number While scanning or making changes to the route cache entries, whenever | the LifeTime expires in any entry that was created as a result of a | received advertisement, that entry is discarded. | Field (4) MAY be the full SIPP identifying-address of the destination, or only the destination cluster number. This is | determined by the cluster-prefix size in (5). Field (7) SHOULD be included. | DISCUSSION: Each route cache entry defines the end-points 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 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 destinations alone, or allow both node and cluster addresses. | Those who favor the use of only node identifiers argue that: (1) Redirect messages will generally result in entries keyed on nodes. The simplest and most general scheme would be to only use node identifiers. (2) The internetwork layer may not always know the prefix-size | for a cluster address in a complex environment. (3) The use of only node identifiers allows the destination to be used as a pure 64-bit number, which may allow the Simpson expires in six months [Page 29] DRAFT SIPP Neighbor Discovery March 1994 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 nodes and clusters 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. | IMPLEMENTATION: The cache needs to be large enough to include entries for the maximum number of destinations 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. A static route is typically a particular preset mapping for destination host or cluster into a particular next-hop router; it might also depend on the Type-of-Service. Static routes would be setup by system administrators to override the normal automatic routing mechanism, and handle exceptional situations. However, any static routing information is a potential source of failure as configurations change or equipment fails. Although the route cache, the lists of default routers, and a | table of static routes are described as conceptually distinct, in practice they may be combined into a single "routing table" data structure. Simpson expires in six months [Page 30] DRAFT SIPP Neighbor Discovery March 1994 6.3. Local/Remote Decision | To decide if the destination is on an attached link, 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) If no Router Advertisements have been heard, then the | destination is assumed to be on an attached link. The | destination is located as described in the "Media Address | Determination" section which follows. (c) If one or more Router Advertisements have been heard, then the | datagram is sent to a single preferred router, as described in | the "Router Selection" section which follows. The router will | send a Redirect when the destination is on the same link. | (d) For a multi-homed node, when one or more Router Advertisements | have been heard on some interfaces, but no Router | Advertisements have been heard on other interfaces, the | datagram is sent to both the preferred router, and to those | interfaces without routers. This allows a node to continue | operation in the presence of private or partitioned links. The | correct interface will be learned through the advertisements of | the target node. Every host MUST operate correctly in a minimal 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 link. | 6.4. Media Address Determination | When the media address for a destination is unknown, the following procedure is used: (a) When a node is multi-homed, the datagram is sent on those | interfaces which have not discovered the presence of a router, | and for which a peer entity is unknown. (b) If any interface has no broadcast capability (a point-to-point link), and the peer entity is unknown, the datagram is sent on that interface. (c) If a virtual interface has no broadcast capability (a Frame- Relay or X.25 link), the datagram is duplicated on each virtual Simpson expires in six months [Page 31] DRAFT SIPP Neighbor Discovery March 1994 circuit for which there is no known peer entity, as if they | were each a separate point-to-point interface on a multi-homed | node. (d) If an interface has no multicast capability, the datagram is sent as a link-layer broadcast. The SIPP Destination is unchanged. (e) For an interface with multicast capability, the datagram is sent as a link-layer multicast. The SIPP Destination is * unchanged. | The link-layer multicast address used is the exclusive-or of | every octet of the SIPP Destination, added to the base | solicited-nodes multicast. This distributes the processing | load among 1/256 of the nodes, even when the nodes are not | attached to a prefix routed link. (f) When there is already an entry in the route cache for an * unknown media address, no further solicitations are sent until the cache entry expires. | (g) When there is no entry in the route cache, a Where-Are-You | General Solicitation is sent, utilizing the same SIPP | Destination as the datagram. The same link-layer addressing | rules of (a) to (e) apply. A route cache entry is added with a | LifeTime of GENERAL_SOLICITATION_INTERVAL. On receipt of a unicast datagram from a unicast, broadcast or | multicast media address, if the SIPP Destination does not match any | SIPP identifying-address of the node, the datagram is silently | discarded. On receipt of a Where-Are-You General Solicitation, the target node | sends an I-Am-Here General Advertisement to the all-nodes multicast, | with the scope set to intra-link. On receipt of an I-Am-Here General Advertisement, all nodes which | have a route cache entry for the SIPP Source update the cache entry | with the current LifeTime and media address, and any other pertinent | field values implemented. 6.5. Router Selection | To decide which router to send a datagram, the following procedure is used: Simpson expires in six months [Page 32] DRAFT SIPP Neighbor Discovery March 1994 (a) Cluster-prefixes are learned from the Routing-Information | extension of Router Advertisements. The prefix-size is the | number of valid bits in the cluster-prefix. | (b) The SIPP Source field of the datagram is compared to the list | of cluster-prefixes in the Router List. (c) If a cluster-prefix exactly matches the Source prefix extracted | by the same prefix-size, then that router is one of the preferred routers for that Source. The node selects the highest preference value of those matching routers. (d) If there are no matching cluster-prefixes, then there is no | preferred router for the Source. The node selects the highest | preference value amoung all routers. (e) If that router is not the best next hop to the destination, | that router will forward the datagram to the best next-hop, and return a Redirect message to the sending node. (f) When the sending node receives a Redirect, it updates the | next-hop in the appropriate route cache entry, so that later datagrams to the same destination will go directly to the best next-hop. Since the cluster-prefix appropriate to the Destination address is | generally not known, a Network Redirect message SHOULD be treated | identically to a Host Redirect message. That is, the cache entry for | the Destination (only) would be updated (or created when an entry for | that node did not exist) for the new router. | DISCUSSION: This recommendation is to protect against routers that erroneously | send Network Redirects for a prefix routed link, in violation of the router requirements. (Do we still have the Network | Redirect???) 6.6. Dead Node Detection | The internetwork-layer MUST be able to detect the failure of a node | that is listed in its route cache. Each cache entry has a LifeTime, which is obtained through the solicitation and advertisement messages. When an entry expires, the routing availability of the destination MUST be redetermined as if no prior entry had existed. Simpson expires in six months [Page 33] DRAFT SIPP Neighbor Discovery March 1994 Negative "advice" from other layers, such as excessive retransmissions by a transport-layer protocol, or a down indication from a link-layer, SHOULD be used to invalidate a cache entry. Positive "advice" from other layers MUST NOT extend the LifeTime of a cache entry. ICMP Echo "pings" MUST NOT be used to actively check a cache entry. Simpson expires in six months [Page 34] DRAFT SIPP Neighbor Discovery March 1994 A. Configuration Summary | Routers | A router requires at least one identifying-address to be | configured. For each interface, a prefix-size is assigned to each | identifying-address. Optionally, other values MAY be altered from their defaults, such | as preference and advertisement lifetime. | Optionally, routing protocols MAY require additional values to be | configured, such as metric and priority. Such functions are | beyond the scope of this document. | Hosts | Most hosts need no prior configuration. | A node attached to a multi-access media creates a local-use | unicast address from the media address. | A node attached to a point-to-point media (using the Point-to- | Point Protocol [RFC-1568]) can be dynamically assigned either a | global or local unicast address. | Other nodes require configuration of an identifying address as | described in the section "Address List". | When a router is present, a local-use unicast address MAY be | combined with a cluster address learned from Router Advertisements | to form a routable address-sequence. | When a Domain Name Service is available, address-sequences of | longer than one cluster can be learned. Such functions are beyond | the scope of this document. | Simpson expires in six months [Page 35] DRAFT SIPP Neighbor Discovery March 1994 Security Considerations References [1] [2] Acknowledgments 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 36] DRAFT SIPP Neighbor Discovery March 1994 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 415-336-2082 hinden@Eng.Sun.com Author's Address Questions about this memo can also be directed to: William Allen Simpson Daydreamer Computer Systems Consulting Services 1384 Fontaine Madison Heights, Michigan 48071 Bill.Simpson@um.cc.umich.edu bsimpson@MorningStar.com Simpson expires in six months [Page 37] DRAFT SIPP Neighbor Discovery March 1994 Table of Contents 1. Introduction .......................................... 1 1.1 Goals ........................................... 1 1.2 Criteria ........................................ 2 1.3 Historic Methods ................................ 6 2. Solution Overview ..................................... 8 2.1 Packets ......................................... 8 2.1.1 Solicitations ................................... 8 2.1.2 Advertisements .................................. 8 2.1.3 LifeTime ........................................ 8 2.1.4 Extensions ...................................... 9 2.2 Router Discovery ................................ 9 2.3 Host Discovery .................................. 10 2.4 Mobility ........................................ 11 | 2.5 Auto-configuration .............................. 11 | 3. Router Solicitation ................................... 12 3.1 Constants ....................................... 12 3.2 Implementation Details .......................... 12 3.3 Validity Check .................................. 13 4. Sending Router Advertisements ......................... 15 4.1 Constants ....................................... 16 4.2 Configuration ................................... 16 4.3 Implementation Details .......................... 18 4.4 Validity Check .................................. 20 5. Processing Router Advertisements ...................... 22 5.1 Configuration ................................... 22 5.1.1 Router List ..................................... 22 | 5.1.2 Address List .................................... 23 | 5.2 Implementation Details .......................... 24 | 5.2.1 Media-Access .................................... 24 5.2.2 Change-Identifier ............................... 24 5.2.3 Routing-Information ............................. 25 5.2.4 Other-Identifier ................................ 26 5.2.5 System-Heard .................................... 27 5.2.6 Service-Information ............................. 27 6. Sending Datagrams ..................................... 28 6.1 Constants ....................................... 28 | 6.2 Route Cache ..................................... 28 6.3 Local/Remote Decision ........................... 31 6.4 Media Address Determination ..................... 31 6.5 Router Selection ................................ 32 Simpson expires in six months [Page ii] DRAFT SIPP Neighbor Discovery March 1994 6.6 Dead Node Detection ............................. 33 APPENDICES ................................................... 35 | A. Configuration Summary ................................. 35 | SECURITY CONSIDERATIONS ...................................... 36 REFERENCES ................................................... 36 ACKNOWLEDGEMENTS ............................................. 36 CHAIR'S ADDRESS .............................................. 37 AUTHOR'S ADDRESS ............................................. 37 Simpson expires in six months [Page iii]