15.4.2. Системы, которые обнаруживают несущую, и протоколы

Как мы видели, протоколы случайного доступа для систем типа АЛОХА (щелевых и бесщелевых) обеспечивает относительно низкую проходимость. Далее, щелевая система АЛОХА требует, чтобы пользователи передавали сигналы в синхронизированных щелях времени. В каналах, в которых задержки передачи относительно малы, возможно синтезировать протоколы случайного доступа, которые дадут более высокую проходимость. Пример такого протокола – протокол обнаружения несущей с детектированием столкновений, который используется как стандарт эфирного протокола в локальных сетях в свободном пространстве. Этот протокол известен как протокол обнаружения несущей при случайном доступе с декодированием столкновений (CSMA/CD – carrier sense multiple access with collusion detection).

Протокол (CSMA/CD) очень прост. Все пользователи прислушиваются к передачам по каналу. Пользователь, который желает передавать пакет, захватывает канал, когда он обнаруживает, что канал не занят. Столкновения могут возникнуть, когда два или больше пользователей обнаруживает, что канал не занят и начинает передачу. Когда пользователи, которые передают одновременно, обнаруживают столкновение, они посылают специальный сигнал, называемый сигналом столкновения (jam), который служит для указания всем пользователям о столкновении, и прекращают свои передачи. И обнаружение несущей, и прекращения передач, когда возникает столкновение, ведут к минимизации времени занятия канала и, следовательно, дают большую проходимость.

Для детальной разработки эффективности CSMA/CD рассмотрим локальную сеть в свободном пространстве, имеющую трассовую (bus) структуру, показанную на рис. 15.4.4.

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

Рис.15.4.4. Локальная сеть в свободном пространстве с трассовой архитектурой

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

Имеется несколько возможных протоколов, которые можно использовать для повторения передач при возникновении столкновений. Один протокол называется ненастойчивый (nonpersistent) CSMA, другой называется 1-настойчивый CSMA, а обобщение последнего называется p-настойчивый CSMA.

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

a) Если канал не занят, пользователь передает пакет,

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

1-настойчивый CSMA. Этот протокол проектируется для достижения высокой проходимости посредством того, что не позволяет каналу быть незанятым, если несколько пользователей имеют пакеты к передаче. Здесь пользователи отслеживают канал и работают согласно следующему правилу:

a) Если обнаружен незанятый канал, пользователь передает пакет с вероятностью 1;

b) Если канал обнаружен занятым, пользователь ждет, пока канал окажется незанятым и передает пакет с некоторой вероятностью.

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

р-настойчивый CSMA. Чтобы сократить скорость столкновений в 1-настойчивом CSMA и увеличить проходимость, мы можем рандомизировать время начала передачи пакетов. В частности, отследив незанятость канала, пользователь, имеющий пакет для передачи, посылает его с вероятностью  или задерживает его на время  с вероятностью . Вероятность  выбирается таким путем, чтобы сократить вероятность столкновений, в то время когда период незанятости между последовательными (неперекрывающимися) передачами сохраняется малым. Это выполняется путем деления оси времени на мини-щели длительностью  и выбора начала передачи пакета в начале мини-щели. В целом в -настойчивом протоколе пользователь, имеющий пакет для передачи, поступает следующим образом:

a)  Если канал обнаружен незанятым, пакет посылается с вероятностью  или с вероятностью  передача задерживается на  секунд.

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

c)   Если при  канал обнаружен занятым, пользователи ждут, пока он окажется незанятым и затем поступают согласно a) и b).

Можно также конструировать щелевые версии описанного выше протокола.

Анализ проходимости для протоколов ненастойчивой и -настойчивой CSMA/CD был выполнено Клейнроком и Тобаджи (1975), основываясь на следующих предположениях:

1.  Среднее время ретрансляции велико по сравнению с длительностью пакета .

2.  Интервалы пребывания точечного процесса, определённые временем старта всех пакетов плюс времени ретрансляций, независимы и распределены экспоненциально.

Для ненастойчивой CSMA проходимость равна

,                                  (15.4.11)

где параметр . Заметим, что когда , . Рис. 15.4.5 иллюстрирует зависимость прохождения от предоставляемого трафика G с параметром а. Видим, что , когда  для . Для  величина  уменьшается.

Рис. 15.4.5. Проходимость в ненастойчивой системе CSMA [Kleinrock и Tobagi (1975), @ IEEE]

Для 1-настойчивого протокола проходимость, полученная Клейнроком и Тобаджи (1975), равна

                     (15.4.12)

В этом случае

                                     (15.4.13)

что дает меньшую величину пика, чем при ненастойчивом протоколе.

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

Рис. 15.2.6. Проходимость канала в р-настойчивой системе CSMA: (а) ; (b) ; (с) ; [Kleinrock и Tobagi (1975), @ IEEE]

Время передачи было также рассчитано Клейнроком и Тобаджи (1975). Рис.15.4.7 иллюстрирует графики задержки (нормировании к ) в зависимости от проходимости  для протоколов щелевой ненастойчивой и -настойчивой CSMA.

Рис. 15.4.7. Проходимость в обмен на задержку (моделирование при ) [Kleinrock и Tobagi (1975), @ IEEE]

Для сравнения также показана зависимость задержки от характеристик прохождения для протоколов щелевой и бесщелевой Алохи. При этом моделировании только вновь генерированные пакеты считались независимыми и с пуассоновским распределением Столкновения и неравномерно распределенные случайные ретрансляции обходятся без последующих предположений. Результаты этого моделирования иллюстрируют превосходство качества -настойчивых и ненастойчивых протоколов относительно протоколов Алохи. Заметим, что значение, обозначенное на графике как «оптимальное -настойчивое» получено путем нахождения оптимального значения  для каждого значения проходимости. Мы видим, что для малых значений проходимости 1-настойчивой  протокол является оптимальным.