RFC2676 日本語訳
2676 QoS Routing Mechanisms and OSPF Extensions. G. Apostolopoulos, S.Kama, D. Williams, R. Guerin, A. Orda, T. Przygienda. August 1999. (Format: TXT=124563 bytes) (Status: EXPERIMENTAL)
プログラムでの自動翻訳です。
英語原文
Network Working Group G. Apostolopoulos
Request for Comments: 2676 D. Williams
Category: Experimental IBM
S. Kamat
Lucent
R. Guerin
UPenn
A. Orda
Technion
T. Przygienda
Siara Systems
August 1999
Apostolopoulosがコメントのために要求するワーキンググループG.をネットワークでつないでください: 2676年のD.ウィリアムズカテゴリ: R.ゲランUPenn A.オルダTechnion T.Przygienda Siaraシステム1999年8月に透明な実験的なIBM S.Kamat
QoS Routing Mechanisms and OSPF Extensions
QoSルート設定メカニズムとOSPF拡張子
Status of this Memo
このMemoの状態
This memo defines an Experimental Protocol for the Internet community. It does not specify an Internet standard of any kind. Discussion and suggestions for improvement are requested. Distribution of this memo is unlimited.
このメモはインターネットコミュニティのためにExperimentalプロトコルを定義します。 それはどんな種類のインターネット標準も指定しません。 議論と改善提案は要求されています。 このメモの分配は無制限です。
Copyright Notice
版権情報
Copyright (C) The Internet Society (1999). All Rights Reserved.
Copyright(C)インターネット協会(1999)。 All rights reserved。
Abstract
要約
This memo describes extensions to the OSPF [Moy98] protocol to support QoS routes. The focus of this document is on the algorithms used to compute QoS routes and on the necessary modifications to OSPF to support this function, e.g., the information needed, its format, how it is distributed, and how it is used by the QoS path selection process. Aspects related to how QoS routes are established and managed are also briefly discussed. The goal of this document is to identify a framework and possible approaches to allow deployment of QoS routing capabilities with the minimum possible impact to the existing routing infrastructure.
このメモは、QoSルートを支えるためにOSPF[Moy98]プロトコルに拡大について説明します。 この機能と、例えば必要である情報と、形式と、それがQoS経路選択工程でそれがどう分配されているか、そして、どう使用されるかをサポートするために、QoSルートを計算するのに使用されるアルゴリズムとOSPFへの必要な変更にはこのドキュメントの焦点があります。 また、簡潔にQoSルートがどう確立されて、管理されるかと関係づけられた局面について議論します。 このドキュメントの目標は最小の可能な衝撃でQoSルーティング能力の展開を既存のルーティングインフラストラクチャに許すために枠組みと可能なアプローチを特定することです。
In addition, experience from an implementation of the proposed extensions in the GateD environment [Con], along with performance measurements is presented.
中では、GateD環境[まやかし]における、提案された拡大の実現からの添加、性能測定に伴う経験は提示されます。
Apostolopoulos, et al. Experimental [Page 1] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[1ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
Table of Contents
目次
1. Introduction 3
1.1. Overall Framework . . . . . . . . . . . . . . . . . . . . 3
1.2. Simplifying Assumptions . . . . . . . . . . . . . . . . . 5
2. Path Selection Information and Algorithms 7
2.1. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2. Advertisement of Link State Information . . . . . . . . . 8
2.3. Path Selection . . . . . . . . . . . . . . . . . . . . .10
2.3.1. Path Computation Algorithm . . . . . . . . . . .11
3. OSPF Protocol Extensions 16
3.1. QoS -- Optional Capabilities . . . . . . . . . . . . . .17
3.2. Encoding Resources as Extended TOS . . . . . . . . . . .17
3.2.1. Encoding bandwidth resource . . . . . . . . . . .19
3.2.2. Encoding Delay . . . . . . . . . . . . . . . . .21
3.3. Packet Formats . . . . . . . . . . . . . . . . . . . . .21
3.4. Calculating the Inter-area Routes . . . . . . . . . . . .22
3.5. Open Issues . . . . . . . . . . . . . . . . . . . . . . .22
4. A Reference Implementation based on GateD 22
4.1. The Gate Daemon (GateD) Program . . . . . . . . . . . . .22
4.2. Implementing the QoS Extensions of OSPF . . . . . . . . .23
4.2.1. Design Objectives and Scope . . . . . . . . . . .23
4.2.2. Architecture . . . . . . . . . . . . . . . . . .24
4.3. Major Implementation Issues . . . . . . . . . . . . . . .25
4.4. Bandwidth and Processing Overhead of QoS Routing . . . .29
5. Security Considerations 32
A. Pseudocode for the BF Based Pre-Computation Algorithm 33
B. On-Demand Dijkstra Algorithm for QoS Path Computation 36
C. Precomputation Using Dijkstra Algorithm 39
D. Explicit Routing Support 43
Endnotes 45
References 46
Authors' Addresses 48
Full Copyright Statement 50
1. 序論3 1.1。 総合的な枠組み. . . . . . . . . . . . . . . . . . . . 3 1.2。 仮定. . . . . . . . . . . . . . . . . 5 2を簡素化します。 経路選択情報とアルゴリズム7 2.1。 測定基準. . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2。 リンク州の情報. . . . . . . . . 8 2.3の広告。 経路選択. . . . . . . . . . . . . . . . . . . . .10 2.3.1。 経路計算アルゴリズム. . . . . . . . . . .11 3。 OSPFは拡大16 3.1について議定書の中で述べます。 QoS--任意の能力. . . . . . . . . . . . . .17 3.2。 拡張TOS. . . . . . . . . . .17 3.2.1としてリソースをコード化します。 帯域幅リソース. . . . . . . . . . .19 3.2.2をコード化します。 遅れ. . . . . . . . . . . . . . . . .21 3.3をコード化します。 パケット・フォーマット. . . . . . . . . . . . . . . . . . . . .21 3.4。 相互領域ルート. . . . . . . . . . . .22 3.5を計算します。 問題. . . . . . . . . . . . . . . . . . . . . . .22 4を開いてください。 リファレンスインプリメンテーションはGateD22 4.1を基礎づけました。 ゲートデーモン(外出を禁止される)プログラム. . . . . . . . . . . . .22 4.2。 OSPF. . . . . . . . .23 4.2.1のQoS拡張子を実行します。 目的と範囲. . . . . . . . . . .23 4.2.2を設計してください。 構造. . . . . . . . . . . . . . . . . .24 4.3。 主要な導入問題. . . . . . . . . . . . . . .25 4.4。 QoSルート設定. . . .29 5の帯域幅と処理オーバヘッド。 BFがダイクストラAlgorithm39のD.の明白なルート設定サポート43エンドノート45参照46作者のものを使用することでQoS経路計算36C.Precomputationのためのプレ計算アルゴリズムの33のB.の要求次第のダイクストラアルゴリズムを基礎づけたので、セキュリティ問題32A.擬似コードは48の完全な著作権宣言文50を記述します。
Apostolopoulos, et al. Experimental [Page 2] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[2ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
1. Introduction
1. 序論
In this document, we describe a set of proposed additions to the OSPF routing protocol (these additions have been implemented on top of the GateD [Con] implementation of OSPF V2 [Moy98]) to support Quality- of-Service (QoS) routing in IP networks. Support for QoS routing can be viewed as consisting of three major components:
本書では、私たちは、IPネットワークでサービスのQuality(QoS)ルーティングを支持するためにOSPFルーティング・プロトコル(これらの追加はOSPF V2[Moy98]のGateD[まやかし]実現の上で実行された)に1セットの提案された追加を説明します。 3個の主要コンポーネントから成るとQoSルーティングのサポートを見なすことができます:
1. Obtain the information needed to compute QoS paths and select a
path capable of meeting the QoS requirements of a given request,
1. QoS経路を計算して、与えられた要求に関するQoS必要条件を満たすことができる経路を選択するのに必要である情報を得てください。
2. Establish the path selected to accommodate a new request,
2. 新しい要求に対応するのが選択された経路を確立してください。
3. Maintain the path assigned for use by a given request.
3. 使用のために与えられた要求で割り当てられた経路を維持してください。
Although we touch upon aspects related to the last two components, the focus of this document is on the first one. In particular, we discuss the metrics required to support QoS, the extension to the OSPF link state advertisement mechanism to propagate updates of QoS metrics, and the modifications to the path selection to accommodate QoS requests. The goal of the extensions described in this document is to improve performance for QoS flows (likelihood to be routed on a path capable of providing the requested QoS), with minimal impact on the existing OSPF protocol and its current implementation. Given the inherent complexity of QoS routing, achieving this goal obviously implies trading-off "optimality" for "simplicity", but we believe this to be required in order to facilitate deployment of QoS routing capabilities.
私たちは最後の2つのコンポーネントに関連する局面に触れますが、このドキュメントの焦点が最初のものにあります。 特に、私たちは、QoS要求に対応するためにOSPFリンク州の広告メカニズムにQoS、拡大を支持するのにQoS測定基準のアップデート、および経路選択への変更を伝播するのに必要である測定基準について議論します。 本書では説明された拡大の目標はQoS流れ(要求されたQoSを提供できる経路で発送されるべき見込み)のために性能を向上させることです、既存のOSPFプロトコルへの最小量の影響とその現在の実現で。 QoSルーティングの固有の複雑さを考えて、この目標を達成すると、下に取り引き「最適」は「簡単さ」のために明らかに含意されますが、私たちは、QoSルーティング能力の展開を容易にするためにこれが必要であると信じています。
In addition to describing the proposed extensions to the OSPF protocol, this document also reports experimental data based on performance measurements of an implementation done on the GateD platform (see Section 4).
また、提案された拡大についてOSPFプロトコルに説明することに加えて、このドキュメントはGateDプラットホームで行われた実現の性能測定に基づく実験データを報告します(セクション4を見てください)。
1.1. Overall Framework
1.1. 総合的な枠組み
We consider a network (1) that supports both best-effort packets and packets with QoS guarantees. The way in which the network resources are split between the two classes is irrelevant, except for the assumption that each QoS capable router in the network is able to dedicate some of its resources to satisfy the requirements of QoS packets. QoS capable routers are also assumed capable of identifying and advertising resources that remain available to new QoS flows. In addition, we limit ourselves to the case where all the routers involved support the QoS extensions described in this document, i.e., we do not consider the problem of establishing a route in a heterogeneous environment where some routers are QoS-capable and others are not. Furthermore, in this document, we focus on the case
私たちは、ネットワークがQoS保証でベストエフォート型パケットとパケットの両方を支持する(1)であると考えます。 ネットワーク資源が2つのクラスの間で分けられる方法は無関係です、ネットワークにおけるそれぞれのQoSのできるルータがQoSパケットの要件を満たすためにリソースのいくつかを捧げることができるという仮定を除いて。 また、QoSのできるルータは新しいQoS流れに利用可能なままで残っているリソースは特定して、広告を出すことができると思われます。 さらに、私たちは自分達をすべてのルータがQoS拡張子が本書では説明したサポートにかかわったケースに制限します、すなわち、ルートを異機種混在環境に確立するといういくつかのルータがQoSできて、他のものができない問題を考えません。 その上、本書では、私たちはケースに焦点を合わせます。
Apostolopoulos, et al. Experimental [Page 3] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[3ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
of unicast flows, although many of the additions we define are applicable to multicast flows as well.
ユニキャスト流れでは、多くですが、私たちが定義する追加はまた、マルチキャスト流れに適切です。
We assume that a flow with QoS requirements specifies them in some fashion that is accessible to the routing protocol. For example, this could correspond to the arrival of an RSVP [RZB+97] PATH message, whose TSpec is passed to routing together with the destination address. After processing such a request, the routing protocol returns the path that it deems the most suitable given the flow's requirements. Depending on the scope of the path selection process, this returned path could range from simply identifying the best next hop, i.e., a hop-by-hop path selection model, to specifying all intermediate nodes to the destination, i.e., an explicit route model. The nature of the path being returned impacts the operation of the path selection algorithm as it translates into different requirements for constructing and returning the appropriate path information. However, it does not affect the basic operation of the path selection algorithm (2).
私たちは、QoS要件がある流れがルーティング・プロトコルにアクセスしやすい何らかのファッションでそれらを指定すると思います。 例えば、これはRSVP[RZB+97]PATHメッセージの到着に対応できました。(メッセージのTSpecは送付先アドレスと共にルーティングに渡されます)。 そのような要求を処理した後に、ルーティング・プロトコルは流れの要件を考えて、それが最も適当であると考える経路を返します。 経路選択の過程の範囲によって、この返された経路は単に次の最も良いホップを特定するので、及ぶことができました、すなわち、ホップごとの経路選択モデル、すべての中間的ノードを目的地に指定するのに、すなわち、明白なルートモデル。 適切な経路情報を構成して、返すための異なった要件に翻訳するとき、返される経路の本質は経路選択アルゴリズムの操作に影響を与えます。 しかしながら、それは経路選択アルゴリズム(2)の基本的な操作に影響しません。
For simplicity and also because it is the model currently supported in the implementation (see Section 4 for details), in the rest of this document we focus on the hop-by-hop path selection model. The additional modifications required to support an explicit routing model are discussed in appendix D, but are peripheral to the main focus of this document which concentrates on the specific extensions to the OPSF protocol to support computation of QoS routes.
簡単さ、また、それが現在実現でサポートされているモデル(詳細に関してセクション4を見る)であるので、このドキュメントの残りでは、私たちはホップごとの経路選択モデルに焦点を合わせます。 明白なルーティングモデルをサポートするのに必要である追加変更は、付録Dで議論しますが、QoSルートの計算を支持するためにOPSFプロトコルへの特定の拡大に集中するこのドキュメントの主な焦点に周囲です。
In addition to the problem of selecting a QoS path and possibly reserving the corresponding resources, one should note that the successful delivery of QoS guarantees requires that the packets of the associated "QoS flow" be forwarded on the selected path. This typically requires the installation of corresponding forwarding state in the router. For example, with RSVP [RZB+97] flows a classifier entry is created based on the filter specs contained in the RESV message. In the case of a Differentiated Service [KNB98] setting, the classifier entry may be based on the destination address (or prefix) and the corresponding value of the DS byte. The mechanisms described in this document are at the control path level and are, therefore, independent of data path mechanisms such as the packet classification method used. Nevertheless, it is important to notice that consistent delivery of QoS guarantees implies stability of the data path. In particular, while it is possible that after a path is first selected, network conditions change and result in the appearance of "better" paths, such changes should be prevented from unnecessarily affecting existing paths. In particular, switching over to a new (and better) path should be limited to specific conditions, e.g., when the initial selection turns out to be inadequate or extremely "expensive". This aspect is beyond the scope
QoS経路を選択して、ことによると対応するリソースを予約するという問題に加えて、QoS保証のうまくいっている配送が、関連「QoS流動」のパケットが選択された経路で進められるのを必要とすることに注意するべきです。 これはルータにおける、対応する推進状態のインストールを通常必要とします。 例えば、RSVP[RZB+97]流れで、クラシファイアエントリーはRESVメッセージに含まれたフィルタ仕様に基づいて作成されます。 Differentiated Service[KNB98]設定の場合では、クラシファイアエントリーは送付先アドレス(または、接頭語)とDSバイトの換算値に基づくかもしれません。 本書では説明されたメカニズムは、コントロール経路レベルにあって、したがって、方法が使用したパケット分類などのデータ経路メカニズムから独立しています。 それにもかかわらず、QoS保証の一貫した配送がデータ経路の安定性を含意するのに気付くのは重要です。 経路が最初に選択された後に、ネットワーク状態が「より良い」経路の外観を変えて、もたらすのが、可能である間、特に、そのような変化は不必要に既存の経路に影響するのが防がれるべきです。 特に、新しくて(より良い)の経路に切り替わるのは一定の条件に制限されるべきです、例えば、初期の選択が不十分であるか非常に「高価である」と判明すると。 この局面は範囲を超えています。
Apostolopoulos, et al. Experimental [Page 4] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[4ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
of QoS routing and belongs to the realm of path management, which is outside the main focus of this document. However, because of its potentially significant impact on the usefulness of QoS routing, we briefly outline a possible approach to path management.
QoSが経路管理を分野に発送して、属させるのについて。(このドキュメントの主な焦点の外に管理があります)。 しかしながら、QoSルーティングの有用性への潜在的に重要な影響のために、私たちは簡潔に経路管理への可能なアプローチについて概説します。
Avoiding unnecessary changes to QoS paths requires that state information be maintained for each QoS path after it has been selected. This state information is used to track the validity of the path, i.e., is the current path adequate or should QoS routing be queried again to generate a new and potentially better path. We say that a path is "pinned" when its state specifies that QoS routing need not be queried anew, while a path is considered "un-pinned" otherwise. The main issue is then to define how, when, and where path pinning and un-pinning is to take place, and this will typically depend on the mechanism used to request QoS routes. For example, when the RSVP protocol is the mechanism being used, it is desirable that path management be kept as synergetic as possible with the existing RSVP state management. In other words, pinning and un- pinning of paths should be coordinated with RSVP soft states, and structured so as to require minimal changes to RSVP processing rules. A broad RSVP-routing interface that enables this is described in [GKR97]. Use of such an interface in the context of reserving resources along an explicit path with RSVP is discussed in [GLG+97]. Details of path management and a means for avoiding loops in case of hop-by-hop path setup can be found in [GKH97], and are not addressed further in this document.
QoS経路への不要な変化を避けるのは、それが選択された後に州の情報がそれぞれのQoS経路に保守されるのを必要とします。 この州の情報が経路の正当性を追跡するのに使用されますか、すなわち、現在の経路が適切ですか、またはQoSルーティングは、新しくて潜在的により良い経路を発生させるように再び質問されるべきですか? 私たちは、州が、QoSルーティングが新たに質問される必要はないと指定すると経路が「ピンで止められる」と言います、経路は別の方法で「不-ピンで止められた」状態で考えられますが。 本題はそして、経路のピンで止めるのと不-のピンで止めることが行われることになっていて、これがQoSルートを要求するのに使用されるメカニズムに通常よる時間と場所でその方法を定義することです。 RSVPプロトコルが使用されるメカニズムであるときに、例えば、経路管理ができるだけ既存のRSVP国家管理で相乗に維持されるのは、望ましいです。 言い換えれば、経路をピンで止めるのと不-のピンで止めることは、RSVP処理規則への最小量の変化を必要とするようにRSVP軟性国家で調整されて、構造化されるべきです。 これを可能にする広いRSVP-ルーティングインタフェースは[GKR97]で説明されます。 [GLG+97]でRSVPがある明白な経路に沿った予約リソースの文脈におけるそのようなインタフェースの使用について議論します。 ホップごとの経路セットアップの場合に輪を避けるための経路管理の細部と手段は、[GKH97]で見つけることができて、さらに本書では記述されません。
1.2. Simplifying Assumptions
1.2. 仮定を簡素化します。
In order to achieve our goal of minimizing impact to the existing protocol and implementation, we impose certain restrictions on the range of extensions we initially consider to support QoS. The first restriction is on the type of additional (QoS) metrics that will be added to Link State Advertisements (LSAs) for the purpose of distributing metrics updates. Specifically, the extensions to LSAs that we initially consider, include only available bandwidth and delay. In addition, path selection is itself limited to considering only bandwidth requirements. In particular, the path selection algorithm selects paths capable of satisfying the bandwidth requirement of flows, while at the same time trying to minimize the amount of network resources that need to be allocated, i.e., minimize the number of hops used.
既存のプロトコルと実現に衝撃を最小にするという私たちの目標を達成するために、私たちは私たちが初めはQoSを支持すると考える拡大の範囲に、ある制限を課します。 測定基準アップデートを広げる目的のためにLink州Advertisements(LSAs)に加えられる追加(QoS)測定基準のタイプの上に最初の制限があります。 明確に私たちが初めは考えるLSAsへの拡大は利用可能な帯域幅と遅れだけを含んでいます。 さらに、唯一の帯域幅が要件であると考えるのに経路選択は制限されます。 すなわち、同時にそうしなければならないネットワーク資源の量を最小にしていようとしている間、流れに関する帯域幅要件を満たすことができる経路がアルゴリズムが選択する経路選択であることを割り当てて、特に、使用されるホップの数を最小にしてください。
This focus on bandwidth is adequate in most instances, and meant to keep initial complexity at an acceptable level. However, it does not fully capture the complete range of potential QoS requirements. For example, a delay-sensitive flow of an interactive application could be put on a path using a satellite link, if that link provided a
帯域幅のこの焦点は、ほとんどの例で適切であり、合格水準における初期の複雑さを保つことになっています。 しかしながら、それは完全に潜在的QoS要件の全種類を得るというわけではありません。 例えば、衛星中継を使用することで対話型アプリケーションの遅れ敏感な流れを経路に置くことができるでしょう、そのリンクがaを提供したなら
Apostolopoulos, et al. Experimental [Page 5] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[5ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
direct path and had plenty of unused bandwidth. This would clearly be an undesirable choice. Our approach to preventing such poor choices, is to assign delay-sensitive flows to a "policy" that would eliminate from the network all links with high propagation delay, e.g., satellite links, before invoking the path selection algorithm. In general, multiple policies could be used to capture different requirements, each presenting to the path selection algorithm a correspondingly pruned network topology, on which the same algorithm would be used to generate an appropriate path. Alternatively, different algorithms could be used depending on the QoS requirements expressed by an incoming request. Such extensions are beyond the scope of this document, which limits itself to describing the case of a single metric, bandwidth. However, it is worth pointing out that a simple extension to the path selection algorithm proposed in this document allows us to directly account for delay, under certain conditions, when rate-based schedulers are employed, as in the Guaranteed Service proposal [SPG97]; details can be found in [GOW97].
経路を指示して、多くの未使用の帯域幅を持っていました。 これは明確に望ましくない選択でしょう。 そのような不十分な選択を防ぐことへの私たちのアプローチは遅れ敏感な流れを割り当てるために、そうする「方針」にすべてにネットワークから排泄されているということです。高い伝播とのリンクは延着します、例えば、衛星中継、経路選択アルゴリズムを呼び出す前に。 一般に、異なった要件を得るのに複数の方針を使用できました、それぞれ対応する剪定されたネットワーク形態(同じアルゴリズムは適切な経路を発生させるのに使用される)を経路選択アルゴリズムに提示して。 あるいはまた、入って来る要求で言い表されたQoS要件によって、異なったアルゴリズムを使用できました。 そのような拡大はこのドキュメントの範囲を超えています、帯域幅。ドキュメントはそれ自体をシングルに関するケースについて説明するのにメートル法で制限します。 しかしながら、私たちが本書では提案された経路選択アルゴリズムへの単純拡大で直接遅れを説明できると指摘する価値があります、一定の条件の下で、レートベースのスケジューラが採用しているとき、Guaranteed Service提案[SPG97]のように。 [GOW97]で詳細を見つけることができます。
Another important aspect to ensure that introducing support for QoS routing has the minimal possible impact, is to develop a solution that has the smallest possible computing overhead. Additional computations are unavoidable, but it is desirable to keep the computational cost of QoS routing at a level comparable to that of traditional routing algorithms. One possible approach to achieve this goal, is to allow pre-computation of QoS routes. This is the method that was chosen for the implementation of the QoS extensions to OSPF and is, therefore, the one described in detail in this document. Alternative approaches are briefly reviewed in appendices. However, it should be noted that although several alternative path selection algorithms are possible, the same algorithm should be used consistently within a given routing domain. This requirement may be relaxed when explicit routing is used, as the responsibility for selecting a QoS path lies with a single entity, the origin of the request, which then ensures consistency even if each router uses a different path selection algorithm. Nevertheless, the use of a common path selection algorithm within an AS is recommended, if not necessary, for proper operation.
QoSルーティングのサポートを導入しながらそれを確実にする別の重要な一面は、最小量の可能な影響力を持って、可能な限り少ないコンピューティングオーバーヘッドを持っている解決策を見いだすことです。 追加計算は避けられないのが、QoSルートのプレ計算を許すそれだけがこの目標を達成するために伝統的なルーティング・アルゴリズム1つの可能なアプローチのものに匹敵するレベルでQoSルーティングのコンピュータの費用を保つのにおいて望ましいことであるということです。 これは、OSPFへのQoS拡張子の実現に選ばれた方法であり、したがって、詳細に本書では説明されたものです。 代替的アプローチは付録で簡潔に見直されます。 しかしながら、いくつかの迂回経路選択アルゴリズムが可能ですが、同じアルゴリズムが与えられた経路ドメインの中で一貫して使用されるべきであることに注意されるべきです。 明白なルーティングが使用されているとき、この要件はリラックスするかもしれません、QoS経路を選択することへの責任が単一体、次に各ルータが異なった経路選択アルゴリズムを使用しても一貫性を確実にする要求の起源にあるとき。 それにもかかわらず、ASの中の共通路選択アルゴリズムの使用が、お勧めである、または適切な操作に必要です。
A last aspect of concern regarding the introduction of QoS routing, is to control the overhead associated with the additional link state updates caused by more frequent changes to link metrics. The goal is to minimize the amount of additional update traffic without adversely affecting the performance of path selection. In Section 2.2, we present a brief discussion of various alternatives that trade accuracy of link state information for protocol overhead. Potential enhancements to the path selection algorithm, which seek to (directly) account for the inaccuracies in link metrics, are described in [GOW97], while a comprehensive treatment of the subject
QoSの導入に関する心配の最後の局面が掘られて、コントロールには引き起こされる追加リンク州のアップデートに関連しているオーバーヘッドが測定基準をリンクするより頻繁な変化でありますか? 目標は経路選択の性能に悪影響を与えないで追加アップデート交通の量を最小にすることです。 セクション2.2では、私たちはプロトコルオーバーヘッドのためのリンク州の情報のその貿易精度を様々な代替手段の簡潔な議論に提示します。 潜在的増進((直接)リンク測定基準の誤りを説明しようとする)は[GOW97]に経路選択アルゴリズムに説明されます、対象の包括的な処理である間
Apostolopoulos, et al. Experimental [Page 6] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[6ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
can be found in [LO98, GO99]. In Section 4, we also describe the design choices made in a reference implementation, to allow future extensions and experimentation with different link state update mechanisms.
[LO98、GO99]で見つけることができます。 また、セクション4では、私たちは異なったリンク州のアップデートメカニズムによる今後の拡大と実験を許すために参照実現でされたデザイン選択について説明します。
The rest of this document is structured as follows. In Section 2, we describe the general design choices and mechanisms we rely on to support QoS request. This includes details on the path selection metrics, link state update extensions, and the path selection algorithm itself. Section 3 focuses on the specific extensions that the OSPF protocol requires, while Section 4 describes their implementation in the GateD platform and also presents some experimental results. Section 5 briefly addresses security issues that the proposed schemes may raise. Finally, several appendices provide additional material of interest, e.g., alternative path selection algorithms and support for explicit routes, but somewhat outside the main focus of this document.
このドキュメントの残りは以下の通り構造化されます。 セクション2では、私たちはQoSが要求するサポートに依存する一般的なデザイン選択とメカニズムについて説明します。 これは経路選択測定基準、リンク州のアップデート拡大、および経路選択アルゴリズム自体に関する詳細を含んでいます。 セクション3はOSPFプロトコルが必要とする特定の拡大に焦点を合わせます、セクション4は、GateDプラットホームの中で彼らの実現について説明して、また、いくつかの実験結果を提示しますが。 セクション5は簡潔に、提案された計画が提起するかもしれない安全保障問題を記述します。 最終的に、興味がある追加材料、例えば、迂回経路選択に明白なルートのアルゴリズムとサポートを提供しますが、数個の付録はこのドキュメントの主な焦点のいくらか外でそうします。
2. Path Selection Information and Algorithms
2. 経路選択情報とアルゴリズム
This section reviews the basic building blocks of QoS path selection, namely the metrics on the which the routing algorithm operates, the mechanisms used to propagate updates for these metrics, and finally the path selection algorithm itself.
このセクションがすなわち、QoS経路選択、測定基準の基本的なブロックを見直す、ルーティング・アルゴリズムが操作するもの、メカニズムは以前はよくこれらの測定基準のためのアップデート、および最終的に経路選択アルゴリズム自体を伝播していました。
2.1. Metrics
2.1. 測定基準
The process of selecting a path that can satisfy the QoS requirements of a new flow relies on both the knowledge of the flow's requirements and characteristics, and information about the availability of resources in the network. In addition, for purposes of efficiency, it is also important for the algorithm to account for the amount of resources the network has to allocate to support a new flow. In general, the network prefers to select the "cheapest" path among all paths suitable for a new flow, and it may even decide not to accept a new flow for which a feasible path exists, if the cost of the path is deemed too high. Accounting for these aspects involves several metrics on which the path selection process is based. They include:
新しい流れのQoS要件を満たすことができる経路を選択する過程は流れの要件と特性に関する知識とネットワークにおける、リソースの有用性の情報の両方を当てにします。 また、さらに、効率の目的のために、アルゴリズムがネットワークが新しい流れを支持するために割り当てなければならないリソースの量を説明するのも、重要です。 一般に、ネットワークは、新しい流れに適したすべての経路の中で「最も安い」経路を選択するのを好みます、そして、実行可能経路が存在する新しい流れを受け入れないと決めさえするかもしれません、経路の費用が高過ぎると考えられるなら。 これらの局面のための会計は経路選択の過程が基づいているいくつかの測定基準にかかわります。 それらは:
- Link available bandwidth: As mentioned earlier, we currently
assume that most QoS requirements are derivable from a rate-
related quantity, termed "bandwidth." We further assume that
associated with each link is a maximal bandwidth value, e.g., the
link physical bandwidth or some fraction thereof that has been set
aside for QoS flows. Since for a link to be capable of accepting
a new flow with given bandwidth requirements, at least that much
bandwidth must be still available on the link, the relevant link
metric is, therefore, the (current) amount of available (i.e.,
- 利用可能な帯域幅をリンクしてください: 先に述べたように、私たちは、現在、ほとんどのQoS要件が「帯域幅」と呼ばれたレートの関連する量から誘導できると思います。 私たちは、各リンクに関連づけられているのが、最大限度の帯域幅値、例えば、リンクの物理的な帯域幅であるかそれのQoSのためにかたわらに置かれた何らかの断片が流れるとさらに思います。 すなわちしたがって、以来メートル法であることが、リンクが多くの帯域幅がリンク、関連リンクでまだ少なくとも、利用可能でなければならないという与えられた帯域幅要件で新しい流れを受け入れることができるためには、利用可能の(現在)の量である、(。
Apostolopoulos, et al. Experimental [Page 7] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[7ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
unallocated) bandwidth. Changes in this metric need to be
advertised as part of extended LSAs, so that accurate information
is available to the path selection algorithm.
「非-割り当て」、)、帯域幅。 この拡張LSAsの一部として広告を出すべきメートル法の必要性における変化によって、その的確な情報は経路選択アルゴリズムに利用可能です。
- Link propagation delay: This quantity is meant to identify high
latency links, e.g., satellite links, which may be unsuitable for
real-time requests. This quantity also needs to be advertised as
part of extended LSAs, although timely dissemination of this
information is not critical as this parameter is unlikely to
change (significantly) over time. As mentioned earlier, link
propagation delay can be used to decide on the pruning of specific
links, when selecting a path for a delay sensitive request; also,
it can be used to support a related extension, as described in
[GOW97].
- 伝播遅延をリンクしてください: この量は高い潜在リンク、例えばリアルタイムの要求に、不適当であるかもしれない衛星中継を特定することになっています。 また、この量は、拡張LSAsの一部として広告を出す必要があります、このパラメタが時間がたつにつれて変化しそうにないので(かなり)、この情報のタイムリーな普及は批判的ではありませんが。 特定の刈り込みのときに遅れのために経路を選択するとき、決めるのにより早く言及されたリンク伝播遅延を使用できるように、機密の要求はリンクされています。 また、関連する拡大を支持するのに[GOW97]で説明されるようにそれを使用できます。
- Hop-count: This quantity is used as a measure of the path cost to
the network. A path with a smaller number of hops (that can
support a requested connection) is typically preferable, since it
consumes fewer network resources. As a result, the path selection
algorithm will attempt to find the minimum hop path capable of
satisfying the requirements of a given request. Note that
contrary to bandwidth and propagation delay, hop count is a metric
that does not affect LSAs, and it is only used implicitly as part
of the path selection algorithm.
- ホップカウント: この量はネットワークへの経路費用の基準として使用されます。 より少ない数のホップ(それは要求された接続を支持できる)がある経路は通常望ましいです、より少ないネットワーク資源を消費するので。 その結果、経路選択アルゴリズムは、最小のホップ経路が与えられた要求の要件を満たすことができるのがわかるのを試みるでしょう。 逆に、帯域幅と伝播遅延、ホップカウントに、LSAsに影響しないaがメートル法であり、それが経路選択アルゴリズムの一部としてそれとなく使用されるだけであることに注意してください。
2.2. Advertisement of Link State Information
2.2. リンク州の情報の広告
The new link metrics identified in the previous section need to be advertised across the network, so that each router can compute accurate and consistent QoS routes. It is assumed that each router maintains an updated database of the network topology, including the current state (available bandwidth and propagation delay) of each link. As mentioned before, the distribution of link state (metrics) information is based on extending OSPF mechanisms. The detailed format of those extensions is described in Section 3, but in addition to how link state information is distributed, another important aspect is when such distribution is to take place.
前項で特定された新しいリンク測定基準は、ネットワークの向こう側に広告を出す必要があります、各ルータが正確で一貫したQoSルートを計算できるように。 各ルータがネットワーク形態のアップデートされたデータベースを維持すると思われます、それぞれのリンクの現状(利用可能な帯域幅と伝播遅延)を含んでいて。 以前言及されるように、リンク州(測定基準)の情報の分配はOSPFメカニズムを広げるのに基づいています。それらの拡大の詳細な形式はセクション3で説明されますが、リンク州の情報がどう分配されているかに加えて、別の重要な一面はそのような分配が行われることになっている時。
One option is to mandate periodic updates, where the period of updates is determined based on a tolerable corresponding load on the network and the routers. The main disadvantage of such an approach is that major changes in the bandwidth available on a link could remain unknown for a full period and, therefore, result in many incorrect routing decisions. Ideally, routers should have the most current view of the bandwidth available on all links in the network, so that they can make the most accurate decision of which path to select. Unfortunately, this then calls for very frequent updates, e.g., each time the available bandwidth of a link changes, which is
1つのオプションは周期的なアップデートを強制することです、アップデートの一区切りがネットワークの許容できる対応する負荷とルータに基づいて決定しているところで。 そのようなアプローチの主な不都合はリンクで利用可能な帯域幅の大きな変化が完全な期間、未知のままで残っていて、したがって、多くの不正確なルーティング決定をもたらすかもしれないということです。 理想的に、ルータはネットワークですべてのリンクで利用可能な帯域幅の最も現在の視点を持つべきです、どの経路を選択したらよいかに関する最も正確な決定をすることができるように。 残念ながら、次に、これは非常に頻繁なアップデートを求めます、例えば、その都度、リンクの利用可能な帯域幅(そうする)は変化します。
Apostolopoulos, et al. Experimental [Page 8] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[8ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
neither scalable nor practical. In general, there is a trade-off between the protocol overhead of frequent updates and the accuracy of the network state information that the path selection algorithm depends on. We outline next a few possible link state update policies, which strike a practical compromise.
スケーラブルでなくて、また実用的ではありません。 一般に、経路選択アルゴリズムが依存する頻繁なアップデートのプロトコルオーバーヘッドとネットワーク州の情報の精度の間には、トレードオフがあります。 私たちは次に、いくつかの可能なリンク州のアップデート方針を概説します。
The basic idea is to trigger link state advertisements only when there is a significant change in the value of metrics since the last advertisement. The notion of significance of a change can be based on an "absolute" scale or a "relative" one. An absolute scale means partitioning the range of values that a metric can take into equivalence classes and triggering an update whenever the metric changes sufficiently to cross a class boundary (3). A relative scale, on the other hand, triggers updates when the percentage change in the metric value exceeds a predefined threshold. Independent of whether a relative or an absolute change trigger mechanism is used, a periodic trigger constraint can also be added. This constraint can be in the form of a hold-down timer, which is used to force a minimum spacing between consecutive updates. Alternatively, a transmit timer can also be used to ensure the transmission of an update after a certain time has expired. Such a feature can be useful if link state updates advertising bandwidth changes are sent unreliably. The current protocol extensions described in Section 3 as well as the implementation of Section 4 do not consider such an option as metric updates are sent using the standard, and reliable, OSPF flooding mechanism. However, this is clearly an extension worth considering as it can help lower substantially the protocol overhead associated with metrics updates.
基本的な考え方は最後の広告以来測定基準の値における著しい変化があるときだけ、リンク州の広告の引き金となることです。 変化の意味の概念は「絶対」のスケールか「相対的な」ものに基づくことができます。 絶対温度目盛は、メートル法の缶が同値類に取る値とメートル法の変化が境界(3)を交差しているaに十分分類するときはいつも、アップデートの引き金となる範囲を仕切ることを意味します。 メートル法の数値における変化率が事前に定義された敷居を超えていると、他方では、相対的なスケールはアップデートの引き金となります。 親類か絶対変化トリガー機構が使用されるかどうかから独立しています、また、周期的な引き金の規制を加えることができます。 この規制は抑制タイマの形にあることができます。(タイマは、連続したアップデートの間の最小のスペースを強制するのに使用されます)。 あるいはまた、aはタイマ缶を送ります、また、使用されて、ある時間が期限が切れた後にアップデートの送信を確実にしてください。 帯域幅変化の広告を出すリンク州のアップデートを当てにならずに送るなら、そのような特徴は役に立つ場合があります。 セクション4の実現と同様にセクション3で説明された現在のプロトコル拡大がメートル法のようなオプションを考えないので、アップデートに標準の、そして、信頼できるOSPF氾濫メカニズムを使用させます。 しかしながら、プロトコルオーバーヘッドが測定基準アップデートと交際したのが、より低く実質的に助けることができるようにこれは明確に考える価値がある拡大です。
In both the relative and absolute change approaches, the metric value advertised in an LSA can be either the actual or a quantized value. Advertising the actual metric value is more accurate and, therefore, preferable when metrics are frequently updated. On the other hand, when updates are less frequent, e.g., because of a low sensitivity trigger or the use of hold-down timers, advertising quantized values can be of benefit. This is because it can help increase the number of equal cost paths and, therefore, improve robustness to metrics inaccuracies. In general, there is a broad space of possible trade- offs between accuracy and overhead and selecting an appropriate design point is difficult and depends on many parameters (see [AGKT98] for a more detailed discussion of these issues). As a result, in order to help acquire a better understanding of these issues, the implementation described in Section 4 supports a range of options that allow exploration of the available design space. In addition, Section 4 also reports experimental data on the traffic load and processing overhead generated by links state updates for different configurations.
In both the relative and absolute change approaches, the metric value advertised in an LSA can be either the actual or a quantized value. Advertising the actual metric value is more accurate and, therefore, preferable when metrics are frequently updated. On the other hand, when updates are less frequent, e.g., because of a low sensitivity trigger or the use of hold-down timers, advertising quantized values can be of benefit. This is because it can help increase the number of equal cost paths and, therefore, improve robustness to metrics inaccuracies. In general, there is a broad space of possible trade- offs between accuracy and overhead and selecting an appropriate design point is difficult and depends on many parameters (see [AGKT98] for a more detailed discussion of these issues). As a result, in order to help acquire a better understanding of these issues, the implementation described in Section 4 supports a range of options that allow exploration of the available design space. In addition, Section 4 also reports experimental data on the traffic load and processing overhead generated by links state updates for different configurations.
Apostolopoulos, et al. Experimental [Page 9] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos, et al. Experimental [Page 9] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
2.3. Path Selection
2.3. Path Selection
There are two major aspects to computing paths for QoS requests. The first is the actual path selection algorithm itself, i.e., which metrics and criteria it relies on. The second is when the algorithm is actually invoked.
There are two major aspects to computing paths for QoS requests. The first is the actual path selection algorithm itself, i.e., which metrics and criteria it relies on. The second is when the algorithm is actually invoked.
The topology on which the algorithm is run is, as with the standard OSPF path selection, a directed graph where vertices (4) consist of routers and networks (transit vertices) as well as stub networks (non-transit vertices). When computing a path, stub networks are added as a post-processing step, which is essentially similar to what is done with the current OSPF routing protocol. The optimization criteria used by the path selection are reflected in the costs associated with each interface in the topology and how those costs are accounted for in the algorithm itself. As mentioned before, the cost of a path is a function of both its hop count and the amount of available bandwidth. As a result, each interface has associated with it a metric, which corresponds to the amount of bandwidth that remains available on this interface. This metric is combined with hop count information to provide a cost value, whose goal is to pick a path with the minimum possible number of hops among those that can support the requested bandwidth. When several such paths are available, the preference is for the path whose available bandwidth (i.e., the smallest value on any of the links in the path) is maximal. The rationale for the above rule is the following: we focus on feasible paths (as accounted by the available bandwidth metric) that consume a minimal amount of network resources (as accounted by the hop-count metric); and the rule for selecting among these paths is meant to balance load as well as maximize the likelihood that the required bandwidth is indeed available.
The topology on which the algorithm is run is, as with the standard OSPF path selection, a directed graph where vertices (4) consist of routers and networks (transit vertices) as well as stub networks (non-transit vertices). When computing a path, stub networks are added as a post-processing step, which is essentially similar to what is done with the current OSPF routing protocol. The optimization criteria used by the path selection are reflected in the costs associated with each interface in the topology and how those costs are accounted for in the algorithm itself. As mentioned before, the cost of a path is a function of both its hop count and the amount of available bandwidth. As a result, each interface has associated with it a metric, which corresponds to the amount of bandwidth that remains available on this interface. This metric is combined with hop count information to provide a cost value, whose goal is to pick a path with the minimum possible number of hops among those that can support the requested bandwidth. When several such paths are available, the preference is for the path whose available bandwidth (i.e., the smallest value on any of the links in the path) is maximal. The rationale for the above rule is the following: we focus on feasible paths (as accounted by the available bandwidth metric) that consume a minimal amount of network resources (as accounted by the hop-count metric); and the rule for selecting among these paths is meant to balance load as well as maximize the likelihood that the required bandwidth is indeed available.
It should be noted that standard routing algorithms are typically single objective optimizations, i.e., they may minimize the hop- count, or maximize the path bandwidth, but not both. Double objective path optimization is a more complex task, and, in general, it is an intractable problem [GJ79]. Nevertheless, because of the specific nature of the two objectives being optimized (bandwidth and hop count), the complexity of the above algorithm is competitive with even that of standard single-objective algorithms. For readers interested in a thorough treatment of the topic, with insights into the connection between the different algorithms, linear algebra and modification of metrics, [Car79] is recommended.
It should be noted that standard routing algorithms are typically single objective optimizations, i.e., they may minimize the hop- count, or maximize the path bandwidth, but not both. Double objective path optimization is a more complex task, and, in general, it is an intractable problem [GJ79]. Nevertheless, because of the specific nature of the two objectives being optimized (bandwidth and hop count), the complexity of the above algorithm is competitive with even that of standard single-objective algorithms. For readers interested in a thorough treatment of the topic, with insights into the connection between the different algorithms, linear algebra and modification of metrics, [Car79] is recommended.
Before proceeding with a more detailed description of the path selection algorithm itself, we briefly review the available options when it comes to deciding when to invoke the algorithm. The two main options are: 1) to perform on-demand computations, that is, trigger
Before proceeding with a more detailed description of the path selection algorithm itself, we briefly review the available options when it comes to deciding when to invoke the algorithm. The two main options are: 1) to perform on-demand computations, that is, trigger
Apostolopoulos, et al. Experimental [Page 10] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos, et al. Experimental [Page 10] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
a computation for each new request, and 2) to use some form of pre- computation. The on-demand case involves no additional issues in terms of when computations should be triggered, but running the path selection algorithm for each new request can be computationally expensive (see [AT98] for a discussion on this issue). On the other hand, pre-computing paths amortizes the computational cost over multiple requests, but each computation instance is usually more expensive than in the on-demand case (paths are computed to all destinations and for all possible bandwidth requests rather than for a single destination and a given bandwidth request). Furthermore, depending on how often paths are recomputed, the accuracy of the selected paths may be lower. In this document, we primarily focus on the case of pre-computed paths, which is also the only method currently supported in the reference implementation described in Section 4. In this case, clearly, an important issue is when such pre-computation should take place. The two main options we consider are periodic pre-computations and pre-computations after a given (N) number of updates have been received. The former has the benefit of ensuring a strict bound on the computational load associated with pre-computations, while the latter can provide for a more responsive solution (5). Section 4 provides some experimental results comparing the performance and cost of periodic pre-computations for different period values.
a computation for each new request, and 2) to use some form of pre- computation. The on-demand case involves no additional issues in terms of when computations should be triggered, but running the path selection algorithm for each new request can be computationally expensive (see [AT98] for a discussion on this issue). On the other hand, pre-computing paths amortizes the computational cost over multiple requests, but each computation instance is usually more expensive than in the on-demand case (paths are computed to all destinations and for all possible bandwidth requests rather than for a single destination and a given bandwidth request). Furthermore, depending on how often paths are recomputed, the accuracy of the selected paths may be lower. In this document, we primarily focus on the case of pre-computed paths, which is also the only method currently supported in the reference implementation described in Section 4. In this case, clearly, an important issue is when such pre-computation should take place. The two main options we consider are periodic pre-computations and pre-computations after a given (N) number of updates have been received. The former has the benefit of ensuring a strict bound on the computational load associated with pre-computations, while the latter can provide for a more responsive solution (5). Section 4 provides some experimental results comparing the performance and cost of periodic pre-computations for different period values.
2.3.1. Path Computation Algorithm
2.3.1. Path Computation Algorithm
This section describes a path selection algorithm, which for a given network topology and link metrics (available bandwidth), pre-computes all possible QoS paths, while maintaining a reasonably low computational complexity. Specifically, the algorithm pre-computes for any destination a minimum hop count path with maximum bandwidth, and has a computational complexity comparable to that of a standard Bellman-Ford shortest path algorithm. The Bellman-Ford (BF) shortest path algorithm is adapted to compute paths of maximum available bandwidth for all hop counts. It is a property of the BF algorithm that, at its h-th iteration, it identifies the optimal (in our context: maximal bandwidth) path between the source and each destination, among paths of at most h hops. In other words, the cost of a path is a function of its available bandwidth, i.e., the smallest available bandwidth on all links of the path, and finding a minimum cost path amounts to finding a maximum bandwidth path. However, because the BF algorithm progresses by increasing hop count, it essentially provides for free the hop count of a path as a second optimization criteria.
This section describes a path selection algorithm, which for a given network topology and link metrics (available bandwidth), pre-computes all possible QoS paths, while maintaining a reasonably low computational complexity. Specifically, the algorithm pre-computes for any destination a minimum hop count path with maximum bandwidth, and has a computational complexity comparable to that of a standard Bellman-Ford shortest path algorithm. The Bellman-Ford (BF) shortest path algorithm is adapted to compute paths of maximum available bandwidth for all hop counts. It is a property of the BF algorithm that, at its h-th iteration, it identifies the optimal (in our context: maximal bandwidth) path between the source and each destination, among paths of at most h hops. In other words, the cost of a path is a function of its available bandwidth, i.e., the smallest available bandwidth on all links of the path, and finding a minimum cost path amounts to finding a maximum bandwidth path. However, because the BF algorithm progresses by increasing hop count, it essentially provides for free the hop count of a path as a second optimization criteria.
Specifically, at the kth (hop count) iteration of the algorithm, the maximum bandwidth available to all destinations on a path of no more than k hops is recorded (together with the corresponding routing
Specifically, at the kth (hop count) iteration of the algorithm, the maximum bandwidth available to all destinations on a path of no more than k hops is recorded (together with the corresponding routing
Apostolopoulos, et al. Experimental [Page 11] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos, et al. Experimental [Page 11] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
information). After the algorithm terminates, this information provides for all destinations and bandwidth requirements, the path with the smallest possible number of hops and sufficient bandwidth to accommodate the new request. Furthermore, this path is also the one with the maximal available bandwidth among all the feasible paths with at most these many hops. This is because for any hop count, the algorithm always selects the one with maximum available bandwidth.
information). After the algorithm terminates, this information provides for all destinations and bandwidth requirements, the path with the smallest possible number of hops and sufficient bandwidth to accommodate the new request. Furthermore, this path is also the one with the maximal available bandwidth among all the feasible paths with at most these many hops. This is because for any hop count, the algorithm always selects the one with maximum available bandwidth.
We now proceed with a more detailed description of the algorithm and the data structure used to record routing information, i.e., the QoS routing table that gets built as the algorithm progresses (the pseudo-code for the algorithm can be found in Appendix A). As mentioned before, the algorithm operates on a directed graph consisting only of transit vertices (routers and networks), with stub-networks subsequently added to the path(s) generated by the algorithm. The metric associated with each edge in the graph is the bandwidth available on the corresponding interface. Let us denote by b(n;m) the available bandwidth on the link from node n to m. The vertex corresponding to the router where the algorithm is being run, i.e., the computing router, is denoted as the "source node" for the purpose of path selection. The algorithm proceeds to pre-compute paths from this source node to all possible destination networks and for all possible bandwidth values. At each (hop count) iteration, intermediate results are recorded in a QoS routing table, which has the following structure:
We now proceed with a more detailed description of the algorithm and the data structure used to record routing information, i.e., the QoS routing table that gets built as the algorithm progresses (the pseudo-code for the algorithm can be found in Appendix A). As mentioned before, the algorithm operates on a directed graph consisting only of transit vertices (routers and networks), with stub-networks subsequently added to the path(s) generated by the algorithm. The metric associated with each edge in the graph is the bandwidth available on the corresponding interface. Let us denote by b(n;m) the available bandwidth on the link from node n to m. The vertex corresponding to the router where the algorithm is being run, i.e., the computing router, is denoted as the "source node" for the purpose of path selection. The algorithm proceeds to pre-compute paths from this source node to all possible destination networks and for all possible bandwidth values. At each (hop count) iteration, intermediate results are recorded in a QoS routing table, which has the following structure:
The QoS routing table:
The QoS routing table:
- a KxH matrix, where K is the number of destinations (vertices in
the graph) and H is the maximal allowed (or possible) number of
hops for a path.
- a KxH matrix, where K is the number of destinations (vertices in the graph) and H is the maximal allowed (or possible) number of hops for a path.
- The (n;h) entry is built during the hth iteration (hop count
value) of the algorithm, and consists of two fields:
- The (n;h) entry is built during the hth iteration (hop count value) of the algorithm, and consists of two fields:
* bw: the maximum available bandwidth, on a path of at most h
hops between the source node (router) and destination node
n;
* bw: the maximum available bandwidth, on a path of at most h hops between the source node (router) and destination node n;
* neighbor: this is the routing information associated with
the h (or less) hops path to destination node n, whose
available bandwidth is bw. In the context of hop-by-hop
path selection (6), the neighbor information is simply the
identity of the node adjacent to the source node on that
path. As a rule, the "neighbor" node must be a router and
not a network, the only exception being the case where the
network is the destination node (and the selected path is
the single edge interconnecting the source to it).
* neighbor: this is the routing information associated with the h (or less) hops path to destination node n, whose available bandwidth is bw. In the context of hop-by-hop path selection (6), the neighbor information is simply the identity of the node adjacent to the source node on that path. As a rule, the "neighbor" node must be a router and not a network, the only exception being the case where the network is the destination node (and the selected path is the single edge interconnecting the source to it).
Apostolopoulos, et al. Experimental [Page 12] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos, et al. Experimental [Page 12] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Next, we provide additional details on the operation of the algorithm and how the entries in the routing table are updated as the algorithm proceeds. For simplicity, we first describe the simpler case where all edges count as "hops," and later explain how zero-hop edges are handled. Zero-hop edges arise in the case of transit networks vertices, where only one of the two incoming and outgoing edges should be counted in the hop count computation, as they both correspond to the same physical hop. Accounting for this aspect requires distinguishing between network and router nodes, and the steps involved are detailed later in this section as well as in the pseudo-code of Appendix A.
Next, we provide additional details on the operation of the algorithm and how the entries in the routing table are updated as the algorithm proceeds. For simplicity, we first describe the simpler case where all edges count as "hops," and later explain how zero-hop edges are handled. Zero-hop edges arise in the case of transit networks vertices, where only one of the two incoming and outgoing edges should be counted in the hop count computation, as they both correspond to the same physical hop. Accounting for this aspect requires distinguishing between network and router nodes, and the steps involved are detailed later in this section as well as in the pseudo-code of Appendix A.
When the algorithm is invoked, the routing table is first initialized with all bw fields set to 0 and neighbor fields cleared. Next, the entries in the first column (which corresponds to one-hop paths) of the neighbors of the computing router are modified in the following way: the bw field is set to the value of the available bandwidth on the direct edge from the source. The neighbor field is set to the identity of the neighbor of the computing router, i.e., the next router on the selected path.
When the algorithm is invoked, the routing table is first initialized with all bw fields set to 0 and neighbor fields cleared. Next, the entries in the first column (which corresponds to one-hop paths) of the neighbors of the computing router are modified in the following way: the bw field is set to the value of the available bandwidth on the direct edge from the source. The neighbor field is set to the identity of the neighbor of the computing router, i.e., the next router on the selected path.
Afterwards, the algorithm iterates for at most H iterations (considering the above initial iteration as the first). The value of H could be implicit, i.e., the diameter of the network or, in order to better control the worst case complexity, it can be set explicitly thereby limiting path lengths to at most H hops. In the latter case, H must be assigned a value larger than the length of the minimum hop-count path to any node in the graph.
Afterwards, the algorithm iterates for at most H iterations (considering the above initial iteration as the first). The value of H could be implicit, i.e., the diameter of the network or, in order to better control the worst case complexity, it can be set explicitly thereby limiting path lengths to at most H hops. In the latter case, H must be assigned a value larger than the length of the minimum hop-count path to any node in the graph.
At iteration h, we first copy column h-1 into column h. In addition, the algorithm keeps a list of nodes that changed their bw value in the previous iteration, i.e., during the (h-1)-th iteration. The algorithm then looks at each link (n;m) where n is a node whose bw value changed in the previous iteration, and checks the maximal available bandwidth on an (at most) h-hop path to node m whose final hop is that link. This amounts to taking the minimum between the bw field in entry (n;h-1) and the link metric value b(n;m) kept in the topology database. If this value is higher than the present value of the bw field in entry (m;h), then a better (larger bw value) path has been found for destination m and with at most h hops. The bw field of entry (m;h) is then updated to reflect this new value. In the case of hop-by-hop routing, the neighbor field of entry (m;h) is set to the same value as in entry (n;h-1). This records the identity of the first hop (next hop from the source) on the best path identified thus far for destination m and with h (or less) hops.
At iteration h, we first copy column h-1 into column h. In addition, the algorithm keeps a list of nodes that changed their bw value in the previous iteration, i.e., during the (h-1)-th iteration. The algorithm then looks at each link (n;m) where n is a node whose bw value changed in the previous iteration, and checks the maximal available bandwidth on an (at most) h-hop path to node m whose final hop is that link. This amounts to taking the minimum between the bw field in entry (n;h-1) and the link metric value b(n;m) kept in the topology database. If this value is higher than the present value of the bw field in entry (m;h), then a better (larger bw value) path has been found for destination m and with at most h hops. The bw field of entry (m;h) is then updated to reflect this new value. In the case of hop-by-hop routing, the neighbor field of entry (m;h) is set to the same value as in entry (n;h-1). This records the identity of the first hop (next hop from the source) on the best path identified thus far for destination m and with h (or less) hops.
Apostolopoulos, et al. Experimental [Page 13] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos, et al. Experimental [Page 13] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
As mentioned earlier, extending the above algorithm to handle zero- hop edges is needed due to the possible use of multi-access networks, e.g., T/R, E/N, etc., to interconnect routers. Such entities are also represented by means of a vertex in the OSPF topology, but a network connecting two routers should clearly be considered as a single hop path rather than a two hop path. For example, consider three routers A, B, and C connected over an Ethernet network N, which the OSPF topology represents as in Figure 1.
As mentioned earlier, extending the above algorithm to handle zero- hop edges is needed due to the possible use of multi-access networks, e.g., T/R, E/N, etc., to interconnect routers. Such entities are also represented by means of a vertex in the OSPF topology, but a network connecting two routers should clearly be considered as a single hop path rather than a two hop path. For example, consider three routers A, B, and C connected over an Ethernet network N, which the OSPF topology represents as in Figure 1.
A----N----B
|
|
C
A----N----B | | C
Figure 1: Zero-Hop Edges
Figure 1: Zero-Hop Edges
In the example of Figure 1, although there are directed edges in both directions, an edge from the network to any of the three routers must have zero "cost", so that it is not counted twice. It should be noted that when considering such environments in the context of QoS routing, it is assumed that some entity is responsible for determining the "available bandwidth" on the network, e.g., a subnet bandwidth manager. The specification and operation of such an entity is beyond the scope of this document.
In the example of Figure 1, although there are directed edges in both directions, an edge from the network to any of the three routers must have zero "cost", so that it is not counted twice. It should be noted that when considering such environments in the context of QoS routing, it is assumed that some entity is responsible for determining the "available bandwidth" on the network, e.g., a subnet bandwidth manager. The specification and operation of such an entity is beyond the scope of this document.
Accommodating zero-hop edges in the context of the path selection algorithm described above is done as follows: At each iteration h (starting with the first), whenever an entry (m;h) is modified, it is checked whether there are zero-cost edges (m;k) emerging from node m. This is the case when m is a transit network. In that case, we attempt to further improve the entry of node k within the current iteration, i.e., entry (k;h) (rather than entry (k;h+1)), since the edge (m;k) should not count as an additional hop. As with the regular operation of the algorithm, this amounts to taking the minimum between the bw field in entry (m;h) and the link metric value b(m;k) kept in the topology database (7). If this value is higher than the present value of the bw field in entry (k;h), then the bw field of entry (k;h) is updated to this new value. In the case of hop-by-hop routing, the neighbor field of entry (k;h) is set, as usual, to the same value as in entry (m;h) (which is also the value in entry (n;h-1)).
Accommodating zero-hop edges in the context of the path selection algorithm described above is done as follows: At each iteration h (starting with the first), whenever an entry (m;h) is modified, it is checked whether there are zero-cost edges (m;k) emerging from node m. This is the case when m is a transit network. In that case, we attempt to further improve the entry of node k within the current iteration, i.e., entry (k;h) (rather than entry (k;h+1)), since the edge (m;k) should not count as an additional hop. As with the regular operation of the algorithm, this amounts to taking the minimum between the bw field in entry (m;h) and the link metric value b(m;k) kept in the topology database (7). If this value is higher than the present value of the bw field in entry (k;h), then the bw field of entry (k;h) is updated to this new value. In the case of hop-by-hop routing, the neighbor field of entry (k;h) is set, as usual, to the same value as in entry (m;h) (which is also the value in entry (n;h-1)).
Apostolopoulos, et al. Experimental [Page 14] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos, et al. Experimental [Page 14] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Note that while for simplicity of the exposition, the issue of equal cost, i.e., same hop count and available bandwidth, is not detailed in the above description, it can be easily supported. It only requires that the neighbor field be expanded to record the list of next (previous) hops, when multiple equal cost paths are present.
Note that while for simplicity of the exposition, the issue of equal cost, i.e., same hop count and available bandwidth, is not detailed in the above description, it can be easily supported. It only requires that the neighbor field be expanded to record the list of next (previous) hops, when multiple equal cost paths are present.
Addition of Stub Networks
Addition of Stub Networks
As was mentioned earlier, the path selection algorithm is run on a graph whose vertices consist only of routers and transit networks and not stub networks. This is intended to keep the computational complexity as low as possible as stub networks can be added relatively easily through a post-processing step. This second processing step is similar to the one used in the current OSPF routing table calculation [Moy98], with some differences to account for the QoS nature of routes.
As was mentioned earlier, the path selection algorithm is run on a graph whose vertices consist only of routers and transit networks and not stub networks. This is intended to keep the computational complexity as low as possible as stub networks can be added relatively easily through a post-processing step. This second processing step is similar to the one used in the current OSPF routing table calculation [Moy98], with some differences to account for the QoS nature of routes.
Specifically, after the QoS routing table has been constructed, all the router vertices are again considered. For each router, stub networks whose links appear in the router's link advertisements will be processed to determine QoS routes available to them. The QoS routing information for a stub network is similar to that of routers and transit networks and consists of an extension to the QoS routing table in the form of an additional row. The columns in that new row again correspond to paths of different hop counts, and contain both bandwidth and next hop information. We also assume that an available bandwidth value has been advertised for the stub network. As before, how this value is determined is beyond the scope of this document. The QoS routes for a stub network S are constructed as follows:
Specifically, after the QoS routing table has been constructed, all the router vertices are again considered. For each router, stub networks whose links appear in the router's link advertisements will be processed to determine QoS routes available to them. The QoS routing information for a stub network is similar to that of routers and transit networks and consists of an extension to the QoS routing table in the form of an additional row. The columns in that new row again correspond to paths of different hop counts, and contain both bandwidth and next hop information. We also assume that an available bandwidth value has been advertised for the stub network. As before, how this value is determined is beyond the scope of this document. The QoS routes for a stub network S are constructed as follows:
Each entry in the row corresponding to stub network S has its bw(s) field initialized to zero and its neighbor set to null. When a stub network S is found in the link advertisement of router V, the value bw(S,h) in the hth column of the row corresponding to stub network S is updated as follows:
Each entry in the row corresponding to stub network S has its bw(s) field initialized to zero and its neighbor set to null. When a stub network S is found in the link advertisement of router V, the value bw(S,h) in the hth column of the row corresponding to stub network S is updated as follows:
bw(S,h) = max ( bw(S,h) ; min ( bw(V,h) , b(V,S) ) ),
bw(S,h) = max ( bw(S,h) ; min ( bw(V,h) , b(V,S) ) ),
where bw(V,h) is the bandwidth value of the corresponding column for the QoS routing table row associated with router V, i.e., the bandwidth available on an h hop path to V, and b(V,S) is the advertised available bandwidth on the link from V to S. The above expression essentially states that the bandwidth of a h hop path to stub network S is updated using a path through router V, only if the minimum of the bandwidth of the h hop path to V and the bandwidth on the link between V and S is larger than the current value.
where bw(V,h) is the bandwidth value of the corresponding column for the QoS routing table row associated with router V, i.e., the bandwidth available on an h hop path to V, and b(V,S) is the advertised available bandwidth on the link from V to S. The above expression essentially states that the bandwidth of a h hop path to stub network S is updated using a path through router V, only if the minimum of the bandwidth of the h hop path to V and the bandwidth on the link between V and S is larger than the current value.
Apostolopoulos, et al. Experimental [Page 15] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos, et al. Experimental [Page 15] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Update of the neighbor field proceeds similarly whenever the bandwidth of a path through V is found to be larger than or equal to the current value. If it is larger, then the neighbor field of V in the corresponding column replaces the current neighbor field of S. If it is equal, then the neighbor field of V in the corresponding column is concatenated with the existing field for S, i.e., the current set of neighbors for V is added to the current set of neighbors for S.
Update of the neighbor field proceeds similarly whenever the bandwidth of a path through V is found to be larger than or equal to the current value. If it is larger, then the neighbor field of V in the corresponding column replaces the current neighbor field of S. If it is equal, then the neighbor field of V in the corresponding column is concatenated with the existing field for S, i.e., the current set of neighbors for V is added to the current set of neighbors for S.
Extracting Forwarding Information from Routing Table
Extracting Forwarding Information from Routing Table
When the QoS paths are precomputed, the forwarding information for a flow with given destination and bandwidth requirement needs to be extracted from the routing table. The case of hop-by-hop routing is simpler than that of explicit routing. This is because, only the next hop needs to be returned instead of an explicit route.
When the QoS paths are precomputed, the forwarding information for a flow with given destination and bandwidth requirement needs to be extracted from the routing table. The case of hop-by-hop routing is simpler than that of explicit routing. This is because, only the next hop needs to be returned instead of an explicit route.
Specifically, assume a new request to destination, say, d, and with bandwidth requirements B. The index of the destination vertex identifies the row in the QoS routing table that needs to be checked to generate a path. Assuming that the QoS routing table was constructed using the Bellman-Ford algorithm presented later in this section, the search then proceeds by increasing index (hop) count until an entry is found, say at hop count or column index of h, with a value of the bw field which is equal to or larger than B. This entry points to the initial information identifying the selected path.
Specifically, assume a new request to destination, say, d, and with bandwidth requirements B. The index of the destination vertex identifies the row in the QoS routing table that needs to be checked to generate a path. Assuming that the QoS routing table was constructed using the Bellman-Ford algorithm presented later in this section, the search then proceeds by increasing index (hop) count until an entry is found, say at hop count or column index of h, with a value of the bw field which is equal to or larger than B. This entry points to the initial information identifying the selected path.
If the path computation algorithm stores multiple equal cost paths, then some degree of load balancing can be achieved at the time of path selection. A next hop from the list of equivalent next hops can be chosen in a round robin manner, or randomly with a probability that is weighted by the actual available bandwidth on the local interface. The latter is the method used in the implementation described in Section 4.
If the path computation algorithm stores multiple equal cost paths, then some degree of load balancing can be achieved at the time of path selection. A next hop from the list of equivalent next hops can be chosen in a round robin manner, or randomly with a probability that is weighted by the actual available bandwidth on the local interface. The latter is the method used in the implementation described in Section 4.
The case of explicit routing is discussed in Appendix D.
The case of explicit routing is discussed in Appendix D.
3. OSPF Protocol Extensions
3. OSPF Protocol Extensions
As stated earlier, one of our goals is to limit the additions to the existing OSPF V2 protocol, while still providing the required level of support for QoS based routing. To this end, all of the existing OSPF mechanisms, data structures, advertisements, and data formats remain in place. The purpose of this section of the document is to describe the extensions to the OSPF protocol needed to support QoS as outlined in the previous sections.
As stated earlier, one of our goals is to limit the additions to the existing OSPF V2 protocol, while still providing the required level of support for QoS based routing. To this end, all of the existing OSPF mechanisms, data structures, advertisements, and data formats remain in place. The purpose of this section of the document is to describe the extensions to the OSPF protocol needed to support QoS as outlined in the previous sections.
Apostolopoulos, et al. Experimental [Page 16] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos, et al. Experimental [Page 16] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
3.1. QoS -- Optional Capabilities
3.1. QoS -- Optional Capabilities
The OSPF Options field is present in OSPF Hello packets, Database Description packets and all LSAs. The Options field enables OSPF routers to support (or not support) optional capabilities, and to communicate their capability level to other OSPF routers. Through this mechanism, routers of differing capabilities can be mixed within an OSPF routing domain. Currently, the OSPF standard [Moy98] specifies the following 5 bits in the options octet:
The OSPF Options field is present in OSPF Hello packets, Database Description packets and all LSAs. The Options field enables OSPF routers to support (or not support) optional capabilities, and to communicate their capability level to other OSPF routers. Through this mechanism, routers of differing capabilities can be mixed within an OSPF routing domain. Currently, the OSPF standard [Moy98] specifies the following 5 bits in the options octet:
+-----------------------------------------------+
| * | * | DC | EA | N/P | MC | E | * |
+-----------------------------------------------+
+-----------------------------------------------+ | * | * | DC | EA | N/P | MC | E | * | +-----------------------------------------------+
Note that the least significant bit (`T' bit) that was used to indicate TOS routing capability in the older OSPF specification [Moy94] has been removed. However, for backward compatibility with previous versions of the OSPF specification, TOS-specific information can be included in router-LSAs, summary-LSAs and AS-external-LSAs.
Note that the least significant bit (`T' bit) that was used to indicate TOS routing capability in the older OSPF specification [Moy94] has been removed. However, for backward compatibility with previous versions of the OSPF specification, TOS-specific information can be included in router-LSAs, summary-LSAs and AS-external-LSAs.
We propose to reclaim the `T' bit as an indicator of router's QoS routing capability and refer to it as the `Q' bit. In fact, QoS capability can be viewed as an extension of the TOS-capabilities and QoS routing as a form of TOS-based routing. A router sets this bit in its hello packets to indicate that it is capable of supporting such routing. When this bit is set in a router or summary links link state advertisement, it means that there are QoS fields to process in the packet. When this bit is set in a network link state advertisement it means that the network described in the advertisement is QoS capable.
We propose to reclaim the `T' bit as an indicator of router's QoS routing capability and refer to it as the `Q' bit. In fact, QoS capability can be viewed as an extension of the TOS-capabilities and QoS routing as a form of TOS-based routing. A router sets this bit in its hello packets to indicate that it is capable of supporting such routing. When this bit is set in a router or summary links link state advertisement, it means that there are QoS fields to process in the packet. When this bit is set in a network link state advertisement it means that the network described in the advertisement is QoS capable.
We need to be careful in this approach so as to avoid confusing any old style (i.e., RFC 1583 based) TOS routing implementations. The TOS metric encoding rules of QoS fields introduced further in this section will show how this is achieved. Additionally, unlike the RFC 1583 specification that unadvertised TOS metrics be treated to have same cost as TOS 0, for the purpose of computing QOS routes, unadvertised TOS metrics (on a hop) indicate lack of connectivity for the specific TOS metrics (for that hop).
We need to be careful in this approach so as to avoid confusing any old style (i.e., RFC 1583 based) TOS routing implementations. The TOS metric encoding rules of QoS fields introduced further in this section will show how this is achieved. Additionally, unlike the RFC 1583 specification that unadvertised TOS metrics be treated to have same cost as TOS 0, for the purpose of computing QOS routes, unadvertised TOS metrics (on a hop) indicate lack of connectivity for the specific TOS metrics (for that hop).
3.2. Encoding Resources as Extended TOS
3.2. Encoding Resources as Extended TOS
Introduction of QoS should ideally not influence the compatibility with existing OSPFv2 routers. To achieve this goal, necessary extensions in packet formats must be defined in a way that either is understood by OSPFv2 routers, ignored, or in the worst case "gracefully" misinterpreted. Encoding of QoS metrics in the TOS field which fortunately enough is longer in OSPF packets than
Introduction of QoS should ideally not influence the compatibility with existing OSPFv2 routers. To achieve this goal, necessary extensions in packet formats must be defined in a way that either is understood by OSPFv2 routers, ignored, or in the worst case "gracefully" misinterpreted. Encoding of QoS metrics in the TOS field which fortunately enough is longer in OSPF packets than
Apostolopoulos, et al. Experimental [Page 17] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos, et al. Experimental [Page 17] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
officially defined in [Alm92], allows us to mimic the new facility as extended TOS capability. OSPFv2 routers will either disregard these definitions or consider those unspecified. Specific precautions are taken to prevent careless OSPF implementations from influencing traditional TOS routers (if any) when misinterpreting the QoS extensions.
officially defined in [Alm92], allows us to mimic the new facility as extended TOS capability. OSPFv2 routers will either disregard these definitions or consider those unspecified. Specific precautions are taken to prevent careless OSPF implementations from influencing traditional TOS routers (if any) when misinterpreting the QoS extensions.
For QoS resources, 32 combinations are available through the use of the fifth bit in TOS fields contained in different LSAs. Since [Alm92] defines TOS as being four bits long, this definition never conflicts with existing values. Additionally, to prevent naive implementations that do not take all bits of the TOS field in OSPF packets into considerations, the definitions of the `QoS encodings' is aligned in their semantics with the TOS encoding. Only bandwidth and delay are specified as of today and their values map onto `maximize throughput' and `minimize delay' if the most significant bit is not taken into account. Accordingly, link reliability and jitter could be defined later if necessary.
QoSリソースに、32の組み合わせが異なったLSAsに含まれたTOS分野での5番目のビットの使用で利用可能です。 [Alm92]が長さ4ビットであるとTOSを定義するので、この定義は既存の値と決して衝突しません。 さらに、問題にOSPFパケットのTOS分野のすべてのビット取らないナイーブな実現を防ぐために、'QoS encodings'の定義は彼らの意味論でTOSコード化に並べられます。 帯域幅と遅れだけが今日現在指定されます、そして、'スループットを最大にしてください'と'遅れを最小にしてください'という最も重要であるならビットへの地図が連れていかれないそれらの値は説明されます。 必要なら、それに従って、後でリンクの信頼性とジターを定義できました。
OSPF encoding RFC 1349 TOS values
___________________________________________
0 0000 normal service
2 0001 minimize monetary cost
4 0010 maximize reliability
6 0011
8 0100 maximize throughput
10 0101
12 0110
14 0111
16 1000 minimize delay
18 1001
20 1010
22 1011
24 1100
26 1101
28 1110
30 1111
RFC1349TOS値をコード化するOSPF___________________________________________ 0000年の0の通常のサービス、2、0001、貨幣原価を最小にしてください、4、0010、信頼性6の0011を最大にしてください、0100が最大にする8、スループット10 0101 12 0110 14 0111 16 1000は遅れ18 1001 20 1010 22 1011 24 1100 26 1101 28 1110 30 1111を最小にします。
Apostolopoulos, et al. Experimental [Page 18] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[18ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
OSPF encoding `QoS encoding values'
'値をコード化するQoS'をコード化するOSPF
-------------------------------------------
32 10000
34 10001
36 10010
38 10011
40 10100 bandwidth
42 10101
44 10110
46 10111
48 11000 delay
50 11001
52 11010
54 11011
56 11100
58 11101
60 11110
62 11111
------------------------------------------- 32 10000 34 10001 36 10010 38 10011 40 10100帯域幅42 10101 44 10110 46 10111 48 11000遅れ50 11001 52 11010 54 11011 56 11100 58 11101 60 11110 62 11111
Representing TOS and QoS in OSPF.
OSPFにTOSとQoSを表します。
3.2.1. Encoding bandwidth resource
3.2.1. 帯域幅リソースをコード化します。
Given the fact that the actual metric field in OSPF packets only provides 16 bits to encode the value used and that links supporting bandwidth ranging into Gbits/s are becoming reality, linear representation of the available resource metric is not feasible. The solution is exponential encoding using appropriately chosen implicit base value and number bits for encoding mantissa and the exponent. Detailed considerations leading to the solution described are not presented here but can be found in [Prz95].
事実を考えて、OSPFパケットの実際のメートル法の分野がメートル法で値が使用したエンコードへのリンクがGbits/sに及ぶ帯域幅を支持して、現実になっている16ビット、利用可能なリソースの直線的な表現を提供するだけであるのは、可能ではありません。 解決策は、仮数をコード化するのに適切に選ばれた暗黙の基礎点と数のビットを使用して、解説者をコード化しながら、指数です。 解決策への先導が説明した詳細な問題をここに提示されませんが、[Prz95]で見つけることができます。
Given a base of 8, the 3 most significant bits should be reserved for the exponent part and the remaining 13 for the mantissa. This allows a simple comparison for two numbers encoded in this form, which is often useful during implementation.
8のベースを考えて、3つの最上位ビットが仮数のための指数部と残っている13のために予約されるべきです。 これはこの実現の間、しばしば役に立つフォームでコード化された2つの番号のための簡単な比較を許します。
The following table shows bandwidth ranges covered when using different exponents and the granularity of possible reservations.
以下のテーブルは可能な予約の異なった解説者と粒状を使用するときカバーされた帯域幅範囲を示しています。
Apostolopoulos, et al. Experimental [Page 19] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[19ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
exponent
value x range (2^13-1)*8^x step 8^x
-------------------------------------------------
0 8,191 1
1 65,528 8
2 524,224 64
3 4,193,792 512
4 33,550,336 4,096
5 268,402,688 32,768
6 2,147,221,504 262,144
7 17,177,772,032 2,097,152
解説者値のx範囲(2^13-1)*8^xステップ8^x------------------------------------------------- 0 8,191 1 1 65,528 8 2 524,224 64 3 4,193,792 512 4 33,550,336 4,096 5 268,402,688 32,768 6 2,147,221,504 262,144 7 17,177,772,032 2,097,152
Ranges of Exponent Values for 13 bits,
base 8 Encoding, in Bytes/s
13ビットExponent Values、Bytes/sのベース8Encodingの範囲
The bandwidth encoding rule may be summarized as: "represent available bandwidth in 16 bit field as a 3 bit exponent (with assumed base of 8) followed by a 13 bit mantissa as shown below and advertise 2's complement of the above representation."
帯域幅符号化規則は以下としてまとめられるかもしれません。 「3ビットの解説者(8の想定されたベースがある)が13ビットの仮数で以下に示すように続いたので、16ビットの分野の利用可能な帯域幅を表してください、そして、上の表現の2補数の広告を出してください。」
0 8 16
| | |
-----------------
|EXP| MANT |
-----------------
0 8 16 | | | ----------------- |EXP| マント| -----------------
Thus, the above encoding advertises a numeric value that is
したがって、上のコード化は数値の広告を出します。
2^16 -1 -(exponential encoding of the available bandwidth):
2^16 -1--(利用可能な帯域幅の指数のコード化):
This has the property of advertising a higher numeric value for lower available bandwidth, a notion that is consistent with that of cost.
これには、下側の利用可能な帯域幅(費用のものと一致した概念)により高い数値の広告を出す特性があります。
Although it may seem slightly pedantic to insist on the property that less bandwidth is expressed higher values, it has, besides consistency, a robustness aspect in it. A router with a poor OSPF implementation could misuse or misunderstand bandwidth metric as normal administrative cost provided to it and compute spanning trees with a "normal" Dijkstra. The effect of a heavily congested link advertising numerically very low cost could be disastrous in such a scenario. It would raise the link's attractiveness for future traffic instead of lowering it. Evidence that such considerations are not speculative, but similar scenarios have been encountered, can be found in [Tan89].
より少ない帯域幅が言い表されたより高い値であると所有地を主張するのがわずかに訳知り顔で思えるかもしれませんが、それは一貫性以外にそれに丈夫さ局面を持っています。 不十分なOSPF実現があるルータは、それに提供された正常な管理費としてのメートル法の帯域幅を誤用するか、または誤解するかもしれません、そして、「正常な」ダイクストラと共に木にかかりながら、計算してください。 ずっしりと充血しているリンクが数の上で非常に低い費用の広告を出すという効果はそのようなシナリオで悲惨であるかもしれません。 それはそれを下ろすことの代わりに将来の交通にリンクの魅力を上げるでしょう。 [Tan89]でそのような問題が投機的ではありませんが、同様のシナリオが遭遇したという証拠を見つけることができます。
Apostolopoulos, et al. Experimental [Page 20] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[20ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
Concluding with an example, assume a link with bandwidth of 8 Gbits/s = 1024^3 Bytes/s, its encoding would consist of an exponent value of 6 since 1024^3= 4,096*8^6, which would then have a granularity of 8^6 or approx. 260 kBytes/s. The associated binary representation would then be %(110) 0 1000 0000 0000% or 53,248 (8). The bandwidth cost (advertised value) of this link when it is idle, is then the 2's complement of the above binary representation, i.e., %(001) 1 0111 1111 1111% which corresponds to a decimal value of (2^16 - 1) - 53,248 = 12,287. Assuming now a current reservation level of 6;400 Mbits/s = 200 * 1024^2, there remains 1;600 Mbits/s of available bandwidth on the link. The encoding of this available bandwidth of 1'600 Mbits/s is 6,400 * 8^5, which corresponds to a granularity of 8^5 or approx. 30 kBytes/s, and has a binary representation of %(101) 1 1001 0000 0000% or decimal value of 47,360. The advertised cost of the link with this load level, is then %(010) 0 0110 1111 1111%, or (2^16-1) -47,360 = 18,175.
3Bytes/sが、8Gbits/s=1024^の帯域幅とのリンクであると例で締めくくって、1024^3= 4,096*8^6以来コード化が6の解説者価値から成ると思います。(次に、*には、およそ8^6か260kBytes/sの粒状があるでしょう)。 そして関連2進法表示は%(110)0 1000 0000 0000%か5万3248(8)でしょう。 それが活動していなく、次に、上の2進法表示の2補数であるときに、帯域幅はこのリンクの(広告を出している値)かかりました、すなわち、(2^16--1)のデシマル値に対応する%(001)1 0111 1111 1111%--53,248 = 12,287。 現在現在の予約が6;400メガビット/s=200*1024^2のレベルであると仮定して、利用可能な帯域幅の1;600メガビット/sがリンクの上に残っています。 1'600メガビット/sのこの利用可能な帯域幅のコード化は6,400*8^5です。(その^はおよそ8^5か30kBytes/sの粒状に対応している、(101)1 1001 0000 0000%か小数が評価する4万7360の'%の2進法表示を持っています)。 そして、この負荷レベルとのリンクの広告を出している費用は%(010)0 0110 1111 1111%、または(2^16-1)-47,360 = 18,175です。
Note that the cost function behaves as it should, i.e., the less bandwidth is available on a link, the higher the cost and the less attractive the link becomes. Furthermore, the targeted property of better granularity for links with less bandwidth available is also achieved. It should, however, be pointed out that the numbers given in the above examples match exactly the resolution of the proposed encoding, which is of course not always the case in practice. This leaves open the question of how to encode available bandwidth values when they do not exactly match the encoding. The standard practice is to round it to the closest number. Because we are ultimately interested in the cost value for which it may be better to be pessimistic than optimistic, we choose to round costs up and, therefore, bandwidth down.
費用関数が振る舞うべきであるように振る舞うことに注意してください、そして、すなわち、より少ない帯域幅がリンクで利用可能であれば利用可能であるほど、費用が、より高く、リンクはそれほど魅力的ではありません。 その上、また、より少ない利用可能な帯域幅とのリンクへの、より良い粒状の狙っている特性は獲得されます。 しかしながら、上記の例で与えられた数がまさにもちろん実際にはいつもケースであるというわけではない提案されたコード化の解決に合っていると指摘されるべきです。 まさにコード化に合っていないと、これはどう利用可能な帯域幅値をコード化するかに関する質問を戸外に発ちます。 標準的技法は最も近い数にそれを一周させることになっています。 私たちが結局悲観的であるのが楽観的であるというよりも良いかもしれない、私たちがコストを四捨五入するのをどれに選ぶか、そして、したがって、帯域幅のために原価価値に興味を持っているので、ダウンしてください。
3.2.2. Encoding Delay
3.2.2. 遅れをコード化します。
Delay is encoded in microseconds using the same exponential method as described for bandwidth except that the base is defined to be 4 instead of 8. Therefore, the maximum delay that can be expressed is (2^13-1) *4^7 i.e., approx. 134 seconds.
遅れは、マイクロセカンドのときにベースが8の代わりに4になるように定義されるのを除いて、帯域幅のための説明されるのと同じ指数の方法を使用することでコード化されます。 したがって、言い表すことができる最大の遅れはすなわち、およそ134秒(2^13-1)*4^7です。
3.3. Packet Formats
3.3. パケット・フォーマット
Given the extended TOS notation to account for QoS metrics, no changes in packet formats are necessary except for the (re)introduction of T-bit as the Q-bit in the options field. Routers not understanding the Q-bit should either not consider the QoS metrics distributed or consider those as `unknown' TOS.
QoS測定基準を説明する拡張TOS記法を考えて、T-ビットの(re)挿入以外に、パケット・フォーマットにおけるどんな変化もQ-ビットとしてオプション分野で必要ではありません。 Q-ビットを理解していないルータは、QoS測定基準が分配されていると考えるべきではありませんし、またそれらが'未知'のTOSであるとみなすべきではありません。
Apostolopoulos, et al. Experimental [Page 21] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[21ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
To support QoS, there are additions to two Link State Advertisements, the Router Links Advertisement and the Summary Links Advertisement. As stated above, a router identifies itself as supporting QoS by setting the Q-bit in the options field of the Link State Header. When a router that supports QoS receives either the Router Links or Summary Links Advertisement, it should parse the QoS metrics encoded in the received Advertisement.
QoSを支持するために、2Link州Advertisements、RouterリンクスAdvertisement、およびSummaryリンクスAdvertisementへの追加があります。 上に述べられているように、ルータはLink州Headerのオプション分野にQ-ビットをはめ込むことによってQoSを支持することであると名乗ります。 QoSを支持するルータがRouterリンクスかSummaryリンクスAdvertisementのどちらかを受けるとき、それは容認されたAdvertisementでコード化されたQoS測定基準を分析するべきです。
3.4. Calculating the Inter-area Routes
3.4. 相互領域ルートを計算します。
This document proposes a very limited use of OSPF areas, that is, it is assumed that summary links advertisements exist for all networks in the area. This document does not discuss the problem of providing support for area address ranges and QoS metric aggregation. This is left for further studies.
このドキュメントはOSPF領域の非常に限られた使用を提案します、すなわち、概要リンク広告がすべてのネットワークのためにその領域に存在すると思われます。 このドキュメントは領域のアドレスの範囲とQoSのメートル法の集合のサポートを提供するという問題について議論しません。 これはさらなる研究に発たれます。
3.5. Open Issues
3.5. 未解決の問題
Support for AS External Links, Virtual Links, and incremental updates for summary link advertisements are not addressed in this document and are left for further study. For Virtual Links that do exist, it is assumed for path selection that these links are non-QoS capable even if the router advertises QoS capability. Also, as stated earlier, this document does not address the issue of non-QoS routers within a QoS domain.
概要リンク広告のためのAS Externalリンクスのサポート、Virtualリンクス、およびアップデート増加は、本書では宛てられないで、さらなる研究に置き去りにされます。 存在するVirtualリンクスに関しては、経路選択のために、ルータがQoS能力の広告を出してもこれらのリンクができる非QoSであると思われます。 また、より早く述べられるように、このドキュメントはQoSドメインの中に非QoSルータの問題を記述しません。
4. A Reference Implementation based on GateD
4. GateDに基づくリファレンスインプリメンテーション
In this section we report on the experience gained from implementing the pre-computation based approach of Section 2.3.1 in the GateD [Con] environment. First, we briefly introduce the GateD environment, and then present some details on how the QoS extensions were implemented in this environment. Finally, we discuss issues that arose during the implementation effort and present some measurement based results on the overhead that the QoS extensions impose on a QoS capable router and a network of QoS routers. For further details on the implementation study, the reader is referred to [AGK99]. Additional performance evaluation based on simulations can be found in [AGKT98].
このセクションで、私たちはGateD[まやかし]環境における、セクション2.3.1のプレ計算のベースのアプローチを実行するという得られる経験に関して報告します。 まず最初に、私たちは、簡潔にGateD環境を導入して、次に、QoS拡張子がこの環境でどう実行されたかに関するいくつかの詳細を提示します。 最終的に、私たちは、実現の努力の間に起こった問題について議論して、QoS拡張子がQoSのできるルータとQoSのネットワークにルータを課すというオーバーヘッドのベースの結果を何らかの測定に提示します。 さらに詳しい明細については実現研究では、読者は言及されます[AGK99]。 [AGKT98]でシミュレーションに基づく追加業績評価は見つけることができます。
4.1. The Gate Daemon (GateD) Program
4.1. ゲートデーモン(外出を禁止される)プログラム
GateD [Con] is a popular, public domain (9) program that provides a platform for implementing routing protocols on hosts running the Unix operating system. The distribution of the GateD software also includes implementations of many popular routing protocols, including the OSPF protocol. The GateD environment offers a variety of services useful for implementing a routing protocol. These services
GateD[まやかし]はUnixオペレーティングシステムを走らせながらホストの上でルーティング・プロトコルを実行するのにプラットホームを提供するポピュラーな公共の場(9)プログラムです。 また、GateDソフトウェアの分配はOSPFプロトコルを含む多くのポピュラーなルーティング・プロトコルの実現を含んでいます。 GateD環境はルーティング・プロトコルを実行することの役に立つさまざまなサービスを提供します。 これらのサービス
Apostolopoulos, et al. Experimental [Page 22] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[22ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
include a) support for creation and management of timers, b) memory management, c) a simple scheduling mechanism, d) interfaces for manipulating the host's routing table and accessing the network, and e) route management (e.g., route prioritization and route exchange between protocols).
創造のa)サポートとタイマ、b)メモリ管理、c) 簡単なスケジューリングメカニズム、ホストの経路指定テーブルを操作して、ネットワークにアクセスするためのd)インタフェース、およびe)ルート管理の経営を含めてください(例えば、優先順位づけとルート交換をプロトコルの間に発送してください)。
All GateD processing is done within a single Unix process, and routing protocols are implemented as one or several tasks. A GateD task is a collection of code associated with a Unix socket. The socket is used for the input and output requirements of the task. The main loop of GateD contains, among other operations, a select() call over all task sockets to determine if any read/write or error conditions occurred in any of them. GateD implements the OSPF link state database using a radix tree for fast access to individual link state records. In addition, link state records for neighboring network elements (such as adjacent routers) are linked together at the database level with pointers. GateD maintains a single routing table that contains routes discovered by all the active routing protocols. Multiple routes to the same destination are prioritized according to a set of rules and administrative preferences and only a single route is active per destination. These routes are periodically downloaded in the host's kernel forwarding table.
ただ一つのUnixの過程の中ですべてのGateD処理をします、そして、1かいくつかのタスクとしてルーティング・プロトコルを実行します。 GateDタスクはUnixソケットに関連しているコードの収集です。 ソケットはタスクの入出力要件に使用されます。 GateDのメイン輪は他の操作の中に何かが読んだか、書いた、またはエラー条件がそれらのどれかに起こったかを決定するというすべてのタスクソケットの上の選んだ()要求を含んでいます。 GateDは、個々のリンク州の記録への速いアクセスに基数木を使用することでOSPFリンク州のデータベースを実行します。 さらに、隣接しているネットワーク要素(隣接しているルータなどの)のためのリンク州の記録はポインタでデータベースレベルで結びつけられます。 GateDはすべてのアクティブなルーティング・プロトコルによって発見されたルートを含む単一の経路指定テーブルを維持します。 1セットの規則と管理好みに従って、同じ目的地への複数のルートが最優先します、そして、ただ一つのルートだけが目的地単位でアクティブです。 ホストのカーネル推進テーブルで定期的にこれらのルートをダウンロードします。
4.2. Implementing the QoS Extensions of OSPF
4.2. OSPFのQoS拡張子を実行します。
4.2.1. Design Objectives and Scope
4.2.1. 設計目標と範囲
One of our major design objectives was to gain substantial experience with a functionally complete QoS routing implementation while containing the overall implementation complexity. Thus, our architecture was modular and aimed at reusing the existing OSPF code with only minimal changes. QoS extensions were localized to specific modules and their interaction with existing OSPF code was kept to a minimum. Besides reducing the development and testing effort, this approach also facilitated experimentation with different alternatives for implementing the QoS specific features such as triggering policies for link state updates and QoS route table computation. Several of the design choices were also influenced by our assumptions regarding the core functionalities that an early prototype implementation of QoS routing must demonstrate. Some of the important assumptions/requirements are:
私たちの主要な設計目標の1つは総合的な実現の複雑さを含んでいる間、機能上完全なQoSルーティング実現のかなりの経験をすることでした。 したがって、私たちの構造は、モジュールで最小量の変化だけに伴う既存のOSPFコードを再利用するのが目的とされました。 QoS拡張子は特定のモジュールに局所化されました、そして、既存のOSPFコードとのそれらの相互作用は最小限に保たれました。 また、開発を抑えて、努力をテストすること以外に、このアプローチはリンク州のアップデートとQoSルートテーブル計算のための方針の引き金となることなどのQoSの特定の特徴を実行するための異なった代替手段で実験を容易にしました。 また、QoSルーティングの初期の原型実現が示さなければならない中心となる機能性に関する私たちの仮定でいくつかのデザイン選択が影響を及ぼされました。 重要な仮定/要件のいくつかは以下の通りです。
- Support for only hop-by-hop routing. This affected the path
structure in the QoS routing table as it only needs to store next
hop information. As mentioned earlier, the structure can be
easily extended to allow construction of explicit routes.
- ホップごとのルーティングだけのために、支持します。 次のホップ情報を格納するのが必要であるだけであるときに、これはQoS経路指定テーブルの経路構造に影響しました。 先に述べたように、明白なルートの構造を許容するために容易に構造を広げることができます。
Apostolopoulos, et al. Experimental [Page 23] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[23ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
- Support for path pre-computation. This required the creation of a
separate QoS routing table and its associated path structure, and
was motivated by the need to minimize processing overhead.
- 経路プレ計算のために、支持します。 これは、別々のQoS経路指定テーブルとその関連経路構造の創造を必要として、処理オーバヘッドを最小にする必要性によって動機づけられました。
- Full integration of the QoS extensions into the GateD framework,
including configuration support, error logging, etc. This was
required to ensure a fully functional implementation that could be
used by others.
- 構成サポート、エラー・ロギングなどを含むGateD枠組みへのQoS拡張子の完全統合 これが、他のものが使用できた完全に機能的な実現を確実にするのに必要でした。
- Ability to allow experimentation with different approaches, e.g.,
use of different update and pre-computation triggering policies
with support for selection and parameterization of these policies
from the GateD configuration file.
- これらの方針の選択とパラメタリゼーションのサポートでGateD構成ファイルから異なるアプローチによる実験、例えば異なったアップデートとプレ計算引き金となる方針の使用を許す能力。
- Decoupling from local traffic and resource management components,
i.e., packet classifiers and schedulers and local call admission.
This is supported by providing an API between QoS routing and the
local traffic management module, which hides all internal details
or mechanisms. Future implementations will be able to specify
their own mechanisms for this module.
- ローカルの交通とすなわち、資源管理コンポーネント、パケットから、クラシファイア、スケジューラ、および市内通話入場の衝撃を吸収します。 これは、QoSルーティングとローカルの輸送管理モジュールの間にAPIを提供することによって、支持されます。それは、すべての内部の詳細かメカニズムを隠します。今後の実現はこのモジュールにそれら自身のメカニズムを指定できるでしょう。
- Interface to RSVP. The implementation assumes that RSVP [RZB+97]
is the mechanism used to request routes with specific QoS
requirements. Such requests are communicated through an interface
based on [GKR97], and used the RSVP code developed at ISI, version
4.2a2 [RZB+97].
- RSVPに連結してください。 実現は、RSVP[RZB+97]が特定のQoS要件でルートを要求するのに使用されるメカニズムであると仮定します。 そのような要求は[GKR97]に基づくインタフェースを通して伝えられました、そして、使用されて、RSVPコードはISIで展開しました、バージョン4.2a2[RZB+97]。
In addition, our implementation also relies on several of the simplifying assumptions made earlier in this document, namely:
また、さらに、私たちの実現が仮定が、より早くこのドキュメントで作った簡素化の数個を当てにする、すなわち:
- The scope of QoS route computation is currently limited to a
single area.
- QoS経路計算の範囲は現在、ただ一つの領域に制限されます。
- All routers within the area are assumed to run a QoS enabled
version of OSPF, i.e., inter-operability with non-QoS aware
versions of the OSPF protocol is not considered.
- 領域の中のルータがQoSを走らせると思われるすべてがOSPF(すなわち、OSPFプロトコルのバージョンが考えられないのを意識している非QoSがある相互運用性)のバージョンを可能にしました。
- All interfaces on a router are assumed to be QoS capable.
- ルータのすべてのインタフェースができるQoSであると思われます。
4.2.2. Architecture
4.2.2. 構造
The above design decisions and assumptions resulted in the architecture shown in Figure 2. It consists of three major components: the signaling component (RSVP in our case); the QoS routing component; and the traffic manager. In the rest of this section we concentrate on the structure and operation of the QoS routing component. As can be seen in Figure 2, the QoS routing extensions are further divided into the following modules:
上のデザイン決定と仮定は図2に示された構造をもたらしました。 それは3個の主要コンポーネントから成ります: シグナリングコンポーネント(私たちの場合におけるRSVP)。 QoSルーティングの部品。 そして、営業主幹。 このセクションの残りでは、私たちはQoSルーティングの部品の構造と操作に集中します。 図2で見ることができるように、QoSルーティング拡張子はさらに以下のモジュールに分割されます:
Apostolopoulos, et al. Experimental [Page 24] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[24ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
- Update trigger module determines when to advertise local link
state updates. This module implements a variety of triggering
policies: periodic, threshold based triggering, and class based
triggering. This module also implements a hold-down timer that
enforces minimum spacing between two consecutive update
triggerings from the same node.
- アップデート引き金のモジュールは、いつ地方のリンク州のアップデートの広告を出すかを決定します。 このモジュールはさまざまな引き金となる政策を実施します: 周期的であることで、敷居は引き金となることを基礎づけました、そして、クラスは引き金となることを基礎づけました。 また、このモジュールは同じノードから2連続したアップデートtriggeringsの間の最小のスペースを実施する抑制タイマを実行します。
- Pre-computation trigger module determines when to perform QoS path
pre-computation. So far, this module implements only periodic
pre-computation triggering.
- プレ計算引き金のモジュールは、いつQoS経路プレ計算を実行するかを決定します。 今までのところ、このモジュールは周期的なプレ計算の引き金となることだけを実行します。
- Path pre-computation module computes the QoS routing table based
on the QoS specific link state information as described in Section
2.3.1.
- 経路プレ計算モジュールはセクション2.3.1で説明されるようにQoSの特定のリンク州の情報に基づくQoS経路指定テーブルを計算します。
- Path selection and management module selects a path for a request
with particular QoS requirements, and manages it once selected,
i.e., reacts to link or reservation failures. Path selection is
performed as described in Section 2.3.1. Path management
functionality is not currently supported.
- 経路選択と管理モジュールは、要求のために特定のQoS要件で経路を選択して、すなわち、いったん選択されると、それを管理します。リンクか予約失敗に反応します。 経路選択はセクション2.3.1で説明されるように実行されます。 経路管理の機能性は現在、支持されません。
- QoS routing table module implements the QoS specific routing
table, which is maintained independently of the other GateD
routing tables.
- QoS経路指定テーブルモジュールはQoSの特定の経路指定テーブルを実行します。(それは、他のGateD経路指定テーブルの如何にかかわらず維持されます)。
- Tspec mapping module maps request requirements expressed in the
form of RSVP Tspecs and Rspecs into the bandwidth requirements
that QoS routing uses.
- モジュール・マップを写像するTspecがRSVP TspecsとRspecsの形でQoSルーティングが使用する帯域幅要件に言い表された要件を要求します。
4.3. Major Implementation Issues
4.3. 主要な導入問題
Mapping the above design to the framework of the GateD implementation of OSPF led to a number of issues and design decisions. These issues mainly fell under two categories: a) interoperation of the QoS extensions with pre-existing similar OSPF mechanisms, and b) structure, placement, and organization of the QoS routing table. Next, we briefly discuss these issues and justify the resulting design decisions.
OSPFのGateD実現の枠組みに上のデザインを写像するのは多くの問題とデザイン決定に通じました。 これらの問題は2つ未満のカテゴリで主に下がりました: a) QoS経路指定テーブルの同様のOSPFメカニズムを先在させるQoS拡張子のinteroperation、b)構造、プレースメント、および組織。 次に、私たちは、簡潔にこれらの問題について議論して、結果として起こるデザイン決定を正当化します。
Apostolopoulos, et al. Experimental [Page 25] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[25ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
+--------------------------------------------------+
| +-----------------------------+ |
| | QoS Route Table Computation | |
| +-----------------------------+ |
| | | |
| V | |
| +-----------------+ | |
+-------------->| QoS Route Table | | |
| | +-----------------+ | |
| | | |
| | +----------------------+ +---------------+ |
| | | Core OSPF Functions | | Precomputation| |
| | | + | | Trigger | |
| | | (Enhanced) Topology | +---------------+ |
| | | Data Base | | |
| | +----------------------+ | |
| | | | | |
| | | +----------------------------+ |
| | | | Receive and update QoS-LSA | |
| | | +----------------------------+ |
| | | | |
| | | +----------------+ |
| | | | Local Interface| |
| | | | Status Monitor | |
| | | +----------------+ |
+----------------+ | | | |
| Path Selection | | +--------------+ +----------------+ |
| & Management | | | Build and | | Link State | |
+----------------+ | | Send QoS-LSA |----------| Update Trigger | |
| | +--------------+ +----------------+ |
+----------------+ | | |
| QoS Parameter | | | |
| Mapping | | OSPF with QoS Routing Extensions | |
|----------------+ +-------------------------------------------|------+
| |
+----------------+ +----------+
| QoS Route | | Local |
| Request Client |<---------------------------------------->| Resource |
| (e.g. RSVP) | | Manager |
+----------------+ +----------+
+--------------------------------------------------+ | +-----------------------------+ | | | QoSルートテーブル計算| | | +-----------------------------+ | | | | | | V| | | +-----------------+ | | +-------------->| QoSルートテーブル| | | | | +-----------------+ | | | | | | | | +----------------------+ +---------------+ | | | | コアOSPF機能| | Precomputation| | | | | + | | 引き金| | | | | (高められます) トポロジー| +---------------+ | | | | データベース| | | | | +----------------------+ | | | | | | | | | | | +----------------------------+ | | | | | QoS-LSAを受けて、アップデートしてください。| | | | | +----------------------------+ | | | | | | | | | +----------------+ | | | | | 局所界面| | | | | | 状態モニター| | | | | +----------------+ | +----------------+ | | | | | 経路選択| | +--------------+ +----------------+ | | 管理| | | そして建て。| | リンク状態| | +----------------+ | | QoS-LSAを送ってください。|----------| アップデート引き金| | | | +--------------+ +----------------+ | +----------------+ | | | | QoSパラメタ| | | | | マッピング| | QoSルート設定拡張子があるOSPF| | |----------------+ +-------------------------------------------|------+ | | +----------------+ +----------+ | QoSルート| | ローカル| | クライアントを要求してください。|<---------------------------------------->| リソース| | (例えば、RSVP) | | マネージャ| +----------------+ +----------+
Figure 2: The software architecture
図2: ソフトウェア・アーキテクチャ
Apostolopoulos, et al. Experimental [Page 26] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[26ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
The ability to trigger link state updates in response to changes in bandwidth availability on interfaces is an essential component of the QoS extensions. Mechanisms for triggering these updates and controlling their rate have been mentioned in Section 2.2. In addition, OSPF implements its own mechanism for triggering link state updates as well as its own hold down timer, which may be incompatible with what is used for the QoS link state updates. We handle such potential conflicts as follows. First, since OSPF triggers updates on a periodic basis with low frequency, we expect these updates to be only a small part of the total volume of updates generated. As a result, we chose to maintain the periodic update triggering of OSPF. Resolving conflicts in the settings of the different hold down timer settings requires more care. In particular, it is important to ensure that the existing OSPF hold down timer does not interfere with QoS updates. One option is to disable the existing OSPF timer, but protection against transient overloads calls for some hold down timer, albeit with a small value. As a result, the existing OSPF hold down timer was kept, but reduced its value to 1 second. This value is low enough (actually is the lowest possible, since GateD timers have a maximum resolution of 1 second) so that it does not interfere with the generation of the QoS link state updates, which will actually often have hold down timers of their own with higher values. An additional complexity is that the triggering of QoS link state updates needs to be made aware of updates performed by OSPF itself. This is necessary, as regular OSPF updates also carry bandwidth information, and this needs to be considered by QoS updates to properly determine when to trigger a new link state update.
インタフェースに関する帯域幅の有用性における変化に対応してリンク州のアップデートの引き金となる能力はQoS拡張子の必須成分です。 これらのアップデートの引き金となって、それらのレートを制御するためのメカニズムはセクション2.2で言及されました。 さらに、OSPFは、それ自身の抑制タイマと同様にリンク州のアップデートの引き金となるようにそれ自身のメカニズムを実行します。タイマはQoSリンク州のアップデートに使用されることと非互換であるかもしれません。 私たちは以下のそのような潜在的闘争を扱います。 OSPFが長波で周期的ベースに関する最新情報の引き金となって、まず最初に、私たちは、これらのアップデートが発生するアップデートの全容積の小さい部分にすぎないと予想します。 その結果、私たちは、OSPFの周期的なアップデートの引き金となることを維持するのを選びました。 異なった抑制タイマ設定の設定での闘争を解決するのは、より多くの注意を必要とします。 タイマの下側への既存のOSPF保持がQoSアップデートを妨げないのを保証するのは特に、重要です。 1つのオプションが既存のOSPFタイマを損傷することですが、一時的なオーバーロードに対する保護はある抑制タイマを求めます、小さい値で。 その結果、タイマの下側への既存のOSPF保持は、1秒まで保たれましたが、値を減少させました。 この値が十分低いので(GateDタイマには最大1秒の解決があるので、実際に最も低いです可能な)、それはQoSリンク州のアップデートの世代を妨げません。(実際に、アップデートにはそれら自身の抑制タイマが、より高い値と共にしばしばあるでしょう)。 追加複雑さはQoSリンク州のアップデートの引き金となるのが、OSPF自身によって実行されたアップデートを意識しているのに作られている必要があるということです。 これが必要です、また、定期的なOSPFアップデートが帯域幅情報を運んで、これが、いつ新しいリンク州のアップデートの引き金となるかを適切に決定するとQoSアップデートで考えられる必要があるとき。
Another existing OSPF mechanism that has the potential to interfere with the extensions needed for QoS routing, is the support for delayed acknowledgments that allows aggregation of acknowledgments for multiple LSAs. Since link state updates are maintained in retransmission queues until acknowledged, excessive delay in the generation of the acknowledgement combined with the increased rates of QoS updates may result in overflows of the retransmission queues. To avoid these potential overflows, this mechanism was bypassed altogether and LSAs received from neighboring routers were immediately acknowledged. Another approach which was considered but not implemented, was to make QoS LSAs unreliable, i.e., eliminate their acknowledgments, so as to avoid any potential interference. Making QoS LSAs unreliable would be a reasonable design choice because of their higher frequency compared to the regular LSAs and the reduced impact that the loss of a QoS LSA has on the protocol operation. Note that the loss of a QoS LSA does not interfere with the base operation of OSPF, and only transiently reduces the quality of paths discovered by QoS routing.
QoSルーティングに必要である拡大を妨げる可能性を持っている別の既存のOSPFメカニズムは複数のLSAsのための承認の集合を許容する遅れた承認のサポートです。 リンク州のアップデートが再送キューで承認されるまで維持されるので、QoSアップデートの増加する速度に結合された承認の世代の過度の遅れは再送キューのオーバーフローをもたらすかもしれません。 これらの潜在的オーバーフローを避けるために、このメカニズムは全体で迂回しました、そして、隣接しているルータから受け取られたLSAsはすぐに、承認されました。 考えられましたが、実行されなかった別のアプローチがQoS LSAsを頼り無くすることであり、すなわち、彼らの承認を排除してください、どんな潜在的干渉も避けるために。 QoS LSAの損失がプロトコル操作のときに持っている通常のLSAsと減少している影響力と比べて、QoS LSAsを頼り無くするのは、彼らの高周波化のために合理的なデザイン選択でしょう。 QoS LSAの損失がOSPFのベース操作を妨げないで、はかなくQoSルーティングで発見された経路の品質を減少させるだけであることに注意してください。
Apostolopoulos, et al. Experimental [Page 27] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[27ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
The structure and placement of the QoS routing table also raises some interesting implementation issues. Pre-computed paths are placed into a QoS routing table. This table is implemented as a set of path structures, one for each destination, which contain all the available paths to this destination. In order to be able to efficiently locate individual path structures, an access structure is needed. In order to minimize the develpement effort, the radix tree structure used for the regular GateD routing tables was reused. In addition, the QoS routing table was kept independent of the GateD routing tables to conform to the design goal of localizing changes and minimizing the impact on the existing OSPF code. An additional reason for maintaining the QoS routing separate and self-contained is that it is re-computed under conditions that are different from those used for the regular routing tables.
また、QoS経路指定テーブルの構造とプレースメントはいくつかのおもしろい導入問題を提起します。 あらかじめ計算された経路はQoS経路指定テーブルに置かれます。 このテーブルは1セットの経路構造、すべての利用可能な経路をこの目的地に含む各目的地あたりのものとして実行されます。 効率的に個々の経路構造の場所を見つけることができるように、アクセス構造が必要です。 develpementの努力を最小にするために、通常のGateD経路指定テーブルに使用される基数木構造は再利用されました。 さらに、QoS経路指定テーブルは既存のOSPFコードで変化を局部にとどめて、衝撃を最小にするというデザイン目標に従わせるGateD経路指定テーブルから独立しているように保たれました。 別々で自己充足的にQoSルーティングを維持する追加理由はそれが通常の経路指定テーブルに使用されるものと異なった条件のもとで再計算されるということです。
Furthermore, since the QoS routing table is re-built frequently, it must be organized so that its computation is efficient. A common operation during the computation of the QoS routing table is mapping a link state database entry to the corresponding path structure. In order to make this operation efficient, the link state database entries were extended to contain a pointer to the corresponding path structure. In addition, when a new QoS routing table is to be computed, the previous one must be de-allocated. This is accomplished by traversing the radix tree in-order, and de-allocating each node in the tree. This full de-allocation of the QoS routing table is potentially wasteful, especially since memory allocation and de-allocation is an expensive operation. Furthermore, because path pre-computations are typically not triggered by changes in topology, the set of destinations will usually remain the same and correspond to an unchanged radix tree. A natural optimization would then be to de-allocate only the path structures and maintain the radix tree. A further enhancement would be to maintain the path structures as well, and attempt to incrementally update them only when required. However, despite the potential gains, these optimizations have not been included in the initial implementation. The main reason is that they involve subtle and numerous checks to ensure the integrity of the overall data structure at all times, e.g., correctly remove failed destinations from the radix tree and update the tree accordingly.
その上、QoS経路指定テーブルが頻繁に再建されるのでそれを組織化しなければならないので、計算は効率的です。 QoS経路指定テーブルの計算の間の一般的な操作はリンク州のデータベースエントリーを対応する経路構造に写像しています。 この操作を効率的にして、リンク州のデータベースエントリーは、対応する経路構造にポインタを含むように広げられました。 新しいQoS経路指定テーブルを計算することになっているとき、さらに、反-前の割り当てなければなりません。 これは、基数木の整然とするのを横断して、木に反-各ノードを割り当てることによって、達成されます。 QoS経路指定テーブルのこの完全な反-配分は潜在的に無駄です、特にメモリアロケーションと反-配分が高価な操作であるので。 その上、経路プレ計算がトポロジーの変化によって通常引き起こされないので、目的地のセットは、通常、同じままで残っていて、変わりのない基数木に対応するでしょう。 自然な最適化は、次に、反-経路構造だけを割り当てて、基数木を維持するだろうことです。 さらなる増進は、必要である場合にだけ、また、経路構造を主張して、それらを増加してアップデートするのを試みるだろうことです。 しかしながら、潜在的利益にもかかわらず、これらの最適化は初期の実現に含まれていません。 主な理由は彼らがいつも総合的なデータ構造の保全を確実にするために微妙で頻繁なチェックにかかわるということです、そして、例えば、基数木から失敗した目的地を正しく取り除いてください、そして、それに従って、木をアップデートしてください。
Apostolopoulos, et al. Experimental [Page 28] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[28ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
4.4. Bandwidth and Processing Overhead of QoS Routing
4.4. QoSルート設定の帯域幅と処理オーバヘッド
After completing the implementation outlined in the previous sections, it was possible to perform an experimental study of the cost and nature of the overhead of the QoS routing extensions proposed in this document. In particular, using a simple setup consisting of two interconnected routers, it is possible to measure the cost of individual QoS routing related operations. These operations are: a) computation of the QoS routing table, b) selection of a path from the QoS routing table, c) generation of a link state update, and d) reception of a link state update. Note that the last two operations are not really specific to QoS routing since regular OSPF also performs them. Nevertheless, we expect the more sensitive update triggering mechanisms required for effective QoS routing to result in increased number of updates, making the cost of processing updates an important component of the QoS routing overhead. An additional cost dimension is the memory required for storing the QoS routing table. Scaling of the above costs with increasing sizes of the topology database was investigated by artificially populating the topology databases of the routers under measurement.
前項で概説された実現を終了した後に、費用の実証研究を実行するのが可能であり、QoSルーティング拡張子のオーバーヘッドの本質は本書では提案しました。 2つのインタコネクトされたルータから成る簡単なセットアップを使用して、関連する操作を発送する個々のQoSの費用を測定するのは特に、可能です。 これらの操作は以下の通りです。 a) QoS経路指定テーブルの計算、QoS経路指定テーブルからの経路のb)選択、リンク州のアップデートのc)世代、およびリンク州のアップデートのd)レセプション。 また、通常のOSPFが彼らを実行するので最後の2つの操作が本当にQoSルーティングに特定でないことに注意してください。 それにもかかわらず、私たちは、より敏感なアップデートトリガー・メカニズムが効果的なQoSルーティングが増加する数のアップデートをもたらすのが必要であると予想します、処理アップデートの費用をQoSルーティングオーバーヘッドの重要なコンポーネントにして。 別途費用寸法はQoS経路指定テーブルを収納するのに必要であるメモリです。 トポロジーデータベースの増加するサイズがある上のコストのスケーリングは、人工的に測定でルータに関するトポロジーデータベースに居住することによって、調査されました。
Table 1 shows how the measured costs depend on the size of the topology. The topology used in the measurements was built by replicating a basic building block consisting of four routers connected with transit networks in a rectangular arrangement. The details of the topology and the measurements can be found in [AGK99]. The system running the GateD software was an IBM IntelliStation Z Pro with a Pentium Pro processor at 200 MHz, 64 MBytes or real memory, running FreeBSD 2.2.5-RELEASE and GateD 4. From the results of Table 1, one can observe that the cost of path pre-computation is not much higher than that of the regular SPF computation. However, path pre- computation may need to be performed much more often than the SPF computation, and this can potentially lead to higher processing costs. This issue was investigated in a set of subsequent experiments, that are described later in this section. The other cost components reported in Table 1 include memory, and it can be seen that the QoS routing table requires roughly 80% more memory than the regular routing table. Finally, the cost of selecting a path is found to be very small compared to the path pre-computation times. As expected, all the measured quantities increase as the size of the topology increases. In particular, the storage requirements and the processing costs for both SPF computation and QoS path pre- computation scale almost linearly with the network size.
テーブル1は測定コストをどうトポロジーのサイズに依存するかを示しています。 測定値で使用されるトポロジーは、長方形のアレンジメントで輸送網に関連づけられた4つのルータから成る基本的なブロックを模写することによって、造られました。 [AGK99]でトポロジーの詳細と測定を見つけることができます。 GateDソフトウェアを動かしたシステムは200MHz、64MBytesまたは本当の記憶におけるPentium ProプロセッサがあるIBM IntelliStation Z Proでした、無料OSの一つ2.2.5-RELEASEとGateD4を走らせて。 Table1の結果から、人は、経路プレ計算の費用が定期的なSPF計算のものよりあまり高くないのを観測できます。 しかしながら、経路プレ計算は、SPF計算よりはるかにしばしば実行される必要があるかもしれません、そして、これは潜在的により高い処理コストに通じることができます。 この問題はその後の実験のセットで調査されて、それは後でこのセクションで説明されます。 Table1で報告された他の費用コンポーネントはメモリを含んでいます、そして、QoS経路指定テーブルが通常の経路指定テーブルよりおよそ80%多くのメモリを必要とするのを見ることができます。 最終的に、経路を選択する費用は経路プレ計算回数と比べて、非常に小さいのがわかっています。 予想されるように、トポロジーのサイズが増加するのに従って、すべての測定した量が増加します。 特に、SPF計算とQoS経路プレ計算スケールの両方のための格納要件と処理コストはネットワークの規模でほとんど直線的です。
Apostolopoulos, et al. Experimental [Page 29] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[29ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
________________________________________________________________________ |Link_state_database_size_______|_25_|__49_|__81__|__121_|__169_|__225_| |Regular_SPF_time_(microsec)____|215_|_440_|_747__|_1158_|_1621_|_2187_| |Pre-computation_time_(microsec)|736_|_1622|_2883_|_4602_|_6617_|_9265_| |SPF_routing_table_size_(bytes)_|2608|_4984|_8152_|_12112|_16864|_22408| |QoS_routing_table_size_(bytes)_|3924|_7952|_13148|_19736|_27676|_36796| |Path_Selection_time_(microsec)_|_.7_|_1.6_|__2.8_|__4.6_|__6.6_|__9.2_|
________________________________________________________________________ |リンク_州の_データベース_サイズ_______|_25_|__49_|__81__|__121_|__169_|__225_| |通常の_SPF_時間_(マイクロセカンド)____|215_|_440_|_747__|_1158_|_1621_|_2187_| |プレ計算_時間_(マイクロセカンド)|736_|_1622|_2883_|_4602_|_6617_|_9265_| |SPF_ルーティング_テーブル_サイズ_(バイト)_|2608|_4984|_8152_|_12112|_16864|_22408| |QoS_ルーティング_テーブル_サイズ_(バイト)_|3924|_7952|_13148|_19736|_27676|_36796| |経路_選択_時間_(マイクロセカンド)_|_.7_|_1.6_|__2.8_|__4.6_|__6.6_|__9.2_|
Table 1: Stand alone QoS routing costs
テーブル1: スタンドアロンQoSルーティングコスト
In addition to the stand alone costs reported in Table 1, it is important to assess the actual operational load induced by QoS routing in the context of a large network. Since it is not practical to reproduce a large scale network in a lab setting, the approach used was to combine simulation and measurements. Specifically, a simulation was used to obtain a time stamped trace of QoS routing related events that occur in a given router in a large scale network. The trace was then used to artificially induce similar load conditions on a real router and its adjacent links. In particular, it was used to measure the processing load at the router and bandwidth usage that could be attributed to QoS updates. A more complete discussion of the measurement method and related considerations can be found in [AGK99].
Table1で報告されたスタンドアロンコストに加えて、大きいネットワークの文脈でのQoSルーティングで引き起こされた実際の操作上の負荷を評価するのは重要です。 研究室設定で大規模ネットワークを再生させるのが実用的でないので、使用されるアプローチはシミュレーションと測定値を結合することでした。 明確に、シミュレーションは、与えられたルータで大規模ネットワークで起こる関連する出来事を発送しながらQoSの時間の押し込まれた跡を得るのに使用されました。 そして、跡は、人工的に本当のルータとその隣接しているリンクに関する同様の負荷状態を引き起こすのに使用されました。 特に、それは、QoSアップデートの結果と考えることができたルータと帯域幅用法で処理負荷を測定するのに使用されました。 [AGK99]で測定方法と関連する問題の、より完全な議論を見つけることができます。
The use of a simulation further allows the use of different configurations, where network topology is varied together with other QoS parameters such as a) period of pre-computation, and b) threshold for triggering link state updates. The results reported here were derived using two types of topologies. One based on a regular but artificial 8x8 mesh network, and another (isp) which has been used in several previous studies [AGKT98, AT98] and that approximates the network of a nation-wide ISP. As far as pre-computation periods are concerned, three values of 1, 5 and 50 seconds were chosen, and for the triggering of link state update thresholds of 10% and 80% were used. These values were selected as they cover a wide range in terms of precision of pre-computed paths and accuracy of the link state information available at the routers. Also note that 1 second is the smallest pre-computation period allowed by GateD.
シミュレーションの使用はさらに異なった構成の使用を許します、ネットワーク形態がプレ計算のa)一区切りなどの他のQoSパラメタ、およびリンク州のアップデートの引き金となるためのb)敷居と共に変えられるところで。 結果は、topologiesの2つのタイプを使用するのが引き出されたと報告しました。 1つは網目状ネットワーク、および前のいくつかの研究[AGKT98、AT98]で使用されて、全国的なISPのネットワークに近似する別の(isp)を通常の、しかし、人工の8×8に基礎づけました。 1の3つの値、プレ計算の期間は関係があるのと同じくらい遠くて、5と50秒は、選ばれて、10%と80%のリンク州のアップデート敷居の引き金となるのに使用されました。 あらかじめ計算された経路の精度とルータで利用可能なリンク州の情報の精度に関して広範囲にわたるとき、これらの値は選択されました。 また、1秒がGateDによって許容された中で最も小さいプレ計算の期間であることに注意してください。
Table 2 provides results on the processing load at the router driven by the simulation trace, for the two topologies and different combinations of QoS parameters, i.e., pre-computation period and threshold for triggering link state updates. Table 3 gives the bandwidth consumption of QoS updates on the links adjacent to the router.
テーブル2はすなわち、QoSパラメタ、計算のプレ期間の2topologiesと異なった組み合わせのためのシミュレーション跡によって追い立てられたルータとリンク州のアップデートの引き金となるための敷居で処理負荷の結果を提供します。 テーブル3はルータに隣接してリンクにおけるQoSアップデートの帯域幅消費を与えます。
Apostolopoulos, et al. Experimental [Page 30] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[30ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
________________________________________________________________
|_____________________|_________Pre-computation_Period_________|
|Link_state_threshold_|___1_sec____|____5_sec____|____50_sec___|
|_________10%_________|.45%_(1.6%)_|__.29%_(2%)__|__.17%_(3%)__|
|_________80%_________|.16%_(2.4%)_|__.04%_(3%)__|_.02%_(3.8%)_|
________________________________________________________________ |_____________________|_________プレの計算_期間_________| |リンク_州の_敷居_|___1_秒____|____5_秒____|____50_秒___| |_________10%_________|.45%_(1.6%)_|__.29%_(2%)__|__.17%_(3%)__| |_________80%_________|.16%_(2.4%)_|__.04%_(3%)__|_.02%_(3.8%)_|
isp
isp
________________________________________________________________
|_________10%_________|3.37%_(2.1%)|_2.23%_(3.3%)|_1.78%_(7.7%)|
|_________80%_________|1.54%_(5.4%)|_.42%_(6.6%)_|_.14%_(10.4%)|
________________________________________________________________ |_________10%_________|3.37%_(2.1%)|_2.23%_(3.3%)|_1.78%_(7.7%)| |_________80%_________|1.54%_(5.4%)|_.42%_(6.6%)_|_.14%_(10.4%)|
8x8 mesh
8×8 メッシュ
Table 2: Router processing load and (bandwidth blocking).
テーブル2: ルータ処理負荷と(帯域幅ブロッキング。)
In Table 2, processing load is expressed as the percentage of the total CPU resources that are consumed by GateD processing. The same table also shows the routing performance that is achieved for each combination of QoS parameters, so that comparison of the different processing cost/routing performance trade-offs can be made. Routing performance is measured using the bandwidth blocking ratio, defined as the sum of requested bandwidth of the requests that were rejected over the total offered bandwidth. As can be seen from Table 2, processing load is low even when the QoS routing table is recomputed every second, and LSAs are generated every time the available bandwidth on a link changes by more than 10% of the last advertised value. This seems to indicate that given today's processor technology, QoS routing should not be viewed as a costly enhancement, at least not in terms of its processing requirements. Another general observation is that while network size has obviously an impact, it does not seem to drastically affect the relative influence of the different parameters. In particular, despite the differences that exist between the isp and mesh topologies, changing the pre- computation period or the update threshold translates into essentially similar relative changes.
Table2では、処理負荷はGateD処理で消費される総CPUリソースの割合として言い表されます。 また、同じテーブルはQoSパラメタの各組み合わせのために達成されるルーティング性能を示しています、異なった加工費/ルーティング性能トレードオフの比較をすることができるように。 ルート設定性能は帯域幅ブロッキング比を使用することで測定されます、合計の上で拒絶された要求の要求された帯域幅の合計が帯域幅を提供したと定義されて。 QoS経路指定テーブルが毎秒、再計算されて、リンクにおける利用可能な帯域幅が最後に広告を出した価値の10%以上変えるときはいつも、LSAsが発生さえするとき、Table2から見ることができるように、処理負荷は低いです。 これは今日のプロセッサ技術を考えて、QoSルーティングが高価な増進として少なくとも処理所要で見なされるべきでないのを示すように思えます。 別の一般的な観測はネットワークの規模には影響力が明らかにある間異なったパラメタの相対的な影響に抜本的に影響するように思えないということです。 ispとメッシュtopologiesの間に存在する違いにもかかわらず、プレ計算の期間かアップデート敷居を特に変えるのは本質的には同様の相対的な変化に翻訳されます。
Similar conclusions can be drawn for the update traffic shown in Table 3. In all cases, this traffic is only a small fraction of the link's capacity. Clearly, both the router load and the link bandwidth consumption depend on the router and link that was the target of the measurements and will vary for different choices. The results shown here are meant to be indicative, and a more complete discussion can be found in [AGK99].
同様の結論にTable3に示されたアップデート交通に達せられることができます。 すべての場合では、この交通はリンクの容量のわずかな部分にすぎません。 明確に、ルータ負荷とリンク帯域幅消費の両方が測定値の目標であり、異なった選択のために異なるルータとリンクに依存します。 ここに示された結果が暗示していることを意味して、[AGK99]で、より完全な議論を見つけることができます。
Apostolopoulos, et al. Experimental [Page 31] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[31ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
_______________________________________
|_Link_state_threshold_|_______________|
|_________10%__________|3112_bytes/sec_|
|_________80%__________|177_bytes/sec__|
_______________________________________ |_リンク_州の_敷居_|_______________| |_________10%__________|3112_バイト/秒の_| |_________80%__________|177_バイト/秒の__|
isp
________________________________________
|_________10%__________|15438_bytes/sec_|
|_________80%__________|1053_bytes/sec__|
isp________________________________________ |_________10%__________|15438_バイト/秒の_| |_________80%__________|1053_バイト/秒の__|
8x8 mesh
8×8 メッシュ
Table 3: Link state update traffic
テーブル3: リンク州のアップデート交通
Summarizing, by carrying out the implementation of the proposed QoS routing extensions to OSPF we demonstrated that such extensions are fairly straightforward to implement. Furthermore, by measuring the performance of the real system we were able to demonstrate that the overheads associated with QoS routing are not excessive, and are definitely within the capabilities of modern processor and workstation technology.
要約、提案されたQoSルーティング拡張子の実現をOSPFに行うことによって、私たちはそのような拡大が実行するためにかなり簡単であることを示しました。 その上、実システムの性能を測定することによって、私たちは、QoSルーティングに関連しているオーバーヘッドが過度でないことを示すことができて、確実に近代的なプロセッサとワークステーション技術の能力の中にいます。
5. Security Considerations
5. セキュリティ問題
The QoS extensions proposed in this document do not raise any security considerations that are in addition to the ones associated with regular OSPF. The security considerations of OSPF are presented in [Moy98]. However, it should be noted that this document assumes the availability of some entity responsible for assessing the legitimacy of QoS requests. For example, when the protocol used for initiating QoS requests is the RSVP protocol, this capability can be provided through the use of RSVP Policy Decision Points and Policy Enforcement Points as described in [YPG97]. Similarly, a policy server enforcing the acceptability of QoS requests by implementing decisions based on the rules and languages of [RMK+98], would also be capable of providing the desired functionality.
本書では提案されたQoS拡張子は通常のOSPFに関連しているものに加えているどんなセキュリティ問題も提起しません。 OSPFのセキュリティ問題は[Moy98]に提示されます。 しかしながら、このドキュメントが、何らかの実体の有用性がQoS要求の合法性を評価するのに原因となると仮定することに注意されるべきです。 QoS要求を開始するのに使用されるプロトコルがRSVPプロトコルであるときに、例えば、[YPG97]で説明されるようにRSVP Policy Decision PointsとPolicy Enforcement Pointsの使用でこの能力を提供できます。 また、同様に、方針サーバが[RMK+98]の規則と言語に基づく決定を実行することによってQoS要求の受容性を実施する場合、必要な機能性を提供できるでしょう。
Apostolopoulos, et al. Experimental [Page 32] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[32ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
APPENDICES
付録
A. Pseudocode for the BF Based Pre-Computation Algorithm
A。 BFのための擬似コードはプレ計算アルゴリズムを基礎づけました。
Note: The pseudocode below assumes a hop-by-hop forwarding approach in updating the neighbor field. The modifications needed to support explicit route construction are straightforward. The pseudocode also does not handle equal cost multi-paths for simplicity, but the modification needed to add this support are straightforward.
以下に注意してください。 以下の擬似コードは、隣人分野をアップデートする際にホップごとの推進がアプローチであると仮定します。 明白なルート工事を支持するのに必要である変更は簡単です。 擬似コードも簡単さのためのマルチ経路の等しい費用を扱いませんが、このサポートを加えるのに必要である変更は簡単です。
Input:
V = set of vertices, labeled by integers 1 to N.
L = set of edges, labeled by ordered pairs (n,m) of vertex labels.
s = source vertex (at which the algorithm is executed).
For all edges (n,m) in L:
* b(n,m) = available bandwidth (according to last received update)
on interface associated with the edge between vertices n and m.
* If(n,m) outgoing interface corresponding to edge (n,m) when n is
a router.
H = maximum hop-count (at most the graph diameter).
以下を入力してください。 Vは整数1によって=が設定した順序対(n、m)の頂点ラベルによってラベルされた縁のN.Lとラベルされた頭頂のセットと等しいです。sはソースの頂点(アルゴリズムはそこで実行される)と等しいです。 Lのすべての縁(n、m)に: * b(n、m)は頭頂nとmの間の縁に関連しているインタフェースにおける利用可能な帯域幅(最近の容認されたアップデートに従って)と等しいです。 * nであるときに、斜めに進ませる(n、m)外向的なインタフェース対応(n、m)がルータであるなら。 Hは最大のホップカウント(高々グラフ直径)と等しいです。
Type:
tab_entry: record
bw = integer,
neighbor = integer 1..N.
以下をタイプしてください。 _エントリーにタブを付けてください: bw=整数、隣人=整数1を記録してください。N。
Variables:
TT[1..N, 1..H]: topology table, whose (n,h) entry is a tab_entry
record, such that:
TT[n,h].bw is the maximum available bandwidth (as
known thus far) on a path of at most h hops
between vertices s and n,
TT[n,h].neighbor is the first hop on that path (a
neighbor of s). It is either a router or the
destination n.
変数: TT[1..N、1..H]: トポロジーテーブル。その(n、h)エントリーはタブ_エントリレコード、以下のことのようにものです。 TT[n、h].bwが高々頭頂sとnの間のhホップの経路における最大の利用可能な帯域幅(これまでのところ知られているように)である、TT[n、h].neighborはその経路(sの隣人)の最初のホップです。 それは、ルータか目的地nのどちらかです。
S_prev: list of vertices that changed a bw value in the TT table
in the previous iteration.
S_new: list of vertices that changed a bw value (in the TT table
etc.) in the current iteration.
_S prev: TTテーブルで前の繰り返しでbw値を変えた頭頂のリスト。 S_新しい: 現在の繰り返しでbw値を変えた(TTでは、などを見送ってください)頭頂のリスト。
The Algorithm:
アルゴリズム:
begin;
始まってください。
for n:=1 to N do /* initialization */
begin;
TT[n,0].bw := 0;
n: 1〜Nが/*初期化*/をする=に関しては、始まってください。 TT[n、0].bw:=0。
Apostolopoulos, et al. Experimental [Page 33] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[33ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
TT[n,0].neighbor := null
TT[n,1].bw := 0;
TT[n,1].neighbor := null
end;
TT[s,0].bw := infinity;
TT[n、0]の.neighborの:=のヌルTT[n、1].bw:=0。 TT[n、1].neighbor:=ヌルの終わり。 TT[s、0].bw:=無限。
reset S_prev;
for all neighbors n of s do
begin;
TT[n,1].bw := max( TT[n,1].bw, b[s,n]);
if (TT[n,1].bw = b[s,n]) then TT[n,1].neighbor := If(s,n);
/* need to make sure we are picking the maximum */
/* bandwidth path for routers that can be reached */
/* through both networks and point-to-point links */
if (n is a router) then
S_prev := S_prev union {n}
/* only a router is added to S_prev, */
/* if it is not already included in S_prev */
else /* n is a network: */
/* proceed with network--router edges, without */
/* counting another hop */
for all (n,k) in L, k <> s, do
/* i.e., for all other neighboring routers of n */
begin;
TT[k,1].bw := max( min( TT[n,1].bw, b[n,k]), TT[k,1].bw );
/* In case k could be reached through another path */
/* (a point-to-point link or another network) with */
/* more bandwidth, we do not want to update TT[k,1].bw */
if (min( TT[n,1].bw, b[n,k]) = TT[k,1].bw )
/* If we have updated TT[k,1].bw by going through */
/* network n */
then TT[k,1].neighbor := If(s,n);
/* neighbor is interface to network n */
if ( {k} not in S_prev) then S_prev := S_prev union {k}
/* only routers are added to S_prev, but we again need */
/* to check they are not already included in S_prev */
end
end;
S_prevをリセットしてください。 すべての隣人に関しては、n sが始まります。 TT[n、1].bw:=最大(TT[n、1].bw、b[s、n])。 (TT[n、1].bwは(s、n)であるならb[s、n)当時のTT[n、1].neighbor:=と等しいです。 私たちが最大の*//*帯域幅経路をルータに選んでいるのを確実にするネットワークとポイントツーポイント接続の両方を通した達している*//*が*/であることができたなら次に、(nはルータです)S_prev:=S_prev組合n/*専用であるならルータがそうである/*必要性がS_prevに加えられて、*それがS_prev*/ほかの/*nに既に含まれていないなら、*//はネットワークです: *//*は、Lですべて(n、k)のための別のホップ*/を数える*//*のない縁(k<>s)がすなわち、n*の他のすべての隣接しているルータのための/*をするネットワーク--ルータで続くか、または始まります。 TT[k、1].bw:=最大(分(TT[n、1].bw、b[n、k])、TT[k、1].bw)。 場合kにおける/*に別の経路*//*(ポイントツーポイント接続か別のネットワーク)を通して*//で達することができました。*より多くの帯域幅、(分(TT[n、1].bw、b[n、k])=TT[k、1].bw)/であるなら*私たちが(s、n)であるなら*//*ネットワークn*/当時のTT[k、1].neighbor:=を通ることによってTT[k、1].bwをアップデートしたならTT[k、1].bw*/をアップデートしたいと思いません。 次に、(S_prevでないところのk)S_prev:=S_prev組合k/*であるなら、/*隣人はネットワークn*/へのインタフェースです。ルータだけがS_prevに加えられますが、私たちは再びS_prev*/エンドエンドに既に含まれなかった状態でチェックへの*//*を必要とします。
for h:=2 to H do /* consider all possible number of hops */
begin;
reset S_new;
for all vertices m in V do
begin;
TT[m,h].bw := TT[m,h-1].bw;
TT[m,h].neighbor := TT[m,h-1].neighbor
end;
h: Hへの2が/*をする=に関しては、すべての可能な数のホップ*/が始まると考えてください。 新しい状態でS_をリセットしてください。 Vのすべての頭頂mに関しては、始まってください。 TT[m、h].bw:=TT[m、h-1].bw。 TT[m、h].neighbor:=TT[m、h-1].neighborエンド。
Apostolopoulos, et al. Experimental [Page 34] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[34ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
for all vertices n in S_prev do
/* as shall become evident, S_prev contains only routers */
begin;
for all edges (n,m) in L do
if min( TT[n,h-1].bw, b[n,m]) > TT[m,h].bw then
begin;
TT[m,h].bw := min( TT[n,h-1].bw, b[n,m]);
TT[m,h].neighbor := TT[n,h-1].neighbor;
if m is a router then S_new := S_new union {m}
/* only routers are added to S_new */
else /* m is a network: */
/* proceed with network--router edges, without counting */
/* them as another hop */
for all (m,k) in L, k <> n,
/* i.e., for all other neighboring routers of m */
if min( TT[m,h].bw, b[m,k]) > TT[k,h].bw then
begin;
/* Note: still counting it as the h-th hop, as (m,k) is */
/* a network--router edge */
TT[k,h].bw := min( TT[m,h].bw, b[m,k]);
TT[k,h].neighbor := TT[m,h].neighbor;
S_new := S_new union {k}
/* only routers are added to S_new */
end
end
end;
S_prev := S_new;
/* the two lists can be handled by a toggle bit */
if S_prev=null then h=H+1 /* if no changes then exit */
end;
*prevが含む明白なS_になるときS_prevのnが/をするすべての頭頂に関しては、ルータ*/だけ、が始まります。 Lの縁(n、m)がするすべてに関しては、分(TT[n、h-1].bw、b[n、m])>TT[m、h].bwであるなら、始まってください。 TT[m、h].bw:=分(TT[n、h-1].bw、b[n、m])。 TT[m、h].neighbor:=TT[n、h-1].neighbor。 当時の新しいルータ:=S_新しい組合S_mはmであるなら/です。*唯一のルータはS_新しい*/ほかの/*mに加えられているのが、ネットワークであるということです: *//*はネットワークを続けます--*//*を数えないで、*すなわち、次に、m*/の他のすべての隣接しているルータが分(TT[m、h].bw、b[m、k])>TT[k、h].bwであるなら始まるので、ルータはすべて(m、k)のための別のホップ*/としてL、k<>n、/でそれらを斜めに進ませます。 /*注意: まだそれをみなしている、h、-、跳んでください、(m、k)が*//*aネットワークであるので--ルータ縁の*/TT[k、h].bw:=第分(TT[m、h].bw、b[m、k]) TT[k、h].neighbor:=TT[m、h].neighbor。 ルータだけが加えられる新しいS:=S_新しい組合_k/*、S_の新しい*/エンド終わりのエンド。 S_prev:=S_新しい。 次に、どんな変化も*/終わりを出ないならS_prevがヌル当時のh=H+1/*と等しいなら、トグルビット*/は2が記載する/*を扱うことができます。
end.
終わってください。
Apostolopoulos, et al. Experimental [Page 35] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[35ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
B. On-Demand Dijkstra Algorithm for QoS Path Computation
B。 QoS経路計算のための要求次第のダイクストラAlgorithm
In the main text, we described an algorithm that allows pre- computation of QoS routes. However, it may be feasible in some instances, e.g., limited number of requests for QoS routes, to instead perform such computations on-demand, i.e., upon receipt of a request for a QoS route. The benefit of such an approach is that depending on how often recomputation of pre-computed routes is triggered, on-demand route computation can yield better routes by using the most recent link metrics available. Another benefit of on-demand path computation is the associated storage saving, i.e., there is no need for a QoS routing table. This is essentially the standard trade-off between memory and processing cycles.
主なテキストでは、私たちはQoSルートのプレ計算を許すアルゴリズムを説明しました。 しかしながら、それは代わりに要求次第でそのような計算を実行するためにQoSルートを求めるいくつかの例、例えば、限られた数の要求で可能であるかもしれません、すなわち、QoSルートを求める要求を受け取り次第。 そのようなアプローチの恩恵はあらかじめ計算されたルートの再計算がどれくらいの頻度で引き起こされるかによって、要求次第の経路計算が利用可能な最新のリンク測定基準を使用することによって、より良いルートをもたらすことができるということです。 要求次第の経路計算の別の恩恵が関連格納の節約である、すなわち、QoS経路指定テーブルの必要は全くありません。 これは本質的にはメモリと加工サイクルの間の標準のトレードオフです。
In this section, we briefly describe how a standard Dijkstra algorithm can, for a given destination and bandwidth requirement, generate a minimum hop path that can accommodate the required bandwidth and also has maximum bandwidth. Because the Dijkstra algorithm is already used in the current OSPF route computation, only differences from the standard algorithm are described. Also, while for simplicity we do not consider here zero-hop edges, the modification required for supporting them is straightforward.
このセクションで、私たちは簡潔に標準のダイクストラアルゴリズムがどう与えられた目的地と帯域幅要件のために必要な帯域幅を収容できる最小のホップ経路は発生させることができて、また、最大の帯域幅を持っているかを説明します。 ダイクストラアルゴリズムが現在のOSPF経路計算に既に使用されるので、標準のアルゴリズムからの唯一の違いが説明されます。 また、私たちは簡単さのためにここで無ホップ縁を考えませんが、それらを支持するのに必要である変更も簡単です。
The algorithm essentially performs a minimum hop path computation, on a graph from which all edges, whose available bandwidth is less than that requested by the flow triggering the computation, have been removed. This can be performed either through a pre-processing step, or while running the algorithm by checking the available bandwidth value for any edge that is being considered (see the pseudocode that follows). Another modification to a standard Dijkstra based minimum hop count path computation, is that the list of equal cost next (previous) hops which is maintained as the algorithm proceeds, needs to be sorted according to available bandwidth. This is to allow selection of the minimum hop path with maximum available bandwidth. Alternatively, the algorithm could also be modified to, at each step, only keep among equal hop count paths the one with maximum available bandwidth. This would essentially amount to considering a cost that is function of both hop count and available bandwidth.
アルゴリズムは本質的には最小のホップ経路計算を実行します、すべての優勢(利用可能な帯域幅は計算の引き金となる流れによって要求されたそれ以下である)を取り除いてあるグラフで。 前処理ステップでこれを実行できますか、またはそれはどんな縁がないかどうか利用可能な帯域幅値をチェックすることによってもアルゴリズムを走らせている間、考えられています(従う擬似コードを見てください)。 標準のダイクストラに基づいている最小のホップカウント経路計算への別の変更は次(前の)の等しい費用のリストが跳ぶという(アルゴリズム売り上げ(利用可能な帯域幅に従って分類されるべき必要性)として維持されます)ことです。 これは、最大の利用可能な帯域幅に伴う最小のホップ経路の選択を許すためのものです。 あるいはまた、また、等しいホップカウント経路の中に各ステップに最大の利用可能な帯域幅に伴うものを閉じ込めるだけであるようにアルゴリズムを変更できました。 これは、ホップカウントと利用可能な帯域幅の両方の機能である費用を考えるのに本質的には等しいでしょう。
Note: The pseudocode below assumes a hop-by-hop forwarding approach in updating the neighbor field. Addition of routes to stub networks is done in a second phase as usual. The modifications needed to support explicit route construction are straightforward. The pseudocode also does not handle equal cost multi-paths for simplicity, but the modifications needed to add this support are also easily done.
以下に注意してください。 以下の擬似コードは、隣人分野をアップデートする際にホップごとの推進がアプローチであると仮定します。 通常通りの2番目のフェーズでネットワークを引き抜くルートの添加をします。 明白なルート工事を支持するのに必要である変更は簡単です。 擬似コードも簡単さのためのマルチ経路の等しい費用を扱いませんが、また、容易にこのサポートを加えるのに必要である変更をします。
Apostolopoulos, et al. Experimental [Page 36] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[36ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
Input:
V = set of vertices, labeled by integers 1 to N.
L = set of edges, labeled by ordered pairs (n,m) of vertex labels.
s = source vertex (at which the algorithm is executed).
For all edges (n,m) in L:
* b(n,m) = available bandwidth (according to last received update)
on interface associated with the edge between vertices n and m.
* If(n,m) = outgoing interface corresponding to edge (n,m) when n is
a router.
d = destination vertex.
B = requested bandwidth for the flow served.
以下を入力してください。 Vは整数1によって=が設定した順序対(n、m)の頂点ラベルによってラベルされた縁のN.Lとラベルされた頭頂のセットと等しいです。sはソースの頂点(アルゴリズムはそこで実行される)と等しいです。 Lのすべての縁(n、m)に: * b(n、m)は頭頂nとmの間の縁に関連しているインタフェースにおける利用可能な帯域幅(最近の容認されたアップデートに従って)と等しいです。 * nであるときに、(n、m)=であるなら、斜めに進ませる外向的なインタフェース対応(n、m)はルータです。dは目的地の頂点と等しいです。 B=は、流れのための帯域幅が役立ったよう要求しました。
Type:
tab_entry: record
hops = integer,
neighbor = integer 1..N,
ontree = boolean.
以下をタイプしてください。 _エントリーにタブを付けてください: ホップ=整数、隣人=整数1を記録してください。N、ontreeは論理演算子と等しいです。
Variables:
TT[1..N]: topology table, whose (n) entry is a tab_entry
record, such that:
TT[n].bw is the available bandwidth (as known
thus far) on a shortest-path between
vertices s and n,
TT[n].neighbor is the first hop on that path (a
neighbor of s). It is either a router or the
destination n.
S: list of candidate vertices;
v: vertex under consideration;
変数: TT[1..N]: トポロジーテーブル。その(n)エントリーはタブ_エントリレコード、以下のことのようにものです。 TT[n].bwが頭頂sとnの間の最短パスにおける利用可能な帯域幅(これまでのところ知られているように)である、TT[n].neighborはその経路(sの隣人)の最初のホップです。 それは、ルータか目的地nのどちらかです。 S: 候補頭頂のリスト。 v: 考慮している頂点。
The Algorithm:
アルゴリズム:
begin;
for n:=1 to N do /* initialization */
begin;
TT[n].hops := infinity;
TT[n].neighbor := null;
TT[n].ontree := FALSE;
end;
TT[s].hops := 0;
始まってください。 n: 1〜Nが/*初期化*/をする=に関しては、始まってください。 TT[n].hops:=無限。 TT[n].neighbor:=ヌル。 TT[n].ontree:=偽。 終わってください。 TT[s].hops:=0。
reset S;
v:= s;
while v <> d do
begin;
TT[v].ontree := TRUE;
for all edges (v,m) in L and b(v,m) >= B do
begin;
リセットS。 v: =s。 <>dに対して、始まってください。 TT[v].ontree:=、本当。 Lのすべての縁(v、m)とb(v、m)>=Bに関しては、始まってください。
Apostolopoulos, et al. Experimental [Page 37] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[37ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
if m is a router
begin;
if not TT[m].ontree then
begin;
/* bandwidth must be fulfilled since all links >= B */
if TT[m].hops > TT[v].hops + 1 then
begin
S := S union { m };
TT[m].hops := TT[v].hops + 1;
TT[m].neighbor := v;
end;
end;
end;
else /* must be a network, iterate over all attached routers */
begin; /* each network -- router edge treated as zero hop edge */
for all (m,k) in L, k <> v,
/* i.e., for all other neighboring routers of m */
if not TT[k].ontree and b(m,k) >= B then
begin;
if TT[k].hops > TT[v].hops then
begin;
S := S union { k };
TT[k].hops := TT[v].hops;
TT[k].neighbor := v;
end;
end;
end;
end; /* of all edges from the vertex under consideration */
mがルータであるなら、始まってください。 そうでなければ、次に、TT[m].ontreeは始まります。 S:=S組合mがその時TT[m].hops>TT[v].hops+1に始まるならすべてが>=B*/をリンクするので、/*帯域幅は実現しなければなりません。 TT[m].hops:=TT[v].hops+1。 TT[m].neighbor:=v。 終わってください。 終わってください。 終わってください。 ほかに、/*はネットワークであるに違いなく、すべての付属ルータ*の上で繰り返すか、または始まってください。 それぞれがネットワークでつなぐ/*--ゼロがLをすべて(m、k)のための縁*/を飛び越すので扱われたルータ縁、次に、k<>v、すなわち、m*の/かTT[k].ontreeとb(m、k)>=Bの他のすべての隣接しているルータのための/*は始まります。 TT[k].hops>TT[v].hopsであるなら、始まってください。 S:=S組合、k。 TT[k].hops:=TT[v].hops。 TT[k].neighbor:=v。 終わってください。 終わってください。 終わってください。 終わってください。 考慮*/の下の頂点からのすべての縁の/*
if S is empty then
begin;
v=d; /* which will end the algorithm */
end;
else
begin;
v := first element of S;
S := S - {v}; /* remove and store the candidate to consider */
end;
end; /* from processing of the candidate list */
end.
Sが空であるなら、始まってください。 v=d。 アルゴリズム*/終わりを終わらせる/*。 ほかに、始まってください。 Sのv:=最初の要素。 S:=S--v。 /*は、*/終わりを考えるために候補を免職して、格納します。 終わってください。 候補リスト*/終わりの処理からの/*。
Apostolopoulos, et al. Experimental [Page 38] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[38ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
C. Precomputation Using Dijkstra Algorithm
C。 ダイクストラAlgorithmを使用するPrecomputation
This appendix outlines a Dijkstra-based algorithm that allows pre- computation of QoS routes for all destinations and bandwidth values. The benefit of using a Dijkstra-based algorithm is a greater synergy with existing OSPF implementations. The solution to compute all "best" paths is to consecutively compute shortest path spanning trees starting from a complete graph and removing links with less bandwidth than the threshold used in the previous computation. This yields paths with possibly better bandwidth but of course more hops. Despite the large number of Dijkstra computations involved, several optimizations such as incremental spanning tree computation can be used and allow for efficient implementations in terms of complexity as well as storage since the structure of computed paths leans itself towards path compression [ST83]. Details including measurements and applicability studies can be found in [Prz95] and [BP95].
この付録はすべての目的地と帯域幅値のためにQoSルートのプレ計算を許すダイクストラベースのアルゴリズムを概説します。 ダイクストラベースのアルゴリズムを使用する利益は既存のOSPF実現がある、よりすごい相乗作用です。 すべての「最も良い」経路を計算する解決策は連続して完全なグラフから始めて、前の計算に使用される敷居より少ない帯域幅とのリンクを取り外す最短パススパニングツリーを計算することです。 これはことによるとより良い帯域幅にもかかわらず、もちろんより多くのホップがある経路をもたらします。 計算がかかわった多くのダイクストラにもかかわらず、計算された経路の構造が経路圧縮[ST83]に向かってそれ自体を傾かせて、増加のスパニングツリー計算などのいくつかの最適化が、格納と同様に複雑さに関して使用されて、効率的な実現を考慮できます。 [Prz95]と[BP95]で測定値と適用性研究を含む詳細は見つけることができます。
A variation of this theme is to trade the "accuracy" of the pre- computed paths, (i.e., the paths being generated may be of a larger hop count than needed) for the benefit of using a modified version of Dijkstra shortest path algorithm and also saving on some computations. This loss in accuracy comes from the need to rely on quantized bandwidth values, which are used when computing a minimum hop count path. In other words, the range of possible bandwidth values that can be requested by a new flow is mapped into a fixed number of quantized values, and minimum hop count paths are generated for each quantized value. For example, one could assume that bandwidth values are quantized as low, medium, and high, and minimum hop count paths are computed for each of these three values. A new flow is then assigned to the minimum hop path that can carry the smallest quantized value, i.e., low, medium, or high, larger than or equal to what it requested. We restrict our discussion here to this "quantized" version of the algorithm.
このテーマの変化はダイクストラ最短パスアルゴリズムの変更されたバージョンを使用して、また、いくつかの計算のときに節約する利益のためにあらかじめ計算された経路の「精度」、(すなわち、発生して、必要とされるより大きいホップカウントがあるかもしれないということである経路)を取り引きすることです。 精度におけるこの損失は最小のホップカウント経路を計算するとき使用された量子化された帯域幅値を当てにする必要性から来ます。 言い換えれば、新しい流れから要求できる可能な帯域幅値の範囲は量子化された値の定数に写像されます、そして、最小のホップカウント経路は値であると量子化されたそれぞれのために発生します。 例えば、人は、帯域幅値が低く、中型であるとして量子化されて、高くて、最小のホップカウント経路がそれぞれのこれらの3つの値のために計算されると仮定できました。 すなわち、新しい流れは、次に、値であると量子化される中で最も小さいものを運ぶことができる最小のホップ経路に割り当てられるか、低いか、中型であるか、または高いです、それが要求したより多くのこと。 私たちはここで議論をアルゴリズムのこの「量子化された」バージョンに制限します。
Here too, we discuss the elementary case where all edges count as "hops", and note that the modification required for supporting zero- hop edges is straightforward.
ここで、また、私たちは、すべての縁が「ホップ」にみなす基本のケースについて議論して、無ホップ縁を支持するのに必要である変更が簡単であることに注意します。
As with the BF algorithm, the algorithm relies on a routing table that gets built as the algorithm progresses. The structure of the routing table is as follows:
BFアルゴリズムのように、アルゴリズムはアルゴリズムが進歩をするので建てられる経路指定テーブルを当てにします。 経路指定テーブルの構造は以下の通りです:
The QoS routing table:
QoS経路指定テーブル:
- a K x Q matrix, where K is the number of vertices and Q is the
number of quantized bandwidth values.
- K x Qマトリクス。(そこでは、Kが頭頂の数であり、Qは量子化された帯域幅値の数です)。
Apostolopoulos, et al. Experimental [Page 39] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[39ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
- The (n;q) entry contains information that identifies the minimum
hop count path to destination n, which is capable of accommodating
a bandwidth request of at least bw[q] (the qth quantized bandwidth
value). It consists of two fields:
- (n; q)エントリーは最小のホップカウント経路を目的地nに特定する情報を含んでいます(qthは、帯域幅が値であると量子化しました)。目的地は少なくともbw[q]の帯域幅要求に対応できます。 それは2つの分野から成ります:
* hops: the minimal number of hops on a path between the source
node and destination n, which can accommodate a request of at
least bw[q] units of bandwidth.
* ホップ: ソースノードと目的地nの間の経路のホップの最少数。目的地は少なくともbw[q]ユニットの帯域幅の要求に対応できます。
* neighbor: this is the routing information associated with the
minimum hop count path to destination node n, whose available
bandwidth is at least bw[q]. With a hop-by-hop routing
approach, the neighbor information is simply the identity of
the node adjacent to the source node on that path.
* 隣人: これは利用可能な帯域幅が少なくともbw[q]である目的地ノードnへの最小のホップカウント経路に関連しているルーティング情報です。 ホップごとのルーティングアプローチで、隣人情報は単にその経路のソースノードに隣接したノードのアイデンティティです。
The algorithm operates again on a directed graph where vertices correspond to routers and transit networks. The metric associated with each edge in the graph is as before the bandwidth available on the corresponding interface, where b(n;m) is the available bandwidth on the edge between vertices n and m. The vertex corresponding to the router where the algorithm is being run is selected as the source node for the purpose of path selection, and the algorithm proceeds to compute paths to all other nodes (destinations).
アルゴリズムは再び、頭頂がルータと輸送網に対応する有向グラフを作動させます。 グラフによる各縁に関連しているメートル法は従来と同様対応するインタフェースにおけるb(n; m)が頭頂nとmの間の縁における利用可能な帯域幅である利用可能な帯域幅です。 アルゴリズムが走ることであるところでルータに対応する頂点は経路選択の目的のためのソースノードとして選定されます、そして、アルゴリズムは他のすべてのノード(目的地)に経路を計算しかけます。
Starting with the highest quantization index, Q, the algorithm considers the indices consecutively, in decreasing order. For each index q, the algorithm deletes from the original network topology all links (n;m) for which b(n;m) < bw[q], and then runs on the remaining topology a Dijkstra-based minimum hop count algorithm (10) between the source node and all other nodes (vertices) in the graph. Note that as with the Dijkstra used for on-demand path computation, the elimination of links such that b(n;m) < bw[q] could also be performed while running the algorithm.
最も高い量子化インデックス、Qから始めて、アルゴリズムは連続して、多いほうから少ないほうへ順に並べるとインデックスリストを考えます。 各インデックスqのために、アルゴリズムは、どのb(n; m)<bw[q]のために、オリジナルのネットワーク形態からすべてのリンク(n; m)を削除するか、そして、次に、グラフで残っているトポロジーでソースノードと他のすべてのノードの間のダイクストラベースの最小のホップカウントアルゴリズム(10)(頭頂)を走らせます。 要求次第の経路計算に、中古のダイクストラのようにそれに注意してください、また、アルゴリズムを走らせている間、b(n; m)<bw[q]を実行できるためのリンクの除去。
After the algorithm terminates, the q-th column in the routing table is updated. This amounts to recording in the hops field the hop count value of the path that was generated by the algorithm, and by updating the neighbor field. As before, the update of the neighbor field depends on the scope of the path computation. In the case of a hop-by-hop routing decision, the neighbor field is set to the identity of the node adjacent to the source node (next hop) on the path returned by the algorithm. However, note that in order to ensure that the path with the maximal available bandwidth is always chosen among all minimum hop paths that can accommodate a given quantized bandwidth, a slightly different update mechanism of the neighbor field needs to be used in some instances. Specifically, when for a given row, i.e., destination node n, the value of the hops field in column q is found equal to the value in column q+1 (here we
アルゴリズムが終わった後にq、-、経路指定テーブルのコラムを第アップデートします。 これは、アルゴリズムと、隣人分野をアップデートすることによって発生した経路のホップカウント価値をホップ分野に記録するのに達します。 従来と同様、隣人分野のアップデートは経路計算の範囲によります。 ホップごとのルーティング決定の場合では、隣人分野はアルゴリズムで返された経路のソースノード(次のホップ)に隣接したノードのアイデンティティへのセットです。 しかしながら、隣人分野のわずかに異なったアップデートメカニズムが、最大限度の利用可能な帯域幅に伴う経路が与えられた量子化された帯域幅を収容できるすべての最小のホップ経路の中でいつも選ばれているのを確実にするのにある場合に使用される必要に注意してください。 すなわち、目的地ノードn、ホップの値が与えられた列のためにコラムqで明確に値と+1と等しい、コラムqの分野が見つけられる(ここ、私たち
Apostolopoulos, et al. Experimental [Page 40] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[40ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
assume q<Q), i.e., paths that can accommodate bw[q] and bw[q+ 1] have the same hop count, then the algorithm copies the value of the neighbor field from entry (n;q+1) into that of entry (n;q).
q<Q)、同じホップがすなわち、bw[q]とbw[q+1]を収容できる経路によって数えられて、次に、アルゴリズムがエントリー(n; q+1)をエントリー(n; q)のものに隣人分野の値を回避すると仮定してください。
Note: The pseudocode below assumes a hop-by-hop forwarding approach in updating the neighbor field. The modifications needed to support explicit route construction are straightforward. The pseudocode also does not handle equal cost multi-paths for simplicity, but the modification needed to add this support have been described above. Details of the post-processing step of adding stub networks are omitted.
以下に注意してください。 以下の擬似コードは、隣人分野をアップデートする際にホップごとの推進がアプローチであると仮定します。 明白なルート工事を支持するのに必要である変更は簡単です。 擬似コードも簡単さのためのマルチ経路の等しい費用を扱うのではなく、上で説明されていた状態でこのサポートがそうであると言い足すのに必要である変更を扱います。 加えているスタッブネットワークの後工程ステップの詳細は省略されます。
Input:
V = set of vertices, labeled by integers 1 to N.
L = set of edges, labeled by ordered pairs (n,m) of vertex labels.
s = source vertex (at which the algorithm is executed).
bw[1..Q] = array of bandwidth values to "quantize" flow requests to.
For all edges (n,m) in L:
* b(n,m) = available bandwidth (according to last received update)
on interface associated with the edge between vertices n and m.
* If(n,m) = outgoing interface corresponding to edge (n,m) when n is
a router.
以下を入力してください。 整数1によって=が設定した縁のN.Lとラベルされた頭頂のV=セットは頂点ラベル順序対(n、m)のs=で、ソースの頂点(アルゴリズムはそこで実行される)bw[1..Q]を流れ要求を「量子化する」帯域幅値の=勢ぞろいとラベルしました。 Lのすべての縁(n、m)に: * b(n、m)は頭頂nとmの間の縁に関連しているインタフェースにおける利用可能な帯域幅(最近の容認されたアップデートに従って)と等しいです。 * nがルータであるときに、(n、m)が斜めに進ませる外向的なインタフェース対応(n、m)と等しいなら。
Type:
tab_entry: record
hops = integer,
neighbor = integer 1..N,
ontree = boolean.
以下をタイプしてください。 _エントリーにタブを付けてください: ホップ=整数、隣人=整数1を記録してください。N、ontreeは論理演算子と等しいです。
Variables:
TT[1..N, 1..Q]: topology table, whose (n,q) entry is a tab_entry
record, such that:
TT[n,q].bw is the available bandwidth (as known
thus far) on a shortest-path between
vertices s and n accommodating bandwidth b(q),
TT[n,q].neighbor is the first hop on that path (a
neighbor of s). It is either a router or the
destination n.
S: list of candidate vertices;
v: vertex under consideration;
q: "quantize" step
変数: TT[1..N、1..Q]: トポロジーテーブル。その(n、q)エントリーはタブ_エントリレコード、以下のことのようにものです。 TT[n、q].bwが頭頂sとn親切な帯域幅b(q)の間の最短パスにおける利用可能な帯域幅(これまでのところ知られているように)である、TT[n、q].neighborはその経路(sの隣人)の最初のホップです。 それは、ルータか目的地nのどちらかです。 S: 候補頭頂のリスト。 v: 考慮している頂点。 q: 「量子化する」ステップ
The Algorithm:
アルゴリズム:
begin;
for r:=1 to Q do
begin;
for n:=1 to N do /* initialization */
始まってください。 rのために: Qへの=1は始まります。 nのために: = 1〜Nは/*初期化*/をします。
Apostolopoulos, et al. Experimental [Page 41] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[41ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
begin;
TT[n,r].hops := infinity;
TT[n,r].neighbor := null;
TT[n,r].ontree := FALSE;
end;
TT[s,r].hops := 0;
end;
for r:=1 to Q do
begin;
S = {s};
while S not empty do
begin;
v := first element of S;
S := S - {v}; /* remove and store the candidate to consider */
TT[v,r].ontree := TRUE;
for all edges (v,m) in L and b(v,m) >= bw[r] do
begin;
if m is a router
begin;
if not TT[m,r].ontree then
begin;
/* bandwidth must be fulfilled since all links >= bw[r] */
if TT[m,r].hops > TT[v,r].hops + 1 then
begin
S := S union { m };
TT[m,r].hops := TT[v,r].hops + 1;
TT[m,r].neighbor := v;
end;
end;
end;
else /* must be a network, iterate over all attached
routers */
begin;
for all (m,k) in L, k <> v,
/* i.e., for all other neighboring routers of m */
if not TT[k,r].ontree and b(m,k) >= bw[r] then
begin;
if TT[k,r].hops > TT[v,r].hops + 2 then
begin;
S := S union { k };
TT[k,r].hops := TT[v,r].hops + 2;
TT[k,r].neighbor := v;
end;
end;
end;
end; /* of all edges from the vertex under consideration */
end; /* from processing of the candidate list */
end; /* of "quantize" steps */
始まってください。 TT[n、r].hops:=無限。 TT[n、r].neighbor:=ヌル。 TT[n、r].ontree:=偽。 終わってください。 TT[s、r].hops:=0。 終わってください。 rのために: Qへの=1は始まります。 Sはsと等しいです。 Sが空になっていない間、始まってください。 Sのv:=最初の要素。 S:=S--v。 /*は、*/TT[v、r].ontreeが:=TRUEであると考えるために候補を免職して、格納します。 Lのすべての縁(v、m)とb(v、m)>=bw[r]に関しては、始まってください。 mがルータであるなら、始まってください。 TT[m、r].ontreeでないなら、始まってください。 S:=S組合mがその時TT[m、r].hops>TT[v、r].hops+1に始まるならすべてが>=bw[r]*/をリンクするので、/*帯域幅は実現しなければなりません。 TT[m、r].hops:=TT[v、r].hops+1。 TT[m、r].neighbor:=v。 終わってください。 終わってください。 終わってください。 ほかに、/*はネットワークであるに違いなく、すべての付属ルータ*の上で繰り返すか、または始まってください。 次に、Lのすべて(m、k)に関しては、k<>v、すなわち、m*/かTT[k、r].ontreeとb(m、k)>=bw[r]の他のすべての隣接しているルータのための/*は始まります。 TT[k、r].hops>TT[v、r].hops+2であるなら、始まってください。 S:=S組合、k。 TT[k、r].hops:=TT[v、r].hops+2。 TT[k、r].neighbor:=v。 終わってください。 終わってください。 終わってください。 終わってください。 すべての/*は頂点から考慮*/終わりで斜めに進みます。 候補リスト*/終わりの処理からの/*。 「量子化ステップ*/すること」の/*
Apostolopoulos, et al. Experimental [Page 42] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[42ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
end.
終わってください。
D. Explicit Routing Support
D。 明白なルート設定サポート
As mentioned before, the scope of the path selection process can range from simply returning the next hop on the QoS path selected for the flow, to specifying the complete path that was computed, i.e., an explicit route. Obviously, the information being returned by the path selection algorithm differs in these two cases, and constructing it imposes different requirements on the path computation algorithm and the data structures it relies on. While the presentation of the path computation algorithms focused on the hop-by-hop routing approach, the same algorithms can be applied to generate explicit routes with minor modifications. These modifications and how they facilitate constructing explicit routes are discussed next.
以前言及されるように、経路選択の過程の範囲は単に流れのために選択されたQoS経路の次のホップを返すので、及ぶことができます、計算された完全な経路を指定するのに、すなわち、明白なルート。 明らかに、経路選択アルゴリズムで返される情報はこれらの2つの場合において異なります、そして、それを組み立てると、異なった要件は経路計算アルゴリズムとそれが当てにするデータ構造につけ込みます。 経路計算アルゴリズムのプレゼンテーションがホップごとのルーティングアプローチに焦点を合わせていた間、小さい方の変更で明白なルートを発生させるように同じアルゴリズムを適用できます。 これらの変更とそれらが、明白なルートを構成するのをどう容易にするかについて次に、議論します。
The general approach to facilitate construction of explicit routes is to update the neighbor field differently from the way it is done for hop-by-hop routing as described in Section 2.3. Recall that in the path computation algorithms the neighbor field is updated to reflect the identity of the router adjacent to the source node on the partial path computed. This facilitates returning the next hop at the source for the specific path. In the context of explicit routing, the neighbor information is updated to reflect the identity of the previous router on the path.
明白なルートの構造を容易にする一般的方法は隣人分野をホップごとのルーティングのためにセクション2.3で説明されるようにそれをする方法と異なってアップデートすることです。 部分的な経路のソースノードに隣接してルータのアイデンティティを反映するために隣人がさばく経路計算アルゴリズムでアップデートされるリコールは計算されました。 これは、ソースで次のホップを特定の経路に返すのを容易にします。 明白なルーティングの文脈では、前のルータのアイデンティティを経路に反映するために隣人情報をアップデートします。
In general, there can be multiple equivalent paths for a given hop count. Thus, the neighbor information is stored as a list rather than single value. Associated with each neighbor, additional information is stored to facilitate load balancing among these multiple paths at the time of path selection. Specifically, we store the advertised available bandwidth on the link from the neighbor to the destination in the entry.
一般に、与えられたホップカウントのための複数の同等な経路があることができます。 したがって、隣人情報はただ一つの値よりむしろリストとして格納されます。 各隣人に関連していて、追加情報は、経路選択時点でこれらの複数の経路の中でロードバランシングを容易にするために格納されます。 明確に、私たちはエントリーに広告を出している利用可能な帯域幅を隣人から目的地へのリンクに格納します。
With this change, the basic approach used to extract the complete list of vertices on a path from the neighbor information in the QoS routing table is to proceed `recursively' from the destination to the origin vertex. The path is extracted by stepping through the precomputed QoS routing table from vertex to vertex, and identifying at each step the corresponding neighbor (precursor) information. The process is described as recursive since the neighbor node identified in one step becomes the destination node for table look up in the next step. Once the source router is reached, the concatenation of all the neighbor fields that have been extracted forms the desired explicit route. This applies to algorithms of Section 2.3.1 and Appendix C. If at a particular stage there are multiple neighbor choices (due to equal cost multi-paths), one of them can be chosen at random with a probability that is weighted, for example, by the
この変化で、経路でQoS経路指定テーブルの隣人情報から頭頂に関する全リストを抜粋するのにおいて中古の基本的なアプローチは'再帰的に'目的地から起源頂点まで続くことになっています。 経路は、precomputed QoS経路指定テーブルを通して頂点から頂点まで踏んで、各ステップで対応する隣人(先駆)情報を特定することによって、抽出されます。 ワンステップで特定された隣人ノードが次のステップで上がっているテーブル表情のための目的地ノードになるので、過程は再帰的であると記述されています。 ソースルータにいったん達していると、抽出されたすべての隣人野原の連結は必要な明白なルートを形成します。 これは複数の隣人選択(等しい費用マルチ経路による)をある特定の段階のセクション2.3.1とAppendix C.Ifのアルゴリズムに適用して、確率で例えばそれが荷重している無作為にそれらの1つは選ぶことができます。
Apostolopoulos, et al. Experimental [Page 43] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[43ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
associated bandwidth on the link from the neighbor to the (current) destination.
隣人から(現在)の目的地へのリンクにおける関連帯域幅。
Specifically, assume a new request to destination, say, d, and with bandwidth requirements B. The index of the destination vertex identifies the row in the QoS routing table that needs to be checked to generate a path. The row is then searched to identify a suitable path. If the Bellman-Ford algorithm of Section 2.3.1 was used, the search proceeds by increasing index (hop) count until an entry is found, say at hop count or column index of h, with a value of the bw field that is equal to or greater than B. This entry points to the initial information identifying the selected path. If the Dijkstra algorithm of Appendix C is used, the first quantized value qB such that qB >= B is first identified, and the associated column then determines the first entry in the QoS routing table that identifies the selected path.
明確に、たとえば、目的地、dに新しい要求を仮定してください。そうすれば、帯域幅要件B.で、目的地の頂点のインデックスは経路を発生させるようにチェックされる必要があるQoS経路指定テーブルの列を特定します。 そして、列は、適当な経路を特定するために捜されます。 セクション2.3.1のBellman-フォードアルゴリズムが使用されたなら、増加するインデックス(ホップ)による売り上げが数えるエントリーがそうになるまでの検索が見つけられて、bw分野の値があるhのホップカウントか列番号ですなわち、B.Thisより等しいか大きいエントリーが選択された経路を特定する初期の情報を示すと言ってください。 Appendix Cのダイクストラアルゴリズムが使用されているなら、1番目が、値がqBであると量子化したので、qB>=Bは最初に特定されます、そして、次に、関連コラムは選択された経路を特定するQoS経路指定テーブルで初記入を決定します。
Once this first entry has been identified, reconstruction of the complete list of vertices on the path proceeds similarly, whether the table was built using the algorithm of Section 2.3.1 or Appendix C. Specifically, in both cases, the neighbor field in each entry points to the previous node on the path from the source node and with the same bandwidth capabilities as those associated with the current entry. The complete path is, therefore, reconstructed by following the pointers provided by the neighbor field of successive entries.
この初記入がいったん特定されると、経路における頭頂に関する全リストの再構成は同様に続きます、テーブルがセクション2.3.1かAppendix C.Specificallyのアルゴリズムを使用することで組立てられたか否かに関係なく、どちらの場合も、各エントリーにおける隣人分野が経路の現在のエントリーに関連づけられたものとしてのソースノードと同じ帯域幅能力がある前のノードを示します。 したがって、完全な経路は、連続したエントリーの隣人分野によって提供されたポインタに続くことによって、再建されます。
In the case of the Bellman-Ford algorithm of Section 2.3.1, this means moving backwards in the table from column to column, using at each step the row index pointed to by the neighbor field of the entry in the previous column. Each time, the corresponding vertex index specified in the neighbor field is pre-pended to the list of vertices constructed so far. Since we start at column h, the process ends when the first column is reached, i.e., after h steps, at which point the list of vertices making up the path has been reconstructed.
セクション2.3.1のBellman-フォードアルゴリズムの場合では、これは、コラムからコラムまでテーブルに後方に入って来ることを意味します、前のコラムで各ステップでエントリーの隣人分野によって示された列のインデックスを使用して。 その都度、隣人分野で指定された対応する頂点インデックスは今までのところ組み立てられている頭頂のリストにあらかじめpendedされます。 私たちがコラムhで始めるので、hがどのポイントで仲直りする頭頂のリストを踏んだかの後にすなわち最初のコラムに達している過程終わりに、経路を再建してあります。
In the case of the Dijkstra algorithm of Appendix C, the backtracking process is similar although slightly different because of the different relation between paths and columns in the routing table, i.e., a column now corresponds to a quantized bandwidth value instead of a hop count. The backtracking now proceeds along the column corresponding to the quantized bandwidth value needed to satisfy the bandwidth requirements of the flow. At each step, the vertex index specified in the neighbor field is pre-pended to the list of vertices constructed so far, and is used to identify the next row index to move to. The process ends when an entry is reached whose neighbor field specifies the origin vertex of the flow. Note that since there are as many rows in the table as there are vertices in the graph, i.e., N, it could take up to N steps before the process terminates.
経路指定テーブルの経路とコラムとの異なった関係でわずかに異なりますが、Appendix Cのダイクストラアルゴリズムの場合において、後戻りの過程が同様である、すなわち、コラムは現在、ホップカウントの代わりに量子化された帯域幅値に対応します。 後戻りは現在、値が満足する必要があった量子化された帯域幅に対応するコラムに沿って流れに関する帯域幅要件を続かせます。 各ステップでは、隣人分野で指定された頂点インデックスは、今までのところ組み立てられている頭頂のリストにあらかじめpendedされて、動く次の列のインデックスを特定するのに使用されます。 隣人分野が流れの起源頂点を指定するエントリーに達しているとき、過程は終わります。 すなわち、テーブルのグラフには頭頂があるのと同じくらい多くの列、Nがあるので、過程が終わる前に、それがNステップまで取ることができたことに注意してください。
Apostolopoulos, et al. Experimental [Page 44] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[44ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
Note that the identification of the first entry in the routing table is identical to what was described for the hop-by-hop routing case. However, as described in this section, the update of the neighbor fields while constructing the QoS routing tables, is being performed differently in the explicit and hop-by-hop routing cases. Clearly, two different neighbor fields can be kept in each entry and updates to both could certainly be performed jointly, if support for both xplicit routing and hop-by-hop routing is needed.
経路指定テーブルでの初記入の識別がホップごとのルーティングケースのために説明されたことと同じであることに注意してください。 しかしながら、QoS経路指定テーブルを組み立てている間のこのセクションで説明されるような隣人分野のアップデートは明白、そして、ホップごとのルーティング場合で異なって実行されています。 明確に、各エントリーに2つの異なった隣人分野を保つことができました、そして、確かに、共同で両方へのアップデートを実行できました、xplicitルーティングとホップごとのルーティングの両方のサポートが必要であるなら。
Endnotes
エンドノート
1. In this document we commit the abuse of notation of calling a
"network" the interconnection of routers and networks through
which we attempt to compute a QoS path.
1. 本書では私たちは「ネットワーク」を私たちがQoS経路を計算するのを試みるルータとネットワークのインタコネクトと呼ぶ記法の乱用を遂行します。
2. This is true for uni-cast flows, but in the case of multi-cast
flows, hop-by-hop and an explicit routing clearly have different
implications.
2. ユニキャスト流れに、これは本当ですが、マルチキャスト流れの場合では、ホップごとの明白なルーティングは明確に異なった意味を持っています。
3. Some hysteresis mechanism should be added to suppress updates when
the metric value oscillates around a class boundary.
3. メートル法の数値がクラス境界の周りで揺れるとき、何らかのヒステリシスメカニズムが、アップデートを抑圧するために加えられるべきです。
4. In this document, we use the terms node and vertex
interchangeably.
4. 本書では、私たちは用語ノードと頂点を互換性を持って使用します。
5. Various hybrid methods can also be envisioned, e.g., periodic
computations except if more than a given number of updates are
received within a shorter interval, or periodic updates except if
the change in metrics corresponding to a given update exceeds a
certain threshold. Such variations are, however, not considered
in this document.
5. 様々なハイブリッド法は超えることができます、また、より短い間隔以内に与えられた数のアップデート以上を受け取るか、そして、測定基準における変化であること以外の周期的なアップデート以外の思い描かれて、例えば、周期的な計算が対応していたなら、与えられたアップデートはある敷居を超えています。 しかしながら、そのような変化は本書では考えられません。
6. Modifications to support explicit routing are discussed in
Appendix D.
6. Appendix Dで明白なルーティングを支持する変更について議論します。
7. Note, that this does not say anything on whether to differentiate
between outgoing and incoming bandwidth on a shared media network.
As a matter of fact, a reasonable option is to set the incoming
bandwidth (from network to router) to infinity, and only use the
outgoing bandwidth value to characterize bandwidth availability on
the shared network.
7. これが共有されたマスメディア網における送受信の帯域幅を区別するかどうかに関して何も言わないというメモ。 実は、正当な選択は、入って来る帯域幅(ネットワークからルータまでの)を無限で設定して、共用回線網に関する帯域幅の有用性を特徴付けるのに外向的な帯域幅値を使用するだけであることです。
8. exponent in parenthesis
8. 挿入句の解説者
9. Access to some of the more recent versions of the GateD software
is restricted to the GateD consortium members.
9. GateDソフトウェアの、より最近のバージョンのいくつかへのアクセスはGateD共同体のメンバーに制限されます。
Apostolopoulos, et al. Experimental [Page 45] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[45ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
10. Note that a Breadth-First-Search (BFS) algorithm [CLR90] could
also be used. It has a lower complexity, but would not allow
reuse of existing code in an OSPF implementation.
10. また、Breadth最初の検索(BFS)アルゴリズム[CLR90]を使用できたことに注意してください。 それは、下側の複雑さを持っていますが、OSPF実現における、既存のコードの再利用を許さないでしょう。
References
参照
[AGK99] G. Apostolopoulos, R. Guerin, and S. Kamat. Implementation
and performance meassurements of QoS routing extensions to
OSPF. In Proceedings of INFOCOM'99, pages 680--688, New
York, NY, March 1999.
[AGK99] G.Apostolopoulos、R.ゲラン、およびS.Kamat。 OSPFへのQoSルーティング拡張子の実現と性能meassurements。 INFOCOM'99、680--688ページのProceedings、ニューヨークニューヨーク、1999'年3月に。
[AGKT98] G. Apostolopoulos, R. Guerin, S. Kamat, and S. K. Tripathi.
QoS routing: A performance perspective. In Proceedings of
ACM SIGCOMM'98, pages 17--28, Vancouver, Canada, October
[AGKT98] G.Apostolopoulos、R.ゲラン、S.Kamat、およびS.K.Tripathi。 QoSルーティング: 性能見解。 ACM SIGCOMM98年、17--28ページ、バンクーバー(カナダ)10月のProceedingsで
[Alm92] Almquist, P., "Type of Service in the Internet Protocol
Suite", RFC 1349, July 1992.
[Alm92] Almquist、P.、「インターネットプロトコル群のサービスのタイプ」、RFC1349、1992年7月。
[AT98] G. Apostolopoulos and S. K. Tripathi. On reducing the
processing cost of on-demand QoS path computation. In
Proceedings of ICNP'98, pages 80--89, Austin, TX, October
1998.
[AT98]G.ApostolopoulosとS.K.Tripathi。 要求次第のQoS経路計算の加工費を下げることに関して。 ICNP98年、80--89ページのProceedings、オースチンテキサス、1998年10月に。
[BP95] J.-Y. Le Boudec and T. Przygienda. A Route Pre-Computation
Algorithm for Integrated Services Networks. Journal of
Network and Systems Management, 3(4), 1995.
[BP95]J.-Y。 Le BoudecとT.Przygienda。 統合サービスネットワークのためのルートプレ計算アルゴリズム。 ネットワークとシステム管理、3(4)のジャーナル、1995。
[Car79] B. Carre. Graphs and Networks. Oxford University Press,
ISBN 0-19-859622-7, Oxford, UK, 1979.
[Car79]B.カレ。 グラフとネットワーク。 オックスフォード大学出版局、ISBN0-19-859622-7、オックスフォードイギリス、1979。
[CLR90] T. H. Cormen, C. E. Leiserson, and R. L. Rivest.
Introduction to Algorithms. MIT Press, Cambridge, MA, 1990.
[CLR90]T.H.Cormen、C.E.Leiserson、およびR.L.Rivest。 アルゴリズムMITプレス、ケンブリッジ(MA)1990への序論。
[Con] Merit GateD Consortium. The Gate Daemon (GateD) project.
[だまします] 外出を禁止された共同体に値してください。 Gate Daemon(GateD)は突出しています。
[GJ79] M.R. Garey and D.S. Johnson. Computers and Intractability.
Freeman, San Francisco, 1979.
[GJ79]M.R.GareyとD.S.ジョンソン。 コンピュータと強情さ。 フリーマン、サンフランシスコ、1979。
[GKH97] R. Guerin, S. Kamat, and S. Herzog. QoS Path Management
with RSVP. In Proceedings of the 2nd IEEE Global Internet
Mini-Conference, pages 1914-1918, Phoenix, AZ, November
[GKH97] R.ゲラン、S.Kamat、およびS.ハーツォグ。 RSVPとのQoS経路管理。 第2IEEE GlobalインターネットMini-コンファレンス、1914-1918ページ、フェニックス(アリゾナ)11月のProceedingsで
[GKR97] Guerin, R., Kamat, S. and E. Rosen, "An Extended RSVP
Routing Interface, Work in Progress.
[GKR97] ゲラン、R.、Kamat、S.、およびE.ローゼン、「拡張RSVPがインタフェースを発送して、進行中で働いてください。」
[GLG+97] Der-Hwa G., Li, T., Guerin, R., Rosen, E. and S. Kamat,
"Setting Up Reservations on Explicit Paths using RSVP", Work
in Progress.
[GLG+97] 「RSVPを使用することで明白な経路に予約をセットアップし」て、Der-Hwa G.、李、T.、ゲラン、R.、ローゼン、E.、およびS.Kamatは進行中で働いています。
Apostolopoulos, et al. Experimental [Page 46] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[46ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
[GO99] R. Guerin and A. Orda. QoS-Based Routing in Networks with
Inaccurate Information: Theory and Algorithms. IEEE/ACM
Transactions on Networking, 7(3):350--364, June 1999.
[GO99] R.ゲランとA.オルダ。 不正確な情報があるネットワークにおけるQoSベースのルート設定: 理論とアルゴリズムネットワークのIEEE/ACM取引、7(3): 350--364と、1999年6月。
[GOW97] R. Guerin, A. Orda, and D. Williams. QoS Routing Mechanisms
and OSPF Extensions. In Proceedings of the 2nd IEEE Global
Internet Mini-Conference, pages 1903-1908, Phoenix, AZ,
November 1997.
[GOW97]R.ゲラン、A.オルダ、およびD.ウィリアムズQoSルート設定メカニズムとOSPF拡張子。 第2IEEE GlobalインターネットMini-コンファレンスのProceedings、1903-1908ページ、フェニックス(アリゾナ)1997年11月に。
[KNB98] Nichols, K., Blake, S., Baker F. and D. Black, "Definition
of the Differentiated Services Field (DS Field) in the IPv4
and IPv6 Headers", RFC 2474, December 1998.
[KNB98]ニコルズとK.とブレークとS.、ベイカーF.とD.黒、「IPv4とIPv6ヘッダーとの微分されたサービス分野(DS分野)の定義」RFC2474(1998年12月)。
[LO98] D. H. Lorenz and A. Orda. QoS Routing in Networks with
Uncertain Parameters. IEEE/ACM Transactions on Networking,
6(6):768--778, December 1998.
[LO98] D.H.ローレンツとA.オルダ。 不確実なパラメタがあるネットワークにおけるQoSルート設定。 ネットワークのIEEE/ACM取引、6(6): 768--778と、1998年12月。
[Moy94] Moy, J., "OSPF Version 2", RFC 1583, March 1994.
[Moy94]Moy、J.、「OSPF、バージョン2インチ、RFC1583、1994インチ年3月。
[Moy98] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[Moy98]Moy、J.、「OSPF、バージョン2インチ、STD54、RFC2328、1998インチ年4月。
[Prz95] A. Przygienda. Link State Routing with QoS in ATM LANs.
Ph.D. Thesis Nr. 11051, Swiss Federal Institute of
Technology, April 1995.
[Prz95]A.Przygienda。 気圧LANで州のルート設定をQoSにリンクしてください。 博士号論文Nr。 11051 1995年4月のスイス連邦工科大学。
[RMK+98] R. Rajan, J. C. Martin, S. Kamat, M. See, R. Chaudhury, D.
Verma, G. Powers, and R. Yavatkar. Schema for
differentiated services and integrated services in networks.
INTERNET-DRAFT, October 1998. work in progress.
R.Chaudhury、D.Verma、[RMK+98]R.Rajan、J.C.マーチン、S.Kamat、M.が見られる、G.強国、およびR.Yavatkar。 ネットワークにおける微分されたサービスと統合サービスのための図式。 インターネット-DRAFT、10月1998日は進行中で働いています。
[RZB+97] Braden, R., Editor, Zhang, L., Berson, S., Herzog, S. and S.
Jamin, "Resource reSerVation Protocol (RSVP) Version 1,
Functional Specification", RFC 2205, September 1997.
[RZB+97]のブレーデン、R.、エディタ、チャン、L.、Berson、S.、ハーツォグ、S.、およびS.ジャマン、「資源予約は(RSVP)バージョン1について議定書の中で述べます、機能的な仕様」、RFC2205、1997年9月。
[SPG97] Shenker, S., Partridge, C. and R. Guerin, "Specification of
Guaranteed Quality of Service", RFC 2212, November 1997.
[SPG97] ShenkerとS.とヤマウズラとC.とR.ゲラン、「保証されたサービスの質の仕様」、RFC2212、1997年11月。
[ST83] D.D. Sleator and R.E. Tarjan. A Data Structure for Dynamic
Trees. Journal of Computer Systems, 26, 1983.
[ST83]D.D.SleatorとR.E.タルジャンダイナミックな木のためのデータ構造。 26、1983コンピュータ・システム、年のジャーナル
[Tan89] A. Tannenbaum. Computer Networks. Addisson Wesley, 1989.
[Tan89]A.タネンバウム。 コンピュータネットワーク。 Addissonウエスリー、1989。
[YPG97] Yavatkar, R., Pendarakis, D. and R. Guerin, "A Framework for
Policy-based Admission Control", INTERNET-DRAFT, April 1999.
Work in Progress.
[YPG97] YavatkarとR.とPendarakisとD.とR.ゲラン、「方針ベースの入場コントロールのための枠組み」、インターネット草稿、1999年4月。 進行中で、働いてください。
Apostolopoulos, et al. Experimental [Page 47] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[47ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
Authors' Addresses
作者のアドレス
George Apostolopoulos IBM T.J. Watson Research Center P.O. Box 704 Yorktown Heights, NY 10598
ニューヨーク ジョージApostolopoulos IBM T.J.ワトソン研究所私書箱704ヨークタウンの高さ、10598
Phone: +1 914 784-6204 Fax: +1 914 784-6205 EMail: georgeap@watson.ibm.com
以下に電話をしてください。 +1 914 784-6204Fax: +1 914 784-6205 メールしてください: georgeap@watson.ibm.com
Roch Guerin University Of Pennsylvania Department of Electrical Engineering, Rm 367 GRW 200 South 33rd Street Philadelphia, PA 19104--6390
電気工学のRochゲランペンシルバニア大学部、第33南通りフィラデルフィア、Rm367GRW200PA19104--6390
Phone: +1 215-898-9351 EMail: guerin@ee.upenn.edu
以下に電話をしてください。 +1 215-898-9351 メールしてください: guerin@ee.upenn.edu
Sanjay Kamat Bell Laboratories Lucent Technologies Room 4C-510 101 Crawfords Corner Road Holmdel, NJ 07733
Sanjay Kamatベル研究所ルーセントテクノロジーズ余地の4C510 101Crawfordsコーナー道路Holmdel、ニュージャージー 07733
Phone: (732) 949-5936 email: sanjayk@dnrc.bell-labs.com
以下に電話をしてください。 (732) 949-5936 メールしてください: sanjayk@dnrc.bell-labs.com
Ariel Orda Dept. Electrical Engineering Technion - I.I.T Haifa, 32000 - ISRAEL
アリエルオルダ部 電気工学Technion--I.I.Tハイファ、32000--イスラエル
Phone: +011 972-4-8294646 Fax: +011 972-4-8323041 EMail: ariel@ee.technion.ac.il
以下に電話をしてください。 +011 972-4-8294646Fax: +011 972-4-8323041 メールしてください: ariel@ee.technion.ac.il
Apostolopoulos, et al. Experimental [Page 48] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[48ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
Tony Przygienda Siara Systems 300 Ferguson Drive Moutain View California 94043
トニーPrzygienda Siara Systems300ファーガソンドライブMoutain Viewカリフォルニア 94043
Phone: +1 732 949-5936 Email: prz@siara.com
以下に電話をしてください。 +1 732 949-5936 メールしてください: prz@siara.com
Doug Williams IBM T.J. Watson Research Center P.O. Box 704 Yorktown Heights, NY 10598
ニューヨーク ダグウィリアムズIBM T.J.ワトソン研究所私書箱704ヨークタウンの高さ、10598
Phone: +1 914 784-5047 Fax: +1 914 784-6318 EMail: dougw@watson.ibm.com
以下に電話をしてください。 +1 914 784-5047Fax: +1 914 784-6318 メールしてください: dougw@watson.ibm.com
Apostolopoulos, et al. Experimental [Page 49] RFC 2676 QoS Routing Mechanisms and OSPF Extensions August 1999
Apostolopoulos、他 実験的な[49ページ]RFC2676QoSルート設定メカニズムとOSPF拡大1999年8月
Full Copyright Statement
完全な著作権宣言文
Copyright (C) The Internet Society (1999). All Rights Reserved.
Copyright(C)インターネット協会(1999)。 All rights reserved。
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
それに関するこのドキュメントと翻訳は、コピーして、それが批評するか、またはそうでなければわかる他のもの、および派生している作品に提供するか、または準備されているかもしれなくて、コピーされて、発行されて、全体か一部広げられた実現を助けるかもしれません、どんな種類の制限なしでも、上の版権情報とこのパラグラフがそのようなすべてのコピーと派生している作品の上に含まれていれば。 しかしながら、このドキュメント自体は何らかの方法で変更されないかもしれません、インターネット協会か他のインターネット組織の版権情報か参照を取り除くのなどように、それを英語以外の言語に翻訳するのが著作権のための手順がインターネットStandardsの過程で定義したどのケースに従わなければならないか、必要に応じてさもなければ、インターネット標準を開発する目的に必要であるのを除いて。
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
上に承諾された限られた許容は、永久であり、インターネット協会、後継者または案配によって取り消されないでしょう。
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
このドキュメントとそして、「そのままで」という基礎とインターネットの振興発展を目的とする組織に、インターネット・エンジニアリング・タスク・フォースが速達の、または、暗示しているすべての保証を放棄するかどうかというここにことであり、他を含んでいて、含まれて、情報の使用がここに侵害しないどんな保証も少しもまっすぐになるという情報か市場性か特定目的への適合性のどんな黙示的な保証。
Acknowledgement
承認
Funding for the RFC Editor function is currently provided by the Internet Society.
RFC Editor機能のための基金は現在、インターネット協会によって提供されます。
Apostolopoulos, et al. Experimental [Page 50]
Apostolopoulos、他 実験的[50ページ]
一覧
スポンサーリンク
