СПОСОБ И УСТРОЙСТВО ДЛЯ РАНЖИРОВАНИЯ РАВНОУРОВНЕВЫХ УЗЛОВ В СЕТИ ПОТОКОВОЙ ПЕРЕДАЧИ Р2Р РЕАЛЬНОГО ВРЕМЕНИ
METHOD AND DEVICE FOR RANKING PEER NODES IN REAL TIME P2P STREAMING NETWORK

Область техники, к которой относится изобретение
Настоящее изобретение относится к способу ранжирования равноуровневых узлов в сети Р2Р (peer-to-peer) и к устройству для ранжирования равноуровневых узлов в сети Р2Р.
Уровень техники
В архитектуре клиент-сервер при потоковой передаче видео в реальном времени клиент принимает видеопоток из сервера потоковой передачи (источника). Видеопоток состоит из набора последовательных элементов данных (подмножеств данных), которые клиент с целью воспроизведения видео время от времени запрашивает. Чтобы удовлетворять потребности возрастающего количества клиентов через Интернет, в расширяемой службе потоковой передачи данных в реальном времени должен использоваться сервер потоковой передачи с высокой пропускной способностью. Чтобы снизить стоимость сервера потоковой передачи, был разработан способ потоковой передачи в реальном времени между узлами одного уровня (равноуровневыми узлами, peer-to-peer, Р2Р). Основной идеей потоковой передачи Р2Р в реальном времени является перенос части нагрузки с сервера потоковой передачи на клиентов, в данном контексте называемых равноуровневыми узлами.
В последние годы к системам потоковой передачи Р2Р в реальном времени привлечено значительное внимание из-за наличия у таких систем преимущества, дающего источнику потоковой передачи возможность транслировать, к примеру, видеоизображение проходящего в настоящий момент мероприятия в большое число равноуровневых узлов без необходимости обеспечения полной требуемой пропускной способности. Это достигается использованием при трансляции информационного материала в равноуровневые узлы имеющейся у самих равноуровневых узлов возможности передавать данные, помогая тем самым источнику потоковой передачи.
К сетям Р2Р относятся все сети, состоящие из элементов, каждый из которых предоставляет другим элементам доступ к части своих ресурсов (например, к вычислительной мощности, емкости дискового хранилища и/или пропускной способности). Концепция Р2Р отличается от концепции, используемой в сетях с обычной архитектурой клиент-сервер, где один или более элементов (например, компьютеров) специально предназначен для обслуживания других элементов сети. Как правило, элементы сети Р2Р используют аналогичные сетевые протоколы и программное обеспечение. Применения сетей Р2Р многочисленны: это может быть, например, передача и/или хранение данных в Интернете, в частности, распространение видеоматериалов владельцами последних.
Для использования способности самих равноуровневых узлов передавать данные разработано множество способов. Указанные способы можно разделить на две основные категории.
Системы на основе дерева строятся с использованием одного или более структурированных деревьев в наложенной сети, где равноуровневые узлы на вершине каждого дерева передают данные в нижележащие равноуровневые узлы. Этот способ хорошо работает, когда не происходит частого присоединения равноуровневых узлов к системе или отсоединения равноуровневых узлов от системы, поскольку дальнейшая передача потока данных осуществляется без передачи сообщений между равноуровневыми узлами. Однако при высокой нагрузке поддержание работоспособности дерева может требовать очень больших затрат, а иногда возникает необходимость в ликвидации и перестройке дерева (деревьев).
Системы на основе ячеистой сети не требуют построения дерева, иными словами, соединения между равноуровневыми узлами не образуют наложенной сети определенного типа, а являются бесструктурными. Указанные узлы обмениваются данными с использованием так называемой эпидемической передачи (gossip communication) или путем передачи между собой запросов данных. Недостатком систем на основе ячеистой сети является возможный рост времени распространения информации, поскольку узлы для поиска равноуровневых узлов должны выполнить согласование между собой. Однако способ на основе ячеистой сети используется во многих системах, поскольку он очень устойчив к высокой нагрузке. В таких системах у каждого равноуровневого узла есть несколько соседних узлов, из которых указанный узел принимает данные, и отказ одного из соседних узлов не столь критичен, как в способах на основе дерева.
Несмотря на то, что в способах на основе ячеистых сетей отдельные равноуровневые узлы принимают решения локально без использования общесетевой информации, при резком росте числа равноуровневых узлов в таких способах все же можно получить выигрыш, сопоставимый со способами на основе деревьев, в основном благодаря отсутствию в способах на основе ячеистых сетей необходимости нести большие накладные расходы на поддержание общесетевой информации о сетевых соединениях.
В децентрализованной сети потоковой передачи Р2Р в реальном времени каждый равноуровневый узел имеет к соседних равноуровневых узлов, из которых он может пытаться принимать данные информационного материала. Таким образом, равноуровневый узел, вместо того, чтобы принимать данные информационного материала из сервера потоковой передачи, предпримет попытку найти соседний равноуровневый узел, из которого возможен прием указанных данных. Однако если в такой наложенной сети известного уровня техники равноуровневые узлы начнут потоковую передачу данных информационного материала с одного и того же момента времени, то ни один из равноуровневых узлов не сможет найти равноуровневый узел, из которого можно принять полезный информационный материал. В результате почти все равноуровневые узлы будут принимать данные из сервера потоковой передачи, и выигрыш в нагрузке на пропускную способность сервера потоковой передачи будет незначительным.
Раскрытие изобретения
Целью настоящего изобретения является устранение или, по меньшей мере, ослабление влияния указанных недостатков известного уровня техники. Данная цель достигается посредством способа и устройства для ранжирования равноуровневых узлов в сети Р2Р в соответствии с независимыми пунктами формулы изобретения и предпочтительными вариантами осуществления, определенными в зависимых пунктах формулы изобретения.
С этой целью из равноуровневого узла, вновь подключенного к сети, принимают запрос на прием данных информационного материала. Затем определяют задержку, с которой указанный вновь подключенный равноуровневый узел должен будет принимать данные информационного материала по отношению к моменту воспроизведения в реальном времени указанных данных информационного материала, распространяемых источником потоковой передачи. После того, как задержка определена, в указанный вновь подключенный равноуровневый узел передают перечень множества случайным образом выбранных равноуровневых узлов, из которых запрошенные данные информационного материала могут быть загружены с ожидаемой вероятностью, зависящей от определенной таким образом задержки. Таким образом, вновь подключенный равноуровневый узел имеет возможность с ожидаемой вероятностью загрузить запрошенные данные информационного материала из выбранного одного из указанного множества случайным образом выбранных равноуровневых узлов с меньшей задержкой по сравнению с задержкой, определенной для указанного вновь подключенного равноуровневого узла.
В результате путем корректного выбора адекватной задержки для вновь подключенного равноуровневого узла можно повысить вероятность выполнения загрузки указанным узлом от одного из своих соседних равноуровневых узлов. Соответственно, снижается риск того, что равноуровневый узел должен будет загружать данные информационных материалов из источника потоковой передачи.
Следует принять во внимание, что настоящее изобретение относится ко всем возможным сочетаниям признаков, приведенных в формуле изобретения. Другие признаки и преимущества настоящего изобретения будут понятны при изучении прилагаемой формулы изобретения и нижеследующего раскрытия. Специалисту в данной области техники должно быть понятно, что различные признаки настоящего изобретения могут сочетаться с целью создания вариантов осуществления, отличающихся от раскрытых далее.
Краткое описание чертежей
Далее настоящее изобретение раскрывается посредством примера со ссылкой на сопровождающие чертежи, в которых:
на фиг. 1 показана потоковая передача данных в сети потоковой передачи Р2Р в реальном времени, соответствующей известному уровню техники;
на фиг. 2а и 2b показана потоковая передача данных в сети потоковой передачи Р2Р в реальном времени согласно варианту осуществления настоящего изобретения;
на фиг. 3 показана функция трекера согласно варианту осуществления настоящего изобретения;
на фиг. 4 показано распределение вероятности задержек для равноуровневых узлов сети по отношению к моменту воспроизведения реального времени в источнике потоковой передачи согласно варианту осуществления настоящего изобретения;
i
на фиг. 5 показан вариант осуществления настоящего изобретения, в котором равноуровневые узлы с задержкой d передают запросы в соседние равноуровневые узлы, относящиеся к области α;
на фиг. 6 показано распределение Пуассона, используемое для моделирования распределения задержек равноуровневых узлов сети согласно варианту осуществления настоящего изобретения;
на фиг. 7 показан выигрыш в пропускной способности источника потоковой передачи согласно варианту осуществления настоящего изобретения; и
на фиг. 8 показана гистограмма задержек равноуровневых узлов сети согласно варианту осуществления настоящего изобретения.
Осуществление изобретения
Далее настоящее изобретение более полно раскрывается со ссылкой на сопровождающие чертежи, на которых показаны некоторые варианты осуществления настоящего изобретения. Настоящее изобретение, однако, может быть осуществлено во множестве различных форм и не должно рассматриваться как ограниченное приведенными здесь вариантами осуществления; указанные варианты осуществления приведены лишь в качестве примера, чтобы сделать раскрытие настоящего описания обстоятельным и полным и в полной мере раскрыть объем настоящего изобретения специалисту в данной области техники.
1
15
1
2
3
6
8
10
14
1
2
3
6
8
10
14
1
2
3
6
8
10
14
2
7
9
13
3
4
На фиг. 1 показана наложенная сеть Р2Р известного уровня техники с равноуровневыми узлами p-p, случайным образом соединенными с сервером SS потоковой передачи. Сервер потоковой передачи распространяет данные информационных материалов, разделенные на небольшие элементы данных, которые передаются в равноуровневые узлы сети. Таким образом, данные информационных материалов делят на последовательные элементы данных, в данной заявке называемые подмножествами данных. Это показано в нижней части фиг. 1, где данные информационного материала разделены на небольшие подмножества DS1-DS3 данных. По завершении источником SS потоковой передачи подготовки подмножества DS данных указанное подмножество может быть передано в равноуровневый узел, который начинает воспроизведение указанного подмножества данных, а источник потоковой передачи в это время готовит следующее подмножество данных. На фиг. 1 сервер потоковой передачи передает подмножество DS1 данных в равноуровневые узлы р, р, p, p, p, p и р, и в каждом из соответствующих равноуровневых узлов начинается воспроизведение DS1. Одновременно с этим сервер потоковой передачи формирует подмножество данных DS2, а когда равноуровневые узлы р, р, р, p, p, p и р полностью воспроизведут подмножество DS1 данных, указанное подмножество сохраняется в буфере воспроизведения соответствующего равноуровневого узла. Затем сервер потоковой передачи передает в равноуровневые узлы р, р, р, p, p, p и рподмножество DS2 данных, а равноуровневый узел р передает последнее полностью принятое подмножество DS1 данных в равноуровневые узлы р, р и р, равноуровневый узел р передает DS1 в равноуровневый узел р и т.д.
Соответственно, в таких сетях потоковой передачи Р2Р в реальном времени, соответствующих известному уровню техники, каждый равноуровневый узел, вновь подключенный к сети, запрашивает в трекере (не показан) информацию о последнем подмножестве данных, с которого следует начать прием данных, и информацию о k случайных равноуровневых узлах, являющихся соседними узлами. Затем указанный вновь подключенный равноуровневый узел обращается к своим соседним узлам за последним подмножеством данных, и если требуемое подмножество данных найдено на каком-либо соседнем равноуровневом узле, то указанный вновь подключенный равноуровневый узел начинает прием данных из указанного соседнего равноуровневого узла. Как пояснялось выше, из-за задержек в сети и асинхронизма вновь подключенный равноуровневый узел будет иметь задержку на по меньшей мере полную длительность одного подмножества данных, принимаемого из своего узла, предоставляющего данные, и по меньшей мере вдвое большую задержку по отношению к серверу потоковой передачи при условии, что указанный узел, предоставляющий данные указанному вновь подключенному равноуровневому узлу, имеет задержку на по меньшей мере полную длительность одного подмножества данных, принимаемого из указанного источника. Иными словами, по отношению к моменту RT воспроизведения реального времени данных информационного материала, распространяемого источником потоковой передачи, вновь подключенный равноуровневый узел будет иметь задержку по меньшей мере на два подмножества данных, а узел, предоставляющий данные, будет иметь задержку на по меньшей мере одно подмножество данных. Если вновь подключенный равноуровневый узел не может найти последнее подмножество данных на одном из своих соседних равноуровневых узлов, то указанный вновь подключенный равноуровневый узел принимает указанное подмножество данных из сервера потоковой передачи. По сравнению с обычной клиент-серверной сетью, где сервер распространяет информационные материалы по всем клиентам, в сети Р2Р на фиг. 1 выигрыш в нагрузке на сервер потоковой передачи составляет 8/15=0,53. Иными словами, вместо потоковой передачи информационного материала во все 15 равноуровневых узлов, сервер потоковой передачи SS передает информационный материал только в семь равноуровневых узлов, которые, передавая в свою очередь информационные материалы в остальные восемь равноуровневых узлов, уменьшают нагрузку на сервер.
i
i
i
i
На фиг. 2а, где показан вариант осуществления настоящего изобретения, новый равноуровневый узел p подключился к сети и запросил у трекера прием данных информационного материала, изначально передающегося из источника SS потоковой передачи. Трекер определяет, что задержка по отношению к моменту RT воспроизведения реального времени данных информационного материала, распространяемого источником потоковой передачи, с которой вновь подключенный равноуровневый узел будет принимать данные информационного материала, равна d единиц времени, т.е. вновь подключенный равноуровневый узел примет и сможет воспроизвести указанное подмножество данных через d единиц времени после того, как указанное подмножество данных было подготовлено в реальном времени источником потоковой передачи. Затем трекер передает во вновь подключенный равноуровневый узел перечень случайным образом выбранных равноуровневых узлов, из которых могут быть приняты данные указанного информационного материала. Указанный перечень равноуровневых узлов определяется или формируется по функции плотности вероятности для указанного равноуровневого узла в зависимости от задержки. Таким образом, вновь подключенный равноуровневый узел получает возможность принять из выбранного подмножества содержащихся в указанном перечне равноуровневых узлов, имеющих меньшую задержку по сравнению с задержкой, определенной для указанного вновь подключенного равноуровневого узла, данные информационного материала с определенной задержкой d по отношению к моменту воспроизведения реального времени в источнике потоковой передачи.
i
i
2
5
6
7
8
2
6
2
6
2
6
2
6
5
7
8
i
5
7
8
На фиг. 2а показано, что подмножеством данных, которое было сформировано источником потоковой передачи в реальном времени к моменту подключения равноуровневого узла к сети, является DS5. Если, например, указанная фиксированная задержка d равна 3 единицам и выражена в единицах длительности подмножества данных, т.е. указанная определенная задержка составляет три полных подмножества данных, а перечень, переданный трекером во вновь подключенный равноуровневый узел p, содержит равноуровневые узлы р, p, р, р и р (на практике количество узлов в перечне будет значительно большим), то вновь подключенный равноуровневый узел сможет найти требуемое подмножество DS2 данных в любом из равноуровневых узлов р и р, при этом указанное подмножество данных будет последним полностью принятым подмножеством данных, хранящимся в буфере воспроизведения узлов р и р, соответственно. Следовательно, DS2 представляет собой последнее подмножество данных, которое может быть передано из равноуровневых узлов р и р. В этом конкретном примере, поскольку равноуровневый узел р передает данные в три других равноуровневых узла, предпочтительным может быть прием данных вновь подключенным равноуровневым узлом из р. Следует отметить, что вновь подключенный равноуровневый узел не может принимать данные из узлов р, р и р, поскольку в момент подключения равноуровневого узла p к сети все перечисленные узлы еще только выполняли обработку подмножества DS2 данных. По указанной причине последним полностью принятым подмножеством данных, хранящимся в соответствующем буфере воспроизведения р, р и р, является подмножество DS1 данных.
По сравнению с обычной клиент-серверной сетью выигрыш в нагрузке на сервер потоковой передачи сети Р2Р на фиг. 2а составляет 13/15=0,87. Иными словами, вместо передачи информационных материалов во все 15 равноуровневых узлов, источник SS потоковой передачи передает информационные материалы в два равноуровневых узла, которые, передавая в свою очередь информационный материал в остальные 13 равноуровневых узлов, снижают нагрузку на источник.
В представленных примерных вариантах осуществления настоящего изобретения определенная задержка, с которой равноуровневый узел, подключившийся к сети, принимает данные информационного материала по отношению к моменту RT воспроизведения реального времени данных информационного материала, распространяемого источником потоковой передачи, выражается в единицах времени, эквивалентных длительности подмножества данных. Например, если в сети Р2Р длительность распространяемого подмножества данных равна 300 мс, то задержка длительностью одна единица означает, что равноуровневый узел принимает подмножество данных через 300 мс после того, как указанное подмножество данных было подготовлено источником потоковой передачи.
i
i
i
3
4
7
8
11
4
11
3
7
8
На фиг. 2b показан еще один вариант осуществления настоящего изобретения, в котором трекер снова определил, что задержка d для вновь подключенного равноуровневого узла p должна составлять 3 единицы. В этом конкретном примере перечень, переданный трекером во вновь подключенный равноуровневый узел p, содержит равноуровневые узлы р, р, р, р и р. В данном случае при определенной задержке, равной трем единицам, вновь подключенный равноуровневый узел не сможет найти требуемое подмножество DS2 данных ни в одном из содержащихся в перечне равноуровневых узлов. Для равноуровневых узлов р и р последним полностью принятым подмножеством данных, хранящимся в соответствующем буфере воспроизведения, является DS0, а для равноуровневых узлов р, р и р последним полностью принятым подмножеством данных является DS1. Таким образом, ни один из равноуровневых узлов, содержащихся в перечне, не сможет передать затребованное подмножество DS2 данных во вновь подключенный равноуровневый узел, вследствие чего вновь подключенный равноуровневый узел за требуемым подмножеством данных будет вынужден обратиться к источнику потоковой передачи.
i
i
3
На фиг. 3 показан еще один вариант осуществления настоящего изобретения, сочетающий способы, рассмотренные совместно с фиг. 2а и 2b. Сплошными линиями обозначены сообщения запросов и ответов, пунктирными линиями обозначены каналы потоковой передачи. Новый равноуровневый узел pподключается к сети и запрашивает у трекера Τ в шаге S101 через его коммуникационный интерфейс CI прием данных информационных материалов, изначально передаваемых из источника SS потоковой передачи. Трекер определяет задержку, с которой вновь подключенный равноуровневый узел должен принимать данные информационных материалов по отношению к моменту воспроизведения реального времени, и в шаге S102 передает во вновь подключенный равноуровневый узел перечень k случайным образом выбранных равноуровневых узлов, из которых могут быть приняты данные указанного информационного материала. Затем вновь подключенный равноуровневый узел запрашивает в шаге S103 у равноуровневых узлов из перечня предоставление последнего подмножества данных с учетом задержки, определенной для указанного вновь подключенного равноуровневого узла. Если имеется по меньшей мере один равноуровневый узел из k случайным образом выбранных равноуровневых узлов с задержкой по отношению к моменту воспроизведения реального времени, более низкой по сравнению с задержкой, определенной для указанного вновь подключенного равноуровневого узла, то в шаге S104 запрошенные данные информационного материала передаются в указанный вновь подключенный равноуровневый узел. На фиг. 3 запрошенные данные информационного материала во вновь подключенный равноуровневый узел p передает равноуровневый узел р. Выбором задержки для вновь подключенного равноуровневого узла можно увеличить вероятность того, что равноуровневый узел сможет в шаге S104 передать запрошенные данные информационных материалов во вновь подключенный равноуровневый узел. При отсутствии случайным образом выбранного равноуровневого узла с задержкой по отношению к моменту воспроизведения реального времени, более низкой по сравнению с задержкой, определенной для указанного вновь подключенного равноуровневого узла, т.е. если все k равноуровневых узлов имеют задержку, равную или более высокую по сравнению с задержкой, определенной для указанного вновь подключенного равноуровневого узла, то передача запрошенных данных информационного материала во вновь подключенный равноуровневый узел в шаге S104 будет невозможной. В этом случае вновь подключенный равноуровневый узел в шаге S105 обратится за требуемыми данными информационного материала к серверу потоковой передачи SS, который затем в шаге S106 передаст запрошенные данные информационного материала во вновь подключенный равноуровневый узел. Соответственно, выбором задержки для вновь подключенного равноуровневого узла можно снизить вероятность того, что серверу потоковой передачи придется в шаге S106 передавать запрошенные данные информационного материала. Указанные вероятности более подробно рассматриваются ниже.
i
В вариантах осуществления настоящего изобретения трекер в соответствии с настоящим изобретением определяет задержку d, с которой подключенный равноуровневый узел должен будет принимать данные информационного материала по отношению к моменту воспроизведения реального времени данных указанного информационного материала, передаваемого источником потоковой передачи, на основании статистической информации. Поведение сети Р2Р, в которой осуществляется настоящее изобретение, является случайным, зависящим от равноуровневых узлов сети, осуществляющих потоковую передачу в настоящий момент. Таким образом, должна использоваться такая статистическая информация, которая позволила бы построить распределение вероятности, описывающее поведение равноуровневых узлов в сети потоковой передачи Р2Р в реальном времени. Имея распределение p(d) вероятности задержки относительно момента воспроизведения реального времени транслируемых данных информационного материала на сервере потоковой передачи, можно рассчитать ожидаемый выигрыш в нагрузке на пропускную способность сервера потоковой передачи. Соответственно, задавая для каждого вновь подключенного равноуровневого узла значение задержки в соответствии с распределением p(d), можно приблизить выигрыш для сервера потоковой передачи к указанному ожидаемому выигрышу, рассчитанному с использованием указанного распределения. То же самое иными словами: определяя подходящую задержку, с которой вновь подключенный равноуровневый узел должен будет принимать данные информационного материала, можно увеличить вероятность того, что будет найден равноуровневый узел сети, из которого вновь подключенный равноуровневый узел сможет принять запрошенные данные информационного материала. Таким образом, выигрыш в пропускной способности сервера потоковой передачи непосредственно связан с вероятностью того, сможет ли какой-либо равноуровневый узел сети передать запрошенные данные информационного материала во вновь подключенный равноуровневый узел.
Показанный на фиг. 3, трекер Т, относящийся к вариантам осуществления настоящего изобретения, как правило, представляет собой устройство, содержащее одно или более устройств CPU обработки данных в форме микропроцессора (микропроцессоров), с целью осуществления требуемой функциональности выполняющего надлежащую программу, хранимую в сопряженном запоминающем устройстве. Однако для управления системой Р2Р и определения задержек равноуровневых узлов путем выполнения надлежащей программы, хранимой в подходящем запоминающем устройстве, например, в оперативном запоминающем устройстве, во флэш-памяти или на жестком диске, в вариантах осуществления способа в соответствии с настоящим изобретением могут быть использованы и другие пригодные устройства с вычислительными возможностями, к примеру, специализированная интегральная схема (application specific integrated circuit, ASIC), программируемая пользователем матрица логических элементов (field programmable gate array, FPGA), сложное программируемое логическое устройство (complex programmable logic device, CPLD) и т.п.
i
i
i
i
На фиг. 4 показана предполагаемая форма распределения задержки по отношению к моменту воспроизведения реального времени в соответствии с вариантами осуществления настоящего изобретения. Поскольку распределением значений задержек управляет трекер, можно установить взаимосвязь между ожидаемым выигрышем и указанным распределением. В вариантах осуществления настоящего изобретения любой вновь подключенный равноуровневый узел i, имеющий k случайным образом выбранных соседей и некоторую определенную трекером задержку d по отношению к моменту воспроизведения реального времени, будет искать среди своих соседей требуемые данные информационного материала, т.е. подмножество данных, которое в числе подмножеств d данных ранее было подготовлено в реальном времени в источнике потоковой передачи, см. фиг. 2а и 2b. Если конкретное подмножество данных не будет найдено, то указанный вновь подключенный равноуровневый узел запросит указанное подмножество данных из сервера потоковой передачи, тем самым расходуя пропускную способность сервера потоковой передачи. Указанная нежелательная ситуация возникает, когда последнее полностью принятое каждым из указанных k соседей подмножество данных имеет задержку, равную или большую по сравнению с задержкой, определенной для указанного вновь подключенного равноуровневого узла, т.е. задержку, лежащую в области β или в области между d - δ и dраспределения p(d).
i
di
i
В то же время если один из указанных k соседних равноуровневых узлов имеет задержку, лежащую в области α (и имеет достаточную пропускную способность), то указанный равноуровневый узел сможет передавать данные во вновь подключенный равноуровневый узел, начиная с запрошенного подмножества данных. Возвращаясь к фиг. 2а и 2b, следует отметить, что область α отграничена значением d - δ, где δ обычно соответствует длительности одного подмножества данных. То есть если задержка, определенная для вновь подключенного равноуровневого узла, равна трем подмножествам данных, то указанный узел сможет принять требуемое подмножество данных из равноуровневого узла, имеющего задержку, равную двум подмножествам данных, считая от момента воспроизведения реального времени. Поэтому вновь подключенный равноуровневый узел сможет принять данные лишь из любого соседнего равноуровневого узла, который опережает указанный вновь подключенный равноуровневый узел по меньшей мере на величину δ. Следовательно, вероятность P того, что для вновь подключенного равноуровневого узла случайным образом выбранный соседний равноуровневый узел относится к области α, равна просто значению интегральной функции распределения (cumulative distribution function, cdf) случайной переменной d в точке d - δ:
i
Таким образом, в варианте осуществления настоящего изобретения задержка d вновь подключенного равноуровневого узла определяется трекером с использованием принципа, выраженного формулой (1) благодаря чему запрошенные данные информационного материала с достаточно высокой вероятностью могут быть приняты из одного из k случайным образом выбранных равноуровневых узлов. В результате путем корректного выбора подходящей задержки для вновь подключенного равноуровневого узла вероятность того, что прием данных указанным вновь подключенным равноуровневым узлом будет осуществляться из одного из своих k соседних равноуровневых узлов, может быть повышена (или, при необходимости, снижена). Платой за повышение для вновь подключенного равноуровневого узла вероятности приема данных из соседнего равноуровневого узла является рост задержки, испытываемой указанным вновь подключенным равноуровневым узлом. Таким образом, если для данной сети потоковой передачи Р2Р в реальном времени вероятность успешного приема из соседнего равноуровневого узла и без того высока, то трекер может выбрать меньшую задержку с сохранением высокой вероятности приема.
Кроме того, заранее может задаваться величина порога, которую указанная вероятность должна превосходить, чтобы вероятность того, что запрошенные данные информационного материала смогут быть приняты из соседнего равноуровневого узла, считалась достаточно большой.
i
i
i
3
4
7
8
11
4
11
3
7
8
Как указано выше, в каждый равноуровневый узел сообщается перечень k случайным образом выбранных соседних равноуровневых узлов, чтобы гарантировать, что определенные задержки от момента воспроизведения реального времени будут согласованы с распределением p(d) вероятности и поэтому не будет иметь место какое-либо несоответствие. Кроме того, как указано выше, вновь подключенный равноуровневый узел будут принимать данные из сервера потоковой передачи, если соответствующее последнее полностью принятое подмножество данных каждого равноуровневого узла из числа k соседних равноуровневых узлов старше, чем подмножество данных, которое указанный вновь подключенный равноуровневый узел запрашивает. Такая ситуация имеет место на фиг. 2b, где трекер определил, что задержка d вновь подключенного равноуровневого узла p должна быть 3 подмножества данных а перечень, переданный трекером во вновь подключенный равноуровневый узел p, содержит равноуровневые узлы р, р, p, pи р. В этом случае при определенной задержке, равной трем единицам, вновь подключенный равноуровневый узел не сможет найти требуемое подмножество DS2 данных ни в одном из содержащихся в перечне равноуровневых узлов. Для равноуровневых узлов р и р последним полностью принятым подмножеством данных, хранящимся в соответствующем буфере воспроизведения, является DS0, а для равноуровневых узлов р, р и р последним полностью принятым подмножеством данных является DS1. Таким образом, ни один из равноуровневых узлов, содержащихся в перечне, не сможет передать затребованное подмножество DS2 данных во вновь подключенный равноуровневый узел, поскольку оба имеющихся в наличии подмножества данных DS1 и DS0 старше, чем запрошенное подмножество данных DS2, вследствие чего вновь подключенный равноуровневый узел за требуемым подмножеством данных будет вынужден обратиться к источнику потоковой передачи. При обращении к фиг. 4 видно, что указанная ситуация имеет место, если все k случайным образом выбранных соседних равноуровневых узла имеют более высокую задержку по сравнению с задержкой, определенной для вновь подключенного равноуровневого узла, т.е. задержку, лежащую в области β распределения p(d) вероятности.
F
В еще одном варианте осуществления настоящего изобретения вероятность того, что все k соседних равноуровневых узлов будут относиться к области β, может быть выражена как биномиальный эксперимент, в котором определяют вероятность получить нулевое количество успешных испытаний в общем наборе из k испытаний. Полагая успешным испытанием нахождение одного соседнего равноуровневого узла, относящегося к области α, вероятность P нахождения нулевого числа соседних равноуровневых узлов, относящихся к области α, среди k соседних равноуровневых узлов может быть выражена как биномиальный эксперимент с x=0 следующим образом:
F
i
i
i
F
i
i
Таким образом, P(d) выражает вероятность того, что принимающий данные равноуровневый узел с определенной задержкой d будет вынужден принимать требуемые данные информационного материала из сервера потоковой передачи, поскольку ни один соседний равноуровневый узел из k случайным образом выбранных равноуровневых узлов не находится в области α на фиг. 4. Соответственно, вероятность того, что вновь подключенный равноуровневый узел с задержкой d найдет среди k случайным образом выбранных равноуровневых узлов по меньшей мере один соседний равноуровневый узел, относящихся к области α (из которого он сможет принять требуемые данные информационного материала), может быть выражена как 1-P(d). Данный вариант осуществления представляет простую модель, которую трекер может использовать для определения задержки dдля вновь подключенного равноуровневого узла для того, чтобы данные информационного материала могли быть с некоторой вероятностью приняты из соседнего равноуровневого узла.
i
Однако в данной модели не принята во внимание ограниченная пропускная способность каждого из равноуровневых узлов сети. Может иметь место ситуация, в которой вновь подключенный к сети равноуровневый узел с задержкой d нашел среди к случайным образом выбранных равноуровневых узлов один или более соседних равноуровневых узлов, относящихся к области α, но указанные соседние равноуровневые узлы не могут передать данные в указанный вновь подключенный равноуровневый узел вследствие ограничений по пропускной способности. В варианте осуществления настоящего изобретения, описываемом далее, трекер принимает во внимание ограниченную пропускную способность равноуровневых узлов сети.
1
2
3
n+1
n
i
i
i
j
i
Для практических целей будет использоваться дискретное распределение вероятности p(d), поскольку на практике задержку относительно момента воспроизведения реального времени выражают дискретным значением, т.е. в единицах длительности подмножества данных. Таким образом, задержки принимают дискретные значения [d;d, d, …], где для всех n выполняется условие d-d=δ. Дискретное распределение вероятности подразумевает, что ожидаемое количество равноуровневых узлов с задержкой d равно N=p(d)N. Для любой задержки d относительно момента воспроизведения реального времени количество запросов приема данных из равноуровневых узлов с задержкой d равно:
pi
F
i
i
i
pi
i
i
i
Здесь N=(1-P(d))N представляет собой ожидаемое количество равноуровневых узлов с задержкой d, которые будут пытаться принять данные из равноуровневых узлов, относящихся к области α. Причиной того, что попытка приема из других равноуровневых узлов, относящихся к области α, окажется успешной только у подмножества N всех равноуровневых узлов N, имеющих задержку d, является возможность отсутствия у равноуровневых узлов с задержкой d соседних равноуровневых узлов, относящихся к α, в результате чего указанные узлы будут вынуждены принимать данные из источника потоковой передачи.
j
Общее количество запросов приема информации, которое соседние равноуровневые узлы передают в равноуровневые узлы с задержкой d, таким образом, равно:
i
На фиг. 5 показан пример, в котором равноуровневые узлы с задержкой dпередают запросы в соседние равноуровневые узлы, относящиеся к области α, который иллюстрирует, что ни одного запроса не будет передано в соседние узлы, относящиеся к области β (данная ситуация соответствует второму условию в формуле 3).
j
j
j
j
Чтобы определить, сколько из этих запросов будет удовлетворено, примем количество равноуровневых узлов с задержкой d равным N и будем считать, что каждый из указанных узлов может одновременно вести Е(u) загрузок, тогда вероятность того, что равноуровневый узел с задержкой d ответит на l запросов из общего количества R запросов приема информации равна:
bw
r
bw
j
j
j
j
j
j
j
j
j
где Е(u) представляет собой среднее количество одновременных загрузок на равноуровневый узел и определяется распределением p пропускной способности и битовой скоростью b передачи данных. Среднее количество одновременных загрузок на равноуровневый узел, таким образом, рассчитывается как Е(u)=E(p/br). Например, если некоторому равноуровневому узлу задана пропускная способность 1 Мбит/с, а битовая скорость потоковой передачи данных равна 200 кбит/с, то указанный равноуровневый узел сможет одновременно передавать данные в пять других равноуровневых узлов. B(l) определяет долю равноуровневых узлов с задержкой d, которые получат l запросов на прием информации. При l≤Е(u) количество успешных запросов будет равно l×B(l)×N, а при l>E(u) количество успешных запросов будет равно E(u)×B(l)×N. Таким образом, равноуровневые узлы с задержкой d примут R запросов приема информации, и каждый из указанных запросов случайным образом попадет в один узел из множества N равноуровневых узлов, при этом распределение запросов приема информации может быть смоделировано биномиальным распределением.
j
j
Следовательно, ожидаемое количество успешных ответов, которым равноуровневые узлы с задержкой d ответят на запросы приема информации из соседних равноуровневых узлов (т.е. нагрузка на равноуровневые узлы с задержкой d) составит:
и потому ожидаемое количество равноуровневых узлов указанной сети Р2Р, осуществляющих потоковую передачу, равно общему количеству успешных загрузок:
j
j
j
Вероятность того, что запрос приема, который соседний равноуровневый узел делает в равноуровневые узлы с задержкой d, окажется успешным, может быть рассчитана как отношение ожидаемого количества успешных ответов и указанного общего количества запросов приема информации, т.е. L/R.
j
F
j
i
F
i
j
j
i
i
i
i
j
j
i
Как результат, вероятность того, что запрос приема из равноуровневого узла с задержкой d попадет в область α, равна (1-P(d)), т.е. вероятность того, что равноуровневый узел с задержкой d найдет среди к случайным образом выбранных равноуровневых узлов по меньшей мере один соседний равноуровневый узел, относящихся κ области α, из которого он сможет загрузить запрошенные данные информационных материалов, может быть выражена как 1-P(d). Вероятность того, что один из указанных запросов в равноуровневые узлы, относящиеся к области α, действительно поступит в равноуровневые узлы, имеющие конкретную задержку d, равна p(d)/Pα (выведено из формулы 3, которая определяет данную вероятность для количества N равноуровневых узлов с задержкой d). Данные вероятности в модели являются независимыми, и вероятность того, что равноуровневый узел, имеющий задержку d, сможет принять информационный материал из соседнего равноуровневого узла, имеющего конкретную задержку d (с учетом ограниченной пропускной способности) может быть выражена как произведение указанных трех вероятностей. Отсюда следует, что вероятность того, что равноуровневый узел, имеющий задержку d, осуществит успешную загрузку из сети Р2Р, т.е. примет данные из любого равноуровневого узла, имеющего задержку менее d, может быть выражена как сумма вероятностей:
j
j
Таким образом, суммирование охватывает все равноуровневые узлы, имеющие задержку менее d, а не только равноуровневые узлы, имеющие конкретную задержку d.
Ожидаемый выигрыш для источника потоковой передачи связан с вероятностью успешного приема каждым равноуровневым узлом в сети:
Однако выигрыш может быть выражен и более просто, как отношение успешных загрузок в равноуровневые узлы сети к общему количеству равноуровневых узлов в сети, т.е.:
Данный способ расчета выигрыша концептуально проще и более эффективен в вычислительном отношении. Обе формулы (7) и (8) дают одинаковый результат.
i
Резюмируя данный вариант осуществления настоящего изобретения, отметим, что ситуация, в которой принимающий данные равноуровневый узел с определенной задержкой d будет вынужден принимать требуемые данные информационного материала из сервера потоковой передачи, возникает, если:
i
(a) ни один соседний равноуровневый узел из к случайным образом выбранных равноуровневых узлов не находится в области α, т.е. ни один соседний равноуровневый узел не имеет задержку d - δ или менее, или
(b) среди к случайным образом выбранных равноуровневых узлов один или более соседних равноуровневых узлов находятся в области α, но указанные соседние равноуровневые узлы не могут отдавать данные из-за ограниченной пропускной способности.
s
i
i
Иными словами, несмотря на то, что в области α, показанной на фиг. 4, могут быть соседние равноуровневые узлы, у указанных узлов из-за ограниченной пропускной способности может не быть возможности передать данные в запрашивающий равноуровневый узел. Вышеприведенная формула 6 учитывает указанные ограничения пропускной способности и дает возможность рассчитать P(d), т.е. вероятность того, что равноуровневый узел, имеющий задержку d, выполнит успешную загрузку из сети Р2Р.
i
Соответственно, в данном варианте осуществления настоящего изобретения задержка d вновь подключенного равноуровневого узла определяется трекером с использованием принципа, выраженного формулой (6), благодаря чему запрошенные данные информационного материала с достаточно высокой вероятностью могут быть приняты из одного из k случайным образом выбранных равноуровневых узлов. В отличие от вышеописанных вариантов осуществления, данный вариант осуществления принимает во внимание ограничения в пропускной способности потоковой передачи.
i
В предыдущем варианте осуществления настоящего изобретения трекер не принимает во внимание ситуацию, в которой имеется совместная вероятность задержки и пропускной способности p(u,d). Моделируя задержку и пропускную способность с использованием совместной вероятности случайных событий, можно более качественно определить задержку для вновь подключенного равноуровневого узла. Распределение вероятности задержки d относительно момента воспроизведения реального времени представляет собой сумму по u совместной
вероятности p(u, d):
bw
bw
где и в соответствии с вышеприведенным описанием представляет собой количество одновременных загрузок для равноуровневого узла и определяется распределением p пропускной способности и битовой скоростью br передачи данных. Количество одновременных загрузок для равноуровневого узла u=p/br. В более совершенном варианте осуществления трекер принимает во внимание тот факт, что равноуровневые узлы, запрашивающие прием данных информационного материала, могут иметь различную пропускную способность u, т.е. различные равноуровневые узлы в сети Р2Р имеют возможность одновременно осуществлять неодинаковое количество загрузок данных. К примеру, в вариантах осуществления, показанных на фиг. 2 и 3, запрос, принимаемый трекером, будет поэтому дополнительно содержать пропускную способность равноуровневого узла по передаче данных.
i
j
Количество запросов загрузки из равноуровневых узлов с задержкой d в равноуровневые узлы с задержкой d и пропускной способностью по передаче данных и равна:
j
Аналогично, общее количество запросов приема информации, которое соседние равноуровневые узлы передают в равноуровневые узлы с задержкой d и пропускной способностью u, равно:
j
ju
j
ju
Чтобы определить, сколько из этих запросов будут удовлетворены, примем количество равноуровневых узлов с задержкой d и пропускной способностью u по передаче данных равным N, тогда вероятность того, что равноуровневый узел с задержкой d и пропускной способностью по передаче данных u ответит на l запросов приема данных из общего количества R запросов приема данных, равна:
ju
j
j
j
где N=p(u, j)N представляет собой ожидаемое количество равноуровневых узлов с задержкой d и пропускной способностью по передаче данных u. Следовательно, ожидаемое количество успешных ответов, которыми равноуровневые узлы с задержкой d и пропускной способностью u по передаче данных ответят на запросы приема информации из соседних равноуровневых узлов (т.е. нагрузка на равноуровневые узлы с задержкой d и пропускной способностью u по передаче данных) равна:
и потому ожидаемое количество равноуровневых узлов указанной сети Р2Р, осуществляющих потоковую передачу, равно общему количеству успешных загрузок:
i
По аналогии с причинами, изложенными выше в связи с формулой 6, вероятность того, что равноуровневый узел с задержкой d осуществит успешную загрузку из сети Р2Р, теперь может быть выражена как:
а выигрыш будет выражаться как в формулах (8) или (7).
В других вариантах осуществления настоящего изобретения, с одной стороны, может использоваться ранее обсуждавшаяся взаимосвязь между распределением p(d) задержек и вероятностью того, что вновь подключенный равноуровневый узел будет принимать данные из равноуровневого узла, имеющего меньшую задержку по сравнению с задержкой, определенной для указанного вновь подключенного равноуровневого узла; с другой стороны, для оптимизации указанного распределения задержек с целью достижения наивысшей возможной вероятности того, что указанный вновь подключенный равноуровневый узел будет принимать данные информационного материала из должным образом выбранного равноуровневого узла сети, может использоваться выигрыш.
При этом в качестве критерия для оценки распределения p(d) используют ожидаемый выигрыш для сервера потоковой передачи. После нахождения оптимального распределения с использованием известного алгоритма эволюционной оптимизации для каждого равноуровневого узла на основании указанного оптимального распределения задается задержка по отношению к моменту воспроизведения реального времени сервера потоковой передачи просто путем выбора трекером значений задержки из указанного оптимального распределения и задания выбранных значений равноуровневым узлам. При поиске оптимального распределения принимают во внимание ранее упомянутое среднее количество E(ui) одновременных загрузок, приходящихся на равноуровневый узел. В варианте осуществления настоящего изобретения учитывают изменения E(ui) и используют их для подгонки p(d) с целью оптимизации под периодические изменения в сети Р2Р. В первом варианте осуществления с целью оптимизации распределение задержек считают известным распределением, например, распределением Пуассона. Поскольку на форму стандартных распределений влияют параметры указанных распределений, необходимо лишь рассмотреть пространство значений этих параметров. Если предполагается, что случайная задержка d описывается распределением Пуассона, то оптимизировать следует параметр λ указанного распределения.
i
i
Как ясно из фиг. 6, для данной задержки d, определенной трекером для вновь подключенного равноуровневого узла, можно варьировать параметр λ до тех пор, пока не будет достигнуто наибольшее значение вероятности. Следовательно, максимизация вероятности того, что вновь подключенный равноуровневый узел будет принимать запрошенные данные информационного материала из равноуровневого узла сети равносильна максимизации выигрыша в нагрузке на пропускную способность сервера потоковой передачи. Например, в примере распределение Пуассона на фиг. 6 для определенной задержки d=10 максимальная вероятность достигается при λ=10.
i
i
i
i
Перед оптимизацией распределения в модуле оптимизации, который управляет оптимизацией распределения p(d|λ), должно быть задано количество к случайным образом выбранных соседних равноуровневых узлов и значение Е(u), т.е. среднее количество одновременных загрузок на равноуровневый узел. После нахождения почти оптимального значения λ, которое максимизирует ожидаемый выигрыш для сервера потоковой передачи, путем выполнения генетического алгоритма (GA) на пространстве λ, трекер затем может начать использовать это оптимальное распределение для выбора значения задержки d для вновь подключенного равноуровневого узла p. На фиг. 7 показан выигрыш по нагрузке на источник потоковой передачи для различных значений λ в предположении, что трекер передает во вновь подключенный равноуровневый узел перечень из k=50 случайным образом выбранных соседних равноуровневых узлов, а Е(u)=3. При этих конкретных значениях система достигнет выигрыша около 82%. По оси x отложена задержка равноуровневого узла.
i
В еще одном варианте осуществления настоящего изобретения предполагается, что распределение p(d) задержек не является распределением заранее определенного вида, а должно оптимизироваться как гистограмма вероятностей. Польза такого способа обусловлена тем, что форма распределения не ограничивается конкретным распределением, а может быть произвольной. В данном контексте предполагается, что наибольшее число столбцов гистограммы, т.е. наибольшая возможная задержка d, равно Dmax. Таким образом, в целевом представлении в виде гистограммы будет только Dmax столбцов (называемых частотными значениями). На фиг. 8 Dmax выбрано равным 21, каждый столбец может принимать значения в интервале [0; 1], что означает, что пространство поиска в данной оптимизации будет содержать 21 переменную для принятия решения. Частоты гистограммы в сумме должны давать 1 (из-за ограничения, налагаемого тем, что гистограмма должна быть распределением вероятности), и хорошим алгоритмом оптимизации, который дает возможность учесть эти ограничения, является генетический алгоритм (GA). С теми же исходными значениями, которые использовались при оптимизации распределения Пуассона, показанного на фиг. 7, т.е. при k=50 и E(ui)=3, оптимальная гистограмма, показанная на фиг. 8, дает ожидаемый выигрыш около 85%.
Несмотря на то, что настоящее изобретение раскрыто со ссылкой на конкретные примерные варианты осуществления, специалисту в данной области техники очевидны разнообразные изменения, модификации и т.п. Раскрытые варианты осуществления поэтому не ограничивают объем настоящего изобретения, определяемый прилагаемой формулой изобретения.