idnits 2.17.1 draft-ietf-urn-ddds-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 2 instances of too long lines in the document, the longest one being 2 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 179 has weird spacing: '...im-char ere ...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (July 14, 2000) is 8686 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 2141 (ref. '1') (Obsoleted by RFC 8141) ** Downref: Normative reference to an Informational RFC: RFC 2276 (ref. '2') -- Possible downref: Non-RFC (?) normative reference: ref. '3' == Outdated reference: A later version (-09) exists of draft-ietf-urn-dns-ddds-database-00 == Outdated reference: A later version (-07) exists of draft-ietf-urn-uri-res-ddds-00 ** Obsolete normative reference: RFC 2168 (ref. '6') (Obsoleted by RFC 3401, RFC 3402, RFC 3403, RFC 3404) Summary: 8 errors (**), 0 flaws (~~), 5 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group M.M. Mealling 3 Internet-Draft Network Solutions, Inc. 4 Expires: January 12, 2001 July 14, 2000 6 Dynamic Delegation Discovery System (DDDS) 7 draft-ietf-urn-ddds-00 9 Status of this Memo 11 This document is an Internet-Draft and is in full conformance with 12 all provisions of Section 10 of RFC2026. 14 Internet-Drafts are working documents of the Internet Engineering 15 Task Force (IETF), its areas, and its working groups. Note that 16 other groups may also distribute working documents as 17 Internet-Drafts. 19 Internet-Drafts are draft documents valid for a maximum of six 20 months and may be updated, replaced, or obsoleted by other documents 21 at any time. It is inappropriate to use Internet-Drafts as reference 22 material or to cite them other than as "work in progress." 24 The list of current Internet-Drafts can be accessed at 25 http://www.ietf.org/ietf/1id-abstracts.txt 27 The list of Internet-Draft Shadow Directories can be accessed at 28 http://www.ietf.org/shadow.html. 29 This Internet-Draft will expire on January 12, 2001. 31 Copyright Notice 33 Copyright (C) The Internet Society (2000). All Rights Reserved. 35 Abstract 37 This document describes a the Dynamic Delegation Discovery System or 38 DDDS which, when applied to a unique string will produce a series of 39 rules that describe the various delegations that may exist based on 40 the syntax of that string. Since the DDDS is an abstract algorithm, 41 this specification does not define either an application or a rule 42 database. 44 Table of Contents 46 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 47 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 48 3. The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 5 49 3.1 Components of a Rule . . . . . . . . . . . . . . . . . . . . . 5 50 3.2 Substitution Expression Syntax . . . . . . . . . . . . . . . . 5 51 3.3 The Complete Algorithm . . . . . . . . . . . . . . . . . . . . 7 52 4. Specifying An Application . . . . . . . . . . . . . . . . . . 8 53 5. Specifying A Database . . . . . . . . . . . . . . . . . . . . 9 54 6. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 55 6.1 An Automobile Parts Identification System . . . . . . . . . . 10 56 6.2 A Document Identification Service . . . . . . . . . . . . . . 11 57 References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 58 Author's Address . . . . . . . . . . . . . . . . . . . . . . . 13 59 Full Copyright Statement . . . . . . . . . . . . . . . . . . . 14 61 1. Introduction 63 The Dynamic Delegation Discovery System is used to map some unique 64 string to data stored within the DDDS by iteratively applying string 65 transformation rules until a terminal condition is reached. This 66 document describes the general algorithm, not any particular 67 application or usage scenario. It is up to other documents to 68 describe how they use the DDDS algorithms. 70 The DDDS's history is an evolution from work done by the Uniform 71 Resource Name Working Group. When Uniform Resource Names[1] were 72 originally formulated there was the desire to locate an 73 authoritative server for a URN which by design contained no 74 information about network locations. A system was formulated that 75 could use a database of rules that could be applied to a URN to find 76 out information about specific chunks of syntax. This system was 77 originally called the Resolver Discovery System[2] and only applied 78 to URNs. 80 Over time other systems began to apply this same algorithm and 81 infrastructure to other, non-URN related, systems. This caused some 82 of the underlying assumptions to change and need clarification. This 83 document, which is one of a series, is an update of those original 84 URN specifications in order to allow new applications and rule 85 databases to be developed in a standardized manner. 87 A direct result of these clarifications and generalizations is that 88 this document, along with [4] and [5], obsoletes RFC 2168[6] and 89 updates RFC 2276[2]. 91 2. Terminology 93 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 94 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 95 this document are to be interpreted as described in RFC 2119. 97 Application Unique String 98 A string that is the target of the rewrite rules. Each possible 99 value of the string must be unique within the space for which it 100 is valid in order for the rewrite rules to apply. 102 Rewrite Rule 103 An object containing several pieces of data that, when combined 104 and applied to an Application Unique String, produces a new key 105 that exists in the Rule Database. Also simply known as a Rule. 107 First Well Known Rule 108 This is a rewrite rule that is defined by the application and not 109 actually in the Rule Database. It is used to produce the first 110 valid key. 112 Terminal Rule 113 This Rule is one where the Flags specify that the iterative 114 process is over and that the output of applying this Rule to the 115 Application Unique String will be the intended output of the 116 entire process. 118 Application 119 A set of protocols and specifications that specify actual values 120 for the various generalized parts of the DDDS algorithm. An 121 Application must define the syntax and semantics of the 122 Application Unique String, the First Well Known Rule, and which 123 Databases are valid for the Application. 125 Database 126 Any store of Rules such that a unique key can identify a set of 127 Rules that specify the delegation step used when that particular 128 Key is used. 130 3. The Algorithm 132 The DDDS algorithm is based on the concept of Rewrite Rules. These 133 rules are given unique Keys that are collected into a database that 134 is known as a DDDS Rule Database. A given Rule, when applied to an 135 Application Unique String, transforms that String into new Key that 136 can be used to retrieve a new Rule from the Rule Database. This new 137 rule is then re-applied to the original Application Unique String 138 and the cycle repeats itself until a terminating condition is 139 reached. 141 3.1 Components of a Rule 143 A Rule is made up of 4 pieces of information: 145 A Priority 146 Simply a number used to show which of two otherwise equal rules 147 may have precedence. This allows the database to express rules 148 that are equivalent but weighted for load balancing reasons. 150 A set of Flags 151 Flags are used to specify attributes of the rule that determine 152 if this rule is the last one to be applied. The last rule is 153 called the terminal rule and its output should be the intended 154 result for the application. 156 A description of Services 157 Services are used to specify attributes of a particular 158 delegation branch. For example, two rules may equally apply to a 159 specific delegation decision for a string. One rule can lead to a 160 terminal rule that produces information for use in high 161 availability environments while another may lead to an archival 162 service that may be slower but is more stable over long periods 163 of time. 165 A Substitution Expression 166 This is the actual string modification part of the rule. It is a 167 combination of a POSIX Extended Regular Expression[3] and a 168 replacement string similar to SED search-replace function. See 169 Section 3.2. 171 3.2 Substitution Expression Syntax 173 The syntax of the Substitution Expression part of the rule is a 174 sed-style substitution expression. True sed(1) substitution 175 expressions are not appropriate for use in this application for a 176 variety of reasons, therefore the contents of the regexp field MUST 177 follow this grammar: 179 subst_expr = delim-char ere delim-char repl delim-char *flags 180 delim-char = "/" / "!" / ... (Any non-digit or non-flag character. 181 All ocurances of a delim_char in a subst_expr must 182 be the same character.) 183 ere = POSIX Extended Regular Expression 184 repl = string / backref / repl string / repl backref 185 string = anychar escapeddelim / escapeddelim anychar 186 anychar = ; any character other than delim-char 187 escapeddelim = "\" delim-char 188 backref = "\" POS_DIGIT 189 flags = "i" 190 POS_DIGIT = "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9" 192 The result of applying the substitution expression to the String 193 MUST result in a key which obeys the rules of the Database. Since it 194 is possible for the regular expression to be improperly specified, 195 such that a non-conforming key can be constructed, client software 196 SHOULD verify that the result is a legal database key before using 197 it. 199 Backref expressions in the repl portion of the substitution 200 expression are replaced by the (possibly empty) string of characters 201 enclosed by '(' and ')' in the ERE portion of the substitution 202 expression. N is a single digit from 1 through 9, inclusive. It 203 specifies the N'th backref expression, the one that begins with the 204 N'th '(' and continues to the matching ')'. For example, the ERE 206 (A(B(C)DE)(F)G) 208 has backref expressions: 210 \1 = ABCDEFG 211 \2 = BCDE 212 \3 = C 213 \4 = F 214 \5..\9 = error - no matching subexpression 216 The "i" flag indicates that the ERE matching SHALL be performed in a 217 case-insensitive fashion. Furthermore, any backref replacements MAY 218 be normalized to lower case when the "i" flag is given. 220 The first character in the substitution expression shall be used as 221 the character that delimits the components of the substitution 222 expression. There must be exactly three non-escaped occurrences of 223 the delimiter character in a substitution expression. Since escaped 224 occurrences of the delimiter character will be interpreted as 225 occurrences of that character, digits MUST NOT be used as 226 delimiters. Backrefs would be confused with literal digits were this 227 allowed. Similarly, if flags are specified in the substitution 228 expression, the delimiter character must not also be a flag 229 character. 231 3.3 The Complete Algorithm 233 The following is the exact DDDS algorithm: 235 1. The First Well Known Rule is applied to the Application Unique 236 String which produces a Key 238 2. That Application asks the Database for the ordered set of Rules 239 that are bound to that Key 241 3. The Substitution Expression of each Rule in the list of Rules is 242 applied to the String in the order in which they were received. 243 In some applications and/or databases the result set can express 244 the case where two or more Rules are considered equal. These 245 Rules are treated as the same Rule, each one possibly having a 246 Priority which is used to weight a random selection among the 247 equivalent Rules (this allows for Rules to 'load balance' 248 themselves). 250 4. The first/next Rule with a Substitution Expression that produces 251 anything other than the empty string is examined to see if the 252 parameters in the Services part of the Rule meet the 253 requirements of the Application. 255 5. If the parameters in the Service part of the Rule do not match 256 those required by the Application then go back to Step 4. 258 6. If the Flags part of the Rule designate that this Rule is 259 Terminal, then apply the Substitution Expression to the String 260 and then go to Step 8. 262 7. Apply the Substitution Expression to the String. The output of 263 this rewrite becomes the new Key. To begin the next iteration, 264 return to Step 2 and use this new Key as the Key in that step. 266 8. Notify the Application that the process has finished and provide 267 the Application with the Flags and Services part of the Rule 268 along with the output of the last Substitution Expression. 270 4. Specifying An Application 272 In order for this algorithm to have any usefulness, a specification 273 must be written describing an application and one or more databases. 274 In order to specify an application the following pieces of 275 information are required: 277 Application Unique String: 278 This is the original string that the rewrite rules will apply to. 279 The string must have some regular structure and be unique within 280 the application such that anyone applying Rules taken from the 281 same Database will end up with the same Keys. For example, the 282 URI Resolution application would define the Application Unique 283 String to be a URI. 285 No application is allowed to define an Application Unique String 286 such that the Key obtained by a rewrite rule is treated as the 287 Application Unique String for input to a new rule. This leads to 288 sendmail style rewrite rules which are fragile and error prone. 290 First Well Known Rule: 291 This is the first rule that, when applied to the Application 292 Unique String, produces the first valid Key. It can be expressed 293 in the same form as a Rule or it can be something more complex. 294 For example, the URI Resolution application might specify that 295 the rule is that the sequence of characters in the URI up to but 296 not including the first colon (the URI scheme) is the first Key. 298 Valid Databases: 299 The application can define which Databases are valid. For each 300 Database the Application must define how the First Well Known 301 Rule's output (the first Key) is turned into something that is 302 valid for that Database. For example, the URI Resolution 303 application could use the Domain Name System (DNS) as a Database. 304 The operation for turning this first Key into something that was 305 valid for the database would be to to turn it into some DNS-valid 306 domain-name. 308 Expected Output: 309 The Application must define what the expected output of the 310 Terminal Rule should be. For example, the URI Resolution 311 application is concerned with finding servers that contain 312 authoritative data about a given URI. Thus the output of the 313 terminal rule would be information (hosts, ports, protocols, etc) 314 that would be used to contact that authoritative server. 316 5. Specifying A Database 318 Additionally, any Application must have at least one corresponding 319 Database from which to retrieve the Rules. A Database specification 320 must include the following pieces of information: 322 General Specification: 323 The Database must have a general specification. This can 324 reference other standards (SQL, DNS, etc) or it can fully specify 325 a novel database system. 327 Lookup Procedure: 328 This specifies how a query is formulated and submitted to the 329 database. In the case of databases that are used for other 330 purposes (such as DNS), the specification must be clear as to how 331 a query is formulated specifically for the database to be a DDDS 332 database. For example, a DNS based Database must specify which 333 Resource Records or Query Types are used. 335 Key Format: 336 If any operations are needed in order to turn a Key into 337 something that is valid for the database then these must be 338 clearly defined. For example, in the case of a DNS database, the 339 Keys must be constructed as valid domain-names. 341 Rule Format: 342 The specification for the output format of a rule. 344 Rule Insertion Procedure: 345 A specification for how a Rule is inserted into the database. 346 This can include policy statements about whether or not a Rule is 347 allowed to be added. 349 6. Examples 351 The examples given here are for pedagogical purposes only. They are 352 specifically taken from fictious applications that have not been 353 specified in any published document. 355 6.1 An Automobile Parts Identification System 357 In this example imagine a system setup where by all automobile 358 manufacturers come together and create a standardized part numbering 359 system for the various parts (nuts, bolts, frames, instruments, etc) 360 that make up the automobile manufacturing and repair process. The 361 problem with such a system is that the auto industry is a very 362 distributed system where parts are built by various third parties 363 distributed around the world. In order to find information about a 364 given part a system must be able to find out who makes that part and 365 contact them about it. 367 To facilitate this distributed system the identification number 368 assigned to a part is assigned hierarchically such that the first 5 369 digits make up a parts manufacturer ID number. The next 3 digits are 370 an auto line identifier (Ford, Toyota, etc). The rest of the digits 371 are assigned by the parts manufacturer according to rules that the 372 manufacturer decides. 374 The auto industry decides to use the DDDS to create a distributed 375 information retrieval system that routes queries to the actual owner 376 of the data. The industry specifies a database and a query syntax 377 for retrieving rewrite rules (the APIDA Network) and then specifies 378 the Auto Parts Identification DDDS Application (APIDA). 380 The APIDA specification would define the following: 382 o Application Unique String: the part number 384 o First Well Known Rule: take the first 5 digits (the manufacturers 385 ID number) and use that as the Key 387 o Valid Databases: The APIDA Network 389 o Expected Output: EDIFAC information about the part 391 The APIDA Network Database specification would define the following: 393 o General Specification: a network of EDI enabled databases and 394 services that, when given a subcomponent of a part number will 395 return an XML encoded rewrite rule 397 o Lookup Procedure: following normal APIDA Network protocols, ask 398 the network for a rewrite rule for the Key. 400 o Key Format: no conversion is required 402 o Rule Format: see APIDA Network documentation for the XML DTD 404 o Rule Insertion Procedure: determined by the authority that has 405 control over each section of the part number. I.e. in order to 406 get a manufacturer ID you must be a member of the Auto Parts 407 Manufacturers Association 409 In order to illustrate how the system would work, imagine the part 410 number "4747301AB7D". The system would take the first 5 digits, 411 '47473' and ask the network for that Rewrite Rule. This Rule would 412 be provided by the parts manufacturers database and would allow the 413 manufacturer to either further sub-delegate the space or point the 414 querier directly at the EDIFAC information in the system. 416 In this example lets suppose that the manufacturer returns a Rule 417 that states that the next 3 digits should be used as part of a query 418 to their service in order to find a new Rule. This new Rule would 419 allow the parts manufacturer to further delegate the query to their 420 parts factories for each auto line. In our example part number the 421 number '01A' denotes the Toyota line of cars. The Rule that the 422 manufacturer returns further delegates the query to a supply house 423 in Japan. This rule also denotes that this Rule is terminal and thus 424 the result of this last query will be the actual information about 425 the part. 427 6.2 A Document Identification Service 429 This example is very similar to the last since the documents in this 430 system can simply be thought of as the auto part in the last 431 example. The difference here is that the information about the 432 document is kept very close to the author (usually on their 433 desktop). Thus there is the probability that the number of 434 delegations can be very deep. Also, in order to keep from having a 435 large flat space of authors, the authors are organized by 436 organizations and departments. 438 Let's suppose that the Application Unique String in this example 439 looks like the following: 441 The Application specification would look like this: 443 o Application Unique String: the Document ID string given above 445 o First Well Known Rule: the characters up to but not including the 446 first '-' is treated as the first Key. 448 o Valid Databases: the DIS LDAP Directory 450 o Expected Output: a record from an LDAP server containing 451 bibliographic information about the document in XML 453 The Database specification for the DIS LDAP Directory would look 454 like this: 456 o General Specification: the Database uses the LDAP directory 457 service. Each LDAP server has a record that contains the Rewrite 458 Rule. Rules refer to other LDAP servers using the LDAP URL scheme. 460 o Lookup Procedure: using standard LDAP queries, the client asks 461 the LDAP server for information about the Key. 463 o Key Format: no conversion is necessary. 465 o Rule Format: See the LDAP Rewrite Rule specification 467 o Rule Insertion Procedure: See the procedures published by the 468 entity that has authority over that section of the DIS tree. The 469 first section, the organization, is owned by the DIS Agency. 471 In this example, the first lookup is for the organization's Rule. At 472 that point the organization may point the client directly at some 473 large, organization wide database that contains the expected output. 474 Other organizations may decentralize this process so that Rules end 475 up delegating the query all the way down to the authors document 476 management environment of choice. 478 References 480 [1] Moats, R., "URN Syntax", RFC 2141, May 1997. 482 [2] Sollins, K., "Architectural Principles of Uniform Resource Name 483 Resolution", RFC 2276, January 1998. 485 [3] The Institute of Electrical and Electronics Engineers, "IEEE 486 Standard for Information Technology - Portable Operating System 487 Interface (POSIX) - Part 2: Shell and Utilities (Vol. 1)", IEEE 488 Std 1003.2-1992, ISBN 1-55937-255-9, January 1993. 490 [4] Mealling, M.M., "A DDDS Database Using The Domain Name System", 491 Internet-Draft draft-ietf-urn-dns-ddds-database-00.txt, May 492 2000. 494 [5] Mealling, M.M., "URI Resolution using the Dynamic Delegation 495 Discovery System", Internet-Draft 496 draft-ietf-urn-uri-res-ddds-00.txt, July 2000. 498 [6] Danie1, R. and M. Mealling, "Resolution of Uniform Resource 499 Identifiers using the Domain Name System", RFC 2168, June 1997. 501 Author's Address 503 Michael Mealling 504 Network Solutions, Inc. 505 505 Huntmar Park Drive 506 Herndon, VA 22070 507 US 509 Phone: +1 770 935 5492 510 EMail: michaelm@netsol.com 511 URI: http://www.netsol.com 513 Full Copyright Statement 515 Copyright (C) The Internet Society (2000). All Rights Reserved. 517 This document and translations of it may be copied and furnished to 518 others, and derivative works that comment on or otherwise explain it 519 or assist in its implmentation may be prepared, copied, published 520 and distributed, in whole or in part, without restriction of any 521 kind, provided that the above copyright notice and this paragraph 522 are included on all such copies and derivative works. However, this 523 document itself may not be modified in any way, such as by removing 524 the copyright notice or references to the Internet Society or other 525 Internet organizations, except as needed for the purpose of 526 developing Internet standards in which case the procedures for 527 copyrights defined in the Internet Standards process must be 528 followed, or as required to translate it into languages other than 529 English. 531 The limited permissions granted above are perpetual and will not be 532 revoked by the Internet Society or its successors or assigns. 534 This document and the information contained herein is provided on an 535 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 536 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 537 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 538 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 539 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 541 Acknowledgement 543 Funding for the RFC editor function is currently provided by the 544 Internet Society.