В студенческом городке развернуто 10 локальных вычислительных сетей (ЛВС). В каждой сети есть один маршрутизатор, его номер соответствует номеру сети. Линии связи между маршрутизаторами указаны на рисунке. Соединение с Интернет имеют только маршрутизаторы с номерами 1, 3 и 5.
В служебной части сетевых пакетов имеется счетчик S, который увеличивается на 1 при каждой пересылке между маршрутизаторами. Из Интернет пакеты попадают в сети со счетчиком S = 1.
При поступлении пакета в очередной маршрутизатор с номером R осуществляется анализ его адреса назначения. Если сетевой пакет не предназначен какому-либо узлу из сети маршрутизатора, то он отправляется одному из соседних маршрутизаторов по правилу:
если S / R < 2, то соседу с минимальным номером;
если S / R == 2, то соседу со средним значением номера;
если S / R > 2, то соседу с максимальным номером.
В какую сеть надо отправить пакет из Интернет, чтобы он дошел до сети с номером 10 за минимальное число шагов? Найдите это число шагов.
Рис. Схема соединения ЛВС
Так как в ответе на задачу необходимо указать количество шагов, то заметить какую-либо закономерность (или особенность) и решить задачу теоретически, получив точный ответ, не представляется возможным. Возможно два варианта поиска ответа: ручной и программный.
Для решения задачи вручную и получения обоснованного ответа необходимо проследить пути пакета до целевого (десятого) маршрутизатора для всех возможных входов в маршрутизаторы, подключенные к сети Интернет.
Вход в маршрутизатор №1:
S |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
R |
1 |
2 |
1 |
4 |
1 |
4 |
1 |
4 |
3 |
5 |
3 |
5 |
3 |
5 |
3 |
5 |
6 |
5 |
6 |
9 |
8 |
9 |
8 |
9 |
8 |
10 |
Вход в маршрутизатор №3:
S |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
R |
3 |
1 |
3 |
1 |
4 |
1 |
4 |
1 |
4 |
3 |
5 |
3 |
5 |
3 |
5 |
6 |
5 |
6 |
9 |
8 |
9 |
8 |
9 |
8 |
10 |
Вход в маршрутизатор №5:
S |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
R |
5 |
2 |
1 |
4 |
1 |
4 |
1 |
4 |
3 |
5 |
3 |
5 |
3 |
5 |
3 |
5 |
6 |
5 |
6 |
9 |
8 |
9 |
8 |
9 |
8 |
10 |
При вычислении пути пакета, отправленного в маршрутизатор №5, можно заметить, что, начиная с шага 2, этот путь будет совпадать с первым путем и сэкономить время на его вычислении.
Таким образом, получаем, что пакет надо отправить через маршрутизатор №3, и он дойдет до маршрутизатора №10 со значением счетчика S=25, то есть между маршрутизаторами будет сделано 24 шага.
Таким ответ будет, если результат операции деления S на R будем считать целочисленным. А, если решать задачу, считая, что результат операции деления вещественный, то значение счетчика S будет следующим: 19, 16 и 19 шагов соответственно. То есть ответом будет: отправить пакет через маршрутизатор №3, и он дойдет до маршрутизатора №10 за 16 шагов.
Эту задачу удобно решать программным способом, так как ее условие можно формализовать и разработать алгоритм решения. Маршрутизаторы и связи между ними можно программно представить либо в виде матрицы смежности, либо в виде массива «соседей». В матрице смежности размером 10 на 10 ноль в i-ой строке и j-ом столбце будет означать отсутствие связи между маршрутизатором i и маршрутизатором j, а единица – наличие связи. В каждой строке будет по три единицы, означающих наличие переходов в маршрутизаторы с наименьшим, средним и наибольшим номерами (рис. ). Вместо матрицы смежности можно создать двумерный массив размером 10 на 3, в каждой строке которого будут последовательно указаны номера маршрутизаторов с наименьшим, средним и наибольшим номерами, соединенных с маршрутизатором, соответствующим номеру этой строки. Далее необходимо реализовать алгоритм обхода графа, представленного одним из описанных выше способов, начиная с каждой из входных вершин и заканчивая в вершине номер 10, соответствующей маршрутизатору №10.
а) целочисленное деление: пакет надо отправить через маршрутизатор №3, и он дойдет до маршрутизатора №10 со значением счетчика S=25 (24 шага);
б) вещественное деление: пакет надо отправить через маршрутизатор №3, и он дойдет до маршрутизатора №10 за 16 шагов.