イベント制御方法、イベント制御装置及びネットワークシミュレーション方法
【課題】ノード間のメッセージの送受信処理の時間粒度が異なるメッセージ列を持つプロトコル、または、時間粒度が異なる複数のプロトコルの動作を行う場合において、処理時間の短縮化を図ることができるイベント制御方法を得る。
【解決手段】互いに独立して動作する複数のサブシステム内で発生する送受信に関する各イベントを処理するに際して、細かい粒度で処理すべきイベントと、粗い粒度で処理可能なイベントが混在している場合のイベント処理を行うイベント制御方法において、前記各イベントのイベント処理を実行するに際して、前記イベントにおける即時送信イベントの有無を判断し、前記イベントに即時送信イベントが含まれる場合に再走査フラグを立てることで、予め設定された単位時間内でイベント処理を繰り返して実行する。
【解決手段】互いに独立して動作する複数のサブシステム内で発生する送受信に関する各イベントを処理するに際して、細かい粒度で処理すべきイベントと、粗い粒度で処理可能なイベントが混在している場合のイベント処理を行うイベント制御方法において、前記各イベントのイベント処理を実行するに際して、前記イベントにおける即時送信イベントの有無を判断し、前記イベントに即時送信イベントが含まれる場合に再走査フラグを立てることで、予め設定された単位時間内でイベント処理を繰り返して実行する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、互いにイベント送受信を行う複数のサブシステムを持つシステムにおけるイベント制御方法に関し、特に、細かい粒度で処理すべきイベントと、粗い粒度で処理可能なイベントが混在している場合に、システム全体の処理時間の短縮化を図るイベント制御方法、及び、イベント制御装置に関する。
また、本発明は、互いに独立して動作する複数のノードが接続されたネットワークに対するネットワークシミュレーション方法に関する。
【背景技術】
【０００２】
互いにイベント送受信を行うシステムにおけるイベント制御方法について、複数のノードのシミュレーションを行うネットワークシミュレーション装置で説明する。
ネットワークシミュレーション装置は、実際にシステムを導入する前に、計画されたネットワークトポロジや使用するデバイスからトポロジ情報とトラヒック情報をもとにモデル化し、トラヒック量や伝搬遅延等についての大まかな推定を行うものであり、シミュレーション用に開発された種々のソフトをネットワーク上で実行することで行われる。このシミュレーションは、単位時間をベースとして複数のノードについて行われる。
【０００３】
例えば、OPNET（商品名）やQualnet（商品名）は、非特許文献１や非特許文献２に示されるように、ネットワークとネットワーク間の接続、ネットワーク上の端末・中継機器上で動作する各種プロトコル（TCP,UDP, HTTPなどの端末プロトコルや、OSPF, BGPなどの中継ノードプロトコルなど）を定義することが可能である。
【０００４】
一方、複雑系シミュレータのArtisoc（商品名）やN3 Simulatorは、非特許文献３や非特許文献４に示されるように、エンド端末の自律分散をシミュレーションすることを目的としたシミュレーション装置であり、エンド端末上のプロトコルを柔軟に定義することが可能である。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】http://www.johokobo.co.jp/opnet/index.html
【非特許文献２】http://www4.kke.co.jp/qualnet/
【非特許文献３】http://www.kke.co.jp/product/catalogue/111_index_msg.html
【非特許文献４】電子情報通信学会 技術研究報告 CPSY2002-32, pp.55-60
【発明の概要】
【発明が解決しようとする課題】
【０００６】
OPNET, Qualnetは、ネットワーク上で、TCP/IP、OSPF/BGPなどのインターネットプロトコルの動作を試験するためのネットワークシミュレーション装置であり、AritisocやN3 Simulatorは、自律分散的に動作するエンド端末をシミュレーションすることに適したシミュレーション装置である。これらのシミュレーション装置では、シミュレーション単位時間ごとに各ノードのイベント処理を行うように設計されているので、単位時間の粒度を細かくすれば、高精度なシミュレーションが可能であるが、処理時間が必要となる。また、単位時間の粒度を粗くすれば、処理時間は削減できるが、シミュレーションの精度が下がる。
【０００７】
シミュレーションは、ある時刻のノードの内部状態を正しく推定した上で、送受信イベントの処理を行う必要があるため、シミュレーション単位時間は、ノードの内部状態の更新頻度に合わせて設定する必要がある。
ノードの内部状態の更新頻度は、ノード上で動作するプロトコルや、与えられたネットワーク構成などによって変化する。上述した例によれば、ノードの内部状態の更新頻度が一定でない（ノードによって異なる、または、ノード上で動作させるプロトコルによって異なる）場合に、精度を高めるには、シミュレーション単位時間の設定を最も短い更新頻度を持つノードやプロトコルに合わせる必要があり、この粒度を必要としないノードやプロトコルにも適用されるため計算時間を余分に要してしまうという問題があった。
【０００８】
すなわち、ノード間のメッセージの送受信処理の時間粒度が異なるメッセージ列を持つプロトコル、または、時間粒度が異なる複数のプロトコルの動作を、一回のシミュレーションで実施する場合、シミュレーションの単位時間を粒度が細かい処理に合わせる必要があり、シミュレーション処理に無駄が生じ、結果的にシミュレーション時間を要するという問題があった。
【０００９】
本発明は上記事情に鑑みて提案されたもので、ノード間のメッセージの送受信処理の時間粒度が異なるメッセージ列を持つプロトコル、または、時間粒度が異なる複数のプロトコルの動作を行う場合において、処理時間の短縮化を図ることができるイベント制御方法及びイベント制御装置、更にはネットワークシミュレーション方法を提供することを目的としている。
【課題を解決するための手段】
【００１０】
上記目的を達成するため本発明は、システムが管理する送受信イベント列において、細かい粒度で処理すべきものについてはイベント毎に再走査フラグを設定することにより、そのイベント列を同一システム単位時間内で繰り返し実行すべきかどうかを選択できるようにしたことを要旨とする。
【００１１】
すなわち、請求項１のイベント制御方法は、互いに独立して動作する複数のサブシステム内で発生する送受信に関する各イベントを処理するに際して、細かい粒度で処理すべきイベントと、粗い粒度で処理可能なイベントが混在している場合のイベント処理を行うイベント制御方法において、
前記各イベントのイベント処理を実行するに際して、前記イベントにおける即時送信イベントの有無を判断し、
前記イベントに即時送信イベントが含まれる場合に再走査フラグを立てることで、予め設定された単位時間内でイベント処理を繰り返して実行する
ことを特徴とする。
【００１２】
請求項２のイベント制御装置は、互いに独立して動作する複数のサブシステム内の各ノードで発生する各イベントを処理するに際して、細かい粒度で処理すべきイベントと、粗い粒度で処理可能なイベントが混在している場合のイベント処理を行う装置において、次の構成を含むことを特徴としている。
前記イベントの種類を判別し前記イベントにおける即時送信イベントの有無を判断してイベント処理を実行するイベント処理部。
前記イベントが即時送信イベントを含む時に相手ノードをリスト（ＲＮＬnext）に追加することでイベント処理の再走査の有無を管理する次回再走査ノードリスト。
イベント処理を実行するノードのリストを管理するとともに、リスト上のノードに関して１回分の再走査を行うため前記次回再走査ノードリストのリストのデータを移動した現再走査ノードリスト。
【００１３】
請求項３のネットワークシミュレーション方法は、互いに独立して動作する複数のノードが接続されたネットワークに対して、請求項１のイベント制御方法を利用して各ノードのイベント処理についてのシミュレーションを行うことを特徴としている。
【発明の効果】
【００１４】
本発明によれば、同一単位時間で処理する送信イベントの有無を予め判断しておくことにより、細かい粒度を必要とするプロトコル動作のみを同一単位時間において繰り返して処理するようにする。これにより、細かい粒度で処理すべきイベント列が存在しても、システム処理単位時間を粗くすることができる。
その結果、シミュレーションを行うに際して単位時間を長く設定しても、計算時間が早くなる上、精度を失うことなくシミュレーションを実行することができ、シミュレーション精度（システムの処理精度）を維持したまま、トータルとしてのシステム処理時間を短縮することができる。
ただし、上述の効果は、細かい粒度で処理すべきイベントと粗い粒度で処理可能なイベントが混在している場合で、細かい粒度で処理すべきイベント列の全イベントに占める割合が大きくない場合にのみ達成できる。
【図面の簡単な説明】
【００１５】
【図１】本発明のネットワークシミュレーション装置の構成を説明するための機能ブロック図である。
【図２】本発明のネットワークシミュレーション装置が適用されるネットワークトポロジの模式図である。
【図３】（ａ）〜（ｄ）は本発明のイベント制御方法で扱うメッセージ例を示す模式図である。
【図４】本発明のイベント制御の手順を説明するためのフローチャート図である。
【図５】図４のイベント制御におけるイベント処理ステップの詳細手順を説明するためのフローチャート図である。
【図６】図５のイベント処理におけるイベント実行ステップの詳細手順を説明するためのフローチャート図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態の一例について、図１及び図２を参照しながら説明する。
実施形態の一例としては、イベント制御方法（イベント制御装置）をネットワークシミュレーション装置に適用する場合について説明する。なお、本発明のイベント制御方法（イベント制御装置）は、ネットワークシミュレーション装置に限らず、同様の構成を持つシステムに対しても適用可能である。
【００１７】
本発明のイベント制御方法が適用されたシミュレーション装置３０は、多数のノード（端末、ルータ、サーバ等の総称）が接続されて構成されるＰ２Ｐ中継システムを構築するネットワークについて、各ノード間のトラヒック量やダウンロード時間の算出を目的としたシミュレーションを行うものであり、図１に示すように、ネットワーク内においてシミュレーションを行うユーザ４０に対して接続可能に構成されている。
【００１８】
ネットワークシミュレーション装置３０は、ユーザ４０からの要求により後述するシミュレーション動作フローにしたがってシミュレーションの実行を行うシミュレーション実行管理部３１と、シミュレーションの設定情報を管理する設定管理部３２と、ネットワークの状態を管理するネットワーク状態管理部３３と、各ノードにおけるイベントの実行をそれぞれ行う複数のノード実行部３４と、各ノード実行部３４でのイベントの実行結果を記録するログ管理部３５と、ユーザ４０からの要求に基づきログ管理部３５を参照してシミュレーション結果を表示するシミュレーション結果表示部３６とを備えて構成されている。
【００１９】
ネットワーク状態管理部３３は、ネットワークシミュレーション装置３０がシミュレーションするネットワーク構成を管理するとともに、ネットワークにおけるクラスタ間の経路管理(SPFで導出されるクラスタ間の経路についての管理)、及び、後述するクラスタ間リンク及びノードリンクの出力キューについてのキュー管理を行う。ネットワークシミュレーション装置３０がシミュレーションするネットワークトポロジは、図２に示すように、いくつかの小さなネットワークであるクラスタに分割される。
各クラスタは、他の地域との接続やISPとの中継を行う部分であるブランチクラスタ１０と、ユーザ（Ｐ２Ｐ中継システムではピアと呼ぶ）が属するアクセスネットワークよりの部分であるリーフクラスタ２０に分かれ、それぞれが相互に接続されている。
【００２０】
ブランチクラスタ１０には、相互に接続された複数のネットワーク中継機器(ルータ等)１１を有している。また、ブランチクラスタ１０によっては、Ｐ２Ｐ中継システムの一部を担うサーバ１２｛コンテンツサーバ、配信制御サーバ（トラッカー）等｝が設定されている。
【００２１】
リーフクラスタ２０は、アクセスネットワークを集約する機器を含んで構成され、機器の配下に複数のピア２１が設定されている。ブランチクラスタ１０は制限なく互いに接続できるが、リーフクラスタ２０はいずれか１つのブランチクラスタ１０のみと接続するようになっている。
【００２２】
ネットワークシミュレーション装置によるネットワークのシミュレーションは、以下のように単純化させて定義する。経路計算は、ブランチクラスタ１０又はリーフクラスタ２０毎のクラスタ単位で行われる。すなわち、クラスタ間に論理的なリンクが存在すると仮定し、リンク毎にコストや伝搬遅延を管理することが行われる。
【００２３】
あるクラスタから別のクラスタへの経路は、OSPFで用いられているSPFアルゴリズムと同様の方法で計算する。従って、クラスタ内のノードが別のクラスタのノードと通信する場合には、上記手段により、リンク毎に計算された経路を用いて通信を行う。
【００２４】
設定管理部３２は、ネットワークをシミュレーションする場合のシミュレーション設定情報を管理する。例えば、どのクラスタ（ノード）とクラスタ（ノード）との間のトラヒック量をシミュレーションするか、Ｐ２Ｐによる各ピースの取得を行うノード（ピア）についての情報はユーザ４０が入力することにより行われる。
また、シミュレーション設定情報の初期設定情報は、ユーザ４０がシミュレーション実行前に設定するものであり、ネットワーク構成（ブランチクラスタ１０又はリーフクラスタ２０）、リンクの接続構成（クラスタ間リンク（リンク１５及びリンク１６）又はノードリンク２２）、各クラスタ上のノード数・種類（ピア又はトラッカー）、ノードの起動タイミングなどの情報を含む。
【００２５】
ノード実行部３４は、ピアまたはトラッカーのいずれかのアルゴリズムに従い、イベント管理において管理しているイベントについて、１つのノードの動作を実行する。本発明のネットワークシミュレーション装置では、10,000以上の独立なノードのシミュレーションを行うことを想定しているため、独立なノード数だけノード実行部３４が存在する。各ノード実行部３４は、ミュレーション処理時間(SUT)を単位に１回、シミュレーション実行管理部３１よりノードID順に呼び出され、イベント管理において管理しているイベントのうち、そのシミュレーション処理時間(SUT)で実行すべきイベントを実行する。ノードは、ピアあるいはトラッカーのいずれかのアルゴリズムを持ち、それぞれのアルゴリズムに従ってイベントの実行を行う。イベントの実行結果は、時系列順に記録され、ログ管理部３５に蓄積される。
【００２６】
ログ管理部３５は、イベント毎に、処理に必要なイベント実行時刻，ノード，相手先ノード，イベント種別の情報が記憶されることで、トラヒック量等のシミュレーション結果を求めることができる。
【００２７】
ノード実行部３４でのイベント処理について説明する。
受信イベント処理は、メッセージの受信に伴うノード状態の更新を行う。ログ管理部３５に、受信イベント処理を行ったことを通知する。さらに、ピア／トラッカーアルゴリズムに従い、他の相手先ノード(複数もありうる)へメッセージを送信する必要がある場合には、送信イベント(複数もありうる)を設定し、送信イベント処理を行う。メッセージの送信に伴うノード状態の更新を行い、ログ管理部３５に送信イベント処理を行ったことを通知する。また、ネットワーク状態管理部３３に該当ノードから相手先ノードへの遅延の計算を依頼し、その結果、相手ノードに、現シミュレーション処理時間(SUT)に遅延時間を加えた時刻をイベント受信時刻として、本メッセージに関する受信イベントを設定する。
【００２８】
上述した構成のネットワークシミュレーション装置は、ｎ個（数万を仮定しているが数量に規定はない）のノード（Ｎ1〜Ｎn）が自律的に動作し、予め設定されたシステム単位時間（SUT: System Time Unit）毎に、イベント駆動型で処理を実行する。各ノードは、イベントキューを持ち、イベントキューには、イベント毎に、実行すべき時刻、イベント発信元、メッセージタイプ、メッセージパラメータの情報が記録される。
【００２９】
イベントには、送信イベント、受信イベント、内部イベントが存在する。送信イベントは、別のノード(相手ノード)にメッセージを送信するイベントであり、相手ノードへの受信イベントとなる。送信イベントには、即時送信イベントと、経過送信イベントの２種類が存在する。
【００３０】
即時送信イベントは、シミュレーション単位時間内で送信実行（つまり相手ノードでの受信）を完了するイベントであり、経過送信イベントは、実行完了までに１SUT以上の経過を必要とするイベントである。即時送信イベントを処理する際には、同じシミュレーション時刻（ｘ SUT、ただしｘはシミュレーション開始からの経過時間を、SUTを単位として表したもの）において、相手ノードでのイベント処理を行う。
【００３１】
受信イベントは、別のノード(相手ノード)からメッセージを受信するイベントであり、受信メッセージ処理としてノード内部状態の更新を行うとともに、条件によっては相手ノードあるいは更に別のノードに送信イベント（即時送信イベントまたは経過送信イベント）を発生させる。
内部イベントは、ノード内部の状態変更のみを行うイベントである。
【００３２】
イベントとその組み合わせのパターンについて、図３を参照して説明する。
図３（ａ）及び（ｂ）は、ノード間（ＮａとＮｂ）で１つのメッセージを送信する際に発生するイベントを示す。メッセージの転送元では送信イベント、メッセージの転送先では受信イベントとして扱われる。即時イベントの場合は、同一シミュレーション時刻にイベントが発生し、経過イベントでは、受信イベントが１SUT以上遅れて実行される。
図３（ｃ）は、内部イベントの例であり、一つのノードでのみイベントが発生する。
図３（ｄ）は、ノード（Ｎａ）の受信イベントに対する応答の組み合わせを示したものである。応答イベントは、即時送信イベント、経過送信イベントのいずれの場合も存在し、さらに、受信イベントの相手ノードと同じ・異なる場合や、一つの受信イベントに対し、複数の送信イベントが存在する場合もある。
【００３３】
本イベント制御方法（イベント制御装置）においては、イベント処理を実行するに際して、当該イベントに即時送信イベントが含まれる場合に再走査フラグを立てることで、予め設定されたシミュレーション時刻（単位時間）内でイベント処理を繰り返して実行する処理を行う。
これを実現するため、イベント制御装置では、前記イベントの種類を判別し前記イベントにおける即時送信イベントの有無を判断してイベント処理を実行するイベント処理部と、イベント処理の再走査の有無を管理する次回再走査ノードリストと、イベント処理を実行するノードのリストを管理する現再走査ノードリストとを有している。
次回再走査ノードリストは、イベントが即時送信イベントを含む時に相手ノードを次回再走査ノードリスト(ＲＮＬnext)に追加することでイベント処理の再走査の有無を管理するものである。
現再走査ノードリストは、イベント処理を実行するノードを現再走査ノードリスト(ＲＮＬnow)で管理するとともに、リスト上のノードに関して１回分の再走査を行うため前記次回再走査ノードリストのリストのデータを移動するものである。
【００３４】
次に、シミュレーション実行管理部３１及びノード実行部３４の動作について、図４のフローチャート図を参照して説明する。
本シミュレーション装置は、シミュレーション処理時間(SUT)ごとに、各ノードがイベント駆動型で独立に処理を実行する。イベントキューは、シミュレーション実行中に、SUT毎に、動的に更新される。
【００３５】
シミュレーション装置起動時に、各ノードのシミュレーション初期条件を設定し、現在実行中のシミュレーション時刻Ｔnowを「０」とする（ステップ１０１）。初期条件としては、ノード数、各ノードで動作するプロトコル、あるノードに指定時刻に発生するイベントなどがある。
初期状態として、次回再走査ノードリスト(ＲＮＬnext)を空に設定し（ステップ１０２）、実行中ノード(Ｎnow)を「１」に設定する（ステップ１０３）。イベント処理として、そのノードのイベントキューに含まれるイベントを実行する（ステップ１０４）。
【００３６】
イベント処理での手順については後述する（図５）。
【００３７】
次に、Ｎnowを「１」増加させ（ステップ１０５）、Ｎnowが「ｎ」以下であればステップ１０４に戻ってイベント処理から繰り返す（ステップ１０６）。Ｎnowが「ｎ」より大きい場合、ループを抜ける。
【００３８】
ステップ１０４のイベント処理において、イベントに即時送信イベントが含まれる場合（0 SUTで送受信されるメッセージがあった場合）、同一SUT内で複数回同一ノードの処理が行われる。すなわち、再走査フラグを立てることで、予め設定されたシミュレーション時間（単位時間）内でイベント処理を繰り返して実行する処理を行う。
すなわち、再走査ノードリスト（ＲＮＬnext）が空かどうかを判断し（ステップ１０７）、ＲＮＬnextが空でなければ、再走査の動作を実行する。再走査では、先ず、リスト上のノードに関して１回分の再走査を行うため現再走査ノードリストＲＮＬnowにＲＮＬnext の値を設定し（ＲＮＬnextのデータを移動する）、ＲＮＬnextを空とする（ステップ１０８）。
【００３９】
次に、ＲＮＬnowより順にノードを抽出し（ステップ１０９）、抽出したノードのイベント処理を実行する（ステップ１１０）。抽出したノードは、ＲＮＬnowから削除され（ステップ１０９）、ノードＲＮＬnowが空となるまで繰り返し実行する（ステップ１１１）。
その後、ＲＮＬnextが空かどうかを再度確認し（ステップ１０７）、空でなければ再び再走査の処理を実行する。ＲＮＬnext が空であれば、Ｔnowを「１」増加させ（ステップ１１２）、Ｔnowが予め設定されたシミュレーション時間Ｔmaxより小さい場合には、最初のノードからのイベント処理に戻る（ステップ１１３）。Ｔnow≧Ｔmaxの場合には、シミュレーション終了条件が成立したとしてシミュレーション結果を出力し（ステップ１１４）、シミュレーションを終了する。
【００４０】
図４のステップ１０４におけるノード、シミュレーション単位時間毎に実行されるイベント処理について、図５のフローチャート図を参照して説明する。
実行中ノードのイベントキューより、時刻Ｔnowで実行すべきイベントのリスト(Ｅ1〜Ｅm)を抽出する（ステップ２０１）。
イベント処理される先頭のリストについて、「１」（ｋ＝１）に設定し（ステップ２０２）、イベントＥkを実行する（ステップ２０３）。
「ｋ」を「１」増加し（ステップ２０４）、「ｋ」が「ｍ」以下になるまで、これらのイベントを順に繰り返し実行する。全イベントの処理を終了後（ステップ２０５）、イベント処理を終了する。
【００４１】
図５のステップ２０３におけるイベントＥkを実行する際の動作について、図６のフローチャート図を参照して説明する。
先ず、処理するイベントについて、送信イベント、受信イベント、内部イベントであるかのイベントタイプによる分岐を行う（ステップ３０１）。
【００４２】
送信イベントの場合、ノード内部状態の更新を行い（ステップ３０２）、相手ノードのイベントキューに受信イベントとして追加する（ステップ３０３）。
この際、相手ノードにとっては、a SUT時間後にそのイベントが発生するようにイベントの追加が行われる（ステップ３０３）が、このうち「a＝０」のものがあるかどうか（即時イベントの有無）を判断する（ステップ３０３）。即時送信イベントが存在する場合は、本イベントを実行する際に、同じシミュレーション時刻において相手ノードでの受信イベントを実行できるように、ＲＮＬnextに相手ノードを追加することで再走査フラグを立てる（ステップ３０５）。
【００４３】
受信イベントの場合、ノード内部状態の更新を行った後（ステップ３１２）、応答となる送信イベントが有るか否かを判断し（ステップ３１３）、応答となる送信イベントが有る場合には、本送信イベントに伴うノード内部状態の更新を行い（ステップ３１４）、送信イベントと同様のステップ３０３以降の処理を行う。
内部イベントの場合は、ノード内部状態の更新のみを行う（ステップ３２２）。
【００４４】
上述のイベント制御方法を実現する場合、対象とするプロトコルが扱う送信イベントが、即時送信イベント、経過送信イベントのいずれであるかを定義する必要がある。どのイベントを即時イベントとして定義するかはシミュレーションの実行環境により異なる。例えば以下のような例が考えられる。
（１）固定網・移動網を含むネットワークを用いて、シミュレーションを行う場合、メッセージが到着するまでの遅延が小さい固定網上でのメッセージ転送に関するイベントは、全て即時送信イベントとする。
（２）メッセージ交換粒度の異なる複数のプロトコルを扱う場合、交換粒度の細かいプロトコルについては、全て即時送信イベントとする。
（３）あるプロトコルにおいて、サイズが大きいデータメッセージと、サイズが小さい制御メッセージを扱う場合、サイズが小さい制御メッセージについては、即時送信イベントとする。
【００４５】
次に、上述したイベント制御方法を使用したシミュレーション計算時間の短縮効果について考察する。
１シミュレーション時刻(SUT)において、１ノードを処理するのに要する時間をtdとし、ノード数をｎ、シミュレーション時間をＴmax SUTとした場合、従前のイベント処理の方法による計算時間Ｔexは、
Ｔex ＝ｎ×Ｔmax × td
となる。
【００４６】
これに対して上述したイベント制御方法によれば、ｘ倍のシミュレーション単位時間を適用できるため、シミュレーション時間は、Ｔmax／ｘ SUTとなる。繰り返し再走査も含め、再走査に要する延べノード数の平均をnrとした場合、
Ｔex ＝（ｎ＋ｎr）×Ｔmax ／（Ｘ × td）
となる。
したがって、上述したイベント制御方法によれば、従前のイベント処理方法に対して、（ｎ＋ｎr）／ｎ／Ｘの計算時間で処理できることとなる。
【００４７】
なお、この式からは、ｎrが極端に大きい場合には、従前の方法よりも計算時間がかかることになるが、ｎrが極端に大きくなる場合は、従前の方法においても精度が保証されないので、このような場合を想定する必要はない。
【００４８】
上述のネットワークシミュレーション装置によれば、同一シミュレーション時間で処理する送信イベントの有無を予め判断することにより、細かい粒度を必要とするプロトコル動作のみを同一シミュレーション時間において繰り返してイベント処理（再走査）できることを可能とする。これにより、シミュレーション単位時間を長く設定しても、計算時間が早くなる上、精度を失うことなくシミュレーションを実行できる。
【００４９】
シミュレーション単位時間を長く設定した場合、同一シミュレーション時間で処理するイベント(即時送信イベント)に対する計算時間は、従来のネットワークシミュレーション装置と同様である。同一シミュレーション時間で処理しないイベント（経過送信イベント）の処理において、イベント駆動有無の確認などの無駄な時間を省けるため、処理時間を短縮することができる。従って、最も多く発生し得るノード内部状態の更新頻度に合わせて、シミュレーション単位時間を設定するのが効果的である。
【００５０】
次に、ノード内部状態の更新頻度が異なる例について説明する。
ネットワーク構成の例としては、２ノードが１Gbit/sの高速な固定リンクに接続され、残りのノードがいずれかのノードに低速な無線リンク(例えば１Mbit/s)で接続されている例である。この場合、シミュレーション単位時間を、１Mbit/sのリンク上で１パケット(1500バイト)を送信するのに要する時間(12msec)と設定しても、この時間内に、固定リンク上の２ノード間で繰り返しやりとりされるメッセージに関するイベントを処理することができる。
【００５１】
プロトコルの例としては、TCP(Transmission Control Protocol)とBGP(Border Gateway Protocol)の振舞いをシミュレーションする場合が考えられる。TCPについてはデータパケットの送信処理や、RTTに基づく再送、輻輳制御などの計算処理などを行うため、１msecあるいはそれよりも細かい単位で処理する必要がある。
一方、BGPでのメッセージ送受信処理は、BGPに関する内部状態の更新頻度が粗いため、１秒程度で十分である。BGPの振舞いのシミュレーションを主目的としながら、TCPの振舞いも扱う場合には本発明の利用が効果的である。
【００５２】
上述した例では、イベント処理を実行するイベント制御方法をネットワークシミュレーション装置に用いたが、同様の構成を持つシステムに適用可能である。すなわち、複数のサブシステムを有し、サブシステム間で異なる頻度でやりとりされるメッセージが存在し、各サブシステムがイベント駆動型で設計されたシステムに関して適用することができる。
【符号の説明】
【００５３】
１…ネットワーク、 １０…ブランチクラスタ、 １１…ネットワーク中継機器(ルータ)、 １２…サーバ、 ２０…リーフクラスタ、 ２１…ピア、 ３０…ネットワークシミュレーション装置、 ３１…シミュレーション実行管理部、 ３２…設定管理部、 ３３…ネットワーク状態管理部、 ３４…ノード実行部、 ３５…ログ管理部、 ３６…シミュレーション結果表示部、 ４０…ユーザ。
【技術分野】
【０００１】
本発明は、互いにイベント送受信を行う複数のサブシステムを持つシステムにおけるイベント制御方法に関し、特に、細かい粒度で処理すべきイベントと、粗い粒度で処理可能なイベントが混在している場合に、システム全体の処理時間の短縮化を図るイベント制御方法、及び、イベント制御装置に関する。
また、本発明は、互いに独立して動作する複数のノードが接続されたネットワークに対するネットワークシミュレーション方法に関する。
【背景技術】
【０００２】
互いにイベント送受信を行うシステムにおけるイベント制御方法について、複数のノードのシミュレーションを行うネットワークシミュレーション装置で説明する。
ネットワークシミュレーション装置は、実際にシステムを導入する前に、計画されたネットワークトポロジや使用するデバイスからトポロジ情報とトラヒック情報をもとにモデル化し、トラヒック量や伝搬遅延等についての大まかな推定を行うものであり、シミュレーション用に開発された種々のソフトをネットワーク上で実行することで行われる。このシミュレーションは、単位時間をベースとして複数のノードについて行われる。
【０００３】
例えば、OPNET（商品名）やQualnet（商品名）は、非特許文献１や非特許文献２に示されるように、ネットワークとネットワーク間の接続、ネットワーク上の端末・中継機器上で動作する各種プロトコル（TCP,UDP, HTTPなどの端末プロトコルや、OSPF, BGPなどの中継ノードプロトコルなど）を定義することが可能である。
【０００４】
一方、複雑系シミュレータのArtisoc（商品名）やN3 Simulatorは、非特許文献３や非特許文献４に示されるように、エンド端末の自律分散をシミュレーションすることを目的としたシミュレーション装置であり、エンド端末上のプロトコルを柔軟に定義することが可能である。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】http://www.johokobo.co.jp/opnet/index.html
【非特許文献２】http://www4.kke.co.jp/qualnet/
【非特許文献３】http://www.kke.co.jp/product/catalogue/111_index_msg.html
【非特許文献４】電子情報通信学会 技術研究報告 CPSY2002-32, pp.55-60
【発明の概要】
【発明が解決しようとする課題】
【０００６】
OPNET, Qualnetは、ネットワーク上で、TCP/IP、OSPF/BGPなどのインターネットプロトコルの動作を試験するためのネットワークシミュレーション装置であり、AritisocやN3 Simulatorは、自律分散的に動作するエンド端末をシミュレーションすることに適したシミュレーション装置である。これらのシミュレーション装置では、シミュレーション単位時間ごとに各ノードのイベント処理を行うように設計されているので、単位時間の粒度を細かくすれば、高精度なシミュレーションが可能であるが、処理時間が必要となる。また、単位時間の粒度を粗くすれば、処理時間は削減できるが、シミュレーションの精度が下がる。
【０００７】
シミュレーションは、ある時刻のノードの内部状態を正しく推定した上で、送受信イベントの処理を行う必要があるため、シミュレーション単位時間は、ノードの内部状態の更新頻度に合わせて設定する必要がある。
ノードの内部状態の更新頻度は、ノード上で動作するプロトコルや、与えられたネットワーク構成などによって変化する。上述した例によれば、ノードの内部状態の更新頻度が一定でない（ノードによって異なる、または、ノード上で動作させるプロトコルによって異なる）場合に、精度を高めるには、シミュレーション単位時間の設定を最も短い更新頻度を持つノードやプロトコルに合わせる必要があり、この粒度を必要としないノードやプロトコルにも適用されるため計算時間を余分に要してしまうという問題があった。
【０００８】
すなわち、ノード間のメッセージの送受信処理の時間粒度が異なるメッセージ列を持つプロトコル、または、時間粒度が異なる複数のプロトコルの動作を、一回のシミュレーションで実施する場合、シミュレーションの単位時間を粒度が細かい処理に合わせる必要があり、シミュレーション処理に無駄が生じ、結果的にシミュレーション時間を要するという問題があった。
【０００９】
本発明は上記事情に鑑みて提案されたもので、ノード間のメッセージの送受信処理の時間粒度が異なるメッセージ列を持つプロトコル、または、時間粒度が異なる複数のプロトコルの動作を行う場合において、処理時間の短縮化を図ることができるイベント制御方法及びイベント制御装置、更にはネットワークシミュレーション方法を提供することを目的としている。
【課題を解決するための手段】
【００１０】
上記目的を達成するため本発明は、システムが管理する送受信イベント列において、細かい粒度で処理すべきものについてはイベント毎に再走査フラグを設定することにより、そのイベント列を同一システム単位時間内で繰り返し実行すべきかどうかを選択できるようにしたことを要旨とする。
【００１１】
すなわち、請求項１のイベント制御方法は、互いに独立して動作する複数のサブシステム内で発生する送受信に関する各イベントを処理するに際して、細かい粒度で処理すべきイベントと、粗い粒度で処理可能なイベントが混在している場合のイベント処理を行うイベント制御方法において、
前記各イベントのイベント処理を実行するに際して、前記イベントにおける即時送信イベントの有無を判断し、
前記イベントに即時送信イベントが含まれる場合に再走査フラグを立てることで、予め設定された単位時間内でイベント処理を繰り返して実行する
ことを特徴とする。
【００１２】
請求項２のイベント制御装置は、互いに独立して動作する複数のサブシステム内の各ノードで発生する各イベントを処理するに際して、細かい粒度で処理すべきイベントと、粗い粒度で処理可能なイベントが混在している場合のイベント処理を行う装置において、次の構成を含むことを特徴としている。
前記イベントの種類を判別し前記イベントにおける即時送信イベントの有無を判断してイベント処理を実行するイベント処理部。
前記イベントが即時送信イベントを含む時に相手ノードをリスト（ＲＮＬnext）に追加することでイベント処理の再走査の有無を管理する次回再走査ノードリスト。
イベント処理を実行するノードのリストを管理するとともに、リスト上のノードに関して１回分の再走査を行うため前記次回再走査ノードリストのリストのデータを移動した現再走査ノードリスト。
【００１３】
請求項３のネットワークシミュレーション方法は、互いに独立して動作する複数のノードが接続されたネットワークに対して、請求項１のイベント制御方法を利用して各ノードのイベント処理についてのシミュレーションを行うことを特徴としている。
【発明の効果】
【００１４】
本発明によれば、同一単位時間で処理する送信イベントの有無を予め判断しておくことにより、細かい粒度を必要とするプロトコル動作のみを同一単位時間において繰り返して処理するようにする。これにより、細かい粒度で処理すべきイベント列が存在しても、システム処理単位時間を粗くすることができる。
その結果、シミュレーションを行うに際して単位時間を長く設定しても、計算時間が早くなる上、精度を失うことなくシミュレーションを実行することができ、シミュレーション精度（システムの処理精度）を維持したまま、トータルとしてのシステム処理時間を短縮することができる。
ただし、上述の効果は、細かい粒度で処理すべきイベントと粗い粒度で処理可能なイベントが混在している場合で、細かい粒度で処理すべきイベント列の全イベントに占める割合が大きくない場合にのみ達成できる。
【図面の簡単な説明】
【００１５】
【図１】本発明のネットワークシミュレーション装置の構成を説明するための機能ブロック図である。
【図２】本発明のネットワークシミュレーション装置が適用されるネットワークトポロジの模式図である。
【図３】（ａ）〜（ｄ）は本発明のイベント制御方法で扱うメッセージ例を示す模式図である。
【図４】本発明のイベント制御の手順を説明するためのフローチャート図である。
【図５】図４のイベント制御におけるイベント処理ステップの詳細手順を説明するためのフローチャート図である。
【図６】図５のイベント処理におけるイベント実行ステップの詳細手順を説明するためのフローチャート図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態の一例について、図１及び図２を参照しながら説明する。
実施形態の一例としては、イベント制御方法（イベント制御装置）をネットワークシミュレーション装置に適用する場合について説明する。なお、本発明のイベント制御方法（イベント制御装置）は、ネットワークシミュレーション装置に限らず、同様の構成を持つシステムに対しても適用可能である。
【００１７】
本発明のイベント制御方法が適用されたシミュレーション装置３０は、多数のノード（端末、ルータ、サーバ等の総称）が接続されて構成されるＰ２Ｐ中継システムを構築するネットワークについて、各ノード間のトラヒック量やダウンロード時間の算出を目的としたシミュレーションを行うものであり、図１に示すように、ネットワーク内においてシミュレーションを行うユーザ４０に対して接続可能に構成されている。
【００１８】
ネットワークシミュレーション装置３０は、ユーザ４０からの要求により後述するシミュレーション動作フローにしたがってシミュレーションの実行を行うシミュレーション実行管理部３１と、シミュレーションの設定情報を管理する設定管理部３２と、ネットワークの状態を管理するネットワーク状態管理部３３と、各ノードにおけるイベントの実行をそれぞれ行う複数のノード実行部３４と、各ノード実行部３４でのイベントの実行結果を記録するログ管理部３５と、ユーザ４０からの要求に基づきログ管理部３５を参照してシミュレーション結果を表示するシミュレーション結果表示部３６とを備えて構成されている。
【００１９】
ネットワーク状態管理部３３は、ネットワークシミュレーション装置３０がシミュレーションするネットワーク構成を管理するとともに、ネットワークにおけるクラスタ間の経路管理(SPFで導出されるクラスタ間の経路についての管理)、及び、後述するクラスタ間リンク及びノードリンクの出力キューについてのキュー管理を行う。ネットワークシミュレーション装置３０がシミュレーションするネットワークトポロジは、図２に示すように、いくつかの小さなネットワークであるクラスタに分割される。
各クラスタは、他の地域との接続やISPとの中継を行う部分であるブランチクラスタ１０と、ユーザ（Ｐ２Ｐ中継システムではピアと呼ぶ）が属するアクセスネットワークよりの部分であるリーフクラスタ２０に分かれ、それぞれが相互に接続されている。
【００２０】
ブランチクラスタ１０には、相互に接続された複数のネットワーク中継機器(ルータ等)１１を有している。また、ブランチクラスタ１０によっては、Ｐ２Ｐ中継システムの一部を担うサーバ１２｛コンテンツサーバ、配信制御サーバ（トラッカー）等｝が設定されている。
【００２１】
リーフクラスタ２０は、アクセスネットワークを集約する機器を含んで構成され、機器の配下に複数のピア２１が設定されている。ブランチクラスタ１０は制限なく互いに接続できるが、リーフクラスタ２０はいずれか１つのブランチクラスタ１０のみと接続するようになっている。
【００２２】
ネットワークシミュレーション装置によるネットワークのシミュレーションは、以下のように単純化させて定義する。経路計算は、ブランチクラスタ１０又はリーフクラスタ２０毎のクラスタ単位で行われる。すなわち、クラスタ間に論理的なリンクが存在すると仮定し、リンク毎にコストや伝搬遅延を管理することが行われる。
【００２３】
あるクラスタから別のクラスタへの経路は、OSPFで用いられているSPFアルゴリズムと同様の方法で計算する。従って、クラスタ内のノードが別のクラスタのノードと通信する場合には、上記手段により、リンク毎に計算された経路を用いて通信を行う。
【００２４】
設定管理部３２は、ネットワークをシミュレーションする場合のシミュレーション設定情報を管理する。例えば、どのクラスタ（ノード）とクラスタ（ノード）との間のトラヒック量をシミュレーションするか、Ｐ２Ｐによる各ピースの取得を行うノード（ピア）についての情報はユーザ４０が入力することにより行われる。
また、シミュレーション設定情報の初期設定情報は、ユーザ４０がシミュレーション実行前に設定するものであり、ネットワーク構成（ブランチクラスタ１０又はリーフクラスタ２０）、リンクの接続構成（クラスタ間リンク（リンク１５及びリンク１６）又はノードリンク２２）、各クラスタ上のノード数・種類（ピア又はトラッカー）、ノードの起動タイミングなどの情報を含む。
【００２５】
ノード実行部３４は、ピアまたはトラッカーのいずれかのアルゴリズムに従い、イベント管理において管理しているイベントについて、１つのノードの動作を実行する。本発明のネットワークシミュレーション装置では、10,000以上の独立なノードのシミュレーションを行うことを想定しているため、独立なノード数だけノード実行部３４が存在する。各ノード実行部３４は、ミュレーション処理時間(SUT)を単位に１回、シミュレーション実行管理部３１よりノードID順に呼び出され、イベント管理において管理しているイベントのうち、そのシミュレーション処理時間(SUT)で実行すべきイベントを実行する。ノードは、ピアあるいはトラッカーのいずれかのアルゴリズムを持ち、それぞれのアルゴリズムに従ってイベントの実行を行う。イベントの実行結果は、時系列順に記録され、ログ管理部３５に蓄積される。
【００２６】
ログ管理部３５は、イベント毎に、処理に必要なイベント実行時刻，ノード，相手先ノード，イベント種別の情報が記憶されることで、トラヒック量等のシミュレーション結果を求めることができる。
【００２７】
ノード実行部３４でのイベント処理について説明する。
受信イベント処理は、メッセージの受信に伴うノード状態の更新を行う。ログ管理部３５に、受信イベント処理を行ったことを通知する。さらに、ピア／トラッカーアルゴリズムに従い、他の相手先ノード(複数もありうる)へメッセージを送信する必要がある場合には、送信イベント(複数もありうる)を設定し、送信イベント処理を行う。メッセージの送信に伴うノード状態の更新を行い、ログ管理部３５に送信イベント処理を行ったことを通知する。また、ネットワーク状態管理部３３に該当ノードから相手先ノードへの遅延の計算を依頼し、その結果、相手ノードに、現シミュレーション処理時間(SUT)に遅延時間を加えた時刻をイベント受信時刻として、本メッセージに関する受信イベントを設定する。
【００２８】
上述した構成のネットワークシミュレーション装置は、ｎ個（数万を仮定しているが数量に規定はない）のノード（Ｎ1〜Ｎn）が自律的に動作し、予め設定されたシステム単位時間（SUT: System Time Unit）毎に、イベント駆動型で処理を実行する。各ノードは、イベントキューを持ち、イベントキューには、イベント毎に、実行すべき時刻、イベント発信元、メッセージタイプ、メッセージパラメータの情報が記録される。
【００２９】
イベントには、送信イベント、受信イベント、内部イベントが存在する。送信イベントは、別のノード(相手ノード)にメッセージを送信するイベントであり、相手ノードへの受信イベントとなる。送信イベントには、即時送信イベントと、経過送信イベントの２種類が存在する。
【００３０】
即時送信イベントは、シミュレーション単位時間内で送信実行（つまり相手ノードでの受信）を完了するイベントであり、経過送信イベントは、実行完了までに１SUT以上の経過を必要とするイベントである。即時送信イベントを処理する際には、同じシミュレーション時刻（ｘ SUT、ただしｘはシミュレーション開始からの経過時間を、SUTを単位として表したもの）において、相手ノードでのイベント処理を行う。
【００３１】
受信イベントは、別のノード(相手ノード)からメッセージを受信するイベントであり、受信メッセージ処理としてノード内部状態の更新を行うとともに、条件によっては相手ノードあるいは更に別のノードに送信イベント（即時送信イベントまたは経過送信イベント）を発生させる。
内部イベントは、ノード内部の状態変更のみを行うイベントである。
【００３２】
イベントとその組み合わせのパターンについて、図３を参照して説明する。
図３（ａ）及び（ｂ）は、ノード間（ＮａとＮｂ）で１つのメッセージを送信する際に発生するイベントを示す。メッセージの転送元では送信イベント、メッセージの転送先では受信イベントとして扱われる。即時イベントの場合は、同一シミュレーション時刻にイベントが発生し、経過イベントでは、受信イベントが１SUT以上遅れて実行される。
図３（ｃ）は、内部イベントの例であり、一つのノードでのみイベントが発生する。
図３（ｄ）は、ノード（Ｎａ）の受信イベントに対する応答の組み合わせを示したものである。応答イベントは、即時送信イベント、経過送信イベントのいずれの場合も存在し、さらに、受信イベントの相手ノードと同じ・異なる場合や、一つの受信イベントに対し、複数の送信イベントが存在する場合もある。
【００３３】
本イベント制御方法（イベント制御装置）においては、イベント処理を実行するに際して、当該イベントに即時送信イベントが含まれる場合に再走査フラグを立てることで、予め設定されたシミュレーション時刻（単位時間）内でイベント処理を繰り返して実行する処理を行う。
これを実現するため、イベント制御装置では、前記イベントの種類を判別し前記イベントにおける即時送信イベントの有無を判断してイベント処理を実行するイベント処理部と、イベント処理の再走査の有無を管理する次回再走査ノードリストと、イベント処理を実行するノードのリストを管理する現再走査ノードリストとを有している。
次回再走査ノードリストは、イベントが即時送信イベントを含む時に相手ノードを次回再走査ノードリスト(ＲＮＬnext)に追加することでイベント処理の再走査の有無を管理するものである。
現再走査ノードリストは、イベント処理を実行するノードを現再走査ノードリスト(ＲＮＬnow)で管理するとともに、リスト上のノードに関して１回分の再走査を行うため前記次回再走査ノードリストのリストのデータを移動するものである。
【００３４】
次に、シミュレーション実行管理部３１及びノード実行部３４の動作について、図４のフローチャート図を参照して説明する。
本シミュレーション装置は、シミュレーション処理時間(SUT)ごとに、各ノードがイベント駆動型で独立に処理を実行する。イベントキューは、シミュレーション実行中に、SUT毎に、動的に更新される。
【００３５】
シミュレーション装置起動時に、各ノードのシミュレーション初期条件を設定し、現在実行中のシミュレーション時刻Ｔnowを「０」とする（ステップ１０１）。初期条件としては、ノード数、各ノードで動作するプロトコル、あるノードに指定時刻に発生するイベントなどがある。
初期状態として、次回再走査ノードリスト(ＲＮＬnext)を空に設定し（ステップ１０２）、実行中ノード(Ｎnow)を「１」に設定する（ステップ１０３）。イベント処理として、そのノードのイベントキューに含まれるイベントを実行する（ステップ１０４）。
【００３６】
イベント処理での手順については後述する（図５）。
【００３７】
次に、Ｎnowを「１」増加させ（ステップ１０５）、Ｎnowが「ｎ」以下であればステップ１０４に戻ってイベント処理から繰り返す（ステップ１０６）。Ｎnowが「ｎ」より大きい場合、ループを抜ける。
【００３８】
ステップ１０４のイベント処理において、イベントに即時送信イベントが含まれる場合（0 SUTで送受信されるメッセージがあった場合）、同一SUT内で複数回同一ノードの処理が行われる。すなわち、再走査フラグを立てることで、予め設定されたシミュレーション時間（単位時間）内でイベント処理を繰り返して実行する処理を行う。
すなわち、再走査ノードリスト（ＲＮＬnext）が空かどうかを判断し（ステップ１０７）、ＲＮＬnextが空でなければ、再走査の動作を実行する。再走査では、先ず、リスト上のノードに関して１回分の再走査を行うため現再走査ノードリストＲＮＬnowにＲＮＬnext の値を設定し（ＲＮＬnextのデータを移動する）、ＲＮＬnextを空とする（ステップ１０８）。
【００３９】
次に、ＲＮＬnowより順にノードを抽出し（ステップ１０９）、抽出したノードのイベント処理を実行する（ステップ１１０）。抽出したノードは、ＲＮＬnowから削除され（ステップ１０９）、ノードＲＮＬnowが空となるまで繰り返し実行する（ステップ１１１）。
その後、ＲＮＬnextが空かどうかを再度確認し（ステップ１０７）、空でなければ再び再走査の処理を実行する。ＲＮＬnext が空であれば、Ｔnowを「１」増加させ（ステップ１１２）、Ｔnowが予め設定されたシミュレーション時間Ｔmaxより小さい場合には、最初のノードからのイベント処理に戻る（ステップ１１３）。Ｔnow≧Ｔmaxの場合には、シミュレーション終了条件が成立したとしてシミュレーション結果を出力し（ステップ１１４）、シミュレーションを終了する。
【００４０】
図４のステップ１０４におけるノード、シミュレーション単位時間毎に実行されるイベント処理について、図５のフローチャート図を参照して説明する。
実行中ノードのイベントキューより、時刻Ｔnowで実行すべきイベントのリスト(Ｅ1〜Ｅm)を抽出する（ステップ２０１）。
イベント処理される先頭のリストについて、「１」（ｋ＝１）に設定し（ステップ２０２）、イベントＥkを実行する（ステップ２０３）。
「ｋ」を「１」増加し（ステップ２０４）、「ｋ」が「ｍ」以下になるまで、これらのイベントを順に繰り返し実行する。全イベントの処理を終了後（ステップ２０５）、イベント処理を終了する。
【００４１】
図５のステップ２０３におけるイベントＥkを実行する際の動作について、図６のフローチャート図を参照して説明する。
先ず、処理するイベントについて、送信イベント、受信イベント、内部イベントであるかのイベントタイプによる分岐を行う（ステップ３０１）。
【００４２】
送信イベントの場合、ノード内部状態の更新を行い（ステップ３０２）、相手ノードのイベントキューに受信イベントとして追加する（ステップ３０３）。
この際、相手ノードにとっては、a SUT時間後にそのイベントが発生するようにイベントの追加が行われる（ステップ３０３）が、このうち「a＝０」のものがあるかどうか（即時イベントの有無）を判断する（ステップ３０３）。即時送信イベントが存在する場合は、本イベントを実行する際に、同じシミュレーション時刻において相手ノードでの受信イベントを実行できるように、ＲＮＬnextに相手ノードを追加することで再走査フラグを立てる（ステップ３０５）。
【００４３】
受信イベントの場合、ノード内部状態の更新を行った後（ステップ３１２）、応答となる送信イベントが有るか否かを判断し（ステップ３１３）、応答となる送信イベントが有る場合には、本送信イベントに伴うノード内部状態の更新を行い（ステップ３１４）、送信イベントと同様のステップ３０３以降の処理を行う。
内部イベントの場合は、ノード内部状態の更新のみを行う（ステップ３２２）。
【００４４】
上述のイベント制御方法を実現する場合、対象とするプロトコルが扱う送信イベントが、即時送信イベント、経過送信イベントのいずれであるかを定義する必要がある。どのイベントを即時イベントとして定義するかはシミュレーションの実行環境により異なる。例えば以下のような例が考えられる。
（１）固定網・移動網を含むネットワークを用いて、シミュレーションを行う場合、メッセージが到着するまでの遅延が小さい固定網上でのメッセージ転送に関するイベントは、全て即時送信イベントとする。
（２）メッセージ交換粒度の異なる複数のプロトコルを扱う場合、交換粒度の細かいプロトコルについては、全て即時送信イベントとする。
（３）あるプロトコルにおいて、サイズが大きいデータメッセージと、サイズが小さい制御メッセージを扱う場合、サイズが小さい制御メッセージについては、即時送信イベントとする。
【００４５】
次に、上述したイベント制御方法を使用したシミュレーション計算時間の短縮効果について考察する。
１シミュレーション時刻(SUT)において、１ノードを処理するのに要する時間をtdとし、ノード数をｎ、シミュレーション時間をＴmax SUTとした場合、従前のイベント処理の方法による計算時間Ｔexは、
Ｔex ＝ｎ×Ｔmax × td
となる。
【００４６】
これに対して上述したイベント制御方法によれば、ｘ倍のシミュレーション単位時間を適用できるため、シミュレーション時間は、Ｔmax／ｘ SUTとなる。繰り返し再走査も含め、再走査に要する延べノード数の平均をnrとした場合、
Ｔex ＝（ｎ＋ｎr）×Ｔmax ／（Ｘ × td）
となる。
したがって、上述したイベント制御方法によれば、従前のイベント処理方法に対して、（ｎ＋ｎr）／ｎ／Ｘの計算時間で処理できることとなる。
【００４７】
なお、この式からは、ｎrが極端に大きい場合には、従前の方法よりも計算時間がかかることになるが、ｎrが極端に大きくなる場合は、従前の方法においても精度が保証されないので、このような場合を想定する必要はない。
【００４８】
上述のネットワークシミュレーション装置によれば、同一シミュレーション時間で処理する送信イベントの有無を予め判断することにより、細かい粒度を必要とするプロトコル動作のみを同一シミュレーション時間において繰り返してイベント処理（再走査）できることを可能とする。これにより、シミュレーション単位時間を長く設定しても、計算時間が早くなる上、精度を失うことなくシミュレーションを実行できる。
【００４９】
シミュレーション単位時間を長く設定した場合、同一シミュレーション時間で処理するイベント(即時送信イベント)に対する計算時間は、従来のネットワークシミュレーション装置と同様である。同一シミュレーション時間で処理しないイベント（経過送信イベント）の処理において、イベント駆動有無の確認などの無駄な時間を省けるため、処理時間を短縮することができる。従って、最も多く発生し得るノード内部状態の更新頻度に合わせて、シミュレーション単位時間を設定するのが効果的である。
【００５０】
次に、ノード内部状態の更新頻度が異なる例について説明する。
ネットワーク構成の例としては、２ノードが１Gbit/sの高速な固定リンクに接続され、残りのノードがいずれかのノードに低速な無線リンク(例えば１Mbit/s)で接続されている例である。この場合、シミュレーション単位時間を、１Mbit/sのリンク上で１パケット(1500バイト)を送信するのに要する時間(12msec)と設定しても、この時間内に、固定リンク上の２ノード間で繰り返しやりとりされるメッセージに関するイベントを処理することができる。
【００５１】
プロトコルの例としては、TCP(Transmission Control Protocol)とBGP(Border Gateway Protocol)の振舞いをシミュレーションする場合が考えられる。TCPについてはデータパケットの送信処理や、RTTに基づく再送、輻輳制御などの計算処理などを行うため、１msecあるいはそれよりも細かい単位で処理する必要がある。
一方、BGPでのメッセージ送受信処理は、BGPに関する内部状態の更新頻度が粗いため、１秒程度で十分である。BGPの振舞いのシミュレーションを主目的としながら、TCPの振舞いも扱う場合には本発明の利用が効果的である。
【００５２】
上述した例では、イベント処理を実行するイベント制御方法をネットワークシミュレーション装置に用いたが、同様の構成を持つシステムに適用可能である。すなわち、複数のサブシステムを有し、サブシステム間で異なる頻度でやりとりされるメッセージが存在し、各サブシステムがイベント駆動型で設計されたシステムに関して適用することができる。
【符号の説明】
【００５３】
１…ネットワーク、 １０…ブランチクラスタ、 １１…ネットワーク中継機器(ルータ)、 １２…サーバ、 ２０…リーフクラスタ、 ２１…ピア、 ３０…ネットワークシミュレーション装置、 ３１…シミュレーション実行管理部、 ３２…設定管理部、 ３３…ネットワーク状態管理部、 ３４…ノード実行部、 ３５…ログ管理部、 ３６…シミュレーション結果表示部、 ４０…ユーザ。
【特許請求の範囲】
【請求項１】
互いに独立して動作する複数のサブシステム内で発生する送受信に関する各イベントを処理するに際して、細かい粒度で処理すべきイベントと、粗い粒度で処理可能なイベントが混在している場合のイベント処理を行うイベント制御方法において、
前記各イベントのイベント処理を実行するに際して、前記イベントにおける即時送信イベントの有無を判断し、
前記イベントに即時送信イベントが含まれる場合に再走査フラグを立てることで、予め設定された単位時間内でイベント処理を繰り返して実行する
ことを特徴とするイベント制御方法。
【請求項２】
互いに独立して動作する複数のサブシステム内の各ノードで発生する各イベントを処理するに際して、細かい粒度で処理すべきイベントと、粗い粒度で処理すべきイベントが混在している場合のイベント処理を行う装置において、
前記イベントの種類を判別し前記イベントにおける即時送信イベントの有無を判断してイベント処理を実行するイベント処理部と、
前記イベントが即時送信イベントを含む時に相手ノードをリストに追加することでイベント処理の再走査の有無を管理する次回再走査ノードリストと、
イベント処理を実行するノードのリストを管理するとともに、リスト上のノードに関して１回分の再走査を行うため前記次回再走査ノードリストのリストのデータを移動した現再走査ノードリストと、
を備えたことを特徴とするイベント制御装置。
【請求項３】
互いに独立して動作する複数のノードが接続されたネットワークに対して、
請求項１のイベント制御方法を利用して各ノードのイベント処理についてのシミュレーションを行うことを特徴とするネットワークシミュレーション方法。
【請求項１】
互いに独立して動作する複数のサブシステム内で発生する送受信に関する各イベントを処理するに際して、細かい粒度で処理すべきイベントと、粗い粒度で処理可能なイベントが混在している場合のイベント処理を行うイベント制御方法において、
前記各イベントのイベント処理を実行するに際して、前記イベントにおける即時送信イベントの有無を判断し、
前記イベントに即時送信イベントが含まれる場合に再走査フラグを立てることで、予め設定された単位時間内でイベント処理を繰り返して実行する
ことを特徴とするイベント制御方法。
【請求項２】
互いに独立して動作する複数のサブシステム内の各ノードで発生する各イベントを処理するに際して、細かい粒度で処理すべきイベントと、粗い粒度で処理すべきイベントが混在している場合のイベント処理を行う装置において、
前記イベントの種類を判別し前記イベントにおける即時送信イベントの有無を判断してイベント処理を実行するイベント処理部と、
前記イベントが即時送信イベントを含む時に相手ノードをリストに追加することでイベント処理の再走査の有無を管理する次回再走査ノードリストと、
イベント処理を実行するノードのリストを管理するとともに、リスト上のノードに関して１回分の再走査を行うため前記次回再走査ノードリストのリストのデータを移動した現再走査ノードリストと、
を備えたことを特徴とするイベント制御装置。
【請求項３】
互いに独立して動作する複数のノードが接続されたネットワークに対して、
請求項１のイベント制御方法を利用して各ノードのイベント処理についてのシミュレーションを行うことを特徴とするネットワークシミュレーション方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１０−２３３０２１（Ｐ２０１０−２３３０２１Ａ）
【公開日】平成２２年１０月１４日（２０１０．１０．１４）
【国際特許分類】
【出願番号】特願２００９−７９２４６（Ｐ２００９−７９２４６）
【出願日】平成２１年３月２７日（２００９．３．２７）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２２年１０月１４日（２０１０．１０．１４）
【国際特許分類】
【出願日】平成２１年３月２７日（２００９．３．２７）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]