Dynamic Delegation Discovery System (DDDS) Part Two: The Algorithm
obsoletes
Extracted elements (22)
Digits MUST NOT be used as delimiter characters in substitution expressions because they would be confused with backref literals (\1–\9). Similarly, if flags are specified, the delimiter must not also be a flag character.
Priority in DDDS is a real preference (better/faster/cheaper delegation path), not a load-balancing mechanism. Applications needing load balancing (e.g., weighted random selection among equivalent servers) must implement that outside the DDDS algorithm, such as via DNS SRV records.
Rule collision avoidance between Applications sharing a Database is handled either by disallowing a key from being valid in two Applications, or by writing substitution expressions whose regular expressions contain enough of the AUS to differentiate between Applications.
The DDDS assumes the delegation decision can be derived solely from the Application Unique String and the Rule itself. It explicitly does not solve the case where delegation requires external knowledge (time of day, financial state, rights management, etc.).
A given Rule Database may be used by more than one Application (e.g., ENUM and URI Resolution sharing a DNS database). Each rule must use its Services and/or substitution expression to match only those AUSs for which it is valid, to prevent cross-application interference.
RFC 3402 obsoletes RFC 2168 (URN resolution via DNS) and RFC 2915 (NAPTR DNS Resource Record), and updates RFC 2276. Applications built on those earlier specifications must migrate to the generalized DDDS framework.
A Database specification MUST be clear about what allowed character sets exist so that keys and rules can be properly encoded. It must also define the lookup procedure, key format, rule format, rule insertion procedure, and rule collision avoidance mechanisms.
An Application MUST NOT apply a Rule to the output of a previous Rule. All Rewrite Rules for all Applications must ALWAYS apply to the exact same Application Unique String that the algorithm started with.
If a previously retrieved Rule has expired during algorithm execution, the application MUST start over at Step 1. Any attempt to optimize by reusing previous keys and Rules must ensure no previously retrieved Rule has expired.
No application is allowed to define an Application Unique String such that a key obtained by a rewrite rule is treated as the AUS for input to a new rule, except when the application defines a flag or state suspending DDDS rules and handing off to another application or rule set.
The 'i' flag indicates that ERE matching SHALL be performed case-insensitively, and backref replacements MAY be normalized to lower case. This flag is meaningful only when both Application and Database define a character set where case insensitivity is valid.
The result of applying a substitution expression to the Application Unique String MUST produce a key conforming to the Database's rules (unless it is a Terminal Rule). Client software SHOULD verify that the result is a legal database key before using it.
A DDDS Rule is composed of four components: a Priority (numeric precedence), a Set of Flags (terminal/non-terminal signals), a Description of Services (semantic attributes of the delegation branch), and a Substitution Expression (the actual string transformation using POSIX ERE and sed-style replacement).
A Terminal Rule is a Rewrite Rule whose output is the final result of the DDDS process rather than another database key. Flags in the rule signal whether it is terminal.
Flags signal attributes of a Rule to the Application, including whether the Rule is terminal. Flags are unique across Applications; one Application cannot redefine a Flag used by another Application, though it may reference another Application's flag definition.
Services describe semantic attributes of a delegation branch, allowing an application to distinguish between branches offering different features (e.g., high availability vs. archival, load balancing, geographic segregation, backward compatibility). They are included as part of a Rule.
The Application Unique String (AUS) is the sole input to DDDS rewrite rules. It must have regular lexical structure implying a unique delegation path, and no application may treat a rule's output key as a new AUS for subsequent rules (to avoid sendmail-style fragile rewrites).
The First Well Known Rule is a rewrite rule defined by the application itself (not stored in the Rule Database) that transforms the Application Unique String into the first valid database key.
The DDDS algorithm itself does not introduce specific security issues; security considerations arise when the algorithm is coupled with a specific Database and Application. Dynamic delegation points are identified as a general point of attack, but specific threats depend on the Application and Database chosen.
The DDDS algorithm iterates through six steps: (1) apply First Well Known Rule to AUS to get first Key; (2) retrieve ordered Rule set from Database for Key; (3) apply Substitution Expressions in order until a non-empty result; (4) check Service match, else continue; (5) if Rule is non-terminal, return to step 2 with substitution result as new Key; (6) return Flags, Services, and substitution output to Application.
Backref expressions in the replacement portion use \N (N = 1–9) to reference the Nth parenthesized sub-expression in the ERE. Referencing a non-existent sub-expression is an error.
The Substitution Expression uses sed-style syntax: delim-char ERE delim-char repl delim-char *flags. The delimiter is the first character of the expression (any octet not in POS-DIGIT or flags), must appear exactly three non-escaped times, and digits MUST NOT be used as delimiters to avoid confusion with backreferences.