 |
Методы случайного доступа к сети
|
|
|
|
ОГЛАВЛЕНИЕ
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
. ПОСТАНОВКА ЗАДАЧИ
Цель проектирования и результаты
Спецификация задачи
. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИССЛЕДОВАНИЯ
. Протоколы канального уровня
Методы случайного доступа к сети
Чистая Алоха
Синхронная Алоха
. ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ
. АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ
ВВЕДЕНИЕ
В век компьютерных технологий и систем, когда компьютеры приходят на производство и в каждый дом, все более актуальной становится задача объединения нескольких компьютерных систем в одно логическое целое.
Объединение компьютеров в распределительную систему позволяет в несколько раз повысить эффективность их работы. Объединение ресурсов нескольких машин позволяет решать такие обширные и важные по своей сути практические задачи, которые невозможно выполнить на единичной машине из-за её ограниченности.
В процессе создания подобных систем возникает необходимость организовать общение между компьютерами - процесс, позволяющий обмениваться пакетами данных между машинами.
Можно сказать, эта задача успешно выполняется и на данный момент существует несколько методов обмена пакетами сообщений.
Целью данной исследовательской работы является сравнительный анализ двух из этих способов: методов чистой и синхронной Алохи.
В процессе исследования требуется алгоритмизировать данные методы и, составить программные модели. На основе результатов работы программных моделей провести анализ производительность каждого из способов.
ПОСТАНОВКА ЗАДАЧИ
Цель проектирования и результаты
В ходе исследования требуется разработать программу, моделирующую работу методов случайного доступа к каналу передачи данных в локальных вычислительных сетях: чистая и синхронная Алоха. Обработать наборы из 100, 1000 и 10000 кадров.
|
|
|
Исходными данными являются:
величины нормированной пропущенной нагрузки 0,075; 0,25 и 1,6.
величины временных интервалов 2, 5, 16.
Выходными данными являются:
Время, необходимое для передачи всего набора кадров;
среднее время, необходимое для передачи кадра;
нормированная производительность протокола передачи;
количество коллизий.
Все результаты исследования оформляются в виде таблиц, строятся графики зависимости производительности от пропущенной нагрузки. Результаты по двум методам сравниваются между собой и с теоретическими результатами. Делается завершающий анализ производительности методов Алоха и всей работы.
Спецификация задачи
Вся особенность данного проектирования заключается в том, что в действительности в работе не используется локально-вычислительная сеть. Нет ни канала передачи данных, ни компьютеров между которыми они должны передаваться. Все исследования проводятся на основе алгоритмизированной и запрограммированной математической модели. В ходе исследования могут допускаться не влияющие на результат округления и допущения.
Несущественные факторы не учитываются или их влияние на процесс передачи кадров считается близким к нулевому результату.
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИССЛЕДОВАНИЯ
Протоколы канального уровня
В последнее время международным стандартом становится протокол ВУК (высокоскоростное управление каналом передачи данных, HDLC). Стандартный формат кадра ВУК изображен на рисунке 2.1.
(флаг) 8 разрядов 8 разрядов 16 разрядов (флаг)
01111110
Рисунок 2.1 - Формат кадра ВУК
В начале и конце кадра для установления и поддержания синхронизации применяется восьмиразрядная последовательность 01111110, называемая флагом, или меткой. Поскольку в начале и в конце кадра применяются флаги, в установке структуры информационного поля нет необходимости. Пакет, поступающий от вышестоящего сетевого уровня, может занимать любое желаемое число разрядов. Проверочное поле занимает 16 разрядов, поля адреса, контроля и управления - по 8 разрядов.
|
|
|
Протокол канального уровня реализует соединение между концами каналов, организацию передачи данных по каналу, разъединение каналов.
Следуя концепции многоуровневой архитектуры, стандартизируется применение на каждом уровне архитектуры четырех основных примитивов услуг, чтобы предусмотреть взаимодействие между пользователями услуг на одном уровне и поставщиками услуг на нижестоящем уровне. Эти примитивы являются основными элементами определения обмена между пользователями услуг. К ним относятся:
запрос;
признак;
ответ;
подтверждение.
При работе примитивов два соседних уровня взаимодействуют между собой. Нижние являются поставщиками услуг, верхние - потребителями.
Существует три вида протоколов канального уровня:
протокол с остановками и ожиданием;
протокол с N-возвращениями (с непрерывной передачей);
с выборочной или селективной передачей.
Методы случайного доступа к сети
программа случайный доступ передача
Двумя основными способами доступа к общей среде передачи являются управляемый доступ с применением опроса и случайный доступ. В свою очередь существуют различные типы стратегий случайного доступа.
Методы случайного доступа полностью децентрализованы. Пользователь может передавать когда угодно, лишь с незначительными ограничениями, зависящими от метода доступа.
Из-за случайности моментов времени, в которые пользователи могут решить начать передачу, независимо от метода не исключена возможность того, что два или несколько пользователей могут выйти на связь в пересекающиеся промежутки времени. Это приводит к столкновениям (коллизиям), которые сначала должны быть распознаны, а затем разрешены. При увеличении нагрузки увеличивается и вероятность коллизий, что приводит к возможной неустойчивости работы рассматриваемых механизмов.
|
|
|
В результате производительность ограничивается некоторым максимальным значением, меньшим пропускной способности канала, и это значение в каждом случае зависит от первоначального механизма доступа и алгоритма разрешения коллизий.
Сначала методы случайного доступа были предложены для случаев, когда большое число пользователей пытаются довольно редко передать пачки сообщений или, когда друг с другом связываются небольшое число ЭВМ. Но применимо к производственным процессам, которые требуют строгого управления задержкой доступа, более предпочтителен управляемый доступ. Рассмотрим два простейших типа стратегии случайного доступа: чистую Алоху и синхронную Алоху.
Чистая Алоха
Эта схема сначала была применена для доступа к общему каналу сотрудниками Гавайского университета в начале 1970-х годов. По этой схеме пользователь, желающий передать сообщение, делает это когда угодно. В результате могут наложиться во времени два или несколько сообщений, вызвав столкновение (коллизию).
Распознавание коллизий и сообщение о них пострадавшим пользователям в первоначальной системе Алоха направлялись по радио на центральный пункт. Также это могло осуществляться путем применения положительных подтверждений в сочетании с перерывом. При обнаружении столкновения пострадавшие станции предпринимают попытки повторной передачи потерянного сообщения, но они должны распределять время попыток случайным образом, следуя некоторому алгоритму столкновения нового конфликта.
Стратегия доступа типа Чистой Алохи позволяет добиться производительности самое большее 1/2e» 0,18 пропускной способности канала. Введем сначала некоторые определения. За доступ к каналу состязаются N станций. Станция передает, в среднем, l пакетов в секунду (интенсивность обращений к сети). Величина 1/m представляет собой пропускную способность канала (m) в передаваемых пакетах в секунду. Рассмотрим теперь частный случай, при котором все передаваемые сообщения (пакеты) имеют среднюю длину t, соответствующую m единицам времени передачи. Будем считать, что интенсивность нагрузки S (эквивалентно r - нормированной по m нагрузке) характеризует использование канала вновь поступающими пакетами
|
|
|
(1)
Величина 1/τ, которая обозначается µ, представляет собой пропускную способность канала в передаваемых пакетах в секунду. Таким образом, Nλ/µ = Nλm - относительное использование канала, или производительность, нормированная относительно каждого компьютера одинакова. Общая интенсивность пакетов, передаваемых в канал, включая вновь генерируемые и передаваемые повторно, имеет некоторое значение λ' > λ. Это происходит, потому что из-за коллизий от каждого компьютера будет передаваться больше сообщений из-за необходимости возобновлять поток. Тогда фактическая интенсивность нагрузки, или использование канала, является параметром G, который равен:
(2)
Рассмотрим типичное сообщение длительностью с, показанное на рис. 2.2.
Рисунок 2.2. Столкновение двух сообщений
Оно подвергается столкновению с другим сообщением, если эти два сообщения будут наложены одно на другое в любой точке. Легко заметить, передвигая пунктирное сообщение во времени, что столкновение может произойти в промежутке времени продолжительностью 2τс. Вероятность того, что в промежутке 2τ с не произойдет столкновения, равна
(3)
Отношение S/G представляет долю сообщений из числа передаваемых в канал, которые проходят успешно. Это число должно быть равно вероятности отсутствия столкновений. Таким образом, уравнение производительности для чистой Алохи:
(4)
Здесь S - нормированная производительность (средняя скорость поступления пакетов, деленная на максимальную производительность 1/m), а G - нормированная пропущенная нагрузка. Таким образом, S - независимая переменная, а G - ее функция. График зависимости G от S имеет вид двузначной кривой (рисунок 2.3).
Рисунок 2.3. Характеристика производительности. Чистая Алоха
Отметим, что S имеет максимум S = 0,5e-1» 0,18 при G = 0.5. Судя по формуле (4) или кривой при малой поступающей нагрузке S столкновения происходят редко, и G à S. Когда S начинает расти, приближаясь к максимальному значению 0.18, число столкновений быстро увеличивается, что ведет в свою очередь к росту вероятности столкновения. Система теряет устойчивость, S падает, а G увеличивается до больших значений.
Синхронная Алоха
Максимально возможная производительность схемы чистой Алохи может быть удвоена с помощью простого приема разметки шкалы времени, и разрешения пользователям начинать попытки передачи сообщений только в начале каждого временного интервала m (равного длительности сообщения). Эта схема требует, чтобы работа всех пользователей системы была синхронизирована во времени. Пример работы такой системы показан на рисунке 2.4, на котором одно сообщение передано успешно, а с другим произошло столкновение.
|
|
|
Рис 2.4. Передача при синхронной Алохе
Поскольку сообщения могут быть переданы только в размеченные промежутки времени, столкновения происходят лишь, когда одна или несколько попыток передачи совершаются в том же промежутке.
Вероятность успешной передачи задается в видеформулы:
(5)
а производительность для синхронной Алохи рассчитывается по формуле:
(6)
Нормированная производительность S достигает максимального значения 1/e à 0,368 при G = 1. Зависимость пропущенной нагрузки от производительности для синхронной Алохи показана на рисунке 2.5, где она сравнивается с соответствующей зависимостью для чистой Алохи.
Рис. 2.5. Характеристика производительности. Синхронная Алоха
Из приведенной характеристики, очевидно, что ввиду двух возможных значений G при заданной производительности S, для этой системы доступа также характерна неустойчивость.
|
|
|
