Subject: Re: Open Routing Area meeting in Vienna

From: Curtis Villamizar <[email-masked]>
Date: Fri, 01 Aug 2003 16:35:08 -0400

In message <p06001a1dbb4f10739860@[64.101.214.208]>, "John G. Scudder" writes:
> 
> BGP's convergence time is said to be O(N!) in the number of 
> autonomous systems in the Internet.  Eek!  However, leaving aside the 
> fact that that's a theoretic upper bound and not the expected case, 
> that is a bound for Internet-wide convergence for a particular 
> destination; there is no term for number of data objects ("routes") 
> in the system.  So that can't be relevant to your comment.

That's just a worst case for the complete withdraw of a route where
longer AS path alternatives are slower to withdraw than the primary.
If route withdraws are treated immediately (or at least quickly) and
changes propogated more slowly, then route withdraw is order(1).  A
route addition is order(1), the addition of a better route is order(1)
and a route change where the better route is removed is order(1).

> That leaves the on-box component.  A decent BGP implementation should 
> have a per AF cost of approximately O(RPlogP) where R is the number 
> of routes ("paths") per prefix, and P is the number of prefixes 
> (destinations) stored in the local db for that AF.  So, right, that's 
> not linear.  But it's per AF.  The cost of any BGP-like protocol 
> supporting a set of related data will equally be O(RPlogP).  So 
> either you sum these terms into BGP, or you divide them into 
> different protocols... and still have to sum them.  So once again, I 
> don't see the basis for your "two smaller sandwiches" comment.

A little more accurate than what I said with NlogN but if you consider
R to be a constant, then the same thing.  The point that you are
making that this is per AF is the same point that I was making.

> This might be about software engineering, or protocol aesthetics, but 
> I don't think it's about theoretical convergence properties.
> 
> --John

Right.

Curtis

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

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 01 Aug 2003 16:35:08 -0400

Right.

Curtis

---

From: Randy Bush <[email-masked]>
Date: Fri, 1 Aug 2003 16:13:43 -0700

> and a route change where the better route is removed is order(1).

actual measured data in the real internet shows a single announce a
couple of hops away can (often) result in over 40 announces and a
few withdraws interspersed.  a single withdraw can be more
exciting.

will be presenting next month at apnic.

randy

---

In theory there is no difference between theory and practice,
but in practice, there is.  -- Patrik Fältström <[email-masked]>

---

From: Randy Bush <[email-masked]>
Date: Fri, 1 Aug 2003 16:13:43 -0700

randy

---

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 01 Aug 2003 22:34:01 -0400

> will be presenting next month at apnic.

For the announce you'll receive one announce for each feasible path.
If the best tend to come first or early, the rest are essentially
remembered but cause no work.  Since ignoring this input is of almost
no consequence, only inserting in AdjIn-RIB, this is still order(1).

The problem with withdraws is that in the case of a split past the
point of failure, one branch of the split can announce alternates that
point to the other side of the split even though they share a common
failure.  For example:

          c ---f--->
         / \   .
    a---b   e  .
         \ /   .
          d ---g--->

When a-b fails, d may decide the best path is by way of ... c-b-a.
This may go through e-c-b-a.  It can't announce back to e, but can
announce the change to g.  Same thing happens at c.  

The only way to prevent this is for c and d to announce the withdraw
immediately, and then if they still have a feasible route after some
number of seconds announce the changed route.  

The objection is that you don't want to black hole traffic so announce
the change.  A slightly smarter way would be to do this (propogate the
withdraw and delay propogating the change) if the replacement route
has a common AS path sequence with the route that is replacing it.
This avoids the explosion and at least partially eliminates the
objection.

***If*** route withdraws are treated immediately (or at least quickly)
and changes propogated more slowly, then route withdraw is order(1).

Most of Craig's work uncovered bugs in widely used implementations.
This is one of them.  Craig pointed out this explosion on withdraw
quite some time ago.

If withdraws propogate very fast and changes are delayed, all of the
withdraws propogate before anyone announces a change.

None of this is news.  The same solutions that were discussed years
ago when Craig brought this up still apply today.  If providers want
this fixed maybe they are not asking loud enough or they forgot why
they didn't want it fixed the last time this issue came up.

The last time this came up avoiding a potential black hole was more
important than the extra routing information so provider input was to
keep things as is.

Curtis

btw- congratulations to the researchers for discovering it again.

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 01 Aug 2003 22:34:01 -0400

c ---f--->
         / \   .
    a---b   e  .
         \ /   .
          d ---g--->

Curtis