Subject: My BGP Route Update Pacing Draft

From: "Abarbanel, Benjamin" <[email-masked]>
Date: Thu, 18 Jul 2002 15:31:54 -0400

Hi all:

   Our recent discussions on this list and my recent work 
 experiences have led me to write this draft and offer it 
 to the IETF community. I would appreciate any comments 
 anyone has to make.
 
 Thanks in advance,
 Ben

---

From: vrishab sikand <[email-masked]>
Date: Thu, 18 Jul 2002 13:37:20 -0700 (PDT)

Specific comment:
Unless the rate of pacing is defined in absolute terms (as opposed to the a subjectively for e.g
yellow 4: reduce update message traffic by 40% of your normal rate). It will be very difficult to verify compliance.
Also in my experience, the "normal rate" varies drastically from vendor to vendor.
 
General comment:
 It appears to me that here is an attempt to solve an internal scheduling or horse power problem with the help of external protocol. 
This mechanism may put undue burden on the transmitting router, which is in the best interest of quick convergence in mind is sending prefixes as fast as possible. 
  "Abarbanel, Benjamin" <[email-masked]> wrote: Hi all:

Thanks in advance,
Ben

Network Working Group Ben Abarbanel
Internet Draft Marconi Communicatons
Expiration Date: December 2002 

BGP Route Update Pacing

draft-abarbanel-bgp-route-update-pacing-00.txt

1. Status of this Memo

This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026 except that the right to
produce derivative works is not granted.

Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.

Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as ``work in progress.''

The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt

The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.

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 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.

3. Specification of Requirements

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", 
"SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be 
interpreted as described in RFC 2119 [RFC2119].

Internet Draft draft-abarbanel-bgp-route-update-pacing-00.txt [Page 2]

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). 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 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 MinRouteAdvertisementInternal and MinAsOriginationInterval 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. 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.

TCP Out of Band Data or Urgent Message is one way to bypass the TCP flow 
control condition and allow high priority BGP messages to get to the 
congested peer, assuming it is able to read the session socket queue. This 
solution has its drawbacks as described in [UNIX-NET] chapter 21, p. 568. 

Internet Draft draft-abarbanel-bgp-route-update-pacing-00.txt [Page 3]

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. By using a peer to peer pacing mechanism which allows one peer to 
rate limit the number of update messages per second received from another 
peer, it can avoid the severe congestion conditions and process these 
messages at a manageable level. In addition, the uncongested peer has the 
knowledge to send high priority messages ahead of or in place of the normal 
high volume of update messages.

Usually, topological disturbances are spiky in nature and once they subside, 
the network returns to its optimum path oriented level. Whatever caused the 
network to become unstable, such as routers handling too much data in a small 
period of time or routers loosing their sessions or their links going up and 
down, occurs in most live network on an infrequent basis. By using the pacing 
mechanism as outlined in this draft, a BGP peer can prevent the serious 
congestion long before it is in trouble and thus ride through topological 
disturbances and still regain its stability without causing its sessions to 
drop or its routes/paths to be discarded and recomputed.

The assumption in this spec is that the source of most or all of the internal 
BGP router congestion is due to the heavy reception of update messages from 
neighboring peers containing large number of routes.

5. BGP Update Pacing Mechanism

The BGP Update Message Pacing Mechanism is used to slow down the rate at 
which a peer sends update messages to another. This extension to the BGP 
protocol is simplified to use session non-destructive messages such as INFORM 
as described in [INFORM]. The pacing is performed dynamically upon congestion 
detection and subsidence and thus needs to use the new [INFORM] message that 
will not infringe on the underlying BGP protocol or all its semantics and 
rules.

5.1 BGP Update Message Pacing (PACE) Dynamic Capability

The BGP Update Message Pacing capability is dynamically negotiated with all 
BGP speakers as type code=PACE (where, PACE=TBD) per TLV structures as 
defined in [BGP-CAP] of the OPEN message or anytime after session is 
established using the Dynamic Capability Message as defined [DYN-CAP] 
specification. All those peers that accept the PACE capability will be 
expected to support the new INFORM message as defined in [INFORM] 
specification to carry the pacing TLV structure. 

Internet Draft draft-abarbanel-bgp-route-update-pacing-00.txt [Page 4]

All PACE capable routers will provide a configuration option to their 
operator to enable the BGP Update Message Pacing mechanism on a per peer 
basis. 

Any peer wishing to withdraw the PACE capability can do so dynamically using 
the Dynamic Capability message as outlined in [DYN-CAP] specification. Once 
withdrawn, affected peering session will remain intact but will not benefit 
from the performance improvements offered by the pacing mechanism.

5.2 Use of INFORM Message

The INFORM message as described in [INFORM] is used to carry the rate 
limiting (pacing TLV) control structure to neighboring peers. This 
information informs the peer that the current BGP router has entered a 
congestion state and it is to rate limit its transmission to the level 
specified. 

The INFORM message contains the following PACE TLV structure:

Type = Pacing Information, type=TBD 
Length = 2
1st Byte of Value = Cmd as shown below 
2nd Byte of Value = Level as shown below

Cmd Description 
------- -----------
11 Request to Pace update messages
12 ACK Response to Pace Update messages
13 NACK Response to Pace Update Messages

A. Request to Pace Update Messages Level Indication (code=11)

The rate is divided into sub levels in term of categories (Gray, Yellow, 
Orange, Red, and Green) to denote the level of pacing which is directly 
related to the level of congestion experienced within the congested peer. The 
colors are used as simple handles used for flagging the severity of the 
condition. The colors are also used as indicators for display by the NMS to 
identify the rate limiting levels from any neighboring peer to the operator. 
Associated Level Management MIBs are defined in section 6. 

The actual pacing control is done via the sub levels within these colors. 

Level Description
------ -----------
Gray (Entering minor congestion state)
1 Reduce update message traffic by 10% your normal rate.
2 Reduce update message traffic by 20% your normal rate.
3 Reduce update message traffic by 30% your normal rate.

Internet Draft draft-abarbanel-bgp-route-update-pacing-00.txt [Page 5]

Yellow (Entering medium congestion state)
4 Reduce update message traffic by 40% your normal rate. 
5 Reduce update message traffic by 50% your normal rate.
6 Reduce update message traffic by 60% your normal rate.

Orange (Entering major congestion state)
7 Reduce update message traffic by 70% your normal rate. 
8 Reduce update message traffic by 80% your normal rate.
9 Reduce update message traffic by 90% your normal rate

Red (Entering critical congestion state)
10 Complete cessation of all update message traffic (flow off). 
At this Level the receiving peer might decide to bypass the 
Congested Router and pick another less optimal router for the
affected Routes.

Green (Exiting any congestion state)
0 Restore update message traffic to your normal level (flow on).
Routes redirected can be resumed to the original peer.

The receiving peer will send an INFORM message with an ACK or NACK Indicating 
it has received and understood the pacing request and will either comply with 
the it or forbid it. If the congested peer receives a NACK, it should remove 
that peer from its list of PACE capable peers but still maintaining its 
session without the use of Pacing. If the NACKing peer decides at a future 
date to re-enable the Pacing with the local peer, it will renegotiate the 
PACE capability with the local peer at that time.

B. Response Message Error Indication:

Level Description
------ -----------
0 ACK indication. The peer will comply with the 
Pacing level request.
1 NACK indication. The peer is unable to perform Pacing or comply 
with the pacing level requested.

5.3 INFORM Message Response Timer

When a congested peer sends an INFORM message with a "Request to Pace Update 
Messages (code=11)" to all peers that support the pacing feature, it will 
also start an associated INFORM Message Response Timer. Any peer that does 
not respond within a 30 second timeout period with either an ACK/NACK INFORM 
Response message, its associated session will be dropped. This is done to 
clear any PACE capable peers that are also congested to the point where their 
communication with the local congested peer is severed.

Internet Draft draft-abarbanel-bgp-route-update-pacing-00.txt [Page 6]

5.4 Congestion Detection Within the Router

There are at least two ways congestion could be detected and measured by a 
BGP router.

- A high CPU utilization condition 

- A Lack of available memory to accept incoming BGP messages or inability 
to get memory to successfully complete BGP processing. 

5.4.1 CPU Utilization Based Level Computation

It is recommended that when the congested router detects its inability to 
perform route calculations or accept new BGP session messages at a normal 
rate meaning the current router's CPU utilization is more than 49%, it should 
inform all its peers of a rate limiting level and slow them down accordingly. 

The recommended way for computing the Level, based on percent CPU 
Utilization, is done using the following:

Level = (((%CPU Utilization – 50) x 2) + 5) / 10).
Where, % CPU Utilization is a whole integer number. Use Integer math 
here to remove any fractional value.

Note: If computed Level is negative, go to Green and set Level = 0. If 
Level = 0 send INFORM message with pacing Level = 0, implying return 
to normal (100%) update rate.

Level implies, whatever number of messages you transmitted per second 
before, transmit (100 – (Level x 10))% of that now. 

e.g. If you transmitted 100 messages/second before. A level 2 (20%) 
reduction will cause you to transmit 80 messages/second now.
Assumption is that these messages have an average size (1500 bytes).

5.4.2 Memory Allocation Based Level Computation

It is recommended that when the congested router detects its inability to 
perform route calculations or accept new BGP session messages at a normal 
rate meaning the current router's memory allocation is more than 69%, it 
should inform all its peers of a rate limiting level and slow them down 
accordingly. 

The recommended way for computing the Level, based on percent Memory 
Allocation, is done using the following:

Level = (((%Memory Allocated – 70) x 2) + 5) / 10).
Where, % Memory Allocated is a whole integer number. Use Integer math 
here to remove any fractional value.

Internet Draft draft-abarbanel-bgp-route-update-pacing-00.txt [Page 7]

Note: If computed Level is negative, go to Green sub-group and set 
Level = 0. If Level = 0 send INFORM message with pacing Level = 0, 
implying return to normal (100%) update rate.

5.5 INFORM Message Throttling

Once the congested peer receives acknowledgement from another peer, it will 
send a modification INFORM message with a new Level to that peer after the 
computed pacing Level changes by at least 1 value. This will amount to no 
more than one INFORM modification message every 5 seconds. This is done to 
debounce any spiky bursts of INFORM messages to all PACE negotiated peers 
each time the computed pacing Level changes. Depending on vendor 
implementations, the internal utilization levels could change at the 
Microsecond or Millisecond rate.

6. Implementation Specific Mechanisms

The Memory Allocation and CPU Utilization Level detection algorithms 
discussed in section 5.4.1 and 5.4.2 are suggested ways one can implement 
these solutions. However, each vendor can implement a unique Memory 
Allocation and CPU Utilization Level detection algorithms that best suits 
his/her needs and will not negatively impact the overall BGP Route Update 
Pacing mechanism described in this spec. Any issues relating to internal 
implementation algorithms are outside the scope of this document.

7. Level Indicators Management MIBs

TBD

8. Security Considerations

This extension to BGP does not change the underlying security issues.

9. References

[BGP-CAP] Chandra, R., Scudder, J., "Capabilities Advertisement with 
BGP-4", draft-ietf-idr-rfc2842bis-02.txt

[DYN-CAP] Chen E., Sangli S., "Dynamic Capability for BGP-4", 
draft-ietf-idr-dynamic-cap-02.txt, October 2002.

[INFORM] Nalawade G., Scudder J., "BGPv4 INFORM Message",
draft-nalawade-bgp-inform-00.txt, December 2002

[BGP-4] Rekhter, Y., and T. Li, "A Border Gateway Protocol 4 
(BGP-4)", RFC 1771, March 1995.

Internet Draft draft-abarbanel-bgp-route-update-pacing-00.txt [Page 8]

[BGP-4-DRAFT] Rekhter, Y. and T. Li (editors), "A Border Gateway Protocol 4
(BGP-4)", Internet Draft draft-ietf-idr-bgp4-18.txt, 
January 2002.

[UNIX-NET] Stevens, R., "UNIX Network Programming, Vol 1", Second Edition
1998 Prentice Hall, Inc.

10. Author Information

Ben Abarbanel
Marconi Communications
1595 Spring Hill Road, 5th Floor
Vienna, VA 22182
Email: [email-masked]

---------------------------------
Do You Yahoo!?
Yahoo! Autos - Get free new car price quotes

---

From: Pedro Roque Marques <[email-masked]>
Date: Thu, 18 Jul 2002 14:27:47 -0700 (PDT)

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.

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...

> 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 ?

> 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 ?

> to do so as a normal reaction to data
> congestion of the TCP session across the network.

[...]

> 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.

> 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 ?

> 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.

In BGP a receiver can choose to accept a anyrate of updates it wants.

> 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... 

> 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.

> 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.

  Pedro.

---

From: [email-masked]
Date: Mon, 22 Jul 2002 14:34:15 -0700

Ben,

One thing we discussed at the meeting in Yokohama was that we MUST NOT
associate protocol actions with the INFORM message.  It is Informational
ONLY.  An INFORM may be followed by a protocol action (such as a NOTIFY),
but, in and of itself, it is not to be used to trigger protocol actions.

Andrew

On Thu, Jul 18, 2002 at 03:31:54PM -0400, Abarbanel, Benjamin wrote:
> Delivered-To: [email-masked]
> Delivered-To: [email-masked]
> Delivered-To: [email-masked]
> From: "Abarbanel, Benjamin" <[email-masked]>
> To: "[email-masked]'" <[email-masked]>
> Subject: My BGP Route Update Pacing Draft
> Date: Thu, 18 Jul 2002 15:31:54 -0400
> X-Mailer: Internet Mail Service (5.5.2650.21)
> Precedence: bulk
> X-OriginalArrivalTime: 18 Jul 2002 19:34:50.0014 (UTC) FILETIME=[2E818BE0:01C22E92]
> 
> Hi all:
>

---

From: Manav Bhatia <[email-masked]>
Date: Tue, 23 Jul 2002 09:42:10 +0530

Hi Ben,
I have some thoughts on the draft.

The crux of your draft is that if a peer gets so congested that it is not
able to send any UPDATE/KEEPALIVE message to the remote uncongested peer
then the session can break down because of the Hold Timer expiring and it
can be prevented by sending some pacing information which will inform the
uncongested peer to limit its route advertisement rate. The PACING
information will too be carried in the TCP packets, so if the TCP is
implementing flow control and is not sending packets to avoid congestion
then how will the PACING information be sent? And if  TCP can send the
PACING information then it can as well send the KEEPALIVE packet which will
keep the HoldTimer from expiring at the other end.

Secondly, if you are aware that your router is old and might come in a
situation when it might not be able to handle the full feed of BGP Updates
from the remote end then it can negotiate a HoldTime of zero and keep the
session running even when it is in the congested state.

Thirdly, the very idea of artificially impeding reachability information
(or sending of BGP UPDATE messages) doesn't really appeal to me. I was
initially against the idea of using MinRouteAdvertisementInternal etc
timers in my implementation arguing that a router should pack off any
reachability information it has as soon as it comes to know of it. But this
created a problem when i got say some 80K routes. I would then be sending
80K packets to my other peers! Finally , better sense prevailed on me and i
started using the timers for efficiently packing my NLRIs in the UPDATE
messages. This is one point where i hold my reachability information from
my peers & I discourage it doing any other time. IMHO i feel we should let
TCP take care of withholding any data it wants with itself till the
congestion state rides by rather than us interfering with it.

What happens say when an uncongested router receives pacing information
telling it to reduce the advertisement rate by some 70%. In that case there
will be many UPDATEs lying with it remaining to be yet announced to the
remote peer which is experiencing congestion. Now what if the uncongested
network receives withdrawals (both implicit and explicit) for certain
prefixes which have already been announced or remain yet to be announced?
You open up a can of worms now !!

You have to now flush all your output buffers regardless of the congestion
state your remote peer lies in!

Thus you end up doing what you always wanted to avoid.

I think a cleaner and a much simpler approach would be to dynamically
negotiate the value of the HoldTimer during the session. If you feel you
are getting congested then increase the value and once the red flags are
all down you can revert back to your original value or decrease it back
again.

Regards,
Manav

----- Original Message -----
From: "Abarbanel, Benjamin" <[email-masked]>
To: <[email-masked]>
Sent: Friday, July 19, 2002 1:01 AM
Subject: My BGP Route Update Pacing Draft

| Hi all:
|
|    Our recent discussions on this list and my recent work
|  experiences have led me to write this draft and offer it
|  to the IETF community. I would appreciate any comments
|  anyone has to make.
|
|  Thanks in advance,
|  Ben
|
|
|
|

---

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

Hello,

> uncongested peer to limit its route advertisement rate.

Note that, right now, it is impossible to send BGP updates to a peer any
faster than the peer is willing to process them.  Period.  TCP flow control
ensures this.  It hence isn't possible for update senders to put any more
load on a peer than that peer itself chooses to accept.  If a BGP peer
wants to ensure that its CPU is never more that 50% busy it can do
that already by not spending more than 50% of its CPU processing BGP updates,
there is no way its neighbours can make it work harder than it wants to.
And the peer is free to stop processing update messages whenever it needs
to, like when it needs to send KEEPALIVEs, so a peer which voluntarily keeps
processing incoming updates which it should have been sending KEEPALIVEs is
just broken and needs to be fixed.

I hence don't think this draft has anything to do with fixing busy
BGP speakers, they are already in full control of their load.  The
draft seems to in fact have something to do with the inconvenience
an idle remote peer might suffer if the busy guy takes a long time
to respond to, say, a Capability message, but since the guys who are
inconvenienced are the guys who have available CPU cycles it seems to me
to be appropriate for those guys to spend the cycles dealing with this
themselves.

Dennis Ferguson