ABSTRACT: The Internet consists of many administrative domains, or Autonomous Systems (ASes), each owned by an economic entity (Microsoft, AT&T, The Hebrew University, etc.). The task of ensuring inter-connectivity between ASes, known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). There are strong justifications for using BGP from an engineering, or networking, perspective: In particular, BGP enables ASes to express elaborate routing policies in a distributed fashion without global coordination. However, "clashes" between routing policies can, in general, lead to undesired anomalies such as protocol divergence (route oscillations). The Gao-Rexford constraints on routing policies, are known to guarantee protocol convergence. These natural economic constraints are said to accurately depict the commercial relations between ASes in the Internet. However, ASes are self-interested and might be willing to manipulate BGP for their benefit, even if this comes at the expense of the global routing outcome (e.g., improving their routing outcomes by causing local route oscillations that do not affect them). 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. Formally, we prove that a slight modification of BGP is incentive-compatible in ex-post Nash equilibrium. Moreover, we show that, if a certain reasonable condition holds, then BGP is also collusion-proof in ex-post Nash i.e., immune to rational manipulations by coalitions of ASes.