この文書はRFC2439の日本語訳（和訳）です。 この文書の翻訳内容の正確さは保障できないため、 正確な知識や情報を求める方は原文を参照してください。 翻訳者はこの文書によって読者が被り得る如何なる損害の責任をも負いません。 この翻訳内容に誤りがある場合、訂正版の公開や、 誤りの指摘は適切です。 この文書の配布は元のＲＦＣ同様に無制限です。
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
ＢＧＰ経路バタつき防止
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.
この文書はインターネット共同体のためのインターネット標準化作業中のプ
ロトコルを指定して、そして改良のために議論と提案を求めます。標準化状
態とこのプロトコル状態は「インターネット公式プロトコル標準」（ＳＴＤ
１）の現在の版を参照してください。このメモの配布は無制限です。
Copyright Notice
著作権表示
Copyright (C) The Internet Society (1998). All Rights Reserved.
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.
ルーティングピアに渡すルーティングトラフィックを減少できる、それ故に
比較的安定した経路の経路収束時間に負の影響を与えずにピアの負荷を減少
できる、ＢＧＰルーティングプロトコルの使用法が記述されます。この技術
はＢＧＰをサポートする商用製品に実装されました。技術は同じくＩＤＲＰ
に適用できます。
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:
これはＢＧＰの他の目的を念頭において達成されるに違いありません：
o pack changes into a small number of updates
o 変更をまとめ、更新を少ないくする。
o preserve consistent routing
o 一貫した経路維持。
o minimal addition space and computational overhead
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".
インターネットプレフィックスの一部の可到達性広告の極端な数の更新がイ
ンターネットで広範囲にあります。これはインターネットオペレーションな
どに関係している多くの人々によって１９９０年代初期に観察されました。
これらの極端な更新の発生は必ずしも周期的ではなく、それで経路振動は紛
らわしい用語であるでしょう。この効果を記述するために使われた非公式の
用語は「経路バタつき」です。ここで記述された技術はは現在広範囲に動作
し、一般に「経路バタつき防止」と述べられます。
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.
インターネットルーティングのスケーラビリティを持続するために、ＣＰＵ
処理の要求条件を制限するため、ＢＧＰで配布するルーティング状態の変化
の量を減らすことは必要です。ＢＧＰ更新の結果として生じる処理負荷の主
要な者はＢＧＰ決定プロセスと転送項の追加削除です。
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.
次の例を考えてください。広く配置されたＢＧＰ実装は高いルーティング更
新量のために失敗する傾向があるかもしれません。例えば、もしＢＧＰかＩ
ＧＰセッションの負荷が重いなら、セッションを維持できないかもしれませ
ん。１つのルータの障害は他のルータにさらに負荷を増やします。この追加
の負荷は、同様の問題のため、同じ又は異なる実装で障害を起こすかもしれ
ません。最悪の場合、結果的に振動が生じます。このような最悪の場合は実
際は観察されました。
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.
ＢＧＰ実装が大量のルーティングトラフィックに対する用意ができているに
違いありません。ＢＧＰ実装は送信者が十分に経路不安定性を保護してくれ
る事を当てにできません。ここのガイドラインは受けた振動を妨げるよう意
図されますが、強靭で効率的な実装の必要を排除しません。ここで記述され
たメカニズムは不安定に隣接するＡＳ境界ルータで、ルーティング不安定性
を落ち着かせることを可能にします。
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.
ＢＧＰ実装が十分に強靭であっても、ルーティングプロセスの処理能力は限
定されています。不必要な変更の配布を制限することは、ルーティングトポ
ロジが成長するにつれて、合理的な経路変化収束時間を持続する際に問題に
なります。
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.
経路広告の頻度を制御する２つの方法がここで記述されます。最初は固定タ
イマを伴います。固定タイマの技術は経路毎の空間的オーバーヘッドを持ち
ませんが、しかし、不安定な経路履歴を持たない標準的な経路の収束を遅く
する欠点を持ちます。２番目の方法はある追加の空間オーバーヘッドを持続
することで、この限界を克服します。追加のオーバーヘッドは経路毎の小さ
な状態と、非常に小さい処理オーバーヘッドを含みます。
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].
両方の技術を結合することは可能で、そして望ましいです。実際、固定タイ
マは小さな時間間隔に設定され、経路更新が別に到着する時に更新の頻度を
減らす事に有用と分かりました。ＢＧＰプロトコルはこれをネットワーク層
可到達性情報（ＮＬＲＩ）[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.
ＢＧＰ３がこのエリアで特定の推薦をしません[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.
ＢＧＰ４が「経路広告の頻度」章を維持し、そして「回路生成の頻度」章を
加えます。ＢＧＰ−４が（構成可能な）固定最小経路広告間隔タイマと固定
最小ＡＳ生成間隔タイマ[5]で制限する経路広告方法を記述します。最小経路
広告間隔の推薦されたタイマ値は３０秒で、最小ＡＳ生成間隔は１５秒です。
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.
経路が不安定である場合に、経路の使用と広告は撤去を抑圧するのではなく、
抑制されるべきです。宛先への１つの経路が安定し、他の同じ宛先への経路
が幾分不安定である場合、もし可能であるなら、不安定な経路は代替パスが
ない場合より積極的に抑制されるべきです。
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.
ＡＳ内で整合した経路を決めることは非常に重要です。内部ＢＧＰ（ＩＢＧ
Ｐ）の非常に小さい遅延だけがされるべきです。ＡＳ境界線を越えての経路
の整合性も非常に重要です。短い時間を除き、使われている経路と異なる経
路を広告することは大いに望ましくありません。ただ再配布だけを抑制する
より、経路の受け入れ（それ故にＩＧＰでの経路の使用）を抑制することは
より望ましいです。
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.
経路が受け入れられた後、それらの再広告は更新をまとめるのを改善するた
めに簡単に抑制されるでしょう。外部経路の受け入れの長い抑制があるかも
しれません。経路が抑制される気管は、経路の将来の不安定性の可能性に関
する予測の数字に基づいています。高い数値を持つ経路が抑制されるでしょ
う。指数減衰アルゴリズムが時間が経つと数字を減らす方法として選択され
ました。これらの選択は実装への提案だと見なされるべきです。
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.
この特性は現在の値(figure-of-merit)にかかわらずひとつの演算で減衰を計
算できるようにします。性能の最適化として、減衰は固定時間の増加を適用
できます。与えられた望ましい半減期に対し、単位時間の減衰は先に計算す
ることができます。複数時間での減衰は以下に表現されます。
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の値は適当な「ｎ」に対して事前に計算して配列に記憶しておくことが
できます。「K」の値は常に１以下です。配列大きさは、値が急速にゼロに
接近するので、限界があります。これはどのぐらい時間が経過したかに関わ
らず、範囲検査と範囲検索と単一の掛け算で計算する事を容易にします。
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.
この経路広告制限方法は経路を送る処理に用いられた固定タイマの使用を伴
います。この主目的はＢＧＰ更新メッセージでの経路をまとめる事を改善す
ることです。安定した経路広告においての遅延は限界があり、そして最小で
あるべきです。到達不能の広告はゼロである必要はありませんが、同じく限
界があるべきで、そして到達可能広告以下であるべきです。
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.
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.
ＢＧＰプロトコルはルーティング情報ベース（ＲＩＢ）の使用を定義します。
再広告される必要がある経路はＲＩＢでマークされるか、ＲＩＢを参照する
外部構造体が維持されます。周期的に、マークされた経路の一部が処理され
ます。これはかなり簡単であって、そして目的を達成します。計算は実装に
は簡単で、Ｎの２乗のオーダーです。Ｎの２乗の処理を避けるために、ある
データ構造体の形式が共通属性で経路をグループ化します。
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.
実装が効率的に更新をまとめて、多分最小の再広告遅延を供給して、最大広
告遅延の制限を供給し、これは最小遅延を供給するアルゴリズムの結果とし
て経験されるであろうし、そして多数の再広告の候補があっても計算量的に
効率的でなくてはなりません。
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.
この経路広告を制限する方法は、経路毎の経路安定性の尺度を使用します。
この技術は、外部ピアからの受信（ＲＢＧＰ）で更新をする時だけ、適用さ
れます。ＩＢＧＰで学んだ経路やＩＢＧＰで広告する経路やに経路選択後に
この技術を適用すると、ルーティングループをもたらしえます。
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.
不安定な経路の動作はかなり予測可能です。バタつく経路がしばしば広告さ
れ、そして特定のプロトコル（問題が存在する所のＩＧＰあるいは外部プロ
トコル）の通常のタイマの時間間隔で撤回されるでしょう。限界の回線や軽
い輻輳が、長期パターンで短時間の経路撤回や短時間の接続を発生すること
があります。
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.
異なったる経路が帯域幅が小さいか、輻輳する傾向があるために、大体等価
な経路で異なる閾値を設定するのは望ましいかもしれません、。これはパラ
メータを異なる優先値範囲と結び付けることによって解決できます。パラメー
タ選択はＢＧＰのローカル優先に基くことができます。
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.
不可欠ではないが、経路毎に多数の設定パラメータの設定が可能なことは望
ましいかもしれません。（ＡＳパスやピアルータや特定の宛先や他の手段に
よって識別された）経路の集合に対応するパラメータの設定が可能なことが
同じく望ましいかもしれません。経験によって最も良くパラメータを設定す
るためにどれぐらい柔軟性が必要か、そしてどのようにそうするべきかが指
摘されるかもしれません。異なる経路のために異なる抑制パラメータを許す
べきかどうかと、経路毎に多数のメリットの数値を許すことは実装の選択で
す。
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)
切離し閾値（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)
再利用閾値（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-hold）
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)
到達可能の間の半減期（decay-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)
到達不能な間の半減期（dencay-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.
４.１章に記述されるようにパラメータの多数のセットがあるかもしれません。
下にリストアップされた設定パラメータは広くシステムに適用されるでしょ
う。これらはすべての計算の時間精度と、以前に抑制された経路の再評価を
制御するパラメータを含みます。
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)
再利用リスト時間精度（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)
再利用リスト記憶（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.
これは最後の再利用リストに対応する時間値です。これはすべてのパラ
メータの設定されるかもしれないＴ−ｈｏｌｄの最大値です。
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.
これは再利用リストの数です。それは明示的に再利用リスト最大あるい
はセットから決定されるかもしれません。
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.
推薦された最適化は、「再利用インデックス配列」と言う配列を使い、
４.８.６章で記述されます。再利用インデックス配列がそれぞれの使用中の
減少率に必要とされます。再利用インデックス配列は、経路が鎮圧される時
に、経路にどの再利用リストを使うかを決めるのに使われます。適切な配置
は、周期的に経路を再利用するか記憶場所を開放するかの決定のための減少
評価を避けます。再利用インデックス配列を使うことは配置を決定するため
の対数計算の必要を避けます。１つの追加のシステム広域パラメータが導入
できます。
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.
半減期は扱う事を意図する経路バタつきの期間よりかなり長く設定されるべ
きです。例えば、もし減少が１０分に設定され、そして経路の撤回と再広告
が正確に１０分毎にされるなら、もし打ち切りが２以上に設定されていれば、
バタつきは続くでしょう。
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.
もし上限値で制限されるなら、ぎざぎざのベースラインはより高い率の経路
バタつきで速く上限に届くでしょう。例えば、もし減少率の４倍でバタつく
なら、次の展開が起こります。経路が最初の時到達不可能になる時、値は１
になります。次のバタつきが生じる時、前の値に、２の４乗根を減少し、１
が加算されます（もし減少が指数関数的なら、半減期の１／４の減少がしょ
うじる）。数列は１、１.８４、２.５５、３.１４、３.６４、４.０６、
４.４２、４.７１、４.９６、５.１７、・・・で、およそ６.２８５に集まり
ます。もし経路の減少率の４倍でバタつくなら、それは４サイクルで３、６
サイクルで４、１０サイクルで５、に達し、およそ６.３の一点に集まるでしょ
う。減少時間の２倍において、７サイクルで３に達して、そして３.５以下の
値の一点に集まるでしょう。
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.
図１が一定の割合での経路バタつきのメリットの安定性数字を示します。時
間軸は半減期の倍数を示します。プロットは半減期の１／２と１／３と１／４
と１／８の間隔の経路バタつきを表示します。４．５の限界が設定され、プ
ロットに与えるの３つに影響が見られ、効率的に前の履歴にかかわらず再広
告までの時間を制限します。打切りと再利用の閾値が１．５と０．７５で、
経路は２−３回到達不可能であると宣言された後で抑制され、半減期のおよ
そ２倍の時間で再利用されるでしょう。
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.
この機能は式で表現できます。経路の可到達性が０と１の間の変数「Ｒ」で
示され、到達不可能と到達可能を示します。到達不可能にＲが１の値を持ち
ます。メリットの数字はそれぞれのＲ＝１からＲ＝０までの移行で１増え、
限界値に付きました。メリットの数字の減少は次のように到達不可能で表現
できます。
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.
４つのプロットは垂直に提示します。スペースの限界のため、時間軸に沿っ
て一部の点だけを示します。メリットの数字の値は与えられます。それぞれ
の値はＡＳＣＩＩ点から構成される非常に低い解像度のストリップチャート
です。これはちょうど値の増減の荒っぽい感触を与えるように意図されます。
ストリップチャートは、ぎざぎざの波形がしばしば互いに交差するから、軸
の部分的に重なり合っている所は示されません。これらの非常に低い解像度
のプロットでも、ベースラインの増減は明白です、しかしぎざぎざの性質は
印刷された値で観察するだけです。
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.
最大保持時間値（Ｔ−ｈｏｌｄ）から、上限の再利用値の比率が決定できま
す。上限の整数値はオーバーフローが問題にならなく、そしてすべての他の
値がスケールできるように、選択できます。もし両方の打切りが指定される
なら、あるいはもし多数のパラメータセットが使われるなら、最も高い上限
が使われるでしょう。
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
図１：一定のバタつきでのメリットの不安定性数字
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
図２：到達不可能である時の、別の減少定数
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).
図２が経路が到達可能であるか否かで別の減少率を設定する効果を示します。
減少率は経路が到達不可能である時は、５倍遅いです。示した３つの場合で、
経路バタつきの期間は半減期と等しいですが、しかし経路は１つは１／８の
時間で到達可能、１つは１／２の時間で到達可能、他は７／８のルートは他
で到達可能です。最後の場合、経路は第３の到達不能まで抑制されません
（それが再び到達可能になった後で閾値の上にあるとき）。
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).
図２の主なポイントは固定周波数の方形波に対し、変数「Ｒ」の方形波の任
務サイクルを変える効果を示す事です。もし減少定数が、減少がＲ＝０（経
路が到達不可）の時に遅くなるように選択されるなら、大部分の時間、経路
が到達可能な場合に、図のメリットの数字がよりゆっくりと上昇します（正
確には、ぎざぎざの波形のベースラインがよりゆっくりと上昇する）。経路
が再び到達可能になるときの効果は、もしぎざぎざが上限値によって抑えら
れるなら、まったく無視してよいが、もし遅い経路バタつき率あるいはは短
時間の経路バタつきがのこぎりの歯の上限値に届かないならより重要です。
図２で経路が不安定である間隔は上限値に届かないほど短く、それゆえ、経
路バタつきのサイクルの多くの時間が到達可能な経路は、その後安定化した
経路（「Ｒ」が１になり、広告状態が到達可能になりそこに留まる事を示す）
に比べてすぐに、再利用されます（ＲＩＢに設定され、ピアに広告される。
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).
図１と図２の両方で、経路が抑制されるでしょう。半減期以下の経路バタつ
きは２ないし３回撤回され、それから安定広告になり半減期の１／２から２
と１／２倍の間（例で与えた上限）安定になるまで撤回されたままとなりま
す。
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.
ＢＧＰ経路バタつきを抑制する目的は、そのルータのプロセッサ負荷の減少
と、下流ルータ（ＢＧＰピアルータと中間ルータの経路広告を見るピアのピ
ア）のプロセッサ負荷を減らすことです。それぞれの不連続の時間間隔で、
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.
より大きい時間解像度はテーブルメモリをダウンに保つでしょう。時間解像
度は期待された最悪の場合の経路バタつきの間隔以下の最小の合理的な時間
であるべきです。コンパイル時にパラメータを固定するか、あるいはデフォ
ルトを設定して強くユーザのそのままにすることを勧めることが、合理的で
あるかもしれません。指数の減少で、小さい量を維持するより、減少の合計
がゼロと考えられる完全な安定期間を設定する事で、配列の大きさはとても
小さく出来ます。代わりに、もし配列の限度を越えるなら、非常に長い減少
が何度も掛け算する事で実装できます。
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.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.
もし設定パラメータの多数のセットが経路毎に許されるなら、１つ以上のメ
リットの数と各経路のパラメータのセットを結び付ける手段が必要です。こ
れらのオブジェクトのつながれたリストを構築することは多くの合理的な実
装の１つのように思われます。同様に、再利用リストに経路を関連づける手
段が必要とされます。データ構造体が再利用リストに選択される際に、ポイ
ンタのための小さいオーバーヘッドが実装に必要でしょう。提案する実装は
双方向リンクリストを使用し、それでメリットの数字毎に２つのポインタが
必要です。
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.
それぞれの設定パラメータが減少配列と再利用配列を参照します。これらの
配列は、メモリ条件が少なくないので、パラメータの多数のセットの間で共
有されるべきです。ルータ全体で再利用リストヘッドは１つだけでしょう。
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 打切り値（cut）
o reuse value (reuse)
o 再利用値（reuse）
o figure of merit ceiling (ceiling)
o メリットの数字の上限（ceiling）
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.
それぞれの設定パラメータセットが１つあるいは２つの減少配列と１つある
いは２つの再利用配列を参照するでしょう。もし減少率が経路が到達可能で
ある間と到達不可能な間で同じなら、あるいはもしメリットの安定性数が経
路が到達不可能である間に減少しないなら、ただ１つの配列が必要でしょう。
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.
下記は直接ではなくけれども設定パラメータから計算されます。計算は４.５
章で記述されます。
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-size）
o reuse index array (reuse-index-array[])
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.
減少配列サイズは大きさは時間精度で与えられた指定された減少メモリに十
分な、あるいはもし値が小さければ整数回の手順でゼロになるまでの配列要
素数に十分なサイズ、あるいは実装が極端にメモリを使う設定を妨げる合理
的なサイズを課さなければなりません。実行が配列サイズをより短くして、
メモリを減らすために長い時間隔で減少させる時に増やすことに決めるかも
しれません。
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.
再利用インデックス配列は減少配列と類似の目的を満たします。ＢＧＰで、
経路が最も良い経路と思われるなら、「使われる」と言われます。この文脈
で、もし経路が「使われる」なら、それはＲＩＢに置かれ、そしてＢＧＰピ
アに広告する資格を有します。もし経路が撤回されるなら（ピアからのＢＧ
Ｐ広告が到達可能ではないことを示す）、それはもう「使用」の資格を有し
ません。経路が到達可能になる時、もしメリットの数字が最近の不安定の存
在を示すなら、すぐに「使われない」かもしれません。経路が安定したまま
で、そしてメリットの数字が「再利用」閾値以下に減少した後、経路は「再
利用される」資格があると言われます（本当に到達可能であるとして扱われ、
ＲＩＢに置かれ、ピアに広告されます）。経路が再利用できるまでの時間量
は配列検索を使って決定できます。配列は与えられた減少率の条件下で構築
できます。配列は、現在のメリットの安定性の数と経路の再利用に必要な値
の比率に対応したスケール整数を使用して、インデックスされます。
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).
情報が経路を表すある項組み毎に維持されなくてはなりません。最小限、Ｎ
ＬＲＩ（ＢＧＰプレフィックスと長さ）は項組みに含まなければなりません。
異なるＢＧＰ属性があるいは特定の状態に依存して、含まれたり除外される
かもしれません。ＡＳパスはデフォルトで項組みに含まれるべきです。項組
みは同じくオプションとして多数出口区別（ＭＥＤ）のような他のＢＧＰ属
性を含んでいるかもしれません。
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.
ＡＳパスは安定化されていないあるいは安定化が不十分な経路を識別するの
に使用され、そして安定パスを不安定パスの入れ替えをします。まれな状況
下で、すべてあるいは一部のプレフィックスでＡＳパスを除去することは望
ましいかもしれません。もしＡＳパスがＡＳ集合で終わるなら、実際はパス
は常に集約です。後続するＡＳ集合に対する変更が無視されるべきです。理
想的にはＡＳパスの比較は、あるＡＳが新旧のＡＳ集合にあることを保証す
るべきですが、しかし後のＡＳ集合の中身を完全に無視することは許容でき
ます。
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.
次の転送先とＭＥＤ変更は、内部的に不安定なＡＳの使用を抑制できるか、
隣接ＡＳの不安定なＩＧＰパスに近い次の転送先を避けることができます。
もし多数のＭＥＤ値が使われるなら、状態の量の増加は問題になるかもしれ
ません。この理由でＭＥＤはデフォルトで適用されず、ＭＥＤ値にかかわら
ずひとつの状態項目を使った項組み比較の一部としてだけ適用可能です。Ｍ
ＥＤを含むことは、変更がさらに伝えられる必要がないけれども、隣接した
ＡＳの使用を抑制するでしょう。ＭＥＤを使うことは、もしパスが他のＡＳ
を通って存在すると知っているか、隣接ＡＳにピアサイトが十分あるり経路
がピアサイトの一部で聞かれた経路が抑制されるなら、安全な習慣に過ぎま
せん。
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.
次の情報は経路毎に維持されなくてはなりません。ここの経路が、４.４.３
章で定義されるように、通常ＮＬＲＩと次の転送先とＡＳパスを含んでいる
項組みであると考えられます。
stability figure of merit (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.
もし再利用リストの実装に二重リンクリストが使用されるなら、前へと
後への２つのポインタが必要とされるでしょう。一般に、経路が抑制さ
れているときに使用されていない二重リンクリストがあり、これは再利
用リスト横断に利用でき、追加のポインタメモリを必要としません。
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-holdから決まる特定の値で設定されま
す。
ceiling = reuse * (exp(T-hold/decay-half-life) * log(2))
In the above equation, reuse is the reuse threshhold described
in Section 4.2.
上記の方程式で、reuseは４.２章で記述した再利用閾値です。
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.
１回の経路撤回のメリットの数値の罰則値と、打ち切り値は上記のスケー
ル因子でスケールしなければなりません。
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.
時間解像度と定義される時間増加毎の減少値は決定されなければなりま
せん（少なくとも初めに浮動小数点数として）。チック毎の減少率は１
未満の数です。Ｎを半減期を時間解像度で割ったものとしたときに、こ
れは２分の１のＮ乗根です。
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.
減少配列のそれぞれのｉ番目の要素がチック毎の減少のｉ乗です。これ
は連続した浮動小数点乗算に続くスケール化と整数化でできるかもしれ
ません。配列自身は起動時に計算が必要なだけです。
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
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 )
再利用配列スケール因子（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.
それぞれの再利用インデックス配列項目がリストヘッドの１つを示す再
利用リスト配列の中のインデックスを含むべきです。もしインデックス
が経路が現在のメリットの数字の値の比率から再利用配列項目の目標再
利用値で適格になった直後に評価される再利用リストに対応するべきで
す。
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.
抑制経路を置くためにどの再利用待ち行列を使うかの決定は次の手順が使わ
れます。メリットの現在の数字を切り捨てます。１を引きます。スケール因
子を掛けます。これは再利用インデックス配列（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.
設定パラメータのサンプルセットと、実装パラメータのサンプルが次の２つ
のリストで供給されます。
1. Configuration Parameters
1. 設定パラメータ
o cut = 1.25
o reuse = 0.5
o T-hold = 15 mins
o decay-ok = 5 min
o decay-ng = 15 min
o Tmax-ok, Tmax-ng = 15, 30 mins
2. Implementation Parameters
2. 実装パラメータ
o delta-t = 1 sec
o delta-reuse = 15 sec
o reuse-list-size = 256
o reuse-index-array-size = 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.
これらの設定と実装パラメータと４.５章の式を使って、スペースオーバーヘッ
ドは計算できます。経路数と独立に固定したスペースオーバーヘッドがあり
ます。安定した経路に関連するスペース条件があります。不安定な経路に関
連するより大きいスペース条件があります。上記パラメータのスペース条件
は下のリストで供給されます。
1. fixed overhead (using parameters from previous example)
1. 固定オーバーヘッド（前の例のパラメータを使用）
o 900 * integer - decay array
o 1,800 * integer - decay array
o 120 * pointer - reuse list-heads
o 2,048 * integer - reuse index arrays
2. overhead per stable route
2. 経路毎のオーバーヘッド
o pointer - containing null entry
3. overhead per unstable route
3. 不安定経路毎のオーバーヘッド
o pointer - to a damping structure containing the following
o integer - figure of merit + bit for state
o integer - last time updated
o 2 * pointer - reuse list pointers (prev, next)
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に関連してサイズを定められま
す。再利用リストヘッドの数はdelta-reuseに基づき、そしてTmax-okか
Tmax-ngより大きいです。その大きさが設定パラメータである２つの再利用イ
ンデックス配列があります。
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.
図３は上で与えられたパラメータでのアルゴリズムの動作を示します。４つ
の場合がこの例で与えられます。すべての場合で、経路振動に１２分の周期
があります。２つの振動周期、２分と４分が、使われます。２つの必須サイ
クルが使われ、１つは経路のサイクルのの２０％で到達可能で、他方は経路
のサイクルの８０％で到達可能です。全ての場合で、経路は２度到達不能に
なると抑制されます。一度抑制されると、安定した後のある程度の期間まで
抑制されます。４分以上の周期の振動経路は安定した後の９−１１分後に抑
制が止まります。２分の振動周期を持つ経路は安定した後に最大１５分の間
抑制さられます。
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.
図３：１２分で繰り返されるあるかなり長い経路バタつきサイクルと、
その後の安定期間
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. ＢＧＰピアあるいは新しい経路が初めて（あるいは長い故障後に）
出てくる（４.８.１章）
2. A route becomes unreachable (Section 4.8.2)
2. 経路が到達不可能になりる（４.８.２章）
3. A route becomes reachable again (Section 4.8.3)
3. 経路が再び到達可能になる（４.８.３章）
4. A route changes (Section 4.8.4)
4. 経路が変化する（４.８.４章）
5. A peer goes down (Section 4.8.5)
5. ピアが停止する（４.８.５章）
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.
再利用リストは抑制された経路の速い評価の手段を供給するために使われま
すが、再利用されるのに十分長い間安定していたか、あるいは新しい経路と
して扱えるほど十分長い間抑制された経路を持ちません。次の２つのオペレー
ションが記述されます。
1. Inserting into a reuse list (Section 4.8.6)
1. 再利用リストに挿入（４.８.６章）
2. Reuse list processing every delta-t seconds (Section 4.8.7)
2. 各delta-t秒毎の再利用リスト処理（４.８.７章）
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.
経路が撤回されるか、あるいは変化する時（４.８.４章はどのように変更を
処理するかを記述）は、次の手順は使われます。
If there is no previous stability history (the damping structure
pointer is zero), then:
もし、前の安定性履歴がないなら（抑制構造体ポインタがゼロなら）：
1. allocate a damping structure
抑制構造体を割り当て
2. set figure-of-merit = 1
3. withdraw the route
経路を撤去
Otherwise, if there is an existing damping structure, then:
さもなければ、もし既存の抑制構造体があるなら：
1. set t-diff = t-now - t-updated
2. if (t-diff puts you off the end of the array) {
t-diffが配列の終りを超える
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
}
}
3. remove the route from a reuse list if it is on one
もしあれば再利用リストから経路を除く
4. withdraw the route unless it is already suppressed
すでに抑制されている場合を除き、経路を撤去
In either case then:
どちらの場合でも：
1. set t-updated = t-now
2. insert into a reuse list (see Section 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）を使って計算します。インデックスは
現在時間から最終更新時間を引いて、時間解像度で割って決定します。もし
インデックスがゼロであるなら、メリットの数字は変化していません（減少
なし）。もしそれが配列サイズより大きいなら、ゼロにします。そうでなけ
れば減少配列要素を取るためにインデックスを使い、そして配列要素によっ
てメリットの数字を増やします。もし提案されたスケール調整整数を使うな
ら、整数に半分切り捨ててください。到達不能に対して、スケールされたペ
ナルティを加算します（上記１参照）。もし結果が上限に達するなら、上限
値と取り替えます。最終更新フィールドを更新します（なるべく減少計算を
する前にどれぐらいの時間が切り捨てられたかを考慮します）。
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.
経路が到達不可能になる時、代替パスが考慮されなくてはなりません。もし
実行可能な代替パスの存在や欠如で異なる設定パラメータが使われるなら、
このプロセスはわずかに複雑です。もし代替経路が前にあり新しい経路撤去
がその状態を変えたためこれらの代替パスのすべてが抑制されるなら、抑制
された代替パスは再評価されなくてはなりません。それらは標準的な経路優
先順序で再評価されるべきです。これらの抑制された代替経路の１つに遭遇
する時、代わりの経路がないく他の経路の再評価が出来ないので、現在有用
です。これは、もし経路に２つの異なる再利用閾値があり、一方は代替パス
と経路の抑制が宛先の到達不能を変化させない時に使用する高い閾値がある
ときに使用される場合に、適用されるだけです。
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.
経路が広告されるとき、もし抑制構造体がないなら、手順は４.８.１章と同
じです。
1. don't create a new damping structure
新しい抑制構造体を作りません。
2. use the route
経路を使用します。
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
2. if (t-diff puts you off the end of the array) {
t-diffが配列の終りを超える
set figure-of-merit =0
}else {
set figure-of-merit= figure-of-merit* decay-array-ng[t-diff]
}
3. if ( not suppressed and figure-of-merit < cut ) {
抑制されてなくて
use the route
経路を使用
}else if( suppressed and figure-of-merit< reuse) {
抑制されていて
set state to not 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. if ( figure-of-merit > 0 ) {
set 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.
もし経路が有用であるとみなされるなら、現在の最良経路の捜索がされなく
てはなりません。新たに到達可能な経路は経路選択のためのＢＧＰプロトコ
ル規則に従って評価されます。
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.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 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.
抑制がすでに適用されたという任意の通過の属性を渡すＢＧＰ通知は、抑制
構造体メモリを持つルータの数を減らすと、将来考えられるかもしれません。
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.
再利用リストは抑制されてるが再び再利用されるのに十分長い間安定してい
た経路の速い評価の手段を供給するために使われます。データ構造はリスト
ヘッダからの列で成り立ちます。それぞれのリストがおよそ同じ時刻に再評
価が予定される経路を含んでいます。リストヘッダの集合は円形配列として
扱われます。図４を参照してください。
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.
リストヘッダの円形配列の単純な実装は、リストヘッダを含む配列です。配
列にアクセスするときオフセットが使われます。オフセットは最初のリスト
を識別するでしょう。Ｎ番目のリストはＮ足すオフセットをリストヘッダの
数で割った余りです。このデザインは次の例で考えられるでしょう。
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).
鍵となる必要条件は最小限の計算で項目を最も適切な列に挿入することが可
能なことです。計算はメリットの数字の現在の値でだけを与えられます。対
数を巻き込む計算の代わりに、４.６章で記述する再利用配列を使います。
配列とスケールと限界は、対数に計算なしでメリットの数字を最も近いリス
トヘッダに対応付けるため、事前に計算します（４.５章参照）。
+-+ +-+ +-+ non-empty linked list means
| | | | | | <-- that there are routes with
+-+ +-+ +-+ defered action to be taken
^ ^ ^ N * delta-reuse seconds later.
| | | 空でないリンクリストは、
| | | Ｎ×delta-reuse秒後に行う動作が
| | | ある経路がある事を意味します。
+------+------+------+------+------+ +------+
| 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)
最初のリストへのオフセット。
（オフセットは毎delta-reuse秒毎に増加します）
Figure 4: Reuse List Data Structures
図４：再利用リストデータ構造体
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」はＣ言語の演算表記で「b % a」
を意味します。例えば、「modulo 16 1023」は１５です。
1. scale figure-of-merit for the index array lookup producing
index
メリットの数値をインデックス配列検索生成インデックスに調整
2. check index against the array bound
インデックス配列範囲内か検査
3. if (within the array bound) {
配列範囲内
set index =reuse-array [index ]
}else {
set index =reuse-list-size -1
}
4. insert into the list
リストに挿入
reuse-list[ 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.
再利用タイマの解像度は減少タイマより荒くなるべきです。結果として、再
利用タイマがタイムアウトする時、抑制経路が多数の減少時間によって減少
させられるべきです。ある計算で、過去の再利用の時間が経つ毎に常に再利
用リストに入れることを避けることができます。再利用リストが「減少メモ
リ」より長い「メモリ」を持つ場合（上記）、もし到達可能か、もし到達不
能なら歴史的項目が処分できるなら、最初の待ち行列の中の全ての経路が直
接再利用に利用可能です。
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.
リストを進める時間になる時、再利用リストの最初の列が処理されなくては
なりません、そして円形列は回転されなくてはなりません。（４.８.６章で
記述された）円形配列の配列とオフセット計算を使用して、下記のアルゴリ
ズムがdelta-reuse秒毎に繰り返されます。
1. save a pointer to the current zeroth queue head and zero the
list head entry
現在のゼロ番目のキューヘッダのポインタを保存し、リストヘッダ項
目をゼロにします。
2. set offset = modulo reuse-list-size ( offset + 1 ), thereby
rotating the circular queue of list-heads
これによりリストヘッダの円形配列を回転させます。
3. if ( the saved list head pointer is non-empty )
保存されたリストヘッダポインタが空でなければ
for each entry {
sett-diff =t-now -t-updated
set figure-of-merit =figure-of-merit *decay-array-ok [t-diff ]
sett-updated =t-now
if( figure-of-merit< reuse)
reuse the route
経路を再利用
else
re-insert into another list (see Section 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.
ゼロ番目のリストヘッドの値は保存されされるでしょう、そして配列項目自
身はゼロにされます。リストヘッドはオフセットを増加する事で進むでしょ
う。古いゼロ番目のリストの先頭から始めて、それぞれの経路が再評価され
そして使われて、再利用に適していなければ処分されるか再度待ち行列に入
れられるでしょう。もし経路が使われるなら、４.８.３章で記述されるよう
に、新しい経路広告であるかのように、扱われなくてはなりません。
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実装でした。
両方の実装が１９９５年に最初に利用可能になり、そして広範囲に使われま
した。rsd実装はＮＳＦが資金を供給したネットワークアクセスポイント（Ｎ
ＡＰ）と他の主要なインターネット相互接続の経路サーバで使用中です。
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.
２年以上のＢＧＰ経路抑制の利用経験があります。ある問題が起こりました。
これまでのところこれらはアルゴリズムの注意深い実装と注意深い利用によっ
て解決可能です。あるトポロジーで調和した配置は助けになり得ます、そし
て例外なく経路抑制の使用と使われたパラメータの公表は接続性問題を解決
する際に大いに有益です。
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.
ある問題が微妙な実装誤りで起こりました。経路抑制は決してＩＢＧＰで学
んだ経路上に適用されないべきです。適用すると経路ループの可能性を生じ
ます。ＡＳ内のＩＢＧＰ経路が整合しないとき、経路ループが容易にできる
ます。ＩＢＧＰで学んだ経路を抑制することはこのような矛盾を起こします。
実装がＩＢＧＰピアの経路の抑制の設定を拒絶するべきです。
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).
ある宛先への多数のＡＳパスがが存在するトポロジーで、第１パスのバタつ
きは第２パスの抑圧をもたらすことができます。これは、もし抑制が経路バ
タつきの原因の近くでされるか、あるいはもし抑制が遠いＡＳでより積極的
に適用されているなら、起こることができます。この問題は２つの方法の１
つで解くことができます。抑制を経路バタつきの原因の近くで行い、そして
抑制パラメータを整合する事です。代わりに、より攻撃的な抑制を要求する
遠いＡＳが、ＡＳパス変更の経路ペナルティを止める、経路が完全に撤去さ
れるときだけペナルティを与える事ができます。そうするためには実装がこ
の選択をサポートしなくてはなりません（４.４.３章で記述されるように）。
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.
経路バタつきが発生源の近くで抑制されるべきです。シングルホームの宛先
は静的経路で対応できます。集約はもう１つの抑制手段を供給します。ＩＧ
Ｐリンク状態発生の抑制はまだルータベンダが実装していないが、プロバイ
ダが自分自身の問題を抑制しすべきです。トポロジで多数のＡＳを使用する
プロバイダは、自ＡＳ間で抑制をすべきです。プロバイダが隣接したプロバ
イダＡＳを抑制すべき。
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.
抑制は、接続性が断続的である時に、極端な経路変化の送信を制限する力を
用意します。問題が修正されるると、修正された問題により抑制されたプレ
フィックスに対応する抑制状態は手作業で許可できます。接続問題の発生時
にどこで抑制が生じたかを決定するため、プロバイダが抑制パラメータを公
開するべきです。他のプロバイダの問題が解決したとの保障を伴う要請によっ
て、プロバイダは手作業で特定のプレフィックスあるいはＡＳパスの抑制を
解除したいと思うかもしれません。
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.
彼ら自身の経路情報を抑制する事で、問題修正後に抑制状態を消す事で、プ
ロバイダが他のプロバイダからの要請を減らす事が出来ます。プロバイダは
リンク状態とＢＧＰセッション状態のモニタの他に、どのプレフィックスや
パスが抑制されているかの事前モニタをするべきです。
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)はgatedＢＧＰ実装のアルゴリズ
ムと多くの貴重なコメントと洞察の記述を供給しました。David Bolen (ANS)
とJordan Becker (ANS) は、特に初期シミュレーションで貴重なコメントを
供給しました。ＢＧＰ作業グループへの最初のドラフト提出（１９９３年
１０月）からこの繰り返しまで４年以上が経過しました。この著作時に２つ
の実装に重要な経験かあります、それぞれが１９９５年から配置されました。
１つ目はＮＳＦルーティング決定者プロジェクトのRamesh Govindan (ISI)に
よって導かれました。２つ目はRavi Chandra (Cisco)によって指揮されまし
た。Sean Doran (Sprintlink)とSerpil Bayraktar (ANS)はCiscoのベータ前
実装の初期独立テスタでした。貴重なコメントと実装フィードバックが、
IETF IDR WGとRIPE Routing Work GroupとIEPGのNANOGの多くの個人によって
共有されました。
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)に感謝します。これらの誤りは、最初
の２つの実装の完了後に書かれた実装の示唆の章の詳細に存在しました。文
書の多数の明確化をもたらした非常に徹底的な批評に対しVern Paxsonに感謝
します。
References
参考文献
[1] Gross, P., and Y. Rekhter, "Application of the border gateway
protocol in the internet", RFC 1268, October 1991.
[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.
[3] Lougheed, K., and Y. Rekhter, "A border gateway protocol 3 (BGP-
3)", RFC 1267, October 1991.
[4] Rekhter, Y., and P. Gross, "Application of the border gateway
protocol in the internet", RFC 1772, March 1995.
[5] Rekhter, Y., and T. Li, "A border gateway protocol 4 (BGP-4)",
RFC 1771, March 1995.
[6] Rekhter, Y., and C. Topolcic,"Exchanging routing information
across provider boundaries in the CIDR environment", RFC 1520,
September 1993.
[7] Traina, P., "BGP-4 protocol analysis", RFC 1774, March 1995.
[8] Traina, P., "Experience with the BGP-4 protocol", RFC 1773, March
1995.
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
EMail: curtis@ans.net
Ravi Chandra
Cisco Systems
EMail: rchandra@cisco.com
Ramesh Govindan
ISI
EMail: govindan@isi.edu
Full Copyright Statement
著作権表示全文
Copyright (C) The Internet Society (1998). All Rights Reserved.
著作権（Ｃ）インターネット学会（２００１）。すべての権利は保留される。
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.
この文書とここに含む情報は無保証で供給され、そしてインターネット学会
とインターネット技術標準化タスクフォースは、特別にも暗黙にも、この情
報の利用が権利を侵害しないことや商業利用や特別の目的への利用に適当で
ある事の保障を含め、すべての保証を拒否します。