Subject: Re: [Idr] AD-review comments on draft-ietf-idr-bgp-analysis-04.txt

From: Alex Zinin <[email-masked]>
Date: Mon, 19 Apr 2004 13:06:50 -0700

Folks-

 I've received some more comments on this document included below.
 Please take them into consideration.

 Thanks.
 
-- 
Alex
http://www.psg.com/~zinin/

>>     # NLRI       Mean AS Distance       # AS's     Bandwidth (MR)
         ^          ^                        ^        ^
         N          M                        A        BW
>>     ----------   ----------------       ------    ----------------
>>     40,000       15                     400        184,000   bytes
>>     100,000      10                     10,000     800,000   bytes
>>     120,000      10                     15,000     1,080,000 bytes
>>     140,000      15                     20,000     1,760,000 bytes
>> 
>>     [note that most of this bandwidth is consumed by the NLRI exchange]
> 
> Is the caption for column 3 correct? It says "# AS's", which reads as
> "number of AS's" while it seems it should be the number of unique paths.

   The text is clear; but your caption would be better.

   At least here the arithmetic is right.

   BTW, the caption for column 4 is also wrong. "MR" hasn't been
introduced yet.

>>    During periods of Internet instability, changes to the reachability
>>    information are passed between routers in UPDATE messages.  The
> 
> While theoretically the text is correct and we could talk about periods
> of stability and instability of the Internet, I wonder if this text is
> still applicable from the practical perspective. I.e., the continuous
> churn that the Internet BGP speakers experience ensures that they
> practically always have something to process.

   Agreed: this is as "stable" as we're going to get; we shouldn't call
it "instability".

> Probably instead of talking about periods of "Internet stability" and
> "Internet instability" we could talk about something like "periods of
> stable state among BGP speakers when they do no have new updates to
> communicate to each other".

   That's accurate; but I wonder whether it's worth talking about.

> Not sure I follow here. What is meant by the "steady state" here? If it
> means convergence on a stable topology after the initial exchange of
> updates, then why talk about "stability of the Internet"?

   I took this to mean that whenever a BGP session starts, there's a
potentially long initial exchange of routes, and we mean to exclude
that startup transient.

   But, of course, we're back to the "stable Internet" paradigm. :^(

> In other words, if the Internet is unstable then can we say that the
> BGP speakers are in steady state?

   We can, but it's kind of confusing. I believe the intent was to
have a "slightly unstable" Internet causing CPU load which doesn't
become visible until we get past the startup transient.

> In the lack of topology changes, it seems that the consumption should
> instead depend on the number of peers (affects KEEPALIVE processing)
> and the number of persistently oscillating routes potentially present
> in the network...

   I'd rather talk in those terms; but it's a rather major rewrite of
this section.

>>                                                           This assumes
>>    that as the Internet grows,  the overall stability of the inter-AS
>>    connectivity of the Internet can be controlled.
> 
> please specify how it is assumed to be "controlled", e.g. through operational
> practices.

   I believe historically this meant route-flap damping.

>>                                                    In particular, while
>>    the size of the IPv4 Internet routing table is bounded by O(232 * M),
> 
> 232 or 2^32?

   Neither makes much sense. Usually one would simply say O(M).

>>    (where M is a slow-moving function describing the AS
>>    interconnectivity of the network),
> 
> slow-moving or slow-growing?

   I believe "slow-moving" is correct -- especially as compared to the
speed of the arm-waving inherent in this sentence. ;^)

>>                                       no such bound can be formulated
>>    for the dynamic properties (i.e., stability) of BGP.

   There's the "stability" word again. :^(

>>                                                          Although, the
>>    dynamic properties of the network cannot be quantitatively bounded,
>>    they can be controlled within BGP.  Beyond certain changes in the
>>    network, BGP can start to suppress such changes using BGP Route Flap
>>    Damping [RFC2439], pacing of its route updates, or BGP would be
>>    unable to keep up with the changes and force suppression of multiple
>>    changes over very short periods by causing the BGP peer socket to
>>    block on the sender.

   The arms are waving again. We list methods of suppressing _some_
multiple changes and claim this avoids suppression of multiple changes.
(This sentence would be quite correct if we said "force suppression of
_all_ changes...")

>> 6.1.2.  Memory requirements
>> 
>>    To quantify the worst case memory requirements for BGP, we 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 unique AS paths as A.  Then the worst case memory
>>    requirements (MR) can be expressed as
>> 
>>            MR = O(N + (M * A))
>> 
>>    Since a mean AS distance M is a slow moving function of the
>>    interconnectivity ("meshiness") of the Internet, 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.  As a result, BGP's memory
>>    scaling properties are linearly related to the total number of
>>    networks in the Internet.
>> 
>>    The following table illustrates typical memory requirements of a
>>    router running BGP.  We denote average number of routes advertised by
>>    each peer as N, the total number of unique AS paths as A, the mean AS
>>    distance of the Internet as M (distance at the level of an autonomous
>>    system, expressed in terms of the number of autonomous systems),
>>    number of bytes required to store a route as R, and number of bytes
>>    required to store one AS in an AS path as P.  It is assumed that each
>>    network is encoded as four bytes, each AS is encoded as two bytes,
>>    and each networks is reachable via some fraction of all of the peers
>>    (# BGP peers/per net).  For purposes of the estimates here, we will
>>    calculate MR = ((N * R) + (M * A) * P)

   One is forced to guess that R = 4.

   I think the intent was that P is two times the BGP-peers column.

>>      # Networks  Mean AS Distance # AS's # BGP peers/per net Memory Req (MR)
          ^         ^                  ^      ^                 ^
          N         M                  A      P (???)           MR
>>      ----------  ---------------- ------ ------------------- --------------
>>       100,000           20         3,000         20             1,040,000
>>       100,000           20        15,000         20             1,040,000
>>       120,000           10        15,000        100            75,000,000
>>       140,000           15        20,000        100           116,000,000

   Well, to tell truth, I've forgotten how I reproduced two of those MR
numbers. But it's certainly obvious they can't all be right; and today I
can't reproduce a single one of them.

>>    In analyzing BGP's memory requirements, we focus on the size of the
>>    forwarding table (and ignoring implementation details).  In
>>    particular, we derive upper bounds for the size of the forwarding
>>    table.
> 
> The above doesn't look like calculations for a forwarding table--the
> FIB doesn't normally contact AS-PATH info or all possible paths to a
> destination.

   Agreed. I didn't think that was a FIB calculation -- though I never
was sure what it was...

_______________________________________________
Idr mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/idr

---

From: David Meyer <[email-masked]>
Date: Mon, 19 Apr 2004 13:33:44 -0700

All, 

	Thanks for the comments. We're working on the update as
	we speak.

>> speed of the arm-waving inherent in this sentence. ;^)

	what I was trying to get at is that the size of the RIB
	is going to be bounded by something like 2^32
	*<something>, where the <something> represents the
	AS-meshiness, which (in practice) doesn't change at a
	very large rate. So O(M) is incorrect. The basic idea was
	to (attempt to) contrast the size of the RIB with its
	dynamic properties. So do people disagree that the size
	of the RIB is bounded in this way?

	Thanks,

	Dave

---

From: David Meyer <[email-masked]>
Date: Mon, 19 Apr 2004 13:33:44 -0700

All, 

	Thanks,

	Dave