[要約] RFC 4829は、MPLSトラフィックエンジニアリングのためのラベルスイッチパス（LSP）の優先度設定ポリシーに関するものです。このRFCの目的は、ネットワークのリソース効率を向上させるために、LSPの優先度設定に関するガイドラインを提供することです。
Network Working Group J. de Oliveira, Ed.
Request for Comments: 4829 Drexel University
Category: Informational JP. Vasseur, Ed.
Cisco Systems, Inc.
L. Chen
Verizon Laboratories
C. Scoglio
Kansas State University
April 2007
Label Switched Path (LSP) Preemption Policies for MPLS Traffic Engineering
MPLSトラフィックエンジニアリングのラベルスイッチ付きパス（LSP）先制ポリシー
Status of This Memo
本文書の位置付け
This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
このメモは、インターネットコミュニティに情報を提供します。いかなる種類のインターネット標準を指定しません。このメモの配布は無制限です。
Copyright Notice
著作権表示
Copyright (C) The IETF Trust (2007).
著作権（c）The IETF Trust（2007）。
IESG Note
IESGノート
This RFC is not a candidate for any level of Internet Standard. The IETF disclaims any knowledge of the fitness of this RFC for any purpose and, in particular, notes that the decision to publish is not based on IETF review for such things as security, congestion control, or inappropriate interaction with deployed protocols. The RFC Editor has chosen to publish this document at its discretion. Readers of this document should exercise caution in evaluating its value for implementation and deployment. See RFC 3932 for more information.
このRFCは、インターネット標準のレベルの候補者ではありません。IETFは、あらゆる目的のためにこのRFCのフィットネスに関する知識を放棄し、特に、公開する決定は、セキュリティ、混雑制御、または展開プロトコルとの不適切な相互作用のIETFレビューに基づいていないことに注意してください。RFCエディターは、その裁量でこのドキュメントを公開することを選択しました。このドキュメントの読者は、実装と展開の価値を評価する際に注意する必要があります。詳細については、RFC 3932を参照してください。
Abstract
概要
When the establishment of a higher priority (Traffic Engineering Label Switched Path) TE LSP requires the preemption of a set of lower priority TE LSPs, a node has to make a local decision to select which TE LSPs will be preempted. The preempted LSPs are then rerouted by their respective Head-end Label Switch Router (LSR). This document presents a flexible policy that can be used to achieve different objectives: preempt the lowest priority LSPs; preempt the minimum number of LSPs; preempt the set of TE LSPs that provide the closest amount of bandwidth to the required bandwidth for the preempting TE LSPs (to minimize bandwidth wastage); preempt the LSPs that will have the maximum chance to get rerouted. Simulation results are given and a comparison among several different policies, with respect to preemption cascading, number of preempted LSPs, priority, wasted bandwidth and blocking probability is also included.
より高い優先度（トラフィックエンジニアリングラベルの切り替えパス）TE LSPの確立が、より低い優先度TE LSPのセットの先制が必要な場合、ノードは、どのTE LSPが先制されるかを選択するためにローカルな決定を下す必要があります。その後、先制型LSPは、それぞれのヘッドエンドラベルスイッチルーター（LSR）によって再ルーティングされます。このドキュメントは、さまざまな目的を達成するために使用できる柔軟なポリシーを提示します。LSPの最小数を先取りします。Preempting Te LSPに必要な帯域幅に最も近い量の帯域幅を提供するTe LSPのセットを先取りします（帯域幅の浪費を最小限に抑えるため）。再ルーティングの最大のチャンスがあるLSPを先取りします。シミュレーション結果が示され、いくつかの異なるポリシー間の比較があります。先制カスケード、先制型LSPの数、優先度、無駄な帯域幅、ブロッキング確率も含まれています。
Table of Contents
目次
1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. LSP Setup Procedure and Preemption . . . . . . . . . . . . . . 5
4. Preemption Cascading . . . . . . . . . . . . . . . . . . . . . 6
5. Preemption Heuristic . . . . . . . . . . . . . . . . . . . . . 7
5.1. Preempting Resources on a Path . . . . . . . . . . . . . . 7
5.2. Preemption Heuristic Algorithm . . . . . . . . . . . . . . 8
6. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.1. Simple Case: Single Link . . . . . . . . . . . . . . . . . 10
6.2. Network Case . . . . . . . . . . . . . . . . . . . . . . . 12
7. Security Considerations . . . . . . . . . . . . . . . . . . . 16
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 16
9. Informative References . . . . . . . . . . . . . . . . . . . . 17
The IETF Traffic Engineering Working Group has defined the requirements and protocol extensions for DiffServ-aware MPLS Traffic Engineering (DS-TE) [RFC3564] [RFC4124]. Several Bandwidth Constraint models for use with DS-TE have been proposed [RFC4127] [RFC4128] [RFC4126] and their performance was analyzed with respect to the use of preemption.
IETFトラフィックエンジニアリングワーキンググループは、Diffserv-Aware MPLSトラフィックエンジニアリング（DS-TE）[RFC3564] [RFC4124]の要件とプロトコル拡張を定義しています。DS-TEで使用するためのいくつかの帯域幅制約モデルが提案されており[RFC4127] [RFC4128] [RFC4126]、そのパフォーマンスは、プリエンプションの使用に関して分析されました。
Preemption can be used as a tool to help ensure that high priority LSPs can always be routed through relatively favorable paths. Preemption can also be used to implement various prioritized access policies as well as restoration policies following fault events [RFC2702].
プリエンプションは、優先度の高いLSPが常に比較的好ましいパスを介して常にルーティングできるようにするためのツールとして使用できます。先制を使用して、さまざまな優先順位付けされたアクセスポリシーと、障害イベントに続く修復ポリシーを実装することもできます[RFC2702]。
Although not a mandatory attribute in the traditional IP world, preemption becomes important in networks using online, distributed Constrained Shortest Path First (CSPF) strategies for their Traffic Engineering Label Switched Path (TE LSP) path computation to limit the impact of bandwidth fragmentation. Moreover, preemption is an attractive strategy in an MPLS network in which traffic is treated in a differentiated manner and high-importance traffic may be given special treatment over lower-importance traffic [DEC-PREP, ATM-PREP]. Nevertheless, in the DS-TE approach, whose issues and requirements are discussed in [RFC3564], the preemption policy is considered an important piece on the bandwidth reservation and management puzzle, but no preemption strategy is defined. Note that preemption also plays an important role in regular MPLS Traffic Engineering environments (with a single pool of bandwidth).
従来のIPの世界では必須の属性ではありませんが、オンラインで分散した制約付き最短パス（CSPF）戦略を使用して、トラフィックエンジニアリングラベルスイッチドパス（TE LSP）パス計算のための制約された最短パス（CSPF）戦略を使用して、帯域幅の断片化の影響を制限するネットワークで先制が重要になります。さらに、先制はMPLSネットワークの魅力的な戦略であり、トラフィックが差別化された方法で処理され、重要性の高いトラフィックが低いトラフィック[Dec-Prep、ATM-Prep]にわたって特別な治療を受ける可能性があります。それにもかかわらず、[RFC3564]で問題と要件が議論されているDS-TEアプローチでは、先制ポリシーは帯域幅の予約と管理パズルに関する重要な部分と見なされますが、先制戦略は定義されていません。先制は、通常のMPLSトラフィックエンジニアリング環境（帯域幅の1つのプールを使用）でも重要な役割を果たしていることに注意してください。
This document proposes a flexible preemption policy that can be adjusted in order to give different weight to various preemption criteria: priority of LSPs to be preempted, number of LSPs to be preempted, amount of bandwidth preempted, blocking probability. The implications (cascading effect, bandwidth wastage, priority of preempted LSPs) of selecting a certain order of importance for the criteria are discussed for the examples given.
このドキュメントでは、さまざまな先制基準に異なる重みを与えるために調整できる柔軟な先制ポリシーを提案します：先制するLSPの優先順位、先制回数の数、帯域幅の量、ブロッキング確率。基準に対して特定の重要な順序を選択することに対する意味（カスケード効果、帯域幅の浪費、先制LSPの優先順位）について説明します。
In [RFC2702], issues and requirements for Traffic Engineering in an MPLS network are highlighted. In order to address both traffic-oriented and resource-oriented performance objectives, the authors point out the need for priority and preemption parameters as Traffic Engineering attributes of traffic trunks. The notion of preemption and preemption priority is defined in [RFC3272], and preemption attributes are defined in [RFC2702] and [RFC3209].
[RFC2702]では、MPLSネットワークでのトラフィックエンジニアリングの問題と要件が強調表示されています。トラフィック指向とリソース指向のパフォーマンス目標の両方に対処するために、著者は、トラフィックトランクのトラフィックエンジニアリング属性として優先順位とプリエンプションパラメーターの必要性を指摘しています。先制および先制優先度の概念は[RFC3272]で定義されており、先制属性は[RFC2702]および[RFC3209]で定義されています。
A traffic trunk is defined as an aggregate of traffic flows belonging to the same class that are placed inside an LSP [RFC3564]. In this context, preemption is the act of selecting an LSP that will be removed from a given path in order to give room to another LSP with a higher priority (lower preemption number). More specifically, the preemption attributes determine whether an LSP with a certain setup preemption priority can preempt another LSP with a lower holding preemption priority from a given path, when there is competition for available resources. Note that competing for resources is one situation in which preemption can be triggered, but other situations may exist, themselves controlled by a policy.
トラフィックトランクは、LSP [RFC3564]内に配置されている同じクラスに属するトラフィックフローの集合体として定義されます。これに関連して、先制は、優先度が高い（先制数が低い）別のLSPにスペースを与えるために、特定のパスから削除されるLSPを選択する行為です。より具体的には、先制属性は、利用可能なリソースの競争がある場合、特定のセットアップの先制優先度を持つLSPが、特定のパスからのより低い保持先の優先度を持つ別のLSPを先取りできるかどうかを決定します。リソースの競争は、先制をトリガーできる状況の1つであるが、他の状況が存在する可能性があり、それ自体がポリシーによって制御される可能性があることに注意してください。
For readability, a number of definitions from [RFC3564] are repeated here:
読みやすさのために、[RFC3564]の多くの定義がここで繰り返されます。
Class-Type (CT): The set of Traffic Trunks crossing a link that is governed by a specific set of Bandwidth constraints. CT is used for the purposes of link bandwidth allocation, constraint-based routing, and admission control. A given Traffic Trunk belongs to the same CT on all links.
クラスタイプ（CT）：帯域幅の制約の特定のセットによって支配されるリンクを横切るトラフィックトランクのセット。CTは、リンク帯域幅の割り当て、制約ベースのルーティング、および入場制御の目的に使用されます。特定のトラフィックトランクは、すべてのリンクで同じCTに属します。
TE-Class: A pair of:
TE-Class：1ペア：
i. A Class-Type.
i. クラスタイプ。
ii. A preemption priority allowed for that Class-Type. This means that an LSP transporting a Traffic Trunk from that Class-Type can use that preemption priority as the set-up priority, as the holding priority, or both.
ii。そのクラスタイプに許可される先制の優先順位。これは、そのクラスタイプからトラフィックトランクを輸送するLSPが、その先制の優先順位をセットアップの優先順位として使用することができることを意味します。
By definition, there may be more than one TE-Class using the same CT, as long as each TE-Class uses a different preemption priority. Also, there may be more than one TE-Class with the same preemption priority, provided that each TE-Class uses a different CT. The network administrator may define the TE-Classes in order to support preemption across CTs, to avoid preemption within a certain CT, or to avoid preemption completely, when so desired. To ensure coherent operation, the same TE-Classes must be configured in every Label Switched Router (LSR) in the DS-TE domain.
定義上、各TEクラスが異なる先制優先度を使用する限り、同じCTを使用して複数のTEクラスがある場合があります。また、各TEクラスが異なるCTを使用している場合、同じ先制優先度を持つ複数のTEクラスがある場合があります。ネットワーク管理者は、CTの先制をサポートしたり、特定のCT内での先制を回避したり、望んでいた場合に完全に先入観を避けるために、TEクラスを定義できます。コヒーレント操作を確保するには、DS-TEドメインのすべてのラベルスイッチルーター（LSR）で同じTEクラスを構成する必要があります。
As a consequence of a per-TE-Class treatment, the Interior Gateway Protocol (IGP) needs to advertise separate Traffic Engineering information for each TE-Class, which consists of the Unreserved Bandwidth (UB) information [RFC4124]. The UB information will be used by the routers, checking against the bandwidth constraint model parameters, to decide whether preemption is needed. Details on how to calculate the UB are given in [RFC4124].
TETクラスごとの治療の結果として、インテリアゲートウェイプロトコル（IGP）は、予約されていない帯域幅（UB）情報[RFC4124]で構成されるTEクラスごとに個別のトラフィックエンジニアリング情報を宣伝する必要があります。UB情報は、ルーターによって使用され、帯域幅制約モデルパラメーターに対してチェックして、プリエンプションが必要かどうかを判断します。UBを計算する方法の詳細は[RFC4124]に記載されています。
A new LSP setup request has two important parameters: bandwidth and preemption priority. The set of LSPs to be preempted can be selected by optimizing an objective function that represents these two parameters, and the number of LSPs to be preempted. More specifically, the objective function could be any, or a combination, of the following [DEC-PREP, ATM-PREP]:
新しいLSPセットアップリクエストには、帯域幅とプリエンプションの優先度の2つの重要なパラメーターがあります。先制するLSPのセットは、これら2つのパラメーターを表す目的関数と、先制するLSPの数を最適化することにより選択できます。より具体的には、目的関数は、次の[decrep、atm-prep]のいずれか、または組み合わせである可能性があります。
* Preempt the LSPs that have the least priority (preemption priority). The Quality of Service (QoS) of high priority traffic would be better satisfied, and the cascading effect described below can be limited.
* 優先度が最も低いLSP（先制優先度）を先取りします。優先度の高いトラフィックのサービス品質（QO）はよりよく満たされ、以下に説明するカスケード効果は制限されます。
* Preempt the least number of LSPs. The number of LSPs that need to be rerouted would be lower.
* LSPの最小数を先取りします。再ルーティングする必要があるLSPの数は低くなります。
* Preempt the least amount of bandwidth that still satisfies the request. Resource utilization could be improved. The preemption of larger TE LSPs (more than requested) by the newly signaled TE LSP implies a larger amount of bandwidth to be rerouted, which is likely to increase the probability of blocking (inability to find a path for some TE LSPs).
* リクエストを満たしている帯域幅の最小量を先取りします。リソースの利用を改善することができます。新たに信号されたTE LSPによるより大きなTE LSP（要求以上）の先制は、再ルーティングされるより多くの帯域幅を意味することを意味します。
* Preempt LSPs that minimize the blocking probability (risk that preempted TE LSP cannot be rerouted).
* ブロッキング確率を最小限に抑えるPreempt LSP（TE LSPを先取りしたリスクは再ルーティングできません）。
After the preemption selection phase is finished, the selected LSPs are signaled as preempted and the new LSP is established (if a new path satisfying the constraints can be found). The UB information is then updated via flooding of an IGP-TE update and/or simply pruning the link where preemption occurred. Figure 1 shows a flowchart that summarizes how each LSP setup request is treated in a preemption-enabled scenario.
プリエンプション選択段階が終了した後、選択されたLSPが先制として信号を送り、新しいLSPが確立されます（制約を満たす新しいパスが見つかる場合）。UB情報は、IGP-TEアップデートの洪水および/または単にプリエンプションが発生したリンクを剪定することで更新されます。図1は、各LSPセットアップリクエストが先制対応シナリオでどのように扱われるかを要約するフローチャートを示しています。
LSP Setup Request
(TE-Class i, bw=r)
|
|
v NO
UB[TE-Class i] >= r ? -------> Reject LSP
Setup and flood an updated IGP-TE
| LSA/LSP
|YES
v NO
Preemption Needed ? -------> Setup LSP/Update UB if a threshold is
| crossed
| YES
v
Preemption ----> Setup LSP/Reroute Preempted LSPs
Algorithm Update UB
Figure 1: Flowchart for LSP setup procedure.
図1：LSPセットアップ手順のフローチャート。
In [DEC-PREP], the authors propose connection preemption policies that optimize the discussed criteria in a given order of importance: number of LSPs, bandwidth, and priority; bandwidth, priority, and number of LSPs. The novelty in our approach is the use of an objective function that can be adjusted by the service provider in order to stress the desired criteria. No particular criteria order is enforced. Moreover, a new criterion is added to the objective function: optimize the blocking probability (to minimize the risk that an LSP is not rerouted after being preempted).
[decrep]では、著者は、議論された基準を特定の重要な順序で最適化する接続先制ポリシーを提案します。LSP、帯域幅、および優先度の数。帯域幅、優先度、およびLSPの数。私たちのアプローチの斬新さは、望ましい基準を強調するためにサービスプロバイダーが調整できる目的関数の使用です。特定の基準順序は施行されていません。さらに、新しい基準が目的関数に追加されます。ブロッキング確率を最適化します（LSPが先制後に再ルーティングされないリスクを最小限に抑えるため）。
The decision of preempting an LSP may cause other preemptions in the network. This is called preemption cascading effect and different cascading levels may be achieved by the preemption of a single LSP. The cascading levels are defined in the following manner: when an LSP is preempted and rerouted without causing any further preemption, the cascading is said to be of level zero. However, when a preempted LSP is rerouted, and in order to be established in the new route it also causes the preemption of other LSPs, the cascading is said to be of level 1, and so on.
LSPを先取りするという決定は、ネットワーク内の他の先制を引き起こす可能性があります。これは、先行式カスケード効果と呼ばれ、単一のLSPの先制により異なるカスケードレベルが達成される可能性があります。カスケードレベルは、次の方法で定義されます。LSPがさらに先制を引き起こすことなく先制および再ルーティングされると、カスケードはレベルゼロと言われます。ただし、先制型LSPが再ルーティングされ、新しいルートで確立されると、他のLSPの先制も引き起こす場合、カスケードはレベル1であると言われています。
Preemption cascading is not desirable and therefore policies that minimize it are of interest. Typically, this can result in severe network instabilities. In Section 5, a new versatile preemption heuristic will be presented. In Section 6, preemption simulation results will be discussed and the cascading effect will be analyzed.
プリエンプションカスケードは望ましくないため、それを最小限に抑えるポリシーは興味深いものです。通常、これは深刻なネットワークの不安定性をもたらす可能性があります。セクション5では、新しい汎用性の高い先制ヒューリスティックが提示されます。セクション6では、プリエンプションシミュレーション結果について説明し、カスケード効果について分析します。
It is important to note that once a request for an LSP setup arrives, each LSR along the TE LSP path checks the available bandwidth on its outgoing link. For the links in which the available bandwidth is not enough, the preemption policy needs to be activated in order to guarantee the end-to-end bandwidth reservation for the new LSP. This is a distributed approach, in which every node on the path is responsible for running the preemption algorithm and determining which LSPs would be preempted in order to fit the new request. A distributed approach may not lead to an optimal solution.
LSPセットアップのリクエストが届くと、TE LSPパスに沿った各LSRが発信リンクで利用可能な帯域幅をチェックすることに注意することが重要です。利用可能な帯域幅では不十分なリンクの場合、新しいLSPのエンドツーエンド帯域幅予約を保証するために、先制ポリシーをアクティブにする必要があります。これは分散アプローチであり、パス上のすべてのノードが先制アルゴリズムを実行し、新しいリクエストに適合するためにどのLSPが先制されるかを決定する責任があります。分散アプローチは、最適なソリューションにつながらない場合があります。
Alternatively, in a centralized approach, a manager entity runs the preemption policy and determines the best LSPs to be preempted in order to free the required bandwidth in all the links that compose the path. The preemption policy would try to select LSPs that overlap with the path being considered (preempt a single LSP that overlaps with the route versus preempt a single LSP on every link that belongs to the route).
あるいは、集中型アプローチでは、マネージャーエンティティが先制ポリシーを実行し、パスを構成するすべてのリンクで必要な帯域幅を解放するために、先制する最適なLSPを決定します。プリエンプションポリシーは、検討されているパスと重複するLSPを選択しようとします（ルートに属するすべてのリンクでルートと重複する単一のLSPと1つのLSPを先取りする）。
Both centralized and distributed approaches have advantages and drawbacks. A centralized approach would be more precise, but require that the whole network state be stored and updated accordingly, which raises scalability issues. In a network where LSPs are mostly static, an offline decision can be made to reroute LSPs and the centralized approach could be appropriate. However, in a dynamic network in which LSPs are set up and torn down in a frequent manner because of new TE LSPs, bandwidth increase, reroute due to failure, etc., the correctness of the stored network state could be questionable. Moreover, the setup time is generally increased when compared to a distributed solution. In this scenario, the distributed approach would bring more benefits, even when resulting in a non-optimal solution (The gain in optimality of a centralized approach compared to a distributed approach depends on many factors: network topology, traffic matrix, TE strategy, etc.). A distributed approach is also easier to be implemented due to the distributed nature of the current Internet protocols.
集中化されたアプローチと分散アプローチには、利点と欠点があります。集中化されたアプローチはより正確になりますが、それに応じてネットワーク状態全体を保存および更新する必要があり、スケーラビリティの問題が発生します。LSPがほとんど静的であるネットワークでは、LSPを再ルーティングするためにオフラインの決定を下すことができ、集中化されたアプローチが適切である可能性があります。ただし、LSPが新たなLSP、帯域幅の増加、障害による再ルーティングなど、LSPが頻繁にセットアップされ、取り壊される動的ネットワークでは、蓄積されたネットワーク状態の正しさは疑わしい可能性があります。さらに、分散型ソリューションと比較すると、セットアップ時間は一般に増加します。このシナリオでは、分散したアプローチは、最適ではないソリューションをもたらす場合でも、より多くの利点をもたらします（分散アプローチと比較して集中的なアプローチの最適性の増加は、ネットワークトポロジ、トラフィックマトリックス、TE戦略などの多くの要因に依存します。。）。現在のインターネットプロトコルの分散性のため、分散アプローチも実装しやすいです。
Since the current Internet routing protocols are essentially distributed, a decentralized approach was selected for the LSP preemption policy. The parameters required by the new preemption policies are currently available for OSPF and Intermediate System to Intermediate System (IS-IS).
現在のインターネットルーティングプロトコルは本質的に分散されているため、LSPプリエンプションポリシーに分散型アプローチが選択されました。新しい先制ポリシーで必要なパラメーターは、現在、OSPFおよび中間システム（IS-IS）から中間システムで利用可能です。
Consider a request for a new LSP setup with bandwidth b and setup preemption priority p. When preemption is needed, due to lack of available resources, the preemptable LSPs will be chosen among the ones with lower holding preemption priority (higher numerical value) in order to fit r=b-Abw(l). The variable r represents the actual bandwidth that needs to be preempted (the requested, b, minus the available bandwidth on link l: Abw(l)).
帯域幅Bとセットアップの先制優先度pを備えた新しいLSPセットアップのリクエストを検討してください。利用可能なリソースが不足しているため、先制が必要な場合、r = b-abw（l）に適合するために、より低い保持先の先制優先度（高い数値値）を持つリソースの間で先制的なLSPが選択されます。変数rは、先制する必要がある実際の帯域幅を表します（要求されたb、リンクl：abw（l）で利用可能な帯域幅を除く）。
L is the set of active LSPs having a holding preemption priority lower (numerically higher) than p. So L is the set of candidates for preemption. b(l) is the bandwidth reserved by LSP l in L, expressed in bandwidth units, and p(l) is the holding preemption priority of LSP l.
lは、preemptionの優先度が低い（数値的に高い）保持先のLSPのセットです。したがって、Lは、先制の候補のセットです。b（l）は、帯域幅単位で発現するLのLSP Lによって予約されている帯域幅であり、P（L）はLSP Lの保持先の優先度です。
In order to represent a cost for each preemption priority, an associated cost y(l) inversely related to the holding preemption priority p(l) is defined. For simplicity, a linear relation y(l)=8-p(l) is chosen. y is a cost vector with L components, y(l). b is a reserved bandwidth vector with dimension L, and components b(l).
各先行優先度のコストを表すために、関連するコストy（l）は、保持先の先制優先度p（l）に反比例することが定義されています。簡単にするために、線形関係y（l）= 8-p（l）が選択されます。yは、lコンポーネントy（l）を備えたコストベクトルです。Bは、寸法LとコンポーネントB（L）を備えた予約された帯域幅ベクトルです。
Concerning the objective function, four main objectives can be reached in the selection of preempted LSPs:
目的関数に関して、先制型LSPの選択において4つの主要な目的に到達できます。
* minimize the priority of preempted LSPs, * minimize the number of preempted LSPs, * minimize the preempted bandwidth, * minimize the blocking probability.
* プリエンプトされたLSPの優先順位を最小化し、 *先制型LSPの数を最小限に抑え、プリエンプトされた帯域幅を最小限に抑え、ブロッキング確率を最小限に抑えます。
To have the widest choice on the overall objective that each service provider needs to achieve, the following equation was defined (for simplicity chosen as a weighted sum of the above mentioned criteria):
各サービスプロバイダーが達成する必要がある全体的な目的に最も広い選択をするために、次の方程式が定義されました（上記の基準の加重合計として選択された単純さのために）：
H(l)= alpha y(l) + beta 1/b(l) + gamma (b(l)-r)^2 + theta b(l)
In this equation:
この式で：
- alpha y(l) captures the cost of preempting high priority LSPs.
- Alpha Y（L）は、優先度の高いLSPを先取りするコストを捉えています。
- beta 1/b(l) penalizes the preemption of low bandwidth LSPs, capturing the cost of preempting a large number of LSPs.
- ベータ1/B（L）は、低帯域幅LSPの先制を罰し、多数のLSPを先取りするコストを獲得します。
- gamma (b(l)-r)^2 captures the cost of preemption of LSPs that are much larger or much smaller than r.
- ガンマ（b（l）-r）^2は、rよりもはるかに大きいまたははるかに小さいLSPの先制コストをキャプチャします。
- theta b(l) captures the cost of preempting large LSPs.
- Theta B（L）は、大きなLSPを先取りするコストを捉えています。
Coefficients alpha, beta, gamma, and theta can be chosen to emphasize one or more components of H.
Hの1つまたは複数のコンポーネントを強調するために、Alpha、Beta、Gamma、およびThetaの係数を選択できます。
The coefficient theta is defined such that theta = 0 if gamma > 0. This is because when trying to minimize the blocking probability of preempted LSPs, the heuristic gives preference to preempting several small LSPs (therefore gamma, which is the weight for minimizing the preempted bandwidth enforcing the selection of LSPs with similar amount of bandwidth as the requested, needs to be set as zero). The selection of several small LSPs in a normally loaded portion of the network will increase the chance that such LSPs are successfully rerouted. Moreover, the selection of several small LSPs may not imply preempting much more than the required bandwidth (resulting in low-bandwidth wastage), as it will be seen in the discussed examples. When preemption is to happen in a heavy loaded portion of the network, to minimize blocking probability, the heuristic will select fewer LSPs for preemption in order to increase the chance of rerouting.
係数は、ガンマ> 0の場合、シータ= 0の場合に定義されています。これは、先制lspのブロッキング確率を最小限に抑えようとすると、ヒューリスティックがいくつかの小さなLSPを先取りすることを好むためです（したがって、ガンマは、先制先入観を最小限に抑えるための重みです。帯域幅要求と同様の量の帯域幅でLSPの選択を強制すると、ゼロとして設定する必要があります）。ネットワークの通常ロードされた部分でいくつかの小さなLSPを選択すると、そのようなLSPが正常に再ルーティングされる可能性が高まります。さらに、いくつかの小さなLSPの選択は、議論された例で見られるように、必要な帯域幅よりもはるかに多くの帯域幅（低帯域幅の浪費をもたらす）よりも多くの先取りを意味しないかもしれません。ブロッキング確率を最小限に抑えるために、ネットワークの重い負荷部分でプリエンプションが発生する場合、ヒューリスティックは再輸送のためにLSPを選択するためにより少ないLSPを選択します。
H is calculated for each LSP in L. The LSPs to be preempted are chosen as the ones with smaller H that add enough bandwidth to accommodate r. When sorting LSPs by H, LSPs with the same value for H are ordered by bandwidth b, in increasing order. For each LSP with repeated H, the algorithm checks whether the bandwidth b assigned to only that LSP is enough to satisfy r. If there is no such LSP, it checks whether the bandwidth of each of those LSPs added to the previously preempted LSPs' bandwidth is enough to satisfy r. If that is not true for any LSP in that repeated H-value sequence, the algorithm preempts the LSP that has the larger amount of bandwidth in the sequence, and keeps preempting in decreasing order of b until r is satisfied or the sequence is finished. If the sequence is finished and r is not satisfied, the algorithm again selects LSPs to be preempted based on an increasing order of H. More details on the algorithm are given in [PREEMPTION].
HはLSPの各LSPについて計算されます。先取りするLSPは、rを収容するのに十分な帯域幅を追加するH hが小さいものとして選択されます。LSPをHで並べ替えると、hに対して同じ値を持つLSPが帯域幅Bで注文され、順序が増えます。繰り返される各LSPについて、アルゴリズムは、そのLSPのみに割り当てられた帯域幅Bがrを満たすのに十分かどうかをチェックします。そのようなLSPがない場合、以前に先取りしたLSPの帯域幅に追加された各LSPの帯域幅がRを満たすのに十分かどうかをチェックします。繰り返されるH値シーケンスのLSPにそれが当てはまらない場合、アルゴリズムはシーケンス内の帯域幅の量が多いLSPを先取りし、Rが満たされるか、シーケンスが終了するまでBの順序を減少させ続けます。シーケンスが終了し、Rが満たされていない場合、アルゴリズムは再びLSPを選択し、Hの増加順序に基づいて先制します。アルゴリズムの詳細は[先制]に記載されています。
When the objective is to minimize blocking, the heuristic will follow two options on how to calculate H:
目的がブロックを最小限に抑えることである場合、ヒューリスティックはHを計算する方法に関する2つのオプションに従います。
* If the link in which preemption is to happen is normally loaded, several small LSPs will be selected for preemption using H(l)= alpha y(l) + theta b(l).
* 通常、プリエンプションが発生するリンクがロードされている場合、H（L）= alpha Y（L）Theta B（L）を使用して、いくつかの小さなLSPが先制のために選択されます。
* If the link is overloaded, few LSPs are selected using H(l)= alpha y(l) + beta 1/b(l).
* リンクが過負荷になっている場合、h（l）= alpha y（l）ベータ1/b（l）を使用して選択されるLSPはほとんどありません。
We first consider a very simple case, in which the path considered for preemption is composed by a single hop. The objective of this example is to illustrate how the heuristic works. In the next section, we will study a more complex case in which the preemption policies are being tested on a network.
最初に非常に単純なケースを検討します。非常に単純なケースでは、先制のパスが単一のホップで構成されています。この例の目的は、ヒューリスティックがどのように機能するかを説明することです。次のセクションでは、ネットワークで先制ポリシーがテストされているより複雑なケースを研究します。
Consider a link with 16 LSPs with reserved bandwidth b in Mbps, preemption holding priority p, and cost y, as shown in Table 1. In this example, 8 TE-Classes are active. The preemption here is being performed on a single link as an illustrative example.
表1に示すように、MBPSに予約された帯域幅B、優先度P、コストYを備えた帯域幅Bを持つ16のLSPを含むリンクを考えてみましょう。この例では、8つのTEクラスがアクティブになります。ここでの先制は、例として単一のリンクで実行されています。
------------------------------------------------------------------
LSP L1 L2 L3 L4 L5 L6 L7 L8
------------------------------------------------------------------
Bandwidth (b) 20 10 60 25 20 1 75 45
Priority (p) 1 2 3 4 5 6 7 5
Cost (y) 7 6 5 4 3 2 1 3
------------------------------------------------------------------
LSP L9 L10 L11 L12 L13 L14 L15 L16
------------------------------------------------------------------
Bandwidth (b) 100 5 40 85 50 20 70 25
Priority (p) 3 6 4 5 2 3 4 7
Cost (y) 5 2 4 3 6 5 4 1
------------------------------------------------------------------
Table 1: LSPs in the considered link.
A request for an LSP establishment arrives with r=175 Mbps and p=0 (highest possible priority, which implies that all LSPs with p>0 in Table 1 will be considered when running the algorithm). Assume Abw(l)=0.
LSP施設のリクエストがr = 175 Mbpsとp = 0で届きます（可能な限り最優先事項です。これは、表1のp> 0のすべてのLSPがアルゴリズムを実行するときに考慮されることを意味します）。ABW（L）= 0と仮定します。
If priority is the only important criterion, the network operator configures alpha=1, beta=gamma=theta=0. In this case, LSPs L6, L7, L10, L12, and L16 are selected for preemption, freeing 191 bandwidth units to establish the high-priority LSP. Note that 5 LSPs were preempted, but all with a priority level between 5 and 7.
優先度が唯一の重要な基準である場合、ネットワーク演算子はalpha = 1、beta = gamma = theta = 0を構成します。この場合、LSPS L6、L7、L10、L12、およびL16が先制用に選択され、高優先度LSPを確立するために191の帯域幅ユニットを解放します。5つのLSPが先制されたが、すべてが5〜7の間の優先レベルのあることに注意してください。
In a network in which rerouting is an expensive task to perform (and the number of rerouted TE LSPs should be as small as possible), one might prefer to set beta=1 and alpha=gamma=theta=0. LSPs L9 and L12 would then be selected for preemption, adding up to 185 bandwidth units (less wastage than the previous case). The priorities of the selected LSPs are 3 and 5 (which means that they might themselves preempt some other LSPs when rerouted).
再ルーティングが実行するための高価なタスクであるネットワーク（および再ルーティングされたTE LSPの数は可能な限り少ないはずです）では、beta = 1とalpha = gamma = theta = 0を設定することを好むかもしれません。その後、LSPS L9とL12が先制のために選択され、最大185の帯域幅ユニット（前のケースよりも無駄が少ない）を追加します。選択したLSPの優先順位は3および5です（つまり、再ルーティング時に他のLSPを先取りする可能性があります）。
Suppose the network operator decides that it is more appropriate to configure alpha=1, beta=10, gamma=0, theta=0 (the parameters were set to values that would balance the weight of each component, namely priority and number, in the cost function), because in this network rerouting is very expensive, LSP priority is important, but bandwidth is not a critical issue. In this case, LSPs L7, L12, and L16 are selected for preemption. This configuration results in a smaller number of preempted LSPs when compared to the first case, and the priority levels are kept between 5 and 7.
ネットワークオペレーターが、alpha = 1、beta = 10、gamma = 0、theta = 0を構成する方が適切であると判断したとします（パラメーターは、各コンポーネントの重み、つまり優先度と数のバランスをとる値に設定されています。このネットワークでは、再ルーティングは非常に高価であるため、LSPの優先順位は重要ですが、帯域幅は重要な問題ではありません。この場合、LSPS L7、L12、およびL16が先制のために選択されます。この構成により、最初のケースと比較した場合、先制的な数のLSPが少なくなり、優先レベルは5〜7の間に保持されます。
To take into account the number of LSPs preempted, the preemption priority, and the amount of bandwidth preempted, the network operator may set alpha > 0, beta > 0, and gamma > 0. To achieve a balance among the three components, the parameters need to be normalized. Aiming for a balance, the parameters could be set as alpha=1, beta=10 (bringing the term 1/b(l) closer to the other parameters), and gamma=0.001 (bringing the value of the term (b(l)-r)^2 closer to the other parameters). LSPs L7 and L9 are selected for preemption, resulting in exactly 175 bandwidth units and with priorities 3 and 7 (note that less LSP are preempted but they have a higher priority which may result in a cascading effect).
先制的なLSPの数、先制優先度、およびプリエンプトの帯域幅の量を考慮するために、ネットワーク演算子はアルファ> 0、ベータ> 0、およびガンマ> 0を設定することができます。正規化する必要があります。バランスを目指して、パラメーターはalpha = 1、beta = 10（1/b（l）を他のパラメーターに近づける）、およびガンマ= 0.001（用語の値をもたらす）として設定できます（b（l））-r）^2他のパラメーターに近い）。LSPS L7とL9は先制のために選択され、正確に175の帯域幅ユニットと優先順位3と7があります（LSPが少ないが、優先度が高いことに注意してください。
If the minimization of the blocking probability is the criterion of most interest, the cost function could be configured with theta=1, alpha=beta=gamma=0. In that case, several small LSPs are selected for preemption: LSPs L2, L4, L5, L6, L7, L10, L14, and L16. Their preemption will free 181 Mbps in this link, and because the selected LSPs have small bandwidth requirement there is a good chance that each of them will find a new route in the network.
ブロッキング確率の最小化が最も関心のある基準である場合、コスト関数はtheta = 1、alpha = beta = gamma = 0で構成できます。その場合、いくつかの小さなLSPが先制のために選択されます：LSPS L2、L4、L5、L6、L7、L10、L14、およびL16。彼らの先制はこのリンクで181 Mbpsを解放します。選択したLSPには小さな帯域幅要件があるため、それぞれがネットワークに新しいルートを見つける可能性が高くなります。
From the above example, it can be observed that when the priority was the highest concern and the number of preempted LSPs was not an issue, 5 LSPs with the lowest priority were selected for preemption. When only the number of LSPs was an issue, the minimum number of LSPs was selected for preemption: 2, but the priority was higher than in the previous case. When priority and number were important factors and a possible waste of bandwidth was not an issue, 3 LSPs were selected, adding more bandwidth than requested, but still with low preemption priority. When considering all the parameters but the blocking probability, the smallest set of LSP was selected, 2, adding just enough bandwidth, 175 Mbps, and with priority levels 3 and 7.
上記の例から、優先順位が最も高い懸念であり、先取りされたLSPの数が問題ではなかった場合、最優先度の5 LSPが先制のために選択されたことが観察できます。LSPの数のみが問題である場合、LSPの最小数は先制のために選択されました：2でしたが、優先度は前のケースよりも高かった。優先順位と数が重要な要因であり、帯域幅の廃棄物の可能性が問題ではない場合、3 LSPが選択され、要求よりも多くの帯域幅を追加しましたが、先制の優先度は低いです。ブロッキング確率以外のすべてのパラメーターを考慮すると、LSPの最小セットが選択され、十分な帯域幅、175 Mbpsを追加し、優先レベル3および7を追加しました。
When the blocking probability was the criterion of interest, several (8) small LSPs were preempted. The bandwidth wastage is low, but the number of rerouting events will increase. Given the bandwidth requirement of the preempted LSPs, it is expected that the chances of finding a new route for each LSP will be high.
ブロッキング確率が関心の基準である場合、いくつかの小さなLSPが先制されました。帯域幅の浪費は低いですが、再ルーティングイベントの数は増加します。先取りされたLSPの帯域幅要件を考えると、各LSPの新しいルートを見つける可能性が高くなると予想されます。
For these experiments, we consider a 150 nodes topology with an average network connectivity of 3. 10% of the nodes in the topology have a degree of connectivity of 6. 10% of the links are OC3, 70% are OC48, and 20% are OC192.
これらの実験では、平均ネットワーク接続が3の150ノードトポロジーを検討します。トポロジのノードの10％は、6の程度の接続性を持っています。リンクの10％はOC3、70％はOC48、20％です。OC192です。
Two classes of TE LSPs are in use: Voice LSPs and Data Internet/VPN LSPs. For each class of TE LSP, the set of preemptions (and the proportion of LSPs for each preemption) and the size distributions are as follows (a total of T LSPs is considered):
TE LSPの2つのクラスが使用されています：Voice LSPとData Internet/VPN LSP。TE LSPの各クラスについて、先制のセット（および各先制のLSPの割合）とサイズ分布のセットは次のとおりです（合計T LSPの合計を考慮してください）：
T: total number of TE LSPs in the network (T = 18,306 LSPs)
T：ネットワーク内のTE LSPの総数（T = 18,306 LSP）
Voice:
声：
Number: 20% of T Preemption: 0, 1 and 2 Size: uniform distribution between 30M and 50M
番号：Tの20％：0、1、2サイズ：30m〜50mの均一な分布
Internet/VPN TE:
インターネット/VPN TE：
Number: 4% of T Preemption: 3 Size: uniform distribution between 20M and 50M
番号：Tの4％：3サイズ：20m〜50mの均一な分布
Number: 8% of T Preemption 4 Size: uniform distribution between 15M and 40M
番号：Tプリエンプション4サイズの8％：15m〜40mの均一な分布
Number: 8% of T Preemption 5 Size: uniform distribution between 10M and 20M
番号：Tの予防5の8％サイズ：10m〜20mの均一な分布
Number: 20% of T Preemption 6 Size: uniform distribution between 1M and 20M
番号：Tプリエンプション6サイズの20％：1m〜20mの均一な分布
Number: 40% of T Preemption 7 Size: uniform distribution between 1K and 1M
番号：Tプリエンプション7サイズの40％：1K〜1Mの間の均一な分布
LSPs are set up mainly due to network failure: a link or a node failed and LSPs are rerouted.
LSPは主にネットワークの障害によりセットアップされます。リンクまたはノードが故障し、LSPが再ルーティングされます。
The network failure events were simulated with two functions:
ネットワーク障害イベントは、2つの機能でシミュレートされました。
- Constant: 1 failure chosen randomly among the set of links every 1 hour.
- 定数：1 1時間ごとにリンクのセットの中でランダムに選択された障害。
- Poisson process with interarrival average = 1 hour.
- Interrival平均= 1時間のポアソンプロセス。
Table 2 shows the results for simulations with constant failure. The simulations were run with the preemption heuristic configured to balance different criteria (left side of the table), and then with different preemption policies that consider the criteria in a given order of importance rather than balancing them (right side of the table).
表2は、一定の障害を伴うシミュレーションの結果を示しています。シミュレーションは、異なる基準（テーブルの左側）のバランスをとるように構成された先制ヒューリスティックで実行され、次に、バランスをとるのではなく、特定の重要な順序で基準を考慮する異なる先制ポリシー（テーブルの右側）で実行されました。
The proposed heuristic was configured to balance the following criteria:
提案されたヒューリスティックは、次の基準のバランスをとるように構成されました。
HPB: The heuristic with priority and bandwidth wastage as the most important criteria (alpha=10, beta=0, gamma=0.001, theta=0).
HPB：最も重要な基準として優先度と帯域幅の無駄を持つヒューリスティック（alpha = 10、beta = 0、gamma = 0.001、theta = 0）。
HBlock: The heuristic considering the minimization of blocking probability (normal load links: alpha=1, beta=0, gamma=0, theta=0.01) (heavy load links: alpha=1, beta=10).
hblock：ブロッキング確率の最小化を考慮したヒューリスティック（通常の負荷リンク：alpha = 1、beta = 0、gamma = 0、theta = 0.01）（重量荷重リンク：alpha = 1、beta = 10）。
HNB: The heuristic with number of preemptions and wasted bandwidth in consideration (alpha=0, beta=10, gamma=0.001, theta=0).
HNB：先取りの数と無駄な帯域幅を考慮したヒューリスティック（alpha = 0、beta = 10、gamma = 0.001、theta = 0）。
Other algorithms that consider the criteria in a given order of importance:
重要性のある順序で基準を考慮する他のアルゴリズム：
P: Sorts candidate LSPs by priority only.
P：優先順位のみで候補LSPを並べ替えます。
PN: Sorts the LSPs by priority, and for cases in which the priority is the same, orders those LSPs by decreasing bandwidth (selects larger LSPs for preemption in order to minimize number of preempted LSPs).
PN：優先順位でLSPを並べ替え、優先度が同じ場合、帯域幅を減らすことでLSPを注文します（先制型LSPの数を最小限に抑えるために、先制のLSPが大きくなります）。
PB: Sorts the LSPs by priority, and for LSPs with the same priority, sorts those by increasing bandwidth (select smaller LSPs in order to reduce bandwidth wastage).
PB：優先度でLSPを並べ替え、同じ優先度のあるLSPの場合、帯域幅を増やすことでそれらをソートします（帯域幅の浪費を減らすために小さなLSPを選択します）。
-------------------------------------------------
| Heuristic | Other algorithms |
-------------------------------------------------
| HPB | HBlock| HNB | P | PN | PB |
-----------------------------------------------------------------
Need to be | 532 | 532 | 532 | 532 | 532 | 532 |
Rerouted | | | | | | |
-----------------------------------------------------------------
Preempted | 612 | 483 | 619 | 504 | 477 | 598 |
-----------------------------------------------------------------
Rerouted |467|76%|341|73%|475|77%|347|69%|335|70%|436|73%|
Blocked |145|24%|130|27%|144|23%|157|31%|142|30%|162|27%|
-----------------------------------------------------------------
Max Cascading | 4.5 | 2 | 5 | 2.75 | 2 | 2.75 |
-----------------------------------------------------------------
Wasted Bandwidth| | | | | | |
AVR (Mbps) | 6638 | 532 | 6479 | 8247 | 8955 | 6832 |
Worst Case(Mbps)| 35321 |26010 |36809 | 28501 | 31406 | 23449 |
-----------------------------------------------------------------
Priority | | | | | | |
Average | 6 | 6.5 | 5.8 | 6.6 | 6.6 | 6.6 |
Worst Case | 1.5 | 3.8 | 1.2 | 3.8 | 3.8 | 3.8 |
-----------------------------------------------------------------
Extra Hops | | | | | | |
Average | 0.23 | 0.25 | 0.22 | 0.25 | 0.25 | 0.23 |
Worst Case | 3.25 | 3 | 3.25 | 3 | 3 | 2.75 |
-----------------------------------------------------------------
Table 2: Simulation results for constant network failure:
1 random failure every hour.
From Table 2, we can conclude that among the heuristic (HPB, HBlock, HNB) results, HBlock resulted in the smaller number of LSPs being preempted. More importantly, it also resulted in an overall smaller rejection rate and smaller average wasted bandwidth (and second overall smaller worst-case wasted bandwidth.)
表2から、ヒューリスティック（HPB、HBLOCK、HNB）の結果の中で、HBlockがLSPの数が少ないと結論付けることができます。さらに重要なことに、それはまた、全体的に拒否率が全体的に小さく、平均無駄な帯域幅が小さい（そして2番目の全体的な最悪の帯域幅帯域幅）をもたらしました。
Although HBlock does not try to minimize the number of preempted LSPs, it ends up doing so, because it preempts LSPs with lower priority mostly, and therefore it does not propagate cascading much further. Cascading was the overall lowest (preemption caused at most two levels of preemption, which was also the case for the policy PN). The average and worst preemption priority was very satisfactory (preempting mostly lowest-priority LSPs, like the other algorithms P, PN, and PB).
Hblockは、先制的なLSPの数を最小限に抑えようとはしていませんが、最優先度の低いLSPを先取りするため、それはそうすることになります。カスケードは全体的に最も低いものでした（最大2つのレベルの先制が引き起こし、これはポリシーPNの場合もありました）。平均的および最悪の先制の優先順位は非常に満足のいくものでした（他のアルゴリズムP、PN、およびPBのように、ほとんど優先度の低いLSPを先制します）。
When HPB was in use, more LSPs were preempted as a consequence of the higher cascading effect. That is due to the heuristic's choice of preempting LSPs that are very similar in bandwidth size to the bandwidth size of the preemptor LSP (which can result in preempting a higher priority LSP and therefore causing cascading). The wasted bandwidth was reduced when compared to the other algorithms (P, PN, PB).
HPBが使用されている場合、より高いカスケード効果の結果として、より多くのLSPが先制されました。これは、帯域幅のサイズが非常に類似しているLSPを先制的に先制的に選択したことが、Preemptor LSPの帯域幅サイズ（より高い優先度LSPを先取りし、したがってカスケードを引き起こす可能性がある）によるものです。無駄な帯域幅は、他のアルゴリズム（P、PN、PB）と比較すると減少しました。
When HNB was used, cascading was higher than the other cases, due to the fact that LSPs with higher priority could be preempted. When compared to P, PN, or PB, the heuristic HNB preempted more LSPs (in fact, it preempted the largest number of LSPs overall, clearly showing the cascading effect), but the average wasted bandwidth was smaller, although not as small as HBlock's (the HNB heuristic tries to preempt a single LSP, meaning it will preempt LSPs that have a reserved bandwidth similar to the actual bandwidth needed. The algorithm is not always successful, because such a match may not exist, and in that case, the wasted bandwidth could be high). The preempted priority was the highest on average and worse case, which also shows why the cascading level was also the highest (the heuristic tries to select LSPs for preemption without looking at their priority levels). In summary, this policy resulted in a poor performance.
HNBを使用した場合、優先度が高いLSPが先制される可能性があるため、HNBが他のケースよりも高かった。P、PN、またはPBと比較した場合、ヒューリスティックHNBはより多くのLSPを先取りしました（実際、全体的にLSPの最大数を先取りし、カスケード効果を明確に示していました）が、Hblockほど小さくはありませんでしたが、平均無駄な帯域幅は小さくなりました。（HNBヒューリスティックは単一のLSPを先取りしようとします。つまり、必要な実際の帯域幅と同様の帯域幅が予約されたLSPを先取りします。そのような一致が存在しない可能性があり、その場合、無駄になるため、アルゴリズムは常に成功していません。帯域幅が高い可能性があります）。先制的な優先順位は、平均して最も高いケースであり、カスケードレベルも最高であった理由を示しています（ヒューリスティックは、優先レベルを調べることなく、先制のためにLSPを選択しようとします）。要約すると、このポリシーの結果、パフォーマンスが低下しました。
Policy PN resulted in the small number of preempted LSPs overall and small number of LSPs not successfully rerouted. Cascading is low, but bandwidth wastage is very high (overall highest bandwidth wastage). Moreover, in several cases in which rerouting happened on portions of the network that were underloaded, the heuristic HBlock preempted a smaller number of LSPs than PN.
ポリシーPNの結果、少数の先制LSPの全体的なLSPが少なく、LSPの数が少ないことに成功しませんでした。カスケードは低いですが、帯域幅の浪費は非常に高いです（全体的に最高帯域幅の浪費）。さらに、下着したネットワークの一部で再ルーティングが発生したいくつかのケースでは、ヒューリスティックなhblockはPNよりも少数のLSPを先取りしました。
Policy P selects a larger number of LSPs (when compared to PN) with low priority for preemption, and therefore it is able to successfully reroute less LSPs when compared to HBlock, HPB, HNB, or PN. The bandwidth wastage is also higher when compared to any of the heuristic results or to PB, and it could be worse if the network had LSPs with a low priority and large bandwidth, which is not the case.
ポリシーPは、先制の優先度が低い多くのLSP（PNと比較して）を選択するため、HBLOCK、HPB、HNB、またはPNと比較した場合、LSPを少なく再ルーティングすることができます。帯域幅の浪費は、ヒューリスティックな結果やPBと比較した場合にも高くなります。また、ネットワークに優先度が低く、大きな帯域幅があるLSPがある場合は悪化する可能性がありますが、そうではありません。
Policy PB, when compared to PN, resulted in a larger number of preempted LSPs and an overall larger number of blocked LSPs (not rerouted), due to preemption. Cascading was slightly higher. Since the selected LSPs have low priority, they are not able to preempt much further and are blocked when the links are congested. Bandwidth wastage was smaller since the policy tries to minimize wastage, and preempted priority was about the same on average and worst case.
ポリシーPBは、PNと比較した場合、先制により多くの先制型LSPとブロックされたLSPの数が多い（再ルーティングされていない）ことをもたらしました。カスケードはわずかに高かった。選択されたLSPの優先度は低いため、リンクが混雑しているときにさらに先取りすることができず、ブロックされます。帯域幅の浪費は、ポリシーが浪費を最小限に抑えようとするため、より小さく、先制優先度は平均してほぼ同じであり、最悪の場合はほぼ同じでした。
The simulation results show that when preemption is based on priority, cascading is not critical since the preempted LSPs will not be able to propagate preemption much further. When the number of LSPs is considered, fewer LSPs are preempted and the chances of rerouting increases. When bandwidth wastage is considered, smaller LSPs are preempted in each link and the wasted bandwidth is low. The heuristic seems to combine these features, yielding the best results, especially in the case of blocking probability. When the heuristic was configured to minimize blocking probability (HBlock), small LSPs with low priority were selected for preemption on normally loaded links and fewer (larger) LSPs with low priority were selected on congested links. Due to their low priority, cascading was not an issue. Several LSPs were selected for preemption, but the rate of LSPs that were not successfully rerouted was the lowest. Since the LSPs are small, it is easier to find a new route in the network. When selecting LSPs on a congested link, fewer larger LSPs are selected improving load balance. Moreover, the bandwidth wastage was the overall lowest. In summary, the heuristic is very flexible and can be configured according to the network provider's best interest regarding the considered criteria.
シミュレーション結果は、先制が優先度に基づいている場合、先制されたLSPが先制をそれほど延長することができないため、カスケードは重要ではないことを示しています。LSPの数が考慮されると、LSPが少なくなり、再退場する可能性が高くなります。帯域幅の浪費が考慮されると、各リンクでより小さなLSPが先取りされ、無駄な帯域幅が低くなります。ヒューリスティックはこれらの機能を組み合わせているようで、特にブロッキング確率の場合に最良の結果をもたらします。ヒューリスティックがブロッキング確率（hblock）を最小限に抑えるように構成された場合、通常ロードされたリンクでの先制のために低い優先度の低いLSPが選択され、混雑したリンクで優先度が低い（より大きな）LSPが選択されました。優先度が低いため、カスケードは問題ではありませんでした。いくつかのLSPが先制のために選択されましたが、正常に再ルーティングされなかったLSPの速度は最低でした。LSPは小さいため、ネットワーク内で新しいルートを見つける方が簡単です。混雑したリンクでLSPを選択すると、LSPが選択されたLSPが少なくなり、負荷バランスが改善されます。さらに、帯域幅の無駄は全体的に最も低かった。要約すると、ヒューリスティックは非常に柔軟であり、考慮された基準に関するネットワークプロバイダーの最大の関心に従って構成できます。
For several cases, the failure of a link resulted in no preemption at all (all LSPs were able to find an alternate path in the network) or resulted in preemption of very few LSPs and subsequent successfully rerouting of the same with no cascading effect.
いくつかのケースでは、リンクの障害により、先制がまったくありませんでした（すべてのLSPはネットワーク内の代替パスを見つけることができました）、または非常に少数のLSPの先制を行い、その後、カスケード効果なしで同じものを正常に再ルーティングしました。
It is also important to note that for all policies in use, the number of extra hops when LSPs are rerouted was not critical, showing that preempted LSPs can be rerouted on a path with the same length or a path that is slightly longer in number of hops.
また、使用中のすべてのポリシーで、LSPが再ルーティングされたときの追加ホップの数は重要ではなく、先制的なLSPが同じ長さのパスまたはパスの数がわずかに長いパスで再ルーティングできることを示していることに注意することも重要です。ホップ。
The practice described in this document does not raise specific security issues beyond those of existing TE.
このドキュメントで説明されている慣行は、既存のTEの問題を超えた特定のセキュリティ問題を提起しません。
We would like to acknowledge the input and helpful comments from Francois Le Faucheur (Cisco Systems) and George Uhl (Swales Aerospace).
Francois Le Faucheur（Cisco Systems）とGeorge Uhl（Swales Aerospace）からの入力と有用なコメントを認めたいと思います。
[ATM-PREP] Poretsky, S. and Gannon, T., "An Algorithm for Connection Precedence and Preemption in Asynchronous Transfer Mode (ATM) Networks", Proceedings of IEEE ICC 1998.
[ATM-Prep] Poretsky、S。およびGannon、T。、「非同期転送モード（ATM）ネットワークでの接続の優先順位と先制のアルゴリズム」、IEEE ICC 1998の議事録。
[DEC-PREP] Peyravian, M. and Kshemkalyani, A. D. , "Decentralized Network Connection Preemption Algorithms", Computer Networks and ISDN Systems, vol. 30 (11), pp. 1029-1043, June 1998.
[Dec-Prep] Peyravian、M。and Kshemkalyani、A。D.、「分散型ネットワーク接続先制アルゴリズム」、コンピューターネットワークおよびISDN Systems、vol。30（11）、pp。1029-1043、1998年6月。
[PREEMPTION] de Oliveira, J. C. et al., "A New Preemption Policy for DiffServ-Aware Traffic Engineering to Minimize Rerouting", Proceedings of IEEE INFOCOM 2002.
[先制] De Oliveira、J。C. et al。、「再ルーティングを最小限に抑えるためのDiffserv-Aware Traffic Engineeringの新しい先制ポリシー」、IEEE Infocom 2002の議事録。
[RFC2702] Awduche, D., Malcolm, J., Agogbua, J., O'Dell, M., and J. McManus, "Requirements for Traffic Engineering Over MPLS", RFC 2702, September 1999.
[RFC2702] Awduche、D.、Malcolm、J.、Agogbua、J.、O'dell、M。、およびJ. McManus、「MPLS上のトラフィックエンジニアリングの要件」、RFC 2702、1999年9月。
[RFC3209] Awduche, D., Berger, L., Gan, D., Li, T., Srinivasan, V., and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP Tunnels", RFC 3209, December 2001.
[RFC3209] Awduche、D.、Berger、L.、Gan、D.、Li、T.、Srinivasan、V。、およびG. Swallow、「RSVP-TE：LSPトンネルのRSVPへの拡張」、RFC 3209、12月2001年。
[RFC3272] Awduche, D., Chiu, A., Elwalid, A., Widjaja, I., and X. Xiao, "Overview and Principles of Internet Traffic Engineering", RFC 3272, May 2002.
[RFC3272] Awduche、D.、Chiu、A.、Elwalid、A.、Widjaja、I。、およびX. Xiao、「インターネットトラフィックエンジニアリングの概要と原則」、RFC 3272、2002年5月。
[RFC3564] Le Faucheur, F. and W. Lai, "Requirements for Support of Differentiated Services-aware MPLS Traffic Engineering", RFC 3564, July 2003.
[RFC3564] Le Faucheur、F。およびW. Lai、「差別化されたサービス認識MPLSトラフィックエンジニアリングのサポートの要件」、RFC 3564、2003年7月。
[RFC4124] Le Faucheur, F., "Protocol Extensions for Support of Diffserv-aware MPLS Traffic Engineering", RFC 4124, June 2005.
[RFC4124] Le Faucheur、F。、「Diffserv-akeare MPLSトラフィックエンジニアリングのサポートのためのプロトコル拡張」、RFC 4124、2005年6月。
[RFC4126] Ash, J., "Max Allocation with Reservation Bandwidth Constraints Model for Diffserv-aware MPLS Traffic Engineering & Performance Comparisons", RFC 4126, June 2005.
[RFC4126] Ash、J。、「Diffserv-akeare MPLSトラフィックエンジニアリングとパフォーマンスの比較のための予約帯域幅制約モデルによる最大割り当て」、RFC 4126、2005年6月。
[RFC4127] Le Faucheur, F., "Russian Dolls Bandwidth Constraints Model for Diffserv-aware MPLS Traffic Engineering", RFC 4127, June 2005.
[RFC4127] Le Faucheur、F。、「Diffserv-aware MPLSトラフィックエンジニアリングのロシア人形帯域幅制約モデル」、RFC 4127、2005年6月。
[RFC4128] Lai, W., "Bandwidth Constraints Models for Differentiated Services (Diffserv)-aware MPLS Traffic Engineering: Performance Evaluation", RFC 4128, June 2005.
[RFC4128] Lai、W。、「差別化されたサービスの帯域幅制約モデル（DIFFSERV） - アウェアMPLSトラフィックエンジニアリング：パフォーマンス評価」、RFC 4128、2005年6月。
Authors' Addresses
著者のアドレス
Jaudelice C. de Oliveira (editor) Drexel University 3141 Chestnut Street (ECE Dept.) Philadelphia, PA 19104 USA
Jaudelice C. de Oliveira（編集者）Drexel University 3141 Chestnut Street（ECE Dept.）Philadelphia、PA 19104 USA
EMail: jau@ece.drexel.edu
JP Vasseur (editor) Cisco Systems, Inc. 1414 Massachusetts Avenue Boxborough, MA 01719 USA
JP Vasseur（編集者）Cisco Systems、Inc。1414 Massachusetts Avenue Boxborough、MA 01719 USA
EMail: jpv@cisco.com
Leonardo Chen Verizon Laboratories 40 Sylvan Rd. LA0MS55 Waltham, MA 02451 USA
レオナルド・チェン・ヴェリゾン研究所40 Sylvan Rd。LA0MS55ウォルサム、マサチューセッツ州02451 USA
EMail: leonardo.c.chen@verizon.com
Caterina Scoglio Kansas State University 2061 Rathbone Hall Manhattan, Kansas 66506-5204 USA
Caterina Scoglio Kansas State University 2061 Rathbone Hall Manhattan、カンザス66506-5204 USA
EMail: caterina@eece.ksu.edu
Full Copyright Statement
完全な著作権声明
Copyright (C) The IETF Trust (2007).
著作権（c）The IETF Trust（2007）。
This document is subject to the rights, licenses and restrictions contained in BCP 78 and at www.rfc-editor.org/copyright.html, and except as set forth therein, the authors retain all their rights.
この文書は、BCP 78およびwww.rfc-editor.org/copyright.htmlに含まれる権利、ライセンス、および制限の対象となり、そこに記載されている場合を除き、著者はすべての権利を保持します。
This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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.
このドキュメントとここに含まれる情報は、「現状のまま」に基づいて提供され、貢献者、彼/彼女が代表する組織（もしあれば）、インターネット協会、IETFトラスト、インターネットエンジニアリングタスクフォースがすべてを否認します。明示的または黙示的な保証。ここでの情報の使用は、特定の目的に対する商品性または適合性の権利または暗黙の保証を侵害しないという保証を含むがこれらに限定されない。
Intellectual Property
知的財産
The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79.
IETFは、知的財産権またはその他の権利の有効性または範囲に関して、本書に記載されている技術の実装または使用、またはそのような権利に基づくライセンスに基づくライセンスの範囲に関連すると主張される可能性のある他の権利に関しては、立場を取得しません。利用可能になります。また、そのような権利を特定するために独立した努力をしたことも表明していません。RFCドキュメントの権利に関する手順に関する情報は、BCP 78およびBCP 79に記載されています。
Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr.
IETF事務局に行われたIPR開示のコピーと、利用可能にするライセンスの保証、またはこの仕様の実装者またはユーザーによるそのような独自の権利の使用のための一般的なライセンスまたは許可を取得するための試みの結果を取得できます。http://www.ietf.org/iprのIETFオンラインIPRリポジトリから。
The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org.
IETFは、関心のある当事者に、著作権、特許、または特許出願、またはこの基準を実装するために必要なテクノロジーをカバーする可能性のあるその他の独自の権利を注意深く招待します。ietf-ipr@ietf.orgのIETFへの情報をお問い合わせください。
Acknowledgement
謝辞
Funding for the RFC Editor function is currently provided by the Internet Society.
RFCエディター機能の資金は現在、インターネット協会によって提供されています。