探索技術

フラッディング

隣接するノードに次々と探索クエリを発行、やりとり

→何も工夫をしないと、探索クエリで帯域を占領してしまい、肝心のファイル交換に支障をきたす

 

工夫1 探索結果のキャッシュ化

工夫2 TTL(TimeToLive)の設定

以下の論文を参照

Revisiting the TTL-based Controlled Flooding Search:Optimality and Randomization

http://www.google.co.jp/url?sa=t&source=web&cd=1&ved=0CBwQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.58.5350%26rep%3Drep1%26type%3Dpdf&rct=j&q=flooding%20time%20to%20live&ei=dAXnTenXOITuvQPIvsD-DQ&usg=AFQjCNGG3c68Rv4c86CzV9Sp4yUcrU_lVg&cad=rja

 

ABSTRACT
In this  paper we  consider  the  problem of  searching  for  a node or an object (i.e., piece of data, ?le, etc.)  in a large network.

Applications of this problem include searching for a destination node in a mobile ad hoc network,  querying for a piece of desired data in a wireless sensor network,

and searching for a shared ?le in an unstructured peer-to-peer network.

この論文で、我々は巨大なネットワークから一つのノードやオブジェクトをどのように探し出すべきなのかを述べることにする。

この問題を抱えているアプリケーションはアドホック(P2Pテクノロジ-基礎1参照：一過性の物)な関係にあるうちのなかから目的のノードを探し出すもの、

無線センサのネットワーク上においてほしい情報の断片を求める物、そしてP2Pネットワークにおいて共有ファイルを探し出す物も含む。

 

We limit our attention in this study to the class of controlled ?ooding search strategies where query/search packets are broadcast and propagated in the network until a preset TTL (time-to-live) value carried in the packet expires.

今回はパケットのTTLの期限が切れるまで、クエリ/探索のパケットが送信され、伝搬していくフラッディング検索戦略の類にのみ焦点をあてて考えていくことにしましょう。

Every unsuccessful search attempt results in an increased TTL value (i.e., larger search area) and the same process is repeated.

検索が失敗するときはTTLの値の増加や同じ処理を繰り返すことを試みる。

 

The primary goal of this study is to derive search strategies (i.e., sequences of TTL values) that will minimize the cost of such searches associated with packet transmissions.

この研究の目的は検索のパケットによって送受信のパケットが最小のコストになるような探索戦略を得ることである。

 

The main results of this paper are as follows.

この論文では結果は以下のようになる。

 

When the probability distribution of the location of the object is known a priori, we present a dynamic programming formulation with which optimal search strategies can be derived that minimize the expected search cost.

もし目的のオブジェクトの流通している可能性のある場所を経験的に知りうるとき、私たちは最小の探索コストで、ダイナミックな策定によって最適な探索戦略を示すことが出来る。

 

We also derive the necessary and su?cient conditions for two very commonly used search strategies to be optimal.

我々はさらに、探索戦略を最適にするために使う2つの非常に共通している必要十分条件を得る。

 

When the probability distribution of the location of the object is not known a priori and the object is to minimize the worst-case search cost,we show that the best strategies are randomized strategies, i.e.,  successive  TTL  values are  chosen  from  certain probability distributions rather than deterministic values.  

目的のオブジェクトが流通している可能性のある場所を経験的に知りえないとき、また、目的のオブジェクトが小さすぎて検索コストが最悪になるとき、我々は最良の戦略としてランダマイズされた戦略を提案する。TTLの値は決定的な値よりも配布物の可能性を重視して決定される。

 

We show that given any deterministic TTL sequence, there exists a randomized version that has a lower worst-case expected search cost.

我々は既に決定されたTTLシーケンスを示す、その中にはランダマイズされたものもあって最大のコストを消費してしまうケースがより少ない。

 

We also derive an asymptotically (as the network size increases) optimal strategy within a class of randomized strategies.

我々はさらに、ランダマイズされた戦略により、漸近的に最適な戦略を得ることを示す。

 

車車間通信に適したフラッディング

フラッディングとは、送信したいパケットをブロードキャストにて電波到達範囲内の全ノードへ送信し、受信したノードが再びそのパケットをブロードキャストすることを繰り返すことで、ネットワーク内の不特定ノードへ同一情報の配信を行うものである。

不特定ノードへ送信するのではなく、自身のルーティングテーブルに載っていない特定のノードへ送信するために利用することもある。

この場合は、目的のノードに届いたら、そのノードは転送をしない。また、TTL（Time To Live）にて転送回数を制限することもある。

フラッディングでは、新しいパケットを受け取ったノードは、必ず１度だけブロードキャストして近隣ノードへ転送することになる。

近隣ノードが全て受け取っていたとしても、それを認識することができないからである。

フラッディングされるパケットには、送信元ノード ID とシーケンス番号のような、他のフラッディングパケットと区別できるようなデータが入れられており、受け取ったノードはこの情報をローカルで保存しておく。

この情報を用いて、ノードが同一内容のパケットを２度目以降受け取った場合には転送はしない。

 

Design of P2P Communication System with using Flashより抜粋

工夫3 検索対象の工夫

データ構造の工夫。

EX.オブジェクト一つ一つではなくて、オブジェクト群のようなものを定義しておき、その群のリストに対してクエリを発行する。

 

分散ハッシュテーブル

従来の探索技術の限界

・インデックス鯖の利用/フラッディング・・・利用者増加により、検索クエリの増大による、ファイル転送帯域の減少。

 

分散ハッシュテーブル(DHT)・・ハッシュ値とデータの存在する位置(ノードのハッシュ値)とのマッピングが行われる。

・データとデータの保存場所のハッシュ値の組

・インデクスノード同士、近いハッシュ値のものを登録先として選ぶ。

・探索要求ノードも同じように近いハッシュ値のインデクスノードに投げる。投げられたノードになければ、そのノードも同じようにハッシュ値の近いインデクスノードに投げる。

・これを繰り返すことにより探索範囲が1/d(dは2以上)になる。

→フラッディングのように発散することがなく、効率的に探索が行える。

→インデクスを分散してもつことで安定性を保っている。

→クエリをダイナミックに処理することでアドホック性も担保されている。

Emacsの利用 -とりあえず初心者ページ見てみる-

ここね

右も左も分からないの、とりあえず初心者ページを覗いてみる。

まあ、言葉の定義は大事だろう。基本的にGNUのものだからWindowsで使うことは想定してないみたい。

なんかやたらにターミナルって言葉出てくるしｗ

 

まあ、その辺は噛み砕いてどんどん前に進もう。

 

・なんかEmacsにはモードなる状態があるらしい。大学のPCがMacなので分かるのだが、たとえばWindowsではExcelを立ち上げても、タスクバーにはExcelが立ち上がってるよという物しか表示されないが、Macではアクティブなソフトのメニューバーみたいなのが表示される。言葉で言っても分からないだろうから、画像を見てくれ。(画像でも分かりにくいがｗ)

 

どうやらEmacsはなにやら色々な機能があって、Macみたく、その機能ごとにメニューバーが変わるらしい。

 

>エコーエリア

>Emacsの画面の最も下に位置している部分が``エコーエリア''と呼び，Emacsからのメッセージや問い合わせを表示する．また，エコーエリアは``ミニバッファ''とも呼ばれ，コマンドやコマンド引数などのユーザからの入力を受けつける．

 

だって、抑える基本的知識はこんなモンかね？

 

とりあえず、メニューバーのしたの方にある、白紙のアイコンをクリックして新規作成する。

 

 

なんかフォントが霞んで見える。こんな事言ったら某所のフォント隔離病棟の患者に怒られるだろうけどｗ

かく言う俺もコレクターとして潜ってはいるのですが・・・

上の状態ではまだ保存していないので、横のメモ帳の中身は真っ白ですが・・・

 

 

保存すると当然こうなる、キチンと日本語も文字化けすることなく保存できるし、コピペも出来るようだ。

 

基本的なカーソルの移動

	C-p ↑
C-a← C-b←		→C-f →C-e
	↓ C-n

キー操作

M-b
カーソルを左の単語(文節)に移動

M-f
カーソルを右の単語(文節)に移動

M-a
カーソルを段落の先頭に移動

M-e
カーソルを段落の末尾に移動

 

Mってなんだよ死ねよと思ったら、どうやらMETAキーという物らしい、

こいつは早い話がShift+Altのことらしい。

 

Emacsのモードラインの左端が，次のように`[-]'になっている状態をたまごの透過モードと呼ぶ．

[--]-J:**  *scratch*         (Lisp Interaction)--L1--All----------

 

良く解らんが、起動させたときはそうなってるらしいから安心しろ。

んで、英語は入力できるのだが、日本語は入力できない。日本語を入力するときにはCtrl+\を押す。

これで日本語は入力できるようになるのだが、この変換ソフトがIMEもびっくり、超弩級のアホで使い物にならない。

したの画像は「美味しい」を変換させた物。

 

 

候補にすら上がらない。これでは使いものにならないのでどうにかしなくてはならないが、今はどんどん前に進むことにしよう。

統計学入門2

4.基準値と偏差値

1.基準化と基準値

同じ点数でも偏差値が違う？

→ 同じ点数でも点数の価値が異なるから

→ 例えば平均からの離れ具合が異なるとか

 

では、平均が同じで、同じ点数でも偏差値が異なる

→ 標準偏差が異なる

→ 標準偏差が小さいほどデータの散らばり具合が小さいわけだから・・・

標準偏差が小さいほど1点に重みがあると言える

 

以上、しかし点数を比較するのはめんどくさい

→ 基準化(標準化)

基準値 ＝ ((個々のデータ) - (平均)) / 標準偏差

2.基準値の特徴

基準化で出した基準値には以下の特徴がある

1.満点が何点の変数であろうとも、その基準値の平均は必ず0，標準偏差は必ず1

→ 100点満点のテストでも、200マン電のテストでも比較できる

2.どのような単位の変数であろうとも、その基準値の平均は必ず0、標準偏差は必ず1

→ 打率とホームラン数など、単位の違うものでも比較できる

基準値が大きいほど点数に価値がある事になる。

 

3.偏差値

偏差値 ＝ 基準値*10+50

1.満点が何点の変数であとろうとも、その偏差値の平均は必ず50、標準偏差は必ず10である

2.どのような単位の変数であろうとも、その偏差値の平均は必ず50、標準偏差は必ず10である

 

4.偏差値の解釈

偏差値 ＝ 基準値*10+50 ＝ (個々のデータ-平均)/標準偏差 * 10 + 50

 

平均と標準偏差が一致していない限り、二つの偏差値は比較できない

偏差値を求める際の平均と標準偏差のでtどことが異なると単純には比較できない

 

◆ まとめ ◆

・基準化は、平均からの離れ具合やデータの散らばりの程度を元に、データの価値を検討しやすくなるデータ変数である。

・基準化を行えば

・満点が異なる変数の比較

・単位が異なる変数の比較

が可能になる。

・基準化されたデータは基準値と呼ばれる

・偏差値は、基準値を応用したおものである

花咲くいろは-治郎丸さんのあの小説の自分なりの保管

この概要は表示できません。投稿を閲覧するには ここをクリック してください。

統計学入門

統計学ってどういう分野に使われているのか

内閣支持率・・・すべての国民に意見を聞くことは不可能

→ そこで人数を絞って調査する(本当の集団：母集団、母集団から抽出された集合：標本)

EX.母集団：有権者全体など

標本から母集団の様子を知る＝統計学

 

§1.データの種類

1.カテゴリデータ、数量データ

計測できるデータ？出来ないデータ？

→ 測れないデータ：カテゴリーデータ、測れるデータ：数量データ

EX 身長は数量データ(間隔が等しい)、英検の級はカテゴリーデータ(間隔が等しくない)

EX 気温：数量、出身県：カテゴリ、柔道の段位：カテゴリ、体重：数量、発行部数：数量、天気：カテゴリ

◆まとめ◆

・ データは数量データとカテゴリデータに分類される

・ カテゴリデータを実務では数量データとして扱うこともある。

 

 

 

§2.データ全体の雰囲気 -数量データ-

1.度数分布表とヒストグラム

ラーメン屋とその価格

→ 生のデータでは値段がバラバラ、数字の羅列だけで全体の把握が困難

→ 値段の範囲ごとに区切ることにする

ラーメンの値段ごとに階が分かれているビルを想像する

・階、すなわち区切りを統計学では階級という。

・各階には値段の真ん中を示した看板が付いている、これを階級値という。

・各階に入っているお店の数のことを度数という。

・すべてのお店の数でその階にあるお店の数を割ったものを相対度数という

図1.ヒストグラムの例

 

全体の分布の雰囲気が何となくわかった。

2.平均

EX ボーリングのスコア

スコアの平均をメンバー数で割ったものが平均

平均・・・算術平均(相加平均)、幾何平均(相乗平均)、調和平均

3.中央値

けど平均をとったとき、例えばメチャクチャスコアの悪いヤツとイイヤツがいたときに

その平均値ってのは本当に集団の性質をうまく表しているかな？

→ そんなときに中央値を使うのだ！

中央値・・・データ数が偶数の時は真ん中の二つの数字の平均、奇数はただの真ん中の値

日本の平均のお年玉→たけえよ死ね→かねもが平均を引き上げている。

だからそのような場合には平均よりも中央値を示してあげるほうが妥当

 

4.標準偏差

まあ、データの真ん中らへんのことは中央値と平均に任せて解決したとして・・・

データの散らばり具合は表せるそれで→無理だよ死ね

標準偏差・・・散らばりの程度を示す、1データあたりの平均からのズレ

散らばりが大きくなればなるほど大きくなる値

標準偏差＝SQRT( (個々のデータ-平均)^2を足した物/データの数）

ただ・・・

母集団の標準偏差を求めるときはこの式を用いるが・・・

標本の標準偏差を求めるときにはデータの数-1で割る事になっている（なんでかはしらね）。

 

5.度数分布表の階級の幅の作り方ｗ

階級の個数を

スタージェスの公式＝1+log10 データの数/log10 2

で求めて

階級の幅を

((データの最大値)-(最小値)) / 階級の個数

でもとめる(厳密)。

↑ウザイ、めんどい、死ね

そもそも階級分布表はデータ全体の雰囲気をつかめればおｋ、だからてめえの好きな幅でやりゃいいらしい(迫真)

 

6.推測統計学と記述統計学

統計学 ┬ 推測統計学

└ 記述統計学

 

・内閣支持率・・・推測統計学

・記述統計学てなナンスカｗｗｗ

データを整理してできるだけ簡潔に示そうとしたもの

 

◆ まとめ ◆

・データ全体の雰囲気をつかむ手がかり

→ 度数分布表・ヒストグラム

・階級の幅・・・スタージェスの公式を利用する

・数学的にデータ全体の雰囲気をつかむ

→ 平均、中央値、標準偏差

・異様に偏っているケースは平均よりも中央値のほうが妥当

・標準偏差＝データの散らばり具合

 

 

 

§3.データ全体の雰囲気をつかむ-カテゴリデータ-

1.単純集計表

◆ まとめ ◆

データの全体の雰囲気-カテゴリデータ-をつかむ手段として、単純集計表の作成がある。

NAT/ファイアウォール透過技術

参考：http://www.ms.u-tokyo.ac.jp/lecture/2006/901-35/2007-01-25.pdf

↑てかこいつは俺と同じ文献読んでるのがまるわかり。せめて文章表現ぐらい少しは変えろよｗ

 

 

NATファイアウォール越えとは簡単に言うものの、しかしながらP2Pオーバレイネットワークとはかなり大まかな概念でしかありません。

なので、現実にはルータやファイアウォールなどの障壁を乗り越えなくてはなりません。

今後はこの具体的な技術を見ていくことにしましょう。

 

逆向き接続

 

Napster、GnutellaなどのP2Pアプリケーションでは当然のテクニックとして採用されている。

 

リレー通信

今度は上で、もう片方のノードもファイアウォールで保護されている場合。その場合は両者以外のノードを中継として利用することでファイアウォール越えを実現している。

 

UPnP

そもそもNATの静的ポートフォワーディングが出来れば必要ない技術。

いわゆるポート開放をしなくてもP2Pソフトウェアが利用出来るようにするための技術。

Torrentのクライアントのほとんどは導入している。故にTorrentが初心者に優しいP2Pソフトの代表になっているのはそのため。

しかしながら、これはルーターがUPnPに対応していることが条件。

 

UDP Hole PunchingとSTUM

AとBというホストが、それぞれのプライベートネットワークにあるとする。N1とN2はそれぞれのNATデバイスである。SはグローバルIPアドレスを持つパブリックサーバである。

1. A と B は S との UDP 通信を開始する。NATデバイス N1 と N2 は UDP 変換状態を作成し、一時的な外部ポート番号を割り当てる。
2. S はそれらのポート番号を A と B にリレーして通知する。
3. A と B は相手のNATデバイスと通知されたポート番号で直接通信する。NAT デバイスはそれ以前に生成されていた変換状態を使い、A および B の間でパケットの送受信が可能になる。

STUN（Simple Traversal of UDP through NATs）は、音声、映像、文章などの双方向リアルタイムIP通信を行うアプリケーションにおいて、NAT traversal（NAT通過）の方法の1つとして使われる標準化された（standards-based）インターネットプロトコルである。 STUNプロトコルは、アプリケーションがNATの存在と種類とを発見し、リモートホストへのUDP（User Datagram Protocol）接続にNATが割り当てたグローバルIPアドレスとポート番号とを得ることを許す。 STUNプロトコルが動作するには、インターネット上にSTUNサーバが存在する必要がある。 STUNプロトコルは、RFC(Request for Comments) 3489に定められる。

STUNはNATゲートウェイとファイアウォールとの存在を発見するために、RFC 3489から構成される下図のアルゴリズムを使用する。

図を通る経路が赤い箱で終わる所ではUDP通信は可能でない。経路が黄色であるか緑の箱で終わる所で、UDP通信は可能である。

 

HTTPカプセル化

ようはHTTP通信であると偽造してP2Pパケットの送受信を行うという手法。

虹ヲタとして

ヲタは偏見を持ってはならない。

ヲタはバイアスを以てして作品を見てはならない。

ヲタは作品に開けているべきである。

これらはすべて、ヲタたるモノ、作品に素直でアレということですな。

日本語はこうも言葉を変えるだけで色々ニュアンスが変わるから面白い。

 

 

可愛い。しかしこいつはどうやら少女漫画が原作らっしい。

俺の友人は腐を異常に嫌っているのだが、俺自体はなんとも思っていない。てかなんでも一括りにして嫌うのは効率の悪いことだと信じているからだ。

まあ、俺らの女版だから性根も顔面も直視できないレベルのものなんだろうけどね。

底辺同士仲良くしろよと思うんだけどねｗどうもこの世界の人間は同属嫌悪が過ぎる

 

 

↑俺登場。そうそう、俺っていつもこんなにイケメンなんだ～

友達からも「どうしたらそんな顔になったの？」とか言われるんだよ。ジョニーデップゥに激似とかよく言われるしね。

阿部寛にも似てるんだって、キムタクにも似てるってよく言われるし。

そうそう、頭もいいんだよ。そして一流大学に入学して、毎日女の子に囲まれてリア充生活でコマッチングな青春をエンジョイしてるんだよね。

ああ、マジで彼女出来ない奴ってどうして出来ないのかマジで理解できねえよ。友人もたくさんいて、毎日学食では俺が中心で楽しい食事会・・・・

 

嗚呼、なんか書いてて悲しくなってきた・・・・ｗ

 

まあ、こんなくっだら無いネタなんてどうでもいいんだけどね、基本的に俺っちは少女漫画の主人公の可愛さも守備範囲内なんだなあ

 

こいつは、なんかこの「りぼん」て雑誌の付録で一話だけ特別にアニメ化された。

 

 

可愛いねえ。まあ、基本的に周りからは、ヲタ友人からも理解されない俺ですが、この趣味だけはやめらんねえｗ

基本的に可愛けりゃ何でもいいんだよね。

女性誌も高校の時代からちょくちょくと買ってました。

CanCanとかじゃなくて、あんなアバズレ中古ゴミなんて見ても興奮なんてしないもんな。

基本的にClassy一択だろJK。

 

 

JJも当たるときは当たるもんなんだなあ。

それがまた、女性誌を買うというスリルがたまらんのですよ。

まずですね、本屋で女性誌のコーナーってのは大抵店の外側にあって、立ち読みして中身を見ていると、周りの通行人に見られるわけですよ。そしてですね、当然女性誌の周辺には惨事のババアがたむろっているわけですから、当然にキモヲタ風情の俺は、かなりの勢いで浮くんですね、というかキモがられる。

けどね、そこで耐えるわけですよ。ひたすら耐える。そうすれば、周りの惨事から大抵はいなくなってくれます。

まあ、いても気にしないからいいんだけどね、そこからはひたすら俺のターン。キモヲタ風情がいるから、そこからは女が寄ってこないし、堂々と中身の物色が出来るってわけだ。

そして、女性店員のレジを選んで持って行くと。これでひとつのプレイが終了するわけです。

 

初めてのやつは、初めてエロ本買った時みたいな緊張感を味わえるかもよｗ

 

女性誌のナニがいいんだってか？考えるんじゃねえよ、感じるんだ。

確かに直ぐにシコシコやってピューてな使い方は出来ないわけですが、ただ単純にきれいなものを見ていると心が安らぐだろ？

青年誌とかのグラビアってアバズレ臭が強すぎて俺的には全然需要がねえんだよな。

 

だから女性誌を見る。女性が読者だから基本的にハズレは無い。というか、それは雑誌でキチンと住み分けがなされているから、自分が「髪の毛をウンコ色に染めて、将来皮膚がんになるために皮膚をやけど寸前まで焼いて、顔に染料を塗りたくって、アフリカの未開の地にいそうな民族のコスプレしてま～す」的なものを選ばなけりゃ問題ない。

 

基本的に出てくる女の質は上物。だから雑誌との感性と会えば、結構男でもグヘヘヘエエエエェできるいい代物だよ。

読者参加記事に出てくるゴミどもは除いてねｗ

けど、これが実際にあってみたいかというと話は全くの別問題なんだよね。

モデルと言っちゃ金遣い荒い、わがまま、人のすべてを顔で判断すると、人間として腐っているようなやつがたくさんいそうだから、ああいうのは雑誌できれいなところだけ見てりゃいい。実際にあったら「死●よKS」てなことになるのは目に見えてるしな。

だから、基本的に二次に限るというのはそういう事だ。惨事の女も見るだけなら何ら問題ない、可愛けりゃ鑑賞の対象にもなりうる。

ただそいつがしゃべってきたり、なんか意見を主張しだすと突然ウザイ存在になる。

そうなんだよ、基本的に動かなけりゃ上物なんだけどね。実際はそうもいかんのだなあ。残念だ。

 

別に可愛いだけじゃなくて、少女漫画にはなかなかの良作も多い。

 

 

これなんかは鉄板だね。僕のSSの心情描写に結構似ているものがある。かなりの良作だよ。