« 2005年1月 | トップページ | 2005年3月 »

2005年2月の17件の投稿

2005.02.26

[P2P勉強会]お疲れ様でした。。

本日P2P勉強会を無事終了しました。
懇親会のメンバを含めると100人弱の出席者のため、うまく回るか不安でしたがボランティア等の方々に助けられながらなんとか成功に結びつける事ができました。今回の勉強会でご協力した頂いた方、大変ありがとうございます!

是非第3回目勉強会も開きたいと思いますのでよろしくお願い致します。勉強会事務局をやってみたい方は是非ご連絡をお願い致します。
また、今回参加された方はBlog等で是非勉強会の感想、メモ等を書いて頂きたいと思います。

※メモ:
私の資料で書いた、DHTとべき乗法則に従ったリンク数を結びつけたアイデアというのは既に論文であるらしい。
それによると、普通はDHTの検索ホップ数はO[log(N)]だが、それを使うとO[log(log(N))]とのこと。
後で論文名を紹介してもらうので、レビューしたいと思います。

| | コメント (1) | トラックバック (3)

2005.02.23

[P2P勉強会]プレゼン資料公開します

第2回P2P勉強会のプレゼン資料について、各講師から順次こちらに送って頂いていますので、準備が出来次第公開致します。
既に公開できる資料については下記URLにおいてありますので、ご覧になって下さい。
第2回P2P勉強会プレゼン資料

よろしくお願い致します。

P.S 今頃気づいたのですが、IP!誌3月号に私のHPが紹介されていました。詳しくは85Pを見て下さい。
※雑誌の掲載の際には私への事前連絡が欲しいです。。。

| | コメント (2) | トラックバック (0)

2005.02.20

[P2P勉強会]プレゼン資料ベータ版

P2P勉強会がいよいよ今週末に迫ってきました。
事務局は120名を超える参加者のためにメンバ表やアンケート作成など忙しい日々を過ごしています。

さて、私のP2P勉強会でのプレゼン資料を作成しましたので、ご紹介します。まだベータ版ですので、誤字脱字、表現の誤り等ございましたらご連絡をお願い致します。
分散ハッシュテーブル(DHT)入門とP2Pにおける認証について:pdf版

コメントがあればご連絡をお願い致します。

| | コメント (0) | トラックバック (0)

2005.02.17

[Blog]ソーシャルタギングとBlogの組み合わせ

そういえば、Blogとソーシャルタギングの組み合わせってないのだろうか?もう既に行われているかもしれないが。

例えば、タイトルに[....]をいれて題名を書くとそれがタグなる。たとえば、

[クラシック][ヴァイオリン]バッハのヴァイオリン無伴奏ソナタ
とすれば「クラシック」「ヴァイオリン」が共通のタグとなる。
※タグと書くと大げさかな。カテゴリとでもした方が良いのかもしれない。

もちろん、タグ用のフォームを専用に作るのもアリだ。

これは、自分用にまずBlogをカテゴライズすることも出来るのだが、(もちろん、他ユーザからそのように見せる仕組みが必要)同時に他の人が同じタグで作成したBlogを容易に参照できる。

例えば、
[クラシック]ショパンの幻想即興曲

というBlogがあるとする。その際、クラシックというタグを押すと、時系列で[クラシック]でタグ付けされたBlogが一覧となって並ばれる、という仕組みである。

あるいはBlogを記入した時間を指定してトラックバックやコメント数に応じて一覧がソートされるのも面白いかもしれない。

もうちょっと意味ネットワーク的なことを書くと、例えば「ヴァイオリン」というタグは「チェロ」「ヴィオラ」「弦楽器」などの言葉を連想するから、そのようなタグ一覧を表示するというのもアリかもしれない。こうなると単なるタグでなく、タグ同士が有機的に繋がってとても面白いシステムになる可能性がある。もしくは、タグに階層を作るのもアリだ。
(例えば、ヴァイオリンなら楽器⇒弦楽器⇒ヴァイオリンなど。でもこれは既定の階層されたタグがないとキツイかも。もしくは、意味ネットワーク的に後でシステムが語彙を階層化して表示されるのもアリだ。こっちの方がスマート。
例えば、「ヴァイオリン」というタグは他のタグの参照をする時には楽器⇒弦楽器⇒ヴァイオリンと階層の同レベルに「チェロ」「トランペット」などのタグを表示するとか。)この辺はセマンティックWEBなどのメタデータや語彙の関連付けを研究している人に聞くと面白そうだ。

※本当はBlogの内容をシステムが理解して勝手にタグ付けすると面白いんだけどもね。そして、その意味空間が近いBlogを紹介できるサービスを作るとか。誰かトライしてみませんか?

ココログに備えているカテゴリ(タグとも呼べるかな)はとても大まかなものなので、このようなタグ付けは便利なツールになるかもしれない。

| | コメント (0) | トラックバック (1)

2005.02.16

[Blog]トラックバックフィルタリング

最近、スパム的にトラックバックをするところが多く居て、正直対応するのが面倒である。
メールのスパム防止のようにトラックバックもフィルタリングするといいとは思いませんか?

例えば。。。
1)トラックバック元のURLからフィルタリング。
2)更にトラックバック元の内容からフィルタリング。
3)これらのスパム的なトラックバックについてはブラックリストとしてサーバで管理し、他のユーザと情報共有する。

もっともスパム的なトラックバックが実は本当に意味のあるトラックバックのある可能性があるので、
◇システムがスパムと判定したトラックバックについてはBlog所有者が許諾しないと掲載されない
というのはどうだろうか?

コメントスパムはプロキシなどでIPアドレスが変更されるからちょっと難しいが、内容からなんとかフィルタリングはできるかもしれない。これも上手くいけば、IPor逆引きでわかるドメイン等でブラックリストができるかもしれない。

実はもう既に実現されていたりして。。。

| | コメント (0) | トラックバック (0)

[P2P]機能拡充とノードの負荷について

分散ハッシュ(DHT)を使うと色々なサービスが容易に展開できることが期待できる。ただし、データの取得はネットワーク全体に分散しているわけだから、使えば使うほどノードとネットワークの負荷がかかるわけである。

これは分散してデータを管理するというDHTの宿命かもしれない。

DHTに参加しているノードは、DHTネットワークを維持することだけでもノードとネットワークのリソースを消費する。これは簡単な例で言うとGnutellaに参加するノードがリンクを維持するためにリソースを消費していると同じ事だ。

それに今度は機能を拡充する「モジュール」が各ノードに入るわけだ。
例えば、SkypeライクなVoIPシステムを作成するとすれば

・呼制御をするためのSIPサーバ用モジュール
・SIPレポジトリを実現するためのレポジトリ(というか簡易データベースorストレージ)用モジュール
・UDP Hole punchingをするためのSTUNサーバ用モジュール
・SymmetricNAT対策用などに使うための、ノード間通信橋渡し用モジュール
・通信路を暗号化し、またクライアント間認証を行うためのSSLモジュール
....

少し考えただけでも色々なモジュールが必要となる。このときに、SIPサーバ用モジュール、STUNサーバ用モジュール、ノード間通信橋渡し用モジュール等については基本的には自分のノードのためのものではない。つまり、「他の人」のノードを機能を提供するために使われる。そういうことになると、「P2P」という機能を考えると当然かもしれないが、自分以外のユーザのためにリソースを取られることを考える事になる。

今はまだあまり問題にされていないが、ある程度機能が拡充されたり、あるいは(ネットワーク越しで)データアクセス頻度が高いサービスを実装するとなると果たしてP2Pでサービスを利用するのか、またはクライアント=サーバ型でサービスを実現するか議論が再燃するかもしれない。この議論についてはその頃のネットワークの帯域、CPU、HDD等の性能にも依存することにもなるとは思うが。

「分散」と「集中」の議論は果てしなく続くのかもしれない。
以上、タダの雑談でした。。

| | コメント (0) | トラックバック (0)

2005.02.15

[P2P]分散ハッシュ(DHT)によるソーシャルタギングの考察

ご存知な方も多いと思うが、現在ソーシャルタギングというサービスが非常に注目を浴びている。 ソーシャルタギング”はGoogleを超えるか (ITmedia) ここではdel.icio.usライクなシステムをDTHで構成した場合どのような課題点があるか考察してみる。 del.icio.usについは下記を参照して欲しい。 del.icio.us でブックマークを管理 まず、自分の用のページを作成する事から始まる。自分用のページについてはユーザ名_更新日時.htmlというファイルを作れば良いだろう。このファイルはNode_ID=hash(username)となるノードで管理するので、電子署名をしておく。 更新日時が新しくて、自分の電子署名で作成した物である事が検証されたら、そのファイルを保存しているノードは上書き(というかファイルの置き換え)を認める。 ところで、del.icio.usの最大のウリは自分がブックマークしたWEBページやBlogなどを、他の人が同じようにブックマークしたかわかることだ。これをなんとかDHTで実現しよう。 今、自分用のページで、URLの部分だけ切り出す。これをNode_ID=hash(URL)となるノードに対して、{URL、username}という情報を蓄積しておく。こうすれば、同じURLをタグしているノードについてはNode_ID=hash(URL)にのsのUsernameデータが格納しているので、判別するということになる。usernameがわかれば、もちろんそのユーザのページ(つまりタグをしている全体のページ)も閲覧できるということになる。なぜなら、あるユーザusernameのタグを管理しているページはNode_ID=hash(username)に格納しているのだから。 こう考察すると簡単にソーシャルタギングがDHTでできそうに見えるが、実は問題がある。 というのは、del.icio.usの場合、自分のタグを管理しているページを閲覧すると、そのタグをしたURLに何人タグをしているか閲覧できるようになっている。ということは、URL毎に何人タグをつけているか、Node_ID=hash(URL)となるノードに全て聞かなくてはならない。これはとてもトラフィック量が多くなる可能性があるし、なによりもページを全て閲覧するのに時間がかかってしまうだろう。もっともこの問題はページの表示の仕方を変えたりすれば改善するかもしれない。 ソーシャルタギングはブックマークだけでなく、様々な情報を共有、レコメンドすることで発展することになるだろう。その際、システムの負荷が現在のソーシャルネットワークのようにとても大きくなる事が予想される。 このような事態になるとDHTで構成されたソーシャルタギングが注目を浴びる事になるだろう。 ※それよりもDHTでシステムを構築することにより、メンバ間でチャットやVoIP、ファイル共有などの機能が簡単に実装することになるメリットの方が高いのかもしれない。

| | コメント (0) | トラックバック (0)

[P2P]分散ハッシュ(DHT)入門プレゼン資料

当Blogで好評?連載中のDHT入門ですが、ついにプレゼン資料を作成しました。
BlogのDHT入門と連動していますので、一緒に読まれると学習効果は倍増だと思います。
分散ハッシュ(DHT)入門

なお、Mixiオフ会や第1回P2P勉強会の資料も同URLに掲載していますので、よりDHTについて詳しい事を知りたい方はそちらもご覧になると良いでしょう。

第2回P2P勉強会は本プレゼン資料にDHTの応用と認証についてのトピックを補筆する予定です。
プレゼン資料に誤字脱字等がありましたらご連絡をお願い致します。

| | コメント (0) | トラックバック (0)

2005.02.11

[P2P]分散ハッシュ(DHT)入門~その7

前回はDHTにノードが参加する場合にどのようにすれば良いのか説明した。今回はノードがDHTから離脱する場合の処理について書きたい。

「あいうえお」DHTで、ノード「う」がDHTに参加する場合、隣接しているノード、すなわちノード「い」とノード「え」に自分の存在を知らせれば良かった。そして、ノード「う」が管理すべき情報をノード「い」から引継ぎする事も必要である。

そうなると離脱する場合には同じように隣接するノード、つまりノード「い」とノード「え」にノード「う」が離脱するよ、と事前に連絡すれば良いことになる。

具体的には、
1.ノード「い」に対してノード「う」が離脱することを伝える。このときに、ノード「い」の隣接ノードがノード「え」になることを確認する。
2.ノード「え」に対してノード「う」が離脱する事を伝える。このときに、ノード「え」の隣接ノードがノード「い」になることを確認する。

これでルーティングテーブルについては受け渡しが完了した訳だが、肝心のノード「う」が持っているデータを受け渡すことを忘れている。ということで、
3.ノード「い」に対してノード「う」のデータを受け渡しする。(なぜなら、ノード「い」は「い」「う」のデータを管理するようなルールにしたから。)

と言う処理を忘れてはならない。

これでメデタシメデタシ。。と言いたい事だが、残念ながらそういうわけにはいかない。
というのは、今の離脱の処理はノードが前もって離脱する意志があって、事前に離脱処理を出来た場合に相当する。実際にはネットワークやノードの関係で急にノードが離脱する可能性もある。(例えばPCの電源断、ルータの故障など)そういう場合にはこのような処理をする事が出来ない。

ということは、ノードが急に離脱してもDHTがうまく働く処理をしないといけない。これがDHTの実装での難関の一つである。ではどのようにすれば良いのだろうか?

例えば、今ノード「う」が急に抜けたとする。その時に隣接ノード、ノード「い」ノード「え」は定期的に自分のルーティングテーブルのノードにpingなどの試験を行って相手のノードの確認をすれば、ノード「う」が急に居なくなってもルーティングテーブルの更新については対応できそうだ。つまり、先ほどの1、2の処理はなんとかなりそうな気がする。

とはいえ、3の処理であるノード「う」が持っているデータを他のノードが引き継ぐのはとても大変そうである。
そこで一工夫する。

今、各ノードの保持しているデータは、隣接ノードにも絶えずコピー(正確には同期)することとしよう。
例えば、ノード「う」はノード「い」とノード「え」にも同じデータのコピーを持っているとする。
すると、例えノード「う」が居なくなっても、そのノード「う」のデータはノード「い」とノード「え」にあるので、データ自体は消去されないということになる。後はルーティングテーブルが復旧すれば、ノード「う」にあったデータはノード「い」でアクセスする事が出来るようになる。

実際のDHTではこのコピーを色々なノードにコピーする事によって、同時に複数のノードがDHTから離脱しても問題なく作動するように設計されている。

分散ハッシュ(DHT)入門その2~その7で簡単にDHTの仕組みについて説明してみた。
Blogに絵がないので少し説明が分かりにくかったかもしれないが、本内容は第2回P2P勉強会で講演する予定なので後日プレゼン資料を作成する。資料が出来次第、ご紹介する予定である。

次回は分散ハッシュ(DHT)入門の最終回。DHTの応用と未来について書いていきたい。

| | コメント (0) | トラックバック (0)

[P2P勉強会]懇親会受付〆切ました。

P2P勉強会の後に行われる懇親会ですが、受付を〆切りました。
多くの方の参加表明を頂き、ありがとうございました!
なお、懇親会の参加者数は50名弱の予定です。

| | コメント (1) | トラックバック (0)

2005.02.06

[Blog]10万ビュー突破!

お蔭様で10万ビューを突破しました!ありがとうございます。
P2Pや音楽を中心にして色々な話題を書いていきましたが、今後はソーシャルネットワークやシミュレーションなどより多様な話題でBlogを書いていきたいと思います。
今後もよろしくお願い致します。
Tomo

| | コメント (0) | トラックバック (0)

[ネットワーキング]分散ハッシュ(DHT)と6次の繋がり

「新ネットワーク思考」という本をご存知だろうか?この本の中に「6次の繋がり」という事が書いてある。
それは、

・ある人とランダムに選んだ世界中にいるある人とは6次で結ばれている

ということである。
例えば、AさんがBさんを知っている場合には1次の繋がり、AさんがBさんを介してCさんを知りうる状況では2次の繋がり、6次となると、A⇒B⇒C⇒D⇒E⇒F⇒Gという繋がりでAがGが知りうる状態を意味する。

なんだか信じられない話だが実際そうらしい。

今回話したい事は、この6次の繋がりをどう説明するか?ということである。
「べき乗の法則」というものがこの6次の繋がりを上手く説明できるそうだ。一般にはほとんどの人が他人と知りうる人はそれなりの数なのだが、少数ながら非常にたくさんの数と知りうる人がいる。それによって、このような6次の繋がりが説明できる、とのこと。(詳しくはあまり知らないのでご容赦を。)
参考:スケールフリー性

ここで分散ハッシュ(DHT)との絡みに持って行きたい。
分散ハッシュでは、あるノードAが他のノードBと連絡できるステップ数は参加者数をNとするとO(log(N))である。
log(N)というは効率的であるが、N=50億人となると、とても平均ステップ数6で知りうる事は大変だろう。
たとえば、logの基底を10としても10^6=1,000,000である。とても50億には届かない。

すると、ここで一つ考え付く事がある。つまり、普通の分散ハッシュでは各ノードについてのルーティングテーブルの大きさがほぼ一定である。これを例えばノードの処理時間や接続時間によってルーティングテーブルの大きさを増減させると、実は検索ステップ数が少なくなるのでは?ということだ。

おそらく人間同士のコミュニケーションでは、知り合いが多い人がハブとなり、それらが絡み合う事により少ないステップ数で人間同士が結ばれるのだ。その原理をオーバーレイネットワークにも持ち込もうということになる。

こうなるとDHTのルーティングの仕方自体もかなり大幅な修正が加えられるはずだが、非常に面白い結果になるかもしれない。

ジャスト・イン・アイデアだが、取り合えずメモ。


| | コメント (1) | トラックバック (0)

分散ハッシュ(DHT)入門~その6

さて、前回はDHTでのルーティングについて説明した。今回はノードがDHTに参加する場合、どうすれば良いのか説明したい。

「あいうえお」DHTで説明しよう。
このときに、ルーティングの方法は前回説明したルーティング3を用いる事にする。
つまり、
ルーティング3:
◇各ノードは各行の先頭ノードを知っている。また、各ノードは隣あうノードを知っている。

これはノード「う」であれば、
・各行の先頭ノード:ノード「あ」、ノード「か」、ノード「さ」.....ノード「わ」
・自分と隣あうノード:ノード「い」、ノード「え」

を知っている事を意味する。

単純な例を説明するため「あいうえお」DHTでノード「う」だけが現在なく、そこにノード「う」が参加することを考えてみよう。

まず、これからDHTに参加するノード「う」は、既にDHTに参加しているノードの一つを少なくとも知っている必要がある。今そのノードをノード「や」としよう。

手順1:
ノード「う」は自分がノード「う」として振舞うためにはノード「い」とノード「え」に対して自分の存在を知らせる必要がある。そのため、まずノード「う」はノード「や」を通して、ルーティング3を使ってノード「い」とノード「え」のIPアドレスを知る。

手順2:
ノード「う」はノード「い」に対して自分の存在を知らせたい。
ノード「い」に対してノード「う」は自分がノード「う」である事を表明し、また自分のIPアドレスを教える。このコマンドを例えば
Join(ノード「う」⇒ノード「い」)
と定義しよう。

ノード「い」のルーティングテーブルは、隣り合うノードの部分についてはノード「あ」とノード「え」であったが、
これが、ノード「あ」とノード「い」に変更する必要がある。
このコマンドをRoutingTable(ノード「い」、NextNode、ノード「う」)としよう。

手順3:
ノード「う」はノード「え」に対して自分の存在を知らせたい。
ノード「え」に対してノード「う」は自分がノード「う」である事を表明し、また自分のIPアドレスを教える。
つまり、Join(ノード「う」⇒ノード「え」)

ノード「え」のルーティングテーブルは、隣り合うノードの部分についてはノード「い」とノード「お」であったが、
これが、ノード「う」とノード「お」に変更する必要がある。
このコマンドをRoutingTable(ノード「え」、FrontNode、ノード「う」)としよう。

手順4:
ノード「う」はまだルーティングテーブルを完全には構築していない。
すなわち、各行の先頭ノードを知っていない。(例えば、ノード「あ」、ノード「か」、ノード「さ」.......)そのため、
ノード「え」に対して、各先頭ノードのIPアドレスを教えて欲しいと要請する。
つまり、
RoutingTableKnown(ノード「う」、ノード「え」、各行の先頭ノード)
となる。

手順5:
各ノードは全てのルーティングテーブルに入っているノードに対して定期的にping等をしてノードが生きているかどうか調べる。

これでノード「う」がDHTに参加することができるようになった。

ところで、DHTではJoinやRoutingTable,RoutingTableKnownの方法については色々と工夫が施され、バラエティに富んでいる。
ただ、いずれにせよDHTのあるノードに対して自分の存在を知らせ、また自分に必要なルーティングテーブルを他の構成することはほぼ共通事項である。

実はこれだけではノード「う」はDHTに参加した事にならない。というのは、ノード「う」が居ない状態では、ノード「い」が頭文字が「う」で始まるデータを管理していたからである。
ということで、

手順6:ノード「い」からノード「う」が管理すべきデータを引き継ぐ

という処理を行う必要がある。
これでノードの参加処理は全て完了である。

次回はDHTからのノードの離脱とそれに対する工夫について説明したい。


| | コメント (0) | トラックバック (0)

2005.02.05

[P2P]分散ハッシュ(DHT)入門~その5

風邪で体調を崩してしまった。風邪がはやっているようなので、皆様も注意して下さいね。
さて、前回はなぜ、分散ハッシュテーブルという名称が使われているのか、その理由を述べた。
今回は「あいうえお」DHTを使ってルーティングの話をしたい。

そもそもルーティングとはなんだろうか?
例えば、ある人が東京から大阪に行きたいとする。今、自動車で大阪に行くとすると、首都高速に乗って高速道路に行く手もあれば、国道や一般道を使ってゆっくり安上がりに行く手もある。このように、あるところから目的にのところまでどうやって行くかを決める手段をルーティングと呼ぶ。

インターネットの場合にはIPアドレスというのがユーザのPCやサーバに割り当てられる。ルーティングはこのIPアドレスを使って、例えばある人が私のBlogをどうやって見ることができるか決める事ができる。ルーティングなしには、インターネットのどんなページも見ることができなくなってしまう。

ところで、DHTでのルーティングというのはどういうことだろうか?
例えば「あいうえおDHT」で自分がノード「あ」だとする。今、「ヤクルト」という情報を欲しい場合にはノード「あ」はノード「や」にアクセスすることになる。このノード「あ」がノード「や」にアクセスする方法がルーティングである。

ではどうやって「あいうえおDHT」はルーティングをすることができるだろうか?
簡単な例を考えてみよう。

◇ルーティング1

各ノードは隣り合った文字のノードの場所を知っているとする。例えばノード「う」はノード「い」とノード「え」を知っているし、ノード「さ」はノード「こ」とノード「し」を知っている事となる。
今、ノード「あ」がノード「「し」を知りたいとすると、 バケツリレーのようにノード「あ」⇒ノード「い」⇒ノード「う」⇒ノード「え」⇒..........⇒ノード「こ」⇒ノード「さ」⇒ノード「し」と言う風になって、通信ができることになる。
でも、この方法はとても通信するのに遅いですよね?

今、各ノードが他のノードを知っている情報の表をルーティングテーブルと呼びましょう。
例えば、ノード「う」のルーティングテーブルにはノード「い」、ノード「え」の各場所の情報(つまりIPアドレス)が入っています。この方法はとてもルーティングするのには遅いのですが、ルーティングテーブルを2つだけ持っていればどんなノードとも通信ができます。

◇ルーティング2
各ノードは自分以外のノードの情報を全て知っているとしましょう。
つまり、ノード「う」は、ノード「あ」、ノード「い」、ノード「え」、ノード「お」,,,,,,,,,,ノード「わ」、ノード「を」ということを知っている事になります。つまりルーティングテーブルの中身は49個のノードの情報が入っています。

もし、この方法であれば、ノード「あ」⇒ノード「し」の通信は、一発でできることがわかりますよね?なぜなら、ノード「あ」はノード「し」の情報を既に知っているのだから。
でもこの方法は事前に49個ものノードの情報を知らないといけないので、その収集することが結構大変そうです。

ルーティング1、ルーティング2とも長所と欠点があります。
つまり、ルーティングテーブルの中身が少ないと、ルーティングに時間がかかるし、ルーティングの中身が多いと、ルーティングの時間が少なくなると言う事です。

では、それなりにルーティングテーブルは少なくて、かつルーティング時間もそれなりに少ない方法があれば便利だと思いませんか?

◇ルーティング3
各ノードは各行の先頭ノードを知っている。また、各ノードは隣あうノードを知っている。
これはどういうことでしょうか?

たとえば、ノード「う」がいるとすれば、このノードは各行の先頭ノードを知っている必要が有りますから、ノード「あ」、ノード「か」、ノード「さ」、ノード「た」.....ノード「わ」を知っているわけです。
それだけでなく、隣接しているノード、ノード「い」とノード「え」も知っています。

今、ノード「あ」がノード「し」を知りたいとすると、ノード「あ」⇒ノード「さ」⇒ノード「し」となりますね?ルーティングテービルの中身も10個程度になり、先ほど実現した、ノードのルーティングテーブルはそれなりに少なく、ルーティングテーブルをそれなりに少ない事が実現されています。

===
ルーティング3の方法は良く考えると、とても面白い方法です。つまり、最初は「行」でざっくりとした場所を検索して、その後は近くなれば場所を詳しく検索すると言う方法です。DHTのChordやPastryなどはこのような方法を使って、ルーティング効率を高めてます。

つまり、DHTの特徴として
-最初は対象ノードについて、おおざっぱに検索して、その後だんだんきちんと検索することによって、早くルーティングができる

ということなのです。
DHTの論文を読むと、ルーティングにユニークな方法が使われているので、びっくりすると思います。興味があれば是非原論文を読んでみて下さいね。

[参考1]
ところで、今回の「あいうえお」DHTでは直接IPアドレスを使ってルーティングを使っていません。ノード「あ」、ノード「い」などの、ノードの情報(あ、い、う、え、お。。。という文字間の距離)を使ってルーティングしました。
つまり、IPアドレスという情報を隠蔽してより抽象的な層でルーティングを行っています。
このようにDHTはIPレイヤーよりも上の層でルーティングしているので、「オーバーレイネットワーク」と呼ぶことがあります。

[参考2]
さてノード間の距離(d)ってなんでしょうか?「あいうえお」DHTでは、ノード「あ」とノード「お」の距離は、どれだけ文字が離れているか、つまりd=4となります。
例えばChordの場合にはハッシュ値Xとハッシュ値Yの絶対値の差、つまりd=|X-Y|となります。これはユークリッド距離と言う物です。しかし、大学の線形代数に習ったように、距離は距離の公理に従えば、いろいろな定義ができます。例えば、DHTのKademliaではd=X xor Y を使ってルーティングしています。

そろそろDHT入門も終盤に差し掛かりました。次回はノードがDHTに参加した時どうするれば良いのか、考えてみます。

| | コメント (0) | トラックバック (0)

2005.02.03

[音楽]指揮者なしの演奏会

通常オーケストラには指揮者がいるものだ。
または指揮者がソリストを兼ねる場合も曲によってはある。(例えばピアノ協奏曲ではピアノが出来る指揮者がそのような場合をすることもある。)

小編成のアンサンブルや弦楽オーケストラでは指揮者がない場合も見受けられる。

だが、この記事はすごい。。
フルネ急病のため都響が指揮者なしで演奏会

大編成のオーケストラの場合、それを纏めるのはとても大変だ。指揮者が居なくて演奏するなんて、ほぼ不可能なぐらい。。
おそらくコンサートマスター(バイオリンのトップが多い)がテンポなどをコントロールしたと思うのだが、相当緊張感のある演奏会だったに違いない。

もうこんな演奏会を聞けることは滅多にないと思うが、一回は聞いてみたいものだ。

| | コメント (1) | トラックバック (0)

2005.02.02

[IT]NET&COMに行ってきました

今日は東京ビックサイトで行われたNET&COMに行ってきました。
隣接会場で大学生のための就職セミナがあったので、ビジネスマンというよりも学生でビックサイトはあふれかえっていました。

ところで、今回展示としてはセキュリティに重みがあるところが多かったです。まずは今年施行される個人情報保護法のための、内部情報漏洩防止のためのソリューションの数々。
全てのファイル操作に対してログ管理をしたり、あるいは外部にファイル漏洩しても暗号化されているために中身が見えないなどのシステムが展示していました。

それよりも気になるのが今話題の検疫システム。

通常のセキュリティソリューションではウィルスが感染した場合にはクライアントソフトがアラームを鳴らして、それによって対処するというのが普通です。検疫システムはそれを一歩先にいったシステムなのです。

まず、ネットワークログイン時には管理セグメントと呼ばれるVLANに一旦入ります。ここで、管理サーバによって、ウィルスソフトのパターンファイルの最新性、Windowsなどのソフトのパッチの更新がされているか、あるいは不要なソフトがインストールされているかチェックします。管理者が定めたポリシーに合致したものだけが通常のネットワーク接続されるというものです。つまり、パスワード&IDが正しくても、PCの状態が適切でないとネットワークに繋がらないのです。

ところで、例えばウィルスソフトのパターンファイルが最新でないときやWindowsのパッチが適切に対処されてない場合にはどうすればよいのでしょうか?この時にはダウンロードサーバから強制的にPCに対してこれらのパッチやパターンファイルがダウンロードされます。その後通常のNW接続ができるということです。
(※ダウンロード中にウィルスやワームに感染しないように、最小限の接続ができるような管理セグメントにあるファイアーウォールを通してダウンロードするようになっています。)

ちなみにこのようなソリューションは一般的に802.1X対応スイッチ+RADIUSで構成されているものが多かったです。
つまりRADIUSやそれに類するサーバによって、収容するPCのポートのVLANを制御しているわけです。

社内への持ち込みPCや勝手にインストールしたソフトによって社内ネットワークが汚染されるケースはよくある事例です。検疫システムはウィルスソフトのように一般化的に認知されるシステムに今後なり得るかもしれませんね。

| | コメント (0) | トラックバック (0)

2005.02.01

[P2P]分散ハッシュ(DHT)入門~その4

前回はDHTとしてハッシュ関数を使う理由を書いてみた。
今回はノード数とハッシュ空間の大きさ、そして分散ハッシュの本質について書いていきたい。

まず、いつものように「あいうおえおDHT」を考えてみよう。「あいうえお」は50音だから、ノードが50個あれば丁度一つの文字に対して一つのノードが対応するわけである。では、ノードが20個ならばそれぞれのノードはどのように管理すれば良いのだろうか?

今、「か」~「さ」行を考えてみよう。「か」行にはノード「か」、ノード「く」、ノード「け」、ノード「す」の4つがあったとする。
それぞれのノードはどの文字を管理すれば良いのだろうか?

このルールは「あいうえおDHT」を作った人にまかされているのだが、例えば次のノードの直前までの文字まで管理すると言うルールにしよう。そうすると、

・ノード「か」は「か」と「き」が始めの文字列のデータを管理する
・ノード「く」は「く」が始めの文字列のデータを管理する
・ノード「け」は「け」、「こ」、「さ」、「し」が始めの文字列のデータを管理する

ということができる。

このように、全てのノードは自分が管理するデータをノード数に応じて「動的に」変化することができる。これはDHTの全てに当てはまる基本だ。
DHTでは、ノードが本来割り当てられているハッシュ値だけでなく、DHTのルールに応じてその付近のデータも管理することになる。そのルールはDHT毎に異なる。

(※ちなみに先ほどの「あいうえお」DHTのルールである次のノードの直前(つまり次のノードのハッシュ値の1つ前)まで管理する方法は実はDHTの代表格「Chord」と全く同じである。)

では話を抽象化してハッシュ空間で考えてみよう。

今、ハッシュ関数Fが0~6までのハッシュ値を取るとする。

◇ノード数が1の場合、そのノードは全てのデータを管理する事になる。
この時全てのデータに関してハッシュ値とそれに対応されたデータの表が一つできるはずである。
このようなデータとハッシュ値を対応した表を「ハッシュテーブル」と呼ぶ事にしよう。
なお、テーブルとは英語で「表」を表わす。

コミックを例に取るとハッシュテーブルとはこんな感じの表になる。

ハッシュ値   ハッシュに対応したデータ
0   ドラえもん
1   ワンピース
2   ドラゴンボール
3   こち亀
4   島耕作
5   マリア様がみてる
6   ジパング

では、ノード数が2の場合にはどうなるのであろうか?
例えば、ノード「0」とノード「2」、ノード「5」の3つのノードが存在する場合にはそれぞれが保持するハッシュテーブルは以下の通りになる。

ノード「0」のハッシュテーブル

  0    ドラえもん
  1    ワンピース

ノード「2」のハッシュテーブル
  
  2    ドラゴンボール
  3    こち亀
  4    島耕作

ノード「5」のハッシュテーブル
  
  5    マリア様がみてる
  6    ジパング

このように「ハッシュテーブル」が各ノードに分散して配置される事になる事が分かるだろう。この技術が
「分散ハッシュテーブル」すなわちDHTと呼ばれることになる。
ようやく語源の理由まで説明する事ができることになった。

今のようにすれば、例えばハッシュ空間が非常に巨大になってノードが数億参加しても同じようなルールで各ノードが分散してハッシューテーブルを持つことになる。

既にピンと来ている人がいると思うが、例えばワンピースのデータが欲しければノード「0」、ジパングのデータがほしければ「ノード5」に問い合わせをすればよい。

ところで、ノード「0」や「ノード5」のノードと通信するにはどうすれば良いのだろうか?全てのノードのIPアドレスを集中管理をするのは大変だ。そこで、ルーティングと言う手段を使って巧妙にこのことを解決している。
次回は「あいうえおDHT」を使ってDHTのルーティングについて触れてみたいと思う。


| | コメント (3) | トラックバック (1)

« 2005年1月 | トップページ | 2005年3月 »