(57)【特許請求の範囲】
【請求項１】
第１の情報処理装置に、
前記第１の情報処理装置と、１又は複数のデータブロックの送信先である第２の情報処理装置との間のネットワークにおいて輻輳が発生したことを検出し、
前記１又は複数のデータブロックの各々について送信時刻及び送達期限を格納するデータ格納部に格納されたデータに基づき、現タイムスロットにおいて送信される１又は複数のデータブロックのうち送信時刻から送達期限までの時間が所定時間より長いという条件を満たす第１のデータブロックを特定し、
前記第１のデータブロックの送達期限を含み且つ前記第１のデータブロックの送信時刻を再設定することを要求する第１の要求を、前記第２の情報処理装置に送信し、
前記第２の情報処理装置から、前記第２の情報処理装置により設定された送信時刻を受信する、
処理を実行させるデータ送信プログラム。
【請求項２】
前記輻輳が発生したことを検出する処理において、
前記１又は複数のデータブロックの合計サイズが減少する速度から送出レートを算出し、
算出された前記送出レートが第１の閾値未満である場合に、前記ネットワークにおいて輻輳が発生したと決定する
請求項１記載のデータ送信プログラム。
【請求項３】
前記輻輳が発生したことを検出する処理において、
前記第１の情報処理装置と前記第２の情報処理装置との間のレイテンシが第２の閾値を超えたか判断し、
前記第１の情報処理装置と前記第２の情報処理装置との間のレイテンシが前記第２の閾値を超えたと判断された場合に、前記ネットワークにおいて輻輳が発生したと決定する
請求項１記載のデータ送信プログラム。
【請求項４】
前記第２の情報処理装置により設定された送信時刻は、
前記第１のデータの送達期限までであって且つ前記第２の情報処理装置の受信リソースに空きがある時刻である
請求項１乃至３のいずれか１つ記載のデータ送信プログラム。
【請求項５】
前記第１の情報処理装置に、
前記ネットワークにおいて輻輳が発生したことを検出した場合、前記第１の情報処理装置と同じグループに属する第３の情報処理装置に、前記第１の情報処理装置に割り当てられた優先度を送信し、
前記第１の情報処理装置に割り当てられた優先度より低い優先度を前記第３の情報処理装置から受信するか判断する、
処理をさらに実行させ、
前記第１の要求を前記第２の情報処理装置に送信する処理において、
前記第３の情報処理装置から優先度を受信しない場合又は前記第１の情報処理装置に割り当てられた優先度より低い優先度を前記第３の情報処理装置から受信した場合、前記第１の要求を前記第２の情報処理装置に送信する、
請求項１乃至４のいずれか１つ記載のデータ送信プログラム。
【請求項６】
前記第１の情報処理装置に、
前記第１の情報処理装置と、前記第１の情報処理装置に対して１又は複数のデータブロックを送信する第４の情報処理装置との間の第２のネットワークにおける輻輳の状態を特定し、
前記第４の情報処理装置から、当該１又は複数のデータブロックの送信時刻を設定することを要求する第２の要求を受信し、
前記第１の情報処理装置の受信リソースに空きがあり且つ特定された前記輻輳の回避が可能である、前記１又は複数のデータブロックの送信時刻を設定し、
設定された前記１又は複数のデータブロックの送信時刻を、前記第４の情報処理装置に送信する
処理をさらに実行させる請求項１乃至５のいずれか１つ記載のデータ送信プログラム。
【請求項７】
前記第１の情報処理装置に、
各データブロックについて当該データブロックに関連するデータブロックの識別子を格納する第２データ格納部を用いて、前記第１のデータブロックに関連するデータブロックである第２のデータブロックを抽出する、
処理をさらに実行させ、
前記第１の要求は、
前記第１のデータブロックの送信時刻及び前記第２のデータブロックの送信時刻を再設定するための要求である
請求項１乃至６のいずれか１つ記載のデータ送信プログラム。
【請求項８】
第１の情報処理装置が、
前記第１の情報処理装置と、１又は複数のデータブロックの送信先である第２の情報処理装置との間のネットワークにおいて輻輳が発生したことを検出し、
前記１又は複数のデータブロックの各々について送信時刻及び送達期限を格納するデータ格納部に格納されたデータに基づき、現タイムスロットにおいて送信される１又は複数のデータブロックのうち送信時刻から送達期限までの時間が所定時間より長いという条件を満たす第１のデータブロックを特定し、
前記第１のデータブロックの送達期限を含み且つ前記第１のデータブロックの送信時刻を再設定することを要求する第１の要求を、前記第２の情報処理装置に送信し、
前記第２の情報処理装置から、前記第２の情報処理装置により設定された送信時刻を受信する、
処理を実行するデータ送信方法。
【請求項９】
情報処理装置であって、
１又は複数のデータブロックの各々について送信時刻及び送達期限を格納するデータ格納部と、
前記情報処理装置と、前記１又は複数のデータブロックの送信先である他の情報処理装置との間のネットワークにおいて輻輳が発生したことを検出し、前記データ格納部に格納されたデータに基づき、現タイムスロットにおいて送信される１又は複数のデータブロックのうち送信時刻から送達期限までの時間が所定時間より長いという条件を満たす第１のデータブロックを特定する特定部と、
前記第１のデータブロックの送達期限を含み且つ前記第１のデータブロックの送信時刻を再設定することを要求する第１の要求を、前記他の情報処理装置に送信し、前記他の情報処理装置から、前記他の情報処理装置により設定された送信時刻を受信する通信部と、
を有する情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノード間におけるデータ送信のスケジューリング技術に関する。
【背景技術】
【０００２】
利用者の属性や状況に応じた適切な広告を配信するシステム（例えば、行動ターゲッティング広告のシステム）が知られている。このシステムは、利用者の好み（例えば購買履歴）や状況（例えば気温）などに応じてお勧めの広告を決定し、街頭に設置されたディスプレイ等に表示するシステムである。
【０００３】
このようなシステムにおいては、ディスプレイ等が設置された地点に利用者が到着するまでに、利用者に関連する情報をその地点に送り届け終えることが前提となっている。但し、利用者がその地点に到着する時刻より長時間前に情報を送り届けると、その地点に有る記憶装置の容量を長時間消費することになる。従って、単に情報を早く送り届ければよいというわけではない。
【０００４】
上記のようなサービスに関し、或る文献は以下のような技術を開示する。具体的には、コンテンツを送信先の装置に送信する時刻（以下、送信時刻と呼ぶ）をコンテンツ毎に算出し、コンテンツの送信時刻に基づき送信スケジュールを管理する。これにより、ユーザが到着するまでにコンテンツを送り届けることを可能にする。
【０００５】
しかし、上記の技術においては、複数のコンテンツの送信時刻が特定の時間帯に集中すると、ネットワークにおいて輻輳が発生し、コンテンツを目標の時刻までに送り届けることができなくなる。
【０００６】
このような輻輳の問題については、その他の文献においても十分な検討が行われていない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】国際公開第２０１１／１０２２９４号パンフレット
【特許文献２】特開平８−８８６４２号公報
【特許文献３】特開２０１３−２５４３１１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
従って、本発明の目的は、１つの側面では、データ送信の遅延を抑制するための技術を提供することである。
【課題を解決するための手段】
【０００９】
本発明に係るデータ送信方法は、第１の情報処理装置と、１又は複数のデータブロックの送信先である第２の情報処理装置との間のネットワークにおいて輻輳が発生したことを検出し、１又は複数のデータブロックの各々について送信時刻及び送達期限を格納するデータ格納部に格納されたデータに基づき、送信時刻から送達期限までの時間が所定時間より長いという条件を満たす第１のデータブロックを特定し、第１のデータブロックの送達期限を含み且つ第１のデータブロックの送信時刻を再設定することを要求する第１の要求を、第２の情報処理装置に送信し、第２の情報処理装置から、第２の情報処理装置により設定された送信時刻を受信する処理を含む。
【発明の効果】
【００１０】
１つの側面では、データ送信の遅延を抑制できるようになる。
【図面の簡単な説明】
【００１１】
【図１】図１は、第１の実施の形態に係るシステムの概要を示す図である。
【図２】図２は、第１の実施の形態等に係る変数を説明するための図である。
【図３】図３は、第１の実施の形態に係るタイムスロットを説明するための図である。
【図４Ａ】図４Ａは、第１の実施の形態の処理概要を説明するための図である。
【図４Ｂ】図４Ｂは、第１の実施の形態の処理概要を説明するための図である。
【図４Ｃ】図４Ｃは、第１の実施の形態の処理概要を説明するための図である。
【図４Ｄ】図４Ｄは、第１の実施の形態の処理概要を説明するための図である。
【図４Ｅ】図４Ｅは、第１の実施の形態の処理概要を説明するための図である。
【図４Ｆ】図４Ｆは、第１の実施の形態の処理概要を説明するための図である。
【図４Ｇ】図４Ｇは、第１の実施の形態の処理概要を説明するための図である。
【図５】図５は、第１の実施の形態に係るノードの構成例を示す図である。
【図６】図６は、第１の実施の形態に係るノードが受信するメッセージのフォーマット例を示す図である。
【図７】図７は、第１の実施の形態に係るノードが受信するメッセージのフォーマット例を示す図である。
【図８】図８は、レイテンシデータ格納部に格納されるデータのフォーマット例を示す図である。
【図９】図９は、リンクデータ格納部に格納されるデータのフォーマット例を示す図である。
【図１０】図１０は、データ転送ルート格納部に格納されるデータのフォーマット例を示す図である。
【図１１Ａ】図１１Ａは、データキューのデータ構造例を示す図である。
【図１１Ｂ】図１１Ｂは、データキューのデータ構造例を示す図である。
【図１２】図１２は、リソース管理データ格納部に格納されるデータのフォーマット例を示す図である。
【図１３】図１３は、リソース管理データ格納部に格納されるデータのフォーマット例を示す図である。
【図１４】図１４は、スケジューリングデータ格納部に格納されるデータのフォーマット例を示す図である。
【図１５】図１５は、第１の実施の形態に係るデータ受信時における処理フローを示す図である。
【図１６】図１６は、スケジュールネゴシエータが実行する処理の処理フローを示す図である。
【図１７】図１７は、スケジューリング要求のデータフォーマット例を示す図である。
【図１８】図１８は、ＪＳＯＮ形式におけるスケジューリング要求の例を示す図である。
【図１９】図１９は、スケジュールネゴシエータが実行する処理の処理フローを示す図である。
【図２０】図２０は、データ送信部が実行する処理の処理フローを示す図である。
【図２１】図２１は、第２スケジューラが実行する処理の処理フローを示す図である。
【図２２】図２２は、スケジューリング処理部の処理内容を説明するための図である。
【図２３】図２３は、第２スケジューラが実行する処理の処理フローを示す図である。
【図２４】図２４は、メッセージのソートを説明するための図である。
【図２５】図２５は、メッセージのソートを説明するための図である。
【図２６】図２６は、第２スケジューラが実行する処理の処理フローを示す図である。
【図２７】図２７は、第２スケジューラが実行する処理の処理フローを示す図である。
【図２８】図２８は、メッセージのソートを説明するための図である。
【図２９】図２９は、第１の実施の形態における監視部が実行する処理の処理フローを示す図である。
【図３０】図３０は、第１の実施の形態における輻輳回避処理の処理フローを示す図である。
【図３１】図３１は、第３スケジューラが実行する処理の処理フローを示す図である。
【図３２】図３２は、第２の実施の形態におけるノードの構成例を示す図である。
【図３３】図３３は、第２レイテンシデータ格納部に格納されるデータの一例を示す図である。
【図３４】図３４は、第２の実施の形態における監視部が実行する処理の処理フローを示す図である。
【図３５】図３５は、第３の実施の形態の概要について説明するための図である。
【図３６】図３６は、第３の実施の形態におけるノードの構成例を示す図である。
【図３７】図３７は、優先度格納部に格納されるデータの一例を示す図である。
【図３８】図３８は、隣接ノードデータ格納部に格納されるデータの一例を示す図である。
【図３９】図３９は、優先度の情報を交換するためのメッセージのフォーマットの一例を示す図である。
【図４０】図４０は、輻輳の検出を通知するためのメッセージのフォーマットの一例を示す図である。
【図４１】図４１は、優先度管理部が実行する処理の処理フローを示す図である。
【図４２】図４２は、優先度管理部が実行する処理の処理フローを示す図である。
【図４３Ａ】図４３Ａは、優先度の交換について説明するための図である。
【図４３Ｂ】図４３Ｂは、優先度の交換について説明するための図である。
【図４４】図４４は、第３の実施の形態における輻輳回避処理の処理フローを示す図である。
【図４５】図４５は、第３の実施の形態における輻輳回避処理の処理フローを示す図である。
【図４６】図４６は、第４の実施の形態におけるノードの構成例を示す図である。
【図４７】図４７は、第３レイテンシデータ格納部に格納されるデータの一例を示す図である。
【図４８】図４８は、第３の実施の形態における第２スケジューラが実行する処理の処理フローを示す図である。
【図４９】図４９は、第３の実施の形態における第２スケジューラが実行する処理の処理フローを示す図である。
【図５０Ａ】図５０Ａは、第２スケジューラの処理内容を説明するための図である。
【図５０Ｂ】図５０Ｂは、第２スケジューラの処理内容を説明するための図である。
【図５１】図５１は、第５の実施の形態におけるノードの構成例を示す図である。
【図５２】図５２は、関連データ格納部に格納されるデータの一例を示す図である。
【図５３】図５３は、第５の実施の形態における輻輳回避処理の処理フローを示す図である。
【図５４】図５４は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１２】
［実施の形態１］
本発明の第１の実施の形態に係るシステムの概要を図１に示す。図１におけるデータ収集配信システムは、複数のノードＡ乃至Ｃを含む。ノードＡ及びＢは、センサなどのデータソースからデータを受信して、ノードＣに送信する。ノードＣは、データを処理する１又は複数のアプリケーションに出力する。
【００１３】
本実施の形態に係るデータ収集配信システムに含まれるノードの数は３に限定されるものではなく、データソースからアプリケーションまでの間に設けられるノードの段数も２に限定されるものではなく、２以上であればよい。すなわち、本実施の形態では、複数段構成になるようにノードが接続される。
【００１４】
ここで以下の説明で用いる変数の定義について説明しておく。ここでは、以下の説明を分かりやすくするために、図２に示すように、ノードＮｄa乃至Ｎｄcによる３段構成になっているものとする。
【００１５】
図２に示すように、ノードＮｄaとノードＮｄbとの間にはリンクＬa,bが設けられ、ノードＮｄbとノードＮｄcとの間にはリンクＬb,cが設けられている。そして、リンクＬa,bのデータ転送遅延（レイテンシ）をｌa,bと表し、リンクＬb,cのデータ転送遅延をｌb,cと表す。
【００１６】
このとき、データｄj（データのサイズはｓjバイトと表すものとする）の転送ルートが［Ｌa,b，Ｌb,c］であるとすると、ノードＮｄaからノードＮｄcまでのエンドツーエンド（end to end）のタイムリミット（time limit。到達期限又は送達期限とも呼ぶ。）をｔlim,jと表すものとする。また、データｄjの、ノードＮｄaでの送信期限ｔlim,j,aは、ｔlim,j−ｓｕｍ（［ｌa,b，ｌb,c］）（ｓｕｍは総和を表す）となる。同様に、データｄjの、ノードＮｄbでの送信期限ｔlim,j,bは、ｔlim,j−ｌb,cとなる。
【００１７】
なお、リンクＬa,bの帯域（ｂｐｓ（bit per second））をｃa,bと表す。
【００１８】
また、以下で説明するタイムスロットについても、図３を用いて説明する。タイムスロットの幅をΔｔと表し、ｉ番目のタイムスロットをｔiと表す。また、１度にスケジューリングを行うタイムスロットの数をｗと表すと、スケジューリングの幅（すなわちスケジューリングウィンドウ）はｗΔｔとなる。なお、ノードＮｄxにおいてスケジューリング要求を行う処理の周期（起動１と起動２の間隔、起動２と起動３の間隔）をＴSR,xと表し、スケジューリング要求を行う処理の起動から、スケジューリング対象のスケジューリングウィンドウの先頭時刻との差をＭxと表すものとする。なお、ノードＮｄxにおいて、スケジューリング要求を処理する側の処理の周期をＴTLS-inter,xと表すものとする。
【００１９】
本実施の形態では、図４Ａで示すように、ノードＡでの送信スケジュールと、ノードＢでの送信スケジュールとを、ノードＣに送信する。送信スケジュールは、スケジューリングウィンドウ（ここではｗ＝４）内の各スロットにおいて送信すべきデータに関する情報を含んでいる。具体的には、宛先までの送達期限ｔlim,j及び送信元のノードにおける送信期限ｔlim,j,xを含む。図４Ａでは、４つのタイムスロットの各々に割り当てられたデータをブロック状に示しており、以下１塊のデータをデータブロックと呼ぶものとする。
【００２０】
ノードＣは、ノードＡ及びＢから送信スケジュールを受信すると、図４Ｂに示すように送信スケジュールを重ね合わせて、各タイムスロットにおいてノードＣの受信リソース以内に送信されるデータが収まっているか否かを判断する。図４Ｂの例では、６つのデータブロックまで１タイムスロット内で受信できるものとする。そうすると３つ目のタイムスロットでは、１つのデータブロックが受信できないことが分かる。そうすると、３つ目のタイムスロットに割り当てられているデータブロックを、ｔlim,j,x及びｔlim,jでソートし、データブロックの優先順位付けを行う。ノードＣは、優先順位に基づきデータブロックを選択して、他のタイムスロットにスケジュールし直すが、図４Ｃに示すように、ここでは受信リソースが余っている１つ手前のタイムスロットに、選択されたデータブロックを割り当てる。そして、ノードＣは、このようなスケジューリングの結果をノードＡ及びノードＢに返信する。図４Ｄに示すように、ノードＢのスケジューリング結果は、元の送信スケジュールと同じであるが、ノードＡのスケジューリング結果は、２番目のタイムスロットと３番目のタイムスロットとで異なっている。ノードＡ及びＢは、このようなスケジューリング結果に従って、データブロックを送信する。
【００２１】
さらに、本実施の形態においては、輻輳が発生した場合において適切なスケジューリングを行うようにする。例えば図４Ｅに示すようなシステムを考える。図４Ｅにおいては、ネットワークにノードＶ乃至Ｚが接続されており、ノードＸがネットワークを介してノードＶにデータを転送し、ノードＹ及びＺがネットワークを介してノードＷにデータを転送する。ノードＹによるデータ転送をデータ転送（１）と呼び、ノードＺによるデータ転送をデータ転送（２）と呼び、ノードＸによるデータ転送をデータ転送（３）と呼ぶ。
【００２２】
図４Ｆに、図４Ｅに示したシステムのネットワークトラフィック量を示す。図４Ｆにおいては、縦軸はネットワークトラフィック量を表し、横軸は時間を表す。点線はデータ転送（１）のネットワークトラフィック量を表し、実線はデータ転送（１）及び（２）のネットワークトラフィック量の合計を表し、太線はデータ転送（１）、（２）及び（３）のネットワークトラフィック量の合計を表す。Network Capacityは、遅延することなく転送可能なデータ量を表し、ネットワークトラフィック量がNetwork Capacityを超える場合には輻輳が発生している。図４Ｆに示すように、データ転送（１）、（２）及び（３）が行われると、ネットワークにおいて一時的に輻輳が発生する。輻輳が発生している間は、送信したデータを遅延することなく送信先まで届けることができない。
【００２３】
そこで本実施の形態においては、輻輳が発生した場合には一部のデータブロックの送信を遅らせることで、輻輳を回避したデータ送信を可能にする。図４Ｇを用いて、輻輳を回避するためのスケジューリングについて説明する。例えば、時刻ｔから時刻ｔ＋Δｔの間で輻輳が発生しているとする。このような場合には、ノードＸがノードＶに対し再スケジューリングを要求する。そして、ノードＶは、図４Ｇに示すように、２つのデータブロックの送信を時刻ｔ＋４Δｔから時刻ｔ＋５Δｔの間に行うようにスケジュールを変更する。ここで、２つのデータブロックの送信期限がｔ＋５Δｔより後であるようにし、また、送達期限までにデータブロックを送り届けることができるようにスケジュールを変更する。これにより、輻輳を回避しつつ、送信期限を徒過しないようにデータブロックを送信できるようになる。
【００２４】
次に、このような処理を行うためのノードＡ乃至Ｃの構成例を図５に示す。ノードは、データ受信部１０１と、第１スケジューラ１０２と、リンクデータ格納部１０３と、データ転送ルート格納部１０４と、第１レイテンシデータ格納部１０５と、データキュー１０６と、データ送信部１０７と、第１スケジュールネゴシエータ１０８と、第２スケジューラ１０９と、リソース管理データ格納部１１０と、スケジューリングデータ格納部１１１と、第３スケジューラ１１３と、監視部１１５と、第２スケジュールネゴシエータ１１７とを有する。
【００２５】
データ受信部１０１は、他のノードやデータソースからメッセージを受信する。なお、ノード自身が、メッセージに含まれるデータに対して処理を行う場合には、データ受信部１０１の前段で処理を行うものとする。本実施の形態において、データ受信部１０１が受信するメッセージのフォーマット例を図６及び図７に示す。データソースから受信したメッセージの場合には、図６に示すように、データのＩＤ（ｄj）と、データの宛先次ノード（直接の送信先のノード）のＩＤと、データ本体とを含む。データ本体はデータのＩＤを含む場合もある。また、宛先次ノードのＩＤではなく、宛先次ノードを特定するためのキーを含むようにして、当該キーから宛先次ノードのＩＤを特定するためのデータ構造を利用して宛先次ノードのＩＤを特定しても良い。
【００２６】
なお、他のノードから受信したメッセージの場合には、図７に示すように、データのＩＤと、データの宛先次ノードのＩＤと、データｄjの宛先までの送達期限ｔlim,jと、データ本体とを含む。
【００２７】
第１レイテンシデータ格納部１０５は、図８に示すように、データのＩＤ毎に、当該データ発生から宛先までの送達に許容される遅延時間を格納している。
【００２８】
また、リンクデータ格納部１０３は、図９に示すように、リンクＩＤ毎に、送信元（Source）ノードのＩＤと、宛先（Destination）ノードのＩＤと、当該リンクの遅延時間とを格納している。
【００２９】
また、データ転送ルート格納部１０４は、図１０に示すように、データのＩＤ毎に、当該データが経由する転送ルートのリンクＩＤ配列（［Ｌ1,2，Ｌ2,3，．．．，Ｌn-1,n］）を格納している。
【００３０】
第１スケジューラ１０２は、リンクデータ格納部１０３とデータ転送ルート格納部１０４と第１レイテンシデータ格納部１０５とを用いて、受信したメッセージに対して宛先までの送達期限（到着期限）を特定し、本ノードにおける送信期限を特定し、メッセージのデータと共に、データキュー１０６に格納する。
【００３１】
データキュー１０６のデータ構造例を図１１Ａ及び図１１Ｂに示す。図１１Ａの例では、開始時刻と終了時刻とで特定されるタイムスロット毎に、当該タイムスロットのためのキューへのポインタ（又はリンク）が登録されるようになっている。キューには、当該キューに投入されたメッセージ（データブロックに対応）が格納される。
【００３２】
図１１Ｂに、キューに投入されたデータのデータフォーマット例を示す。図１１Ｂの例では、データのＩＤと、宛先までの送達期限と、本ノードにおける送信期限と、データ本体又はデータへのリンクとが含まれる。
【００３３】
データ送信部１０７は、データキュー１０６に規定されているタイムスロット毎に、当該タイムスロットに割り当てられているメッセージを宛先ノードやアプリケーションに送信する。
【００３４】
第１スケジュールネゴシエータ１０８は、データキュー１０６に格納されているデータから、送信スケジュールを含むスケジューリング要求を生成し、メッセージ送信先のノードに送信する。第１スケジュールネゴシエータ１０８は、メッセージ送信先のノードからスケジューリング結果を含むスケジュール通知を受信する。そして、第１スケジュールネゴシエータ１０８は、受信したスケジューリング結果に従って、データキュー１０６の内容を更新する。
【００３５】
第２スケジューラ１０９は、他のノードからスケジューリング要求を受信してスケジューリングデータ格納部１１１に格納する。そして、第２スケジューラ１０９は、スケジューリングデータ格納部１１１に格納された複数ノードからのスケジューリング要求及びリソース管理データ格納部１１０に格納されているデータを用いて、各ノードの送信スケジュールを変更する。
【００３６】
リソース管理データ格納部１１０には、例えば図１２及び図１３で示すようなデータフォーマットでデータが格納される。すなわち、図１２の例では、開始時刻と終了時刻とで特定されるタイムスロット毎に、ノードの受信リソースの使用済み数と空き数と最大数と、当該タイムスロットについてのキュー（データリストとも呼ぶ）へのポインタとが格納される。この例では、タイムスロットの幅は１秒で、１０データブロック（すなわち１０メッセージ）を１タイムスロットで受信できるようになっている。
【００３７】
キューには、当該キューに投入された、データブロックに関する情報が格納される。但し、この情報は、図１３に示すように、データブロック毎に、データのＩＤと、送達期限ｔlim,jと、要求元ノードｘの送信期限ｔlim,j,xとを含む。
【００３８】
また、スケジューリングデータ格納部１１１には、例えば図１４に示すようなデータフォーマットでデータが格納される。すなわち、スケジューリング要求元のノードのＩＤ毎に、スケジューリング要求本体又はそれへのリンクと、スケジューリング結果とが格納される。第２スケジューラ１０９は、スケジューリングデータ格納部１１１に格納されたスケジューリング結果を、各ノードへ送信する。
【００３９】
監視部１１５は、データキュー１０６にデータが格納されたメッセージの合計サイズに基づき、ネットワークにおける輻輳を検出し、第２スケジュールネゴシエータ１１７に通知する。
【００４０】
第２スケジュールネゴシエータ１１７は、輻輳の発生を示す通知を監視部１１５から受け取った場合に、データキュー１０６に格納されているデータから、送信スケジュールを含む再スケジューリング要求を生成する。そして、第２スケジュールネゴシエータ１１７は、生成された再スケジューリング要求をメッセージ送信先のノードに送信する。そして、第２スケジュールネゴシエータ１１７は、メッセージ送信先のノードからスケジューリング結果を含むスケジュール通知を受信する。そして、第２スケジュールネゴシエータ１１７は、受信したスケジューリング結果に従って、データキュー１０６の内容を更新する。
【００４１】
第３スケジューラ１１３は、他のノードから再スケジューリング要求を受信する。そして、第３スケジューラ１１３は、受信した再スケジューリング要求、スケジューリングデータ格納部１１１に格納されたスケジューリング要求、及びリソース管理データ格納部１１０に格納されているデータを用いて、再スケジューリング要求の送信元のノードの送信スケジュールを変更する。第３スケジューラ１１３は、再スケジューリングの結果を含むスケジュール通知を、再スケジューリング要求の送信元のノードに送信する。
【００４２】
次に、図１５乃至図２８を用いて、ノードの処理内容について説明する。
【００４３】
まず、図１５を用いてメッセージ受信時の処理内容について説明する。なお、アンダーバーは、表記の問題を解決するために下付け文字を表すものとする。
【００４４】
データ受信部１０１は、データ（ｄj）を含むメッセージを受信し、第１スケジューラ１０２に出力する（ステップＳ１）。自ノードがデータソースに接続されている最上流ノードであれば（ステップＳ３：Ｙｅｓルート）、第１スケジューラ１０２は、データのＩＤ「ｄj」で第１レイテンシデータ格納部１０５を検索して、宛先までに許容される遅延時間を読み出して、送達期限ｔlim,jを取得する（ステップＳ５）。例えば、現時刻＋遅延時間にて送達期限を算出する。なお、第１レイテンシデータ格納部１０５に送達期限そのものが格納されていれば、それを用いる。一方、自ノードが最上流ノードでなければ（ステップＳ３：Ｎｏルート）、処理はステップＳ９に移行する。
【００４５】
また、第１スケジューラ１０２は、受信したメッセージヘッダに送達期限ｔlim,jを追加する（ステップＳ７）。これによって、図７に示すようなメッセージが生成される。
【００４６】
さらに、第１スケジューラ１０２は、データ転送ルート格納部１０４をｄjで検索して転送ルート［Ｌx,y］を読み出す（ステップＳ９）。転送ルートは、リンクＩＤの配列データであるものとする。
【００４７】
そして、第１スケジューラ１０２は、転送ルート［Ｌx,y］の各リンクＩＤで第１レイテンシデータ格納部１０５を検索して、各リンクの遅延時間（レイテンシ）ｌx,yを読み出す（ステップＳ１１）。
【００４８】
その後、第１スケジューラ１０２は、送達期限ｔlim,j及びレイテンシｌx,yから、本ノードの送信期限ｔlim,j,xを算出する（ステップＳ１３）。具体的には、ｔlim,j−Σｌx,y（転送経路上の全リンクについての総和）によって計算する。
【００４９】
そして、第１スケジューラ１０２は、送信期限ｔlim,j,xから送出要求時刻ｔreq,j,xを決定する（ステップＳ１５）。ｔlim,j,x＝ｔreq,j,xの場合もあれば、一定のマージンαを考慮してｔreq,j,x＝ｔlim,j,x−αと設定する場合もある。なお、以下の説明では、説明を簡単にするため、送信期限＝送出要求時刻とする。
【００５０】
そして、第１スケジューラ１０２は、送出要求時刻ｔreq,j,xのタイムスロットに、メッセージを付加データと共に投入する（ステップＳ１７）。図１１Ｂに示すようなデータが格納される。
【００５１】
以上のような処理を、メッセージを受信する毎に実行する。
【００５２】
次に、図１６乃至図２０を用いて、第１スケジュールネゴシエータ１０８の処理内容について説明する。
【００５３】
まず、第１スケジュールネゴシエータ１０８は、時間間隔ＴSR,xの起動タイミングであるか否かを判断する（図１６：ステップＳ２１）。起動タイミングでなければ処理はステップＳ２９に移行する。一方、起動タイミングであれば、第１スケジュールネゴシエータ１０８は、今回のスケジューリングウィンドウを決定する（ステップＳ２３）。具体的には、図３で説明したように、現在時刻ｔとすると、ｔ＋Ｍxからｔ＋Ｍx＋ｗΔｔまでが今回のスケジューリングウィンドウとなる。なお、本実施の形態では、システム内の全ノードが同期しているものとする。
【００５４】
そして、第１スケジュールネゴシエータ１０８は、データキュー１０６から、スケジューリングウィンドウ内のデータ（データ本体を除く）を読み出し、スケジューリング要求を生成する（ステップＳ２５）。
【００５５】
スケジューリング要求のデータフォーマット例を図１７に示す。図１７の例では、送信元ノードＩＤと、宛先ノードＩＤと、各タイムスロットのデータとが含まれる。各タイムスロットのデータは、当該タイムスロットの識別情報（例えば開始時刻−終了時刻）と、各データブロック（メッセージ）について、データのＩＤと、送達期限と、送信期限とが含まれる。
【００５６】
例えば、ＪＳＯＮ（Javascript Object Notation）形式で具体値を入れると、図１８に示すようになる。図１８の例では、第１のタイムスロットについては２つのデータブロックに関するデータが含まれ、第２のタイムスロットについても２つのデータブロックに関するデータが含まれ、最後のタイムスロットについても２つのデータブロックに関するデータが含まれる。
【００５７】
その後、第１スケジュールネゴシエータ１０８は、スケジューリング要求を、データの送信先に送信する（ステップＳ２７）。
【００５８】
そして、第１スケジュールネゴシエータ１０８は、処理終了が指示されたか判断し（ステップＳ２９）、処理終了ではない場合には処理はステップＳ２１に戻る。一方、処理終了であれば、処理を終了する。
【００５９】
このように複数のタイムスロットについてスケジューリング要求を行うことで、送信タイミングの調整が適切に行われるようになる。
【００６０】
次に、図１９及び図２０を用いて、スケジュール結果を受信した際の処理を説明する。
【００６１】
第１スケジュールネゴシエータ１０８は、スケジュール結果を含むスケジュール通知を受信する（図１９：ステップＳ３１）。スケジュール通知のデータフォーマットは、図１７及び図１８に示したようなフォーマットである。
【００６２】
そして、第１スケジュールネゴシエータ１０８は、スケジュール通知を受信すると、スケジュール通知に従って、データキュー１０６におけるメッセージ（すなわちデータブロック）が投入されるタイムスロットを更新する処理を行う（ステップＳ３３）。スケジュール通知で通知された送信スケジュールとスケジューリング要求における送信スケジュールとが一致する場合もあるので、その場合には特に処理は行わない。異なるタイムスロットに移動させられた場合には、そのタイムスロットのキューにエンキューする。そのタイムスロットのデータがなければ、この段階で生成する。
【００６３】
このようにすれば、送信先ノードにおいて調整された送信スケジュールを、データキュー１０６に反映させることができる。
【００６４】
次に、データ送信部１０７の処理内容について、図２０を用いて説明する。
【００６５】
データ送信部１０７は、タイムスロット幅Δｔの起動タイミングｔになったか否かを判断する（図２０：ステップＳ４１）。起動タイミングｔになっていない場合には、処理はステップＳ５３に移行する。一方、起動タイミングｔになると、データ送信部１０７は、データキュー１０６における時刻ｔからｔ＋Δｔのタイムスロットのキューから、メッセージ（すなわちデータブロック）を読み出す処理を行う（ステップＳ４３）。
【００６６】
ステップＳ４３でメッセージのデータを読み出すことができなければ（ステップＳ４５：Ｎｏルート）、このタイムスロットについての処理は終了することになる。
【００６７】
一方、メッセージのデータを読み出すことができれば（ステップＳ４５：Ｙｅｓルート）、データ送信部１０７は、自ノードが転送経路の末端ノードであるか否かを判断する（ステップＳ４７）。すなわち、アプリケーションにメッセージを出力するノードであるか否かを判断する。
【００６８】
そして、自ノードが末端ノードである場合には、データ送信部１０７は、読み出したメッセージに付加されている送達期限を削除する（ステップＳ４９）。一方、自ノードが末端ノードでない場合には、処理はステップＳ５１に移行する。
【００６９】
その後、データ送信部１０７は、読み出したメッセージを、送信先に送信する（ステップＳ５１）。そして、データ送信部１０７は、処理終了であるか否かを判断し（ステップＳ５３）、処理が終了でなければ処理はステップＳ４１に戻る。一方、処理が終了であれば、処理を終了する。
【００７０】
このように送信先ノードによって決定された送信スケジュールに従ってメッセージを送信できるようになる。従って、送信先ノードでは、その受信リソースで受信できるだけのデータが送信される。よって、データの遅延が抑制される。
【００７１】
次に、第２スケジューラ１０９の処理内容について、図２１乃至図２８を用いて説明する。
【００７２】
第２スケジューラ１０９は、データソースに近い各ノードから、スケジューリング要求を受信し、スケジューリングデータ格納部１１１に格納する（図２１：ステップＳ６１）。
【００７３】
そして、第２スケジューラ１０９は、各スケジューリング要求を、各タイムスロットについて展開して、各タイムスロットでメッセージ数（データブロック数）を合算する（ステップＳ６３）。この処理結果については、図１２及び図１３に示すように、リソース管理データ格納部１１０に格納される。
【００７４】
図２２に本ステップの具体例を示す。図２２の例では、ノードＬ乃至Ｎからスケジューリング要求を受信した場合を示しており、各々４つのタイムスロットについての送信スケジュールのデータが含まれる。このような送信スケジュールを、各タイムスロットについて重ね合わせると、図２２の右側のようになる。このような状態を表すデータが、図１２及び図１３に示すようなデータフォーマットで格納される。この例では、１番目のタイムスロットは、受信リソースの上限である８つのデータブロックが割り当てられており、２番目のタイムスロットは受信リソースより少ない６つのデータブロックが割り当てられており、３番目のタイムスロットは受信リソースを超える９つのデータブロックが割り当てられており、４番目のタイムスロットは受信リソースより少ない７つのデータブロックが割り当てられている。
【００７５】
そうすると、第２スケジューラ１０９は、各タイムスロットで送信されるメッセージの数（データブロックの数）は、受信リソースの範囲内（すなわち、最大値以下）であるか否かを判断する（ステップＳ６５）。各タイムスロットで送信されるメッセージの数が受信リソースの範囲内であれば、第２スケジューラ１０９は、スケジューリングデータ格納部１１１に格納されているスケジューリング要求の内容をそのまま含むスケジュール通知を、各要求元ノードに送信する（ステップＳ６７）。このような場合には、各ノードの送信スケジュールを変更せずとも受信できるためである。
【００７６】
そして、第２スケジューラ１０９は、各スケジュール通知の内容を、スケジューリングデータ格納部１１１に格納する（ステップＳ６９）。また、第２スケジューラ１０９は、今回受信した各スケジュール要求を破棄する（ステップＳ７１）。
【００７７】
一方、いずれかのタイムスロットのメッセージの数が受信リソースの範囲を超える場合には、処理は端子Ａを介して図２３の処理に移行する。
【００７８】
まず、第２スケジューラ１０９は、タイムスロットのカウンタｎを１に初期化する（ステップＳ７３）。そして、第２スケジューラ１０９は、ｎ番目のタイムスロットのメッセージの数が受信リソースを超えているか判断する（ステップＳ７５）。ｎ番目のタイムスロットのメッセージの数が受信リソースの範囲内であれば、処理は端子Ｃを介して図２６の処理に移行する。
【００７９】
一方、ｎ番目のタイムスロットのメッセージの数が受信リソースを超えている場合には、第２スケジューラ１０９は、ｎ番目のタイムスロット内のメッセージを、送信元ノードの送信期限を第１のキーとして、送達期限を第２のキーとしてソートする（ステップＳ７７）。
【００８０】
図２２の３番目のタイムスロットについて図２４及び図２５を用いて本ステップの具体例を説明する。なお、キュー（データリストとも呼ぶ）の上が先頭で下が末尾であるものとする。図２４では、９つのメッセージ（データブロック）のうち１番目から４番目がノードＬについてのメッセージであり、５及び６番目がノードＭについてのメッセージであり、７番目から９番目がノードＮについてのメッセージである。ｅ２ｅ＿ｌｉｍは送達期限を表し、ｌｏｃａｌ＿ｌｉｍはノードの送信期限を表すとする。上で述べたように、送信期限及び送達期限でこれらのメッセージをソートすると、図２５のような結果が得られる。すなわち、同じタイムスロットに割り当てられているメッセージが送信期限及び送達期限から優先順位付けされることになる。
【００８１】
その後、第２スケジューラ１０９は、ｎ番目のタイムスロットより前のタイムスロットに、受信リソースの空きがあるか判断する（ステップＳ７９）。空きがなければ処理は端子Ｂを介して図２６の処理に移行する。送信を前倒しできれば、データ送信遅延の可能性を抑制できるため、先に前のタイムスロットを判断する。
【００８２】
一方、ｎ番目のタイムスロットより前のタイムスロットに空きがあれば、第２スケジューラ１０９は、ｎ番目のタイムスロットの先頭から、空きのあるタイムスロットの末尾にメッセージを移動させる（ステップＳ８１）。
【００８３】
図２２に示した例では、３番目のタイムスロットより前の２番目のタイムスロットに空きがあるので、３番目のタイムスロットの先頭のメッセージを、２番目のタイムスロットの末尾に移動させる。
【００８４】
なお、２以上のメッセージが受信リソースの範囲を超える場合もある。この場合には、ｎ番目のタイムスロットより前のタイムスロットの空き数だけ、ｎ番目のタイムスロットの先頭からメッセージを取り出して、移動させる。３つのメッセージが受信リソースの範囲を超えるが、前のタイムスロットに２つしか空きがない場合には、２つだけメッセージを前のタイムスロットに移動させる。残りの１つは以下の処理で対応策が決定される。
【００８５】
そして、第２スケジューラ１０９は、ｎ番目のスロットにはまだ受信リソースの範囲を超えるメッセージが割り当てられている状態であるか否かを判断する（ステップＳ８３）。この条件を満たす場合には、処理は端子Ｂを介して図２６の処理に移行する。
【００８６】
一方、ｎ番目のスロットのメッセージの数が受信リソースの範囲内となった場合には、処理は端子Ｃを介して図２６の処理に移行する。
【００８７】
図２６の処理の説明に移行して、第２スケジューラ１０９は、ｎ番目のタイムスロットより後のタイムスロットに空きがあるか否かを判断する（ステップＳ８５）。空きがない場合には、処理はステップＳ９１に移行する。
【００８８】
一方、ｎ番目より後ろのスロットにタイムスロットに空きがある場合には、第２スケジューラ１０９は、ｎ番目のタイムスロットの末尾から、空きのあるタイムスロットの先頭にメッセージを移動させる（ステップＳ８７）。
【００８９】
図２２に示した例で、３番目のタイムスロットより前に空きがないと仮定した場合、４番目のタイムスロットにも空きがあるので、３番目のタイムスロットの末尾のメッセージを、４番目のタイムスロットの先頭に移動させる。
【００９０】
なお、２以上のメッセージが受信リソースの範囲を超える場合もある。この場合には、ｎ番目のタイムスロットより後のタイムスロットの空き数だけ、ｎ番目のタイムスロットの末尾からメッセージを取り出して、移動させる。３つのメッセージが受信リソースの範囲を超えるが、後のタイムスロットに２つしか空きがない場合には、２つだけメッセージを後のタイムスロットに移動させる。残りの１つは後に処理される。
【００９１】
さらに、第２スケジューラ１０９は、ｎ番目のタイムスロットにはまだ受信リソースの範囲を超えるメッセージが割り当てられている状態であるか否かを判断する（ステップＳ８９）。この条件を満たさない場合には、処理はステップＳ９５に移行する。
【００９２】
この条件を満たす場合には、第２スケジューラ１０９は、今回のスケジューリングウィンドウの後ろにタイムスロットを追加する（ステップＳ９１）。そして、第２スケジューラ１０９は、ｎ番目のスロットの末尾から、追加タイムスロットの先頭に、この段階で受信リソースの範囲を超えた分のメッセージを移動させる（ステップＳ９３）。
【００９３】
このようにすれば、スケジューリングウィンドウの各タイムスロットにおいては、受信リソースの範囲内にメッセージの受信を抑制できるので、輻輳が抑制され、データ送信の遅延が抑制される。
【００９４】
そして、第２スケジューラ１０９は、カウンタｎが、スケジューリングウィンドウ内のタイムスロット数ｗ以上となったか判断する（ステップＳ９５）。この条件を満たさない場合には、第２スケジューラ１０９は、ｎを１インクリメントして（ステップＳ９７）、処理は端子Ｄを介して図２３のステップＳ７５に戻る。一方、ｎがｗ以上となると、処理は端子Ｅを介して図２７の処理に移行する。
【００９５】
図２７の処理の説明に移行して、第２スケジューラ１０９は、各要求元ノードについて、そのメッセージのスケジューリング結果（すなわち送信スケジュール）を抽出して、スケジュール通知を生成し、各要求元ノードに送信する（ステップＳ９９）。
【００９６】
図２８に示すように、ノードＬでは、３番目のタイムスロットにおけるノードＬのデータブロック（メッセージ）を、２番目のタイムスロットに移動させるので、ノードＬに対するスケジュール通知では、１番目から４番目までのタイムスロットで均等にデータブロック（メッセージ）を送信するという送信スケジュールを指示するようになる。
【００９７】
そして、第２スケジューラ１０９は、各スケジュール通知の内容を、スケジューリングデータ格納部１１１に格納する（ステップＳ１０１）。また、第２スケジューラ１０９は、今回受信した各スケジュール要求を破棄する（ステップＳ１０３）。
【００９８】
このような処理を行えば、データの受信側のリソースの範囲内で送信元ノードからデータを受信できるようになり、輻輳が抑制され、データの遅延が抑制される。
【００９９】
次に、図２９及び図３０を用いて、監視部１１５が実行する処理について説明する。
【０１００】
まず、監視部１１５は、前回の合計サイズを表す変数であるＱＬ［ｐｒｅｖ］をデータキュー１０６にデータが格納されたメッセージの現合計サイズに設定する（図２９：ステップＳ１１１）。ステップＳ１１１においては、各メッセージのサイズが同じである場合には、そのサイズにメッセージの数を乗じることで現合計サイズを求めることができる。各メッセージのサイズが同じではない場合、ステップＳ１１１において現合計サイズを計算してもよい。
【０１０１】
監視部１１５は、現時刻が処理の実行タイミングになったか判断する（ステップＳ１１３）。本実施の形態においては、監視部１１５が定期的に処理を実行するので、ステップＳ１１３においては、前回の実行から所定の実行間隔が経過したか判断される。
【０１０２】
現時刻が処理の実行タイミングになっていない場合（ステップＳ１１３：Ｎｏルート）、処理を一定時間休止し、ステップＳ１１３の処理に戻る。一方、現時刻が処理の実行タイミングになった場合（ステップＳ１１３：Ｙｅｓルート）、監視部１１５は、今回の合計サイズを表す変数であるＱＬ［ｎｏｗ］をデータキュー１０６にデータが格納されたメッセージの現合計サイズに設定する（ステップＳ１１５）。
【０１０３】
監視部１１５は、ＱＬ［ｐｒｅｖ］及びＱＬ［ｎｏｗ］に基づき送出レートを算出する（ステップＳ１１７）。例えば、キュー長の減少速度（（ＱＬ［ｐｒｅｖ］−ＱＬ［ｎｏｗ］）／実行間隔）を送出レートとする。
【０１０４】
監視部１１５は、ステップＳ１１７において算出された送出レートが閾値未満であるか判断する（ステップＳ１１９）。ステップＳ１１９における閾値は、例えば、輻輳が無い場合における送出レートから一定の値を引いた値である。
【０１０５】
送出レートが閾値以上である場合（ステップＳ１１９：Ｎｏルート）、輻輳は発生していないとみなすことができるので、ステップＳ１２３の処理に移行する。一方、送出レートが閾値未満である場合（ステップＳ１１９：Ｙｅｓルート）、監視部１１５は、第２スケジュールネゴシエータ１１７に処理の実行を指示する。これに応じ、第２スケジュールネゴシエータ１１７は、第１の実施の形態における輻輳回避処理を実行する（ステップＳ１２１）。第１の実施の形態における輻輳回避処理については、図３０を用いて説明する。
【０１０６】
まず、第２スケジュールネゴシエータ１１７は、現タイムスロットにおいて送信されるメッセージのうち、送出時刻から送達期限ｔlim,jまでの時間が所定の時間より長いメッセージを探索する（図３０：ステップＳ１３１）。送出時刻は、例えば、現タイムスロットの終了時刻である。
【０１０７】
第２スケジュールネゴシエータ１１７は、ステップＳ１３１においてメッセージを検出したか判断する（ステップＳ１３３）。メッセージを検出していない場合（ステップＳ１３３：Ｎｏルート）、呼び出し元の処理に戻る。
【０１０８】
一方、メッセージを検出した場合（ステップＳ１３３：Ｙｅｓルート）、第２スケジュールネゴシエータ１１７は、検出されたメッセージのデータ（データ本体を除く）を読み出し、再スケジューリング要求を生成する。再スケジューリング要求のデータフォーマットは、スケジューリング要求のデータフォーマットと同様であり、図１７に示したとおりである。そして、第２スケジュールネゴシエータ１１７は、検出されたメッセージの送信先ノードに対して、再スケジューリング要求を送信する（ステップＳ１３５）。なお、再スケジューリング要求を受信したノードが実行する処理については、後で説明する。
【０１０９】
第２スケジュールネゴシエータ１１７は、スケジュール結果を含むスケジュール通知を、送信先ノードから受信する（ステップＳ１３７）。再スケジュール要求に対するスケジュール通知のデータフォーマットは、図１７及び図１８に示したようなフォーマットである。
【０１１０】
そして、第２スケジュールネゴシエータ１１７は、スケジュール通知を受信すると、スケジュール通知に従って、データキュー１０６に登録された、検出されたメッセージの送信スケジュールデータを更新する（ステップＳ１３９）。そして呼び出し元の処理に戻る。スケジュール通知で通知された送信スケジュールとスケジューリング要求における送信スケジュールとが一致する場合もあるので、その場合には特に処理は行わない。異なるタイムスロットに移動させられた場合には、そのタイムスロットのキューにエンキューする。そのタイムスロットのデータがなければ、この段階で生成する。
【０１１１】
図２９の説明に戻り、監視部１１５は、ＱＬ［ｐｒｅｖ］をＱＬ［ｎｏｗ］に設定する（ステップＳ１２３）。
【０１１２】
監視部１１５は、処理終了が指示されたか判断する（ステップＳ１２５）。処理終了が指示されていない場合（ステップＳ１２５：Ｎｏルート）、処理はステップＳ１１３に戻る。一方、処理終了が指示された場合（ステップＳ１２５：Ｙｅｓルート）、処理を終了する。
【０１１３】
以上のような処理を実行すれば、輻輳が発生した場合においても、輻輳を回避するようにスケジュールを再設定することができるようになる。
【０１１４】
次に、図３１を用いて、第３スケジューラ１１３が実行する処理について説明する。まず、第３スケジューラ１１３は、輻輳を回避するための再スケジューリング要求を、メッセージの送信元のノードから受信し（図３１：ステップＳ１４１）、スケジューリングデータ格納部１１１に格納する。
【０１１５】
第３スケジューラ１１３は、再スケジューリング要求において指定されたメッセージについて、送達期限を徒過せず且つ受信リソースが不足しないように、スケジュールを再設定する（ステップＳ１４３）。例えば図４Ｇに示すように、現タイムスロットにおいて送信することになっているデータブロック（すなわちメッセージ）を、後のタイムスロットで送信するようにスケジュールを変更する。但し、送達期限までにデータブロックを送り届けることができるようにする。また、スケジュールを変更したことが原因で受信リソースが不足しないことを確認する処理を実行する。この処理は、第２スケジューラ１０９が実行する処理と同様であるので、ここでは詳細な説明を省略する。なお、ステップＳ１４３においては、再スケジューリング要求に含まれるスケジュールをそのまま採用する場合もある。
【０１１６】
第３スケジューラ１１３は、再スケジューリングの結果（すなわち送信スケジュール）を含むスケジュール通知を生成し、送信元ノードに送信する（ステップＳ１４５）。そして処理を終了する。なお、第３スケジューラ１１３は、スケジュール通知の内容を、スケジューリングデータ格納部１１１に格納する。また、第３スケジューラ１１３は、今回受信した再スケジューリング要求を破棄する。
【０１１７】
以上のような処理を実行すれば、送信元ノードは、輻輳を回避し且つ送達期限を徒過することが無いようにデータを送信できるようになる。
【０１１８】
［実施の形態２］
第２の実施の形態においては、第１の実施の形態とは異なる輻輳検出の方法について説明する。
【０１１９】
図３２に、第２の実施の形態におけるノードＡ乃至Ｃの構成例を示す。ノードは、データ受信部１０１と、第１スケジューラ１０２と、リンクデータ格納部１０３と、データ転送ルート格納部１０４と、第１レイテンシデータ格納部１０５と、データキュー１０６と、データ送信部１０７と、第１スケジュールネゴシエータ１０８と、第２スケジューラ１０９と、リソース管理データ格納部１１０と、スケジューリングデータ格納部１１１と、第３スケジューラ１１３と、監視部１１５と、第２スケジュールネゴシエータ１１７と、第２レイテンシデータ格納部１１９とを有する。
【０１２０】
図３３に、第２レイテンシデータ格納部１１９に格納されるデータの一例を示す。図３３の例では、送信元ノードのＩＤと、宛先次ノードのＩＤと、制御メッセージの遅延時間（ここでは、制御メッセージが送信元ノードから宛先次ノードまで転送されるのに要する時間）を格納している。制御メッセージとは、例えばスケジュール通知等である。第１スケジュールネゴシエータ１０８は、受信した制御メッセージの遅延時間を計算し、第２レイテンシデータ格納部１１９に格納する。制御メッセージの遅延時間は、宛先次ノードから受信する制御メッセージに含まれる宛先次ノードの送信時刻と、制御メッセージの受信時刻とから算出される。
【０１２１】
次に、図３４を用いて、第２の実施の形態における監視部１１５が実行する処理について説明する。
【０１２２】
監視部１１５は、現時刻が処理の実行タイミングになったか判断する（図３４：ステップＳ１５１）。本実施の形態においては、監視部１１５が定期的に処理を実行するので、ステップＳ１５１においては、前回の実行から所定の実行間隔が経過したか判断される。
【０１２３】
現時刻が処理の実行タイミングになっていない場合（ステップＳ１５１：Ｎｏルート）、処理を一定時間休止し、ステップＳ１５１の処理に戻る。一方、現時刻が処理の実行タイミングになった場合（ステップＳ１５１：Ｙｅｓルート）、監視部１１５は、第２レイテンシデータ格納部１１９から、制御メッセージの遅延時間を取得する（ステップＳ１５３）。
【０１２４】
監視部１１５は、ステップＳ１５３において取得された遅延時間が、予め定められた閾値を超えたか判断する（ステップＳ１５５）。ステップＳ１５５における閾値は、例えば、輻輳が無い場合における遅延時間から一定の値を引いた値である。
【０１２５】
遅延時間が閾値を超えていない場合（ステップＳ１５５：Ｎｏルート）、輻輳は発生していないとみなすことができるので、ステップＳ１５９の処理に移行する。一方、遅延時間が閾値を超えた場合（ステップＳ１５５：Ｙｅｓルート）、監視部１１５は、第２スケジュールネゴシエータ１１７に処理の実行を指示する。これに応じ、第２スケジュールネゴシエータ１１７は、輻輳回避処理を実行する（ステップＳ１５７）。ステップＳ１５７において実行される輻輳回避処理は、ステップＳ１２１において実行される輻輳回避処理と同じであるので、説明を省略する。
【０１２６】
監視部１１５は、処理終了が指示されたか判断する（ステップＳ１５９）。処理終了が指示されていない場合（ステップＳ１５９：Ｎｏルート）、処理はステップＳ１５１に戻る。一方、処理終了が指示された場合（ステップＳ１５９：Ｙｅｓルート）、処理を終了する。
【０１２７】
以上のような処理を実行すれば、輻輳が発生した場合においても、輻輳を回避するようにスケジュールを再設定することができるようになる。
【０１２８】
［実施の形態３］
第１及び第２の実施の形態においては、データ転送のペア（ここでは、送信元ノード及び宛先次ノード）が輻輳回避のためのスケジューリングをするか決定しており、他のペアの状態等を考慮しない。従って、同じネットワークにおいて複数のペアが同じタイミングで輻輳回避のためのスケジューリングをすることがある。その場合、送達期限を徒過することは無いが、ネットワークの帯域が必要以上に空き、リソースの利用効率が低下する。
【０１２９】
そこで第３の実施の形態においては、優先度を用いて送信を制御する。具体的には、例えば図３５に示すように、輻輳回避のためのスケジューリングを、同じグループに属する複数のノードが協調して行うようにする。図３５においては、同じグループに属するノードは一点鎖線で囲まれており、６台のノードが同じグループに属する。各ノードは、同じグループに属する他のノードと優先度の情報を交換し、優先度に基づき輻輳回避のためのスケジューリングを行う。
【０１３０】
このように、協調して動作するノードを同じグループに属するノードに限定すれば、ネットワーク全体を監視する装置を設けてスケジュール調整を行う方法と比べると、スケジュール調整のために転送される制御メッセージの量を減らすことができる。
【０１３１】
以下、第３の実施の形態について詳細に説明する。図３６に、第３の実施の形態におけるノードＡ乃至Ｃの構成例を示す。ノードは、データ受信部１０１と、第１スケジューラ１０２と、リンクデータ格納部１０３と、データ転送ルート格納部１０４と、第１レイテンシデータ格納部１０５と、データキュー１０６と、データ送信部１０７と、第１スケジュールネゴシエータ１０８と、第２スケジューラ１０９と、リソース管理データ格納部１１０と、スケジューリングデータ格納部１１１と、第３スケジューラ１１３と、監視部１１５と、第２スケジュールネゴシエータ１１７と、優先度管理部１２１と、優先度格納部１２３と、隣接ノードデータ格納部１２５とを有する。
【０１３２】
図３７に、優先度格納部１２３に格納されるデータの一例を示す。図３７の例では、その優先度格納部１２３を有するノードに割り当てられた優先度の情報が格納される。優先度の情報の送信先（以下、隣接ノードと呼ぶ）は、隣接ノードデータ格納部１２５に格納されるデータに基づき特定される。図３８に、隣接ノードデータ格納部１２５に格納されるデータの一例を示す。図３８の例では、隣接ノードのＩＤが格納される。
【０１３３】
図３９に、優先度の情報を交換するためのメッセージのフォーマットの一例を示す。図３９の例では、メッセージには、メッセージの送信元ノードのＩＤと、メッセージの宛先ノード（ここでは、隣接ノード）のＩＤと、優先度の情報とが含まれる。
【０１３４】
図４０に、輻輳の検出を通知するためのメッセージの一例を示す。図４０の例では、メッセージには、送信元ノード（ここでは、輻輳を検出したノード）のＩＤと、そのノードに割り当てられた優先度の情報とが含まれる。
【０１３５】
次に、図４１乃至図４３Ｂを用いて、優先度管理部１２１が実行する処理について説明する。優先度管理部１２１は、現時刻が処理の実行タイミングになったか判断する（図４１：ステップＳ１６１）。本実施の形態においては、優先度管理部１２１が定期的に処理を実行するので、ステップＳ１６１においては、前回の実行から所定の実行間隔が経過したか判断される。
【０１３６】
現時刻が処理の実行タイミングになっていない場合（ステップＳ１６１：Ｎｏルート）、処理を一定時間休止し、ステップＳ１６１の処理に戻る。一方、現時刻が処理の実行タイミングになった場合（ステップＳ１６１：Ｙｅｓルート）、優先度管理部１２１は、優先度格納部１２３から、本処理を実行するノードに割り当てられた優先度の情報を読み出す（ステップＳ１６３）。
【０１３７】
優先度管理部１２１は、隣接ノードのＩＤを隣接ノードデータ格納部１２５から特定する。そして、優先度管理部１２１は、隣接ノードに対して、ステップＳ１６３において読み出された優先度の情報を送信する（ステップＳ１６５）。
【０１３８】
優先度管理部１２１は、処理終了が指示されたか判断する（ステップＳ１６７）。処理終了が指示されていない場合（ステップＳ１６７：Ｎｏルート）、処理はステップＳ１６１に戻る。一方、処理終了が指示された場合（ステップＳ１６７：Ｙｅｓルート）、処理を終了する。
【０１３９】
そして、優先度管理部１２１は、優先度の情報の受信については以下のような処理を実行する。まず、優先度管理部１２１は、他のノードから優先度の情報を受信する（図４２：ステップＳ１７１）。この他のノードにとっての隣接ノードは、本処理を実行するノードである。
【０１４０】
優先度管理部１２１は、受信した優先度の情報で、優先度格納部１２３に格納されたデータを更新する（ステップＳ１７３）。ステップＳ１７３の処理によって、優先度格納部１２３に格納される優先度の情報は、定期的に更新されるようになる。
【０１４１】
以上のような処理を各ノードが実行すれば、同じグループに属する複数のノードが優先度を交換できるようになる。例えば、図４３Ａに示すように優先度が割り当てられているとする。図４３Ａの例では、ノードＰに優先度＃１が割り当てられ、ノードＱに優先度＃２が割り当てられ、ノードＲに優先度＃３が割り当てられ、ノードＳに優先度＃４が割り当てられている。ここで、ノードＰにとっての隣接ノードはノードＱであり、ノードＱにとっての隣接ノードはノードＲであり、ノードＲにとっての隣接ノードはノードＳであり、ノードＳにとっての隣接ノードはノードＰであるとする。
【０１４２】
このような状態において優先度を交換すると、図４３Ｂに示すような状態になる。図４３Ｂにおいては、ノードＰに優先度＃４が割り当てられ、ノードＱに優先度＃１が割り当てられ、ノードＲに優先度＃２が割り当てられ、ノードＳに優先度＃３が割り当てられている。
【０１４３】
以上のように優先度を交換すれば、特定のノードに割り当てられた優先度が常に高い状態になることを抑制できるようになる。
【０１４４】
次に、第３の実施の形態における輻輳回避処理について説明する。第３の実施の形態における輻輳回避処理は、第１及び第２の実施の形態と同様、監視部１１５が第２スケジュールネゴシエータ１１７に処理の実行を指示した場合に実行される。
【０１４５】
まず、第２スケジュールネゴシエータ１１７は、現タイムスロットにおいて送信されるメッセージのうち、送出時刻から送達期限ｔlim,jまでの時間が所定の時間より長いメッセージを探索する（図４４：ステップＳ１８１）。送出時刻は、例えば、現タイムスロットの終了時刻である。
【０１４６】
第２スケジュールネゴシエータ１１７は、ステップＳ１８１においてメッセージを検出したか判断する（ステップＳ１８３）。メッセージを検出していない場合（ステップＳ１８３：Ｎｏルート）、呼び出し元の処理に戻る。
【０１４７】
一方、メッセージを検出した場合（ステップＳ１８３：Ｙｅｓルート）、第２スケジュールネゴシエータ１１７は、優先度格納部１２３から優先度の情報を読み出す。そして、第２スケジュールネゴシエータ１１７は、同じグループに属するノードに対して、読み出した優先度の情報及び本ノードのＩＤを含むメッセージを送信する（ステップＳ１８５）。ステップＳ１８５において送信されるメッセージのフォーマットは、図４０に示したフォーマットである。同じグループに属するノードの情報（例えばアドレス）は予め取得されているものとする。
【０１４８】
第２スケジュールネゴシエータ１１７は、タイマによる時間の計測を開始し（ステップＳ１８７）、予め定められた時間が経過した場合にタイマによる時間の計測を終了する（ステップＳ１８９）。
【０１４９】
第２スケジュールネゴシエータ１１７は、タイマによる計測中に、輻輳の検出を通知するためのメッセージを他のノードから受信したか判断する（ステップＳ１９１）。輻輳の検出を通知するためのメッセージを他のノードから受信していない場合（ステップＳ１９１：Ｎｏルート）、本ノードが検出した輻輳の回避を実行できるので、処理は端子Ｆを介して図４５のステップＳ１９７に移行する。
【０１５０】
一方、輻輳の検出を通知するためのメッセージを他のノードから受信した場合（ステップＳ１９１：Ｙｅｓルート）、第２スケジュールネゴシエータ１１７は、受信したメッセージに含まれる情報から特定される、メッセージの送信元ノードの優先度と、本ノードの優先度とを比較する（ステップＳ１９３）。なお、タイマによる計測中に複数のメッセージを受信した場合、ステップＳ１９３においては各メッセージの送信元ノードの優先度と本ノードの優先度とが比較される。
【０１５１】
第２スケジュールネゴシエータ１１７は、本ノードの優先度が他のノードの優先度より高いか判断する（ステップＳ１９５）。なお、タイマによる計測中に複数のメッセージを受信した場合、ステップＳ１９５においては、いずれの優先度よりも本ノードの優先度が高いか判断される。
【０１５２】
本ノードの優先度が他のノードの優先度より高くない場合（ステップＳ１９５：Ｎｏルート）、他のノードが検出した輻輳の回避を優先すべきであるので、処理は端子Ｇを介して図４５の処理に移行し、呼び出し元の処理に戻る。本ノードの優先度が他のノードの優先度より高い場合（ステップＳ１９５：Ｙｅｓルート）、本ノードが検出した輻輳の回避を実行できるので、処理は端子Ｆを介して図４５のステップＳ１９７に移行する。
【０１５３】
図４５の説明に移行し、第２スケジュールネゴシエータ１１７は、ステップＳ１８１において検出されたメッセージのデータ（データ本体を除く）を読み出し、再スケジューリング要求を生成する。再スケジューリング要求のデータフォーマットは、スケジューリング要求のデータフォーマットと同様であり、図１７に示したとおりである。そして、第２スケジュールネゴシエータ１１７は、検出されたメッセージの送信先ノードに対して、再スケジューリング要求を送信する（ステップＳ１９７）。なお、再スケジューリング要求を受信したノードが実行する処理については、後で説明する。
【０１５４】
第２スケジュールネゴシエータ１１７は、スケジュール結果を含むスケジュール通知を、送信先ノードから受信する（ステップＳ１９９）。再スケジュール要求に対するスケジュール通知のデータフォーマットは、図１７及び図１８に示したようなフォーマットである。
【０１５５】
そして、第２スケジュールネゴシエータ１１７は、スケジュール通知を受信すると、スケジュール通知に従って、データキュー１０６に登録された、検出されたメッセージの送信スケジュールデータを更新する（ステップＳ２０１）。そして呼び出し元の処理に戻る。スケジュール通知で通知された送信スケジュールとスケジューリング要求における送信スケジュールとが一致する場合もあるので、その場合には特に処理は行わない。異なるタイムスロットに移動させられた場合には、そのタイムスロットのキューにエンキューする。そのタイムスロットのデータがなければ、この段階で生成する。
【０１５６】
以上のような処理を実行すれば、ネットワークの帯域に空きが生じたにも関わらず輻輳回避のためのスケジューリングを実行することを防げるので、ネットワークの帯域の利用効率が低下するのを抑制できる。
【０１５７】
［実施の形態４］
第４の実施の形態においては、データの送信先において輻輳を検出し、輻輳の検出を回避するためのスケジューリングを行う方法について説明する。
【０１５８】
このような処理を行うためのノードＡ乃至Ｃの構成例を図４６に示す。ノードは、データ受信部１０１と、第１スケジューラ１０２と、リンクデータ格納部１０３と、データ転送ルート格納部１０４と、第１レイテンシデータ格納部１０５と、データキュー１０６と、データ送信部１０７と、第１スケジュールネゴシエータ１０８と、第２スケジューラ１０９と、リソース管理データ格納部１１０と、スケジューリングデータ格納部１１１と、第３レイテンシデータ格納部１１２とを有する。
【０１５９】
図４７に、第３レイテンシデータ格納部１１２に格納されるデータの一例を示す。図４７の例では、送信元ノードのＩＤと、宛先次ノードのＩＤと、制御メッセージの遅延時間（ここでは、制御メッセージが送信元ノードから宛先次ノードまで転送されるのに要する時間）とを格納している。制御メッセージとは、例えばスケジュール要求等である。第２スケジューラ１０９は、受信した制御メッセージの遅延時間を計算し、第３レイテンシデータ格納部１１２に格納する。制御メッセージの遅延時間は、宛先次ノードから受信する制御メッセージに含まれる宛先次ノードの送信時刻と、制御メッセージの受信時刻とから算出される。
【０１６０】
次に、図４８乃至図５０Ｂを用いて、第４の実施の形態における第２スケジューラ１０９が実行する処理について説明する。
【０１６１】
まず、第２スケジューラ１０９は、データソースに近い各ノードから、スケジューリング要求を受信し、スケジューリングデータ格納部１１１に格納する（図４８：ステップＳ２１１）。
【０１６２】
第２スケジューラ１０９は、スケジューリング要求の送信元ノードのうち未処理の送信元ノードを１台特定し（ステップＳ２１３）、制御メッセージの遅延時間を第３レイテンシデータ格納部１１２から取得する（ステップＳ２１５）。
【０１６３】
第２スケジューラ１０９は、ステップＳ２１５において取得された遅延時間が、予め定められた閾値を超えたか判断する（ステップＳ２１７）。ステップＳ２１７における閾値は、例えば、輻輳が無い場合における遅延時間から一定の値を引いた値である。
【０１６４】
遅延時間が閾値を超えていない場合（ステップＳ２１７：Ｎｏルート）、輻輳は発生していないとみなすことができるので、ステップＳ２２１の処理に移行する。一方、遅延時間が閾値を超えた場合（ステップＳ２１７：Ｙｅｓルート）、第２スケジューラ１０９は、輻輳回避のためのスケジューリングを実行する（ステップＳ２１９）。例えば図４Ｇに示すように、現タイムスロットにおいて送信することになっているデータブロック（すなわちメッセージ）を、後のタイムスロットで送信するようにスケジュールを変更する。但し、送達期限までにデータブロックを送り届けることができるようにする。そして、特定された送信元ノードについてのスケジューリング要求を、ステップＳ２１９におけるスケジューリングの結果に基づき変更し、スケジューリングデータ格納部１１１に格納する。
【０１６５】
第２スケジューラ１０９は、未処理の送信元ノードが有るか判断する（ステップＳ２２１）。未処理の送信元ノードが有る場合（ステップＳ２２１：Ｙｅｓルート）、次の送信元ノードについて処理するため、ステップＳ２１３の処理に戻る。一方、未処理の送信元ノードが無い場合（ステップＳ２２１：Ｎｏルート）、処理は端子Ｈを介して図４９のステップＳ２２３に移行する。
【０１６６】
図４９の説明に移行し、第２スケジューラ１０９は、各スケジューリング要求を、各タイムスロットについて展開して、各タイムスロットでメッセージ数（データブロック数）を合算する（ステップＳ２２３）。この処理結果については、図１２及び図１３に示すように、リソース管理データ格納部１１０に格納される。
【０１６７】
第２スケジューラ１０９は、各タイムスロットで送信されるメッセージの数（データブロックの数）は、受信リソースの範囲内（すなわち、最大値以下）であるか否かを判断する（ステップＳ２２５）。
【０１６８】
ここまでの処理について、図５０Ａ及び図５０Ｂを用いて説明する。図５０Ａにおいては、ノードＬ乃至Ｎからスケジューリング要求を受信したケースが示されており、各々４つのタイムスロットについての送信スケジュールのデータが含まれる。ここで、ノードＬとの間の通信経路についてステップＳ２１７において輻輳を検出したとすると、ノードＬからのスケジューリング要求に含まれるスケジュールが変更される。具体的には、１番目のタイムスロットにおける２つのデータブロック（すなわちメッセージ）が３番目のタイムスロットに移動される。
【０１６９】
このような送信スケジュールを、各タイムスロットについて重ね合わせると、図５０Ｂのようになる。この例では、１番目のタイムスロットは、受信リソースより少ない６つのデータブロックが割り当てられており、２番目のタイムスロットは受信リソースより少ない６つのデータブロックが割り当てられており、３番目のタイムスロットは受信リソースを超える９つのデータブロックが割り当てられており、４番目のタイムスロットは受信リソースより少ない６つのデータブロックが割り当てられている。このような状態を表すデータが、図１２及び図１３に示すようなデータフォーマットで格納される。
【０１７０】
図４９の説明に戻り、各タイムスロットで送信されるメッセージの数が受信リソースの範囲内である場合（ステップＳ２２５：Ｙｅｓルート）、第２スケジューラ１０９は、スケジューリングデータ格納部１１１に格納されているスケジューリング要求の内容をそのまま含むスケジュール通知を、各要求元ノードに送信する（ステップＳ２２７）。但し、ステップＳ２１９の処理が実行された送信元ノードに対しては、変更後のスケジュールを含むスケジュール通知が送信される。
【０１７１】
そして、第２スケジューラ１０９は、各スケジュール通知の内容を、スケジューリングデータ格納部１１１に格納する（ステップＳ２２９）。また、第２スケジューラ１０９は、今回受信した各スケジュール要求を破棄する（ステップＳ２３１）。
【０１７２】
一方、いずれかのタイムスロットのメッセージの数が受信リソースの範囲を超える場合（ステップＳ２２５：Ｎｏルート）、処理は端子Ａを介して図２３の処理に移行する。端子Ａ以降の処理については第１の実施の形態において説明したとおりなので、ここでは説明を省略する。
【０１７３】
以上のような処理を実行すれば、送信先ノードにおいて輻輳を検出する場合にも、データ送信の遅延が発生することを抑制できるようになる。
【０１７４】
［実施の形態５］
第５の実施の形態においては、関連する複数のデータブロックについての送信スケジュールを一括して再設定する方法について説明する。
【０１７５】
図５１に、第５の実施の形態におけるノードＡ乃至Ｃの構成例を示す。ノードは、データ受信部１０１と、第１スケジューラ１０２と、リンクデータ格納部１０３と、データ転送ルート格納部１０４と、第１レイテンシデータ格納部１０５と、データキュー１０６と、データ送信部１０７と、第１スケジュールネゴシエータ１０８と、第２スケジューラ１０９と、リソース管理データ格納部１１０と、スケジューリングデータ格納部１１１と、第３スケジューラ１１３と、監視部１１５と、第２スケジュールネゴシエータ１１７と、関連データ格納部１２７とを有する。
【０１７６】
図５２に、関連データ格納部１２７に格納されるデータの一例を示す。図５２の例では、データのＩＤと、そのデータに関連するデータのＩＤを配列で表すデータとが格納される。
【０１７７】
次に、図５３を用いて、第５の実施の形態における輻輳回避処理について説明する。
【０１７８】
まず、第２スケジュールネゴシエータ１１７は、現タイムスロットにおいて送信されるメッセージのうち、送出時刻から送達期限ｔlim,jまでの時間が所定の時間より長いメッセージを探索する（図５３：ステップＳ２４１）。送出時刻は、例えば、現タイムスロットの終了時刻である。
【０１７９】
第２スケジュールネゴシエータ１１７は、ステップＳ２４１においてメッセージを検出したか判断する（ステップＳ２４３）。メッセージを検出していない場合（ステップＳ２４３：Ｎｏルート）、呼び出し元の処理に戻る。
【０１８０】
一方、メッセージを検出した場合（ステップＳ２４３：Ｙｅｓルート）、第２スケジュールネゴシエータ１１７は、検出したメッセージに係るデータに関連するデータのＩＤを、関連データ格納部１２７から抽出する（ステップＳ２４５）。
【０１８１】
第２スケジュールネゴシエータ１１７は、検出されたメッセージのデータ（データ本体を除く）及びそのデータに関連するデータ（データ本体を除く）を読み出し、再スケジューリング要求を生成する。再スケジューリング要求のデータフォーマットは、スケジューリング要求のデータフォーマットと同様であり、図１７に示したとおりである。そして、第２スケジュールネゴシエータ１１７は、検出されたメッセージの送信先ノードに対して、再スケジューリング要求を送信する（ステップＳ２４７）。なお、再スケジューリング要求を受信したノードが実行する処理については、第１の実施の形態において説明したとおりであるので、ここでは説明を省略する。
【０１８２】
第２スケジュールネゴシエータ１１７は、スケジュール結果を含むスケジュール通知を、送信先ノードから受信する（ステップＳ２４９）。再スケジュール要求に対するスケジュール通知のデータフォーマットは、図１７及び図１８に示したようなフォーマットである。
【０１８３】
そして、第２スケジュールネゴシエータ１１７は、スケジュール通知を受信すると、スケジュール通知に従って、データキュー１０６に登録された、検出されたメッセージの送信スケジュールデータを更新する（ステップＳ２５１）。そして呼び出し元の処理に戻る。
【０１８４】
以上のような処理を実行すれば、例えば、関連する複数のデータブロックが揃わないと宛先次ノードにおいて処理を開始できないというような制約がある場合、一部のデータブロックだけを受信した状態で送信先ノードが待機することになることを回避できるようになる。
【０１８５】
以上本発明の一実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上で説明したノードの機能ブロック構成は実際のプログラムモジュール構成に一致しない場合もある。
【０１８６】
また、上で説明したデータ保持構成は一例であって、上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【０１８７】
例えば、第３の実施の形態においては優先度の情報を交換したが、各ノードが予め定められたルールに従って優先度を変更することで、優先度の割り当てに偏りが生じないようにしてもよい。
【０１８８】
また、第４の実施の形態において端子Ａ以降の処理を実行する場合、輻輳を増長するようなスケジューリングを行うことを回避するため、データブロックの移動先を現タイムスロットより後のタイムスロットだけに限定してもよい。
【０１８９】
また、輻輳回避のためのスケジューリングにおいては、メッセージ検出の対象となるタイムスロットは現タイムスロットだけに限定されるわけではない。輻輳の解消に有効である場合には、例えば、現タイムスロットの１つ後のタイムスロットからメッセージを検出してもよい。
【０１９０】
なお、上で述べたノードは、コンピュータ装置であって、図５４に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本発明の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１９１】
以上述べた本発明の実施の形態をまとめると、以下のようになる。
【０１９２】
本実施の形態に係るデータ送信方法は、（Ａ）第１の情報処理装置と、１又は複数のデータブロックの送信先である第２の情報処理装置との間のネットワークにおいて輻輳が発生したことを検出し、（Ｂ）１又は複数のデータブロックの各々について送信時刻及び送達期限を格納するデータ格納部に格納されたデータに基づき、送信時刻から送達期限までの時間が所定時間より長いという条件を満たす第１のデータブロックを特定し、（Ｃ）第１のデータブロックの送達期限を含み且つ第１のデータブロックの送信時刻を再設定することを要求する第１の要求を、第２の情報処理装置に送信し、（Ｄ）第２の情報処理装置から、第２の情報処理装置により設定された送信時刻を受信する処理を含む。
【０１９３】
このようにすれば、輻輳が発生した場合にデータブロックの送信時刻をずらすことができるので、データ送信の遅延が発生することを抑制できるようになる。
【０１９４】
また、輻輳が発生したことを検出する処理において、（ａ１）１又は複数のデータブロックの合計サイズが減少する速度から送出レートを算出し、（ａ２）算出された送出レートが第１の閾値未満である場合に、ネットワークにおいて輻輳が発生したと決定してもよい。このようにすれば、ネットワークにおいて輻輳が発生したことを適切に検出できるようになる。
【０１９５】
また、輻輳が発生したことを検出する処理において、（ａ３）第１の情報処理装置と第２の情報処理装置との間のレイテンシが第２の閾値を超えたか判断し、（ａ４）第１の情報処理装置と第２の情報処理装置との間のレイテンシが第２の閾値を超えたと判断された場合に、ネットワークにおいて輻輳が発生したと決定してもよい。このようにすれば、ネットワークにおいて輻輳が発生したことを適切に検出できるようになる。
【０１９６】
また、上で述べた第２の情報処理装置により設定された送信時刻は、第１のデータの送達期限と第２の情報処理装置の受信リソースとに基づき設定されてもよい。このようにすれば、データブロックの送達期限を徒過することを防ぎ、且つ宛先の情報処理装置の受信リソースが不足することを防げるようになる。
【０１９７】
また、本データ送信方法は、（Ｅ）ネットワークにおいて輻輳が発生したことを検出した場合、第１の情報処理装置と同じグループに属する第３の情報処理装置に、第１の情報処理装置に割り当てられた優先度を送信し、（Ｆ）第１の情報処理装置に割り当てられた優先度より低い優先度を第３の情報処理装置から受信するか判断する処理をさらに含んでもよい。そして、上で述べた第１の要求を第２の情報処理装置に送信する処理において、（ｃ１）第３の情報処理装置から優先度を受信しない場合又は第１の情報処理装置に割り当てられた優先度より低い優先度を第３の情報処理装置から受信した場合、第１の要求を第２の情報処理装置に送信してもよい。このようにすれば、たとえ輻輳が発生したとしても第１の要求を送信しない場合が生じるので、不要な再設定をすることを抑制できるようになる。
【０１９８】
また、本データ送信方法は、（Ｇ）第１の情報処理装置と、第１の情報処理装置に対して１又は複数のデータブロックを送信する第４の情報処理装置との間の第２のネットワークにおける輻輳の状態を特定し、（Ｈ）第４の情報処理装置から、当該１又は複数のデータブロックの送信時刻を設定することを要求する第２の要求を受信し、（Ｉ）第１の情報処理装置の受信リソースと、特定された輻輳の状態とに基づき、１又は複数のデータブロックの送信時刻を設定し、（Ｊ）設定された１又は複数のデータブロックの送信時刻を、第４の情報処理装置に送信する処理をさらに含んでもよい。このようにすれば、輻輳を回避しつつデータを受信できるようになる。また、受信リソースが不足することを防げるようになる。
【０１９９】
また、本データ送信方法は、（Ｋ）各データブロックについて当該データブロックに関連するデータブロックの識別子を格納する第２データ格納部を用いて、第１のデータブロックに関連するデータブロックである第２のデータブロックを抽出する処理をさらに含んでもよい。そして、上で述べた第１の要求は、第１のデータブロックの送信時刻及び第２のデータブロックの送信時刻を再設定するための要求であってもよい。このようにすれば、関連する複数のデータブロックについての再設定を一度に行えるようになる。
【０２００】
なお、上記方法による処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【０２０１】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０２０２】
（付記１）
第１の情報処理装置に、
前記第１の情報処理装置と、１又は複数のデータブロックの送信先である第２の情報処理装置との間のネットワークにおいて輻輳が発生したことを検出し、
前記１又は複数のデータブロックの各々について送信時刻及び送達期限を格納するデータ格納部に格納されたデータに基づき、送信時刻から送達期限までの時間が所定時間より長いという条件を満たす第１のデータブロックを特定し、
前記第１のデータブロックの送達期限を含み且つ前記第１のデータブロックの送信時刻を再設定することを要求する第１の要求を、前記第２の情報処理装置に送信し、
前記第２の情報処理装置から、前記第２の情報処理装置により設定された送信時刻を受信する、
処理を実行させるデータ送信プログラム。
【０２０３】
（付記２）
前記輻輳が発生したことを検出する処理において、
前記１又は複数のデータブロックの合計サイズが減少する速度から送出レートを算出し、
算出された前記送出レートが第１の閾値未満である場合に、前記ネットワークにおいて輻輳が発生したと決定する
付記１記載のデータ送信プログラム。
【０２０４】
（付記３）
前記輻輳が発生したことを検出する処理において、
前記第１の情報処理装置と前記第２の情報処理装置との間のレイテンシが第２の閾値を超えたか判断し、
前記第１の情報処理装置と前記第２の情報処理装置との間のレイテンシが前記第２の閾値を超えたと判断された場合に、前記ネットワークにおいて輻輳が発生したと決定する
付記１記載のデータ送信プログラム。
【０２０５】
（付記４）
前記第２の情報処理装置により設定された送信時刻は、
前記第１のデータの送達期限と前記第２の情報処理装置の受信リソースとに基づき設定される
付記１乃至３のいずれか１つ記載のデータ送信プログラム。
【０２０６】
（付記５）
前記第１の情報処理装置に、
前記ネットワークにおいて輻輳が発生したことを検出した場合、前記第１の情報処理装置と同じグループに属する第３の情報処理装置に、前記第１の情報処理装置に割り当てられた優先度を送信し、
前記第１の情報処理装置に割り当てられた優先度より低い優先度を前記第３の情報処理装置から受信するか判断する、
処理をさらに実行させ、
前記第１の要求を前記第２の情報処理装置に送信する処理において、
前記第３の情報処理装置から優先度を受信しない場合又は前記第１の情報処理装置に割り当てられた優先度より低い優先度を前記第３の情報処理装置から受信した場合、前記第１の要求を前記第２の情報処理装置に送信する、
付記１乃至４のいずれか１つ記載のデータ送信プログラム。
【０２０７】
（付記６）
前記第１の情報処理装置に、
前記第１の情報処理装置と、前記第１の情報処理装置に対して１又は複数のデータブロックを送信する第４の情報処理装置との間の第２のネットワークにおける輻輳の状態を特定し、
前記第４の情報処理装置から、当該１又は複数のデータブロックの送信時刻を設定することを要求する第２の要求を受信し、
前記第１の情報処理装置の受信リソースと、特定された前記輻輳の状態とに基づき、前記１又は複数のデータブロックの送信時刻を設定し、
設定された前記１又は複数のデータブロックの送信時刻を、前記第４の情報処理装置に送信する
処理をさらに実行させる付記１乃至５のいずれか１つ記載のデータ送信プログラム。
【０２０８】
（付記７）
前記第１の情報処理装置に、
各データブロックについて当該データブロックに関連するデータブロックの識別子を格納する第２データ格納部を用いて、前記第１のデータブロックに関連するデータブロックである第２のデータブロックを抽出する、
処理をさらに実行させ、
前記第１の要求は、
前記第１のデータブロックの送信時刻及び前記第２のデータブロックの送信時刻を再設定するための要求である
付記１乃至６のいずれか１つ記載のデータ送信プログラム。
【０２０９】
（付記８）
第１の情報処理装置が、
前記第１の情報処理装置と、１又は複数のデータブロックの送信先である第２の情報処理装置との間のネットワークにおいて輻輳が発生したことを検出し、
前記１又は複数のデータブロックの各々について送信時刻及び送達期限を格納するデータ格納部に格納されたデータに基づき、送信時刻から送達期限までの時間が所定時間より長いという条件を満たす第１のデータブロックを特定し、
前記第１のデータブロックの送達期限を含み且つ前記第１のデータブロックの送信時刻を再設定することを要求する第１の要求を、前記第２の情報処理装置に送信し、
前記第２の情報処理装置から、前記第２の情報処理装置により設定された送信時刻を受信する、
処理を実行するデータ送信方法。
【０２１０】
（付記９）
情報処理装置であって、
１又は複数のデータブロックの各々について送信時刻及び送達期限を格納するデータ格納部と、
前記情報処理装置と、前記１又は複数のデータブロックの送信先である他の情報処理装置との間のネットワークにおいて輻輳が発生したことを検出し、前記データ格納部に格納されたデータに基づき、送信時刻から送達期限までの時間が所定時間より長いという条件を満たす第１のデータブロックを特定する特定部と、
前記第１のデータブロックの送達期限を含み且つ前記第１のデータブロックの送信時刻を再設定することを要求する第１の要求を、前記他の情報処理装置に送信し、前記他の情報処理装置から、前記他の情報処理装置により設定された送信時刻を受信する通信部と、
を有する情報処理装置。
【符号の説明】
【０２１１】
１０１  データ受信部
１０２  第１スケジューラ
１０３  リンクデータ格納部
１０４  データ転送ルート格納部
１０５  第１レイテンシデータ格納部
１０６  データキュー
１０７  データ送信部
１０８  第１スケジュールネゴシエータ
１０９  第２スケジューラ
１１０  リソース管理データ格納部
１１１  スケジューリングデータ格納部
１１２  第３レイテンシデータ格納部
１１３  第３スケジューラ
１１５  監視部
１１７  第２スケジュールネゴシエータ
１１９  第２レイテンシデータ格納部
１２１  優先度管理部
１２３  優先度格納部
１２５  隣接ノードデータ格納部
１２７  関連データ格納部
【図１】
0006398674.tif 000002
【図２】
0006398674.tif 000003
【図３】
0006398674.tif 000004
【図４Ａ】
0006398674.tif 000005
【図４Ｂ】
0006398674.tif 000006
【図４Ｃ】
0006398674.tif 000007
【図４Ｄ】
0006398674.tif 000008
【図４Ｅ】
0006398674.tif 000009
【図４Ｆ】
0006398674.tif 000010
【図４Ｇ】
0006398674.tif 000011
【図５】
0006398674.tif 000012
【図６】
0006398674.tif 000013
【図７】
0006398674.tif 000014
【図８】
0006398674.tif 000015
【図９】
0006398674.tif 000016
【図１０】
0006398674.tif 000017
【図１１Ａ】
0006398674.tif 000018
【図１１Ｂ】
0006398674.tif 000019
【図１２】
0006398674.tif 000020
【図１３】
0006398674.tif 000021
【図１４】
0006398674.tif 000022
【図１５】
0006398674.tif 000023
【図１６】
0006398674.tif 000024
【図１７】
0006398674.tif 000025
【図１８】
0006398674.tif 000026
【図１９】
0006398674.tif 000027
【図２０】
0006398674.tif 000028
【図２１】
0006398674.tif 000029
【図２２】
0006398674.tif 000030
【図２３】
0006398674.tif 000031
【図２４】
0006398674.tif 000032
【図２５】
0006398674.tif 000033
【図２６】
0006398674.tif 000034
【図２７】
0006398674.tif 000035
【図２８】
0006398674.tif 000036
【図２９】
0006398674.tif 000037
【図３０】
0006398674.tif 000038
【図３１】
0006398674.tif 000039
【図３２】
0006398674.tif 000040
【図３３】
0006398674.tif 000041
【図３４】
0006398674.tif 000042
【図３５】
0006398674.tif 000043
【図３６】
0006398674.tif 000044
【図３７】
0006398674.tif 000045
【図３８】
0006398674.tif 000046
【図３９】
0006398674.tif 000047
【図４０】
0006398674.tif 000048
【図４１】
0006398674.tif 000049
【図４２】
0006398674.tif 000050
【図４３Ａ】
0006398674.tif 000051
【図４３Ｂ】
0006398674.tif 000052
【図４４】
0006398674.tif 000053
【図４５】
0006398674.tif 000054
【図４６】
0006398674.tif 000055
【図４７】
0006398674.tif 000056
【図４８】
0006398674.tif 000057
【図４９】
0006398674.tif 000058
【図５０Ａ】
0006398674.tif 000059
【図５０Ｂ】
0006398674.tif 000060
【図５１】
0006398674.tif 000061
【図５２】
0006398674.tif 000062
【図５３】
0006398674.tif 000063
【図５４】
0006398674.tif 000064