[go: up one dir, main page]

WO2015133448A1 - パケット処理装置、パケット処理方法およびプログラム - Google Patents

パケット処理装置、パケット処理方法およびプログラム Download PDF

Info

Publication number
WO2015133448A1
WO2015133448A1 PCT/JP2015/056143 JP2015056143W WO2015133448A1 WO 2015133448 A1 WO2015133448 A1 WO 2015133448A1 JP 2015056143 W JP2015056143 W JP 2015056143W WO 2015133448 A1 WO2015133448 A1 WO 2015133448A1
Authority
WO
WIPO (PCT)
Prior art keywords
action
rule
packet processing
packet
pointer
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2015/056143
Other languages
English (en)
French (fr)
Inventor
智久 横田
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NEC Corp
Original Assignee
NEC Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by NEC Corp filed Critical NEC Corp
Priority to EP15757950.9A priority Critical patent/EP3116178B1/en
Priority to US15/122,133 priority patent/US10284478B2/en
Priority to JP2016506487A priority patent/JP6217839B2/ja
Publication of WO2015133448A1 publication Critical patent/WO2015133448A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/24—Traffic characterised by specific attributes, e.g. priority or QoS
    • H04L47/2483—Traffic characterised by specific attributes, e.g. priority or QoS involving identification of individual flows
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/64—Hybrid switching systems
    • H04L12/6418—Hybrid transport
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H04L47/20—Traffic policing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/90—Buffering arrangements
    • H04L49/901—Buffering arrangements using storage descriptor, e.g. read or write pointers

Definitions

  • the present invention is based on a Japanese patent application: Japanese Patent Application No. 2014-041624 (filed on Mar. 4, 2014), and the entire description of the application is incorporated herein by reference.
  • the present invention relates to a packet processing device, a packet processing method, and a program, and more particularly, to a packet processing device, a packet processing method, and a program in a centralized control type network.
  • packet processing units are often implemented by software.
  • NFV Network Functions Virtualization
  • SDN Software-Defined Networking
  • Non-Patent Documents 1 and 2 describe OpenFlow.
  • OpenFlow captures communication as an end-to-end flow and performs path control, failure recovery, load balancing, and optimization on a per-flow basis.
  • the OpenFlow switch (OFS: OpenFlow Switch) defined in Non-Patent Document 2 has a secure channel for communication with the OpenFlow controller (OFC: OpenFlow Controller), and is a flow table that is instructed to be added or rewritten as appropriate from the OFC. Works according to.
  • the OFS searches the flow table for an entry having a matching condition (see “5.3 Matching” in Non-Patent Document 2) that matches the header information of the received packet.
  • the OFS updates the flow statistical information (counter) and processes the process contents (from the specified port) described in the instruction field of the entry for the received packet. Packet transmission, flooding, discarding, etc.).
  • OFS requests entry setting to the OFC via the secure channel, that is, a control information transmission request for processing the received packet. (Packet-In message) is transmitted.
  • the OFS receives the flow entry in which the processing content is defined and updates the flow table. In this way, OFS performs packet transfer using the entry stored in the flow table as control information.
  • the processing speed is slower than hardware processing.
  • the rule search at the time of packet processing is performed by software, the search process takes a long time compared to the hardware process, except for some search methods such as exact match search. In many cases, a longest match search, a mask search, or a range specification search is required. In these cases, the software search is slower in processing speed than the hardware search.
  • the flow cache table is a table for holding a plurality of rule searches necessary for each packet as a cache. By using the flow cache table, it is possible to collectively acquire a plurality of rule search results by searching once to which flow a packet belongs.
  • the flow cache table in the related technology is created and managed by a process such as a rule control unit separate from the packet processing unit.
  • a process such as a rule control unit separate from the packet processing unit.
  • the packet processing unit accesses the flow cache table, it is necessary to perform exclusive processing between the packet processing unit and the rule control unit. Therefore, when the packet processing unit accesses the flow cache table, there is a problem that a waiting time due to exclusive processing occurs, and time is required for packet processing.
  • An object of the present invention is to provide a packet processing device, a packet processing method, and a program that contribute to solving such a problem.
  • a packet processing device includes a storage unit that holds an action table that includes an action that defines processing contents of a packet and a rule table that includes a rule for searching for an action to be applied to the packet.
  • the packet processing apparatus includes a rule control unit that updates rules included in the rule table. Further, the packet processing device retrieves an action to be applied to the received packet from the action table using the rule table, processes the packet according to the retrieved action, and stores a pointer for the retrieved action.
  • a processing unit is provided. Here, after storing the pointer, the packet processing unit determines whether or not the rule table has been updated by the rule control unit, and if not, stores the action applied to the received packet. Extract from the action table according to the pointer.
  • a packet processing method includes a step in which a computer stores, in a storage unit, an action table that includes an action that defines a processing content of the packet and a rule table that includes a rule for searching for an action to be applied to the packet.
  • the packet processing method includes a step in which the first process updates a rule included in the rule table.
  • the second process retrieves an action to be applied to the received packet from the action table using the rule table, processes the packet according to the retrieved action, and retrieves the action Accumulating pointers to.
  • the second process determines whether or not the rule table has been updated by the first process after the pointer has been accumulated. Extracting an action to be applied to the action table according to the accumulated pointer.
  • a program causes a computer to execute a process of storing an action table including an action for defining processing contents of a packet and a rule table including a rule for searching for an action applied to the packet in a storage unit. Further, the program causes the computer to execute a process in which a first process updates a rule included in the rule table. Furthermore, the program searches the action table using the rule table for an action to be applied to the received packet by the second process, processes the packet according to the searched action, and points to the searched action. The computer is caused to execute a process for storing. In addition, the program determines whether or not the rule table has been updated by the first process after the second process has accumulated the pointer.
  • the program is applied to the received packet.
  • the computer is caused to execute processing for extracting an action to be performed from the action table according to the accumulated pointer.
  • the program can also be provided as a program product recorded in a non-transitory computer-readable storage medium.
  • the packet processing device According to the packet processing device, the packet processing method, and the program according to the present invention, it is possible to speed up the packet processing by the packet processing unit implemented by software.
  • a lockless flow cash table is proposed.
  • the flow cache table is implemented in a lockless manner, thereby eliminating the waiting time when accessing the flow cache table and speeding up the packet processing.
  • the packet processor creates and manages the flow cache table. Also, by performing processing for synchronizing the flow cache table with the rule table in the packet processing unit, access to the flow cache table by the rule control unit is unnecessary, and a lockless flow cache table is realized.
  • FIG. 1 is a block diagram illustrating the configuration of a packet processing device according to an embodiment.
  • the packet processing apparatus 10 includes an action table 26 that includes an action that defines the processing content of a packet, and a storage unit 13 that stores a rule table 24 that includes a rule for searching for an action to be applied to the packet.
  • the rule control unit 12 that updates the rule included in the rule table 24 and the action to be applied to the received packet are searched from the action table 26 using the rule table 24, and the packet is processed according to the searched action.
  • a packet processing unit 16 for storing a pointer to the searched action. After storing the pointer, the packet processing unit 16 determines whether or not the rule table 24 has been updated by the rule control unit 12. If not, the action applied to the received packet is determined according to the stored pointer. Extract from table 26.
  • the following configuration can be employed.
  • an identifier for example, a sequence number
  • the packet processing unit 16 holds the identifier recorded in the storage unit (shared memory 14) when accumulating the pointer.
  • the packet processing unit 16 compares the stored identifier with the identifier recorded in the storage unit (shared memory 14) by the rule control unit 12, thereby accumulating the pointer, and then the rule control unit 12 updates the rule table 24. It is determined whether or not it has been done.
  • the rule control unit 12 updates the sequence number in the entry of the action table 26 when the entry is updated (for example, added / changed / deleted).
  • the packet processing unit 16 caches the sequence number in the entry of the action table 26 as a cookie in addition to caching the pointer to the action table 26.
  • the packet processing unit 16 searches the flow cache table 28 and refers to the action entry according to the pointer to the action table 26 registered in the flow cache table 28 when a hit is found. At this time, the packet is cached in the flow cache table 28.
  • the sequence number cookie is compared with the current sequence number registered in the action table 26. If the two match, the packet processing unit 16 determines that the action table 26 has not changed from the previous time, and continues packet processing.
  • the packet processing unit 16 determines that the action table 26 has been changed, and determines that the flow cache entry is invalid. At this time, the packet processing unit 16 searches the rule table 24, references the action table 26, and registers the flow cache table 28 in order to create a new flow cache entry.
  • the flow cache table 28 in addition to speeding up rule search by the flow cache table 28, the flow cache table 28 can be implemented without a lock, and the waiting time when the packet processing unit 16 accesses the flow cache table 28 is eliminated.
  • the packet processing speed can be increased when the packet processing unit 16 is implemented by software.
  • FIG. 2 is a block diagram illustrating an example of the configuration of the packet processing apparatus 10 according to the present embodiment.
  • the packet processing apparatus 10 includes a rule control unit 12, a shared memory 14, and a packet processing unit 16.
  • the shared memory 14 holds a rule table 24 and an action table 26.
  • the packet processing unit 16 has a local memory 18 and holds a flow cache table 28 on the local memory 18.
  • the rule control unit 12 performs management such as addition / change / deletion for the action table 26 used in packet processing and the rule table 24 used for searching the action table 26. Since the action table 26 and the rule table 24 need to be accessed from both the rule control unit 12 and the packet processing unit 16, they are mounted in the shared memory 14.
  • the packet processing unit 16 first searches the rule table 24 when receiving a packet. Next, the packet processing unit 16 refers to the corresponding action entry in the action table 26 according to the pointer obtained as a search result, and performs packet processing according to the action entry.
  • the packet processing unit 16 registers a flow cache entry using the flow information as a key after packet processing in the flow cache table 28 on the local memory in the packet processing unit 16. Thereby, the search of the action entry by the packet processing unit 16 can be speeded up.
  • this embodiment employs the following method.
  • the rule control unit 12 registers a sequence number in the action table 26 when updating (for example, adding / changing / deleting) the rule table 24.
  • the sequence number refers to information indicating that the information in the action table has been rewritten when the action table is updated.
  • a value that does not overflow for example, a time stamp value
  • the sequence number is not limited to the time stamp value.
  • the packet processing unit 16 caches the sequence number in the action table 26 as cookie information when creating the flow cache table 28 and registers it in the flow cache table 28.
  • the packet processing unit 16 searches the flow cache table 28 and refers to the action table 26, and compares the cookie information of the sequence number in the flow cache table 28 with the current sequence number in the action table 26. If the two match, the packet processing unit 16 determines that the rule table 24 has not been updated since the previous time, and the flow cache table 28 is valid, and continues processing.
  • the packet processing unit 16 determines that the rule table 24 has been updated by the rule control unit 12 from the time when the rule table 24 referred to the previous time and created the flow cache entry, and the corresponding entry in the flow cache table 28 is It is determined to be invalid. In this case, the packet processing unit 16 turns on the invalid flag for the corresponding entry in the flow cache table 28. In addition, after setting the invalid flag to ON, the packet processing unit 16 searches the rule table 24 to create a new flow cache entry, and refers to the action table 26. At this time, if the search is hit, the packet processing unit 16 processes the packet according to the hit entry. Further, the packet processing unit 16 registers a new entry in the flow cache table 28 after packet processing.
  • the packet processing unit 16 periodically searches the flow cache table 28 and identifies an entry whose invalid flag is ON. When the packet processing unit 16 identifies an entry whose invalid flag is ON, the packet processing unit 16 deletes the corresponding entry.
  • the configuration of the table is changed when the entry is deleted from the flow cache table 28, the table configuration is also changed (for example, when the hash table is formed by the chain method, the chain configuration is changed). Recombination operation).
  • FIG. 3 to 5 are sequence diagrams illustrating an example of the operation of the packet processing device 10.
  • FIG. 3 is a sequence diagram illustrating an operation of registering 24 rules in the rule table by the rule control unit 12 and an operation of processing the 1st packet and the 2nd packet belonging to the same flow by the packet processing unit 16.
  • the rule control unit 12 updates (for example, adds, changes, or deletes a rule) to the rule table 24 that is used to search the action table 26 (step S2).
  • the rule control unit 12 adds, changes, or deletes the rule table 24, the rule control unit 12 registers a sequence number in the action table 26 (step S1).
  • the packet processing unit 16 searches the rule table 24 (step S5). Next, the packet processing unit 16 refers to the corresponding action entry in the action table 26 according to the pointer obtained as a search result (step S6), and performs packet processing according to the action entry (step S7).
  • the packet processing unit 16 registers a flow cache entry with the flow information as a key in the flow cache table 28 on the local memory in the packet processing unit 16 (step S8).
  • the packet processing unit 16 may process the packet (step S7) after registering the entry in the flow cache table (step S8).
  • the packet processing unit 16 caches the sequence number in the action table 26 as cookie information and registers it in the flow cache table 28. Further, the packet processing unit 16 sets the invalid flag for the flow cache entry to OFF in order to indicate that the registered flow cache entry is valid.
  • the packet processing unit 16 When receiving the second and subsequent packets belonging to the same flow (step S9), the packet processing unit 16 searches the flow cache table 28 (step S10), and refers to the action table 26 (step S11). The sequence number cookie information in the cache table 28 is compared with the current sequence number in the action table 26. If the two match, the packet processing unit 16 determines that the rule table 24 has not been updated since the previous time, and the flow cache table 28 is valid, and continues processing. That is, the packet processing unit 16 processes the packet based on the action entry in the action table 26 obtained according to the flow cache entry registered in the flow cache table 28 (step S12).
  • FIG. 4 is a sequence diagram illustrating the operation of the packet processing apparatus 10 when the rule control unit 12 adds, changes, or deletes the action table 26 and the rule table 24.
  • the rule control unit 12 adds, changes, or deletes the rule table 24 (step S22).
  • the rule control unit 12 registers a new sequence number in the action table 26 when adding, changing, or deleting the rule table 24.
  • the packet processing unit 16 When the packet processing unit 16 receives the packet after the rule change by the rule control unit 12 (step S23), the packet processing unit 16 searches the flow cache table 28 (step S24) and refers to the action table 26 (step S25). The sequence number cookie information in the cache table 28 is compared with the current sequence number in the action table 26. Since the latter sequence number is updated to a new number by the rule control unit 12, the two do not match. Therefore, the packet processing unit 16 determines that the rule table 24 has been updated by the rule control unit 12 from the time when the rule table 24 referred to the previous time and created the flow cache entry, and determines that the corresponding entry in the flow cache table 28 is invalid. . In this case, the packet processing unit 16 turns on the invalid flag for the corresponding entry in the flow cache table 28 (step S26).
  • the packet processing unit 16 searches the rule table 24 to create a new flow cache entry (step S27), and refers to the action table 26 according to the searched rule (step S28). ). At this time, if the search is hit, the packet processing unit 16 processes the packet according to the hit entry (step S29). The packet processing unit 16 registers a new entry in the flow cache table 28 after packet processing (step S30). The packet processing unit 16 may process the packet (step S29) after registering the entry in the flow cache table (step S30).
  • FIG. 5 is a sequence diagram illustrating an operation of deleting invalid entries in the flow cache table 28.
  • the packet processing unit 16 periodically searches the flow cache table 28 to identify an entry whose invalid flag is ON (step S41).
  • the packet processing unit 16 deletes the entry and updates the flow cache table 28 (step S42).
  • the search of the rule table 24 occurs a plurality of times depending on packet processing.
  • a plurality of rule table 24 searches can be bypassed, and all actions can be specified by a single flow cache table 28 search. Thereby, the number of searches can be reduced, and the packet processing can be speeded up.
  • the search of the rule table 24 is not necessarily an exact match search.
  • the software processing requires more processing time than the hardware processing.
  • the flow cache table 28 can be implemented by exact match search, for example, it can be implemented by a hash table. According to the hash search, a high-speed search comparable to hardware processing can be performed even in software processing. As described above, according to the flow cache table 28, it is possible to speed up the packet processing by speeding up the search.
  • the packet processing unit 16 performs addition / change / deletion processing on the flow cache table 28, and other processes do not access the flow cache table 28.
  • the flow cache table 28 can be implemented in a lockless manner, so that no waiting time occurs due to exclusive processing when the packet processing unit 16 accesses. Therefore, useless cost due to idling of the packet processing unit 16 (processor) does not occur, and the packet processing can be speeded up.
  • the packet processing unit 16 may sequentially delete the corresponding entry.
  • the packet processing unit 16 determines that the flow cache table 28 is invalid, the invalid flag of the corresponding entry is set to ON, and the actual deletion process and the update process of the flow cache table 28 are thereby performed. Were carried out separately by periodic processing.
  • a method of separately mounting a flow cache entry list table is possible.
  • the packet processing unit 16 adds an entry to the flow cache table 28
  • the packet processing unit 16 also adds an entry to the flow cache entry list table.
  • the packet processing unit 16 determines that the corresponding entry is invalid
  • the packet processing unit 16 sets an invalid flag for the corresponding entry in the flow cache entry list table instead of the flow cache table 28.
  • it is not necessary to search the flow cache table 28 at the time of periodic invalid entry search processing, and it is possible to specify an invalid entry without searching only by referring to the flow cache entry list table sequentially and sequentially. It becomes possible.
  • the present invention can be applied to a field where packet processing such as NFV (Network Functions Virtualization) and SDN (Software-Defined Networking) needs to be implemented by software as an example.
  • packet processing such as NFV (Network Functions Virtualization) and SDN (Software-Defined Networking) needs to be implemented by software as an example.
  • NFV Network Functions Virtualization
  • SDN Software-Defined Networking
  • the packet processing unit includes a flow cache table that stores a pointer to the searched action; A flag table for storing a flag indicating the validity of the pointer stored in the flow cache table, When the accumulated pointer is invalidated, a flag corresponding to the invalidated pointer is set invalid in the flag table, and the invalidated pointer is changed by referring to the flag table in the predetermined cycle.
  • the packet processing device according to the sixth aspect.
  • the packet processing method according to the second aspect is as described above.
  • packet processing device 10 packet processing device 12 rule control unit 13 storage unit 14 shared memory 16 packet processing unit 18 local memory 24 rule table 26 action table 28 flow cache table

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

　パケット処理装置は、パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを保持する記憶部と、ルールテーブルに含まれるルールを更新するルール制御部と、受信したパケットに適用するアクションを、ルールテーブルを用いてアクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積するパケット処理部と、を備え、パケット処理部は、ポインターを蓄積した後、ルール制御部によりルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを蓄積したポインターに従ってアクションテーブルから抽出する。ソフトウェアで実装されたパケット処理部によるパケット処理を高速化する。

Description

パケット処理装置、パケット処理方法およびプログラム
　［関連出願についての記載］
　本発明は、日本国特許出願：特願２０１４－０４１６２４号（２０１４年３月４日出願）に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
　本発明は、パケット処理装置、パケット処理方法およびプログラムに関し、特に、集中制御型のネットワークにおけるパケット処理装置、パケット処理方法およびプログラムに関する。
　近年、通信システムに設けられたスイッチ等のパケット処理装置において、パケット処理部をソフトウェアで実装することが多くなってきている。特に、汎用プロセッサの性能向上とＮＦＶ(Network Functions Virtualization)やＳＤＮ（Software-Defined Networking）の潮流により、パケット処理部をソフトウェアで実装するニーズが高まっている。また、ソフトウェア処理に基づいてパケット処理を行う際に、ハードウェア処理と同等の処理性能を満たすことが求められている。
　ＮＦＶやＳＤＮに基づいて集中制御型のネットワークを実現する技術として、例えば、非特許文献１、２にオープンフロー（OpenFlow）が記載されている。オープンフローは、通信をエンドツーエンドのフローとして捉え、フロー単位で経路制御、障害回復、負荷分散、最適化を行うものである。非特許文献２に規定されているオープンフロースイッチ（ＯＦＳ：OpenFlow Switch）は、オープンフローコントローラ（ＯＦＣ：OpenFlow Controller）との通信用のセキュアチャネルを備え、ＯＦＣから適宜追加または書き換え指示されるフローテーブルに従って動作する。フローテーブルには、フロー毎に、パケットヘッダと照合するマッチ条件（Match Fields）と、フロー統計情報（Counters）と、処理内容を定義したインストラクション（Instructions）と、の組が定義される（非特許文献２の「5.2 Flow Table」の項参照）。
　ＯＦＳは、パケットを受信すると、フローテーブルから、受信パケットのヘッダ情報に適合するマッチ条件（非特許文献２の「5.3 Matching」参照）を持つエントリーを検索する。検索の結果、受信パケットに適合するエントリーが見つかった場合、ＯＦＳは、フロー統計情報（カウンタ）を更新するとともに、受信パケットに対して、当該エントリーのインストラクションフィールドに記述された処理内容（指定ポートからのパケット送信、フラッディング、廃棄など）を実施する。一方、検索の結果、受信パケットに適合するエントリーが見つからなかった場合、ＯＦＳは、セキュアチャネルを介して、ＯＦＣに対してエントリー設定の要求、すなわち、受信パケットを処理するための制御情報の送信要求（Packet-Inメッセージ）を送信する。ＯＦＳは、処理内容が定められたフローエントリを受け取ってフローテーブルを更新する。このように、ＯＦＳは、フローテーブルに格納されたエントリーを制御情報として用いてパケット転送を行う。
Nick McKeownほか７名、"OpenFlow: Enabling Innovation in Campus Networks"、[online]、［平成２６（２０１４）年２月２４日検索］、インターネット〈URL:http://www.openflow.org/documents/openflow-wp-latest.pdf〉 "OpenFlow Switch Specification"Version 1.3.1 (Wire Protocol 0x04)、[online]、［平成２６（２０１４）年２月２４日検索］、インターネット〈URL:https://www.opennetworking.org/images/stories/downloads/specification/openflow-spec-v1.3.1.pdf〉
　上記非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明者によってなされたものである。
　上述のとおり、汎用プロセッサの性能向上、および、ＮＦＶ(Network Function Virtualization) やＳＤＮ（Software-Defined Networking）の潮流により、パケット処理部をソフトウェアで実装する機会が増加している。
　しかし、一般に、パケット処理部をソフトウェアで実装した場合、ハードウェア処理と比較して処理速度が遅いことが知られている。特に、パケット処理時のルール検索をソフトウェアで行う場合、完全一致検索のような一部の検索方式を除くと、ハードウェア処理と比較して検索処理に長い時間を要する。また、最長一致検索やマスク検索、範囲指定の検索が必要とされる場合が多く、これらの場合には、ソフトウェア検索によると、ハードウェア検索と比較して処理速度が遅くなる。
　ソフトウェアに基づくパケット処理を高速化するための関連技術として、フローキャッシュテーブルを用いる方法が発明されている。フローキャッシュテーブルとは、パケット毎に必要な複数回のルール検索をキャッシュとして保持するためのテーブルである。フローキャッシュテーブルを用いることにより、パケットがいずれのフローに属するかを一回検索することにより、複数回分のルール検索結果をまとめて取得することが可能となる。
　ところで、上記関連技術におけるフローキャッシュテーブルは、パケット処理部とは別個のルール制御部のようなプロセスによって作成および管理されている。かかる技術によると、パケット処理部がフローキャッシュテーブルにアクセスする場合、パケット処理部とルール制御部との間で排他処理を行う必要が生じる。したがって、パケット処理部がフローキャッシュテーブルにアクセスする際、排他処理による待ち時間が生じ、パケット処理に時間を要するという問題がある。
　そこで、ソフトウェアで実装されたパケット処理部によるパケット処理を高速化することが課題となる。本発明の目的は、かかる課題解決に寄与するパケット処理装置、パケット処理方法およびプログラムを提供することにある。
　本発明の第１の態様によると、パケット処理装置が提供される。前記パケット処理装置は、パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを保持する記憶部を備えている。また、前記パケット処理装置は、前記ルールテーブルに含まれるルールを更新するルール制御部を備えている。さらに、前記パケット処理装置は、受信したパケットに適用するアクションを、前記ルールテーブルを用いて前記アクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積するパケット処理部を備えている。ここで、前記パケット処理部は、前記ポインターを蓄積した後、前記ルール制御部により前記ルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを前記蓄積したポインターに従って前記アクションテーブルから抽出する。
　本発明の第２の態様によると、パケット処理方法が提供される。前記パケット処理方法は、コンピュータが、パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを記憶部に保持する工程を含む。また、前記パケット処理方法は、第１のプロセスが、前記ルールテーブルに含まれるルールを更新する工程を含む。さらに、前記パケット処理方法は、第２のプロセスが、受信したパケットに適用するアクションを、前記ルールテーブルを用いて前記アクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積する工程を含む。また、前記パケット処理方法は、前記第２のプロセスが、前記ポインターを蓄積した後、前記第１のプロセスにより前記ルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを前記蓄積したポインターに従って前記アクションテーブルから抽出する工程を含む。
　本発明の第３の態様によると、プログラムが提供される。前記プログラムは、パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを記憶部に保持する処理をコンピュータに実行させる。また、前記プログラムは、第１のプロセスが、前記ルールテーブルに含まれるルールを更新する処理前記コンピュータに実行させる。さらに、前記プログラムは、第２のプロセスが、受信したパケットに適用するアクションを、前記ルールテーブルを用いて前記アクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積する処理を前記コンピュータに実行させる。また、前記プログラムは、前記第２のプロセスが、前記ポインターを蓄積した後、前記第１のプロセスにより前記ルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを前記蓄積したポインターに従って前記アクションテーブルから抽出する処理を前記コンピュータに実行させる。なお、プログラムは、非一時的なコンピュータ可読記録媒体（non-transitory computer-readable storage medium）に記録されたプログラム製品として提供することもできる。
　本発明に係るパケット処理装置、パケット処理方法およびプログラムによると、ソフトウェアで実装されたパケット処理部によるパケット処理を高速化することが可能となる。
一実施形態に係るパケット処理装置の構成を例示するブロック図である。 第１の実施形態に係るパケット処理装置の構成を例示するブロック図である。 第１の実施形態に係るパケット処理装置の動作を例示するシーケンス図である。 第１の実施形態に係るパケット処理装置の動作を例示するシーケンス図である。 第１の実施形態に係るパケット処理装置の動作を例示するシーケンス図である。
　はじめに、一実施形態の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
　一実施形態では、ロックレスなフローキャッシュテーブルを提案する。フローキャッシュテーブルによるルール検索高速化に加えて、フローキャッシュテーブルをロックレスで実装することでフローキャッシュテーブルに対するアクセス時の待ち時間を解消し、パケット処理の高速化を図る。
　ロックレスなフローキャッシュテーブルを実現する手段として、パケット処理部でフローキャッシュテーブルの作成・管理を行う。また、フローキャッシュテーブルをルールテーブルと同期する処理をパケット処理部で行うことで、ルール制御部によるフローキャッシュテーブルに対するアクセスを不要とし、ロックレスなフローキャッシュテーブルを実現する。
　図１は、一実施形態に係るパケット処理装置の構成を例示するブロック図である。図１を参照すると、パケット処理装置１０は、パケットの処理内容を規定するアクションを含むアクションテーブル２６と、パケットに適用するアクションを検索するためのルールを含むルールテーブル２４を保持する記憶部１３と、ルールテーブル２４に含まれるルールを更新するルール制御部１２と、受信したパケットに適用するアクションを、ルールテーブル２４を用いてアクションテーブル２６から検索し、検索したアクションに従って当該パケットを処理するとともに、検索したアクションに対するポインターを蓄積するパケット処理部１６と、を備えている。パケット処理部１６は、ポインターを蓄積した後、ルール制御部１２によりルールテーブル２４が更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを、蓄積したポインターに従ってアクションテーブル２６から抽出する。
　このように、ルール制御部１２ではなく、パケット処理部１６自身が検索したアクションに対するポインターを蓄積することで、ルール制御部１２とパケット処理部１６との間の排他処理が不要となる。したがって、パケット処理部１６をソフトウェアで実装した場合におけるパケット処理を高速化することが可能となる。
　パケット処理部１６が、ポインターを蓄積した後、ルール制御部１２によりルールテーブル２４が更新されたか否かを判定するために、例えば、以下の構成を採用することができる。
　図２を参照すると、ルール制御部１２は、ルールテーブル２４に含まれるルールを更新する際、当該更新を識別する識別子（例えば、シーケンス番号）を記憶部（例えば、共有メモリ１４が保持するアクションテーブル２６内）に記録し、パケット処理部１６は、前記ポインターを蓄積する際、記憶部（共有メモリ１４）に記録された識別子を保持する。パケット処理部１６は、保持した識別子とルール制御部１２により記憶部（共有メモリ１４）に記録された識別子を比較することにより、前記ポインターを蓄積した後、ルール制御部１２によりルールテーブル２４が更新されたか否かを判定する。
　より具体的には、ルール制御部１２はエントリーの更新（例えば、追加・変更・削除など）時にアクションテーブル２６のエントリー内のシーケンス番号を更新する。パケット処理部１６はフローキャッシュテーブル２８を作成する際に、アクションテーブル２６へのポインターをキャッシュするのに加えて、アクションテーブル２６のエントリー内のシーケンス番号をクッキーとしてキャッシュする。パケット処理部１６はフローキャッシュテーブル２８を検索し、ヒットした場合にフローキャッシュテーブル２８に登録されたアクションテーブル２６へのポインターに従い、アクションエントリーを参照するが、このときフローキャッシュテーブル２８内にキャッシュしたシーケンス番号のクッキーとアクションテーブル２６に登録されている現在のシーケンス番号を比較する。両者が一致すれば、パケット処理部１６はアクションテーブル２６は前回から変更がないと判定し、パケット処理を継続する。一方、両者が一致しない場合、パケット処理部１６はアクションテーブル２６が変更されていると判定し、フローキャッシュエントリーは無効であると判定する。このとき、パケット処理部１６は、新規のフローキャッシュエントリーを作成するために、ルールテーブル２４の検索とアクションテーブル２６の参照、フローキャッシュテーブル２８の登録を行う。
　かかる構成によると、フローキャッシュテーブル２８によるルール検索高速化に加えて、フローキャッシュテーブル２８をロックレスで実装することができ、パケット処理部１６がフローキャッシュテーブル２８にアクセスする際の待ち時間を解消し、パケット処理部１６をソフトウェアで実装した場合におけるパケット処理の高速化が可能となる。
＜実施形態１＞
　次に、第１の実施形態に係るパケット処理装置について、図面を参照して説明する。図２は、本実施形態のパケット処理装置１０の構成を一例として示すブロック図である。
　図２を参照すると、パケット処理装置１０は、ルール制御部１２、共有メモリ１４、および、パケット処理部１６を備えている。共有メモリ１４は、ルールテーブル２４とアクションテーブル２６を保持している。パケット処理部１６は、ローカルメモリ１８を有し、ローカルメモリ１８上にフローキャッシュテーブル２８を保持している。
　本実施形態では、ルールテーブル２４の検索でヒットした場合に、その結果として得られるアクションテーブル２６へのポインター情報をパケット処理部１６内のローカルなフローキャッシュテーブル２８に登録する。同一のフローに属する後続パケットについては、パケット処理部１６によるルールテーブル２４の検索をバイパスし、フローキャッシュテーブル２８を検索することで検索処理を高速化する。
　ルール制御部１２は、パケット処理で使用されるアクションテーブル２６と、アクションテーブル２６を検索するために使用されるルールテーブル２４に対して、追加・変更・削除といった管理を行う。アクションテーブル２６およびルールテーブル２４はルール制御部１２とパケット処理部１６の双方からアクセスする必要があるため、共有メモリ１４に実装される。
　パケット処理部１６は、パケット受信時に、まず、ルールテーブル２４を検索する。次に、パケット処理部１６は、検索結果として得られるポインターに従って、アクションテーブル２６内の該当アクションエントリーを参照し、アクションエントリーに従ってパケット処理する。
　ここで、同一のフローに属する後続のパケットついては、同一のアクションエントリーで処理することができる。そこで、パケット処理部１６は、パケット処理後にフロー情報をキーとしたフローキャッシュエントリーを、パケット処理部１６内のローカルメモリ上のフローキャッシュテーブル２８に登録する。これにより、パケット処理部１６によるアクションエントリーの検索を高速化することができる。
　また、パケット処理部１６で作成したフローキャッシュテーブル２８と、ルールテーブル２４との間で同期をとる必要がある。同期をとるために、本実施形態では、以下の方法を採用する。
　ルール制御部１２は、ルールテーブル２４に対して、更新（例えば、追加・変更・削除など）を行う際、アクションテーブル２６内にシーケンス番号を登録する。ここで、シーケンス番号とは、アクションテーブルを更新した際に、アクションテーブルの情報が書き換えられたことを示す情報をいう。一例として、シーケンス番号として、オーバフローしないような値（例えば、タイムスタンプ値等）を用いることができる。なお、本発明において、シーケンス番号は、タイムスタンプ値に限定されない。
　パケット処理部１６は、フローキャッシュテーブル２８の作成時に、アクションテーブル２６内のシーケンス番号をクッキー情報としてキャッシュし、フローキャッシュテーブル２８内に登録する。
　パケット処理部１６は、フローキャッシュテーブル２８を検索し、アクションテーブル２６を参照する際に、フローキャッシュテーブル２８内のシーケンス番号のクッキー情報と、アクションテーブル２６内の現在のシーケンス番号とを比較する。両者が一致した場合、パケット処理部１６は、ルールテーブル２４が前回から更新されておらず、フローキャッシュテーブル２８は有効であるものと判定して、処理を継続する。
　一方、両者が一致しない場合、パケット処理部１６はルールテーブル２４が前回参照してフローキャッシュエントリーを作成した時点からルール制御部１２によって更新されたものと判定し、フローキャッシュテーブル２８の該当エントリーは無効であると判定する。この場合、パケット処理部１６は、フローキャッシュテーブル２８の該当エントリーに対する無効フラグをＯＮにする。また、パケット処理部１６は、無効フラグをＯＮに設定後、新規のフローキャッシュエントリーを作成するためにルールテーブル２４を検索し、アクションテーブル２６を参照する。このとき、検索がヒットすれば、パケット処理部１６はヒットしたエントリーに従ってパケットを処理する。また、パケット処理部１６は、パケット処理後、フローキャッシュテーブル２８に新しいエントリーを登録する。
　ただし、この方法だけでは、フローキャッシュテーブル２８内の無効エントリーが残存し、メモリリソースが枯渇するおそれがある。そこで、パケット処理部１６は、フローキャッシュテーブル２８を周期的に検索し、無効フラグがＯＮのエントリーを特定する。パケット処理部１６は、無効フラグがＯＮのエントリーを特定すると、該当エントリーの削除を行う。なお、フローキャッシュテーブル２８から該当エントリーを削除した際にテーブルの構成に変更が生じる場合には、併せて、テーブルの構成の変更(例えば、ハッシュテーブルをチェーン法で形成しているときには、チェーンの組み換え操作)を行う。
　次に、図面を参照して、本実施形態のパケット処理装置１０の動作について説明する。図３～図５は、パケット処理装置１０の動作を一例として示すシーケンス図である。
　図３は、ルール制御部１２によるルールテーブルへ２４のルールの登録の動作と、パケット処理部１６による同一のフローに属する1stパケットと2ndパケットの処理の動作を例示するシーケンス図である。
　図３を参照すると、ルール制御部１２は、アクションテーブル２６を検索するのに使用されるルールテーブル２４に対して、更新（例えば、ルールの追加、変更または削除）を行う（ステップＳ２）。ルール制御部１２は、ルールテーブル２４に対して、追加、変更または削除を行う際、アクションテーブル２６内にシーケンス番号を登録する（ステップＳ１）。
　パケット処理部１６が受信したパケットがファーストパケットである場合（ステップＳ３）、フローキャッシュテーブル２８には、当該パケットに相当するフローキャッシュエントリーが未登録である（ステップＳ４）。そこで、パケット処理部１６は、ルールテーブル２４を検索する（ステップＳ５）。次に、パケット処理部１６は、検索結果として得られるポインターに従って、アクションテーブル２６内の該当アクションエントリーを参照し（ステップＳ６）、アクションエントリーに従ってパケット処理する（ステップＳ７）。
　また、パケット処理部１６は、パケット処理の後、フロー情報をキーとしたフローキャッシュエントリーを、パケット処理部１６内のローカルメモリ上のフローキャッシュテーブル２８に登録する（ステップＳ８）。なお、パケット処理部１６は、フローキャッシュテーブルへのエントリーの登録後（ステップＳ８）、パケットを処理（ステップＳ７）してもよい。
　また、パケット処理部１６は、フローキャッシュテーブル２８の作成時に、アクションテーブル２６内のシーケンス番号をクッキー情報としてキャッシュし、フローキャッシュテーブル２８内に登録する。さらに、パケット処理部１６は、登録したフローキャッシュエントリーが有効であることを示すために、当該フローキャッシュエントリーに対する無効フラグをＯＦＦに設定する。
　パケット処理部１６は、同一のフローに属する２番目以降のパケットを受信すると（ステップＳ９）、フローキャッシュテーブル２８を検索し（ステップＳ１０）、アクションテーブル２６を参照する際に（ステップＳ１１）、フローキャッシュテーブル２８内のシーケンス番号のクッキー情報と、アクションテーブル２６内の現在のシーケンス番号を比較する。両者が一致した場合、パケット処理部１６は、ルールテーブル２４が前回から更新されておらず、フローキャッシュテーブル２８は有効であると判定して、処理を継続する。すなわち、パケット処理部１６は、フローキャッシュテーブル２８に登録されたフローキャッシュエントリーに従って得られたアクションテーブル２６内のアクションエントリーに基づいて、当該パケットを処理する（ステップＳ１２）。
　図４は、ルール制御部１２がアクションテーブル２６と、ルールテーブル２４に対して、追加、変更または削除を行った場合のパケット処理装置１０の動作を例示するシーケンス図である。
　図４を参照すると、ルール制御部１２は、ルールテーブル２４に対して、追加、変更または削除を行う（ステップＳ２２）。また、ルール制御部１２は、ルールテーブル２４に対して、追加、変更または削除を行う際、アクションテーブル２６内に新たなシーケンス番号を登録する。
　パケット処理部１６は、ルール制御部１２よるルール変更後のパケットを受信すると（ステップＳ２３）、フローキャッシュテーブル２８を検索し（ステップＳ２４）、アクションテーブル２６を参照する際に（ステップＳ２５）、フローキャッシュテーブル２８内のシーケンス番号のクッキー情報と、アクションテーブル２６内の現在のシーケンス番号とを比較する。後者のシーケンス番号はルール制御部１２より新しい番号に更新されているため、両者は一致しない。そこで、パケット処理部１６はルールテーブル２４が前回参照してフローキャッシュエントリーを作成した時点からルール制御部１２によって更新されたものと判定し、フローキャッシュテーブル２８の該当エントリーは無効であると判定する。この場合、パケット処理部１６は、フローキャッシュテーブル２８の該当エントリーに対する無効フラグをＯＮにする（ステップＳ２６）。
　また、パケット処理部１６は、無効フラグをＯＮに設定後、新規のフローキャッシュエントリーを作成するためにルールテーブル２４を検索し（ステップＳ２７）、検索したルールに従ってアクションテーブル２６を参照する（ステップＳ２８）。このとき、検索がヒットすれば、パケット処理部１６はヒットしたエントリーに従ってパケットを処理する（ステップＳ２９）。また、パケット処理部１６は、パケット処理後、新しいエントリーをフローキャッシュテーブル２８に登録する（ステップＳ３０）。なお、パケット処理部１６は、フローキャッシュテーブルへのエントリーの登録後（ステップＳ３０）、パケットを処理（ステップＳ２９）してもよい。
　図５は、フローキャッシュテーブル２８内の無効エントリーを削除する動作を例示するシーケンス図である。図５を参照すると、パケット処理部１６は、フローキャッシュテーブル２８を周期的に検索し、無効フラグがＯＮのエントリーを特定する（ステップＳ４１）。パケット処理部１６は、無効フラグがＯＮのエントリーを特定すると、該当エントリーの削除とフローキャッシュテーブル２８の更新を行う（ステップＳ４２）。
　次に、本実施形態のパケット処理装置１０による効果について説明する。ルールテーブル２４の検索はパケット処理によっては複数回発生する。フローキャッシュテーブル２８を用いることにより、複数回のルールテーブル２４検索をバイパスし、一度のフローキャッシュテーブル２８検索によりすべてのアクションを特定することができる。これにより、検索回数を削減でき、パケット処理を高速化することが可能となる。
　また、ルールテーブル２４の検索は完全一致検索とは限らない。最長一致検索やマスク検索、範囲指定エントリーの検索を行う場合、ソフトウェア処理ではハードウェア処理と比較して検索に多くの処理時間を要する。フローキャッシュテーブル２８は完全一致検索で実装することができるため、例えば、ハッシュテーブルで実装することが可能である。ハッシュ検索によると、ソフトウェア処理であっても、ハードウェア処理に匹敵する高速な検索が可能となる。このように、フローキャッシュテーブル２８によると、検索の高速化により、パケット処理を高速化することが可能となる。
　さらに、本実施形態では、パケット処理部１６がフローキャッシュテーブル２８に対して追加・変更・削除処理を行い、他のプロセスがフローキャッシュテーブル２８にアクセスすることがない。これにより、フローキャッシュテーブル２８をロックレスで実装することができるため、パケット処理部１６がアクセスする際に排他処理により待ち時間が発生しない。したがって、パケット処理部１６(プロセッサ)の空転による無駄なコストが発生せず、パケット処理を高速化することができる。
＜他の実施形態＞
　第１の実施形態では、パケット処理部１６がフローキャッシュテーブル２８を無効と判定した場合、該当エントリーの無効フラグをＯＮに設定し、実際の削除処理とそれによるフローキャッシュテーブル２８の更新処理は別途周期的な処理で実施するものとした。
　他の実施形態として、パケット処理部１６は、フローキャッシュテーブル２８が無効であると判定した際、該当エントリーを逐次削除処理するようにしてもよい。
　また、第１の実施形態では、パケット処理部１６がフローキャッシュテーブル２８を無効と判定した場合、該当エントリーの無効フラグをＯＮに設定し、実際の削除処理とそれによるフローキャッシュテーブル２８の更新処理は別途周期的な処理で実施するものとした。
　他の実施形態として、別途、フローキャッシュエントリーリストテーブルを実装する方法も可能である。パケット処理部１６はフローキャッシュテーブル２８にエントリーを追加した際、フローキャッシュエントリーリストテーブルにもエントリーを追加する。パケット処理部１６は該当エントリーを無効と判定した際、フローキャッシュテーブル２８ではなく、フローキャッシュエントリーリストテーブルの該当エントリーに無効フラグを設定する。これにより、周期的な無効エントリーの検索処理時には、フローキャッシュテーブル２８を検索する必要がなく、フローキャッシュエントリーリストテーブルを横断的に順次エントリー参照するだけで、検索なしで無効エントリーを特定することが可能になる。
　本発明は、一例として、ＮＦＶ(Network Functions Virtualization)やＳＤＮ（Software-Defined Networking）のようなパケット処理をソフトウェアで実装する必要がある分野に適用することができる。
　なお、本発明において、下記の形態が可能である。
［形態１］
　上記第１の態様に係るパケット処理装置のとおりである。
［形態２］
　前記ルール制御部は、前記ルールテーブルに含まれるルールを更新する際、該更新を識別する識別子を前記記憶部に記録し、
　前記パケット処理部は、前記ポインターを蓄積する際、前記記憶部に記録された識別子を保持する
　形態１に記載のパケット処理装置。
［形態３］
　前記パケット処理部は、前記保持した識別子と前記ルール制御部により前記記憶部に記録された識別子を比較することにより、前記ポインターを蓄積した後、前記ルール制御部により前記ルールテーブルが更新されたか否かを判定する
　形態２に記載のパケット処理装置。
［形態４］
　前記パケット処理部は、前記保持した識別子と前記ルール制御部により前記記憶部に記録された識別子が一致しない場合、前記蓄積したポインターを無効化する
　形態２または３に記載のパケット処理装置。
［形態５］
　前記パケット処理部は、前記蓄積したポインターのうちの無効化されたものを所定のタイミングで特定し、特定したポインターを削除する
　形態４に記載のパケット処理装置。
［形態６］
　前記パケット処理部は、前記蓄積したポインターのうちの無効化されたものを所定の周期で、または、無効化された際に削除する
　形態５に記載のパケット処理装置。
［形態７］
　前記パケット処理部は、検索したアクションに対するポインターを蓄積するフローキャッシュテーブルと、
　前記フローキャッシュテーブルに蓄積したポインターの有効性を示すフラグを蓄積するフラグテーブルと、を有し、
　前記蓄積したポインターが無効化されると、無効化されたポインターに対応するフラグを前記フラグテーブルにおいて無効に設定し、前記所定の周期で前記フラグテーブルを参照することにより、無効化されたポインターを特定する
　形態６に記載のパケット処理装置。
［形態８］
　上記第２の態様に係るパケット処理方法のとおりである。
［形態９］
　前記第１のプロセスは、前記ルールテーブルに含まれるルールを更新する際、該更新を識別する識別子を前記記憶部に記録し、
　前記第２のプロセスは、前記ポインターを蓄積する際、前記記憶部に記録された識別子を保持する
　形態８に記載のパケット処理方法。
［形態１０］
　前記第２のプロセスは、前記保持した識別子と前記第１のプロセスにより前記記憶部に記録された識別子を比較することにより、前記ポインターを蓄積した後、前記第１のプロセスにより前記ルールテーブルが更新されたか否かを判定する
　形態９に記載のパケット処理方法。
［形態１１］
　前記第２のプロセスは、前記保持した識別子と前記第１のプロセスにより前記記憶部に記録された識別子が一致しない場合、前記蓄積したポインターを無効化する
　形態９または１０に記載のパケット処理方法。
［形態１２］
　上記第３の態様に係るプログラムのとおりである。
［形態１３］
　前記第１のプロセスは、前記ルールテーブルに含まれるルールを更新する際、該更新を識別する識別子を前記記憶部に記録し、
　前記第２のプロセスは、前記ポインターを蓄積する際、前記記憶部に記録された識別子を保持する
　形態１２に記載のプログラム。
［形態１４］
　前記第２のプロセスは、前記保持した識別子と前記第１のプロセスにより前記記憶部に記録された識別子を比較することにより、前記ポインターを蓄積した後、前記第１のプロセスにより前記ルールテーブルが更新されたか否かを判定する
　形態１３に記載のプログラム。
［形態１５］
　前記第２のプロセスは、前記保持した識別子と前記第１のプロセスにより前記記憶部に記録された識別子が一致しない場合、前記蓄積したポインターを無効化する
　形態１３または１４に記載のプログラム。
　なお、上記非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
１０　　パケット処理装置
１２　　ルール制御部
１３　　記憶部
１４　　共有メモリ
１６　　パケット処理部
１８　　ローカルメモリ
２４　　ルールテーブル
２６　　アクションテーブル
２８　　フローキャッシュテーブル

Claims (10)

  1. 　パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを保持する記憶部と、
    　前記ルールテーブルに含まれるルールを更新するルール制御部と、
    　受信したパケットに適用するアクションを、前記ルールテーブルを用いて前記アクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積するパケット処理部と、を備え、
    　前記パケット処理部は、前記ポインターを蓄積した後、前記ルール制御部により前記ルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを前記蓄積したポインターに従って前記アクションテーブルから抽出する
    　ことを特徴とするパケット処理装置。
  2. 　前記ルール制御部は、前記ルールテーブルに含まれるルールを更新する際、該更新を識別する識別子を前記記憶部に記録し、
    　前記パケット処理部は、前記ポインターを蓄積する際、前記記憶部に記録された識別子を保持する
    　請求項１に記載のパケット処理装置。
  3. 　前記パケット処理部は、前記保持した識別子と前記ルール制御部により前記記憶部に記録された識別子を比較することにより、前記ポインターを蓄積した後、前記ルール制御部により前記ルールテーブルが更新されたか否かを判定する
    　請求項２に記載のパケット処理装置。
  4. 　前記パケット処理部は、前記保持した識別子と前記ルール制御部により前記記憶部に記録された識別子が一致しない場合、前記蓄積したポインターを無効化する
    　請求項２または３に記載のパケット処理装置。
  5. 　前記パケット処理部は、前記蓄積したポインターのうちの無効化されたものを所定のタイミングで特定し、特定したポインターを削除する
    　請求項４に記載のパケット処理装置。
  6. 　前記パケット処理部は、前記蓄積したポインターのうちの無効化されたものを所定の周期で、または、無効化された際に削除する
    　請求項５に記載のパケット処理装置。
  7. 　前記パケット処理部は、検索したアクションに対するポインターを蓄積するフローキャッシュテーブルと、
    　前記フローキャッシュテーブルに蓄積したポインターの有効性を示すフラグを蓄積するフラグテーブルと、を有し、
    　前記蓄積したポインターが無効化されると、無効化されたポインターに対応するフラグを前記フラグテーブルにおいて無効に設定し、前記所定の周期で前記フラグテーブルを参照することにより、無効化されたポインターを特定する
    　請求項６に記載のパケット処理装置。
  8. 　コンピュータが、パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを記憶部に保持する工程と、
    　第１のプロセスが、前記ルールテーブルに含まれるルールを更新する工程と、
    　第２のプロセスが、受信したパケットに適用するアクションを、前記ルールテーブルを用いて前記アクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積する工程と、
    　前記第２のプロセスが、前記ポインターを蓄積した後、前記第１のプロセスにより前記ルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを前記蓄積したポインターに従って前記アクションテーブルから抽出する工程と、を含む
    　ことを特徴とするパケット処理方法。
  9. 　前記第１のプロセスは、前記ルールテーブルに含まれるルールを更新する際、該更新を識別する識別子を前記記憶部に記録し、
    　前記第２のプロセスは、前記ポインターを蓄積する際、前記記憶部に記録された識別子を保持する
    　請求項８に記載のパケット処理方法。
  10. 　パケットの処理内容を規定するアクションを含むアクションテーブルと、パケットに適用するアクションを検索するためのルールを含むルールテーブルを記憶部に保持する処理と、
    　第１のプロセスが、前記ルールテーブルに含まれるルールを更新する処理と、
    　第２のプロセスが、受信したパケットに適用するアクションを、前記ルールテーブルを用いて前記アクションテーブルから検索し、検索したアクションに従って該パケットを処理するとともに、検索したアクションに対するポインターを蓄積する処理と、
    　前記第２のプロセスが、前記ポインターを蓄積した後、前記第１のプロセスにより前記ルールテーブルが更新されたか否かを判定し、更新されていない場合、受信したパケットに適用するアクションを前記蓄積したポインターに従って前記アクションテーブルから抽出する処理と、をコンピュータに実行させる
    　ことを特徴とするプログラム。
PCT/JP2015/056143 2014-03-04 2015-03-03 パケット処理装置、パケット処理方法およびプログラム Ceased WO2015133448A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
EP15757950.9A EP3116178B1 (en) 2014-03-04 2015-03-03 Packet processing device, packet processing method, and program
US15/122,133 US10284478B2 (en) 2014-03-04 2015-03-03 Packet processing device, packet processing method and program
JP2016506487A JP6217839B2 (ja) 2014-03-04 2015-03-03 パケット処理装置、パケット処理方法およびプログラム

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2014-041624 2014-03-04
JP2014041624 2014-03-04

Publications (1)

Publication Number Publication Date
WO2015133448A1 true WO2015133448A1 (ja) 2015-09-11

Family

ID=54055254

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2015/056143 Ceased WO2015133448A1 (ja) 2014-03-04 2015-03-03 パケット処理装置、パケット処理方法およびプログラム

Country Status (4)

Country Link
US (1) US10284478B2 (ja)
EP (1) EP3116178B1 (ja)
JP (1) JP6217839B2 (ja)
WO (1) WO2015133448A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP7010922B2 (ja) 2016-07-04 2022-01-26 新華三技術有限公司 フォワーディングエントリアクセス

Families Citing this family (44)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9225638B2 (en) 2013-05-09 2015-12-29 Vmware, Inc. Method and system for service switching using service tags
KR20160124161A (ko) * 2014-02-19 2016-10-26 닛본 덴끼 가부시끼가이샤 네트워크 제어 방법, 네트워크 시스템, 장치, 및 프로그램
US9825913B2 (en) 2014-06-04 2017-11-21 Nicira, Inc. Use of stateless marking to speed up stateful firewall rule processing
US9692698B2 (en) 2014-06-30 2017-06-27 Nicira, Inc. Methods and systems to offload overlay network packet encapsulation to hardware
US10225137B2 (en) 2014-09-30 2019-03-05 Nicira, Inc. Service node selection by an inline service switch
US10320679B2 (en) 2014-09-30 2019-06-11 Nicira, Inc. Inline load balancing
US9825810B2 (en) 2014-09-30 2017-11-21 Nicira, Inc. Method and apparatus for distributing load among a plurality of service nodes
US10609091B2 (en) 2015-04-03 2020-03-31 Nicira, Inc. Method, apparatus, and system for implementing a content switch
JP6540296B2 (ja) * 2015-07-09 2019-07-10 富士通株式会社 ネットワークプロセッサ、通信装置、パケット転送方法及びパケット転送プログラム
US11038845B2 (en) 2016-02-23 2021-06-15 Nicira, Inc. Firewall in a virtualized computing environment using physical network interface controller (PNIC) level firewall rules
EP3501146A1 (en) * 2016-08-26 2019-06-26 Huawei Technologies Co., Ltd. A data packet forwarding unit in a data transmission network
US11546266B2 (en) * 2016-12-15 2023-01-03 Arbor Networks, Inc. Correlating discarded network traffic with network policy events through augmented flow
US10805181B2 (en) 2017-10-29 2020-10-13 Nicira, Inc. Service operation chaining
US10708229B2 (en) * 2017-11-15 2020-07-07 Nicira, Inc. Packet induced revalidation of connection tracker
US11012420B2 (en) 2017-11-15 2021-05-18 Nicira, Inc. Third-party service chaining using packet encapsulation in a flow-based forwarding element
US10757077B2 (en) 2017-11-15 2020-08-25 Nicira, Inc. Stateful connection policy filtering
US10797910B2 (en) 2018-01-26 2020-10-06 Nicira, Inc. Specifying and utilizing paths through a network
US10541918B2 (en) 2018-02-22 2020-01-21 Juniper Networks, Inc. Detecting stale memory addresses for a network device flow cache
US10805192B2 (en) 2018-03-27 2020-10-13 Nicira, Inc. Detecting failure of layer 2 service using broadcast messages
US11595250B2 (en) 2018-09-02 2023-02-28 Vmware, Inc. Service insertion at logical network gateway
US11604666B2 (en) 2019-02-22 2023-03-14 Vmware, Inc. Service path generation in load balanced manner
US11169932B2 (en) * 2019-05-17 2021-11-09 Google Llc Flow table aging optimized for dram access
US11140218B2 (en) 2019-10-30 2021-10-05 Vmware, Inc. Distributed service chain across multiple clouds
US11283717B2 (en) 2019-10-30 2022-03-22 Vmware, Inc. Distributed fault tolerant service chain
US11223494B2 (en) 2020-01-13 2022-01-11 Vmware, Inc. Service insertion for multicast traffic at boundary
US11659061B2 (en) 2020-01-20 2023-05-23 Vmware, Inc. Method of adjusting service function chains to improve network performance
US11153406B2 (en) 2020-01-20 2021-10-19 Vmware, Inc. Method of network performance visualization of service function chains
US11528219B2 (en) 2020-04-06 2022-12-13 Vmware, Inc. Using applied-to field to identify connection-tracking records for different interfaces
US11962518B2 (en) 2020-06-02 2024-04-16 VMware LLC Hardware acceleration techniques using flow selection
US11792134B2 (en) 2020-09-28 2023-10-17 Vmware, Inc. Configuring PNIC to perform flow processing offload using virtual port identifiers
US11829793B2 (en) 2020-09-28 2023-11-28 Vmware, Inc. Unified management of virtual machines and bare metal computers
US12021759B2 (en) 2020-09-28 2024-06-25 VMware LLC Packet processing with hardware offload units
US11611625B2 (en) 2020-12-15 2023-03-21 Vmware, Inc. Providing stateful services in a scalable manner for machines executing on host computers
US11734043B2 (en) 2020-12-15 2023-08-22 Vmware, Inc. Providing stateful services in a scalable manner for machines executing on host computers
US11394651B1 (en) * 2021-02-02 2022-07-19 Nokia Solutions And Networks Oy Smart cache control for mission-critical and high priority traffic flows
US11995024B2 (en) 2021-12-22 2024-05-28 VMware LLC State sharing between smart NICs
US12229578B2 (en) 2021-12-22 2025-02-18 VMware LLC Teaming of smart NICs
US11863376B2 (en) 2021-12-22 2024-01-02 Vmware, Inc. Smart NIC leader election
US12373237B2 (en) 2022-05-27 2025-07-29 VMware LLC Logical memory addressing by smart NIC across multiple devices
US11928367B2 (en) 2022-06-21 2024-03-12 VMware LLC Logical memory addressing for network devices
US11928062B2 (en) 2022-06-21 2024-03-12 VMware LLC Accelerating data message classification with smart NICs
US12481444B2 (en) 2022-06-21 2025-11-25 VMware LLC Smart NIC responding to requests from client device
US11899594B2 (en) 2022-06-21 2024-02-13 VMware LLC Maintenance of data message classification cache on smart NIC
EP4614926A1 (en) * 2024-03-07 2025-09-10 TxOne Networks Inc. Network management device and method for updating rules

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH11163940A (ja) * 1997-09-12 1999-06-18 Lucent Technol Inc パケット検証方法
JP2000089957A (ja) * 1998-09-08 2000-03-31 Nippon Steel Corp 知識システム及びこれを用いた推論制御方法、知識ベースの管理装置及び方法、記録媒体、ルールシステム
WO2012105677A1 (ja) * 2011-02-04 2012-08-09 日本電気株式会社 パケット処理装置、パケット処理方法およびプログラム

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6173364B1 (en) 1997-01-15 2001-01-09 At&T Corp. Session cache and rule caching method for a dynamic filter
US7474653B2 (en) * 2003-12-05 2009-01-06 Hewlett-Packard Development Company, L.P. Decision cache using multi-key lookup

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH11163940A (ja) * 1997-09-12 1999-06-18 Lucent Technol Inc パケット検証方法
JP2000089957A (ja) * 1998-09-08 2000-03-31 Nippon Steel Corp 知識システム及びこれを用いた推論制御方法、知識ベースの管理装置及び方法、記録媒体、ルールシステム
WO2012105677A1 (ja) * 2011-02-04 2012-08-09 日本電気株式会社 パケット処理装置、パケット処理方法およびプログラム

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP7010922B2 (ja) 2016-07-04 2022-01-26 新華三技術有限公司 フォワーディングエントリアクセス

Also Published As

Publication number Publication date
EP3116178A1 (en) 2017-01-11
JP6217839B2 (ja) 2017-10-25
JPWO2015133448A1 (ja) 2017-04-06
EP3116178A4 (en) 2017-10-25
US20160373364A1 (en) 2016-12-22
EP3116178B1 (en) 2019-02-06
US10284478B2 (en) 2019-05-07

Similar Documents

Publication Publication Date Title
JP6217839B2 (ja) パケット処理装置、パケット処理方法およびプログラム
US11811660B2 (en) Flow classification apparatus, methods, and systems
US8627448B2 (en) Selective invalidation of packet filtering results
US20190334948A1 (en) Webshell detection method and apparatus
JP6064291B2 (ja) ネットワークデバイスのフロールックアップ管理のための技術
US10666672B2 (en) Collecting domain name system traffic
US20130246651A1 (en) Longest prefix match searches with variable numbers of prefixes
US20140280276A1 (en) Database sharding by shard levels
US9860332B2 (en) Caching architecture for packet-form in-memory object caching
JP2004172917A (ja) パケット検索装置及びそれに用いるパケット処理検索方法並びにそのプログラム
CN104836741B (zh) 在网络报文分流设备中实现分片报文处理的方法及处理板
CN107682266B (zh) 流表项的匹配方法及装置、计算机可读存储介质
US20210306264A1 (en) Method, electronic device, and computer program product for data processing
US11012542B2 (en) Data processing method and apparatus
US11314711B2 (en) Network switch with network analysis data producer-consumer shared memory
US9781038B2 (en) Packet routing and forwarding in information centric networking
Ruia et al. Flowcache: A cache-based approach for improving SDN scalability
JP2009017439A (ja) パケット転送装置およびパケット転送方法。
JP2018101926A (ja) ネットワーク装置および異常検知システム
JP5814830B2 (ja) フロー単位パケット転送のための宛先検索装置および検索方法
JP6266445B2 (ja) パケット中継装置及びパケット中継方法
KR101467942B1 (ko) 고속 어플리케이션 인지 시스템 및 처리 방법
JP4646823B2 (ja) ルータ装置、ルータ装置におけるルート決定方法
CN105447077B (zh) 基于OpenFlow的查询词抽取方法及系统
JP2016006942A (ja) テーブル管理装置，及びテーブル管理方法

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 15757950

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2016506487

Country of ref document: JP

Kind code of ref document: A

WWE Wipo information: entry into national phase

Ref document number: 15122133

Country of ref document: US

REG Reference to national code

Ref country code: BR

Ref legal event code: B01A

Ref document number: 112016019210

Country of ref document: BR

NENP Non-entry into the national phase

Ref country code: DE

REEP Request for entry into the european phase

Ref document number: 2015757950

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 2015757950

Country of ref document: EP

ENP Entry into the national phase

Ref document number: 112016019210

Country of ref document: BR

Kind code of ref document: A2

Effective date: 20160819