読者です 読者をやめる 読者になる 読者になる

理系院卒のネットワークなブログ

意外なところに「つながり」ってありますよね

【勉強】Counting to Infinity問題を解説してみた

勉強

たまには情報ネットワークを専攻している人っぽい記事を書きます。

IPパケットを転送する技術についてネットで調べていました。いろいろ親切に書いてあるページがたくさんあります。しかし、かゆいところに手が届かない面もあって、先生や先輩に教えていただいた事項があります。それを書いておこうかなと思ったわけです。

 

IPパケットの転送方式

IPパケットはバケツリレーのように送られます。その転送のステップは大きく分けて2つです。

・ルーチングテーブルに基づき、パケットを転送するIPフォワーディングという技術
・ルーチングテーブルを作成する、IPルーチングという技術

このうち、IPルーチングを行う(ルーチングテーブルを作成する)手法にはいくつか種類があります。ディスタンスベクター、パスベクター、リンクステートなどが挙げられます。これらを解説したページはけっこう見つかります。

 

ディスタンスベクター

その中で、ディスタンスベクターを使ったときに発生する問題がCounting to Infinityという問題です。これはどういう問題なのか、なんとなく説明していこうと思います。

ディスタンスベクターはだいたい次のようなことをして、バケツリレーの次の相手を決めています。下の図を見てください。

SをスタートDをゴールとしてバケツリレーをします。Sに繋がっているのはAとBです。Aまでは距離3、Bまでは距離2です。いまSに分かっているのはここまでです。

f:id:ytera22:20140607163404p:plain

なるだけ早くDまで情報を送りたいので、距離は短い方がいいですね。SからBに渡したくなりますが、その先がどのようなネットワークになっているのかはわかりません。

ここでAとBはSへディスタンスベクターを送ります。ディスタンスベクターには宛先とその宛先までの距離が書かれていると思ってください。

例えば、Aから来たディスタンスベクターには「Dまでは距離50だよ」と書いてあり、Bからのには「Dまでは距離100だよ」と書いてあったとしましょう。

当然、SからDへバケツリレーするならAですよね。Aを選べば50+3で距離53となり、Bを選ぶと100+2で距離は102ですから。

 

実際にはどのような処理を行っているのかというと次のような説明になります。

『各ルータがディスタンスベクター(宛先アドレス、宛先アドレスまでの距離、次ホップルータ)を交換し、隣接ルータから宛先ごとのディスタンスベクターを基に自分のディスタンスベクター表を更新し、宛先アドレスごとの次ホップを算出するものである。ディスタンスベクター表には宛先ごとの距離とその時に用いる隣接ルータへのリンクの組を記録する。』

「ルータ」と言うのは中継基地のようなもので図ではAとかBとかで表しているものです。「次ホップ」というのはバケツリレーの次の相手です。

どのルータも自前の表を持っていて、「この宛先のパケットが来たらこっちにリレーする」ってのを決めておくんですね。その表を作るために、ディスタンスベクターを交換するというわけです。リンクは動的に変化するので、ディスタンスベクターは定期的に交換されます。そうすれば自動的に変化にも対応できるというわけですね。

 

Counting to Infinity問題の発生

ところで、ある連絡線が切れてしまった場合どのようなことが起きるでしょうか。下の図で考えていきます。

()で囲ってあるのは(Aまでの距離,Aに到達するときのリレーの次の相手)を表しています。四角で囲ってあるのはディスタンスベクター表だと思ってください。本当は(Bまでの距離,Bに到達するときのリレーの次の相手)(Cまでの距離,Cに到達するときのリレーの次の相手)・・・と書き連ねてあるものなんですが、今回は宛先をAに絞って考えます。

線はすべて距離1とします。

 

いま、AとBを結ぶ線が切れてしまいました。

BからAへは行けないので距離が無限大(Infinity)だと判断して(Inf,A)となります。

一方、ディスタンスベクターは一定時間毎に、定期的に交換されます。Cから送られてくる時間になりました。(BからCへも送られていますが、見づらくなるので関係ない矢印は書きません)

f:id:ytera22:20140607163450p:plain

Cからは、「僕に渡してくれれば、Aへは距離2でいけるよ」というディスタンスベクターが送られてきます。なのでBは「Cを経由すれば距離3でAにいけるんじゃん」と判断して表を書き換えます。

f:id:ytera22:20140607163509p:plain

次にディスタンスベクターを交換する時間になりました。BからCへ「僕に渡してくれれば、Aへは距離3でいけるよ」というディスタンスベクターを送ります。なのでCは「Bを経由すれば距離4でAにいけるんじゃん」と判断して表を書き換えます。

f:id:ytera22:20140607163518p:plain

もうお分かりですね。無限ループです。距離がどんどん大きくなっていくだけの不毛なやりとりです。無限までカウントされいくでしょう。だからCounting to Infinityなのです。

 

対応策は・・・

これを対策する方法として一番手っ取り早いのが、距離に制限をかけることです。ある基準値より大きくなったディスタンスベクターが出現したら、異常事態だと認識するようにすればよいのです。

では、どのくらい増えたら異常事態だと設定すればいいでしょうか。

今の例でいくと、基準値を5ぐらいにしたらすぐに異常が検知されますが100にしたらだいぶ時間がかかりそうですよね。

でも基準を5にしたら、異常がなくても距離5以上離れている宛先には送れなくなります。

 

つまり

・基準の距離を大きくすると収束するまでの時間が長くなる
・逆に小さくするとネットワークの規模が制限されてしまう

ということが言えるわけです。ネットワークの規模を制限してしまったら本末転倒なので、ディスタンスベクター表が収束するまでの時間を短縮する方法がいろいろと考えられています。

そのうちの1つを勉強したので、そちらも書き残して起きます。

【勉強】スプリットホライズン・ポイズンリバースを解説してみた - 大学院生のネットワークなブログ