Ненавязчивый сервис

Алгоритм Дейкстры

Нахождение расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Дано: ориентированный граф <V,E> с выделенным источником s € V, матрица весов дуг A[u,v], u,v € V (все веса неотрицательны). Результат: расстояние от источника до всех вершин графа D[v]=d(s,v), v € V.

begin

for v € V do D[v]:=A[s,v];

D[s]:=0;

T:=V \ {s};

while T<> Ø do begin

u:=произвольная вершина r € T, такая что D[r]=min{D[p]:p € T};

T:=T \ {u};

for v € T do D[v]:=min(D[v], D[u]+A[u,v]}

end

end

Наиболее популярные протоколы состояния канала - это IS-IS и OSPF. Протокол IS-IS изначально создавался для сетей OSI, но впоследствии был адаптирован и к другим протоколам сетевого уровня, в частности к IP. Например, сеть NSFNet широко использует IS-IS в своей работе. К основным достоинствам IS-IS принято относить его "врожденную" способность взаимодействовать с самыми различными протоколами сетевого уровня, что делает его особенно полезным в крупных многопротокольных сетях. В сетях TCP/IP, все же, более популярен протокол OSPF. Протоколы IS-IS и OSPF имеют очень много общего (OSPF, по сути, является улучшенной версией IS-IS). Все сказанное ранее о протоколах состояния канала в равной степени справедливо и для IS-IS, и для OSPF.

Протоколом OSPF предусмотрена полезная возможность вычисления отдельного набора маршрутов для каждого значения поля "тип сервиса" (Type-Of-Service, TOS) в заголовке протокола IP. До создания OSPF ни один протокол не использовал значение этого поля.

Поле "тип сервиса" позволяет запрашивать для трафика определенный уровень сервиса. Длина поля - четыре бита, из которых значимым может быть только один. Таким образом, мы имеем всего четыре возможных варианта: минимальная задержка, максимальная пропускная способность, максимальная надежность, минимальная стоимость (в смысле оплаты). Каждое приложение по-разному устанавливает значение поля TOS. Значения битов данного поля для некоторых приложений приведены ниже (см. Таблица 1).

Таблица 1. Значения поля TOS для различных приложений

Как видно из таблицы, протоколам FTP и SMTP требуется передавать команды с минимальной задержкой, а для передачи данных им необходима большая пропускная способность. Если запрос DNS передается по протоколу UDP, то, очевидно, что программа-resolver, пославшая этот запрос, желает получить ответ как можно скорее, так как дейтаграммы UDP не требуют посылки подтверждений. Настроив протокол OSPF для определения маршрутов либо с минимальной задержкой, либо с максимальной пропускной способностью, в зависимости от TOS, мы можем еще больше ускорить работу DNS, так же как FTP и SMTP.

Однако не стоит забывать, что протоколы состояния канала очень требовательны к памяти. Злоупотребление богатыми возможностями OSPF быстро приведет к переполнению памяти маршрутизатора и сбоям при вычислениях маршрутов. В итоге весь трафик окажется в состоянии хаоса, и никакого заявленного типа сервиса он не получит.