(57)【特許請求の範囲】
【請求項１】
複数のネットワークを接続し、前記ネットワークから入力されたパケットを経路情報に基づいて次の転送先に出力するネットワーク中継装置であって、
ネットワークに接続され、ネットワークとのインタフェースを制御するネットワークインタフェース部と、
ひとつ又は複数の前記ネットワークインタフェース部と接続され、前記ネットワークインタフェース部から入力されたパケットのルーティングを行うルーティング処理部と、
装置内部を管理するルーティング管理部と、
前記ルーティング管理部及び複数の前記ルーティング処理部の各々を接続する接続部とを備え、
前記ルーティング処理部は、
入力パケットを記憶するパケットバッファと、
前記パケットバッファと非同期にアクセス可能で入力パケットのヘッダ及び内部ヘッダを含むヘッダ情報を記憶する高速に読出し及び書込み可能なヘッダメモリと、
宛先のＩＰアドレスに対応する次ルータのＩＰアドレスを含む経路情報を記憶する経路テーブルと、
次ルータのＩＰアドレスに対応する次ルータのＭＡＣアドレスを記憶するアドレス検索テーブルと、
転送元及び宛先のＩＰヘッダを含む比較条件に対応するアクションを記憶したフロー検索テーブルと、
ネットワークから受信した入力パケットを前記パケットバッファへ記憶するとともに、パケットのヘッダに内部ヘッダを付加してヘッダ情報として前記ヘッダメモリへ記憶する受信処理と、前記パケットバッファから入力パケットを読み出し、前記パケットバッファに記憶された入力パケット及び前記ヘッダメモリに記憶された、転送先情報とアクションとを含むヘッダ情報により出力パケットを作成して、出力パケットを前記接続部に出力する送信処理とを実行する転送エンジンと、
前記受信処理で前記ヘッダメモリに記憶されたヘッダ情報に基づき前記経路テーブルを参照して、転送先情報を検索する入力検索処理と、当該入力検索処理で求められた次ルータのＩＰアドレスに基づきアドレス検索テーブルを参照して次ルータのＭＡＣアドレスを検索するとともに、フロー検索テーブルを参照してＱｏＳを含む各種アクションを検索し、前記ヘッダメモリのヘッダ情報に書き込む出力検索処理とを実行する検索エンジンと
を備え、
第１の入力パケット、第２の入力パケット、第３の入力パケット、第４の入力パケットの順番で入力パケットを受信した場合に、前記経路テーブル、前記アドレス検索テーブル及び前記フロー検索テーブルを、各々独立に読出し又は書込みを行うことができるように別個の記憶回路で構成することで、
前記転送エンジンの前記第１の入力パケットに対する送信処理と、前記第４の入力パケットに対する受信処理、および、
前記検索エンジンの前記第２の入力パケットに対する出力検索処理と、前記第３の入力パケットに対する入力検索処理をそれぞれ並列に実行することを特徴とするネットワーク中継装置。
【請求項２】
前記転送エンジンは、受信処理において、
入力されたパケットを前記パケットバッファに記憶し、
入力パケットのＭＡＣヘッダ及びＩＰヘッダに、入出力ポート番号及びＱｏＳ制御情報を含む内部ヘッダを付加してヘッダ情報として前記ヘッダメモリに記憶し、
前記検索エンジンは、入力検索処理において、
前記転送エンジンにより前記ヘッダメモリに記憶されたヘッダ情報からＩＰヘッダ中の宛先ＩＰアドレスを抽出し、
この宛先ＩＰアドレスに基づき前記経路テーブルを参照して、次ルータのＩＰアドレスを含む転送先情報を検索し、
前記検索エンジンは、出力検索処理において、
入力検索処理で求められた次ルータのＩＰアドレスを抽出し、
このＩＰアドレスに基づきアドレス検索テーブルを参照して次ルータのＭＡＣアドレスを検索するとともに、フロー検索テーブルを参照して転送先及び宛先の情報を含む比較条件に基づきＱｏＳを含むアクション情報を検索し、
これら検索された転送制御情報を前記ヘッダメモリに記憶し、
前記転送エンジンは、送信処理において、
前記検索エンジンの出力検索処理が検索した転送制御情報に基づいて、前記パケットバッファに記憶された入力パケット及び前記ヘッダメモリに記憶されたヘッダ情報により出力パケットを作成して、
出力パケットを前記接続部又は前記ネットワークインタフェース部に出力することを特徴とする請求項１に記載のネットワーク中継装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ネットワーク中継装置及びネットワーク中継方法に係る。本発明は、特に、コンピュータネットワークシステムにおけるルータ等のネットワーク中継装置において、入力されたパケットの転送先を高速に検索することができるネットワーク中継装置及びネットワーク中継検索方法に関する。
【０００２】
【従来の技術】
一般に、ネットワークシステムにおいては、複数のネットワーク間を接続するためにルータやブリッジ等のネットワーク中継装置が用いられる。ルータは、接続されているネットワークやサブネット等から受け取ったパケットの宛先アドレスを調べてパケットの転送先を決定し、転送先のルータ又はホストが接続されたネットワークやサブネット等にパケットを転送する。
【０００３】
図１３に、従来のネットワーク中継装置の構成図を示す。この図において、ルータ１００は、ルーティング制御部（ＲＭ）１１０、ルータバス１２０、ネットワークインタフェース部（ＮＩＦ）１３０、ポート１４０等を備える。各ポート１４０は、適宜のネットワーク１５０に接続される。
【０００４】
ネットワークインタフェース部１３０は、ポート１４０に接続されたネットワークからパケットを受け取り、受け取ったパケットをルータバス１２０経由でルーティング制御部１１０に送信する。ルーティング制御部１１０は、ルーティング情報を保持するルーティングテーブルを備え、このルーティング情報を用いて受け取ったパケットの宛先から転送先のネットワーク１５０を決定し、そのネットワーク１５０が接続されるポート１４０のネットワークインタフェース部１３０にパケットを送信する。ルーティング制御部１１０からパケットを受け取ったネットワークインタフェース部１３０は、そのパケットを転送先のネットワーク１５０に送出する。なお、ルーティング制御部１１０は、受け取ったパケットのヘッダ情報に基づいてルーティングテーブルに保持するルーティング情報を更新・保守するとともに、ルータ１００全体の管理機能を備えている。
【０００５】
ここで、ルータがパケットを受け取ったときに、次に転送するアドレス及びパケットを出力するポートを検索する経路検索処理について説明する。通常、経路検索には、構成定義情報及びルータ間での送受により得られた情報等から作成される経路検索テーブル（ルーティングテーブル）が用いられる。ルーティングテーブルは、ネットワークアドレスとネットワークマスク長等の組を検索のキーとして、出力ポート、次ホップアドレス、及び、ネットワークが直接接続されているか否かの情報（次ホップ情報）等を検索するためのテーブルである。
【０００６】
また、他の従来技術として、特開平０５−１９９２３０号公報（米国特許第５，４３４，８６３号参照）には、ルーティング処理の高速性を損なうことなく、ネットワークの規模に柔軟に対応できるようにしたインタネットワーク装置及び通信ネットワークシステムが記載されている。この装置及びシステムでは、ルータ管理部と、ルーティングを行う複数のルーティングアクセラレータモジュールとが、高速バスで結合される構成となっている。また、各々のルーティングアクセラレータには、複数の通信ポートが互いに独立に接続されている。このような従来技術によると、複数のルーティングアクセラレータにより、高速ルーティングを可能とし、また、ルーティングアクセラレータを増設すれば、小規模から大規模ネットワークへの対応が容易に実現できる。
【０００７】
【発明が解決しようとする課題】
近年、ネットワーク運用中にネットワークの構成などを認識して、ルーティング処理のための中継情報を動的に生成、追加、変更、削除するダイナミックルーティングの必要性が高まってきている。即ち、ルータでは、各ルータ間でネットワークに関する情報をやり取りするためのルーティングプロトコル（例えば、ＴＣＰ／ＩＰプロトコル群におけるＲＩＰ：Routing Information ProtocolやＯＳＰＦ：Open Shortest Path Firstなど）の処理が必要となる。さらに、ルータ自体の性能情報などの管理情報をネットワーク上の管理マスタ局と通信するためのネットワークマネジメントプロトコル（例えば、ＴＣＰ／ＩＰプロトコル群におけるＳＮＭＰ：Simple Network Management Protocolなど）の処理も、従来例におけるルーティングを行う手段が兼用せざるを得ないため、本来の中継性能が充分発揮できない。従って、従来のルータでは、近年出現してきたの高速ＬＡＮ(Local Area Network)や、広帯域ＩＳＤＮ及びＡＴＭ(Asynchronous Transfer Mode)など高速回線に対応するのは困難である。
【０００８】
また、近年のネットワークの高速化に伴い、ルータやブリッジに用いられるデータ処理装置は、ネットワークコントローラがメモリから転送先経路を検索する処理なども高速化が必要である。さらに、プロセッサとのメモリのアクセス競合を考慮すると、従来のルータにおいては、メモリのアクセス競合によって発生する性能低下を吸収するために、搭載できるネットワークコントローラの数を制限したり、またはコスト的に非効率であるが、高速のメモリ装置もしくは非同期にプロセッサやネットワークコントローラなどからアクセス可能なデュアルポートメモリを使用しなければならない問題があった。また、従来のルータにおける経路検索は、主にソフトウェアにより実行されており、高速にルーティング処理を実行することは難しかった。
【０００９】
本発明は、高通信品質（ＱｏＳ）、高信頼性、セキュリティーを保証して高速にルーティングするネットワーク中継装置及び方法を提供することを目的とする。また、本発明は、転送エンジン及び検索エンジン等の機能ブロック毎にハードウェア処理を行うことで、ルーティング及びパケット転送を高速に行うことを目的とする。また、本発明は、独立にアクセスできる複数のテーブルを設けるとともに、ルーティング処理を、独立に処理される受信処理、送信処理、入力検索処理及び出力検索処理に分割し、必要なテーブルを独立に使用することで、高速にルーティングを行うことを目的とする。さらに、本発明では、パイプライン制御により各処理を実行することにより、一層の高速化を実現することを目的とする。
【００１０】
【課題を解決するための手段】
本発明の第１の解決手段によると、
複数のネットワークを接続し、前記ネットワークから入力されたパケットを経路情報に基づいて次の転送先に出力するネットワーク中継装置であって、
ネットワークに接続され、ネットワークとのインタフェースを制御するネットワークインタフェース部と、
ひとつ又は複数の前記ネットワークインタフェース部と接続され、前記ネットワークインタフェース部から入力されたパケットのルーティングを行うルーティング処理部と、
装置内部を管理するルーティング管理部と、
前記ルーティング管理部及び複数の前記ルーティング処理部の各々を接続する接続部と
を備え、
前記ルーティング処理部は、
入力パケットを記憶するパケットバッファと、
前記パケットバッファと非同期にアクセス可能で入力パケットのヘッダ及び内部ヘッダを含むヘッダ情報を記憶する高速に読出し及び書込み可能なヘッダメモリと、
宛先のＩＰアドレスに対応する次ルータのＩＰアドレスを含む経路情報を記憶する経路テーブルと、
次ルータのＩＰアドレスに対応する次ルータのＭＡＣアドレスを記憶するアドレス検索テーブルと、
転送元及び宛先のＩＰヘッダを含む比較条件に対応するアクションを記憶したフロー検索テーブルと、
ネットワーク又は前記接続部から受信した入力パケットを前記パケットバッファへ記憶するとともに、パケットのヘッダに内部ヘッダを付加してヘッダ情報として前記ヘッダメモリへ記憶する受信処理と、前記パケットバッファから入力パケットを読み出し、前記パケットバッファに記憶された入力パケット及び前記ヘッダメモリに記憶されたヘッダ情報により出力パケットを作成して、出力パケットを前記接続部又はネットワークに出力する送信処理とを実行する転送エンジンと、
前記ヘッダメモリに記憶されたヘッダ情報に基づき前記経路テーブルを参照して、転送先情報を検索する入力検索処理と、入力検索処理で求められた次ルータのＩＰアドレスに基づきアドレス検索テーブルを参照して次ルータのＭＡＣアドレスを検索するとともに、フロー検索テーブルを参照してＱｏＳを含む各種アクションを検索する出力検索処理とを実行する検索エンジンと
を備えたことを特徴とするネットワーク中継装置を提供する。
【００１１】
本発明の第２の解決手段によると、
ネットワークと接続されたネットワークインタフェース部と、前記ネットワークインタフェース部から入力されたパケットのルーティングを行うルーティング処理部と、装置内部を管理するルーティング管理部と、前記ルーティング管理部及び複数の前記ルーティング処理部の各々を接続する接続部とを備えたネットワーク中継装置において、ネットワークから入力された入力パケットを転送先に出力するネットワーク中継方法であって、
入力されたパケットを記憶し、入力パケットのＭＡＣヘッダ及びＩＰヘッダに、入出力ポート番号及びＱｏＳ制御情報を含む内部ヘッダを付加してヘッダ情報として入力パケットとは別に記憶する受信処理と、
前記受信処理により記憶されたヘッダ情報からＩＰヘッダ中の宛先ＩＰアドレスを抽出し、この宛先ＩＰアドレスに基づき、次ルータのＩＰアドレスを含む転送先情報を検索する入力検索処理と、
前記入力検索処理で求められた次ルータのＩＰアドレスを抽出し、このＩＰアドレスに基づき次ルータのＭＡＣアドレスを検索するとともに、転送先及び宛先の情報を含む比較条件に基づきＱｏＳを含むアクション情報を検索し、これら検索された転送先情報及びアクション情報をヘッダ情報中に記憶する出力検索処理と、
入力パケット及びヘッダ情報に基づいて出力パケットを作成して、出力パケットを前記接続部又は前記ネットワークインタフェース部に出力する送信処理と
を含むネットワーク中継方法を提供する。
【００１２】
【発明の実施の形態】
図１に、本発明に係るネットワーク中継装置の構成図を示す。この図において、ルータ１は、ルーティング処理部（ＲＰ, Routing Processor）１０、スイッチ部（ＣＳ, Crossbar Switch）２０、ネットワークインタフェース部（ＮＩＦ, Network Interface）３０、ポート４０、ルーティング管理部（ＲＭ, Routing Manager）６０、電源（ＰＳ, Power Supply）７０等を備える。各ポート４０は、適宜のネットワーク５０に接続される。ネットワーク５０としては、例えば、イーサネット等のＬＡＮ、ＷＡＮ、ＡＴＭ等がある。なお、装置の信頼性向上させるため、電源７０及び共通部等を適宜二重化することができる。
【００１３】
ルーティング制御のための機能は、ルーティング機能を実行するルーティング処理部１０及びルータ１の管理を行うルーティング管理部６０に分かれる。さらに、ルータ１は、ひとつ又は複数のネットワークインタフェース部３０を有するルーティング処理部１０を、複数備えている。ルーティング管理部６０は、ルータ１全体の管理機能を備えるとともに、ルート計算処理を実行し、また、他のルータとの間でルーティング情報を送受するとともに、ルータ内の各ルーティング処理部１０にルーティング情報を配布する。ルーティング管理部６０は、ここでは、二重化構成が採用される。スイッチ部２０は、クロスバスイッチ等のスイッチを備え、ルーティング処理部１０相互間又はルーティング処理部１０とルーティング管理部６０との間の通信及び交換を行う。スイッチ部２０は、ここでは、二重化構成が採用される。なお、スイッチ部２０に代えてバス等により接続しても良い。また、クロスバスイッチを用いた場合、ルーティング管理部６０及び複数のルーティング処理部１０のうち１組により接続経路が占有されることなく、同時に複数の組が送受信を行うことができる。
【００１４】
ルーティング処理部１０は、接続されたネットワークインタフェース部３０によりパケット転送を行う。ルーティング処理部１０は、また、他のルーティング処理部１０に接続されたネットワーク５０にパケットを転送する場合は、スイッチ部２０を介して該当するルーティング処理部１０にパケットを転送する。ルーティング処理部１０は、各機能がハードウェア構成により高速動作をするよう設計される。ルーティング処理部１０は、さらに詳細には、例えば、スイッチング処理、ルート検索、フォワーディング、フィルタリング、ＱｏＳ、ＩＰマルチキャスト等の機能を有する。ルーティング処理部１０は、自己のルーティング処理部１０内のネットワークインタフェース部３０の各ポート４０、他の各ルーティング処理部１０及びルーティング管理部６０等の各々について、適宜入力バッファ及び出力バッファを備える。ネットワークインタフェース部３０は、ひとつ又は複数のポート４０を有し、ネットワーク５０とルーティング処理部１０とのインタフェースを制御する。
【００１５】
図２に、ルーティング処理部の内部構成を表したネットワーク中継装置の動作説明図を示す。この図を用いて、経路検索と、経路検索の結果得られた宛先にパケットを転送する動作について、ルーティング処理部１０の内部構成図を参照して説明する。
ルーティング処理部１０は、転送エンジン１３、検索エンジン１４、ヘッダＲＡＭ１１、パケットバッファ１２、経路テーブル１５、ＡＲＰテーブル（アドレス検索テーブル）(ARP, Address Resolution Protocol)１６、フィルタ／ＱｏＳテーブル（フロー検索テーブル）１７を備える。転送エンジン１３は、例えば、パケットの入出力処理を行う。検索エンジン１４は、主に、パケットのヘッダ情報に基づき経路検索処理及びＱｏＳ制御等のフロー検索処理を行う。検索エンジン１４は、専用ＬＳＩ等により、高速処理が可能なハードウェアで構成される。
【００１６】
パケットバッファ１２は、転送エンジン１３がルーティング処理部１０に入力されたパケットを転送するまでの間、入力されたパケットを格納しておく。ヘッダＲＡＭ１１は、入力されたパケットのヘッダのみを抽出して記憶する。ヘッダＲＡＭ１１は、読み出し／書込速度の高速なメモリを用いる。この実施の形態では、ネットワークから受信したパケットや他のデータ処理装置から転送されたパケットを格納するバッファメモリとは別に、パケットバッファ１２と非同期にアクセス可能なヘッダＲＡＭ１１を設け、パケットをパケットバッファ１２へ格納すると同時に該パケットのヘッダ部をヘッダＲＡＭ１１へも格納（コピー）するようにした。転送エンジン１３及び検索エンジン１４等の各々のプロセッサは、ヘッダＲＡＭ１１を使用してパケットのヘッダ部を取り込み、ヘッダ部を解析している間、パケットバッファ１２に対するパケットの読み書きが可能になり、あるパケットのヘッダ解析処理と他のパケットの転送処理等の並列動作が達成される。
【００１７】
したがって、検索エンジン１４のプロセッサがヘッダ情報をヘッダＲＡＭ１１から読み出している間、パケットバッファ１２はプロセッサが使用しないので、転送エンジン１３によるパケット送信又は転送のためのアクセスが可能になり、検索エンジン１４と転送エンジン１３とのパケットバッファ１２へのアクセス競合が起こらないようにすることができる。なお、ネットワーク側からの受信パケット及びそのヘッダ部を格納する領域と、スイッチ部２０側からの転送パケット及びそのヘッダ部を格納する領域とを、それぞれ別構成としてもよい。このように別構成にすると、パケットの管理が容易になる。
【００１８】
また、経路テーブル１５、ＡＲＰテーブル１６及びフィルタ／ＱｏＳテーブル１７は、それぞれ独立に分割して構成される。これにより、検索エンジン１４が各テーブルを個別にアクセスして読み出し又は書込を行うことで、ルーティング情報、ＱｏＳ等を高速に検索することができる。さらに、ルーティング処理の高速化の実現のために、パイプライン処理を実行することができる。各テーブルの詳細及びパイプライン処理については、後述する。
【００１９】
図３に、ネットワーク中継装置の動作概要のシーケンス図を示す。
まず、ネットワークからポートを介して、第１のネットワークインタフェース部３０にパケットが入力されると、第１のネットワークインタフェース部３０は、これを転送エンジン１３に送信する。転送エンジン１３は、受信したパケットをパケットバッファ１２に記憶する。また、転送エンジン１３は、入力パケットのヘッダのみを抽出し、内部ヘッダを付加してヘッダ情報を形成し、ヘッダ情報をヘッダＲＡＭ１１に記憶する。内部ヘッダについては、後述する。
【００２０】
検索エンジン１４は、ヘッダＲＡＭ１１をアクセスしてヘッダ情報を読み出す。なお、転送エンジン１３が、ヘッダＲＡＭ１１に記憶されたヘッダ情報を検索エンジン１４に送信するようにしてもよい。検索エンジン１４では、ヘッダ情報により、宛先のルータ・ＲＰ・ポートの各番号又はアドレス、ＭＡＣアドレス等の次の転送経路に関する情報、及び、ＱｏＳ制御情報等の通信品質に関する制御についての情報等を適宜検索する。検索エンジン１４は、検索された各番号・アドレス情報等の転送先情報及びＱｏＳ情報等のアクション情報を含む転送制御情報をヘッダＲＡＭ１１に書き込む。なお、検索エンジン１４は、転送エンジン１３に転送制御情報を送信するようにしてもよい。
【００２１】
転送エンジン１３では、パケットバッファ１２に記憶されたパケット及びヘッダＲＡＭ１１に記憶されたヘッダ情報（転送制御情報を含む）に基づいて、出力パケットを作成する。そして、転送エンジン１３は、作成された出力パケットを転送先に出力する。この際、転送エンジン１３は、転送経路が他のルーティング処理部１０に属するものである場合は、該当する他のルーティング処理部１０へのバッファにキューイングし、自己のルーティング処理部１０のネットワークインタフェース部３０に属するものである場合は、対応するポート４０のバッファにキューイングする。
【００２２】
なお、ルーティング処理部１０により検索される転送経路は、ひとつに限らず、複数経路として各経路に同報転送することもできる。この場合、複数の各経路毎に適宜のバッファにキューイングされる。
【００２３】
以下に、ルーティング処理部の詳細な構成及び動作を説明する。まず、各メモリの説明をする。図４に、パケットバッファ１２及びヘッダＲＡＭ１１の説明図を示す。
【００２４】
図４（Ａ）に、パケットバッファ１２に記憶されるパケットのファーマットの一例を示す。パケットバッファ１２には、ネットワーク５０又はスイッチ部２０等から、パケットが入力される。このパケットのフォーマットは、例えば、ＩＰパケットに、レイヤ２・ＭＡＣヘッダ４０１が付加されたものである。ＩＰパケットは、例えば、レイヤ３・ＩＰヘッダ４０２、レイヤ４・ヘッダ４０３及びペイロード４０４を含む。
【００２５】
レイヤ２・ＭＡＣヘッダ４０１は、例えば、パケットを直前に送出したルータの物理アドレス（ハードウエアアドレス）である送信元ＭＡＣアドレス（Source Address Media Access Control、SAMAC）と、パケットを次に受信するルータの物理アドレスである宛先ＭＡＣアドレス（Destination Address Media Access Control、DAMAC）等を有する。レイヤ３・ＩＰヘッダ４０２は、送信元アドレス（送信端末のアドレス）である送信元ＩＰアドレス（Source IP Address：以下「SIP」という。）と、宛先アドレス（受信端末のアドレス）である宛先ＩＰアドレス（Destination IP Address：以下「DIP」という。）等を有する。レイヤ４ヘッダ４０３は、プロトコル（＝上位アプリケーション）を表す送信元ポート（Source Port：以下「SPORT」という。）と宛先ポート（Destination Port：以下「DPORT」という。）等を有する。ペイロード４０４は、ユーザデータを含む。各ヘッダとしては、上述の他に優先度を表すTOS（Type of Service）、ＩＰプロトコルの上位プロトコル等の情報も格納される場合があるが、上述した各情報と同様に処理することができる。
【００２６】
また、図４（Ｂ）に、ヘッダＲＡＭに記憶されるヘッダ情報のフォーマット一例を示す。ヘッダ情報は、例えば、パケットフォーマット中のレイヤ２・ＭＡＣヘッダ４０１及びレイヤ３・ＩＰヘッダ４０２に、制御情報として内部ヘッダ４０５を付加したものである。この内部ヘッダ４０５は、例えば、入力回線番号、出力回線番号、ＱｏＳ制御情報等を有する。なお、ルータ内部での内部パケットフォーマットは、ネットワークのパケットのフォーマットに内部ヘッダ４０５が付加される。その際、パケットバッファ１２に記憶された情報とヘッダＲＡＭ１１に記憶された情報とにより内部パケットが形成されることができる。また、パケットバッファ１２に、内部ヘッダ４０５を含めた内部パケットフォーマットの形式で記憶するようにして、パケットバッファ１２のみの情報から内部パケットを転送するようにしても良い。また、検索エンジン１４により検索された転送先情報及びアクション情報等の転送制御情報は、この内部ヘッダ４０５に書き込まれることができる。
【００２７】
つぎに、図５に、経路検索に用いられる各テーブルの説明図を示す。
図５（Ａ）に示すように、経路テーブル１５の各エントリは、例えば、宛先のＩＰアドレス５０１、次ルータのＩＰアドレス５０２、自ルータの送出ＲＰ番号５０３及び送出ポート番号５０４等を含む。また、図５（Ｂ）に示すように、ＡＲＰテーブル１６の各エントリは、例えば、次ルータのＩＰアドレス５０２、次ルータのＭＡＣアドレス５０６等を含む。また、図５（Ｃ）に示すように、フィルタ／ＱｏＳテーブル１７の各エントリは、例えば、ＩＰヘッダ／レイヤ４ヘッダの値（範囲）５０７及びアクション５０８等を含む。ここで、アクション５０８としては、通過又は廃棄をする処理であるフィルタ、カプセル化する又はカプセル化しない処理であるトンネル、ＱｏＳ等がある。特にＱｏＳについては、後述する。
【００２８】
図６に、ルーティング処理部による高速化処理の説明図を示す。この図を参照して、ギガビット等の高速な回線速度に追従できるようにしたパケット転送の実現化方法について説明する。ここでは、ルーティング処理のパラレル化／パイプライン化により、高速化を実現する。以下に、図４及び図５に示されるフォーマットを参照して、動作を説明する。
【００２９】
ルーティング処理は、主に、受信処理▲１▼、入力検索処理▲２▼、出力検索処理▲３▼、送信処理▲４▼に分けられる。
まず、受信処理▲１▼では、転送エンジン１３は、ネットワークインタフェース部３０からの受信パケットを受け取る。パケットバッファ１２には、前述のとおり入力パケット又は内部ヘッダを付加した内部パケットフォーマットのパケットが記憶される。また、入力パケットのレイヤ２・ＭＡＣヘッダ４０１及びレイヤ３・ＩＰヘッダ４０２に内部ヘッダ４０５を付加してヘッダ情報とし、ヘッダ情報がヘッダＲＡＭ１１に記憶される。ヘッダＲＡＭ１１は、パケットバッファ１２と独立に高速に読み出し及び書き込みが可能であり、ヘッダ情報のみを記憶することで、記憶容量を削減し、一層高速に処理をすることができる。検索エンジン１４は、抽出されたヘッダ情報を、適宜のタイミングでアクセスすることができる。
【００３０】
つぎに、入力検索処理▲２▼では、検索エンジン１４は、ヘッダ情報からレイヤ３・ＩＰヘッダ４０２中にある宛先ＩＰアドレスを抽出し、このアドレスに基づき経路テーブル１５を参照して、次ルータのＩＰアドレス５０２、自ルータの送出ＲＰ番号５０３及び送出ポート番号５０４等を検索する。さらに、検索エンジン１４は、受信したヘッダ情報からレイヤ３・ＩＰヘッダ４０２及びレイヤ４・ヘッダ４０３等の比較情報に基づき、フィルタ／ＱｏＳテーブル１７を参照して、ＱｏＳ等の入力側の各種アクション５０８を検索する。これらの入力側フィルタ／ＱｏＳ検索及び経路検索は、各々のテーブルが別個に設けられているため、並列して実行することができる。
【００３１】
つぎに、出力検索処理▲３▼では、検索エンジン１４は、入力検索処理▲２▼で求められた次ルータのＩＰアドレスを抽出し、このアドレスに基づきＡＲＰテーブル１６を参照して、次ルータのＭＡＣアドレス５０６等を検索するとともに、フィルタ／ＱｏＳテーブル１７を参照して、ＱｏＳ等の出力側の各種アクション５０８を検索する。これらの出力側フィルタ／ＱｏＳ検索及び回線表／ＡＲＰ検索は、各々のテーブルが別個に設けられているため、並列して実行することができる。求められた次の転送先に関する番号・アドレス情報等の転送先情報及びＱｏＳ制御情報等のアクション情報を含む転送制御情報は、ヘッダＲＡＭ１１に記憶される。転送制御情報は、例えば、ヘッダ情報中の内部ヘッダ４０５又はその他の位置に適宜書き込むことができる。
【００３２】
つぎに、送信処理▲４▼では、出力検索処理▲３▼が検索した転送制御情報を含むヘッダ情報をヘッダＲＡＭ１１から読み出し、ヘッダ情報とパケットバッファ１２に基づき出力パケットを作成して、ネットワークインタフェース部３０又は他のルーティング処理部１０若しくはルーティング管理部６０に対するバッファにキューイングする。
【００３３】
図７に、ハードウェアによる検索エンジンの構成図の一例を示す。
検索エンジン１４は、経路テーブル１５、ＡＲＰテーブル１６、フィルタ／ＱｏＳテーブル１７等の各テーブルについて、例えば、木構造検索により必要なデータを検索することができる。ここでは、ハードウェアで構成した検索エンジン１４の処理部の一例として、経路テーブル１５を用いて転送先経路を検索するための経路検索処理部について説明する。
【００３４】
経路検索処理部２１３は、木構造検索回路２１３０と、読み込みアドレス生成回路２１３１と、経路検索処理制御回路２１３２を備える。木構造検索回路２１３０は、経路テーブル１５等の各テーブルに格納された２のｐ乗分木構造を検索し、次に読み込むべきノードのポインタの生成、受信パケットの宛先ＩＰアドレスの検査ビット値の抽出、木構造検索の終了判定、検索結果である経路情報の候補の更新等を行う。また、読み込みアドレス生成回路２１３１は、木構造検索回路２１３０から出力される読み込むべきノードへのポインタ、および検査ビット値に従い、実際に読み込むノードの一部のワードのメモリアドレスを生成する。また、経路検索処理制御回路２１３２は、経路検索処理部２１３全体の制御(各回路の動作タイミングおよび動作状態管理など)を行う。
【００３５】
次に、経路検索処理部２１３の動作について説明する。
木構造検索回路２１３０は、ヘッダＲＡＭ１１から受信パケットの宛先ＩＰアドレスを受け取り、この宛先ＩＰアドレスとノードのマスク長の値から次ノードへのポインタを生成して、読み込みアドレス生成回路２１３１に渡す。また、木構造検索回路２１３０は、ノードのマスク長で示される宛先ＩＰアドレスの検査ビット位置の値(検査ビット値)を抽出して、読み込みアドレス生成回路２１３１に渡す。
【００３６】
読み込みアドレス生成回路２１３１はこのノードへのポインタと、検査ビット値と、経路検索処理制御回路２１３２からのタイミング信号を用いて、読み出すべきノードデータが格納されているメモリアドレスを生成し、メモリ制御回路２１３２へ送信し、メモリ制御回路２１３２はこのメモリアドレスと経路検索処理制御回路２１３２からのタイミング信号を用いてメモリ制御信号を生成し、経路テーブル１５へ転送する。上記のメモリ制御信号を受信した経路テーブル１５は、対応するノードデータを信号線２１５を用いて木構造検索回路へ転送する。
【００３７】
木構造検索回路２１３０はこのノードデータを用いて、検索し、木構造検索を終了すると判定した場合は、木構造検索終了信号を経路検索処理制御回路２１３２へ出力し、経路検索処理制御回路２１３２は、木構造検索回路２１３０内に保持された経路情報のうちのエントリ有りフラグを調べ、その値が０の場合は経路検索処理を終了し、転送エンジン１３等へ検索結果無しという通知をする。エントリ有りフラグの値が１の場合は、経路情報を出力し検索処理を終了し、次のパケット処理の制御を行う。
【００３８】
つぎに、図８に、パイプライン制御による高速処理の説明図を示す。図示されるように、受信処理▲１▼、入力検索▲２▼、出力検索処理▲３▼、転送処理▲４▼の各処理をパイプラインで処理し、各処理部が常に動作するように制御することにより、ルーティング処理を高速化することができる。ここでは、さらに、入力検索▲２▼において、入力フィルタ処理（入力フィルタ／ＱｏＳ検索）と、経路表検索（経路検索）を平行して実行している。また、出力検索処理▲３▼、出力フィルタ処理（出力フィルタ／ＱｏＳ検索）と、出力回線表検索（出力回線表／ＡＲＰ検索）を平行して実行している。パイプライン構成は、この図に限らず、適宜の順序で実行することができる。
【００３９】
パイプライン処理では上述の各処理部のうちの処理部１がエントリＮの処理１を終了すると、処理１より後の処理２を行う処理部２がエントリＮの処理２を終了したか否かに拘わらず、処理部１がエントリＮ＋１の処理を開始する。この様なパイプライン処理を行うことにより、エントリＮを処理する時間は、１つの処理の時間となり、処理速度は４倍となる。前述の例では、フロー検索が４つの処理に分割されパイプライン処理したが、Ｐ個の処理に分割し、パイプライン処理できればＰ倍の性能となる。
【００４０】
つぎに、図９に、フロー検索処理の説明図を示す。
一般に、ルータ等のネットワーク中継装置は、予めコネクションを設定していないので、ＡＴＭ交換機の場合のコネクション情報テーブルやコネクション情報テーブル内のＱｏＳ制御情報を持っていない（パケット型通信）。このため、ルータでＱｏＳ制御を行うためには、ＡＴＭ交換機と同様の優先転送機能の他に、入力パケット毎にヘッダ内の情報等によりＱｏＳ制御情報を検索するフロー検索手段が必要となる。ここでは、一例として、フロー検索手段により、検索されたＱｏＳ制御情報に対し優先転送機能を適用する。なお、ここでは、ヘッダ内の情報等の情報を組み合わせて作成したパケット識別の条件をフロー条件と呼び、フロー条件に一致する一連のトラヒックをフローと呼び、また、フロー条件に入力パケットが一致するか否かを判定してＱｏＳ制御情報や転送可否情報等のアクション情報を検出することをフロー検索と呼ぶ。
【００４１】
本実施の形態では、ＱｏＳ制御を入力側ルーティング処理部１０−１及び出力側ルーティング処理部１０−２に、それぞれ設けると共に、スイッチ部２０にＱｏＳ機能を持たせるようにした。入力ルーティング処理部１０−１では、入力検索フローとしてフィルタフロー検索９１１、トンネルフロー検索９１２、ＱｏＳフロー検索９１３を備える。同様に、出力ルーティング処理部１０−２では、出力検索フローとしてフィルタフロー検索９２１、トンネルフロー検索９２２、ＱｏＳフロー検索９２３を備える。スイッチ部２０は、優先度により送信する順序を選択するアービトレーション機能を備えることで、ＱｏＳ機能を持たせるようにした。なお、スイッチ部２０にも、ルーティング処理部１０−１及び１０−２と同様に、フィルタフロー検索、トンネルフロー検索、ＱｏＳフロー検索を備えることもできる。
【００４２】
フィルタフロー検索９１１及び９２１では、パケットを通過させるか又は廃棄するかを求める。トンネルフロー検索９１２及び９２２では、パケットをカプセル化するか否かを求め、カプセル化する場合は、カプセル化のソフトウェア処理を実行する。
【００４３】
ＱｏＳフロー検索９１３及び９２３では、例えば、パケットの優先制御、廃棄制御、帯域制御等がある。優先制御とは、重要度の高いデータやリアルタイム系データ等を優先的に送信する制御である。廃棄制御とは、トラフィックが多い場合・障害発生等において、重要度の低いデータを廃棄することにより、重要なデータの消失を防止する制御である。また、帯域制御とは、回線内を複数の帯域に分割したり、帯域幅を変更する制御である。たとえば、優先クラスと廃棄クラスのマトリクスを用いてトラフィック制御することで、優先及び廃棄制御を行うことができる。この場合、優先クラスにより、例えば、ＨＮＡ／ＳＮＡ、音声、動画等は遅延小とし、ＦＴＰ、メール、ＷＷＷウェブ等は、遅延大とする制御を行うことができる。また、廃棄クラスにより、例えば、制御パケットは廃棄率を小さくし、音声、動画等は、廃棄率を大とするように制御することができる。
【００４４】
つぎに、スイッチ部２０でのＱｏＳ制御について説明する。ルーティング処理部１０から送られてきたパケットには、制御情報中にＱｏＳ制御情報が含まれている。スイッチ部２０では、特に出力側において、このＱｏＳ情報による優先制御等を行う。実際には、例えば、優先順位毎にキューを備えて出力制御を行うこと等により制御が可能である。これにより、一段と高品質の通信及び転送を行うことができる。
【００４５】
図１０に、フロー検索テーブルの説明図を示す。
このフロー検索テーブルは、上述のフィルタ／ＱｏＳテーブル１７に対応するものである。ここでは、一例として、図示のように、比較フィールド１０１として、転送元ＩＰアドレス、宛先ＩＰアドレス、パケット長、ＩＰ優先度、ＩＰ上位プロトコル、送達確認フラグ、転送先ＴＣＰ／ＵＤＰポート、宛先ＴＣＰ／ＵＤＰポートを含む。また、アクションフィールド１０２としては、フィルタ（通過／廃棄）、トンネル（カプセル化する／しない）、ＱｏＳ（遅延クラス、廃棄クラス、帯域等）が記憶されている。
【００４６】
次に、ＱｏＳフロー検索の具体的方法を説明する。ここでは、一例としてＱｏＳフロー検索に注目して説明するが、フィルタフロー検索又はトンネルフロー検索についても、同様に実施することができる。なお、アクションフィールド１０２には、これら各フローの制御情報が混在して記憶されていても良いし、また、各フロー毎にフロー検索テーブルが設けられるようにしても良い。
【００４７】
まず、リニアサーチ方式について説明する。アクションのひとつとしてのパケットのＱｏＳ制御情報を判定する際、予め設定されたエントリをエントリテーブルの上から順に読みだす。そして、パケットのヘッダ部等の値とエントリの比較フィールド１０１内の有効なフロー条件に全て一致したか否か判定する。なお、一致した場合にはエントリ内のアクションフィールド１０２内のＱｏＳ制御情報をパケットのＱｏＳ制御情報と判定し、ＱｏＳフロー検索を終了する。フロー条件に一致する場合が検索されると、アクションフィールド１０２内のＱｏＳ制御情報をＱｏＳ制御情報と決定し次のエントリの検索を実行せずフロー検索を終了する。
【００４８】
以上のようなリニアーサーチ方式では、大量のエントリが設定されるネットワークにおいては高速にＱｏＳ制御やフィルタリングを実行することが困難となる場合がある。そこで、本実施の形態のフロー検索方式では、大量のエントリが設定された場合でも、リニアサーチ方式と比較して高速にフロー検索を行うことができる、入力回線限定方式等を採用するとよい。以下、入力回線限定方式の概要を説明する。入力回線限定方式では、リニアーサーチ方式の比較フィールドを構成する入力回線番号に一致するエントリだけを検索し、高速化を図るようにする。
【００４９】
図１１に、第１の入力回線限定方式の説明図を示す。第１の入力回線限定方式においては、リニアーサーチ方式の比較フィールドから入力回線番号と入力回線番号有効ビットを削除したエントリ５１１−ｉを入力回線毎に設定しておく。フロー条件部５２１−ｉは、例えば、送信元あるいは宛先ユーザを識別する条件はSIPとDIPの上限値と下限値であるSIP上限値５０１、SIP下限値５０２、DIP上限値５０３、DIP下限値５０４と、SIPとDIPの上限値と下限値が有効であることを示すIP有効ビット５６２と、送信元ポートであるSPORT５０５と、宛先ポートであるDPORT５０６と、前記SPORT５０５とDPORT５０６が有効であることを示すポート有効ビット５６３等を含む。ＱｏＳ制御情報部５３０−ｉは、例えば、優先転送機能で使用するＱｏＳ制御情報であるＱｏＳ制御情報５０７を含む。フロー条件である入力回線番号が一致したエントリ５１１−ｉだけ検索するためエントリ５１１−ｉ内に入力回線番号は必要ない。フロー検索時には、パケットが入力した入力回線に割り当てられたエントリ５１１−ｉのみ検索する。
【００５０】
ここで、上述の第１の入力回線限定方式では、入力回線番号に関係ないエントリ５１１−ｉを設定する（例えば「全ての入力回線から入力されたＴｅｌｎｅｔのトラヒックは高優先」と設定する）場合、エントリ５１１−ｉを入力回線数（＝Ｎ）設定する必要があり、エントリテーブルを実現するメモリの効率が悪くなる場合がある。そこで、以下に、一層高速な入力回線限定方式について説明する。
【００５１】
図１２に、第２の入力回線限定方式の説明図を示す。第２の入力回線限定方式では、エントリテーブル７５０のアドレスであるリスト５４０を、入力回線毎にリストテーブル７６０に設定しておく。例えば、リストテーブルアドレスが”１”のリスト５４０−１１はエントリ５１１−１のアドレスであり、リストテーブルアドレスが”２”のリスト５４０−１２はエントリ５１１−Ｈのアドレスである。フロー検索時には、パケットが入力された入力回線に割り当てられたリスト５４０だけ読みだし、このリスト５４０がポイントするエントリ５１１−ｉを読み出す。ビット幅の小さなリスト５４０（例えば、１０２４エントリ持った時にも１０ｂｉｔ程度）を入力回線毎に所持し、ビット幅の大きなエントリ５１１−ｉを各入力回線で共有すれば、エントリテーブルを実現するメモリを有効に使用することができる。このため、高速化を実現しつつ、多数のエントリ５１１−ｉを設定することが可能となる。
【００５２】
フロー検出方式の他の実施例として出力回線限定方式がある。出力回線限定方式では、フロー条件である出力回線番号が一致するエントリ５１１−ｉのみを、上述の入力限定方式と同様に処理することで、フロー検出の高速化を実現する。また、フロー条件としてヘッダ情報内の入力回線番号の代わりにSAMACを用いた際のSAMAC限定方式がある。SAMAC限定方式では、SAMACのグループであるSAMACグループを定義し、SAMACグループの識別子であるSAMAC識別子でエントリを限定することで、上述の入力限定方式と同様にフロー検索を実行することができる。
【００５３】
【発明の効果】
本発明によると、高通信品質（ＱｏＳ）、高信頼性、セキュリティーを保証して高速にルーティングするネットワーク中継装置及び方法を提供することができる。また、本発明によると、転送エンジン及び検索エンジン等の機能ブロック毎にハードウェア処理を行うことで、ルーティング及びパケット転送を高速に行うことができる。また、本発明によると、独立にアクセスできる複数のテーブルを設けるとともに、ルーティング処理を、独立に処理される受信処理、送信処理、入力検索処理及び出力検索処理に分割し、必要なテーブルを独立に使用することで、高速にルーティングを行うことができる。さらに、本発明では、パイプライン制御により各処理を実行することにより、一層の高速化を実現することができる。
【図面の簡単な説明】
【図１】本発明に係るネットワーク中継装置の構成図。
【図２】ルーティング処理部の内部構成を表したネットワーク中継装置の動作説明図。
【図３】ネットワーク中継装置の動作概要のシーケンス図。
【図４】パケットバッファ及びヘッダＲＡＭの説明図。
【図５】経路検索に用いられる各テーブルの説明図。
【図６】ルーティング処理部による高速化処理の説明図。
【図７】ハードウェアによる検索エンジンの構成図。
【図８】パイプライン制御による高速処理の説明図。
【図９】フロー検索処理の説明図。
【図１０】フロー検索テーブルの説明図。
【図１１】第１の入力回線限定方式の説明図。
【図１２】第２の入力回線限定方式の説明図。
【図１３】従来のネットワーク中継装置の構成図。
【符号の説明】
１    ネットワーク中継装置
１０  ルーティング処理部
２０  スイッチ部
３０  ネットワークインタフェース部
４０  ポート
５０  ネットワーク
６０  ルーティング管理部
【図１】
0003645734.tif 000002
【図２】
0003645734.tif 000003
【図３】
0003645734.tif 000004
【図４】
0003645734.tif 000005
【図５】
0003645734.tif 000006
【図６】
0003645734.tif 000007
【図７】
0003645734.tif 000008
【図８】
0003645734.tif 000009
【図９】
0003645734.tif 000010
【図１０】
0003645734.tif 000011
【図１１】
0003645734.tif 000012
【図１２】
0003645734.tif 000013
【図１３】
0003645734.tif 000014