ネットワーク中継装置
【課題】パケットの転送処理機構、検索処理機構を並列化し、ハードウエア要素の高速化以上にネットワーク中継装置全体の中継処理性能を向上させる。
【解決手段】ルータ内でパケットの転送処理を行うパケット転送ユニット４４００〜４４０７を並列化し、並列化した各パケット転送ユニット４４００〜４４０７へパケットを振り分けるパケット振り分けユニット４４２０、４４２２と、パケット転送ユニット４４００〜４４０７の出力を再配列するパケット再配列ユニット４４２１、４４２３を設ける。さらに、パケット転送ユニット４４００〜４４０７内でパケットヘッダを検索するパケット検索ユニットを並列化する。
【解決手段】ルータ内でパケットの転送処理を行うパケット転送ユニット４４００〜４４０７を並列化し、並列化した各パケット転送ユニット４４００〜４４０７へパケットを振り分けるパケット振り分けユニット４４２０、４４２２と、パケット転送ユニット４４００〜４４０７の出力を再配列するパケット再配列ユニット４４２１、４４２３を設ける。さらに、パケット転送ユニット４４００〜４４０７内でパケットヘッダを検索するパケット検索ユニットを並列化する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク中継装置に係る。本発明は、特に、コンピュータネットワークシステムにおけるルータ、リピータ等のネットワーク中継装置において、入力されたパケットの転送先を高速に検索することができるネットワーク中継装置に関する。
【背景技術】
【０００２】
一般にネットワークシステムにおいては、複数のネットワーク間を接続するためにルータやブリッジ等のネットワーク中継装置が用いられる。ルータは、接続されているネットワークから受け取ったパケットの宛先アドレスを調べてパケットの転送先を決定し、転送先のルータ又はホストが接続されたネットワークにパケットを転送する。
【０００３】
ルータは、ネットワークインターフェースボードからパケットを入力する毎にパケットのヘッダ情報に含まれるパケットの宛先情報からそのパケットをどのインターフェースに出力するかを決定し、さらに、出力するインターフェースに接続されるホスト又はルータの内、どのホストまたはルータに転送するかを決定して、パケットを転送する。さらに高機能のルータでは、パケットを転送するだけでなくパケットヘッダ条件に従いパケットの廃棄を行う機能（フィルタリング機能）、複数のパケットを転送するときにパケットの出力優先度を決定し、パケットの優先度の順にパケットを出力する機能（優先制御機能）、パケットヘッダ内の優先度情報（ＴｏＳ）を書き換える機能等を実行する。
【０００４】
さらに、一般にルータは統計機能を有しており、転送を行ったパケット数およびバイト数、ルータ内でフィルタリングやルータ内のパケットの輻輳により廃棄したパケット数、パケットの出力先の検索（経路検索）の結果、どこに出力するかが定義されていなかったパケットの数（経路無し）、ルータ自身に宛てたパケットの数や、フィルタリングの廃棄条件に一致したパケット数等を数えている。これらの統計情報は、ルータの操作や状態表示等の管理を行う端末に表示したり、ネットワーク内に存在するネットワーク管理装置に送られ、ネットワークの管理に使用される。
【０００５】
また、統計機能ではないが、パケットのデータ転送バイト数の測定が必要な場合として、ネットワーク業者がユーザからのパケットを受信する時にパケットのヘッダ条件に従いパケットを分類し（例えば、ソース・デスティネーションのサブネット、ＴＣＰ／ＩＰのポート番号、アドレス等）、この分類（以後フローと呼ぶ）毎にデータ転送速度の監視を行い、このフローのデータ転送速度がこのフローを流しているユーザとの間で契約している帯域以上のパケットを廃棄したり輻輳時に優先して廃棄するようにする機能（帯域監視機能）、または、ネットワークユーザがネットワーク業者のネットワークにパケットを送信する時にルータから各フローに属するパケットデータを出力する速度をネットワーク業者との間で契約している帯域以内に制限する機能（シェーピング機能）がある。帯域監視機能またはシェーピング機能を実現するためには、ルータを流れるパケットの一定時間毎のデータ転送バイト数（データ転送速度）を測定する必要がある。
【０００６】
ルータの処理内容には、ルータにパケットが入ってくる毎に行う必要がある上述のような処理と、ルータ間でネットワークシステム内の経路情報をやりとりしルータ内に経路テーブルを作成するという処理や、ネットワーク管理装置との間でのルータの統計情報のやり取りのようにルータにパケットが入ってくる毎には行う必要がない処理がある。
【０００７】
従来、上記ルータの処理はソフトウエア処理により行われており、ルータにパケットが入ってくる毎に必要となる処理の性能向上のため、この処理を行うユニット（ＲＰ： Ｒｏｕｔｉｎｇ Ｐｒｏｃｅｓｓｏｒ）をルータ内に複数設け、各ＲＰ毎にネットワークインターフェースボードを接続し、別々のＲＰの配下に繋がるネットワークインターフェースボード間でパケットを転送するためにＲＰ間をバスまたはクロスバースイッチにより接続することにより高速化が図られていた。このようなルータの例として、例えば、池田、他の特開平５−１９９２３０号公報「インタネットワーク装置及び通信ネットワークシステム」等が挙げられる。
しかし、さらにネットワークを流れるトラフィックが増大しルータ処理を高速化する必要性が出てきた結果、ソフトウエア処理により実現されていたルータ処理をハードウエア処理で置き換えるということが行われるようになってきた。このようなルータの例として、日経エレクトロニクス１９９９年１１月２日号ｐｐ．３５−３６に示す日立製作所のルータ「ＧＲ２０００］等が挙げられる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平５−１９９２３０号公報
【非特許文献】
【０００９】
【非特許文献１】日経エレクトロニクス１９９９年１１月２日号ｐｐ．３５−３６
【発明の概要】
【発明が解決しようとする課題】
【００１０】
近年のネットワークを流れるトラフィックは、ＬＳＩ製造技術等のハードウエアの要素技術の進歩により実現できる処理能力の向上以上のペースで増大し続けており、ルータやブリッジがネットワークインターフェースボードからパケットを入力する毎に行う処理をハードウエア化するだけでは増大するネットワークトラフィックを処理しきれない。
本発明は、以上の点に鑑み、ルータの処理を行うハードウエアを並列化することにより、ＬＳＩ製造技術等のハードウエアの要素技術の進歩により実現できる処理能力の向上以上にルータのトータル性能を上げ、近年の増大し続けるネットワークトラフィックを十分に処理することができるネットワーク中継装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の特徴のひとつとしては、ルータ内にパケットの入出力のインターフェースを行うネットワークインターフェースボード（ＮＩＦ： Ｎｅｔｗｏｒｋ Ｉｎｔｅｒｆａｃｅ Ｂｏａｒｄ）、パケットのヘッダ情報からパケットの転送先を検索しパケットを転送するルーティングプロセッサ（ＲＰ： Ｒｏｕｔｉｎｇ Ｐｒｏｃｅｓｓｏｒ）、各ＲＰの制御およびルーティングプロトコル等の制御パケットの送受信を行うルーティングマネージャ（ＲＭ： Ｒｏｕｔｉｎｇ Ｍａｎａｇｅｒ）、および、各ＲＰおよびＲＭを接続しＲＰ間およびＲＭ、ＲＰ間のパケットの転送を行うクロスバスイッチ（ＣＳＷ： Ｃｒｏｓｓ ｂａｒ Ｓｗｉｔｃｈ）を設け、パケットのヘッダ情報からパケットの宛先を検索しパケットを転送するという処理を実行するパケット転送ユニットを各ＲＰ内に複数個設け、ＮＩＦから入ってきたパケットおよびＣＳＷから入ってきたパケットを、パケット単位にパケット転送ユニットに振り分けるようにする。
パケット転送ユニットが行う処理を限定しパケット転送ユニットの構成を簡単化するためには、ＮＩＦから入ってきたパケットをＣＳＷに転送する処理を行うパケット転送ユニットと、ＣＳＷ経由で入ってきたパケットをＮＩＦに転送する処理を行うパケット転送ユニットを別々に設けるようにすればよい。また、パケット転送ユニットが処理を行わないアイドル時間を短くしパケット転送ユニット当りのルータの処理性能を向上させるためには、各パケット転送ユニットにＮＩＦからＣＳＷへの転送とＣＳＷからＮＩＦへの転送のどちらの転送処理も行わせるようにすればよい。
【００１２】
本発明の他の特徴のひとつとしては、各ＲＰがＮＩＦまたはＣＳＷから入ってきたパケットを各ＲＰ内の複数のパケット転送ユニットに振り分けるために、転送パケット振り分けユニットを設け、この転送パケット振り分けユニットは、パケットが入ってきた順にパケット転送ユニットに順番に振り分ける方法（ラウンドロビン法）か、空いているパケット転送ユニットに振り分ける方法（アウトオブオーダ法）か、パケットのヘッダ条件から振り分けるパケット転送ユニットを一意に決定する方法（ハッシュ法）によりパケットを振り分けるようにする。
ハッシュ法でパケットの転送先を決定する関数（ハッシュ関数）には、パケットの転送元から転送先に連続して送られる一連のパケットは全て同じパケット転送ユニットに振り分ける、という条件を設けることができる。さらに、各パケット転送ユニットにパケットができるだけ均等に振り分けられるように、ハッシュ関数としてパケットヘッダ条件から作成された擬似乱数を使用するようにすることができる。
【００１３】
また、本発明の他の特徴のひとつとして、各ＲＰ内に、ＲＰ内の複数のパケット転送ユニットが転送処理を行ったパケットを再び配列してＮＩＦまたはＣＳＷに送出する転送パケット再配列ユニットを設ける。
転送パケット振り分けユニットの振り分け法がラウンドロビン法またはアウトオブオーダ法の場合には、ＲＰ内の複数のパケット転送ユニットがパケット転送処理を終了する順番が、パケットの転送元から転送先に連続して送られる一連のパケットの間で逆転することが有り得るので、転送パケット再配列ユニットは、各パケット転送ユニットがパケット転送処理を終了したパケットをパケットが入ってきた順に並べ直す。転送パケット振り分けユニットの振り分け法がアウトオブオーダ法の場合には、転送パケット再配列ユニットがルータにパケットが入ってきた順番にパケットを再配列するために、転送パケット振り分けユニットがパケット転送ユニットにパケットを振り分ける時点で各パケットにシーケンス番号を付け、シーケンス番号とパケットとを一緒にパケット転送ユニットの中を持ち回り、転送パケット再配列ユニットはパケットに付けられたシーケンス番号の順にパケットを再配列してパケットを送出するようにする。
【００１４】
また、本発明のさらに他の特徴のひとつとしては各パケット転送ユニット内には、転送パケット振り分けユニットからパケットを受けてからパケット転送処理を開始するまでの間待つためのキューである転送パケット処理待ちキューと、パケット転送処理ユニットが処理を終了してから転送パケット再配列ユニットにパケットを送出するまでの間待つためのキューである転送パケット再配列処理待ちキューを設けるようにする。
パケット転送ユニットが行う処理の内、パケットヘッダの検索を並列化して高速化を図るためには、一つのパケット転送ユニット内にパケットヘッダの検索処理を行うパケット検索ユニットを複数個設けるようにすることができる。また、パケット転送ユニット内でパケットのヘッダの抽出を行うパケットヘッダ操作機構がパケットのヘッダ情報を抽出するようにし、抽出したパケットヘッダを各パケット検索ユニットに振り分ける検索パケット振り分けユニットを設け、各パケット検索ユニットはパケットのヘッダ情報に基づきパケットの転送先、パケットを廃棄するか転送するかの検索（フィルタリング検索）、および、パケットを出力するときの出力順の優先順位（通信品質検索）を行い、パケットの転送先、パケットを廃棄するか否かの情報、パケットの出力優先順位を返すようにし、各パケット検索ユニットの検索結果を再び配列してパケットヘッダ操作機構に渡す検索パケット再配列ユニットを設けるようにすることができる。
さらに高速化を図るためには、パケット転送ユニットの並列化とパケット検索ユニットの並列化を同時に実行することもできる。
【００１５】
さらに、本発明の他の特徴のひとつとしては、複数のパケット転送ユニットまたは複数のパケット検索ユニットにそれぞれ採取された統計情報を集計しルータ全体の統計情報として管理端末に表示する、あるいはネットワーク管理装置に送るために、ルータ全体を管理するソフトウエアが各パケット転送ユニットまたはパケット検索ユニット内の統計情報を読み、ソフトウエア処理により集計するようにすることができる。あるいは、各ＲＰ毎にプロセッサを設け、このプロセッサ上で動作するソフトウエアが各パケット転送ユニットまたはパケット検索ユニット内の統計情報を読み、ソフトウエア処理により集計するようにすることができる。
また、本発明のさらに他の特徴のひとつとしては、パケットのヘッダ条件毎にパケットを分類し、この分類（以後フローと呼ぶ）毎にデータ転送速度を測定し、データ転送速度に従いパケットを廃棄したり輻輳時にパケットを廃棄され易くするため、あるいはパケットの送出時にパケットの送出速度を制限するために、フローに番号を付け、各データ転送ユニットまたは各データ検索ユニットからフローの番号を出力し、転送パケット再配列ユニットまたは検索パケット再配列ユニット内で、フローの番号毎にフローのデータ転送速度を測定するようにすることができる。
【発明の効果】
【００１６】
本発明によると、パケットのヘッダ情報からパケットの宛先を検索しパケットを転送するという処理を実行するパケット転送ユニットを各ＲＰ内に複数個設け、ＮＩＦから入ってきたパケットおよびＣＳＷから入ってきたパケットを、パケット単位にパケット転送ユニットに振り分けることにより、パケットの転送処理ユニットの並列度に応じパケット転送処理を高速化できる。
本発明によると、ＮＩＦから入ってきたパケットをＣＳＷに転送する処理を行うパケット転送ユニットと、ＣＳＷ経由で入ってきたパケットをＮＩＦに転送する処理を行うパケット転送ユニットを別々に設けることにより、それぞれのパケット転送ユニットが行う処理が限定され、パケット転送ユニットの構成を簡単化できる。本発明によると、各パケット転送ユニットにＮＩＦからＣＳＷへの転送とＣＳＷからＮＩＦへの転送のどちらの転送処理も行わせるようにすることにより、各パケット転送ユニットが処理をしていない時間を少なくしパケット転送ユニット当りのルータの処理性能を向上できる。
【００１７】
本発明によると、転送パケット振り分けユニットのパケット振り分け方法として、パケットが入ってきた順にパケット転送ユニットに順番に振り分ける方法（ラウンドロビン法）を採用することにより、パケットの振り分け方法が簡単であり実現が容易とすることができる。また、本発明によると、空いているパケット転送ユニットに振り分ける方法（アウトオブオーダ法）を採用することにより、パケット転送ユニットのパケット処理時間がパケット毎にばらついた場合でも、パケット転送ユニットのアイドル時間を短くし、ルータのトータル性能として見たときのパケット転送ユニット当りのパケット転送処理性能を良くすることができる。さらに、本発明によると、パケットのヘッダ条件から振り分けるパケット転送ユニットを一意に決定する方法（ハッシュ法）を採用することにより、パケットの転送元から転送先に連続して送られる一連のパケットが全て同じパケット転送ユニットに振り分けるので、パケットを送出する前にパケットの順番を再配列しなくてもパケットの追い抜きが発生しないようにすることができる。さらに、ハッシュ法において、各パケット転送ユニットにパケットができるだけ均等に振り分けられるように、ハッシュ関数としてパケットヘッダ条件から作成された擬似乱数を使用することにより、パケット転送ユニット間での処理パケット数の時間的ばらつきを抑えることができる。
本発明によると、パケット再配列ユニットは、各パケット転送ユニットが出力したパケットをＲＰへのパケットの入力順に再配列するので、パケットの追い抜きが発生しないようにできる。また、パケットの振り分け法がアウトオブオーダ法の場合に、パケットの振り分け時にパケットにシーケンス番号を付け、パケット転送ユニット内をパケットと共に持ち回ることにより、パケット再配列ユニットがパケットの入力順を知ることができ、パケットを入力順に再配列するこができる。
【００１８】
本発明によると、各パケット転送ユニット内に転送パケット振り分けユニットからパケットを受けてからパケット転送処理を開始するまでの間待つためのキュー、および、パケット転送処理ユニットが処理を終了してから転送パケット再配列ユニットにパケットを送出するまでの間待つためのキューを設けることにより、各パケット転送ユニットの各パケットの処理時間の長短、および、転送パケット振り分けユニットの振り分け方がハッシュ法の場合に各パケット転送ユニットにパケットを振り分けるときの時間的偏りを吸収し、各パケット転送ユニットが処理をしていない時間を少なくしパケット転送ユニット当りのルータの処理性能を向上できる。
本発明によると、パケット転送ユニットでなく、パケット転送ユニットが行う処理の内、パケットヘッダの検索処理という限定された処理だけを行うパケット検索ユニットのみを並列化することにより、ハードウエアの増加を抑えつつ、パケット毎に必要となる処理の内複雑でボトルネックになり易い処理であるパケットヘッダ検索処理を高速化できる。
【００１９】
本発明によると、パケット転送ユニットの並列化とパケット検索ユニットの並列化を同時に実行することにより、ルータ内でパケット毎に必要となる処理の並列度を、パケット転送ユニットの並列度とパケット検索ユニットの並列度まで高めることができ、ルータのトータル性能をさらに上げることができる。
本発明によると、複数のパケット転送ユニットまたは複数のパケット検索ユニットのそれぞれに統計情報を採取し、ルータ全体を管理するソフトウエアが各パケット転送ユニットまたはパケット検索ユニット内の統計情報を読み、ソフトウエア処理により集計するか、あるいは、各ＲＰ毎にプロセッサを設け、このプロセッサ上で動作するソフトウエアが各パケット転送ユニットまたはパケット検索ユニット内の統計情報を読み、ソフトウエア処理により集計することにより、ルータ全体としての統計情報を得ることができる。
【００２０】
本発明によると、複数のパケット転送ユニットまたは複数のパケット検索ユニットのそれぞれが、パケットのヘッダ条件毎にパケットを分類し、この分類（以後フローと呼ぶ）に番号を付け、各データ転送ユニットまたは各データ検索ユニットからフローの番号を出力し、転送パケット再配列ユニットまたは検索パケット再配列ユニット内で、フローの番号毎にフローのデータ転送速度を測定することにより、全パケット転送ユニット、あるいは全パケット検索ユニットで処理したトータルとしてのフロー毎のデータ転送速度を測定でき、データ転送速度に従いパケットを廃棄したり輻輳時にパケットを廃棄され易くすること、あるいはパケットの送出時にパケットの送出速度を制限することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明のルータが適用されるネットワークシステム全体図。
【図２】本発明のルータ全体の内部構成ブロック図。
【図３】パケット転送ユニットを並列化した本発明のルーティングプロセッサ内部ブロック図（転送方向によりパケット転送ユニットを独立に持つ場合のブロック図）。
【図４】パケット転送ユニットを並列化した本発明のルーティングプロセッサ内部ブロック図（一つのパケット転送ユニットが、両方向のパケット転送処理を行う場合のブロック図）。
【図５】本発明のパケット転送ユニットの内部ブロック図。
【図６】本発明のパケット検索ユニットを並列化しない場合のパケット転送ユニットとその内部のパケット転送処理機構の内部ブロック図。
【図７】本発明のパケット検索ユニットを並列化した場合のパケット転送ユニットとその内部のパケット転送処理機構の内部ブロック図。
【図８】本発明のパケット検索ユニットの内部ブロック図。
【図９】本発明のパケット検索ユニット内で採取した統計情報をルーティングプロセッサ内が読み出し集計するという処理を表す概念図。
【図１０】本発明の複数のパケット検索ユニットが検索したフロー番号に従い検索パケット再配列ユニットがフロー毎の転送速度を測定する部分を抜粋したパケット転送処理機構の内部ブロック図。
【図１１】本発明の転送パケット振り分けユニットの振り分け方法がラウンドロビン法の場合のパケット転送ユニットのパケット転送処理を表すタイムチャート。
【図１２】本発明の転送パケット振り分けユニットの振り分け方法がアウトオブオーダ法の場合のパケット転送ユニットのパケット転送処理を表すタイムチャート。
【図１３】本発明の転送パケット振り分けユニットの振り分け方法がハッシュ法の場合のパケット転送ユニットのパケット転送処理を表すタイムチャート。
【図１４】フロー検索テーブルの説明図。
【図１５】第１の入力回線限定方式の説明図。
【図１６】第２の入力回線限定方式の説明図。
【発明を実施するための形態】
【００２２】
図１に、本発明のルータ装置が適用されるネットワークシステム全体の概念図を示す。図１において、パケットの送信元および受信先になり得るホスト１、２および３、パケットのヘッダ内に記述されている宛先アドレスに従いパケットを転送するルータ４および５、ホストおよびルータが直接接続され、ホストおよびルータ間のデータを伝送するサブネットワーク６、７および８が示される。ルータ４および５もパケットの送信元および受信先になり得る。
【００２３】
例えば、ホスト１からホスト２にパケットを転送する場合、ホスト１はインターフェース１０からサブネットワーク６を介して繋がるルータ４に向かってパケットを送出する。ルータ４はサブネットワーク６に繋がるインターフェース４０からパケットを受け取り、インターフェース４１からサブネットワーク７を介して繋がるルータ５に向かってパケットを転送する。同様にルータ５はインターフェース５０からパケットを受け取り、インターフェース５１からサブネットワーク８を介して繋がるホスト２に向かってパケットを転送する。ホスト２はインターフェース２０からパケットを受け取る。サブネットワーク内の特定のルータまたはホストの特定のためにはサブネットワーク内のアドレスが使用される。
【００２４】
図２に、ルータ内部の全体ブロック図を示す。図２においてルータ４は、パケットの入出力のインターフェースを行うネットワークインターフェースボード（ＮＩＦ： Ｎｅｔｗｏｒｋ Ｉｎｔｅｒｆａｃｅ Ｂｏａｒｄ）４５０〜４５５、パケットのヘッダ情報からパケットの転送先を検索しパケットを転送するルーティングプロセッサ（ＲＰ：Ｒｏｕｔｉｎｇ Ｐｒｏｃｅｓｓｏｒ）４４０〜４４２、ルータ全体の管理、各ＲＰの制御、および、ルーティングプロトコル等の制御パケットの送受信を行い経路情報の管理等を行うルーティングマネージャ（ＲＭ： Ｒｏｕｔｉｎｇ Ｍａｎａｇｅｒ）４２、および、各ＲＰおよびＲＭを接続し、ＲＰ間およびＲＭ、ＲＰ間のパケットの転送を行うクロスバスイッチ（ＣＳＷ： Ｃｒｏｓｓ ｂａｒ Ｓｗｉｔｃｈ）４３を備える。各ネットワークインターフェースボード（ＮＩＦ）４５０〜４５５からはネットワークインターフェース４００〜４０５が繋がる。図２のネットワークインターフェース４００〜４０５は、図１のネットワークインターフェース４０、４１に対応するものである。ネットワークインターフェースの種類には、イーサネット等のＬＡＮ（Ｌｏｃａｌ ＡｒｅａＮｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ Ｔｒａｎｓｆｅｒ Ｍｏｄｅ）等があり、各ＮＩＦ４５０〜４５５はインターフェースの種類毎に異なるハードウエアで構成される。
【００２５】
図３および図４にＲＰ ４４０の内部のブロック図を示す。図３および図４は、パケット転送ユニットを並列化した本発明のルーティングプロセッサ内部の構成の２つの例を表す構成図である。パケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）は、ＲＰ内でパケットのヘッダ情報からパケットの宛先を検索し、パケットを転送するという処理を実行するユニットであり、ＲＰ内には負荷分散のために複数個のパケット転送ユニットを設け、ＮＩＦから入ってきたパケットおよびＣＳＷから入ってきたパケットをパケット単位にパケット転送ユニットに振り分けるようにする。図３はＮＩＦから入ってきたパケットを転送するパケット転送ユニット４４００〜４４０３とＣＳＷから入ってきたパケットを転送するパケット転送ユニット４４０４〜４４０７を別々に設ける場合のＲＰの構成例であり、図４は各パケット転送ユニット４４１０〜４４１３がＮＩＦから入ってきたパケットとＣＳＷから入ってきたパケットのどちらの転送処理も行う場合のＲＰの構成例である。
【００２６】
転送パケット振り分けユニット４４２０、４４２２（図３）および４４３０、４４３２（図４）は、ＮＩＦまたはＣＳＷから入ってきたパケットを複数のパケット転送ユニットのいずれかに振り分けるという処理を行うユニットであり、パケットの振り分け方法として、パケットが入ってきた順にパケット転送ユニットに順番に振り分ける方法（ラウンドロビン法）と、空いているパケット転送ユニットに振り分ける方法（アウトオブオーダ法）と、パケットのヘッダ条件から振り分けるパケット転送ユニットを一意に決定する方法（ハッシュ法）等がある。図１１、図１２、図１３にそれぞれ、転送パケット振り分けユニットのパケット振り分け方法が、ラウンドロビン法、アウトオブオーダ法、ハッシュ法の場合の各パケット転送ユニットのパケット転送処理を表すタイムチャートを示す。図１１、１２、１３のタイムチャート内の番号はＲＰへのパケットの入力順を示し、各矩形は各パケット転送ユニットが各パケットを処理している時間を示す。図１１、１２、１３では、処理時間が長く掛かるパケットが奇数番目に入ってきて、処理時間が短いパケットが偶数番目に入ってきた場合の例について示す。
【００２７】
ハッシュ法でパケットの転送先を決定する関数（ハッシュ関数）には、例えば、パケットの転送元から転送先に連続して送られる一連のパケットは全て同じパケット転送ユニットに振り分ける、という条件を設ける。この条件により、パケット毎に転送処理に掛かる時間が異なった場合にパケット転送処理が終了した順にパケットを送出しても、パケットの転送元から転送先に連続して送られる一連のパケットの間で転送元からパケットを送った順に転送先に到着させることができる。
【００２８】
さらに、各パケット転送ユニットにパケットができるだけ均等に振り分けられるように、ハッシュ関数としてパケットヘッダ条件から作成された擬似乱数を使用することもできる。パケット転送ユニットの数が２個の場合のハッシュ関数の例として、３２ビットのソースＩＰアドレスと３２ビットのデスティネーションＩＰアドレスの全ビットの排他的論理和を取る、という方法がある。この場合、全ビットの排他的論理和により得られる１ビットにより２個の転送ユニットの内どちらに振り分けるかを決定する。パケット転送ユニットの数が４個の場合には１ビットでなく２ビットを出力するハッシュ関数を用いる。図１３では１、３番目のパケットがパケット検索ユニット４４１０に振り分けられ、２、４番目が４４１１に、５、７番目が４４１２に、６、８番目が４４１３にそれぞれ振り分けられた場合の例について示している。
【００２９】
転送パケット振り分けユニット４４２０、４４２２（図３）および４４３０、４４３２（図４）の振り分け法がラウンドロビン法またはアウトオブオーダ法の場合には、ＲＰ内の複数のパケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）がパケット転送処理を終了する順番が、パケットの転送元から転送先に連続して送られる一連のパケットの間で逆転することが有り得るので、転送パケット再配列ユニット４４２１、４４２３（図３）および４４３１、４４３３（図４）は、各パケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）がパケット転送処理を終了したパケットをパケットが入ってきた順に並べ直す。また、転送パケット振り分けユニット４４２０、４４２２（図３）および４４３０、４４３２（図４）の振り分け法がアウトオブオーダ法の場合には、転送パケット再配列ユニット４４２１、４４２３（図３）および４４３１、４４３３（図４）がルータにパケットが入ってきた順番にパケットを再配列するために、転送パケット振り分けユニット４４２０、４４２２（図３）および４４３０、４４３２（図４）がパケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）にパケットを振り分ける時点で各パケットにシーケンス番号を付け、シーケンス番号とパケットとを一緒にパケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）の中を持ち回り、転送パケット再配列ユニット４４２１、４４２３（図３）および４４３１、４４３３（図４）はパケットに付けられたシーケンス番号の順にパケットを再配列してパケットを送出する。
【００３０】
また、転送パケット振り分けユニット４４２０、４４２２（図３）および４４３０、４４３２（図４）の振り分け法がハッシュ法の場合には、各パケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）に送られたパケット間でパケットの出力順は前後して良く、転送パケット再配列ユニット４４２１、４４２３（図３）および４４３１、４４３３（図４）はパケット転送処理の終了順にパケットを送出する。複数のパケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）のパケット転送処理が終了していた場合には、パケット転送処理が終了した複数のパケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）間で順番にパケットを送出する。
【００３１】
つぎに、図５に、本発明のパケット転送ユニットの内部構成図を示す。パケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）は、パケットの転送方向、即ちＮＩＦ４５０からＣＳＷ４３向きか、ＣＳＷ４３からＮＩＦ４５０向きかが異なるが内部の処理待ちのためのキューの持ち方は同じであり、図５は、代表してパケット転送ユニット４４００の内部の処理待ちのためのキューの持ち方を示すブロック図を表したものである。図５のパケット転送ユニット４４００内にはパケット転送処理を実行するパケット転送処理機構４４０００、転送パケット振り分けユニット４４２０等が各パケット転送ユニット４４００にパケットを振り分けた後、各パケット転送処理機構４４０００がパケット処理を開始するまで処理を待つためのキューである転送パケット処理待ちキュー４４００１と、各パケット転送処理機構４４０００が処理を終了後、転送パケット再配列ユニット４４２１等がパケットを再配列し出力するまで待つためのキューである転送パケット再配列処理待ちキュー４４００２を備える。
【００３２】
転送パケット処理待ちキュー４４００１および転送パケット再配列処理待ちキュー４４００２は、各パケット転送ユニット４４００等の各パケットの処理時間の長短、および、転送パケット振り分けユニット４４２０等の振り分け方がハッシュ法の場合に各パケット転送ユニット４４００等にパケットを振り分けるときの時間的偏りを吸収し、各パケット転送ユニット４４００等が処理をしていない時間を少なくするという効果がある。
【００３３】
次に、パケット転送ユニット４４００内でパケットの検索処理を行う部分だけを並列化して高速化を図る場合の実施の形態を示す。まず、図６に、パケットヘッダの検索処理を行うパケット検索ユニットを並列化しない場合のパケット転送ユニット４４００およびその内部のパケット転送処理機構４４０００の内部構成図を示す。また、図７に、パケット検索ユニットを並列化した場合のパケット転送ユニット４４００およびその内部のパケット転送処理機構４４０００の内部構成図を示す。
【００３４】
図６のパケット転送処理機構４４０００は、パケットヘッダ操作機構４４００００とパケット検索ユニット４４０００１を備える。パケットヘッダ操作機構４４００００は、パケットのヘッダ部分を抽出し、パケット検索ユニット４４０００１に渡す。パケット検索ユニット４４０００１はパケットヘッダ操作機構４４００００から渡されたパケットヘッダ情報に基づきパケットの転送先、パケットを廃棄するか転送するかの検索（フィルタリング検索）、および、パケットを出力するときの出力順の優先順位（通信品質検索）等を行い、パケットの転送先、パケットを廃棄するか否かの情報、パケットの出力優先順位等の情報をパケットヘッダ操作機構４４００００に渡す。パケットヘッダ操作機構４４００００はパケット検索ユニット４４０００１から渡されたパケットの転送先、パケットを廃棄するか転送するか等の情報に従い、パケットを転送、または廃棄する。
【００３５】
図７に、パケット検索ユニットを並列化した場合の、パケット転送ユニット４４００の構成を示す。このパケット転送ユニット４４００は、パケット転送処理機構４４０００、パケットヘッダ操作機構４４００００、図６のパケット検索ユニット４４０００１に対応するパケット検索ユニット４４０００１〜４４０００４、パケット転送処理機構４４０００が複数のパケット検索ユニット４４０００１〜４４０００４の一つにパケットヘッダの検索処理を振り分ける検索パケット振り分けユニット４４０００５、各パケット検索ユニット４４０００１〜４４０００４の検索結果を再配列する検索パケット再配列ユニット４４０００６を備える。
【００３６】
検索パケット振り分けユニット４４０００５のパケット検索ユニットの振り分け方法には、転送パケット振り分けユニット４４２０、４４２２（図３）、および４４３０、４４３２（図４）と同様、ラウンドロビン法とアウトオブオーダ法とハッシュ法を取り得て、それぞれの振り分け法の特徴も転送パケット振り分けユニットの場合と同様である。検索パケット再配列ユニット４４０００６の再配列方法も、転送パケット再配列ユニット４４２１、４４２３（図３）および４４３１、４４３３（図４）の再配列方法と同様である。
【００３７】
ここで、図８に、本発明のパケット検索ユニットの内部構成図を示す。図７のパケット検索ユニット４４０００１〜４４０００４は内部の処理待ちのためのキューの持ち方は同じであり、図８は、代表してパケット検索ユニット４４０００１の内部の処理待ちのためのキューの持ち方を示すブロック図を表したものである。図８のパケット検索ユニット４４０００１内にはパケット検索処理を実行するパケット検索処理機構４４０００１０、検索パケット振り分けユニット４４０００５が各パケット検索ユニット４４０００１等にパケットを振り分けた後、各パケット検索処理機構４４０００１０がパケット処理を開始するまで処理を待つためのキューである検索パケット処理待ちキュー４４０００１１と、各パケット検索処理機構が処理を終了後、検索パケット再配列ユニットがパケットを再配列し出力するまで待つためのキューである検索パケット再配列処理待ちキュー４４０００１２を備える。
【００３８】
検索パケット処理待ちキュー４４０００１１および検索パケット再配列処理待ちキュー４４０００１２は、各パケット検索ユニット４４０００１等の各パケットの処理時間の長短、および、検索パケット振り分けユニットの振り分け方がハッシュ法の場合に各パケット検索ユニットにパケットを振り分けるときの時間的偏りを吸収し、各パケット検索ユニットが処理をしていない時間を少なくするという効果がある。
【００３９】
次に、上記パケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）またはパケット検索ユニット４４０００１〜４４０００４を並列化した場合の統計情報採取法について示す。例えばパケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）内では転送を行ったパケット数およびバイト数、ルータ内でフィルタリングやルータ内のパケットの輻輳により廃棄したパケット数を数えており、また、パケット検索ユニット４４０００１〜４４０００４内ではパケットの出力先の検索（経路検索）の結果、どこに出力するかが定義されていなかったパケットの数（経路無し）、ルータ自身に宛てたパケットの数や、フィルタリングの廃棄条件に一致したパケット数等を数えている。
【００４０】
本発明ではパケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）またはパケット検索ユニット４４０００１〜４４０００４を並列化しているので上記各統計を各パケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または各パケット検索ユニット４４０００１〜４４０００４内で採取するようにした場合には、図２に示したＲＭ４２上で動作しているソフトウエア、或いは図２に示したＲＰ４４０〜４４２内にプロセッサを搭載し、このプロセッサ上でソフトウエアを動作させ、これらのソフトウエアが各パケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または各パケット検索ユニット４４０００１〜４４０００４内に採取された統計情報を読み、並列化されている全パケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または全パケット検索ユニット４４０００１〜４４０００４に取られた統計情報を足し合わせるようにする。
【００４１】
図９に、本発明のパケット検索ユニット内で採取した統計情報をルーティングプロセッサ内が読み出し集計するという処理を表す概念図を示す。図９では、パケット転送処理機構４４０００内のパケット検索ユニット４４０００１〜４４０００４は、それぞれ統計カウンタ４４０００１３〜４４０００４３を備える。そして、パケット検索ユニット４４０００１〜４４０００４内で採取した統計カウンタ４４０００１３、４４０００２３、４４０００３３、４４０００４３の値をＲＰ ４４０内のプロセッサ４４５がレジスタバスを介して読み、集計する。図９ではパケットの収集に直接関係しない部分は省略してある。
【００４２】
また、統計機能ではないがパケットのデータ転送バイト数の測定が必要な場合として、ネットワーク業者がユーザからのパケットを受信する時にパケットのヘッダ条件に従いパケットを分類し、この分類（以後フローと呼ぶ）毎にデータ転送速度の監視を行い、このフローのデータ転送速度がこのフローを流しているユーザとの間で契約している帯域以上のパケットを廃棄したり輻輳時に優先して廃棄するようにする機能（帯域監視機能）、または、ネットワークユーザがネットワーク業者のネットワークにパケットを送信する時にルータから各フローに属するパケットデータを出力する速度をネットワーク業者との間で契約している帯域以内に制限する機能（シェーピング機能）がある。帯域監視機能またはシェーピング機能を実現するためには、ルータを流れるパケットの一定時間毎のデータ転送バイト数（データ転送速度）を測定する必要がある。
【００４３】
複数のパケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または複数のパケット検索ユニット４４０００１〜４４０００４を並列化した場合には、一つのフローが複数のパケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または複数のパケット検索ユニット４４０００１〜４４０００４に分散されて処理されるので、一つのフロー全体のデータ転送速度を求めるためには、各パケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または各パケット検索ユニット４４０００１〜４４０００４を流れるフローのデータ転送速度を共通の個所に採取する必要がある。一つのフローのデータ転送速度を共通の個所に採取するために、各フローに番号を付け、各データ転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または各データ検索ユニット４４０００１〜４４０００４からパケットヘッダ検索結果の一つとしてフローの番号を出力し、転送パケット再配列ユニット４４２１、４４２３、４４３１、４４３３または検索パケット再配列ユニット４４０００６内で、フローの番号毎にフローのデータ転送速度を測定するようにし、帯域監視機能実現時にはフローのデータ転送速度に従い、（例えば、閾値以上になったら）パケットを廃棄したり、パケットを廃棄されやすくしたりする。さらに、フロー番号毎にトラフィック統計を求めることもできる。また、シェーピング機能実現時にはフローのデータ転送速度がネットワーク業者との間の契約帯域を超えないように出力を制限するようにする。
【００４４】
図１０に、本発明の複数のパケット検索ユニットが検索したフロー番号に従い検索パケット再配列ユニットがフロー毎の転送速度を測定する部分を抜粋したパケット転送処理機構の内部構成図を示す。検索パケット再配列ユニット４４０００６は、フロー番号に対応して、パケット数及びバイト数等のパケットデータ転送速度に関する情報を記憶したフロー毎の転送速度カウンタ４４０００６０を備える。パケット検索ユニット４４０００１〜４４０００４がパケット検索結果の一つとしてフロー番号を含む情報を出力し、検索パケット再配列ユニット４４０００６がフローの番号毎の転送速度カウンタ４４０００６０に各フローのパケットデータ転送速度を測定する。図１０ではフロー毎のパケットデータ転送速度の測定に直接関係しない部分は省略してある。
【００４５】
つぎに、フロー検索について説明する。図１４に、フロー検索テーブルの説明図を示す。このフロー検索テーブルは、一例として、図示のように、比較フィールド１０１として、転送元ＩＰアドレス、宛先ＩＰアドレス、パケット長、ＩＰ優先度、ＩＰ上位プロトコル、送達確認フラグ、転送先ＴＣＰ／ＵＤＰポート、宛先ＴＣＰ／ＵＤＰポートを含む。また、アクションフィールド１０２としては、フィルタ（通過／廃棄）、トンネル（カプセル化する／しない）、ＱｏＳ（遅延クラス、廃棄クラス、帯域等）が記憶されている。
【００４６】
つぎに、ＱｏＳフロー検索の具体的方法を説明する。ここでは、一例としてＱｏＳフロー検索に注目して説明するが、各種フロー検索についても、同様に実施することができる。なお、アクションフィールド１０２には、これら各フローの制御情報が混在して記憶されていても良いし、また、各フロー毎にフロー検索テーブルが設けられるようにしても良い。
【００４７】
まず、リニアサーチ方式について説明する。アクションのひとつとしてのパケットのＱｏＳ制御情報を判定する際、予め設定されたエントリをエントリテーブルの上から順に読みだす。そして、パケットのヘッダ部等の値とエントリの比較フィールド１０１内の有効なフロー条件に全て一致したか否か判定する。なお、一致した場合にはエントリ内のアクションフィールド１０２内のＱｏＳ制御情報をパケットのＱｏＳ制御情報と判定し、ＱｏＳフロー検索を終了する。フロー条件に一致する場合が検索されると、アクションフィールド１０２内のＱｏＳ制御情報をＱｏＳ制御情報と決定し次のエントリの検索を実行せずフロー検索を終了する。
【００４８】
以上のようなリニアーサーチ方式では、大量のエントリが設定されるネットワークにおいては高速にＱｏＳ制御やフィルタリングを実行することが困難となる場合がある。そこで、大量のエントリが設定された場合でも、リニアサーチ方式と比較して高速にフロー検索を行うことができる、入力回線限定方式等を採用するとよい。以下、入力回線限定方式の概要を説明する。入力回線限定方式では、リニアーサーチ方式の比較フィールドを構成する入力回線番号に一致するエントリだけを検索し、高速化を図るようにする。
【００４９】
図１５に、第１の入力回線限定方式の説明図を示す。第１の入力回線限定方式においては、リニアーサーチ方式の比較フィールドから入力回線番号と入力回線番号有効ビットを削除したエントリ５１１−ｉを入力回線毎に設定しておく。フロー条件部５２１−ｉは、例えば、送信元あるいは宛先ユーザを識別する条件はＳＩＰとＤＩＰの上限値と下限値であるＳＩＰ上限値５０１、ＳＩＰ下限値５０２、ＤＩＰ上限値５０３、ＤＩＰ下限値５０４と、ＳＩＰとＤＩＰの上限値と下限値が有効であることを示すＩＰ有効ビット５６２と、送信元ポートであるＳＰＯＲＴ５０５と、宛先ポートであるＤＰＯＲＴ５０６と、前記ＳＰＯＲＴ５０５とＤＰＯＲＴ５０６が有効であることを示すポート有効ビット５６３等を含む。ＱｏＳ制御情報部５３０−ｉは、例えば、優先転送機能で使用するＱｏＳ制御情報であるＱｏＳ制御情報５０７を含む。フロー条件である入力回線番号が一致したエントリ５１１−ｉだけ検索するためエントリ５１１−ｉ内に入力回線番号は必要ない。フロー検索時には、パケットが入力した入力回線に割り当てられたエントリ５１１−ｉのみ検索する。
【００５０】
ここで、上述の第１の入力回線限定方式では、入力回線番号に関係ないエントリ５１１−ｉを設定する（例えば「全ての入力回線から入力されたＴｅｌｎｅｔのトラヒックは高優先」と設定する）場合、エントリ５１１−ｉを入力回線数（＝Ｎ）設定する必要があり、エントリテーブルを実現するメモリの効率が悪くなる場合がある。そこで、以下に、一層高速な入力回線限定方式について説明する。
【００５１】
図１６に、第２の入力回線限定方式の説明図を示す。第２の入力回線限定方式では、エントリテーブル７５０のアドレスであるリスト５４０を、入力回線毎にリストテーブル７６０に設定しておく。例えば、リストテーブルアドレスが”１”のリスト５４０−１１はエントリ５１１−１のアドレスであり、リストテーブルアドレスが”２”のリスト５４０−１２はエントリ５１１−Ｈのアドレスである。フロー検索時には、パケットが入力された入力回線に割り当てられたリスト５４０だけ読みだし、このリスト５４０がポイントするエントリ５１１−ｉを読み出す。ビット幅の小さなリスト５４０（例えば、１０２４エントリ持った時にも１０ｂｉｔ程度）を入力回線毎に所持し、ビット幅の大きなエントリ５１１−ｉを各入力回線で共有すれば、エントリテーブルを実現するメモリを有効に使用することができる。このため、高速化を実現しつつ、多数のエントリ５１１−ｉを設定することが可能となる。
【００５２】
フロー検出方式の他の実施例として出力回線限定方式がある。出力回線限定方式では、フロー条件である出力回線番号が一致するエントリ５１１−ｉのみを、上述の入力限定方式と同様に処理することで、フロー検出の高速化を実現する。また、フロー条件としてヘッダ情報内の入力回線番号の代わりにＭＡＣ（Ｍｅｄｉａ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌ）レイヤーのソースアドレスである。ＳＡＭＡＣを用いた際のＳＡＭＡＣ限定方式がある。ＳＡＭＡＣ限定方式では、ＳＡＭＡＣのグループであるＳＡＭＡＣグループを定義し、ＳＡＭＡＣグループの識別子であるＳＡＭＡＣ識別子でエントリを限定することで、上述の入力限定方式と同様にフロー検索を実行することができる。
【００５３】
なお、図３、図４に示したパケット転送ユニットの並列化と図７に示したパケット検索ユニットの並列化を同時に実行することも可能であり、同時に実行した場合、各ＲＰ内のパケット検索ユニットの並列度は、パケット転送ユニットの並列度とパケット検索ユニットの並列度の掛け算になる。
【産業上の利用可能性】
【００５４】
本発明は、例えば、コンピュータネットワークシステムにおけるルータ、リピータ等のネットワーク中継装置に利用可能である。
【符号の説明】
【００５５】
１〜３ ホスト
４〜５ ルータ
６〜８ サブネットワーク
４００〜４０５ ネットワークインターフェース
４２ ルータ制御部（ＲＭ）
４３ クロスバスイッチ（ＣＳＷ）
４４０〜４４２ ルーティングプロセッサ
４５０〜４５５ ネットワークインターフェースボード（ＮＩＦ）
４４００〜４４０７ パケット転送ユニット
４４２０、４４２２ 転送パケット振り分けユニット
４４２１、４４２３ 転送パケット再配列ユニット
４４１０〜４４１３ パケット転送ユニット
４４３０、４４３２ 転送パケット振り分けユニット
４４３１、４４３３ 転送パケット再配列ユニット
４４０００ パケット転送処理機構
４４００１ 転送パケット処理待ちキュー
４４００２ 転送パケット再配列処理待ちキュー
４４００００ パケットヘッダ操作機構
４４０００１〜４４０００４ パケット検索ユニット
４４０００５ 検索パケット振り分けユニット
４４０００６ 検索パケット再配列ユニット
４４０００１０ パケット検索処理機構
４４０００１１ 検索パケット処理待ちキュー
４４０００１２ 検索パケット再配列処理待ちキュー
４４０００１３、４４０００２３、４４０００３３、４４０００４３ 統計カウンタ
４４５ プロセッサ
４４０００６０ フロー毎の転送速度カウンタ
【技術分野】
【０００１】
本発明は、ネットワーク中継装置に係る。本発明は、特に、コンピュータネットワークシステムにおけるルータ、リピータ等のネットワーク中継装置において、入力されたパケットの転送先を高速に検索することができるネットワーク中継装置に関する。
【背景技術】
【０００２】
一般にネットワークシステムにおいては、複数のネットワーク間を接続するためにルータやブリッジ等のネットワーク中継装置が用いられる。ルータは、接続されているネットワークから受け取ったパケットの宛先アドレスを調べてパケットの転送先を決定し、転送先のルータ又はホストが接続されたネットワークにパケットを転送する。
【０００３】
ルータは、ネットワークインターフェースボードからパケットを入力する毎にパケットのヘッダ情報に含まれるパケットの宛先情報からそのパケットをどのインターフェースに出力するかを決定し、さらに、出力するインターフェースに接続されるホスト又はルータの内、どのホストまたはルータに転送するかを決定して、パケットを転送する。さらに高機能のルータでは、パケットを転送するだけでなくパケットヘッダ条件に従いパケットの廃棄を行う機能（フィルタリング機能）、複数のパケットを転送するときにパケットの出力優先度を決定し、パケットの優先度の順にパケットを出力する機能（優先制御機能）、パケットヘッダ内の優先度情報（ＴｏＳ）を書き換える機能等を実行する。
【０００４】
さらに、一般にルータは統計機能を有しており、転送を行ったパケット数およびバイト数、ルータ内でフィルタリングやルータ内のパケットの輻輳により廃棄したパケット数、パケットの出力先の検索（経路検索）の結果、どこに出力するかが定義されていなかったパケットの数（経路無し）、ルータ自身に宛てたパケットの数や、フィルタリングの廃棄条件に一致したパケット数等を数えている。これらの統計情報は、ルータの操作や状態表示等の管理を行う端末に表示したり、ネットワーク内に存在するネットワーク管理装置に送られ、ネットワークの管理に使用される。
【０００５】
また、統計機能ではないが、パケットのデータ転送バイト数の測定が必要な場合として、ネットワーク業者がユーザからのパケットを受信する時にパケットのヘッダ条件に従いパケットを分類し（例えば、ソース・デスティネーションのサブネット、ＴＣＰ／ＩＰのポート番号、アドレス等）、この分類（以後フローと呼ぶ）毎にデータ転送速度の監視を行い、このフローのデータ転送速度がこのフローを流しているユーザとの間で契約している帯域以上のパケットを廃棄したり輻輳時に優先して廃棄するようにする機能（帯域監視機能）、または、ネットワークユーザがネットワーク業者のネットワークにパケットを送信する時にルータから各フローに属するパケットデータを出力する速度をネットワーク業者との間で契約している帯域以内に制限する機能（シェーピング機能）がある。帯域監視機能またはシェーピング機能を実現するためには、ルータを流れるパケットの一定時間毎のデータ転送バイト数（データ転送速度）を測定する必要がある。
【０００６】
ルータの処理内容には、ルータにパケットが入ってくる毎に行う必要がある上述のような処理と、ルータ間でネットワークシステム内の経路情報をやりとりしルータ内に経路テーブルを作成するという処理や、ネットワーク管理装置との間でのルータの統計情報のやり取りのようにルータにパケットが入ってくる毎には行う必要がない処理がある。
【０００７】
従来、上記ルータの処理はソフトウエア処理により行われており、ルータにパケットが入ってくる毎に必要となる処理の性能向上のため、この処理を行うユニット（ＲＰ： Ｒｏｕｔｉｎｇ Ｐｒｏｃｅｓｓｏｒ）をルータ内に複数設け、各ＲＰ毎にネットワークインターフェースボードを接続し、別々のＲＰの配下に繋がるネットワークインターフェースボード間でパケットを転送するためにＲＰ間をバスまたはクロスバースイッチにより接続することにより高速化が図られていた。このようなルータの例として、例えば、池田、他の特開平５−１９９２３０号公報「インタネットワーク装置及び通信ネットワークシステム」等が挙げられる。
しかし、さらにネットワークを流れるトラフィックが増大しルータ処理を高速化する必要性が出てきた結果、ソフトウエア処理により実現されていたルータ処理をハードウエア処理で置き換えるということが行われるようになってきた。このようなルータの例として、日経エレクトロニクス１９９９年１１月２日号ｐｐ．３５−３６に示す日立製作所のルータ「ＧＲ２０００］等が挙げられる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平５−１９９２３０号公報
【非特許文献】
【０００９】
【非特許文献１】日経エレクトロニクス１９９９年１１月２日号ｐｐ．３５−３６
【発明の概要】
【発明が解決しようとする課題】
【００１０】
近年のネットワークを流れるトラフィックは、ＬＳＩ製造技術等のハードウエアの要素技術の進歩により実現できる処理能力の向上以上のペースで増大し続けており、ルータやブリッジがネットワークインターフェースボードからパケットを入力する毎に行う処理をハードウエア化するだけでは増大するネットワークトラフィックを処理しきれない。
本発明は、以上の点に鑑み、ルータの処理を行うハードウエアを並列化することにより、ＬＳＩ製造技術等のハードウエアの要素技術の進歩により実現できる処理能力の向上以上にルータのトータル性能を上げ、近年の増大し続けるネットワークトラフィックを十分に処理することができるネットワーク中継装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の特徴のひとつとしては、ルータ内にパケットの入出力のインターフェースを行うネットワークインターフェースボード（ＮＩＦ： Ｎｅｔｗｏｒｋ Ｉｎｔｅｒｆａｃｅ Ｂｏａｒｄ）、パケットのヘッダ情報からパケットの転送先を検索しパケットを転送するルーティングプロセッサ（ＲＰ： Ｒｏｕｔｉｎｇ Ｐｒｏｃｅｓｓｏｒ）、各ＲＰの制御およびルーティングプロトコル等の制御パケットの送受信を行うルーティングマネージャ（ＲＭ： Ｒｏｕｔｉｎｇ Ｍａｎａｇｅｒ）、および、各ＲＰおよびＲＭを接続しＲＰ間およびＲＭ、ＲＰ間のパケットの転送を行うクロスバスイッチ（ＣＳＷ： Ｃｒｏｓｓ ｂａｒ Ｓｗｉｔｃｈ）を設け、パケットのヘッダ情報からパケットの宛先を検索しパケットを転送するという処理を実行するパケット転送ユニットを各ＲＰ内に複数個設け、ＮＩＦから入ってきたパケットおよびＣＳＷから入ってきたパケットを、パケット単位にパケット転送ユニットに振り分けるようにする。
パケット転送ユニットが行う処理を限定しパケット転送ユニットの構成を簡単化するためには、ＮＩＦから入ってきたパケットをＣＳＷに転送する処理を行うパケット転送ユニットと、ＣＳＷ経由で入ってきたパケットをＮＩＦに転送する処理を行うパケット転送ユニットを別々に設けるようにすればよい。また、パケット転送ユニットが処理を行わないアイドル時間を短くしパケット転送ユニット当りのルータの処理性能を向上させるためには、各パケット転送ユニットにＮＩＦからＣＳＷへの転送とＣＳＷからＮＩＦへの転送のどちらの転送処理も行わせるようにすればよい。
【００１２】
本発明の他の特徴のひとつとしては、各ＲＰがＮＩＦまたはＣＳＷから入ってきたパケットを各ＲＰ内の複数のパケット転送ユニットに振り分けるために、転送パケット振り分けユニットを設け、この転送パケット振り分けユニットは、パケットが入ってきた順にパケット転送ユニットに順番に振り分ける方法（ラウンドロビン法）か、空いているパケット転送ユニットに振り分ける方法（アウトオブオーダ法）か、パケットのヘッダ条件から振り分けるパケット転送ユニットを一意に決定する方法（ハッシュ法）によりパケットを振り分けるようにする。
ハッシュ法でパケットの転送先を決定する関数（ハッシュ関数）には、パケットの転送元から転送先に連続して送られる一連のパケットは全て同じパケット転送ユニットに振り分ける、という条件を設けることができる。さらに、各パケット転送ユニットにパケットができるだけ均等に振り分けられるように、ハッシュ関数としてパケットヘッダ条件から作成された擬似乱数を使用するようにすることができる。
【００１３】
また、本発明の他の特徴のひとつとして、各ＲＰ内に、ＲＰ内の複数のパケット転送ユニットが転送処理を行ったパケットを再び配列してＮＩＦまたはＣＳＷに送出する転送パケット再配列ユニットを設ける。
転送パケット振り分けユニットの振り分け法がラウンドロビン法またはアウトオブオーダ法の場合には、ＲＰ内の複数のパケット転送ユニットがパケット転送処理を終了する順番が、パケットの転送元から転送先に連続して送られる一連のパケットの間で逆転することが有り得るので、転送パケット再配列ユニットは、各パケット転送ユニットがパケット転送処理を終了したパケットをパケットが入ってきた順に並べ直す。転送パケット振り分けユニットの振り分け法がアウトオブオーダ法の場合には、転送パケット再配列ユニットがルータにパケットが入ってきた順番にパケットを再配列するために、転送パケット振り分けユニットがパケット転送ユニットにパケットを振り分ける時点で各パケットにシーケンス番号を付け、シーケンス番号とパケットとを一緒にパケット転送ユニットの中を持ち回り、転送パケット再配列ユニットはパケットに付けられたシーケンス番号の順にパケットを再配列してパケットを送出するようにする。
【００１４】
また、本発明のさらに他の特徴のひとつとしては各パケット転送ユニット内には、転送パケット振り分けユニットからパケットを受けてからパケット転送処理を開始するまでの間待つためのキューである転送パケット処理待ちキューと、パケット転送処理ユニットが処理を終了してから転送パケット再配列ユニットにパケットを送出するまでの間待つためのキューである転送パケット再配列処理待ちキューを設けるようにする。
パケット転送ユニットが行う処理の内、パケットヘッダの検索を並列化して高速化を図るためには、一つのパケット転送ユニット内にパケットヘッダの検索処理を行うパケット検索ユニットを複数個設けるようにすることができる。また、パケット転送ユニット内でパケットのヘッダの抽出を行うパケットヘッダ操作機構がパケットのヘッダ情報を抽出するようにし、抽出したパケットヘッダを各パケット検索ユニットに振り分ける検索パケット振り分けユニットを設け、各パケット検索ユニットはパケットのヘッダ情報に基づきパケットの転送先、パケットを廃棄するか転送するかの検索（フィルタリング検索）、および、パケットを出力するときの出力順の優先順位（通信品質検索）を行い、パケットの転送先、パケットを廃棄するか否かの情報、パケットの出力優先順位を返すようにし、各パケット検索ユニットの検索結果を再び配列してパケットヘッダ操作機構に渡す検索パケット再配列ユニットを設けるようにすることができる。
さらに高速化を図るためには、パケット転送ユニットの並列化とパケット検索ユニットの並列化を同時に実行することもできる。
【００１５】
さらに、本発明の他の特徴のひとつとしては、複数のパケット転送ユニットまたは複数のパケット検索ユニットにそれぞれ採取された統計情報を集計しルータ全体の統計情報として管理端末に表示する、あるいはネットワーク管理装置に送るために、ルータ全体を管理するソフトウエアが各パケット転送ユニットまたはパケット検索ユニット内の統計情報を読み、ソフトウエア処理により集計するようにすることができる。あるいは、各ＲＰ毎にプロセッサを設け、このプロセッサ上で動作するソフトウエアが各パケット転送ユニットまたはパケット検索ユニット内の統計情報を読み、ソフトウエア処理により集計するようにすることができる。
また、本発明のさらに他の特徴のひとつとしては、パケットのヘッダ条件毎にパケットを分類し、この分類（以後フローと呼ぶ）毎にデータ転送速度を測定し、データ転送速度に従いパケットを廃棄したり輻輳時にパケットを廃棄され易くするため、あるいはパケットの送出時にパケットの送出速度を制限するために、フローに番号を付け、各データ転送ユニットまたは各データ検索ユニットからフローの番号を出力し、転送パケット再配列ユニットまたは検索パケット再配列ユニット内で、フローの番号毎にフローのデータ転送速度を測定するようにすることができる。
【発明の効果】
【００１６】
本発明によると、パケットのヘッダ情報からパケットの宛先を検索しパケットを転送するという処理を実行するパケット転送ユニットを各ＲＰ内に複数個設け、ＮＩＦから入ってきたパケットおよびＣＳＷから入ってきたパケットを、パケット単位にパケット転送ユニットに振り分けることにより、パケットの転送処理ユニットの並列度に応じパケット転送処理を高速化できる。
本発明によると、ＮＩＦから入ってきたパケットをＣＳＷに転送する処理を行うパケット転送ユニットと、ＣＳＷ経由で入ってきたパケットをＮＩＦに転送する処理を行うパケット転送ユニットを別々に設けることにより、それぞれのパケット転送ユニットが行う処理が限定され、パケット転送ユニットの構成を簡単化できる。本発明によると、各パケット転送ユニットにＮＩＦからＣＳＷへの転送とＣＳＷからＮＩＦへの転送のどちらの転送処理も行わせるようにすることにより、各パケット転送ユニットが処理をしていない時間を少なくしパケット転送ユニット当りのルータの処理性能を向上できる。
【００１７】
本発明によると、転送パケット振り分けユニットのパケット振り分け方法として、パケットが入ってきた順にパケット転送ユニットに順番に振り分ける方法（ラウンドロビン法）を採用することにより、パケットの振り分け方法が簡単であり実現が容易とすることができる。また、本発明によると、空いているパケット転送ユニットに振り分ける方法（アウトオブオーダ法）を採用することにより、パケット転送ユニットのパケット処理時間がパケット毎にばらついた場合でも、パケット転送ユニットのアイドル時間を短くし、ルータのトータル性能として見たときのパケット転送ユニット当りのパケット転送処理性能を良くすることができる。さらに、本発明によると、パケットのヘッダ条件から振り分けるパケット転送ユニットを一意に決定する方法（ハッシュ法）を採用することにより、パケットの転送元から転送先に連続して送られる一連のパケットが全て同じパケット転送ユニットに振り分けるので、パケットを送出する前にパケットの順番を再配列しなくてもパケットの追い抜きが発生しないようにすることができる。さらに、ハッシュ法において、各パケット転送ユニットにパケットができるだけ均等に振り分けられるように、ハッシュ関数としてパケットヘッダ条件から作成された擬似乱数を使用することにより、パケット転送ユニット間での処理パケット数の時間的ばらつきを抑えることができる。
本発明によると、パケット再配列ユニットは、各パケット転送ユニットが出力したパケットをＲＰへのパケットの入力順に再配列するので、パケットの追い抜きが発生しないようにできる。また、パケットの振り分け法がアウトオブオーダ法の場合に、パケットの振り分け時にパケットにシーケンス番号を付け、パケット転送ユニット内をパケットと共に持ち回ることにより、パケット再配列ユニットがパケットの入力順を知ることができ、パケットを入力順に再配列するこができる。
【００１８】
本発明によると、各パケット転送ユニット内に転送パケット振り分けユニットからパケットを受けてからパケット転送処理を開始するまでの間待つためのキュー、および、パケット転送処理ユニットが処理を終了してから転送パケット再配列ユニットにパケットを送出するまでの間待つためのキューを設けることにより、各パケット転送ユニットの各パケットの処理時間の長短、および、転送パケット振り分けユニットの振り分け方がハッシュ法の場合に各パケット転送ユニットにパケットを振り分けるときの時間的偏りを吸収し、各パケット転送ユニットが処理をしていない時間を少なくしパケット転送ユニット当りのルータの処理性能を向上できる。
本発明によると、パケット転送ユニットでなく、パケット転送ユニットが行う処理の内、パケットヘッダの検索処理という限定された処理だけを行うパケット検索ユニットのみを並列化することにより、ハードウエアの増加を抑えつつ、パケット毎に必要となる処理の内複雑でボトルネックになり易い処理であるパケットヘッダ検索処理を高速化できる。
【００１９】
本発明によると、パケット転送ユニットの並列化とパケット検索ユニットの並列化を同時に実行することにより、ルータ内でパケット毎に必要となる処理の並列度を、パケット転送ユニットの並列度とパケット検索ユニットの並列度まで高めることができ、ルータのトータル性能をさらに上げることができる。
本発明によると、複数のパケット転送ユニットまたは複数のパケット検索ユニットのそれぞれに統計情報を採取し、ルータ全体を管理するソフトウエアが各パケット転送ユニットまたはパケット検索ユニット内の統計情報を読み、ソフトウエア処理により集計するか、あるいは、各ＲＰ毎にプロセッサを設け、このプロセッサ上で動作するソフトウエアが各パケット転送ユニットまたはパケット検索ユニット内の統計情報を読み、ソフトウエア処理により集計することにより、ルータ全体としての統計情報を得ることができる。
【００２０】
本発明によると、複数のパケット転送ユニットまたは複数のパケット検索ユニットのそれぞれが、パケットのヘッダ条件毎にパケットを分類し、この分類（以後フローと呼ぶ）に番号を付け、各データ転送ユニットまたは各データ検索ユニットからフローの番号を出力し、転送パケット再配列ユニットまたは検索パケット再配列ユニット内で、フローの番号毎にフローのデータ転送速度を測定することにより、全パケット転送ユニット、あるいは全パケット検索ユニットで処理したトータルとしてのフロー毎のデータ転送速度を測定でき、データ転送速度に従いパケットを廃棄したり輻輳時にパケットを廃棄され易くすること、あるいはパケットの送出時にパケットの送出速度を制限することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明のルータが適用されるネットワークシステム全体図。
【図２】本発明のルータ全体の内部構成ブロック図。
【図３】パケット転送ユニットを並列化した本発明のルーティングプロセッサ内部ブロック図（転送方向によりパケット転送ユニットを独立に持つ場合のブロック図）。
【図４】パケット転送ユニットを並列化した本発明のルーティングプロセッサ内部ブロック図（一つのパケット転送ユニットが、両方向のパケット転送処理を行う場合のブロック図）。
【図５】本発明のパケット転送ユニットの内部ブロック図。
【図６】本発明のパケット検索ユニットを並列化しない場合のパケット転送ユニットとその内部のパケット転送処理機構の内部ブロック図。
【図７】本発明のパケット検索ユニットを並列化した場合のパケット転送ユニットとその内部のパケット転送処理機構の内部ブロック図。
【図８】本発明のパケット検索ユニットの内部ブロック図。
【図９】本発明のパケット検索ユニット内で採取した統計情報をルーティングプロセッサ内が読み出し集計するという処理を表す概念図。
【図１０】本発明の複数のパケット検索ユニットが検索したフロー番号に従い検索パケット再配列ユニットがフロー毎の転送速度を測定する部分を抜粋したパケット転送処理機構の内部ブロック図。
【図１１】本発明の転送パケット振り分けユニットの振り分け方法がラウンドロビン法の場合のパケット転送ユニットのパケット転送処理を表すタイムチャート。
【図１２】本発明の転送パケット振り分けユニットの振り分け方法がアウトオブオーダ法の場合のパケット転送ユニットのパケット転送処理を表すタイムチャート。
【図１３】本発明の転送パケット振り分けユニットの振り分け方法がハッシュ法の場合のパケット転送ユニットのパケット転送処理を表すタイムチャート。
【図１４】フロー検索テーブルの説明図。
【図１５】第１の入力回線限定方式の説明図。
【図１６】第２の入力回線限定方式の説明図。
【発明を実施するための形態】
【００２２】
図１に、本発明のルータ装置が適用されるネットワークシステム全体の概念図を示す。図１において、パケットの送信元および受信先になり得るホスト１、２および３、パケットのヘッダ内に記述されている宛先アドレスに従いパケットを転送するルータ４および５、ホストおよびルータが直接接続され、ホストおよびルータ間のデータを伝送するサブネットワーク６、７および８が示される。ルータ４および５もパケットの送信元および受信先になり得る。
【００２３】
例えば、ホスト１からホスト２にパケットを転送する場合、ホスト１はインターフェース１０からサブネットワーク６を介して繋がるルータ４に向かってパケットを送出する。ルータ４はサブネットワーク６に繋がるインターフェース４０からパケットを受け取り、インターフェース４１からサブネットワーク７を介して繋がるルータ５に向かってパケットを転送する。同様にルータ５はインターフェース５０からパケットを受け取り、インターフェース５１からサブネットワーク８を介して繋がるホスト２に向かってパケットを転送する。ホスト２はインターフェース２０からパケットを受け取る。サブネットワーク内の特定のルータまたはホストの特定のためにはサブネットワーク内のアドレスが使用される。
【００２４】
図２に、ルータ内部の全体ブロック図を示す。図２においてルータ４は、パケットの入出力のインターフェースを行うネットワークインターフェースボード（ＮＩＦ： Ｎｅｔｗｏｒｋ Ｉｎｔｅｒｆａｃｅ Ｂｏａｒｄ）４５０〜４５５、パケットのヘッダ情報からパケットの転送先を検索しパケットを転送するルーティングプロセッサ（ＲＰ：Ｒｏｕｔｉｎｇ Ｐｒｏｃｅｓｓｏｒ）４４０〜４４２、ルータ全体の管理、各ＲＰの制御、および、ルーティングプロトコル等の制御パケットの送受信を行い経路情報の管理等を行うルーティングマネージャ（ＲＭ： Ｒｏｕｔｉｎｇ Ｍａｎａｇｅｒ）４２、および、各ＲＰおよびＲＭを接続し、ＲＰ間およびＲＭ、ＲＰ間のパケットの転送を行うクロスバスイッチ（ＣＳＷ： Ｃｒｏｓｓ ｂａｒ Ｓｗｉｔｃｈ）４３を備える。各ネットワークインターフェースボード（ＮＩＦ）４５０〜４５５からはネットワークインターフェース４００〜４０５が繋がる。図２のネットワークインターフェース４００〜４０５は、図１のネットワークインターフェース４０、４１に対応するものである。ネットワークインターフェースの種類には、イーサネット等のＬＡＮ（Ｌｏｃａｌ ＡｒｅａＮｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ Ｔｒａｎｓｆｅｒ Ｍｏｄｅ）等があり、各ＮＩＦ４５０〜４５５はインターフェースの種類毎に異なるハードウエアで構成される。
【００２５】
図３および図４にＲＰ ４４０の内部のブロック図を示す。図３および図４は、パケット転送ユニットを並列化した本発明のルーティングプロセッサ内部の構成の２つの例を表す構成図である。パケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）は、ＲＰ内でパケットのヘッダ情報からパケットの宛先を検索し、パケットを転送するという処理を実行するユニットであり、ＲＰ内には負荷分散のために複数個のパケット転送ユニットを設け、ＮＩＦから入ってきたパケットおよびＣＳＷから入ってきたパケットをパケット単位にパケット転送ユニットに振り分けるようにする。図３はＮＩＦから入ってきたパケットを転送するパケット転送ユニット４４００〜４４０３とＣＳＷから入ってきたパケットを転送するパケット転送ユニット４４０４〜４４０７を別々に設ける場合のＲＰの構成例であり、図４は各パケット転送ユニット４４１０〜４４１３がＮＩＦから入ってきたパケットとＣＳＷから入ってきたパケットのどちらの転送処理も行う場合のＲＰの構成例である。
【００２６】
転送パケット振り分けユニット４４２０、４４２２（図３）および４４３０、４４３２（図４）は、ＮＩＦまたはＣＳＷから入ってきたパケットを複数のパケット転送ユニットのいずれかに振り分けるという処理を行うユニットであり、パケットの振り分け方法として、パケットが入ってきた順にパケット転送ユニットに順番に振り分ける方法（ラウンドロビン法）と、空いているパケット転送ユニットに振り分ける方法（アウトオブオーダ法）と、パケットのヘッダ条件から振り分けるパケット転送ユニットを一意に決定する方法（ハッシュ法）等がある。図１１、図１２、図１３にそれぞれ、転送パケット振り分けユニットのパケット振り分け方法が、ラウンドロビン法、アウトオブオーダ法、ハッシュ法の場合の各パケット転送ユニットのパケット転送処理を表すタイムチャートを示す。図１１、１２、１３のタイムチャート内の番号はＲＰへのパケットの入力順を示し、各矩形は各パケット転送ユニットが各パケットを処理している時間を示す。図１１、１２、１３では、処理時間が長く掛かるパケットが奇数番目に入ってきて、処理時間が短いパケットが偶数番目に入ってきた場合の例について示す。
【００２７】
ハッシュ法でパケットの転送先を決定する関数（ハッシュ関数）には、例えば、パケットの転送元から転送先に連続して送られる一連のパケットは全て同じパケット転送ユニットに振り分ける、という条件を設ける。この条件により、パケット毎に転送処理に掛かる時間が異なった場合にパケット転送処理が終了した順にパケットを送出しても、パケットの転送元から転送先に連続して送られる一連のパケットの間で転送元からパケットを送った順に転送先に到着させることができる。
【００２８】
さらに、各パケット転送ユニットにパケットができるだけ均等に振り分けられるように、ハッシュ関数としてパケットヘッダ条件から作成された擬似乱数を使用することもできる。パケット転送ユニットの数が２個の場合のハッシュ関数の例として、３２ビットのソースＩＰアドレスと３２ビットのデスティネーションＩＰアドレスの全ビットの排他的論理和を取る、という方法がある。この場合、全ビットの排他的論理和により得られる１ビットにより２個の転送ユニットの内どちらに振り分けるかを決定する。パケット転送ユニットの数が４個の場合には１ビットでなく２ビットを出力するハッシュ関数を用いる。図１３では１、３番目のパケットがパケット検索ユニット４４１０に振り分けられ、２、４番目が４４１１に、５、７番目が４４１２に、６、８番目が４４１３にそれぞれ振り分けられた場合の例について示している。
【００２９】
転送パケット振り分けユニット４４２０、４４２２（図３）および４４３０、４４３２（図４）の振り分け法がラウンドロビン法またはアウトオブオーダ法の場合には、ＲＰ内の複数のパケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）がパケット転送処理を終了する順番が、パケットの転送元から転送先に連続して送られる一連のパケットの間で逆転することが有り得るので、転送パケット再配列ユニット４４２１、４４２３（図３）および４４３１、４４３３（図４）は、各パケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）がパケット転送処理を終了したパケットをパケットが入ってきた順に並べ直す。また、転送パケット振り分けユニット４４２０、４４２２（図３）および４４３０、４４３２（図４）の振り分け法がアウトオブオーダ法の場合には、転送パケット再配列ユニット４４２１、４４２３（図３）および４４３１、４４３３（図４）がルータにパケットが入ってきた順番にパケットを再配列するために、転送パケット振り分けユニット４４２０、４４２２（図３）および４４３０、４４３２（図４）がパケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）にパケットを振り分ける時点で各パケットにシーケンス番号を付け、シーケンス番号とパケットとを一緒にパケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）の中を持ち回り、転送パケット再配列ユニット４４２１、４４２３（図３）および４４３１、４４３３（図４）はパケットに付けられたシーケンス番号の順にパケットを再配列してパケットを送出する。
【００３０】
また、転送パケット振り分けユニット４４２０、４４２２（図３）および４４３０、４４３２（図４）の振り分け法がハッシュ法の場合には、各パケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）に送られたパケット間でパケットの出力順は前後して良く、転送パケット再配列ユニット４４２１、４４２３（図３）および４４３１、４４３３（図４）はパケット転送処理の終了順にパケットを送出する。複数のパケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）のパケット転送処理が終了していた場合には、パケット転送処理が終了した複数のパケット転送ユニット４４００〜４４０７（図３）および４４１０〜４４１３（図４）間で順番にパケットを送出する。
【００３１】
つぎに、図５に、本発明のパケット転送ユニットの内部構成図を示す。パケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）は、パケットの転送方向、即ちＮＩＦ４５０からＣＳＷ４３向きか、ＣＳＷ４３からＮＩＦ４５０向きかが異なるが内部の処理待ちのためのキューの持ち方は同じであり、図５は、代表してパケット転送ユニット４４００の内部の処理待ちのためのキューの持ち方を示すブロック図を表したものである。図５のパケット転送ユニット４４００内にはパケット転送処理を実行するパケット転送処理機構４４０００、転送パケット振り分けユニット４４２０等が各パケット転送ユニット４４００にパケットを振り分けた後、各パケット転送処理機構４４０００がパケット処理を開始するまで処理を待つためのキューである転送パケット処理待ちキュー４４００１と、各パケット転送処理機構４４０００が処理を終了後、転送パケット再配列ユニット４４２１等がパケットを再配列し出力するまで待つためのキューである転送パケット再配列処理待ちキュー４４００２を備える。
【００３２】
転送パケット処理待ちキュー４４００１および転送パケット再配列処理待ちキュー４４００２は、各パケット転送ユニット４４００等の各パケットの処理時間の長短、および、転送パケット振り分けユニット４４２０等の振り分け方がハッシュ法の場合に各パケット転送ユニット４４００等にパケットを振り分けるときの時間的偏りを吸収し、各パケット転送ユニット４４００等が処理をしていない時間を少なくするという効果がある。
【００３３】
次に、パケット転送ユニット４４００内でパケットの検索処理を行う部分だけを並列化して高速化を図る場合の実施の形態を示す。まず、図６に、パケットヘッダの検索処理を行うパケット検索ユニットを並列化しない場合のパケット転送ユニット４４００およびその内部のパケット転送処理機構４４０００の内部構成図を示す。また、図７に、パケット検索ユニットを並列化した場合のパケット転送ユニット４４００およびその内部のパケット転送処理機構４４０００の内部構成図を示す。
【００３４】
図６のパケット転送処理機構４４０００は、パケットヘッダ操作機構４４００００とパケット検索ユニット４４０００１を備える。パケットヘッダ操作機構４４００００は、パケットのヘッダ部分を抽出し、パケット検索ユニット４４０００１に渡す。パケット検索ユニット４４０００１はパケットヘッダ操作機構４４００００から渡されたパケットヘッダ情報に基づきパケットの転送先、パケットを廃棄するか転送するかの検索（フィルタリング検索）、および、パケットを出力するときの出力順の優先順位（通信品質検索）等を行い、パケットの転送先、パケットを廃棄するか否かの情報、パケットの出力優先順位等の情報をパケットヘッダ操作機構４４００００に渡す。パケットヘッダ操作機構４４００００はパケット検索ユニット４４０００１から渡されたパケットの転送先、パケットを廃棄するか転送するか等の情報に従い、パケットを転送、または廃棄する。
【００３５】
図７に、パケット検索ユニットを並列化した場合の、パケット転送ユニット４４００の構成を示す。このパケット転送ユニット４４００は、パケット転送処理機構４４０００、パケットヘッダ操作機構４４００００、図６のパケット検索ユニット４４０００１に対応するパケット検索ユニット４４０００１〜４４０００４、パケット転送処理機構４４０００が複数のパケット検索ユニット４４０００１〜４４０００４の一つにパケットヘッダの検索処理を振り分ける検索パケット振り分けユニット４４０００５、各パケット検索ユニット４４０００１〜４４０００４の検索結果を再配列する検索パケット再配列ユニット４４０００６を備える。
【００３６】
検索パケット振り分けユニット４４０００５のパケット検索ユニットの振り分け方法には、転送パケット振り分けユニット４４２０、４４２２（図３）、および４４３０、４４３２（図４）と同様、ラウンドロビン法とアウトオブオーダ法とハッシュ法を取り得て、それぞれの振り分け法の特徴も転送パケット振り分けユニットの場合と同様である。検索パケット再配列ユニット４４０００６の再配列方法も、転送パケット再配列ユニット４４２１、４４２３（図３）および４４３１、４４３３（図４）の再配列方法と同様である。
【００３７】
ここで、図８に、本発明のパケット検索ユニットの内部構成図を示す。図７のパケット検索ユニット４４０００１〜４４０００４は内部の処理待ちのためのキューの持ち方は同じであり、図８は、代表してパケット検索ユニット４４０００１の内部の処理待ちのためのキューの持ち方を示すブロック図を表したものである。図８のパケット検索ユニット４４０００１内にはパケット検索処理を実行するパケット検索処理機構４４０００１０、検索パケット振り分けユニット４４０００５が各パケット検索ユニット４４０００１等にパケットを振り分けた後、各パケット検索処理機構４４０００１０がパケット処理を開始するまで処理を待つためのキューである検索パケット処理待ちキュー４４０００１１と、各パケット検索処理機構が処理を終了後、検索パケット再配列ユニットがパケットを再配列し出力するまで待つためのキューである検索パケット再配列処理待ちキュー４４０００１２を備える。
【００３８】
検索パケット処理待ちキュー４４０００１１および検索パケット再配列処理待ちキュー４４０００１２は、各パケット検索ユニット４４０００１等の各パケットの処理時間の長短、および、検索パケット振り分けユニットの振り分け方がハッシュ法の場合に各パケット検索ユニットにパケットを振り分けるときの時間的偏りを吸収し、各パケット検索ユニットが処理をしていない時間を少なくするという効果がある。
【００３９】
次に、上記パケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）またはパケット検索ユニット４４０００１〜４４０００４を並列化した場合の統計情報採取法について示す。例えばパケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）内では転送を行ったパケット数およびバイト数、ルータ内でフィルタリングやルータ内のパケットの輻輳により廃棄したパケット数を数えており、また、パケット検索ユニット４４０００１〜４４０００４内ではパケットの出力先の検索（経路検索）の結果、どこに出力するかが定義されていなかったパケットの数（経路無し）、ルータ自身に宛てたパケットの数や、フィルタリングの廃棄条件に一致したパケット数等を数えている。
【００４０】
本発明ではパケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）またはパケット検索ユニット４４０００１〜４４０００４を並列化しているので上記各統計を各パケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または各パケット検索ユニット４４０００１〜４４０００４内で採取するようにした場合には、図２に示したＲＭ４２上で動作しているソフトウエア、或いは図２に示したＲＰ４４０〜４４２内にプロセッサを搭載し、このプロセッサ上でソフトウエアを動作させ、これらのソフトウエアが各パケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または各パケット検索ユニット４４０００１〜４４０００４内に採取された統計情報を読み、並列化されている全パケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または全パケット検索ユニット４４０００１〜４４０００４に取られた統計情報を足し合わせるようにする。
【００４１】
図９に、本発明のパケット検索ユニット内で採取した統計情報をルーティングプロセッサ内が読み出し集計するという処理を表す概念図を示す。図９では、パケット転送処理機構４４０００内のパケット検索ユニット４４０００１〜４４０００４は、それぞれ統計カウンタ４４０００１３〜４４０００４３を備える。そして、パケット検索ユニット４４０００１〜４４０００４内で採取した統計カウンタ４４０００１３、４４０００２３、４４０００３３、４４０００４３の値をＲＰ ４４０内のプロセッサ４４５がレジスタバスを介して読み、集計する。図９ではパケットの収集に直接関係しない部分は省略してある。
【００４２】
また、統計機能ではないがパケットのデータ転送バイト数の測定が必要な場合として、ネットワーク業者がユーザからのパケットを受信する時にパケットのヘッダ条件に従いパケットを分類し、この分類（以後フローと呼ぶ）毎にデータ転送速度の監視を行い、このフローのデータ転送速度がこのフローを流しているユーザとの間で契約している帯域以上のパケットを廃棄したり輻輳時に優先して廃棄するようにする機能（帯域監視機能）、または、ネットワークユーザがネットワーク業者のネットワークにパケットを送信する時にルータから各フローに属するパケットデータを出力する速度をネットワーク業者との間で契約している帯域以内に制限する機能（シェーピング機能）がある。帯域監視機能またはシェーピング機能を実現するためには、ルータを流れるパケットの一定時間毎のデータ転送バイト数（データ転送速度）を測定する必要がある。
【００４３】
複数のパケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または複数のパケット検索ユニット４４０００１〜４４０００４を並列化した場合には、一つのフローが複数のパケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または複数のパケット検索ユニット４４０００１〜４４０００４に分散されて処理されるので、一つのフロー全体のデータ転送速度を求めるためには、各パケット転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または各パケット検索ユニット４４０００１〜４４０００４を流れるフローのデータ転送速度を共通の個所に採取する必要がある。一つのフローのデータ転送速度を共通の個所に採取するために、各フローに番号を付け、各データ転送ユニット４４００〜４４０７（図３）、４４１０〜４４１３（図４）または各データ検索ユニット４４０００１〜４４０００４からパケットヘッダ検索結果の一つとしてフローの番号を出力し、転送パケット再配列ユニット４４２１、４４２３、４４３１、４４３３または検索パケット再配列ユニット４４０００６内で、フローの番号毎にフローのデータ転送速度を測定するようにし、帯域監視機能実現時にはフローのデータ転送速度に従い、（例えば、閾値以上になったら）パケットを廃棄したり、パケットを廃棄されやすくしたりする。さらに、フロー番号毎にトラフィック統計を求めることもできる。また、シェーピング機能実現時にはフローのデータ転送速度がネットワーク業者との間の契約帯域を超えないように出力を制限するようにする。
【００４４】
図１０に、本発明の複数のパケット検索ユニットが検索したフロー番号に従い検索パケット再配列ユニットがフロー毎の転送速度を測定する部分を抜粋したパケット転送処理機構の内部構成図を示す。検索パケット再配列ユニット４４０００６は、フロー番号に対応して、パケット数及びバイト数等のパケットデータ転送速度に関する情報を記憶したフロー毎の転送速度カウンタ４４０００６０を備える。パケット検索ユニット４４０００１〜４４０００４がパケット検索結果の一つとしてフロー番号を含む情報を出力し、検索パケット再配列ユニット４４０００６がフローの番号毎の転送速度カウンタ４４０００６０に各フローのパケットデータ転送速度を測定する。図１０ではフロー毎のパケットデータ転送速度の測定に直接関係しない部分は省略してある。
【００４５】
つぎに、フロー検索について説明する。図１４に、フロー検索テーブルの説明図を示す。このフロー検索テーブルは、一例として、図示のように、比較フィールド１０１として、転送元ＩＰアドレス、宛先ＩＰアドレス、パケット長、ＩＰ優先度、ＩＰ上位プロトコル、送達確認フラグ、転送先ＴＣＰ／ＵＤＰポート、宛先ＴＣＰ／ＵＤＰポートを含む。また、アクションフィールド１０２としては、フィルタ（通過／廃棄）、トンネル（カプセル化する／しない）、ＱｏＳ（遅延クラス、廃棄クラス、帯域等）が記憶されている。
【００４６】
つぎに、ＱｏＳフロー検索の具体的方法を説明する。ここでは、一例としてＱｏＳフロー検索に注目して説明するが、各種フロー検索についても、同様に実施することができる。なお、アクションフィールド１０２には、これら各フローの制御情報が混在して記憶されていても良いし、また、各フロー毎にフロー検索テーブルが設けられるようにしても良い。
【００４７】
まず、リニアサーチ方式について説明する。アクションのひとつとしてのパケットのＱｏＳ制御情報を判定する際、予め設定されたエントリをエントリテーブルの上から順に読みだす。そして、パケットのヘッダ部等の値とエントリの比較フィールド１０１内の有効なフロー条件に全て一致したか否か判定する。なお、一致した場合にはエントリ内のアクションフィールド１０２内のＱｏＳ制御情報をパケットのＱｏＳ制御情報と判定し、ＱｏＳフロー検索を終了する。フロー条件に一致する場合が検索されると、アクションフィールド１０２内のＱｏＳ制御情報をＱｏＳ制御情報と決定し次のエントリの検索を実行せずフロー検索を終了する。
【００４８】
以上のようなリニアーサーチ方式では、大量のエントリが設定されるネットワークにおいては高速にＱｏＳ制御やフィルタリングを実行することが困難となる場合がある。そこで、大量のエントリが設定された場合でも、リニアサーチ方式と比較して高速にフロー検索を行うことができる、入力回線限定方式等を採用するとよい。以下、入力回線限定方式の概要を説明する。入力回線限定方式では、リニアーサーチ方式の比較フィールドを構成する入力回線番号に一致するエントリだけを検索し、高速化を図るようにする。
【００４９】
図１５に、第１の入力回線限定方式の説明図を示す。第１の入力回線限定方式においては、リニアーサーチ方式の比較フィールドから入力回線番号と入力回線番号有効ビットを削除したエントリ５１１−ｉを入力回線毎に設定しておく。フロー条件部５２１−ｉは、例えば、送信元あるいは宛先ユーザを識別する条件はＳＩＰとＤＩＰの上限値と下限値であるＳＩＰ上限値５０１、ＳＩＰ下限値５０２、ＤＩＰ上限値５０３、ＤＩＰ下限値５０４と、ＳＩＰとＤＩＰの上限値と下限値が有効であることを示すＩＰ有効ビット５６２と、送信元ポートであるＳＰＯＲＴ５０５と、宛先ポートであるＤＰＯＲＴ５０６と、前記ＳＰＯＲＴ５０５とＤＰＯＲＴ５０６が有効であることを示すポート有効ビット５６３等を含む。ＱｏＳ制御情報部５３０−ｉは、例えば、優先転送機能で使用するＱｏＳ制御情報であるＱｏＳ制御情報５０７を含む。フロー条件である入力回線番号が一致したエントリ５１１−ｉだけ検索するためエントリ５１１−ｉ内に入力回線番号は必要ない。フロー検索時には、パケットが入力した入力回線に割り当てられたエントリ５１１−ｉのみ検索する。
【００５０】
ここで、上述の第１の入力回線限定方式では、入力回線番号に関係ないエントリ５１１−ｉを設定する（例えば「全ての入力回線から入力されたＴｅｌｎｅｔのトラヒックは高優先」と設定する）場合、エントリ５１１−ｉを入力回線数（＝Ｎ）設定する必要があり、エントリテーブルを実現するメモリの効率が悪くなる場合がある。そこで、以下に、一層高速な入力回線限定方式について説明する。
【００５１】
図１６に、第２の入力回線限定方式の説明図を示す。第２の入力回線限定方式では、エントリテーブル７５０のアドレスであるリスト５４０を、入力回線毎にリストテーブル７６０に設定しておく。例えば、リストテーブルアドレスが”１”のリスト５４０−１１はエントリ５１１−１のアドレスであり、リストテーブルアドレスが”２”のリスト５４０−１２はエントリ５１１−Ｈのアドレスである。フロー検索時には、パケットが入力された入力回線に割り当てられたリスト５４０だけ読みだし、このリスト５４０がポイントするエントリ５１１−ｉを読み出す。ビット幅の小さなリスト５４０（例えば、１０２４エントリ持った時にも１０ｂｉｔ程度）を入力回線毎に所持し、ビット幅の大きなエントリ５１１−ｉを各入力回線で共有すれば、エントリテーブルを実現するメモリを有効に使用することができる。このため、高速化を実現しつつ、多数のエントリ５１１−ｉを設定することが可能となる。
【００５２】
フロー検出方式の他の実施例として出力回線限定方式がある。出力回線限定方式では、フロー条件である出力回線番号が一致するエントリ５１１−ｉのみを、上述の入力限定方式と同様に処理することで、フロー検出の高速化を実現する。また、フロー条件としてヘッダ情報内の入力回線番号の代わりにＭＡＣ（Ｍｅｄｉａ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌ）レイヤーのソースアドレスである。ＳＡＭＡＣを用いた際のＳＡＭＡＣ限定方式がある。ＳＡＭＡＣ限定方式では、ＳＡＭＡＣのグループであるＳＡＭＡＣグループを定義し、ＳＡＭＡＣグループの識別子であるＳＡＭＡＣ識別子でエントリを限定することで、上述の入力限定方式と同様にフロー検索を実行することができる。
【００５３】
なお、図３、図４に示したパケット転送ユニットの並列化と図７に示したパケット検索ユニットの並列化を同時に実行することも可能であり、同時に実行した場合、各ＲＰ内のパケット検索ユニットの並列度は、パケット転送ユニットの並列度とパケット検索ユニットの並列度の掛け算になる。
【産業上の利用可能性】
【００５４】
本発明は、例えば、コンピュータネットワークシステムにおけるルータ、リピータ等のネットワーク中継装置に利用可能である。
【符号の説明】
【００５５】
１〜３ ホスト
４〜５ ルータ
６〜８ サブネットワーク
４００〜４０５ ネットワークインターフェース
４２ ルータ制御部（ＲＭ）
４３ クロスバスイッチ（ＣＳＷ）
４４０〜４４２ ルーティングプロセッサ
４５０〜４５５ ネットワークインターフェースボード（ＮＩＦ）
４４００〜４４０７ パケット転送ユニット
４４２０、４４２２ 転送パケット振り分けユニット
４４２１、４４２３ 転送パケット再配列ユニット
４４１０〜４４１３ パケット転送ユニット
４４３０、４４３２ 転送パケット振り分けユニット
４４３１、４４３３ 転送パケット再配列ユニット
４４０００ パケット転送処理機構
４４００１ 転送パケット処理待ちキュー
４４００２ 転送パケット再配列処理待ちキュー
４４００００ パケットヘッダ操作機構
４４０００１〜４４０００４ パケット検索ユニット
４４０００５ 検索パケット振り分けユニット
４４０００６ 検索パケット再配列ユニット
４４０００１０ パケット検索処理機構
４４０００１１ 検索パケット処理待ちキュー
４４０００１２ 検索パケット再配列処理待ちキュー
４４０００１３、４４０００２３、４４０００３３、４４０００４３ 統計カウンタ
４４５ プロセッサ
４４０００６０ フロー毎の転送速度カウンタ
【特許請求の範囲】
【請求項１】
ネットワーク内でパケットのヘッダ情報に従いパケットの中継先を決定しパケットを中継するネットワーク中継装置であり、
入力されるパケットの転送処理を行う複数個のパケット転送ユニットと、
前記ネットワーク中継装置のインターフェース又はスイッチから入力したパケットを各前記パケット転送ユニットに振り分けるパケット振り分けユニットと、
各前記パケット転送ユニットがパケット転送処理を行ったパケットを、パケットの入力順に再配列するパケット再配列ユニットと
を備え、
前記パケット転送ユニットは、予め定められたパケットのヘッダ条件に従い入力されるパケットを分類し、この分類結果を特定する番号とパケットを出力し、
前記パケット再配列ユニットは、前記パケット転送ユニットから入力されたパケットに対して、入力された分類結果を特定する番号毎にパケットの転送速度を測定することを特徴とするネットワーク中継装置。
【請求項２】
請求項１に記載のネットワーク中継装置において、
前記パケット再配列ユニットで測定された転送速度に従い、入力されたパケットの転送速度が予め定められた値以上の場合にパケットを廃棄する処理、または、輻輳時に廃棄され易くする処理、または、出力するパケットの速度が予め定められた値以上にならないようにパケットの出力速度を抑える処理を実行することを特徴とするネットワーク中継装置。
【請求項３】
ネットワーク内でパケットのヘッダ情報に従いパケットの中継先を決定しパケットを中継するネットワーク中継装置であり、
入力されるパケットの転送処理を行う複数個のパケット転送ユニットと、
前記ネットワーク中継装置のインターフェース又はスイッチから入力したパケットを各前記パケット転送ユニットに振り分けるパケット振り分けユニットと、
各前記パケット転送ユニットがパケット転送処理を行ったパケットを、パケットの入力順に再配列するパケット再配列ユニットと
を備え、
前記パケット転送ユニットは、予め定められたパケットのヘッダ条件に従い入力されるパケットのフローを特定し、
前記パケット再配列ユニットは、前記パケット転送ユニットが特定したパケットのフロー毎にトラフィック統計情報を採取することを特徴とするネットワーク中継装置。
【請求項４】
ネットワーク内でパケットのヘッダ情報に従いパケットの中継先を決定しパケットを中継するネットワーク中継装置であって、入力パケットの転送処理を行うパケット転送ユニットを備え、
前記パケット転送ユニットは、
前記入力パケットのパケットヘッダの抽出を行うパケットヘッダ操作機構と、
前記パケットヘッダ操作機構が抽出したパケットヘッダをキーとしてパケットヘッダの検索処理を行う複数個のパケット検索ユニットと、
複数の前記パケット検索ユニットに、抽出されたパケットヘッダを振り分ける検索パケット振り分け機構と、
複数の前記パケット検索ユニットが出力するパケットヘッダ検索結果を再配列する検索パケット再配列ユニットと
を備え、
前記パケット検索ユニットは、予め定められたパケットのヘッダ条件に従い前記入力パケットを分類し、この分類結果を特定する番号を出力し、
前記検索パケット再配列ユニットは、前記パケット検索ユニットから入力された分類結果を特定する番号毎に、前記入力パケットの転送速度を測定することを特徴とするネットワーク中継装置。
【請求項５】
請求項４に記載のネットワーク中継装置において、
前記検索パケット再配列ユニットで測定された転送速度に従い、入力されたパケットの転送速度が予め定められた値以上の場合にパケットを廃棄する処理、または、輻輳時に廃棄され易くする処理、または、出力するパケットの速度が予め定められた値以上にならないようにパケットの出力速度を抑える処理を実行することを特徴とするネットワーク中継装置。
【請求項６】
ネットワーク内でパケットのヘッダ情報に従いパケットの中継先を決定しパケットを中継するネットワーク中継装置であって、入力パケットの転送処理を行うパケット転送ユニットを備え、
前記パケット転送ユニットは、
前記入力パケットのパケットヘッダの抽出を行うパケットヘッダ操作機構と、
前記パケットヘッダ操作機構が抽出したパケットヘッダをキーとしてパケットヘッダの検索処理を行う複数個のパケット検索ユニットと、
複数の前記パケット検索ユニットに、抽出されたパケットヘッダを振り分ける検索パケット振り分け機構と、
複数の前記パケット検索ユニットが出力するパケットヘッダ検索結果を再配列する検索パケット再配列ユニットと
を備え、
前記パケット検索ユニットは、予め定められたパケットのヘッダ条件に従い前記入力パケットのフローを特定し、
前記検索パケット再配列ユニットは、前記パケット検索ユニットが特定したパケットのフロー毎にトラフィック統計情報を採取することを特徴とするネットワーク中継装置。
【請求項７】
請求項１乃至３のいずれかに記載のネットワーク中継装置において、請求項４乃至６のいずれかに記載のネットワーク中継装置における前記パケット転送ユニットを用いるようにしたネットワーク中継装置。
【請求項１】
ネットワーク内でパケットのヘッダ情報に従いパケットの中継先を決定しパケットを中継するネットワーク中継装置であり、
入力されるパケットの転送処理を行う複数個のパケット転送ユニットと、
前記ネットワーク中継装置のインターフェース又はスイッチから入力したパケットを各前記パケット転送ユニットに振り分けるパケット振り分けユニットと、
各前記パケット転送ユニットがパケット転送処理を行ったパケットを、パケットの入力順に再配列するパケット再配列ユニットと
を備え、
前記パケット転送ユニットは、予め定められたパケットのヘッダ条件に従い入力されるパケットを分類し、この分類結果を特定する番号とパケットを出力し、
前記パケット再配列ユニットは、前記パケット転送ユニットから入力されたパケットに対して、入力された分類結果を特定する番号毎にパケットの転送速度を測定することを特徴とするネットワーク中継装置。
【請求項２】
請求項１に記載のネットワーク中継装置において、
前記パケット再配列ユニットで測定された転送速度に従い、入力されたパケットの転送速度が予め定められた値以上の場合にパケットを廃棄する処理、または、輻輳時に廃棄され易くする処理、または、出力するパケットの速度が予め定められた値以上にならないようにパケットの出力速度を抑える処理を実行することを特徴とするネットワーク中継装置。
【請求項３】
ネットワーク内でパケットのヘッダ情報に従いパケットの中継先を決定しパケットを中継するネットワーク中継装置であり、
入力されるパケットの転送処理を行う複数個のパケット転送ユニットと、
前記ネットワーク中継装置のインターフェース又はスイッチから入力したパケットを各前記パケット転送ユニットに振り分けるパケット振り分けユニットと、
各前記パケット転送ユニットがパケット転送処理を行ったパケットを、パケットの入力順に再配列するパケット再配列ユニットと
を備え、
前記パケット転送ユニットは、予め定められたパケットのヘッダ条件に従い入力されるパケットのフローを特定し、
前記パケット再配列ユニットは、前記パケット転送ユニットが特定したパケットのフロー毎にトラフィック統計情報を採取することを特徴とするネットワーク中継装置。
【請求項４】
ネットワーク内でパケットのヘッダ情報に従いパケットの中継先を決定しパケットを中継するネットワーク中継装置であって、入力パケットの転送処理を行うパケット転送ユニットを備え、
前記パケット転送ユニットは、
前記入力パケットのパケットヘッダの抽出を行うパケットヘッダ操作機構と、
前記パケットヘッダ操作機構が抽出したパケットヘッダをキーとしてパケットヘッダの検索処理を行う複数個のパケット検索ユニットと、
複数の前記パケット検索ユニットに、抽出されたパケットヘッダを振り分ける検索パケット振り分け機構と、
複数の前記パケット検索ユニットが出力するパケットヘッダ検索結果を再配列する検索パケット再配列ユニットと
を備え、
前記パケット検索ユニットは、予め定められたパケットのヘッダ条件に従い前記入力パケットを分類し、この分類結果を特定する番号を出力し、
前記検索パケット再配列ユニットは、前記パケット検索ユニットから入力された分類結果を特定する番号毎に、前記入力パケットの転送速度を測定することを特徴とするネットワーク中継装置。
【請求項５】
請求項４に記載のネットワーク中継装置において、
前記検索パケット再配列ユニットで測定された転送速度に従い、入力されたパケットの転送速度が予め定められた値以上の場合にパケットを廃棄する処理、または、輻輳時に廃棄され易くする処理、または、出力するパケットの速度が予め定められた値以上にならないようにパケットの出力速度を抑える処理を実行することを特徴とするネットワーク中継装置。
【請求項６】
ネットワーク内でパケットのヘッダ情報に従いパケットの中継先を決定しパケットを中継するネットワーク中継装置であって、入力パケットの転送処理を行うパケット転送ユニットを備え、
前記パケット転送ユニットは、
前記入力パケットのパケットヘッダの抽出を行うパケットヘッダ操作機構と、
前記パケットヘッダ操作機構が抽出したパケットヘッダをキーとしてパケットヘッダの検索処理を行う複数個のパケット検索ユニットと、
複数の前記パケット検索ユニットに、抽出されたパケットヘッダを振り分ける検索パケット振り分け機構と、
複数の前記パケット検索ユニットが出力するパケットヘッダ検索結果を再配列する検索パケット再配列ユニットと
を備え、
前記パケット検索ユニットは、予め定められたパケットのヘッダ条件に従い前記入力パケットのフローを特定し、
前記検索パケット再配列ユニットは、前記パケット検索ユニットが特定したパケットのフロー毎にトラフィック統計情報を採取することを特徴とするネットワーク中継装置。
【請求項７】
請求項１乃至３のいずれかに記載のネットワーク中継装置において、請求項４乃至６のいずれかに記載のネットワーク中継装置における前記パケット転送ユニットを用いるようにしたネットワーク中継装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２００９−１６５１５９（Ｐ２００９−１６５１５９Ａ）
【公開日】平成２１年７月２３日（２００９．７．２３）
【国際特許分類】
【出願番号】特願２００９−５７６７０（Ｐ２００９−５７６７０）
【出願日】平成２１年３月１１日（２００９．３．１１）
【分割の表示】特願２０００−１６５８２（Ｐ２０００−１６５８２）の分割
【原出願日】平成１２年１月２６日（２０００．１．２６）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２１年７月２３日（２００９．７．２３）
【国際特許分類】
【出願日】平成２１年３月１１日（２００９．３．１１）
【分割の表示】特願２０００−１６５８２（Ｐ２０００−１６５８２）の分割
【原出願日】平成１２年１月２６日（２０００．１．２６）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]