ルーティング わかりやすく

分かれ道で選ぶ

パケットは途中の駅を通っていきます。けれども、ある駅に着いてみると、出ていく道が一本だけということはまれで、隣の駅がいくつもあることがほとんどです。
では、次はどの駅へ渡せばよいのでしょうか。それを選ぶことが、ルーティングの始まりです。インターネットでは、この駅をルーターと呼びます。

点滅している隣の駅のどれかを押して、パケットを渡します。（駅 = ルーター・押す = 次の駅を選ぶ）分かれ道ごとに選んでいくと、目的地に届きます。

一度渡すと、パケットは隣の駅へ移り、その駅でまた分かれ道が現れました。こうして一駅ずつ渡していけば、いつかは目的地に着きます。
けれども、どの隣の駅でもかまわず選ぶと、見当違いのところをぐるぐる回ってしまうかもしれません。だから、駅ごとに選ぶ基準が必要です。

道案内表を見る

どの駅も、小さな表を一枚ずつ持っています。これを道案内表と呼びましょう。表の行ごとに「この目的地へ行くなら、この隣の駅に渡せ」と書いてあります。
パケットが着くと、駅は目的地の住所を見て表からその行を探し、書いてあるとおりに次の駅へ渡します。実際のルーターでは、この表をルーティングテーブルと呼びます。

道案内表の目的地の行を一つ押すと、その目的地へ行くには次にどの駅へ渡せばよいかが出てきます。（表 = 道案内表）違う目的地が同じ隣の駅を指すこともあります。

表があれば、駅は迷いません。目的地がどこであっても、その行さえ見つければ次の一歩が決まります。
大切なのは、駅が道のりの全体を知る必要がないということです。すぐ次にだれへ渡すかさえわかればよく、その先は次の駅が自分の表を見て引き継ぎます。
小さな表がつながって、長い道ができあがるのです。

より短い道を選ぶ

目的地へ行く道は一本だけとはかぎりません。遠回りの道も、近道もあります。では、表にはどの道を書いておくのでしょうか。もちろん、いちばん短い道です。
この問題には前にも出会いました。アルゴリズムの分野で、点と線でできたグラフの上で最短経路を探したのと同じことを、ルーティングでもそのまま使います。
実際のインターネットでは、距離だけでなく、回線の速さや混み具合などいくつもの基準をあわせて考えることもあります。

上の道と下の道を押して、距離の合計を比べます。通るマスの数は下の道のほうが多いのに、距離の合計は下の道のほうが短いので、表には下の道が書かれます。

短い道を選んで表に書いておけば、その目的地へ向かうパケットは、次からは自然に速い道を流れていきます。
つまりルーティングは、二つの仕事をしています。一つはいちばん短い道を探して表をつくる仕事、もう一つはパケットが来たら表のとおりに渡す仕事です。
前者がアルゴリズムの分野で学んだ最短経路探しで、後者が分かれ道での選択です。

中央の管制塔はない

ここで、いちばん驚くべき点が出てきます。これらすべてを指揮する中央の管制塔がないのです。全体の地図を手にしている人は、どこにもいません。
どの駅も自分の表だけを見て、次の一歩を自分で決めます。このように、一か所がすべてを決めるのではなく、たくさんの駅が分担して判断するしくみを分散と呼びます。
駅どうしは隣の駅と道の情報をたえずやり取りしながら、自分の表を直していきます。

中央制御と分散のどちらかを選んでから、真ん中の駅を押して止めます。中央制御では道が途切れ、分散では隣の駅が自分で回り道を見つけます。

一つの駅が止まっても、道は途切れませんでした。隣の駅が自分の表を直して、別の道へ回ったからです。
もし中央の管制塔一つがすべての道を決めていたら、その塔が止まった瞬間にすべてが止まっていたでしょう。分散だからこそ、一か所が倒れても全体は動き続けます。

まとめ

ルーティングを一言でまとめると、パケットは一駅ずつ渡されながら道を見つけます。駅ごとに道案内表を見て次にだれへ渡すかを選び、表にはいちばん短い道が書かれています。
中央の管制塔はありません。駅ごとに自分で判断する分散のしくみなので、一つの駅が止まっても、パケットは回り道で進み続けます。

四つの要点を順に押してまとめます。（分かれ道で選ぶ → 道案内表 → いちばん速い道 → 中央のない分散）四つすべてが光れば、まとめは完了です。

インターネットがめったに途切れない秘密は、ここにあります。すべてを中央の一か所に任せなかったからです。たくさんの駅がそれぞれ道案内表を見て速い道へパケットを渡し、どこかがふさがればほかの駅が回り道を見つけます。
小さな判断が集まって、世界中を結ぶ巨大な道になっているのです。次のレッスンでは、アドレスバーに打ち込む名前を数字の住所に変えてくれる案内所を扱います。