动态委托发现系统（DDDS）第二部分：算法

RFC3402：Dynamic Delegation Discovery System (DDDS) Part Two: The Algorithm，October 2002

本备忘录的状态

本文件规定了互联网社区的互联网标准跟踪协议，并要求进行讨论和提出改进建议。有关本协议的标准化状态和状态，请参阅当前版本的“互联网官方协议标准”（STD 1）。这份备忘录的分发是无限的。

版权声明

版权所有（C）互联网协会（2002）。保留所有权利。

摘要

本文档描述了用于将动态检索的字符串转换规则应用于应用程序唯一字符串的动态委派发现系统（Dynamic Delegation Discovery System，DDDS）算法。格式良好的转换规则将反映与字符串相关联的信息的管理委托。本文档也是“动态委托发现系统（DDDS）第一部分：综合DDDS”（RFC 3401）中完全指定的系列的一部分。需要注意的是，如果不阅读其他文件，就不可能阅读和理解本系列中的任何文件。

1、 简介

动态委派发现系统（DDDS）用于实现字符串到数据的延迟绑定，以支持动态配置的委派系统。DDDS的功能是通过迭代应用字符串转换规则，将一些唯一字符串映射到存储在DDDS数据库中的数据，直到达到终端条件。

本文档描述了一般的DDDS算法，而不是任何特定的应用或使用场景。整个系列文件在“动态委托发现系统（DDDS）第一部分：综合DDDS”（RFC 3401）[1]中有详细说明。需要注意的是，如果不阅读相关文件，就不可能阅读和理解该系列中的单个文件。

DDDS的历史是从统一资源名称工作组的工作演变而来的。当统一资源名称（Uniform Resource Names，URN）[6]最初制定时，需要为URN定位一个权威服务器，该URN（按设计）不包含有关网络位置的信息。制定了一个系统，该系统可以使用可应用于URN的规则数据库来查找有关特定语法块的信息。该系统最初称为解析器发现服务（Resolver Discovery Service，RDS）[7]，仅适用于URNs。

随着时间的推移，其他系统开始将相同的算法和基础设施应用于其他与URN无关的系统（有关使用DDDS的其他方法的示例，请参见第6节）。这导致一些基本假设发生了变化，需要澄清。这些文件是对原始URN规范的更新，以便以标准化的方式开发新的应用程序和规则数据库。

该文档废弃了RFC 2168[11]和RFC 2915[9]，并更新了RFC 2276[7]。

2、 术语

本文件中的关键词“必须”、“不得”、“要求”、“应”、“不应”、”应该“、”不应“、”推荐“、”可能“和”可选“应按照RFC 2119中的描述进行解释。

Application Unique String：应用程序唯一字符串，作为DDDS应用程序的初始输入的字符串。该字符串的词法结构必须隐含一个唯一的委托路径，通过重复选择和应用重写规则来分析和跟踪该路径。

Rewrite Rule：重写规则，应用于应用程序唯一字符串的规则，用于生成从规则数据库中选择新重写规则的新键，或返回给调用应用程序的最终结果字符串。也称为规则。

First Well Known Rule：第一条众所周知的规则，这是一个重写规则，由应用程序定义，而实际上不在规则数据库中。它用于生成第一个有效密钥。

Terminal Rule：终端规则，一种重写规则，当使用时，它会产生一个字符串，该字符串是DDDS过程的最终结果，而不是另一个数据库键。

Application：应用，一组协议和规范，为DDDS算法的各个通用部分指定实际值。应用程序必须定义应用程序唯一字符串、第一个已知规则以及一个或多个对应用程序有效的数据库的语法和语义。

Rule Database：规则数据库，任何规则存储，使得唯一密钥可以标识一组规则，这些规则指定使用该特定密钥时使用的委派步骤。

Services：服务，公共规则数据库可以用于将不同的服务与给定的应用程序唯一字符串相关联；例如，不同的协议功能、不同的操作特性、地理隔离、向后兼容性等。可能的服务差异可能是电子邮件/传真/语音邮件的消息接收服务、网络服务器上的负载均衡、附近镜像服务器的选择、成本与性能的权衡等。这些服务是规则的一部分，允许应用程序从服务的角度根据一个分支或另一个分支的适用性做出分支决策。

Flags：标志，大多数申请都需要一种规则向申请发出信号的方式，即某些规则提供了其他规则没有提供的特定结果；例如，不同的输出格式、可扩展性机制、终端规则信令等。大多数数据库将定义一个标志字段，应用程序可以使用该字段来编码表示这些信号的各种值。

3、 算法

DDDS算法基于重写规则的概念。这些规则被收集到DDDS规则数据库中，并通过给定的唯一密钥进行访问。给定的规则应用于应用程序唯一字符串时，会将该字符串转换为可用于从规则数据库检索新规则的新密钥。然后将此新规则重新应用于原始应用程序唯一字符串，并重复该循环，直到达到终止条件。应用程序不得将规则应用于先前规则的输出。所有应用程序的所有重写规则必须始终应用于与算法开始时完全相同的应用程序唯一字符串。

应用程序唯一字符串具有某种规则可以应用的规则词法结构是一个基本假设。DDDS的一个假设是，用于做出委托决策的词法元素足够简单，可以包含在应用程序唯一串本身中。DDDS不能解决使用AUS和规则（一天中的时间、金融交易、权利管理等）之外的知识做出授权决定的情况。

从图表上看，该算法如下所示：

3.1、 规则的组成部分

规则由4条信息组成：

一个优先级

简单地说，一个数字，用于显示两个相等的规则中的哪一个可能具有优先权。这允许数据库表达可能提供大致相同结果的规则，但一种委托路径可能比另一种更快、更好、更便宜。

一组标志

标志用于指定规则的属性，以确定此规则是否是最后一个应用的规则。最后一条规则称为终端规则，其输出应该是应用程序的预期结果。标志在应用程序中是唯一的。应用程序可以指定它正在使用另一个应用程序定义的标志，但它必须使用该另一应用程序的定义。一个应用程序无法重新定义另一应用程序使用的标志。这可能意味着未来将需要标志的注册，但目前这不是一项要求。

一个服务说明

服务用于指定特定委派分支的语义属性。在许多情况下，两个委派分支是相同的，只是一个委派到提供一组功能的结果，而另一个则提供另一组功能。功能可能包括操作问题，如负载均衡、基于地理位置的流量隔离、旧客户端的降级但向后兼容的功能等。例如，两个规则可能同样适用于字符串的特定委托决策。一种规则可能导致终端规则，该规则生成用于高可用性环境的信息，而另一种规则则可能导致存档服务，该服务可能较慢，但在较长时间内更稳定。

一个替换表达式

这是规则中实际的字符串修改部分。它是POSIX扩展正则表达式[8]和类似于Unix sed样式的替换表达式的替换字符串的组合。

3.2、 替换表达式语法

替换表达式所在的字符集以及可以对其执行操作的字符集既依赖于应用程序，也依赖于正在使用的数据库。应用程序必须定义应用程序唯一字符串允许的字符集。DDDS数据库规范必须定义生成其密钥所需的字符集以及替换表达式本身的编码方式。以下语法要求的字符只有在为数据库和/或应用程序定义了特定字符集后才有意义。

规则的替换表达式部分的语法是sed样式的替换表达式。由于各种原因，True sed样式的替换表达式不适合在此应用程序中使用，因此regexp字段的内容必须遵循以下语法：

subst-expr   = delim-char ere delim-char repl delim-char *flagsdelim-char   = "/" / "!" / <Any octet not in 'POS-DIGIT' or 'flags'>; subst_expr中出现的所有delim_char都必须是相同的字符。>ere          = <POSIX Extended Regular Expression>repl         = *(string / backref)string       = *(anychar / escapeddelim)anychar      = <any character other than delim-char>escapeddelim = "" delim-charbackref      = "" POS-DIGITflags        = "i"POS-DIGIT    = "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"

将替换表达式应用于字符串的结果必须产生一个遵守数据库规则的键（当然，除非它是终端规则，在这种情况下，输出遵循应用程序的规则）。由于正则表达式可能被不正确地指定，从而可以构造不一致的密钥，因此客户端软件在使用它之前应该验证结果是否是合法的数据库密钥。

替换表达式的repl部分中的Backref表达式替换为替换表达式的ERE部分中由“（”和“）”括起来的字符串（可能为空）。N是从1到9（包括1到9）的一位数字。它指定了第N个backref表达式，该表达式以第N个“（”开始，一直到匹配的“）”。例如，ERE

(A(B(C)DE)(F)G)

具有backref表达式：

1     = ABCDEFG2     = BCDE3     = C4     = F5..9 = error - no matching subexpression

“i”标志表示ERE匹配应以不区分大小写的方式执行。此外，当给出“i”标志时，任何backref替换都可以标准化为小写。只有当应用程序和数据库都定义了不区分大小写有效的字符集时，此标志才有意义。

替换表达式中的第一个字符应用作分隔替换表达式组成部分的字符。在替换表达式中，分隔符必须恰好出现三次非转义字符。由于分隔符的转义出现将被解释为该字符的出现，因此数字不得用作分隔符。如果允许的话，Backrefs将与文字数字混淆。类似地，如果在替换表达式中指定了标志，则分隔符不能也是标志字符。

3.3、 完整算法

以下是确切的DDDS算法：

1、第一个众所周知的规则被应用于产生密钥的应用程序唯一字符串。

2、应用程序要求数据库提供绑定到该密钥的有序规则集（请参阅下面关于订单详细信息的注释）。

3、列表中每个规则的替换表达式按顺序应用于应用程序唯一字符串，直到生成非空字符串为止。注意列表中的位置，并将生成非空字符串的规则用于下一步。如果下一步拒绝此规则并返回此步骤，则替换表达式应用程序进程将在其停止的位置继续。如果列表已用完，但没有有效的匹配项，则会通知应用程序没有可用的有效输出。

4、如果规则的服务描述不符合客户端的要求，请返回步骤3并继续查看已检索到的规则列表。如果它确实符合客户的要求，那么该规则将用于下一步。如果且仅当客户端能够处理它，并且应用程序规范认为这样做是安全的，则客户端可以记下当前规则，但仍然返回到步骤3，就好像它拒绝了它一样。在任何一种情况下，此步骤的输出都是一个且只有一个规则。

5、如果规则的标志部分指定该规则不是终端，则返回步骤2，将替换结果作为新密钥。

6、通知应用程序该过程已经完成，并向应用程序提供规则的标志和服务部分以及最后一个替换表达式的输出。

注1：在某些应用程序和/或数据库中，结果集可以表示两个或多个规则被视为相等的情况。这些规则被视为相同的规则，每个规则可能都有一个优先级，用于传达对其他等效规则的偏好。这使得规则可以作为其他规则的倒退。需要注意的是，这是一个真正的首选项，而不是负载均衡机制。应用程序应该仔细定义差异。

注2：数据库可能有也可能没有规则来确定数据库中的记录何时以及如何过期（过期日期、生存时间等）。在任何情况下都必须遵守这些过期机制。具体而言，由于数据库记录的过期可能会导致检索到与以前的规则不一致的新规则，而在算法中，任何通过返回到以前的密钥和规则来优化过程的尝试都必须确保以前检索到的规则没有过期。如果规则已过期，则应用程序必须在步骤1重新启动。

4、 指定应用程序

为了使该算法有用，必须编写描述应用程序和一个或多个数据库的规范。为了指定应用程序，需要以下信息：

Application Unique String：应用程序唯一字符串。这是重写规则将应用到的唯一字符串。该字符串必须具有某种规则结构，并且在应用程序中是唯一的，这样任何应用来自同一数据库的规则的人最终都将使用相同的键。例如，URI解析应用程序将应用程序唯一字符串定义为URI。

任何应用程序都不允许定义应用程序唯一字符串，从而将重写规则获得的密钥视为新规则输入的应用程序唯一串。这导致了sendmail风格的重写规则，这些规则很脆弱且容易出错。唯一的例外是，当应用程序定义某个标志或状态时，该应用程序的规则将被挂起，而新的DDDS应用程序或其他任意规则集将接管。如果是这种情况，那么根据定义，这些规则都不适用。在URI解析应用程序中可以找到一种这样的情况，该应用程序定义了“p”标志，该标志表示下一步是“特定于协议的”，因此不在DDDS的范围内。

First Well Known Rule：第一条众所周知的规则。这是应用于应用程序唯一字符串时生成第一个有效密钥的第一条规则。它可以用与规则相同的形式表达，也可以是更复杂的东西。例如，URI解析应用程序可能会指定规则为URI中的字符序列（不包括第一个冒号（URI方案））为第一个Key。

Valid Databases：有效数据库。应用程序可以定义哪些数据库是有效的。对于每个数据库，应用程序必须定义如何将第一个已知规则的输出（第一个密钥）转换为对该数据库有效的内容。例如，URI解析应用程序可以使用域名系统（Domain Name System，DNS）作为数据库。将第一个密钥转换为对数据库有效的密钥的操作是将其转换为某个DNS有效域名。此外，对于应用程序定义的每个数据库，它还必须指定将生成正确密钥的有效字符集。在这里显示的URI解析示例中，URI的字符集是7位ASCII，这与DNS对其区域文件中字符的8位限制非常匹配。

Expected Output：预期输出。应用程序必须定义终端规则的预期输出。例如，URI解析应用程序涉及查找包含给定URI的权威数据的服务器。因此，终端规则的输出将是用于联系该权威服务器的信息（主机、端口、协议等）。

过去，在负载均衡和DDDS“优先级”的使用方面存在一些混乱。应用程序应该意识到，给定规则的优先级只是：一种指定一个规则比另一个规则“更好、更快、更便宜”的方式。如果应用程序需要某种方法来允许客户端在服务器之间进行负载均衡（即加权随机选择等），那么它应该在DDDS算法之外这样做。例如，使用DNS数据库的应用程序可以使用SRV记录作为表示特定服务实际上由相互协作的几个主机处理的一种方式。不同之处在于，负载均衡是在彼此相同的主机之间进行的，因为DDDS涉及具有某些特定功能集或管理域的委派路径。

5、 指定数据库

此外，任何应用程序都必须至少有一个相应的数据库，以便从中检索规则。需要注意的是，一个给定的数据库可能被多个应用程序使用。如果是这种情况，则每个规则都必须使用其服务和/或替换表达式的某种组合，以仅匹配其有效的应用程序唯一字符串。

数据库规范必须包括以下信息：

General Specification：通用规范。

数据库必须有一个通用规范。这可以参考其他标准（SQL、DNS等），也可以完全指定一个新颖的数据库系统。本规范必须明确存在哪些允许的字符集，以便知道密钥和规则是在哪个字符集中编码的。

Lookup Procedure：查找过程。

这指定了如何制定查询并将其提交到数据库。在数据库用于其他目的（如DNS）的情况下，规范必须明确如何专门为数据库制定查询，使其成为DDDS数据库。例如，基于DNS的数据库必须指定要使用的资源记录或查询类型。

Key Format：密钥格式。

如果需要任何操作来将密钥转换为对数据库有效的东西，则必须明确定义这些操作。例如，在DNS数据库的情况下，密钥必须构造为有效的域名。

Rule Format：规则格式。

规则输出格式的规范。

Rule Insertion Procedure：规则插入程序。

关于如何将规则插入数据库的规范。这可以包括关于是否允许添加规则的策略声明。

Rule Collision Avoidance：规则冲突避免。

由于数据库可以由多个应用程序使用（例如ENUM和URI Resolution），因此规范必须明确如何避免规则冲突。通常有两种处理方法：1）禁止一个密钥在两个不同的应用程序中有效；2） 如果1不可能，那么编写替换表达式，使正则表达式部分包含足够的应用程序唯一字符串作为其匹配的一部分，以区分两个应用程序。

6、 示例

这里给出的例子仅用于教学目的。它们特别取自任何已发布文件中未指定的虚构应用程序。

6.1、 汽车零部件识别系统

在这个例子中，想象一个系统设置，所有汽车制造商聚集在一起，为构成汽车制造和维修过程的各种零件（螺母、螺栓、框架、仪器等）创建一个标准化的零件编号系统。这种系统的问题在于，汽车行业是一个非常分散的系统，零件由分布在世界各地的各种第三方制造。为了找到关于给定零件的信息，系统必须能够找到该零件的制造者并就此与他们联系。

为了便于这种分布式系统，分配给零件的识别号是分层分配的，使得前5位数字组成零件制造商ID号。接下来的3位数字是汽车生产线标识符（福特、丰田等）。其余数字由零件制造商根据制造商决定的规则分配。

汽车行业决定使用DDDS创建一个分布式信息检索系统，将查询路由到数据的实际所有者。该行业指定了用于检索重写规则的数据库和查询语法（APIDA网络），然后指定了汽车零件标识DDDS应用程序（APIDA）。

APIDA规范将定义以下内容：

*应用程序唯一字符串：零件号。

*第一条众所周知的规则：取前5位数字（制造商ID号）作为密钥。

*有效数据库：APIDA网络。

*预期输出：有关部件的EDIFAC信息。

APIDA网络数据库规范将定义以下内容：

*通用规范：启用EDI的数据库和服务网络，当给定零件号的子组件时，将返回XML编码的重写规则。

*查找过程：遵循正常的APIDA网络协议，向网络请求密钥的重写规则。

*密钥格式：不需要转换。

*规则格式：有关XML DTD，请参阅APIDA网络文档。

*规则插入程序：由对零件号的每个部分具有控制权的机构确定。也就是说，为了获得制造商ID，你必须是汽车零部件制造商协会的成员。

为了说明系统将如何工作，请想象零件号“4747301AB7D”。系统会取前5位数字“47473”，并向网络询问“重写规则”。该规则将由零件制造商数据库提供，并允许制造商进一步细分空间或将查询器直接指向系统中的EDIFAC信息。

在这个例子中，我们假设制造商返回一个规则，该规则规定接下来的3位数字应该作为查询的一部分使用到他们的服务，以便找到新的规则。这一新规则将允许零部件制造商进一步将查询委托给他们的每个汽车生产线的零部件工厂。在我们的示例零件号中，数字“01A”表示丰田汽车系列。制造商返回的规则进一步将查询委托给日本的供应机构。该规则还表示该规则是终端规则，因此最后一次查询的结果将是有关零件的实际信息。

6.2、 文件识别服务

这个例子与上一个非常相似，因为这个系统中的文档可以简单地被认为是上一个例子中的汽车部件。这里的区别在于，有关文档的信息与作者非常接近（通常在他们的桌面上）。因此，代表团的数目可能非常多。此外，为了避免作者的空间太大，作者是按组织和部门组织的。

假设本例中的应用程序唯一字符串如下所示：

<organization>-<department>-<author>:<project>-<bookcase>-<book>

应用程序规范如下所示：

*应用程序唯一字符串：上面给出的文档ID字符串。

*第一个众所周知的规则：第一个“-”之前但不包括第一个的字符被视为第一个键。

*有效数据库：DIS LDAP目录。

*预期输出：来自LDAP服务器的记录，包含有关XML文档的目录信息。

DIS LDAP目录的数据库规范如下所示：

*一般规范：数据库使用LDAP目录服务。每个LDAP服务器都有一个包含“重写规则”的记录。规则指的是使用LDAP URL方案的其他LDAP服务器。

*查找过程：使用标准LDAP查询，客户端向LDAP服务器询问有关密钥的信息。

*密钥格式：无需转换。

*规则格式：请参阅LDAP重写规则规范。

*规则插入程序：请参阅对DIS树的该部分拥有权限的实体发布的程序。第一部分，即该组织，由综合安全分遣队机构所有。

在本例中，第一个查找是针对组织的规则。在这一点上，组织可以将客户端直接指向包含预期输出的某个大型组织范围的数据库。其他组织可能会分散这个过程，这样规则最终会将查询一直委托给所选的作者文档管理环境。

7、 安全注意事项

本文档仅定义了DDDS算法，因此其本身并不意味着任何安全问题。只有当该算法与数据库和应用程序相结合时，才能充分了解安全考虑因素，从而列举它们，而不仅仅是简单地说动态委派点是可能的攻击点。

8、 IANA注意事项

本文件未对IANA提出任何要求。数据库和应用程序规范可能有相当大的要求，但此处无法列举。

9、 参考文献

[1] Mealling, M., "Dynamic Delegation Discovery System (DDDS) Part One: The Comprehensive DDDS", RFC 3401, October 2002.[2] Mealling, M., "Dynamic Delegation Discovery System (DDDS) Part Two: The Algorithm", RFC 3402, October 2002.[3] Mealling, M., "Dynamic Delegation Discovery System (DDDS) Part Three: The Domain Name System (DNS) Database", RFC 3403, October 2002.[4] Mealling, M., "Dynamic Delegation Discovery System (DDDS) Part Four: The Uniform Resource Identifiers (URI) Resolution Application", RFC 3404, October 2002.[5] Mealling, M., "Dynamic Delegation Discovery System (DDDS) Part Five: URI.ARPA Assignment Procedures", RFC 3405, October 2002.[6] Moats, R., "URN Syntax", RFC 2141, May 1997.[7] Sollins, K., "Architectural Principles of Uniform Resource Name Resolution", RFC 2276, January 1998.[8] 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.[9] Mealling, M. and R. Daniel, "The Naming Authority Pointer (NAPTR) DNS Resource Record", RFC 2915, August 2000.[10] Faltstrom, P., "E.164 number and DNS", RFC 2916, September 2000.[11] Daniel, R. and M. Mealling, "Resolution of Uniform Resource Identifiers using the Domain Name System", RFC 2168, June 1997.

完整版权声明

版权所有（C）互联网协会（2002）。保留所有权利。

本文件及其译文可复制并提供给他人，对其进行评论或以其他方式解释或协助其实施的衍生作品可全部或部分制作、复制、出版和分发，不受任何形式的限制，前提是上述版权声明和本段包含在所有此类复制品和衍生作品中。然而，本文件本身不得以任何方式进行修改，例如删除版权声明或提及互联网协会或其他互联网组织，除非是为了制定互联网标准而需要，在这种情况下，必须遵守互联网标准流程中定义的版权程序，或者根据需要将其翻译成英语以外的语言。

上述授予的有限权限是永久性的，互联网协会或其继承人或受让人不会撤销。

本文件及其包含的信息以“原样”为基础提供，互联网协会和互联网工程工作组不承担任何明示或暗示的保证，包括但不限于任何保证，即使用本文件中的信息不会侵犯任何权利或对适销性或特定用途适用性的任何暗示保证。

声明

RFC编辑器功能的资金目前由互联网协会提供。