Net1 (Контрольная работа 1)

2. Принцип уровневости3. Принцип инкапсуляцииИнкапсуляция в компьютерных сетях — это метод построения модульных сетевыхпротоколов, при котором логически независимые функции сети абстрагируются отнижележащих механизмов путём включения или инкапсулирования этих механизмов вболее высокоуровневые объекты. Например, когда процесс хочет послать сообщение спомощью UDP, то производится последовательность действий:● процесс передает сообщение к UDP в соответствии с парой гнездовых адресов идлины данных;● UDP получает данные, дополненные заголовком UDP;● UDP передает пользовательскую датаграмму к IP с гнездовым адресом;● IP дополняет свой заголовок, который использует значение 17 в поле протокола,указывающее, что данные поступили от UDP­протокола;● IP­датаграмма дополняет и добавляет собственный заголовок (при необходимостии окончание) и передает его к физическому уровню;● физический уровень кодирует биты в электрические или оптические сигналы ипосылает их отдалённой машине.Пример: Virtual Private Network (VPN):● данные НТТР приложения в● ТСР транспортный сегмент в● IP пакет в● безопасное представление TLS сообщения● ТСР транспортный сегмент в● IP пакет в● кадр Ethernet канала•Упрощает представление данных при переходе между уровнями•Инкапсуляция данных на каждом уровне:Помогает разделению сервисов на каждом уровнеПомогает строго соблюдать границы между уровнямиУпрощает реализацию каждого уровня4. Принцип коммутации пакетовПакет – единица данных, несущая достаточно информации, чтобы быть доставленной кместу назначения● каждый пакет самодостаточен● не надо поддерживать/хранить информацию о состоянии потока● в случае ошибки нет изменений состояния потокаКоммутация пакетов (англ. packet switching) — принцип коммутации, при котороминформация разделяется на отдельные пакеты, которые передаются в сети независимодруг от друга. В таких сетях по одной физической линии связи могут обмениватьсяданными много узлов.Трафик в сети крайне неравномерный● Если выделять часть канала для каждого пакета, то канал будет использован неэффективно● Коммутация пакетов позволяет каждому потоку использовать всю пропускнуюспособность канала● Статистическое мультиплексирование/уплотнение канала5. Принцип: имена и адреса●Имя указывает что есть объект именования○ Кабинет Смелянского○ pluto.lvk.cs.msu.su○ list_srt●Адрес указывает где расположен объект○ 119899, Москва, Ленинские горы, МГУ, 2­ой учебный корпус, ком.764○ IP: 171.66.3.9○ 0x0040005080●Телефонный номер – это адрес или имя?○ Это лишь концептуальная модель!●Структура имени:○ oодноуровневое:■ имя бирж (РТС, ММВБ, NSDQ), названия аэропортов (SVO, DMV)■ cервисы – http, ftp, VPN■ Apple ID, Skype ID● набор (БД): пол: муж.; ФИО: Смелянский Р.Л.; должность: профессор;● иерархия:○ lvk.cs.msu.su○ Смелянский Руслан Леонидович, профессор ф­та ВМК, МосковскийГос. Университет●Структура адреса влияет на то, как мы можем указывать на объект○ одно ранговый адрес: номер порта, адрес основной памяти○ набор: координаты (x,y,z); (55°45′с.ш.:37°36′в.д. )○ иерархические адреса■ адрес сегмента данных на диске (цилиндр, дорожка, сегмент)■ страна, город, улица, дом, квартира●●●Internet адреса: 32 IPv4; 128 IPv6Internet имена: система доменных имен (DNS): lvk.cs.msu.suИмена и адреса на более высоких уровнях○ имя сервиса (http), имя порта (80)○ SIP идентификатор (pal@a.com), е­адрес (pal@a.com)●Internet Corporation for Assigned Names and Numbers (ICANN)○ Internet Assigned Number Authority (IANA)●То как Вы именуете и адресуете что­то, имеет огромное влияние на организациюсети и ее протоколов● Структура имен и адресов также имеет большое влияние на простоту и удобствоинтеграции сетей и протоколов6. Принцип E2EВ этой фундаментальной услуге сети, которая сама по себе не представляет ценности,нашел отражение один из основополагающих архитектурных принципов Интернета ­принцип прозрачности или end­to­end principle. Суть его заключается в подходе, прикотором большая часть функциональности реализована в оконечных устройствах ­поключенных к сети компьютерах, ­ а не в самой сети. Сеть должна предоставлять толькоуниверсальные и нейтральные услуги, а конкретно ­ маршрутизации и передачи пакетовданных в режиме "best effort". Сеть не дает никиких гарантий относительно параметровкачества передачи, и даже не гарантирует, что данные дойдут до адресата ­ поддержка"надежности" передачи данных остается за оконечными устройствами­приложениями.Помимо существенного упрощения сетевой архитектуры принцип прозрачности непозволял Сети обрести специализацию, что усложнило бы ее применение для других,пока неизвестных приложений. Благодаря этому принципу и соответствующей емуархитектуре Интернета, а также открытости стандартов, на которых построена всясистема, входной порог участия был (и пока остается) чрезвычайно низким, апользователи скорее являются "вкладчиками", привнося в Сеть свои инновационныеразработки.На самом деле это единственный архитектурый подход, который может работать вИнтернете. Ведь сама Сеть образована из некоординированной связности разнородныхсетей, каждая со своими параметрами производительности, технологиями и задачами.Взаимоотношения между сетями в большинстве сводятся к одному из двух вариантов ­отношения пиров или предоставление транзита. В редких случаях эти договоренностивключают нечто большее, чем "маршрутизацию и передачу пакетов данных в режиме besteffort". Универсально обязательным является только использование протоколовинтернета7. 4­х уровневая модель Интернета8. Интернет IP­сервисIP объединяет сегменты сети в единую сеть, обеспечивая доставку данных междулюбыми узлами сети. Он классифицируется как протокол третьего уровня по сетевоймодели OSI. IP не гарантирует надёжной доставки пакета до адресата. В частности,пакеты могут прийти не в том порядке, в котором были отправлены, продублироваться(приходят две копии одного пакета), оказаться повреждёнными (обычно повреждённыепакеты уничтожаются) или не прийти вовсе. Гарантию безошибочной доставки пакетовдают некоторые протоколы более высокого уровня —транспортного уровня сетевоймодели OSI, — например, TCP, которые используют IP в качестве транспорта.●●●Предотвращает «зацикливание» пакетовФрагментирует пакеты если они слишком длинныеИспользует контрольную сумму, чтобы сократить возможности доставки внеправильное место назначение● Две версии○ IPv4 с 32 битным адресом○ IPv6 с 128 битным адресом● Позволяет добавлять новые опции к заголовку9. Интернет: модель TCP/UDP сервисов10. Интернет модель ICMP сервиса●●●●Предназначен для поддержки IP протоколаIP протокол○ Создает IP дейтаграммы○ Передает их hop­by­hopТаблицы маршрутизации и алгоритмы распространения таких таблицICMP протокол○●●●Обеспечивает коммуникацию между сетевыми уровнями хостов имаршрутизаторов○ Сообщения об ошибках○ Диагностика проблемICMP предоставляет информацию о сетевом уровне хостам и маршрутизаторамICMP работает над IP и относится к транспортному уровнюping и traceroute реализованы с помощью ICMP11. Примеры сетевых приложенийОбщие особенности BitTorrent●●●●●●●●Отсутствие очередей на скачивание.Файлы закачиваются небольшими фрагментами; чем менее доступен фрагмент,тем чаще он будет передаваться. Таким образом, присутствие в сети «сидера» сполным файлом для загрузки необязательно — система распределяет сегментымежду «пирами», чтобы в последующем они могли обмениваться недостающимисегментами.Клиенты (peers) обмениваются сегментами непосредственно между собой, попринципу «ты — мне, я — тебе».Скачанные фрагменты становятся немедленно доступны другим клиентам.Контролируется целостность каждого фрагмента.На фрагменты разбиваются не отдельные файлы, а вся раздача целиком, поэтомуу «личера», пожелавшего скачать лишь некоторые файлы из раздачи, дляподдержания целостности фрагментов нередко будет храниться также небольшойобъём избыточной (для него) информации.В качестве объекта раздачи могут выступать несколько файлов (например,содержимое каталога).Трекер — специализированный сервер, работающий по протоколу HTTP. Трекернужен для того, чтобы клиенты могли найти друг друга.12. Пакет13. Средства описания протоколов. Диаграммы переходов дляконечных автоматов14. Коммутация пакетов: что это такое?Коммутация каналов● У каждого соединения точка­точка своя гарантированная, изолированнаяпропускная способность● Каждый звонок состоит из трех фаз:○ Установление соединения точка­точка●●○ Передача○ Разрыв соединенияВо времена Александра Белла соединение представляло собой проводСегодня, соединение – это виртуальный индивидуальный проводКоммутация каналов: проблемы● Неэффективность: взаимодействие между компьютерами в сети очень неравномерно (набор текста по ssh соединению и просмотр web страницы). Есликаждая коммуникация будет использовать выделенное соединение, это будеткрайне неэффективно.● Большой разброс скоростей взаимодействия● Управление состоянием взаимодействия: все коммутаторы, задействованные всоединении должны поддерживать согласованно состояние взаимодействияКоммутация пакетов● Пакеты маршрутизируют индивидуально согласно адресам локальной таблицымаршрутизации● Все пакеты используют полную пропускную способность канала● Маршрутизаторы не поддерживают состояния каждого взаимодействия●Эффективное использование дорогих каналов○ Каналы всегда дорогие и дефицитны○ Коммутация пакетов позволяет многим крайне неравномерным потокамэффективно разделять один и тот же канал○ Коммутация каналов редко используют для соединения компьютеров из­занеэффективности использования линий● Устойчивость к ошибкам каналов и маршрутизаторов● Если какой­то канал или маршрутизатор будет разрушен/выйдет из строя, тоутерянную дейтаграмму всегда можно послать еще раз другим маршрутом15. Коммутация пакетов: сквозная задержка (e2e delay)Задержка распространения­время распространения одного бита поканалу со скоростью CЗадержка пакетизации∶время,за которое биты с первого до последнего переданы в каналПример 1: 64Кб пакет будет передан в канал с пропускной способностью 100Мб/с за 5.12μсПример 2: 1Кб пакет будет передан в 1 Кб/с канал за 1.024 с.Answer the following as it relates to the link layer and a telephony application. Suppose that apacket consists ofP bytes of data and 18 bytes of header. Consider sending a digitally encoded voice streamencoded at 128 kb/s.Assume that a packet payload is completely filled (at a rate of 128 kb/s) before the packet issent. The time tofill the packet payload is called the packetization delay.a) What is the packetization delay for packets with P = 46 bytes and P = 1500 bytes?1.5 pts for each calculation (3 pts total and round­up)Packetization delay for P = 46 bytes = (46 * 8) / 128,000 = 2.875 millisecondsPacketization delay for P = 1500 bytes = (1500 * 8) / 128,000 = 93.75 millisecondsЗадержка в очереди:16. Коммутация пакетов: ресиверная буферизация playbackbufferPlayback buffer (буфер­ресивер)● При коммутации пакетов е2е задержка – величина изменчивая. Буфер­ресиверпозволяет сгладить эти изменения.● Можно делать буфер­ресивер сразу большим, но тогда будет большая задержка настарте.● Поэтому приложение должно оценивать задержку, устанавливать размербуфера­ресивера, и изменять этот размер при изменении задержки.● Приложения реального времени используют ресиверную буферизацию длясглаживания задержек в очередях17. Коммутация пакетов: модели с очередямиКоммутация пакетов: простая модель с очередями● Для понимания динамики пакетов в сети вполне подходит простаядетерминированная модель.● Разбиение сообщения на пакеты позволяет нам параллельно передаватьнесколько пакетов, сокращая е2е задержку.● Статистическое мультиплексирование позволяет передавать несколько потоковчерез один и тот же канал18. Коммутация пакетов: свойства очередей●●●нерегулярность увеличивает задержкунеравномерность увеличивает задержкудетерминизм сокращает задержкуПуассоновский процесс● Процесс поступления является Пуассоновским если:○ Вероятность поступления k заявок за t секунд○ Интервалы между последовательнымипоступлениями независимы● Тогда число заявок поступивших за время t : E = λt● Пуассоновские процессы хорошо моделируют многие случайные процессы(телефонные звонки, распад частиц, шумы в электрических цепях и т.д.)● Удобный математический аппарат●●●Сетевой трафик очень не регулярныйПоступление пакетов не является Пуассоновским процессомВполне подходит для моделирования поступления новых потоков19­20. Коммутация пакетов: как работает пакетный коммутаторEthernet коммутатор1.Проверяет заголовок каждого прибывающего кадра2.Если адрес DA есть в таблице коммутации, то кадр передают на надлежащийвыходной порт3.Если адрес DA нет в таблице, кадр рассылается по всем портам, кроме того накоторый пришел.4.Когда придет ответ на разосланный пакет, то по его адресу отправителя мыузнаем , куда надо направлять пакеты с такими адресами получателей.Интернет маршрутизатор1.Если Ethernet DA поступившего кадра есть Ethernet адрес маршрутизатора, топринять кадр, иначе сбросить его.2.Просмотреть поля IP version и длина дейтаграммы3.Сократить поле TTL, пересчитать контрольную сумму IP заголовка4.Проверить TTL на 05.Если IP DA есть в таблице маршрутизации, переслать на надлежащий выходнойпорт для следующего скачка (hop)6.Найти Ethernet DA для следующего маршрутизатора7.Построить новый Ethernet кадр и отправить егоБазовые операции коммутатора1.Поиск адреса: как адрес ищется в таблице маршрутизации?2.Коммутация: как пакет пересылают на надлежащий выходной порт?Поиск адреса: EthernetТаблица Ethernet адресовАдреса хранятся в хэш­таблицеИщем в хэш­таблице точное совпадениеТаблица IP адресов в маршрутизатореИщут совпадение по самому длинному префиксу,а не точное совпадение.Троичная Ассоциативная памятьДвоичная АП — простейший тип ассоциативной памяти, который использует слова поискаданных, состоявшие полностью из единиц и нулей. В троичной АП добавляется третьезначение для сравнения «X» или «не важно», для одного или более битов в сохраненномслове данных, добавляя таким образом большей гибкости поиску. Например, в троичнойАП могло бы быть сохранено слово «10XX0», которое выдаст совдпадение на любое изчетырех слов поиска «10000», «10010», «10100», или «10110». Добавление гибкости кпоиску приходит за счет увеличения цены двоичной АП, поскольку внутренняя ячейкапамяти должна теперь закодировать три возможных состояния вместо двух. Этодополнительное состояние обычно осуществляется добавлением бита маски«важности»(«важно»/«не важно») к каждой ячейке памяти.Голографическая ассоциативная память обеспечивает математическую модель дляинтегрированного ассоциативного воспоминания бита «не важно», используякомплекснозначное представление.Поиск адреса <совпадение, действие>Обобщение поиска и коммутации в коммутаторах,маршрутизаторах и т.п.БуферизацияОрганизация очередей на входе.Примером такого варианта размещения может служить организация буферов на входныхпортах неблокирующей структуры с пространственным разделением, напримербаньяновидной сети Бэтчера. К его недостаткам можно отнести опасность возникновенияблокировки в начале очереди. Если две одновременно поступившие ячейки направляютсяна один и тот же выходной порт, одна из них попадет во входной буфер и будетпрепятствовать прохождению следующих за ней ячеек, снижая тем самым пропускнуюспособность коммутатора. Решением проблемы является значительное увеличениепроизводительности коммутационного поля с пространственным разделением или заменадисциплины «пришедший первым обслуживается первым» (FIFO) на другую, скажем«пришедший первым обслуживается в случайном порядке» (FIRO).Организация очередей на выходе.Этот тип буферизации используется в выходных портах структуры с разделяемой шиной.Он оптимален с точки зрения производительности и задержек, но требует применениядополнительных средств для организации одновременной множественной доставки ячеекна любой выходной порт. Таким образом, либо выходные буферы должныфункционировать с достаточно высокой скоростью, либо на каждом выходном портетребуются несколько буферов. Оба решения ограничивают производительность имасштабируемость устройства: в первом случае — из­за необходимости существенноповысить внутреннее быстродействие коммутатора, а во втором — буферов.Head­of­line blocking:Решение проблемы ­ Virtual Output Queueing(VOQ):Each output port has n buffers per port to accommodate a given maximum number ofsimultaneous data packets that each port can receive at a time. This buffering mechanismremoves the bottleneck per port on peak time and distributes it over a period of time increasingthe switch performance.Пакетный коммутатор: заключение● Пакетный коммутатор выполняет две базовые операции:○ Поиск соответствия в таблице коммутации○ Передачу на надлежащий выходной порт● Самый простой и самый медленный коммутатор использует буферизацию навыходе с минимальной задержкой пакета● Высокоскоростные коммутаторы используют буферизацию на входе свиртуальными очередями на выходах для увеличения пропускной способности.21. Коммутация пакетов: приоритеты и гарантированнаяскорость потокаВзвешенная справедливая очередь (англ. Weighted fair queuing, WFQ) — механизмпланирования пакетных потоков данных с различными приоритетами. Его целью являетсярегулировать использования одного канала передачи данных несколькимиконкурирующими потоками. В данном случае под потоком понимается очередь пакетовданных.Это обобщение алгоритма честных планировщиков (англ. Fair Queuing) (FQ). Обапланировщика имеют отдельные FIFO­очереди для каждого потока данных. Так, есликанал со скоростью   используется для   потоков, то скорость обработки каждого изних будет  при использовании честного планировщика. Честный планировщик сприоритетнымикоэффициентами позволяет регулировать долю каждого потока. Еслиимеется  активных потоков, с приоритетами , то  ­ый поток будет иметьскорость .●●FIFO очередь – нет приоритетов, не гарантирована скоростьСтрогие приоритеты: высокоприоритетный трафик «не видит» низкоприоритетноготрафика в сети. Полезно, когда высокоприоритетного трафика ограниченноеколичество● Waited Fair Queuing (WFQ) позволяет каждому потоку обеспечить гарантированныйсервис, планируя их в порядке bit­by­bit finishing time22. Коммутация пакетов: гарантированная задержка●Если мы знаем длину очереди и дисциплину ее обслуживания, то мы можемограничить величину задержки в ней.● Выбрав длину очереди, и, используя WFQ, мы можем определить скоростьобслуживания.● Поэтому самое главное не допустить сброса пакетов. Для этого можноиспользовать текущий буфер.● Таким образом, мы можем ограничить величину е2е задержки.23. Интернет: управление потоком (Stop and Wait)Stop and Wait (используется, например, протколом TFTP, который использует UDP):● В одно и то же время передают не более одного пакета● Sender отправляет пакет● Receiver посылает пакет с ack , когда получает пакет данных● Получив аск, sender шлет новый пакет с данными●По time_out, sender повторно посылает пакет с даннымиИсходы:Решение проблемы дублирования:Счетчик на 1 бит в данных и уведомлении позволяет отличать новые данные отдубликатов.Будем предполагать:● Сама сеть не размножает пакеты● Запаздывание пакетов гарантированно не более одного time_out24. Интернет: управление потоком (Sliding Window)Сделаем обобщение S&W протокола:● Разрешаем использовать сразу несколько неподтвержденных сегментов● Максимальное число таких сегментов – окно● Можем плотно «забить» каналSliding Window (используется в TCP) позволяет отправителюпередать несколько пакетов, перед тем как он остановится и будетждать подтверждения. При этом данные передаются быстрее, таккак отправитель не должен останавливаться и ждатьподтверждения каждый раз после отправки пакета.SW Sender:●●У каждого сегмента есть последовательный номерПоддерживаются 3 переменных:○ Размер окна отправки (SWS ­ Send window size)○ Последнее полученное подтверждение (LAR ­ last ACK received)○ Последний отправленный сегмент (LSS ­ last segment sent)● Всегда (LSS – LAR) ≤ SWS● LAR возрастает при каждом новом подтверждении● Буфер на SWS сегментов (неподтвержденных)Sender actions:● When an ACK offrame K arrives, set LAR to K and send up to (K ‐ LARold) segments●  Associate a timer with each transmitted frame;retransmit the frame upon timeout.SW Receiver:●●●●Поддерживаются 3 переменных:○ Размер окна отправки (RWS ­ Receive Window Size)○ Наибольший допустимый сегмент (LAS ­ largest acceptable segment)○ Последний полученный сегмент (LSR ­ last segment received)Всегда (LAS – LSR) ≤ RWSLAS возрастает при каждом новом подтвержденииЕсли полученный сегмент < LAS, то шли подтверждение○ Накопительный ack: если получены 1,2,3,5 – подтверждаем 3○ ТСР в уведомлении подтверждает номер ожидаемого сегментаRWS, SWS и пространство последовательных номеров:● RWS≥ 1, SWS ≥ 1, RWS ≥ SWS● Если RWS=1, “go back N” протокол, нужно SWS+1 последовательных номеров● Если RWS=SWS, нужно 2 SWS последовательных номеров● В общем случае нужно RWS + SWS номеров○ RWS пакеты в неизвестном состоянии (аск могут быть утеряны)○ SWS пакеты в пути, но не должны переполнять пространствопоследовательных номеровУправление потоком в ТСР:● Receiver информирует о размере RSW через поле Window в ТСР заголовке● Sender может посылать данные с номерами не больше LAR + windowУправление потоком с SW:● Допускает в окне только пакеты в пути, т.е. неподтвержденные● Как только пришло уведомление, окно сдвигается● Необходимое пространство последовательных номеров зависит от размера окна(поле window)Пример:25. Интернет: ФрагментацияПроблема возникает когда PDU верхнего уровня превышает PDU на нижних уровнях●Фрагментация: получаем PDU большого размера и разбиваем его на короткиепорции● Сборка: получаем набор коротких порций данных и собираем их в нужном порядке.● Пример:○ Транспорт: ТСР получает поток байт и разделает его на ТСР сегменты○ Сетевой: IP пакет может оказаться слишком коротким для ТСР сегмента○ Канальный: IP пакет длиннее кадра (Ethernet кадр – 1,5КБ, IP packet – 64KБ)Фрагментация: пример на IP●●●●●●●IP адреса + поле ident идентифицируют фрагментыпакетаФлаг MF =1 у всех фрагментов кроме последнегоПоле offset указывает смещение фрагмента (8байтовыми порциями)Длины всех фрагментов кроме последнего должныбыть кратны 8 байтамЕсли IP­дейтаграмма подверглась фрагментации, онане будет собрана, пока не достигнет конечного пунктаназначения.Если IP­дейтаграмма была фрагментирована, токаждый фрагмент становится отдельным пакетом сосвоим собственным IP­заголовком.Несмотря на то что IP­фрагментация выполняется"незаметно" для транспортно​го уровня, она можетпривести к нежелательным последствиям, которыесказывают​ся на уровнях выше IP. Дело в том, что из­запотери одного фрагмента потребуется передатьповторно всю дейтаграмму, а поскольку в самомпротоколе IP не предус​мотрены таймаут и повторнаяпередача, то эти функции должны быть возложены на более высокие уровни.ПротоколTCP осуществляет повторную передачу по таймауту, a UDP — нет.(Некоторые приложения, использующие UDP, сами реализуют ме​ханизм таймаута иретрансмиссии.)●Если окажется, что потерян некоторый фрагмент сегмента TCP, то по таймаутубудет повторена передача всего сегмента TCP, который содержался вфрагментированной IP­дейтаграмме. Повторная передача отдельного фрагментаIP­дейта​граммы невозможна в принципе.Фрагментация: пример ТСР● Избегай IP фрагментации всегда, когда можно● ТСР может выбирать размер сегмента так, чтобы избежать фрагментации● Флаг DF (don't fragment). Если установлен флаг DF, модуль IP не станетфрагментировать дейтаграмму. Вмес​то этого дейтаграмма отбрасывается и попротоколу ICMP генерируется сообщение об ошибкенеобходима фрагментация,но установлен флаг запрета фрагментации, которое посылается отправителюпакета.26. Интернет: Обнаружение ошибок – 3 схемыДобавление контрольной суммы в пакеты IP, TCP● Быстро, аппаратно, но можно и программно● Не очень надежноПолиномиальные CRC коды (используются в Ethernet кадрах)● Дороже контрольной суммы (вычисляются аппаратно)● Устойчивы к двукратным ошибкам, групповым ошибкам и ошибкам четностиMessage Authentication Code (MAC): на основе криптографии● Защищает от малейших модификаций сообщений, но не от ошибок● 2 сообщения длины n могут иметь одинаковый МАС с вероятностью 1 / 2^nКонтрольная сумма в IP пакете:● IP, UDP и ТСР используют один и тот же алгоритм комплементарной контрольнойсуммы:○ Установить поле checksum= 0○ Сложить все 16 разрядные слова в пакете○ Установить разряд четности○ Контрольная сумма должны быть такой чтобы сумма всего пакета, включаяконтрольную сумму была бы 0хffff● Основное достоинство – простота● Недостаток – слабая защита от ошибок (только одиночные ошибки).● Пример расчёта контрольной суммы○ Для примера рассчитаем контрольную сумму нескольких 16­битных слов:0x398a, 0xf802, 0x14b2, 0xc281. Находим их сумму с поразряднымдополнением. 0x398a + 0xf802 = 0x1318c → 0x318d○ 0x318d + 0x14b2 = 0x0463f → 0x463f○ 0x463f + 0xc281 = 0x108c0 → 0x08c1○ Теперь находим поразрядное дополнение до единицы полученногорезультата:○ 0x08c1 = 0000 1000 1100 0001 → 1111 0111 0011 1110 = 0xf73e или, иначе —0xffff − 0x08c1 = 0xf73e. Это и есть искомая контрольная сумма.Обнаружение и исправление ошибок:● Ошибки единичные и групповые (блочные)● Коды с обнаружением ошибок○ кодослово○ расстояние Хемминга● Коды исправляющие ошибки○ 0000000000, 0000011111, 1111100000,1111111111○ (n+1)2m  2n; (m+r+1)  2rКод Хемминга для единичных ошибок:● разряды кодослова нумеруют слева направо, начиная с 1;● все биты, номера которых есть степень 2 (1,2,4,8,16 и т.д.) ­ контрольные,остальные ­ биты сообщения;● каждый контрольный бит отвечает за четность группы битов, включая себя. Одини тот же бит может относиться к разным группам. Значение бита сообщенияопределяется по значениям контрольных битов. Чтобы определить какиеконтрольные биты контролируют бит в позиции k надо представить значение k постепеням двойки. Например, 11= 1+2+8, 39=1+2+4+32.(CRC ­ Cyclic redundancy check)● Отправитель и получатель договариваются о конкретном генераторе полиномовG(x) степени r (коэффициенты при старшем члене и при младшем члене должныбыть равны 1).● Для вычисления контрольной суммы блока из m бит надо чтобы обязательно m>r.● Добавить контрольную сумму к передаваемому блоку, рассматриваемому какполином М(х) так, чтобы передаваемый блок с контрольной суммой был кратенG(x). Когда получатель получает блок с контрольной суммой, он делит его на G(x).Если есть остаток, то были ошибки при передаче.● Алгоритм вычисления контрольной суммы:○ Добавить r нулей в конец блока так, что он теперь содержит m+r разрядов исоответствует полиному xrM(x);○ Разделить по модулю 2 полином xrM(x) на G(x);○ Вычесть остаток ( длина которого всегда не более r разрядов) из строки,соответствующей xrM(x), по модулю 2. Результат и есть блок с контрольнойсуммой ( назовем его Т(х)).● Существует три международных стандарта на вид G(x):○ CRC­12 = x12+x11+x3+x2+x+1○ CRC­16 = x16+x15+x2+1○ CRC­CCITT = x16+x12+x5+1●CRC­12 используется для передачи символов из 6 разрядов. Два остальных ­ для8 разрядных. CRC­16 и CRC­CCITT ловят одиночные, двойные ошибки, групповыеошибки длины не более 16 и нечетное число изолированных ошибок свероятностью 99,997%.Message Authentication Code (MAC)● Использует криптографию для вычисления m= MAC (M,s), |m|<<|M|○ M известно, s – секретно => можем проверить m= MAC (M,s), |m|<<|M|○ Если s не известно, то получить m практически не возможно○ Если известно m, то практически не возможно вычислить M, даже зная MAC● Не столь устойчиво к ошибкам как CRC● Защищает от злоумышленников27. Интернет: заголовок TCPСвойствоПоведениеПоток байтСервис доставки байтС установкой соединенияПроцедура 3­х кратного рукопожатияНадежная доставка1.Ack подтверждает доставку2.Контрольная сумма выявляет ошибкипередачи (охватывает весь сегмент)3.Последовательные номера позволяютобнаружить пропущенные данные4.Управление потоком предотвращаетполучателя от «захлебывания»Сохранение последовательностиДанные доставляют приложению в том жепорядке, в каком они передавалисьУправление перегрузкойУправление перегрузками в сети28. TCP: установка и разрыв надежного соединенияПроблемы● Надежность взаимодействия достигается благодаря наличию согласованныхсостояний на концах соединения● Проблема: как установить соединение (установить согласованные состояния)● Проблема: как разорвать соединение (установить согласованные состояния,освободить порты, очереди и т.д.)Сеанс обмена данными заканчивается процедурой разрыва соединения, котораяаналогична процедуре установки, с той разницей, что вместо SYN для разрываиспользуется служебный бит FIN (“данных для отправки больше не имею”), которыйустанавливается в заголовке последнего сегмента с данными, отправляемого узлом.Разрыв ТСР соединенияДля того чтобы установить соединение, необходимо 3 сегмента, а для того чтобы разорвать ­ 4. Этообъясняется тем, что TCP соединение может быть в наполовину закрытом состоянии. Так как TCPсоединениеполнодуплексное (данные могут передвигаться в каждом направлении независимо отдругого направления), каждое направление должно быть закрыто независимо от другого.●●●Разряд FIN означает, что более данных не будет○ Это вызывает закрытие/очистку очередей на стороне получателяЧтобы соединение было разорвано, обе стороны должны обменяться FINТипичная последовательность обменов при разрыве●Закрытие может выполняться одновременно обеими сторонамиБезопасное закрытие сокета● Проблемы с закрытым сокетом○ Что будет если последний АСК будет потерян?○ Что будет если та же пара портов будет сразу повторно использована длянового соединения?● Решение: инициатор разрыва устанавливает Time Wait○ Инициатор разрыва шлет FIN до того как он получит такой же○ Не закрывает сокет в течении 2 MSL (Maximum Segment Lifetime)● Одновременное закрытие:●Проблемы на стороне сервера:○ Работа OS замедляется, т.к. очень много сокетов в состоянии Time Wait○ Уязвимость: в состоянии Time Wait можно послать RST и переустановитьпараметры сокета29. Интернет: перегрузкаПримеры перегрузок:● Столкновение двух пакетов в маршрутизаторе● Потоки превысили пропускную способность канала● Слишком много пользователей используют один и тот же канал в одно и то жевремяПерегрузки неизбежны!● Коммутацию пакетов используют потому, что она позволяет эффективноиспользовать пропускную способность каналов. Поэтому буферы вмаршрутизаторах часто загружены.● Если буферы пусты, задержки малы, но интенсивность использования сети низкая.● Если буферы постоянно загружены, задержки возрастают, но интенсивностьиспользования сети возрастаетЗамечания● Перегрузки неизбежны и возможно желательны● Перегрузки возможны в разных случаях○ Коллизия пакетов в маршрутизаторе○ Некоторые потоки шлют данные с очень большой скоростью○ Толпа пользователей объявилась в сети● Если пакет был сброшен, то его ретрансмиссия может усугубить перегрузку● Когда пакет сброшен, то все ресурсы, которые были потрачены до того чтобы егодоставить к месту сброса, потрачены зря● Необходимо ввести понятие справедливости, чтобы решить как потоки будутразделять ресурсы перегруженного каналаСправедливость и пропускная способностьРаспределение ресурсов1. rA = 0.25, rB = 1.75, rC = 0.75 Общая пропускная способность = 2.752. rA = 0.5, rB = 1.5, rC = 0.5 Общая пропускная способность = 2.5Случай 2 «справедливее».Max­min справедливостьОпределение:Распределение max­min справедливо если нельзя увеличить скорость какого­нибудьпотока, не понизив скорости другого потокаЦели управления перегрузкой1.Высокая пропускная способность: каналы загружены, скорость потоков высокая2.max­min справедливость3.Быстрая реакция на изменения состояния сети4.Распределенное управление30. Управление перегрузкой: основные подходыОчередь со справедливой дисциплиной (FQ ­ Fair Queuing)● Он  является  основой  для   целого  класса  дисциплин   управления  очередями,  вкоторых каждый пакет рано или поздно гарантированно будет обслужен.● Смысл  его  работы  состоит  в  том,  что  все  пакеты  разделяются  классификаторомна  потоки,  для каждого потока создается FIFO очередь, а  из FIFO очередей пакетыизвлекаются  при  помощи  карусельного  планировщика  –  сначала  проверяетсяпервая  очередь  на  наличие  пакета,  если  он  есть,  он  извлекается,  и  алгоритмпереходит  ко  второй,  и  т.д.  Если  очередь  пуста,  то  она игнорируется и начинаетсяработа со следующей очередью.Управление перегрузками в ТСР● В ТСР управление перегрузкой размещается на конечном хосте● Реакция на события, наблюдаемые на конечном хосте (например, потеря пакета).● Использование скользящего окна, предназначенного для управления потоком вТСР● Постараться оценить сколько пакетов можно безопасно отправить в сетьодновременно.●ТСР варьирует число пакетов отправляемых в сеть, изменяя размер скользящегоокна:cwnd ­ Congestion WindowAIMD (Additive Increase Multiple Decrease)В ТСР управление перегрузкой располагается на хосте● Реакция на события, наблюдаемые на конечном хосте (например, потеря пакета).● Использование скользящего окна, предназначенного для управления потоком вТСР● Постараться оценить сколько пакетов можно безопасно отправить в сетьдновременно.● Изменять размер окна в соответствии с алгоритмом AIMD31. Управление перегрузкой: AIMD с одним потоком●●В протоколе TCP используется так называемое «мультипликативное уменьшение»,означающее двойное уменьшение размера окна перегрузки при потере пакета.