Э. Таненбаум, Д. Уэзеролл - Компьютерные сети (1114668), страница 83
Текст из файла (страница 83)
Контрольнаясумма не может (и не должна) отличать полную потерю информации от частичной.Потеря есть потеря.Самым интересным в данной ситуации является вопрос об эффективности каналасистемы ALOHA. Другими словами, какая часть всех передаваемых кадров способнаизбежать коллизий при любых обстоятельствах? Сначала рассмотрим бесконечноемножество пользователей, сидящих за своими компьютерами (станциями). Пользователь всегда находится в одном из двух состояний: ввод с клавиатуры и ожидание.Вначале все пользователи находятся в состоянии ввода. Закончив набор строки,пользователь перестает вводить текст, ожидая ответа.
В это время станция передаеткадр, содержащий набранную строку, по общему каналу на центральный компьютери опрашивает канал, проверяя успешность передачи кадра. Если кадр передан успешно, пользователь видит ответ и продолжает набор. В противном случае пользовательждет, пока кадр не будет передан повторно, и это может происходить несколько раз.Пусть «время кадра» означает интервал времени, требуемый для передачи стандартного кадра фиксированной длины (то есть длину кадра, деленную на скоростьпередачи данных). На данный момент мы предполагаем, что новые кадры, порождаемые станциями, хорошо распределены по Пуассону со средним значением N кадровза время кадра.
(Допущение о бесконечном количестве пользователей необходимодля того, чтобы гарантировать, что величина N не станет уменьшаться по мере блокирования пользователей.) Если N > 1, это означает, что сообщество пользователейформирует кадры с большей скоростью, чем может быть передано по каналу, и почтикаждый кадр будет страдать от столкновений. Мы будем предполагать, что 0 < N <1.288 Глава 4. Подуровень управления доступом к средеПомимо новых кадров, станции формируют повторные передачи кадров, пострадавших от столкновений. Допустим также, что старые и новые кадры хорошо распределены по Пуассону со средним значением G кадров за время кадра. Очевидно,что G ≥ N. При малой загрузке канала (то есть при N ≈ 0) столкновений будет мало,поэтому мало будет и повторных передач, то есть G ≈ N.
При большой загрузке канала столкновений будет много, а следовательно, G > N. Какая бы ни была нагрузка,производительность канала S будет равна предлагаемой загрузке G, умноженной навероятность успешной передачи, то есть S = GP0, где P0 — вероятность того, что кадрне пострадает в результате коллизии.Кадр не пострадает от коллизии в том случае, если в течение интервала времениего передачи не будет послано больше ни одного кадра, как показано на рис. 4.2.
Прикаких условиях затененный кадр будет передан без повреждений? Пусть t — этовремя, требуемое для передачи кадра. Если какой-либо пользователь сформируеткадр в интервале времени между t0 и t0 + t, то конец этого кадра столкнется с началомзатененного кадра. При этом судьба затененного кадра предрешена еще до того, какбудет послан его первый бит, однако, поскольку в чистой системе ALOHA станции непрослушивают канал до начала передачи, у них нет способа узнать, что канал занят ипо нему уже передается кадр. Аналогичным образом, любой другой кадр, передача которого начнется в интервале от t0 + t до t0 + 2t, столкнется с концом затененного кадра.Рис. 4.2.
Уязвимый период времени для затененного кадраВероятность того, что в течение времени кадра, когда ожидается G кадров, будетсформировано k кадров, можно вычислить по формуле распределения Пуассона:Pr[k] =G ke !Gk!(4.2)Таким образом, вероятность формирования нуля кадров в течение этого интервалавремени равна e–G. Среднее количество кадров, сформированных за интервал времени4.2. Протоколы коллективного доступа 289длиной в два кадра, равно 2G. Вероятность того, что никто не начнет передачу в течение всего уязвимого периода, равна P0 = e–2G. Учитывая, что S = GP0, получаем:S = Ge–2G.Зависимость производительности канала от предлагаемого трафика показана нарис. 4.3.
Максимальная производительность достигает значения S = 1/(2e), что приблизительно равно 0,184, при G = 0,5. Другими словами, лучшее, на что мы можем надеяться, — это использовать канал на 18 %. Этот результат несколько разочаровывает,однако в случае, когда каждый передает, когда хочет, трудно ожидать стопроцентногоуспеха.Рис. 4.3.
Зависимость производительности канала от предлагаемого трафика для систем ALOHAДискретная система ALOHAВскоре после появления на сцене системы ALOHA Робертс (Roberts, 1972) опубликовал описание метода, позволяющего удвоить производительность систем ALOHA.Его предложение заключалось в разделении времени на дискретные интервалы, называемые слотами (или тактами), соответствующие времени одного кадра. При такомподходе пользователи должны согласиться с определенными временными ограничениями. Одним из способов достижения синхронизации является установка специальнойстанции, испускающей синхронизирующий сигнал в начале каждого интервала.В системе Робертса, известной под названием дискретная ALOHA, в отличие отчистой системы ALOHA Абрамсона, станция не может начинать передачу сразу после ввода пользователем строки.
Вместо этого она должна дождаться начала новоготакта. Таким образом, система ALOHA с непрерывным временем превращается в дискретную. Уязвимый временной интервал теперь становится в два раза короче. Чтобыпонять это, взгляните на рис. 4.3 и представьте, какие теперь возможны коллизии.Вероятность отсутствия передачи по каналу за тот же интервал времени, в течениекоторого передается тестовый кадр, равна e–G. В результате получаем:S = Ge–G.(4.3)290 Глава 4. Подуровень управления доступом к средеКак видно из рис. 4.3, дискретная система ALOHA имеет пик при G = 1. При этомпроизводительность канала составляет S = 1/e, что приблизительно равно 0,368, тоесть в два раза больше, чем в чистой системе ALOHA.
Если система работает приусловии G = 1, то вероятность появления пустого слота равна 0,368 (из выражения 4.2). Для дискретной системы ALOHA в оптимальной ситуации 37 % интерваловбудут пустыми, 37 % — с успешно переданными кадрами и 26 % — со столкнувшимисякадрами. При увеличении количества попыток передачи в единицу времени G количество пустых интервалов уменьшается, но увеличивается количество конфликтныхинтервалов.
Чтобы увидеть, насколько быстро растет количество конфликтных интервалов, рассмотрим передачу тестового кадра. Вероятность того, что он избежитстолкновения, равна e–G. Фактически это вероятность того, что все остальные станциибудут молчать в течение данного тактового интервала. Таким образом, вероятностьстолкновения равна 1 – e–G. Вероятность передачи кадра ровно за k попыток (то естьпосле k – 1 столкновения, за которыми последует успешная передача) равна:Pk = e–G(1 – e–G)k–1.Ожидаемое число попыток передачи для одной строки, введенной на терминале,равно:E="# kPk =k !1"#k ek!G(1 ! e !G )k !1 = eG .k!1Поскольку число попыток передачи для одного кадра E экспоненциально зависитот количества попыток передачи в единицу времени G, небольшое увеличение нагрузки в канале может сильно снизить его производительность.Дискретная система ALOHA чрезвычайно важна по одной причине, которая напервый взгляд не кажется очевидной.
Она появилась в 1970-х годах, применяласьв некоторых экспериментальных системах, затем была почти забыта. Когда былизобретен метод доступа в Интернет по кабельным сетям, вновь возникла проблемараспределения единственного канала между большим числом конкурирующих абонентов.
Тогда с полок достали запыленные описания дискретной системы ALOHA.Позднее в ситуации, когда несколько тегов RFID пытались общаться с однимсчитывателем RFID, возник еще один вариант старой проблемы. Дискретная система ALOHA, приправленная несколькими другими идеями, снова сумела спастиситуацию. Не раз уже было так, что вполне работоспособные протоколы и методыоказывались невостребованными по политическим причинам (например, когдакакая-нибудь крупная компания выражала желание, чтобы все на свете использовали исключительно ее продукцию) или из-за постоянно меняющихся технологий.Однако по прошествии многих лет какой-нибудь мудрый человек вспоминал о существовании одного древнего метода, способного решить современную проблему.По этой причине мы изучим в данной главе ряд элегантных протоколов, которыесейчас широко не используются, но запросто могут оказаться востребованными в будущем, — если, конечно, об их существовании будет знать достаточное количестворазработчиков сетей. Разумеется, мы изучим и многие протоколы, используемыев настоящее время.4.2.
Протоколы коллективного доступа 2914.2.2. Протоколы множественного доступас контролем несущейВ дискретной системе ALOHA максимальный коэффициент использования канала,который может быть достигнут, равен 1/e. Такой скромный результат неудивителен,поскольку станции передают данные, когда хотят, не считаясь с тем, что делают остальные станции. В такой системе неизбежно возникает большое количество коллизий.Однако в локальных сетях можно организовать процесс таким образом, что станциибудут учитывать поведение друг друга. За счет этого можно достичь значения коэффициента использования канала значительно большего, чем 1/e.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
