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:
(<originating_device_id, sequence_number> matches a stored message)
{
Update last received time.
Discard message.
End.
}
Store message record.
Including
- Message identifier, ie <originating_device_id, sequence_number>
- Interface message was received on
- Sender's link local address
- Time received
- No Deny sent
If device has claim on this <Domain_ID, UID>:
{
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 <originating_device_id, domain_id, uid>)
{
Interrupt claim and Fail.
End.
}
If Claim-Deny message matches a Claim-Attempt message
(same <originating_device_id, sequence_number>)
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 <originating_device_id, sequence_number> 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
(<originating_device_id, sequence_number>) 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 <domain_id, uid space> 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]