MALLOC working group Mark Handley, ACIRI Internet Draft Stephen R. Hanna, Sun Microsystems, Inc. June 2000 draft-ietf-malloc-aap-04.txt Expires: December 2000 Multicast Address Allocation Protocol (AAP) Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026. 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. Abstract The document defines a Multicast Address Allocation Protocol (AAP) that forms a part of the Internet Multicast Address Allocation Architecture being defined by the IETF Multicast Address Allocation Working Group. AAP addresses the specific issue of coordination among Multicast Address Allocation Servers within a domain. 1. Introduction This document describes and defines the Multicast Address Allocation Protocol (AAP), which allows Multicast Address Allocation Servers (MAAS's) to coordinate multicast address allocation within a domain. Section 1 introduces the concepts and terms used throughout the document. Section 2 gives an overview of the protocol. Sections 3 and 4 describe how MAAS's and Prefix Coordinators behave with respect to the protocol. Section 5 describes protocol details and message formats. Section 6 describes Security Considerations and section 7 describes IANA Considerations. Section 8 lists acknowledgements, Handley and Hanna [Page 1] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 section 9 lists references, and section 10 gives the authors' addresses. Appendix A includes sample protocol interactions. Appendix B lists constants and timers defined in this document. Appendix C lists changes made in this version of the document. 1.1 Terminology 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 [3]. Constants and timers defined in this document are listed in Appendix B. Their names are written in all caps with square braces surrounding them (like [TIMER-1]). References to other documents are listed in section 9. They are indicated by arabic numerals in square braces (like [1]). 1.2. Definitions AAP Address The reserved scope-relative multicast address used for the AAP protocol within an allocation domain. Allocation Domain (or domain) An administratively scoped multicast-capable region of the network, within which multicast addresses are allocated dynamically using an intra-domain protocol such as AAP. Allocation domains will normally coincide with unicast Autonomous Systems (AS's). For more information, see section 2.1. Multicast IP Multicast, as defined in [4] and modified in [5]. Multicast Address An IP multicast address or group address, as defined in [4] and [6]. An identifier for a group of nodes. Multicast Scope A range of multicast addresses configured so that traffic sent to these addresses is limited to some subset of the internetwork. See [6] and [7]. Multicast Address Allocation Server (MAAS) A host providing multicast address allocation services. Handley and Hanna [Page 2] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 Prefix Coordinator A host that announces the set of multicast addresses available for use within an allocation domain. Scope Zone One multicast scope may have several instances, which are known as Scope Zones or zones, for short. For instance, an organization may have multiple sites. Each site might have its own site-local Scope Zone, each of which would be an instance of the site-local Scope. However, a given interface on a given host would only ever be in at most one instance of a given scope. Messages sent by a host in a site-local Scope Zone to an address in the site-local Scope would be limited to the site-local Scope Zone containing the host. 1.3 The Internet Multicast Address Allocation Architecture AAP fits into the Internet Multicast Address Allocation Architecture [1] being defined by the IETF Multicast Address Allocation Working Group. This architecture has three layers: o A host-server protocol or mechanism that a host uses to request multicast address allocation services from a Multicast Address Allocation Server (MAAS). An example of such a protocol is MADCAP [8]. o An intra-domain protocol or mechanism that MAAS's use to coordinate allocations within a domain to ensure that they do not collide. AAP plays this role. o An inter-domain protocol or mechanism that coordinates multicast address allocation across domains to avoid duplicate allocations and perhaps achieve other goals, such as improving aggregation of multicast addresses to reduce the size of multicast routing tables. MASC [2] or static allocations by AS number [9] can be used at this layer. 1.4 Requirements The AAP protocol is designed to meet certain requirements which are appropriate for its role as an interdomain multicast address allocation protocol designed primarily to coordinate the actions of Multicast Address Allocation Servers within an allocation domain. o The first and most important requirement is to ensure the continued availability of multicast address allocation services. AAP has a decentralized architecture so that it can survive the failure of Handley and Hanna [Page 3] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 one or more Multicast Address Allocation Servers or Prefix Coordinators. AAP is also designed to continue functioning during a short-term network partition. Long-term partitions may cause duplicate address allocations. Section 2.2 contains a more detailed discussion of how network partitions are handled. o Since multicast addresses are a relatively scarce commodity, AAP is designed to achieve high utilization. That is, it is designed to ensure that in a situation where demand for multicast addresses exceeds supply, all or almost all addresses can be in use simultaneously. o AAP helps MAAS's to detect and resist denial of service and other attacks. AAP messages may be authenticated so that unauthorized messages can be ignored. Even an attack from an authorized AAP server can be resisted by blocking all of its claims with Address In Use messages. o Duplicate address allocations (collisions) are largely avoided. Network partition, excessive packet loss, or unstable MAAS's can cause collisions, but this should be rare. When collisions occur, they can be detected via AAP. However, applications that use multicast must always be prepared to filter out extraneous traffic, since the IP Multicast model allows anyone to send on any multicast address. 2 Protocol Overview The Multicast Address Allocation Protocol (AAP) allows Multicast Address Allocation Servers (MAAS's) and Prefix Coordinators within an allocation domain to coordinate their actions. MAAS's and Prefix Coordinators communicate by sending UDP messages to a reserved port number and a reserved scope-relative multicast address (known as the AAP address). This ensures that all MAAS's and Prefix Coordinators within a domain receive all messages concerning address allocation within that domain. The reserved port number is 2878. The reserved scope-relative multicast address has been requested from IANA, but has not yet been assigned. Prefix Coordinators periodically announce the set of multicast addresses and lifetimes available for allocation within the domain using the Address Space Announce (ASA) message. MAAS's periodically announce with the Address In Use (AIU) message the set of multicast addresses that they have allocated. Before Handley and Hanna [Page 4] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 allocating addresses, a MAAS listens on the AAP address for at least [STARTUP-WAIT] so that it has a good idea of currently available addresses. To allocate one or more addresses, a MAAS sends an Address Claim (ACLM) message listing the addresses and lifetimes desired and retransmits this message at exponentially increasing intervals. If another MAAS is aware of a conflicting allocation, it will send an AIU listing the conflict (using a randomized timer to avoid storms). If an AIU listing a conflict is received, the claiming MAAS will choose another set of addresses and start again by sending an ACLM for those addresses. If no AIU is received within [ANNOUNCE-WAIT] seconds, the claiming MAAS will consider the addresses allocated and begin announcing them periodically using the AIU message. MAAS's can "preallocate" addresses using the Address Intent To Use (AITU) message. To preallocate one or more addresses, a MAAS periodically announces the preallocation using AITU. If another MAAS knows of a conflict, it responds as it would to a conflict to an ACLM. If a MAAS has sent at least two AITU messages without receiving notice of a conflict, it can skip the ACLM and move directly to sending an AIU and allocating the addresses. If a MAAS cannot meet its allocation needs with the addresses currently available for allocation, it can report this to the other MAAS's with an Address Not Available (ANA) message. An Address Space Report (ASRP) message is sent periodically by a MAAS (selected using random timeouts) to indicate to the Prefix Coordinator(s) how much of the current address space is in use and how many addresses are needed to satisfy demands. Prefix Coordinator(s) are often small devices with no stable storage and this provides a way for them to track usage without having to track individual addresses. The Prefix Coordinator(s) may decide to increase or decrease the available address space in response to a single ASRP message or an observed trend in usage. If security is desired, IPsec is used to authenticate messages (using a manually configured shared key). Unauthenticated messages are ignored. 2.1 Scopes AAP can be used to manage global multicast addresses and/or administratively scoped multicast addresses [7]. A MAAS will typically use MZAP [10] to learn about the administrative scopes that it is in. For each scope, it will learn the range of addresses assigned to the scope, the name or names assigned to the scope, and Handley and Hanna [Page 5] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 whether the scope is a "large"/"divisible" scope or a "small"/"indivisible" scope. AAP MUST NOT be used to manage TTL-scoped multicast addresses. 2.1.1 Large Scopes A large scope is divided up using some interdomain multicast address allocation protocol or mechanism into multiple allocation domains. Some addresses within the large scope are assigned to each allocation domain and AAP (or some other intradomain protocol or mechanism) is used to manage these addresses within the allocation domain. The Internet Multicast Address Allocation Architecture [1] defines a new administrative scope named the Allocation Scope. Whenever AAP is to be used to manage addresses on large scopes, an Allocation Scope MUST be defined. Its boundary MUST coincide with the edge of the allocation domain and all large scopes active within the allocation domain MUST contain the Allocation Scope. If the Allocation Scope is not active within a region of the network, then AAP cannot be used to manage large scopes in that region. However, it can still be used to manage small scopes. The AAP traffic for managing large scopes within a given allocation domain is sent on the scope-relative multicast address reserved for AAP within the Allocation Scope. For the purposes of AAP, the global address space is considered to be a large scope, although it is not an administrative scope and its existence is not announced using MZAP. 2.1.2 Small Scopes The AAP traffic for managing a small scope is sent on the scope- relative multicast address reserved for AAP within the scope being managed. ASA and ASRP messages SHOULD NOT be used within a small scope and Prefix Coordinators are not needed, since there is no need to coordinate with an inter-domain protocol or mechanism. However, these messages MAY be sent for network management or other reasons. All small scopes active in an allocation domain MUST be contained within (or topologically equal to) the Allocation Scope for that allocation domain (if an Allocation Scope is defined). 2.1.3 Handling Multiple Scopes When a MAAS or Prefix Coordinator is handling multiple scopes at the Handley and Hanna [Page 6] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 same time, it should treat each scope separately. Also, each AAP message MUST pertain to only one scope. This is especially important when multiple large scopes share a single allocation domain and Allocation Scope, because this allows a MAAS or Prefix Coordinator that is not interested in a particular scope to discard messages pertaining to other scopes. 2.2 Network Partition The AAP protocol is designed to continue functioning properly in spite of short-term network partitions or server failures. However, certain steps should be taken to ensure optimal robustness. First, MAAS's SHOULD preallocate enough addresses to last through a short-term network partition (1 hour is a reasonable default). Second, if the network is partitioned, no new MAAS's should be added during the partition. Otherwise, the new MAAS's will not know about addresses preallocated by MAAS's separated from them by the network partition. The failure of one or more MAAS's should not cause significant problems. Other MAAS's will defend the allocations of the failed MAAS's until their end time. After that, the allocations will be deleted. The failure of one or more Prefix Coordinators is also accomodated. If another Prefix Coordinator is still around, it will pick up the duties of the failed Prefix Coordinator. If no Prefix Coordinators are working, the MAAS's will resend the latest ASA message until the Prefix Coordinators are working again. In this circumstance, the system should continue to work until the address lifetimes listed in the ASA message expire. 3 Multicast Address Allocation Servers A Multicast Address Allocation Server (MAAS) is a host providing multicast address allocation services. This host may be providing multicast address allocation services to other hosts using the MADCAP protocol (or some other protocol or mechanism). Alternatively, a MAAS may be concerned only with its own address allocation needs. 3.1 MAAS Requirements All MAAS's MUST maintain stable storage so that they remember their own address allocations, those of other MAAS's in the domain, and the addresses available in the domain. This stable storage MUST be maintained across power losses, reboots, etc. Handley and Hanna [Page 7] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 If the stable storage on one MAAS is lost, other MAAS's in the domain will continue to defend its allocations. However, the loss of stable storage on several MAAS's or the combination of a network outage with the loss of stable storage in a MAAS can result in duplicate address allocations. All MAAS's MUST attempt to maintain active participation in the AAP protocol at all times, with constant network connectivity. Occasional outages will be handled by by other MAAS's defending the missing MAAS's allocations, but an extended loss of connectivity with one or more MAAS's can result in duplicate address allocations. Because of these requirements (and because of scaling limitations), most hosts should not be MAAS's. Instead, a few reliable, well- connected hosts should be selected as MAAS's. Other hosts should connect to those MAAS's using a client-server protocol such as MADCAP. This will relieve them from the burdens of keeping the available addresses and all the allocations in the domain in stable storage, maintaining constant network connectivity and participation in the AAP protocol, and waiting [STARTUP-WAIT] seconds after joining the AAP address before they can allocate an address. Any host that does not support a client-server protocol such as MADCAP SHOULD NOT operate as a MAAS for a given scope if a MADCAP server is available serving that scope. For scopes larger than Local scope, a host that does not support a client-server protocol such as MADCAP SHOULD NOT operate as a MAAS even if there is no MADCAP server available serving that scope. These behaviors may be overridden by configuration. 3.2 Specification of MAAS Behavior The primary function of a MAAS is to allocate multicast addresses. The hard part is to do this robustly, efficiently, and without collisions. 3.2.1 The Allocation Record A MAAS MUST listen to messages sent to the AAP address for all scopes in which it is active. It MUST maintain a separate Allocation Record for each scope, including information about all allocations (announced using the AIU message), preallocations (announced using the AITU message), address requests (announced using the ANA message), and available addresses (announced using the ASA message). The information about allocations, preallocations, and address requests SHOULD be removed when they reach their end time. The information about available addresses SHOULD be retained until it is superseded by information from a newer ASA message. Handley and Hanna [Page 8] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 The entries in this record allow a MAAS to defend the allocations of other MAAS's (if those MAAS's are unable to defend their own allocations for some reason). They also allow the MAAS to determine which addresses it should choose for its own allocations. 3.2.2 Defending Allocations A MAAS MUST send AIU messages periodically for all the addresses that it currently has allocated. Each of these addresses SHOULD be included in an AIU message about every [REPEAT-INTERVAL] seconds. Actually, the MAAS SHOULD vary the interval by about 30% (+ or -) to avoid synchronization effects. For these regular AIU announcements (as opposed to AIU messages sent in response to ACLM or AITU messages or AIU messages sent with a shorter retransmission timer than [REPEAT-INTERVAL]), a MAAS SHOULD consolidate its allocated addresses into as few AIU messages as possible (while ensuring that the UDP payload of the AIU message does not exceed 500 bytes). The MAAS should also use a separate randomized timer for each of these messages or some similar technique to avoid synchronizing the time when the messages are sent. This will reduce the background traffic due to AIU messages and avoid synchronization effects. A MAAS that has just allocated one or more addresses SHOULD resend the AIU for those addresses again after [RESEND-WAIT] seconds, and again after a further [RESEND-WAIT]*2 seconds, doubling each time until the interval reaches [REPEAT-INTERVAL] seconds. When a MAAS A receives an ACLM or AITU message from another MAAS B, it SHOULD check its Allocation Record to see whether it believes that any of the addresses in question are already allocated (that is, whether it has received an AIU for those addresses). If so, it SHOULD set an Allocation Defense timer based on the algorithm below and follow the processing rules described in the next two paragraphs. If MAAS A sees an AIU message from someone other than MAAS B containing one or more of the addresses in question before the Allocation Defense timer expires, it SHOULD restart the timer with double its original value. If MAAS A sees an ACLM or AITU message from MAAS B with the same Request Sequence Number and a different set of addresses, it SHOULD cancel the Allocation Defense timer and check this message against the Allocation Record as described above. If MAAS A's Allocation Defense timer expires, it SHOULD send an AIU message containing the addresses in question and restart the timer with twice its previous value, unless that value was 0, in which case it SHOULD set it to [RESEND-WAIT]. If the timer interval becomes Handley and Hanna [Page 9] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 greater than [REPEAT-INTERVAL], the timer SHOULD be cancelled. In this case, the remote MAAS probably suffered some form of failure after sending the ACLM or AITU. The initial value for the Allocation Defense timer is determined as follows: o If MAAS A allocated one or more of the addresses in question, the initial value of the timer is 0. o If MAAS A did not allocate any of the addresses in question, the initial value of the timer (t) is set to a random number between [RESEND-WAIT]*2 and [RESEND-WAIT]*8. 3.2.3 Allocation Conflicts If a MAAS (MAAS A) receives an AIU message for an address that it has already allocated for itself, this indicates that it has an allocation conflict. The MAAS SHOULD attempt to undo its own allocation, notifying all users to stop using the address. If it is able to do this, it SHOULD remove the address from its Allocation Record and stop advertising it using AIU messages. However, this may not always be possible (if the address has been widely advertised, for instance). In any case, a MAAS that is operating as a MADCAP server SHOULD NOT give out an address to MADCAP clients if there is already an allocation conflict for that address. A MAAS MAY log a message when an allocation conflict occurs. 3.2.4 Startup When a MAAS starts up, it MUST choose a random number between [STARTUP-WAIT] and [STARTUP-WAIT]*1.3, set a Startup Timer to expire at that point in the future, and listen on the AAP address until the timer expires. It MUST NOT send any AAP messages during this interval. This randomized timer avoids synchronization effects that might cause a packet storm if a bunch of MAAS's start up simultaneously. For large scopes, a MAAS SHOULD have received at least one ASA message during the startup interval. If it does not receive an ASA message within this time, it MAY allocate addresses only if it has cached a previous ASA message which includes at least one range that has not reached its end time. Handley and Hanna [Page 10] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 3.2.5 Allocating Addresses Using ACLM The simplest way to allocate addresses using AAP is to use the Address Claim (ACLM) message. The MAAS selects one or more addresses and an end time for the claim (using the techniques described in section 3.2.7). It then sends these addresses in an ACLM message. After sending the ACLM message, the MAAS SHOULD then set a Claim Timer for [ANNOUNCE-WAIT] seconds in the future. The MAAS SHOULD also resend the ACLM message after [RESEND-WAIT] seconds, and again after a further [RESEND-WAIT]*2 seconds, doubling each time until the Claim Timer expires. If the MAAS receives an ACLM message or an AIU message from another MAAS listing an address being claimed before the Claim Timer expires, this indicates a collision. It MUST cancel the Claim Timer and give up on the addresses mentioned in the ACLM or AIU message. It MAY choose new addresses (possibly including addresses in the original claim for which no collisions were reported), send another ACLM message with the same Request Sequence Number listing the new addresses, and set a new Claim Timer for [ANNOUNCE-WAIT] seconds in the future. If the MAAS receives an ASA message whose Expiration Time (after adjusting for clock skew, as described in section 5.3.1) is newer than the last ASA message processed and the newer ASA message does not indicate that all of the addresses being claimed are available, the MAAS MUST cancel the Claim Timer and give up on the unavailable addresses. This should not normally happen, since the MAAS should have been aware of the set of available addresses before it sent out the ACLM message and the set of available addresses should not change in a way that invalidates outstanding claims. If the Claim Timer expires, the MAAS can conclude that there is a good probability that the addresses being claimed are unique. It SHOULD then send an AIU message listing those addresses and add the addresses to its list of allocated addresses. 3.2.5.1 Anticipatory Allocation A MAAS may allocate addresses because they are needed to satisfy an immediate demand or in anticipation of a future demand. Anticipatory allocation can reduce the amount of time required for a MAAS to respond to an allocation request. However, MAAS's SHOULD be moderate in their anticipatory allocations, especially those with distant end times. If a MAAS allocates one or more addresses with a distant end time in anticipation of demand and Handley and Hanna [Page 11] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 then the MAAS fails, other MAAS's will defend the allocation and the address space will be effectively lost. Preallocation is a better way to handle this problem, as well as several others. 3.2.6 Preallocating Addresses using AITU Preallocation (using the Address Intent To Use or AITU message) allows a MAAS to indicate which addresses it intends to use in the future. Other MAAS's will attempt to avoid using these addresses. However, these addresses are not completely off-limits, as they would be if the MAAS allocated them (using the AIU message). Other MAAS's are free to allocate preallocated addresses if address space runs low. To preallocate an address, a MAAS selects one or more addresses and an end time for the preallocation (using the techniques described in section 3.2.7). It then sends these addresses in an AITU message. After sending the AITU message, the MAAS SHOULD then set a Preallocation Timer for [ANNOUNCE-WAIT] seconds in the future. The AITU message SHOULD be resent with the same time intervals as an AIU message - i.e. the interval between messages starts at [RESEND- WAIT] seconds and doubles until it reaches [REPEAT-INTERVAL]. As with an AIU message, the MAAS SHOULD vary the interval by about 30% (+ or -) to avoid synchronization effects. If the MAAS receives an ACLM, AITU, or AIU message from another MAAS listing one or more of the addresses being preallocated before the Preallocation Timer expires, this indicates a collision. It MUST cancel the Preallocation Timer and give up on that preallocation. It MAY choose another set of addresses, send another AITU message with the same Request Sequence Number listing the new addresses, set a new Preallocation Timer for [ANNOUNCE-WAIT] seconds in the future, and begin resending the AITU message again. If the MAAS receives an ASA message whose Expiration Time (after adjusting for clock skew, as described in section 5.3.1) is newer than the last ASA message processed and the newer ASA message does not indicate that all of the addresses in the AITU message are available, the MAAS MUST cancel the Preallocation Timer and give up on the unavailable addresses. This should not normally happen, since the MAAS should have been aware of the set of available addresses before it sent out the AITU message and the set of available addresses should not change in a way that invalidates outstanding claims. Handley and Hanna [Page 12] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 If the Preallocation Timer expires, the MAAS can conclude that there is a good probability that there is no collision. It SHOULD continue sending the AITU message listing these addresses and can add the addresses to its list of preallocated addresses. However, if the MAAS receives an AITU, ACLM, or AIU message from another MAAS listing one or more of the preallocated addresses, the MAAS MUST abandon the preallocation. Also, if the MAAS processes an ASA message that does not indicate that all of the addresses in the AITU message are available, the MAAS MUST abandon the preallocation. 3.2.6.1 Allocating a Preallocated Address Once a set of addresses has been preallocated, there should not be any collisions for those addresses. Therefore, the MAAS that preallocated the addresses can skip the ACLM portion of the allocation process and go directly to the normal process of sending an AIU message. To be explicit, when a MAAS that has preallocated some addresses wants to allocate one or more of those addresses, it SHOULD send an AIU message for the addresses, resend the AIU again after [RESEND- WAIT] seconds, and again after a further [RESEND-WAIT]*2 seconds, doubling each time until the interval reaches [REPEAT-INTERVAL] seconds. If the MAAS is allocating only a subset of the addresses that were preallocated, it SHOULD continue sending the AITU message for the remaining preallocated addresses. 3.2.6.2 Benefits of Preallocation Preallocation has several benefits. First, it allows a MAAS to respond to requests for addresses rapidly without requiring the MAAS to allocate addresses in anticipation of demand (which uses up address space needlessly). Second, and most importantly, it provides some protection against network partition. If MAAS's have preallocated addresses before a network partition, they can satisfy allocation requests safely by using those preallocated addresses. Other MAAS's will avoid using those preallocated addresses because they heard the preallocation announcement before the network partition. See section 2.2 for limitations of this technique and more details about handling network partition. Handley and Hanna [Page 13] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 3.2.7 Selecting Addresses for Allocation or Preallocation The first step in allocating or preallocating addresses is to select the addresses to use. The first selection criterion SHOULD be to favor addresses that have not been allocated or preallocated by any other MAAS. This can be determined by consulting the Allocation Record, including the set of addresses advertised in the most recent ASA message. If there are no more addresses that have not been allocated or preallocated by any other MAAS, then preallocation MUST NOT be done. However, allocation (using ACLM) is allowed. For allocation, the next choice SHOULD be addresses that have been preallocated and where the preallocation has been announced recently. After that SHOULD come addresses that have been preallocated and where the preallocation has not been announced recently. The rationale for this preference is that with addresses that have been preannounced recently, the MAAS that preallocated them will probably be able to hear the ACLM messages and stop preallocating the addresses. With addresses that have not been preannounced recently, the MAAS that preallocated them may not be able to hear the ACLM messages (due to network partition or other failure) and may then proceed to allocate them, causing a collision. A further criterion that SHOULD be applied if the first criterion provides several options is that a MAAS SHOULD choose addresses from an address range whose end time is the shortest that will satisfy the requirements of the MAAS. If several options are still available, the MAAS SHOULD favor addresses which are adjacent to other addresses already allocated by the MAAS. This will allow the MAAS to avoid increasing the size of its AIU messages. And if there are still several options available, the MAAS SHOULD choose randomly among the available addresses. This will reduce the likelihood of collisions. 3.2.8 Choosing an End Time for Allocation or Preallocation When allocating or preallocating an address, a MAAS chooses an end time and includes this end time in the ACLM, AIU, or AITU messages that it sends. This is the time until which the addresses should be allocated (or preallocated). After this time, they may be removed from the Allocation Records of other MAAS's in the domain. The allocating MAAS can choose this end time in any way it likes, as long as the end time does not exceed the lifetime listed for that Handley and Hanna [Page 14] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 address in the ASA message. In order to avoid excess traffic, MAAS's SHOULD NOT use many short-lived allocations. Instead, they should use a few long-lived allocations and reuse those addresses. This also has the benefit of ensuring that if the network is partitioned, allocations for MAAS's on one side of the partition will not time out of the Allocation Records of MAAS's on the other side of the partition. A MAAS can change the end time for an allocated or preallocated address at any time by changing it in the AIU or AITU message for that address. This technique can be used to extend an allocation or to shorten it. By reducing the end time to a time a few minutes after the current time, the allocation is effectively deleted. Note that if some MAAS's are partitioned from the network during the time when this deletion is being announced, they may defend the earlier allocation when they are later reconnected. In this case, the MAAS that deleted the allocation SHOULD advertise the allocation again with the correct end time (now in the past) so that it is deleted from the Allocation Records of the MAAS's that were partitioned. No start time is included in any AAP messages because all allocations start immediately. It is too difficult to manage two MAAS's with allocations for the same address at different times. However, a single MAAS can reuse an address for multiple clients over time. 3.2.9 Allocation Failure If no addresses are available that meet the demands placed on the MAAS (either because there are no addresses available at all or because the lifetimes of the available addresses are not long enough), the MAAS should indicate this by sending an Address Not Available (ANA) message. This will allow other MAAS's to note the allocation failure and report it to the Prefix Coordinator in the next ASRP message. The Prefix Coordinator may, in response, attempt to allocate more addresses or get a longer lifetime. Since small scopes do not have Prefix Coordinators, MAAS's MUST NOT send ANA messages for small scopes. Instead, they MAY log the failed allocation so that the administrator can increase the number of addresses in the scope. An ANA message contains an address count and a requested lifetime. When an allocation fails, the MAAS SHOULD assemble and send an ANA message. After sending the ANA message, the MAAS SHOULD set an ANA Retransmission Timer for [ANNOUNCE-WAIT] seconds in the future. The MAAS SHOULD also resend the ANA message after [RESEND-WAIT] seconds, Handley and Hanna [Page 15] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 and again after a further [RESEND-WAIT]*2 seconds, doubling each time until the ANA Retransmission Timer expires. A MAAS that receives an ANA message SHOULD check to see if it already has noted this address request in its Allocation Record (by comparing the number of addresses, lifetime, and Request Sequence number). If not, it SHOULD add the request. Because ANA messages are not repeated indefinitely, each MAAS may have a different set of address requests in its Allocation Record. This is normal and should not cause a problem. Note that allocation failure (and therefore ANA messages) should not be common. Allocations should generally proceed in a predictable manner, so Prefix Coordinators should have enough time to react to changes in demand and supply more addresses before allocations fail. 3.2.10 Interacting with Prefix Coordinators In "large" scopes, one or more Prefix Coordinators handle the interaction between MAAS's within the allocation domain and those in other allocation domains within the scope. In particular, the Prefix Coordinators periodically announce the set of multicast addresses available for allocation within the domain using the Address Space Announce (ASA) message. And MAAS's periodically inform the Prefix Coordinators of how much address space is currently in use, using the Address Space Report (ASRP) message. Prefix Coordinators (along with the ASA and ASRP messages) are not needed or used in small scopes. In a small scope, the complete set of addresses in the scope (as indicated by MZAP) is considered to be available for use within the allocation domain, for an indefinite lifetime. 3.2.10.1 Processing ASA Messages The ASA message lists a number of address ranges, each of which has an associated lifetime. The announcement also contains a timestamp to detect replays or clock skew and an expiration time. Each ASA message MUST contain the complete set of addresses available for a given scope in the allocation domain at the time the message was sent. A Prefix Coordinator MUST NOT attempt to split the available addresses across multiple ASA messages. As described in section 2.1.3, each ASA message MUST pertain only to one scope and each MAAS (and Prefix Coordinator) MUST treat each scope separately. When an ASA message is received, a MAAS SHOULD adjust the Expiration Time for clock skew as described in section 5.3.1 and compare it to Handley and Hanna [Page 16] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 the adjusted Expiration Time of the last ASA message processed. If the adjusted Expiration Time of the newly received ASA message is earlier than or equal to the adjusted Expiration Time of the last ASA message processed, the newly received ASA message SHOULD be ignored. Otherwise, it SHOULD be processed. Under normal circumstances, the set of addresses available in the allocation domain should change in only three ways. First, addresses can be removed once they have reached the end of their lifetime. Second, the lifetime of one or more addresses can be extended. Third, new addresses can be added. Any other change in the set of available addresses (removing addresses, moving their start time later, or making their end time earlier) is called an invalidating change, since it may invalidate MAAS allocations and therefore SHOULD be strongly avoided. If an ASA message being processed does not contain any invalidating changes (as determined by comparing it to the last ASA message processed), it can be processed by updating the set of available addresses in the Allocation Record (and caching the UDP payload of the ASA message, as described later). If the ASA message extends the lifetime of one or more addresses or adds new addresses, any outstanding address requests in the Allocation Record SHOULD be checked to see if they have been satisfied. If so, they SHOULD be removed from the Allocation Record. It may sometimes be necessary to make an invalidating change. If a MAAS detects such a change, it should revise all allocations and preallocations in its Allocation Record to conform with the change. Actually, it need not revise its Allocation Record, but SHOULD behave within AAP as if it has done so. The MAAS or its clients SHOULD also stop using the invalidated addresses in any way which conflicts with their revised status as soon as possible. If a MAAS detects an invalidating change, it MAY log a message or otherwise alert an administrator. An invalidating change is an unusual and highly undesirable situation. ASA messages MAY alternate between several cooperating Prefix Coordinators. One common reason for invalidating changes is when an allocation domain has two Prefix Coordinators whose actions are not coordinated. This is a serious error that may make it nearly impossible for MAAS's to allocate new addresses so this situation should be remedied as soon as possible. To prevent hostile parties from causing a denial of service by sending invalidating ASA messages, ASA messages SHOULD be authenticated and MAAS's SHOULD ignore unauthenticated ASA messages. See section 6 (Security Considerations) for more information. Handley and Hanna [Page 17] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 3.2.10.2 Resending ASA Messages All ASA messages include an Expiration Time. Normally, the Expiration Time is set so that several newer ASA messages will have been sent before an ASA message expires. If an ASA message expires in a MAAS's Allocation Record (that is, no newer ASA messages have been received at the Expiration Time) and the MAAS is not in startup mode, something has gone wrong. Either the Prefix Coordinator has stopped sending ASA messages or they are being lost. Under such a circumstance, a MAAS MAY log an error or notify an operator. However, the MAAS SHOULD continue to work, using the information in the old ASA until the address lifetimes are exceeded. The MAAS SHOULD also resend the information included in the old ASA, as described in the next paragraph. This allows new MAAS's to find out what addresses are available for allocation. It also allows a Prefix Coordinator to recover this information if it has lost it (by losing its stable storage or simply rebooting, if it does not have stable storage) and it cannot recover it via another mechanism (from its MASC peers, for instance). When an ASA message expires, each MAAS SHOULD choose a random number between [ASA-INTERVAL]*0.7 and [ASA-INTERVAL]*1.3. It should set an ASA Resend timer for a time this far in the future. If the timer expires without an ASA message arriving, the MAAS SHOULD send an ASA message with the same contents as the expired ASA message, but with the Current Time field incremented by the amount of time passed since the expired ASA message was received. Updating the Current Time field ensures that anyone who receives the message will be able to adjust the times in the message properly to compensate for clock skew (as described in section 5.3.1). It also ensures that the Current Time will be greater than the Expiration Time, which makes it evident that this is a retransmitted ASA message. If the MAAS receives an ASA with an Expiration Time that is newer (after adjustment for clock skew) than the Expiration Time of the cached message before the timer expires, it SHOULD discard the timer and process the newer ASA message. If, however, the MAAS receives an ASA message that does not have a newer adjusted Expiration Time, the MAAS SHOULD simply reset the ASA Resend timer to a new random number in the same range. 3.2.10.3 Sending ASRP Messages Unless otherwise configured, all MAAS's SHOULD participate in sending Handley and Hanna [Page 18] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 periodic ASRP messages to the AAP address (for large scopes). An ASRP message lists the same address ranges included in the most recent ASA message, along with the number of addresses used in each range. It may also include a list of address requests, each of which contains a number of addresses and a lifetime. As described in section 2.1.3, each ASRP message MUST pertain only to one scope and each MAAS (and Prefix Coordinator) MUST treat each scope separately. Whenever a MAAS completes its [STARTUP-WAIT] period, it SHOULD choose a random number between [ASRP-INTERVAL]*0.7 and [ASRP-INTERVAL]*1.3. It should set an ASRP Send timer for a time this far in the future. If the timer expires without an ASRP message for that scope being received, the MAAS SHOULD send an ASRP message containing a summary of current address space usage in the allocation domain for that scope. If an ASRP message for that scope is received before the timer expires, the MAAS SHOULD reset the ASRP Resend timer to a new random number in the same range. When sending an ASRP message, a MAAS should list each address range included in the most recent ASA message, along with the number of addresses used in each range (calculated by consulting the Allocation Record, including allocated addresses but not preallocated ones). The address requests should be constructed based on the address requests noted in the Allocation Record. These requests SHOULD be combined to ensure that the UDP payload of the ASRP message does not exceed 500 bytes. The address requests SHOULD be combined by finding requests whose end times are similar, adding their counts, and taking the earlier of the two start times. This (and other effects) will cause changes in the address request list from one ASRP message to another, but that is to be expected. 4 Prefix Coordinators A Prefix Coordinator is a host that announces the set of multicast addresses available for use within an allocation domain. Prefix Coordinators are not needed for "small" scopes, where all addresses in the scope are available for use within the allocation domain. The mechanism or protocol by which a Prefix Coordinator determines the set of available addresses is not specified in this document. It may use an inter-domain protocol such as MASC, static allocations by AS number [9], or some other system. It makes no difference to AAP or to the MAAS's. 4.1 Prefix Coordinator Requirements Prefix Coordinators SHOULD listen to and participate in the AAP protocol on a regular basis, in order to send ASA messages and Handley and Hanna [Page 19] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 receive ASRP messages. However, if a Prefix Coordinator is temporarily unable to participate in the AAP protocol, MAAS's within the allocation domain will step in and send ASA messages on its behalf. This ASA resend feature may also be used to restore the state of a Prefix Coordinator which has lost its state. Therefore, Prefix Coordinators need not have stable storage. If their state is lost (during a power failure, for instance), they can use the information in the ASA messages resent by MAAS's to restore their state. However, a prolonged outage on the part of a Prefix Coordinator will result in the expiration of the prefix lifetimes advertised by the Prefix Coordinator in its ASA message. And an inoperative Prefix Coordinator will not be able to respond to changes in demand, as reported by MAAS's using ASRP messages. Therefore, it is best for a Prefix Coordinator to be functioning at all times. A Prefix Coordinator can be a MASC router or another host. But it should be located on a machine with sufficient processing power and network connectivity to participate in the AAP protocol. 4.2 Specification of Prefix Coordinator Behavior The primary function of a Prefix Coordinator is to announce the set of multicast addresses available for use within an allocation domain. It is also responsible for accepting feedback from MAAS's regarding demand for addresses. 4.2.1 Sending ASA Messages The ASA message lists a number of address ranges, each of which has an associated lifetime. The announcement also contains a timestamp to detect replays or clock skew and an expiration time. Each ASA message MUST contain the complete set of addresses available for a given scope in the allocation domain at the time the message was sent. A Prefix Coordinator MUST NOT attempt to split the available addresses across multiple ASA messages. As described in section 4.2.3, each ASA message MUST pertain only to one scope and each MAAS (and Prefix Coordinator) MUST treat each scope separately. When a Prefix Coordinator is ready to begin announcing addresses in an allocation domain, the Prefix Coordinator SHOULD choose a random number between [ASA-INTERVAL]*1.7 and [ASA-INTERVAL]*2.3. It should set an ASA Send timer for a time this far in the future. If the timer expires without a new (not resent) ASA message arriving, the Prefix Coordinator SHOULD send an ASA message and reset the timer to a new random number between [ASA-INTERVAL]*0.7 and [ASA-INTERVAL]*1.3. A Handley and Hanna [Page 20] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 Prefix Coordinator can identify a resent ASA message by checking the Expiration Time in the message. If the Expiration Time exceeds the Current Time in the message, the message has been resent by a MAAS. If a Prefix Coordinator receives a new (not resent) ASA message before the timer expires, it should reset the timer to a new random number between [ASA-INTERVAL]*1.7 and [ASA-INTERVAL]*2.3. If more than one Prefix Coordinator is operating within a domain, this timer mechanism should encourage one of the Prefix Coordinators (the "lead Prefix Coordinator") to take the lead, consistently sending ASA messages. However, if that Prefix Coordinator stops working (due to failure or network partition), another Prefix Coordinator will step in to take its place. The timers used by a Prefix Coordinator MAY be reduced to ensure that it will become the lead Prefix Coordinator. 4.2.1.1 Avoiding Invalidating Changes Under normal circumstances, the set of addresses available in the allocation domain should change in only three ways. First, addresses can be removed once they have reached the end of their lifetime. Second, the lifetime of one or more addresses can be extended. Third, new addresses can be added. Any other change in the set of available addresses (removing addresses, moving their start time later, or making their end time earlier) is called an invalidating change, since it may invalidate MAAS allocations and therefore SHOULD be strongly avoided. One common reason for invalidating changes is when an allocation domain has two Prefix Coordinators which are announcing different sets of available addresses. This is a serious error that may make it nearly impossible for MAAS's to allocate new addresses so this situation should be remedied as soon as possible. If more than one Prefix Coordinator is active within a single allocation domain, the Prefix Coordinators MUST be configured so that their actions are coordinated. They MUST NOT announce different sets of addresses. To detect and correct such a situation, a Prefix Coordinator that detects ASA messages from another Prefix Coordinator that are not consistent with its own SHOULD notify an operator and stop sending ASA messages until it has not heard a new (not resent) inconsistent ASA message for at least [ASA-INTERVAL]*5 seconds. This default behavior may be overridden by configuration. This behavior allows a malicious person to send invalid ASA messages, confusing the MAAS's and keeping the valid Prefix Coordinator from sending ASA messages. The best solution for this problem is for MAAS's and Prefix Coordinators to ignore messages unless they are authenticated. Then the invalid ASA messages will be ignored. Even Handley and Hanna [Page 21] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 without authentication, the valid Prefix Coordinator will notify the operator of the problem and the MAAS's MAY log an error or alert an administrator when they see an invalidating change. 4.2.2 Processing ASRP Messages Prefix Coordinators SHOULD (unless otherwise configured) listen for and process ASRP messages. ASRP messages are sent periodically by MAAS's and are intended to report address space usage to Prefix Coordinators. When a MAAS sends an ASRP message, it includes the address ranges it received in the ASA message it processed most recently, along with the number of addresses used in each range. It may also include a list of address requests, each of which contains a number of addresses and a lifetime. As described in section 2.1.3, each ASRP message MUST pertain only to one scope and each MAAS (and Prefix Coordinator) MUST treat each scope separately. When a Prefix Coordinator receives an ASRP message, it SHOULD ignore the message unless it is the lead Prefix Coordinator (unless otherwise configured). If the Prefix Coordinator is the lead Prefix Coordinator, it SHOULD first check to see whether the address ranges included in the ASRP message match the address ranges that it has most recently announced. If the address ranges do not match, it SHOULD ignore the ASRP message and MAY log a message. Otherwise, the Prefix Coordinator MAY process the data included in the ASRP message in whatever way it deems appropriate. The algorithm used by the Prefix Coordinator to decide what actions to take, if any, and the mechanism or protocol used to effect these actions are beyond the scope of this document. However, with MASC the actions might include a request for more addresses and with a static allocation mechanism the actions might include a notice to an operator that more (or fewer) addresses are needed. Taking no action at all is also acceptable. In general, it is expected that the goals of the Prefix Coordinator in responding to ASRP messages may be as follows. If it notices that there is a growing demand for addresses, it may attempt to allocate more addresses via a higher-level mechanism. If it notices a diminishing demand, it may choose not to extend the lifetime of certain addresses. It may also choose to allocate addresses to respond directly to the list of address requests included in the ASRP message, although this is intended more as an indication of emergent demand than a specific request for addresses. Handley and Hanna [Page 22] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 4.2.3 Handling Multiple Scopes When a Prefix Coordinator is handling multiple scopes at the same time, it should treat each scope separately. Also, as described in section 2.1.3, each AAP message MUST pertain to only one scope. This is especially important when multiple large scopes share a single allocation domain and Allocation Scope, because it allows a MAAS that is not interested in a particular scope to discard messages pertaining to other scopes. 5 Protocol Details This section describes the message formats and specifics of message processing. 5.1 Message Formats AAP messages are binary format, as the additional flexibility of having a textual format is not required in this case. All AAP messages start with a common header, followed by a body whose format differs depending on the message type. Figure 1 shows the format of the header and Table 1 describes each of the fields in the header. The numbers in parentheses indicate the size of each field in octets. The names for the fields given in the figure are used throughout this document to refer to the fields in AAP messages. All multi-octet quantities are in network byte-order. Any message whose UDP data is too short to hold this format (at least 12 bytes) MUST be ignored. +-+-+-+-+-+-+-+-+ | version (1) | +---------------+ | msgtype (1) | +---------------+ | addrfamily | | (2) | +---------------+ | rseq | | (3) | | | +---------------+ | mseq (1) | +---------------+ | | | body | Handley and Hanna [Page 23] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 | (variable) | | ... | +---------------+ Figure 1: Format of an AAP message FIELD OCTETS DESCRIPTION ----- ------ ----------- version 1 Protocol version number (zero for this specification) msgtype 1 Message type (ACLM, AIU, etc.) addrfamily 2 Address family (IPv4, IPv6, etc.) rseq 3 Request sequence number mseq 1 Message sequence number body var Body (format varies by msgtype) Table 1: Description of fields in an AAP message 5.1.1 The version field The version field MUST always be zero for this version of the protocol. Any messages that include other values in this field MUST be ignored. 5.1.2 The msgtype field The msgtype field defines the "type" of a MADCAP message. For more information about this field, see section 5.2. 5.1.3 The addrfamily field The addrfamily field defines the default address family (such as IPv4 or IPv6) for this AAP message, using the address family numbers defined in by the IANA (including those defined in [10]). Unless otherwise specified, all addresses included in the message will be from this family. 5.1.4 The rseq field The rseq field is a Request Sequence Number. The first message that a MAAS or Prefix Coordinator sends after a restart should have a request sequence number of 0 and the request sequence number should be incremented for every subsequent distinct message or request. When an AITU or ACLM message results in a detected clash, a new address is chosen and an new message is sent with the same rseq as the original. In such cases, the message sequence number (mseq) is incremented instead. AIU messages always get new rseq if the addresses in use Handley and Hanna [Page 24] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 change, otherwise mseq is incremented instead. ASA messages always get a new rseq because they may alternate sender between multiple Prefix Coordinators. At peak usage rates of one request per second, it is possible for the rseq space to wrap about every 6 months. It is unlikely that any message sequence will last this long, but it conceivable that an AITU message sequence might do so. Implementors should be aware of this possibility and avoid reusing the rseq value that is in use. 5.1.5 The mseq field The mseq field is a message sequence number that is used to identify different messages of the same request. For example, if a MAAS sends a new ACLM message with rseq=27, mseq=0, and receives an AIU message from another MAAS for the same address, it then chooses a new address and sends a new ACLM message with rseq=27, mseq=1. This may be resent after [RESEND-WAIT] seconds with rseq=27, mseq=2, after [RESEND-WAIT]*2 seconds with rseq=27, mseq=3, etc. After [ANNOUNCE- WAIT] seconds, the MAAS can send an AIU message for the address with rseq=28, mseq=0. mseq may wrap when AITU is sent for longer than about 2 hours (with default timer values) without an address being requested. This should not cause a problem, but if mseq and rseq are being used to monitor loss, this should be taken into account. mseq may also wrap if a long series of address collisions occurs when sending ACLM. Under normal circumstances, this is extremely unlikely and probably signals a denial-of-service attack. Implementors should be aware of this possibility. 5.1.6 The body field The format of the body field varies, depending on the value of the msgtype field. For more information, see section 5.4. 5.2. Message Types The msgtype field defines the type of an AAP message. Legal values for this field are: Value Message Type ----- ------------ 0 Address Claim (ACLM) 1 Address In Use (AIU) 2 Address Intent To Use (AITU) 3 Address Space Announce (ASA) Handley and Hanna [Page 25] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 4 Address Space Report (ASRP) 5 Address Not Available (ANA) Table 2: AAP message types Throughout this document, AAP messages are referred to by the type of the message; e.g., an AAP message with a message type of 1 is referred to as an AIU message. MAAS's and Prefix Coordinators MUST handle all AAP message types defined in this document in a manner consistent with this document. If a MAAS or Prefix Coordinator receives an AAP message whose message type it does not recognize, it MUST ignore the message. New AAP message types may only be defined by IETF Consensus, as described in section 7. For a brief description of the AAP message types, see section 2. For a description of how each message should be handled by MAAS's and Prefix Coordinators, see sections 3 and 4. And for a description of the format of the message body for each message type, see section 5.4. 5.3 AAP Time Fields AAP messages contain a number of places where absolute times must be represented. These time values are represented as unsigned 32 bit integers in network byte order giving the number of seconds since 00:00 UTC, 1st January 1970. This arbitrary baseline is convenient on many current operating systems and can be converted to an NTP [13] timestamp by adding decimal 2208988800. Thus AAP time fields will not wrap until the year 2106. 5.3.1 Correcting for Clock Skew All AAP messages that include an absolute time field also include a Current Time field. This field SHOULD be used to detect and correct for clock skew. The sender SHOULD set the Current Time field to the time when the message is sent (as indicated by the sender's clock). The receiver SHOULD determine the difference between the Current Time indicated in the message and the time when the message is received (as indicated by the receiver's clock). Then it SHOULD add this difference to all times in the AAP message. This will adjust the times to compensate for any clock skew between the sender and the receiver. Unfortunately, it will also cause times in the messages to drift backward due to message transmission time. However, this drift should not accumulate under normal circumstances. Handley and Hanna [Page 26] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 A few seconds' drift should not cause any problems with multicast address allocation, since MAAS's should be allowing minutes or hours of buffer time between allocations, anyway. See Appendix A for an example of correcting for clock skew. 5.4 Body Formats The format of the AAP message body depends on the value of the msgtype field. Here is a description of the body formats associated with all message types defined in this document. 5.4.1 Address Claim (ACLM) The Address Claim (ACLM) message is used by a MAAS to announce addresses that it wants to allocate. Current Time Range 1 Range 2 ... +----+----+----+----+----...----+----...----+----...----+ | current-time | R1 | R2 | | +----+----+----+----+----...----+----...----+----...----+ where each of the Ranges is of the following format: First Last Address Address End Time +----...----+----...----+----+----+----+----+ | first | last | end-time | +----...----+----...----+----+----+----+----+ current-time is the current time at the sending MAAS. first and last are the first and last address in the range of addresses being claimed. The address family of the addresses is determined by the addrfamily field in the message header. end-time is the time when the sending MAAS plans to stop using the addresses. 5.4.2 Address In Use (AIU) The Address In Use (AIU) message is used by a MAAS to announce addresses that it has allocated. Current Time Range 1 Range 2 ... +----+----+----+----+----...----+----...----+----...----+ | current-time | R1 | R2 | | +----+----+----+----+----...----+----...----+----...----+ Handley and Hanna [Page 27] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 where each of the Ranges is of the following format: First Last Address Address End Time +----...----+----...----+----+----+----+----+ | first | last | end-time | +----...----+----...----+----+----+----+----+ current-time is the current time at the sending MAAS. first and last are the first and last address in the range of allocated addresses. The address family of the addresses is determined by the addrfamily field in the message header. end-time is the time when the sending MAAS plans to stop using the addresses. 5.4.3 Address Intent To Use (AITU) The Address Intent To Use (AITU) message is used by a MAAS to announce addresses that wishes to preallocate. Current Time Range 1 Range 2 ... +----+----+----+----+----...----+----...----+----...----+ | current-time | R1 | R2 | | +----+----+----+----+----...----+----...----+----...----+ where each of the Ranges is of the following format: First Last Address Address End Time +----...----+----...----+----+----+----+----+ | first | last | end-time | +----...----+----...----+----+----+----+----+ current-time is the current time at the sending MAAS. first and last are the first and last address in the range of addresses being preallocated. The address family of the addresses is determined by the addrfamily field in the message header. end-time is the time when the sending MAAS plans to stop using the addresses. 5.4.4 Address Space Announce (ASA) The Address Space Announce (ASA) message is used by a Prefix Coordinator to announce the set of multicast addresses and lifetimes Handley and Hanna [Page 28] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 available for allocation within the domain using the Address Space Announce (ASA) message. Current Time Expiration Time Range 1 Range 2 ... +---+---+---+---+---+---+---+---+---...---+---...---+---...---+ | current-time |expiration-time| R1 | R2 | | +---+---+---+---+---+---+---+---+---...---+---...---+---...---+ where each of the Ranges is of the following format: First Last Address Address End Time +----...----+----...----+----+----+----+----+ | first | last | end-time | +----...----+----...----+----+----+----+----+ current-time is the current time at the sending Prefix Coordinator. expiration-time is the time at which MAAS's should start resending this ASA message. first and last are the first and last address in the range of addresses. The address family of the addresses is determined by the addrfamily field in the message header. end-time is the time until which the addresses are available for allocation. 5.4.5 Address Space Report (ASRP) The Address Space Report (ASRP) message is sent by a MAAS to indicate to the Prefix Coordinator(s) how much of the current address space is in use and to request more address space. Current Time Report List Request List +----+----+----+----+----...----+----...----+ | current-time | reports | requests | +----+----+----+----+----...----+----...----+ where the Report List is a single octet count of reports, followed by the reports: Report Count Report 1 Report n +-----+----...----+----...----+----...----+ | n | report-1 | | report-n | +-----+----...----+----...----+----...----+ Handley and Hanna [Page 29] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 and each Report is of the following form: First Last Number of Address Address Addresses In Use +----...----+----...----+----+----+----+----+ | first | last | in-use-count | +----...----+----...----+----+----+----+----+ and the Request List is a single octet count of requests, followed by the requests: Request Count Request 1 Request m +-----+----...----+----...----+----...----+ | m | request-1 | | request-m | +-----+----...----+----...----+----...----+ and each Request is of the following form: Number of Addresses End Time Requested Requested +----+----+----+----+----+----+----+----+ | addrs-requested | end-time-requested| +----+----+----+----+----+----+----+----+ current-time is the current time at the sending MAAS. n is a single octet count of address space reports, one for each address range listed in the most recent ASA message processed. first and last are the first and last address in the range of addresses. The address family of the addresses is determined by the addrfamily field in the message header. in-use-count is an unsigned four-octet number indicating the number of addresses in use in the range. If the number of addresses in use exceeds 0xfffffffe, then 0xffffffff is sent. m is a single octet count of address space requests. addrs-requested is an unsigned four-octet number indicating the number of addresses requested. end-time-requested is the time until which the addresses are desired to be available for allocation. Handley and Hanna [Page 30] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 5.4.6 Address Not Available (ANA) The Address Not Available (ANA) message is sent by a MAAS to indicate that no addresses are available that meet its needs. Current Time Address Count End Time +----+----+----+----+----+----+----+----+----+----+----+----+ | current-time | address-count | end-time | +----+----+----+----+----+----+----+----+----+----+----+----+ current-time is the current time at the sending MAAS. address-count is an unsigned four-octet number indicating the number of addresses needed to satisfy the MAAS's needs. end-time is the time until which the addresses are needed. 6 Security Considerations Most attacks on AAP depend on being able to send a message that will be accepted by MAAS's and Prefix Coordinators as valid. A malicious party could send a false ASA message indicating that no addresses are available. This would cause MAAS's to stop allocating addresses (although they could continue to use addresses that they had already allocated). A false ASA message could also encourage MAAS's to allocate addresses that are already in use in another domain or addresses that will not be routed out of the domain. Another attack is to send an AIU message indicating a conflict whenever a MAAS tries to claim or preallocate an address. This would prevent the MAAS from claiming or preallocating any addresses. One more attack is to send an ASRP message reporting great demand when there is little. This could cause the Prefix Coordinator to allocate addresses that are not needed. Alternatively, a false ASRP could report little usage and demand when in fact there is a lot of usage and demand. This could cause the Prefix Coordinator to allocate too few addresses. Both of these attacks would take a while to effect, since the Prefix Coordinator typically changes the set of addresses available for allocation only slowly in response to long- term trends in demand. Of course, there is no way in the current multicast routing protocols to prevent an unauthorized party from sending data on an arbitrary multicast address or joining an arbitrary multicast group. Therefore, the multicast address allocation architecture is currently advisory in nature. Still, it is desirable to design for the future. Handley and Hanna [Page 31] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 The best way to address these attacks is by authenticating AAP messages and ignoring unauthenticated messages. Therefore, it is RECOMMENDED that when security is deemed necessary for AAP, IPsec be used to authenticate AAP messages and that unauthenticated messages be ignored. As currently specified and implemented, IPsec does not include support for group key establishment. The Secure Multicast Research Group (SMuG) in the IRTF is working on group key establishment and management techniques, but these are not yet ready for standardization. Therefore, for the time being, manual keying will need to be employed to establish and maintain a shared group key. However, it is hoped that the work of the SMuG group will allow for easier key establishment techniques in the future. It should also be mentioned that use of a shared group key does not protect against malicious acts by group members. Because all group members share a single key, it is not possible to securely determine which member sent a given message. In general, this should not be a problem for AAP, since all MAAS's and Prefix Coordinators are generally considered equal peers. But in some environments, this might be useful. Using asymmetric (public key) encryption would make it possible to securely determine which member sent a given message, but would add greatly to the cost of verifying the authenticity of each message. The SMuG group is also working on techniques for securely identifying the sender of a multicast message with greater efficiency. When these techniques are standardized, it may be useful to apply them to AAP. Protecting the confidentiality of AAP messages is not usually considered an important goal. Although some information about current network activities could be derived from monitoring AAP traffic, the same information (or more) could be derived from simple traffic analysis (who's using which multicast groups). Integrity protection for AAP messages is important, but will be taken care of by the IPsec authentication described above. Replay detection in a multicast situation is difficult. Because a shared group key is employed, a per-sender sequence number is not practical. A clock may be used (and all AAP messages include such a clock), but synchronized clocks cannot be assumed and even with synchronized clocks, some leeway must be allowed for transmission delays. Fortunately, replay detection is not a requirement for AAP. Replay of AIU, ANA, AITU messages should not be a problem, since they are supposed to be persistent anyway. Replay of ACLM messages will not Handley and Hanna [Page 32] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 be harmful, since they will be rejected if they interfere with an existing allocation. Replay of ASA messages should not be very problematic, since any messages that are inconsistent with a Prefix Coordinator's own state will be reported by the Prefix Coordinator to an operator. And replay of ASRP messages will simply result in the Prefix Coordinator not responding to changes in demand (which is a permissible action for the Prefix Coordinator, anyway). Once efficient techniques for sender authentication in a group are developed, per-sender sequence numbers should be used for replay detection. 7 IANA Considerations New AAP Message Types may only be defined by IETF Consensus, as described in [12]. Basically, this means that they are defined by RFCs approved by the IESG. 8 Acknowledgments The authors would like to thank the participants of the IETF Multicast Address Allocation Working Group (malloc) and the IETF as a whole for their assistance with this protocol. 9 References [1] Handley, M., D. Thaler, D. Estrin, "The Internet Multicast Address Allocation Architecture", Internet Draft, draft-ietf-malloc-arch-04.txt, January 2000. [2] Estrin, D., R. Govindan, M, Handley, S. Kumar, P. Radoslavov, D. Thaler, "The Multicast Address Set Claim (MASC) Protocol", Internet Draft, draft-ietf-malloc-masc-05.txt, January 2000. [3] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, March 1997. [4] Deering, S., "Host Extensions for IP Multicasting", RFC 1112, August 1989. [5] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6) Specification", RFC 2460, December 1998. [6] Hinden, R. and S. Deering, "IP Version 6 Addressing Architecture", RFC 2373, July 1998. [7] Meyer, D., "Administratively Scoped IP Multicast", RFC 2365, July 1998. Handley and Hanna [Page 33] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 [8] Hanna, S., B. Patel, M. Shah, "Multicast Address Dynamic Client Allocation Protocol (MADCAP)", RFC 2730, December 1999. [9] Meyer, D., and P. Lothberg, "GLOP Addressing in 233/8", RFC 2770, February 2000. [10] Handley, M., Thaler, D., and R. Kermode, "Multicast-Scope Zone Announcement Protocol (MZAP)", RFC 2776, February 2000. [11] Reynolds, J. and J. Postel, "Assigned Numbers", RFC 1700, October 1994. [12] Alvestrand, H. and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", RFC 2434, October 1998. [13] Mills, D., "Network Time Protocol (Version 3) Specification, Implementation and Analysis", RFC 1305, March 1992. 10 Authors' Addresses Mark Handley AT&T Center for Internet Research at ISCI (ACIRI) 1947 Center St., Suite 600 Berkeley, CA 94704 Email: mjh@aciri.org Stephen R. Hanna Sun Microsystems, Inc. One Network Drive Burlington, MA 01803 Phone: +1.781.442.0166 Email: steve.hanna@sun.com Appendix A: Examples This appendix includes several examples of typical AAP protocol exchanges. 1. Address Allocation In this example, MAAS A wants to allocate an address. It has already determined its scope list (probably using MZAP). It has listened to the AAP address for the scope in which it wants to allocate the address and built up an Allocation Record for that scope, using ASA, AITU, AIU, and other messages received on that address and referring to addresses in the scope. The MAAS begins by choosing an address and end time using the Handley and Hanna [Page 34] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 techniques describe in section 3.2.7. Then it sends an ACLM message listing the address to be allocated and the end time. It sets a Claim Timer for [ANNOUNCE-WAIT] seconds in the future. It resends the ACLM message after [RESEND-WAIT] seconds and again after a further [RESEND-WAIT]*2 seconds, doubling each time until the Claim Timer expires. The other MAAS's check their Allocation Records when they receive the ACLM messages. In this case, they have not received any AITU or AIU messages referring to this address so they do not do anything in response to the ACLM message. The Prefix Coordinator ignores the ACLM message because it always ignores all messages except ASA, ASRP, and ANA messages. After the Claim Timer expires, the allocating MAAS updates its Allocation Record to indicate that the address is allocated for itself and adds the address to the set of addresses announced in its AIU message. Then it begins sending an AIU message, resending the AIU again after [RESEND-WAIT] seconds, again after a further [RESEND- WAIT]*2 seconds, and so on until the interval reaches [REPEAT- INTERVAL] seconds. At this point, it will resend the AIU message every [REPEAT-INTERVAL] (plus or minus 30% to avoid synchronization effects). In the figure below, only the first AIU message is shown. Handley and Hanna [Page 35] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 Prefix MAAS A MAAS B Coordinator v v v | | | | | | | _____________/|\_____________ | |/ ACLM | ACLM \| | _____________/|\_____________ | |/ ACLM | ACLM \| | | | | | | | _____________/|\_____________ | |/ ACLM | ACLM \| | | | | | | | | | | | | | | | | | | | _____________/|\_____________ | |/ ACLM | ACLM \| | | | | | | | | | | | | | _____________/|\_____________ | |/ AIU | AIU \| | | | v v v Figure 2: Timeline diagram of messages exchanged in Address Allocation example 2. Preallocation In this example, MAAS A wants to preallocate a set of addresses, in anticipation of future demands. It has already determined its scope list and built its Allocation Record. The MAAS begins by choosing a set of addresses and an end time using the techniques describe in section 3.2.7. Then it sends an AITU message listing the addresses to be preallocated and the end time. It sets a Preallocation Timer for [ANNOUNCE-WAIT] seconds in the future. It resends the AITU message after [RESEND-WAIT] seconds and again after a further [RESEND-WAIT]*2 seconds, planning to double each time until it reaches [REPEAT-INTERVAL]. When MAAS B receives the AITU message, it checks the status of the Handley and Hanna [Page 36] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 specified addresses (using its Allocation Record). It discovers that one of the addresses chosen by MAAS A was earlier allocated by MAAS C (which is down for maintenance). MAAS B sets an Allocation Defense timer for a random value between [RESEND-WAIT]*2 and [RESEND-WAIT]*8. MAAS B does not see any AIU messages pertaining to the address in question, so when the Allocation Defense timer expires, MAAS B sends an AIU message for the address and resets its Allocation Defense Timer to double the previous value. When MAAS A receives the AIU message from MAAS B, it marks the address listed in the message as allocated, cancels its Preallocation Timer, and gives up on this preallocation. Then it chooses a new set of addresses and starts the preallocation process again. This second preallocation effort is indicated with the AITU' messages in the figure below. MAAS B retransmits its AIU message two more times, doubling its Allocation Defense Timer each time. After that, doubling the timer would cause it to be greater than [REPEAT-INTERVAL], so the timer is cancelled. MAAS A receives the retransmitted AIU messages, but finds that they are already reflected in its Allocation Record and therefore takes no action based on them. MAAS A does not receive any ACLM, AITU, or AIU messages overlapping the set of addresses chosen for its second preallocation effort before its Preallocation Timer expires. Therefore, this effort is successful. The addresses are marked as preallocated and MAAS A continues to send an AITU message for them every [REPEAT-INTERVAL] (+/- 30%). At some later time, MAAS A could quickly allocate one or more of the preallocation addresses by skipping the ACLM portion of the allocation process and going directly to sending an AIU (starting with an interval of [RESEND-WAIT] and increasing to [REPEAT- INTERVAL]). Alternatively, another MAAS could notice a collision while MAAS A was still sending the AITU messages (perhaps because of a healed network partition) and send an AIU message, causing MAAS A to abandon its preallocation. Or if address space was low, another MAAS might allocate the addresses using an ACLM message, even though they had been preallocated by MAAS A. None of these examples are shown here. Handley and Hanna [Page 37] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 The figure below shows this exchange, omitting some of the later retransmissions. Prefix MAAS A MAAS B Coordinator v v v | | | | | | | _____________/|\_____________ | |/ AITU | AITU \| | _____________/|\_____________ | |/ AITU | AITU \| | | | | | | | _____________/|\_____________ | |/ AITU | AITU \| | | | | | | | ______________|______________/| |/ AIU |/ AIU | | | | | | | | _____________/|\_____________ | |/ AITU' | AITU' \| | _____________/|\_____________ | |/ AITU' | AITU' \| | | | | | | | _____________/|\_____________ | |/ AITU' | AITU' \| | ______________|______________/| |/ AIU |/ AIU | | | | | | | | | | | | | | _____________/|\_____________ | |/ AITU' | AITU' \| | | | | | | v v v Figure 3: Timeline diagram of messages exchanged in Preallocation example Appendix B: Recommended Constant Values Table 3 lists recommended values for constants defined in this Handley and Hanna [Page 38] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 specification. Constant Name Recommended Value ------------- ----------------- [STARTUP-WAIT] 150 seconds [ANNOUNCE-WAIT] 10 seconds [RESEND-WAIT] 1 second [REPEAT-INTERVAL] 30 seconds [ASA-INTERVAL] 30 seconds [ASRP-INTERVAL] 30 seconds Table 3: Recommended Constant Values Appendix C: Change Log Note to the RFC Editor: This section should be removed before publication. Changes since draft-ietf-malloc-aap-03.txt: * Removed scaling analysis. * Updated references. Changes since draft-ietf-malloc-aap-02.txt: * Noted reserved port number: 2878. * Removed Appendix D (Unresolved Issues). * Added scaling analysis (section 6). * Added recommendation that hosts use MADCAP instead of AAP if a MADCAP server is available. * Changed last step in address selection preference algorithm (section 3.2.7) to choose randomly. This should reduce the likelihood of collisions. * Added discussion of allocation conflicts (section 3.2.3). * Added examples (Appendix A). Changes since draft-ietf-malloc-aap-01.txt: * Fixed formatting in Appendix C. * Merged several sections and subsections into section 2. * Removed the definition of Allocation Scope, since that is now defined in the Architecture document. * Updated the reference to the architecture document. * Renumbered the various drafts to conform to the Internet Drafts editor's ideas. They think that the June 1999 draft was -00 and the rewrite draft was -01. And they insist this cannot be changed. So I have decided to agree with them. This draft will be -02. Handley and Hanna [Page 39] Internet Draft draft-ietf-malloc-aap-04.txt June 2000 Changes since draft-ietf-malloc-aap-00.txt: * Complete rewrite. Many details filled in. * Use IPsec for security. * Added support for IPv6 addresses. * Added ANA message. Handley and Hanna [Page 40]