Американские ученые создали новый алгоритм оценки задержек и потерь пакетов

Исследователи из Калифорнийского университета в г. Сан-Диего и университета Пердью предложили новый алгоритм, который поможет существенно уточнить измерение таких важных параметров, как задержка передачи и потери пакетов с данными. Точная оценка этих характеристик очень важна в коммуникациях реального времени, сетевых научно-технических вычислениях, а также в такой актуальной сфере финансового рынка, как автоматизированная торговля ценными бумагами с повышенной скоростью заключения сделок (high-frequency trading).

Авторы алгоритма под названием LDA (Lossy Difference Aggregator – агрегатор отклонений с потерями) проводили свое исследование в рамках двух грантов: от национального научного фонда США (NSF – National Science Foundation) и компании Cisco. Разработка нового алгоритма была обусловлена неспособностью имеющихся технологий – протоколов SNMP, NetFlow и активного зондирования – измерять задержки и потери пакетов с точностью до микросекунд. К сожалению, внедрение нового алгоритма требует аппаратной модернизации современных роутеров и другого активного сетевого оборудования. Кроме того, нужны изменения в недавно принятом стандарте IEEE 1588 для синхронизации часов через сеть. С другой стороны, предложенная схема позволяет вводить новое оборудование постепенно, с плавным повышением точности измерений.

В общем случае мониторинг неполадок в сети заключается в назначении каждому пакету метки времени и последующем контроле таких меток. Такая маркировка всех пакетов подряд существенно увеличивает нагрузку на процессоры сетевого оборудования, поэтому разработчики алгоритма Lossy Difference Aggregator предложили оценивать производительность сети по репрезентативной выборке пакетов. На отправляющей стороне для каждого пакета рассчитывается значение хэша. Это значение определяет позицию пакета в специальной матрице фиксированного размера (номер столбца и строки). В примере, который приведен в статье авторов, 3 нуля в начале хэша означают помещение в первый столбец («банк» в терминологии разработчиков), а 7 нулей – во второй столбец-«банк». Похожим образом вычисляется номер строки для пакета. Вся информация, не имеющая отношения к позиционированию пакета в матрице, отбрасывается. Например, последовательность из 1024 элементов может содержать 1 банк на 1024 элемента, либо 4 банка по 256 элементов.

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

Авторы алгоритма LDA считают, что реализация новой технологии мониторинга качества передачи не потребует серьезных затрат даже для самых недорогих ASIC-микросхем, лежащих в основе массового, недорогого сетевого оборудования. Для передачи контрольных данных дополнительно потребуется всего 72 Кбит/с на канал. Перспективность новой разработки сильно зависит от потенциальных заказчиков: научные вычислительные центры и финансовые организации, заключающие десятки тысяч сделок в секунду, некритично относятся к повышению стоимости, но очень щепетильны в вопросах микросекундных задержек и малейших потерь пакетов, так что алгоритм LDA может быть внедрен в такого рода средах в самое ближайшее время.