Канальный уровень сети X.25

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 22:33, 26 января 2015.
Данная статья была согласована с её автором Р.А. Бельферым 28 апреля 2012 года.

__NUMBEREDHEADINGS__

Временная диаграмма последовательности обмена кадрами

Настоящая глава посвящена описанию основной процедуры второго (канального) уровня сети X.25 (X.25/2) – обеспечению безошибочного обмена информационными кадрами, передаваемых по подверженным помехам каналам связи[1][2]. Эта функция называется управление потоками и используется не только для сети пакетной коммутации стандарта Х.25, но и для других сетей, обеспечивающих службу передачи данных. При этом алгоритм реализации этой функции отличается в сетях разных технологий. Для сетей связи, обеспечивающих службу телефонии или видео, управление потоком не производится. Основной принцип управления потоками в Х.25/2 состоит в следующем. Передаваемый информационный кадр сохраняется в памяти передающего узла, ожидая приема квитанции о правильном приеме кадра узлом-получателем. В качестве этих узлов могут быть смежные транзитные коммутаторы или оконечный коммутатор. В следующей главе приводится описание структурных схем программного обеспечения по реализации функции управления потоками в Х.25/2. Поэтому в настоящей главе приводится относительно подробное описание этой функции. Под кадром понимается элемент данных протокола PDU X.25/2 (между оконечным пунктом и ЦКП или между смежными ЦКП). Помехи в канале связи могут вызывать потерю, дублирование, искажение кадра, нарушение порядка прибытия кадра адресату. Кадр состоит из последовательности байтов. В начале и в конце кадра устанавливается синхронизирующий байт для определения начала и конца кадра. Этот синхронизирующий байт («01111110») называется флагом, а процедура обеспечения синхронизации бит-стаффингом. Для того чтобы можно было передавать байт такого содержания в информационной части кадра перед передачей после пяти непрерывных информационных «1» производится вставка «0» и изъятие этого бита на приеме.

Выполнение функции безошибочного обмена информационными кадрами обеспечивается подмножеством высокоуровневого протокола управления каналом HDLC (High-level Data Link Control) - процедурой сбалансированного доступа LAP-B (Link Access Protocol-Balanced). Этот протокол обеспечивает режим работы, в котором оба взаимодействующих в соединении узла равноправны.

Для описания алгоритма работы канального уровня сети Х.25 используются примитивы. Примитивами являются блоки данных определенного вида, которые передаются между уровнями системы для вызова различных процедур. Примитивы определяются согласно рекомендации ITU-T Х.210. На рис. 1 представлен обмен примитивами между уровнями модели OSI. Показаны четыре типа примитивов – запрос, индикация, ответ, подтверждение.

Рис. 1. Обмен примитивами между уровнями модели OSI

В некоторых случаях достаточно двух типов примитивов (запрос, подтверждение).

На рис. 2 приведена временная диаграмма последовательности обмена кадрами при установлении соединения, передача одного информационного кадра и разъединение соединения. Приведём эту последовательность.

Рис. 2. Временная диаграмма последовательности обмена кадрами при установлении соединения, передаче информационного кадра и разъединении канального соединения
  1. С сетевого уровня на канальный уровень станции A передаётся примитив «Запрос соединения». При выполнении этого примитива в канал связи с канального уровня передаётся кадр SABM о запросе соединения.
  2. При поступлении этого кадра на станцию Б он передаётся канальным уровнем на сетевой уровень в виде примитива «Индикация запроса соединения», в ответ на который выдается примитив «Ответ на запрос соединения». В результате в канал с канального уровня отправляется кадр UA о согласии на соединение.
  3. После приёма этого кадра с канального уровня на сетевой уровень станции Б направляется примитив «Подтверждение соединения».
  4. С сетевого уровня на канальный уровень станции А передаётся примитив «Запрос на посылку пакета данных». При выполнении этого примитива в канал связи с канального уровня передаётся информационный кадр «I» на противоположную станцию.
  5. Кадр «I», поступивший со станции А, передаёт сетевому уровню пакет данных с помощью примитива «Индикация прибытия правильного пакета данных».
  6. С канального уровня станции Б в канал передаётся кадр «RR» подтверждения приёма правильного пакета данных.

Как видно из рис. 2, далее показан обмен примитивами и кадрами (DISC и UA) фазы завершения работы соединения.

Формат кадра

На рис. 3 приведен формат информационного кадра Х.25. Этот формат включает заголовок кадра З2, концевик кадра К2 и пакет данных третьего уровня. Кадр обрамляется флагами (F). Основным полем заголовка З2 является поле управления потоком, в котором основными характеристиками являются тип кадра и номера передаваемого и принимаемого информационного кадра: соответственно – N(S) и N(R).

Управление потоком в канале (например, между смежными узлами в сети X.25) состоит в следущем. Передаваемый кадр сохраняется в буфере передающего узла, ожидая приёма квитанции о правильном приёме кадра узла получателя. Если кадр был искажен в канале, то передача должна быть повторена.

Поле «Данные» (пакет сетевого уровня «Д») присутствует только в информационном кадре («I»). З3 означает заголовок пакета «Д». Концевик включает в себя контрольно-проверочную комбинацию КПК (К2), необходимую для выявления кадров, искаженных помехами в канале. Кроме информационных кадров в процедуре используются супервизорные кадры RR, REJ для подтверждения или запроса повторной передачи «I» кадров, принятых с искажениями из-за помех в канале, а также кадр RNR для приостановки передачи информационных кадров при перегрузке принимающей стороны. Эти кадры включают только параметр N(R). Ненумерованные кадры (SABM, DISK, UA и др.) служат, например, для установления или разъединения соединений между смежными узлами коммутации.

Рис. 3. Формат информационного кадра Х.25

Убедимся в необходимости применения при службе передачи данных схем обнаружения ошибок в принимаемых кадрах. Для этого определим вероятность появления таких искаженных кадров. Обозначим вероятность единичного ошибочного бита через Рв – эта характеристика канала, именуемая также частотой ошибочных битов (bit error rate – BER). При использовании каналов в сети Х.25 эта величина может составлять Рв=0,0001. Если считать, что в канале возникают одиночные ошибки, статически независимые, то при длине кадра Х.25 порядка L=128 байт вероятность безошибочного приема кадра , т.е. каждый десятый кадр искажен на приеме.

Частота появления ошибочных бит в аналоговом канале сети Х.25 нередко составляет даже . Ошибки в каналах связи чаще бывают не единичными, а групповыми, то есть имеет место пакетирование ошибок. Это значительно уменьшает частоту искаженных кадров.

Полученный результат свидетельствует о необходимости применения схем обнаружения ошибок. Работа всех методов обнаружения ошибок основывается на использовании помехоустойчивого кодирования. На передающей стороне заголовок З2 и информационная часть, которая присутствует только в информационных кадрах, представляется как последовательность из k бит, которую требуется защитить от ошибок. К данной последовательности добавляется контрольно-проверочная комбинация КПК, которая вычисляется по определенному алгоритму как функция k битов передаваемого кадра. В результате формируется кодовая комбинация, имеющая длину n бит и включающая контрольно-проверочную комбинацию (n-k) бит (рис. 4). На приеме из кадра выделяется КПК. На основании принятых k бит приемник вычисляет КПК и сверяет результат вычисления с принятой КПК. Если принятая и вычисленная КПК не совпадают, кадр считается искаженным и аннулируется. В сети Х.25 используется один из наиболее широко используемых методов обнаружения ошибок – с помощью циклического избыточного кода CRC (Cyclic redundancy check). В сети X.25 n-k = 16 бит.

Рис. 4. Контрольно-проверочная комбинация в составе кадра из n бит

В разделе 4 приводится описание кода CRC тремя способами: с помощью арифметики по модулю 2, с использованием полинома, аппаратная реализация. Циклический код используется не только в сетях X.25, но и в IP - сетях, в беспроводных сетях стандарта GSM и др.

Восстановление информационных кадров

Приведем описание алгоритма передачи последовательности кадров Х.25 в условиях помех в каналах связи. Такой алгоритм называется управлением потоками на канальном уровне. Все передаваемые «I» кадры заносятся в буфер передатчика и ожидают получения положительного подтверждения от противоположной принимающей стороны. По запросу противоположной стороны производится повторная выдача из буфера принятых с искажениями «I» кадров. В измененном алгоритме восстановление блоков данных из-за помех в каналах связи применяется и в других технологиях сетей связи как, например, на транспортном уровне IP-сети, в сети ТфОП и др. Достаточно подробное изложение алгоритма управления потоками в Х.25 приводится для описания в следующей главе принципов составления алгоритмов программного обеспечения.

На канальном уровне Х.25 восстановление искаженных кадров предусматривает нумерацию передаваемых «I» кадров. Для описания метода в рекомендации ITU-T Х.25 введены следующие обозначения:

  • V(S) – переменная состояния передачи.
  • N(S) – порядковый номер передаваемого кадра «I». N(S) устанавливается равным V(S).
  • V(R) – переменная состояния приема.
  • N(R) - порядковый номер I-кадра, ожидаемого на прием.

V(S) означает текущий порядковый номер кадра «I», содержащего пакет данных и подлежащего передаче на физический уровень. Переменная V(S) в нормальном режиме функционирования звена данных принимает значения по модулю 8 (в цикле от 0 до 7), в расширенном режиме - по модулю 128 (в цикле от 0 до 127). Расширенная нумерация применяется в каналах с большим временем задержки (межконтинентальная связь или спутниковые каналы). По окончании передачи кадра значение V(S) увеличивается на единицу.

Переменная V(R) содержит текущее значение порядкового номера очередного кадра «I», который ожидают на приеме. Для V(R), как и для V(S), приняты нормальный и расширенный режимы нумерации. После приема I-кадра, в котором не обнаружены ошибки, и номер которого совпадает с ожидаемым приемной стороной N(S)=V(R), значение V(R) увеличивается на единицу.

N(R) – порядковый номер I-кадра, ожидаемого на прием. N(R) содержится в заголовке (З2) принимаемых кадров «I» и в супервизорных кадрах RR, REJ, RNR. N(R) в кадрах RR и «I» указывает, что переданные с противоположной стороны канала кадры «I» с номерами N(S)<N(R) были приняты правильно.

Информационный кадр «I» содержит оба параметра N(S) и N(R). Информационные кадры стираются из буфера повторной передачи при подтверждении правильного приема.

Супервизорный кадр готовность к приему RR (receive ready) является положительной квитанцией, поступающей от принимающей стороны, и указывает на то, что переданные «I» кадры с номерами N(S)<N(R) приняты правильно и могут быть стерты из буфера повторной передачи. Здесь N(R) является параметром кадра RR. В случае приема «I» кадра входящий в него параметр N(R) также является положительной квитанцией кадров буфера с N(S)<N(R).

Супервизорный кадр отказ REJ (reject) является отрицательной квитанцией и указывает, что «I» кадры, с номерами N(S)<N(R) приняты правильно. А кадры с номерами, начиная с N(S)=N(R), должны быть повторно переданы из буфера. Повтор из буфера «I» кадров может потребоваться также по истечении определенного времени, в течение которого не была получена положительная квитанция RR о приеме. Предельное число «I» кадров, переданных и не получивших подтверждение RR, называется шириной окна W. В этом случае очередной пакет данных с сетевого уровня не инкапсулируется в кадр «I» для передачи в канал.

Если в приемник поступил «I» кадр, в котором не обнаружены ошибки и с ожидаемым номером N(R), то служебные поля канального уровня (З2 и К2) отбрасываются, и входящий в кадр пакет данных передается с канального на сетевой уровень. На рис. 5 приведена временная диаграмма обмена «I» кадрами между пунктами А и Б (случай приема «I» кадров без искажения, исходное состояние V(S)=V(R)=0, буферы повтора пустые).

Рис. 5. Временная диаграмма обмена «I» кадрами, принятыми с канала без искажений

Обозначения:

  • I (i, j) – информационный кадр с параметрами N(S)=i, N(R)=j
  • RR(j) – кадр RR с параметром N(R)=j

Крестиком отмечен искаженный в канале кадр. Ниже приведено описание последовательности операций.

  1. Передача «I» кадра с параметрами N(S)=0, N(R)=0. Запись кадра «I» в буфер станции А. Изменение текущего значения V(S):=V(S) + 1, т.е. V(S)=1 (на станции А).
  2. Прием без ошибок I (0,0) на станции Б. Номер кадра N(S) совпадает с ожидаемым номером V(R), то есть N(S)=V(R)=0. Изменение текущего состояния приема V(R):=V(R)+1, т.е. V(R)=1 в Б.
  3. Подтверждение приема кадра I (0,0), т.е. передача положительной квитанции RR(1).
  4. Прием RR(1) и стирание из буфера кадра I (0,0).
  5. Передача кадра I (1,0), запись его в буфер, V(S)=2.
  6. Прием без ошибок I (1,0) на станции Б, V(R)=2.
  7. Подтверждение приема I (1,0), т.е. передача квитанции RR(2).
  8. Прием искаженного в канале кадра RR(2). Кадр отбрасывается.
  9. Передача очередного «I» кадра I (2,0), запись его в буфер (в буфере станции А теперь записаны два кадра I (1,0), I (2,0), которые ждут подтверждения об их приеме на станции Б), V(S)=3.
  10. Прием безошибочного I (2,0) на станции Б, V(R)=3.
  11. Передача «I» кадра со станции Б на станцию А с параметрами N(S)=0, N(R)=3, т.е. I (0,3). V(S)=1 (на станции Б), запись в буфер I (0,3) на станции Б. Этот кадр одновременно является квитанцией правильного приема станцией Б «I» кадров с номерами 1 и 2.
  12. Прием без ошибок I (0,3), стирание из буфера станции А кадров I (1,0) и I(2,0).

В приведенной на рис. 5 диаграмме все «I» кадры принимаются неискаженными. Поэтому операции приема этих кадров (2, 6, 10 на станции Б и 12 на станции А) завершаются передачей входящих в них пакетов данных на сетевой уровень.

На рис. 6 представлена диаграмма, включающая прием некоторых искаженных кадров «I». Для наглядности диаграммы параметры V(S) и V(R) на рисунке не приведены.

Как видно из диаграммы, искаженные в канале кадры I(2,0), I(3,0), I(4,0) при получении кадра REJ(1) передаются на станцию Б повторно из буфера. Кадры I(0,0) со станции А и I(0,4), I(1,5) со станции Б повторно из буферов не передаются, поскольку они подтверждаются соответственно кадрами RR(1), I(4,1) и RR(2). Необходимо отметить, что нумерация кадров N(S) и N(R) циклическая. При нормальной нумерации для этого отводится 3 бита, а при расширенной - 7 бит. Напомним, что под шириной (размером) окна W понимается максимальное число неподтвержденных кадров в буфере. При заполнении такого числа кадров в буфере согласно алгоритму требуется перейти к повторной передаче этих кадров из буфера. Чем выше пропускная способность канала и больше протяженность канала, тем размер окна выше.

Рис. 6. Временная диаграмма восстановления «I» кадров при приеме отрицательной квитанции REJ

Рассчитаем величину задержки кадра длинной порядка 128 байт при скорости передачи 64 кбит/с. Задержка составляет 128 байт / 64 кбит/с = 16 мсек. Сравним эту величину со временем задержки распространения кадра по спутниковому каналу протяженностью 72000 км, приняв скорость распространения сигнала равной скорости света в вакууме – 300000 км/с. Эта величина составляет 72000 км / 300000 км/с = 240 мсек, т.е. в канале одновременно могут находиться 15 кадров (240/16). Отсюда ясно, почему при использовании спутниковых каналов в сети Х.25 применяется расширенная нумерация и соответственно большая ширина окна W , чем при нормальной нумерации.

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

На рис. 7 и рис. 8 приведены диаграммы повтора «I» кадров из буфера по истечении тайм-аута. Примеры приведены для случая запрета передачи очередного кадра «I» при числе ожидающих в буфере повтора «I» кадров равном окну W (W=4).

Как видно из диаграммы, по истечении тайм-аута кадр «I» повторяется из буфера. Причиной повторения по таймеру может быть искажение только «I» кадров (рис. 7), либо искажение кадров «I» и кадров подтверждения RR (рис. 8). В случае правильного приема кадра I(0,0) пакет сетевого уровня должен быть отправлен на сетевой уровень, но повторный прием кадра I(0,0) считается копией уже принятого кадра, а поэтому он сбрасывается, т.е. не пересылается на сетевой уровень.

Рис. 7. Временная диаграмма восстановления кадра «I» по истечении тайм-аута
Рис. 8. Временная диаграмма сброса копии «I(0,0)» кадра, принятого повторно из станции Б по истечении тайм-аута на А

Обнаружение ошибок с помощью избыточного циклического кода

Ниже приводятся три способа описания определения кода CRC: с использованием арифметики по модулю 2, с использованием полинома и аппаратная реализация[3].

Пример с использованием арифметики по модулю 2

В вычислениях по модулю 2 используется двоичное сложение без переноса в старший разряд (операция исключающего ИЛИ).

Введем следующие обозначения:

  • T – n-битовый кадр, который необходимо передать;
  • D – k-битовый блок сообщения (k первых бит кадра T);
  • R – (n-k) – битовая контрольная последовательность кадра (последние (n-k) бит кадра T). Значение R необходимо вычислить;
  • P - (n-k+1) – битовый делитель.
Пример:
  1. Дано:
    сообщение D – 1010001101 (10 бит);
    последовательность P – 110101 (6 бит);
    Итак, n =15, k=10, n-k=5.
  2. Сообщение умножается на , что дает в результате: 101000110100000.
  3. Полученная последовательность делится на P:
    SiSS 4.9 p .png

    Здесь Q – целое число от деления.
  4. Полученный остаток складывается с , результат ( T = 101000110101110) передается.
  5. При отсутствии ошибок принятая последовательность T не отличается от переданной. Приемник выполняет деление на P:
    SiSS 4.9 t .png

    Поскольку деление не дало остатка, считается, что ошибки отсутствуют.

Пример с использованием полинома

Используя предыдущий пример, получаем: последовательности D = 1010001101 соответствует полином , последовательности Р = 110101 - полином , последовательности .

Полиномиальное деление, соответствующее приведенному ранее двоичному делению, показано на рис. 9.

Ошибка не обнаружится только в том случае, если соответствующий полином Е (Х) делится на Р(Х). При надлежащем выборе полинома Р (Х) выявляются такие ошибки:

  • все 1-битовые ошибки, если Р (Х) имеет более одного ненулевого члена;
  • все 2-битовые ошибки, если Р (Х) имеет делитель из трех членов;
  • любое нечетное количество ошибок, если в разложении Р (Х) по множителям: присутствует (X + 1);
  • любой пакет ошибок, длина которого не превышает n-k, или, эквивалентно, не превышает длину контрольной последовательности кадра.

Здесь Q(X) – полином от Q.

Рис. 9. Пример полиномиального деления

Приведем примеры длин п-к КПК (FCS) используемых полиномов Р(Х) в сетях связи:
CRC – 3: в GSM.
CRC – 16: в ОКС№7, X.25, Интернет (на межсетевом уровне, на транспортном уровне по протоколу TCP).
CRC – 32: в ATM.

Пример аппаратной реализации

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

Реализация схемы выглядит следующим образом.

  1. Регистр, содержащий (n - k) бит (по размеру контрольно-проверочной комбинации).
  2. До (n - k) элементов исключающего ИЛИ.
  3. Наличие или отсутствие логического элемента соответствует наличию или отсутствию члена в полиноме-делителе Р (Х), исключая члены 1 и .

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

сообщение ; ;
делитель ; .

На рис. 10,а представлена реализация регистра сдвига. Процесс начинается с очистки регистра (все ячейки обнуляются). После этого передаваемое сообщение (делимое) побитово вводится в регистр, начиная со старшего бита. На pис. 10,б приведена таблица, которая иллюстрирует пошаговую работу схемы по мере введения отдельных битов. Строки таблицы содержат значения пяти ячеек регистра сдвига в соответствующие моменты времени. Кроме того, в строках таблицы приводятся значения на выходе трех схем исключающего ИЛИ. Последнее число в каждой строке - значение следующего входного бита, который станет доступен для работы на следующем этапе.

Отметим, что операция исключающее ИЛИ влияет на значения ячеек С4, С2 и С0 при следующем сдвиге, что идентично рассмотренному ранее процессу двоичного деления. Процесс выполняется для всех битов передаваемого сообщения. Для обеспечения корректности выходного сигнала используются два ключа. При вводе битов данных оба ключа находятся в положении А. В результате за первые 10 шагов входные биты подаются в регистр сдвига и также используются в качестве выходных битов. По окончании обработки последнего бита данных регистр сдвига содержит остаток деления - содержание регистров после этапа 10. При вводе последнего бита данных в регистр оба ключа устанавливаются в положение В. В этом случае:

  1. все логические элементы больше не изменяют значения битов;
  2. за следующие 5 шагов на выход подаются 5 бит контрольно-проверочной комбинации (т.е. содержимое регистров после этапа 10).

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

В результате на выход регистра будут подаваться двоичные нули и по завершении приема все ячейки будут иметь значение 0.

Рис. 10. Схема реализации аппаратным способом

Примечания

  1. Мельников Д.А. Информационные процессы в компьютерных сетях. Протоколы, стандарты, интерфейсы, модули.М.: КУДИЦ – ОБРАЗ. 2001. 256с.
  2. Блэк Ю. Сети ЭВМ: Протоколы, стандарты, интерфейсы. М.: Мир. 1990. 506с.
  3. Столингс В. Беспроводные линии связи и сети. М.:Вильямс, 2003. 640с