Алгоритмы для жизни: Простые способы принимать верные решения - [100]

Вскоре после принятия присяги в Первом окружном суде на Гавайях судья Стивен Альм обратил внимание на странную картину. Участники программы неоднократно нарушали условия своего испытательного срока, а окружные судьи, регулярно пользуясь своими особыми полномочиями, отпускали их с предупреждением без наказания. Но в какой-то момент, вероятно после дюжины-другой нарушений, судья принимал решение быть строгим и приговаривал нарушителя к нескольким годам тюремного заключения. Альм вспоминает: «Я подумал: что за идиотский способ заставить кого-то изменить свое поведение!» И Альм предложил нечто практически противоположное. Вместо слушаний о нарушениях, расписанных на месяцы вперед, требующих непонятных вызовов в суд и иногда завершающихся значительными санкциями, «НАДЕЖДА» практикует немедленные, заранее установленные наказания, которые начинаются с одного дня в тюрьме, и срок этот увеличивается после каждого инцидента. Пятилетнее исследование Департамента юстиции доказало, что подопечных «НАДЕЖДЫ» арестовывали за новые преступления или отзывали с испытательного срока в два раза реже, чем обычных участников программы. И наркотики они употребляли на 72 % реже. Семнадцать штатов последовали примеру Гавайев и запустили свои собственные версии «НАДЕЖДЫ».

Управление потоком и предотвращение перегрузки

Первые усилия в построении компьютерных сетей были сосредоточены на обеспечении надежной передачи сообщений посредством ненадежных соединений. Эти усилия оказались вполне успешными. Таким образом, сразу же возникла вторая забота: необходимо было удостовериться, что перегруженная сеть сможет избежать катастрофического обвала. Только-только TCP-протоколу (протокол управления передачей) удалось решить проблему с доставкой информации из пункта А в пункт Б, как он столкнулся с новой проблемой – затором.

Первое значимое предупреждение появилось в 1986 году на линии, соединяющей Национальную лабораторию Беркли им. Э. Лоуренса и студенческий городок Университета Беркли, находящиеся друг от друга на расстоянии длины футбольного поля. (В Беркли пространство действительно занято настоящим футбольным полем.) Однажды пропускная способность линии резко упала с привычных 32 000 бит в секунду до 40 бит в секунду. Пострадавшие в этой ситуации Ван Джейкобсон из LBL и Майкл Карелс из UCB «были поражены этим внезапным тысячекратным падением и решили выяснить, что стало причиной произошедшего».

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

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

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

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

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