BGP Literature

Some recent studies:

BGP Routing Properties at a Large Time Scale, G. Siganos, M. Faloutsos, Global Internet Symposium, Taipei, Taiwan, November 17-21, 2002
Observation and Analysis of BGP Behavior under Stress Lan Wang, Xiaoliang Zhao, Dan Pei, Randy Bush, Daniel Massey, Allison Mankin, S. Felix Wu, Lixia Zhang, IMW 2002.
BGP Routing Stability of Popular Destinations Jennifer Rexford, Jia Wang, Zhen Xiao, Yin Zhang, IMW 2002
An Empirical Study of Router Response to Large BGP Routing Table Load Di-Fa Chang, Ramesh Govindan, John Heidemann, IMW 2002
On the structure and application of BGP policy Atoms Yehuda Afek, Omer Ben-Shalom, Anat Bremler-Barr, IMW 2002

The following links are copied for your convenience from the excellent site of T. Griffin at AT\&T. We recommend the reader to visit the site.

ISP Peering and Settlement

Interconnection, Peering and Settlements. Geoff Huston, (

Part I

Part II

Internet Protocol Journal

Interconnection, Peering and Financial Settlements in the Internet. A talk by Geoff Huston, June 28, 1999.
Without Public Peer: The potential Regulatory and Universal Service Consequences of Internet Balkanization.Robert Frieden. Virginia Journal of Law and Technology. Fall 1998.
Peering and Fearing: ISP Interconnection and Regulatory Issues. K.N. Cukier.

Dynamic behavior of BGP

The Impact of Internet Policy and Topology on Delayed Routing Convergence. Craig Labovitz (University of Michigan), Abha Ahuja (Merit Network), Roger Wattenhofer (Microsoft), Srinivasan Venkatachary (Microsoft). INFOCOM 2001. (postscript)
The Impact of Internet Policy on Internet Paths. Hongsuda Tangmunarunkit (USC/Information Sciences Institute), Ramesh Govindan (USC/Information Sciences Institute), Scott Shenker (ACIRI), Deborah Estrin (USC/Information Sciences Institute) INFOCOM 2001. (postscript)
Routing Stability in Congested Networks: Experimentation and Analysis. Aman Shaikh, Lampros Kalampoukas, Rohit Dube, and Anujan Varma. SIGCOMM 2000. (postscript).
An Experimental Study of BGP Convergence. Craig Labovitz, Abha Ahuja, Abhijit Abose, and Farnam Jahanian. SIGCOMM 2000. (postscript). Also as Microsoft Technical Report.
Origins of Internet Routing Instability. C. Labovitz, R. Malan, F. Jahanian. INFOCOM99, New York, NY, June, 1999. (postscript).
Experimental Study of Internet Stability and Wide-Area Network Failures. C. Labovitz, A. Ahuja, F. Jahanian. Proceedings of FTCS99, Madison, WI, June 22, 1999. (pdf).
Internet Routing Instability. Craig Labovitz, G. Robert Malan and Farnam Jahanian. IEEE/ACM Transactions on Networking, vol. 6, no. 5, pp. 515-528, Oct. 1998. (TON Oct'98)
Internet Routing Instability. Craig Labovitz, G. Robert Malan and Farnam Jahanian. SIGCOMM Symposium on Communications Architectures and Protocols, (Cannes, France), Sep. 1997. (postscript).
An Analysis of Inter-Domain Topology and Route Stability. Ramesh Govindan, Anoop Reddy. Proceedings of the IEEE INFOCOM 1997. (postscript).
End-to-End Routing Behavior in the Internet. Vern Paxson. IEEE/ACM Transactions on Networking, Vol.5, No.5, pp. 601-615, October 1997. (postscript) An earlier version appeared at SIGCOMM '96.

Global sanity of BGP routing

Inherently Safe Backup Routing with BGP Lixin Gao (Smith College), Timothy Griffin (AT&T Labs - Research), Jennifer Rexford (AT&T Labs - Research). INFOCOM 2001. (postscript)
Persistent Route Oscillations in Inter-Domain Routing. Kannan Varadhan, Ramesh Govindan, and Deborah Estrin. Computer Networks, Jan. 2000. (pdf). Also USC Tech Report CS TR 96-631, Feb. 1996, Department of Computer Science, University of Southern California. (postscript).
A Safe Path Vector Protocol. Timothy G. Griffin and Gordon Wilfong. INFOCOM 2000. (postscript)
Stable Internet routing without global coordination. Lixin Gao and Jennifer Rexford. SIGMETRICS 2000. (postscript). An extended version appears as AT&T Research Technical Report 991110-08, November 1999.
Policy Disputes in Path Vector Protocols. Timothy G. Griffin, F. Bruce Shepherd, and Gordon Wilfong. ICNP'99. (postscript, pdf)
An Architecture for Stable, Analyzable Internet Routing. Ramesh Govindan, Cengiz Alaettinoglu, George Eddy, David Kessens, Satish Kumar, and WeeSan Lee. IEEE Network Magazine, Jan-Feb 1999. (postscript).
An Analysis of BGP Convergence Properties. Timothy G. Griffin and Gordon Wilfong. SIGCOMM'99. Link to paper.

Security

Secure Border Gateway Protocol (S-BGP) -- Real World Performance and Deployment Issues. Stephen Kent, Charles Lynn, Joanne Mikkelson and Karen Seo. Proc. of Network and Distributed System Security Symposium, (San Diego, California), Feb. 2000. (pdf).
Securing the Border Gateway Routing Protocol. Bradley R. Smith and J.J. Garcia-Luna-Aceves. Proceedings of Global Internet, Jon Crowcroft and Henning Schulzrinne, ed., (London, England), pp. 81--85, Nov. 1996. (postscript).

Visualization

Heuristics for Internet Map Discovery. Ramesh Govindan and Hongsuda Tangmunarunkit. INFOCOM 2000. (postscript) Also as Technical Report 99-717, Computer Science Department, University of Southern California, October 1999, (postscript).
Otter: A General-Purpose Network Visualization Tool. Bradley Huffaker, Evi Nemeth and K. Claffy. Proc. of INET, (San Jose, California), Jun. 1999. (online version).

BGP Scaling

Analysing the Internet BGP Routing Table. Geof Huston. The Internet Protocol Journal.

iBGP Scaling

A Comparison of Scaling Techniques for BGP. Rohit Dube. ACM Computer Communication Review, vol. 29, no. 3, Jul. 1999. (postscript).
BGP Scaling Techniques Revisited. John G. Scudder and Rohit Dube. ACM Computer Communication Review, vol. 29, no. 3, Oct. 1999. (postscript).

Route Servers

Route Servers for Inter-Domain Routing. Ramesh Govindan, Cengiz Alaettinoglu, Kannan Varadhan, Deborah Estrin. Computer Networks and ISDN Systems, vol 30, pp 1157-1174, 1998. (pdf).
Time-Space Tradeoffs in Route Server Implementation. Ramesh Govindan. Internetworking: Research and Experience, vol 6, no 2, June 1995. (postscript).

Extracting information from BGP routing tables

On Inferring Autonomous System Relationships in the Internet. Lixin Gao. To appear in IEEE Global Internet, Nov 2000. (postscript).
On Network-Aware Clustering of Web Clients. Balachander Krishnamurthy and Jia Wang. SIGCOMM 2000. (postscript).
On Power-law relationships of the Internet Topology. Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. SIGCOMM'99. Link to paper.
A Passive System for Server Selection within Mirrored Resource Environments Using AS Path Length Heuristics. Patrick R. McManus. AppliedTheory Communications, New York, Apr. 1999. (study link)

CIDR Addressing, Fast IP Lookup

Optimal Routing Table Design for IP Address Lookups Under Memory Constraints. Gene Cheung and Steve McCanne. Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999. (pdf).
Constructing Optimal IP Routing Tables. Richard Draves, Christopher King, Srinivasan Venkatachary and Brian Zill. Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999. (pdf).
Tradeoffs for Packet Classification. Anja Feldmann and S. Muthukrishnan. Proceedings of the Conference on Computer Communications (IEEE Infocom), (Tel Aviv, Israel), Mar. 2000. (postscript).
Flexible Routing and Addressing in a Next-Generation Internet Protocol. Paul Francis and Ramesh Govindan. In Proceedings of the ACM Sigcomm 1994, London, Sept 1994 (postscript).
Near Optimal Routing Lookups with Bounded Worst Case Performance. Pankaj Gupta, Balaji Prabhakar, Stephen Boyd. Proceedings of the Conference on Computer Communications (IEEE Infocom), (Tel Aviv, Israel), Mar. 2000. (pdf).
A Fast IP Routing Lookup Scheme for Gigabit Switching Routers. Nen-Fu Huang, Shi-Ming Zhao, Jen-Yi Pan and Chi-An Su. Proceedings of the Conference on Computer Communications (IEEE Infocom), (New York), Mar. 1999. (pdf).
IP Lookups Using Multiway and Multicolumn Search. B. Lampson, V. Srinivasan and G. Varghese. Conference on Computer Communications (IEEE Infocom), (San Francisco, California), pp. 1248, March/April 1998. (pdf).