idnits 2.17.1 draft-ietf-urn-ddds-02.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 5 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 (September 21, 2000) is 8617 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. -------------------------------------------------------------------------------- 1 Network Working Group M.M. Mealling 2 Internet-Draft Network Solutions, Inc. 3 Expires: March 22, 2001 September 21, 2000 5 Dynamic Delegation Discovery System (DDDS) 6 draft-ietf-urn-ddds-02 8 Status of this Memo 10 This document is an Internet-Draft and is in full conformance with 11 all provisions of Section 10 of RFC2026. 13 Internet-Drafts are working documents of the Internet Engineering 14 Task Force (IETF), its areas, and its working groups. Note that 15 other groups may also distribute working documents as 16 Internet-Drafts. 18 Internet-Drafts are draft documents valid for a maximum of six 19 months and may be updated, replaced, or obsoleted by other documents 20 at any time. It is inappropriate to use Internet-Drafts as reference 21 material or to cite them other than as "work in progress." 23 The list of current Internet-Drafts can be accessed at 24 http://www.ietf.org/ietf/1id-abstracts.txt 26 The list of Internet-Draft Shadow Directories can be accessed at 27 http://www.ietf.org/shadow.html. 29 This Internet-Draft will expire on March 22, 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 . . . . . . . . . . . . . . . . . . 9 53 5. Specifying A Database . . . . . . . . . . . . . . . . . . . . 11 54 6. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 55 6.1 An Automobile Parts Identification System . . . . . . . . . . 12 56 6.2 A Document Identification Service . . . . . . . . . . . . . . 13 57 References . . . . . . . . . . . . . . . . . . . . . . . . . . 15 58 Author's Address . . . . . . . . . . . . . . . . . . . . . . . 15 59 Full Copyright Statement . . . . . . . . . . . . . . . . . . . 16 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 = "/" / "!" / 181 ; All ocurances of a delim_char in a subst_expr must 182 ; be the same character.> 183 ere = 184 repl = *(string / backref) 185 string = *(anychar / escapeddelim) 186 anychar = 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 The character set(s) that the substitution expression is in and can 232 act on are dependent both on the Application and on the Database 233 beind used. An Application must define what the allowed character 234 sets are for the Application Unique String. A DDDS Database 235 specification must define what character sets are required for 236 producing its keys and for how the substitution expression itself is 237 encoded. The grammar required characters from above only have 238 meaning once a specific character set is defined for the Database or 239 Application. 241 3.3 The Complete Algorithm 243 The following is the exact DDDS algorithm: 245 1. The First Well Known Rule is applied to the Application Unique 246 String which produces a Key 248 2. That Application asks the Database for the ordered set of Rules 249 that are bound to that Key 251 3. The Substitution Expression of each Rule in the list of Rules is 252 applied to the String in the order in which they were received. 253 In some applications and/or databases the result set can express 254 the case where two or more Rules are considered equal. These 255 Rules are treated as the same Rule, each one possibly having a 256 Priority which is used to weight a random selection among the 257 equivalent Rules (this allows for Rules to 'load balance' 258 themselves). 260 4. The first/next Rule with a Substitution Expression that produces 261 anything other than the empty string is examined to see if the 262 parameters in the Services part of the Rule meet the 263 requirements of the Application. 265 5. If the parameters in the Service part of the Rule do not match 266 those required by the Application then go back to Step 4. 268 6. If the Flags part of the Rule designate that this Rule is 269 Terminal, then apply the Substitution Expression to the String 270 and then go to Step 8. 272 7. Apply the Substitution Expression to the String. The output of 273 this rewrite becomes the new Key. To begin the next iteration, 274 return to Step 2 and use this new Key as the Key in that step. 276 8. Notify the Application that the process has finished and provide 277 the Application with the Flags and Services part of the Rule 278 along with the output of the last Substitution Expression. 280 4. Specifying An Application 282 In order for this algorithm to have any usefulness, a specification 283 must be written describing an application and one or more databases. 284 In order to specify an application the following pieces of 285 information are required: 287 Application Unique String: 288 This is the original string that the rewrite rules will apply to. 289 The string must have some regular structure and be unique within 290 the application such that anyone applying Rules taken from the 291 same Database will end up with the same Keys. For example, the 292 URI Resolution application would define the Application Unique 293 String to be a URI. 295 No application is allowed to define an Application Unique String 296 such that the Key obtained by a rewrite rule is treated as the 297 Application Unique String for input to a new rule. This leads to 298 sendmail style rewrite rules which are fragile and error prone. 300 First Well Known Rule: 301 This is the first rule that, when applied to the Application 302 Unique String, produces the first valid Key. It can be expressed 303 in the same form as a Rule or it can be something more complex. 304 For example, the URI Resolution application might specify that 305 the rule is that the sequence of characters in the URI up to but 306 not including the first colon (the URI scheme) is the first Key. 308 Valid Databases: 309 The application can define which Databases are valid. For each 310 Database the Application must define how the First Well Known 311 Rule's output (the first Key) is turned into something that is 312 valid for that Database. For example, the URI Resolution 313 application could use the Domain Name System (DNS) as a Database. 314 The operation for turning this first Key into something that was 315 valid for the database would be to to turn it into some DNS-valid 316 domain-name. Additionally, for each Database an Application 317 defines, it must also specify what the valid character sets are 318 that will produce the correct Keys. In the URI Resolution 319 example, the character set of a URI is 7 bit ASCII which matches 320 fairly well with DNS's 8 bit limitation on characters in its zone 321 files. 323 Expected Output: 324 The Application must define what the expected output of the 325 Terminal Rule should be. For example, the URI Resolution 326 application is concerned with finding servers that contain 327 authoritative data about a given URI. Thus the output of the 328 terminal rule would be information (hosts, ports, protocols, etc) 329 that would be used to contact that authoritative server. 331 5. Specifying A Database 333 Additionally, any Application must have at least one corresponding 334 Database from which to retrieve the Rules. A Database specification 335 must include the following pieces of information: 337 General Specification: 338 The Database must have a general specification. This can 339 reference other standards (SQL, DNS, etc) or it can fully specify 340 a novel database system. This specification must be clear as to 341 what allowed character sets exist in order to know in which 342 character set the Rules and subsequence substitution expression 343 are encoded in. 345 Lookup Procedure: 346 This specifies how a query is formulated and submitted to the 347 database. In the case of databases that are used for other 348 purposes (such as DNS), the specification must be clear as to how 349 a query is formulated specifically for the database to be a DDDS 350 database. For example, a DNS based Database must specify which 351 Resource Records or Query Types are used. 353 Key Format: 354 If any operations are needed in order to turn a Key into 355 something that is valid for the database then these must be 356 clearly defined. For example, in the case of a DNS database, the 357 Keys must be constructed as valid domain-names. 359 Rule Format: 360 The specification for the output format of a rule. 362 Rule Insertion Procedure: 363 A specification for how a Rule is inserted into the database. 364 This can include policy statements about whether or not a Rule is 365 allowed to be added. 367 6. Examples 369 The examples given here are for pedagogical purposes only. They are 370 specifically taken from fictious applications that have not been 371 specified in any published document. 373 6.1 An Automobile Parts Identification System 375 In this example imagine a system setup where by all automobile 376 manufacturers come together and create a standardized part numbering 377 system for the various parts (nuts, bolts, frames, instruments, etc) 378 that make up the automobile manufacturing and repair process. The 379 problem with such a system is that the auto industry is a very 380 distributed system where parts are built by various third parties 381 distributed around the world. In order to find information about a 382 given part a system must be able to find out who makes that part and 383 contact them about it. 385 To facilitate this distributed system the identification number 386 assigned to a part is assigned hierarchically such that the first 5 387 digits make up a parts manufacturer ID number. The next 3 digits are 388 an auto line identifier (Ford, Toyota, etc). The rest of the digits 389 are assigned by the parts manufacturer according to rules that the 390 manufacturer decides. 392 The auto industry decides to use the DDDS to create a distributed 393 information retrieval system that routes queries to the actual owner 394 of the data. The industry specifies a database and a query syntax 395 for retrieving rewrite rules (the APIDA Network) and then specifies 396 the Auto Parts Identification DDDS Application (APIDA). 398 The APIDA specification would define the following: 400 o Application Unique String: the part number 402 o First Well Known Rule: take the first 5 digits (the manufacturers 403 ID number) and use that as the Key 405 o Valid Databases: The APIDA Network 407 o Expected Output: EDIFAC information about the part 409 The APIDA Network Database specification would define the following: 411 o General Specification: a network of EDI enabled databases and 412 services that, when given a subcomponent of a part number will 413 return an XML encoded rewrite rule 415 o Lookup Procedure: following normal APIDA Network protocols, ask 416 the network for a rewrite rule for the Key. 418 o Key Format: no conversion is required 420 o Rule Format: see APIDA Network documentation for the XML DTD 422 o Rule Insertion Procedure: determined by the authority that has 423 control over each section of the part number. I.e. in order to 424 get a manufacturer ID you must be a member of the Auto Parts 425 Manufacturers Association 427 In order to illustrate how the system would work, imagine the part 428 number "4747301AB7D". The system would take the first 5 digits, 429 '47473' and ask the network for that Rewrite Rule. This Rule would 430 be provided by the parts manufacturers database and would allow the 431 manufacturer to either further sub-delegate the space or point the 432 querier directly at the EDIFAC information in the system. 434 In this example lets suppose that the manufacturer returns a Rule 435 that states that the next 3 digits should be used as part of a query 436 to their service in order to find a new Rule. This new Rule would 437 allow the parts manufacturer to further delegate the query to their 438 parts factories for each auto line. In our example part number the 439 number '01A' denotes the Toyota line of cars. The Rule that the 440 manufacturer returns further delegates the query to a supply house 441 in Japan. This rule also denotes that this Rule is terminal and thus 442 the result of this last query will be the actual information about 443 the part. 445 6.2 A Document Identification Service 447 This example is very similar to the last since the documents in this 448 system can simply be thought of as the auto part in the last 449 example. The difference here is that the information about the 450 document is kept very close to the author (usually on their 451 desktop). Thus there is the probability that the number of 452 delegations can be very deep. Also, in order to keep from having a 453 large flat space of authors, the authors are organized by 454 organizations and departments. 456 Let's suppose that the Application Unique String in this example 457 looks like the following: 459 The Application specification would look like this: 461 o Application Unique String: the Document ID string given above 463 o First Well Known Rule: the characters up to but not including the 464 first '-' is treated as the first Key. 466 o Valid Databases: the DIS LDAP Directory 468 o Expected Output: a record from an LDAP server containing 469 bibliographic information about the document in XML 471 The Database specification for the DIS LDAP Directory would look 472 like this: 474 o General Specification: the Database uses the LDAP directory 475 service. Each LDAP server has a record that contains the Rewrite 476 Rule. Rules refer to other LDAP servers using the LDAP URL scheme. 478 o Lookup Procedure: using standard LDAP queries, the client asks 479 the LDAP server for information about the Key. 481 o Key Format: no conversion is necessary. 483 o Rule Format: See the LDAP Rewrite Rule specification 485 o Rule Insertion Procedure: See the procedures published by the 486 entity that has authority over that section of the DIS tree. The 487 first section, the organization, is owned by the DIS Agency. 489 In this example, the first lookup is for the organization's Rule. At 490 that point the organization may point the client directly at some 491 large, organization wide database that contains the expected output. 492 Other organizations may decentralize this process so that Rules end 493 up delegating the query all the way down to the authors document 494 management environment of choice. 496 References 498 [1] Moats, R., "URN Syntax", RFC 2141, May 1997. 500 [2] Sollins, K., "Architectural Principles of Uniform Resource Name 501 Resolution", RFC 2276, January 1998. 503 [3] The Institute of Electrical and Electronics Engineers, "IEEE 504 Standard for Information Technology - Portable Operating System 505 Interface (POSIX) - Part 2: Shell and Utilities (Vol. 1)", IEEE 506 Std 1003.2-1992, ISBN 1-55937-255-9, January 1993. 508 [4] Mealling, M.M., "A DDDS Database Using The Domain Name System", 509 Internet-Draft draft-ietf-urn-dns-ddds-database-00.txt, May 510 2000. 512 [5] Mealling, M.M., "URI Resolution using the Dynamic Delegation 513 Discovery System", Internet-Draft 514 draft-ietf-urn-uri-res-ddds-00.txt, July 2000. 516 [6] Danie1, R. and M. Mealling, "Resolution of Uniform Resource 517 Identifiers using the Domain Name System", RFC 2168, June 1997. 519 Author's Address 521 Michael Mealling 522 Network Solutions, Inc. 523 505 Huntmar Park Drive 524 Herndon, VA 22070 525 US 527 Phone: +1 770 935 5492 528 EMail: michaelm@netsol.com 529 URI: http://www.netsol.com 531 Full Copyright Statement 533 Copyright (C) The Internet Society (2000). All Rights Reserved. 535 This document and translations of it may be copied and furnished to 536 others, and derivative works that comment on or otherwise explain it 537 or assist in its implmentation may be prepared, copied, published 538 and distributed, in whole or in part, without restriction of any 539 kind, provided that the above copyright notice and this paragraph 540 are included on all such copies and derivative works. However, this 541 document itself may not be modified in any way, such as by removing 542 the copyright notice or references to the Internet Society or other 543 Internet organizations, except as needed for the purpose of 544 developing Internet standards in which case the procedures for 545 copyrights defined in the Internet Standards process must be 546 followed, or as required to translate it into languages other than 547 English. 549 The limited permissions granted above are perpetual and will not be 550 revoked by the Internet Society or its successors or assigns. 552 This document and the information contained herein is provided on an 553 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 554 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 555 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 556 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 557 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 559 Acknowledgement 561 Funding for the RFC editor function is currently provided by the 562 Internet Society.