Mercurial > hg > Papers > 2008 > fuchita-master
changeset 13:4b3b91501102
fix
| author | fuchita |
|---|---|
| date | Fri, 15 Feb 2008 22:09:51 +0900 |
| parents | d0afeaf4d60c |
| children | 9a65c4336120 |
| files | paper/conclusion.tex paper/evaluation.tex paper/implementation_of_compact_routing.tex paper/introduction.tex paper/master_paper.log |
| diffstat | 5 files changed, 53 insertions(+), 42 deletions(-) [+] |
line wrap: on
line diff
--- a/paper/conclusion.tex Fri Feb 15 20:58:55 2008 +0900 +++ b/paper/conclusion.tex Fri Feb 15 22:09:51 2008 +0900 @@ -13,15 +13,16 @@ 利点として、Java言語のオブジェクト指向やリファクタリングといった利点を示した。 最後には、分散開発環境において必要となるデバッグインターフェースの提案を行い、 -新しい実装を用いた機能拡張として、通信状態のFederated Lindaに対して、通信を止める事無く -その通信のスケーラビリティを知るデバッグインターフェースを実装しその効果を評価した。 +新しい実装を用いた機能拡張として、通信状態のFederated Lindaに対して通信を止める事無く、 +その通信のスケーラビリティや、通信の確かさを確認できるデバッグインターフェースを実装し、 +その効果を評価した。 \section{今後の課題} 今後の課題として、分散デバッグインターフェースを用いての新しいアプリケーションの実装と評価や、 分散デバッグ情報としてリングトポロジでの分散スナップショット機能をタプルサーバーへの拡張として 実装を行う事が挙げられる。 -また、Federated Lindaのtype3としてのより高度な実装として +また、Federated Lindaのより高度な実装として Protocol Engineをステートレスに実装する事で、タプルサーバー内の情報だけでFederated Linda全体の -状態遷移を検証可能とする実装が考えられる。 +状態遷移を検証可能とする実装が、分散スナップショットの実現には必要であると考えられる。
--- a/paper/evaluation.tex Fri Feb 15 20:58:55 2008 +0900 +++ b/paper/evaluation.tex Fri Feb 15 22:09:51 2008 +0900 @@ -5,13 +5,15 @@ Federated LindaによるCompact Routingの実験においては、ルーティングテーブルの構築を例に、 分散環境でのスケーラビリティをもった実装を確認しようとしたが、現状のLindaの実装では個々のノードが どのような通信状態をもってスケーラビリティを達成するのか明確に確認することが困難なばかりか、 -meshトポロジにおける実験においてはどのような通信状態によってノード全体のスケーラビリティが低下 +格子状のメッシュ型トポロジにおける実験においては、どのような通信状態によってノード全体のスケーラビリティが低下 しているのかを確認するすべが存在しなかった。これを解決する為には、Federated Lindaの通信を阻害せずに 大域的な情報でデバッグが行えるインターフェースが必要である。 -よって本章では分散環境におけるデバッグの難しさと分散デバッグに必要な機能について説明し、 -そのうちから通信状態のスケーラビリティを確認するという点において、 -Federated Lindaでの分散開発環境におけるデバッグ機能の追加を行う。 +よって本章では、分散環境におけるデバッグの難しさと分散デバッグに必要な機能について説明し、 +そのうちから通信状態の集中を検知するという点において、 +Java版Lindaサーバーへの通信状態のデバッグインターフェースの実装と、視覚的に通信状態を確認する +モニターツール実装の二点を行い、 +その評価を行う。 本論文でFederated Lindaに追加する分散デバッグ機能のアプローチは、 4章で必要性を述べた通信状態のデバッグをJava版Linda サーバーへの拡張を行う事で実現するものである。 @@ -353,7 +355,7 @@ 本論文では、前述した分散アルゴリズムにおいてデバッグすべき対象のうちから、 通信の集中を検知するデバッグインターフェースについて実装を行った。 このデバッグインターフェースを用いる事により、３章で提示したCompact Routingを用いるFederated Linda -において、meshトポロジで起こったデバッグ困難な通信の集中を伴う状態の検知を行う事を目標とする。 +において、格子状のメッシュ型トポロジで起こった、デバッグ困難な通信の集中を伴う状態の検知を行う事を目標とする。 以下にその詳細を示す。 @@ -445,8 +447,8 @@ } \end{itembox} \end{center} -通信ループ内において、通信状態のデバッグインターフェースを受け付けるのは要求があった -idが、PRIVILEGED(特権的な)\_IDとして確保した領域であった場合である。今回は1〜65535ま +通信ループ内において、通信状態のデバッグインターフェースを受け付けるのは、要求があった +idがPRIVILEGED(特権的な)\_IDとして確保した領域であった場合である。今回は1〜65535ま でのタプルスペースIDのうちidが32769以降の場合において、その要求をデバッグインター フェースの為の特権IDとして用いた。特権IDでの要求を検知した場合、ComDebug.addChannel を行い、通信状態の報告を行うセッションのリストに追加を行う。 @@ -509,7 +511,7 @@ Lindaサーバーへの通信状態デバッグ機能の追加と、その為のクライアントプログラムによって、 Federated Lindaの通信状態のログを取得する事ができた。しかし、取得したログはそれだけではどのよう な通信状態の変化があったのかを直感的に知る事は難しい。よって、前述したデバッグインタ -ーフェースを用いて取得したログを視覚的に確認できるツールの開発を行った。 +ーフェースを用いて取得したログを、視覚的に確認できるツールの開発を行った。 このツールは、Federated LindaのLink Configurationに用いたOmni Graffleファイル、 同じくLink Configurationに用いたノードリスト、そしてデバッグインターフェースで取得した通信 @@ -568,8 +570,8 @@ その後、表示したトポロジ図のノードと投入する通信状態のログからそれぞれのマッチングを行い、 通信状態の変化をステップ実行で確認できる。 -ツール上に表示可能な通信ログのデータは、送受信元ノードのTSID, 送受信ノードTSID, In/Out/Rd/Ck のモード情報と回数, - タプルID, シーケンス番号, タプルのデータ内容, である。 +ツール上に表示可能な通信ログのデータは、送信ノードのTSID, 受信ノードのTSID, In/Out/Rd/Ck の +モード情報と累積発行回数, タプルID, シーケンス番号, タプルのデータ内容, である。 図\ref{visual01}に通信ログ・モニタツールの動作状況を示す。 \newpage \begin{figure}[htbp] @@ -584,20 +586,20 @@ 実装した通信状態のデバッグインターフェースの評価として、3章で述べたDistance Vector型及び、 Compact Routingの実装を用いるFederated Lindaの通信状態デバッグを行う。 この評価の狙いは通信デバッグインターフェースを用いることで、従来のFederated Lindaにおける -printf情報などを用いたテスト駆動開発では困難であった通信状態の確認を可能とする事である。 +printf情報などを用いたテスト駆動開発では困難であった、通信状態の確認を可能とする事である。 また、この評価によるバグ要因の特定も目標とする。 \subsection{評価条件} \subsubsection{問題点} Federated Lindaは分散アルゴリズムを用いてタプルの伝搬を行うが、先行研究にて開発した - Distance Vector型及び、Compact Routingの実装は共に格子状のメッシュトポロジ上での - ルーティングテーブルの構築に問題がある。Distance Vector型はメッシュトポロジ上での + Distance Vector型及び、Compact Routingの実装は共に格子状のメッシュ型トポロジ上での + ルーティングテーブルの構築に問題がある。Distance Vector型はメッシュ型トポロジ上での ルーティングテーブル の構築が、ライン型トポロジや、バイナリツリー型トポロジとの場合に比べて、 大幅に時間がかかるという問題、 - Compact Routingの実装では格子状のメッシュトポロジ上でのルーティングテーブルの構築が、 + Compact Routingの実装では格子状のメッシュ型トポロジ上でのルーティングテーブルの構築が、 通信の集中や、Landmark情報の更新の失敗によって、構築が行えないという問題である。 - 図\ref{meshtime}にDistance Vector型において格子状のメッシュトポロジでのルーティングテーブルの + 図\ref{meshtime}にDistance Vector型において格子状のメッシュ型トポロジでのルーティングテーブルの 構築時間とバイナリツリー型トポロジによる物を比較した結果を示す。 \begin{figure}[htbp] @@ -641,9 +643,9 @@ 評価条件に示した実験を行い、6ノードで構成される格子状のメッシュトポロジにおける Federated Lindaのルーティングテーブル構築の通信状態ログを取得した。 - これにより、通信状態ログを用いたモニタツールでのデバッグが可能となった。 + これにより、通信状態ログを用いたモニターツールでのデバッグが可能となった。 ここで示す通信状態ログによるデバッグとは、Lindaサーバー単体、Lindaサーバー全体、タプルID、 - シーケンス番号などを単位に通信ログをモニタツールに投入し、ステップ実行でタプルの通信を + シーケンス番号などを単位に通信ログをモニターツールに投入し、ステップ実行でタプルの通信を 確認するデバッグ方法である。 図\ref{debug1}と図\ref{debug2}にその様子を示す。 @@ -666,7 +668,7 @@ \newpage \subsubsection{バグ要因の特定} 通信ログ・モニターツールを用いてDistace Vector型、Compact Routing実装のデバッグを - 行った所、Link Configuratin処理が正しく終了していない為にルーティングテーブル構築時の + 行った所、Link Configuratin処理が正しく終了していない為に、ルーティングテーブル構築時の 通信量が増えているというバグを発見した。 通常、Federated Lindaにおけるルーティングテーブルの構築は、最初にLink Configurationを @@ -674,7 +676,7 @@ の転送とコネクトをもって全ノード間のコネクションのLink Configurationを行う。 しかし、格子状のメッシュトポロジでは、隣接ノードへの転送から次ノードへ別経路で - Link Configurationが到達する為にLink Configuratinを行うタプル転送が消滅せずに、 + Link Configurationが到達する為、Link Configuratinを行うタプル転送が消滅せずに、 ルーティングテーブルの構築中でもLink Configurationが発生しているというバグである。 図\ref{bugfig}にその様子を示す。 @@ -689,7 +691,7 @@ ルーティングテーブルの構築時においてもLink Configurationのタプル転送が発生していたことで、 Distance Vector型での構築時間はバイナリツリー型トポロジに対して大幅に増加していたという - ことが、今回の通信状態デバッグインターフェースによって特定できた。また、Compact Routing実装の + ことが、今回の通信状態デバッグインターフェースによって特定できた。また、Compact Routing実装の、 格子状メッシュトポロジにおけるルーティングテーブルの構築失敗もローカルネットワークの構築と Landmark情報の更新にDistance Vector型の転送方法を用いている為に、同様に別経路からの情報更新 要求が正常終了せずに流れている為と分かった。 @@ -718,16 +720,17 @@ Java版Lindaサーバーを開発したことにより、以前のC言語による実装よりも機能拡張を容易に行う事が 可能となった。そのため、前述した分散アルゴリズムにおいてデバッグすべき対象のうち、通信の集中 -を検知できるデバッグインターフェースとして、通信状態のログ取得デバッグインターフェースとそのログを -視覚的に表示し、ステップ実行で通信の状態を確かめられるログ・モニターツールを開発した。 +を検知できるデバッグインターフェースとして、通信状態のログ取得デバッグインターフェースと、 +そのログを視覚的に表示し、ステップ実行で通信の状態を確かめられるログ・モニターツールを開発した。 開発した通信状態のデバッグインターフェースの評価として、6ノードで構成される格子状メッシュトポロジ -におけるルーティングテーブルの構築を、Distance Vectorg型とCompact Routin実装のFederated Lindaで +におけるルーティングテーブルの構築を、Distance Vectorg型とCompact Routing実装のFederated Lindaで 行い、通信状態のデバッグインターフェースを適用した。 この結果、正常終了しなかったLink Configurationのタプル転送が別経路から送信されているというバグ 要因を特定した。 通信状態のログ・モニターツールを用いる事で、これまでprintfによるデバッグでは困難であった通信状態 の確認を非常に分かりやすく行うことができる。これは、スナップショットを用いたログデバッグであっても -同様で、デッドロック, ライブロック, スケーラビリティ, 通信の集中, 大量のパケットの集中はなんらかの -スナップショット・モニターツールの開発が必要であると考える。 \ No newline at end of file +同様で、デッドロック, ライブロック, スケーラビリティ, 通信の集中, 大量のパケットの送信, +等の効率的な +検知を行うには、なんらかのスナップショット・モニターツールの開発が必要であると考える。 \ No newline at end of file
--- a/paper/implementation_of_compact_routing.tex Fri Feb 15 20:58:55 2008 +0900 +++ b/paper/implementation_of_compact_routing.tex Fri Feb 15 22:09:51 2008 +0900 @@ -390,8 +390,8 @@ \section{ルーティングテーブル構築時間の測定} ここで、Distance Vector型のルーティングテーブルを構築する方法[3]と今回実装した コンパクトルーティングを行う方法のルーティングテーブルの構築時間をそれぞれ -10,20,30のノードでトポロジはLine型トポロジとBinary Tree型トポロジを用いて測定した。 -Mesh型トポロジに対しても同様に測定を行ったが、トポロジ依存によるパケットの +10,20,30のノードでトポロジはライン型トポロジとバイナリツリー型トポロジを用いて測定した。 +格子状のメッシュ型トポロジに対しても同様に測定を行ったが、トポロジ依存によるパケットの ビジールーブが解決できず、正確に測定が出来なかったためここには記載しない。 またこの場合、コンパクトルーティングを行う際のローカルネットワークのホップカウントは 2と固定して測定を行う。 @@ -507,7 +507,7 @@ 多ターミナルでのテスト駆動開発によって開発を行っているが、 実際に開発を行ってみて気がつく開発のやりにくさやデバッグ環境の不備があった。 -具体的例として、メッシュトポロジにおけるFederated Lindaの実装に原因特定不可能な +具体的例として、格子状のメッシュ型トポロジにおけるFederated Lindaの実装に原因特定不可能な パケットのビジーループが見られた。現在のような多ターミナルによるテスト駆動開発では このような問題を特定するのに十分なデバッグ情報を得る事ができず、また一回の駆動実験 にかかる起動コストも、よりテストを煩雑な物と化している。
--- a/paper/introduction.tex Fri Feb 15 20:58:55 2008 +0900 +++ b/paper/introduction.tex Fri Feb 15 22:09:51 2008 +0900 @@ -36,13 +36,16 @@ を提供することである。 本論文では、本研究室で開発した分散プログラミングモデル Federated Linda を用いた -分散アルゴリズムの記述事例としてCompactRoutingというルーティングテーブルの収束速度や +分散アルゴリズムの記述事例として、CompactRoutingという、ルーティングテーブルの収束速度や ネットワークのスケーラビリティに対して優位なアルゴリズムの実装例について紹介し、 その開発によって得られた知見から本モデルに必要な機能拡張を提案する。 -本モデルへの機能拡張としてまず最初の段階で、Lindaサーバーの実装プログラミング言語を -Java言語とし、Java言語の高度な移植性やコードの再利用性を得た。 -これをもって、FederatedLindaの記述経験から必要と考える拡張機能を実装し、その評価を行う。 +本モデルへの機能拡張としてまず最初の段階で、Federated Lindaの実装プログラミング言語を +Java言語とし、Java言語のオブジェクト指向やリファクタリングを用いた開発の効率化を得た。 +これをもって、FederatedLindaによるCompact Routingの実装経験から必要と考える、 +分散デバッグ環境について検討を行い、実際にデバッグインターフェースの拡張機能を実装する。 +実装したデバッグインターフェースの評価として、Federated Lindaでの分散アルゴリズム +におけるバグの特定を行い、その有用性を示す。 @@ -51,13 +54,17 @@ また、実装するにあたっての段階分けや現時点でFederated Lindaに実装されている機能についても述べる。 第3章では提案する分散プログラミングモデル Federated Linda を用いた分散アルゴリズム -の実装をスケーラビリティに優れたアルゴリズムである``Compact Routing''による実装 +の実装を、スケーラビリティに優れたアルゴリズムである``Compact Routing''による実装 を用いて紹介する。 第4章ではFederated Linda による分散アルゴリズムの実装の経験によって得られた知見を -もとにJava言語によるタプルサーバーの実装と、 +もとに、Java言語によるタプルサーバーの実装と、 Java言語でFederated Lindaの開発を行う事による利点について述べる。 -第5章では通信量のスケーラビリティを検証するデバッグインターフェースの開発と評価を行い、 -第6章でまとめと今後の課題を述べる。 +第5章ではFederated Lindaに必要と考える分散デバッグ機能の検討を行い、 +デバッグインターフェース機能拡張の例として、 +通信量のスケーラビリティを検証するデバッグインターフェースの開発と評価を行う。 +第6章ではFederated Lindaと同じくタプルスペースをベースにしたアーキテクチャであるJiniとの +比較を述べ、7章においてまとめと今後の課題とする。 +
--- a/paper/master_paper.log Fri Feb 15 20:58:55 2008 +0900 +++ b/paper/master_paper.log Fri Feb 15 22:09:51 2008 +0900 @@ -1,4 +1,4 @@ -This is pTeX, Version 3.14159-p3.1.5 (euc) (Web2C 7.4.5) (format=platex-euc 2005.5.19) 15 FEB 2008 21:27 +This is pTeX, Version 3.14159-p3.1.5 (euc) (Web2C 7.4.5) (format=platex-euc 2005.5.19) 15 FEB 2008 22:38 **master_paper (./master_paper.tex pLaTeX2e <2005/01/04>+0 (based on LaTeX2e <2001/06/01> patch level 0) @@ -602,4 +602,4 @@ 14 hyphenation exceptions out of 1000 33i,12n,24p,300b,631s stack positions out of 1500i,500n,5000p,200000b,5000s -Output written on master_paper.dvi (82 pages, 264272 bytes). +Output written on master_paper.dvi (82 pages, 265768 bytes).