Алгоритмы выбора маршрута [ 4 ]

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

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

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

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

Рис. 7.4. [ 4 ] Тупиковая ситуация в сети с коммутацией каналов

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

Популярным алгоритмом маршрутизации, который применяется для прямо­угольных решеток с любым числом измерений и в котором никогда не возникает тупиковых ситуаций, является пространственная маршрутизация. В соответствии с этим алгоритмом пакет сначала перемещается вдоль оси х до нужной координа­ты, а затем вдоль оси у до нужной координаты и т. д. (в зависимости от количества измерений). Например, чтобы перейти из (3, 7,5) в (6,9,8), пакет сначала должен переместиться из точки х=3 в точку х=6 через (4, 7, 5), (5,7,5) и (6,7, 5). Затем он должен переместиться по оси у через (6,8, 5) и (6,9, 5). Наконец, он должен пере­меститься по оси z в (6, 9, 6), (6, 9, 7) и (6, 9, 8). Такой алгоритм предотвращает тупиковые ситуации.