[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [RRG] Route Flap Damping parameters
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 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:DMedhi@umkc.edu]
Sent: Tuesday, June 26, 2007 4:27
PM
To: LOWE Jim; K. Sriram; rrg@psg.com
Subject: 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
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.
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/