Анализ сетевых боттлнеков (2)

Продолжение (предыдущая заметка здесь)

Целью всей этой истории является разработка некоего решения, которое бы позволило оценивать пропускную способность канала аплинка для использования в системе QoS роутера. Т.е все это для того, что бы пользователь не утруждался вводом “договорной пропускной способности” в соответствующее поле настроек.

Широко применяемые методики — speedtest, netperf или iperf тут слабо применимы, потому что предполагают скачивание существенных объемов трафика из какого-то особого места, например, CDN. В случае, когда такие измерения носят массовый характер, это может оказаться очень накладно во всех смыслах. Кроме того, такая методика неустойчива к постороннему трафику — т.е если в момент, когда имеряется скорость канала путем генерации/приема эталонного объема трафика кто-то на этом канале делает что-то еще, результаты будут искажены.

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

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

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

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

мы получим

что вселяет веру в успех всей этой затеи, ведь это ровно ширина моего аплинка по договору с провайдером (если что, мне просто пока хватает).

Это всего лишь заметка в блоге, а не статья и не доклад к конференции, поэтому я не буду делать полный обзор всех известных алгоритмов. В финал вышли PPRate, MultiQ и CapProbe — все ищутся поиском. Существует пара работ, сравнивающих эти алгоритмы,
и в них PPRate показывает себя не хуже двух других, а иногда и лучше, и сравнимо с pathrate, который использует “сотрудничающее окружение”, т.е использует генератор трафика. Кроме того, PPRate использует намного более простой и понятный способ препроцессинга входных данных, что и определило моё решение остановиться пока на нём.

Где-то на полях надо заметить, что во всей этой истории с пассивным определением пропускной способности канала есть некоторая странность. Исходные коды практически всех описываемых в документах программ недоступны. Самые старые, типа pchar еще встречаются даже в репозиториях Debian, но они толком не работают. Остальное же просто давно куда-то исчезло, несмотря на то, что в документах есть URL, где якобы можно скачать исходники. Встречаются более поздние попытки реализации, например, MultiQ, но в таком виде, что явно придется переписывать.

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

Ну что же. Модифицируем утилиту для захвата пакетов из предыдущей заметки таким образом, что бы она сохраняла таймстемпы пакетов, а не межпакетные интервалы. Интервалы будем считать уже в оффлайне. Реализуем алгоритм pprate, а именно:

Для начала посчитаем межпакетные интервалы по таймстемпам по потокам, найдем моды и если распределение унимодальное, то найдем сразу скорость, и не будем приступать к процедуре дальнейшей обработке, которая тут заключается в измерении дисперсии времени в “packet trains” т.е последовательностей пакетов всё нарастающей длины, пока распределение не станет унимодальным.

Вместо hstat можно использовать более функциональный statistics, в нём многое есть сразу и не нужно ничего писать.

Полный дамп кода можно посмотреть ниже, для начала же можно сказать следующее:

Распределение межпакетных интервалов по потокам в основном унимодальное, редко две моды, больше я не видел.

Данные требуют препроцессинга, т.к. в них пакеты распределены очень неравномерно, есть как огромные интервалы (единицы секунд), так и какое-то заметное количество сосредоточенное вокруг величины, которая заведомо не соответствует пропускной способности канала — вероятно, как-то связано с обработкой пакетов в ядре линукса или проблемы механизма захвата.

Шаг гистограммы авторы алгоритма предлагают брать равный “5% от интерквартильного растояния измерения пропускной способности”. Возможно, этот пункт я не вполне понял, поэтому взял 5% этого самого интерквартильного расстояния от самой выборки.

Автоматический выбор диапазона гистограммы (Statistics.Sample.Histogram) очень часто приводит к отрицательным значениям первого бина, и как результат бессмысленным значениям времени/скорости. Для борьбы с этим пришлось отбросить несколько первых и последних квантилей, как это рекомендует, например, автор статьи из предыдущей заметки:

На вход функции pitHistogram поступает количество вагонов “packet train” (мы начинаем с двух), и приведенные к Double таймстемпы в наносекундах, остальное, я думаю, вполне понятно из кода.

Итог (неутешительный). Несмотря на то, что скорость довольно правдоподобно определяется на незашейпленом Ethernet, сопоставимо с тем, что показывает speedtest, при наличии программного шейпинга точность сильно падает — т.е стабильно занижается в два с половиной раза. Но намного хуже всё обстоит на wlan, там разброс огромен и получаемые значения совершенно бессмысленны. Более того, наблюдаемый характер распределения этих самых межпакетных интервалов вызывает сомнения в состоятельности вообще всего куста методик, основанных на измерениях межпакетной дисперсии, в каком бы виде они ни были — пары пакетов, “поезда пакетов” и так далее. Дописывать вторую часть алгоритма я не стал, так как 1) распределения и так получались, в основном, унимодальные 2) выбирая из большого числа потоков можно выбрать только те, где эти распределения унимодальные 3) последующая аппроксимация при помощи “packet trains” только ухудшает точность.

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

Полный дамп релевантного кода, пускай будет иллюстрацией к пакету statistics.

Продолжение возможно следует…