Полный курс лекций 2009-го года (1130357), страница 41
Текст из файла (страница 41)
Таким образом, ни один из известных статических методов не позволяет эффективно распределятьнагрузку. Поэтому мы сосредоточимся на динамических методах распределения доступа к каналу.4.1.2. Динамическое предоставление каналаПрежде чем перейти к описанию многочисленных динамических способов предоставления доступа кканалу, сформулируем основные пять предположений, которые и будут составлять основу моделей,которые мы будем использовать при оценке этих способов:1.Станции. Модель состоит из N независимых станций (компьютеров, телефонов, факс-машин и т.п.). Накаждой работает пользователь или программа, которые генерируют кадры для передачи. Вероятностьпоявления кадра в интервале длины D t равна lD t, где l - константа и 0 < l < 1.
Предполагается, что есликадр сгенерирован, то станция блокируется, и новый кадр не появится, пока не будет передан первый. Этопредположение означает, что станции независимы, и на каждой работает только одна программа илипользователь, которые генерируют нагрузку с постоянной скоростью.2.Единственность канала. Канал один и он доступен всем станциям.
Все станции равноправны. Ониполучают кадры и передают кадры только через этот единственный канал. Аппаратные средства всехстанций для доступа к каналу одинаковы, но программно можно устанавливать станциям приоритеты.3.Коллизии. Если две станции передают кадры в одно и то же время, то сигналы накладываются иразрушаются. Этот случай будем называть коллизией.
Любая станция может обнаружить коллизию. Кадры,разрушенные при коллизии, должны быть посланы повторно позднее. Кроме коллизий, других ошибокпередачи нет.4.Время. Мы будем предполагать две модели времени – непрерывное время и дискретное время.A.Непрерывное время. Передача кадра может начаться в любой момент. Нет единых часов в системе,которые разбивают время на слоты.B.Дискретное время. В слоте может оказаться 0 кадров, если это слот ожидания, 1 кадр - если в этомслоте передача кадра прошла успешно, несколько кадров, если в этом слоте произошла коллизия.5.Доступ к каналу: возможны два способа доступа станции к каналу.A.С обнаружением несущей. Станция, прежде чем использовать канал, всегда определяет, занят он илинет.
Если он занят, то станция не начинает передачу.B.Отсутствие несущей. Станция ничего не знает о состоянии канала, пока не начнет использовать его.Она сразу начинает передачу и лишь позднее обнаруживает коллизию.Есть и другие модели, которые предусматривают многопользовательские станции, но эти моделинамного сложнее. Единый канал передачи - это краеугольное предположение. Иного способапередать кадр нет - только по каналу.4.2.1. ALOHAВ 70-х годах Норман Абрамсон (Norman Abramson) со своими коллегами из университета Гавайипредложил простой способ распределения доступа к каналу.
Абрамсон назвал систему, реализующую этотспособ распределения канала, ALOHA, что по-гавайски означает что-то вроде «привет». Система состоялаиз наземных радиостанций, связывающих острова между собой. Идея была позволить в вещательной сределюбому количеству пользователей неконтролируемо использовать один и тот же канал.Мы здесь рассмотрим два варианта системы: чистая ALOHA и слотированная ALOHA, т.е. разбитая наслоты. Основное различие - в первом случае никакой синхронизации пользователей не требуется, вовтором она нужна.4.2.1.1. Чистая ALOHAИдея чистой ALOHA проста - любой пользователь, желающий передать сообщение, сразу пытаетсяэто сделать. Благодаря тому, что в вещательной среде он всегда имеет обратную связь, т.е. можетопределить, пытался ли кто-то еще передавать на его частоте, то он может установить возникновениеконфликта при передаче.
Такая обратная связь в среде LAN происходит практически мгновенно, всистемах спутниковой связи задержка составляет около 270 мсек. Обнаружив конфликт, пользовательожидает некоторый случайный отрезок времени, после чего повторяет попытку. Интервал времени наожидание должен быть случайным, иначе конкуренты будут повторять попытки в одно и то же время, чтоприведет к их блокировке.
Системы подобного типа, где пользователи конкурируют за получение доступак общему каналу, называются системами с состязаниями.Не важно, когда произошел конфликт: когда первый бит одного кадра «наехал» на последний битдругого кадра или как-то иначе, оба кадра считаются испорченными и должны быть переданы повторно.Контрольная сумма, защищающая данные в кадре, не позволяет различать разные случаи наложениякадров.Какова эффективность системы ALOHA, измеренная в количестве кадров, которые избежаликоллизий? Для ответа на этот вопрос рассмотрим следующую модель. Для ответа на эти вопросырассмотрим следующую модель. Есть неограниченное число пользователей, работающих на компьютерах.Все что они могут делать, - это либо набирать текст, либо ждать, пока набранный текст будет передан.Когда пользователь заканчивает набирать очередную строку, он останавливается и ждет ответа отсистемы.
Система пытается передать эту строку. Когда она сделает это, пользователь видит отклик иможет продолжать работу.Назовем временем кадра время, необходимое на передачу кадра стандартной фиксированной длины.Предполагаем, что число пользователей неограниченно, и они порождают кадры по закону Пуассона сосредним S кадров за время кадра. Поскольку при S>1 очередь на передачу будет только расти и всекадры будут страдать от коллизий, то мы будем предполагать 0<S<1.Также будем предполагать, что вероятность за время кадра сделать k попыток передачираспределена по закону Пуассона со средним G. Понятно, что должно быть GіS, иначе очередь будет растибесконечно.
При слабой загрузке (S»0) будет мало передач, а следовательно и коллизий, поэтомудопустимо G»S. При высокой загрузке должно быть G>S. При любой нагрузке пропускная способность это- число кадров, которые надо передать, умноженное на вероятность успешной передачи. Если обозначитьP0 вероятность отсутствия коллизий при передаче кадра, то S=GP0.Рассмотрим внимательно, сколько времени нужно отправителю, чтобы обнаружить коллизию. Пустьон начал передачу в момент времени t0 и пусть требуется время t, чтобы кадр достиг самой отдаленнойстанции. Тогда, если в тот момент, когда кадр почти достиг этой отдаленной станции, она начнет передачу(ведь в системе ALOHA станция сначала передает, а потом слушает), то отправитель узнает об этом толькочерез t0 + 2t (рисунок 4-1).Рисунок 4-1. Время, требуемое на обнаружение коллизииВероятность появления k кадров при передаче кадра при распределении Пуассона равнапоэтому вероятность, что появится 0 кадров, равна e-G.За двойное время кадра среднее число кадров будет равна 2G, отсюдаP0 = e-2Gа так как S = G P0, тоS = Ge-2GЗависимость между нагрузкой и пропускной способностью показана на рисунке 4-2 (нижнийграфик).
Максимальная пропускная способность достигается при G = 0,5 при S = 1 / 2e, что составляетпримерно 18% от номинальной пропускной способности. Это означает, что если мы будем генерироватькадры с большей скоростью, чем 18% от скорости канала, то очереди переполнятся и система«захлебнется». Результат не очень вдохновляющий, но это плата за удобство: каждый передает, когдазахочет.Рисунок 4-2.
Зависимость между нагрузкой и пропускной способностьюсистемы ALOHA4.2.1.2. Слотированная ALOHAВ 1972 году Робертс (Roberts) предложил модификацию чистой ALOHA. Все время работы каналаразделяют на слоты. Размер слота определяют так, чтобы он был равен максимальному времени кадра.Ясно, что такая организация работы канала требует синхронизации. Кто-то, например, одна из станцийиспускает сигнал начала очередного слота. Поскольку передачу теперь можно начинать не в любоймомент, а только по специальному сигналу, то время на обнаружение коллизии сокращается вдвое. ОтсюдаS = Ge-GКак видно из рисунка 4-3, максимум пропускной способности слотированной ALOHA наступает приG= 1, где S= 1/e, т.е.
около 0,37, что вдвое больше, чем у чистой ALOHA.Рассмотрим, как G влияет на пропускную способность. Для этого подсчитаем вероятность успешнойпередачи кадра за k попыток. Так как e-G - вероятность отсутствия коллизии при передаче, то вероятность,что кадр будет передан ровно за k попыток, равнаPk = e-G (1 - e-G) k-1Среднее ожидаемое число повторных передач будет равноЭта экспоненциальная зависимость показывает, что с ростом G резко возрастает число повторныхпопыток.
Поэтому незначительное увеличение загрузки канала ведет к резкому падению пропускнойспособности.4.2.2. Протоколы множественного доступа с обнаружением несущейМаксимальная пропускная способность, какую мы можем получить для системы ALOHA, достигаетсяпри S = 1 / е. Это не удивительно, так как в этих системах станция не обращает внимания на то, что делаютдругие. Поэтому вероятность коллизии чрезвычайно высока. В локальных сетях есть возможностьопределить, что делают другие станции, и только после этого решать, что делать самому.Протоколы, которые реализуют именно эту идею – сначала определить, занят канал или нет и толькопосле этого действовать - называются протоколами с обнаружением несущей CSMA (Carrier SensitiveMultiple Access).4.2.2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
