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

За последнее десятилетие исследователи в промышленности и академических кругах разработали несколько алгоритмов, которые пытаются достичь высоких показателей при одновременном контроле задержек. Некоторые из них, такие как алгоритм BBR, разработанный Google, в настоящее время широко используются многими веб-сайтами и приложениями.

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

"Что действительно удивительно в этой статье и ее результатах, так это то, что если принять во внимание реальную сложность сетевых путей и все то, что они могут сделать с пакетами данных, то для алгоритмов управления перегрузкой, контролирующих задержку, в принципе невозможно избежать голода, используя современные методы", - говорит Мохаммад Ализаде, доцент кафедры электротехники и компьютерных наук (EECS).

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

Ализаде написал статью вместе с первым автором и аспирантом EECS Венкатом Аруном и старшим автором Хари Балакришнаном, профессором компьютерных наук и искусственного интеллекта Fujitsu. Исследование будет представлено на конференции ACM Special Interest Group по передаче данных (SIGCOMM).

Контроль заторов

Контроль перегрузки - фундаментальная проблема в сетевых технологиях, которую исследователи пытаются решить с 1980-х годов.

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

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

Даже если алгоритм контроля перегрузки идеально измеряет задержку, он не может определить разницу между задержкой, вызванной перегрузкой, и задержкой, вызванной дрожанием. Задержка, вызванная дрожанием, непредсказуема и сбивает отправителя с толку. Из-за этой двусмысленности пользователи начинают по-разному оценивать задержку, что заставляет их отправлять пакеты с неодинаковой скоростью. В конечном счете, это приводит к ситуации, когда возникает голод, и кто-то оказывается полностью изолированным, объясняет Арун.

"Мы начали проект, потому что нам не хватало теоретического понимания поведения контроля перегрузки при наличии дрожания. Чтобы поставить это на более прочную теоретическую основу, мы построили математическую модель, которая была достаточно простой для осмысления, но в то же время способной охватить некоторые сложности Интернета. Было очень полезно, когда математика рассказывала нам о вещах, которых мы не знали, и которые имеют практическое значение", - говорит он.

Изучение голодания

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

"Мы не могли этого сделать. Мы перепробовали все известные нам алгоритмы и придумали несколько новых. Ничего не помогало. Компьютер всегда сталкивался с ситуацией, когда некоторые люди получают всю полосу пропускания, а по крайней мере один человек практически ничего не получает", - говорит Арун.

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

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

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

"Чтобы контролировать задержки, алгоритмы попытались также связать вариации задержки с желаемым равновесием, но нет ничего плохого в том, чтобы потенциально создавать большие вариации задержки для получения лучших измерений застойных задержек. Это просто новая философия дизайна, которую вам придется принять", - добавляет Балакришнан.

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

"Мы все больше полагаемся на компьютерные системы в очень важных вещах, и нам необходимо поставить их надежность на более прочную концептуальную основу. Мы показали удивительные вещи, которые вы можете обнаружить, если потратите время на то, чтобы сформулировать эти формальные спецификации того, в чем на самом деле заключается проблема", - говорит Ализаде.