--- 1/draft-ietf-p2psip-service-discovery-08.txt 2013-08-05 11:14:22.928974185 -0700 +++ 2/draft-ietf-p2psip-service-discovery-09.txt 2013-08-05 11:14:22.968975287 -0700 @@ -1,87 +1,87 @@ P2PSIP Working Group J. Maenpaa Internet-Draft G. Camarillo Intended status: Standards Track Ericsson -Expires: August 27, 2013 February 23, 2013 +Expires: February 06, 2014 August 05, 2013 Service Discovery Usage for REsource LOcation And Discovery (RELOAD) - draft-ietf-p2psip-service-discovery-08.txt + draft-ietf-p2psip-service-discovery-09.txt Abstract REsource LOcation and Discovery (RELOAD) does not define a generic service discovery mechanism as a part of the base protocol. This document defines how the Recursive Distributed Rendezvous (ReDiR) service discovery mechanism used in OpenDHT can be applied to RELOAD overlays to provide a generic service discovery mechanism. -Status of this Memo +Status of This Memo - This Internet-Draft is submitted to IETF in full conformance with the + This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. 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." - This Internet-Draft will expire on August 27, 2013. + This Internet-Draft will expire on February 06, 2014. Copyright Notice Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents - 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 - 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 + 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 + 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Introduction to ReDiR . . . . . . . . . . . . . . . . . . . . 4 - 4. Using ReDiR in a RELOAD Overlay Instance . . . . . . . . . . . 7 - 4.1. Data Structure . . . . . . . . . . . . . . . . . . . . . . 7 - 4.2. Selecting the Starting Level . . . . . . . . . . . . . . . 8 - 4.3. Service Provider Registration . . . . . . . . . . . . . . 9 - 4.4. Refreshing Registrations . . . . . . . . . . . . . . . . . 9 + 4. Using ReDiR in a RELOAD Overlay Instance . . . . . . . . . . 7 + 4.1. Data Structure . . . . . . . . . . . . . . . . . . . . . 7 + 4.2. Selecting the Starting Level . . . . . . . . . . . . . . 8 + 4.3. Service Provider Registration . . . . . . . . . . . . . . 8 + 4.4. Refreshing Registrations . . . . . . . . . . . . . . . . 9 4.5. Service Lookups . . . . . . . . . . . . . . . . . . . . . 10 - 4.6. Removing Registrations . . . . . . . . . . . . . . . . . . 11 - 5. Access Control Rules . . . . . . . . . . . . . . . . . . . . . 12 + 4.6. Removing Registrations . . . . . . . . . . . . . . . . . 11 + 5. Access Control Rules . . . . . . . . . . . . . . . . . . . . 11 6. REDIR Kind Definition . . . . . . . . . . . . . . . . . . . . 12 - 7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 - 7.1. Service Registration . . . . . . . . . . . . . . . . . . . 13 - 7.2. Service Lookup . . . . . . . . . . . . . . . . . . . . . . 15 - 8. Overlay Configuration Document Extension . . . . . . . . . . . 15 - 9. Security Considerations . . . . . . . . . . . . . . . . . . . 16 - 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16 - 10.1. Access Control Policies . . . . . . . . . . . . . . . . . 16 - 10.2. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . . 16 - 10.3. ReDiR Namespaces . . . . . . . . . . . . . . . . . . . . . 16 - 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 17 - 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17 - 12.1. Normative References . . . . . . . . . . . . . . . . . . . 17 - 12.2. Informative References . . . . . . . . . . . . . . . . . . 17 - Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 17 + 7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 12 + 7.1. Service Registration . . . . . . . . . . . . . . . . . . 13 + 7.2. Service Lookup . . . . . . . . . . . . . . . . . . . . . 14 + 8. Overlay Configuration Document Extension . . . . . . . . . . 15 + 9. Security Considerations . . . . . . . . . . . . . . . . . . . 15 + 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 + 10.1. Access Control Policies . . . . . . . . . . . . . . . . 15 + 10.2. Data Kind-ID . . . . . . . . . . . . . . . . . . . . . . 16 + 10.3. ReDiR Namespaces . . . . . . . . . . . . . . . . . . . . 16 + 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16 + 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 17 + 12.1. Normative References . . . . . . . . . . . . . . . . . . 17 + 12.2. Informative References . . . . . . . . . . . . . . . . . 17 + Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 17 1. Introduction REsource LOcation And Discovery (RELOAD) [I-D.ietf-p2psip-base] is a peer-to-peer signaling protocol that can be used to maintain an overlay network, and to store data in and retrieve data from the overlay. Although RELOAD defines a Traversal Using Relays around Network Address Translation (TURN) specific service discovery mechanism, it does not define a generic service discovery mechanism as a part of the base protocol. This document defines how the @@ -96,21 +96,21 @@ peers in a RELOAD Overlay Instance can offer to each other include a TURN relay service, a voice mail service, a gateway location service, and a transcoding service. Typically, only a small subset of the peers participating in the system are providers of a given service. A peer that wishes to use a particular service faces the problem of finding peers that are providing that service from the Overlay Instance. A naive way to perform service discovery is to store the Node-IDs of all nodes providing a particular service under a well-known key k. - The limitation of this approach is that it scales linearly in the + The limitation of this approach is that it scales linearly with the number of nodes that provide the service. The problem is two-fold: the node n that is responsible for service s identified by key k may end up storing a large number of Node-IDs and most importantly, may also become overloaded since all service lookup requests for service s will need to be answered by node n. An efficient service discovery mechanism does not overload the nodes storing pointers to service providers. In addition, the mechanism must ensure that the load of providing a given service is distributed evenly among the nodes providing the service. @@ -132,44 +131,59 @@ 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]. This document uses the terminology and definitions from the Concepts and Terminology for Peer to Peer SIP [I-D.ietf-p2psip-concepts] draft. DHT: Distributed Hash Tables (DHTs) are a class of decentralized distributed systems that provide a lookup service similar to a - hash table. Given a key, any participating peer can retrieve the - value associated with that key. The responsibility for - maintaining the mapping from keys to values is distributed among - the peers. + regular hash table. Given a key, any peer participating in the + system can retrieve the value associated with that key. The + responsibility for maintaining the mapping from keys to values is + distributed among the peers. - H(x): Hash calculated over x. + H(x): Refers to a hash function (e.g., SHA-1) calculated over the + value x. - I(l,k): An interval at level l in the ReDiR tree that encloses key - k. + I(lvl,k): An interval at level lvl in the ReDiR tree that encloses + key k. As an example, I(5,10) refers to an interval at level 5 in + the ReDiR tree within whose range key 10 falls. - n.id: Node-ID of node n. + n.id: Refers to the RELOAD Node-ID of node n. Namespace: An arbitrary identifier that identifies a service - provided in the RELOAD Overlay Instance. An example of a - namespace is "voice-mail". The namespace is an UTF-8 text string. + provided in the RELOAD Overlay Instance. Examples of potential + namespaces include "voice-mail" and "turn-relay". The namespace + is an UTF-8 text string. - numBitsInNodeId: Number of bits in a Node-ID. + numBitsInNodeId: Refers to the number of bits in a RELOAD Node-ID. + This value is used in the equations for calculating the ranges of + intervals that ReDiR tree nodes are responsible for. ReDiR tree: A tree structure of the nodes that provide a particular service. The nodes embed the ReDiR tree into the RELOAD Overlay - Instance using RELOAD Store and Fetch requests. + Instance using RELOAD Store and Fetch requests. Each tree node in + the ReDiR tree belongs to some level in the tree. The root node + of the ReDiR tree is located at level 0 of the ReDiR tree. The + child nodes of the root node are located at level 1. The children + of the tree nodes at level 1 are located at level 2, and so forth. + The ReDiR tree has a branching factor b. At every level lvl in the + ReDiR tree, there is room for a maximum of b^lvl tree nodes. Each + tree node in the ReDiR tree is uniquely identified by a pair + (lvl,j), where lvl is a level in the ReDiR tree and j is the + position of the tree node (from the left) at that level. Successor: The successor of identifier k in namespace ns is the node - belonging to ns whose identifier most immediately follows k. + belonging to the namespace ns whose identifier most immediately + follows the identifier k. 3. Introduction to ReDiR Recursive Distributed Rendezvous (ReDiR) [Redir] does not require new functionality from the RELOAD base protocol. This is possible since ReDiR interacts with the RELOAD Overlay Instance by simply storing and fetching data, that is, using RELOAD Store and Fetch requests. ReDiR creates a tree structure of the service providers of a particular service and stores it into the RELOAD Overlay Instance using the Store and Fetch requests. ReDiR service lookups require a @@ -304,44 +318,37 @@ select (type) { /* This type may be extended */ } extension; } RedirServiceProvider; The contents of the RedirServiceProvider Resource Record are as follows: - type The type of an extension to the RedirServiceProvider Resource Record. Unknown types are allowed. - destination_list A list of IDs through which a message is to be routed to reach the service provider. The destination list consists of a sequence of Destination values. The contents of the Destination structure are as defined in RELOAD base [I-D.ietf-p2psip-base]. - namespace An opaque UTF-8 encoded string containing the namespace. - level The level in the ReDiR tree. - node The position of the node storing this RedirServiceProvider record at the current level in the ReDiR tree. - length The length of the rest of the Resource Record. - extension An extension value. The RedirServiceProvider Resource Record can be extended to include for instance service or service provider specific information. 4.2. Selecting the Starting Level Before registering as a service provider or performing a service lookup, a peer needs to determine the starting level Lstart for the registration or lookup operation in the ReDiR tree. It is RECOMMENDED that Lstart is set to 2. In subsequent registrations, @@ -520,43 +532,38 @@ parameter). Finally, provided that exists=TRUE, H(namespace,level,node), where namespace, level, and node are taken from the RedirServiceProvider structure being stored, MUST be equal to the Resource-ID for the resource. The NODE-ID-MATCH policy may only be used with dictionary types. 6. REDIR Kind Definition This section defines the REDIR kind. - Name REDIR - Kind IDs The Resource Name for the REDIR Kind-ID is created by concatenating three pieces of information: namespace, level, and node number. Namespace is an opaque UTF-8 encoded string identifying a service, such as "turn-server". Level is an integer specifying a level in the ReDiR tree. Node number is an integer identifying a ReDiR tree node at a specific level. The data stored is a RedirServiceProvider structure that was defined in Section 4.1. - Data Model The data model for the REDIR Kind-ID is dictionary. The dictionary key is the Node-ID of the service provider. - Access Control The access control policy for the REDIR kind is the NODE-ID-MATCH policy that was defined in Section 5. 7. Examples - 7.1. Service Registration Figure 4 shows an example of a ReDiR tree containing information about four different service providers whose Node-IDs are 2, 3, 4, and 7. In the example, numBitsInNodeID=4. Initially, the ReDiR tree is empty; Figure 4 shows the state of the tree at the point when all the service providers have registered. Level 0 ____2_3___4_____7_|__________________ | | @@ -569,32 +576,32 @@ Figure 4: Example of a ReDiR tree First, peer 2 whose Node-ID is 2 joins the namespace. Since this is the first registration peer 2 performs, peer 2 sets the starting level Lstart to 2, as was described in Section 4.2. Also all other peers in this example will start from level 2. First, peer 2 fetches the contents of the tree node associated with interval I(2,2) from the RELOAD Overlay Instance. This tree node is the first tree node from the left at Level 2 since key 2 is associated with the second interval of the first tree node. Peer 2 also stores its - RedirServiceProvider record in that tree node. Since peer 2's - Node-ID is the only Node-ID stored in the tree node (i.e., peer 2's - Node-ID fulfills the condition in Section 4.3 that it is the - numerically lowest or highest among the keys stored in the node), - peer 2 continues up the tree. In fact, peer 2 continues up in the - tree all the way to the root inserting its own Node-ID in all levels - since the tree is empty (which means that peer 2's Node-ID always - fulfills the condition that it is the numerically lowest or highest - Node-ID in the interval I(level, 2) during the upward walk). As - described in Section 4.3, peer 2 also walks down the tree. The - downward walk peer 2 does ends at level 2 since peer 2 is the only - node in its interval at that level. + RedirServiceProvider record in that tree node. Since peer 2's Node- + ID is the only Node-ID stored in the tree node (i.e., peer 2's Node- + ID fulfills the condition in Section 4.3 that it is the numerically + lowest or highest among the keys stored in the node), peer 2 + continues up the tree. In fact, peer 2 continues up in the tree all + the way to the root inserting its own Node-ID in all levels since the + tree is empty (which means that peer 2's Node-ID always fulfills the + condition that it is the numerically lowest or highest Node-ID in the + interval I(level, 2) during the upward walk). As described in + Section 4.3, peer 2 also walks down the tree. The downward walk peer + 2 does ends at level 2 since peer 2 is the only node in its interval + at that level. The next peer to join the namespace is peer 3, whose Node-ID is 3. Peer 3 starts from level 2. At that level, peer 3 stores its RedirServiceProvider entry in the same interval I(2,3) that already contains the RedirServiceProvider entry of peer 2. Interval I(2,3), that is, the interval at Level 2 enclosing key 3, is associated with the right hand side interval of the first tree node. Since peer 3 has the numerically highest Node-ID in the tree node associated with I(2,3), peer 3 continues up the tree. Peer 3 stores its RedirServiceProvider record also at levels 1 and 0 since its Node-ID @@ -701,66 +709,71 @@ Data Kind-ID" Registry: +--------------+------------+----------+ | Kind | Kind-ID | RFC | +--------------+------------+----------+ | REDIR | 104 | RFC-AAAA | +--------------+------------+----------+ This Kind-ID was defined in Section 6. + Note to RFC Editor: please replace AAAA with the RFC number for this + specification. + 10.3. ReDiR Namespaces IANA SHALL create a "ReDiR Namespaces" Registry. Entries in this registry are strings denoting ReDiR namespace values. The initial contents of this registry are: +----------------+----------+ | Namespace | RFC | +----------------+----------+ | turn-server | RFC-AAAA | +----------------+----------+ The namespace 'turn-server' is used by nodes that wish to register as providers of a TURN relay service in the RELOAD overlay and by nodes that wish to discover providers of a TURN relay service from the RELOAD overlay. -11. Acknowledgments + Note to RFC Editor: please replace AAAA with the RFC number for this + specification. +11. Acknowledgments The authors would like to thank Marc Petit-Huguenin and Joscha Schneider for their comments on the draft. 12. References 12.1. Normative References [I-D.ietf-p2psip-base] Jennings, C., Lowekamp, B., Rescorla, E., Baset, S., and H. Schulzrinne, "REsource LOcation And Discovery (RELOAD) - Base Protocol", draft-ietf-p2psip-base-25 (work in + Base Protocol", draft-ietf-p2psip-base-26 (work in progress), February 2013. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 12.2. Informative References [I-D.ietf-p2psip-concepts] - Bryan, D., Willis, D., Shim, E., Matthews, P., and S. + Bryan, D., Matthews, P., Shim, E., Willis, D., and S. Dawkins, "Concepts and Terminology for Peer to Peer SIP", - draft-ietf-p2psip-concepts-04 (work in progress), - October 2011. + draft-ietf-p2psip-concepts-05 (work in progress), July + 2013. [Redir] Rhea, S., Godfrey, P., Karp, B., Kubiatowicz, J., Ratnasamy, S., Shenker, S., Stoica, I., and H. Yu, "Open - DHT: A Public DHT Service and Its Uses". + DHT: A Public DHT Service and Its Uses", October 2005. Authors' Addresses Jouni Maenpaa Ericsson Hirsalantie 11 Jorvas 02420 Finland Email: Jouni.Maenpaa@ericsson.com