(57)【要約】【課題】IPルックアップ処理の高速化を実現すること。【解決手段】通信装置が、パケットを受信する受信手段と、ネクストホップに関する情報と、Multiway Trieで経路表を表現した場合における次の階層に関する情報とがそれぞれ含まれる複数の配列要素で構成される配列を用いて、SIMD演算を用いたロンゲストマッチにより、前記受信手段が受信した複数のパケットの宛先アドレスのネクストホップに関する情報を前記配列から並列に取得するルックアップ処理手段と、前記ルックアップ処理手段が取得した複数のネクストホップに関する情報のそれぞれに従って、前記受信手段が受信した複数のパケットのそれぞれを送信する送信手段と、を有することを特徴とする。【選択図】図１
2020156058.tif 000002
【特許請求の範囲】
【請求項１】
パケットを受信する受信手段と、
ネクストホップに関する情報と、Multiway Trieで経路表を表現した場合における次の階層に関する情報とがそれぞれ含まれる複数の配列要素で構成される配列を用いて、SIMD演算を用いたロンゲストマッチにより、前記受信手段が受信した複数のパケットの宛先アドレスのネクストホップに関する情報を前記配列から並列に取得するルックアップ処理手段と、
前記ルックアップ処理手段が取得した複数のネクストホップに関する情報のそれぞれに従って、前記受信手段が受信した複数のパケットのそれぞれを送信する送信手段と、
を有することを特徴とする通信装置。
【請求項２】
前記配列は、最適化として、前記ネクストホップに関する情報が下位の階層に予め展開されていること、及び、同一のネクストホップに関する情報が含まれる上位の配列要素が存在する場合に下位の配列要素が削除されていること、の少なくも一方が行われていることを特徴とする請求項１に記載の通信装置。
【請求項３】
前記ルックアップ処理手段は、
Multiway Trieで表現された前記経路表の階層毎に、該階層に応じて、前記複数のパケットからそれぞれ取得された複数の宛先アドレスから所定の長さのビット列をそれぞれ抽出し、抽出した複数のビット列と前記階層を構成する配列要素とをマッチングし、マッチングした配列要素に含まれるネクストホップに関する情報と次の階層に関する情報とを取得することを繰り返す、ことを特徴とする請求項１又は２に記載の通信装置。
【請求項４】
前記宛先アドレスはIPv4アドレスであり、
前記ルックアップ処理手段は、
前記マッチングの対象となる配列要素で構成される階層が第１階層目である場合、前記複数の宛先アドレスの先頭から16ビット長のビット列をそれぞれ抽出し、抽出した複数のビット列と前記階層を構成する配列要素とをマッチングし、マッチングした配列要素に含まれるネクストホップに関する情報と次の階層に関する情報とを取得し、
前記マッチングの対象となる配列要素で構成される階層が第２階層目以降である場合、前記階層毎に、前記複数の宛先アドレスの未抽出部分の先頭から8ビット長のビット列をそれぞれ抽出し、抽出した複数のビット列と前記階層を構成する配列要素とをマッチングし、マッチングした配列要素に含まれるネクストホップに関する情報と次の階層に関する情報とを取得することを繰り返す、ことを特徴とする請求項３に記載の通信装置。
【請求項５】
前記宛先アドレスがIPv6アドレスである場合、前記ルックアップ処理手段により取得された次の階層に関する情報が所定の値となるまで、32ビット毎に、前記宛先アドレスからビット列を抽出する抽出手段を有し、
前記ルックアップ処理手段は、
前記抽出手段が抽出したビット列をIPv4アドレスの宛先アドレスと見做して、SIMD演算を用いたロンゲストマッチにより、前記宛先アドレスのネクストホップに関する情報と前記次の階層に関する情報とを前記配列から並列に取得することを繰り返す、こと特徴とする請求項４に記載の通信装置。
【請求項６】
前記ルックアップ処理手段は、
前記SIMD演算を用いたロンゲストマッチにより前記ネクストホップに関する情報が並列に取得される宛先アドレスの個数をN、パイプライン処理による並列実行数をMとして、前記パイプライン処理により、N×M個の宛先アドレスのネクストホップに関する情報を同時に取得する、ことを特徴とする請求項１乃至５の何れか一項に記載の通信装置。
【請求項７】
パケットを受信する受信手順と、
ネクストホップに関する情報と、Multiway Trieで経路表を表現した場合における次の階層に関する情報とがそれぞれ含まれる複数の配列要素で構成される配列を用いて、SIMD演算を用いたロンゲストマッチにより、前記受信手順で受信した複数のパケットの宛先アドレスのネクストホップに関する情報を前記配列から並列に取得するルックアップ処理手順と、
前記ルックアップ処理手順で取得した複数のネクストホップに関する情報のそれぞれに従って、前記受信手順で受信した複数のパケットのそれぞれを送信する送信手順と、
をコンピュータが実行することを特徴とする通信方法。
【請求項８】
パケットを受信する受信手順と、
ネクストホップに関する情報と、Multiway Trieで経路表を表現した場合における次の階層に関する情報とがそれぞれ含まれる複数の配列要素で構成される配列を用いて、SIMD演算を用いたロンゲストマッチにより、前記受信手順で受信した複数のパケットの宛先アドレスのネクストホップに関する情報を前記配列から並列に取得するルックアップ処理手順と、
前記ルックアップ処理手順で取得した複数のネクストホップに関する情報のそれぞれに従って、前記受信手順で受信した複数のパケットのそれぞれを送信する送信手順と、
をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信装置、通信方法及びプログラムに関する。
【背景技術】
【０００２】
IPv4(Internet Protocol version 4) / IPv6(Internet Protocol Version 6)の通信において、通信経路上のノードがパケットの宛先アドレス（つまり、宛先として設定されているIPアドレス）に応じて転送先を選択する処理はIPルックアップと呼ばれる。IPルックアップはルータ及びエンドノードにおける通信機能の核となる部分であり、ソフトウェア・ハードウェアを問わず性能向上が求められている。
【０００３】
これまでソフトウェアでIPルックアップを高速に処理する手法は複数提案されている。例えば、従来手法の1つとして、特許文献１に記載されている手法がある。
【０００４】
また、近年では、NFV(Network Functions Virtualization)の普及によって様々なネットワーク機能がソフトウェアで実現されるようになっている。NFVの機能にはルーティングのみの装置と比較して複雑な処理が求められるDPI(Deep Packet Inspection)等が含まれるため、IPルックアップの処理負荷を低減することが求められている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第５９６０８６３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、IPルックアップの処理に要する演算時間は、現在通信キャリアで用いられる伝送速度に対して充分に短いとは言えず、依然として演算時間の短縮が求められている。例えば、現在通信キャリアのネットワークでは100Gbps Ethernetが主要な伝送規格として用いられているが、ソフトウェアルータではCPU(Central Processing Unit) 1コアで100Gbps水準のトラフィックに対するIPルックアップを遅滞なく処理することは困難である。
【０００７】
なお、IPルックアップを含めたパケット処理を高速化する手法として、CPU以外にGPU(Graphics Processing Unit)やFPGA(Field-Programmable Gate Array)等を用いる手法もあるが、これらの手法ではGPUやFPGA等のハードウェアを追加する必要がある。ソフトウェアによるパケット処理は、導入コストの安い汎用サーバで実行可能であること、改変が容易であり新機能の開発コストを下げられること等が利点であるが、GPUやFPGA等の特別なハードウェアを追加することは、これらの利点を弱めてしまうことになる。
【０００８】
本発明は、上記の点に鑑みてなされたもので、IPルックアップ処理の高速化を実現することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明の実施形態に係る通信装置は、パケットを受信する受信手段と、ネクストホップに関する情報と、Multiway Trieで経路表を表現した場合における次の階層に関する情報とがそれぞれ含まれる複数の配列要素で構成される配列を用いて、SIMD演算を用いたロンゲストマッチにより、前記受信手段が受信した複数のパケットの宛先アドレスのネクストホップに関する情報を前記配列から並列に取得するルックアップ処理手段と、前記ルックアップ処理手段が取得した複数のネクストホップに関する情報のそれぞれに従って、前記受信手段が受信した複数のパケットのそれぞれを送信する送信手段と、を有することを特徴とする。
【発明の効果】
【００１０】
IPルックアップ処理の高速化を実現することができる。
【図面の簡単な説明】
【００１１】
【図１】本実施形態に係る通信装置の全体構成の一例を示す図である。
【図２】Multiway Trieによるロンゲストマッチの一例を説明するための図である。
【図３】経路表の配列展開の一例を説明するための図である。
【図４】最適化の一例を説明するための図（その1）である。
【図５】最適化の一例を説明するための図（その2）である。
【図６】本実施形態に係るIPルックアップ処理（IPv4）の一例を示すフローチャートである。
【図７】ルックアップに使用する領域の抽出（初回）の一例を説明するための図である。
【図８】最初にルックアップする配列要素のインデックスの生成の一例を説明するための図である。
【図９】配列展開した経路表からのノードの取得の一例を説明するための図である。
【図１０】inf値の抽出の一例を説明するための図である。
【図１１】jmp値の抽出の一例を説明するための図である。
【図１２】ルックアップが継続している対象のinf値の保持の一例を説明するための図である。
【図１３】ルックアップに使用する領域の抽出（2回目以降）の一例を説明するための図である。
【図１４】次にルックアップする配列要素のインデックスの生成の一例を説明するための図である。
【図１５】本実施形態に係るIPルックアップ処理（IPv6）の一例を示すフローチャートである。
【図１６】IPv6アドレスの先頭64ビットの抽出の一例を説明するための図である。
【図１７】IPv6アドレスの先頭32ビットの抽出の一例を説明するための図である。
【図１８】並べ替えの一例を説明するための図である。
【図１９】本実施形態に係る通信装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態（以降、「本実施形態」とも表す。）について説明する。本実施形態では、SIMD(Single Instruction/Multiple Data)演算を用いて複数の宛先アドレスを並列にIPルックアップすることで、IPルックアップ処理の高速化を実現する通信装置１０について説明する。
【００１３】
SIMD演算とは、単一の命令により複数のデータを同時に処理する演算のことである。SIMD演算は並列での計算を適用可能な問題では効果が大きい反面、使用可能な演算命令が限られる点や条件分岐のオーバーヘッド等が高い点等に起因して、既存のソフトウェアにそのまま適用しても性能が向上しない場合が多い。このため、本実施形態では、後述するように、IPルックアップ処理をSIMD演算で処理可能にする経路表のデータ構造とIPルックアップ処理の処理手順とを工夫することで、IPルックアップ処理の高速化を実現する。
【００１４】
ここで、本実施形態に係る通信装置１０は、IPルックアップ処理を含むパケット処理をソフトウェア（プログラム）により実現するコンピュータ（例えば汎用サーバやPC（パーソナルコンピュータ）等）であるものとする。
【００１５】
＜通信装置１０の全体構成＞
まず、本実施形態に係る通信装置１０の全体構成について、図１を参照しながら説明する。図１は、本実施形態に係る通信装置１０の全体構成の一例を示す図である。
【００１６】
図１に示すように、本実施形態に係る通信装置１０は、機能部として、受信部１０１と、ルックアップ処理部１０２と、送信部１０３とを有する。
【００１７】
受信部１０１は、他の機器や他の装置（例えば、他の通信装置１０）等から送信又は転送されたパケットを受信する。
【００１８】
ルックアップ処理部１０２は、SIMD演算を用いてIPルックアップ処理を実行する。すなわち、ルックアップ処理部１０２は、受信部１０１により受信されたパケットの宛先アドレスに応じて、経路表から転送先アドレスを選択する。ここで、転送先アドレスとは、パケットの転送先となる他の機器又は他の装置のIPアドレスのことであり、例えば、「経路情報」や「ネクストホップ」等とも称される。以降では、主に、転送先アドレスのことを経路情報と表す。
【００１９】
ここで、経路表とは、宛先ネットワーク（ネットワークアドレス）と経路情報とを対応付けた表（テーブル）のことであり、ルーティングテーブルとも称される。本実施形態では、後述するように、経路表は、配列の形式で経路情報を保持するFIB(Forwarding Information Base)である。
【００２０】
送信部１０３は、ルックアップ処理部１０２により選択された転送先に対して、受信部１０１により受信されたパケットを転送する。
【００２１】
ここで、本実施形態の全体の手順は以下の１〜３となる。
【００２２】
１．経路情報をRIB(Routing Information Base)として保持する。
【００２３】
２．RIBをFIBに変換する。このとき、FIBは配列の形式で保持する。
【００２４】
３．FIBに対するSIMD演算により、宛先アドレスに対してロンゲストマッチを行って、転送先となる経路情報を選択する（すなわち、SIMD演算を用いたIPルックアップ処理を実行する。）。
【００２５】
このうち、上記の１及び２は、IPルックアップ処理の実行前に事前に行っておく必要がある。なお、上記の１及び２は、ルックアップ処理部１０２が行ってもよいし、ルックアップ処理部１０２とは異なる他の機能部（例えば、「経路表作成部」等と称される、図示しない機能部）が行ってもよい。
【００２６】
＜１．経路情報をRIBとして保持＞
まず、経路情報をRIBとして保持する手順について説明する。本実施形態では、RIBをMultiway Trieとして保持する。Multiway Trieとは、1つの階層で2ビット以上の幅を表現するTrie木のことである。二分木で構成されるTrie（つまり、いわゆるBinary Trie）に対して、多分木で構成されるMultiway Trieは、一般的に、マッチングを行う際に木を辿る操作が少なくなるという利点がある。
【００２７】
Multiway Trieにおけるロンゲストマッチでは、以下のStep1〜Step4により経路情報を選択する。
【００２８】
Step1) Multiway Trieの該当の階層の幅に応じて宛先アドレスを切り出した上で、この切り出されたアドレスとのマッチングを行うことで、当該階層における該当のノードを得る。
【００２９】
Step2) 当該ノードが経路情報を保持していれば、その経路情報を一時保存する。
【００３０】
Step3) 当該ノードが次の階層へのポインタを保持していれば、上記のStep1に戻る。
【００３１】
Step4) そして、上記のStep1で取得したノードが次の階層へのポインタを保持していない場合、上記のステップStep2で最後に一時保存した経路情報が転送先アドレス（つまり、ロンゲストマッチの結果）となる。
【００３２】
本実施形態に係るRIBでは、Multiway Trieの1階層を1つの配列として表現する。このとき、配列の各要素（以降では、配列の要素を「配列要素」とも表す。）は、経路情報と次の階層へのポインタとを保持する。このRIBによるロンゲストマッチの一例を図２に示す。図２に示す例では、宛先ネットワーク「1.0.0.0/8」、「1.0.1.0/24」及び「192.0.2.0/24」を持つ経路表（Routing table）をRIBで表現し、宛先アドレス（Destination）「192.0.2.1」をロンゲストマッチした場合を示している。また、図２に示す例では、RIBを構成する各配列要素のtableには次の階層へのポインタ（NULLである場合も含む。）が設定され、hopには経路情報が設定されている。
【００３３】
また、本実施形態のRIB（及びFIB）では、ルックアップを高速化するため、1階層目の幅を16ビット、2階層目以降の幅を8ビットとする。図２に示す例では、Tbl0は1階層目を表現する配列（要素数：216=65536）を表すテーブルであり、Tbl1及びTbl2は2階層目に属する配列（要素数：28=256）をそれぞれ表すテーブルである。
【００３４】
1階層目の幅を16ビットとするのは、（１）実際にはプレフィックス長が8〜24ビットの経路が多くを占めるため、1階層目を8ビットとすると多くのケースで2回以上のルックアップが必要になること、（２）ルックアップでSIMD演算のバイト単位のシャッフル命令を用いているため、階層の幅を8ビット単位でしか変更できないこと、（３）1階層を24ビット幅とするとFIBのメモリ空間の使用効率が悪いこと、等を考慮したためである。ただし、これら（１）〜（３）を考慮しなければ、1階層目の幅を8ビットや24ビットとしてもよい。
【００３５】
＜２．RIBをFIBに変換＞
次に、RIBをFIBに変換する手順について説明する。本実施形態に係るFIBは、RIBとして構築したMultiway Trieを配列形式に変換する（つまり、1つの配列として配列展開する）ことで構築される。図２に示すRIBの配列展開を図３に示す。上述したように、本実施形態に係る経路表は、RIBを配列展開したFIBである。
【００３６】
原則として、FIBの各行はMultiway Trieにおける8ビット幅（256要素）の1階層を表すが、0行目は特殊用途、1〜256行目は16ビット幅（65536要素）の1階層を表す。
【００３７】
FIBを構成する各配列要素は32ビットの空間を持ち、その配列要素に対応するノードにマッチした場合の経路情報のインデックス番号を示すinf値と次の階層へのインデックス番号を示すjmp値とを保持する。したがって、FIBは、32ビットの配列要素が1行に256個並んだ2次元配列で表される。ただし、本実施形態では、この2次元配列のi行j列目の配列要素のインデックス番号をi×256+jで表し、1次元配列として扱うものとする。
【００３８】
ここで、0行目の配列要素（つまり、特殊用途の配列要素）はルックアップが終了した宛先アドレスに対して無意味なルックアップを実行するために使用され、全ての配列要素のjmp値には0が設定（つまり、jmp=0）されている。本実施形態に係るIPルックアップ処理では、SIMD演算を用いて複数の宛先アドレスを並列にルックアップするため、既にルックアップが終了した宛先アドレスに対しても全ての宛先アドレスのルックアップが終了するまで、同じルックアップを繰り返す必要がある。そして、全ての宛先アドレスがFIBの0行目に到達した時点でIPルックアップ処理が終了となる。
【００３９】
図３に示すFIBを用いて、宛先アドレス「192.0.2.1」をルックアップする場合、まず、宛先アドレスの先頭16ビットである「192.0」と、1〜256行目の配列要素とを用いてルックアップが行われ、193行0列目の配列要素がマッチすることとなる。次に、宛先アドレスの先頭から17〜24ビット目までの部分「2」と、当該配列要素のjmp値「258」に対応する258行目の配列要素とを用いてルックアップが行われ、258行2列目の配列要素がマッチすることとなる。このとき、マッチした配列要素のinf値「X」が保持される。
【００４０】
最後に、宛先アドレスの先頭から25〜32ビット目までの部分「1」と、当該配列要素のjmp値「0」に対応する0行目の配列要素とを用いてルックアップが行われ、0行目1列の配列要素がマッチすることとなり、ロンゲストマッチが終了する。これにより、最終的に保持されているinf値「X」に対応する経路情報が転送先アドレス（つまり、ロンゲストマッチの結果）となる。
【００４１】
ここで、本実施形態では、RIBをFIBに変換する際に、次の2つの最適化を行う。
【００４２】
・最適化その1：経路情報のインデックス番号（inf値）を末端ノードへ事前展開
本実施形態に係るRIBでは、1階層のマッチングを行う毎に、マッチしたノードが経路情報を保持しているか否かを確認し、一時保持していた。しかし、ノードが経路情報を保持しているか否かを確認するためには最低1回のCPU命令が必要となる。そこで、事前に、上位階層の経路情報を、下位階層の経路情報を持つノードが現れるまでの部分（つまり、ロンゲストマッチの結果が上位階層の経路情報になるノード）に再帰的に展開することで、上記の確認を行うためのCPU命令を不要とすることができる。この最適化の一例を図４に示す。
【００４３】
図４に示す例では、257行目の各配列要素のinf値として、上位ノード（2行0列目の配列要素）が保持しているinf値「X」を展開している。これにより、ルックアップ時に各ノードが経路情報を保持しているか否か（すなわち、当該ノードに対応する配列要素のinf値がNULLであるか否か）を確認又は判定する必要がなくなり、IPルックアップ処理の高速化を図ることが可能となる。
【００４４】
・最適化その2：経路集約
経路集約はよく知られた手法であり、同じネクストホップを持つ複数の経路をよりプレフィックス長の短い単一の経路として扱う手法である。この最適化の一例を図５に示す。
【００４５】
図５に示す例では、257行目の各配列要素が保持している情報は、上位ノード（2行0列目の配列要素）に集約可能であるため、削除している。これにより、FIBのサイズを縮約させることができるため、CPUキャッシュのヒット率向上が期待できる。
【００４６】
＜３．SIMD演算を用いたIPルックアップ処理＞
次に、SIMD演算を用いてIPルックアップ処理について説明する。
【００４７】
≪IPルックアップ処理（IPv4）≫
以降では、IPアドレスがIPv4である場合のIPルックアップ処理について、図６を参照しながら説明する。図６は、本実施形態に係るIPルックアップ処理（IPv4）の一例を示すフローチャートである。
【００４８】
なお、本実施形態では、一例として、SIMD拡張命令セットとしてIntel AVX2を想定し、256ビット幅のレジスタを用いた宛先アドレス8個の同時処理を実現する場合について説明する。ただし、本実施形態は、Intel AVX2以外の他のアーキテクチャに対しても同様に適用可能である。
【００４９】
また、SIMDでは同じ操作又は処理結果を実現するために複数通りの実装方法が存在する場合があるが、本実施形態では、全てIntel AVX2においてCPU命令のレイテンシが最も低くなる実装方法を採用するものとする。
【００５０】
ステップＳ１０１：ルックアップ処理部１０２は、SIMD演算命令の1つであるロード命令（例えばVMOVDQA等）によりメモリからレジスタに宛先アドレス（IPv4アドレス）を8個ロードする。これら8個の宛先アドレスは、予めメモリ上に連続に保持されているものとする。なお、これら8個の宛先アドレスの各々は、受信部１０１により受信されたパケットの宛先アドレスである。
【００５１】
ステップＳ１０２：次に、ルックアップ処理部１０２は、ルックアップに使用する領域をレジスタから抽出する。例えば、図７に示すように、レジスタにロードされた8個の宛先アドレスをDst1, Dst2, …,Dst8として、これらDst1, Dst2, …,Dst8で構成される領域をdstとする。このとき、ルックアップ処理部１０２は、SIMD演算命令の1つであるシャッフル命令（例えばVPSHUFB等）により、Dst1〜Dst8それぞれの上位16ビットを別のレジスタの32ビット領域の下位16ビットにそれぞれコピーする。以降では、Dst1〜Dst8それぞれの上位16ビットがコピーされた32ビット領域をそれぞれTgt1〜Tgt8として、これら8個のTgt1〜Tgt8で構成される領域をtgtとする。
【００５２】
なお、本実施形態では1階層目の幅を16ビットであるものとしたが、例えば1階層目の幅を8ビットとした場合には、ルックアップ処理部１０２は、Dst1〜Dst8それぞれの上位8ビットを別のレジスタの32ビット領域の下位8ビットにそれぞれコピーすればよい。同様に、例えば1階層目の幅を24ビットとした場合には、ルックアップ処理部１０２は、Dst1〜Dst8それぞれの上位24ビットを別のレジスタの32ビット領域の下位24ビットにそれぞれコピーすればよい。
【００５３】
ステップＳ１０３：次に、ルックアップ処理部１０２は、最初にルックアップする配列要素のインデックスを生成する。例えば、図８に示すように、ルックアップ処理部１０２は、上記のステップＳ１０３で得られたtgtを構成するTgt1〜Tgt8のそれぞれに対して、SIMD演算命令の1つである加算命令（VPDDD）により、256を加算する。これは、FIBで表された経路表の0行をスキップ（すなわち、インデックス番号「0」〜「255」までの配列要素をスキップ）し、次のルックアップを1〜256行目に設定（すなわち、1階層目の配列要素に設定）することに相当する。以降では、Tgt1〜Tgt8のそれぞれに256を加算した結果をIdx1〜Idx8として、これらIdx1〜Idx8で構成される領域をidxとする。この時点で、これらのIdx1〜Idx8は、Dst1〜Dst8それぞれの初回のルックアップに使用される配列要素（ノード）のインデックス番号となる。
【００５４】
ステップＳ１０４：次に、ルックアップ処理部１０２は、メモリ上の配列（つまり、配列展開された経路表）からノード（つまり、配列要素）を取得する。例えば、図９に示すように、ルックアップ処理部１０２は、SIMD演算命令の1つであるギャザー命令（例えばVPGATHERDD等）により、Idx1〜Idx8のそれぞれに格納されているインデックス番号の配列要素を経路表から取得して、レジスタに格納する。以降では、Idx1〜Idx8のそれぞれに格納されているインデックス番号の配列要素が格納された領域をVal1〜Val8として、これら8個のVal1〜Val8で構成される領域をvalとする。これにより、Val1〜Val8の各々には、経路情報のインデックス番号を示すinf値（16ビット）と、次の階層へのインデックス番号を示すjmp値（16ビット）とが格納される。なお、「jmp値×256＋次にルックアップする8ビット幅の値」が、配列展開された経路表（FIB）上で次にルックアップする配列要素のインデックス番号となる。
【００５５】
なお、従来ではギャザー命令の性能が低く、IPルックアップを始めとするテーブルルックアップ系の処理を高速に行うことが難しかったが、近年では、ギャザー命令の性能が向上し、上記のステップＳ１０４の処理をギャザー命令により高速に実行することが可能である。
【００５６】
ステップＳ１０５：次に、ルックアップ処理部１０２は、valからinf値を取得する。例えば、図１０に示すように、ルックアップ処理部１０２は、SIMD演算命令の1つであるシャッフル命令（例えばVPSHUFB等）により、Val1〜Val8それぞれの上位16ビットを別のレジスタの32ビット領域の下位16ビットにそれぞれコピーする。以降では、Val1〜Val8それぞれの上位16ビットがコピーされた32ビット領域をそれぞれInf1〜Inf8として、これら8個のInf1〜Inf8で構成される領域をinfとする。これにより、Inf1〜Inf8には、Val1〜Val8に格納されているinf値がそれぞれ格納される。
【００５７】
ステップＳ１０６：次に、ルックアップ処理部１０２は、valからjmp値を取得する。例えば、図１１に示すように、ルックアップ処理部１０２は、SIMD演算命令の1つであるシャッフル命令（例えばVPSHUFB等）により、Val1〜Val8それぞれの下位16ビットを別のレジスタの32ビット領域の下位16ビットにそれぞれコピーする。以降では、Val1〜Val8それぞれの下位16ビットがコピーされた32ビット領域をそれぞれJmp1〜Jmp8として、これら8個のJmp1〜Jmp8で構成される領域をjmpとする。これにより、Jmp1〜Jmp8には、Val1〜Val8に格納されているjmp値がそれぞれ格納される。
【００５８】
なお、上記のステップＳ１０５及びステップＳ１０６の処理順は順不同である。すなわち、ステップＳ１０６の処理が実行された後、ステップＳ１０５の処理が実行されてもよい。
【００５９】
ステップＳ１０７：次に、ルックアップ処理部１０２は、ルックアップが継続している対象（すなわち、jmp値が0でない宛先アドレス）のinf値を保持する。例えば、図１２に示すように、ルックアップ処理部１０２は、まず、SIMD演算命令の1つである比較命令（例えばVPCMPEQD等）により、jmp値が0でない対象のみを選択するマスク（msk）を作成する。すなわち、ルックアップ処理部１０２は、比較命令により、Jmp1〜Jmp8それぞれに格納されているjmp値が0であるか否かを比較することでMsk1〜Msk8をそれぞれ作成し、これらMsk1〜Msk8で構成される領域をmskとする。なお、Msk1は、例えば、Jmp1に格納されているjmp値が0である場合は全てのビット値が1の32ビット領域、Jmp1に格納されているjmp値が0でない場合は全てのビット値が0の32ビット領域である。Msk2〜Msk8についても同様である。
【００６０】
次に、ルックアップ処理部１０２は、SIMD演算命令の1つであるブレンド命令（例えばVPBLENDVB等）により、mskとjmpとからルックアップが継続している対象のinf値を別のレジスタに保持する。すなわち、ルックアップ処理部１０２は、ブレンド命令により、Msk1〜Msk8と、Inf1〜Inf8とをそれぞれ混合（ブレンド）して、その結果を32ビット領域にそれぞれ上書きする。これらの32ビット領域をそれぞれNhop1〜Nhop8として、これら8個のNhop1〜Nhop8で構成される領域をnhopとする。Nhop1〜Nhop8には、ルックアップが継続している対象のinf値が格納される。なお、混合（ブレンド）とは、2つのビット列の各要素を条件付きでコピーすることを意味する。このとき、条件としてMsk1〜Msk8の最上位ビットを用いて、Inf1〜Inf8とNhop1〜Nhop8とをそれぞれ混合して、新しいNhop1〜Nhop8とする。これにより、例えば、Msk1の最上位ビットが0の場合はInf1が新しいNhop1にコピーされ、Msk1の最上位ビットが1の場合はNhop1が新しいNhop1にコピーされる。Inf2〜Inf8及びNhop2〜Nhop8についても同様である。
【００６１】
なお、RIBをFIBに変換する際に上記の最適化その1（つまり、経路情報のインデックス番号（inf値）を末端ノードへ事前展開）を行っていることにより、Msk1〜Msk8と、Inf1〜Inf8とをそれぞれ混合（ブレンド）した結果は、常にNhop1〜Nhop8に上書き可能である。
【００６２】
ステップＳ１０８：次に、ルックアップ処理部１０２は、全てのjmp値が0であるか否かを判定する。すなわち、ルックアップ処理部１０２は、SIMD演算命令の1つであるテスト命令（例えばVPTEST等）により、jmpを構成するJmp1〜Jmp8の全てが0であるか否かを判定する。
【００６３】
上記のステップＳ１０８で全てのjmp値が0であると判定された場合、ルックアップ処理部１０２は、IPルックアップ処理を終了する。この場合、Nhop1〜Nhop8のそれぞれに格納されているinf値（つまり、経路情報のインデックス番号）が示す経路情報が、Dst1〜Dst8のそれぞれに格納された宛先アドレスのネクストホップ（転送先アドレス）となる。したがって、その後、送信部１０３により、各パケットがネクストホップに転送される。
【００６４】
一方で、ステップＳ１０８で全てのjmp値が0であると判定されなかった場合、ルックアップ処理部１０２は、ステップＳ１０９の処理に進む。
【００６５】
ステップＳ１０９：ルックアップ処理部１０２は、次のルックアップに使用する領域をレジスタから抽出する。例えば、図１３に示すように、2回目のルックアップでは、ルックアップ処理部１２０は、SIMD演算命令の1つであるシャッフル命令（例えばVPSHUFB等）により、Dst1〜Dst8それぞれの上位17ビット目〜24ビット目までの8ビットを、別のレジスタの32ビット領域の下位8ビットにコピーする。これらの32ビット領域もそれぞれTgt1〜Tgt8として、8個のTgt1〜Tgt8で構成される領域をtgtとする。なお、3回目のルックアップでは、ルックアップ処理部１２０は、SIMD演算命令の1つであるシャッフル命令により、Dst1〜Dst8それぞれの上位25ビット目〜32ビット目までの8ビットを、別のレジスタの32ビット領域の下位8ビットにコピーすればよい。
【００６６】
なお、上記のステップＳ１０２及びステップＳ１０９の処理で使用するシャッフル命令の制御マスク（つまり、dstのどのビットをtgtにコピーするかを制御するためのマスク）は、例えば、SIMD演算命令の1つである_mm256_add_epi32()で加算することにより更新する。
【００６７】
ステップＳ１１０：次に、ルックアップ処理部１０２は、次にルックアップする配列要素のインデックスを生成する。例えば、図１４に示すように、ルックアップ処理部１０２は、現在のjmpのJmp1〜Jmp8のそれぞれを1バイト（8ビット）左にシフトした上で、SIMD演算命令の1つであるOR演算命令（例えばVPOR等）により、tgtとOR演算を実行する。これは、Jmp1〜Jmp8のそれぞれに格納されているjmp値を256倍した上で、Tgt1〜Tgt8のそれぞれとOR演算を行うことを意味する。これらのOR演算の結果が格納される32ビット領域もそれぞれIdx1〜Idx8として、これらIdx1〜Idx8で構成される領域をidxとする。これらのIdx1〜Idx8は、Dst1〜Dst8それぞれの次のルックアップに使用される配列要素（ノード）のインデックス番号となる。
【００６８】
そして、ルックアップ処理部１０２は、ステップＳ１０４の処理に戻る。これにより、上記のIndを用いて、ステップＳ１０４以降の処理（つまり、各宛先アドレスの次の8ビット部分のルックアップ）が実行される。すなわち、上記のステップＳ１０４〜ステップＳ１１０の処理は、各宛先アドレスに含まれる所定の8ビット部分毎に繰り返し実行される。
【００６９】
なお、本実施形態では、8個の宛先アドレスを並列にルックアップするIPルックアップ処理を説明したが、パイプライン処理を利用することで、複数のIPルックアップ処理を並列に実行することもできる。例えば、IPルックアップ処理を2回分のループアンロールで実装することで、パイプライン処理により、16個の宛先アドレスを同時にルックアップすることが可能となる（ただし、パイプライン処理内では逐次的に処理が実行されるため、厳密には同時ではなく、逐次的なルックアップになる。）。同様に、3回以上のループアンロールで実装することも可能である。
【００７０】
また、本実施形態では、通信キャリアのネットワーク上に通信装置１０が設置されており、8個の宛先アドレス毎に、IPルックアップ処理を繰り返し実行することを想定しているが、本実施形態に係る通信装置１０は、例えば比較的低速なネットワーク上に設置することも可能である。比較的低速ネットワーク上ではIPルックアップ処理の実行を開始する際に、宛先アドレスが8個存在しない場合も有り得る。このような場合には、例えば、全てが0の32ビット長のビット列を宛先アドレスと見做して、この宛先アドレスを１以上含む8個の宛先アドレスに対してIPルックアップ処理を実行すればよい。
【００７１】
≪IPルックアップ処理（IPv6）≫
以降では、IPアドレスがIPv6である場合のIPルックアップ処理について、図１５を参照しながら説明する。図１５は、本実施形態に係るIPルックアップ処理（IPv6）の一例を示すフローチャートである。
【００７２】
IPv4アドレスのビット長が32ビットであるのに対してIPv6アドレスのビット長は128ビットであるため、IPルックアップ処理（IPv6）では、IPv6アドレス8個をそれぞれ先頭から32ビットずつ切り出した上で、IPルックアップ処理（IPv4）と同様の処理を行う。そして、32ビット分のルックアップが終了した時点で、ルックアップが継続している宛先アドレスがあれば、次の32ビットを切り出すことを繰り返す。また、ルックアップ終了後、ルックアップ結果（つまり、ネクストホップを示すinf値）の順序と宛先アドレスの順序とが一致しないため、ルックアップ結果の並べ替えを行う。
【００７３】
ステップＳ２０１：ルックアップ処理部１０２は、SIMD演算命令の1つであるロード命令（例えばVMOVDQA等）によりメモリからレジスタに宛先アドレス（IPv6アドレス）を2個ずつ合計8個ロードする。これら8個の宛先アドレスは、予めメモリ上に連続に保持されているものとする。なお、これら8個の宛先アドレスの各々は、受信部１０１により受信されたパケットの宛先アドレスである。
【００７４】
ステップＳ２０２：次に、ルックアップ処理部１０２は、4個の宛先アドレス（IPv6）の先頭64ビットを抽出する。例えば、図１６に示すように、宛先アドレスをDst1, Dst2, …,Dst8として、Dst1及びDst2、Dst3及びDst4、Dst5及びDst6、Dst7及びDst8がそれぞれ同一のレジスタにロードされたものとする。また、Dst1及びDst2で構成される領域をdst_1、Dst3及びDst4で構成される領域をdst_2、Dst5及びDst6で構成される領域をdst_3、Dst7及びDst8で構成される領域をdst_4とする。更に、例えば、Dst1の1ビット目から32ビット目までをDst1[0:31]、33ビット目から64ビット目までをDst1[32:63]等と表す。他のビット部分及び他の宛先アドレスDst2〜Dst8についても同様である。
【００７５】
このとき、ルックアップ処理部１０２は、SIMD演算命令の1つであるアンパック命令（例えばVPUNPCKLDQ等）により、Dst1, Dst2, Dst5, Dst6の先頭64ビットをそれぞれ抽出して、別のレジスタにコピーする。以降では、このレジスタの領域をdst_1_3とする。なお、後半の32ビット（すなわち、Dst1[32:64], Dst5[32:64], Dst2[32:64], Dst6[32:64]）は次のステップＳ２０３の処理で破棄される。
【００７６】
同様に、ルックアップ処理部１０２は、SIMD演算命令の1つであるアンパック命令により、Dst3, Dst4, Dst7, Dst8の先頭64ビットをそれぞれ抽出して、別のレジスタにコピーする。以降では、このレジスタの領域をdst_2_4とする。なお、後半の32ビット（すなわち、Dst3[32:64], Dst7[32:64], Dst4[32:64], Dst8[32:64]）は次のステップＳ２０３の処理で破棄される。
【００７７】
ステップＳ２０３：次に、ルックアップ処理部１０２は、8個の宛先アドレス（IPv6）の先頭32ビットを抽出する。例えば、図１７に示すように、ルックアップ処理部１０２は、SIMD演算命令の1つであるアンパック命令（例えばVPUNPCKLDQ等）により、Dst1, Dst2, Dst5, Dst6の先頭32ビットをそれぞれ抽出して、別のレジスタにコピーする。以降では、このレジスタの領域をupkとする。
【００７８】
ステップＳ２０４：次に、ルックアップ処理部１０２は、upkを用いて、図６のステップＳ１０２〜ステップＳ１０３の処理を実行する。すなわち、ルックアップ処理部１０２は、upkをdstと見做して、図６に示すIPルックアップ処理（IPv4）のステップＳ１０２〜ステップＳ１０３の処理を実行する。
【００７９】
ステップＳ２０５：次に、ルックアップ処理部１０２は、図６のステップＳ１０４〜ステップＳ１０７の処理を実行する。
【００８０】
ステップＳ２０６：次に、ルックアップ処理部１０２は、図６のステップＳ１０８の処理と同様に、全てのjmp値が0であるか否かを判定する。
【００８１】
上記のステップＳ２０６で全てのjmp値が0である判定されなかった場合（つまり、ルックアップが継続している場合）、ルックアップ処理部１０２は、ステップＳ２０７の処理に進む。
【００８２】
一方で、ステップＳ２０６で全てのjmp値が0であると判定された場合（つまり、ルックアップが継続していない場合）、ルックアップ処理部１０２は、ステップＳ２０９の処理に進む。
【００８３】
ステップＳ２０７：ルックアップ処理部１０２は、32ビット分のルックアップが行われた場合（つまり、dstと見做されたupkのdst1〜dst8の各32ビット領域の全てのビット列がルックアップ済みである場合）、SIMD演算命令の1つである論理シフト命令（例えばVPSRLDQ等）により、dst_1〜dst_4をそれぞれ32ビット左にシフトする。ただし、32ビット分のルックアップが未だ行われていない場合、本ステップの処理は実行されない。なお、dst1〜dst8の各32ビット領域の全てのビット列をルックアップ済みであるとは、例えば、8ビット毎にルックアップを行う場合には4回ルックアップが行われたことを意味し、16ビットでルックアップを行った後、8ビット毎にルックアップを行う場合には3回ルックアップが行われたことを意味する。
【００８４】
そして、ルックアップ処理部１０２は、32ビット左シフトされたdst_1〜dst_4を用いて、ステップＳ２０２〜ステップＳ２０３の処理を実行する。これにより、宛先アドレス（IPv6）の次の32ビット部分がupkとして抽出される。
【００８５】
ステップＳ２０８：ルックアップ処理部１０２は、図６のステップＳ１０９〜ステップＳ１１０の処理を実行する。すなわち、ルックアップ処理部１０２は、upkをdstと見做して、図６に示すIPルックアップ処理（IPv4）のステップＳ１０９〜ステップＳ１１０の処理を実行する。そして、ルックアップ処理部１０２は、上記のステップＳ２０５の処理に戻る。
【００８６】
ステップＳ２０９：ルックアップ処理部１０２は、ルックアップ結果が格納されているNhop1〜Nhop8を並べ替える。例えば、図１８に示すように、本実施形態では、nhopは、Nhop1, Nhop3, Nhop5, Nhop7, Nhop2, Nhop4, Nhop6, Nhop8の順で構成されている。なお、Nhop1〜Nhop8にはそれぞれdst1〜dst8のネクストホップを示すinf値（つまり、経路情報のインデックス番号）が格納されている。このとき、ルックアップ処理部１０２は、SIMD演算命令の1つである並び替え命令（例えばVPSRLDQ等）により、Nhop1, Nhop2, Nhop3, Nhop4, Nhop5, Nhop6, Nhop7, Nhop8の順にNhop1〜Nhop8を並び替える。これにより、各宛先アドレス（IPv6）のネクストホップが得られる。
【００８７】
なお、本実施形態では、ルックアップ終了後に並べ替えを行っているが、ルックアップ前に、upkを構成するDst1〜Dst8を、Dst1, Dst2, Dst3, Dst4, Dst5, Dst6, Dst7, Dst8の順に並べ替えてもよい。ただし、ルックアップ前に並べ替える場合には、32ビットの切り出し毎に並べ替えが必要となる。一方で、本実施形態のように、ルックアップ終了後に並べ替えを行えば並べ替えが1回で済むため、効率的な並べ替えが可能となる。
【００８８】
＜通信装置１０のハードウェア構成＞
次に、本実施形態に係る通信装置１０のハードウェア構成について、図１９を参照しながら説明する。図１９は、本実施形態に係る通信装置１０のハードウェア構成の一例を示す図である。
【００８９】
図１９に示すように、本実施形態に係る通信装置１０は、ハードウェアとして、入力装置２０１と、表示装置２０２と、外部I/F２０３と、通信I/F２０４と、プロセッサ２０５と、記憶装置２０６とを有する。これら各ハードウェアは、それぞれがバスＢを介して通信可能に接続されている。
【００９０】
入力装置２０１は、例えばキーボードやマウス、タッチパネル等である。表示装置２０２は、例えばディスプレイ等である。なお、通信装置１０は、入力装置２０１及び表示装置２０２の少なくとも一方を有していなくてもよい。
【００９１】
外部I/F２０３は、外部装置とのインタフェースである。外部装置には、記録媒体２０３ａ等がある。通信装置１０は、外部I/F２０３を介して、記録媒体２０３ａの読み取りや書き込み等を行うことができる。記録媒体２０３ａには、例えば、通信装置１０が有する各機能部（つまり、受信部１０１、ルックアップ処理部１０２及び送信部１０３）を実現する1以上のプログラム等が記録されていてもよい。
【００９２】
通信I/F２０４は、通信装置１０を通信ネットワークに接続するためのインタフェースである。
【００９３】
プロセッサ２０５は、例えばCPU等である。なお、プロセッサ２０７にはレジスタが内蔵されている。通信装置１０が有する各機能部は、記憶装置２０６に格納されている1以上のプログラムが、プロセッサ２０５に処理を実行させることで実現される。
【００９４】
記憶装置２０６は、RAM(Random Access Memory)、HDD(Hard Disk Drive)やSSD(Solid State Drive)等の補助記憶装置等である。記憶装置２０６にはROM(Read Only Memory)が含まれていてもよい。記憶装置２０６には、各種プログラムやデータが記憶されている。これらのプログラムやデータには、例えば、OS(Operating System)やアプリケーションプログラム、通信装置１０が有する各機能部を実現する1以上のプログラム、経路表等が挙げられる。
【００９５】
本実施形態に係る通信装置１０は、図１９に示すハードウェア構成を有することにより、上述したIPルックアップ処理を実現することができる。なお、図１９に示す例では、本実施形態に係る通信装置１０が1台の装置（コンピュータ）で実現されている場合を示したが、これに限られない。本実施形態に係る通信装置１０は、複数台の装置（コンピュータ）で実現されていてもよい。また、1台の装置（コンピュータ）には、複数のプロセッサ２０５や複数の記憶装置２０６が含まれていてもよい。
【００９６】
＜まとめ＞
以上のように、本実施形態に係る通信装置１０は、SIMD演算を用いて複数の宛先アドレスを並列にIPルックアップすることができる。このため、本実施形態に係る通信装置１０では、IPルックアップ処理の高速化を実現することが可能となる。
【００９７】
しかも、本実施形態に係る通信装置１０は、IPルックアップ処理を高速化するためにSIMD演算を用いているため、以下の2つのメリットがある。
【００９８】
メリット1：低コスト
SIMD演算機能は現在広く流通しているサーバ向けプロセッサに標準的に搭載されていることが多いため、特別なハードウェア（例えば、GPUやFPGA等）を追加で用意することなく、IPルックアップ処理を高速化させることが可能となる。また、SIMD演算を使用する処理の開発プロセスは通常のソフトウェアと変わらないため、開発コストも増大しない。
【００９９】
メリット2：マルチコアへのスケーラビリティ
SIMD演算は単位のCPUコア毎に使用できる機構であるため、従来から利用されてきたマルチコアによるスケーリング手法を同時に利用することができる。
【０１００】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【０１０１】
１０        通信装置
１０１      受信部
１０２      ルックアップ処理部
１０３      送信部
【図１】
2020156058.tif 000003
【図２】
2020156058.tif 000004
【図３】
2020156058.tif 000005
【図４】
2020156058.tif 000006
【図５】
2020156058.tif 000007
【図６】
2020156058.tif 000008
【図７】
2020156058.tif 000009
【図８】
2020156058.tif 000010
【図９】
2020156058.tif 000011
【図１０】
2020156058.tif 000012
【図１１】
2020156058.tif 000013
【図１２】
2020156058.tif 000014
【図１３】
2020156058.tif 000015
【図１４】
2020156058.tif 000016
【図１５】
2020156058.tif 000017
【図１６】
2020156058.tif 000018
【図１７】
2020156058.tif 000019
【図１８】
2020156058.tif 000020
【図１９】
2020156058.tif 000021