ネットワークシミュレーション装置
【課題】Ｐ２Ｐ中継型の配信システムで構築されるネットワークにおけるトラヒック量等の評価に適したネットワークシミュレーション装置を得る。
【解決手段】複数のノードが接続された複数のクラスタを有するネットワークにおいて、前記複数のクラスタについて、中継を行うブランチクラスタ１０と一つのブランチクラスタのみに接続されるリーフクラスタ２０とに分割し、前記ブランチクラスタ同士及び前記ブランチクラスタと前記リーフクラスタとの間のクラスタ間リンクをノード間の通信でシェアし、前記リーフクラスタ内におけるノード（ピア２１）同士のノード間リンクをノード毎に帯域を占有し、前記各ノードは、ノード間リンクとクラスタ間リンクのキューを併せ持ち、前記クラスタ内のノードが送信したデータのみをノード間リンク及びクラスタ間リンクのキューにて順番待ちを考慮して出力する扱いにより上り回線に限定して遅延時間を計算する。
【解決手段】複数のノードが接続された複数のクラスタを有するネットワークにおいて、前記複数のクラスタについて、中継を行うブランチクラスタ１０と一つのブランチクラスタのみに接続されるリーフクラスタ２０とに分割し、前記ブランチクラスタ同士及び前記ブランチクラスタと前記リーフクラスタとの間のクラスタ間リンクをノード間の通信でシェアし、前記リーフクラスタ内におけるノード（ピア２１）同士のノード間リンクをノード毎に帯域を占有し、前記各ノードは、ノード間リンクとクラスタ間リンクのキューを併せ持ち、前記クラスタ内のノードが送信したデータのみをノード間リンク及びクラスタ間リンクのキューにて順番待ちを考慮して出力する扱いにより上り回線に限定して遅延時間を計算する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの配信システムにおけるトラヒック量やスループット等についての評価を行うためのネットワークシミュレーション装置に関する。
【背景技術】
【０００２】
ネットワークシミュレーション装置は、実際にシステムを導入する前に、計画されたネットワークトポロジや使用するデバイスからトポロジ情報とトラヒック情報をもとにモデル化し、トラヒック量やスループット等についての大まかな推定を行うものであり、シミュレーション用に開発された種々のソフトをネットワーク上で実行することで行われる。
【０００３】
例えば、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などのインターネットプロトコルの動作を試験するためのネットワークシミュレーション装置であり、端末におけるパケット送受信や、ルータにおけるキューイング処理などを細かくシミュレーションできる。
【０００７】
しかしながら、BitTorrentなどのように、個々の端末が自律分散的に動作するプロトコルを定義できないという課題があった。また、扱うべき端末やルータの規模が多い場合、計算量が多くなるので、標準的なサーバ用PCを用いた場合、例えばルータ数が1,000程度までしか扱うことができないという課題があった。
【０００８】
前述のArtisocや、N3 Simulatorは、自律分散的に動作するエンド端末をシミュレーションすることに適したシミュレータであり、インターネットプロトコルに限らず、エンド端末上のプロトコルや、エンド端末上のイベント発生タイミングを独自に定義できることができる。
【０００９】
しかしながら、端末の動作に特化しているため、ネットワーク上のリンクやルータなどの振舞いまでをシミュレーションできないという課題があった。
【００１０】
本発明は上記事情に鑑みて提案されたもので、Ｐ２Ｐ中継型の配信システムで構築されるネットワークにおけるノード（端末、ルータ、サーバ等の総称）間のトラヒック量やスループットの評価に適したネットワークシミュレーション装置を提供することを目的としている。
【課題を解決するための手段】
【００１１】
上記目的を達成するため本発明は、ネットワークを定義する際、中継ネットワークとアクセスネットワークの役割を分け、Ｐ２Ｐ中継型の配信システムのシミュレーションにおいて重要となるアクセスネットワークに関してのみ、リンクのキューなどのネットワーク的な振舞いを忠実に再現する機能を持たせることにより、少ない計算量で大規模にネットワークと端末の双方をシミュレーションすることを可能としたものである。
【００１２】
すなわち、請求項１のネットワークシミュレーション装置は、複数のノードがそれぞれ接続された複数のクラスタ（小ネットワーク）を有するネットワークにおいて、前記複数のクラスタについて、中継を行うブランチクラスタと一つのブランチクラスタのみに接続されるリーフクラスタとに分割し、前記ブランチクラスタ同士及び前記ブランチクラスタと前記リーフクラスタとの間のクラスタ間リンクをノード間の通信でシェアし、前記リーフクラスタ内におけるノード同士のノード間リンクをノード毎に帯域を占有している。
そして、前記各ノードは、ノード間リンクとクラスタ間リンクのキューを併せ持ち、前記クラスタ内のノードが送信したデータのみをノード間リンク及びクラスタ間リンクのキューにて順番待ちを考慮して出力する扱いにより上り回線に限定して前記クラスタ単位で遅延時間を計算することでトラヒック量またはスループット（＝単位時間当たりのトラヒック量）の評価を行うことを特徴としている。
すなわち、クラスタを単位として管理されるネットワーク情報（ネットワーク構成情報、経路管理情報、キュー管理情報）に従い、ノード間で送受信されるメッセージの遅延時間を計算することで、クラスタ間毎のトラヒック量またはスループット（＝単位時間当たりのトラヒック量）の評価を行うものである。
【００１３】
請求項２のネットワークシミュレーション装置は、請求項１において、ビットトレント（BitTorrent）プロトコルを対象とし、前記クラスタ内の各ノードは、自律分散的に動作するトラッカーやピアであることを特徴としている。
【発明の効果】
【００１４】
本発明によれば、Ｐ２Ｐ中継型コンテンツ配信のネットワークシミュレーションを実現するにあたり、複数のノードが接続された複数のクラスタについて、中継を行うブランチクラスタと一つのブランチクラスタのみに接続されるリーフクラスタとに分割し、クラスタ内のノードが送信したデータのみをノード間リンク及びクラスタ間リンクのキューにて順番待ちを考慮して出力するよう扱うことにより、ネットワークとして忠実に再現する部分をアクセスネットワークの上り回線に限定している。これにより、従来のネットワークシミュレーション装置に比べて少ない計算量でＰ２Ｐ中継型コンテンツ配信のシミュレーションが実現できる。
【００１５】
従来のネットワークシミュレーション装置では、計算量の観点から、標準的なサーバ用PCを用いて、ネットワークのシミュレーションと、自律分散システムのシミュレーションを同時に行うことが難しいという問題があったが、本発明のネットワークシミュレーション装置によれば、中継を行うブランチクラスタと一つのブランチクラスタのみに接続されるリーフクラスタとに分割し、各クラスタに対して設定したネットワーク情報（ネットワーク構成情報、経路管理情報、キュー管理情報）に従い、ノード間で送受信されるメッセージの遅延時間を推定できるようにしたので、標準的なサーバ用PCを用いた場合でも、上述した両方の機能を持ち合わせることができる。
【図面の簡単な説明】
【００１６】
【図１】本発明のネットワークシミュレーション装置の構成を説明するための機能ブロック図である。
【図２】本発明のネットワークシミュレーション装置が適用されるネットワークトポロジの模式図である。
【図３】（ａ）及び（ｂ）は本発明のネットワークシミュレーション装置におけるリンクの概念を示す模式図である。
【図４】（ａ）〜（ｃ）は本発明のネットワークシミュレーション装置における遅延の定義を説明するための模式図である。
【図５】（ａ）〜（ｂ）は本発明のネットワークシミュレーション装置における遅延発生を説明するための模式図である。
【図６】本発明のネットワークシミュレーション装置における動作を説明するためのフローチャート図である。
【図７】（ａ）〜（ｅ）は本発明のネットワークシミュレーション装置で扱うメッセージ例を示す模式図である。
【図８】Ｐ２Ｐ中継型配信システムを実現するためのプロトコルとして利用されているBitTorrentプロトコルについての概要を説明するフロー図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態の一例について、図１及び図２を参照しながら説明する。
本発明のシミュレーション装置３０は、多数のノード（端末、ルータ、サーバ等の総称）が接続されて構成されるＰ２Ｐ中継システムを構築するネットワークについて、各ノード間のトラヒック量やスループット、ダウンロード時間の算出を目的としたシミュレーションを行うものであり、図１に示すように、ネットワーク内においてシミュレーションを行うユーザ４０に対して接続可能に構成されている。
【００１８】
ネットワークシミュレーション装置３０は、ユーザ４０からの要求により後述するシミュレーション動作フローにしたがってシミュレーションの実行を行うシミュレーション実行管理部３１と、シミュレーションの設定情報を管理する設定管理部３２と、ネットワークの状態を管理するネットワーク状態管理部３３と、各ノードにおけるイベントの実行をそれぞれ行う複数のノード実行部３４と、各ノード実行部３４でのイベントの実行結果を記録するログ管理部３５と、ユーザ４０からの要求に基づきログ管理部３５を参照してシミュレーション結果を表示するシミュレーション結果表示部３６とを備えて構成されている。
【００１９】
ネットワーク状態管理部３３は、ネットワークシミュレーション装置３０がシミュレーションするネットワーク構成を管理するとともに、ネットワークにおけるクラスタ間の経路管理(SPFで導出されるクラスタ間の経路についての管理)、及び、後述するクラスタ間リンク及びノードリンクの出力キューについてのキュー管理を行う。ネットワークシミュレーション装置３０がシミュレーションするネットワークトポロジは、図２に示すように、いくつかの小さなネットワークであるクラスタに分割される。
各クラスタは、他の地域との接続やISPとの中継を行う部分であるブランチクラスタ１０と、ユーザ（Ｐ２Ｐ中継システムではピアと呼ぶ）が属するアクセスネットワークよりの部分であるリーフクラスタ２０に分かれ、それぞれが相互に接続されている。
【００２０】
ブランチクラスタ１０には、相互に接続された複数のネットワーク中継機器(ルータ等)１１を有している。また、ブランチクラスタ１０によっては、Ｐ２Ｐ中継システムの一部を担うサーバ１２｛コンテンツサーバ、配信制御サーバ（トラッカー）等｝が設定されている。
【００２１】
リーフクラスタ２０は、アクセスネットワークを集約する機器を含んで構成され、機器の配下に複数のピア２１が設定されている。ブランチクラスタ１０は制限なく互いに接続できるが、リーフクラスタ２０はいずれか１つのブランチクラスタ１０のみと接続するようになっている。
【００２２】
ネットワークシミュレーション装置によるネットワークのシミュレーションは、以下のように単純化させて定義する。経路計算は、ブランチクラスタ１０又はリーフクラスタ２０毎のクラスタ単位で行われる。すなわち、クラスタ間に論理的なリンクが存在すると仮定し、リンク毎にコストや伝搬遅延を管理することが行われる。
【００２３】
あるクラスタから別のクラスタへの経路は、OSPFで用いられているSPFアルゴリズムと同様の方法で計算する。従って、クラスタ内のノードが別のクラスタのノードと通信する場合には、上記手段により、リンク毎に計算された経路を用いて通信を行う。
【００２４】
リンクのタイプとしては、図３に示すように、クラスタ間を接続するリンクとして論理的に存在するクラスタ間リンク（ブランチクラスタ１０同士間のリンク１５、及び、ブランチクラスタ１０とリーフクラスタ２０間のリンク１６）と、リーフクラスタ２０内に存在するノード毎に存在しノードとネットワークを接続するノードリンク２２とが存在する。したがって、一つのブランチクラスタ１０に属するノードと、他のブランチクラスタ１０に属するノードとの間の通信は、１つのクラスタ間リンク１５でシェアされる。また、リーフクラスタ２０に属するノードと、ブランチクラスタ２０に属するノードの接続の場合、ノード単位で帯域がシェアされるノードリンク２２と、クラスタ間リンク（ブランチクラスタ１０とリーフクラスタ２０間のリンク１６）の二つを経由して、ノード間の通信が行われる。
【００２５】
設定管理部３２は、ネットワークをシミュレーションする場合のシミュレーション設定情報を管理する。クラスタ（ノード）とクラスタ（ノード）との間のトラヒック量は、シミュレーション実行時に計算し、ログ管理部３５にて蓄積する。これにより、ユーザ４０は、シミュレーション実行後に、特定のクラスタ（ノード）間のトラヒック量を入手することができる。
また、シミュレーション設定情報の初期設定情報は、ユーザ４０がシミュレーション実行前に設定するものであり、ネットワーク構成（ブランチクラスタ１０又はリーフクラスタ２０）、リンクの接続構成（クラスタ間リンク（リンク１５及びリンク１６）又はノードリンク２２）、各クラスタ上のノード数・種類（ピア又はトラッカー）、ノードの起動タイミングなどの情報を含む。
【００２６】
ノード実行部３４は、ピアまたはトラッカーのいずれかのアルゴリズムに従い、イベント管理において管理しているイベントについて、１つのノードの動作を実行する。本発明のネットワークシミュレーション装置では、１０，０００以上の独立なノードのシミュレーションを行うことを想定しているため、独立なノード数だけノード実行部３４が存在する。各ノード実行部３４は、シミュレーション処理時間(SUT)を単位に１回、シミュレーション実行管理部３１よりノードＩＤ順に呼び出され、イベント管理において管理しているイベントのうち、そのシミュレーション処理時間(SUT)で実行すべきイベントを実行する。ノードは、ピアあるいはトラッカーのいずれかのアルゴリズムを持ち、それぞれのアルゴリズムに従ってイベントの実行を行う。イベントの実行結果は、時系列順に記録され、ログ管理部３５に蓄積される。
【００２７】
ログ管理部３５は、イベント毎に、処理に必要なイベント実行時刻，ノード，相手先ノード，イベント種別の情報が記憶されることで、トラヒック量等のシミュレーション結果を求めることができる。
【００２８】
ノード実行部３４でのイベント処理について説明する。
受信イベント処理は、メッセージの受信に伴うノード状態の更新を行う。ログ管理部３５に、受信イベント処理を行ったことを通知する。さらに、ピア／トラッカーアルゴリズムに従い、他の相手先ノード（複数もありうる)へメッセージを送信する必要がある場合には、送信イベント(複数もありうる)を設定し、送信イベント処理を行う。メッセージの送信に伴うノード状態の更新を行い、ログ管理部３５に送信イベント処理を行ったことを通知する。また、ネットワーク状態管理部３３に該当ノードから相手先ノードへの遅延の計算を依頼し、その結果、相手ノードに、現シミュレーション処理時間(SUT)に遅延時間を加えた時刻をイベント受信時刻として、本メッセージに関する受信イベントを設定する。
【００２９】
シミュレーション結果表示部３６は、ユーザ４０からの要求に基づきログ管理部３５を参照してシミュレーション結果としてのトラヒック量やスループットの表示を行う。
このトラヒック量は、メッセージの長さの合計で計算される。計算するタイミングとしては、例えば、ノードが送信イベントとしてメッセージを送信したときに行う。メッセージの長さは、シミュレーション初期設定により変えることも可能であるが、メッセージタイプ毎に固定長であり、例えばピースメッセージであれば２５６キロバイト等に設定する。基本的には、BitTorrentプロトコルに従って、メッセージの長さが決められる。
スループットは、時間当たりのトラヒック量であり、メッセージの長さの合計をシミュレーション対象時間の合計で割ることにより計算される。
【００３０】
次に、シミュレーション結果の具体例について説明する。
１単位のシミュレーション処理時間(SUT)を１００ミリ秒とし、シミュレーション全体で１０，０００SUTを消費したとすれば、１，０００秒間のシミュレーションを行ったことになります。この間で、クラスタＡ−Ｂ間のメッセージの長さの合計が２，０００ＭＢ(メガバイト)だったとすれば、クラスタＡ−Ｂ間のトラヒック量は２，０００ＭＢ、クラスタＡ−Ｂ間のスループットは、（２，０００／１，０００）×８＝１６Ｍｂｉｔ／秒となる。
【００３１】
次に、ネットワークシミュレーション装置のシミュレーションにおいて、ノード間のデータの通信で発生する３種類の遅延（伝搬遅延・伝送遅延・キューイング遅延）の定義について、図４を参照して説明する。なお、ネットワークシミュレーション装置で扱うデータの単位はメッセージと呼ばれる。
メッセージは、IPのプロトコルとしては、１〜複数のIPパケットに相当するが、ネットワークシミュレーション装置ではIP、TCP、UDPといったプロトコルを厳密に処理することは想定しておらず、アプリケーションレベルでの情報をメッセージという単位で表している。メッセージには、プロトコル制御情報の伝達を目的とする制御メッセージと、コンテンツなどのアプリケーションデータの転送を目的とするデータメッセージが存在する。本発明のネットワークシミュレーション装置では、制御メッセージのメッセージサイズは０であるとみなしている。
【００３２】
伝搬遅延は、図４（ａ）に示すように、クラスタ間リンクにおいて、メッセージが物理的に到着するのに要する遅延である。電気信号の伝達と関係し、ブランチクラスタ間の物理的な距離に比例して発生する遅延である。
伝送遅延は、図４（ｂ）に示すように、メッセージを、有限の帯域を持つリンクに送信開始し、送信完了するまでに要する遅延を表す。リンクの帯域が小さく、メッセージサイズが大きいほど、伝送遅延は大きくなる。
キューイング遅延は、図４（ｃ）に示すように、複数のメッセージ転送をシェアするリンクにおいて、メッセージの転送要求が発生してから該当するメッセージの転送処理を開始できるまでに要する時間である。メッセージを即座に転送出来ない場合は、メッセージは出力キューに蓄積される。この遅延は該当するメッセージのサイズには比例せず、出力キューのサイズが大きくリンクの帯域が小さいほど大きくなる。
【００３３】
次に、図５を参照して、上記の遅延を用いた遅延発生モデルについて述べる。
図５（ａ）に示すように、ブランチクラスタ１０内のノードが送信したメッセージについては、ブランチクラスタ毎に持つ出力キューのキューイング遅延、クラスタ間リンク１５での伝送遅延および伝搬遅延が発生する。
図５（ｂ）に示すように、リーフクラスタ２０内のノードが送信したメッセージについては、ノードリンク２２でのキューイング遅延および伝送遅延と、クラスタ間リンク１６でのキューイング遅延、伝送遅延および伝搬遅延が発生する。
図５（ｃ）に示すような複数のブランチクラスタ１０を経由するメッセージについては、各ブランチクラスタを経由する毎に、経由するブランチクラスタ１０での伝送遅延および伝搬遅延が発生する。
【００３４】
また、図５で示した遅延発生モデルに関して、モデルを単純化し計算量を減らすため、以下の条件を適用する。
（１）中継するクラスタ間リンクや、下りノードリンクでのキューイング遅延は発生しない。
（２）出力キューのサイズは無限大と考え、キューあふれによるパケットロスは発生しない。
（３）中継機器やリンクでのデータ転送誤り(ビットエラー)は発生しない。
（４）従って、ネットワーク上のパケットロスは一切発生せず、TCPでの再送による遅延なども考慮しない。
（５）ブランチクラスタ内のノードが、クラスタ間リンクが存在するルータへメッセージを転送するまでの遅延は考慮しない。
【００３５】
遅延の計算式は、クラスタ経路をＸ1・Ｘ2 … Ｘnとした場合、クラスタＸ1に属するノードａと、クラスタＸnに属するノードｂとのエンドエンドによる遅延時間Ｄe2e（秒）で表示することができる。そして、遅延時間Ｄe2eは、クラスタ間リンクの伝搬遅延（秒）であるＤp、クラスタ間リンクの伝送遅延（秒）であるＤt、クラスタ間リンクのキューイング遅延（秒）であるＤqの関数で表示することができる。
すなわち、Ｄp（ＸＹ）をクラスタＸ−Ｙ間のクラスタ間リンクの伝搬遅延（秒）、Ｂ（ＸＹ）をクラスタＸ−Ｙ間のクラスタ間リンクのＸ−Ｙ方向の帯域（bps）、Ｍをメッセージ長さ（byte）、Ｑt-1（ＸＹ）をクラスタＸ−Ｙ間のクラスタ間リンクの時刻t-1における出力キュー長（byte）とすると、クラスタ間リンク１５，１６における伝搬遅延Ｄp、伝送遅延Ｄt、キューイング遅延Ｄqは、それぞれ表１のように定義される。また、遅延時間Ｄe2eは、クラスタＸがブランチクラスタの場合、数１で計算される。
【００３６】
【表１】
【００３７】
【数１】
【００３８】
また、Ｂ（a）をクラスタＸ内でのノードａのノードリンクの上り方向の帯域（bps）、Ｑt-1（ａ）をクラスタＸ内でのノードａのノードリンクの上り方向の時刻t-1における出力キュー長（byte）とすると、ノードリンク２２における伝搬遅延Ｄp、伝送遅延Ｄt、キューイング遅延Ｄqは、それぞれ表２のように定義される。また、遅延時間Ｄe2eは、クラスタＸがリーフクラスタの場合、遅延時間Ｄe2e（秒）は数２で計算される。
【００３９】
【表２】
【００４０】
【数２】
【００４１】
次に、シミュレーション実行管理部３１の動作について、図６を参照して説明する。
本シミュレーション装置は、シミュレーション処理時間(SUT)ごとに、各ノードがイベント駆動型で独立に処理を実行する。シミュレーション装置起動時には、予め設定された項目に従い、各ノードの初期状態を設定し、SUTを初期状態の「０」とする（ステップＳ１０１）。SUT毎に、各ノードにおける受信イベントを処理し（ステップＳ１０２）、その後、送信イベントを処理する（ステップＳ１０３）。
0 SUTで送受信されるメッセージがあった場合、同一SUT内で複数回同一ノードの処理を行う必要がある。このため、再走査フラグを設け、再走査ありの場合（ステップＳ１０４）には、SUTを増加させる繰り返し各ノードの処理を実行する。
再走査無しとなったとき、SUTを増加させ（ステップＳ１０５）、次のSUTでの処理を実行する。シミュレーション終了条件が成立した場合（ステップＳ１０６）、結果出力を行い（ステップＳ１０７）、シミュレーションを終了する。
【００４２】
シミュレーション装置で扱われるイベントについて説明する。
ノード毎のイベントは、発生時刻、相手先、イベント種別、パラメータとともに、イベントキューに保持される。発生時刻は、シミュレーション起動開始からの経過SUTで表す。相手先は、イベントを送受信する相手のノードを識別する番号である。イベント種別は、メッセージのタイプ等である。パラメータは、イベントに付随するパラメータである。ノード間で転送されるメッセージは、送信・受信ノードにおいて、送信・受信イベントとしてそれぞれ処理される。
【００４３】
Ｐ２Ｐ中継型コンテンツ配信のプロトコルを実現するにあたり、ネットワークシミュレーション装置が対象とするメッセージの例について図７に示す。
図７（ａ）は、ノード間（Ｎ１とＮ２）で時間的な遅延なしにメッセージ転送が行われる場合である。
図７（ｂ）は、ノード間（Ｎ１とＮ２）でのメッセージ転送に、ａ時間のSUT時間の遅延が発生する例である。
図７（ｃ）は、ノード間（Ｎ１とＮ２）でのメッセージ転送において、受信メッセージに対する応答として、送信メッセージが発生する例である。システム内の処理遅延は無いものと仮定している。
図７（ｄ）は、ノード（Ｎ１）から複数のメッセージを同時刻に複数のノード（Ｎ２、Ｎ３）に対して送信する例である。
図７（ｅ）は、ノード間（Ｎ１とＮ２）の0 SUT内で、複数のメッセージがやりとりされる例である。
【００４４】
次に、Ｐ２Ｐ中継型配信システムを実現するためのプロトコルとして、広く利用されているビットトレント（BitTorrent）プロトコルについての概要について、図８を参照しながら説明する。
BitTorrentでは、１つのファイルを複数の固定長のピース（Piece）に分割し、Pieceメッセージを１つの単位として、複数のピアから独立に、自身が持っていないピースを受信する。各ピアは、転送可(Unchoke)にするピア、ピースをダウンロードする順番などに関して、ピア毎の自律的な判断で実施する。
【００４５】
BitTorrentは、配信制御を行うトラッカー(Tracker)と、コンテンツのダウンロード／アップロードを行うピア(Peer)の２種類のノードで構成される。ダウンロードを行うピア＃１(peer #1)は、まずトラッカーに対し、コンテンツを要求し（ステップ２０１）、トラッカーは、コンテンツのダウンロードが可能なピアリストをピア＃１(peer #1)に返す（ステップ２０２）。
ピア＃１(peer #1)は、ピアリストで通知された各ピア(peer #2,peer #3)とのTCPの接続を行い（ステップ２０３，２０５，２０６、及び、ステップ２０４，２０７，２０８）、その後、BitTorrentレベルでの接続(Handshake)を行う（ステップ２０９，２１０、及び、ステップ２１１，２１２）。
【００４６】
以降、例えばピア＃２(peer #2)に対してのピースマップのやり取り(Bitfield) （ステップ２１３及びステップ２１４）、ピアへの興味の通知(Interested／Not interested)（ステップ２１５及びステップ２１６）と、ピアへの転送可否の通知(Unchoke／Choke)（ステップ２１７及びステップ２１８）を行う。その後、ピア＃１(peer #1)はピア＃２(peer #2)にピースを要求(Request)し（ステップ２１９）、応答としてピース(Piece)を受信する（ステップ２２０）。
【００４７】
次に、上述したビットトレント（BitTorrent）プロトコルをネットワークシミュレーション装置で実現する方法を以下に述べる。Pieceメッセージはデータメッセージとし、それ以外のメッセージは制御メッセージとして扱う。
メッセージ転送については、ネットワークシミュレーション装置において、メッセージタイプ毎の送受信イベントを設定することにより実現する。各ピアが行う自律的な判断については、BitTorrentが持つアルゴリズムと同じものをネットワークシミュレーション装置で持たせる。
【００４８】
すなわち、ピアアルゴリズムでは、相手先ピアとの接続状態(TCPコネクションの接続、choke／unchoke状態等)、相手先ピアが保有するピース(コンテンツの一部)、相手先ピアの性能を示す情報(ダウンロード時間)などを管理し、どの相手先ピアから、どのピースを入手するか、choke／unchoke状態の変更タイミングなどを決定する。
トラッカーアルゴリズムでは、あるコンテンツのダウンロード要求を行った全てのピアの情報を管理し、新しいピアからピアリスト要求を受けた際に、一定数のピアリストを返答する。
アルゴリズムとしては、流通度の低いピースを優先的にダウンロードするRarest first algorithmや、ダウンロード速度が速いピアを優先的にデータ転送可とするTit-for-tat algorithmなどが存在する。
【００４９】
シミュレーション実行条件の例を以下に示す。
ピア毎に、クラスタ、起動時刻、終了時刻を設定する。起動時刻はSUT時刻で設定し、終了時刻はダウンロード完了からn SUT時刻経過などといった設定を行う。多数のピアの統計多重的な振舞いをシミュレーションするため、複数のピアについて設定をグループ化することを可能とする。例えば、一定間隔で起動、ダウンロード完了からａを平均、ｂを分散とする正規分布に従う時間経過後に終了などといった、統計的な振舞いを考慮した設定を可能とする。
シミュレーション結果としては、ダウンロード時間、メッセージタイプごとのメッセージ数などを出力する。各SUTでのノード処理時に結果出力に必要な情報を記録し、シミュレーション後に一斉に収集することとする。
【００５０】
上述したネットワークシミュレーション装置によれば、シミュレーション処理時間(SUT)を単位として各ノードをイベント駆動型でシミュレーションする基本設計であるため、１単位のシミュレーション処理時間(SUT)の時間を変えることにより、シミュレーションの精度を変えられるという利点がある。
また、ノード数の増加に伴うソフトウェアの実装へのインパクトは少なく、高性能なハードウェアを導入すればシミュレーション時間を単純に減らすことができる。
更に、ノード単位で独立に処理できる部分が多いため、マルチCPU、マルチスレッド化への対応が容易である。
【００５１】
上述したネットワークシミュレーション装置は、中継ネットワークとアクセスネットワークの役割を分け、クラスタを単位として管理されるネットワーク情報（ネットワーク構成情報、経路管理情報、キュー管理情報）に従い、ノード間で送受信されるメッセージの遅延時間を計算することで、クラスタ間毎のトラヒック量またはスループット（＝単位時間当たりのトラヒック量）の評価を行うので、少ない計算量で大規模のネットワークのシミュレーションを可能とし、10,000〜10,000,000相当の規模のユーザを対象としたＰ２Ｐ中継型コンテンツ配信モデルを評価するのに適している。
【符号の説明】
【００５２】
１…ネットワーク、 １０…ブランチクラスタ、 １１…ネットワーク中継機器(ルータ)、 １２…サーバ、 １５…クラスタ間リンク、 １６…クラスタ間リンク、 ２０…リーフクラスタ、 ２１…ピア、 ２２…ノードリンク、 ３０…ネットワークシミュレーション装置、 ３１…シミュレーション実行管理部、 ３２…設定管理部、 ３３…ネットワーク状態管理部、 ３４…ノード実行部、 ３５…ログ管理部、 ３６…シミュレーション結果表示部、 ４０…ユーザ。
【技術分野】
【０００１】
本発明は、ネットワークの配信システムにおけるトラヒック量やスループット等についての評価を行うためのネットワークシミュレーション装置に関する。
【背景技術】
【０００２】
ネットワークシミュレーション装置は、実際にシステムを導入する前に、計画されたネットワークトポロジや使用するデバイスからトポロジ情報とトラヒック情報をもとにモデル化し、トラヒック量やスループット等についての大まかな推定を行うものであり、シミュレーション用に開発された種々のソフトをネットワーク上で実行することで行われる。
【０００３】
例えば、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などのインターネットプロトコルの動作を試験するためのネットワークシミュレーション装置であり、端末におけるパケット送受信や、ルータにおけるキューイング処理などを細かくシミュレーションできる。
【０００７】
しかしながら、BitTorrentなどのように、個々の端末が自律分散的に動作するプロトコルを定義できないという課題があった。また、扱うべき端末やルータの規模が多い場合、計算量が多くなるので、標準的なサーバ用PCを用いた場合、例えばルータ数が1,000程度までしか扱うことができないという課題があった。
【０００８】
前述のArtisocや、N3 Simulatorは、自律分散的に動作するエンド端末をシミュレーションすることに適したシミュレータであり、インターネットプロトコルに限らず、エンド端末上のプロトコルや、エンド端末上のイベント発生タイミングを独自に定義できることができる。
【０００９】
しかしながら、端末の動作に特化しているため、ネットワーク上のリンクやルータなどの振舞いまでをシミュレーションできないという課題があった。
【００１０】
本発明は上記事情に鑑みて提案されたもので、Ｐ２Ｐ中継型の配信システムで構築されるネットワークにおけるノード（端末、ルータ、サーバ等の総称）間のトラヒック量やスループットの評価に適したネットワークシミュレーション装置を提供することを目的としている。
【課題を解決するための手段】
【００１１】
上記目的を達成するため本発明は、ネットワークを定義する際、中継ネットワークとアクセスネットワークの役割を分け、Ｐ２Ｐ中継型の配信システムのシミュレーションにおいて重要となるアクセスネットワークに関してのみ、リンクのキューなどのネットワーク的な振舞いを忠実に再現する機能を持たせることにより、少ない計算量で大規模にネットワークと端末の双方をシミュレーションすることを可能としたものである。
【００１２】
すなわち、請求項１のネットワークシミュレーション装置は、複数のノードがそれぞれ接続された複数のクラスタ（小ネットワーク）を有するネットワークにおいて、前記複数のクラスタについて、中継を行うブランチクラスタと一つのブランチクラスタのみに接続されるリーフクラスタとに分割し、前記ブランチクラスタ同士及び前記ブランチクラスタと前記リーフクラスタとの間のクラスタ間リンクをノード間の通信でシェアし、前記リーフクラスタ内におけるノード同士のノード間リンクをノード毎に帯域を占有している。
そして、前記各ノードは、ノード間リンクとクラスタ間リンクのキューを併せ持ち、前記クラスタ内のノードが送信したデータのみをノード間リンク及びクラスタ間リンクのキューにて順番待ちを考慮して出力する扱いにより上り回線に限定して前記クラスタ単位で遅延時間を計算することでトラヒック量またはスループット（＝単位時間当たりのトラヒック量）の評価を行うことを特徴としている。
すなわち、クラスタを単位として管理されるネットワーク情報（ネットワーク構成情報、経路管理情報、キュー管理情報）に従い、ノード間で送受信されるメッセージの遅延時間を計算することで、クラスタ間毎のトラヒック量またはスループット（＝単位時間当たりのトラヒック量）の評価を行うものである。
【００１３】
請求項２のネットワークシミュレーション装置は、請求項１において、ビットトレント（BitTorrent）プロトコルを対象とし、前記クラスタ内の各ノードは、自律分散的に動作するトラッカーやピアであることを特徴としている。
【発明の効果】
【００１４】
本発明によれば、Ｐ２Ｐ中継型コンテンツ配信のネットワークシミュレーションを実現するにあたり、複数のノードが接続された複数のクラスタについて、中継を行うブランチクラスタと一つのブランチクラスタのみに接続されるリーフクラスタとに分割し、クラスタ内のノードが送信したデータのみをノード間リンク及びクラスタ間リンクのキューにて順番待ちを考慮して出力するよう扱うことにより、ネットワークとして忠実に再現する部分をアクセスネットワークの上り回線に限定している。これにより、従来のネットワークシミュレーション装置に比べて少ない計算量でＰ２Ｐ中継型コンテンツ配信のシミュレーションが実現できる。
【００１５】
従来のネットワークシミュレーション装置では、計算量の観点から、標準的なサーバ用PCを用いて、ネットワークのシミュレーションと、自律分散システムのシミュレーションを同時に行うことが難しいという問題があったが、本発明のネットワークシミュレーション装置によれば、中継を行うブランチクラスタと一つのブランチクラスタのみに接続されるリーフクラスタとに分割し、各クラスタに対して設定したネットワーク情報（ネットワーク構成情報、経路管理情報、キュー管理情報）に従い、ノード間で送受信されるメッセージの遅延時間を推定できるようにしたので、標準的なサーバ用PCを用いた場合でも、上述した両方の機能を持ち合わせることができる。
【図面の簡単な説明】
【００１６】
【図１】本発明のネットワークシミュレーション装置の構成を説明するための機能ブロック図である。
【図２】本発明のネットワークシミュレーション装置が適用されるネットワークトポロジの模式図である。
【図３】（ａ）及び（ｂ）は本発明のネットワークシミュレーション装置におけるリンクの概念を示す模式図である。
【図４】（ａ）〜（ｃ）は本発明のネットワークシミュレーション装置における遅延の定義を説明するための模式図である。
【図５】（ａ）〜（ｂ）は本発明のネットワークシミュレーション装置における遅延発生を説明するための模式図である。
【図６】本発明のネットワークシミュレーション装置における動作を説明するためのフローチャート図である。
【図７】（ａ）〜（ｅ）は本発明のネットワークシミュレーション装置で扱うメッセージ例を示す模式図である。
【図８】Ｐ２Ｐ中継型配信システムを実現するためのプロトコルとして利用されているBitTorrentプロトコルについての概要を説明するフロー図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態の一例について、図１及び図２を参照しながら説明する。
本発明のシミュレーション装置３０は、多数のノード（端末、ルータ、サーバ等の総称）が接続されて構成されるＰ２Ｐ中継システムを構築するネットワークについて、各ノード間のトラヒック量やスループット、ダウンロード時間の算出を目的としたシミュレーションを行うものであり、図１に示すように、ネットワーク内においてシミュレーションを行うユーザ４０に対して接続可能に構成されている。
【００１８】
ネットワークシミュレーション装置３０は、ユーザ４０からの要求により後述するシミュレーション動作フローにしたがってシミュレーションの実行を行うシミュレーション実行管理部３１と、シミュレーションの設定情報を管理する設定管理部３２と、ネットワークの状態を管理するネットワーク状態管理部３３と、各ノードにおけるイベントの実行をそれぞれ行う複数のノード実行部３４と、各ノード実行部３４でのイベントの実行結果を記録するログ管理部３５と、ユーザ４０からの要求に基づきログ管理部３５を参照してシミュレーション結果を表示するシミュレーション結果表示部３６とを備えて構成されている。
【００１９】
ネットワーク状態管理部３３は、ネットワークシミュレーション装置３０がシミュレーションするネットワーク構成を管理するとともに、ネットワークにおけるクラスタ間の経路管理(SPFで導出されるクラスタ間の経路についての管理)、及び、後述するクラスタ間リンク及びノードリンクの出力キューについてのキュー管理を行う。ネットワークシミュレーション装置３０がシミュレーションするネットワークトポロジは、図２に示すように、いくつかの小さなネットワークであるクラスタに分割される。
各クラスタは、他の地域との接続やISPとの中継を行う部分であるブランチクラスタ１０と、ユーザ（Ｐ２Ｐ中継システムではピアと呼ぶ）が属するアクセスネットワークよりの部分であるリーフクラスタ２０に分かれ、それぞれが相互に接続されている。
【００２０】
ブランチクラスタ１０には、相互に接続された複数のネットワーク中継機器(ルータ等)１１を有している。また、ブランチクラスタ１０によっては、Ｐ２Ｐ中継システムの一部を担うサーバ１２｛コンテンツサーバ、配信制御サーバ（トラッカー）等｝が設定されている。
【００２１】
リーフクラスタ２０は、アクセスネットワークを集約する機器を含んで構成され、機器の配下に複数のピア２１が設定されている。ブランチクラスタ１０は制限なく互いに接続できるが、リーフクラスタ２０はいずれか１つのブランチクラスタ１０のみと接続するようになっている。
【００２２】
ネットワークシミュレーション装置によるネットワークのシミュレーションは、以下のように単純化させて定義する。経路計算は、ブランチクラスタ１０又はリーフクラスタ２０毎のクラスタ単位で行われる。すなわち、クラスタ間に論理的なリンクが存在すると仮定し、リンク毎にコストや伝搬遅延を管理することが行われる。
【００２３】
あるクラスタから別のクラスタへの経路は、OSPFで用いられているSPFアルゴリズムと同様の方法で計算する。従って、クラスタ内のノードが別のクラスタのノードと通信する場合には、上記手段により、リンク毎に計算された経路を用いて通信を行う。
【００２４】
リンクのタイプとしては、図３に示すように、クラスタ間を接続するリンクとして論理的に存在するクラスタ間リンク（ブランチクラスタ１０同士間のリンク１５、及び、ブランチクラスタ１０とリーフクラスタ２０間のリンク１６）と、リーフクラスタ２０内に存在するノード毎に存在しノードとネットワークを接続するノードリンク２２とが存在する。したがって、一つのブランチクラスタ１０に属するノードと、他のブランチクラスタ１０に属するノードとの間の通信は、１つのクラスタ間リンク１５でシェアされる。また、リーフクラスタ２０に属するノードと、ブランチクラスタ２０に属するノードの接続の場合、ノード単位で帯域がシェアされるノードリンク２２と、クラスタ間リンク（ブランチクラスタ１０とリーフクラスタ２０間のリンク１６）の二つを経由して、ノード間の通信が行われる。
【００２５】
設定管理部３２は、ネットワークをシミュレーションする場合のシミュレーション設定情報を管理する。クラスタ（ノード）とクラスタ（ノード）との間のトラヒック量は、シミュレーション実行時に計算し、ログ管理部３５にて蓄積する。これにより、ユーザ４０は、シミュレーション実行後に、特定のクラスタ（ノード）間のトラヒック量を入手することができる。
また、シミュレーション設定情報の初期設定情報は、ユーザ４０がシミュレーション実行前に設定するものであり、ネットワーク構成（ブランチクラスタ１０又はリーフクラスタ２０）、リンクの接続構成（クラスタ間リンク（リンク１５及びリンク１６）又はノードリンク２２）、各クラスタ上のノード数・種類（ピア又はトラッカー）、ノードの起動タイミングなどの情報を含む。
【００２６】
ノード実行部３４は、ピアまたはトラッカーのいずれかのアルゴリズムに従い、イベント管理において管理しているイベントについて、１つのノードの動作を実行する。本発明のネットワークシミュレーション装置では、１０，０００以上の独立なノードのシミュレーションを行うことを想定しているため、独立なノード数だけノード実行部３４が存在する。各ノード実行部３４は、シミュレーション処理時間(SUT)を単位に１回、シミュレーション実行管理部３１よりノードＩＤ順に呼び出され、イベント管理において管理しているイベントのうち、そのシミュレーション処理時間(SUT)で実行すべきイベントを実行する。ノードは、ピアあるいはトラッカーのいずれかのアルゴリズムを持ち、それぞれのアルゴリズムに従ってイベントの実行を行う。イベントの実行結果は、時系列順に記録され、ログ管理部３５に蓄積される。
【００２７】
ログ管理部３５は、イベント毎に、処理に必要なイベント実行時刻，ノード，相手先ノード，イベント種別の情報が記憶されることで、トラヒック量等のシミュレーション結果を求めることができる。
【００２８】
ノード実行部３４でのイベント処理について説明する。
受信イベント処理は、メッセージの受信に伴うノード状態の更新を行う。ログ管理部３５に、受信イベント処理を行ったことを通知する。さらに、ピア／トラッカーアルゴリズムに従い、他の相手先ノード（複数もありうる)へメッセージを送信する必要がある場合には、送信イベント(複数もありうる)を設定し、送信イベント処理を行う。メッセージの送信に伴うノード状態の更新を行い、ログ管理部３５に送信イベント処理を行ったことを通知する。また、ネットワーク状態管理部３３に該当ノードから相手先ノードへの遅延の計算を依頼し、その結果、相手ノードに、現シミュレーション処理時間(SUT)に遅延時間を加えた時刻をイベント受信時刻として、本メッセージに関する受信イベントを設定する。
【００２９】
シミュレーション結果表示部３６は、ユーザ４０からの要求に基づきログ管理部３５を参照してシミュレーション結果としてのトラヒック量やスループットの表示を行う。
このトラヒック量は、メッセージの長さの合計で計算される。計算するタイミングとしては、例えば、ノードが送信イベントとしてメッセージを送信したときに行う。メッセージの長さは、シミュレーション初期設定により変えることも可能であるが、メッセージタイプ毎に固定長であり、例えばピースメッセージであれば２５６キロバイト等に設定する。基本的には、BitTorrentプロトコルに従って、メッセージの長さが決められる。
スループットは、時間当たりのトラヒック量であり、メッセージの長さの合計をシミュレーション対象時間の合計で割ることにより計算される。
【００３０】
次に、シミュレーション結果の具体例について説明する。
１単位のシミュレーション処理時間(SUT)を１００ミリ秒とし、シミュレーション全体で１０，０００SUTを消費したとすれば、１，０００秒間のシミュレーションを行ったことになります。この間で、クラスタＡ−Ｂ間のメッセージの長さの合計が２，０００ＭＢ(メガバイト)だったとすれば、クラスタＡ−Ｂ間のトラヒック量は２，０００ＭＢ、クラスタＡ−Ｂ間のスループットは、（２，０００／１，０００）×８＝１６Ｍｂｉｔ／秒となる。
【００３１】
次に、ネットワークシミュレーション装置のシミュレーションにおいて、ノード間のデータの通信で発生する３種類の遅延（伝搬遅延・伝送遅延・キューイング遅延）の定義について、図４を参照して説明する。なお、ネットワークシミュレーション装置で扱うデータの単位はメッセージと呼ばれる。
メッセージは、IPのプロトコルとしては、１〜複数のIPパケットに相当するが、ネットワークシミュレーション装置ではIP、TCP、UDPといったプロトコルを厳密に処理することは想定しておらず、アプリケーションレベルでの情報をメッセージという単位で表している。メッセージには、プロトコル制御情報の伝達を目的とする制御メッセージと、コンテンツなどのアプリケーションデータの転送を目的とするデータメッセージが存在する。本発明のネットワークシミュレーション装置では、制御メッセージのメッセージサイズは０であるとみなしている。
【００３２】
伝搬遅延は、図４（ａ）に示すように、クラスタ間リンクにおいて、メッセージが物理的に到着するのに要する遅延である。電気信号の伝達と関係し、ブランチクラスタ間の物理的な距離に比例して発生する遅延である。
伝送遅延は、図４（ｂ）に示すように、メッセージを、有限の帯域を持つリンクに送信開始し、送信完了するまでに要する遅延を表す。リンクの帯域が小さく、メッセージサイズが大きいほど、伝送遅延は大きくなる。
キューイング遅延は、図４（ｃ）に示すように、複数のメッセージ転送をシェアするリンクにおいて、メッセージの転送要求が発生してから該当するメッセージの転送処理を開始できるまでに要する時間である。メッセージを即座に転送出来ない場合は、メッセージは出力キューに蓄積される。この遅延は該当するメッセージのサイズには比例せず、出力キューのサイズが大きくリンクの帯域が小さいほど大きくなる。
【００３３】
次に、図５を参照して、上記の遅延を用いた遅延発生モデルについて述べる。
図５（ａ）に示すように、ブランチクラスタ１０内のノードが送信したメッセージについては、ブランチクラスタ毎に持つ出力キューのキューイング遅延、クラスタ間リンク１５での伝送遅延および伝搬遅延が発生する。
図５（ｂ）に示すように、リーフクラスタ２０内のノードが送信したメッセージについては、ノードリンク２２でのキューイング遅延および伝送遅延と、クラスタ間リンク１６でのキューイング遅延、伝送遅延および伝搬遅延が発生する。
図５（ｃ）に示すような複数のブランチクラスタ１０を経由するメッセージについては、各ブランチクラスタを経由する毎に、経由するブランチクラスタ１０での伝送遅延および伝搬遅延が発生する。
【００３４】
また、図５で示した遅延発生モデルに関して、モデルを単純化し計算量を減らすため、以下の条件を適用する。
（１）中継するクラスタ間リンクや、下りノードリンクでのキューイング遅延は発生しない。
（２）出力キューのサイズは無限大と考え、キューあふれによるパケットロスは発生しない。
（３）中継機器やリンクでのデータ転送誤り(ビットエラー)は発生しない。
（４）従って、ネットワーク上のパケットロスは一切発生せず、TCPでの再送による遅延なども考慮しない。
（５）ブランチクラスタ内のノードが、クラスタ間リンクが存在するルータへメッセージを転送するまでの遅延は考慮しない。
【００３５】
遅延の計算式は、クラスタ経路をＸ1・Ｘ2 … Ｘnとした場合、クラスタＸ1に属するノードａと、クラスタＸnに属するノードｂとのエンドエンドによる遅延時間Ｄe2e（秒）で表示することができる。そして、遅延時間Ｄe2eは、クラスタ間リンクの伝搬遅延（秒）であるＤp、クラスタ間リンクの伝送遅延（秒）であるＤt、クラスタ間リンクのキューイング遅延（秒）であるＤqの関数で表示することができる。
すなわち、Ｄp（ＸＹ）をクラスタＸ−Ｙ間のクラスタ間リンクの伝搬遅延（秒）、Ｂ（ＸＹ）をクラスタＸ−Ｙ間のクラスタ間リンクのＸ−Ｙ方向の帯域（bps）、Ｍをメッセージ長さ（byte）、Ｑt-1（ＸＹ）をクラスタＸ−Ｙ間のクラスタ間リンクの時刻t-1における出力キュー長（byte）とすると、クラスタ間リンク１５，１６における伝搬遅延Ｄp、伝送遅延Ｄt、キューイング遅延Ｄqは、それぞれ表１のように定義される。また、遅延時間Ｄe2eは、クラスタＸがブランチクラスタの場合、数１で計算される。
【００３６】
【表１】
【００３７】
【数１】
【００３８】
また、Ｂ（a）をクラスタＸ内でのノードａのノードリンクの上り方向の帯域（bps）、Ｑt-1（ａ）をクラスタＸ内でのノードａのノードリンクの上り方向の時刻t-1における出力キュー長（byte）とすると、ノードリンク２２における伝搬遅延Ｄp、伝送遅延Ｄt、キューイング遅延Ｄqは、それぞれ表２のように定義される。また、遅延時間Ｄe2eは、クラスタＸがリーフクラスタの場合、遅延時間Ｄe2e（秒）は数２で計算される。
【００３９】
【表２】
【００４０】
【数２】
【００４１】
次に、シミュレーション実行管理部３１の動作について、図６を参照して説明する。
本シミュレーション装置は、シミュレーション処理時間(SUT)ごとに、各ノードがイベント駆動型で独立に処理を実行する。シミュレーション装置起動時には、予め設定された項目に従い、各ノードの初期状態を設定し、SUTを初期状態の「０」とする（ステップＳ１０１）。SUT毎に、各ノードにおける受信イベントを処理し（ステップＳ１０２）、その後、送信イベントを処理する（ステップＳ１０３）。
0 SUTで送受信されるメッセージがあった場合、同一SUT内で複数回同一ノードの処理を行う必要がある。このため、再走査フラグを設け、再走査ありの場合（ステップＳ１０４）には、SUTを増加させる繰り返し各ノードの処理を実行する。
再走査無しとなったとき、SUTを増加させ（ステップＳ１０５）、次のSUTでの処理を実行する。シミュレーション終了条件が成立した場合（ステップＳ１０６）、結果出力を行い（ステップＳ１０７）、シミュレーションを終了する。
【００４２】
シミュレーション装置で扱われるイベントについて説明する。
ノード毎のイベントは、発生時刻、相手先、イベント種別、パラメータとともに、イベントキューに保持される。発生時刻は、シミュレーション起動開始からの経過SUTで表す。相手先は、イベントを送受信する相手のノードを識別する番号である。イベント種別は、メッセージのタイプ等である。パラメータは、イベントに付随するパラメータである。ノード間で転送されるメッセージは、送信・受信ノードにおいて、送信・受信イベントとしてそれぞれ処理される。
【００４３】
Ｐ２Ｐ中継型コンテンツ配信のプロトコルを実現するにあたり、ネットワークシミュレーション装置が対象とするメッセージの例について図７に示す。
図７（ａ）は、ノード間（Ｎ１とＮ２）で時間的な遅延なしにメッセージ転送が行われる場合である。
図７（ｂ）は、ノード間（Ｎ１とＮ２）でのメッセージ転送に、ａ時間のSUT時間の遅延が発生する例である。
図７（ｃ）は、ノード間（Ｎ１とＮ２）でのメッセージ転送において、受信メッセージに対する応答として、送信メッセージが発生する例である。システム内の処理遅延は無いものと仮定している。
図７（ｄ）は、ノード（Ｎ１）から複数のメッセージを同時刻に複数のノード（Ｎ２、Ｎ３）に対して送信する例である。
図７（ｅ）は、ノード間（Ｎ１とＮ２）の0 SUT内で、複数のメッセージがやりとりされる例である。
【００４４】
次に、Ｐ２Ｐ中継型配信システムを実現するためのプロトコルとして、広く利用されているビットトレント（BitTorrent）プロトコルについての概要について、図８を参照しながら説明する。
BitTorrentでは、１つのファイルを複数の固定長のピース（Piece）に分割し、Pieceメッセージを１つの単位として、複数のピアから独立に、自身が持っていないピースを受信する。各ピアは、転送可(Unchoke)にするピア、ピースをダウンロードする順番などに関して、ピア毎の自律的な判断で実施する。
【００４５】
BitTorrentは、配信制御を行うトラッカー(Tracker)と、コンテンツのダウンロード／アップロードを行うピア(Peer)の２種類のノードで構成される。ダウンロードを行うピア＃１(peer #1)は、まずトラッカーに対し、コンテンツを要求し（ステップ２０１）、トラッカーは、コンテンツのダウンロードが可能なピアリストをピア＃１(peer #1)に返す（ステップ２０２）。
ピア＃１(peer #1)は、ピアリストで通知された各ピア(peer #2,peer #3)とのTCPの接続を行い（ステップ２０３，２０５，２０６、及び、ステップ２０４，２０７，２０８）、その後、BitTorrentレベルでの接続(Handshake)を行う（ステップ２０９，２１０、及び、ステップ２１１，２１２）。
【００４６】
以降、例えばピア＃２(peer #2)に対してのピースマップのやり取り(Bitfield) （ステップ２１３及びステップ２１４）、ピアへの興味の通知(Interested／Not interested)（ステップ２１５及びステップ２１６）と、ピアへの転送可否の通知(Unchoke／Choke)（ステップ２１７及びステップ２１８）を行う。その後、ピア＃１(peer #1)はピア＃２(peer #2)にピースを要求(Request)し（ステップ２１９）、応答としてピース(Piece)を受信する（ステップ２２０）。
【００４７】
次に、上述したビットトレント（BitTorrent）プロトコルをネットワークシミュレーション装置で実現する方法を以下に述べる。Pieceメッセージはデータメッセージとし、それ以外のメッセージは制御メッセージとして扱う。
メッセージ転送については、ネットワークシミュレーション装置において、メッセージタイプ毎の送受信イベントを設定することにより実現する。各ピアが行う自律的な判断については、BitTorrentが持つアルゴリズムと同じものをネットワークシミュレーション装置で持たせる。
【００４８】
すなわち、ピアアルゴリズムでは、相手先ピアとの接続状態(TCPコネクションの接続、choke／unchoke状態等)、相手先ピアが保有するピース(コンテンツの一部)、相手先ピアの性能を示す情報(ダウンロード時間)などを管理し、どの相手先ピアから、どのピースを入手するか、choke／unchoke状態の変更タイミングなどを決定する。
トラッカーアルゴリズムでは、あるコンテンツのダウンロード要求を行った全てのピアの情報を管理し、新しいピアからピアリスト要求を受けた際に、一定数のピアリストを返答する。
アルゴリズムとしては、流通度の低いピースを優先的にダウンロードするRarest first algorithmや、ダウンロード速度が速いピアを優先的にデータ転送可とするTit-for-tat algorithmなどが存在する。
【００４９】
シミュレーション実行条件の例を以下に示す。
ピア毎に、クラスタ、起動時刻、終了時刻を設定する。起動時刻はSUT時刻で設定し、終了時刻はダウンロード完了からn SUT時刻経過などといった設定を行う。多数のピアの統計多重的な振舞いをシミュレーションするため、複数のピアについて設定をグループ化することを可能とする。例えば、一定間隔で起動、ダウンロード完了からａを平均、ｂを分散とする正規分布に従う時間経過後に終了などといった、統計的な振舞いを考慮した設定を可能とする。
シミュレーション結果としては、ダウンロード時間、メッセージタイプごとのメッセージ数などを出力する。各SUTでのノード処理時に結果出力に必要な情報を記録し、シミュレーション後に一斉に収集することとする。
【００５０】
上述したネットワークシミュレーション装置によれば、シミュレーション処理時間(SUT)を単位として各ノードをイベント駆動型でシミュレーションする基本設計であるため、１単位のシミュレーション処理時間(SUT)の時間を変えることにより、シミュレーションの精度を変えられるという利点がある。
また、ノード数の増加に伴うソフトウェアの実装へのインパクトは少なく、高性能なハードウェアを導入すればシミュレーション時間を単純に減らすことができる。
更に、ノード単位で独立に処理できる部分が多いため、マルチCPU、マルチスレッド化への対応が容易である。
【００５１】
上述したネットワークシミュレーション装置は、中継ネットワークとアクセスネットワークの役割を分け、クラスタを単位として管理されるネットワーク情報（ネットワーク構成情報、経路管理情報、キュー管理情報）に従い、ノード間で送受信されるメッセージの遅延時間を計算することで、クラスタ間毎のトラヒック量またはスループット（＝単位時間当たりのトラヒック量）の評価を行うので、少ない計算量で大規模のネットワークのシミュレーションを可能とし、10,000〜10,000,000相当の規模のユーザを対象としたＰ２Ｐ中継型コンテンツ配信モデルを評価するのに適している。
【符号の説明】
【００５２】
１…ネットワーク、 １０…ブランチクラスタ、 １１…ネットワーク中継機器(ルータ)、 １２…サーバ、 １５…クラスタ間リンク、 １６…クラスタ間リンク、 ２０…リーフクラスタ、 ２１…ピア、 ２２…ノードリンク、 ３０…ネットワークシミュレーション装置、 ３１…シミュレーション実行管理部、 ３２…設定管理部、 ３３…ネットワーク状態管理部、 ３４…ノード実行部、 ３５…ログ管理部、 ３６…シミュレーション結果表示部、 ４０…ユーザ。
【特許請求の範囲】
【請求項１】
複数のノードがそれぞれ接続された複数のクラスタ（小ネットワーク）を有するネットワークにおいて、
前記複数のクラスタについて、中継を行うブランチクラスタと一つのブランチクラスタのみに接続されるリーフクラスタとに分割し、
前記ブランチクラスタ同士及び前記ブランチクラスタと前記リーフクラスタとの間のクラスタ間リンクをノード間の通信でシェアし、
前記リーフクラスタ内におけるノード同士のノード間リンクをノード毎に帯域を占有し、
前記各ノードは、ノード間リンクとクラスタ間リンクのキューを併せ持ち、前記クラスタ内のノードが送信したデータのみをノード間リンク及びクラスタ間リンクのキューにて順番待ちを考慮して出力する扱いにより上り回線に限定して前記クラスタ単位で遅延時間を計算することでトラヒック量またはスループットの評価を行う
ことを特徴としたネットワークシミュレーション装置。
【請求項２】
ビットトレント（BitTorrent）プロトコルを対象とし、前記クラスタ内の各ノードは、自律分散的に動作するトラッカーやピアである請求項１に記載のネットワークシミュレーション装置。
【請求項１】
複数のノードがそれぞれ接続された複数のクラスタ（小ネットワーク）を有するネットワークにおいて、
前記複数のクラスタについて、中継を行うブランチクラスタと一つのブランチクラスタのみに接続されるリーフクラスタとに分割し、
前記ブランチクラスタ同士及び前記ブランチクラスタと前記リーフクラスタとの間のクラスタ間リンクをノード間の通信でシェアし、
前記リーフクラスタ内におけるノード同士のノード間リンクをノード毎に帯域を占有し、
前記各ノードは、ノード間リンクとクラスタ間リンクのキューを併せ持ち、前記クラスタ内のノードが送信したデータのみをノード間リンク及びクラスタ間リンクのキューにて順番待ちを考慮して出力する扱いにより上り回線に限定して前記クラスタ単位で遅延時間を計算することでトラヒック量またはスループットの評価を行う
ことを特徴としたネットワークシミュレーション装置。
【請求項２】
ビットトレント（BitTorrent）プロトコルを対象とし、前記クラスタ内の各ノードは、自律分散的に動作するトラッカーやピアである請求項１に記載のネットワークシミュレーション装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１０−２１９６７７（Ｐ２０１０−２１９６７７Ａ）
【公開日】平成２２年９月３０日（２０１０．９．３０）
【国際特許分類】
【出願番号】特願２００９−６１７２９（Ｐ２００９−６１７２９）
【出願日】平成２１年３月１３日（２００９．３．１３）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２２年９月３０日（２０１０．９．３０）
【国際特許分類】
【出願日】平成２１年３月１３日（２００９．３．１３）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]