JP4488256B2 - 通信方法、ノード及び制御プログラム - Google Patents

Description

本発明は通信方法、ノード及び制御プログラムに関し、特に、複数の経路の多重化通信の通信方法、ノード及び制御プログラムに関する。

複数の通信経路を多重化して１本の論理的な広帯域リンクを構成する技術の公知例としては、地上の通信経路のみを多重化する方法としては非特許文献１に記載されるMultilink PPPや、非特許文献２に記載されるATMにおける逆多重方式などが知られており、また、無線リンクを多重化する方法としては非特許文献２に記載されている逆多重化技術が知られている。これらはいずれも、負荷を経路間に分散することにより、単一の経路の帯域を上回る広帯域の転送リンクを提供する。

負荷分散の方法としては、非特許文献４に記載される、地上の通信経路を多重化する際には、各経路の速度に応じた重み付けを行い、周回的に送信経路を選択する重み付きランドロビン方式が広く用いられている。しかし、この方法では各経路の想定速度をあらかじめ設定する必要があるため、速度や遅延が頻繁に変動する無線リンクを含む経路の多重化に適用すると、無線リンクの平均速度などを想定速度として設定しても、想定速度と各時刻での実際の速度とが異なるために転送効率が低下する問題があった。

この問題を解決する技術として、無線リンクの多重化を想定した負荷分散の手法が非特許文献３に記載されている。この技術は、逆多重方式におけるように、各リンクの送信バッファの余裕を基に送信経路を選択する方法である。ただし、この方法も、送信ノードがボトルネックリンクに直結していて、送信バッファの余裕からボトルネックリンクの負荷が推定できる場合にのみ有効であり、複数リンクを含む経路においてはいずれかのノードがボトルネックに直結できなくなるので、双方向の通信には適用できない問題があった。

この問題を解決する負荷分散手法としては、各経路の速度及び遅延の推定結果を両ノードが交換して、その推定結果より各リンクの予測遅延を比較して送信経路を選択する、非特許文献５に記載されるMobile InverseMux技術が知られている。
RFC1990 Langdon, Robin D., "Imuxing ATM, Bit by Bit." Larscom white paper, 1997. 磯村学、今井尚樹、吉原貴仁、堀内浩規、"モバイルルータのための異種通信メディアの逆多重方式の性能評価"、FIT2004(第３回情報科学技術フォーラム)、論文M-070、pp.239-240 (2004) Cisco Systems, "Load Balancing with Cisco Express Forwarding," Cisco Application Note, Jan.1998 T. Nakata et al.,"Efficient bundling of heterogeneous radio resources for broadband Internet access from moving vehicles," in proceedings of Global Mobile Congress 2004, Oct. 11-13 2004, Shanghi, China.

以上述べた従来技術はいずれも、負荷を経路間に分散することにより、単一の経路では実現できない大容量の転送リンクを提供する。

速度が安定している地上リンクのみからなる経路の場合は、従来技術の重みつきラウンドロビン方式による負荷分散を用いて各経路への負荷を均等にできるが、それぞれの経路の遅延が異なる場合、多重化リンク全体としての遅延は、最も遅延の大きい経路の遅延と等しくなる。このため、多重化対象の経路のうち遅延の小さい経路に比べて多重化リンクの遅延は大きくなる。その結果、多重化により帯域は拡大するという性能向上が得られる一方で、遅延が増大するという性能劣化が生じてしまう問題があった。

また、無線リンクを含む経路間に従来技術のMobile InverseMuxを用いて負荷分散を行う場合、予測遅延の最も小さい経路にパケットを送信している限りは多重化による遅延の増大はないが、そうすると遅延の大きい経路に負荷をかけるのは遅延の小さい経路に、両経路の遅延差分以上の負荷をかかった場合のみになり、帯域拡大の効果が表れるのもそのような場合に限られる。つまり、経路間の遅延差が大きい場合に、負荷が分散されにくくなる。この問題を避けるため、各経路に許容遅延の最大値を設定し、もともと遅延の小さい経路にはこの許容遅延も小さく設定することで、遅延の大きい経路にも負荷が分散されやすくすることも可能であるが、この場合、重みつきラウンドロビン方式の場合と同様、多重化による遅延の増加が生じる。

このように、従来技術はいずれも、遅延の異なる経路を多重化する場合に、経路間の負荷の最適配分と、多重化による遅延増加の防止とが両立できない問題があった。

そこで、本発明は上記課題に鑑みて発明されたものであって、その目的は経路間の負荷の最適配分と、多重化による遅延増加の防止とを両立することができる技術を提供することにある。

上記課題を解決する第１の発明は、少なくとも第１の経路と第２の経路とを含む複数経路を利用可能な２ノード間の通信方法であって、第２の経路の輻輳を予測または検出すると、第１のノードに到着した２つ以上のパケットのうち、到着時刻の遅い第２のパケットを第１の経路より送信した後、到着時刻の早い第１のパケットを第２の経路から送信することを特徴とする。

上記課題を解決する第２の発明は、上記第１の発明において、前記第１のパケットの前記第２の経路からの送信は、前記第２の経路の輻輳の解消を予測または検出してから行うことを特徴とする。

上記課題を解決する第３の発明は、上記第１又は第２の発明において、前記輻輳の予測又は輻輳の解消の予測は、各経路の送信履歴に基づき決定されることを特徴とする。

上記課題を解決する第４の発明は、上記第１又は第２の発明において、前記輻輳の予測又は輻輳の解消の予測は、各経路の推定速度に基づき決定されることを特徴とする。

上記課題を解決する第５の発明は、第１の経路と第２の経路とを含む複数経路を利用可能な２ノード間の通信方法であって、第１のノードに到着した複数のパケットを第２のノードに送信する際、各経路の遅延および速度の推定値から、前記複数のパケットの前記第２のノードへの到着予測時刻の順番が、前記複数のパケットの前記第１のノードに到着した時刻の順番と等しくなるように、前記複数のパケットの送信経路を決定し、前記複数のパケットのうち各経路に輻輳を起こさずに第２のノードに到着すると予測されるパケットのみを、決定した送信経路に送信することを特徴とする。

上記課題を解決する第６の発明は、上記第５の発明において、前記到着予測時刻又は前記輻輳の判断は、各経路の送信履歴に基づき行われることを特徴とする。

上記課題を解決する第７の発明は、上記第５の発明において、前記到着予測時刻又は前記輻輳の判断は、各経路の推定速度に基づき行われることを特徴とする。

上記課題を解決する第８の発明は、少なくとも第１の経路と第２の経路とを含む複数経路を利用可能なノードであって、各経路の遅延および速度の推定値に基づいて、受信した複数のパケットの他ノードへの到着予測時刻を求め、前記到着予測時刻に基づいて、前記複数のパケットの前記他ノード到着順番が、前記複数のパケットの到着順番と等しくなるように、前記複数のパケットの送信経路を決定する手段を有することを特徴とする。

上記課題を解決する第９の発明は、上記第８の発明において、前記複数のパケットのうち各経路に輻輳を起こさずに前記他ノードに到着すると予測されるパケットのみを、決定した送信経路に送信する手段を有することを特徴とする。

上記課題を解決する第１０の発明は、上記第８又は第９の発明において、前記到着予測時刻又は前記輻輳の判断は、各経路の送信履歴に基づき行われることを特徴とする。

上記課題を解決する第１１の発明は、上記第８又は第９の発明において、前記到着予測時刻又は前記輻輳の判断は、各経路の推定速度に基づき行われることを特徴とする。

上記課題を解決する第１２の発明は、少なくとも第１の経路と第２の経路とを含む複数経路を利用可能なノードの制御プログラムであって、各経路の遅延および速度の推定値に基づいて、受信した複数のパケットの他ノードへの到着予測時刻を求め、前記到着予測時刻に基づいて、前記複数のパケットの前記他ノード到着順番が、前記複数のパケットの到着順番と等しくなるように、前記複数のパケットの送信経路を決定する処理をノードに実行させることを特徴とする。

上記課題を解決する第１３の発明は、上記第１２の発明において、前記複数のパケットのうち各経路に輻輳を起こさずに前記他ノードに到着すると予測されるパケットのみを、決定した送信経路に送信する処理をノードに実行させることを特徴とする。

上記課題を解決する第１４の発明は、上記第１２又は第１３の発明において、前記到着予測時刻又は前記輻輳の判断は、各経路の送信履歴に基づき行われることを特徴とする。

上記課題を解決する第１５の発明は、上記第１２又は第１３の発明において、前記到着予測時刻又は前記輻輳の判断は、各経路の推定速度に基づき行われることを特徴とする。

以上に述べた課題を解決するために、本発明は、各経路の遅延および速度の推定値から、送信する各パケットの予定送信経路を、受信ノードへの到着予測時刻の順番が送信ノードに到着した時刻の順番と等しくなるように決定し、そのうち各経路に許容される最大遅延以内に到着すると予測されるパケットのみを送信する。

例えば、先に送信ノードに到着したパケット１および後に到着したパケット２を送信する際、多重化対象経路のうち低速な第１の経路の予測遅延が高速な第２の経路の予測遅延よりも大きいが、第２の経路の予測遅延は最大遅延を越えている場合、第１の経路にパケット２を送信し、第２の経路の輻輳状態（予測遅延が最大遅延を超えている状態）が解消してから第２の経路よりパケット１を送信する。このようにすることで、送信ノードからのパケット送信順序が送信ノードへの到着順と異なるが、受信側ノードの到着順序はパケット１が先でパケット２が後と、送信ノードへの到着順序と同じとなり、またパケット１，２ともに高速な経路２のみを用いた場合と同等以下の遅延で到着し、かつ経路１と２の双方に負荷が分散される。

本発明によれば、経路間の負荷の最適配分と、多重化による遅延増加の防止とを両立することができる。

図１は実施の形態の一構成図である。 図２は実施の形態の一構成図である。 図３はスケジューリング部２０２の動作フローチャート（SDLプロセスグラフ）である。 図４は経路選択部２０３が従う動作フローチャート（SDLプロセスグラフ）である。 図５は実施の形態を説明する為の図である。 図６は実施の形態を説明する為の図である。

符号の説明

１０１、１０２ 通信ノード
２０１ 入力キュー
２０２ スケジューリング部
２０３ 経路選択部
２０４ パケット送信部
２０５ 記憶部
２０６ パケット受信部
２０７ パケット解析部

本発明の実施の形態を説明する。

本実施の形態は、複数の通信経路を利用して通信する２つのノード間で実施される。図１に示される例では、通信ノード１０１はパケット送信部２０４とパケット受信部２０６を１個ずつ持ち、一方通信ノード１０２はパケット送信部２０４とパケット受信部２０６を２個ずつ持つ。

ノード１０１からノード１０２までの経路は、ノード１０１のパケット送信部２０４を起点とし、ネットワーク４００を経由しノード１０２のパケット受信部２０６−１を終点とする経路と、ノード１０１のパケット送信部２０４を起点とし、ネットワーク４００を経由しノード１０２のパケット受信部２０６−２を終点とする経路との２つがある。またノード１０２からノード１０１までの経路は、ノード１０２のパケット送信部２０４−１を起点とし、ネットワーク４００を経由しノード１０１のパケット受信部２０６を終点とする経路と、ノード１０２のパケット送信部２０４−２を起点とし、ネットワーク４００を経由しノード１０１のパケット受信部２０６を終点とする経路との２つがある。このように、ノード１０１のパケット送受信部が１対であっても対向するノード１０２が複数のパケット送受信部を持てば複数経路が構成可能であるが、以降説明する実施例は双方のノードが複数のパケット送受信部を持つ図２に示される構成でも同様に実施可能である。

双方のノードのパケット解析部２０７は、各経路の状態をパケットの到着時刻や到着間隔から解析し、相手ノードに経路状態の通知を送信する。一方、通知を受信した場合には、通知内容に基づく最新の経路状態を記憶部２０５に記憶する。スケジューリング部２０２は、記憶部２０５に記録された経路情報に基づきパケット送信順序、パケット送信時刻及び各パケットの送信に用いる経路を決定して経路選択部に通知する。経路選択部２０３は、スケジューリング部２０２からの通知に基づき入力パケットを入力キュー２０１から取り出し、それぞれに対しスケジューリング部が指定した時刻に、指定した経路から送信する。

次に、ノード１０１の入力キュー２０１に複数のパケットがある場合の、スケジューリング部２０２の動作を説明する。ノード１０１のスケジューリング部２０２は、図３の動作フローチャート（SDLプロセスグラフ）に従い動作する。つまり、経路選択部からのスケジューリング依頼により以下の動作が起動される。

まず、経路選択部２０３よりｊ個のパケットのスケジューリング依頼を受信すると（Ｓｔｅｐ１００）、ｉ＝１として（Ｓｔｅｐ１０１）スケジューリング依頼された各パケットにつき、入力キュー２０１への到着順に、各経路から送信した場合の予測受信時刻を求める（Ｓｔｅｐ１０２）。ここで予測受信遅延は、パケットの末尾が相手ノード１０２に到着すると予想される時刻である。その結果、最も予測受信時刻が小さい経路を当該パケットの送信経路とする（Ｓｔｅｐ１０３）。図５は、最初のパケット３００−１の到着時刻予測の例を示している。パケット先頭の予測到着時刻は経路１の方が早いにもかかわらず、経路２の速度は経路１よりも大きいため、パケット末尾の予測到着時刻、つまり予測受信時刻が早い経路２が送信経路となる。入力キュー２０１への到着順が２番目以降のパケットに関しては、より到着順の若いパケットが全て以上の手順により決められた送信経路から送信されたものと仮定して、受信時刻の予測を行う。

図６は、２番目のパケット３００−２の受信時刻予測の例を示している。ここでは３００−１の送信により経路２の遅延が増加したため、予測受信時刻は経路１の方が早く、したがって経路１がパケット３００−２の送信経路となる。

次に、各経路の輻輳状態の確認および予測を行い、送信可能時刻を求める（Ｓｔｅｐ１０４）。なお輻輳状態とは、経路の予測遅延が許容値以上であるため即時にパケットを送信できない状態を指している。遅延の許容値は予め設定するか、回線状態によりスケジューリング部２０２が決定する。図６では、経路２が送信すべき３００−１の予測受信時刻が現在より経路２の許容遅延以上未来であるため、経路２は輻輳状態である。パケット３００−１の予測遅延、すなわちパケット３００−１の予測受信時刻と送信時刻の差が経路２の遅延許容値以下となるためには、送信時刻がt1以降である必要がある。このt1を、パケット３００−１の送信可能時刻とする。一方パケット３００−２の送信経路である経路１は輻輳状態にないため、送信可能時刻は即時となる。

スケジューリング部２０２は、ｉを１インクリメントしながら（Ｓｔｅｐ１０７）、ｉ＝ｊとなるまで以上の処理を行い、ｉ＝ｊとなると（Ｓｔｅｐ１０５）、入力キュー２０１内の各パケットの送信経路および送信可能時刻を経路選択部２０３に通知する（Ｓｔｅｐ１０６）。

次に、経路選択部２０３の動作について説明する。

スケジューリング部２０２から通知を受けた経路選択部２０３は、各パケットを通知された送信可能時刻に、通知された送信経路に対応するパケット送信部２０４から送信する。このとき経路選択部２０３が従う動作フローチャート（SDLプロセスグラフ）を図４に示す。

スケジューリング部２０２にスケジューリング依頼済みの経路選択部２０３はactive状態にあり、このときスケジューリング部２０２よりｋ個のパケットの送信経路及び送信可能時刻の通知を受信すると（Ｓｔｅｐ２００）、ａ＝１を初期値として（Ｓｔｅｐ２０１）、送信可能時間がａ番目に早いパケットを入力キュー２０１から取り出す（Ｓｔｅｐ２０２）。そして、送信可能時間がａ番目に早いパケットの送信可能時間まで待機し（Ｓｔｅｐ２０３）、送信可能時間がａ番目に早いパケットを、スケジューリング部から指定された送信経路に対応するパケット送信部２０４に送信する（Ｓｔｅｐ２０４）。

以上の処理を、ａをインクリメントし（Ｓｔｅｐ２０５）、ａがｋとなるまで行う。

ａがｋとなり（Ｓｔｅｐ２０６）、入力キュー２０１にパケットがなければ（Ｓｔｅｐ２０７）、idle状態となり次のパケット到着を待機する（Ｓｔｅｐ２０８）。

入力キュー２０１にパケットがある（Ｓｔｅｐ２０７）、又は、入力キュー２０１より新規パケットの受信通知を受けた場合（Ｓｔｅｐ２０９）は、スケジューリング依頼をスケジューリング部２０２に送信する（Ｓｔｅｐ２１０）。

なお、スケジューリング依頼するパケットの数は入力キュー２０１にあるパケット数以下の任意の数である。例えば入力キュー２０１にあるパケットの全数としてもよいし、任意の上限を設けてもよい。

以上の動作により２つのパケットを送信する図６の例では、先に入力キュー２０１に到着したパケット３００−１の方がパケット３００−２よりも後から送信されるが、相手ノードの受信予想順序は入力キュー２０１に到着した順序と同じである。つまりノード１０１のパケット送信部２０４から出力される際にはノード１０１に到着した順序の逆順であるが、ネットワーク４００内でパケットの順序再逆転が起こり、ノード１０２での到着順序はノード１０１での到着順序と同様になると予測している。このときいずれのパケットの遅延も経路１のみ、または経路２のみを用いた場合と同等以下であり、かつ両経路に負荷が分散されている。

以上では本発明の動作を経路が２本使用可能な構成を例に説明したが、図３、図４に示したアルゴリズムは使用可能な経路が３本以上ある場合にも適用可能である。その場合装置の構成は、例えば、図２に示されるものになり、図２のノード１０１およびノード１０２の間を転送されるパケットの遅延は両ノード間のいずれの経路のみを用いた場合と同等以下となり、かつ各経路への負荷分散による帯域拡大が実現される。

また、上述した実施の形態では、各部をハードウェアで構成したが、各部の動作を行わせる制御プログラムにより動作する情報処理装置により、構成することも可能である。

Claims (13)

1. 少なくとも第１の経路と第２の経路とを含む複数経路を利用可能な２ノード間の通信方法であって、
   第２の経路の輻輳を予測または検出すると、第１のノードに到着した２つ以上のパケットのうち、到着時刻が遅くかつ第１のノードの受信キューの先頭から２番目以降にキューイングされた第２のパケットを第１の経路より送信した後、到着時刻が早くかつ第１のノードの受信キューの先頭にキューイングされた第１のパケットを第２の経路から送信することを特徴とする通信方法。
2. 前記第１のパケットの前記第２の経路からの送信は、前記第２の経路の輻輳の解消を予測または検出してから行うことを特徴とする請求項１記載の通信方法。
3. 前記輻輳の予測又は輻輳の解消の予測は、各経路の送信履歴に基づき決定されることを特徴とする請求項１に記載の通信方法。
4. 前記輻輳の予測又は輻輳の解消の予測は、各経路の推定速度に基づき決定されることを特徴とする請求項１に記載の通信方法。
5. 第１の経路と第２の経路とを含む複数経路を利用可能な２ノード間の通信方法であって、
   第１のノードに到着し、受信キューにキューイングされた複数のパケットを第２のノードに送信する際、各経路の遅延および速度の推定値から、前記複数のパケットの前記第２のノードへの到着予測時刻の順番が、前記複数のパケットの前記第１のノードに到着した時刻の順番と等しくなるように、前記複数のパケットの送信経路を決定し、第１のノードの受信キューから、前記複数のパケットのうち各経路に輻輳を起こさずに第２のノードに到着すると予測されるパケットを、受信キュー内の順序によらず選択し、選択したパケットのみを、前記決定した送信経路に送信することを特徴とする通信方法。
6. 前記到着予測時刻又は前記輻輳の判断は、各経路の送信履歴に基づき行われることを特徴とする請求項５に記載の通信方法。
7. 前記到着予測時刻又は前記輻輳の判断は、各経路の推定速度に基づき行われることを特徴とする請求項５に記載の通信方法。
8. 少なくとも第１の経路と第２の経路とを含む複数経路を利用可能なノードであって、
   各経路の遅延および速度の推定値に基づいて、受信キューにキューイングされた複数のパケットの他ノードへの到着予測時刻を求め、前記到着予測時刻に基づいて、前記複数のパケットの前記他ノード到着順番が、前記複数のパケットの到着順番と等しくなるように、前記複数のパケットの送信経路を決定し、前記複数のパケットのうち各経路に輻輳を起こさずに前記他ノードに到着すると予測されるパケットを、受信キュー内の順序によらず選択し、選択したパケットのみを、前記決定した送信経路に送信する手段を有することを特徴とするノード。
9. 前記到着予測時刻又は前記輻輳の判断は、各経路の送信履歴に基づき行われることを特徴とする請求項８に記載のノード。
10. 前記到着予測時刻又は前記輻輳の判断は、各経路の推定速度に基づき行われることを特徴とする請求項８に記載のノード。
11. 少なくとも第１の経路と第２の経路とを含む複数経路を利用可能なノードの制御プログラムであって、
    各経路の遅延および速度の推定値に基づいて、受信キューにキューイングされた複数のパケットの他ノードへの到着予測時刻を求め、前記到着予測時刻に基づいて、前記複数のパケットの前記他ノード到着順番が、前記複数のパケットの到着順番と等しくなるように、前記複数のパケットの送信経路を決定し、前記複数のパケットのうち各経路に輻輳を起こさずに前記他ノードに到着すると予測されるパケットを、受信キュー内の順序によらず選択し、選択したパケットのみを、前記決定した送信経路に送信する処理をノードに実行させることを特徴とする制御プログラム。
12. 前記到着予測時刻又は前記輻輳の判断は、各経路の送信履歴に基づき行われることを特徴とする請求項１２に記載の制御プログラム。
13. 前記到着予測時刻又は前記輻輳の判断は、各経路の推定速度に基づき行われることを特徴とする請求項１２に記載の制御プログラム。

Images