Nets2010 (1131259), страница 27

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

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

Рассмотрим подробнее алгоритм состязаний. Сколько времени станции, начавшей передачу, нужно, чтобы определить коллизию? Обозначим через τ время распространения сигнала до самой удаленной станции на линии. Для коаксиала в 1 км τ=5 мксек., в таком случае минимальное время для определения коллизии будет равно 2τ. Поэтому станция не может быть уверена, что она захватила канал до тех пор, пока не убедится, что в течение 2τ секунд не было коллизий. Поэтому мы будем рассматривать период состязаний как слотированную систему ALOHA со слотом 2τ секунд на один бит. Захватив канал, станция может далее передавать кадр с любой скоростью.

Стоит подчеркнуть, что обнаружение коллизий – это аналоговый процесс. Поэтому, чтобы обнаруживать их, нужно использовать специальные кодировки на физическом уровне. Надо также отметить, что МАС-подуровень обеспечивает надежную передачу, используя специальные приемы кодирования данных. Примеры таких кодировок мы рассматривали в гл. 2 (Манчестерские коды).

38. Протоколы множественного доступа к каналу: Бесконфликтные протоколы (Bit-Map протокол, Адресный счетчик). Протоколы с ограниченным числом конфликтов. Протоколы с множественным доступом и разделением частот.

Будем предполагать, что у нас есть N станций с адресами от 0 до N-1. Все адреса уникальны. Основным является вопрос: как определить, кто будет владеть каналом, когда закончится текущая передача?

Bit-Map-протокол.

Идея этого метода показана на рисунке 4-5. Выделяют специальный период состязаний, где количество слотов равно числу станций. Каждая станция, имеющая кадр для передачи, проставляет 1 в свой слот. Поскольку мы рассматриваем канал с множественным доступом (т.е. все видят, что проходит в канале), то в конце состязаний все станции знают, кто будет передавать кадры и в каком порядке. Передача происходит в том же порядке, в каком пронумерованы слоты. Раз станции знают, кто будет передавать и в каком порядке, то конфликтов не будет. Если станция опоздала с заявкой на передачу, то она должна ждать следующего периода состязаний, который начнется по окончании передач, заявленных на предыдущем периоде состязаний. Такие протоколы, когда заявки на передачу откладываются и могут быть сделаны лишь в определенные периоды времени, называются протоколами с резервированием.

Рисунок 4-5. Bit-Map-протокол

Теперь рассмотрим производительность этого метода. Будем для удобства измерять время в количестве слотов состязаний. Будем также предполагать, что передача одного кадра будет занимать ровно d таких слотов. Для станции с небольшим номером, например, 0 или 1, время ожидания на передачу в среднем будет равняться 1,5 N, потому что она, пропустив начало состязаний, будет ждать 0,5 N в первом периоде состязаний и N единиц времени во втором. Другая участь у станций со старшими номерами. Эти станции будут ожидать в среднем N/2 слотов до начала передачи. Таким образом, в среднем любая станция должна будет ждать N слотов до передачи.

При небольшой нагрузке накладные расходы на передачу одного кадра будут N бит, а эффективность передачи одного кадра - d/(d+N), где N - накладные расходы на передачу кадра. При плотной загрузке, когда практически каждая станция каждый раз что-то посылает, накладные расходы будут 1 бит на кадр, т.е. d/(d+1). Средняя задержка кадра будет равна средней задержке кадра внутри очереди в станции плюс N(d+1)/2 слотов ожидания, когда кадр достигнет заголовка очереди. Отсюда видно, что с ростом N, хотя накладные расходы на передачу одного кадра и падают, задержка кадра в канале существенно возрастает, и эффективность падает. Следует также отметить, что если d и N - сопоставимые величины, то значительную часть пропускной способности канала мы будем тратить на состязания.

Один из недостатков bit-map протокола - затраты в 1 бит на кадр. При коротких кадрах это накладно. Есть другая возможность, позволяющая повысить эффективность использования канала. Она основана на двоичном представлении адреса станции.

В этом методе каждая станция, готовая к передаче, выставляет свой адрес бит за битом, начиная со старшего разряда. Эти разряды подвергаются логическому сложению. Если станция выставила на очередном шаге 0, а результат логического сложения - 1, то она должна ждать и в текущих состязаниях участия не принимает. Эффективность использования канала в этом методе - d/(d+lnN). Если структура заголовка кадра была выбрана так, чтобы его можно было использовать для выбора очередной станции для передачи, то lnN битов также будет использовано, тем самым эффективность использования канала достигнет 100%.

Этот метод имеет один существенный недостаток – он не справедливый: чем больше номер станции, тем скорее она захватит канал. В 1979 году Мок (Mok) и Уорд (Ward) предложили модификацию этого метода, когда у станций динамически изменяется приоритет, на основе которого определяется победитель. Победивший в текущих состязаниях получает наименьший приоритет, который будет увеличиваться от состязания к состязанию.

Протоколы с ограниченным числом конфликтов.

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

Естественно попытаться создать протокол, объединяющий достоинства этих двух групп методов, т.е. использовать состязания при небольших нагрузках и бесконфликтные методы - при высоких. Такие протоколы существуют и называются протоколами с ограниченным числом конфликтов. Их изучением мы и закончим рассмотрение класса протоколов с контролем несущей.

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

Рассмотрим производительность в случае симметричного случая. Пусть у нас есть k станций, каждая из которых с вероятностью p готова передать кадр. Тогда вероятность, что какая-то станция успешно передаст свой кадр, равна kp(1-p)^k-1. Эта вероятность достигает максимума при p=1/k. Тогда вероятность передать сообщение какой-либо станцией равна

При небольшом числе станций шансы передать кадр достаточно велики, но с ростом числа станций эти шансы резко падают. Единственным способом увеличить шансы на передачу является сократить конфликты. Для этого в протоколах с ограниченным числом конфликтов все станции разбивают на непересекающиеся группы. За слот с номером 0 состязаются только станции из группы 0. Если передавать нечего или была коллизия, то начинают состязания за слот 1 члены группы 1, и т.д. В результате в каждом слоте конкуренция падает. Основную сложность в этом методе составляет распределение станций по группам.

Адаптивный древовидный протокол устроен по принципу тестирования солдат американской армии на сифилис во второй мировой войне. У n солдат брали кровь на анализ. В первой пробе в общей пробирке смешивали часть крови каждого солдата. Если тест давал отрицательный результат, то все n считались здоровыми. Если тест давал положительную реакцию, то в пробирке смешивали только кровь первой половины солдат и опять тестировали. Если был положительный результат, то эту половину делили опять пополам и т.д., пока не обнаруживали носителя.

На рисунке 4-8 показано, как эта процедура применяется к станциям. Станции - листья. За слот 0 борются все станции. Если какая-то победила - хорошо. Если нет, то за слот 1 борются только станции поддерева с корнем в вершине 2. Если какая-то победила, то следующий слот резервируется для станций поддерева 3. Если был конфликт, то за следующий слот борются станции поддерева 4, и т.д.

Рисунок 4-8. Дерево для восьми станций

Когда число станций велико и все они готовы передавать, то вряд ли целесообразно начинать поиск с уровня 0 в дереве. Возникает вопрос: с какого уровня надо начинать эту процедуру при заданном числе станций? Пусть число станций, готовых к передаче, нормально распределено. Обозначим это число через q. Тогда число станций, готовых к передаче и расположенных ниже уровня i, будет ровно 2^-iq. Заметим, что их доля от общего числа станций, расположенных в дереве ниже уровня i, равна 2^-i. Естественно, надо подобрать такое соотношение между i и q, когда количество конкурирующих станций будет 1, т.е. 2^-iq=1, или log₂q=i.

У этого алгоритма есть много вариантов. Мы здесь описали лишь основную идею.

Протоколы с множественным доступом и разделением частот.

Иной подход к распределению доступа к каналу основан на разделении канала на подканалы, используя FDM-, TDM-метод или сразу оба этих метода.

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

Обозначим через m число слотов в управляющем канале и через n+1 - в канале данных. Из них n слотов - для данных, а последний - для сообщения о статусе канала. Протокол поддерживает три класса трафика:

1. Постоянный с соединением (видео)

2. Переменный с соединением (передача файлов)

3. Дейтаграммный (типа UDP)

4. У каждой станции есть два ресивера и два трансивера:

5. Ресивер для фиксированной длины волны для канала управления

6. Настраиваемый трансивер для передачи в каналы управления других станций

7. Трансивер для фиксированной длины волны для передачи данных

8. Настраиваемый ресивер для получения данных

Другими словами, каждая станция постоянно слушает свой управляющий канал, но должна настраиваться при приеме на волну передающей станции. Рассмотрим, как станция А устанавливает соединение класса 2 со станцией В для передачи файла. А настраивается на управляющий канал станции В, чтобы определить, какие слоты уже заняты, а какие свободны. На рисунке 4-9 видно, что у В из 8 управляющих слотов свободны 0, 4 и 5.

Рисунок 4-9. Множественный доступ с разделением частот

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

После того как соединение установлено, А посылает В управляющее сообщение типа: «Жди. В слоте 3 канала данных есть кадр». Получив такое сообщение, В настраивается на волну канала А и считывает кадр. Таким образом, мы имеем бесконфликтный канал. Хотя может случиться, что если А и С имеют соединение с В и оба скажут «смотри на слот 3, там кадр от меня», то от какого из двух получит сообщение В, сказать заранее нельзя.

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

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