RFC 5148 Jitter Considerations in Mobile Ad Hoc Networks (MANETs)

Network Working Group                                         T. Clausen
Request for Comments: 5148              LIX, Ecole Polytechnique, France
Category: Informational                                      C. Dearlove
                                  BAE Systems Advanced Technology Centre
                                                              B. Adamson
                                          U.S. Naval Research Laboratory
                                                           February 2008

 

Временные вариации в сетях MANET

Jitter Considerations in Mobile Ad Hoc Networks (MANETs)

PDF

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

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

Аннотация

Этот документ содержит рекомендации по внесению вариаций (случайно меняющиеся задержки) при передаче управляющего трафика протоколов маршрутизации в сетях MANET¹ для снижения числа конфликтов при передаче.

1. Введение

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

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

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

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

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

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

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

Возможным решением проблемы является внесение варьируемой задержки (jitter) в процесс синхронизации. Такие задержки реализованы, например, в [2], [3] и [4], где интервалы передачи регулярных сообщений уменьшаются на небольшую, ограниченную случайную величину для рассинхронизации отправителей и, следовательно, устранения перегрузки среды и получателей. В данном документе рассматривается рекомендации по применению вариаций задержки для передачи управляющих сообщений в сетях MANET с целью предотвращения конфликтов, обусловленных перечисленными выше причинами.

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

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

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

Node – узел

Маршрутизатор MANET, реализующий протокол передачи сообщений.

MANET interface — интерфейс MANET

Сетевое устройство, участвующее в сети MANET. Узел может иметь один или множество интерфейсов MANET.

Message – сообщение

Объект, передающий протокольную информацию, предназначенную для обмена между узлами. Сообщения передаются через интерфейсы MANET, будучи вложенными в пакеты.

Packet – пакет

Объект, который может включать сообщения для передачи через интерфейс MANET на узле.

Transmission – передача

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

Generation – генерация

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

Forwarding – пересылка

Повторная передача полученного сообщения (измененного или неизменного) через один или множество интерфейсов MANET на узле.

Collision – конфликт

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

3. Заявление о применимости

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

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

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

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

Документ обобщает механизм временных вариаций (jitter mechanism), используемый проактивным протоколом маршрутизации MANET OLSR² [5].

4. Обзор протокола и его работы

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

5. Вариации

Для предотвращения одновременной передачи от узлов MANET при сохранении максимальной автономности этих узлов следует вносить случайную вариацию (jitter) при определении момента передачи пакета узлом. Следует реализовать три описанных здесь механизма задания вариаций с целью снижения вероятности одновременной передачи и предотвращения повторов, если одновременная передача все же произойдет.

Различаются три варианта:

• периодическая генерация сообщений;

• генерация сообщений по внешним событиям;

• пересылка сообщений.

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

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

Вопросы выбора значений MAXJITTER рассматриваются в параграфе 5.4.

5.1. Периодическая генерация сообщений

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

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

Значения вариаций задержки следует выбирать случайным образом из интервала от 0 до MAXJITTER с равномерным распределением.

Отметим, что узел будет знать свое значение MESSAGE_INTERVAL и может легко обеспечить для значения MAXJITTER выполнение условий, указанных в параграфе 5.4.

5.2. Генерация сообщений по внешним событиям

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

При инициировании сообщения (регулярного или не регулярного) протокол может задавать минимальный интервал между последовательными передачами однотипных сообщений, обозначаемый MESSAGE_MIN_INTERVAL. Если такой интервал не нужен, предполагается MESSAGE_MIN_INTERVAL = 0. Для отличных от нуля значений MESSAGE_MIN_INTERVAL допускается уменьшение этого интервала на случайное значение вариации (jitter). Т. е., после отправки сообщения следующее сообщение этого типа может быть передано по истечении времени (MESSAGE_MIN_INTERVAL – jitter). Значение jitter следует выбирать случайным образом из интервала от 0 до MAXJITTER с однородным распределением (используя значение MAXJITTER для регулярных сообщений).

Задание минимального интервала между сообщениями MESSAGE_MIN_INTERVAL может показаться бессмысленным, поскольку вариации позволяют уменьшать этот интервал. Для периодических сообщений установка значений (MESSAGE_INTERVAL – MAXJITTER) > MESSAGE_MIN_INTERVAL обеспечивает между последовательными сообщениями интервал по крайней мере MESSAGE_MIN_INTERVAL. В очень динамичных сетях с сообщениями по событиям внешние обстоятельства могут приводить к генерации сообщений с интервалом меньше MESSAGE_MIN_INTERVAL, эффективно делая значение MESSAGE_MIN_INTERVAL используемым «по умолчанию» интервалом между сообщениями (вместо MESSAGE_INTERVAL). Таким образом, для предотвращения синхронизации в очень динамичных сетях следует применять вариации и к MESSAGE_MIN_INTERVAL. Это также позволяет задавать MESSAGE_MIN_INTERVAL = MESSAGE_INTERVAL даже при использовании вариаций.

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

5.3. Пересылка сообщений

При пересылке сообщений узлам следует вносить вариации, добавляя случайные задержки. Значения задержек следует выбирать из интервала от 0 до MAXJITTER с однородным распределением.

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

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

Во многих случаях, включая OLSR [5] и протоколы, использующие полную функциональность [7], сообщения передаются поэтапно (hop-by-hop) с возможностью наличия нескольких сообщений в одном пакете и для некоторых или всех сообщений требуется пересылка. В целях эффективности, пересылать следует также один пакет и, следовательно, вариация для всех сообщений из одного пакета будет одинаковой (это также требует использования для всех сообщений одинаковых значений MAXJITTER). Для предполагаемого равномерного распределения нужно выбрать одно случайное значение вариации для всех сообщений. Вариант с заданием случайной вариации для каждого сообщения и последующим выбором минимальной вариации не подходит, поскольку такая процедура не обеспечивает равномерного распределения и уменьшает среднее значение вариации.

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

5.4. Определение максимальных вариаций

При рассмотрении вопроса о максимальных вариациях (один или множество экземпляров параметра MAXJITTER) принимаются во внимание приведенные ниже аспекты.

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

• Для периодических сообщений для каждого экземпляра MAXJITTER имеется ряд требований:

• отрицательные значения недопустимы;

• недопустимы значения, превышающие MESSAGE_INTERVAL/2;

• не следует выбирать значения, превышающие MESSAGE_INTERVAL/4.

• Если MESSAGE_MIN_INTERVAL > 0,

• значение MAXJITTER недопустимо устанавливать больше MESSAGE_MIN_INTERVAL;

• значение MAXJITTER не следует устанавливать больше MESSAGE_MIN_INTERVAL/2.

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

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

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

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

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

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

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

7.1. Нормативные документы

[1] Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels”, BCP 14, RFC 2119, March 1997.

7.2. Дополнительная литература

[2] Moy, J., “OSPF Database Overflow”, RFC 1765, March 1995.

[3] Marlow, D., “Host Group Extensions for CLNP Multicasting”, RFC 1768, March 1995.

[4] Rekhter, Y., Ed., Li, T., Ed., and S. Hares, Ed., “A Border Gateway Protocol 4 (BGP-4)”, RFC 4271, January 2006.

[5] Clausen, T., Ed., and P. Jacquet, Ed., “Optimized Link State Routing Protocol (OLSR)”, RFC 3626, October 2003.

[6] Perkins, C., Belding-Royer, E., and S. Das, “Ad hoc On-Demand Distance Vector (AODV) Routing”, RFC 3561, July 2003.

[7] Clausen, T., Dearlove, C., Dean, J., and C. Adjih, “Generalized MANET Packet/Message Format”, Work in Progress³.

Приложение A. Благодарности

Авторы благодарят рабочую группу MANET и команду OLSRv2 Design, особо отмечая Joe Macker и Justin Dean (оба из NRL), за их вклад в работу, а также дискуссии по разработке и проверке концепций, относящихся к данному документу, и Alan Cullen (BAE Systems) за критический обзор этой спецификации. В протоколе OLSRv1, как указано в [5], была введена концепция временных вариаций (jitter) для управляющего трафика, которая была протестирована Gitte Hansen и Lars Christensen (в тот момент оба работали в Aalborg University).

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

Thomas Heide Clausen

LIX, Ecole Polytechnique, France

Phone: +33 6 6058 9349

EMail: T.Clausen@computer.org

URI: http://www.ThomasClausen.org/

Christopher Dearlove

BAE Systems Advanced Technology Centre

Phone: +44 1245 242194

EMail: chris.dearlove@baesystems.com

URI: http://www.baesystems.com/

Brian Adamson

U.S. Naval Research Laboratory

Phone: +1 202 404 1194

EMail: adamson@itd.nrl.navy.mil

URI: http://www.nrl.navy.mil/

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

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

nmalykh@gmail.com

Полное заявление авторских прав

Copyright (C) The IETF Trust (2008).

К этому документу применимы права, лицензии и ограничения, указанные в BCP 78, и, за исключением указанного там, авторы сохраняют свои права.

Этот документ и содержащаяся в нем информация представлены “как есть” и автор, организация, которую он/она представляет или которая выступает спонсором (если таковой имеется), Internet Society и IETF отказываются от каких-либо гарантий (явных или подразумеваемых), включая (но не ограничиваясь) любые гарантии того, что использование представленной здесь информации не будет нарушать чьих-либо прав, и любые предполагаемые гарантии коммерческого использования или применимости для тех или иных задач.

Интеллектуальная собственность

IETF не принимает какой-либо позиции в отношении действительности или объема каких-либо прав интеллектуальной собственности (Intellectual Property Rights или IPR) или иных прав, которые, как может быть заявлено, относятся к реализации или использованию описанной в этом документе технологии, или степени, в которой любая лицензия, по которой права могут или не могут быть доступны, не заявляется также применение каких-либо усилий для определения таких прав. Сведения о процедурах IETF в отношении прав в документах RFC можно найти в BCP 78 и BCP 79.

Копии раскрытия IPR, предоставленные секретариату IETF, и любые гарантии доступности лицензий, а также результаты попыток получить общую лицензию или право на использование таких прав собственности разработчиками или пользователями этой спецификации, можно получить из сетевого репозитория IETF IPR по ссылке http://www.ietf.org/ipr.

IETF предлагает любой заинтересованной стороне обратить внимание на авторские права, патенты или использование патентов, а также иные права собственности, которые могут потребоваться для реализации этого стандарта. Информацию следует направлять в IETF по адресу ietf-ipr@ietf.org.

---

1Mobile Ad hoc NETwork.