В компьютерных сетях теоретически могут использоваться самые разнообразные методы (алгоритмы) маршрутизации, обеспечивающие разные эффекты и зависящие от структурно-функциональных особенностей сети и требований, предъявляемых к качеству функционирования сети. На рис. 1.39 представлена одна из возможных классификаций различных методов маршрутизации, которые можно разбить на 3 группы:
• простые;
• фиксированные;
• адаптивные.
К простым относятся следующие методы маршрутизации.
1. Случайная маршрутизация,при которой выбор направления передачи данных осуществляется случайным образом между всеми каналами узла (портами маршрутизатора) за исключением канала, по которому эти данные поступили в узел. Например, если маршрутизатор имеет 4 порта (канала) и по одному из них поступили данные, то вероятность передачи по любому из трёх других каналов будет равна 1/3, при этом адрес назначения не используется для выбора выходного канала. Очевидно, что применение такого алгоритма маршрутизации оправдано только в том случае, если отсутствует информация о топологии сети и сетевых адресах, что делает невозможным построение таблицы маршрутизации. Несмотря на то, что направление передачи пакетов осуществляется случайным образом, вероятность доставки пакета конечному адресату отлична от нуля, но меньше единицы, поскольку существует вероятность зацикливания пакета в сети.
2. Лавинообразная маршрутизация,заключающаяся в размножении поступившего пакета и рассылке его копии по всем направлениям, кроме того, по которому поступил пакет. Такое размножение приводит к большой загрузке каналов и узлов сети и, в то же время, обеспечивает доставку пакета конечному адресату с вероятностью единица. Если в некоторый узел поступает несколько копий одного и того же пакета, то все они, кроме одного пакета, уничтожаются. Как и в предыдущем случае, применение лавинообразного алгоритма оправдано, если невозможно построить таблицу маршрутизации из-за отсутствия информации о топологии сети и сетевых адресах.
Случайная и, особенно, лавинообразная маршрутизации являются скорее экзотическими методами, которые могут использоваться в условиях неопределённости, возникших, например, в результате боевых действий, приведших к выходу из строя значительной части сетевых ресурсов и, как следствие, к отсутствию сведений о топологии сети и сетевых адресах.
3. Маршрутизация по предыдущему опытуявляется наиболее интересной среди простых алгоритмов и заключается в автоматическом построении таблицы маршрутизации.
Заголовки пакетов, передаваемых в сети с маршрутизацией от источника, кроме адреса получателя АП и адреса отправителя АО содержат специальное поле «расстояние», значение которого в узле-отправителе устанавливается равным 0. В процессе передачи пакета в сети в каждом промежуточном узле значение поля «расстояние» увеличивается на единицу. Таким образом, в каждом узле значение этого поля показывает расстояние, которое прошел пакет от узла-отправителя до этого узла и которое измеряется в количестве промежуточных узлов на пути передачи пакета.
Рассмотрим принцип реализации метода маршрутизации по предыдущему опыту на примере построения таблицы маршрутизации узла У7 сети, показанной на рис. 1.40.
Положим, что в некоторый момент времени в узел У7 поступает пакет от узла У1(адрес отправителя АО = У1) по маршруту, пролегающему через узлы У3, У5, У9 в каждом из которых значение поля «расстояние» было увеличено на 1:
В узле У7 анализируется адрес отправителя АО и, если такой адрес отсутствует в таблице маршрутизации, то он заносится в таблицу. Для этого же адреса одновременно указывается адрес соседнего узла У9, от которого поступил этот пакет, и расстояние до узла-отправителя, содержащееся в поле «расстояние»заголовка пакета и равное 3 (рис. 1.41).
Положим теперь, что через некоторое время в узел У7 поступит новый пакет от узла У1 с адресом отправителя АО=У1 маршрут которого пролегал через узлы У2, У6:
Поскольку в таблице маршрутизации узла У7 уже есть строка с адресом У1, то для этого адреса сравнивается значение расстояния от узла отправителя, содержащееся в заголовке поступившего пакета в поле «расстояние», со значением расстояния, записанного в таблице маршрутизации. Если расстояние, указанное в заголовке поступившего пакета, меньше расстояния, записанного в таблице маршрутизации, то новый маршрут считается более коротким и в таблице маршрутизации корректируется строка, соответствующая адресу назначения У1 адрес соседнего узла заменяется на У6, а расстояние до адреса назначения становится равным 2 (рис.1.42).
И наконец, если через некоторое время в узел У7 поступит пакет от узла Уь маршрут которого пролегал через узел У4: , то поле «расстояние» в заголовке пакета будет иметь значение, равное 1, что меньше значения в таблице маршрутизации. Тогда после корректировки таблицы маршрутизации, соответствующая строка примет вид, показанный на рис. 1.43.
Таким образом, анализируя всякий раз адрес отправителя и расстояние от узла-отправителя всех проходящих через узел пакетов и корректируя таблицу маршрутизации, после некоторого времени получим в таблице маршрутизации наилучший маршрут, по которому будут передаваться пакеты с соответствующим адресом назначения. В нашем примере поступающие в узел У7 пакеты с адресом назначения с АН=У1 будут направляться в узел У4.
