ルーティング

ルーティング（）あるいは経路制御（けいろせいぎょ）とは、データを目的地まで送信するために、コンピュータネットワーク上のデータ配送経路を決定する制御の事である。ネットワークのトポロジとトラフィック状態に関する情報を収集するためのプロトコルと、ネットワークを介したルートを設計するためのアルゴリズムで構成される。

概要 
OSI参照モデルのネットワーク層（第3層）の中継機器がこの制御を担っている。

ルーティングを行うための通信プロトコルを「ルーティングプロトコル」という。

経路が判明すれば、その経路に沿って、発信元から最終的な受取先へ、結節点またはノード（ここではルータと呼ばれる）を経由しながら転送を繰り返して情報が送られる。情報はパケット（小包の意。データをある程度の量ずつに小分けして送信する、その一単位）として送られ、各パケットには論理的なアドレスが付加してある。各ルータはルーティングテーブルという表を保持しており、この表に従ってパケットの転送先を決定する。

ルーティングテーブルとはネットワーク上の様々な宛先に対する最も良い経路が記録されたものである。ルーティングの目的は、ルーティングテーブルを構築・維持・管理することである。ルーティングでは、似たアドレスはネットワークの近傍に存在するようにアドレスが構造化されていることを想定している。
（例えばjp.example.orgから見ると、us.example.orgはtw.example.orgより遠く、ru.example.orgより近い。全て架空のアドレス）

また、ネットワーク的に近傍にある複数のアドレスを、ルーティングテーブル内の一つの項目にまとめることができる。
（例えば、***.example.orgから転送する場合、ルーティングテーブルで example.org を参照する）
この点がネットワークのブリッジと異なる点であり、インターネットにおける経路決定の主要な方法になっている理由である。

ルーティングには、スタティック（静的）ルーティングとダイナミック（動的）ルーティングとがある。

小規模なネットワークでは、手動でルーティングテーブルを構成してもよい (静的ルーティング)。ネットワークが大規模になると複雑なトポロジーを持ち、しかも間断なく変更される。そのためルーティングテーブルの構築は大きな問題となりがちである。それでもなお、公衆交換電話網は、ルーティングテーブルをあらかじめ計算し用意した上で、最も短い経路が使えなくなった場合に備えて予備回線も用意する方法をとっている。動的ルーティングは自動的にルーティングテーブルを構築する方法によって、この問題を解決しようというものである。ルーティングテーブルの構築はルーティング・プロトコルによって伝えられる情報に基づいて行われる。この手法によって、通信の断絶が起きないように、自律的といっていいほどのルーティング能力が得られる。だが、プロトコルの構成には技術が要求され、現時点ではルーティングが完全に自動的に行われるというわけではない。

インターネットのようなパケット交換(packet switching)方式ではデータはパケットに分解される。パケットには個々に完全な宛先がラベルされ、独立してルーティングされる。対照的な方法である公衆交換電話網のような回線交換方式(circuit switching: 回路を実際に接続するなどの方法で持続的な回線を用意する方式）でも、電話の発呼のように、回線への経路を探すためにルーティングが行われる。しかし一旦接続が成立すれば、完全な宛先をラベルとして貼らなくても連続的に大量のデータを送ることができる。

ルーティングを行う装置としては、レイヤ3スイッチ、ルーターなどがあるが、一般的にルーティングと言う場合にはレイヤ3以上のアドレス（ここではIPアドレス）に関する経路制御を指す。

ルーティング方式 

 ユニキャスト - 単一の特定のノードにメッセージを配信
 ブロードキャスト - ネットワーク内のすべてのノードにメッセージを配信
 マルチキャスト - メッセージを受信する特定のノードのグループにメッセージを配信
 エニーキャスト - ソースに最も近い、典型的には1ノードのグループにメッセージを配信
  - 地理的領域にメッセージを配信

動的ルーティングの基礎 
指示された経路が有効でなくなっている場合、現存するノードを使った別の経路を決めなければならない。これは通常ルーティングプロトコルと経路決定アルゴリズムによってなされる。経路決定アルゴリズムには二種類あって、一つは距離ベクトルアルゴリズム (distance vector algorithm, 以下DVA)、もう一つはリンク状態アルゴリズム (link state algorithm, 以下LSA) である。この内どちらか一方が用いられるが、この二つがわかれば、インターネット上の経路決定問題はほとんど理解できることになろう。 

以下用いられる「コスト」ないし「距離」は経由するルータの数（「ホップ数」）や回線速度を数値化したもので、「メトリック metric」と呼ばれる。メトリックの決定法はプロトコルによって異なる。

DVA 
DVAは Bellman-Fordアルゴリズムを用いている。この方法では、各ノード間に「コスト」と呼ばれる数値が割り振られる。二点間を結ぶ経路のコストは、その間に経由するノード間のコストの総和であり、その情報はノードから得られる。

アルゴリズムは極めて単純である。最初の段階では、各ノードは直近のノードがどれかという情報と、それらの間とのコストだけを知っている（このような、「行き先リスト」とそれぞれの総コスト、やりとりするべき「次の相手(next hop)」を集めたものがルーティングテーブルないし、ディスタンステーブルである）。定期的にノード間でやりとりがなされ、互いにルーティングテーブルのデータを交換する。もし隣から渡されたデータに、自分のルーティングテーブルより優れたもの（同じ行き先に到達するのに、コストが少ない）があれば、それを用いてテーブルを更新する。自分のテーブルにない相手への情報が入っていた場合も同様である。時間をかけると、全てのノードがあらゆる宛先についての最良の「次の相手」と最良の「コスト」を見つけだす。

あるノードが脱落した場合は、そこを「次の相手」としていたノード全てにおいて、ルーティングテーブルの破棄と再構築が行われる。この情報は隣のノードに次々伝えられて行き、最終的には到達可能な全てのノードについて最良の経路が発見されることになる。

経路収束が遅いため、現在はあまり用いられていない。

LSA 
LSAでは、各ノードが用いるのはネットワークのマップであり、それはグラフの形で格納されている。このマップをつくるために、全てのノードがネットワーク全体に「自分が接続しているノード」をブロードキャストする。各ノードはそのデータをもとに、個々独立してマップを計算し生成する。自分で生成したマップをもとに、各ノードは他のノードへの最短経路を決定する。

最短経路の計算にはダイクストラのアルゴリズムが用いられる。このアルゴリズムはネットワーク全体を木構造で表現する。木の根（最初の要素）は各ノードそれ自体である。次いで、ノードの集合から未登録のノードを一つずつ木に加えていく。加えるノードは既に木に存在するノードのどれかから到達できるノードのうち、最も少ないコストで到達できるものである。ネットワーク上の全てのノードを登録するまでこれを繰り返す。

木構造ができあがったら、それを用いて、ルーティングテーブルをつくる。最良の「次の相手」等がそこに登録される。

ルーティッドプロトコルとルーティングプロトコル
しばしばルーティッドプロトコルとルーティングプロトコルとを混同する人がいる。

 
 ネットワークプロトコルのうち、パケットを転送すべきネットワーク層のアドレスについて十分な情報を与えるもの全てを呼ぶ。その情報を用いて、アドレッシングスキームに基づき、あるホストから他のホストにパケットの転送がなされる。Routed protocolはパケットに付加されたフィールドのフォーマットと利用法を定義するものである。パケットは端末から端末へ運ばれる。Internet Protocolが代表である。
 ルーティングプロトコル
 ネットワーク間でルーティング情報を交換するための方法である。このプロトコルによって、ルータは動的にルーティングテーブルを生成することができる。伝統的なインターネットプロトコル(IP)によるルーティングは単純である。というのも、パケットを転送すべき「次の相手(next hop)」を用いているだけで、そこから先の経路については何も考えなくてよいからである。

この動的ルーティングは非常に複雑なものになりうるのだが、インターネットの柔軟性をもたらしているものでもあり、IPが用いられるようになって以来、8桁も規模が大きくなることのできた基盤でもある。

前記したルーティングメトリック routing metric は経路の優劣を比較できれば実はどんなものでもいい。帯域幅（≒データ転送速度）、遅延、ホップ数、経路のコスト、負荷、MTU、信頼性、通信コスト、といったものから求められる。ルーティングテーブルは利用可能な最良の経路を記録するだけだが、リンク状態、あるいはトポロジーのデータベースはそれ以上の情報を持ちうる。

管理上の距離 (Administrative distance) は複数のルーティングプロトコルで、同一の宛先に対し別の経路を最適とした場合、その中から最良のものを選択するのに用いられる値である。この値は、ルーティングプロトコルの信頼性を定義するもので、その値によってプロトコルの優先順位が決まる（値が低い方が一般には優先される）。Preferenceと呼ばれることもある。

他の自律システム (autonomous system, AS) に対するルータの相対的な位置によって、様々な種類のルーティングプロトコルが存在する:

 アドホックネットワーク (Ad hoc network) ルーティングプロトコル - わずかなインフラで（あるいはインフラなしで）構成されるネットワーク。
 Interior Gateway Protocol (IGPs) - 単一の自律システム(AS)内で用いられるルーティングプロトコル。
 IGRP (Interior Gateway Routing Protocol)
 EIGRP (Enhanced Interior Gateway Routing Protocol)
 OSPF (Open Shortest Path First)
 RIP (Routing Information Protocol)
 IS-IS (Intermediate System to Intermediate System)
 Exterior Gateway Protocol (EGPs)  - 異なるAS間のルーティングプロトコル。
 EGP  - 以前用いられたインターネットのバックボーンへの接続用プロトコル。
 BGP (Border Gateway Protocol - 現行のバージョンはBGPv4。1995年頃採用された。

関連項目 
 ルーティング・プロトコル
 経路探索アルゴリズム
 Hierarchical routing
 Edge Disjoint Shortest Pair Algorithm
 "Hot-potato routing"
 "Cold-potato routing"
 Deflection routing
 Policy based routing
 Wormhole routing
 Adaptive routing
 特定のルーティング法
 Classless Inter-Domain Routing (CIDR)
 MPLS routing
 ATM routing
 Routing in the PSTN
 ソース・ルーティング
 パケット転送関連（経路選択ではない）
 IPマスカレード (NAT)
 IP spoofing (Security)
 複数のメトリックを用いた経路決定問題の数学的複雑性
 Quality of Service in routing

参考資料 
 Computer Networking., Kurose, James E. and Ross, Keith W.. Benjamin/Cummings, 2004,  ISBN 0321227352

脚注

外部リンク 
 Routing, A diagram on how routing works
 ITPRC's IP Routing Resource Center
 Router Troubleshooting Primer - Take a look at the proper steps to troubleshooting routing problems