Архив задач

Маршрутизация

В студенческом городке развернуто 10 локальных вычислительных сетей (ЛВС). В каждой сети есть один маршрутизатор, его номер соответствует номеру сети. Линии связи между маршрутизаторами указаны на рисунке. Соединение с Интернет имеют только маршрутизаторы с номерами 1, 3 и 5.

В служебной части сетевых пакетов имеется счетчик S, который увеличивается на 1 при каждой пересылке между маршрутизаторами. Из Интернет пакеты попадают в сети со счетчиком S = 1.

При поступлении пакета в очередной маршрутизатор с номером R осуществляется анализ его адреса назначения. Если сетевой пакет не предназначен какому-либо узлу из сети маршрутизатора, то он отправляется одному из соседних маршрутизаторов по правилу:

  • если S / R < 2, то соседу с минимальным номером;

  • если S / R == 2, то соседу со средним значением номера;

  • если S / R > 2, то соседу с максимальным номером.

В какую сеть надо отправить пакет из Интернет, чтобы он дошел до сети с номером 10 за минимальное число шагов? Найдите это число шагов.

Рис. Схема соединения ЛВС