Mboned Working Group Roger Kermode Internet Engineering Task Force Motorola INTERNET-DRAFT Dave Thaler
22 January 19995 September 2000 Microsoft Expires 22 July 19995 March 2001 Scoped Address Discovery Protocol (SADP) <draft-ietf-mboned-sadp-01.txt><draft-ietf-mboned-sadp-02.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." To view theThe list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories, seeDirectories can be accessed at http://www.ietf.org/shadow.html. Abstract This document defines an application-layer protocol, the Scoped Address Discovery Protocol (SADP), for discovering the scoped multicast address(es) associated with a session at particular scopes within a hierarchically nested set of multicast scopes. SADP is designed to work within the context of Multicast Address Allocation Architecture [MAAA]. It is intended that SADP will provide the necessary general services for reliable multicast and searching applications to use expanding-scope searches in lieu of the well known, but less efficient expanding-ring search. Copyright Notice Copyright (C) The Internet Society (1999).(2000). All Rights Reserved. Contents Abstract. . . . . . . . . . . . . . . . . . . . . . . . . 1 1. Introduction. . . . . . . . . . . . . . . . . . . . . 3 2. Overview. . . . . . . . . . . . . . . . . . . . . . . 4 3. Usage . . . . . . . . . . . . . . . . . . . . . . . . 6 3.1 Session Identifiers . . . . . . . . . . . . . . . . 6 3.2 Session Member Operation. . . . . . . . . . . . . . 6 3.3 SADP Server Operation . . . . . . . . . . . . . . . 7 4. Packet Formats. . . . . . . . . . . . . . . . . . . . 8 4.1 SADP Request. . . . . . . . . . . . . . . . . . . . 10 4.2 SADP Response . . . . . . . . . . . . . . . . . . . 10 4.24.3 SADP New Address. . . . . . . . . . . . . . . . . . 11 5. Constants . . . . . . . . . . . . . . . . . . . . . . 11 6. Security Considerations . . . . . . . . . . . . . . . 1112 7. Acknowledgements. . . . . . . . . . . . . . . . . . . 1112 8. References. . . . . . . . . . . . . . . . . . . . . . 1112 9. Author's Address. . . . . . . . . . . . . . . . . . . 1213 10. Full Copyright Statement. . . . . . . . . . . . . . . 1214 1. Introduction Administrative scoping [RFC2365] provides a useful means for limiting the spread of IP multicast traffic across the Internet. Unlike Time- To-Live (TTL) scoping, administrative scoping provides the means to ensure that, for a given scope and ignoring packet loss, the same set of nodes will receive a message, regardless of which node sent the message. Thus, the use of administrative scoping greatly simplifies the design of multicast protocols that require localization, since the non-reception of sent packets is solely due to loss and not design. The Multicast Address Dynamic Client Allocation Protocol (MADCAP) [MADCAP][RFC2730, NESTOPT] will provide applications with the means for discovering the various scopes that are locally visible at each point in the Internet. The determination of which scopes nest inside each other will be performed by the Multicast-Scope Zone Announcement Protocol (MZAP) [MZAP].[RFC2776]. MZAP's ability to provide this service will allow scopes to be arranged into hierarchies so that applications can then use expanding scope searches instead of the less efficient and more problematic expanding-ring (TTL) searches. One example of how expanding-scope searches provide increased localization can be found in the Scoped Hybrid Automatic Repeat reQuest with Forward Error Correction (SHARQFEC) reliable multicast protocol [SHARQFEC]. While expanding-ring searches use one multicast address and increasing TTLs, expanding-scope searches involve changing the multicast addresses for each attempt at a different scope. For well- known services, these addresses can be obtained by applying an IANA- assigned offset from the top of the scope's address range. Applications, on the other hand, generally require the use of dynamically allocated addresses with offsets that will most likely vary from scope to scope. SADP builds upon the Multicast Address Allocation Architecture [MAAA] by adding a new application-layer service that allows applications to discover the relevant multicast address(es) associated with a session at each level in a hierarchy of scopes. SADP does not provide the means to allocate an address should one not be present for a session in a particular zone. In this case the application should take steps to obtain an address for that scope and then announce it to other application instances that join that scope at a later time. One proposed mechanism for allocating addresses is the Multicast Address Dynamic Allocation Protocol (MADCAP) [MADCAP].[RFC2730]. 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 [RFC2119]. 2. Overview Administrative scoping affords the ability to create network partitions or zones in which multicast traffic addressed to one of a block of addresses assigned to that zone will be limited to that zone. The boundary of the zone is enforced by Zone Border Routers (ZBRs) that reside at the edges of the zone. ZBRs must be carefully configured so that traffic addressed within the zone does not pass outside the zone. Ensuring consistency among boundary routers can be a non-trivial task, and hence the Multicast Zone Announcement Protocol (MZAP) [MZAP],[RFC2776], which is used to announce the existence of zones, also provides the mechanisms to detect ZBR misconfigurations. . . . . . . . . . +B+------> . . / . * . <---+A*--------+C+---> . + . . / . . Zone X <--- . . . . . . . ... A, B, C - Routers * - border interface + - interface . - border Figure 1: Admin scope zone border example Zones may be of different sizes and can also overlap. In addition to the services of zone announcement and fault detection, MZAP also provides mechanisms for determining and announcing the existence of zones that nest inside others as shown in Figure 2. +-----------+ +-----------+ +-------------+ | zone a | | zone c | | zone e | | +------+| | +------+ | . . . . .|. . | |zone b|| | |zone d| | : zone f | : | +------+| | | | | : | : +-----------+ +----+------+ +-------------+ : : . . . . . : (a) "Contained" (b) "Common Border" (c) "Overlap" zone b nests zone d nests zones e and f inside zone a inside zone c do not nest Figure 2: Zone nesting examples This feature allows admin scope zones to be arranged in a hierarchy as shown in Figure 3. The ability to nest admin scope zones in hierarchies like that shown in Figure 3 is useful since it affords localization through expanding-scope searches. For example, consider a distributed application with session members distributed evenly through out zone a. A session member in scope e, would perform a search by multicasting a query within scope e, and if unsuccessful, expand the scope to search in scope b, and eventually scope a if so needed. . . . . . . . . . . . . . . . . . . . scope a . Scope Boundaries . . . = scope a . _______________ ________________ . - = scopes b,c . / scope b \ / scope c \ . # = scopes d,e,f, & g .| | | |. .| ##### ##### | | ##### ##### |. .| #scope# #scope#| | #scope# #scope# |. .\ # d # # e # | | # f # # g # /. .\ #### #####/ #### #### /. .\____________/ _____________/. . . . . . . . . . . . . . . . . . Figure 3 : Admin Scope Zone Nesting Hierarchy example In order for expanding-scope searches to be feasible, session members must be able to determine two things: o which scopes are involved in the hierarchy for a particular session. o what address(es) are to be used for communicating with other session members within these scopes. SADP affords the ability to discover this information by using a single multicast group inside each scope [SADP-RELATIVE-GROUP] for communication between SADP servers (see section 3.2) and the members of various sessions. New members to a session use the channels provided by the addresses to query existing SADP servers and session members as to which specific scopes are valid and which scopes to use. Since there is only one multicast address used per admin scope zone for this purpose, members of a particular session will ignore traffic intended for members of another session. 3. Usage In this section we summarize how session members can use SADP to determine which admin zones are used by the session's hierarchy and also the address(es) within these zones that are used by the current session members should such addresses exist. 3.1 Session Identifiers Each session that uses administrative scoping will be identified by a Session Identifier (SID) that corresponds to the address of the group used in the largest scope zone. Applications that require multiple addresses shall be decomposed into multiple individual sessions which will then be treated independently. 3.2 Session Member Operation Several predefined administrative scopes already exist [RFC2365]: o Link Local: Traffic is only carried across one physical link. o Local: Traffic is restricted to a specific network region. o Global: The entire multicast enabled network. By definition Link Local scopes nest inside Local scopes which in turn nest inside the Global Scope. Other scopes may exist between the local and global scopes. These scopes are constructed by the union of the admin scope zones that correspond to two or more topologically adjacent local scopes and are announced to routers within their confines using MZAP [MZAP].[RFC2776]. The general algorithm that new members to a session should use to determine which scopes and addresses are involved in the hierarchy for a particular session is as follows: 1) Determine largest scope, and address for the largest scope for the session. (this task is beyond the scope of this document, but can be assumed to involve some kind of out-of-band communication.) 2) Starting with the SADP group [SADP-RELATIVE-GROUP] for the local scope, issue a SADP Request (SADP_REQ) message containing the SID address. 3) Wait for a response on the SADP [SADP-RELATIVE-GROUP] address for at least [SADP-REQ-TIMEOUT] seconds. If no response is heard, wait for some small amount of time, and then repeat the request at the same scope. 4) If after a total of 32 attempts at a given scope, no response has been received, increase the scope to the next largest scope and repeat steps 2 and 3. In cases where there are two non-nesting scopes larger than the current, try one scope and then the other, should the first scope not result in a reply. 5) Continue steps 2), 3), and 4) until the largest scope has been queried or a response has been heard. In cases where the scope must be increased in order to find a session member that can reply, the new session member MAY decide to add levels to the hierarchy in order to increase localization for future session members. New session members that decide to take this step will use the existing addresses as discovered using SADP and request new ones. (e.g., via MADCAP [MADCAP]).[RFC2730]). Upon the successful allocation of a new address for use in the hierarchy, the new session member shall announce the new address via a SADP_NEW_ADDR message to the [SADP-RELATIVE-GROUP] address for the scope in which the address was allocated. This will cause the address to be cached by any SADP servers within the new address's scope. SADP servers and existing session members, upon hearing an SADP_REQ message from a new session member from [SADP-RELATIVE-GROUP] at a particular scope will issue an SADP Response (SADP_RESP) to the [SADP-RELATIVE-GROUP] at the same scope after waiting for a random amount of time (T) that is calculated as follows:follows [HAND98]: Choose a random value X from a uniform random interval [0:1] Let C = 256 Set T = [SADP-SUPPRESSION-INTERVAL] log( C*X + 1) / log(C) Should a member receive a SADP_RESP before its timer it expires it SHALL suppress its own response. This method ensures that close to one session member will respond. 3.3 SADP Server Operation Were SADP to be deployed in a wide scale session with the members of various sessions to use SADP between each other it would quickly cause catastrophic congestion. The reason for this is that whenever a new node joined a sparsely populated session with a large maximum scope, it would inevitably end up sending SADP_REQs to every scope up until the largest scope. Thus the highly likely occurrence of having a global and continental scopes combined with numerous sparse sessions (probably on the order of 10,000 to 100,000) would quickly cause SADP_REQ flooding at the continental scope. To address this shortcoming SADP allows, and in fact encourages, the deployment of SADP servers. These servers subscribe to the [SADP- RELATIVE-GROUP] for each scope they are in and cache the SADP_RESP messages they receive at each scope. Having cached and merged the responses for sessions at various scopes, they can then respond to SADP_REQs heard at lower scopes using the information heard at the larger scope(s). Should a SADP server hear a SADP_REQ at some intermediate scope it MUST NOT announce address information for scopes smaller than one on which the SADP_REQ was received. The effect of allowing larger-scoped information to be announced at lower scopes by SADP servers significantly reduces the number of scopes a new session will have to query. New session members now need only expand the scope until a SADP server is found. This is a marked improvement over the case where no SADP servers exist and the search must continue until an existing session member is found. An analysis of how the pressence of SADP Servers improve SADP protcol performance can be found in [KT99]. Scope b Boundary Scope a : Scope a and Scope b _________ : ____________ _____________ / \ : / \ / \ |Source at| _____:___\ |SADP Server | /___________ | New Session | |Scope a | SADP_RESP/ | Scopes a,b | \ SADP_REQ | Member | \_________/ : \____________/ ___________\ | Scopes a,b | : SADP_RESP/ \_____________/ : Figure 4 : SADP Server acting as proxy session member 4. Packet Formats All SADP messages are sent over UDP, with a destination port of [SADP-PORT]. The common SADP message header (which follows the UDP header), is shown below, 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 | PTYPE | Num Scopes | Addr Family | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Largest Scope GroupSession ID Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + | Authentication Block | + + | | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Version: 8 bits The version defined in this document is version 0. Packet Type (PTYPE): 8 bits The packet types defined in this document are: 0: SADP Request 1: SADP Response 2: SADP New Address Number of Scope Entries (Num Scopes) : 4 bits The number of scope entries present within a SADP_RESP message. This field should be set to zero for SADP_REQ messages. Address Family (AddrFam): 4 bits This indicates the IANA-assigned address family number to be used for address contained in this message. Currently assigned values are listed in RFC 1700[RFC1700]. The values for IP addresses are: IPv4: 1 IPv6: 2 Session ID Address: 32 bits (IPv4) or 128 bits (IPv6) The group address corresponding to the largest scope for this hierarchy of addresses. Authentication Block: The Authentication Block provides information which can be used to confirm that the sender of the SADP message is a valid member of the session. Session Members that cannot confirm that the sender of ana SADP Request Message is a session member or a known SADP Server MAY ignore it, while new session members that receive ana SADP Response Message MUST ignore it. (The format of theThe authentication block consists of an MD5 digest that is constructed by applying the MD5 algorihtm [RFC1321] to be decided)these items in the following order: 1) Session Identifer Address 2) Address of the Session Member making the announcement 3) The contents of any subsequent SADP Response or SADP New Address message data. 4.1 SADP Request SADP Request (SADP_REQ) Messages have PTYPE=0, and are sent by new session members that wish to learn which administrative scopes and multicast addresses to use within a particular session. SADP_REQ Messages are sent according to the algorithm described in 3.2. 4.2 SADP Response The SADP Response (SADP_RESP) Message has PTYPE=1, and is sent in response to a SADP_REQ Message to the same scope from which the SADP_REQ was received. It contains the address that is to be used by an application instance within a session for each scope that nests within the scope to which the SADP_REQ was sent. (N.B. This includes the scope to which the SADP_REQ was sent) Session members that transmit SADP Response Messages MUST NOT include scope and address information for scopes that are known to overlap or be larger than that of the scope upon which the triggering SADP_REQ Message was The format for a SADP Response Message is shown below: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ SADP Header +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ | Scope Start Address 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Scope 1 Session Address | +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ . . . . . . . +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ | Scope Start Address N | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Scope N Session Address | +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ Scope X Start Address : 32 bits (IPv4) or 128 bits (IPv6) The smallest address for the block of multicast addresses associated with a scope. If a scope X is valid for the range 220.127.116.11 to 18.104.22.168, this field will be set to 22.214.171.124. Scope X Session Address : 32 bits (IPv4) or 128 bits (IPv6) Address to be used for the named scope. 4.24.3 SADP New Address The SADP New Address (SADP_NEW_ADDR) Message has PTYPE=2. It is transmitted by session members that have attempted to find an address for a particular scope, failed, and have then subsequently allocated a new address for use in the session at that scope. Its purpose is to inform other members of the session of the existence of this newly allocated address and its availability for subsequent use. Should two members attempt to announce a new address to the same scope at the same time, their SADP_NEW_ADDR messages will result in a collision. SADP_NEW_ADDR collisions are resolved by the session members picking the lower of the two addresses. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ SADP Header +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ | Scope Start Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | New Scope Session Address | +=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ Scope Start Address : 32 bits (IPv4) or 128 bits (IPv6) The smallest address for the block of multicast addresses associated with a scope. If a scope X is valid for the range 126.96.36.199 to 188.8.131.52, this field will be set to 184.108.40.206. New Scope Session Address : 32 bits (IPv4) or 128 bits (IPv6) Address of the newly allocated group to be used for the specified scope. 5. Constants [SADP-RELATIVE-GROUP]: The relative group with each scope, to which session members send SADP Requests and Responses. All application instances that use SADP for constructing hierarchies of scopes MUST subscribe to this address for each scope which nests within the session scope, in order to ensure that each application instance uses the hierarchy in the most efficient manner. [SADP-REQ-TIMEOUT]: The time after which a session member that sends SADP Request should wait before concluding that no session members are present at the current scope. Default value is 3 seconds. [SADP-SUPPRESSION-INTERVAL]: The interval over which a session member chooses a random delay before responding to SADP Request. Default value 2 seconds. 6. Security Considerations SADP employs distributed mechanisms to allow new session members to learn of the existence of session-specific admin scoped multicast address. This fact lays SADP open to attack by malicious hosts that could potentially mis-inform new session members of incorrect addresses, thereby affecting a man-in-the-middle attack. To prevent attacks of this nature by non-session members from occurring all SADP messages are signed by the sender. However, this measure does not prevent malicious hosts from joining a session and then performing the same attack. Hence, SADP's security depends upon a suitable gating process for new-member admittance combined with (as yet to be determined) mechanisms that allow spoofed SADP messages to be identified for removal before processing. 7. Acknowledgments The Authors would like to acknowledge Mark Handley for the helpful discussions and feedback which helped shape and refine this document. 8. References [MADCAP] Patel. B.V., Shah, M., Hanna, S.R., "Multicast Address Dynamic Client Allocation Protocol (MADCAP)", Internet Draft, draft-ietf-malloc-madcap-03.txt, February 1999.[MAAA] Handley, M., Thaler, D., and D. Estrin, "The Internet Multicast Address Allocation Architecture", Internet Draft, December 1997. [MZAP]draft-ietf-malloc-arch-**.txt, June 2000. [HAND98] Handley, M., "Session directories and scalable internet multicast address allocation for private internets", In Proceedings of ACM SIGCOMM, pp 105-116, 1998. [SHARQFEC] Kermode, R., "Scoped Hybrid Automatic Repeat reQuest with Forward Error Correction (SHARQFEC)", ACM SIGCOMM98, Vancouver Canada, September 1998. [NESTOPT] Kermode, R., "MADCAP Multicast Scope Nesting State Option", draft-ietf-malloc-madcap-nest-opt-05.txt, April, 2000. [KT99] Kermode, R., & Thaler, D., "Multicast-Scope Zone Announcement Protocol (MZAP)", draft-ietf-mboned-mzap-02.txt, Internet-Draft, August, 1998."Support for reliable Sessions with a Large Number of Members", First International Workshop on Networked Group Communication, Pisa Italy, November 1999 [RFC1321] Rivest, R. and S. Dusse, "The MD5 Message-Digest Algorithm", RFC 1321, April 1992. [RFC1700] Reynolds, J., Postel, J., "Assigned Numbers", RFC 1700, October 1994. [RFC1884] Hinden, R., Deering, S., "IP Version 6 Addressing Architecture", RFC 1884, December 1995. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP, RFC 2119, March 1997. [RFC2365] Meyer, D., "Administratively Scoped IP Multicast", BCP, RFC 2365, July 1998. [SHARQFEC] Kermode, R., "Scoped Hybrid Automatic Repeat reQuest with Forward Error Correction (SHARQFEC)", ACM SIGCOMM98, Vancouver Canada, September 1998.[RFC2730] Patel. B.V., Shah, M., Hanna, S.R., "Multicast Address Dynamic Client Allocation Protocol (MADCAP)", RFC2730, December 1999. [RFC2776] Handley, M., Thaler, D., "Multicast-Scope Zone Announcement Protocol (MZAP)", RFC 2776, February 2000 9. Authors' Addresses Roger Kermode Motorola Australia Research Centre 12 Lord St. Botany, NSW 20912019 Australia Email: Roger_Kermode@email.mot.comRoger.Kermode@motorola.com David Thaler Microsoft One Microsoft Way Redmond, WA 98052 USA Email: firstname.lastname@example.org 10. Full Copyright Statement Copyright (C) The Internet Society (1999).(2000). 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 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."