Тема: сетевой уровень стека. маршрутизация и транзит пакетов Литература: Танненбаум. Компьютерные сети. [https://www.litmir.me/br/?b=639789&p=4] 5.2. Алгоритмы маршрутизации........................................... 392 5.2.1. Принцип оптимальности маршрута .............................. 394 5.2.2. Алгоритм нахождения кратчайшего пути.......................... 395 5.2.3. Заливка...................................................... 398 5.2.4. Маршрутизация по вектору расстояний .......................... 399 5.2.5. Маршрутизация с учетом состояния линий ....................... 403 5.2.6. Иерархическая маршрутизация ................................. 409 5.2.7. Широковещательная маршрутизация............................ 411 5.2.8. Многоадресная рассылка - 413 5.2.9. Произвольная маршрутизация - 416 5.2.10. Алгоритмы маршрутизации для мобильных хостов - 417 Сети и телекоммуникации : учебник и практикум для вузов / К. Е. Самуйлов [и др.] ; под редакцией К. Е. Самуйлова, И. А. Шалимова, Д. С. Кулябова. — Москва : Издательство Юрайт, 2020. — 363 с. — (Высшее образование). — ISBN 978-5-534-00949-1. — Текст : электронный // ЭБС Юрайт [сайт]. — URL: https://biblio-online.ru/bcode/450234 (дата обращения: 19.03.2020). Конспект лекций [сетевой уровень] - маршрутизация - выбор маршрута - передача через промежуточные узлы - единая система нумерации локальных/глобальных адресов - балансировка нагрузки - диагностика сети - объединение сетей - независимость от технологии маршрутизации -- можно использовать любую и комбинацию [маршрутизация] - выбор исходящего интерфейса конвергенция (convergence) - установление маршрута кратчайшего пути длина(метрика) пути - расстояние между узлами - кол-во промежуточных участков - среднее время передачи - пропускная способность - комбинация с учетом нужных характеристик алгоритма характеристики алгоритмов корректность - правильность простота - стоимость устройств надежность - изменение конфигурации устойчивость - быстрое нахождение путей справедливость/эффективность принцип оптимальности маршрута - оптимальный маршрут до приемника состоит из оптимальных путей от промежуточных узлов - не зависит от топологии и трафика виды локальная/полная информация о сети статическая/динамическая/адаптивная маршрутизация - учет текущей конфигурации сети(админстратор/рассылки) - сбор информации о сети (обучение) алгоритмы shortes path - кратчайший путь в графе - полный, без обновления (ПС) алгоритм Дейкстры - разметка кратчайшими путями от посылателя -- динамическое программирование, волновой алгоритм sink tree - размеченное дерево-путь до конкретного приемника -- пакет будет доставлен за конечное число пересылок directed acyclic graph(DAG) - несколько деревьев с одной длиной -- несколько корней flooding - передача на все интерфейсы, кроме входного - локальный, динамический (ЛА) - простота, надежность - широковещательная рассылка - экспоненциальная нагрузка сети - широковещательная рассылка запрет повторной пересылки счетчик пересылок(возраст, TimeToLive) - максимальное разрешенное число прохождения промежуточных узлов (кол-во пересылок) метка о пересылке этого пакета от источника - порядковый номер - старый/новый статические таблицы маршрутизации - известные кратчайшие пути (выходные интерфейсы) до узла - локальный, без обновления (ЛС) адрес узла(-ов) предпочитаемый выходной интерфейс предполагаемое расстояние по вектору расстояний (distance vector) - по таблице маршрутизации - локальный, обновляемый (ЛД) - 1957, алгоритм Беллмана-Форда, RIP -- быстрая реакция на хорошие, плохая плохие новости -- большая нагрузка на сеть distance vector - суммарное расстояние путей в маршруте обновление записей в таблице - периодический обмен таблицами между соседними узлами - известно расстояние до узлов M(self-X) если M(X->Y) < M(self->Y) + M(self->X) то замена новым минимальным маршрутом - count-to-infinity - бесконечное увеличение длины пути до выпавшего узла - не учет состава пути до узла -- прохождение через себя с учетом состояний линий (link state) - по построенному графу - полный, обновляемый(ПД) - учет состояния линий - 1979, IS-IS, OSPF обнаружить соседей запрос HELLO по всем интерфейсам, ответ имя соседа определить метрику расстояния до соседей время оборота пакета HELLO/ECHO заданная информация о типе линии обменяться информацией имя (идентификатор) отправителя список соседей и расстояний - периодически/по событию - flooding вычислить кратчайшие пути до остальных узлов построить граф сети - неполная, ошибочная информация найти кратчайшие пути обновить таблицу маршрутизации on-demand distance vector - волновая прокладка пути по требованию - 1999, Perkins, Royer (la) ROUTE REQUEST - поиск получателя flooding до получателя ROUTE REPLY - поиск пути до отправителя возврат по наикратчайшему пути - хранение информации об направлении получения запроса - хранение информации о направлении до получателя HELLO - запрос проверка соседей очистка таблицы маршрутизации уведомление соседей о нерабочем маршруте иерархическая таблица маршрутизации - уменьшение размера графа - размер таблицы пропорционален числу узлов (N) регион - сегмент сети обрабатываемый из вне как один узел - кластеры, зоны, группы - делегирование задачи маршуртизации узлу-маршрутизатору региона - оптимальное кол-во уровней - ln(N) e ln(N) - записей для каждого региона [транзит пакетов] - пересылки - маршрутизатор unicasting - одному узлу - послать в нужном направлении - метрика и маршруты default gateway - маршрут для неизвестных получателей broadcasting - всем одновременно - эффективнее с разделяемым соединением flooding(broadcast) - по всем направлениям - broadcast storm reverse path - только в прямом направлении - 1978, Dadal, Metcalfe дерево встречного продвижения - направление наилучшего маршрута пересылки - отброс дубликатов пришедших с других направлений spanning tree - в направлении других узлов дерева multicasting - заданной группе - членство узла в группах multidestination - по направлениям соответствующим указанным в списке/маске адресатов - нужен список всех узлов broadcast - если группа плотная multicast tree - усеченное связующее дерево до членов группы - 1990, Диринг, Черинтон - усечение полного дерева - рекурсивное сообщение отсечения (PRUNE) от транзитных узлов не ведущих к членам группы - необходимо хранить каждое построенное усеченное дерево core-based trees - построение общего дерева группы - 1993, Ballardie, для разреженных групп выбор корня дерева (точки встречи) построение дерева - посылка корню специального пакета - рассылка через любого узла дерева anycasting - одному из группы замена членов группы одним узлом -- стягивание в одну точку пересылка наикратчайшим путем mobile-casting - мобильному хосту(mobile host) - найти узел в сети - перепрокладка маршрутов неэффективна reverse home location - домашний (стационарный) адрес peering(triangle) - получение временного адреса хоста и передача напрямую home agent - транзитный узел, знающий адрес mobile host tunneling - передача через созданный канал rerouting - перенаправление пакетов adhoc-casting - в самоорганизующейся сети ad hoc - (лат. по месту) - в текущей ситуации - мобильны хосты и маршрутизаторы - топология не имеет значения dynamic source routing greedy perimeter stateless routing - на основе расположения узлов, в сторону получателя