Архитектура плоскости переадресации маршрутизатора контента

Архитектура плоскости переадресации маршрутизатора контента

Иллюстрации

Показать все

Реферат

ПЕРЕКРЕСТНАЯ ССЫЛКА НА РОДСТВЕННЫЕ ЗАЯВКИ

[0001] По настоящей заявке испрашивается приоритет патентной заявки США № 13/022412, поданной 7 февраля 2011 года и озаглавленной «Content Router Forwarding Plane Architecture», по которой испрашивается приоритет предварительной патентной заявки США № 61/389548, поданной 4 октября 2010 года заявителями Jianming Wu и др. и озаглавленной «High Capacity and Performance Software Content Router Storage Architecture for Commodity Servers», и предварительной патентной заявки США № 61/394211, поданной 18 октября 2010 года заявителями Jianming Wu и др. и озаглавленной «High Capacity and Performance Software Content Router Storage Architecture for Commodity Servers», которые включены в настоящий документ посредством ссылки, как если бы они были воспроизведены в полном объеме.

ОТЧЕТ О ФИНАНСИРУЕМОМ ИЗ ФЕДЕРАЛЬНОГО БЮДЖЕТА ИССЛЕДОВАНИИ ИЛИ РАЗРАБОТКЕ

[0002] Не применимо.

ССЫЛКА НА ПРИЛОЖЕННЫЙ МИКРОФИЛЬМ

[0003] Не применимо.

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

[0004] Настоящее изобретение относится к технологиям связи и, в частности, к архитектуре плоскости переадресации маршрутизатора контента.

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

[0005] Существующие сети, работающие по протоколу интернета (IP), содержат множество узлов, включая множество маршрутизаторов в ядре сети и множество хостов на краю сети. Маршрутизаторы коллективно соединяют каналы связи между хостами. Узлам присвоены общесетевые уникальные IP-адреса, чтобы сделать возможной правильную и эффективную переадресацию трафика к узлам назначения. Маршрутизаторы маршрутизируют пакеты в IP сетях, основываясь на IP-адресах, которые несут пакеты. Пакеты переадресовывают посредством маршрутизаторов в правильные пункты назначения, основываясь на паре <адрес источника, адрес пункта назначения>, которая может быть указана в каждом пакете. IP версии 4 (IPv4) представляет собой обычно используемый протокол IP во многих сетях, таких как локальные сети (LAN) и интернет. Адрес IPv4 содержит приблизительно 32 бита, включая префикс IP-адреса, который содержит приблизительно вплоть до 24 битов. Соответственно, маршрутизатор может оперировать приблизительно вплоть до 16 миллионами (или 2²⁴) адресами пунктов назначения. IP-адреса также могут быть локализованы в блоках на основе различных географических областей, что делает возможным агрегирование IP-адресов, основываясь на географической области, и, таким образом, уменьшает пространство поиска для пунктов назначения в маршрутизаторе.

[0006] Некоторые существующие сети включают сети контента, которые предоставляют контент или услуги потребителям, такой как контент по запросу. В сети контента маршрутизатор контента отвечает за маршрутизацию запросов пользователей и контента правильным получателям. В сети контента общедоменное уникальное имя присваивают каждому объекту, который представляет часть инфраструктуры доставки контента. Объекты могут содержать контент данных, такой как видеоролики или веб-страницы, и/или инфраструктурные элементы, такие как маршрутизаторы, коммутаторы или серверы. Маршрутизатор контента использует общие префиксы имен (которые могут представлять полные имена контента или правильные префиксы имен контента), чтобы маршрутизировать пакеты контента внутри сети контента. По существу, пространство решений о маршрутизации расширено значительно больше пространства имен в сравнении с ограниченным пространством префиксов IP, что представляет некоторые проблемы для современных архитектур или схем маршрутизаторов, например, которые основаны на переадресации по IP-адресам.

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

[0007] В одном из вариантов осуществления раскрытие содержит плоскость переадресации маршрутизатора, которая содержит фильтр Блума, который хранят в запоминающей среде первого уровня, и журнал переадресации информации, который связан с фильтром Блума и хранится в запоминающей среде второго уровня.

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

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

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

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

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

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

[0013] На фиг.1 представлено схематическое изображение варианта осуществления архитектуры плоскости переадресации маршрутизатора.

[0014] На фиг.2 представлено схематическое изображение варианта осуществления фильтра Блума.

[0015] На фиг.3 представлено схематическое изображение варианта осуществления комбинации фильтра Блума и счетного фильтра Блума.

[0016] На фиг.4 представлено схематическое изображение другого варианта осуществления масштабированного фильтра Блума.

[0017] На фиг.5 представлена блок-схема варианта осуществления способа переадресации для маршрутизатора.

[0018] На фиг.6 представлено схематическое изображение варианта осуществления блока передатчика/приемника.

[0019] На фиг.7 представлено схематическое изображение варианта осуществления компьютерной системы общего назначения.

ПОДРОБНОЕ ОПИСАНИЕ

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

[0021] По мере развития интернета сети контента становятся более популярными, например, в связи с растущими запросами на видеоконтент, мобильными хостами и безопасностью контента. В сети контента данные или сетевой объект могут быть ассоциированы с общесетевым уникальным именем, которое указывает на объект и делает его доступным для пользователей сети. Сетевой объект может предоставлять один и тот же контент с множества распределенных серверов. Сеть контента работает на уровне контента, где общие префиксы имен контента используют для того, чтобы маршрутизировать информацию, например, вместо IP-адресов в пакетах. Таким образом, пользователи контента могут запрашивать контент по одному и тому же имени, но сеть может маршрутизировать их запросы на различные серверы, которые предоставляют запрашиваемый контент, например, основываясь на местоположениях пользователей.

[0022] Однако, вследствие по существу больших требований к пространству имен контента в сетях контента, установление плоскости переадресации маршрутизатора контента для обращения с по существу большим количеством префиксов имен с приемлемой эффективностью может быть затруднительным. Поскольку число объектов контента может быть существенно больше, чем число узлов IP-сети, пространство поиска для имен контента может быть существенно больше, чем пространство поиска для IP-адресов. Дополнительно, пространство имен контента может быть разреженным в силу требований к присвоению имен контента. Например, в сети контента, который имеет длину имени приблизительно вплоть до 64 байтов, общее число возможных имен может быть меньше чем или равным приблизительно 2⁵¹². Если разрешены только читаемые человеком символы, такие как в существующем формате унифицированных указателей ресурсов (URL), то число имен может быть равным приблизительно 2³⁶⁰, что больше, чем гугол. Кроме того, в настоящее время нет доступного эффективного способа агрегирования имен. В отличие от IP-адресов имена контента или префиксы имен не могут быть сгруппированы по географическим областям и, таким образом, не могут быть агрегированы, основываясь на географической области, для того, чтобы уменьшать пространство имен на маршрутизаторе.

[0023] В настоящем документе описаны система и способ для архитектуры плоскости переадресации маршрутизатора, которые можно использовать для маршрутизации контента. Архитектура плоскости переадресации маршрутизатора может позволить переадресацию имени контента в сетях контента с улучшенной масштабируемостью и производительностью, например, в сравнении со схемами переадресации по IP-адресам. Архитектура плоскости переадресации маршрутизатора может содержать систему трехуровневой памяти и/или накопителя, которую можно организовать с использованием доступных коммерческих или потребительских серверов и программного обеспечения, что может снижать стоимость. Система трехуровневой памяти/накопителя может содержать фильтр Блума, счетный фильтр Блума и журнал переадресации информации, которые могут представлять собой компоненты, включающие программное обеспечение, аппаратное обеспечение, программно-аппаратное обеспечение или их сочетания, которые поддерживаются тремя соответствующими уровнями аппаратных компонентов памяти/накопителя. Архитектура плоскости переадресации маршрутизатора может обеспечивать относительно быструю переадресацию контента и большой накопитель, который может поддерживать по существу большие требования к пространству имен контента. Дополнительно, архитектура плоскости переадресации маршрутизатора может обеспечивать относительно быстрое устранение ошибок, например, в случае сбоев аппаратного обеспечения.

[0024] На фиг.1 проиллюстрирован вариант осуществления архитектуры плоскости переадресации маршрутизатора 100, который можно использовать для маршрутизации контента в сети. Например, сеть может представлять собой какую-либо сеть связи, которая предоставляет услуги для конечных пользователей, включая сети на основе Ethernet, сети, работающие по протоколу интернета (IP), пассивные оптические сети (PON), сети подписчиков цифровых абонентский линий (DSL), беспроводные сети, другие сети связи или их сочетания. В качестве альтернативы сеть может представлять собой опорную сеть, в которой реализован протокол опорной сети, такой как Ethernet, IP или протокол управления передачей (TCP). Контент может содержать данные, голос, видео, телевидение (TV), интернет и/или какой-либо специфичный контент приложения, такой как игровой контент. Конечный пользователь может представлять собой какого-либо провайдера/потребителя контента сети и/или какое-либо пользовательское оборудование, соединенное с сетью. Например, конечный пользователь может быть связан с пользовательским оборудованием на потребительском оборудовании, таком как терминал оптической сети (ONU) или блок приемопередатчика высокоскоростной DSL (VDSL) в месте жительства абонента (VTU-R). В качестве альтернативы конечный пользователь может соответствовать домашнему оборудованию связи, такому как телевизионная приставка, стационарное персональное устройство, такое как настольный компьютер, или мобильное персональное устройство, такое как сотовый телефон, портативный компьютер или портативный планшет.

[0025] Архитектура плоскости переадресации маршрутизатора 100 может содержать систему трехуровневой памяти/накопителя, которая может быть установлена в узле или маршрутизаторе с использованием доступного аппаратного обеспечения, такого как потребительские серверы, и установленного программного обеспечения. В частности, система трехуровневой памяти/накопителя может содержать фильтр Блума 110, счетный фильтр Блума 120 и журнал 130 переадресации информации, которые могут представлять собой компоненты программного обеспечения или структуры данных, установленных и поддерживаемых тремя соответствующими уровнями аппаратных компонентов памяти/накопителя. Архитектура плоскости переадресации маршрутизатора 100 также может содержать дополнительные компоненты программного обеспечения, такие как таблица предпочтения портов (не показано), которые могут быть расположены на первом уровне памяти/накопителя.

[0026] Фильтр Блума 110 может представлять собой компонент программного обеспечения или структуру данных, сконфигурированных для запроса элементов, например, входящих общих префиксов имен, для каждого порта маршрутизатора. Фильтр Блума 110 может содержать массив бинарных битов, который можно использовать для хранения или регистрации совокупности сигнатур для множества элементов, связанных с фильтром Блума 110, и связанного порта. Для каждого элемента одну или несколько сигнатур можно генерировать с использованием одной или нескольких соответствующих хэш-функций, где одни и те же хэш-функции можно использовать для того, чтобы генерировать сигнатуры для множества элементов. Например, набор хэш-функций можно применять к множеству общих префиксов имен, которые могут представлять собой элементы фильтра Блума 110, чтобы генерировать набор сигнатур для каждого префикса имени. Каждая сигнатура в наборе сигнатур может соответствовать одной хэш-функции в наборе хэш-функций. Каждую сигнатуру элемента в наборе сигнатур можно показать или представить, задав один бит в фильтре Блума 110.

[0027] Для каждого порта в узле новый элемент можно добавлять к связанному фильтру Блума, задавая биты в фильтре Блума 110, чтобы показывать сигнатуры, полученные с использованием хэш-функций. Для маршрутизации контента сигнатуры выходящего префикса имени можно вычислять с использованием хэш-функций, и получаемые значения битов можно сравнивать с битами фильтра Блума 110 для каждого порта. Затем контент можно переадресовать через один из портов, если префикс имени представляет собой элемент фильтра Блума 110 этого порта, например, если сигнатуры префикса имени совпадают с соответствующими значениями битов в фильтре Блума 110.

[0028] Счетный фильтр Блума 120 может представлять собой компонент программного обеспечения или структуру данных, сконфигурированные для поддержки удаления элементов фильтра Блума 110. Счетный фильтр Блума 120 может содержать набор бинарных битов для каждого бита в фильтре Блума 110, который соответствует одной сигнатуре. Набор битов для каждой сигнатуры может указывать текущее или последнее обновленное количество элементов, которые совместно используют одну и ту же сигнатуру в фильтре Блума 110. Количество битов в наборе битов для каждой сигнатуры может определять максимальное число элементов, которые могут совместно использовать одну и ту же сигнатуру в фильтре Блума 110. Когда элемент удаляют или исключают из набора элементов порта, связанного с фильтром Блума 110, количество элементов, указанных в соответствующем наборе битов в счетном фильтре Блума 120, может быть уменьшено на один. В качестве альтернативы количество элементов, указанных в наборе битов в счетном фильтре Блума 120, можно увеличивать на один, когда новый элемент, который имеет сигнатуру, соответствующую набору битов, добавляют в набор элементов порта. Когда последний оставшийся элемент, который имеет сигнатуру, соответствующую набору битов в счетном фильтре Блума 120, удаляют из набора элементов порта, количество элементов, указываемых посредством набора битов, можно уменьшать приблизительно до нуля, и соответствующий бит в фильтре Блума 110 можно сбрасывать, например, приблизительно до нуля.

[0029] Журнал 130 переадресации информации может представлять собой компонент программного обеспечения или структуру данных, которая содержит данные, которые можно использовать для правильной маршрутизации контента в сети, такие как префиксы имен, время прибытия различного контента и какая-либо другая информация, связанная с маршрутизацией. Информацию о маршрутизации можно добавлять в журнал 130 переадресации информации, когда информация прибывает на маршрутизатор. Таким образом, журнал 130 переадресации информации может сохранять текущую или последнюю обновленную информацию о маршрутизации для маршрутизатора. Информацию в журнале 130 переадресации информации можно не использовать непосредственно для того, чтобы маршрутизировать контент и/или обрабатывать префиксы имен, например, в реальном времени, а можно использовать для того, чтобы реконструировать фильтр Блума 110 и/или счетный фильтр Блума 120 в случае потери информации в фильтре Блума 110 и/или счетном фильтре Блума 120, например, в связи со сбоем запоминающей среды, сбоем аппаратного обеспечения или сбоем программного обеспечения. Например, журнал 130 переадресации информации можно использовать для того, чтобы реконструировать по меньшей мере часть счетного фильтра Блума 120, который можно использовать для того, чтобы реконструировать по меньшей мере часть фильтра Блума 110. Журнал 130 переадресации информации в одном или нескольких первых маршрутизаторах также можно использовать для восстановления схожей информации о маршрутизации в одном или нескольких вторых маршрутизаторах, если вторые маршрутизаторы отказали.

[0030] Современная архитектура маршрутизаторов, например, которая основана на схемах IP маршрутизации и отправки, может не позволять маршрутизаторам обрабатывать по существу большое количество общих префиксов имен контента с приемлемой скоростью сети, например, не превышая приемлемую стоимость сети. Например, современные IP маршрутизаторы можно выполнять с возможностью обработки, самое большее, приблизительно 16 миллионов префиксов IP адресов, например, согласно описанию IPv4. Такие маршрутизаторы могут требовать большего пространства памяти, кластерных технологий и/или специального аппаратного обеспечения для расширения пространства поиска имен и, таким образом, обработки маршрутизации контента, что может увеличивать стоимость системы. В качестве альтернативы маршрутизаторы могут использовать усовершенствованные или сложные алгоритмы поиска или низкопроизводительные накопительные устройства большой емкости, которые могут снижать производительность системы.

[0031] Система трехуровневой памяти/накопителя архитектуры плоскости переадресации маршрутизатора 100 может компенсировать недостатки современной архитектуры плоскости переадресации маршрутизатора. В системе трехуровневой памяти/накопителя можно более часто осуществлять доступ к фильтру Блума 110 и требовать более быстрого времени ответа и, таким образом, более быстрой запоминающей среды, чем другие два компонента. Фильтр Блума 110 также может содержать меньше данных и, таким образом, требовать меньшего пространства памяти, чем другие два компонента. Аналогичным образом, можно более часто осуществлять доступ к счетному фильтру Блума 120 и требовать более быстрого времени ответа и, таким образом, более быстрой запоминающей среды, чем журнал 130 переадресации информации. Счетный фильтр Блума 120 также может содержать меньше данных и требовать меньше пространства памяти, чем журнал 130 переадресации информации.

[0032] Поскольку три компонента архитектуры плоскости переадресации маршрутизатора 100 могут иметь различающиеся требования к пространству памяти, скорости доступа к памяти и задержке, три компонента можно помещать на различных запоминающих средах с различным размером накопителя и скоростью доступа к памяти, при необходимости, для того, чтобы снижать стоимость системы по существу без снижения эффективности. По существу, первая память/запоминающая среда для первого уровня памяти/накопителя (например, для фильтра Блума 110) может иметь более высокую эффективность, например, в отношении скорости доступа к памяти или задержки, чем другие два уровня. Первая память/запоминающая среда также может иметь более высокую единичную стоимость в сравнении с остальными уровнями в связи с отличием в виде более высокой эффективности. Однако, поскольку фильтр Блума 110 может иметь меньшие требования к пространству памяти, чем другие два компонента, стоимость первой памяти/запоминающей среды можно ограничить посредством ограничения емкости накопителя первой памяти/запоминающей среды при необходимости поддержать фильтр Блума 110.

[0033] Аналогичным образом, вторая память/запоминающая среда для второго уровня памяти/накопителя (например, счетного фильтра Блума 120) может иметь более высокую скорость доступа к памяти (и/или более низкую задержку доступа к памяти) и более высокую единичную стоимость в сравнении с третьим уровнем. Стоимость второй памяти/запоминающей среды также можно ограничить посредством ограничения емкости накопителя второй памяти/запоминающей среды как необходимо, чтобы поддерживать счетный фильтр Блума 120. Третья память/запоминающая среда для второго уровня памяти/накопителя (например, журнала 130 переадресации информации) может иметь меньшую скорость доступа к памяти, меньшую единичную стоимость и большую емкость в сравнении с каждым из первого уровня и второго уровня.

[0034] В одном из примеров фильтр Блума 110 может располагаться в динамическом оперативном запоминающем устройстве (DRAM), счетный фильтр Блума 120 может располагаться в твердотельном накопителе (SSD), а журнал 130 переадресации информации может находиться в накопителе на жестком диске (HDD). В других примерах другую память/запоминающие среды можно использовать для размещения этих трех компонентов. Например, фильтр Блума 110, счетный фильтр Блума 120 и журнал 130 переадресации информации могут располагаться в DRAM, памяти с изменением фазового состояния (PCM) и SSD, соответственно.

[0035] На фиг.2 проиллюстрирован вариант осуществления фильтра Блума 200, который может соответствовать фильтру Блума 110 в архитектуре плоскости переадресации маршрутизатора 100. Фильтр Блума 200 может быть связан с портом в узле сети (например, маршрутизатор контента) и может содержать битовый массив 210. Битовый массив 210 можно хранить в первом уровне памяти/накопителя (например DRAM), и он может содержать множество битов, например, приблизительно восемь битов, как показано на фиг.2. В других вариантах осуществления битовый массив 210 может содержать любое количество битов, например, больше чем приблизительно один. Битовый массив 210 можно выполнять с возможностью указывать одну или несколько сигнатур для одного или нескольких элементов (например, общие префиксы имен), которые связаны с портом. Каждый элемент может иметь уникальный набор сигнатур, который представлен посредством отличающегося набора битов в битовом массиве 210.

[0036] Например, каждый бит, который соответствует сигнатуре для элемента порта, можно задавать равным приблизительно единице. Остальные биты, которые могут не соответствовать сигнатуре элемента, можно задавать равными приблизительно нулю. Набор сигнатур для всех элементов порта может содержать приблизительно такое же количество сигнатур или битов. Изначально, все биты можно задавать равными приблизительно нулю, например, до присвоения какого-либо элемента порту. Когда элемент (например, общий префикс контента имени) добавляют к порту, сигнатуры элементов можно вычислять и соответствующие биты можно задавать в битовом массиве 210. По существу, биты битового массива 210 можно обновлять каждых раз, когда добавляют элемент.

[0037] Чтобы решить, являются ли префиксы имен элементами и соответственно переадресовать соответствующий входящий контент на порт, сигнатуры входящих имен или префиксов можно вычислять и сопоставлять с битами в битовом массиве 210. Например, маршрутизатор может принимать первый контент, связанный с первым префиксом (K1) 220, и второй контент, связанный со вторым префиксом (K2) 230. Таким образом, первый набор сигнатур можно получить для K1 и второй набор сигнатур можно получить для K2 с использованием одного и того же набора хэш-функций. Например, приблизительно три первые сигнатуры для K1 и приблизительно три вторые сигнатуры для K2 можно получить с использованием приблизительно трех одинаковых хэш-функций, которые могут отображать K1 и K2 в два различных набора значений.

[0038] Например, три сигнатуры первого префикса (K1) 220 могут быть равны приблизительно нулю, двум и четырем и соответствовать первому, третьему и пятому битам в битовом массиве 210, соответственно. Три сигнатуры второго префикса (K2) 230 могут быть равны приблизительно двум, четырем и семи, что может соответствовать третьему, пятому и восьмому битам в битовом массиве 210, соответственно. Поскольку одна из первых сигнатур, например, та, которая соответствует первому биту (слева), не задана в битовом массиве 210 (например, имеет соответствующий нулевой бит), K1 может не являться элементом фильтра Блума 200, и, таким образом, соответствующий контент не может быть переадресован на порт, связанный с фильтром Блума 200. Поскольку все вторые сигнатуры заданы в битовом массиве 210 (например, имеют соответствующие единичные биты), K2 может представлять собой элемент фильтра Блума 200, и, таким образом, соответствующий контент может быть переадресован на порт, связанный с фильтром Блума 200.

[0039] Фильтр Блума, схожий с фильтром Блума 200, можно использовать для каждого порта в узле или маршрутизаторе. Используя фильтры Блума для того, чтобы переадресовывать контент на порты маршрутизатора, можно заменить функцию таблицы переадресации для портов, такую как используют в типичных схемах переадресации по IP-адресам. Когда пакет получают в маршрутизаторе контента, сигнатуры можно вычислять с использованием имени цели в пакете и затем использовать для того, чтобы опрашивать множество фильтров Блума для множества портов. Если совпадение находят в одном или нескольких фильтрах Блума, то пакет можно переадресовывать на один или несколько портов, связанных с фильтрами Блума. Если ни один из фильтров Блума не совпадает с сигнатурами имени или префикса в пакете, тогда можно осуществлять лавинную маршрутизацию пакета (например, переадресовать через все порты) или можно его отбросить.

[0040] Фильтры Блума для портов можно опрашивать параллельно, например, приблизительно в один и тот же момент времени, на скорости доступа к памяти, если среда хоста представляет собой память. Фильтры Блума можно опрашивать параллельно, используя механизм кэширования доступа к памяти центрального процессора (CPU), где фильтры Блума можно выравнивать в строку кэша памяти CPU. Например, размер строки кэша в современных CPU INTEL равен приблизительно 64 байтам. По существу, приблизительно вплоть до 512 фильтров Блума можно опрашивать приблизительно в один и тот же момент времени, если фильтры Блума выровнены должным образом в памяти. Дополнительно, сигнатуры для одного и того же имени или префикса можно проверять или сопоставлять с фильтрами Блума приблизительно в один и тот же момент времени. Поскольку хэш-функции, используемые для того, чтобы вычислять сигнатуры (для каждого имени или префикса), не зависят друг от друга, каждое ядро CPU может реализовывать одну из хэш-функций для одного префикса имени, и все ядра CPU могут работать параллельно для того, чтобы вычислять все сигнатуры. В существующем аппаратном обеспечении сервер может содержать приблизительно больше, чем восемь ядер CPU, которые могут позволять маршрутизатору контента опрашивать приблизительно 512 фильтров Блума для всех сигнатур (например, приблизительно по восемь сигнатур на префикс) за одно обращение к памяти.

[0041] Фильтр Блума можно хранить в памяти/запоминающей среде первого уровня, которая имеет наименьшую задержку доступа в системе трехуровневой памяти/накопителя. Существующие DRAM, такие как синхронные DRAM с двойной скоростью три (DDR3) (DDR3 SDRAM), могут иметь низкую задержку доступа приблизительно в 10 нс, которая может быть подходящей для работы фильтров Блума. Однако емкость DRAM может быть относительно низкой, и единичная стоимость может быть относительно высокой в сравнении с другими накопительными устройствами. Максимальная емкость DDR3 SDRAM на одной машине или сервере может быть равна приблизительно до 96 гигабайт (ГБ), и единичная стоимость может быть равна приблизительно 30 долларам США за ГБ. Таким образом, DRAM можно использовать на первом уровне памяти/накопителя для того, чтобы размещать фильтр Блума.

[0042] Опрос фильтра Блума может зависеть от количества используемых хэш-функций, но допускает эффективное масштабирование до значительно большого пространства имен контента, например, без значительного ухудшения эффективности. Например, битовый массив приблизительно в 20 битов на элемент можно использовать для того, чтобы организовать фильтр Блума, который имеет уровень ложноположительных срабатываний (FPR) приблизительно 0,01 процента. Маршрутизатор контента, который содержит память приблизительно 50 ГБ может обрабатывать приблизительно 20 миллиардов общих префиксов имен, например, приблизительно в одно и то же время. Такая относительно высокая скорость опроса может обеспечивать высокую пропускную способность для маршрутизатора контента. Например, односерверная система обработки и хранения может обрабатывать поток со скоростью приблизительно 3,2 терабита в секунду (Tbps) для относительно маленьких пакетов контента размером приблизительно четыре килобайта (КБ), таких как веб-страницы, и поток со скоростью приблизительно восемь петабитов в секунду (Pbps) для относительно большого контента приблизительно по 10 мегабайтов (МБ), такого как видеоролики.

[0043] FPR относится к вероятности получить значение «истина» (или положительный результат) для запроса префикса имени в фильтре Блума, который может не являться элементом фильтра Блума, например, вследствие сжатого представления с потерями информации о принадлежности элементов. Схему архитектуры плоскости переадресации маршрутизатора можно корректировать как необходимо, чтобы поддерживать приемлемый уровень FPR фильтра Блума. FPR можно управлять посредством корректировки количества используемых хэш-функций и количества битов на элемент в фильтре Блума. Например, чтобы добиться FPR приблизительно в один процент, размер фильтра Блума в битах можно задать приблизительно в 10 раз больше, и ожидаемое число элементов и количество хэш-функций для генерации сигнатур может быть равно приблизительно семи. Кроме того, FPR может по существу не влиять или не снижать доступность или успешную доставку контента в сети, но может добавлять некоторое количество дополнительного трафика. Типично в сетях контента, контент можно переадресовывать с использованием многотрактовой маршрутизации, например, вместо сквозных моделей, и промежуточные узлы могут иметь возможность накопления и/или кэширования. По существу, маршрутизаторы в сети могут устанавливать множество путей для повышения или оптимизации условий трафика в сети и обеспечения доставки контента, что может представлять собой одну из задач разработки сетей контента.

[0044] Одна из сложностей в использовании фильтра Блума состоит в отсутствии операции удаления, например, для того, чтобы удалить сигнатуры для удаленного элемента. Например, когда элемент удаляют из порта, соответствующие биты в фильтре Блума не могут быть сброшены приблизительно до нуля, поскольку некоторые биты могут совместно использоваться другими элементами, например, могут соответствовать сигнатурам других элементов. Сброс таких совместно используемых битов может вносить уровень ложноотрицательных результатов в фильтр Блума, например, можно возвращать значение «ложь» для запросов истинных элементов в фильтре Блума. Эта ситуация может усложнять работу фильтра Блума и снижать эффективность маршрутизатора контента. Вместо этого счетный фильтр Блума может быть связан с фильтром Блума и использоваться для того, чтобы предоставлять эффективную операцию удаления для фильтра Блума.

[0045] На фиг.3 проиллюстрирован вариант осуществления комбинации 300 фильтра Блума и счетного фильтра Блума, которая может содержать фильтр Блума 310 и счетный фильтр Блума 320. Например, фильтр Блума 310 и счетный фильтр Блума 320 могут соответствовать фильтру Блума 110 и счетному фильтру Блума 120. Фильтр Блума 310 может быть связан с портом в маршрутизаторе контента, содержать битовый массив приблизительно из четырех битов и храниться в первом уровне памяти/накопителя (например, DRAM). Фильтр Блума 310 может работать по существу аналогично фильтру Блума 200.

[0046] Счетный фильтр Блума 320 может быть связан с фильтром Блума 310 и портом и может содержать множество поднаборов или подмассивов из приблизительно равного количества битов, каждый из которых соответствует одному из битов фильтра Блума 310. Например, счетный фильтр Блума 320 может содержать всего приблизительно 16 битов, где каждый поднабор приблизительно из четырех битов может быть связан с соответствующим битом в фильтре Блума 310. Количество битов в каждом поднаборе в счетном фильтре Блума 320 можно определять на основе приближения Пуассона, которое предполагает, что приблизительно четыре бита на один бит или сигнатуру в фильтре Блума 310 могут быть достаточными для того, чтобы покрыть максимальное ожидаемое количество элементов на сигнатуру. Однако, в других вариантах осуществления любое количество битов можно использовать в поднаборах счетного фильтра Блума 320, например, больше, чем один бит на сигнатуру. Счетный фильтр Блума 320 можно хранить во втором уровне памяти/накопителя (например, SSD).

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

[0048] Счетный фильтр Блума 320 можно хр