<<
>>

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

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

Прямым следствием принципа оптимальности является возможность рассмотрения множества оптимальных маршрутов от всех источников к приемникам в виде дерева.

Такое дерево называется входным деревом. Оно изображено

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

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

<< | >>
Источник: Э. ТАНЕНБАУМ. КОМПЬЮТЕРНЫЕ СЕТИ 4-Е ИЗДАНИЕ. 2003

Еще по теме Принцип оптимальности маршрута:

  1. ПРИНЦИП КЛЮЧА — ПРИНЦИП ОПТИМАЛЬНОСТИ.
  2. ПРИНЦИП КЛЮЧА — ПРИНЦИП ОПТИМАЛЬНОСТИ.
  3. Оптимальные условия
  4. АКТИВАЦИЯ: УРОВЕНЬ ОПТИМАЛЬНЫЙ
  5. ПОРОГ РАЗЛИЧЕНИЯ ОПТИМАЛЬНОГО
  6. 6.2.4. Поиск оптимальной финансовой модели СМИ
  7. 1.1.4. Оптимальная модель социальной сферы современного общества
  8. 2.3. Принципі оптимального поєднання централізованого і локального правового регулювання
  9. Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.
  10. Ключ помогает находить в себе то оптимальное состояние, которое вам нужно.
  11. 4.2. ПРИНЦИПЫ ОБУЧЕНИЯ Принципы как категория дидактики