(57)【特許請求の範囲】
【請求項１】
複数の入力回線と、複数の出力回線と、前記複数の入力回線のうちの一つの入力回線から入力された入力パケットを前記複数の出力回線の何れかの出力回線に出力するパケット中継装置であって、
入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報のうち少なくとも一つの情報と、その情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとし、該エントリを複数有するエントリテーブルが前記アドレス情報毎に分割して設定されており、
前記入力パケット内のアドレス情報に対応するエントリテーブルのみを検索し、そのエントリを読み出すエントリ読み出し手段と、
前記入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報と前記エントリ読み出し手段が読み出したエントリ内の情報との一致判定をする一致判定手段と、
前記一致判定手段で一致と判定された場合に、前記エントリ内の前記通信品質制御情報又は前記フィルタリング制御情報により、前記入力パケットの転送の優先度又は、転送の可否を決定する手段とを備えたパケット中継装置。
【請求項２】
複数の入力回線と、複数の出力回線と、前記複数の入力回線のうちの一つの入力回線から入力された入力パケットを前記複数の出力回線の何れかの出力回線に出力するパケット中継装置であって、
入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報のうちの少なくとも一つの情報と、その情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとし、該エントリーを複数有するエントリテーブルと、
前記エントリテーブル内のエントリを指定するエントリポインタを前記アドレス情報毎に分割して設定したエントリーポインタテーブルと、
入力パケット内のアドレス情報に対応するエントリポインタテーブルのみを検索し、そのエントリポインタを読み出すエントリポインタ読み出し手段と、
前記エントリポインタ読みだし手段が読み出したエントリポインタが指定するエントリを前記エントリテーブルから読み出すエントリ読み出し手段と、
入力パケット内のアドレス情報、用途を識別する情報又は優先度を識別する情報と、前記エントリ読み出し処理部が読み出したエントリ内の情報との一致判定をする一致判定手段と、
前記一致判定手段で一致と判定された場合に、前記エントリ内の前記通信品質制御情報又は前記フィルタリング制御情報により、入力パケットの転送の優先度又は、転送の可否を決定する手段を有することを特徴とするパケット中継装置。
【請求項３】
請求項１記載のパケット中継装置であって、前記エントリ読み出し手段と、前記一致判定手段と、前記入力パケットの転送の優先度又は、転送の可否を決定する手段とをパイプライン制御することを特徴とするパケット中継装置。
【請求項４】
請求項３記載のパケット中継装置であって、前記エントリポインタ読み出し手段と、前記エントリ読み出し手段と、前記一致判定手段と、前記入力パケットの転送の優先度又は、転送の可否を決定する手段とをパイプライン制御することを特徴とするパケット中継装置。
【請求項５】
複数の入力回線と、複数の出力回線と、前記複数の入力回線のうちの一つの入力回線から入力された入力パケットを前記複数の出力回線の何れかの出力回線に出力するパケット中継装置であって、
前記入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報のうちの少なくとも一つの情報と、その情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとし、該エントリを複数有するエントリテーブルが、前記アドレス情報毎に分割して設定されており、
入力パケットのアドレス情報に対応するエントリテーブルのみを検索し、そのエントリを読み出すエントリ読み出し手段と、入力パケット内のアドレス情報、用途を識別する情報又は優先度を識別する情報と前記エントリ読み出し手段が読み出したエントリ内の情報との一致判定をする一致判定手段とを有し、
前記エントリテーブルと前記一致判定手段とは同一の半導体チップに実装したことを特徴とするパケット中継装置。
【請求項６】
複数の入力回線と、複数の出力回線と、前記複数の入力回線のうちの一つの入力回線から入力された入力パケットを前記複数の出力回線の何れかの出力回線に出力するパケット中継装置であって、
前記入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報のうちの少なくとも一つの情報と、その情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとし、該エントリーを複数有するエントリテーブルと、
前記エントリテーブル内のエントリを指定するエントリポインタを前記アドレス情報毎に分割して設定したエントリーポインタテーブルとを有し、
入力パケット内のアドレス情報に対応するエントリポインタテーブルのみを検索し、そのエントリポインタを読み出すエントリポインタ読み出し手段と、
前記エントリポインタ読みだし手段が読み出したエントリポインタが指定するエントリを前記エントリテーブルから読み出すエントリ読み出し手段と、
入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報と、前記エントリ読み出し手段が読み出したエントリ内の情報との一致判定をする一致判定手段とを有し、
前記エントリテーブルと前記一致判定手段とは同一の半導体チップに実装したことを特徴とするパケット中継装置。
【請求項７】
請求項６に記載のパケット中継装置において、
前記エントリポインタテーブルは前記半導体チップと異なる半導体チップで構成したことを特徴とするパケット中継装置。
【請求項８】
請求項１から７のいずれか１項に記載のパケット中継装置において、
前記アドレス情報は、前記入力回線または前記出力回線の識別番号であることを特徴とするパケット中継装置。
【請求項９】
請求項１から７のいずれか１項に記載のパケット中継装置において、
前記アドレス情報は、送信元または送信先の物理アドレスであることを特徴とするパケット中継装置。
【請求項１０】
請求項１から７のいずれか１項に記載のパケット中継装置において、
前記アドレス情報は、送信元または送信先サブネット識別情報であることを特徴とするパケット中継装置。
【請求項１１】
請求項１から７のいずれか１項に記載のパケット中継装置において、
前記エントリテーブルは、入力パケットのアドレス情報と、前記アドレス情報の有効／無効を示すフラグ情報と、それらの情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとすることを特徴とするパケット中継装置。
【請求項１２】
請求項１１に記載のパケット中継装置において、
前記アドレス情報は、インターネット・プロトコル（ＩＰ）アドレス情報と、入力回線情報とであり、前記アドレス情報の有効／無効を示すフラグ情報は、前記ＩＰアドレス情報の有効／無効を示すフラグ情報と、前記入力回線情報の有効／無効を示すフラグ情報とであることを特徴とするパケット中継装置。
【請求項１３】
請求項１２に記載のパケット中継装置において、
前記一致判定手段は、ＩＰアドレス情報と、入力回線情報毎に設けられた複数の比較手段を有し、
ＩＰアドレス情報に対応して設けられた前記比較手段は、前記ＩＰアドレス情報の有効／無効を示すフラグ情報に応じて動作し、
入力回線情報に対応して設けられた前記比較手段は、前記入力回線情報の有効／無効を示すフラグ情報に応じて動作することを特徴とするパケット中継装置。
【請求項１４】
請求項１３に記載のパケット中継装置において、
ＩＰアドレス情報に対応して設けられた前記比較手段は、前記ＩＰアドレス情報の有効／無効を示すフラグ情報が有効を示す場合のみ一致判定を行い、入力回線情報に対応して設けられた前記比較手段は、前記入力回線情報の有効／無効を示すフラグ情報が有効を示す場合のみ一致判定を行うことを特徴とするパケット中継装置。
【請求項１５】
請求項１から１４のいずれか１項に記載のパケット中継装置において、
前記通信品質制御情報は、帯域監視情報であることを特徴とするパケット中継装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数のネットワークを相互に接続し、パケットを中継する中継装置に関する。
【０００２】
【従来の技術】
インターネットユーザの増加に伴い、インターネットを流れるトラヒック（パケット）が急増している。インターネットで用いられているパケット型通信方式では、多数のユーザからのパケットが同じ回線を共用使用できるため、帯域あたりのコストを低く抑えることが出来る。また、ユーザ毎の品質制御等の厳密な管理を行っていなかったことも、低コスト実現の要因である。
【０００３】
このパケット型通信方式の低コスト性の為、従来、専用の網で実現していた電話網や企業網をインターネットで統合して、通信コストの低減を実現しようという動きが出てきた。これらを統合するためには、従来の電話網や企業網が実現していた低遅延時間や低廃棄率等の通信品質（QoS：Quality of Service）やセキュリティを実現する必要がある。
【０００４】
QoSを実現するQoS制御は、制御の対象となる具体的な用途（電話トラヒック等）や個別のユーザ（企業等）を識別しつつ、その契約に応じた優先度で優先転送しなくてはならない。QoS制御に関してはATM（Asynchronous Transfer Mode）交換機で一般的である。ATM交換機のQoS制御はネットワーク入り口で契約された帯域で帯域監視を実施する帯域監視手段、前記帯域を遵守しているパケットに対して契約された優先度で優先転送する優先転送手段より成る。
【０００５】
このATM交換機における優先転送手段に関しては例えば特開平6-197128号（以下「従来技術1」という。）に記載されている。ここでは各出力回線毎にCBR用、VBR用の２つの出力バッファを設けている。CBR用バッファに蓄積されたセルの出力優先度をVBR用バッファに蓄積されたセルよりも高くすることにより、通信遅延に厳しい制約を持つCBRトラヒックのセル群について、 ATM交換機内の通信遅延時間を一定値以内に抑えることができる。
【０００６】
また、ATM交換機における帯域監視機能についてはThe ATM Forum Traffic Management Specification  Version 4.0の第4章（以下「従来技術2」という。）に記載されている。従来技術2は帯域監視のアルゴリズムであるGCRA(Generic Cell Rate Algorithm)について説明している。ネットワークの入り口で前記GCRAに基づく帯域監視を行う事により、特定ユーザがネットワークの資源を占有することを防止できる。
【０００７】
ATM交換機は予めコネクションを設定し、入力セルのコネクション情報(ユーザや用途の情報が含まれる)によりATM交換機内に設定されたコネクション情報テーブル内の帯域監視情報や優先度情報（セル転送の優先度）等のQoS制御情報を読み出し、その帯域監視情報を用いて帯域監視を、優先度情報に対し優先転送を実行する（コネクション型通信）。一方、ルータ装置は予めコネクションを設定していないので、ATM交換機の場合のコネクション情報テーブルやコネクション情報テーブル内の帯域監視情報や優先度情報等のQoS制御情報を持っていない（パケット型通信）。このため、ルータ装置で優先転送、帯域監視を行うためには、ルータ装置は入力パケット毎にヘッダ内の情報等により帯域監視情報、優先度情報を検出するフロー検出手段が新たに必要となる。フロー検出手段により、検出された帯域監視情報、優先度情報に対し帯域監視手段、優先転送手段を適用する。なお、本願明細書では、ヘッダ内の情報等の情報を組み合わせて作成したパケット識別の条件をフロー条件と、フロー条件に一致する一連のトラヒックをフローと、フロー条件に入力パケットが一致するか否かを判定することをフロー検出と呼ぶ。
【０００８】
ルータ装置におけるQoS制御に関しては、例えば、特開平6-232904 号（以下「従来技術3」という。）で言及されている。従来技術3はルータにおいてQoS制御を実行するために、パケット内の優先度を識別する情報とプロトコル（＝上位アプリケーション）情報の全ての組み合わせの優先度を保持するマッピングテーブルに基づきパケットの優先度を判定する旨を開示する。この判定された優先度に基づき優先転送を実行してQoSを確保することが出来る。
【０００９】
ルータ装置におけるQoS制御に関する他の従来技術として、IETF(Internet Engineering Task Force)のRFC2475に記されているDiffserv(Differentiated Service)（以下「従来技術4」という。）がある。
【００１０】
従来技術4を図2を用いて説明する。インターネット325は企業網A〜Dとインターネット325間で契約されたQoSを実現している。従来技術4はインターネット325の入口のエッジルータA326やエッジルータB327(従来技術4ではバウンダリーノードと呼ばれる)が企業網A321や企業網B324からのパケットを受信するとフロー検出手段(従来技術4ではクラシファイアーと呼ばれる)によりTCP/IPヘッダ内の送信元・宛先IPアドレス、送信元・宛先ポート番号、プロトコル等をフロー条件としてフロー検出する旨を開示している。さらに、前記クラシファイアーにより抽出されたフローの帯域監視を実行してインターネット325における優先度であるDSを判定し、DSフィールド(＝TOS)に書き込む旨を開示する。さらに、インターネット325のコアのノードであるバックボーンルータ328(従来技術4ではインテリアノードと呼ばれる)は前記DSフィールドの値に基づきQoS制御することによりバックボーンルータ328におけるQoSを実現する旨を開示する。
【００１１】
セキュリティーを実現するためのフィルタリングを実行するためにもフロー検出を行う必要がある。コネクション型通信の場合、予め許可された相手とだけコネクションを設定し、許可されていない相手とのコネクション設定を禁止すれば、予期しない相手からのセルを受信する事はないためセキュリティを守りやすい。しかし、パケット型通信の場合、網に繋がる全ての端末からパケットを受信する可能性があり、予期しない相手からのパケットを完全に廃棄するフィルタリングを実行することが必要である。フィルタリングにおいてもQoS制御と同様に、まず、入力パケット毎にフィルタリングの対象（例えば、社内他事業所からのパケットかそれ以外からのパケットか）を識別するフロー検出を行い、パケット転送の可否を表す転送可否情報を決定する必要がある。ルータはこの転送可否情報に基づいてパケットの転送および廃棄を実行し、企業網のセキュリティーを実現する。
【００１２】
ルータ装置におけるフィルタリングに関しては、例えば、特開平6-104900号（以下「従来技術5」という。）に記載されている。従来技術5では、送信元アドレスと宛先アドレスの情報を登録するフィルタリングテーブルを設け、前記フィルタリングテーブルに登録された送信元アドレスから宛先アドレスへのパケットのみ転送し、フィルタリングを実現している。
【００１３】
【発明の解決しようとする課題】
インターネットユーザの増加に伴い、ルータが検出しなければならないフローの数が増加しているため、ルータのフロー検出手段は多数のフロー条件を設定できなくてはならない。また、インターネットを流れるトラヒックの急増、回線速度の高速化により、ルータにおける１パケットあたりの処理時間の短縮が必要となる。そのため、ルータは、設定されるフロー条件数が増加した場合にも、QoS制御(優先転送、帯域監視等)やフィルタリングを高速に行えなければならない。さらに、フロー条件の設定に関しては、ルータの管理者が望む多種多様なフロー条件に柔軟に対応できることが望ましい。
【００１４】
しかし、従来技術3乃至従来技術5では、かかる観点は検討されていない。  そこで、本発明の第一の目的は、ユーザを識別する情報やプロトコル情報や優先度を識別する情報等のフロー条件を大量に設定でき、回線速度の高速化やフロー条件の増加に対応し、高速にフロー検出し、高速にQoS制御やフィルタリングを実現できるパケット中継装置を提供することである。
【００１５】
また、本発明の他の目的は、フロー条件の記述性を向上させ、ルータの管理者が望む多種多様なフロー条件に柔軟に対応することができるパケット中継装置を提供することにある。
【００１６】
さらに、ルータ間がATMネットワークやフレームリレーネットワークで接続された図46の様なネットワークにおいては、公衆ATMネットワーク4301において過剰トラヒックによる輻輳が発生し、QoSを維持できない可能性がある。そのため、ルータ間を接続するATMネットワークやフレームリレーネットワークにおいてもQoS制御が行われなくてはならない。しかし、従来技術3乃至従来技術5では、高速にフロー検出し、ATMやフレームリレーのQoS制御を活用するコネクション(VC(Virtual Channel)/VP(Virtual Path)やDLCI)の決定法に関しては記述されていない。
【００１７】
本発明の他の目的は、高速にフロー検出を実行してVC/VPあるいはDLCIを決定し、ATMやフレームリレーネットワークのQoS制御を活用可能なルータ装置を提供することである。
【００１８】
【課題を解決するための手段】
上記目的を達成するために、本発明のパケット中継装置では、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報のうち少なくとも一つの情報と、その情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとし、該エントリを複数有するエントリテーブルを、前記アドレス情報毎に分割して設定したことを特徴とする。
【００１９】
また、他のパケット中継装置では、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報のうちの少なくとも一つの情報と、その情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとし、該エントリーを複数有するエントリテーブルと、前記エントリテーブル内のエントリを指定するエントリポインタを前記アドレス情報毎に分割して設定したエントリーポインタテーブルとを有することを特徴とする。
【００２０】
また、他のパケット中継装置では、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報のうちの少なくとも一つの情報と、その情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとし、該エントリを複数有するエントリテーブルが、前記アドレス情報毎に分割して設定されており、前記内部ヘッダ情報が付加された入力パケット内のアドレス情報に対応するエントリテーブルのみを検索し、そのエントリを読み出すエントリ読み出し手段と、前記入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報と前記エントリ読み出し手段が読み出したエントリ内の情報との一致判定をする一致判定手段と、前記一致判定手段で一致と判定された場合に、前記エントリ内の前記通信品質制御情報又は前記フィルタリング制御情報により、前記入力パケットの転送の優先度又は、転送の可否を決定する手段とをパイプライン制御することを特徴とする。
【００２１】
また、他のパケット中継装置では、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報のうちの少なくとも一つの情報と、その情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとし、該エントリーを複数有するエントリテーブルと、前記エントリテーブル内のエントリを指定するエントリポインタを前記アドレス情報毎に分割して設定したエントリーポインタテーブルとを有し、入力パケット内のアドレス情報に対応するエントリポインタのみを読み出すエントリポインタ読み出し手段と、前記エントリポインタ読みだし手段が読み出したエントリポインタが指定するエントリを前記エントリテーブルから読み出すエントリ読み出し手段と、入力パケット内のアドレス情報、用途を識別する情報又は優先度を識別する情報と、前記エントリ読み出し処理部が読み出したエントリ内の情報との一致判定をする一致判定手段と、前記一致判定手段で一致と判定された場合に、前記エントリ内の前記通信品質制御情報又は前記フィルタリング制御情報により、入力パケットの転送の優先度又は、転送の可否を決定する手段とをパイプライン制御することを特徴とする。
【００２２】
また、他のパケット中継装置では、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報のうちの少なくとも一つの情報と、その情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとし、該エントリを複数有するエントリテーブルが、前記アドレス情報毎に分割して設定されており、入力パケットのアドレス情報に対応するエントリテーブルのみを検索し、そのエントリを読み出すエントリ読み出し手段と、入力パケット内のアドレス情報、用途を識別する情報又は優先度を識別する情報と前記エントリ読み出し手段が読み出したエントリ内の情報との一致判定をする一致判定手段とを有し、前記エントリテーブルと前記一致判定手段とは同一の半導体チップに実装したことを特徴とする。
【００２３】
また、他のパケット中継装置では、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報のうちの少なくとも一つの情報と、その情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとし、該エントリーを複数有するエントリテーブルと、前記エントリテーブル内のエントリを指定するエントリポインタを前記アドレス情報毎に分割して設定したエントリーポインタテーブルとを有し、入力パケット内のアドレス情報に対応するエントリポインタのみを読み出すエントリポインタ読み出し手段と、前記エントリポインタ読みだし手段が読み出したエントリポインタが指定するエントリを前記エントリテーブルから読み出すエントリ読み出し手段と、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報と、前記エントリ読み出し手段が読み出したエントリ内の情報との一致判定をする一致判定手段とを有し、前記エントリテーブルと前記一致判定手段とは同一の半導体チップに実装したことを特徴とする。望ましくは、前記エントリポインタテーブルは前記半導体チップと異なる半導体チップで構成する。
【００２４】
また、他のパケット中継装置では、複数の入力回線のうちの一つの入力回線から入力された入力パケットを複数の出力回線の何れかの出力回線に出力するスイッチ手段と、入力パケットの送信者を識別する情報、受信者を識別する情報、用途を識別する情報、又は優先度を識別する情報のうち少なくとも一つの情報に応じて、該入力されたパケットに対する通信品質制御情報又はフィルタリング制御情報を決定するフロー検出手段とを有し、前記スイッチ手段と、前記フロー検出手段とは、それぞれ異なる半導体チップに実装されていることを特徴とする。
【００２５】
また、他のパケット中継装置では、入力パケットのアドレス情報と、前記アドレス情報の有効／無効を示すフラグ情報と、それらの情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとし、該エントリを複数有するエントリテーブルを有することを特徴とするパケット中継装置。望ましくは、前記アドレス情報は、インターネット・プロトコル（ＩＰ）アドレス情報と、入力回線情報であり、前記アドレス情報の有効／無効を示すフラグ情報は、前記ＩＰアドレス情報の有効／無効を示すフラグ情報と、前記入力回線情報の有効／無効を示すフラグ情報とする。前記エントリテーブルのエントリを読み出すエントリ読み出し手段と、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報と、前記エントリ読み出し処理部が読み出したエントリ内の情報との一致判定をする一致判定手段とを有し、前記一致判定手段は、ＩＰアドレス情報と、入力回線情報毎に設けられた複数の比較手段を有し、ＩＰアドレス情報に対応して設けらた前記比較手段は、前記ＩＰアドレス情報の有効／無効を示すフラグ情報に応じて動作し、入力回線情報に対応して設けらた前記比較手段は、前記入力回線情報の有効／無効を示すフラグ情報に応じて動作する。より具体的には、ＩＰアドレス情報に対応して設けらた前記比較手段は、前記ＩＰアドレス情報の有効／無効を示すフラグ情報が有効を示す場合のみ一致判定を行い、入力回線情報に対応して設けらた前記比較手段は、前記入力回線情報の有効／無効を示すフラグ情報が有効を示す場合のみ一致判定を行う。
【００２６】
また、前記エントリには、さらに入力パケットの用途を識別する情報と、前記用途を識別する情報の有効／無効を示すフラグ情報とが含めることが望ましい。
【００２７】
前記エントリテーブルのエントリを読み出すエントリ読み出し手段と、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報と、前記エントリ読み出し処理部が読み出したエントリ内の情報との一致判定をする一致判定手段とを有し、前記一致判定手段は、入力パケットのアドレス情報、用途を識別する情報毎に設けられた複数の比較手段を有し、アドレス情報に対応して設けらた前記比較手段は、前記アドレス情報の有効／無効を示すフラグ情報に応じて動作し、用途を識別する情報に対応して設けらた前記比較手段は、前記用途を識別する情報の有効／無効を示すフラグ情報に応じて動作する。より具体的には、アドレス情報に対応して設けらた前記比較手段は、前記アドレス情報の有効／無効を示すフラグ情報が有効を示す場合のみ一致判定を行い、用途を識別する情報に対応して設けらた前記比較手段は、前記用途を識別する情報の有効／無効を示すフラグ情報が有効を示す場合のみ一致判定を行う。
【００２８】
また、他のパケット中継装置では、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報のうちの少なくとも一つの情報と、その情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとし、該エントリを複数有するエントリテーブルが、前記アドレス情報毎に分割して設定されており、入力パケットのアドレス情報に対応するエントリテーブルのみを検索し、そのエントリを読み出すエントリ読み出し手段と、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報と、前記エントリ読み出し処理部が読み出したエントリ内の情報との一致判定をする一致判定手段とを有し、前記一致判定手段は、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報毎に比較手段を有していることを特徴とする。
【００２９】
また、他のパケット中継装置では、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報のうちの少なくとも一つの情報と、その情報に対応する通信品質制御情報又はフィルタリング制御情報とをエントリとし、該エントリーを複数有するエントリテーブルと、
前記エントリテーブル内のエントリを指定するエントリポインタを前記アドレス情報毎に分割して設定したエントリーポインタテーブルとを有し、入力パケットのアドレス情報に対応するエントリポインタのみを読み出すエントリポインタ読み出し手段と、前記エントリポインタ読み出し手段が読み出したエントリポインタが指定するエントリを前記エントリテーブルから読み出すエントリ読み出し手段と、入力パケットのアドレス情報、用途を識別する情報又は優先度を識別する情報と、前記エントリ読み出し処理部が読み出したエントリ内の情報との一致判定をする一致判定処理手段とを有し、前記一致判定手段は、入力パケット内のアドレス情報、用途を識別する情報又は優先度を識別する情報毎に比較手段を有していることを特徴とする。
【００３０】
その他の本願が解決しようとする課題、その解決手段は、本願の「発明の実施の形態」の欄及び図面で明らかにされる。
【００３１】
【発明の実施の形態】
以下、本発明の実施例を説明する。
【００３２】
まず、フロー検出方式であるリニアサーチ方式の問題点を図3乃至図6を用いて説明する。
【００３３】
図３は、ネットワークにおけるパケットのフォーマットの一例を示す。ネットワークにおけるパケットのフォーマットはヘッダ部410とデータ部420から構成される。ヘッダ部410はパケットを直前に送出したルータの物理アドレス（ハードウエアアドレス）である送信元MACアドレス（Source Address Media Access Control：以下「SAMAC」という。）400と、パケットを次に受信するルータの物理アドレスである宛先MACアドレス（Destination Address Media Access Control：以下「DAMAC」という。）401と、送信元アドレス（送信端末のアドレス）である送信元IPアドレス（Source IP Address：以下「SIP」という。）402と、宛先アドレス（受信端末のアドレス）である宛先IPアドレス（Destination IP Address：以下「DIP」という。）403と、プロトコル（＝上位アプリケーション）を表す送信元ポート（Source Port：以下「SPORT」という。）404と宛先ポート（Destination Port：以下「DPORT」という。）405とネットワーク内の優先度を表すTOS(Type of Service) 411(＝DSフィールド)から構成される。また、データ部420はユーザデータであるユーザデータ406から構成される。ヘッダ部410には前記情報以外にIPプロトコルの上位プロトコル等の情報も格納されているが、前記情報と同様に処理することができる。図3のフォーマットは、トランスポート層のプロトコルがTCP（Transmission Control Protocol）またはUDP（User Datagram Protocol）で、ネットワーク層のプロトコルがIP（Internet Protocol）のパケットのものを示したが、それ以外（例えばネットワーク層のプロトコルがIPX等）でも良い。
【００３４】
図4は、ルータ内部でのパケットのフォーマットの一例を示す。ルータ内部でのパケットのフォーマットはネットワークのパケットのフォーマットに内部ヘッダ部430がつけ加わる。この内部ヘッダ部430は入力回線番号である入力回線番号407と、出力回線番号である出力回線番号408と、QoS制御の優先転送にて使用する優先度情報409から構成される。
【００３５】
図6のエントリテーブル550は一つあるいは複数のエントリ510-i(=1〜H)から構成される。エントリ510-iはフロー条件部520-iとQoS制御情報部530-iから構成される。QoS制御情報部530-iは優先転送で使用するQoS制御情報である優先度情報507より成る。フロー条件部520-iは送信元あるいは宛先ユーザを識別するフロー条件と用途(アプリケーション)を識別するフロー条件と優先度を識別するフロー条件から構成される。送信元あるいは宛先ユーザを識別する条件はSIPとDIPの上限値と下限値であるSIP上限値501、SIP下限値502、DIP上限値503、DIP下限値504と、SIPとDIPの上限値と下限値が有効であることを示すIP有効ビット562と、入力回線番号である入力回線番号508と、入力回線番号508が有効であることを示す入力回線番号有効ビット561である。例えば、図2ネットワークのエッジルータB327はパケットが入力した回線によりパケットを送信した企業網(企業網C323か企業網D324か)を識別することができる。また、SIP、DIPにて上限値および下限値を設定する様にしたのは、ネットワーク(＝サブネット)を１つのエントリ510-iで指定可能とするためである。図5は、IPアドレス440のフォーマットを示す。IPアドレス440はネットワークアドレス441とホストアドレス442から構成される。ネットワークアドレス441によりネットワーク(＝サブネット)が識別され、ホストアドレス442により前記ネットワーク内の端末が識別される。IPアドレス440は、上位ビットがネットワークアドレスなので、同一ネットワーク内の端末は連続したIPアドレスを持つことになる。したがって、ネットワーク内の全ての端末をIPアドレスの範囲（上限値および下限値）で指定することができる。
【００３６】
用途を識別するフロー条件は送信元ポートであるSPORT 505と、宛先ポートであるDPORT 506と、前記SPORT 505とDPORT 506が有効であることを示すポート有効ビット563である。現在ポート番号が割り当てられているアプリケーションとポート番号の対応の一例を図45に示した。優先度を識別するフロー条件はTOS 515とTOS有効ビット564である。従来技術4のDiffservにおけるインテリアノードは前記TOS 515によりフロー検出を実行して優先転送を行う。
【００３７】
入力回線番号有効ビット561、IP有効ビット562、ポート有効ビット563、TOS有効ビット564はそれぞれ入力回線番号、IPアドレス、ポート番号、TOSによりパケットを識別する場合には「有効」と、識別しない場合には「無効」と設定される。
【００３８】
QoS制御情報の判定時、予め設定されたエントリ510-iがエントリテーブル550の上から順に読みだされる。そして、前記パケットの内部ヘッダ部430とヘッダ部410等の値とフロー条件部520-i内の有効なフロー条件に全て一致したか否か判定される。なお、一致した場合にはエントリ510-i内の優先度情報507がパケットの優先度情報と判定され、フロー検出は終了する。3番目のエントリ510-3のフロー条件に一致した場合、優先度情報507-3が優先度情報と判定され、4番目のエントリ510-4の検索は実行されず、フロー検出は終了する。
【００３９】
本願明細書では、上記のフロー検出方式をリニアーサーチ方式と呼ぶ。
【００４０】
図2に示すインターネット325でQoS制御およびフィルタリングを実行する場合を考える。図2のネットワークは同一企業の企業網A 321、企業網B 322、企業網C 323と、前記企業とは別の企業の企業網D 324が公衆IPネットワークであるインターネット325によって接続されたネットワークである。インターネット325は企業網A 321と企業網B 322が接続するエッジルータA 326と、企業網C 323と企業網D 324が接続するエッジルータB 327と、エッジルータA 326とエッジルータB 327を接続するバックボーンルータ328より構成される。また、企業網B 322のインターネット325への出入り口にはゲートウェイルータ329が配置されている。
【００４１】
QoS制御の優先転送は主にインターネット325内のエッジルータA 326とエッジルータB 327とバックボーンルータ328で、QoS制御の帯域監視やTOS書換は主にインターネット325内のエッジルータA 326と、エッジルータB 327で行われる。インターネット325では企業間の大量のパケットが通過するためパケットあたりの処理時間は短く、エッジルータA 326とエッジルータB 327とバックボーンルータ328は高速にQoS制御を行う必要がある。しかし、インターネット325に接続される企業網が増加すると多数の企業網を識別しなくてはならないため、エントリテーブル550に大量のエントリ510-iが設定される。リニアーサーチ方式ではエントリテーブル550に設定された全てのエントリ510-iが検索されるため、エッジルータA 326、エッジルータB 327、バックボーンルータ328は高速にQoS制御を実行することが困難になるおそれがある。
【００４２】
図2のネットワークでフィルタリングを行う場合を考える。フィルタリングにおけるフロー検出ではエントリ内の優先度情報507を転送の可否を示す転送可否情報とすれば良い。フィルタリングは企業網B322内のゲートウェイルータ329で行われる。企業網B322に入力する全てのパケットを処理するためパケットあたりの処理時間は短く、ゲートウェイルータ329は高速にフィルタリングを行う必要がある。フィルタリングでは同一企業である企業網A 321、企業網B 322、企業網C 323間のパケットを転送する様エントリ510-iが設定される。同一企業の企業網の数が3ではなく、さらに多くなると、設定されるエントリ510-iの数も増加する。リニアーサーチ方式ではエントリテーブル550に設定された全てのエントリ510-iが検索されるため、ゲートウェイルータ329は大量のエントリ510- iが設定されると高速にフィルタリングを行うことが困難となるおそれがある。
【００４３】
以上のように、リニアーサーチ方式では大量のエントリ510-iが設定されるネットワークにおいて、ルータは高速にQoS制御やフィルタリングを実行することが困難となるおそれがある。そこで、本実施例のフロー検出方式では、大量のエントリ510- iが設定された場合でもリニアサーチ方式と比較して高速にフロー検出を行うことができる入力回線限定方式を採用する。以下、入力回線限定方式の概要を説明する。
【００４４】
入力回線限定方式では、リニアーサーチ方式のフロー条件部520-iを構成する入力回線番号508に一致するエントリ510-iだけが検索される。図7は入力回線限定方式の一実施例を示す。
【００４５】
図7による入力回線限定方式ではリニアーサーチ方式のフロー条件部520-iから入力回線番号508と入力回線番号有効ビット561を削除したエントリ511-iが入力回線毎に設定される。フロー条件である入力回線番号が一致したエントリ511-iだけ検索されるため、エントリ511-i内に入力回線番号508は必要ない。
【００４６】
図8は、入力回線限定方式の他の実施例を示す。図7で説明した入力回線限定方式では、入力回線番号に関係ないエントリ511-iを設定する（例えば「全ての入力回線から入力されたTelnetのトラヒックは高優先」と設定する）場合、エントリ511-iを入力回線数(=N)分設定する必要があり、エントリテーブル551を実現するメモリの効率が悪くなる場合がある。そこで、図8に示す入力回線限定方式では、エントリテーブル750のアドレスであるリスト540を入力回線毎にリストテーブル760に設定しておく。リストテーブルアドレスが1のリスト540-11はエントリ511-1のアドレスを、リストテーブルアドレスが2のリスト540-12はエントリ511-Hのアドレスである。フロー検出時にはパケットが入力された入力回線に割り当てられたリスト540だけ読みだされ、前記リスト540がポイントするエントリ511-iが読み出される。ビット幅の小さなリスト540(1024エントリ持った時にも10bit)を入力回線毎に所持し、ビット幅の大きなエントリ511-iを各入力回線で共有すればエントリテーブル750を実現するメモリを有効に使用することができる。このため、高速化を実現しつつ、多数のエントリ511-iを設定することが可能となる。
【００４７】
図1は、ルータの一構成例を示す。ルータ100はルーティング処理とフロー検出とARP（Address Resolution Protocol）処理を行うヘッダ処理部110とパケットの入出力を行うパケット入出力部120とプロセッサ130から構成される。ヘッダ処理部110はルーティング処理部111と、フロー検出部112と、ARP処理部113より、パケット入出力部120は出力FIFO（First In First Out）バッファ振り分け回路121、回線対応部122-i(i=1〜N)および回線i 123-iより構成される。また、プロセッサ130にはルータ100外部の管理端末140が接続されている。
【００４８】
回線i 123-iからパケットが入力されると、受信回路124-iは前記パケットが入力された回線の番号 iを入力回線番号407として付加する。そして、ルータ内部のパケットフォーマットに変換した後、入力FIFOバッファ126-iに送信する。この時の出力回線番号408とQoS制御情報409は無意味な情報となる。入力FIFOバッファ126-iはパケットを蓄積し、パケットが蓄積された順番にパケットを出力FIFOバッファ振り分け回路121に送信する。出力FIFOバッファ振り分け回路121はそのパケットを一時蓄積バッファ128に蓄積すると共に、ヘッダ情報11をヘッダ処理部110に出力する。ヘッダ情報11は内部ヘッダ部430とヘッダ部410内の情報から構成される。
【００４９】
ルーティング処理部111はヘッダ情報11内のDIPからルーティングテーブルを検索し、前記DIPが属するサブネットに転送するための出力回線番号と、ルータ100が送出するパケットを次に受信するルータのIPアドレス（NIP：Next Hop IP Address）を判定する。ルータ100のプロセッサ130がこのルーティングテーブルの作成、管理を実行する。このルーティングテーブルの検索に関しては、例えば特開平10-222535号に記載されている。さらに、ルーティング処理部111は前記出力回線番号から構成される出力回線情報12をパケット入出力部120の出力FIFOバッファ振り分け回路121とフロー検出部112に、NIPから構成されるNIP情報14をARP処理部113に出力する。出力FIFOバッファ振り分け回路121は前記出力回線情報12を受信すると、一時蓄積バッファ128に蓄積されているパケットの出力回線番号408に前記出力回線情報12を書き込む。
【００５０】
ARP処理部113は前記NIP情報14を受信すると、そのNIPに対応するMACアドレスを決定する。さらに、前記MACアドレスから構成されるDAMAC情報15をパケット入出力部120の出力FIFOバッファ振り分け回路121とフロー検出部112に出力する。出力FIFOバッファ振り分け回路121は前記DAMAC情報15を受信すると、一時蓄積バッファ128に蓄積されているパケットのDAMAC401に前記DAMAC情報15を書き込む。
【００５１】
一方、フロー検出部112はヘッダ情報11を基にエントリテーブル750を検索して優先度情報を判定する。さらに、優先度情報から成るパケット優先度情報13をパケット入出力部120の出力FIFOバッファ振り分け回路121に出力する。出力FIFOバッファ振り分け回路121はパケット優先度情報13を受信すると、一時蓄積バッファ128に蓄積されているパケットのQoS制御情報409に前記パケット優先度情報13を書き込む。
【００５２】
出力FIFOバッファ振り分け回路121は出力回線番号408、DAMAC401およびQoS制御情報409が全て書き込まれた時点で、出力回線番号408が指示する回線対応部122-iのQoS制御情報409が指示する出力FIFOバッファ127-ij（j=1 or 2）にパケットを送信する。回線対応部122-iは出力FIFOバッファ127-ijに前記パケットを蓄積する。回線対応部122-i内の送信回路125-iは出力FIFOバッファ127-ijの読み出しを制御する。読みだし制御として「完全優先制御」や「重みづけ巡回制御」等が知られている。「完全優先制御」では優先度の高い出力FIFOバッファ127-i1にパケットが蓄積されている場合、出力FIFOバッファ127-i1からパケットが蓄積された順番にパケットが読みだされる。出力FIFOバッファ127-i1にパケットが蓄積されていない時だけ優先度の低い出力FIFOバッファ127-i2からパケットが蓄積された順番にパケットが読み出される。一方、「重みづけ巡回制御」では予め設定された比率に基づき出力FIFOバッファ127-i1および出力FIFOバッファ127-i2からパケットが読み出される。なお、送信回路125-iにおける読み出し制御はルータ100の管理者により管理端末140を用いて設定される。さらに、送信回路125-iは読み出したパケットの内部ヘッダ部430を削除する。そして、SAMAC401に回線i 123-iのMACアドレスを書き込み、回線i 123-iにパケットを送出する。
【００５３】
フロー検出部112のブロック図を図12に示す。フロー検出部112は結果判定部710、条件一致判定部720、リスト読み出し部730、エントリ読み出し部740、エントリテーブル750、リストテーブル760から構成される。フロー検出部112のフローチャートを図11に示す。フロー検出部112の処理は検出開始処理600、リスト読みだし処理630、エントリ読み出し処理640、条件一致判定処理620、結果判定処理610の５つに大きく分けられる。後述の４つの処理はそれぞれ、リスト読みだし部730、エントリ読み出し部740、条件一致判定部720、結果判定部710において実行される。
【００５４】
エントリテーブル750のフォーマットを図8に示す。エントリ読み出し処理640を短時間で行うために、図17に示す様にエントリテーブル750は半導体チップ 1200内部のメモリで実現される。半導体チップ内部のメモリを使用すると半導体チップ 1200のデータ入出力ピンを使用せず大量のデータを一度に読み出すことが可能であるため、半導体チップ内部のメモリはエントリテーブル750の実現に適している。半導体チップ 1200外部のメモリでエントリテーブル750を実現する場合、半導体チップ 1200のピンには限りがあるため、エントリテーブル750を接続するために大量のピンを使用できない。そのため、一度に読み出し可能なビット幅が小さく、エントリ読み出し処理640の処理時間が長くなる。フロー検出を高速化する観点から見ると、半導体チップ 1200外部のメモリはエントリテーブル750の実現に不向きである。
【００５５】
リストテーブル760は入力回線毎のG個のリスト540より構成される。リスト540の数Gはエントリテーブル750のエントリ511の収容個数HとG≦Hの関係がある。フロー検出時には、パケットが入力された入力回線のリスト540だけメモリアドレスが一番小さいリスト540から大きいリスト540へと順番に読み出される。
【００５６】
リストテーブル760は図17に示した様に半導体チップ 1200外部のメモリで実現される。リスト540はビット幅が小さいため、半導体チップ 1200のピン数を消費しなくても高速に読み出すことができる。また、全ての入力回線に全エントリ511-iを設定可能とした時(即ち、G=Hの時)、「リストテーブル760の容量＝リスト540のビット幅×入力回線数×エントリ数(＝H)」となるため、入力回線数が増加するとリストテーブル760の容量が大きくなる。そのため、容量の大きな半導体チップ1200外部のメモリはリストテーブル760に最適である。また、エントリ511-iを指定するビット幅の小さなリスト540を入力回線毎に持ち、エントリ511-iを入力回線で共有することによりメモリの容量の小さい半導体チップ 1200内部のメモリを効率良く使用することができる。
【００５７】
以下、フロー検出時の処理を図11を用いて順番に説明する。検出開始処理600では、パケットのヘッダ情報11がヘッダ処理部110に送信されると、フロー検出部112は前記ヘッダ情報11内の入力回線番号407、SIP402、DIP 403、SPORT404、DPORT405およびTOS 411の各情報をそれぞれリスト読み出し部730内の入出力回線番号蓄積手段732、条件一致判定部720内のパケット内SIP蓄積手段722-2、パケット内DIP蓄積手段723-2、パケット内SPORT蓄積手段724-2、パケット内DPORT蓄積手段725-2およびパケット内TOS蓄積手段728-2に蓄積する(ステップ601)。
【００５８】
リスト読みだし処理630は、リスト読みだし部730がリストテーブル760のヘッダ情報11内の入力回線番号に割り当てられたリスト540だけを読みだしてリスト蓄積手段741に蓄積する処理である。まず、リスト読みだし部730は回線i用の先頭のリスト540-i1を読み出す様に、リスト番号カウンタ733の値Mを1にリセットする(ステップ631)。次に、リストテーブルアドレス生成回路731は入出力回線番号蓄積手段732に蓄積されている入力回線番号とリスト番号カウンタ733の値M(今の場合1)からリストテーブル760のアドレスを生成しリスト540-i1を読みだし、リスト蓄積手段741に蓄積する(ステップ632)。リストテーブル760のアドレスは「(入力回線番号−1)×入力回線毎のリストの個数G＋M」となる。最後に、リストテーブルアドレス生成回路731はリスト540を読み出したことをリスト番号カウンタ733に通知し、リスト番号カウンタ733は次のリスト読み出し処理630を実行する時にリスト540-i2を読み出すように、リスト番号カウンタ733の値Mを１カウントアップする(ステップ633)。以上のリスト読み出し処理630を繰り返すことにより、リスト読み出し部730はリスト540をリストテーブルアドレスが小さい方から大きい方へ順番に読み出す。
【００５９】
エントリ読み出し処理640では、エントリ読み出し部740はエントリテーブル750からエントリ511-iを読み出す。エントリ読み出し部740内のエントリテーブルアドレス生成回路742はリスト蓄積手段741に蓄積されている値をそのままエントリテーブルアドレスとしてエントリテーブル750からエントリ511-iを読みだし、SIP上限値501とSIP下限値502の情報を条件一致判定部720内のエントリ内SIP蓄積手段722-3に、DIP上限値503とDIP下限値504の情報をエントリ内DIP蓄積手段723-3に、SPORT 505とDPORT 506の情報をそれぞれエントリ内SPORT蓄積手段724-3とエントリ内DPORT蓄積手段725-3に、TOS515の情報をエントリ内TOS蓄積手段728-3に、IP有効ビット562とポート有効ビット563とTOS有効ビット564を有効ビット蓄積手段726に、優先度情報507を結果判定部710のQoS制御情報蓄積手段713に蓄積する(ステップ641)。
【００６０】
条件一致判定処理620では、条件一致判定部720はエントリ内SIP蓄積手段722-3、エントリ内DIP蓄積手段723-3、エントリ内SPORT蓄積手段724-3、エントリ内DPORT蓄積手段725-3、エントリ内TOS蓄積手段728-3に蓄積されているフロー条件に優先度情報を判定するパケットが一致するか否かを判定する。図11のフローチャートではSIP、DIP、SPORT、DPORT、TOSの各フロー条件とパケットが一致するか否か判定する処理は直列に行う様に書かれているが、条件一致判定部720は条件一致判定処理620を短時間で実行するために、SIP、DIP、SPORT、DPORT、TOSの各フロー条件専用に比較回路を持ち並列に判定を実行する。
【００６１】
SIP比較回路722-1はパケット内SIP蓄積手段722-2に蓄積されているSIP上限値および下限値とエントリ内SIP蓄積手段722-3に蓄積されているSIPが「SIP下限値≦ SIP ≦ SIP上限値」の条件を満たすかまたは有効ビット蓄積手段726内のIP有効ビットが「無効」の場合に「一致」と判定する(ステップ621-1)。DIP比較回路723-1はSIPと同様の処理をDIPに関して実行する(ステップ621-2)。SPORT比較回路724-1はパケット内SPORT蓄積手段724-2に蓄積されているSPORTとエントリ内SPORT蓄積手段724-3に蓄積されているSPORTが等しいかまたは有効ビット蓄積手段726内のポート有効ビットが「無効」の場合に「一致」と判定する(ステップ621-3)。DPORT比較回路725-1はSPORTと同様の処理をDPORTに関して実行する(ステップ621-4)。TOS比較回路728-1はパケット内TOS蓄積手段728-2に蓄積されているTOSとエントリ内TOS蓄積手段728-3に蓄積されているTOSが等しいかまたは有効ビット蓄積手段726内のTOS有効ビットが「無効」の場合に「一致」と判定する(ステップ621-6)。条件一致判定回路721はステップ621-1、ステップ621-2、ステップ621-3、ステップ621-4、ステップ621-6において全て「一致」と判定された場合、結果判定部710内の条件一致結果蓄積手段712に「一致」を表す情報を(ステップ622-1)、それ以外の場合、「不一致」を表す情報を蓄積する(ステップ622-2)。 上記実施例では各比較回路がIP有効ビット562、ポート有効ビット563およびTOS有効ビット564が「無効」のフロー条件には常に「一致」と判定することにより、前記有効ビットが「無効」の場合には、パケット内のSIP/DIPとSPORT/DPORTとTOSの比較を行わなかった場合と同様に振る舞う。これら有効ビットを設けることにより、IPアドレス、ポート番号またはTOSに無関係なフロー条件を記述することができ、フロー条件の記述性が大幅に向上する。これにより、ルータ100の管理者が望む多種多様なフロー条件に柔軟に対応することができる。
【００６２】
結果判定処理610では、条件一致結果蓄積手段712に「一致」を表す情報が格納されている時、結果判定回路711はQoS制御情報蓄積手段713の値を優先度情報と決定し、前記優先度情報から構成されるパケット優先度情報13をパケット入出力部120の出力FIFOバッファ振り分け回路121に出力し、フロー検出を終了する(ステップ611)。条件一致結果蓄積手段712に「不一致」を表す情報が格納されている時、フロー検出部112はステップ632に戻りフロー検出処理を継続し、最終的に優先度情報を判定する。
【００６３】
入力回線限定方式では、検索するエントリ511-iを入力回線番号に一致したエントリ511-iに限定することにより高速化を図っている。図2のネットワークのエッジルータB 327で企業網C 323と企業網D 324が送出したパケットのQoS制御を行う場合を考える。企業網C 323と企業網D 324は企業が異なるため、一般的にはフロー検出が異なる。そのため、エッジルータB 327は企業網C323用のエントリ511-iと企業網D 324用のエントリ511-iを持たなくてはならない。リニアーサーチ方式ではこれら全てのエントリ511-iを検索されが、入力回線限定方式では前記エントリ511-iのうち入力回線（企業網）が一致するエントリ511-iのみ検索される。そのため、入力回線限定方式はリニアサーチ方式に比べて２倍の性能を実現する。エッジルータB 327にK社の企業網が接続される場合、およそK倍の性能を実現する。さらに、リスト540を導入することにより、多数のフロー条件を設定できる。
【００６４】
フロー検出方式の他の実施例として出力回線限定方式を説明する。出力回線限定方式では、フロー条件である出力回線番号が一致するエントリ511-iのみ処理され、フロー検出の高速化が実現される。以下、入力回線限定方式との相違点を中心に出力回線限定方式について説明をする。
【００６５】
出力回線限定方式のリストテーブル760は入力回線毎ではなく出力回線毎にリスト540を所持する。それに伴い、ステップ601ではフロー検出部112は入出力回線蓄積手段732に入力回線番号を蓄積されず、ルーティング処理部111が送出する出力回線情報12内の出力回線番号が蓄積される。さらに、ステップ632では、リストテーブルアドレス生成回路731は入出力回線番号蓄積手段732内の出力回線番号とリスト番号カウンタ733の値Mからリストテーブルアドレスを生成する。これら以外は入力回線限定方式と同一である。
【００６６】
図2のネットワークのエッジルータB 327で企業網C 323と企業網D 324に送出するパケットのQoS制御を行う場合を考える。企業網C 323へ送出するパケットと企業網D 324へ送出するパケットのフロー検出が異なる場合、入力回線限定方式と同様に出力回線限定方式はリニアーサーチ方式に比べ2倍の性能を実現する。
【００６７】
フロー条件としてヘッダ情報11内の入力回線番号の代わりにSAMACを用いた際のSAMAC限定方式について説明する。SAMAC限定方式では、SAMACのグループであるSAMACグループが定義され、前記SAMACグループの識別子であるSAMAC識別子が一致するエントリのみ検索が行われる。 以下、入力回線限定方式との相違点を中心にSAMAC限定方式について説明する。
【００６８】
図9は、SAMAC限定方式のおけるエントリテーブル750およびリストテーブル860のフォーマットを示す。エントリテーブル750は入力回線限定方式と同一であるが、リストテーブル860はSAMAC識別子でL個の領域に分割される。また、フロー検出部812のブロック図を図13に示す。リスト読み出し部830は入出力回線番号蓄積手段732の代わりに、MAC識別子蓄積手段832およびMAC識別子生成回路834を備える。
【００６９】
ステップ601では、MAC識別子生成回路834がSAMAC（6Byte）をハッシュ関数によりハッシュし、SAMACよりビット幅の小さなSAMAC識別子を生成する。さらに、リストテーブル860は前記 SAMAC識別子を入力回線番号の代わりにMAC識別子蓄積手段832に蓄積する。なお、前記ハッシュ関数のハッシュ値が同一のSAMACが一つのSAMACグループを構成する。ステップ632では、リストテーブルアドレス生成回路831はMAC識別子蓄積手段832内のSAMAC識別子とリスト番号カウンタ733の値Mからリストテーブルアドレスを生成する。これら以外は入力回線限定方式と同一である。
【００７０】
図18に示したネットワークでQoS制御を実行する場合を考える。このネットワークはルータA1301の回線A1311（MACアドレスAを持つ）と、ルータB1302の回線B1312（MACアドレスBを持つ）と、ルータC1303の回線C1313（MACアドレスCを持つ）がバス接続されたネットワークである。ルータA1301がネットワークB1322およびネットワークC1323の送出したパケットのQoS制御を実行する。この場合、ルータA1301は受信パケットの送信ネットワークを入力回線番号で識別することができない。そのため、ルータA1301はMACアドレス（MACアドレスBかCか）からネットワークを識別する。ネットワークB1322とネットワークC1323でフロー検出が異なる場合、ルータA1301はネットワークB1322用のエントリ511-iとネットワークC1323用のエントリ511-iを持たなくてはならない。この時、MACアドレスBとCのSAMAC識別子が異なれば、パケット入力時には片一方のネットワークのエントリ511-iだけが検索され、SAMAC限定方式はリニアーサーチ方式に比べ2倍の性能を実現できる。
【００７１】
フロー条件としてヘッダ情報11内のSAMACの代わりにARP処理部113が決定するDAMACを用いた際のDAMAC限定方式を説明する。DAMAC限定方式では、DAMACのグループであるDAMACグループが定義され、前記DAMACグループの識別子であるDAMAC識別子が一致するエントリのみ検索が行われる。以下、SAMAC限定方式との相違点を中心にDAMAC限定方式について説明する。
【００７２】
DAMAC限定方式のおけるリストテーブル860はSAMAC識別子でなくDAMAC識別子で分割されている。SAMAC限定方式では、MAC識別子生成回路834がヘッダ情報11内のSAMACからSAMAC識別子を生成していた。しかし、DAMAC限定方式のステップ601では、MAC識別子生成回路834がDAMAC情報15内のDAMACからDAMAC識別子を生成し、前記DAMAC識別子をMAC識別子蓄積手段832に蓄積する。また、ステップ632では、リストテーブルアドレス生成回路831はMAC識別子蓄積手段832内のDAMAC識別子とリスト番号カウンタ733の値Mからリストテーブルアドレスを生成する。これら以外はSAMAC限定方式と同一である。
【００７３】
図18のネットワークのルータA1301がネットークB1322およびネットワークC1323に送出するパケットのQoS制御を実行する場合を考える。ネットワークB1322およびネットワークC1323へ送出するパケットのフロー検出が異なる場合、MACアドレスBとCのDAMAC識別子が異なれば、パケット入力時には片一方のネットワークのエントリ511-iだけが検索され、DAMAC限定方式はリニアーサーチ方式に比べ2倍の性能を実現できる。
【００７４】
次に、送信元サブネットでエントリを限定する送信元サブネット限定方式を説明する。以下、入力回線限定方式との相違点を中心に送信元サブネット限定方式について説明する。
【００７５】
送信元サブネット限定方式のおけるエントリテーブル1050およびリストテーブル1060のフォーマットを図10に示した。エントリテーブル1050内のエントリ510-iは入力回線番号508と入力回線番号有効ビット561が入力回線限定方式のエントリ511-iに比べ増加し、リニアサーチ方式のエントリと同一になる。一方、リストテーブル1060は送信元サブネット識別子でR個の領域に分割されている。
【００７６】
送信元サブネット限定方式におけるフロー検出部1012のブロック図を図15に示す。送信元サブネット限定方式のフロー検出部1012は入出力回線番号蓄積手段732がサブネット識別子蓄積手段1032となり、回線番号比較回路1027-1と、パケット内回線番号蓄積手段1027-2と、エントリ内回線番号蓄積手段1027-3が増加する。さらに、ルーティング処理部111にも変更が加わる。入力回線限定方式のルーティング処理部111はDIPが属するサブネットに転送するための出力回線番号を判定していた。しかし、送信元サブネット限定方式では出力回線番号だけでなくDIPが属するサブネットの識別子である宛先サブネット識別子を決定する。前述した特開平10-222535号公報に記載の検索方式を用いれば、ルーティング処理部111は宛先サブネット識別子も決定することができる。さらに、ルーティング処理部111はDIPと同様の方法を用いて、SIPが属するサブネットの識別子である送信元サブネット識別子も決定する。前記送信元および宛先サブネット識別子から構成されるサブネット識別子情報16をフロー検出部1012に送信する。
【００７７】
送信元サブネット限定方式のおけるフローチャートを図14に示す。以下、図14のフローチャートを用いて入力回線限定方式の処理との相違点を中心に送信元サブネット限定方式の処理を説明する。まず、リストテーブル1060のフォーマット変更に伴う変更箇所を説明する。検出開始処理900のステップ901では、フロー検出部1012はヘッダ情報11内の入力回線番号408を入出力回線番号蓄積手段732ではなく、条件一致判定部1020内のパケット内回線番号蓄積手段1027-2に蓄積する。フロー検出部1012は前記サブネット識別子情報16を受信すると、送信元サブネット識別子をサブネット識別子蓄積手段1032に蓄積する(ステップ902) 。リスト読み出し処理930では、リストテーブルアドレス生成回路1031は、サブネット識別子蓄積手段1032に蓄積された送信元サブネット識別子とリスト番号カウンタ733の値Mからリストテーブルアドレスを生成し、リストテーブル1060内のリスト540を読み出す(ステップ932)。次に、条件一致判定部1020が入力回線番号の比較を実行するための変更箇所を説明する。エントリ読みだし処理940のステップ941にはエントリ内回線番号蓄積手段1027-3に入力回線番号508を蓄積する処理と、入力回線番号有効ビット561を有効ビット蓄積手段1026に蓄積する処理が加わる。また、条件一致判定処理920では、回線番号比較回路1027-1がパケット内回線番号蓄積手段1027-2内の情報とエントリ内回線番号蓄積手段1027-3内の情報と有効ビット蓄積手段1026内の入力回線番号有効ビット561から一致判定を行う処理(ステップ921-5)が加わる。上記以外の動作は入力回線限定方式と同一である。
【００７８】
図2のネットワークのバックボーンルータ328で企業網C 323と企業網D 324が送出したパケットのQoS制御を行う場合を考える。エッジルータB327とは異なり入力回線番号で企業網を識別できないため、送信元サブネットが企業網の特定に使用される。企業網Cと企業網D 324のフロー検出が異なる時、バックボーンルータ328は企業網C323用のエントリ510-iと企業網D 324用のエントリ510-iを持たなくてはならない。リニアーサーチ方式ではこれら全てのエントリ510-iが検索されるが、送信元サブネット限定方式では前記エントリのうち送信元サブネットが一致するエントリのみ検索される。そのため、送信元サブネット限定方式はリニアサーチ方式に比べ2倍の性能を実現する。
【００７９】
次に、宛先サブネットでエントリを限定する宛先サブネット限定方式を説明する。以下、送信元サブネット限定方式との相違点を中心に宛先サブネット限定方式について説明する。
【００８０】
宛先サブネット限定方式ではリストテーブル1060は送信元サブネット識別子ではなく宛先サブネット識別子毎にリスト540を所持する。それに伴い、ステップ902では、サブネット識別子蓄積手段1032にサブネット識別子情報16内の宛先サブネット識別子を蓄積する。さらに、ステップ932では、リストテーブルアドレス生成回路1031はサブネット識別子蓄積手段1032内の宛先サブネット識別子とリスト番号カウンタ733の値Mからリストテーブルアドレスを生成する。これら以外は送信元サブネット限定方式と同一である。
【００８１】
図2のネットワークのバックボーンルータ328で企業網C 323と企業網D 324へ転送するパケットのQoS制御を行う場合を考える。企業網C 323と企業網D 324のフロー検出が異なる場合、宛先サブネットでエントリ510-iを限定しているため、宛先サブネット限定方式はリニアサーチ方式に比べ2倍の性能を実現できる。
【００８２】
これまでQoS制御情報が優先度情報の場合について説明してきた。帯域監視を実行するために必要な帯域監視情報およびTOS書換を実行するために必要な書換TOS情報の決定について説明する。入力回線限定方式によりフロー検出を実行し、帯域監視情報および書換TOS情報を決定する場合のテーブルフォーマットを図22に、結果判定部2310のブロック図を図23に、ヘッダ処理部2410のブロック図を図24に、フローチャートを図25に示した。以下、QoS制御の優先度情報のみを判定するフロー検出(入力回線限定方式)を実施した場合との違いを説明する。エントリ内のQoS制御情報部2230は帯域監視情報2213および書換TOS情報2214が新たに加わる。それに伴い、フロー検出時にはエントリ読みだし処理2540のステップ2541に帯域監視情報2213および書換TOS情報2214をQoS制御情報蓄積手段2316に蓄積する処理が加わる。結果判定処理2510では、結果判定回路2311はQoS制御情報蓄積手段2316の値を優先度情報、帯域監視情報、書換TOS情報と決定し、前記優先度情報から構成されるパケット優先度情報13を出力FIFOバッファ振り分け回路121に送信する処理に加え、前記帯域監視情報から構成されるパケット帯域監視情報17を帯域監視部2414に、前記書換TOS情報から構成されるパケット書換TOS情報19を出力FIFOバッファ振り分け回路121に送信する(ステップ2511)。
【００８３】
帯域監視部2414はパケット帯域監視情報17から入力パケットの「遵守」または「違反」を判定し、判定結果を帯域監視結果情報18として出力FIFOバッファ振り分け回路121に出力する。出力FIFOバッファ振り分け回路121はパケット優先度情報13およびパケット書換TOS情報19を受信すると、一時蓄積バッファ128に蓄積されているパケットのQoS制御情報409とTOS411にそれぞれ書き込む処理が加わる。出力FIFOバッファ振り分け回路121は出力回線番号408、DAMAC401、QoS制御情報409およびTOS411が全て書き込まれた時点で、帯域監視結果情報18が「遵守」の場合は一時蓄積バッファ128のパケットを出力回線番号408が指示する回線対応部122-iのQoS制御情報409内の優先度情報が指示する出力FIFOバッファ127-ij（j=1 or 2）にパケットを送信する。帯域監視結果情報18が「違反」の場合は、一時蓄積バッファ128のパケットを廃棄するか、TOS411やQoS制御情報409内の優先度情報を低優先の優先度情報に書き換え、書き換え後の優先度情報が指示する出力FIFOバッファ127-ij（j=1 or 2）にパケットを送信する。
【００８４】
ルータ間を接続するATMあるいはフレームリレーネットワークにおいてもQoSを実現するために、ルータはユーザや用途に応じてコネクション(VC/VPやDLCI)を振り分けてデータリンク層のQoS制御を利用することが必要である。そのため、ルータはフロー検出を実行してコネクション情報を決定することも必要となる。図46を用いてコネクションの振り分けが必要な例を説明する。図46は公衆ATMネットワーク4301により企業網A4302と企業網B4303接続されたネットワークである。公衆ATMネットワーク4301はATMスイッチA 4310とATMスイッチB4311から構成される。また、企業網A4302のルータA4312と企業網B4303のルータB 4313間にはCBR(Constant Bit Rate)のコネクションVC1とUBR(Unspecified Bit Rate)のコネクションVC2が設定されている。VC1上のパケットはATMスイッチA4310とATMスイッチB 4311 においてVC2上のパケットよりも優先的に転送されQoSが保証されるが、VC2上のパケットのQoSは保証されない。企業網A4302から企業網B4303へパケットを送出すると、ルータA4312 はフロー検出を実行してQoSが必要なパケットにVC1を、それ以外のパケットにVC2を割り当てる。
【００８５】
入力回線限定方式によりフロー検出を実行し、コネクション情報を決定する場合のエントリテーブル2650のテーブルフォーマットを図26に、結果判定部2710のブロック図を図27に、フローチャートを図28に示した。QoS制御の優先度情報のみを判定するフロー検出(入力回線限定方式)を実施した場合との違いを説明する。エントリ内のQoS制御情報2630にはコネクション情報2615が新たに加わる。それに伴い、エントリ読みだし処理2840では、コネクション情報2615をQoS制御情報蓄積手段2716に蓄積する処理が加わる。結果判定処理2810では、結果判定回路2711は優先度情報を決定すると共にQoS制御情報蓄積手段2716内のコネクション情報の値をコネクション情報と決定し、パケット優先度情報13に加えて前記コネクション情報から構成されるパケットコネクション情報20を出力FIFOバッファ振り分け回路121に出力する(ステップ2811)。出力FIFOバッファ振り分け回路121はパケット優先度情報13に加えてパケットコネクション情報20を一時蓄積バッファ128に蓄積されているパケットのQoS制御情報409に書き込む。送信回路125はQoS制御情報409内のコネクション情報が指示するコネクションのパケットとして回線123-iにパケットを送出する。
【００８６】
これまでQoS制御におけるフロー検出について説明した。以下、フィルタリングにおけるフロー検出について説明する。入力回線限定方式をフィルタリングのフロー検出に適用した場合のテーブルフォーマットを図29に、結果判定部3010のブロック図を図30にフローチャートを図31に示した。以下、QoS制御の優先度情報を判定するフロー検出(入力回線限定方式) を実施した場合との違いを説明する。フィルタリングでは転送可否情報を決定するため、エントリ内のQoS制御情報部530がフィルタリング制御情報部2931となり、優先度情報507が転送可否情報2916となる。さらに、QoS制御情報蓄積手段713の代わりにフィルタリング制御情報蓄積手段3016となる。フロー検出時には、エントリ読みだし処理3140では、優先度情報507を蓄積する代わりに転送可否情報2916をフィルタリング制御情報蓄積手段3016に蓄積する。結果判定処理3110では、結果判定回路3011は優先度情報を決定する代わりにフィルタリング制御情報蓄積手段3016の値を転送可否情報と決定し、前記転送可否情報から構成されるパケット転送可否情報21を出力FIFOバッファ振り分け回路121に出力する(ステップ3111)。
【００８７】
QoS制御あるいはフィルタリング、いずれか一方のフロー検出を実行する場合について説明してきた。図2のインターネット325内のルータはQoS制御のみ行う場合が多いが、ゲートウェイルータ329は両方のフロー検出を行う必要がある。この場合、以下に説明する同時フロー検出方式または２段フロー検出方式が用いられる。
【００８８】
まず、同時フロー検出方式について説明する。同時フロー検出方式はQoS制御で使用するQoS制御情報とフィルタリングで使用する転送可否情報を同時に決定する方式である。入力回線限定方式に同時フロー検出方式を適用した場合のテーブルフォーマットを図32に、結果判定部3310のブロック図を図33に、フローチャートを図34に示した。
【００８９】
QoS制御の優先度情報のみを判定するフロー検出(入力回線限定方式)を実施した場合との違いを説明する。エントリ3211はQoS制御情報部530に加え転送可否情報2916より成るフィルタリング制御情報部2931が備わる。それに伴い、結果判定部3310にはフィルタリング制御情報蓄積手段3016が加わる。フロー検出時には、エントリ読みだし処理3440のステップ3441において、転送可否情報2916をフィルタリング制御情報蓄積手段3016に蓄積する処理が加わる。結果判定処理3410では、結果判定回路3311は優先度情報を決定しパケット優先度情報13を送出すると共にフィルタリング制御情報蓄積手段3016の値を転送可否情報と決定し、前記転送可否情報から構成されるパケット転送可否情報21を出力FIFOバッファ振り分け回路121に出力する。
【００９０】
次に、２段フロー検出方式について説明する。２段フロー検出方式では、QoS制御とフィルタリングのフロー検出が直列に実行される。入力回線限定方式に２段フロー検出方式を適用した場合のリストテーブル3560とエントリテーブル3550を図35に、ブロック図を図36に、フローチャートを図37に示した。以下、２段フロー検出方式を用いて優先度情報と転送可否情報を決定する場合について説明する。なお、図37ではステップ621-1〜4および621-6をまとめてステップ621と記してある。エントリテーブル3550にはフィルタリング用のエントリ2911とQoS制御用のエントリ511が混在する。リストテーブル3560はフィルタリング用のエントリ2911をポイントするフィルタリング用のリスト3540とQoS制御用のエントリ511をポイントするQoS制御用のリスト3541の領域に分割されており、フィルタリングのフロー検出時にはフィルタリング用のリスト3540、QoS制御のフロー検出時にはQoS制御用のリスト3541が読み出される。フロー検出部3612はフィルタリングまたはQoS制御いずれのフロー検出を実行しているかを表すフロー検出状態蓄積手段3670を新たに備える。
【００９１】
ヘッダ情報11が入力されると検出開始処理600のステップ601の後、フロー検出部3612はフィルタリングのフロー検出を行うためにフロー検出状態蓄積手段3670の値を「フィルタリングのフロー検出を表す値」にセットする(ステップ3750)。まず、フィルタリングのフロー検出を行う。リスト読みだし処理3730では、リスト読みだし部3630はフロー検出状態蓄積手段3670の値(この場合フィルタリングを表している)を参照し、フィルタリング用のエントリ2911をポイントするリスト3540を順に読み出していく(ステップ3732)。また、エントリ読み出し処理3740では、フロー検出状態蓄積手段3670の値が「フィルタリングのフロー検出を表す値」の時には、フィルタリング制御情報部3531内の転送可否情報がフィルタリング制御情報蓄積手段3016に蓄積される(ステップ3741)。条件一致判定処理620の後、結果判定処理3710でも結果判定部3610はフロー検出状態蓄積手段3670の値がフィルタリングあるいはQoS制御のフロー検出かを判定して(ステップ3713)、フィルタリングのフロー検出時、結果判定回路3611はフィルタリング制御情報蓄積手段3016の値をパケット転送可否情報21として送出する(ステップ3712)。さらに、結果判定部3610は転送可否情報が「廃棄」か「通過」かを参照する(ステップ3714)。フロー検出部3612は前記転送可否情報が「廃棄」の場合にはQoS制御用のフロー検出を実行せずにフロー検出を終了し(ステップ3715)、「通過」の場合には、QoS制御用のフロー検出を行うため、フロー検出状態蓄積手段3670の値を「QoS制御のフロー検出を表す値」にセットし(ステップ3760)、QoS制御のフロー検出を開始する。2段フロー検出方式では、フロー検出部3612はフィルタリング用のフロー検出を最初に行い、フィルタリングで廃棄されるパケットに対してQoS制御用のフロー検出を実行しないことにより、フロー検出を高速化している。
【００９２】
QoS制御のリスト読みだし処理3730ではリスト読み出し部3630はフロー検出状態蓄積手段3670の値(この場合QoS制御を表している)を参照し、QoS制御用のエントリ511をポイントするリスト3541を順に読み出していく(ステップ3732)。また、エントリ読み出し処理3740でも結果判定部3610はフロー検出状態蓄積手段3670の値が「QoS制御のフロー検出を表す値」の時には、QoS制御情報部3532内の優先度情報がQoS制御情報蓄積手段713に蓄積される(ステップ3741)。条件一致判定処理620の後、結果判定処理3710では、結果判定部3610はフロー検出状態蓄積手段3670の値がフィルタリングあるいはQoS制御のフロー検出かを判定して(ステップ3713) QoS制御のフロー検出の時には、結果判定回路3611はQoS制御情報蓄積手段713の値をパケット優先度情報13として送出し(ステップ3711)、フロー検出を終了する(ステップ3715)。
【００９３】
以上に述べた処理を実行することにより、QoS制御およびフィルタリング両方のフロー検出を行うことができる。
【００９４】
フロー条件により、２段フロー検出方式の方が設定エントリが少なく高速化に適している場合と、同時フロー検出方式の方が設定エントリが少なく高速化に適している場合がある。まず、QoS制御とフィルタリングのフロー条件が同一なフロー検出を図2のゲートウェイルータ329にて実行する場合について説明する。図38に同時フロー検出方式におけるエントリテーブル3250の設定を、図39に２段フロー検出方式におけるエントリテーブル3550の設定を示す。図39のエントリテーブル3550の上から3つのエントリがフィルタリング用、下から２つのエントリがQoS制御用である。フィルタリングとQoS制御 共にフロー条件はSIP＝企業網A321、企業網C323、企業網D324、DIP=企業網B322である。フィルタリングではゲートウェイルータ329は企業網A 321、企業網C 323からのパケットを転送し、別企業である企業網D324からのパケットを廃棄する。一方、QoS制御では企業網A 321からのパケットを優先転送し、企業網C 323からのパケットを非優先転送する。２段フロー検出方式の場合、5つのエントリが設定されるが、同時フロー検出方式の場合、3つのエントリが設定されるだけで良い。なお、２段フロー検出方式において企業網D324のQoS制御用のエントリが無いのは、ステップ3714にて廃棄の場合、フロー検出部3612はQoS制御用のフロー検出を行わず、フロー検出を終了し、フロー検出を高速化しているからである。
【００９５】
次に、QoS制御とフィルタリングのフロー条件が異なるフロー検出を図2のゲートウェイルータ329にて実行する場合について説明する。図40に同時フロー検出方式におけるエントリテーブル3250の設定を、図41に２段フロー検出方式におけるエントリテーブル3550の設定を示す。フィルタリングのフロー条件はSIP＝企業網A321、企業網C323、企業網D324、DIP＝企業網B322であるが、QoS制御のフロー条件は用途(FTP、TELNET、HTTP)であり、FTP/HTTPのパケットが非優先、TELNETのパケットが優先である。同時フロー検出方式の場合、7つのエントリが設定されるが、２段フロー検出方式の場合、6つのエントリが設定されるだけで良い。本例ではフィルタリングおよびQoS制御のフロー条件の組み合わせはそれぞれ3通りであるが、前記組み合わせが多くなるほど、設定するエントリ数の差が大きくなる。
【００９６】
以上述べた様に、QoS制御とフィルタリングのフロー条件が同一の場合には同時フロー検出方式の方が、フロー条件が異なる場合には2段フロー検出方式の方が設定されるエントリ数が少ない。本発明の一方式である切り替えフロー検出方式は２段フロー検出方式と同時フロー検出方式を切り替えて設定エントリを削減する。以下、切り替えフロー検出方式について2段フロー検出方式との違いを中心に説明する。
【００９７】
テーブルフォーマットを図42に、結果判定部4010のブロック図を図43に、フローチャートを図44に示した。図42に示す様に同時フロー検出方式のエントリ3211に比べて、エントリ3911は2段フロー検出方式と同時フロー検出方式を切り替えるフロー検出モード3965が加わる。フロー検出モード3965は同時フロー検出方式または2段フロー検出方式を表す値となる。フロー検出モード3965を蓄積するために、結果判定部4010にフロー検出モード蓄積手段4014が加わる。
【００９８】
切り替えフロー検出方式のエントリ読み出し処理4140のステップ4141では、フロー検出状態蓄積手段3670の値に関わらず、QoS制御情報部530の優先度情報507をQoS制御情報蓄積手段713へ、フィルタリング制御情報部3531の転送可否情報2916をフィルタリング制御情報蓄積手段3016へ、フロー検出モード3965をフロー検出モード蓄積手段4014へ蓄積する。結果判定処理4110では、結果判定回路4011はフロー検出モード蓄積手段4014の値を参照し(ステップ4116)、前記フロー検出モード蓄積手段4014の値が「同時フロー検出方式を表す値」の時には、QoS制御情報蓄積手段713の値を優先度情報と決定し、前記優先度情報から構成されるパケット優先度情報13を送出すると共に、フィルタリング制御情報蓄積手段3016の値を転送可否情報と決定し、前記転送可否情報から構成されるパケット転送可否情報21を出力FIFOバッファ振り分け回路121に出力する(ステップ4117)。その後、フロー検出が終了する(ステップ4115)。フロー検出モード蓄積手段4014の値が「2段フロー検出方式を表す値」の時には、結果判定部4010はフロー検出状態蓄積手段3670の値がフィルタリングあるいはQoS制御のフロー検出かを判定する(ステップ4113)。フロー検出状態蓄積手段3670の値がフィルタリングを表す場合、結果判定回路4011はフィルタリング制御情報蓄積手段3016の値を転送可否情報と決定し、前記転送可否情報から構成されるパケット転送可否情報21を出力FIFOバッファ振り分け回路121に出力する(ステップ4112)。さらに、結果判定部4010は転送可否情報が「廃棄」か「通過」かを参照する(ステップ4114)。フロー検出部は「廃棄」の場合にはQoS制御用のフロー検出を実行せずにフロー検出を終了し(ステップ4115)、「通過」の場合には、QoS制御用のフロー検出を行うため、フロー検出状態蓄積手段3670の値を「QoS制御のフロー検出を表す値」にセットし(ステップ3760)、QoS制御のフロー検出を開始する。フロー検出状態蓄積手段3670の値がQoS制御を表す場合、結果判定回路4011はQoS制御情報蓄積手段713の値を優先度情報と決定し、前記優先度情報から構成されるパケット優先度情報13を出力FIFOバッファ振り分け回路121に出力する(ステップ4111)。その後、フロー検出が終了する(ステップ4115)。
【００９９】
以上に述べた様に、2段フロー検出方式および同時フロー検出方式をエントリ毎に切り替えて実行することができる。そのため、ルータ100の管理者はフロー条件に応じて2段フロー検出方式と同時フロー検出方式を切り替えて設定エントリ数を削減することができる。
【０１００】
次に入力回線限定方式のパイプライン処理について説明する。
【０１０１】
図16(a)は、入力回線限定方式において、４つ処理部であるリスト読みだし部730、エントリ読みだし部740、条件一致判定部720、結果判定部710がそれぞれリスト読みだし処理630、エントリ読みだし処理640、条件一致判定処理620、結果判定処理610を直列（シリアル）に実行する様子を表したものである。図16のパケット１とは、フロー検出部112がパケット１の検出開始処理600を実行していることを表し、エントリNとは、結果判定部710、条件一致判定部720、リスト読みだし部730、エントリ読みだし部740がそれぞれエントリNの結果判定処理610、条件一致判定処理620、リスト読みだし処理630、エントリ読みだし処理640を実行していることを表している。なお、簡単のため 図16では上記各処理の処理時間は同一としている。直列処理ではある処理を実行している場合、他の処理を実行する処理部は動作していない。例えば、条件一致判定処理620を実行している場合にはエントリ読みだし処理640を行うエントリ読みだし部740は動作していない。直列処理の場合、エントリNを処理する時間はリスト読みだし処理630、エントリ読みだし処理640、条件一致判定処理620、結果判定処理610の処理時間の総和となる。
【０１０２】
よりフロー検出を高速化するためには、図16(b)に示すように、リスト読みだし処理630、エントリ読みだし処理640、条件一致判定処理620、結果判定処理610をパイプライン処理し、前記４つの処理部が常に動作するようにすることが望ましい。パイプライン処理では前記4つの処理部のうちの処理部1がエントリNの処理1を終了すると、前記処理1より後の処理２を行う処理部２がエントリNの処理2を終了したか否かに関わらず、前記処理部1がエントリN+1の処理を開始する。この様なパイプライン処理を行うことにより、エントリNの処理時間は1つの処理の時間となり図16の場合、処理速度は4倍となる。前述の例ではフロー検出が４つの処理に分割されパイプライン処理されたが、P個の処理に分割されパイプライン処理されればP倍の性能となる。
【０１０３】
入力回線限定方式のパイプライン処理について述べてきた。他の方式（出力回線限定方式、SAMAC限定方式、DAMAC限定方式、送信元サブネット限定方式、宛先サブネット限定方式）においてもフロー検出部が同様のパイプライン処理を行うことにより高速化を実現できる。
【０１０４】
次に、ルータ100のチップ分割について説明する。ヘッダ処理部110とパケット入出力部120をそれぞれ別の半導体チップに実装する。QoS制御の優先度情報を決定する場合、前記ヘッダ処理部110を実装する半導体チップと前記パケット入出力部120を実装する半導体チップ間の情報は、ヘッダ情報11と、出力回線情報12と、パケット優先度情報13と、DAMAC情報15である。すなわち、ヘッダ処理部110とパケット入出力部120間では情報量の大きいユーザデータを転送されないため、ヘッダ処理部110とパケット入出力部120とを実装する各半導体チップは、前記半導体チップ間の入出力ピンを多数使う必要がない。また、ヘッダ処理部110を実装する半導体チップは複数の回線により共有されているため、回線毎にヘッダ処理を実装する半導体チップを設ける必要がなく半導体チップの個数を削減することができる。なお、ルーティング処理部111、フロー検出部112、及びARP処理部113を全て異なる半導体チップ上に実装しても、ルーティング処理部111、フロー検出部112、及びARP処理部113の共通化による共通化効果を期待できる。
【０１０５】
図19乃至図21は本実施例の効果を説明するグラフである。図19乃至図21の縦軸はフロー検出性能（pps：1秒間に処理できるパケット数）、横軸は設定されるエントリの数である。
【０１０６】
図19は、リニアサーチ方式と入力回線限定方式、出力回線限定方式とを比較したグラフを示す。ルータがN個の入力回線を持ち、全ての入力回線のフロー検出が異なる場合（回線毎につながる企業が異なる場合等）、ルータはそれぞれの入力回線用のエントリを所持しなくてはならない。リニアーサーチ方式ではこれら全てのエントリが検索されるが、入力回線限定方式では入力回線が一致するエントリのみ検索される。そのため、検索するエントリが1/Nとなりフロー検出時間が1/Nとなるため、入力回線限定方式はリニアーサーチ方式に比べてN倍の性能を実現する。同様にルータがN個の出力回線を持ち、全ての出力回線のフロー検出が異なる場合、出力回線限定方式はN倍の性能を実現する。
【０１０７】
図20は、リニアサーチ方式と送信元サブネット限定方式、宛先サブネット限定方式とを比較したグラフを示す。R個の送信元ネットワークが送出するパケットのフロー検出を行う場合を考える。この場合、R個の送信元ネットワークのフロー検出が全て異なると、ルータはそれぞれの送信元サブネット用のエントリを所持しなくてはならない。リニアーサーチ方式ではこれら全てのエントリが検索されるが、送信元サブネット限定方式では前記エントリのうち送信元サブネットが一致するエントリのみ検索される。そのため、送信元サブネット限定方式はリニアーサーチ方式に比べR倍の性能を実現する。同様にR個の宛先ネットワークへのパケットのフロー検出を行い、全ての宛先ネットワークのフロー検出が異なる場合、宛先サブネット限定方式はリニアーサーチ方式に比べR倍の性能を実現する。
【０１０８】
図21は、入力回線限定方式のフロー検出をシリアル処理で行った場合とパイプライン処理で行った場合の性能を比較したグラフを示す。入力回線限定方式の前記実施例では、シリアル処理にくらべパイプライン処理は４倍の性能を実現する。また、フロー検出がP個の処理に分割されパイプライン処理されればP倍の性能となる。
【０１０９】
【発明の効果】
本発明によれば、フロー条件を格納するエントリーテーブルを検索する際に、その検索範囲を限定して検索を行うことができるので、ユーザを識別する情報やプロトコル情報や優先度情報等のフロー条件を大量に設定した場合でも、高速にフローを検出し、高速にQoS制御やフィルタリングを行うことができる。
【０１１０】
また、本発明では、フロー検出部をハードウェア化したことにより、高速にQoS制御やフィルタリングを行うことができる。
【０１１１】
また、本発明では、フロー条件の記述性を大幅に向上させることができる。
【図面の簡単な説明】
【図１】本発明のルータの構成を示すブロック図。
【図２】インターネットの構成図。
【図３】ネットワークにおけるパケットのフォーマットを示す図。
【図４】ルータ内におけるパケットのフォーマットを示す図。
【図５】  IPアドレスのフォーマットを示す図。
【図６】リニアサーチ方式の概念図。
【図７】エントリを入力回線毎に限定する方式を説明する図。
【図８】本発明の入力回線限定方式のリストテーブル860とエントリテーブル750のフォーマット。
【図９】本発明のSAMAC限定方式のリストテーブル860とエントリテーブル750のフォーマット。
【図１０】本発明の送信元サブネット限定方式のリストテーブル1060とエントリテーブル1050のフォーマット。
【図１１】本発明の一方式である入力回線限定方式を適用したフロー検出部112のフローチャート。
【図１２】本発明の入力回線限定方式を適用したフロー検出部112のブロック図。
【図１３】本発明のSAMAC限定方式を適用したフロー検出部812のブロック図。
【図１４】本発明の一方式である送信元サブネット限定方式を適用したフロー検出部1012のフローチャート。
【図１５】本発明の一方式である送信元サブネット限定方式を適用したフロー検出部1012のブロック図。
【図１６】フロー検出部が直列に各処理を処理した場合のタイムチャート、及びフロー検出部が各処理をパイプライン処理した場合のタイムチャートを示す図。
【図１７】エントリテーブルとリストテーブルと条件一致判定部の配置を説明する図。
【図１８】ルータがバス状に接続されたネットワークを示す図。
【図１９】本発明の入力回線限定方式と出力回線限定方式の効果を表す図。
【図２０】本発明の送信元サブネット限定方式と宛先サブネット限定方式の効果を表す図。
【図２１】パイプライン処理の効果を表す図。
【図２２】  入力回線限定方式により優先度情報、帯域監視情報および書換TOS情報を判定する際のエントリテーブル2250のフォーマット。
【図２３】入力回線限定方式により優先度情報、帯域監視情報および書換TOS情報を判定する際の結果判定部2310のブロック図。
【図２４】入力回線限定方式により優先度情報、帯域監視情報および書換TOS情報を判定する際のヘッダ処理部2410のブロック図。
【図２５】入力回線限定方式により優先度情報、帯域監視情報および書換TOS情報を判定する際のフロー検出部2412のフローチャート。
【図２６】入力回線限定方式により優先度情報およびコネクション情報を判定する際のエントリテーブル2650のフォーマット。
【図２７】入力回線限定方式により優先度情報およびコネクション情報を判定する際の結果判定部2710のブロック図。
【図２８】入力回線限定方式により優先度情報およびコネクション情報を判定する際のフロー検出部のフローチャート。
【図２９】入力回線限定方式によりフィルタリングを実行する際のエントリテーブル2950のフォーマット。
【図３０】入力回線限定方式によりフィルタリングを実行する際の結果判定部3010のブロック図。
【図３１】入力回線限定方式によりフィルタリングを実行する際のフローチャート。
【図３２】本発明の一方式である同時フロー検出方式を適用したエントリテーブル3250のフォーマット。
【図３３】本発明の一方式である同時フロー検出方式を適用した結果判定部3310のブロック図。
【図３４】本発明の一方式である同時フロー検出方式を適用した際のフロー検出部のフローチャート。
【図３５】本発明の一方式である2段フロー検出方式を適用したリストテーブル3560とエントリテーブル3550。
【図３６】本発明の一方式である2段フロー検出方式を適用したフロー検出部3612のブロック図。
【図３７】本発明の一方式である２段フロー検出方式を適用した際のフロー検出部3612のフローチャート。
【図３８】同時フロー検出方式を適用したエントリテーブル3250の設定例(フィルタリングとQoS制御のフロー条件が同一の場合)。
【図３９】２段フロー検出方式を適用したエントリテーブル3550の設定例(フィルタリングとQoS制御のフロー条件が同一の場合)。
【図４０】同時フロー検出方式を適用したエントリテーブル3250の設定例(フィルタリングとQoS制御のフロー条件が異なる場合)。
【図４１】２段フロー検出方式を適用したエントリテーブル2950の設定例(フィルタリングとQoS制御のフロー条件が異なる場合)。
【図４２】本発明の一方式である切り替えフロー検出方式を適用したエントリテーブル3950のフォーマット。
【図４３】本発明の一方式である切り替えフロー検出方式を適用した結果判定部4010のブロック図。
【図４４】本発明の一方式である切り替えフロー検出方式を適用した際のフローチャート。
【図４５】用途(アプリケーション)とポート番号の対応を表す図。
【図４６】企業網が公衆ATMネットワークにより接続されたネットワーク。
【符号の説明】
11・・・ヘッダ情報、12・・・出力回線情報、13・・・パケット優先度情報、14・・・NIP情報、15・・・DAMAC情報、16・・・サブネット識別子情報、17・・・パケット帯域監視情報、18・・・帯域監視結果情報、19・・・パケット書換TOS情報、20・・・パケットコネクション情報、21・・・パケット転送可否情報。
【図１】
0003721880.tif 000002
【図２】
0003721880.tif 000003
【図３】
0003721880.tif 000004
【図４】
0003721880.tif 000005
【図５】
0003721880.tif 000006
【図６】
0003721880.tif 000007
【図７】
0003721880.tif 000008
【図８】
0003721880.tif 000009
【図９】
0003721880.tif 000010
【図１０】
0003721880.tif 000011
【図１１】
0003721880.tif 000012
【図１２】
0003721880.tif 000013
【図１３】
0003721880.tif 000014
【図１４】
0003721880.tif 000015
【図１５】
0003721880.tif 000016
【図１６】
0003721880.tif 000017
【図１７】
0003721880.tif 000018
【図１８】
0003721880.tif 000019
【図１９】
0003721880.tif 000020
【図２０】
0003721880.tif 000021
【図２１】
0003721880.tif 000022
【図２２】
0003721880.tif 000023
【図２３】
0003721880.tif 000024
【図２４】
0003721880.tif 000025
【図２５】
0003721880.tif 000026
【図２６】
0003721880.tif 000027
【図２７】
0003721880.tif 000028
【図２８】
0003721880.tif 000029
【図２９】
0003721880.tif 000030
【図３０】
0003721880.tif 000031
【図３１】
0003721880.tif 000032
【図３２】
0003721880.tif 000033
【図３３】
0003721880.tif 000034
【図３４】
0003721880.tif 000035
【図３５】
0003721880.tif 000036
【図３６】
0003721880.tif 000037
【図３７】
0003721880.tif 000038
【図３８】
0003721880.tif 000039
【図３９】
0003721880.tif 000040
【図４０】
0003721880.tif 000041
【図４１】
0003721880.tif 000042
【図４２】
0003721880.tif 000043
【図４３】
0003721880.tif 000044
【図４４】
0003721880.tif 000045
【図４５】
0003721880.tif 000046
【図４６】
0003721880.tif 000047