Курсовые и лабораторные работы Математика решение задач Электротехника Лабораторные работы по электронике Физика Информатика На главную
Реализация сервиса виртуальные каналы Алгоритмы маршрутизации Метод заливки Маршрутизация Иерархическая маршрутизация Широковещательная маршрутизация Многоадресная рассылка Борьба с флуктуациями

Принцип оптимальности маршрута

Прежде чем перейти к рассмотрению отдельных алгоритмов, возможно, следует привести некие общие положения, описывающие оптимальные маршруты, вне зависимости от топологии или трафика. Такой основополагающей идеей является принцип оптимальности. В соответствии с этим принципом, если маршрутизатор В располагается на оптимальном маршруте от маршрутизатора А к маршрутизатору С, то оптимальный маршрут от маршрутизатора В к маршрутизатору С совпадет с частью первого маршрута. Чтобы убедиться в этом, обозначим часть маршрута от маршрутизатора А к маршрутизатору В как r1, а остальную часть маршрута — r2. Если бы существовал более оптимальный маршрут от маршрутизатора В к маршрутизатору С, чем r2, то его можно было объединить с r1, чтобы улучшить маршрут от маршрутизатора А к маршрутизатору С, что противоречит первоначальному утверждению о том, что маршрут r1r2 является оптимальным.

Прямым следствием принципа оптимальности является возможность рассмотрения множества оптимальных маршрутов от всех источников к приемникам в виде дерева. Такое дерево называется входным деревом. Оно изображено на рис. 5.5. Расстояния измеряются количеством транзитных участков. Обратите внимание на то, что входное дерево не обязательно является уникальным. У одной сети могут существовать несколько входных деревьев с одинаковыми длинами путей. Цель всех алгоритмов выбора маршрутов заключается в вычислении и использовании входных деревьев для всех маршрутизаторов. интернет магазин кофе доставкой


Рис. 5.5. Подсеть (а); входное дерево для маршрутизатора В (б)

Поскольку входное дерево действительно является деревом, оно не содержит петель, поэтому каждый пакет будет доставлен за конечное и ограниченное число пересылок. На практике все это не так просто. Линии связи и маршрутизаторы могут выходить из строя и снова появляться в сети во время выполнения операции, поэтому у разных маршрутизаторов могут оказаться различные представления о текущей топологии сети. Кроме того, мы обошли вопрос о том, собирает ли маршрутизатор информацию для вычисления входного дерева сам или эта информация каким-то другим образом поступает к нему. Мы вскоре рассмотрим этот вопрос. Тем не менее, принцип оптимальности и входное дерево — это те точки отсчета, относительно которых можно измерять эффективность различных алгоритмов маршрутизации.


Тройные интегралы в цилиндрических координатах
Сетевой уровень Управление доступом У каждого хоста и маршрутизатора в Интернете есть IP-адрес