Subject: Route Flap Damping - more reader comments

From: Curtis Villamizar <[email-masked]>
Date: Wed, 06 May 1998 21:38:15 -0400

Jayesh,

Thanks for the comments.

Curtis

------- Forwarded Message

To: [email-masked] (Jayesh Bhatt)
cc: [email-masked]
Reply-To: [email-masked]
Subject: Re: Route Flap Damping question ... 
Date: Wed, 06 May 1998 18:19:03 -0400
From: Curtis Villamizar <[email-masked]>

In message <[email-masked]>, Jayesh Bhatt 
writes:
> Hi,
> 
> I was going through the Route Flap Damping draft:
>     draft-ietf-idr-route-damp-02.txt
> and was wondering if I could ask you some questions 
> to understand it better since I think it's a really clever
> way to manage the penalties without having
> to walk all the BGP routes and adjusting penalties.

Sorry for the delay in answering this.  I've been busy with other
science projects.  :-)

> I was trying to understand some of the equations to
> calculate decay-arrays and reuse-lists.  I understand
> the calculations in concept [if that's possible :-)]
> but I had some questions on some of the equations
> themselves.

We've just found out a few are wrong.  Lets see if you've hit on yet
another error or just lack of clarity.

> I  - When you say "log" you mean the natural log correct??

log is natural log and exp is e raised to some power.

> II - On page 18 of the draft, I understand that the decay-factor per
>      decay timer "delta-t" is 
> 
>      decay[1] = exp( (1/ (decay-rate/delat-t)) * log(1/2) )
> 
>      which reduces to:  [e**(ln(a)) = a  where ln is log base e] 
> 
>      (1/2)**( 1/(half-life/delta-t) )
> 
>      OR
> 
>      (1/2)**( delta-t/half-life)
>  
>      where ** means "to the power of"
> 
>      Is my understanding correct??

Yes.  This was decay[half-life/delat-t] = 1/2, which is the definition
of half life.

> III - On  page 18 and 19, section 4.6 - "Building the Reuse Index Array":
> 
>      max-ratio = min(    ceiling/reuse, 
>                          exp( (1/(half-life/reuse-array-time))*log(1/2) )    
> )
> 
>      ceiling = the max-value the figure-of-merit can reach
> 
>      reuse   = the value of figure-of-merit below which the route will be 
>                reuseable.
> 
>      half-life = time over which the figure-of-merit reduces to half.
> 
>      reuse-array-time = total time that reuse lists cover.
>                         i.e. if we have 1024 reuse lists and 
>                         reuse-time-granularity is 5 seconds, reuse-array-time
>  
>                         = 1024*5 = 5120.
> 
>     Is this correct???
> Or is 
>      reuse-array-time = the reuse-time-granularity = the time interval after
>                         which the reuse list will be looked up again to move 
>                         reuseable routes into reuseable lists. 

How observant.  Rob Coltun (or actually Sanjay) already pointed this
out.  I can see you are also going through the draft carefully.  The
short answer is the log(1/2) was supposed to be a log(2).

> IV 
> 
>               So the max-ratio is minumum of ceiling/reuse and
> 
>                (1/2)**( 1/(half-life/reuse-array-time) )
>               OR 
>                (1/2)**( reuse-array-time/half-life) )
> 
>     If I use the reuse-array-time to be the total time (e.g. 1024 above)
>     the max-ratio approaches 0 very quickly.
> 
>     If I use the reuse-array-time to be the time a single reuse list covers
>     (i.e. 5 seconds above), the max-ratio remains less than 1 approaching
>     1 very slowly. 

This is not right.  See 4.8.6 "Inserting into the Reuse Timer List"
and 4.8.7 "Handling Reuse Timer Events".  This describes how the reuse
data structures are used.  These are not decay arrays.

> V  Further in section 4.6 I am a little confused by the terminology:
> 
>   reuse-array-scale-factor, or simply the scale-factor is used to
>   determine which reuse-list to insert a route into correct? 
> 
>   This is either 0 or less than 1 from above if
> 
>    scale factor is = (max-ratio-1)/reuse-array-size
> 
>   Where did I go wrong??

max-ratio is usually a small number.  Take 3 for example.  If the
array has 32 elements, then scale-factor is 1/16.  See the message to
Rob that I will shortly forward for some clarification on this.  I'll
also try to make the I-D a bit more clear.  Rob got it and John
Scudder got it but it is true that the draft could be better here.

> VI Is reuse-array-size the number of entries per reuse list and is
>    reuse-index-array = the array which indexes into the reuse lists based
>    on current figure-of-merit?

The second equation in section 4.6 should use reuse-index-array-size
rather than reuse-array-size.  

You multiply the figure-of-merit by 1/scale-factor (it might have
helped to invert the definition).  You truncate and look up in
reuse-index-array and get an integer.  You use that integer to pick a
reuse-list.  reuse-index-array-size is the size of the
reuse-index-array.

The third equation is 4.6 is completely wrong.  I guess this just
proves I can't do algebra reliably.

> Thanks and sorry for the loooong mail.

Not so long considering that it seems you are going through this is
sufficient detail to implement it.  If so, that would make yours
implementation #5 AFAIK.  (Cisco, ISI, IENG, Fore, Bay).

> J
> 
> -- 
> -------------------------------------------------
> Jayesh Bhatt
> 600 Technology Park
> Mail Stop: 60-304
> Billerica, MA  01821
> Bay Networks                FAX    (508) 670-8760
> [email-masked]      Direct (508) 916-3566
> -------------------------------------------------

Again.  Sorry it took so long to respond.

Curtis

------- End of Forwarded Message