CSMA с обнаружением коллизий

Настойчивые и ненастойчивые CSMA протоколы несомненно есть улучшение ALOHA, т.к. они начинают передачу только проверив состояние канала. Другим улучшением, которое можно сделать, - станции должны уметь определять коллизии как можно раньше, а не по окончании отправки кадра. Это экономит время и пропускную способность канала. Такой протокол, известный как CSMA/CD - Carrier Sense Multiply Access with Collision Detection, широко используется в локальных сетях.

Таким образом в работе протокола CSMA/CD можно выделить три периода: состязаний, передачи и ожидания, когда нет кадров для передачи.

26 Бесконфликтные протоколы. Протоколы с ограниченными конфликтами. Адаптивный древовидный протокол.

4.1.5 Бесконфликтные протоколы

Хотя в протоколе CSMA/CD коллизии могут возникать только в период состязаний, тем не менее при больших t и коротких кадрах они съедают часть пропускной способности канала. Здесь мы рассмотрим как можно избежать этих коллизий.

Мы будем предполагать, что у нас есть N станций с адресами от 0 до N-1. Все адреса уникальны. Основным является вопрос: как определить кто будет владеть каналом, когда закончиться текущая передача.

Идея этого метода показана на рис.4.6.Выделяется специальный период состязаний, где количество слотов равно числу станций. Каждая станция, имеющая кадр для передачи, проставляет 1 в свой слот. В результате, в конце состязаний все станции знают кто будет передавать и в каком порядке. Передача происходит в том же порядке, в каком пронумерованы слоты. Раз станции знают кто будет передавать и в каком порядке конфликтов не будет. Если станция опоздала с заявкой на передачу, то она должна ждать следующего периода состязаний, который начнется по окончании передач, заявленных на предыдущем периоде состязаний. Такие протоколы, когда заявки на передачу откладываются и могут быть сделаны лишь в определенные периоды времени называются протоколами с резервированием.

4.1.6 Протоколы с ограниченным числом конфликтов

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

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

На рис.4.9 показано как эта процедура применяется к станциями. Станции - листья. За слот 0 борются все станции. Если какая-то победила - хорошо. Если нет, то за слот 1 борются только станции поддерева с корнем в вершине 2. Если какая-то победила, то следующий слот резервируется для станций поддерева 3. Если был конфликт, то за следующий слот борются станции поддерева 4 и т.д.

Для того, чтобы по настоящему мобильным, компьютер должен использовать радио канал для связи. Локальны сети построенные на основе радо канала существенно отличаются от обычных локальных сетей. Они имеют специальный МАС подуровень.

Обычная конфигурация таких сетей - в здании размещается сеть стационарных приемопередающих станций, соединенных кабелем. Если настроить приемопередатчики станций и компьютеров на расстояние 3-4 метра, то каждая комната в здании образует ячейку. В каждой ячейке действует только один канал, пропускную способность которого разделяют все машины этой ячейки. Обычна она равна 1-2 Мбита/сек.

Естественно было бы попытаться использовать протокол CSMA для радио канала. Однако, в нашем случае возникают проблемы. Рассмотрим рис.4.11.Станции А и В могут взаимодействовать, станция С может взаимодействовать с B и D, но не с А. Рассмотрим, что будет происходить когда А будет передавать В (рис.4.11(а)). Поскольку С вне действия А, то она не слышит передачи А и может начать свою, что приведет к коллизии. Эта проблема станции, не способной увидеть конкурента называется проблемой спрятанной станции.

Рассмотрим теперь что будет если В начнет передачу, например, А. С услышит эту передачу и ложно заключит что она не может передавать станции D, хотя она свободна. Эта ситуация называется проблемой мнимой станции. MACA.
Первые протоколы, разработанные для беспроводных сетей относились к протоколам класса МАСА (Multiple Access Collision Avoidance). Идея заключалась в том, чтобы отправитель принудил получателя послать короткое сообщение перед началом передачи. Все станции, находящиеся в зоне действия получателя, услышат этот сигнал и не начнут передачи. Этот протокол иллюстрирует рис.4.12.

Рассмотрим как А передает сообщение В. А начинает с передачи специального сообщения RTS (Request To Send). Это короткое сообщение (30 байт) несет информацию (например, длину) о настоящем сообщении. В в ответ шлет CLS (Clear To Send) сообщение. В этом сообщении повторяются данные о сообщении, которое последует. По получении CTS А начинает передачу.

Теперь рассмотрим как другие станции реагируют на RTS и CTS сообщения. Станции близко расположенные к A слышат RTS и знают что надо хранить молчание достаточное время, чтобы передать сообщение. Станции близкие к В слышат CTS и тоже не будут инициировать передачу для В. Эти ситуации показаны на рис.4.12.

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