Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 25)

Самое трудное - выделить кадр из потока битов. На уровне битов ячейка - это 53х8 = 424 бита. Нет маркеров ни начала, ни конца кадра. Как определить границы кадра?

На ТС-подуровне есть сдвиговый регистр на 40 бит. Если в этих 40 бит правые 8 представляют собой НЕС, то последующие 32 левых бита - заголовок ячейки. Если условие не выполнено, то все сдвигается на один бит и проверка повторяется. Этот процесс продолжается до тех пор, пока не будет обнаружен НЕС.

Схема распознавания в том виде, как она описана не надежна. Вероятность того, что случайный байт будет выглядеть как НЕС, равна 1/256. Чтобы исправить эту схему, используют автомат, схема состояний которого изображена на рисунке 3-24. Есть три состояния: HUNT, PRESYNCH, SYNCH. В состоянии HUNT ищется НЕС. Как только найден похожий байт, автомат переходит в состояние PRESYNCH и отчитывает следующие 53 байта. Если предположение о том, что найденный НЕС - начало ячейки, то сдвиг на 53 байта приведет к следующему НЕС. Происходит проверка последовательно δ ячеек, после этого происходит переход в состояние SYNCH.

Если в состоянии SYNCH α последовательных ячеек оказались плохими, происходит переход в состояние HUNT.

Рисунок 3-24. Процедура поиска ячеек

37. Протоколы множественного доступа к каналу (динамическое vs статическое выделение канала). Модель системы ALOHA. Сравнение производительности систем: чистая ALOHA, слотированная ALOHA. Протоколы множественного доступа с обнаружением несущей (настойчивые и не настойчивые CSMA, CSMA с обнаружением коллизий).

В средах с множественным доступом ключевым является вопрос: как определить, кому из абонентов, запросивших канал, предоставить право пользоваться этим каналом? Протоколы для решения этой проблемы составляют основу этой главы. Эти протоколы относятся к подуровню канального уровня, который называется подуровнем доступа к среде или МАС - Medium Access Control подуровнем канального уровня. Выше этого подуровня действуют все те протоколы, о которых мы говорили в предыдущей главе. Протоколы этого подуровня регулируют доступ к каналу при наличии нескольких абонентов.

Раздел 4.1. Проблема предоставления канала

4.1.1. Статическое предоставление канала

Есть два основных подхода к мультиплексированию нескольких конкурирующих пользователей на одном канале - частотное разделение (FDM) и временное разделение (TDM). Частотное разделение хорошо работает в условиях, когда число пользователей фиксировано, и каждый порождает плотную загрузку канала. Тогда каждому из них выделяется своя полоса частот, которую он использует независимо от других.

Однако, когда число пользователей велико, их число меняется или трафик отдельных пользователей не регулярный, у FDM появляются проблемы. Если весь диапазон разделить на N полос и лишь немногим из N потребуется передача, то большая часть пропускной способности не будет использована. Если число пользователей, кому необходимо передать данные, больше N, и мы жестко зафиксируем расписание доступа пользователей к каналу, то часть из них получит отказ из-за недостатка пропускной способности, хотя часть тех, кому канал будет предоставлен, может ничего не передавать или не принимать.

Таким образом, статическое разделение канала на подканалы является неэффективным решением при предположении о постоянстве числа пользователей в среднем. Положение усугубляет то обстоятельство, что трафик в сетях, как правило, носит взрывной характер.

Ни один из известных статических методов не позволяет эффективно распределять нагрузку.

4.1.2. Динамическое предоставление канала

Основные предположения, которые и будут составлять основу моделей, которые мы будем использовать при оценке способов динамического предоставления канала:

1. Станции. Модель состоит из N независимых станций (компьютеров, телефонов, факс-машин и т.п.). На каждой работает пользователь или программа, которые генерируют кадры для передачи. Вероятность появления кадра в интервале длины Δt равна λΔt, где λ - константа и 0<λ<1. Предполагается, что если кадр сгенерирован, то станция блокируется, и новый кадр не появится, пока не будет передан первый. Это предположение означает, что станции независимы, и на каждой работает только одна программа или пользователь, которые генерируют нагрузку с постоянной скоростью.

1. Единственность канала. Канал один и он доступен всем станциям. Все станции равноправны. Они получают кадры и передают кадры только через этот единственный канал. Аппаратные средства всех станций для доступа к каналу одинаковы, но программно можно устанавливать станциям приоритеты.

1. Коллизии. Если две станции передают кадры в одно и то же время, то сигналы накладываются и разрушаются. Этот случай будем называть коллизией. Любая станция может обнаружить коллизию. Кадры, разрушенные при коллизии, должны быть посланы повторно позднее. Кроме коллизий, других ошибок передачи нет.

1. Время. Мы будем предполагать две модели времени – непрерывное время и дискретное время.

1. Непрерывное время. Передача кадра может начаться в любой момент. Нет единых часов в системе, которые разбивают время на слоты.

1. Дискретное время. В слоте может оказаться 0 кадров, если это слот ожидания, 1 кадр - если в этом слоте передача кадра прошла успешно, несколько кадров, если в этом слоте произошла коллизия.

1. Доступ к каналу: возможны два способа доступа станции к каналу.

1. С обнаружением несущей. Станция, прежде чем использовать канал, всегда определяет, занят он или нет. Если он занят, то станция не начинает передачу.

1. Отсутствие несущей. Станция ничего не знает о состоянии канала, пока не начнет использовать его. Она сразу начинает передачу и лишь позднее обнаруживает коллизию.

Единый канал передачи - это краеугольное предположение. Иного способа передать кадр нет - только по каналу.

ALOHA.

В 70-х годах Норман Абрамсон (Norman Abramson) со своими коллегами из университета Гавайи предложил простой способ распределения доступа к каналу. Абрамсон назвал систему, реализующую этот способ распределения канала, ALOHA, что по-гавайски означает что-то вроде «привет». Система состояла из наземных радиостанций, связывающих острова между собой. Идея была позволить в вещательной среде любому количеству пользователей неконтролируемо использовать один и тот же канал.

Мы здесь рассмотрим два варианта системы: чистая ALOHA и слотированная ALOHA, т.е. разбитая на слоты. Основное различие - в первом случае никакой синхронизации пользователей не требуется, во втором она нужна.

Чистая ALOHA.

Идея чистой ALOHA проста - любой пользователь, желающий передать сообщение, сразу пытается это сделать. Благодаря тому, что в вещательной среде он всегда имеет обратную связь, т.е. может определить, пытался ли кто-то еще передавать на его частоте, то он может установить возникновение конфликта при передаче. Такая обратная связь в среде LAN происходит практически мгновенно, в системах спутниковой связи задержка составляет около 270 мсек. Обнаружив конфликт, пользователь ожидает некоторый случайный отрезок времени, после чего повторяет попытку. Интервал времени на ожидание должен быть случайным, иначе конкуренты будут повторять попытки в одно и то же время, что приведет к их блокировке. Системы подобного типа, где пользователи конкурируют за получение доступа к общему каналу, называются системами с состязаниями.

Не важно, когда произошел конфликт: когда первый бит одного кадра «наехал» на последний бит другого кадра или как-то иначе, оба кадра считаются испорченными и должны быть переданы повторно. Контрольная сумма, защищающая данные в кадре, не позволяет различать разные случаи наложения кадров.

Какова эффективность системы ALOHA, измеренная в количестве кадров, которые избежали коллизий? Для ответа на этот вопрос рассмотрим следующую модель. Есть неограниченное число пользователей, работающих на компьютерах. Все что они могут делать, - это либо набирать текст, либо ждать, пока набранный текст будет передан. Когда пользователь заканчивает набирать очередную строку, он останавливается и ждет ответа от системы. Система пытается передать эту строку. Когда она сделает это, пользователь видит отклик и может продолжать работу.

Назовем временем кадра время, необходимое на передачу кадра стандартной фиксированной длины. Предполагаем, что число пользователей неограниченно, и они порождают кадры по закону Пуассона со средним S кадров за время кадра. Поскольку при S>1 очередь на передачу будет только расти и все кадры будут страдать от коллизий, то мы будем предполагать 0<S<1.

Также будем предполагать, что вероятность за время кадра сделать k попыток передачи распределена по закону Пуассона со средним G. Понятно, что должно быть GіS, иначе очередь будет расти бесконечно. При слабой загрузке (S»0) будет мало передач, а следовательно и коллизий, поэтому допустимо G»S. При высокой загрузке должно быть G>S. При любой нагрузке пропускная способность это - число кадров, которые надо передать, умноженное на вероятность успешной передачи. Если обозначить P0 вероятность отсутствия коллизий при передаче кадра, то S=GP0.

Рассмотрим внимательно, сколько времени нужно отправителю, чтобы обнаружить коллизию. Пусть он начал передачу в момент времени t₀ и пусть требуется время t, чтобы кадр достиг самой отдаленной станции. Тогда, если в тот момент, когда кадр почти достиг этой отдаленной станции, она начнет передачу (ведь в системе ALOHA станция сначала передает, а потом слушает), то отправитель узнает об этом только через t₀+2t (рисунок 4-1).

Рисунок 4-1. Время, требуемое на обнаружение коллизии

Вероятность появления k кадров при передаче кадра при распределении Пуассона равна

поэтому вероятность, что появится 0 кадров, равна e^-G.

За двойное время кадра среднее число кадров будет равна 2G, отсюда

P₀=e^-2G

а так как S=GP₀, то

S=Ge^-2G

Зависимость между нагрузкой и пропускной способностью показана на рисунке 4-3. Максимальная пропускная способность достигается при G=0,5 при S=1/2e, что составляет примерно 18% от номинальной пропускной способности. Это означает, что если мы будем генерировать кадры с большей скоростью, чем 18% от скорости канала, то очереди переполнятся и система «захлебнется». Результат не очень вдохновляющий, но это плата за удобство: каждый передает, когда захочет.

Слотированная ALOHA.

В 1972 году Робертс (Roberts) предложил модификацию чистой ALOHA. Все время работы канала разделяют на слоты. Размер слота определяют так, чтобы он был равен максимальному времени кадра. Ясно, что такая организация работы канала требует синхронизации. Кто-то, например, одна из станций испускает сигнал начала очередного слота. Поскольку передачу теперь можно начинать не в любой момент, а только по специальному сигналу, то время на обнаружение коллизии сокращается вдвое. Отсюда

S=Ge^-G

Как видно из рисунка 4-3, максимум пропускной способности слотированной ALOHA наступает при G=1, где S=1/e, т.е. около 0,37, что вдвое больше, чем у чистой ALOHA.

Рассмотрим, как G влияет на пропускную способность. Для этого подсчитаем вероятность успешной передачи кадра за k попыток. Так как e^-G - вероятность отсутствия коллизии при передаче, то вероятность, что кадр будет передан ровно за k попыток, равна

P_k=e^-G(1-e^-G)^k-1

Среднее ожидаемое число повторных передач будет равно

Эта экспоненциальная зависимость показывает, что с ростом G резко возрастает число повторных попыток. Поэтому незначительное увеличение загрузки канала ведет к резкому падению пропускной способности.

Протоколы множественного доступа с обнаружением несущей.

В локальных сетях есть возможность определить, что делают другие станции, и только после этого решать, что делать самому. Протоколы, которые реализуют именно эту идею – сначала определить, занят канал или нет и только после этого действовать - называются протоколами с обнаружением несущей CSMA (Carrier Sensitive Multiple Access).

Настойчивые и ненастойчивые CSMA-протоколы.

Согласно протоколу, который мы сейчас рассмотрим, станция, прежде чем что-либо передавать, определяет состояние канала. Если канал занят, то она ждет. Как только канал освободился, она пытается начать передачу. Если при этом произошла коллизия, она ожидает случайный интервал времени и все начинает с начала. Этот протокол называется настойчивым CSMA-протоколом первого уровня или 1-настойчивым CSMA-протоколом, потому что станция, следуя этому протоколу, начинает передачу с вероятностью 1, как только обнаруживает, что канал свободен.

Здесь важную роль играет задержка распространения сигнала в канале. Всегда есть шанс, что, как только одна станция начала передачу, другая также стала готовой передавать. Если вторая станция проверит состояние канала прежде, чем до нее дойдет сигнал от первой о том, что она заняла канал, то вторая станция сочтет канал свободным и начнет передачу. В результате - коллизия. Чем больше время задержки, тем больше вероятность такого случая, тем хуже производительность канала.

Однако даже если время задержки будет равно 0, коллизии все равно могут возникать. Например, если готовыми передавать оказались две станции, пока одна станция продолжает передавать. Они вежливо подождут, пока первая закончит передачу, а потом будут состязаться между собой. Тем не менее, этот протокол более эффективен, чем любая из систем ALOHA, так как станция учитывает состояние канала, прежде чем начать действовать.

Другой вариант CSMA-протокола - ненастойчивый CSMA-протокол. Основное отличие его от предыдущего в том, что готовая к передаче станция опрашивает канал. Если он свободен, то она начинает передачу. Если он занят, то она не будет настойчиво его опрашивать в ожидании, когда он освободится, а будет делать это через случайные отрезки времени. Это несколько увеличивает задержку при передаче, но общая эффективность протокола возрастает.

И, наконец, настойчивый CSMA-протокол уровня р. Он применяется к слотированным каналам. Когда станция готова к передаче, она опрашивает канал. Если он свободен, то она с вероятностью р передает свой кадр и с вероятностью q=1-p ждет следующего слота. Так она действует, пока не передаст кадр. Если произошла коллизия во время передачи, она ожидает случайный интервал времени и опрашивает канал опять. Если при опросе канала он оказался занят, станция ждет начала следующего слота, и весь алгоритм повторяется. На рисунке 4-3 показана пропускная способность этого протокола в зависимости от нагрузки.

Характеристики

Список файлов ответов (шпаргалок)