Управление доступом к среде
Интуитивные предпосылки к использованию случайного доступа к среде могут быть найдены в результатах анализа эффективности АRQ-процедур. Выражение (4.1) показывает, что время реакции среды 
на попытку передачи кадра оказывает существенное влияние на производительность МАС-протокола. Нечто подобное наблюдалось и при анализе эффективности процедур ARQ. Протокол с остановкой и ожиданием демонстрировал хорошую эффективность лишь в условиях малости времени реакции системы (tp+tpr) на отсылаемый кадр. Существенное снижение эффективности процедуры SW_ARQ при росте времени (tp+tpr) легко объяснялось жесткой связью действий протокола с фактом прибытия подтверждений, а последние не могли приходить с задержкой меньшей 2(tp+tpr). Это препятствия было преодолено в процедуре ARQ с возвратом на N посредством разрешения передачи очередного кадра без получения подтверждения успешного приема предшествующего; при этом меры к исправлению ошибок передачи принимались лишь тогда, когда они действительно возникали.
Аналогичные аргументы можно привести и в пользу случайного метода доступа к среде, при котором передача разрешается в любой момент времени, а с последствиями коллизий начинают бороться только тогда, когда они возникают. Первая реализация такого метода, - алгоритм ALOHA, - был применен не в локальной, а в распределенной территориальной сети.
Алгоритм ALOHA
Впервые метод случайного доступа к среде передачи был реализован в компьютерной сети университете штата Гавайи (США). Кампус университета располагался на нескольких островах, и терминальные пункты вычислительных лабораторий необходимо было соединить с хост-компьютером. Для этого были построены радиоканалы, работающие на одной частоте, и каждому терминалу разрешалось начинать передачу в любой момент, когда у него появлялся кадр. Поскольку терминалы находились на значительном удалении от хост-компьютера и один от другого, то контролировать состояние других терминалов и, следовательно, занятость канала они не могли. Это имело два следствия.
1. Любой терминал мог начать свою передачу в период передачи кадра другим терминалом, что приводило к искажениям обоих кадров в точке приема.
2. Индикация факта возникновения/отсутствия коллизии передающими терминалами оказывалась невозможной. Поэтому, единственным способом извещения передатчика о «судьбе» отправленного им кадра оставалась отправка приемником кадра-подтверждения. Неполучение его передатчиком в определенном интервале времени интерпретировалось как факт потери переданного кадра.
Очевидно, что пока интенсивность генерации кадров терминалами оставалась относительно невысокой, вероятность их «столкновений» была малой, и система работала вполне удовлетворительно. Однако, рост интенсивности трафика неизбежно вел к росту вероятности коллизий, увеличению числа повторных передач и к падению эффективной производительности сети. В этих условиях, вопрос о предельно допустимых нагрузках в таких системах приобрел очевидную актуальность. Н. Абрамсон (1971) провел анализ производительности алгоритма ALOHA, который в основных чертах излагается ниже.
Пусть размер кадров является постоянным и равен L, а битовая скорость их передачи равна R. Тогда, время передачи одного кадра составит 
. На рис. 4.6 приведен один из возможных сценариев, когда после передачи кадра выдерживается тайм-аут длительностью не менее двух времен его доставки и обработки приемником, а при отсутствии подтверждения успешной доставки, со случайной задержкой в В секунд производится повторная передача.
 |
Из рис. 4.6. хорошо видно, что вероятность передачи кадра без коллизии равна вероятности отсутствия передачи двумя, тремя и т.д. терминалами в интервале времени [ 
], т.е. в интервале, равном 2Х. Вычисление этой вероятности требует определенных допущений о статистических характеристиках процесса поступления кадров в среду.
Пусть S – среднее количество кадров, успешно переданных в сети за время 
. Значение S > 1 означало бы возможность одновременной передачи в среде нескольких кадров без их коллизий, что невозможно. Поэтому, всегда 
. Для передачи этих кадров, пропускная способность канала затрачивалась и на повторные передачи «испорченных» кадров, т.е., среднее число кадров, переданных в канале за время X, равно 
. Рассматривая величину 
как нагрузку среды передачи, можно величину 
трактовать как показатель уровня «полезного» ее использования (производительность протокола доступа).
В общем случае, взаимосвязь величин S и G установить трудно. Вместе с тем, есть достаточно оснований считать, что поток кадров, поступающих в MAC-модули сетевых узлов, является пуассоновским случайным процессом. Допустим также, что и поток повторно передаваемых кадров является пуассоновским. Вообще говоря, это не так, поскольку повторные передачи являются зависимыми случайными событиями. Тем не менее, достаточно строгое рассмотрение показало, что допущение о пуассоновском характере потока вторичных передач справедливо при умеренной их интенсивности. Примем это допущение, и будем считать полный поток кадров, поступающих в среду передачи пуассоновским со средним значением интенсивности G/X. Тогда, среднее число кадров, поступающих в канал за время уязвимости (2X секунд) составит 2G, а вероятность поступления в канал за это же время k кадров будет равной
.
Кадр, передача которого началась в момент 
, будет успешно получен, если за время [ ] другими станциями не будет отправленоно ни одного кадра. Вероятность такого события вычисляется из приведенного выше выражения при 
. В соответствии с этим, среднее количество успешно доставленных получателю кадров за время X составит
. (4.2)
Зависимость S(G) представлена на рис. 4.7 (кривая «чистая ALOHA»). Экстремум этой функции, очевидно, соответствует значению G=0,5 и равен 0,184. Это очень скромная величина, но не будем забывать, что она достигнута при минимальных затратах на управление доступом к каналу.
 |
Важной характеристикой алгоритма является среднее время доставки кадра. В рассматриваемом алгоритме среднее число попыток, предпринимаемых для пересылки одного кадра, составляет
. (4.3)
Следовательно, число неудачных попыток 
.
Считая, что время распространения сигнала от передающей станции к приемной равно tр, для среднего времени доставки кадра можно записать очевидное соотношение
Соответственно, нормированное к длительности передачи кадра, время доставки будет
. (4.4)
Полученное выражение показывает, что время доставки может расти экспоненциально с ростом нагрузки (см. рис. 4.5) и большие значения параметра a, будут негативно сказываться на времени доставки кадра.
Производительность алгоритма ALOHA можно заметно увеличить, если дополнить его ограничением, позволяющим станциям начинать передачу своих кадров не в произвольный момент времени, а только в моменты, кратные длительности генерации кадра, т.е. в моменты X, 2X, 3X, и т.д. Это дало основание назвать такой алгоритм «тактированная ALOHA» (дискретная, синхронная ALOHA). Эта простая мера позволяет сократить интервал уязвимости (рис. 4.5) вдвое. Соответственно, уменьшается и вероятность коллизий кадров в канале
,
а производительность протокола будет описываться выражением
. (4.5)
Экстремум такой функция S(G) достигает при G=1 и ее максимальное значение равно 0,368 (рис. 4.7). Это примерно вдвое больше, чем для «чистого» алгоритма ALOHA. Таким образом, введение большей упорядоченности в систему (дополнительные усилия по управлению доступом к среде) сказалось благоприятно на ее производительности. «Цена» такой упорядоченности – необходимость стабильных тактовых генераторов и общесетевой системы их синхронизации.
Низкие значения максимально достижимой производительности при рассмотренном методе доступа к среде является следствием полной асинхронности поведения передатчиков станций, отсутствия возможности взаимной их координации. В локальных сетях такая координация поведения станций оказывается возможной, что и позволяет повысить эффективность используемых в них алгоритмов случайного доступа.