BGP ist eine Abkürzung für "Border Gateway Protocol". Es ist ein Inter-AS-Routing-Protokoll, also zuständig für die Kommunikation zwischen verschiedenen autonomen Systemen.

Die Kernidee des BGP ist, dass Router in der Routing-Tabelle nicht nur die kürzeste Distanz zu einem Ziel speichern, sondern alle möglichen Verbindungen und zusätzlich noch den Pfad, welcher für jede Verbindung verwendet wird. Dadurch wird das Count-to-Infinity-Problem gelöst. Die Border-Router (die Verbindungsknoten der autonomen Systeme) teilen einander bei einer Änderung die neuen Verbindungen inklusive Pfadangabe mit (announce-Meldungen).

Jeder Router, der eine solche Nachricht bekommt, überprüft, ob im Pfad keine Kreise vorkommen. Falls nicht, dann ist die Verbindung verwendbar und die Routing-Tabelle wird dementsprechend korrigiert. Wenn ein Kreis vorhanden ist, dann wird dieser Kreis aus dem Pfad herausgelöscht und der kürzere Weg gespeichert. Bekommt ein Router einen Pfad, indem er selbst auftaucht, so wird dieser nicht akzeptiert (dies ist ebenfalls ein Kreis).

Bekommt ein Router eine withdraw-Meldung (mit Pfadangabe), so bedeutet dies, dass eine bestimmte Verbindung nicht mehr verwendbar ist. Der Router wird die Verbindung aus seiner Tabelle löschen. Falls nun eine andere Verbindung (Backup) zum selben Ziel vorhanden ist, so wird diese versendet. Ist keine mehr vorhanden, so wird ebenfalls eine withdraw-Meldung versendet.

BGP-Nachrichten werden via TCP verschickt. Die Nachrichten, die die BGP-Router versenden sind die folgenden:

• OPEN: Ein Router kam hinzu und gibt mit dem OPEN sein autonomes System den anderen bekannt.
• UPDATE: Eine neue Pfadangabe wird versendet (announce oder withdraw).
• KEEPALIVE: Falls nichts neues zu versenden ist, wird diese Meldung verschickt, um den andern mitzuteilen, dass der Router noch vorhanden ist.
• NOTIFICATION: Damit können Fehler der vorherigen Meldung gemeldet werden. Wird auch für das Beenden einer Verbindung verwendet.

BGP ist sehr robust, selbst bei den verrücktesten Verbindungen wird irgendwann immer die beste Verbindung vorhanden sein. Damit aber das Internet nicht ständig mit solchen Meldungen verstopft wird, können BGP-Meldungen immer nur frühestens 30 Sekunden nach der letzten Meldung versendet werden. Damit erreicht man zwar ein wenig-oszillierendes Netzwerk, jedoch kann es sehr lange (mehrere Minuten) dauern, bis neue beste Verbindungen erkannt werden. Besonders, wenn eine Verbindung nicht mehr benutzt werden kann, dauert es sehr lange, bis das gesamte Netzwerk dies gemerkt hat.

Eine Erleichterung bietet die Möglichkeit der Mitgabe von Cause-Tags (BGP-CT). Bei dem Wegfallen einer Verbindung werden mit dem Cause-Tag die beiden Knoten mitgegeben, zwischen denen die Verbindung abgebrochen war. Dadurch erhalten alle Nachbarknoten augenblicklich die Meldung, dass alle Verbindungen, die über diese Verbindung gehen sollten, nicht mehr verfügbar sind.

Mit BGP können die Kosten einer Verbindung selbst definiert werden. Kein Router hat die Pflicht, jedem seine Dienste anzubieten. Jeder kann sich die billigsten, schnellsten oder bequemsten Pfade aussuchen.