Проблемы передачи данных на канальном уровне (Сервис, предоставляемый сетевому уровню, Разбиение на кадры, Контроль ошибок, Управление потоком). Простейшие протоколы канала данных (Симплекс протокол без ограничений, Симплекс старт стопный протокол, Симплексный протокол для канала с шумом).

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

1. Сервис без уведомления и без соединения

2. Сервис с уведомлением и без соединения

3. Сервис с уведомлением и с соединением

Сервис без уведомления и без соединения не предполагает, что до начала передачи должно быть установлено соединение, которое после передачи должно быть разорвано, что факт приема переданного кадра должен подтверждаться специальным сообщением. Если в результате помех на физическом уровне кадр будет потерян, то никаких попыток его восстановить на канальном уровне произведено не будет. Следующий вид сервиса – сервис с уведомлением без соединения. В этом виде сервиса получение каждого посланного кадра должно быть подтверждено. Если подтверждения не пришло в течение определенного промежутка времени, то считают, что кадр не принят и должен быть послан опять. Наиболее сложный класс сервиса на канальном уровне - сервис с соединением и уведомлением. Этот класс сервиса предполагает, что до начала передачи между машинами устанавливают соединение и данные передают по этому соединению. Каждый передаваемый кадр нумеруется, и канальный уровень гарантирует, что он будет обязательно получен, причем только один раз, а также что все кадры будут получены в надлежащей последовательности. При сервисе без соединения этого гарантировать нельзя, потому что потеря подтверждения получения кадра приведет к его пересылке, что, в свою очередь, приведет к появлению нескольких идентичных кадров. Использование сервиса с соединением особенно полезно в том случае, когда канал образует СПД. Как мы уже видели, в СПД может быть достаточно сложная организация канала, при которой может происходить коммутация потоков данных самыми разными способами. Здесь полезно вспомнить структуру кадра в Х.25, рассмотренную в разделе 2.3. С точки зрения структуры, в Х.25 есть три вида кадров: с 3-битовым полем номера кадра, 7- и 12-битовым. Таким образом, в Х.25 предусмотрен сервис с соединением, причем, в зависимости от длины передаваемых данных, можно оптимизировать затраты на поддержку соединения. При сервисе с соединением и уведомлением передача данных разбивается на три этапа. На первом этапе устанавливают соединение: на обеих машинах инициируют переменные и счетчики, отслеживающие, кадры с какими номерами были приняты, а с какими нет. На втором этапе передают нужные кадры. На третьем - соединение разрывают. Разбиение на кадры. Сервис, создаваемый канальным уровнем для сетевого уровня, опирается на сервис, создаваемый физическим уровнем. Отправленное количество битов не обязательно должно быть равно принятому количеству битов, значение посланного бита также не обязательно должно быть равно принятому значению бита. Поэтому на канальном уровне нужны специальные действия по обнаружению и исправлению таких ошибок. Типовой подход к решению подобных проблем - разбиение потока битов на кадры, подсчет контрольной суммы для каждого кадра и передача этой суммы вместе с кадром данных. При приеме контрольная сумма вычисляется для каждого кадра заново и сравнивается с той, что хранится в кадре. Если они различаются, то это признак ошибки передачи. На канальном уровне должны быть приняты меры к исправлению ошибки, например, сбросить плохой кадр и послать сообщение об ошибке тому, кто прислал этот кадр. четыре основных метода:

1. счетчик символов . 2. вставка специальных стартовых и конечных символов

3.вставка стартовых и концевых битов; 4.нарушение кодировки на физическом уровне

1 - В начале каждого кадра указывают, сколько символов в кадре. При приеме кадра вновь подсчитывают число принятых символов. Если число полученных символов отлично от ожидаемого числа, то этот факт воспринимают как ошибку. Однако этот метод имеет существенный недостаток: счетчик символов может быть искажен при передаче. Тогда принимающая сторона не сможет обнаружить границы кадра. Даже обнаружив несовпадение контрольных сумм, принимающая сторона не сможет сообщить передающей, какой кадр надо переслать и сколько символов пропало. Этот метод сейчас используется редко. Второй метод построен на вставке специальных символов. Обычно для этого используют последовательность символов DLE STX для начала кадра и DLE ETX для конца кадра. DLE (Data Link Escape), STX (Start TeXt), ETX (End TeXt) – это специальные символы, имеющие специальную кодировку. При этом методе, если даже была потеряна граница текущего кадра, нужно просто найти ближайшую последовательность DLE STX или DLE ETX. Однако здесь есть одна опасность: при передаче чисел или программы в объектном коде такие последовательности могут уже содержаться в передаваемых данных. Для решения этой проблемы используют прием экранирования: каждая последовательность DLE или STX просто дублируется в передаваемых данных. Поэтому, если при приеме есть два последовательных DLE, то один удаляется. Основным недостатком только что рассмотренного метода является то, что он жестко связан с размером байта и конкретным методом кодировки символов - ASCII. По мере развития сетей эта связь становилась все более и более обременительной. Кроме этого, на стороне отправителя надо было просматривать кадр, чтобы обнаружить недопустимые последовательности. Был предложен иной прием, позволяющий использовать любое число битов на символ и любую кодировку. Его идея состоит в том, что каждый кадр начинается и заканчивается специальным флаг-байтом: 01111110. Этот метод прозрачен для сетевого уровня так же, как и метод вставки байтов. Таким образом, кадр легко может быть распознан по флаг-байту. Если граница очередного кадра по какой-то причине была потеряна, то все что надо делать – «ловить» ближайший флаг-байт. Последний метод - нарушение кодировки используется там, где применяется специальная кодировка битов на физическом уровне. Например, пусть для передачи одного бита используется два импульса. «1» кодируется как переход «высокое-низкое», «0» - как переход «низкое-высокое». Их и используют для границ кадра. На практике используют, как правило, комбинацию этих методов. Например, счетчик символов с одним из выше перечисленных. Обнаружение ошибок. Для решения этой проблемы устанавливают обратную связь между отправителем и получателем в виде кадра подтверждения. Если кадр-подтверждение несет положительную информацию, то считается, что переданные кадры прошли нормально, если же в нем сообщение об ошибке, то переданные кадры надо передать заново. Однако возможны ситуации, когда из-за ошибок в канале кадр исчезнет целиком. В этом случае получатель не будет никак реагировать, а отправитель будет сколь угодно долго ждать подтверждения. Для решения этой проблемы на канальном уровне вводят таймеры. Когда передается очередной кадр, то одновременно устанавливается таймер на определенное время. Этого времени должно хватать на то, чтобы получатель получил кадр и отправил уведомление, а отправитель получил его. Если отправитель не получит уведомление раньше, чем истечет время, установленное на таймере, то он будет считать, что кадр потерян и повторит его еще раз. Однако если кадр-подтверждение был утерян, то вполне возможно, что один и тот же кадр получатель получит дважды. Как быть? Для решения этой проблемы каждому кадру присваивают порядковый номер. С помощью этого номера получатель может обнаружить дубли. Итак, таймеры и нумерация кадров - основные средства на канальном уровне, обеспечивающие доставку каждого кадра до сетевого уровня в единственном экземпляре и в нужном порядке. Управление потоком .Другая важная проблема, которую надо решать на канальном уровне - управление потоком. Вполне может случиться, что отправитель будет посылать кадры столь часто, что получатель не будет успевать их обрабатывать. Для борьбы с такими ситуациями вводят специальный механизм управления потоком. Существует много схем управления потоком, но все они в основе своей используют следующий сценарий. Прежде чем отправитель начнет передачу, он спрашивает у получателя, сколько кадров тот может принять. Получатель сообщает ему определенное число. Отправитель, после того как передаст это число кадров, должен приостановить передачу и спросить у получателя еще раз, сколько кадров тот может принять, и т.д. Позднее на примерах мы познакомимся с конкретными механизмами управления потоком.

Простейшие протоколы канала данных

Рассмотрение протоколов уровня канала данных мы начнем с нескольких предположений. Будем предполагать, что физический уровень, уровень канала данных, сетевой уровень – реализованы в виде независимых процессов, взаимодействующих с помощью передачи сообщений. Также мы предположим, что есть две машины: А и В. У машины А есть бесконечно длинный набор данных, который надо передать машине В с помощью надежного сервиса, ориентированного на соединение. Передача всегда происходит от А к В, хотя позднее мы допустим одновременную передачу от В к А. Также будем предполагать, что если канальный уровень на машине А запрашивает данные для передачи от сетевого уровня, то они всегда есть и нет задержки на их подготовку. Канальный уровень рассматривает данные, которые он получает от сетевого, как неструктурированные, несмотря на то, что там есть хотя бы заголовок сетевого уровня. Все эти данные должны быть переданы равнозначному сетевому уровню. Когда канальный уровень получает пакет, он погружает его в кадр, добавляя заголовок и концевик. Этот кадр затем передается по физическому уровню.

Симплекс-протокол без ограничений

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

Симплексный старт-стопный протокол

Теперь снимем одно из ограничений предыдущего протокола - способность сетевого уровня обрабатывать поступающие данные сколь угодно быстро. Все остальные предположения остаются в силе: канал абсолютно надежный, трафик однонаправленный. Основная проблема - как предотвратить ситуацию, когда отправитель «заваливает» данными получателя. Если получателю требуется время Δt, чтобы исполнить from_physical_layer плюс to_network_layer, то отправитель должен передавать данные со средней скоростью один кадр в Δt. Решением такой проблемы может быть введение коротких специальных служебных сообщений. Получатель, получив один или несколько кадров, отправляет отправителю короткий специальный кадр, означающий, что отправитель может передавать следующий.

Симплексный протокол для канала с шумом

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

Протоколы скользящего окна

Для передачи в обоих направлениях можно потребовать на физическом уровне двух симплексных каналов. Один для передачи кадров, другой - для передачи подтверждений. Однако использование канала только для подтверждений - довольно дорогое удовольствие. Можно смешивать кадры с данными и кадры с подтверждениями на одном канале. Это, конечно. решение проблемы, но по-прежнему на подтверждения будет тратиться полезная пропускная способность канала. А что, если для подтверждения использовать полезные кадры с данными? Получатель не сразу отправляет подтверждение, а ожидает от сетевого уровня очередного пакета. Как только такой пакет возникает, то канальный уровень помещает в кадр с пакетом также уведомление о получении в специальное поле ack. Что делать, если тайм-аут у отправителя на получения подтверждения заканчивается, а с сетевого уровня получателя не поступает запроса на передачу пакета? Поэтому на канальном уровне должен быть фиксированный интервал времени, в течение которого канальный уровень ждет от сетевого попутного кадра. Если до истечения этого срока пакет с сетевого уровня не поступил, то канальный уровень отправляет подтверждение отдельным кадром. Рассмотренный здесь протокол является представителем класса протоколов скользящего окна. Кроме вышесказанного, протоколы этого класса делают следующее: у отправителя и получателя есть определенная константа n - число кадров, которое отправитель может послать, не ожидая подтверждения для каждого кадра. По мере получения подтверждений отправленные кадры будут сбрасываться из буфера отправителя, и буфер будет пополняться новыми кадрами. У получателя и отправителя есть набор последовательных чисел - номеров кадров,   которые отправитель может отправить, не ожидая подтверждения каждого.   Эти кадры образуют окно отправки.   Аналогично, у получателя есть буфер для получения и временного хранения получаемых кадров - окно получения. Хотя в этих условиях у отправителя есть определенная свобода в порядке отправления кадров, мы по-прежнему будем считать, что кадры отправляют в соответствии с порядковыми номерами. У окон отправки и получения есть верхняя и нижняя границы. Порядковые номера кадров в окне отправки - кадры отправленные, но не подтвержденные. Как только от сетевого уровня поступил еще один пакет, ему присваивают первый свободный наибольший номер, и верхняя граница окна отправителя поднимается. Как только приходит подтверждение, нижняя граница окна поднимается. Таким образом, в окне все время находятся неподтвержденные кадры.

Протокол скользящего окна в 1 бит

Прежде чем переходить к общему случаю, рассмотрим протокол скользящего окна с максимальным размером окна в 1 бит. Такой протокол использует старт-стопный режим и, послав кадр, не шлет другой, пока не придет подтверждение на первый. На рисунке 3-13 показан текст протокола для этого простейшего случая. Как и все, он начинается с определения переменных. Next_frame_to_send указывает, какой кадр посылается. Переменная frame_expected определяет, какой кадр получатель ожидает. Есть только два значения - 0 или 1. Есть два случая: первый - простой и наиболее удобный, когда только один из канальных уровней первым начинает передачу. В этом случае вне тела основного цикла одной из программ канального уровня есть обращения к процедурам to_phisical_layer и start_timer. Случай, когда оба уровня одновременно могут начинать передачу, описывается позже, поскольку он требует более детального рассмотрения. Машина, инициирующая обмен, берет пакет от сетевого уровня, формирует кадр и посылает его. Когда он (или любой другой кадр) поступает, канальный уровень-получатель проверяет: не является ли этот кадр дубликатом. Если поступивший кадр тот, что ожидался, то он передается на сетевой уровень и окно получателя сдвигается вверх.

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

Протокол с возвратом на n кадров и протокол с выборочным повтором

До сих пор мы предполагали, что время доставки кадра и время доставки подтверждения пренебрежимо малы. В некоторых случаях это предположение очевидно не работает. Оно может приводить к серьезным бесполезным тратам пропускной способности канала. потеря пропускной способности канала. Эта проблема есть следствие правила, по которому отправитель ждет подтверждения прежде, чем пошлет следующий кадр. Это требование можно ослабить - разрешить отправителю отправлять до w кадров, не дожидаясь их подтверждения. Надлежащим выбором значения w отправитель может заполнить все время, необходимое на отправку кадра и получение его подтверждения. Эта техника известна как конвейер. Ее применение в случае ненадежного канала наталкивается на ряд проблем. Первая - что делать, если в середине потока пропадет или попадется поврежденный кадр? Получатель уже получит большое количество кадров к тому моменту, когда отправитель обнаружит, что что-то произошло. Когда получатель получил поврежденный кадр, он его должен сбросить, что делать с последующими кадрами? Помните, что канальный уровень обязан передавать пакеты на сетевой уровень в том порядке, в каком их отправлял отправитель. Есть два приема для решения этих вопросов: откат и выборочный повтор. При откате все кадры, поступившие после поврежденного кадра, сбрасываются и не подтверждаются. Отправитель по тайм-ауту повторно отправляет все кадры, начиная с первого неподтвержденного кадра. Этот подход показан на рисунке 3-15 (а), где размер окна у получателя - 1. При выборочном повторе у получателя длина окна такая же, как и у отправителя. Отправитель отмечает неподтвержденный кадр и посылает его еще раз. Получатель не передает на сетевой уровень последовательность пакетов, если в ней есть разрывы.

Примеры протоколов канала данных.

Протокол HDLC (High Level Data Link Control)

До сих пор мы рассматривали решение основных проблем, с которыми приходится иметь дело на канальном уровне. Теперь мы познакомимся с группой давно известных, но по-прежнему широко используемых на практике протоколов. Все они имеют одного предшественника - SDLC (Synchronous Data Link Control) - протокола управления синхронным каналом, предложенного фирмой IBM в рамках архитектуры SNA. ISO модифицировало этот протокол и выпустило под название HDLC - High level Data Link Control. МКТТ модифицировало HDLC для X.25 и выпустило под именем LAP - Link Access Procedure. Позднее он был модифицирован в LAPB. Все эти протоколы построены на одних и тех же принципах. Они используют технику вставки специальных последовательностей битов и являются бит–ориентированными протоколами. Различия между ними незначительные.