Канальная сеть. Теория построения сетей

Канальный уровень (Data Link Layer) определяет правила доступа к физической среде и управляет передачей информации по каналу, осуществляя формирование сигнала о начале передачи и организуя начало и собственно передачу информации с созданием сигнала окончания передачи и последующим переводом канала в пассивное состояние. В процессе передачи выполняется проверка принимаемой информации и исправление возникающих ошибок, отключение канала при возникновении неисправности, а также формирование сообщений о возникновении неустранимых ошибок для вышестоящего уровня с восстановлением передачи по окончании ремонта техники. В ряде случаев данный уровень осуществляет слежение за скоростью обмена и окончанием информационных блоков, а также управляет физической цепью при ее мультиплексорном использовании.

На физическом уровне просто пересылаются биты и при этом не учитывается, что физическая среда передачи может быть занята. Поэтому одной из задач канального уровня (Data Link layer) является проверка доступности среды передачи. Другая задача канального уровня – реализация механизмов обнаружения и коррекции ошибок. Для этого на канальном уровне биты группируются в наборы, называемые кадрами (frames). Канальный уровень обеспечивает корректность передачи каждого кадра помещая специальную последовательность бит в начало и конец каждого кадра, для его выделения, а также вычисляет контрольную сумму, обрабатывая все байты кадра определенным способом, и добавляет контрольную сумму к кадру. Когда кадр приходит по сети, получатель снова вычисляет контрольную сумму полученных данных и сравнивает результат с контрольной суммой из кадра. Если они совпадают, кадр считается правильным и принимается. Если же контрольные суммы не совпадают, то фиксируется ошибка. Канальный уровень может не только обнаруживать ошибки, но и исправлять их за счет повторной передачи поврежденных кадров. Необходимо отметить, что функция исправления ошибок для канального уровня не является обязательной, поэтому в некоторых протоколах этого уровня она отсутствует, например в Ethernet и frame relay.

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

При передаче - собственно передачи кадра данных с сетевого уровня на физический уровень и обеспечения безошибочной передачи по физическому уровню кадров с одной системы на другую;

При приеме - перераспределения несмонтированных битов из физического уровня в кадры для более высоких уровней.

Функции канального уровня, как правило, реализуются программно-аппаратно.

Со временем возникла необходимость разделения канального уровня на два подуровня – уровень управления логической связью (Logical Link Control, LLC) и уровень управления доступом к физической среде (Media Access Control, MAC).

Подуровень MAC работает с физическими адресами, которые называются МАС-адресами. В сетях Ethernet и Token Ring МАС-адреса представляют собой шестнадцатиричные числа, записанные в микросхему сетевого адаптера. МАС-адрес сети Ethernet (иногда его называют адресом Ethernet) – это 12 шестнадцатиричных цифр, каждая пара из которых отделена двоеточием. Эти 12 шестнадцатеричных цифр представляют двоичное число длиной 48 бит (или 6 байт). Первые три байта содержат код производителя, присвоенный организацией IEEE. Последние три байта присваиваются производителем. МАС-адрес, или физический адрес, иногда называют адресом устройства. Он отличается от логического адреса,т.е. IP-адреса в сети ТСР/IР тем, что его нельзя изменить. Логический адрес присваивается программным обеспечением, изменить его очень просто. Оба адреса служат для идентификации компьютера в сети.

На подуровне LLC определяется логическая топология сети. Она может не совпадать с физической топологией. Подуровень LLC отвечает за связь (или интерфейс) между подуровнем MAC и расположенным выше сетевым уровнем, преобразуя биты и байты, полученные с уровня MAC, в формат, требуемый сетевым устройствам.

В локальных сетях протоколы канального уровня поддерживаются мостами, коммутаторами и маршрутизаторами. В компьютерах функции канального уровня реализуются совместными усилиями сетевых адаптеров и их драйверов. В протоколах канального уровня, используемых в локальных сетях, заложена определенная структура связей между компьютерами и способы их адресации. Хотя канальный уровень и обеспечивает доставку кадра между любыми двумя узлами локальной сети, он это делает только в сети с определенной топологией связей, именно той топологией, для которой он был разработан. К таким типовым топологиям, поддерживаемым протоколами канального уровня локальных сетей, относятся "общая шина", "кольцо" и "звезда", а также структуры, полученные из них с помощью мостов и коммутаторов. Во всех этих конфигурациях адрес назначения имеет локальный смысл для данной сети и не изменяется при прохождении кадра от узла-источника к узлу назначения. Возможность передавать данные между локальными сетями разных технологий связана с тем, что в этих технологиях используются адреса одинакового формата, к тому же производители сетевых адаптеров обеспечивают уникальность адресов независимо от технологии. Примерами протоколов канального уровня являются протоколы Ethernet, Token Ring, FDDI, 100VG-AnyLAN.

В территориально-распределенных сетях, т.е. сетях уровня WAN, которые редко обладают регулярной топологией, канальный уровень часто обеспечивает обмен сообщениями только между двумя соседними компьютерами, соединенными индивидуальной линией связи. Примерами протоколов "точка-точка" (как часто называют такие протоколы) могут служить широко распространенные протоколы канального уровня PPP и LAP-B, ответственные за доставку кадра непосредственному узлу-соседу. Адрес в этом случае не имеет принципиального значения, а на первый план выходит способность протокола восстанавливать искаженные и утерянные кадры, так как плохое качество территориальных каналов, особенно коммутируемых телефонных, часто требует выполнения подобных действий.

Если же перечисленные выше условия не соблюдаются, например связи между сегментами Ethernet имеют петлевидную структуру, либо объединяемые сети используют различные способы адресации, как в сетях Ethernet и X.25, то протокол канального уровня не может в одиночку справиться с задачей передачи кадра между узлами и требует помощи протокола сетевого уровня. Именно так организованы сети X.25. Таким образом, когда в сетях уровня WAN функции канального уровня в чистом виде выделить трудно, то они объединяются с функциями сетевого уровня в одном и том же протоколе. Примерами такого подхода могут служить протоколы технологий ATM и frame relay.

На канальном уровне используются такие протоколы, как широко известный для последовательных соединений протокол ISO High-level DataLink Conrol (HDLC), протоколы ITU-T Link Access Procedures Balanced (LAPB), Link Access Procedures on the D-channel (LAPD) и Link Access Procedures to Frame Mode Bearer Services (LAPF), протоколы IEEE 802.2 LLC (тип I и тип II), обеспечивающий MAC для сред локальных сетей 802.Х, а также протоколы Ethernet, Token ring, FDDI, X.25 и FR.

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

NUMBEREDHEADINGS__

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

Настоящая глава посвящена описанию основной процедуры второго (канального) уровня сети X.25 (X.25/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» подтверждения приёма правильного пакета данных.

Формат кадра

На рис. 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 байт вероятность безошибочного приема кадра P = (1 − P B) ≈ (0 , 9999) 1024 ≈ 0 , 9 {\displaystyle P=(1-P_{B})\approx (0,9999)^{1024}\approx 0,9} , т.е. каждый десятый кадр искажен на приеме.

Частота появления ошибочных бит в аналоговом канале сети Х.25 нередко составляет даже P B = 0 , 001 {\displaystyle P_{B}=0,001} . Ошибки в каналах связи чаще бывают не единичными, а групповыми, то есть имеет место пакетирование ошибок. Это значительно уменьшает частоту искаженных кадров.

Полученный результат свидетельствует о необходимости применения схем обнаружения ошибок. Работа всех методов обнаружения ошибок основывается на использовании помехоустойчивого кодирования. На передающей стороне заголовок З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)

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

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

Супервизорный кадр отказ REJ (reject) является отрицательной квитанцией и указывает, что «I» кадры, с номерами N(S)шириной окна 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, с использованием полинома и аппаратная реализация .

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

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

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

• T – n-битовый кадр, который необходимо передать;
• D – k-битовый блок сообщения (k первых бит кадра T );
• R – (n-k) – битовая контрольная последовательность кадра (последние (n-k) бит кадра T ). Значение R необходимо вычислить;
• P - (n-k+1) – битовый делитель.

Пример:

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

Используя предыдущий пример, получаем: последовательности D = 1010001101 соответствует полином , последовательности Р = 110101 - полином , последовательности R = 01110 − R (X) = X 3 + X 2 + X {\displaystyle R=01110-R(\mathrm {X})=\mathrm {X} ^{3}+\mathrm {X} ^{2}+\mathrm {X} } .

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

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

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

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

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

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

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

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

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

Из рисунка 1.4 видно, что основная задача канального уровня в семействе протоколов TCP/IP - посылать и принимать (1) IP датаграммы для IP модуля, (2) ARP запросы и отклики для ARP модуля, и (3) RARP запросы и отклики для RARP модуля. TCP/IP поддерживает различные канальные уровни, в зависимости от того какой тип сетевого аппаратного обеспечения используется: Ethernet, Token ring, FDDI (Fiber Distributed Data Interface), последовательные линии RS-232, и так далее.

В этой главе мы подробно рассмотрим канальный уровень Ethernet, два специализированных канальных уровня для последовательных интерфейсов (SLIP и PPP) и драйвер loopback, который присутствует практически во всех реализациях. Ethernet и SLIP это канальные уровни, используемые для большинства примеров в данной книге. Также мы рассмотрим максимальный блок передачи (MTU - Maximum Transmission Unit), который является характеристикой канального уровня и к которой мы обращаемся много раз в этой главе и в следующих. Также мы покажем некоторые расчеты, с помощью которых можно выбрать MTU для последовательной линии.

Термин Ethernet обычно означает стандарт, опубликованный в 1982 году компаниями Digital Equipment Corp., Intel Corp., и Xerox Corp. В настоящее время это основная технология применяемая в локальных сетях использующих TCP/IP. В Ethernet используется метод доступа, называемый CSMA/CD, что обозначает наличие несущей (Carrier Sense), множественный доступ (Multiple Access) с определением коллизий (Collision Detection). Обмен осуществляется со скоростью 10 Мбит/сек, с использованием 48-битных адресов.

Несколько лет спустя Комитет 802 Института инженеров по электротехнике и радиоэлектронике ( IEEE - Institute of Electrical and Electronics Engineers) опубликовал отличающийся набор стандартов. 802.3 описывает полный набор сетей CSMA/CD, 802.4 описывает сети с передачей маркера и 802.5 описывает сети Token ring. Общим для всех них является стандарт 802.2, который определяет управление логическим каналом ( LLC - Logical link control) и который является общим для большинства сетей 802. К сожалению, комбинация 802.2 и 802.3 определяет форматы фрейма отличные от Ethernet ( описывает все детали стандартов IEEE 802).

В мире TCP/IP инкапсуляция IP датаграмм определена в RFC 894 для сетей Ethernet и в RFC 1042 для сетей IEEE 802. В Host Requirements RFC к каждому компьютеру, подключенному к Internet через кабель Ethernet 10 Мбит/сек, предъявляются следующие требования:

1. Компьютер должен иметь возможность посылать и получать пакеты, инкапсулированные с использованием RFC 894 (Ethernet).
2. У компьютера должна быть возможность получать пакеты RFC 1042 (IEEE 802), перемешанные с пакетами RFC 894.
3. Компьютер должен иметь возможность посылать пакеты с использованием инкапсуляции RFC 1042. Если компьютер может посылать оба типа пакетов, то тип пакета должен быть конфигурируемым, а конфигурация по умолчанию должна быть настроена на пакеты RFC 894.

Наиболее широко используется инкапсуляция RFC 894. На рисунке 2.1 показаны два различных метода инкапсуляции. Цифры под каждым квадратиком на рисунке это размер в байтах.

В обоих форматах фрейма используется 48-битовый (6-байтовый) формат представления адресов источника и назначения (802.3 позволяет использование 16-битных адресов, однако обычно используются 48-битные). Это как раз то, что мы называем по тексту аппаратными адресами (hardware addresses). Протоколы ARP и RARP (см. главу 4 и главу 5) устанавливают соответствие между 32-битными IP адресами и 48-битными аппаратными адресами.

Следующие 2 байта в этих форматах фрейма различаются. Поле длины (length) 802 содержит количество следующих за ним байтов, однако не содержит в конце контрольной суммы. Поле тип (type) в Ethernet определяет тип данных, которые следуют за ним. Во фрейме 802 то же поле типа (type) появляется позже в заголовке протокола доступа к подсети (SNAP - Sub-Network Access Protocol). К счастью, величины, находящиеся в поле длины (length) 802, никогда не совпадают с величинами, находящимися в поле типа (type) Ethernet, поэтому эти два формата фрейма легко различимы.

Во фрейме Ethernet данные следуют сразу после поля тип (type), тогда как во фрейме 802 за ним следуют 3 байта LLC 802.2 и 5 байт SNAP 802.2. Поля DSAP (точка доступа к сервису назначения - Destination Service Access Point) и SSAP (точка доступа к сервису источника - Source Service Access Point) оба установлены в 0xAA. Поле ctrl установлено в 3. Следующие 3 байта, org code установлены в 0. Затем идет 2-байтовое поле тип (type), такое же, как мы видели в формате фрейма Ethernet (дополнительные значения, которые могут появиться в поле типа, описаны в RFC 1340 ).

Поле контрольной суммы ( CRC) определяет ошибки, возникшие при транспортировке фрейма (также оно иногда называется FCS или последовательность контроля фрейма - frame check sequence).

Минимальный размер фреймов 802.3 и Ethernet требует, чтобы размер данных был хотя бы 38 байт для 802.3 или 46 байт для Ethernet. Чтобы удовлетворить этому требованию, иногда вставляются байты заполнения, для того чтобы фрейм был соответствующей длины.

Мы еще столкнемся с минимальным размером, когда будем рассматривать движение пакетов по кабелям. Также мы еще не раз обратимся к инкапсуляции Ethernet, потому что это, пожалуй, самая широко распространенная форма инкапсуляции.