Протоколы множественного доступа к каналу (динамическое vs статическое выделение канала). Модель системы ALOHA. Сравнение производительности систем: чистая ALOHA, слотированная ALOHA. Протоколы множественного доступа с обнаружением несущей (настойчивые и не настойчивые CSMA, CSMA с обнаружением коллизий).

Статическое предоставление канала

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

Динамическое предоставление канала

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

1. Станции. Модель состоит из N независимых станций (компьютеров, телефонов, факс-машин и т.п.). На каждой работает пользователь или программа, которые генерируют кадры для передачи. Вероятность появления кадра в интервале длины Δt равна λΔt, где λ - константа и 0<λ<1. Предполагается, что если кадр сгенерирован, то станция блокируется, и новый кадр не появится, пока не будет передан первый. Это предположение означает, что станции независимы, и на каждой работает только одна программа или пользователь, которые генерируют нагрузку с постоянной скоростью.

2. Единственность канала. Канал один и он доступен всем станциям. Все станции равноправны. Они получают кадры и передают кадры только через этот единственный канал. Аппаратные средства всех станций для доступа к каналу одинаковы, но программно можно устанавливать станциям приоритеты.

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

4. Время. Мы будем предполагать две модели времени – непрерывное время и дискретное время.

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

2. Дискретное время. В слоте может оказаться 0 кадров, если это слот ожидания, 1 кадр - если в этом слоте передача кадра прошла успешно, несколько кадров, если в этом слоте произошла коллизия.

1. Доступ к каналу: возможны два способа доступа станции к каналу.

1. С обнаружением несущей. Станция, прежде чем использовать канал, всегда определяет, занят он или нет. Если он занят, то станция не начинает передачу.

2. Отсутствие несущей. Станция ничего не знает о состоянии канала, пока не начнет использовать его. Она сразу начинает передачу и лишь позднее обнаруживает коллизию.

Есть и другие модели, которые предусматривают многопользовательские станции, но эти модели намного сложнее. Единый канал передачи - это краеугольное предположение.

Протоколы множественного доступа.

ALOHA

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

Чистая ALOHA

Идея чистой ALOHA проста - любой пользователь, желающий передать сообщение, сразу пытается это сделать. Благодаря тому, что в вещательной среде он всегда имеет обратную связь, т.е. может определить, пытался ли кто-то еще передавать на его частоте, то он может установить возникновение конфликта при передаче. Такая обратная связь в среде LAN происходит практически мгновенно, в системах спутниковой связи задержка составляет около 270 мсек. Обнаружив конфликт, пользователь ожидает некоторый случайный отрезок времени, после чего повторяет попытку. Интервал времени на ожидание должен быть случайным, иначе конкуренты будут повторять попытки в одно и то же время, что приведет к их блокировке. Системы подобного типа, где пользователи конкурируют за получение доступа к общему каналу, называются системами с состязаниями. Не важно, когда произошел конфликт: когда первый бит одного кадра «наехал» на последний бит другого кадра или как-то иначе, оба кадра считаются испорченными и должны быть переданы повторно. Контрольная сумма, защищающая данные в кадре, не позволяет различать разные случаи наложения кадров. Какова эффективность системы ALOHA, измеренная в количестве кадров, которые избежали коллизий? Для ответа на этот вопрос рассмотрим следующую модель.  Есть неограниченное число пользователей, работающих на компьютерах. Все что они могут делать, - это либо набирать текст, либо ждать, пока набранный текст будет передан. Когда пользователь заканчивает набирать очередную строку, он останавливается и ждет ответа от системы. Система пытается передать эту строку. Когда она сделает это, пользователь видит отклик и может продолжать работу. Назовем временем кадра время, необходимое на передачу кадра стандартной фиксированной длины. Предполагаем, что число пользователей неограниченно, и они порождают кадры по закону Пуассона со средним S кадров за время кадра. Поскольку при S>1 очередь на передачу будет только расти и все кадры будут страдать от коллизий, то мы будем предполагать 0<S<1. Также будем предполагать, что вероятность за время кадра сделать k попыток передачи распределена по закону Пуассона со средним G. Понятно, что должно быть GіS, иначе очередь будет расти бесконечно. При слабой загрузке (S»0) будет мало передач, а следовательно и коллизий, поэтому допустимо G»S. При высокой загрузке должно быть G>S. При любой нагрузке пропускная способность это - число кадров, которые надо передать, умноженное на вероятность успешной передачи. Если обозначить P0 вероятность отсутствия коллизий при передаче кадра, то S=GP0.

Рассмотрим внимательно, сколько времени нужно отправителю, чтобы обнаружить коллизию. Пусть он начал передачу в момент времени t₀ и пусть требуется время t, чтобы кадр достиг самой отдаленной станции. Тогда, если в тот момент, когда кадр почти достиг этой отдаленной станции, она начнет передачу (ведь в системе ALOHA станция сначала передает, а потом слушает), то отправитель узнает об этом только через t₀+2t . Вероятность появления k кадров при передаче кадра при распределении Пуассона равна

поэтому вероятность, что появится 0 кадров, равна e^-G.

За двойное время кадра среднее число кадров будет равна 2G, отсюда

P0=e^-2G

а так как S=GP₀, то

S=Ge^-2G

Зависимость между нагрузкой и пропускной способностью показана на рисунке 4-2 (нижний график). Максимальная пропускная способность достигается при G=0,5 при S=1/2e, что составляет примерно 18% от номинальной пропускной способности. Это означает, что если мы будем генерировать кадры с большей скоростью, чем 18% от скорости канала, то очереди переполнятся и система «захлебнется». Результат не очень вдохновляющий, но это плата за удобство: каждый передает, когда захочет.

Слотированная ALOHA

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

S=Ge^-G

Как видно из рисунка 4-3, максимум пропускной способности слотированной ALOHA наступает при G=1, где S=1/e, т.е. около 0,37, что вдвое больше, чем у чистой ALOHA.

Рассмотрим, как G влияет на пропускную способность. Для этого подсчитаем вероятность успешной передачи кадра за k попыток. Так как e^-G - вероятность отсутствия коллизии при передаче, то вероятность, что кадр будет передан ровно за k попыток, равна  

P_k=e^-G(1-e^-G)^k-1

Среднее ожидаемое число повторных передач будет равно

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

Протоколы множественного доступа с обнаружением несущей

Максимальная пропускная способность, какую мы можем получить для системы ALOHA, достигается при S=1/е. Это не удивительно, так как в этих системах станция не обращает внимания на то, что делают другие. Поэтому вероятность коллизии чрезвычайно высока. В локальных сетях есть возможность определить, что делают другие станции, и только после этого решать, что делать самому. Протоколы, которые реализуют именно эту идею – сначала определить, занят канал или нет и только после этого действовать -  называются протоколами с обнаружением несущей CSMA (Carrier Sensitive Multiple Access).

Настойчивые и ненастойчивые CSMA-протоколы

Согласно протоколу, который мы сейчас рассмотрим, станция, прежде чем что-либо передавать, определяет состояние канала. Если канал занят, то она ждет. Как только канал освободился, она пытается начать передачу. Если при этом произошла коллизия, она ожидает случайный интервал времени и все начинает с начала. Этот протокол называется  настойчивым CSMA-протоколом первого уровня или 1-настойчивым CSMA-протоколом, потому что станция, следуя этому протоколу, начинает передачу с вероятностью 1, как только обнаруживает, что канал свободен. Здесь важную роль играет задержка распространения сигнала в канале. Всегда есть шанс, что, как только одна станция начала передачу, другая также стала готовой передавать. Если вторая станция проверит состояние канала прежде, чем до нее дойдет сигнал от первой о том, что она заняла канал, то вторая станция сочтет канал свободным и начнет передачу. В результате - коллизия. Чем больше время задержки, тем больше вероятность такого случая, тем хуже производительность канала. Однако даже если время задержки будет равно 0, коллизии все равно могут возникать. Например, если готовыми передавать оказались две станции, пока одна станция продолжает передавать. Они вежливо подождут, пока первая закончит передачу, а потом будут состязаться между собой. Тем не менее, этот протокол более эффективен, чем любая из систем ALOHA, так как станция учитывает состояние канала, прежде чем начать действовать. Другой вариант CSMA-протокола - ненастойчивый CSMA-протокол. Основное отличие его от предыдущего в том, что готовая к передаче станция опрашивает канал. Если он свободен, то она начинает передачу. Если он занят, то она не будет настойчиво его опрашивать в ожидании, когда он освободится, а будет делать это через случайные отрезки времени. Это несколько увеличивает задержку при передаче, но общая эффективность протокола возрастает. И, наконец, настойчивый CSMA-протокол уровня р. Он применяется к слотированным каналам. Когда станция готова к передаче, она опрашивает канал. Если он свободен, то она с вероятностью р передает свой кадр и с вероятностью q=1-p ждет следующего слота. Так она действует, пока не передаст кадр. Если произошла коллизия во время передачи, она ожидает случайный интервал времени и опрашивает канал опять. Если при опросе канала он оказался занят, станция ждет начала следующего слота, и весь алгоритм повторяется. На рисунке 4-3 показана пропускная способность этого протокола в зависимости от нагрузки.

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

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

На рисунке 4-4 показана модель, которая используется во многих протоколах этого класса. В момент t0 станция заканчивает передачу очередного кадра. Все станции, у которых есть кадр для передачи, начинают передачу. Естественно, происходят коллизии, которые быстро обнаруживаются сравнением отправленного сигнала с тем, который есть на линии. Обнаружив коллизию, станция сразу прекращает передачу на случайный интервал времени, после чего все начинается сначала. Таким образом, в работе протокола CSMA/CD можно выделить три стадии: состязания, передачи и ожидания, когда нет кадров для передачи.

Рисунок 4-4. Стадии работы протокола CSMA/CD

Надо также отметить, что МАС-подуровень обеспечивает надежную передачу, используя специальные приемы кодирования данных. Примеры таких кодировок мы рассматривали в гл. 2 (см. Манчестерские коды).

1. Протоколы множественного доступа к каналу: Бесконфликтные протоколы (Bit-Map протокол, Адресный счетчик). Протоколы с ограниченным числом конфликтов. Протоколы с множественным доступом и разделением частот

Хотя в протоколе CSMA/CD коллизии могут возникать только в период состязаний, тем не менее, при больших t и коротких кадрах они съедают часть пропускной способности канала. Здесь мы рассмотрим, как можно этих коллизий избежать. Мы будем предполагать, что у нас есть N станций с адресами от 0 до N-1. Все адреса уникальны. Основным является вопрос: как определить, кто будет владеть каналом, когда закончится текущая передача?

Bit-Map-протокол

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