AAA

RFC 3402 — Система DDDS. Часть 2 — Алгоритм

Статус документа

Этот документ содержит спецификацию стандартного протокола, предложенного сообществу Internet, и служит приглашением к дискуссии в целях развития. Текущее состояние стандартизации и статус описанного здесь протокола можно узнать из документа "Internet Official Protocol Standards" (STD 1). Документ может распространяться без ограничений.

Тезисы

Этот документ описывает алгоритм DDDS (Dynamic Delegation Discovery System — динамическая система детектирования передачи полномочий) для применения динамически отыскиваемых правил преобразования строк по отношению уникальным строкам приложений. Четко определенные правила преобразования будут отражать передачу полномочий управления информацией, связанной со строкой. Этот документ является частью серии документов, полностью указанной в "Dynamic Delegation Discovery System (DDDS) Part One: The Comprehensive DDDS" (RFC 3401). Важно отметить, что чтение и понимание каждого документа этой серии невозможно без прочтения остальных документов.

Оглавление

1. Введение

Система DDDS используется для реализации простого связывания строк с данными, обеспечивающего поддержку динамически настраиваемых систем передачи полномочий (делегирования). DDDS отображает некие уникальные строки на данные, хранящиеся в DDDS Database, путем итеративного применения правил преобразования строк, пока не будут достигнуты условия завершения.

Этот документ описывает общий алгоритм DDDS, а не какие-либо частные алгоритмы или сценарии использования. Вся серия документов указана в "Dynamic Delegation Discovery System (DDDS) Part One: The Comprehensive DDDS" (RFC 3401) [1]. Важно отметить, что чтение и понимание каждого документа этой серии невозможно без прочтения остальных документов.

История DDDS включает процесс, начавшийся с работы группы Uniform Resource Name. Когда были изначально сформулированы имена URN [6], было принято решение определить полномочный сервер для URN так, чтобы (конструктивно) там не содержалось информации о местоположении в сети. Система может использовать базу данных с правилами, которые будут применяться к URN для отыскания информации о конкретных синтаксических блоках. Эта система изначально получила название RDS [7] и применялась только по отношению к URN.

С течением времени множество систем начало использовать такой же алгоритм и инфраструктуру для других, не связанных с URN, систем (см. примеры использования DDDS в главе 6). Это привело к необходимости изменения и разъяснения некоторых основополагающих допущений. Этот набор документов служит обновлением для исходных спецификаций URN, позволяющим разрабатывать новые приложения и базы правил стандартным способом.

Этот документ отменяет RFC 2168 [11] и RFC 2915 [9], а также обновляет RFC 2276 [7].

2. Терминология

Ключевые слова необходимо (MUST), недопустимо (MUST NOT), требуется (REQUIRED), нужно (SHALL), не следует (SHALL NOT), следует (SHOULD), не нужно (SHOULD NOT), рекомендуется (RECOMMENDED), возможно (MAY), необязательно (OPTIONAL) в данном документе интерпретируются в соответствии с RFC 2119.

3. Алгоритм

Алгоритм DDDS основан на концепции Правил перезаписи (Rewrite Rule). Эти правила собираются в базу DDDS Rule Database, и доступ к ним обеспечивается по уникальным ключам. Конкретное Правило, будучи примененным к Application Unique String, преобразует эту строку в новый Ключ, который может использоваться для отыскания нового Правила в Базе. Это новое правило применяется к исходной строке Application Unique String и цикл повторяется, пока не будет выполнено условие завершения. Приложению недопустимо применять правило для вывода предыдущего правила. Все Правила перезаписи для всех Приложений должны всегда применяться точно к той же строке Application Unique String, с которой алгоритм начал работу.

Фундаментальны допущением является то, что строка Application Unique String представляет собой некий тип регулярной лексической структуры, к которой применяются правила. DDDS предполагает, что лексический элемент, используемый для принятия решения о передаче полномочий, содержится в самой строке Application Unique String. DDDS не решает задачи, когда для принятия решения о делегировании требуется информация, содержащаяся за пределами строки AUS и Правила (время сутом, финансовые транзакции и т. п..).

Схема работы алгоритма показана на рисунке.

+--------- Application Unique String
|                 +----+
|                 |ввод|
|         +-------+    +----------+
|         | First Well Known Rule |
|         +-------+     +---------+
|                 |вывод|
|                 +-----+
|               Первый ключ
|                    |
|                    +----<--------------<--------------+
|                    |                                  |
|                  ключ     (База данных DDDS всегда    |
|                 +----+     принимает ключ и           |
|                 |ввод|     возвращает правило)        ^
|       +---------+    +--------+                       |
|       | Поиск в DDDS Database |                       |
|       +---------+     +-------+                       |
|                 |вывод|                               |
|                 +-----+                               |
|               Набор правил                            |
|                    |                                  |
|                    |       (вводом для правила служит |
|               Набор правил  правило и AUS.            ^
|                 +----+      Выводом всегда служит     |
+---------------->|ввод|      ключ или результат)       |
  +---------------+    +-------------------+            |
  | Правила применяются к AUS,             |            |
  | пока не будет получен результат,       |            |
  | удовлетворяющий требованиям приложения |            |
  +---------------+     +------------------+            |
                  |вывод|                               |
                  +-----+                               ^
                    ключ                                |
                     |                                  |
                     v                                  |
     +-------------------------------------+            |
     | Последнее правило было завершающим? | Нет >------+
     +-------------------------------------+
                     Да     (если правило не является завершающим,
                     |       его вывод служит новым ключом
                     |       для поиска следующего правила)
    +-----------------------------------+
    | Вывод последнего правила является |
    | результатом для приложения        |
    +-----------------------------------+

3.1 Компоненты правила

Правило содержит до 4 компонент:

3.2 Синтаксис выражения для замены

Набор (наборы) символов, используемый в выражениях для замены, определяется как Приложением, так и Базой данных. Приложение должно определить допустимый набор символов для строки AUS. Спецификация DDDS Database должна определить, какие наборы символов требуются для создания ключей и как представляется само выражение для замены. Приведенные ниже символы имеют смысл лишь при выборе определенного набора символов в базе данных и/или Приложении.

Синтаксис Выражения для замены в правилах представляет собой выражение в стиле редактора sed. Сами по себе выражения в стиле sed не подходят для использования в приложениях по ряду причин., следовательно, содержимое поля regexp должно соответствовать приведенным ниже правилам:

subst-expr   = delim-char  ere  delim-char  repl  delim-char  *flags
delim-char   = "/" / "!" / <любой октет, отсутствующий в полях 'POS-DIGIT' и 'flags'>
                   ; Все вхождения delim_char в subst_expr должны быть одинаковы
ere          = <POSIX Extended Regular Expression>
repl         = *(string / backref)
string       = *(anychar / escapeddelim)
anychar      = <любой символ, отличный от delim-char>
escapeddelim = "\" delim-char
backref      = "\" POS-DIGIT
flags        = "i"
POS-DIGIT    = "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"

Применение выражения для замены к Строке должно давать в результате ключ, который соответствует правилам базы данных (естественно, если текущий ключ не является завершающим, при котором возвращается не новый ключ, а окончательный результат). Поскольку имеется возможность некорректно задать регулярное выражение, что будет приводить к созданию неприемлемого ключа, клиентской программе следует убедиться, что результат является корректным ключом базы данных, прежде, чем использовать этот ключ.

Выражения backref в repl-части выражения для замены меняются на строку (возможно пустую) символов, заключенных в круглые скобки () в ERE-части выражения для замены. N представляет собой одиночную цифру от 1 до 9, включительно. Эта цифра задает N-ое выражение backref, которое начинается с N-ой скобки ( и продолжается до соответствующей скобки ). Например, ERE

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

имеет backref-выражения:

\1  = ABCDEFG
\2  = BCDE
\3  = C
\4  = F
\5..\9  = ошибка - нет соответствующего субвыражения

Флаг i показывает, что соответствие ERE следует проверять без учета регистра символов. Более того, любые backref-подстановки могут быть нормализованы к нижнему регистру при наличии флага i. Этот флаг имеет смысл только в тех случаях, когда Приложение и База данных определяют набор символов, в котором отказ от учета регистра символов является корректным.

Первый символ выражения для замены следует использовать, как символ-ограничитель компонент этого выражения. В выражении для замены должно быть ровно три символа-ограничителя без предшествующего escape-символа. Поскольку символы-ограничители с предшествующим символом escape будут интерпретироваться как собственно символы (не ограничители), недопустимо использовать в качестве ограничителей цифровые символы. При включении цифр будут возникать проблемы в выражениях backref. Кроме того, при наличии флагов в выражении для замены символ флага недопустимо использовать в качестве ограничителя.

3.3 Полный алгоритм

Ниже приводится алгоритм DDDS целиком.

  1. Применяется правило First Well Known Rule к строке Application Unique String и в результате возвращается ключ Key.

  2. Приложение запрашивает Базу данных для получения упорядоченного списка правил, соответствующих ключу Key.

  3. Для каждого Правила в списке используется замена с помощью Substitution Expression, применяемая с соблюдением порядка к строке Application Unique String, пока не будет возвращена непустая строка. Положение в списке фиксируется и породившее непустую строку Правило используется для следующего шага. Если на следующем шаге выбранное правило отвергается, происходит возврат к использованию Substitution Expression для оставшейся части списка правил. Если список завершится без возврата корректно соответствия, приложение уведомляется об этом.

  4. Если Описание сервиса в правиле не соответствует требованиям клиента, происходит возврат к п. 3 и продолжение работы с оставшейся частью списка правил. Если в списке имеется правило, соответствующее требованиям клиента, это Правило используется для следующего шага. В том (и только в том) случае, когда клиент способен обработать Правило и если такая обработка представляется безопасной в соответствии со спецификацией Приложения, клиент может отметить текущее Правило и продолжить выполнение п. 3, как будто правило было отвергнуто. В любом случае результатом данного этапа является одно и только одно Правило.

  5. Если Flags в Правиле показывает, что данное правило не является завершающим (NOT Terminal), происходит возврат к п. 2 с использованием полученного результата в качестве нового Ключа.

  6. Приложение уведомляется о завершении процесса и ему передаются из Правила значения Flags и Services вместе с выводом последнего выражения Substitution Expression.

4. Спецификация Приложения

Для того, чтобы описанный алгоритм стал используемым, нужно написать спецификации приложения и по крайней мере одной базы данных. Для задания спецификации приложения требуются перечисленные ниже компоненты.

В прошлом были некоторые недоразумения, касающиеся распределения нагрузки и использования DDDS Priority. Приложениям следует понимать, что Priority данного правила является лишь способом показать, что одно правило «быстрее, лучше, дешевле» другого. Если приложению требуется некий метод, позволяющий клиенту распределять нагрузку между серверами (например, взвешенный случайный выбор и т. п.), это следует реализовать за пределами алгоритма DDDS. Например, Приложение, использующее DNS Database может трактовать запись SRV, как способ обозначения того, что определенная служба действительно поддерживается несколькими скооперированными хостами. Распределение нагрузки будет осуществляться между хостами, которые идентичны с точки зрения DDDS в части путей передачи полномочий, которые имеют некий общий набор свойств или административный домен.

5. Спецификация Базы данных

В дополнение к сказанному каждое Приложение должно иметь по крайней мере одну Базу данных, в которой отыскиваются Правила. Важно отметить, что данная База может использоваться и другими Приложениями. В таких случаях каждое правило должно использовать некую комбинацию своих служб (Service) и/или выражений для замены, соответствующую только той строке Application Unique Strings, для которой правило корректно.

Спецификация базы данных должна включать перечисленные ниже компоненты.

6. Примеры

Приведенные ниже примеры служат лишь для учебных целей. Рассмотренные приложения не специфицированы в каких-либо реальных документах.

6.1 Система идентификации автомобильных деталей

В этом примере рассматривается воображаемая система, в которой собраны воедино все производители автомобилей и используется стандартизованная система кодирования различных деталей (болты, гайки, шайбы, инструменты и т. п.), которая применяется в процессе производства и ремонта автомобилей. Проблема такого рода систем заключается в том, что автомобильная промышленность является сильно распределенной и многие детали производятся различными фирмами, расположенными по всему миру. Для того, чтобы найти информацию о какой-либо детали, система должна быть способна выяснить производителя этой детали и контактировать с ним.

Для облегчения задачи идентификационные номера выделяются как часть иерархической системы, в которой первые 5 цифр являются идентификатором производителя. Следующие 3 цифры идентифицируют линейку автомобилей (например, Ford, Toyota). Остальные цифры присваиваются производителями деталей по своему усмотрению.

Автомобильная промышленность приняла решение об использовании DDDS для создания распределенной системы поиска информации, которая маршрутизирует запросы к реальным держателям данных. Отрасль специфицировала базу данных и синтаксис запросов для отыскания правил перезаписи (APIDA Network) и Приложение Auto Parts Identification DDDS Application (APIDA).

Спецификация APIDA будет определять следующее:

Спецификация Базы данных APIDA Network будет определять следующее:

В качестве иллюстрации рассмотрим деталь с кодом 4747301AB7D. Система будет брать первые 5 цифр 47473 и запрашивать в сети Правило перезаписи (Rewrite Rule). Это правило будет предоставляться базой данных о производителях деталей и позволит производителю передать полномочия далее или напрямую возвратить запрашивающему информацию EDIFAC.

Предположим для примера, что производитель возвращает Правило, которое говорит, что следующие 3 цифры нужно использовать как часть запроса к их сервису для получения нового Правила. Это новое Правило позволит производителю деталей передать полномочия на заводы по производству деталей для каждой линейки автомобилей. В нашем примере цифры 01A означают автомобили Toyota. Правило, которое возвращает производитель передает полномочия далее производителю в Японии. Это правило также означает, что данное Правило является завершающим и, таким образом, результатом последнего запроса будет информация о детали.

6.2 Служба идентификации документов

Этот пример напоминает предыдущий, поскольку документы в этой системе можно рассматривать аналогично автомобильным деталям. Различие состоит в том, что информация о документе хранится близко к его автору (обычно на его настольном компьютере). Это означает, что число передач полномочий может быть достаточно большим. Кроме того, для того, чтобы избавиться от необходимости поддержки большого плоского пространства авторов, они организованы по компаниям и подразделениям.

Предположим, что строка Application Unique String для данного примера имеет вид:

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

Спецификация приложения может выглядеть примерно так:

Спецификация базы данных для DIS LDAP Directory будет иметь вид:

В этом примере первый поиск осуществляется по организации. В результате организация может может возвратить клиенту конечный результат, если база данных этой организации содержит его. В других случаях процесс может включать дополнительные Правила и делегировать запрос вниз по иерархии к владельцу документа.

7. Вопросы безопасности

Этот документ просто определяет алгоритм DDDS и, таким образом, сам по себе не оказывает влияния на безопасность. Когда алгоритм объединяется с Базой данных и Приложением, могут возникать связанные с безопасностью вопросы, одним из которых является возможность организации атак на динамические точки делегирования.

8. Согласование с IANA

Этот документ не создает каких-либо требований к IANA. Спецификации Баз данных и Приложений могут выдвигать такие требования, но они не рассматриваются здесь.

Литература

  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 Doman 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.

Адрес автора

Michael Mealling
VeriSign
21345 Ridgetop Circle
Sterling, VA 20166 US
URI: http://www.verisignlabs.com
EMail: ten.mynoen@leahcim

Перевод на русский язык

Николай Малых, moc.milib@hkylamn