Устройство обработки пакета, способ конфигурирования записи потока и программа

Устройство обработки пакета, способ конфигурирования записи потока и программа

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ

[0001] [Перекрестная ссылка на связанные заявки]

Настоящая заявка испрашивает приоритет японской заявки на патент № 2012-276734 (поданной 19 декабря 2012 года), содержимое которой тем самым включено в его целостности посредством ссылки в настоящее описание. Настоящее изобретение относится к устройству обработки пакетов, способу конфигурирования записи потока и программе, и в частности, к устройству обработки пакетов, способу конфигурирования записи потока и программе, где хранятся множество записей потоков и обработанные пакеты.

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

[0002] Непатентная литература 1 и 2 предлагает технологию, известную как OpenFlow. В OpenFlow связь осуществляется в качестве непрерывного потока и управления маршрутом, восстановления после отказа, балансировки нагрузки и оптимизации, выполняемых на основе каждого потока. Коммутатор OpenFlow, как задано в Непатентной литературе 2, снабжен безопасным каналом для связи с контроллером OpenFlow и работает согласно таблице потоков, в которой добавление или переписывание инструктируется подходящим образом посредством контроллера OpenFlow. В таблице потоков для каждого потока имеются определения наборов условий совпадения (Поля Совпадения) для сопоставления с заголовками пакета, статистическая информация потока (Счетчики) и инструкции (Инструкции), которые определяют содержимое обработки (относится к “5.2 Таблицам Потоков” в Непатентной литературе 2).

[0003] Например, когда коммутатор OpenFlow принимает пакет, выполняется поиск записи, имеющей условие соответствия (относится к “5.3 Соответствиям” в Непатентной литературе 2), которое соответствует информации заголовка принятого пакета из таблицы потоков. В результате поиска в случае, когда записи, соответствующие принятому пакету, найдены, коммутатор OpenFlow обновляет статистическую информацию потока (Счетчики) и также реализует содержимое обработки (передачу пакета от заданного порта, лавинная рассылка, отбрасывание, или подобное), описанное в поле Инструкции соответствующих записей для принятого пакета. С другой стороны в результате поиска в случае, когда запись, соответствующая принятому пакету, не найдена, коммутатор OpenFlow передает запрос о наборе записи контроллеру OpenFlow через безопасный канал, то есть запрос на передачу информации управления для того, чтобы обработать принятый пакет. Коммутатор OpenFlow принимает записи потоков, выявленные посредством содержимого обработки, и обновляет таблицу потоков. Таким образом, коммутатор OpenFlow выполняет отправку пакета, используя записи, хранимые в таблице потоков, в качестве информации управления.

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

[0005] Патентная литература 2 раскрывает управляющий сдвиговый регистр буфера (сдвиговый регистр, имеющий функцию обработки приоритета) для передачи ячеек АТМ, сохраненных в устройстве АТМ-коммутатора во время выполнения администрирования в соответствии с конечными сроками ячеек памяти.

СПИСОК ЦИТАТ

ПАТЕНТНАЯ ЛИТЕРАТУРА

[0006]

[PTL 1] Публикация Kokai Японского патента № JP09-81099A

[PTL 2] Публикация Kokai Японского патента № JP07-254906A

НЕПАТЕНТНАЯ ЛИТЕРАТУРА

[0007] [НПЛ 1]

Nick McKeown и семь других авторов, “OpenFlow: Enabling Innovation in Campus Networks”, [online], [Поиск, выполненный 24 ноября 2012], Интернет <URL: http://www.openflow.org/documents/openflow-wp-latest.pdf>

[НПЛ 2]

“Openflow Switch Specification” Version 1.3.1 Implemented (Wire Protocol 0x04), [online], [Поиск, выполненный 11 декабря 2012], Интернет <URL: https://www.opennetworking.org/images/stories/downloads/specification/openflow-spec-v1.3.1.pdf>

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

Техническая проблема

[0008] Следующий анализ дан согласно настоящему изобретению. В коммутаторе OpenFlow из Непатентной литературы 1 или 2 известно, что записи потока скомпонованы и хранятся в порядке приоритетов, и извлечение записей потока выполняется с высокой скоростью.

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

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

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

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

Решение проблемы

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

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

[0015] Согласно третьему аспекту предоставляется программа, которая исполняется на компьютере, установленном в устройстве обработки пакетов, содержащем таблицу потоков, в которой записи потока могут быть сохранены в областях, распределенных в порядке группы приоритетов, и блок извлечения записи, который выполняет сканирование с начала таблицы потоков, извлекает запись, имеющую условие совпадения, которое совпадает с принятым пакетом и выявляет обработку, которая должна быть применена к принятому пакету, причем программа выполняет: процесс различения, в случае приема новой записи потока от предписанного устройства управления, группы приоритетов, к которым новая запись потока принадлежит, на основании информации приоритета, включенной в новую запись потока; процесс различения приоритета уровня, который используется для того, чтобы выявить позицию в пределах различенной группы приоритетов на основании информации приоритета, включенной в упомянутую новую запись потока; и процесс сохранения новой записи потока в области, соответствующей группе приоритетов и приоритета уровня 2, в таблице потоков. Необходимо отметить, что эта программа может быть записана на считываемом компьютером (не временном) носителе информации. Таким образом, настоящее изобретение может быть воплощено в качестве компьютерного программного продукта.

Выгодные эффекты изобретения

[0016] Согласно настоящему изобретению возможно уменьшить затраты на сортировку, когда новую запись потока записывают в устройство обработки пакетов, где записи потока скомпонованы и хранятся в порядке приоритетов.

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

[0017] Фиг. 1 является диаграммой, показывающей конфигурацию устройства обработки пакетов в первом примерном варианте осуществления настоящего изобретения.

Фиг. 2 является диаграммой, показывающей подробную конфигурацию устройства обработки пакетов в первом примерном варианте осуществления изобретения.

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

Фиг. 4 является диаграммой, показывающей пример таблицы администрирования записи, хранимой в блоке администрирования записи устройства обработки пакетов в первом примерном варианте осуществления изобретения.

Фиг. 5 является диаграммой, показывающей отношения соответствия между таблицей потоков согласно Фиг. 3 и таблицей администрирования записи согласно Фиг. 4.

Фиг. 6 является диаграммой последовательности операций, представляющей первый примерный вариант осуществления изобретения.

Фиг. 7 является диаграммой, представляющей изменение (необходимость сдвига) соответствующих таблиц в случае нового приема новой записи F потока, в состоянии, показанном на Фиг. 5.

Фиг. 8 является диаграммой, представляющей операции в случае решения, что обработка сдвига записи необходима в этапе S003 на Фиг. 6.

Фиг. 9 является диаграммой, представляющей изменение (необходимость сдвига) соответствующих таблиц в случае нового приема новой записи G потока в состоянии, показанном в Фиг. 7.

Фиг. 10 является диаграммой сценария на Фиг. 9.

Фиг. 11 является диаграммой сценария на Фиг. 10.

ОПИСАНИЕ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ

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

[0019] Настоящее изобретение в его примерном варианте осуществления может реализоваться посредством устройства обработки пакетов, снабженного блоком администрирования записи (22 на Фиг. 1) и блоком извлечения записи (21 на Фиг. 1), который сканирует таблицу потоков (211 на Фиг. 1) с начала, извлекает запись, имеющую условие совпадения, которое совпадает с принятым пакетом, и выявляет обработку, которая должна быть применена к принятому пакету.

[0020] Более конкретно, таблица потоков (211 на Фиг. 1) способна хранить записи потока в областях, распределенных в порядке групп приоритетов. В случае приема новой записи потока от предписанного устройства управления (10 на Фиг. 1) блок администрирования записи (22 на Фиг. 1) выявляет позицию хранения в таблице потоков согласно тому, к которой группе приоритетов среди множества групп приоритетов новая запись потока принадлежит, и приоритету уровня 2, который выявляет позицию в пределах группы приоритетов.

[0021] Как описано выше, в таблице потоков (211 на Фиг. 1), так как область распределена в порядке группы приоритетов, если пустая область существует в области приоритета, к которой новая запись потока принадлежит, сортировка на основании приоритета является ненужной. Даже там, где нет никакой пустой области в релевантной позиции группы приоритетов, к которой принадлежит новая запись потока, возможно уменьшить затраты на сортировку, когда новая запись потока записывается, без выполнения обработки, чтобы осуществлять поиск самой близкой пустой области и сдвинуть запись потока или записи.

[0022] [Первый примерный вариант осуществления]

Фиг. 1 является диаграммой, показывающей конфигурацию устройства обработки пакетов в первом примерном варианте осуществления настоящего изобретения. Со ссылками на фиг. 1 показана конфигурация, которая включает в себя устройство 10 администрирования, которое передает сообщение установки записи потока, которое инструктирует, что запись потока должна быть установлена в таблице 211 потоков, относительно устройства 20 обработки пакетов; и устройство 20 обработки пакетов, которое обращается к записи потока, принятой от устройства 10 управления, чтобы обработать пакеты, принятые от другого устройства обработки пакетов, терминала, сервера или подобного.

[0023] Устройство 10 управления создает запись потока, подлежащую установке в устройство 20 обработки пакетов в соответствии с запросом установить запись потока, от устройства 20 обработки пакетов или заранее определенной политики связи, и передает сообщение установки записи потока в устройство 20 обработки пакетов. Необходимо отметить, что для записи потока могут использоваться ассоциации условий совпадения (Поля Совпадения) для сопоставления с заголовками пакета, и инструкции (Инструкции), которые определяют содержимое обработки. Необходимо отметить, что относительно этого типа устройства 10 управления возможно использовать контроллер OpenFlow из Непатентной литературы 1 или 2.

[0024] Устройство 20 обработки пакетов снабжено блоком 21 извлечения записи, который извлекает запись потока, имеющую условие совпадения, совпадающее с принятым пакетом, из таблицы 211 потоков, и блоком 22 администрирования записи, который администрирует конфигурацию записи потока и т.п. в таблице 211 потоков. Относительно этого типа устройства 10 управления помимо физических коммутаторов, имеющих функциональные возможности, подобные коммутаторам OpenFlow Непатентной литературы 1 или 2, можно указать виртуальный коммутатор, который работает на виртуальном сервере, или коммутатор программного обеспечения, который обрабатывает пакеты от высокоуровневого приложения, работающего на пользовательском терминале или подобном.

[0025] Фиг. 2 является диаграммой, показывающей детальную конфигурацию вышеупомянутого устройства обработки пакетов. В примере на Фиг. 2 таблица 211 потоков способна к хранению N записей потока в порядке более высокого приоритета. При приеме пакета от другого устройства обработки пакетов, терминала, сервера или подобного блок 21 извлечения записи продолжает сопоставлять заголовок или подобное принятого пакета в порядке от записи 1, которая обладает самым высоким приоритетом в таблице 211 потоков, с условиями совпадения записи потока. В результате сопоставления в случае, когда есть совпадение условия совпадения и принятого пакета в записи X на Фиг. 2, блок 21 извлечения записи исполняет обработку содержимого (направление принятого пакета, переписывание заголовка, или подобное), как описано в инструкциях (Инструкции) записи потока, которая совпадает с условием совпадения. Кроме того, когда запись потока, совпадающая с принятым пакетом, как описано выше, найдена (“совпадение условия” на Фиг. 2), блок 21 извлечения записи пропускает сопоставление записей потока в записи X и ниже (“пропуск извлечения”) на Фиг. 2).

[0026] Фиг. 3 является диаграммой, показывающей пример таблицы 211 потоков. В таблице 211 потоков настоящего примерного варианта осуществления множество областей распределены в порядке группы приоритетов, и записи потока могут быть сохранены в порядке групп приоритетов. Внутригрупповые уровни приоритетов (приоритеты уровня 2) для записей потока, принадлежащих к одной и той же группе приоритетов, представлены посредством позиций хранения в пределах областей, распределенных индивидуальным группам приоритетов (в случае настоящего примерного варианта осуществления, чем выше приоритет, тем выше позиция хранения). Например, запись 1 и запись 2 на Фиг. 3 обе принадлежат к группе приоритетов = 2, которая обладает самым высоким приоритетом среди существующих записей потока, и так как запись 1 обладает более высоким внутригрупповым приоритетом (приоритет уровня 2), чем запись 2, записи потока устанавливаются в порядке запись 1, запись 2. Точно так же запись (n-1) и запись N на Фиг. 3 обе принадлежат группе приоритетов = 8, которая обладает самым низким приоритетом среди существующих записей потока, и так как запись (n-1) обладает более высоким внутригрупповым приоритетом (приоритет уровня 2), чем запись N, записи потока устанавливаются в порядке запись (n-1), запись N. Необходимо отметить, что области с обозначением “:” на Фиг. 3 являются пустыми областями.

[0027] Количество областей для хранения записей потока, распределенных в каждой группе приоритетов в таблице 211 потоков, может быть выявлено заранее, или может быть динамически изменено во время операции. Таким образом, количество пустых записей в каждой группе приоритетов в таблице 211 потоков может быть легко получено.

[0028] Блок 22 администрирования записи снабжен таблицей 222 администрирования записи, которая администрирует содержимое и позицию набора записей потока в таблице 211 потоков, и блоком 221 установки записи, который выполняет операции, такие как запрос на запись таблицы 211 потоков и т.п., на основании таблицы 222 администрирования записи.

[0029] Фиг. 4 является диаграммой, показывающей пример таблицы 222 администрирования записи. Со ссылками на фиг. 4 относительно каждой из записей потока, сохраненных в таблице 211 потоков, диаграмма показывает записи, ассоциирующие группу приоритетов, внутригрупповой приоритет (приоритет уровня 2) и содержимое записи потока, с номером записи. Например, запись Номер 1 в таблице 222 администрирования записи имеет содержимое, ассоциирующее позицию хранения (приоритет) записи (n-1) таблицы 211 потоков на Фиг. 3 и содержимое записи потока.

[0030] Фиг. 5 является диаграммой, показывающей отношения соответствия между таблицей 211 потоков на Фиг. 3 и таблицей 222 администрирования записи на Фиг. 4. При приеме нового сообщения установки записи потока от устройства 10 управления блок 221 установки записи получает группу приоритетов и внутригрупповой приоритет из ее содержимого, делает запись этого в таблице 222 администрирования записи и записывает запись потока в позиции, идентифицированной посредством группы приоритетов и внутригруппового приоритета таблицы 211 потоков. При приеме сообщения инструкции удаления записи потока от устройства 10 управления блок 221 установки записи обращается к таблице 222 администрирования записи и после удаления релевантной записи потока в таблице 211 потоков удаляет запись, соответствующую удаленной записи потока в таблице 222 администрирования записи.

[0031] Необходимо отметить, что в случае записи новой записи потока, например, между записью 1 и записью 2 и между записью (n-1) и записью N на Фиг. 3, могут быть случаи, когда позиция, идентифицированная согласно группе приоритетов и внутригрупповому приоритету, не является пустой в таблице 211 потоков. В этом случае блок 221 установки записи осуществляет поиск самой близкой пустой области и сдвигает запись потока, чтобы защитить область для сохранения релевантной новой записи потока. Например, в случае приема записи потока, подлежащей сохранению между записью 1 и записью 2 на Фиг. 3 от устройства 10 управления блок 221 установки записи сдвигает запись 2 вниз на один шаг и сохраняет новую запись потока в позиции, где запись 2 была сохранена прежде.

[0032] Необходимо отметить, что блок 22 извлечения записи блока 20 обработки пакетов, показанный на Фиг. 1 и Фиг. 2, может быть реализован посредством компьютерной программы, которая исполняет оперативную обработку таблицы 211 потоков, работающую вместе с таблицей 222 администрирования записи, описанной выше, на компьютере, конфигурирующим устройство 20 обработки пакетов, используя его аппаратное обеспечение.

[0033] Ниже дается детальное описание соответствующих операций существующего примерного варианта осуществления со ссылками на чертежи. Фиг. 6 является диаграммой последовательности, представляющей операции первого примерного варианта осуществления изобретения. Устройство 10 управления создает запись потока, подлежащую установке в устройство 20 обработки пакетов в соответствии с запросом установить запись потока от устройства 20 обработки пакетов или заранее определенной политикой связи, и передает сообщение установки записи потока в устройство 20 обработки пакетов (этап S001).

[0034] При приеме нового сообщения установки записи потока устройство 20 обработки пакетов идентифицирует группу приоритетов, к которой новая запись потока принадлежит, и внутригрупповой приоритет (приоритет уровня 2) (этап S002). Относительно способа идентификации группы приоритетов и внутригруппового приоритета можно рассмотреть различные способы: например, возможно использовать старший(ие) бит(ы) информации приоритета, назначенной в новом сообщении установки записи потока от устройства 10 управления, при идентификации группы приоритетов и использовать более младший(иу) бит(ы) при идентификации внутригруппового приоритета.

[0035] Затем устройство 20 обработки пакетов подтверждает, пуста ли позиция в таблице 211 потоков или нет, соответствующая идентифицированной группе приоритетов и внутригрупповому приоритету, то есть, необходима ли операция сдвига существующей записи или нет (этап S003).

[0036] В результате подтверждения в случае, когда позиция в таблице 211 потоков, соответствующая идентифицированной группе приоритетов и внутригрупповому приоритету, пуста, то есть, в случае, когда новая запись потока может быть сохранена без выполнения операции сдвига существующей записи ("Нет" в этапе S003), устройство 20 обработки пакетов записывает новую запись потока в релевантной позиции таблицы 221 потоков (этапы S004, S005) и записывает позиции (номер записи) в таблице 211 потоков в колонке номера записи релевантной записи таблицы 222 администрирования записи (этап S006).

[0037] Фиг. 7 является диаграммой, представляющей изменение в соответствующих таблицах в случае нового приема новой записи потока F, имеющей приоритет группы “4” и внутригрупповой приоритет “2”, относительно состояния, показанного на Фиг. 5. Устройство 20 обработки пакетов подтверждает, пуста ли позиция, соответствующая приоритету группы “4” и внутригрупповому приоритету “2” в таблице 211 потоков, или нет. В этот момент на Фиг. 5, так как позиция, соответствующая приоритету группы “4” и внутригрупповому приоритету “2” в таблице 211 потоков, пуста, устройство 20 обработки пакетов записывает запись потока F в (x-1)-ую область от вершины таблицы 211 потоков. Устройство 20 обработки пакетов записывает (x-1) в качестве номера записи запись потока F в таблицу 222 администрирования записи.

[0038] Фиг. 8 является диаграммой последовательности, представляющей операции в случае решения, в результате подтверждения в этапе S003 на Фиг. 6, что нет пустой позиции в таблице 211 потоков, соответствующей идентифицированной группе приоритетов и внутригрупповому приоритету, то есть, что операция сдвига существующей записи необходима ("Да" в этапе S003). В этом случае устройство 20 обработки пакетов осуществляет поиск пустой области в той же самой группе приоритетов, самой близкой к релевантной позиции таблицы 211 потоков. В результате поиска в случае, когда пустая область не найдена в той же самой группе приоритетов, устройство 20 обработки пакетов удаляет сообщение установки записи потока, и возвращает ошибку устройству 10 управления (этап S103). Устройство 10 управления принимает ответ ошибки и рассматривает удаление ненужной записи потока из таблицы 211 потоков.

[0039] С другой стороны, в результате поиска в случае, когда пустая область найдена в той же самой группе приоритетов, устройство 20 обработки пакетов создает пустую область посредством сдвига записи потока, принадлежащей к той же самой группе приоритетов, в направлении пустой области с позицией, соответствующей идентифицированной группе приоритетов и внутригрупповому приоритету в качестве начальной точки (этап S104). После этого устройство 20 обработки пакетов возвращается к этапу S004 и последующим на Фиг. 6 и исполняет запись новой записи потока в таблицу 211 потоков и обновление таблицы 222 администрирования записи.

[0040] Фиг. 9 является диаграммой, представляющей изменение в соответствующих таблицах в случае нового приема новой записи G потока, имеющей приоритет группы “2” и внутригрупповой приоритет “4”, относительно состояния, показанного на Фиг. 7. Устройство 20 обработки пакетов подтверждает, есть ли пустая область в позиции, соответствующей приоритету группы “2” и внутригрупповому приоритету “4” в таблице 211 потоков, или нет. В этот момент на Фиг. 7, так как запись 1 (внутригрупповой приоритет “2”) и запись 2 (внутригрупповой приоритет “6”), принадлежащие приоритету группы “2”, сохранены рядом, то нет никакой пустой позиции, соответствующей приоритету группы “2” и внутригрупповому приоритету “4” в таблице 211 потоков.

[0041] Соответственно, как показано на Фиг. 10, устройство 20 обработки пакетов обнаруживает, что есть пустая область после записи 2 в таблице 211 потоков и исполняет обработку сдвига, чтобы сдвинуть позицию хранения записи 2 на один шаг вниз. В сочетании с этим устройство 20 обработки пакетов модифицирует номер записи для записи, которая была номером 2 записи прежде в таблице 222 администрирования записи, на “3”. Необходимо отметить, что операция сдвига здесь может быть только новой величиной записи потока, то есть, сдвигом только на 1, или может быть сдвигом, чтобы сделать множество областей пустым, в ожидании будущего использования.

[0042] Когда пустая область может быть защищена посредством обработки сдвига, устройство 20 обработки пакетов, как показано на Фиг. 11, записывает новую запись G потока (новая запись 2) в качестве номера 2 записи в таблицу 211 потоков. Устройство 20 обработки пакетов записывает “2” в колонке номера записи новой записи G потока в таблице 222 администрирования записи.

[0043] Как ясно из вышеупомянутого описания, согласно существующему примерному варианту осуществления возможно реализовать как ускорение обработки совпадения посредством компоновки записей потока в порядке приоритетов так и уменьшить затраты на сортировку посредством записи новых записей потока.

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

[0045] Например, в примерном варианте осуществления, описанном выше, были даны описания, в которых более младший бит(ы) уровня информации приоритета, заданный в новом сообщении установки записи потока от устройства 10 управления, используется в качестве внутригруппового приоритета или приоритетов, но также возможно использовать порядок прибытия сообщения установки записи потока от устройства 10 управления в качестве внутригруппового приоритета (приоритет уровня 2). Делая так, возможно далее ограничить частоту возникновения обработки сдвига записей потока.

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

[0047] (1) В случае, когда есть пустая область в другой группе приоритетов таблицы 211 потоков, новая запись потока записывается в релевантной пустой области. Наряду с этим, область, в которой записана новая запись потока, добавляется к областям, распределенным релевантной группе приоритетов таблицы 211 потоков (область, в которой была записана новая запись потока, удаляется из областей, распределенных другой группе приоритетов, где есть пустая область). В этом случае, когда есть множество групп приоритетов с пустыми областями, возможно выбрать группу приоритетов с самым низким приоритетом, или группу приоритетов, самую близкую к приоритету. Необходимо отметить, что в этом случае, чтобы не концентрировать распределение областей в конкретной группе приоритетов, распределение пустой области может быть возвращено к первоначальной группе приоритетов ко времени удаления записи потока релевантной группы приоритетов.

[0048] (2) В случае, когда нет никакой пустой области во всех группах приоритетов таблицы 211 потоков запись потока, выбранная посредством предписанной ссылки, удаляется, и выдается отчет на устройство 10 управления. Необходимо отметить, что относительно предписанной ссылки запись потока, предназначенная для удаления, может быть выбрана согласно ссылке, такой как группа низкого приоритета и внутригрупповой приоритет, по меньшей мере, недавно используемый или подобное.

[0049] (3) Несколько областей таблицы 211 потоков могут быть защищены как совместно используемые области, не принадлежащие к какой-либо из групп приоритетов в исходном состоянии. Делая так, возможно использовать области таблицы 211 потоков более эффективно.

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

[Первый Режим]

(Со ссылками на устройство обработки пакетов согласно первому аспекту, описанному выше).

[Второй Режим]

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

[Третий Режим]

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

[Четвертый Режим]

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

[Пятый Режим]

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

[Шестой Режим]

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

[Седьмой Режим]

(Со ссылками на способ конфигурации записи потока согласно второму аспекту, описанному выше).

[Восьмой Режим]

(Со ссылками на программу согласно третьему аспекту, описанному выше).

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

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

СПИСОК ССЫЛОЧНЫХ ПОЗИЦИЙ

[0052]

10 устройство управления

20 устройство обработки пакетов

21 блок извлечения записи

22 блок администрирования записи

211 таблица потоков

221 блок установки записи

222 таблица администриров