relation: https://mpra.ub.uni-muenchen.de/2110/
title: The Strategic Justification for BGP
creator: Levin, Hagay
creator: Schapira, Michael
creator: Zohar, Aviv
subject: D8 - Information, Knowledge, and Uncertainty
subject: D7 - Analysis of Collective Decision-Making
subject: D85 - Network Formation and Analysis: Theory
description: The Internet consists of many administrative domains, or \emph{Autonomous Systems} (ASes), each owned by an economic entity (Microsoft, AT\&T, The Hebrew University, etc.). The task of ensuring interconnectivity between ASes, known as \emph{interdomain routing}, is currently handled by the \emph{Border Gateway Protocol} (BGP).  ASes are self-interested and might be willing to manipulate BGP for their benefit. In this paper we present the strategic justification for using BGP for interdomain routing in today's Internet: We show that, in the realistic Gao-Rexford setting, BGP is immune to almost all forms of rational manipulation by ASes, and can easily be made immune to all such manipulations. The Gao-Rexford setting is said to accurately depict the current commercial relations between ASes in the Internet. Formally, we prove that a slight modification of BGP is incentive-compatible in \emph{ex-post Nash equilibrium}. Moreover, we show that, if a certain reasonable condition holds, then this slightly modified BGP is also \emph{collusion-proof} in ex-post Nash -- i.e., immune to rational manipulations even by \emph{coalitions} of \emph{any} size.  Unlike previous works on achieving incentive-compatibility in interdomain routing, our results \emph{do not require any monetary transfer between ASes} (as is the case in practice). We also strengthen the Gao-Rexford constraints by proving that one of the three constraints can actually be enforced by the rationality of ASes if the two other constraints hold.
date: 2006-11-20
type: MPRA Paper
type: NonPeerReviewed
format: application/pdf
language: en
identifier: https://mpra.ub.uni-muenchen.de/2110/1/MPRA_paper_2110.pdf
identifier:   Levin, Hagay and Schapira, Michael and Zohar, Aviv  (2006): The Strategic Justification for BGP.    
language: en