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




3.1. Семейство протоколов ALOHA.

В 70-хгодах НорманАбрамсон со своими коллегами из университета Гаваи предложил простой способ распределения канала. Абрамсон назвал систему ALOHA - это приветствие по гавайски, состоявшей из наземных радиостанций, связывающих острова между собой. Идея была позволить в вещательной среде любому количеству пользователей неконтролируемо использовать один и тот же канал.

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

Чистая ALOHA
Идея чистой ALOHA проста - любой пользователь пытается передать сообщение. Благодаря тому, что в вещательной среде он всегда имеет обратную связь, то он видит возникновение конфликта при передаче. Эта обратная связь в среде LAN происходит практически мгновенно, в системах спутниковой связи задержка составляет около 270 mсек.

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

Неважно когда произошел конфликт когда первый бит одного кадра наложился на последний бит другого кадра или как-то иначе, оба кадра считаются испорченными и должны быть переданы повторно. Контрольная суммам не позволяет различать разные случаи наложения.

Какова эффективность системы ALOHA? Какая часть кадров избежала коллизий? Рассмотрим следующую модель. Есть неограниченное число пользователей, работающих на компьютерах. Все что они могут делать это - либо набирать текст, либо ждать пока набранный текст передается. Когда пользователь заканчивает набирать очередную строку, он останавливается и ждет ответа от системы. Система пытается передать эту строку. Когда она сделает это успешно, пользователь видит отклик и может продолжать работу.

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

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

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

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

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

,

а так как , то

.

Рис.3. 1 Зависимость производительности канала от предлагаемого трафика для систем ALOHA

Зависимость между нагрузкой и пропускной способность показана на Рис.3.1. максимальная пропускная способность достигается при при , что составляет примерно 18%. Результат не очень вдохновляющий.

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

.

Как видно из рис. 1 максимум пропускной способности слотированной ALOHA наступает при , где , т.е. около 0,37, что в двое больше чем у чистой ALOHA.

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

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

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

3.2. Протоколы множественного доступа с контролем несущей (CSMA).

Лучший результат, какой мы можем получить для системы ALOHA - 1/е. Это не удивительно, так как там станция не обращает внимание на, что делают другие. В локальных сетях есть возможность определить, что делают другие станции и только после этого решать что делать.

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

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

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

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

И,наконец, CSMA настойчивый протокол уровня р. Он применяется к слотированным каналам. Когда станция готова к передаче она опрашивает канал, если он свободен, то она с вероятностью р передает свой кадр и с вероятностью ждет следующего слота. Так она действует пока не передаст кадр. Если произошла коллизия вовремя передачи, она ожидает случайный интервал времени и опрашивает канал опять. Если при опросе канала он оказался занят, станция ждет начала следующего слота и весь алгоритм повторяется. НаРис.3.2 показана пропускная способность в зависимости от нагрузки.

Рис.3. 2 Сравнение использования канала в зависимости отего нагрузки для различных протоколов коллективного доступа

3.3. Протоколы множественного доступа с контролем несущей с определением коллизий (CSMA/CD).

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

Рис.3.3 Протокол CSMA/CD может находиться в одном из трех состояний: конкуренции, передачи и простоя.

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

Рис.3. 4 Алгоритмы приема и передачи данных в узле при CSMA/CD

На Рис.3.4 представлены алгоритмы приема и передачи данных в одном из узлов при CSMA/CD.

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

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

3.4. Доступ с передачей маркера

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

Когда какой-либо компьютер «наполнит» маркер своей информацией и пошлет его по сетевому кабелю, другие компьютеры уже не могут передавать данные. Так в каждый момент времени только один компьютер будет использовать маркер, в сети не возникнет ни состязания, ни коллизий, ни временных пауз.

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

3.5. Доступ по приоритету запроса.

Доступ по приоритету запроса — относительно новый метод доступа, разработан для стандарта сети Ethernet со скоростью передачи данных 100 Мбит/с — 100VG-AnyLAN. Он стандартизован IEEE в категории 802.12.

Этот метод доступа основан на том, что все сети 100VG-AnyLAN строятся только из концентраторов и оконечных узлов. Концентраторы управляют доступом к кабелю, последовательно опрашивая все узлы в сети и выявляя запросы на передачу. Концентратор должен знать все адреса, связи и узлы и проверять их работоспособность. Оконечным узлом, в соответствии с определением 100VG-AnyLAN, может быть компьютер, мост, маршрутизатор или коммутатор.

Состязание приоритетов запроса

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

В сетях с использованием доступа по приоритету запроса каждый компьютер может одновременно передавать и принимать данные (дуплексный обмен данными), поскольку для этих сетей разработана специальная схема кабеля. В них применяется восьмипроводной кабель, по каждой паре проводов сигналы передаются с частотой 25 МГц.

Опросные системы идеальны для сетевых устройств, чувствительных ко времени, например, при автоматизации оборудования.

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-29 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: