2.3.3. Метод статической лавинной маршрутизации

Метод лавинной маршрутизации, представляет со­бой еще один статический алгоритм планирования различных (в том числе, оптимальных) маршрутов [3,17].

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

При этом узлам ТКС не требуется что-либо знать о состоянии сети. Поэтому метод лавинной маршрутизации не требует никаких вычислительных операций.

Данный метод приводит к избыточным сетевым нагрузкам, так как при пересылке пакета данных от узла-источника к узлу-получателю “лавинообразно” (подобно цепной реакции) порождается огромное количество дублированных (реплицированных) пакетов данных с замкнутыми контурами (линиями связи) такое дублирование может происходить до бесконечности или пока не наступит перегрузка сети.

Заметим, что в ТКС для снижения сетевых перегрузок каждому пакету данных можно задать ограничение либо на длину проходимого им маршрута (если пакет не достигает узла-получателя за определенное число шагов, то он уничтожается), либо каждый узел ретранслирует приходящие на него пакеты не более одного раза.

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

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

Достоинством метода является его вычислительная «дешевизна» и высокая надежность: доставка пакета производится даже в том случае, когда некоторые узлы ТКС вышли из строя. Благодаря этому данный метод применим в нестабильных сетях, а также при широковещательных запросах или сообщениях (поскольку пакет получают практически все узлы ТКС прямо или косвенно связанные с узлом-источником). Кроме того, алгоритм может применяться в качестве эталона для тестирования других алгоритмов маршрутизации, поскольку при лавинной маршрутизации будут задействованы все допустимые (в том числе оптимальные) маршруты от узла-источника к узлу-получателю.

Метод лавинной маршрутизации можно использовать для построения графа допустимых маршрутов G(s,f,w) узлов-источников для любых s и f. Затем по этому графу легко построить оптимальные маршруты, используя для этого, например, алгоритм Дейкстры.

2.3.4. Методы вероятностной маршрутизации

Случайная маршрутизация является вероятностной модификацией лавинной маршрутизации и позволяет существенно сократить накладные расходы сетевых ресурсов. При случайной маршрутизации на каждом узле, осуществляющем ретрансляцию пакетов данных для всех пар вида «узел, приславший пакет»-«узел-получатель» задается вектор распределения вероятностей P [3,17].

Значения компонентов вектора P соответствуют вероятностям пересылки пакета по тому или иному исходящему каналу связи ретранслирующего узла, его длина равна числу этих каналов. Вектор вероятностей обладает следующими свойствами:

1) если j-й элемент вектора P соответствует узлу, приславшему пакет, то P_j=0;

2), (2.3.2.)

где P_i – значение i-го элемента вектора;

Остальные значения вектора P можно рассчитывать разными способами. Например, можно использовать формулу

, (2.3.3.)

где P_i – вероятность выбора канала i; R_i – скорость передачи данных по каналу i.

Алгоритмы случайной маршрутизации могут найти применение в задачах динамической и адаптивной маршрутизации, при неполной информации о текущем состоянии динамики ТКС. Маршруты, прокладываемые с помощью таких стохастических (рандомизированных) алгоритмов, хотя и не всегда будут оптимальными, но могут значительно снизить сетевые нагрузки на ТКС.