Spray-and-Wait

Spray-and-Wait — это протокол маршрутизации в сетях с задержками и разрывами соединений (Delay-Tolerant Networking, DTN), основанный на стратегии ограниченного копирования сообщений. Относится к классу эпидемических (epidemic) алгоритмов, но в отличие от классической эпидемической маршрутизации, где сообщение копируется на каждый встреченный узел, Spray-and-Wait использует фиксированное количество копий (L), что позволяет снизить нагрузку на сеть и расход энергии при сохранении высокой вероятности доставки. Протокол был предложен в 2005 году исследователями Тэдди Спиропулосом, Ксенофонтом Псаунисом и Чандракхантом Рагавендрой из Калифорнийского университета в Лос-Анджелесе.

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

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

Spray-and-Wait впервые был описан в работе «Spray and Wait: An Efficient Routing Scheme for Intermittently Connected Mobile Networks» (2005). Протокол быстро привлёк внимание исследователей благодаря простоте реализации и хорошему балансу между вероятностью доставки и накладными расходами. В последующие годы появились многочисленные модификации, адаптирующие базовый алгоритм под различные сценарии: мобильные сенсорные сети, сети транспортных средств (VANET), подводные акустические сети и даже межпланетные коммуникации.

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

Spray-and-Wait состоит из двух фаз: фазы распыления (spray phase) и фазы ожидания (wait phase).

Фаза распыления

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

Фаза ожидания

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

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

Классификация и модификации

Spray-and-Wait может быть реализован в двух основных вариантах:

• Бинарный Spray-and-Wait (Binary Spray-and-Wait): в фазе распыления узел, имеющий n копий (n > 1), при встрече с узлом, не имеющим копии, передаёт ему floor(n/2) копий, а себе оставляет ceil(n/2). Это ускоряет распространение сообщения, так как копии распространяются быстрее (экспоненциально), но требует более сложной логики на узлах.
• Линейный Spray-and-Wait (Linear Spray-and-Wait): в фазе распыления узел передаёт по одной копии за встречу. Этот вариант проще в реализации, но медленнее распространяет копии.

Известны также гибридные схемы, где L динамически подстраивается под плотность сети или интенсивность трафика. Например, в протоколе Spray-and-Focus фаза ожидания заменяется на фазу фокусировки, где узел с одной копией может передать её другому узлу, если тот имеет более высокую «полезность» (например, большую вероятность встретить получателя).

Характеристики и производительность

Spray-and-Wait обеспечивает следующие свойства:

• Масштабируемость: количество копий фиксировано, что позволяет работать в сетях с большим числом узлов без перегрузки.
• Энергоэффективность: меньшее количество передач снижает расход энергии на мобильных устройствах (например, в сенсорных сетях с батарейным питанием).
• Устойчивость к разрывам: протокол не требует постоянного соединения между узлами, что характерно для DTN.
• Вероятность доставки: при оптимальном выборе L вероятность доставки близка к 1, если среднее время между встречами узлов меньше времени жизни сообщения.

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

Применение

Spray-and-Wait применяется в различных областях, где сети характеризуются частыми разрывами и ограниченными ресурсами:

• Мобильные сенсорные сети (MSN): для сбора данных с датчиков, установленных на животных, транспортных средствах или в труднодоступных местах.
• Сети транспортных средств (VANET): для передачи сообщений между автомобилями в условиях отсутствия инфраструктуры (например, в сельской местности или при авариях).
• Подводные акустические сети: из-за высокой задержки и низкой пропускной способности каналов под водой.
• Межпланетные коммуникации: для передачи данных между космическими аппаратами и Землёй, где задержки могут достигать минут и часов.
• Экстренные и военные коммуникации: в условиях разрушения инфраструктуры или в зонах боевых действий.

Сравнение с другими протоколами DTN

Spray-and-Wait занимает промежуточное положение между простыми, но неэффективными протоколами (например, Direct Delivery — прямая доставка только при встрече с получателем) и ресурсоёмкими, но надёжными (эпидемическая маршрутизация). По сравнению с протоколом PROPHET (Probabilistic Routing Protocol using History of Encounters and Transitivity), который использует вероятностные метрики, Spray-and-Wait не требует хранения истории встреч и менее чувствителен к изменениям топологии. Однако PROPHET может быть эффективнее в сетях с предсказуемыми паттернами мобильности.

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

Основные критические замечания в адрес Spray-and-Wait связаны с тем, что фиксированное количество копий не всегда оптимально: в плотных сетях оно может быть избыточным, а в разреженных — недостаточным. Кроме того, протокол не учитывает такие факторы, как пропускная способность каналов, задержки передачи и размер сообщений. В некоторых работах отмечается, что при больших объёмах данных Spray-and-Wait может приводить к перегрузке отдельных узлов, накапливающих много копий.

Интересные факты

• Название протокола отражает две фазы: «распыление» (spray) копий по сети, а затем «ожидание» (wait) встречи с получателем.
• Бинарная версия Spray-and-Wait была доказана как оптимальная с точки зрения минимизации задержки доставки при фиксированном числе копий в однородных мобильных сетях.
• Протокол реализован в нескольких симуляторах DTN, включая ONE (Opportunistic Network Environment) и ns-3.

Источники

• 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, 252–259.
• Spyropoulos, T., Psounis, K., & Raghavendra, C. S. (2007). Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility. IEEE Transactions on Mobile Computing, 6(7), 795–808.
• Fall, K., & Farrell, S. (2008). DTN: An Architectural Retrospective. IEEE Journal on Selected Areas in Communications, 26(5), 828–836.
• Keränen, A., Ott, J., & Kärkkäinen, T. (2009). The ONE Simulator for DTN Protocol Evaluation. Proceedings of the 2nd International Conference on Simulation Tools and Techniques, 55.