Subject: BGP Route Flap Damping -03-preview

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

The web pages were updated at:

  http://engr.ans.net/route-damp/

The BGP Route Flap Damping is now available in -03-preview flavor.

The following summarizes the changes (from the web page):

    The current (-03-preview) draft in this directory is a preview of the
    draft about to be resubmitted to the Internet Draft editors.  This
    preview corrects a few errors noted in the prior version in the
    additional implementation details added after the first two
    implementations were completed.  The errors were noted by individuals
    during the process of writing what will be the third, fourth, and
    fifth independent implementations of the draft.

And the following was added to the acknowledgements.

    Thanks to Rob Coltun (Fore Systems), John Scudder (IENG) and Jayesh
    Bhatt (Bay Networks) for pointing out errors in the math uncovered
    during coding of more recent implementations. These errors appeared in
    the details of the implementation suggestion sections written after
    the first two implementations were completed.

If you **really** want to know what changed and just **love** reading
unified diffs of latex source, I've included diffs below.  :-)

Curtis

btw- If there are no further comments I'll drop the -preview and send
this off to the internet-drafts editor (IETF secretariate).  The WG
chairs then have the task of deciding how to proceed given that this
has already reached the IESG.  Start over from the WG last call?

Index: route-damp.rfc
===================================================================
RCS file: /usr/local/CVS-routing-dev/doc/ietf/route-dampen/route-damp.rfc,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- route-damp.rfc	1998/02/13 19:51:50	1.7
+++ route-damp.rfc	1998/05/07 01:17:24	1.8
@@ -9,7 +9,7 @@
 \author{Ramesh Govindan}
 \address{ISI}
 \footer{Villamizar, Chandra, Govindan}
-\filename{draft-ietf-idr-route-damp-02}
+\filename{draft-ietf-idr-route-damp-03-preview}
 \begin{document}
 \begin{alltt}
 \bibliographystyle{plain}
@@ -493,9 +493,10 @@
 reuse index array is needed for each decay rate in use.  The reuse
 index array is used to estimate which reuse list to place a route when
 it is suppressed.  Proper placement avoids the need to periodically
-evaluate decay to determine if a route can be reused.  Using the reuse
-index array avoids the need to compute a logarithm to determine
-placement.  One additional system wide parameter can be introduced.
+evaluate decay to determine if a route can be reused or when storage
+can be recovered.  Using the reuse index array avoids the need to
+compute a logarithm to determine placement.  One additional system
+wide parameter can be introduced.
 
 \begin{description}
 \resync
@@ -542,12 +543,12 @@
 \label{flap-rates}
 \end{figure}
 
-From either maximum hold time value (\mathortext{$ Tmax _ {ok} $ or $
-Tmax _ {ng} $}{Tmax-ok or Tmax-ng}), 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.
+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.
 
 \begin{figure}
 \unitlength=0.8in
@@ -609,6 +610,15 @@
 used to arrange suppressed routes according to the time remaining
 until they can be reused.
 
+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.
+
 If multiple sets of configuration parameters are allowed per route,
 there is a need for some means of associating more than one figure of
 merit and set of parameters with each route.  Building a linked list
@@ -668,13 +678,13 @@
   \mathortext{( $ Size _ D $ )}{(decay-array-size)}
 \item
   decay array
-  \mathortext{( $ D [ \  ] $ )}{(decay)}
+  \mathortext{( $ D [ \  ] $ )}{(decay[])}
 \item
   reuse index array size
   \mathortext{( $ Size _ {R_{index}} $ )}{(reuse-index-array-size)}
 \item
   reuse index array
-  \mathortext{( $ R _ {index} [ \  ] $ )}{(reuse-index-array)}
+  \mathortext{( $ R _ {index} [ \  ] $ )}{(reuse-index-array[])}
 \end{itemize}
 
 For each decay rate specified, an array will be used to store the
@@ -792,6 +802,22 @@
 number of values that will be used repeatedly and retain these to
 speed later computations that will be required frequently.
 
+Scaling is usually dependent on the highest value that
+\mathortext{$\epsilon$}{figure-of-merit} can attain, referred to here
+as the ceiling\mathortext{ ($\epsilon_{ceiling}$)}{}.  The real number
+value of the ceiling will typically be determined by the following
+equation.
+
+\mathortext{%
+  \begin{displaymath}
+  \epsilon_{ceiling} = \epsilon_{cut} e ^ {\frac{T_{hold}}{\lambda} \log 2}
+  \end{displaymath}
+}{\begin{quotation}
+  \resync
+  ceiling = reuse * (exp(T-hold/decay-rate) * log(2))
+\end{quotation}
+}
+
 The methods of scaled integer arithmetic are not described in detail
 here.  The methods of determining the real values are given.
 Translation into scaled integer values and the details of scaled
@@ -808,7 +834,7 @@
   the scaled integers to be multiplied by the scaled decay value and
   then shifted down.  Implementations may prefer to use real numbers
   or may use any integer scaling deemed appropriate for their
-  architecture.
+  architecture.  
 \item{penalty value and thresholds (as proportional scaled integers)} \par
   The figure of merit penalty for one route withdrawal and the cutoff
   values must be scaled according to the above scaling factor.
@@ -898,13 +924,13 @@
   ratio _ {max} = min( \frac{\epsilon _ {ceiling}}{ \epsilon _ {reuse} } ,
 		       e ^ { \frac{1}
 			     { \left( \frac{\lambda}{T_{reuse}} \right) } }
-		       \log { \frac{1}{2} } )
+		       \log {2} )
   \end{displaymath}
   }{%
   \begin{quotation}
     \resync
     max-ratio = min(ceiling/reuse,
-                    exp((1 / (half-life/reuse-array-time)) * log(1/2)))
+                    exp((1 / (half-life/reuse-array-time)) * log(2)))
   \end{quotation}
   }
 \item{reuse array scale factor
@@ -915,16 +941,16 @@
   used.
   \mathortext{%
   \begin{displaymath}
-  scale _ {reuse} = \frac{{ ratio _ {max} } - 1 }{ Size _ R }
+  scale _ {reuse} = \frac{ Size _ {R_{index}} }{{ ratio _ {max} } - 1 }
   \end{displaymath}
   }{%
   \begin{quotation}
     \resync
-    scale-factor = (max-ratio - 1) / reuse-array-size
+    scale-factor = reuse-index-array-size / (max-ratio - 1)
   \end{quotation}
   }
 \item{reuse index array
-  \mathortext{( $ R_{index} [] $ )}{(reuse)}
+  \mathortext{( $ R_{index} [\ ] $ )}{(reuse-index-array[])}
   } \par
   Each reuse index array entry should contain an index into the reuse list
   array pointing to one of the list heads.  This index should
@@ -934,15 +960,15 @@
   the the reuse array entry.
   \mathortext{%
   \begin{displaymath}
-  R_{index} [ i ] = integer \left( \log 
-    \frac{ \frac{1}{ { 1 + ( ( j + 1 ) (  { ratio_{max} } - 1 ) ) } }
-	  }{ \Delta { t _ {reuse} } } \right)
+  R_{index} [ j ] = integer \left( \frac{\lambda}{\Delta{t_{reuse}}}
+    \log {\left( frac{1}{\epsilon_{reuse}(1+\frac{j}{scale_{reuse}})} \right)}
+    \log {\frac{1}{2}} \right)
   \end{displaymath}
   }{%
   \begin{quotation}
     \resync
-    reuse-array[j] = integer(log(1 / (1 + ((j+1) * (max-ratio-1))))
-                             / reuse-time-granularity)
+    reuse-index-array[j] = integer((decay-rate / reuse-time-granularity)
+        * log(1/(reuse * (1 + (j / scale-factor)))) / log(1/2))
   \end{quotation}
   }
 \end{description}
@@ -950,10 +976,14 @@
 To determine which reuse queue to place a route which is being
 suppressed, the following procedure is used.  Divide the current
 figure of merit by the cutoff.  Subtract one.  Multiply by the scale
-factor.  This is the array index.  If it is off the end of the array
-use the last queue otherwise look in the array and pick the number of
-the queue from the array at that index.  This is quite fast and
-well worth the setup and storage required.
+factor.  This is the index into the reuse index array \mathortext{( $
+R_{index} [\ ] $ )}{(reuse-index-array[])}.  The value fetched from
+the reuse index array \mathortext{( $R_{index} [\ ] $
+)}{(reuse-index-array[])} is an index into the array of reuse lists
+\mathortext{( $R[\ ]$ )}{(reuse-array[])}.  If this index is off the
+end of the array use the last queue otherwise look in the array and
+pick the number of the queue from the array at that index.  This is
+quite fast and well worth the setup and storage required.
 
 \subsection{A Sample Configuration}
 
@@ -1556,6 +1586,12 @@
 comments and implementation feedback were shared by many individuals
 on the IETF IDR WG and the RIPE Routing Work Group and in NANOG and
 IEPG.
+
+Thanks also to Rob Coltun (Fore Systems), John Scudder (IENG) and
+Jayesh Bhatt (Bay Networks) for pointing out errors in the math
+uncovered during coding of more recent implementations.  These errors
+appeared in the details of the implementation suggestion sections
+written after the first two implementations were completed.
 
 % References

---

From: Yakov Rekhter <[email-masked]>
Date: Thu, 07 May 98 06:01:32 PDT

Curtis,

> this off to the internet-drafts editor (IETF secretariate).  The WG

Yes, please.

> has already reached the IESG.  Start over from the WG last call?

Yes, as soon as the new internet draft will become available.

Yakov.