ほぼ日刊サービス開発日誌

React, firebase, 機械学習など

sponsored

ルータはどうやってルーティングテーブルを作っているのか - AS(Autonomous System)と経路制御プロトコル

AS とはなにか

インターネットに繋がる、ルーティングポリシー配下にあるIPネットワークやルータの集合のことをインターネットにおける自律システム (autonomous system) といい、ASと略します。それぞれの縄張りには「AS番号」と呼ばれる識別番号が付与されています。規模の大きなISP(Internet Services Provider)のネットワークは、大抵固有のASを形成しています。 この識別番号は全世界で一意です。

各ルータは「このパケットはどっちに転送すればいいか」を示す地図である「ルーティングテーブル」を持っています。これをどう作るかについてまとめます。

初期化された段階では、ルーターは直接接続している経路しか知りません。しかし、それぞれの情報を近隣ルータに伝達し、また近隣に伝達し・・・を繰り返し、最終的には全ての経路が全てのルータに学習されます。(新規経路を全てのルータが学習するまでの時間を収束時間といいます)

ASの内部に情報を配布する経路制御プロトコルは内部ゲートウェイプロトコル / IGP(Interior Gateway Protocol)と呼ばれます。

ASどうしの間で行われる経路制御プロトコルは外部ゲートウェイプロトコル / EGP(Exterior Gateway Protocol)と呼ばれます。

http://www.soi.wide.ad.jp/class/20020036/slides/35/img/5.png

http://wa3.i-3-i.info/img/diff/100/df00157-7.png

ルーティングテーブルについて

ルーターは、それぞれが「ルーティングテーブル」を維持していて、その中の各エントリが宛先を示している。

それぞれの経路について、ルーティングテーブルには以下のエントリが格納されている。

  • 次ホップアドレス

  • メトリック:宛先に到達するまでの総距離。メトリックの値は、この値をルーティングテーブルに提供した経路制御プロトコルによって異なる。異なる経路制御プロトコルが算出したメトリック値は互いに比較することはできない。なのでどの経路制御プロトコルの値を採用するか、各プロトコルに優先順位を割り当てて決めなくてはいけない。

  • タイマー:最後に経路情報が更新されてからの時間を表す。

  • 経路提供元:このエントリの情報提供元を表し、直接接続か・スタティックルートか・RIPか・BGPかなどの経路制御プロトコルが示される。

IGP(ネットワーク内で行われるルーティング)

日本国内ではOSPF(Open Shortest Path First)と呼ばれるプロトコルが最も多く使われています。これはRIPというもっとも古いプロトコルの弱点を克服するために作られたので、まずRIPについて説明します。

RIP(Routing Information Protocol)

最も歴史あるIGPのルーティング・プロトコルのRIP。シンプルさゆえに多くの企業で利用されています。経由するルータの数が15個までというプロトコル上の制約があるので、大規模ネットワークのEGPには向きません。

RIPでは、宛先までのルータの数(ホップ)をカウントして、それがより少ない経路情報が最適経路として使用されます。

(ルータ一台はそれぞれ1ホップとカウントされます。)

UDPのブロードキャスト・データ・パケットを用いて、経路情報を、直接つながれている近隣のルータに定期的に配布します。

この中には、「メトリック」と呼ばれるあて先ネットワークまでのディスタンスを表す情報(ルータのホップ数)が含まれており、ルータを超えるごとに1つずつ加算されます。RIPは、このメトリックを利用してネットワーク・トポロジを把握するため、「ディスタンス・ベクタ・アルゴリズム」に基づいたルーティング・プロトコルと呼ばれています。

あるルータより180秒以内にレギュラー・アップデートなどを受信しなかった場合、その相手先ルータにおける障害発生、または、そこに接続されたネットワークが無効になったと見なし、これに該当する経路情報が無効化されます。

このように接続されたネットワークが利用できなくなった場合、そのネットワークあての経路を無効化すると同時に、これを隣接したルータに伝えるため、(すぐに削除することはしないで、)無効経路となった経路情報にメトリック16(到達不可能)をセットして送信します。 このような処理を、経路ポイゾニング処理といいます。

IPルーティング入門(4):RIPの仕組みと運用法を知ろう! - @IT

180秒以内のレギュラーアップデート、30秒周期の隣接ルータへのアナウンスなど、配信間隔による制約があるため、収束には時間がかかる方です。また、RIPにおいては、メトリックには伝達速度が考慮されていないので、リアルタイムな帯域幅や遅延や負荷・信頼性などの測定による経路選択は行えません。

OSPF(Open Shortest Path First)

RIPのイマイチなところ(収束が遅い・到達範囲が短い・ネットワークの特性は無視して距離しかかんがえれない)を克服するために設計されました。

それぞれのルータは、リンクステートデータベース(LSDB)とよばれる自分のルータ内のデータベースに、受信したリンクステート広告(LSA, Link State Advertisement) を保存します。

OSPFでは、コスト値の低い経路情報が最適経路として使用されます。LSDBを用いて、ルータは各経路に対する最小コストパスのツリーを構築します。

このツリーの構築のための計算は、グラフ上の2頂点間の最短経路を求めるアルゴリズムダイクストラ法( Djikstra’s algorithm)によりなされます。Djikstraアルゴリズムについては  ダイクストラ法(最短経路問題)がわかりやすいです。

コスト(メトリック)の値は、その帯域の広さと反比例、つまり、帯域が広いほどコストが低いというように認識されます。

ネットワークのトポロジ情報を各ルータが格納・計算しなくてはならないため、ネットワークの規模が大きすぎるとルータのリソースが追いつかないので、大規模ネットワークには向きませんが、収束速度はRIPに比べて速いです。1箇所のデータの変更が同一ASの全てのルータに伝播されるので、データベースの処理にはCPUやメモリをとても使ってしまうわけです。なので、OSPF方式では、ASをエリアごとに分割することによって負荷を軽減しています。

一度リンクステート情報が交換されると、この情報に更新がない場合は、基本的にはHelloパケットによる生存確認のみを行います。変更がある場合は差分のみが送信されます。

Helloプロトコルは、初期化されたさいに、近隣にいるルータをみつけるときにも使われます。

EGP(異なるASネットワーク間で行われるルーティング)

EGPとして利用されているプロトコルのほとんどはBGP(Border Gateway Protocol)です。

BGP(Border Gateway Protocol)

BGPルータは、隣接したルータとTCPを用いて1対1のセッションを確立し、セッション確立直後にすべての経路情報を交換します。その後、この情報に更新がない場合は、Keep Aliveパケットによる生存確認のみを行います。また、更新があった場合には、その差分情報だけを交換します。BGP経路情報には、パス属性と呼ばれるパスに関する情報が含まれており、これに基づき最適経路が決定されます。

IPルーティング入門(1):ルーティング・プロトコルの役割を理解する - @IT

BGP ハイジャック

BGPをルーティングパスを書き換えるために使ってしまおうと言うものです。

突然,一部のユーザーが米グーグルの動画サイト「YouTube」にアクセスできなくなる──。こんな事件が2008年2月24日に発生した。この事件の背景には,インターネットのバックボーンを支えるプロトコルの一つ,BGPの仕様上の弱点があった。

BGPでは,経路情報をやり取りする大規模ネットワークをASという単位でとらえ,「AS番号」と呼ばれる一意の番号を振っている。大抵のISPやデータ・センター,一部の大企業などはAS番号を持っている。

AS同士はBGPを使って,「どのASの先にどんなアドレスのネットワークがあるか」といった経路情報を交換する。膨大な経路情報をなるべく安定してやり取りするため,経路情報はアドレスを大きなブロック単位に束ねた形で送る。また,送られてくる経路情報はいちいち認証せず,基本的に信用する。どこか1カ所の経路情報が変わると,変更内容は世界中のルーターに自動的に伝わっていく仕組みだ。

前述の2008年2月の事件は,このBGPの仕様に原因があった。パキスタンの通信事業者であるパキスタン・テレコミュニケーションが国内からYouTubeへのアクセスを止めるために,「YouTubeのネットワークが自社のAS内にある」との偽経路情報を国内ネットワークに流したのが発端だ。この時,本来はパキスタン国内だけに流れるはずだった経路情報が,設定ミスでインターネット上に流れてしまった。つまり,経路情報を信用した世界中のルーターが「YouTubeのネットワークはパキスタン・テレコミュニケーションのAS内にある」と勘違いしたのである。 もちろんYouTube側のASも正しい経路情報を流していたが,BGPの仕様では該当経路が複数ある場合,プレフィックス値が大きい方を優先するのが原則。2008年2月の事件では,よりプレフィックス値が大きいパキスタン・テレコミニケーションの経路情報が優先された。

ぜい弱性に揺らぐインターネット - [BGP経路ハイジャック]誤った経路に導く,難しい根本対策の徹底:ITpro

ホットポテトルーティング(Hot Potato Routing)

インターネットサービスプロバイダ同士が複数の接続点でピアリングしている時、ISP間の通信は送信側に近い接続点を通るようなルーティング方法。ゆでたてのじゃがいも(ホットポテト)は手で持つと熱いので、すぐに他人に渡してしまう、ということからこの名前がついたらしいです。

ホットポテトルーティング ‐ 通信用語の基礎知識

両者がこのようなルーティングを実施した場合、パケットの行きと帰り(上りと下り)の経路が異なることになりますが、両プロバイダのバックボーンの帯域が著しく異なる場合、効率的にトラフィックが分散されないというデメリットもあります。

ルーティングとフォワーディングの違い

ルーティングとは「経路を選ぶこと」である。一方のフォワーディングとは,ルーティングによって選んだ適切な経路へ「パケットを転送する」という意味。つまり,ルーターはルーティングだけでなく,フォワーディングも行う装置というわけだ。

1週間で学ぶネットワークの要点 - ルーティング事始め 入門編 第2回:ITpro

参考

http://wa3.i-3-i.info/diff157routing.html

EGPとIGPの違いを簡潔に教えてください - EGP:大規模なネットワークで使用され... - Yahoo!知恵袋

http://www.soi.wide.ad.jp/class/20020036/slides/35/5.html

IPルーティング入門(1):ルーティング・プロトコルの役割を理解する - @IT

IPv6 エッセンシャルズ 第2版

IPv6 エッセンシャルズ 第2版