8-1 Маршрутизация (Лекции 2014 года)

Маршрутизация: Основы(том 2 стр.30-52)Введение в компьютерные сетипроф. Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУПроблема• Как пакеты из А достигнут В?Введение в компьютерные сетипроф.Смелянский Р.Л.30.03.20142ОсновыПодходы• Лавиной• От источника• Таблица коммутации• Соединяющее деревоМетрикиСоединяющие деревья наикратчайшего путиДругие типы маршрутизации• по множеству путей• групповаяВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.20143Лавина• Не эффективное использование линий• Пакеты могут зацикливаться• Используется когда топология не известна (или ей нельзя доверять)Введение в компьютерные сетипроф.Смелянский Р.Л.30.03.20144Маршрутизация от источника• Не требует поддержки от сети• Пакеты содержать списки адресов, переменной длины(могут быть очень длинными)• Выбор маршрута на конечной хосте, который должен знать топологию• Используется когда пользователь хочет сам управлять маршрутизациейВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.20145Таблицы коммутации•••Оптимизация: сеть маршрутизирует по скачкамНеобходимо много таблиц коммутацииСостояния от места назначения, а не от потокаВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.20146Соединяющие деревьяСоединяющее деревосоединяющее – все листья достижимыдерево – нет цикловВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.20147МетрикиМетрики:• мин.

расстояние• мин. скачки• мин. задержка• макс. пропускная способность• мин. загруженный• макс. надежный• с мин. стоимостью• макс. безопасный• …Введение в компьютерные сетипроф.Смелянский Р.Л.30.03.20148Пример взвешенного графаВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.20149Пример взвешенного графаСоединяющее дерево с минимальной стоимостьюВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201410Введение в компьютерные сетипроф.Смелянский Р.Л.30.03.201411По множеству путейВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201412ГрупповаяВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201413ГрупповаяВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201414Заключение• Есть много способов маршрутизации пакетов в••••сетиДля расчета маршрута используют протоколмаршрутизацииАлгоритмы маршрутизации часто используютсоединяющие деревья с минимальной стоимостьюдо места назначенияМаршрутизация с множественными путямипозволяет распределять нагрузку по несколькимлиниям одновременноГрупповая маршрутизация обеспечивает доставкусразу нескольким хостамВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201415Маршрутизация повектору расстояния:алгоритм Белмана-Форда(том 2 стр.38-41)Компьютерные сетипроф.

Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУПроблемаКак маршрутизаторам могут совместно найти соединяющее деревоминимальной стоимости?Введение в компьютерные сетипроф.Смелянский Р.Л.30.03.201417Эквивалентно нахождению соединяющего дерева минимальной стоимоститолько среди маршрутизаторовВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201418Распределенный алгоритм БеллманаФорда (пример соединяющего дерева мин. стоимости для R8• Пусть каждый маршрутизатор знает стоимостьлинии к каждому его соседу• Маршрутизатор Ri рассчитывает стоимость Сi длядостижения R8• Вектор С = (С1,С2, … ,С7) – вектор расстояния до R8• Изначально С = (∞, ∞, … , ∞)1.2.3.Каждые Т секунд, R шлет С всем своим соседямЕсли R нашел более дешевый пусть, то он обновляет С у всех своихсоседейВернуться к 1iiВведение в компьютерные сетипроф.Смелянский Р.Л.ii30.03.201419Примершаг 0шаг 1Введение в компьютерные сетипроф.Смелянский Р.Л.шаг 2шаг 3шаг 4шаг 530.03.201420Алгоритм Беллмана-ФордаВопросы:1.

Каково максимальное время работы алгоритма?2. Всегда ли алгоритм будет сходиться?3. Что будет если измениться стоимость линии, илиотключится маршрутизатор/линия?Введение в компьютерные сетипроф.Смелянский Р.Л.30.03.201421Проблемы с алгоритмом Б-ФПлохие вести распространяются медленноРассмотрим расчет расстояния для R4Линия R3 - R4 недействуетИтак добесконечностиВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201422Проблема счетчика до бесконечности• Установить ограничение на «бесконечность» (e.g.16)• Разделение направлений: т.к. R2 получает данные омаршруте с наименышей стоимостью от R3, тозапретить R2 сообщать R3 о маршрутах, проходящихчерез R3• Разделение направлений с бесконечностью: R2посылает R3 ∞• Есть и другие проблемы, связанные с алгоритмомБ-ФВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201423Беллман-Форд на практике• Алгоритм Беллмана-Форда - пример алгоритма повектору расстояния• Этот алгоритм использовался в первых Интернетпротоколах маршрутизации RIP• Он не требует больших вычислений,распределенный и , в конечном счете, сходится• Со временем он был вытеснен алгоритмами,которые рассчитывали соединяющее дерево длякаждого маршрутизатораВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201424Маршрутизация посостоянию канала:алгоритм наикратчайшегопути Дейкстры(том 2 стр.33, 41-46)Введение в компьютерные сетипроф.

Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУПервый алгоритм Дейкстрынаикратчайшего пути1. Обмен состояниями линий: Маршрутизаторпередает лавиной всем другим маршрутизаторамсостояния своих линийooПериодическиКогда изменяется состояние линии2. Вычисление по алгоритму Дейкстры: каждыймаршрутизатор независимо запускает алгоритмДейкстры наикратчайшего пути.Каждый маршрутизатор находит соединяющее деревос минимальной стоимостью до каждого другогомаршрутизатораВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201426Пример для R8Введение в компьютерные сетипроф.Смелянский Р.Л.30.03.201427Пример для R8Добавляем путь стоимости1Введение в компьютерные сетипроф.Смелянский Р.Л.2230.03.201428Пример для R8Добавляем путь стоимости4Введение в компьютерные сетипроф.Смелянский Р.Л.430.03.201429Пример для R8Добавляем путь стоимости5Введение в компьютерные сетипроф.Смелянский Р.Л.630.03.201430АлгоритмВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201431АлгоритмВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201432Алгоритм ДейкстрыВопросы:o Сколько времени работает этот алгоритм?o Что происходит когда изменяется стоимостьлинии или когда маршрутизатор/линия выходятиз строя?Введение в компьютерные сетипроф.Смелянский Р.Л.30.03.201433Алгоритм Дейкстры на практике• Алгоритм Дейкстры – это пример алгоритма посостоянию каналаo состояние линии знает каждый маршрутизаторo каждый маршрутизатор строит соединяющее дерево минимальнойстоимости до каждого другого маршрутизатора• Этот алгоритм является основой OSPF (OpenShortest Path First) - широко используемогопротокола маршрутизации (том 2 стр.82-86)Введение в компьютерные сетипроф.Смелянский Р.Л.30.03.201434Маршрутизация вИнтернет(том 2 стр.82-88)Введение в компьютерные сетипроф.

Смелянский Р.Л.Лаборатория Вычислительных комплексовф-т ВМК МГУСодержание• Иерархия Автономных Систем• Протоколы Внутренней Маршрутизации• Структура ИнтернетВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201436Иерархическая структура ИнтернетВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201437Автономные СистемыЕдиница иерархии в ИнтернетooВнутри АС ее владелец решает как маршрутизировать потоки данныхМежду АС должен использоваться протокол BGP-4 (Border GatewayProtocol v4 RFC 1771)Как найти номер АС?Введение в компьютерные сетипроф.Смелянский Р.Л.30.03.201438Протоколы внутренней маршрутизацииRIP (RFC 2453 )(www.rfc.com.ru, http://www.ietf.org/rfc.html)•••••используют алгоритм по вектору расстояния (алгоритм Б-Ф)обновление векторов каждые 30 секундаутентификация при обновлениях не применяетсяизначально был использован в BSD Unixсегодня применяется редкоOSPF (RFC 2328)• изменения состояний линии рассылаются лавиной•••••по необходимостикаждый маршрутизатор использует алгоритм Дейкстрыизменения аутентифицируютсяАС можно разбивать на областиШироко используется, сложныйАналог IS-IS (RFC 1142), который также широко используетсяВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201439Маршрутизация через одну точку выходаВ АС выделяют одну точку выхода, так чтомаршрутизаторы внутри АС могут использоватьмаршрутизацию по умолчанию• Каждый маршрутизатор знает все префиксы внутри АС• Пакеты для других АС пересылаются намаршрутизатор-выход по умолчанию• Маршрутизатор-выход по умолчанию – пограничныйшлюз для других АСТаблицы маршрутизации в АС с одним выходом(маршрутизатор-выход) по умолчанию, какправило, имеют не большой размерВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201440Маршрутизация через несколько точеквыходаo Используется в транзитных АС и сетях международныхкомпаний с разветвленной сетью офисовo Каждому внутреннему маршрутизатору должно бытьсообщено какую точку выхода он должен использоватьдля определенного префикса точки назначенияo Таблица маршрутизации существенно разрастаетсяo Два подхода:• «горячая картошка» – переслать ближайшему выходу• выбрать выход ближе всего к токе назначенияВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201441Протокол внешней маршрутизацииo Все АС взаимодействуют, используя протокол BGP-4o BGP-4 был разработан чтобы решить следующиепроблемы:• Топология: Интернет плохо структурированная смесьразнообразных АС• Автономия АС: каждая АС по-своему определяетстоимость линии, поэтому невозможно построить путь снаименьшей стоимостью• Доверие: некоторые АС не могут доверять теммаршрутам, которые предлагают другие АС (дваконкурирующих провайдера, защита конфиденциальностичерез территорию неприятеля)• Политика: разные АС преследуют разные цели (мин.число скачков vs предпочтение одного провайдера переддругими)Введение в компьютерные сетипроф.Смелянский Р.Л.30.03.201442Структура ИнтернетВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201443Структура ИнтернетlocalTier 3localTier-2PrivatepeeringPoint-topointTier 1localTier-2Tier 1Tier-2locallocalВведение в компьютерные сетипроф.Смелянский Р.Л.localIIXPTier 1Tier-2localPublicpeeringSwitch farmTier-2local30.03.201444Заключение• Интернет состоит из множества независимо••••управляемых АСКаждая АС использует свой внутренний протоколмаршрутизацииОконечные АС используют простуюмаршрутизацию по умолчаниюТранзитные АС должны сами определять какойвыход использоватьДля взаимодействия АС должны использовать BGP4 протоколВведение в компьютерные сетипроф.Смелянский Р.Л.30.03.201445Маршрутизация в BGPВведение в компьютерные сетипроф.