パケットが みちを さがす ほうほう、ルーティング

わかれみちで えらぶ

てがみは とちゅうの えきを とおりました。
でも ひとつの えきに つくと
みちが ひとつだけ ある わけでは ありません。
となりの えきが いくつも ある ことが おおいです。
では つぎは どの えきへ わたしますか?
それを えらぶのが ルーティングの はじまりです。
インターネットでは この えきを ルーターと よびます。
下で つぎの えきを じぶんで えらんで。

となりの えき こうほの ひとつを おして パケットを わたして。(えき = ルーター · おす = つぎの えき えらび)

いちど わたすと パケットは となりの えきへ いきました。
その えきで また わかれみちが でます。
こうして 一えき 一えき わたしていくと
いつか もくてきちに つきます。
でも てきとうな となりの えきを えらぶと
ちがう ところを ぐるぐる まわる ことが あります。
だから えきごとに きじゅんが ひつようです。
なにを 見て えらぶか、つぎで 見ます。

みちあんないひょうを 見る

えきごとに 小さな ひょうを 一まい もっています。
「みちあんないひょう」です。
ひょうには ぎょうごとに こう かいてあります。
「あの もくてきちへ いくなら、この となりの えきに わたせ。」
だから パケットが つくと
えきは もくてきちの じゅうしょを 見て
ひょうで その ぎょうを さがし
かいてある とおり つぎの えきに わたします。

もくてきちの ぎょうを おして「つぎは だれに わたすか」を しらべて。(ひょう = みちあんないひょう)

ひょうを 見れば えきは まよいません。
もくてきちが どこでも
その ぎょうを さがせば つぎの 一ぽが きまります。
大事なのは えきが ぜんたいの みちを
ぜんぶ 知る ひつようが ない ことです。
「すぐ つぎは だれに」だけ わかれば いいのです。
のこりは つぎの えきが また じぶんの ひょうを 見て つづけます。
小さな ひょうが つながって ながい みちを つくります。

いちばん はやい みちを えらぶ

もくてきちへの みちは ひとつだけでは ありません。
まわる みちも、ちかみちも あります。
では ひょうには どの みちを かいて おくでしょう?
もちろん いちばん はやい みちです。
これは まえに 見た ことが あります。
点と 線の うえで さいたん きょりを さがした こと、
まさに その いちばん はやい みち さがしを
ここ ルーティングで そのまま つかいます。

二つの みちを おして きょりを くらべて。みじかい みちが ひょうに かかれる みち。(さいたんけいろ かいしゅう)

みじかい みちを えらんで ひょうに かいて おけば、
つぎから その もくてきちへの パケットは
じどうで はやい みちを ながれます。
だから ルーティングは 二つの しごとを します。
ひとつは いちばん はやい みちを さがして ひょうを つくる こと、
もう ひとつは パケットが きたら ひょうどおり わたす こと。
まえのが algorithms で ならった さいたんけいろ、
うしろのが わかれみちで えらぶ ことです。

ちゅうおう かんせいとうが ない

ここで いちばん おどろく ことが でます。
この すべてを しきする ちゅうおう かんせいとうが ありません。
どこにも「ぜんたいの ちずを にぎる ひと」が いません。
かくえきが じぶんの ひょうだけ 見て
じぶんで つぎの 一ぽを きめます。
こういうのを ぶんさんと いいます。
ちゅうおう 一かしょが ぜんぶ きめるのでは なく
たくさんの えきが わけて はんだんするのです。

えきを ひとつ おして とめてみて。ちゅうおう せいぎょなら みちが きれますが、ぶんさんなら ほかの えきが うかいろを みつけます。

ひとつの えきが とまっても みちは きれませんでしたね?
となりの えきが じぶんの ひょうを なおして
べつの みちへ うかいしました。
もし ちゅうおう かんせいとう ひとつが
すべてを きめて いたら、
その とうが とまった しゅんかん ぜんぶ とまったでしょう。
ぶんさんだから 一かしょが しんでも
ぜんたいは うごきつづけます。

まとめ

ルーティングを 一行に まとめます。
パケットは 一えき 一えき わたされて みちを さがします。
かくえきは みちあんないひょうを 見て
つぎは だれに わたすかを えらびます。
ひょうには いちばん はやい みちが かいてあります。
ちゅうおう かんせいとうは ありません。
かくえきが じぶんで はんだんする ぶんさん システムだから
ひとつの えきが とまっても てがみは うかいろで すすみます。

かなめを じゅんに おして まとめます。(わかれみちで えらぶ → みちあんないひょう → いちばん はやい みち → ちゅうおうの ない ぶんさん)

インターネットが なかなか きれない ひみつが ここに あります。
ちゅうおう 一かしょに すべてを まかせなかったからです。
たくさんの えきが それぞれ みちあんないひょうを 見て
はやい みちで パケットを わたします。
どこかが ふさがると べつの えきが うかいろを みつけます。
小さな はんだんが あつまって
ぜんせかいを つなぐ きょだいな みちに なります。
それが パケットが みちを さがす ほうほうです。