Топология слухов, или Почему пакеты ходят через ванкувер

Признаюсь, меня уже очень давно занимает один простой (до примитивности) вопрос: почему в одно и то же время связь с сайтом X бывает превосходной, а с сайтом Y - плохой. В другое время все наоборот, Y попадает в «зону уверенного приема», а X из нее вылетает. А с тех пор, как Internet Explorer повадился при небольшой скорости качания обрывать связь и сообщать «сервер недоступен», я разозлился не на шутку и возжелал докопаться до истины. Кое-что удалось узнать все в том же Интернете, до чего-то пришлось додумываться самому; некоторые детали картинки так и остаются неподтвержденными предположениями.

Начну издалека - из очень далекого далека. В математике давно известна задача о скорости распространения слухов: N друзей одновременно узнали N новостей, причем каждый узнал одну новость. Они стали звонить друг другу и обмениваться новостями. Каждый разговор длится один час. За один разговор можно передать сколько угодно новостей. Какое минимальное «время X» необходимо, чтобы все узнали все новости?

Ответ в этой задаче весьма сильно зависит от четности N и от ближайшей к N сверху степени двойки. Например, имеет смысл рассмотреть отдельно случаи N=16, N=25 и N=100.

Эта задача имеет весьма важное общее свойство с моим вопросом о скорости связи в Интернете. На всякий случай объясню подробнее: передача информации через Интернет происходит не непрерывно, а дискретно - отдельными пакетами. Более того, каждый пакет идет от отправителя до получателя кратчайшим путем. Протокол связи устроен так, что, если получатель уже имеет некий пакет, он повторно его больше не получит. Но в целом разные пакеты могут идти разными путями - и только в конце, у адресата, складываться, как puzzle-мозаики, в то самое целое, которое нужно получить. Если при этом какая-то часть мозаики по каким-либо причинам не дошла, ее немного ждут, а потом протокол «заказывает» ее заново: время ожидания загрузки. Добавим, что одновременно по Сети гуляют миллионы пользователей. Не правда ли, просматривается некая аналогия с задачей о слухах?

Аналогия будет еще полнее, если мы вспомним о топологии Сети, то есть о том, что реально вовсе не каждые два компьютера являются «друзьями» и могут связываться друг с другом, чтобы обменяться информацией. Сообразив это, будем учитывать, какие именно пары компьютеров могут связаться друг с дружкой, а какие - нет. Интернет устроен очень сложно, но топологию небольших сетей (или подсетей) можно проиллюстрировать рисунками 1-4.

Наиболее распространена «звезда» (рис. 4). Соответственно, компьютеры связываются друг с другом только через центральный сервер.

Усложненным вариантом этой топологии является рисунок, который я назвал «расческой» (рис. 3).

Одна из простых схем - кольцо (рис. 2). Все компьютеры равноправны, зато по пути от одной машины к другой нужно пройти через большое число «посредников».

И, наконец, самая симпатичная и «регулярная» (по внешнему виду) схемка - «решетка» (рис. 1). В реальности такая схема почти не встречаются, но для задачек, разминающих мозги, она пригодится как нельзя лучше.

Прикиньте на глазок, какая из четырех схем дает самую высокую скорость распространения слухов. А теперь строго решите задачу о скорости распространения слухов для каждой из четырех описанных выше топологий. (Я очень надеюсь, что вы не будете решать эту задачку вручную, а воспользуетесь компьютером и запрограммируете решение. Честное слово, это совсем не сложно… А главное - позволяет освободить мозги для более творческой работы.)

Предположим, что вы - администратор создаваемой сети из 16 компьютеров. Вам выделены деньги на 15 попарных соединений (иначе говоря, приходится делать не решетку и даже не кольцо, а что-то типа «расчески», - говоря более строгим языком, строить дерево). Как именно должна быть устроена схема соединений, чтобы итоговое «время X» было наименьшим из возможных?

А теперь - на закуску - самое интересное блюдо в этом меню.

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

Итак, предположим, что четыре «центральных» компьютера на рис. 1 работают не все время, а только каждый четный такт. Остальное время они отдыхают (помните бородатый анекдот: чукча будет по четным академиком, а по нечетным, однако, рыбу будет ловить). Но все остальные компьютеры об этом «не подозревают» и действуют при передаче и приеме информации (решая задачку 1) так, как если бы эти 4 компьютера работали постоянно. На сколько при этом увеличится «время X» для всей сети? Точнее, во сколько раз оно увеличится?

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

[i37143]