--- 1/draft-ietf-urn-ddds-03.txt 2007-12-18 19:09:26.000000000 +0100 +++ 2/draft-ietf-urn-ddds-04.txt 2007-12-18 19:09:26.000000000 +0100 @@ -1,211 +1,326 @@ Network Working Group M. Mealling -Internet-Draft Network Solutions, Inc. -Expires: May 2, 2001 November 1, 2000 +Internet-Draft Verisign +Expires: August 9, 2001 February 8, 2001 Dynamic Delegation Discovery System (DDDS) - draft-ietf-urn-ddds-03 + draft-ietf-urn-ddds-04 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 the entire list of Internet-Draft Shadow Directories, see http://www.ietf.org/shadow.html. - This Internet-Draft will expire on May 2, 2001. + This Internet-Draft will expire on August 9, 2001. Copyright Notice - Copyright (C) The Internet Society (2000). All Rights Reserved. + Copyright (C) The Internet Society (2001). All Rights Reserved. Abstract This document describes the Dynamic Delegation Discovery System (DDDS). The DDDS defines an abstract algorithm for applying dynamically retrieved string transformation rules to an application-unique string. Well-formed transformation rules will reflect the delegation of management of information associated with - the string. This memo does not specify any application or database, - although it does define the requirements for doing so. + the string. Other documents specify applications and rule databases + with which this algorithm may be used. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 - 3. The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 5 - 3.1 Components of a Rule . . . . . . . . . . . . . . . . . . . . . 5 - 3.2 Substitution Expression Syntax . . . . . . . . . . . . . . . . 5 - 3.3 The Complete Algorithm . . . . . . . . . . . . . . . . . . . . 7 - 4. Specifying An Application . . . . . . . . . . . . . . . . . . 9 - 5. Specifying A Database . . . . . . . . . . . . . . . . . . . . 11 - 6. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 - 6.1 An Automobile Parts Identification System . . . . . . . . . . 13 - 6.2 A Document Identification Service . . . . . . . . . . . . . . 14 - References . . . . . . . . . . . . . . . . . . . . . . . . . . 16 - Author's Address . . . . . . . . . . . . . . . . . . . . . . . 16 - Full Copyright Statement . . . . . . . . . . . . . . . . . . . 17 + 3. The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 6 + 3.1 Components of a Rule . . . . . . . . . . . . . . . . . . . . . 7 + 3.2 Substitution Expression Syntax . . . . . . . . . . . . . . . . 8 + 3.3 The Complete Algorithm . . . . . . . . . . . . . . . . . . . . 9 + 4. Specifying An Application . . . . . . . . . . . . . . . . . . 11 + 5. Specifying A Database . . . . . . . . . . . . . . . . . . . . 13 + 6. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 + 6.1 An Automobile Parts Identification System . . . . . . . . . . 15 + 6.2 A Document Identification Service . . . . . . . . . . . . . . 16 + 7. Security Considerations . . . . . . . . . . . . . . . . . . . 18 + 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 + References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 + Author's Address . . . . . . . . . . . . . . . . . . . . . . . 20 + Full Copyright Statement . . . . . . . . . . . . . . . . . . . 21 1. Introduction The Dynamic Delegation Discovery System is used to map some unique string to data stored within the DDDS by iteratively applying string transformation rules until a terminal condition is reached. This document describes the general algorithm, not any particular application or usage scenario. It is up to other documents to describe how they use the DDDS algorithms. Two such documents are RFXXXX[5] which describes the URI Resolution Application and RFC2916[7] which describes the E.164 Telephone Number to URI Mapping Application. The DDDS's history is an evolution from work done by the Uniform Resource Name Working Group. When Uniform Resource Names[1] were originally formulated there was the desire to locate an - authoritative server for a URN which by design contained no + authoritative server for a URN that (by design) contained no information about network locations. A system was formulated that could use a database of rules that could be applied to a URN to find out information about specific chunks of syntax. This system was originally called the Resolver Discovery System[2] and only applied to URNs. Over time other systems began to apply this same algorithm and - infrastructure to other, non-URN related, systems. This caused some - of the underlying assumptions to change and need clarification. This + infrastructure to other, non-URN related, systems (see Section 6 for + examples of other ways of using the DDDS). This caused some of the + underlying assumptions to change and need clarification. This document, which is one of a series, is an update of those original URN specifications in order to allow new applications and rule databases to be developed in a standardized manner. - A direct result of these clarifications and generalizations is that - this document, along with RFC YYYY[4] and RFC XXXX[5], obsoletes RFC - 2168[8] and RFC 2915[6] as well as updates RFC 2276[2]. + This document, RFC YYYY[4] and RFC XXXX[5] comprise a suite of + specifications based on the generic DDDS algorithm: + + o This document describes the generic algorithm, assuming access to + a seperately defined database of transformation rules and a + specification of the actual application that makes use of the + algorithm. + + o RFC YYYY describes a rule database that uses the DNS as its data + store. + + o RFC XXXX describes how to use the above two specifications for + pulling apart Uniform Resource Identifiers and finding + authoritative metadata servers for those URIs. + + These three documents obsolete RFC 2168[8] and RFC 2915[6] as well + as updates RFC 2276[2]. 2. 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. Application Unique String - The string that is the target of all the rewrite rules. By the - nature of the DDDS algorithm, each string defines a unique - delegation path; therefore strings must be chosen to reflect the - one-to-one relationship between whatever is being delegated and - the string (uniqueness). + A string that is the initial input to a DDDS application. The + lexical structure of this string must imply a unique delegation + path, which is analyzed and traced by the repeated selection and + application of Rewrite Rules. Rewrite Rule - An object containing several pieces of data that, when combined - and applied to an Application Unique String, produces a new key - that exists in the Rule Database. Also simply known as a Rule. + A rule that is applied to an Application Unique String to produce + either a new key to select a new rewrite rule from the rule + database, or a final result string that is returned to the + calling application. Also simply known as a Rule. First Well Known Rule This is a rewrite rule that is defined by the application and not actually in the Rule Database. It is used to produce the first valid key. Terminal Rule - This Rule is one where the Flags specify that the iterative - process is over and that the output of applying this Rule to the - Application Unique String will be the intended output of the - entire process. + A Rewrite Rule that, when used, yields a string that is the final + result of the DDDS process, rather than another database key. Application A set of protocols and specifications that specify actual values for the various generalized parts of the DDDS algorithm. An Application must define the syntax and semantics of the - Application Unique String, the First Well Known Rule, and which - Databases are valid for the Application. + Application Unique String, the First Well Known Rule, and one or + more Databases that are valid for the Application. - Database + Rule Database Any store of Rules such that a unique key can identify a set of Rules that specify the delegation step used when that particular Key is used. + Services + A common rule database may be used to associate different + services with a given Application Unique String; e.g. different + protocol functions, different operational characteristics, + geographic segregation, backwards compatibility, etc. Possible + service differences might be message receiving services for + email/fax/voicemail, load balancing over web servers, selection + of a nearby mirror server, cost vs performance trade-offs, etc. + These Services are included as part of a Rule to allow the + Application to make branching decisions based on the + applicability of one branch or the other from a Service + standpoint. + + Flags + Most Applications will require a way for a Rule to signal to the + Application that some Rules provide particular outcomes that + others do not; e.g. different output formats, extensibility + mechanisms, terminal rule signaling, etc. Most Datatabases will + define a Flags field that an Application can use to encode + various values that express these signals. + 3. The Algorithm The DDDS algorithm is based on the concept of Rewrite Rules. These - rules are given unique Keys that are collected into a database that - is known as a DDDS Rule Database. A given Rule, when applied to an - Application Unique String, transforms that String into new Key that - can be used to retrieve a new Rule from the Rule Database. This new - rule is then re-applied to the original Application Unique String - and the cycle repeats itself until a terminating condition is - reached. + rules are collected into a DDDS Rule Database, and accessed by given + unique keys. A given Rule, when applied to an Application Unique + String, transforms that String into new Key that can be used to + retrieve a new Rule from the Rule Database. This new rule is then + re-applied to the original Application Unique String and the cycle + repeats itself until a terminating condition is reached. + + It is a fundamental assumption that the Application Unique String + has some kind of regular, lexical structure that the rules can be + applied to. It is an assumption of the DDDS that the lexical element + used to make a delegation decision is simple enough to be contained + within the Application Unique String itself. The DDDS does not solve + the case where a delegation decision is made using knowledge + contained outside the AUS and the Rule (time of day, financial + transactions, rights management, etc). + + Diagramatically the algorithm looks like this: + + +--------- Application Unique String + | +-----+ + | |input| + | +-------+ +---------+ + | | First Well Known Rule | + | +-------+ +--------+ + | |output| + | +------+ + | First Key + | | + | | + | +----<--------------<--------------+ + | | | + | key (a DDDS database always | + | +-----+ takes a key and returns | + | |input| a rule) ^ + | +---------+ +------------+ | + | | Lookup key in DDDS Database| | + | +---------+ +-----------+ | + | |output| | + | +------+ | + | rule set | + | | | + | | (the input to a rule | + | rule set is the rule and the AUS. ^ + | +-----+ The output is always | + +---------------->|input| either a key or the result) | + +---------------+ +------------------+ | + | Apply Rules to Application Unique String| | + | until non-empty result are obtained | | + | that meet the applications requirements | | + +---------------+ +-----------------+ | + |output| | + +------+ ^ + key | + | | + | | + | | + | | + v | + +--------------------------------------+ | + | Was the last matching rule terminal? | No >------+ + +--------------------------------------+ + Yes (if the rule isn't terminal + | then its output is the new + | key which is used to find a + | new rule set) + | + +------------------------------------+ + | The output of the last rule is the | + | result desired by the application | + +------------------------------------+ 3.1 Components of a Rule A Rule is made up of 4 pieces of information: A Priority Simply a number used to show which of two otherwise equal rules may have precedence. This allows the database to express rules that are equivalent but weighted for load balancing reasons. A set of Flags Flags are used to specify attributes of the rule that determine if this rule is the last one to be applied. The last rule is called the terminal rule and its output should be the intended result for the application. A description of Services - Services are used to specify attributes of a particular - delegation branch. For example, two rules may equally apply to a - specific delegation decision for a string. One rule can lead to a - terminal rule that produces information for use in high - availability environments while another may lead to an archival - service that may be slower but is more stable over long periods - of time. + Services are used to specify semantic attributes of a particular + delegation branch. There are many cases where two delegation + branches are identical except that one delegates down to a result + that provides one set of features while another provides some + other set. Features may include operational issues such as load + balancing, geographically based traffic segregation, degraded but + backwardly compatibile functions for older clients, etc. For + example, two rules may equally apply to a specific delegation + decision for a string. One rule can lead to a terminal rule that + produces information for use in high availability environments + while another may lead to an archival service that may be slower + but is more stable over long periods of time. A Substitution Expression This is the actual string modification part of the rule. It is a combination of a POSIX Extended Regular Expression[3] and a - replacement string similar to Unix sed(1) search-replace - function. See Section 3.2. + replacement string similar to Unix sed-style substitution + expression. 3.2 Substitution Expression Syntax + The character set(s) that the substitution expression is in and can + act on are dependent both on the Application and on the Database + being used. An Application must define what the allowed character + sets are for the Application Unique String. A DDDS Database + specification must define what character sets are required for + producing its keys and for how the substitution expression itself is + encoded. The grammar-required characters below only have meaning + once a specific character set is defined for the Database and/or + Application. + The syntax of the Substitution Expression part of the rule is a - sed-style substitution expression. True sed(1) substitution + sed-style substitution expression. True sed-style substitution expressions are not appropriate for use in this application for a variety of reasons, therefore the contents of the regexp field MUST follow this grammar: subst-expr = delim-char ere delim-char repl delim-char *flags - delim-char = "/" / "!" / - ; All ocurances of a delim_char in a subst_expr must + delim-char = "/" / "!" / + ; All occurances of a delim_char in a subst_expr must ; be the same character.> ere = repl = *(string / backref) string = *(anychar / escapeddelim) anychar = escapeddelim = "\" delim-char backref = "\" POS-DIGIT flags = "i" POS-DIGIT = "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9" The result of applying the substitution expression to the String - MUST result in a key which obeys the rules of the Database. Since it - is possible for the regular expression to be improperly specified, - such that a non-conforming key can be constructed, client software - SHOULD verify that the result is a legal database key before using - it. + MUST result in a key which obeys the rules of the Database (unless + of course it is a Terminal Rule in which case the output follows the + rules of the application). Since it is possible for the regular + expression to be improperly specified, such that a non-conforming + key can be constructed, client software SHOULD verify that the + result is a legal database key before using it. Backref expressions in the repl portion of the substitution expression are replaced by the (possibly empty) string of characters enclosed by '(' and ')' in the ERE portion of the substitution expression. N is a single digit from 1 through 9, inclusive. It specifies the N'th backref expression, the one that begins with the N'th '(' and continues to the matching ')'. For example, the ERE (A(B(C)DE)(F)G) @@ -213,83 +328,70 @@ \1 = ABCDEFG \2 = BCDE \3 = C \4 = F \5..\9 = error - no matching subexpression The "i" flag indicates that the ERE matching SHALL be performed in a case-insensitive fashion. Furthermore, any backref replacements MAY be normalized to lower case when the "i" flag is given. This flag - only has meaning when both the Application and Database define a + has meaning only when both the Application and Database define a character set where case insensitivity is valid. The first character in the substitution expression shall be used as the character that delimits the components of the substitution expression. There must be exactly three non-escaped occurrences of the delimiter character in a substitution expression. Since escaped occurrences of the delimiter character will be interpreted as occurrences of that character, digits MUST NOT be used as delimiters. Backrefs would be confused with literal digits were this allowed. Similarly, if flags are specified in the substitution expression, the delimiter character must not also be a flag character. - The character set(s) that the substitution expression is in and can - act on are dependent both on the Application and on the Database - being used. An Application must define what the allowed character - sets are for the Application Unique String. A DDDS Database - specification must define what character sets are required for - producing its keys and for how the substitution expression itself is - encoded. The grammar required characters from above only have - meaning once a specific character set is defined for the Database or - Application. - 3.3 The Complete Algorithm The following is the exact DDDS algorithm: 1. The First Well Known Rule is applied to the Application Unique String which produces a Key - 2. That Application asks the Database for the ordered set of Rules - that are bound to that Key - - 3. The Substitution Expression of each Rule in the list of Rules is - applied to the String in the order in which they were received. - In some applications and/or databases the result set can express - the case where two or more Rules are considered equal. These - Rules are treated as the same Rule, each one possibly having a - Priority which is used to weight a random selection among the - equivalent Rules (this allows for Rules to 'load balance' - themselves). - - 4. The first/next Rule with a Substitution Expression that produces - anything other than the empty string is examined to see if the - parameters in the Services part of the Rule meet the - requirements of the Application. + 2. The Application asks the Database for the ordered set of Rules + that are bound to that Key (see NOTE below on order details) - 5. If the parameters in the Service part of the Rule do not match - those required by the Application then go back to Step 4. + 3. The Substitution Expression for each Rule in the list is applied + to the Application Unique String until a non-empty string is + yielded. The rule that produced the non-empty string is used for + the next step. If the list is exhausted without a valid match + then the application is notified that no valid output was + available. - 6. If the Flags part of the Rule designate that this Rule is - Terminal, then apply the Substitution Expression to the String - and then go to Step 8. + 4. If the Service description of the rule does not match the + Application requirements, go back to step 3 and continue through + the already retrieved list of rules. - 7. Apply the Substitution Expression to the String. The output of - this rewrite becomes the new Key. To begin the next iteration, - return to Step 2 and use this new Key as the Key in that step. + 5. If the Flags part of the Rule designate that this Rule is NOT + Terminal, go back to step 2 with the substitution result as the + new Key. - 8. Notify the Application that the process has finished and provide + 6. Notify the Application that the process has finished and provide the Application with the Flags and Services part of the Rule along with the output of the last Substitution Expression. + NOTE: In some applications and/or databases the result set can + express the case where two or more Rules are considered equal. These + Rules are treated as the same Rule, each one possibly having a + Priority which is used to weight a random selection among the + equivalent Rules (this allows for Rules to 'load balance' + themselves). + 4. Specifying An Application In order for this algorithm to have any usefulness, a specification must be written describing an application and one or more databases. In order to specify an application the following pieces of information are required: Application Unique String: This is the only string that the rewrite rules will apply to. The string must have some regular structure and be unique within the @@ -350,24 +452,23 @@ this is the case, each rule must be use some combination of its Services and/or substitution expression to match only those Application Unique Strings for which it is valid. A Database specification must include the following pieces of information: General Specification: The Database must have a general specification. This can reference other standards (SQL, DNS, etc) or it can fully specify - a novel database system. This specification must be clear as to + a novel database system. This specification MUST be clear as to what allowed character sets exist in order to know in which - character set the Rules and subsequence substitution expression - are encoded. + character set the Keys and Rules are encoded. Lookup Procedure: This specifies how a query is formulated and submitted to the database. In the case of databases that are used for other purposes (such as DNS), the specification must be clear as to how a query is formulated specifically for the database to be a DDDS database. For example, a DNS based Database must specify which Resource Records or Query Types are used. Key Format: @@ -380,24 +481,24 @@ The specification for the output format of a rule. Rule Insertion Procedure: A specification for how a Rule is inserted into the database. This can include policy statements about whether or not a Rule is allowed to be added. Rule Collision Avoidance: Since a Database may be used by multiple Applications (ENUM and URI Resolution for example), the specification must be clear - about collisions will be avoided. There are usually two methods - for handling this: 1) disallow one key from being valid in two - different Applications; 2) if 1 isn't possible then write the - substitution expression such that the regular expression part + about how rule collisions will be avoided. There are usually two + methods for handling this: 1) disallow one key from being valid + in two different Applications; 2) if 1 isn't possible then write + the substitution expression such that the regular expression part contains enough of the Application Unique String as part of its match to differentiate between the two Applications. 6. Examples The examples given here are for pedagogical purposes only. They are specifically taken from fictious applications that have not been specified in any published document. 6.1 An Automobile Parts Identification System @@ -517,20 +618,35 @@ entity that has authority over that section of the DIS tree. The first section, the organization, is owned by the DIS Agency. In this example, the first lookup is for the organization's Rule. At that point the organization may point the client directly at some large, organization wide database that contains the expected output. Other organizations may decentralize this process so that Rules end up delegating the query all the way down to the authors document management environment of choice. +7. Security Considerations + + This document simply defines the DDDS algorithm and thus, by itself, + does not imply any security issues. It is when this algorithm is + coupled with a Database and an Application that security + considerations can be known well enough to enumerate them beyond + simply saying that dynamic delegation points are a possible point of + attack. + +8. IANA Considerations + + This document does not create any requirements on the IANA. Database + and Application specifications may have considerable requirements + but they cannot be enumerated here. + References [1] Moats, R., "URN Syntax", RFC 2141, May 1997. [2] Sollins, K., "Architectural Principles of Uniform Resource Name Resolution", RFC 2276, January 1998. [3] The Institute of Electrical and Electronics Engineers, "IEEE Standard for Information Technology - Portable Operating System Interface (POSIX) - Part 2: Shell and Utilities (Vol. 1)", IEEE @@ -548,32 +664,32 @@ (NAPTR) DNS Resource Record", RFC 2915, August 2000. [7] Faltstrom, P., "E.164 number and DNS", RFC 2916, September 2000. [8] Daniel, R. and M. Mealling, "Resolution of Uniform Resource Identifiers using the Domain Name System", RFC 2168, June 1997. Author's Address Michael Mealling - Network Solutions, Inc. + Verisign 505 Huntmar Park Drive Herndon, VA 22070 US - Phone: +1 770 935 5492 + Phone: +1 770 921-2251 EMail: michaelm@netsol.com - URI: http://www.netsol.com + URI: http://www.verisign.com Full Copyright Statement - Copyright (C) The Internet Society (2000). All Rights Reserved. + Copyright (C) The Internet Society (2001). 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 implmentation 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