(57)【要約】【課題】  パケットに記述された目的アドレスを用いたルーティング処理を行わずにルータにおいてパケットの転送を確定的に行う。【解決手段】  本発明は、任意のノード間の最短ホップ距離を算出し、トポロジ情報及び各発着ノード間の最短ホップ長に関する情報から、最大ホップ長以内の全ノードの組合せに対して各隣接ノードに対するパケット転送が可能か否かの実施判定を行い、判定結果を得る。各隣接ノードに対して同一ノードを経由しないで到達可能な最大ホップ長を算出する。パケットが当該ノード装置に到着する毎に、判定情報と最大到達ホップ長を用いて、各隣接ノードｊに対してパケットの転送を行うか否かの判定を行うと共に、自ノード装置が発ノードである場合は、目的ノードに至る最短ホップ長を許容ホップ上限値としてパケットのヘッダに記入し、各出力ポートにパケットを送出する。【選択図】  図１
2013098645.tif 000002
【特許請求の範囲】
【請求項１】
複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（ＮＷ）におけるパケット転送システムであって、
任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、
経由ノードは、
前記着ノードのアドレスを用いずに、所定の論理に基づいて転送すべき次ノードのリンクを確定してパケットの転送を行う確定的転送手段を有する
ことを特徴とするパケット転送システム。
【請求項２】
前記確定的転送手段は、
隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで得られた該NW全体の接続構造（以下、「トポロジ」と記す）及び、トポロジ情報から任意のノード間の最短ホップ距離を自律的に算出し、トポロジ情報記憶手段に格納する隣接ノード情報交換手段と、
パケットを転送するパケット転送手段と、
を有し、
前記パケット転送手段は、
自身を発ノードとし、任意のノードを着ノードとするパケットに対して、自身と該着ノードの組に対して前記最短ホップ距離を許容残余ホップ長とし、該着ノードのＩＤをパケットのヘッダに挿入して送出する手段と、
任意の入力ポートからパケットが到着した際は、ヘッダに記入された着ノードＩＤが自身のノードのIDと合致するかを確認する確認手段と、
前記確認手段で合致すると判定された場合は、到着した当該パケットの転送は行わず、合致しない場合は、前記残余許容ホップ長を１だけ減少させ、該残余許容ホップ長が２以上の場合は、パケットが転送されてきた隣接ノードを除く他の出力ポートに転送する手段と、を含む
請求項１記載のパケット転送システム。
【請求項３】
任意のノードnは、
パケットを生成し、該ノードnのIDを直近の経由ノード情報としてパケットのヘッダ内に記述し、任意の目的ノードdに対してパケットを送出する手段を有し、
前記経由ノードの前記パケット転送手段は、
当該経由ノードのIDを直近の経由ノードとしてパケットのヘッダ内に追記する処理を反復し、記述された経由ノード数が所定の数（ｐ）となった場合には、最も古い経由ノードのIDを削除してから追記する手段を含む
請求項２記載のパケット転送システム。
【請求項４】
前記確定的転送手段は、
前記トポロジ情報記憶手段から前記トポロジ情報及び前記最短ホップ長を取得し、自身のノードからｇホップで到達可能な各ノードmに対して、該ノードmからノードnの隣接ノードjへの最短ホップ長hmjが、該ノードnからノードjに転送した場合のホップ長g＋1よりも小さい場合、該ノードnから該ノードjへのパケット転送は行わないものと設定し、自身のノードから最大pホップ以内で到達可能な全ての経由ノードの組合せに対して、該ノードnから該ノードjへのパケット転送を行うか否かの設定を前記転送判定情報記憶手段のエントリに格納する転送判定算出手段を有し、
前記パケット転送手段は、
前記ノードnにパケットが到着した際には、該パケットのヘッダに記述されている最大p個の直近経由ノードIDの組合せに対応する前記転送判定情報記憶手段上のエントリを調べ、その設定がパケットの転送を行う場合にのみ、到着した該パケットを各出力ポートｊに転送する手段を含む
請求項２記載のパケット転送システム。
【請求項５】
前記確定的転送手段は、
前記ノードnから隣接ノードjへのリンク（n,j）に対して、該ノードjに該ノードnからパケットを転送後に同一のノードを複数回経由しないで到達することが可能な最大ホップ長αnjを算出し、最大到達ホップ長記憶手段に格納する最大到達ホップ長算出手段と、
前記ノードnにパケットが到着した際には、該パケットのヘッダに記述された残余許容ホップ長hと各隣接ノードjに対する前記最大到達ホップ長記憶手段の前記最大ホップ長αnjを比較し、h＞αnjの場合には、該隣接ノードjへのパケット転送は行わず、そうでない場合のみ転送を行う手段を含む
請求項１記載のパケット転送システム。
【請求項６】
複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（ＮＷ）におけるパケット転送方法であって、
任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、
隣接ノード情報交換手段が、隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで得られた該NW全体の接続構造（以下、「トポロジ」と記す）及び、トポロジ情報から任意のノード間の最短ホップ距離を自律的に算出し、トポロジ情報記憶手段に格納する隣接ノード情報交換ステップと、
転送判定算出手段が、前記トポロジ情報記憶手段から前記トポロジ情報及び各発着ノード間の最短ホップ長に関する情報を取得して、最大ホップ長以内の全ノードの組合せに対して各隣接ノードに対するパケット転送が可能か否かの実施判定を行い、判定結果を転送判定記憶手段に格納する転送判定算出ステップと、
最大到達ホップ長算出手段が、前記トポロジ情報記憶手段の前記トポロジ情報に基づいて、各隣接ノードに対して同一ノードを経由しないで到達可能な最大ホップ長を算出し、最大到達ホップ長記憶手段に格納する最大到達ホップ長算出ステップと、
パケット転送手段が、パケットが当該ノード装置に到着する毎に、前記転送判定記憶手段の判定情報と前記最大到達ホップ長記憶手段の前記最大到達ホップ長を用いて、各隣接ノードｊに対してパケットの転送を行うか否かの判定を行と共に、自ノード装置が発ノードである場合は、目的ノードに至る最短ホップ長を許容ホップ上限値としてパケットのヘッダに記入し、各出力ポートにパケットを送出するパケット転送ステップと、
を行うことを特徴とするパケット転送方法。
【請求項７】
前記転送判定算出ステップにおいて、
前記トポロジ情報記憶手段から前記トポロジ情報及び前記最短ホップ長を取得し、自身のノードからｇホップで到達可能な各ノードmに対して、該ノードmからノードnの隣接ノードjへの最短ホップ長hmjが、該ノードnからノードjに転送した場合のホップ長g＋1よりも小さい場合、該ノードnから該ノードjへのパケット転送は行わないものと設定し、自身のノードから最大pホップ以内で到達可能な全ての経由ノードの組合せに対して、該ノードnから該ノードjへのパケット転送を行うか否かの設定を前記転送判定情報記憶手段のエントリに格納し、
前記パケット転送ステップにおいて、
前記ノードnにパケットが到着した際には、該パケットのヘッダに記述されている最大p個の直近経由ノードIDの組合せに対応する前記転送判定情報記憶手段上のエントリを調べ、その設定がパケットの転送を行う場合にのみ、到着した該パケットを各出力ポートｊに転送する
請求項６記載のパケット転送方法。
【請求項８】
複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（ＮＷ）におけるパケット転送システムのノード装置であって、
隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで得られた該NW全体の接続構造（以下、「トポロジ」と記す）及び、トポロジ情報から任意のノード間の最短ホップ距離を自律的に算出し、トポロジ情報記憶手段に格納する隣接ノード情報交換手段と、
前記トポロジ情報記憶手段から前記トポロジ情報及び各発着ノード間の最短ホップ長に関する情報取得して、最大ホップ長以内の全ノードの組合せに対して各隣接ノードに対するパケット転送が可能か否かの実施判定を行い、判定結果を転送判定記憶手段に格納する転送判定算出手段と、
前記トポロジ情報記憶手段の前記トポロジ情報に基づいて、各隣接ノードに対して同一ノードを経由しないで到達可能な最大ホップ長を算出し、最大到達ホップ長記憶手段に格納する最大到達ホップ長算出手段と、
パケットが当該ノード装置に到着する毎に、前記転送判定記憶手段の判定情報と前記最大到達ホップ長記憶手段の前記最大到達ホップ長を用いて、各隣接ノードｊに対してパケットの転送を行うか否かの判定を行と共に、自ノード装置が発ノードである場合は、目的ノードに至る最短ホップ長を許容ホップ上限値としてパケットのヘッダに記入し、各出力ポートにパケットを送出するパケット転送手段と、
を有することを特徴とするノード装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット転送システム及び方法及びノード装置に係り、特に、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（NW）において、任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、経由ノードにおいて着ノードのアドレスを用いないでパケットの転送を確定的に行うためのパケット転送システム及び方法及びノード装置に関する。
【背景技術】
【０００２】
現在のインターネットは、ISP（Internet Services Protocol）等の運用するＮＷを複数、相互に接続した形態となっている。各ISPのＮＷは単一もしくは複数の自律したＮＷ（AS）から構成されており、各AS内はOSPF(Open Shortest Path First)を、AS間はBGP(Border Gateway Protocol)を用いることで、任意の発端末から任意の着端末に対するパケットの転送が実現される。
【０００３】
OSPFでは、ルータは隣接ノード間と接続リンクのコスト情報を交換することで、NW全体のリンクコスト情報を含むトポロジ構造を把握し、ダイクストラのアルゴリズムを用いることで、各発着ノード間の最小コスト経路を算出する。そして、各ノードは、各パケットが最小コスト経路上を転送されるよう、各着アドレスを有するパケットが到着した際に、次に転送すべき出力ポートを事前に算出し、ルーティングテーブルとして管理する。このようなルーティングテーブルの作成・更新は、各ノードにおいて自律的に実施される。
【０００４】
パケットがルータに到着すると、ルータはパケットの目的アドレスをキーとして、ルーティングテーブルを検索し、該当する項目に記述されている、次に転送すべきルータに関する情報を得て、そのルータに接続されている出力ポートに対して到着パケットを転送する。ルーティングテーブルには最終到達ルータのアドレスが記されている場合もあれば、複数のルータのアドレスを含有する形でのアドレスの一部のみが記されている場合もある。ルータは、パケットに記述された目的アドレスに対して、最も合致するエリアが大きいルーティングテーブル上のエントリを検索する必要がある（例えば、非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】"BUFFALO: Bloom Filter Forwarding Architecture for Large Organizations," ACM CoNEXT 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記のルータが到着パケットの目的アドレスに最も多く合致するルーティングテーブル内のエントリを探し出す方法として広く用いられている方法は、目的アドレスをキーにして得られるハッシュ値を用いる方法であるが、ハッシュ値が衝突した際には別途、他のアドレスを用意する等の方策を用いる必要がある。
【０００７】
また、Bloom filterを用いて、アドレスルックアップに要する処理負荷を低減する検討も行われている。しかし、これらの方法は全て、目的アドレスに基づきパケットを転送すべき出力ポートを決めているため、NW規模（目的アドレス数）や、NWを流れるトラヒック量の増加に伴い、パケットのルーティング処理に要する負荷が増加する問題がある。
【０００８】
本発明は、上記の点に鑑みなされたもので、パケットに記述された目的アドレスを用いたルーティング処理を行わずにルータにおいてパケットの転送を確定的に行うことが可能なパケット転送システム及び方法及びノード装置を提供することを目的とする。
【０００９】
詳しくは、目的ノードを用いたルーティングを行わない場合、経由ノードにおいて、多数の出力リンクに同一のパケットが転送されるため、リンク負荷が大きくなる。そこで可能な限り無駄なパケット転送を回避することで、リンク負荷の増加を抑える。
【課題を解決するための手段】
【００１０】
上記の課題を解決するため、本発明（請求項１）は、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（ＮＷ）におけるパケット転送システムであって、
任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、
経由ノードは、
前記着ノードのアドレスを用いずに、所定の論理に基づいて転送すべき次ノードのリンクを確定してパケットの転送を行う確定的転送手段を有する。
【００１１】
また、本発明（請求項２）は、前記確定的転送手段において、
隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで得られた該NW全体の接続構造（以下、「トポロジ」と記す）及び、トポロジ情報から任意のノード間の最短ホップ距離を自律的に算出し、トポロジ情報記憶手段に格納する隣接ノード情報交換手段と、
パケットを転送するパケット転送処理手段と、
を有し、
前記パケット転送処理手段は、
自身を発ノードとし、任意のノードを着ノードとするパケットに対して、自身と該着ノードの組に対して前記最短ホップ距離を許容残余ホップ長とし、該着ノードのＩＤをパケットのヘッダに挿入して送出する手段と、
任意の入力ポートからパケットが到着した際は、ヘッダに記入された着ノードＩＤが自身のノードのIDと合致するかを確認する確認手段と、
前記確認手段で合致すると判定された場合は、到着した当該パケットの転送は行わず、合致しない場合は、前記残余許容ホップ長を１だけ減少させ、該残余許容ホップ長が２以上の場合は、パケットが転送されてきた隣接ノードを除く他の出力ポートに転送する手段と、含む。
【００１２】
また、本発明（請求項３）は、任意のノードnにおいて、
パケットを生成し、該ノードnのIDを直近の経由ノード情報としてパケットのヘッダ内に記述し、任意の目的ノードdに対してパケットを送出する手段を有し、
前記経由ノードの前記パケット転送手段において、
当該経由ノードのIDを直近の経由ノードとしてパケットのヘッダ内に追記する処理を反復し、記述された経由ノード数が所定の数（ｐ）となった場合には、最も古い経由ノードのIDを削除してから追記する手段を含む。
【００１３】
また、本発明（請求項４）は、前記確定的転送手段において、
前記トポロジ情報記憶手段から前記トポロジ情報及び前記最短ホップ長を取得し、自身のノードからｇホップで到達可能な各ノードmに対して、該ノードmからノードnの隣接ノードjへの最短ホップ長hmjが、該ノードnからノードjに転送した場合のホップ長g＋1よりも小さい場合、該ノードnから該ノードjへのパケット転送は行わないものと設定し、自身のノードから最大pホップ以内で到達可能な全ての経由ノードの組合せに対して、該ノードnから該ノードjへのパケット転送を行うか否かの設定を前記転送判定情報記憶手段のエントリに格納する転送判定算出手段を有し、
前記パケット転送手段は、
前記ノードnにパケットが到着した際には、該パケットのヘッダに記述されている最大p個の直近経由ノードIDの組合せに対応する前記転送判定情報記憶手段上のエントリを調べ、その設定がパケットの転送を行う場合にのみ、到着した該パケットを各出力ポートｊに転送する手段を含む。
【００１４】
また、本発明（請求項５）は、前記確定的転送手段において、
前記ノードnから隣接ノードjへのリンク（n,j）に対して、該ノードjに該ノードnからパケットを転送後に同一のノードを複数回経由しないで到達することが可能な最大ホップ長αnjを算出し、最大到達ホップ長記憶手段に格納する最大到達ホップ長算出手段と、
前記ノードnにパケットが到着した際には、該パケットのヘッダに記述された残余許容ホップ長hと各隣接ノードjに対する前記最大到達ホップ長記憶手段の前記最大ホップ長αnjを比較し、h＞αnjの場合には、該隣接ノードjへのパケット転送は行わず、そうでない場合のみ転送を行う手段を含む。
【００１５】
本発明（請求項６）は、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（ＮＷ）におけるパケット転送方法であって、
任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、
隣接ノード情報交換手段が、隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで得られた該NW全体の接続構造（以下、「トポロジ」と記す）及び、トポロジ情報から任意のノード間の最短ホップ距離を自律的に算出し、トポロジ情報記憶手段に格納する隣接ノード情報交換ステップと、
転送判定算出手段が、前記トポロジ情報記憶手段から前記トポロジ情報及び各発着ノード間の最短ホップ長に関する情報を取得して、最大ホップ長以内の全ノードの組合せに対して各隣接ノードに対するパケット転送が可能か否かの実施判定を行い、判定結果を転送判定記憶手段に格納する転送判定算出ステップと、
最大到達ホップ長算出手段が、前記トポロジ情報記憶手段の前記トポロジ情報に基づいて、各隣接ノードに対して同一ノードを経由しないで到達可能な最大ホップ長を算出し、最大到達ホップ長記憶手段に格納する最大到達ホップ長算出ステップと、
パケット転送手段が、パケットが当該ノード装置に到着する毎に、前記転送判定記憶手段の判定情報と前記最大到達ホップ長記憶手段の前記最大到達ホップ長を用いて、各隣接ノードｊに対してパケットの転送を行うか否かの判定を行と共に、自ノード装置が発ノードである場合は、目的ノードに至る最短ホップ長を許容ホップ上限値としてパケットのヘッダに記入し、各出力ポートにパケットを送出するパケット転送ステップと、を行う。
【００１６】
また、本発明（請求項７）は、前記転送判定算出ステップにおいて、
前記トポロジ情報記憶手段から前記トポロジ情報及び前記最短ホップ長を取得し、自身のノードからｇホップで到達可能な各ノードmに対して、該ノードmからノードnの隣接ノードjへの最短ホップ長hmjが、該ノードnからノードjに転送した場合のホップ長g＋1よりも小さい場合、該ノードnから該ノードjへのパケット転送は行わないものと設定し、自身のノードから最大pホップ以内で到達可能な全ての経由ノードの組合せに対して、該ノードnから該ノードjへのパケット転送を行うか否かの設定を前記転送判定情報記憶手段のエントリに格納し、
前記パケット転送ステップにおいて、
前記ノードnにパケットが到着した際には、該パケットのヘッダに記述されている最大p個の直近経由ノードIDの組合せに対応する前記転送判定情報記憶手段上のエントリを調べ、その設定がパケットの転送を行う場合にのみ、到着した該パケットを各出力ポートｊに転送する。
【００１７】
本発明（請求項８）は、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（ＮＷ）におけるパケット転送システムのノード装置であって、
隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで得られた該NW全体の接続構造（以下、「トポロジ」と記す）及び、トポロジ情報から任意のノード間の最短ホップ距離を自律的に算出し、トポロジ情報記憶手段に格納する隣接ノード情報交換手段と、
前記トポロジ情報記憶手段から前記トポロジ情報及び各発着ノード間の最短ホップ長に関する情報取得して、最大ホップ長以内の全ノードの組合せに対して各隣接ノードに対するパケット転送が可能か否かの実施判定を行い、判定結果を転送判定記憶手段に格納する転送判定算出手段と、
前記トポロジ情報記憶手段の前記トポロジ情報に基づいて、各隣接ノードに対して同一ノードを経由しないで到達可能な最大ホップ長を算出し、最大到達ホップ長記憶手段に格納する最大到達ホップ長算出手段と、
パケットが当該ノード装置に到着する毎に、前記転送判定記憶手段の判定情報と前記最大到達ホップ長記憶手段の前記最大到達ホップ長を用いて、各隣接ノードｊに対してパケットの転送を行うか否かの判定を行と共に、自ノード装置が発ノードである場合は、目的ノードに至る最短ホップ長を許容ホップ上限値としてパケットのヘッダに記入し、各出力ポートにパケットを送出するパケット転送手段と、を有する。
【発明の効果】
【００１８】
本発明によれば、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（NW）において、任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、所定の論理に基づいてパケット転送を行うか否かを記憶手段に設定しておき、パケット転送時に参照することで、経由ノードにおいて、着ノードのアドレスを用いないでパケットの転送を確定的に行うことが可能となる。
【図面の簡単な説明】
【００１９】
【図１】本発明の一実施の形態におけるシステム構成図である。
【図２】本発明の一実施の形態における確定的ルーティングフリー・パケット転送方式のシーケンス図である。
【図３】本発明の一実施の形態における転送テーブル作成時のルート例である。
【図４】本発明の一実施の形態における最大到達ホップ長を説明するための図である。
【図５】OSPFを用いた場合に対する相対平均リンク負荷を示す図である。
【図６】OSPFを用いた場合に対する相対最大リンク負荷を示す図である。
【図７】本発明の平均到達パケット数を示す図である。
【発明を実施するための形態】
【００２０】
以下図面と共に、本発明の実施の形態を説明する。
【００２１】
本発明は、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク(NW)において、任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、経由ノードにおいて、着ノードのアドレスを用いないでパケットの転送を、ある論理に基づいて転送すべき次ノードのリンクを確定して行うものである。
【００２２】
図１は、本発明の一実施の形態におけるシステム構成を示す。
【００２３】
同図に示すノードは、隣接ノード情報交換部１０１、トポロジ情報記憶部１０２、転送判定算出部１０３、転送判定テーブル１０４、最大到達ホップ長算出部１０５、最大到達ホップ長記憶部１０６、パケット転送処理部１０７から構成される。
【００２４】
上記のトポロジ情報記憶部１０２、転送判定テーブル１０４、最大到達ホップ長記憶部１０６は、ハードディスク等の記憶媒体である。
【００２５】
隣接ノード情報処理部１０１は、自身が接続するノードに関する情報と、隣接ノードから通知された同様の情報を、隣接ノードに対して通知するという、隣接ノード間での情報交換を反復することで、NW全体のトポロジを把握し、トポロジ情報としてトポロジ情報記憶部１０２に格納する。また、トポロジ情報から各発着信ノード間野最短ホップ数を算出してトポロジ記憶部１０２に格納する。
【００２６】
転送判定算出部１０３は、トポロジ情報記憶部１０２から得られる各発着ノード間の最短ホップ長に関する情報を用いて、最大pホップ以内の全ノードの組合せに対して各隣接ノードに対するパケット転送の実施判定を行い、その結果を転送判定テーブル１０４に格納する。
【００２７】
最大到達ホップ長算出部１０５は、各隣接ノードに対して同一ノードを経由しないで到達可能な最大ホップ長を、トポロジ情報記憶部１０２のトポロジ情報を用いて算出し、最大到達ホップ長記憶部１０６に格納する。
【００２８】
パケット転送処理部１０７は、パケットがノードｎに到着するごとに、転送判定テーブル１０４と最大到達ホップ長記憶部１０６から読み出した最大到達ホップ長を用いて、各隣接ノードｊに対してパケットの転送を行うか否かの判定を行う。また、ノードｎを発とするパケットの転送を行う際には、パケット転送処理部１０７は、目的ノードに至る最短ホップ長を許容ホップ上限値としてパケットのヘッダに記入し、各出力ポートにパケットを送出する。
【００２９】
図２は、本発明の一実施の形態における確定的ルーティングフリー・パケット転送方式のシーケンスを示す。
【００３０】
サービス運用の開始に先立ち、各ノードの隣接ノード情報交換部１０１は、隣接ノードとの間で接続ノードに関する情報を交換し、トポロジ情報を取得し、トポロジ情報記憶部１０２に格納する（ステップ１）転送判定算出部１０３において転送判定テーブル１０４を生成し（ステップ２）、最大到達ホップ長算出部１０５においてトポロジ情報から最大到達ホップ長を求め、最大到達ホップ長記憶部１０６に格納する（ステップ３）。
【００３１】
サービス運用が開始されると（ステップ４）、パケット転送処理部１０７は、入力ポートからパケットが到着するか、自ノードを発とするパケットを生成する毎に、各出力ポートにパケットを転送する（ステップ５）。
【００３２】
次に、本発明の実施の形態における確定的ルーティングフリー・パケット転送方式について詳細に説明する。
【００３３】
［事前準備］
NWはN個のノードから構成され、任意のノード間にリンクが設置されている。まず、パケット転送をする開始する前に、各ノードnにおいて自律的に実施される事前準備について述べる。
【００３４】
各ノードnの隣接ノード情報交換部１０１は、隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで、NW全体の接続構造（以下、「トポロジ」と記す）を取得し、当該トポロジ情報から任意のノードペアij間の最短ホップ距離hijを算出し、トポロジ情報と共にトポロジ情報記憶部１０２に格納する。
【００３５】
次に、転送判定算出部１０３は、トポロジ情報記憶部１０２からトポロジ情報及び最短ホップ距離hijを取得し、任意に与えられた整数パラメータｐに対して、ノードnからpホップ以内で到達可能なノードの集合Dn,pを作成する。ノードnからホップ長がg（g≦p）でDn,pに含まれるノードmから、ノードnの隣接ノードjへの最短ホップ長hmjが、ノードｍからノードnを経由してノードjにパケットを転送した場合のホップ長g+1よりも小さい場合、ノードｍから転送され、ノードnに到着したパケットを更にノードjに転送しても同一のパケットがより少ないホップ数でノードｍから他の経路を通ってノードｊに届いている。そのため、ノードnからノードjに転送することは無駄となる。
【００３６】
例えば、図３に示す例の場合、ノードmpからノードｊには２ホップで到達できるルートが存在する。そのため、ノードmp，mp−1，…，m1，n経由でパケットをノードjに転送した場合（ホップ数はｐ＋１）よりも、より短いホップ数でノードmpからノードjにパケットが到達可能である。
【００３７】
そこで、ノードmをノード集合Qn,jに追加する。但し、Qn,jに含まれるノードを過去に経由したパケットがノードnに到達した場合、このパケットを隣接ノードjには転送しない。このようなQn,jへの収容判定をDn,pに含まれる全てのノードを対象に行う。
【００３８】
そして、Dn,pに含まれるノードを対象とした最大p個の全てのノードの組合せを対象に、各々の組合せについて、一つ以上のノードがQn,jに含まれる場合には０を、Qn,jに含まれるノードが存在しない場合には１をエントリに記入したテーブルを作成し、ノードnにおける隣接ノードjへの転送判定テーブル１０４とする。転送判定算出部１０３は、このような処理を、ノードnにおいて、全ての隣接ノードjに対して行う。
【００３９】
最大到達ホップ長算出部１０５は、ノードnから隣接ノードjへのリンク（n，j）に対して、ノードjにノードnからパケットを転送後に同一のノードを複数回経由しないで到達することが可能な最大ホップ長αnjを事前に算出し、最大到達ホップ長記憶部１０６に格納する。例えば、図４に示す例の場合、ノードnからノードj1にパケットを転送したときに同一ノードを経由しないで到達可能な最大ホップ長は２なので、
【００４０】
【数１】
2013098645.tif 000003
となる。同様に、ノードnからノードj2にパケットを転送したときに同一ノードを経由しないで到達可能な最大ホップ数は３なので、
【００４１】
【数２】
2013098645.tif 000004
となる。パケット転送部１０７は、上記から、許容残余ホップ長がαn,jより大きなパケットがノードnに到着した際に、このパケットをノードjに転送したとしても、ノードjから到達できる範囲にこのパケットの目的ノードｄが存在しないことは明らかなので、ノードjへのパケット転送は行わない。
【００４２】
[パケット転送方法]
ノードｎの隣接ノード集合をA'n、隣接ノード数をA n、ノードｓを発ノード、ノードｄを着ノードとするパケット（以下、「パケットsd」と記す）の転送に対して許容されるホップ数の上限を、ノードsd間の最短ホップ長hsd,とし、最大到達ホップ長記憶部１０６に格納されているものとする。パケットのヘッダには、現在のインターネットで用いられているのと同様に、発着アドレス、発着ポート番号、許容残余ホップ長値（TTL: Time to Live）が記述される。
【００４３】
また、これらの情報に加えて、ヘッダ内には、最大でｐ個の直近に経由したノードのIDが記述される。すなわち、ノードnのパケット転送処理部１０７がパケットを生成し、任意の目的ノードdに対してパケットを送出する際に、ノードnのIDを直近の経由ノード情報（経由ノードリスト）としてパケットのヘッダ内に記述し、以後、経由ノードにおいては経由ノードのIDを直近の経由ノードとしてパケットのヘッダ内に追記する処理を反復し、記述された経由ノード数がp個となった場合には、最も古い経由ノードのIDを削除してから追記することで、パケットのヘッダ内には常に、最大でp個の直近の経由ノードのIDが記述された状態を維持する。なお、経由ノード数はトポロジ情報記憶部１０２で保持されているものとする。
【００４４】
ノードnのパケット転送処理部１０７が、新たに目的ノードdに対するパケットを生成する際には、最大到達ホップ長記憶部１０６のｈsdの値をヘッダ内の許容残余ホップ長値として記述し、直近の経由ノードリストに自身のIDを記述した後、全ての出力ポートに対してパケットを送出する。また、ｉ∈A'nの入力ポートiからノードnにパケットが到着した際には、以下の全ての条件が満たされる場合に、j≠iの各出力ポートにパケットを転送する。なお、以下の条件は、予めパケット転送処理部１０７内のメモリ（図示せず）に保持されているものとする。
【００４５】
（１）パケットヘッダに記述された着アドレスdがｄ≠nを満たすこと。
【００４６】
（２）ヘッダ内に記述された許容残余ホップ長hが、２以上でかつ、αnj以下であること。
【００４７】
（３）転送判定テーブル１０４内の、パケットのヘッダに記述されている直近経由ノードリストと合致するエントリが１であること。
【００４８】
パケット転送処理部１０７は、これらの全ての条件を満足する全ての出力リンクjに対して、ヘッダ内の許容残余ホップ長を１だけ減少させた後パケットを転送する。
【００４９】
[性能値の導出]
ここでは、本発明の各性能を図るための尺度を導出する。
【００５０】
パケットsdで、直近にノード集合m、を経由した後、ノードsを出てからkホップ目にノードjに到達する場合に１を、到達しない場合に０をとる２値変数を
【００５１】
【数３】
2013098645.tif 000005
とする。u(C)を条件Cが真のときに１を、偽のときに０をとる２値変数とすると、以下の漸化式が得られる。
【００５２】
【数４】
2013098645.tif 000006
上記の漸化式をk=1からk=hsdまで順に解くことで、ノードnに到達する前に経由することが可能な任意のノード集合ｍに対して、1≦k≦hsdの各kにおける
【００５３】
【数５】
2013098645.tif 000007
を得ることができる。
【００５４】
また、パケットsdでノードｉとｊの間に設置されたリンク（i,j）を単位時間当たりに流れる個数を
【００５５】
【数６】
2013098645.tif 000008
とすると、
【００５６】
【数７】
2013098645.tif 000009
となる。但し、vsdはパケットsdの単位時間あたりに生成される個数である。
【００５７】
wijをリンク（i，j）のトラヒック量（単位時間当たりに流れるパケット数）とすると、
【００５８】
【数８】
2013098645.tif 000010
より得られる。但し、NはNWを構成するノードの集合である。
【００５９】
また、パケットsdの目的ノードdに到達する個数をR(sd)とすると、
【００６０】
【数９】
2013098645.tif 000011
となる。但し、∀mはノードｄに最大pホップで到達可能な全ての経由ノードの組合せの集合である。また、NW全体の平均パケット到達数をRとすると、
【００６１】
【数１０】
2013098645.tif 000012
となる。但し、VはNW全体のトラヒックデマンド量（単位時間あたりに生成されるパケット数）である。
【００６２】
[性能評価]
評価には、CAIDAのWebページでトポロジが公開されている36の商用ISPバックボーンNWを用いる。NW全体の総トラヒックデマンド量Vに対して、交流トラヒックデマンド量を、両端ノードの人口比の積で比例配分する。
【００６３】
図５は、OSPFを用いた場合に対する相対平均リンク負荷を示す。平均リンク負荷を、NWを構成するM本のリンクの負荷wijの平均値とする。図５（a）は、本発明の(i)転送判定テーブルを用いた転送判定と(ii)最大到達ホップ長テーブルを用いた転送判定とを用いずに、最大ホップ長を最大許容転送ホップ数とし、目的ノードに到達したパケットの転送と、ループバックを回避して全出力ポートにパケットを転送した場合（naive法）の平均リンク負荷を、OSPFによる目的アドレスに基づくパケット転送を行った場合の平均リンク負荷で除した値を、各NWに対して、ノード数Nに対してプロットしたものである。また、図5（b）〜(d)は、本発明における、最大ホップ数pを１，２，３とした場合の平均リンク負荷を、同様に、OPSFにおける平均リンク負荷で除した値を、各NWのノード数Nに対してプロットした例である。Nの小さい小規模のNWの場合、本発明とnaive法との差異が小さく、本発明の効果は低い。しかし、中規模〜大規模NWにおいては、ｐを2以上とした場合の本発明の効果は高い。
【００６４】
p＝2と設定した場合、ノードの最大次数程度の要素数のテーブル管理を行えばよいため、テーブル管理コストが低く抑えられるメリットがある。naive法の場合、OSPFと比較して平均リンク負荷が10〜100倍程度になるのに対して、本発明を用いることで、例えば、p=2の場合、平均リンク負荷を5〜10倍程度に抑制できることが確認できる。
【００６５】
図６は、OSPFを用いた場合に対する相対最大リンク負荷を示す。
【００６６】
図６(a)は、naive法における最大リンク負荷をOSPFにおける最大リンク負荷で除した値を各NWのノード数Nに対してプロットした例である。同様に、図６(b)〜(d)に、本発明の、ｐの三つの値におけるOSPFに対する相対最大リンク負荷をプロットする。本発明を用いることで、naive法と比較して最大リンク負荷を低減することができ、例えば、p＝2の場合、最大リンク負荷のOSPFと比較した増加を２〜７倍程度に抑えることができる。
【００６７】
また、図７は、本発明の平均到達パケット数であり、各NWの平均パケット到達数Rをノード数Nにプロットした結果を示す。本発明のRはpの値とは無関係に、またnaive法におけるRとも全て一致する。これは、許容ホップ長の上限をOSPFにおける最短ホップ長としているため、とり得る最短ホップ経路の数が到達パケット数となるためである。多くのNWにおいて平均的に１〜２個程度のパケットが目的ノードに到達することが確認できる。
【００６８】
上記のように、本発明は、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したNWにおいて、任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、経由ノードにおいて着ノードのアドレスを用いずに、パケット転送を、上記に述べた論理に基づいて転送すべき次ノードのリンクを確定して行う。これにより、目的アドレスに基づきパケットを転送すべき出力ポートを決めていたため、NW規模（目的アドレス数）や、NWを流れるトラヒック量の増加に伴い、パケットのルーティング処理に要する負荷が増加するという問題を解決することができる。
【００６９】
なお、図１に示すノード装置の各構成要素の動作をプログラムとして構築し、上記のネットワーク上のノード装置として利用されるコンピュータにインストールする、または、ネットワークを介して流通させることが可能である。
【００７０】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００７１】
１０１  隣接ノード情報交換部
１０２  トポロジ情報記憶部
１０３  転送判定算出部
１０４  転送判定テーブル
１０５  最大到達ホップ長算出部
１０６  最大到達ホップ長記憶部
１０７  パケット転送処理部
【図１】
2013098645.tif 000013
【図２】
2013098645.tif 000014
【図３】
2013098645.tif 000015
【図４】
2013098645.tif 000016
【図５】
2013098645.tif 000017
【図６】
2013098645.tif 000018
【図７】
2013098645.tif 000019