Border Gateway Protocol
BGPとインターネットインフラが直面している最大級の問題のひとつにインターネットルーティングテーブルの増大が挙げられる。もしインターネットルーティングテーブルが適切な範囲を超えて増大した場合、ルータのルーティングテーブルを維持するためのメモリ要求やCPUの負荷はその能力を超え、インターネットのゲートウェイとしての役割を果たせなくなるだろう。それに加えてルーティングテーブルが巨大化したことによりネットワーク構成に大きな変化があった場合、ネットワークの安定化(上記参照)に相当長い時間かかり、その間ネットワークサービスは全く信頼のできない状態になるか、最悪の場合、全く利用できなくなるだろう。
2001年の後半までグローバルルーティングテーブルは指数関数的に成長しており、それはインターネットへの接続性の維持への脅威となっていた。それに対してグローバルルーティングテーブルをCIDRやルート集約を用いて、なるべく小さく維持するという各ISPによる協調努力があった。その努力の甲斐あってその後数年は線形的成長にとどまった。
しかし、2014年8月にはBGPテーブルのエントリ数が512K(512,000~524,288 エントリ)を突破し、ルータの処理能力が不足しつつあったため、CISCO等の機器メーカーは、対応可能な上位機種にルータを変更したり、設定を変更したりすることを勧告した。
2014年8月12日から北米においてフルルートを扱うBGPルータのルーティングテーブルが溢れたことによるISP間の通信障害が発生した。自律システムの1つであるVerizonの経路集約の設定が失敗し、大量の経路情報が外部に流出したことが原因であった。
BGPのピアは他のBGPのピアとの動作の決定にシンプルな有限オートマトン(finite state machine、以下FSMと略す)を使用する。FSMにはIdle、Connect、Active、OpenSent、OpenConfirm、Establishedの6つの状態がある。BGPのピアはTCP接続がされ次第、ピアのセッションが確立・維持される方向で状態遷移する。