Network Working Group W A Simpson Internet Draft Daydreamer expires in six months December 1993 SIPP Neighbor Discovery draft-ietf-sip-discovery-03.txt 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. Abstract 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 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 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 Mobility The same mechanisms which support wired identification and location are used to provide mobile beaconing and roaming within clusters. 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 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 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 retained. Auto-configuration The connection procedures for a configuring a new system 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 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. 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. 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 moving. 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 choices. Simplicity 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 ARP 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 techniques. 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 node. 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 router. 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 network. 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 interfaces. 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 unchanged. (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 unchanged. (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 solicitations. 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. DISCUSSION: 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. IMPLEMENTATION: 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 structure. 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 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 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 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 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