Неформальное объяснение

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

42 Поняття автономної системи. Протокол маршрутизації BGP. Особливості використання.

Автономная система (AS) в интернете — это система IP-сетей и маршрутизаторов, управляемых одним или несколькими операторами, имеющими единую политику маршрутизации с Интернетом. См. RFC 1930 для дополнительной информации по данному определению.

Поначалу определение требовало единого оператора, обычно Интернет-провайдера или очень большую организацию с независимыми соединениями с несколькими сетями, который бы придерживался единой и ясно определенной политики маршрутизации. См. RFC 1771, оригинальное определение (сейчас устаревшее) Border Gateway Protocol.

Новое определение из RFC 1930 вошло в употребление, так как несколько организаций могло подключиться к Интернет-провайдеру через BGP, используя приватные номера AS, а провайдер, в свою очередь, подключал все эти организации к Интернету. Хотя существуют несколько автономных систем, поддерживаемых данным Интернет-провайдером, в Интернете видно только политику маршрутизации данного провайдера. Именно этот Интернет-провайдер и должен иметь зарегистрированный публичный номер AS.

Уникальный номер AS (или ASN) присваивается каждой AS для использования в BGP маршрутизации. На середину 2011 года в глобальной таблице маршрутизации представлено более 37 тысяч автономных систем.