Source: https://patents.google.com/patent/JP3936883B2/en
Timestamp: 2019-05-27 01:51:17
Document Index: 17431436

Matched Legal Cases: ['art 1', 'art 1', 'art 1', 'art 2', 'art 2', 'art 3', 'art 2', 'art 3', 'art 2', 'art 1', 'art 2']

JP3936883B2 - Flow detection device and a packet transfer device including a flow detection function - Google Patents
Flow detection device and a packet transfer device including a flow detection function Download PDF
JP3936883B2
JP3936883B2 JP2002105362A JP2002105362A JP3936883B2 JP 3936883 B2 JP3936883 B2 JP 3936883B2 JP 2002105362 A JP2002105362 A JP 2002105362A JP 2002105362 A JP2002105362 A JP 2002105362A JP 3936883 B2 JP3936883 B2 JP 3936883B2
JP2002105362A
JP2003304278A (en
2002-04-08 Application filed by 株式会社日立製作所 filed Critical 株式会社日立製作所
2002-04-08 Priority to JP2002105362A priority Critical patent/JP3936883B2/en
2003-10-24 Publication of JP2003304278A publication Critical patent/JP2003304278A/en
2007-06-27 Publication of JP3936883B2 publication Critical patent/JP3936883B2/en
本発明は、複数のネットワークを接続するパケット転送装置およびフロー検出装置に関し、更に詳しくは、ＣＡＭ（Content Addressable Memory）を利用したフロー検出装置およびパケット転送装置に関する。 The present invention relates to a packet transfer device and a flow detection device for connecting a plurality of networks, and more particularly, to a flow detection device and a packet transfer apparatus utilizing CAM (Content Addressable Memory).
ＩＰ（Internet Protocol）ネットワークを構成するパケット転送装置、例えば、ルータは、受信パケットのヘッダ情報から該パケットの属するフローを検出するフロー検出機能が必要となる。 IP packet forwarding apparatus constituting the (Internet Protocol) network, for example, routers, flow detection function for detecting the flows belonging from the header information of the received packet of the packet is necessary. ここで、フローとは、パケットの入力回線または出力回線の識別子（回線番号）や、受信パケットのヘッダに含まれるＩＰアドレス、プロトコル識別子、優先度等の情報の組み合せによって特定される一連のパケットを意味している。 Here, the flow and the input line or output line identifier (line number) and the packet, IP address, included in a header of a received packet, a protocol identifier, a sequence of packets identified by a combination of the priority information, etc. it means. パケット転送装置は、フロー検出部によって検出されたフロー毎に、例えば、パケット廃棄の要否判定（フィルタリング判定）や、通信品質を確保するためのパケット転送優先度（ＱｏＳ：Quality of Service）の判定等のフロー制御を行う。 Packet transfer device, for each flow detected by the flow detection unit, for example, necessity determination of packet discard (filtering decision) and a packet transfer priority for ensuring the communication quality: determination (QoS Quality of Service) It performs flow control and the like.
近年、ＩＰトラフィックの急増に対応するために、フロー検出の高速化が検討されている。 Recently, in order to correspond to rapid increase in IP traffic, speed of flow detection has been studied. 例えば、２０００年電子情報通信学会総合大会講演論文集、ＳＢ−４−２には、ＣＡＭ（Content Addressable Memory）を利用した「連想メモリを用いたフロー識別法」（従来技術１）が開示されている。 For example, in 2000 Institute of Electronics, Information and Communication Engineers General Conference Papers, the SB-4-2, CAM "flow identification method using an associative memory" using (Content Addressable Memory) is (prior art 1) disclosure there.
ＣＡＭを使用したフロー検出では、図２に示すように、フロー制御部６１で検索キーＫＥＹを生成し、ＣＡＭ６２に与える。 In the flow detection using CAM, as shown in FIG. 2, it generates a search key KEY at the flow controller 61, giving the CAM 62. ＣＡＭ６２には、図３に示すように、フロー識別条件となる項目値を記述した複数のフローエントリ６２０−１〜６２０−ｎが格納してあり、ＣＡＭからは、検索キーＫＥＹと一致したフロー識別条件をもつフローエントリのアドレスが出力される。 The CAM 62, as shown in FIG. 3, Yes and stores a plurality of flow entry 620-1~620-n describing the item value as a flow identification condition, from CAM, matched flow identification and the search key KEY address of the flow entry with the condition is output. フロー制御部６１は、ＣＡＭ６２のフローエントリアドレスと対応して入力パケットに実施すべき転送制御を指示した検索結果保持テーブル６３を備えており、検索結果保持テーブル６３から上記ＣＡＭ出力アドレスと対応した転送制御指示を読み出し、該指示に従って入力パケットを処理する。 Flow control unit 61 is provided with a search result holding table 63 has been specified correspondingly transfer control to be performed on the input packet with the flow entry address of CAM 62, corresponding from the search result holding table 63 and the CAM output address transfer reading a control instruction, to process the input packet in accordance with the instructions. ＣＡＭは、エントリの検索所要時間が登録フローエントリ数に依存しないため、ＣＡＭを利用することによってフロー検出を高速化することができる。 CAM, since the search time required entry does not depend on the number of registered flow entry, it is possible to speed up the flow detection by utilizing the CAM.
従来技術１は、入力パケットのヘッダ情報からフロー識別に必要な全ての項目（フィールド）、例えば、送信元ＩＰアドレス６０１、宛先ＩＰアドレス６０２、プロトコル６０３等を検索キー情報として抽出し、ＣＡＭ６２内に検索キーと一致するフローエントリが複数存在していた場合、アドレスが最も若いエントリを優先させることを提案している。 Prior art 1, all the necessary items from the header information to the flow identification of the incoming packet (field), e.g., the source IP address 601, and extracts a destination IP address 602, a protocol 603 such as search key information, in the CAM62 If the flow entry matching the search key was there exist a plurality, it proposes to give priority to address the youngest entry. また、従来技術１は、１つのＣＡＭ内に、長いビット幅を持つフロー識別用のエントリと、短いビット幅をもつフォワーディング制御用のエントリとを登録しておき、検索キーが示すフロー識別条件に一致するフロー識別エントリと、フロー識別条件の上位特定項目に一致したフォワーディング制御用のエントリとを同時に検索することを提案している。 Further, the prior art 1, in one CAM, and entries for flow identification with a long bit width, have created the entry for forwarding control with a short bit width, the flow identification condition indicated by the retrieval key and flow identification entries matching, proposes to find the entry for forwarding control that matches the upper specific item of flow identification condition simultaneously.
ＩＰネットワークでは、ＩＰｖ６（RFC2460、Internet Protocol Version 6(IPv6) Specification、 R.Hinden他）によるＩＰアドレスの拡張、ＭＰＬＳ−ＶＰＮ（RFC2547、BGP/MPLS VPNs、E.Rosen他）、ＭＰＬＳ Ｆａｓｔ Ｒｅｒｏｕｔｅ（draft-haskin-mpls-fast-reroute-05.txt、”Method for Setting an Alternative Label Switched Paths to Handle Fast Reroute” D.Haskin他）によるＭＰＬＳラベルスタック（RFC3032、”MPLS Label Stack Encoding” E.Rosen他）等の新規技術に対応するために、パケット転送装置のフロー検出部における検索キー（フロー識別条件）のビット長が拡大し、フロー識別条件が多様化する傾向にある。 In the IP network, IPv6 (RFC2460, Internet Protocol Version 6 (IPv6) Specification, R.Hinden other) IP address extension of the due to, MPLS-VPN (RFC2547, BGP / MPLS VPNs, E.Rosen other), MPLS Fast Reroute (draft -haskin-mpls-fast-reroute-05.txt, "Method for Setting an Alternative label Switched Paths to Handle Fast Reroute" MPLS label stack according to D.Haskin other) (RFC3032, "MPLS label stack Encoding" E.Rosen other) to accommodate new technology etc., bit length expanded search key in the flow detector of the packet transfer apparatus (flow identification condition), tends to flow identification conditions are diversified.
フロー識別条件のビット長が増大し、ＣＡＭで提供可能な検索ビット幅を超えた場合の対策として、例えば、２０００年電子情報通信学会通信ソサイエティ大会Ｂ−６−２１では、検索キーを２分割し、前半キーによるフローエントリ検索と後半キーによるフローエントリ検索の２回の検索を実行することによって、フロー検出条件に合致したエントリを見つける「連想メモリを用いたＩＰｖ６のフロー識別法」（従来技術２）が提案されている。 Bit length increases the flow identification condition, as a countermeasure in the case of exceeding the available search bit width provided CAM, for example, in the 2000 IEICE Communication Society Conference B-6-21, the search key bisected , by executing two search flow entry search by flow entry search and late key by the first half keys, flow finds an entry that matches the detection condition "IPv6 flow identification method using a content addressable memory" (prior art 2 ) it has been proposed.
従来技術２では、図４のように、ＣＡＭを前半用フローエントリ領域６２Ａと後半用フローエントリ領域６２Ｂに分け、各フローエントリに、前後半の区分フィールド６２１とルール番号フィールド６２２を与えている。 In the prior art 2, as shown in FIG. 4, divided CAM in the first half for flow entry region 62A and the second half for flow entry area 62B, each flow entry, has given partition field 621 and rule number field 622 of the second halves. また、検索結果保持テーブル６３（６３Ａ、６３Ｂ）で、後半検索の要否６３１、ルール番号６３２、アクション６３３を指定している。 The search result holding table 63 (63A, 63B), a designates the necessity 631, rule number 632, an action 633 of the second half search. 前半キーＫＥＹ−Ａと前半用フローエントリでは、ルール番号フィールド６２２がDon't Care値となっており、前半キーＫＥＹ−ＡによるＣＡＭ検索の結果、検索結果保持テーブル６３Ａからルール番号が特定され、このルール番号を適用した後半キーＫＥＹ−ＢによるＣＡＭ検索によって、入力パケットに対して実行すべきアクションが決まる。 In the first half key KEY-A and the first half for the flow entry, rule number field 622 has become a Do not Care value, the result of CAM search due to the first half of key KEY-A, rule number is identified from the search result holding table 63A, by CAM search by the second half of key kEY-B you apply this rule number, the action is determined to be performed with respect to the input packet.
また、特開２００１−１５６８４０号公報（従来技術３）には、入力パケットのヘッダから、フロー識別条件となり得る特定のフィールド、例えば、ＩＰヘッダに含まれる送信元アドレス、宛先アドレス、プロトコル、ＴＯＳ（Type of Service）と、ＴＣＰまたはＵＤＰヘッダに含まれる発信元ポート、宛先ポートを抽出し、これらのフィールド項目に対して、予め入力論理リンク番号と対応して検索フラグテーブルに登録されたマスク用のフラグビットを適用することによって、入力論理リンク毎に、フロー検出に必要な項目（フィールド）にのみ有効データを残し、フロー検出に不要な項目は無効値に置き換えた形の検索キーを生成し、この検索キーでフロー検索テーブル用のＣＡＭをアクセスするようにしたフロー識別装置が提案されてい Further, JP 2001-156840 (prior art 3), from the header of the input packet, the specific field can be a flow identification condition, e.g., source address contained in the IP header, destination address, protocol, TOS ( a Type of Service), source port included in the TCP or UDP header, it extracts the destination port, for these fields fields, for pre-input logical link number and a mask registered in correspondence to the search flag table by applying the flag bit for each input logical link, leaving valid data only to required flow detection fields (fields), unnecessary items the flow detection generates a search key in the form of replacing the invalid value, flow search flow identification apparatus adapted to access the CAM for the table has not been proposed in the search key 。 .
然るに、上記従来技術２は、検索キーのビット長が増大した場合の１つの解決策を提案したものであって、検索キーおよびフローエントリのビット長短縮を意図したものではない。 However, the prior art 2, the search be one bit length of the key is proposed one solution in the case of increasing, not intended bit length shortening of the search key and the flow entry. また、従来技術３は、フロー識別条件となり得るヘッダ情報項目の全てを含む汎用的な検索キー・フォーマットを採用し、入力論理リンク毎に、不要となるヘッダ情報項目をマスキングすることによって、検索キーとフローエントリとの照合を容易にしたものであり、従来技術２と同様、検索キーおよびフローエントリのビット長短縮を意図したものではない。 Further, the prior art 3, by adopting a generic search key formats, including all header information items that can be a flow identification condition for each input logical link, masking the header information items to be unnecessary, the search key and is obtained by facilitating the matching of the flow entry, similar to the prior art 2, not intended bit length shortening of the search key and the flow entry.
多様化するフロー識別条件に対して、このように汎用化された同一フォーマットの検索キーで対応しようとすると、検索キーのビット長が増大し、ＣＡＭ６２とフロー制御用ＬＳＩ６１におけるピンネックおよびＣＡＭの容量不足の問題に直面する。 For the flow identification condition to diversify, an attempt to cope with the search key in the same format that the thus generalized, the bit length increases the search key, out of space pin neck and CAM in CAM62 and flow control LSI61 to face the problem.
本発明の目的は、ＣＡＭを有効に利用して、多様化されたフロー識別条件に対応できるフロー検出装置およびパケット転送装置を提供することにある。 An object of the present invention, by effectively utilizing the CAM, is to provide a flow detector and the packet transfer apparatus can cope with diversified flow identification condition.
本発明の他の目的は、ＣＡＭ検索キーのビット長を短縮することによって、フロー識別条件が多様化した場合でも、ＣＡＭ容量を有効に利用できるフロー検出装置およびパケット転送装置を提供することにある。 Another object of the present invention, by reducing the bit length of the CAM search key, even when the flow identification condition is diversified, there is provided a flow detection device and a packet transfer apparatus which can effectively use the CAM capacity .
上記目的を達成するため、本発明のフロー検出装置は、複数のフロー定義エントリを有するフロー検出ＣＡＭ（Content Addressable Memory）と、フロー識別条件によって異なるフォーマットの検索キーを生成する検索キー生成部と、上記ＣＡＭの各フロー定義エントリのアドレスと対応してフロー検索結果を保持するテーブルとを備え、上記ＣＡＭをフロー識別条件に応じてパケットヘッダから抽出された少なくとも１つのヘッダ情報項目を含む可変フォーマットの検索キーでアクセスし、上記ＣＡＭから出力される上記検索キーに一致したフロー定義エントリのアドレスに従って、上記テーブルからフロー検索結果を得るようにしたことを特徴とする。 To achieve the above object, the flow detection device of the present invention, a flow detection CAM having a plurality of flow definition entry (Content Addressable Memory), a search key generating unit for generating a search key in different formats by flow identification condition, and a table for holding an address and corresponding to the flow results for the flow definition entry in the CAM, the variable format that includes at least one of the header information items extracted from the packet header in accordance with the flow identification condition the CAM accessed by search keys, in accordance with the address of the flow definition entry that matches the above search key output from the CAM, characterized in that to obtain the flow search results from the table.
上記フロー検出ＣＡＭは、例えば、検索キー・フォーマットの種類と対応した複数のテーブル領域からなり、テーブル領域毎に、フロー識別条件となるヘッダ情報項目の値を記述した複数のフロー定義エントリを有し、検索キーに一致した最初のフロー定義エントリのアドレスを出力する。 The flow detection CAM, for example, a plurality of table area corresponding with the type of the search key format for each table area, a plurality of flow definition entry that describes the value of the header information items to be flow identification condition , and it outputs the address of the first flow definition entry matching the search key.
また、本発明は、複数の入、出力回線に接続され、各入力回線から受信したパケットをヘッダ情報によって特定される何れかの出力回線に転送するパケット転送装置において、各受信パケットのヘッダ情報から該パケットが属するパケットフローを識別するためのフロー検出部と、各受信パケットに対して予めパケットフロー毎に指定された転送制御を実施するための手段とを有し、 Further, the present invention includes a plurality of input connected to the output line, in a packet transfer device for transferring to one of the output lines specified by the header information received packet from each input line, from the header information of each received packet and means for performing a flow detection unit for identifying a packet flow to which the packet belongs, the transfer control specified in advance for each packet flow for each received packet,
上記フロー検出部が、複数のフロー定義エントリを有するフロー検出ＣＡＭと、フロー識別条件によって異なるフォーマットの検索キーを生成する検索キー生成部とを備え、上記ＣＡＭをパケットヘッダから抽出された少なくとも１つのヘッダ情報項目を含む可変フォーマットの検索キーでアクセスして、フロー検出することを特徴とする。 The flow detection unit, and the flow detection CAM having a plurality of flow definition entry, a search key generating unit for generating a search key in different formats by flow identification condition, at least one of the extracted the CAM from the packet header and access variable format search key including header information item, characterized by flow detection.
更に詳述すると、上記検索キー生成部は、例えば、各入力回線の識別子と対応してフロー識別条件となるヘッダ情報項目を指定した検索キー定義テーブルを備え、各受信パケットの入力回線の識別子に基づいて上記検索キー定義テーブルを参照し、該テーブルで指定されたヘッダ情報項目を含む検索キーを生成する。 To be more specific, the search key generation unit is provided with, for example, a search key definition table specifies the header information items to be flow identification condition in correspondence with the identifier of each input line, the identifier of the input line of each received packet based referring to the search key definition table, and generates a search key including the header information items specified in the table.
本発明の１実施例によれば、上記検索キー生成部が、各入力回線の識別子とフロー検出モードとの対応関係を示すフロー検出モードテーブルと、上記フロー検出モードテーブルが示す各フロー検出モードと対応してフロー識別条件となるヘッダ情報項目を指定した検索キー定義テーブルを備え、上記検索キー生成部が、上記フロー検出モードテーブルを参照して各受信パケットのフロー検出モードを特定し、上記検索キー定義テーブルが示す上記特定フロー検出モードのフロー識別条件に従って、検索キーを生成する。 According to one embodiment of the present invention, the search key generation unit, and the flow detection mode table showing the correspondence between the identifier and the flow detection mode for each input line, and each flow detection mode indicated by the flow detection mode table includes a search key definition table is specified header information item corresponding to the flow identification condition, the search key generation unit, identifies a flow detection mode of each received packet with reference to the flow detection mode table, the search according to the flow identification condition of the specific flow detection mode indicated by the key definition table, and generates a search key.
本発明の別の実施例では、上記検索キー生成部が、各入力回線の識別子とモード識別条件との対応関係を示すモード識別条件テーブルと、各入力回線の識別子とモード識別条件とフロー検出モードとの対応関係を示す検出モードテーブルと、上記フロー検出モードテーブルが示す各フロー検出モードと対応してフロー識別条件となるヘッダ情報項目を指定した検索キー定義テーブルを備え、上記検索キー生成部が、各受信パケットの入力回線の識別子と上記モード識別条件テーブルで指定されたモード識別条件に従って、上記フロー検出モードテーブルから各受信パケットのフロー検出モードを特定し、上記検索キー定義テーブルが示す上記特定フロー検出モードのフロー識別条件に従って、検索キーを生成する。 Another In embodiments, the search key generation unit, correspondence between the mode identification condition table showing the identifier and mode identification condition of each input line, identifiers and mode identification condition and the flow detection mode for each input line of the present invention a detection mode table indicating a correspondence relationship between, in correspondence with each flow detection mode indicated by the flow detection mode table comprises a search key definition table specifies the header information items to be flow identification condition, the search key generation unit according identifier and the mode identification condition table is the mode identification condition specified in the input line of each received packet to identify the flow detection mode for each received packet from the flow detection mode table, the specific indicated by the search key definition table according to the flow identification condition of the flow detection mode, to generate a search key.
ここで、フロー検出部が参照するヘッダ情報には、各入力回線に接続された入力回線インタフェースで生成された内部ヘッダ情報を含む。 Here, the header information flow detection unit refers, it includes an internal header information generated by the input line interface connected to the input line. 内部ヘッダ情報は、例えば、入力回線識別子、出力回線識別子、転送優先度情報を示す複数のフィールドからなり、１つの物理回線上に論理的な複数のパスが多重化される場合は、上記入／出力回線識別子として、物理回線識別子と論理回線識別子とが適用される。 Internal header information includes, for example, if the input line identifier, an output line identifier, a plurality of fields indicating a transfer priority information, a plurality of logical paths on a single physical line is multiplexed, the upper input / as an output line identifier, a physical line identifier and the logical channel identifier is applied. また、モード識別条件テーブルには、同一入力回線上に多重化されたパス毎にフロー識別条件を設定する場合に、モード識別条件として、例えば、入力論理回線番号やフローラベル等のパス特定情報が記憶される。 In addition, the mode identification condition table, when setting the flow identification condition each path multiplexed on the same input line, a mode identification condition, for example, the path identification information such as the input logical line numbers or the flow label It is stored.
本発明によれば、ＣＡＭ検索キーが、冗長フィールドのない、各受信パケットのフロー識別に必要な項目のみを含むフォーマットとなっているため、検索キーとＣＡＭフローエントリのビット長を短縮することができ、フロー識別条件が多様化しても、ＣＡＭ容量を有効に利用して、高速のフロー検索が可能となる。 According to the present invention, CAM search key, without redundant field, since a format including only the items required for flow identification for each received packet, is possible to shorten the bit length of the search key and the CAM flow entries It can also diversified flow identification conditions, by effectively utilizing the CAM capacity, enabling high-speed flow search.
図５は、本発明のパケット転送装置が適用される通信ネットワークの１例を示す。 Figure 5 shows an example of a communication network packet forwarding device of the present invention is applied.
この通信ネットワークでは、企業Ａに属したサイトＡ１とＡ２、企業Ｂに属したサイトＢ１とＢ２が、それぞれキャリアＩＰネットワーク２００を介して通信する。 This communication network sites A1 and A2 belonging to the company A, the site B1 and B2 belonging to the company B, and communicates through the carrier IP network 200, respectively.
キャリアＩＰネットワーク２００は、エッジルータ２０１、２０２と、これらのエッジルータ間に配置されたバックボーンルータ２０３、２０４からなる。 Carrier IP network 200, the edge router 201 and 202, consisting of a backbone router 203 and 204 disposed between these edge routers. キャリアＩＰネットワーク２００内でのパケット転送は、例えば、ＩＰパケットに付加されたＭＰＬＳラベルによりパスを識別するＭＰＬＳ（Multi Protocol Label Switching）によって行われる。 Packet transfer in the carrier IP network 200 within, for example, performed by MPLS (Multi Protocol Label Switching) identifying a path through the added MPLS labels to the IP packets. ＭＰＬＳでは、トラフィックエンジニアリングやＶＰＮ（仮想閉域網）を実現でき、ＥＸＰ（EXPerimental）ビットフィールドでパケット転送の優先度を表示することができる。 In MPLS, can achieve traffic engineering and VPN (virtual private network), it is possible to display the priority of packet transfer in EXP (Experimental) bit field.
サイトＡ１は、ゲートウェイ（ＧＷ）ルータ２１１を介してエッジルータ２０１に接続される複数の端末２１２、２１３、・・・からなり、サイトＡ２は、ＧＷルータ２３１を介してエッジルータ２０２に接続される複数の端末２３２、２３３、・・・からなる。 Site A1 is a plurality of terminals 212 and 213 are connected to the edge router 201 via a gateway (GW) router 211, consists ..., site A2 is connected to the edge router 202 via the GW router 231 a plurality of terminals 232 and 233, consisting of .... 同様に、サイトＢ１は、ＧＷルータ２２１を介してエッジルータ２０１に接続される複数の端末２２２、２２３、・・・からなり、サイトＢ２は、ＧＷルータ２４１を介してエッジルータ２０２に接続される複数の端末２４２、２４３、・・・からなる。 Similarly, sites B1, a plurality of terminals 222 and 223 connected to the edge router 201 via the GW router 221 consists ..., site B2 is connected to the edge router 202 via the GW router 241 a plurality of terminals 242 and 243, consisting of ....
本発明のパケット転送装置は、エッジルータ２０１、２０２に適用される。 Packet transfer apparatus of the present invention is applied to the edge router 201. 以下の説明では、サイトＡ１、Ｂ１とエッジルータ２０１との間で、ＩＰｖ６アドレスをもつＩＰパケットが通信されるものと仮定する。 In the following description, with the sites A1, B1 and the edge router 201, it is assumed that IP packet having the IPv6 address is communicated. 本発明では、例えば、ＧＷルータ２２１からエッジルータ２０１に向かうパケットフローＦＬ１、エッジルータ２０１からＧＷルータ２１１に向かうパケットフローＦＬ２、エッジルータ２０１からバックボーンルータ２０３に向かうパケットフローＦＬ３のように、エッジルータ２０１が、各入力パケットの属したフローを識別し、各入力パケットに対して、フロー毎に予め指定された転送制御制御を実行する。 In the present invention, for example, packet flow FL1 directed from GW router 221 to the edge router 201, the packet flow FL2 directed from the edge router 201 to the GW router 211, such as the packet flow FL3 toward the edge router 201 to the backbone router 203, the edge router 201, identifies the flows belonging of each input packet, performing for each input packet, the pre-specified transfer control control for each flow.
図６は、エッジルータ２０１が扱うパケットフォーマットを示す。 Figure 6 shows a packet format of the edge router 201 is responsible for.
図６（Ａ）は、エッジルータ２０１とサイトＡ１、Ｂ１との間で送受信されるパケット５００のフォーマットを示す。 FIG 6 (A) shows a format of a packet 500 transmitted and received between the edge router 201 and site A1, B1. パケット５００は、データ（ユーザ情報）部５１０に、ＩＳＯ参照モデルにおけるレイヤ４（トランスポート層）のヘッダ５２０、レイヤ３（ネットワーク層）のヘッダ５３０、レイヤ２（データリンク層）のヘッダ５４０からなるパケットヘッダを付加した構成となっている。 Packet 500, the data (user information) section 510, consisting of layer 4 header 520 (transport layer), the header 530 of the Layer 3 (network layer), the header 540 of the layer 2 (data link layer) in the ISO reference model It has a configuration obtained by adding a packet header.
レイヤ４ヘッダ５２０は、上位アプリケーションを表す送信ポート（Source Port：「ＳＰＯＲＴ」）５２１と、宛先ポート（Destination Port：「ＤＰＯＲＴ」）５２２と、図面では省略されたシーケンス番号などの情報を含む。 Layer 4 header 520, the transmission port for the upper application includes the:: ( "DPORT" Destination Port) 522, information such as a sequence number that is omitted in the drawing and (Source Port "SPORT") 521, a destination port. レイヤ３ヘッダ５３０は、送信元ＩＰアドレス（Source IP Address：「ＳＩＰ」）５３１、宛先ＩＰアドレス（Destination IP Address：「ＤＩＰ」）５３２、フローラベル５３３、その他の情報を含む。 Layer 3 header 530, the source IP address (Source IP Address: "SIP") 531, a destination IP address: including (Destination IP Address "DIP") 532, a flow label 533, and other information.
レイヤ２ヘッダ５４０には、ＧＷルータ２１１、２２１とエッジルータ２０１との接続回線の種類に応じて、例えば、イーサネット（登録商標）の場合は、送信元ＭＡＣアドレスと宛先ＭＡＣアドレス、フレームリレー回線の場合はＤＬＣＩ（Data Link Connection Identifier）等の情報が設定される。 The layer 2 header 540, depending on the type of connection line between the GW router 211 and 221 and the edge router 201, for example, Ethernet (registered trademark), the source MAC address and destination MAC address, a frame relay line If information such as DLCI (data Link Connection Identifier) ​​is set. 接続回線がＡＴＭ回線の場合、データ部５１０〜レイヤ３ヘッダ５３０からなるＩＰパケットが固定長の複数のブロック分割され、各ブロックにＶＰＩ／ＶＣＩを含むセルヘッダを付加し、ＡＴＭセル形式のデータ転送が行われる。 If the connection line is an ATM line, IP packets comprising data unit 510 to the Layer 3 header 530 is a plurality of blocks divided in a fixed length, adds a cell header containing the VPI / VCI in each block, the data transfer of the ATM cell format It takes place. この場合、レイヤ２ヘッダ５４０は、ＡＴＭセルに付加すべきＶＰＩ／ＶＣＩを意味している。 In this case, layer 2 header 540, which means the VPI / VCI to be added to the ATM cell. ここでは、ネットワーク層のプロトコルがＩＰのパケットフォーマットを示したが、本発明のフロー制御は、ネットワーク層のプロトコルがＩＰ以外のもの、例えば、ＩＰＸ等であっても良い。 Here, the network layer protocol is the IP packet format, the flow control of the present invention, those of the network layer protocols other than IP, for example, it may be an IPX or the like.
図６（Ｂ）は、エッジルータ２０１とバックボーンルータ２０３、２０４との間で送受信されるパケット５０１のフォーマットを示す。 6 (B) shows a format of a packet 501 transmitted and received between the edge router 201 and backbone router 203.
パケット５０１は、パケット５００のレイヤ２ヘッダ５４０とレイヤ３ヘッダ５３０との間に、ＭＰＬＳ用のＳｈｉｍヘッダ５５０を付加した構成となっている。 Packet 501, between the layer 2 header 540 and the layer 3 header 530 of the packet 500 has a configuration obtained by adding the Shim header 550 for MPLS. Ｓｈｉｍヘッダ５５０は、ＭＰＬＳラベル５５１と、優先度等を表すＥＸＰ５５２と、ＴＴＬ（生存時間）等の情報を含む。 Shim header 550 includes a MPLS label 551, and EXP552 representing the priority or the like, information such as TTL (time-to-live).
図６（Ｃ）は、エッジルータ２０１内部でのパケット転送とフロー制御のために、上記パケット５００および５０１の先頭に付加される内部ヘッダ５６０の構成を示す。 FIG. 6 (C), for packet transfer and flow control inside the edge router 201, shows the configuration of the internal header 560 which is prepended to the packet 500 and 501.
内部ヘッダ５６０は、例えば、パケットを受信した入力回線の識別子（物理回線番号５６１と論理回線番号５６２）と、パケットを送出すべき出力回線の識別子（物理番号回線５６３と論理回線番号５６４）と、パケット転送の優先度５６５とを示すフィールドからなっている。 Internal header 560, for example, an input line of the identifiers received packets (physical line number 561 and the logical line number 562), the identifier of the output line to be transmitted packets (physical number lines 563 and the logical line number 564), It consists field indicating the priority 565 of the packet transfer. 論理回線番号５６２、５６４を示すフィールドの内容は、例えば、ＡＴＭ回線やＭＰＬＳ回線のように、入出力回線上に複数のパスが多重化されている場合に有効となる。 Contents of the field indicating the logical line number 562, 564, for example, as an ATM line or MPLS line becomes effective when a plurality of paths on the input and output lines are multiplexed.
図１は、上述したエッジルータ２０１として適用可能な本発明によるパケット転送装置１０の１実施例を示す。 Figure 1 shows an embodiment of a packet transfer apparatus 10 according to the invention, applicable as the edge router 201 as described above.
パケット転送装置１０は、それぞれ入力回線ＩＮｉ(ｉ＝１〜ｎ)に接続された複数の入力回線インタフェース１１−ｉ(ｉ＝１〜ｎ)と、それぞれ出力回線ＯＵＴｉ(ｉ＝１〜ｎ)に接続された複数の出力回線インタフェース１２−ｉ(ｉ＝１〜ｎ)と、出力回線インタフェース１２−ｉ毎に設けられた出力バッファ１３−ｉおよびパケット振り分け回路１８−ｉ(ｉ＝１〜ｎ)と、上記複数の入力回線インタフェース１１−ｉおよびパケット振り分け回路１８−ｉに接続されたパケット中継部（パケットスイッチ部）１４と、各入力回線インタフェース１１−ｉで受信された可変長パケットの転送先となる出力回線の判定（ルーティング）機能とフロー検出機能とを備えた制御部１５と、上記各入力回線インタフェース１１−ｉから信号線Ｌ１−ｉ(ｉ Packet transfer apparatus 10 each input line INi and (i = 1 to n) connected to a plurality of input line interface 11-i (i = 1~n), each output line OUTi (i = 1~n) a plurality of connected output line interface 12-i (i = 1 to n), the output line interface 12-i is provided for each output buffer 13-i and a packet distribution circuit 18-i (i = 1~n) When, the plurality of input line interface 11-i and a packet distribution circuit 18-i connected to the packet relay unit (packet switches) 14, the transfer destination variable length packets received by each input line interface 11-i determined to become an output line (routing) and capabilities and control unit 15 that includes a flow detection function, each input line interface 11-i from the signal line L1-i (i １〜ｎ)に出力されたパケットヘッダ情報を順次に制御部１５に供給する多重化回路１６と、制御部１５が信号線Ｌ２、Ｌ３に出力した出力回線識別子（出力回線番号）とフロー制御指示情報を各パケットヘッダ情報の送信元となる入力回線インタフェース１１−ｉに供給する振り分け回路１７とからなる。 A multiplexing circuit 16 supplies the sequentially control unit 15 the packet header information output to the 1 to n), the output line identifier (output line number control unit 15 is output to the signal line L2, L3) and flow control instruction the information consists of source and comprising input line interface 11-i to supply distribution circuit 17. each packet header information.
後述するように、制御部１５は、各種のテーブルおよびＣＡＭを備えており、これらのテーブル類へのデータ設定は管理端末９０から信号線Ｌ４を介して行われる。 As described later, the control unit 15 includes a variety of tables and CAM, data setting to these tables such is through the signal line L4 from the management terminal 90.
図７は、入力回線インタフェース１１−ｉと制御部１５の詳細を示す。 Figure 7 shows details of input line interface 11-i and the control unit 15.
入力回線インタフェース１１−ｉは、入力回線ＩＮｉからの受信信号から入力パケット５００または５０１を再生するＬ２終端部１１１と、Ｌ２終端部１１１から受信した入力パケットに内部ヘッダ５３０を付加し、内部パケットとして出力する内部ヘッダ付加部１１２と、内部ヘッダ付加部１１２から受信した内部パケットを入力バッファ１１４に格納すると共に、内部パケットから抽出したパケットヘッダ（レイヤ４ヘッダ５２０〜内部ヘッダ５６０）を信号線Ｌ１−ｉに出力するパケットヘッダ抽出部１１３と、入力バッファ１１４に蓄積されたパケットのヘッダ情報の書き換えとパケット中継部１４への転送を制御するパケット転送制御部１１５と、入力バッファ１１４からヘッダ変換されたパケットを読み出すパケット読出し部１ Input line interface 11-i includes a L2 termination unit 111 for reproducing an input packet 500 or 501 from the received signal from the input line INi, adds the internal header 530 to the input packet received from the L2 end portion 111, as an internal packet an internal header adding unit 112 outputs, stores the internal packet received from the internal header adding unit 112 in the input buffer 114, a signal line packet header extracted from the internal packet (layer 4 header 520 to the internal header 560) L1- a packet header extraction unit 113 to be output to the i, the packet transfer control unit 115 for controlling the transfer to rewrite the packet relay unit 14 of the header information stored in the input buffer 114 packets, which the header is converted from the input buffer 114 packet reading unit 1 for reading the packet ６とからなる。 Consisting of 6.
Ｌ２終端部１１１は、入力回線ＩＮｉからの受信パケットがＡＴＭセルの場合、受信セルから入力パケット５００または５０１を再生し、受信セルヘッダから抽出したＶＰＩ／ＶＣＩの値をレイヤ２ヘッダ５４０に設定する。 L2 terminating unit 111 receives a packet from the input line INi if the ATM cell, reproduces the input packet 500 or 501 from the received cell, it sets the value of the extracted VPI / VCI from the received cell header to the layer 2 header 540. 内部ヘッダ付加部１１２は、図６の（Ｃ）に示したフォーマットを持つ内部ヘッダ５６０を生成し、予め指定してある入力回線ＩＮｉの識別子（番号）を入力物理回線番号５６１に設定する。 Internal header adding unit 112 generates the internal header 560 having a format shown in FIG. 6 (C), sets an identifier (ID) of the input line INi you have specified in advance in the input physical line number 561. 入力回線上に多重化パスが形成されていた場合は、パス識別子が入力論理回線番号５６２に設定され、そうでない場合は、入力論理回線番号５６２に無意味な値が設定される。 If multiplexing path has been formed on the input line, the path identifier is set to the input logical line number 562, otherwise, meaningless values ​​are set to the input logic line number 562. この時点では、出力物理回線番号５６３、出力論理回線番号５６４、パケット転送優先度５６５には、無意味な値が設定される。 At this point, the output physical port number 563, the output logic line number 564, a packet transfer priority 565, meaningless values ​​are set.
制御部１５は、ルーティング処理部２０と、フロー検出部３０と、フロー制御指示部４０とからなっている。 Control unit 15, a routing processing section 20, the flow detection unit 30 consists of a flow control instruction unit 40.
ルーティング処理部２０は、ルーティングテーブルを備え、多重化回路１６から信号線Ｌ１に出力されるパケットヘッダ情報から宛先ＩＰアドレス５２２を抽出し、ルーティングテーブルから上記宛先ＩＰアドレスと対応して予め登録されている出力回線識別子（出力物理回線番号と出力論理回線番号）を読出して、信号線Ｌ２に出力する。 Routing processing unit 20 includes a routing table, extracts the destination IP address 522 from the packet header information output from the multiplexing circuit 16 to the signal line L1, is registered in advance in correspondence with the destination IP address from the routing table reads the output line identifier (output physical port number and an output logical line number) are Te, and outputs to the signal line L2.
フロー検出部３０は、後述するように、フロー識別条件に応じて上記パケットヘッダ情報から抽出した複数のヘッダ情報項目からなる検索キーを生成し、フロー検出ＣＡＭから上記検索キーに該当したフローエントリを検索する。 Flow detection unit 30, as described later, it generates a search key composed of a plurality of header information items extracted from the packet header information in accordance with the flow identification condition, a flow entry that corresponds to the search key from the flow detection CAM Search for. フロー制御指示部４０は、フロー検出ＣＡＭから信号線Ｌ５に出力されるフローエントリアドレスの値に従って、検索結果保持テーブルを参照し、該テーブルで指定されたフロー制御指示情報（パケット処理の種類または転送優先度）を信号線Ｌ３に出力する。 Flow control instruction unit 40, in accordance with the flow entry address value output from the flow detection CAM to the signal line L5, the search results with reference to the holding table, the type or the transfer flow control instruction information (packet processing specified by the table and it outputs the priority) to the signal line L3.
信号線Ｌ２に出力された出力回線識別子と、信号線Ｌ３に出力されたフロー制御指示情報は、振り分け回路１７に入力される。 An output line identifier outputted to the signal line L2, flow control instruction information output to the signal line L3 is inputted to the distribution circuit 17. 振り分け回路１７には、信号線Ｌ１に出力されたパケットヘッダ情報中の入力回線番号５６１の値ｉが制御信号として与えてあり、信号線Ｌ２、Ｌ３から入力された出力回線番号とフロー制御指示情報が、上記入力回線番号ｉで特定される入力回線インタフェース１１−ｉのパケット転送制御部１１５に振り分けられる。 The distribution circuit 17, the value i of the input line number 561 in the packet header information output to the signal line L1 is Yes given as a control signal, the output line number and flow control instruction information input from the signal line L2, L3 but it is distributed to the packet transfer control unit 115 of the input line interface 11-i specified by the input line number i.
フロー制御指示情報が特定の優先度付与を示していた場合、パケット転送制御部１１５は、入力バッファ１１４に蓄積された先頭パケットの内部ヘッダ５６０に、上記振り分け回路１７から受信した出力回線識別子（出力物理回線番号５６３と出力論理回線番号５６４の値）と優先度（パケット転送優先度５６５の値）を書き込み、信号線Ｌ１１５を介して、パケット読出し部１１６に上記パケットの読出しを指示する。 If flow control instruction information indicates particular prioritization, the packet transfer control unit 115, the internal header 560 of the first packet stored in the input buffer 114, the output line identifier (output received from the distribution circuit 17 physical line number 563 and the output logic line number value of 564) and priority write (the value of the packet transfer priority 565), via a signal line L115, and instructs the reading of the packet to the packet read unit 116. これによって、入力パケットに対するＱｏＳ制御が実現される。 Thereby, QoS control is realized for the input packet.
フロー制御指示情報がパケット廃棄を示していた場合は、上記内部ヘッダ５６０への情報の書き込みとパケット読出し部１１６へのパケット読出しの指示は省略され、受信パケットが廃棄処理される。 If flow control instruction information indicates a packet discard instruction of the packet read into the writing and the packet reading unit 116 of the information to the internal header 560 is omitted, the received packet is discarded. これによって、入力パケットのフィルタリング制御が実現される。 Thus, the filtering control of the input packet is implemented.
パケット転送制御部１１５は、入力バッファ１１４からのパケットの転送または廃棄の都度、入力バッファの読出しアドレスを次パケットの先頭アドレスに位置付けることによって、入力バッファ中の蓄積パケットを次々と処理する。 Packet transfer control unit 115, every time the transfer or discard the packet from the input buffer 114, by positioning the read address of the input buffer to the start address of the next packet to process successively the packets accumulated in the input buffer.
図７に示した実施例では、ルーティング処理部２０が複数の入力回線インタフェースで共用される構成となっているが、ルーティング処理部２０を各入力回線インタフェース１１−ｉに配置し、制御部１５がフロー検出部３０とフロー制御指示部４０を備えた構成としてもよい。 In the embodiment shown in FIG. 7 has a configuration in which the routing processor 20 is shared by a plurality of input line interface, placing a routing processing unit 20 to each input line interface 11-i, the control unit 15 it may include the flow detection unit 30 and the flow control instruction unit 40.
図１において、パケット中継部１４は、入力回線インタフェース１１−ｉ（ｉ＝１〜ｎ）と接続される入力ポートＰＩｉ（ｉ＝１〜ｎ）と、パケット振り分け回路１８−ｉ（ｉ＝１〜ｎ）と接続される出力ポートＰＯｉ（ｉ＝１〜ｎ）とを備えており、各入力ポートＰＩｉから受信したパケットを出力物理回線番号５６３の値ｊで特定される出力ポートＰＩｊにスイッチングする。 In Figure 1, the packet relaying unit 14 includes an input port PIi (i = 1~n) connected to the input line interface 11-i (i = 1~n), the packet distribution circuits 18-i (i = 1~ n) and has an output port POi (i = 1~n) connected to switch the output port PIj identified packets received from each input port PIi by the value j in the output physical port number 563. 送信バッファ１３−ｊは、優先度に対応した複数の送信キューからなっており、振り分け回路１８―ｊは、出力ポートＰＩｊから出力されたパケットを内部ヘッダのパケット転送優先度５６５に従って、何れかの送信キューに蓄積する。 The transmission buffer 13-j is formed of a plurality of transmission queue corresponding to the priority, the distribution circuit 18-j according to the packet transfer priority 565 of the internal header a packet output from the output port PIj, either It is stored in the transmission queue. 出力回線インタフェース１２−ｊは、送信バッファ１３−ｊの蓄積パケットを優先度順に読み出し、内部ヘッダ５３０を除去した後、出力回線ＯＵＴｊのデータリンク層プロトコルに従ったＬ２ヘッダを付加した形で、出力回線ＯＵＴｊに送出する。 Output line interface 12-j reads the packets accumulated in the transmission buffer 13-j in order of priority, after removal of the internal header 530, in the form of adding the L2 header in accordance with the data link layer protocol of the output line OUTj, output It is transmitted to the line OUTj.
図８は、フロー検出部３０とフロー制御指示部４０の１実施例を示す。 Figure 8 shows an embodiment of a flow detection unit 30 and the flow control instruction unit 40.
フロー検出部３０は、検索キー生成部３１と、ＣＡＭ制御部３２と、フロー検出ＣＡＭ３３とからなる。 Flow detection unit 30 includes a retrieval key generator 31, a CAM control unit 32, consisting of flow detection CAM33 Prefecture. 検索キー生成部３１は、信号線Ｌ１から受信したヘッダ情報を格納するためのヘッダ情報レジスタ３１０と、フロー検出モードテーブル３１１と、検索キー定義テーブル３１２と、検索キー生成制御部３１３とからなっている。 Search key generation unit 31, a header information register 310 for storing header information received from the signal line L1, the flow detection mode table 311, the search key definition table 312, becomes the search key generation controller 313 there.
フロー検出モードテーブル３１１は、例えば、図９に示すように、入力回線番号（入力物理回線番号）３１１１と対応して、入力回線上のプロトコルを示す識別子３１１２と、フロー検出モード３１１３とを示した複数のエントリ３１１−１、３１１−２、…からなっている。 Flow detection mode table 311, for example, as shown in FIG. 9, in correspondence with the input line number (input physical line number) 3111, an identifier 3112 that indicates the protocol on the input lines showed the flow detection mode 3113 a plurality of entries 311-1 and 311-2, are made of .... フロー検出モード３１１３は、検索キー生成制御部３１３で生成すべき検索キーのフォーマット種類（タイプ）を示している。 Flow detection mode 3113 indicates the format type of the search key to be generated by the search key generation controller 313 (type).
また、検索キー定義テーブル３１２は、例えば、図１０に示すように、フロー検出モード３１２１と対応して、フロー識別条件となる検索キー要素３１２２を指定した複数のエントリ３１２−１、３１２−２、・・・からなっている。 The search key definition table 312, for example, as shown in FIG. 10, the flow in correspondence with the detection mode 3121, a plurality of entries specifying the search key element 3122 serving as a flow identification condition 312-1 and 312-2, It is made from .... 検索キー要素３１２２は、検索キー生成制御部３１３で生成すべき検索キーの構成要素となるヘッダ情報の項目名（フィールド名）を示している。 Search key element 3122 shows item names of the components to become the header information of the search key to be generated by the search key generation controller 313 (field name).
ここで、エントリ３１２−１は、検出モード１のフローが、入力パケットのＭＰＬＳフィールド５５１とＥＸＰフィールド５５２（図６（Ｂ）参照）の組み合せによって識別されことを意味し、エントリ３１２−２は、検出モード２のフローが、入力パケットのＳＩＰ５３１とＳＰＯＲＴ５２１の組み合せによって決まることを意味している。 Here, entry 312-1, the flow detection mode 1, which means that is identified by the combination of MPLS fields 551 and EXP field 552 of the incoming packet (see FIG. 6 (B)), the entry 312-2, flow detection mode 2, which means that determined by the combination of SIP531 and SPORT521 of the input packet. また、エントリ３１２−３は、検出モード３のフローが、入力パケットのＤＩＰ５３２とＤＰＯＲＴ５２２の組み合せによって決まることを意味している。 Further, entry 312-3, the flow detection mode 3, which means that determined by the combination of DIP532 and DPORT522 of the input packet.
図８に戻って、ヘッダ情報レジスタ３１０には、信号線Ｌ１を介して、パケットヘッダ抽出部１１３で抽出した入力パケットのヘッダ情報５６０〜５２０が設定される。 Returning to FIG. 8, the header information register 310, via the signal line L1, the header information 560 to 520 of the input packet extracted by the packet header extracting section 113 is set. 本実施例において、検索キー生成制御部３１３は、ヘッダ情報レジスタ３１０に設定されたヘッダ情報の中から、信号線Ｓ１で示すように、内部ヘッダ５６０の先頭に位置した入力物理回線番号（以下、単に入力回線番号という）フィールド５６１の値を読み出し、フロー検出モードテーブル３１１から、上記入力回線番号５６１（信号線Ｓ２）と対応したプロトコル識別子３１１２（信号線Ｓ３）とフロー検出モード３１１３（信号線Ｓ４）を読み出す。 In the present embodiment, the search key generation controller 313, from the header information set in the header information register 310, as shown by the signal line S1, the input physical line number located at the head of the internal header 560 (hereinafter, simply reading the value of the input of line number) field 561, flow detection from the mode table 311, the input line number 561 (signal line S2) and the protocol identifier 3112 corresponding (signal line S3) flow detection mode 3113 (signal line S4 ) read out.
検索キー生成制御部３１３は、フロー検出モード３１１３（信号線Ｓ５）に従って検索キー定義テーブル３１２を参照し、上記フロー検出モードと対応する検索キー要素３１１２（信号線Ｓ６）を読み出す。 Search key generation controller 313 refers to the search key definition table 312 in accordance with the flow detection mode 3113 (signal lines S5), reads out the search key element 3112 (signal line S6) corresponding to the flow detection mode. また、ヘッダ情報レジスタ３１０から、上記検索キー要素３１１２で指定されたヘッダ情報項目（信号線Ｓ７）の値を読み出して、これらのヘッダ情報項目を含むフロー検索キーＫＥＹを生成する。 Further, from the header information register 310, reads the value of the specified header information items (signal line S7) in the search key element 3112 generates a flow search key KEY that contain these header information items.
尚、ヘッダ情報レジスタ３１０に格納されたヘッダ情報は、図６の（Ａ）、（Ｂ）で示したように、入力回線によって部分的に異なったフォーマットとなっているが、レジスタ３１０に格納されているヘッダ情報のフォーマットは、フロー検出モードテーブル３１１から読み出されたプロトコル識別子３１１２によって特定されるため、検索キー生成制御部３１３は、上記プロトコル識別子に従って、ヘッダ情報レジスタ３１０から検索キー要素３１１２で指定された任意のヘッダ情報項目を抽出できる。 The header information stored in the header information register 310, of FIG. 6 (A), as shown in (B), but has a partly different format by the input line, is stored in the register 310 and the format of the header information and, in order to be identified by the protocol identifier 3112 read from the flow detection mode table 311, search key generation controller 313, according to the above protocol identifier, a header information register 310 in the search key elements 3112 the specified arbitrary header information items are extractable. また、フロー検出モードテーブル３１１と検索キー定義テーブル３１２へのエントリの設定と更新は、管理端末９０から信号線Ｌ４、検索キー生成制御部３１３を介して行われる。 The setting of the entry to the flow detection mode table 311 to the search key definition table 312 and updates the signal line L4 from the management terminal 90 is performed via a search key generation controller 313.
図１１は、検索キー生成制御部３１３で生成されるフロー検索キーの１例を示す。 Figure 11 shows an example of a flow search key generated by the search key generation controller 313.
フロー検索キーは、フロー検出モード３２１と、入力回線番号３２２と、検索キー定義テーブル３１２で指定された検索キー要素３２３、３２４、・・・とからなる。 Flow retrieval key is comprised of a flow detection mode 321, an input line number 322, the search key definition table 312 specified by the search key elements 323, 324, and .... ここに示したフロー検索キーＫＥＹ１〜ＫＥＹ３は、それぞれ図１０に示した検出モード１〜検出モード３に対応している。 Flow retrieval key KEY1~KEY3 shown here corresponds to the detection mode 1 detection mode 3 shown in FIG. 10, respectively.
本実施例によれば、回線番号１の入力回線からの受信パケットを処理する時は、モード１、入力回線番号１、ＭＰＬＳ、ＥＸＰからなるフォーマットのフロー検索キーＫＥＹ１が生成され、回線番号２の入力回線からの受信パケットを処理する時は、モード２、入力回線番号２、ＳＩＰ、ＳＰＯＲＴからなるフォーマットのフロー検索キーＫＥＹ２が生成される。 According to this embodiment, when processing a received packet from the input line of the line number 1, mode 1, the input line number 1, MPLS, the flow search key KEY1 format consisting of EXP is generated, the line number 2 when processing a received packet from the input line, mode 2, input line number 2, SIP, flow retrieval key KEY2 format consisting SPORT is generated. また、回線番号３の入力回線からの受信パケットを処理する時は、モード３、入力回線番号３、ＤＩＰ、ＤＰＯＲＴからなるフォーマットのフロー検索キーＫＥＹ３が生成される。 Also, when processing a received packet from the input line of the line number 3, mode 3, input line number 3, DIP, a flow search key KEY3 format consisting DPORT is generated.
検索キー生成制御部３１３で生成されたフロー検索キーＫＥＹは、ＣＡＭ制御部３２に与えられる。 Flow search key KEY that is generated by the search key generation controller 313 is given to the CAM control unit 32. ＣＡＭ制御部３２は、上記フロー検索キーＫＥＹに従ってフロー検出ＣＡＭ３３をアクセスする。 CAM control unit 32 accesses the flow detection CAM33 according to the above flow search key KEY.
本発明において、フロー検出ＣＡＭ３３は、例えば、図１２に示すように、フロー検出モード（フロー検出キー・フォーマット）と対応した複数のテーブル領域３３０−１〜３３０−ｎに分割され、各テーブル領域３３０−ｊには、フロー検索キーと対応したヘッダ情報項目を記述した複数のフローエントリＥＮ−ｊｋ（ｊ＝１〜ｎ、ｋ＝１、２、・・・）が登録されている。 In the present invention, the flow detection CAM33, for example, as shown in FIG. 12, is divided into a plurality of tables regions 330-1~330-n corresponding with the flow detection mode (flow detection key format), the table area 330 -j, the plurality of flow entries EN-jk describing the header information items corresponding with the flow search key (j = 1~n, k = 1,2, ···) are registered.
従って、前述のフロー検索キーＫＥＹ１でアクセスした場合、テーブル領域３３０−１に登録されたエントリＥＮ−１１〜ＥＮ−１ｉのうちの何れが検索され、最初に見つかったフローエントリのアドレスが信号線Ｌ５に出力される。 Thus, when accessed by the aforementioned flow retrieval key KEY1, is any search of the entries EN-11~EN-1i registered in the table area 330-1, the address of the flow entry found first signal line L5 It is output to. 同様に、フロー検索キーＫＥＹ２でアクセスした場合は、テーブル領域３３０−２に登録されたエントリ群（ＥＮ−２１〜ＥＮ−２ｊ）、フロー検索キーＫＥＹ３でアクセスした場合は、テーブル領域３３０−３に登録されたエントリ群（ＥＮ−３１、ＥＮ−３２、・・・）の中から検索条件に合致したエントリが検索され、それぞれの領域で最初に見つかったエントリアドレスが信号線Ｌ５に出力される。 Similarly, when accessed by the flow search key KEY2, registered entry group in the table area 330-2 (EN-21~EN-2j), and when accessed by the flow search key KEY3, the table area 330-3 registered entry group (EN-31, EN-32, ···) is searched entry matching the search condition from the first entry address found in each region is output to the signal line L5. 尚、フロー検出ＣＡＭ３３へのフローエントリの設定と更新は、管理端末９０から信号線Ｌ４、ＣＡＭ制御部３２を介して行われる。 The update a set of flow entries in flow detection CAM33 is performed via a signal line L4, CAM control unit 32 from the management terminal 90.
フレー検出ＣＡＭ３３から信号線Ｌ５に出力されたエントリアドレスは、フロー制御指示部４０に入力される。 Entry address output from the frame detection CAM33 the signal line L5 is input to the flow control instruction unit 40. フロー制御指示部４０は、図８に示すように、テーブル制御部４１と、検索結果保持テーブル４２とからなる。 Flow control instruction unit 40, as shown in FIG. 8, the table control unit 41, consisting of the search result holding table 42.
検索結果保持テーブル４２は、ＣＡＭ検索結果を保持するためのものであり、例えば、図１３に示すように、フロー検索ＣＡＭ３３のフローエントリアドレスと対応した複数のエントリ４１０−１〜４１０−ｑを含んでいる。 Search result holding table 42 is for holding the CAM search results, for example, as shown in FIG. 13, includes a plurality of entries 410-1~410-q corresponding with the flow entry address of the flow search CAM33 They are out. これらのエントリ４１０−１〜４１０−ｑには、フロー制御指示情報として、入力パケットに与えるべきＱｏＳ制御（優先度）情報やフィルタリング制御情報が設定されている。 These entries 410-1~410-q, as a flow control instruction information, QoS control (priority) information and filtering control information to be given to the input packet is set.
テーブル制御部４１は、上記信号線Ｌ５からフローエントリアドレスを受信すると、検索結果保持テーブル４２から上記フローエントリアドレスと対応するフロー制御指示情報を信号線Ｌ３に読み出す。 Table control unit 41 receives the flow entry address from the signal line L5, read the flow control instruction information from the corresponding search result holding table 42 and the flow entry address on the signal line L3. 検索結果保持テーブル４２へのエントリの設定と更新は、管理端末９０から信号線Ｌ４、テーブル制御部４１を介して行われる。 Results setting an entry to the holding table 42 and updates the signal line L4 from the management terminal 90 is performed via the table control unit 41.
上述したように、本発明のフロー検出部３０では、入力回線毎に、予め検索キー定義テーブル３１２で指定されたフロー識別条件に従って、フロー検索キーＫＥＹを生成し、フロー検出ＣＡＭ３３から上記フロー検索キーＫＥＹに一致したフローエントリを検索するようにしている。 As described above, the flow detection unit 30 of the present invention, for each input line, according to the flow identification condition designated in advance by the search key definition table 312, and generates a flow search key KEY, the flow search key from the flow detection CAM33 so that to find the flow entry that matches the KEY. 従って、本発明によれば、図１１に示したように、各フロー検索キーＫＥＹが、入力回線毎に固有のヘッダ情報項目のみを組み合せた構造となるため、フロー検索キーのビット長を短縮することが可能となる。 Therefore, according to the present invention, as shown in FIG. 11, the flow search key KEY is, since a structure in which a combination of only the specific header information items for each input line, to shorten the bit length of the flow search key it becomes possible. また、フロー検索キーのビット長が短縮された結果、フロー定義ＣＡＭ３３に登録されるフローエントリのビット長も短縮され、フロー定義ＣＡＭ３３のメモリ容量を有効に利用できる。 As a result of the bit length of the flow search key is shortened, the bit length of the flow entries registered in the flow definition CAM 33 also shortened, can effectively use the memory capacity of the flow definition CAM 33.
これに対して、例えば、従来技術１のように、常に同一フォーマットの検索キーでＣＡＭをアクセスする方式を採用した場合は、上述したモード１〜モード３のようにヘッダ情報の組み合せを異にした複数種類のフロー識別条件が必要となった時、フロー検索キーとＣＡＭエントリが、個々のフロー検出では無用となる冗長なフィールドを含むことになる。 In contrast, for example, as in the prior art 1, when the always adopts a method of accessing a CAM search key of the same format were different in combination of header information as modes 1 3 described above when a plurality of types of flow identification condition is needed, the flow search key and CAM entries will contain a redundant fields to be useless in the individual flow detection.
例えば、図１０に示したモード１〜モード３の３種類のフロー検出を従来技術で実現しようとすると、入力回線番号、ＭＰＬＳ、ＥＸＰ、ＳＩＰ、ＳＰＯＲＴ、ＤＩＰ、ＤＰＯＲＴの７つのフィールドからなる検索キー・フォーマットにおいて、モード１のフロー検出では、検索キーとフローエントリのＳＩＰ、ＳＰＯＲＴ、ＤＩＰ、ＤＰＯＲＴフィールドをDon't Care値とし、モード２のフロー検出では、ＭＰＬＳ、ＥＸＰ、ＤＩＰ、ＤＰＯＲＴフィールドをDon't Care値、モード３のフロー検出では、ＭＰＬＳ、ＥＸＰ、ＳＩＰ、ＳＰＯＲＴフィールドをDon't Care値とする必要がある。 For example, in order to realize in the prior art three flow detection of modes 1 to 3 shown in FIG. 10, the input line number, MPLS, EXP, consisting SIP, SPORT, DIP, seven fields DPORT search key in format, the flow detection mode 1, the search key and the flow entry of SIP, SPORT, DIP, in a DPORT fields and Do not Care value, mode 2 of the flow detection, MPLS, EXP, DIP, Don the DPORT fields 't Care value, in the flow detection mode 3, MPLS, EXP, SIP, it is necessary to Do not Care value SPORT field.
この場合、本発明に比較して、検索キーのビット長が増大し、ＣＡＭ容量の利用率が大幅に低下することは明らかである。 In this case, compared to the present invention, the bit length increases the retrieval key, it is clear that utilization of CAM capacity is greatly reduced. また、ＣＡＭで検索可能なエントリビット幅の制約から、例えば、従来技術２のように、検索キーを前半キーと後半キーに分け、ＣＡＭを前半用フローエントリ領域と後半用フローエントリ領域に分割せざるを得なくなった場合、上述したＣＡＭ容量の利用率低下の他に、フロー処理の所要時間増加の問題が発生する。 Moreover, the restriction of searchable entries bit wide CAM, for example, as in the prior art 2, divided into the first half key and the second half and the search key, thereby dividing the CAM in the first half for flow entry area and the second half for flow entry area If you no longer help but, in addition to lowering utilization of the CAM capacity described above, the problem of the time required increase in flow processing occurs. これらの問題は、本発明を適用することによって解決される。 These problems are solved by applying the present invention.
図８に示したフロー検出部３０では、検索キー生成制御部３１３が、フロー検出モードテーブル３１１と検索キー定義テーブル３１２を使用して、入力回線毎に固有のフロー検索キーＫＥＹを生成したが、入力回線番号とフロー識別条件とが１対１の関係にある場合は、フロー検出モードテーブル３１１と検索キー定義テーブル３１２とを統合し、フロー検出モード３１１３を介在させることなく、検索キー生成制御部３１３が、入力回線番号（Ｓ２）に基づいて、統合テーブルからプロトコル識別子３１１２（Ｓ３）と検索キー要素３１２２（Ｓ６）を直接的に入手するようにしてもよい。 The flow detection unit 30 shown in FIG. 8, the search key generation controller 313, using the flow detection mode table 311 to search key definition table 312 has to generate a unique flow search key KEY for each input line, If input line number and the flow identification condition is in one-to-one relationship, integrating the flow detection mode table 311 and the search key definition table 312, without an intervening flow detection mode 3113, the search key generation controller 313, based on the input line number (S2), from the integrated table protocol identifier 3112 and (S3) the search key elements 3122 (S6) may be directly obtain. この場合、各検出キーとフロー検出ＣＡＭ３３の各フローエントリから、検出モード３３１を除外できる。 In this case, from each flow entry for each detected key and flow detection CAM 33, you can exclude detection mode 331.
図１４は、検索キー生成部３１の第２の実施例を示す。 Figure 14 shows a second embodiment of the search key generation unit 31.
本実施例は、同一入力回線上に複数種類のフロー検出モードを設定可能にしたものであり、フロー検出モードテーブル３１１が、モード識別条件テーブル３１１Ａとフロー検出モードテーブル３１１Ｂとからなることを特徴としている。 This embodiment is obtained by allowing setting a plurality of types of flow detection mode on the same input line, it is characterized in that the flow detection mode table 311 is composed of a mode identification condition table 311A ​​and the flow detection mode table 311B there.
モード識別条件テーブル３１１Ａは、例えば、図１５に示すように、入力回線番号３１１１と対応して、プロトコル識別子３１１２とモード識別条件３１１４とを示す複数のエントリ３１１Ａ−１〜３１１Ａ−ｎからなっている。 Mode identification condition table 311A, for example, as shown in FIG. 15, corresponds to the input line number 3111, has a plurality of entries 311A-1~311A-n indicating the protocol identifier 3112 and mode identification condition 3114 . ここで、モード識別条件３１１４は、入力回線番号３１１１をもつ入力回線上でフロー検出モードを特定するために必要なヘッダ情報項目を示す。 Here, mode identifying condition 3114 shows the header information items necessary to specify the flow detection mode on input line having an input line number 3111.
一方、本実施例におけるフロー検出モードテーブル３１１Ｂは、例えば、図１６に示すように、入力回線番号３１１１と対応して、モード識別条件となるヘッダ情報項目３１１５とフロー検出モード３１１３との関係を示す複数のエントリ３１１Ｂ−１〜３１１Ｂ−ｐからなっている。 On the other hand, the flow detection mode table 311B in the present embodiment, shown for example, as shown in FIG. 16, corresponds to the input line number 3111, the relationship between the header information items 3115 and flow detection mode 3113 to be mode identification condition It is made up of a plurality of entries 311B-1~311B-p. モード識別条件３１１５は、モード識別条件テーブル３１１Ａでモード識別条件３１１４として使用されたヘッダ情報項目と対応する複数の項目、この例では、入力論理回線番号３１１５−１とフローラベル３１１５−２の値を示している。 Mode identification conditions 3115, a plurality of items corresponding to the header information items that are used as the mode identification condition 3114 in mode identification condition table 311A, in this example, the value of the input logical line numbers 3115-1 and flow label 3115-2 shows. マーク＊は、モード識別条件から除外されるマスク項目またはDon't Care値を意味している。 Mark * means a mask item or Do not Care value is excluded from the mode identification condition.
検索キー生成制御部３１３は、ヘッダ情報レジスタ３１０から入力回線番号５７１（信号線Ｓ１）を読み出し、モード識別条件テーブル３１１Ａから、上記入力回線番号（信号線Ｓ２）と対応するエントリのプロトコル識別子３１１２（信号線Ｓ３）とモード識別条件３１１４（信号線Ｓ１０）を読み出す。 Search key generation controller 313 reads the input line number 571 from the header information register 310 (signal line S1), the mode from the identification condition table 311A, the input line number (signal line S2) and the corresponding entry protocol identifier 3112 ( signal line S3) a mode identification condition 3114 reads the (signal lines S10).
ここで、例えば、ヘッダ情報レジスタ３１０から読み出した入力回線番号５７１の値が「回線番号２」であったと仮定すると、モード識別条件テーブル３１１Ａからは、モード識別条件３１１４として、エントリ３１１Ａ−２が示す「入力論理回線番号」が読み出される。 Here, for example, the value of the input line number 571 read from the header information register 310 is assumed to have been "line number 2", from the mode identification condition table 311A, as the mode identification condition 3114 shows entries 311A-2 "input logical line number" is read out. この場合、検索キー生成制御部３１３は、ヘッダ情報レジスタ３１０から内部ヘッダ３５６の入力論理回線番号５６２の値を抽出し、「回線番号２」と上記入力論理回線番号５６２の値をキー（信号線Ｓ１１）として、フロー検出モードテーブル３１１Ｂからフロー検出モード３１１３（信号線Ｓ４）を読み出す。 In this case, the search key generation controller 313 extracts the value of the input logical line number 562 of the internal header 356 from the header information register 310, a "line number 2" the value of the input logical line number 562 key (the signal line as S11), it reads the flow detection mode 3113 (signal line S4) from the flow detection mode table 311B. 上記入力論理回線番号５６２の値が「論理回線１」であれば、フロー検出モードは「モード３」となり、「論理回線２」であれば、フロー検出モードは「モード２」となる。 If the value of the input logical line number 562 is "logical line 1", the flow detection mode "Mode 3", and if "logical line 2", the flow detection mode is "mode 2".
検索キー生成制御部３１３は、図８で説明した第１実施例と同様、上記検出モード３１１３（信号線Ｓ５）に従って検索キー定義テーブル３１２を参照し、検出モード３１１３と対応する検索キー要素３１１２（信号線Ｓ６）を読み出し、ヘッダ情報レジスタ３１０から、上記検索キー要素３１１２で指定された項目のヘッダ情報（信号線Ｓ７）を読み出して、これらのヘッダ情報を含むフロー検索キーＫＥＹを生成する。 Search key generation controller 313, as in the first embodiment described in FIG. 8, the detection mode refers to the search key definition table 312 in accordance with 3113 (signal lines S5), corresponding to the detection mode 3113 search key elements 3112 ( signal line S6) reads, from the header information register 310, reads the header information of the item specified by the retrieval key element 3112 (signal line S7), and generates a flow search key kEY that contain these header information.
本実施例によれば、図１６に示したフロー検出モードテーブル３１１Ｂの内容から明らかなように、同一の入力回線上に多重化された複数のフローに対して選択的にフロー検出モードを指定し、同一入力回線上に異なった複数種類のフロー識別条件を適用することが可能となる。 According to this embodiment, as is clear from the contents of the flow detection mode table 311B shown in FIG. 16, selectively specify the flow detection mode for multiplexed plurality of flows on the same input line , it is possible to apply a plurality of types of flow identification condition differently on the same input line.
図１７は、フロー検出キー生成部３１の第３の実施例を示す。 Figure 17 shows a third embodiment of a flow detector key generator 31.
本実施例では、第２実施例におけるフロー検出モードテーブル３１１Ｂの検索にＣＡＭを適用することによって、検索キーＫＥＹの生成に要する時間を短縮したことを特徴としている。 In this embodiment, by applying the CAM to search the flow detection mode table 311B in the second embodiment is characterized in that to shorten the time required for generation of the search key KEY. 本実施例の検索キー生成制御部３１は、図１４に示したモード識別条件テーブル３１１Ａとフロー検出モードテーブル３１１Ｂに代えて、プロトコル識別子テーブル３１１Ｃと、ＣＡＭ制御部３１４と、検出モード定義ＣＡＭ３１５と、検出モード保持テーブル３１１Ｄとを備えている。 Search key generation controller 31 of the present embodiment, instead of the mode identification condition table 311A ​​and the flow detection mode table 311B shown in FIG. 14, and the protocol identifier table 311C, the CAM control unit 314, a detection mode define CAM315, and a detection mode holding table 311D.
プロトコル識別子テーブル３１１Ｃは、例えば、図１５に示したモード識別条件テーブル３１１Ａにおける入力回線番号３１１１とプロトコル識別子３１１２との関係を示している。 Protocol identifier table 311C, for example, shows a relationship between the input line number 3111 and the protocol identifier 3112 in mode identification condition table 311A ​​shown in FIG. 15. また、検出モード定義ＣＡＭ３１５は、例えば、図１６に示したフロー検出モードテーブル３１１Ｂにおける入力回線番号３１１１とモード識別条件３１１５（３１１５−１、３１１５−２）との関係を示す複数のエントリからなり、検出モード保持テーブル３１１Ｄには、上記検出モード定義ＣＡＭ３１５のエントリアドレスと対応して、上記フロー検出モードテーブル３１１Ｂにおける検出モード３１１３の値が格納されている。 The detection mode definition CAM315, for example, a plurality of entries indicating a relationship between the input line number 3111 and mode identification condition 3115 (3115-1,3115-2) in the flow detection mode table 311B shown in FIG. 16, the detection mode holding table 311D, in correspondence with the entry address of the detection mode define CAM315, the value of the detection mode 3113 in the flow detection mode table 311B is stored.
検索キー生成制御部３１３は、ヘッダ情報レジスタ３１０から入力回線番号５７１（信号線Ｓ１）を読み出し、プロトコル識別子テーブル３１１Ｃから、上記入力回線番号（信号線Ｓ２）と対応するプロトコル識別子３１１２（信号線Ｓ３）を読み出す。 Search key generation controller 313 reads the input line number 571 from the header information register 310 (signal line S1), the protocol from the identifier table 311C, the protocol identifier 3112 corresponding to the input line number (signal line S2) (signal line S3 ) read out.
本実施例では、検索キー生成制御部３１３は、入力回線番号には関係なく、ヘッダ情報レジスタ３１０から、上記検出モード定義ＣＡＭ３１５でモード識別条件３１１５として指定されている入力論理回線番号５６２とフローラベル５３２の値（信号線Ｓ７）を読み出し、図１８に示すように、入力回線番号５７１と入力論理回線番号５６２とフローラベル５３２とからなる検索キーＫＹを生成し、これをＣＡＭ制御部３１４に与える。 In this embodiment, the search key generation controller 313, regardless of the input line number, the header information from the register 310, the detection mode definition inputs logical line number 562 and flow label specified as the mode identification condition 3115 in CAM315 It reads the 532 values ​​(signal line S7), as shown in FIG. 18, and generates a search key KY comprising the input line number 571 input logical line number 562 and the flow label 532 to be provided to the CAM control unit 314 .
ＣＡＭ制御部３１４は、上記検索キーＫＹによって検出モード定義ＣＡＭ３１５をアクセスする。 CAM control unit 314 accesses the detection mode defined CAM315 by the search key KY. この結果、検出モード定義ＣＡＭ３１５から信号線Ｓ１２に、上記検索キーＫＹに一致した内容をもつ最初に見つかったエントリのアドレスが出力され、検出モード保持テーブル３１１Ｄから信号線Ｓ４に、上記ＣＡＭ出力アドレスと対応する検出モードの値が読み出される。 As a result, the signal line-S12 detection mode define CAM315, address of the first occurrence of entry with contents that match the search key KY is output to the signal line to S4 detection mode holding table 311D, and the CAM output address the value of the corresponding detection mode is read.
検索キー生成制御部３１３は、図８、図１４で説明した実施例と同様、上記検出モード（信号線Ｓ５）に従って検索キー定義テーブル３１２を参照し、検出モード３１１３と対応する検索キー要素３１１２（信号線Ｓ６）を読み出し、ヘッダ情報レジスタ３１０から、上記検索キー要素３１１２で指定されたヘッダ情報項目の値（信号線Ｓ７）を読み出して、これらのヘッダ情報項目を含むフロー検索キーＫＥＹを生成する。 Search key generation controller 313, FIG. 8, similarly to the embodiment explained in FIG. 14, the reference to the search key definition table 312 according to the detection mode (signal lines S5), corresponding to the detection mode 3113 search key elements 3112 ( signal line S6) reads, from the header information register 310, reads the search key elements 3112 header information item values ​​specified in (a signal line S7), and generates a flow search key kEY that contain these header information item .
本実施例によれば、入力回線上の複数のフローに対して、例えば、図１６のエントリ３１１Ｂ−１や３１１Ｂ−ｐが示すように、同一の検出モード（同じヘッダ情報項目の組み合せ）でフロー識別条件を設定した場合でも、あるいは、図１６のエントリ３１１Ｂ−２、３１１Ｂ−３が示すように、入力論理回線番号やフローラベルなどの特定ヘッダ情報項目の値に応じて異なる検出モード（異なるヘッダ情報項目の組み合せ）でフロー識別条件を設定した場合でも、入力回線番号とモード識別条件となり得る数種類のヘッダ情報項目を利用して、フロー検出モードを迅速に特定し、フロー定義ＣＡＭ３３のアクセスに必要な検索キーＫＥＹを短時間で生成することが可能となる。 According to this embodiment, the flow to a plurality of flows on the input line, for example, as indicated by the entry 311B-1 and 311B-p in FIG. 16, in the same detection mode (a combination of the same header information items) even if you set the identification condition, or, as indicated by the entry 311B-2,311B-3 of Figure 16, different detection modes (different headers depending on the value of the specific header information items such as the input logical line numbers or the flow label even if you set the flow identification condition information combinations of items), utilizing several types of header information items that can be the input line number and the mode identification criteria, and quickly identify the flow detection mode, required to access the flow definition CAM33 it is possible to generate in a short period of time Do not search key kEY.
以上の実施例から明らかなように、本発明によれば、フロー識別条件に応じて異なったフォーマットの検索キーを生成することによって、フロー識別条件が多様化した場合でも、検索キーのビット長を短縮できる。 As apparent from the above examples, according to the present invention, by generating a search key different formats depending on the flow identification condition, even when the flow identification condition is diversified, the bit length of the search key It can be shortened. 従って、本発明によれば、検索キーと対応関係にあるフローエントリのビット長も短縮することができ、フロー検出用のＣＡＭ容量の有効利用と、多様化されたフロー識別条件下での高速フロー検出を実現できる。 Therefore, according to the present invention, the bit length of the flow entry in the search key on the corresponding relationship can also be shortened, high-speed flow of the effective use of CAM capacity for flow detection in diversified flow identification conditions detection can be realized.
【図１】本発明によるパケット転送装置の１実施例を示すブロック図。 Block diagram illustrating one embodiment of a packet transfer apparatus according to the invention; FIG.
【図２】ＣＡＭを利用したフロー検出システムの概略的な構成を示す図。 FIG. 2 shows a schematic configuration of a flow detection system utilizing the CAM.
【図３】ＣＡＭを利用した従来技術１によるフロー検出を説明するための図。 Diagram for explaining the flow detection according to Figure 3 prior to use of the CAM technology 1.
【図４】ＣＡＭを利用した従来技術２によるフロー検出を説明するための図。 Diagram for explaining the flow detection according to Figure 4 prior art utilizing CAM technology 2.
【図５】本発明によるパケット転送装置が適用される通信ネットワークの１例を示す図。 View showing an example of a communication network [5] The packet transfer apparatus according to the present invention is applied.
【図６】図５に示したエッジルータ２０１に入力されるパケット（Ａ、Ｂ）と、エッジルータで生成される内部ヘッダ（Ｃ）のフォーマットの１例を示す図。 6 shows Figure 5 in is input to the edge router 201 showing packet (A, B) and, an example of the format of the internal header (C) generated by the edge router.
【図７】図１に示した入力回線インタフェース１１−ｉと制御部１５の詳細を示すブロック構成図。 [7] input line interface 11-i and the block diagram showing details of a control unit 15 shown in FIG.
【図８】図７に示した検索キー生成部３１の第１の実施例とフロー処理部４０の詳細を示す図。 [Figure 8] Figure 1 showing the details of the embodiments and the flow processing unit 40 of the search key generation unit 31 shown in FIG.
【図９】図８に示したフロー検出モードテーブル３１１の内容の１例を示す図。 9 is a diagram showing an example of the contents of the flow detection mode table 311 shown in FIG.
【図１０】図８に示した検索キー定義テーブル３１２の内容の１例を示す図。 10 is a view showing an example of the contents of the search key definition table 312 shown in FIG.
【図１１】図８に示した検索キー生成部３１から出力されるフロー検索キーＫＥＹの１例を示す図。 11 is a view showing an example of a flow search key KEY that is output from the search key generation unit 31 shown in FIG.
【図１２】図８に示したフロー検出ＣＡＭ３３の内容の１例を示す図。 12 is a diagram showing an example of the contents of the flow detection CAM33 shown in FIG.
【図１３】図８に示した検索結果保持テーブル４２の内容の１例を示す図。 13 is a view showing an example of content of the search result holding table 42 shown in FIG.
【図１４】検索キー生成部３１の第２の実施例を示す図。 14 illustrates a second embodiment of the search key generation unit 31.
【図１５】図１４に示したモード識別条件テーブル３１１Ａの内容の１例を示す図。 FIG. 15 is a diagram showing an example of contents of the mode identification condition table 311A ​​shown in FIG. 14.
【図１６】図１４に示したフロー検出モードテーブル３１１Ｂの内容の１例を示す図。 FIG. 16 is a diagram showing an example of the contents of the flow detection mode table 311B shown in FIG. 14.
【図１７】検索キー生成部３１の第３の実施例を示す図。 17 illustrates a third embodiment of the search key generation unit 31.
【図１８】図１７に示した検索キー生成制御部３１３からＣＡＭ制御部３１４に与えられるＣＡＭ検索キーＫＹの１例を示す図。 FIG. 18 is a diagram showing an example of a given CAM search key KY in the CAM control unit 314 from the search key generation controller 313 shown in FIG. 17.
１０：パケット転送装置（ルータ）、１１：入力回線インタフェース、 10: packet transfer device (router), 11: input line interface,
１２：出力回線インタフェース、１３：出力バッファ、１４：パケット中継部、 12: output line interface, 13: Output buffer 14: the packet relay unit,
１５：制御部、１６：多重化回路、１７、１８：振り分け回路、 15: control unit, 16: multiplexing circuit, 17, 18: distribution circuit,
２０：ルーティング処理部、３０：フロー検出部、３１：検索キー生成部、 20: routing processing unit, 30: flow detection unit, 31: search key generation unit,
３２：ＣＡＭ制御部、３３：フロー検索ＣＡＭ、３１０：ヘッダ情報レジスタ、 32: CAM control unit, 33: flow search CAM, 310: header information register,
３１１：フロー検出モードテーブル、３１２：検索キー定義テーブル、 311: flow detection mode table, 312: search key definition table,
４０：フロー制御指示部、４１：テーブル制御部、４２：検索結果保持テーブル。 40: flow control instruction unit, 41: table control unit, 42: search result storage table.
複数の入、出力回線に接続され、各入力回線から受信したパケットをヘッダ情報によって特定される何れかの出力回線に転送するパケット転送装置であって、 A plurality of input connected to an output line, a packet transfer apparatus for transferring to one of the output lines specified by the header information received packet from each input line,
各受信パケットのヘッダ情報から該パケットが属するパケットフローを識別するためのフロー検出部と、 A flow detection unit for identifying a packet flow to which the packet belongs from the header information of each received packet,
各受信パケットに対して予めパケットフロー毎に指定された転送制御を実施するための手段とを有し、 And means for implementing been transferred control specified in advance for each packet flow for each received packet,
上記フロー検出部が、複数のフロー定義エントリを有するフロー検出ＣＡＭ（Content Addressable Memory）と、フロー識別条件によって異なるフォーマットの検索キーを生成する検索キー生成部とを備え、 The flow detection unit is provided with a flow detection CAM having a plurality of flow definition entry (Content Addressable Memory), and a search key generating unit for generating a search key in different formats by flow identification condition,
上記ＣＡＭの各フロー定義エントリが、上記検索キー生成部で生成される検索キーの情報項目数と同数のフィールドからなり、同一のフィールドに、上記検索キー生成部で生成される検索キーフォーマットに応じて種類が異なる情報項目が登録されており、 Each flow definition entry in the CAM is made from the information items as many fields of search keys generated by the search key generation unit, in the same field, according to the search key format generated by the search key generation unit type Te is different information items are registered,
上記フロー検出部が、上記ＣＡＭをパケットヘッダから抽出された少なくとも１つのヘッダ情報項目を含む可変フォーマットの検索キーでアクセスして、フロー検出することを特徴とするパケット転送装置。 The flow detection unit may access a search key variable format including at least one of the header information items extracted the CAM from the packet header, the packet transfer device, characterized in that the flow detection.
各受信パケットのヘッダ情報から該パケットが属するパケットフローを識別し、受信パケットに対して実施すべき転送制御を決定する制御装置と、 A controller identifies a packet flow to which the packet belongs from the header information of each received packet, determines a transfer control to be performed on the received packet,
各受信パケットに対して上記制御装置で決定した転送制御を実施するための手段とを有し、 And means for performing the transfer control determined by the control device for each received packet,
上記制御装置が、複数のフロー定義エントリを有するフロー検出ＣＡＭ（Content Addressable Memory）と、フロー識別条件によって異なるフォーマットの検索キーを生成する検索キー生成部とからなるフロー検出部を備え、 The control device comprises a flow detection CAM having a plurality of flow definition entry (Content Addressable Memory), a flow detector comprising a search key generation unit for generating a search key in different formats by flow identification condition,
前記制御装置が、前記フロー検出ＣＡＭの各フロー定義エントリのアドレスと対応して、受信パケットに対して実施すべき転送制御内容を示す検索結果保持テーブルを有し、上記ＣＡＭからフロー検出結果として出力されるフロー定義エントリのアドレスに従って、上記検索結果保持テーブルから受信パケットに対して実施すべき転送制御内容を読み出すようにしたことを特徴とする請求項２に記載のパケット転送装置。 Wherein the controller, in response to the address of each flow definition entry in said flow detection CAM, has a search result storage table showing the transfer control content to be performed on the received packet, the output as a flow detection result from the CAM according to the address of the flow definition entries, the packet transfer apparatus according to claim 2, characterized in that it has to read out the transfer control content to be performed on the packet received from the search results holding table.
前記検索キー生成部が、前記各入力回線の識別子と対応してフロー識別条件となるヘッダ情報項目を指定した検索キー定義テーブルを備え、各受信パケットの入力回線の識別子に基づいて上記検索キー定義テーブルを参照し、該テーブルで指定されたヘッダ情報項目を含む検索キーを生成することを特徴とする請求項１〜請求項３の何れかに記載のパケット転送装置。 The search key generation unit includes the search key definition table specifies an identifier and header information items to be flow identification condition corresponding to each input line, the search key defined on the basis of the identifier of the input line of each received packet Referring to the table, the packet transfer device according to any one of claims 1 to 3, characterized in that to generate the search key including the header information items specified in the table.
前記検索キー生成部が、前記各入力回線の識別子とフロー検出モードとの対応関係を示すフロー検出モードテーブルと、上記フロー検出モードテーブルが示す各フロー検出モードと対応してフロー識別条件となるヘッダ情報項目を指定した検索キー定義テーブルを備え、 The search key generating unit, a response and the flow detection mode table indicating the relationship, the flow identification condition correspond to each flow detection mode indicated by the flow detection mode table between identifiers and flow detection mode of the respective input line header with a search key definition table by specifying the information item,
上記検索キー生成部が、上記フロー検出モードテーブルを参照して各受信パケットのフロー検出モードを特定し、上記検索キー定義テーブルが示す上記特定フロー検出モードのフロー識別条件に従って、前記検索キーを生成することを特徴とする請求項１〜請求項３の何れかに記載のパケット転送装置。 The search key generation unit, with reference to the flow detection mode table identifies the flow detection mode for each received packet, according to the flow identification condition of the specific flow detection mode indicated by the search key definition table, generates the search key the packet transfer device according to any one of claims 1 to 3, characterized in that.
前記検索キー生成部が、前記各入力回線の識別子とモード識別条件との対応関係を示すモード識別条件テーブルと、前記各入力回線の識別子とモード識別条件とフロー検出モードとの対応関係を示す検出モードテーブルと、上記フロー検出モードテーブルが示す各フロー検出モードと対応してフロー識別条件となるヘッダ情報項目を指定した検索キー定義テーブルを備え、 The search key generation unit, wherein the corresponding relationship between the mode identification condition shown table between identifiers and mode identification condition of each input line, detection indicating the correspondence between the identifier and the mode identification condition and the flow detection mode for each input line comprising a mode table, the search key definition table specifies the header information items to be flow identification condition correspond to each flow detection mode indicated by the flow detection mode table,
上記検索キー生成部が、各受信パケットの入力回線の識別子と上記モード識別条件テーブルで指定されたモード識別条件に従って、上記フロー検出モードテーブルから各受信パケットのフロー検出モードを特定し、上記検索キー定義テーブルが示す上記特定フロー検出モードのフロー識別条件に従って、前記検索キーを生成することを特徴とする請求項１〜請求項３の何れかに記載のパケット転送装置。 The search key generation unit according to the identifier and the mode identification condition table is the mode identification condition specified in the input line of each received packet to identify the flow detection mode for each received packet from the flow detection mode table, the search key according to the above flow identification condition of a specific flow detection mode indicated by the definition table, the packet transfer device according to any one of claims 1 to 3, characterized in that to generate the search key.
前記各受信パケットのヘッダ情報が、前記各入力回線に接続された入力回線インタフェースで生成された内部ヘッダ情報を含み、該内部ヘッダ情報が入力回線識別子と出力回線識別子とを含むことを特徴とする請求項１〜請求項６の何れかに記載のパケット転送装置。 It said header information of each received packet comprises said internal header information generated by the input line interface connected to the input line, characterized in that the internal header information includes an input line identifier and the output line identifier the packet transfer device according to any one of claims 1 to 6.
複数のフロー定義エントリを有するフロー検出ＣＡＭ（Content Addressable Memory）と、フロー識別条件によって異なるフォーマットの検索キーを生成する検索キー生成部と、上記ＣＡＭの各フロー定義エントリのアドレスと対応してフロー検索結果を保持するテーブルとを備え、 The flow detection CAM having a plurality of flow definition entry (Content Addressable Memory), flow searched corresponding with the retrieval key generation unit for generating a search key in different formats by flow identification condition, the address of each flow definition entry in the CAM and a table for holding a result,
上記ＣＡＭをパケットヘッダから抽出された少なくとも１つのヘッダ情報項目を含む可変フォーマットの検索キーでアクセスし、上記ＣＡＭから出力される上記検索キーに一致したフロー定義エントリのアドレスに従って、上記テーブルからフロー検索結果を得るようにしたことを特徴とするフロー検出装置。 Accessed variable format search key comprising at least one of the header information items extracted the CAM from the packet header, in accordance with the address of the flow definition entry that matches the above search key output from the CAM, flow retrieval from the table flow detection device being characterized in that to obtain the results.
前記フロー検出ＣＡＭが、前記検索キーのフォーマットと対応した複数のテーブル領域からなり、上記テーブル領域毎に、フロー識別条件となるヘッダ情報項目の値を含む複数のフロー定義エントリを有し、前記検索キーに一致した最初のフロー定義エントリのアドレスを出力することを特徴とする請求項８に記載のフロー検出装置。 The flow detection CAM is a plurality of tables areas corresponding to the format of the search key, for each of the table area comprises a plurality of flow definition entry containing the value of the header information items to be flow identification condition, the search flow detection device according to claim 8, characterized in that outputs the address of the first flow definition entry that matches the key.
JP2002105362A 2002-04-08 2002-04-08 Flow detection device and a packet transfer device including a flow detection function Active JP3936883B2 (en)
US10/215,846 US7286535B2 (en) 2002-04-08 2002-08-12 Device for flow classifying and packet forwarding device with flow classify function
US11/898,905 US7773600B2 (en) 2002-04-08 2007-09-17 Device for flow classifying and packet forwarding device with flow classify function
JP2003304278A JP2003304278A (en) 2003-10-24
JP3936883B2 true JP3936883B2 (en) 2007-06-27
JP2002105362A Active JP3936883B2 (en) 2002-04-08 2002-04-08 Flow detection device and a packet transfer device including a flow detection function
US9641437B2 (en) 2013-08-05 2017-05-02 Alaxala Networks Corporation Packet relay device and packet relay method
US20180167318A1 (en) * 2016-12-13 2018-06-14 Oracle International Corporation System and method for providing partitions of classification resources in a network device
2002-04-08 JP JP2002105362A patent/JP3936883B2/en active Active
2002-08-12 US US10/215,846 patent/US7286535B2/en active Active
2007-09-17 US US11/898,905 patent/US7773600B2/en active Active
US7286535B2 (en) 2007-10-23
US20030189932A1 (en) 2003-10-09
US20080037546A1 (en) 2008-02-14
JP2003304278A (en) 2003-10-24
US7773600B2 (en) 2010-08-10