« 2007年11月 | トップページ | 2008年1月 »

2007年12月の3件の投稿

2007.12.22

[P2P]DHTにおける部分一致検索の間接参照による解決法の提案

2007年ももう少しで終わりですね。今年は娘の誕生、P2P教科書の出版、総務省支援のP2P実証実験への技術検討メンバ参加など、プライベート・仕事ともに節目の年でした。

来年もP2Pに関する講演等が決まりつつあるので後ほど紹介致します。

さて、2月末にとある団体が主催によるP2P研究会にて講演を行う予定です。その中でDynamoなどのP2Pデータベースの話も触れたいので、少しずつネタをBlogに書いておこうと思います。仕事でP2Pに関する業務が正式に認められましたが、アイデアベースで出せるものは今後もBlogで公開したいと思いますので皆様のコメントを是非お寄せ下さい。

□部分一致検索とDHTの親和性
DHTはご存知の通りハッシュ関数を使います。通常使うハッシュ関数は暗号的ハッシュ関数といわれるもので、これはハッシュ関数H()においてH[A]=Bというときに、BからAを推定できない性質があります。もう少し噛み砕いて言うと、Aにちょっとだけデータが変化したA'とすると、H[A']=B'という値が出力しますが、BとB'は全然違う値になります。

つまり、暗号的ハッシュ関数を使うと完全一致検索は容易ですが、部分一致検索は非常に難しいという事になります。

□部分一致検索への模索
ではどのようにすれば部分一致検索が可能なのでしょうか?
私のBlogでも何回か提案しました。スマートな方法の一つが形態素解析を使う事です。形態素解析を使う事で、文章から単語を抽出して単語ベースでの検索可能とします。

[DHT]DHTによるデータの部分列検索の考察
SkipGraphを利用した部分一致検索の提案

この方法の欠点は形態素解析用の辞書を持つ必要があることです。このため、新しいキーワードに対して検索するのは難しい事が予測されます。(ただし形態素解析自体の技術が向上しているので、この課題は解決できるかもしれません。)

他のアイデアとしては暗号化ハッシュ関数ではないハッシュ関数を使う事です。それは例えばハッシュ関数に線形性を持たせる事です。このようにすることで、あるキーワードKに対して、H(K)=Dとすれば、Dに近いハッシュ値に関連付けられた情報を引っ張る事でキーワードをある程度検索できるかもしれません。ただし、この方法ではキーワード数とハッシュ空間の大きさを慎重に吟味する必要があるでしょう。私は単純なハッシュ関数ではなく、Bloom Filterを使って解決を模索したことあります。先ほど紹介した[DHT]DHTによるデータの部分列検索の考察もBloom Filterを使っています。

どちらの方法にしてもオーバーレイマルチキャストを使う事で、効率的な検索ができることが期待されます。

さて、いずれ方法にしても複数のKeyに対するValueにはデータをそのものを格納していました。ということはかなりの数のノードにデータのレプリカをする必要があり、ノードのストレージに対して相当の負担がかかります。

□DHTにおける間接参照の導入

そこで、DHTにおける間接参照を導入します。
先ほど書いたように今まではKeyとして検索するキーワード、Valueとして検索対象のデータそのものが入っていました。そこで、新たな方法としてValueに格納するものを検索対象データへのポインタとします。

このとき、Get(Key=P2P)とすれば、Valueとして、P2Pという文字列を含むデータへのポインターのリスト(具体的にはデータのハッシュ値)帰ってきます。そこで、実際のデータにアクセスしたければ再度DHTを使ってデータを取得すれば良いのです。

この方法でもAND検索やOR検索も容易です。なぜなら
Get(Key=P2P AND KEY=DHT)=GET(Key=P2P) AND GET(Key=DHT)
Get(Key=P2P  OR KEY=DHT)=GET(Key=P2P) OR GET(Key=DHT)
だからです。

ノードにはポインターの情報が色々とばら撒かれますが、そもそもデータそのものではないので、今までの方法よりもノードに対する(ストレージ的な)負荷は下がると予想されます。そのかわり、実際のデータにたどり着くまでの時間や信号数は増えます。

□通常の検索システムへの置き換えへ

ポインターを導入する事で、ノードへのストレージ負荷を大幅に下げる事に成功しました。となると検索としてわざわざ形態素解析を導入しなくても、通常の検索システムで使うNグラム法でOK!ということになります。これなら通常の検索システムのソースを使ってDHTに簡単に移植できるかもしれません。

全文検索-Wikipedia

□来年に向けて
今考えているのはDynamoのようなP2Pな分散データベースで、どのような適用範囲なら使えるか、あるいはどのような実装なら容易に実現できるかということを考えています。データベースはあまり詳しくないのですが、そのうち講演等でディスカッションさせて頂ければと思います。

今後の予定ですが、
・1月18日:吉田鎌ケ迫へのオフィスツアー
・2月末:P2P研究会で講演(P2Pのアーキテクチャと最新動向について)
・3月上旬:信学会の研究会で招待講演(P2Pのアーキテクチャとユビキタスとの関連)
・3月中旬:信学会の全国大会で講演(NAT越え)

となっています。業務でP2Pの研究会開発が正式に認められたので今まで以上に活動できそうです。また私への講演や技術打ち合わせを御検討されている方はお気軽にメールかMixi経由でご連絡下さい。




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

2007.12.16

VoIP Conference 2008 開催概要&参加者募集のお知らせ

VoIP Conference 2008開催のご案内

2007年1月に開催して大好評だったVoIP Conference 2007ですが、参加者による強い要望により2008年2月に再度開催することが決定しました。プログラム概要、参加募集方法は以下のとおりです。

☆VoIP Conference 2008概要☆

◇開催主旨:恒例のVoIP(Voice Over IP)技術に関する研究会を下記にて開催します。活発な議論をお願いします。今回は,VoIP Next Generationに関し、次世代のフレームワーク、伝送技術、ネットワークアーキテクチャに関する議論を中心に行いたいと思います。ふるって御参加を お願いします。

◇日時:2008年2月8日(金) 10:00~17:30(終了予定)
◇主催者:VoIP Conference 2008 実行委員会
◇協力:情報通信研究機構 新世代ネットワーク研究センター
◇場所:東京都小金井市貫井北町4-2-1
    情報通信研究機構 小金井本部 4号館大会議室
    http://www.nict.go.jp/about/hq.html

◇参加者定員:100名
◇参加費:1000円(ボランティア等協力スタッフは無料)

◇講演スケジュール

2/8(金)
9:00~ 準備開始(ボランティアの方は9:00に会場集合)
9:30~ 開場
10:00~10:10 開会の挨拶

10:10~10:40(質問10分含む) 
「VoIP最新動向 VoIPの次を考える」
VoIP Conference 2008 実行委員長 西谷 智広

2007年を振り返るとSkype携帯やP2PSIP-WGなどVoIPの既存の枠組みを超えた新たな動きが見られる
ようになりました。本講演ではVoIPの最新動向を解説すると共にVoIPの今後の方向性について議論します。

10:40~12:00(質問10分含む) 
「VoIPとSIPとNGN」
KDDI株式会社 澤田 拓也

日本だけでなく世界的にもVoIPとSIPによる音声通信網のマイグレーションが現実的になっている。NTTグループによるNGNを念頭に置きながら、この流れを概観するとともに、NGNの特長を踏まえて今後の通信インフラとサービスの可能性について議論していきたい。

13:00~14:00(質問10分含む)
「NGN/IMS時代のWebアプリケーション開発」
~クライアント間マッシュアップ用UA Servletアプリケーションサーバ
「雷電」の紹介とデモ~
SIPropプロジェクト代表 今村謙之

SIPropプロジェクトにおいて開発中の「雷電」とは、Webのようなクライアント-サーバ間通信だけでなく、VoIPのようなクライアント間通信も、考慮されたアプリケーション用の基盤ソフトウェアである。
これについて、なぜ、このような基盤ソフトウェアが必要であるのか?という思想や背景どのような設計となっているのか?という設計や実装どんなアプリケーションが開発できるのか?というデモという、
3つの視点から解説する

14:10~15:00(質問10分含む)
「ストリーミングアプリケーションのQoS制御に関する理論的一考察」
東京工業大学 大学院理工学研究科 准教授 山岡 克式 

VoIPやビデオストリーミングの通信品質(QoS)を安定維持するためのQoS制御も,通信状況によっては万能ではなく,通信品質を維持できな い状況が発生しうる.本講演では,特にQoS制御として一般的である優先制御を対象として,そのような状況の発生する条件を,なるべく複雑にならないよう 心がけながら,理論的な観点から考察する.

15:10~16:10(質問10分含む)
「オープンソースPBX Asteriskの現状と将来」
日本Asteriskユーザ会、Asterisk関連書籍著者 高橋 隆雄

ようやく日本でも知名度が上がってきたAsteriskだが、日本における問題点はどの程度解決しているのかや、日本独自の取り組みはどうなっているかなどの現状を解説。また今後Asteriskはどうなるのか?も俯瞰する。

16:20~17:20(質問10分含む)
「P2P通信技術:NAT越え」
~STUNとUPnPと、時々、TURN~
株式会社コナミデジタルエンタテインメント
プロジェクトソリューションセンター R&D推進グループ 佐藤 良

VoIPやオンラインゲームでP2P通信する時に必ず問題になるのが、ブロードバンドルータのNAT(Network Address Translation)機能です。
NATとは何かから、NAT越えで何が問題になるのか、どのように解決するのかを解説して、最後にコナミのオンラインゲームでの導入事例をご紹介します。

17:20 閉会の挨拶

◇募集方法
Mixiの参加者募集トピックから参加申し込みをお願い致します。
http://mixi.jp/view_event.pl?id=26127658

なお、ボランティアの募集については別途御連絡致します。

◇懇親会について
懇親会を開催予定です。詳細は別途御連絡いたします。

皆様のご参加をスタッフ一同お待ちしております。

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

2007.12.10

P2P教科書は12/26(水)に発売です!

先日からお知らせしているインプレスR&DのP2P教科書がいよいよ12/26(水)に発売されます!東大 江崎先生が監修しています。376Pというボリューム満載の一冊です。

Amazonで既に予約を受け付けています。興味のある方は是非予約を!

詳細情報はインプレスダイレクトのページから見れます。
インプレスダイレクトのページ

目次は以下の通りです。
本書へのメッセージ
「ピア・ツー・ピアとBitTorrent」
ブラム・コーエン(Bram Cohen)、ビットトレント、チーフ・サイエンティスト(BitTorrent Inc., Chief Scientist、BitTorrent 開発者)

「ピア・ツー・ピアは幅広い応用の可能性をもつ」
金子 勇(Isamu Kaneko)、(株)ドリームボート、技術顧問(Winny制作者)

第1章 Q&Aで学ぶP2P(ピア・ツー・ピア)の基礎知識

第2章 P2Pの歴史と発展
= 合法的なビジネス活用に進展したP2P技術 =

第3章 著作権の現状とP2Pにおける著作権侵害の課題
= 諸外国の裁判内容からWinny事件まで =

第4章 P2Pのアーキテクチャの分類とその応用例

第5章 構造化オーバーレイとP2Pアーキテクチャの研究動向

第6章 CDNシステムとP2Pシステムはどこが違うのか?
= Webサーバの基本動作からCDN/P2Pまで =

第7章 Winnyをベースに商用化されたコンテンツ配信システム「SkeedCast」

第8章 P2Pに関するコミュニケーション・システム
= SIP/P2P SIP、IMSの仕組みからSkypeまで =

第9章 実例で学ぶP2P型マルチキャスト技術
= オーバーレイ・マルチキャスト方式の「BBブロードキャスト」 =

第10章 モバイル(携帯電話)におけるオールIP化とP2Pへの展開
= PHS/無線LAN/WiMAXなどもP2Pへ =

第11章 P2Pアプリケーションのインターネット・トラフィック特性への影響

第12章 P2Pによる新ビジネス・モデルと商用サービス

12-1 P2Pによる新ビジネス・モデルの展開事例
= デジタルミュージシャン・ネット(DMN)/Joost/FMO/orz(がっくし) =

12-2 P2Pによる商用ファイル配信サービス「BitTorrent DNA」

私が取りまとめ(一部執筆)を担当したのは3章で、うち2章はP2Pアーキテクチャの説明、残り1章はコミュニケーション関連(SIP、IMS、Skype)となっています。今回のP2P教科書を執筆する上で、初期メンバとして目次作りから関わる事ができ、大変貴重な経験ができたと思います。

とりまとめ+執筆した章:

第4章 P2Pのアーキテクチャの分類とその応用例
第5章 構造化オーバーレイとP2Pアーキテクチャの研究動向

第8章 P2Pに関するコミュニケーション・システム

特に構造化オーバーレイの説明には力をいれ、おなじみのP2P勉強会講師陣メンバやUNIX Magazine P2P特集執筆者によるChord,Pasty,Kedemlia,Skipgraphの説明、Overlay WeaverやPlanet lab、複雑系との関連の記事など最新動向も踏まえた内容となっています。ページ数の関係上、深く入れなかった部分が多々ありますが執筆陣による渾身の章となっていますので是非ご期待下さい。

思えば用語の定義、章内の目次、執筆陣の決定、スケジュール管理等非常に難しい調整が続きましたが、ようやく形になる事ができてホッとしています。私のP2Pな人生にも一つの区切りができたと思います。

是非ご覧になったら感想をお寄せ下さい。次回の改訂版リリースや講演時の参考とさせていただきます。

最後になりましたが、監修の江崎先生、編集部の皆様、執筆陣の皆様、草稿を読んでコメントを頂いた方には大変お世話になりました。この貴重な体験を今後のキャリアアップに活かしたいと考えています。

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

« 2007年11月 | トップページ | 2008年1月 »