Ломтик паркетный

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

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

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

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

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

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

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

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

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

Задачка 1,
для программистов и не только для них

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

Задачка 2,
административно-распределительная

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

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

Задачка 3,
результат которой удивляет даже профессионалов

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

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

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

Загадки

А Вывеска на учреждении гласит: "Абсолютно смертельно! Кроме русских".

Б ГАИшник останавливает легковушку, в которой набилось гораздо больше пассажиров, чем положено. Водитель берет права, выходит из машины и понуро плетется к милиционеру. Через некоторое время в приподнятом настроении возвращается к машине, открывает багажник, показывает гаишнику содержимое, забирает свои права в целости и сохранности и уезжает.

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

Г Человек ночью встал с кровати, пошел в туалет, отодрал от унитаза деревянный стульчак, положил его рядом с собой на кровать и лег обратно.

Д Посольство СССР в Великобритании прислало в МИД такое сообщение: "Королева Виктория зачислена в штат посольства в должности стенографистки с окладом в размере... Просим внести соответствующие изменения в штатное расписание".

Е В фашистский штаб во время важного заседания вламывается красноармеец, громко извиняется на "русском устном" и беспрепятственно убегает.

Ж Офис фирмы. Разгар рабочего дня. Вдруг в коридоре проламывается потолок, и сверху падает огромный бультерьер с проводом в зубах.

З Человек пробегает мимо продуктовой палатки, на бегу кидает продавцу деньги и с криком "Гриша, стой, прибью, гад!" бежит дальше.

И "Я не пустое место, я декан мехмата", - говорит человек и уезжает.

Й Человек проехал на велосипеде лишних 150 километров, а в результате стал верующим.

Разгадки

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

Б ГАИшник пересчитал людей в машине и сказал: "У тебя сидит девять человек, а это не рекорд. Вот если бы было десять, я бы тебя отпустил..." В ответ водитель подвел его к багажнику и показал лежащего там десятого человека.

В Милиционер с женой ездили на Украину к родителям жены. Захватили с собой кучу покупок, сувениров и подарков, а денег почти не осталось. В общем, когда на границе украинский таможенник потребовал от них заплатить пошлину, милиционер не долго думая стукнул таможенника по голове чем-то тяжелым и засунул в рундук. Поезд тронулся, а остальные таможенники так и не обнаружили пропажу коллеги. Через некоторое время пострадавший оклемался, но вылезать из рундука категорически отказался. Так и доехал до Москвы...

Г Наш человек! До этого он, мертвецки пьяный, несколько раз вставал с кровати и ходил в туалет, извините, блевать. А потом, видимо, решил, что если положить деревянный круг рядом, то и ходить никуда не понадобится...

Д На недоуменный встречный вопрос сотрудника МИД (типа "пить надо меньше") чрезвычайный и полномочный посол СССР в Великобритании прислал ответ: "Виктория Петровна Корол§ва зачислена на должность стенографистки. Кому из нас надо меньше пить?"

Е Дело было в театре во время спектакля. Красноармеец - актер массовки - отвлекся и выбежал на сцену раньше, чем это требовалось по сюжету.

Ж В офисе нужно было проложить сетевые кабели. Чтобы не лезть самим на фальшпотолок, ребята закинули туда дрессированного пса, который с проводом в зубах честно прополз по потолку длинного коридора почти до середины. Прополз бы и дальше, но потолок не выдержал веса собаки.

З А это еще одна история про бультерьера: Гришей зовут пса, за которым гонится его хозяин. Перед этим песик подбежал к палатке, торгующей молочными продуктами, положил передние лапы на прилавок, под вопли продавца "бери все, что хошь, только меня не трожь!" подкрепился творожным сырком и побежал дальше.

И Возможно, эта данетка не столь романтична, но больно уж фраза хороша...

Дело было так. Высотное здание МГУ на Воробьевых горах. Утром студенты набиваются в лифт так, что ни вдохнуть, ни выдохнуть. А снаружи народ все наседает: "пройдите в угол, там пустое место". И вот тут-то из угла невысокий человек и произносит ту самую фразу, после чего двери лифта наконец закрываются.

Й Увы, еще одна история о вреде пьянства и алкоголизма. Этот горе-велосипедист сильно набрался в гостях, а потому, не доехав по трассе до своего села, свалился в кювет и заснул. Через некоторое время мимо проезжали двое водителей на грузовике. Дело было зимой, они остановились и решили, что не стоит оставлять человека мерзнуть прямо на дороге. По документам пьяницы они поняли, что его надо отвезти еще километров десять по шоссе, поэтому погрузили мужика в багажник вместе с его велосипедом и поехали дальше. Отвлеклись, заболтались - в результате вспомнили про попутчика только через два часа. Ну не возвращаться же обратно! Вытащили мужика, положили в кювет, уехали. Теперь представьте себя на месте мужика: ехал-ехал на велосипеде, потом провал в памяти, очнулся в почти незнакомой местности, на 150 километров дальше родного села... Тут не только в бога поверишь - еще и тарелочки с инопланетянами почудятся...

Ломтик паркетный

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

Данетки из жизни