技術講座

[技術講座（ルーティング技術―１）] 　　　　　　　　　　　　　　　　　（2003/05/20作成）

　インターネットにおける通信経路の制御技術であるルーティングについてまとめました。

１．IPとルーティング

１．１ルーティングとは

（１）ルーテイングテーブル

　インターネットの通信は、IPパケットのやりとりで成り立っています。IPパケットのヘッダには、宛先IPアドレスが書いてあります。また各ルータでは、宛先IPアドレスが所属するネットワークとネクストホップの関係をまとめたルーティングテーブルを持っています。ルータは、IPパケットの宛先アドレスとルーティングテーブルを参照して、ネクストホップを決定します。

（２）IPパケットが目的地まで到達する仕組み

　ホストAからホストC行きのIPパケットが送信された例で示します。ホストAからIPパケットが直近のルータXに来ると、ルータXではIPパケットの宛先アドレスCと、ルータX自身が持っているルーティングテーブルを比較します。アドレスCがネットワークCに含まれることが分かると、ルーティングテーブルでネットワークCに対応するネクストホップを読み、それがルータZであることが分かると、ルータXはこのIPパケットをルータZに向けて転送します。

　ルータZに到着したIPパケットは同様に処理されます。IPパケットの宛先アドレスとルータZのルーティングテーブルを参照して、ネクストホップがルータVであることが分かると、ルータVに転送するわけです。

　以上のように、ルータではIPパケットの宛先アドレスと、自身のルーティングテーブルを参照して次のルータに転送します。それを繰り返して、最後にIPパケットは宛先アドレスのホストにたどり着きます。つまり、IPパケットはホップバイホップに（１つ１つ順々に）転送されていくわけです。

（３）ルーティングとフォワーディング

　インターネットで適切に通信が行われるためには、各ルータのルーティングテーブルが適切に設定されていなければなりません。また、実際のインターネットでは、経由するルータの組み合わせは何通りもある場合が少なくないため、その中から最も効率的な経路を選択することも重要です。

　このように、送信元から目的の宛先までの最適な経路を選択するタスクをルーテイングと呼びます。具体的には、「パケットが最適な経路を通るように各ルータのルーテイングテーブルを作成し、それに基づいてルータに入力されたパケットをどのインタフェースに出力するかを決定すること」がルーテイングということになります。

　一方、実際に入力したパケットを、ルーティングによって選ばれた出力インタフェースに出力することをフォワーディングと言います。つまり、ルータはルーティングにより最適な出力インタフェースを決定し、それに基づいてパケットをフォワーディングしていくわけです。

（４）なぜルーティングが必要か

　ルータやホストは、自分のネットワークインタフェースにつながっているネットワークのアドレスは分かります。ネットワークインタフェースにはIPアドレスとサブネットマスクが割り当てられているため、そこにつながるネットワークを簡単に割り出すことができます。

　従って、IPパケットの宛先アドレスが同一ネットワークにつながる装置の場合、該当するネットワークインタフェースにパケットを送出すればよく、ルーティングの設定は不要です。ルーティングの設定をしなくても、同じネットワーク（直接接続されているネットワーク）の情報は、ルーティングテーブルに載っているので設定は不要ということです。

　図1 に示す構成で、ルータAのEther0のインタフェースとルータBのEther0のインタフェースが通信する場合、各ルータでは各インタフェースにつながるネットワークは192.168.100.32/29であることが分かっています。



　図1 ルーティングの設定が不要な場合

　従って、ルータAで宛先アドレスが192.168.100.36のIPパケットを送出する場合、その宛先アドレスは192.168.100.32/29の範囲内なので、ルータAのEther0と同じネットワークにあり、ルータAはそのパケットをEther0から送出すればよいことが分かります。逆向きも同様です。

　このように、図1では、ルータAのEther0のインタフェースとルータBのEther0のインタフェースの通信には、ルーティングの設定は不要となります。

　ところが、IPパケットの宛先アドレスが自分のインタフェースにつながるネットワークの範囲外である場合は、そのパケットをどのインタフェースから送出すればよいか分かりません。従って、異なるネットワークにつながっている装置同士の通信では、ルーティングの設定が必要になります。

　図2に示す構成で、ルータAでは192.168.100.32/29がEther0につながっているネットワークであること、10.1.2.144/28がEther1につながっているネットワークであることは分かりますが、172.16.3.16/29や10.5.6.64/27のネットワークがどこにあるのかは分かりません。



　　図2 ルーティングの設定が必要な場合

　そこで、ルータAでは10.5.6.64/27のネットワークがルータBの向こう側であることをルーテイングテーブルに書き込む必要があるわけです。

１．２ IP

（１）IPv4パケットのフォーマット

　図3にRFC791に規定されたIPv4パケットのフォーマットを示します。



　　図3 IPv4パケットのフォーマット

[Versionフィールド]
　IPのバージョンを示します。RFC791の規定はIPバージョン4なので、フィールド値は「4」となります。

[IHLフィールド]
　IHLは「Internet Header Length」の略で、32ビットを単位としたIPヘッダの長さを表します。オプションがない場合のIPパケットでは、この値は「5」となります。

[Type of Serviceフィールド]
　本フィールドは「TOSフィールド」と呼ばれ、そのIPパケットがどのような品質で扱われるべきかを区別するために用いられます。

[Total Lengthフィールド]
　ヘッダを含むIPパケット全体の長さをオクテットの単位で示すものです。このフィールドは16ビットあるためIPパケットの最大長は65535オクテットとなりますが、実際にはイーサネットなど一般的なネットワークのMTU(Maximum Transmission Unit：１フレームで転送可能な最大オクテット数)が1500オクテット程度であるため、ほとんどの場合パケット長はこれより短くなります。

[identificationフィールド][Flagsフィールド][Fragment Offsetフィールド]
　送ろうとするパケットの長さがネットワークのMTUより大きいときに、そのパケットは分割されます。このパケットの分割・再構成を実現するために使われるのがこれらのフィールドです。

[Time to Liveフィールド]
　本フィールドは「TTLフィールド」とも呼ばれ、IPパケットがルータなどの中継機器を通過する際に１つずつ減らされる値で、「0」になるとそのIPパケットは廃棄されます。

[Protocolフィールド]
　Dataフィールドで運ばれる上位のプロトコルを識別するフィールドです。１番：ICMP、６番：TCP、17番：UDP、41番：IPv6 over IPv4、89番：OSPF等があります。

[Header Checksumフィールド]
　IPパケットの伝送エラーがないかチェックするためのフィールドです。送信側では、伝送するIPパケットのヘッダのビットを組み合わせて数値計算をし、その結果の値をこのフィールドに入れます。受信側でも同様の数値計算をし、受け取った値と比較して伝送エラーがないかどうかを確認します。

　実際は、ルータでTTLを１つずつ減らすためにビット配列が変わり、数値計算の結果が変わってしまうので、各ルータでは転送する前にヘッダチェックサムの再計算をする必要があります。従って、チェックサムの値はルータを通過する毎に変わっていくことになり、その値は次のルータまで伝送エラーがないかどうかの値となります。また、NAT（アドレス変換装置）においても、送信元アドレスや宛先アドレスを変更するので、ヘッダチェックサムの再計算が必要となります。

[Source Addressフィールド][Destination Addressフィールド]
　「Source Address」は送信元IPアドレス、「Destination Address」は宛先IPアドレスを示します。

[Optionsフィールド]
　オプションを指定するフィールドです。オプションにはIPパケットが通るルートをあらかじめ決定できるソースルーティングなどがあります。

（２）IPアドレス

　(a) ネットワークアドレス部とホストアドレス部
　32ビットで構成されるIPアドレスは、ネットワークアドレス部とホストアドレス部で構成されます。前者はインターネット全体の中でネットワークがどこにあるかを示し、後者はそのネットワークの中でホストがどこにあるかを示します。

　(b) クラス
　32ビットの内、ネットワークアドレス部とホストアドレス部の区分はクラスによって決まっています。図4に各クラスのビット構成を示します。IPアドレスの先頭のビットが「0」のアドレスは、ネットワークアドレス部が先頭の8ビットとなり、「クラスA」と呼びます。



　　　図4 クラス（A〜E）のビット構成

先頭が「10」のアドレス（クラスB）は、ネットワークアドレス部が先頭の16ビット、先頭ビットが「110」のアドレス（クラスC）は、ネットワークアドレス部が先頭の24ビットというように決められてきました。クラスには、クラスA、B、Cの他に、マルチキャスト通信で使用されるクラスD、実験用に予約されているクラスEがあります。

　(c) ネットワークアドレスとブロードキャストアドレス
　一般的に使用されるアドレスは、クラスA、B、Cのアドレスです。ただし、ホストアドレス部のビットがすべて「0」または「1」のものは、各クラスともに通常のアドレスとしては使用できません。前者はそのネットワーク自身のネットワークアドレスを表します。後者はそのネットワーク全体に対するブロードキャストアドレスを表します。

　(d) ブロードキャスト
　ブロードキャストアドレス宛にIPパケットを送ると、そのブロードキャストアドレスで指定されているネットワークセグメントに接続されたすべてのホストにパケットが転送されます。

　ブロードキャストアドレスには32ビットすべてが「1」のローカルブロードキャスト（10進数表記では255.255.255.255）と、ホストアドレス部分だけのビットがすべて「1」であるダイレクトブロードキャストがあります。前者は、そのホストが接続されたネットワークへのブロードキャストであり、パケットを受け取ったルータがそれを他のネットワークに転送するようなことはありません。後者は他のネットワークに向かってルーティングすることも可能です。

　(e) クラスA
　クラスAは先頭1ビットが２進数で「0」なので、先頭の8ビットが表す範囲は00000000〜01111111（10進数表記では0〜127）になります。しかし、ネットワークアドレス「0」はデフォルトルートや自分自身を意味し、「127」はループバックアドレス用に指定されているため、使用できるネットワークの数は1〜126となります。

　１ネットワークの最大ホスト数は、ホストアドレス部が24ビットのため、2²⁴から2を引いた16,777,214個となります。2を引くのは、すべてのビットが「0」（ネットワークアドレス）または「1」（ブロードキャストアドレス）のアドレスはホスト用のアドレスとして使用できないからです。

　(f) クラスB
　クラスBは先頭2ビットが2進数で「10」なので、10進数で表したIPアドレスの最初の数字は、128〜191（2進数では10000000〜10111111）となります。1ネットワークの最大ホスト数は、ホストアドレス部が16ビットのため65,534個（=2¹⁶−2）となります。

　(g) クラスC
　クラスCは先頭3ビットが2進数で「110」なので、10進数で表したIPアドレスの最初の数字は、192〜223（2進数では11000000〜11011111）となります。1ネットワークの最大ホスト数は、ホストアドレス部が8ビットのため254個（2⁸−2）となります。

　(h) アドレス部の最初の数字を見ればクラスが分かる
　それぞれのクラスでアドレスの範囲は決まっているため、IPアドレスを構成する4つの10進数の内最初の数字によって、そのアドレスが属しているクラスが分かります。例えば、「61.」であればクラスA、「210」であればクラスCということになります。

（３）サブネット

　(a) サブネット
　実際のネットワークでは、ホスト数が10台もないようなネットワークは珍しくありません。そのようなときにクラスの概念通りに使用すると、クラスCでも254台分の大きさですから、実際に使用されないアドレスが多くなります。全世界で32ビットしかないIPv4アドレスの枯渇問題が取りざたされている状況で、このようなもったいない使用方法は問題となります。

　また、ある程度大きな企業でも、ブロードキャストのトラフィックを制限したい、使用しているメディアが違う（EthernetとFDDIなど）等の理由で、部などの単位組織毎にネットワークを分割することが少なくありません。このようなとき、ネットワークをクラスの概念よりも細かく分けて、それぞれにアドレスを割り当てて有効にアドレスを使用するサブネットという概念を使います。1つのネットワークをサブネットに分割するためには、ホストアドレスの一部をサブネットアドレスとします。

　(b) サブネットのアドレッシング
　例えば、クラスCにおいて、図5のようにホストアドレス部の8ビットの内先頭の3ビットを、ホストアドレス部としてではなく、分割したネットワークを表すサブネットアドレス部に使うことができます。このサブネットが表すアドレス範囲は、ホストアドレス部を「00000」から「11111」まで変化させていくと分かります。図5の例にあるサブネットは192.168.100.64〜192.168.100.95のアドレス範囲を示すネットワークになります。



　　図5 サブネットアドレスの例

　(c) 使用できるアドレス数
　ホストアドレスとして使用できるアドレスは、最初の192.168.100.64（ネットワークアドレス）と、最後の192.168.100.95（ブロードキャストアドレス）を除いた192.168.100.65〜192.168.100.94になります。従って、このネットワークには30台までのホストを接続することが可能です。なお、この「ホストの数」には、ルータ等のネットワーク装置に割り当てるIPアドレスも含みます。また、サブネットアドレス部を変えることにより、サブネットの表す範囲は図6のように変わります。



　　　　図6 サブネットが表すアドレス範囲

　(d) サブネットマスク
　図7に示すように、IPアドレス中のネットワークアドレス部とサブネットアドレス部を示す範囲に、ビット1を立てたものをサブネットマスクと言います。192.168.100.64〜192.168.100.95のネットワークは、「192.168.100.64 255.255.255.224」と表すことができます。



　　　　図7 サブネットマスク


　またこのネットワークに属するホストの内、192.168.100.75のアドレスを持つホストのアドレスを「192.168.100.75 255.255.255.224」と表します。図8に示すように、あるアドレスとそのサブネットマスクの論理積を取れば、そのアドレスが属するサブネットのネットワークが分かります。



図8 アドレスとサブネットマスクの論理積を取る

　(e) プレフィックス表記
　また、192.168.100.64〜192.168.100.95のネットワークを「192.168.199.64/27」と表すこともあります。これをプレフィックス表記と言います。図9に示すように、「/27」は先頭のビットから27ビットのサブネットマスクを使用することを意味します。つまり、サブネットワーク部を含むネットワークアドレス部の長さが27ビットであるという意味です。また、このマスクの長さをマスク長、サブネットマスク長、プレフィックス長等と言います。



　　図9 プレフィックス表記

　(f) サブネット内のホスト数
　例えば「/27」のネットワークに接続可能なホスト数は、次のような計算により30台と分かります。IPアドレス全体の32ビットの内、ネットワークアドレス部とサブネットアドレス部で27ビット分ですから、残りの5ビットがホストアドレス部となります。従って、ネットワークアドレス（すべて0）とブロードキャストアドレス（すべて1）の２つを引いた2⁵−2=30が、このネットワークに接続できるホストの数となります。

　(g) マスク長と接続可能なホスト数
　また、30台を超えるホストが接続されているネットワークにおいては、ホストアドレス部の範囲を5ビットから6ビットに広げて「/27」を「/26」に変更すれば、ネットワークに接続できるホストの数が62台となります。ただし、ホストアドレス部を広くした分、サブネットアドレス部が狭くなるため、構築できるネットワーク（セグメント）の数は減少します。例えば、１つのクラスCアドレスで「/27」のネットワークは8つ（=2^27-24）作れますが、「/26」のネットワークでは4つ（=2^26-24）しか作れません。

　表1にサブネットマスク、プレフィックス長、サブネットワーク数、接続可能ホスト数の関係を示します。マスク長が長くなるほど接続ホスト数は少なくなりますが、１つのクラスCで作成できるネットワークの数は多くなります。言い換えると、接続可能ホスト数に適したマスク長を設定することにより、より多くのネットワークを作成することができます。

　(h) VLSM
　VLSMとは「Variable Length Subnet Mask」の略で、１つのネットワークをサブネットに分割する際に、サブネット毎に異なる長さのマスクを使用する方法です。例えば、ある１つのクラスCを分割するときに、「/26」と「/27」を同時に使用するようなことです。VLSMを使用したネットワークでダイナミックルーティングを使用する場合は、OSPFやRIP Version 2などのVLSMに対応したルーティングプロトコルを使う必要があります。

（４）CIDR

　CIDRとは「Classless Inter-Domain Routing」の略で、「サイダー」と読みます。これは、クラスA、B、Cの概念を取り払い、IPアドレスのネットワークアドレス部とホストアドレス部の長さを任意に決めることを可能にする考えです。1993年頃より使用されています。

　CIDRでは192.168.8.0/22のように、クラスCについてもプレフィックス長を24未満にすることができます。このように、あるネットワークの通常のマスク長（ナチュラルマスク：クラスCなら「24」）よりも短いマスク長で表すネットワークを、「supernet：スーパーネット」と呼びます。

　また、CIDRにおいて、プレフィックス表記で表すようなネットワーク、つまりマスクの情報を含めたネットワークを「prefix：プレフィックス」と言います。つまり、192.168.8.0/22は１つのプレフィックスです。

　CIDRではクラスの概念がないため、サブネットアドレス部という概念もなく、ネットワークアドレス部とホストアドレス部の２つにしか分かれません。その２つの部分は、任意の場所によって区別することができ、左端からそこまでのビット数がマスク長になります。

　CIDRにより、ネットワーク規模に準じた大きさのネットワークアドレスを表すことができます。例えば、400台のホストを１つのネットワークセグメントに接続するときに、クラスBのアドレスを使用することなく、クラスCのネットワーク２つ分を付与してそれを「/23」で使用することが可能になります。

　CIDRを使用すると、連続したネットワークを集約することができます。例えば、192.168.8.0/24、192.168.9.0/24、192.168.10.0/24、192.168.11.0/24の４つの連続したクラスCのネットワークを、192.168.8.0/22という１つのCIDRに集約して表現することができます。

　集約することのメリットは次の通りです。ルータはルーティングテーブルを持っています。ルーティングテーブルは、宛先ネットワークとネクストホップの対応情報の集まりです。従って、経路が集約されて対応情報の数が経れば、ルーティングテーブルの登録（エントリ）数を減らすことができ、ルータの使用メモリを減らすことができます。

　また、IPパケットが転送されるときにはルーティングテーブルが検索されますが、登録数が少なければそれだけ検索にかかる計算量も少なくてすむため、ルータの負荷を軽減することにもつながります。CIDRの採用による経路の集約は、あるISPから外部のISPへBGPで広告する経路情報において実際に使われます。

（５）IPアドレスの配分方法

　現在日本ではJPNIC（日本ネットワークインフォメーションセンター）からISPへIPアドレスが割り振られます。ISPは割り振られたアドレス空間（アドレスブロック）の一部を、さらにエンドユーザに割り当てます。正確に言うと、このISPはJPNICからIPアドレス割り当て管理業務を行う指定を受けた「IPアドレス管理指定事業者（IP指定事業者）」となります。

　JPNICやISP（IP指定事業者）は「IR：インターネットレジストリ」の１つとなります。IRはIPアドレス空間を下位のIRまたは顧客に分配し、その分配をデータベースに登録する責任を負います。JPNICは国別IR（NIR：National Internet Registry）の１つです。また、ISPはローカルIR（LIR：Local Internet Registry）となります。

　JPNICの上位にはAPNIC(Asia Pacific Network Information Center)があります。これは地域IR(RIR：Regional Internet Registry)の１つで、アジアパシフィック地域を担当します。さらにAPNICの上には、IPアドレス空間の元締めと言うべきIANA(Internet Assigned Numbers Authority)があります。

　最近では、国際非営利法人組織としてICANN(Internet Corporation for Assigned Names and Numbers)が設立され、現在、IANAはICANNの組織の中の一部となっています。

　(a) 割り振りと割り当て
　割り振り（allocation）とは、再配分用としてアドレス空間をIRに分配することです。割り当て（assignment）とはIRがエンドユーザに対し、割り振られたアドレス空間の一部（または全部）をエンドユーザのネットワークで利用するために分配することです。なお、ここで言うエンドユーザとはグローバルアドレスを固定でもらうエンドユーザのことになります。ダイヤルアップユーザはアドレス割り当てではなく、ISPのアドレスを借りている形になります。

　(b) 全インターネットの経路情報
　図10に示すように、ルーティングプロトコル的には、あるISPから外のインターネット全体にBGPで経路情報を広告するときは、JPNICから割り振られたアドレスブロックだけを広告すればいいことになります。このように、あるAS(Autonomous System)から外部には大きくまとまったアドレスブロックの経路情報を流すだけでよいので、インターネット上のルータの使用メモリやCPUの負荷などを減らすことができることになります。これがアドレス集約を行う大きなメリットの１つです。



　　　図10 インターネット上に流れる経路情報

（６）プライベートアドレスとNAT

　(a) グローバルアドレス
　グローバルアドレスとは、IRから割り当てられる全世界で唯一のアドレスのことで、インターネットに直接接続される装置に割り当てられます。グローバルアドレスの所在は、経路情報としてインターネット上に伝わりますので、インターネットのどこからでもグローバルアドレス宛のIPパケットは目的地に到達できます。

　通常、IPの通信ではIPパケットを受け取ると、そのパケットの送信元アドレスを宛先アドレスにして応答します。従って、グローバルアドレスが割り当てられたホスト同士の通信は、行きも帰りも宛先アドレスがグローバルアドレスになりますから、特別な装置を介することなく通信することができます。

　(b) プライベートアドレス
　グローバルアドレスに対して、個別のネットワーク内部で自由に設定できるIPアドレス領域をプライベートアドレスと言います。プライベートアドレスについてはRFC1918に詳しく書かれており、IANAは表2に示す３つのIPアドレス空間ブロックをプライベートアドレスのために予約しています。


　　　　　　　　表２　３つのプライベートアドレス空間

　これらのプライベートアドレスは各組織で自由に使用可能で、IRからの割り当てを受ける必要がありません。また、プライベートアドレスは、インターネットにおいて唯一でなくてよく、ある組織と別の組織で同じアドレスが使用可能です。そのため、プライベートアドレスに関しては、経路情報をインターネット上に伝えることはできません。よって、プライベートアドレスが割り当てられたホストは、直接インターネットと通信することはできません。

　(c) NAT
　プライベートアドレスが割り当てられたホストがインターネットと通信するためには、プライベートアドレスのネットワーク（例えば社内ネットワーク）からインターネットへ出るところにNAT(Network Address Translation)と言う装置を入れます。

　NATの装置（NAT　boxと呼ばれる）は、パケットがプライベートアドレスのネットワークから外部に出る際に、送信元アドレスを内部のプライベートアドレスから外部のグローバルアドレスに付け替えます。そして、その応答パケットが外部から来たとき、NATはその宛先アドレスをグローバルアドレスから元のプライベートアドレスに戻します。

　つまり、NATではプライベートアドレスとグローバルアドレスの対応関係を管理しています。これによって、プライベートアドレスが割り当てられたホストからインターネットへのアクセスを可能にします。NATの装置にはNAT専用装置もありますが、ルータやファイヤーウォールのNAT機能を利用したり、PCやWSなどにNATの機能を入れて使用したりすることもよくあります。

　(d) NAPT
　上記のようにIPアドレスだけを変換する方法では、パケットヘッダにある送信元と宛先のIPアドレスだけを識別するため、プライベートアドレスとグローバルアドレスの対応は常に１対１でなければなりません。このため１つのグローバルアドレスを使用して外部にアクセスできるノードは、ある時点で１つだけに制限されてしまいます。

　これに対して現在一般的に使用されているものは、送信元IPアドレス、宛先アドレスの他に、送信元TCP/UDPポート、宛先TCP/UDPポートの対応関係を管理することで、１つのグローバルアドレスで複数のプライベートアドレスのホストが同時に通信できるようにする仕組みです。

　この機能はNAPTと呼ばれRFC2663に詳しく書かれています。また、この機能はLinux用語であるIPマスカレードと呼ばれることもあります。また、「PAT」「NAT+」「マルチNAT」と呼ばれることもあります。狭義にはNATとNAPTは別のものですが、広義にはNAPTを含めてNATと呼ばれることもあります。

　(e) NATを使用する場合の注意点
　NATやNAPTを使用することにより、データの中にIPアドレスやポート番号を含むアプリケーションや、逆方向（インターネット側からプライベートアドレス側）でアクセスし直すようなプロトコル（例えばFTP data）について、使用できない場合もあるので注意する必要があります。

　また、インターネットからプライベートアドレス側に向けてコネクションを張るようなことは基本的にできません。最初のコネクションを張ろうとするパケットが届かないからです。逆に言えばセキュリティの強化という利点にもつながります。

（７）IPv6

　IPv4アドレスの枯渇問題に対する長期的解決策としてIPv6があります。IPv4のアドレスは32ビットなので2³²個（約43億個）のアドレス空間ですが、IPv6のアドレスは128ビットなので2¹²⁸個（約340澗個、澗=10³⁶）のアドレス空間があります。

　IPv6のアドレス空間はほぼ無限なため、プライベートアドレスを使用するためのNATも不要になります。従ってIPv6の普及により、双方向接続が可能になるという大きなメリットがあります。また、セキュリティについてもIPv6にはIPsecが標準装備されているため、end-to-endでの安全な通信が可能になります。

[出典]
　(1) 友近剛史他２：インターネットルーティング入門，翔泳社（2002-1）

　以上、IPとルーティングについてまとめました。次回はルーティングの概要についてまとめる予定です。

　今回はルーティングの概要についてまとめました。

２．ルーティングの概要

２．１ デフォルトルート

　デフォルトルートとは、ルータに来たパケットの宛先アドレスがルーテイングテーブルに登録さていなかった場合に、そのパケットをどこに送ればよいかを指定するものです。ルーテイングテーブルに載っているアドレス以外はすべてデフォルトルートに転送するように指定されます。言い換えると、デフォルトルートとはルーテイングテーブルを検索する際に、必ず最後にマッチする経路であるということになります。

　デフォルトルートは、ルーテイングテーブルで通常「0.0.0.0/0」として表現し、設定するルータより１ホップISP側にあるルータをネクストホップに設定することが多いです。

２．２ スタティックルーテイングとダイナミックルーテイング

（１）スタティックルーテイング

　スタティックルーテイングとは、人間が直接手でルータにデータを入力し、ルーテイング情報を固定で設定する方法です。ネットワーク管理者がネットワーク構成を把握した上で、手作業でルーテイングテーブルを設定します。実際の設定では、ルータにコンソールをつなげて設定、telnet経由で遠隔設定、Webブラウザを使って設定など、方法は様々です。

　多くのネットワークに対しては設定が大変ですが、デフォルトルートを効果的に使用できるときは少ない設定ですみます。実際のパケットはルーティングテーブル設定後、そのテーブルに従って転送されます。

（２）ダイナミックルーティング

　ダイナミックルーティングとは、ルータ同士が話し合ってネットワークなどの情報（経路情報）をやりとりし、自動的にルータでルーティングテーブルを作成する方法です。ルータ間で行われるやりとりの方法を規定しているものを、ルーティングプロトコルと言います。ルーティングプロトコルにはOSPF、RIP、BGPなどがあります。

　図11にOSPFを話すルータによるダイナミックルーティングの例を示します。



　　　　　図11 ダイナミックルーティング

�@ ルータFは自分のところに198.168.10.0/24があると把握しており、その経路情報をネットワークに伝えようとします。

�A その経路情報がルータFからダイナミックルーティングプロトコルを通じて隣のルータDに伝わります。

�B ルータDではその経路情報を受けて、宛先が192.168.10.0/24のパケットはルータFの方に転送するように自分のルーティングテーブルに書き加えます。

�C さらに、ルータDは192.168.10.0/24に関する経路情報をルータCやルータEに伝えます。

�D ルータCやEでは、それを受けて宛先が192.168.10.0/24のパケットはルータDに転送すればよいと分かり、そのように自分のルーティングテーブルに書き加えます。

�E ルータCはさらにルータAにその経路情報を伝え、ルータAではそれを受けて自分のルーティングテーブルに同様に書き加えます。

　実際には192.168.10.0/24以外にもネットワークはたくさん存在する場合がほとんどで、その場合、各ネットワークに対して上記と同様に動作します。図11のようなネットワークを構築した最初の時に、ダイナミクルーティングプロトコルによってルーティングテーブルが作成され、その後パケットはルーティングテーブルに従って転送されます。ダイナミックルーティングのポイントは、経路情報と実際のデータパケットの向きが逆になることです。

（３）スタチックルーティングとダイナミックルーティングの比較

　(a) スタチクルーティングの短所

　第一に、大規模なネットワークの場合に設定管理が困難なことが挙げられます。デフォルトルートやネットワークのアドレス集約が有効に活用できない場合、すべてのルータですべてのネットワークに向けて手作業で設定することになります。また、初期設定だけでなく、ネットワーク構成を変更する場合も大変になります。

　第二の短所として、動的に経路を変更することが不可能であることが挙げられます。例えば中継ルータ間で回線切断などの障害が起こっても、発信元ルータはではそれを認識しないので、バックアップ経路に切り替わることができません。従って、パケットは目的地にたどり着けません。

　(b) ダイナミックルーティングの短所

　第一に、ルータでダイナミックルーティングを動かすためルータに負荷がかかります。大規模で複雑なネットワークの場合問題になることがあります。

　第二に、ルータ間で経路情報のやりとりをするため、ダイナミックルーティング自体のトラフィックが発生することです。

　例えば、ダイヤルアップルータでトラフィックが発生したときだけISDN回線や電話回線をつなげるような設定（よくある設定）の場合、ユーザが回線を使用していないときもダイナミックルーティング自体のトラフィックが発生して回線がつながり、電話料金を多く取られてしまいます。

　表3にスタティックルーティングとダイナミックルーティングの比較をまとめて示します。


　　　　　表3スタティックルーティングとダイナミックルーティングの比較

２．３ ルーティングプロトコルの種類

（１）ASとは

　「AS」とはインターネットの構成単位であり、各ASはそれぞれの運用ポリシーを持っています。一般的に、ASの多くはISPであり、学術系ネットワークがASであることもあります。AS同士が各種の形態で接続されてインターネットが形成されています。

　ASは「Autonomous System」の略で、「自律システム」と訳すことができます。なお、ISPや学術系ネットワーク以外の組織でも、条件を満たせばASになることはできます。

　(a) AS番号
　各ASは、AS番号という世界で一意な番号を持ちます。AS番号は1〜65535の範囲で表されます。このうちAS番号1〜64511はグローバルAS番号で、グローバルIPアドレスと同様にインターネットレジストリによって管理され、一意に割り当てられます。

　一方、AS番号64512〜65535はプライベートAS番号のために確保されています。プライベートAS番号は、IPアドレスにおけるプライベートIPアドレスと同様のもので、これらの番号は、個別のAS内部で自由に使用することができます。しかし、AS外にその情報を流してはいけません。

　(b) IGPとEGP
　ダイナミックルーティングのプロトコルは、大きく分けてIGP(Interior Gateway Protocol)とEGP(Exterior Gateway Protocol)に分類されます。IGPはAS内部で、EGPはAS間で使用されます。

　(c) IGP
　IGPはAS内部で使用されるルーティングプロトコルで、OSPF(Open Shortest Path First)、RIP(Routing Information Protocol)などの一般的なものや、OSIスタックのIS-IS(Intermediate System-to-Intermediate System)、Cisco社独自のIGRP(Interior Gateway Routing Protocol)などがあります。

　(d) EGP
　EGPはAS間で使用されるルーティングプロトコルで、現在使用されているものにBGP(Boarder Gateway Protocol)があります。

　図12にこれらのルーティングプロトコルをまとめて示します。



　　　図12 EGPとIGPの各種プロトコル

　(e) アルゴリズム
　これらのルーテイングプロトコルを、使用するアルゴリズムで分類すると図13のようになります。



　　図13 ルーティングプロトコルの各アルゴリズム

[出典]
　(1) 友近剛史他２：インターネットルーティング入門，翔泳社（2002-1）

　以上、ルーティングの概要についてまとめました。次回はルーテイングプロトコルの１つであるOSPFについてまとめる予定です。

　今回はルーテイングプロトコルの１つであるOSPFの概要についてまとめました。

３．OSPF

３．１ OSPFの概要

（１）OSPFの概要と特徴

　OSPFはAS内部で使用されるIGPの１つで、RIPと同様に多くの場所で使われているルーティングプロトコルです。現在、一般的に使用されているのはOSPF Version2で、RFC2328で標準化されています。

　RIPに比べると、OSPFより歴史が長いことや、サポートするルータやホストが多いなどの理由により、エンドユーザではRIPが使われていることが多いようです。しかし、最近ではOSPFのメリットが注目され、大規模ネットワークを初めとする多くの場所でOSPFが使われています。

　OSPFは「Open Shortest Path First」の略で、Shortest Path First(SPF)アルゴリズムに由来する名前です。OSPFの特徴としては次のものが挙げられます。

　・リンクステートアルゴリズムを採用し、素早い収束性を実現
　・コストに基づいたルーティング
　・VLSMのサポート
　・エリアの使用による高いスケーラビリティの実現
　・イコールコストマルチパスのサポート
　・DRとBDRの概念
　・マルチキャストの使用
　・認証のサポート

（２） リンクステートルーティングプロトコル

　OSPFはリンクステートアルゴリズムを使用したルーティングプロトコルです。ルータはリンクステートと呼ばれるメッセージを出します。図14に示すように、リンクステートにはルータが接続しているリンク（ルータに直接接続されたメディア）の状態や、そのリンクのネットワークアドレス、コストなどの情報が入っています。



　　　図14 リンクステートアルゴリズム

　このようにリンクステートには、あるルータがどのリンクにどのように接続しているか、と言う情報が書かれています。リンクステートを受け取ったルータでは、その情報に基づいてネットワーク構成を把握します。そして、ネットワーク構成を表す表を構築します。

　いわば、各ルータが全ルータとリンクの構成を把握した地図を持っているようになります。このネットワークを表す表を「リンクステートデータベース（トポロジカルデータベース）」と言います。

　各ルータは、このデータベースからShortest Path Firstアルゴリズムを用いて、自身をroot（始点）とした最短パスツリーを作成します。そして最後に、最短パスツリーからルーティングテーブルを作成します。

　リンクステートアルゴリズムの大きなメリットとして、各ルータがネットワーク構成を把握していることにより、ネットワーク構成が変化した際に、素早くルーティングテーブルを再構築することができます（素早い収束性）。このことは、大きなネットワークで安定して運用できることにつながり、OSPFはスケーラビリティ（規模対応性）に優れていると言えます。

（３）OSPFによるダイナミックルーティング

　[メトリック]
　メトリックとは、宛先ネットワークとの距離を表すパラメータ（計測単位）を示す一般用語です。同じネットワーク（同じプレフィックス）の経路情報が複数方向から来た場合、つまりそのネットワークにたどり着くのに複数の経路がある場合、ルータはメトリックが小さい経路の方が近いと判断し、そちらの方にパケットを転送します。OSPFではコストという値をメトリックとして用います。

　[コスト]
　コストは、ネットワーク管理者が各ルータのインタフェースで設定します。そして、リンクステートがルータのインタフェースを通過するときに足されていきます。

　図15に例を示します。管理者は、ルータDとルータEの右側のインタフェースでのコストを「10」とし、ルータBの右側のインタフェースでのコストを「5」、ルータCの右側のインタフェースでのコストを「20」、ルータAの右側のインタフェースでのコストを「10」としました。



　　　　　　　　　図15 OSPFにおけるコスト

　この場合、192.168.2.0/24のネットワークの情報が含まれるリンクステートは、ルータD→ルータB→ルータAと、ルータE→ルータC→ルータAと言う方向で流れてきます。前者はコストが10+5+10=25、後者はコストが10+20+10=40となっています。従って、ルータAはコストの小さい前者を選択し、ルーティングテーブルに載せます。その結果、ルータAに192.168.2.0/24宛のIPパケットが来た際には、ルータAはルータBに転送します。

　[バックアップ経路]
　図15の例で、上のリンクが切れた場合下の経路を選択することになります。従って、２本の経路がある場合には、コストの低い方がメイン経路、コストの高い方がバックアップ経路となります。

　[イコールコストマルチパス]
　OSPFはイコールコストマルチパスをサポートします。「イコールコストマルチパス」とは、その名の通りコストが同じ場合、複数の経路を選択することです。等コストの経路がn本ある時は、データトラフィックを各経路に1/nずつ転送します。このようにトラフィックを分散させることを、ロードバランスまたはロードシェアリングと言います。また、ロードバランス時も、経路の１本に切断などの障害が起こったら、その経路がルーティングテーブルから消え、トラフィックは残りの経路の方に行きます。

　[ロンゲストマッチ]
　すべてのルーティングプロトコルで、ルータにIPパケットが来た際に宛先アドレスを調べて、マッチするネットワークアドレスが複数ある場合には、通常プレフィックス長が長い方のネットワークアドレスを選択し、転送されます。これを「ロンゲストマッチ（longest match：最長一致)の規則）と言います。

　なお、前述のメトリックやコストは、プレフィックス長を含めて同じネットワーク、つまり全く同じプレフィックスが複数ある時に、どれをルーティングテーブルに載せるかを比較するものです。ここで述べているのは、ネットワークのアドレス部分は同じですがプレフィックス長が違うときのことで、違うプレフィックスですからコストで比較することなく両方ともルーティングテーブルに載るわけです。

（４）エリア

　OSPFを適用したネットワーク上のすべてのルータは、各ルータが発信したリンクステートをもとに作成したリンクステートデータベースを持ちます。そのため、ネットワークが大規模になればデータベースのサイズが膨大になり、ネットワーク上を飛び交うリンクステートの数も増えます。そこでOSPFには図16に示すように、ネットワークをエリアと呼ぶ論理的な単位に細分化して運用管理できる仕組みが備わっています。



　　　図16 エリア

　各エリアのルータは、全部のネットワーク構成ではなく、自分の所属するエリア内だけのネットワーク構成が分かるリンクステートデータベースを持ちます。自分のエリア外のネットワークについてはネットワーク構成までは把握せず、自エリアのエリア境界ルータの内どのルータの向こう側にあるかのみを把握するようにします。

　以上の仕組みにより、リンクステートデータベースのサイズが小さくなり、ルーティングテーブル作成時の演算も少なくて済み、エリア内のリンクステートのトラフィック量も少なくできます。これによって、OSPFは高いスケーラビリティを実現しています。

　各エリアは32ビットのエリアIDで区別されます。IDの付け方はIPアドレス風（例：Area 0.0.0.1）、単なる数（例：Area 1）など様々です。

　[バックボーンエリア]
　エリア間はバックボーンエリアと呼ぶ特別なエリアを介して相互に接続します。従って、OSPFではバックボーンエリアに他のすべてのエリアがぶら下がるような二階層構造をとることになります。バックボーンエリアは「Area 0」または「Area 0.0.0.0」で表します。また、エリアが１つだけのネットワークは、すべてがバックボーンエリアになります。

　[エリア境界ルータ]
　複数のエリアに属するルータは、エリア境界ルータ（ABR：エリアボーダールータ）と言います。エリアは必ずバックボーンエリアと接続されるため、エリア境界ルータは必ずバックボーンエリアにも属すことになります。

　[スタブエリア]
　他のルーティングプロトコルで発生し、それをOSPFルーティング領域に再配信した経路をAS-external経路（または単にExternal経路）と言います。スタブエリア（stub area）とは、AS-external経路が流れないようにした特殊なエリアです。

　スタブエリアがない場合、AS-external経路はすべてのOSPFルーティング領域に流れます。時にはAS-external経路が膨大になり、リンクステートデータベースの多くがこれらの経路で占められることがあります。スタブエリアはこれを回避するためのものです。スタブエリア内のルータはAS-external経路情報を持たないため、その分リンクステートデータベースのサイズを小さくでき、ルータに必要なメモリも少なくて済みます。

　スタブエリアに属するエリア境界ルータは、スタブエリアの中に向けてデフォルトルートを広告します。これは、「デフォルトルートを自分（エリア境界ルータ）に向けろ」という経路情報を他のルータに伝えることです。それにより、スタブエリア内のルータはデフォルトルートであるエリア境界ルータに向けてパケットをフォワードします。

　デフォルトルートによってOSPFルーティング領域以外のネットワークへの到達性が確保されるわけです。従って、スタブエリアは出口が１つ（エリア境界ルータが１つ）であるエリア、またはパケットの宛先アドレス毎にエリアの出口を選択する必要のないエリアで使われます。また、スタブエリア内にはAS境界ルータが置けません。

　[NSSA]
　[NSSA]とは「Not So Stubby Area」の略で、準スタブエリアとも呼ばれます。OSPF自体の規定であるRFC2328ではなく、RFC1587”The OSPF NSSA Option”で規定されています。NSSAはAS境界ルータを置けないスタブエリアの制限を回避する仕組みで、AS-external経路情報は必要ないがAS境界ルータを置きたい、というエリアに使われる特別なエリアです。

　[エリアの設計]
　中規模以下のネットワークでは特にエリアを分ける必要はありませんが、大規模で複雑なネットワークではエリアを分けることが必須になります。その区分は、ルータの台数、ネットワーク構成の複雑さ、ルータの処理能力、ネットワークの安定性など様々な要素が関係するので一概には言えません。

　日本全国各地のLAN同士がWANでつながっているような大規模なネットワークにおいては、まず中心部分のWAN部分をバックボーンエリアにし、LAN部分を他エリアにしてユニークなエリアIDを与えていくようにします。

　ISPなどの高い信頼性を必要とするネットワークであれば、リダンダンシー（冗長性）確保のため、あるエリアをバックボーンエリアにつなげる際に複数のエリア境界ルータを置くべきです。また、できるだけ１つのエリア境界ルータが所属するエリアは２つまでにし、エリア境界ルータにおいてエリア毎の経路が集約できるように設計するべきです。

　[バーチャルリンク]
　すべてのエリアはバックボーンエリアに接続している必要がありますが、物理的にエリアをバックボーンに接続することが困難な場合があります。この場合、バーチャルリンクを用いて論理的に接続させることが可能です。バーチャルリンクは、バックボーン以外の共通のエリアにインタフェースを持つ任意の２つのルータ間で設定可能です。バーチャルリンク自体はバックボーンエリアに属しており、バックボーンエリアを張り出すものと言えます。

（５）DR

　[AdjacencyとNeighbor]
　OSPFでは、リンクステートの交換は同じネットワークセグメントに所属したルータ同士で行いますが、すべてのルータ同士で行うわけではありません。リンクステートを交換するルータのペアの関係を「Adjacency(Adjacent関係：隣接関係)」と呼びます。一方、同じネットワークセグメントに所属したルータのペアの関係を「Neighbor」と呼びます。つまり、Neighborであるルータのペアは、必ずしもAdjacencyにはならないと言うことです。

　Neighborの関係であるルータ同士は、Helloプロトコルのやりとりを定期的に行います。HelloプロトコルによりNeighbor関係を確立し維持します。マルチアクセスネットワークではHelloプロトコルによりDRを選出し、これによりAdjacencyがどのルータ同士になるかが決まります。そして図17に示すように、Adjacency担ったルータ同士はリンクステートの交換を行います。



　　　　図17 AdjacencyとNeighbor

　[DR]
　「DR」はDesignated Routerのことで指名ルータと呼ばれます。OSPFは、すべてのマルチアクセスネットワークにおいて必ず１つだけのDRを持ちます。DRは同一ネットワークの他の全ルータとAdjacencyとなり、リンクステートの交換を行います。DRでもBDRでもないルータ同士はAdjacencyとはなりません。これは、リンクステート自体のトラフィックを減らすためです。DRはいわば、ルータ間の情報交換の中心拠点の役割を果たします。

　Adjacentなルータはリンクステートの交換をし、それぞれのリンクステートについてどちらが新しい情報を知っているかを比較し、リンクステートデータベースを同期し、新しく知った情報はさらに他のルータへ知らせます。このことをflooding手続きと言います。

　DRは大事なルータであるため、ネットワーク管理者は信頼性のあるルータをDRにするべきです。ISP等の大規模なネットワークではDRはかなりな負荷がかかりますので、これを考慮に入れてDRを決めた上で、ネットワークを設計する必要があります。

　[BDR]
　マルチアクセスネットワークにおいてDRは１台しかありません。よって、DRがダウンした際には、新たなDRを選択してリンクステートの交換からflooding手続きを行うことが必要になってきます。しかし、これには多くの時間がかかり、長い時間の通信断絶となりかねません。

　そこで、DRの障害時に新たなDRへの移行をスムーズに行うために、各マルチアクセスネットワークには１つのBDR(Backup Designated Router：バックアップ指名ルータ)が存在します。BDRもDRと同様に同一ネットワークの他の全ルータとAdjacencyとなります。DRが故障しても同じ情報をBDRが持っているため、DRの移行を最小限の時間で達成することができます。

　BDRはDRと比較すると、flooding手続きにおいていくつかの役割をDRに任せることで、リンクステートのトラフィックを減らすようにしています。また、DRのもう１つの大きな役割であるネットワークLSAの生成はBDRでは行いません。

（６）その他の特徴

　[VLSMに対応]
　OSPFはVLSMに対応しています。従って、OSPFではネットワークの規模に見合うプレフィックス長を設定できるため。IPアドレスを無駄に使用することを避けられます。

　[リンクステートのアップデートのタイミング]
　リンクステートは、30分に一度の定期的なリフレッシュを除くと、ネットワーク構成が変更になったときだけリンクステートのアップデート（Link-state Updateパケット）が送信されます。これによって、OSPFのルーティングプロトコル自体で発生するトラフィックと、ルータで行う処理を軽減しています。

　[プロトコル]
　RIPはUDP上、BGPはTCP上で動作しますが、OSPFはそれらと異なり、IPを直接使用します。IPプロトコル番号は「89」を使用します。

　[マルチキャスト]
　OSPFのメッセージは、ルータ間でIPマルチキャストを使用することができます。例えば、イーサネットなどのブロードキャストネットワークでのHelloパケットは、マルチキャストでAIISPFRoutersというマルチキャストアドレス（224.0.0.5）に送信されます。OSPFを話しているルータは、このアドレスのパケットを受け取らなければなりません。

　また、DRとBDRは、Link-state UpdateパケットとLink-state Acknowledgmentパケットを、やはりマルチキャストアドレスAIISPFRoutersに送信します。逆に、DR、BDR以外の全ルータはLink-state UpdateパケットとLink-state AcknowledgmentパケットをマルチキャストアドレスAIIDRouters（224.0.0.6）に送信します。DRとBDRはこのアドレスのパケットを受け取らなければなりません。

　[TOSに基づいた経路制御]
　1994年3月のRFC1583では、OSPFでIPパケットの各TOS(Type of Service)について独立した経路を計算することを規定していました。しかし、ほとんど使用されなかったこともあり、1997年7月のRFC2178ではTOSルーティングのオプションは削除されました。ただ、以前との互換性を保つために、OSPFのパケットフォーマットにはTOSを考慮するフィールドが残されています。これは現在のRFC2328でも同様です。

　[認証]
　OSPFは、ルータ間でOSPFルーティングプロトコルの情報交換について、認証を行わせることができます。認証には多様な機構を使用することができます。実際、各ネットワークセグメントについて違った認証機構を設定することが可能です。

[出典]
　(1) 友近剛史他２：インターネットルーティング入門，翔泳社（2002-1）

　以上、ルーテイングプロトコルの１つであるOSPFの概要についてまとめました。次回はOSPFのルーティングテーブル作成の過程についてまとめる予定です。

　今回はOSPFのルーティングテーブル作成の過程についてまとめました。

３．２ ルーティングテーブル作成の過程

（１）リンクステートデータベースの作成

　(a) リンクステートデータベース

　リンクステートデータベースとは、ネットワークの情報を図18に示すような表の形にまとめたものです。この表は、ルータとルータ、あるいはルータとネットワークの間を辺で結んでその関係を表すグラフ構造を持っています。



　　　　　図18 リンクステートデータベース

　(b) ネットワークのタイプや接続ルータ数による表現の仕方

　リンクステートデータベースは、ネットワークのタイプ（P-P、ブロードキャスト、マルチアクセス等）やネットワークに接続するルータの数によって異なる表現方法があります。

　図19はトランジットネットワークの例です。「トランジットネットワーク」とは、マルチアクセスネットワークで２台以上のルータが接続されている状態のことで、リンクステートデータベースのグラフは双方向になります。従って、ルータからネットワークの向きでも、ネットワークからルータへの向きでも辺で結ばれます。



　　　図19 トランジットネットワーク

　図20はスタブネットワークの例です。「スタブネットワーク」とは、ルータが１台しか接続されていないネットワークのことで、リンクステートデータベースのグラフはルータからネットワークへ向けての片方向になります。



　　　図20 スタブネットワーク

　図21はPoint-to-Point(P-P)ネットワークで２つのルータが物理的に結ばれている例です。リンクステートデータベースのグラフは、２つのルータが双方向の辺で結ばれる形になります。これはunnumbered（インタフェースに専用のIPアドレスを割り当てる必要がないリンク）に対応しやすいようにするためです。インタフェースにIPアドレスが割り当てられた場合は、それをスタブリンクとみなし、ルータから対向するルータのインタフェースに向けて、片方向の辺で結ばれる形になります。



　　　図21 Point-to-Pointネットワーク

　(c) リンクステートデータベースの例

　図22に１つのエリアのネットワーク構成図とリンクステートデータベースの例を示します。この図は次のような状態を表しています。

　・ルータ間の線はP-Pネットワークを表します。
　・RT5とRT7はAS境界ルータであり、BGPのコネクションをOSPF外に持ちます。
　・「H」はホストを表しています。従ってH1につながるRT12はホストルート（/32の経路）を流しています。
　・P-Pネットワークの内インタフェースにアドレスを割り当てたのはRT6とRT10だけです。



　　　図22 １つのエリアにおけるリンクステートデータベースの例

　(d) コストの値

　実際のリンクステートデータベースでは、行と列で交差する部分に「X」ではなくコストの値を入れます。前述のように、コストはリンクステートがルータに入ってくるところで効きます。リンクステートとデータトラフィックの向きは逆であり、データトラフィックの観点から見ると、コストはルータインタフェースからデータトラフィックが出るところで効くことになります。

　また、リンクステートデータベースのグラフの向きはデータトラフィックの向きと同じです。従って、コストはデータベース表の「FROM」欄に表記された各ルータの列に、そのインタフェースのコスト値を入れます。また、ネットワークからルータへ向けてはコスト「0」となります。

　(e) LSA
　LSAとは5種類のOSPFパケットの内、Type4にあたるLink-state Updateパケットに含まれるLink-State Advertisement（リンクステート広告）を指します。LSAはルータやネットワークの状態を記述したデータです。表4に示すように、LSAには5種類のTypeがあります。


　　　　　　　　　　表4 LSAの種類

　(f) LSAからリンクステートデータベースが作成される様子

　図23にLSAからリンクステートデータベースが作成される様子を示します。図の右下にLS Type1であるRouter-LSAからリンクステートデータベースの一部を作成した例を示します。Router-LSAはルータに接続されているネットワークの情報を伝えます。RT12からのRouter-LSAによって、RT12がN9、N10、H1に接続されていることと、それらに接続しているインタフェースのコストが分かります。その情報からリンクステートデータベースの一部が作成されます。



　図23 LSAからリンクステートデータベースが作成される様子

　また、図の右上にLS Type2であるNetwork-LSAからリンクステートデータベースの一部を作成した例を示します。Network-LSAはそのネットワークに接続しているすべてのルータの情報を伝えるので、N9がRT9、RT11、RT12に接続されていることが分かります。従ってリンクステートデータベースの一部が作成されます。

　このようにLSAを集めていくと、リンクステートデータベースになるわけです。

（２）リンクステートデータベースからのルーティングテーブルの作成

　(a) 自身をrootとした最短パスツリーの作成

　リンクステートデータベースが作成されると、そこからルータは自身をrootとした最短パスツリー（Shortest Path Tree）を作成します。そのときに使用されるアルゴリズムがSPFアルゴリズム（Dijkstraアルゴリズム）です。

　図24にリンクステートデータベースから作成される最短パスツリーを示します。ここではRT6が作る最短パスツリーの例を示しており、RT6がrootになっています。SPFアルゴリズムは「すべてのノードの中でコストが最小のノードを確定し、そのノードから次のノードを加えていく」ことを繰り返すだけで非常に単純です。



図24 リンクステートデータベースから作成される最短パスツリー

　[１回目のステップ]
　RT6自身がrootになるので始点にRT6を置きます。そして、リンクステートデータベースからRT6の次のノードを選びます。FROM欄がRT6の列を見ると、RT3、RT5、RT10、Ibが存在します。従って、それらをコストとともに最短パスツリーに書き加えます。この時点で確定しているのはRT6自体だけです。そして、SPFアルゴリズムの１回目の選択が始まります。

　「すべてのノードの中でコストが最小のノードを確定する」とは、最短パスツリーのリーフにあるノードの中でコストが最小であるものを確定していくということです。この段階ではコストの最小は「6」なので、コストが「6」であるRT3とRT5を確定します。

　[2回目のステップ]
　先ほど確定したRT3とRT5の次のノードを探します。FROMがRT3の列を見ると、RT6、N3、N4が存在します。ただし、RT6はすでに確定しているため対象外と考えます。従って、N3とN4を次のノードと考えてコストとともに最短パスツリーに書き加えます。

　ネットワークからルータへのコストは「0」なので、ネットワークの場合、次のノードも一緒に考えることにします。そこで、リンクステートデータベースからFROMがN3とN4の列があるかどうか探します。すると、FROMがN3の列が存在し、そこにはRT1、RT2、RT3、RT4が存在すると分かります。ただし、RT3はすでに確定しているため対象外と考えます。

　従って、RT1、RT2、RT4を次のノードと考えて、最短パスツリーに書き加えます。N4についてはFROMに存在しないのでそこでツリーは終わります。これはN4がスタブネットワークであることを意味します。

　一方、FROMがRT5の列を見ると、RT4、RT6、RT7、N12、N13、N14の６つが存在すると分かります。ただし、RT6はすでに確定しているため対象外と考えます。従って、RT4、RT7、N12、N13、N14の５つをコストとともに最短パスツリーに書き加えます。さらに、ネットワークについて次のノードを探しますが、ここではN12、N13、N14の３つともFROMにないので、その先のノードはないことが分かります。

　次に、SPFアルゴリズムの２回目の選択が始まります。１回目の最小コスト「6」を超える最小のコストのリーフを探します。ここでは、コスト「7」が最小で、対象はN3、RT1、RT2、RT4、RT10、Ibとなります。従ってこれらを確定します。

　さらに、確定したノードと同じノードが他の場所にあれば他の場所のものを消去します。ここでは、RT4がすでに確定した場所（N3の左側）以外に存在する（左上側：RT5の次）ので、そのRT4を消去します。

　[3回目のステップ]
　先ほど確定したN3、RT1、RT2、RT4、RT10、Ibの次のノードを探します。N3は２回目のステップで次のノードを探し終えていますし、Ibはインタフェースなので、対象はRT1、RT2、RT4、RT10の４つになります。

　FROMがRT1の列を見ると、N1とN3が存在します。ただし、N3はすでに確定しているため対象外と考えます。よって、N1をコストとともに最短パスツリーに書き加えます。また、N1がFROMにないので、N1の先は無いことが分かります。FROMがRT2の列も同様にして、N2をコストとともに最短パスツリーに書き加えます。

　FROMがRT4の列を見ると、RT5とN3が存在します。ただし、RT5もN3もすでに確定しているため対象外と考えます。従って、RT4の先はないことが分かります。

　図24を見ると、実際にはRT4はリング状のネットワーク構成の中にあります。しかし、２回目のステップにおいて、RT6から見て時計回り（RT3→N3経由）の経路の方を選択し、反時計回りの経路（RT5経由）は消去したため、RT5とRT4の間のリンクが消去した形となり、時計回りでRT3→N3→RT4の先は無いことになっているわけです。このようなことが次々に起こり、実際は複雑なトポロジーの網でも最終的にツリーで表現することができるわけです。

　続いて、FROMがRT10の列を見るとRT6、N6、N8、Iaが存在します。ただし、RT6はすでに確定しているため対象外と考えます。従って、N6、N8、Iaをコストとともに最短パスツリーに書き加えます。さらに、N6とN8についてはFROMにあるので、同様にリンクステートデータベースを見て、N6の先にはRT7とRT8、N8の先にはRT11を最短パスツリーに書き加えます。

　次にSPFアルゴリズムの３回目の選択が始まります。２回目の最小コスト「7」を超える最小コストのリーフを探します。ここでは、コスト「8」が最小で対象はN6、RT7、RT8となります。従って、これらを確定します。

　さらに、確定したノードと同じものが他にあれば消去します。ここでは、RT7がすでに確定していた場所（N6の右側）以外に存在します（左上側）ので、そこのRT7を消去します。これで３回目の作業は終了します。

　以上のような動作を繰り返すことによって、SPFアルゴリズムは、リンクステートデータベースから最短パスツリーを構築するわけです。

　(b) 最短パスツリーからルーティングテーブルの作成

　最短パスツリーからルーティングテーブルを作成することは非常に簡単です。自分のルータから対象となるネットワークまでの最短パスツリーにおける次のルータを示せばいいだけです。図25にRT6において、最短パスツリーからルーティングテーブルが作成される様子を示します。



図25 最短パスツリーからルーティングテーブルが作成される様子

[出典]
　(1) 友近剛史他２：インターネットルーティング入門，翔泳社（2002-1）

　以上、OSPFのルーティングテーブル作成の過程についてまとめました。次回はルーティングプロトコルの１つであるRIPについてまとめる予定です。

　今回はルーティングプロトコルの１つであるRIPについてまとめました。

４　RIP

４．１ RIPの歴史と概要

（１）RIPの概要

　RIP(Routing Information Protocol)の原理は、インターネットの元祖であるARPANET時代から使われてきました。RIPはいわば最初の世代のルーティングプロトコルです。そんなに古いプロトコルがまだ使われているのは、RIPが簡素なプロトコルであるため使うのも実装するのも容易だからです。ホスト数が数十の大きさのネットワークであれば、RIPは良い選択肢となり得るでしょう。

（２）RIPの歴史

　RIPは他のプロトコルと異なり、特に標準という規定がないまま実装されてきました。それぞれの実装は色々な点で細かい動作が異なります。1988年にRFC1058が規定されることにより、ようやく文書での標準といえる仕様が確定しました。このRFCは、4.3BSD UNIXで配布されデファクトスタンダードになったroutedというRIPの実装をベースに記述されています。

４．２ RIPの原理

（１）ディスタンスベクター型アルゴリズムの動作例

　(a) ディスタンスベクター型アルゴリズムの概要

　RIPは目的地までのホップ数（経由するルータの数）を距離と考え、目的のネットワークまで最もホップ数の少ない経路でパケットが配送されるように各ルータのルーティングテーブルを作る、ディスタンスベクター型のルーティングプロトコルです。図26にRIPによるルーティング例を示します。



　　　図26 ホップ数が最小になるルーティング

　(b) ディスタンスベクター型アルゴリズムの動作イメージ

　貴方がある国の秘密工作員だとしましょう。現在数十名の仲間と秘密作戦を展開しています。しかし、秘密工作員は捕らえられた時に仲間の情報を漏らすことがないよう、仲間についてほとんど知らされていません。仲間同士連絡を取り合う必要がある場合には、あなたが直接コンタクトを取ることのできる数人の仲間の誰かに、手紙を託すしかありません。

　あなたは仲間Zに伝えなければならないことがあり、Zに手紙を書きました。図27に示すように、あなたには手紙を渡すことのできる仲間が３人います。この仲間をA、B、Cとしましょう。あなたはA、B、Cの３人の誰かを選んで、Zへの手紙の転送を依頼します。手紙が確実に転送されるよう、仲間同士は次のような情報交換を行います。



　　　　　　　図27 仲間との情報交換

　あなたは、Aが誰に手紙を渡すことができるのかを、Aから聞きます。そうすると、Aは「DとEに直接渡すことができる」と言ってきました。同時に、あなたはAに対して、「BとCに直接渡すことができる」と伝えます。

　この情報交換により、Aは貴方経由でBとCに手紙を渡すことができることを知り、貴方はAを経由してDとEに手紙を渡すことができることを知りました。このAとの情報交換と同様に、BとCとも情報を交換します。

　しかし、情報交換はこれで終わりません。あなたがA、B、C３人に教えてもらった情報をすべて合わせて、「自分はBとCに直接渡すことができ、１人経由すればF、G、H、Iにもわたすことができる」と再度Aに教えます。これによって、Aは貴方経由でB、C、F、G、H、Iに手紙を届けることができるようになりました。

　同時に、Aも仲間DとEから聞いた情報を足して、あなたに「DとEに直接渡すことができ、１人経由すればZにも渡すことができる」と教えてきます。これで貴方もAを通してD、E、Zに手紙を渡してもらえることを知るのです。貴方は同様の情報交換をB、Cとも行います。

　すべての仲間はこの情報交換を定期的に繰り返します。そしてそれぞれ３人先、４人先と手紙を転送できる範囲を広げていき、最終的にどの仲間にも手紙を転送することができるようになるのです。

　さて、貴方は２巡目の情報交換で、Aに手紙を渡せばAがさらに誰かに渡して、その人が目的の仲間Zに直接渡してくれる、ということを知っています。そして３巡目の情報交換ではさらにBを経由してBの３人先にZがいることも知りました。貴方には仲間Zに手紙を渡すのに、Aに転送してもらう方法と、Bに転送してもらう方法の２つの選択肢があることになります。

　このとき、貴方はAとBのどちらに手紙を託すべきでしょうか。貴方が持っているZに関する情報は、「Aの２人先にいる」ということと、「Bの３人先にいる」ということの２つだけです。とすれば、少しでも早くZに手紙が届いたほうがいいので、仲間Zへの手紙はAに託すことにするでしょう。

　これが、ディスタンスベクター型アルゴリズムによる経路情報交換です。それぞれが手紙を渡すことができる仲間についての情報を交換し続けることで、すべての仲間がどの仲間にも手紙を転送することができるようになります。

　仲間同士の手紙の受け渡しが可能なルートがある場合は、このような情報交換によって確実に手紙を渡す方法を発見することができると数学的に証明されています。

（２）RIPの基本的な動作

　(a) RIPが繰り返す動作

　上記の工作員をルータに、手紙をIPパケットに置き換えれば、それがそのままRIPの基本的な動作となります。RIPによってルーティングテーブルを作ろうとするルータは、図28に示す手順を繰り返します。



　　　　　図28 RIPの基本動作

　・各ルータは、いくつのルータを経由した先にどんなネットワークがあるかというルーティングテーブル上の情報を、直接接続されているルータに定期的に送信する。

　・各ルータは、直接接続されたルータから教わったどのネットワークがいくつのルータを経由した先にあるかという情報を、自身のルーティングテーブルに付け加える。その際、そのネットワークへのネクストホップはその情報を教えてくれたルータにする。また、いくつのルータを経由した先にあるかという情報は、教わった情報に自分自身の分である「1」を足しておく。

　(b) タイマーとレギュラーアップデート

　各ルータはRIPの情報送信用にタイマーを持っており、タイマーは「0」から始まって１秒に「1」ずつ 値が増えていきます。ルータはタイマーを見張っており、タイマーが「30」になると持っている情報を隣接するルータに対して送信し、タイマーをまた「0」に戻してこの処理を繰り返します。こうして、定期的に情報を送信するという動作をするわけです。

　このような定期的なルート情報の送信を、RIPではレギュラーアップデートと呼びます。通常時の情報更新というような意味で、30秒ごとにそのルータのすべてのルート情報を隣接するルータにブロードキャストします。

　(c) メトリック、コスト、ホップカウント

　「どのネットワークがいくつのルータを経由した先にあるか」という情報をメトリックと言います。あるネットワークに関する情報が、ルータからルータへメトリックが「1」ずつ 増えながら伝わっていくことで、そのネットワークはいくつのルータを経由した先にあるかという情報を、各ルータは得ることができるわけです。この情報は何ホップ先にあるかという意味で、ホップカウント（ホップ数）とも呼ばれます。

　さて、ここでメトリックを増やす単位を「1」でなくしたらどうなるでしょうか。あるルータが例えばメトリックを「5」増やして次のルータに伝えるとすると、情報を伝えられたルータは、そのルートがとても遠くにあると判断します。そしてルートの選択に影響を与えることになるのです。

　このようにメトリックを増やす単位をコストと言います。多くの場合RIPではコストは常に「1」で、実装によってコストを「1」以外にできない場合もあります。なお、RIPではメトリック数を「15」までに制限しています。メトリックが「16」以上のネットワークは、RIPでは到達できない無限に遠いネットワークと判断します。

　(d) メトリックによるルート選択

　RIPの基本動作が全ルータで繰り返し行われることで、各ルータはすべてのネットワークへのネクストホップとメトリックを知ることになります。各ルータはこうして学習した経路情報の内、行き方が複数ある経路について、どの経路をルーティングテーブル上に採用するかを決めなければなりません。

　この場合、ルータは各経路のメトリックを比較します。そしてメトリックが小さい方を「より近く、好ましい」経路だと判断し、自身のルーティングテーブルに採用するのです。こうして、メトリック的に最小となる経路を各ネットワークに対して選択することができます。

　各ルータはこのように最適な経路を選択するので、ルータ（あるいはインタフェース）のコストを「1」よりも大きくすることで、そのルータ（あるいはインタフェース）を経由する経路のメトリックを意図的に大きくして、そこを経由する経路を選択されにくくすることができます。

　(e) ルート情報のタイムアウト

　ルータ間を結ぶ回線が切断された場合、何の対策もしなければルータはすでに作成したルーティングテーブルに従って、パケット転送を続けます。しかし、回線が切断されているルートではパケットが到達できません。

　このようなルートを捨て去り、新しいルートを選択し直すために。RIPでは前述のレギュラーアップデートを使用します。各ルータのルーティングテーブル上の各ルートには、個別にタイマーが付いており、１秒ごとにそれぞれ「1」ずつ 増加していきます。このルート毎のタイマーは、タイムアウトタイマーと呼ばれます。

　各ルータは、レギュラーアップデートなどでそのルートに関する情報を受け取ると、そのルートのタイムアウトタイマーを「0」にリセットします。従って、タイムアウトタイマーの値が小さいルートは、更新し続けられている有効なルートであり、この値が大きいルートは、情報更新されなくなった使用できないルートだと判断できるわけです。

　RIPでは、ルートの有効、無効の判断基準に180秒という時間を使用します。これは、30秒毎のレギュラーアップデートを６回連続受け取ることができなかった場合に相当します。タイムアウトタイマーが180秒より大きくなったルートは、ルーティングテーブルから取り除きます。

　そして同じ宛先に到達できる、次にメトリックが小さいルートがある場合は、それを新しいルートとしてルーティングテーブルに採用します。こうして、各ルータは回線断等で到達不能になったルートを取り除き、新しい有効なルートを選択し直すことができるわけです。

（３）ルート情報の取り下げ

　(a) ネットワーク構成の変化

　前述の動作だけではルータ間の断線、接続変更、ルータの損傷、増設などによるネットワーク構成の変化に対応して、素早く新しいルーティングテーブルを作成することはできません。例えば、目的ネットワークへのルートの途中に回線断があった場合、レギュラーアップデートによる更新は180秒経過後に行われるので、その間、断線部分と直接接続しているルータ以外のルータは、古い情報に基づく到達不能のルート（断線部分と直接接続しているルータ経由）でパケットを送り続けることになります。

　(b) ルート取り消し情報の送信

　RIPでは、断線部分に直接接続されているルータは、線が切れたのを知ると、目的ネットワークへのメトリックに「16」を入れたRIPアップデート情報を、直接接続されたルータ（断線していない側）に送ります。メトリック「16」はRIPの世界では無限に遠いということを意味します。

　このRIPパケットを受信した近隣のルータは、それを送信してきたルータ経由では目的地に到達できなくなったことを知ります。そして直ぐに、このルートを放棄します。

（４）スプリットホライズン

　(a) ループの発生

　通常、RIPルータはルートをくれたルータに対して、そのルートは自分経由で到達できるよ、と教え直します。しかし、これは構成が変化したときに問題を引き起こします。図29のようにルータが４台接続されている状況を考えます。



　　　図29 ループの形成

　ルータDが故障した場合、ルータCはルータDからのレギュラーアップデートを受け取れなくなったり、電気的に回線が切れていたりすることにより、Dへのルートを失ったことを知ります。ルータCはそれまでメトリック１で広告していたDへのルートに、改めてメトリック16を付けてBに広告します。これによりルータBは、ルータC経由でDに到達できないことを知ります。

　このようなやりとりに先立ち、ルータBはルータAに、Dへは自分を経由してメトリック3で到達できるよ、と教えています。そして、ルータAはその情報をくれたルータBに、Dへは自分を経由してメトリック4で到達できるよ、と教え返しています。この状況では、ルータBはより有利なルータC経由のルートを選択しています。

　しかし、このような状態でルータCからDへのメトリックが「16」であるという情報を受け取ると、ルータBはなんとルータAからのルートを採用し、DへのパケットをルータAに転送し始めてしまいます。しかし、このルートは、以前ルータBがルータAに教えたルートなので、ルータAはD宛のパケットをルータBに転送します。

　つまり、ルータAとルータBはDへのパケットをお互いに投げ合う、と言うことを繰り返し、ループが発生してしまうのです。このループは、教え合うルートのメトリックが増えていき、最終的に無限遠の「16」に達して解消されますが、そもそも生じさせる必要のない無駄なループです。

　(b) シンプルスプリットホライズン

　ループの発生を防ぐため、他のルータからもらった情報はその情報をくれた本人には流さない、というルールができました。このような動作をシンプルスプリットホライズンと言います。

　(c) ポイズンリバース付スプリットホライズン

　ポイズンリバース付スプリットホライズンでは、そのルートをくれた本人に、無限遠を指すメトリック16を入れて送り返すという動作をし、明示的にルートがないことを示します。ポイズンリバース付スプリットホライズンはシンプルスプリットホライズンよりも誤りを正す力が強くなります。しかし欠点もあります。

　(d) シンプルスプリットホライズンとポイズンリバース付スプリットホライズンの比較

　図30に示すように、イーサネットなどのブロードキャストメディアにRIPを話すルータが多数接続されており、各RIPルータが背後に多数のネットワークを抱えている状況を想定します。この場合、RIPパケットは次のようになります。



　図30 ポイズンリバースによる経路情報の増大

　シンプルスプリットホライゾンの場合、各RIPルータは自身が背後に持っているネットワークを、30秒に一度RIPアップデートとしてイーサネットにブロードキャストします。RIPルータが20台あり、各ルータが背後に10ネットワークずつ抱えているとすると、30秒間にイーサネットにブロードキャストされるエントリ数は、10×20＝200エントリということになります。

　ポイズンリバース付スプリットホライズンの場合、各RIPルータは他の19台からもらったルートについてポイズンリバースします。すなわち、もらったすべてのルートにメトリック16を付けて、RIPアップデートで広告します。

　これにより、各ルータは自身の10ネットワークの情報と、他RIPルータから学習した10×19＝190ルートが到達不能だという情報を、30秒に一度ブロードキャストしてしまいます。従って、30秒間にイーサネットにブロードキャストされるエントリ数は、(10＋10×19)×20＝4,000エントリにもなってしまいます。

　ここで例としてあげたネットワーク構成は、比較的ループの発生しにくいものです。従って、ポイズンリバース付スプリットホライズンを導入するメリットはあまりありません。ポイズンリバース付スプリットホライズンの必要性については、ネットワーク設計の段階でよく検討する必要があります。

（５）無限カウント問題とトリガードアップデート

　(a) 防ぐことのできないループ

　図31に示すネットワークにおいて、ルータB-E間の回線が切れたとします。この場合、次のようなことが起こります。



　　　図31 無限カウント問題

　�@ ルータBは、AとDにEへのルートが無くなったことを通知します（Eへのルートはメトリック16だというパケットを送ります）。これにより、ルータAとDはBを通ってEに到達するルート情報を無効にします。

　�A ルータCはAとDからEへの経路を学習しており、もともとルータD（またはルータA）をEへのネクストホップとして採用しています。また、このルートをAに教えています。ルータAはB経由のルートを失ったため、Cからのこのルート情報を新たに採用します。

　�B ル−タAはこのルートをルータBにも教えます。
　�C ルータBはこのルートを採用し、ルータDにも教えます。
　�D ルータDも同様の動作を繰り返すため、こうしてルートの伝達がループします。

　�E ルートを教えるときに、各ルータはルートのメトリックを増やすため、最終的にルートのメトリックは「16」に達し、ループが解消されます。この時点でようやくこのルートが謝ったものであったことが分かるのです・

　あり得ないルートなのですが、各ルータ間の定期的な情報交換は30秒に１回しかないため、メトリックが「16」に達してループが取り除かれるのに、30秒×15コストで7分以上もかかる場合もあり得るのです。

　このようにリング状になっているネットワークで、ルート情報がループしてしまうのは、RIPの採用しているディスタンスベクター型アルゴリズムの一般的な欠点と言えます。

　(b) トリガードアップデート

　上記の状況を打破するためには、残念ながらループの発生を防ぐという方法ではなく、できたループが無限コストに達するのを早めるという戦略がとられます。極めて単純ですが、各ルータは自身の経路情報に変化があったらレギュラーアップデートを待たずに、すぐに変化のあった情報を隣接ルータに送ります。この特別なアップデートをトリガーアップデートと呼んで、30秒おきのレギュラーアップデートと区別します。結局はメトリックが「16」に達するまで、無意味な情報を交換することは変わらないのですが、これでかなり収束時間を短くすることができるのです。

（６）ホールドダウンタイマー

　あるネットワークに対する同じルータからのルート情報のメトリックが増加していくのは、ループが発生してメトリックが徐々に増えている状況という可能性があります。Cisco社のルータでは、このような状況を検知したら、直ぐにそのルートを一時的に無効にするという動作を実装しています。

　具体的には、ルートのメトリックが、ネクストホップが変わらないまま「16」以外に増加すると、

　・そのルートを一時的に無効にし、ホールドダウンタイマーというタイマーを「0」にセットして開始する。
　・ホールドダウンタイマーの値を１秒に１ずつ増加させる。
　・そのルートのメトリックが再び増加したら、ホールドダウンタイマーの値を「0」に戻し、１秒に１ずつの値の増加とルートの無効を継続する。
　・メトリックがそれ以上増加せずホールドダウンタイマーの値が180秒に達したら、そのメトリックの増加は適切なものであったと判断して、ルートの無効を解除する。

　この動作により、トリガーアップデートによってルートがコスト16に達する以前に、ループを取除くことができるわけです。

４．３ RIPの限界とOSPFとの比較

（１）RIPの限界

　RIPはルート交換の仕組みから、比較的小規模なネットワークでIGPとして使用されることを想定しています。このようなRIPの適用領域は、下記のプロトコル仕様上の制約からもたらされます。

　・ループの解消は基本的にホップの無限カウントに頼っています。これは多くのホストで構成された複雑なネットワークの場合、頻繁なトリガーアップデートのブロードキャストなどで非常に多くの通信帯域を浪費します。また、無限カウントに頼ったルーティングテーブルの収束は、OSPFなどのリンクステート型プロトコルによる収束と比較して時間がかかりがちです。

　・通常すべてのネットワークに対して等しく「1」のコストを使用します。しかし、RIPが適用されるような構内ネットワークにおいても、ギガビットイーサネットから低速なシリアル回線まで、極めて多様な回線が使用され、回線の帯域を考慮せずホップ数だけで最適なルートを決定することは困難です。

　・最大15までのメトリックしかサポートしていないため、RIPによって作られるルーティングテーブルでは、15ホップ先のルータまでしか到達できません。

（２）OSPFとの比較

　(a) 長所

　・多くのネットワーク機器で実装されている。
　・処理の負担が小さい。

　(b) 短所

　・ディスタンスベクター方式のため、ネットワーク変更の際収束に時間がかかる。
　・ホップ数が「15」までしかなく、より小規模なネットワーク向きである。
　・VLSM(Variable Length Subnet Mask)を処理できない。
　・ルーティングテーブルのすべてのエントリをブロードキャストで流してしまうため、帯域を必要以上に消費する。
　・基本的にネットワーク毎の重み付けができないため、回線の帯域に応じて適切な経路を選ぶことが難しい。
　・エリア分けできないため、RIPネットワーク全体で同じ情報を使わざるを得ない。

　(c) 適用領域

　・大規模ネットワークには、収束が速く階層構造を作ることのできるOSPFが適する。
　・さほど大規模ではなく、デフォルトルートを効果的に使えるようなネットワークで、さらにVLSMが必要でない場合には、実装している機器が多いRIPが適する。

４．４ RIP Version 2

（１）RIP2による拡張

　(a) VLSM

　RIP2はRIP1と基本的に同じパケットフォーマットを使いながら、ルート毎にサブネットマスク情報を選ぶことでVLSMに対応できるようになりました。

　(b) 認証

　RIPアップデートパケットで認証を行うことが可能になりました。具体的には、アップデートパケットの１エントリ目に経路情報ではなく認証情報（パスワード）を格納することで、そのアップデートパケットの認証を行います。

　(c) ネクストホップの指定

　RIP1ではアップデートパケットの送信アドレスが自動的にネクストホップとして採用されましたが、RIP2ではルート毎にネクストホップを指定することもできるようになりました。これは、RIPを話さないゲートウェイをあるルートのネクストホップにしたい場合などに、他のRIPスピーカーが代理で広告する場合などに使用されます。

　(d) マルチキャストの使用

　RIPを話さないルータに無用な負荷を与えないため、RIPアップデートパケット送信にマルチキャストを使用することができるようになりました。

[出典]
　(1) 友近剛史他２：インターネットルーティング入門，翔泳社（2002-1）

　以上、RIPについてまとめました。次回はルーティングプロトコルの１つであるBGPについてまとめる予定です。

　今回はルーティングプロトコルの１つであるBGP についてまとめました。

４　BGP

４．１ BGP-4とは

（１）BGP-4の役割

　(a) BGP-4

　BGP(Border Gateway Protocol)は、EGP(Exterior Gateway)の１つで、AS(Autonomous System)間の標準的なルーティングプロトコルです。現在使われているバージョンは4であることからBGP-4と一般的に呼ばれ、RFC1771に記述されています。

　BGP-4はパスベクターアルゴリズムと呼ばれる考え方を採用し、AS間で経路情報のやりとりを行うために、172.16.0.0/16などとプレフィックスで表記されるIPアドレス(NLRI：Network Layer Reachability Information)とそれに付随したパス属性(Path Attribute)を、BGPの設定をした装置間で交換します。

　このNLRIとパス属性を使うことにより、AS間の経路制御をそのASの持つポリシーに従って行うことができます。経路制御を行うことで、その経路情報を参照してルーティングされるトラフィックを制御することができます。

　なお、BGPを設定した装置をBGPスピーカーと呼びます。BGP-4は、CIDRにも対応しており、アドレスのクラスにとらわれない経路制御が可能です。

　(b) BGP-4とインターネット

　BGP-4で用いられるASは自律システム、つまり１つの運用ポリシーを持ったネットワークのかたまりです。一般的にISPが１つのASを構成しています。研究機関や学術系ネットワーク、その他の組織がASを持っていることもあります。

　インターネットは、各ISPがASという概念を持ち、BGP-4でお互いに接続され、全世界に渡るネットワークを構成しています。現在は、数千〜数万のASがBGP-4を通じて接続され、流れる経路情報は10万経路以上に達しています。現在のインターネットはBGP-4で成り立っていると言っても過言ではありません。

　(c) BGP-4と経路制御

　一般に１つのASがインターネットへ接続する際に、信頼性を高めるために２つの接続点を持つことがよくあります。このとき、２つの回線に負荷を分散させてトラフィックを流すのか、または片方をメイン、もう片方をバックアップとして使うのかの選択が考えられます。どのISPと接続し、どのようにトラフィックを流すか、というのが最も簡単なポリシーと言えるでしょう。

　また、トラフィックには２つの方向があります。自ASから外のASに流れるトラフィック（上りトラフィック）と、外のASから自ASに流れてくるトラフィック（下りトラフィック）です。BGPでは、BGP特有のパス属性を使った経路制御技術によって、両方のトラフィックの流れを別々に制御することができます。図32にその様子を示します。



　　　　　　　　図32 BGP-4と経路制御

　ただし、上りトラフィックは完全に自分の思い通りに制御できますが、下りトラフィックについては、接続先ASのポリシーとの兼ね合いになるので、必ず制御できるとは限りません。自分たちがメインで使いたい回線を、接続先のASはバックアップで使いたい、などとポリシーが相反する可能性があるからです。

　自ASの持つポリシーを接続先に伝えることはBGPを通じてできますが、接続先がそのポリシーを認めてくれる、または解釈してくれるかどうかは、接続先次第となります。これが、インターネットの世界でBGPを運用する上での難しいところです。

（２）BGP-4での経路情報交換

　BGPでは、経路情報を交換するためにTCP（ポート番号179）を使用します。一般的なIGPとは異なり、BGP-4では経路情報をより確実に伝えるため、情報を交換するルータ同士でTCPを用いた１対１のBGPセッション（以下、BGPピアと呼びます）を使用します。そして、図33に示すようにこのセッションを確立した上で、経路情報の交換を行うのです。



　　　図33 BGPピア

　(a) BGP-4の基本的動作

　図34にBGP-4の基本的な動作を示します。はじめにTCPを利用したピアを張ります。ピアが張れると隣接BGPスピカーから経路情報をもらいます。もらった経路情報は、BGPテーブルと一般に呼ばれるデータベースに格納されます。そしてパス属性の評価が行われた後、ベストパスと呼ばれる最適経路が各プレフィックスに１つ選ばれるのです。



　　　図34 BGPの基本的な動作の流れ

　選ばれたベストパスは、実際にフォワーディング処理に使われるためルーティングテーブルに載せられます。ベストパスの情報は、さらに別のピア先に対して広告されます。

　このとき一部のパス属性には変更が加えられます。パス属性の変更方法および別のピア先にアナウンスするか否かの判断は、その相手が同じASに属しているか、異なるASに属しているか等によって変わります。また、自分自身で経路を生成し、アナウンスを始める場合には、すべてのピア先に対してその経路情報をアナウンスします。

　注意が必要なのは、他のピアに対してアナウンスされる経路はベストパスとして選ばれた経路だということです。同じ経路情報を２つの異なるピアから受け取った場合も、どちらか一方だけがベストパスとして選択され、他のピアにアナウンスされます。

　経路情報のやりとりが終わった後は、変化があった時にいつでも経路情報のやりとりができるように、ピアを張った状態を維持します。

　このようにBGPでは、ピアを張って経路情報をもらい、ベストパス選択をしてルーティングテーブルを作り、さらにその情報を他のピアにアナウンスするという動作を、すべてのBGPスピーカが行います。

（３）BGP-4交換メッセージの種類

　BGP-4でやりとりされる情報には以下の４種類があります。
　− OPEN
　− UPDATE
　− NOTIFICATION
　− KEEPALIVE

　(a) OPENメッセージ
　ピアを張る際にやりとりされるメッセージで、AS番号などの情報が交換されます。

　(b) UPDATEメッセージ
　NLRIとパス属性をやりとりする際に使用されます。BGP-4では、ピアが確立した直後にはすべての経路情報を交換しますが、その後は変更分だけのやりとりをこのUPDATEメッセージで行います

　(c) NOTIFICATIONメッセージ
　エラーなどを検知した際に、相手にそのことを伝えるために使われます。

　(d) KEEPALIVEメッセージ
　ピアが正常に確立されているかを、定期的に確認するために使われます。

（４）BGPテーブルとルーティングテーブル

　BGPでは、OSPFのようなトポロジカルデータベースは持ちませんが、BGPテーブルと一般に呼ばれる、BGPで得た経路情報だけを格納するテーブルを持ちます。このBGPテーブルを基に、最終的にはルーティングテーブルを作成します。

　BGPテーブル上には、複数のBGPスピーカから同じ経路（NLRI）を得たため、全く同じ経路が複数存在することがあります。このときには、経路に付随したパス属性を基に、ベストパスだけが最終的にルーティングテーブルのエントリとして採用され、フォワーディング処理に使用されます。

　このベストパスを選ぶ動作はベストパス選択アルゴリズムと呼ばれ、ある規則に従った選択が行われます。

（５）Routing Information Bases(RIBs)

　BGPテーブルは、RFC上では「RIB(Routing Information Base)」と呼ばれ、BGPスピーカの内部では図35に示すように、UPDATEメッセージに含まれる情報を次の３つのテーブルに分けて扱います。

　− Adj-RIBs-In
　− Loc-RIB
　− Adj-RIBs-Out



　　　　　図35 BGPテーブルとルーティングテーブル

　(a) Adj-RIBs-In
　ピア先から受け取ったUPDATEメッセ時の内容、つまり、NLRIとそれに付随したパス属性等がそのまま蓄積されます。

　(b) Loc-RIB
　Adj-RIBs-Inの情報を取り出し、このBGPスピーカのポリシーを反映させた結果を蓄積したものです。ポリシーによっては、Adj-RIBs-Inの中のパス属性の内容を書き換えたり、不要な経路をフィルタリングして受け取らなかったりした結果がLoc-RIBの内容になります。Loc-RIBの内容は、最終的にルーティングテーブルに適用され、フォワーディングする際に使用されます。

　(c) Adj-RIBs-Out
　他のBGPスピーカにUPDATEをアナウンスする際に送られる情報が蓄積されます。ここにはベストパス選択された経路情報だけが載り、さらにどの経路情報を該当のBGPスピーカにアナウンスさせるかのポリシーを反映させることができます。

（６）パス属性

　BGP-4の特徴として、宛先アドレス情報（NLRI）に付随したパス属性が挙げられます。前述のように、パス属性はベストパス選択などBGP-4の動作を決める重要な役割を担います。パス属性の代表的なものには以下のものがあります。

　− ORIGIN属性
　− AS_PATH属性
　− NEXT_HOP属性
　− LOCAL_PREF属性
　− MULTI_EXIT_DISC(MED)属性

　特にAS_PATH属性、LOCAL_PREF属性、MED属性は、ISPの運用において経路情報にポリシーを反映させるためによく使用されます。

（７）eBGPとiBGP

　BGP-4には、異なるASに属するBGPスピーカ間のBGPピアであるeBGP(External BGP)と、同一AS内部のBGPスピーカ間のBGPピアであるiBGP(Internal BGP)の２種類のBGPセッションがあり、図36に示すようにそれぞれ異なった働きをします。



　　　　　図36 iBGPとeBGP

　(a) eBGP
　eBGPは、BGP-4の本来の目的であるAS外のBGPスピーカと経路情報のやりとりを行います。AS間を接続するときには、何らかの物理媒体を通して直接つなぎ、通常は隣接するBGPスピーカ間でピアを設定します。

　(b) iBGP
　eBGPで得た自分以外のASからの経路情報を、さらに自分のAS内の他のBGPスピーカに伝えるときに使われるのがiBGPです。例えば図36のように、他のASとつながるルータが複数ある場合や、AS内部でフォワーディング処理を行うためにBGPの経路情報が必要な場合などに使われます。

　eBGPでは、原則隣接するBGPスピーカ同士でピアを張りますが、iBGPでは、間に複数のルータが入るような離れたBGPスピーカ間でもピアを張ることができます。

　(c) iBGPの注意点
　離れた場所にいるBGPスピーカ同士がピアを張るためには、IP通信ができる必要があります。そのため、各BGPスピーカが持つIPアドレス情報がOSPFなどのIGPによって伝搬されなくてはなりません。

　iBGPで経路情報の交換ができるならOSPFはいらないのでは、と思われがちですが、iBGPのピアを張るための前提として、OSPFなどのIGPが設定されている必要があります。iBGPのピアノ相手は隣のルータでないことが多いため、IGPを設定していないとiBGPのピア先のアドレスがどこにあるか分からないからです。この場合、iBGPのピアが張れなくなります。

　また、iBGPは原則として、AS内のすべてのBGPスピーカとフルメッシュでピアを張っておく必要があります。iBGPでは、経路のループを防ぐため、あるiBGPピアを通してもらった経路情報を他のiBGPピアに送ることはしません。

　BGPスピーカの数が多くなると、このピアの数も膨大になりますが、これを解決する技術として後述のルートリフレクタが用いられます。

（８）BGPピアConfig設定例

　図37、図38にCisco社ルータでのBGPのピア設定の例を示します。



　　　　　図37 eBGPの設定例




　　　　　図38 iBGPの設定例

　最初にBGPプロセスを起動する設定は、

　router bgp 65001

となります。このルータはAS65001に所属するという意味になります。eBGPでピアを張る際には、

　neighbor X.X.X.X remote-as 65002

と設定します。X.X.X.Xはピア先のBGPスピーカが持つアドレスです。自分のAS番号とremote-asの番号が異なる場合はeBGPのピアとなります。

　iBGPでピアを張る際には、

　neighbor X.X.X.X remote-as 65001
　neighbor X.X.X.X update-source loopback0

と設定します。Remote-asのAS番号が自分のASと同じですからiBGPとなります。またupdate-sourceとは、BGPパケットを送出する際のソースアドレスを指定するもので、ここではループバックインタフェース（物理インタフェースに依存しない論理インタフェース）であるloopback0を設定しています。

４．２ BGP-4のパス属性

（１）パス属性とは

　UPDATEメッセージで送られるパス属性には、表5に示すように様々な種類が存在します。パス属性をうまく使うことで、インターネット経路制御においてそのASの持つポリシーを反映させたり、他のASに自分の持つポリシーを伝えたりすることができます。BGP-4において最も重要とも特徴的とも言える機能です。

　　　　　　　　　　表5 パス属性タイプ一覧

（２）パス属性の４つのカテゴリ

　表5に示したとおり、すべてのパス属性は以下の４つのカテゴリ（属性タイプ）のいずれかに分類されます。

　(a) Well-known mandatory、Well-known discretionary

　Well-known属性は、すべてのBGPスピーカがサポートしていなくてはなりません。Well-known属性には２種類あります。まずWell-known mandatoryは、すべてのUPDATEメッセージに含まれていなくてはならない属性です。例としては、ORIGIN属性やAS_PATH属性が該当します。

　一方Well-known discretionaryは、UPDATEメッセージによって含まれる場合と含まれない場合があります。LOCAL_PREF属性などが例としてあげられます。なお、すべてのWell-known属性は、BGPスピーカから他のBGPスピーカへ伝えられて行かなくてはなりません。

　(b) Optional transitive、Optional non-transitive

　Well-known属性以外の属性はOptional属性になります。Optional属性は、すべてのBGPスピーカが必ずしもサポートしている必要のない属性です。Optional属性にも２種類あり、Optional transitiveは、これに該当する属性を受け取ったBGPスピーカが、この属性をサポートしておらず理解できなかったときでも、他のBGPスピーカに伝えられなくてはならないOptional属性です。AGGREGATOR属性やCOMMUNITY属性がこれに該当します。

　Optional non-transitiveは、自分がその属性をサポートしていなかったときに、他のBGPスピーカに伝える必要がないOptional属性です。MULTI_EXIT_DISC属性などがこれに該当します。

　このようなパス属性の扱いの違いは、UPDATEメッセージのPath Attributeフィールドに格納される、Attribute Flagsの値で区別されます。Well-known属性かOptional属性かの違いは、Attribute Flagsの内ビット0の値によって区別されます。Optional属性の場合のtransitiveかnon-transitiveかの違いは、ビット1で表します。

（３）AS_PATH属性

　AS_PATH属性は、ISPの運用に当たって最もよく参照される属性値の１つです。Well-known mandatory属性に該当し、AS内に閉じず、BGPで接続されているASのすべてのBGPスピーカに情報が伝わります。

　この属性は、該当するルーティング情報が通ってきたASを示すものです。図39にAS_PATH属性の情報が流れる様子を示します。eBGPのピアにおいて隣接のルータに経路を伝える際に、AS_PATHのリストに自分のAS番号を加えていきます。複数のASを経由して流れる経路は、途中通った分だけのAS番号がリストとして格納されます。



　　　　　図39 AS PATH属性

　AS_PATHは長けれ�