Салют, Хабр!

Я Дарья, занимаюсь разработкой на C++ в SberDevices. В прошлом году мы рассказывали на Хабре, как реализовали функции умных колонок Sber Мультирум и Стереопара. В Мультируме один и тот же трек играет на нескольких устройствах синхронно, а в Стереопаре два устройства, воспроизводя звук одновременно, делят его на левый и правый — каждое устройство проигрывает свой канал. 

Перед нами встала задача развивать колонки далее: добавить опцию радио в режимах Мультирума и Стереопары, дать пользователям возможность выводить на стереопару звук с умного телевизора Sber и подключаться к ней по bluetooth, чтобы воспроизводить звук со смартфона. Сегодня я расскажу о передаче аудиопотока по протоколу UDP и алгоритмах избыточного кодирования.

Как работали режимы и как они работают теперь

Для Мультирума и Стереопары мы применяли Precision Time Protocol (PTP): он выбирал master-устройство по наименьшему MAC-адресу и синхронизировал время остальных устройств относительно него. Каждая колонка скачивала аудиопоток и начинала в одно и то же время играть семпл с точки 0. Далее мы проверяли, что в любую секунду времени на каждом устройстве в динамик уходит одно и то же количество аудиоданных. 

Вместе с этим по статистике многие слушали на своей умной колонке — в единственном числе — именно радио. Но в режимах Мультирума и Стереопары не могло работать ни радио, ни аудиопоток с умного телевизора или умной приставки, ни bluetooth-трансляция с другого устройства, например, со смартфона. Это всё потоковое аудио, у которого нет начала и конца. Соответственно, колонки не могли скачать подобное аудио и начать синхронно играть с точки 0:

  1. Потоковое аудио не обладает единой, фиксированной точкой синхронизации (точкой 0) для всех потребителей.

  2. Зачастую его вообще невозможно «скачать»: оно есть в одном экземпляре на одной колонке (это верно для bluetooth-стрима, например). 

  3. Оно существует в реальном времени, мы не можем заранее скачать с запасом часть звуковой дорожки. Да, можно накопить сколько-то данных, но в кейсах, где стрим озвучивает видео, накопление такого буфера приведёт к тому, что звук будет отставать от видео. То есть вывод звука с умного телевизора на колонки или стриминг bluetooth неизбежно будут проигрывать по скорости.

Исходя из этих вводных мы решили, что аудиопоток должен транслироваться с master-колонки на остальные по UDP. Ведь мы не можем позволить себе слишком большие задержки и чрезмерную нагрузку локальной сети. Разумеется, дополнительно обдумали вариант отправлять аудио по Multicast. Но его проблемы мы описывали в предыдущем тексте: нужна специальная настройка на некоторых роутерах, иначе он не будет работать или не справится с обработкой. Оборудование, которое предоставляет провайдер, может иметь трудности при работе с Multicast; вместе с тем у пользователя зачастую нет доступа к необходимым настройкам. Поэтому мы решили, что аудиопоток будет отправляться по Unicast, а режим Мультирум ограничили 10 устройствами — больше добавить туда нельзя.

Аудио потоковое, поэтому его отправитель — master-устройство — добавляет заголовки, из которых можно поня��ь, какому аудиовремени от начала проигрывания соответствует пакет. Далее устройства договариваются о времени начала проигрывания. Получается что-то вроде rtp, но очень облегчённое. 

Как доставить пакет с пакетами, или об алгоритмах forward error correction

Итак, для передачи аудиопотока мы используем протокол UDP — он обеспечивает более быструю доставку, но… даже при нормальной сети теряет пакеты. Чтобы уменьшить пропуски аудиоданных, мы используем механизм forward error correction (FEC, алгоритмы избыточного кодирования). Вместе с полезными данными отправляются дополнительные— такие, с помощью которых можно было бы восстановить потери в полезных данных. Несколько примеров FEC:

Дублирование пакетов

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

XOR

Ещё один из простых алгоритмов избыточного кодирования. Функция XOR паре бит сопоставляет 1, если они разные, и 0, если одинаковые:

0,0

0

0,1

1

1,0

1

1,1

0

Так как XOR ассоциативна, мы можем говорить о XOR от множества переменных, будем обозначать XOR(a,b,c) = XOR(XOR(a,b),c) = XOR(a, XOR(b,c)). Ещё она коммутативна, поэтому порядок переменных в выражении XOR(a1,...an) не имеет значения. Но главное свойство для нашей задачи — реверсивность:

XOR(a, b, b) = XOR(a, 0) = a

Значит, если у нас есть биты a1,....,an, мы можем посчитать от них x = XOR(a1,...an). И тогда для любого i:

XOR(a₁, …, aᵢ₋₁, aᵢ₊₁, …, aₙ, x) = XOR(a₁, a₁, a₂, a₂, …, aᵢ₋₁, aᵢ₋₁, aᵢ, aᵢ₊₁, aᵢ₊₁, …, aₙ, aₙ) = XOR(aᵢ, 0) = aᵢ

Таким образом, добавление 1 бита, являющимся XOR от всех остальных, позволяет восстановить потерю одного любого бита. 

Понятно, что можно применить побитово функцию к n пакетам и получить один пакет с XOR всех пакетов. Например, отправлять 5 полезных пакетов, потом 1 пакет с XOR от них. В таком случае мы отправляем в (n+1)/n больше траффика, а восстановить сможем максимум 1 пакет из n (в случае, если потеряется ровно 1 пакет).

Reed-Solomon

Этот алгоритм уже мощнее вышеперечисленных. Он позволяет к n полезным пакетам добавить k избыточных пакетов и при потерях, меньше или равных k, восстановить все эти потери. Можно даже корректировать ошибки, когда неизвестно, какой именно пакет потерян/ искажён, но в этой задаче нам не нужна такая опция. Ниже опишу работу этого алгоритма с теми параметрами, которые используем мы сами и которые при этом более-менее стандартны для такого рода задач.

Конечное поле

Мы будем работать в конечном поле из 256 элементов. Таким образом получится, что каждый байт представляет собой элемент в этом поле. Как строится поле:

  1. Берётся кольцо многочленов над GF(2) (поле из двух элементов — 0 и 1).

  2. В этом кольце берётся примитивный многочлен степени 8 — он должен быть неприводимым, а его корень должен быть примитивным элементом в соответствующем расширении поля (изоморфном GF(256)), об этом дальше. Обозначим его f, допустим,

    f = x⁸ + x⁷ + x² + x + 1

  3. Фактор по нему GF(2)[x]/(f) будет как раз полем из 256 элементов (GF(256)). 

Каждый элемент в получившемся поле можно представить в виде многочлена 7 степени с коэффициентами 0 и 1 (остаток от деления многочлена из GF(2)[x] на f). Получается, любой элемент поля можно задать 8 коэффициентами такого многочлена; таким образом получается, что можно сопоставить 1 байт такому многочлену (или элементу поля GF(256)).

Что ещё удобно в таком поле: если выкинуть из него 0, то это циклическая группа по умножению. В поле существует элемент alpha, такой, что 1, alpha, ... alpha254 − все различные элементы, alpha255 = 1.  Его называют примитивным элементом; всегда можно сопоставить этот элемент корню многочлена f, так как мы изначально выбрали такой многочлен для генерации поля.

Получается, что, с одной стороны, каждый элемент представляется многочленом 7 степени с коэффициентами 0 и 1 (то есть 8 битами), а с другой — каждый ненулевой элемент представляется степенью примитивного элемента alpha. Значит, имея таблицу, можно дёшево складывать и умножать элементы поля.

Элемент

В виде коэффициентов

В виде степени alpha

1

00..0001

0

..

x

00..0010

1

x7+x2+x+1

10000111

8

Алгоритм

Всюду дальше мы работаем в поле, которое описано выше: GF(256) из 256 элементов. Многочлены будут уже над ним (не путать с многочленами над GF(2), которые сами являются элементами поля).

У нас есть msg полезных байт. Мы хотим добавить ecc дополнительных так, чтобы можно было восстановить ecc потерь. Пусть для примера у нас 4 msg и 3 ecc. Строим многочлен степени 6 (msg+ecc-1) такой, чтобы его корнями были 1, alpha, alpha2. Корней столько, сколько ecc, все корни — степени примитивного элемента. Строится он таким образом:

m(x) = msg[0] ⋅ x⁶ + msg[1] ⋅ x⁵ + msg[2] ⋅ x⁴ + msg[3] ⋅ x³

В формуле выше мы оставляем место для трёх ecc коэффициентов. Делим его с остатком на g(x) = (x-1)*(x-alpha)*(x-alpha2):

m(x) = g(x) ⋅ somepolynomial(x) + r(x)

где r(x) — остаток от деления, deg(r(x)) < deg(g(x)) = ecc. То есть остаток r степени меньше ecc. Запишем его в таком виде:

r(x) = ecc[0] ⋅ x² + ecc[1] ⋅ x + ecc[2]

Дальше строим многочлен result(x) = m(x) + r(x). Он делится на g(x), потому что r(x) + r(x) = 0, так как все коэффициенты в GF(256) и имеют характеристику 2 (при сложении сами с собой дают ноль). Получается:

result(x) = msg[0] ⋅ x⁶ + msg[1] ⋅ x⁵ + msg[2] ⋅ x⁴ + msg[3] ⋅ x³ + ecc[0] ⋅ x² + ecc[1] ⋅ x + ecc[2]

Вот эти коэффициенты мы и передаём по сети. Получается 4 полезных байт (msg) и 3 дополнительных (ecc). То есть мы передаём по сети семь коэффициентов многочлена, к��рнями которого являются три известных числа в нашем поле.

Зная позиции потерь, получатель может восстановить любые 3 потерянных коэффициента, подставляя 3 корня (1, alpha, alpha2) в полученный многочлен. Например, если потерялись пакеты на позициях msg[0], msg[2] и ecc[0], то в теории можно подставить (1, alpha, alpha2) сюда:

msg[1] ⋅ x⁵ + msg[3] ⋅ x³ + ecc[1] ⋅ x + ecc[2] = msg[0] ⋅ x⁶ + msg[2] ⋅ x⁴ + ecc[0] ⋅ x²

И получить три уравнения от трёх неизвестных. (На практике алгоритм чуть более сложен, но в целом видно, что декодирование возможно). Плюс все вычисления происходят в конечном поле, где можно совершать арифметические операции и не выходить из байтового представления чисел.

Практика алгоритмов избыточного кодирования

Мы не тратили очень много времени на анализ других алгоритмов, потому что Reed-Solomon дает минимальное количество возможных накладных расходов для нашего сценария —позволяет исправить любое количество (n) потерянных пакетов, добавив всего n избыточных. Остальные популярные алгоритмы (например, RaptorQ) лишь приближаются к таким показателям. Единственное, что можно улучшить — это для каких-то из вариантов параметров (количества полезных пакетов, количества избыточных) применять более производительные алгоритмы. Например, для случая с 1 избыточным пакетом мы просто используем XOR. В планах ещё больше расширить спектр применяемых алгоритмов. 

Мотивацией использовать другие алгоритмы могла бы стать их лучшая производительность за счёт снижения корректирующей способности. Но в нашем случае параметры подстраиваются под состояние сети, и в подавляющем большинстве случаев FEC либо не используются вообще, либо используется только XOR, потому что он дает минимум нагрузки на cpu. Для плохих сетевых условий, когда всё-таки приходится использовать Reed-Solomon, принимающая сторона декодирует только те блоки, где были потери полезных пакетов за счёт того, что кодирование систематическое (сами пакеты отправляются в исходном виде). 

При выборе параметров нужно стремиться на выходе:

  1. Получить как можно меньше потерь.

  2. Не увеличить слишком сильно задержку.

  3. Не создать чрезмерную нагрузку на сеть (да и на cpu тоже не хочется давать больше нагрузки, чем надо).

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

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

На первом графике показано, сколько в итоге теряет пакетов получатель  при разных сетевых потерях и разных параметрах fec. Например, если в сети теряется 1% пакетов, то при использовании параметров (3,1) получатель в итоге теряет всего 0,37% пакетов. А если использовать (6,5), то итог — 0,23% потерь.

Второй график демонстрирует, сколько потерянных полезных пакетов удаётся восстановить с разными параметрами и разными сетевыми потерями. Так, если в сети теряется 1% пакетов, то при использовании параметров (3,1) удается восстановить 62% пакетов. А если использовать (6,5), то 77%.

Тут приводится не очень большая выборка и для определённого размера пакета, и определённой частоты отправки. Выше данные по тому, как восстанавливаются пакеты, содержащие 10 мс аудио-данных, то есть без избыточных пакетов это 100 штук в секунду (отправка каждые 10 мс), с максимальной используемой нами избыточностью 200 в секунду (отправка каждые 5 мс). От пресловутой частоты очень сильно зависит, насколько удачно удаётся восстановить потерянные пакеты. В некоторых условиях отправка больших пакетов реже с 1 избыточным даёт меньше потерь на выходе, чем отправлять много маленьких пакетов даже с x2 избыточностью. Поэтому для источников, для которых мы можем заранее получить данные (например, скачиваемых из сети), делаем пакеты побольше. А для таких источников, как стрим bluetooth, вынуждены всё равно отправлять более мелкие пакеты чаще и добавлять больше избыточных. 

Ниже сравнение восстановительной способности одних и тех же FEC параметров (1 избыточный пакет на 3 полезных) для случаев, когда отправляем пакеты по 10 мс (отправка каждые 8 мс примерно) и по 40 мс (отправка каждые 30мс).

Точное время

Мы также немного поменяли протокол синхронизации времени. В прошлой статье рассказывали, как мы адаптировали протокол PTP под свою задачу. С тех пор мы его заменили на собственный PTP-alike алгоритм, который считает разницу CLOCK_MONOTONIC_RAW-часов. Эти часы опираются на кварцевый резонатор устройства, чип реального времени или другое подобное устройство и отсчитывают время с начала загрузки системы. Они не подвержены корректировкам системы (adjtime и сдвигам), а ещё их поведение более стабильно на коротком времени, что позволяет получить более точные оценки их разниц на устройствах. Master-колонка начинает играть с опорой на свой monotonic raw clock, и каждое slave-устройство, «зная» свою разницу во времени с master, начинает играть одновременно с ним.  

Выбор «мастера» в классическом PTP был больным местом, особенно когда он менялся. Это могло произойти, например, когда устройство, которое было PTP-MASTER, пропадало из сети. Остальные устройства начинали снова согласовывать мастера и пересчитывать свои ptp-параметры (а момент начальной подстройки самый плохой для синхронизации). Так, если пользователь выключил свое устройство по питанию, это могло влиять на синхронизацию двух других его устройств (например, стереопары). Мы ушли от этого: теперь в каждой паре устройств есть свой «ptp-мастер». Мы просто выбираем устройство с минимальным идентификатором, и оно становится ptp-мастером в этой паре. Устройства обмениваются несколькими сообщениями между собой, как и в обычном PTP, по udp; мастер делает оценку смещения часов и оценку разницы их скорости, ничего не корректируя при этом. 

На наших устройствах эти часы (monotonic_raw) идут почти что с одинаковой скоростью; в целом они даже не требуют оценки drift относительно друг друга. Особенно это относится к колонкам. Но на всякий случай мы подсчитываем также drift; для случая, если он слишком велик, у нас есть механизм изменения скорости подачи семплов на аудиодрайвер.

Заключение

Работа software-команды не ограничивается выпуском устройства: мы продолжаем «прокачивать» его и развивать с каждой новой прошивкой. Теперь медиаконтент получает и делится им с другими только одно устройство — master-устройство. Оно может быть любым, в том числе умным телевизором Sber в случае, если к нему подключена Стереопара. Алгоритмы FEC обеспечивают восстановление потерянных пакетов. Разработка и внедрение нового подхода позволили улучшить качество синхронизации и обработки ошибок — а значит, и пользовательский опыт владельца умных колонок Sber.

В подготовке статьи участвовали: Алексей Белый, Павел Конюхов