tanenbaum_seti_all.pages (525408), страница 78
Текст из файла (страница 78)
Средняя входная скорость в каждом подканэле теперь будет равна л/М кадров в секунду. Сосчитав новое значение средней задержки Т, получим: (4.1) р(с/'м) (л/'л~) пс-л Это означает, что при использовании частотного уплотнения значение средней задержки стало в М раз хуже значения, которое было бы в канале, если бы все кадры были каким-то волшебным образом организованы в одну общую очередь, 294 Глава 4.
Подуровень управления доступом к среде Те же самые аргументы применимы и к временному уплотнению (Т()М, Типе 1)1у1э1оп Ми1г1р1ех1пя — мультиплексная передача с временным разделением). Каждому пользователю в данном случае статически выделяется )у'-й интервал времени.
Если интервал не используется абонентом, то он просто пропадает. С тем же успехом можно разделить сети физически. Если взять 100-мегабитную сеть и сделать из нее десять 10-мегабитных, статически распределив по ним пользователей, то в результате средняя задержка возрастет с 200 мкс до 2 мс. Таким образом, ни один статический метод распределения каналов не годится для пульсирующего графика, поэтому далее мы рассмотрим динамические методы. Динамическое распределение каналов в локальных и региональных сетях Прежде чем приступить к рассмотрению многочисленных методов распределения каналов, следует тщательно сформулировать решаемую проблему.
В основе всех разработок в данной области лежат следующие пять допущений. 1. Станционная модель. Модель состоит из У независимых станций (компьютеров, телефонов, персональных средств связи и т. д,), в каждой из которых программа пользователя формирует кедры для передачи. Станции иногда называют терминалами. Вероятность формирования кадра в интервале времени ьг равна оХд где х является константой (скорость прибытия новых кадров). Как только кадр сформирован, станция блокируется и ничего не делает, пока кадр не будет успешно передан.
2. Предположение о едином канале. Единый канал доступен для всех. Все станции могут передавать и принимать данные по нему. С точки зрения аппаратуры все станции считаются равными, хотя программно протокол может устанавливать для них различные приоритеты. 3. Допущение о коллизиях. Если два кадра передаются одновременно, они перекрываются по времени, в результате сигнал искажается. Такое событие называется конфликтом, или коллизией. Все станции могут обнаруживать конфликты, Искаженный вследствие конфликта кадр должен быть передан повторно. Других ошибок, кроме тех, которые вызваны конфликтами, нет. 4а. Непрерывное время. Передача кадров может начаться в любой момент времени.
Не существует никаких синхронизирущих импульсов, которые делили бы время на дискретные интервалы. 46. Дискретное время. Время разделено на дискретные интервалы (такты). Передача кадра может начаться только с началом такта Один временной интервал может содержать О, 1 или более кадров, что соответствует свободному интервалу, успешной передаче кадра или коллизии.
ба. Контроль несущей. Станции могут определить, свободна или занята линия, до ее использования. Если канал занят, станции не будут пытаться передавать кадры по нему, пока он не освободится. Протоколы коллективного доотупв 295 бб. Отсутствие контроля несущей. Станции не могут определить, свободна или занята линия, пока не попытаются ее использовать. Они просто начинают передачу. Только потом они могут определить, была ли передача успешной.
О приведенных ранее допущениях следует сказать несколько слов. Первое допущение утверждает, что станции независимы и работают с постоянной скоростью, Также неявно предполагается, что у каждой станции имеется только один пользователь или программа, поэтому пока станция заблокирована, она не производит никакой работы. Более сложные модели рассматривают многопрограммные станции, которые могут работать в заблокированном состоянии, однако и анализ подобных станций намного сложнее. Допущение о едином канале является, на самом деле, центральным в данной модели.
Никаких внешних каналов связи нет, Станции ие могут тянуть руки, привлекая к себе внимание и убеждая учителя спросить их. Допущение о коллизиях также является основным, хотя в некоторых системах (особенно в системах с расширенным спектром) данное допущение звучит не столь строго, что приводит к неожиданным результатам. Кроме того, в некоторых локальных сетях, например в сети голеи угля (маркерное кольцо), применяется механизм разрешения коллизий, реализуемый за счет специальных пакетов — маркеров, передающихся от станции к станции. Помещать в канал кадр может только тот, у кого в данный момент находится маркер. Далее мы обсудим модель моноканала с конкуренцией и коллизиями.
Для времени существует два альтернативных допущения. В одних системах время может быть непрерывным (4а), в других — дискретным, поэтому мы рассмотрим оба варианта. Аналогично этому, контроль несущей также реализован не во всех системах. Станции локальных сетей обычно знают, когда линия занята, однако в беспроводных сетях контррля несущей нет, потому что отдельно взятая станция не может «слышать» все остальные из-за разницы частотных диапазонов. Станции проводных сетей с контролем несущей могут приостанавливать собственную передачу, обнаружив коллизию. Обратите внимание на слово «несущая».
В данном случае оно означает электрический сигнал, распространяющийся по каналу'. Протоколы коллективного доступа Известно много алгоритмов коллективного доступа, В следующих разделах будут рассмотрены наиболее интересные алгоритмы и даны примеры их применения. Система А1 ОНА В 70-х годах Норман Абрамсон (Хоппап АЬгашзоп) и его коллеги из Гавайского университета разработали новый элегантный метод решения проблемы распределения каналов. Их труды впоследствии стали основой многих исследований г Слою *загнет» («несунгзя») в английском ялике означает также «неревозчнк». — Примеч. зерее.
296 Глава 4. Подуровень управления доступом к среде (АЬгашзоп, 1985). Хотя в работе Абрамсона, получившей название А1.ОНА, использовалась широковещательная радиосвязь со стационарными передатчиками, основная идея применима к любой системе, в которой независимые пользователи соревнуются за право использования одного общего канала. В данной главе мы рассмотрим две версии системы АЕОНА: чистую и дискретную. Они отличаются тем, делится ли время на дискретные интервалы, в течение которых передаются кадры, или нет. В чистой системе АЕОНА не требуется общая синхронизация времени, а в дискретной требуется, Чистая систвма А1.0НА В основе системы А1.ОНА лежит простая идея: разрешить пользователям передачу, как только у них появляются данные для отсылки. Конечно, при этом будут столкновения, и столкнувшиеся кадры будут разрушены. Однако благодаря свойству обратной связи широковещательной системы отправитель всегда может установить, дошел ли его кадр до получателя или был разрушен.
Для этого ему нужно просто прослушивать канал, как это делают все остальные пользователи. В локальных сетях обратная связь мгновенная, а в спутниковых системах существует задержка в 270 мс, и только после этого отправитель может узнать, насколько успешной была передача. Если кадр был уничтожен, отправитель просто выжидает некоторое случайное время и пытается переслать этот кадр снова. Время ожидания должно быть случайным. В противном случае при равных фиксированных интервалах времени ожидания коллизии будут повторяться снова и снова. Системы, в которых несколько пользователей используют один общий канал таким способом, что время от времени возникиот конфликты, называются системами с конкуренцией.
На рис. 4.1 показан пример формирования кадров в системе А1.ОНА. Все кадры на нашем рисунке имеют один размер, так как при этом пропускная способность системы сделана максимальной именно за счет фиксированного размера кадров. А С::~ (:::~ в СЗ с О П (:Л С:1 (:::1 С:1 (:1 С:1 (::1 (:::1 (:Л Время Рис. 4.1. В чистой системе АьОНА кадры передаются в абсолютно произвольное время Когда два кадра одновременно пытаются занять канал, они сталкиваются и уничтожаются.
Даже если только один первый бит второго кадра перекрывается последним битом первого кадра, оба кадра уничтожаются полностью. При этом оба Протоколы коллективного доступа 297 кадра будут переданы позднее повторно. Контрольная сумма не может (и не должна) отличать полную потерю информации от частичной. Потеря есть потеря. Самым интересным в данной ситуации является вопрос об эффективности канала системы АЕОНА. Другими словами, какая часть всех передаваемых кздров способна избежать коллизий при любых обстоятельствах? Сначала рассмотрим бесконечное множество интерактивных пользователей, сидящих за своими компьютерами (станциями).
Пользователь всегда находится в одном из двух состояний: ввод с клавиатуры и ожидание. Вначале все пользователи находятся в состоянии ввода, Закончив набор строки, пользователь перестает вводить текст, ожидая ответа. В это время станция передает кадр, содержащий набранную строку, и опрашивает канал, проверяя успешность передачи кадра.
Если кадр передан успешно, пользователь видит ответ и продолжает набор. В противном случае пользователь ждет, пока кадр не будет передан. Пусть «время кадра» означает интервал времени, требующийся для передачи стандартного кадра фиксированной длины (то есть длину кадра, деленную на скорость передачи данных). На данный момент мы предполагаем, что бесконечное количество пользователей порождает новые кадры, распределенные по Пуассону со следующим средним значением: М кадров за время кадра. (Допущение о бесконечном количестве пользователей необходимо для того, чтобы гарантировать, что величина У не станет уменьшаться по мере блокирования пользователей.) Если Аг > 1, это означает, что сообщество пользователей формирует кадры с большей скоростью, чем может быть передано по каналу, и почти каждый кадр будет страдать от столкновений.
Мы будем предполагать, что 0 < Аг< 1. Помимо новых кадров, станции формируют повторные передачи кадров, пострадавших от столкновений. Допустим также, что вероятность Й попыток передачи старых и новых кадров за время кадра также имеет пуассоновское распределение со средним значением 6 за время кадра. Очевидно, что С~Аг. При малой загрузке канала (то есть при Аг О) столкновений будет мало, поэтому мало будет и повторных передач, то есть СиУ.