Link bandwidth and CPU utilization

Immediately after the initial BGP connection setup, the peers exchange complete set of routing information. If we denote the total number of routes in the Internet by N, the mean AS distance of the Internet by M (distance at the level of an autonomous system, expressed in terms of the number of autonomous systems), the total number of autonomous systems in the Internet by A, and assume that the networks are uniformly distributed among the autonomous systems, then the worst case amount of bandwidth consumed during the initial exchange between a pair of BGP speakers is

                    MR = O(N + M * A)

The following table illustrates typical amount of bandwidth consumed during the initial exchange between a pair of BGP speakers based on the above assumptions (ignoring bandwidth consumed by the BGP Header).

   # NLRI       Mean AS Distance       # AS's    Bandwidth
   ----------   ----------------       ------    ---------
   10,000       15                     300       49,000 bytes
   20,000       8                      400       86,000 bytes *
   40,000       15                     400       172,000 bytes
   100,000      20                     3,000     520,000 bytes

   * the actual "size" of the Internet at the the time of this
     document's publication

Note that most of the bandwidth is consumed by the exchange of the Network Layer Reachability Information (NLRI).

BGP-4 was created specifically to reduce the amount of NLRI entries carried and exchanged by border routers. BGP-4, along with CIDR [4] has introduced the concept of the "Supernet" which describes a power-of-two aggregation of more than one class-based network.

Due to the advantages of advertising a few large aggregate blocks instead of many smaller class-based individual networks, it is difficult to estimate the actual reduction in bandwidth and processing that BGP-4 has provided over BGP3. If we simply enumerate all aggregate blocks into their individual class-based networks, we would not take into account "dead" space that has been reserved for future expansion. The best metric for determining the success of BGP-4's aggregation is to sample the number NLRI entries in the globally connected Internet today and compare it to projected growth rates before BGP-4 was deployed.

In January of 1994, router carrying a full routing load for the globally connected Internet had approximately 19,000 network entries (this number is not exact due to local policy variations). The BGP deployment working group estimated that the growth rate at that time was over 1000 new networks per month and increasing. Since the widespread deployment of BGP-4, the growth rate has dropped significantly and a sample done at the end of November 1994 showed approximately 21,000 entries present, as opposed to the expected 30,000.

CPU cycles consumed by BGP depends only on the stability of the Internet. If the Internet is stable, then the only link bandwidth and router CPU cycles consumed by BGP are due to the exchange of the BGP KEEPALIVE messages. The KEEPALIVE messages are exchanged only between peers. The suggested frequency of the exchange is 30 seconds. The KEEPALIVE messages are quite short (19 octets), and require virtually no processing. Therefore, the bandwidth consumed by the KEEPALIVE messages is about 5 bits/sec. Operational experience confirms that the overhead (in terms of bandwidth and CPU) associated with the KEEPALIVE messages should be viewed as negligible. If the Internet is unstable, then only the changes to the reachability information (that are caused by the instabilities) are passed between routers (via the UPDATE messages). If we denote the number of routing changes per second by C, then in the worst case the amount of bandwidth consumed by the BGP can be expressed as O(C * M). The greatest overhead per UPDATE message occurs when each UPDATE message contains only a single network. It should be pointed out that in practice routing changes exhibit strong locality with respect to the AS path. That is routes that change are likely to have common AS path. In this case multiple networks can be grouped into a single UPDATE message, thus significantly reducing the amount of bandwidth required (see also Appendix 6.1 of [1]).

Since in the steady state the link bandwidth and router CPU cycles consumed by the BGP protocol are dependent only on the stability of the Internet, but are completely independent on the number of networks that compose the Internet, it follows that BGP should have no scaling problems in the areas of link bandwidth and router CPU utilization, as the Internet grows, provided that the overall stability of the inter-AS connectivity (connectivity between ASs) of the Internet can be controlled. Stability issue could be addressed by introducing some form of dampening (e.g., hold downs). Due to the nature of BGP, such dampening should be viewed as a local to an autonomous system matter (see also Appendix 6.3 of [1]). It is important to point out, that regardless of BGP, one should not underestimate the significance of the stability in the Internet.

Growth of the Internet has made the stability issue one of the most crucial ones. It is important to realize that BGP, by itself, does not introduce any instabilities in the Internet. Current observations in the NSFNET show that the instabilities are largely due to the ill-behaved routing within the autonomous systems that compose the Internet. Therefore, while providing BGP with mechanisms to address the stability issue, we feel that the right way to handle the issue is to address it at the root of the problem, and to come up with intra-autonomous routing schemes that exhibit reasonable stability.

It also may be instructive to compare bandwidth and CPU requirements of BGP with EGP. While with BGP the complete information is exchanged only at the connection establishment time, with EGP the complete information is exchanged periodically (usually every 3 minutes). Note that both for BGP and for EGP the amount of information exchanged is roughly on the order of the networks reachable via a peer that sends the information (see also Section 5.2). Therefore, even if one assumes extreme instabilities of BGP, its worst case behavior will be the same as the steady state behavior of EGP.

Operational experience with BGP showed that the incremental updates approach employed by BGP presents an enormous improvement both in the area of bandwidth and in the CPU utilization, as compared with complete periodic updates used by EGP (see also presentation by Dennis Ferguson at the Twentieth IETF, March 11-15, 1991, St.Louis).