Э. Таненбаум - Компьютерные сети. (4-е издание) (DJVU) (1130092), страница 79
Текст из файла (страница 79)
Пользователь В ьЛ с 1::) ь. ) 1:Л В ьз1::) 1::) 1:::) В1) П 1) 1) Время рис. 4.1. В чистой системе АгОнА кадры передаются в абсолютно произвольное время Когда два кадра одновременно пытаются занять канал, опи сталкиваются и уничтожаются. Даже если только один первый бит второго кадра перекрывается последним битом первого кадра, оба кадра уничтожаются полностью. При этом оба Протоколы коллективного доступа 297 кадра будут переданы позднее повторно.
Контрольная сумма не может (и не должна) отличать полную потерю информации от частичной. Потеря есть потеря. Самым интересным в данной ситуации является вопрос об эффективности канала системы АЕОНА. Другими словами, какая часть всех передаваемых кгдров способна избежать коллизий при любых обстоятельствах? Сначала рассмотрим бесконечное множество интерактивных пользователей, сидяших за своими компьютерами (станциями). Пользователь всегда находится в одном из двух состояний: ввод с клавиатуры и ожидание. Вначале все пользователи находятся в состоянии ввода. Закончив набор строки, пользователь перестает вводить текст, ожидая ответа.
В это время станция передает кадр, содержащий набранную строку, и опрашивает канал, проверяя успешность передачи кадра. Если кадр передан успешно, пользователь видит ответ и продолжает набор. В противном случае пользователь ждет, пока кадр не будет передан. Пусть «время кадраь означает интервал времени, требующийся для передачи стандартного кадра фиксированной длины (то есть длину кадра, деленную на скорость передачи данных). На данный момент мы предполагаем, что бесконечное количество пользователей порождает новые кадры, распределенные по Пуассону со следующим средним значением: Х кадров за время кадра (Допущение о бесконечном количестве пользователей необходимо для того, чтобы гарантировать, что величина М не станет уменыпаться по мере блокирования пользователей.) Если М > 1, это означает, что сообщество пользователей формирует кадры с большей скоростью, чем может быть передано по каналу, и почти каждый кадр будет страдать от столкновений.
Мы будем предполагать, что 0 < И< 1. Помимо новых кадров, станции формируют повторные передачи кадров, пострадавших от столкновений. Допустим также, что вероятность я попыток передачи старых и новых кадров за время кадра также имеет пуассоновское распределение со средним значением С за время кадра. Очевидно, что С~И При малой загрузке канала (то есть при Ум О) столкновений будет мало, поэтому мало будет и повторных передач, то есть СаМ. При большой загрузке канала столкновений будет много, а следовательно, С > М.
Какая бы ни была нагрузка, производительность канала 5 будет равна предлагаемой загрузке С, умноженной на вероятность успешной передачи, то есть Я= СР„где Р, — вероятность того, что кадр не пострадает в результате коллизии. Кадр не пострадает от коллизии в том случае, если в течение интервала времени его передачи не будет послано больше ни одного кадра, как показано на рис. 4.2. При каких условиях затененный кадр будет передан без повреждениИ Пусть à — это время, требуемое для передачи кадра. Если какой-либо пользователь сформирует кадр в интервале времени между 1, и г, + й то конец этого кадра столкнется с началом затененного кадра. При этом судьба затененного кадра предрешена еще до того, как будет послан его первый бит, однако, поскольку в чистой системе АЕОНА станции не прослушивают канал до начала передачи, у них нет способа узнать, что канал занят и по нему уже передается кадр.
Аналогичным образом любой другой кадр, передача которого начнется в интервале от ~, + Г до 1, + 2г, столкнется с концом затененного кадра. 2аа Глава 4. Подуровень управления доступом к среде Столкновение с концом затененного кадра Столкновение с началом затененного го + г го + период Гз + 3 Г Время — Р Рис. 4.2. Опасный интервал времени для затененного кащза Вероятность того, что в течение времени кадра будет сформировано в кадров, можно вычислить по формуле распределения Пуассона: Сза-с Рг1а1 = —.
1! (4.2) Таким образом, вероятность формирования нуля кадров в течение этого интервала времени равна е с. Среднее количество кадров, сформированных за интервал времени длиной в два кадра, равно 2С. Вероятность того, что никто не начнет передачу в течение всего опасного периода, равна Р, = е-'с. учитывая, что Я = СР„получаем: Се-и Зависимость производительности канала от предлагаемого трафика показана на рис. 4.3. Максимальная производительность достигает значения 5 = 1г2е, что приблизительно равно 0,184 при С = 0,5, Другими словами, лучшее, на что мы можем надеяться, — это использовать канал на 18%. Этот результат несколько Разочаровывает, однако в случае, когда каждый передает, когда хочет, трудно ожидать стопроцентного успеха.
Дискретная система А~ОНА В 1972 г. Робертс (КоЬеггз) опубликовал описание метода, позволяющего удвоить производительность систем АЕОНА (КоЬегтз, 1972), Его предложение заключалось в разделении времени на дискретные интервалы, соответствующие времени одного кадра. При таком подходе пользователи должны согласиться с определенными временными ограничениями. Одним из способов достижения синхРонизации является установка специальной станции, испускающей синхронизирующий сигнал в начале каждого интервала.
Протоколы коллективного доступа 299 $ $0,40 3,0 1.5 2,0 О,б 1,0 8 (количество попыток за время кадра) рис. я.в. зависимость производительности канала от предлагаемого »рафике для систем М.ОНА В системе Робертса, известной под названием дискретная АЕОНА, в отличие от чистой системы АЕОНА Абрамсона, компьютер не может начинать передачу сразу после нажатия пользователем клавиши Еп1ег. Вместо этого он должен дождаться начала нового такта. Таким образом, непрерывная чистая система А1.ОНА превращается в дискретную. Поскольку опасный временной интервал теперь становится в два раза короче, вероятность отсутствия передачи по каналу за тот же интервал времени, в течение которого передается тестовый кадр, равна е-с. В результате получаем: ЯмСе с (4.3) Как видно из рис. 4.3, дискретная система АЕОНА имеет пик при С = 1.
Прн этом производительность канала составляет Ум 1/е, что приблизительно равно 0„366, то есть в два раза больше, чем в чистой системе А) ОНА. Для дискретной системы А|ОНА в оптимальной ситуации 37 % интервалов будут пустыми, 37»е — с успешно переданными кадрами и 26 — со столкнувшимися кадрами. При увеличении количества попыток передачи в единицу времени О количество пустых интервалов уменьшается, но увеличивается количество конфликтных интервалов. Чтобы увидеть, насколько быстро растет количество конфликтных интервалов, рассмотрим передачу тестового кадра. Вероятность того, что он избежит столкновения, равна е с. Фактически, это вероятность того, что все остальные пользователи будут молчать в течение данного тактового интервала. Таким образом, вероятность столкновения равна 1 — е-с.
Вероятность передачи кадра ровно за к попыток (то есть после к — 1 столкновения, эа которыми последует успешная передача), равна Р е-с(1 е-с)»"! Ожидаемое число попыток передачи для одного кадра равно У ЬР ~ йс-с(1 Е-с )»-~ Ес »1 ми 300 Глава 4. Подуровень управления доступом к среде Поскольку число попыток передачи для одного кадра Е экспоненциально зависит от количества попыток передачи в единицу времени С, небольшое увеличение нагрузки в канале может сильно снизить его производительность. Дискретная система А|ОНА чрезвычайно важна по одной причине, которая на первый взгляд не кажется очевидной.
Она появилась в 1970-х годах, применялась в некоторых экспериментальных системах, затем была почти забыта. Когда был изобретен метод доступа в Интернет по кабельным сетям, вновь возникла проблема распределения единственного канала между болыпим числом конкурирующих абонентов. Тогда с полок достали запыленные описания дискретной А1.ОНА. Не раз уже было так, что вполне работоспособные протоколы и методы оказывались невостребованными по политическим причинам (например, когда какая-нибудь крупная компания выражала желание, чтобы все на свете использовали исключительно ее продукцию), однако по прошествии многих лет какой- нибудь мудрый человек вспоминал о существовании одного древнего метода, способного решить современную проблему.
По этой причине мы изучим в этой главе ряд элегантных протоколов, которые сейчас широко не используются, но запросто могут оказаться востребованными в будущем — если, конечно, об их существовании будет знать достаточное количество разработчиков сетей. Разумеется, мы изучим и используемые в настоящее время протоколы. Протоколы множественного доступа с контролем несущей В дискретной системе АЕОНА максимальный коэффициент использования канала, который может быть достигнут, равен 1/е. Такой скромный результат неудивителен, поскольку станции передают данные, когда хотят, не считаясь с тем, что делают остальные станции. В такой системе неизбежно возникает большое количество коллизий.
Однако в локальных сетях можно организовать процесс таким образом, что станции будут учитывать поведение друг друга. За счет этого можно достичь значения коэффициента использования канала значительно большего, чем 1/е. В данном разделе мы рассмотрим некоторые протоколы, позволяющие улучшить производительность канала. Протоколы, в которых станции прослушивают среду передачи данных и действуют в соответствии с этим, называются протоколами с контролем несущей.
Было разработано много таких протоколов, Кляйнрок (К1е(пгоск) и Тобаги (ТоЬая1) в 1975 году детально исследовали несколько таких протоколов. Далее мы рассмотрим несколько версий протоколов с контролем несущей. Настойчивый и ненастойчивый СЗМА Первый протокол с опросом несущей, который мы рассмотрим, называется 1-настойчивый протокол СЯМА (Сагнег Бепзе Мц1Вр1е Ассезв — множественный доступ с контролем несущей). Когда у станции появляются данные для передачи, она сначала прослушивает канал, проверяя, свободен он или занят. Если канал занят, то есть по нему передает какая-либо другая станция, станция ждет, пока он освободится. Когда канал освобождается, станция передает кадр.
Если происхо- Протоколы коллективного доступе 301 дит столкновение, станция ждет в течение случайного интервала времени, затем снова прослушивает канал и, если он свободен, пытается передать кадр еще раз. Такой протокол называется протоколом СЕМА с настойчивостью 1, так как станция передает кадр с вероятностью 1, как только обнаружит, что канал свободен, Ээдержка распространения сигнала оказывает сильное влияние на производительность данного протокола.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
