Реферат: Канальный уровень модели iso/osi. Протоколы доступа к среде (семейство протоколов aloha, протокол csma, полнодуплексный доступ)
РОССИЙСКИЙ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ
Факультет физико-математических и естественных наук
НаправлениеМатематика. Компьютерные науки.
Кафедрасистем телекоммуникаций
Дисциплинасети и системы телекоммуникаций
Реферат
Канальный уровень модели ISO/OSI. Протоколы доступа к среде (семейство протоколов ALOHA, протокол CSMA, полнодуплексный доступ).
СтудентРоманова Наталья Александровна
ГруппаНК-301
Лекторк. ф.-м. н., доцент Кулябов Д.С.
Заведующий кафедройд. т. н. Самуйлов К.Е.
МОСКВА
2005 г.
Оглавление
1.Назначение, функции и услуги канального уровня модели ISO/OSI. 5
1.1.Сервис, предоставляемый сетевому уровню… 6
1.5.Обнаружение и исправление ошибок. 13
Коды с исправлением ошибок. 13
Коды обнаруживающие ошибки. 15
2.Доступ к среде, модели статического и динамического выделения канала. 18
2.1.Статическое предоставление канала. 18
2.2.Динамическое предоставление канала. 19
3.Протоколы множественного доступа. 22
3.1.Семейство протоколов ALOHA. 22
3.2.Протоколы множественного доступа с контролем несущей (CSMA). 25
Настойчивые и не настойчивые CSMA. 25
3.3.Протоколы множественного доступа с контролем несущей с определением коллизий (CSMA/CD). 26
3.4.Доступ с передачей маркера. 28
3.5.Доступ по приоритету запроса. 28
4.Примеры протоколов множественного доступа. 30
Список сокращений
Англоязычные сокращения
CRC | – | Cyclic Redundancy Code |
CSMA | – | Carrier Sense Multiply Access |
CSMA/CD | – | Carrier Sense Multiply Access with Collision Detection |
DLC | – | Data Link Layer |
DLE | – | Data Link Escape |
ETX | – | End TeXt |
FDDI | – | Fiber Distributed Data Interface |
FDM | – | Frequency Division Multiplexing |
LAN | – | Local Area Network |
LLC | – | Logical Link Control |
MAC | – | Media Access Control |
STX | – | Start TeXt |
TDM | – | Time Division Multiplexing |
WAN | – | World Area Network |
Введение
Канальный уровень предназначен для обеспечения взаимодействия сетей на физическом уровне и контроля за ошибками, которые могут возникнуть. Полученные с физического уровня данные он упаковывает в кадры данных, проверяет на целостность, если нужно исправляет ошибки и отправляет на сетевой уровень. Канальный уровень может взаимодействовать с одним или несколькими физическими уровнями, контролируя и управляя этим взаимодействием. Спецификация IEEE 802 разделяет этот уровень на 2 подуровня — MAC (Media Access Control) регулирует доступ к разделяемой физической среде, LLC (Logical Link Control) обеспечивает обслуживание сетевого уровня (Рис. Введение 1). На этом уровне работают коммутаторы, мосты.
Рис. Введение 1 Модель OSI
1. Назначение, функции и услуги канального уровня модели ISO/OSI
Канальный уровень (Data Link Layer) также носит названия: уровень управления передачей данных (Data Link Control, DLC), уровень звена данных.
Канальный уровень обеспечивает функциональные и процедурные средства для установления, поддержания и разрыва соединений канального уровня между стевыми логическими объектами и для передачи сервисных блоков данных этого уровня. Соединение канального уровня строится на основе одного или нескольких физических соединений.
Канальный уровень обнаруживает и по возможности исправляет ошибки, которые могут возникнуть на физическом уровне. Кроме того, канальный уровень обеспечивает для сетевого уровня возможность управлять подключением каналов данных на физическом уровне.
Единицу информации на канальном уровне называют кадром (frame).
Услуги, предоставляемые сетевому уровню. Канальный уровень предоставляет следующие услуги или элементы услуг:
— соединение канального уровня;
— сервисные блоки данных канального уровня;
— идентификаторы оконечного пункта соединения канального уровня;
— упорядочение блоков данных;
— оповешение об ошибках;
— управление потоком данных;
— параметры качества услуги.
Функции, выполняемые на канальном уровне. На канальном уровне выполняются следующие функции:
— установление и разрыв соединения канального уровня;
— отображение сервисных блоков данных канального уровня;
— расщепление соединения канального уровня;
— разграничение и синхронизация;
— упорядочение блоков данных;
— обнаружение ошибок;
— восстановление при ошибках;
— управление потоком данных;
— идентификация и обмен параметрами;
— управление переключением каналов данных;
— административное управление канальноо уровня.
1.1. Сервис, предоставляемый сетевому уровню
Основной задачей канального уровня обеспечить сервис сетевому уровню. Назначение этого сервиса — помочь передать данные процесса на сетевом уровне одной машины процессу на сетевой уровень другой машины.
Рис1. 1 Виртуальное соединение (а); реальное соединение (б)
Так как это показано на Рис1.1. Фактически передача будет происходить так, как показано на Рис1.1b. Однако, для простоты изложения мы будем считать, что это происходит как на Рис1.1а.
Канальный уровень может создаваться для различного сервиса, который может варьироваться от системы к системе. Однако, есть три общие вида сервиса:
— Сервис без уведомления и без соединения.
— Сервис с уведомлением и без соединения.
— Сервис с уведомлением и с соединением.
Сервис без уведомления и без соединения не предполагает, что прием переданного кадра должен подтверждаться, что до начала передачи должно устанавливаться соединение, которое после передачи должно разрываться. Если в результате помех на физическом уровне кадр будет потерян, то никаких попыток его восстановить на канальном уровне не будет. Этот класс сервиса используется там, где физический уровень обеспечивает высокую надежность при передаче так, что восстановление при потери кадров можно оставить на верхние уровни. Он также применяется при передаче данных в реальном времени там, где лучше потерять часть данных, чем увеличить задержку в их доставке. Например, передача речи. Большинство ЛВС использует этот класс сервиса на канальном уровне.
Следующий класс сервиса — уведомление без соединения. В этом классе получение каждого посланного кадра должно быть подтверждено. Если подтверждения не пришло в течении определенного времени, то кадр должен быть послан опять. Этот класс сервиса используется над ненадежной физической средой передачи, например, беспроводной.
Можно конечно было бы подтверждать не кадры, а все сообщение на сетевом уровне. Однако, это было бы не выгодно для больших сообщений, при передаче которых разрушалось бы 10-20%. Повторная передача таких сообщений заняла бы больше времени, чем передача их отдельных фрагментов. Так что подтверждение на канальном уровне следует рассматривать как оптимизацию, а не необходимость.
Наиболее сложный класс сервиса на канальном уровне — сервис с уведомлением и соединением. Этот класс сервиса предполагает, что до начала передачи между машинами устанавливается соединение и данные передаются по этому соединению. Каждый передаваемый кадр нумеруется и канальный уровень гарантирует, что он будет обязательно получен и только один раз и все кадры будут получены в надлежащей последовательности. При сервисе без соединения этого гарантировать нельзя потому, что потеря подтверждения получения кадра приведет к его пересылке так, что появиться несколько идентичных кадров.
При сервисе с подтверждение и соединением передача разбивается на три этапа. На первом этапе устанавливается соединение: инициируются переменные на обоих машинах и счетчики, отслеживающие какие кадры были приняты, а какие нет. На втором этапе один или несколько кадров передается. На третьем — соединение разрывается: переменные, счетчики, буфера и другие ресурсы, использованные для поддержки соединения, освобождаются.
Рис1. 2 Протокол передачи данных
На Рис1.2 показан типичный фрагмент WAN где два маршрутизатора соединены через телефонную линию. Когда кадр поступает в маршрутизатор, аппаратура проверяет контрольную сумму и передает кадр канальному уровню. Канальный уровень проверяет является ли поступивший кадр ожидаемым и если да, то передает пакет, расположенный в кадре, сетевому уровню на другой машине. Процесс на сетевом уровне выбирает надлежащую линию для передачи и посылает пакет на канальный уровень.
Не желательно на сетевом уровне заниматься пропажей кадров. Это задача канального уровня обеспечить надежный канал. Это особенно важно при беспроводной среде передачи.
Сервис, создаваемый канальным уровнем для сетевого, опирается на сервис, создаваемый физическим уровнем. На физическом уровне протекают потоки битов. Посланное количество битов не обязательно равно принятому, значение посланного бита так же не обязательно равно принятому. Все это требует специальных усилий на канальном уровне по обнаружению и исправлению ошибок.
Типовой подход к решению этой проблемы — разбиение потока битов на кадры, подсчет контрольной суммы для каждого кадра при посылке данных. При приеме контрольная сумма вычисляется для каждого кадра заново и сравнивается с той что храниться в кадре. Если они различаются, то это признак ошибки передачи. Канальный уровень должен принять меры к исправлению ошибки, например, сбросить плохой кадр, послать сообщение об ошибке тому кто прислал этот кадр.
Разбиение потока битов на кадры — задача не простая. Один из способов — делать временную паузу между битами разных кадров. Однако, в сети где нет единого таймера нет гарантии, что эта пауза сохраниться или, наоборот, не появятся новые.
Так как временные методы ненадежны, то применяются другие. Здесь мы рассмотрим четыре основных:
— счетчик символов
— вставка специальных стартовых и конечных символов
— вставка стартовых и концевых битов
— нарушение кодировки на физическом уровне
Первый метод показан на Рис1.3. В начало каждого кадра указывается сколько символов в кадре. При приеме число принятых символов подсчитывается опять. Однако, этот метод имеет существенный недостаток: счетчик символов может быть искажен при передаче. Тогда принимающая сторона не сможет обнаружить границы кадра. Даже обнаружив не совпадение контрольных сумм, принимающая сторона не сможет сообщить передающей какой кадр надо переслать, сколько символов пропало. Этот метод ныне используется редко.
Рис1. 3 Поток символов: без ошибок (а); с одноц ошибкой (б)
Второй метод построен на вставке специальных символов. Обычно для этого используют аж последовательность DLE STX для начала кадра и DLE ETX для конца кадра. DLE — Data Link Escape; STX — Start TeXt, ETX — End TeXt. При этом методе если даже была потеряна граница текущего кадра, надо просто искать ближайшую последовательность DLE STX или DLE ETX. Здесь есть одна опасность: при передаче чисел или программы в объектном коде такие последовательности могут уже содержаться в передаваемых данных. Для решения этой проблемы используется прием экранирования: каждая последовательность DLE просто дублируется в передаваемых данных. Поэтому при приеме если есть два последовательных DLE, то один удаляется. Этот метод проиллюстрирован на Рис1.4.
Рис1. 4 Кадр, ограниченный длаговыми байтами (а); кадр, обработанный на канальном уровне (б); данные, передаваемые на сетевой уровень (в)
Основным недостатком этого метода является то, что он жестко связан с размером байта и кодировкой ASCII. По мере развития сетей эта связь становилась все более и более обременительной.
Был предложен новый прием, позволяющий использовать любое число битов на символ и любую кодировку. Его идея состоит в том, что каждый кадр начинается и заканчивается со специального флаг-байта: 01111110. Посылающая сторона встретив последовательно 5 единиц обязательно вставит 0. Принимающая сторона, приняв 5 последовательных единиц обязательно удалит следующий за ними 0. Если в передаваемых данных встретиться конфигурация флаг-байта, то она будет преобразована в конфигурацию 011111010. Этот метод иллюстрирует Рис1.5. Ясно что он прозрачен для сетевого уровня так, же как и метод вставки байтов.
Рис1. 5 Битовое заполнение: исходные данные (а); данные на линии (б); данные, сохраненные в памяти после удаления вставленных битов (в)
Таким образом, кадр легко может быть распознан по флаг-байту. Если граница очередного кадра по какой-то причине была потеряна, то все что надо делать — ловить ближайший флаг-байт.
Последний метод используется там, где применяется специальная кодировка битов на физическом уровне. Например, для передачи одного бита используется два импульса. 1 кодируется как переход высокое-низкое, 0 — как низкое-высокое. Сочетания низкое-низкое или высокое-высокое не используются для передачи данных. Их то и используют для границ кадра. Так делают в стандарте IEEE 802 для ЛВС, который мы рассмотрим позже.
Наконец, на практике используют, как правило, комбинацию этих методов. Например, счетчик символов с одним из выше перечисленных. Тогда если число символов в кадру совпадает с кодировкой границы кадра, кадр считается переданным правильно.
Решив проблему разбиения на кадры, мы приходим к следующей проблеме: как обеспечить, чтобы кадры попадали на сетевой уровень по назначению и в надлежащей последовательности? Если для отправляющей стороны все равно в какой последовательности поступают кадры, то этой проблемы нет. Например, если нам нужен сервис без уведомления и соединения, но если нам нужен сервис с подтверждением и с соединением, то как быть?
Для решения этой проблемы устанавливают обратную связь между отправителем и получателем в виде кадра подтверждения. Если кадр-подтверждение несет положительную информацию, то считается что переданные кадры прошли нормально, если там сообщение об ошибке, то переданные кадры надо передать заново.
Однако, возможны случаи когда из-за ошибок в канале кадр исчезнет целиком. В этом случае получатель не будет реагировать ни как, а отправитель будет сколь угодно долго ждать подтверждения. Для решения этой проблемы на канальном уровне вводят таймеры. Когда передается очередной кадр, то одновременно устанавливается таймер на определенное время. Этого времени должно хватать на то, чтобы получатель получил кадр, а отправитель получил подтверждение. Если отправитель не получит подтверждение раньше, чем истечет время, установленное на таймере, то он будет считать, что кадр потерян и повторит его еще раз.
Однако, если кадр-подтверждение был утерян, то вполне возможно, что один и тот же кадр получатель получит дважды. Как быть? Для решения этой проблемы каждому кадру присваивают порядковый номер. С помощью этого номера получатель может обнаружить дубли.
Другой важной проблемой, которая решается на канальном уровне — управление потоком. Дело в том, что вполне может случиться, что отправитель будет слать кадры столь часто, что получатель не будет успевать их обрабатывать. Это может случиться если, например, машина-отправитель более мощная или загружена слабее, чем машина-получатель.
1.5. Обнаружение и исправление ошибок
В рассмотрении физической среды мы отмечали, что у беспроводных систем связи, аналоговых каналов, например, петля в телефонных системах, достаточно высокий уровень ошибок в канале. Поэтому ошибки при передаче- это реальность, которую надо обязательно учитывать.
В разных средах характер ошибок разный. Ошибки могут быть одиночные, а могут возникать группами, сразу по несколько. У групповых ошибок есть свои достоинства и недостатки. Достоинство заключается в следующем. Пусть данные передаются блоками по 1000 бит, а уровень ошибки 0,001 на бит. Если ошибки изолированные и независимые, то практически каждый блок будет содержать ошибку в среднем. Если же они
Коды с исправлением ошибок
Для надежной передачи кодов было предложено два основных метода. Первый — внести избыточность в форме дополнительных битов в передаваемый блок данных так, чтобы, анализируя полученный блок, можно было бы указать где возникли искажения. Это, так называемые, коды с исправлением ошибок. Второй — внести избыточность, но лишь настолько, чтобы, анализируя полученные данные, можно было сказать есть в переданном блоке ошибки или нет. Это, так называемые, коды с обнаружением ошибок.
Пусть данные занимают разрядов и мы добавляем разрядов как контрольные разряды. Нам надо передать слово длины , которое называют n-битовым кодословом. Пусть у нас есть два кодослова 10001001 и 10110001. С помощью операции EXCLUSIVE OR легко определить число различных разрядов. В данном случае их 3. Количество разных битов в двух кодословах называется расстоянием Хемминга. Поэтому если два кодослова находятся на расстоянии по Хеммингу, это значит, что надо преобразовать ровно разрядов, чтобы преобразовать одно кодослово в другое.
В силу избыточности не все комбинаций возможны. Зная алгоритм установки контрольных разрядов, мы можем вычислить минимальное расстояние по Хеммингу между допустимыми кодословами. Способен код исправлять ошибки или только обнаруживать зависит от расстояния между его кодословами по Хеммингу. Если мы хоти обнаруживать ошибок, то надо чтобы кодослова отстояли друг от друга на расстояние . Тогда если принятый код отстоит на расстояние , то принятое кодослово содержит k ошибок. Если мы хотим исправлять ошибки, то надо чтобы кодослова отстояли друг от друга на . Поэтому даже если переданное кодослово содержит ошибок, оно все равно ближе к правильному кодослову, чем к какому-либо еще, и следовательно можно определить, исходное слово.
Простым примеров кода с обнаружением одной ошибки является код с битом четности. Конструкция его такова: к исходному кодослову добавляется бит четности. Если число 1 в исходном кодослове четно, то значение этого бита 0. Если нечетно, то 0. Кодослова с битом четности имеют расстояние хемминга 2.
Для примера кода с исправлением ошибки рассмотрим код, у которого есть только четыре правильных кодослова: 0000000000, 0000011111, 11111100000, 11111111111. Расстояние по хеммингу у этого кода 5, следовательно он может исправлять двойные ошибки. Если получатель получит слово 0000000111, то ясно, что исходное слово имело вид 0000011111.
Оценим минимальное количество контрольных разрядов, необходимое для исправления одиночных ошибок. Пусть у нас есть код из бит сообщения и контрольных бит. Каждое из правильных кодослов имеет неправильных кодослов на расстоянии 1. Такими образом, с каждым из кодослов связано кодослов. Так как общее число кодослов, то
, учитывая чтополучаем
Этот теоретический предел достижим при использовании метода, предложенного Хеммингом. Идея его в следующем: все биты, номера которых есть степень 2 (1,2,4,8,16 и т.д.) — контрольные, остальные — биты сообщения. Каждый контрольный бит отвечает за четность группы битов, включая себя. Один и тот же бит может относиться к разным группам. Значение бита сообщения определяется по значениям контрольных битов. Чтобы определить какие контрольные биты контролируют бит в позиции k надо представить значение k по степеням двойки. Например, , а .
Получив кодослово, получатель устанавливает специальный счетчик в ноль. Затем он проверят каждый контрольный бит на предмет правильности четности. Если четность нарушена, то порядковый номер этого бита заноситься в счетчик. Если после этой проверки счетчик ноль, то все в порядке. Если нет, то он содержит номер неправильного разряда. Например, 1, 2, 8 — ошибочные контрольные разряды, то ошибка в 11 разряде, так как только он связан одновременно с этими контрольными разрядами.
Код хемминга может исправлять только единичные ошибки. Однако, есть прием, который позволяет распространить идеи Хемминга на случай групповых ошибок. Пусть нам надо передать k кодослов. Расположим их в виде матрицы одно слово — строка. Обычно, передают слово за словом. Но мы поступим иначе, передадим слово длины , из 1-ых разрядов всех слов, затем — вторых и т.д. По приеме всех слов матрица восстанавливается. Если мы хотим обнаруживать групповые ошибки размера , то в каждой строке восстановленной матрицы будет не более одной ошибки. А с одиночными ошибками код хемминга справиться.
Коды обнаруживающие ошибки
Начнем а небольшого примера. Пусть у нас есть канал с единичными ошибкой с частотой 10-6 на бит. Если мы хотим исправлять единичные ошибки при передаче блока в 1000 бит, то нам потребуется 10 контрольных бит. При передаче 1 Мбит данных, потребуется 10 000 контрольных бит. В тоже время для обнаружения единичной ошибки достаточно одного бита четности. Поэтому, если мы применим технику повторной передачи, то на передачу 1000 блоков надо будет потратить 1001 бит дополнительно или с повторной передачей 2002 бит, вместо 10,000 бит в случае кода с исправлением ошибки.
Применение техники четности «в лоб» в случае групповых ошибок не даст нужного результата. Однако, ее можно скорректировать. Пусть нам надо передать слов по бит. Расположим их в виде матрицы . Для каждого столбца вычислим бит четности и разместим его в дополнительной строке. Матрица затем передается по строкам. По получению матрица восстанавливается и если хоть один бит нарушен, то весь блок передается повторно.
Этот метод позволяет обнаружить групповые ошибки длины . Против групповых ошибок длины он бессилен. В общем случае вероятность правильной передачи при длине групповой ошибке , равна .
Поэтому на практике применяют другую технику, которая называется полиномиальными кодами или циклическим избыточным кодом (Cyclic Redundancy Code) или CRC кодом.
CRC коды построены на рассмотрении битовой строки как строки коэффициентов полинома. битовая строка — коэффициенты полинома степени . Самый левый бит строки — коэффициент при старшей степени. Например, строка 110001 представляет полином.
Полиномиальная арифметика выполняется по модулю 2. Сложение и вычитание происходит без переноса разрядов. Так, что обе это операции эквивалентны EXCLUSIVE OR. Например,
Деление выполняется как обычно в двоичной системе с той лишь разницей, что вычитание выполняется по модулю два.
Использование полиномиальных кодов при передаче заключается в следующем. Отправитель и получатель заранее договариваются о конкретном генераторе полиномов , у него коэффициенты при старшем члене и при младшем члене должны быть равны 1. Пусть степень равна r. Для вычисления контрольной суммы блока из m бит надо чтобы обязательно . Идея состоит в том, чтобы добавить контрольную сумму к передаваемому блоку, рассматриваемому как полином так, чтобы передаваемый блок с контрольной суммой был кратен . Когда получатель получает блок с контрольной суммой, он делит его на . Если есть остаток, то были ошибки при передаче.
Алгоритм вычисления контрольной суммы:
1) Добавить нулей в конец блока так, что он теперь содержит m+r разрядов и соответствует полиному ;
2) Разделить по модулю 2 полином на ;
Этот метод позволяет отлавливать одиночные ошибки. Групповые ошибки длины не более . Нечетное число отдельных ошибок.
Существует три международных стандарта на вид :
.
CRC-12 используется для передачи символов из 6 разрядов. Два остальных — для 8 разрядных. CRC-16 и CRC-CCITT ловят одиночные, двойные ошибки, групповые ошибки длины не более 16 и нечетное число изолированных ошибок с вероятностью 99,997%.
2. Доступ к среде, модели статического и динамического выделения канала.
Будем рассматривать протоколы доступа к среде передаче данных с множественным доступом. Существует два вида сред передачи данных: точка-точка и с множественным доступом. В среде точка-точка доступ возможен только с двух сторон. Проблемы синхронизации доступа здесь не столь сложны. Этот вид сред передачи характерен для WAN сетей. Здесь мы рассмотрим каналы с множественным доступом или, как их еще называют, протоколы со случайным доступом.
В средах с множественным доступом ключевым является вопрос: как определить кому из запросивших отдать канал? Представим себе конференцию по телефону. Когда говоривший закончит речь возможно, что сразу несколько участников захотят высказаться. Они начнут говорить одновременно. Как предотвратить хаос? Протоколы для решения этой проблемы составляют основу этой главы.
Протоколы для определения кто захватит канал в случае конкуренции относятся к подуровню канального уровня, который называется МАС — Medium Access Control.
2.1. Статическое предоставление канала
Существует два основных подхода к мультиплексированию нескольких конкурирующих пользователей на одном канале — частотное разделение (FDM). Частотное разделение хорошо работает в условиях, когда число пользователей фиксировано и каждый порождает плотную загрузку канала. Тогда каждому из них выделяется своя полоса частот, которую он использует независимо от других.
Однако, когда число пользователей велико или величина переменная, или когда трафик очень не регулярный, у FDM появляются проблемы. Если весь диапазон разделить на полос и лишь не многим из потребуется передача, то большая часть пропускной способности будет теряться. Если число пользователей, кому необходимо передать данные, больше , то часть из них получит отказ из-за недостатка пропускной способности, хотя часть тех кому канал будет предоставлен может ничего не передавать или не принимать.
Таким образом предположение о постоянстве числа пользователей в среднем и статическое разделение канала на подканалы является не эффективным решение. Положение усугубляет то обстоятельство, что трафик в сетях, как правило, носит взрыво-образный характер ( отличие пиковых нагрузок от средних достигает 1000 раз). Поэтому статическое распределение было бы не эффективно, т.к. большую часть времени канал простаивал.
Это можно показать теоретически на следующей модели. Пусть у нас есть канал со скоростью bps и мы хотим оценить среднее временя задержки. Средняя скорость поступления кадров равна кадр/сек и средняя длина кадра имеет экспоненциальное распределение со средним бит/кадр. Тогда
Теперь разделим канал на подканалов каждый со скоростью bps. Скорость поступления кадров в каждом из подканалов будет теперь . Соответственно получаем
.
Отсюда видно, что частотное разделение в раз хуже, по сравнению с тем как если бы все кадры как-то были бы распределены из единой очереди.
2.2. Динамическое предоставление канала
Прежде чем перейти к описанию многочисленных динамических способов предоставления канала сформулируем основные пять предположений, которые мы будем использовать:
— Многостационная модель. Модель состоит из независимых станций (компьютеров, телефонов, факс-машин и т.п.). На каждой работает пользователь или программа, которые генерируют кадры для передачи. Вероятность, появления кадра в интервале равна , где v константа. Предполагается, что если кадр сгенерирован, то новый не появится, пока не будет передан первый.
— Модель единого канала. Канал один и он доступен всем станциям. Все станции равноправны. Они получаю кадры и передаю кадры только через этот единственный канал. Аппаратные средства всех станцией для доступа к каналу одинаковы, но программно можно устанавливать приоритеты.
— Модель с коллизиями. Если две станции передают кадры в одно и то же время, то сигналы накладываются и разрушаются. Этот случай будем называть коллизией. Любая станция может обнаружить коллизию. Кадры, столкнувшиеся в коллизии, должны быть посланы повторно позднее. Кроме коллизий других ошибок передачи нет.
— Временные модели :
— Непрерывное время . Передача кадра может начаться в любой момент. Нет единых часов в системе, которые разбивают время на слоты.
— Дискретное время . Время разбивается на дискретные интервалы — слоты. Кадр начинает передаваться только в начале слота. Слот может соответствовать нескольким кадрам, если это слот ожидания, он может содержать коллизию, либо успешную передачу.
— Модели с несущей :
— Обнаружение несущей . Станция всегда определяет занят ли канал прежде, чем использовать его. Если он занят, то ни одна станция не начинает передачу.
— Отсутствие несущей . Станция ничего не знает о состоянии канал пока не начнет использовать его. Она сразу начинает передачу и лишь позднее обнаруживает коллизию.
3. Протоколы множественного доступа.
3.1. Семейство протоколов ALOHA.
В 70-хгодах Норман Абрамсон со своими коллегами из университета Гаваи предложил простой способ распределения канала. Абрамсон назвал систему ALOHA — это приветствие по гавайски, состоявшей из наземных радиостанций, связывающих острова между собой. Идея была позволить в вещательной среде любому количеству пользователей неконтролируемо использовать один и тот же канал.
Мы здесь рассмотрим два варианта системы: чистая ALOHA и слотированная, т.е. разбитая на слоты. Основное различие — в первом случае никакой синхронизации пользователей не требуется, во втором она нужна.
Чистая ALOHA
Идея чистой ALOHA проста — любой пользователь пытается передать сообщение. Благодаря тому, что в вещательной среде он всегда имеет обратную связь, то он видит возникновение конфликта при передаче. Эта обратная связь в среде LAN происходит практически мгновенно, в системах спутниковой связи задержка составляет около 270 mсек.
Обнаружив конфликт, пользователь ожидает некоторый случайный отрезок времени после чего повторяет попытку. Ожидание должно быть случайным, иначе конкуренты будут повторять попытки в одно и то же время, что приведет к блокировке. Системы подобного типа, где пользователи конкурируют за получение общего канала, называются системами с состязаниями.
Неважно когда произошел конфликт когда первый бит одного кадра наложился на последний бит другого кадра или как-то иначе, оба кадра считаются испорченными и должны быть переданы повторно. Контрольная суммам не позволяет различать разные случаи наложения.
Какова эффективность системы ALOHA? Какая часть кадров избежала коллизий? Рассмотрим следующую модель. Есть неограниченное число пользователей, работающих на компьютерах. Все что они могут делать это — либо набирать текст, либо ждать пока набранный текст передается. Когда пользователь заканчивает набирать очередную строку, он останавливается и ждет ответа от системы. Система пытается передать эту строку. Когда она сделает это успешно, пользователь видит отклик и может продолжать работу.
Назовем временем кадра — время необходимое на передачу кадра стандартной фиксированной длины. Предполагаем, что пользователей не ограниченное число и они порождаю кадры по закону Пуассона со средним кадров за время кадра. Поскольку при очередь на передачу будет только расти и все кадры будут страдать от коллизий, то мы будем предполагать, .
Также будем предполагать что вероятность k попыток послать как новые, так и ранее не прошедшие кадры за время кадра распределена по закону Пуассона со средним попыток. Понятно, что . При слабой загрузке (приближенно равно нулю) будет не много передач, а следовательно и коллизий — G приближенно равно . При высокой загрузке . При любой нагрузке пропускная способность это — число кадров, которые надо передать, умноженное на вероятность успешной передачи. Если обозначить — вероятность успешной передачи, то .
Рассмотрим внимательно сколько времени надо отправителю, чтобы обнаружить коллизию. Пусть он начал передачу в момент времени и пусть требуется время , чтобы кадр достиг самой отдаленной станции. Тогда если в тот момент, когда кадр почти достиг этой отдаленной станции она начнет передачу ( ведь в системе ALOHA станция сначала передает, а потом слушает), то отправитель узнает об этом только через .
Вероятность появления k кадров на передачу при распределении Пуассона равна
поэтому вероятность, что появится 0 кадров равна . За двойное время кадра среднее число кадров будет , отсюда
,
а так как, то
.
Рис.3. 1 Зависимость производительности канала от предлагаемого трафика для систем ALOHA
Зависимость между нагрузкой и пропускной способность показана на Рис.3.1. максимальная пропускная способность достигается при при , что составляет примерно 18%. Результат не очень вдохновляющий.
Слотированная ALOHA .
В 1972 году Робертс предложил модификацию чистой ALOHA. Все время разделяют на слоты — один кадр на слот. Ясно, что это требует синхронизации. Одна станция должна испускать сигнал начала очередного слота. Поскольку передачу теперь можно начинать не в любой момент, а только по специальному сигналу, то время на обнаружение коллизии сокращается в двое. Отсюда
.
Как видно из рис. 1 максимум пропускной способности слотированной ALOHA наступает при , где , т.е. около 0,37, что в двое больше чем у чистой ALOHA.
Рассмотрим как влияет на пропускную способность подсчитаем вероятность успешной передачи за попыток. Так как вероятность отсутствия коллизии при передаче, то вероятность что кадр будет передан ровно за попыток, равна
Среднее ожидаемое число повторных передач будет
Эта экспоненциальная зависимость показывает, что с ростом резко возрастает число повторных попыток, а следовательно и общая пропускная способность канала.
3.2. Протоколы множественного доступа с контролем несущей (CSMA).
Лучший результат, какой мы можем получить для системы ALOHA — 1/е. Это не удивительно, так как там станция не обращает внимание на, что делают другие. В локальных сетях есть возможность определить, что делают другие станции и только после этого решать что делать.
Протоколы, которые реализую именно эту идею — определить есть ли передача и действовать соответствующе, называются протоколами с обнаружением несущей CSMA (Carrier Sense Multiply Access).
Настойчивые и не настойчивые CSMA.
Согласно протоколу, который мы сейчас рассмотрим, станция прежде чем что-либо передавать определяет состояние канала. Если канал занят, то она ждет. Как только канал освободился она пытается начать передачу. Если при этом произошла коллизия, она ожидает случайный интервал времени и все начинает с начала. Этот протокол называется CSMA настойчивым протоколом первого уровня или 1-настойчивым CSMA протоколом, потому что он начинает передачу с вероятность 1 как только обнаруживает, что канал свободен.
Здесь существенной является задержка распространения сигнала. Чем она больше. Тем больше будет коллизий, так как две готовые к передачи станции обнаружат что они обе в режиме передачи только по истечении времени задержки. Тем не менее этот протокол более эффективен, чем любая из ALOHA, так как учитывают что происходит на канале прежде, чем начать действовать.
Другой вариант CSMA — не настойчивый CSMA протокол. Основное отличие его от предыдущего в том, что готовая к передаче станция не опрашивает постоянно канал, в ожидании когда он освободиться, а делает это через случайные отрезки времени. Это несколько увеличивает задержку при передаче, но общая эффективность возрастает.
И, наконец, CSMA настойчивый протокол уровня р. Он применяется к слотированным каналам. Когда станция готова к передаче она опрашивает канал, если он свободен, то она с вероятностью р передает свой кадр и с вероятностью ждет следующего слота. Так она действует пока не передаст кадр. Если произошла коллизия вовремя передачи, она ожидает случайный интервал времени и опрашивает канал опять. Если при опросе канала он оказался занят, станция ждет начала следующего слота и весь алгоритм повторяется. На Рис.3.2 показана пропускная способность в зависимости от нагрузки.
Рис.3. 2 Сравнение использования канала в зависимости отего нагрузки для различных протоколов коллективного доступа
3.3. Протоколы множественного доступа с контролем несущей с определением коллизий (CSMA/CD).
Настойчивые и ненастойчивые CSMA протоколы несомненно есть улучшение ALOHA, т.к. они начинают передачу только проверив состояние канала. Другим улучшением, которое можно сделать, — станции должны уметь определять коллизии как можно раньше, а не по окончании отправки кадра. Это экономит время и пропускную способность канала. Такой протокол, известный как CSMA/CD — Carrier Sense Multiply Access with Collision Detection, широко используется в локальных сетях.
Рис.3.3 Протокол CSMA/CD может находиться в одном из трех состояний: конкуренции, передачи и простоя.
На рис. 3-3 показана модель, которая используется во многих протоколах. В момент t0 станция заканчивает передачу очередного фрейма. Все станции, у которых есть кадр для передачи начинают передачу. Естественно происходят коллизии, который быстро обнаруживаются, сравнивая отправленный сигнал с тем который есть на линии. Обнаружив коллизию, станция сразу прекращает передачу на случайный интервал времени, после чего все начинается сначала. Таким образом в работе протокола CSMA/CD можно выделить три периода: состязаний, передачи и ожидания, когда нет кадров для передачи.
Рис.3. 4 Алгоритмы приема и передачи данных в узле при CSMA/CD
На Рис.3.4 представлены алгоритмы приема и передачи данных в одном из узлов при CSMA/CD.
Сколько времени станции, начавшей передачу, нужно, чтобы определить коллизию. Обозначим t время распространения сигнала до самой удаленной станции на линии. Для коаксиала в 1 км . Тогда минимальное время для определения коллизии будет . Поэтому, станция не может быть уверена, что она захватила канал до тех пор, пока в течении секунд не будет коллизий. Поэтому, весь период состязаний разбивается на слоты по секунд по одному биту на слот. Захватив канал, станция может далее передавать кадр с любой скоростью.
Надо подчеркнуть, что МАС подуровень обеспечивает надежную передачу, используя специальные приемы кодирования данных. Позднее, при рассмотрении Ethernet, мы подробно рассмотрим как это достигается.
3.4. Доступ с передачей маркера
Суть доступа с передачей маркера заключается в следующем: пакет особого типа, маркер (token) циркулирует по кольцу от компьютера к компьютеру. Маркер — это специальное сообщение, которое передает временное управление средой передачи устройству, владеющему маркером. Чтобы послать данные в сеть, любой из компьютеров сначала должен дождаться прихода свободного маркера и захватить его.
Когда какой-либо компьютер «наполнит» маркер своей информацией и пошлет его по сетевому кабелю, другие компьютеры уже не могут передавать данные. Так в каждый момент времени только один компьютер будет использовать маркер, в сети не возникнет ни состязания, ни коллизий, ни временных пауз.
Сети с передачей маркера следует использовать при наличии зависящего от времени приоритетного трафика, типа цифровых видео— и аудиоданных, или при наличии очень большого количества пользователей.
3.5. Доступ по приоритету запроса.
Доступ по приоритету запроса — относительно новый метод доступа, разработан для стандарта сети Ethernet со скоростью передачи данных 100 Мбит/с — 100VG-AnyLAN. Он стандартизован IEEE в категории 802.12.
Этот метод доступа основан на том, что все сети 100VG-AnyLAN строятся только из концентраторов и оконечных узлов. Концентраторы управляют доступом к кабелю, последовательно опрашивая все узлы в сети и выявляя запросы на передачу. Концентратор должен знать все адреса, связи и узлы и проверять их работоспособность. Оконечным узлом, в соответствии с определением 100VG-AnyLAN, может быть компьютер, мост, маршрутизатор или коммутатор.
Состязание приоритетов запроса
Как и при CSMA/CD, при доступе по приоритету запроса два компьютера могут бороться за право передать данные. Однако только последний метод реализует схему, по которой определенные типы данных — если возникло состязание, — имеют соответствующий приоритет. Получив одновременно два запроса, концентратор вначале отдаст предпочтение запросу с более высоким приоритетом. Если запросы имеют одинаковый приоритет, они будут обслужены в произвольном порядке.
В сетях с использованием доступа по приоритету запроса каждый компьютер может одновременно передавать и принимать данные (дуплексный обмен данными), поскольку для этих сетей разработана специальная схема кабеля. В них применяется восьмипроводной кабель, по каждой паре проводов сигналы передаются с частотой 25 МГц.
Опросные системы идеальны для сетевых устройств, чувствительных ко времени, например, при автоматизации оборудования.
4. Примеры протоколов множественного доступа.
Канальный уровень определяет методы форматирования данных для передачи и методы контроля доступа в сеть. В этой главе рассмотрены следующие протоколы канального уровня:
— Ethernet;
— Token Ring;
— FDDI.
FDDI, Token Ring и Ethernet могут рассматриваться как физические интерфейсы или логические протоколы, инкапсулированные в протоколы WAN или ATM.
На Рис. 4.1 показано представление протоколов ЛВС в модели OSI.
Рис. 4. 1Протоколы ЛВС в модели ISO/OSI
ANSI/ IEEE 802.3 1933-00
Широко используемый для построения компьютерных сетей стандарт Ethernet был разработан компаниями DEL, Intel и Xerox. Ethernet — самая популярная в настоящее время сетевая архитектура. Она использует узкополосную передачу со скоростью 10 Мбит/с, топологию «шина» или «звезда», а для регулирования трафика в физическом сегменте— CSMA/CD.
Сеть Ethernet имеет следующие характеристики:
топологии — линейная шина, звезда-шина;
— тип передачи — узкополосная;
— метод доступа CSMA/CD;
— скорость передачи данных кабельная система — 10 и 100 Мбит/с;
— спецификации — IEEE 802.3;
— кабельная система — толстый и тонкий коаксиальный, UTP.
Структура заголовка Ethernet показана на Рис. 4.2.
Рис. 4. 2 Структура заголовка Ethernet
Адрес получателя
Поле адреса получателя имеет структуру, показанную на Рис. 4.3.
Рис. 4. 3 Структура адреса получателя
I/G Персональный (I) или групповой (G) адрес:
0 персональный адрес DASP;
1 групповой адрес DASP.
U/L Универсалльный (U) или локальный (L) адрес:
0 универсальный адрес DASP;
1 локальный адрес DASP.
Адрес отправителя
Поле адреса отправителя имеет показанную на Рис. 4.4 структуру.
Рис. 4. 4 Структура адреса отправителя
0 Первый бит адреса отправителя всегда имеет нулевое значение.
U/L Универсальный(U) или локальный (L) адрес:
0 универсальный адрес SSAP;
1 локальный адрес SSAP.
Длина / Тип
Для протокола Ethernet это поле содержит идентификатор типа Ethernet (используемый отправителем протокол сетевого уровня – значение, превышающее 0x0600).
Для протокола 802.3 значение этого поля (46-1500) показывает длину поля данных, представляющего собой инкапсуляцию протокола LLC (заголовок LLC показывает тип вложенного протокола).
Данные + биты заполнения
Протокол LLC.
FSC
Контрольная сумма кадра.
IEEE 802.3 1995-00
Token Ring представляет собой протокол ЛВС, в которых все станции соединены в (логическое) кольцо и каждая станция может принимать данные только от своего ближайшего соседа. Разрешение на передачу определяется специальным маркером (token), передаваемым по кольцу.
Структура заголовка Token Ring показана на Рис. 4.5.
Рис. 4. 5 Структура заголовка Token Ring
SDEL / EDEL
Начальный (SDEL) или конечный (EDEL) указатель. Оба типа полей содержат преднамеренные нарушения манчестерского кодирования, которые позволяют отличить поля SDEL и EDEL в потоке другой информации.
Управление доступом
Поле управления доступом имеет формат, показанный на Рис. 4.6.
Рис. 4. 6 Структура поля упраления доступом
РРР Биты приоритета:
000 низший приоритет;
111 высший приоритет.
Т Бит маркера:
0 маркер;
1 кадр.
М Счетчик мониторинга:
0 исходное значение;
1 изменено для активного монитора.
R Биты резервирования:
000 резервирование низшего приоритета;
111 резервирование высшего приоритета.
Управление кадром
Формат поля управления кадром показан на Рис. 4.7:
Рис. 4. 7 Структура поля управления
Поле, обозначающее тип кадра может принимать следующие значения:
00 MAC-кадр;
01 кадр LLC;
10 тип кадра не определен;
11 тип кадра не определен.
Следующие два бита всегда имеют нулевые значения.
Индикатор показывает кадры, для которых адаптер использует специальные средства буферизации и обработки:
0000 экспресс-буфер;
0010 предостережение;
0011 маркер претензий;
0100 чистка кольца;
0101 присутствует активный монитор;
0110 присутствует неактивный (standby) монитор.
Адрес получателя
Поле адреса получателя имеет структуру, показанную наРис. 4.8:
Рис. 4. 8 Структура адреса получателя
I/G Персональный (I) или групповой (G) адрес:
0 персональный адрес DSAP;
1 групповой адрес DSAP.
U/L Универсальный (U) или локальный (L) адрес:
0 универсальный адрес DSAP;
1 локальный адрес DSAP.
Адрес отправителя
Поле адреса отправителя имеет общую стрктуру (Рис. 4.9):
Рис. 4. 9 Структура адреса отправителя
RII Индикатор маршрутной информации:
0 маршрутная информация отсутствует;
1 маршрутная информация присутствует.
I/G Персональный (I) или групповой (G) адрес:
0 персональный адрес SSAP;
1 групповой адрес SSAP.
Сведения о маршрутизации
Поле маршрутной информации имеет следующую стрктуру (Рис. 4.10):
Рис. 4. 10 Структура поля маршрутной информации
RC Управление маршрутизацией.
RDn Дескриптор маршрута.
RT Тип маршрутизации.
LTH Длина
D Бит направления.
LF Самый большой кадр.
r Зарезервирован.
Данные
Информационное поле (данные) может содержать данные уровня LLC или MAC. Структура поля показана на Рис. 4.11:
Рис. 4. 11 Структура инфомационного поля
VL
Длина основного вектора в октета (байтах).
VI
Идентификатор основного вектора. Поле VI имеет следующий формат, показанный на Рис. 4.12.
Рис. 4. 12 Идентификатор основного вектора
Класс отправителя и получателя
Поля класса отправителя и получателя обеспечивают корректную маршрутизацию в станции кольца:
0 станция кольца;
4 сервер конфигурационных отчетов;
5 сервер параметров кольца;
6 монитор ошибок в кольце.
Код основного вектора
Код основного вектора определяет тип этого вектора, например:
0x00 отклик;
0x02 предостережение (beacon) и т.д.
SVL
Длина субвектора в октетах (байтах).
SVI
Код субвектора определяет тип этого вектора, например:
0x00 тип предостережения (beacon);
0x02 NAUN (Next Adress. Upstream Neighbor) – адрес соседней станции, от которой приходят кадры и т.д.
SVV
Значение субвектора (информационное поле переменной длины).
FCS
Контрольная сумма кадра.
Состояние кадра
Это поле содержит биты, которые могут быть установлены получателем кадра для того, чтобы сообщить о распознавании адреса и успешном копировании кадра.
FDDI (Fiber Distributed Data Interface) представляет собой технологию передачи данных со скоростью 100 Мбит/с по двойному кольцу (из деревьвев). Стандарт FDDI предложен Американским интститутлм стандартизации (ANSI).
Структура заголовка кадра FDDI показа на на Рис. 4.13.
Рис. 4. 13 Структура заголовка FDDI
Управление кадром.
Поле управления кадром имеет следующую структуру (Рис. 4.14):
Рис. 4. 14 Структура поля управления кадром FDDI
C Бит класса:
0 асинхронный кадр;
1 синхронный кадр.
L Бит длины адреса:
0 16 битов (не используется никогда);
1 48 битов (используется всегда).
FF Биты формата.
ZZZZ Биты управления
Адрес получателя
Поле адреса получателя имеет следующую структуру (Рис. 4.15).
Рис. 4. 15 Структура адреса получателя
I/G Персональный (I) или групповой (G) адрес:
0 персональный адрес DASP;
1 групповой адрес DASP.
U/L Универсалльный (U) или локальный (L) адрес:
универсальный адрес DASP;
локальный адрес DASP.
Адрес отправителя
Поле адреса отправителя имеет общую стрктуру (Рис. 4.16):
Рис. 4. 16 Структура адреса отправителя
I/G Персональный (I) или групповой (G) адрес:
0 персональный адрес SSAP;
1 групповой адрес SSAP.
RII Индикатор маршрутной информации:
0 маршрутная информация отсутствует;
1 маршрутная информация присутствует.
Маршрутная информация
Структура поля маршрутной инфомации показана на Рис. 4.17.
Рис. 4. 17 Структура поля маршрутной информации
RC Управление маршрутизацией (16 битов).
RDn Дескриптор маршрута.
RT Тип маршрутизации.
LTH Длина
D Бит направления.
LF Самый большой кадр.
r Зарезервирован.
Данные
Информационное поле (данные) может содержать протокол LLC, MAC или SMT.
FSC
Контрольная сумма кадра.
Заключение
Задачей уровня передачи данных является преобразование необработанного потока битов, поступающего с физического уровня, в поток кадров, который может использовать сетевой уровень. В данном реферате были рассмотрены различные методы кадрирования, включая подсчет символов, символьное и битовое заполнение. Протоколы уровня передачи данных могут обладать возможностями контроля ошибок, который осуществляется при повторной передаче потерянных млм испорченных кадров.
Также в данной работе рассмотрены протоколы множественного доступа, такие как семейства протоколов ALOHA и CSMA. Даны описания работы протоколов и оценена их эффективность. Приведены сравнительные графики КПД протоколов.
Были рассмотрены примеры конкретных протоколов (Ethernet, Token Ring, FDDI).
Список источников
1. Э. Таненбаум. Компьютерные сети, 4-е изд.— Питер. 2005.
2. К.Е. Самуйлов, Д.С. Кулябов. Учебно-методическое пособие по курсу «Сети и системы телекоммуникаций».- М.: РУДН.- 2002.— www.telesys.pfu.edu.ru/studies/book/kulyabov-nets-st.pdf
3. С. Пушкин. Передача данных по кабелю // Компьютерные решения.— № 34, 2000.— krmagazine.ru/?archive/34/article7
4. Доступ к среде передачи данных // сайт Красноярского государственного технического университета.— www.kgtu.runnet.ru/WD/TUTOR/cn/mac.html
5. Протоколы канального уровня ЛВС // REDCOM, Ltd., 1999, Перевод на русский. BILIM Systems Ltd., 2000.— www.bilim.com