Э. Таненбаум - Компьютерные сети. (4-е издание) (PDF) (1130118), страница 75
Текст из файла (страница 75)
Обратите внимание на слово «несущая». В данномслучае оно означает электрический сигнал, распространяющийся по каналу1.Протоколы коллективного доступаИзвестно много алгоритмов коллективного доступа. В следующих разделах будутрассмотрены наиболее интересные алгоритмы и даны примеры их применения.Система ALOHAВ 70-х годах Норман Абрамсон (Norman Abramson) и его коллеги из Гавайскогоуниверситета разработали новый элегантный метод решения проблемы распределения каналов. Их труды впоследствии стали основой многих исследованийСлово «carrier» («несущая») в английском языке означает также «перевозчик».
— Примеч. перев.296Глава 4. Подуровень управления доступом к среде(Abramson, 1985). Хотя в работе Абрамсона, получившей название ALOHA, использовалась широковещательная радиосвязь со стационарными передатчиками,основная идея применима к любой системе, в которой независимые пользователисоревнуются за право использования одного общего канала.В данной главе мы рассмотрим две версии системы ALOHA: чистую и дискретную.
Они отличаются тем, делится ли время на дискретные интервалы, в течение которых передаются кадры, или нет. В чистой системе ALOHA не требуется общая синхронизация времени, а в дискретной требуется.Чистая система ALOHAВ основе системы ALOHA лежит простая идея: разрешить пользователям передачу, как только у них появляются данные для отсылки. Конечно, при этом будутстолкновения, и столкнувшиеся кадры будут разрушены. Однако благодарясвойству обратной связи широковещательной системы отправитель всегда можетустановить, дошел ли его кадр до получателя или был разрушен. Для этого емунужно просто прослушивать канал, как это делают все остальные пользователи.В локальных сетях обратная связь мгновенная, а в спутниковых системах существует задержка в 270 мс, и только после этого отправитель может узнать, насколько успешной была передача.
Если кадр был уничтожен, отправитель просто выжидает некоторое случайное время и пытается переслать этот кадр снова. Времяожидания должно быть случайным. В противном случае при равных фиксированных интервалах времени ожидания коллизии будут повторяться снова и снова. Системы, в которых несколько пользователей используют один общий каналтаким способом, что время от времени возникают конфликты, называются системами с конкуренцией.На рис. 4.1 показан пример формирования кадров в системе ALOHA. Все кадрына нашем рисунке имеют один размер, так как при этом пропускная способностьсистемы сделана максимальной именно за счет фиксированного размера кадров.ПользовательАВ•СD•••ЕВремяРис.
4 . 1 . В чистой системе ALOHA кадры передаются в абсолютно произвольное времяКогда два кадра одновременно пытаются занять канал, они сталкиваются и уничтожаются. Даже если только один первый бит второго кадра перекрывается последним битом первого кадра, оба кадра уничтожаются полностью. При этом обаПротоколы коллективного доступа297кадра будут переданы позднее повторно. Контрольная сумма не может (и недолжна) отличать полную потерю информации от частичной. Потеря есть потеря.Самым интересным в данной ситуации является вопрос об эффективностиканала системы ALOHA. Другими словами, какая часть всех передаваемых кадров способна избежать коллизий при любых обстоятельствах? Сначала рассмотрим бесконечное множество интерактивных пользователей, сидящих за своимикомпьютерами (станциями).
Пользователь всегда находится в одном из двух состояний: ввод с клавиатуры и ожидание. Вначале все пользователи находятся всостоянии ввода. Закончив набор строки, пользователь перестает вводить текст,ожидая ответа. В это время станция передает кадр, содержащий набранную строку, и опрашивает канал, проверяя успешность передачи кадра. Если кадр передан успешно, пользователь видит ответ и продолжает набор. В противном случаепользователь ждет, пока кадр не будет передан.Пусть «время кадра» означает интервал времени, требующийся для передачистандартного кадра фиксированной длины (то есть длину кадра, деленную наскорость передачи данных).
На данный момент мы предполагаем, что бесконечное количество пользователей порождает новые кадры, распределенные по Пуассону со следующим средним значением: N кадров за время кадра. (Допущениео бесконечном количестве пользователей необходимо для того, чтобы гарантировать, что величина N не станет уменьшаться по мере блокирования пользователей.) Если N> 1, это означает, что сообщество пользователей формирует кадры сбольшей скоростью, чем может быть передано по каналу, и почти каждый кадрбудет страдать от столкновений. Мы будем предполагать, что 0 < N< 1.Помимо новых кадров, станции формируют повторные передачи кадров, пострадавших от столкновений. Допустим также, что вероятность k попыток передачи старых и новых кадров за время кадра также имеет пуассоновское распределение со средним значением G за время кадра.
Очевидно, что G>N. Прималой загрузке канала (то есть при N« 0) столкновений будет мало, поэтому мало будет и повторных передач, то есть G&N. При большой загрузке каналастолкновений будет много, а следовательно, G> N. Какая бы ни была нагрузка,производительность канала 5 будет равна предлагаемой загрузке G, умноженнойна вероятность успешной передачи, то есть S = GPQ, где Ро — вероятность того,что кадр не пострадает в результате коллизии.Кадр не пострадает от коллизии в том случае, если в течение интервала времени его передачи не будет послано больше ни одного кадра, как показано нарис.
4.2. При каких условиях затененный кадр будет передан без повреждений?Пусть t — это время, требуемое для передачи кадра. Если какой-либо пользователь сформирует кадр в интервале времени между t0 и t0 +1, то конец этого кадрастолкнется с началом затененного кадра. При этом судьба затененного кадрапредрешена еще до того, как будет послан его первый бит, однако, поскольку вчистой системе ALOHA станции не прослушивают канал до начала передачи, уних нет способа узнать, что канал занят и по нему уже передается кадр. Аналогичным образом любой другой кадр, передача которого начнется в интервале отt0 +1 до tu + 2t, столкнется с концом затененного кадра.298Протоколы коллективного доступаГлава 4.
Подуровень управления доступом к средетI299Дискретная ALOHA: S = Ge~GСтолкновениес концомзатененногокадраСтолкновениес началомзатененногокадраI00to+2t(о + 3 f Время0,51,01,52,03,0G (количество попыток за время кадра)Уязвимый.периодРис. 4.3. Зависимость производительности канала от предлагаемого трафика для систем ALOHAРис. 4 . 2 . Опасный интервал времени для затененного кадраВероятность того, что в течение времени кадра будет сформировано k кадров,можно вычислить по формуле распределения Пуассона:Рг[*] = -(4.2)Таким образом, вероятность формирования нуля кадров в течение этого интервала времени равна е~с.
Среднее количество кадров, сформированных за интервал времени длиной в два кадра, равно 2G. Вероятность того, что никто неначнет передачу в течение всего опасного периода, равна Ро = e~2G. Учитывая, что5 = GP0, получаем:S=Ge-2C.Зависимость производительности канала от предлагаемого трафика показанана рис. 4.3. Максимальная производительность достигает значения 5= 1/2е, чтоприблизительно равно 0,184 при G = 0,5. Другими словами, лучшее, на что мыможем надеяться, — это использовать канал на 18 %. Этот результат несколькоразочаровывает, однако в случае, когда каждый передает, когда хочет, трудноожидать стопроцентного успеха.Дискретная система ALOHAВ 1972 г. Роберте (Roberts) опубликовал описание метода, позволяющего удвоить производительность систем ALOHA (Roberts, 1972).
Его предложение заключалось в разделении времени на дискретные интервалы, соответствующиевремени одного кадра. При таком подходе пользователи должны согласиться сопределенными временными ограничениями. Одним из способов достижениясинхронизации является установка специальной станции, испускающей синхронизирующий сигнал в начале каждого интервала.В системе Робертса, известной под названием дискретная ALOHA, в отличиеот чистой системы ALOHA Абрамсона, компьютер не может начинать передачусразу после нажатия пользователем клавиши Enter. Вместо этого он должен дождаться начала нового такта. Таким образом, непрерывная чистая системаALOHA превращается в дискретную.
Поскольку опасный временной интервалтеперь становится в два раза короче, вероятность отсутствия передачи по каналуза тот же интервал времени, в течение которого передается тестовый кадр, равнае~с. В результате получаем:S=Ge~c.(4.3)Как видно из рис. 4.3, дискретная система ALOHA имеет пик при G = 1. Приэтом производительность канала составляет S = 1/е, что приблизительно равно0,368, то есть в два раза больше, чем в чистой системе ALOHA. Для дискретнойсистемы ALOHA в оптимальной ситуации 37 % интервалов будут пустыми,37 % — с успешно переданными кадрами и 26 % — со столкнувшимися кадрами.При увеличении количества попыток передачи в единицу времени G количествопустых интервалов уменьшается, но увеличивается количество конфликтныхинтервалов. Чтобы увидеть, насколько быстро растет количество конфликтныхинтервалов, рассмотрим передачу тестового кадра.
Вероятность того, что он избежит столкновения, равна е~с. Фактически, это вероятность того, что все остальные пользователи будут молчать в течение данного тактового интервала. Таким образом, вероятность столкновения равна 1 - e~G. Вероятность передачикадра ровно за k попыток (то есть после k - 1 столкновения, за которыми последует успешная передача), равнаОжидаемое число попыток передачи для одного кадра равноk = £ ke'pе'= °3 0 0 Глава 4. Подуровень управления доступом к средеПоскольку число попыток передачи для одного кадра Е экспоненциально зависит от количества попыток передачи в единицу времени G, небольшое увеличение нагрузки в канале может сильно снизить его производительность.Дискретная система ALOHA чрезвычайно важна по одной причине, котораяна первый взгляд не кажется очевидной. Она появилась в 1970-х годах, применялась в некоторых экспериментальных системах, затем была почти забыта.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
