To quantify the worst case memory requirements for BGP, denote the total number of networks 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 the total number of BGP speakers that a system is peering with by K (note that K will usually be dominated by the total number of the BGP speakers within a single autonomous system). Then the worst case memory requirements (MR) can be expressed as
MR = O((N + M * A) * K)
In the current NSFNET Backbone (N = 2110, A = 59, and M = 5) if each network is stored as 4 octets, and each autonomous system is stored as 2 octets then the overhead of storing the AS path information (in addition to the full complement of exterior routes) is less than 7 percent of the total memory usage.
It is interesting to point out, that prior to the introduction of BGP in the NSFNET Backbone, memory requirements on the NSFNET Backbone routers running EGP were on the order of O(N * K). Therefore, the extra overhead in memory incurred by the NSFNET routers after the introduction of BGP is less than 7 percent.
Since a mean AS distance grows very slowly with the total number of networks (there are about 60 autonomous systems, well over 2,000 networks known in the NSFNET backbone routers, and the mean AS distance of the current Internet is well below 5), for all practical purposes the worst case router memory requirements are on the order of the total number of networks in the Internet times the number of peers the local system is peering with. We expect that the total number of networks in the Internet will grow much faster than the average number of peers per router. Therefore, scaling with respect to the memory requirements is going to be heavily dominated by the factor that is linearly proportional to the total number of networks in the Internet.
The following table illustrates typical memory requirements of a router running BGP. It is assumed that each network is encoded as 4 bytes, each AS is encoded as 2 bytes, and each networks is reachable via some fraction of all of the peers (# BGP peers/per net).
# Networks Mean AS Distance # AS's # BGP peers/per net Memory Req ---------- ---------------- ------ ------------------- ---------- 2,100 5 59 3 27,000 4,000 10 100 6 108,000 10,000 15 300 10 490,000 100,000 20 3,000 20 1,040,000
To put memory requirements of BGP in a proper perspective, let's try to put aside for a moment the issue of what information is used to construct the forwarding tables in a router, and just focus on the forwarding tables themselves. In this case one might ask about the limits on these tables. For instance, given that right now the forwarding tables in the NSFNET Backbone routers carry well over 20,000 entries, one might ask whether it would be possible to have a functional router with a table that will have 200,000 entries. Clearly the answer to this question is completely independent of BGP. On the other hand the answer to the original questions (that was asked with respect to BGP) is directly related to the latter question. Very interesting comments were given by Paul Tsuchiya in his review of BGP in March of 1990 (as part of the BGP review committee appointed by Bob Hinden). In the review he said that, "BGP does not scale well. This is not really the fault of BGP. It is the fault of the flat IP address space. Given the flat IP address space, any routing protocol must carry network numbers in its updates." With the introduction of CIDR [4] and BGP-4, we have attempted to reduce this limitation. Unfortunately, we cannot erase history nor can BGP-4 solve the problems inherent with inefficient assignment of future address blocks.
To reiterate, BGP limits with respect to the memory requirements are directly related to the underlying Internet Protocol (IP), and specifically the addressing scheme employed by IP. BGP would provide much better scaling in environments with more flexible addressing schemes. It should be pointed out that with only very minor additions BGP was extended to support hierarchies of autonomous system [8]. Such hierarchies, combined with an addressing scheme that would allow more flexible address aggregation capabilities, can be utilized by BGP-like protocols, thus providing practically unlimited scaling capabilities.