АРХИТЕКТУРА ПЛОСКОСТИ ПЕРЕАДРЕСАЦИИ МАРШРУТИЗАТОРА КОНТЕНТА Российский патент 2015 года по МПК H04L12/00 

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

[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 можно хранить в памяти/запоминающей среде второго уровня, которая может иметь баланс между эффективностью и стоимостью, более низкой задержкой доступа, чем третий слой, и более низкой единичной стоимостью, чем первый уровень системы памяти/накопителя. Например, существующие SSD могут быть подходящими для хранения счетного фильтра Блума 320 на втором уровне системы памяти/накопителя. В SSD можно использовать флэш-память в качестве запоминающей среды, которая представляет собой один тип энергонезависимой среды. Средняя задержка доступа SSD может быть равна приблизительно 100 мкс, и единичная стоимость может быть равна приблизительно 3 долларам США за ГБ.

[0049] Счетный фильтр Блума на втором уровне памяти/накопителя также может позволять масштабировать фильтр Блума на первом уровне памяти/накопителя, например, чтобы увеличивать и уменьшать размер фильтра Блума на основе потребностей. На фиг.4 проиллюстрирован вариант осуществления масштабирования 400 фильтра Блума из фильтра Блума 420 в фильтр Блума 410, которое уменьшает размер фильтра Блума 420 приблизительно до половины его размера в фильтре Блума 410 для того, чтобы сделать возможным больше свободного пространства на первом уровне памяти/накопителя в обмен на более высокий FPR. Фильтр Блума можно масштабировать из второго фильтра Блума 420, который соответствует фильтру Блума 310 и содержит приблизительно четыре бита, в первый фильтр Блума 410, который содержит приблизительно два бита. По существу, каждые два бита во втором фильтре Блума 420 можно отображать в один бит в первом фильтре Блума 410. Таким образом, общее количество элементов может не меняться, но принадлежность этих элементов может быть представлена меньшим числом битов. В целом, второй фильтр Блума 420 можно сворачивать в несколько раз, чтобы получить меньший фильтр Блума 410 или даже меньшие фильтры Блума.

[0050] Размер первого фильтра Блума 410 можно масштабировать для поддержания почти постоянного уровня плотности или фиксированного FPR по мере изменения количества его элементов. Например, когда FPR первого фильтра Блума 410 приблизительно превышает предварительно заданное значение или порог, например, в связи с увеличением элементов фильтра Блума, больший фильтр Блума, такой как второй фильтр Блума 420, можно конструировать из счетного фильтра Блума 320, чтобы представлять более точную информацию о принадлежности элементов, чем первый фильтр Блума 410. Таким образом, существование счетного фильтра Блума позволяет хранить фильтр Блума на первом уровне памяти/накопителя, чтобы динамически увеличивать его размер по мере увеличения количества элементов.

[0051] Как показано на фиг.4, первый и третий биты (слева) во втором фильтре Блума 420 можно отображать в первый бит (слева) в первом фильтре Блума 410. Аналогичным образом, второй и четвертый биты во втором фильтре Блума 420 можно отображать во второй бит в первом фильтре Блума 410. Первый бит в первом фильтре Блума 410 можно задавать (например, приблизительно равным единице), если одна или обе из двух соответствующих сигнатур связаны с элементами, и их нельзя задавать (например, может быть равен приблизительно нулю), если обе соответствующие сигнатуры не связаны с элементами. Аналогичным образом, второй бит в первом фильтре Блума 410 можно задать, если одна или обе из двух соответствующих сигнатур связаны с элементами, и нельзя задавать, если обе соответствующие сигнатуры не связаны с элементами.

[0052] Если первый бит в первом фильтре Блума 410 задан, неоднозначность в отношении того, которая из двух соответствующих сигнатур задана, можно разрешить посредством проверки соответствующего счетного фильтра Блума, например, счетного фильтра Блума 320. Например, первый поднабор (слева) в счетном фильтре Блума 320 может показывать больше, чем приблизительно один элемент для первой из двух соответствующих сигнатур для первого бита во втором фильтре Блума 420, и второй поднабор в счетном фильтре Блума 320 может показывать ноль элементов для второй из двух соответствующих сигнатур. Аналогичным образом, если второй бит в первом фильтре Блума 410 задан, неоднозначность в отношении того, какая из двух соответствующих сигнатур задана, можно разрешить посредством проверки соответствующего счетного фильтра Блума 320. Например, третий поднабор в счетном фильтре Блума 320 может показывать ноль элементов для первой из двух соответствующих сигнатур для второго бита во втором фильтре Блума 420, и четвертый поднабор в счетном фильтре Блума 320 может показывать приблизительно один элемент для второй из двух соответствующих сигнатур.

[0053] Журнал переадресации информации, например, журнал 130 переадресации информации, можно хранить в памяти/запоминающей среде третьего уровня, где каждое новое информационное сообщение о маршрутизации можно присоединять к журналу. Присоединение информации о маршрутизации к журналу может позволять поддерживать и отслеживать временную линейку событий маршрутизации, что может позволять сканирование и повторное воспроизведение журнала. Дополнительно, присоединенная информация может повышать эффективность хранения, например, с использованием возможности последовательной записи в случае HDD. Журнал переадресации информации в системе памяти/накопителя третьего уровня можно использовать для восстановления системы после сбоя. Например, когда происходит сбой системы (аппаратного обеспечения или программного обеспечения), счетный фильтр Блума на втором уровне может быть полностью или частично восстановлен посредством сканирования и повторного воспроизведения журнала 130 переадресации информации, например, от точки или момента сбоя. Если память/запоминающая среда третьего уровня также повреждена, маршрутизатор контента может контактировать с соседним маршрутизатором(ами) и запрашивать поврежденную или потерянную часть журнала.

[0054] Поскольку восстанавливаемую часть можно выбирать, например, основываясь на запрошенной информации, длительность перерыва в работе для восстановления может быть по существу короткой, например, приблизительно несколько секунд. Таким образом, можно смягчать вопросы конвергенции протоколов обмена информацией о маршрутизации, таких как от Промежуточной системы к Промежуточной системе (IS-IS) и Открытый поиск кратчайшего пути (OSPF). В некоторых вариантах осуществления фильтры Блума и счетные фильтры Блума также можно хранить на третьем уровне в целях устойчивости и дублирования. Кроме того, обмен информацией о переадресации в журнале можно выполнять в форме фильтров Блума, например, вместо исходной формы информации о маршрутизации в маршрутизаторах. По существу, ширина полосы, необходимой для обмена информацией об отправке, может быть по существу уменьшена в связи с компактными размерами фильтров Блума.

[0055] Память/запоминающая среда третьего уровня, в которой находится журнал переадресации информации, может иметь наибольшую емкость и наименьшую единичную стоимость среди трех уровней системы памяти/накопителя. Память/запоминающая среда третьего уровня также может служить в качестве устойчивого накопителя для невосстанавливаемой информации об отправке, которую можно восстановить с трудом или нельзя восстановить. Журнал переадресации информации может содержать информацию, которую можно не использовать во время процесса опроса, маршрутизации и переадресации контента, например, в реальном времени. Например, современные HDD можно использовать для хранения журнала переадресации информации на третьем уровне системы памяти/накопителя. HDD представляет собой обыкновенный накопительный компонент для применений большой емкости. Например, ориентированные на эффективность последовательного интерфейса подключения дисковых накопителей (SATA) HDD могут обеспечивать задержку доступа, равную приблизительно 10 мс. Несмотря на то, что такая запоминающая среда может быть медленной в сравнении с запоминающими средами первого и второго уровня (например, DRAM и SSD), HDD могут иметь по существу более низкую единичную стоимость приблизительно 0,05 доллара США за ГБ.

[0056] Другой компонент архитектуры плоскости переадресации маршрутизатора может представлять собой таблицу предпочтения портов, которую можно хранить на первом или втором уровне системы памяти/накопителя. Таблица предпочтения портов может содержать указатель или предпочтительный порт для запрашиваемого общего префикса имени, такого, как когда общий префикс имени совпадает с множеством фильтров Блума для множества портов. Таблица предпочтения портов может точно определять часть некоторого трафика на каждый порт. Например, таблица предпочтения портов может содержать множество входов, где каждый вход может указывать на порт и связанный префикс контента. Поскольку многотрактная маршрутизация часто используется в сети контента, например, для улучшения доставки контента, пакет контента может быть согласован с множеством портов в маршрутизаторе. В отсутствие предпочтения порта для маршрутизируемого контента порты, связанные с этим контентом, можно обрабатывать одинаково и, таким образом, контент можно переадресовывать на все связанные порты. В качестве альтернативы таблицу предпочтения портов можно использовать для того, чтобы выбирать предпочтительный порт и переадресовывать контент только на предпочтительный порт. Таблицу предпочтения портов может задавать оператор, например, вручную, и она может не содержать существенно большого числа входов, и, таким образом, ее можно хранить в системе памяти/накопителя первого уровня (например, DRAM) с фильтром Блума. Если таблица предпочтения портов содержит существенно большое количество входов, тогда таблицу можно хранить в системе памяти/накопителя второго уровня (например, SSD) со счетным фильтром Блума.

[0057] На фиг.5 проиллюстрирован вариант осуществления способа переадресации маршрутизатора 500, который можно использовать для того, чтобы переадресовывать контент, основываясь на архитектуре плоскости переадресации маршрутизатора, описанной выше. Например, способ переадресации маршрутизатора 500 можно реализовать посредством маршрутизатора, который содержит систему трехуровневой памяти/накопителя. В блоке 510 контент можно принимать, например, на порте маршрутизатора. Контент может представлять собой какие-либо данные контента, такие как текст, голос, видео, телевиденье (TV), интернет и/или какой-либо специфичный контент приложения, или может представлять собой запрос контента, например, от конечного пользователя, другого маршрутизатора или сервера контента. В блоке 520 префикс контента можно получить из контента. Например, маршрутизатор может обнаруживать префикс имени в контенте. В блоке 530 множество фильтров Блума, например, на первом уровне памяти/накопителя, можно опрашивать для того, чтобы найти совпадение для префикса контента. Фильтры Блума могут быть связаны с множеством портов маршрутизатора и могут быть запрошены параллельно, например, приблизительно в один момент времени, в памяти (например, DRAM).

[0058] В блоке 540 способ 500 может определять, найдено ли совпадение для префикса контента. Если совпадение найдено, тогда способ 500 может переходить к блоку 550. Иначе способ 500 может переходить к блоку 580. В блоке 550 способ 500 может определять, найдено ли множество совпадений для префикса контента. Если находят множество совпадений, связанных с множеством портов, тогда способ 500 может переходить к блоку 560. Иначе способ 500 может переходить к блоку 570. В блоке 560 предпочтительный порт можно выбирать для переадресации контента. Предпочтительный порт можно выбирать из таблицы предпочтения портов, и он может быть связан с префиксом контента. В блоке 570 контент можно переадресовывать на все порты, которые совпадают с префиксом контента. В блоке 580 можно осуществлять лавинную маршрутизацию контента на все порты, например, за исключением входного порта, или его можно отбросить. Затем способ 500 может заканчиваться. В другом варианте осуществления способ 500 можно использовать для того, чтобы маршрутизировать какой-либо контент или данные, основываясь на адресе или префиксе, таком как IP-адреса, который может быть связан с множеством портов, с использованием множества фильтров Блума.

[0059] На фиг.6 проиллюстрирован вариант осуществления блока передатчика/приемника 600, который может представлять собой какое-либо устройство, которое передает пакеты и/или контент через сеть. Например, блок передатчика/приемника 600 может быть расположен в маршрутизаторе контента или каком-либо узле в сети контента. Блок 600 передатчика/приемника может содержать один или несколько входных портов или блоков 610 для приема пакетов, объектов или тип-длину-значение (TLV) от других сетевых компонентов, логическую схему 620 для того, чтобы определять, на какие сетевые компоненты посылать пакеты, и один или несколько выходных портов или блоков 630 для передачи кадров на другие сетевые компоненты.

[0060] Сетевые компоненты, описанные выше, можно реализовать на каком-либо сетевом компоненте общего назначения, таком как компьютер или сетевой компонент с достаточной обрабатывающей мощностью, ресурсами памяти и пропускной способностью сети, чтобы обрабатывать необходимую рабочую нагрузку, возложенную на него. На фиг.7 проиллюстрирован типичный сетевой компонент 700 общего назначения, подходящий для реализации одного или нескольких вариантов осуществления компонентов, описанных в настоящем документе. Сетевой компоненте 700 содержит процессор 702 (который можно называть центральным процессором или CPU), который связан с устройствами памяти, включая вторичный накопитель 704, постоянное запоминающее устройство (ROM) 706, оперативное запоминающее устройство (RAM) 708, устройства ввода/вывода (I/O) 710 и устройства 712 связи сети. Процессор 702 может быть реализован в виде одного или нескольких кристаллов CPU, или он может представлять собой часть одной или нескольких специализированных интегральных схем (ASIC).

[0061] Вторичный накопитель 704 типично состоит из одного или нескольких приводов дисков или накопителей на ленте и используется для энергонезависимого хранения данных и в качестве накопительного устройства при переполнении данными, если RAM 708 не достаточно велика, чтобы вмещать все рабочие данные. Вторичный накопитель 704 можно использовать для хранения программ, которые загружены в RAM 708, когда такие программы выбирают для исполнения. ROM 706 используют для хранения инструкций и, возможно, данных, которые считывают во время исполнения программы. ROM 706 представляет собой энергонезависимое устройство памяти, которое типично имеет маленькую емкость памяти относительно вторичного накопителя 704 с большей емкостью памяти. RAM 708 используют для хранения временных данных и, возможно, для хранения инструкций. Доступ как к ROM 706, так и к RAM 708 типично происходит быстрее, чем ко вторичному накопителю 704.

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

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

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

Группа изобретений относится к устройствам переадресации маршрутизатора. Технический результат заключается в обеспечении возможности реконструирования фильтра Блума и счетного фильтра Блума в случае потери информации из-за системных сбоев. Заявлены фильтр Блума, хранящийся в запоминающей среде первого уровня, и журнал переадресации информации, связанный с фильтром Блума и хранящийся в запоминающей среде второго уровня, обеспечивающие их реконструирование в случае отказов системы, а также сетевой компонент, содержащий приемник, выполненный с возможностью принимать контент, содержащий общий префикс имени, запоминающую среду первого уровня, выполненную с возможностью хранить множество фильтров Блума, связанных с множеством общих префиксов имен и множеством соответствующих портов, логическую схему, выполненную с возможностью вычислять множество сигнатур, основываясь на общем префиксе имени принятого контента, и передатчик, выполненный с возможностью переадресовывать принятый контент по меньшей мере на один из портов, которые связаны по меньшей мере с одним из фильтров Блума, если общий префикс имени представляет собой элемент по меньшей мере одного из фильтров Блума. 4 н. и 18 з.п. ф-лы, 7 ил.

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

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

3. Аппарат по п. 2, в котором фильтр Блума поддерживает маршрутизацию со скоростью приблизительно 3,2 терабита в секунду (Tbps) для относительно маленьких пакетов контента порядка килобайтов (KB), со скоростью приблизительно восемь петабитов в секунду (Pbps) для относительно большого контента порядка мегабайтов (MB), или обе.

4. Аппарат по п. 1, который дополнительно содержит счетный фильтр Блума, связанный с фильтром Блума и хранящийся в запоминающей среде третьего уровня, причем запоминающая среда первого уровня содержит динамическое оперативное запоминающее устройство (DRAM), запоминающая среда третьего уровня содержит твердотельный накопитель (SSD), и запоминающая среда второго уровня содержит накопитель на жестком диске (HDD).

5. Аппарат по п. 1, который дополнительно содержит счетный фильтр Блума, связанный с фильтром Блума и хранящийся в запоминающей среде третьего уровня, причем запоминающая среда первого уровня содержит динамическое оперативное запоминающее устройство (DRAM), запоминающая среда третьего уровня содержит память с изменением фазового состояния (РСМ), и запоминающая среда второго уровня содержит твердотельный накопитель (SSD).

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

7. Аппарат по п. 1, в котором фильтр Блума связан с одним портом на маршрутизаторе.

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

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

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

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

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

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

14. Сетевой компонент по п. 9, в котором счетные фильтры Блума, фильтры Блума или оба восстанавливают за относительно короткий интервал времени приблизительно в несколько секунд по отношению к процессу переадресации контента.

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

16. Способ по п. 15, который дополнительно содержит:
выбор предпочтительного порта, который связан с общим префиксом контента, в таблице предпочтения портов, если общий префикс контента совпадает с множеством портов, связанных с множеством фильтров Блума; и
переадресацию контента на предпочтительный порт.

17. Способ по п. 15, который дополнительно содержит:
вычисление множества сигнатур для нового общего префикса контента с использованием множества хэш-функций;
установку множества битов, которые соответствуют вычисленным сигнатурам в фильтре Блума, который связан с портом, присвоенным новому общему префиксу контента; и
увеличение на единицу множества счетчиков, соответствующих сигнатурам в счетном фильтре Блума, который связан с фильтром Блума и портом.

18. Способ по п. 15, который дополнительно содержит:
вычисление множества сигнатур для общего префикса контента, который представляет собой элемент фильтра Блума и предварительно присвоен порту, связанному с фильтром Блума;
очистку множества битов, которые соответствуют вычисленным сигнатурам в фильтре Блума, который связан с портом; и
снижение на единицу множества счетчиков, соответствующих сигнатурам в счетном фильтре Блума, который связан с фильтром Блума и портом.

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

20. Аппарат по п. 19, в котором запоминающая среда первого уровня содержит твердотельный накопитель (SSD), и запоминающая среда второго уровня содержит накопитель на жестком диске (HDD).

21. Аппарат по п. 19, в котором запоминающая среда первого уровня содержит память с изменением фазового состояния (РСМ), и запоминающая среда второго уровня содержит твердотельный накопитель (SSD).

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