(57)【要約】【課題】  ネットワーク内のパケット数が変動する環境においても、ネットワークの転送効率を高く維持でき、ネットワーク内の余分なパケット数を少なく維持できるパケット通信網のフロー制御方法を提供する。【解決手段】  パケット通信網の各ノードは、自ノードより下流にあるリンクの利用可能帯域の仮定最小値を、自ノードにパケットを送出する上流ノードに通知するために、自ノードから隣接ノードに向かうリンクの利用可能帯域とその隣接ノードより下流にあるリンクの利用可能帯域の仮定最小値とを用いて決定する。パケット通信網のノードの少なくともいずれかは、自ノードから隣接ノードへのパケット転送レートを、自ノードより下流にあるリンクの利用可能帯域の仮定最小値以下の範囲内で設定する。【選択図】      図２
2005072711.tif 000002
【特許請求の範囲】
【請求項１】
パケット通信網の各ノードが、パケット送出先の隣接ノードから受け取る情報および自ノードの情報に基づき、所定の規則に従って自ノードから隣接ノードへのパケット転送レートを設定するパケット通信網のフロー制御方法において、
前記所定の規則は、
自ノードより下流にあるリンクの利用可能帯域の仮定最小値を、自ノードにパケットを送出する上流ノードに通知するために、自ノードから隣接ノードに向かうリンクの利用可能帯域とその隣接ノードより下流にあるリンクの利用可能帯域の仮定最小値とを用いて決定する規則と、
前記パケット通信網のノードの少なくともいずれかにおいて、自ノードから隣接ノードへのパケット転送レートを、自ノードより下流にあるリンクの利用可能帯域の仮定最小値以下の範囲内で設定する規則とを含むことを特徴とするパケット通信網のフロー制御方法。
【請求項２】
請求項１記載のパケット通信網のフロー制御方法において、
時刻ｔにおける自ノードｉ（ｉは正の整数）より下流にあるリンクの利用可能帯域の仮定最小値li(t)は、自ノードｉと隣接ノードｉ＋１との間の伝搬遅延をdi、自ノードｉから隣接ノードｉ＋１に向かうリンクの利用可能帯域をLi(t)、隣接ノードｉ＋１から自ノードｉに通知される隣接ノードｉ＋１より下流にあるリンクの利用可能帯域の仮定最小値をli+1(t-di)としたときに、
li(t)＝min(Li(t),li+1(t-di))
で決定され、
時刻ｔにおける自ノードｉから隣接ノードｉ＋１へのパケット転送レートJi(α,t)は、隣接ノードｉ＋１から自ノードｉに指定されるパケット転送レートをri(t-di)、自ノードｉ内のパケット数をni(t)、隣接ノードｉ＋１から自ノードｉに通知される隣接ノードｉ＋１内のパケット数をni+1(t-di)、比例係数をα(>0)，Di(>0)としたときに、
自ノードから隣接ノードへのパケット転送レートを、自ノードより下流にあるリンクの利用可能帯域の仮定最小値以下の範囲内で設定するノードにおいて、
Ji(α,t)＝max(0,min(li(t),J'i(α,t)))
[但し、J'i(α,t)＝αri(t-di)−Di(ni+1(t-di)−ni(t))]
で設定され、
前記パケット通信網のこれらを除くノードにおいて、
Ji(α,t)＝max(0,min(Li(t),J'i(α,t)))
で設定されることを特徴とするパケット通信網のフロー制御方法。
【請求項３】
請求項２記載のパケット通信網のフロー制御方法において、
自ノードから隣接ノードへのパケット転送レートを、自ノードより下流にあるリンクの利用可能帯域の仮定最小値以下の範囲内で設定するノードは、前記パケット通信網の外部からパケットを受信する入口ノード（ｉ＝１）のみであり、
時刻ｔにおける自ノードｉから隣接ノードｉ＋１へのパケット転送レートJi(α,t)は、
前記パケット通信網の入口ノード（ｉ＝１）において、
J1(α,t)＝max(0,min(l1(t),J'1(α,t)))
で設定され、
前記パケット通信網の入口ノードを除くノード（ｉ≧２）において、
Ji(α,t)＝max(0,min(Li(t),J'i(α,t)))
で設定されることを特徴とするパケット通信網のフロー制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット通信網のフロー制御方法に関し、特に、パケット通信網における各ノードのパケット転送レートの設定方法に関する。
【背景技術】
【０００２】
従来、高速なネットワーク（パケット通信網）に適したフロー制御方法として、自律分散フロー制御方法が提案されている（例えば、非特許文献１〜５参照）。この自律分散フロー制御方法は、ネットワーク全体のリアルタイム情報を得るのが原理的に困難な高速ネットワークで利用されるものである。高速ネットワークにおける各ノードは、その時点で知り得る自ノードの情報とパケット送出先の隣接ノードから通知される限られた情報とに基づき、所定の規則に従って隣接ノードへのパケット転送レートを自律的に制御し、ネットワーク全体のフローを間接的に制御する。以下、従来のパケット通信網のフロー制御方法を図面を用いて説明する。
【０００３】
図１は、従来のパケット通信網のフロー制御方法を示している。あるパケットフローに沿って一次元的に接続されたネットワークにおいて、ノードｉ（自ノード）は、下流ノードｉ＋１（隣接ノード）にパケットを片方向に転送する（図中の実線矢印）。また、ノードｉは、パケット転送方向とは逆方向にフィードバック情報を送受する（図中の破線矢印）。ノードｉでの自律的なフロー制御は、自身の情報およびその時点で知り得た下流ノードｉ＋１からのフィードバック情報のみに基づいて実施される。フロー制御の枠組みは、全てのノードに共通で次の通りである。
・各ノードｉは、自身の状態情報および下流ノードｉ＋１からフィードバックされる状態情報のみに基づいて、全てのノードに共通の規則によりパケット転送レートを自律的に決定し、決定したパケット転送レートで下流ノードｉ＋１にパケットを送出する。ただし、各ノードｉは、ノードｉ内にパケットが存在しない場合、パケットを送出しない。
・各ノードｉは、全てのノードに共通の規則により自身に関する情報を生成し、フィードバック情報として上流ノードｉ−１に通知する。
・パケット転送およびフィードバック情報通知は、上り／下りともに同一の伝搬遅延を受ける。
【０００４】
以上のフロー制御の枠組みに基づき、各ノードがパケット送出先の隣接ノードと相互作用しながら自律的に動作するネットワークにおいて、各ノードは、隣接ノードへのパケット転送レートを以下のように設定する。
時刻ｔにおけるノードｉから下流ノードｉ＋１へのパケット転送レートJi(α,t)は、ノードｉと下流ノードｉ＋１との間の伝搬遅延をdi、下流ノードｉ＋１からノードｉに指定されるパケット転送レートをri(t-di)、ノードｉ内のパケット数をni(t)、下流ノードｉ＋１からノードｉに通知される下流ノードｉ＋１内のパケット数をni+1(t-di)、ノードｉから下流ノードｉ＋１に向かうリンクの利用可能帯域をLi(t)としたときに、
Ji(α,t)＝max(0,min(Li(t),J'i(α,t)))       ・・・（１）
J'i(α,t)＝αri(t-di)−Di(ni+1(t-di)−ni(t))   ・・・（２）
で設定される。なお、式（２）の右辺の第１項をドリフト項、第２項を拡散項と呼び、定数α(>0)をフロー強度係数、定数Di(>0)を拡散係数と呼ぶ。リンクの利用可能帯域は、具体的には、リンク上に存在できる最大パケット数（リンク容量）を示す。
【０００５】
ノードｉから下流ノードｉ＋１へのパケット転送レートJi(α,t)を設定するには、式（２）に示される下流ノードｉ＋１からのフィードバック情報を用いる必要がある。下流ノードｉ＋１からノードｉに到達するフィードバック情報は、伝搬遅延diを受けて、＜ri(t-di), ni+1(t-di)＞で表される。また、ノードｉから上流ノードｉ−１に指定されるパケット転送レートri-1(t)は、
ri-1(t)＝J'i(α,t)                          ・・・（３）
で決定され、ノードｉから上流ノードｉ−１に通知されるフィードバック情報は、＜ri-1(t), ni(t)＞で表される。
【非特許文献１】Masaki Aida and Chisa Takano, "Stability of autonomous decentralized flow control schemes in high-speed networks", Proceedings of IEEE ICDCS 2002 Workshop (ADSN2002), pp.63-68, Vienna, Austria, July 2, 2002.
【非特許文献２】高野知佐，会田雅樹，"自律分散フロー制御のネットワーク状態適応性の検討"，2002年電子情報通信学会ソサイエティ大会，B-7-10，2002年9月．
【非特許文献３】高野知佐，会田雅樹，"高速ネットワークにおける自律分散フロー制御の安定性の検討"，2002年電子情報通信学会総合大会，SB-4-4，2002年3月．
【非特許文献４】会田雅樹，高野知佐，栗林伸一，"リンク伝搬遅延が不均一なネットワークに対する自律分散フロー制御の適用法の検討"，電子情報通信学会  情報ネットワーク研究会，IN2003-6(2003-5)，2003年5月．
【非特許文献５】高野知佐，会田雅樹，栗林伸一，"非対称高速ネットワークにおける自律分散フロー制御の安定性"，2003年電子情報通信学会総合大会，B-7-21，2003年3月．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従来のパケット通信網のフロー制御方法は、ネットワーク内のパケット数が一定である環境（クローズドネットワーク）において、リンク上で転送中のパケットの総数を高く安定させるとともに、ノード内で処理中または処理待ちのパケットの総数を低く安定させる。リンク上の総パケット数が高いことは、ネットワークのパケット転送効率が高いことに対応する。ノード内の総パケット数が低いことは、ネットワーク内の余分なパケット数が少ないことに対応する。ノード内の総パケット数の増大は、ネットワーク内での遅延時間の増大やパケット損失の発生の原因となるため望ましくない。
【０００７】
しかしながら、従来のパケット通信網のフロー制御方法は、例えば、ノード１がネットワークの外部からパケットを受信する入口ノードであり、ネットワーク内のパケット数が変動する環境（オープンネットワーク）において、リンク上の総パケット数を高く安定させるものの、ノード内の総パケット数を低く安定させることができなかった。これは、ネットワークのノードのいずれにおいても、自ノードから隣接ノードへのパケット転送レートの設定に隣接ノードより下流にあるリンクの利用可能帯域が考慮されていないため、ネットワーク内への余分なパケットの流入を抑制できないことに起因する。
【０００８】
本発明は、このような課題を鑑みてなされたものであり、ネットワーク内のパケット数が変動する環境においても、ネットワークのパケット転送効率を高く維持でき、ネットワーク内の余分なパケット数を少なく維持できるパケット通信網のフロー制御方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
請求項１のパケット通信網のフロー制御方法は、パケット通信網の各ノードが、パケット送出先の隣接ノードから受け取る情報および自ノードの情報に基づき、所定の規則に従って自ノードから隣接ノードへのパケット転送レートを設定するパケット通信網のフロー制御方法において、前記所定の規則は、自ノードより下流にあるリンクの利用可能帯域の仮定最小値を、自ノードにパケットを送出する上流ノードに通知するために、自ノードから隣接ノードに向かうリンクの利用可能帯域とその隣接ノードより下流にあるリンクの利用可能帯域の仮定最小値とを用いて決定する規則と、前記パケット通信網のノードの少なくともいずれかにおいて、自ノードから隣接ノードへのパケット転送レートを、自ノードより下流にあるリンクの利用可能帯域の仮定最小値以下の範囲内で設定する規則とを含むことを特徴とする。
【００１０】
請求項２のパケット通信網のフロー制御方法は、請求項１記載のパケット通信網のフロー制御方法において、時刻ｔにおける自ノードｉ（ｉは正の整数）より下流にあるリンクの利用可能帯域の仮定最小値li(t)は、自ノードｉと隣接ノードｉ＋１との間の伝搬遅延をdi、自ノードｉから隣接ノードｉ＋１に向かうリンクの利用可能帯域をLi(t)、隣接ノードｉ＋１から自ノードｉに通知される隣接ノードｉ＋１より下流にあるリンクの利用可能帯域の仮定最小値をli+1(t-di)としたときに、li(t)＝min(Li(t),li+1(t-di))で決定され、時刻ｔにおける自ノードｉから隣接ノードｉ＋１へのパケット転送レートJi(α,t)は、隣接ノードｉ＋１から自ノードｉに指定されるパケット転送レートをri(t-di)、自ノードｉ内のパケット数をni(t)、隣接ノードｉ＋１から自ノードｉに通知される隣接ノードｉ＋１内のパケット数をni+1(t-di)、比例係数をα(>0)，Di(>0)としたときに、自ノードから隣接ノードへのパケット転送レートを、自ノードより下流にあるリンクの利用可能帯域の仮定最小値以下の範囲内で設定するノードにおいて、Ji(α,t)＝max(0,min(li(t),J'i(α,t)))[但し、J'i(α,t)＝αri(t-di)−Di(ni+1(t-di)−ni(t))]で設定され、前記パケット通信網のこれらを除くノードにおいて、Ji(α,t)＝max(0,min(Li(t),J'i(α,t)))で設定されることを特徴とする。
【００１１】
請求項３のパケット通信網のフロー制御方法は、請求項２記載のパケット通信網のフロー制御方法において、自ノードから隣接ノードへのパケット転送レートを、自ノードより下流にあるリンクの利用可能帯域の仮定最小値以下の範囲内で設定するノードは、前記パケット通信網の外部からパケットを受信する入口ノード（ｉ＝１）のみであり、時刻ｔにおける自ノードｉから隣接ノードｉ＋１へのパケット転送レートJi(α,t)は、前記パケット通信網の入口ノード（ｉ＝１）において、J1(α,t)＝max(0,min(l1(t),J'1(α,t)))で設定され、前記パケット通信網の入口ノードを除くノード（ｉ≧２）において、Ji(α,t)＝max(0,min(Li(t),J'i(α,t)))で設定されることを特徴とする。
【発明の効果】
【００１２】
本発明のパケット通信網のフロー制御方法では、パケット通信網のノードの少なくともいずれかにおいて（例えば、パケット通信網の入口ノードのみにおいて）、自ノードから隣接ノードへのパケット転送レートを、自ノードより下流にあるリンクの利用可能帯域のうち最小と仮定した値以下の範囲内で設定するため、ネットワーク内に流入するパケット数を適切に制御できる。この結果、ネットワーク内のパケット数が変動する環境においても、ネットワークの転送効率を高く維持でき、ネットワーク内の余分なパケット数を少なく維持できる。
【００１３】
特に、自ノードから隣接ノードへのパケット転送レートを、自ノードより下流にあるリンクの利用可能帯域のうち最小と仮定した値以下の範囲内で設定するノードがパケット通信網の入口ノードである場合、パケット通信網外からパケット通信網内へのパケット転送レートは、パケット通信網内のリンクの利用可能帯域の最小値を考慮して決定される。このため、ネットワーク内のパケット数が変動する環境において、ネットワーク内の余分なパケット数をより確実に少なく維持できる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施形態を図面を用いて説明する。
図２は、本発明のパケット通信網のフロー制御方法の一実施形態を示している。なお、本実施形態におけるフロー制御の枠組みは、前述したフロー制御の枠組みと同様である。
本実施形態では、時刻ｔにおけるノードｉ（ｉは正の整数）より下流にあるリンクの利用可能帯域の仮定最小値li(t)は、ノードｉと下流ノードｉ＋１との間の伝搬遅延をdi、ノードｉから下流ノードｉ＋１に向かうリンクの利用可能帯域をLi(t)、下流ノードｉ＋１からノードｉに通知される下流ノードｉ＋１より下流にあるリンクの利用可能帯域の仮定最小値をli+1(t-di)としたときに、
li(t)＝min(Li(t),li+1(t-di))                 ・・・（４）
で決定される。すなわち、ノードｉより下流にあるリンクの利用可能帯域の仮定最小値li(t)は、ノードｉから下流ノードｉ＋１に向かうリンクの利用可能帯域Li(t)と、下流ノードｉ＋１からノードｉに通知される下流ノードｉ＋１より下流にあるリンクの利用可能帯域の仮定最小値li+1(t-di)とを用いて、これらの小さい方に決定される。
【００１５】
時刻ｔにおけるノードｉ（自ノード）から下流ノードｉ＋１（隣接ノード）へのパケット転送レートJi(α,t)は、下流ノードｉ＋１からノードｉに指定されるパケット転送レートをri(t-di)、ノードｉ内のパケット数をni(t)、下流ノードｉ＋１からノードｉに通知される下流ノードｉ＋１内のパケット数をni+1(t-di)としたときに、ネットワークの入口ノード（ｉ＝１）において、
J1(α,t)＝max(0,min(l1(t),J'1(α,t)))       ・・・（５）
で設定され、ネットワークの入口ノードを除くノード（ｉ≧２）において、
Ji(α,t)＝max(0,min(Li(t),J'i(α,t)))       ・・・（６）
で設定される。すなわち、ノード１からノード２へのパケット転送レートJ1(α,t)は、ノード１より下流にあるリンクの利用可能帯域の仮定最小値l1(t)以下の範囲内で設定される。なお、J'i(α,t)は、前述した従来のフロー制御方法と同様に、式（２）で決定される。リンクの利用可能帯域は、具体的には、リンク上に存在できる最大パケット数を示す。
【００１６】
下流ノードｉ＋１からノードｉに到達するフィードバック情報は、伝搬遅延diを受けて、＜ri(t-di), ni+1(t-di), li+1(t-di)＞で表される。また、ノードｉから上流ノードｉ−１に指定されるパケット転送レートri-1(t)は、
ri-1(t)＝J'i(1,t)                           ・・・（７）
で決定され、ノードｉから上流ノードｉ−１に通知されるフィードバック情報は、＜ri-1(t), ni(t), li(t)＞で表される。
【００１７】
本実施形態と従来のフロー制御方法との違いは、ネットワーク（パケット通信網）の外部からパケットを受信する入口ノード（ｉ＝１）において、ノード１からノード２へのパケット転送レートJ1(α,t)を、ネットワーク内のリンクの利用可能帯域のうち一番小さいとノード１が認識する値（ノード１より下流にあるリンクの利用可能帯域の仮定最小値）以下の範囲に制限するところにある。このため、ネットワーク内に流入するパケット数は適切に制御される。この結果、ネットワーク内のパケット数が変動する環境においても、ネットワークの転送効率が高く維持され、ネットワーク内の余分なパケット数が少なく維持される。
【００１８】
ここで、本発明のフロー制御方法を従来のフロー制御方法と比較して評価する。図３は、フロー制御方法の評価に用いるネットワークモデルを示している。ネットワークモデルの条件は次の通りである。
・ノード数：60個（i＝1〜60）
・ノード間の伝搬遅延：1.0単位時間
・初期状態(時刻ｔ＝0)のネットワーク内に存在する総パケット数：6000個
・輻輳ノード（ボトルネックノード）：ノード30
・輻輳リンク（ボトルネックリンク）：ノード30からノード31に向かうリンク
・輻輳リンクを除く各リンク上に存在できる最大パケット数：Li＝100個（L30を除く）
・輻輳リンク上に存在できる最大パケット数：L30＝50個
・フロー強度係数、拡散係数：α＝1.01、Di＝0.1
また、ネットワークが混雑した場合のフロー制御の安定性を評価するために、前述の条件に加えて、ノード30の輻輳状態をつくるために、初期状態として、400個のパケットをノード30内に配置し、残りの5600個のパケットを他のノード内またはリンク上にランダムに配置した。
【００１９】
図４および図５は、本発明のフロー制御方法の評価結果をそれぞれ示している。図６および図７は、従来のフロー制御方法の評価結果をそれぞれ示している。図４および図６において、縦軸はリンク上の総パケット数を示し、横軸は時間を示している。図５および図７において、縦軸はノード内の総パケット数を示し、横軸は時間を示している。
図４および図６に示すように、本発明および従来のフロー制御方法のいずれを適用した場合にも、リンク上の総パケット数は、理論的上限値3000（50パケット/リンク×60リンク）程度で安定する。すなわち、本発明および従来のフロー制御方法は、オープンネットワークにおいて、共にネットワークのパケット転送効率を高く維持できる。
【００２０】
一方、図５に示すように、本発明のフロー制御方法を適用した場合、ノード内の総パケット数は、数百個程度で安定する。これに対して、図７に示すように、従来のフロー制御方法を適用した場合、ノード内の総パケット数は、5500個程度で安定してしまう。すなわち、本発明のフロー制御方法は、従来のフロー制御方法と比べて、ノード内の総パケット数を低く安定させることができる。換言すれば、本発明のフロー制御方法は、オープンネットワークにおいて、ネットワーク内の余分なパケット数を少なく維持できる。
【００２１】
以上、本実施形態では、ネットワークの入口ノード（ｉ＝１）において、ノード１からノード２へのパケット転送レートJ1(α,t)は、ネットワーク内におけるリンクの利用可能帯域の最小値を考慮して設定されるため、ネットワーク内に流入するパケット数を適切に制御できる。この結果、オープンネットワークにおいても、ネットワークの転送効率を高く維持でき、ネットワーク内の余分なパケット数を少なく維持できる。
【００２２】
なお、前述の実施形態では、自ノードから隣接ノードへのパケット転送レートを、自ノードより下流にあるリンクの利用可能帯域の仮定最小値以下の範囲内で設定するノードがネットワークの入口ノード（ｉ＝１）のみである例について述べた。本発明は、かかる実施形態に限定されるものではない。例えば、そのようなノードは、ネットワークの入口ノード（ｉ＝１）を除くノード（ｉ≧２）であってもよいし、ネットワーク内に複数存在してもよい。
【００２３】
以上、本発明について詳細に説明してきたが、前述の実施形態は発明の一例に過ぎず、本発明はこれに限定されるものではない。本発明を逸脱しない範囲で変形可能であることは明らかである。
【図面の簡単な説明】
【００２４】
【図１】従来のパケット通信網のフロー制御方法を示す説明図である。
【図２】本発明のパケット通信網のフロー制御方法の一実施形態を示す説明図である。
【図３】フロー制御方法の評価に用いるネットワークモデルを示す説明図である。
【図４】本発明のフロー制御方法の第１の評価結果を示す説明図である。
【図５】本発明のフロー制御方法の第２の評価結果を示す説明図である。
【図６】従来のフロー制御方法の第１の評価結果を示す説明図である。
【図７】従来のフロー制御方法の第２の評価結果を示す説明図である。
【符号の説明】
【００２５】
Ｊ  パケット転送レート
Ｌ  利用可能帯域
ｒ  パケット転送レート
ｎ  パケット数
ｌ  仮定最小値
【図１】
2005072711.tif 000003
【図２】
2005072711.tif 000004
【図３】
2005072711.tif 000005
【図４】
2005072711.tif 000006
【図５】
2005072711.tif 000007
【図６】
2005072711.tif 000008
【図７】
2005072711.tif 000009