Subject: BGP Route Flap Damping - reader comments

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

Rob, John,

Thanks for the comments.

Curtis

------- Forwarded Message

To: Rob Coltun <[email-masked]>
cc: [email-masked], John Scudder <[email-masked]>
Reply-To: [email-masked]
Subject: Re: more comments on dampening... 
Date: Wed, 06 May 1998 17:47:35 -0400
From: Curtis Villamizar <[email-masked]>

In message <[email-masked]>, Rob Coltun write
s:
> ...from sanjay
> 
> In addition to the last equation in section 4.6 pointed out here
> (also had it marked as an error) :

John point this section out.  According to John the text was OK but
the equations were wrong.  I'll address this below.

Keep in mind that this section was written after the first two
implementations so it is not surprising that the 3rd and 4th stumbled
on the error.

> There is another one that I think might be an error .
> Last line on page 8 (section 4.3) :
>   From either Tmaxok or Tmax-ng a ratio of cutoff to a celing
>   can be determined.
>   
> I think it should be T-hold rather than T-max. And penalty ceiling
> should be related to penalty-reuse rather than penalty-cutoff.

I changed that paragraph to read:

    From the maximum hold time value (\mathortext{$T_{hold}$}{T-hold}),
    a ratio of the cutoff to a ceiling can be determined.  An integer
    value for the ceiling can then be chosen such that overflow will not
    be a problem and all other values can be scaled accordingly.  If both
    cutoffs are specified or if multiple parameter sets are used the
    highest ceiling will be used.

Before this the text was saying hold time but had T-max in parens.
Good catch.  This error was probably there from the start.

> I think the equation to determine ceiling should be :
>   penalty-ceiling = (penalty-reuse) * (exp((T-hold/T) * log 2))
> 
>  (where log is natural-log).
>  T-hold, T and penalty-reuse are all configurable.
>  penalty-celing can therefore be determined from the above
>  equation. Basically this means that penlaty is being limited 
>  to penalty-ceiling so that it can decay to re-use value 
>  in some multiple of half life time.

I never actually gave an equation to compute the ceiling.  What you
have here is not quite right though (just variable name confusion
again).  You can get the ceiling by going backwards from the reuse
value (\epsilon_{reuse}), the max hold time (T_{hold}), and the decay
rate (\lambda).

In text it is:

  ceiling = reuse * 2 ^ (T-hold/decay-rate)

  ceiling = reuse * log(2) * exp(T-hold/decay-rate)

In math mode this is:

  \epsilon_{ceiling} = \epsilon_{cut} * \log 2 e ^ \frac{T_{hold}}{\lambda}

Doesn't the latex source clear things up nicely.  :-)

>  Another thing is that the spec talks about putting routes on
>  the re-use list based on how much time it will take for the
>  route's current penalty to decay to penalty-reuse. 
>  However when a route becomes re-usable we still have to track 
>  it's penalty till it reaches a value at which we can forget it
>  i.e. stop tracking it altogether. The route should be put onto
>  another timer-list (say penalty-remove-list) based on the time
>  it will take the penalty to decay enough so that we can stop
>  tracking it. Spec does not talk abt this. Might be more of an   
> implementation issue, but since they talk about re-use lists 
>  (which is also implementation issue) they can probably indicate 
>  this too.

I thought I had covered that but apparently not.  It is necessary to
clean up unused storage.  A second set of reuse arrays, maybe we
should call them recycle arrays, could be described.  Sometimes I
think it would have been easier to just provide code.

I added the following paragraph:

    A separate reuse list can be used to hold unreachable routes for the
    purpose of later recovering storage if they remain unreachable too
    long.  This might be more accurately described as a recycling list.
    The advantage this would provide is making free data structures
    available as soon as possible.  Alternately, the data structures can
    simply be placed on a queue and the storage recovered when the route
    hits the front of the queue and if storage is needed.  The latter is
    less optimal but simple.

That ought to cover recycling adequately.  At least I hope so because
adding a recycling array where the math is identical to the reuse
array would be a substantial pain and probably would not add to
clarity.

Back to section 4.6.  The best thing at this point is to try out the
math on an example, see if it works, fix if necessary, and check the
text to see if it matches.

The first equation is:

    max-ratio = min(ceiling/reuse,
	exp((1 / (half-life/reuse-array-time)) * log(1/2)))

Looks like this should be log(2).

If:

	ceiling = 5
	reuse = 1.5
	half-life = 30*60
	reuse-array-time = 300*60

then:

	max-ratio = min(5/1.5, exp((300/30) * 0.69315))
	max-ratio = min(3.3333, 1024)

If reuse-array-time is small, for example 45*60:

	max-ratio = min(3.3333, 2.8284)

This seems to work.

Next equation is:

    scale-factor = (max-ratio - 1) / reuse-array-size

If reuse-array-size = 32 (and we're back to 300):

    scale-factor = (3.33 - 1) / 32 = 0.072813

Next and final is:

    reuse-array[j] = integer(log(1 / (1 + ((j+1) * (max-ratio-1))))
	/ reuse-time-granularity)

Lets use reuse-time-granularity of 5.

This is all wrong.

We want the property:

  reuse-array[j] = delay-until-reuse / reuse-time-granularity

  j = ((X / reuse) - 1) / scale-factor
  X = reuse * (1 + (j * scale-factor))

  D[1] = exp((1 / (decay-rate/delta-t)) * log (1/2))
  D[i] = D[1] ** i

  D[i] = exp(i * ((1 / (decay-rate/delta-t)) * log (1/2)))

  i = T/delta-t
  X = 1/D[i]

  D[i] = 1/X

  reuse-array[j] = T / reuse-time-granularity

Need to solve for T in:

  1/X = exp((T/delta-t) * ((1 / (decay-rate/delta-t)) * log (1/2)))

  T = decay-rate * log(1/X) / log(1/2)

  T = decay-rate * log(1/(reuse * (1 + (j * scale-factor)))) / log(1/2)

Try it:

  reuse-array[j] = (30*60)/(5*60)*log(1/(1.5*(1+(j*0.072813))))/log(1/2)

	j	reuse-array[j]	X
	 0	 3.5	 3	1.5
	 1	 4.1	 4	1.6
	 2	 4.7	 4	1.7
	 3	 5.2	 5	1.8
	 4	 5.7	 5	1.9
	 5	 6.2	 6	2.0
	 6	 6.6	 6	2.2
	 7	 7.1	 7	2.3
	 8	 7.5	 7	2.4
	 9	 7.8	 7	2.5
	10	 8.2	 8	2.6
	12	 8.9	 8	2.8
	14	 9.6	 9	3.0
	16	10.2	10	3.2
	20	11.3	11	3.7
	24	12.3	12	4.1
	28	13.1	13	4.6
	32	13.9	13	5.0

This tells us that the array need only be 16 long for a half life of
30 minutes and evaluation of the reuse array every 5 minutes.  When
using the array take X, or epsilon elsewhere, multiply by
1/scale-factor to get J, truncate, look up in reuse-array, get an
integer index K, put the structure in the Kth list.

Now to get that in the draft.

Curtis

------- End of Forwarded Message