RFC 1332 The PPP Internet Protocol Control Protocol (IPCP)

Network Working Group                                    G. McGregor
Request for Comments: 1332                                     Merit
Obsoletes: RFC 1172                                         May 1992

Протокол IPCP

The PPP Internet Protocol Control Protocol (IPCP)

PDF

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

Данный RFC задает проект стандартного протокола IAB для сообщества Internet и служит приглашением к дискуссии и развитию протокола. Состояние стандартизации протокола можно найти в документе IAB Official Protocol Standards. Документ может распространяться без ограничений.

Тезисы

Протокол PPP1 [1] обеспечивает стандартный метод инкапсуляции данных протокола сетевого уровня (Network Layer) для соединений «точка-точка». PPP также определяет расширяемый протокол управления каналом LCP2 и предлагает семейство протоколов управления сетью (NCP3) для организации и настройки разных протоколов сетевого уровня.

Данный документ определяет NCP для организации и настройки IP [2] через PPP, а также метод согласования и применения компрессии заголовков TCP/IP [3] Van Jacobson для протокола PPP.

Данный RFC является результатом работы группы Point-to-Point Protocol по эгидой IETF4.

Оглавление

Исключено в версии HTML

1. Введение

PPP состоит из трех основных компонент:

  1. Метод инкапсуляции дейтаграмм для передачи через последовательные каналы.

  2. Протокол управления каналом (LCP) для организации, настройки и проверки соединений канального уровня.

  3. Семейство протоколов управления (NCP) для организации и настройки разных протоколов сетевого уровня.

Для организации связи через канал «точка-точка» каждая из сторон соединения PPP должна сначала передать пакеты LCP для настройки и проверки канала данных. После организации канала и согласования дополнительных возможностей в соответствии с потребностями LCP протокол PPP должен передать пакеты NCP для выбора и настройки одного или множества протоколов сетевого уровня. После настройки выбранных протоколов сетевого уровня через канал могут передаваться дейтаграммы этого протокола.

Канал будет сохранять коммуникационные настройки до тех пор, пока явные пакеты LCP или NCP не закроют соединение или пока не произойдет некое внешнее событие (например, тайм-аут или действия администратора).

2. Протокол NCP для IP

Протокол IPCP5 отвечает за настройку конфигурации и отключение модулей протокола IP на обеих сторонах соединения «точка-точка». IPCP использует такой же механизм обмена пакетами, какой применяется в LCP. Обмен пакетами IPCP становится возможным только после перехода протокола PPP в фазу Network-Layer Protocol. Полученные до этого пакеты IPCP следует отбрасывать без уведомления.

Протокол IPCP имеет некоторые отличия от протокола LCP [1]:

Поле Protocol в кадрах канального уровня

В точности один пакет IPCP инкапсулируется в поле Information кадров канального уровня PPP, где поле Protocol содержит шестнадцатеричное значение 8021 (IP Control Protocol).

Поле Code

Используются коды от 1 до 7 (Configure-Request, Configure-Ack, Configure-Nak, Configure-Reject, Terminate-Request, Terminate-Ack и Code-Reject). Остальные коды следует трактовать, как нераспознанные и возвращать в Code-Reject.

Тайм-ауты

Обмен пакетами IPCP не может происходить, пока PPP не достигнет фазы Network-Layer Protocol. Реализациям следует быть готовыми к ожиданию завершения Authentication и Link Quality Determination, не фиксируя тайм-аут ожидания Configure-Ack или иного отклика. Реализация предлагается фиксировать тайм-аут только после вмешательства пользователя или по истечении заданного в конфигурации времени.

Типы конфигурационных опций

IPCP имеет свой набор конфигурационных опций, которые определены ниже.

2.1. Передача дейтаграмм IP

До того, как начнется передача каких-либо пакетов IP, протокол PPP должен достигнуть фазы Network-Layer Protocol, а протокол IPCP — состояния Opened.

В точности один пакет IPCP инкапсулируется в поле Information кадров канального уровня PPP, где поле Protocol содержит шестнадцатеричное значение 0021 (Internet Protocol).

Максимальный размер пакета IP, передаваемого по каналу PPP, совпадает с максимальным размером поля Information в кадрах канального уровня PPP. Более крупные дейтаграммы IP должны фрагментироваться. Если система желает предотвратить фрагментацию и сборку фрагментов, ей следует использовать опцию TCP MSS6 [4] и механизм MTU discovery [5].

3. Конфигурационные опции IPCP

Конфигурационные опции IPCP позволяют согласовать желаемые параметры протокола IP. IPCP использует такой же формат Configuration Option, какой определен для LCP [1], но со своим набором опций.

Большинство актуальных значений поля IPCP Option Type указано в действующей редакции документа Assigned Numbers [6]. В настоящее время выделены значения:

1 IP-Addresses

2 IP-Compression-Protocol

3 IP-Address

3.1. IP-Addresses

Использование конфигурационной опции IP-Addresses не рекомендуется. Опыт показал, что достаточно сложно обеспечить схождение при согласовании этой опции для всех ситуаций. В RFC 1172 [7] приведены данные для реализаций, которым нужна совместимость со старыми версиями. Взамен данной опции предложена конфигурационная опция IP-Address и ее применение является предпочтительным.

Эту опцию не следует передавать в запросах Configure-Request при получении запроса Configure-Request с опцией IP-Addresses или IP-Address. Опцию можно передавать при получении отказа Configure-Reject для опции IP-Address или подтверждения Configure-Nak с опцией IP-Addresses, добавленной в конце.

Поддержка этой опции может быть исключена после получения протоколом IPCP статуса Internet Draft Standard.

3.2. IP-Compression-Protocol

Эта конфигурационная опция обеспечивает способ согласования использования конкретного протокола сжатия. По умолчанию компрессия отключена.

Формат опции IP-Compression-Protocol показан ниже. Поля передаются в порядка «слева направо».

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |    Length     |     IP-Compression-Protocol   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    Data ...
   +-+-+-+-+

Type

2

Length

>= 4

IP-Compression-Protocol

Поле IP-Compression-Protocol занимает два октета и указывает желаемый протокол компрессии. Значения для этого поля совпадают со значения поля PPP Data Link Layer Protocol для того же протокола сжатия.

Актуальные значения поля IP-Compression-Protocol указаны в последнем документе Assigned Numbers [6]. В настоящее время определено значение:

Шестнадцатеричное значение

Протокол

002d

Van Jacobson Compressed TCP/IP

Data

Поле Data может содержать дополнительные данные, определяемые конкретным протоколом сжатия.

Параметры, используемые по умолчанию

Протокол сжатия не используется.

3.3. IP-Address

Эта конфигурационная опция обеспечивает способ согласования адреса IP, который будет применяться на локальной стороне канала. Опция позволяет отправителю Configure-Request указать, какую опцию IP-address он желает получить, или запросить у партнера предоставление информации. Партнер может предоставить эту информацию, подтверждая (NAK) опцию или возвращая корректную опцию IP-address.

Если требуется согласование опции IP-address на удаленной стороне и партнер не включил опцию в свой Configure-Request, опцию следует добавить в конце Configure-Nak. Значение IP-address должно быть приемлемо на удаленной стороне или указывать на запрос информации от партнера.

По умолчанию IP-адрес не присваивается.

Формат конфигурационной опции IP-Address показан ниже. Поля опции передаются в порядке «слева направо».

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |    Length     |           IP-Address
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
           IP-Address (продолжение)|
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type

3

Length

6

IP-Address

4-октетное поле IP-Address указывает желаемый локальный адрес отправителя Configure-Request. Если все октеты имеют нулевые значения, это говорит о запросе информации IP-Address у партнера.

Параметры, используемые по умолчанию

IP-адрес не присваивается.

4. Компрессия заголовков TCP/IP Van Jacobson

Компрессия Van Jacobson для заголовков TCP/IP уменьшает размер заголовков вплоть до 3 байтов. Это может быть существенно для медленных последовательных линий, особенно при интерактивном трафике.

Конфигурационная опция IP-Compression-Protocol служит для индикации возможности приема пакетов со сжатыми заголовками. Если нужно сжатие в обоих направлениях, каждая сторона должна независимо запросить эту опцию.

При передаче пакетов IP значение поля PPP Protocol устанавливается в соответствии с приведенной ниже таблицей.

Шестнадцатеричное значение

21

Type IP. Пакет не относится к TCP, содержит фрагмент или не может быть сжат.

002d

Compressed TCP. Заголовки TCP/IP сжаты.

002f

Uncompressed TCP. Поле IP protocol заменено идентификатором слота.

4.1. Формат конфигурационной опции

Формат конфигурационной опции IP-Compression-Protocol для согласования компрессии Van Jacobson для заголовков TCP/IP показан ниже. Поля опции передаютсяв порядке «слева направо».

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |    Length     |     IP-Compression-Protocol   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Max-Slot-Id  | Comp-Slot-Id  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type

2

Length

6

IP-Compression-Protocol

002d (шестнадцатеричное) для сжатых по методу Van Jacobson заголовков TCP/IP.

Max-Slot-Id

Поле Max-Slot-Id размером 1 октет показывает максимальный идентификатор слота. Число реальных слотов на 1 больше, поскольку они нумеруются от 0 до Max-Slot-Id.

Примечание: Могут возникать проблемы с реализациями, поддерживающими единственный слот (Max-Slot-Id = 0), как описано в работе [3]. Например, реализация [3] будет работать только с номерами слотов от 3 до 254.

Comp-Slot-Id

Однооктетное поле Comp-Slot-Id показывает возможность сжатия поля идентификатора слота.

0 Идентификатор слота не может быть сжат. Все сжатые пакеты TCP должны иметь установленный бит C в каждой маске изменений и включать идентификатор слота.

1 Идентификатор слота может быть сжат.

Идентификатор слота не допускается сжимать, если на канальном уровне PPP отсутствует возможность индикации ошибки при получении для модуля декомпрессии. Синхронизация после ошибки зависит от получения пакета с идентификатором слота (см. обсуждение в работе [3]).

Приложение A. Рекомендуемые опции IPCP

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

IP-Compression-Protocol — не менее 4 слотов (обычно, 16).

IP-Address — только для коммутируемых телефонных линий.

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

Вопросы безопасности не рассматриваются в этом документе.

Литература

[1] Simpson, W., «The Point-to-Point Protocol», RFC 13317, May 1992.

[2] Postel, J., «Internet Protocol», RFC 791, USC/Information Sciences Institute, September 1981 (перевод).

[3] Jacobson, V., «Compressing TCP/IP Headers», RFC 1144, January 1990 (перевод).

[4] Postel, J., «The TCP Maximum Segment Size Option and Related Topics», RFC 879, USC/Information Sciences Institute, November 1983.

[5] Mogul, J., and S. Deering, «Path MTU Discovery», RFC 1191, November 1990 (перевод).

[6] Reynolds, J., and J. Postel, «Assigned Numbers», RFC 10608, USC/Information Sciences Institute, March 1990.

[7] Perkins, D., and R. Hobby, «Point-to-Point Protocol (PPP) initial configuration options», RFC 1172, August 1990.

Благодарности

Часть текста документа заимствована из RFC 1171 и RFC 1172, подготовленных Drew Perkins из Carnegie Mellon University и by Russ Hobby из University of California в Davis.

Информацию для введения опции IP-Compression предоставил Van Jacobson на конференции SIGCOMM ’90.

Bill Simpson помог с форматированием документа.

Адрес руководителя группы

С рабочей группой можно связаться через ее руководителя:

Brian Lloyd

Lloyd & Associates

3420 Sudbury Road

Cameron Park, California 95682

Phone: (916) 676-1147

EMail: brian@ray.lloyd.com

Адрес автора

Связанные с этим документом вопросы следует направлять по адресу:

Glenn McGregor

Merit Network, Inc.

1071 Beal Avenue

Ann Arbor, MI 48109-2103

Phone: (313) 763-1203

EMail: Glenn.McGregor@Merit.edu

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

Николай Малых

nmalykh@gmail.com


1Point-to-Point Protocol.

2Link Control Protocol.

3Network Control Protocol.

4Internet Engineering Task Force.

5IP Control Protocol.

6Maximum Segment Size — максимальный размер сегмента.

7Этот документ утратил силу и заменен RFC 1661 (перевод). Прим. перев.

8В соответствии с RFC 3232 документ Assigned Numbers утратил силу. Информация в настоящее время представлена в базе данных на сайте IANA. Прим. перев.




RFC 1323 TCP Extensions for High Performance

RTO Network Working Group                                V. Jacobson
Request for Comments: 1323                                       LBL
Obsoletes: RFC 1072, RFC 1185                              R. Braden
                                                                 ISI
                                                           D. Borman
                                                       Cray Research
                                                            May 1992

Расширения TCP для высокой производительности

TCP Extensions for High Performance

PDF

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

Этот документ содержит проект стандарта IAB для сообщества Internet и служит приглашением к дискусии в целях развития и совершенствования протокола. Информацию о текущем состоянии стандартизации для этого протокола вы можете найти в документе «IAB Official Protocol Standards»1. Допускается свободное распространение документа.

Тезисы

Этот документ представляет набор расширений TCP, обеспечивающих повышение производительности для путей с большими значениями произведения полосы пропускания на время кругового обхода (bandwidth*delay) и надежную работу через каналы с очень высокой скоростью. Документ определяет новые поции TCP для масштабирования окон и временных меток, которые должны обеспечить совместимость и интероперабельность с реализациями TCP, не поддерживающими это расширение. Временные метки используются для двух разных механизмов — RTTM2 и PAWS3. Селективные подтверждения не включены в этот документ.

Этот документ объединяет в себе информацию, содержащуюся в RFC 1072 и RFC 1185, отменяя действие обоих документов. Приведенные в этом документе спецификации являются более детальными. В Приложении C рассматриваются отличия от упомянутых RFC.

Оглавление

Удалено из HTML-версии

1. Введение

Протокол TCP [Postel81] был разработан для обеспечения гарантированной доставки практически во всех средах передачи, независимо от скорости, величины задержки, потери и дублирования, а также изменения порядка доставки сегментов. Работа реализаций TCP в настоящее время4 оптимизирована для передачи данных со скоростями от 100 бит/с до 107 бит/с и временами кругового обхода от 1 мсек до 100 секунд. Недавние исследования показали, что протокол TCP может работать с самыми разными путями Internet, начиная от каналов ввода-вывода со скоростью 800 Мбит/с и заканчивая модемными соединениями со скоростью 300 бит/с [Jacobson88a].

Использование оптических каналов привело к значительному росту скорости и наиболее скоростные пути вышли за те пределы, для которых изначально создавался протокол TCP. В этом документе определен набор незначительных расширений протокола TCP, которые учитывают рост производительности сетей. Документ основан на утративших силу RFC 1072 [Jacobson88b] и RFC 1185 [Jacobson90b].

Документ не дает однозначного ответа на вопрос: «Сколь быстро может работать TCP?» В документе отдельно рассматриваются вопросы производительности и надежности, в зависимости от различных параметров.

1.1 Производительность TCP

Производительность TCP зависит не только от скорости передачи, как таковой, но и от произведения скорости передачи на время кругового обхода. Это произведение bandwidth*delay определяет количество данных, которые «заполнят трубу». Эта величина определяет размер буферов, требуемых на стороне отправителя и получателя для обеспечения максимальной производительности соединения TCP через данный путь, т. е., объем данных с еще не подтвержденной доставкой, которые протокол TCP должен обеспечивать для «заполнения трубы». При больших значениях произведения bandwidth*delay могут возникать проблемы с производительностью TCP. Будем обозначать пути через Internet с большим значением произведения, как «long, fat pipe5», а сети, содержащие такие пути, как «LFN» (произносится «elephan(t)»6).

Широкополосные спутниковые каналы (например, DARPA Wideband Net) относятся к числу LFN. Например, спутниковый канал со скоростью DS1 имеет произведение скорости на время кругового обхода порядка 106 или более битов; это соответствует 100 находящимся в сети сегментам TCP размером по 1200 байтов каждый. Наземные оптические каналы также относятся к числу LFN. Например, при задержке международного канала 30 мсек и полосе DS3 (45 Мбит/с) произведение составит 106 битов.

При использовании современных реализаций TCP через пути LFN возникают 3 фундаментальных проблемы.

  1. Ограничение размера окнаЗаголовок TCP использует 16-битовое поле для передачи отправителю информации о размере окна приема. Следовательно, максимальный размер окна приема составляет 216 байт = 64 Кбайт7.Для решения этой проблемы в главе 2 данного документа определена новая опция TCP — Window Scale, позволяющая задавать размер окна более 216. Эта опция определяет неявный множитель, который используется в качестве коэффициента при определении реального размера окна из значения, полученного в заголовке TCP.
  2. Восстановление при потеряхПотеря пакетов в LFN может приводить к катастрофическому снижению производительности. Вплоть до недавнего времени корректно работающие реализации TCP могли уменьшать «размер трубы» в ответ на потерю каждого пакета и требовать использования процедуры замедленного старта для восстановления. Недавно были предложены алгоритмы Fast Retransmit8 и Fast Recovery9 [Jacobson90c]. Суммарный эффект использования этих алгоритмов заключается в том, что при потере одного пакета не происходит «сужения трубы». Однако при потере более одного пакета в окне обычно будет возникать таймаут повтора передачи с соответствующим «сужением трубы» и использованием алгоритма slow start.Увеличение размера окна с учетом полосы LFN ведет к повышению вероятности отбрасывания более одного пакета в окне. Это может существенно снижать производительность работы TCP через LFN. Кроме того, если механизм контроля насыщения основан на использовании той или иной формы случайного отбрасывания пакетов на шлюзе, отбрасывание пакетов со случайным интервалом между ними станет более распространенным и приведет к росту вероятности отбрасывания более одного пакета в окне.Для обобщения механизмов Fast Retransmit/Fast Recovery на случай потери множества пакетов в окне требуется механизм селективных подтверждений. В отличие от кумулятивных подтверждений TCP, селективные подтверждения дают отправителю полную картину сегментов, которые уже находятся в очереди на приемной стороне, и пакетов, которые еще не доставлены. Некоторые преимущества использования селективных подтверждений были приведены в работе [NBS85] и механизм селективных подтверждений был включен во множество экспериментальных протоколов Internet – VMTP [Cheriton88], NETBLT [Clark87] и RDP [Velten84], а также предложен для OSI TP4 [NBS85]. Однако при работе без LFN селективные подтверждения снижают число повторов передачи пакетов, но не приводят к росту производительности, что делает применимость этого достаточно сложного механизма весьма спорной. Вместе с тем, для случаев работы через LFN важность селективных подтверждений может значительно вырасти.RFC 1072 определяет новую опцию TCP для передачи селективных подтверждений (SACK). Однако имеется ряд важных технических проблем с форматом и семантикой опции SACK. Поэтому данная опция была исключена из предлагаемого в этом документе списка расширений. Эта опция однако может быть возвращена в процессе стандартизации10.
  3. Измерение времени кругового обходаTCP обеспечивает гарантированную доставку данных за счет повтора передачи сегментов, которые не были подтверждены в течение интервала RTO11. Аккуратное динамическое определение значения RTO имеет важное значение для производительности TCP. Значение RTO определяется путем оценки среднего значения и вариаций времени кругового обхода RTT (интервал между передачей сегмента и получением подтверждения его доставки [Jacobson88a]).В параграфе 3.212 определяется новая опция TCP Timestamps и механизм ее использования, позволяющий определять время почти для каждого сегмента (включая повторы), практически без дополнительных издержек на вычисления. Для этого механизма используется аббревиатура RTTM13, чтобы отличить его от других вариантов использования опции.

1.2 Надежность TCP

Далее мы рассмотрим вопросы надежности доставки. Повышение скорости передачи ведет к росту производительности TCP, как bandwidth*delay. Однако повышение скорости передачи может угрожать надежности доставки TCP по той причине, что не будут выполняться допущения, используемые протоколом TCP для детектирования дубликатов и нарушения порядка доставки.

Особенно серьезные неприятности могут возникать в результате нечаянного повторного использования порядковых номеров TCP в сегментах данных. Предположим, что «старый сегмент-дубликат» (например, дубликат сегмента данных, задержанного в очередях Internet) доставлен получателю в неподходящий момент и его порядковый номер попадает в текущее окно. При проверке контрольной суммы ошибки обнаружено не будет и в результате может возникнуть трудно детектируемое повреждение данных. Получение старого дубликата сегмента ACK отправителем также может приводить к серьезным неприятностям, вплоть до блокирования соединения и последующей передачи RST.

Надежность TCP зависит от наличия границы для времени жизни сегмента — MSL14. Значение MSL в общем случае требуется для любого транспортного протокола с гарантированной доставкой, поскольку поле порядкового номера имеет конечный размер и, следовательно, возможно повторное использование порядковых номеров. В стеке протоколов Internet значение MSL ограничивается временем жизни (TTL) пакетов на уровне IP.

Дублирование порядковых номеров может возникать в двух случаях:

  1. Порядковые номера достигают максимального значения в течение срока существования данного соединения.Порядковые номера TCP имеют размер 32 бита. При достаточно высокой скорости верхняя граница 32-битового пространства порядковых номеров может быть достигнута за то время, что сегмент будет находиться в очередях.
  2. Прежняя инкарнация соединения.Предположим, что соединение разрывается путем корректного или аварийного завершения и незамедлительно создается такое же (с той же парой сокетов) новое соединение. Задержанный сегмент из разорванного соединения может попасть в текущее окно и новая инкарнация воспримет его, как корректный.

От дубликатов из более ранних инкарнаций (случай 2) можно избавиться с использованием текущего фиксированного значения MSL, определенного спецификацией TCP (см. параграф 5.3 и Приложение B к этой спецификации). Однако для случая (1) предотвращение повторного использования порядковых номеров в одном соединении требует ограничивать MSL в соответствии со скоростью передачи и для высоких скоростей нужен новый механизм.

Если максимальная эффективная полоса, которая доступна TCP через конкретный путь, составляет B байтов в секунду, для безошибочной работы требуется выполнение следующего условия:

231/B > MSL (сек) [1]
Сеть

B*8

B байт/с Twrap (сек)
ARPANET

56 кбит/с

7 кбайт/с

3*105 (~3,6 дней)
DS1

1,5 Вбит/с

190 кбайт/с

104 (~3 часа)
Ethernet

10 Мбит/с

1,25 Мбайт/с

1700 (~ 30 мин.)
DS3

45 Мбит/с

5,6 Мбайт/с

380

FDDI

100 Мбит/с

12,5 Мбайт/с

170

Gigabit

1 Гбит/с

125 Мбайт/с

17

Приведенная справа таблица содержит значения Twrap = 231/B для некоторых распространенных значений полосы B.

Очевидно, что достижение границы значений порядковых номеров не составляет проблемы для сетей с коммутацией пакетов со скоростью 56 кбит/с и даже для сетей Ethernet 10 Мбит/с. С другой стороны, при скоростях DS3 и FDDI значение Twrap становится сравнимым со значением MSL=2 мин., заданным спецификацией TCP [Postel81]. При переходе к гигабитной скорости значение Twrap становится слишком малым для того, чтобы надежная доставка могла обеспечиваться принятым в Internet механизмом TTL.

16-битовое поле окна TCP ограничивает эффективную полосу B значением 216/RTT, где RTT – время кругового обхода в секундах [McKenzie89]. Если значение RTT достаточно велико, это будет ограничивать полосу B значением, которое удовлетворяет требованиям выражения [1] для большого значения MSL. Например, рассмотрим трансконтинентальную магистраль с RTT = 60 мсек. (определяется физическими параметрами). Если произведение bandwidth*delay ограничено размером максимального окна TCP (64 кбайт), полоса B будет ограничена значением 1,1 Мбит/с независимо от того, какова физическая скорость канала передачи. Это соответствует времени использования всего пространства порядковых номеров Twrap= 2000 сек., что достаточно безопасно для современной сети Internet.

Важно понимать, что причиной ограничения является не маленькое окно, а широкая полоса. В качестве примера рассмотрим (очень скоростную) ЛВС FDDI с диаметром 10 км. Используя значение скорости света, можно рассчитать значение RTT для кольца, как (2*104)/(3*108) = 67 мксек, и значение delay*bandwidth = 833 байта. Соединение TCP через такую ЛВС при размере окна 833 байта будет работать с полной скоростью 100 Мбит/с и пространство порядковых номеров будет полностью использовано за время порядка 3 минут, что очень близко к значению MSL для TCP. Таким образом, очень высокая скорость может создавать проблемы с надежностью в результате достижения максимального порядкового номера даже без применения расширенных окон.

Протокол Ватсона Delta-T [Watson81] включает механизмы сетевого уровня для точного исполнения MSL. В отличие от этого в протоколе IP механизм исполнения MSL определен слабо и еще более слабо реализован в Internet. Следовательно, неразумно полагаться на использование MSL для соединений TCP и нереально задавать значения MSL меньше принятых в настоящее время (например, меньше заданного спецификацией TCP значения 120 сек.).

Возможным решением проблемы достижения границы порядковых номеров является увеличение размера поля порядкового номера TCP. Например, поле порядкового номера (и номера подтверждения) можно расширить до 64 битов. Это можно сделать путем изменения заголовка TCP или введения новой опции.

В главе 5 предлагается иной механизм (PAWS15) повышения надежности TCP для скоростей передачи, превосходящих предсказуемые пределы. PAWS использует опцию TCP Timestamps, определенную в главе 4, для защиты от появления старых дубликатов в том же соединении.

1.3 Использование опций TCP

Все определенные в этом документе расширения используют новые опции TCP. Мы должны решить два вопроса, связанные с использованием опций TCP, — (1) совместимость и (2) дополнительные издержки.

Требуется обратить внимание на совместимость, т. е., интероперабельность с существующими реализациями. Единственная определенная ранее опция TCP MSS16 может появляться только в сегментах SYN. Каждой реализации следует игнорировать неизвестные опции в сегментах SYN (предполагается, что большинство реализаций делает это). Однако некоторые ошибочные реализации TCP могут аварийно завершать работу при первом появлении опции в сегменте, отличном от SYN. Следовательно, для каждого расширения, определенного ниже, опции TCP будут передаваться в сегментах, отличных от SYN только в тех случаях, когда обмен опциями в сегментах SYN показал, что обе стороны понимают расширение. Более того, опции расширения будут передаваться в сегментах SYN,ACK только в ответ на получение соответствующей опции в начальном сегменте SYN.

Может возникнуть вопрос о расходе полосы и дополнительных вычислениях, связанных с опциями TCP. Те опции, что появляются в сегментах SYN, не будут, очевидно, создавать проблем с производительностью. Создание соединения TCP требует выполнения значительного объема специального кода и обработка опций не приведет к существенному росту издержек в этом случае.

С другой стороны, опция Timestamps может появляться в любых сегментах данных и подтверждений (ACK), добавляя 12 байтов к 20-байтовому заголовку TCP. Мы надеемся, что полоса, сэкономленная за счет предотвращения ненужных повторов, будет больше, нежели расход полосы в связи с увеличением заголовка.

Существует также проблема дополнительного расхода вычислительных ресурсов на обработку опций переменного размера, выровненных по границе байта, в частности для процессоров с RISC-архитектурой. В Приложении A приводится рекомендуемая схема опций в заголовке TCP, обеспечивающая разумное выравнивание полей. Применяя идею метода Header Prediction17, TCP может быстро проверить эту схему и при положительном результате использовать быстрый путь. Хосты, которые используют эту каноническую схему, будут эффективно применять опции, как набор полей с фиксированным форматом, появляющихся в заголовке TCP. Однако для сохранения философии и схемы опций протокол TCP должен быть готов к разбору произвольных полей опций, пусть и менее эффективно.

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

2. Опция масштабирования окна TCP

2.1 Введение

Расширение для масштабирования окна увеличивает поле окна TCP до 32 битов и использует коэффициент масштабирования для передачи этого 32-битового размера в 16-битовом поле Window заголовка TCP (SEG.WND в RFC 793). Коэффициент масштабирования передается в новой опции TCP Window Scale. Эта опция передается только в сегменте SYN, следовательно коэффициент масштабирования фиксирован для каждого направления после того, как соединение организовано. Другим вариантом решения была установка коэффициента масштабирования для каждого сегмента TCP. Будет некорректно передавать опцию Window scale только при изменении коэффициента масштабирования, так как опция TCP в сегменте подтверждения не будет доставляться с гарантией (если ACK не объединяентся с передаваемым в обратном направлении пакетом данных). Фиксация коэффициента масштабирования при организации соединения снижает издержки, но недостатком этого варианта является невозможность изменения коэффициента масштабирования окна в процессе работы соединения.

Максимальное окно приема и, следовательно, коэффициент масштабирования определяются максимальным размером приемного буфера. В типовой современной реализации максимальное буферное пространство задается по умолчанию, но может быть изменено пользовательской программой до того, как будет организовано соединение TCP. Это определяет коэффициент масштабирования и, следовательно, не требуется дополнительный пользовательский интерфейс для масштабирования окна.

2.2 Опция Window Scale

Трехбайтовая опция Window Scale может передаваться в сегментах SYN. Опция служит двух целям: (1) показать, что протокол TCP готов масштабировать окна приема и передачи, а также (2) передать значение коэффициента масштабирования, который будет использоваться для окна приема. Таким образом, реализации TCP, готовой к масштабированию окон, следует передавать эту опцию даже при использовании коэффициента 1. Коэффициент масштабирования задается степенью числа 2 и представляется в логарифмическом масштабе, чтобы можно было реализовать масштабирование путем операции двоичного сдвига.

Опция TCP Window Scale (WSopt)

Тип: 3, размер: 3 байта

+---------+---------+---------+
| Kind=3  |Length=3 |shift.cnt|
+---------+---------+---------+

Эта опция служит предложением, а не обещанием — обе стороны должны передать опции Window Scale в своих сегментах SYN для того, чтобы разрешить масштабирование окна в каждом направлении. Если масштабирование окна разрешено, реализация TCP, которая передает эту опцию, будет смещать на shift.cnt битов вправо свой истинный размер окна (SEG.WND) перед включением размера окна в заголовок. Значение shift.cnt может быть нулевым (коэффициент масштабирования окна приема равен 1).

Эта опция может быть передана в начальном сегменте SYN (т. е., сегменте с флагом SYN, но без флага ACK) или в сегменте SYN,ACK (но только в том случае, когда опция Window Scale была получена в начальном сегменте SYN). Опции Window Scale в сегментах без флага SYN следует игнорировать.

Поле Window в сегменте с флагом SYN (т. е., SYN или SYN,ACK) никогда не масштабируется.

2.3 Использование опции Window Scale

Ниже описана модель реализации масштабирования окна с использованием нотации RFC 793 [Postel81]:

  • Все размеры окон трактуются как 32-битовые значения размера буфера для хранения блока управления соединением и локальных расчетов. Размеры задаются для окна передачи (SND.WND), окна приема (RCV.WND) и окна насыщения.
  • Состояние соединения зависит также от двух коэффициентов масштабирования Snd.Wind.Scale и Rcv.Wind.Scale, применяемых к входящим и исходящим полям размера окна, соответственно.
  • Если модуль TCP получает сегмент SYN, содержащий опцию Window Scale, он передает в ответ свою опцию Window Scale в сегменте SYN,ACK.
  • Опция Window Scale передается с shift.cnt = R, где R задает значение коэффициента, которое TCP будет использовать для своего окна приема.
  • При получении сегмента SYN с опцией Window Scale, содержащей shift.cnt = S, модуль TCP устанавливает для Snd.Wind.Scale значение S, а для Rcv.Wind.Scale — R; в противном случае для обоих параметров Snd.Wind.Scale и Rcv.Wind.Scale устанавливается нулевое значение.
  • Поле размера окна SEG.WND в заголовке каждого входящего сегмента (за исключением сегментов SYN) смещается влево на Snd.Wind.Scale перед обновлением значения SND.WND:

SND.WND = SEG.WND << Snd.Wind.Scale

(предполагается, что другие условия RFC793 выполнены и используется нотация языка C << для сдвига влево).

  • Поле размера окна для исходящих сегментов (за исключением SYN) получается из истинного размера путем сдвига SEG.WND вправо на Rcv.Wind.Scale:

SEG.WND = RCV.WND >> Rcv.Wind.Scale

TCP определяет «старые» и «новые» данные в сегментах, проверяя, попадает ли их порядковый номер в 231 байтов от левого края окна (данные, которые не попадают, считаются «старыми»). Чтобы новые и старые данные никогда не путались, левый край окна отправителя находится не более, чем на 231 байта от правого края окна получателя. Аналогичное условие выполняется и относительно левого края окна получателя и правого края окна отправителя. Поскольку правый и левый край окна отправителя или получателя отличаются на размер окна, а окна отправителя и получателя могут быть расфазированы не более, чем на величину размера окна с учетом приведенных выше ограничений, удвоенный максимальный размер окна должен быть меньше 231 или

max window < 2**30

Поскольку максимальный размер окна в 2S (где S задает число битов сдвига при масштабировании окна) превышает 216-1 (максимальный размер окна без масштабирования), для максимального размера окна гарантируется значение меньше 230, если S <= 14. Таким образом, значение счетчика сдвига не должно быть более 14 (это значение разрешает размер окна 230 байт = 1 Гбайт). Если получена опция Window Scale со значением shift.cnt, превышающим 14, модулю TCP следует записать сообщение об ошибке в системный журнал и использовать 14 взамен указанного в полученной опции значения.

Коэффициент масштабирования применяется только к значению поля Window, переданному в заголовке TCP; каждый модуль TCP, использующий расширенные окна, будет локально поддерживать для размера окна 32-битовые значения. Например, окно насыщения, рассчитываемое алгоритмами Slow Start и Congestion Avoidance, не будет увеличиваться на коэффициент масштабирования, поэтому масштабирование окна не будет оказывать влияния на расчет окна насыщения.

3. RTTM — измерение времени кругового обхода

3.1 Введение

Точная и своевременная оценка RTT необходима для адаптации изменений в условиях передачи трафика и предотвращения нестабильности, называемой «congestion collapse18» [Nagle84] в загруженной сети. Однако точное измерение RTT может оказаться затруднительным как в теории, так и для реализации.

Многие реализации TCP измеряют RTT на основе выборки единственного пакета в окне. Хотя этот метод дает адекватную оценку RTT для небольших окон, точность его неприемлема для LFN. Если рассматривать оценку RTT как задачу обработки сигналов (каковой она и является), сигнал данных с некоторой частотой (скорость передачи пакетов) будет выбираться с низкой частотой («скорость» окна). Такая редкая выборка сигналов противоречит критерию Найквиста и может, следовательно, вносить «эффект наложения» в измерение RTT [Hamming77].

Хорошая система оценки RTT с консервативным расчетом таймаута повторной передачи может быть устойчивой к «наложению» при частоте выборки, близкой к частоте данных. Например, для окна в 8 пакетов частота выборки19 составляет 1/8 от частоты данных, отличаясь меньше, чем на порядок. Однако, когда окно включает десятки и сотни пакетов, оценка RTT может давать серьезные ошибки, приводящие к ненужным повторам передачи.

Отбрасывание пакетов осложняет проблему. Zhang [Zhang86], Jain [Jain86] и Karn [Karn87] показали невозможность аккумулировать надежные оценки RTT, если при такой оценке используются передаваемые повторно сегменты. Поскольку до повтора передачи было передано полное окно данных, все сегменты этого окна будут подтверждены до того, как будет сделана следующая выборка RTT. Это означает, что между измерениями RTT пройдет по крайней мере время передачи дополнительного окна и, поскольку частота ошибок близка к одной ошибке на размер окна (например, 10-6 ошибок на бит для спутниковой сети Wideband), корректное измерение RTT становится невозможным.

Решение этой проблемы, значительно упрощающее работу отправителя, состоит в следующем — используя опции TCP, отправитель включает временную метку в каждый сегмент данных, а получатель возвращает эти временные метки в сегментах ACK. После этого одна операция вычитания дает отправителю точное значение RTT для каждого сегмента ACK (который будет соответствовать каждому сегменту данных при разумном поведении получателя). Мы назвали этот механизм RTTM.

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

3.2 Опция TCP Timestamps

Протокол TCP является симметричным и позволяет в любой момент передавать данные в обоих направлениях, следовательно возврат временных меток также может осуществляться в обоих направлениях. Для простоты и симметрии будем предполагать, что временные метки всегда передаются и возвращаются в обоих направлениях. Для повышения эффективности поля timestamp и timestamp reply объединены в одну опцию TCP Timestamps.

Опция TCP Timestamps (TSopt):

тип: 8

размер: 10 байтов

+-------+-------+---------------------+---------------------+
|Kind=8 |  10   |  TS Value (TSval)   |TS Echo Reply (TSecr)|
+-------+-------+---------------------+---------------------+
    1       1              4                     4

Опция Timestamps передает два 4-байтовых поля временных меток. Поле Timestamp Value (TSval) содержит текущее значение временной метки передающей опцию стороны TCP.

Поле Timestamp Echo Reply (TSecr) корректно только при установленном флаге ACK в заголовке TCP; в этом случае поле содержит значение временной метки, переданное удаленной стороной TCP в поле TSval опции Timestamps. Если поле Tsecr некорректно, его значение должно быть нулевым. Значение TSecr в общем случае берется из последней принятой опции Timestamp, однако имеются некоторые исключения, описанные ниже.

TCP может передавать опцию Timestamps (TSopt) в начальном сегменте SYN (т. е., в сегменте с флагом SYN, но без флага ACK), а также в других сегментах, если опция TSopt была получена в начальном сегменте SYN для этого соединения.

3.3 Механизм RTTM

Значение временной метки, которое будет передаваться в Tsval, берется из показаний (виртуальных) часов, которые называют «timestamp clock20». Показания этого хронометра для измерения RTT должны быть по крайней мере приблизительно пропорциональны реальному времени.

TCP A                                 TCP B
           <A,TSval=1,TSecr=120> ------>
<---- <ACK(A),TSval=127,TSecr=1>
           <B,TSval=5,TSecr=127> ------>
<---- <ACK(B),TSval=131,TSecr=5>
. . . . . . . . . . . . . . . . . . . . . .
           <C,TSval=65,TSecr=131> ------>
<---- <ACK(C),TSval=191,TSecr=65>
(и т. д.)

Приведенный на рисунке пример иллюстрирует односторонний поток данных без потери сегментов. A, B, C… представляют блоки данных с последовательными порядковыми номерами, а ACK(A),… представляют соответствующие кумулятивные подтверждения. Два поля временных меток опции Timestamps показаны, как <TSval= x, TSecr=y>. Каждое поле TSecr содержит значение полученного последним поля TSval.

Строка точек показывает паузу (продолжительностью в 60 временных интервалов), в течение которой узел A ничего не передает. Отметим, что эта пауза завышает значение RTT, которое узел B может взять из полученного в сегменте данных C значения TSecr=131. Таким образом, при одностороннем потоке данных механизм RTTM для обратного направления дает значение, увеличенное на продолжительность паузы в передаче данных. Однако приведенное ниже правило позволяет предотвратить ненужное увеличение RTT:

Значение Tsecr, полученное в сегменте, используется для обновления среднего значения RTT лишь в тех случаях, когда сегмент подтверждает некие новые данные (т. е., номер подтверждения смещен вперед относительно левого края окна передачи).

Поскольку TCP B не передает данных, сегмент данных C не подтверждает никаких новых данных, поэтому увеличенный на продолжительность паузы в передаче результат RTTM не используется узлом B для обновления времени кругового обхода.

3.4 Какую метку следует возвращать

Если получено более одной опции Timestamps до передачи сегмента отклика, модуль TCP должен выбрать для возврата одно из значений Tsvals, игнорируя остальные. Для минимизации числа хранимых получателем состояний (например, числа необработанных значений Tsval) получателю следует сохранять не более одной временной метки в блоке управления соединением.

Следует рассмотреть три ситуации:

  1. Задержанные подтверждения.Многие реализации TCP подтверждают лишь каждый K-ый сегмент из группы сегментов, прибывающих в течение короткого интервала времени. Такой подход обычно называют «отложенным подтверждением». Отправитель данных TCP должен измерить эффективное значение RTT, включая дополнительное время, связанное с отложенными подтверждениями, поскольку в противном случае будут переданы ненужные повторы. Таким образом, при использовании отложенных подтверждений получателю следует возвращать то значение поля Tsval, которое было включено в первый из неподтвержденных сегментов.
  2. Пропуск в порядковых номерах (потеря сегментов).Отправитель будет продолжать передачу данных до заполнения окна, а получатель может генерировать подтверждения по прибытии сегментов с нарушением порядка (например, для активизации ускоренного повтора).Потеря сегмента может говорить о перегрузке в сети и в такой ситуации отправителю следует быть консервативным при решении вопроса о повторе передачи. Более того, лучше переоценить значение RTT, нежели недооценить его. В подтверждениях сегментов, доставленных с нарушением порядка, следует по этой причине указывать временную метку из последнего принятого сегмента, который расположен впереди окна.Такая же ситуация происходит и при нарушении порядка следования пакетов в сети.
  3. Заполнение пропуска в порядковых номерах.Сегмент, который заполняет пропуск, представляет наиболее свежую информацию для измерения характеристик сети. С другой стороны, значение RTT, рассчитанное для более раннего сегмента, может включать таймаут повторной передачи для отправителя, что окажет отрицательное воздействие на полученное отправителем среднее значение RTT. Таким образом, следует передавать значение временной метки из последнего сегмента, который заполняет пропуск в порядковых номерах.

Описанный ниже алгоритм обработки опций Timestamps для синхронизированного соединения учитывает все три рассмотренных выше случая.

  1. Состояние соединения сохраняется в двух 32-битовых переменных — TS.Recent содержит временную метку для возврата в поле TSecr при передаче сегмента, а Last.ACK.sent — поле ACK из последнего переданного сегмента. Значение Last.ACK.sent будет равно RCV.NXT за исключением тех случаев, когда передача подтверждения была отложена.
  2. Если значение Last.ACK.sent попадает в диапазон порядковых номеров входящего сегмента

    SEG.SEQ <= Last.ACK.sent < SEG.SEQ + SEG.LEN

    поле TSval из этого сегмента копируется в TS.Recent; в противном случае TSval игнорируется.

  3. Когда TSopt передается, в поле TSecr помещается текущее значение TS.Recent.

Приведенные ниже примеры иллюстрируют эти правила. A, B, C… представляют сегменты, занимающие последовательные блоки порядковых номеров, а ACK(A),… представляют соответствующие сегменты подтверждения. Отметим, что ACK(A) имеет такой же порядковый номер, как B. Для простоты представлено только одно направление возврата временных меток.

                                  TS.Recent
<A, TSval=1> ------------------->
                                      1
<B, TSval=2> ------------------->
                                      1
<C, TSval=3> ------------------->
                                      1
<---- <ACK(C), TSecr=1>
(и т. д.)
                                  TS.Recent
<A, TSval=1> ------------------->
                                      1
<---- <ACK(A), TSecr=1>
                                      1
<C, TSval=3> ------------------->
                                      1
<---- <ACK(A), TSecr=1>
                                      1
<B, TSval=2> ------------------->
                                      2
<---- <ACK(C), TSecr=2>
                                      2
<E, TSval=5> ------------------->
                                      2
<---- <ACK(C), TSecr=2>
                                      2
<D, TSval=4> ------------------->
                                      4
<---- <ACK(E), TSecr=4>
(и т. д.)
  • Пакеты доставляются с сохранением порядка, некоторые подтверждения откладываются (рисунок справа).

  • В случае (A) возвращается временная метка из наиболее старого неподтвержденного сегмента.
  •  Пакеты доставляются с нарушением порядка и каждый пакет подтверждается (рисунок слева).

    В случае (B), возвращается временная метка из последнего сегмента, который находится впереди левого края окна, пока не будет доставлен отсутствующий сегмент, для которого временная метка возвращается в соответствии с (C). Такая же последовательность будет наблюдаться при потере и повторной передаче сегментов B и D..

4. PAWS — защита от перехода порядкового номера через верхнюю границу

4.1 Введение

В параграфе 4.2 описан простой механизм для отказа от приема старых сегментов-дубликатов, которые могут повредить активное соединение TCP; будем называть этот механизм PAWS (Protect Against Wrapped Sequence numbers – защита от достижения максимального значения порядкового номера). PAWS работает в масштабе одного соединения TCP, используя состояние, хранящееся в блоке управления соединением. В параграфе 4.3 и Приложении C обсуждается влияние механизма PAWS на избавление от старых дубликатов из предыдущих инкарнаций того же соединения.

4.2 Механизм PAWS

PAWS использует ту же опцию TCP Timestamps, что и механизм RTTM, описанный выше, и предполагает, что каждый принятый сегмент TCP (включая сегменты ACK) содержит временную метку SEG.TSval, значения полей которой не снижаются с течением времени. Основная идея заключается в том, что сегмент может быть отброшен как старый дубликат, если он получен со значением временной метки SEG.TSval, которое меньше полученного недавно значения временной метки для этого соединения.

В обоих механизмах PAWS и RTTM временные метки представляют собой 32-битовые целые числа без знака (модуль 232). Таким образом, отношение «меньше чем» для временных меток трактуется так же, как для порядковых номеров TCP и могут использоваться такие же методы реализации Если s и t – значения временных меток, s < t, если 0 < (t — s) < 231 при использовании арифметики 32-битовых целых чисел без знака.

Выбор принимаемых временных меток для сохранения с целью последующего сравнения должен гарантировать монотонный рост значений. Например, можно сохранить временную метку из сегмента, который был получен последним и располагается на левом краю окна приема (т. е., самый свежий из неподтвержденных сегментов). Однако вместо этого мы выберем значение TS.Recent, описанное в параграфе 3.4 для механизма RTTM, поскольку использование общего значения для механизмов PAWS и RTTM упрощает реализацию обоих. Как сказано в параграфе 3.4, TS.Recent отличается от временной метки из полученного последним сегмента с корректным порядком доставки только в случае использования отложенных подтверждений и, следовательно, меньше, чем на одно окно. Любой из вариантов выбора будет обеспечивать защиту для случаев перехода порядковых номеров через верхнюю границу пространства нумерации.

RTTM задается синхронно, поэтому временные метки Tsval, передаваемые в сегментах данных и подтверждений, будут возвращаться в полях Tsecr, передаваемых в ответ подтверждений или сегментов данных. PAWS подвергает все входящие сегменты однотипной проверке и, следовательно, обеспечивает защиту от дубликатов сегментов данных и подтверждений. Дополнительный асимметричный алгоритм будет защищать от старых дубликатов ACK — отправитель данных будет отвергать входящие сегменты ACK, в которых значение TSecr меньше, чем аналогичное значение, сохраненное из последнего сегмента ACK, в котором номер подтверждения располагается впереди левого края окна передачи.

Временные метки Tsval, передаваемые в сегментах SYN и SYN,ACK, используются для инициализации PAWS. Механизм PAWS защищает от старых дубликатов сегментов без флага SYN и дубликатов сегментов SYN, полученных в засинхронизированном состоянии соединения. Дубликаты сегментов SYN и SYN,ACK, полученные при отсутствии соединения, будут отбрасываться обычной процедурой 3-этапного согласования и проверки порядковых номеров TCP.

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

4.2.1 Базовый алгоритм PAWS

Алгоритм PAWS требует выполнения перечисленных ниже операций для всех входящих сегментов синхронизированного соединения:

  1. Если в полученном сегменте имеется опция Timestamps, SEG.TSval < TS.Recent и значение TS.Recent корректно (см. ниже), принятый сегмент трактуется, как неприемлемый:в ответ передается подтверждение, как указано в RFC 793 (стр. 6921), а сегмент отбрасывается22.
  2. Если сегмент не попадает в окно, его следует отвергнуть (обычная обработка TCP).
  3. Если прибывающий сегмент удовлетворяет условию SEG.SEQ Last.ACK.sent (см. параграф 3.4), временная метка записывается в TS.Recent.
  4. Если прибывающий сегмент не нарушает порядок доставки (т. е., располагается на левом краю окна), он воспринимается нормально.
  5. В остальных случаях сегмент трактуется как попадающий в окно и доставленный с нарушением порядка (т. е., сегмент помещается в очередь для доставки пользователю).

Этапы R2, R4 и R5 являются стандартными этапами обработки TCP, определенными в RFC 793.

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

Предположим, что была передана последовательность сегментов A.1, B.1, C.1, …, Z.1, в которой буква представляет порядковый номер, а цифра – временную метку. Предположим также, что сегмент B.1 был потерян. Временная метка в TS.TStamp будет иметь значение 1 (из сегмента A.1), поэтому сегменты C.1, …, Z.1 будут рассматриваться как приемлемые и помещены в очередь. Когда B будет передан повторно, как B.2 (с использованием новой временной метки), он заполнит пропуск и приведет к подтверждению всех сегментов вплоть до Z и доставке их пользователю. При этом временные метки из пакетов, находящихся в очереди, не будут проверяться заново, поскольку эти сегменты уже были приняты. При получении сегмента B.2 для переменной TS.Stamp будет установлено значение 2.

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

В некоторых маловероятных ситуациях правила R1-R4 могут приводить к неоправданному отбрасыванию некоторых пакетов, как показано в следующем примере.

Предположим, что сегменты A.1, B.1, C.1, …, Z.1 переданы с соблюдением порядка и сегмент B.1 потерян. Кроме того, предположим, что некоторые из сегментов C.1, … Z.1 были задержаны и получены после доставки получателю повторного сегмента B.2. Эти задержанные сегменты будут неоправданно отброшены, поскольку в них будут содержаться устаревшие временные метки.

Описанная ситуация маловероятна. Если повтор передачи был вызван таймаутом, некоторые из сегментов C.1, … Z.1 должны быть задержаны, на время, превышающее RTO. Это представляется маловероятным, если не предположить возникновение множества ложных таймаутов и повторов передачи. Если повтор передачи сегмента B был вызван алгоритмом Fast Retransmit (т. е, дубликатами ACK), находящиеся в очереди сегменты, которые вызвали передачу этих дубликатов, уже должны быть получены.

Даже при задержке сегмента на время больше RTO механизм Fast Retransmit [Jacobson90c] будет приводить к повторной передаче задержанных пакетов одновременно с B.2, избавляя от дополнительного периода RTT и, следовательно, минимально снижая производительность.

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

4.2.2 Хронометр временных меток

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

Используемый получателем алгоритм предъявляет некоторые требования к хронометру временных меток.

  1. Хронометр временных должен быть не «слишком медленным».Показания хронометра должны изменяться не менее одного раза за время передачи 231 байтов. Фактически, для того, чтобы хронометр приносил отправителю пользу при оценке времени кругового обхода, его показания должны изменяться не реже одного раза за время передачи окна данных и даже при использовании расширения окна в соответствии с RFC 1072 231 байтов данных должны размещаться по крайней мере в двух окнах.Переходя к цифрам, можно сказать, что часы с изменением показаний 1 раз в секунду будут обеспечивать предотвращение старых дубликатов при скорости канала ~8 Гбит/с. Временные метки с разрешением 1 мсек будут работать при скорости канала до 8 Тбит/с (8*1012 бит/с)!
  2. Хронометр временных должен быть не «слишком быстрым».Время полного цикла отсчета времени хронометром должно быть больше MSL. Поскольку временная метка имеет размер 32 бита, а MSL не более 255 секунд, максимально допустимая скорость хода хронометра составляет 1 «тик» за каждые 59 нсек.Однако желательно иметь значительно более продолжительный цикл отсчета для того, чтобы обрабатывать устаревшие временные метки в бездействующих соединениях (см. параграф 4.2.3) и снизить требования к MSL для защиты от перехода порядковых номеров через верхнюю границу. При дискретности хронометра в 1 мсек 32-битовые временные метки начнут повторяться через 24,8 дней. Таким образом, это обеспечит возможность предотвращения старых дубликатов из того же соединения, если значение MSL не превышает 24,8 дней. Такой вариант представляется очень безопасным — значения MSL в 24,8 дней или больше могут вероятно предполагаться шлюзовыми системами без требования точного исполнения MSL на основе значения TTL на уровне IP.

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

Механизм PAWS предъявляет жесткое требование монотонности изменения показаний хронометра временных меток на стороне отправителя. Способы выполнения этого требования зависят от оборудования и программ, используемых в системе.

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

4.2.3 Устаревшие временные метки

Если соединение в течение достаточно долгого времени бездействует, бит знака хронометра временных меток другой стороны TCP поменяет значение, хранящееся в переменной TS.Recent значение становится слишком старым и механизм PAWS будет приводить к отбрасыванию всех последующих сегментов, «замораживая» соединение (пока бит знака хронометра временных меток не восстановит свое значение).

При использовании выбранного периода изменения показаний хронометра временных меток (от 1 мсек. до 1 cек.) период смены знака будет составлять от 24,8 до 24800 дней. Маловероятно, что кто-то будет сохранять бездействующие соединения TCP дольше 24 дней. Тем не менее, внесение каких-либо ограничений на срок жизни соединений TCP нежелательно.

Поэтому мы требуем, чтобы реализация PAWS включала механизм признания значения TS.Recent «некорректным», если соединение бездействует более 24 дней. Другим вариантов решения проблемы устаревших временных меток является передача сегментов keepalive с очень малой частотой, которая, тем не менее, превышает частоту перехода значения таймера временных меток через максимум (например, можно передавать 1 такое сообщение в день). Эти сообщения будут вносить пренебрежимо малые издержки. Однако спецификация протокола не включает сегментов keepalive, поэтому было выбрано решение констатировать некорректность TS.Recent, как сказано выше.

Отметим, что модуль TCP не знает частоты и, следовательно, времени полного цикла отсчета хронометра другого узла TCP, поэтому ему следует исходить из худших предположений. Корректность TS.Recent требуется проверять только в тех случаях, когда не проходит базовая проверка PAWS для временной метки (например, если SEG.TSval < TS.Recent). Если обнаружена некорректность TS.Recent, сегмент принимается независимо от результата проверки временной метки и правило R3 обновляет TS.Recent значением TSval из нового сегмента.

Для детектирования продолжительности бездействия соединения TCP может обновлять показания часов или значение временной метки, связанные с соединением, например, при обновлении значения TS.Recent. Детали этого процесса определяются реализацией.

4.2.4 Предсказание заголовка

Header prediction [Jacobson90a] представляет собой метод реализации высокопроизводительного транспортного протокола, который важнее всего для высококскоростных каналов. Этот метод оптимизирует код для более общего случая корректного приема сегментов с сохранением порядка. При использовании предсказания заголовков получатель задает вопрос: «Является этот сегмент следующим по порядку?» Ответ на этот вопрос требует меньшего числа процессорных команд, нежели ответ на вопрос: «Попадает ли этот сегмент в окно?»

Добавление предсказания заголовков к процедурам работы с временными метками ведет к приведенной ниже рекомендуемой процедуре обработки прибывающего сегмента TCP:

  1. Проверка временной метки (см. R1 выше).
  2. Процедура предсказания заголовка — если сегмент является следующим по порядку и не требуется специальной дополнительной обработки, сегмент принимается, значение временной метки сохраняется и этап H3 пропускается.
  3. Выполняется обычная обработка сегмента в соответствии с RFC 793. Эта обработка включает отбрасывание сегментов, выходящих за пределы окна, может включать передачу подтверждения и включает размещение в очереди относящихся к окну сегментов, которые доставлены с нарушением порядка.

Возможен вариант замены местами этапов H1 и H2, т. е., выполнение сначала процедуры предсказания заголовка H2, а затем выполнения H1 и перехода к H3 только при негативном результате предсказания заголовка. Это может обеспечить повышение производительности, поскольку проверка временной метки на этапе H1 с большой вероятностью дает позитивный результат, а для ее выполнения требуется использование интервальной арифметики на конечном поле, что занимает достаточно много ресурсов. Выполнение этой проверки для каждого отдельного сегмента противоречит философии предсказания заголовка. Мы надеемся, что это изменение может снизить расход процессорного времени на обработку заголовка TCP в высокоскоростных сетях на 5-10%.

Однако перенос этапа H2 в начало связан с опасностью — сегмент из 232 прошлых байтов может быть принят точно в неподходящее время и ошибочно принят на этапе предсказания заголовка. В работе [Jacobson90b] был отмечен ряд причин, по которым вероятность такого события можно считать пренебрежимо малой.

Если все сегменты показывают себя, как старые дубликаты, вероятность того, что старый дубликат точно соответствует левому краю окна, будет равна частному от деления размера максимального сегмента (MSS) на размер пространства порядковых номеров. Это значение должно быть меньше 2-16, поскольку значение MSS должно быть меньше 216 (например, для каналов FDDI это отношение будет 212/232 = 2-20). Однако для наиболее старого сегмента сохранение его в сети Internet менее очевидно и вероятность того, что старый дубликат точно попадает в левый край окна, должна быть много меньше 2-16.

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

Однако вероятностные аргумента принимаются не всеми и в настоящий момент принято решение, согласно которому повышение производительности в общем случае не оправдывает возникающего риска. Следовательно, рекомендуется выполнять сначала этип H1, а затем H2.

4.3. Дубликаты из прежних инкарнаций соединения

Механизм PAWS обеспечивает защиту от ошибок, связанных с достижением порядковым номером верхней границы диапазона на высокоскоростных соединениях. Сегменты из предыдущих инкарнаций того же соединения также могут быть причиной появления старых дубликатов. В обоих случаях механизм TCP для предотвращения таких ошибок зависит от контроля максимального срока жизни сегмента (MSL) на уровне IP (см. Приложение к RFC 1185, где этот вопрос рассмотрен детально). В отличие от случая достижения максимальных значений порядковых номеров требование соблюдения MSL для предотвращения дубликатов из прежних инкарнаций не зависит от скорости передачи. Если уровень IP ограничивает рекомендуемым значением (2 минуты) MSL для протокола TCP и протокол TCP следует правилам, соединения TCP не будут подвергаться опасному воздействию дубликатов из предыдущих инкарнаций, независимо от скорости работы сети. Следовательно, механизм PAWS в этом случае не требуется.

Остается вопрос — может ли механизм PAWS обеспечить дополнительную защиту от дубликатов из предшествующих соединений, которая позволила бы ослабить требование ограничения MSL на уровне IP. В Приложении B, где рассматривается этот вопрос, показано, что нужны дополнительные допущения и/или механизмы, помимо PAWS. Это выходит за пределы данного расширения.

5. Заключение и благодарности

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

Механизмы реализуются с использованием новых опций TCP для масштабирования окна и временных меток. Метки используются двумя разными механизмами — RTTM (измерение времени кругового обхода) и PAWS (защита от ошибок при достижении верхней границы порядковых номеров).

Опция Window Scale была изначально предложена Mike St. Johns из USAF/DCA. Текущая форма этой опции была разработана Mike Karels из UC Berkeley в ответ на более громоздкую схему, которую предложил Van Jacobson. Lixia Zhang помог с описанием механизма PAWS, предложенного в RFC 1185.

В заключение отметим, что значительная часть этой работы основана на результатах обсуждений в рабочей группе End-to-End Task Force теоретических ограничений транспортных протоколов вообще и TCP, в частности. Позднее члены рабочей группы вместе с другими участниками почтовой конференции end2end внесли существенный вклад в поиск недостатков в алгоритмах и описании. Авторы выражают свою признательность за эту работу.

6. Литература

[Clark87] Clark, D., Lambert, M., and L. Zhang, «NETBLT: A Bulk Data Transfer Protocol», RFC 998, MIT, March 1987.

[Garlick77] Garlick, L., R. Rom, and J. Postel, «Issues in Reliable Host-to-Host Protocols», Proc. Second Berkeley Workshop on Distributed Data Management and Computer Networks, May 1977.

[Hamming77] Hamming, R., «Digital Filters», ISBN 0-13-212571-4, Prentice Hall, Englewood Cliffs, N.J., 1977.

[Cheriton88] Cheriton, D., «VMTP: Versatile Message Transaction Protocol», RFC 1045, Stanford University, February 1988.

[Jacobson88a] Jacobson, V., «Congestion Avoidance and Control», SIGCOMM ’88, Stanford, CA., August 1988.

[Jacobson88b] Jacobson, V., and R. Braden, «TCP Extensions for Long-Delay Paths», RFC 1072, LBL and USC/Information Sciences Institute, October 1988.

[Jacobson90a] Jacobson, V., «4BSD Header Prediction», ACM Computer Communication Review, April 1990.

[Jacobson90b] Jacobson, V., Braden, R., and Zhang, L., «TCP Extension for High-Speed Paths», RFC 1185, LBL and USC/Information Sciences Institute, October 1990.

[Jacobson90c] Jacobson, V., «Modified TCP congestion avoidance algorithm», Message to end2end-interest mailing list, April 1990.

[Jain86] Jain, R., «Divergence of Timeout Algorithms for Packet Retransmissions», Proc. Fifth Phoenix Conf. on Comp. and Comm., Scottsdale, Arizona, March 1986.

[Karn87] Karn, P. and C. Partridge, «Estimating Round-Trip Times in Reliable Transport Protocols», Proc. SIGCOMM ’87, Stowe, VT, August 1987.

[McKenzie89] McKenzie, A., «A Problem with the TCP Big Window Option», RFC 1110, BBN STC, August 1989.

[Nagle84] Nagle, J., «Congestion Control in IP/TCP Internetworks», RFC 896, FACC, January 1984.

[NBS85] Colella, R., Aronoff, R., and K. Mills, «Performance Improvements for ISO Transport», Ninth Data Comm Symposium, published in ACM SIGCOMM Comp Comm Review, vol. 15, no. 5, September 1985.

[Postel81] Postel, J., «Transmission Control Protocol – DARPA Internet Program Protocol Specification», RFC 793, DARPA, September 1981.

[Velten84] Velten, D., Hinden, R., and J. Sax, «Reliable Data Protocol», RFC 908, BBN, July 1984.

[Watson81] Watson, R., «Timer-based Mechanisms in Reliable Transport Protocol Connection Management», Computer Networks, Vol. 5, 1981.

[Zhang86] Zhang, L., «Why TCP Timers Don’t Work Well», Proc. SIGCOMM ’86, Stowe, Vt., August 1986.

Приложение A: Предложения по реализации

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

+--------+--------+--------+--------+
|  NOP   |  NOP   | TSopt  |   10   |
+--------+--------+--------+--------+
|          TSval timestamp          |
+--------+--------+--------+--------+
|          TSecr timestamp          |
+--------+--------+--------+--------+

Приложение B: Дубликаты из прежних инкарнаций соединения

Рассматриваются два случая: (1) системный сбой (с потерей состояния соединений) с перезапуском и (2) повторная организация соединения без потери данных о состоянии. Эти ситуации рассматриваются в отдельных параграфах.

B.1 Системный отказ с потерей состояния

Бездействие TCP в течение периода MSL используется после системного сбоя/перезапуска с потерей информации о состоянии соединений. Разъяснения приведены в параграфе «Когда нужно сохранять паузу24» спецификации протокола TCP [Postel81]. Продолжительность требуемого интервала MSL не зависит от скорости передачи в сети. Текущее значение TCP MSL (2 минуты) представляется разумным компромиссом, поскольку многие системы загружаются после отказа в течение примерно такого времени.

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

Для полного отказа от периода бездействия нужно, чтобы часы хоста были синхронизированы с часами, которые сохраняют отсчет времени в период отказа/перезапуска системы и обеспечивают точность меток не хуже «одного тика». От этого жесткого требования можно отступить, чтобы воспользоваться преимуществами аппроксимации при синхронизации часов. Предположим, что часы всегда синхронизируются за N «тиков» и время загрузки (при необходимости дополненное периодом бездействия) составляет более N «тиков». Это будет гарантировать монотонный рост значений временных меток, что позволяет использовать метки для отбрасывания старых дубликатов даже без выполнения требований MSL.

B.2 Повторная организация соединения

При завершении соединения TCP задержка 2*MSL в состоянии TIME-WAIT связывает пару сокетов на 4 минуты (см. параграф 3.5 в [Postel81]). Работающее по протоколу TCP приложение, которое закрыло соедиение и открывает новое (например, при передаче данных по протоколу FTP в потоковом режиме), должно каждый раз выбирать новую пару сокетов. Задержка TIME-WAIT используется в двумя разными целями:

  1. Реализация полнодуплексного согласования для гарантированного закрытия TCP.Подходящее время для задержки на этапе окончательного закрытия соединения реально не связано с MSL — оно зависит от RTO для сегментов FIN и, следовательно, от значения RTT для пути. (Можно сказать, что передавшая сегмент FIN сторона знает требуемый уровень надежности и, следовательно, она должна быть способна определить размер задержки TIME-WAIT для получателя FIN. Это можно обеспечить с помощью подходящей опции TCP в сегментах FIN.)Хотя формально верхняя граница для RTT не задается, опыт эксплуатации сетей говорит, что значения RTT более 1 крайне маловероятны. Таким образом, 4-минутная задержка в состоянии TIME-WAIT удовлетворительно обеспечивает надежное полнодуплексное завершение TCP. Отметим еще раз, что эта задержка не зависит от требований MSL и скорости сети.Состояние TIME-WAIT может вызывать опосредованные проблемы, если приложению требуется достаточно часто закрывать одно соединение и открывать другое, поскольку число доступных на хосте портов TCP меньше 216. Однако высокая скорость сети не является основным источником этой проблемы — RTT ограничивает скорость открытия и закрытия соединений. Следовательно, с ростом скорости сети эта проблема не усугубляется.
  2. Обеспечить исчезновение старых дубликатов сегментов.Для замены этой функции состояния TIME-WAIT нужен механизм, работающий с разными соединениями. Механизм PAWS определен строго для работы в рамках одного соединения — последняя временная метка TS.Recent хранится в блоке управления соединением и отбрасывается при закрытии соединения.В TCP может быть добавлен дополнительный механизм кэширования на уровне хоста последних временных меток, полученных из всех соединений. Кэшированные метки могут использоваться механизмом PAWS для отбрасывания старых дубликатов сегментов из предшествующих инкарнаций соединения, если гарантируется, что значение таймера временных меток увеличилось хотя бы на один «тик» с момента открытия старого соединения. Это будет требовать, чтобы за время задержки TIME-WAIT + RTT значения временных меток на стороне отправителя различались по крайней мере на «один тик». Подобное расширение не входит в число предложений данного RFC.Отметим наличие варианта механизма, который предложили Garlick, Rom, и Postel [Garlick77], требующий от каждого хоста поддерживать для соединений записи, включающие максимальные значения порядковых номеров для этого соединения. При использовании вместо номеров временных меток достаточно сохранять одно значение на каждый удаленный хост25, независимо от числа одновременных соединений с этим хостом.

Приложение C: Отличия от RFC 1072 и RFC 1185

Расширения протокола, определенные в этом документе, имеют ряд существенных отличий от расширений RFC 1072 и RFC 1185.

  1. Опция SACK была «отложена» во втором документе.
  2. Точные правила передачи временных меток (см. параграф 3.4) имеют ряд существенных отличий. Прежние правила могли приводить к занижению значения RTT в некоторых ситуациях (отбрасывание и нарушение порядка достаки).
  3. Одно значение TS.Recent сейчас используется двумя разными механизмами RTTM и PAWS. Это упрощение стало возможным в результате изменения (b).
  4. Устранена неоднозначность RFC 1185 в пользу включения временных меток в сегменты ACK, наряду с сегментами данных. Это поддерживает симметрию протокола TCP.
  5. Опции echo и echo reply из RFC 1072 объединены в одну опцию Timestamps в целях сохранения симметрии и упрощения обработки.
  6. Решена проблема устаревших временных меток для соединений с продолжительным бездействием (параграф 4.2.2).
  7. В RFC 1185 предлагается сначала использовать предсказание заголовка, а потом — проверку временной метки. На основе некоторого скептицизма в части вероятностных аргументов, приведенных в параграфе 4.2.4, принято решение об изменении порядка операций.
  8. Спецификация изменена так, что опции расширения будут передаваться в сегментах SYN,ACK только в тех случаях, когда эти опции были получены в соответствующих сегментах SYN. Это обеспечивает наиболее консервативный подход к вопросам взаимодействия с реализациями, которые не поддерживают расширений.

В дополнение к существенным изменениям данный RFC пытается однозначно задать спецификации алгоритмов путем представления изменений в правила обработки событий из RFC 793 (см. Приложение E).

Приложение D: Использованные обозначения

Далее описаны обозначения, использованные в данном документе.

Опции

WSopt — опция масштабирования окна TCP.
TSopt — опция TCP Timestamps (временные метки)

Поля опций

shift.cnt — байт масштабирования размера окна в WSopt.
TSval — 32-битовое значение поля Timestamp Value в TSopt.
TSecr — 32-битовое значение поля Timestamp Reply в TSopt.

Поля опций в текущем сегменте

SEG.TSval — поле TSval из TSopt в текущем сегменте.
SEG.TSecr — поле TSecr из TSopt в текущем сегменте.
SEG.WSopt — 8-битовое значение в WSopt

Значения таймеров

my.TSclock — 32-битовые значения временных меток из локального источника.
my.TSclock.rate — период my.TSclock (от 1 мсек до 1 сек).

Переменные состояния соединений

TS.Recent — полученная последней временная метка.
Last.ACK.sent — переданное последним поле ACK.

Snd.TS.OK — 1-битовый флаг.
Snd.WS.OK — 1-битовый флаг.

Rcv.Wind.Scale — коэффициент масштабирования (показатель степени) окна приема.
Snd.Wind.Scale — коэффициент масштабирования (показатель степени) окна передачи.

Приложение E: Обработка событий

Вызов OPEN

...

Выбирается начальное значение порядкового номера для передачи (ISS). Передается сегмент SYN вида:

<SEQ=ISS><CTL=SYN><TSval=my.TSclock><WSopt=Rcv.Wind.Scale>
...

Вызов SEND

Состояние CLOSED (TCB не существует)

...

Состояние LISTEN

Если задан удаленный сокет, пассивное соедиение заменяется активным и выбирается ISS. Передается сегмент SYN, содержащий опции Tsval=my.TSclock и WSopt=Rcv.Wind.Scale. Устанавливается значение SND.UNA для ISS, SND.NXT для ISS+1.
Переход в состояние SYN-SENT. …

Состояние SYN-SENT

Состояние SYN-RECEIVED

Состояние ESTABLISHED

Состояние CLOSE-WAIT

Буфер сегментируется и передается с прицепленным подтверждением (значение подтверждения = RCV.NXT). …
Если установлен флаг срочности (urgent) …
Если установлен флаг Snd.TS.OK, опция TCP Timestamps Tsval=my.TSclock,TSecr=TS.Recent включается включается в каждый сегмент.
Масштабируется окно приема в заголовке сегмента для передачи:

SEG.WND = (SND.WND >> Rcv.Wind.Scale).

Прибытие сегмента

Если состояние LISTEN, то

сначала проверить флаг RST

затем проверить флаг ACK

в-третьих, проверить флаг SYN

Если флаг SYN установлен, проверить security. Если …

Если SEG.PRC < TCB.PRC, продолжить.

Проверить опцию масштабирования окна (Wsopt). Если она присутствует, сохранить SEG.WSopt в Snd.Wind.Scale и установить флаг Snd.WS.OK. В противном случае установить нулевые значения Snd.Wind.Scale и Rcv.Wind.Scale, а также сбросить флаг Snd.WS.OK.

Проверить опцию Tsopt. Если она присутствует, сохранить SEG.TSval в переменной TS.Recent и установить флаг Snd.TS.OK.

Установить RCV.NXT = SEG.SEQ+1, IRS = SEG.SEQ, прочие элементы управления и текст помещаются в очередь для последующей обработки. Следует выбрать значение ISS и передать сегмент SYN вида:

<SEQ=ISS><ACK=RCV.NXT><CTL=SYN,ACK>

Если установлен флаг Snd.WS.OK, включить в сегмент опцию WSopt=Rcv.Wind.Scale. Если установлен флаг Snd.TS.OK, включить в сегмент опцию TSopt с TSval=my.TSclock,TSecr=TS.Recent. Установить Last.ACK.sent = RCV.NXT.

Установить SND.NXT = ISS+1 и SND.UNA = ISS. Состояние соединения следует сменить на SYN-RECEIVED. Отметим, что все прочие элементы управления и данные (комбинируемые с SYN) обрабатываются в состоянии SYN-RECEIVED, но повторять обработку SYN и ACK не следует. Если прослушивание не было задано полностью (т. е., не полностью задан удаленный сокет), следует заполнить незаданные поля.

В-четвертых, прочие элементы управления и текст

Если состояние SYN-SENT, то

сначала проверить флаг ACK

в-четвертых, проверить флаг SYN

Если флаг SYN установлен, а поля security/compartment26 и precedence27 имеют приемлемые значения, устанавливается RCV.NXT = SEG.SEQ+1, IRS = SEG.SEQ, а любые сегменты из очереди на повтор, которые в связи с этим становятся подтвержденными, следует удалить.

Проверить опцию масштабирования окна (Wsopt). Если опция присутствует, сохранить SEG.WSopt в Snd.Wind.Scale, в противном случае установить нулевые значения для Snd.Wind.Scale и Rcv.Wind.Scale.

Проверить опцию Tsopt. Если она присутствует, сохранить SEG.TSval в переменной TS.Recent и установить флаг Snd.TS.OK в блоке управления соединением. Если установлен флаг ACK, используется значение my.TSclock — SEG.TSecr в качестве начальной оценки RTT.

Если SND.UNA > ISS (сегмент SYN подтвержден), сменить состояние соединения на ESTABLISHED, сформировать и передать сегмент ACK:

<SEQ=SND.NXT><ACK=RCV.NXT><CTL=ACK>

Если установлен флаг Snd.Echo.OK, включить в сегмент ACK опцию Tsopt с Tsval=my.TSclock,TSecr=TS.Recent. Установить Last.ACK.sent = RCV.NXT.

Можно включить данные и элементы управления, размещенные в очереди на передачу. Если в сегментеимеются другие элементы управления или данные, их обработка будет продолжена на шестом этапе, описанном ниже, где проверяется флаг URG. В остальных случаях происходит возврат управления.

Иначе осуществляется переход в состояние SYN-RECEIVED, формируется и передается сегмент SYN,ACK:

<SEQ=ISS><ACK=RCV.NXT><CTL=SYN,ACK>

Если установлен флаг Snd.Echo.OK в сегмент включается опция Tsopt с Tsval=my.TSclock,TSecr=TS.Recent. Если установлен флаг Snd.WS.OK, в сегмент включается опция WSopt=Rcv.Wind.Scale. Устанавливается Last.ACK.sent = RCV.NXT.

Если в сегменте имеются другие элементы управления или данные, их обработка продолжается после перехода в состояние ESTABLISHED. Осуществляется возврат управления.

В-пятых, если ни один из флагов SYN и RST не установлен, сегмент отбрасывается с возвратом управления.

В противном случае

Сначала проверяется порядковый номер

Состояние SYN-RECEIVED

Состояние ESTABLISHED

Состояние FIN-WAIT-1

Состояние FIN-WAIT-2

Состояние CLOSE-WAIT

Состояние CLOSING

Состояние LAST-ACK

Состояние TIME-WAIT

Сегменты обрабатываются по порядку. Начальные проверки служат для отбрасывания старых дубликатов и дальнейшая обработка осуществляется в соответствии со значениями SEG.SEQ. Если содержимое сегмента относится к старой и новой части, обрабатывать следует только новую часть.

Масштабируется поле окна приема:

TrueWindow = SEG.WND << Snd.Wind.Scale

и значение TrueWindow используется на последующих этапах вместо SEG.WND.

Проверяется наличие в сегменте опции Timestamps и установка флага Snd.TS.OK. Если опция есть и флаг установлен:

Если SEG.TSval < TS.Recent, проверяется, не бездействовало ли соединение более 24 дней. Если то и другое справедливо, сегмент является неприемлемым и для него выполняются описанные ниже действия.

Если SEG.SEQ = Last.ACK.sent, значение SEG.ECopt сохраняется в переменной TS.Recent.

Существует четыре случая при проверке приемлемости входящего сегмента:

Если входящий сегмент неприемлем, в ответ следует передать подтверждение (если установлен флаг RST, сегмент отбрасывается с возвратом управления):

<SEQ=SND.NXT><ACK=RCV.NXT><CTL=ACK>

Для Last.ACK.sent устанавливается значение SEG.ACK из подтверждения. Если установлен флаг Snd.Echo.OK, в сегмент ACK включается опция Timestamps с TSval=my.TSclock,TSecr=TS.Recent. Устанавливается Last.ACK.sent = SEG.ACK и передается сегмент ACK. После передачи подтверждения неприемлемый сегмент отбрасывается с возвратом управления.

В-пятых, проверяется поле ACK.

Если бит ACK не установлен, сегмент отбрасывается с возвратом управления.

Если флаг ACK установлен

Состояние ESTABLISHED

Если SND.UNA < SEG.ACK =< SND.NXT, устанавливается SND.UNA <- SEG.ACK. Рассчитывается новое значение периода кругового обхода. Если установлен флаг Snd.TS.OK, используется my.TSclock — SEG.TSecr; в противном случае используется оценка времени, прошедшего с момента передачи первого сегмента из очереди на повтор. Все сегменты из очереди повтора в результате считаются полностью подтвержденными …

В-седьмых, обрабатываются данные сегмента.

Состояние ESTABLISHED

Состояние FIN-WAIT-1

Состояние FIN-WAIT-2

Передается подтверждение вида:

<SEQ=SND.NXT><ACK=RCV.NXT><CTL=ACK>

Если установлен флаг Snd.TS.OK в сегмент ACK включается опция Timestamps с TSval=my.TSclock,TSecr=TS.Recent. Для Last.ACK.sent устанавливается значение SEG.ACK из подтверждения и подтверждение передается. Это подтверждение следует прицеплять к передаваемому сегменту, если это не приведет к недопустимой задержке подтверждения.

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

В данном документе вопросы безопасности не рассматриваются.

Адреса авторов

Van Jacobson
University of California
Lawrence Berkeley Laboratory
Mail Stop 46A
Berkeley, CA 94720
Phone: (415) 486-6411
EMail: van@CSAM.LBL.GOV

Bob Braden
University of Southern California
Information Sciences Institute
4676 Admiralty Way
Marina del Rey, CA 90292
Phone: (310) 822-1511
EMail: Braden@ISI.EDU

Dave Borman
Cray Research
655-E Lone Oak Drive
Eagan, MN 55121
Phone: (612) 683-5571
Email: dab@cray.com


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

Николай Малых

nmalykh@protocols.ru

 

1В настоящее время документ называется “Internet Official Protocol Standards” (STD1). Текущая версия STD1 опубликована в RFC 3700. Прим. перев.

2Round Trip Time Measurement — измерение времени кругового обхода.

3Protect Against Wrapped Sequences — защита от перехода порядкового номера через максимально возможное значение.

4Май 1992 г. Прим. перев.

5Длинная, толстая труба.

6Слон. Прим. перев.

7В оригинале указано «65Kbytes». Прим. перев.

8Ускоренный повтор передачи.

9Ускоренное восстановление.

10В несколько измененной форме эта опция была «возвращена» в RFC 2018, перевод которого имеется на сайте www.protocols.ru. Прим. перев.

11Retransmission timeout — таймаут повтора передачи.

12В оригинале ошибочно указано, что эта опция определена в главе 4. Прим. перев.

13Round Trip Time Measurement – измерение времени кругового обхода

14Maximum Segment Lifetime — максимальный срок жизни сегмента.

15Protect Against Wrapped Sequence — защита от перехода порядкового номера через максимально возможное значение.

16Максимальный размер сегмента. Прим. перев.

17Предсказание заголовка.

18Коллапс насыщения.

19При выборке одного пакета из окна. Прим. перев.

20Хронометр временных меток.

21Страница 23 опубликованного на сайте www.protocols.ru перевода RFC 793. Прим. перев.

22Передача сегмента ACK требуется для того, что сохранить возможность работы механизма детектирования и восстановления полуоткрытых соединений TCP. Примером может служить рисунок 10 в RFC 793.

23Перевод этого стандарта имеется на сайте http://www.protocols.ru. Прим. перев.

24Название параграфа спецификации дано в соответствии с переводом, опубликованным на сайте www.protocols.ru. Прим. перев.

25С которым организовано соединение TCP. Прим. перев.

26Безопасность/разделение.

27Предпочтения.




RFC 1322 A Unified Approach to Inter-Domain Routing

Network Working Group                                      D. Estrin
Request for Comments: 1322                                       USC
                                                          Y. Rekhter
                                                                 IBM
                                                             S. Hotz
                                                                 USC
                                                            May 1992

 

Унифицированная модель междоменной маршрутизации

A Unified Approach to Inter-Domain Routing

PDF

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

Этот документ содержит информацию для сообщества Internet. Документ не задает каких-либо стандартов Internet. Допускается свободное распространение документа.

Тезисы

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

Примечание: Работа D. Estrin и S. Hotz финансировалась Национальным научным фондом (National Science Foundation) по контракту NCR-9011279 с GTE Laboratories. Работа Y. Rekhter финансировалась Агентством перспективных оборонных проектов DARPA1 по контракту DABT63-91-C-0019. Выводы и заключения, содержащиеся в этом документе могут отличаться от точки зрения DARPA и NSF.

1.0 Постановка задачи

Глобальную среду межсетевого взаимодействия2 можно представить в виде модели из множества хостов, соединенных между собой через каналы связи и коммутационные узлы3. Управление хостами, каналами и коммутаторами, которые совместно образуют ресурсы глобальной сети2, не является однородным и распределено между множеством областей администрирования. Ресурсы, находящиеся под единым управлением, образуют домен. Для поддержки автономности и гетерогенности доменов маршрутизацию делят на две компоненты – внутридоменную4 (внутреннюю) и междоменную5 (внешнюю). Внутренняя маршрутизацию обеспечивает поддержку обмена данными между хостами, которые связаны каналами и коммутаторами, относящимися к одному домену. Междоменная маршрутизация обеспечивает поддержку обмена данными между хостами в тех случаях, когда данные передаются через каналы и коммутаторы множества доменов. Устройства, пересылающие пакеты через границу домена называются граничными маршрутизаторами (BR6). Устройства, отвечающие за обмен данными междоменной маршрутизации, называют маршрутными серверами (RS7). Функции RS и BR могут быть реализованы в одном устройстве8.

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

  1. ограничения на выбор транзитных сетей, вносимые отправителями, получателями и транзитными сетями;
  2. различные типы запрашиваемого и предлагаемого сервиса;
  3. наличие множества операторов с различными схемами оплаты.

Наличие многочисленных комбинаций перечисленных критериев с разными весами значительно усложняет механизмы, обеспечиваемые традиционными архитектурами поэтапной маршрутизации9 [ISIS10589, OSPF, Hedrick88, EGP].

Текущий подход к междоменной маршрутизации в сообществе можно разделить по двум направлениям, одно из которых лучше всего представлено архитектурой BGP10/IDRP11 [BGP91, Honig90, IDRP91], а другое — архитектурой IDPR12 [IDPR90, Clark90]. В этом документе предложено рассматривать эти две архитектуры, как дополняющие, а не взаимоисключающие.

Предполагается, что в течение следующих 5 — 10 лет будут появляться новые типы сервиса, для обеспечения которых будут развернуты специальные устройства. Хотя число и разнообразие маршрутов, обеспечиваемых архитектурами поэтапной маршрутизации с поддержкой TOS13 (например, множественные маршруты с метками), достаточно для большей части трафика, важно отметить востребованность механизмов поддержки эффективной маршрутизации специализированных типов трафика через особые маршруты. Примерами особых маршрутов являются:

  1. маршруты, проходящие через один или множество транзитных доменов, которые нежелательны с точки зрения домена отправителя;
  2. маршруты через транзитные домены, которые поддерживают недостаточно широко используемый сервис.

Все прочие маршруты будем относить к базовому типу.

Желание эффективно поддерживать специальные маршруты ведет к исследованию вопроса о динамической организации маршрутов [Breslau-Estrin91, Clark90, IDPR90]. В работе [Breslau-Estrin91] рассмотрен выбор алгоритма междоменной маршрутизации на базе правил и особо рассмотрены вопросы, связанные со специфическими для отправителя маршрутами и другими «специальными» маршрутами. По результатам рассмотрения сделан вывод о том, что для поддержки специальных маршрутов лучше всего подходят алгоритмы с заданием маршрута отправителем и расширенные алгоритмы маршрутизации по состоянию каналов14; далее эта модель будет называться «маршрутизацией по запросу отправителя»15. Однако архитектура с маршрутизацией по запросу отправителя, если ее сделать единственной архитектурой междоменной маршрутизации, приводит к возникновению проблем масштабирования, поскольку эта архитектура не включает иерархической кластеризации и агрегирования маршрутной информации. Например, если маршрут из промежуточного транзитного домена X к домену получателя Y используется 1000 доменов-отправителей, IDPR требует организации и поддержки состояний для каждого из 1000 маршрутов в транзитных граничных шлюзах между доменами X и Y. В противоположность этому, другая модель междоменной маршрутизации, основанная на поэтапной маршрутизации и распределенной системе расчета маршрутов (см. ниже), обеспечивает широкую поддержку агрегирования, а также абстрагирование информации о доступности, топологии и пересылке пакетов. Такую модель используют протоколы BGP и IDRP [BGP91, IDRP91]. Хотя архитектура BGP/IDRP способна обеспечить маршрутизацию для очень большого числа сетей, основанных на использовании дейтаграмм, эта архитектура не обеспечивает поддержки специальных требований к маршрутам и гибкости маршрутизации IDPR.

1.1 Обзор унифицированной архитектуры

Мы хотим обеспечить поддержку специальных маршрутов, а при отсутствии необходимости в таких маршрутах — возможность использовать агрегирование. Следовательно, наша масштабируемая архитектура междоменной маршрутизации состоит из двух компонент — маршрутизации по запросу отправителя (SDR3) и узловой маршрутизации (NR16). Компонента NR обеспечивает расчет и организацию маршрутов, совместно используемых большим числом отправителей. Эти обычные маршруты широко используются и распространяются, следовательно для них имеет важное значение возможность агрегирования. Компонента SDR рассчитывает и организует специальные маршруты, используемые небольшим количеством отправителей, когда нет смысла использовать NR17. Потенциально большое число различных специальных маршрутов вкупе с их редким использованием делают для таких маршрутов использование механизма NR неоправданно дорогим.

Хорошей аналогией может служить производство продукции общего назначения. Когда имеется предсказуемая картина спроса, компания может выпускать и продавать серийную продукцию. В рассматриваемой архитектуре NR обеспечивает поддержку «серийных» маршрутов. Если запросы невозможно предсказать, производитель принимает заказы и выпускает продукцию по мере необходимости. Кроме того, если продукция настолько специфична, что ее потребляет один или несколько заказчиков, потребители могут повторно запрашивать продукцию, даже если потребность в ней предсказуема, поскольку потребители не создают достаточно большого рынка для серийного выпуска продукции. SDR обеспечивает для таких специальных случаев маршрутизацию по запросам.

Объединяя NR и SDR мы обеспечим поддержку междоменной маршрутизации в глобальных сетях достаточно большого размера с одновременной эффективной поддержкой маршрутов со специализированными требованиями.

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

Хотя функции пересылки пакетов в компонентах NR и SDR слабо связаны между собой, механизм обмена информацией о связности для SDR опирается на сервис, обеспечиваемый компонентой NR.

1.2 Структура документа

В разделе 2 очерчены требования и приоритеты для разработки компонент NR и SDR. В разделах 3 и 4 описано устройство NR и SDR, соответственно, в свете приведенных здесь требований. Раздел 5 описывает поддержку протокола для унифицированной архитектуры и кратко рассматривает процесс перехода к ее использованию. Последний раздел содержит краткое резюме.

2.0 Архитектурные требования и приоритеты

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

2.1 Сложность

Сложность междоменной маршрутизации должна оцениваться на основе следующих метрик производительности:

  1. издержки на хранение (storage overhead);
  2. издержки на расчеты (computational overhead);
  3. издержки на сообщения (message overhead).

Такая оценка имеет существенное значение для определения масштабируемости любой архитектуры.

2.1.1 Издержки на хранение

Издержки на хранение для объекта, принимающего участие в междоменной маршрутизации, связаны с необходимостью хранения базы маршрутной информации RIB19 и базы информации о пересылке FIB20. База RIB содержит маршрутную информацию которой объекты обмениваются с использованием протокола междоменной маршрутизации; данные RIB являются источником информации для расчета маршрутов. База FIB содержит информацию, которую объекты используют для пересылки междоменного трафика; данные FIB являются результатом расчета маршрутов. Для того, чтобы уровень издержек на хранение был приемлемым, базы FIB и RIB должны по мере увеличения числа доменов в глобальной сети расти существенно медленней линейной функции (например, близко к логарифмической). Для удовлетворения этих требований в части RIB архитектура должна обеспечивать механизмы агрегирования и абстрагирования маршрутной информации и информации о пересылке или нахождения подмножества этой информации по запросу. Для удовлетворения требований в части FIB архитектура должна обеспечивать механизмы агрегирования информации о пересылке (для рассчитанных маршрутов NR) или динамической организации/отзыва этой информации (для рассчитанных маршрутов SDR).

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

2.1.2 Издержки на расчеты

Работа компоненты NR основана преимущественно на предварительном расчете маршрутов. Если междоменная маршрутизация используется повсеместно, предварительно рассчитанные маршруты включают все достижимые точки назначения. Следовательно, сложность таких расчетов следует минимизировать. В частности, весьма желательна реализация в архитектуре той или иной формы частичного расчета, при котором расчет результатов изменения топологии будет требовать меньших ресурсов, нежели полный расчет. Даже при необходимости проведения полного расчета сложность его должна расти в зависимости от числа доменов медленней, чем линейная функция.

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

Ни при каких обстоятельствах не допускается экспоненциальный рост сложности расчетов в зависимости от числа доменов (ни для NR, ни для SDR).

2.1.3 Дополнительный расход полосы

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

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

2.2 Агрегирование

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

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

База маршрутной информации RIB содержит три типа данных:

  1. топология (например, соединения между доменами или группами доменов);
  2. доступность на сетевом уровне;
  3. ограничения на транзит.

Агрегирование маршрутных данных должно приводить к снижению размера всех трех компонент. Агрегирование информации о пересылке будет следовать за агрегированием информации о доступности.

Кластеризация (путем формирования конфедераций доменов) позволяет решить следующие задачи агрегирования:

  1. сокрытие части реальной физической топологии и связанное с этим абстрагирование топологических данных;
  2. объединение множества достижимых объектов в один объект для снижения издержек на хранение;
  3. выражение ограничений на транзит в терминах кластеров, а не отдельных доменов.

Как отмечено в работе [Breslau-Estrin91], архитектура должна разрешать формирование и изменение конфедераций без излишних операций по настройке и координированию. В частности, создание конфедерации не должно требовать какой-либо глобальной координации (например, требуемой в ECMA [ECMA89]. Кроме того, агрегирование не должно требовать явного указания взаимного расположения каждого домена относительно других доменов (например, от доменов или конфедераций не должно требоваться согласия на частичное упорядочение — кто за кем и т. п.).

Архитектура должна позволять различным доменам использовать разные методы агрегирования и абстрагирования. Например, исследователь из IBM может организовать маршрут в USC как объект доменного уровня для получения преимуществ в результате специальной обработки TOS для получения доступа к USC или даже транзита через этот домен. В то же время некий сотрудник Digital Equipment Corporation может видеть информацию на уровне California Educational Institutions Confederation и знать лишь, что USC является членом этой конфедерации. В дополнение к сказанному USC может видеть часть внутренней структуры IBM Confederation (на уровне доменов), тогда как UCLA может маршрутизировать конфедерацию доменов IBM только как единое целое.

Поддержка конфедераций должна быть гибкой. В частности, архитектура должна позволять перекрытие конфедераций без их полной вложенности (например, домен или группа доменов могут быть частью одной или множества конфедераций). Например, USC может быть частью California Educational Institutions Confederation и частью US R&D Institutions Confederation, хотя эти конфедерации не являются подмножеством по отношению одна к другой. Другой пример, T.J. Watson Research Center может быть частью NYSERNET Confederation и частью IBM-R&D-US Confederation. Хотя в обоих примерах зона перекрытия представляет собой один домен, возможны случаи, когда зона перекрытия состоит из множества доменов. В качестве примера рассмотрим множество доменов, формирующих IBM Confederation, и другое множество, образующее DEC Confederation. В конфедерации IBM есть домен IBM-Research, а в конфедерации DEC — DEC-Research. Оба эти домена могут участвовать в некой совместной работе с организацией между ними прямого соединения. В таком случае архитектура должна позволять ограничить использование этого канала так, чтобы другие домены IBM Confederation не могли использовать канал для связи с другими доменами DEC Confederation. Подобные примеры возникают и в тех случаях, когда транснациональная корпорация формируют конфедерацию, а отдельные филиалы в каждой стране могут входить в соответствующие конфедерации своей страны. Корпорации в таких случаях может потребоваться предотвращение использования своего домена в качестве транзитного внутри страны (в соответствии с локальной или международной политикой). Все приведенные выше примеры показывают ситуации с перекрытием конфедераций при необходимости контроля трафика, который проходит через перекрывающиеся ресурсы.

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

2.3 Правила маршрутизации

Правила маршрутизации, которые должна поддерживать архитектура, можно в общем случае, отнести к правилам транзита и правилам выбора маршрутов [Breslau-Estrin 91, Estrin89].

Вносимые правилами транзита ограничения могут быть обусловлены разными причинами. Архитектура должна поддерживать ограничения по адресам отправителя/получателя, типу обслуживания (TOS), идентификации класса пользователя (UCI22), оплате и пути [Estrin89, Little89]. Архитектура должна обеспечивать возможность задания правил транзита для всех маршрутов (NR и SDR). Даже для широко используемых маршрутов NR с незначительными ограничениями по отправителям и получателям, маршруты NR могут иметь некую транзитную классификацию (например, ограничения по TOS, стоимости, классу пользователей). Если широко используемый маршрут к адресатам имеет классификацию политики, последняя должна анонсироваться NR с явным указанием транзитных ограничений.

Правила выбора маршрутов позволяют каждому домену выбрать один маршрут к адресату из множества доступных маршрутов к нему. Для обеспечения максимальной автономии и независимости доменов архитектура должна поддерживать гетерогенные правила выбора маршрутов, когда каждый домен может использовать свои критерии выбора. Этот аргумент уже приводился в более ранних документах [IDPR90, Clark90, Breslau-Estrin91] применительно к выбору маршрута, задаваемого отправителем. Кроме того, каждый транзитный домен должен иметь возможность задания своих критериев выбора маршрутов, предоставляемых ему соседями. На практике это является прямым следствием приведенного выше требования — если мы позволяем выражать правила выбора для маршрутов NR, мы не можем предполагать что все домены будут использовать такие же правила. Для поддержки разнородных правил выбора маршрутов одним из ключевых моментов является разграничение междоменной и внутридоменной маршрутизации [ECMA89, Estrin89]. Однако поддержка всех возможных правил выбора маршрутов не относится к числу задач архитектуры. Список неподдерживаемых правил выбора маршрутов приведен ниже в параграфе 2.3.2.

2.3.1 Сокрытие маршрутной информации

Архитектура не должна требовать от всех доменов глобальной сети показа их связности и ограничений на транзит. Домены должны иметь возможность выполнения своих правил транзита при минимальном анонсировании своих соединений и правил транзита. В архитектуре не следует требовать, чтобы все домены в межсетевой среде (internet) выявляли связи между собой и транзитные ограничения; анонсирование следует выполнять на основе критерия «необходимо знать». Более того, анонсирование правил транзита доменам, которые не могут воспользоваться этими правилами, будет увеличивать объем информации, которую требуется хранить, обрабатывать и распространять. Для маршрутизаторов поддержка полной информации о междоменной топологии и правилах транзита может быть не только неудобной, но и просто запрещенной.

2.3.2 Неподдерживаемые правила

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

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

2.4 Поддержка TOS-маршрутизации

В этом документе упоминается поддержка TOS24-маршрутизации. Ведется много исследований и разработок в части сетевой архитектуры и протоколов для обработки широкополосного multimedia-трафика. Часть такого трафика чувствительна к задержкам, другая часть требует широкой полосы. Неразумно предполагать, что одна коммуникационная система, развернутая в масштабах глобальной сети (включая все городские, региональные и магистральные сети) обеспечит однородную поддержку всех типов трафика. Для поддержки различающихся требований в гетерогенной среде будут использоваться различные механизмы управления ресурсами (например, различные варианты резервирования ресурсов) в разных частях глобальной сети [ST2-90, Zhang91].

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

2.5 Общее в компонентах маршрутизации

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

2.6 Взаимодействие с адресацией

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

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

3.0 Устройство компоненты NR

В этом разделе рассматривается компонента NR с учетом рассмотренных выше архитектурных требований и приоритетов. При обсуждении NR предполагается поэтапная (hop-by-hop) маршрутизация. Задаваемая отправителем маршрутизация имеет иные ограничения и используется для компоненты SDR.

3.1 Обзор NR

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

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

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

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

Потенциальное снижение объемов маршрутной информации и информации о пересылке находиться в сильной зависимости от способа распределения адресов и структурирования доменов и конфедераций. «Если отсутствует корреляция между иерархией распределения адресов и организацией доменов маршрутизации, … для каждого домена маршрутизации OSIE потребуется включить запись в таблицу маршрутизации на каждой граничной IS27 всех остальных доменов маршрутизации» [Oran89]. Бесспорно, что масштабирование компоненты NR почти полностью предсказуемо на основе на основе допущения о наличии общего соответствия между иерархией агентств по распределению адресов и способами организации доменов маршрутизации, при котором становится возможным эффективное и частое агрегирование и абстрагирование данных маршрутизации и пересылки. Следовательно, по природе междоменной маршрутизации в целом и NR-компоненты, в частности, масштабируемость архитектуры сильно зависит от гибкости схемы для агрегирования и абстрагирования, а также вносимых такой схемой предварительных условий. Более того, благодаря гибкости архитектуры, эффективность работы (масштабируемость) глобальной сети в целом или отдельных ее частей будет зависеть от соотношения между гибкостью и агрегированием.

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

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

3.2 Выбор алгоритма маршрутизации для NR

С учетом того, что компонента NR, основанная на поэтапной маршрутизации, требуется для обеспечения масштабируемой и эффективной междоменной маршрутизации, остальная часть этого раздела посвящена фундаментальным вопросам выбора алгоритма маршрутизации для NR.

Обычно при обсуждении алгоритмов маршрутизации рассматриваются алгоритмы на основе состояния канала (link state — LS) и векторов удаления (distance vector — DV). Однако простые протоколы DV (например, Routing Information Protocol [Hedrick88]) не обеспечивают должного масштабирования в связи с возникновением проблем схождения28. Для решения этой проблемы были разработаны усовершенствованные протоколы DV [Jaffee82, Zaumen91, Shin87], использующие механизмы синхронизации или дополнительную информацию о пути. Для случая междоменной маршрутизации добавление информации о пути имеет важное значение для политики поддержки. Следовательно, алгоритмы, рассматриваемые для NR, будут работать на основе состояния каналов и один из таких алгоритмов мы назвали PV29. Хотя характеристики алгоритмов LS в общем случае понятны (см., например, [Zaumen 91]), мы должны отвлечься от обсуждения для краткого описания концепций алгоритма PV30.

3.2.1 Обзор протокола Path Vector

Протоколы маршрутизации BGP31 [BGP91] и IDRP32 [IDRP91] являются примерами использования алгоритма PV. BGP представляет собой протокол маршрутизации между автономными системами в сетях TCP/IP. IDRP представляет собой протокол междоменной маршрутизации OSI, который планируется стандартизировать в ISO33. Поскольку в терминах функциональности BGP представляет собой подмножество IDRP, в оставшейся части документа будет обсуждаться только протокол IDRP.

Алгоритм маршрутизации, реализованный в PV, имеет некоторое сходство с традиционным алгоритмом маршрутизации Беллмана-Форда (Bellman-Ford) в том смысле, что каждый граничный маршрутизатор анонсирует соседним BR34 доступных для него адресатов. Однако алгоритм маршрутизации PV дополняет анонсы доступных адресатов информацией о свойствах пути к этим адресатам.

Эта дополнительная информация представляется в форме атрибутов пути. Для подчеркивания тесной связи пути к адресату и свойств этого пути PV определяет маршрут как пару «путь — атрибуты пути». Это объясняет название протокола «path-vector» — BR получает от соседних BR вектор, содержащий пути к множеству адресатов35. Путь, выражаемый в терминах доменов (или конфедераций), через которые он проходит, передается как специальный атрибут, содержащий последовательность доменов маршрутизации, через которые прошла информация о доступности адресатов. Подавление маршрутных петель реализуется с помощью специального атрибута пути в отличие от алгоритмов LS36 и DV37, использующих монотонно возрастающую глобальную метрику для выбора маршрута [Shin87].

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

3.3 Сложность

На основе приведенного выше описания алгоритма PV мы можем сравнить его с алгоритмами LS в терминах определенных выше параметров сложности.

3.3.1 Издержки на хранение

Без учета агрегирования маршрутной информации и издержек, связанных с ограничениями на транзит можно показать, что в достаточно типовых условиях средние издержки на хранение RIB для схемы PV при одном значении TOS принимают значение в диапазоне от O(N) до O(Nlog(N)), где N задает общее число доменов маршрутизации [Rekhter91]. LS RIB без агрегирования маршрутной информации, без учета ограничений на транзит при общем для всех доменов наборе правил выбора маршрутов для одного значения TOS потребуется топологическое отображение домена в целом, размер которого составит O(N).

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

Способность дополнительного снижения издержек на хранение обеспечивается алгоритмом PV за счет того, что расчет маршрутов выполняется до их распространения и в соседние домены передается только информация о маршрутах, выбранных доменом. В противоположность этому выбор маршрута с использованием LS оторван от распространения маршрутной информации и не оказывает влияния на это распространение.

Хотя в теории агрегирование маршрутной информации может снижать издержки на хранение как для LS, так и для PV, только агрегирование топологической информации дает одинаковый эффект в обоих алгоритмах. Агрегирование транзитных ограничений при использовании LS может приводить к потере информации, но при использовании PV этого не происходит.

Агрегирование гетерогенных правил выбора маршрутов весьма проблематично для LS. В PV распространения правил выбора маршрутов не происходит, поэтому агрегирование правил выбора не создает проблем39.

Поддержка разных значений TOS имеет одинаковое влияние на LS и PV.

Потенциально размер LS FIB можно уменьшить при расчете маршрутов на каждом узле по запросу. Однако реальный эффект будет сильно зависеть от картины трафика, размера памяти и стратегии кэширования. Если трафик не является в значительной степени локальным, может наблюдаться некоторое снижение производительности за счет избыточного расхода ресурсов на вычисление маршрутов и дополнительной задержки связанной с расчетом при пересылке пакетов новым адресатам. Если расчет маршрутов по запросу не используется для LS, размер FIB будет одинаковым для LS и PV.

3.3.2 Сложность расчета маршрутов

Даже при использовании одинаковых правил выбора маршрутов во всех доменах сложность расчета маршрутов в PV меньше, нежели в LS. Расчет в PV состоит из оценки недавно полученного маршрута и сравнения его с имеющимся40, тогда как расчет в LS требует использования алгоритма SPF41 (например, Dijkstra).

При использовании PV изменения топологии вызывают необходимость пересчета только для тех маршрутов, на которые воздействуют эти изменения, что более эффективно, нежели полный пересчет. Однако за счет того, что в каждый вектор удаленности включается полная информация о пути, эффект изменения топологии может простираться существенно дальше, нежели для традиционных алгоритмов на основе вектора удаленности. С другой стороны, число доменов, на которые изменения воздействуют при использовании PV может быть меньше, чем при традиционной поэтапной маршрутизации на основе LS. При использовании PV необходимость пересчета маршрутов возникает только в тех доменах, чьи маршруты были изменены, тогда как при традиционной поэтапной маршрутизации с использованием LS требуется пересчет во всех доменах. Хотя в LS также можно реализовать частичный пересчет (например, при изменении топологии пересчитываются только измененные маршруты), «изучение показывает, что изменение незначительного числа каналов (возможно 2) ожидаемая сложность расчетов нарастающих обновлений превышает сложность полного пересчета» [ANSI87-150R]. Однако такие проверки существенно проще, нежели полное выполнение процессов SPF.

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

Поскольку NR опирается прежде всего на предварительный расчет маршрутов, агрегирование оказывает существенное влияние на долгосрочную масштабируемость архитектуры. В известной степени агрегирование упрощается при использовании PV за счет снижения сложности вычислений. Хотя подобные аргументы можно использовать и по отношению к LS, возможности агрегирования в LS более проблематичны, поскольку LS опирается на согласованные топологические планы каждого узла. Не очевидно также повышение сложности расчетов, связанное с транзитными ограничениями и неоднородными правилами выбора маршрутов в LS.

3.3.3 Дополнительный расход полосы

Маршрутные обновления PV распространяются в открытом виде42. Анонсируется полный маршрут для каждого поддерживаемого TOS. В LS значение TOS лишь несколько увеличивает размер маршрутного анонса, что значительно меньше числа анонсируемых маршрутов. Хотя значения TOS в LS могут кодироваться более эффективно, нежели в PV, информация о состоянии каналов лавинно рассылается во все домены, тогда как в PV обновления маршрутов распространяются только в те домены, которые эти маршруты используют. Следовательно, трудно в общем виде сравнивать дополнительный расход полосы для разных схем, когда все прочие условия совпадают.

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

3.4 Агрегирование

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

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

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

3.5 Правила

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

Все транзитные ограничения LS могут поддерживаться в PV, но не наоборот. Иными словами, существуют некоторые транзитные ограничения (например, связанные с конкретным путем), которые легко реализуются в PV, а их поддержка в LS связана со значительными издержками. Например, не очевидно как NR при использовании LS сможет поддерживать правила в стиле ECMA, основанные на иерархических отношениях между доменами, хотя такие правила достаточно просто поддерживаются в PV.

Как показано выше, поддержка гетерогенных правил выбора маршрутов непрактична для поэтапной маршрутизации LS по причине значительных издержек на расчеты и хранение маршрутов. Напротив, PV поддерживает гетерогенный выбор маршрутов без дополнительных издержек.

3.6 Сокрытие информации

PV имеет явные преимущества в части сокрытия указанной части информации. Поэтапная маршрутизация LS основана на возможности поддерживать во всех доменах в точности совпадающую информацию — это вступает в явное противоречие с возможностью сокрытия заданной части информации. Т. е., требование сокрытия части информации не может быть удовлетворено для поэтапной маршрутизации LS.

3.7 Общее в компонентах NR и SDR

В работе [Breslau-Estrin91] рассмотрено использование алгоритма LS для маршрутизации SDR. Следовательно, имеются некоторые предпочтения для использования LS с маршрутизацией NR. Однако в силу некоторых причин маршрутная информация NR и SDR не совпадает в точности даже при использовании одного алгоритма. Более того, имеется несколько предложений по унификации обработки (распространение и хранение) маршрутной информации и информации о пересылке даже при использовании разных алгоритмов.

При рассмотрении различий между NR и SDR мы должны обратить внимание на несколько аспектов:

  1. Маршрутная информация и протокол распространения: LS для SDR в достаточной степени отличается от использования LS при маршрутизации NR. Например, в SDR алгоритму LS не требуется агрегировать домены; напротив в SDR алгоритму LS требуется детальная информация для генерации специальных маршрутов. В дополнение к этому существенные для NR требования согласованности не имеют значения для компоненты SDR. Следовательно информация LS для компоненты SDR может быть получена по запросу, тогда как компонента NR должна использовать лавинную рассылку топологической информации.
  2. Алгоритм расчета маршрутов: Не очевидно в каких случаях компоненты SDR и NR могут использовать общие алгоритмы расчета маршрутов в связи с трудностями поддержки гетерогенных правил выбора маршрутов в NR.
  3. Информация о пересылке: Использование различных алгоритмов расчета маршрутов не препятствует однотипной пересылке пакетов в обеих компонентах. Даже при использовании LS с компонентой NR, требования будут такими же, т. е., агент пересылки может определить, когда следует использовать предварительно рассчитанные маршруты NR, а когда — организовать маршрут SDR для пересылки конкретных пакетов данных.

В заключение отметим, что использование похожих алгоритмов и механизмов в компонентах SDR и NR будет давать преимущества. Однако эти преимущества не будут доминировать над другими факторами, рассмотренными выше.

3.8 Резюме

С учетом издержек, связанных с глобальной маршрутизацией, агрегирование маршрутной информации имеет важное значение; в то же время, мы отмечали, что такое агрегирование должно быть гибким. В связи с трудностями поддержки поэтапной маршрутизации LS при наличии (a) гибкого агрегирования, (b) гетерогенных правил выбора маршрутов и (c) неполноты или несогласованности маршрутной информации, мы не видим альтернативы использованию алгоритма PV для компоненты NR в предлагаемой архитектуре.

С учетом отмеченного выше наша компонента NR использует архитектуру PV, в которой расчет и организация маршрутов осуществляется в распределенной манере маршрутизаторами, принимающими участие в работе NR-компоненты44.

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

4.0 Маршрутизация по запросу отправителя (SDR)

Междоменные маршрутизаторы, участвующие в работе компоненты SDR, пересылают пакеты в соответствии с маршрутной информацией, рассчитанной и организованной доменами, из которых исходит трафик (доменами source routing).

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

В общем случае информация, используемая доменами source routing для расчета маршрута по запросу отправителя, отражает административное (но не рабочее) состояние элементов маршрутизации (т. е., заданной топологии и правилам)45. Следовательно, для домена source routing возможен расчет маршрута, который не является работающим на момент организации. Компонента SDR пытается уведомить исходный домен об отказе при попытке организации маршрута. Подобно этому, компонента SDR обеспечивает механизмы для уведомления домена source routing об отказах с ранее организованными активными маршрутами. Иными словами, компонента SDR выполняет маршрутизацию, которая адаптируется к изменениям топологии; однако такая адаптивность достигается, как следствие механизмов организации маршрутов и управления ими. Это отличается от поведения компоненты NR, где изменения состояния распространяются и принимаются узлами по мере возможности. Следовательно, для ускорения адаптации к изменениям в рабочем состоянии элементов маршрутизации, компонента SDR позволяет исходному домену переключаться на маршрут, рассчитанный компонентой NR, если обнаружен отказ на запрошенном отправителем маршруте (на фазе организации маршрута или после его установки) и правила разрешают использовать маршрут NR.

Для решения задач масштабирования компонента NR будет группировать модемы в конфедерации [IDRP91]. Напротив, SDR будет разрешать использование маршрутов уровня AD46 отдельными доменами, не разрешая использовать такой маршрут всей конфедерации, к которой домен относится. Подобно этому, один транзитный домен может поддерживать правило или специальное значение TOS, которые не поддерживаются другими доменами в их конфедерации(ях). Иными словами, архитектура использует SDR для поддержки неиерархических, неагрегируемых правил тогда и там, когда и где они требуются. Следовательно, компонента SDR сама по себе не обеспечивает свойств масштабирования, присущих NR. В компенсацию SDR не требует полного, глобального плана доменов если отдельные фрагменты сети никогда не пересекаются пакетами и не передаются туда. В результате утраты структуры маршрутизации SDR не гарантирует, что принимающие участие в маршрутизации домены всегда будут иметь информацию, требуемую для расчета пути к адресату. Кроме того, если домен имеет всю требуемую информацию, ее объем может оказаться слишком велик для своевременного сохранения и/или расчета маршрута. Однако, несмотря на отсутствие гарантий, целью архитектуры является обеспечение эффективных методов, с помощью которых отправитель может получить информацию, требуемую для расчета нужных маршрутов47.

Существенным для SDR является допущение о том, что маршруты, организованные по запросу, будут использоваться бережливо. Архитектура предполагает, что в любой заданный момент времени набор из всех установленных по запросам маршрутов в глобальной сети, образует малую часть маршрутов по запросу, которые могут быть потенциально организованы всеми доменами. Архитектура предполагает, что число маршрутов, установленных в BR48 компонентой SDR, должно иметь значение порядка log N (где N — общее число доменов маршрутизации в Internet), чтобы параметры масштабирования компоненты SDR были сравнимы с параметрами масштабирования NR. Компонента NR обеспечивает масштабируемость за счет иерархии.

Отметим, что приведенное выше требование не означает, что лишь малое число доменов может принимать участие в SDR или что маршруты, организованные компонентой SDR должны иметь малое время жизни. Все, что следует из этого требования — это то, что произведение числа маршрутов, задаваемых доменами, которые участвуют в SDR, на среднее время жизни маршрута SDR является ограниченным. Например, архитектура позволяет существовать небольшому числу маршрутов SDR со сравнительно долгим временем жизни или множеству короткоживущих маршрутов. Однако архитектура явно запрещает установку множества маршрутов SDR с относительно большим временем жизни. Число маршрутов SDR является функцией от числа доменов, использующих маршруты SDR, и числа маршрутов, используемых в расчете на один домен-отправитель.

В заключение отметим, что SDR хорошо подходит для трафика, который (1) используется недостаточно широко (или слабо предсказуем, или не имеет устоявшегося характера) для использования компоненты NR и (2) имеет продолжительность, существенно превышающую время на организацию маршрута.

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

4.1 Сравнение алгоритмов Path Vector и Link State для SDR

При задаваемой отправителем маршрутизации для расчета маршрутов можно использовать как методы, основанные на состоянии каналов, так и методы, основанные на векторах удаленности. Целесообразно использовать метод вектора удаленности или состояния канала при расчете пути с задаваемой отправителем маршрутизацией (source routing). Например, протокол типа BGP, в котором отправитель использует полную информацию AD о пути, полученную в маршрутных обновлениях, для создания source route. Такой протокол позволяет преодолеть некоторые недостатки, связанные с поэтапной работой алгоритмов на основе векторов удаленности. Однако мы не будем более обсуждать такие протоколы, поскольку можно добиться больших результатов при использовании задаваемой отправителем маршрутизации без применения алгоритмов на основе состояния канала. Возможности задаваемой отправителем маршрутизации в контексте внутридоменной (AD) маршрутизации на базе правил дают отправителю контроль над всем маршрутом. Эта задача не может быть решена полностью, когда промежуточные узлы контролируют анонсирование маршрутов соседям и, следовательно, отправителю.

Иными словами, промежуточные узлы должны быть способны предотвратить использование маршрута путем задания правил транзита, но если маршрут не заблокирован (т. е., является корректным для всех AD на маршруте), маршрут следует сделать доступным для отправителя независимо от предпочтений промежуточных доменов для их собственных потоков трафика.

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

4.2 Распространение маршрутной информации

За счет использования поэтапной маршрутизации компоненты NR, основанной на алгоритме PV в дополнение к задаваемой отправителем маршрутизации компоненты SDR мы уменьшаем сложности, связанные с агрегированием информации о пересылке SDR — большой процент междоменного трафика, передаваемого в каждый момент любым граничным маршрутизатором, будет пересылаться с использованием агрегированной информации о пересылке компоненты NR. Однако использование NR не решает другой важной проблемы масштабирования, связанной с SDR, — распределения, хранения и расчета с использованием полного топологического плана на уровне домена. В этом параграфе описаны перспективные предложения по расширению возможностей масштабирования при распределении, хранении и расчете маршрутной информации SDR.

Отметим, что для решения этой проблемы мы не предлагаем такой же путь, который используется для NR. A priori здесь не применима, поскольку разные домены могут требовать различных методов абстрагирования маршрутной информации. Например, если агрегируется маршрутная информация доменов, в которых не используются одинаковые правила и характеристики TOS (т. е., службы), тогда за пределами агрегата будут анонсироваться только те службы, которые анонсируются всеми доменами агрегата. Для размещения специальных маршрутов SDR использует агрегаты только тогда, когда домены-компоненты (и агрегат в целом) анонсируют требуемые параметры TOS и правила. Когда требуемые параметры TOS или правила не обеспечиваются агрегатом, используется полная информация о доменах-компонентах для создания маршрута через те домены, которые поддерживают требуемые характеристики. Следовательно, требуется иной, более гибкий, способ снижения объема хранимой и распространяемой информации. Таким образом решается два вопроса — распространение заданной конфигурацией топологической информации и правил, а также распространение динамической информации о состоянии.

4.2.1 Конфигурационные параметры

Информация о существовании междоменных каналов и поддерживаемых доменами правилах изменяется достаточно медленно. Такого типа информация относится к конфигурационным параметрам. В текущей спецификации IDPR полная, глобальная конфигурационная информация хранится сервером маршрутов каждого домена. Серверы маршрутов (RS49) представляют собой объекты, которые рассчитывают маршруты, задаваемые отправителем. При старте RS может загружать базу данных о соединениях с соседнего RS, по мере изменения доменов, междоменных соединений или правил осуществляется лавинная рассылка данных об изменениях маршрутным серверам в каждом домене.

Мы еще не задали точный механизм распределения конфигурационных параметров связности для SDR. Однако, в отличие от текущей спецификации IDPR, компонента SDR не будет использовать глобальную лавинную рассылку всех конфигурационных параметров. Исследуется несколько методов организации и распространения такой информации.

Конфигурационные параметры могут регулярно распространяться за пределами основного канала (например, на компакт-дисках). Можно также передавать эту информацию в несколько заранее согласованных мест, например, на серверы FTP. В промежутках между такими «серьезными» обновлениями агрегированные наборы обновлений могут глобально рассылаться в лавинном режиме. Более того, может использоваться ограниченная лавинная рассылка (например, на заданное число интервалов) в зависимости от важности внесенных изменений — информация об изменении правил для основной магистрали может рассылаться глобально, информация о новом межрегиональном канале может рассылаться только в связанных с этим каналом регионах, а информация о новом канале в домене, не являющемся транзитным, станет доступной только после очередного регулярного «серьезного» обновления.

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

Даже если в начальной реализации используется простая глобальная лавинная рассылка, мы должны изучить проблему структурирования информации о связности, чтобы эти данные можно было отыскивать и распределять более селективно с сохранением для отправителей возможности нахождения желаемых маршрутов. Например, можно рассмотреть RS, запрашивающие один у другого отфильтрованную информацию. Как в таких случаях RS следует определять фильтры, чтобы получить информацию, достаточную для нахождения специального маршрута при эффективном ограничении объема передаваемой информации? Другой вопрос связан с эффективным предвидением и описанием информации, которая может потребоваться для расчета маршрута.

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

Одним из перспективных предложений является организация информации с использованием фрагментов маршрутов50 (частичных путей). Хотя число маршрутных фрагментов растет быстрее, чем число доменов (по крайней мере, как O(N^2)), мы можем выбрать те фрагменты, которые будут полезны при расчете маршрутов. В частности, для каждого тупикового домена фрагменты будут содержать пути к нескольким хорошо известным магистралям51. К преимуществам этого способа относится агрегирование доменной информации в манере, полезной для расчета маршрутов, задаваемых отправителем, и индексирование по адресатам, которое обеспечивает ссылки на информацию и нахождение данных, требуемых для расчета конкретного маршрута. В настоящий момент пока не очевидно, как фрагменты маршрутов будут влиять на способность SDR обнаруживать неиерархические маршруты.

4.2.2 Динамические данные о состоянии

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

В текущей версии IDPR динамическая информация о состоянии рассылается глобально в лавинном режиме в дополнение к конфигурационной информации. Мы предлагаем распространять информацию о состоянии в жесткой зависимости от местоположения. Во-первых, динамическая информация будет анонсироваться в малой окрестности (незначительное число интервалов). Этот простой механизм с малыми издержками использует механизм топологической локализации. В дополнение к лавинной рассылке обновлений состояния в ближайшей окрестности мы также хотим обеспечить более точную маршрутную информацию для более протяженной окрестности (дальше нескольких интервалов). RPU52 представляет собой механизм передачи динамической информации о состоянии узлам, находящимися за пределами окрестности радиусом k интервалов (hop), используемого для обновлений, но этот механизм никогда не будет обеспечивать лучшего сервиса (меньшего числа установок некорректных маршрутов) чем получение доступа к динамической информации о состоянии [Estrinetal91].

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

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

4.3 Управление SDR

SDR можно построить поверх сетевого уровня, поддерживаемого компонентой NR, или параллельно этому уровню. Пересылка SDR будет поддерживаться двумя методами — loose source-routing53 и route setup54.

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

Второй метод основан на механизмах, предложенных для IDPR и описанных в [IDPR90]. Этот метод хорошо подходит для сеансов, продолжительность которых значительно превышает время кругового обхода. Протокол организации маршрута определяет форматы пакетов и обрабатывает пакеты организации маршрута (т. е., пакеты setup). Когда источник генерирует пакет setup, первый граничный маршрутизатор вдоль заданного source route проверяет запрос на организацию маршрута и, если этот запрос приемлем, устанавливает маршрутную информацию, которая включает идентификатор пути, предыдущий и следующий маршрутизаторы и другую связанную с учетом информацию, которую требует конкретный домен. Пакет setup передается следующему BR в source route доменного уровня, где описанная процедура повторяется55. Когда установочный пакет достигает адресата, в обратном направлении отправляется подтверждение56, которое поэтапно проходит через маршрутизаторы и каждый BR на пути активизирует свою маршрутную информацию. Последующие пакеты данных, проходящие по тому же пути к адресату, будут включать в себя идентификатор пути. Этот идентификатор используется для нахождения соответствующей информации о следующем интервале для каждого пакета.

Граничные маршрутизаторы, которые поддерживают обе компоненты — NR и SDR, должны быть способны определить, какой механизм следует использовать. При наличии соответствующей информации в PDU сетевого уровня такой BR должен быть способен принять однозначное решение о пересылке данного PDU с использованием компоненты NR или SDR. Механизм определения компоненты зависит о того, реализован сетевой уровень компоненты SDR поверх сетевого уровня NR или параллельно ему. После того, как решение принято, пакеты, которые пересылаются с использованием маршрутов, организованных компонентой SDR, пересылаются в выходной порт, связанный со значением Path ID в заголовке пакета. Пакеты, которые будут пересылаться с использованием маршрутов NR, пересылаются в выходной порт, связанный с соответствующим адресатом и значением ToS (если оно присутствует) в заголовках пакетов.

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

Если в процессе организации маршрута BR обнаруживает, что остальная часть (после BR) указанного маршрута от BR до адресата совпадает с маршрутом NR от BR до адресата, данный BR может отключить маршрут SDR в данной точке и отобразить его на маршрут NR. Чтобы это произошло, спецификация маршрута SDR должна полностью соответствовать маршруту NR. В дополнение к этому весь маршрут пересылки (т. е., оставшиеся до адресата интервалы) должен совпадать.

Более того, если маршрут NR изменяется на протяжении активного маршрута SDR и новый маршрут NR не совпдает с маршрутом SDR, тогда для оставшейся части пути к адресату должен быть организован маршрут SDR. Следовательно, при отображении маршрута SDR на маршрут NR исходный пакет setup должен быть сохранен. Пакеты на пути от отправителя к получателю могут, следовательно, проходить сегменты маршрутов SDR и NR, однако пакет не будет проходить других сегментов SDR после его прохождения через сегмент NR. Тем не менее, в течение переходного периода пакеты могут идти по некорректным маршрутам и, следовательно, эта функция должна быть опциональной и управляемой.

Отправитель может также запросить уведомление, если через некоторое время после неудачной организации маршрута неработоспособный канал или узел возвращается в работоспособное состояние. Если BR на маршруте обнаруживает, что на следующем интервале BR недоступен, обнаруживший проблему BR может добавить отправителя в список уведомлений и когда следующий BR снова станет доступным, отправителю может быть передано уведомление. Этот механизм обеспечивает возможность получения информации о прекращении неполадок. Например, домен может принять решение о маршрутизации через резервный путь при отказе на основном маршруте — упомянутый выше механизм будет своевременно информировать отправителя о восстановлении предпочтительного маршрута.

Третья опция обеспечивает адаптацию после организации маршрута. Если BR в процессе пересылки пакетов по активному маршруту SDR обнаруживает отказ на маршруте SDR, он может перенаправить трафик к адресату в существующий маршрут NR. Такая адаптация допустима лишь в том случае, когда используемый маршрут NR не противоречит правилам (например, на маршруте могут быть неприемлемые условия обслуживания — ToS). Адаптация происходит лишь в тех случаях, когда отправитель выбрал соответствующую опцию при организации маршрута. Отправитель также задает для себя режим уведомления о случаях описанной выше смены маршрута.

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

В заключение отметим, что при организации маршрута отправитель имеет несколько опций, представляемых в виде флагов в пакете setup:

  1. Если доступен маршрут NR, удовлетворяющий всем локальным правилам и TOS, использовать этот маршрут.
  2. Флаг согласия отправителя на использование принятого по умолчанию маршрута NR при отказе в процессе организации маршрута SDR.
  3. Запрос уведомлений об отображении в маршрут NR.
  4. Запрос дополнительной конфигурационной информации при отказе.
  5. Запрос на включение в список рассылки уведомлений о доступности ресурсов.
  6. Разрешение на перемаршрутизацию пакетов в NR при отказе после организации маршрута (в течение времени, пока не будут нарушаться правила).
  7. Запрос уведомления при перемаршрутизации пакетов данных.
  8. Запрос дополнительной конфигурационной информации при отказе, когда маршрут активен.
  9. Запрос на добавление в список рассылки уведомлений при отказе на активном маршруте.

5.0 Унифицированная архитектура

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

  1. База маршрутной информации: Возможно удастся использовать одну RIB для NR и SDR. Маршруты NR могут представляться как прямые графы, помеченные флагами (на узлах или каналах), соответствующими базовым ограничениям на транзит. SDR требует, чтобы к этому графу были добавлены каналы с отличными от базовых правилами, которые были найдены и организованы для специальных маршрутов. Кроме того, могут добавляться специальные флаги правил к каналам, уже организованным компонентой NR.
  2. Распространение информации: Векторы пути NR могут включать адреса репозиториев обновлений SDR для каждого AD (или конфедерации), чтобы помочь компоненте SDR в получении требуемой информации по запросу. Для доменов с минимальными правилами, где пространство для хранения информации меньше, чем пространство, требуемое для хранения адресов репозиториев (например, если правила для домена выражены простым шаблоном), векторы пути NR могут включать соответствующий флаг.
  3. Пересылка пакетов: Следует рассмотреть вопрос замены текущего заголовка сетевого уровня в стиле IDPR (который содержит глобальный идентификатор пути, используемый при пересылке пакетов данных следующему шлюзу правил на маршруте IDPR) стандартным заголовков (например, IP или CLNP), дополненным некоторыми опциональными полями. Это позволит унифицировать разбор заголовков пакетов и функции пересылки для SDR и NR, а также (возможно) снизить издержки на инкапсуляцию.
  4. Информация о доступности: В настоящее время IDRP распространяет информацию о доступности сетей в обновлениях, тогда как IDPR распространяет только информацию о доступности доменов. IDPR использует службу доменных имен для отображения номеров сетей на номера доменов, требуемые для принятия решения о маршрутизации. Следует рассмотреть вопрос о получении информации о доступности сетей и доменах в одинаковой манере.

5.1 Применимость для различных протоколов сетевого уровня

Предложенная здесь архитектура разработана для аккомодации таких протоколов сетевого уровня, как IP [Postel81], CLNP [ISO-473-88] и ST-II [ST2-90]. Кроме того, эта архитектура предназначается для поддержки будущих механизмов сетевого уровня, например, предложений Clark и Jacobson или интегрированного сервиса IP, предложенного Braden и Casner. Однако мы не можем дать никаких гарантий относительно самих механизмов. В любом случае не все упомянутые протоколы будут способны использовать возможности, обеспечиваемые архитектурой. Например, пока нет соответствия между растущим числом предлагаемых сетевых служб и способностью конкретного протокола сетевого уровня однозначно выражать запросы таких служб, способность архитектуры поддерживать маршрутизацию при наличии множества разнотипных служб остается по большей части академической. Т. е., не все компоненты архитектуры будут одинаково важны для разных протоколов сетевого уровня. С другой стороны, эта архитектура разработана для работы в глобальной сетевой среде будущего. Ведущиеся в настоящее время исследования позволят реализовать и оценить сетевые механизмы для разных типов сервиса, которые могут использоваться в сетях будущего, предлагающих такой сервис.

Одной из фундаментальных проблем предложенной архитектуры является решение вопроса о поддержке одного или множества протоколов. Архитектура не содержит каких-либо предположений о протоколах сетевого уровня для поддержки протокола междоменной маршрутизации в каждом домене или едином протоколе междоменной маршрутизации, который будет работать с множеством протоколов сетевого уровня57. Т. е., предлагаемая архитектура может быть реализована на основе одного протокола междоменной маршрутизации, поддерживающего множество протоколов сетевого уровня или на основе множества протоколов междоменной маршрутизации (с одинаковой архитектурой), предназначенных для конкретных протоколов сетевого уровня58.

5.2 Переходный период

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

В то же время, архитектура не требует полномасштабного развертывания в существующей сети Internet. Компонента NR может развертываться постепенно. Например, NR для протокола IP можно развернуть путем замены существующей маршрутизации EGP-2 маршрутизацией на основе BGP. После установки компоненты NR она может быть дополнена элементами, обеспечиваемыми компонентой SDR.

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

6.0 Заключение и перспективы продолжения работы

Предложенная здесь архитектура объединяет протоколы поэтапной маршрутизации на основе векторов пути (hop-by-hop path-vector) и задаваемой отправителем маршрутизации по состоянию каналов (source-routed link-state), используя каждый из этих протоколов в тех случаях, когда протокол подходит лучше всего. Компонента NR использует алгоритм PV и многоуровневые гибкие конфедерации доменов для поддержки эффективной маршрутизации базовых пакетов с использованием обычных маршрутов. Компонента SDR использует алгоритм LS и рассчитывает маршруты на основе базы данных о конфигурационных и динамических параметрах для передачи специфического трафика через специальные маршруты. В прошлом эти два подхода к маршрутизации рассматривались как взаимоисключающие, хотя они могут хорошо дополнять друг друга. В настоящее время оба подхода к маршрутизации уже используются в параллель. Два механизма маршрутизации при их совместном использовании обеспечивают гибкую и эффективную поддержку маршрутизации с использованием TOS и правил в масштабах глобальной сети Internet.

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

7.0 Благодарности

Авторы выражают благодарность Hans-Werner Braun (San Diego Supercomputer Center), Lee Breslau (USC), Scott Brim (Cornell University), Tony Li (cisco Systems), Doug Montgomery (NIST), Tassos Nakassis (NIST), Martha Steenstrup (BBN) и Daniel Zappala (USC) за их комментарии к предварительным вариантам документа.

8.0 Литература

[ANSI 87-150R] «Intermediate System to Intermediate System Intra-Domain Routing Exchange Protocol», ANSI X3S3.3/87-150R.

[BGP 91] Lougheed, K., and Y. Rekhter, «A Border Gateway Protocol 3 (BGP-3)», RFC 1267, cisco Systems, T.J. Watson Research Center, IBM Corp., October 1991.

[Breslau-Estrin 91] Breslau, L., and D. Estrin, «Design and Evaluation of Inter-Domain Policy Routing Protocols», To appear in Journal of Internetworking Research and Experience, 1991. (Earlier version appeared in ACM Sigcomm 1990.)

[Clark 90] Clark, D., «Policy Routing in Internetworks», Journal of Internetworking Research and Experience, Vol. 1, pp. 35-52, 1990.

[Dijkstra 59] Dijkstra, E., «A Note on Two Problems in Connection with Graphs», Numer. Math., Vol. 1, 1959, pp. 269-271.

[ECMA89] «Inter-Domain Intermediate Systems Routing», Draft Technical Report ECMA TR/ISR, ECMA/TC32-TG 10/89/56, May 1989.

[EGP] Rosen, E., «Exterior Gateway Protocol (EGP)», RFC 827, BBN, October 1982.

[Estrin 89] Estrin, D., «Policy Requirements for Inter Administrative Domain Routing», RFC 1125, USC Computer Science Department, November 1989.

[Estrin-etal91] Estrin, D., Breslau, L., and L. Zhang, «Protocol Mechanisms for Adaptive Routing in Global Multimedia Internets», University of Southern California, Computer Science Department Technical Report, CS-SYS-91-04, November 1991.

[Hedrick 88] Hedrick, C., «Routing Information Protocol», RFC 1058, Rutgers University, June 1988.

[Honig 90] Honig, J., Katz, D., Mathis, M., Rekhter, Y., and J. Yu, «Application of the Border Gateway Protocol in the Internet», RFC 116460, Cornell Univ. Theory Center, Merit/NSFNET, Pittsburgh Supercomputing Center, T.J. Watson Research Center, IBM Corp., June 1990.

[IDPR90] Steenstrup, M., «Inter-Domain Policy Routing Protocol Specification and Usage: Version 1», Work in Progress61, February 1991.

[IDRP91] «Intermediate System to Intermediate System Inter-domain Routeing Exchange Protocol», ISO/IEC/JTC1/SC6 CD10747.

[ISIS10589] «Information Processing Systems — Telecommunications and Information Exchange between Systems — Intermediate System to Intermediate System Intra-Domain Routing Exchange Protocol for use in Conjunction with the protocol for providing the Connectionless-mode Network Service (ISO 8473)», ISO/IEC 10589.

[ISO-473 88] «Protocol for providing the connectionless-mode network service», ISO 8473, 1988.

[Jaffee 82] Jaffee, J., and F. Moss, «A Responsive Distributed Routing Algorithm for Computer Networks», IEEE Transactions on Communications, July 1982.

[Little 89] Little, M., «Goals and Functional Requirements for Inter-Autonomous System Routing», RFC 1126, SAIC, October 1989.

[Oran 89] Oran, D., «Expert’s Paper: The Relationship between Addressing and Routeing», ISO/JTC1/SC6/WG2, 1989.

[OSPF] Moy, J., «The Open Shortest Path First (OSPF) Specification», RFC 1131, Proteon, October 1989.

[Postel 81] Postel, J., «Internet Protocol», RFC 79162, DARPA, September 1981.

[Rekhter 91] Rekhter, Y., «IDRP protocol analysis: storage complexity», IBM Research Report RC17298(#76515), October 1991.

[Shin87] Shin, K., and M. Chen, «Performance Analysis of Distributed Routing Strategies Free of Ping-Pong-Type Looping», IEEE Transactions on Computers, February 1987.

[ST2-90] Topolcic, C., «Experimental Internet Stream Protocol, version 2 (ST II)», RFC 119063, CIP Working Group, October 1990.

[Zaumen 91] Zaumen, W., and J. Garcia-Luna-Aceves, «Dynamics of Link State and Loop-free Distance-Vector Routing Algorithms», ACM Sigcomm ’91, Zurich, Switzerland, September 1991.

[Zhang 91] Zhang, L., «Virtual Clock: A New Traffic Control Algorithm for Packet Switching Networks».

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

Вопросы безопасности в этом документе не обсуждаются.

Адреса авторов

Deborah Estrin

University of Southern California

Computer Science Department, MC 0782

Los Angeles, California 90089-0782

Phone: (310) 740-4524

EMail: estrin@usc.edu

Yakov Rekhter

IBM T.J. Watson Research Center

P.O. Box 218

Yorktown Heights, New York 10598

Phone: (914) 945-3896

EMail: yakov@ibm.com

Steven Hotz

University of Southern California

Computer Science Department, MC 0782

Los Angeles, California 90089-0782

Phone: (310) 822-1511

EMail: hotz@usc.edu


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

Николай Малых

nmalykh@protocols.ru

1 Defense Advanced Research Projects Agency

2 В оригинале «global internet». Прим. перев.

3 В оригинале «switching facilities». Это понятие существенно шире, нежели термин «коммутатор» в современном понимании. Тем не менее, для краткости будет использоваться термин «коммутатор». Прим. перев.

4 intra-domain (interior).

5 inter-domain (exterior).

6 border router.

7 route server.

8 В настоящее время это является нормальной практикой и функции граничного маршрутизатора реализуются в одном устройстве с функциями маршрутного сервера. Прим. перев.

9hop-by-hop routing.

10 Border Gateway Protocol — протокол граничного шлюза.

11 Inter-Domain Routing Protocol — протокол междоменной маршрутизации.

12 Inter-Domain Policy Routing — междоменная маршрутизация на базе правил.

13 type of service — тип обслуживания.

14 extended link-state algorithm.

15 source-demand routing — маршрутизация по запросу отправителя. Такая модель используется в архитектуре междоменной маршрутизации на базе правил (IDPR).

16 node routing — маршрутизация в узлах (сети).

17 Для маршрутов, которые используются лишь спорадически (например, запросы на организацию таких маршрутов не являются постоянными или возникновение запросов трудно предсказуемо), зачастую целесообразно применять SDR.

18 Прежде, чем продолжить рассмотрение архитектуры, следует отметить, что поддержка сильно специализированных маршрутов для всех пар «отправитель — получатель» в глобальной сети или даже приближение к этому является неосуществимой задачей для любой архитектуры маршрутизации, которую можно предположить. Иными словами, мы не предполагаем, что какая-либо предсказуемая архитектура маршрутизации сможет поддерживать естественный рост требований пользователей и сетевых служб. Однако проблемы здесь не возникает. Возможности архитектуры могут превосходить потребности пользователей. Более того, некоторые требования, которые мы считаем невыполнимыми с точки зрения междоменной маршрутизации, могут быть полностью выполнены за пределами маршрутизации. Тем не менее, высказанные здесь предостережения избавляют от нереальных ожиданий.

19 Routing Information Base

20 Forwarding Information Base

21 Хотя мы не говорим об отсутствии иных путей обеспечить масштабирование, нам неизвестны какие-либо иные механизмы, обеспечивающие агрегирование/абстрагирование, за исключением кластеризации. Следовательно, в остальной части документа предполагается, что для агрегирования/абстрагирования используется кластеризация.

22 user class identification.

23 Как было отмечено выше, теоретически издержки могут расти по закону O(N^2), где N показывает число доменов в сети. Однако не очевидно, что это будет служить фактором, ограничивающим широкое использование SDR, при условии, что для обычных маршрутов доступна компонента NR.

24 Type of service — тип обслуживания (сервиса).

25 Адаптивный выбор маршрута предполагает адаптивность только в процессе выбора. После того, как маршрут выбран, он не подвергается каким-либо изменениям за исключением отзыва устаревших маршрутов.

26 В оригинале «routing facilities». Прим. перев.

27 Intermediate System — промежуточная система. Прим. перев.

28 В оригинале «convergence problem». Прим. перев.

29 Path Vector — вектор путей.

30 Мы предполагаем что для расчета путей по топологической базе при использовании алгоритмов LS будет применяться та или иная форма алгоритма SPF [Dijkstra59, OSPF].

31 Border Gateway Protocol — протокол граничного шлюза.

32 Inter Domain Routing Protocol — протокол междоменной маршрутизации.

33 В настоящее время протокол IDRP стандартизован, как ISO/IEC 10747:1994. Прим. перев.

34 Border Router -граничный маршрутизатор. Прим. перев.

35 Термин «path-vector protocol» имеет случайное сходство с термином «distance-vector protocol». В последнем случае BR получает от каждого из своих соседей вектор, содержащий «расстояния» по множества адресатов.

36 Link State — состояние канала. Прим. перев.

37 Distance Vector — вектор удаленности. Прим. перев.

38 Это краткое пояснение адресовано Ross Callon (Digital Equipment Corporation).

39 Хотя принятые в домене правила выбора маршрутов не распространяются в явном виде, они оказывают влияние на маршруты, доступные для других доменов. Маршрут, который может быть предпочтителен для отдельного домена и не запрещен правилами транзита, может оказаться недоступным в результате применения правил выбора некого промежуточного домена. Возможность расчета и организации маршрутов, которые могут быть утраченными при поэтапной маршрутизации (как LS, так и PV), является важной особенностью SDR.

40 При получении обновлений требуется выполнить некие дополнительные проверки для предотвращения петель.

41 Shortest Path First — сначала кратчайший путь. Прим. перев.

42 В оригинале «fully-expanded information». Прим. перев.

43 Состоящими из несмежных частей. Прим. перев.

44 Пересылка пакетов по маршрутам, создаваемым компонентой NR, может осуществляться с использованием маршрутизации, задаваемой отправителем (source routing) или поэтапной (hop-by-hop) маршрутизации. Второй вариант является более предпочтительным, поскольку он обеспечивает снижение числа состояний в маршрутизаторах (если используется организация маршрута) и позволяет избежать явного включения маршрута в пакеты сетевого уровня. Однако архитектура не запрещает маршрутизации, задаваемой отправителем (или организации маршрута) по маршрутам рассчитанным, но не организованным компонентой NR.

45 Если SDR использует информацию NR, рабочее состояние можно рассматривать как выбор некого маршрута.

46 Административный домен — Administrative domain. Прим. перев.

47 Основной целью правила или TOS-маршрутизации является расчет маршрута, который удовлетворяет набору заданных требований, и эти требования имеют преимущество по отношению к оптимизации маршрута. Иными словами, даже если домен, участвующий в SDR или NR, имеет достаточно информации для расчета маршрута, с учетом заданного набора требований архитектура не гарантирует оптимальности рассчитанного маршрута.

48 Граничный маршрутизатор — Border router. Прим. перев.

49 Route server — сервер маршрутов. Прим. перев.

50 Понятие маршрутных фрагментов изначально предложили Dave Clark и Noel Chiappa.

51 Фрагменты маршрута могут быть рассчитаны сервером маршрутов на стороне получателя и сделаны доступными через информационные запросы или путем глобальной информационной рассылки. В дополнение к этому маршруты, рассчитанные компонентой NR, также могут использоваться в качестве фрагментов маршрутов SDR.

52 Reverse path update — обновление обратного пути.

53 Нечеткая маршрутизация со стороны отправителя.

54 Организация маршрута.

55 Для снижения задержки начальный пакет (setup packet) может быть передан до завершения проверок.

56 accept message — сообщение о восприятии.

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

58 Если будет принято решение об использовании одного протокола, очевидно, что IDRP будет использоваться в качестве базового протокола для компоненты NR. Поскольку в настоящее время IDRP развивается в направлении CLNP, требуется дополнительная работа по добавлению поддержки протоколов IP и ST-II. При выборе поддержки множества протоколов очевидно, что протокол BGP будет использоваться в качестве базового для компоненты NR в сетях IP, а IDRP будет использоваться в качестве базового для компоненты NR в среде CLNP. Потребуется дальнейшая работа по поддержке компоненты NR для протокола ST-II. Может также потребоваться дополнительная работа по спецификации новых функций, которые могут быть добавлены в BGP.

59 local configuration information — локальная конфигурационная информация.

60Этот документ признан устаревшим и заменен RFC 1268. Прим. перев.

61Работа опубликована в RFC 1479. Прим. перев.

62Перевод этого документа на русский язык имеется на сайте www.protocols.ru. Прим. перев.

63Этот документ признан устаревшим и заменен RFC 1819. Прим. перев.