Протокол антиколлизии

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

История возникновения

Проблема коллизий возникла с появлением первых компьютерных сетей с общей шиной, где несколько устройств разделяли одну физическую линию связи. В 1970-х годах в рамках разработки сети ALOHAnet на Гавайях был предложен первый протокол случайного доступа — ALOHA. Он позволял устройствам передавать данные в любой момент, а при возникновении коллизии — повторять передачу через случайный интервал времени. Недостатком была низкая пропускная способность (до 18 % от максимальной).

В 1973 году сотрудники Xerox PARC Роберт Меткалф и Дэвид Боггс разработали протокол CSMA/CD (Carrier Sense Multiple Access with Collision Detection), который стал основой для Ethernet. Этот протокол значительно повысил эффективность использования канала за счёт прослушивания среды перед передачей и обнаружения коллизий во время передачи. В 1980-х годах Ethernet с CSMA/CD стал доминирующей технологией локальных сетей.

С развитием беспроводных сетей (Wi-Fi) в 1990-х годах возникла необходимость в новых протоколах антиколлизии, так как в радиоканале невозможно одновременно слушать и передавать (коллизия обнаруживается только после получения подтверждения). Для этого был разработан протокол CSMA/CA (Collision Avoidance), использующий механизмы ожидания и случайных отсрочек (backoff).

Классификация протоколов антиколлизии

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

Детерминированные протоколы

Гарантируют, что каждое устройство получит доступ к каналу в строго определённый момент времени. Коллизии полностью исключены. Примеры:

• Token Ring — устройства передают данные по кольцу, а право на передачу даётся специальным маркером (токеном). Только устройство, владеющее токеном, может отправлять данные.
• Polling (опрос) — центральный контроллер последовательно опрашивает устройства, разрешая им передавать данные. Используется в системах промышленной автоматизации (Modbus, Profibus).
• TDMA (Time Division Multiple Access) — временное разделение канала: каждому устройству выделяется фиксированный временной слот. Применяется в спутниковой связи и некоторых стандартах сотовой связи (GSM).

Вероятностные (случайные) протоколы

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

• ALOHA (чистый и слотовый) — устройства передают данные в случайные моменты времени. В слотовом ALOHA время делится на временные слоты, что снижает вероятность коллизий.
• CSMA/CD — перед передачей устройство прослушивает канал (Carrier Sense). Если канал свободен — начинает передачу. Во время передачи устройство продолжает мониторинг сигнала; при обнаружении коллизии (по искажению сигнала) немедленно прекращает передачу и отправляет сигнал «затор» (jam signal), после чего все устройства ждут случайное время (backoff) перед повторной попыткой.
• CSMA/CA — устройство перед передачей прослушивает канал. Если канал занят — ждёт случайное время. Для снижения вероятности коллизий используется механизм RTS/CTS (Request to Send / Clear to Send): устройство отправляет короткий запрос на передачу, а точка доступа отвечает разрешением, после чего только это устройство может передавать данные в течение заданного времени.

Устройство и принцип работы (на примере CSMA/CD)

Протокол CSMA/CD, используемый в классическом Ethernet (стандарты IEEE 802.3 до 10BASE-T), работает по следующему алгоритму:

1. Прослушивание канала (Carrier Sense). Устройство проверяет, есть ли в среде передачи несущий сигнал от другого устройства. Если канал занят — устройство ожидает его освобождения.
2. Начало передачи. Если канал свободен в течение межкадрового интервала (9,6 мкс для 10 Мбит/с Ethernet), устройство начинает передачу данных.
3. Обнаружение коллизии (Collision Detection). Во время передачи устройство сравнивает уровень сигнала на выходе и на входе. Если они различаются (например, из-за одновременной передачи другого устройства), фиксируется коллизия.
4. Реакция на коллизию. Устройство немедленно прекращает передачу и отправляет короткий сигнал «затор» (32 бита), чтобы все остальные устройства узнали о коллизии.
5. Случайная отсрочка (Backoff). После коллизии каждое устройство выбирает случайное число (k) из диапазона от 0 до 2^n-1, где n — номер повторной попытки (до 10). Устройство ждёт k * 512 битовых интервалов (для 10 Мбит/с Ethernet — 51,2 мкс на интервал) и затем повторяет попытку. После 16 неудачных попыток передача отменяется.

Этот алгоритм гарантирует, что при увеличении загрузки сети время разрешения коллизий растёт, но сеть остаётся работоспособной до определённого порога (обычно до 40–50 % загрузки).

Применение

Протоколы антиколлизии используются в различных областях:

• Локальные сети (Ethernet) — CSMA/CD применялся в сетях на коаксиальном кабеле и витой паре до появления коммутируемых сетей. Современные Ethernet-сети (с коммутаторами) используют полнодуплексный режим, где коллизии исключены архитектурно.
• Беспроводные сети (Wi-Fi) — CSMA/CA с механизмом RTS/CTS является основой стандартов IEEE 802.11. Позволяет нескольким устройствам делить радиоканал без централизованного управления.
• Спутниковая связь — TDMA и ALOHA (слотовый) используются для доступа множества земных станций к одному спутниковому транспондеру.
• Промышленные сети — Profibus, Modbus RTU используют детерминированные протоколы (опрос) для гарантии времени доставки данных.
• RFID-системы — протоколы антиколлизии (например, на основе алгоритма «слотового ALOHA») позволяют считывателю одновременно идентифицировать несколько меток в поле действия.

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

• В классическом Ethernet максимальное расстояние между узлами сети ограничивалось 2500 метрами (с повторителями) из-за времени распространения сигнала: коллизия должна быть обнаружена до окончания передачи минимального кадра (64 байта).
• Протокол CSMA/CD был формально исключён из стандарта IEEE 802.3 в 2011 году, когда все современные Ethernet-сети перешли на полнодуплексный режим с коммутацией.
• В беспроводных сетях проблема «скрытого узла» (когда два устройства не слышат друг друга, но оба слышат точку доступа) решается именно механизмом RTS/CTS, который резервирует канал на время передачи.
• Алгоритм экспоненциальной отсрочки (exponential backoff) в CSMA/CD был вдохновлён методами разрешения коллизий в сетях ALOHA и впоследствии адаптирован для других протоколов, включая TCP (управление перегрузкой).

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

Вероятностные протоколы (CSMA/CD, CSMA/CA) имеют фундаментальные ограничения:

• Неэффективность при высокой загрузке — при загрузке канала более 50 % количество коллизий резко возрастает, снижая пропускную способность. В CSMA/CD при загрузке 80 % эффективность падает до 30 %.
• Неопределённое время доступа — невозможно гарантировать, что устройство передаст данные в заданный интервал времени, что неприемлемо для систем реального времени.
• Проблема «скрытого узла» в беспроводных сетях — CSMA/CA частично решает её через RTS/CTS, но это увеличивает накладные расходы.
• Зависимость от длины канала — в CSMA/CD минимальный размер кадра должен быть больше времени двойного оборота сигнала (round-trip time), чтобы коллизия была обнаружена всеми узлами.

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

Источники

• IEEE 802.3-2018 — Standard for Ethernet (раздел 4, CSMA/CD).
• IEEE 802.11-2020 — Standard for Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications.
• Tanenbaum A., Wetherall D. — Computer Networks, 5th Edition (2010).
• Stallings W. — Data and Computer Communications, 10th Edition (2013).
• Меткалф Р., Боггс Д. — Ethernet: Distributed Packet Switching for Local Computer Networks (1976).