(57)【特許請求の範囲】
【請求項１】
負荷分散方法であって、
複数の通信経路を選択可能な２ノード間において、送信側ノードにおいて入力されるパケットごとに、選択可能な各経路の経路状態を監視し、その経路状態の経路状態情報と、この経路状態情報が有効となる時刻又はパケットの識別情報を記憶するステップと、
経路状態情報と、前記経路状態情報が有効となる時刻以降のパケットの送信履歴、又は前記送信済みパケットの識別情報で特定されるパケットの送信以降のパケットの送信履歴に基づいて、各経路におけるパケットの到着予想時刻を推定するステップと、
前記推定された到着予想時刻に基づいて、経路の選択、又は選択優先度の更新を行うステップと
を有することを特徴とする負荷分散方法。
【請求項２】
前記経路状態情報は、経路の遅延を含むことを特徴とする請求項１に記載の負荷分散方法。
【請求項３】
前記経路状態情報は、経路の通信速度を含むことを特徴とする請求項１に記載の負荷分散方法。
【請求項４】
前記経路状態情報は、経路の負荷を含むことを特徴とする請求項１に記載の負荷分散方法。
【請求項５】
経路の選択又は選択優先度の更新に際し、各経路の経路状態情報が更新されると、更新以前に送信されたパケットに関する送信コスト計算結果に修正を加えることを特徴とする請求項１に記載の負荷分散方法。
【請求項６】
各経路の送信コスト計算結果の修正に際し、最新の経路状態情報が有効となる最初の送信済パケット以前の履歴を破棄することを特徴とする請求項５に記載の負荷分散方法。
【請求項７】
パケットを送信する経路として、受信側ノードでの受信完了時刻の推定値が最も早い経路を選択することを特徴とする請求項１に記載の負荷分散方法。
【請求項８】
パケットを送信する経路として、受信側ノードで特定時刻までに受信完了できるデータ量の推定値が最大の経路を選択することを特徴とする請求項１に記載の負荷分散方法。
【請求項９】
各経路につき、推測される現在の経路状態に応じてデータの送信を中断することを特徴とする請求項１に記載の負荷分散方法。
【請求項１０】
前記データ送信中断の基準が、推定受信完了時刻が特定の値以上であることを特徴とする請求項９に記載の負荷分散方法。
【請求項１１】
経路選択又は送信中断の判断を、送信データの属性ごとに異なるポリシーにより行うことを特徴とする請求項１に記載の負荷分散方法。
【請求項１２】
受信パケットの宛先アドレスに対応する通信インターフェースを、通信インターフェースのアドレスと、その通信インターフェースを経由して到達する宛先アドレスとが関連付けられたテーブルから選択し、前記受信パケットに送信元アドレス又は通信インターフェースを指定する情報がある場合には、前記送信元アドレス又は通信インターフェースに対応する通信インターフェースを前記選択された通信インターフェースから選択し、前記受信パケットに送信元アドレス又は通信インターフェースの情報がない場合には、前記選択された通信インターフェースの中から任意の通信インターフェースを選択し、選択した通信インターフェースに前記受信パケットを送出することを特徴とする請求項１に記載の負荷分散方法。
【請求項１３】
パケットを送信する経路を複数選択可能なノードであって、
送信側ノードにおいて入力されるパケットごとに、選択可能な各経路の経路状態を監視し、その経路状態の経路状態情報と、この経路状態情報が有効となる時刻又はパケットの識別情報とを監視する監視手段と、
前記経路状態情報と、この経路状態情報が有効となる以降のパケットの送信履歴とが記憶された記憶手段と、
前記経路状態情報と、この経路状態情報が有効となる以降のパケットの送信履歴に基づいて、各経路におけるパケットの到着予想時刻を推定し、前記推定された到着予想時刻に基づいて、経路の選択、又は選択優先度の更新を行うスケジューリング手段と
を有することを特徴とするノード。
【請求項１４】
前記経路状態情報は、経路の遅延を含むことを特徴とする請求項１３に記載のノード。
【請求項１５】
前記経路状態情報は、経路の通信速度を含むことを特徴とする請求項１３に記載のノード。
【請求項１６】
前記経路状態情報は、経路の負荷を含むことを特徴とする請求項１３に記載のノード。
【請求項１７】
前記スケジューリング手段は、経路の選択又は選択優先度の更新に際し、各経路の経路状態情報が更新されると、更新以前に送信されたパケットに関する送信コスト計算結果に修正を加えることを特徴とする請求項１３に記載のノード。
【請求項１８】
前記スケジューリング手段は、各経路の送信コスト計算結果の修正に際し、最新の経路状態情報が有効となる最初の送信済パケット以前の履歴を破棄することを特徴とする請求項１７に記載のノード。
【請求項１９】
前記スケジューリング手段は、パケットを送信する経路として、受信側ノードでの受信完了時刻の推定値が最も早い経路を選択することを特徴とする請求項１３に記載のノード。
【請求項２０】
前記スケジューリング手段は、パケットを送信する経路として、受信側ノードで特定時刻までに受信完了できるデータ量の推定値が最大の経路を選択することを特徴とする請求項１３に記載のノード。
【請求項２１】
前記スケジューリング手段は、各経路につき、推測される現在の経路状態に応じてデータの送信を中断することを特徴とする請求項１３に記載のノード。
【請求項２２】
前記データ送信中断の基準が、推定受信完了時刻が特定の値以上であることを特徴とする請求項２１に記載のノード。
【請求項２３】
前記スケジューリング手段は、経路選択又は送信中断の判断を、送信データの属性ごとに異なるポリシーにより行うことを特徴とする請求項１３に記載のノード。
【請求項２４】
通信インターフェースのアドレスと、その通信インターフェースを経由して到達する宛先アドレスとが関連付けられたテーブルと、
送信するパケットの宛先アドレスに対応する通信インターフェースを前記テーブルから選択し、前記送信するパケットに送信元アドレス又は通信インターフェースを指定する情報がある場合には、前記送信元アドレス又は通信インターフェースに対応する通信インターフェースを前記選択された通信インターフェースから選択し、選択した通信インターフェースに前記送信するパケットを送出するルーティング手段と
を有することを特徴とする請求項１３に記載のノード。
【請求項２５】
パケットを送信する経路を複数選択可能なノードの制御プログラムであって、
前記プログラムはノードを、
送信側ノードにおいて入力されるパケットごとに、選択可能な各経路の経路状態を監視し、その経路状態の経路状態情報と、この経路状態情報が有効となる時刻又はパケットの識別情報とを監視する監視手段と、
前記経路状態情報と、この経路状態情報が有効となる以降のパケットの送信履歴に基づいて、各経路におけるパケットの到着予想時刻を推定し、前記推定された到着予想時刻に基づいて、経路の選択、又は選択優先度の更新を行うスケジューリング手段と
して機能させることを特徴とするノードの制御プログラム。
【請求項２６】
前記経路状態情報は、経路の遅延を含むことを特徴とする請求項２５に記載のノードの制御プログラム。
【請求項２７】
前記経路状態情報は、経路の通信速度を含むことを特徴とする請求項２５に記載のノードの制御プログラム。
【請求項２８】
前記経路状態情報は、経路の負荷を含むことを特徴とする請求項２５に記載のノードの制御プログラム。
【請求項２９】
前記制御プログラムは、前記スケジューリング手段を、経路の選択又は選択優先度の更新に際し、各経路の経路状態情報が更新されると、更新以前に送信されたパケットに関する送信コスト計算結果に修正を加えるように機能させることを特徴とする請求項２５に記載のノードの制御プログラム。
【請求項３０】
前記制御プログラムは、前記スケジューリング手段を、各経路の送信コスト計算結果の修正に際し、最新の経路状態情報が有効となる最初の送信済パケット以前の履歴を破棄するように機能させることを特徴とする請求項２９に記載のノードの制御プログラム。
【請求項３１】
前記制御プログラムは、前記スケジューリング手段を、パケットを送信する経路として、受信側ノードでの受信完了時刻の推定値が最も早い経路を選択するように機能させることを特徴とする請求項２５に記載のノードの制御プログラム。
【請求項３２】
前記制御プログラムは、前記スケジューリング手段を、パケットを送信する経路として、受信側ノードで特定時刻までに受信完了できるデータ量の推定値が最大の経路を選択するように機能させることを特徴とする請求項２５に記載のノードの制御プログラム。
【請求項３３】
前記制御プログラムは、前記スケジューリング手段を、各経路につき、推測される現在の経路状態に応じてデータの送信を中断するように機能させることを特徴とする請求項２５に記載のノードの制御プログラム。
【請求項３４】
前記データ送信中断の基準が、推定受信完了時刻が特定の値以上であることを特徴とする請求項３３に記載のノードの制御プログラム。
【請求項３５】
前記制御プログラムは、前記スケジューリング手段を、経路選択又は送信中断の判断を、送信データの属性ごとに異なるポリシーにより行うように機能させることを特徴とする請求項２５に記載のノードの制御プログラム。
【請求項３６】
前記制御プログラムは、送信するパケットの宛先アドレスに対応する通信インターフェースを、通信インターフェースのアドレスと、その通信インターフェースを経由して到達する宛先アドレスとが関連付けられたテーブルから選択し、前記送信するパケットに送信元アドレス又は通信インターフェースを指定する情報がある場合には、前記送信元アドレス又は通信インターフェースに対応する通信インターフェースを前記選択された通信インターフェースから選択し、選択した通信インターフェースに前記送信するパケットを送出するルーティング手段として機能させることを特徴とする請求項２５に記載のノードの制御プログラム。
【請求項３７】
送信パケットの到着時刻又は受信完了時刻を推定する送信パケットの時刻推定方法であって、
送信側ノード側から送信される送信パケットにパケットを識別するパケット識別情報を付加して送信するステップと、
送信側ノード側にて、送信したパケットの送信履歴をパケット識別情報と共に記憶するステップと、
受信ノード側にて、経路状態の情報を、この経路状態時に受信した最後のパケットのパケット識別情報を含めて送信側ノードに送信するステップと、
送信側ノード側にて、前記経路状態と、前記経路状態の情報に含まれるパケット識別情報で特定されるパケット以降に送信されたパケットの送信履歴とに基づいて、送信しようとするパケットの到着時刻又は受信完了時刻を推定するステップと
を有することを特徴とする送信パケットの時刻推定方法。
【請求項３８】
ノードであって、
送信パケットにパケットを識別するパケット識別情報を付加して送信する手段と、
送信したパケットの送信履歴をパケット識別情報と共に記録する手段と、
受信側から送信されてくる経路状態の情報を受信し、この経路状態と、この経路状態が有効となるパケット以降に送信されたパケットの送信履歴とに基づいて、送信しようとするパケットの到着時刻又は受信完了時刻を推定する手段と
を有することを特徴とするノード。
【請求項３９】
パケットを送信するノードの制御プログラムであって、
前記制御プログラムはノードを、
送信パケットにパケットを識別するパケット識別情報を付加して送信する手段と、
送信したパケットの送信履歴をパケット識別情報と共に記録する手段と、
受信側から送信されてくる経路状態の情報を受信し、この経路状態と、この経路状態が有効となるパケット以降に送信されたパケットの送信履歴とに基づいて、送信しようとするパケットの到着時刻又は受信完了時刻を推定する手段と
して機能させることを特徴とするノードの制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は複数の通信経路を利用可能な２ノード間の通信方式に関し、特に送信ノードによる経路間負荷分散の技術に関する。
【背景技術】
【０００２】
２ノード間に複数の通信経路が存在する場合、送信側ノードがトラフィックを各経路に分散して入力し、受信側で各経路からのトラフィックを再統合することにより、単一の経路を用いた場合よりも原理的に高い転送速度が得られる。この仕組みは、経路を組み合わせて、一つの論理的な経路とする技術であり、代表的なものとしてInverse Multiplexingがあり、複数の低速リンクから論理的な広帯域回線を得る目的で利用される。データ通信への適用例としては、ATM回線の多重化や、PPPリンクの多重化プロトコルであるMultilink PPPなどが挙げられる。【０００３】
Inverse Multiplexingに代表されるような、経路を組み合わせて一つの論理的な経路とする技術におけるトラフィック分散方式としては、例えば各経路に順番にパケットまたはフラグメントを送信するラウンドロビン方式が広く用いられている（例えば、非特許文献１）。この方法は各経路の速度がほぼ同一で一定な場合には有効であるが、経路ごとに速度の不均衡がある場合には２ノード間の転送速度が最も低速な経路に律速されてしまう問題があった。【０００４】
この問題に対応する方法としては各経路の利用頻度を速度に応じて制御する重みつきラウンドロビンが知られており、経路を組み合わせて一つの論理的な経路とする技術に対応したルータ製品等に実装されている。またCisco社等の製品では、入力パケットをハッシングして出力経路を決め、最適負荷分散を図る方法も実装されている。これらの情報は各社の公開文書に記されている（例えば、非特許文献２）。【０００５】
以上はいずれも経路が有線リンクのみから成る場合を想定した公知技術である。【０００６】
一方、経路を組み合わせて一つの論理的な経路とする技術において、経路が無線リンクを含む場合についても提案されている。提案されている方式では、入力パケットをフラグメントに分割して各経路に割り当てるが、そのフラグメントの大きさの比率を送信時の各経路の速度のみに応じて変更するものである。（例えば、非特許文献３、特許文献６）。【０００７】
また、複数経路が選択可能な通信方式において、各経路の状態を監視し、その経路状態や、遅延時間等を考慮して経路を選択する技術も提案されている（例えば、特許文献１、特許文献２、特許文献３、特許文献４、特許文献５）。
【特許文献１】特開２０００−４９８６２号公報
【特許文献２】特開２００１−３０８９１７号公報
【特許文献３】特開２００１−３３３１００号公報
【特許文献４】特開２００２−１７６４４１号公報
【特許文献５】特開昭５８−２７４４９号公報
【特許文献６】特開２０００−２１６８１５号公報
【非特許文献１】”Striping Within the Network Subsystem,” IEEE Network, July/August 1995
【非特許文献２】Cisco Systems, ”Load Balancing with Cisco Express Forwarding,” Cisco Application Note, Jan.1998
【非特許文献３】”Adaptive Inverse Multiplexing for Wide-Area Wireless Networks,” Snoeren et al, Proceedings of IEEE GlobeCom, Dec. 1999
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上述した２ノード間の経路中に無線リンクを含む場合の従来の技術では、送信ノードが送信経路を選択する際に選択基準として各経路の速度や遅延を参照する。しかし、それらが動的に変動する無線リンクを含む経路については経路状態の測定誤差が累積しやすいので、送信しようとするパケットが受信ノード側に到着する時刻や受信完了する時刻の正確な予測が困難であった。その結果、その予測結果に基づいて経路選択を行うと、実際には速度が著しく低下している経路を選択し、多重化効率が低下するという問題があった。【０００９】
以下に、従来技術による送信パケットの到着時刻や受信完了時刻を予測する技術について、図８を用いて説明する。【００１０】
図８中700-1,
700-2, 700-3は送出されるデータパケットであり、その送信側ノードでのパケットの送信履歴（実線）と受信側ノードでのパケットの受信履歴（実線）およびパケットの到着及び受信完了時刻の予測（点線）がそれぞれ時間軸上で示されている。【００１１】
まず、実際のパケットの送受信であるが、送信側ノード側から時刻T1にデータパケット700-1の送信が開始され、時刻T2に送信が完了している。そして、受信側ノードで、パケット700-1は、時刻T3より受信が開始され、時刻T5に受信が完了している。【００１２】
その後、送信側ノード側から時刻T4にデータパケット700-2の送信が開始され、時刻T7に送信が完了している。そして、受信側ノード側では、通信速度の低下により、データパケット700-2は、時刻T6より受信が開始され、時刻T11に受信が完了している。【００１３】
更に、送信側ノード側から時刻T8にデータパケット700-3の送信が開始され、時刻T9に送信が完了している。そして、受信側ノード側では、データパケット700-3が、時刻T12より受信が開始され、時刻T13に受信が完了している。【００１４】
一方、従来技術では、データパケット700-1の受信完了時に受信ノードから発行される伝送速度等の経路状態の情報に基づいて、パケットの到着時刻及び受信完了時刻を予測している。【００１５】
例えば、図８において、送信ノードは、受信ノードからの経路状態の情報を時刻TXに受信している。送信ノード側では、データパケット700-3の到着時刻及び受信完了時刻の予測に際して、時刻TXに受信した経路状態の情報を用いる。その結果、伝送遅延I1等を知ることができ、データパケット700-3の送信時刻T8に伝送遅延I1を加えた時刻T10を、データパケット700-3の到着時刻と予測していった。【００１６】
しかしながら、実際のデータパケット700-3の到着時刻は時刻T12であり、予測した到着時刻T10とは、時間ID分誤差が生じている。【００１７】
このように実際の時間とは大きく異なる予測により、誤った経路選択を行い、その結果として多重化効率の低下を招いていた。【００１８】
この問題は、予測時の経路状態をリアルタイムで入手することができ、この経路状態を送信時に反映することができれば解決するが、実際には現在の経路状態をリアルタイムで入出することは不可能である。【００１９】
そこで、本発明は上記課題に鑑みて発明されたものであって、その目的は、受信側から入手した経路状態を過去に送信したデータにも反映させることにより、実際のデータの到着時刻又は受信完了時刻に近い到着時刻又は受信完了時刻を予測することができる技術を提供することにある。【００２０】
また、本発明の目的は、複数経路を選択可能な２ノード間のデータ転送に際し、受信側から入手した経路状態を過去に送信したデータにも反映させることにより、実際のデータの到着時刻又は受信完了時刻に近い到着時刻又は受信完了時刻を予測し、この予測に基づいて経路選択を行うことにより、多重化効率に優れる技術を提供することにある。【００２１】
また、本発明の目的は、複数経路を選択可能な２ノード間のデータ転送に際し、各経路の性能が動的に変化し、かつその時定数に比べ無視できないほど大きな往復遅延が存在する場合にも効率的な経路リソースの活用を可能とする技術を提供することにある。
【課題を解決するための手段】
【００２３】
上記課題を解決する第１の発明は、負荷分散方法であって、
複数の通信経路を選択可能な２ノード間において、送信側ノードにおいて入力されるパケットごとに、選択可能な各経路の経路状態を監視し、その経路状態の経路状態情報と、この経路状態情報が有効となる時刻又はパケットの識別情報を記憶するステップと、
経路状態情報と、前記経路状態情報が有効となる時刻以降のパケットの送信履歴、又は前記送信済みパケットの識別情報で特定されるパケットの送信以降のパケットの送信履歴に基づいて、各経路におけるパケットの到着予想時刻を推定するステップと、
前記推定された到着予想時刻に基づいて、経路の選択、又は選択優先度の更新を行うステップとを有することを特徴とする。
【００２４】
上記課題を解決する第２の発明は、上記第１の発明において、前記経路状態情報は、経路の遅延を含むことを特徴とする。
【００２５】
上記課題を解決する第３の発明は、上記第１又は第２の発明において、前記経路状態情報は、経路の通信速度を含むことを特徴とする。
【００２６】
上記課題を解決する第４の発明は、上記第１から第３の発明のいずれかにおいて、前記経路状態情報は、経路の負荷を含むことを特徴とする。
【００２７】
上記課題を解決する第５の発明は、上記第１から第４の発明のいずれかにおいて、経路の選択又は選択優先度の更新に際し、各経路の経路状態情報が更新されると、更新以前に送信されたパケットに関する送信コスト計算結果に修正を加えることを特徴とする。
【００２８】
上記課題を解決する第６の発明は、上記第５の発明のいずれかにおいて、各経路の送信コスト計算結果の修正に際し、最新の経路状態情報が有効となる最初の送信済パケット以前の履歴を破棄することを特徴とする。
【００２９】
上記課題を解決する第７の発明は、上記第１から第６の発明のいずれかにおいて、パケットを送信する経路として、受信側ノードでの受信完了時刻の推定値が最も早い経路を選択することを特徴とする。
【００３０】
上記課題を解決する第８の発明は、上記第１から第７の発明のいずれかにおいて、パケットを送信する経路として、受信側ノードで特定時刻までに受信完了できるデータ量の推定値が最大の経路を選択することを特徴とする。
【００３１】
上記課題を解決する第９の発明は、上記第１から第８の発明のいずれかにおいて、各経路につき、推測される現在の経路状態に応じてデータの送信を中断することを特徴とする。
【００３２】
上記課題を解決する第１０の発明は、上記第９の発明のいずれかにおいて、前記データ送信中断の基準が、推定受信完了時刻が特定の値以上であることを特徴とする。
【００３３】
上記課題を解決する第１１の発明は、上記第１から第１０の発明のいずれかにおいて、経路選択又は送信中断の判断を、送信データの属性ごとに異なるポリシーにより行うことを特徴とする。
【００３４】
上記課題を解決する第１２の発明は、上記第１から第１１の発明のいずれかにおいて、受信パケットの宛先アドレスに対応する通信インターフェースを、通信インターフェースのアドレスと、その通信インターフェースを経由して到達する宛先アドレスとが関連付けられたテーブルから選択し、前記受信パケットに送信元アドレス又は通信インターフェースを指定する情報がある場合には、前記送信元アドレス又は通信インターフェースに対応する通信インターフェースを前記選択された通信インターフェースから選択し、前記受信パケットに送信元アドレス又は通信インターフェースの情報がない場合には、前記選択された通信インターフェースの中から任意の通信インターフェースを選択し、選択した通信インターフェースに前記受信パケットを送出することを特徴とする。
【００３６】
上記課題を解決する第１３の発明は、パケットを送信する経路を複数選択可能なノードであって、
送信側ノードにおいて入力されるパケットごとに、選択可能な各経路の経路状態を監視し、その経路状態の経路状態情報と、この経路状態情報が有効となる時刻又はパケットの識別情報とを監視する監視手段と、
前記経路状態情報と、この経路状態情報が有効となる以降のパケットの送信履歴とが記憶された記憶手段と、
前記経路状態情報と、この経路状態情報が有効となる以降のパケットの送信履歴に基づいて、各経路におけるパケットの到着予想時刻を推定し、前記推定された到着予想時刻に基づいて、経路の選択、又は選択優先度の更新を行うスケジューリング手段と
を有することを特徴とする。
【００３７】
上記課題を解決する第１４の発明は、上記第１３の発明において、前記経路状態情報は、経路の遅延を含むことを特徴とする。
【００３８】
上記課題を解決する第１５の発明は、上記第１３又は第１４の発明のいずれかにおいて、前記経路状態情報は、経路の通信速度を含むことを特徴とする。
【００３９】
上記課題を解決する第１６の発明は、上記第１３から第１５の発明のいずれかにおいて、前記経路状態情報は、経路の負荷を含むことを特徴とする。
【００４０】
上記課題を解決する第１７の発明は、上記第１３から第１６の発明のいずれかにおいて、前記スケジューリング手段は、経路の選択又は選択優先度の更新に際し、各経路の経路状態情報が更新されると、更新以前に送信されたパケットに関する送信コスト計算結果に修正を加えることを特徴とする。
【００４１】
上記課題を解決する第１８の発明は、上記第１７の発明において、前記スケジューリング手段は、各経路の送信コスト計算結果の修正に際し、最新の経路状態情報が有効となる最初の送信済パケット以前の履歴を破棄することを特徴とする。
【００４２】
上記課題を解決する第１９の発明は、上記第１３から第１８の発明のいずれかにおいて、前記スケジューリング手段は、パケットを送信する経路として、受信側ノードでの受信完了時刻の推定値が最も早い経路を選択することを特徴とする。
【００４３】
上記課題を解決する第２０の発明は、上記第１３から第１９の発明のいずれかにおいて、前記スケジューリング手段は、パケットを送信する経路として、受信側ノードで特定時刻までに受信完了できるデータ量の推定値が最大の経路を選択することを特徴とする。
【００４４】
上記課題を解決する第２１の発明は、上記第１３から第２０の発明のいずれかにおいて、前記スケジューリング手段は、各経路につき、推測される現在の経路状態に応じてデータの送信を中断することを特徴とする。
【００４５】
上記課題を解決する第２２の発明は、上記第２１の発明において、前記データ送信中断の基準が、推定受信完了時刻が特定の値以上であることを特徴とする。
【００４６】
上記課題を解決する第２３の発明は、上記第１３から第２２の発明のいずれかにおいて、前記スケジューリング手段は、経路選択又は送信中断の判断を、送信データの属性ごとに異なるポリシーにより行うことを特徴とする。
【００４７】
上記課題を解決する第２４の発明は、上記第１３から第２３の発明のいずれかにおいて、通信インターフェースのアドレスと、その通信インターフェースを経由して到達する宛先アドレスとが関連付けられたテーブルと、送信するパケットの宛先アドレスに対応する通信インターフェースを前記テーブルから選択し、前記送信するパケットに送信元アドレス又は通信インターフェースを指定する情報がある場合には、前記送信元アドレス又は通信インターフェースに対応する通信インターフェースを前記選択された通信インターフェースから選択し、選択した通信インターフェースに前記送信するパケットを送出するルーティング手段とを有することを特徴とする。
【００４９】
上記課題を解決する第２５の発明は、パケットを送信する経路を複数選択可能なノードの制御プログラムであって、前記プログラムはノードを、
送信側ノードにおいて入力されるパケットごとに、選択可能な各経路の経路状態を監視し、その経路状態の経路状態情報と、この経路状態情報が有効となる時刻又はパケットの識別情報とを監視する監視手段と、
前記経路状態情報と、この経路状態情報が有効となる以降のパケットの送信履歴に基づいて、各経路におけるパケットの到着予想時刻を推定し、前記推定された到着予想時刻に基づいて、経路の選択、又は選択優先度の更新を行うスケジューリング手段と
して機能させることを特徴とする。
【００５０】
上記課題を解決する第２６の発明は、上記第２５の発明において、前記経路状態情報は、経路の遅延を含むことを特徴とする。
【００５１】
上記課題を解決する第２７の発明は、上記第２５又は第２６の発明のいずれかにおいて、前記経路状態情報は、経路の通信速度を含むことを特徴とする。
【００５２】
上記課題を解決する第２８の発明は、上記第２５から第２７の発明のいずれかにおいて、前記経路状態情報は、経路の負荷を含むことを特徴とする。
【００５３】
上記課題を解決する第２９の発明は、上記第２５から第２８の発明のいずれかにおいて、前記制御プログラムは、前記スケジューリング手段を、経路の選択又は選択優先度の更新に際し、各経路の経路状態情報が更新されると、更新以前に送信されたパケットに関する送信コスト計算結果に修正を加えるように機能させることを特徴とする。
【００５４】
上記課題を解決する第３０の発明は、上記第２９の発明において、前記制御プログラムは、前記スケジューリング手段を、各経路の送信コスト計算結果の修正に際し、最新の経路状態情報が有効となる最初の送信済パケット以前の履歴を破棄するように機能させることを特徴とする。
【００５５】
上記課題を解決する第３１の発明は、上記第２５から第３０の発明のいずれかにおいて、前記制御プログラムは、前記スケジューリング手段を、パケットを送信する経路として、受信側ノードでの受信完了時刻の推定値が最も早い経路を選択するように機能させることを特徴とする。
【００５６】
上記課題を解決する第３２の発明は、上記第２５から第３１の発明のいずれかにおいて、前記制御プログラムは、前記スケジューリング手段を、パケットを送信する経路として、受信側ノードで特定時刻までに受信完了できるデータ量の推定値が最大の経路を選択するように機能させることを特徴とする。
【００５７】
上記課題を解決する第３３の発明は、上記第２５から第３２の発明のいずれかにおいて、前記制御プログラムは、前記スケジューリング手段を、各経路につき、推測される現在の経路状態に応じてデータの送信を中断するように機能させることを特徴とする。
【００５８】
上記課題を解決する第３４の発明は、上記第３３の発明において、前記データ送信中断の基準が、推定受信完了時刻が特定の値以上であることを特徴とする。
【００５９】
上記課題を解決する第３５の発明は、上記第２５から第３４の発明のいずれかにおいて、前記制御プログラムは、前記スケジューリング手段を、経路選択又は送信中断の判断を、送信データの属性ごとに異なるポリシーにより行うように機能させることを特徴とする。
【００６０】
上記課題を解決する第３６の発明は、上記第２５から第３５の発明のいずれかにおいて、前記制御プログラムは、送信するパケットの宛先アドレスに対応する通信インターフェースを、通信インターフェースのアドレスと、その通信インターフェースを経由して到達する宛先アドレスとが関連付けられたテーブルから選択し、前記送信するパケットに送信元アドレス又は通信インターフェースを指定する情報がある場合には、前記送信元アドレス又は通信インターフェースに対応する通信インターフェースを前記選択された通信インターフェースから選択し、選択した通信インターフェースに前記送信するパケットを送出するルーティング手段として機能させることを特徴とする。
【００６１】
上記課題を解決する第３７の発明は、送信パケットの到着時刻又は受信完了時刻を推定する送信パケットの時刻推定方法であって、
送信側ノード側から送信される送信パケットにパケットを識別するパケット識別情報を付加して送信するステップと、
送信側ノード側にて、送信したパケットの送信履歴をパケット識別情報と共に記憶するステップと、
受信ノード側にて、経路状態の情報を、この経路状態時に受信した最後のパケットのパケット識別情報を含めて送信側ノードに送信するステップと、
送信側ノード側にて、前記経路状態と、前記経路状態の情報に含まれるパケット識別情報で特定されるパケット以降に送信されたパケットの送信履歴とに基づいて、送信しようとするパケットの到着時刻又は受信完了時刻を推定するステップと
を有することを特徴とする。
【００６２】
上記課題を解決する第３８の発明は、ノードであって、
送信パケットにパケットを識別するパケット識別情報を付加して送信する手段と、
送信したパケットの送信履歴をパケット識別情報と共に記録する手段と、
受信側から送信されてくる経路状態の情報を受信し、この経路状態と、この経路状態が有効となるパケット以降に送信されたパケットの送信履歴とに基づいて、送信しようとするパケットの到着時刻又は受信完了時刻を推定する手段と
を有することを特徴とする。
【００６３】
上記課題を解決する第３９の発明は、パケットを送信するノードの制御プログラムであって、前記制御プログラムはノードを、
送信パケットにパケットを識別するパケット識別情報を付加して送信する手段と、
送信したパケットの送信履歴をパケット識別情報と共に記録する手段と、
受信側から送信されてくる経路状態の情報を受信し、この経路状態と、この経路状態が有効となるパケット以降に送信されたパケットの送信履歴とに基づいて、送信しようとするパケットの到着時刻又は受信完了時刻を推定する手段として機能させることを特徴とする。
【００６４】
本発明は、データ（パケット）送信時において、送信データ（パケット）の送信履歴を記憶する。この送信履歴には、例えば、送信データ（パケット）を識別する識別子や、送信開始時刻等を記述する。一方、受信側では、データ（パケット）が通る経路の状態情報（例えば、速度やパケット遅延）を送信側に送信する。この経路状態情報には、上述したデータ（パケット）の識別子のような、経路状態情報が適用される最新のデータ（パケット）を識別する情報を含める。【００６５】
送信側では、経路の状態情報を受信し、この経路状態に含まれているデータ（パケット）を識別する情報（例えば、識別子）により、この経路状態が有効となる送信済みのデータ（パケット）を、送信履歴から求める。そして、求めたデータ（パケット）以降のデータについて、受信した経路の状態を適用して受信完了時刻等を予測し、更に、この予測と受信した経路の状態情報とに基づいて、各経路におけるこれから送信しようとするデータの到着時刻又は受信完了時刻を予測する。【００６６】
経路選択においては、予測されたデータの到着時刻又は受信完了時刻に基づいて、最も適切な経路、例えば到着時刻が最も早いと予測される経路を選択する。
【発明の効果】
【００６７】
本発明は、受信側から得られる経路の状態情報を、この情報が有効となる過去に送信したデータ（パケット）にも適用し、この結果を送信しようとするデータ（パケット）の予測にも反映させてデータの到着時刻又は受信完了時刻を予測しているので、従来と比べて精度の良い予測を行うことができる。何故なら、従来技術では、受信側から得られる経路の情報を、送信しようとするデータ（パケット）のみに適用して到着時刻又は受信完了時刻を予測しているからである。【００６８】
また、本発明は、複数経路を選択可能な２ノード間のデータ転送に際し、受信側から得られる経路の状態情報を、この情報が有効となる過去に送信したデータにも適用し、この結果を送信しようとするデータの予測にも反映させてデータの到着時刻又は受信完了時刻を予測し、この予測に基づいて経路選択を行うので、予測の誤差による誤った経路選択をすることなく、適切な経路を選択することによって多重化効率の低下といった問題を回避することができる。【００６９】
本発明によれば、複数経路を選択可能な２ノード間のデータ転送に際し、各経路の性能が動的に変化し、かつその時定数に比べ無視できないほど大きな往復遅延が存在する場合にも効率的な経路リソースの活用を可能とする。
【図面の簡単な説明】
【００７０】
【図１】図１は本発明の実施の形態におけるノード間経路の構成を示す図である。
【図２】図２は送信側ノードの構成を示す図である。
【図３】図３は実施の形態における送信側ノードおよび受信側ノードでのパケット処理のタイミングを説明する為の図である。
【図４】図４は実施の形態におけるスケジューリング部の動作フローチャートである。
【図５】図５は他の実施の形態における送信側ノードおよび受信側ノードでのパケット処理タイミングを説明する為の図である。
【図６】図６は他の実施の形態におけるスケジューリング部の動作フローチャートである。
【図７】図７は実施の形態における送信側ノードおよび受信側ノードにおける、到着時刻又は受信完了時刻の予測を説明する為の図である。
【図８】図８は従来の技術を説明する為の図である。
【図９】図９は通信インターフェースが個別のIPアドレスを持つ場合の構成例を示したものである。
【図１０】図１０は図９の系における送信ノード100-2の内部構成の一例を示した図である。
【図１１】図１１はIPルーティング処理部1318の構成を表した図である。
【図１２】図１２は経路制御テーブル1321の一例を示す図である。
【図１３】図１３はIFアドレス管理テーブル1322の一例を示す図である。
【図１４】図１４はメモリ部315-2に保存される経路⇔通信インターフェース対応表1330の一例を示した図である。
【図１５】図１５は送信IPパケット生成データ1510の構成を示す図である。
【図１６】図１６は送出IPパケット1610の構成を示す図である。
【図１７】図１７は送信IF判定・送出処理部1320による送信IF決定のフローチャートである。
【図１８】図１８は他の送信IPパケット生成データを示す図である。
【図１９】図１９は他の送出IPパケットを示す図である。
【図２０】図２０は送信IF判定・送出処理部1320による他の送信IF決定のフローチャートである。
【図２１】図２１は経路制御テーブル1321のエントリの一例を示す図である。
【符号の説明】
【００７１】
１０    データ生成ノード
１１    宛先ノード
１００  送信ノード
１０１  受信ノード
１０２  有線ネットワーク
２００  無線送信手段
２０１  無線受信手段
２０２  無線リンク
３００  無線網
３１０  通信インターフェース
３１２  キューイング部
３１３  スケジューリング部
３１４  経路状態監視部
３１５  メモリ部
【発明を実施するための最良の形態】
【００７２】
本発明を実施するための形態について説明する。【００７３】
本形態では、速度と共に遅延が動的に変動する複数の経路、特に無線リンクを含む経路を組み合わせて、一つの論理的な経路とする技術への適用を想定している。以下の説明では、複数の経路を組み合わせて一つの論理的な経路とする技術の例として、Inverse Multiplexingを例にして説明する。【００７４】
図１は本実施の形態の構成例を示したものである。【００７５】
図１では、データ生成ノード10から宛先ノード11までの経路上に、Inverse Multiplexingを行う送信ノード100と受信ノード101がある。送信ノード100と受信ノード101の間には3つの経路があり、それぞれが無線送信手段200-1〜200-3と無線受信手段201-1〜201-3の間の通信路として、無線リンク202-1〜202-3を含む。尚、図１では3つの経路の場合を示しているが、経路の数は2以上の任意の値を取ることができる。また、送受信ノード間の経路は全て無線でもかまわないが、一般に有線網102も含むものとする。更に、一般に各無線リンクは異なる無線網300に属する。この例では、経路202-1、202-2はセルラーネットワーク300-1であり、無線網300-2は無線LANである。【００７６】
図１の系において送信ノード100は、データ生成ノード10より受信したトラフィックを、状態情報に基づき各経路に分配し、受信ノード101は各経路を経由した送信ノード100からのトラフィックを再統合して宛先ノード11に向けて送信する。【００７７】
ここで、送信ノード100の内部構成を図２に示す。【００７８】
データ発生ノード10が宛先ノード11に向けて送信したトラフィックは通信インターフェース310-1から入力され、キューイング部312、スケジューリング部313を経てInverse Multiplexingリンクの送信側通信インターフェースである310-2または310-3から送出される。尚、複数の経路が最も送信ノード寄りの物理リンクを共有する場合もあるので、Inverse Multiplexingリンクを構成する経路は必ずしも通信インターフェースと1対1対応するものではない。【００７９】
スケジューリング部313は、キューイング部312から入力データを取り出し、特定の経路に送出する。取り出したデータの転送に用いる経路の選択は、経路状態監視部314が管理する経路状態を参照して行われる。経路状態監視部314は受信ノード101から通信インターフェース310-2または310-3を介して断続的に各経路の状態情報および更新が有効となる送信パケットを識別する情報（以下、レポートと称する）を受信し、それらに基づきメモリ部315に格納された経路状態情報を更新する。【００８０】
ここで経路状態情報とは、通信性能の指標となる情報一般を指す。本実施の形態では、そのうち経路の速度とパケット遅延を用いる。また、経路状態情報の有効時とは、送信ノード側における経路状態情報の更新時を意味するものでなく、経路状態情報で示される経路状態となった時間、その経路状態において伝送されたパケットで特定される時刻等である。従って、経路状態情報の有効時以降の送信履歴とは、経路状態情報の有効時以降に送信されたパケットの送信履歴等をいう。尚、この時刻は、その測定の元になったパケット情報（パケットを識別する識別子）や、受信ノード側から送信される受信時等から得られるが、多少のずれはかまわない。また、経路状態情報を得る為、受信ノードが速度や遅延を測定する方法は各種提案されているが、本実施の形態で想定している方法を以下に述べる。【００８１】
送信ノード100は、受信ノード101へのパケットの各々に識別子と送信時刻を挿入して転送するものとする。受信ノードはパケット遅延を、送信ノードが挿入した送信時刻と自身が受信した時刻を比較することで測定する。また、送信ノードは定期的に測定用のパケット列を送信し、受信ノードはその到着時間のばらつきから速度を推定できる。推定の方法の詳細は例えば文献「Dovrolis, Ramanathan, and Moore, ”What DoPacket Dispersion Techniques Measuere?,” IEEE INFOCOM 2001」で紹介されている。前記Dovrolisらの文献においては、送信側ノードが２つのパケットを同時に送信し、送信側でこの２つのパケットの到着時刻差からリンク速度を推定する。パケットの到着間隔を広げるのは伝送遅延であり、伝送遅延はリンク速度と関係があることから、到着間隔より速度を推定可能である。【００８２】
受信ノード101は、定期的にこれらの測定値を経路状態情報として送信ノード100に送信する。また、そのときまでに受信した最新のパケットの識別子を、送信する状態情報が有効となるパケットの識別情報として同時に送信する。これらの情報が、上述したレポートとして送信ノードで受信される。尚、以上の方式は一例であり、本発明の実施可能性は経路状態情報及びこれが有効となるパケットの決定及び伝達の方法には依存しない。【００８３】
スケジューリング部313は、次に転送すべきパケットにつき、送信経路ごとに現在の経路情報およびその情報が有効となるパケットの送信時以降の送信履歴を参照し、受信側ノード101での到着遅延を予測する。送信履歴はメモリ部315に記憶されている。スケジューリング部313は、予測した到着遅延が最小となる経路を次に転送すべきパケットの送信経路として選択し、選択した経路へのパケット転送後、その転送時刻をメモリ部315上の送信履歴に加える。【００８４】
スケジューリング部313で動作する経路ごとの到着遅延推定方法の一例を図３に示す。図３中400-1, 400-2, 400-3はデータパケットであり、その送信側ノード100での送信履歴および予測と受信側ノード101での受信履歴および予測がそれぞれ時間軸上で示されている。例えばデータパケット400-1は送信側ノードで時刻T1に送信が開始され、時刻T2に送信が完了している。また同じパケット400-1は受信側ノードで時刻T3より受信が開始され、時刻T4に受信が完了している。ここでT1とT3との差I1が伝送遅延である。また、T4とT2との差I2が、伝送遅延I1に送信インターフェースと転送経路の速度差とにより生じるパケットの分散を加えた総遅延となる。【００８５】
ここで、時間軸上TPの現在時刻において、パケット400-3を送信しようとしているものとする。そして、この経路につき、T5とTPの間でレポート結果通知の受信により、経路状態情報が更新され、この経路状態情報が有効となるパケットは400-1からとする。そこで、経路状態情報が有効となるパケット（400-1、400-2）の送信履歴に基づいて、パケット400-1、パケット400-2を考慮したパケット400-3の受信完了時刻の推定を行う。【００８６】
すると、パケット400-1より後に送信されたパケット400-2の受信側ノード101での受信開始時刻及び完了時刻は現在受信している経路状態情報に含まれる速度及び伝送遅延から推定される。推定された受信開始時刻は図３中T5、受信完了時刻はT7である。ここで、経路状態情報が示す伝送遅延はI1に等しいとすると、TPに送信開始したパケット400-3は時刻T6に受信開始されるはずであるが、そのときまだ受信側ノードではパケット400-2の受信が完了していないと推定されるのでパケット400-3の推定受信開始時刻はパケット400-2の受信が完了すると推定されるT7となり、パケット400-3の推定受信完了時刻は経路状態情報に含まれる経路速度から推定されるパケット分散を加えたT8となる。同様にパケット400-3の受信完了時刻の推定を各経路につき行い、それが最も早い時刻となる経路にパケット400-3は送出される。【００８７】
なお、図３におけるTPの時点での受信側の到着時刻推定に用いている経路状態情報は、T5とTPの間でレポート結果通知の受信により更新されたものである。すると、パケット400-2を送信した際の到着時刻推定はTPにおけるより古い経路状態情報に基づいて行われたことになる。この古い状態情報を情報A、T5とTPとの間で更新された新しい情報を情報Bとすると、リンク状態の変動により情報Aと情報Bに含まれる遅延や経路速度が異なれば、Aに基づく到着時刻予測は、図３に示される情報Bに基づく到着時刻予測と異なっていたはずである。したがって、図３に示したパケット400-1および400-2の到着時刻予測は情報Bを得た結果の修正を反映している。ひとたび経路状態情報の更新が行われると、その更新が有効となるパケット以前の送信履歴は参照不要となるのでこれを破棄する。【００８８】
更に、本発明を適用した場合のパケット到着時刻推定及び受信完了時刻と、従来のパケット到着時刻推定及び受信完了時刻との差を、図７を用いて具体的に説明する。【００８９】
図７中500-1, 500-2, 500-3は送出されるデータパケットであり、その送信側ノードでのパケットの送信履歴（実線）と受信側ノードでの実際のパケットの受信履歴（実線）がそれぞれ時間軸上で示されている。また、パケットの到着及び受信完了時刻の予測（点線）もそれぞれ時間軸上で示されている。また、図７上部に記した曲線は、伝送経路の速度変化を示すものである。図７では、時間が経過するとともに伝送速度が遅くなっている旨を示している。【００９０】
まず、実際のパケットの送受信であるが、送信側ノード側から時刻T1にデータパケット500-1の送信が開始され、時刻T2に送信が完了している。そして、受信側ノードで、パケット500-1は、時刻T3より受信が開始され、時刻T5に受信が完了している。【００９１】
その後、送信側ノード側から時刻T4にデータパケット500-2の送信が開始され、時刻T8に送信が完了している。そして、受信側ノード側では、通信速度の低下により、データパケット500-2は、時刻T7より受信が開始され、時刻T13に受信が完了している。【００９２】
更に、送信側ノード側から時刻T9にデータパケット500-3の送信が開始され、時刻T10に送信が完了している。そして、受信側ノード側では、データパケット500-3が、時刻T14より受信が開始され、時刻T16に受信が完了している。【００９３】
次に、上述のような実際のパケットの送受信において、本発明を適用した場合のパケットの到着時刻及び受信完了時刻の予測について説明する。【００９４】
上述の如く、データパケット500-1は、時刻T1に、データパケット500-1の送信時刻及びパケット識別子の情報と共に送信側ノードで送信が開始され、時刻T2に送信が完了している。このとき、送信側ノードでは、送信履歴としてデータパケット500-1の送信時刻及びパケット識別子を記憶している。【００９５】
続いて、送信側ノードより、データパケット500-2が、データパケット500-2の送信時刻及びパケット識別子の情報と共に時刻T4に送信が開始され、時刻T8に送信が完了している。このとき、送信側ノードでは、上述と同様に、送信履歴としてデータパケット500-2の送信時刻及びパケット識別子を記憶している。【００９６】
受信ノード側では、データパケット500-1が、時刻T3より受信が開始され、時刻T5に受信が完了している。このとき、受信ノード側は、データパケット500-1の識別子、受信完了時刻及び通信速度等の情報をレポートとして、送信ノードに送信する。【００９７】
送信ノード側では、時刻TXに受信ノードからレポートを受信したとする。そして、レポートに含まれるデータパケット500-1の識別子により、レポートの経路状態情報の有効時は、データパケット500-1の送信時刻T1と判断する。【００９８】
そこで、送信ノードは、時刻T1以降の送信履歴に基づいて、データパケット500-3の到着時刻及び受信完了時刻の予測を行う。時刻T1以降の送信履歴によると、対象となるデータパケットはデータパケット500-1、データパケット500-2である。データパケット500-1の受信完了時刻は、レポートにより、時刻T5とわかる。データパケット500-2の到着時刻及び受信完了時刻の予測には、レポートのデータパケット500-1の通信速度や、受信完了時刻が用いられ、これらの情報により、伝送遅延やパケットの総遅延の時間がわかる。尚、伝送遅延はT1とT3との差I1である。また、パケットの総遅延は、伝送遅延I1に送信インターフェースと転送経路の速度差とにより生じるパケットの分散を加えた時間であり、T5とT2との差I2である。データパケット500-2の到着時刻は、伝送遅延I1により求められ、データパケット500-2の送信時刻T4に伝送遅延I1を加えた時刻T6と予測される。また、データパケット500-2の受信完了時刻は、レポートの通信速度によりパケット遅延を求めることができるので、データパケット500-2の受信完了時刻は時刻T12と予測することができる。従って、この経路において、データパケット500-3の受信ノードの到着時刻は、時刻T12以降と予測することができる。また、この時刻T12から受信が開始された場合の受信完了時刻は、上述したパケット分散の予測により、時刻T15と予測することができる。このような予測の結果によれば、予測したデータパケット500-3の到着時刻T12と、実際のデータパケット500-3の到着時刻T14との差は、時間ID1である。【００９９】
一方、従来技術によるパケットの到着時刻及び受信完了時刻の予測では、受信ノードより得られたレポートの到着時刻において、レポートで示される経路状態を有効としており、データパケット500-3の予測にあたっても、レポートで示される経路状態をそのまま適用している。すなわち、データパケット500-3の到着時刻の予測にあたって、データパケット500-3の送信時刻T9に伝送遅延I1を加えた時刻T11と予測している。このような予測の結果によれば、予測したデータパケット500-3の到着時刻T11と、実際のデータパケット500-3の到着時刻T14との差は、時間ID2である。【０１００】
従って、実際の到着時間との誤差時間ID1と誤差時間ID2とでは、本発明による予測による誤差時間ID1の方が、誤差時間ID2よりも誤差が少ないことは、図面からも明らかである。【０１０１】
次に、以上説明したような到着時刻推定を含む、スケジューラの経路選択の手順を図４に示す。【０１０２】
まず、キューイング部312により、パケットが受信される（Ｓｔｅｐ  １００）。【０１０３】
次に、いずれかの経路で、その経路から最後のパケットを送信した後に経路状態情報が更新されたかを判断する（Ｓｔｅｐ  １０１）。経路状態情報が更新された場合には、更新された全ての経路で、経路状態情報が有効となる以前の送信履歴を削除する（Ｓｔｅｐ  １０２）。【０１０４】
続いて、各経路において、経路状態情報と送信履歴とに基づいて、パケットの到着時刻を予測（推定）する（Ｓｔｅｐ  １０３）。そして、予測（推定）到着時刻が最も早い経路にパケットを送信する（Ｓｔｅｐ  １０４）。【０１０５】
最後に、パケット送信に用いた経路の送信履歴を更新する（Ｓｔｅｐ  １０５）。【０１０６】
以上の如く、経路状態情報更新の際にはそれ以前に送信済みのパケットの到着時刻予測が修正され、それ以降のパケット送信の際の判断に反映されるので、結果的に過去の送信実績の補償が可能になる。この補償の効果は各経路の往復遅延が大きく、経路の状態変動の周期に対して無視できない場合に顕著になる。以下にその理由を述べる。【０１０７】
経路の状態変動が往復遅延程度の時間で起こる場合、ある状態情報を送信側ノードが取得したころには既に当該経路の状態は変わっているかもしれないのでその情報は信頼するに足らない。したがってパケットを送信する時点で経路選択およびタイミング設定を最適に行うことは不可能であり、一般には非最適な経路およびタイミングでパケットが送信されることになる。状態情報更新の際に到着時刻予測を修正することは、既に行われた非最適な送信のインパクトを、状態情報更新間隔分の時間が経ってから推定することに等しい。例えば、以前に高すぎるレートで送信していた場合、状態情報の更新により送信済みパケットの到着予測時刻は延長されてその経路の送信コストは引き上げられる。【０１０８】
以上のような、状態情報更新による過去の送信パケットの到着時刻予測の修正は経路選択の最適化の効果があるが、経路選択のみならず送信タイミング制御に到着時刻予測の修正をフィードバックすると各経路の輻輳制御も長期的に最適化される。【０１０９】
次に、実施するための他の形態について説明する。【０１１０】
以下の形態では簡単なタイミング制御を実装した場合の動作を説明する。【０１１１】
次に示す他の形態では、上述した形態と同様に送出パケットの受信完了時刻を経路ごとに推定し、最も評価値の高い経路を選択するが、新たに経路ごとに許容推定遅延を定義し、推定遅延がその値を超えないよう送信側ノード100が送信タイミングを制御する簡単なタイミング制御を導入することもできる。図５を用いて本形態の動作を説明する。【０１１２】
図５中、許容推定遅延をTMとしている。この意味は、TPの時点でパケットを送出するにはそのパケットはTM+TPまでに受信完了すると推定されなければならないということである。ところが上述した形態と同様な手段でパケット400-3の受信完了時刻を推定するとT8となり、これはTM+TPよりも未来である。したがって推定受信完了時刻がTM+TPとなるまでの間、送信側ノード100はこの経路からパケット400-3を送出できない。この場合送信側ノード100はいずれかの経路の推定受信完了時刻がTM+TP以下となるまでパケット400-3を保留し、最も早く保留が解ける経路よりこのパケットを送信する。以上の形態でのスケジューリング部313の動作フローを図６に示す。【０１１３】
まず、キューイング部312により、パケットが受信される（Ｓｔｅｐ  ２００）。【０１１４】
次に、いずれかの経路で、その経路から最後のパケットを送信した後に経路状態情報が更新されたかを判断する（Ｓｔｅｐ  ２０１）。経路状態情報が更新された場合には、更新された全ての経路で、経路状態情報が有効となる以前の送信履歴を削除する（Ｓｔｅｐ  ２０２）。【０１１５】
続いて、各経路において、経路状態情報と送信履歴とに基づいて、パケットの到着時刻を予測（推定）する（Ｓｔｅｐ  ２０３）。そして、予測（推定）された到着時刻を用いて、全ての経路について、（予測（推定）到着時刻）＞（現在時刻＋許容推定遅延）であるかを判断し（Ｓｔｅｐ  ２０４）、いずれかの経路で（予測（推定）到着時刻）≦（現在時刻＋許容推定遅延）である場合には、それらの経路のうち予測（推定）到着時刻が最も早い経路にパケットを送信する（Ｓｔｅｐ  ２０５）。【０１１６】
一方、全ての経路で、（予測（推定）到着時刻）＞（現在時刻＋許容推定遅延）である場合には、いずれかの経路で現在時刻が（予測到着時刻−許容推定遅延）となるまで待機し、いずれかの経路で条件を満たした場合にはＳｔｅｐ  ２０５に進む（Ｓｔｅｐ  ２０６）。【０１１７】
最後に、パケット送信に用いた経路の送信履歴を更新する（Ｓｔｅｐ  ２０７）。【０１１８】
尚、許容遅延TPの値は経路ごとに独立に設定してよい。例えば各経路の遅延や経由するサーバのバッファ量等が大きく異なる場合、特に高負荷下ではTMの設定値を各経路で異なる設定とすることで各経路の帯域の有効活用が図れると考えられる。【０１１９】
また、経路選択の判断は推定受信完了時刻の他に、例えばパケット欠落率や回線使用料金などが監視可能であればそれらを優先して評価してもよい。また判断の方法は送られるデータの属性により異なってもよい。例えば音声データであれば遅延を、緊急ではないファイル転送データであれば回線使用料金を重視した選択を行うなどである。本発明の特徴は、いずれの場合においても、送信ノードが経路状態情報を更新する際に同時にその更新が有効となる送信パケットまたは時刻を取得し、有効パケットまたは有効時刻以降の送信履歴より送信コストへのインパクトを推定し、コスト最小の経路に次のパケットを送信することである。その結果、遅延が大きく経路の状態変動の時定数に比べ無視できないほど大きい場合にも、過去の非最適な送信により既に与えてしまったコスト基準へのインパクトをその後の送信タイミングの調整に反映させることで補償することができ、経路の利用効率を向上させる効果がある。【０１２０】
次に、上述した本発明の経路選択方法を、図９に示すようなIPネットワークに適用した場合について説明する。【０１２１】
図９は、本実施の形態で、通信インターフェースが個別のIPアドレスを持つ場合の構成例を示したものである。【０１２２】
図９では、データ生成ノード10-2から宛先ノード11-2までの経路上に、複数の経路を持つ送信ノード100-2と受信ノード101-2がある。送信ノード100-2と受信ノード101-2の間には3つの経路がある。図９の構成例では、送信ノード100-2は送信手段として通信インターフェースであるS-IF#1 1310-1、S-IF#2 1310-2、S-IF#3 1310-3、S-IF#4 1310-4を装備している。通信インターフェースS-IF#1 1310-1〜S-IF#3 1310-3は、それぞれ異なる無線網1300-1〜1300-3に属しており、無線リンク202-4〜202-6を介してセルラーキャリア網内に位置するキャリア網ゲートウェイ1400-1〜1400-3と接続している。また、通信インターフェースS-IF#4 1310-４は、有線または無線リンク202-7を介してデータ生成ノード10-2に搭載された通信インターフェースである D-IF 1200と接続している。また、受信ノード101-2は受信手段として通信インターフェースであるR-IF 1500-1を装備している。受信ノード101-２は、通信インターフェースR-IF 1500-1と有線網102-2を介して、各キャリア網ゲートウェイ1400-1〜1400-3と接続している。【０１２３】
図９の系においては、通信インターフェースS-IF#1 1310-1〜S-IF#3 1310-3はそれぞれ、Point to Point Protocol(PPP)等の手段を用いることにより個別のIPアドレスとして「100.1.2.3」、「110.1.2.3」、「120.1.2.3」が割り当てられている。また、通信インターフェースR-IF 1500-1には、固定的に設定もしくはDHCPなどの手段を用いることによりIPアドレスとして「200.7.8.9」が割り当てられている。さらに、通信インターフェースD-IF 1200には、固定的に設定もしくはDHCPなどの手段を用いることによりIPアドレスとして「192.168.2.50」が割り当てられている。【０１２４】
ここで、図１０に、図９の系における送信ノード100-2の内部構成の一例を示す。送信ノード100-2ではIP通信を行うために、パケットのキューイング部312-2と、スケジューリング部313-2と、経路状態監視部314-2と、メモリ部315-2と、IPパケット生成部1316と、IPパケットキューイング部1317と、IPルーティング処理部1318とから構成される。【０１２５】
スケジューリング部313-2は、キューイング部312-2から入力データ(宛先アドレス、送信データ)を取り出し、特定の通信インターフェースを選択する。取り出したデータの転送に用いる通信インターフェース (経路)の選択は、経路状態監視部314-2が管理する経路状態を参照して行われる。スケジューリング部313-2及び経路状態監視部314-2の経路選択方法は、上述したスケジューリング部313及び経路状態監視部314の同様な動作により、経路を選択して決定する。また、経路状態の情報は、上述したメモリ部315と同様にメモリ部315-2に格納される。尚、以下の説明では、スケジューリング部313-2及び経路状態監視部314-2が、上述した動作と同様な動作により、通信インターフェース (経路)の選択が行われたものとして説明する。【０１２６】
IPパケット生成部1316は、スケジューリング部313-2から受け取ったデータにIPヘッダを付与することでIPパケットを生成するものである。また、IPパケットキューイング部1317は、IPパケット生成部1316が生成したIPパケットを蓄積するバッファである。また、IPルーティング処理部1318は、IPパケットキューイング部1317に蓄積されたIPパケットを取り出し、IPパケットの次の転送先を判別すると共に、通信インターフェースS-IF#1 1310-1〜S-IF#4 1310-4のうち適切なものを使用してIPパケットの送出を行うものである。【０１２７】
図１１は、IPルーティング処理部1318の構成を表したものである。IPルーティング処理部1318には、渡されたIPパケットの転送先を判別するために使用される経路制御テーブル1321(図１２に示す)が備えられている。また、搭載されている各通信インターフェースに割り当てられているIPアドレスが記録されているIFアドレス管理テーブル1322(図１３に示す)が備えられている。そして、これらの経路制御テーブル1321とIFアドレス管理テーブル1322を使用して、IPルーティング処理部1318に渡されたIPパケットの転送先を判別し、対応する通信インターフェースS-IF#1 1310-１〜S-IF#4 1310-4に向けて、該IPパケットを送出する、送信IF判定・送出処理部1320が備えられている。【０１２８】
図１４は、メモリ部315-2に保存される、通信経路とそれに対応する通信インターフェースの対応を保存したテーブル (以下、経路⇔通信インターフェース対応表1330)の一例を示したものである。経路⇔通信インターフェース対応表1330の各エントリには、スケジューリング部313-2および経路状態監視部314-2が意識する各通信経路の識別子である通信経路番号と、それぞれの通信経路との接続に利用している通信インターフェース名の情報が格納されている。【０１２９】
図１２に示される経路制御テーブル1321には一般的に、IPパケットの送信先となる宛先ネットワークIPアドレス毎に、ネットワークマスクと、そのネットワークへIPパケットを到達させるために次の転送先を示すゲートウェイIPアドレスが記述されている。そして、そのゲートウェイIPアドレスと同一のサブネットワークに接続された通信インターフェースを示す情報が記録されている。なお、実際には他に同一サブネットに属する全ての通信機器に送信を行うためのマルチキャストアドレス等が設定される場合もあるが、これについての図示および説明を省略する。【０１３０】
図１３に示されるIFアドレス管理テーブル1322には、送信ノードに搭載されている通信インターフェースとそれに割り当てられているIPアドレスの対応が記録されている。IFアドレス管理テーブル1322の内容は、各通信インターフェースに割り当てられるIPアドレスが変更される毎に更新される。【０１３１】
本実施の形態では、受信ノード101-2は受信手段として単一の通信インターフェースであるR-IF 1500-1のみを装備しているのに対して、送信ノード100-2はそれぞれ個別のIPアドレスが割り当てられた通信インターフェースであるS-IF#1 1310-1〜S-IF#4 1310-4を装備している。そのため、経路制御テーブル1321には、宛先ネットワークIPアドレスの値が同一の「200.7.8.9」に対して、それぞれ異なるゲートウェイIPアドレスと通信インターフェースが登録されたエントリ1321-a、1321-b、1321-cが存在している。また、経路制御テーブル1321には、データ生成ノード10-2への経路情報である1321-dも存在している。【０１３２】
送信IF判定・送出処理部1320は、受け取ったIPパケットのヘッダ情報と経路制御テーブル1321を用いてIPパケットの送出に使用するインターフェースを決定する、いわゆるIPルーティングと呼ばれる処理を実行する。【０１３３】
本実施の形態では、図１２に示すように、「宛先ネットワークIPアドレス」が重複したエントリが複数存在し、IPルーティング処理は、送出に使用するインターフェースを決定するものである。【０１３４】
以降では、図９に示す本実施の形態において、スケジューリング部313-2で送信経路として、経路⇔通信インターフェース対応表1330に登録されている通信経路番号が「3」の経路が選択されたものとして、決定された経路に対応する通信インターフェースであるS-IF#2 202-5を用いてIPパケットを送出させる場合の例を示す。他の経路が選択された場合も同様の処理で実現することができる。【０１３５】
スケジューリング部313-2は、通信経路として通信経路番号が「3」の経路を選択すると、該通信経路に対応する通信インターフェース名である「S-IF#2」を経路⇔通信インターフェース対応表1330から取得する。【０１３６】
次に、取得した通信インターフェース名「S-IF#2」をキーとして、IPルーティング処理部1318内にあるIFアドレス管理テーブル1322を探索し、S-IF#2に割り当てられているIPアドレス「110.1.2.3」を取得する。次に、スケジューリング部313-2は、送信IPパケットを生成するための情報(以下、送信IPパケット生成データ)を作成し、IPパケット生成部1316に渡す。【０１３７】
図１５に、送信IPパケット生成データ1510の構成を示す。「宛先IPアドレス」として受信ノード101-2の通信インターフェース1500-1のIPアドレス「200.7.8.9」が、「送信元IPアドレス」として通信インターフェースS-IF#2 1310-2のIPアドレスである「110.1.2.3」がそれぞれ格納される。【０１３８】
IPパケット生成部1316では、受け取った送信IPパケット生成データ1510を元にして、図１６に示す送出IPパケット1610を作成し、IPパケットキューイング部1317に追加する。送出IPパケット1610には、受け取った送信IPパケット生成データ1510に含まれる情報を元にして、IPヘッダの「送信元IPアドレス」フィールドには通信インターフェースであるS-IF#2 1310-2のIPアドレス「110.1.2.3」が、IPヘッダの「宛先IPアドレス」フィールドには受信ノード101-2の通信インターフェースであるR-IF 1500-1のIPアドレス「200.7.8.9」が、それぞれ格納される。【０１３９】
次に、IPルーティング処理部1318にある送信IF判定・送出処理部1320は、IPパケットキューイング部1317から送出IPパケット1610を取り出し、経路制御テーブル1321とIFアドレス管理テーブル1322とを用いて、送出IPパケットを受け渡す通信インターフェースを決定し、送出処理を実行する。【０１４０】
図１７は、本実施における送信IF判定・送出処理部1320による送信IF決定の流れを表したものである。送信IF判定・送出処理部1320は、使用している経路制御テーブル1321がエントリ数xで構成されるとき、第1の条件によって探索処理を行う際に経路制御テーブル1321の何エントリ目を処理の対象としているかを表すカウンタ値iと、第1の条件によって送信候補として選択された経路制御テーブルのエントリを格納する配列である第1の候補リストと、第1の候補リストに格納されたエントリ数を表すカウンタ値mと、第2の条件による選択処理を行う際に第1の候補リストの何エントリ目を処理の対象としているかを表すカウンタ値jと、第2の条件によって送信候補として選択された送信インターフェースを格納する配列である第2の候補リストと、第2の候補リストに格納されたエントリ数を表すカウンタ値nとを変数として用意している。まず、IPパケットキューイング部1317より送出IPパケット1610を取り出す(Step300)。そして、初期値としてカウンタ値i、jにそれぞれ「１」を、カウンタ値m、nにそれぞれ「0」を設定し(Step301)、Step302に進む。【０１４１】
次に、カウンタ値iとxを比較し、第1の候補探索が完了したかどうかを判定する(Step302)。具体的には、カウンタ値iとxの値が等しくなれば第1の候補探索が完了したことになる。カウンタ値iとxの値が等しくない場合(Step302：NO)、送出IPパケット1610の宛先IPアドレスに格納されている値と、経路制御テーブルi番目のエントリの宛先ネットワークIPアドレスに格納されている値との比較を行う(Step303)。比較の結果が一致となる場合(Step303：YES)、第1の候補リストm番目のエントリに経路制御テーブルi番目のエントリの内容を複写する(Step304)。そして、カウンタ値mの値を1つ増加させる(Step305)。さらに、カウンタ値iの値を1つ増加させて(Step306)、次の経路制御テーブルエントリの処理に移る。送出IPパケット1610の宛先IPアドレスに格納されている値と、経路制御テーブルi番目のエントリの宛先ネットワークIPアドレスに格納されている値とが一致しない場合(Step303：NO)、そのままStep306へ進む。【０１４２】
Step302からStep306を繰り返すことで、経路制御テーブルの第1エントリから順に各エントリについて処理が行われることになる。そして、処理が最終エントリに達すると(Step302：YES)、第1の候補リストにエントリが存在するかどうかを判定するためにStep307へ進む。【０１４３】
第1の候補が存在するかどうかは、具体的にはカウンタ値mの値によって判定される。カウンタ値mの値が「0」である場合(Step307：YES)、送出IPパケット1610を送出するための通信インターフェースが存在しないため、処理を終了する(エンド)。カウンタ値mの値が「0」以外の値である場合(Step307：NO)、第1の候補が存在することになりStep308の処理に移る。次に、カウンタ値mの値が「1」であるかどうかを判断する(Step308)。カウンタ値mの値が「1」である場合(Step308：YES)、送出IPパケット1610を送出するための通信インターフェースが一意に決定されるため、第1の候補リスト1番目のエントリに記録されている通信インターフェース取得し(Step309)、取得した通信インターフェースを用いて送出IPパケット1610を送出し(Step322)、終了する(エンド)。カウンタ値mの値が「1」でない場合(Step308：NO)、送出IPパケット1610の送出に使用する通信インターフェースが一意に決定できないため、Step310へ進む。【０１４４】
Step310では第2の候補探索が完了したかどうかを判定している。具体的には、カウンタ値jとカウンタ値mが等しくなれば第2の候補探索が完了したことになる。カウンタ値jとmが等しくない場合(Step：NO)、まず、第1の候補リストj番目のエントリの通信インターフェースを取得する(Step311)。次に、IFアドレス管理テーブル1322から、Step310で取得した通信インターフェースに対応する割当IPアドレスを取得する(Step312)。続いて、送出IPパケット1610の送信元IPアドレスとStep311で取得した割当IPアドレスを比較し(Step313)、送出IPパケット1610の送信元IPアドレスと割当IPアドレスが一致する場合(Step313：YES)、第2の候補リストn番目のエントリにStep311で取得した通信インターフェースを複写し(Step314)、カウンタ値nの値を1つ増加させる(Step315)。さらに、カウンタ値jの値を1つ増加させて(Step316)、第1の候補リストの次エントリの処理に移る。送出IPパケット1610の送信元IPアドレスと割当IPアドレスが一致しない場合(Step313：NO)、そのままStep316へ進む。【０１４５】
Step310からStep316を繰り返すことで、第1の候補リストの第1エントリから順に各エントリについて処理が行われることになる。そして、処理が最終エントリに達すると(Step310：YES)、第2の候補リストにエントリが存在するかどうかを判定するためにStep317へ進む。【０１４６】
第2の候補が存在するかどうかは、具値的にはカウンタ値nの値によって判定される。カウンタ値nの値が「0」とは、第1の候補リストに送出IPパケット1610の送出が可能な通信インターフェースが存在するが、一意には決定されていないことを意味する。カウンタ値nの値が「１」とは、送出IPパケット1610の送出が可能な通信インターフェースが一意に決定されることを意味する。カウンタ値nの値が「2」以上の場合とは、第2の候補リストに送出IPパケット1610の送出が可能な通信インターフェースが存在するが、一意に決定されていないことを意味する。【０１４７】
カウンタ値nの値が「1」である場合(Step317：YES)、第2の候補リスト1番目エントリから通信インターフェースを取得し(Step318)、取得した通信インターフェースを用いて送出IPパケット1610を送出し(Step322)、終了する(エンド)。カウンタ値nの値が「1」で無い場合(Step317：NO)、Step319へ進む。【０１４８】
次に、カウンタ値nの値が「0」である場合(Step319：YES)、第1の候補リストの任意のエントリから送信インターフェースを取得し(Step320)、取得した送信インターフェースを用いて送出IPパケット1610を送出し(Step322)、終了する(エンド)。カウンタ値nの値が「0」で無い場合(Step319：NO)、第2の候補リストの任意のエントリから送信インターフェースを取得し(Step321)、取得した送信インターフェースを用いて送出IPパケット1610を送出し(Step322)、終了する(エンド)。【０１４９】
ここでは、送出IPパケット1610のIPヘッダ内の宛先IPアドレスには「200.7.8.9」が、送信元IPアドレスには「110.1.2.3」がそれぞれ格納されている。したがって、第1の候補としては、図２１に示す経路制御テーブル1321のエントリである1321-a、1321-b、1321-cが該当し、Step307の処理を実行する段階では、第1の候補リスト1番目のエントリには経路制御テーブル1321のエントリ1321-aの内容が、第1の候補リスト２番目のエントリには経路制御テーブル1321のエントリ1321-bの内容が、第1の候補リスト3番目のエントリには経路制御テーブル1321のエントリ1321-cの内容がそれぞれ格納される。また、カウンタ値mには「3」が格納される。さらに、Step312の処理においては、j=1の場合は「100.1.2.3」が、j=2の場合は「110.1.2.3」が、j=3の場合は「120.1.2.3」が、それぞれ割当IPアドレスとして取得される。さらに、Step317の処理を実行する段階では、第2の候補リストには送信インターフェースとして「S-IF#2」のみが格納され、カウンタ値には「1」が格納される。すなわち、Step317の処理による判定の結果、Step318の処理が実行されることとなり、Step318では送信インターフェースとして「S-IF#2」が取得され、送信IF判定・送出処理部1320は、スケジューリング部313-2が選択した経路番号「3」の経路に対応する通信インターフェースであるS-IF#2 1310-2を用いて送出IPパケット1610の送出が行われることになる。【０１５０】
結果として、送出IPパケット1610は、通信インターフェースであるS-IF#2 1310-2から送出され、キャリア網GW1400-3を介し、受信ノード101-2が装備する通信インターフェースであるR-IF 1500-1により受信されることとなる。【０１５１】
以上に説明した手順を行うことにより、本実施の形態のような、送信ノード100-2と受信ノード101-2がそれぞれ1対1に対応しない複数の通信インターフェースを装備し、かつ各通信インターフェースには個別のIPアドレスが割り当てられているIPネットワーク構成の場合においても、スケジューリング部313-2で決定された経路を利用してIPパケットを送信することが可能となる。また、送信元IPアドレスが特に格納されていない、従来技術でのIPルーティングを期待しているIPパケットに対しても、IPルーティング処理を行うことも可能である。【０１５２】
また、さらに他の実施として、送信ノード100-2の内部構成の場合において、スケジューリング部313-2が、通信経路として通信経路番号が「3」の経路を選択した後、IPパケット生成部1316に渡す送信IPパケット生成データとして図１８に示す形式とすることも可能である。【０１５３】
図１８に、本実施における送信IPパケット生成データ1511を示す。スケジューリング部313-2は、送信IPパケット生成データ1511の「宛先IPアドレス」として受信ノード101-2の通信インターフェース1500-1のIPアドレス「200.7.8.9」を格納し、さらに、送信IPパケット生成データ1510の「送信元インターフェース」として、経路⇔通信インターフェース対応表1330より取得された、通信経路番号「3」に対応する通信インターフェース名「S-IF#2」を格納する。【０１５４】
IPパケット生成部1316は、送信IPパケット生成データ1511を受け取ると、図１９に示す送出IPパケット1611を作成し、IPパケットキューイング部1317に追加する。送出IPパケット1611には、受け取った送信IPパケット生成データ1511に含まれる情報を元にして、IPヘッダの「送信元IPアドレス」フィールドには通信インターフェース名である「S-IF#2」が、IPヘッダの「宛先IPアドレス」フィールドには受信ノード101-2の通信インターフェースであるR-IF 1500-1のIPアドレス「200.7.8.9」が、それぞれ格納される。【０１５５】
次に、IPルーティング処理部1318にある送信IF判定・送出処理部1320は、IPパケットキューイング部1317から送出IPパケット1611を取り出し、経路制御テーブル1321とIFアドレス管理テーブル1322とを用いて、送出IPパケットを受け渡す通信インターフェースを決定し、送出処理を実行する。【０１５６】
図２０は、本実施における送信IF判定・送出処理部1320による送信IF決定の流れを表したものである。本実施においても、送信IF判定・送出処理部1320は、使用している経路制御テーブル1321がエントリ数xで構成されるとき、第1の条件によって探索処理を行う際に経路制御テーブル1321の何エントリ目を処理の対象としているかを表すカウンタ値iと、第1の条件によって送信候補として選択された経路制御テーブルのエントリを格納する配列である第1の候補リストと、第1の候補リストに格納されたエントリ数を表すカウンタ値mと、第2の条件による選択処理を行う際に第1の候補リストの何エントリ目を処理の対象としているかを表すカウンタ値jと、第2の条件によって送信候補として選択された送信インターフェースを格納する配列である第2の候補リストと、第2の候補リストに格納されたエントリ数を表すカウンタ値nとを変数として用意している。まず、IPパケットキューイング部1317より送出IPパケット1611を取り出す(Step400)。そして、初期値としてカウンタ値i、jにそれぞれ「１」を、カウンタ値m、nにそれぞれ「0」を設定し(Step401)、Step402に進む。【０１５７】
次に、カウンタ値iとxを比較し、第1の候補探索が完了したかどうかを判定する(Step402)。具体的には、カウンタ値iとxの値が等しくなれば第1の候補探索が完了したことになる。カウンタ値iとxの値が等しくない場合(Step402：NO)、送出IPパケット1611の宛先IPアドレスに格納されている値と、経路制御テーブルi番目のエントリの宛先ネットワークIPアドレスに格納されている値との比較を行う(Step403)。比較の結果が一致となる場合(Step403：YES)、第1の候補リストm番目のエントリに経路制御テーブルi番目のエントリの内容を複写する(Step404)。そして、カウンタ値mの値を1つ増加させる(Step405)。さらに、カウンタ値iの値を1つ増加させて(Step406)、次の経路制御テーブルエントリの処理に移る。送出IPパケット1611の宛先IPアドレスに格納されている値と、経路制御テーブルi番目のエントリの宛先ネットワークIPアドレスに格納されている値とが一致しない場合(Step403：NO)、そのままStep406へ進む。【０１５８】
Step402からStep406を繰り返すことで、経路制御テーブルの第1エントリから順に各エントリについて処理が行われることになる。そして、処理が最終エントリに達すると(Step402：YES)、第1の候補リストにエントリが存在するかどうかを判定するためにStep407へ進む。【０１５９】
第1の候補が存在するかどうかは、具体的にはカウンタ値mの値によって判定される。カウンタ値mの値が「0」である場合(Step407：YES)、送出IPパケット1611を送出するための通信インターフェースが存在しないため、処理を終了する(エンド)。カウンタ値mの値が「0」以外の値である場合(Step407：NO)、第1の候補が存在することになりStep408の処理に移る。次に、カウンタ値mの値が「1」であるかどうかを判断する(Step408)。カウンタ値mの値が「1」である場合(Step408：YES)、送出IPパケット1611を送出するための通信インターフェースが一意に決定されるため、第1の候補リスト1番目のエントリに記録されている通信インターフェース取得し(Step409)、取得した通信インターフェースを用いて送出IPパケット1611を送出し(Step422)、終了する(エンド)。カウンタ値mの値が「1」でない場合(Step408：NO)、送出IPパケット1611の送出に使用する通信インターフェースが一意に決定できないため、Step410へ進む。【０１６０】
Step410では第2の候補探索が完了したかどうかを判定している。具体的には、カウンタ値jとカウンタ値mが等しくなれば第2の候補探索が完了したことになる。カウンタ値jとmが等しくない場合(Step：NO)、まず、第1の候補リストj番目のエントリの通信インターフェースを取得する(Step411)。次に、送出IPパケット1611の送信元IPアドレスに格納されている通信インターフェースと、Step411で取得した通信インターフェースとを比較し(Step412)、一致する場合(Step412：YES)、第2の候補リストn番目のエントリにStep411で取得した通信インターフェースを複写し(Step413)、カウンタ値nの値を1つ増加させる(Step414)。さらに、カウンタ値jの値を1つ増加させて(Step415)、第1の候補リストの次エントリの処理に移る。送出IPパケット1611の送信元IPアドレスに格納されたインターフェースとStep411で取得した通信インターフェースとが一致しない場合(Step412：NO)、そのままStep415へ進む。【０１６１】
Step410からStep415を繰り返すことで、第1の候補リスト1番目のエントリから順に各エントリについて処理が行われることになる。そして、処理が最終エントリに達すると(Step410：YES)、第2の候補リストにエントリが存在するかどうかを判定するためにStep417へ進む。【０１６２】
第2の候補が存在するかどうかは、具値的にはカウンタ値nの値によって判定される。カウンタ値nの値が「0」とは、第1の候補リストに送出IPパケット1611の送出が可能な通信インターフェースが存在するが、一意には決定されていないことを意味する。カウンタ値nの値が「１」とは、送出IPパケット1611の送出が可能な通信インターフェースが一意に決定されることを意味する。カウンタ値nの値が「2」以上の場合とは、第2の候補リストに送出IPパケット1611の送出が可能な通信インターフェースが存在するが、一意に決定されていないことを意味する。【０１６３】
カウンタ値nの値が「1」である場合(Step416：YES)、第2の候補リスト1番目のエントリから通信インターフェースを取得し(Step417)、取得した通信インターフェースを用いて送出IPパケット1611を送出し(Step421)、終了する(エンド)。カウンタ値nの値が「1」で無い場合(Step416：NO)、Step419へ進む。【０１６４】
次に、カウンタ値nの値が「0」である場合(Step418：YES)、第1の候補リストの任意のエントリから送信インターフェースを取得し(Step419)、取得した送信インターフェースを用いて送出IPパケット1611を送出し(Step421)、終了する(エンド)。カウンタ値nの値が「0」で無い場合(Step418：NO)、第2の候補リストの任意のエントリから送信インターフェースを取得し(Step420)、取得した送信インターフェースを用いて送出IPパケット1611を送出し(Step421)、終了する(エンド)。【０１６５】
ここでは、送出IPパケット1611のIPヘッダ内の宛先IPアドレスには「200.7.8.9」が、送信元IPアドレスには実際にはIPアドレスではない識別子である「S-IF#2」がそれぞれ格納されている。したがって、第1の候補としては、経路制御テーブル1321のエントリである1321-a、1321-b、1321-cが該当し、Step407の処理を実行する段階では、第1の候補リスト1番目のエントリには経路制御テーブル1321のエントリ1321-aの内容が、第1の候補リスト２番目のエントリには経路制御テーブル1321のエントリ1321-bの内容が、第1の候補リスト3番目のエントリには経路制御テーブル1321のエントリ1321-cの内容がそれぞれ格納される。また、カウンタ値mには「3」が格納される。さらに、Step416の処理を実行する段階では、第2の候補リストには送信インターフェースとして「S-IF#2」のみが格納され、カウンタ値には「1」が格納される。すなわち、Step417の処理による判定の結果、Step418の処理が実行されることとなり、Step418では送信インターフェースとして「S-IF#2」が取得され、送信IF判定・送出処理部1320は、スケジューリング部313-2が選択した経路番号「3」の経路に対応する通信インターフェースであるS-IF#2 1310-2を用いて送出IPパケット1611の送出が行われることになる。【０１６６】
結果として、送出IPパケット1611は、通信インターフェースであるS-IF#2 1310-2から送出され、キャリア網GW1400-3を介し、受信ノード101-2が装備する通信インターフェースであるR-IF 1500-1により受信されることとなる。【０１６７】
以上に説明した手順を行うことにより、本実施の形態においても、送信ノード100-2と受信ノード101-2がそれぞれ1対1に対応しない複数の通信インターフェースを装備し、かつ各通信インターフェースには個別のIPアドレスが割り当てられているIPネットワーク構成の場合においても、スケジューリング部313-2で決定された経路を利用してIPパケットを送信することが可能となる。【０１６８】
また、通信インターフェースが特に指定されていない、従来技術でのIPルーティングを期待しているIPパケットに対しても、IPルーティング処理を行うことも可能である。【０１６９】
尚、上述の実施の形態において、送信ノードのキューイング部、スケジューリング部及び経路状態監視部をそれぞれ別の部として構成したが、これらの全部又は一部を、制御プログラムで動作するＣＰＵ等で構成しても良い。
【図１】
0004396859.tif 000002
【図２】
0004396859.tif 000003
【図３】
0004396859.tif 000004
【図４】
0004396859.tif 000005
【図５】
0004396859.tif 000006
【図６】
0004396859.tif 000007
【図７】
0004396859.tif 000008
【図８】
0004396859.tif 000009
【図９】
0004396859.tif 000010
【図１０】
0004396859.tif 000011
【図１１】
0004396859.tif 000012
【図１２】
0004396859.tif 000013
【図１３】
0004396859.tif 000014
【図１４】
0004396859.tif 000015
【図１５】
0004396859.tif 000016
【図１６】
0004396859.tif 000017
【図１７】
0004396859.tif 000018
【図１８】
0004396859.tif 000019
【図１９】
0004396859.tif 000020
【図２０】
0004396859.tif 000021
【図２１】
0004396859.tif 000022