Лекции 2010-го года (1130544), страница 41
Текст из файла (страница 41)
Предположим, что у нас есть канал со скоростьюС бит/сек., средняя скорость поступления кадров в который равна λ кадров в секунду, асредняя длина кадра имеет экспоненциальное распределение со средним 1/μ бит/кадр.Тогда теория массового обслуживания или, как ее еще называют, теория очередей даетнам следующее соотношение:Теперь разделим канал на N подканалов, каждый со скоростью C/N бит/сек.
Скоростьпоступления кадров в каждом из подканалов будет теперь λ/N. Другими словами, чтовыгоднее иметь N разных очередей, каждую из которых надо обслуживать медленно илиодну, которую надо обслуживать быстро. Соответственно, получаем:Отсюда видно, что в сделанных предположениях частотное разделение в N раз хуже посравнению с тем, как если бы все кадры были бы распределены из единой очереди.Те же самые рассуждения можно применить и к временному разделению. Если каждомупользователю выделить свой слот и тот его не использует, то это пустая трата пропускнойспособности канала. Таким образом, ни один из известных статических методов непозволяет эффективно распределять нагрузку.
Поэтому мы сосредоточимся надинамических методах распределения доступа к каналу.4.1.2. Динамическое предоставление каналаПрежде чем перейти к описанию многочисленных динамических способовпредоставления доступа к каналу, сформулируем основные пять предположений, которыеи будут составлять основу моделей, которые мы будем использовать при оценке этихспособов:1.Станции.
Модель состоит из N независимых станций (компьютеров, телефонов,факс-машин и т.п.). На каждой работает пользователь или программа, которыегенерируют кадры для передачи. Вероятность появления кадра в интервале длины Δtравна λΔt, где λ - константа и 0<λ<1. Предполагается, что если кадр сгенерирован, тостанция блокируется, и новый кадр не появится, пока не будет передан первый. Этопредположение означает, что станции независимы, и на каждой работает только однапрограмма или пользователь, которые генерируют нагрузку с постоянной скоростью.2.Единственность канала. Канал один и он доступен всем станциям.
Все станцииравноправны. Они получают кадры и передают кадры только через этотединственный канал. Аппаратные средства всех станций для доступа к каналуодинаковы, но программно можно устанавливать станциям приоритеты.3.Коллизии. Если две станции передают кадры в одно и то же время, то сигналынакладываются и разрушаются. Этот случай будем называть коллизией. Любаястанция может обнаружить коллизию. Кадры, разрушенные при коллизии, должныбыть посланы повторно позднее.
Кроме коллизий, других ошибок передачи нет.54.Время. Мы будем предполагать две модели времени – непрерывное время идискретное время.A. Непрерывное время. Передача кадра может начаться в любой момент. Нет единыхчасов в системе, которые разбивают время на слоты.B. Дискретное время. В слоте может оказаться 0 кадров, если это слот ожидания, 1кадр - если в этом слоте передача кадра прошла успешно, несколько кадров, если вэтом слоте произошла коллизия.5.Доступ к каналу: возможны два способа доступа станции к каналу.A. С обнаружением несущей. Станция, прежде чем использовать канал, всегдаопределяет, занят он или нет.
Если он занят, то станция не начинает передачу.B. Отсутствие несущей. Станция ничего не знает о состоянии канала, пока не начнетиспользовать его. Она сразу начинает передачу и лишь позднее обнаруживаетколлизию.Есть и другие модели, которые предусматривают многопользовательские станции, но этимодели намного сложнее. Единый канал передачи - это краеугольное предположение.Иного способа передать кадр нет - только по каналу.Раздел 4.2. Протоколы множественного доступа.4.2.1. ALOHAВ 70-х годах Норман Абрамсон (Norman Abramson) со своими коллегами из университетаГавайи предложил простой способ распределения доступа к каналу.
Абрамсон назвалсистему, реализующую этот способ распределения канала, ALOHA, что по-гавайскиозначает что-то вроде «привет». Система состояла из наземных радиостанций,связывающих острова между собой. Идея была позволить в вещательной среде любомуколичеству пользователей неконтролируемо использовать один и тот же канал.Мы здесь рассмотрим два варианта системы: чистая ALOHA и слотированная ALOHA,т.е.
разбитая на слоты. Основное различие - в первом случае никакой синхронизациипользователей не требуется, во втором она нужна.4.2.1.1. Чистая ALOHAИдея чистой ALOHA проста - любой пользователь, желающий передать сообщение, сразупытается это сделать. Благодаря тому, что в вещательной среде он всегда имеет обратнуюсвязь, т.е. может определить, пытался ли кто-то еще передавать на его частоте, то онможет установить возникновение конфликта при передаче. Такая обратная связь в средеLAN происходит практически мгновенно, в системах спутниковой связи задержкасоставляет около 270 мсек. Обнаружив конфликт, пользователь ожидает некоторыйслучайный отрезок времени, после чего повторяет попытку.
Интервал времени наожидание должен быть случайным, иначе конкуренты будут повторять попытки в одно ито же время, что приведет к их блокировке. Системы подобного типа, где пользователиконкурируют за получение доступа к общему каналу, называются системами ссостязаниями.6Не важно, когда произошел конфликт: когда первый бит одного кадра «наехал» напоследний бит другого кадра или как-то иначе, оба кадра считаются испорченными идолжны быть переданы повторно. Контрольная сумма, защищающая данные в кадре, непозволяет различать разные случаи наложения кадров.Какова эффективность системы 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 (рисунок 41).Рисунок 4-1. Время, требуемое на обнаружение коллизииВероятность появления k кадров при передаче кадра при распределении Пуассона равна7поэтому вероятность, что появится 0 кадров, равна e-G.За двойное время кадра среднее число кадров будет равна 2G, отсюдаP0=e-2Gа так как S=GP0, то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.8Рассмотрим, как G влияет на пропускную способность.
Для этого подсчитаем вероятностьуспешной передачи кадра за k попыток. Так как e-G - вероятность отсутствия коллизии припередаче, то вероятность, что кадр будет передан ровно за k попыток, равнаPk=e-G(1-e-G)k-1Среднее ожидаемое число повторных передач будет равноЭта экспоненциальная зависимость показывает, что с ростом G резко возрастает числоповторных попыток. Поэтому незначительное увеличение загрузки канала ведет к резкомупадению пропускной способности.4.2.2. Протоколы множественного доступа с обнаружениемнесущейМаксимальная пропускная способность, какую мы можем получить для системы ALOHA,достигается при S=1/е. Это не удивительно, так как в этих системах станция не обращаетвнимания на то, что делают другие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
