[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: [RRG] Route Flap Damping parameters



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: owner-rrg@psg.com [mailto:owner-rrg@psg.com] On Behalf Of LOWE Jim
Sent: Tuesday, June 26, 2007 2:43 PM
To: K. Sriram; rrg@psg.com
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':
 
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:ksriram@nist.gov]
Sent: Tuesday, June 26, 2007 12:53 PM
To: LOWE Jim; rrg@psg.com
Subject: Re: [RRG] Route Flap Damping parameters

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: ksriram@nist.gov
Web:  http://www.antd.nist.gov/~ksriram/