ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Categories:

Бомбим подсеть

Вопрос из книги Таненбаума про компьютерные сети к главе 1 «Введение», цитата:

18. Подсеть на рис. 1.22, б проектировалась таким образом, чтобы выстоять во время ядерной войны. Сколько бомб потребуется, чтобы разбить сеть на две изолированные части, если одна бомба разрушает узел со всеми линиями, подходящими к нему.


Сначала разберем предысторию рисунка 1.22, б. На предыдущем рисунке 1.22, а в книге изображен пример организации телефонной сети:
Маленькими черными точками здесь изображены телефонные коммутационные станции, каждая из которых соединена с тысячами телефонов. Здесь речь идет не о мобильных телефонах, а о стационарных телефонах, которые работают через провода.

В свою очередь, эти телефонные коммутационные станции на рисунке соединены линиями со станциями более высокого уровня, обозначенными черными квадратиками, а те, в свою очередь, соединены со станцией еще более высокого уровня, обозначенной черным шестиугольником.

Очевидно, что если противник уничтожит (разбомбит, к примеру) одну из станций более высокого уровня, то сразу множество обычных телефонных коммутационных станций окажется отсоединенным от основной телефонной сети и абоненты этих станций окажутся без связи.

В 1960-х годах американский инженер и изобретатель Пол Бэран предлагал изменить вышеизложенную архитектуру телефонной сети с целью сделать ее более устойчивой к уничтожению отдельных ее звеньев следующим образом.

Во-первых, вообще убираем из сети все станции высоких уровней, а также провода, идущие к ним от рядовых телефонных коммутационных станций. Освободившиеся провода используем для соединения рядовых телефонных коммутационных станций между собой. Этот процесс проиллюстрирован ниже с помощью трех рисунков:

Крайний справа рисунок из этих трех и обозначен в книге как 1.22, б. Очевидно, что уничтожение противником любой одной из рядовых телефонных коммутационных станций при такой архитектуре телефонной сети не приведет к разделению этой телефонной сети на две изолированные части. Все «выжившие» рядовые телефонные коммутационные станции останутся связанными в обход уничтоженной станции.

В задании не сказано, сколько минимум может быть коммутационных станций в одной изолированной части. Предположим, мы хотим изолировать какую-то одну любую коммутационную станцию на рисунке 1.22, б. Я немного подумал над этим рисунком и понял следующее: чтобы изолировать любую коммутационную станцию на рисунке, нужно уничтожить все станции, от которых идут линии к целевой станции. А значит, для этого бомб нужно будет сбросить столько, сколько к целевой станции подходит линий.

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

Предположим, требуется изолировать от остальной сети любые две примыкающие друг к другу станции. Сколько для этого потребуется бомб? Как это вычислить? Очень просто. Объединяем эти две станции в одну, для этого можно перерисовать наш рисунок. А далее действуем так же, как и было описано выше: количество бомб для отделения одной станции мы уже умеем определять.

На рисунке ниже я привел два примера (А и Б) отделения от основной сети изолированной части из двух станций. В примере Б всё должно быть понятно: после объединения станций в одну станцию к ней подходят три линии, поэтому для изолирования этих двух станций от основной сети потребуется три бомбы. В примере А, однако, линий к нашей объединенной станции на первый взгляд подходит четыре, а бомбы требуется только три. Почему так? На самом деле, линии под номерами 2 и 3 после объединения наших двух станций тоже должны объединиться в одну, так как они выходят из одной станции и входят в одну (объединенную) станцию. Поэтому линий будет три и бомбы потребуется тоже три.
Изложенный метод можно распространить на отделение от основной сети изолированной части из трех, четырех и так далее станций.
Tags: Образование
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments