BGPルータの512K問題について

2014/8/18-1

インターネットでの通信障害を発生させた「BGPルータの512K問題」が一部界隈で話題です。今回は、それがどういった問題で、それが発生する背景がどのようなものであるかを紹介します。

インターネットの仕組みとBGP

インターネットは、AS(Autonomous System/自律システム)という単位で運営されていますが、AS同士はBGPという経路をやり取りするプロトコルを利用して互いに接続することで成り立っています。BGPは、伝言ゲームのように「私の隣に○○というASの××というネットワークがある」という情報を伝えて行くものです。世界中のASが伝言ゲームに参加することによって、世界中のASへの到達方法を共有しているのがインターネットなのです。

BGPによって集められた、世界中のASに含まれるネットワークへの経路を全て(もしくは全てと推測される規模の)経路情報は「フルルート(Full Route)」と言われます。512K問題は、主に、フルルートを扱うBGPルータで発生します。

512K問題とTCAM

今回の512K問題は、BGPルータに搭載されているTCAM(Ternary Content-Addressable Memory)というメモリに関連します。フルルートが、BGPルータに搭載されたTCAMの容量を超える規模になってしまったので、著しくBGPルータの性能が落ちるなどしてネットワークが不安定になるというものです。

TCAMは、CAM(Content-Addressable Memory)と呼ばれるメモリの一種です。メモリといえば、パソコンなどで利用されるDRAM(Dynamic Random Access Memory)を思い浮かべる方々が多いと思いますが、DRAMとCAMは全く違う仕組みです。

DRAMは、指定されたアドレスに情報を格納したり、格納された情報を取り出すといった機能を持ちます。一方で、CAMは、指定された情報とマッチする情報を高速に取り出せるというものです。CAMにあらかじめ多数のデータを保持しておいた状態で、CAMに対して検索を行う情報を指定すると、それにマッチする項目が返ります。返ってくる結果が複数の場合もあります。

完全に一致する情報を探すCAMは、binary CAMと呼ばれていますが、ルータなどのネットワーク機器で利用されるのはbinary CAMではなくTCAMです。TCAMは、ビットが「マッチする」「マッチしない」「気にしない」という3種類のマッチングが行えます。

なぜTCAMが使われるかというと、TCAMを使うことでサブネットを考慮したIPアドレス検索を行いやすいためです。たとえば、32ビットのIPv4アドレスに対して経路を検索する用途でTCAMにあらかじめ保存される情報は次のようになります。TCAMにあらかじめ登録される経路表にある/24のネットワークを示す項目では上位24ビットが「マッチする」、下位8ビットは「気にしない」という条件でTCAMに登録されます。同様に、/16のネットワークであれば、上位16ビットが「マッチする」、下位16ビットが「気にしない」という条件でTCAMに登録されます。

32ビットのIPv4アドレスでTCAMを使った検索を行うと、そのIPv4アドレスにマッチする全ての経路情報が得られます。TCAMから得られた経路候補から、最も長いサブネット長を持つ経路を選ぶ、いわゆる「ロンゲストマッチ」の計算を行うのはTCAM以外の仕組みになります。

こういった仕組みを持つTCAMは、サブネットマスクやアクセスリスト（ACL / Access Control List）をハードウェアで高速に処理するためにネットワーク機器に搭載されています。

（余談ですが、OpenFlowが当初考案されたのは、多くのネットワーク機器にTCAMがあらかじめ搭載されているからです。TCAMが搭載されたハードウェアが既に市場に出回っているので、それらの機器に対してソフトウェアだけ更新すれば面白いことができるといった発想でOpenFlowは考案されています。余談終わり。）

TCAMは大規模なトラフィックを処理するために必要なもの

で、今回の話題では、TCAMをBGPルータのFIB(Forward Information Base)として利用するときの話です。

BGPによってルーティングテーブルが作成されますが、ルーティングテーブル作成などの作業はDRAMに対してRIB(Routing Information Base)として保存されます。DRAMに保存したうえで、BGPルータのCPUを使って個々のパケットがどこに転送されるべきかの計算をしていては処理が追いつかないので、高速処理が可能なFIBが利用されますが(ただし、全てのルータのFIBがTCAMで実現されているわけではありません)、そのFIBの容量が溢れてしまったというのが512K問題です。512K問題が発生したとしても、ただちにそのBGPルータが破綻するわけではなく、「パケットロスが増えた」などの事例報告がされているのも、「FIBに乗っていないからといって処理できないわけではない」のが理由です(Catalyst 6500系は一度発生すると「Current IPv4 FIB exception state = TRUE」の状態になり、復旧にはリロードする必要あり。参考)。

さらに言うと、BGPルータでフルルートを扱っていたとしても、そのBGPルータが転送するトラフィックが少ないのであれば、TCAMを大量に搭載した高価な機器は必要ありません。BGPの処理だけを行い、大量のトラフィックを転送しないのであれば、一般的なPCでBGPのフルルートを受け取ることも可能です。問題はパケットを高速に転送することであり、BGPそのものの処理ではないのです(例としては、route reflector、IX等で運用されるroute server、大学等の研究で情報収集用にPCサーバがBGPソフトウェアを運用する場合など)。

多少細かい話ではありますが、これも混同されがちなポイントです。

512K問題とインターネットでの経路数の増大

512K問題が発生したのは、インターネットの経路数が増えているからです。

インターネットの経路数は、インターネットの誕生から現在まで常に増え続けています。インターネットの規模が大きくなればなるほど、そこに参加するネットワークの数も増えるので、経路数も増えるのです。

最近は、インターネットの普及だけではなく、IPv4アドレス在庫枯渇も経路数を増大させる大きな要因です。IPv4アドレスの在庫が枯渇しましたが、それは、利用可能なIPv4アドレスの上限までインターネットが拡大してたことを意味します。数年前までは、インターネットの成長とともに、割り振りするIPv4アドレスを増やして行くことができましたが、今はもうそれができなくなってしまいました。

しかし、いまもなおインターネットに新たにネットワークが追加され続けています。どのようにそれをしているかというと、過去に割り当てられたIPv4アドレスを細かく分割して使っているのです。これにより、IPv4アドレス全体としては上限に達したものの、ネットワーク数としては増えて行くという状況になっています。個々のネットワーク規模が縮小することで経路の数が増加しているのです。

先ほど、IPv4アドレス割り振りを受けられなくなったと書きましたが、厳密に言うと「最後の1回は可能」です。世界5つのRIRは、各RIRごとに最後の割り振りポリシを持っていますが、たとえば「各組織、/22を最後に一回だけ」など、IPv4アドレス在庫枯渇前と比べて著しく細かいアドレスを割り振りする仕組みになっています。RIRでの細かいIPv4アドレス割り振りも、IPv4での経路数増加の要因です。

なお、経路数が増えているのはIPv4だけではありません。IPv4ほどの規模ではないものの、IPv6の経路数も増えています。

512K問題の影響範囲

512K問題の影響を受けるのは、ルーティングテーブルのためにTCAMを利用する最大数が512K(512,000個、2の19乗である約52万個ではないので注意)になっているBGPルータです。Cisco公式ブログで影響を受ける機器と対処方法が公開されています。

Cisco Blogs: Global Internet Routing Table Reaches 512k Milestone

これまで、フルルートが512K個を超えるようなことがなかったので、この問題が表面化しなかったのですが、ついに、フルルートが512K個を超えたので問題が発生したという部分も重要なポイントです。どういうことかというと、フルルートを扱っていないBGPルータには影響がないのです(フルルート運用を捨てた例としては「BGPフルルートは必要か？GREEの事例」参照)。

最新の機器であれば、512K問題は発生しないという点も重要なポイントです。512K問題を抱えた機器を、最新型の機器へとリプレースしてあれば影響を受けません(場合によっては1台あたり億単位のお金が必要になるのでリプレースが困難という組織も多いのだろうとは思いますが)。

過去にインターネットの経路数が256K個を超えたときにも、今回ほどの広範囲な影響は発生しなかったとはいえ、一部BGPルータで同様の問題が発生しています。そういう意味では、512K問題は「いままでなかったような衝撃的な障害」とまでは言えなさそうです。

日本でも多少発生していたようですが、北米ほどの話題にはなっていないようです。日本では、機器購入後にベンダーや商社によるサポート等を受けることが多いので、問題が発生するよりも前に対処が行われていたものと思われます（新型機器へのリプレースを含む）。

現段階ではまだ本番はこれからという話もありそうですが、今回の問題は、かなり前から発生することがわかっていた問題のようなので、それに対処していなかった組織が障害を発生させてしまったということだろうと思います。主に技術系ではない媒体において大問題が発生したかのようなオーバーな表現での記事が目立っていましたが、512K問題によってインターネットが即座に破綻してしまうような話ではないので、「へぇー、そういう障害があったのね。」ぐらいの気持ちで各種記事をご覧頂くと良いと思う今日この頃です。

追記

8月12日に発生した512K問題と、これから発生する512K問題

過去記事

過去記事一覧

超凄いIPv6解説書(488ページ)を無料配布します！