Subject: FW: My BGP Route Update Pacing Draft

From: "Abarbanel, Benjamin" <[email-masked]>
Date: Thu, 18 Jul 2002 18:14:33 -0400

> -----Original Message-----
> From: Abarbanel, Benjamin 
> Sent: Thursday, July 18, 2002 6:10 PM
> To: 'Pedro Roque Marques'; Abarbanel, Benjamin
> Subject: RE: My BGP Route Update Pacing Draft
> 
> 
> Pedro:
> 
> > -----Original Message-----
> > From: Pedro Roque Marques [mailto:[email-masked]]
> > Sent: Thursday, July 18, 2002 5:28 PM
> > To: Abarbanel, Benjamin
> > Cc: [email-masked]'
> > Subject: My BGP Route Update Pacing Draft
> > 
> > 
> > Abarbanel, Benjamin writes:
> > 
> > 
> > Ben,
> > I'm my opinion your draft offers a much worse alternative 
> solution to
> > a problem that is already solved in a much more elegant way 
> using TCP
> > flow control mechanism.
> > 
>   I would agree only if you flow control only update packets. 
> But now we
>   introduce other packets like Capability Message, Inform 
> Message, etc.
>   they too will be flow controlled, right?
> 
>   If so, would it be a problem?
> 
> > To test the assertion above that the problem has been solved, take a
> > mature BGP implementation and congest the resources of receiver. You
> > will see that the sender will automatically throttle it's sending
> > proccess. Contrary to what you state, sessions are not dropped.
> > 
> > BGP when correctly implemented is a very resilient protocol 
> and it has
> > been widly deployed in very demanding environments.
> > 
> > I'm also including some comments inline...
> > 
> > > 2. Abstract
> > 
> > > This document defines a mechanism for controlling or limiting the
> > > rate at which BGP update messages are sent from one peer 
> to the next
> > > when a BGP peer experiences internal congestion. With the
> > > introduction of new dynamic BGP protocol capabilities 
> [CAP] message
> > > or other none BGP session destructive messages, it is necessary to
> > > limit the rate at which the BGP update messages are sent 
> > 
> > What difference does the introduction of capabilities do ?
> > 
>  Same as above.
> 
> > > without
> > > affecting the entire BGP session and without relying on the
> > > transport (TCP) layer
> > 
> > Why not relly on the transport. Flow control is after all
> > traditionally the function of the transport. What makes you think it
> > needs to be reinvented... and how is your version of flow control
> > supperior to the current one ?
> >
> My way allows the two peer to exchange more detail 
> information on the proper
> course of action during congestion, like how fast or how slow 
> to go. The 
> TCP flow control is a stop, start mechanism. Either the pipe 
> is open or closed.
> The other end that is being flow controlled does not know why 
> or by how much he
> will be flow controlled off. Remember on a long session with 
> many hops it takes significant time to communicate the flow 
> control condition by ACKing or not ACKing messages. For me 
> this is not a direct but indirect mechanism.
> In the interim, the pipe will be full of data.
> 
> With a pacing message you can add more intelligence to the 
> communication and convey directly whatever you want without 
> affecting the underlying TCP protocol.
>  
> > > to do so as a normal reaction to data
> > > congestion of the TCP session across the network.
> > 
> > [...]
> > 
> > > 4. Introduction
> > 
> > > This document defines a mechanism for controlling or limiting the
> > > rate at which BGP update messages are sent from one peer 
> to the next
> > > when a BGP peer experiences internal congestion. With the
> > > introduction of new dynamic BGP protocol capabilities 
> [CAP] message
> > > or other none BGP session destructive messages, it is necessary to
> > > limit the rate at which the BGP update messages are sent without
> > > affecting the entire BGP session and without relying on the
> > > transport (TCP) layer to do so as a normal reaction to data
> > > congestion of the TCP session across the network.
> > 
> > > When a router enters a state where either its CPU utilization is
> > > maximized (reaches close to 100%) or its memory is nearly depleted
> > > (less than 10% of memory left), it cannot handle new or heavy
> > > streams of updates from its peers and at times unable to send
> > > messages to its peer in a timely manner (within 30 seconds).
> > 
> > If a router cannot send a message for 30 seconds there is something
> > very wrong with it. It is not clear to me how your 
> mechanism prevents
> > that.
> 
> By starting the pacing early in the game you avoid the 
> implosion that might
> occur. Now, maybe you might say its an internal 
> implementation bug. I bet
> I can put the top vendor's routers under alot of update 
> stress and they will 
> implode. Especially with several hundred sessions.
> 
> 
> > 
> > > As a
> > > consequence it cannot keep current with the topological state. In
> > > some scenarios, a non-congested peer might want to negotiate new
> > > capabilities with a congested peer. The congested peer is so
> > > degraded that its TCP session goes into significant flow 
> control off
> > > conditions and is unable to see the new BGP messages. Peer to peer
> > > communication is severely hampered and as a result the uncongested
> > > peer will take corrective action when its hold timer expires and
> > > drops the session. The uncongested peer computes alternate routing
> > > paths that are suboptimal in distance or attribute and thus affect
> > > the forwarding decisions of all routers in this network. It is
> > > possible that the congested peer's routing (control) 
> plane is badly
> > > degraded but its forwarding plane is at normal working level. The
> > > mistake
> > 
> > What mistake ?
> 
> Recomputing the routes because control plane is not working 
> right. Yet, 
> forwarding plane is working perfect.
> 
> > 
> > > is made by the uncongested peer since it does not see any
> > > Keepalive/Update messages before its Hold timer expires and drops
> > > the session thereby dropping all its associated routes. 
> After routes
> > > are dropped, network instability occurs and suboptimal paths are
> > > used by the remaining peers.
> > 
> > The scenario that you present above is one where you 
> basically have a
> > peer that is totally broken. What does it matter ? A decent
> > implementation will choose to degrade it is service levels
> > gradually. It may achieve that with the current mechanisms.
> > 
> > > The MinRouteAdvertisementInternal and MinAsOriginationInterval
> > 
> > What does min advert interval have to do with the topic in
> > discussion... ? These control only the rate at which the sender may
> > attempt to generate updates, not the rate at which the 
> receiver needs
> > to accept it.
> >
> 
> True, but these timers cause the sender to slow down the rate 
> at which it
> sends the updates on an artificial basis with no regards to 
> current processing
> congestions or such. That is why I mentioned it, in case 
> someone would say
> we have these timers to control the sender why do we need 
> your solution.
>  
> > In BGP a receiver can choose to accept a anyrate of updates 
> it wants.
> >
> 
> Yes, it can by reading or not reading the TCP socket queue. 
> Which gets us
> back to the original point I mentioned earlier. TCP FLOW 
> Control is not
> perfect.
>  
> > 
> > > timers are inadequate since they are mostly implemented on a peer
> > > session basis and studies have shown when they are used they
> > > severely degrade route convergence time. The problem with 
> statically
> > > defined timers (initialized during system load or session
> > > establishment phase) is that they do not adjust to peer internal
> > > dynamically changing congestion conditions.
> > 
> > You are completly missing the point... 
> 
> Please explain what I missed. I found very little background 
> information on these
> timers.
> 
> I have a report done, that shows when the 
> MinRouteAdvertisemetInterval is used
> and set to 30 seconds it degrades the convergence time. When 
> set to 0 or 1, things work much better.
> 
> Check this out:
> http://www.ripe.net/ripe/meetings/archive/ripe-42/presentation
s/ripe42-eof-bgp/sld038.html

> > The problem with the
> > congested peer using TCP flow control to reduce its congestion
> > condition, is that it completely stops all incoming session traffic
> > and thus preventing any messages of high priority nature from being
> > seen.
> 
> What would be high priority in a BGP session... ?
> To my understanding there is no need to introduce priorities 
> in BGP messages.

I think by having dynamic messages that change the nature of the session
traffic, they need to have a sense of priority. You dont want to change
the type of NLRI (say from IPv4 to IPv6) and wait 10 minutes to see if it
happened. Since BGP is piggy backing so much other stuff in its update
messages
it only seems reasonable to put priority on these messages.

> 
> > This document presents a mechanism by which the BGP session of a
> > congested router need not be degraded to the level that
> > communication is broken with its peers.
> 
> Please do offer more to substantiate this other than your claim that
> the problem exists.
>
 
By the fact that the pacing control is more direct and implicit to a
particular
traffic type (in this case update messages). The pacing mechanism is
deterministic, whereas TCP flow control is not. You should talk to people
who build IPC mechanisms to replace TCP about this issue. 

whether the session breaks or badly degraded is an implementation specific
case. 
But I feel there is enough there to warrant the improvements.

The rest needs to be proving empiracly.

Ben

---

From: Dennis Ferguson <[email-masked]>
Date: Tue, 23 Jul 2002 14:42:27 -0700

Hello,

[...]
> In the interim, the pipe will be full of data.

I think you are confused about this.  TCP flow control does not work by
withholding ACKs. TCP always ACKs messages that are received, and flow
control is instead implemented by directly telling the other end
not to send more.  The sender is informed of this condition as soon as
it occurs, and will be informed that the condition has cleared in the
time it takes for a packet to transit the path between the peers (which
is why it is probably good to have a TCP window of outstanding data
at the receiver that it can process until the sender gets the
message to send more, and noting that the receiver is in full control
of just how much or little data that is).  It doesn't get much better
than that.

Now a sender who has had all outstanding packets ACK'd but which
is flow controlled off knows precisely why this has occurred; it
has been sending updates faster than the receiver was willing to
process them.  There is no ambiguity, this is the only way this
situation could occur.

Therefore, out of everything you said above, the only thing I can
see which is perfectly accurate is that the flow-controlled sender
won't know how long it will be flow-controlled off.  This will depend
on what other things the receiving router has to do which it finds
more important than processing BGP messages from this particular
peer.  It is hard to see how the receiver could know how long that
is going to take until it actually does it, however, so it seems
that telling the sender this would require the receiver to be able
to predict the future (the sender knows all about the past already
so there isn't much use having the receiver tell the sender about
that).  I can't dispute that both prescient routers and fortune tellers
might be useful, but I'm not sure that either is a practical
possibility in real life.

While I doubt the implementability of the future-prediction you
seem to be looking for here, however, I think there is another
more fundamental issue which says your approach is incorrect.  That
is, TCP flow control already puts the congested receiver in full
control of its load.  No one can send data faster than the congested
receiver is willing to process it.  The congested receiver directly
controls how much data is outstanding when flow control is asserted.
The sender can't do anything to the receiver that the receiver doesn't
explicitly permit.  With TCP flow control the congested receiver
has full control of its resources.  If there is any problem at all
here, then, it is that the sender has no control at all over the
receiver's resources and hence may be inconvenienced by a congested
receiver which chooses to take its time responding.  And, in fact,
if we're talking about Capability messages in particular, it is of
no advantage in general at all to the busy receiver to get this
message any earlier than updates or anything else; it doesn't even know
the message is coming until it sees it.  Only the uncongested sender
knows there is an outstanding capability message.

So if there is a problem here at all it is a problem for the
idle sender, which might have to wait for a response to a Capability
message, rather than the busy receiver.  Yet your proposed solution
for this is to have the busy receiver do yet more work, continually
predicting the future and sending Inform messages about it to all of
its (possibly many) peers, on the off chance that a sender which
might someday have a Capability message to send, and which has CPU
cycles to burn, isn't inconvenienced.  Since it is the guy who has
CPU cycles available which has the problem in the first place it seems
utterly backwards to make the guy who has no CPU cycles free do more
work to fix it.  The guy with the CPU cycles should be the one to fix
this, i.e. the sender should spend his free cycles doing whatever it
takes to wait until the congested guy gets around to responding.  Then
everything works fine with no protocol changes.

> back to the original point I mentioned earlier. TCP FLOW 

Your original point seems to have been based on a faulty understanding
of how TCP flow control works.

> who build IPC mechanisms to replace TCP about this issue. 

Or the guys that built deterministic FDDI or Token Ring or Token Bus
or ATM LANs to replace non-deterministic Ethernets.  We have networks
where non-deterministic stuff just happens despite our best efforts to
avoid it, so you might be better off to write code which deals with
that rather than depending on some other box to deterministically
predict the future so you aren't inconvenienced.  While you are correct
that this would be easier for your box if other routers could predict
their future for you with 100% reliability, I don't think this is
likely to be possible in any case.

Dennis Ferguson

---

From: Padmaja kotamarthiC <[email-masked]>
Date: Tue, 23 Jul 2002 14:56:12 -0700 (PDT)

Hi ,
    Here's a transcript of my (offline) discussion
with Ben.

sri 

Ben wrote :
> OK,

> From: Padmaja kotamarthiC
[mailto:[email-masked]]
> Sent: Tuesday, July 23, 2002 12:48 PM
> To: Abarbanel, Benjamin
> Subject: RE: Route Update Pacing
> > > Hi Ben ,
> In a *practical* situation with all the
> knobs/configurations provided by the protocol i am
not
> sure if this situation can be encountered. If in a
> *practical* situation this situation is encountered
i
> would consider the onus is on the system/router than
> the protocol. 
> > Like i said for the hypothetical case you mentiond
> limiting the number of routes/prefix per peer based
on
> the system/router specs should sufficiently handle
the
> congestion if not the onus is on the system and not
> the protocol. 
> > sri
> > --- "Abarbanel, Benjamin"
> <[email-masked]> wrote:
> > 300 peers with 100k routes each stressing the
router
> > continuously by
> > adding and withdrawing routes.
> > > > Although this is hypothetical, the router
should be
> > able to handle
> > it without session drops or data loss. And a
> > reasonable convergence
> > time under 1 minute.
> > > > Ben
> > > From: Padmaja kotamarthiC
> > [mailto:[email-masked]]
> > > Sent: Tuesday, July 23, 2002 12:24 PM
> > > To: Abarbanel, Benjamin
> > > Subject: RE: Route Update Pacing
> > > > > > > > > Hi Ben ,
> > > The thing to understand is what conditions
> > > this situation arises. How many peers and routes
> > are
> > > being processed when this situation (congestion)
> > is
> > > encountered by you? I am just trying to
understand
> > if
> > > there's a:  system/router bottleneck or protocol
> > > issue.
> > > > > > sri
> > > > > > --- "Abarbanel, Benjamin"
> > > <[email-masked]> wrote:
> > > > > From: Padmaja kotamarthiC
> > > > [mailto:[email-masked]]
> > > > > Sent: Tuesday, July 23, 2002 11:38 AM
> > > > > To: Abarbanel, Benjamin; [email-masked]
> > > > > Cc: [email-masked]
> > > > > Subject: Route Update Pacing
> > > > > > > > > > > > > > > Hi Ben ,
> > > > > What is the affect of this solution on
> > > > > convergence ? Your solution seems to be
> > similar to
> > > > > minimumrouteadvertisementinterval with a
> > > > modification
> > > > > that this timer comes into picture only
during
> > > > > congestion rather than all times. If we can
> > modify
> > > > the
> > > > > role of minimumrouteadvertisementinterval by
> > > > > implementing as stated above it can solve
the
> > > > issue
> > > > > too rather than introducing new messages.
> > > > > > > > > > sri
> > > > > > > > > Sri:
> > > > The minimumrouteadvertisementinterval for IBGP
> > > > routes works 
> > > > on a preconfigured timeout value. This value
> > does
> > > > not change 
> > > > dynamically to load/stress conditions
therefore
> > it
> > > > is suboptimal
> > > > to handle the congestion problem. There has
been
> > a
> > > > study done
> > > > that shows its partner timer
> > > > MinRouteAdvertisementInternal for EBGP
> > > > routes to take to long and cause convergence
> > > > problems.
> > > > > > > > check this out:
> > > > > > > >
> > >
> >
>
> > > > > > Ben

__________________________________________________
Do You Yahoo!?
Yahoo! Health - Feel better, live better
http://health.yahoo.com