Авторы : Rodrigo Fonseca, Omprakash Gnawali, Kyle Jamieson, Sukun Kim, Philip Levis, and Alec Woo

Автор перевода : Тимков А.В.

Источник : http://www.tinyos.net/tinyos-2.x/doc/html/tep123.html

Протокол коллекций передает данные в один из возможно нескольких приемников данных, обеспечивая сетевой слой «много-к-одному». Коллекция – это фундаментальный компонент большинства приложений сенсорных сетей. Протокол дерева коллекций (CTP) связан с протосолом Collection в TinyOS 2.x. Пользователи используют интерфейсы Collection, описанные в TEP 119[3], для применения их в своих приложениях.

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

Все поля в этой спецификации располагаются в сетевом байтовом порядке.

CTP это древовидный протокол коллекций. Некоторое количество узлов в сети объявляют себя как корни дерева. Узлы формируют набор маршрутизируемых деревьев к этим корням. CTP – «безадресный» протокол по той причине, что узел не отправляет пакет конкретному корню; вместо этого, он неявно выбирает корень при выборе следующего хопа (один двухточечный отрезок пути передачи сообщения в сети). Узлы генерируют маршруты к корням, используя маршрутизируемый градиент.

Протокол CTP protocol подразумевает, что слой передачи данных обеспечивает 4 сущности:
     1) Обеспечивает эффективный локальный адрес для широкого вещания.
     2) Обеспечивает синхронизированные распознавания для отдельных пакетов.
     3) Обеспечивает поле распределения протокола для поддержки множественных протоколов высокого уровня.
     4) Имеет однохоповый 16-битный источник и поля назначения.

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

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

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

CTP использует ожидаемые передачи (ETX) в качестве своего маршрутизируемого градиента. Корень имеет значение ETX равное 0. ETX узла – это сумма ETX его родителя плюс ETX своих связей со своим родителем. Эта дополнительная единица измерения подразумевает, что узлы используют повторные передачи на канальном уровне. При выборе допустимых маршрутов, CTP ДОЛЖЕН выбирать узел с наименьшим значением ETX. CTP представляет ETX -величины как 16-битные десятичные реальные числа с фиксированной запятой с точностью до десятых. ETX величиной 45, например, представляется ETX = 4.5, тогда как ETX величиной 10 представляется как ETX = 1.

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

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

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

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

Формат кадра данных CTP:

    	    		1
	 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	|P|C| reserved  |      THL        |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	|              ETX                |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	|             origin              |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	|     seqno     |   collect_id    |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	|    data ...                     |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
							

Определения полей:
     * P: Запрос маршрута. Бит P позволяет узлам запрашивать маршрутную информацию у других узлов. Если узел, содержащий эффективный маршрут, которому адресован кадр данных, «услышал» пакет с установленным битом P, он ОБЯЗАН передать маршрутный пакет как можно быстрее. Любые другие узлы МОГУТ реагировать на бит P в кадре данных.
     * C: Уведомление о перегруженности. Если узел отбросил кадр данных CTP, то он ДОЛЖЕН выставить поле C на следующий кадр данных, который он передает.
     * THL: Время жизни. Когда узел генерирует кадр данных CTP, он ДОЛЖЕН установить THL в 0. Когда узел получает кадр данных CTP, он ДОЛЖЕН инкрементировать THL. Если узел получает THL, равный 255, он сбрасывает THL в 0.
     * ETX: Маршрутная метрика односкачкового отправителя. Когда узел передает кадр данных CTP, он ДОЛЖЕН поместить величину ETX своего маршрута через односкачковый узел назначения в поле ETX. Если узел получает пакет с отклонением меньшим, чем его собственное, то он ДОЛЖЕН запланировать передачу маршрутного кадра в ближайшем будущем.
     * origin: Исходящий адрес пакета. Узел, пересылающий кадр данных, НЕ ДОЛЖЕН модифицировать поле origin.
     * seqno: Исходный номер последовательности. Узел отправления устанавливает это поле, а узел, пересылающий кадр данных, НЕ ДОЛЖЕН модифицировать его.
     * collect_id: Идентификатор протокола высокого уровня. Исходный узел устанавливает это поле, а узел, пересылающий кадр данных, НЕ ДОЛЖЕН модифицировать его.
     * data: полезные данные 0 или более байт. Узел, пересылающий кадр данных НЕ ДОЛЖЕН модифицировать полезные данные. Длина поля данных подсчитывается вычитанием размера заголовка CTP из размера полезных данных канального уровня.

Вместе поля origin, seqno и collect_id обозначают уникальный «исходный пакет». Вместе поля origin, seqno, collect_id и THL обозначают уникальный «экземпляр пакета» внутри сети. Распознавание важно для подавления дублирования в имеющихся маршрутных петлях. Если узел подавляет исходные пакеты, то, если его попросят переслать этот же самый пакет еще раз вследствие зацикливания, то он будет отбрасывать пакет. Однако, если узел подавляет экземпляры пакетов, то он будет успешно их маршрутизировать в присутствующих кратковременных циклах до тех пор пока THL произведет круговой оборот перенаправляя экземпляр пакета.

Узел ДОЛЖЕН отсылать кадры данных CTP как однонаправленные сообщения включенным подтверждением на канальном уровне.

Формат маршрутного кадра CTP:

                        1
	 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	|P|C| reserved  |      parent     |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	|     parent    |       ETX       |
	+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	|      ETX      |
	+-+-+-+-+-+-+-+-+
							

Поля :
     * P: То же самое, что и в кадре данных, но с одним отличием: маршрутные кадры широковещательные, поэтому реагировать на бит P в маршрутных кадрах могут множество узлов.
     * C: Уведомление о перегруженности. Если узел отбросил кадр данных CTP, он ДОЛЖЕН установить поле C на следующий маршрутный кадр, который он передает.
     * parent: «Родитель» текущего узла.
     * metric: Величина маршрутной метрики текущего узла.

Когда узел «слышит» маршрутный кадр, он ДОЛЖЕН обновить свою таблицу маршрутов, чтобы отражать новую метрику адресов. Если величина ETX узла существенно изменяется, то CTP ОБЯЗАН в скором времени передать широковещательный кадр, после чего уведомить другие узлы, которые могут обновить свои маршруты. Поле parent действует как заместитель для однохопового поля андреса названичения пакета данных: «родитель» может распознавать, когда величина ETX «ребенка» существенно ниже, чем его собственная. Когда «родитель» «слышит», что «ребенок» оповещает о величине ETX ниже его собственной, он ДОЛЖЕН подготовить маршрутный кадр для передачи в ближайшем будущем.

Узел ДОЛЖЕН отправлять маршрутные пакеты CTP как широковещательные сообщения.

Реализация CTP может быть найдена в каталоге tos/lib/net/ctp TinyOS 2.0. Этот раздел описывает структуру реализации и не в коем случае не является частью спецификации CTP.

Эта реализация содержит 3 основных субкомпонента:

1) «Оценщик соединения», который ответственен за оценку односкачковой ETX при передаче информации между односкачковыми соседями.

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

3) «Механизм (движок) пересылки», который поддерживает очередь пакетов для отправки. Он решает, когда и нужно ли отсылать их. Название немного вводит в заблуждение: механизм пересылки отвечает за пересылаемый трафик, а также за трафик, генерируемый на узле.

Реализация использует два механизма для оценки качества соединения: периодические LEEP-пакеты (Link Estimation Exchange Protocol – протокол оценки и обмена информации о качестве соединения между соседями)[1]_ и пакеты данных. Реализация отсылает маршрутные маркеры как LEEP-пакеты. Эти пакеты распределяются в соседней таблице с двунаправленными величинами ETX. Реализация адаптирует скорость отправки маркеров на основе на сетевой динамики, используя алгоритм, похожий на протокол струйного рассеивания (trickle dissemination protocol) [2]_. Маркеры отсылаются по увеличивающемуся экспоненциально случайному таймеру. Реализация сбрасывает таймер в меньшее значение, когда выполняются одно или несколько следующих условий:

1) маршрутизации пуста (также устанавливается бит P)
      2) Маршрутная ETX узла увеличивается на 1 или более передач
      3) Узел получает пакет с установленным битом P

Реализация наращивает оценки качества передачами данных. Это непосредственная единица измерения ETX. Всякий раз, когда канал передачи данных передает пакет, он «рассказывает» оценщику соединения об узле назначения и об успешном подтверждении. Оценщик производит оценку ETX каждые 5 таких передач, где 0 успехов имеет ETX 6.

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

Компонентt tos/lib/net/4bitle/LinkEstimatorP реализует оценщика соединения. Он связывает оценки на основе LEEP-протокола и данных как описано в [4]_.

Реализуемый механизм маршрутизации отвечает за «вытаскивание» следущего хопа (скачка или узла) для передачи данных. Он отслеживает траекторию изменения величин ETX подмножества узлов, обслуживаемого таблицей оценок соединения. Маршрут с наименьшей стоимостью имеет наименьшую сумму всех ETX пути от этого узла и ETX соединения этого узла. Поэтому ETX пути – это сумма значений ETX соединений на протяжении всего маршрута. Компонент tos/lib/net/ctp/CtpRoutingEngineP реализует механизм маршрутизации.

Компонент tos/lib/net/ctp/CtpForwardingEngineP реализует механизм пересылки. Он состоит и пяти функций:

1) Передача пакетов к следующему хопу, повторная передача при необходимости и передача подтверждающей информации оценщику соединения
      2) Решает, «когда» передавать пакеты следующему хопу
      3) Выявление несоответствий в маршруте и информирование механизм маршрутизации
      4) Поддержка очереди пакетов для передачи, которые представляют собой смесь локально сгенерированных и пересылаемых пакетов
      5) Определение дублирования на односкачковой передаче, вызванного потерей подтверждений

Четыре ключевых функции механизма пересылки: получение пакета (``SubReceive.receive()``), пересылка пакета (``forward()``), передача пакета (``sendTask()``) и решение, что делать с пакетом после передачи (``SubSend.sendDone()``).

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

Функция пересылки форматирует пакет для пересылки. Она проверяет полученный пакет, чтобы заметить возможные петли (зацикливания) в сети. Она проверяет, есть ли свободное место в очереди передачи. Если свободного места нет, она отбрасывает пакет и выставляет бит C. Если очередь передачи пуста, он инициирует задачу отправки.

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

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