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

38. Управление перегрузкой.TCP Reno.По time_out поведение такое же как и у TahoeПри тройном уведомленииo устанавливает порог = CWDN/2o CWDN=CWDN/2 (быстрое восстановление)o Повторно пересылает пропущенный сегмент (быстрое retransmit)o Остается в фазе избегания перегрузкиTCP New RenoПо time_out поведение такое же как и у Tahoe/RenoВ фазе быстрого восстановления:o при входе в эту фазу - запомнить последний неподтвержденный пакетo при каждом повторном уведомлении – увеличить CWND на MSSo Когда последний пакет подтвержден: вернуться в фазу избегания перегрузки восстановить размер CWDN до того размера, который оно имело до входа вфазу быстрого восстановленияo Начать отправку новых пакетов пока находимся в фазе быстрого восстановленияУправление перегрузкамиОдна из сложнейших проблем в компьютерных сетях (особенно на неоднородных,протяженных, с ошибками соединениях)Основной подход: AIMD (additive increase, multiple decrease)Для того чтобы поддерживать канал заполненным в соответствии с его пропускнойспособностью, хорошо бы:o Быстрая повторная пересылка данных (не дожидаясь time_out)o Увеличение CWDN (не ждать RTT, чтобы послать новые данные)40.

Основы маршрутизацииАлгоритмы маршрутизации часто используют соединяющие деревья с минимальнойстоимостью до места назначенияМаршрутизация с множественными путями позволяет распределять нагрузку понескольким линиям одновременноГрупповая маршрутизация обеспечивает доставку сразу нескольким хостам1Маршрутизация лавиной (затопление)Каждый поступающий пакет отправляется по всем имеющимся линиям за исключением той, покоторой он поступил.Неэффективное использование линийПакеты могут зацикливатьсяo нужно ограничивать время жизни пакетов (начальное значение можно задатьхудшим случаем: диаметром графа (наибольшим расстоянием между паройвершин в графе))o можно также отслеживать пакеты, проходящие несколько раз через один и тот жемаршрутизатор. Если такие возникают, то их нужно сбрасывать (для распознаваниякаждый маршрутизатор помечает пакет своим уникальным номером)Используется когда топология не известна (или ей нельзя доверять)Маршрутизация от источникаНе требует поддержки от сетиПакеты содержат списки адресов, переменной длины (могут быть очень длинными)Выбор маршрута на конечном хосте, который должен знать топологиюИспользуется, когда пользователь хочет сам управлять маршрутизациейМаршрутизация по таблицам коммутацииОптимизация: сеть маршрутизирует по скачкамНеобходимо много таблиц коммутацииСостояния от места назначения, а не от потокаМаршрутизация по наикратчайшему путиСтатический алгоритм, идея которого заключается в построении графа транспортной среды (гдевершины – маршрутизаторы, а дуги – каналы связи) и нахождении наикратчайшего пути в этомграфе (по алгоритму, например, Дейкстры).Метрики:мин.

Расстояниемин. Скачкимин. Задержкамакс. пропускная способностьмин. Загруженныймакс. надежныйс мин. Стоимостьюмакс. Безопасный2…Соединяющее деревоВсе маршруты к заданной точке транспортной среды образуют дерево с корнем в этой точке,которое называется деревом захода (т.к. это дерево, то в нём нет циклов + оно соединяющее —все листья достижимы).41. Маршрутизация по вектору расстоянияКак маршрутизаторы могут совместно найти соединяющее дерево минимальной стоимости? Длярешения этой проблемы применяют алгоритм Беллмана-Форда.Алгоритм Беллмана-Форда:У каждого маршрутизатора в транспортной среде есть таблица расстояний до всех другихмаршрутизаторов, принадлежащих этой транспортной среде. Периодически каждыймаршрутизатор обменивается этой информацией со своими соседями и обновляет информацию всвоей таблице.

Каждый элемент этой таблицы включает в себя два поля: первое – номер канала,по которому следует отправлять пакеты, чтобы достичь нужного места, второе – значениезадержки до места назначения.(пример для R8):Пусть каждый маршрутизатор знает стоимость линии к каждому его соседуМаршрутизатор Ri рассчитывает стоимость Сi для достижения R8Вектор С = (С1,С2, … ,С7) – вектор расстояния до R8Изначально С = (∞, ∞, … , ∞)1. После Т секунд, Ri шлет Сi всем своим соседям2. Если Ri нашел более дешевый пусть, то он обновляет Сi у всех своих соседей3. Вернуться к 1Проблемы:3Плохие вести распространяются медленно: информация о разрушении какого-либомаршрута может идти очень долго (а счётчик задержки будет бесконечно расти).Установить ограничение на «бесконечность» (e.g.

16)Разделение горизонта: т.к. R2 получает данные о маршруте с наименышей стоимостью отR3, то запретить ему это делатьРазделение горизонта с бесконечностью: R2 посылает R3 ∞Есть и другие проблемы, связанные с алгоритмом Б-ФБ-Ф на практикеЭтот алгоритм использовался в первых Интернет протоколах маршрутизации RIPОн не требует больших вычислений, распределенный и, в конечном счете, сходитсяСо временем он был вытеснен алгоритмами, которые рассчитывали соединяющее дереводля каждого маршрутизатора42. Маршрутизация по состоянию каналаКаждый маршрутизатор в транспортной среде должен выполнить пять шагов:1.

Определить список своих непосредственных соседей и их сетевые адреса (рассылка повсем подсоединённым каналам специального пакета HELLO, на который всемаршрутизаторы отвечают своими уникальными в данной сети именами).2. Изменить задержку или оценить затраты на передачу до каждого соседа (посылаетсяECHO пакет и замеряется время до его возвращения).3. Сформировать пакет, где указаны все данные, полученные на шаге 2 (отправитель,последовательное число, возраст, список соседей и задержки до них).4. Послать этот пакет всем другим маршрутизаторам. Проще всего рассылать лавиной, новозникают следующие проблемы:a.

Размер поля последовательных номеров пакетов (решено: поле 32 бита).b. Если маршрутизатор упал и потерял использованные последовательные номера,то неясно, как их восстановить.c. Если в результате передачи возникает ошибка в одном бите, например, вместопакета с номером 4 получили пакет с номером 65540, то все пакеты с 5-го номера4по 65540-ой будут сбрасываться как устаревшие, т.к. текущий номер: 65540(решение: поле «возраст» в пакете состояний каналов).5.

Вычислить наикратчайший маршрут до каждого маршрутизатора.Первый алгоритм Дейкстры поиска наикратчайшего пути1. Обмен состояниями линий: Маршрутизатор передает всем другим маршрутизаторамсостояния своих линий Периодически Когда изменяется состояние линии2. Вычисление по алгоритму Дейкстры: каждый маршрутизатор независимо запускаеталгоритм Дейкстры наикратчайшего пути.Каждый маршрутизатор знает состояние лини и находит соединяющее дерево с минимальнойстоимостью до каждого другого маршрутизатора.Этот алгоритм является основой OSPF (Open Shortest Path First) - широко используемогопротокола маршрутизации (том 2 стр.82-86).43. Маршрутизация в ИнтернетеАвтономная система (АС) — единица иерархии в Интернет (группа маршрутизаторов,обменивающихся маршрутной информацией через общий протокол маршрутизации)Внутри АС ее владелец решает как маршрутизировать потоки данныхМежду АС должен использоваться протокол BGP-4 (Border Gateway Protocol v4 RFC 1771)Алгоритмы маршрутизации, применяемые внутри АС называются внутренними протоколамишлюзов.

Алгоритмы маршрутизации, применяемые между АС, называются внешнимипротоколами шлюзов. Изначально в качестве внутреннего протокола шлюзов использовалсяпротокол по вектору расстояния RIP:RIP (RFC 2453)используют алгоритм по вектору расстояния (алгоритм Б-Ф)обновление векторов каждые 30 секундаутентификация при обновлениях не применяетсяизначально был использован в BSD Unixсегодня применяется редко (из-за отсутствия достойного решения проблемыбесконечного счётчика и медленной сходимости)В 1979 году RIP был заменён протоколом маршрутизации по состоянию каналов.

А в 1988 годуначали разработку внутреннего протокола маршрутизации шлюзов OSPF (Open Shortest Path First),который стал стандартом в 1990 году.OSPF (RFC 2328)изменения состояний линии рассылаются лавиной по необходимостикаждый маршрутизатор использует алгоритм Дейкстрыизменения аутентифицируютсяАлгоритм работает с разными метриками маршрутов: расстоянием, пропускнойспособностью, задержкой и т.п.Алгоритм должен обеспечивать балансировку нагрузки во избежание перегрузки и принеобходимости направлять потоки по разным каналам, а не только по наилучшему.5АС можно разбивать на области, где каждая область — это либо сеть, либопоследовательность сетей. Эти области не пересекаются. Область — это обобщениепонятия подсети.

Извне топологии область не видна. Каждая АС имеет магистральнуюобласть, называемую областью 0. Все области одной АС соединяются через магистральнуюобласть, возможно, при помощи туннелирования.Широко используется, сложныйАналог IS-IS (RFC 1142), который также широко используетсяМаршрутизация через одну точку выходаВ АС выделяют одну точку выхода, так что маршрутизаторы внутри АС могут использоватьмаршрутизацию по умолчаниюкаждый маршрутизатор знает все префиксы внутри АСПакеты для других АС пересылаются на маршрутизатор-выход по умолчаниюМаршрутизатор-выход по умолчанию – пограничный шлюз для других АСТаблицы маршрутизации в маршрутизаторах-выходах по умолчанию, как правило, имеютнебольшой размер.Маршрутизаторы через несколько точек выходаИспользуется в транзитных АСКаждому внутреннему маршрутизатору должно быть сообщено какую точку выхода ондолжен использовать для определенного префикса точки назначенияТаблица маршрутизации существенно разрастаетсяДва подхода:o «горячая картошка» – переслать ближайшему выходуo выбрать выход ближе всего к токе назначенияПротокол внешней маршрутизацииВсе АС взаимодействуют, используя протокол BGP-4BGP-4 был разработан чтобы решить следующие проблемы:o Топология: Интернет плохо структурированная смесь разнообразных АСo Автономия АС: каждая АС по-своему определяет стоимость линии, поэтомуневозможно построить путь с наименьшей стоимостьюo Доверие: некоторые АС не могут доверять тем маршрутам, которые предлагаютдругие АС (два конкурирующих провайдера, защита конфиденциальности черезтерриторию неприятеля)o Политика: разные АС преследуют разные цели (мин.

число скачков vsпредпочтение одного провайдера перед другими)6ЗаключениеИнтернет состоит из множества независимо управляемых АСКаждая АС использует свой внутренний протокол маршрутизацииОконечные АС используют простую маршрутизацию по умолчаниюТранзитные АС должны сами определять какой выход использоватьДля взаимодействия АС должны использовать BGP-4 протокол44. Маршрутизация BGP-4 (Border Gateway Protocol – протокол пограничных шлюзов)Основы BGP-47BGP использует «вектор пути»Каждый BGP маршрутизатор рассылает список путей (путь – список АС)o AS_PATHo К сети 171.64/16 можно пройти по пути {AS7,AS52,AS13}Наличие цикла в маршруте определяется локально и такие маршруты игнорируютсяИз множества доступных маршрутов выбирается тот, который наиболее всегосоответствует политике АСЕсли маршрутизатор/линии вышли из строя, то маршрут изымается из спискаИерархия заказчиков и провайдеровЗаказчики платят провайдеру за свои пакетыОтношение PeeringPeers предоставляют транзит для своих важных заказчиковPeers не допускают транзита через себя другим peersPeers не ведут, как правило, взаиморасчетовBGP сообщенияOpen — Установка BGP сессииKeep Alive — Проверка работоспособности через регулярные интервалыNotification — Закрытие peering сессииUpdate — Объявление нового или изъятие ранее объявленного маршрутаBGP объявление = префикс + атрибуты маршрутаPath attributeso следующий скачок (hop)o список АС (path)o предпочтения8ooправило определения выхода…Заключение о BGP-4Все АС для взаимодействия в Интернете должны использовать BGP-4BGP-4 использует алгоритм маршрутизации по вектору пути, которые легко распознаетциклыBGP-4 имеет сложный интерфейс, позволяющий каждой АС устанавливать свою локальнуюполитику маршрутизацииКаждая АС устанавливает свою политику для построения маршрутов, безопасности илокальных особенностей45.