Задача оптимальной статической маршрутизации

Исходные данные:

• Топология из N ЦК и М КС

• Пропускные способности КС С={c1,c2,c3… cm}

• Информационные потоки (γjk[пакет/сек]), где j,k=1…N

• Средняя длина пакета l

В качестве целевой функции выбирается средняя задержка T. Рис36

Задача состоит в следующем: Для каждой пары j и k центров коммутации распределить поток γjk между множеством маршрутов, идущих из j в k так, чтобы минимизировать T.

При этом выполняются ограничения:

1. Потоки, удовлетворяющие этому ограничению, образуют выпуклые многоугольники, вершины которых обозначают потоки.

2. fi < ci. Поток в КС не должен превышать свою ПС. (если fi₀ >= ci₀, то T->∞ перегрузка!)

Решение сформулированной задачи основано на следующем утверждении: совокупность путевых потоков минимизируют Т только в том случае, если каждый маршрутный поток является кратчайшим в метрике длин каналов связи.

–скорость роста целевой функции при приращении КС. В итоге поток выбирает путь с минимальным приращением, а значит, функция T минимизирована.

Рис37. Локальный минимум будет являться глобальным.

Алгоритм решения задачи (алгоритм отклонения потоков)

Шаг 0:

рис38. Начальное распределение потоков (при инициализации сети) в метрике длин КС.

Шаг 1:

Необходимо определить все возможные

Шаг 2:

Решить задачу определения кратчайших маршрутов в метрике длин di, где i=1…M.

Рис38. Каждый поток γjk направить по этим маршрутам и определить результирующие потоки в КС. В результате получим:

Шаг 3-5:

Рис38.

Система адресации стека tcp/ip.

В стеках IPX/SPX адрес связан с внутренним адресом.

В TCP/IP используются разные адреса.

Используется 3 типа адресов:

1. Локальные адреса

2. Числовые адреса

3. Символьные адреса (имена) – используются пользователями в целях идентификации

Первые две группы устанавливаются программными и аппаратными средствами сети для идентификации узла.

Основной тип – числовые адреса. В науке его называют IP адрес. IP – 4 байта, разделенные между собой точками. Например: 141.35.27.80. Здесь 141.35 – адрес подсети, а 27.50 – адрес узла.

Локальные адреса

В стеке TCP/IP локальный адрес – это тот, который используется базовой технологией подсети для доставки данных в своих пределах (LAN). В локальных технологиях LAN – адрес сетевого адаптера – это и есть MAC–адрес.

Между локальным адресом и IP адресом нет никакой функциональной (алгоритмической) связи, но имеется взаимно-однозначное соответствие. По IP адресу можно определить МАС-адрес по протоколу ARP. Чтобы определить IP по локальному адресу, необходимо воспользоваться реверсивным ARP протоколом - RARP.

В ARP таблице (в маршрутизаторе) содержится соответствие IP и локальных адресов.

Рис39. ARP протокол формирует ARP запрос - ARP адрес, для которого формируется собственный IP адрес и его локальный адрес. Этот запрос отправляется в сеть и станция, которая узнает свой IP адрес формирует ARP ответ, в котором указывается искомый локальный адрес и в ARP таблице появляется запись соответствия IP-адрес – локальный адрес.

В это время IP пакет уничтожается (очень редко остается в буфере), и этот маршрутизатор отправляет сообщение по ICMP протоколу (internet control message protocol). И отправитель после отправки сообщения может заново посылать новый пакет.

В глобальных сетях предусмотрены ARP сервера, которые решают соответствие IP адреса локальному адресу.