パケット転送システム及び方法及びノード装置
【課題】 パケットに記述された目的アドレスを用いたルーティング処理を行わずにルータにおいてパケットの転送を確率的に行う。
【解決手段】 本発明は、隣接ノード間に位置するノード装置において、隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで、NW全体のトポロジを把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、各入力ポートiから到着したパケットを各出力ポートｊに転送する確率ｒij(n)と、ノードnを発とするパケットを各出力ポートjに転送する確率Rj(n)とを算出し、許容ホップ長上限値をパケットのヘッダに記入し、転送確率記憶手段の確率に従って各出力ポートにパケットを転送する。
【解決手段】 本発明は、隣接ノード間に位置するノード装置において、隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで、NW全体のトポロジを把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、各入力ポートiから到着したパケットを各出力ポートｊに転送する確率ｒij(n)と、ノードnを発とするパケットを各出力ポートjに転送する確率Rj(n)とを算出し、許容ホップ長上限値をパケットのヘッダに記入し、転送確率記憶手段の確率に従って各出力ポートにパケットを転送する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット転送システム及び方法及びノード装に係り、特に、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（ＮＷ）において、任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、経由ノードにおいて着ノードのアドレスを用いないでパケットの転送を確率的に行うパケット転送システム及び方法及びノード装に関する。
【背景技術】
【０００２】
現在のインターネットは、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全体の接続構造（以下、「トポロジ」と記す）を把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、許容ホップ上限記憶手段に格納する最短ホップ経路算出手段と、
パケットの転送を行うパケット転送手段と、
を有し、
前記パケット転送手段は、
自身を発ノードとし、任意のノードを着ノードとするパケットに対して、自身と該着ノードの組に対して前記許容ホップ上限記憶手段の許容ホップ長上限値を残余許容ホップ長とし、該着ノードのＩＤをパケットのヘッダに挿入して送出する手段と、
任意の入力ポートからパケットが到着した際は、ヘッダに記入された着ノードＩＤと合致するかを確認する確認手段と、
前記確認手段で合致すると判定された場合は、到着した当該パケットの転送は行わず、合致しない場合は、前記残余許容ホップ長を１だけ減少させ、該残余許容ホップ長が２以上の場合は、パケットが転送されてきた隣接ノードを除く他の出力ポートに転送する手段と、を有する手段を含む。
【００１１】
また、本発明（請求項３）は、前記転送処理手段において、
予め定められたパケットの転送確率ｒij(n)とＲj(n)を格納する転送確率記憶手段を更に有し、
前記パケット転送手段において、
前記ｒij(n)と前記Ｒj(n)を用いて、ノードｎは隣接ノードｉからの到着パケットを該確率ｒij(n)で隣接ノードｊに転送し、また、該ノードｎを発ノードとするパケットを確率Ｒj(n)でノードｎから隣接ノードｊに転送する手段を含む。
【００１２】
また、本発明（請求項４）は、前記ノードｎから前記隣接ノードｊに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Ｂnj以下となる条件の下で、該隣接ノードｊ以外の全ての隣接ノードｉからの到着パケットに対する該隣接ノードｊへの転送確率ｒij(n)と、該ノードｎを発ノードとするパケットの該隣接ノードｊへの転送確率Ｒj(n)を同一の値に自律的にランダムな時間間隔で求め、前記転送確率記憶手段に格納する転送確率算出手段を含む。
【００１３】
また、本発明（請求項５）は、請求項４の前記転送確率算出手段において、
【００１４】
【数１】
をノードｓを発ノード、ノードｄを着ノードとするパケット（以下、「パケットｓｄ」と記す）で、該ノードｄに一つ以上到達する確率とし、また、前記ノードｎにおいて、前記隣接ノードｉからの到着パケットｓｄを前記隣接ノードｊに対して転送した場合と転送しない場合の
【００１５】
【数２】
の差分を
【００１６】
【数３】
とし、さらに、
【００１７】
【数４】
が最小となるノードｓとノードｄのペアをｓ*，ｄ*とし、同様に該ノードｎを発ノードとするパケットに対しても、ｉ＝０として定義し、ｒij(n)＞０を満たす隣接ノードｉの中で、
【００１８】
【数５】
が最大の隣接ノードｉをｋ２とし、ｒij(n)＜１、
【００１９】
【数６】
を満たす隣接ノードｉの中で、
【００２０】
【数７】
が最小の隣接ノードｉをｋ１とするとき、該隣接ノードｋ２からの（ｋ２の場合はノードｎを発ノードとする）トラヒックの該隣接ノードｊへの転送量を減少させ、逆に隣接ノードｋ１からの（ｋ１＝の場合はノードｎを発ノードとする）トラヒックの隣接ノードｊへの転送量を増加させることで、該ノードｎから該ノードｊへのリンク上を流れるトラヒック量を前記目標値Ｂnjに維持したまま、
【００２１】
【数８】
となるよう
【００２２】
【数９】
（もしくはＲj(n)）と
【００２３】
【数１０】
（もしくはＲj(n)）とを、ノードｎにおいてランダムな時間で更新する手段を含む。
【発明の効果】
【００２４】
本発明によれば、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワークにおいて、任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、経由ノードにおいて着ノードのアドレスを用いずに、ある論理に基づいて転送すべき次ノードのリンクを確率的に選択して転送することにより、パケットの転送を確率的に行うことができる。
【図面の簡単な説明】
【００２５】
【図１】本発明の一実施の形態におけるシステム構成図である。
【図２】本発明の一実施の形態における確率的ルーティングフリー・パケット転送方式のシーケンス図である。
【図３】本発明の均等割当法における最小到達確率を示す図である。
【図４】本発明の最大最小到達率法の最小到達確率改善効果を示す図である。
【図５】本発明の最大最小到達率法における最小到達確率を示す図である。
【図６】本発明の最大最小到達率法における平均到達確率を示す図である。
【発明を実施するための形態】
【００２６】
以下図面と共に、本発明の実施の形態を説明する。
【００２７】
本発明は、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワークにおいて、任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、経由ノードにおいて着ノードのアドレスを用いないでパケットの転送を、ある論理に基づいて転送すべき次のノードのリンクを確率的に選択して行う。
【００２８】
図１は、本発明の一実施の形態におけるシステム構成を示す。
【００２９】
同図に示す確率的ルーティングフリー・パケット転送システムは、隣接ノード情報交換部１０１、トポロジ情報記憶部１０２、最短ポップ経路算出部１０３、許容ホップ上限記憶部１０４、転送確率算出部１０５、転送確率記憶部１０６、パケット転送処理部１０７から構成される。トポロジ情報記憶部１０２、許容ホップ上限記憶部１０４、転送確率記憶部１０６は、ハードディスク等の記憶媒体である。
【００３０】
隣接ノード情報処理部１０１は、自身が接続するノードに関する情報と、隣接ノードから通知された同様の情報を、隣接ノードに対して通知する。このような隣接ノード間での情報交換を反復することでNW全体のトポロジを把握し、トポロジ情報記憶部１０２に格納する。
【００３１】
最短ホップ経路算出部１０３は、各発着ノード間の最短ホップ経路を、トポロジ情報記憶部１０２のトポロジ情報を用いて算出し、各発着ノードペアに対して最短ホップ長から許容できるホップ数上限値を算出し、許容ホップ上限記憶部１０４に格納する。
【００３２】
転送確率算出部１０５は、各入力ポートiから到着したパケットを各出力ポートｊに転送する確率ｒij(n)と、ノードnを発とするパケットを各出力ポートjに転送する確率Rj(n)とを算出し、転送確率記憶部１０６に格納する。
【００３３】
パケット転送処理部１０７は、パケットがノードnに到着する毎に、転送確率記憶部１０６に格納された転送確率Rj(n)に従い、各出力ポートにパケットを転送する。また、ノードnを発とするパケットの転送を行う際には、パケット転送処理部１０７は、許容ホップ上限記憶部１０４に格納されているホップ上限値をパケットのヘッダに記入し、転送確率記憶部１０６に収容された転送確率に従い、各出力ポートにパケットを転送する。
【００３４】
図２は、本発明の一実施の形態における確率的ルーティングフリー・パケット転送方式のシーケンス図を示す。
【００３５】
サービス運用の開始に先立ち、各ノードの隣接ノード情報交換部１０１は隣接ノードとの間で接続ノードに関する情報を交換し（ステップ１）、最短ホップ経路算出部１０３は、各発着ノードペアに対する許容ホップ長上限を許容ホップ情報記憶部１０４に設定する（ステップ２）。そして、転送確率算出部１０５においてパケット転送確率を設定する（ステップ３）。
【００３６】
サービス運用中（ステップ４）は、入力ポートからパケットが到着するか、自身を発ノードとするパケットを生成するごとに、パケット転送処理部１０７は、転送確率記憶部１０６の予め定めたパケット転送確率に従い、各出力ポートにパケットを転送する（ステップ５）。転送確率算出部１０５は、更にランダムな時間間隔で自立的に、転送確率記憶部１０６のパケット転送確率を更新する（ステップ６）。
【００３７】
次に、本発明の確率的ルーティングフリー・パケット転送方式について詳細に説明する。
【００３８】
[パケット転送方法]
ノードnの隣接ノード集合をA'n、隣接ノード数をA n、ノードsを発ノード、ノードdを着ノードとするパケット（以下、「パケットsd」と記す）の転送に対して許容されるホップ長の上限をMsdとする。なお、A'n、A n、ノードs,dのトポロジ情報はトポロジ情報記憶部１０２に格納され、Msdは許容ホップ上限記憶部１０４に格納されているものとし、転送確率R j (n)が転送確率記憶部１０６に格納されているものとする。パケットのヘッダには、現在のインターネットで用いられているのと同様に、発着アドレス、発着オート番号、許容残余ホップ長値（TTL: time to live）が記述される。
【００３９】
ノードnに収容された下位のNWや端末から生成された、任意の他のノードjを着ノードとするパケットの転送要求に対して、ノードnのパケット転送処理部１０７は、Mndの値をパケットのTTLに記述し、ｊ∈A' nの各出力ポートjに対してR j (n)の確率で転送する。そのため二つ以上の出力ポートに対して同一のパケットが出力される可能性や、どの出力ポートにもパケットが出力されない可能性がある。
【００４０】
また、パケット転送処理部１０７は、i∈A'nの入力ポートiからノードnにパケットが到着した際には、パケットのヘッダに記述された着アドレスdがノードnか否かをチェックし、d=nの場合には、パケットの転送を行わない。
【００４１】
一方、d≠nの場合には、TTLをチェックして1である場合には、やはりパケットの転送を行わない。２以上である場合には、TTLの値を１だけ減少させた後、j∈A'nでｊ≠iの各出力ポートｊに対してｒij (n)の確率で転送する。そのため、やはり２つ以上の出力ポートに対して同一のパケットが出力される可能性や、どの出力ポートにもパケットが出力されない可能性がある。
【００４２】
各ノードｎの転送確率算出部１０５は自律的にランダムな時間間隔で、以下に述べる二つの方法（ｉ）均等割当法、（ii）最大最小到達率法、のいずれかを用いて、パケット転送確率Ｒj(n)，rij(n)を設定する。
【００４３】
（i）均等割当法：
ノードｎからｊ∈A'nの隣接ノードｊに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Ｂn,j以下となる条件の下で、ｊ以外の全ての隣接ノードｉからの到着パケットに対するノードｊへの転送確率rij(n)と、ノードｎを発ノードとするパケットのノードｊへの転送確率Ｒj (n)を同一の値に設定する。
【００４４】
パケットsdの中で、ノードｓを出発してからｋホップ目に、ノードｉから隣接ノードｎに到着するものの個数の期待値を
【００４５】
【数１１】
とすると、ｋ＝1に対しては、
【００４６】
【数１２】
が成立する。また２≦ｋ≦Ｍsdの各ｋに対して、以下の漸近式が成立する。
【００４７】
【数１３】
上記の式（２）の漸近式をｋ＝２から順に解くことで、１≦ｋ≦Msdの各ｋに対して
【００４８】
【数１４】
を得ることができる。
【００４９】
また、パケットsdの中で、ノードｉがノードｎに単位時間当たりに到着するものの個数を
【００５０】
【数１５】
とすると、
【００５１】
【数１６】
より得られる。但し、ｖsdはノードｓを発ノード、ノードｄを着ノードとするトラヒック量（単位時間あたりに発生するパケット数）である。さらにノードｉからノードｎに単位時間あたりに到着するパケット数をｗinとする。
【００５２】
【数１７】
今、任意のｊ∈A'nに対して、ｉ∈A n、ｉ≠ｊの全てのｉに対するrij(n)と、R j (n)を同一の値ｒに設定することを考える。ノードｎを発ノードとするパケットの単位時間当たりの発生数をＶnとすると、リンク（ｎ，ｊ）に流れるトラヒック量（単位時間あたりのパケット数）は、
【００５３】
【数１８】
となり、これが目標値Ｂnj以下となるようｒを設定すればよい。またｒは明らかにｒ∈１を満たすため、ｒを次式で設定する。
【００５４】
【数１９】
[最大最小到達率法]
ノードsを発ノード、ノードdを着ノードとするパケットは、経由ノードにおける確率的な転送を反復する結果、目的ノードdに複数のパケットが到着する可能性もあれば、全く到着しない可能性もある。一つ以上のパケットがノードｄに到着した場合に、このパケット転送が成功したものとみなせるため、パケットsdの到達確率y(sd)をその確率と定義すると、
【００５５】
【数２０】
となる。均等割当法を用いた場合、特定のsdペア間においてパケット到達確率ｙ(sd)が低くなる可能性がある。パケット到達確率が低いと、パケットが正しく目的ノードに届くまでに、何度も再送を繰り返す必要があり、データ転送の完了までに要する時間が長くなり、実用上、問題となる。そこで、均等割当法を用いてノードnにおける隣接ノードjに対するパケット転送確率Rj (n)、rij (n)を設定した状態において、さらにRj (n)，ｒij (n)を調整することで、NW上の最小パケット到達確率の向上を図る。
【００５６】
以下に、ノードnにおいて、隣接ノードjへの出力ポートへのパケット転送確率ｒij (n)、i∈A' n、R j (n)の調整方法について説明する。ノードiとｊがノードnに隣接している場合に、ノードnにノードiから到着したパケットsdをノードjに転送した場合の、パケットsdの到達確率を
【００５７】
【数２１】
とする。同様に、ノードnにノードiから到着したパケットsdをノードｊに転送しない場合の、パケットsdの到達確率を
【００５８】
【数２２】
とする。
【００５９】
【数２３】
を、ノードｉからノードnに到達したパケットをノードｊに転送する確率がrij(n)のときの、パケットsdの到達確率とすると、
【００６０】
【数２４】
は、ノードnを経由しないでノードdに到達する場合の貢献成分
【００６１】
【数２５】
と、ノードnを経由してノードdに到達する場合の貢献成分
【００６２】
【数２６】
との和となるため、
【００６３】
【数２７】
で与えられる。同様にノードnを発ノードとするパケットに対しても、ノードnにおいて隣接ノードｊに転送した場合と転送しない場合の到達確率を各々、
【００６４】
【数２８】
とすると、到達確率
【００６５】
【数２９】
は、
【００６６】
【数３０】
となる。
【００６７】
パケットが転送されてきたノードiにパケットを再度転送するとループバックとなるため、ｒii（n）=0に設定する。
【００６８】
【数３１】
の各々において、これらの値が最小となるsdペアを、各々
【００６９】
【数３２】
とするとき、ak，bk，rkを以下のように定義する。
【００７０】
【数３３】
また、0≦ｋ≦A'n，k≠ｊの各ｋに対して、ｙkをｙk＝ｂkｒkで定義する。
【００７１】
そして、ｂk＞０、ｒk＜１を満たすｋの中で、ｙkが最小のｋをｋ1とする。また、rk>0,
k≠ｋ1を満たすｋの中でｙkが最大のｋをｋ2とする。入力リンクｋ2からの（ｋ2＝0の場合はノードｎを発とする）パケットの出力リンクｊへの転送量を減少させ、代わりに入力リンクｋ1からの（ｋ1＝０の場合はノードｎを発とする）パケットの出力リンクｊへの転送量を増加させることで、出力リンクｊのトラヒック量をBnj以下に維持したまま、
【００７２】
【数３４】
となるよう次式のように、更新前の確率
【００７３】
【数３５】
と、更新後の確率
【００７４】
【数３６】
を更新する。但し、w0n=Vnとする。
【００７５】
【数３７】
但し、更新後の
【００７６】
【数３８】
が更新前の
【００７７】
【数３９】
を下回る場合には、更新は行わず、次の候補をｋ1に設定して同様に更新を試みる処理を、更新対象が見つかるまで反復する。
【００７８】
［性能評価］
評価には、CAIDA（Cooperative Association for Internet Data Analysis）のWebページでトポロジが公開されている商用ISPバックボーンＮＷの中から、ノード数Ｎが40以下の27のNWを用いる。NW全体の総トラヒックデマンド量（単位時間あたりに各ノードにおいて生成されるパケット転送要求数のＮの全ノードについての総計）Vに対して、交流トラヒックデマンド量を、両端ノードの人口比の積で比例配分する。パケット転送確率の初期値は全て0.5に設定する。各sdペアに対して、経由ホップ数上限Ｍsdを、以下のように実数パラメータβを用いてsd間の最短ホップ長Hsdのβ倍に設定する。
【００７９】
【数４０】
また、ノードij間に設置されたリンクを流れるトラヒック量の目標上限値βijを、全てのリンクにおいて同一の値αVに設定する。但し、αは実数パラメータである。
【００８０】
図３に、均等割当法を用いた場合の27の各NWにおける最小パケット到達確率yminをαに対してプロットした結果を示す。但し、βを1.1と1.5に設定した場合の結果を各々示しており、また見やすくするために９つのNWごとにグラフを分けて示している。ランダムに選択したノードにおいて転送レートを更新する処理を、10N回反復した。殆どのNWは、例えばｙmin=0.9を達成するためにはNW全体の総デマンド量の２〜10倍程度のリンク容量が必要となる。また、フルメッシュNW(6,12)はホップ長がMsd以下となる経路が多いため、リンク容量が総デマンド量の0.1〜0.5倍程度であってもymin=0.9を達成できる。小規模NW（15,17）は、リンク負荷が低く抑えられるためα＝0.9程度でymin＝0.9を達成することが可能である。βの増加に伴い、経路の候補の多様性が増し、パケット到達確率が向上する効果がある反面、リンク負荷が増加するためパケット転送確率を低く抑える必要があり、パケット到達確率が低下する効果がある。後者の影響の方がより大きいため、βの増加に伴い、ｙminは全体的に低下する。
【００８１】
また、図４に、最大最小到達率法を用いた場合の各NWにおける最小パケット到達確率yminを、均等割当法を用いた場合のｙminで除した値をαに対してプロットする。α＜１の領域では、最小パケット到達確率ｙminは数倍程度改善するが、α＞１の領域では改善効果は小さい。このことは、αが小さく（リンク容量が小さく）条件が厳しいほど、最大最小到達率法を用いて転送確率を調整することで最小パケット到達確率ｙminを改善できることを意味する。また、βが小さい方が、最大最小到達率法による改善効果は大きい。
【００８２】
図５に、最大最小到達率法を用いた場合の各NWにおける最小パケット到達確率ｙminをαに対してプロットする。依然として多くのNWでは、ｙmin＝0.9を達成するにはNW全体の総デマンド量の２〜10倍程度のリンク容量が必要となる。しかし、0.1＜α＜１の領域では最小パケット到達確率ｙminの改善効果は大きく、多くのNWで0.3〜0.8程度となる。
【００８３】
各sdペアの到達確率ysdにsdペアのトラヒックデマンド量比率を乗じて足し合わせたものを平均到達確率と定義する。図６に、最大最小到達率法を用いた場合の各NWにおける平均到達確率をαに対してプロットする。多くのNWにおいて、NW全体のトラヒックデマンド量に相当するリンク容量があれば、平均到達確率は1に近い。また、βの増加に伴い平均到達確率は僅かに低下する。
【００８４】
上記のように本発明では、目的アドレスに基づいてパケットを転送すべき出力ポートを決めているため、ＮＷ規模（目的アドレス数）や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全体の接続構造（以下、「トポロジ」と記す）を把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、許容ホップ上限記憶手段に格納する最短ホップ経路算出手段と、
パケットの転送を行うパケット転送手段と、
を有し、
前記パケット転送手段は、
自身を発ノードとし、任意のノードを着ノードとするパケットに対して、自身と該着ノードの組に対して前記許容ホップ上限記憶手段の許容ホップ長上限値を残余許容ホップ長とし、該着ノードのＩＤをパケットのヘッダに挿入して送出する手段と、
任意の入力ポートからパケットが到着した際は、ヘッダに記入された着ノードＩＤと合致するかを確認する確認手段と、
前記確認手段で合致すると判定された場合は、到着した当該パケットの転送は行わず、合致しない場合は、前記残余許容ホップ長を１だけ減少させ、該残余許容ホップ長が２以上の場合は、パケットが転送されてきた隣接ノードを除く他の出力ポートに転送する手段と、を有する手段を含む。
【００１１】
また、本発明（請求項３）は、前記転送処理手段において、
予め定められたパケットの転送確率ｒij(n)とＲj(n)を格納する転送確率記憶手段を更に有し、
前記パケット転送手段において、
前記ｒij(n)と前記Ｒj(n)を用いて、ノードｎは隣接ノードｉからの到着パケットを該確率ｒij(n)で隣接ノードｊに転送し、また、該ノードｎを発ノードとするパケットを確率Ｒj(n)でノードｎから隣接ノードｊに転送する手段を含む。
【００１２】
また、本発明（請求項４）は、前記ノードｎから前記隣接ノードｊに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Ｂnj以下となる条件の下で、該隣接ノードｊ以外の全ての隣接ノードｉからの到着パケットに対する該隣接ノードｊへの転送確率ｒij(n)と、該ノードｎを発ノードとするパケットの該隣接ノードｊへの転送確率Ｒj(n)を同一の値に自律的にランダムな時間間隔で求め、前記転送確率記憶手段に格納する転送確率算出手段を含む。
【００１３】
また、本発明（請求項５）は、請求項４の前記転送確率算出手段において、
【００１４】
【数１】
をノードｓを発ノード、ノードｄを着ノードとするパケット（以下、「パケットｓｄ」と記す）で、該ノードｄに一つ以上到達する確率とし、また、前記ノードｎにおいて、前記隣接ノードｉからの到着パケットｓｄを前記隣接ノードｊに対して転送した場合と転送しない場合の
【００１５】
【数２】
の差分を
【００１６】
【数３】
とし、さらに、
【００１７】
【数４】
が最小となるノードｓとノードｄのペアをｓ*，ｄ*とし、同様に該ノードｎを発ノードとするパケットに対しても、ｉ＝０として定義し、ｒij(n)＞０を満たす隣接ノードｉの中で、
【００１８】
【数５】
が最大の隣接ノードｉをｋ２とし、ｒij(n)＜１、
【００１９】
【数６】
を満たす隣接ノードｉの中で、
【００２０】
【数７】
が最小の隣接ノードｉをｋ１とするとき、該隣接ノードｋ２からの（ｋ２の場合はノードｎを発ノードとする）トラヒックの該隣接ノードｊへの転送量を減少させ、逆に隣接ノードｋ１からの（ｋ１＝の場合はノードｎを発ノードとする）トラヒックの隣接ノードｊへの転送量を増加させることで、該ノードｎから該ノードｊへのリンク上を流れるトラヒック量を前記目標値Ｂnjに維持したまま、
【００２１】
【数８】
となるよう
【００２２】
【数９】
（もしくはＲj(n)）と
【００２３】
【数１０】
（もしくはＲj(n)）とを、ノードｎにおいてランダムな時間で更新する手段を含む。
【発明の効果】
【００２４】
本発明によれば、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワークにおいて、任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、経由ノードにおいて着ノードのアドレスを用いずに、ある論理に基づいて転送すべき次ノードのリンクを確率的に選択して転送することにより、パケットの転送を確率的に行うことができる。
【図面の簡単な説明】
【００２５】
【図１】本発明の一実施の形態におけるシステム構成図である。
【図２】本発明の一実施の形態における確率的ルーティングフリー・パケット転送方式のシーケンス図である。
【図３】本発明の均等割当法における最小到達確率を示す図である。
【図４】本発明の最大最小到達率法の最小到達確率改善効果を示す図である。
【図５】本発明の最大最小到達率法における最小到達確率を示す図である。
【図６】本発明の最大最小到達率法における平均到達確率を示す図である。
【発明を実施するための形態】
【００２６】
以下図面と共に、本発明の実施の形態を説明する。
【００２７】
本発明は、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワークにおいて、任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、経由ノードにおいて着ノードのアドレスを用いないでパケットの転送を、ある論理に基づいて転送すべき次のノードのリンクを確率的に選択して行う。
【００２８】
図１は、本発明の一実施の形態におけるシステム構成を示す。
【００２９】
同図に示す確率的ルーティングフリー・パケット転送システムは、隣接ノード情報交換部１０１、トポロジ情報記憶部１０２、最短ポップ経路算出部１０３、許容ホップ上限記憶部１０４、転送確率算出部１０５、転送確率記憶部１０６、パケット転送処理部１０７から構成される。トポロジ情報記憶部１０２、許容ホップ上限記憶部１０４、転送確率記憶部１０６は、ハードディスク等の記憶媒体である。
【００３０】
隣接ノード情報処理部１０１は、自身が接続するノードに関する情報と、隣接ノードから通知された同様の情報を、隣接ノードに対して通知する。このような隣接ノード間での情報交換を反復することでNW全体のトポロジを把握し、トポロジ情報記憶部１０２に格納する。
【００３１】
最短ホップ経路算出部１０３は、各発着ノード間の最短ホップ経路を、トポロジ情報記憶部１０２のトポロジ情報を用いて算出し、各発着ノードペアに対して最短ホップ長から許容できるホップ数上限値を算出し、許容ホップ上限記憶部１０４に格納する。
【００３２】
転送確率算出部１０５は、各入力ポートiから到着したパケットを各出力ポートｊに転送する確率ｒij(n)と、ノードnを発とするパケットを各出力ポートjに転送する確率Rj(n)とを算出し、転送確率記憶部１０６に格納する。
【００３３】
パケット転送処理部１０７は、パケットがノードnに到着する毎に、転送確率記憶部１０６に格納された転送確率Rj(n)に従い、各出力ポートにパケットを転送する。また、ノードnを発とするパケットの転送を行う際には、パケット転送処理部１０７は、許容ホップ上限記憶部１０４に格納されているホップ上限値をパケットのヘッダに記入し、転送確率記憶部１０６に収容された転送確率に従い、各出力ポートにパケットを転送する。
【００３４】
図２は、本発明の一実施の形態における確率的ルーティングフリー・パケット転送方式のシーケンス図を示す。
【００３５】
サービス運用の開始に先立ち、各ノードの隣接ノード情報交換部１０１は隣接ノードとの間で接続ノードに関する情報を交換し（ステップ１）、最短ホップ経路算出部１０３は、各発着ノードペアに対する許容ホップ長上限を許容ホップ情報記憶部１０４に設定する（ステップ２）。そして、転送確率算出部１０５においてパケット転送確率を設定する（ステップ３）。
【００３６】
サービス運用中（ステップ４）は、入力ポートからパケットが到着するか、自身を発ノードとするパケットを生成するごとに、パケット転送処理部１０７は、転送確率記憶部１０６の予め定めたパケット転送確率に従い、各出力ポートにパケットを転送する（ステップ５）。転送確率算出部１０５は、更にランダムな時間間隔で自立的に、転送確率記憶部１０６のパケット転送確率を更新する（ステップ６）。
【００３７】
次に、本発明の確率的ルーティングフリー・パケット転送方式について詳細に説明する。
【００３８】
[パケット転送方法]
ノードnの隣接ノード集合をA'n、隣接ノード数をA n、ノードsを発ノード、ノードdを着ノードとするパケット（以下、「パケットsd」と記す）の転送に対して許容されるホップ長の上限をMsdとする。なお、A'n、A n、ノードs,dのトポロジ情報はトポロジ情報記憶部１０２に格納され、Msdは許容ホップ上限記憶部１０４に格納されているものとし、転送確率R j (n)が転送確率記憶部１０６に格納されているものとする。パケットのヘッダには、現在のインターネットで用いられているのと同様に、発着アドレス、発着オート番号、許容残余ホップ長値（TTL: time to live）が記述される。
【００３９】
ノードnに収容された下位のNWや端末から生成された、任意の他のノードjを着ノードとするパケットの転送要求に対して、ノードnのパケット転送処理部１０７は、Mndの値をパケットのTTLに記述し、ｊ∈A' nの各出力ポートjに対してR j (n)の確率で転送する。そのため二つ以上の出力ポートに対して同一のパケットが出力される可能性や、どの出力ポートにもパケットが出力されない可能性がある。
【００４０】
また、パケット転送処理部１０７は、i∈A'nの入力ポートiからノードnにパケットが到着した際には、パケットのヘッダに記述された着アドレスdがノードnか否かをチェックし、d=nの場合には、パケットの転送を行わない。
【００４１】
一方、d≠nの場合には、TTLをチェックして1である場合には、やはりパケットの転送を行わない。２以上である場合には、TTLの値を１だけ減少させた後、j∈A'nでｊ≠iの各出力ポートｊに対してｒij (n)の確率で転送する。そのため、やはり２つ以上の出力ポートに対して同一のパケットが出力される可能性や、どの出力ポートにもパケットが出力されない可能性がある。
【００４２】
各ノードｎの転送確率算出部１０５は自律的にランダムな時間間隔で、以下に述べる二つの方法（ｉ）均等割当法、（ii）最大最小到達率法、のいずれかを用いて、パケット転送確率Ｒj(n)，rij(n)を設定する。
【００４３】
（i）均等割当法：
ノードｎからｊ∈A'nの隣接ノードｊに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Ｂn,j以下となる条件の下で、ｊ以外の全ての隣接ノードｉからの到着パケットに対するノードｊへの転送確率rij(n)と、ノードｎを発ノードとするパケットのノードｊへの転送確率Ｒj (n)を同一の値に設定する。
【００４４】
パケットsdの中で、ノードｓを出発してからｋホップ目に、ノードｉから隣接ノードｎに到着するものの個数の期待値を
【００４５】
【数１１】
とすると、ｋ＝1に対しては、
【００４６】
【数１２】
が成立する。また２≦ｋ≦Ｍsdの各ｋに対して、以下の漸近式が成立する。
【００４７】
【数１３】
上記の式（２）の漸近式をｋ＝２から順に解くことで、１≦ｋ≦Msdの各ｋに対して
【００４８】
【数１４】
を得ることができる。
【００４９】
また、パケットsdの中で、ノードｉがノードｎに単位時間当たりに到着するものの個数を
【００５０】
【数１５】
とすると、
【００５１】
【数１６】
より得られる。但し、ｖsdはノードｓを発ノード、ノードｄを着ノードとするトラヒック量（単位時間あたりに発生するパケット数）である。さらにノードｉからノードｎに単位時間あたりに到着するパケット数をｗinとする。
【００５２】
【数１７】
今、任意のｊ∈A'nに対して、ｉ∈A n、ｉ≠ｊの全てのｉに対するrij(n)と、R j (n)を同一の値ｒに設定することを考える。ノードｎを発ノードとするパケットの単位時間当たりの発生数をＶnとすると、リンク（ｎ，ｊ）に流れるトラヒック量（単位時間あたりのパケット数）は、
【００５３】
【数１８】
となり、これが目標値Ｂnj以下となるようｒを設定すればよい。またｒは明らかにｒ∈１を満たすため、ｒを次式で設定する。
【００５４】
【数１９】
[最大最小到達率法]
ノードsを発ノード、ノードdを着ノードとするパケットは、経由ノードにおける確率的な転送を反復する結果、目的ノードdに複数のパケットが到着する可能性もあれば、全く到着しない可能性もある。一つ以上のパケットがノードｄに到着した場合に、このパケット転送が成功したものとみなせるため、パケットsdの到達確率y(sd)をその確率と定義すると、
【００５５】
【数２０】
となる。均等割当法を用いた場合、特定のsdペア間においてパケット到達確率ｙ(sd)が低くなる可能性がある。パケット到達確率が低いと、パケットが正しく目的ノードに届くまでに、何度も再送を繰り返す必要があり、データ転送の完了までに要する時間が長くなり、実用上、問題となる。そこで、均等割当法を用いてノードnにおける隣接ノードjに対するパケット転送確率Rj (n)、rij (n)を設定した状態において、さらにRj (n)，ｒij (n)を調整することで、NW上の最小パケット到達確率の向上を図る。
【００５６】
以下に、ノードnにおいて、隣接ノードjへの出力ポートへのパケット転送確率ｒij (n)、i∈A' n、R j (n)の調整方法について説明する。ノードiとｊがノードnに隣接している場合に、ノードnにノードiから到着したパケットsdをノードjに転送した場合の、パケットsdの到達確率を
【００５７】
【数２１】
とする。同様に、ノードnにノードiから到着したパケットsdをノードｊに転送しない場合の、パケットsdの到達確率を
【００５８】
【数２２】
とする。
【００５９】
【数２３】
を、ノードｉからノードnに到達したパケットをノードｊに転送する確率がrij(n)のときの、パケットsdの到達確率とすると、
【００６０】
【数２４】
は、ノードnを経由しないでノードdに到達する場合の貢献成分
【００６１】
【数２５】
と、ノードnを経由してノードdに到達する場合の貢献成分
【００６２】
【数２６】
との和となるため、
【００６３】
【数２７】
で与えられる。同様にノードnを発ノードとするパケットに対しても、ノードnにおいて隣接ノードｊに転送した場合と転送しない場合の到達確率を各々、
【００６４】
【数２８】
とすると、到達確率
【００６５】
【数２９】
は、
【００６６】
【数３０】
となる。
【００６７】
パケットが転送されてきたノードiにパケットを再度転送するとループバックとなるため、ｒii（n）=0に設定する。
【００６８】
【数３１】
の各々において、これらの値が最小となるsdペアを、各々
【００６９】
【数３２】
とするとき、ak，bk，rkを以下のように定義する。
【００７０】
【数３３】
また、0≦ｋ≦A'n，k≠ｊの各ｋに対して、ｙkをｙk＝ｂkｒkで定義する。
【００７１】
そして、ｂk＞０、ｒk＜１を満たすｋの中で、ｙkが最小のｋをｋ1とする。また、rk>0,
k≠ｋ1を満たすｋの中でｙkが最大のｋをｋ2とする。入力リンクｋ2からの（ｋ2＝0の場合はノードｎを発とする）パケットの出力リンクｊへの転送量を減少させ、代わりに入力リンクｋ1からの（ｋ1＝０の場合はノードｎを発とする）パケットの出力リンクｊへの転送量を増加させることで、出力リンクｊのトラヒック量をBnj以下に維持したまま、
【００７２】
【数３４】
となるよう次式のように、更新前の確率
【００７３】
【数３５】
と、更新後の確率
【００７４】
【数３６】
を更新する。但し、w0n=Vnとする。
【００７５】
【数３７】
但し、更新後の
【００７６】
【数３８】
が更新前の
【００７７】
【数３９】
を下回る場合には、更新は行わず、次の候補をｋ1に設定して同様に更新を試みる処理を、更新対象が見つかるまで反復する。
【００７８】
［性能評価］
評価には、CAIDA（Cooperative Association for Internet Data Analysis）のWebページでトポロジが公開されている商用ISPバックボーンＮＷの中から、ノード数Ｎが40以下の27のNWを用いる。NW全体の総トラヒックデマンド量（単位時間あたりに各ノードにおいて生成されるパケット転送要求数のＮの全ノードについての総計）Vに対して、交流トラヒックデマンド量を、両端ノードの人口比の積で比例配分する。パケット転送確率の初期値は全て0.5に設定する。各sdペアに対して、経由ホップ数上限Ｍsdを、以下のように実数パラメータβを用いてsd間の最短ホップ長Hsdのβ倍に設定する。
【００７９】
【数４０】
また、ノードij間に設置されたリンクを流れるトラヒック量の目標上限値βijを、全てのリンクにおいて同一の値αVに設定する。但し、αは実数パラメータである。
【００８０】
図３に、均等割当法を用いた場合の27の各NWにおける最小パケット到達確率yminをαに対してプロットした結果を示す。但し、βを1.1と1.5に設定した場合の結果を各々示しており、また見やすくするために９つのNWごとにグラフを分けて示している。ランダムに選択したノードにおいて転送レートを更新する処理を、10N回反復した。殆どのNWは、例えばｙmin=0.9を達成するためにはNW全体の総デマンド量の２〜10倍程度のリンク容量が必要となる。また、フルメッシュNW(6,12)はホップ長がMsd以下となる経路が多いため、リンク容量が総デマンド量の0.1〜0.5倍程度であってもymin=0.9を達成できる。小規模NW（15,17）は、リンク負荷が低く抑えられるためα＝0.9程度でymin＝0.9を達成することが可能である。βの増加に伴い、経路の候補の多様性が増し、パケット到達確率が向上する効果がある反面、リンク負荷が増加するためパケット転送確率を低く抑える必要があり、パケット到達確率が低下する効果がある。後者の影響の方がより大きいため、βの増加に伴い、ｙminは全体的に低下する。
【００８１】
また、図４に、最大最小到達率法を用いた場合の各NWにおける最小パケット到達確率yminを、均等割当法を用いた場合のｙminで除した値をαに対してプロットする。α＜１の領域では、最小パケット到達確率ｙminは数倍程度改善するが、α＞１の領域では改善効果は小さい。このことは、αが小さく（リンク容量が小さく）条件が厳しいほど、最大最小到達率法を用いて転送確率を調整することで最小パケット到達確率ｙminを改善できることを意味する。また、βが小さい方が、最大最小到達率法による改善効果は大きい。
【００８２】
図５に、最大最小到達率法を用いた場合の各NWにおける最小パケット到達確率ｙminをαに対してプロットする。依然として多くのNWでは、ｙmin＝0.9を達成するにはNW全体の総デマンド量の２〜10倍程度のリンク容量が必要となる。しかし、0.1＜α＜１の領域では最小パケット到達確率ｙminの改善効果は大きく、多くのNWで0.3〜0.8程度となる。
【００８３】
各sdペアの到達確率ysdにsdペアのトラヒックデマンド量比率を乗じて足し合わせたものを平均到達確率と定義する。図６に、最大最小到達率法を用いた場合の各NWにおける平均到達確率をαに対してプロットする。多くのNWにおいて、NW全体のトラヒックデマンド量に相当するリンク容量があれば、平均到達確率は1に近い。また、βの増加に伴い平均到達確率は僅かに低下する。
【００８４】
上記のように本発明では、目的アドレスに基づいてパケットを転送すべき出力ポートを決めているため、ＮＷ規模（目的アドレス数）やNWを流れるトラヒック量の増加に伴い、パケットのルーティング処理に要する負荷が増加するという、従来技術の課題を解決することができる。
【００８５】
なお、本発明では、上記の図１に示すノードの各構成要素の動作をプログラムとして構築し、パケットの転送を行う各ノード装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００８６】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００８７】
１０１ 隣接ノード情報交換部
１０２ トポロジ情報記憶部
１０３ 最短ホップ経路算出部
１０４ 許容ホップ上限記憶部
１０５ 転送確率算出部
１０６ 転送確率記憶部
１０７ パケット転送処理部
【特許請求の範囲】
【請求項１】
複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（ＮＷ）におけるパケット転送システムであって、
任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、
経由ノードは、
着ノードのアドレスを用いずに、予め設定された論理に基づいて、転送すべき次ノードのリンクを確率的に選択してパケットの転送を行う転送処理手段を有する
ことを特徴とするパケット転送システム。
【請求項２】
前記転送処理手段は、
隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで、NW全体の接続構造（以下、「トポロジ」と記す）を把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、許容ホップ上限記憶手段に格納する最短ホップ経路算出手段と、
パケットの転送を行うパケット転送手段と、
を有し、
前記パケット転送手段は、
自身を発ノードとし、任意のノードを着ノードとするパケットに対して、自身と該着ノードの組に対して前記許容ホップ上限記憶手段の許容ホップ長上限値を残余許容ホップ長とし、該着ノードのＩＤをパケットのヘッダに挿入して送出する手段と、
任意の入力ポートからパケットが到着した際は、ヘッダに記入された着ノードＩＤと合致するかを確認する確認手段と、
前記確認手段で合致すると判定された場合は、到着した当該パケットの転送は行わず、合致しない場合は、前記残余許容ホップ長を１だけ減少させ、該残余許容ホップ長が２以上の場合は、パケットが転送されてきた隣接ノードを除く他の出力ポートに転送する手段と、を有する手段を含む
請求項１記載のパケット転送システム。
【請求項３】
前記転送処理手段は、
予め定められたパケットの転送確率ｒij(n)とＲj(n)を格納する転送確率記憶手段を更に有し、
前記パケット転送手段は、
前記ｒij(n)と前記Ｒj(n)を用いて、ノードｎは隣接ノードｉからの到着パケットを該確率ｒij(n)で隣接ノードｊに転送し、また、該ノードｎを発ノードとするパケットを確率Ｒj(n)でノードｎから隣接ノードｊに転送する手段を含む
請求項２記載のパケット転送システム。
【請求項４】
前記ノードｎから前記隣接ノードｊに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Ｂnj以下となる条件の下で、該隣接ノードｊ以外の全ての隣接ノードｉからの到着パケットに対する該隣接ノードｊへの転送確率ｒij(n)と、該ノードｎを発ノードとするパケットの該隣接ノードｊへの転送確率Ｒj(n)を同一の値に自律的にランダムな時間間隔で求め、前記転送確率記憶手段に格納する転送確率算出手段を含む
請求項３記載のパケット転送システム。
【請求項５】
前記転送確率算出手段は、
【数４１】
をノードｓを発ノード、ノードｄを着ノードとするパケット（以下、「パケットｓｄ」と記す）で、該ノードｄに一つ以上到達する確率とし、また、前記ノードｎにおいて、前記隣接ノードｉからの到着パケットｓｄを前記隣接ノードｊに対して転送した場合と転送しない場合の
【数４２】
の差分を
【数４３】
とし、さらに、
【数４４】
が最小となるノードｓとノードｄのペアをｓ*，ｄ*とし、同様に該ノードｎを発ノードとするパケットに対しても、ｉ＝０として定義し、ｒij(n)＞０を満たす隣接ノードｉの中で、
【数４５】
が最大の隣接ノードｉをｋ２とし、ｒij(n)＜１、
【数４６】
を満たす隣接ノードｉの中で、
【数４７】
が最小の隣接ノードｉをｋ１とするとき、該隣接ノードｋ２からの（ｋ２の場合はノードｎを発ノードとする）トラヒックの該隣接ノードｊへの転送量を減少させ、逆に隣接ノードｋ１からの（ｋ１＝の場合はノードｎを発ノードとする）トラヒックの隣接ノードｊへの転送量を増加させることで、該ノードｎから該ノードｊへのリンク上を流れるトラヒック量を前記目標値Ｂnjに維持したまま、
【数４８】
となるよう
【数４９】
（もしくはＲj(n)）と
【数５０】
（もしくはＲj(n)）とを、ノードｎにおいてランダムな時間で更新する手段を含む
請求項４記載のパケット転送システム。
【請求項６】
複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（ＮＷ）におけるパケット転送方法であって、
隣接ノード間に位置し、任意のノード（発ノード）から任意ノード（着ノード）へパケット転送するノード装置において、
最短ホップ経路算出手段が、隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで、NW全体の接続構造（以下、「トポロジ」と記す）を把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、許容ホップ上限記憶手段に格納する最短ホップ経路算出ステップと、
転送確率算出手段が、各入力ポートiから到着したパケットを各出力ポートｊに転送する確率ｒij(n)と、ノードnを発とするパケットを各出力ポートjに転送する確率Rj(n)とを算出し、転送確率記憶手段に格納する転送確率算出ステップと、
パケット転送手段が、前記許容ホップ上限記憶手段に格納された前記許容ホップ長上限値をパケットのヘッダに記入し、前記転送確率記憶手段の前記確率に従って各出力ポートにパケットを転送するパケット転送ステップと、
からなり、
前記転送確率算出ステップにおいて、
前記ノードｎから前記隣接ノードｊに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Ｂnj以下となる条件の下で、該隣接ノードｊ以外の全ての隣接ノードｉからの到着パケットに対する該隣接ノードｊへの転送確率ｒij(n)と、該ノードｎを発ノードとするパケットの該隣接ノードｊへの転送確率Ｒj(n)を同一の値に自律的にランダムな時間間隔で求め、前記転送確率記憶手段に格納し、
前記パケット転送ステップにおいて、
前記ｒij(n)と前記Ｒj(n)を用いて、ノードｎは隣接ノードｉからの到着パケットを該確率ｒij(n)で隣接ノードｊに転送し、また、該ノードｎを発ノードとするパケットを確率Ｒj(n)でノードｎから隣接ノードｊに転送する
ことを特徴とするパケット転送方法。
【請求項７】
複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（ＮＷ）におけるパケット転送システムにおいて、 隣接ノード間に位置し、任意のノード（発ノード）から任意ノード（着ノード）へパケット転送するノード装置であって、
隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで、NW全体の接続構造（以下、「トポロジ」と記す）を把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、許容ホップ上限記憶手段に格納する最短ホップ経路算出手段と、
各入力ポートiから到着したパケットを各出力ポートｊに転送する確率ｒij(n)と、ノードnを発とするパケットを各出力ポートjに転送する確率Rj(n)とを算出し、転送確率記憶手段に格納する転送確率算出手段と、
前記許容ホップ上限記憶手段に格納された前記許容ホップ長上限値をパケットのヘッダに記入し、前記転送確率記憶手段の前記確率に従って各出力ポートにパケットを転送するパケット転送手段と、
を有し、
前記転送確率算出手段は、
前記ノードｎから前記隣接ノードｊに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Ｂnj以下となる条件の下で、該隣接ノードｊ以外の全ての隣接ノードｉからの到着パケットに対する該隣接ノードｊへの転送確率ｒij(n)と、該ノードｎを発ノードとするパケットの該隣接ノードｊへの転送確率Ｒj(n)を同一の値に自律的にランダムな時間間隔で求め、前記転送確率記憶手段に格納する手段を含み、
前記パケット転送手段は、
前記ｒij(n)と前記Ｒj(n)を用いて、ノードｎは隣接ノードｉからの到着パケットを該確率ｒij(n)で隣接ノードｊに転送し、また、該ノードｎを発ノードとするパケットを確率Ｒj(n)でノードｎから隣接ノードｊに転送する手段を含む
と、含むことを特徴とするノード装置。
【請求項１】
複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（ＮＷ）におけるパケット転送システムであって、
任意のノード（発ノード）から任意のノード（着ノード）へのパケット転送を行う場合に、
経由ノードは、
着ノードのアドレスを用いずに、予め設定された論理に基づいて、転送すべき次ノードのリンクを確率的に選択してパケットの転送を行う転送処理手段を有する
ことを特徴とするパケット転送システム。
【請求項２】
前記転送処理手段は、
隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで、NW全体の接続構造（以下、「トポロジ」と記す）を把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、許容ホップ上限記憶手段に格納する最短ホップ経路算出手段と、
パケットの転送を行うパケット転送手段と、
を有し、
前記パケット転送手段は、
自身を発ノードとし、任意のノードを着ノードとするパケットに対して、自身と該着ノードの組に対して前記許容ホップ上限記憶手段の許容ホップ長上限値を残余許容ホップ長とし、該着ノードのＩＤをパケットのヘッダに挿入して送出する手段と、
任意の入力ポートからパケットが到着した際は、ヘッダに記入された着ノードＩＤと合致するかを確認する確認手段と、
前記確認手段で合致すると判定された場合は、到着した当該パケットの転送は行わず、合致しない場合は、前記残余許容ホップ長を１だけ減少させ、該残余許容ホップ長が２以上の場合は、パケットが転送されてきた隣接ノードを除く他の出力ポートに転送する手段と、を有する手段を含む
請求項１記載のパケット転送システム。
【請求項３】
前記転送処理手段は、
予め定められたパケットの転送確率ｒij(n)とＲj(n)を格納する転送確率記憶手段を更に有し、
前記パケット転送手段は、
前記ｒij(n)と前記Ｒj(n)を用いて、ノードｎは隣接ノードｉからの到着パケットを該確率ｒij(n)で隣接ノードｊに転送し、また、該ノードｎを発ノードとするパケットを確率Ｒj(n)でノードｎから隣接ノードｊに転送する手段を含む
請求項２記載のパケット転送システム。
【請求項４】
前記ノードｎから前記隣接ノードｊに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Ｂnj以下となる条件の下で、該隣接ノードｊ以外の全ての隣接ノードｉからの到着パケットに対する該隣接ノードｊへの転送確率ｒij(n)と、該ノードｎを発ノードとするパケットの該隣接ノードｊへの転送確率Ｒj(n)を同一の値に自律的にランダムな時間間隔で求め、前記転送確率記憶手段に格納する転送確率算出手段を含む
請求項３記載のパケット転送システム。
【請求項５】
前記転送確率算出手段は、
【数４１】
をノードｓを発ノード、ノードｄを着ノードとするパケット（以下、「パケットｓｄ」と記す）で、該ノードｄに一つ以上到達する確率とし、また、前記ノードｎにおいて、前記隣接ノードｉからの到着パケットｓｄを前記隣接ノードｊに対して転送した場合と転送しない場合の
【数４２】
の差分を
【数４３】
とし、さらに、
【数４４】
が最小となるノードｓとノードｄのペアをｓ*，ｄ*とし、同様に該ノードｎを発ノードとするパケットに対しても、ｉ＝０として定義し、ｒij(n)＞０を満たす隣接ノードｉの中で、
【数４５】
が最大の隣接ノードｉをｋ２とし、ｒij(n)＜１、
【数４６】
を満たす隣接ノードｉの中で、
【数４７】
が最小の隣接ノードｉをｋ１とするとき、該隣接ノードｋ２からの（ｋ２の場合はノードｎを発ノードとする）トラヒックの該隣接ノードｊへの転送量を減少させ、逆に隣接ノードｋ１からの（ｋ１＝の場合はノードｎを発ノードとする）トラヒックの隣接ノードｊへの転送量を増加させることで、該ノードｎから該ノードｊへのリンク上を流れるトラヒック量を前記目標値Ｂnjに維持したまま、
【数４８】
となるよう
【数４９】
（もしくはＲj(n)）と
【数５０】
（もしくはＲj(n)）とを、ノードｎにおいてランダムな時間で更新する手段を含む
請求項４記載のパケット転送システム。
【請求項６】
複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（ＮＷ）におけるパケット転送方法であって、
隣接ノード間に位置し、任意のノード（発ノード）から任意ノード（着ノード）へパケット転送するノード装置において、
最短ホップ経路算出手段が、隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで、NW全体の接続構造（以下、「トポロジ」と記す）を把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、許容ホップ上限記憶手段に格納する最短ホップ経路算出ステップと、
転送確率算出手段が、各入力ポートiから到着したパケットを各出力ポートｊに転送する確率ｒij(n)と、ノードnを発とするパケットを各出力ポートjに転送する確率Rj(n)とを算出し、転送確率記憶手段に格納する転送確率算出ステップと、
パケット転送手段が、前記許容ホップ上限記憶手段に格納された前記許容ホップ長上限値をパケットのヘッダに記入し、前記転送確率記憶手段の前記確率に従って各出力ポートにパケットを転送するパケット転送ステップと、
からなり、
前記転送確率算出ステップにおいて、
前記ノードｎから前記隣接ノードｊに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Ｂnj以下となる条件の下で、該隣接ノードｊ以外の全ての隣接ノードｉからの到着パケットに対する該隣接ノードｊへの転送確率ｒij(n)と、該ノードｎを発ノードとするパケットの該隣接ノードｊへの転送確率Ｒj(n)を同一の値に自律的にランダムな時間間隔で求め、前記転送確率記憶手段に格納し、
前記パケット転送ステップにおいて、
前記ｒij(n)と前記Ｒj(n)を用いて、ノードｎは隣接ノードｉからの到着パケットを該確率ｒij(n)で隣接ノードｊに転送し、また、該ノードｎを発ノードとするパケットを確率Ｒj(n)でノードｎから隣接ノードｊに転送する
ことを特徴とするパケット転送方法。
【請求項７】
複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワーク（ＮＷ）におけるパケット転送システムにおいて、 隣接ノード間に位置し、任意のノード（発ノード）から任意ノード（着ノード）へパケット転送するノード装置であって、
隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで、NW全体の接続構造（以下、「トポロジ」と記す）を把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、許容ホップ上限記憶手段に格納する最短ホップ経路算出手段と、
各入力ポートiから到着したパケットを各出力ポートｊに転送する確率ｒij(n)と、ノードnを発とするパケットを各出力ポートjに転送する確率Rj(n)とを算出し、転送確率記憶手段に格納する転送確率算出手段と、
前記許容ホップ上限記憶手段に格納された前記許容ホップ長上限値をパケットのヘッダに記入し、前記転送確率記憶手段の前記確率に従って各出力ポートにパケットを転送するパケット転送手段と、
を有し、
前記転送確率算出手段は、
前記ノードｎから前記隣接ノードｊに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Ｂnj以下となる条件の下で、該隣接ノードｊ以外の全ての隣接ノードｉからの到着パケットに対する該隣接ノードｊへの転送確率ｒij(n)と、該ノードｎを発ノードとするパケットの該隣接ノードｊへの転送確率Ｒj(n)を同一の値に自律的にランダムな時間間隔で求め、前記転送確率記憶手段に格納する手段を含み、
前記パケット転送手段は、
前記ｒij(n)と前記Ｒj(n)を用いて、ノードｎは隣接ノードｉからの到着パケットを該確率ｒij(n)で隣接ノードｊに転送し、また、該ノードｎを発ノードとするパケットを確率Ｒj(n)でノードｎから隣接ノードｊに転送する手段を含む
と、含むことを特徴とするノード装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１３−９８６４６（Ｐ２０１３−９８６４６Ａ）
【公開日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【出願番号】特願２０１１−２３７７５０（Ｐ２０１１−２３７７５０）
【出願日】平成２３年１０月２８日（２０１１．１０．２８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【出願日】平成２３年１０月２８日（２０１１．１０．２８）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]