情報科学屋さんを目指す人のメモ

方法・手順・解説を書き残すブログ。私と同じことを繰り返さずに済むように。

Basho Japanにて構造化オーバレイアルゴリズムGFRT-Chordの仕組みを解説してきました

P2P (6)

Basho Japanにて、私の提案アルゴリズム GFRT-Chord (P2P由来のルーティングアルゴリズム)の詳細を解説してきました。

アルゴリズムに興味がありましたら、説明に伺えるかも知れません。声をおかけください(知り合いか知り合い経由に限る)

Basho Japan 入り口

GFRT-Chord

GFRT-Chordは、構造化オーバレイと呼ばれるP2P型ネットワークを構築するアルゴリズムのひとつであり、あらかじめマシン群をグループとして指定しておくと、グループをまたぐ回数が削減されるように経路を構築する特長があります

この特長により、一般的な構造化オーバレイアルゴリズムの問題である、スイッチやISP、データセンターをまたぐ通信の増加を大幅に抑制します。そしてその特長は証明によって裏付けられています。

このとき、GFRT-Chordでは経路表サイズを任意に増減可能であり、ノード数が少ない状況においても効率の良いルーティングが可能で、さまざまなサイズのネットワークやグループ数に対応することができます。

例えばシステム構築直後の小規模なネットワークや、グループの数が極端に多い(少ない)状況においても安定して性能を発揮することができます。あらかじめグループ数やノード数を知る必要が無く、未知で構いません。

ScalarisとGFRT-Chord

GFRT-Chordは、オープンソースのキーバリューストアScalarisに実装されており、公開されています(自分が実装したのではなく、気が付いたら実装されていました)。

ScalarisのWebサイト

Basho Japan訪問のきかっけ

昨年末、研究室にBashoの方々をお招きして、お互いに発表し合う技術交流会を開催しました。

そのとき、自分に割り当てられた発表時間がとても短くなってしまい、アルゴリズムの仕組みをほとんど紹介できなかったのですが、@itawasa さんが興味を持ってくださって、Basho Japanのオフィスにて、アルゴリズムを細かく解説できることになりました。

Bashoは、RiakというKVSを開発しています。Riakの場合、構造化オーバレイと通常呼ばれるものそのものを利用しているわけではありません。しかし、構造化オーバレイの特殊な場合を利用していると考えることができ、GFRT-Chordはちょうどその特殊な場合と、通常の構造化オーバレイとの間の橋渡しができるようなアルゴリズムです。RiakとGFRT-Chordはそんな関係にあると言えます(あえて言えば)。

Basho JapanにてGFRT-Chordを紹介

こんな経緯で、Basho Japanオフィスにお邪魔してきました。

プレゼンテーション@Basho Japan

2時間程度かけて、構造化オーバレイのあまり説明されることのない基本的な特徴・性質から、GFRT-ChordのベースになっているFRT-Chordアルゴリズムの詳細、GFRT-Chordそのものの仕組みや挙動について説明しました。

普段はなかなか話すことのない、アルゴリズムの細かいところまで話すことができました。アルゴリズムの詳細な動作を、かなりしっかりと理解していただけたようで大満足でした

basho-mug-and-ball

アルゴリズムの詳細に興味がありましたら、説明に伺えるかも知れません。声をおかけください(知り合いか知り合い経由に限る)

このアルゴリズムは、今週末に開かれる情報科学若手の会冬の陣2014というイベントでも発表する予定です。発表時間の都合上、概要を話す程度になると思います。

おまけ

別にそういうわけじゃ(笑

参考

すごく古いスライドですが、一応スライドがあります(GFRT-Chordという名前にする前でLFRT-Chordという名前です)。

論文は「Flexible Routing Tables: Designing Routing Algorithms for Overlays Based on a Total Order on a Routing Table Set」で検索してみてください。個人ページで無料DL可能にしてあります。

コメント(0)

新しいコメントを投稿




  • カテゴリ ナビ
  • 著者紹介

    ブログが趣味で、 月間1,000万PV を達成しました。

    自分が困ったことをブログに書けば、次に困る人の参考になって、みんながみんな同じ苦労をせずに済む、というのが原点です。

    最近の関心は、スマホやパソコンに詳しくない人の行動や思考、 そしてそんな人を手助けする方法や枠組み。 また、それに関連するような、"身近な"セキュリティ。

    ※SNS(特にTwitter)でシェアされた記事は、内容の追加・更新を行っています。 必ず、ではありませんが、気に入った記事は積極的にシェアしてみてください。

    RSS | Facebook | Twitter | About