СПОСОБ И УСТРОЙСТВО ДЛЯ БЛАГОПРИЯТНОГО ДЛЯ СЕТИ СОВМЕСТНОГО КЭШИРОВАНИЯ

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

Настоящее изобретение относится к технологиям связи, и в частности - к способу и устройству для благоприятного для сети совместного кэширования.

УРОВЕНЬ ТЕХНИКИ

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

РАСКРЫТИЕ ИЗОБРЕТЕНИЯ

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

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

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

Эти и другие особенности будут более ясно поняты из последующего подробного описания, рассматриваемого вместе с сопроводительными чертежами и формулой изобретения.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

Фиг. 1 - схематическое представление варианта осуществления сетевой архитектуры.

Фиг. 2 - схематическое представление варианта осуществления схемы распределенного TE и совместного кэширования.

Фиг. 3 - схематическое представление другого варианта осуществления сетевой архитектуры.

Фиг. 4 - схематическое представление варианта осуществления средства кэширования.

Фиг. 5 - последовательность операций варианта осуществления способа кэширования.

Фиг. 6 - график варианта осуществления результатов моделирования совместного кэширования.

Фиг. 7 - график другого варианта осуществления результатов моделирования совместного кэширования.

Фиг. 8 - график другого варианта осуществления результатов моделирования совместного кэширования.

Фиг. 9 - карта варианта осуществления результатов моделирования использования сети.

Фиг. 10 - карта другого варианта осуществления результатов моделирования использования сети.

Фиг. 11 - схематическое представление варианта осуществления блока передачи/приема.

Фиг. 12 - схематическое представление варианта осуществления универсальной компьютерной системы.

ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

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

В данной работе раскрыты устройство и способ кэширования контента, которые могут улучшать производительность сети, например, по сравнению с предшествующими схемами кэширования контента. Кэширование контента может осуществляться, используя множество кэш-серверов, которыми можно управлять совместным способом и/или распределенным способом. Производительность сети можно улучшать, совместно выполняя множество требований кэширования контента и/или множество эксплуатационных требований для сети, таких как те, которые могут быть установлены поставщиком Интернет-услуг. Эксплуатационные требования могут содержать требования TE, которые включают в себя балансировку трафика на линиях связи по сети, защиту возможных дефектных линий связи, достижение показателей в соглашениях об уровне обслуживания или комбинации любого одного или большего количества из указанных ранее.

Устройство и способ могут объединять схему TE и схему совместного кэширования (CC) для распределенных сетевых ресурсов. Способ может содержать получение стоимости TE (или виртуального TE) из набора задач оптимизации для увеличения эффективности сети с CC. Задачи оптимизации могут быть сформулированы в соответствии с множеством предположений TE, например, для каждого рассматриваемого эксплуатационного требования. Предположения TE могут включать в себя одного провайдера сетевых услуг, обычную модель сети, представление логической кластеризации, непротиворечивые сетевые эксплуатационные требования, которые включают в себя непротиворечивое требование оптимизации, или комбинации любого одного или большего количества из указанных ранее. Стоимость TE можно вычислять для каждой сетевой линии связи в соответствии с эксплуатационными требованиями сети, такими как требования TE, и может использоваться для управления множеством взаимодействующих кэшей для перемещения контента, замещения контента и/или дублирования контента.

В предположениях для формулировки задачи оптимизации (для TE и CC) множество критериев оптимизации сети и услуг можно рассматривать для одного провайдера сетевых услуг. Провайдер сетевых услуг может содержать и иметь множество узлов CONA. Узлы CONA могут соединяться друг с другом в обычной неиерархической модели сети. Обычная неиерархическая модель сети может также включать в себя случай иерархической модели сети. Сетевые требования могут содержать балансировку нагрузки и стоимость линии связи с кусочно-линейной характеристикой. Балансировку нагрузки можно устанавливать в соответствии с формулировкой задачи оптимизации, с распределенным алгоритмом и CC, как описано дополнительно ниже. Множество узлов CONA можно также группировать или кластеризовать и обрабатывать как один логический узел, например, когда множество узлов мультиплексора доступа к цифровой абонентской линии (DSLAM) CONA подключено через коммутатор Ethernet. Объединенная сеть может содержать множество подсистем, например, подсистему маршрутизации, подсистему кэширования и/или другие подсистемы. У каждой подсистемы может быть соответствующее требование оптимизации. Однако, общая цель работы всей сети может быть непротиворечивой, причем требования различных подсистем не могут находиться в противоречии друг с другом, например, в соответствии с конструкцией и/или осуществлением.

Фиг. 1 показывает вариант осуществления сетевой архитектуры 100, который может быть сконфигурирован в общем случае в «плоской» структуре. Сетевая архитектура 100 может содержать множество узлов 110-160, которые могут быть соединены друг с другом в обычной неиерархической модели сети, например, в ячеистой топологии. Соответственно, любой из узлов 110-160 может переключаться между передачей трафика напрямую или через другой узел (узлы) без иерархических ограничений или зависимостей. Сетевая архитектура 100 может соответствовать любой сети передачи данных, которая обеспечивает услуги для клиента/абонентов, которая включает в себя сети на основе Ethernet, сети на основе Интернет-протокола (IP), пассивные оптические сети (PON), сети цифровой абонентской линии (DSL), беспроводные сети, другие сети передачи данных или их комбинации. В одном из вариантов осуществления сетевая архитектура 100 может соответствовать корпоративной сети или магистральной сети, которые обычно имеют «плоскую» структуру.

Узлы 110-160 могут быть сконфигурированы для перемещения трафика или данных в сети. Трафик может содержать пакеты (например, пакеты IP), кадры (например, кадры Ethernet), сообщения, сигналы или комбинации любого одного или большего количества из вышеизложенного. Например, узлы 110-160 могут включать в себя мосты, маршрутизаторы и/или коммутаторы, которые принимают, обрабатывают и/или передают трафик в сети. Узлы 110-160 могут перемещать сетевой трафик, используя множество линий связи или маршрутов (как обозначено сплошными линиями на Фиг. 1), который может определяться, используя TE, и могут поддерживать CC по меньшей мере между некоторыми из узлов. Узлы 110-160 могут представлять узлы физического уровня, которые принимают, обрабатывают и/или передают трафик на сетевом физическом уровне. Узлы 110, 120 и 130 могут также быть сконфигурированы для перемещения контента и/или услуг, которые могут запрашивать один или большее количество конечных пользователей. Например, узлы 110, 120 и 130 могут быть узлами CONA, которые принимают, перемещают, кэшируют и обмениваются трафиком контента друг с другом (как обозначено линиями со стрелками на Фиг. 1) в сети с возможностью CONA. Узлы 110, 120 и 130 могут представлять узлы CONA, которые обрабатывают трафик в плоскости контента, и соответствующие узлы физического уровня, которые обрабатывают сетевой трафик на физических уровнях.

Контент может содержать данные, голосовую информацию, видеоинформацию, мультимедийную информацию, информацию из Интернет и/или любой контент, ориентированный на конкретное применение, например, контент, относящийся к играм. В некоторых вариантах осуществления конечный пользователь может быть любым пользовательским устройством, соединенным с сетью, например, с любым из узлов 110-160. В дополнительном варианте осуществления сетевая архитектура может соответствовать ISP (поставщику интернет-услуг), и конечный пользователь может соответствовать поставщику контента или клиенту ISP. Например, конечный пользователь может быть сопоставлен с устройством связи в доме клиента или с пользовательским устройством, таким как оптический сетевой терминал (ONU) или приемопередающее устройство сверхскоростной DSL (VDSL) в городском поселении (VTU-R). Альтернативно, конечный пользователь может соответствовать домашнему оборудованию связи, например, телевизионной приставке, стационарному персональному устройству (такому, как настольный компьютер), или мобильному персональному устройству, такому, как сотовый телефон (который включает в себя так называемые «интеллектуальные» телефоны (то есть сотовые устройства, имеющие возможность передачи голоса и данных)), ноутбук или переносное вычислительное устройство, такое, как планшетный компьютер.

В сетевой архитектуре 100 стоимость TE может быть получена из набора задач оптимизации, которые могут увеличивать эффективность сети и поддерживать CC между узлами CONA. Задачи оптимизации могут быть разработаны или сформулированы в соответствии с некоторыми требованиями или необходимыми свойствами вычислительных систем. Например, может быть необходимо, чтобы системное решение было по существу распределенным для улучшения масштабируемости данного решения в сети. Может также быть необходимо избежать использования целочисленного программирования (IP) при формулировке задач, если возможно, что может быть результатом формулировки задачи с недетерминированным полиномиальным (NP) временем. Дополнительно, может быть необходимо получить решение, которое является относительно легко наращиваемым или расширяемым для настройки новых подсистем, которые могут быть добавлены к сети. Например, новая подсистема «Облако памяти» (SC) (совокупность устройств хранения данных) может быть добавлена к объединенной подсистеме TE и подсистеме CC без необходимости значительного перепроектирования результирующей объединенной системы TE, CC и SC.

Требования TE можно рассматривать совместно для множества классов трафика в сети, например, не делая различий между различными классами трафика. Классы трафика могут содержать передачи данных между кэшами, например, между узлами 110, 120 и 130, которые могут обрабатываться аналогично другому сетевому трафику. Совместная задача TE и CC (TECC) может быть сформулирована следующим образом:

Эти шесть вышеупомянутых ограничений (помечены (1)-(6)) представляют множество ограничений для формулировки задачи TECC. Первое ограничение (например, ограничение (1)) может соответствовать требованию TE (например, балансировки нагрузки). В ограничении (1) t_ij - трафик между кэшами (из-за передачи данных от узла i к узлу j), I_e (i, j) - матрица маршрутизации (значения которой могут быть равны приблизительно единице, если линия связи e находится на прямом маршруте от i до j), c_e - физическая емкость (например, пропускная способность) линии связи e, и b_e - фоновый трафик, вызванный другими приложениями, по линии связи e. Ограничение (1) является требованием TE для балансировки нагрузки для линии связи, но могут также использоваться другие требования, такие как одна или большее количество кусочно-линейных функций стоимости линии связи для фиксации полной стоимости сети.

Ограничение (2) может гарантировать передачу данных между кэшами, например, соответствовать требованию CC. В ограничении (2) узел j может принимать объект k данных запроса с вероятностью q_j ^k. Если j не имеет локальной копии (например, y_j ^k=0, таким образом 1-y_j ^k=1), то j должен извлекать объект из другого узла i, который имеет данный контент (например, y_j ^k=1). Для любого объекта k, когда y_j ^k=1 (например, узел j имеет локальную копию) или=0 (например, узел i не имеет локальной копии), тогда передача данных между кэшами из i в j может не происходить (например, y_i ^k (1-y_j ^k)=0). Ограничение (3) может гарантировать, что копия может существовать в каком-то узле. В ограничении (3) любой объект k может быть скопирован с помощью одного или большего количества узлов. Ограничение (4) может соответствовать предельному значению объема запоминающего устройства кэша. В ограничении (4) весь объем запоминающего устройства, используемый копиями, не может превышать доступный физический объем запоминающего устройства (например, физический объем диска) узла i.

Ограничение (5) может гарантировать, что запоминающее устройство кэша является достаточно большим, так что весь объект данных может быть скопирован с помощью доступных кэшей, например, при объединении. Запоминающее устройство кэша, доступное в сетевых узлах, которые рассматривают, может быть недостаточно большим. Также один или большее количество виртуальных узлов CONA могут быть введены в соответствии с запросом (так называемое «динамическое кэширование»), например, один или большее количество серверов, которые служат источником контента. Серверы могут сохранять только соответствующие объекты и обслуживать запросы на такие сохраненные объекты. Ограничение (6) может представлять двоичную переменную, чтобы показать, хранятся или нет объекты в кэше. В ограничении (6) y_j ^k=1, если объект k хранится локально в узле i, и y_j ^k=0 иначе. Вышеизложенная задача TECC может воплощаться, используя программу квадратичного программирования.

В другом варианте осуществления упрощенная задача TECC может быть сформулирована, например, удаляя квадратичные термины в формулировке приведенной выше задачи TECC. Индикаторная переменная x_ij ^k может быть введена для представления передачи данных между кэшами (например, x_ij ^k=1, если узел i перемещает объект k в узел j). Использование индикаторной переменной может упрощать задачу TECC, которая может затем воплощаться, используя программу целочисленного программирования вместо программы квадратичного программирования. Однако формулировка TECC в соответствии с программой целочисленного программирования может все еще быть трудной для решения.

В другом варианте осуществления задачи TECC каждый узел CONA может воплощать по меньшей мере частичное кэширование, где часть объекта контента может локально кэшироваться в одном или большем количестве узлов CONA. Эта форма «распределенного кэширования» по меньшей мере части контента в одном или большем количестве локальных узлов CONA значительно улучшает производительность сети, особенно в видео- и мультимедийных приложениях. Задача TECC для частичного кэширования может быть сформулирована следующим образом:

Ограничение (12) может указывать, что когда узел j имеет локальную копию объекта k, тогда j может не извлекать тот же самый объект из других узлов. Формулировка задачи TECC для частичного кэширования может воплощаться, используя программу целочисленного программирования. Реализация частичного кэширования может использоваться для кэширования объектов видео контента. Например, каждый видеофильм может иметь продолжительность приблизительно от 1,5 до приблизительно двух часов и иметь размер в пределах от приблизительно 200 мегабайтов (Мб) до приблизительно четырех гигабайтов (Гб), например, используя кодек H.264 или аналогичное видео кодирование, и степень сжатия, приблизительно равную двум. Пользователь может смотреть первый видеофильм в течение некоторого времени и затем выполнить ускоренную перемотку вперед к последующей части в видеофильме, или переключиться на второй видеофильм до того, как посмотрит весь первый видеофильм. В таких сценариях совместное кэширование CONA может быть неэффективным, если каждый узел CONA сконфигурирован для кэширования всего видео объекта. Частичное кэширование может предоставлять возможность каждому узлу CONA сохранять часть объекта вместо всего объекта, что может быть выгодным в случае по существу больших видео объектов.

В одном из вариантов осуществления задача TECC может быть сформулирована в соответствии с индикаторной переменной x_ij ^k, которая представляет частично кэшируемую часть объекта k, который перемещают из i в j. Задача TECC может быть сформулирована следующим образом:

Ограничение (16) может гарантировать, что (a) любой объект кэшируется в сети, и (b) любой узел i может получить по существу полную копию каждого объекта из одного или большего количества других узлов. Ограничение (19) может указывать, что часть объекта k, которую узел i может загружать из j, является самое большее частью, которую i локально кэшировал (например, узел i не может обеспечивать больше контента, чем он имеет). Ограничение (20) может указывать, что каждый объект контента может делиться на части для целей сохранения и кэширования, и что размер части по меньшей мере равен . Когда существует остаток объекта контента (например, s_k mod ), этот остаток можно извлекать из источника (например, из сервера контента) и его можно нигде не кэшировать в узлах CONA. Вышеуказанная формулировка задачи TECC может воплощаться, используя программу линейного программирования, которую можно проще решить, чем программу квадратичного или целочисленного программирования. Однако, воплощение ограничения (12), например, , в формулировке или алгоритме может быть сложным для решения, поскольку x_ij ^k не указывает, насколько различны кэшируемые части объекта, хранящиеся в двух узлах.

Так как различия между частями объекта, кэшируемыми двумя узлами, могут быть не известны, может использоваться более простая формулировка задачи. Также, задача TECC может быть сформулирована в соответствии с индикаторной переменной x_i ^k, которая представляет частично кэшируемую часть объекта k в узле i, следующим образом:

В приведенной выше формулировке для каждого объекта определяют значение в процентах, которое каждый узел CONA может кэшировать локально, но решение о том, какую часть каждый узел может кэшировать для каждого объекта, может не определяться. Соответственно, вычисляют значение в процентах от любого рассматриваемого объекта, которое каждый узел CONA может кэшировать локально. Вычисление значения в процентах от объектов, которые могут кэшироваться каждым узлом CONA, может не подходить для всех рассматриваемых объектов, так как некоторые объекты могут быть относительно большими, а другие объекты могут быть относительно маленькими. Дополнительно, некоторые объекты можно считать более важными, чем другие объекты. В таких сценариях объекты можно классифицировать в один или большее количество соответствующих классов, например, в соответствии с их уровнями важности, приоритетами (которые определяются пользователем или оператором или иным образом), размерами и/или другой классификацией. Таким образом, задача может быть повторно сформулирована, вводя концепцию «класса объекта». Приведенная выше формулировка задачи TECC может воплощаться, используя программу линейного программирования.

В другом варианте осуществления задача TECC может быть сформулирована в соответствии с первой индикаторной переменной x_ij ^k, которая представляет часть объекта k, которую посылают от узла i к узлу j, и в соответствии со второй индикаторной переменной y_i ^k, которая представляет часть объекта k, которую кэшируют с помощью узла i. Задача TECC может быть сформулирована следующим образом:

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

Ie(i,j) Индикаторная переменная линия связи-маршрут, =1 означает, что линия связи e находится на прямом маршруте от i до j ce Емкость линии связи e be Фоновый трафик по e sk Размер объекта k νi Объем (емкость запоминающего устройства) узла i CONA yi k Двоичная переменная, yi k=1, если узел i имеет объект k в своем локальном кэше, иначе 0 qi k Частота использования объекта k, наблюдаемая локально узлом i (локальное представление),

Приведенные выше задачи TECC могут быть сформулированы и решены для распределения сетевых ресурсов и увеличения эффективности сети. Например, таблица 2 показывает решение, которое может быть получено, решая приведенную выше формулировку задачи TECC для сети 100 в соответствии с ограничениями (14)-(21):

В приведенном выше решении могут быть сделаны два наблюдения. Во-первых, диагональный элемент в каждой строке таблицы 2 может доминировать, например, может быть больше, чем остальные элементы в строке, так как часть объекта, которую каждый узел может обеспечивать к другим узлам, не может быть больше, чем часть, которую данный узел может кэшировать локально (например, ). Во-вторых, сумма элементов в каждом столбце не может быть меньше, чем приблизительно единица, так как каждый узел CONA может иметь возможность получать полную копию объекта ( ). В соответствии с этим решением, подсистема CC может иметь возможность вычислять план по разделению каждого объекта и сохранению части объекта в каждом узле CONA.

Таблица 3 показывает решение, которое может быть получено с помощью решения формулировки задачи TECC для сети 100 в соответствии с ограничениями (22)-(28):

Согласно приведенному выше решению три узла CONA 110, 120 и 130 могут кэшировать приблизительно 60 процентов, 20 процентов и 30 процентов, соответственно, объекта в классе 1. Сумма элементов в строке таблицы 3 может быть больше, чем приблизительно единица (например, ).

В одном из вариантов осуществления распределенный алгоритм может быть получен из декомпозиции приведенных выше задач оптимизации. Например, формулировку задачи TECC в соответствии с ограничениями (22)-(28) можно разделить на подзадачу TE сети и подзадачу CC сети. Когда решают подзадачу TE, можно вычислять стоимость p_e TE сети для множества линий связи. Стоимость p_e TE может быть стоимостью маршрутизации текущего трафика по линии связи e. Вычисленная стоимость TE может объединяться по маршруту в сети, например, по последовательности линий связи. Подзадача CC может быть решена средствами локального кэширования (например, узлами CONA), получая вычисленную стоимость TE и вычисляя оптимальное значение x_i ^k для каждого объекта, которое указывает, какую часть объекта каждый кэш может локально хранить. Индикаторная переменная x_i ^k может быть вычислена в соответствии со стоимостью TE.

Фиг. 2 показывает вариант осуществления схемы 200 распределенного TE и CC. Схема 200 распределенного TE и CC может воплощаться в сети с возможностью CONA, например, в сетевой архитектуре 100, изображенной на Фиг. 1. Схема 200 распределенного TE и CC может решать задачу TECC, решая подзадачу TE и затем подзадачу CC сети. Сеть может содержать узлы 210 и 220 CONA и другие узлы 225 (например, узлы, не являющиеся узлами CONA), которые включают в себя узлы 230, 240 и 250. Узлы 210-250 могут быть сконфигурированы по существу аналогично соответствующим узлам в сетевой архитектуре 100. Узлы 210-250 могут обрабатывать сетевой трафик на физическом уровне (и/или на любом другом уровне модели взаимодействия открытых систем (OSI)), и узлы 210 и 220 могут также быть узлами CONA, которые содержат средства локального кэширования, которые поддерживают CC.

Узлы 210-250 могут быть расположены так, как показано на Фиг. 2, причем узлы 225 могут располагаться в тракте между узлами 210 и 220 CONA. Также, узлы 230, 240 и 250 могут быть транзитными узлами, которые перемещают трафик, который включает в себя объекты контента, между узлами 210 и 220. С помощью решения подзадачи TE, стоимость каждой линии связи, например, p_e1(t) между узлами 230 и 240 и p_e2(t) между узлами 240 и 250, может вычисляться, например, в соответствии с количеством или объемом трафика по линиям связи. Линии связи обозначены пунктирными линиями на Фиг. 2. Вычисленную стоимость линии связи можно затем передавать к узлам 210 и/или 220 CONA (как обозначено сплошными линиями со стрелками на Фиг. 2). Полная стоимость линии связи t_k (t) для объединенных линий связи может вычисляться с помощью средства TE, которое может соответствовать одному или большему количеству узлов или серверов в сети, и передаваться к узлам 210 и/или 220 CONA, или может вычисляться узлами 210 и/или 220 в соответствии с переданной стоимостью линии связи, например, p_e1(t) и p_e2(t). Узлы 210 и/или 220 могут затем использовать стоимость линии связи для решения подзадачи CC и таким образом для вычисления локальной политики кэширования, например, локальной политики размещения копии или частей объекта, и они могут определять, как эти политики воплощают.

Фиг. 3 показывает вариант осуществления другой сетевой архитектуры 300, которая может иметь иерархическую структуру. Сетевая архитектура 300 может содержать множество узлов 310-350, которые могут быть соединены друг с другом в иерархической модели сети, например, в древовидной топологии. Соответственно, узлы могут быть классифицированы или организованы в различных иерархиях или уровнях, причем количество узлов на более низких иерархиях может быть больше количества узлов на более высоких иерархиях. Таким образом средняя пропускная способность на один узел на нижних иерархиях может быть меньше по сравнению с верхними иерархиями. Дополнительно, узлы на том же самом уровне могут не осуществлять связь друг с другом, но могут осуществлять связь с другими узлами на более высоких или более низких иерархиях. Например, узел 310 может быть расположен на первом уровне и может осуществлять связь с узлами 320 и 330 на более низком втором уровне, которые могут не осуществлять связь друг с другом непосредственно. Узел 320 может осуществлять связь с узлами 340 на более низком третьем уровне, которые могут не осуществлять связь друг с другом непосредственно. Точно так же узел 330 может осуществлять связь с узлами 350 на третьем уровне, которые также могут не осуществлять связь друг с другом непосредственно.

Сетевая архитектура 300 может быть особым случаем сетевой архитектуры 100, и узлы 310-350 могут быть сконфигурированы по существу аналогично соответствующим узлам 110-150. Например, узлы 310, 320 и 330 могут быть узлами CONA, а узлы 340 и 350 могут быть узлами, которые не являются узлами CONA. Таким образом, узлы 310, 320 и 330 могут кэшировать объекты контента в соответствии с любой из приведенных выше задач TECC. В одном из вариантов осуществления сетевая архитектура 300 может соответствовать сети доступа, где DSLAM, широкополосный сервер удаленного доступа (BRAS) и/или маршрутизаторы магистрали могут формировать иерархическую структуру с множеством уровней (например, с тремя уровнями). Например, узел 310 может содержать маршрутизатор магистрали, каждый из узлов 320 и 330 может содержать BRAS, и узлы 340 и 350 могут содержать множество DSLAM.

Для решения задачи TECC в сетевой архитектуре 300 различная стоимость линии связи (например, стоимость TE) может быть назначена линиям связи в различных иерархиях, например, ручным способом с помощью оператора. Например, если обычно DSLAM в относительно небольшой географической области (например, в микрорайоне, в районе с одним почтовым индексом, в городе или на другой территории, например, площадью приблизительно 5, приблизительно 10, приблизительно 20 или приблизительно 50 квадратных километров) подключены через коммутаторы Ethernet, то стоимость линий связи, которые подключают DSLAM, может быть по существу ниже, чем стоимость линий связи, которые подключают другие узлы BRAS. Стоимость можно предварительно вычислять, корректировать вручную заранее или оперативно (например, в режиме реального времени) или вычислять с помощью алгоритма по запросу.

Фиг. 4 - схематическое представление варианта осуществления средства 400 кэширования. Средство кэширования может быть расположено в узле CONA и может быть сконфигурировано для управления CC. Также, средство 400 кэширования может воплощать распределенный алгоритм CC (например, для решения подзадачи CC), генерировать политики CC, обновлять контент кэша согласно политикам CC, или их комбинации. Средство 400 кэширования может содержать средство 410 политики кэширования, компонент 420 алгоритма замещения, компонент 430 передачи данных между кэшами, компонент 440 получения статистической информации и средство 450 сохранения. Компоненты средства 400 кэширования могут быть расположены, как показано на Фиг. 4, и могут воплощаться, используя аппаратные средства, программное обеспечение или и то, и другое.

Средство 410 политики кэширования может содержать компонент 412 политики сети, компонент 414 глобальной политики кэширования и компонент 416 локальный политики кэширования. Компонент 412 политики сети может быть сконфигурирован для получения информации политики сети, например, информации обратной связи TE в соответствии со стоимостью TE линии связи, например, p_e. Когда рассматривают другие эксплуатационные требования, стоимость линии связи может определяться в контексте таких требований. Компонент 414 глобальной политики кэширования может быть сконфигурирован для изменения набора параметров, относящихся к перемещаемым частям объекта, например, x_j ^k, и соответствующих вероятностей, например, q_j ^k, с помощью другого средства или компонента кэширования (в других узлах CONA). Компонент 414 глобальной политики кэширования может осуществлять распределенный алгоритм для вычисления политики кэширования. Политика кэширования может содержать оптимальную стратегию размещения копии, например, x_i ^k, которая может быть входной информацией для компонента 416 локальной политики кэширования. Компонент 416 локальной политики кэширования может быть сконфигурирован для определения, какую часть каждого объекта следует локально кэшировать в соответствии с политикой кэширования, вычисленной с помощью компонента 414 глобальной политики кэширования. Соответственно, компонент 416 локальной политики кэширования может давать команду компоненту 430 передачи данных между кэшами о том, какие части объекта следует извлекать из других узлов.

Компонент 430 передачи данных между кэшами может быть сконфигурирован для приема частей объекта и передачи частей объекта в средство 450 сохранения для кэширования. Компонент 420 алгоритма замещения может быть сконфигурирован для определения, какие объекты или части должны быть замещены, например, удалены и направлены к другим узлам, и может давать команду средству 450 сохранения сделать это. Компонент 440 получения статистической информации может быть сконфигурирован для получения различной статистической информации от компонента 414 политики кэширования, компонента 420 алгоритма замещения и средства 450 сохранения и для передачи этой информации к сети или к другим узлам. Средство 450 сохранения может содержать носитель данных (например, жесткий диск) и может быть сконфигурировано для сохранения или кэширования принятых объектов или частей и замещения указанных сохраненных объектов или частей. Средство 450 сохранения может быть пассивным компонентом, таким как кэш или запоминающее устройство. Альтернативно, средство 450 сохранения может быть активным компонентом, который осуществляет обработку или другую активную функцию.

В одном из вариантов осуществления множество узлов CONA может содержать множество средств кэширования, аналогичных средству 400 кэширования, и может коллективно решать подзадачу CC, например, распределенным способом. Узлы могут также поддерживать перемещение контента между собой для распределения контента или части объекта и обеспечения частичного кэширования. Перемещение контента можно обеспечивать, решая подзадачу CC, используя соответствующее средство 410 политики кэширования, извлекая части объекта, используя компоненты 430 передачи данных между кэшами, и замещая некоторые кэшируемые объекты или части, используя компоненты 420 алгоритма замещения. Перемещение контента между узлами может соответствовать требованиям кэширования контента, например, политикам кэширования, и эксплуатационным требованиям, например, требованиям или политикам TE.

Фиг. 5 показывает вариант осуществления способа 500 кэширования, который может воплощаться в узле CONA. Например, способ 500 кэширования можно воплощать с помощью средства 400 кэширования как часть распределенного алгоритма CC для решения подзадачи CC. Решение подзадачи CC может быть частью решения одной из описанных выше задач TECC, которое использует распределенный алгоритм. На этапе 510 могут принимать множество значений стоимости TE для множества линий связи. Например, компонент 412 политики сети может принимать стоимость TE линий связи, которые можно объединять для объединенных линий связи, или может вычислять объединенную стоимость линии связи в соответствии с отдельными принятыми значениями. Стоимость TE можно вычислять с помощью средства TE для распределенного способа с помощью множества узлов, соединенных с данными линиями связи, и затем направлять к узлу CONA, который содержит средство 400 кэширования или компонент 412 политики сети.

На этапе 520 могут принимать информацию о множестве частей объекта. Например, компонент 414 глобальной политики кэширования может принимать информацию ограничения об одной или большем количестве частей объекта (например, для различных объектов контента) для одного или большего количества узлов CONA. На этапе 530 политику кэширования для частей объекта можно вычислять в соответствии со стоимостью TE. Например, компонент 414 глобальной политики кэширования может осуществлять распределенный алгоритм (CC), используя стоимость TE линии связи, для вычисления подходящей стратегии размещения/распределения контента среди одного или большего количества узлов CONA. На этапе 540 одну или большее количество частей объекта можно извлекать для локального кэширования в соответствии с вычисленной политикой кэширования. Например, компонент 416 локальной политики кэширования может выбирать части объекта для кэширования в соответствии с глобальной политикой кэширования, вычисленной с помощью компонента 414 глобальной политики кэширования, и следовательно компонент 430 передачи данных между кэшами может извлекать выбранные части объекта из соответствующих им узлов.

На этапе 550 извлеченные части объекта можно локально кэшировать. Например, средство 450 сохранения может сохранять части объекта, принятые компонентом 430 передачи данных между кэшами. В некоторых вариантах осуществления способ 500 кэширования может также содержать этапы 560 и 570. На этапе 560 одна или большее количество кэшируемых частей объекта может быть назначена для замещения. Например, компонент 420 алгоритма замещения может выбирать, какая из частей объекта, хранящихся в носителе данных, может быть замещена в соответствии с принятыми обновлениями от других узлов, с пользовательским запросом и/или с другими изменениями условий в сети (например, с изменением пропускной способности или с перегрузкой трафика). На этапе 570 части объекта, назначенные для замещения, могут быть направлены к одному или большему количеству узлов. Например, средство 450 сохранения может посылать части объекта, указанные с помощью компонента 420 алгоритма замещения, к одному или большему количеству узлов CONA. Способ 500 кэширования может затем заканчиваться.

Решения задачи TECC могут быть смоделированы в соответствии с выбранной топологией сети, используя программное обеспечение или программу моделирования. Например, файл топологии сети может использоваться в качестве входной информации для моделирования. Топология сети может использоваться для определения кэширующих узлов. При моделировании множество узлов-источников для объектов контента может быть сгенерировано и соединено с множеством кэширующих узлов, например, узлов CONA, с помощью множества линий связи от источника. Информация об узлах-источниках, кэширующих узлах и линиях связи может прилагаться к файлу топологии сети. Следовательно, файл топологии может быть проанализирован и может использоваться для инициализации модели или структуры сети, в которой могут создаваться объекты из линий связи и узлов. Подпрограмма удаления элементов, которые дольше всего не использовались, (LRU) может использоваться для вычисления решения для схемы LRU. Решение может быть результатом моделирования. Подпрограмма обобщенного линейного программирования (GLP) может также использоваться для вычисления решения для схемы оптимизации с помощью линейного программирования (LP), которая может соответствовать некоторым из приведенных выше задач TECC. Полученное решение может быть добавлено к базе данных для входного отображения.

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

Для моделирования изменяющегося со временем поведения сети пользовательский запрос можно генерировать динамически, исходя из определенных представлений. Соответственно, пользователь может запрашивать один контент или объект в определенный момент времени, создавать множество сеансов, принимать контент от кэширующих узлов или узлов-источников и заканчивать сеансы после приема полной или завершенной копии запрашиваемого контента. Для достижения такого поведения сети дополнительные особенности могут быть добавлены к моделированию. Особенности могут содержать класс «сеанс», который может быть получен из класса «поток», который включает в себя моделирование, и может использоваться, чтобы различать между собой многочисленные магистрали. Особенности могут содержать класс «узел», который может включать в себя сеанс LinkedList, функцию addSession(), функцию removeSession() и функцию updateSession(), которые просматривают список связанных сеансов, уменьшают оставшееся время работы каждого сеанса согласно скорости передачи данных, и посылают событие, если сеанс закончен. Класс «узел» может также включать в себя функцию initSession(), которая случайным образом генерирует запрос контента, исходя из представления пользовательского запроса.

Особенности могут также содержать класс «сеть», который может включать в себя событие «очередь», функцию updateEvent(), функцию eventDispatcher() и функцию eventHandler(), которая может вызывать функцию eventDispatcher(). Класс «сеть» может содержать больше одного обработчика для различных целей. Класс «сеть» может также включать в себя модифицированную функцию calcLinkUtilization() для вычисления пропускной способности. Особенности могут также содержать класс «событие», который может включать в себя вещественную переменную двойной точности timeStamp и целочисленную переменную evenType.

Фиг. 6 показывает пример графика результатов 600 моделирования CC, которые получены с помощью решения задачи TECC и использования моделирования, как описано выше. Результаты 600 моделирования CC могут представлять производительность, воспринимаемую конечным пользователем в соответствии с двумя алгоритмами, алгоритмом CONA или TECC и алгоритмом сети доставки контента (CDN), который в настоящее время используется для некоторых сетей. Каждая точка на графике представляет результат, полученный из одной реализации или выполнения моделирования. Точки указывают задержку доступа в миллисекундах (мс) в зависимости от процента от максимального использования линии связи. В данных моделированиях рассматривали распределение относительно большого контента, например, чтобы ясно показать различие эффективности алгоритмов CONA и CDN. Используемый алгоритм CONA или TECC можно воплощать и для сетей на основе CONA, и также для сетей на основе IP, таких как Интернет. Как показано на Фиг. 6, задержка доступа для приема контента конечными пользователями, использующими алгоритм CONA, приблизительно на 30 процентов ниже задержки, полученной с помощью использования алгоритма CDN. Максимальное использование линии связи, обеспечиваемое с использованием алгоритма CONA, также по существу меньше максимального использования линии связи, обеспеченного с использованием алгоритма CDN для всех рассматриваемых точек.

Фиг. 7 показывает пример графика усредненных результатов 700 моделирования CC, которые соответствуют результатам 600 моделирования CC. Диаметр круга в верхнем правом углу представляет дисперсию задержек доступа, полученных с помощью алгоритма CDN. Этот намного меньший диаметр круга представляет полученную дисперсию задержки доступа с использованием алгоритма CONA, которая может быть по существу меньше, чем дисперсия задержки доступа алгоритма CDN. Дисперсия задержки доступа может указывать на стабильность эффективности соответствующего алгоритма, причем меньшая дисперсия указывает более стабильную производительность. Кривая на графике представляет область допустимых решений, например, допустимые решения, которые могут быть обеспечены.

Фиг. 8 показывает пример графика результатов 800 моделирования CC, которые соответствуют результатам 600 моделирования CC. Каждая точка на графике соответствует одной из точек в результатах 600 моделирования CC и представляет результат, полученный из одной реализации моделирования, как наблюдается с точки зрения провайдера сетевых услуг. Таким образом, результаты 800 моделирования CC могут представлять воспринимаемую конечным пользователем производительность. Точки указывают загрузку по трафику в источнике по отношению к значению в процентах от максимального использования линии связи, которая получена с использованием алгоритмов CONA и CDN. Загрузка по трафику в источнике, например, полученная в помещении поставщиков контента (например, в серверной ферме, в восходящей линии связи и т.д.), может быть решающим фактором производительности сети, поскольку трафик можно непосредственно передавать во множество серверов, которые могут поддерживаться с помощью поставщиков контента и сопоставленной стоимости (включающей в себя и стоимость сервера, и стоимость пропускной способности). Таким образом, чем ниже загрузка по трафику в источнике (например, в помещении поставщиков контента), тем лучшая производительность сети может быть обеспечена. Как показано на Фиг. 8, алгоритм CONA может уменьшать нагрузку в источнике примерно до 50 процентов по сравнению с алгоритмом CDN.

Фиг. 9 и 10 показывают сопоставление результатов 900 моделирования использования сети в соответствии с алгоритмом CONA и результатов 1000 моделирования использования сети в соответствии с алгоритмом CDN, соответственно. Результаты 900 моделирования использования сети и результаты 1000 моделирования использования сети получены, используя моделирования на обычной топологии провайдера сетевых услуг (например, сети Абилин). В обоих случаях одинаковые наборы контента распределяют по сети с данной топологией одинаковому набору пользователей. Сравнивая два результата моделирования, становится ясно, что распределение нагрузки из-за контента намного лучше сбалансировано по набору пользователей в случае алгоритма CONA. Фиг. 9 показывает, что от приблизительно одного до приблизительно 10 процентов нагрузки может распределяться, используя алгоритм CONA (или TECC), по каждой линии связи между узлами или пользователями по сети. Напротив, Фиг. 10 показывает, что по существу другие значения загрузки по трафику или значений в процентах могут распределяться, используя алгоритм CDN, по каждой линии связи между узлами по сети, причем данное распределение значительно изменяется, в пределах от 0% до 102%.

Фиг. 11 показывает вариант осуществления блока 1100 передачи/приема, который может быть любым устройством, которое перемещает пакеты через сеть. Например, блок 1100 передачи/приема может быть расположен в любом из узлов в сетевой архитектуре 100 или 300, например, в любом из узлов CONA, и может содержать средство 400 кэширования. Блок 1100 передачи/приема может содержать один или большее количество входных портов или блоков 1110 для приема пакетов, объектов или элементов «длина-тип-значение» (TLV) от других сетевых компонентов, логическую схему 1120 для определения, в какие сетевые компоненты следует посылать пакеты, и один или большее количество выходных портов или блоков 1130 для передачи кадров к другим сетевым компонентам. Логическая схема 1120 может содержать компоненты средства 400 кэширования, и блок 1100 передачи/приема может воплощать способ 500 кэширования.

Описанные выше компоненты сети могут воплощаться на любом универсальном сетевом компоненте, таком как компьютер или сетевой компонент с мощностью обработки, ресурсами запоминающего устройства и сетевой пропускной способностью, достаточной для обработки необходимой рабочей нагрузки, размещенной в нем. Фиг. 12 показывает типичный универсальный компонент 1200 сети, подходящий для воплощения одного или большего количества раскрытых вариантов осуществления компонентов. Компонент 1200 сети включает в себя процессор 1202 (который может упоминаться как центральный процессор или ЦП), который обменивается данными с запоминающими устройствами, которые включают в себя внешнее запоминающее устройство 1204, постоянное запоминающее устройство (ПЗУ) 1206, оперативную память (ОП) 1208, устройства 1210 ввода-вывода (В/В) и устройства 1212 обеспечения связи с сетью. Процессор 1202 можно воплощать как одну или большее количество микросхем ЦП, или он может быть частью одной или большего количества специализированных интегральных схем (ASIC) и/или процессоров цифровой обработки сигналов (DSP).

Внешнее запоминающее устройство 1204 обычно состоит из одного или большего количества дисководов или лентопротяжных устройств и используется для энергонезависимого хранения данных и в качестве устройства хранения избыточных данных, если ОП 1208 недостаточно большая для хранения всех рабочих данных. Внешнее запоминающее устройство 1204 может использоваться для хранения программ, которые загружены в ОП 1208, когда такие программы выбраны для выполнения. ПЗУ 1206 используется для хранения команд и, возможно, данных, которые считывают во время выполнения программы. ПЗУ 1206 является энергонезависимым запоминающим устройством, которое обычно имеет небольшой объем запоминающего устройства относительно большего объема запоминающего устройства внешнего запоминающего устройства 1204. ОП 1208 используется для хранения энергозависимых данных и, возможно, для хранения команд. Доступ и к ПЗУ 1206, и к ОП 1208 обычно быстрее, чем к внешнему запоминающему устройству 1204, поскольку они используют различные технологии, но это не является обязательным.

Раскрыт по меньшей мере один из вариантов осуществления, и разновидности, комбинации и/или модификации варианта(ов) осуществления и/или особенности варианта(ов) осуществления, выполненные специалистом, находятся в пределах объема раскрытия. Альтернативные варианты осуществления, которые являются результатом объединения, дополнения и/или исключения особенностей варианта(ов) осуществления, также находятся в пределах объема раскрытия. Когда числовые диапазоны или ограничения явно заявлены, следует понимать, что такие явные диапазоны или ограничения включают в себя итерационные диапазоны или ограничения аналогичной величины, находящиеся в пределах явно заявленных диапазонов или ограничений (например, от приблизительно 1 до приблизительно 10 включает в себя, 2, 3, 4 и т.д.; больше 0,10 включает в себя 0,11, 0,12, 0,13 и т.д.). Например, когда указан числовой диапазон с нижним пределом R₁ и верхним пределом R_u, любое число, находящееся в пределах этого диапазона, конкретно указано. В частности следующие числа в пределах данного диапазона конкретно указаны: R=R₁+k*(R_u-R₁), причем k является переменной в пределах от 1 процента до 100 процентов с 1-процентным приращением, то есть k составляет 1 процент, 2 процента, 3 процента, 4 процента, 7 процентов, …, 70 процентов, 71 процент, 72 процента, …, 97 процентов, 96 процентов, 97 процентов, 98 процентов, 99 процентов или 100 процентов. Кроме того, также конкретно указан любой числовой диапазон, определенный двумя числами R, как определено выше. Следует понимать, что использование более широких терминов, таких как «содержит», «включает в себя» и «имеющий», оказывает поддержку для более узких терминов, такой как «состоящий из», «состоящий по существу из» и «содержащий в основном». Соответственно, объем правовой охраны не ограничен изложенным выше описанием, но определяется последующей формулой изобретения, этот объем включает в себя все эквиваленты предмета формулы изобретения. Каждый и все пункты формулы изобретения внедрены в качестве дополнительного раскрытия в описание, и формула изобретения является вариантом(ами) осуществления настоящего раскрытия. Обсуждение ссылок в данном раскрытии не является подтверждением, что они являются предшествующим уровнем техники, в частности, любой ссылки, которая имеет год издания после даты приоритета данной заявки. Раскрытие всех патентов, патентных заявок и публикаций, указанных в данном раскрытии, тем самым представлено в качестве ссылки, до той степени, пока они обеспечивают примерные, процедурные или другие подробности, дополнительные к данному раскрытию.

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

Кроме того, методики, системы, подсистемы и способы, описанные и показанные в различных вариантах осуществления, как обособленные или отдельные, могут быть объединены или совмещены с другими системами, модулями, методиками или способами, не отступая от объема настоящего раскрытия. Другие элементы, показанные или обсуждаемые, как соединенные или непосредственно соединенные или осуществляющие связь друг с другом, могут быть опосредованно соединены или осуществлять связь через некоторый интерфейс, устройство или промежуточный компонент или электрически, или механически, или иным образом. Другие примеры изменений, замен и модификаций могут определяться специалистами и могут выполняться, не отступая от раскрытых объема и формы изобретения.