koie blog : FRT

第二十四回P2PSIP勉強会にいってきた。場所はいつもの首藤研ではなくギークハウス武蔵小杉。(天気が雨で風も強かったので行くかどうか実はちょっと迷った)

@did2memo 「FRTに基づくルーティングアルゴリズムデザイン」

DHTの説明があったあと、経路表がIDしか考えてないのは制限がきつすぎるよねーという問題提起。そもそも経路表はいろんなのがあるはずで、DHTはノード数Nに対して経路表のエントリ数がO(log N)になる経路表の集合のなかの1つにすぎない。そこでIDだけで決めるのをやめるにはどうすればいいかという話に。

そこでFlexible Routing Tables (FRT)の提案:

ルーティングアルゴリズムに合せて ≦ID という経路表を比較する演算(小さい方が良い経路表を定義して

1. 到達性保証操作(最低限の保証)
2. エントリ学習操作 (知ってしまったエントリをどんどんつっこむ)
3. エントリ厳選操作エントリを削ったときに ≦ID 的にもっともよくなるように。

1→2→3→2→3→のように1を保証した上でエントリを増やしたり減らしたりすることで次第に最適な経路表になるというしかけ。

具体例としてFRT-Chordの説明があって、最低限のエントリを経路表につっこんだ上で、短縮倍率 = HOP後の残りID距離 / HOP前の残りID距離 (距離というのはID空間での距離) を定義して、経路表の中で短縮倍率が最悪(最大)なものを経路表の短縮倍率として≦IDを短縮倍率の大小比較として定義することで、短縮倍率が均等な経路表ができあがるということであった。

単純にエントリ数を増やせばどんどん短縮倍率は小さくなってゆくが、増やしすぎるとノードダウンで経路表を再構築するコストが増えてくるので、適当なサイズがあるのではないかということであった。

[2011-04-30追加]

@kumagi 「範囲検索の一貫性」

前提条件としてISPをまたがるようなネットワークではなくてデータセンターのようなall-to-allができる環境を想定。

範囲検索を分散してスケールさせるために一貫性と耐障害性を確保するにはどうすればよいかということで、

KVS(キーバリューストア)が耐障害性を担保して
その上に分散ハッシュテーブルをのせて
さらにその上にSTM流のトランザクションをのせて
自由なデータ構造を構築できる

という方向らしい。

STMでアトミックな更新を実現する構造(おれおれメモ)

struct Variable {
    struct Locator* locator;
};
struct Locator {
    T* old;
    T* new;
    Owner* owner;
};
struct Owner {
    enum { COMMIT, ACTIVE, ABORT } state;
};

[2011-04-30追加]

範囲検索の一貫性

@did2memo 匿名掲示板の開発

wikileaksみたいなに属人性(特定の個人が単一障害点になる)のはマズい。

そこで受信者ではなくて送信者を隠せるようにして匿名の情報提供ができるようにしたい。

その手法として

つねにあやしい送信をつづけることで情報発信を隠す
- このため大きなファイルを送信することはできないという制限あり
2つのパケットを待ち合わせてから転送することでパケット間の相関をなくす
chordで大きくジャンプすると発信者の可能性が高くなってしまうのであえて効率を無視して小さくジャンプするとか。
- token ringっぽいね。

しかしこのようなソフトウェアが一般化してしまうと「道端に包丁を置くようなもの」になっていまい問題があるとして、採択はされなかった。いまのところこのようなソフトを必要としているのは中国の人権団体くらいらしいが、他にいい応用例はないだろうか?とのこと。

@nekomatu 実世界とオンラインサービスと融合するためのオーバレイネットワーク構築手法

人間か感じる範囲に限定した通信というのを考えている。いってみれば観光地のゲストノートみたいなもの。人が集まっているときは安定していて解散するとネットワークが消えるイメージ。似たようなものにiDovatterやNintendoDSのすれちがい通信などがある。会場でのブレストでは以下のような意見がでた:

加速度でクラスタリング列車特定
環境音で場所特定

@ohnishim 災害ネットワークのはなし

メッシュネットワークはリンクがいっぱいあるので分断するのがとっても難しい。
低レイヤはスケーラビリティがない。
災害時は上のレイヤ(ネットワークやDB)は使えなくなる。
ロケーターの広告が重要。
リンクはしょちゅう切れるので、そのたびにフラッディングするとルーティングテーブルが安定して組めない。
世の中ではノードをクラスタリングして代表ノードだけにすることでネットワークを小さくして回避している。
そもそも離散グラフをベースにすると広告の量がへらせないという問題! (これ重要、らしい)
ジオメトリックルーティング (グリーディルーティング)
- 位置情報をベースに近づく方向に転送する。
- でも袋小路に嵌り込む危険性がある。
そこでドロネーグラフ!
- なんでも三角にしちゃう。
- 基本中の基本らしい。
- 三角にならないなら足りないリンクをトンネルでつくっちゃう。
世間でおこなわれているルーティングを安定させる方法は
- 品質をあげる
- 帯域をあげる
もういっかいさがす
- L2はtreeを決めたらそれをずっとつかいつづける
- P2Pはちかくまでいったらしらべなおす
  - ちかくという概念がむつかしい
  - 離散グラフで「方向」という概念はむつかしい
宛先をかきかえてしまうのもある。コンテントベースルーティング。
世の中の論文でヒューリスティックを試してみました!これだけ改善しました!論文が多すぎる。こんなのは終わりがない。こういうのを書いてる奴はいったい何考えてるんだろうか.

本格カレー

懇親会をキークハウスでやることになって、@kitaindia さんがつくってくれた。
ふつうのトマトカレーとマスタードの種入り大根カレー
- ちょっと辛め
- 香辛料がしっかり

グダグダタイム

binary XML のメリット
- 小さくなる
- あいまいさがなくなる

高専卒で就職
- 推薦がほとんど。自由応募はほとんどなし。企業側が推薦を受け入れるのは辞退されないという側面もある。
- リーマンショック後、ほんとにきびしい。数字にでてる。

なんでSIになりたい学生が多いんだろうか
- かっこいい金融系SIの例
  - 「おれがトランザクションをロックしてあるあいだに逃げろ!」
  - 「一貫性がくずれるぞ!」
  - 「abort!」「abort!」「abort!」

社会人ドクター
- 時間の問題。働きながら研究の時間をつくるのはたいへん。
- 修士のテーマがそのままつかえない。
- 留学で一気に仕上げる方がいいかも。

成田空港で景気がわかる
- 不景気になるとスルスルに。

大西さんはカードゲーム収集家
- ドイツ人は同人誌をつくるノリでボードゲームをつくって毎年アワードをきめている。
- なぜか鞄にカードゲームがいくつも入っている。
- 「はやぶさ君の冒険」がはじまる。
  - 勝ち負けがない。ゲームとしてはめずらしい。
  - 結局、地球に帰還できなかったようだ。プレイ時間は1時間ほど。