[go: up one dir, main page]

WO2014098114A1 - パケット処理装置、フローエントリの配置方法及びプログラム - Google Patents

パケット処理装置、フローエントリの配置方法及びプログラム Download PDF

Info

Publication number
WO2014098114A1
WO2014098114A1 PCT/JP2013/083857 JP2013083857W WO2014098114A1 WO 2014098114 A1 WO2014098114 A1 WO 2014098114A1 JP 2013083857 W JP2013083857 W JP 2013083857W WO 2014098114 A1 WO2014098114 A1 WO 2014098114A1
Authority
WO
WIPO (PCT)
Prior art keywords
entry
priority
flow
flow entry
new flow
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/JP2013/083857
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 CA2895688A priority Critical patent/CA2895688A1/en
Priority to CN201380066973.9A priority patent/CN104871501A/zh
Priority to JP2014553172A priority patent/JP5967222B2/ja
Priority to KR1020157019071A priority patent/KR101746316B1/ko
Priority to US14/651,641 priority patent/US9876716B2/en
Priority to EP13866082.4A priority patent/EP2938029B1/en
Priority to BR112015014211A priority patent/BR112015014211A2/pt
Priority to RU2015129507A priority patent/RU2628477C2/ru
Publication of WO2014098114A1 publication Critical patent/WO2014098114A1/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
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/54—Organization of routing tables
    • 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
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/38—Flow based routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W72/00—Local resource management
    • H04W72/50—Allocation or scheduling criteria for wireless resources
    • H04W72/56—Allocation or scheduling criteria for wireless resources based on priority criteria
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/64—Routing or path finding of packets in data switching networks using an overlay routing layer

Definitions

  • the present invention is based on a Japanese patent application: Japanese Patent Application No. 2012-276734 (filed on December 19, 2012), and the entire description of the application is incorporated and described in this document by reference.
  • the present invention relates to a packet processing apparatus, a flow entry arrangement method, and a program, and more particularly, to a packet processing apparatus, a flow entry arrangement method, and a program that process a packet while holding a plurality of flow entries.
  • Non-patent documents 1 and 2 propose a technique called open flow.
  • 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 specified in Non-Patent Document 2 includes a secure channel for communication with the OpenFlow controller, and operates according to a flow table that is appropriately added or rewritten from the OpenFlow controller. For each flow, a set of match conditions (Match Fields), flow statistical information (Counters), and instructions (Instructions) that define processing contents are defined for each flow (non-patented). (Refer to “5.2 Flow Table” in Document 2).
  • the OpenFlow switch 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. If an entry that matches the received packet is found as a result of the search, the OpenFlow switch updates the flow statistical information (counter) and processes the processing (designated) in the instruction field of the entry for the received packet. Perform packet transmission, flooding, discard, etc. from the port. On the other hand, if no entry matching the received packet is found as a result of the search, the OpenFlow switch sends an entry setting request to the OpenFlow controller via the secure channel, that is, a control for processing the received packet. An information transmission request (Packet-In message) is transmitted. The OpenFlow switch receives a flow entry whose processing content is defined and updates the flow table. As described above, the OpenFlow switch performs packet transfer using the entry stored in the flow table as control information.
  • a matching condition see “5.3 Matching” in Non-Patent Document 2
  • the OpenFlow switch updates the flow statistical information (counter
  • Patent Document 1 discloses an information storage unit that collects information from a network, a priority determination unit that determines the priority of information, and an importance determination that determines the importance of information according to the user's interest.
  • Means interest information management means for managing information indicating the user's interest, priority comparison means for determining output / accumulation of information according to priority, and sorting means for sorting information in descending order of importance
  • a degree of detail determination means for converting the information into a degree of detail according to the degree of importance, a reduction means for generating simplified information, a history management means for organizing the stored information, and accumulation of collected information
  • Information storage means for recording, priority monitoring means for recording the priority of the information being output, and a presentation timing control means for controlling the timing of output of information stored in the terminal and collection of information from the network With the door, the information presentation apparatus that presents the information collected from the network at the right time and amount is disclosed.
  • Patent Document 2 discloses a buffer control shift register (shift register having a priority processing function) for transmitting an ATM cell stored in an ATM switching device while managing the ATM cell using a deadline of the cell. It is disclosed.
  • Non-Patent Documents 1 and 2 there are known ones that store flow entries in order of priority and speed up the search of flow entries.
  • the OpenFlow switch having the above function receives a new flow entry from the OpenFlow controller, it stores it in the flow table as follows.
  • the OpenFlow switch first compares the priority of the existing flow entry with the priority of the new flow entry. As a result of the comparison, the OpenFlow switch detects the flow entry on the high priority side and the flow entry on the low priority side that has the closest priority to the new flow entry. Then, the OpenFlow switch calculates the registration location of these two flow entries, and stores the new flow entry at the intermediate position.
  • the two flow entries of the flow table may be stored in succession, and there may be no free space at the intermediate position.
  • the OpenFlow switch searches for a free area closest to the storage position and performs a process of shifting the storage position of the existing flow entry by a predetermined number of entries.
  • the shift amount at this time is determined in accordance with, for example, the size of the vacant area at the shift destination.
  • the present invention provides a packet processing apparatus and a flow entry arrangement method that can contribute to a reduction in rearrangement cost at the time of registration of a new flow entry in a packet processing apparatus that arranges and holds flow entries represented by the above-described open flow switches in order of priority. And to provide a program.
  • the new flow entry when a new flow entry is received from a flow table capable of storing a flow entry in an area assigned in order of priority groups and a predetermined control device, the new flow entry includes the plurality of flow entries.
  • An entry management unit that determines a storage position in the flow table based on which priority group of the priority groups belongs to and a second level priority that determines a position in the priority group; and the flow
  • a packet processing device including an entry search unit that scans from the top of a table to search for an entry having a matching condition that matches a received packet and determines a process to be applied to the received packet.
  • a flow table capable of storing a flow entry in an area assigned in the order of priority groups, and scanning from the top of the flow table to find an entry having a matching condition that matches a received packet
  • an entry search unit for determining a process to be applied to the received packet, and a method for arranging a new flow entry in a packet processing device, wherein the new flow entry is received when a new flow entry is received from a predetermined control device.
  • a flow table capable of storing a flow entry in an area assigned in order of priority groups, and scanning from the top of the flow table to search for an entry having a matching condition that matches a received packet
  • An entry search unit that determines a process to be applied to the received packet, and a computer installed in the packet processing device receives a new flow entry from a predetermined control device, and is included in the new flow entry
  • Program for executing a process of storing the new flow entry in the region corresponding to the priority of the Le is provided.
  • This program can be recorded on a computer-readable (non-transient) storage medium. That is, the present invention can be embodied as a computer program product.
  • FIG. 5 is a diagram illustrating a correspondence relationship between the entry management table in FIG. 3 and the flow table in FIG. 4. It is a sequence diagram showing operation
  • FIG. 6 is a diagram illustrating changes (no need for shift) of each table when a new flow entry F is newly received in the state illustrated in FIG. 5.
  • FIG. 7 is a sequence diagram illustrating an operation when it is determined that entry shift processing is necessary in step S003 of FIG. 6.
  • FIG. 8 is a diagram illustrating changes (shift required) in each table when a new flow entry G is newly received in the state illustrated in FIG. 7.
  • FIG. 10 is a continuation diagram of FIG. 9.
  • FIG. 11 is a continuation diagram of FIG. 10.
  • the entry management unit (22 in FIG. 1) and the flow table (211 in FIG. 1) are scanned from the top to search for an entry having a matching condition that matches the received packet.
  • This can be realized by a packet processing device including an entry search unit (21 in FIG. 1) that determines a process to be applied to the received packet.
  • the flow table (211 in FIG. 1) can store flow entries in areas assigned in the order of priority groups.
  • the entry management unit (22 in FIG. 1) receives a new flow entry from a predetermined control device (10 in FIG. 1), the new flow entry is assigned to which priority group of the plurality of priority groups. And the storage position in the flow table is determined according to the second level priority for determining the position in the priority group.
  • the flow table (211 in FIG. 1) since areas are assigned in the order of priority groups, if there is an empty area in the priority area to which the new flow entry belongs, the flow table (211) is arranged based on the priority. No replacement is necessary. Even if there is no empty area at the corresponding position of the priority group to which the new flow entry belongs, it is only necessary to search for the nearest empty area and shift (shift) the flow entry. Sorting costs at the time of registration can be reduced.
  • FIG. 1 is a diagram illustrating a configuration of a packet processing device according to a first embodiment of this invention.
  • the control device 10 that transmits a flow entry setting message that instructs the packet processing device 20 to set the flow entry in the flow table 211, and the flow entry received from the control device 10 are referred to.
  • the control device 10 creates a flow entry to be set in the packet processing device 20 according to a flow entry setting request from the packet processing device 20 or a predetermined communication policy, and transmits a flow entry setting message to the packet processing device 20. .
  • As the flow entry it is possible to use a match condition (Match Fields) to be matched with the packet header and an instruction (Instructions) defining the processing content.
  • the open flow controller of a nonpatent literature 1 and 2 can be used.
  • the packet processing device 20 includes an entry search unit 21 that searches the flow table 211 for a flow entry having a matching condition that matches the received packet, and an entry management unit 22 that manages the arrangement of flow entries in the flow table 211. Yes.
  • a control apparatus 10 in addition to a physical switch having the same function as the open switch of Non-Patent Documents 1 and 2, a virtual switch that operates on a virtualization server, or a host application that operates on a user terminal And a software switch for processing packets from
  • FIG. 2 is a diagram showing a detailed configuration of the packet processing apparatus.
  • the flow table 211 can store N flow entries in descending order of priority.
  • the entry search unit 21 receives a packet from another packet processing device, terminal, server, or the like, the header etc. of the received packet and the match condition of the flow entry are sequentially entered from the entry 1 having the highest priority in the flow table 211. Will be matched.
  • the entry search unit 21 processes the processing contents (instruction of the received packet) described in the instruction (Instructions) of the flow entry that matches the matching condition. Transfer, header rewriting, etc.).
  • the entry search unit 21 omits collation with the flow entry after the entry X (" Search omitted ").
  • FIG. 3 is a diagram illustrating an example of the flow table 211.
  • a plurality of areas are assigned in the order of priority groups, and flow entries can be stored in the order of priority groups.
  • the number of flow entry storage areas allocated to each priority group in the flow table 211 may be determined in advance, or may be dynamically changed during operation. As a result, the number of empty entries in each priority group in the flow table 211 can be easily grasped.
  • the entry management unit 22 performs operations such as a write request to the flow table 211 based on the entry management table 222 for managing the contents and position of the flow entry set in the flow table 211 and the entry management table 222. And an entry setting unit 221.
  • FIG. 4 is a diagram illustrating an example of the entry management table 222.
  • an entry in which a priority group, an intra-group priority (second level priority), a flow entry content, and an entry number are associated with each other. It is shown.
  • the entry 1 has contents that associate the storage position (priority) of the entry (N-1) in the flow table 211 in FIG. 3 with the contents of the flow entry.
  • FIG. 5 is a diagram showing a correspondence relationship between the flow table 211 of FIG. 3 and the entry management table 222 of FIG.
  • the entry setting unit 221 Upon receiving the new flow entry setting message from the control device 10, the entry setting unit 221 obtains the priority group and the intra-group priority from the content, registers them in the entry management table 222, and stores the priority groups and groups in the flow table 211. A flow entry is registered at a position specified by the internal priority.
  • the entry setting unit 221 receives the flow entry deletion instruction message from the control device 10
  • the entry setting unit 221 refers to the entry management table 222, deletes the corresponding flow entry in the flow table 211, and then deletes the entry in the entry management table 222. Delete the entry corresponding to the flow entry.
  • the entry setting unit 221 searches for the nearest free area and shifts the flow entry to secure an area for storing the new flow entry. For example, when the flow entry to be stored between the entry 1 and the entry 2 in FIG. 3 is received from the control device 10, the entry setting unit 221 shifts the entry 2 down by one stage, and the entry 2 has been stored so far. Store the new flow entry in the new location.
  • the entry search unit 22 of the packet processing device 20 shown in FIGS. 1 and 2 uses the hardware of the computer that constitutes the packet processing device 20 in the flow table 211 linked with the entry management table 222 described above. It can also be realized by a computer program that executes an operation process.
  • FIG. 6 is a sequence diagram showing the operation of the first exemplary embodiment of the present invention.
  • the control device 10 creates a flow entry to be set in the packet processing device 20 according to a flow entry setting request or a predetermined communication policy from the packet processing device 20, and transmits a flow entry setting message to the packet processing device 20. (Step S001).
  • the packet processing device 20 specifies the priority group to which the new flow entry belongs and the priority within the group (second level priority) (step S002).
  • the priority group and the priority within the group There are various methods for specifying the priority group and the priority within the group. For example, the higher-order bits of the priority information specified in the new flow entry setting message from the control device 10 are assigned to the priority group. It can be used for identification, and the lower bits can be used for identification of priority within the group.
  • the packet processing device 20 determines whether or not there is a vacancy in the position of the flow table 211 corresponding to the specified priority group and the priority in the group, that is, whether or not a shift operation of an existing entry is necessary. Confirmation is made (step S003).
  • FIG. 7 is a diagram showing changes in each table when a new flow entry F having a new group priority “4” and an intra-group priority “2” is received in the state shown in FIG.
  • the packet processing device 20 checks whether or not there is an empty area at a position corresponding to the group priority “4” and the intra-group priority “2” in the flow table 211. At the time of FIG. 5, the position corresponding to the group priority “4” and the intra-group priority “2” in the flow table 211 is vacant. The flow entry F is registered in the) th area. Further, the packet processing device 20 registers (X ⁇ 1) as the entry number of the flow entry F in the entry management table 222.
  • FIG. 8 shows that as a result of the confirmation in step S003 of FIG. 6, there is no space in the position of the flow table 211 corresponding to the specified priority group and the priority in the group, that is, a shift operation of the existing entry is necessary.
  • the packet processing device 20 searches for a free area of the same priority group closest to the corresponding position in the flow table 211 (step S101). If no free area of the same priority group is found as a result of the search, the packet processing device 20 discards the flow entry setting message and returns an error to the control device 10 (step S103). In response to the error response, the control device 10 considers deleting unnecessary flow entries from the flow table 211.
  • the packet processing device 20 starts the direction of the free area from the specified priority group and the position corresponding to the priority in the group.
  • a free area is created by shifting the flow entries belonging to the same priority group (step S104). Thereafter, the packet processing device 20 returns to step S004 and subsequent steps in FIG. 6 to register a new flow entry in the flow table 211 and update the entry management table 222.
  • FIG. 9 is a diagram showing changes in each table when a new flow entry G having a new group priority “2” and an intra-group priority “4” is received in the state shown in FIG.
  • the packet processing device 20 checks whether or not there is an empty area at a position corresponding to the group priority “2” and the intra-group priority “4” in the flow table 211.
  • entry 1 (in-group priority “2”) and entry 2 (in-group priority “6”) belonging to group priority “2” are stored in succession, and the in-group priority
  • the positions corresponding to the group priority “2” and the intra-group priority “4” in the “4” flow table 211 are not vacant.
  • the packet processing device 20 detects that there is an empty area after the entry 2 of the flow table 211, and executes a shift process for shifting the storage position of the entry 2 downward by one. At the same time, the packet processing device 20 corrects the entry number of the entry that was the conventional entry number 2 in the entry management table 222 to “3”. Note that the shift operation here may be shifted by the amount of the new flow entry, that is, by one, or may be shifted so as to leave a plurality of areas in anticipation of future use.
  • the packet processing apparatus 20 registers a new flow entry G (new entry 2) as entry number 2 in the flow table 211 as shown in FIG. Further, the packet processing device 20 records “2” in the entry number column of the new flow entry G of the entry management table 222.
  • the low-order bit of the priority information specified in the new flow entry setting message from the control device 10 has been described as being used as the priority in the group.
  • the arrival order of the setting messages can also be used as the intra-group priority (second level priority). By doing so, it is possible to further suppress the frequency of occurrence of the flow entry shift processing.
  • the packet processing device 20 discards the flow entry setting message and returns an error to the control device 10.
  • transformation implementation can also be performed.
  • the flow entry selected on the basis of a predetermined criterion is deleted and reported to the control device 10.
  • the predetermined criteria the flow entry to be deleted can be selected based on criteria such as those having a low priority group and intra-group priority, or least recently used (Least Recently Used).
  • some areas of the flow entry 211 may be secured as shared areas that do not belong to any priority group in the initial state. In this way, the area of the flow table 211 can be used more efficiently.
  • the entry management unit is a packet processing device that manages a flow entry set in the flow table by using an entry management table having a management entry corresponding one-to-one with the flow table entry.
  • a packet processing device that uses the order in which new flow entries are received from the predetermined control device as the second level of priority.
  • the entry management unit receives a new flow entry, and there is no free area of the priority group to which the new flow entry belongs in the flow table, the priority is lower than the priority group to which the new flow entry belongs.
  • control device 10 control device 20 packet processing device 21 entry search unit 22 Entry Management Unit 211 Flow Table 221 Entry Setting Unit 222 Entry Management Table

Landscapes

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

Abstract

　フローエントリを優先度順に並べて保持するパケット処理装置における新規フローエントリの登録時の並び替えコストを低減する。パケット処理装置は、優先度グループの順に割り当てられた領域にフローエントリを格納可能なフローテーブルと、所定の制御装置から新規フローエントリを受信した場合、前記新規フローエントリが、前記複数の優先度グループのうちのどの優先度グループに属するかと、前記優先度グループ内の位置を決定する第２レベルの優先度により前記フローテーブルへの格納位置を決定するエントリ管理部と、前記フローテーブルの先頭から走査して、受信パケットに適合するマッチ条件を持つエントリを検索して、前記受信パケットに適用する処理を決定するエントリ検索部と、を備える。

Description

パケット処理装置、フローエントリの配置方法及びプログラム
　［関連出願についての記載］
　本発明は、日本国特許出願：特願２０１２－２７６７３４号（２０１２年１２月１９日出願）に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
　本発明は、パケット処理装置、フローエントリの配置方法及びプログラムに関し、特に、複数のフローエントリを保持してパケットを処理するパケット処理装置、フローエントリの配置方法及びプログラムに関する。
　非特許文献１、２に、オープンフローという技術が提案されている。オープンフローは、通信をエンドツーエンドのフローとして捉え、フロー単位で経路制御、障害回復、負荷分散、最適化を行うものである。非特許文献２に仕様化されているオープンフロースイッチは、オープンフローコントローラとの通信用のセキュアチャネルを備え、オープンフローコントローラから適宜追加または書き換え指示されるフローテーブルに従って動作する。フローテーブルには、フロー毎に、パケットヘッダと照合するマッチ条件（Ｍａｔｃｈ　Ｆｉｅｌｄｓ）と、フロー統計情報（Ｃｏｕｎｔｅｒｓ）と、処理内容を定義したインストラクション（Ｉｎｓｔｒｕｃｔｉｏｎｓ）と、の組が定義される（非特許文献２の「５．２　Ｆｌｏｗ　Ｔａｂｌｅ」の項参照）。
　例えば、オープンフロースイッチは、パケットを受信すると、フローテーブルから、受信パケットのヘッダ情報に適合するマッチ条件（非特許文献２の「５．３　Ｍａｔｃｈｉｎｇ」参照）を持つエントリを検索する。検索の結果、受信パケットに適合するエントリが見つかった場合、オープンフロースイッチは、フロー統計情報（カウンタ）を更新するとともに、受信パケットに対して、当該エントリのインストラクションフィールドに記述された処理内容（指定ポートからのパケット送信、フラッディング、廃棄等）を実施する。一方、検索の結果、受信パケットに適合するエントリが見つからなかった場合、オープンフロースイッチは、セキュアチャネルを介して、オープンフローコントローラに対してエントリ設定の要求、即ち、受信パケットを処理するための制御情報の送信要求（Ｐａｃｋｅｔ－Ｉｎメッセージ）を送信する。オープンフロースイッチは、処理内容が定められたフローエントリを受け取ってフローテーブルを更新する。このように、オープンフロースイッチは、フローテーブルに格納されたエントリを制御情報として用いてパケット転送を行う。
　また、特許文献１には、ネットワークから情報を収集する情報蓄積手段と、情報の優先度を判定する優先度判定手段と、情報に対してユーザの興味に応じた重要度を判定する重要度判定手段と、ユーザの興味を示す情報を管理する興味情報管理手段と、優先度に応じて情報の出力・蓄積を判定する優先度比較手段と、情報を重要度の高い順に並び替える並び替え手段と、前記情報を重要度に応じた詳細度に変換する詳細度決定手段と、簡約化した情報を生成する簡約手段と、蓄積された情報の整理を行う履歴管理手段と、収集された情報の蓄積をする情報蓄積手段と、出力している情報の優先度を記録する優先度監視手段と、端末に蓄積された情報の出力およびネットワークからの情報の収集のタイミングを制御する提示タイミング制御手段とを備え、ネットワークから収集した情報を適切なタイミングと分量で提示するという情報提示装置が開示されている。
　また、特許文献２には、ＡＴＭスイッチング装置に記憶されているＡＴＭセルをそのセルが持っているデッドラインによって管理しつつ送信させるためのバッファ制御用シフトレジスタ（優先処理機能を有するシフトレジスタ）が開示されている。
特開平９－８１０９９号公報 特開平７－２５４９０６号公報
Ｎｉｃｋ　ＭｃＫｅｏｗｎほか７名、"ＯｐｅｎＦｌｏｗ：　Ｅｎａｂｌｉｎｇ　Ｉｎｎｏｖａｔｉｏｎ　ｉｎ　Ｃａｍｐｕｓ　Ｎｅｔｗｏｒｋｓ"、［ｏｎｌｉｎｅ］、［平成２４（２０１２）年１１月２４日検索］、インターネット〈URL:http://www.openflow.org/documents/openflow-wp-latest.pdf〉 "ＯｐｅｎＦｌｏｗ　Ｓｗｉｔｃｈ　Ｓｐｅｃｉｆｉｃａｔｉｏｎ"　Ｖｅｒｓｉｏｎ　１．３．１　（Ｗｉｒｅ　Ｐｒｏｔｏｃｏｌ　０ｘ０４）、［ｏｎｌｉｎｅ］、［平成２４（２０１２）年１２月１１日検索］、インターネット〈URL: https://www.opennetworking.org/images/stories/downloads/specification/openflow-spec-v1.3.1.pdf〉
　以下の分析は、本発明によって与えられたものである。非特許文献１、２のオープンフロースイッチにおいて、フローエントリを優先度順に並べて保持し、フローエントリの検索を高速化するものが知られている。
　上記機能を持つオープンフロースイッチは、オープンフローコントローラから、新しいフローエントリを受け取ると、次のように、フローテーブルに格納する。オープンフロースイッチは、まず、既存のフローエントリの優先度と、新規フローエントリの優先度とを比較する。前記比較の結果、オープンフロースイッチは、新規フローエントリと優先度が最も近い高優先度側のフローエントリと、低優先度側のフローエントリと、を検出する。そして、オープンフロースイッチは、これら２つのフローエントリの登録場所を算出し、新規フローエントリをその中間位置に格納する。
　このとき、フローテーブルの前記２つのフローエントリが連続して格納されていて、中間位置に空き領域が無い場合がある。この場合、オープンフロースイッチは、前記格納位置に最も近い空き領域を探し、所定エントリ数分既存フローエントリの格納位置をシフトさせる処理を行っている。このときのシフト量は、例えば、シフト先の空き領域のサイズに応じて決定している。
　このため、新規フローエントリの優先度が特定の値に偏った場合、フローテーブル内のフローエントリの並び替えの頻度が多くなるという問題点がある。また、新規フローエントリの優先度によっては、１回のフローエントリ登録に伴うフローエントリのシフトによる並び替えが多量になり、並び替えのための処理時間が大きくなり、新規フローエントリの登録に要する時間が長くなるという問題点もある。
　本発明は、上記したオープンフロースイッチに代表されるフローエントリを優先度順に並べて保持するパケット処理装置における新規フローエントリの登録時の並び替えコストの低減に貢献できるパケット処理装置、フローエントリの配置方法及びプログラムを提供することを目的とする。
　第１の視点によれば、優先度グループの順に割り当てられた領域にフローエントリを格納可能なフローテーブルと、所定の制御装置から新規フローエントリを受信した場合、前記新規フローエントリが、前記複数の優先度グループのうちのどの優先度グループに属するかと、前記優先度グループ内の位置を決定する第２レベルの優先度と、により前記フローテーブルへの格納位置を決定するエントリ管理部と、前記フローテーブルの先頭から走査して、受信パケットに適合するマッチ条件を持つエントリを検索して、前記受信パケットに適用する処理を決定するエントリ検索部と、を備えたパケット処理装置が提供される。
　第２の視点によれば、優先度グループの順に割り当てられた領域にフローエントリを格納可能なフローテーブルと、前記フローテーブルの先頭から走査して、受信パケットに適合するマッチ条件を持つエントリを検索して、前記受信パケットに適用する処理を決定するエントリ検索部と、を備えてパケット処理装置における新規フローエントリの配置方法であって、所定の制御装置から新規フローエントリを受信した場合、前記新規フローエントリに含まれる優先度情報に基づいて、前記新規フローエントリが属する優先度グループを判別するステップと、前記新規フローエントリに含まれる優先度情報に基づいて、前記判別した優先度グループ内の位置を決定する第２レベルの優先度を判別するステップと、前記フローテーブルの、前記優先度グループと前記第２レベルの優先度に対応する領域に前記新規フローエントリを格納するステップと、を含むフローエントリの配置方法が提供される。本方法は、フローエントリを優先度順に並べて保持してパケットを処理するパケット処理装置という、特定の機械に結びつけられている。
　第３の視点によれば、優先度グループの順に割り当てられた領域にフローエントリを格納可能なフローテーブルと、前記フローテーブルの先頭から走査して、受信パケットに適合するマッチ条件を持つエントリを検索して、前記受信パケットに適用する処理を決定するエントリ検索部と、を備えてパケット処理装置に搭載されたコンピュータに、所定の制御装置から新規フローエントリを受信した場合、前記新規フローエントリに含まれる優先度情報に基づいて、前記新規フローエントリが属する優先度グループを判別する処理と、前記新規フローエントリに含まれる優先度情報に基づいて、前記判別した優先度グループ内の位置を決定する第２レベルの優先度を判別する処理と、前記フローテーブルの、前記優先度グループと前記第２レベルの優先度に対応する領域に前記新規フローエントリを格納する処理と、を実行させるプログラムが提供される。なお、このプログラムは、コンピュータが読み取り可能な（非トランジエントな）記憶媒体に記録することができる。即ち、本発明は、コンピュータプログラム製品として具現することも可能である。
　本発明によれば、フローエントリを優先度順に並べて保持するパケット処理装置における新規フローエントリの登録時の並び替えコストを低減することが可能となる。
本発明の第１の実施形態のパケット処理装置の構成を示す図である。 本発明の第１の実施形態のパケット処理装置の詳細構成を示す図である。 本発明の第１の実施形態のパケット処理装置のエントリ検索部に保持されるフローテーブルの一例を示す図である。 本発明の第１の実施形態のパケット処理装置のエントリ管理部に保持されるエントリ管理テーブルの一例を示す図である。 図３のエントリ管理テーブルと図４のフローテーブルとの対応関係を示す図である。 本発明の第１の実施形態の動作を表したシーケンス図である。 図５に示す状態において、新たに新規フローエントリＦを受信した場合の各テーブルの変化（シフト不要）を表した図である。 図６のステップＳ００３においてエントリのシフト処理が必要と判断した場合の動作を表したシーケンス図である。 図７に示す状態において、新たに新規フローエントリＧを受信した場合の各テーブルの変化（シフト要）を表した図である。 図９の続図である。 図１０の続図である。
　はじめに本発明の一実施形態の概要について図面を参照して説明する。なお、この概要に付記した図面参照符号は、理解を助けるための一例として各要素に便宜上付記したものであり、本発明を図示の態様に限定することを意図するものではない。
　本発明は、その一実施形態において、エントリ管理部（図１の２２）と、フローテーブル（図１の２１１）を先頭から走査して、受信パケットに適合するマッチ条件を持つエントリを検索し、前記受信パケットに適用する処理を決定するエントリ検索部（図１の２１）と、を備えたパケット処理装置にて実現できる。
　より具体的には、フローテーブル（図１の２１１）は、優先度グループの順に割り当てられた領域にフローエントリを格納可能となっている。そして、エントリ管理部（図１の２２）は、所定の制御装置（図１の１０）から新規フローエントリを受信した場合、新規フローエントリが、前記複数の優先度グループのうちのどの優先度グループに属するかと、前記優先度グループ内の位置を決定する第２レベルの優先度により前記フローテーブルへの格納位置を決定する。
　前述のように、フローテーブル（図１の２１１）は、優先度グループの順に領域が割り当てられているため、新規フローエントリが属する優先度の領域に空き領域が存在すれば、優先度に基づく並び替えは不要となる。また、新規フローエントリが属する優先度グループの該当位置に空き領域が存在しない場合であっても、最寄りの空き領域を探してフローエントリをずらす（シフトさせる）処理を行えばよく、新規フローエントリの登録時の並び替えコストを低減することができる。
［第１の実施形態］
　図１は、本発明の第１の実施形態のパケット処理装置の構成を示す図である。図１を参照すると、パケット処理装置２０に対してフローテーブル２１１へのフローエントリの設定を指示するフローエントリ設定メッセージを送信する制御装置１０と、前記制御装置１０から受信したフローエントリを参照して、他のパケット処理装置、端末、サーバ等から受信したパケットを処理するパケット処理装置２０とを含む構成が示されている。
　制御装置１０は、パケット処理装置２０からフローエントリの設定要求や予め定めた通信ポリシに従って、パケット処理装置２０に設定するフローエントリを作成し、パケット処理装置２０に対してフローエントリ設定メッセージを送信する。なお、フローエントリとしては、パケットヘッダと照合するマッチ条件（Ｍａｔｃｈ　Ｆｉｅｌｄｓ）と、処理内容を定義したインストラクション（Ｉｎｓｔｒｕｃｔｉｏｎｓ）と、を対応付けたものを用いることができる。なお、このような制御装置１０としては、非特許文献１、２のオープンフローコントローラを用いることができる。
　パケット処理装置２０は、フローテーブル２１１から受信パケットに適合するマッチ条件を持つフローエントリを検索するエントリ検索部２１と、フローテーブル２１１におけるフローエントリの配置等を管理するエントリ管理部２２とを備えている。このような制御装置１０としては、非特許文献１、２のオープンスイッチと同等の機能を有する物理スイッチのほか、仮想化サーバ上で動作する仮想スイッチ、あるいは、ユーザ端末上で動作して上位アプリケーションからのパケットを処理するソフトウェアスイッチ等が挙げられる。
　図２は、上記パケット処理装置の詳細構成を示す図である。図２の例では、フローテーブル２１１は、優先度が高い順に、Ｎ個のフローエントリを格納可能となっている。エントリ検索部２１は、他のパケット処理装置、端末、サーバ等からパケットを受信すると、フローテーブル２１１のうち優先度の最も高いエントリ１から順番に、受信パケットのヘッダ等と、フローエントリのマッチ条件とを照合してゆく。前記照合の結果、図２のエントリＸで受信パケットとマッチ条件が一致した場合、エントリ検索部２１は、前記マッチ条件が一致したフローエントリのインストラクション（Ｉｎｓｔｒｕｃｔｉｏｎｓ）に記述された処理内容（受信パケットの転送、ヘッダ書換え等）を実行する。また、前記のように受信パケットに適合するフローエントリが見つかった場合（図２の「条件一致」）、エントリ検索部２１は、エントリＸ以降のフローエントリとの照合を省略する（図２の「検索省略」）。
　図３は、フローテーブル２１１の一例を示す図である。本実施形態のフローテーブル２１１には、優先度グループの順に複数の領域が割り当てられ、優先度グループ順にフローエントリを格納可能となっている。また、同一の優先度グループ内に属するフローエントリ同士のグループ内優先度（第２レベルの優先度）の高低は、個々の優先度グループに割り当てられた領域内での格納位置（本実施形態の場合、優先度が高いほど上位に格納される）にて表される。例えば、図３のエントリ１、エントリ２は、共に既存フローエントリの中では最も優先順位の高い優先度グループ＝２に属しており、エントリ１の方がエントリ２よりもグループ内優先度（第２レベルの優先度）が高いため、エントリ１、エントリ２の順にフローエントリが設定されている。同様に、図３のエントリ（Ｎ－１）、エントリＮは、共に既存フローエントリの中では最も優先順位の低い優先度グループ＝８に属しており、エントリ（Ｎ－１）の方がエントリＮよりもグループ内優先度（第２レベルの優先度）が高いため、エントリ（Ｎ－１）、エントリＮの順にフローエントリが設定されている。なお、図３において「：」が記されている領域は空きエントリであるものとする。
　また、フローテーブル２１１の各優先度グループに割り当てるフローエントリ格納用の領域の数は、事前に決めていてもよいし、運用中に動的に変更してもよい。これにより、フローテーブル２１１の各優先度グループの空きエントリの数が容易に把握できるようになる。
　エントリ管理部２２は、フローテーブル２１１に設定されているフローエントリの内容や位置を管理するエントリ管理テーブル２２２と、前記エントリ管理テーブル２２２に基づいて、フローテーブル２１１への書込み要求等の操作を行うエントリ設定部２２１とを備えている。
　図４は、エントリ管理テーブル２２２の一例を示す図である。図４を参照すると、フローテーブル２１１に格納された個々のフローエントリについて、優先度グループ、グループ内優先度（第２レベルの優先度）、フローエントリの内容と、エントリ番号とを対応付けたエントリが示されている。例えば、エントリ管理テーブル２２２のＮｏ．１のエントリは、図３のフローテーブル２１１のエントリ（Ｎ－１）の格納位置（優先度）とフローエントリの内容とを対応付けた内容となっている。
　図５は、図３のフローテーブル２１１と図４のエントリ管理テーブル２２２との対応関係を示す図である。エントリ設定部２２１は、制御装置１０から新規フローエントリ設定メッセージを受信すると、その内容から優先度グループ及びグループ内優先度を求め、エントリ管理テーブル２２２に登録し、フローテーブル２１１の優先度グループ及びグループ内優先度によって特定される位置に、フローエントリを登録する。また、エントリ設定部２２１は、制御装置１０からフローエントリ削除指示メッセージを受信すると、エントリ管理テーブル２２２を参照して、フローテーブル２１１の該当フローエントリを削除した後、エントリ管理テーブル２２２の前記削除したフローエントリに対応するエントリを削除する。
　なお、新規フローエントリを登録する場合において、例えば図３のエントリ１とエントリ２の間、エントリ（Ｎ－１）とエントリＮとの間のように、フローテーブル２１１において、優先度グループ及びグループ内優先度によって特定される位置に空きが無い場合が起こりうる。この場合、エントリ設定部２２１は、最寄りの空き領域を探してフローエントリをシフトさせて、当該新規フローエントリを格納する領域を確保する。例えば、制御装置１０から、図３のエントリ１とエントリ２の間に格納すべきフローエントリを受け取った場合、エントリ設定部２２１は、エントリ２を一段下にずらし、これまでエントリ２が格納されていた場所に、新規フローエントリを格納する。
　なお、図１、２に示したパケット処理装置２０のエントリ検索部２２は、パケット処理装置２０を構成するコンピュータに、そのハードウェアを用いて、上記したエントリ管理テーブル２２２と連動したフローテーブル２１１の操作処理を実行させるコンピュータプログラムにより実現することもできる。
　続いて、本実施形態の動作について図面を参照して詳細に説明する。図６は、本発明の第１の実施形態の動作を表したシーケンス図である。制御装置１０が、パケット処理装置２０からフローエントリの設定要求や予め定めた通信ポリシに従って、パケット処理装置２０に設定するフローエントリを作成し、パケット処理装置２０に対してフローエントリ設定メッセージを送信する（ステップＳ００１）。
　新規フローエントリ設定メッセージを受信すると、パケット処理装置２０は、新規フローエントリが属する優先度グループと、グループ内の優先度（第２レベルの優先度）を特定する（ステップＳ００２）。優先度グループ及びグループ内の優先度の特定方法としては種々の方法が考えられるが、例えば、制御装置１０からの新規フローエントリ設定メッセージにて指定された優先度情報の上位ビットを優先度グループの特定に用い、下位ビットをグループ内の優先度の特定に用いることができる。
　次に、パケット処理装置２０は、前記特定した優先度グループとグループ内の優先度に対応するフローテーブル２１１の位置に空きがあるか否か、即ち、既存エントリのシフト操作が必要か否かを確認する（ステップＳ００３）。
　前記確認の結果、前記特定した優先度グループとグループ内の優先度に対応するフローテーブル２１１の位置に空きがある、即ち、既存エントリのシフト操作を行わなくとも、新規フローエントリを格納可能である場合（ステップＳ００３のＮｏ）、パケット処理装置２０は、フローテーブル２１１の該当位置に新規フローエントリを登録し（ステップＳ００４、Ｓ００５）、エントリ管理テーブル２２２の該当エントリのエントリ番号欄にフローテーブル２１１上の位置（エントリ番号）を記録する（ステップＳ００６）。
　図７は、図５に示す状態において、新たにグループ優先度“４”、グループ内優先度“２”を持つ新規フローエントリＦを受信した場合の各テーブルの変化を表した図である。パケット処理装置２０は、フローテーブル２１１のグループ優先度“４”、グループ内優先度“２”に対応する位置に空き領域があるか否かを確認する。図５の時点では、フローテーブル２１１のグループ優先度“４”、グループ内優先度“２”に対応する位置は空いているので、パケット処理装置２０は、フローテーブル２１１の上から（Ｘ－１）番目の領域にフローエントリＦを登録する。また、パケット処理装置２０は、エントリ管理テーブル２２２のフローエントリＦのエントリ番号として（Ｘ－１）を登録する。
　図８は、図６のステップＳ００３の確認の結果、特定した優先度グループとグループ内の優先度に対応するフローテーブル２１１の位置に空きがない、即ち、既存エントリのシフト操作が必要であると判定した場合（ステップＳ００３のＹｅｓ）の動作を示すシーケンス図である。この場合、パケット処理装置２０は、フローテーブル２１１の該当位置に最も近い同一優先度グループの空き領域を検索する（ステップＳ１０１）。前記検索の結果、同一優先度グループの空き領域が見つからなかった場合、パケット処理装置２０は、フローエントリ設定メッセージを破棄し、制御装置１０に対し、エラーを返す（ステップＳ１０３）。制御装置１０は、前記エラー応答を受けて、フローテーブル２１１からの不要なフローエントリの削除等を検討することになる。
　一方、前記検索の結果、同一優先度グループの空き領域が見つかった場合、パケット処理装置２０は、前記特定した優先度グループとグループ内の優先度に対応する位置を起点として、前記空き領域の方向に、同一の優先度グループに属するフローエントリをずらして空き領域を作成する（ステップＳ１０４）。その後、パケット処理装置２０は、図６のステップＳ００４以下に戻って、フローテーブル２１１への新規フローエントリの登録、エントリ管理テーブル２２２の更新を実行する。
　図９は、図７に示す状態において、新たにグループ優先度“２”、グループ内優先度“４”を持つ新規フローエントリＧを受信した場合の各テーブルの変化を表した図である。パケット処理装置２０は、フローテーブル２１１のグループ優先度“２”、グループ内優先度“４”に対応する位置に空き領域があるか否かを確認する。図７の時点では、グループ優先度“２”に属するエントリ１（グループ内優先度“２”）、 エントリ２（グループ内優先度“６”）が連続して格納されており、グループ内優先度“４”フローテーブル２１１のグループ優先度“２”、グループ内優先度“４”に対応する位置は空いていない。
　そこで、パケット処理装置２０は、図１０に示すように、フローテーブル２１１のエントリ２の後に空き領域があることを検出し、エントリ２の格納位置を一つ下にずらすシフト処理を実行する。また、これに併せて、パケット処理装置２０は、エントリ管理テーブル２２２の従来エントリ番号２であったエントリのエントリ番号を「３」に修正する。なお、ここでのシフト操作としては、新規フローエントリの分だけ、即ち１つだけシフトさせてもよいし、将来の利用を見越して複数の領域を空けるようシフトさせてもよい。
　前記シフト処理によって空き領域が確保できると、パケット処理装置２０は、図１１に示すように、フローテーブル２１１のエントリ番号２として、新規フローエントリＧ（新エントリ２）を登録する。また、パケット処理装置２０は、エントリ管理テーブル２２２の新規フローエントリＧのエントリ番号欄に「２」に記録する。
　以上の説明から明らかなように、本実施形態によれば、優先度順にフローエントリを並べることによるマッチング処理の高速性と、新規フローエントリの登録時の並び替えコストの低減とを両立することができる。
　以上、本発明の各実施形態を説明したが、本発明は、上記した実施形態に限定されるものではなく、本発明の基本的技術的思想を逸脱しない範囲で、更なる変形・置換・調整を加えることができる。例えば、各図面に示したネットワーク構成や要素の構成は、本発明の理解を助けるための一例であり、これらの図面に示した構成に限定されるものではない。
　例えば、上記した実施形態では、制御装置１０からの新規フローエントリ設定メッセージにて指定された優先度情報の下位ビットをグループ内の優先度として用いるものとして説明したが、制御装置１０からのフローエントリ設定メッセージの到着順序をグループ内優先度（第２レベルの優先度）として用いることもできる。このようにすることで、フローエントリのシフト処理の発生頻度をより抑えることが可能になる。
　また、上記した実施形態では、新規フローエントリを格納する同一優先度グループの空き領域が見つからなかった場合、パケット処理装置２０は、フローエントリ設定メッセージを破棄し、制御装置１０に対し、エラーを返すものとして説明したが、以下のような変形実施を行うこともできる。
（１）フローテーブル２１１の他の優先度グループに空きが有る場合は、当該空き領域に新規フローエントリを登録する。併せてフローテーブル２１１の該当優先度グループに割り当てられた領域に、前記新規フローエントリを登録した領域を追加する（空き領域のあった他の優先度グループに割り当てられた領域から、前記前記新規フローエントリを登録した領域を削除する）。また、この場合において、空き領域のある優先度グループが複数ある場合、最も優先度の低い優先度グループや最も優先度の近い優先度グループを選択することができる。なお、この場合において、特定の優先度グループへの領域の割り当てが集中しないよう、該当優先度グループのフローエントリを削除したタイミングで、空き領域の割り当てを元の優先度グループに戻してもよい。
（２）フローテーブル２１１のすべての優先度グループに空きがない場合は、所定の基準で選択したフローエントリを削除し、制御装置１０に対して報告する。なお、前記所定の基準としては、優先度グループ及びグループ内優先度が低いもの、最も最近使われなかったもの（Ｌｅａｓｔ　Ｒｅｃｅｎｔｌｙ　Ｕｓｅｄ）等の基準により削除対象のフローエントリを選択することができる。
（３）また、フローエントリ２１１のいくつかの領域を、初期状態においていずれの優先度グループにも属さない共用領域として確保しておいてもよい。このようにすれば、フローテーブル２１１の領域をより効率よく利用できる。
　最後に、本発明の好ましい形態を要約する。
［第１の形態］
　（上記第１の視点によるパケット処理装置参照）
［第２の形態］
　第１の形態のパケット処理装置において、
　前記第２レベルの優先度によって決定される位置に空きが無い場合、前記エントリ管理部は、前記第２レベルの優先度によって決定される位置を起点として、同一優先度のグループの最寄の空き領域の方向に、前記新規フローエントリと同一の優先度グループに属するフローエントリをずらして前記新規フローエントリを格納するパケット処理装置。
［第３の形態］
　第１又は第２の形態のパケット処理装置において、
　前記エントリ管理部は、前記フローテーブルのエントリと１対１に対応する管理用エントリを持つエントリ管理テーブルを用いて、前記フローテーブルに設定したフローエントリを管理するパケット処理装置。
［第４の形態］
　第１の形態のパケット処理装置において、
　前記第２のレベルの優先度として、前記所定の制御装置から新規フローエントリを受信した順序を用いるパケット処理装置。
［第５の形態］
　第１から第４いずれか一の形態のパケット処理装置において、
　前記エントリ管理部は、新規フローエントリを受信した際に、前記フローテーブルに、前記新規フローエントリが属する優先度グループの空き領域が無い場合、前記新規フローエントリが属する優先度グループよりも下位の優先度グループの空き領域に前記新規フローエントリを格納するパケット処理装置。
［第６の形態］
　第５の形態のパケット処理装置において、
　前記第２のレベルの優先度に対応する前記新規フローエントリが属する優先度グループのグループ内の位置の空き領域が無い場合、前記新規フローエントリを格納する優先度グループとして、空き領域を有する優先度グループのうち優先度が最も下位の優先度グループの空き領域に前記新規フローエントリを格納するパケット処理装置。
［第７の形態］
　（上記第２の視点によるフローエントリの配置方法参照）
［第８の形態］
　（上記第３の視点によるプログラム参照）
　なお、上記第７、第８の形態は、第１の形態と同様に、第２～第６の形態に展開することが可能である。
　なお、上記の特許文献および非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施形態ないし実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
　１０　制御装置
　２０　パケット処理装置
　２１　エントリ検索部　
　２２　エントリ管理部
　２１１　フローテーブル
　２２１　エントリ設定部
　２２２　エントリ管理テーブル

Claims (8)

  1. 　優先度グループの順に割り当てられた領域にフローエントリを格納可能なフローテーブルと、
    　所定の制御装置から新規フローエントリを受信した場合、前記新規フローエントリが、前記複数の優先度グループのうちのどの優先度グループに属するかと、前記優先度グループ内の位置を決定する第２レベルの優先度と、により前記フローテーブルへの格納位置を決定するエントリ管理部と、
    　前記フローテーブルの先頭から走査して、受信パケットに適合するマッチ条件を持つエントリを検索して、前記受信パケットに適用する処理を決定するエントリ検索部と、
    　を備えたパケット処理装置。
  2. 　前記第２レベルの優先度によって決定される位置に空きが無い場合、前記エントリ管理部は、前記第２レベルの優先度によって決定される位置を起点として、同一優先度のグループの最寄の空き領域の方向に、前記新規フローエントリと同一の優先度グループに属するフローエントリをずらして前記新規フローエントリを格納する請求項１のパケット処理装置。
  3. 　前記エントリ管理部は、前記フローテーブルのエントリと１対１に対応する管理用エントリを持つエントリ管理テーブルを用いて、前記フローテーブルに設定したフローエントリを管理する請求項１又は２のパケット処理装置。
  4. 　前記第２のレベルの優先度として、前記所定の制御装置から新規フローエントリを受信した順序を用いる請求項１のパケット処理装置。
  5. 　前記エントリ管理部は、新規フローエントリを受信した際に、前記フローテーブルに、前記新規フローエントリが属する優先度グループの空き領域が無い場合、前記新規フローエントリが属する優先度グループよりも下位の優先度グループの空き領域に前記新規フローエントリを格納する請求項１から４いずれか一のパケット処理装置。
  6. 　前記第２のレベルの優先度に対応する前記新規フローエントリが属する優先度グループのグループ内の位置の空き領域が無い場合、前記新規フローエントリを格納する優先度グループとして、空き領域を有する優先度グループのうち優先度が最も下位の優先度グループの空き領域に前記新規フローエントリを格納する請求項５のパケット処理装置。
  7. 　優先度グループの順に割り当てられた領域にフローエントリを格納可能なフローテーブルと、前記フローテーブルの先頭から走査して、受信パケットに適合するマッチ条件を持つエントリを検索して、前記受信パケットに適用する処理を決定するエントリ検索部と、を備えてパケット処理装置における新規フローエントリの配置方法であって、
    　所定の制御装置から新規フローエントリを受信した場合、前記新規フローエントリに含まれる優先度情報に基づいて、前記新規フローエントリが属する優先度グループを判別するステップと、
    　前記新規フローエントリに含まれる優先度情報に基づいて、前記判別した優先度グループ内の位置を決定する第２レベルの優先度を判別するステップと、
    　前記フローテーブルの、前記優先度グループと前記第２レベルの優先度に対応する領域に前記新規フローエントリを格納するステップと、を含むフローエントリの配置方法。
  8. 　優先度グループの順に割り当てられた領域にフローエントリを格納可能なフローテーブルと、前記フローテーブルの先頭から走査して、受信パケットに適合するマッチ条件を持つエントリを検索して、前記受信パケットに適用する処理を決定するエントリ検索部と、を備えてパケット処理装置に搭載されたコンピュータに、
    　所定の制御装置から新規フローエントリを受信した場合、前記新規フローエントリに含まれる優先度情報に基づいて、前記新規フローエントリが属する優先度グループを判別する処理と、
    　前記新規フローエントリに含まれる優先度情報に基づいて、前記判別した優先度グループ内の位置を決定する第２レベルの優先度を判別する処理と、
    　前記フローテーブルの、前記優先度グループと前記第２レベルの優先度に対応する領域に前記新規フローエントリを格納する処理と、を実行させるプログラム。
PCT/JP2013/083857 2012-12-19 2013-12-18 パケット処理装置、フローエントリの配置方法及びプログラム Ceased WO2014098114A1 (ja)

Priority Applications (8)

Application Number Priority Date Filing Date Title
CA2895688A CA2895688A1 (en) 2012-12-19 2013-12-18 Packet processing apparatus, flow entry configuration method and program
CN201380066973.9A CN104871501A (zh) 2012-12-19 2013-12-18 分组处理装置、流表项配置方法和程序
JP2014553172A JP5967222B2 (ja) 2012-12-19 2013-12-18 パケット処理装置、フローエントリの配置方法及びプログラム
KR1020157019071A KR101746316B1 (ko) 2012-12-19 2013-12-18 패킷 처리 장치, 플로 엔트리 배치 방법 및 프로그램
US14/651,641 US9876716B2 (en) 2012-12-19 2013-12-18 Packet processing apparatus, flow entry configuration method and program
EP13866082.4A EP2938029B1 (en) 2012-12-19 2013-12-18 Packet processing device, flow entry arrangement method and program
BR112015014211A BR112015014211A2 (pt) 2012-12-19 2013-12-18 aparelho de processamento de pacotes, método de configuração de entrada de fluxo e programa
RU2015129507A RU2628477C2 (ru) 2012-12-19 2013-12-18 Устройство обработки пакета, способ конфигурирования записи потока и программа

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2012276734 2012-12-19
JP2012-276734 2012-12-19

Publications (1)

Publication Number Publication Date
WO2014098114A1 true WO2014098114A1 (ja) 2014-06-26

Family

ID=50978439

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2013/083857 Ceased WO2014098114A1 (ja) 2012-12-19 2013-12-18 パケット処理装置、フローエントリの配置方法及びプログラム

Country Status (9)

Country Link
US (1) US9876716B2 (ja)
EP (1) EP2938029B1 (ja)
JP (1) JP5967222B2 (ja)
KR (1) KR101746316B1 (ja)
CN (1) CN104871501A (ja)
BR (1) BR112015014211A2 (ja)
CA (1) CA2895688A1 (ja)
RU (1) RU2628477C2 (ja)
WO (1) WO2014098114A1 (ja)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104283805A (zh) * 2014-10-27 2015-01-14 杭州华三通信技术有限公司 一种sdn网络报文发送方法及设备
US11956146B2 (en) 2020-03-10 2024-04-09 Mitsubishi Electric Corporation Controller, network system, and flow management method

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20150090212A (ko) * 2012-11-28 2015-08-05 닛본 덴끼 가부시끼가이샤 스위치 장치, vlan 설정 관리 방법 및 프로그램
US9692684B2 (en) * 2014-09-05 2017-06-27 Telefonaktiebolaget L M Ericsson (Publ) Forwarding table precedence in SDN
US10003529B2 (en) * 2015-08-04 2018-06-19 Telefonaktiebolaget Lm Ericsson (Publ) Method and system for memory allocation in a software-defined networking (SDN) system
EP3369225B1 (en) * 2016-03-31 2020-09-30 NEC Corporation Software-enhanced stateful switching architecture
TWI626837B (zh) * 2016-12-01 2018-06-11 財團法人工業技術研究院 封包傳遞方法、封包傳遞裝置及非暫態電腦可讀取媒體
US11632332B2 (en) * 2018-06-07 2023-04-18 Vmware, Inc. Packet classification with multiple classifiers

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH07254906A (ja) 1994-03-16 1995-10-03 Mitsubishi Electric Corp 優先処理機能を有するシフトレジスタ、それを用いたパケット通信用スイッチング装置及びそれを用いたａｔｍネットワーク並びに優先処理を伴うパケット通信方式及び優先処理を伴うａｔｍ通信方式
JPH0981099A (ja) 1995-09-08 1997-03-28 Nec Corp 情報提示装置
WO2011083786A1 (ja) * 2010-01-06 2011-07-14 日本電気株式会社 通信制御システム、及び通信制御方法
WO2012032864A1 (ja) * 2010-09-08 2012-03-15 日本電気株式会社 スイッチシステム、スイッチ制御方法、及び記憶媒体

Family Cites Families (24)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3449326B2 (ja) * 1999-12-08 2003-09-22 日本電気株式会社 データ検索システム及びパケット処理装置並びに制御方法
US7089240B2 (en) * 2000-04-06 2006-08-08 International Business Machines Corporation Longest prefix match lookup using hash function
JP3591420B2 (ja) * 2000-04-07 2004-11-17 日本電気株式会社 ルータにおけるキャッシュテーブル管理装置およびプログラム記録媒体
JP2002185513A (ja) * 2000-12-18 2002-06-28 Hitachi Ltd パケット通信ネットワークおよびパケット転送制御方法
JP3936883B2 (ja) * 2002-04-08 2007-06-27 株式会社日立製作所 フロー検出装置およびフロー検出機能を備えたパケット転送装置
BR0314694A (pt) * 2002-09-26 2005-08-09 Koninkl Philips Electronics Nv Aparelho e método para transferência contìnua de dados em tempo real a partir de um meio de armazenagem
US20040151197A1 (en) * 2002-10-21 2004-08-05 Hui Ronald Chi-Chun Priority queue architecture for supporting per flow queuing and multiple ports
BRPI0406978A (pt) * 2003-01-24 2006-01-10 Coco Communications Corp Sistema para organizar sem administração central uma rede de dispositivos de computação sem confiança
US7418505B2 (en) * 2003-05-26 2008-08-26 Ewha University Industry Collaboration Foundation IP address lookup using either a hashing table or multiple hash functions
US7787471B2 (en) * 2003-11-10 2010-08-31 Broadcom Corporation Field processor for a network device
JP4336625B2 (ja) * 2004-06-17 2009-09-30 株式会社日立製作所 パケット転送装置
KR100612256B1 (ko) * 2005-01-14 2006-08-14 삼성전자주식회사 터너리 내용 주소화 메모리 관리 장치 및 그 방법
JP4556761B2 (ja) * 2005-05-06 2010-10-06 株式会社日立製作所 パケット転送装置
CA2617168A1 (en) * 2005-08-01 2007-02-08 Volt Information Sciences Inc. Outsourced service level agreement provisioning management system and method
US7606968B2 (en) * 2006-05-08 2009-10-20 Mcdata Corporation Multi-level content addressable memory
JP2009239401A (ja) * 2008-03-26 2009-10-15 Alaxala Networks Corp パケット転送装置
US20100064072A1 (en) * 2008-09-09 2010-03-11 Emulex Design & Manufacturing Corporation Dynamically Adjustable Arbitration Scheme
EP2395712A4 (en) * 2009-02-03 2012-07-04 Nec Corp APPLICATION SWITCHING SYSTEM AND APPLICATION SWITCHING METHOD
JP5640986B2 (ja) 2009-10-07 2014-12-17 日本電気株式会社 通信システムの制御装置、制御方法及びプログラム
US8677030B2 (en) * 2009-12-09 2014-03-18 Oracle America, Inc. Apparatus and method for managing packet classification tables
US20110145255A1 (en) * 2009-12-11 2011-06-16 Sap Ag. Systems and methods for distribution of data in a database index
WO2011102312A1 (ja) * 2010-02-16 2011-08-25 日本電気株式会社 パケット転送装置、通信システム、処理規則の更新方法およびプログラム
CN102263664A (zh) 2011-08-11 2011-11-30 北京星网锐捷网络技术有限公司 一种会话流处理方法及装置
KR101887581B1 (ko) * 2011-12-26 2018-08-14 한국전자통신연구원 플로우 기반의 패킷 전송 장치 및 그것의 패킷 처리 방법

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH07254906A (ja) 1994-03-16 1995-10-03 Mitsubishi Electric Corp 優先処理機能を有するシフトレジスタ、それを用いたパケット通信用スイッチング装置及びそれを用いたａｔｍネットワーク並びに優先処理を伴うパケット通信方式及び優先処理を伴うａｔｍ通信方式
JPH0981099A (ja) 1995-09-08 1997-03-28 Nec Corp 情報提示装置
WO2011083786A1 (ja) * 2010-01-06 2011-07-14 日本電気株式会社 通信制御システム、及び通信制御方法
WO2012032864A1 (ja) * 2010-09-08 2012-03-15 日本電気株式会社 スイッチシステム、スイッチ制御方法、及び記憶媒体

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
"Openflow Switch Specification", WIRE PROTOCOL OX04, 11 December 2012 (2012-12-11)
NICK MCKEOWN, OPENFLOW: ENABLING INNOVATION IN CAMPUS NETWORKS, 24 November 2012 (2012-11-24), Retrieved from the Internet <URL:http://www.openflow.org/documents/openflow-wp-latest.pdf>
See also references of EP2938029A4

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN104283805A (zh) * 2014-10-27 2015-01-14 杭州华三通信技术有限公司 一种sdn网络报文发送方法及设备
CN104283805B (zh) * 2014-10-27 2017-11-10 新华三技术有限公司 一种sdn网络报文发送方法及设备
US11956146B2 (en) 2020-03-10 2024-04-09 Mitsubishi Electric Corporation Controller, network system, and flow management method

Also Published As

Publication number Publication date
BR112015014211A2 (pt) 2017-07-11
JPWO2014098114A1 (ja) 2017-01-12
KR101746316B1 (ko) 2017-06-12
US9876716B2 (en) 2018-01-23
US20150326477A1 (en) 2015-11-12
CN104871501A (zh) 2015-08-26
JP5967222B2 (ja) 2016-08-10
RU2628477C2 (ru) 2017-08-17
EP2938029A4 (en) 2016-08-10
EP2938029A1 (en) 2015-10-28
KR20150097663A (ko) 2015-08-26
EP2938029B1 (en) 2019-03-27
RU2015129507A (ru) 2017-01-26
CA2895688A1 (en) 2014-06-26

Similar Documents

Publication Publication Date Title
JP5967222B2 (ja) パケット処理装置、フローエントリの配置方法及びプログラム
CN102783097B (zh) 分组转发系统、控制设备、转发设备以及用于准备处理规则的方法
JP5800019B2 (ja) 通信経路制御システム、経路制御装置、通信経路制御方法および経路制御プログラム
US10523576B1 (en) High-performance garbage collection in a network device
CN104704779A (zh) 用于加速软件定义网络中的转发的方法和设备
WO2012090993A1 (ja) 情報システム、制御装置、通信方法およびプログラム
KR101577926B1 (ko) 통신 노드, 패킷 처리 방법 및 프로그램
CN103828313A (zh) 网络系统、前端单元和控制消息传输速率降低方法
JP5747997B2 (ja) 制御装置、通信システム、仮想ネットワークの管理方法およびプログラム
KR101812856B1 (ko) 스위치 장치, vlan 설정 관리 방법, 및 컴퓨터 판독가능 저장매체
US20150281091A1 (en) Control apparatus, node, communication system, communication method, and program
WO2014157460A1 (ja) 通信システム、制御装置、情報収集方法およびプログラム
WO2014010723A1 (ja) スイッチ、通信システム、スイッチ制御方法及びプログラム
CN113615249A (zh) 基于时延的对漫游事件的动态优先级排序
US9860178B2 (en) Control message relay apparatus, control message relay method, and program
JP4769316B2 (ja) パケットキューイング装置およびパケットキューイング方法
RU2675148C1 (ru) Способ организации автоматической балансировки потоков многопоточного соединения на коммутационных устройствах с использованием их самообучения
CN109842557B (zh) 管理流规则表的方法和交换器
CN120111014A (zh) 数据处理方法及装置、非易失性存储介质、电子设备
JP2008085886A (ja) パケット処理装置、パケット処理方法及びパケット処理プログラム
WO2014038143A1 (en) Flow information collecting system, method and program
HK1175622A (en) Packet transfer system, control apparatus, transfer apparatus, method of creating processing rules, and program
WO2019050423A1 (ru) Способ организации автоматической балансировки потоков многопоточного соединения на коммутационных устройствах с использованием их самообучения
WO2014027687A1 (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: 13866082

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 2013866082

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 14651641

Country of ref document: US

ENP Entry into the national phase

Ref document number: 2895688

Country of ref document: CA

ENP Entry into the national phase

Ref document number: 2014553172

Country of ref document: JP

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: DE

REG Reference to national code

Ref country code: BR

Ref legal event code: B01A

Ref document number: 112015014211

Country of ref document: BR

ENP Entry into the national phase

Ref document number: 20157019071

Country of ref document: KR

Kind code of ref document: A

ENP Entry into the national phase

Ref document number: 2015129507

Country of ref document: RU

Kind code of ref document: A

ENP Entry into the national phase

Ref document number: 112015014211

Country of ref document: BR

Kind code of ref document: A2

Effective date: 20150616