Алгоритмы маршрутизации

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

Алгоритмы маршрутизации можно разделить на две категории:

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

Алгоритмы маршрутизации

Рис. 17.8. Алгоритмы маршрутизации

статическая маршрутизация, когда маршрут одинаков для всех пакетов, передаваемых к одному и тому же конечному пункту;

адаптивная маршрутизация, когда коммутатор при выборе принимает во внимание текущий трафик.

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

 
< Пред   СОДЕРЖАНИЕ     След >