Network Working Group W A Simpson Internet Draft Daydreamer expires in six months September 1994 IPv6 Neighbor Discovery -- Design Requirements draft-simpson-ipv6-discovery-req-00.txt Status of this Memo This document is a submission to the IPng Working Group of the Internet Engineering Task Force (IETF). Comments SHOULD be submitted to the ipng@sunroof.eng.sun.com mailing list. Distribution of this memo is unlimited. 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 requirements for identification of and forwarding to adjacent IPv6 nodes. Simpson expires in six months [Page i] DRAFT IPv6 Discovery Requirements September 1994 1. Introduction 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 IPv6, 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 IPv6 are required to be distinguishable from previous IP versions. This is an opportunity to design a uniform and coherent method for accomplishing these goals. 2. Goals 2.1. Find Neighbors Each IPv6 node needs to determine the availability of other IPv6 nodes as demand for communication occurs. Each IPv6 host needs to detect the presence of available IPv6 routers. 2.2. Redirection A redirect is used when a packet could be sent more directly to the IPv6 next-hop, or to indicate that another IPv6 router should be used for forwarding specific packets. 2.3. 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. Simpson expires in six months [Page 1] DRAFT IPv6 Discovery Requirements September 1994 2.4. Learn Routing-Prefix When prefix routing is in use, it is necessary to determine the prefix(es) for a link. Multiple cluster-prefixes need to be supported. 2.5. Change Routing-Prefix When a cluster-prefix changes, it is necessary to update the node IPv6 Addresses. 2.6. Mobility The same mechanisms which support wired identification and location are used to provide mobile beaconing and roaming. 3. 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. 3.1. Multicast support All IPv6 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 IPv6 Header, this technique will work even when using link-layer broadcast, or link-layer unicast to each recipient. Older nodes will discard IPv6 Headers at the internetwork-layer. Simpson expires in six months [Page 2] DRAFT IPv6 Discovery Requirements September 1994 3.2. 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. Also, per packet processing costs are much larger than other transmission costs. On bandwidth-bound congested links, the increased per frame overhead for contention resolution dominates throughput considerations. On processor-bound saturated systems, the packet processing is likely to be delayed, or the packet dropped altogether. 3.3. 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 can 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 is retained. 3.4. Auto-configuration The connection procedures for a configuring a new node SHOULD be Simpson expires in six months [Page 3] DRAFT IPv6 Discovery Requirements September 1994 reduced to the minimal set of "plug it in, turn on the power, and run". - Each node self-assigns an identifier, usually within the number space assigned to one or more links to which it is attached. - Each node discovers the routers attached to each link, so that it can exchange packets with remote nodes. - Each 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 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 determined. 2) Random identifier assignments MUST 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 MUST be transparent to the human users. In particular, renumbering for changes of providers, and assignment of alias identifiers as a Mobile Node moves, MUST be automatic. 4) Users MUST NOT be concerned with cluster-prefixes, or the routing methods extant in the local administrative domain. When used, such prefixes MUST be automatically determined, and dynamic changes MUST propagate automatically. Simpson expires in six months [Page 4] DRAFT IPv6 Discovery Requirements September 1994 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. 3.5. 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. 3.6. 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. 3.7. 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. Discovery mechanisms 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. Simpson expires in six months [Page 5] DRAFT IPv6 Discovery Requirements September 1994 3.8. 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 Nodes continue to use their native IPv6 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. 3.9. Simplicity The design MUST reduce the number of packet types which are be supported in a pure IPv6 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. 4. Historic Methods 4.1. 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. Simpson expires in six months [Page 6] DRAFT IPv6 Discovery Requirements September 1994 Worse, many current ARP implementations drop the original datagram while waiting for resolution. This can happen at each successive hop, causing tremendous delay and retransmission. 4.2. 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. 4.3. ES-IS Hellos The ISO solution (ES-IS) addresses some of these problems. Each host and router sends Hellos on a periodic basis. 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. Every router MUST remember all of the media addresses for all of the other nodes on each attached link. In many implementations, every host also remembers all of the other nodes on each attached link. It does not provide a comprehensive solution to self-identification, mobility, black-hole detection, or media independence. 4.4. 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 Simpson expires in six months [Page 7] DRAFT IPv6 Discovery Requirements September 1994 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 8] DRAFT IPv6 Discovery Requirements September 1994 5. Solution Overview This design is a combination of the best features of the preceding techniques. The process uses 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. 5.1. Solicitations A solicitation is used to find other nodes, and associated resources and services. Router solicitations are sent when a node interface is initialized. General solicitations are sent when one node is ready to communicate with another particular node. 5.2. Advertisements An advertisement is sent in answer to the solicitation. Advertisements are also sent on a periodic basis to indicate special resources, particularly the presence of routers. Periodic advertisements from a few commonly requested nodes result in less traffic than repeated solicitations and advertisements from many nodes. 5.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 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. Simpson expires in six months [Page 9] DRAFT IPv6 Discovery Requirements September 1994 The lifetime is also set when a solicitation is sent, to prevent the sending of repeated solicitations. 5.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 advertisement and redirect packets, a further query and response can be avoided entirely. This also 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. 6. 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 unicast 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- server), the extra solicitation and advertisement packets will be rare. 7. 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 Router Simpson expires in six months [Page 10] DRAFT IPv6 Discovery Requirements September 1994 Solicitation and Advertisement 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 Router Solicitation to prompt for immediate Router Advertisements, rather than waiting for the next periodic advertisement to arrive. Each router periodically sends a Router Advertisement from each of its interfaces. Nodes discover the location of their 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 in 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. Simpson expires in six months [Page 11] DRAFT IPv6 Discovery Requirements September 1994 8. Mobility In addition to their function over wired links, the Router Advertisements 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. 9. Self-configuration The Router Advertisements are also used to determine the cluster- prefix. An IPv6 local-use unicast address MAY be combined with a cluster- prefix learned from Router Advertisements to form a routable IPv6 Address. 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 12] DRAFT IPv6 Discovery Requirements September 1994 Security Considerations Security issues are not discussed in this memo. Acknowledgements The document was initially composed of 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?). 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 13] DRAFT IPv6 Discovery Requirements September 1994 Table of Contents 1. Introduction .......................................... 1 2. Goals ................................................. 1 2.1 Find Neighbors .................................. 1 2.2 Redirection ..................................... 1 2.3 Resolve Media Address ........................... 1 2.4 Learn Routing-Prefix ............................ 2 2.5 Change Routing-Prefix ........................... 2 2.6 Mobility ........................................ 2 3. Criteria .............................................. 2 3.1 Multicast support ............................... 2 3.2 Reduced net traffic ............................. 3 3.3 Low storage overhead ............................ 3 3.4 Auto-configuration .............................. 3 3.5 Mobility ........................................ 5 3.6 Black hole detection ............................ 5 3.7 Media independence .............................. 5 3.8 Optimal route determination ..................... 6 3.9 Simplicity ...................................... 6 4. Historic Methods ...................................... 6 4.1 ARP ............................................. 6 4.2 ICMP Router Discovery ........................... 7 4.3 ES-IS Hellos .................................... 7 4.4 Media Multicast ................................. 7 5. Solution Overview ..................................... 9 5.1 Solicitations ................................... 9 5.2 Advertisements .................................. 9 5.3 LifeTime ........................................ 9 5.4 Extensions ...................................... 10 6. Host Discovery ........................................ 10 7. Router Discovery ...................................... 10 8. Mobility .............................................. 12 9. Self-configuration .................................... 12 SECURITY CONSIDERATIONS ...................................... 13 ACKNOWLEDGEMENTS ............................................. 13 Simpson expires in six months [Page ii] DRAFT IPv6 Discovery Requirements September 1994 AUTHOR'S ADDRESS ............................................. 13