Subject: draft-ietf-idr-bgp-analysis-03.txt

From: Curtis Villamizar <[email-masked]>
Date: Wed, 14 May 2003 10:08:40 -0400

David, Keyur,

I have some suggestions for improvement to this draft ( BGP-4 Protocol
Analysis <draft-ietf-idr-bgp-analysis-03.txt>).  See comments inline
below.  Feel free to take what you consider valid and worth changing.

Curtis

In "1. Introduction" you should mention that BGP4 was the first to
support CIDR and due to their lack of support for CIDR versions 1-3
are considered obsolete and unusable in today's Internet.

------------

Somewhere in key features it should be mentioned that BGP makes the
assumption that packets are routed from source towards destination
independent of the source.  A good place for this would be near the
statement "BGP does not make any assumptions about intra-autonomous
system routing protocols deployed within the various autonomous
systems".  Or refer to the statement in the beginning of
"7. Applicability".

------------

In the following paragraph, why don't we just say that this algorithm
is referred to as a "Path Vector" algorithm.

   BGP uses an algorithm that is neither a pure distance vector
   algorithm or a pure link state algorithm. It is instead a modified
   distance vector algorithm that uses path information to avoid
   traditional distance vector problems. Each route within BGP pairs
   destination with path information to that destination. Path
   information (also known as AS_PATH information) is stored within the
   AS_PATH attribute in BGP. This allows BGP to reconstruct large
   portions of overall topology whenever required.

------------

Alex probably made you put in some FSM stuff (don't read too much into
the wording here).  I don't think it belongs in this document.  That
is clearly something for the protocol spec.

------------

In the section "4. BGP Persistent Peer Oscillations" or in a nearby
section (preferable) it should be mentioned that BGP is work
conserving.  Here is some suggested text:

   A robust BGP implementation is work conserving.  This means that if
   the number of prefixes is bound, arbitrarily high levels of route
   change can be tolerated with bounded impact on route convergence
   for occasionaly changes in generally stable routes.

   A BGP implementation under high load conditions should empty as
   much inbound routing updates from its input streams, processing
   only the most recent route if the route for a given NLRI changes
   multiple times.  TCP also provides blocking on the writes on the
   sender side.  A BGP implementation under load should expect blocks
   on write calls and send only the most recent routes when sockets
   unblock rather than sending entire history.  

   A robust implemention of BGP should have the following
   characteristics:

      1.  It is able to operate in almost arbitrarily high levels of
	  route flap without loosing peerings (failing to send
	  keepalives) or loosing other protocol adjacencies as a
	  result of BGP load.

      2.  Instability of a subset of routes should not affect the
          route advertisements or forwarding associated with the set
          of stable routes.

      3.  High levels of instability and peers of different CPU speed
          or load resulting in faster or slower processing of routes
          should not cause instability and should have a bounded
          impact on the convergence time for generally stable routes.

   Numerous robust BGP implementations exist.  Producing a robust
   implementation is not a trivial matter but clearly acheivable.

------------

I find the following paragraph problematic without further
explanation.

   It is important to note that BGP does not require all the routers
   within an autonomous system to participate in the BGP protocol. In
   particular, only the border routers that provide connectivity between
   the local autonomous system and their adjacent autonomous systems
   need participate in BGP. The ability to constrain the set of BGP
   speakers is one way to address scaling issues.

Either you need to default to the borders and exit at any border or
you need some mechanism to tunnel between border routers for a pure
transport network.  I favor removing the above paragraph.  Tunnelling
to remove BGP is out of scope.  Default routing to reach any arbitrary
border need not be mentioned.  Things which actually do improve
scaling within an AS are RR and confeds.

------------

Section "5.1 Link bandwidth and CPU utilization" may still be overly
simplistic and as a result may be incorrect.  See comments below.

------------

In terms of bandwidth, the number of unique AS paths in practice is a
small number compared to the number of NLRI.  Since many NLRI are
packed in a single update with the AS path included only once, in
practice the number of NLRI completely dominates the amount of
bandwidth consumed.

The MR = 4 * (N + (M * A)) may be inaccurate for the reasons I gave in
the prior paragraph.  The M*A may drasticly understate the impact of
the unique AS paths.  Instead of defining A as the number of AS, A
could be defined as the number of unique AS paths with M*A then being
average AS path length times number of unique AS paths.  

Also why is both memory and bandwidth represented as MR?  Wouldn't BW
be a better variable name for bandwidth?

The O(C * M) thing in the next paragraph is also invalid above some
value of C but for different reasons.  Above some value of C, either
the sender will begin pacing it sending of updates on its own
(suppressing multiple changes over very short periods) or the receiver
will be unable to keep up with the rate of change and force
suppression of multiple changes over very short periods by causing the
BGP socket to block on the sender.

------------

The following statement is incorrect:

   Finally, since the dynamic properties of the network cannot be
   quantitatively bounded, stability must be addressed via heuristics
   such as BGP Route Flap Damping [RFC2439]. Due to the nature of BGP,
   such damping should be viewed as a matter local to an autonomous
   system matter (see also Appendix F.2 of [BGP4]).

The amount of change is inherently bounded in BGP (as I described
above).  BGP Route Flap Damping was initially proposed for two
reasons, 1) to protect a specific commercial implementation that was
not sufficiently robust, 2) to improve convergence of stable routes.
BGP Route Flap Damping is not necessary to bound the amount of change
in BPG routing.

------------

We can drop the following comparison to a historic protocol:

   It may also be instructive to compare bandwidth and CPU requirements
   of BGP with the Exterior Gateway Protocol (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 number of networks reachable via a peer that sends the
   information. Therefore, even if one assumes extreme  instabilities of
   BGP, its worst case behavior will be the same as the steady state
   behavior of its predecessor, EGP.

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

We should drop other references to EGP.

------------

In "5.1.2. Memory requirements", the MR = O((N + M * A) * K) the same
comment applies regarding the M*A term.  A should be unique AS paths,
not number of AS and is not multiplied by K.  In practice the K term
is small because it is the number of peers sending full routing, which
is generally much less than the worst case number of peers.  Large
providers who carry full routing typically send each other only their
customer routes to avoid providing free transit to each other.  This
reduces the impact of K.

------------

We can drop:

   It is interesting to note 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).

------------

In the MR = ((N*4) + (M*A)*2) * K, we can make this quite accurate by
defining N as the average number of routes advertised by each peer and
A as the number of unique AS paths, moving (M*A)*2) outside of the *K
and changing N*4 to N*R and (M*A)*2) to (M*A)*P) where R is the number
of bytes required to store a route and P is the number of bytes needed
to store one AS in an AS path.  If K is small, then some overhead such
as the patricia trie storage figures into R and if K is large, the
data structures may be linked lists off the patricia trie.  Claiming
that a route can be stored in 4 bytes is rather naive.

The N*R*K term in practice dominates over the (M*A)*P term.  If we
conservatively estimate a route as taking 16 bytes (large K allowing
patricia trie overhead to be ignored, indices or pointers to unique AS
Path or other attributes, etc).  If we wanted to include a term to
make things accurate for small K we could add U*X where U is the
number of unique NRLI and X is the overhead per unique NLRI (and I ran
out of useful single letters).  Typically X is greater than R.

------------

   Interestingly, in his review of the BGP protocol for the BGP review
   committee in March of 1990, Paul Tsuchiya noted that "BGP does not
   scale well.

Paul was wrong.  It does scale well and that's why it is being used.
BGP is a solution that scales as well as the problem allows and no
better.

------------

In "10. Security Considerations" we can reference the separate
security analysis document.  Or maybe not.

---

From: Keyur Patel <[email-masked]>
Date: Wed, 14 May 2003 10:15:28 -0700

Curtis:
    Thanks for your comments. We will incorporate them in next revision.
-Keyur