Network Working Group M. Mealling Request for Comments: 3402 Verisign Obsoletes: 2915, 2168 October 2002 Category: Standards Track Dynamic Delegation Discovery System (DDDS) Part Two: The Algorithm Status of this Memo This document specifies an Internet standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (2002). All Rights Reserved.
AbstractThis document describes the Dynamic Delegation Discovery System (DDDS) 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 document is also part of a series that is completely specified in "Dynamic Delegation Discovery System (DDDS) Part One: The Comprehensive DDDS" (RFC 3401). It is very important to note that it is impossible to read and understand any document in this series without reading the others.
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 4 3.1 Components of a Rule . . . . . . . . . . . . . . . . . . . . . 6 3.2 Substitution Expression Syntax . . . . . . . . . . . . . . . . 6 3.3 The Complete Algorithm . . . . . . . . . . . . . . . . . . . . 8 4. Specifying An Application . . . . . . . . . . . . . . . . . . 9 5. Specifying A Database . . . . . . . . . . . . . . . . . . . . 11 6. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.1 An Automobile Parts Identification System . . . . . . . . . . 12 6.2 A Document Identification Service . . . . . . . . . . . . . . 14 7. Security Considerations . . . . . . . . . . . . . . . . . . . 15 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 References . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Author's Address . . . . . . . . . . . . . . . . . . . . . . . 16 Full Copyright Statement . . . . . . . . . . . . . . . . . . . 17 RFC 3401) . It is very important to note that it is impossible to read and understand a single document in that series without reading the related documents. The DDDS's history is an evolution from work done by the Uniform Resource Name Working Group. When Uniform Resource Names (URNs)  were originally formulated there was the desire to locate an 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 Service (RDS)  and only applied to URNs.
Over time other systems began to apply this same algorithm and 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. These documents are an update of those original URN specifications in order to allow new applications and rule databases to be developed in a standardized manner. This document obsoletes RFC 2168  and RFC 2915  as well as updates RFC 2276 . RFC 2119. Application Unique String 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 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 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 one or more Databases that are valid for the Application.
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 Databases will define a Flags field that an Application can use to encode various values that express these signals.
Diagrammatically 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 | +------------------------------------+
8] and a replacement string similar to Unix sed-style substitution expression.
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-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 = "/" / "!" / <Any octet not in 'POS-DIGIT' or 'flags'> ; All occurrences of a delim_char in a subst_expr ; must be the same character.> ere = <POSIX Extended Regular Expression> repl = *(string / backref) string = *(anychar / escapeddelim) anychar = <any character other than delim-char> 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 (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) has backref expressions: \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 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.
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. 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 1: 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 communicate a preference for otherwise equivalent Rules. This allows for Rules to act as fallbacks for others. It should be noted that this is a real Preference, not a load balancing mechanism. Applications should define the difference carefully. NOTE 2: Databases may or may not have rules that determine when and how records within that database expire (expiration dates, times to live, etc.). These expiration mechanisms must be adhered to in all cases. Specifically, since the expiration of a databases record could cause a new Rule to be retrieved that is inconsistent with previous Rules, while in the algorithm any attempts to optimize the process by falling back to previous keys and Rules MUST ensure that no previously retrieved Rule has expired. If a Rule has expired then the application MUST start over at Step 1.
suspended and a new DDDS Application or some other arbitrary set of rules take over. If this is the case then, by definition, none of these rules apply. One such case can be found in the URI Resolution application which defines the 'p' flag which states that the next step is 'protocol specific' and thus outside of the scope of DDDS. First Well Known Rule: This is the first rule that, when applied to the Application Unique String, produces the first valid Key. It can be expressed in the same form as a Rule or it can be something more complex. For example, the URI Resolution application might specify that the rule is that the sequence of characters in the URI up to but not including the first colon (the URI scheme) is the first Key. Valid Databases: The application can define which Databases are valid. For each Database the Application must define how the First Well Known Rule's output (the first Key) is turned into something that is valid for that Database. For example, the URI Resolution application could use the Domain Name System (DNS) as a Database. The operation for turning this first Key into something that was valid for the database would be to to turn it into some DNS-valid domain-name. Additionally, for each Database an Application defines, it must also specify what the valid character sets are that will produce the correct Keys. In the URI Resolution example shown here, the character set of a URI is 7 bit ASCII which matches fairly well with DNS's 8 bit limitation on characters in its zone files. Expected Output: The Application must define what the expected output of the Terminal Rule should be. For example, the URI Resolution application is concerned with finding servers that contain authoritative data about a given URI. Thus the output of the terminal rule would be information (hosts, ports, protocols, etc.) that would be used to contact that authoritative server. In the past there has been some confusion concerning load balancing and the use of the DDDS 'Priority'. Applications should be aware that the Priority of a given rule is just that: a way of specifying that one rule is "better, faster, cheaper" than another. If an application needs some method of allowing a client to load balance between servers (i.e., weighted random selection, etc.) then it should do so outside the DDDS algorithm. For example, Applications that make use of the DNS Database may use the SRV record as a way of signifying that a particular service is actually handled by several hosts cooperating with each other. The difference being that load
balancing is done between hosts that are identical to each other where as DDDS is concerned with delegation paths that have some particular feature set or administrative domain.
Rule Collision Avoidance: Since a Database may be used by multiple Applications (ENUM and URI Resolution for example), the specification must be clear 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.
o Valid Databases: The APIDA Network. o Expected Output: EDIFAC information about the part. The APIDA Network Database specification would define the following: o General Specification: a network of EDI enabled databases and services that, when given a subcomponent of a part number will return an XML encoded rewrite rule. o Lookup Procedure: following normal APIDA Network protocols, ask the network for a rewrite rule for the Key. o Key Format: no conversion is required. o Rule Format: see APIDA Network documentation for the XML DTD. o Rule Insertion Procedure: determined by the authority that has control over each section of the part number. I.e., in order to get a manufacturer ID you must be a member of the Auto Parts Manufacturers Association. In order to illustrate how the system would work, imagine the part number "4747301AB7D". The system would take the first 5 digits, '47473' and ask the network for that Rewrite Rule. This Rule would be provided by the parts manufacturers database and would allow the manufacturer to either further sub-delegate the space or point the querier directly at the EDIFAC information in the system. In this example let's suppose that the manufacturer returns a Rule that states that the next 3 digits should be used as part of a query to their service in order to find a new Rule. This new Rule would allow the parts manufacturer to further delegate the query to their parts factories for each auto line. In our example part number the number '01A' denotes the Toyota line of cars. The Rule that the manufacturer returns further delegates the query to a supply house in Japan. This rule also denotes that this Rule is terminal and thus the result of this last query will be the actual information about the part.
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.  Mealling, M., "Dynamic Delegation Discovery System (DDDS) Part One: The Comprehensive DDDS", RFC 3401, October 2002.  Mealling, M., "Dynamic Delegation Discovery System (DDDS) Part Two: The Algorithm", RFC 3402, October 2002.  Mealling, M., "Dynamic Delegation Discovery System (DDDS) Part Three: The Domain Name System (DNS) Database", RFC 3403, October 2002.  Mealling, M., "Dynamic Delegation Discovery System (DDDS) Part Four: The Uniform Resource Identifiers (URI) Resolution Application", RFC 3404, October 2002.  Mealling, M., "Dynamic Delegation Discovery System (DDDS) Part Five: URI.ARPA Assignment Procedures", RFC 3405, October 2002.  Moats, R., "URN Syntax", RFC 2141, May 1997.  Sollins, K., "Architectural Principles of Uniform Resource Name Resolution", RFC 2276, January 1998.
 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 Std 1003.2-1992, ISBN 1-55937-255-9, January 1993.  Mealling, M. and R. Daniel, "The Naming Authority Pointer (NAPTR) DNS Resource Record", RFC 2915, August 2000.  Faltstrom, P., "E.164 number and DNS", RFC 2916, September 2000.  Daniel, R. and M. Mealling, "Resolution of Uniform Resource Identifiers using the Domain Name System", RFC 2168, June 1997. http://www.verisignlabs.com
Full Copyright Statement Copyright (C) The Internet Society (2002). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society.