Р.Л. Смелянский - Компьютерные сети. Том 1. Системы передачи данных (1130069), страница 28
Текст из файла (страница 28)
Расположим их в виде матрицы л к й. Для каждого столбца установим бит четности и разместим его в дополнительной строке, после чего передадим матрицу по строкам. При получении матрица восстанавливается, и если хоть один бит нарушен, то весь блок передается повторно. Этот метод позволяет обнаружить групповые ошибки длиной п, однако против групповых ошибок длиной и ч- 1 он бессилен. На практике применяют другую технику, которая называется циклическим избыточным кодом (Сусйс Кес(ппс!апсу Сос)е — СКС) !46!. СркС-коды построены на основе представления битовой строки как строки коэффициентов полинома.
При этом битовую строку длиной А рассматривают как коэффициенты полинома степени )с — 1, а самый левый бит строки — как коэффициент при старшей степени. Например, строка 110001 представляет собой полипом вида х' 4- хл м хо. Использование полиномиальных кодов при передаче заключается в следуюшем. Отправитель и получатель заранее договариваются о некотором определенном полиноме С(х), в котором коэффициенты при старшем и младшем членах должны быть равны 1 и который называется образующим. Идея данного метода состоит в добавлении контрольной суммы к передаваемому блоку, рассматриваемому как полипом М(х), таким образом, чтобы передаваемый блок с контрольной суммой был кратен полиному С(х).
Когда к получателю приходит блок данных с контрольной суммой, он делит его на С(х)*. Наличие при этом остатка свидетельствует об ошибках при передаче. Пусть степень С(х) равна г. При вычислении контрольной суммы блока из т бит должно выполняться условие и < т. Арифметические операции с полиномами выполняются по модулю 2. При делении сложение и вычитание происходят без переноса разрядов, т.е. по модулю, и, следовательно, этн операции становятся эквивалентными операции ЕХСШо!ЧЕ ОК. Алгоритм вычисления контрольной суммы, где г — степень С(х), следующий. 1) добавить г нулей в конец передаваемого блока таким образом, чтобы он содержал т м г разрядов и соответствовал полиному хлМ(х); 2) разделить по модулю 2 полипом х"М(х) на С(х); ' Поскольку онераиия веления на вычислительных машинах сволится к оперании санита, то она может быть реализована эффективно.
120 к ди погопоп Генератор. 1ООП Сесбшсние после прибавлении четырех нулей; П010!!0000 П00001010 » Гйюл5п55ь 00001 00000 000!О 00000 00!О! 00000 О!ОП 00000 !О ПО 00000 01010 00000 !0100 !0011 01 ПО ООООО О П10 Переданный кадр: ПО!0 ПОП П 10 Рнс. 4.3. Расчет контрольной суммы для полиномиального кода 3) вычесть остаток (длина которого всегда не более и разрядов) из строки, соответствующей полиномух"М(х) по модулю 2. Полученный ,';;~-'" .° результат и является блоком с контрольной суммой (назовем его ";:,.;..'::::„':.
Т(х)) Рис. 4.3 [40] показывает, как этот алгоритм работает для блока 1101011011 и 6(х) = х4 ч х + 1 Данный метод позволяет обнаруживать одиночные ошибки, групповые ошибки длинной не более и и нечетное число отдельных ошибок Существует три международных стандарта на вид полинома !т(х); СКС-12 — хо ч- хн ч- хт ч хт ч- х ь 1, ° СКС-16 — х'е + х" ах' + 1; ° СКС-СС1ТТ вЂ” х'ь э х" э х' э 1. Стандарт СКС-12 используется лля передачи символов из шести разрядов, а СКС-!6 и СКС-СС1ТТ вЂ” из восьми. Стандарты СКС-16 и СКС-СС1ТТ ловят одиночные, двойные ошибки, групповые ошибки длиной не более 16 и нечетное число изолированных ошибок. Достаточно подробно техника циклических кодов рассматривается в (40! 121 4 2.
Протоколы ДПЯ каналОЯ типа тОчка — тОчка 4.2. Т. Простейшие протоколы канала данных Рассмотрение протоколов уровня канала данных начнем с нескольких предположений. Во-первых, предположим, что физический уровень, уровень канала данных и сетевой уровень реализованы в виде независимых процессов, взаимодействующих с помощью передачи сообщений. В некоторых случаях процессы физического уровня и уровня канала данных могут выполняться на некотором вспомогательном процессоре ввода-вывода, внешнем по отношению к основному процессору, а в некоторых — на основном процессоре. Возможны также разные реализации; физический и канальный уровни могут быть реализованы в виде процедур, вызываемых сетевым уровнем, и т.д.
Однако здесь мы будем предполагать, что все три уровня представлены как независимые процессы. Также предположим, что имеется две машины: А и В. У машины А есть бесконечно длинный набор данных, который надо передать машине В с помощью надежного сервиса, ориентированного на соединение. Передача всегда происходит от А к В, хотя позднее сделаем допущение и об одновременной передаче от В к А.
Также предположим, что если канальный уровень машины А запрашивает данные для передачи от сетевого уровня, то эти данные всегда имеются и нет задержки на их подготовку. Канальный уровень рассматривает данные, получаемые от сетевого уровня, как неструктурированные, несмотря на то что в них имеется хотя бы заголовок сетевого уровня.
Все эти данные должны быть переданы равнозначному сетевому уровню. Когда канальный уровень получает пакет, он погружает его в кадр, добавляя признаки начала и конца кадра. Этот кадр затем передается на физическом уровне. Допустим, что есть две библиотечные функции: !гоги у/гауз!са! !ауст — для получения кадра с физического уровня, и го рЛуяси! !ауег — для передачи кадра на физический уровень.
Предположим также, что вычисление и добавление контрольных сумм происходит аппаратно. Изначально получатель просто ожидает наступления какого-либо события, ничего не предпринимая. В наших примерах это отражается вызовом функции ша!! ~от еиеп!(Аеиеп!), где параметр еиел! возвращает информацию о произошедшем событии. Ясно, что в действительности никто не будет ожидать в цикле (для этого обычно используются прерывания), но мы будем так считать для упрощения.
Кот ха кадр поступает к получателю, контрольная сумма вычисляется аппаратно. Если она неверна, то канальному уровню сообщается следующее: еиеп! = саха егг. Если же кадр поступил без повреждений, то канальный уровень получает сообщение: ецепг=агате атее!. Приведем перечень структур и функций [40), используемых в реализации протокола канального уровня: 122 1)х)ех1пе МАХ РХТ 1024 /* размер пакета в байтах */ (Га1ез, Ххпе) Ьоо1еап: /* булевский тиг. */ пеб 1пх зео пх: тип для последовательной нумерации или подтверждения получения (цпвгдлес спах сага [мах рхт)) расчес: тип/пакет (х)ага, аск, паЕ) гхаше Й1пб; /* виды кадров зуребер еппш суребеу цпвгс 1уребеГ вгхцс ,-:;г", 'Гуребер епцш дуребег згхцс .
'~.':,'-':,:,';::, .Тхаше Ктпс) Еех( пх зес( 4„~1!!'!',*' 'вес( пг аз'к. с.фй ' ' .$~~4~:."„:::ЧО1б Хо песне "'!~~ . ураб Хо роуз ! р~~:,'.'чо10 вгахг х1 .,".«-„"',"::"-'.У* остановка ,~~~!:;.:::уо1б асор хгш .,!;:у ас)х 11шех *у ;";,', чб10 згахг ас у* остановка асХ 11шех *l чо1б ягор азк l* разрешенпе пехнохк 1ауех 'ф~:"1 Чо10 епаЫе и /* кадры, передаваемые на этом уровне */ /* вид кадра *( /* последовательный номер */ номер подтверждаемого кадра */ сетевой пакет */ обытия возврашает тип события */ ечепг(ечепх гуре*ечепг); пакета от сетевого уровня для передачи на нохк 1ауех(раскас *р); нформации из полученного кадра на сетевой хк 1ауех (раснег *р); кадра с Физического уровня и копирование его Х 11шех(чоИ) ' вспомогательного таймера и запрет события 11шех (чо10): сетевому уровняло генерировать событие геабу ехнохк 1ауех(чо10): 123 з1са1 1ауех(глаше *х); кадра на физический уровень для отправки */ гса1 1ауех(рхаше *з); таймера и ожидание события 11шеоцг шех (вес( и таймера и отмена ожидания события ххшеоцг */ ех(зех( пх чомогательного таймера и разрешение события /* запрет сетевому уровню генерировать событие пепногх 1ауег геас(у *Х чоха б1ваЬ1е пехнохх 1ауег(чо)б).
Как уже отмечалось, лля обеспечения возможности обнаружения потери кадров уровень канала, отправляя калр, должен устанавливать таймер. Если подтверждение не прихолит до истечения времени, установленного таймером, считается, что кадр не дошел, В этом случае получают сообщение еиеп( = 6теоил Процедуры пакт Птег и пор атея используются соответственно для запуска и остановки таймера, причем процедуру запуска таймера можно вызывать, не ожидая окончания предыдущего запуска. Подобное обращение означает перезапуск таймера на новый интервал.
Процедуры з(агу аст атея и втор ас( йтег используются для управления дополнительным таймером, используемым в определенных случаях для уведомления. 4.2.2. Симплекс-протокол без ограничений Рассмотрим простейший симплексный протокол канального уровня: /* Протокол 1 позволяет передавать данные от передатчика к получателю. Предполагается, что канал передачи свободен от ошибок и получатель способен обрабатывать входные данные сколь угодно быстро. */ Хуребех еппп (хгап~е агхтча1)ечепп суре: ()1пс1пбе "ргогосо1.Ь" чотб яепбег1(чохи) ) Е гаке з буФер для входного кадра */ буФер для входного пакета раскех Ьнххег; в.тпто=бпххег; Ьо рпузхса1 1ауех(ьв) чохи гесехчег1 (чо1с() 124 нЬ11е (Хгсе) ( хлою пехнохх 1ауег(ьЬпххех); *получаем то, что будем отправлять /*копируем в в для передачи /* отсылаем /* и снова, и снова, и снова тг вше г, еуепс суре етепс; заполняется при ожида- нии, но здесь не используется яу ) ~,';:::.': Этот протокол передает данные только в одно --:;;:1,,;этом считается, что получатель и отправитель „~~.;.';:,:,:;~алке и получению данных.
Время обработки да -':-:~„':::Предполагается также, что буфер имеет неогра ::;;-;-" изданные в канале не теряются и не искажаются 4.2.3. Симплексный старт-стопны Теперь снимем одно из ограничений предыд ' з.;;;!:::.'способность сетевого уровня обрабатывать по '":ь~~,",~сколь угодно б1ястро. Все остальные предположе1 :,;;~;;:;:канал абсолютно надежный, график однонапра -,."~~Ф!', 'Основная проблема — предотврагдение ситуа '-,.';.;:-:!тель «заваливает» данными получателя. Если по ;~:::,'-~.,'Время Лг для исполнения функции глот рлуу1 ,:"~;:„-'пепоог/с 1ауег, то отправитель должен передават ; .:!:: —."."СКоростью один кадр за время ЛГ ' ":::-; '., Решением этой проблемы может быль введен —.:.-:;",'"",",-:Й%ных служебных сообщений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
