ДИНАМИЧЕСКОЕ ПЕРЕМЕЖЕНИЕ ПОТОКОВ И ДОСТАВКА НА ОСНОВЕ ПОДПОТОКОВ
DYNAMIC STREAM INTERLEAVING AND SUB-STREAM BASED DELIVERY

Перекрестная ссылка на родственные заявки
Данная заявка испрашивает приоритет предварительной заявки на патент США номер 60/912145, озаглавленной "Dynamic Stream Interleaving and Sub-Stream Based Delivery", поданной 16 апреля 2007 года. Содержимое этой заявки полностью включено в данном документе посредством ссылки для всех целей.
Настоящее раскрытие сущности изобретения также включает в себя посредством ссылки, как если бы они были полностью изложены в этом документе, для всех целей, следующие совместно переуступленные заявки/патенты:
Патент США №6307487 на имя Luby (в дальнейшем "Luby I");
Патент США №7068729 на имя Shokrollahi и др. (в дальнейшем "Shokrollahi I");
Патентная заявка США №11/423391, поданная 9 июня 2006 и озаглавленная "Forward Error-Correcting (FEC) Coding and Streaming", на имя Luby и др. (в дальнейшем "Luby II"); и
Патентная заявка США №11/674625, поданная 13 февраля 2007 года, озаглавленная "Streaming and Buffering Using Variable FEC Overhead and Protection Periods", на имя Watson и др. (в дальнейшем "Watson").
Область техники, к которой относится изобретение
Настоящее изобретение относится к повышению качества потоковой доставки, времени на переключение содержимого, масштабированной распределенной доставке потоков и использованию FEC-кодирования во всех аспектах, чтобы совершенствовать решения по потоковой передаче. Потоковая передача содержит потоковую передачу аудио, видео и данных, на постоянной скорости или переменной скорости передачи битов, для воспроизведения содержимого в форме списков воспроизведения по запросу или прямого воспроизведения.
Уровень техники
Доставка потокового мультимедиа становится все более важной, поскольку становится все более распространенным, что высококачественное аудио и видео доставляется по сетям с коммутацией пакетов, таким как Интернет, сотовые и беспроводные сети, линии электросети и многие другие сети. Качество доставляемого потокового мультимедиа зависит от ряда факторов, в том числе качества исходного содержимого, качества кодирования исходного содержимого, возможностей приемников декодировать и отображать видео, своевременности и качества сигнала, принимаемого в приемниках, и т.д. Чтобы создавать высококачественное восприятие потокового мультимедиа, транспортировка и своевременность сигнала, принимаемого в приемниках, являются особенно важными. Хороший транспорт предоставляет точность воспроизведения потока, принимаемого в приемнике, по сравнению с тем, что отправляется от передатчика, тогда как своевременность представляет то, как быстро приемник может начинать воспроизведение содержимого после начального запроса этого содержимого.
В последнее время стало установившейся практикой рассматривать использование кодов прямой коррекции ошибок (FEC) для защиты потокового мультимедиа во время передачи. Когда отправляется по пакетной сети, примеры которой включают в себя Интернет и беспроводные сети, такие как стандартизированные посредством таких групп, как 3GPP, 3GPP2 и DVB, исходный поток помещается в пакеты по мере того, как он формируется или становится доступным, и тем самым пакеты используются для того, чтобы переносить исходный поток или поток содержимого в том порядке, в котором он формируется или становится доступным, в приемники.
В нетипичном варианте применения FEC-кодов для этих видов сценариев кодер использует FEC-код при создании исправляющих пакетов, которые затем отправляются в дополнение к первоначальным исходным пакетам, содержащим исходный поток. Исправляющие пакеты имеют такое свойство, что, когда возникает потеря исходных пакетов, принимаемые исправляющие пакеты могут использоваться для того, чтобы восстанавливать данные, содержащиеся в потерянных исходных пакетах. Исправляющие пакеты могут использоваться для того, чтобы восстанавливать содержимое потерянных исходных пакетов, которые потеряны полностью, но также могут использоваться для восстановления после того, как возникает частичная потеря пакетов, либо за счет полностью принимаемых исправляющих пакетов, либо даже за счет частично принимаемых исправляющих пакетов. Таким образом, полностью или частично принимаемые исправляющие пакеты могут использоваться для того, чтобы восстанавливать полностью или частично потерянные исходные пакеты.
В других примерах другие типы повреждения могут возникать для отправляемых данных, к примеру, значения битов могут быть инвертированы, и, таким образом, исправляющие пакеты могут использоваться для того, чтобы корректировать это повреждение и предоставлять максимально точное восстановление исходных пакетов. В других примерах исходный поток не обязательно отправляется в дискретных пакетах, а вместо этого может отправляться, например, как непрерывный поток битов.
Имеется много примеров FEC-кодов, которые могут использоваться для того, чтобы предоставлять защиту исходного потока. Коды Рида-Соломона - это известные коды для коррекции ошибок и стирания в системах связи. Для коррекции стирания, например, в сетях пакетной передачи данных известная эффективная реализация кодов Рида-Соломона использует матрицы Коши или Вандермонда, как описано в L. Rizzo, "Effective Erasure Codes for Reliable Computer Communication Protocols", Computer Communication Review, 27 (2): 24-36 (апрель 1997 года) (в дальнейшем "Rizzo") и Bloemer и др., "An XOR-Based Erasure-Resilient Coding Scheme", Technical Report TR-95-48, International Computer Science Institute, Berkeley, California (1995) (в дальнейшем "XOR-Reed-Solomon"), или в других источниках.
Другие примеры FEC-кодов включают в себя LDPC-коды, коды цепной реакции, такие как описанные в Luby I, и коды многостадийной цепной реакции, такие как в Shokrollahi I.
Примеры процесса FEC-декодирования для разновидностей кодов Рида-Соломона описываются в Rizzo и XOR-Reed-Solomon. В этих примерах декодирование применяется после того, как принято достаточно исходных и исправляющих пакетов данных. Процесс декодирования может требовать большого объема вычислений, и, в зависимости от доступных ресурсов CPU, его выполнение может отнимать большое количество времени относительно длительности времени, охватываемой посредством мультимедиа в блоке. Приемник должен принимать во внимание эту длительность времени, требуемую для декодирования, при вычислении задержки, требуемой между началом приема медиапотока и воспроизведением медиа. Эта задержка, обусловленная декодированием, воспринимается пользователем как задержка между его запросом на предмет конкретного медиапотока и началом воспроизведения. Таким образом, желательно минимизировать эту задержку.
Во многих вариантах применения пакеты дополнительно подразделяются на символы, к которым применяется FEC-процесс. Пакет может содержать один или более символов (или менее одного символа, но обычно символы не разбиваются между пакетами). Символ может иметь любой размер, но зачастую размер символа самое большее равен размеру пакета. Исходные символы - это символы, которые кодируют данные, которые должны быть переданы. Исправляющие символы - это символы, сформированные из исходных символов, которые прямо или косвенно являются в дополнение к исходным символам (т.е. данные, которые должны быть переданы, могут быть полностью восстановлены, если все исходные символы доступны, и ни один из исправляющих символов недоступен).
Некоторые FEC-коды основаны на блоках в том, что операции кодирования зависят от символа(ов), которые находятся в блоке, и могут быть независимыми от символов не в этом блоке. При блочном кодировании FEC-кодер может формировать исправляющие символы для блока из исходных символов в этом блоке, затем переходить к следующему блоку и не обязательно должен обращаться к исходным символам, отличным от символов для текущего кодированного блока. При передаче исходный блок, содержащий исходные символы, может представляться посредством кодированного блока, содержащего кодированные символы (которые могут быть несколькими исходными символами, несколькими исправляющими символами или и тем, и другим). При наличии исправляющих символов не все исходные символы требуются в каждом кодированном блоке.
Для некоторых FEC-кодов, а именно кодов Рида-Соломона, время кодирования и декодирования становится непрактичным по мере того, как число кодированных символов на исходный блок возрастает. Таким образом, на практике зачастую предусмотрена целесообразная верхняя граница (255 - это приблизительное целесообразное ограничение для некоторых приложений) для общего числа кодированных символов, которые могут быть сформированы на исходный блок, в частности, в типичном случае, где процесс кодирования и декодирования по Риду-Соломону выполняется посредством специализированных аппаратных средств, к примеру, MPE-FEC-процессы, которые используют коды Рида-Соломона, включенные как часть DVB-H-стандарта, для защиты потоков от потери пакетов, реализуются в специализированных аппаратных средствах в сотовом телефоне, который ограничен всего 255 кодированными символами Рида-Соломона на исходный блок. Поскольку символы зачастую должны помещаться в отдельные рабочие данные пакета, это задает целесообразную верхнюю границу на максимальную длину кодированного исходного блока. Например, если рабочие данные пакета ограничены 1024 байтами или менее и каждый пакет переносит один кодированный символ, то кодированный исходный блок может составлять самое большее 255 Кбайт (килобайт), и это, разумеется, также является верхней границей размера самого исходного блока.
Другие проблемы, к примеру, возможность декодировать исходные блоки достаточно быстро, чтобы не отставать от скорости исходной потоковой передачи, чтобы минимизировать время задержки на декодирование, вводимое посредством FEC-декодирования, и использовать только небольшую часть доступной мощности CPU в приемнике в любой момент времени во время FEC-декодирования, представляют сложность в решении.
Другие проблемы включают в себя возможность начинать воспроизведение потока, например, декодирование и подготовку посредством рендеринга принимаемых аудио- и видеопотоков с использованием персонального компьютера и отображение видео на экране компьютера и воспроизведение аудио через встроенные динамики, или, в качестве еще одного примера, декодирование и подготовку посредством рендеринга принимаемых аудио- и видеопотоков с использованием абонентской приставки и отображение видео на телевизионном дисплее, и воспроизведение аудио через стереосистему. Первоочередная задача заключается в том, чтобы минимизировать задержку между тем, когда пользователь решает просматривать новое содержимое, доставляемое как поток, и когда содержимое начинает воспроизведение, в дальнейшем называемую "временем на переключение содержимого". Примером переключения содержимого является, когда пользователь просматривает первое содержимое, доставляемое через первый поток, и затем пользователь решает просматривать второе содержимое, доставляемое через второй поток, и инициирует действие, чтобы начинать просмотр второго содержимого. Второй поток может отправляться из того же набора или другого набора серверов по сравнению с первым потоком. Другим примером переключения содержимого является, когда пользователь посещает веб-узел и решает начинать просмотр первого содержимого, доставляемого через первый поток, посредством щелчка ссылки в окне обозревателя. Еще одним примером переключения содержимого является, когда пользователю желательно находить и начинать просмотр в новой позиции, вперед или назад, в этом же потоке содержимого. Минимизация времени на переключение содержимого является важной для просмотра видео, чтобы предоставлять пользователям высококачественную быструю навигацию по содержимому при поиске и выборке широкого диапазона доступного содержимого. Высококачественная быстрая навигация по содержимому зачастую положительно коррелирована с объемом содержимого, которое используют пользователи.
Зачастую имеет место то, что основным фактором времени на переключение содержимого является базовая структура FEC. Другая задача заключается в минимизации временного промежутка между окончанием воспроизведения одного фрагмента содержимого и началом воспроизведения другого фрагмента содержимого, который предпочтительно идет следом с небольшой паузой или без нее. Например, если один фрагмент содержимого - это широковещательная телевизионная передача, а следующий фрагмент содержимого - это реклама, или наоборот, длительный промежуток (в данном документе называемый "временем на смену содержимого") между их воспроизведением нежелателен.
Безусловно, желательна минимизация времени на смену содержимого при одновременной минимизации скорости потоковой передачи в приемник в течение периодов времени, окружающих переход.
Другая задача заключается в том, чтобы максимизировать качество доставляемого потока при использовании сети доставки на основе принципа максимальной эффективности, такой как Интернет, которая может отбрасывать пакеты и которая может вызывать глобальные изменения количества времени, которое занимает доставка пакетов, при одновременной минимизации использования сетевых ресурсов, таких как полоса пропускания.
Другая задача заключается в том, чтобы предоставлять отказоустойчивое и масштабируемое решение по доставке потоковой передачи, которое дает возможность компонентам системы отказывать без негативного влияния на качество потоков, доставляемых в приемники.
Перемежение может использоваться для того, чтобы предоставлять превосходную защиту от дефектов в канале, таких как скачкообразная потеря пакетов. Например, потеря пакетов зачастую является в некоторой степени пульсирующей, и тем самым распределение исходного блока по более длительным периодам времени может быть преимущественным. Для некоторых FEC-кодов собственное использование больших исходных блоков целесообразно, но для других FEC-кодов, таких как коды Рида-Соломона, зачастую имеются целесообразные ограничения на размер исходного блока, который может использоваться. Таким образом, чтобы распределять передачу пакетов, ассоциированных с исходным блоком, по более длительному интервалу времени, может быть преимущественным перемежать отправку пакетов, содержащих кодированные символы для различных исходных блоков.
Ранее появились способы, которые разрешают некоторые из задач, описанных выше. Например, некоторые новые способы формирования исходных FEC-блоков и перемежения описываются в Luby II. Некоторые способы перемежения являются статическими в том смысле, что величина перемежения является фиксированной для всего потока. Таким образом, иногда предусматривается компромисс между величиной перемежения, которая влияет на качество защиты, предлагаемое посредством таких способов, и временем на переключение содержимого, т.е. большие величины перемежения предоставляют лучшую защиту потоков, но задают более длительное время на переключение содержимого, и этот компромисс определяется фиксированным способом для всей длительности потоковой передачи в приемник.
Имеются некоторые способы, которые предоставляют небольшое время на переключение содержимого и большие величины перемежения в течение значительной части процесса отправки потока, например некоторые способы, описанные в Watson. Некоторые из способов, описанных в Watson, динамически переходят от коротких начальных исходных блоков ко все более длинным исходным блокам и в течение переходного периода отправляются на немного большей скорости, чем скорость потоковой передачи содержимого. Эти способы предоставляют небольшое время на переключение содержимого при одновременном предоставлении возможности повышения качества защиты, предоставляемой по мере того, как продолжается прохождение потока. Например, один способ применения некоторых из способов, описанных в Watson, состоит в том, чтобы определять структуру исходных блоков и выполнять FEC-кодирование в то время, когда поток отправляется, т.е. структура исходных блоков "от коротких к длинным" определяется и FEC-кодируется по мере того, как они отправляются в каждой точке, где к ним осуществляется доступ, в отдельные приемники, и тем самым формирование структуры исходных блоков и FEC-кодирование выполняются уникально для каждого приемника, и поток, отправляемый в каждый приемник, является уникальным. Тем не менее, иногда желательно иметь структуру исходных блоков потока содержимого, определяемую независимо от доставки потока, к примеру независимо от приемников, независимо от того, когда содержимое просматривается, и где в потоке содержимого начинается просмотр, и независимо от того, в каком порядке доставляются данные в рамках потока. Это особенно важно, если поток содержимого должен быть доставлен из нескольких серверов в один приемник.
Таким образом, желательно совершенствовать процессы и устройство.
Сущность изобретения
Варианты осуществления кодеров, декодеров и системы связи согласно аспектам настоящего изобретения предусматривают способы динамического перемежения потоков, в том числе способы для динамического введения больших величин перемежения по мере того, как поток передается, независимо от структуры исходных блоков. Некоторые преимущества этих способов заключаются в том, что они распределяют потери или ошибки в канале по гораздо большему периоду времени в рамках первоначального потока, чем если бы перемежение не вводилось, они предоставляют превосходную защиту от потери пакетов или повреждения пакетов при использовании с FEC-кодированием, они предоставляют превосходную защиту от нарушения синхронизации в сети, и они дают возможность снижения времени на переключение содержимого и времени на смену содержимого до минимума. Некоторые дополнительные преимущества этих способов включают в себя сглаживание скорости потоковой передачи, в том числе через смены от потоковой передачи одного содержимого на другое содержимое, и минимальное время на смену содержимого.
Варианты осуществления кодеров, декодеров и системы связи согласно аспектам настоящего изобретения также могут предусматривать секционирование потока данных на подпотоки, доставку подпотоков в приемники по различным трактам через сеть и прием одновременно различных подпотоков в приемнике, отправляемых от потенциально различных серверов. При использовании вместе с FEC-кодированием способы включают в себя доставку частей кодирования каждого исходного блока от потенциально различных серверов. Некоторые преимущества этих способов включают в себя улучшение времени на переключение содержимого, повышение устойчивости к сбоям сервера и сбоям в тракте, повышение устойчивости к дисковым сбоям, повышение устойчивости к потере и/или повреждению пакетов, улучшение масштабируемости общего решения по доставке потоковой передачи и улучшение хранения содержимого и баланса скорости потоковой передачи между серверами.
Варианты осуществления кодеров, декодеров и системы связи согласно аспектам настоящего изобретения также могут предусматривать комбинирование динамического перемежения с доставкой подпотоков. Например, с помощью динамического перемежения структура исходных блоков и FEC-кодирование могут быть определены, кодированный поток может быть секционирован на подпотоки, и комбинации подпотоков могут доставляться в приемники с использованием динамического перемежения, чтобы предоставлять отказоустойчивую систему доставки потоковой передачи, которая предоставляет минимальные времена на переключение содержимого. Преимущества этих комбинированных способов - это комбинация преимуществ динамического перемежения и доставки подпотоков.
Следующее подробное описание вместе с прилагаемыми чертежами предоставляет лучшее понимание характера и преимуществ настоящего изобретения.
Краткое описание чертежей
Фиг.1 - блок-схема системы связи согласно одному варианту осуществления настоящего изобретения.
Фиг.2 - схема, иллюстрирующая время на переключение содержимого.
Фиг.3A - чертеж, иллюстрирующий компоненты времени на переключение содержимого.
Фиг.3B - чертеж, иллюстрирующий использование CPU для FEC во время декодирования.
Фиг.4 - чертеж, иллюстрирующий структуру исходных блоков потока содержимого и представление соответствующей скорости передачи потока содержимого для каждого исходного блока.
Фиг.5 - чертеж, иллюстрирующий структуру кодированных блоков, соответствующих потоку содержимого по фиг.4.
Фиг.6 - чертеж, иллюстрирующий приемник и время на переключение содержимого, соответствующее базовому способу отправки.
Фиг.7 - чертеж, иллюстрирующий ленточный способ отправки потока.
Фиг.8 - чертеж, иллюстрирующий статическое перемежение согласно ленточному способу отправки потока.
Фиг.9 - чертеж, иллюстрирующий приемник и время на переключение содержимого, соответствующее способу отправки со статическим перемежением.
Фиг.10 - чертеж, иллюстрирующий способ отправки с динамическим перемежением, когда новый поток отправляется в приемник.
Фиг.11 - чертеж, иллюстрирующий время на переключение содержимого и период долгосрочной защиты, испытываемые на приемнике для способа отправки с динамическим перемежением.
Фиг.12 - чертеж, иллюстрирующий смену содержимого между двумя последовательными сегментами содержимого для способа отправки с динамическим перемежением.
Фиг.13 - чертеж, иллюстрирующий смену содержимого между двумя непоследовательными сегментами содержимого для способа отправки с динамическим перемежением.
Фиг.14 - чертеж, иллюстрирующий поток кодированного содержимого, распределяемый из центрального сервера в различные распределенные серверы, который должен использоваться в способе доставки на основе подпотоков.
Фиг.15 - чертеж, иллюстрирующий приемник, запрашивающий поток содержимого из различных распределенных серверов и принимающий потоки кодированного содержимого от некоторых из этих серверов в способе доставки на основе подпотоков.
Подробное описание
Варианты осуществления представляют новые способы динамического перемежения потоков, включая способы для динамического введения больших величин перемежения по мере того, как поток передается независимо от структуры исходных блоков, где передача осуществляется по сети и т.п. Варианты осуществления также представляют новые способы секционирования потока данных на подпотоки, доставки подпотоков в приемники по различным трактам через сеть и прием одновременно различных подпотоков в приемнике, отправляемых от потенциально различных серверов. При использовании вместе с FEC-кодированием способы включают в себя доставку частей кодирования каждого исходного блока от потенциально различных серверов. Варианты осуществления также представляют новые способы комбинирования динамического перемежения с доставкой подпотоков.
Далее предполагается, что сеть, переносящая данные, является сетью с коммутацией пакетов, чтобы упрощать описание в данном документе, с пониманием того, что специалисты в данной области техники могут легко видеть то, как процессы и способы, описанные в данном документе, могут применяться к другим типам сетей передачи, таких как сети с непрерывным потоком битов. Далее предполагается, что FEC-коды предоставляют защиту от потерянных пакетов или потерянных частичных данных в рамках пакетов, чтобы упрощать описание в данном документе, с пониманием того, что специалисты в данной области техники могут легко видеть то, как процессы и способы, описанные в данном документе, могут применяться к другим типам повреждений при передаче данных, таким как инвертирование битов. В этом описании предполагается, что данные, которые должны быть кодированы (исходные данные), разбиваются на "символы" равной длины, которые могут иметь любую длину (вплоть до одного бита минимум), но которые могут иметь различную длину для различных частей данных.
Символы могут переноситься по сети передачи данных в пакетах, при этом целое число символов явно переносится или подразумевается в каждом пакете. В некоторых случаях возможно, что исходный пакет не является кратным длине символа, в этом случае последний символ в пакете может усекаться. В этом случае, в целях FEC-кодирования неявно предполагается, что этот последний символ дополняется до конца фиксированной комбинацией битов, к примеру битов с нулевым значением, так что даже если эти биты не переносятся в пакете, приемник по-прежнему может заполнять этот последний усеченный символ до полного символа. В других вариантах осуществления фиксированная комбинация битов может быть помещена в пакет, тем самым фактически дополняя символы до длины, равной длине пакета. Размер символа зачастую может измеряться в битах, при этом символ имеет размер M битов и символ выбирается из алфавита в 2^M (два в степени M) символов. Недвоичные цифры также рассматриваются, но биты предпочтительны, поскольку они чаще всего используются.
FEC-коды, рассматриваемые для использования с потоковой передачей, типично являются систематическими FEC-кодами, т.е. исходные символы исходного блока включаются как часть кодирования исходного блока, и тем самым исходные символы передаются. Специалистам в данной области техники должно быть понятно, что способы и процессы, описанные в данном документе, применяются с равным успехом к FEC-кодам, которые не являются систематическими. Систематический FEC-кодер формирует из исходного блока исходных символов некоторое число исправляющих символов, причем комбинация, по меньшей мере, некоторых из исходных и исправляющих символов - это кодированные символы, которые отправляются по каналу, представляющему исходный блок. Некоторые FEC-коды полезны для эффективного формирования точно необходимого числа исправляющих символов, например "информационные аддитивные коды" или "фонтанные коды", и примеры этих кодов включают в себя "коды с цепной реакцией" и "коды с многостадийной цепной реакцией". Другие FEC-коды, такие как коды Рида-Соломона, фактически могут формировать только ограниченное число исправляющих символов для каждого исходного блока.
Предусмотрено множество других способов для переноса символов, и, хотя нижеприведенное описание использует способ пакетов для простоты, оно не имеет намерение быть ограничивающим или исчерпывающим. В контексте нижеприведенного описания термин "пакет" не имеет намерение быть ограниченным так, чтобы означать буквально то, что отправляется как одна единица данных. Наоборот, он имеет намерение включать в себя более широкое понятие задания логического группирования символов и частичных символов, которые могут отправляться или могут не отправляться как одна единица данных.
Имеются также формы повреждения данных, отличные от потери символов, к примеру, символы, которые при передаче изменяют свое значение или повреждаются другими способами, к которым способы, описанные ниже, применимы в равной степени. Таким образом, хотя нижеприведенное описание зачастую описывает потерю символов, способы с равным успехом применяются к другим типам повреждения и к другим типам FEC-кодов, помимо FEC-кодов со стиранием ошибок, таких как FEC-коды с коррекцией ошибок.
Пример FEC-кода
Фиг.1 - это блок-схема системы 100 связи, которая использует FEC-кодирование с цепной реакцией. В системе 100 связи входной файл 101 или входной поток 105 предоставляется в формирователь 110 входных символов. Формирователь 110 входных символов формирует последовательность из одного или более входных символов (IS(0), IS(1), IS(2), …) из входного файла или потока, при этом каждый входной символ имеет значение и позицию (обозначаемые на фиг.1 как целое число в скобках). Возможные значения для входных символов, т.е. их алфавит, - это типично алфавит из двух миллионов символов, так что каждый входной символ кодирует M битов входного файла. Значение M, в общем, определяется при помощи системы 100 связи, но система общего назначения может включать в себя ввод размера символа для формирователя 110 входных символов так, чтобы M могло варьироваться каждый раз. Вывод формирователя 110 входных символов предоставляется в кодер 115.
Формирователь 120 ключей формирует ключ для каждого выходного символа, который должен формироваться посредством кодера 115. Каждый ключ может быть сформирован согласно одному из способов, описанных в Luby I или в Shokrollahi I, или любому сравнимому способу, который обеспечивает то, что значительная часть ключей, формируемых для одного входного файла или блока данных в потоке, является уникальной, независимо от того, формируются ли они посредством этого или другого формирователя ключей. Например, формирователь 120 ключей может использовать комбинацию вывода счетчика 125, уникального идентификатора 130 потока и/или вывода случайного формирователя 135, чтобы формировать каждый ключ. Вывод формирователя 120 ключей предоставляется в кодер 115. В других примерах, например в некоторых приложениях потоковой передачи, набор ключей может быть фиксированным и повторно использованным для каждого блока данных в потоке. В типичном варианте осуществления число ключей, которые могут быть сформированы, диктуется посредством разрешения формирователя ключей, а не размера или другой характеристики входного файла или потока. Например, если, как ожидается, ввод составляет зачастую порядка тысячи символов или менее, ключевое разрешение может составлять 32 бита, обеспечивая до 4 миллиардов уникальных ключей. Один результат этих относительных чисел состоит в том, что кодер, который кодирует согласно ключам, может допускать формирование 4 миллиардов уникальных выходных символов для четырех тысяч символов ввода. На практике большинство систем связи не должны терять 0,999999 части символов, так что нигде не потребуется формировать порядка 4 миллиардов выходных символов, и поэтому число возможных ключей может трактоваться как фактически неограниченное и не обязательно должно повторяться, и вероятность, что два независимых выбора ключей захватят одинаковый ключ, является незначительно малой. Тем не менее, если это произошло по какой-либо причине, разрешение формирователя ключей может быть увеличено так, что процессы, которые используют ключи, могут действовать, как если бы ключи предоставлялись бесконечно.
Из каждого ключа I, предоставляемого посредством формирователя 120 ключей, кодер 115 формирует выходной символ со значением B(I) из входных символов, предоставляемых посредством формирователя входных символов.
Значение каждого выходного символа формируется на основе его ключа и некоторой функции от одного или более из входных символов, упоминаемых в данном документе как "ассоциированные входные символы" выходного символа или просто его "ассоциирования". Как правило, но не всегда, M является идентичным для входных символов и выходных символов, т.е. они оба кодируют идентичное число битов. В некоторых вариантах осуществления число K входных символов используется посредством кодера для того, чтобы выбирать ассоциирование. Если K не известно заранее, например, когда ввод - это поток, и K может варьироваться между каждым блоком в потоке, K может быть просто оценкой. Значение K также может использоваться посредством кодера 115 для того, чтобы выделять память под хранение входных символов.
Кодер 115 предоставляет выходные символы в передающий модуль 140, и формирователь 120 ключей предоставляет ключ каждого такого выходного символа в передающий модуль 140. Передающий модуль 140 передает выходные символы, и, в зависимости от используемого способа манипуляции, передающий модуль 140 также может передавать некоторые данные о ключах передаваемых выходных символов по каналу 145 в приемный модуль 150. Предполагается, что канал 145 является каналом со стиранием, но это необязательно для надлежащей работы системы 100 связи. Модули 140, 145 и 150 могут быть любыми подходящими аппаратными компонентами, программными компонентами, физическими средами или любой комбинацией вышеозначенного, до тех пор пока передающий модуль 140 выполнен с возможностью передавать выходные символы и все необходимые данные о своих ключах в канал 145, а приемный модуль 150 выполнен с возможностью принимать символы и потенциально некоторые данные о своих ключах от канала 145. Значение K, если используется для того, чтобы определять ассоциирование, может отправляться по каналу 145 или оно может задаваться заранее в соответствии с согласованием кодера 115 и декодера 155.
Канал 145 может быть каналом реального времени, таким как тракт через Интернет или широковещательная линия связи от телевизионного передающего устройства в телевизионный приемник, или телефонное соединение от одной точки к другой, либо канал 145 может быть каналом с памятью, таким как CD-ROM, накопитель, веб-узел и т.п. Канал 145 даже может быть комбинацией канала реального времени и канала с памятью, такой как канал, формируемый, когда один пользователь передает входной файл из персонального компьютера поставщику Интернет-услуг (ISP) по телефонной линии связи, входной файл сохраняется на веб-сервере и впоследствии передается получателю по Интернету.
Если канал 145 содержит пакетную сеть, система 100 связи может не иметь возможности допускать, что относительный порядок любых двух или больше пакетов сохраняется в пути через канал 145. Следовательно, ключ выходных символов определяется с использованием одной или более из схем манипуляции, описанных выше и не обязательно определяемых в соответствии с порядком, в котором выходные символы выходят из приемного модуля 150.
Приемный модуль 150 предоставляет выходные символы в декодер 155, и все данные, которые приемный модуль 150 принимает о ключах этих выходных символов, предоставляются в повторный формирователь 160 ключей. Повторный формирователь 160 ключей восстанавливает ключи для принимаемых выходных символов и предоставляет эти ключи в декодер 155. Декодер 155 использует ключи, предоставляемые посредством повторного формирователя 160 ключей, вместе с соответствующими выходными символами для того, чтобы восстанавливать входные символы (снова IS(0), IS(1), IS(2), …). Декодер 155 предоставляет восстановленные входные символы в повторный сборщик 165 входных файлов, который формирует копию 170 входного файла 101 или копию 175 входного потока 105.
Приложения потоковой передачи мультимедиа
При использовании в приложениях потоковой передачи мультимедиа исходные пакеты, формирующие исходный мультимедийный поток, иногда собираются в группы, называемые исходными блоками. Например, исходный блок может быть группой исходных пакетов, охватывающих фиксируемую продолжительность, и, например, код со стиранием Рида-Соломона может применяться независимо к этим исходным блокам, чтобы формировать исправляющие пакеты, которые отправляются вместе с первоначальными исходными пакетами исходного блока в приемники.
В передатчике исходный поток может непрерывно секционироваться на исходные блоки по мере того, как исходные пакеты поступают, и исправляющие пакеты формируются для каждого исходного блока и отправляются. Иногда предпочтительно минимизировать полную сквозную задержку, добавляемую посредством использования FEC-кодов, в частности, для приложений прямой или интерактивной потоковой передачи, и таким образом иногда предпочтительно, если общая разработка решения FEC такова, что исходные пакеты задерживаются как можно меньше в передатчике перед отправкой и все исходные и исправляющие пакеты для исходного блока отправляются с минимально возможной полной задержкой. Также предпочтительно, если скорость FEC-кодированного потока является максимально плавной, т.е. имеется минимально возможная изменчивость скорости FEC-кодированного потока или, по меньшей мере, нет усиления изменчивости, которая уже существует в первоначальном исходном потоке, поскольку это делает использование полосы пропускания FEC-кодированного потока более прогнозируемым и минимизирует воздействие на сеть и на другие возможно конкурирующие потоки. Также предпочтительно, если данные, отправляемые в пакетах для исходного блока, распределяются максимально равномерно по периоду, когда пакеты отправляются для этого исходного блока, поскольку это предоставляет лучшую защиту от потерь пакетов. Также предпочтительно, чтобы исходные блоки составлялись таким образом, чтобы минимизировать время на переключение содержимого и время на смену содержимого. Также предпочтительно, чтобы логика в приемнике была максимально простой.
В приемнике, если пакеты теряются или принимаются с ошибками (что может обнаруживаться и отвергаться, например, с использованием CRC-контроля), то при условии, что принято достаточно исправляющих пакетов, исправляющие пакеты могут использоваться для того, чтобы восстанавливать потерянные исходные пакеты.
В некоторых вариантах применения пакеты дополнительно подразделяются на символы, к которым применяется FEC-процесс. Для некоторых FEC-кодов, а именно кодов Рида-Соломона, время кодирования и декодирования становится непрактичным по мере того, как число кодированных символов на исходный блок возрастает, и зачастую имеется верхняя граница на общее число кодированных символов, которые могут быть сформированы на исходный блок. Поскольку символы размещаются в различных рабочих данных пакета, это задает целесообразную верхнюю границу на максимальную длину при кодировании исходного блока, а также, конечно, задает верхнюю границу на размер самого исходного блока.
Во многих приложениях, когда защита должна предоставляться в течение длительного периода времени или когда скорость потоковой передачи медиа является высокой, может быть предпочтительным предоставлять защиту для данных, которые превышают максимальный размер исходного блока. В этих случаях применение исходных блоков, которые короче максимального размера исходного блока, и последующее перемежение исходных пакетов из различных исходных блоков предоставляет решение, когда исходные пакеты от отдельного отправляемого исходного блока распределяются по большим периодам времени. В других приложениях, когда желательно небольшое время на переключение содержимого и когда структура исходных блоков определяется независимо от способов перемежения, желательно использовать меньшие исходные блоки и отправлять их последовательно первоначально, когда к содержимому осуществляется доступ посредством приемника, и затем увеличивать величину перемежения по мере того, как потоковая передача содержимого продолжается, чтобы распределять отправку исходных блоков по более длительным интервалам времени, чтобы повышать уровень защиты от потери пакетов. Другая задача заключается в том, чтобы иметь возможность декодировать исходные блоки достаточно быстро, чтобы не отставать от скорости исходной потоковой передачи, чтобы минимизировать время задержки на декодирование, вводимое посредством FEC-декодирования, и использовать только небольшую часть доступной мощности CPU в приемном устройстве в любой момент времени во время FEC-декодирования. Таким образом, желательно использовать перемежение исходных блоков, которое дает возможность распределения FEC-декодирования каждого исходного блока максимально равномерно во времени и минимизирует время задержки FEC-декодирования.
Различные варианты осуществления, описанные в данном документе, предоставляют одно или более из этих преимуществ.
Потоковая передача и FEC-коды
В целях предоставления защиты FEC исходного потока исходный поток может быть комбинацией одного или более логических потоков, примерами которых являются комбинация RTP-потока аудио и RTP-потока видео, комбинация MIKEY-потока и RTP-потока, комбинация двух или более видеопотоков и комбинация RTCP-трафика управления и RTP-потока. По мере того как исходный поток поступает в передатчик в формате, который, например, является потоком исходных битов, потоком исходных символов или потоком исходных пакетов, передатчик может буферизовать поток в исходные блоки и формировать исправляющий поток из исходных блоков. Передатчик может планировать и отправлять исходный поток и исправляющий поток, например, в пакетах, которые должны отправляться по пакетной сети. FEC-кодированный поток - это комбинированный исходный и исправляющий поток. FEC-приемник принимает FEC-кодированный поток, который, возможно, поврежден, например, вследствие потерь или инвертирования битов. FEC-приемник пытается восстанавливать первоначальные исходные блоки исходного потока и планирует и делает доступным первоначальный исходный поток в приемнике.
Во многих вариантах применения структура исходных блоков определяется вместе со структурой базовых потоков, к примеру GOP-структурой и/или структурой кадра видеопотока по стандарту H.264 AVC. В некоторых из этих вариантов применения структура исходных блоков определяется до и/или независимо от порядка отправки потока пакетов, причем порядок отправки потока пакетов может зависеть от того, когда и где к потоку осуществляется доступ посредством приемников, чтобы принимать поток. В этих вариантах применения предпочтительно, чтобы структура исходных блоков определялась таким образом, что каждый исходный блок содержит последовательный набор исходных пакетов из потока, чтобы обеспечивать минимизацию времени на переключение содержимого и времени на смену содержимого.
В некоторых вариантах применения формирование структуры исходных блоков и FEC-кодирование потока предпочтительно выполняются до отправки потока. Одна причина этого заключается в том, что поток может отправляться во множество приемников, и таким образом формирование структуры исходных блоков и FEC-кодирование выполняется один раз для всех приемников, что дает некоторые преимущества по масштабируемости.
Для приложения потоковой передачи предусмотрено несколько основных параметров, которые являются вводами в шаблон того, как использовать FEC-коды для того, чтобы защищать исходный поток, и несколько ключевых показателей, которые типично важно оптимизировать.
Один возможный ключевой входной параметр при разработке структуры исходных блоков - это длительность исходного блока. Длительность исходного блока для исходного блока может быть задана как продолжительность времени, в течение которого символы, сформированные из этого исходного блока, должны отправляться, если исходные блоки отправляются последовательно, т.е. неперемеженными, и если они отправляются на обычной скорости, т.е., по существу, на обычной скорости воспроизведения. Альтернативно, длительность исходного блока может быть задана так, чтобы быть временем воспроизведения видео, представляемого посредством исходного блока. В некоторых случаях эти два определения совпадают, но они могут не совпадать. Тем не менее, для простоты в описании в данном документе используется длительность исходного блока без указания того, какое определение является целевым, делая упрощающее допущение о том, что эти два определения совпадают. Специалистам в данной области техники должно быть ясно, что способы и процессы, описанные в данном документе, относятся к любому определению длительности исходного блока, даже если эти два определения не совпадают, и даже в некоторых случаях исходный блок может отправляться гораздо быстрее, чем его скорость воспроизведения. Кроме того, специалистам в данной области техники должно быть ясно, что имеются другие способы указания размера или времени воспроизведения исходного блока, к примеру, посредством указания числа символов в исходном блоке и размера символа для исходного блока.
Период защиты для исходного блока - это период времени, в течение которого исходный блок отправляется, независимо от того, перемежает или нет отправка исходных блоков отправку пакетов из некоторых исходных блоков с отправкой пакетов из других исходных блоков. Отметим, что период защиты, в общем, равен длительности исходного блока, если перемежение исходных блоков не используется, но период защиты может быть более длительным и иногда существенно более длительным, чем длительность исходного блока при использовании перемежения.
Величина защиты для исходного блока - это число исправляющих символов FEC, отправляемых для исходного блока, выраженное как часть или процент от числа исходных символов в исходном блоке. Например, если величина защиты составляет 20% и имеется 10000 исходных символов в исходном блоке, то имеется 2000 исправляющих символов, сформированных из исходного блока. Величина защиты является относительным понятием, т.е. величина защиты для одного исходного блока может варьироваться в зависимости от того, откуда отправляется исходный блок и куда отправляется исходный блок. Например, исходный блок может отправляться из первого сервера в другой сервер с величиной защиты 50%, тогда как этот же исходный блок может отправляться из второго сервера в приемник с величиной защиты 10%.
Как длительность исходного блока, так и величина защиты на исходный блок могут варьироваться от одного исходного блока до следующего. Например, когда исходный блок предпочтительно не охватывает определенные исходные пакеты в исходном потоке, к примеру, когда первый пакет - это последний пакет группы изображений (GOP) в видеопотоке MPEG2, а второй последовательный пакет - это первый пакет следующей GOP, то исходный блок может быть завершен после первого пакета, и новый исходный блок начат во втором пакете. Это дает возможность совмещения FEC-кодированного блока с блоком кодирования видео, что может иметь множество преимуществ, включая преимущество того, что время задержки приемника или время на переключение каналов могут быть минимизированы вследствие возможности минимизации комбинации буферизации видео и FEC-буферизации в приемнике. В других приложениях может быть предпочтительным по множеству причин всегда сохранять неизменную длительность исходного блока и/или размер исходного блока для каждого последовательного исходного блока. В некоторых из нижеприведенных описаний для простоты предполагается, что длительность исходного блока и величина защиты являются одинаковыми для каждого последующего исходного блока. Для специалистов в данной области техники должно быть понятным на основе этого раскрытия сущности изобретения, что это не является ограничением, поскольку можно легко определить на основе этого раскрытия, как применяются процессы и способы, описанные в данном документе, когда либо величина защиты, либо длительность исходного блока, либо и то, и другое варьируются от одного исходного блока к следующему и когда размеры исходного блока варьируются от одного к следующему.
Для упрощения некоторых из последующих пояснений, иногда предполагается, что исходные символы первоначального потока поступают на установившейся скорости в передатчик, который должен выполнять формирование исходных блоков и FEC-кодирование, и что как только FEC-приемник сначала делает исходные символы доступными в приемнике, то последующие исходные символы делаются доступными посредством FEC-приемника на той же установившейся скорости, при условии, что в первом исходном блоке, из которого принимается исходный символ, нет потери исходных символов, и что в каждом последующем исходном блоке потеря кодированных символов составляет, самое большее, максимум, возможный для того, чтобы обеспечивать успешное FEC-декодирование. Это упрощающее допущение не присутствует при работе или разработке процессов и описанных ниже способов, и нет намерения ограничивать эти процессы таким допущением каким-либо образом, а оно вводится просто как средство для упрощения некоторых из описаний свойств процессов и способов. Например, для потоков с переменной скоростью соответствующее условие состоит в том, что исходные символы делаются доступными посредством FEC-приемника на той же или практически той же скорости, на которой они поступают в передатчик. В некоторых вариантах применения предпочтительно доставлять декодированные исходные символы в приемнике в видеопроигрыватель как можно быстрее, чтобы минимизировать время на переключение содержимого, и в таких случаях исходные символы могут доставляться в пакетах исходных блоков. В некоторых вариантах применения желательно разделять этапы формирования исходных блоков, FEC-кодирования и отправки на два или более различных этапов. Например, как описано ниже, формирование исходных блоков и FEC-кодирование могут выполняться в одном сервере, и кодированный поток затем секционируется на подпотоки, а затем подпотоки отправляются в один или более распределенных серверов и кэшируются локально, и после этого некоторые или все из подпотоков отправляются в приемник от некоторых из одного или более распределенных серверов.
Некоторые ключевые важные для минимизации показатели включают в себя время задержки в передатчике, которое является временем задержки, вводимой передатчиком. Минимизация времени задержки в передатчике желательна для некоторых приложений, таких как прямая потоковая передача видео или интерактивные приложения, такие как видеоконференц-связь. Один аспект общей разработки для передатчика, помогающей минимизировать время задержки в передатчике, состоит в том, чтобы отправлять кодированные символы для начального исходного блока или блоков для потока в приемник в последовательном порядке. Другие аспекты разработки, которые минимизируют время задержки в передатчике, описываются ниже.
Другой важный показатель - это время на переключение содержимого. Как показано на фиг.2, это время между моментом, когда приемник присоединяется или запрашивает поток, до момента, когда FEC-приемник первый раз делает доступными исходные символы из потока. В общем, желательно минимизировать время на переключение содержимого, поскольку это минимизирует время между тем, когда к потоку присоединяется приемник и когда поток первый раз становится доступным в приемнике, например, для воспроизведения видеопотока. Один важный аспект минимизации времени на переключение содержимого заключается в том, чтобы передатчик сохранял первоначальный порядок отправки кодированных символов для начальных исходных блоков, но, как описано ниже, есть много других важных аспектов разработки, которые оказывают большое влияние на время переключения содержимого.
Время на переключение содержимого типично содержит несколько компонентов. Пример этих компонентов для потока, который секционируется на последовательные исходные блоки, показан на фиг.3A и 3B, где перемежение не используется. Фиг.3A показывает один исходный блок на период защиты, и пример показывает случай, когда приемник присоединяется к потоку в начале исходного блока. Два компонента времени на переключение содержимого в этом примере - это период защиты и время задержки на FEC-декодирование. Период защиты приемника для исходного блока - это время, в течение которого приемник буферизует принимаемые кодированные символы из исходного блока. Отметим, что период защиты передатчика и период защиты приемника являются идентичными, если канал между передатчиком и приемником не имеет отклонения с точки зрения интервала времени, которое занимает то, чтобы каждый бит, байт, символ или пакет переместился от передатчика в приемник. Таким образом, на практике период защиты передатчика может отличаться от периода защиты приемника для одного и того же исходного блока вследствие изменений синхронизации в сети при доставке.
Для упрощения приводимых здесь иллюстраций предполагается, что период защиты передатчика и период защиты приемника являются идентичными для каждого исходного блока (и "период защиты" используется синонимично для периода защиты передатчика и периода защиты приемника), но это не всегда имеет место. Другими словами, имеется допущение о том, что время доставки в сети является одинаковым для всех данных. Специалисты в данной области техники, после прочтения этого раскрытия сущности, могут производить необходимые изменения в способах и устройствах, описанных в данном документе, чтобы учитывать различия периодов защиты передатчика и приемника вследствие колебаний времени доставки в сети.
Компонент периода защиты времени на переключение содержимого является неисключаемым, поскольку даже если в первом исходном блоке нет потери каких-либо исходных символов, по-прежнему требуется задерживать задание исходных символов доступными в течение, по меньшей мере, периода защиты, чтобы обеспечивать плавную доставку исходных символов по всем последующим исходным символам, когда есть потери кодированных символов в последующих исходных блоках. В течение периода защиты часть, или большая часть, или все FEC-декодирование исходного блока может осуществляться одновременно с приемом кодированных символов. В конце периода защиты может быть дополнительное FEC-декодирование, которое осуществляется до того, как первый исходный символ исходного блока доступен из FEC-приемника, и этот период времени помечается как время задержки на FEC-декодирование на фиг.3A. Помимо этого, даже после того, как первый исходный символ доступен, может быть дополнительное FEC-декодирование, которое осуществляется до того, как второй и последующие исходные символы исходного блока доступны. Для простоты это дополнительное FEC-декодирование не показано на фиг.3A, и в этом примере предполагается, что имеется достаточно доступных ресурсов CPU для того, чтобы декодировать все исходные символы после первого на достаточно высокой скорости.
Другой возможный компонент времени на переключение содержимого может быть временем между тем, когда приемник запрашивается, чтобы присоединяться к потоку, и когда первые пакеты для того потока поступают в приемник. Эта величина времени может быть переменной и зависеть от времени двустороннего распространения между приемником и одним или более передатчиками пакетов для потока. Этот компонент времени на переключение содержимого не описан подробно в данном документе, но специалистам в данной области техники должно быть ясно, что иногда это может быть важным вкладом во время переключения содержимого, который должен приниматься во внимание, и что способы и процессы, описанные в данном документе, могут легко модифицироваться, чтобы принимать во внимание этот потенциальный вклад во время переключения содержимого.
Фиг.3B показывает две потенциальные кривые использования CPU для FEC-декодирования, которые могут соответствовать примеру, показанному на фиг.3A. Для одной из двух кривых, показанных на фиг.3B, использование CPU, применяемое для FEC-декодирования, является одинаковым в каждой точке во времени, т.е. использование CPU распределяется равномерно. Это желательная кривая использования CPU, поскольку она очевидно использует одинаковую величину ресурсов CPU в каждой точке во времени и минимизирует максимальные ресурсы CPU при условии, что одинаковая величина полных ресурсов CPU требуется для того, чтобы декодировать весь исходный блок. Для другой из двух кривых, показанных на фиг.3B, использование CPU, применяемого для FEC-декодирования, не является одинаковым в каждой точке во времени, и в частности, использование CPU при и сразу после окончания приема кодированных символов для исходного блока значительно выше, чем в другие моменты времени. Это нежелательная кривая использования CPU, поскольку использование ресурсов CPU дает выброс в определенных точках во времени, которые могут быть точками во времени, когда другие процессы, такие как видеопроигрыватель, также отправляют запросы в CPU и тем самым повышают возможность возникновения, например, сбоя при воспроизведении видеопотока. Таким образом, разработка решения FEC по защите потоков состоит в том, чтобы предоставлять решение, в котором FEC-декодер использует CPU максимально плавно и равномерно во времени. В качестве примера, расчетные критерии могут заключаться в том, что максимальное использование CPU в любой момент времени в процессе FEC-декодирования при наихудшем случае потери кодированных символов находится ниже определенного порога, к примеру, использует самое большее 10% мощности CPU в каждом интервале 100 миллисекунд.
В некоторых приложениях потоковой передачи, когда приемник присоединяется к потоку в середине исходного блока, время на переключение содержимого может быть столь же малым, как длительность исходного блока плюс время задержки на декодирование, когда нет потери исходных символов из того первого частичного исходного блока, пока первоначальный порядок отправки и скорость доставки исходных пакетов сохраняются на начальном уровне передатчиком. В других приложениях потоковой передачи видеопередатчик всегда начинает отправку потока в приемник с начала GOP, причем предпочтительно начало исходного блока совмещается с началом GOP. Таким образом, чтобы минимизировать задержку переключения содержимого, желательно, чтобы передатчик сохранял первоначальный порядок отправки исходных символов для начальных исходных блоков.
Решение по потоковой передаче FEC также может использоваться для того, чтобы минимизировать сквозное время задержки на FEC, которое для приложения прямой потоковой передачи составляет полное время задержки для сценария наихудшего случая, вводимое за счет использования FEC, между моментом, когда исходный пакет готов к потоковой передаче в передатчике до применения FEC-кодирования, и моментом, когда он доступен для воспроизведения в приемнике, после применения FEC-декодирования. Для других типов приложений потоковой передачи, таких как потоковая передача по запросу или потоковая передача содержимого по списку воспроизведения, сквозное время задержки на FEC не является основной проблемой.
В приложениях потоковой передачи всех типов важно минимизировать время на переключение содержимого и время на смену содержимого. Вместе с тем важно минимизировать скорость отправки потока, т.е. ограничивать скорость отправки так, чтобы она всегда немного превышала скорость потоковой передачи содержимого, в том числе в ходе переключения содержимого и смен содержимого.
Решение по потоковой передаче FEC также может использоваться для того, чтобы минимизировать колебания скорости отправки при использовании FEC. Одно преимущество этого заключается в том, что в пакетных сетях потоки с колеблющейся скоростью отправки более подвержены потере пакетов вследствие перегрузки или переполнения буфера, когда пики скорости отправки потока совпадают с пиками другого трафика в точках сети с ограниченной пропускной способностью. Как минимум, колебания скорости FEC-кодированного потока должны быть не хуже колебаний скорости первоначального исходного потока, и предпочтительно, чем большая защита FEC применяется к первоначальному исходному потоку, тем колебания скорости FEC-кодированного потока становятся меньше. Как частный случай, если первоначальный поток отправляется на постоянной скорости, предпочтительно, чтобы FEC-кодированный поток отправлялся на скорости, которая максимально возможно близка к постоянной.
Свойство, состоящее в том, что время, когда последний кодированный символ для каждого последующего исходного блока принимается, распределяется во времени максимально возможно равномерно, является желательным свойством. Время, когда последний кодированный символ принимается для исходного блока, является временем, когда вся информация для декодирования исходного блока доступна FEC-декодеру, и типично является временем в условиях потерь по сценарию наихудшего случая, которое FEC-декодер должен работать с наибольшей интенсивностью, чтобы завершать декодирование в рамках заданного бюджета времени задержки на декодирование. Таким образом, равномерное распределение приема последнего кодированного символа для исходных блоков дает возможность более плавного использования CPU для FEC-декодирования.
Решение по потоковой передаче FEC должно предоставлять максимально простую логику в FEC-приемнике. Это важно во многих контекстах, поскольку FEC-приемник может быть встроен в устройство с ограниченными вычислительными характеристиками, характеристиками по памяти и другими ресурсами. Кроме того, в некоторых случаях может быть значительная потеря или повреждение символов при передаче, и, таким образом, FEC-приемнику, вероятно, придется восстанавливаться после сценариев фатальной потери или повреждений, при этом, когда условия улучшаются, есть небольшой или вообще отсутствует контекст, чтобы понимать, с какого момента в потоке продолжается прием. Таким образом, чем проще и более отказоустойчива логика в FEC-приемнике, тем быстрее и надежнее FEC-приемник сможет начинать восстановление и задание снова доступными исходных символов исходного потока из приема FEC-кодированного потока.
Исправляющие пакеты для исходного блока могут отправляться до, после или смешанными с исходными пакетами для исходного блока, и, как поясняется в данном документе, различные стратегии имеют свои преимущества.
Некоторые из всех желательных признаков решения по потоковой передаче FEC включают в себя:
1. Небольшое время на переключение содержимого.
2. Небольшое время на смену содержимого.
3. Скорость отправки потоков всегда должна быть ограничена, т.е. немного превышать скорость передачи потока содержимого.
4. Скорость отправки потоков должна быть плавной и должна быть, по меньшей мере, настолько плавной, что и скорость передачи потока содержимого.
5. Когда FEC-кодирование используется, формирование исходных блоков и FEC-кодирование могут выполняться для потока и идентичный кодированный поток может отправляться в возможно различные моменты времени во множество приемников.
6. Когда FEC-кодирование используется, защита от потери пакетов должна интенсивно использовать небольшую длительность исходного блока с минимальными необходимыми величинами защиты, в частности, когда потери являются немного пульсирующими по характеру.
7. Когда FEC-кодирование используется, исходные блоки должны содержать смежные части потока.
8. При FEC-кодировании для приложений прямой потоковой передачи сквозное время задержки на FEC должно быть небольшим.
9. Когда FEC-кодирование используется, FEC-декодирование должно плавно распределять использование CPU.
Основная отправка FEC-кодированного потока
В этом разделе описываются основные способы и процессы для передатчика, чтобы распределять по времени отправку пакетов потока, который может быть FEC-кодирован. Пусть k - число исходных символов в исходном блоке, T - длительность исходного блока для исходного блока, p - величина защиты, выражаемой как доля, и, таким образом, p*k исправляющих символов должно отправляться для исходного блока. Значения k, T и p могут определяться динамически, по мере того как каждый исходный блок формируется, и, таким образом, значения k и T для исходного блока могут быть известны процессу формирования исходных блоков, только когда большинство или все исходные символы для того исходного блока поступили в процесс, и значение p может быть определено после того, как все исходные символы для исходного блока поступили в процесс формирования исходных блоков, или посредством отдельного процесса. Кроме того, процесс формирования исходных блоков может варьировать размер символа для различных исходных блоков. Таким образом, многие или все эти параметры для конкретного исходного блока могут быть хорошо известны процессу формирования исходных блоков при приеме данных для этого исходного блока.
Следующий процесс описывает основной передатчик, который не использует перемежение. Для простоты для этого основного передатчика предполагается, что процесс формирования исходных блоков уже применялся к потоку, и что он секционирован на последовательные исходные блоки, при этом каждый такой исходный блок содержит k исходных символов и с длительностью исходного блока в T секунд, и что для каждого такого исходного блока p*k исправляющих символов уже сформированы.
Когда приемник запрашивает поток, начинающийся в конкретном исходном блоке (или поток проактивно отправляется с явным запросом на начало от приемника), основной передатчик начинает отправку (1+p)*k кодированных символов для запрашиваемого исходного блока за период в T секунд и после этого отправляет кодированные символы для следующего исходного блока после запрашиваемого исходного блока и т.д.
Основной передатчик имеет следующие свойства:
1. Период защиты равен T, что равно длительности исходного блока.
2. Символы, отправляемые для исходного блока, распределяются равномерно за период T секунд. Это подразумевает, что уровень защиты, предоставляемой против потерь, когда есть перебой в передаче пакета фиксированной длительности, не зависит от того, когда перебой возникает во время передачи символов, что желательно.
3. Передатчик не вводит колебания в общую скорость отправки символов. В частности, если первоначальная скорость отправки исходных символов является постоянной, то скорость отправки всех символов по-прежнему является постоянной, а если первоначальная скорость поступления исходных символов в передатчике является переменной, то, по меньшей мере, постоянная скорость отправки символов на исходный блок гасит колебания. Это является желательным свойством.
4. Время на переключение содержимого может составлять всего T. Это подразумевает минимальную буферизацию (1+p)*k символов (при условии, что все исходные блоки содержат k исходных символов), что является минимально возможным в течение данного периода защиты и таким образом желательно.
Одно свойство, которое имеет основной передатчик, заключается в том, что время на переключение содержимого составляет, по меньшей мере, время в течение периода защиты, и период защиты напрямую связан с качеством защиты от потерь при передаче пакетов. Таким образом, иногда должен быть компромисс между периодом защиты и временем на переключение содержимого. Например, желательно иметь время на переключение содержимого менее одной секунды, при этом также желательно иметь периоды защиты, которые охватывают несколько секунд, чтобы предоставлять лучшую защиту от временных перебоев в работе сети или других типов проблем неустойчивости сети, которые вызывают потерю при передаче пакетов, которая может длиться порядка десятков или сотен миллисекунд, а в некоторых случаях и целых секунд, при этом одновременно используя достаточно небольшую величину защиты, к примеру 10%. Должно быть желательным иметь возможность определять период защиты, который гораздо больше, чем время на переключение содержимого, и это одно из многих преимуществ, которые предоставляют способы перемежения, описанные в следующем разделе.
Перемежение потоков
Этот раздел описывает новые способы и процессы обработки потока данных и применения различных временных задержек к различным частям потока данных таким образом, чтобы некоторые части задерживались больше в процессе отправки, чем другие части. Одним из более важных аспектов этих способов и процессов является средство для динамического регулирования величин задержки, вызываемой в различных частях потока по мере того, как поток данных отправляется.
Зачастую предпочтительно совмещать исходные блоки со структурой группы изображений (GOP) или другой структурой кадра видеопотока, чтобы минимизировать время на переключение содержимого и предоставлять лучшую защиту потока. В некоторых приложениях желательно, чтобы процесс перемежения мог осуществляться независимо от процесса формирования исходных блоков, возможно, выполняемого в другое время или возможно выполняемого в другом месте. В некоторых случаях, возможно, желателен процесс перемежения, например, чтобы распределять ошибки пакетной передачи более равномерно по потоку, даже если процесс формирования исходных блоков не используется, например, поскольку не используется FEC-кодирование. Способы, описанные в данном документе, применяются, даже когда формирование исходных блоков и FEC-кодирование не используется, как должны признавать специалисты в данной области техники.
В некоторых случаях могут быть преимущества предоставления возможности передатчику перемежать отправку символов из различных исходных блоков так, чтобы символы для каждого исходного блока могли распределяться по более длительному периоду защиты, чем длительность исходного блока. Одна причина для этого состоит в том, что предоставляется лучшая защита от потерь с временной зависимостью (к примеру, потерь пакетов), т.е. меньшая величина защиты требуется для того, чтобы предоставлять защиту от потерь пакетов фиксированной длительности, поскольку период защиты для исходного блока возрастает. Хотя длительность исходного блока может составлять t секунд, требуемый период защиты для исходного блока может составлять p секунд, где p>>t. Другие желательные свойства передатчика, который использует перемежение, включают в себя: (1) исходные пакеты отправляются в своем первоначальном порядке в рамках исходного блока, и (2) время, когда последний кодированный символ для каждого последующего исходного блока принимается, распределяется во времени максимально возможно равномерно.
При использовании FEC-кодирования вводятся способы, которые статически перемежают отправку кодированных символов для исходных блоков, и вводятся способы, которые динамически регулируют величину перемежения по мере того, как поток отправляется, типично с небольшим перемежением или без перемежения в начале отправки потока и тем самым с периодами защиты, приблизительно равными длительности исходного блока, и плавно введя все большую величину перемежения по мере того, как продолжается отправка потока, и тем самым периоды защиты возрастают так, чтобы быть гораздо более продолжительными, чем длительность исходного блока. Это дает возможность минимизации времени на переключение содержимого в приемнике, при этом в то же время все больше защиты от потерь пакетов или повреждения достигается по мере того, как продолжается отправка. Другое преимущество описанных способов состоит в возможности постепенно защищать от постоянно возрастающего нарушения синхронизации в сети по мере того, как продолжается отправка потока.
Чтобы упрощать нижеприведенное описание, предполагается, что процессы формирования исходных блоков и FEC-кодирования осуществляются до отправки потока. Это не ограничение способов, поскольку специалисты в данной области техники должны признавать, что процессы формирования исходных блоков и выполнения FEC-кодирования для этих исходных блоков и отправки потоков, описанные ниже, могут выполняться одновременно, и в некоторых случаях это является предпочтительным. Кроме того, для некоторых приложений формирование исходных блоков, процесс FEC-кодирования и способы, описанные ниже для перемежаемой отправки потоков, могут быть динамически взаимозависимыми, т.е. то, как исходные блоки формируются и FEC-кодируются, может зависеть в некоторых случаях от стратегии отправки потока.
Ленточный способ отправки потока
Чтобы описывать новые способы перемежения, полезно вводить следующий ленточный способ отправки потока. Фиг.4 - это иллюстративный чертеж потока содержимого, для которого уже определена структура исходных блоков. Для каждого исходного блока 405(1), 405(2), …, ширина 410(1), 410(2), …, показывает длительность воспроизведения содержимого этого исходного блока, а высота каждого исходного блока 415(1), 415(2) показывает среднюю скорость воспроизведения каждого исходного блока потока содержимого, причем в этом примере различные исходные блоки имеют различные скорости воспроизведения.
Фиг.5 показывает соответствующую структуру кодированных блоков, соответствующую фиг.4, т.е. FEC-кодирование применено к каждому исходному блоку, чтобы формировать дополнительные исправляющие данные 510(1), 510(2), …, для каждого исходного блока, чтобы формировать кодированные блоки. Высота 515(1), 515(2), …, для 510(1), 510(2), …, указывает объем дополнительных исправляющих данных, формируемых для каждого исходного блока в каждом кодированном блоке, т.е. если кодированный блок отправляется в течение такой же длительности, как соответствующий исходный блок, то высота указывает среднюю скорость отправки кодированного исходного блока. Этот чертеж является только иллюстративным, а не ограничивающим, поскольку, например, величина исправляющих данных, сформированных для каждого кодированного блока, может значительно превышать величину, отправляемую для каждого кодированного блока, и величина, отправляемая для каждого кодированного блока, может варьироваться от приемника к приемнику. Кроме того, фиг.5 не имеет намерения предлагать представление упорядочения исходных и исправляющих символов в рамках кодированного исходного блока.
Фиг.6 - это иллюстративный чертеж, показывающий время на переключение содержимого, испытываемое на приемнике, соответствующего базовому способу отправки. Некоторые из компонентов времени 605 на переключение содержимого содержат время 610, которое у приемника требует прием достаточных данных из первого кодированного блока потока для того, чтобы декодировать первый исходный блок, время, которое у приемника требует декодирование первого исходного блока из принимаемых частей первого кодированного блока 620, и время 630 буфера резервирования, зарезервированного для поглощения нарушения синхронизации в сети, изменений длительности исходного блока и времени декодирования исходных блоков из частей принимаемых кодированных блоков во время приема потока.
Описан ленточный способ отправки потоков, но специалистам в данной области техники должно быть ясно, что есть много эквивалентных описаний, формирующих аналогичные способы, и разновидностей этого описания, формирующих разновидности способов, описанных здесь. Фиг.7 показывает пример ленточного способа, соответствующего структуре кодированных блоков, показанной на фиг.5. В ленточном способе отправка потока данных указывается посредством представления потока, который должен отправляться, как лента 705, где каждая позиция 710 вдоль X-оси ленты соответствует различной точке во времени в структуре кодированных блоков и где высота ленты всегда неизменна, к примеру, номинально высотой в единицу независимо от скорости кодированного исходного блока в этой точке времени в ленте. Отправка потока, представляемого посредством ленты, может указываться посредством перемещающейся линии 720(1), 720(2), которая идет сверху ленты 725 к низу ленты 730. В одном представлении перемещение линии 720(1), 720(2) во времени представляет порядок отправки данных из кодированных блоков потока. Каждая точка в ленте 740(1), 740(2), …, представляет фрагмент потоковых данных, который должен отправляться, например, каждая точка может представлять пакет кодированных символов для кодированного блока, или каждая точка может представлять отдельный кодированный символ для кодированного блока. Точки, которые находятся внутри области, соответствующей кодированному блоку 750(1), 750(2), …, представляют данные, которые ассоциированы с этим кодированным блоком.
Процесс отправки согласно ленточному способу отправки потоков представляется посредством перемещения линии 720(1), 720(2) через ленту во времени по мере того, как поток отправляется, и каждый раз, когда линия проходит через точку, данные потока, соответствующие этой точке, отправляются. Фиг.7 показывает линию в два различных момента времени в процессе отправки, где линия 720(1) является своей конфигурацией в первый момент времени, когда и линия 720(2) является своей конфигурацией во второй момент времени. Таким образом, процесс отправки отправляет все данные, ассоциированные с точками внутри области, ограниченной посредством 720(1), 720(2), 725 и 730, в течение интервала времени между первым моментом времени и вторым моментом времени. Распределение точек в рамках каждого кодированного блока предпочтительно равномерно распределяется в рамках ленточной области для этого кодированного блока согласно их весовому коэффициенту, к примеру распределяется произвольно или распределяется псевдослучайно, или распределяется детерминированно посредством процесса, который обеспечивает то, что точки распределяются равномерно согласно весовому коэффициенту каждой точки, где весовой коэффициент точки - это объем данных, представляемый посредством этой точки.
Как описано выше, линия 720 является прямой, но специалистам в данной области техники должно быть ясно, что есть много вариантов, к примеру линия может быть изогнутой или содержать последовательность последовательных линейных сегментов, и линия может изменять свою форму по мере того, как она перемещается в ходе процесса отправки. Также имеются другие варианты способа ленточной отправки, в том числе представление ленты так, что лента не имеет одинаковую высоту, а вместо этого ее высота варьируется согласно скорости потока в этой позиции 710 ленты.
Предусмотрены различные способы задания перемещения линии по ленте в ходе процесса отправки, как подробнее описано ниже.
Способы статического перемежения
Ленточный способ отправки потоков может использоваться для того, чтобы достигать статического перемежения любой глубины для любого типа потока содержимого или потока кодированного содержимого независимо от того, используется или нет FEC-кодирование и используется или нет структура исходных блоков. В качестве иллюстрации предполагается, что структура исходных блоков уже задана и что используется FEC-кодирование.
Один способ достижения статического перемежения данной величины с использованием ленточного способа отправки потоков описывается в качестве примера со ссылкой на фиг.7. В этом примере каждый кодированный блок перемежается на количество времени D с другими соседними кодированными блоками, т.е. глубина перемежения равна D. В этом примере при запрашивании потока приемник передает позицию X и значение для D. Затем процесс отправки в передатчике описывается посредством конфигурирования линии 720 так, что первоначально линия 720 пересекает нижнюю часть ленты 730 в позиции X-D, первоначально линия 720 пересекает верхнюю часть ленты 725 в позиции X, и затем процесс отправки перемещает линию 720 вперед во времени на такой же скорости, как скорость воспроизведения потока, т.е. во время t после начала процесса отправки линия 720 переместилась таким образом, что она пересекает нижнюю часть ленты 730 в позиции X-D+t, и линия 720 пересекает верхнюю часть ленты 725 в позиции X+t.
В этом описании способа статического перемежения, если способ используется для отправки нового запрашиваемого потока в приемник, то является предпочтительным, чтобы X находилось в позиции в потоке, где воспроизведение должно начинаться в приемнике, к примеру, X - это позиция начала кодированного блока, или X - это позиция начала GOP в видеопотоке, и начало кодированного блока совмещено с началом GOP. Кроме того, в этих случаях для передатчика предпочтительно вообще не отправлять данные до позиции X вдоль ленты в приемник, поскольку, в общем, приемник должен принимать только часть кодированных блоков и наиболее вероятно недостаточно полностью декодировать частично принимаемые кодированные блоки.
Фиг.8 - это иллюстративный чертеж, иллюстрирующий форму отправляемого потока, когда передатчик использует вышеописанный способ статического перемежения. В этом случае способ статического перемежения применяется к ленте, показанной на фиг.7, которая соответствует кодированному потоку, показанному на фиг.5. В этом примере приемник указывает значение X как позицию начала первого кодированного блока 750(1) на фиг.7, и, таким образом, в этом примере нет данных, которые должны отправляться, т.е. вдоль ленты до позиции X. В этом примере приемник также указывает значение для D, которое может быть таким значением, как 10 секунд. Результирующий поток, который отправляется посредством передатчика согласно этому процессу, выглядит так, как показано на фиг.8, где область 850(1), 850(2), …, является такой же, как область 405(1) плюс 510(1), 405(2) плюс 510(2), …, по фиг.5 соответственно. Отметим, что скорость отправки, как показано на фиг.8, является сглаженной версией скорости исходного содержимого, как показано на фиг.5.
Фиг.9 - это иллюстративный чертеж, показывающий время на переключение содержимого, испытываемое приемником, соответственно способу статического перемежения, описанному выше. Некоторые из компонентов времени 905 на переключение содержимого содержат время 910, которое приемнику требуется, чтобы принимать достаточно из первого кодированного блока потока для декодирования первого исходного блока, которое является суммой длительности исходного блока и глубины перемежения D, время, которое требуется приемнику, чтобы декодировать первый исходный блок из принимаемых частей первого кодированного блока 920, и время 930 буфера резервирования, зарезервированного для ожидаемой задержки из-за нарушения синхронизации в сети, изменений длительности исходного блока и времени декодирования исходных блоков из частей принимаемых кодированных блоков во время приема потока. Отметим, что, поскольку период защиты, который в данном случае составляет длительность исходного блока плюс глубина перемежения D, может быть гораздо большим, чем длительность исходного блока, время 905 на переключение содержимого может быть гораздо большим, чем длительность исходного блока, при использовании этого описанного способа.
Способы динамического перемежения
Ленточный способ отправки потоков может использоваться для того, чтобы достигать динамического перемежения в любом темпе любой глубины перемежения для любого типа потока содержимого или потока кодированного содержимого независимо от того, используется или нет FEC-кодирование и используется или нет структура исходных блоков. В качестве иллюстрации предполагается, что структура исходных блоков уже задана и что используется FEC-кодирование.
Один способ достижения динамического перемежения, начинающегося при отсутствии перемежения и идущего вплоть до данной глубины перемежения с использованием ленточного способа отправки потоков, описан в качестве примера со ссылкой на фиг.7. В типичном использовании этого способа первый кодированный блок отправляется с небольшим перемежением, и затем постепенно во времени последующие кодированные блоки плавно перемежаются все больше до тех пор, пока глубина перемежения D не достигается с другими соседними кодированными блоками. Другое использование этого способа также раскрывается ниже, и как понятно специалистам в данной области техники, также имеется множество других разновидностей. При этом примерном способе выражения параметров для способа, при запрашивании потока приемник передает начальную верхнюю позицию UL для линии 720, начальную нижнюю позицию LI для линии 720, конечную верхнюю позицию UF для линии 720, конечную нижнюю позицию LF для линии 720 и значение времени T. Для простоты далее предполагается, что UF≥UI, LF≥LI, UF≥LF, UI≥LI, T≥0. Как правило, предпочтительно иметь UF≥UI+T и LF≥LI+T, чтобы обеспечивать то, что данные в приемнике всегда доступны при необходимости. Как поясняется в примерах ниже, эти значения для UF, UI, LF, LI и T могут давать возможность плавного увеличения буфера резервирования содержимого в приемнике, поскольку перемежение динамически регулируется.
Способ отправки в передатчике реализует ленточный способ с использованием параметров LI, UI, LF, UF и T следующим образом. Во-первых, линия 720 по фиг.7 первоначально сконфигурирована во время отправки t=0 так, что первоначально линия 720 пересекает нижнюю часть ленты 730 в позиции LI, и первоначально линия 720 пересекает верхнюю часть ленты 725 в позиции UI, затем в течение времени отправки от t=0 до t=T линия 720 перемещается по ленте так, что во время t линия 720 пересекает нижнюю часть ленты 730 в позиции t*(LF-LI)/T+LI, и во время t линия 720 пересекает верхнюю часть ленты 725 в позиции t*(UF-UI)/T+UI. Затем, для всех времен отправки t>T, линия 720 перемещается через ленту так, что во время t линия 720 пересекает нижнюю часть ленты 730 в позиции t-T+LF, и во время t линия 720 пересекает верхнюю часть ленты 725 в позиции t-T+UF, т.е. для t>T перемежение является статическим, причем используется глубина перемежения D=UF-LF.
Способы динамического перемежения для новых запрашиваемых потоков
Одно примерное применение способа динамического перемежения состоит в том, чтобы отправлять новый запрашиваемый поток в приемник. В качестве примера, как показано на фиг.10, все начальные значения могут быть заданы равными одинаковому значению I=UI=LI, т.е. первоначально нет перемежения, и для позиции S, в которой приемник должен начинать воспроизведение потока содержимого, удовлетворяется S=I. Это обеспечивает то, что приемник отправил всю ленту содержимого с позиции S и далее. Как показано на фиг.10, предпочтительно S=UI=LI, где S - это позиция в потоке содержимого, в которой он может воспроизводиться, к примеру, S - это начало кодированного блока, начало которого совмещено с началом GOP. Кроме того, преимущественно, что T≤LF-S. Это обеспечивает то, что если приемник воспроизводит содержимое на скорости содержимого, то отправка содержимого выполняется на скорости, которая, по меньшей мере, не меньше скорости воспроизведения содержимого в приемнике, и время буфера резервирования R=LF-S-T секунд плавно увеличивается и длится по мере того, как статическое перемежение достигается во время отправки T с начала отправки в приемник, причем буфер резервирования может поглощать нарушение синхронизации в сети, варьирование длительностей исходных блоков и времени декодирования. Величина перемежения плавно возрастает от отсутствия перемежения до D=UF-LF секунд перемежения.
В качестве конкретного примера способа динамического перемежения предположим, что приемник осуществляет доступ к содержимому с самого начала, и что в установившемся режиме достигает 5-секундного буфера резервирования, и что глубина перемежения в 10 секунд требуется в установившемся режиме, и скорость отправки должна быть приблизительно на 10% больше скорости кодированного потока в течение периода времени, когда перемежение и буфер резервирования увеличиваются. В таком случае, возможные настройки для параметров следующие: S=UI=LI - требуемая начальная позиция, T=100 секунд, LF=S+T+5 секунд, и UF=LF+10 секунд. Таким образом, если скорость передачи потока содержимого равна 1 Мбит/с для этого примера и используется 10%-ная величина защиты, то скорость кодированного потока должна составлять 1,1 Мбит/с. Затем в течение первых 100 секунд отправки с помощью способа динамического перемежения с использованием настроек параметров, поясненных выше, скорость отправки должна составлять приблизительно 1,21 Мбит/с, поскольку 100+(5+15)/2=110 секунд потока отправляется в течение первых 100 секунд. После 100 секунд отправки буфер резервирования должен составлять 5 секунд, и глубина перемежения должна составлять 10, и в таком случае скорость отправки далее должна составлять 1,1 Мбит/с. За несколько секунд непосредственно перед тем, как будут достигнуты 100 секунд потоковой передачи, скорость отправки должна плавно переходить от скорости 1,21 Мбит/с к скорости 1,1 Мбит/с. Также следует отметить, что вначале скорость отправки следует скорости кодированного потока и плавно по мере того, как глубина перемежения и буфер резервирования увеличиваются, скорость отправки сглаживается и все более точно совпадает со средней скоростью кодированного потока.
Время на переключение содержимого, испытываемое на приемнике, соответственно способу динамического перемежения, описанному выше, описывается со ссылкой на фиг.11. Некоторые из компонентов времени 1105 на переключение содержимого содержат время 1110, которое требуется приемнику, чтобы принимать достаточно из первого кодированного блока потока для того, чтобы декодировать первый исходный блок, время, которое требуется приемнику, чтобы декодировать первый исходный блок из принимаемых частей первого кодированного блока 1120, и начальное время 1130 буфера резервирования, зарезервированное для ожидаемой задержки из-за нарушения синхронизации в сети, изменений длительности исходного блока и времен декодирования исходных блоков из частей принимаемых кодированных блоков во время приема потока.
Поскольку буфер резервирования увеличивается со временем при использовании динамического перемежения, начальное время 1130 буфера резервирования может быть гораздо меньшим при использовании динамического перемежения, чем имеет место, когда размер буфера резервирования является фиксированным для всей длительности отправки потока. Например, при использовании основного потокового передатчика размер буфера резервирования может быть задан равным двум секундам, чтобы буферизовать от долговременного нарушения синхронизации в сети вплоть до двух секунд, тогда как для способа отправки с динамическим перемежением начальное время 1130 буфера резервирования может быть гораздо меньшим, к примеру 200 миллисекунд, поскольку, вероятно, будет небольшое нарушение синхронизации в сети в течение первых нескольких секунд отправки потока и к тому времени буфер резервирования существенно увеличился.
Поскольку период защиты для каждого исходного блока постепенно увеличивается при использовании динамического перемежения, начальная длительность исходного блока может быть гораздо меньшей при использовании динамического перемежения, чем когда период защиты - это длительность исходного блока для всей длительности отправки потока. Например, при использовании основного потокового передатчика длительность исходного блока может быть задана равной пяти секундам, а величина защиты может быть задана равной 20%, чтобы защищать от коротких потерь при передаче пакетов в 500 миллисекунд, тогда как при способе отправки с динамическим перемежением длительность исходного блока может быть гораздо короче, к примеру 500 миллисекунд, и величина защиты может быть задана гораздо меньшей, к примеру 5%, чтобы предоставлять такой же уровень защиты от таких пакетов, поскольку маловероятно, что этот пакет возникает в течение первых нескольких секунд отправки потока, и к тому времени период защиты существенно увеличился, например, до первоначальной длительности исходного блока плюс 10 секунд глубины перемежения, чтобы защищать от таких пакетов.
Таким образом, в целом, при использовании способа динамического перемежения время на переключение содержимого может быть небольшим, к примеру, время на переключение содержимого менее чем 1 секунда, в сравнении с несколькими секундами при использовании основного способа отправки потока при тех же самых характеристиках сети, и при этом способы динамического перемежения могут предоставлять превосходную долговременную защиту от нарушения синхронизации в сети и потерь при пакетной передаче.
Предусмотрено множество вариантов того, как могут задаваться параметры. Например, вместо этого можно указывать начальную исходную позицию на ленте, начальную величину перемежения, конечную величину перемежения и период времени, за который следует плавно переходить от начального перемежения к конечному перемежению. Альтернативно, вместо задания периода времени, за который следует плавно переходить от начального перемежения к конечному перемежению, можно указывать скорость относительно скорости потоковой передачи содержимого, на которой выполнять переход. В качестве еще одного примера варианта дополнительные параметры могут быть известны передатчику или указываться посредством приемника, к примеру, приемник может явно передавать в служебных сигналах начальную позицию S, с которой приемник должен начинать воспроизведение содержимого.
Предусмотрено множество вариантов способов динамического перемежения, как должно быть понятно специалистам в данной области техники. Например, передатчик может решать, отфильтровывать и не отправлять некоторые из кодированных данных из некоторых или всех кодированных блоков в отдельные приемники, например, поскольку эти приемники не испытывают существенные потери. В качестве еще одного варианта структура исходных блоков может быть заранее определенной, но по мере того как процесс отправки осуществляется, FEC-кодирование осуществляется, чтобы формировать кодированные блоки для отдельных приемников или иногда формировать большое количество исправляющих символов для некоторых кодированных блоков, поскольку встречены приемники, которые требуют больших величин защиты, чем предшествующие приемники.
В качестве еще одного варианта, который зачастую является более предпочтительным, приемник может управлять заданием начальных параметров для способов динамического перемежения, и сервер или набор серверов может определять конечные целевые параметры для способов динамического перемежения. Например, приемник может указывать, что поток содержимого должен запускаться с глубиной перемежения в 2 секунды и буфером резервирования в 1 секунду, и сервер затем может определять, что он должен выполнять отправку таким образом, что глубина перемежения в 20 секунд с буфером резервирования в 10 секунд достигается за первые 2 минуты отправки. Одно преимущество управления посредством сервера или серверов конечными параметрами для способов динамического перемежения состоит в том, что гораздо проще поддерживать прямую потоковую передачу, когда части потока содержимого за рамками текущего времени недоступны, и таким образом сервер может управлять параметрами динамического перемежения до конечного значения, которое работает при данных ограничениях. В качестве еще одного примера преимущества наличия серверов, задающих конечные параметры в том, что сервер может в некоторых случаях регулировать параметры для нескольких клиентов, обслуживаемых согласно одному потоку содержимого фактически с одной позиции в рамках потока, таким образом, что в конечном счете множество из приемников управляются до достижения одних и тех же конечных параметров, что приводит к эффективной отправке пакетов посредством сервера в эти приемники, поскольку в одной точке во времени один пакет должен отправляться из потока содержимого во все эти приемники.
Способы динамического перемежения для смен сегментов содержимого
Одно примерное использование способа динамического перемежения - это когда приемник переходит от одного сегмента содержимого к следующему сегменту содержимого в списке сегментов содержимого, например, когда переходит от сегмента эпизода шоу к рекламе и затем обратно к следующему сегменту шоу, причем все переходы осуществляются вообще без взаимодействия с приемником. Различные сегменты содержимого могут отправляться посредством различных передатчиков, к примеру сегменты эпизода шоу могут отправляться в приемник посредством сервера содержимого, тогда как промежуточные рекламные ролики могут отправляться в приемник посредством рекламных серверов.
Первый пример - это когда приемник просматривал первый сегмент содержимого, который отправляется посредством первого передатчика с помощью способов динамического перемежения, описанных выше, и первый передатчик отправлял в течение достаточно длительного времени для того, чтобы достигались полная глубина перемежения D и время буфера резервирования R. Далее плавный переход ко второму сегменту содержимого может осуществляться следующим образом при использовании способа динамического перемежения:
1. За D+R секунд перед окончанием отправки первого сегмента содержимого, скорость отправки для первого сегмента должна линейно снижаться со скорости кодированного потока до нуля за период в D секунд, и в этой точке первый передатчик должен прекращать отправку первого сегмента.
2. За D+R секунд перед тем, как первый сегмент содержимого завершает воспроизведение, приемник запрашивает второй сегмент содержимого из второго сервера с параметрами UL=0, LI=-D, UF=0, LF=-D, T=0. При условии отсутствия времени задержки в сети второй сервер должен начинать отправку потока для второго сегмента содержимого, увеличивая скорость линейно в течение первых D секунд отправки, и после этого отправка выполняется на скорости кодированного потока.
3. Когда первый сегмент содержимого заканчивает воспроизведение, буфер резервирования для второго содержимого увеличился до R секунд и глубина перемежения увеличилась до D секунд. В данный момент воспроизведение второго содержимого может быть запущено.
Таким образом, переход от первого сегмента содержимого ко второму сегменту содержимого поддерживает скорость приема в приемнике равной скорости кодированного потока, т.е. в то время, когда скорость отправки для первого сегмента содержимого линейно снижается, скорость отправки для второго сегмента содержимого линейно повышается таким образом, что комбинированная скорость в ходе перехода такова, как если бы отправлялся один сегмент содержимого непрерывно. Кроме того, защита буфера резервирования и защита перемежения для второго потока является такой же, как для первого потока в установившемся режиме. На Фиг.12 приведена иллюстрация этого.
Даже если время немного сдвинуто при начале отправки потока для второго сегмента содержимого по сравнению с окончанием отправки первого сегмента содержимого, поскольку снижающиеся скорости и повышающиеся скорости являются плавно линейными, чистая ошибка скорости потоковой передачи незначительна. Например, если имеется ошибка на 500 миллисекунд в синхронизации перехода между двумя потоками и глубина перемежения составляет 10 секунд, то ошибка в скорости потоковой передачи самое большее равна 5%. Это также означает, что параметры для второго сегмента содержимого могут быть заданы немного более консервативно, чем описано выше, т.е. таким образом, что они пытаются немного больше увеличивать буфер резервирования и время перемежения вместо простой попытки сохранять эти значения такими же, как для первого потока, и последующее увеличение комбинированной скорости потоковой передачи в течение смены сегмента содержимого будет незначительным.
Второй пример смены сегмента содержимого соответствует тому, когда приемник просматривал первый сегмент содержимого, который отправляется посредством первого передатчика с использованием способов динамического перемежения, описанных выше, но первый передатчик не отправлял в течение достаточно длительного времени для того, чтобы достигались полная глубина перемежения D и время буфера резервирования R. Далее плавный переход ко второму сегменту содержимого может осуществляться следующим образом при использовании способа динамического перемежения, причем в этом случае то, что делает приемник, это задает параметры и запрашивает второй поток таким образом, что переход от первого потока ко второму потоку выполняется, как если бы эти два сегмента содержимого конкатенировались вместе и отправлялись посредством одного сервера. Специалистам в данной области техники могут быть понятны подробности того, как достичь этого типа перехода с использованием способов динамического перемежения.
Третий пример смены сегмента содержимого соответствует тому, когда приемник просматривал первый сегмент содержимого, который отправляется посредством первого передатчика с использованием способов динамического перемежения, описанных выше, и затем есть интервал между периодом времени между тем, когда воспроизведение первого сегмента содержимого завершается в приемнике и воспроизведение второго сегмента содержимого должно начинаться. Например, это может быть желательным режимом, когда есть первый сегмент эпизода передачи, который завершает воспроизведение, за которым следует непотоковая реклама, например, длительностью в 30 секунд, за которой следует мгновенное воспроизведение второго сегмента содержимого эпизода передачи. В этом случае способы динамического перемежения могут использоваться следующим образом, для простоты предполагая, что первый сегмент содержимого отправлялся в приемник довольно долго для того, чтобы достигались полная глубина перемежения D и время буфера резервирования R. В этом случае, как имело место для первого примера выше, приемник отправляет запрос на предмет второго сегмента содержимого за D+R секунд до окончания воспроизведения первого сегмента содержимого с параметрами UI=0, LI=-D, UF=0, LF=-D, T=0. Это заставляет второй сервер начинать отправку второго сегмента содержимого на такой скорости, что, когда комбинируется со скоростью первого сегмента содержимого, отправляемого из первого сервера, полная скорость - это скорость отправки одного потока. Затем, только в то время, когда первый сегмент содержимого заканчивает воспроизведение в приемнике, приемник сигнализирует второму серверу завершать отправку потока для второго сегмента содержимого и скорость отправки в приемник сразу снижается до нуля. Затем возникает промежуток, например, в течение 30 секунд. В конце промежутка приемник сразу начинает воспроизведение второго сегмента содержимого и одновременно отправляет запрос на начало отправки во второй сервер на предмет второго содержимого с параметрами UI=D+R, LI=R, UF=D+R, LF=R, T=0. Это заставляет второй сервер продолжать отправку второго содержимого с момента, где он закончил непосредственно перед промежутком. Общим эффектом является мгновенное воспроизведение второго содержимого в назначенное время, при этом одновременно комбинированная скорость отправки в приемник во всех точках в течение перехода является такой же, как скорость одного кодированного потока в ходе воспроизведения этих двух сегментов содержимого, и скорость отправки равна нулю, когда ни один из этих двух сегментов содержимого не воспроизводится. Фиг.13 иллюстрирует данный случай.
Предусмотрено множество других применений и вариантов способов динамического перемежения, описанных выше, как должны признавать специалисты в данной области техники.
Способы доставки на основе подпотоков
Доставка на основе подпотоков - это способы для взятия FEC-кодированного потока и секционирования его на подпотоки так, что, например, приблизительно равное количество каждого кодированного блока включается в каждый подпоток. Например, кодированный поток может быть секционирован на 40 подпотоков, при этом каждый подпоток состоит приблизительно из 5% каждого исходного блока, и тем самым в этом примере величина исправляющих данных, формируемых для каждого исходного блока при использовании FEC-кодирования, приблизительно равна размеру исходного блока. Если обобщить, когда FEC-кодирование применяется к каждому исходному блоку и затем применяется доставка на основе подпотоков, то полные кодированные данные для каждого исходного блока секционируются на подпотоки так, что приблизительно равная величина кодирования каждого исходного блока включается в каждый подпоток, при этом кодированные данные каждого исходного блока содержат первоначальные данные каждого исходного блока плюс сформированные исправляющие данные, если FEC-кодирование является систематическим, и при этом кодированные данные каждого исходного блока могут содержать исправляющие данные, если FEC-кодирование не является систематическим.
Одна из основных идей доставки на основе подпотоков состоит в том, чтобы отправлять подпотоки для потока по потенциально различным трактам и через потенциально различные серверы, чтобы достигать ряда желательных целей. В качестве примера, может быть предусмотрен сервер, далее называемый центральным сервером (HES), который захватывает поток содержимого в систему доставки на основе подпотоков, при этом некоторые из процессов, которые выполняет HES, заключаются в том, чтобы создавать структуру исходных блоков для потока содержимого, FEC-кодировать поток, секционировать кодированный поток на подпотоки и затем отправлять подпотоки в другие серверы, далее называемые распределенными серверами (DS), которые могут быть распределены в пределах различных центров обработки и хранения данных или в пределах различных сетевых пунктов. Пример этого можно видеть на фиг.14. На фиг.14, каждый из DS 1430 принимает различный сегмент потока 1420 кодированного содержимого от HES 1410. Некоторые из процессов, которые выполняет DS, включают в себя кэширование подпотоков потоков содержимого по мере того, как они проходят на пути в приемники, чтобы принимать запрос на подпотоки из конкретных потоков содержимого от приемников и отправлять подпотоки в приемники, например, на основе запросов приемника на предмет конкретных подпотоков или на основе подписок приемника. Частный случай передачи подпотоков содержит первоначальный кодированный поток, который не секционируется дополнительно.
Приемники в системе доставки на основе подпотоков могут запрашивать и принимать подпотоки для одного сегмента содержимого, начинающегося в одной начальной позиции, при этом запросы могут отправляться в различные DS для различных подпотоков, и в этом случае несколько различных подпотоков для одного кодированного потока с одной начальной позицией могут отправляться из различных DS в один приемник. Пример этого можно видеть на фиг.15. На фиг.15, приемник 1530 запрашивает поток содержимого из различных DS 1510, 1520. В этом случае один из DS 1520 не реагирует на запрос от приемника, тогда как другие DS 1510 отправляют подпотоки в приемник. Может быть возможным для приемника полностью восстанавливать поток содержимого с использованием FEC-кодирования, если реагирующие DS передают достаточно данных в приемник, чтобы сделать это.
В качестве примера первоначальный поток содержимого в 1 Мбит/с может быть захвачен в HES, HES формирует структуру исходных блоков по мере того, как поток содержимого проходит, и добавляет столько исправляющих данных, сколько имеется исходных данных в первоначальном потоке (100%-ное исправление), секционирует кодированный поток в 2 Мбит/с на подпотоки по 100 кбит/с и отправляет результирующие 20 подпотоков в 20 различных DS. Приемник, который хочет воспроизводить поток содержимого, начиная с конкретной позиции внутри потока, может отправлять запрос в 12 из этих 20 DS, запрашивая подпоток, который DS имеет для содержимого, начинающегося в указанной исходной позиции. В ответ все 12 из DS одновременно отправляют подпоток, который они имеют для кодированного потока, в приемник, начиная с указанной начальной точки, и таким образом каждый из этих 12 DS отправляет на скорости 100 кбит/с в приемник, так что полная скорость составляет 1,2 Мбит/с.
Есть несколько преимуществ системы доставки на основе подпотоков, описанной выше, некоторые или все из которых могут быть найдены в вариантах осуществления настоящего изобретения, включая 1) естественную компенсацию нагрузки содержимого, смешивая популярное и не очень популярное, с преимуществами естественной компенсации нагрузки для обслуживания пропускной способности и емкости хранения на серверах, 2) устойчивость к сбоям в тракте, т.е. один тракт выходит из строя, и при этом есть достаточно данных, которые приемник принимает из других трактов, так что поток содержимого по-прежнему может полностью восстанавливаться с помощью FEC-декодирования, 3) устойчивость к сбоям DS, сбоям дисков DS и т.д., 4) отправка данных из нескольких DS в сравнении с одним сервером предоставляет большую вероятность того, что совокупная скорость отправки сохранится в приемнике и не будет зависания буфера в приемнике. Это, в частности, имеет место, если TCP или HTTP используются для того, чтобы отправлять подпотоки в приемник из DS, но правда даже в том случае, если UDP используется для того, чтобы отправлять подпоток в приемник из DS, и 5) элементы, отказы которых приводят к отказу всей системы, располагаются на входе в HES и в приемник, а не в другом месте.
Комбинирование способов динамического перемежения и способов доставки на основе подпотоков
Способы динамического перемежения и способы доставки на основе подпотоков, описанные в данном документе, могут быть комбинированы для существенной выгоды, т.е. все преимущества обоих способов находятся в комбинированном решении. Например, при использовании способов динамического перемежения структура исходных блоков и FEC-кодирование для потока содержимого могут выполняться посредством HES по мере того, как поток содержимого захватывается в систему. Способы подпотока могут использоваться для того, чтобы формировать подпотоки FEC-кодированного потока в HES, и эти подпотоки затем могут отправляться в различные DS для хранения. Когда приемник хочет принимать поток содержимого с конкретной позиции внутри потока, приемник может отправлять соответствующие параметры динамического перемежения во все DS, отправляющие подпоток в приемник, и DS должны отправлять подпотоки согласно этим параметрам в приемник. Приемник может объединять пакеты из подпотоков для исходных блоков, чтобы воссоздавать поток исходного содержимого для воспроизведения. Способы динамического перемежения дают возможность буферу резервирования и глубине перемежения увеличиваться в ходе потоковой передачи, предоставляя превосходную защиту от потерь при пакетной передаче и нарушения синхронизации в сети, при этом одновременно предоставляя для приемника малое время на переключение каналов. DS в этом примерном решении не должны выполнять FEC-кодирование, и тем не менее они могут доставлять поток содержимого в приемник по распределенным трактам из различных частей сети, таким образом повышая диверсификацию серверов и диверсификацию трактов доставки, тем самым увеличивая надежность и устойчивость к сбоям серверов и сети.
Кроме того, величина защиты для каждого исходного блока может быть существенно выше между HES и DS в этом примере, чем между DS и приемником. Например, 20 подпотоков могут быть сформированы и отправлены из HES в 20 DS, тогда как только 10 подпотоков могут быть необходимы для того, чтобы восстанавливать поток исходного содержимого (величина защиты 100%), тогда как приемник может запрашивать только, например, 12 подпотоков от 12 из этих 20 DS, т.е. 20%-ная величина защиты, которая дает возможность приемнику по-прежнему иметь возможность восстанавливать поток исходного содержимого, даже если один из DS выходит из строя, и возникает до 10% потерь пакетов в целом по всем трактам из оставшихся 11 DS, из которых приемник принимает подпотоки.
Примерное решение, поясненное выше, имеет дополнительное свойство, состоящее в том, что с помощью надлежащей логики, включенной в приемник, который имеет список более 12 из 20 DS, когда один из 12 DS, из которых приемник принимает подпоток, выходит из строя, приемник может автоматически обнаруживать это и запрашивать другой подпоток из одного из других DS, из которых приемник в настоящий момент не принимает подпоток, тем самым повышая надежность потока от приема 11 подпотоков снова до приема 12 подпотоков из 12 различных DS.
Изменения в способах, требуемые для того, чтобы комбинировать способы динамического перемежения и способы подпотока, являются относительно незначительными. Например, способы для распределения точек данных в пределах кодированного блока для определения времени отправки для способов динамического перемежения должны быть дополнены таким образом, чтобы каждый DS мог принимать решения относительно того, как распределять данные, которые он имеет для каждого подпотока в рамках кодированного блока, равномерно по области кодированного блока в пределах ленты кодированного потока (см. фиг.7). Решения, принимаемые посредством DS, чтобы равномерно распределять данные, могут осуществляться независимо от решений, принимаемых посредством других DS, так чтобы совокупное распределение данных из всех подпотоков в рамках кодированного блока от всех DS, отправляющих в приемник, являлось достаточно равномерным в области кодированных блоков в пределах ленты кодированного потока (см. фиг.7).
В качестве еще одного примера изменений способов, требуемых для их комбинирования, является предпочтительным расширять информацию, отправляемую с каждым пакетом так, что, когда приемник указывает конкретную позицию в рамках потока для DS, которые должны отправлять его подпотоки, все DS могут интерпретировать конкретную позицию для подпотока, который они должны отправлять в приемник способом, согласованным с интерпретацией всех других DS, отправляющих подпоток для того же самого содержимого в приемник. Как должны признавать специалисты в данной области техники, эти и потенциально еще несколько других незначительных изменений дают возможность комбинировать способы перемежаемой потоковой передачи и способы доставки на основе подпотоков для существенной выгоды.
Хотя изобретение описано относительно примерных вариантов осуществления, специалистам в данной области техники должно быть понятно, что возможны многочисленные модификации на основе данного раскрытия сущности изобретения. Например, процессы, описанные в данном документе, могут реализовываться с помощью аппаратных компонентов, программных компонентов и/или любой комбинации вышеозначенного. Таким образом, хотя изобретение описано относительно примерных вариантов осуществления, следует принимать во внимание, что изобретение имеет намерение охватывать все модификации и эквиваленты в рамках объема прилагаемой формулы изобретения.