[要約] RFC 2676は、QoSルーティングメカニズムとOSPF拡張に関する情報を提供するものであり、主な目的はネットワーク内のトラフィックの品質を向上させるためのルーティング手法と拡張機能を提案することです。
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
QoS Routing Mechanisms and OSPF Extensions
QoSルーティングメカニズムとOSPF拡張
Status of this 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.
このメモは、インターネットコミュニティの実験プロトコルを定義します。いかなる種類のインターネット標準を指定しません。改善のための議論と提案が要求されます。このメモの配布は無制限です。
Copyright Notice
著作権表示
Copyright (C) The Internet Society (1999). All Rights Reserved.
Copyright（c）The Internet Society（1999）。無断転載を禁じます。
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ルートを計算するために使用されるアルゴリズムと、この機能をサポートするために必要なOSPFに必要な変更にあります。プロセス。QoSルートの確立と管理方法に関連する側面についても簡単に説明します。このドキュメントの目標は、既存のルーティングインフラストラクチャに最小限の影響を与える可能性のあるQoSルーティング機能の展開を可能にするためのフレームワークと可能なアプローチを特定することです。
In addition, experience from an implementation of the proposed extensions in the GateD environment [Con], along with performance measurements is presented.
さらに、ゲート環境[CON]で提案された拡張機能の実装とパフォーマンス測定とともに経験が示されています。
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
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:
このドキュメントでは、OSPFルーティングプロトコルへの提案された追加の追加について説明します（これらの追加は、foldent-of-service（qos）ルーティングをサポートするために、Gated [con]実装の上に実装されています）。IPネットワーク。QoSルーティングのサポートは、3つの主要なコンポーネントで構成されると見ることができます。
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をサポートするために必要なメトリック、QoSメトリックの更新を伝播するOSPFリンク状態広告メカニズムの拡張、およびQoSリクエストに対応するためのパス選択の変更について説明します。このドキュメントで説明されている拡張機能の目標は、既存のOSPFプロトコルとその現在の実装への影響を最小限に抑えて、QoSフローのパフォーマンスを改善することです（要求されたQoSを提供できるパスでルーティングする可能性があります）。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プロトコルの提案された拡張機能を説明することに加えて、このドキュメントは、ゲートプラットフォームで行われた実装のパフォーマンス測定に基づいて実験データを報告します（セクション4を参照）。
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 of unicast flows, although many of the additions we define are applicable to multicast flows as well.
QoS保証を使用して、ベストエフォルトパケットとパケットの両方をサポートするネットワーク（1）を検討します。ネットワーク内の各QOS対応ルーターがQoSパケットの要件を満たすためにリソースの一部を専用できるという仮定を除いて、ネットワークリソースが2つのクラス間で分割される方法は無関係です。QoS対応ルーターは、新しいQoSフローが利用できるままであるリソースを識別して広告することができると想定されています。さらに、関係するすべてのルーターがこのドキュメントで説明されているQOS拡張機能をサポートする場合に制限します。つまり、一部のルーターがQoS対応であり、他のルーターがそうではない不均一な環境でルートを確立する問題を考慮しません。。さらに、このドキュメントでは、ユニキャストフローのケースに焦点を当てていますが、定義する追加の多くはマルチキャストフローにも適用できます。
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]パスメッセージの到着に対応する可能性があります。そのような要求を処理した後、ルーティングプロトコルは、フローの要件を考えると、最も適切なと思われるパスを返します。パス選択プロセスの範囲に応じて、この返されたパスは、最高の次のホップ、つまりホップバイホップパス選択モデルの識別から、すべての中間ノードを宛先に指定すること、つまり明示的なルートモデルまでの範囲にあります。。返されるパスの性質は、適切なパス情報を構築および返却するためのさまざまな要件に変換されるため、パス選択アルゴリズムの動作に影響を与えます。ただし、パス選択アルゴリズムの基本操作には影響しません（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 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保証の配信が成功するには、関連する「QoSフロー」のパケットを選択したパスに転送する必要があることに注意する必要があります。これには通常、ルーターに対応する転送状態を設置する必要があります。たとえば、RSVP [RZB 97]の流れでは、RESVメッセージに含まれるフィルター仕様に基づいて分類器エントリが作成されます。差別化されたサービス[KNB98]設定の場合、分類器エントリは、宛先アドレス（またはプレフィックス）とDSバイトの対応する値に基づいている場合があります。このドキュメントで説明されているメカニズムは制御パスレベルにあるため、使用されるパケット分類方法などのデータパスメカニズムとは無関係です。それにもかかわらず、QoS保証の一貫した配信がデータパスの安定性を意味することに注意することが重要です。特に、パスが最初に選択された後、ネットワークの条件が変化し、「より良い」パスの出現につながる可能性がありますが、そのような変更は既存のパスに不必要に影響を与えることを防ぐ必要があります。特に、新しい（そしてより良い）パスに切り替えることは、例えば、最初の選択が不十分または非常に「高価」であることが判明した場合、特定の条件に制限する必要があります。この側面は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]で説明されています。RSVPとの明示的な経路に沿ってリソースを予約するコンテキストでのこのようなインターフェイスの使用については、[GLG 97]で説明しています。パス管理の詳細と、ホップバイホップパスのセットアップの場合のループを回避する手段は[GKH97]に記載されており、このドキュメントではこれ以上対処されていません。
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をサポートするために最初に検討する拡張の範囲に特定の制限を課します。最初の制限は、メトリックの更新を配布する目的で状態広告（LSA）をリンクするために追加される追加（QOS）メトリックのタイプです。具体的には、最初に検討するLSAへの拡張には、利用可能な帯域幅と遅延のみが含まれています。さらに、パスの選択自体は、帯域幅要件のみを考慮することに限定されます。特に、パス選択アルゴリズムは、フローの帯域幅要件を満たすことができるパスを選択しますが、同時に、割り当てられる必要があるネットワークリソースの量を最小限に抑えようとします。つまり、使用するホップ数を最小化します。
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 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要件の完全な範囲を完全にはキャプチャしません。たとえば、そのリンクが直接パスを提供し、未使用の帯域幅がたくさんある場合、インタラクティブアプリケーションの遅延敏感なフローを衛星リンクを使用してパスに配置できます。これは明らかに望ましくない選択です。このような貧弱な選択を防ぐための私たちのアプローチは、パス選択アルゴリズムを呼び出す前に、高い伝播遅延、例えば衛星リンクなどのすべてのリンクをネットワークから排除する「ポリシー」に遅延依存フローを割り当てることです。一般に、複数のポリシーを使用して異なる要件をキャプチャすることができます。各ポリシーは、それぞれがパス選択アルゴリズムAに対応する剪定ネットワークトポロジを提示し、適切なパスを生成するために同じアルゴリズムを使用します。あるいは、着信要求で表されるQoS要件に応じて、異なるアルゴリズムを使用できます。このような拡張は、このドキュメントの範囲を超えており、単一のメトリック、帯域幅のケースを説明することに制限されています。ただし、このドキュメントで提案されているパス選択アルゴリズムの単純な拡張機能により、保証されたサービス提案[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ルーティングのサポートを導入することが最小限の影響を与えることを保証するためのもう1つの重要な側面は、可能な限り最小のコンピューティングオーバーヘッドを持つソリューションを開発することです。追加の計算は避けられませんが、QoSルーティングの計算コストを従来のルーティングアルゴリズムのレベルに匹敵するレベルに維持することが望ましいです。この目標を達成するための1つの可能なアプローチは、QoSルートの事前計算を許可することです。これは、QOS拡張機能をOSPFに実装するために選択された方法であり、したがって、このドキュメントで詳細に説明されている方法です。代替アプローチは、付録で簡単にレビューされています。ただし、いくつかの代替パス選択アルゴリズムが可能ですが、特定のルーティングドメイン内で同じアルゴリズムを一貫して使用する必要があることに注意してください。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 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.
QoSルーティングの導入に関する懸念の最後の側面は、リンクメトリックのより頻繁な変更によって引き起こされる追加のリンク状態の更新に関連するオーバーヘッドを制御することです。目標は、パス選択のパフォーマンスに悪影響を与えることなく、追加の更新トラフィックの量を最小限に抑えることです。セクション2.2では、プロトコルオーバーヘッドのリンク状態情報の精度を取引するさまざまな代替案の簡単な議論を紹介します。リンクメトリックの不正確さを（直接）説明しようとするパス選択アルゴリズムの潜在的な強化は[GOW97]で説明されていますが、被験者の包括的な治療は[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ではゲートプラットフォームでの実装について説明し、いくつかの実験結果も示します。セクション5では、提案されたスキームが提起する可能性のあるセキュリティの問題について簡単に説明します。最後に、いくつかの付録は、特徴的なルートの代替パス選択アルゴリズムとサポートなど、関心のある追加資料を提供しますが、このドキュメントの主な焦点の外側にあります。
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パス選択の基本的な構成要素、つまり、ルーティングアルゴリズムが動作するメトリック、これらのメトリックの更新を伝播するために使用されるメカニズム、および最後にパス選択アルゴリズム自体を確認します。
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., 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.
- リンク利用可能な帯域幅：前述のように、現在、ほとんどのQoS要件は「帯域幅」と呼ばれるレート関連の数量から派生可能であると想定しています。さらに、各リンクに関連付けられていることは、最大帯域幅の値であると仮定します。たとえば、リンクの物理帯域幅またはQoSフローのために確保されている一部の画分です。特定の帯域幅要件を備えた新しいフローを受け入れることができるリンクは、少なくともリンクでまだ多くの帯域幅を利用できる必要があるため、関連するリンクメトリックは、利用可能な（つまり、現在の）量の量です（つまり、unallocated）帯域幅。このメトリックの変更は、拡張されたLSAの一部として宣伝する必要があります。そのため、PATH選択アルゴリズムが正確な情報を使用できます。
- 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].
- リンク伝播遅延：この数量は、リアルタイムのリクエストには不適切な場合、高レイテンシリンク、たとえば衛星リンクを識別することを目的としています。また、この数量は拡張LSAの一部として宣伝する必要がありますが、この情報のタイムリーな普及は、このパラメーターが時間とともに（大幅に）変化する可能性は低いため、重要ではありません。前述のように、遅延に敏感な要求のパスを選択するときに、リンク伝播遅延を使用して、特定のリンクの剪定を決定できます。また、[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.
- ホップカウント：この数量は、ネットワークへのパスコストの尺度として使用されます。より少ないネットワークリソースを消費するため、通常、ホップ数が少ない（要求された接続をサポートできる）パスが望ましいです。その結果、パス選択アルゴリズムは、特定のリクエストの要件を満たすことができる最小ホップパスを見つけようとします。帯域幅と伝播遅延に反して、ホップ数はLSAに影響を与えないメトリックであり、パス選択アルゴリズムの一部として暗黙的にのみ使用されることに注意してください。
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 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.
1つの選択肢は、定期的な更新を義務付けることです。この場合、更新期間は、ネットワークとルーターの許容可能な対応する負荷に基づいて決定されます。このようなアプローチの主な欠点は、リンクで利用可能な帯域幅の大きな変化が完全な期間不明のままである可能性があり、したがって、多くの誤ったルーティングの決定をもたらす可能性があることです。理想的には、ルーターは、ネットワーク内のすべてのリンクで利用可能な帯域幅の最新ビューを持つ必要があり、選択するパスを最も正確に決定できるようにします。残念ながら、これには非常に頻繁な更新が必要です。たとえば、リンクの利用可能な帯域幅が変更されるたびに、スケーラブルでも実用的でもありません。一般に、頻繁な更新のプロトコルオーバーヘッドと、パス選択アルゴリズムが依存するネットワーク状態情報の精度の間にはトレードオフがあります。次に、いくつかの可能なリンク状態更新ポリシーの概要を説明します。
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）。一方、相対スケールは、メトリック値の変化率が事前定義されたしきい値を超えると更新をトリガーします。相対的または絶対変化トリガーメカニズムが使用されるかどうかに関係なく、周期的なトリガー制約も追加できます。この制約は、連続した更新間の最小間隔を強制するために使用されるホールドダウンタイマーの形であります。または、送信タイマーを使用して、特定の時間が切れた後に更新の送信を確保することもできます。このような機能は、リンク状態の更新広告帯域幅の変更が間違いなく送信される場合に役立ちます。セクション3で説明されている現在のプロトコル拡張機能とセクション4の実装は、メトリックの更新が標準を使用して送信されるため、そのようなオプションを考慮していません。ただし、これは明らかに、メトリックの更新に関連するプロトコルオーバーヘッドを大幅に下げるのに役立つため、考慮に値する拡張機能です。
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.
相対的および絶対的な変化の両方のアプローチでは、LSAで宣伝されているメトリック値は、実際の値または量子化された値のいずれかになります。実際のメトリック値を広告することはより正確であるため、メトリックが頻繁に更新される場合に好ましいです。一方、更新の頻度が低い場合、たとえば、感度のトリガーが低いか、ホールドダウンタイマーの使用のために、広告の量子化された値が有益です。これは、等しいコストパスの数を増やすのに役立ち、したがって、メトリックの不正確さに対する堅牢性を向上させることができるためです。一般に、精度とオーバーヘッドの間には幅広いトレードオフがあり、適切な設計ポイントを選択することは困難であり、多くのパラメーターに依存します（これらの問題の詳細については[AGKT98]を参照）。その結果、これらの問題のより良い理解を得るために、セクション4で説明されている実装は、利用可能な設計スペースの調査を可能にするさまざまなオプションをサポートしています。さらに、セクション4は、リンクによって生成されたトラフィック負荷と処理オーバーヘッドに関する実験データも、さまざまな構成の状態の更新を状態にしていることを報告しています。
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.
QoSリクエストには、計算パスには2つの主要な側面があります。1つ目は、実際のパス選択アルゴリズム自体、つまり、メトリックと基準に依存していることです。2つ目は、アルゴリズムが実際に呼び出されるときです。
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.
アルゴリズムが実行されるトポロジーは、標準のOSPFパス選択と同様に、頂点（4）がルーターとネットワーク（トランジット頂点）、スタブネット（非輸送頂点）で構成されている指向グラフです。パスを計算すると、スタブネットワークが後処理ステップとして追加されます。これは、現在のOSPFルーティングプロトコルで行われているものと本質的に似ています。パス選択で使用される最適化基準は、トポロジ内の各インターフェイスに関連するコストと、アルゴリズム自体でそれらのコストがどのように説明されるかに反映されます。前述のように、パスのコストは、ホップ数と利用可能な帯域幅の量の両方の関数です。その結果、各インターフェイスはメトリックに関連付けられており、これはこのインターフェイスで利用可能な帯域幅の量に対応します。このメトリックは、ホップカウント情報と組み合わせてコスト値を提供します。その目標は、要求された帯域幅をサポートできるものの中で最小限のホップ数でパス数を選択することです。そのようなパスがいくつか利用できる場合、好みは、利用可能な帯域幅（つまり、パス内のリンクのいずれかで最小値）が最大であるパスに対するものです。上記のルールの理論的根拠は次のとおりです。最小限のネットワークリソースを消費する（ホップカウントメトリックで説明されている）、実行可能なパス（利用可能な帯域幅メトリックで説明されている）に焦点を当てます。また、これらのパスを選択するためのルールは、負荷のバランスをとることと、必要な帯域幅が実際に利用可能である可能性を最大化することを目的としています。
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.
標準のルーティングアルゴリズムは通常、単一の客観的な最適化であることに注意してください。つまり、ホップカウントを最小限に抑えるか、パス帯域幅を最大化する可能性がありますが、両方ではありません。二重の客観的なパス最適化はより複雑なタスクであり、一般的に、それは扱いにくい問題です[GJ79]。それにもかかわらず、最適化されている2つの目的の特定の性質（帯域幅とホップカウント）のため、上記のアルゴリズムの複雑さは、標準の単一客観的アルゴリズムの複雑さでさえ競合します。このトピックの徹底的な扱いに関心のある読者には、さまざまなアルゴリズム、線形代数、およびメトリックの変更との関係に関する洞察がある[CAR79]が推奨されます。
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 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つの主なオプションは、1）オンデマンド計算、つまり、新しい要求ごとに計算をトリガーすること、2）何らかの形のプレコンピューションを使用することです。オンデマンドのケースには、計算がトリガーされる時期に関して追加の問題は含まれませんが、新しいリクエストごとにパス選択アルゴリズムを実行すると、この問題に関する議論については[AT98]を参照）。一方、事前計算パスは複数のリクエストにわたって計算コストを償却しますが、各計算インスタンスは通常、オンデマンドの場合よりも高価です（パスはすべての宛先に計算され、すべての可能な帯域幅要求に対して1つではなく、可能なすべての帯域幅要求に対して計算されます。宛先および特定の帯域幅リクエスト）。さらに、パスの頻度に応じて、選択したパスの精度が低い場合があります。このドキュメントでは、主に事前に計算されたパスのケースに焦点を当てます。これは、セクション4で説明されている参照実装で現在サポートされている唯一の方法です。この場合、明らかに重要な問題は、そのような再構成が必要な場合です。場所。私たちが考慮する2つの主なオプションは、特定の（n）数の更新が受信された後の定期的な事前計算と事前計算です。前者は、事前計算に関連する計算負荷に厳密な拘束力を確保するという利点があり、後者はより応答性の高いソリューションを提供できます（5）。セクション4では、異なる期間値の定期的な事前計算のパフォーマンスとコストを比較するいくつかの実験結果を提供します。
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.
このセクションでは、特定のネットワークトポロジとリンクメトリック（利用可能な帯域幅）に対して、可能なすべてのQoSパスを事前にコンピューションしながら、適度に低い計算の複雑さを維持するパス選択アルゴリズムについて説明します。具体的には、アルゴリズムは任意の宛先の最小ホップカウントパスを最大帯域幅の最小ホップカウントパスの事前計算で、標準のBellman-Ford最短パスアルゴリズムのそれに匹敵する計算の複雑さを持っています。Bellman-Ford（BF）最短経路アルゴリズムは、すべてのホップカウントで利用可能な最大帯域幅のパスを計算するように適合しています。これは、BFアルゴリズムのプロパティであり、そのhth iterationでは、ソースと各宛先の間の最適な（コンテキスト：最大帯域幅）パスを、ほとんどのHホップのパスの間で識別します。言い換えれば、パスのコストは、利用可能な帯域幅の関数、つまりパスのすべてのリンクで利用可能な最小の帯域幅であり、最小コストパスを見つけることは最大帯域幅パスを見つけることになります。ただし、BFアルゴリズムはホップ数を増やすことで進行するため、基本的に2番目の最適化基準としてパスのホップカウントを無料で提供します。
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 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.
具体的には、アルゴリズムのKTH（HOPカウント）反復では、Kホップ以下のパス上のすべての目的地が利用できる最大帯域幅が記録されます（対応するルーティング情報とともに）。アルゴリズムが終了した後、この情報は、すべての目的地と帯域幅の要件、可能な限り少ない数のホップ数と新しいリクエストに対応するのに十分な帯域幅を備えたパスを提供します。さらに、このパスは、これらの多くのホップを含むすべての実行可能なパスの間に利用可能な最大帯域幅を持つパスでもあります。これは、任意のホップカウントの場合、アルゴリズムは常に最大利用可能な帯域幅のあるアルゴリズムを選択するためです。
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:
ここで、アルゴリズムのより詳細な説明と、ルーティング情報を記録するために使用されるデータ構造、つまりアルゴリズムが進行するにつれて構築されるQoSルーティングテーブル（アルゴリズムの擬似コードは付録Aにあります）。前述のように、アルゴリズムは、トランジット頂点（ルーターとネットワーク）のみで構成される方向のグラフで動作し、その後、アルゴリズムによって生成されたパスにスタブネットワークが追加されます。グラフ内の各エッジに関連付けられたメトリックは、対応するインターフェイスで使用可能な帯域幅です。ノードnからmへのリンク上の使用可能な帯域幅をb（n; m）で示します。アルゴリズムが実行されているルーター、つまりコンピューティングルーターがパス選択を目的として「ソースノード」として示されるルーターに対応する頂点があります。このアルゴリズムは、このソースノードから可能なすべての宛先ネットワーク、および可能なすべての帯域幅値に合わせてパスを事前に計算することになります。各（ホップカウント）反復で、中間結果はQoSルーティングテーブルに記録されます。これには次の構造があります。
The QoS routing table:
QoSルーティングテーブル：
- 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.
- KXHマトリックスは、kは宛先数（グラフ内の頂点）であり、Hはパスのホップ数の最大（または可能な）数です。
- The (n;h) entry is built during the hth iteration (hop count value) of the algorithm, and consists of two fields:
- （n; h）エントリは、アルゴリズムのHTH反復（ホップカウント値）中に構築され、2つのフィールドで構成されています。
* bw: the maximum available bandwidth, on a path of at most h hops between the source node (router) and destination node n;
* BW：ソースノード（ルーター）と宛先ノードNの間の最大Hホップのパス上の最大利用可能な帯域幅。
* 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).
* 近隣：これは、H（またはそれ以下の）宛先ノードNへのパスに関連するルーティング情報です。ホップバイホップパスの選択（6）のコンテキストでは、隣接情報は、そのパスのソースノードに隣接するノードの単位です。原則として、「隣接」ノードはネットワークではなくルーターでなければなりません。唯一の例外は、ネットワークが宛先ノードである場合です（選択したパスは、ソースをインターコネクションする単一エッジです）。
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.
次に、アルゴリズムの操作と、アルゴリズムが進むにつれてルーティングテーブルのエントリが更新される方法に関する追加の詳細を提供します。簡単にするために、最初にすべてのエッジが「ホップ」としてカウントされるより単純なケースを説明し、後でゼロホップエッジがどのように処理されるかを説明します。ゼロホップのエッジは、トランジットネットワークの頂点で発生します。ここでは、2つの着信エッジと発信エッジのうち1つだけが、両方とも同じ物理ホップに対応するため、ホップカウント計算でカウントする必要があります。この側面を説明するには、ネットワークノードとルーターノードを区別する必要があり、関連する手順は、このセクションの後半および付録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.
アルゴリズムが呼び出されると、ルーティングテーブルが最初に初期化され、すべてのBWフィールドが0に設定され、近隣フィールドがクリアされます。次に、コンピューティングルーターのネイバーの最初の列のエントリ（ワンホップパスに対応）は、次の方法で変更されます。BWフィールドは、ソースから直接エッジで利用可能な帯域幅の値に設定されます。。隣接フィールドは、コンピューティングルーターの隣人、つまり選択したパス上の次のルーターのアイデンティティに設定されます。
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.
その後、アルゴリズムはほとんどの場合に反復します（上記の初期反復を最初のものとして考慮します）。Hの値は暗黙的である可能性があります。つまり、ネットワークの直径、または最悪のケースの複雑さをより適切に制御するために、ほとんどのHホップにパスの長さを制限することができます。後者の場合、Hには、グラフ内の任意のノードへの最小ホップカウントパスの長さよりも大きい値を割り当てる必要があります。
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.
反復hでは、最初に列h-1を列hにコピーします。さらに、アルゴリズムは、以前の反復でBW値を変更したノードのリストを保持します。次に、アルゴリズムは各リンク（n; m）を調べます。ここで、nは以前の反復でBW値が変化したノードであり、最終ホップであるノードMへの（せいぜい）H-HOPパスで最大利用可能な帯域幅をチェックします。リンク。これは、トポロジーデータベースに保持されているエントリ（n; h-1）とリンクメトリック値b（n; m）の間で最小値を取得することになります。この値が入力中のBWフィールドの現在の値（M; H）よりも高い場合、宛先MおよびほとんどのHホップでより良い（より大きなBW値）パスが見つかりました。次に、BWフィールド（M; H）が更新され、この新しい値が反映されます。ホップバイホップルーティングの場合、エントリの隣接フィールド（m; h）は、エントリ（n; h-1）と同じ値に設定されます。これは、これまで識別された最良のパスで、宛先MおよびH（以下）ホップで最初のホップ（ソースからの次のホップ）のアイデンティティを記録します。
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.
前述のように、上記のアルゴリズムをゼロホップエッジを処理するために拡張することが必要です。これは、マルチアクセスネットワーク（T/R、E/Nなど）がルーターを相互接続するために使用する可能性があるためです。このようなエンティティは、OSPFトポロジの頂点によっても表されますが、2つのルーターを接続するネットワークは、2つのホップパスではなく、単一のホップパスとは明確に考慮する必要があります。たとえば、OSPFトポロジが図1のように表すイーサネットネットワークNに接続された3つのルーターA、B、およびCを考慮してください。
A----N----B
|
|
C
Figure 1: Zero-Hop Edges
図1：ゼロホップエッジ
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.
図1の例では、両方向に向けられたエッジがありますが、ネットワークから3つのルーターのいずれかへのエッジはゼロ「コスト」を持つ必要があるため、2回カウントされません。QoSルーティングのコンテキストでそのような環境を検討する場合、一部のエンティティはネットワーク上の「利用可能な帯域幅」を決定する責任があると想定されていることに注意してください。このようなエンティティの仕様と操作は、このドキュメントの範囲を超えています。
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)).
上記のパス選択アルゴリズムのコンテキストでゼロホップエッジを収容することは、次のように行われます。各反復h（最初から始まる）で、エントリ（m; h）が変更された場合は、ゼロがあるかどうかを確認されます - ノードMから出現するコストエッジ（M; K）。これは、Mがトランジットネットワークである場合です。その場合、エッジ（m; k）がカウントされないため、現在のイテレーション内のノードkのエントリ、つまりエントリ（k; h）ではなく（k; h 1）ではなく）さらに改善しようとします。追加のホップとして。アルゴリズムの定期的な動作と同様に、これは、トポロジーデータベース（7）に保持されているエントリ（M; H）とリンクメトリック値B（M; K）の間で最小値を取得することになります。この値が入力中のBWフィールドの現在の値（k; h）よりも高い場合、BWエントリフィールド（k; h）がこの新しい値に更新されます。ホップバイホップルーティングの場合、エントリの近隣フィールド（k; h）は、通常どおり、エントリ（m; h）と同じ値に設定されます（これはエントリ（n;H-1））。
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
スタブネットワークの追加
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.
前述したように、パス選択アルゴリズムは、頂点がルーターとトランジットネットワークのみで構成され、スタブネットワークではなく、その頂点のみで構成されているグラフで実行されます。これは、ポスト処理ステップでスタブネットワークを比較的簡単に追加できるため、計算の複雑さをできるだけ低く保つことを目的としています。この2番目の処理ステップは、現在のOSPFルーティングテーブル計算[MOY98]で使用されているステップと類似しており、ルートのQoS性質を説明するためにいくつかの違いがあります。
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:
具体的には、QoSルーティングテーブルが構築された後、すべてのルーターの頂点が再び考慮されます。各ルーターについて、ルーターのリンク広告にリンクが表示されるスタブネットワークが処理され、利用可能なQoSルートが決定されます。スタブネットワークのQoSルーティング情報は、ルーターおよびトランジットネットワークのQoSルーティング情報と類似しており、追加の行の形でQoSルーティングテーブルへの拡張機能で構成されています。その新しい行の列には、異なるホップカウントのパスに再び対応し、帯域幅と次のホップ情報の両方が含まれています。また、スタブネットワークで利用可能な帯域幅値が宣伝されていると仮定します。前と同様に、この値がどのように決定されるかは、このドキュメントの範囲を超えています。スタブネットワークのQoSルートは、次のように構築されます。
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:
Stub Network Sに対応する行の各エントリには、BWフィールドがゼロに初期化され、隣接がnullに設定されています。Router Vのリンク広告にスタブネットワークSが見つかった場合、スタブネットワークSに対応する行のHTH列の値BW（S、H）が次のように更新されます。
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.
ここで、BW（V、H）は、ルーターVに関連付けられたQOSルーティングテーブル行の対応する列の帯域幅値、つまりVへのHホップパスで利用可能な帯域幅、およびB（V、S）は利用可能な宣伝されていますVからSへのリンク上の帯域幅上記の式は、Hホップパスの帯域幅の帯域幅の最小値とvへの帯域幅の最小値とを使用して、ルーターvを介したパスを使用して、スタブネットワークSへのHホップパスの帯域幅が更新されることを本質的に述べています。Vと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.
隣接フィールドの更新は、Vを通るパスの帯域幅が現在の値よりも大きいことがわかった場合、同様に進行します。それが大きい場合、対応する列のvの隣接フィールドは、Sの現在の隣接フィールドに置き換えます。等しい場合、対応する列のvの隣接フィールドは、sの既存のフィールド、つまり、つまり、Vの近隣の現在のセットは、Sの現在の隣人セットに追加されます。
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.
QoSパスが事前に計算される場合、指定された宛先と帯域幅要件を備えたフローの転送情報をルーティングテーブルから抽出する必要があります。ホップバイホップルーティングのケースは、明示的なルーティングのケースよりも簡単です。これは、明示的なルートではなく、次のホップのみを返す必要があるためです。
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.
具体的には、宛先への新しいリクエスト、たとえばD、および帯域幅要件Bを仮定します。宛先頂点のインデックスは、パスを生成するためにチェックする必要があるQoSルーティングテーブルの行を識別します。QoSルーティングテーブルがこのセクションで提示されたBellman-Fordアルゴリズムを使用して構築されたと仮定すると、検索は、Enterが見つかるまでインデックス（HOP）カウントを増加させ、HOPカウントまたはHの列インデックスで値で、B以上のBWフィールドのこのエントリは、選択したパスを識別する初期情報を指します。
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.
パス計算アルゴリズムが複数の等しいコストパスを格納する場合、パス選択時にある程度の負荷分散を達成できます。同等の次のホップのリストからの次のホップは、丸いロビンの方法で、またはローカルインターフェイスで実際に利用可能な帯域幅によって重み付けされる確率でランダムに選択できます。後者は、セクション4で説明されている実装で使用される方法です。
The case of explicit routing is discussed in Appendix D.
明示的なルーティングの場合については、付録Dで説明します。
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.
前述のように、私たちの目標の1つは、既存のOSPF V2プロトコルへの追加を制限することであり、QoSベースのルーティングに必要なレベルのサポートを提供することです。この目的のために、既存のOSPFメカニズム、データ構造、広告、およびデータ形式のすべてが整ったままです。ドキュメントのこのセクションの目的は、前のセクションで概説したQoSをサポートするために必要なOSPFプロトコルの拡張を説明することです。
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:
OSPFオプションフィールドは、OSPFハローパケット、データベース説明パケット、およびすべてのLSAに存在します。オプションフィールドにより、OSPFルーターはオプションの機能をサポート（またはサポートしない）ことを可能にし、他のOSPFルーターに機能レベルを伝達します。このメカニズムを通じて、異なる機能のルーターはOSPFルーティングドメイン内で混合できます。現在、OSPF標準[MOY98]は、オプションのオプションで次の5ビットを指定しています。
+-----------------------------------------------+
| * | * | 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.
古いOSPF仕様[MOY94]のTOSルーティング機能を示すために使用された最も有意なビット（「T」ビット）が削除されたことに注意してください。ただし、OSPF仕様の以前のバージョンとの後方互換性の場合、TOS固有の情報をRouter-LSA、Summary-LSA、およびAS-External-LSAに含めることができます。
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.
ルーターのQoSルーティング機能のインジケーターとして「T」ビットを取り戻し、「Q」ビットと呼ぶことを提案します。実際、QoS機能は、TOS能力とQoSルーティングの拡張とTOSベースのルーティングの形式として見ることができます。ルーターは、このビットをハローパケットに設定して、そのようなルーティングをサポートできることを示します。このビットがルーターまたは要約リンクリンク状態広告で設定されている場合、パケットで処理するQoSフィールドがあることを意味します。このビットがネットワークリンク状態広告で設定されている場合、広告で説明されているネットワークがQOS対応であることを意味します。
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).
古いスタイル（つまり、RFC 1583ベース）のTOSルーティングの実装を混乱させないように、このアプローチには注意する必要があります。このセクションでさらに紹介されたQoSフィールドのルールをさらにエンコードするTOSメトリックは、これがどのように達成されるかを示します。さらに、RFC 1583の仕様とは異なり、宣伝されていないTOSメトリックをTOS 0と同じコストで扱うように扱われ、QoSルートを計算するために、宣伝されていないTOSメトリック（ホップ）は、特定の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 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.
QoSの導入は、理想的には既存のOSPFV2ルーターとの互換性に影響を与えないはずです。この目標を達成するために、パケット形式の必要な拡張機能は、OSPFv2ルーターによって理解され、無視され、最悪の場合は「優雅に」誤解されている方法で定義する必要があります。[ALM92]で公式に定義されているよりもOSPFパケットで十分に長くなるTOSフィールドでのQoSメトリックのエンコードにより、TOS機能として新しい施設を模倣することができます。OSPFV2ルーターは、これらの定義を無視するか、不特定の定義を検討します。不注意なOSPFの実装が、QOS拡張機能を誤って解釈するときに従来のTOSルーター（存在する場合）に影響を与えるのを防ぐために特定の注意事項が取られます。
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リソースの場合、異なるLSAに含まれるTOSフィールドで5番目のビットを使用することにより、32の組み合わせが利用できます。[ALM92]はTOSを4ビットの長さであると定義するため、この定義は既存の値と矛盾することはありません。さらに、OSPFパケットのTOSフィールドのすべてのビットを考慮に入れることができない素朴な実装を防ぐために、「QoSエンコーディング」の定義は、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
OSPF encoding `QoS encoding values'
-------------------------------------------
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
Representing TOS and QoS in OSPF.
OSPFでTOSとQOを表す。
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パケットの実際のメトリックフィールドは、使用される値をエンコードするための16ビットのみを提供し、GBITS/sに及ぶ帯域幅をサポートするリンクが現実になりつつあるという事実を考えると、利用可能なリソースメトリックの線形表現は実現できません。ソリューションは、マンティッサと指数をエンコードするための適切に選択された暗黙的な基本値と数ビットを使用して、指数エンコードです。説明されているソリューションにつながる詳細な考慮事項はここでは示されていませんが、[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.
次の表は、異なる指数を使用した場合の帯域幅の範囲と、予約の可能性の粒度を示しています。
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
Ranges of Exponent Values for 13 bits, base 8 Encoding, in Bytes/s
13ビットの指数値の範囲、ベース8エンコーディング、バイト/s
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."
帯域幅エンコーディングルールは、次のように要約できます。「16ビットフィールドで利用可能な帯域幅を3ビット指数（8の想定ベース）として表し、以下に示すように13ビットマンティッサが続き、2の上記の表現の補完を宣伝します。」
0 8 16
| | |
-----------------
|EXP| MANT |
-----------------
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]に記載されています。
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.
例として結論として、8 GBITS/S = 1024^3バイト/sの帯域幅のリンクを仮定します。そのエンコードは、1024^3 = 4,096*8^6以降の指数値6で構成されます。8^6または約260 kbytes/s。関連するバイナリ表現は、％（110）0 1000 0000 0000％または53,248（8）になります。このリンクの帯域幅コスト（宣伝された値）がアイドル状態である場合、上記のバイナリ表現の2の補数、すなわち％（001）1 0111 1111 1111％（2^16-1）-53,248 = 12,287。現在、6; 400 mbits/s = 200 * 1024^2の現在の予約レベルがあると仮定すると、リンクに利用可能な帯域幅の1; 600 mbits/sが残っています。1'600 mbits/sのこの利用可能な帯域幅のエンコードは6,400 * 8^5で、これは8^5または約の粒度に対応します。30 kbytes/s、および％（101）1 1001 0000 0000％または小数値47,360のバイナリ表現を持っています。この負荷レベルでのリンクの広告コストは、％（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.
コスト関数は必要に応じて動作することに注意してください。つまり、リンクで帯域幅が少ないほど、コストが高くなり、リンクが魅力的ではありません。さらに、利用可能な帯域幅が少ないリンクに対するより良い粒度のターゲットプロパティも達成されます。ただし、上記の例に記載されている数値は、提案されたエンコードの解像度と正確に一致していることを指摘する必要があります。これにより、エンコードと正確に一致しない場合、利用可能な帯域幅の値をエンコードする方法の問題が明らかになります。標準的な慣行は、それを最も近い数に丸めることです。私たちは最終的に、楽観的よりも悲観的である方が良いかもしれないコスト価値に関心があるため、コストを上げて帯域幅を締めくくることを選択します。
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と定義されていることを除いて、帯域幅について説明されている同じ指数法を使用してマイクロ秒でエンコードされます。したがって、表現できる最大遅延は（2^13-1） *4^7つまり、約134秒。
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表記を考えると、オプションフィールドのQビットとしてTビットを（再）導入することを除いて、パケット形式の変更は必要ありません。Qビットを理解していないルーターは、分散したQoSメトリックを検討してはならないか、「不明な」TOSと見なすべきではありません。
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をサポートするために、2つのリンク状態広告、ルーターリンク広告、および概要リンク広告への追加があります。上記のように、ルーターは、リンク状態ヘッダーのオプションフィールドにQビットを設定することにより、QoSをサポートするものとして識別します。QOSをサポートするルーターがルーターリンクまたはサマリリンク広告のいずれかを受信する場合、受信した広告にエンコードされたQOSメトリックを解析する必要があります。
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メトリック集約のサポートを提供する問題については説明していません。これはさらなる研究のために残されています。
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.
サマリーリンク、仮想リンク、および概要リンク広告の増分更新などのサポートは、このドキュメントでは対処されておらず、さらなる調査のために残されています。存在する仮想リンクの場合、ルーターがQoS機能を宣伝している場合でも、これらのリンクが非QOS対応であるとパス選択が想定されています。また、前述のように、このドキュメントは、QoSドメイン内の非QoSルーターの問題に対処していません。
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].
このセクションでは、ゲート[CON]環境でセクション2.3.1のコンピュータンス前ベースのアプローチを実装することから得られた経験について報告します。最初に、ゲート環境を簡単に紹介し、次にこの環境でQoS拡張機能がどのように実装されたかについての詳細を示します。最後に、実装の取り組み中に発生した問題について説明し、QoS拡張がQoS対応ルーターとQoSルーターのネットワークに課すオーバーヘッドにいくつかの測定ベースの結果を提示します。実装調査の詳細については、読者は[AGK99]を参照しています。シミュレーションに基づく追加のパフォーマンス評価は、[AGKT98]にあります。
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 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).
Gated [Con]は、UNIXオペレーティングシステムを実行しているホストにルーティングプロトコルを実装するためのプラットフォームを提供する人気のあるパブリックドメイン（9）プログラムです。ゲートソフトウェアの分布には、OSPFプロトコルを含む多くの一般的なルーティングプロトコルの実装も含まれています。ゲート環境は、ルーティングプロトコルの実装に役立つさまざまなサービスを提供します。これらのサービスには、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プロセス内で行われ、ルーティングプロトコルは1つまたは複数のタスクとして実装されます。ゲートタスクは、UNIXソケットに関連付けられたコードのコレクションです。ソケットは、タスクの入力要件と出力要件に使用されます。ゲートのメインループには、他の操作の中でも、すべてのタスクソケットにselect（）呼び出しが含まれており、それらのいずれかで読み取り/書き込みまたはエラー条件が発生したかどうかを判断します。ゲートは、個々のリンク状態レコードに迅速にアクセスするために、RADIXツリーを使用してOSPFリンク状態データベースを実装します。さらに、隣接するネットワーク要素（隣接するルーターなど）のリンク状態レコードは、データベースレベルでポインターと一緒にリンクされます。Gatedは、すべてのアクティブルーティングプロトコルによって発見されたルートを含む単一のルーティングテーブルを維持します。同じ宛先への複数のルートは、一連のルールと管理の設定に従って優先順位付けされ、宛先ごとにアクティブなルートのみが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ルーティングテーブルのパス構造に影響を与えました。前述のように、明示的なルートの構築を可能にするために、構造を簡単に拡張できます。
- 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.
- 構成サポート、エラーロギングなどを含む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.
- さまざまなアプローチでの実験を許可する能力、例えば、ゲート構成ファイルからのこれらのポリシーの選択とパラメーター化のサポートを伴うさまざまな更新およびプレコンピューション前トリガートリガーポリシーの使用。
- 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]に基づくインターフェイスを介して伝達され、ISIで開発されたRSVPコード、バージョン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.
- エリア内のすべてのルーターは、OSPFのQoS対応バージョンを実行すると想定されています。つまり、OSPFプロトコルの非QOS認識バージョンとの間の操作性は考慮されません。
- All interfaces on a router are assumed to be QoS capable.
- ルーター上のすべてのインターフェイスは、QOS対応であると想定されています。
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ルーティング拡張機能は次のモジュールにさらに分割されます。
- 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つの連続した更新トリガー間の最小間隔を実施するホールドダウンタイマーも実装します。
- Pre-computation trigger module determines when to perform QoS path pre-computation. So far, this module implements only periodic pre-computation triggering.
- Pre-Computationトリガーモジュールは、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.
- PATH Pre-Computationモジュールは、セクション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.
- PATH選択および管理モジュール特定の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固有のルーティングテーブルを実装します。
- Tspec mapping module maps request requirements expressed in the form of RSVP Tspecs and Rspecs into the bandwidth requirements that QoS routing uses.
- TSPECマッピングモジュールマップは、QOSルーティングが使用する帯域幅要件にRSVP TSPECとRSPECの形で表される要件を要求要件を要求します。
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のゲート実装のフレームワークにマッピングすると、多くの問題と設計上の決定が行われました。これらの問題は、主に2つのカテゴリに分類されました。a）既存の同様のOSPFメカニズムを備えたQoS拡張機能の相互操作、およびb）QoSルーティングテーブルの構造、配置、および構成。次に、これらの問題について簡単に議論し、結果の設計上の決定を正当化します。
+--------------------------------------------------+
| +-----------------------------+ |
| | 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 |
+----------------+ +----------+
Figure 2: The software architecture
図2：ソフトウェアアーキテクチャ
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は、リンク状態の更新と独自のホールドダウンタイマーをトリガーするための独自のメカニズムを実装しています。次のような潜在的な競合を処理します。第一に、OSPFは低周波数で定期的に更新をトリガーするため、これらの更新は生成された更新の総量のわずかな部分に過ぎないと予想しています。その結果、OSPFの定期的な更新トリガーを維持することを選択しました。異なるホールドダウンタイマー設定の設定で競合を解決するには、より多くの注意が必要です。特に、既存のOSPFがタイマーを押し続けると、QoSの更新が妨げられないようにすることが重要です。1つのオプションは、既存のOSPFタイマーを無効にすることですが、過渡的な過負荷に対する保護は、わずかな値ではありますが、いくつかのホールドダウンタイマーを必要とします。その結果、既存のOSPFのホールドダウンタイマーは保持されましたが、その値を1秒に減らしました。この値は十分に低く（ゲートタイマーの最大解像度が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メカニズムは、複数のLSAの謝辞の集約を可能にする遅延承認のサポートです。リンク状態の更新は、認識されるまで再送信キューで維持されるため、QoS更新の増加率と組み合わされた確認の生成の過度の遅延は、再送信キューのオーバーフローにつながる可能性があります。これらの潜在的なオーバーフローを回避するために、このメカニズムは完全にバイパスされ、隣接するルーターから受け取ったLSAはすぐに認められました。考慮されたが実装されていない別のアプローチは、QOS LSAを信頼できないようにすること、つまり、潜在的な干渉を避けるために謝辞を排除することでした。QoS LSAを信頼できないようにすることは、通常のLSAと比較してより高い頻度と、QoS LSAの損失がプロトコル操作に与える影響の減少のため、合理的な設計の選択になります。QoS LSAの損失は、OSPFの基本動作を妨げず、QoSルーティングによって発見されたパスの品質を一時的に低下させるだけであることに注意してください。
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ルーティングテーブルに配置されます。このテーブルは、この宛先への利用可能なすべてのパスを含む各宛先用のパス構造のセットとして実装されています。個々のパス構造を効率的に特定できるようにするには、アクセス構造が必要です。開発の取り組みを最小限に抑えるために、通常のゲートルーティングテーブルに使用される基数の木構造が再利用されました。さらに、QoSルーティングテーブルは、ゲートルーティングテーブルから独立しており、変更をローカル化し、既存のOSPFコードへの影響を最小限に抑えるという設計目標に準拠しています。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ルーティングテーブルのこの完全な脱配列は、特にメモリの割り当てと脱配列が高価な操作であるため、潜在的に無駄になります。さらに、パスの事前計算は通常、トポロジの変化によってトリガーされないため、通常、目的地のセットは同じままで、変更されていない基数の木に対応します。自然な最適化は、経路構造のみを解釈し、基数の木を維持することになります。さらなる強化は、パス構造も維持し、必要な場合にのみ徐々に更新しようとすることです。ただし、潜在的な利益にもかかわらず、これらの最適化は最初の実装に含まれていません。主な理由は、それらが常に全体的なデータ構造の完全性を確保するために微妙かつ多数のチェックを伴うことです。
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ルーティングテーブルの計算、b）QoSルーティングテーブルからのパスの選択、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]に記載されています。ゲートソフトウェアを実行しているシステムは、200 MHz、64 MBYTES、または実際のメモリでPentium Proプロセッサを備えたIBM Intellistation Z Proで、FreeBSD 2.2.5リリースとゲート4を実行しています。表1の結果から、1つは、パスの事前計算のコストは、通常のSPF計算のコストよりもはるかに高くありません。ただし、PATHの事前計算は、SPF計算よりもはるかに頻繁に実行される必要がある場合があり、これにより、処理コストが高くなる可能性があります。この問題は、このセクションの後半で説明されている一連の後続の実験で調査されました。表1に報告されている他のコストコンポーネントにはメモリが含まれており、QoSルーティングテーブルには通常のルーティングテーブルよりも約80％多くのメモリが必要であることがわかります。最後に、パスを選択するコストは、コンピューティング前のパスと比較して非常に少ないことがわかります。予想どおり、トポロジのサイズが増加すると、すべての測定量が増加します。特に、SPF計算とQoSパスの両方の両方のストレージ要件と処理コストは、ネットワークサイズとほぼ直線的に行われます。
________________________________________________________________________
|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_|
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].
表1で報告されているスタンドアローンコストに加えて、大規模なネットワークのコンテキストで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）プリコンピューションの期間、b）リンク状態の更新をトリガーするためのしきい値など、ネットワークトポロジが他のQoSパラメーターとともに変化するさまざまな構成をさらに使用できます。ここで報告された結果は、2種類のトポロジを使用して導出されました。1つは通常のが人工的な8x8メッシュネットワークに基づいており、もう1つは以前のいくつかの研究[AGKT98、AT98]で使用されており、全国的なISPのネットワークに近いものです。計算前の期間に関する限り、1、5、50秒の3つの値が選択され、リンク状態の更新しきい値のトリガーのために、10％と80％のトリガーが使用されました。これらの値は、事前に計算されたパスの精度と、ルーターで利用可能なリンク状態情報の精度の点で幅広い範囲をカバーするために選択されました。また、1秒がゲートによって許可された最小のプレコンピューション期間であることに注意してください。
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パラメーターの2つのトポロジとさまざまな組み合わせ、つまりリンク状態の更新をトリガーするための再計算期間としきい値を示します。表3に、ルーターに隣接するリンクのQoS更新の帯域幅消費量を示します。
________________________________________________________________
|_____________________|_________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%)_|
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%)|
8x8 mesh
8x8メッシュ
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.
表2では、処理荷重は、ゲート処理によって消費される総CPUリソースの割合として表されます。同じ表は、QoSパラメーターの各組み合わせに対して達成されるルーティングパフォーマンスも示しているため、さまざまな処理コスト/ルーティングパフォーマンスのトレードオフの比較を行うことができます。ルーティングパフォーマンスは、提供される帯域幅の合計で拒否された要求の要求された帯域幅の合計として定義された帯域幅ブロッキング比を使用して測定されます。表2からわかるように、QoSルーティングテーブルが毎秒再計算され、リンクで利用可能な帯域幅が最後に広告された値の10％以上変化するたびにLSAが生成された場合でも、処理荷重が低くなります。これは、今日のプロセッサテクノロジーを考えると、QoSルーティングは、少なくともその処理要件の点では、費用のかかる強化と見なされるべきではないことを示しているようです。もう1つの一般的な観察は、ネットワークサイズが明らかに影響を及ぼしますが、異なるパラメーターの相対的な影響に劇的に影響しないように見えるということです。特に、ISPとメッシュのトポロジーの間に存在する違いにもかかわらず、コンピューティング前の期間または更新のしきい値を変更すると、本質的に同様の相対的な変化に変換されます。
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].
表3に示す更新トラフィックについて、同様の結論を導き出すことができます。すべての場合、このトラフィックはリンクの容量のほんの一部にすぎません。明らかに、ルーターの負荷とリンク帯域幅の消費の両方は、測定のターゲットであり、選択肢が異なるルーターとリンクに依存します。ここに示されている結果は指標であることを意図しており、より完全な議論は[AGK99]で見つけることができます。
_______________________________________
|_Link_state_threshold_|_______________|
|_________10%__________|3112_bytes/sec_|
|_________80%__________|177_bytes/sec__|
isp
________________________________________
|_________10%__________|15438_bytes/sec_|
|_________80%__________|1053_bytes/sec__|
8x8 mesh
8x8メッシュ
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ルーティングに関連するオーバーヘッドが過剰ではなく、間違いなく最新のプロセッサとワークステーションテクノロジーの機能内にあることを実証することができました。
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ポリシー決定ポイントとポリシー執行ポイントを使用して提供できます。同様に、[RMK 98]のルールと言語に基づいて決定を実装することにより、QoS要求の受容性を強制するポリシーサーバーも、目的の機能を提供することができます。
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にラベル付けされています。L=頂点ラベルの順序付きペア（n、m）でラベル付けされたエッジのセット。S =ソース頂点（アルゴリズムが実行される）。l： * b（n、m）のすべてのエッジ（n、m）=頂点nとmの間のエッジに関連するインターフェイスの利用可能な帯域幅（最後の更新に従って）。* if（n、m）nがルーターである場合のエッジ（n、m）に対応する発信インターフェイス。H =最大ホップカウント（せいぜいグラフの直径）。
Type: tab_entry: record bw = integer, neighbor = integer 1..N.
タイプ：Tab_Entry：BW = Integer、Neighbor = Integer 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）エントリはtab_entryレコードであり、tt [n、h] .bwは最大利用可能な帯域幅です（このようにしているように、このようにしています。遠い）頂点SとN、TT [N、H]の間のほとんどの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_NEW：現在の反復でBW値（TTテーブルなど）を変更した頂点のリスト。
The Algorithm:
アルゴリズム：
begin;
始める;
for n:=1 to N do /* initialization */
begin;
TT[n,0].bw := 0;
TT[n,0].neighbor := null
TT[n,1].bw := 0;
TT[n,1].neighbor := null
end;
TT[s,0].bw := infinity;
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;
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;
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;
end.
終わり。
B. On-Demand Dijkstra Algorithm for QoS Path Computation
B. QoSパス計算のためのオンデマンドDijkstraアルゴリズム
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ルートのリクエストを受信したときにそのような計算を実行することができます。このようなアプローチの利点は、事前に計算されたルートの再計算がトリガーされる頻度に応じて、オンデマンドルート計算が利用可能な最新のリンクメトリックを使用してより良いルートを生成できることです。オンデマンドパス計算のもう1つの利点は、関連するストレージ保存です。つまり、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.
このセクションでは、標準のDijkstraアルゴリズムが、特定の宛先および帯域幅の要件に対して、必要な帯域幅に対応し、最大帯域幅を持つことができる最小ホップパスを生成する方法について簡単に説明します。Dijkstraアルゴリズムは現在の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.
アルゴリズムは、基本的に最小ホップパス計算を実行します。グラフでは、入手可能な帯域幅が計算をトリガーするフローによって要求された帯域幅よりも少ないグラフで削除されました。これは、前処理ステップを通じて、または考慮されているエッジの使用可能な帯域幅値をチェックしてアルゴリズムを実行したときに実行できます（次の擬似コードを参照）。標準のDijkstraベースの最小ホップカウントパス計算のもう1つの変更は、アルゴリズムが進行するにつれて維持される等しいコスト（以前の）ホップのリストを利用可能な帯域幅に従ってソートする必要があることです。これは、利用可能な最大帯域幅の最小ホップパスの選択を許可するためです。あるいは、アルゴリズムは、各ステップで、最大利用可能な帯域幅を持つ等しいホップカウントパスのみを維持するように変更することもできます。これは、ホップ数と利用可能な帯域幅の両方の関数であるコストを考慮することに基本的になります。
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フェーズで行われます。明示的なルート構築をサポートするために必要な変更は簡単です。擬似コードは、簡単にするために等しいコストのマルチパスを処理しませんが、このサポートを追加するために必要な変更も簡単に行われます。
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にラベル付けされています。L=頂点ラベルの順序付きペア（n、m）でラベル付けされたエッジのセット。S =ソース頂点（アルゴリズムが実行される）。l： * b（n、m）のすべてのエッジ（n、m）=頂点nとmの間のエッジに関連するインターフェイスの利用可能な帯域幅（最後の更新に従って）。* if（n、m）= nがルーターである場合のエッジ（n、m）に対応する発信インターフェイス。D =宛先頂点。b =提供されるフローの要求された帯域幅。
Type: tab_entry: record hops = integer, neighbor = integer 1..N, ontree = boolean.
タイプ：tab_entry：レコードホップ= integer、neighbor = integer 1..n、ontree = boolean。
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）エントリはTAB_ENTRYレコードであり、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;
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;
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 */
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.
C. Precomputation Using Dijkstra Algorithm
C. Dijkstraアルゴリズムを使用した事前計算
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ルートの事前計算を可能にするDijkstraベースのアルゴリズムの概要を説明しています。Dijkstraベースのアルゴリズムを使用する利点は、既存のOSPF実装とのより大きな相乗効果です。すべての「最良の」パスを計算する解決策は、完全なグラフから始まり、前の計算で使用されたしきい値よりも帯域幅の少ないリンクを削除するツリーにまたがる最短パスを連続的に計算することです。これにより、帯域幅が良くなる可能性がありますが、もちろんより多くのホップでパスが生成されます。多数のDijkstra計算にもかかわらず、計算された経路の構造がパス圧縮に傾いているため、増分スパニングツリー計算などのいくつかの最適化を使用し、複雑さとストレージの観点から効率的な実装を可能にします[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.
このテーマのバリエーションは、事前に計算されたパスの「正確性」を交換することです（つまり、生成されるパスは、Dijkstraの最短パスアルゴリズムの修正バージョンを使用するために、必要以上にホップカウントである可能性があります）また、いくつかの計算を保存します。この精度の損失は、最小ホップカウントパスを計算するときに使用される量子化された帯域幅値に依存する必要性に起因します。言い換えれば、新しいフローによって要求できる帯域幅値の範囲は、一定数の量子化された値にマッピングされ、各量子化された値に対して最小ホップカウントパスが生成されます。たとえば、帯域幅の値は、これらの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は量子化された帯域幅値の数です。
- 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）エントリには、少なくともbw [q]（qth Quantized帯域幅値）の帯域幅要求に対応できる宛先Nへの最小ホップカウントパスを識別する情報が含まれています。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.
* 近隣：これは、宛先ノードNへの最小ホップカウントパスに関連付けられたルーティング情報であり、その利用可能な帯域幅は少なくともBW [Q]です。ホップバイホップルーティングアプローチを使用すると、近隣情報は、そのパスのソースノードに隣接するノードの単位のアイデンティティです。
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について、アルゴリズムは元のネットワークトポロジから削除されます。すべてのリンク（n; m）b（n; m）<bw [q]で、残りのトポロジでダイクストラベースの最小ホップカウントアルゴリズムを実行します（10）ソースノードとグラフ内の他のすべてのノード（頂点）の間。オンデマンドパス計算に使用されるDijkstraと同様に、アルゴリズムの実行中に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 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番目の列が更新されます。これは、ホップフィールドでの記録に相当し、アルゴリズムによって生成されたパスのホップカウント値と、近隣フィールドを更新することになります。前と同様に、隣接フィールドの更新は、パス計算の範囲に依存します。ホップバイホップルーティングの決定の場合、近隣フィールドは、アルゴリズムによって返されるパス上のソースノード（次のホップ）に隣接するノードのIDに設定されます。ただし、特定の量子化された帯域幅に対応できるすべての最小ホップパスの中で、利用可能な最大帯域幅のパスが常に選択されることを確認するには、場合によっては、隣接フィールドのわずかに異なる更新メカニズムを使用する必要があることに注意してください。具体的には、特定の行、つまり宛先ノードnの場合、列qのホップフィールドの値は列q 1の値（ここではq <qを想定しています）、つまりBWに対応できるパスに等しく見られます[Q]およびBW [Q 1]は同じホップカウントを持ち、アルゴリズムはエントリ（n; q 1）からneighterフィールドの値をエントリ（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.
入力：V =頂点のセット、整数1からNにラベル付けされています。L=頂点ラベルの順序付きペア（n、m）でラベル付けされたエッジのセット。S =ソース頂点（アルゴリズムが実行される）。bw [1..q] =帯域幅の値の配列は、フロー要求を「Quantize」します。l： * b（n、m）のすべてのエッジ（n、m）=頂点nとmの間のエッジに関連するインターフェイスの利用可能な帯域幅（最後の更新に従って）。* if（n、m）= nがルーターである場合のエッジ（n、m）に対応する発信インターフェイス。
Type: tab_entry: record hops = integer, neighbor = integer 1..N, ontree = boolean.
タイプ：tab_entry：レコードホップ= integer、neighbor = integer 1..n、ontree = boolean。
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）エントリはTAB_ENTRYレコードであり、TT [N、Q] .BWは利用可能な帯域幅です（これまでのところ既知のように）頂点b（q）に対応する頂点SとNの間の最短パスでは、TT [n、q]。ルーターまたは宛先nのいずれかです。S：候補の頂点のリスト。V：検討中の頂点。Q：「Quantize」ステップ
The Algorithm:
アルゴリズム：
begin;
for r:=1 to Q do
begin;
for n:=1 to N do /* initialization */
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 */
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で説明されているように、ホップバイホップルーティングの方法とは異なる方法で近隣フィールドを更新することです。パス計算アルゴリズムでは、計算された部分パスのソースノードに隣接するルーターのIDを反映するように隣接フィールドが更新されていることを思い出してください。これにより、特定のパスのソースで次のホップを返すことが容易になります。明示的なルーティングのコンテキストでは、パス上の以前のルーターの身元を反映するように近隣情報が更新されます。
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 associated bandwidth on the link from the neighbor to the (current) destination.
この変更により、QoSルーティングテーブルの近隣情報からパス上の頂点の完全なリストを抽出するために使用される基本的なアプローチは、宛先からオリジンの頂点まで「再帰的」に進むことです。パスは、事前計算されたQoSルーティングテーブルを頂点から頂点まで踏み込み、各ステップで対応する隣接（前駆体）情報を識別することにより抽出されます。1つのステップで識別されたネイバーノードが次のステップで検索される宛先ノードになるため、プロセスは再帰的であると説明されています。ソースルーターに到達すると、抽出されたすべての隣接フィールドの連結は、目的の明示的ルートを形成します。これは、セクション2.3.1および付録Cのアルゴリズムに適用されます。特定の段階に複数の隣接選択がある場合（等しいマルチパスが等しいため）、そのうちの1つは、加重される確率でランダムに選択できます。、近隣から（現在の）宛先へのリンク上の関連する帯域幅によって。
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-Fordアルゴリズムが使用された場合、検索はインデックス（ホップ）が見つかるまでカウントされます。B以上または大きい場合、このエントリは、選択したパスを識別する初期情報を指します。付録CのDijkstraアルゴリズムが使用されている場合、Qb> = Bが最初に識別されるように最初の量子値QBが最初に識別され、関連する列が選択されたパスを識別する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のアルゴリズムを使用してテーブルが構築されたか、付録Cを使用してテーブルが構築されたかどうかにかかわらず、パス上の頂点の完全なリストの再構成も同様に進行します。ソースノードからのパス上の前のノードと、現在のエントリに関連付けられたものと同じ帯域幅の機能を指します。したがって、完全なパスは、連続したエントリの隣接分野によって提供されたポインターに従うことによって再構築されます。
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-Fordアルゴリズムの場合、これは、各ステップで前の列のエントリの隣接フィールドが指す行インデックスを使用して、列から列へのテーブルの後方に戻ることを意味します。毎回、隣接フィールドで指定されている対応する頂点インデックスは、これまでに作成された頂点のリストにプリペインされています。列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.
付録CのDijkstraアルゴリズムの場合、ルーティングテーブルのパスと列との関係が異なるため、バックトラッキングプロセスはわずかに異なりますが、列はホップカウントの代わりに量子化された帯域幅値に対応しています。バックトラッキングは、フローの帯域幅要件を満たすために必要な量子化された帯域幅値に対応する列に沿って進みます。各ステップで、隣接フィールドで指定された頂点インデックスは、これまでに作成された頂点のリストにプリペーンされており、移動する次の行インデックスを識別するために使用されます。プロセスは、隣のフィールドが流れの原点頂点を指定するエントリに到達すると終了します。グラフに頂点があるのと同じくらい多くの行があるので、つまりn、つまり、プロセスが終了する前にnステップにかかる可能性があることに注意してください。
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. これはUni-Castフローに当てはまりますが、マルチキャストフローの場合、ホップバイホップと明示的なルーティングは明らかに異なる意味を持ちます。
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. 明示的なルーティングをサポートするための変更については、付録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. ゲートソフトウェアの最近のバージョンのいくつかへのアクセスは、ゲートコンソーシアムのメンバーに制限されています。
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. 幅最初の検索（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。Guerin、およびS. Kamat。QoSルーティング拡張機能の実装とパフォーマンスの測定値は、OSPFへの拡張機能を測定します。InfoCom'99の議事録、1999年3月、ニューヨーク州ニューヨーク680--688ページ。
[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。Guerin、S。Kamat、およびS. K. Tripathi。QoSルーティング：パフォーマンスの観点。ACM Sigcomm'98の議事録、17〜28ページ、カナダ、バンクーバー、10月
[Alm92] Almquist, P., "Type of Service in the Internet Protocol Suite", RFC 1349, July 1992.
[ALM92] Almquist、P。、「インターネットプロトコルスイートのサービスの種類」、RFC 1349、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パス計算の処理コストを削減すると。ICNP'98の議事録、ページ80--89、テキサス州オースティン、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。統合サービスネットワーク用のルートプレコンピューティングアルゴリズム。Journal of Network and Systems Management、3（4）、1995。
[Car79] B. Carre. Graphs and Networks. Oxford University Press, ISBN 0-19-859622-7, Oxford, UK, 1979.
[CAR79] B.カール。グラフとネットワーク。Oxford University Press、ISBN 0-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 Press、ケンブリッジ、マサチューセッツ州、1990年。
[Con] Merit GateD Consortium. The Gate Daemon (GateD) project.
[con]ゲートコンソーシアムのメリット。ゲートデーモン（ゲート）プロジェクト。
[GJ79] M.R. Garey and D.S. Johnson. Computers and Intractability. Freeman, San Francisco, 1979.
[GJ79] M.R. GareyとD.S. Johnson。コンピューターと扱いにくい。フリーマン、サンフランシスコ、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。カマト、およびS.ヘルツォグ。RSVPを使用したQoSパス管理。第2 IEEEグローバルインターネットミニカンファレンスの議事録、ページ1914-1918、アリゾナ州フェニックス、11月
[GKR97] Guerin, R., Kamat, S. and E. Rosen, "An Extended RSVP Routing Interface, Work in Progress.
[GKR97] Guerin、R.、Kamat、S。、およびE. Rosen、「拡張された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] der-hwa G.、Li、T.、Guerin、R.、Rosen、E。、およびS. Kamat、「RSVPを使用した明示的なパスの予約の設定」、進行中の作業。
[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. Guerin、A。Orda、およびD. Williams。QoSルーティングメカニズムとOSPF拡張。第2 IEEEグローバルインターネットミニカンファレンスの議事録、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] Nichols、K.、Blake、S.、Baker F.、D。Black、「IPv4およびIPv6ヘッダーの差別化されたサービスフィールド（DSフィールド）の定義」、RFC 2474、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」、RFC 1583、1994年3月。
[Moy98] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[MOY98] Moy、J。、「OSPFバージョン2」、STD 54、RFC 2328、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。ATM LANSの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.
[RMK 98] R. Rajan、J。C。Martin、S。Kamat、M。See、R。Chaudhury、D。Verma、G。Powers、およびR. Yavatkar。ネットワークにおける差別化されたサービスと統合サービスのスキーマ。インターネットドラフト、1998年10月。進行中の作業。
[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] Braden、R.、Editor、Zhang、L.、Berson、S.、Herzog、S.およびS. Jamin、「リソース予約プロトコル（RSVP）バージョン1、機能仕様」、RFC 2205、1997年9月。
[SPG97] Shenker, S., Partridge, C. and R. Guerin, "Specification of Guaranteed Quality of Service", RFC 2212, November 1997.
[SPG97] Shenker、S.、Partridge、C。およびR. Guerin、「保証されたサービス品質の仕様」、RFC 2212、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.タルジャン。動的な木のデータ構造。Journal of Computer Systems、26、1983。
[Tan89] A. Tannenbaum. Computer Networks. Addisson Wesley, 1989.
[タン89] A.タネンバウム。コンピューターネットワーク。アディソン・ウェスリー、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. Guerin、「政策ベースの入場管理のためのフレームワーク」、1999年4月、インターネットドラフト。
Authors' Addresses
著者のアドレス
George Apostolopoulos IBM T.J. Watson Research Center P.O. Box 704 Yorktown Heights, NY 10598
George Apostolopoulos IBM T.J.ワトソン研究センターP.O.ボックス704ヨークタウンハイツ、ニューヨーク10598
Phone: +1 914 784-6204
Fax: +1 914 784-6205
EMail: georgeap@watson.ibm.com
Roch Guerin University Of Pennsylvania Department of Electrical Engineering, Rm 367 GRW 200 South 33rd Street Philadelphia, PA 19104--6390
ペンシルベニア大学電気工学部、RM 367 GRW 200サウス33rdストリートフィラデルフィア、ペンシルベニア州19104-6390
Phone: +1 215-898-9351
EMail: guerin@ee.upenn.edu
Sanjay Kamat Bell Laboratories Lucent Technologies Room 4C-510 101 Crawfords Corner Road Holmdel, NJ 07733
Sanjay Kamat Bell Laboratories Lucent Technologies Room 4C-510 101 Crawfords Corner Road Holmdel、NJ 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
Ariel Orda Dept. Electrical Engineering Technion -I.I.THaifa、32000-イスラエル
Phone: +011 972-4-8294646 Fax: +011 972-4-8323041 EMail: ariel@ee.technion.ac.il Tony Przygienda Siara Systems 300 Ferguson Drive Moutain View California 94043
電話：011 972-4-8294646ファックス：011 972-4-8323041メール：ariel@ee.technion.ac.il Tony Przygienda Siara Systems 300 Ferguson Drive Moutain View California 94043
Phone: +1 732 949-5936
Email: prz@siara.com
Doug Williams IBM T.J. Watson Research Center P.O. Box 704 Yorktown Heights, NY 10598
ダグ・ウィリアムズIBM T.J.ワトソン研究センターP.O.ボックス704ヨークタウンハイツ、ニューヨーク10598
Phone: +1 914 784-5047
Fax: +1 914 784-6318
EMail: dougw@watson.ibm.com
Full Copyright Statement
完全な著作権声明
Copyright (C) The Internet Society (1999). All Rights Reserved.
Copyright（c）The Internet Society（1999）。無断転載を禁じます。
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
このドキュメントと翻訳は他の人にコピーされて提供される場合があります。また、それについてコメントまたは説明する派生作品、またはその実装を支援することは、いかなる種類の制限なしに、準備、コピー、公開、および部分的に配布される場合があります。、上記の著作権通知とこの段落がそのようなすべてのコピーとデリバティブ作品に含まれている場合。ただし、このドキュメント自体は、インターネット協会や他のインターネット組織への著作権通知や参照を削除するなど、いかなる方法でも変更できない場合があります。インターネット標準プロセスに従うか、英語以外の言語に翻訳するために必要な場合に従う必要があります。
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
上記の限られた許可は永続的であり、インターネット社会またはその後継者または譲受人によって取り消されることはありません。
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
この文書と本書に含まれる情報は、「現状」に基づいて提供されており、インターネット社会とインターネットエンジニアリングタスクフォースは、ここにある情報の使用が行われないという保証を含むがこれらに限定されないすべての保証を否認します。特定の目的に対する商品性または適合性の権利または黙示的な保証を侵害します。
Acknowledgement
謝辞
Funding for the RFC Editor function is currently provided by the Internet Society.
RFCエディター機能の資金は現在、インターネット協会によって提供されています。