Memory requirements
Connected: An Internet Encyclopedia
Memory requirements
Up:
Connected: An Internet Encyclopedia
Up:
Requests For Comments
Up:
RFC 1774
Prev: Link bandwidth and CPU utilization
Next: Applicability of BGP
Memory requirements
Memory requirements
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 BGP4, we have attempted to reduce
this limitation. Unfortunately, we cannot erase history nor can
BGP4 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 BGPlike protocols, thus providing practically unlimited
scaling capabilities.
Next: Applicability of BGP
Connected: An Internet Encyclopedia
Memory requirements
