34 Обнаружение ошибок (Лекции 2014 года)

Интернет: Обнаружениеошибок – 3 схемыКомпьютерные сетипроф. Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУОбнаружение ошибокIP dataТСР dataКомпьютерные сети.проф. Смелянский Р.Л.TCP HdrIP Hdr23.02.20142Три схемы обнаружения ошибок• Добавление контрольной суммы в пакеты IP, TCPo Быстро, аппаратно, но можно и программноo Не очень надежно• Полиномиальные CRC коды (Ethernet)o Дороже контрольной суммы (вычисляются аппаратно)o Защищают от групповых ошибок, пакетов ошибок и ошибок четности• Message Authentication Code (MAC): на основекриптографииo Защищает от малейших модификаций сообщений, но не от ошибокo 2 сообщения длины n могут иметь одинаковый МАС с вероятностью2−Компьютерные сети.проф.

Смелянский Р.Л.23.02.20143контрольная сумма в IP пакете• IP, UDP и ТСР используют один и тот же алгоритмкомплементарной контрольной суммы:ooooУстановить поле checksum= 0Сложить все 16 разрядные слова в пакетеУстановить разряд четностиКонтрольная сумма должны быть такой чтобы сумма всего пакета,включая контрольную сумму была бы 0хffff• Основное достоинство – простота• Недостаток – слабая защита от ошибок (толькоодиночные ошибки).Компьютерные сети.проф. Смелянский Р.Л.23.02.20144Обнаружение и исправление ошибок(см. учебник т.1 стр.116-122)• Ошибки единичные и групповые (блочные)• Коды с обнаружением ошибокo кодословоo расстояние Хемминга• Коды исправляющие ошибки0000000000, 0000011111, 1111100000,1111111111(n+1)2m  2n; (m+r+1)  2rСети ЭВМпроф.

Смелянский Р.Л.23.02.20145Коды с исправлением ошибок Код Хемминга для единичных ошибок разряды кодослова нумеруют слеванаправо,начиная с 1; все биты, номера которых есть степень 2 (1,2,4,8,16и т.д.) - контрольные, остальные - биты сообщения; каждый контрольный бит отвечает за четностьгруппы битов, включая себя. Один и тот же битможет относиться к разным группам.

Значение битасообщенияопределяетсяпозначениямконтрольных битов. Чтобы определить какиеконтрольные биты контролируют бит в позиции kнадо представить значение k по степеням двойки.Например, 11= 1+2+8, 39=1+2+4+32.Сети ЭВМпроф. Смелянский Р.Л.23.02.20146Код Хемминга для исправления одиночных ошибокСети ЭВМпроф. Смелянский Р.Л.23.02.20147Коды обнаруживающие ошибки• Групповые ошибки• Биты четности не позволяют эффективно бороться сгрупповыми ошибками• Иногда перепослать дешевле, чем исправить• CRC код (Cyclic Redundancy Code)o строка 110001 представляет полином x5+x4+x0o арифметика выполняется по модулю 2Сети ЭВМпроф.

Смелянский Р.Л.23.02.20148Коды обнаруживающие ошибки (CRC)• Отправительи получатель договариваются оконкретном генераторе полиномов G(x) степени r(коэффициенты при старшем члене и при младшемчлене должны быть равны 1).• Для вычисления контрольной суммы блока из m битнадо чтобы обязательно m>r.• Добавить контрольную сумму к передаваемомублоку, рассматриваемому как полином М(х) так,чтобы передаваемый блок с контрольной суммойбыл кратен G(x). Когда получатель получает блок сконтрольной суммой, он делит его на G(x). Еслиесть остаток, то были ошибки при передаче.Сети ЭВМпроф. Смелянский Р.Л.23.02.20149Коды обнаруживающие ошибки• Алгоритм вычисления контрольной суммы:• Добавить r нулей в конец блока так, что онтеперь содержит m+r разрядов исоответствует полиному xrM(x);• Разделить по модулю 2 полином xrM(x) наG(x);• Вычесть остаток ( длина которого всегдане более r разрядов) из строки,соответствующей xrM(x), по модулю 2.Результат и есть блок с контрольнойсуммой ( назовем его Т(х)).Сети ЭВМпроф.

Смелянский Р.Л.23.02.201410Сети ЭВМпроф. Смелянский Р.Л.23.02.201411Коды обнаруживающие ошибки• Существует три международных стандарта навид G(x):o CRC-12o CRC-16o CRC-CCITT= x12+x11+x3+x2+x+1= x16+x15+x2+1= x16+x12+x5+1• CRC-12 используется для передачи символов из 6разрядов. Два остальных - для 8 разрядных. CRC-16 иCRC-CCITTловят одиночные, двойные ошибки,групповые ошибки длины не более 16 и нечетноечисло изолированных ошибок с вероятностью99,997%.Сети ЭВМпроф. Смелянский Р.Л.23.02.201412Message Auth. Code• Message Authentication Code (MAC)o Не путать с Media Access Control!• Использует криптографию для вычисленияm= MAC (M,s), |m|<<|M|o M известно, s – секретно => можем проверить m= MAC (M,s), |m|<<|M|o Если s не известно, то получить m практически не возможноo Если известно m, то практически не возможно вычислить M, даже знаяMAC• Не столь устойчиво к ошибкам как CRC• Защищает от злоумышленниковКомпьютерные сети.проф.

Смелянский Р.Л.23.02.201413Три схемы обнаружения ошибок• Контрольная сумма добавляется в IP, TCP,UDPпакетыo Быстро, дешевоo Неустойчиво• CRC коды используются в Ethernet кадрахo Дороже чем контрольная суммаo Устойчивы к двукратным ошибкам, групповым ошибкам и ошибкамчетности• Message Authentication Code (MAC): на основекриптографииo Защищает от малейших модификаций сообщений, но не от ошибокo 2 сообщения длины n могут иметь одинаковый МАС с вероятностью2−Компьютерные сети.проф. Смелянский Р.Л.23.02.201414.