(57)【要約】【課題】極端にリンク長が異なるパケット通信網においても、安定した高スループットを実現するフロー制御方法を提供する。【解決手段】パケット通信網の各ノードが隣接ノードから受け取る情報および自ノードの情報に基づき、所定の規則に従って各ノードが隣接ノードへのパケット転送レートを決定するフロー制御方法において、所定の規則は、自ノードと隣接ノードに存在するパケット数の差に比例し、かつ自ノードと隣接ノードとの間の伝播遅延時間に反比例する量に応じてパケット転送レートを決定する。【選択図】        図１
2004260361.tif 000002
【特許請求の範囲】
【請求項１】
パケット通信網の各ノードが隣接ノードから受け取る情報および自ノードの情報に基づき、所定の規則に従って各ノードが隣接ノードへのパケット転送レートを決定するフロー制御方法において、
前記所定の規則は、自ノードと隣接ノードに存在するパケット数の差に比例し、かつ自ノードと隣接ノードとの間の伝播遅延時間に反比例する量に応じて前記パケット転送レートを決定することを特徴とするフロー制御方法。
【請求項２】
請求項１に記載のフロー制御方法において、
前記パケット数の差に代えて、前記パケットの総バイト数の差とすることを特徴とするフロー制御方法。
【請求項３】
請求項１に記載のフロー制御方法において、
時刻ｔにおける自ノードｉのパケット転送レートＪｉ（ｔ）は、自ノードｉに存在するパケット数をｎｉ（ｔ）、パケット送出先の隣接ノードｉ＋１に存在するパケット数をｎｉ＋１（ｔ）、隣接ノードｉ＋１から指定されたレート情報をｒｉ  、自ノードｉと隣接ノードｉ＋１との間の伝播遅延をｄｉ  、比例係数をα（＞０），  ｋ（＞０）としたときに、
Ｊｉ（ｔ）＝αｒｉ（ｔ−ｄｉ）−（ｋ／ｄｉ）（ｎｉ＋１（ｔ−ｄｉ）−ｎｉ（ｔ））
とすることを特徴とするフロー制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、異なるリンク長をもつパケット通信網において、安定した動作を実現するために各ノードでパケット転送レートを自律分散制御で決定するフロー制御方法に関する。
【０００２】
【従来の技術】
従来の高速ネットワークに適したフロー制御方法として、自律分散フロー制御方法が提案されている（非特許文献１〜５）。この自律分散フロー制御方法は、ネットワーク全体のリアルタイム情報（特にリンク上に存在する転送データ量）を得るのが原理的に困難な高速ネットワークで利用されるものである。各ノードは、その時点で知りうる自ノードの情報と隣接ノードから通知される限られた情報に基づき、所定の規則に従って自律的にパケット転送レートを制御し、間接的に全ネットワークのフローを分散制御する。以下、非特許文献２，３，４，５を例に、従来の自律分散フロー制御方法について、図１のネットワークモデルを参照して説明する。
【０００３】
一次元的に接続されたネットワークでは、ノードｉは下流ノードｉ＋１にパケットを片方向に転送する。また、各ノードｉは、パケット転送方向とは逆方向にフィードバック情報を送受信する。各ノードｉでの自律的なフロー制御は、ノードｉ自身の情報と、その時点で知り得た下流ノードｉ＋１からのフィードバック情報のみに基づいて行われる。その枠組みは、全てのノードに共通で次の通りである。
【０００４】
▲１▼各ノードｉは、ノードｉ自身の状態情報と、下流ノードｉ＋１からフィードバックされた状態情報のみに基づいて、全てのノードに共通の規則によりパケット転送レートＪｉ  を自律的に決定し、そのレートで下流ノードｉ＋１にパケットを送出する。ただし、ノード内にパケットがない場合は送出しない。
▲２▼各ノードｉは、全てのノードに共通の規則によりノードｉ自身の関する情報を生成し、上流ノードｉ−１に通知する。
▲３▼パケット転送とフィードバック情報通知は、上り／下りともに同一の伝播遅延を受ける。
【０００５】
以上の枠組みに基づき、各ノードが隣接ノードと相互作用しながら自律的に動作するネットワークにおいて、各ノードｉのパケット転送レートの決定規則は次のようになる。
【０００６】
時刻ｔにおけるノードｉのパケット転送レートＪｉ（ｔ）は、ノードｉに存在するパケット数をｎｉ（ｔ）、下流ノードｉ＋１に存在するパケット数をｎｉ＋１（ｔ）、下流ノードｉ＋１から指定されたレート情報をｒｉ  、ノードｉとノードｉ＋１との間の伝播遅延をｄｉ  としたときに、
Ｊｉ（ｔ）＝αｒｉ（ｔ−ｄｉ）−Ｄ（ｎｉ＋１（ｔ−ｄｉ）  −ｎｉ（ｔ））    …（１）  と設定する。なお、式（１）  の右辺第１項をドリフト項、第２項を拡散項と呼び、定数α（＞０）をドリフト係数、定数Ｄ（＞０）を拡散係数と呼ぶ。
【０００７】
ノードｉのパケット転送レートＪｉ（ｔ）を算出するには、式（１）  に示される下流ノードｉ＋１からのフィードバック情報を用いる必要がある。下流ノードｉ＋１からノードｉに到達するフィードバック情報は、伝播遅延ｄｉ  を受けて、
＜ｒｉ（ｔ−ｄｉ）、ｎｉ＋１（ｔ−ｄｉ）＞
である。また、ノードｉから上流ノードｉ−１に通知するレート情報ｒｉ−１（ｔ）は、
ｒｉ−１（ｔ）＝Ｊｉ（ｔ）          …（２）
とし、上流ノードｉ−１へのフィードバック情報として
＜ｒｉ−１（ｔ）、ｎｉ（ｔ）＞
を通知する。
【０００８】
【非特許文献１】
Ｍａｓａｋｉ  Ａｉｄａ，  Ｋｅｎｊｉ  Ｈｏｒｉｋａｗａ，”Ｓｔａｂｉｌｉｔｙ  ａｎａｌｙｓｉｓ  ｆｏｒ  ｇｌｏｂａｌ  ｐｅｒｆｏｒｍａｎｃｅ  ｏｆ  ｆｌｏｗ  ｃｏｎｔｒｏｌ  ｉｎ  ｈｉｇｈ−ｓｐｅｅｄ  ｎｅｔｗｏｒｋｓ  ｂａｓｅｄ  ｏｎ  ｓｔａｔｉｓｔｉｃａｌ  ｐｈｙｓｉｃｓ”，ＩＥＩＣＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，  ｖｏｌ．Ｅ８２−Ｂ，  ｎｏ．１２，  ｐｐ．２０９５−２１０６，  １９９９
【０００９】
【非特許文献２】
Ｍａｓａｋｉ  Ａｉｄａ，  Ｃｈｉｓａ  Ｔａｋａｎｏ，”Ｓｔａｂｉｌｉｔｙ  ｏｆ  ａｕｔｏｎｏｍｏｕｓ  ｄｅｃｅｎｔｒａｌｉｚｅｄ  ｆｌｏｗ  ｃｏｎｔｒｏｌ  ｓｃｈｅｍｅｓ  ｉｎ  ｈｉｇｈ−ｓｐｅｅｄ  ｎｅｔｗｏｒｋｓ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＥＥＥ  ＩＣＤＣＳ  ２００２  Ｗｏｒｋｓｈｏｐ（ＡＤＳＮ  ２００２），  ｐｐ．６３−６８，  Ｖｉｅｎｎａ，  Ａｕｓｔｒｉａ，  Ｊｕｌｙ  ２，  ２００２
【００１０】
【非特許文献３】
高野知佐，会田雅樹，”自律分散フロー制御のネットワーク状態適応性の検討”，２００２年電子情報通信学会ソサイエティ大会，Ｂ−７−１０，２００２年９月
【００１１】
【非特許文献４】
高野知佐，会田雅樹，”高速ネットワークにおける自律分散フロー制御の安定性の検討”，２００２年電子情報通信学会総合大会，ＳＢ−４−４，２００２年３月
【００１２】
【非特許文献５】
会田雅樹，高野知佐，”高速ネットワークにおける自律分散フロー制御の安定性について”，第四回アシュアランスシステ研究会，２００１年１１月
【００１３】
【発明が解決しようとする課題】
従来の自律分散フロー制御方法では、拡散係数Ｄをノードｉによらない定数としていた。そのため、リンク長がすべて等しい高度な対称性をもつ通信網では安定的なフロー制御が可能であるものの、異なるリンク長をもつ通信網では、全体として安定した高スループットを実現することはできなかった。それは、リンク長の伝播遅延が異なることが原因と言える。
【００１４】
本発明は、極端にリンク長が異なるパケット通信網においても、安定した高スループットを実現するフロー制御方法を提供することを目的とする。
【００１５】
【課題を解決するための手段】
本発明は、パケット通信網の各ノードが隣接ノードから受け取る情報および自ノードの情報に基づき、所定の規則に従って各ノードが隣接ノードへのパケット転送レートを決定するフロー制御方法において、所定の規則は、自ノードと隣接ノードに存在するパケット数の差に比例し、かつ自ノードと隣接ノードとの間の伝播遅延時間に反比例する量に応じてパケット転送レートを決定する。なお、パケット数の差に代えて、パケットの総バイト数の差としてもよい。
【００１６】
【発明の実施の形態】
本実施形態では、時刻ｔにおけるノードｉのパケット転送レートＪｉ（ｔ）は、ノードｉに存在するパケット数をｎｉ（ｔ）、下流ノードｉ＋１に存在するパケット数をｎｉ＋１（ｔ）、下流ノードｉ＋１から指定されたレート情報をｒｉ  、ノードｉとノードｉ＋１との間の伝播遅延をｄｉ  、比例係数をｋ（＞０）としたときに、
Ｊｉ（ｔ）＝αｒｉ（ｔ−ｄｉ）−（ｋ／ｄｉ）（ｎｉ＋１（ｔ−ｄｉ）−ｎｉ（ｔ））    …（３）  と設定する。
【００１７】
なお、下流ノードｉ＋１からノードｉに通知するフィードバック情報は、
＜ｒｉ（ｔ−ｄｉ）、ｎｉ＋１（ｔ−ｄｉ）＞
であり、ノードｉから上流ノードｉ−１に通知するフィードバック情報は、
＜ｒｉ−１（ｔ）＝Ｊｉ（ｔ）、ｎｉ（ｔ）＞
であるが、これは従来と同様である。
【００１８】
従来のパケット転送レートを決める式（１）  との違いは、定数である拡散係数Ｄに代えて、ノードｉとノードｉ＋１との間の伝播遅延ｄｉ  に反比例する拡散係数ｋ／ｄｉ  を用いるところにある。すなわち、自ノードと下流のノードに存在するパケット数の差に比例する拡散項の比例係数として、隣接ノード間の伝播遅延に反比例する値を用いる。
【００１９】
これにより、下流ノードとの伝播遅延ｄｉ  が大きくなれば、自ノードと下流のノードに存在するパケット数の差に比例する拡散項の影響が小さいなるようにする。一方、下流ノードとの伝播遅延ｄｉ  が小さくなれば、自ノードと下流のノードに存在するパケット数の差に比例する拡散項の影響が大きくなるようにする。その結果、ノード間の伝播遅延＝リンク長が異なるネットワークにおいて、リンク長の違いを吸収してすべてのリンクが同じ長さをもつようなネットワークと同等の安定したフロー制御が可能になる。
【００２０】
なお、式（３）  において、パケット数ｎｉ（ｔ）、ｎｉ＋１（ｔ−ｄｉ）に代えてパケットの総バイト数を用いても同様である。
【００２１】
図２は、ノード間のリンク長が異なるネットワークモデルを示す。ここでは、６０個のノードからなる閉じたネットワークモデルを考える。１カ所のボトルネック（輻輳）ノード２９、ノード２９からノード３０に向かうボトルネックリンク以外は、すべてのノードおよびリンクは同じ条件とする。ネットワークモデルの条件は次の通りである。
【００２２】
▲１▼ノード数：６０個
▲２▼ノード間の距離：平均は  １．０、分散は  ５．２の対数正規分布に従う
▲３▼ネットワーク内に存在するパケットの総数：６０００個
▲４▼ボトルネックノード：ｉ＝２９
▲５▼ボトルネックリンク以外の各リンクが単位時間当たりに転送可能な最大パケット数：１００  個
▲６▼ボトルネックリンクが単位時間当たりに転送可能な最大パケット数：５０個
【００２３】
ここで、▲５▼と▲６▼の最大パケット数の差は、ボトルネックリンクの転送速度が他と同じとするとリンク長が１／２に相当し、ボトルネックリンクのリンク長が他と同じとすると転送速度が１／２に相当する。すなわち、リンク上に存在する転送データ量は、転送速度と転送距離（リンク長）の積になる。例えば１Ｍｂｉｔ／ｓ  で１ｋｍを転送する場合と、１Ｇｂｉｔ／ｓ  で１０００ｋｍを転送する場合では、同等の転送データがリンク上に存在することになる。
【００２４】
このネットワーク混雑時のフロー制御の安定性を調べるため、上記の条件に加えて、ノード２９の輻輳状態をつくるため、初期状態としてノード２９に存在するパケット数を４００  個とし、残りの５６００個のパケットは他のノード内またはリンク内にランダムに配置した。
【００２５】
図２のネットワークモデルにおいて、ネットワーク内のすべてのリンク上に存在するパケット数を採取し、拡散係数の違いによる性能について評価した結果を図３に示す。ここでは、本発明の伝播遅延ｄｉ  に反比例する拡散係数ｋ／ｄｉ  を  ０．１／ｄｉ  、従来の拡散係数Ｄを０．１  、参考のために伝播遅延ｄｉ  に比例する拡散係数を  ０．１×ｄｉ  とした場合のリンク上の総パケット数の時間変化を太実線、細実線、破線で示す。縦軸はリンク上の総パケット数、横軸は時間を表す。
【００２６】
本発明の伝播遅延ｄｉ  に反比例する拡散係数を用いることにより安定したスループットが得られるが、その他の場合では安定しないことがわかる。全スループットの値も、本発明によれば理論的上限値の３０００（５０パケット／リンク×６０リンク）に近くなっており、良好な性能が得られていることがわかる。
【００２７】
【発明の効果】
以上説明したように、本発明のフロー制御方法は、リンク長に応じたパケット転送レートを決定できるので、リンク長の複雑さを吸収した安定したフロー制御を実現することができる。
【図面の簡単な説明】
【図１】ネットワークモデルを示す図。
【図２】本発明の効果を評価するためのネットワークモデルを示す図。
【図３】本発明の効果の評価結果を示す図。
【図１】
2004260361.tif 000003
【図２】
2004260361.tif 000004
【図３】
2004260361.tif 000005