Сети передачи данных

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

В основе лавинной маршрутизации лежит эффект размножения пакетов, при котором узел, получив пакет, генерирует дополнительные, идентичные с ним пакеты и передает их во всех направлениях, кроме того по которому поступил пакет (рис. 6.8). Таким образом копии пакета лавинообразно распространяются по сети. Достоинством метода является то, что он обеспечивает минимальную задержку распространения пакетов, поскольку используются все пути через сеть, в том числе и кратчайший, по которому и придет первый пакет. Для рас­сматриваемого случая это путь через вершины: А1 (A3 (А5 (А9. В то же время, при боль­шом числе связей между узлами сильно проявляется эффект размножения пакетов, напри­мер, в момент времени t3 в рассматриваемом фрагменте сети будет присутствовать 9 копий пакета, что сказывается на пропускной способности сети. Влияние эффекта размножения па­кетов можно уменьшить за счет добавления определенных средств учета прохождения паке­тов через узлы коммутации. Например, каждый узел может распознавать повторное попада­ние в него копии полученного ранее пакета и удалять ее. Таким образом, копии пакетов по­степенно исчезают из сети. Для рассматриваемого примера в момент времени t4 остается только две копии пакетов, которые в свою очередь уничтожаются на входе девятого узла. Этот процесс называется вырождением пакетов и позволяет существенно повысить пропуск­ную способность сети передачи данных.

X/ /Г'

7 /

/х _t

4 // /Дз /

X

 

(^A3j

\*

 

 

ух	X
/	^//
t3w	/" ~~"\/
, ^	( А«\

'. Рис.6.8 Лавинообразная маршрутизация, где: tj ^ — направление передачи пакета

X — уничтожение пакета на входе узла коммутаци:

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

Глава 2. Аббёойёооба ёинфоадшб пйдйё 101

пройденных узлов, на основании содержимого которого формируется адрес следующего уз­ла на пути следования пакета к получателю. Таким образом, на начальном этапе маршрути­зации путь следования пакетов может определяться случайным образом или способом лавин­ного заполнения пакетов, а затем, по мере прохождения следующих пакетов путь их следова­ния корректируется. После прохождения первого пакета по какому то маршруту в каждом узле коммутации сохраняется информация об адресе отправителя, получателя, предыдущего узла и числе пройденных узлов. При поступлении пакета с теми же значениями адресов от­правителя и получателя, но с меньшим значением счетчика пройденных узлов, осуществля­ется корректировка маршрута в узлах коммутации. Допустим, что для участка сети (рис. 6.9) первоначально был сформирован путь (ао (А1 (А2 (A3 (А4 (Ак), которому соответству­ют следующие значения маршрутов в узлах: А2 = {Ак, ао, А1, A3, 2}; A3 = {Ак, ао, А2, А4, 3 } и А4= {Ак, ао, A3, А5, 4 }, где на первом месте стоит адрес получателя, на втором — ад­рес отправителя, на третьем — адрес предыдущего узла, на четвертом — последующего узла и на пятом — число предшествующих узлов. В случае появления в узле А4 пакета, пришед­шего из узла А2 со значением счетчика пройденных узлов равного трем, осуществляется корректировка маршрута в узлах А2 и А4 на значения: А2 = {Ак, ао, А1, А4, 2} и А4= {Ак, ао, А2, А5, 3 }. В результате чего формируется новый, более короткий путь: (ао (А1 (А2 (А4 (Ак), в соответствии с которым пакеты, движущиеся в направлении Ак, из узла А2 будут сразу направляться в узел А4. Таким образом, можно говорить об элементах адаптации, од­нако, этот процесс протекает медленно и не всегда достаточно эффективен.

^L4J Л^Ак

Коррекция маршрута

Рис. 6.9. Маршрутизация по предыдущему опыту,

где:--------------------- > — первоначальный маршрут,

> — маршрут после коррекции.

Табличные методы маршрутизации, в зависимости от момента формирования таблиц маршрутов, подразделяют на статические и динамические. При статической маршрутизации таблицы маршрутов формируются при генерации сети и в последующем, как правило, не из­меняются. И только при изменении конфигурации сети, например, при выходе некоторого узла из строя, осуществляется корректировка соответствующих маршрутов.

К статическим способам маршрутизации относятся фиксированная и маршрутизация способом кратчайшей очереди. При фиксированной маршрутизации для любой пары або­нентских систем устанавливаются одиночный или групповой каналы передачи данных. В первом случае говорят об одно-путевой маршрутизации, так как существует только один маршрут следования пакетов от отправителя к получателю. Это наиболее простой способ маршрутизации, однако он не учитывает возможные аварийные ситуации и реальную загруз­ку отдельных каналов, что может привести к перегрузке отдельных участков сети при общей недозагрузке ее в целом. С целью выравнивания нагрузки на основных (магистральных) ка­налах передачи данных используют много путевую маршрутизацию, при которой между смежными узлами коммутации создается группа виртуальных каналов, каждый из которых может назначаться тому или иному пути следования пакетов. Данный подход используется в сети SNA фирмы IBM и рассматривается ниже.