Алгоритмы для жизни. Простые способы принимать верные решения - Том Гриффитс

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

Коммутация пакетов – кардинально иная история. Телефонная система переполняется, почтовая система начинает тормозить. К сожалению, не существует специальных возможностей или сигналов, чтобы сообщить отправителю, сколько еще отправителей посылают информацию в данный момент или насколько загружена система в определенный момент, при этом уровень загрузки постоянно меняется. Таким образом, отправитель и получатель должны не просто коммуницировать, а метакоммуницировать: им необходимо понять, как быстро информация должна быть отправлена. Так или иначе, смешанные потоки пакетов, находящиеся вне явного управления или координации, должны освободить друг другу путь и быстро воспользоваться любым освободившимся пространством.

Результатом детективного расследования Джейкобсона и Карелса стал набор обновленных алгоритмов контроля потоков и предотвращения перегрузок – одна из самых глобальных модификаций в протоколе TCP за 40 лет.

В основе контроля перегрузок протокола TCP лежит алгоритм аддитивного увеличения, мультипликативного уменьшения (АУМУ). Прежде чем АУМУ вступает в игру, новое соединение будет агрессивно наращивать свою скорость передачи данных: если первый пакет успешно получен, оно направит еще два, если и они успешно получены, то соединение вышлет еще четыре и т. д. Но как только подтверждение приема не возвращается к отправителю, АУМУ начинает действовать. Согласно этому алгоритму любой полностью полученный набор пакетов приводит не к удвоению передаваемых пакетов, а к сокращению их числа на один, а недоставленные пакеты сокращают скорость передачи вполовину (отсюда и название алгоритма). В сущности, действие алгоритма похоже на указания «еще немного, еще немного, еще немного, о-о-о, слишком много, немного меньше, о'кей, немного больше, еще немного больше…». Таким образом, это приводит к форме частотного диапазона, известного как пилообразный TCP (равномерные подъемы вверх, прерываемые резкими падениями).

Так почему происходит такой четкий асимметричный спад? Как объясняли Джейкобсон и Карелс, в первый раз АУМУ вступает в игру, как только соединение теряет первый пакет в своей агрессивно нарастающей фазе. Поскольку эта первоначальная фаза привела к двукратному увеличению скорости передачи с каждым успешно переданным пакетом, решение урезать скорость вдвое, как только появляется проблема, выглядит вполне логичным. И если соединение вновь начинает давать сбой после того, как заработает, это происходит, скорее всего, потому, что какое-то новое соединение сражается за сеть. Наиболее консервативная оценка данной ситуации (буквально предположим, что вы единственный человек, использующий сеть, и теперь второй человек забирает половину ваших ресурсов) также приводит к урезанию наполовину. Консерватизм здесь необходим: сеть может стабилизироваться, только если ее пользователи перестанут с ней работать на скорости, равной скорости передачи данных, когда сеть перегружается. По той же причине исключительно аддитивное увеличение помогает стабилизировать сеть для всех, предупреждая возникновение быстрых циклов «перегрузка – восстановление».

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

Например, в рамках довольно неожиданного сотрудничества в 2012 году эколог Стэнфордского университета Дебора Гордон и программист Балажи Прабхакар выяснили, что муравьи разработали свои алгоритмы контроля потока за миллионы лет до людей. Подобно компьютерной сети, колония муравьев сталкивается с проблемой распределения, пытаясь организовать свой «поток» (в данном случае поток муравьев, направляющихся на поиски пищи) в различных условиях, способных резко повлиять на скорость, с которой муравьи могут успешно вернуться с поисков. И, подобно компьютерам в интернете, муравьи должны решить эту общую проблему без лидера вместо того, чтобы развивать, как обозначила Гордон, «контроль без иерархии». Оказывается, что и решение у муравьев похожее: цикл с обратной связью, в котором успешные добытчики должны быстрее покинуть муравейник, а менее успешным возвращающимся приходится сокращать их поисковую активность.

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

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

Шуточный принцип Питера, озвученный в 1960-е годы профессором Лоуренсом Питером, утверждает, что «каждый сотрудник склонен подняться до своего уровня некомпетентности». Идея заключается в том, что при иерархической организации любой, выполняющий свою работу эффективно, будет награжден повышением на новую должность, что может повлечь за собой более сложные и/или новые задачи и вызовы. Когда работник наконец получает ту роль, в которой он не показывает высоких результатов, его движение по карьерной лестнице останавливается, и он остается в этой должности до конца своей карьеры. Таким образом, согласно принципу Питера получается, что каждое место в организации в конце концов будет занято кем-то, кто плохо справляется со своей работой. Примерно за 50 лет до появления формулировки Питера, в 1910 году, испанский философ Хосе Ортега-и-Гассет высказал такую же мысль. «Каждый чиновник должен быть незамедлительно понижен в должности, – писал он, – поскольку они получали повышение до тех пор, пока не стали некомпетентными».

Некоторые организации попытались использовать принцип Питера, просто увольняя сотрудников, которые не демонстрировали прогресса. Так называемая система Крэвет, изобретенная ведущей юридической фирмой Cravath, Swaine & Moore, подразумевает почти исключительный наем недавних выпускников на самые низкие должности, за которым следует либо повышение, либо увольнение. В 1980 году Вооруженные силы США начали использовать похожий принцип «вверх или за дверь» с принятием Закона о прохождении службы офицерским составом ВС. В Соединенном Королевстве подобным образом применялась политика контроля комплектования.

Есть ли какая-то альтернатива, какая-либо золотая середина между институциональной стагнацией принципа Питера и драконовскими мерами политики «вверх или за дверь»? Алгоритм АУМУ может предложить именно такой подход, поскольку он предназначен именно для работы в условиях переменчивой окружающей среды и обстоятельств. Компьютерная сеть должна справляться со своей максимальной пропускной способностью, плюс скоростью передачи данных своих клиентов, каждая из которых может быть непредсказуемо неустойчивой. Аналогичным образом коммерческая компания обладает ограниченным количеством средств для оплаты операций, а каждый работник или продавец имеет ограниченные возможности в части объема работ, которые он может сделать, и ответственности, с которой он может справиться. Потребности, возможности и партнерские взаимоотношения всегда переменчивы.