7.4 Заливка

Метод заливки, называемый также лавинной маршрутизацией, представляет собой еще один статический алгоритм, при котором каждый приходящий пакет посылается во все исходящие линии, кроме той, по которой пришел пакет. Алгоритм заливки порождает огромное количество дублированных пакетов, даже бесконечное количество в сетях с замкнутыми контурами, если не принять специальных мер. Одна из таких мер состоит в помещении в заголовке пакета счетчика преодоленных им транзитных участков, уменьшаемого при прохождении каждого маршрутизатора. Когда значение этого счетчика падает до нуля, пакет удаляется. В идеальном случае счетчик транзитных участков должен вначале устанавливаться равным длине пути от отправителя до получателя. Если отправитель не знает расстояния до получателя, он может установить значение счетчика на длину максимального пути в данной подсети.

Альтернативный способ ограничения количества тиражируемых пакетов заключается в учете проходящих через маршрутизатор пакетов, чтобы не посылать их еще раз. Один из способов состоит в том, что каждый маршрутизатор кладет в каждый получаемый от своих хостов пакет порядковый номер. Каждый маршрутизатор ведет список маршрутизаторов – источников, в котором сохраняет все порядковые номера пакетов, которые ему встречались. Если пакет от данного источника с таким порядковым номером уже есть в списке, он удаляется.

На практике чаще применяется вариант данного алгоритма под названием «выборочная заливка». В данном алгоритме маршрутизаторы посылают пакеты не по всем линиям, а только по тем, которые идут приблизительно в нужном направлении. Недостаток этого алгоритма – непрактичность. Например, применение нашел в военных приложениях, где большая часть маршрутизаторов в любой момент может оказаться уничтоженной, высокая надежность алгоритма заливки является, наоборот, желательной. В распределенных базах данных иногда бывает необходимо одновременно обновить все базы данных, и в этом случае заливка оказывается полезной. Третье применение алгоритма заливки – эталонное тестирование других алгоритмов выбора маршрутов, т.к. заливка всегда находит все возможные пути в сети, а следовательно, и кратчайшие.

7.5 Маршрутизация на основании потока

Вышеперечисленные алгоритмы рассматривали только топологию, они не учитывали нагрузку. Если, например, поток данных от станции А к станции В всегда велик, тогда, возможно, лучше направить трафик от А к С по пути AGEFC, хотя этот маршрут значительно длиннее, чем АВС. Данный алгоритм является статическим, использует для определения оптимального маршрута как топологию, так и загрузку.

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

В основе этого алгоритма лежит идея: если для данной линии известны ее пропускная способность и среднее значение потока, то на основании теории массового обслуживания можно вычислить среднюю задержку для пакета. По средним значениям задержки для всех линий можно затем вычислить средневзвешенную задержку пакета для всей подсети. После этого задача маршрутизации сводится к созданию алгоритма выбора маршрута, который бы минимизировал среднюю задержку по всей сети.

Чтобы воспользоваться этим методом, необходимо знать заранее определенную информацию. Должна быть известна топология подсети, должна быть задана матрица трафика Fij, должна быть доступна матрица пропускной способности линий Сij. И наконец, должен быть выбран алгоритм выбора маршрутов.

В качестве примера этого метода рассмотрим дуплексную подсеть, показанную на на рисунке 72. На рисунке – подсеть с пропускной способностью, показанной в килобитах в секунду. Весовые коэффициенты дуг соответствуют пропускной способности линий Сij в каждом направлении в кбит/сек.

Матрица на рисунке 73 содержит маршруты для каждой пары узлов, а также количество пакетов в секунду, посылаемых от источника I к приемнику j. Например, от узла В к узлу D пересылаются три пакета в секунду по маршруту BFD. Обратим внимание, что некий алгоритм выбора маршрутов уже был применен для определения маршрутов, показанных в матрице.

Рисунок 72 - Подсеть с пропускной способностью линий в кбит/с

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

НАЗНАЧЕНИЕ
		A	B	C	D	E	F
ИСТОЧНИК	A		9 AB	4 ABC	1 ABFD	7 AE	4 AEF
	B	9 BA		8 BC	3 BFD	2 BFE	4 BF
	C	4 CBA	8 CB		3 CD	3 CE	2 CEF
	D	1 DFBA	3 DFB	3 DC		3 DCE	4 DF
	E	7 EA	2 EFB	3 EC	3 ECD		5 EF
	F	4 FEA	4 FB	2 FEC	4 FD	5 FE

Рисунок 73 - Трафик в пакетах в секунду и матрица маршрутов