3 (1130535), страница 2
Текст из файла (страница 2)
. .– [RFC 1958]Компьютерные сетипроф.Смелянский Р.Л.23.02.20147Интернет: Обнаружениеошибок – 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Средства описания протоколов:Диаграммы переходов для конечныхавтоматовКомпьютерные сетипроф.
Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУ23.02.2014Конечный автомат<Ain; Aout; S; Q: aq -> bq’; s*>Cсобытие, вызывающее переходДействие при изменении состояния21событиедействие3Компьютерные сетипроф.Смелянский Р.Л.23.02.20142Пример: HTTP запросКомпьютерные сетипроф.Смелянский Р.Л.23.02.20143Пример: диаграмма ТСР соединенияКомпьютерные сетипроф.Смелянский Р.Л.23.02.20144Интернет: управлениепотоком (Stop and Wait)Компьютерные сетипроф.
Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУПроблемаА500 000 пакетов/сКомпьютерные сети.проф. Смелянский Р.Л.В200 000 пакетов/с23.02.20142Управление потоком• Не посылать пакетов больше, чем можетпринять получатель• Есть обратная связь между отправителем иполучателем• Два основных подхода:o Stop and Waito Скользящее окноКомпьютерные сети.проф. Смелянский Р.Л.23.02.20143Конечный автомат (FSM)<Ain; Aout; S; Q: aq -> bq’; s*>Cсобытие, вызывающее переходДействие изменении состояния31событиедействие2Компьютерные сетипроф.Смелянский Р.Л.23.02.20144Управление потокомКомпьютерные сети.проф. Смелянский Р.Л.23.02.20145Управление потокомКомпьютерные сети.проф.
Смелянский Р.Л.23.02.20146Управление потокомwait event = acksend a packet with ackКомпьютерные сети.проф. Смелянский Р.Л.23.02.20147Управление потоком (stop and wait)•••••В одно и то же время передают не более одного пакетаSender отправляет пакетReceiver посылает пакет с ack , когда получает пакет данныхПолучив аск, sender шлет новый пакет с даннымиПо time_out, sender повторно посылает пакет с даннымиКомпьютерные сети.проф.
Смелянский Р.Л.23.02.20148Управление потокомreceive datasend ackdeliver dataWaitforpacketReceiver FSMcallSend packetSender FSMWaitfordataWaitfor acktime outresendreceive ack-Компьютерные сети.проф. Смелянский Р.Л.23.02.20149Управление потокомКомпьютерные сети.проф. Смелянский Р.Л.23.02.201410ДублированиеreceiversenderooСама сеть не размножает пакетыЗапаздывание пакетовгарантированно не более одногоtime_outКомпьютерные сети.проф.
Смелянский Р.Л.timeout•Счетчик на 1 бит в данных иуведомлении позволяетотличать новые данные отдубликатовБудем предполагатьtimeout•timeoutdata 0ack 0data 1ack 1data 0ack 023.02.201411Интернет: управлениепотоком (Sliding Window)Компьютерные сетипроф. Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУУправление потоком (stop and wait)••••••В одно и то же время передают не более одного пакетаSender отправляет пакетReceiver посылает пакет с ack , когда получает пакет данныхПолучив аск, sender шлет новый пакет с даннымиПо time_out, sender повторно посылает пакет с даннымиСчетчик на 1 бит позволяет выявлять дублированиеКомпьютерные сети.проф.
Смелянский Р.Л.23.02.20142ПроблемаМоскваАНовосибирскВ10 Мб/сRTT = 50 mсМакс. пропускная способность 10Мб/сRTT – 50mcКомпьютерные сети.проф. Смелянский Р.Л.Сделаем обобщение S&W протокола:- Разрешаем использовать сразунесколько неподтвержденныхсегментов- Максимальное число такихсегментов – окно- Можем плотно «забить» канал23.02.20143Примерreceiversendersenderreceivertimeouttimeouttimeoutdata 0ack 0data 1Sliding Windowack 1data 0ack 0Компьютерные сети.проф.
Смелянский Р.Л.23.02.20144SW Sender••У каждого сегмента естьпоследовательный номерПоддерживаются 3 переменныхooo•••Размер окна отправки (SWS)Последнее полученное от получателя подтверждение (LAR)Последний отправленный сегмент (LSS)Всегда (LSS – LAR) ≤ SWSLAR возрастает при каждом новомподтвержденииБуфер на SWS сегментовКомпьютерные сети.проф. Смелянский Р.Л.23.02.20145SW Receiver•Поддерживаются 3 переменныхooo•••Размер окна отправки (RWS)Наибольший допустимый сегмент (LAS)Последний полученный сегмент (LSR)Всегда (LAS – LSR) ≤ RWSLAR возрастает при каждом новомподтвержденииЕсли полученный сегмент < LAS, тошли подтверждениеooНакопительный ack: если получены 1,2,3,5 –подтверждаем 3ТСР в уведомлении подтверждает номер ожидаемогосегмента (т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
