RFC 2439 - BGP Route Flap Damping 日本語訳

原文URL : https://datatracker.ietf.org/doc/html/rfc2439
タイトル : RFC 2439 - BGPルートフラップダンピング
翻訳編集 : 自動生成

[要約] RFC 2439は、BGPルートフラップダンピングに関するガイドラインです。その目的は、ネットワークの安定性を向上させ、ルートフラップによるネットワークの振動を抑制することです。

Network Working Group                                       C. Villamizar
Request for Comments: 2439                                            ANS
Category: Standards Track                                      R. Chandra
                                                                    Cisco
                                                              R. Govindan
                                                                      ISI
                                                            November 1998

BGP Route Flap Damping

BGPルートフラップダンピング

Status of this Memo

本文書の状態

This document specifies an Internet standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited.

このドキュメントは、インターネットコミュニティのインターネット標準トラックプロトコルを指定し、改善のための議論と提案を要求します。このプロトコルの標準化状態とステータスについては、「インターネット公式プロトコル標準」（STD 1）の最新版を参照してください。このメモの配布は無制限です。

著作権表示

Abstract

概要

A usage of the BGP routing protocol is described which is capable of reducing the routing traffic passed on to routing peers and therefore the load on these peers without adversely affecting route convergence time for relatively stable routes. This technique has been implemented in commercial products supporting BGP. The technique is also applicable to IDRP.

ルーティングピアに渡されるルーティングトラフィックを削減し、比較的安定したルートのルート収束時間に悪影響を与えることなくこれらのピアの負荷を軽減できるBGPルーティングプロトコルの使用法について説明します。この手法は、BGPをサポートする商用製品に実装されています。この手法はIDRPにも適用できます。

The overall goals are:

全体的な目標は次のとおりです。

o to provide a mechanism capable of reducing router processing load caused by instability

o 不安定性によるルーターの処理負荷を軽減できるメカニズムを提供する

o in doing so prevent sustained routing oscillations

o そうすることで、持続的なルーティング振動を防ぎます

o to do so without sacrificing route convergence time for generally well behaved routes.

o 一般的に適切に動作するルートのルート収束時間を犠牲にすることなくこれを行うため。

This must be accomplished keeping other goals of BGP in mind:

これは、BGPの他の目標を念頭に置いて達成する必要があります。

o pack changes into a small number of updates

o 変更を少数の更新にパックする

o preserve consistent routing o minimal addition space and computational overhead

o一貫したルーティングを維持o最小限の追加スペースと計算オーバーヘッド

An excessive rate of update to the advertised reachability of a subset of Internet prefixes has been widespread in the Internet. This observation was made in the early 1990s by many people involved in Internet operations and remains the case. These excessive updates are not necessarily periodic so route oscillation would be a misleading term. The informal term used to describe this effect is "route flap". The techniques described here are now widely deployed and are commonly referred to as "route flap damping".

インターネットプレフィックスのサブセットのアドバタイズされた到達可能性に対する過度の更新率がインターネットで広まっています。この観察は、1990年代初頭にインターネット運用に携わる多くの人々によって行われたものであり、現在もそうです。これらの過剰な更新は必ずしも定期的ではないため、ルートの振動は誤解を招く用語になるでしょう。この影響を説明するために使用される非公式な用語は「ルートフラップ」です。ここで説明する技術は現在広く展開されており、一般に「ルートフラップダンピング」と呼ばれています。

1 Overview

1。概要

To maintain scalability of a routed internet, it is necessary to reduce the amount of change in routing state propagated by BGP in order to limit processing requirements. The primary contributors of processing load resulting from BGP updates are the BGP decision process and adding and removing forwarding entries.

ルーティングされたインターネットのスケーラビリティを維持するには、処理要件を制限するために、BGPによって伝達されるルーティング状態の変更量を減らす必要があります。 BGP更新による処理負荷の主な原因は、BGP決定プロセスと、転送エントリの追加と削除です。

Consider the following example. A widely deployed BGP implementation may tend to fail due to high routing update volume. For example, it may be unable to maintain it's BGP or IGP sessions if sufficiently loaded. The failure of one router can further contribute to the load on other routers. This additional load may cause failures in other instances of the same implementation or other implementations with a similar weakness. In the worst case, a stable oscillation could result. Such worse cases have already been observed in practice.

次の例を考えてみましょう。広く展開されているBGP実装は、ルーティングアップデートの量が多いために失敗する傾向があります。たとえば、十分にロードされていると、BGPまたはIGPセッションを維持できない場合があります。 1つのルーターに障害が発生すると、他のルーターの負荷がさらに増大する可能性があります。この追加の負荷により、同じ実装の他のインスタンスまたは同様の弱点を持つ他の実装で障害が発生する可能性があります。最悪の場合、安定した発振が得られます。そのような最悪のケースは実際にすでに観察されています。

A BGP implementation must be prepared for a large volume of routing traffic. A BGP implementation cannot rely upon the sender to sufficiently shield it from route instabilities. The guidelines here are designed to prevent sustained oscillations, but do not eliminate the need for robust and efficient implementations. The mechanisms described here allow routing instability to be contained at an AS border router bordering the instability.

BGP実装は、大量のルーティングトラフィックに対応できるように準備する必要があります。 BGPの実装では、ルートの不安定性からBGPを十分に保護するために送信者に依存することはできません。ここでのガイドラインは、持続的な振動を防止するように設計されていますが、堅牢で効率的な実装の必要性を排除するものではありません。ここで説明するメカニズムにより、ルーティングの不安定性を、その不安定性に隣接するAS境界ルーターに含めることができます。

Even where BGP implementations are highly robust, the performance of the routing process is limited. Limiting the propagation of unnecessary change then becomes an issue of maintaining reasonable route change convergence time as a routing topology grows.

BGP実装が非常に堅牢である場合でも、ルーティングプロセスのパフォーマンスは制限されます。不要な変更の伝播を制限することは、ルーティングトポロジが大きくなるにつれて、適切なルート変更の収束時間を維持するという問題になります。

2 Methods of Limiting Route Advertisement

2ルートアドバタイズメントを制限する方法

Two methods of controlling the frequency of route advertisement are described here. The first involves fixed timers. The fixed timer technique has no space overhead per route but has the disadvantage of slowing route convergence for the normal case where a route does not have a history of instability. The second method overcomes this limitation at the expense of maintaining some additional space overhead. The additional overhead includes a small amount of state per route and a very small processing overhead.

ここでは、ルートアドバタイズメントの頻度を制御する2つの方法について説明します。 1つ目は、固定タイマーに関するものです。固定タイマー手法には、ルートごとのスペースオーバーヘッドはありませんが、ルートに不安定性の履歴がない通常のケースでは、ルートの収束が遅くなるという欠点があります。 2番目の方法は、追加のスペースオーバーヘッドをいくらか維持する代わりに、この制限を克服します。追加のオーバーヘッドには、ルートごとの少量の状態と非常に小さな処理オーバーヘッドが含まれます。

It is possible and desirable to combine both techniques. In practice, fixed timers have been set to very short time intervals and have proven useful to pack routes into a smaller number of updates when routes arrive in separate updates. The BGP protocol refers to this as packing Network Layer Reachability Information (NLRI) [5].

両方の手法を組み合わせることが可能であり、望ましいです。実際には、固定タイマーは非常に短い時間間隔に設定されており、ルートが個別の更新で到着したときに、ルートを少数の更新にパックするのに役立つことが実証されています。 BGPプロトコルは、これをネットワーク層到達可能性情報（NLRI）のパッキングと呼びます[5]。

Seldom are fixed timers set to the tens of minutes to hours that would be necessary to actually damp route flap. To do so would produce the undesirable effect of severely limiting routing convergence.

ルートフラップを実際に減衰させるために必要となる、数十分から数時間に設定された固定タイマーはめったにありません。これを行うと、ルーティングの収束を厳しく制限するという望ましくない影響が生じます。

2.1 Existing Fixed Timer Recommendations

2.1 既存の固定タイマーの推奨事項

BGP-3 does not make specific recommendations in this area [1]. The short section entitled "Frequency of Route Selection" simply recommends that something be done and makes broad statements regarding certain properties that are desirable or undesirable.

BGP-3は、この領域で特定の推奨を行いません[1]。「ルート選択の頻度」と題された短いセクションは、単に何かを行うことを推奨し、望ましいまたは望ましくない特定の特性に関して幅広い声明を出します。

BGP4 retains the "Frequency of Route Advertisement" section and adds a "Frequency of Route Origination" section. BGP-4 describes a method of limiting route advertisement involving a fixed (configurable) MinRouteAdvertisementInterval timer and fixed MinASOriginationInterval timer [5]. The recommended timer values of MinRouteAdvertisementInterval is 30 seconds and MinASOriginationInterval is 15 seconds.

BGP4は、「ルートアドバタイズメントの頻度」セクションを保持し、「ルートオリジネーションの頻度」セクションを追加します。 BGP-4は、固定（構成可能）MinRouteAdvertisementIntervalタイマーと固定MinASOriginationIntervalタイマー[5]を含むルートアドバタイズメントを制限する方法を説明しています。 MinRouteAdvertisementIntervalの推奨タイマー値は30秒、MinASOriginationIntervalは15秒です。

2.2 Desirable Properties of Damping Algorithms

2.2 ダンピングアルゴリズムの望ましい特性

Before describing damping algorithms the objectives need to be clearly defined. Some key properties are examined to clarify the design rationale.

減衰アルゴリズムを説明する前に、目的を明確に定義する必要があります。いくつかの主要なプロパティは、設計の根拠を明確にするために調べられます。

The overall objective is to reduce the route update load without limiting convergence time for well behaved routes. To accomplish this, criteria must be defined for well behaved and poorly behaved routes. An algorithm must be defined which allows poorly behaved routes to be identified. Ideally, this measure would be a prediction of the future stability of a route.

全体的な目的は、正常に動作するルートの収束時間を制限することなく、ルート更新の負荷を減らすことです。これを実現するには、正常に動作するルートと正常に動作しないルートの基準を定義する必要があります。動作不良のルートを特定できるアルゴリズムを定義する必要があります。理想的には、この測定はルートの将来の安定性の予測になるでしょう。

Any delay in propagation of well behaved routes should be minimal. Some delay is tolerable to support better packing of updates. Delay of poorly behave routes should, if possible, be proportional to a measure of the expected future instability of the route. Delay in propagating an unstable route should cause the unstable route to be suppressed until there is some degree of confidence that the route has stabilized.

正常に動作するルートの伝播の遅延は最小限に抑える必要があります。更新のより良いパッキングをサポートするために、多少の遅延は許容できます。動作不良のルートの遅延は、可能であれば、ルートの予想される将来の不安定性の測定値に比例する必要があります。不安定なルートの伝播が遅れると、ルートが安定したというある程度の信頼ができるまで、不安定なルートが抑制されます。

If a large number of route changes are received in separate updates over some very short period of time and these updates have the potential to be combined into a single update then these should be packed as efficiently as possible before propagating further. Some small delay in propagating well behaved routes is tolerable and is necessary to allow better packing of updates.

非常に短期間に大量のルート変更が個別の更新で受信され、これらの更新が単一の更新に結合される可能性がある場合、これらをさらに伝達する前に、可能な限り効率的にパックする必要があります。正常に動作するルートの伝播に多少の遅延が許容され、更新をより適切にパッキングできるようにするために必要です。

Where routes are unstable, use and announcement of the routes should be suppressed rather than suppressing their removal. Where one route to a destination is stable, and another route to the same destination is somewhat unstable, if possible, the unstable route should be suppressed more aggressively than if there were no alternate path.

ルートが不安定な場合、ルートの削除を抑制するのではなく、ルートの使用とアナウンスを抑制する必要があります。宛先への1つのルートが安定していて、同じ宛先への別のルートがやや不安定である場合、可能であれば、不安定なルートは代替パスがない場合よりも積極的に抑制されるべきです。

Routing consistency within an AS is very important. Only very minimal delay of internal BGP (IBGP) should be done. Routing consistency across AS boundaries is also very important. It is highly undesirable to advertise a route that is different from the route that is being used, except for a very minimal time. It is more desirable to suppress the acceptance of a route (and therefore the use of that route in the IGP) rather than suppress only the redistribution.

AS内のルーティングの一貫性は非常に重要です。内部BGP（IBGP）の非常に最小限の遅延のみを実行する必要があります。 AS境界を越えたルーティングの一貫性も非常に重要です。非常に最小限の時間を除いて、使用されているルートとは異なるルートをアドバタイズすることは非常に望ましくありません。再配布だけを抑制するのではなく、ルートの受け入れを（したがって、IGPでのそのルートの使用を）抑制することがより望ましいです。

It is clearly not possible to accurately predict the future stability of a route. The recent history of stability is generally regarded as a good basis for estimating the likelihood of future stability. The criteria that is used to distinguish well behaved from poorly behaved routes is therefore based on the recent history of stability of the route. There is no simple quantitative expression of recent stability so a figure of merit must be defined. Some desirable characteristics of this figure of merit would be that the farther in the past that instability occurred, the less it's affect on the figure of merit and that the instability measure would be cumulative rather than reflecting only the most recent event.

ルートの将来の安定性を正確に予測することは明らかに不可能です。最近の安定の歴史は、一般的に将来の安定の可能性を推定するための良い基礎と見なされています。したがって、正常に動作するルートと正常に動作しないルートを区別するために使用される基準は、ルートの安定性に関する最近の履歴に基づいています。最近の安定性の単純な定量的表現はないため、性能指数を定義する必要があります。この性能指数のいくつかの望ましい特性は、過去に不安定性が発生したほど、性能指数への影響が少なくなり、不安定性の測定値が最新のイベントのみを反映するのではなく累積的であることです。

The algorithms should behave such that for routes which have a history of stability but make a few transitions, those transitions should be made quickly. If transitions continue, advertisement of the route should be suppressed. There should be some memory of prior instability. The degree to which prior instability is considered should be gradually reduced as long as the route remains announced and stable.

アルゴリズムは、安定性の履歴があるが、いくつかの遷移を行うルートの場合、それらの遷移が迅速に行われるように動作する必要があります。遷移が続く場合、ルートのアドバタイズを抑制する必要があります。以前の不安定性のいくつかのメモリがあるはずです。ルートがアナウンスされて安定している限り、以前の不安定性が考慮される程度は徐々に下げられるべきです。

2.3 Design Choices

2.3 デザインの選択

After routes have been accepted their readvertisement will be briefly suppressed to improve packing of updates. There may be a lengthy suppression of the acceptance of an external route. How long a route will be suppressed is based on a figure of merit that is expected to be correlated to the probability of future instability of a route. Routes with high figure of merit values will be suppressed. An exponential decay algorithm was chosen as the basis for reducing the figure of merit over time. These choices should be viewed as suggestions for implementation.

ルートが受け入れられた後、更新のパッキングを改善するために、それらのreadvertisementは一時的に抑制されます。外部ルートの受け入れが長く抑制される可能性があります。ルートが抑制される期間は、ルートの将来の不安定性の確率と相関すると予想される性能指数に基づいています。性能指数の値が高いルートは抑制されます。指数関数的減衰アルゴリズムは、時間の経過とともに性能指数を低減するための基礎として選択されました。これらの選択は、実装の提案と見なす必要があります。

An exponential decay function has the property that previous instability can be remembered for a fairly long time. The rate at which the instability figure of merit decays slows as time goes on. Exponential decay has the following property.

指数関数的減衰関数には、以前の不安定性をかなり長い間記憶することができるという特性があります。不安定な性能指数が減衰する速度は、時間が経過するにつれて遅くなります。指数関数的減衰には次の特性があります。

         f(f(figure-of-merit, t1), t2) = f(figure-of-merit, t1+t2)

This property allows the decay for a long period to be computed in a single operation regardless of the current value (figure-of-merit). As a performance optimization, the decay can be applied in fixed time increments. Given a desired decay half life, the decay for a single time increment can be computed ahead of time. The decay for multiple time increments is expressed below.

このプロパティを使用すると、現在の値（性能指数）に関係なく、1回の操作で長期間の減衰を計算できます。パフォーマンスの最適化として、減衰を一定の時間増分で適用できます。望ましい減衰半減期が与えられた場合、単一の時間増分の減衰を事前に計算できます。複数の時間増分の減衰は次のように表されます。

        f(figure-of-merit, n*t0) = f(figure-of-merit, t0)**n = K**n

The values of K ** n can be precomputed for a reasonable number of "n" and stored in an array. The value of "K" is always less than one. The array size can be bounded since the value quickly approaches zero. This makes the decay easy to compute using an array bound check, an array lookup and a single multiply regardless as to how much time has elapsed.

K ** nの値は、適切な数の「n」について事前に計算して、配列に格納できます。「K」の値は常に1未満です。値はすぐにゼロに近づくため、配列のサイズは制限されます。これにより、経過時間に関係なく、配列の境界チェック、配列のルックアップ、および単一の乗算を使用して、減衰を簡単に計算できます。

3 Limiting Route Advertisements using Fixed Timers

3固定タイマーを使用したルートアドバタイズの制限

This method of limiting route advertisements involves the use of fixed timers applied to the process of sending routes. It's primary purpose is to improve the packing of routes in BGP update messages. The delay in advertising a stable route should be bounded and minimal. The delay in advertising an unreachable need not be zero, but should also be bounded and should probably have a separate bound set less than or equal to the bound for a reachable advertisement.

ルートアドバタイズメントを制限するこの方法では、ルートの送信プロセスに適用される固定タイマーを使用します。その主な目的は、BGP更新メッセージのルートのパッキングを改善することです。安定したルートをアドバタイズする際の遅延は制限され、最小限でなければなりません。到達不能のアドバタイズの遅延はゼロである必要はありませんが、制限する必要があり、到達可能なアドバタイズの境界以下の別個の境界セットを設定する必要があります。

The BGP protocol defines the use of a Routing Information Base (RIB). Routes that need to be readvertised can be marked in the RIB or an external set of structures maintained, which references the RIB.

BGPプロトコルは、ルーティング情報ベース（RIB）の使用を定義します。再アドバタイズする必要があるルートは、RIBまたはRIBを参照する維持されている外部の構造セットでマークできます。

Periodically, a subset of the marked routes can be flushed. This is fairly straightforward and accomplishes the objectives. Computation for too simple an implementation may be order N squared. To avoid N squared performance, some form of data structure is needed to group routes with common attributes.

定期的に、マークされたルートのサブセットをフラッシュできます。これはかなり簡単で、目的を達成します。単純すぎる実装の計算は、Nの2乗の次数になる場合があります。 Nの2乗のパフォーマンスを回避するには、共通の属性を持つルートをグループ化するために、何らかの形式のデータ構造が必要です。

An implementation should pack updates efficiently, provide a minimum readvertisement delay, provide a bounds on the maximum readvertisement delay that would be experienced solely as a result of the algorithm used to provide a minimum delay, and must be computationally efficient in the presence of a very large number of candidates for readvertisement.

実装では、更新を効率的にパックし、最小のreadvertisement遅延を提供し、最小の遅延を提供するために使用されるアルゴリズムの結果としてのみ発生する最大のreadvertisement遅延の境界を提供し、再広告のための多数の候補者。

4 Stability Sensitive Suppression of Route Advertisement

4ルートアドバタイズメントの安定性に敏感な抑制

This method of limiting route advertisements uses a measure of route stability applied on a per route basis. This technique is applied when receiving updates from external peers only (EBGP). Applying this technique to IBGP learned routes or to advertisement to IBGP or EBGP peers after making a route selection can result in routing loops.

ルートアドバタイズメントを制限するこの方法では、ルートごとに適用されるルートの安定性の測定値を使用します。この手法は、外部ピアからのみ更新を受信するときに適用されます（EBGP）。この手法をIBGP学習ルートに適用したり、ルート選択を行った後にIBGPまたはEBGPピアにアドバタイズしたりすると、ルーティングループが発生する可能性があります。

A figure of merit based on a measure of instability is maintained on a per route basis. This figure of merit is used in the decision to suppress the use of the route. Routes with high figure of merit are suppressed. Each time a route is withdrawn, the figure of merit is incremented. While the route is not changing the figure of merit value is decayed exponentially with separate decay rates depending on whether the route is stable and reachable or has been stable and unreachable. The decay rate may be slower when the route is unreachable, or the stability figure of merit could remain fixed (not decay at all) while the route remains unreachable. Whether to decay unreachable routes at the same rate, a slower rate, or not at all is an implementation choice. Decaying at a slower rate is recommended.

不安定性の測定に基づく性能指数は、ルートごとに維持されます。この性能指数は、ルートの使用を抑制する決定に使用されます。性能指数の高いルートは抑制されます。ルートが撤回されるたびに、性能指数が増加します。ルートが変化していない間は、ルートが安定していて到達可能であるか、ルートが安定していて到達不可能であるかに応じて、性能指数の値は個別の減衰率で指数関数的に減衰します。ルートが到達不能である場合、減衰率は遅くなる可能性があります。または、ルートが到達不能のままである場合、安定性能指数は固定されたままである（まったく減衰しない）可能性があります。到達不可能なルートを同じレートで減衰するか、遅いレートで減衰するか、まったくしないかは、実装の選択です。遅い速度で減衰することをお勧めします。

A very efficient implementation is suggested in the following sections. The implementation only requires computation for the routes contained in an update, when an update is received or withdrawn (as opposed to the simplistic approach of periodically decaying each route). The suggested implementation involves only a small number of simple operations, and can be implemented using scaled integers.

次のセクションでは、非常に効率的な実装を提案します。実装では、更新を受信または撤回するときに、更新に含まれるルートの計算のみが必要です（各ルートを定期的に減衰させる単純なアプローチとは対照的）。推奨される実装は、少数の単純な操作のみを含み、スケーリングされた整数を使用して実装できます。

The behavior of unstable routes is fairly predictable. Severely flapping routes will often be advertised and withdrawn at regular time intervals corresponding to the timers of a particular protocol (the IGP or exterior protocol in use where the problem exists). Marginal circuits or mild congestion can result in a long term pattern of occasional brief route withdrawal or occasional brief connectivity.

不安定なルートの動作はかなり予測可能です。激しくフラッピングするルートは、特定のプロトコル（問題が存在する場所で使用されているIGPまたは外部プロトコル）のタイマーに対応する定期的な時間間隔でアドバタイズおよび撤回されることがよくあります。限界回路または穏やかな輻輳は、時折の短い経路の撤退または時折の短い接続の長期パターンをもたらす可能性があります。

4.1 Single vs. Multiple Configuration Parameter Sets

4.1 単一構成パラメーターセットと複数構成パラメーターセット

The behavior of the algorithm is modified by a number of configurable parameters. It is possible to configure separate sets of parameters designed to handle short term severe route flap and chronic milder route flap (a pattern of occasional drops over a long time period). The former would require a fast decay and low threshold (allowing a small number of consecutive flaps to cause a route to be suppressed, but allowing it to be reused after a relatively short period of stability). The latter would require a very slow decay and a higher threshold and might be appropriate for routes for which there was an alternate path of similar bandwidth.

アルゴリズムの動作は、いくつかの構成可能なパラメーターによって変更されます。短期の深刻なルートフラップと慢性のより穏やかなルートフラップ（長期間にわたる偶発的なドロップのパターン）を処理するように設計された個別のパラメータセットを設定することが可能です。前者は高速の減衰と低いしきい値を必要とします（少数の連続したフラップによってルートが抑制されるようにしますが、比較的短い期間の後に再利用できます）。後者は、非常に遅い減衰とより高いしきい値を必要とし、同様の帯域幅の代替パスが存在するルートに適している可能性があります。

It may also be desirable to configure different thresholds for routes with roughly equivalent alternate paths than for routes where the alternate paths have a lower bandwidth or tend to be congested. This can be solved by associating a different set of parameters with different ranges of preference values. Parameter selection could be based on BGP LOCAL_PREF.

また、代替パスの帯域幅が低いか、輻輳する傾向があるルートの場合よりも、ほぼ同等の代替パスを持つルートに異なるしきい値を設定することが望ましい場合があります。これは、異なるパラメーターのセットを異なる範囲の設定値に関連付けることによって解決できます。パラメータの選択は、BGP LOCAL_PREFに基づくことができます。

Parameter selection could also be based on whether an alternate route was known. A route would be considered if, for any applicable parameter set, an alternate route with the specified preference value existed and the figure of merit associated with the parameter set did not indicate a need to suppress the route. A less aggressive suppression would be applied to the case where no alternate route at all existed. In the simplest case, a more aggressive suppression would be applied if any alternate route existed. Only the highest preference (most preferred) value needs to be specified, since the ranges may overlap.

パラメータの選択は、代替ルートが既知であるかどうかに基づくこともできます。該当するパラメーターセットについて、指定された優先順位値を持つ代替ルートが存在し、パラメーターセットに関連付けられた性能指数がルートを抑制する必要性を示さなかった場合、ルートが考慮されます。代替ルートがまったく存在しない場合には、それほど積極的ではない抑制が適用されます。最も単純なケースでは、代替ルートが存在する場合、より強力な抑制が適用されます。範囲が重複する可能性があるため、最も高い優先度（最も好ましい）値のみを指定する必要があります。

It might also be desirable to configure a different set of thresholds for routes which rely on switched services and may disconnect at times to reduce connect charges. Such routes might be expected to change state somewhat more often, but should be suppressed if continuous state changes indicate instability.

また、スイッチドサービスに依存し、接続を切断して接続料金を削減する可能性があるルートに対して、異なるしきい値のセットを構成することが望ましい場合もあります。そのようなルートは、状態をいくらか頻繁に変更すると予想されるかもしれませんが、継続的な状態変化が不安定を示す場合は抑制されるべきです。

While not essential, it might be desirable to be able to configure multiple sets of configuration parameters per route. It may also be desirable to be able to configure sets of parameters that only correspond to a set of routes (identified by AS path, peer router, specific destinations or other means). Experience may dictate how much flexibility is needed and how to best to set the parameters. Whether to allow different damping parameter sets for different routes, and whether to allow multiple figures of merit per route is an implementation choice.

必須ではありませんが、ルートごとに複数の構成パラメータセットを構成できることが望ましい場合があります。ルートのセット（ASパス、ピアルーター、特定の宛先またはその他の手段によって識別される）にのみ対応するパラメーターのセットを構成できることが望ましい場合もあります。経験により、どの程度の柔軟性が必要で、どのようにパラメーターを設定するのが最善かが決まります。ルートごとに異なる減衰パラメーターセットを許可するかどうか、およびルートごとに複数の性能指数を許可するかどうかは、実装の選択です。

Parameter selection can also be based on prefix length. The rationale is that longer prefixes tend to reach less end systems and are less important and these less important prefixes can be damped more aggressively. This technique is in fairly widespread use. Small sites or those with dense address allocation who are multihomed are often reachable by long prefixes which are not easily aggregated. These sites tend to dispute the choice of prefix length for parameter selection. Advocates of the technique point out that it encourages better aggregation.

パラメータの選択は、プレフィックス長に基づくこともできます。理論的根拠は、プレフィックスが長いほどエンドシステムに到達しない傾向があり、重要性が低くなるため、これらの重要性の低いプレフィックスをより積極的に減衰させることができます。この手法はかなり広く使用されています。小さなサイトや、マルチホームのアドレス割り当てが密集しているサイトは、簡単に集約できない長いプレフィックスで到達できることがよくあります。これらのサイトは、パラメータ選択のためのプレフィックス長の選択に異議を唱える傾向があります。この手法の支持者は、この手法がより良い集約を促進すると指摘しています。

4.2 Configuration Parameters

4.2 構成パラメータ

At configuration time, a number of parameters may be specified by the user. The configuration parameters are expressed in units meaningful to the user. These differ from the parameters used at run time which are in unit convenient for computation. The run time parameters are derived from the configuration parameters. Suggested configuration parameters are listed below.

構成時に、いくつかのパラメーターをユーザーが指定できます。構成パラメーターは、ユーザーにとって意味のある単位で表されます。これらは実行時に使用されるパラメータとは異なります。これらは計算に便利な単位です。実行時パラメーターは、構成パラメーターから導出されます。推奨される構成パラメーターを以下に示します。

cutoff threshold (cut)

カットオフしきい値（カット）

This value is expressed as a number of route withdrawals. It is the value above which a route advertisement will be suppressed.

この値は、ルート撤回の数として表されます。これは、それを超えるとルートアドバタイズメントが抑制される値です。

reuse threshold (reuse)

再利用しきい値（再利用）

This value is expressed as a number of route withdrawals. It is the value below which a suppressed route will now be used again.

この値は、ルート撤回の数として表されます。この値を下回ると、抑制されたルートが再び使用されるようになります。

maximum hold down time (T-hold)

最大ホールドダウン時間（Tホールド）

This value is the maximum time a route can be suppressed no matter how unstable it has been prior to this period of stability.

この値は、ルートがこの安定期間の前にどれほど不安定であったとしても、ルートを抑制できる最大時間です。

decay half life while reachable (decay-ok)

到達可能な半減期の減衰（減衰OK）

This value is the time duration in minutes or seconds during which the accumulated stability figure of merit will be reduced by half if the route if considered reachable (whether suppressed or not).

この値は、ルートが到達可能と見なされた場合（抑制されているかどうかに関係なく）、累積された安定性能指数が半分に削減される期間（分または秒）です。

decay half life while unreachable (decay-ng)

到達不能な半減期の減衰（decay-ng）

This value is the time duration in minutes or seconds during which the accumulated stability figure of merit will be reduced by half if the route if considered unreachable. If not specified or set to zero, no decay will occur while a route remains unreachable.

この値は、ルートが到達不能と見なされた場合に、累積された安定性能指数が半分に減らされる時間（分または秒）です。指定しないかゼロに設定した場合、ルートが到達不能のままである間、減衰は発生しません。

decay memory limit (Tmax-ok or Tmax-ng)

減衰メモリ制限（Tmax-okまたはTmax-ng）

This is the maximum time that any memory of previous instability will be retained given that the route's state remains unchanged, whether reachable or unreachable. This parameter is generally used to determine array sizes.

これは、到達可能か到達不可能かに関わらず、ルートの状態が変更されないままである場合に、以前の不安定性のメモリが保持される最大時間です。このパラメーターは通常、配列サイズを決定するために使用されます。

There may be multiple sets of the parameters above as described in Section 4.1. The configuration parameters listed below would be applied system wide. These include the time granularity of all computations, and the parameters used to control reevaluation of routes that have previously been suppressed.

セクション4.1で説明されているように、上記のパラメータのセットが複数存在する場合があります。以下にリストされている構成パラメーターは、システム全体に適用されます。これらには、すべての計算の時間の細分性、および以前に抑制されたルートの再評価を制御するために使用されるパラメーターが含まれます。

time granularity (delta-t)

時間の粒度（delta-t）

This is the time granularity in seconds used to perform all decay computations.

これは、すべての減衰計算を実行するために使用される秒単位の時間粒度です。

reuse list time granularity (delta-reuse)

リスト時間の粒度を再利用する（デルタ再利用）

This is the time interval between evaluations of the reuse lists. Each reuse lists corresponds to an additional time increment.

これは、再利用リストの評価の時間間隔です。各再利用リストは、追加の時間増分に対応しています。

reuse list memory reuse-list-max

再利用リストメモリ再利用リスト最大

This is the time value corresponding to the last reuse list. This may be the maximum value of T-hold for all parameter sets of may be configured.

これは、最後の再利用リストに対応する時間値です。これは、構成されているすべてのパラメーターセットのTホールドの最大値である場合があります。

number of reuse lists (reuse-list-size)

再利用リストの数（reuse-list-size）

This is the number of reuse lists. It may be determined from reuse-list-max or set explicitly.

再利用リストの数です。これは、reuse-list-maxから決定するか、明示的に設定できます。

A recommended optimization is described in Section 4.8.6 that involves an array referred to as the "reuse index array". A 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 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.

「再利用インデックス配列」と呼ばれる配列を含む推奨される最適化については、セクション4.8.6で説明しています。使用中の減衰率ごとに再利用インデックス配列が必要です。再利用インデックス配列は、抑制されたときにルートを配置する再利用リストを推定するために使用されます。適切に配置することで、定期的に減衰を評価して、ルートを再利用できるかどうか、またはストレージを復旧できるかどうかを判断する必要がなくなります。再利用インデックス配列を使用すると、配置を決定するために対数を計算する必要がなくなります。システム全体に1つのパラメーターを追加できます。

reuse index array size (reuse-index-array-size)

インデックス配列サイズを再利用（reuse-index-array-size）

This is the size of reuse index arrays. This size determines the accuracy with which suppressed routes can be placed within the set of reuse lists when suppressed for a long time.

これは、再利用インデックス配列のサイズです。このサイズは、長期間抑制されたときに抑制されたルートを再利用リストのセット内に配置できる精度を決定します。

4.3 Guidelines for Setting Parameters

4.3 パラメータ設定のガイドライン

The decay half life should be set to a time considerably longer than the period of the route flap it is intended to address. For example, if the decay is set to ten minutes and a route is withdrawn and readvertised exactly every ten minutes, the route would continue to flap if the cutoff was set to a value of 2 or above.

減衰半減期は、対応するルートフラップの期間よりもかなり長い時間に設定する必要があります。たとえば、減衰が10分に設定されていて、ルートが10分ごとに撤回および再アドバタイズされる場合、カットオフが2以上の値に設定されていると、ルートはフラップし続けます。

The stability figure of merit itself is an accumulated time decayed total. This must be kept in mind in setting the decay time, cutoff values and reuse values. The figure of merit is increased each time a route transitions from reachable to unreachable. The figure of merit is decayed at a rate proportional to its current value. Increasing the rate of route flap therefore increments the figure of merit more often and reaches a given threshhold in a shorter amount of time. When the response to a constant rate route flap is plotted this looks like a sawtooth with an abrupt rising edge and a decaying falling edge. Since the absolute decay amount is proportional to the figure of merit, at a continuous constant flap rate the baseline of the sawtooth will tend to stop rising and converge if not clipped by a ceiling value.

安定性能指数自体は、累積された時間減衰合計です。これは、減衰時間、カットオフ値、および再利用値を設定する際に留意する必要があります。ルートが到達可能から到達不能に移行するたびに、性能指数が増加します。性能指数は、その現在の値に比例する割合で減衰します。したがって、ルートフラップのレートを上げると、性能指数がより頻繁に増加し、短時間で所定のしきい値に到達します。定速ルートフラップへの応答がプロットされると、これは急激な立ち上がりエッジと減衰する立ち下がりエッジを持つ鋸歯状に見えます。絶対減衰量は性能指数に比例するため、連続一定フラップレートでは、鋸歯のベースラインは上昇を停止し、上限値でクリッピングされない場合は収束する傾向があります。

If clipped by a ceiling value, the sawtooth baseline will simply reach the ceiling faster at a higher rate of route flap. For example, if flapping at four times the decay rate the following progression occurs. When the route becomes unreachable the first time the value becomes 1. When the next flap occurs, one is added to the previous value, which has been decreased by the fourth root of 2 (the amount of decay that would occur in 1/4 of the half life time if decay is exponential). The sequence is 1, 1.84, 2.55, 3.14, 3.64, 4.06, 4.42, 4.71, 4.96, 5.17, ..., converging at about 6.285. If a route flaps at four times the decay rate, it will reach 3 in 4 cycles, 4 in 6 cycles, 5 in 10 cycles, and will converge at about 6.3. At twice the decay time, it will reach 3 in 7 cycles, and converge at a value of less than 3.5.

天井値で切り取られた場合、のこぎり歯のベースラインは、ルートフラップの割合が高いほど、天井に簡単に到達します。たとえば、減衰率の4倍で羽ばたくと、次のような進行が起こります。最初に値が1になったときにルートが到達不能になると、次のフラップが発生すると、前の値に1が加算されます。これは、2の4乗根（1/4で発生する減衰の量）だけ減らされています。減衰が指数関数的である場合の半減期）。シーケンスは1、1.84、2.55、3.14、3.64、4.06、4.42、4.71、4.96、5.17、...、約6.285に収束します。ルートが減衰率の4倍でフラップする場合、4サイクルで3、6サイクルで4、10サイクルで5に達し、約6.3に収束します。減衰時間の2倍になると、7サイクルで3に達し、3.5未満の値に収束します。

Figure 1 shows the stability figure of merit for route flap at a constant rate. The time axis is labeled in multiples of the decay half life. The plots represent route flap with a period of 1/2, 1/3, 1/4, and 1/8 times the decay half life. A ceiling of 4.5 was set, which can be seen to affect three of the plots, effectively limiting the time it takes to readvertise the route regardless of the prior history. With cutoff and reuse thresholds of 1.5 and 0.75, routes would be suppressed after being declared unreachable 2-3 times and be used again after approximately 2 decay half life periods of stability.

図1は、一定速度でのルートフラップの安定性能指数を示しています。時間軸は、減衰半減期の倍数でラベル付けされています。プロットは、減衰半減期の1 / 2、1 / 3、1 / 4、および1/8倍の周期でルートフラップを表します。 4.5の天井が設定されました。これは3つのプロットに影響を与えることがわかり、以前の履歴に関係なくルートを再アドバタイズするのにかかる時間を効果的に制限します。カットオフと再利用のしきい値が1.5と0.75の場合、ルートは到達不能と2〜3回宣言された後に抑制され、約2減衰の半減期の安定後に再び使用されます。

This function can be expressed formally. Reachability of a route can be represented by a variable "R" with possible values of 0 and 1 representing unreachable and reachable. At a discrete time R can only have one value. The figure of merit is increased by 1 at each transition from R=1 to R=0 and clipped to a ceiling value. The decay in figure of merit can then be expressed over a set of discrete times as follows.

この関数は形式的に表現できます。ルートの到達可能性は、変数 "R"で表すことができます。0と1の値は、到達不能と到達可能を表します。離散時間では、Rは1つの値しか持てません。性能指数は、R = 1からR = 0に遷移するたびに1ずつ増加し、上限値にクリップされます。次に、性能指数の減衰は、次のように一連の離散時間にわたって表現できます。

      figure-of-merit(t) = K * figure-of-merit(t - delta-t)
      K = K1 for R=0 K=K2 for R=1

The four plots are presented vertically. Due to space limitations, only a limited set of points along the time axis are shown. The value of the figure of merit is given. Along side each value is a very low resolution strip chart made up of ASCII dots. This is just intended to give a rough feel for the rise and fall of the values. The strip charts are not displayed on an overlapping set of axes because the sawtooth waveforms cross each other quite frequently. At the very low resolution of these plots, the rise and fall of the baseline is evident, but the sawtooth nature is only observed in the printed value.

4つのプロットは垂直に表示されます。スペースの制限により、時間軸に沿った限られたポイントセットのみが表示されています。性能指数の値が示されています。各値は、ASCIIドットで構成された非常に低解像度のストリップチャートです。これは、値の上昇と下降の大まかな感じを与えることを目的としています。のこぎり波は非常に頻繁に互いに交差するため、ストリップチャートは軸の重なり合うセットに表示されません。これらのプロットの解像度が非常に低い場合、ベースラインの上昇と下降は明白ですが、鋸歯状の性質は印刷された値でのみ観察されます。

From the maximum hold time value (T-hold), a ratio of the reuse value 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.

最大ホールドタイム値（T-hold）から、上限に対する再利用値の比率を決定できます。オーバーフローが問題にならないように上限の整数値を選択し、他のすべての値を適宜スケーリングできます。両方のカットオフが指定されている場合、または複数のパラメーターセットが使用されている場合は、最も高い天井が使用されます。

time figure-of-merit as a function of time (in minutes)

時間の関数としての時間の性能指数（分単位）

0.00 0.000 . 0.000 . 0.000 . 0.000 . 0.08 0.000 . 0.000 . 0.000 . 0.000 . 0.16 0.000 . 0.000 . 0.000 . 0.973 . 0.24 0.000 . 0.000 . 0.000 . 0.920 . 0.32 0.000 . 0.000 . 0.946 . 1.817 . 0.40 0.000 . 0.953 . 0.895 . 2.698 . 0.48 0.000 . 0.901 . 0.847 . 2.552 . 0.56 0.953 . 0.853 . 1.754 . 3.367 . 0.64 0.901 . 0.807 . 1.659 . 4.172 . 0.72 0.853 . 1.722 . 1.570 . 3.947 . 0.80 0.807 . 1.629 . 2.444 . 4.317 . 0.88 0.763 . 1.542 . 2.312 . 4.469 . 0.96 0.722 . 1.458 . 2.188 . 4.228 . 1.04 1.649 . 2.346 . 3.036 . 4.347 . 1.12 1.560 . 2.219 . 2.872 . 4.112 . 1.20 1.476 . 2.099 . 2.717 . 4.257 . 1.28 1.396 . 1.986 . 3.543 . 4.377 . 1.36 1.321 . 2.858 . 3.352 . 4.141 . 1.44 1.250 . 2.704 . 3.171 . 4.287 . 1.52 2.162 . 2.558 . 3.979 . 4.407 . 1.60 2.045 . 2.420 . 3.765 . 4.170 . 1.68 1.935 . 3.276 . 3.562 . 4.317 . 1.76 1.830 . 3.099 . 4.356 . 4.438 . 1.84 1.732 . 2.932 . 4.121 . 4.199 . 1.92 1.638 . 2.774 . 3.899 . 3.972 . 2.00 1.550 . 2.624 . 3.688 . 3.758 . 2.08 1.466 . 2.483 . 3.489 . 3.555 . 2.16 1.387 . 2.349 . 3.301 . 3.363 . 2.24 1.312 . 2.222 . 3.123 . 3.182 . 2.32 1.242 . 2.102 . 2.955 . 3.010 . 2.40 1.175 . 1.989 . 2.795 . 2.848 . 2.48 1.111 . 1.882 . 2.644 . 2.694 . 2.56 1.051 . 1.780 . 2.502 . 2.549 . 2.64 0.995 . 1.684 . 2.367 . 2.411 . 2.72 0.941 . 1.593 . 2.239 . 2.281 . 2.80 0.890 . 1.507 . 2.118 . 2.158 . 2.88 0.842 . 1.426 . 2.004 . 2.042 . 2.96 0.797 . 1.349 . 1.896 . 1.932 . 3.04 0.754 . 1.276 . 1.794 . 1.828 . 3.12 0.713 . 1.207 . 1.697 . 1.729 . 3.20 0.675 . 1.142 . 1.605 . 1.636 . 3.28 0.638 . 1.081 . 1.519 . 1.547 . 3.36 0.604 . 1.022 . 1.437 . 1.464 . 3.44 0.571 . 0.967 . 1.359 . 1.385 .

Figure 1: Instability figure of merit for flap at a constant rate

図1：一定速度でのフラップの不安定性性能指数

time figure-of-merit as a function of time (in minutes)

時間の関数としての時間の性能指数（分単位）

0.00 0.000 . 0.000 . 0.000 . 0.20 0.000 . 0.000 . 0.000 . 0.40 0.000 . 0.000 . 0.000 . 0.60 0.000 . 0.000 . 0.000 . 0.80 0.000 . 0.000 . 0.000 . 1.00 0.999 . 0.999 . 0.999 . 1.20 0.971 . 0.971 . 0.929 . 1.40 0.945 . 0.945 . 0.809 . 1.60 0.919 . 0.865 . 0.704 . 1.80 0.894 . 0.753 . 0.613 . 2.00 1.812 . 1.657 . 1.535 . 2.20 1.762 . 1.612 . 1.428 . 2.40 1.714 . 1.568 . 1.244 . 2.60 1.667 . 1.443 . 1.083 . 2.80 1.622 . 1.256 . 0.942 . 3.00 1.468 . 1.094 . 0.820 . 3.20 2.400 . 2.036 . 1.694 . 3.40 2.335 . 1.981 . 1.475 . 3.60 2.271 . 1.823 . 1.284 . 3.80 2.209 . 1.587 . 1.118 . 4.00 1.999 . 1.381 . 0.973 . 4.20 2.625 . 2.084 . 1.727 . 4.40 2.285 . 1.815 . 1.503 . 4.60 1.990 . 1.580 . 1.309 . 4.80 1.732 . 1.375 . 1.139 . 5.00 1.508 . 1.197 . 0.992 . 5.20 1.313 . 1.042 . 0.864 . 5.40 1.143 . 0.907 . 0.752 . 5.60 0.995 . 0.790 . 0.654 . 5.80 0.866 . 0.688 . 0.570 . 6.00 0.754 . 0.599 . 0.496 . 6.20 0.656 . 0.521 . 0.432 . 6.40 0.571 . 0.454 . 0.376 . 6.60 0.497 . 0.395 . 0.327 . 6.80 0.433 . 0.344 . 0.285 . 7.00 0.377 . 0.299 . 0.248 . 7.20 0.328 . 0.261 . 0.216 . 7.40 0.286 . 0.227 . 0.188 . 7.60 0.249 . 0.197 . 0.164 . 7.80 0.216 . 0.172 . 0.142 . 8.00 0.188 . 0.150 . 0.124 .

Figure 2: Separate decay constants when unreachable

図2：到達できない場合の個別の減衰定数

Figure 2 shows the effect of configuring separate decay rates to be used when the route is reachable or unreachable. The decay rate is 5 times slower when the route is unreachable. In the three case shown, the period of the route flap is equal to the decay half life but the route is reachable 1/8 of the time in one, reachable 1/2 the time in one, and reachable 7/8 of the time in the other. In the last case the route is not suppressed until after the third unreachable (when it is above the top threshold after becoming reachable again).

図2は、ルートが到達可能または到達不可能であるときに使用される個別の減衰率を構成する効果を示しています。ルートに到達できない場合、減衰率は5倍遅くなります。示されている3つのケースでは、ルートフラップの期間は減衰半減期と同じですが、ルートは一度に1/8の時間に到達可能、1分の1の半分に到達可能、7/8の時間に到達可能です他の。最後のケースでは、ルートは3番目の到達不能になるまで抑制されません（再び到達可能になり、上限しきい値を超える場合）。

The main point of Figure 2 is to show the effect of changing the duty cycle of the square wave in the variable "R" for a fixed frequency of the square wave. If the decay constants are chosen such that decay is slower when R=0 (the route is unreachable), then the figure of merit rises more slowly (more accurately, the baseline of the sawtooth waveform rises more slowly) if the route is reachable a larger percentage of the time. The effect when the route becomes persistently reachable again can be fairly negligible if the sawtooth is clipped by a ceiling value, but is more significant if a slow route flap rate or short interval of route flapping is such that the sawtooth does not reach the ceiling value. In Figure 2 the interval in which the routes are unstable is short enough that the ceiling value is not reached, therefore, the routes that are reachable for a greater percentage of the route flap cycle are reused (placed in the RIB and advertised to peers) sooner than others after the route becomes stable again ("R" becomes 1, indicating the announced state goes to reachable and remains there).

図2の要点は、方形波の固定周波数に対して変数「R」で方形波のデューティサイクルを変更した場合の影響を示すことです。 R = 0（ルートに到達できない場合）の減衰が遅くなるように減衰定数が選択されている場合、ルートに到達可能であれば、性能指数はよりゆっくりと上昇します（より正確には、ノコギリ波のベースラインはよりゆっくりと上昇します）。時間の大きな割合。鋸歯が天井値によって切り取られている場合、ルートが再び持続的に到達可能になったときの影響はかなり無視できますが、遅いルートフラップレートまたはルートフラッピングの短い間隔が鋸歯が天井値に達しないほど大きい場合、より重要です。。図2では、ルートが不安定になる間隔が短すぎて上限値に到達しないため、ルートフラップサイクルのより大きな割合で到達可能なルートが再利用されます（RIBに配置され、ピアにアドバタイズされます）。ルートが再び安定した後、他よりも早く（「R」が1になり、アナウンスされた状態が到達可能になり、そこに留まることを示します）。

In both Figure 1 and Figure 2, routes would be suppressed. Routes flapping at the decay half life or less would be withdrawn two or three times and then remain withdrawn until they had remained stably announced and stable for on the order of 1 1/2 to 2 1/2 times the decay half life (given the ceiling in the example).

図1と図2の両方で、ルートは抑制されます。減衰半減期以下でフラッピングするルートは、2回または3回撤回され、その後、崩壊半減期の約1 1/2から2 1/2倍の安定したアナウンスと安定が維持されるまで、撤回されたままになります。例では天井）。

The purpose of damping BGP route flap is to reduce the processor burden at the immediate router and the processor burden to downstream routers (BGP peer routers and peers of peers that will see the route announcements advertised by the immediate router). Computing a figure of merit at each discrete time interval using figure-of-merit(t) = K * figure-of-merit(t - delta-t) would be very inefficient and defeat the purpose. This problem is addressed by defering computation as long as possible and doing a single simple computation to compensate for the decay during the time that has elapsed since the figure of merit was last updated. The use of decay arrays provides the single simple calculation. The use of reuse lists (described later) provide a means to defer calculations. A route becomes usable if there was not further change for a period of time and the route is unreachable. The data structure storage is recovered if the route's state has not changed for a period of time and it has been unreachable. The reuse arrays provide a means to estimate how long a computation can be deferred if there is no further change.

BGPルートフラップを抑制する目的は、直接のルーターでのプロセッサの負担と、ダウンストリームルーター（BGPピアルーター、および直接のルーターによってアドバタイズされたルートアナウンスを受信するピアのピア）へのプロセッサの負担を軽減することです。 figure-of-merit（t）= K * figure-of-merit（t-delta-t）を使用して離散時間間隔ごとに性能指数を計算することは非常に非効率的であり、目的を達成できません。この問題は、可能な限り計算を延期し、性能指数が最後に更新されてから経過した時間の減衰を補償するために単一の単純な計算を実行することで対処されます。減衰配列の使用により、単一の単純な計算が提供されます。再利用リスト（後述）を使用すると、計算を延期することができます。一定期間さらに変更がなく、ルートに到達できない場合、ルートは使用可能になります。ルートの状態が一定期間変化せず、到達できなかった場合、データ構造ストレージが回復されます。再利用配列は、それ以上変更がない場合に計算を延期できる時間を推定する手段を提供します。

A larger time granularity will keep table storage down. The time granularity should be less than a minimal reasonable time between expected worse case route flaps. It might be reasonable to fix this parameter at compile time or set a default and strongly recommend that the user leave it alone. With an exponential decay, array size can be greatly reduced by setting a period of complete stability after which the decayed total will be considered zero rather than retaining a tiny quantity. Alternately, very long decays can be implemented by multiplying more than once if array bounds are exceeded.

時間の細分性が大きいほど、テーブルのストレージは低く抑えられます。時間の細分性は、予想される最悪のケースのルートフラップ間の最小の妥当な時間未満である必要があります。コンパイル時にこのパラメーターを修正するか、デフォルトを設定して、ユーザーにそのままにしておくことを強くお勧めします。指数関数的減衰では、完全な安定期間を設定することにより、アレイサイズを大幅に削減できます。その後、減衰した合計は、小さな量を保持するのではなくゼロと見なされます。または、配列の境界を超えた場合、非常に長い減衰を2回以上掛けることで実装できます。

The reuse lists hold suppressed routes grouped according to how long it will be before the routes are eligible for reuse. Periodically each list will be advanced by one position and one list removed as described in Section 4.8.7. All of the suppressed routes in the removed list will be reevaluated and either used or placed in another list according to how much additional time must elapse before the route can be reused. The last list will always contain all the routes which will not be advertised for more time than is appropriate for the remaining list heads. When the last list advances to the front, some of the routes will not be ready to be used and will have to be requeued. The time interval for reconsidering suppressed routes and number of list heads should be configurable. Reasonable defaults might be 30 seconds and 64 list heads. A route suppressed for a long time would need to be reevaluated every 32 minutes.

再利用リストは、ルートが再利用に適格になるまでの期間に応じてグループ化された抑制されたルートを保持します。セクション4.8.7で説明されているように、各リストは定期的に1ポジション進められ、1リストは削除されます。削除されたリスト内の抑制されたルートはすべて再評価され、ルートが再利用される前にどれだけの時間が経過する必要があるかに従って、使用または別のリストに配置されます。最後のリストには常に、残りのリストヘッドに適切な時間よりもアドバタイズされないすべてのルートが含まれます。最後のリストが前に進むと、一部のルートは使用する準備ができておらず、キューに再登録する必要があります。抑制されたルートとリストヘッドの数を再検討する時間間隔は、構成可能である必要があります。妥当なデフォルトは、30秒と64のリストヘッドです。長時間抑制されたルートは、32分ごとに再評価する必要があります。

4.4 Run Time Data Structures

4.4 実行時のデータ構造

A fixed small amount of per system storage will be required. Where sets of multiple configuration parameters are used, storage will be required per set of parameters. A small amount of per route storage is required. A set of list heads is needed. These list heads are 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 of these objects seems like one of a number of reasonable implementations. Similarly, a means of associating a route to a reuse list is required. A small overhead will be required for the pointers needed to implement whatever data structure is chosen for the reuse lists. The suggested implementation uses a double linked lists and so requires two pointers per figure of merit.

ルートごとに複数の構成パラメーターのセットが許可される場合は、複数の性能指数とパラメーターのセットを各ルートに関連付ける何らかの手段が必要です。これらのオブジェクトのリンクリストを作成することは、多くの合理的な実装の1つに思えます。同様に、ルートを再利用リストに関連付ける手段も必要です。再利用リスト用に選択されたデータ構造を実装するために必要なポインターには、小さなオーバーヘッドが必要です。推奨される実装では、二重リンクリストを使用するため、性能指数ごとに2つのポインターが必要です。

Each set of configuration parameters can reference decay arrays and reuse arrays. These arrays should be shared among multiple sets of parameters since their storage requirement is not negligible. There will be only one set of reuse list heads for the entire router.

構成パラメーターの各セットは、減衰配列を参照し、配列を再利用できます。これらの配列は、ストレージ要件が無視できないため、複数のパラメーターセットで共有する必要があります。ルータ全体で使用できる再利用リストヘッドのセットは1つだけです。

4.4.1 Data Structures for Configuration Parameter Sets

4.4.1 構成パラメーターセットのデータ構造

Based on the configuration parameters described in the previous section, the following values can be computed as scaled integers directly from the corresponding configuration parameters.

前のセクションで説明した構成パラメーターに基づいて、以下の値は、対応する構成パラメーターから直接スケーリングされた整数として計算できます。

o decay array scale factor (decay-array-scale-factor)

o 減衰配列スケール係数（decay-array-scale-factor）

o cutoff value (cut)

o カットオフ値（カット）

o reuse value (reuse)

o 再利用値（再利用）

o figure of merit ceiling (ceiling)

o 性能指数天井（天井）

Each configuration parameter set will reference one or two decay arrays and one or two reuse arrays. Only one array will be needed if the decay rate is the same while a route is unreachable as while it is reachable, or if the stability figure of merit does not decay while a route is unreachable.

各構成パラメーターセットは、1つまたは2つの減衰配列と1つまたは2つの再利用配列を参照します。ルートに到達できないときと到達できないときの減衰率が同じ場合、またはルートに到達できないときに安定性性能指数が減衰しない場合は、アレイが1つだけ必要です。

4.4.2 Data Structures per Decay Array and Reuse Index Array

4.4.2 減衰配列ごとのデータ構造とインデックス配列の再利用

The following are also computed from the configuration parameters though not as directly. The computation is described in Section 4.5.

以下も直接ではありませんが、構成パラメーターから計算されます。計算については、セクション4.5で説明します。

o decay rate per tick (decay-delta-t)

o ティックごとの減衰率（decay-delta-t）

o decay array size (decay-array-size)

o 減衰配列サイズ（decay-array-size）

o decay array (decay[])

o 減衰配列（decay []）

o reuse index array size (reuse-index-array-size) o reuse index array (reuse-index-array[])

oインデックス配列のサイズを再利用（reuse-index-array-size）oインデックス配列を再利用（reuse-index-array []）

For each decay rate specified, an array will be used to store the value of a computed parameter raised to the power of the index of each array element. This is to speed computations. The decay rate per tick is an intermediate value expressed as a real number and used to compute the values stored in the decay arrays. The array size is computed from the decay memory limit configuration parameter expressed as an array size or as a maximum hold time.

指定された減衰率ごとに、配列を使用して、各配列要素のインデックスで累乗された計算パラメーターの値を格納します。これは計算を高速化するためです。ティックごとの減衰率は、実数として表される中間値であり、減衰配列に格納される値を計算するために使用されます。配列サイズは、配列サイズまたは最大保持時間として表される減衰メモリ制限構成パラメーターから計算されます。

The decay array size must be of sufficient size to accommodate the specified decay memory given the time granularity, or sufficient to hold the number of array elements until integer rounding produces a zero result if that value is smaller, or a implementation imposed reasonable size to prevent configurations which use excessive memory. Implementations may chose to make the array size shorter and multiply more than once when decaying a long time interval to reduce storage.

decay配列のサイズは、指定されたdecayメモリに対応するのに十分なサイズである必要があります。または、その値が小さい場合に整数の丸めがゼロの結果を生成するまで配列要素の数を保持するのに十分なサイズであるか、実装が適切なサイズを課して、過剰なメモリを使用する構成。実装は、ストレージを削減するために長い時間間隔を減衰させるときに、配列サイズを短くし、複数回乗算することを選択する場合があります。

The reuse index arrays serve a similar purpose to the decay arrays. In BGP, a route is said to be "used" if it is considered the best route. In this context, if the route is "used" it is placed in the RIB and is eligible for advertisement to BGP peers. If a route is withdrawn (a BGP announcement is made by a peer indicating that it is no longer reachable), then it is no longer eligible for "use". When a route becomes reachable it may not be "used" immediately if the figure of merit indicates that a recent instability has occurred. After the route remains stable and the figure of merit decays below the "reuse" threshhold, the route is said to be eligible to be "reused" (treated as truly reachable, placed in the RIB and advertised to peers). The amount of time until a route can be reused can be determined using a array lookup. The array can be built given the decay rate. The array is indexed using a scaled integer proportional to the ratio between a current stability figure of merit value and the value needed for the route to be reused.

再利用インデックス配列は、崩壊配列と同様の目的を果たします。 BGPでは、ルートが最適なルートと見なされる場合、そのルートは「使用されている」と言います。このコンテキストでは、ルートが「使用」されている場合、そのルートはRIBに配置され、BGPピアへのアドバタイズの資格があります。ルートが撤回された場合（ピアからBGPアナウンスが行われ、到達できなくなったことを示す）、そのルートは "使用"できなくなります。ルートが到達可能になったときに、最近の不安定性が発生したことを性能指数が示している場合、そのルートはすぐに「使用」されない可能性があります。ルートが安定したままで、性能指数が「再利用」のしきい値を下回ると、ルートは「再利用」する資格があると言われます（本当に到達可能として扱われ、RIBに配置され、ピアにアドバタイズされます）。ルートを再利用できるようになるまでの時間は、配列ルックアップを使用して決定できます。減衰率を考慮してアレイを構築できます。配列は、現在の安定性能指数値とルートを再利用するために必要な値との比率に比例するスケーリングされた整数を使用してインデックスが付けられます。

4.4.3 Per Route State

4.4.3 ルート状態ごと

Information must be maintained per some tuple representing a route. At the very minimum, the NLRI (BGP prefix and length) must be contained in the tuple. Different BGP attributes may be included or excluded depending on the specific situation. The AS path should also be contained in the tuple by default. The tuple may also optionally contain other BGP attributes such as MULTI_EXIT_DISCRIMINATOR (MED).

ルートを表すタプルごとに情報を維持する必要があります。最低でも、NLRI（BGPプレフィックスと長さ）がタプルに含まれている必要があります。特定の状況に応じて、さまざまなBGP属性を含めたり除外したりできます。 ASパスもデフォルトでタプルに含まれている必要があります。タプルには、オプションでMULTI_EXIT_DISCRIMINATOR（MED）などの他のBGP属性を含めることもできます。

The tuple representing a route for the purpose of route flap damping is:

ルートフラップダンピングの目的でルートを表すタプルは次のとおりです。

      tuple entry            default      options
      -------------------------------------------
      NLRI
        prefix               required
        length               required
      AS path                included     option to exclude
      last AS set in path    excluded     option to include
      next hop               excluded     option to include
      MED                    excluded     option to include
                                          in comparisons only

The AS path is generally included in order to identify downstream instability which is not being damped or not being sufficiently damped and is alternating between a stable and an unstable path. Under rare circumstances it may be desirable to exclude AS path for all or a subset of prefixes. If an AS path ends in an AS set, in practice the path is always for an aggregate. Changes to the trailing AS set should be ignored. Ideally the AS path comparison should insure that at least one AS has remained constant in the old and new AS set, but completely ignoring the contents of a trailing AS set is also acceptable.

減衰されていないか、十分に減衰されておらず、安定したパスと不安定なパスを交互に繰り返すダウンストリームの不安定性を特定するために、ASパスが一般に含まれています。まれな状況では、プレフィックスのすべてまたはサブセットのASパスを除外することが望ましい場合があります。 ASパスがASセットで終了する場合、実際には、パスは常にアグリゲート用です。後続のASセットへの変更は無視する必要があります。理想的には、ASパスの比較により、少なくとも1つのASが新旧のASセットで一定のままであることが保証されますが、後続のASセットの内容を完全に無視することも可能です。

Including next hop and MED changes can help suppress the use of an AS which is internally unstable or avoid a next hop which is closer to an unstable IGP path in the adjacent AS. If a large number of MED values are used, the increase in the amount of state may become a problem. For this reason MED is disabled by default and enabled only as part of the tuple comparison, using a single state entry regardless of MED value. Including MED will suppress the use of the adjacent AS even though the change need not be propagated further. Using MED is only a safe practice if a path is known to exist through another AS or where there are enough peering sites with the adjacent AS such that routes heard at only a subset of the peering sites will be suppressed.

ネクストホップとMEDの変更を含めると、内部的に不安定なASの使用を抑制したり、隣接ASの不安定なIGPパスに近いネクストホップを回避したりできます。多数のMED値を使用すると、状態量の増加が問題になる場合があります。このため、MEDはデフォルトでは無効であり、タプル比較の一部としてのみ有効であり、MED値に関係なく単一の状態エントリを使用します。 MEDを含めると、変更をさらに伝播する必要がない場合でも、隣接ASの使用が抑制されます。 MEDの使用は、パスが別のASを介して存在することがわかっている場合、またはピアリングサイトのサブセットでのみ受信されるルートが抑制されるように隣接ASとのピアリングサイトが十分にある場合にのみ安全な方法です。

4.4.4 Data Structures per Route

4.4.4 ルートごとのデータ構造

The following information must be maintained per route. A route here is considered to be a tuple usually containing NLRI, next hop, and AS path as defined in Section 4.4.3.

ルートごとに以下の情報を保持する必要があります。ここでのルートは、セクション4.4.3で定義されているように、通常、NLRI、ネクストホップ、およびASパスを含むタプルと見なされます。

stability figure of merit (figure-of-merit)

安定性の性能指数（性能指数）

Each route must have a stability figure of merit per applicable parameter set.

各ルートには、該当するパラメーターセットごとに安定度の性能指数が必要です。

last time updated (time-update)

最終更新日時（time-update）

The exact last time updated must be maintained to allow exponential decay of the accumulated figure of merit to be deferred until the route might reasonable be considered eligible for a change in status (having gone from unreachable to reachable or advancing within the reuse lists).

ルートがステータスの変更に適格であると合理的に見なされる（再利用リスト内で到達または進行する）まで、累積性能指数の指数関数的減衰を延期できるように、正確に最後に更新された時刻を維持する必要があります。

config block pointer

構成ブロックポインター

Any implementation that supports multiple parameter sets must provide a means of quickly identifying which set of parameters corresponds to the route currently being considered. For implementations supporting only parameter sets where all routes must be treated the same, this pointer is not required.

複数のパラメーターセットをサポートする実装は、現在検討中のルートに対応するパラメーターのセットをすばやく識別する手段を提供する必要があります。すべてのルートを同じように処理する必要があるパラメーターセットのみをサポートする実装の場合、このポインターは必要ありません。

reuse list traversal pointers

リスト走査ポインタを再利用する

If doubly linked lists are used to implement reuse lists, then two pointers will be needed, previous and next. Generally there is a double linked list which is unused when a route is suppressed from use that can be used for reuse list traversal eliminating the need for additional pointer storage.

二重リンクリストを使用して再利用リストを実装する場合、前と次の2つのポインタが必要になります。一般に、再利用リストトラバーサルに使用できるルートの使用が抑制されている場合に使用されない二重リンクリストがあり、追加のポインターストレージの必要性がなくなります。

4.5 Processing Configuration Parameters

4.5 構成パラメータの処理

From the configuration parameters, it is possible to precompute a 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 figure-of-merit can attain, referred to here as the ceiling. The real number value of the ceiling will typically be determined by the following equation. The ceiling can also be configured to a specific value, which in turn dictates T-hold.

スケーリングは通常、性能指数が達成できる最高値（ここでは上限と呼ばれます）に依存しています。天井の実数値は、通常、次の式で決定されます。シーリングは特定の値に設定することもでき、それがTホールドを決定します。

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

In the above equation, reuse is the reuse threshhold described in Section 4.2.

上記の式で、再利用はセクション4.2で説明した再利用のしきい値です。

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 integer arithmetic are left up to the individual implementations.

スケーリングされた整数演算の方法については、ここでは詳しく説明しません。実際の値を決定する方法が示されています。スケーリングされた整数値への変換とスケーリングされた整数演算の詳細は、個々の実装に任されています。

The ceiling value can be set to be the largest integer that can fit in half the bits available for an unsigned integer. This will allow 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.

上限値は、符号なし整数に使用できるビットの半分に収まる最大の整数に設定できます。これにより、スケーリングされた整数にスケーリングされた減衰値を乗算してから、下にシフトできます。実装は、実数を使用することを好むかもしれませんし、それらのアーキテクチャに適切であると思われる整数スケーリングを使用するかもしれません。

penalty value and thresholds (as proportional scaled integers)

ペナルティ値としきい値（比例スケーリングされた整数として）

The figure of merit penalty for one route withdrawal and the cutoff values must be scaled according to the above scaling factor.

1つのルートの撤回とカットオフ値のメリットフィギュアペナルティは、上記のスケーリングファクターに従ってスケーリングする必要があります。

decay rate per tick (decay[1])

ティックごとの減衰率（decay [1]）

The decay value per increment of time as defined by the time granularity must be determined (at least initially as a floating point number). The per tick decay is a number slightly less than one. It is the Nth root of the one half where N is the half life divided by the time granularity.

時間の細分性によって定義される時間の増分ごとの減衰値を決定する必要があります（少なくとも最初は浮動小数点数として）。ティックごとの減衰は、1をわずかに下回る数値です。これは、1/2のN乗根で、Nは半減期を時間粒度で割ったものです。

          decay[1] = exp ((1 / (decay-half-life/delta-t)) * log (1/2))

decay array size (decay-array-size)

減衰配列サイズ（decay-array-size）

The decay array size is the decay memory divided by the time granularity. If integer truncation brings the value of an array element to zero, the array can be made smaller. An implementation should also impose a maximum reasonable array size or allow more than one multiplication.

減衰配列サイズは、減衰メモリを時間粒度で割ったものです。整数の切り捨てにより配列要素の値がゼロになる場合は、配列を小さくすることができます。実装はまた、最大の妥当な配列サイズを課すか、複数の乗算を許可する必要があります。

                       decay-array-size = (Tmax/delta-t)

decay array (decay[])

減衰配列（decay []）

Each i-th element of the decay array is the per tick delay raised to the i-th power. This might be best done by successive floating point multiplies followed by scaling and integer rounding or truncation. The array itself need only be computed at startup.

減衰配列の各i番目の要素は、ティックごとの遅延をi乗したものです。これは、連続する浮動小数点乗算と、それに続くスケーリングと整数の丸めまたは切り捨てによって最適に行われる可能性があります。配列自体は起動時にのみ計算する必要があります。

                            decay[i] = decay[1] ** i

4.6 Building the Reuse Index Arrays

4.6 再利用インデックス配列の作成

The reuse lists may be accessed quite frequently if a lot of routes are flapping sufficiently to be suppressed. A method of speeding the determination of which reuse list to use for a given route is suggested. This method is introduced in Section 4.2, its configuration described in Section 4.4.2 and the algorithms described in Section 4.8.6 and Section 4.8.7. This section describes building

多くのルートが抑制されるのに十分なフラッピングをしている場合、再利用リストに非常に頻繁にアクセスできます。特定のルートに使用する再利用リストの決定を高速化する方法が提案されています。このメソッドはセクション4.2で導入され、その構成はセクション4.4.2で説明され、アルゴリズムはセクション4.8.6とセクション4.8.7で説明されています。このセクションでは、ビルドについて説明します

the reuse list index arrays.

再利用リストのインデックス配列。

A ratio of the figure of merit of the route under consideration to the cutoff value is used as the basis for an array lookup. The ratio is scaled and truncated to an integer and used to index the array. The array entry is an integer used to determine which reuse list to use.

検討中のルートの性能指数とカットオフ値の比が、配列ルックアップの基礎として使用されます。比率は整数にスケーリングおよび切り捨てられ、配列のインデックス付けに使用されます。配列エントリは、使用する再利用リストを決定するために使用される整数です。

reuse array maximum ratio (max-ratio)

配列の最大比率を再利用（max-ratio）

This is the maximum ratio between the current value of the stability figure of merit and the target reuse value that can be indexed by the reuse array. It may be limited by the ceiling imposed by the maximum hold time or by the amount of time that the reuse lists cover.

これは、安定性の性能指数の現在の値と、再利用配列によってインデックスを付けることができる目標再利用値の間の最大比率です。これは、最大保持時間によって課せられる上限、または再利用リストがカバーする時間の長さによって制限される場合があります。

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

reuse array scale factor ( scale-factor )

配列のスケール係数を再利用（スケール係数）

Since the reuse array is an estimator, the reuse array scale factor has to be computed such that the full size of the reuse array is used.

再利用配列は推定量であるため、再利用配列のフルサイズが使用されるように、再利用配列のスケール係数を計算する必要があります。

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

reuse index array (reuse-index-array[])

インデックス配列を再利用（reuse-index-array []）

Each reuse index array entry should contain an index into the reuse list array pointing to one of the list heads. This index should corresponding to the reuse list that will be evaluated just after a route would be eligible for reuse given the ratio of current value of the stability figure of merit to target reuse value corresponding the the reuse array entry.

各再利用インデックス配列エントリには、リストヘッドの1つを指す再利用リスト配列へのインデックスが含まれている必要があります。このインデックスは、再利用配列エントリに対応する目標再利用値に対する安定性性能指数の現在の値の比率を考えると、ルートが再利用に適格になった直後に評価される再利用リストに対応する必要があります。

          reuse-index-array[j] = integer((decay-half-life / reuse-
       time-granularity) * log(1/(reuse * (1 + (j / scale-factor)))) /
       log(1/2))

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 index into the reuse index array (reuse-index-array[]). The value fetched from the reuse index array (reuse-index-array[]) is an index into the array of reuse lists (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.

抑制されているルートを配置する再利用キューを決定するには、次の手順を使用します。現在の性能指数をカットオフで割ります。 1を減算します。スケール係数を掛けます。これは、再利用インデックス配列（reuse-index-array []）へのインデックスです。再利用インデックス配列（reuse-index-array []）からフェッチされた値は、再利用リストの配列（reuse-array []）へのインデックスです。このインデックスが配列の末尾から外れている場合は、最後のキューを使用します。それ以外の場合は配列を調べ、そのインデックスにある配列からキューの番号を選択します。これは非常に高速で、必要なセットアップとストレージに十分に値します。

4.7 A Sample Configuration

4.7 サンプル構成

A simple example is presented here in which the space overhead is estimated for a set of configuration parameters. The design here assumes:

ここでは、一連の構成パラメーターについてスペースのオーバーヘッドを見積もる簡単な例を示します。ここでの設計は、以下を前提としています。

1. there is a single parameter set used for all routes,

1. すべてのルートに使用される単一のパラメータセットがあり、

2. decay time for unreachable routes is slower than for reachable routes

2. 到達不可能なルートの減衰時間は到達可能なルートよりも遅い

3. the arrays must be full size, rather than allow more than one multiply per decay operation to reduce the array size.

3. 配列は、配列サイズを縮小するために、減衰操作ごとに複数の乗算を許可するのではなく、フルサイズでなければなりません。

This example is used in later sections. The use of multiple parameter sets complicates the examples somewhat. Where multiple parameter sets are allowed for a single route, the decay portion of the algorithm is repeated for each parameter set. If different routes are allowed to have different parameter sets, the routes must have pointers to the parameter sets to keep the time to locate to a minimum, but the algorithms are otherwise unchanged.

この例は、後のセクションで使用されます。複数のパラメーターセットを使用すると、例が多少複雑になります。単一のルートに複数のパラメーターセットが許可されている場合、アルゴリズムの減衰部分が各パラメーターセットに対して繰り返されます。異なるルートが異なるパラメーターセットを持つことを許可されている場合、ルートは、検索する時間を最小限に抑えるためにパラメーターセットへのポインターを持っている必要がありますが、そうでなければアルゴリズムは変更されません。

A sample set of configuration parameters and a sample set of implementation parameters are provided in in the two following lists.

構成パラメーターのサンプルセットと実装パラメーターのサンプルセットを、次の2つのリストに示します。

1. Configuration Parameters

1. 構成パラメータ

o cut = 1.25

o カット= 1.25

o reuse = 0.5

o 再利用= 0.5

o T-hold = 15 mins

o Tホールド= 15分

o decay-ok = 5 min

o 減衰OK = 5分

o decay-ng = 15 min

o 減衰ng = 15分

o Tmax-ok, Tmax-ng = 15, 30 mins

o Tmax-ok、Tmax-ng = 15、30分

2. Implementation Parameters

2. 実装パラメーター

o delta-t = 1 sec

o delta-t = 1秒

o delta-reuse = 15 sec o reuse-list-size = 256

oデルタ再利用= 15秒o再利用リストサイズ= 256

o reuse-index-array-size = 1,024

o 再利用インデックス配列サイズ= 1,024

Using these configuration and implementation parameters and the equations in Section 4.5, the space overhead can be computed. There is a fixed space overhead that is independent of the number of routes. There is a space requirement associated with a stable route. There is a larger space requirement associated with an unstable route. The space requirements for the parameters above are provide in the lists below.

これらの構成パラメータと実装パラメータ、およびセクション4.5の式を使用して、スペースのオーバーヘッドを計算できます。ルートの数に依存しない固定スペースのオーバーヘッドがあります。安定したルートに関連するスペース要件があります。不安定なルートに関連付けられているより大きなスペース要件があります。上記のパラメーターのスペース要件は、以下のリストに記載されています。

1. fixed overhead (using parameters from previous example)

1. 固定オーバーヘッド（前の例のパラメーターを使用）

o 900 * integer - decay array

o 900 *整数-減衰配列

o 1,800 * integer - decay array

o 1,800 *整数-減衰配列

o 120 * pointer - reuse list-heads

o 120 *ポインタ-リストヘッドを再利用する

o 2,048 * integer - reuse index arrays

o 2,048 *整数-インデックス配列を再利用

2. overhead per stable route

2. 安定したルートあたりのオーバーヘッド

o pointer - containing null entry

o ポインタ-nullエントリを含む

3. overhead per unstable route

3. 不安定なルートごとのオーバーヘッド

o pointer - to a damping structure containing the following

o ポインタ-以下を含む減衰構造へ

o integer - figure of merit + bit for state

o 整数-性能指数+状態のビット

o integer - last time updated

o 整数-最終更新日時

o 2 * pointer - reuse list pointers (prev, next)

o 2 *ポインタ-リストポインタを再利用します（前、次）

The decay arrays are sized acording to delta-t and Tmax-ok or Tmax-ng. The number of reuse list-heads is based on delta-reuse and the greater of Tmax-ok or Tmax-ng. There are two reuse index arrays whose size is a configured parameter.

減衰配列は、delta-tおよびTmax-okまたはTmax-ngに従ってサイズが決定されます。再利用リストヘッドの数は、デルタ再利用と、Tmax-okまたはTmax-ngの大きい方に基づいています。サイズが構成されたパラメーターである2つの再利用インデックス配列があります。

Figure 3 shows the behavior of the algorithm with the parameters given above. Four cases are given in this example. In all four, there is a twelve minute period of route oscillations. Two periods of oscillation are used, 2 minutes and 4 minutes. Two duty cycles are used, one in which the route is reachable during 20% of the cycle and the other where the route is reachable during 80% of the cycle. In all four cases, the route becomes suppressed after it becomes unreachable the second time. Once suppressed, it remains suppressed until some period after becoming stable. The routes which oscillate over a 4 minute period are no longer suppressed within 9-11 minutes after becoming stable. The routes with a 2 minute period of oscillation are suppressed for nearly the maximum 15 minute period after becoming stable.

図3は、上記のパラメーターを使用したアルゴリズムの動作を示しています。この例では、4つのケースが示されています。 4つすべてで、12分のルート振動があります。 2分間と4分間の2つの振動周期が使用されます。 2つのデューティサイクルが使用されます。1つはサイクルの20％の間にルートに到達可能で、もう1つはサイクルの80％の間にルートに到達可能です。 4つのケースすべてで、2回目に到達できなくなった後、ルートは抑制されます。抑制されると、安定してからしばらくの間抑制されたままです。 4分間にわたって振動するルートは、安定してから9〜11分以内に抑制されなくなりました。 2分の振動周期を持つルートは、安定してから最大で15分のほぼ間抑制されます。

4.8 Processing Routing Protocol Activity

4.8 ルーティングプロトコルアクティビティの処理

The prior sections concentrate on configuration parameters and their relationship to the parameters and arrays used at run time and provide the algorithms for initializing run time storage. This section provides the steps taken in processing routing events and timer events when running.

前のセクションでは、構成パラメーターと、実行時に使用されるパラメーターおよび配列との関係に焦点を当て、実行時のストレージを初期化するためのアルゴリズムを提供しました。このセクションでは、実行時にルーティングイベントとタイマーイベントを処理する手順を説明します。

The routing events are:

ルーティングイベントは次のとおりです。

1. A BGP peer or new route comes up for the first time (or after an extended down time) (Section 4.8.1)

1. BGPピアまたは新しいルートが初めて（または長時間のダウン時間後に）起動する（セクション4.8.1）

2. A route becomes unreachable (Section 4.8.2)

2. ルートが到達不能になる（セクション4.8.2）

3. A route becomes reachable again (Section 4.8.3)

3. ルートが再び到達可能になります（セクション4.8.3）

4. A route changes (Section 4.8.4)

4. ルート変更（セクション4.8.4）

5. A peer goes down (Section 4.8.5)

5. ピアがダウンする（セクション4.8.5）

time figure-of-merit as a function of time (in minutes)

時間の関数としての時間の性能指数（分単位）

0.00 0.000 . 0.000 . 0.000 . 0.000 . 0.62 0.000 . 0.000 . 0.000 . 0.000 . 1.25 0.000 . 0.000 . 0.000 . 0.000 . 1.88 0.000 . 0.000 . 0.000 . 0.000 . 2.50 0.977 . 0.968 . 0.000 . 0.000 . 3.12 0.949 . 0.888 . 0.000 . 0.000 . 3.75 0.910 . 0.814 . 0.000 . 0.000 . 4.37 1.846 . 1.756 . 0.983 . 0.983 . 5.00 1.794 . 1.614 . 0.955 . 0.935 . 5.63 1.735 . 1.480 . 0.928 . 0.858 . 6.25 2.619 . 2.379 . 0.901 . 0.786 . 6.88 2.544 . 2.207 . 0.876 . 0.721 . 7.50 2.472 . 2.024 . 0.825 . 0.661 . 8.13 3.308 . 2.875 . 1.761 . 1.608 . 8.75 3.213 . 2.698 . 1.711 . 1.562 . 9.38 3.122 . 2.474 . 1.662 . 1.436 . 10.00 3.922 . 3.273 . 1.615 . 1.317 . 10.63 3.810 . 3.107 . 1.569 . 1.207 . 11.25 3.702 . 2.849 . 1.513 . 1.107 . 11.88 3.498 . 2.613 . 1.388 . 1.015 . 12.50 3.904 . 3.451 . 2.312 . 1.953 . 13.13 3.580 . 3.164 . 2.120 . 1.791 . 13.75 3.283 . 2.902 . 1.944 . 1.643 . 14.38 3.010 . 2.661 . 1.783 . 1.506 . 15.00 2.761 . 2.440 . 1.635 . 1.381 . 15.63 2.532 . 2.238 . 1.499 . 1.267 . 16.25 2.321 . 2.052 . 1.375 . 1.161 . 16.88 2.129 . 1.882 . 1.261 . 1.065 . 17.50 1.952 . 1.725 . 1.156 . 0.977 . 18.12 1.790 . 1.582 . 1.060 . 0.896 . 18.75 1.641 . 1.451 . 0.972 . 0.821 . 19.38 1.505 . 1.331 . 0.891 . 0.753 . 20.00 1.380 . 1.220 . 0.817 . 0.691 . 20.62 1.266 . 1.119 . 0.750 . 0.633 . 21.25 1.161 . 1.026 . 0.687 . 0.581 . 21.87 1.064 . 0.941 . 0.630 . 0.533 . 22.50 0.976 . 0.863 . 0.578 . 0.488 . 23.12 0.895 . 0.791 . 0.530 . 0.448 . 23.75 0.821 . 0.725 . 0.486 . 0.411 . 24.37 0.753 . 0.665 . 0.446 . 0.377 . 25.00 0.690 . 0.610 . 0.409 . 0.345 .

Figure 3: Some fairly long route flap cycles, repeated for 12 minutes, followed by a period of stability.

図3：12分間繰り返されるかなり長いルートフラップサイクルと、その後の安定期間。

The reuse list is used to provide a means of fast evaluation of route that had been suppressed, but had been stable long enough to be reused again or had been suppressed long enough that it can be treated as a new route. The following two operations are described.

再利用リストは、抑制されたルートを迅速に評価する手段を提供するために使用されますが、再利用できるほど長く安定しているか、新しいルートとして処理できるほど長く抑制されていました。次の2つの操作について説明します。

1. Inserting into a reuse list (Section 4.8.6)

1. 再利用リストへの挿入（セクション4.8.6）

2. Reuse list processing every delta-t seconds (Section 4.8.7)

2. delta-t秒ごとにリスト処理を再利用します（セクション4.8.7）。

4.8.1 Processing a New Peer or New Routes

4.8.1 新しいピアまたは新しいルートの処理

When a peer comes up, no action is required if the routes had no previous history of instability, for example if this is the first time the peer is coming up and announcing these routes. For each route, the pointer to the damping structure would be zeroed and route used. The same action is taken for a new route or a route that has been down long enough that the figure of merit reached zero and the damping structure was deleted.

ピアが起動したときに、ルートに以前の不安定性の履歴がない場合、たとえばこれが初めてピアが起動してこれらのルートをアナウンスする場合など、アクションは必要ありません。ルートごとに、減衰構造へのポインタがゼロになり、ルートが使用されます。新しいルート、または性能指数がゼロになり、ダンピング構造が削除されるのに十分な時間が経過したルートについても、同じアクションが実行されます。

4.8.2 Processing Unreachable Messages

4.8.2 到達不能メッセージの処理

When a route is withdrawn or changed (Section 4.8.4 describes how a change is handled), the following procedure is used.

ルートが撤回または変更された場合（セクション4.8.4は、変更の処理方法を説明しています）、次の手順を使用します。

If there is no previous stability history (the damping structure pointer is zero), then:

以前の安定性履歴がない場合（減衰構造ポインターがゼロ）、次のようになります。

1. allocate a damping structure

1. 減衰構造を割り当てる

2. set figure-of-merit = 1

2. 性能指数= 1に設定

3. withdraw the route

3. ルートを撤回する

Otherwise, if there is an existing damping structure, then:

それ以外の場合、既存の減衰構造がある場合は、次のようになります。

1. set t-diff = t-now - t-updated

1. set t-diff = t-now-t-updated

2. if (t-diff puts you off the end of the array) {

2. if（t-diffが配列の最後から離れる）{

setfigure-of-merit =1

setfigure-of-merit = 1

}else {

}そうしないと {

      setfigure-of-merit =figure-of-merit *decay-array-ok [t-diff ]+ 1

      if(figure-of-merit >ceiling) {

setfigure-of-merit =ceiling

setfigure-of-merit = ceiling

}

｝

}

｝

3. remove the route from a reuse list if it is on one

3. 再利用リストにある場合は、そのルートを再利用リストから削除します

4. withdraw the route unless it is already suppressed

4. すでに抑制されていない限り、ルートを撤回する

In either case then:

どちらの場合でも：

1. set t-updated = t-now

1. t-updated = t-nowを設定します

2. insert into a reuse list (see Section 4.8.6)

2. 再利用リストに挿入（セクション4.8.6を参照）

If there was a stability history, the previous value of the stability figure of merit is decayed. This is done using the decay array (decay-array). The index is determined by subtracting the current time and the last time updated, then dividing by the time granularity. If the index is zero, the figure of merit is unchanged (no decay). If it is greater than the array size, it is zeroed. Otherwise use the index to fetch a decay array element and multiply the figure of merit by the array element. If using the suggested scaled integer method, shift down half an integer. Add the scaled penalty for one more unreachable (shown above as 1). If the result is above the ceiling replace it with the ceiling value. Now update the last time updated field (preferably taking into account how much time was truncated before doing the decay calculation).

安定性の履歴があった場合、安定性の性能指数の以前の値は減衰します。これは、減衰配列（decay-array）を使用して行われます。インデックスは、現在の時刻と最後に更新された時刻を差し引いてから、時間の粒度で割ることによって決定されます。インデックスがゼロの場合、性能指数は変化しません（減衰なし）。配列サイズより大きい場合は、ゼロに設定されます。それ以外の場合は、インデックスを使用して減衰配列要素をフェッチし、性能指数に配列要素を掛けます。推奨されるスケーリングされた整数法を使用する場合は、整数の半分だけシフトダウンします。到達不能な1つ以上のスケーリングされたペナルティを追加します（上記の1として示されています）。結果が上限を超えている場合は、上限値に置き換えます。次に、最後に更新されたフィールドを更新します（できれば、減衰計算を行う前に切り捨てられた時間を考慮に入れてください）。

When a route becomes unreachable, alternate paths must be considered. This process is complicated slightly if different configuration parameters are used in the presence or absence of viable alternate paths. If all of these alternate paths have been suppressed because there had previously been an alternate route and the new route withdrawal changes that condition, the suppressed alternate paths must be reevaluated. They should be reevaluated in order of normal route preference. When one of these alternate routes is encountered that had been suppressed but is now usable since there is no alternate route, no further routes need to be reevaluated. This only applies if routes are given two different reuse thresholds, one for use when there is an alternate path and a higher threshold to use when suppressing the route would result in making the destination completely unreachable.

ルートが到達不能になった場合、代替パスを検討する必要があります。実行可能な代替パスがある場合とない場合に異なる構成パラメーターを使用する場合、このプロセスは少し複雑になります。以前に代替ルートがあったためにこれらのすべての代替パスが抑制されており、新しいルートの撤回によってその状態が変化した場合、抑制された代替パスを再評価する必要があります。それらは、通常のルート優先の順序で再評価する必要があります。これらの代替ルートの1つが検出されたが抑制されていたが、代替ルートがないために現在使用可能である場合、それ以上のルートを再評価する必要はありません。これは、ルートに2つの異なる再利用しきい値が与えられている場合にのみ適用されます。1つは代替パスがある場合に使用し、もう1つはルートを抑制して宛先を完全に到達不能にする場合に使用するしきい値です。

4.8.3 Processing Route Advertisements

4.8.3 ルートアドバタイズの処理

When a route is readvertised if there is no damping structure, then the procedure is the same as in Section 4.8.1.

制振構造がない場合にルートが再度アドバタイズされる場合、手順はセクション4.8.1と同じです。

1. don't create a new damping structure

1. 新しい減衰構造を作成しないでください

2. use the route

2. ルートを使う

If an damping structure exists, the figure of merit is decayed and the figure of merit and last time updated fields are updated. A decision is now made as to whether the route can be used immediately or needs to be suppressed for some period of time.

減衰構造が存在する場合、性能指数は減衰し、性能指数と最終更新フィールドが更新されます。これで、ルートをすぐに使用できるか、または一定期間抑制する必要があるかが決定されます。

1. set t-diff = t-now - t-updated

1. set t-diff = t-now-t-updated

2. if (t-diff puts you off the end of the array) {

2. if（t-diffが配列の最後から離れる）{

set figure-of-merit =0

性能指数= 0に設定

}else {

}そうしないと {

set figure-of-merit= figure-of-merit* decay-array-ng[t-diff]

set figure-of-merit = figure-of-merit * decay-array-ng [t-diff]

}

｝

3. if ( not suppressed and figure-of-merit < cut ) {

3. if（抑制されず、性能指数<カット）{

use the route

ルートを使う

         }else if( suppressed and figure-of-merit< reuse) {

set state tonot suppressed

状態を抑制しないに設定

remove the route from a reuse list

再利用リストからルートを削除する

use the route

ルートを使う

}else {

}そうしないと {

set state to suppressed

状態を抑制に設定

don't use the route

ルートを使用しないでください

insert into a reuse list (see Section 4.8.6)

再利用リストに挿入（セクション4.8.6を参照）

}

｝

4. if ( figure-of-merit > 0 ) {

4. if（性能指数> 0）{

set t-updated= t-now

t-updated = t-nowを設定

}else {

}そうしないと {

recover memory for damping struct

構造体を減衰させるためにメモリを回復する

zero pointer to damping struct

減衰構造体へのゼロポインター

}

｝

If the route is deemed usable, a search for the current best route must be made. The newly reachable route is then evaluated according to the BGP protocol rules for route selection.

ルートが使用可能であると思われる場合、現在の最適ルートの検索を行う必要があります。次に、新たに到達可能なルートは、ルート選択のためのBGPプロトコルルールに従って評価されます。

If the new route is usable, the previous best route is examined. Prior to route comparisons, the current best route may have to be reevaluated if separate parameter sets are used depending on the presence or absence of an alternate route. If there had been no alternate the previous best route may be suppressed.

新しいルートが使用可能な場合、以前の最適ルートが調べられます。ルート比較の前に、代替ルートの有無に応じて個別のパラメーターセットが使用されている場合、現在の最適ルートを再評価する必要があります。代替ルートがなかった場合、以前の最適ルートが抑制される可能性があります。

If the new route is to be suppressed it is placed on a reuse list only if it would have been preferred to the current best route had the new route been accepted as stable. There is no reason to queue a route on a reuse list if after the route becomes usable it would not be used anyway due to the existence of a more preferred route. Such a route would not have to be reevaluated unless the preferred route became unreachable. As specified here, the less preferred route would be reevaluated and potentially used or potentially added to a reuse list when processing the withdrawal of a more preferred best route.

新しいルートが抑制される場合、新しいルートが安定として受け入れられた場合、現在の最適ルートよりも優先された場合にのみ、再利用リストに配置されます。ルートが使用可能になった後、より優先されるルートが存在するためにルートが使用されない場合、そのルートを再利用リストにキューイングする理由はありません。このようなルートは、優先ルートに到達できなくなった場合を除き、再評価する必要はありません。ここで指定されているように、優先度の低いルートは再評価され、潜在的に使用されるか、優先度の高いルートの撤回を処理するときに再利用リストに追加される可能性があります。

4.8.4 Processing Route Changes

4.8.4 ルート変更の処理

If a route is replaced by a peer router by supplying a new path, the route that is being replaced should be treated as if an unreachable were received (see Section 4.8.2). This will occur when a peer somewhere back in the AS path is continuously switching between two AS paths and that peer is not damping route flap (or applying less damping). There is no way to determine if one AS path is stable and the other is flapping, or if they are both flapping. If the cycle is sufficiently short compared to convergence times neither route through that peer will deliver packets very reliably. Since there is no way to affect the peer such that it chooses the stable of the two AS paths, the only viable option is to penalize both routes by considering each change as an unreachable followed by a route advertisement.

ルートが新しいパスを提供することによってピアルーターに置き換えられた場合、置き換えられているルートは、到達不能を受信したかのように扱われる必要があります（セクション4.8.2を参照）。これは、ASパスのどこかにあるピアが2つのASパス間を継続的に切り替えており、そのピアがルートフラップを減衰していない（または減衰をあまり適用していない）場合に発生します。 1つのASパスが安定していて、もう一方がフラッピングしているかどうか、または両方がフラッピングしているかどうかを判別する方法はありません。コンバージェンス時間と比較してサイクルが十分に短い場合、そのピアを経由するどちらのルートもパケットを非常に確実に配信しません。 2つのASパスの安定を選択するようにピアに影響を与える方法はないため、唯一の実行可能なオプションは、各変更を到達不能と見なしてルートアドバタイズメントを実行することにより、両方のルートにペナルティを課すことです。

4.8.5 Processing A Peer Router Loss

4.8.5 ピアルーターの損失の処理

When a peer routing session is broken, either all individual routes advertised by that peer may be marked as unstable, or the peering session itself may be marked as unstable. Marking the peer will save considerable memory. Since the individual routes are advertised as unreachable to routers beyond the immediate problem, per route state will be incurred beyond the peer immediately adjacent to the BGP session that went down. If the instability continues, the immediately adjacent router need only keep track of the peer stability history. The routers beyond that point will receive no further advertisements or withdrawal of routes and will dispose of the damping structure over time.

ピアルーティングセッションが切断されると、そのピアによってアドバタイズされたすべての個々のルートが不安定とマークされるか、ピアリングセッション自体が不安定とマークされることがあります。ピアをマークすると、メモリを大幅に節約できます。個々のルートは当面の問題を超えてルーターに到達できないとアドバタイズされるため、ルートごとの状態は、ダウンしたBGPセッションに直接隣接するピアを越えて発生します。不安定性が続く場合、直接隣接するルーターは、ピアの安定性の履歴を追跡するだけで済みます。そのポイントを超えるルーターは、それ以上のアドバタイズまたはルートの撤回を受信せず、減衰構造を時間の経過とともに破棄します。

BGP notification through an optional transitive attribute that damping will already be applied may be considered in the future to reduce the number of routers that incur damping structure storage overhead.

オプションの推移属性によるダンピングがすでに適用されているというBGP通知は、ダンピング構造のストレージオーバーヘッドが発生するルーターの数を減らすために、将来的に検討される可能性があります。

4.8.6 Inserting into the Reuse Timer List

4.8.6 再利用タイマーリストへの挿入

The reuse lists are used to provide a means of fast evaluation of route that had been suppressed, but had been stable long enough to be reused again. The data structure consists of a series of list heads. Each list contains a set of routes that are scheduled for reevaluation at approximately the same time. The set of reuse list heads are treated as a circular array. Refer to Figure 4.

再利用リストは、抑制されていたが、再利用できるほど長期間安定していたルートを迅速に評価する手段を提供するために使用されます。データ構造は一連のリストヘッドで構成されます。各リストには、ほぼ同時に再評価がスケジュールされている一連のルートが含まれています。再利用リストヘッドのセットは、循環配列として扱われます。図4を参照してください。

A simple implementation of the circular array of list heads would be an array containing the list heads. An offset is used when accessing the array. The offset would identify the first list. The Nth list would be at the index corresponding to N plus the offset modulo the number of list heads. This design will be assumed in the examples that follow.

リストヘッドの循環配列の単純な実装は、リストヘッドを含む配列になります。オフセットは、配列にアクセスするときに使用されます。オフセットは最初のリストを識別します。 N番目のリストは、Nに対応するインデックスと、リストヘッドの数を法とするオフセットにあります。この設計は、以下の例で想定されています。

A key requirement is to be able to insert an entry in the most appropriate queue with a minimum of computation. The computation is given only the current value of figure-of-merit. Instead of a computation which would involve a logarithm, the reuse array (reuse-array[]) described in Section 4.6 is used. The array, scale, and bounds are precomputed to map figure-of-merit to the nearest list head without requiring a logarithm to be computed (see Section 4.5).

重要な要件は、最小限の計算で最も適切なキューにエントリを挿入できることです。計算には、性能指数の現在の値のみが与えられます。対数を伴う計算の代わりに、セクション4.6で説明されている再利用配列（reuse-array []）が使用されます。配列、スケール、および境界は、対数の計算を必要とせずに性能指数を最も近いリストヘッドにマップするために事前計算されます（セクション4.5を参照）。

       +-+    +-+    +-+          non-empty linked list means
       | |    | |    | |     <--  that there are routes with
       +-+    +-+    +-+          defered action to be taken
        ^      ^      ^           N * delta-reuse seconds later.
        |      |      |
     +------+------+------+------+------+      +------+
     | list | list | list | list | list |  ... | list |
     | head | head | head | head | head |  ... | head |
     +------+------+------+------+------+      +------+
        ^      ^      ^      ^      ^             ^
       Nth    1st    2nd    3rd    4th           N-1
               |
       offset to first list
       (the offset is incremented every delta-reuse seconds)

Figure 4: Reuse List Data Structures

図4：リストデータ構造の再利用

Note that in the following sections the operator prefix notation "modulo a b" means "b % a" in C language algebraic operator notation. For example, "modulo 16 1023" would be 15.

以下のセクションでは、演算子の接頭表記「modulo a b」は、C言語の代数演算子表記の「b％a」を意味することに注意してください。たとえば、「モジュロ16 1023」は15になります。

1. scale figure-of-merit for the index array lookup producing index

1. インデックス配列ルックアップを生成するインデックスのスケール性能指数

2. check index against the array bound

2. バインドされた配列に対してインデックスをチェックします

3. if (within the array bound) {

3. if（配列の境界内）{

set index =reuse-array [index ]

set index = reuse-array [index]

}else {

}そうしないと {

set index =reuse-list-size -1

set index = reuse-list-size -1

}

｝

4. insert into the list

4. リストに挿入する

reuse-list[ moduloreuse-list-size (index +offset )]

再利用リスト[moduloreuse-list-size（index + offset）]

Choosing the correct reuse list involves only a multiply and shift to do the scaling, an integer truncation, then an array lookup in the reuse array (reuse-array[]). The value retrieved from the reuse array is used to select a reuse list. The reuse list is a circular list. The most common method of implementing a circular list is to use an array and apply an offset and modulo operation to pick the correct array entry. The offset is incremented to rotate the circular list.

正しい再利用リストを選択するには、乗算とシフトだけでスケーリングを行い、整数の切り捨てを行った後、再利用配列（reuse-array []）で配列を検索します。再利用配列から取得した値は、再利用リストを選択するために使用されます。再利用リストは循環リストです。循環リストを実装する最も一般的な方法は、配列を使用し、オフセットとモジュロ演算を適用して正しい配列エントリを選択することです。オフセットは、循環リストを回転させるために増分されます。

4.8.7 Handling Reuse Timer Events

4.8.7 再利用タイマーイベントの処理

The granularity of the reuse timer should be more coarse than that of the decay timer. As a result, when the reuse timer fires, suppressed routes should be decayed by multiple increments of decay time. Some computation can be avoided by always inserting into the reuse list corresponding to one time increment past reuse eligibility. In cases where the reuse lists have a longer "memory" than the "decay memory" (described above), all of the routes in the first queue will be available for immediate reuse if reachable or the history entry could be disposed of if unreachable.

再利用タイマーの粒度は、減衰タイマーの粒度よりも粗くする必要があります。その結果、再利用タイマーが作動すると、抑制されたルートは、減衰時間の複数の増分によって減衰する必要があります。一部の計算は、過去の再利用適格性の1回の増分に対応する再利用リストに常に挿入することで回避できます。再利用リストの「メモリ」が「減衰メモリ」（上記）よりも長い場合、最初のキューのすべてのルートは、到達可能であればすぐに再利用でき、到達不可能であれば履歴エントリを破棄できます。

When it is time to advance the lists, the first queue on the reuse list must be processed and the circular queue must be rotated. Using an array and an offset as a circular array (as described in Section 4.8.6), the algorithm below is repeated every delta-reuse seconds.

リストを進めるときは、再利用リストの最初のキューを処理し、循環キューをローテーションする必要があります。配列とオフセットを循環配列として使用して（セクション4.8.6で説明）、以下のアルゴリズムがデルタ再利用の秒ごとに繰り返されます。

1. save a pointer to the current zeroth queue head and zero the list head entry

1. 現在のゼロ番目のキューヘッドへのポインタを保存し、リストヘッドエントリをゼロにする

2. set offset = modulo reuse-list-size ( offset + 1 ), thereby rotating the circular queue of list-heads

2. セットオフセット=モジュロ再利用リストサイズ（オフセット+ 1）、それによってリストヘッドの循環キューを回転

3. if ( the saved list head pointer is non-empty )

3. if（保存されたリストのヘッドポインターが空ではない）

for each entry {

各エントリに対して{

sett-diff =t-now -t-updated

sett-diff = t-now -t-updated

set figure-of-merit =figure-of-merit *decay-array-ok [t-diff ]

set figure-of-merit = figure-of-merit * decay-array-ok [t-diff]

sett-updated =t-now

sett-updated = t-now

if( figure-of-merit< reuse)

if（性能指数<再利用）

reuse the route

ルートを再利用する

else

そうしないと

re-insert into another list (seeSection 4.8.6)

別のリストに再挿入する（セクション4.8.6を参照）

}

｝

The value of the zeroth list head would be saved and the array entry itself zeroed. The list heads would then be advanced by incrementing the offset. Starting with the saved head of the old zeroth list, each route would be reevaluated and used, disposed of entirely or requeued if it were not ready for reuse. If a route is used, it must be treated as if it were a new route advertisement as described in Section 4.8.3.

0番目のリストヘッドの値が保存され、配列エントリ自体がゼロ化されます。次に、オフセットをインクリメントしてリストの先頭を進めます。古いゼロ番目のリストの保存された先頭から始めて、各ルートは再評価されて使用されるか、完全に破棄されるか、再利用の準備ができていなければ再キューイングされます。ルートを使用する場合は、4.8.3項で説明するように、新しいルートアドバタイズであるかのように処理する必要があります。

5 Implementation Experience

5実装経験

The first implementations of "route flap damping" were the route server daemon (rsd) coding by Ramesh Govindan (ISI) and the Cisco IOS implementation by Ravi Chandra. Both implementations first became available in 1995 and have been used extensively. The rsd implementation has been in use in route servers at the NSF funded Network Access Points (NAPs) and at other major Internet interconnects. The Cisco IOS version has been in use by Internet Service Providers worldwide. The rsd implementation has been integrated in releases of gated (see http://www.gated.org) and is available in commercial routers using gated.

「ルートフラップダンピング」の最初の実装は、Ramesh Govindan（ISI）によるルートサーバーデーモン（rsd）のコーディングと、Ravi ChandraによるCisco IOSの実装でした。どちらの実装も1995年に利用可能になり、広く使用されています。 rsdの実装は、NSFが資金を提供するネットワークアクセスポイント（NAP）やその他の主要なインターネット相互接続のルートサーバーで使用されています。 Cisco IOSバージョンは、世界中のインターネットサービスプロバイダーによって使用されています。 rsd実装は、gatedのリリース（http://www.gated.orgを参照）に統合されており、gatedを使用する市販のルーターで利用できます。

There are now more than 2 years of BGP route damping deployment experience. Some problems have occurred in deployment. So far these are solvable by careful implementation of the algorithm and by careful deployment. In some topologies coordinated deployment can be helpful and in all cases disclosure of the use of route damping and the parameters used is highly beneficial in debugging connectivity problems.

現在、BGPルートダンピング展開の経験は2年以上あります。デプロイメントでいくつかの問題が発生しました。これまでのところ、これらはアルゴリズムの注意深い実装と注意深い配備によって解決可能です。トポロジによっては、調整された展開が役立つ場合があり、すべての場合において、ルートダンピングの使用と使用されるパラメーターの開示は、接続の問題のデバッグに非常に役立ちます。

Some of the problems have occurred due to subtle implementation errors. Route damping should never be applied on IBGP learned routes. To do so can open the possibility for persistent route loops. When IBGP routes within an AS are inconsistent, route loops can easily form. Suppressing IBGP learned routes causes such inconsistencies. Implementations should disallow configuration of route damping on IBGP peers.

いくつかの問題は、微妙な実装エラーが原因で発生しています。ルートダンピングは、IBGPで学習されたルートには適用しないでください。そうすることで、永続的なルートループの可能性が開かれます。 AS内のIBGPルートに一貫性がない場合、ルートループが簡単に形成される可能性があります。 IBGPで学習されたルートを抑制すると、このような不整合が発生します。実装では、IBGPピアでのルートダンピングの構成を禁止する必要があります。

Penalties for instability should only be applied when a route is removed or replaced and not when a route is added. If damping parameters are applied consistently, this implementation constraint will result in a stable secondary path being preferred over an unstable primary path due to damping of the primary path near the source.

不安定性に対するペナルティは、ルートが削除または置換されたときにのみ適用され、ルートが追加されたときは適用されません。減衰パラメーターが一貫して適用される場合、この実装の制約により、ソース付近のプライマリパスの減衰により、安定したセカンダリパスが不安定なプライマリパスよりも優先されます。

In topologies where multiple AS paths to a given destination exist flapping of the primary path can result in suppression of the secondary path. This can occur if no damping is being done near the cause of the route flap or if damping is being applied more aggressively by a distant AS. This problem can be solved in one of two ways. Damping can be done near the source of the route flap and the damping parameters can be made consistent. Alternately, a distant AS which insists on more aggressive damping parameters can disable penalizing routes on AS path change, penalizing routes only if they are withdrawn completely. In order to do so, the implementation must support this option (as described in Section 4.4.3).

特定の宛先への複数のASパスが存在するトポロジでは、プライマリパスのフラッピングにより、セカンダリパスが抑制される可能性があります。これは、ルートフラップの原因の近くでダンピングが行われていない場合、または遠くのASによってダンピングがより積極的に適用されている場合に発生する可能性があります。この問題は、2つの方法のいずれかで解決できます。ルートフラップの発生源の近くでダンピングを行うことができ、ダンピングパラメータを一貫させることができます。あるいは、より積極的なダンピングパラメータを要求する遠くのASは、ASパスの変更時にペナルティルートを無効にし、ルートが完全に撤回された場合にのみペナルティを課すことができます。そのためには、実装でこのオプションをサポートする必要があります（セクション4.4.3を参照）。

Route flap should be damped near the source. Single homed destinations can be covered by static routes. Aggregation provides another means of damping. Providers should damp their own internal problems, however damping on IGP link state origination is not yet implemented by router vendors. Providers which use multiple AS within their own topology should damp between their own AS. Providers should damp adjacent providers AS.

ルートフラップは、発生源の近くで減衰させる必要があります。シングルホームの宛先は静的ルートでカバーできます。集約は、減衰の別の手段を提供します。プロバイダーは独自の内部問題を緩和する必要がありますが、IGPリンク状態の発生の抑制はまだルーターベンダーによって実装されていません。独自のトポロジ内で複数のASを使用するプロバイダーは、独自のAS間でダンプする必要があります。プロバイダーは、隣接するプロバイダーのASをダンプする必要があります。

Damping provides a means to limit propagation excessive route change when connectivity is highly intermittent. Once a problem is corrected, damping state corresponding to the prefixes known to be damped due to the problem just fixed can be manually cleared. In order to determine where damping may have occurred after connectivity problems, providers should publish their damping parameters. Providers should be willing to manually clear damping on specific prefixes or AS paths at the request of other providers when the request is accompanied by credible assurance that the problem has truly been addressed.

ダンピングは、接続が非常に断続的であるときに、過度のルート変更の伝播を制限する手段を提供します。問題が修正されると、修正されたばかりの問題によって減衰されることがわかっている接頭辞に対応する減衰状態を手動でクリアできます。接続の問題の後にダンピングが発生した可能性がある場所を特定するために、プロバイダーはダンピングパラメーターを公開する必要があります。プロバイダーは、問題が本当に対処されたという信頼できる保証が要求に伴う場合、他のプロバイダーの要求で特定のプレフィックスまたはASパスのダンピングを手動でクリアする必要があります。

By damping their own routing information, providers can reduce their own need to make requests of other providers to clear damping state after correcting a problem. Providers should be pro-active and monitor what prefixes and paths are suppressed in addition to monitoring link states and BGP session state.

プロバイダーは独自のルーティング情報をダンピングすることにより、問題を修正した後にダンピング状態をクリアするよう他のプロバイダーに要求する必要性を減らすことができます。プロバイダーはプロアクティブであり、リンク状態とBGPセッション状態の監視に加えて、抑制されるプレフィックスとパスを監視する必要があります。

Acknowledgements

謝辞

This work and this document may not have been completed without the advise, comments and encouragement of Yakov Rekhter (Cisco). Dennis Ferguson (MCI) provided a description of the algorithms in the gated BGP implementation and many valuable comments and insights. David Bolen (ANS) and Jordan Becker (ANS) provided valuable comments, particularly regarding early simulations. Over four years elapsed between the initial draft presented to the BGP WG (October 1993) and this iteration. At the time of this writing there is significant experience with two implementations, each having been deployed since 1995. One was led by Ramesh Govindan (ISI) for the NSF Routing Arbiter project. The second was led by Ravi Chandra (Cisco). Sean Doran (Sprintlink) and Serpil Bayraktar (ANS) were among the early independent testers of the Cisco pre-beta implementation. Valuable 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.

この作業とこのドキュメントは、Yakov Rekhter（Cisco）の助言、コメント、および励ましがなければ完成しなかった可能性があります。 Dennis Ferguson（MCI）は、ゲーテッドBGP実装のアルゴリズムの説明と、多くの貴重なコメントと洞察を提供しました。 David Bolen（ANS）とJordan Becker（ANS）は、特に初期のシミュレーションに関して貴重なコメントを提供しました。 BGP WG（1993年10月）に提示された最初のドラフトとこの反復の間には4年以上が経過しました。これを書いている時点では、2つの実装でかなりの経験があり、それぞれが1995年以降に展開されています。1つはNSF Routing ArbiterプロジェクトのRamesh Govindan（ISI）が率いました。 2つ目はRavi Chandra（Cisco）が主導しました。 Sean Doran（Sprintlink）とSerpil Bayraktar（ANS）は、シスコプレベータ実装の初期の独立テスターの1人でした。貴重なコメントと実装フィードバックは、IETF IDR WGとRIPEルーティングワークグループ、およびNANOGとIEPGで多くの個人によって共有されました。

Thanks also to Rob Coltun (Fore Systems), Sanjay Wadhwa (Fore), John Scudder (IENG), Eric Bennet (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. Thanks also to Vern Paxson for a very thorough review resulting in numerous clarifications to the document.

最近の実装のコーディング中に明らかになった数学のエラーを指摘してくれたRob Coltun（Fore Systems）、Sanjay Wadhwa（Fore）、John Scudder（IENG）、Eric Bennet（IENG）、およびJayesh Bhatt（Bay Networks）にも感謝します。これらのエラーは、最初の2つの実装が完了した後に書かれた実装提案セクションの詳細に表示されました。非常に徹底的なレビューを行った結果、ドキュメントが数多く明確化されたVern Paxsonにも感謝します。

References

参考文献

[1] Gross, P., and Y. Rekhter, "Application of the border gateway protocol in the internet", RFC 1268, October 1991.

[1] Gross、P。、およびY. Rekhter、「インターネットにおける境界ゲートウェイプロトコルの適用」、RFC 1268、1991年10月。

[2] ISO/IEC. Iso/iec 10747 - information technology - telecommuni-cations and information exchange between systems - protocol for exchange of inter-domain routeing information among intermediate systems to support forwarding of iso 8473 pdus. Technical report, International Organization for Standardization, August 1994. ftp://merit.edu/pub/iso/idrp.ps.gz.

[2] ISO / IEC。 ISO / IEC 10747-情報技術-システム間の通信と情報交換-中間システム間でドメイン間ルーティング情報を交換して、ISO 8473 PDUの転送をサポートするためのプロトコル。テクニカルレポート、国際標準化機構、1994年8月。ftp：//merit.edu/pub/iso/idrp.ps.gz。

[3] Lougheed, K., and Y. Rekhter, "A border gateway protocol 3 (BGP-3)", RFC 1267, October 1991.

[3] Lougheed、K。、およびY. Rekhter、「A Border Gateway Protocol 3（BGP-3）」、RFC 1267、1991年10月。

[4] Rekhter, Y., and P. Gross, "Application of the border gateway protocol in the internet", RFC 1772, March 1995.

[4] Rekhter、Y。、およびP. Gross、「インターネットでの境界ゲートウェイプロトコルの適用」、RFC 1772、1995年3月。

[5] Rekhter, Y., and T. Li, "A border gateway protocol 4 (BGP-4)", RFC 1771, March 1995.

[5] Rekhter、Y。、およびT. Li、「A Border Gateway Protocol 4（BGP-4）」、RFC 1771、1995年3月。

[6] Rekhter, Y., and C. Topolcic,"Exchanging routing information across provider boundaries in the CIDR environment", RFC 1520, September 1993.

[6] Rekhter、Y。、およびC. Topolcic、「CIDR環境でプロバイダーの境界を越えてルーティング情報を交換する」、RFC 1520、1993年9月。

[7] Traina, P., "BGP-4 protocol analysis", RFC 1774, March 1995.

[7] Traina、P。、「BGP-4プロトコル分析」、RFC 1774、1995年3月。

[8] Traina, P., "Experience with the BGP-4 protocol", RFC 1773, March 1995.

[8] Traina、P。、「BGP-4プロトコルの経験」、RFC 1773、1995年3月。

Security Considerations

セキュリティに関する考慮事項

The practices outlined in this document do not further weaken the security of the routing protocols. Denial of service is possible in an already insecure routing environment but these practices only contribute to the persistence of such attacks and do not impact the methods of prevention and the methods of determining the source.

このドキュメントで概説されているプラクティスは、ルーティングプロトコルのセキュリティをさらに弱めることはありません。すでに安全ではないルーティング環境ではサービス拒否が発生する可能性がありますが、これらの方法はそのような攻撃の持続に寄与するだけであり、防止方法やソースの決定方法には影響しません。

Authors' Addresses

著者のアドレス

Curtis Villamizar ANS

カーティス・ビジャミザールANS

   EMail: curtis@ans.net

Ravi Chandra Cisco Systems

   EMail: rchandra@cisco.com

Ramesh Govindan ISI

ラメシュゴビンダンISI

   EMail: govindan@isi.edu

Full Copyright Statement

完全な著作権表示

This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.

このドキュメントとその翻訳はコピーして他のユーザーに提供することができ、コメントまたはその他の方法で説明したり、その実装を支援する二次的著作物は、いかなる種類の制限なしに、全体または一部を準備、コピー、公開、および配布することができますただし、上記の著作権表示とこの段落は、そのようなすべてのコピーと派生物に含まれています。ただし、このドキュメント自体は、著作権に関する通知を削除したり、インターネットソサエティや他のインターネット組織への参照を削除したりするなど、いかなる方法でも変更できません。ただし、インターネット標準を開発する目的で必要な場合は除きます。インターネット標準のプロセスに従うか、または必要に応じて、それを英語以外の言語に翻訳する必要があります。

The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.

上記で付与された制限付きのアクセス許可は永続的であり、インターネットソサエティまたはその後継者または譲受人によって取り消されることはありません。

This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

このドキュメントとここに含まれる情報は「現状有姿」で提供され、インターネット社会およびインターネット技術タスクフォースは、明示または黙示を問わず、ここに記載されている情報の使用が保証するものに限定されないいかなる保証も含め、一切の保証を否認します。商品性または特定の目的への適合性に関する権利または黙示の保証を侵害すること。