Канальный уровень (Data Link layer)
Сервис, предоставляемый сетевому уровню
Доступ к среде передачи данных
Проблема предоставления канала
Статическое предоставление канала
Динамическое предоставление канала
Протоколы множественного доступа
Протоколы множественного доступа с обнаружением несущей
Протоколы с ограниченным числом конфликтов
Протоколы с множественным доступом и разделением частот
Канальный уровень (Data Link layer)
Этот уровень предназначен для обеспечения взаимодействия сетей на физическом уровне и контроля за ошибками, которые могут возникнуть. Полученные с физического уровня данные он упаковывает в кадры данных, проверяет на целостность, если нужно исправляет ошибки и отправляет на сетевой уровень. Канальный уровень может взаимодействовать с одним или несколькими физическими уровнями, контролируя и управляя этим взаимодействием. Спецификация IEEE 802 разделяет этот уровень на 2 подуровня — MAC (Media Access Control) регулирует доступ к разделяемой физической среде, LLC (Logical Link Control) обеспечивает обслуживание сетевого уровня. На этом уровне работают коммутаторы, мосты.
Проблемы передачи по каналу.
Сервис, предоставляемый сетевому уровню
Основной задачей канального уровня обеспечить сервис сетевому уровню. Назначение этого сервиса - помочь передать данные процесса на сетевом уровне одной машины процессу на сетевой уровень другой машины.
Канальный уровень может создаваться для различного сервиса, который может варьироваться от системы к системе. Однако, есть три общие вида сервиса:
- Сервис без уведомления и без соединения.
- Сервис с уведомлением и без соединения.
- Сервис с уведомлением и с соединением.
Не желательно на сетевом уровне заниматься пропажей кадров. Это задача канального уровня обеспечить надежный канал. Это особенно важно при беспроводной среде передачи.
Разбиение на кадры
Сервис, создаваемый канальным уровнем для сетевого, опирается на сервис, создаваемый физическим уровнем. На физическом уровне протекают потоки битов. Посланное количество битов не обязательно равно принятому, значение посланного бита так же не обязательно равно принятому. Все это требует специальных усилий на канальном уровне по обнаружению и исправлению ошибок.
Типовой подход к решению этой проблемы - разбиение потока битов на кадры, подсчет контрольной суммы для каждого кадра при посылке данных. При приеме контрольная сумма вычисляется для каждого кадра заново и сравнивается с той что храниться в кадре. Если они различаются, то это признак ошибки передачи. Канальный уровень должен принять меры к исправлению ошибки, например, сбросить плохой кадр, послать сообщение об ошибке тому кто прислал этот кадр.
Так как временные методы ненадежны, то применяются другие. Здесь мы рассмотрим четыре основных:
- счетчик символов
- вставка специальных стартовых и конечных символов
- вставка стартовых и концевых битов
- нарушение кодировки на физическом уровне
На практике используют, как правило, комбинацию этих методов. Например, счетчик символов с одним из выше перечисленных. Тогда если число символов в кадре совпадает с кодировкой границы кадра, кадр считается переданным правильно.
Контроль ошибок.
Таймеры и нумерация кадров - это основные средства на канальном уровне, обеспечивающие доставку каждого кадра до сетевого уровня в единственном экземпляре
Обнаружение и исправление ошибок
В разных средах характер ошибок разный. Ошибки могут быть одиночные, а могут возникать группами, сразу по несколько.
Для надежной передачи кодов было предложено два основных метода. Первый - внести избыточность в форме дополнительных битов в передаваемый блок данных так, чтобы, анализируя полученный блок, можно было бы указать где возникли искажения. Это, так называемые, коды с исправлением ошибок. Второй - внести избыточность, но лишь настолько, чтобы, анализируя полученные данные, можно было сказать есть в переданном блоке ошибки или нет. Это, так называемые, коды с обнаружением ошибок.
Коды с исправлением ошибок- Код хемминга(может исправлять только единичные ошибки. Однако, есть прием, который позволяет распространить идеи Хемминга на случай групповых ошибок)
Коды обнаруживающие ошибки- CRC код(Cyclic Redundancy Code)
(CRC-16 и CRC-CCITT ловят одиночные, двойные ошибки, групповые ошибки длины не более 16 и нечетное число изолированных ошибок с вероятностью 99,997%.)
Управление потоком.
Доступ к среде передачи данных
В средах с множественным доступом ключевым является вопрос: как определить кому из запросивших отдать канал? Протоколы для определения кто захватит канал в случае конкуренции относятся к подуровню канального уровня, который называется МАС - Medium Access Control.
Проблема предоставления канала
Основной вопрос - как распределять единственный канал между многими конкурирующими пользователями.
Статическое предоставление канала
Как мы уже рассматривали ранее есть два основных подхода к мультиплексированию нескольких конкурирующих пользователей на одном канале - частотное разделение (FDM-Frequency Division Multiplexing).Частотное разделение хорошо работает в условиях, когда число пользователей фиксировано и каждый порождает плотную загрузку канала. Тогда каждому из них выделяется своя полоса частот, которую он использует независимо от других. Однако, когда число пользователей велико или величина переменная, или когда трафик очень не регулярный,у FDM появляются проблемы.
Те же самые рассуждения можно применить к временному разделению (TDM-Time Division Multiplexing). Таким образом, ни один из известных статических методов не позволяет эффективно распределять нагрузку.
Динамическое предоставление канала
Протоколы множественного доступа
Чистая 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.
Рассмотрим как влияет на пропускную способность подсчитаем
вероятность успешной передачи за 
попыток. Так как вероятность отсутствия коллизии при
передаче, то вероятность что кадр будет передан ровно за попыток, равна
Среднее ожидаемое число повторных передач будет 
Эта экспоненциальная зависимость показывает, что с ростом резко возрастает число
повторных попыток, а следовательно и общая пропускная способность канала.
Протоколы множественного доступа с обнаружением несущей
В локальных сетях есть возможность определить, что делают другие станции и только после этого решать, что делать.
Протоколы, которые реализую именно эту идею - определить есть ли передача и действовать соответствующе, называются протоколами с обнаружением несущей CSMA (Carrier Sense Multiply Access).
Настойчивые и не настойчивые CSMA.
Согласно протоколу, который мы сейчас рассмотрим, станция прежде чем что-либо
передавать определяет состояние канала. Если канал занят, то она ждет. Как
только канал освободился она пытается начать передачу. Если при этом произошла
коллизия, она ожидает случайный интервал времени и все начинает с начала. Этот
протокол называется CSMA настойчивым протоколом первого уровня или 1-настойчивым
CSMA протоколом, потому что он начинает передачу с вероятностью 1 как
только обнаруживает, что канал свободен.
Другой вариант CSMA - не настойчивый CSMA протокол. Основное отличие его от предыдущего в том, что готовая к передаче станция не опрашивает постоянно канал, в ожидании когда он освободиться, а делает это через случайные отрезки времени. Это несколько увеличивает задержку при передаче, но общая эффективность возрастает.
И ,наконец, CSMA настойчивый протокол уровня р. Он применяется к слотированным каналам. Когда станция готова к передаче она опрашивает канал, если он свободен, то она с вероятностью р передает свой кадр и с вероятностью q=1-p ждет следующего слота. Так она действует пока не передаст кадр. Если произошла коллизия вовремя передачи, она ожидает случайный интервал времени и опрашивает канал опять. Если при опросе канала он оказался занят, станция ждет начала следующего слота и весь алгоритм повторяется. На рисунке показана пропускная способность в зависимости от нагрузки.
CSMA с обнаружением коллизий
Настойчивые и ненастойчивые CSMA протоколы несомненно есть улучшение ALOHA,
т.к. они начинают передачу только проверив состояние канала. Другим улучшением,
которое можно сделать, - станции должны уметь определять коллизии как можно
раньше, а не по окончании отправки кадра. Это экономит время и пропускную
способность канала. Такой протокол, известный как CSMA/CD - Carrier Sense
Multiply Access with Collision Detection , широко используется в локальных
сетях.
Бесконфликтные протоколы
Bit-Map протокол
Идея этого метода показана на рисунке:
Выделяется специальный период состязаний, где количество слотов равно числу станций. Каждая станция, имеющая кадр для передачи , проставляет 1 в свой слот. В результате, в конце состязаний все станции знают кто будет передавать и в каком порядке. Передача происходит в том же порядке, в каком пронумерованы слоты. Раз станции знают кто будет передавать и в каком порядке конфликтов не будет. Если станция опоздала с заявкой на передачу, то она должна ждать следующего периода состязаний, который начнется по окончании передач, заявленных на предыдущем периоде состязаний. Такие протоколы, когда заявки на передачу откладываются и могут быть сделаны лишь в определенные периоды времени называются протоколами с резервированием.
Адресный счетчик
В этом методе каждая станция, желающая передать выставляет свой адрес бит за
битом, начиная со старшего разряда. Эти разряды подвергаются логическому
сложению. Если станция выставила на очередном шаге 0, а результат логического
сложения - 1, то она должна ждать и в текущих состязаниях участия не принимает.
Этот метод проиллюстрирован на рисунке левее. Эффективность этого метода d/(d +
log2N)
Протоколы с ограниченным числом конфликтов
Существую протоколы, объединяющие в себе свойства 2 предыдущих групп. Эти протоколы называются протоколы с ограниченным числом конфликтов.
Общая производительность системы может быть улучшена если разным станциям будет сопоставлена разная вероятность.
График этой функции показан на рисунке левее. При небольшом числе станций шансы передать кадр достаточно велики, но с ростом числа станций они резко падают. Единственным способом увеличить шансы на передачу сократить состязания. Для этого в протоколах с ограниченным числом конфликтов все станции разбиваются на непересекающиеся группы. За слот с номером 0 состязаются только станции из группы 0. Если передавать нечего или была коллизия, то члены группы 1 начинают состязания за слот 1 и т.д. Основную сложность составляет распределение станций по группам.
Адаптивный древовидный протокол.
На рисунке показано как эта процедура протокола применяется к станциями. Станции - листья. За слот 0 борются все станции. Если какая-то победила - хорошо. Если нет, то за слот 1 борются только станции поддерева с корнем в вершине 2. Если какая-то победила, то следующий слот резервируется для станций поддерева 3. Если был конфликт, то за следующий слот борются станции поддерева 4 и т.д.
Протоколы с множественным доступом и разделением частот
рассмотрим работу протоколов множественного доступа для оптоволоконных систем. Они построены на идее разделения частот. Вся полоса разделяется на каналы по два на станцию. Они узкий - управляющий канал, второй широкий для передачи данных. Каждый канал разбит на слоты. Все слоты синхронизируются от единых часов. Отмечается только 0 слот, чтобы можно было определить начало каждого цикла.
