Network Working Group A. White Internet-Draft A. Williams Expires: August 21, 2002 Motorola February 20, 2002 Unique Identifier Allocation Protocol draft-white-zeroconf-uiap-00.txt Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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 and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on August 21, 2002. Copyright Notice Copyright (C) The Internet Society (2002). All Rights Reserved. Abstract This memo specifies a distributed mechanism for testing the uniqueness of identifiers within a connected collection of devices. The mechanism supports multiple identifier domains, and uses only link-local communication and flooding. White & Williams Expires August 21, 2002 [Page 1] Internet-Draft Unique Identifier Allocation Protocol February 2002 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 4 1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . 4 2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 UIAP Capabilities and Limitations . . . . . . . . . . . . 5 2.1.1 What UIAP Does . . . . . . . . . . . . . . . . . . . . . . 5 2.1.2 What UIAP Doesn't Do . . . . . . . . . . . . . . . . . . . 6 2.2 Domains and Claims . . . . . . . . . . . . . . . . . . . . 6 2.3 Requirements . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Example Protocol Behaviour . . . . . . . . . . . . . . . . 7 2.4.1 Make a Claim . . . . . . . . . . . . . . . . . . . . . . . 7 2.4.2 Receive a Claim-Attempt Message . . . . . . . . . . . . . 8 2.4.3 Forward a Claim-Attempt Message . . . . . . . . . . . . . 10 2.4.4 Receive a Claim-Deny Message . . . . . . . . . . . . . . . 10 2.4.5 Send a Claim-Deny Message . . . . . . . . . . . . . . . . 10 2.4.6 Handle a Simultaneous Claim . . . . . . . . . . . . . . . 11 3. UIAP Implementation . . . . . . . . . . . . . . . . . . . 11 3.1 Device Requirements . . . . . . . . . . . . . . . . . . . 12 3.2 Number Spaces . . . . . . . . . . . . . . . . . . . . . . 12 3.2.1 Describing a Number Space . . . . . . . . . . . . . . . . 12 3.2.1.1 Characteristics of Number Spaces . . . . . . . . . . . . . 13 3.2.1.2 Example Number Spaces . . . . . . . . . . . . . . . . . . 14 3.2.2 Describing a UID Claim . . . . . . . . . . . . . . . . . . 14 3.2.3 Representing UIDs . . . . . . . . . . . . . . . . . . . . 14 3.2.4 Comparing UIDs . . . . . . . . . . . . . . . . . . . . . . 14 4. UIAP Messages . . . . . . . . . . . . . . . . . . . . . . 15 4.1 Common message format . . . . . . . . . . . . . . . . . . 15 4.1.1 Message Types . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Claim-Attempt . . . . . . . . . . . . . . . . . . . . . . 18 4.2.1 Message Format . . . . . . . . . . . . . . . . . . . . . . 18 4.2.2 Claim-Attempt Handling . . . . . . . . . . . . . . . . . . 18 4.2.2.1 Receiving a Claim-Attempt . . . . . . . . . . . . . . . . 18 4.2.2.2 Simultaneous Claim-Attempts . . . . . . . . . . . . . . . 19 4.2.2.3 Other . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.3 Claim-Deny . . . . . . . . . . . . . . . . . . . . . . . . 20 4.3.1 Message Format . . . . . . . . . . . . . . . . . . . . . . 20 4.3.2 Claim-Deny Handling . . . . . . . . . . . . . . . . . . . 20 4.4 Reclaim . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.5 Other Key Concepts . . . . . . . . . . . . . . . . . . . . 21 4.5.1 Floods and Sequence Numbers . . . . . . . . . . . . . . . 21 4.5.2 Claim Lifetime . . . . . . . . . . . . . . . . . . . . . . 22 5. Extensions . . . . . . . . . . . . . . . . . . . . . . . . 22 5.1 Proxy Defense . . . . . . . . . . . . . . . . . . . . . . 22 6. Allocation of Domain Identifiers . . . . . . . . . . . . . 23 6.1 Writing Domain Identifiers . . . . . . . . . . . . . . . . 24 6.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . 24 7. Security Considerations . . . . . . . . . . . . . . . . . 24 White & Williams Expires August 21, 2002 [Page 2] Internet-Draft Unique Identifier Allocation Protocol February 2002 8. IANA Considerations . . . . . . . . . . . . . . . . . . . 25 8.1 UIAP . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 8.2 Domains . . . . . . . . . . . . . . . . . . . . . . . . . 25 9. Other Concerns . . . . . . . . . . . . . . . . . . . . . . 25 10. Table of Constants . . . . . . . . . . . . . . . . . . . . 26 References . . . . . . . . . . . . . . . . . . . . . . . . 26 Authors' Addresses . . . . . . . . . . . . . . . . . . . . 26 A. Acknowledgements . . . . . . . . . . . . . . . . . . . . . 27 B. Intellectual Property . . . . . . . . . . . . . . . . . . 27 Index . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Full Copyright Statement . . . . . . . . . . . . . . . . . 29 White & Williams Expires August 21, 2002 [Page 3] Internet-Draft Unique Identifier Allocation Protocol February 2002 1. Introduction This memo specifies the Unique Identifier Allocation Protocol (UIAP). UIAP is a distributed mechanism for testing the uniqueness of identifiers within a connected collection of devices. UIAP supports multiple domains of identifiers (e.g. network address, host name), and is intended to assist applications wishing to allocate unique identifiers in a network. Two UIAP devices are connected if UIAP packets from one device can reach the other (and vice versa). UIAP devices sharing a network link are connected. UIAP devices on separate links are connected if there are UIAP devices spanning the intermediate links to allow hop- by-hop transmission. UIAP is designed to run over a small-scale network, for example a home or office network. It is not suitable for large or high latency networks. UIAP requires only link local communications protocols. UIAP devices provide packet forwarding between links. Routing support is not required. 1.1 Definitions UIAP: Unique Identifier Allocation Protocol. Site: The set of devices currently connected by UIAP, and the links over which UIAP messages will be sent. The composition of a site may vary over time. A site is bounded by leaf networks and devices which do not forward UIAP packets. Site Boundary: The limit of UIAP for this site. A site boundary could be caused by a leaf network or the presence of a routing device that will not forward UIAP packets. UIAP Device: A networked device running UIAP on at least one interface. UIAP devices with multiple participating interfaces forward UIAP packets as appropriate between those interfaces. UID: A unique identifier; a binary string up to 255 octets in length. UIAP tests the uniqueness of UIDs within a UIAP site and identifier domain. UID Space: A contiguous sequence of one or more UIDs. UIAP can test the uniqueness of a space of identifiers, in addition to single identifiers. White & Williams Expires August 21, 2002 [Page 4] Internet-Draft Unique Identifier Allocation Protocol February 2002 UIAP Domain: A given number space from which UIDs are allocated. Each domain defines the allowed range and semantic meaning of UIDs allocated from that domain. DID: A domain identifier; a binary string, 8 octets in length, representing a domain. Applications will attach semantic meaning to the domain ID and the associated domain. UIAP treats the domain ID as an abitrary identifier; UIAP does not compare UIDs with different domain IDs. Collision: A situation where a UID is not unique within its scope. Merging two sites may cause collisions. UIAP does not monitor for collisions. Device ID: A 64 bit number uniquely identifying a particular UIAP device. Message ID: A 96 bit number, being a combination of the device ID of the originating device and a sequence number, that identifies a particular UIAP message. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119. 2. Overview 2.1 UIAP Capabilities and Limitations 2.1.1 What UIAP Does UIAP offers a service to applications. UIAP will verify that an identifier (or set of identifiers) presented by an application is unique within a site and application space (a domain). If the identifier is unique, UIAP will attempt to defend its uniqueness for a period of time requested by the application. An application that needs a unique identifier first generates a proposed unique identifier (UID) or UID space, based on the rules for the appropriate domain. It then invokes UIAP, passing the UID space, domain ID, and a lifetime. This requests UIAP to verify the uniqueness of this UID space within the domain, claim the sole right to use this UID space, and defend this claim for the specified time. The UIAP service attempts to claim the given UID space. If the claim is successful, the application's request succeeds, and the application may consider the UID space unique and use these UIDs. The UIAP service on that device will defend the UID space against White & Williams Expires August 21, 2002 [Page 5] Internet-Draft Unique Identifier Allocation Protocol February 2002 other claims for the given lifetime. If the claim is unsuccessful, the application's request fails. Usually, the application will generate a new proposed UID space and try again. An application that wishes to re-verify its claim on a UID space or extend the lifetime of its UID space may re-invoke UIAP as required. 2.1.2 What UIAP Doesn't Do UIAP only guarantees the uniqueness of a UID space at the time the claim is made, and only within the scope of the current site. UIAP will defend the claim against other claims from the same site, but will not actively monitor the uniqueness of a UID space. If two UIAP sites merge, it is possible that a UIAP device from each site may have an existing claim on a particular UID space. At the time the claims were made, the UID space was unique to each site, but the UID space is no longer unique on the merged site. UIAP has no mechanism to detect this. The collision will only be detected if one of the UIAP devices (at the direction of an application) attempts to re-claim the UID space, or if the applications themselves have some collision detection mechanism. Recovery after collision is the responsibility of the application. Collisions can also be caused if a UIAP device that was a member of a site temporarily leaves the site (e.g. temporary network failure). This is actually just a special case of merging. Each UIAP device defends its own claims. If a UIAP device goes down, its claims will not be defended. 2.2 Domains and Claims UIAP may be used for a variety of different purposes, called domains. Claims in one domain are independant of claims in another domain. UIAP includes a domain identifier (DID) to distinguish domains. A domain identifier consists of 7 octets of arbitrary identifier and 1 octet of flags. The first seven octets identify a particular instance of UIAP at the application level, and are preferably assigned by an administrative body such as IANA. UIAP places no interpretation on this value. The last octet contains a set of flags that describe how UIAP devices should compare UIDs within the domain (see Section 3.2). These flags are fixed for a given DID, are specified as part of the DID specification, and are always treated as part of the DID. They are intended to be sufficiently comprehensive White & Williams Expires August 21, 2002 [Page 6] Internet-Draft Unique Identifier Allocation Protocol February 2002 to allow the use of UIAP in a wide variety of applications. The payload of a claim message is divided into two parts. The first part is the DID that defines the domain. This is constant for all claim messages in a given domain. The second part defines the UID space being claimed, and varies between claims. Note that the semantics of a domain may impose stricter rules than the domain's number space. UIAP has no mechanism for detecting such legal but meaningless claims; it is the responsibility of the application to make meaningful claims. 2.3 Requirements UIAP is designed to operate over a link layer that supports link- local multicast to all listening nodes. UIAP may not operate correctly on links with hidden nodes, as may be present in wireless networks. Where applicable, this document describes UIAP over IPv6, using link local unicast and multicast UDP. UIAP could equally be implemented over IPv4 or over another protocol that supports link-local communication. 2.4 Example Protocol Behaviour The pseudo-code below describes some of the most common operations in UIAP. Note that these algorithms are descriptive, not prescriptive. 2.4.1 Make a Claim To claim, the UIAP device sends out a Claim-Attempt message, then waits for other devices to send back messages to deny the claim. For new claims, 3 messages are usually sent with each message separated a suitable delay to help protect against dropped packets. If the claim process runs to completion and times out, it succeeds (and returns success to the application). If it is interrupted by a Claim-Deny, it fails (and returns a failure to the application). If the claim process is interrupted by a conflicting Claim-Attempt, the resolution process in Section 4.2.2.2 is used to determine whether the claim fails. White & Williams Expires August 21, 2002 [Page 7] Internet-Draft Unique Identifier Allocation Protocol February 2002 Repeat 3 times: { Send Claim-Attempt message. Wait UIAP_CLAIM_PERIOD. } Wait UIAP_CLAIM_TIMEOUT. Succeed. Note that a claim will immediately fail if a conflicting claim already exits on the local device. 2.4.2 Receive a Claim-Attempt Message A device receiving a Claim-Attempt message must first perform several checks against the devices remembered state. Known messages are dropped. Conflicting messages cause Claim-Deny messages to be sent. Other messages are forwarded. White & Williams Expires August 21, 2002 [Page 8] Internet-Draft Unique Identifier Allocation Protocol February 2002 If device has already seen this Claim-Attempt message: ( matches a stored message) { Update last received time. Discard message. End. } Store message record. Including - Message identifier, ie - Interface message was received on - Sender's link local address - Time received - No Deny sent If device has claim on this : { If claim in progress: { Handle Simultaneous Claim. } Else { Send Claim-Deny Message. } } Else { Forward Claim-Attempt message out other active interfaces. } Received Claim-Attempt messages must be remembered for long enough to allow them to propagate throughout the network. Once they are no longer current, they should be discarded to save memory and to (eventually) allow sequence numbers to be reused. White & Williams Expires August 21, 2002 [Page 9] Internet-Draft Unique Identifier Allocation Protocol February 2002 2.4.3 Forward a Claim-Attempt Message Process Claim-Attempt message. If hop limit > 0 { Decrement Hop Limit. For each active interface: (except the interface the Claim-Attempt was received on) { Send copy of Claim-Attempt message to UIAP multicast group. } } 2.4.4 Receive a Claim-Deny Message Incoming Claim-Deny messages may be related to a current claim, may need to be forwarded, or may be defunct. If Claim-Deny message matches a claim in progress: (same ) { Interrupt claim and Fail. End. } If Claim-Deny message matches a Claim-Attempt message (same ) AND a Claim-Deny has not yet been sent for this Claim-Attempt: { Forward Claim-Deny to next-hop. } Else { Drop Claim-Deny message. } 2.4.5 Send a Claim-Deny Message Claim-Deny messages are sent back to the originator using next-hop routing information stored with the Claim-Attempt records. Copy Claim-Attempt message. Set message type to Claim-Deny. Reset hop limit to maximum (currently 32). Send Claim-Deny message to next-hop sender. Record that Claim-Deny has been sent for this Claim-Attempt message. White & Williams Expires August 21, 2002 [Page 10] Internet-Draft Unique Identifier Allocation Protocol February 2002 Forwarding a Claim-Deny message is similar to sending one, except that the hop limit is decremented rather than being reset. 2.4.6 Handle a Simultaneous Claim On rare occasions, a UIAP device may receive a Claim-Attempt for the a UID that it is in the process of claiming. This is the only time that UIAP devices actively perform collision detection and resolution as part of the UIAP protocol. UIAP distinguishes between a device re-claiming a UID and claiming a UID for the first time. The reclaiming device is preferred when simultaneous claims occur for the same UID or UID space. If device is reclaiming: { Send Claim-Deny message. If received message indicates reclaiming: { Interrupt current claim and Fail. } } Else (new claim) { If received message indicates reclaiming: { Forward Claim-Attempt message out other interfaces. } else { Send Claim-Deny message. } Interrupt current claim and Fail. } 3. UIAP Implementation UIAP uses a claim-collide mechanism to resolve claims. When a claim is made, a Claim-Attempt message is sent to all UIAP devices in the site. Any device that wishes to Deny the claim must respond with a Claim-Deny message. If no Claim-Deny is received after 3 attempts, the claim succeeds. All UIAP messages use link-local UDP. The originating device multicasts a Claim-Attempt message out each participating interface. White & Williams Expires August 21, 2002 [Page 11] Internet-Draft Unique Identifier Allocation Protocol February 2002 Each device that receives a Claim-Attempt message examines it. If the device wishes to deny the claim, it sends back a Claim-Deny. If not, it forwards the Claim-Attempt out its other participating interfaces (if any). Unless denied, a Claim-Attempt will flood to all connected UIAP devices. Each device that handles a Claim-Attempt records the Claim-Attempt and the incoming link. Each Claim-Attempt flood contains a sequence number as part of its payload; this is used to determine whether a claim attempt message has been seen before. If a UIAP device receives further Claim-Attempt messages with the same originator and sequence number they are silently ignored. Claim-Deny messages are returned to the originating device using hop- by-hop forwarding. When a device receives a Claim-Deny message that matches a recorded Claim-Attempt, it forwards the Claim-Deny out the interface on which the Claim-Attempt was received. Non-matching Claim-Deny messages are discarded. Only one Claim-Deny message is sent or forwarded per Claim-Attempt message. If the device has already sent or forwarded one Claim-Deny for a particular Claim-Attempt message, it silently drops any further Claim-Deny messages. Once the originator times out (success) or receives a Claim-Deny (failure), it returns the result of the claim to the application. 3.1 Device Requirements UIAP is designed to run over link-local IPv6, but could be run over any protocol that supports link-local multicast. UIAP devices MUST run the UIAP protocol and MUST join the UIAP multicast group. Each UIAP device MUST have a valid Host ID (as per the IPv6 unicast Host ID [1]) and MUST have a valid link local address on each participating interface. UIAP uses link-local multicast address UIAP_MULTICAST_ADDR and ports UIAP_CLAIM_PORT and UIAP_REPLY_PORT. 3.2 Number Spaces The set of all possible UIDs in a domain forms a number space. Each claim attempts to validate a set of one or more UIDs within that number space. 3.2.1 Describing a Number Space Different number spaces have different structures. For example, 8- White & Williams Expires August 21, 2002 [Page 12] Internet-Draft Unique Identifier Allocation Protocol February 2002 bit integers, IPv4 addresses, and DNS names are all number spaces in which an application could use UIAP for validation. However, the structures are quite different. 8-bit integers are binary data, have a fixed size and are arranged numerically. IPv4 addresses are similar, but have a hierarchical structure from left to right. DNS names are character data of variable size, hierarchical, and ordered from right to left. UIAP places some restrictions on number spaces (and thus UIDs). All UIDs in a number space must be left-significant (most significant element is on the left), and representable within 255 octets of data. Right-significant number spaces (eg DNS names) MUST be transformed into a left significant form. 3.2.1.1 Characteristics of Number Spaces There are five characteristics of number spaces that are particularly relevant to UIAP. Length: UIDs may be either fixed-width or variable-width (up to the 255 octet limit). The size of a UID is stored with the UID. Restrictions on size are specified by the domain specification; there is no mechanism to specify or enforce UID sizes within UIAP. Data Type: Is the UID data binary data or character data? Justification: Are UIDs within a domain aligned by their leftmost or rightmost octet? Variable-sized integers are right-aligned, while hierarchical values (such as IP addresses) are left-aligned. UIAP contains a domain level flag which controls whether UIDs are treated as left or right aligned. Bit or Octet Aligned: UIDs may be octet aligned, or bit aligned. The last octet on the unjustified side of a bit aligned UID may be only partially significant. UIDs represented as characters are octet aligned; binary UIDs may be bit aligned. The number of significant bits in the last octet of a UID is stored with each UID. As with size, the domain specification describes whether bit aligned UIDs are semantically meaningful in a domain. Significant Zeros: When testing for equality, are extra zero octets on the unjustified side treated as significant? Treating zeros as insignificant is functionally equivalent to zero-padding the shorter UID to be the same length as the longer. UIAP treats all data in a UID as significant. The domain specification describes whether (and how) UIDs are to be padded. Most characteristics are specified as part of the domain White & Williams Expires August 21, 2002 [Page 13] Internet-Draft Unique Identifier Allocation Protocol February 2002 specification, not UIAP. 3.2.1.2 Example Number Spaces The following table suggests some sample number spaces and their characteristics. Number space Data Just. Length Alignment ---------------------------------------------------------- Integers binary right varies bit IPv4 addresses binary left 4 octet IPv4 CIDR subnets binary left up to 4 bit IPv6 prefixes binary left up to 8 bit DNS names * char left varies octet Note: The above table assumes that DNS names have been transformed into a left-significant form. 'www.ietf.org' becomes 'org.ietf.www'. The exact representation chosen is mandated by the specification for the particular UIAP Domain, and does not affect UIAP itself. 3.2.2 Describing a UID Claim UIDs may be claimed as either individual elements of a number space or as a contiguous set of elements. There are three ways to describe a UID space. Unique value: A single UID value. Range: A contiguous range. For example, every number between 13 and 42 inclusive. Ranges require two values to be included, as lower and upper bound. Prefix: All UIDs sharing a common prefix. For example, everything beginning with 192.168 (i.e. subnet 192.168/16). Prefixes are only valid for hierarchical, left justified, number spaces. 3.2.3 Representing UIDs UIDs are represented as a length counter and string of octets, from most significant to least significant. Bit-aligned UIDs have an additional field which specifies how many bits in the last octet are significant. Insignificant bits in the last octet MUST be set 0. 3.2.4 Comparing UIDs UID spaces are compared according to their values and the rules of the number space. The comparison fails if two UID spaces overlap at White & Williams Expires August 21, 2002 [Page 14] Internet-Draft Unique Identifier Allocation Protocol February 2002 any point, or succeeds if the intersection is null. When comparing individual UIDs, the following rules describe UID ordering under the various number spaces. UIDs are always compared on an octet-by-octet basis. These rules do not require a particular implementation of the comparison routines, but the results must be identical to those given. In number spaces that are left-justified, left-significant, a simple string comparison is performed. If zeroes are significant, longer UIDs are considered larger. If zeroes are not significant, the shorter UID is zero-padded until the UIDs being compared are of the same length. Comparison is done octet by octet, not bit by bit. Number spaces that are right-justified, left-significant are compared from the left end of the longest string first. If zeroes are not significant, then the shorter string is zero-padded to make the strings the same length. If zeroes are significant, the longer string is larger. Comparison is octet by octet. If bit-aligned UIDs are identical on an octet-by-octet comparison but have different bit lengths in the last field, then the longer UID is larger. Otherwise they are equal. UIDs from different number spaces or domains is cannot be meaningfully compared. UIAP devices MUST NOT perform such a comparison. Results of such are comparison are undefined. 4. UIAP Messages 4.1 Common message format All UIAP messages share a common message format. White & Williams Expires August 21, 2002 [Page 15] Internet-Draft Unique Identifier Allocation Protocol February 2002 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | Type | 0 |X|R| 0 | Hop Limit | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Lifetime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originating Device ID | | 8 octets | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Claim Reference Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Domain ID ________________| | 7 + 1 octets |J| 0 (Reserved)| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 (Reserved) | BA | BA2 |Fmt| UID Len | UID Len 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | UID | | variable length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Version: Version of UIAP. 1 octet. This is version 0x01. UIAP devices MAY silently discard UIAP messages with unknown version numbers. UIAP Message Type: 4 bits. Legal message types are described below. 0: Reserved field. 2 bits. MUST be set 0 by sender and ignored by receiver. X: Proxy Enable flag. 1 bit. Claim-Attempt messages with this flag set MAY be defended by proxy defense. R: Reclaim flag. 1 bit. This flag indicates that the originating device believes that this UID has previously been successfully claimed. 0: Reserved field. 1 octet. MUST be set 0 by sender and ignored by receiver. Hop Limit: 1 octet. This field provides additional protection against loops in the network. It is originally set to 32, and is decremented by the sending device each time a UIAP message is forwarded on a link. Messages with a hop limit of 0 SHOULD be processed but MUST NOT be forwarded. White & Williams Expires August 21, 2002 [Page 16] Internet-Draft Unique Identifier Allocation Protocol February 2002 Lifetime: Lifetime of this UID. 4 octets. The length of time (in seconds) that the originating UIAP device intends to defend this claim. Originating Device ID: Host ID of originating UIAP device. 8 octets. This field SHOULD be constructed in the same way as the Host ID portion of an IPv6 address [1]. Note that a device has only one device ID, even if it has multiple interfaces. A device SHOULD use its own EUI if it has one; otherwise it MAY use the EUI of one of its interfaces, or choose any suitable ID. ID 0 (all bits 0) is reserved to represent a non-existent device, and MUST NOT appear in a message. Sequence Number: 4 octets. The sequence number is an unsigned integer used for flood tracking. Claim Reference Number: 4 octets. An internal reference number used by the originating service to track a particular claim (not a flood). This field may be set to any value the originating UIAP service finds useful and MUST be preserved intact by forwarding UIAP services. Domain ID: Domain identifier. 8 octets including flags. UIAP devices treat the Domain ID as an unformatted identifier. Applications using UIAP SHOULD attach semantic meaning to the Domain ID and behave accordingly. J: Justification flag. 1 bit. 0 implies left justified. 1 implies right justified. 0: Reserved field. 7 bits. MUST be set 0 by sender and ignored by receiver. 0: Reserved field. 1 octet. MUST be set 0 by sender and ignored by receiver. BA: Bit Alignment. 3 bits. How many bits in last octet are significant? 0 indicates all bits. Octet aligned data always sets this field 0. BA2: Bit Alignment, 2nd UID. 3 bits. How many bits in last octet are significant? 0 indicates all bits. Octet aligned data always sets this field 0. This field is ignored (and MUST be set 0 by senders) if the UID space is not a range (and thus only needs one UID). Fmt: UID Format. 2 bits. How UID should interpret the UID/s. A unique ID is 0, a prefix is 1, and a range (requiring two UIDs) is White & Williams Expires August 21, 2002 [Page 17] Internet-Draft Unique Identifier Allocation Protocol February 2002 2. UID Len: UID Length. 1 octet. The number of octets of data in the UID, from 0 to 255 octets. UID Len 2: 2nd UID Length. 1 octet. As UID Len, but only valid when dealing with ranges, which have two UIDs in the data. The second UID begins the octet after the first finishes. If not a range, MUST be set 0 by sender and ignored by received. UID: UID space. Variable length (see UID Len and UID Len 2). UIAP devices treat the UID space as a variable length string of octets. Comparisons between UID spaces are specified by the rules for the number space. Legal values for a UID space are determined by the Domain ID, at the application layer. When considering ranges, consists of two UIDs, the second beginning the octet immediately following the first. 4.1.1 Message Types 0: Claim-Attempt message. 1: Claim-Deny message. 4.2 Claim-Attempt A Claim-Attempt message is used to claim a UID space in a domain. The claiming UIAP device (the originator) multicasts the Claim- Attempt message to the UIAP multicast group on all participating interfaces. Receiving UIAP devices process the Claim-Attempt, then (usually) flood the message out their remaining interfaces. 4.2.1 Message Format Claim-Attempt messages use the common message format (Figure 8). The message type is 0x0. 4.2.2 Claim-Attempt Handling 4.2.2.1 Receiving a Claim-Attempt Each Claim-Attempt message is uniquely identified by its Message ID (i.e. the tuple). UIAP devices receiving a Claim-Attempt message MUST remember the Message ID of the Claim-Attempt for X seconds, and then SHOULD discard the message as soon as convenient. White & Williams Expires August 21, 2002 [Page 18] Internet-Draft Unique Identifier Allocation Protocol February 2002 Upon receiving a Claim-Attempt, a UIAP device MUST first check if it has already processed that Claim-Attempt (identified by the Message ID). If the message has already been processed, it SHOULD NOT be processed again. If the message has not been processed, it MUST be remembered and processed. A UIAP device MUST compare the UID space in the Claim-Attempt to its own list of current claims (those defended by this device). If the device has a conflicting claim (same DID and intersecting UID space), the device MUST send back a Claim-Deny (Section 4.3). If the Claim-Attempt does not conflict with any existing claim, then the device MUST forward the Claim-Attempt out all participating interfaces, except the interface the Claim-Attempt was received on (flooding). A device MAY forward the Claim-Attempt out the receiving interface, but this is NOT RECOMMENDED. If a UIAP device receives a duplicate copy of a Claim-Attempt message on a second interface while processing a message on the first interface, the duplicate message MUST be discarded. It is RECOMMENDED that device does not forward the message out the second receiving interface. UIAP devices sending or forwarding a Claim-Attempt message on a link MUST use a valid link-local address as the source address of the message. UIAP devices receiving a Claim-Attempt MUST remember and associate with the message the link-local address of the device that forwarded them the Claim-Attempt. A device receiving multiple copies of a message MUST remember the sender of the first copy. It is RECOMMENDED that other senders be discarded. 4.2.2.2 Simultaneous Claim-Attempts It is possible that a UIAP device may receive a Claim-Attempt for a UID space that it is currently in the process of claiming. In this case, it is ambiguous as to who should back off. The Reclaim (R) flag is used to determine the behaviour in this situation. If both the incoming Claim-Attempt and the outgoing Claim-Attempt are new claims (R not set) or re-claims (R set), then the receiving UIAP device sends a Claim-Deny message and reports a failure to the application. If one Claim-Attempt is a re-claim and the other is not, then the re- claim takes precedence. If the outgoing Claim-Attempt has the R flag set but the incoming Claim-Attempt does not, then the incoming claim is denied and the outgoing claim continues. If the incoming Claim- Attempt has the R flag set but the outgoing claim does not, then the outgoing claim fails immediately and the incoming claim is forwarded as normal. White & Williams Expires August 21, 2002 [Page 19] Internet-Draft Unique Identifier Allocation Protocol February 2002 Other UIAP devices receiving conflicting Claim-Attempts from multiple sources SHOULD NOT attempt to resolve the Claim-Attempts, but SHOULD forward the Claim-Attempt messages as normal. 4.2.2.3 Other Note that a device MUST remember Claim-Attempt messages that it originates, in order to protect against loops. A UIAP device MAY choose any appropriate values for the number of claim attempts sent during a claim and the for the various times. However, the values provided are RECOMMENDED as suitable defaults. 4.3 Claim-Deny A Claim-Deny messages may be sent in response to a Claim-Attempt. Claim-Deny messages are not multicast, but unicast hop-by-hop back to the originator. Next hop information is stored by devices as they process Claim-Attempt messages. 4.3.1 Message Format Claim-Deny messages use the common message format (Figure 8). A Claim-Deny message is a copy of the Claim-Attempt message being denied, except that the Type field is set to 0x1 and the Hop Limit field is reset to 32. The X and R fields are ignored on Claim-Deny messages. 4.3.2 Claim-Deny Handling A UIAP device initiating a Claim-Deny MUST send the Claim-Deny message out the same interface that the matching Claim-Attempt was first received. The destination of this message is the link-local address of the interface that forwarded the Claim-Attempt (as recorded with the Claim-Attempt message). A claim deny MAY be sent out multiple interfaces, but this is NOT RECOMMENDED. A UIAP device receiving a Claim-Deny message MUST examine its record of recent Claim-Attempts for a matching message (as given by Message ID). If a match is found, it MUST forward the Claim-Deny to the sending interface (or interfaces) associated with the Claim-Attempt, unless the matching Claim-Attempt was originated by this device. If a match is not found, it SHOULD silently discard the Claim-Deny. If the matching Claim-Attempt was originated by the device and the claim is still in progress (has not returned a result to the application), the UIAP device MUST return a failure to the application and stop the claim. If a result has already been White & Williams Expires August 21, 2002 [Page 20] Internet-Draft Unique Identifier Allocation Protocol February 2002 returned to the application, the Claim-Deny message MUST be discarded. A UIAP device SHOULD NOT forward more than one Claim-Deny per Claim- Attempt message. After the first, additional Claim-Deny messages SHOULD be silently dropped. 4.4 Reclaim A Reclaim message is a Claim-Attempt message (message type 0x0) with the Reclaim flag set. Reclaim messages may be eligible for proxy defense and are given preference in the case of simultaneous claims, but are otherwise treated identically to normal Claim-Attempt messages. Reclaim messages are used when a UIAP device wishes to issue another Claim-Attempt message for a claim that has already succeeded. Rather than send a series of three Claim-Attempt messages, a single Claim- Attempt (with reclaim flag set) is sent. This reduces network traffic and improves application response time; no collision is expected since the UIAP device has previously validated the UID as unique. A UIAP device MAY choose to send more than one Claim-Attempt message when attempting a Reclaim, if reliability issues offset the performance concerns. 4.5 Other Key Concepts 4.5.1 Floods and Sequence Numbers Each Claim-Attempt message sent by UIAP when testing the uniqueness of a UID is flooded throughout the site. A message ID () is used to prevent loops by forwarding only the first copy of each message seen. Messages can be uniquely identified by their originating host ID and sequence number. On initialisation, the UIAP device chooses a random sequence number from the available range. Each time the device initiates a Claim- Attempt flood, it MUST increment the sequence number. Each flood MUST use a different, monotonically increasing, sequence number. Each UIAP device MUST order its own sequence numbers, but SHOULD treat other devices' sequence numbers as arbitrary identifiers. Sequence numbers wrap when they overflow the 32 bit field. For example, 0 is the sequence number that follows 2^32-1. White & Williams Expires August 21, 2002 [Page 21] Internet-Draft Unique Identifier Allocation Protocol February 2002 4.5.2 Claim Lifetime Each Claim-Attempt contains a lifetime field. The value of this field is a time in seconds and is semanticically identical to that of IPv6 address lifetimes (see [3]). A lifetime of 0 is valid. Lifetime fields are primarily used for proxy defense (Section 5.1). The lifetime provides the length of time (in seconds) that the originating UIAP device permits other UIAP devices to assume it will defend a claim. This MUST NOT be longer than the actual time than the originating device intends to defend the claim, but MAY be shorter. Devices performing proxy defense MUST NOT defend a claim for longer than the period specified in the lifetime. UIAP devices sending Claim-Attempt messages are not required to include the same lifetime as the application requested, and MAY choose any smaller value (including 0). Devices sending Claim-Deny messages MAY choose not to copy the lifetime from the request, and set it to 0 instead. 5. Extensions 5.1 Proxy Defense Proxy defense allows UIAP devices to defend claims on behalf of other UIAP devices. This limits network traffic and may improve reliability in a unreliable network, at the expense of some false Claim-Deny messages. A UIAP device implementing proxy defense remembers Claim-Attempt messages from other devices and defends these claims as if they were the device's own. Only Claim-Attempt messages with both the X (proxy enabled) and R (reclaim) flags set may be proxied. Claim-Attempt messages without both these flags set MUST NOT be proxied. A device providing proxy defense MUST stop defending a claim once the lifetime specified in the Claim-Attempt expires. The lifetime is measured from the time the device receives the Claim-Attempt message. It MAY stop defending a claim at any earlier time. There is no mechanism to explicitly remove or revoke proxy defense. If a device providing proxy defense receives multiple Claim-Attempt messages relating to a particular claim, it MAY choose to defend any or all of them, subject to other considerations. Implementations may wish to use sequence numbers or other mechanisms to decide which Claim-Attempt messages are more recent. A device providing proxy defense MUST NOT defend the claim against White & Williams Expires August 21, 2002 [Page 22] Internet-Draft Unique Identifier Allocation Protocol February 2002 the original claimant. A device may transmit multiple Claim-Attempt messages related to a single claim, and the device providing proxy device must forward each of these as normal. To enable proxy-defense after a successful Claim-Attempt, the claiming device immediately attempts a reclaim on the successful claim with the proxy enabled flag set. This allows devices offering proxy defense to defend the claim. 6. Allocation of Domain Identifiers Each DID is an 8 octet value. While DIDs are essentially arbitrary (except for the 8th octet), a minimal structure is imposed upon them to aid allocation. Draft note: All allocations listed here are proposals. IANA approval is required before this becomes policy. The first two octets are allocated by IANA, and denote the allocating authority for the remaining six octets. Current allocations are: Value Authority Notes ------ ----------- ------- 0x0000 Reserved 0x0001 IANA Standardised allocations 0x0002 Reserved Allowing for growth in IANA and private spaces ... 0x0FFD 0x0FFE Private Private usage, site or organisation local deployment. 0x0FFF Experimental Experimental work. 0x1000 Reserved 0x1001 Reserved Reserved for other allocating authorities. ... 0xFFFF Organisations wishing to allocate Domains independently of the IETF process may request a top level domain identifier from the upper end of the space. Every IANA Domain MUST have an associated specification describing the semantics of that domain and how UIDs from that domain may be constructed and interpreted by applications. This specification prescribes which number space options are to be used and what UID constructions are legal. A single specification may cover multiple related Domains (with corresponding DIDs). Specifications MUST be reviewed by the IETF or IESG before being presented to IANA for DID allocation. White & Williams Expires August 21, 2002 [Page 23] Internet-Draft Unique Identifier Allocation Protocol February 2002 It is strongly RECOMMENDED that non-IANA Domains use similar specifications. Non-IANA top level domain identifiers may be allocated as required, with the top level octets being assigned by IANA. Organisations wishing to allocate top level octets SHOULD convince a designated expert or the IESG/IETF as to their need to allocate domains rather than requesting IANA allocation. The last octet is allocated as part of the DID allocation process, but its value is not arbitrary, and should instead be set to correctly describe the number space defined by the DID. 6.1 Writing Domain Identifiers Each DID is an 8 octet number. DIDs may be expressed as four colon separated hexadecimal quads, as in '0001:0002:0003:0000', or abbreviated to '1:2:3:0'. Ranges of DIDs may be expressed by substituting an '*' character in place of one or more quads. For example, '1:2:3:*' represents all DIDs beginning with '1:2:3:' and ending with 0x0000 to 0xFFFF. Smaller ranges may be represented replacing characters with the '?' character, as in '1:2:3:0???', but the quad must be fully expanded. 6.2 Example See the subnet allocation draft [4] for an example of Domain allocation. 7. Security Considerations UIAP is intended to be used in small-scale networks such those found inside the home. To prevent denial of service attacks against applications using UIAP, each recipient must be able to authenticate the sender of every UIAP message. To prevent leakage of information as might occur when using a wireless network in the home, UIAP payloads should be encrypted. Source authentication may also be necessary to prevent unintentional merging (with associated security and performance issues) if two sites accidentally overlap. UIAP itself does not provide security mechanisms to address the above requirements. The IP Security protocol suite provides the functionality that is required, and it is RECOMMENDED that IPSec be used to secure UIAP. Another alternative is to ensure that appropriate layer-2 security schemes are used on all shared media links in the site that UIAP messages will pass over (e.g. wireless and powerline networks). White & Williams Expires August 21, 2002 [Page 24] Internet-Draft Unique Identifier Allocation Protocol February 2002 UIAP messages are forwarded on a hop-by-hop basis using only link- local communication, implying that messages must be authenticated at each hop before they are propagated. Since devices using UIAP engage in controlled flooding of messages, it is critical to ensure that rogue forwarders cannot engage in the protocol. The IP Security protocols as currently specified can support packet authentication and privacy for the unicast and multicast messages used by UIAP. At present, there is no standard key agreement protocol designed for IP multicast. In addition, IKE may not be ideal for the link-local, hop-by-hop behaviour exhibited by UIAP. A manually configured "shared SA" seems to be the only choice at present, and senders to the UIAP multicast group would use the same Security Parameter Index (SPI) (Section 4.7, [2]). 8. IANA Considerations 8.1 UIAP Over IPv6 or IPv4, UIAP requires a link local multicast address (UIAP_MULTI_ADDR) and two well known UDP ports (UIAP_CLAIM_PORT and UIAP_REPLY_PORT). These are to be IANA standardised. UIAP over non-IP protocols will have similar requirements. 8.2 Domains IANA is responsible for allocating top level domains and allocating particular domains inside the IANA space. Domains inside the IANA space require an accompanying specification for each domain with at least IESG approval. Top level domains do not require specifications but do require justification of the need to create a new top-level domain. 9. Other Concerns In UIAP, there is a very small potential for message ID collision if two devices share a device ID and their sequence numbers are sufficiently close together. If a device receives a message that contains the device's ID as the originator ID but the device has no record of sending that message, there may be a device ID conflict. If the sequence number is "close" to the device's current sequence number, the device MAY choose a new random sequence number that is sufficiently different from the current sequence numbers. UIAP devices could also use UIAP to validate the uniqueness of their device ID. The mechanics of this are beyond the scope of this document. White & Williams Expires August 21, 2002 [Page 25] Internet-Draft Unique Identifier Allocation Protocol February 2002 10. Table of Constants This table describes the symbolic constants used in this document. Where appropriate, values are suggested. UIAP_MULTICAST_ADDR Link local multicast address for UIAP. IANA allocated. UIAP_CLAIM_PORT UDP port for UIAP Claim-Attempt message floods. IANA allocated. UIAP_REPLY_PORT UDP port for UIAP unicast replies (Claim-Deny messages). IANA allocated. UIAP_CLAIM_PERIOD Time between initiating Claim-Attempt floods for a particular claim. Suggested default: 500 milliseconds. UIAP_CLAIM_TIMEOUT Time period to wait for a Claim-Deny after a Claim-Attempt flood is initiated. Suggested default: 1 second. References [1] Hinden, R. and S. Deering, "IP Version 6 Addressing Architecture", RFC 2373, July 1998. [2] Kent, S. and R. Atkinson, "Security Architecture for the Internet Protocol", RFC 2401, November 1998. [3] Narten, T., Nordmark, E. and W. Simpson, "Neighbour Discovery for IP Version 6 (IPv6)", RFC 2461, December 1998. [4] White, A. and A. Williams, "Zero-Configuration Subnet Prefix Allocation Using UIAP", ID draft-white-subnet-prefix-alloc-00, November 2001. Authors' Addresses Andrew White Motorola Australian Research Centre Locked Bag 5028 Botany, NSW 1455 AU Phone: +61 2 9666 0500 EMail: Andrew.E.White@motorola.com URI: http://www.motorola.com.au/marc/ White & Williams Expires August 21, 2002 [Page 26] Internet-Draft Unique Identifier Allocation Protocol February 2002 Aidan Williams Motorola Australian Research Centre Locked Bag 5028 Botany, NSW 1455 AU Phone: +61 2 9666 0500 EMail: Aidan.Williams@motorola.com URI: http://www.motorola.com.au/marc/ Appendix A. Acknowledgements The authors thank John Judge and Kwan-Wu Chin of the Motorola Australian Research Centre for their assistance with this draft. Stuart Cheshire provided a careful and helpful review of an earlier version of this document. Appendix B. Intellectual Property Motorola has submitted a patent claim covering UIAP technology. White & Williams Expires August 21, 2002 [Page 27] Internet-Draft Unique Identifier Allocation Protocol February 2002 Index D Domain Identifier 6 domain 5 M Messages Claim-Attempt 18 Claim-Deny 20 N number space 12 White & Williams Expires August 21, 2002 [Page 28] Internet-Draft Unique Identifier Allocation Protocol February 2002 Full Copyright Statement Copyright (C) The Internet Society (2002). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society. White & Williams Expires August 21, 2002 [Page 29]