Contact Graph Routing¶

Contact Graph Routing (CGR) — это алгоритм маршрутизации, разработанный для сетей с задержками и разрывами соединений (DTN). В отличие от классических протоколов маршрутизации, предполагающих наличие непрерывного двустороннего канала связи, CGR оперирует понятием «контактов» — заранее известных или прогнозируемых временных интервалов, в течение которых два узла могут обмениваться данными. Алгоритм строит граф контактов, где вершинами являются узлы сети, а рёбрами — сами контакты с указанием времени начала, длительности, пропускной способности и задержки, после чего вычисляет оптимальный маршрут доставки сообщения с учётом временных ограничений.

¶История и предпосылки создания

Идея CGR возникла в рамках развития концепции «межпланетного интернета» (IPN, Interplanetary Internet), предложенной в конце 1990-х годов группой учёных под руководством Винта Серфа. Традиционные протоколы TCP/IP не работают в условиях космической связи: сигнал идёт от Земли до Марса от 4 до 24 минут, а планеты постоянно движутся, периодически скрываясь за Солнцем. Это приводит к разрывам соединений на часы и дни.

Первая реализация CGR была выполнена в Лаборатории реактивного движения НАСА (JPL) в рамках проекта DTN для космических миссий. Алгоритм впервые был описан в 2003 году в работе Скотта Берлиги, Винта Серфа и других исследователей. В 2008 году CGR был включён в экспериментальную версию протокола Bundle Protocol (BP), ставшего основой DTN.

В 2010-х годах CGR начал применяться не только в космосе, но и в наземных сетях с нестабильной связью — например, в системах связи с беспилотными летательными аппаратами (БПЛА) и подводными аппаратами, а также в сетях датчиков в труднодоступных регионах.

¶Основные понятия

¶Контакт

Контакт — это временной интервал, в течение которого два узла могут обмениваться данными. Каждый контакт характеризуется:

идентификаторами узлов-отправителя и получателя;
временем начала (start time);
длительностью (duration);
пропускной способностью (capacity) — максимальный объём данных, который можно передать за контакт;
задержкой распространения (propagation delay) — время, необходимое сигналу для преодоления расстояния между узлами.

¶Граф контактов

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

¶План контактов

План контактов (contact plan) — это таблица, содержащая полный набор контактов для всей сети на определённый период. План может быть составлен на основе расписания движения космических аппаратов, прогнозов погоды (для наземных радиоканалов) или данных о трафике.

¶Принцип работы алгоритма

CGR работает на уровне пакетов (bundles) протокола Bundle Protocol. Алгоритм выполняет следующие шаги:

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

¶Пример работы

Допустим, есть три узла: Земля (E), Марс (M) и орбитальный спутник (S). План контактов:

E → S: с 10:00 до 10:30, задержка 5 минут;
S → M: с 10:45 до 11:15, задержка 10 минут.

Пакет, отправленный с Земли в 10:00, сначала передаётся на спутник (контакт E→S), затем ждёт до 10:45 и передаётся на Марс (контакт S→M). CGR вычисляет, что доставка займёт 35 минут (5 минут задержки на первом участке + 10 минут ожидания + 10 минут задержки на втором участке).

¶Классификация и варианты

¶По способу построения графа

Статический CGR — используется фиксированный план контактов, известный заранее. Применяется в миссиях с предсказуемой динамикой (например, спутники на стабильных орбитах).
Динамический CGR — план контактов обновляется в реальном времени на основе измерений или прогнозов. Используется в наземных сетях с переменными условиями (например, связь с БПЛА в зоне урагана).

¶По критерию оптимизации

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

¶Реализации

ION (Interplanetary Overlay Network) — эталонная реализация DTN от НАСА, включающая CGR. Написана на C, используется в экспериментальных космических миссиях.
µD3TN — реализация DTN для встроенных систем, поддерживающая упрощённую версию CGR.
DTN2 — исследовательская реализация, включающая экспериментальные версии CGR.

¶Применение

¶Космическая связь

CGR является основным алгоритмом маршрутизации в проектах межпланетного интернета. Использовался в миссиях:

Mars Reconnaissance Orbiter (2005) — тестирование DTN с CGR для передачи данных с марсоходов.
ISS (Международная космическая станция) — с 2016 года CGR применяется для маршрутизации сообщений между модулями и наземными центрами.
Lunar Gateway (планируется) — будет использоваться для связи с лунной орбитальной станцией.

¶Наземные сети с задержками

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

¶Преимущества и ограничения

¶Преимущества

Работа в условиях разрывов — CGR не требует непрерывного соединения, что критично для космоса и удалённых регионов.
Предсказуемость — если план контактов известен, алгоритм гарантирует доставку в заданное время.
Масштабируемость — граф контактов может содержать тысячи узлов, и алгоритм работает за полиномиальное время.

¶Ограничения

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

¶Критика и альтернативы

Некоторые исследователи отмечают, что CGR плохо подходит для сетей с высокой динамикой (например, роя спутников на низких орбитах, где контакты меняются каждые несколько секунд). В таких случаях предпочтительнее алгоритмы, основанные на прогнозировании (например, Epidemic Routing или Spray-and-Wait). Кроме того, CGR требует централизованного составления плана контактов, что снижает устойчивость сети к сбоям.

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

¶Источники

Burleigh, S. et al. "Delay-Tolerant Networking: An Approach to Interplanetary Internet." IEEE Communications Magazine, 2003.
Cerf, V. et al. "Interplanetary Internet (IPN): Architectural Definition." IETF RFC 4838, 2007.
Fraire, J. A. et al. "Contact Graph Routing in Delay Tolerant Networks: A Survey." IEEE Communications Surveys & Tutorials, 2020.
NASA JPL. "Interplanetary Overlay Network (ION) Documentation." 2019.