Epidemic Routing

Epidemic Routing (эпидемическая маршрутизация) — это протокол маршрутизации в сетях, не имеющих постоянной связности (так называемых сетях с задержками и разрывами, DTN — Delay-Tolerant Networks), основанный на принципе распространения данных, подобном распространению инфекции в эпидемии. В отличие от традиционных сетей (например, Интернета), где между отправителем и получателем существует непрерывный путь, в DTN узлы могут контактировать друг с другом лишь эпизодически. Epidemic Routing решает задачу доставки сообщения, копируя его на каждый встречный узел, который, в свою очередь, передаёт копию дальше, пока сообщение не достигнет цели.

Принцип работы

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

1. Обмен сводками (summary vectors): Каждый узел отправляет другому список идентификаторов сообщений, которые у него есть в буфере.
2. Запрос недостающих сообщений: Узел, получивший сводку, сравнивает её со своим буфером и запрашивает у собеседника те сообщения, которых у него нет (и которые он ещё не получал).
3. Передача копий: Узел-отправитель передаёт запрошенные сообщения. В результате после встречи оба узла имеют идентичный набор сообщений.

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

История и происхождение

Концепция Epidemic Routing была впервые предложена в 2000 году группой исследователей из Дартмутского колледжа (США) в работе Amin Vahdat и David Becker «Epidemic Routing for Partially-Connected Ad Hoc Networks». Исследователи стремились создать алгоритм маршрутизации для мобильных ad-hoc сетей (MANET), где узлы (например, смартфоны или датчики) перемещаются и связь между ними часто прерывается. Название «эпидемический» было выбрано из-за сходства процесса распространения данных с распространением биологических инфекций: каждый «заражённый» узел (имеющий копию сообщения) может «заразить» здорового узла (не имеющего копии).

Характеристики и особенности

Epidemic Routing обладает рядом ключевых свойств, отличающих его от других протоколов DTN:

• Высокая надёжность доставки: Если в сети существует хотя бы один путь (даже с разрывами) между отправителем и получателем, сообщение будет доставлено с вероятностью, близкой к 100%, при условии неограниченного времени жизни сообщения (TTL).
• Максимальная задержка: Время доставки может быть очень большим — от минут до дней, в зависимости от плотности сети и частоты контактов между узлами.
• Минимальное знание топологии: Узлам не нужно знать структуру сети или местоположение других узлов. Достаточно лишь возможности обмениваться данными при встрече.
• Чрезвычайно высокое потребление ресурсов: Это главный недостаток протокола. Каждое сообщение копируется на множество узлов, что приводит к:
• Перегрузке буферов: Узлы вынуждены хранить огромное количество копий.
• Избыточному трафику: Сеть заполняется дублирующимися пакетами.
• Расходу энергии: Постоянная передача и приём данных быстро разряжают батареи мобильных устройств.

Применение

Несмотря на ресурсоёмкость, Epidemic Routing и его модификации находят применение в сценариях, где надёжность доставки важнее скорости и затрат энергии:

• Сети сенсоров в труднодоступных местах: Например, сбор данных с датчиков, разбросанных в дикой природе (лесные пожары, мониторинг ледников), где связь возможна только при прохождении мимо мобильного сборщика (например, человека с планшетом или дрона).
• Коммуникация в условиях катастроф: После землетрясений или наводнений, когда базовая инфраструктура связи разрушена, а спасатели перемещаются пешком. Epidemic Routing позволяет передавать сообщения от одного спасателя к другому.
• Сети «умного города»: Передача данных от датчиков парковок или мусорных контейнеров на проезжающие мимо автомобили, которые затем доставляют данные на центральный сервер.
• Военные и тактические сети: В условиях, где централизованная связь невозможна или подавлена противником, а узлы (солдаты, транспорт) постоянно перемещаются.
• Космические сети (Interplanetary Internet): Связь между космическими аппаратами, где задержки могут составлять часы, а связность — редкой.

Модификации и альтернативы

Из-за высокой ресурсоёмкости оригинального протокола были разработаны его улучшенные версии и альтернативы:

• Spray and Wait: Узел-отправитель создаёт фиксированное число копий (L копий) и «распыляет» (spray) их на L встречных узлов. Каждый узел, получивший копию, переходит в режим «ожидания» (wait) и передаёт её только получателю. Это резко снижает число копий по сравнению с Epidemic Routing.
• PROPHET (Probabilistic Routing Protocol using History of Encounters and Transitivity): Узлы вычисляют вероятность встречи с каждым другим узлом на основе истории предыдущих контактов. Копия передаётся только тому узлу, у которого вероятность доставить сообщение получателю выше, чем у текущего владельца.
• MaxProp: Протокол, который ранжирует сообщения в буфере на основе вероятности их доставки и приоритета. Сообщения с более высоким приоритетом передаются первыми, а при переполнении буфера удаляются наименее перспективные.

Критика и ограничения

Основные критические замечания в адрес Epidemic Routing связаны с его непрактичностью для реальных крупномасштабных сетей:

• Масштабируемость: С ростом числа узлов и сообщений объём служебного трафика (обмен сводками) и хранимых данных растёт экспоненциально, что делает протокол непригодным для сетей с тысячами и миллионами узлов.
• Управление буфером: Алгоритмы удаления устаревших или уже доставленных сообщений (например, с использованием времени жизни или механизма подтверждений) сложны и сами по себе потребляют ресурсы.
• Безопасность: Протокол уязвим для атак типа «мусорный ящик» (garbage flood), когда злоумышленник распространяет ложные сообщения, заполняя буферы всех узлов и блокируя доставку легитимных данных.

Тем не менее, Epidemic Routing остаётся фундаментальной теоретической моделью, на основе которой разрабатываются более эффективные и практичные протоколы для сетей с задержками.

Источники

1. Vahdat, A., & Becker, D. (2000). Epidemic Routing for Partially-Connected Ad Hoc Networks. Technical Report CS-2000-06, Duke University.
2. Fall, K. (2003). A Delay-Tolerant Network Architecture for Challenged Internets. Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM '03).
3. Lindgren, A., Doria, A., & Schelén, O. (2003). Probabilistic routing in intermittently connected networks. ACM SIGMOBILE Mobile Computing and Communications Review, 7(3).
4. Spyropoulos, T., Psounis, K., & Raghavendra, C. S. (2005). Spray and Wait: An Efficient Routing Scheme for Intermittently Connected Mobile Networks. Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking (WDTN '05).
5. Burgess, J., Gallagher, B., Jensen, D., & Levine, B. N. (2006). MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks. Proceedings IEEE INFOCOM 2006.