Internet DRAFT - draft-ietf-sip-discovery
draft-ietf-sip-discovery
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
