Nets2010 (1131259), страница 26

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

Текст из файла (страница 26)

Рисунок 4-3. Пропускная способность настойчивого CSMA-протокола уровня р по сравнению с другими

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

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

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

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

Рассмотрим подробнее алгоритм состязаний. Сколько времени станции, начавшей передачу, нужно, чтобы определить коллизию? Обозначим через τ время распространения сигнала до самой удаленной станции на линии. Для коаксиала в 1 км τ=5 мксек., в таком случае минимальное время для определения коллизии будет равно 2τ. Поэтому станция не может быть уверена, что она захватила канал до тех пор, пока не убедится, что в течение 2τ секунд не было коллизий. Поэтому мы будем рассматривать период состязаний как слотированную систему ALOHA со слотом 2τ секунд на один бит. Захватив канал, станция может далее передавать кадр с любой скоростью.

ALOHA.

В 70-х годах Норман Абрамсонсо своими коллегами из университета Гавайи предложил простой способ распределения доступа к каналу. Абрамсон назвал систему, 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 (рисунок 4-1).

Рисунок 4-1. Время, требуемое на обнаружение коллизии

Вероятность появления k кадров при передаче кадра при распределении Пуассона равна

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

За двойное время кадра среднее число кадров будет равна 2G, отсюда P₀=e^-2G

а так как S=GP₀, то S=Ge^-2G

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

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

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

S=Ge^-G

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

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

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

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

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

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

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

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

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

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

Однако даже если время задержки будет равно 0, коллизии все равно могут возникать. Например, если готовыми передавать оказались две станции, пока одна станция продолжает передавать. Они вежливо подождут, пока первая закончит передачу, а потом будут состязаться между собой. Тем не менее, этот протокол более эффективен, чем любая из систем ALOHA, так как станция учитывает состояние канала, прежде чем начать действовать.

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

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

Рисунок 4-3. Пропускная способность настойчивого CSMA-протокола уровня р по сравнению с другими

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

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

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

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

Характеристики

Список файлов ответов (шпаргалок)