(57)【要約】      （修正有）【課題】  ＬＭＥを用いながら、流量制御や輻輳制御などのトラヒックエンジニアリングを行うに適するフォワーディングテーブルを提供する。【解決手段】  ＬＭＥによるフォワーディングのうち、特に負荷が重い、もしくは、あらかじめ予想されて設定されている閾値を上回るトラヒックのアドレスに関しては、詳細なテーブルに自動的に展開して、サブネットワーク毎もしくはＩＰ端末毎にトラヒックを計数する。【選択図】図３
2005117215.tif 000002
【特許請求の範囲】
【請求項１】
到着するＩＰ(Internet Protocol)パケットのＩＰアドレスと事前に設定された検索用アドレスとを比較し、その中で最も長くビット列が一致した検索用アドレスの示す出力方路を検索する手段と、
この検索結果に基づき転送されたパケット数を前記検索用アドレス毎にカウントする手段と、
このカウント結果に基づきカウント値が閾値を超えた検索用アドレスについては、当該検索用アドレスと最も長くビット列が一致したＩＰアドレスを有するＩＰパケットが到着したときにそのＩＰアドレスを解析する手段と、
この解析結果に基づき当該ＩＰアドレスを有するＩＰパケットの転送先となる下の階層の１以上のサブネットワークもしくはＩＰ端末のＩＰアドレスを特定する手段と、
この特定結果に基づき当該サブネットワークもしくはＩＰ端末に転送されるＩＰパケットを特定するための検索用下位アドレスを生成する手段と、
当該サブネットワークもしくはＩＰ端末に転送されたパケット数を当該サブネットワークもしくはＩＰ端末の検索用下位アドレス毎にカウントする手段と
を備えたことを特徴とするフォワーディングテーブル。
【請求項２】
前記サブネットワークもしくはＩＰ端末の検索用下位アドレス毎に当該検索用下位アドレス毎の前記カウント結果が記録されたテーブルを自己の下位テーブルとして生成する手段を備えた請求項１記載のフォワーディングテーブル。
【請求項３】
前記下位テーブルとして生成する手段は、
検索用アドレスおよびカウント値を含む第一のエントリのカウント値が閾値を超えたときに、当該検索用アドレスに対応する下の階層の１以上のサブネットワークもしくはＩＰ端末の検索用下位アドレスを含む１以上の第二のエントリを生成し、この第二のエントリを前記第一のエントリとのリンク関係を表示する識別情報を付加して記録する手段を備えた請求項２記載のフォワーディングテーブル。
【請求項４】
前記下位テーブルとして生成する手段は、
検索用アドレスおよびカウント値を含む第一のエントリのカウント値が閾値を超えたときに、当該検索用アドレスに対応する下の階層の１以上のサブネットワークもしくはＩＰ端末の検索用下位アドレスを含む１以上の第二のエントリを生成し、この第二のエントリの前記検索用下位アドレスと前記第一のエントリの前記検索用アドレスとの大小関係に基づき前記第一のエントリの間に前記第二のエントリを挿入してソートする手段を備えた請求項２記載のフォワーディングテーブル。
【請求項５】
情報処理装置にインストールすることにより、その情報処理装置に、
到着するＩＰパケットのＩＰアドレスと事前に設定された検索用アドレスとを比較し、その中で最も長くビット列が一致した検索用アドレスの示す出力方路を検索する機能と、
この検索結果に基づき転送されたパケット数を前記検索用アドレス毎にカウントする機能と、
このカウント結果に基づきカウント値が閾値を超えた検索用アドレスについては、当該検索用アドレスと最も長くビット列が一致したＩＰアドレスを有するＩＰパケットが到着したときにそのＩＰアドレスを解析する機能と、
この解析結果に基づき当該ＩＰアドレスを有するＩＰパケットの転送先となる下の階層の１以上のサブネットワークもしくはＩＰ端末のＩＰアドレスを特定する機能と、
この特定結果に基づき当該サブネットワークもしくはＩＰ端末に転送されるＩＰパケットを特定するための検索用下位アドレスを生成する機能と、
当該サブネットワークもしくはＩＰ端末に転送されたパケット数を当該サブネットワークもしくはＩＰ端末の検索用下位アドレス毎にカウントする機能と
を備えたフォワーディングテーブルに相応する機能を実現させることを特徴とするプログラム。
【請求項６】
前記サブネットワークもしくはＩＰ端末の検索用下位アドレス毎に当該検索用下位アドレス毎の前記カウント結果が記録されたテーブルを自己の下位テーブルとして生成する機能を実現させる請求項５記載のプログラム。
【請求項７】
前記下位テーブルとして生成する機能として、
検索用アドレスおよびカウント値を含む第一のエントリのカウント値が閾値を超えたときに、当該検索用アドレスに対応する下の階層の１以上のサブネットワークもしくはＩＰ端末の検索用下位アドレスを含む１以上の第二のエントリを生成し、この第二のエントリを前記第一のエントリとのリンク関係を表示する識別情報を付加して記録する機能を実現させる請求項５記載のプログラム。
【請求項８】
前記下位テーブルとして生成する機能として、
検索用アドレスおよびカウント値を含む第一のエントリのカウント値が閾値を超えたときに、当該検索用アドレスに対応する下の階層の１以上のサブネットワークもしくはＩＰ端末の検索用下位アドレスを含む１以上の第二のエントリを生成し、この第二のエントリの前記検索用下位アドレスと前記第一のエントリの前記検索用アドレスとの大小関係に基づき前記第一のエントリの間に前記第二のエントリを挿入してソートする機能を実現させる請求項５記載のプログラム。
【請求項９】
請求項５ないし８のいずれかに記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰ(Internet Protocol)ネットワークに利用する。パケットの流量制御または輻輳制御などのトラヒックエンジニアリング技術に関する。
【背景技術】
【０００２】
従来のパケットフォワーディング回路を図７および図８に示す。図７は従来のパケットフォワーディング回路の構成図である。図８は従来のフォワーディングテーブルの検索方法を説明するための図である。従来のパケットフォワーディング回路は、パケット処理部１により抽出された到着するＩＰパケットのＩＰアドレスと事前に設定されたフォワーディングテーブル１２の検索用アドレスとを比較し、その中で最も長くビット列が一致した検索用アドレスの示す出力方路を検索し、到着したＩＰパケットを検索した出力方路に向けて転送する。このような検索を行う回路をＬＭＥ(Longest Matching Engine)という。
【０００３】
例えば、１２８．１４．２５．０８というＩＰアドレスは、図８の表では、１２８．１５．２５．ｘｘおよび１２８．１５．ｘｘ．ｘｘに一致するが、１２８．１５．２５．ｘｘの方が長いビットに一致しているので、Ｙ3へフォワーディングされる（例えば、特許文献１または２参照）。なお、図中ｘは検索対象外となるビットを表す。
【特許文献１】特開２０００−３５８０６４号公報
【特許文献２】特開２０００−３３２７８６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ＬＭＥを用いると、テーブルが小さく効率よくフォワーディングできる一方、具体的には、どこの端末もしくはサブネットワークへ、どの程度の量のトラヒックを送っているか把握することが困難であるため、流量制御や輻輳制御などのトラヒックエンジニアリングを行うことは困難であった。一方、完全一致テーブルをすべて事前に持つ手段もあるが、現在、通常の中継ルータには１００万を超えるユーザ（エントリ）が存在して、また、全ユーザのＩＰアドレスのテーブルを持つと考えると、２32ビットのアドレス空間を全て持つことになり、高価となってしまう。
【０００５】
本発明は、このような背景に行われたものであって、ＬＭＥを用いながら、流量制御や輻輳制御などのトラヒックエンジニアリングを行うに適するフォワーディングテーブルを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、ＬＭＥによるフォワーディングのうち、特に負荷が重い、もしくは、あらかじめ予想されて設定されている閾値を上回るトラヒックのアドレスに関しては、詳細なテーブルに自動的に展開して、サブネットワーク毎もしくはＩＰ端末毎にトラヒックを計数することを特徴とする。
【０００７】
本発明はフォワーディングテーブルであって、本発明の特徴とするところは、到着するＩＰパケットのＩＰアドレスと事前に設定された検索用アドレスとを比較し、その中で最も長くビット列が一致した検索用アドレスの示す出力方路を検索する手段と、この検索結果に基づき転送されたパケット数を前記検索用アドレス毎にカウントする手段と、このカウント結果に基づきカウント値が閾値を超えた検索用アドレスについては、当該検索用アドレスと最も長くビット列が一致したＩＰアドレスを有するＩＰパケットが到着したときにそのＩＰアドレスを解析する手段と、この解析結果に基づき当該ＩＰアドレスを有するＩＰパケットの転送先となる下の階層の１以上のサブネットワークもしくはＩＰ端末のＩＰアドレスを特定する手段と、この特定結果に基づき当該サブネットワークもしくはＩＰ端末に転送されるＩＰパケットを特定するための検索用下位アドレスを生成する手段と、当該サブネットワークもしくはＩＰ端末に転送されたパケット数を当該サブネットワークもしくはＩＰ端末の検索用下位アドレス毎にカウントする手段とを備えたところにある（請求項１）。
【０００８】
また、前記サブネットワークもしくはＩＰ端末の検索用下位アドレス毎に当該検索用下位アドレス毎の前記カウント結果が記録されたテーブルを自己の下位テーブルとして生成する手段を備えることができる（請求項２）。
【０００９】
これにより、フォワーディングされるパケットのうち、特に負荷が重い、もしくは、あらかじめ予想されて設定されている閾値を上回るトラヒックのアドレスに関しては、詳細なテーブルに自動的に展開して、サブネットワーク毎もしくはＩＰ端末毎にトラヒックを計算することができる。したがって、ＬＭＥを用いながら、流量制御や輻輳制御などのトラヒックエンジニアリングを行うことができる。
【００１０】
また、前記下位テーブルとして生成する手段は、検索用アドレスおよびカウント値を含む第一のエントリのカウント値が閾値を超えたときに、当該検索用アドレスに対応する下の階層の１以上のサブネットワークもしくはＩＰ端末の検索用下位アドレスを含む１以上の第二のエントリを生成し、この第二のエントリを前記第一のエントリとのリンク関係を表示する識別情報を付加して記録する手段を備えることができる（請求項３）。
【００１１】
これによれば、元からのフォワーディングテーブルはそのままにしておき、任意の場所に下位テーブルを実現することができる。例えば、元からのフォワーディングテーブルと同じメモリ上に下位テーブルを実現してもよいし、あるいは、元からのフォワーディングテーブルとは別のメモリ上に下位テーブルを実現してもよい。これにより、テーブル設計の自由度を向上させることができる。また、下位テーブルを元からのフォワーディングテーブルと分離してあるので、下位テーブルを定期的にリセットするなどの管理が簡単に行える利点がある。
【００１２】
あるいは、前記下位テーブルとして生成する手段は、検索用アドレスおよびカウント値を含む第一のエントリのカウント値が閾値を超えたときに、当該検索用アドレスに対応する下の階層の１以上のサブネットワークもしくはＩＰ端末の検索用下位アドレスを含む１以上の第二のエントリを生成し、この第二のエントリの前記検索用下位アドレスと前記第一のエントリの前記検索用アドレスとの大小関係に基づき前記第一のエントリの間に前記第二のエントリを挿入してソートする手段を備えることがきでる（請求項４）。
【００１３】
これによれば、元からのフォワーディングテーブルと同じ場所に下位テーブルを実現することができる。例えば、元からのフォワーディングテーブルと同じメモリ上に下位テーブルを実現することができるため、メモリを有効利用することができる。
【００１４】
本発明の他の観点はプログラムであって、本発明の特徴とするところは、情報処理装置にインストールすることにより、その情報処理装置に、到着するＩＰパケットのＩＰアドレスと事前に設定された検索用アドレスとを比較し、その中で最も長くビット列が一致した検索用アドレスの示す出力方路を検索する機能と、この検索結果に基づき転送されたパケット数を前記検索用アドレス毎にカウントする機能と、このカウント結果に基づきカウント値が閾値を超えた検索用アドレスについては、当該検索用アドレスと最も長くビット列が一致したＩＰアドレスを有するＩＰパケットが到着したときにそのＩＰアドレスを解析する機能と、この解析結果に基づき当該ＩＰアドレスを有するＩＰパケットの転送先となる下の階層の１以上のサブネットワークもしくはＩＰ端末のＩＰアドレスを特定する機能と、この特定結果に基づき当該サブネットワークもしくはＩＰ端末に転送されるＩＰパケットを特定するための検索用下位アドレスを生成する機能と、当該サブネットワークもしくはＩＰ端末に転送されたパケット数を当該サブネットワークもしくはＩＰ端末の検索用下位アドレス毎にカウントする機能とを備えたフォワーディングテーブルに相応する機能を実現させるところにある（請求項５）。
【００１５】
また、前記サブネットワークもしくはＩＰ端末の検索用下位アドレス毎に当該検索用下位アドレス毎の前記カウント結果が記録されたテーブルを自己の下位テーブルとして生成する機能を実現させることができる（請求項６）。
【００１６】
また、前記下位テーブルとして生成する機能として、検索用アドレスおよびカウント値を含む第一のエントリのカウント値が閾値を超えたときに、当該検索用アドレスに対応する下の階層の１以上のサブネットワークもしくはＩＰ端末の検索用下位アドレスを含む１以上の第二のエントリを生成し、この第二のエントリを前記第一のエントリとのリンク関係を表示する識別情報を付加して記録する機能を実現させる（請求項７）。
【００１７】
また、前記下位テーブルとして生成する機能として、検索用アドレスおよびカウント値を含む第一のエントリのカウント値が閾値を超えたときに、当該検索用アドレスに対応する下の階層の１以上のサブネットワークもしくはＩＰ端末の検索用下位アドレスを含む１以上の第二のエントリを生成し、この第二のエントリの前記検索用下位アドレスと前記第一のエントリの前記検索用アドレスとの大小関係に基づき前記第一のエントリの間に前記第二のエントリを挿入してソートする機能を実現させることができる（請求項８）。
【００１８】
本発明の他の観点は、本発明のプログラムが記録された前記情報処理装置読み取り可能な記録媒体である（請求項９）。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００１９】
これにより、汎用の情報処理装置を用いて、ＬＭＥを用いながら、流量制御や輻輳制御などのトラヒックエンジニアリングを行うに適するフォワーディングテーブルを実現することができる。
【発明の効果】
【００２０】
本発明によれば、ＬＭＥを用いながら、流量制御や輻輳制御などのトラヒックエンジニアリングを行うに適するフォワーディングテーブルを提供することができる。
【発明を実施するための最良の形態】
【００２１】
本発明実施例のフォワーディングテーブルを図１ないし図６を参照して説明する。
【００２２】
（第一実施例）
本発明第一実施例のフォワーディングテーブルを図１を参照して説明する。図１は第一実施例のフォワーディング回路の構成図である。
【００２３】
第一実施例はフォワーディングテーブル２であって、第一実施例の特徴とするところは、パケット処理部１によって抽出された到着するＩＰパケットのＩＰアドレスと事前に設定された検索用アドレスとを比較し、その中で最も長くビット列が一致した検索用アドレスの示す出力方路を検索する手段と、この検索結果に基づき転送されたパケット数を前記検索用アドレス毎にカウントする手段と、このカウント結果に基づきカウント値が閾値を超えた検索用アドレスについては、当該検索用アドレスと最も長くビット列が一致したＩＰアドレスを有するＩＰパケットが到着したときにそのＩＰアドレスを解析する手段と、この解析結果に基づき当該ＩＰアドレスを有するＩＰパケットの転送先となる下の階層の１以上のサブネットワークもしくはＩＰ端末のＩＰアドレスを特定する手段と、この特定結果に基づき当該サブネットワークもしくはＩＰ端末に転送されるＩＰパケットを特定するための検索用下位アドレスを生成する手段と、当該サブネットワークもしくはＩＰ端末に転送されたパケット数を当該サブネットワークもしくはＩＰ端末の検索用下位アドレス毎にカウントする手段とを詳細展開部３に備えたところにある（請求項１）。
【００２４】
パケット処理部１は、ＩＰパケットのＩＰアドレスをフォワーディングテーブル２へ転送し、出力方路を検索してＩＰパケットをフォワーディングする。このときに、フォワーディングテーブル２では、トラヒックの大きい検索用アドレス（以降、ＬＭＥ用アドレスという）は、より詳細なサブネットワークレベルでのトラヒックを計数する。
【００２５】
第一実施例のフォワーディングテーブル２の動作を図２および図３を参照して説明する。図２は第一実施例のフォワーディングテーブルの動作を説明するための図である。図２のテーブルでは、１２８．ｘｘ．ｘｘ．ｘｘのアドレスに規定値Ｙ1を超えるパケットがヒットしているので、１２８より１つ階層の下のサブネットワークもしくはＩＰ端末のＬＭＥ用アドレス、
１２８．３６．ｘｘ．ｘｘ
１２８．１６．ｘｘ．ｘｘ
１２８．８．ｘｘ．ｘｘ
それぞれのカウント値を計数する。このときＬＭＥ用アドレスがテーブルにある場合は単純にカウントアップし、テーブルにない場合はＬＭＥ用アドレスを生成する。
【００２６】
第一実施例のテーブル作成動作のフローチャートを図３に示した。図３に示すフローチャートによれば、ＩＰパケットが到着すると、フォワーディングテーブル２内のＬＭＥ用アドレスによる検索を行い、ＬＭＥ用アドレス毎にパケット数のカウントを行う。カウント結果が閾値Ｙ1を超えていれば、一段下のサブネットワークまたはＩＰ端末に対応する下位テーブルのＬＭＥ用アドレスによる検索を行い、その下位テーブルにＬＭＥ用アドレスがなければ該当するＬＭＥ用アドレスを生成し、ＬＭＥ用アドレス毎にパケット数をカウントする。このカウント数が閾値Ｙi（ｉは自然数）を超えていれば、さらに一段下のサブネットワークまたはＩＰ端末に対応する下位テーブルのＬＭＥ用アドレスによる検索を行う。このことにより、現在流れているトラヒックの多いサブネットワークもしくはＩＰ端末を発見することが可能である。
【００２７】
（第二実施例）
第二実施例を図４を参照して説明する。図４は第二実施例のフォワーディングテーブルの構成図である。
【００２８】
第二実施例のフォワーディングテーブル２は、サブネットワークもしくはＩＰ端末の検索用下位アドレス毎に当該検索用下位アドレス毎の前記カウント結果が記録された詳細ＬＭＥテーブル５をＬＭＥテーブル４の下位テーブルとして生成する詳細展開部３を備える（請求項２）。
【００２９】
このように、第二実施例では、通常のＬＭＥテーブル４にヒットさせ、カウント値が大きい場合には、詳細展開部３がコントロールして、詳細ＬＭＥテーブル５を作成する。この方式は、一定時間毎に階層化した詳細ＬＭＥテーブル５のリセットや管理が容易であり、また、従来のＬＭＥテーブル４がほとんどそのまま応用できる特徴がある。
【００３０】
（第三実施例）
第三実施例を図５を参照して説明する。図５は、第三実施例のフォワーディングテーブルの構成を示す図である。第三実施例は、展開した下の階層のテーブルをどのように持つかというものである。すなわち、詳細展開部３は、検索用アドレスおよびカウント値を含む第一のエントリのカウント値が閾値を超えたときに、当該検索用アドレスに対応する下の階層の１以上のサブネットワークもしくはＩＰ端末の検索用下位アドレスを含む１以上の第二のエントリを生成し、この第二のエントリを前記第一のエントリとのリンク関係を表示する識別情報を付加して記録する手段を備える（請求項３）。
【００３１】
すなわち、あるアドレスをヒットさせ、そのカウンタ値が一定値を超えると、リンク先アドレスを設定し、１つ下の階層テーブルを図５のように生成する。その場合は、詳細化されたテーブルをカウントアップする。リンク先が“−”となっているアドレスは、カウンタ値が閾値に達していない。その場合は、カウントアップするのみで処理を終了する。
【００３２】
（第四実施例）
第四実施例を図６を参照して説明する。図６は第四実施例のフォワーディングテーブルの構成図である。第四実施例では、詳細展開部３は、自フォワーディングテーブル２上の検索用アドレスおよびカウント値を含む第一のエントリのカウント値が閾値を超えたときに、当該検索用アドレスに対応する下の階層の１以上のサブネットワークもしくはＩＰ端末の検索用下位アドレスを含む１以上の第二のエントリを生成し、この第二のエントリの前記検索用下位アドレスと前記第一のエントリの前記検索用アドレスとの大小関係に基づき前記第一のエントリの間に前記第二のエントリを挿入してソートする手段を備える（請求項４）。
【００３３】
第四実施例は、第三実施例と同様に、ある一定値を超えたアドレスは、その下に１つ下の階層のアドレスを展開する。その際、同一のテーブルにインタリーブしてソートしている。例では、１２８．ｘｘ．ｘｘ．ｘｘは、詳細展開中となったので、その下のサブネットワーク階層が存在することがわかる。
【００３４】
（第五実施例）
本発明は、汎用の情報処理装置にインストールすることにより、その情報処理装置に本発明のフォワーディングテーブルに相応する機能を実現させるプログラムとして実現することができる（請求項５〜８）。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ（請求項９）、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、詳細展開部３、ＬＭＥテーブル４、詳細ＬＭＥテーブル５にそれぞれ相応する機能を実現させることができる。
【産業上の利用可能性】
【００３５】
本発明によれば、ＬＭＥを用いながら、流量制御や輻輳制御などのトラヒックエンジニアリングを行うことができる。これにより、ダイナミックなＭＰＬＳや光パスのトリガーとして、このテーブルを使うことができる。
【図面の簡単な説明】
【００３６】
【図１】第一実施例のパケットフォワーディング回路の構成図。
【図２】第一実施例のフォワーディングテーブルの詳細展開を示す図。
【図３】第一実施例のフォワーディングテーブルの動作を示すフローチャート。
【図４】第二実施例のフォワーディングテーブルの構成図。
【図５】第三実施例のフォワーディングテーブルの詳細展開を示す図。
【図６】第四実施例のフォワーディングテーブルの詳細展開を示す図。
【図７】従来のパケットフォワーディング回路の構成図。
【図８】従来のフォワーディングテーブルの検索方法を説明するための図。
【符号の説明】
【００３７】
１  パケット処理部
２、１２  フォワーディングテーブル
３  詳細展開部
４  ＬＭＥテーブル
５  詳細ＬＭＥテーブル
【図１】
2005117215.tif 000003
【図２】
2005117215.tif 000004
【図３】
2005117215.tif 000005
【図４】
2005117215.tif 000006
【図５】
2005117215.tif 000007
【図６】
2005117215.tif 000008
【図７】
2005117215.tif 000009
【図８】
2005117215.tif 000010