Subject: [RRG] Route Flap Damping parameters

From: "LOWE Jim" <[email-masked]>
Date: Tue, 26 Jun 2007 07:15:07 -0500

Hello,
 
I have been following the discussion about BGP path hunting ('[RRG] BGP
path hunting, MRAI timer and Path Length Damping') on this list with
some interest. With Route Flap Damping (RFD) being a possible factor in
the observed behavior, I had some questions about determining values for
its configurable parameters (Suppression threshold, Reuse threshold,
Time-to-half amplitude, and Maximum suppression time). 
 
I understand that prior to the recommendation made in RIPE-378 to not
use RFD, RIPE-229 made recommendations about configurable parameter
settings. In reading RIPE-229, it seems the recommendations were not
strongly based on observations of actual dynamics (although I could be
dead wrong on this since I'm not familiar with all the work that lead to
the creation of RIPE-229). As well, from reading a selection of papers
on the subject of RFD preventing timely convergence, there doesn't seem
to be an analysis of what might happen if RFD parameter sets other than
the common defaults were applied, nor does there appear to be a history
of literature on this subject. My reading in this area has been by no
means exhaustive, so my questions are: has there been any work done on
determining what the impact of other sets of RFD parameters might be;
how have (or might) such sets be chosen; have the dynamical properties
of the RFD algorithm been worked out - with a view towards assessing
whether they would even be potentially capable of improving observed
dynamics? I have been thinking about these areas, but wasn't sure if it
had all been done before and these were dumb questions.
 
Cheers,
Jim.

---

From: "K. Sriram" <[email-masked]>
Date: Tue, 26 Jun 2007 12:52:37 -0400

Jim:

I am not sure these papers provide all the insights you are looking for,
but they generally address some of the questions you've posed.

http://www.ensc.sfu.ca/~ljilja/papers/spects2005_steve.pdf
http://www.eecs.umich.edu/~zmao/Papers/sig02.pdf
http://www.antd.nist.gov/~ksriram/BGP_Security_Sriram_IEEE_JSAC.pdf
(The third one includes an analytical sensitivity study w.r.t RFD parameters;
comparing parameter values used by two different vendors; however, the study
primarily reports simulation results of BGP vulnerability to attacks 
on BGP sessions,
including aggravating influence due to RFD.)

Sriram

At 08:15 AM 6/26/2007, LOWE Jim wrote:
>Hello,
>
>I have been following the discussion about BGP path hunting ('[RRG] 
>BGP path hunting, MRAI timer and Path Length Damping') on this list 
>with some interest. With Route Flap Damping (RFD) being a possible 
>factor in the observed behavior, I had some questions about 
>determining values for its configurable parameters (Suppression 
>threshold, Reuse threshold, Time-to-half amplitude, and Maximum 
>suppression time).
>
>I understand that prior to the recommendation made in RIPE-378 to 
>not use RFD, RIPE-229 made recommendations about configurable 
>parameter settings. In reading RIPE-229, it seems the 
>recommendations were not strongly based on observations of actual 
>dynamics (although I could be dead wrong on this since I'm not 
>familiar with all the work that lead to the creation of RIPE-229). 
>As well, from reading a selection of papers on the subject of RFD 
>preventing timely convergence, there doesn't seem to be an analysis 
>of what might happen if RFD parameter sets other than the common 
>defaults were applied, nor does there appear to be a history of 
>literature on this subject. My reading in this area has been by no 
>means exhaustive, so my questions are: has there been any work done 
>on determining what the impact of other sets of RFD parameters might 
>be; how have (or might) such sets be chosen; have the dynamical 
>properties of the RFD algorithm been worked out - with a view 
>towards assessing whether they would even be potentially capable of 
>improving observed dynamics? I have been thinking about these areas, 
>but wasn't sure if it had all been done before and these were dumb questions.
>
>Cheers,
>Jim.
>
>

K. Sriram, Ph.D.
Advanced Network Technologies Division
National Institute of Standards and Technology
100 Bureau Drive, Stop 8920
Gaithersburg, MD 20899-8920
Phone: (301) 975-3973
E-Mail: [email-masked]
Web:  http://www.antd.nist.gov/~ksriram/

---

From: "LOWE Jim" <[email-masked]>
Date: Tue, 26 Jun 2007 14:42:40 -0500

Hi Sriram,
 
Thank-you for pointing out these references. I have read the first two,
but the third one (which I assume is your paper?) is new to me, and it
looks like it touches on what I'm getting at - especially the discussion
surrounding equations (1) to (3) and figure 7. I need to spend some time
to read it through.
 
I was trying to see if by examining the equation that defines the
penalty algorithm, one could come up with a parameter set(s) that would
make RFD behave 'better'. By that I mean, suppress early into a sequence
of flaps, but unsuppress fairly soon after the sequence had passed
thereby preventing the long suppressions that are detrimental to
convergence. It is very early days on this work, but it looks like some
approximate equations that connect the configurable parameters to
flapping characteristics might be derivable, which would then point the
way to how to configure the parameters. For example, figure 7 in your
paper is quite interesting because it looks like work I was doing on an
approximate equation linking the time-to-half amplitude to suppression
threshold, flapping penalty and flapping frequency to get suppression to
occur in 3 flaps. This equation 'might be':
 
Suppression threshold = n * Flap penalty, where n >= 1 and,
n = 1 + exp(ln(1/2)*tf / thalf) + sqr(exp(ln(1/2)*tf / thalf))
where, thalf is the configurable time-to-half amplitude
           tf is the flapping frequency.
{I hope I didn't leave out any brackets when I transcribed this}
 
I have said 'might be' instead of 'is' because extensive verification
with BGP simulations and testing against actual flapping data is still
not done. As well, it also seems possible to develop other simple,
approximate equations linking other RFD parameters to flapping
charateristics. I can't say this is the last word on the subject yet,
but it looks possible to give RFD 'better' damping characteristics
through different parameters, but, to repeat myself, simulation and use
in the saddle is still very much required.
 
I look forward to reading your paper. 
 
Cheers,
Jim.

________________________________

From: K. Sriram [mailto:[email-masked]] 
Sent: Tuesday, June 26, 2007 12:53 PM
To: LOWE Jim; [email-masked]
Subject: Re: [RRG] Route Flap Damping parameters

Jim:

http://www.ensc.sfu.ca/~ljilja/papers/spects2005_steve.pdf
http://www.eecs.umich.edu/~zmao/Papers/sig02.pdf
http://www.antd.nist.gov/~ksriram/BGP_Security_Sriram_IEEE_JSAC.pdf 
(The third one includes an analytical sensitivity study w.r.t RFD
parameters;
comparing parameter values used by two different vendors; however, the
study
primarily reports simulation results of BGP vulnerability to attacks on
BGP sessions,
including aggravating influence due to RFD.)

Sriram

	Hello,
	 
	I have been following the discussion about BGP path hunting
('[RRG] BGP path hunting, MRAI timer and Path Length Damping') on this
list with some interest. With Route Flap Damping (RFD) being a possible
factor in the observed behavior, I had some questions about determining
values for its configurable parameters (Suppression threshold, Reuse
threshold, Time-to-half amplitude, and Maximum suppression time). 
	 
	I understand that prior to the recommendation made in RIPE-378
to not use RFD, RIPE-229 made recommendations about configurable
parameter settings. In reading RIPE-229, it seems the recommendations
were not strongly based on observations of actual dynamics (although I
could be dead wrong on this since I'm not familiar with all the work
that lead to the creation of RIPE-229). As well, from reading a
selection of papers on the subject of RFD preventing timely convergence,
there doesn't seem to be an analysis of what might happen if RFD
parameter sets other than the common defaults were applied, nor does
there appear to be a history of literature on this subject. My reading
in this area has been by no means exhaustive, so my questions are: has
there been any work done on determining what the impact of other sets of
RFD parameters might be; how have (or might) such sets be chosen; have
the dynamical properties of the RFD algorithm been worked out - with a
view towards assessing whether they would even be potentially capable of
improving observed dynamics? I have been thinking about these areas, but
wasn't sure if it had all been done before and these were dumb
questions.
	 
	Cheers,
	Jim.

K. Sriram, Ph.D.

---

From: "Medhi, Deep" <[email-masked]>
Date: Tue, 26 Jun 2007 15:26:57 -0500

Hi JIm,
 
   RFC2439 talks about the originally idea of RFD. However, the steps
aren't easy to follow, always. So, I derived the formula, which is
really the solution of a differential equation with exponential decay,
so that I can emulate the idea. The formulat is shown in LaTeX math mode
below (it looks ugly in this form, much nicer/simpler in actual
display:-)
 
\begin{equation}
   \begin{array}{lll}
   P(t) &= &\left\{ \begin{array}{ll}
              0, &  t < t_0 \\
              P_{{\scriptsize\textrm{inc}}}, & t = t_0 \\\
   P(t_i)\ \times\ \e^{^{   \frac{- ( t - t_i) \log 2}{H}}}, &  t > t_0
      \end{array} \right. \\
      \\
  P(t_i) &= &    P(t_i) + P_{{\scriptsize\textrm{inc}}} \qquad \quad
i=1, 2, ... .
  \end{array}
\end{equation}
 
where $H$ is the half-life quantity, penalty amount per flap is
$P_{inc}$, and route flap occurs at t_0, t_1, t_2, ...
You can play with supress limit and reuse limit. 

This is described in detail in Section 8.9 of  
 
D. Medhi and K. Ramasamy, Network Routing: Algorithms, Protocols, and
Architectures, Morgan Kaufmann Publishers, 2007,
 
For comparative purpose, I plotted for a couple of different values of
flaps and max-flaps in a figure, also included in Section 8.9. I wrote
an awk code to generate data for the plots. If you want my awk code,
please let me know. By playing with it, I believe you might be able to
try out your idea, unless I missed something.
 
Thanks.

    -- Deep
    http://www.csee.umkc.edu/~dmedhi

	From: [email-masked] [mailto:[email-masked]] On Behalf Of
LOWE Jim
	Sent: Tuesday, June 26, 2007 2:43 PM
	To: K. Sriram; [email-masked]
	Subject: RE: [RRG] Route Flap Damping parameters

	Hi Sriram,
	 
	Thank-you for pointing out these references. I have read the
first two, but the third one (which I assume is your paper?) is new to
me, and it looks like it touches on what I'm getting at - especially the
discussion surrounding equations (1) to (3) and figure 7. I need to
spend some time to read it through.
	 
	I was trying to see if by examining the equation that defines
the penalty algorithm, one could come up with a parameter set(s) that
would make RD behave 'better'. By that I mean, suppress early into a
sequence of flaps, but unsuppress fairly soon after the sequence had
passed thereby preventing the long suppressions that are detrimental to
convergence. It is very early days on this work, but it looks like some
approximate equations that connect the configurable parameters to
flapping characteristics might be derivable, which would then point the
way to how to configure the parameters. For example, figure 7 in your
paper is quite interesting because it looks like work I was doing on an
approximate equation linking the time-to-half amplitude to suppression
threshold, flapping penalty and flapping frequency to get suppression to
occur in 3 flaps. This equation 'might be':

	I have said 'might be' instead of 'is' because extensive
verification with BGP simulations and testing against actual flapping
data is still not done. As well, it also seems possible to develop other
simple, approximate equations linking other RFD parameters to flapping
charateristics. I can't say this is the last word on the subject yet,
but it looks possible to give RFD 'better' damping characteristics
through different parameters, but, to repeat myself, simulation and use
in the saddle is still very much required.

	Cheers,
	Jim.

	Jim:
	
	I am not sure these papers provide all the insights you are
looking for,
	but they generally address some of the questions you've posed.  

http://www.antd.nist.gov/~ksriram/BGP_Security_Sriram_IEEE_JSAC.pdf 
	(The third one includes an analytical sensitivity study w.r.t
RFD parameters;
	comparing parameter values used by two different vendors;
however, the study
	primarily reports simulation results of BGP vulnerability to
attacks on BGP sessions,
	including aggravating influence due to RFD.)
	
	Sriram

		Hello,
		 
		I have been following the discussion about BGP path
hunting ('[RRG] BGP path hunting, MRAI timer and Path Length Damping')
on this list with some interest. With Route Flap Damping (RFD) being a
possible factor in the observed behavior, I had some questions about
determining values for its configurable parameters (Suppression
threshold, Reuse threshold, Time-to-half amplitude, and Maximum
suppression time). 
		 
		I understand that prior to the recommendation made in
RIPE-378 to not use RFD, RIPE-229 made recommendations about
configurable parameter settings. In reading RIPE-229, it seems the
recommendations were not strongly based on observations of actual
dynamics (although I could be dead wrong on this since I'm not familiar
with all the work that lead to the creation of RIPE-229). As well, from
reading a selection of papers on the subject of RFD preventing timely
convergence, there doesn't seem to be an analysis of what might happen
if RFD parameter sets other than the common defaults were applied, nor
does there appear to be a history of literature on this subject. My
reading in this area has been by no means exhaustive, so my questions
are: has there been any work done on determining what the impact of
other sets of RFD parameters might be; how have (or might) such sets be
chosen; have the dynamical properties of the RFD algorithm been worked
out - with a view towards assessing whether they would even be
potentially capable of improving observed dynamics? I have been thinking
about these areas, but wasn't sure if it had all been done before and
these were dumb questions.
		 
		Cheers,
		Jim.

	K. Sriram, Ph.D.

---

From: "LOWE Jim" <[email-masked]>
Date: Wed, 27 Jun 2007 07:29:54 -0500

Thanks for the information Deep. I have developed a model of the RFD
algorithm, and have been using it to test some equations derived from
them which characterize some of the time-response properties of the
algorithm. These equations can then be used to set the RFD parameters to
achieve certain response properties. This takes the analysis one step
above just trying different parameter sets in a simulation. As a first
cut, the flap profiles presented in Bush and Griffin's presentation
package: http://www.nanog.org/mtg-0210/ppt/flap.pdf
<http://www.nanog.org/mtg-0210/ppt/flap.pdf>  were plugged into the
model to see if the damping response could be improved. The early
results look promising, but the analysis needs to be taken to the next
step and these need to be tested in a BGP simulation. 
 
Cheers,
Jim.

From: Medhi, Deep [mailto:[email-masked]] 
Sent: Tuesday, June 26, 2007 4:27 PM
To: LOWE Jim; K. Sriram; [email-masked]
Subject: RE: [RRG] Route Flap Damping parameters

Hi JIm,

\begin{equation}
   \begin{array}{lll}

 

Thanks.

    -- Deep

	Hi Sriram,

	 

	 
	Cheers,
	Jim.

	Jim:

	
	
	Sriram

		Hello,

		 
		Cheers,
		Jim.

	K. Sriram, Ph.D.