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
        

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)IETFトラスト(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はインターネットStandardのどんなレベルの候補ではありません。 IETFは、いかなる目的のために、このRFCのフィットネスの知識を放棄して、具体的には、公開する決定が展開されたプロトコルとセキュリティ、輻輳制御、または不適切な相互作用のようなもののためにIETFレビューに基づいていないことを指摘しています。 RFC Editorはその裁量でこの文書を公開することを選択しました。このドキュメントの読者は実現と展開のためにその値を評価する際に警戒する必要があります。詳細については、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を先取りします。 LSPの最小数を先取り。先取り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
        
1. Motivation
1.動機

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の対応の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の世界ではない必須の属性は、プリエンプションは、オンライン使用してネットワーク上で重要となりますが、帯域幅の断片化の影響を制限するために彼らのトラフィックエンジニアリングラベルスイッチパス(TE LSP)経路計算のための制約最短パスファースト(CSPF)戦略を配布しました。また、プリエンプションは、トラフィックが分化方法で処理され、高重要度のトラフィックが低い重要度トラフィック[DEC-PREP、ATM-PREP]上の特殊処理を施してもよいしたMPLSネットワークにおける魅力的な戦略です。それにも関わらず、その問題点と要件[RFC3564]で議論されているDS-TEのアプローチで、プリエンプションポリシーは、帯域予約および管理、パズルの重要な部分と考えられているが、ないプリエンプション戦略が定義されていません。プリエンプションはまた、(帯域幅の単一のプール付き)定期的なMPLSトラフィックエンジニアリング環境において重要な役割を果たしていることに注意してください。

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の数先取りする、先取り帯域幅の量は、ブロッキング確率:この文書は、様々なプリエンプション基準に異なる重みを与えるために調整することができる柔軟なプリエンプションポリシーを提案しています。基準の重要性の特定の順序を選択する意義(カスケード効果、帯域幅浪費、横取りLSPの優先)は、所与の例について議論されています。

2. Introduction
2.はじめに

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-クラス:対:

i. A Class-Type.

私。クラスタイプ。

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-Classは異なる先取り優先順位を使用するように、同じCTを使用して複数のTEクラスが存在してもよいです。また、同一の先取り優先順位を持つ複数のTEクラスがあってもよい、各TE-Classは異なるCTを使用することを条件とします。ネットワーク管理者は、特定のCT内プリエンプションを避けるために、または所望の場合、完全に、プリエンプションを避けるために、CTS、横切っプリエンプションをサポートするために、TE-クラスを定義してもよいです。コヒーレント動作を保証するために、同じTE-クラスは、すべてのラベルで構成されている必要がありDS-TEドメイン内のルータ(LSR)を交換。

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].

毎TEクラスの処理の結果として、インテリアゲートウェイプロトコル(IGP)が未予約帯域幅(UB)情報[RFC4124]で構成され、各TEクラスのための別個のトラフィックエンジニアリング情報をアドバタイズする必要があります。 UB情報は、プリエンプションが必要とされているかどうかを決定するために、帯域幅の制約モデルパラメータに対してチェックする、ルータによって使用されます。 UBの計算方法の詳細については、[RFC4124]に記載されています。

3. LSP Setup Procedure and Preemption
3. LSPのセットアップ手順とプリエンプション

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の数をプリエンプトします。より具体的には、目的関数は、以下の[DEC-PREP、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を先取り。優先度の高いトラフィックのサービス品質(QoS)は、より良い満足だろう、と下記のカスケード効果を制限することができます。

* 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のプリエンプションは、(いくつかのTE LSPのためのパスを見つけることができない)ブロッキングの確率を増加させる可能性がある再ルーティングされる帯域幅のより大きな量を意味しています。

* Preempt LSPs that minimize the blocking probability (risk that preempted TE LSP cannot be rerouted).

*ブロッキング確率(TE LSPを先取りリスクを再ルーティングすることはできません)を最小化する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).

[DEC-PREP]において、著者らは、重要度の所定の順序で論じ基準最適化接続プリエンプションポリシー提案:LSPの数、帯域幅、および優先度を、 LSPの帯域幅、優先順位、および数。我々のアプローチでの目新しさは、所望の基準を強調するために、サービスプロバイダによって調整することができ、目的関数を使用することです。いかなる特定の基準の順序は強制されません。また、新たな基準は、目的関数に追加される:(LSPをプリエンプトされた後に再ルーティングされていないというリスクを最小限にするために)ブロッキング確率を最適化します。

4. Preemption Cascading
4.プリエンプションカスケード

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章では、プリエンプションのシミュレーション結果を説明すると、カスケード効果を分析します。

5. Preemption Heuristic
5.プリエンプションヒューリスティック
5.1. Preempting Resources on a Path
5.1. パス上のリソースを先取り

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をプリエンプト)考慮される経路と重複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が故障にリルート、なぜなら新しいTE 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)のために用意されています。

5.2. Preemption Heuristic Algorithm
5.2. プリエンプションヒューリスティックアルゴリズム

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設定のための要求を考慮してください。プリエンプションは、利用可能なリソースの不足のために、必要とされる場合、プリエンプタブルLSPは、R = B-ABW(L)を適合させるために、下部保持先取り優先順位(高い数値)を持つものの中から選択されます。変数rは、プリエンプトされる必要がある実際の帯域幅(:ABW(L)要求、B、マイナスリンク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はPより(数値的に高い)低い保持先取り優先順位を有する活性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).

各先取り優先のコストを表現するために、逆保持先取り優先度P(L)に関係する関連コストY(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:

目的関数に関しては、4つの主要な目的は、先取りLSPの選択に到達することができます。

* 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)

H(L)=アルファY(L)+ベータ1 / B(L)+γ(B(L)-R)^ 2 +シータB(L)

In this equation:

この式において:

- alpha y(l) captures the cost of preempting high priority LSPs.

- アルファ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.

- シータB(L)大きいLSPを先取りのコストを捕捉します。

Coefficients alpha, beta, gamma, and theta can be chosen to emphasize one or more components of H.

係数アルファ、ベータ、ガンマ、及びシータはHの1つまたは複数の構成要素を強調するように選択することができます

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.

これは横取りLSPのブロッキング確率を最小化しようとすると、ヒューリスティックは、いくつかの小さなLSPを先取りに優先を与えるからである(従って、ガンマ、プリエンプトを最小化する量である、γ> 0の場合、係数シータは、そのシータ= 0と定義されます。要求された帯域幅の同様の量の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はプリエンプトするL.ザのLSPの各LSPのために計算されるRを収容するのに十分な帯域幅を追加小さなHを有するものとして選択されます。 HによりLSPをソートするとき、Hで同じ値を持つLSPは昇順で、帯域幅Bによって順序付けられます。繰り返さHと各LSPのために、アルゴリズムをチェックするかどうかLSPをrを満たすのに十分であることのみに割り当てられbの帯域幅。そのようなLSPが存在しない場合、それは以前に先取りのLSP帯域幅に加え、これらのLSPのそれぞれの帯域幅はRを満たすのに十分であるかどうかをチェックします。それはその繰り返しH-値シーケンス内の任意のLSPのために真でない場合、アルゴリズムは、シーケンス内の帯域幅のより大きな量を有し、そしてRが満たされているか、シーケンスが終了するまで、Bの順に先取りし続けるLSPをプリエンプト。シーケンスが完了し、rが満足でない場合、アルゴリズムは再度アルゴリズムについての詳細は[プリエンプション]に記載されているH.の昇順に基づいて先取りするLSPを選択します。

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).

プリエンプションが発生するようになっているリンクが正常にロードされている場合*、いくつかの小さなLSPはH(L)=アルファY(L)+シータB(L)を使用して、プリエンプションのために選択されるであろう。

* If the link is overloaded, few LSPs are selected using H(l)= alpha y(l) + beta 1/b(l).

*リンクが過負荷である場合、いくつかのLSPは、H(L)=アルファY(L)+ベータ1 / B(L)を使用して選択されます。

6. Examples
6.例
6.1. Simple Case: Single Link
6.1. シンプルなケース:シングルリンク

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 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.

優先度が唯一の重要な基準である場合、ネットワークオペレータは、α= 1、β=ガンマ=シータ= 0を設定します。この場合、LSPを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の数はできるだけ小さくなければならない)であるネットワークでは、1 = 1およびα=ガンマ=シータ= 0、βを設定することを好むかもしれません。 LSPをL9とL12は、次いで、185の帯域幅ユニット(前の場合より少ない消耗)まで添加すること、プリエンプションのために選択されるであろう。選択されたLSPの優先順位は、(再ルーティングするとき、彼らは自分たちが他のLSPを先取り可能性があることを意味する)3と5です。

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.

ネットワークオペレータは、設定することがより適切であると判断したと仮定し、α= 1、β= 10、ガンマ= 0、シータ= 0(パラメータがで、各構成要素、すなわち、優先度と数の重量のバランスを取ることになる値に設定しました。費用関数)このネットワークの再ルーティングでは非常に高価であるため、LSPの優先順位は重要ですが、帯域幅が重要な問題ではありません。この場合、LSPを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、γの3つのコンポーネントのバランスを達成するために、パラメータ正規化する必要があります。バランスを目指して、パラメータは、α= 1、β用語(Bの値をもたらし、そしてガンマ= 0.001((用語1 / B(L)他のパラメータに近いをもたらす)= 10(Lとして設定することができ)他のパラメータに)-r)^ 2に近いです。 LSP 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.

ブロッキング確率の最小化は、最も関心の基準である場合、費用関数は、シータ= 1、アルファ=ベータ=ガンマ= 0で構成することができます。その場合、いくつかの小さなLSPは先取りのために選択されるのLSP 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とを加算し、2を選択しました。

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.

ブロッキング確率は、関心の基準であった場合、いくつかの(8)小LSPは先取りしました。帯域幅の浪費は低いが、再ルーティングイベントの数が増加します。先取りLSPの帯域幅要件を考えると、各LSPのための新しいルートを見つける可能性が高くなることが予想されます。

6.2. Network Case
6.2. ネットワークケース

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.

これらの実験のために、私たちはOC48をしている、70%OC3をされているリンクの6. 10%の接続性の度合いを持っているトポロジ内のノードの3平均10%のネットワーク接続で150個のノードのトポロジを考慮し、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つのクラスが使用されている:音声のLSPとデータインターネット/ VPNのLSP。 TE LSP、プリエンプションのセット(各先取りのためのLSPの割合)及びサイズ分布のクラスごと(T LSPの合計が考慮される)以下の通りであります:

T: total number of TE LSPs in the network (T = 18,306 LSPs)

T:ネットワークにおけるTE LSPの総数(T = 18306件の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:

ネットワーク障害のイベントは、二つの機能をシミュレートしました。

- Constant: 1 failure chosen randomly among the set of links every 1 hour.

- 定数:1失敗はリンクのセットごとに1時間の間でランダムに選ばれました。

- Poisson process with interarrival average = 1 hour.

- 到着間の平均= 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:最も重要な基準として優先順位及び帯域幅を浪費とヒューリスティック(アルファ= 10、β= 0、γ= 0.001、シータ= 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:(重負荷リンク:アルファ= 1、β= 10):確率(アルファ= 1、β= 0、γ= 0、シータ= 0.01通常負荷リンク)ブロックの最小化を考慮ヒューリスティック。

HNB: The heuristic with number of preemptions and wasted bandwidth in consideration (alpha=0, beta=10, gamma=0.001, theta=0).

HNB:プリエンプションの数とを考慮して無駄な帯域幅(アルファ= 0、β= 10、ガンマ= 0.001、シータ= 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のより少ない数をもたらしました。より重要なことに、それはまた、全体的な小さな拒否率およびより小さい平均帯域幅の浪費をもたらした(第二全体小さい最悪の場合無駄な帯域幅。)

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を先取りしているため、それは、そうやってしまい、そのためには、更に多くのカスケード反映されません。カスケードは、全体的な最低(プリエンプションが、ポリシーPNの場合のプリエンプションのほとんどの2つのレベルで生じる)でした。平均最悪先取り優先順位は、(他のアルゴリズム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を先取りすることができたという事実に、他のケースよりも高かったです。 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の少数になりました。カスケードは低いですが、帯域幅の浪費は、(全体的な最高の帯域幅の浪費)が非常に高いです。また、再ルーティングが過小たネットワークの部分に起こったいくつかのケースでは、ヒューリスティック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は先取りのための優先度の低い(PNと比較して)LSPのより大きな数を選択し、したがって、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

シミュレーションの結果は、プリエンプションは、優先度に基づいている場合横取りするLSPは更に多くのプリエンプションを伝播することはできませんから、カスケードは重要ではないことを示しています。 LSPの数を考慮すると、より少ないLSPはプリエンプトと増加を再ルーティングする機会れます。帯域幅の浪費を考慮すると、小さな

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は、各リンクに横取りされており、無駄な帯域幅が低くなります。ヒューリスティックは、特に確率をブロックする場合には、最良の結果が得られ、これらの機能を組み合わせているようです。ヒューリスティックは、ブロッキング確率(HBlock)を最小化するように構成された場合、優先度の低い小さな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のが再ルーティングされ、余分なホップの数は重要ではなかったことに注意することも重要ですホップ。

7. Security Considerations
7.セキュリティの考慮事項

The practice described in this document does not raise specific security issues beyond those of existing TE.

この文献に記載の練習では、既存のTEのそれを超えて特定のセキュリティ上の問題を提起しません。

8. Acknowledgements
8.謝辞

We would like to acknowledge the input and helpful comments from Francois Le Faucheur (Cisco Systems) and George Uhl (Swales Aerospace).

私たちは、フランソワ・ル・Faucheur(シスコシステムズ)とジョージ・ユール(スウェールズエアロスペース)からの入力と有益なコメントを承認したいと思います。

9. Informative References
9.参考文献

[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.及びギャノン、T.、IEEE ICC 1998会報 "アン接続優先順位アルゴリズムとプリエンプションは、非同期転送モード(ATM)ネットワークで"。

[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.およびKshemkalyani、A. D.、 "分散型ネットワーク接続プリエンプションアルゴリズム"、コンピュータネットワークとISDNシステム、巻。 30(11)、頁。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.

【プリエンプション]オリベイラ、J. C.ら、IEEE INFOCOM 2002会報、「diffserv対応トラフィックエンジニアリングのための新しいプリエンプションポリシー再ルーティングを最小化するために」脱。

[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.、マルコム、J.、Agogbua、J.、オデル、M.、およびJ.マクマナス、 "トラフィックエンジニアリングオーバー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.、バーガー、L.、ガン、D.、李、T.、スリニヴァサン、V.、およびG.ツバメ、 "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.、チウ、A.、Elwalid、A.、Widjaja、I.、およびX.シャオ、 "インターネットトラフィックエンジニアリングの概要と原則"、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]ルFaucheur、F.およびW.ライ、 "差別化サービスを意識したMPLSトラフィックエンジニアリングのサポートのための要件"、RFC 3564、2003年7月。

[RFC4124] Le Faucheur, F., "Protocol Extensions for Support of Diffserv-aware MPLS Traffic Engineering", RFC 4124, June 2005.

[RFC4124]ルFaucheur、F.、 "Diffservの認識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]アッシュ、J.、RFC 4126「のDiffservを意識したMPLSトラフィックエンジニアリング&パフォーマンスの比較のための予約帯域幅の制約モデルによる最大配分」、2005年6月。

[RFC4127] Le Faucheur, F., "Russian Dolls Bandwidth Constraints Model for Diffserv-aware MPLS Traffic Engineering", RFC 4127, June 2005.

[RFC4127]ルFaucheur、F.、 "Diffservの認識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]ライ、W.は、 "差別化サービス(DiffServ)のための帯域幅制約モデルは、MPLSトラフィックエンジニアリングを-aware:性能評価"、RFC 4128、2005年6月。

Authors' Addresses

著者のアドレス

Jaudelice C. de Oliveira (editor) Drexel University 3141 Chestnut Street (ECE Dept.) Philadelphia, PA 19104 USA

Jaudelice C.・デ・オリベイラ(エディタ)ドレクセル大学3141チェスナットストリート(ECE部門)、フィラデルフィア、PA 19104 USA

EMail: jau@ece.drexel.edu

メールアドレス:jau@ece.drexel.edu

JP Vasseur (editor) Cisco Systems, Inc. 1414 Massachusetts Avenue Boxborough, MA 01719 USA

JP Vasseur(エディタ)シスコ・システムズ・インク1414年マサチューセッツアベニューボックスボロー、MA 01719 USA

EMail: jpv@cisco.com

メールアドレス:jpv@cisco.com

Leonardo Chen Verizon Laboratories 40 Sylvan Rd. LA0MS55 Waltham, MA 02451 USA

レオナルド・チェンベライゾンラボラトリーズ40シルバンRdを。 LA0MS55ウォルサム、MA 02451 USA

EMail: leonardo.c.chen@verizon.com

メールアドレス:leonardo.c.chen@verizon.com

Caterina Scoglio Kansas State University 2061 Rathbone Hall Manhattan, Kansas 66506-5204 USA

カテリーナScoglioのカンザス州立大学2061ラスボーンホールでマンハッタン、カンザス州66506から5204 USA

EMail: caterina@eece.ksu.edu

メールアドレス:caterina@eece.ksu.edu

Full Copyright Statement

完全な著作権声明

Copyright (C) The IETF Trust (2007).

著作権(C)IETFトラスト(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.

この文書とここに含まれている情報は、基礎とCONTRIBUTOR「そのまま」、ORGANIZATION HE / SHEが表すまたはインターネットSOCIETY、(もしあれば)を後援し、IETF TRUST ANDインターネットエンジニアリングタスクフォース放棄ALLに設けられています。保証は、明示または黙示、この情報の利用および特定目的に対する権利または商品性または適合性の黙示の保証を侵害しない任意の保証がこれらに限定されません。

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.

IPRの開示のコピーが利用できるようにIETF事務局とライセンスの保証に行われた、または本仕様の実装者または利用者がそのような所有権の使用のための一般的なライセンスまたは許可を取得するために作られた試みの結果を得ることができます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 Editor機能のための基金は現在、インターネット協会によって提供されます。