[要約] 要約：RFC 2386は、インターネットにおけるQoSベースのルーティングのフレームワークを提供しています。 目的：このRFCの目的は、ネットワーク内のトラフィックの品質を向上させるために、QoSベースのルーティング手法を提案することです。
Network Working Group E. Crawley
Request for Comments: 2386 Argon Networks
Category: Informational R. Nair
Arrowpoint
B. Rajagopalan
NEC USA
H. Sandick
Bay Networks
August 1998
A Framework for QoS-based Routing in the Internet
インターネットにおけるQoSベースのルーティングのフレームワーク
Status of this Memo
本文書の状態
This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
このメモは、インターネットコミュニティに情報を提供します。いかなる種類のインターネット標準も規定していません。このメモの配布は無制限です。
Copyright Notice
著作権表示
Copyright (C) The Internet Society (1998). All Rights Reserved.
Copyright（C）The Internet Society（1998）。全著作権所有。
ABSTRACT
概要
QoS-based routing has been recognized as a missing piece in the evolution of QoS-based service offerings in the Internet. This document describes some of the QoS-based routing issues and requirements, and proposes a framework for QoS-based routing in the Internet. This framework is based on extending the current Internet routing model of intra and interdomain routing to support QoS.
QoSベースのルーティングは、インターネットでのQoSベースのサービス提供の進化において欠けているものとして認識されています。このドキュメントでは、QoSベースのルーティングの問題と要件の一部について説明し、インターネットでのQoSベースのルーティングのフレームワークを提案します。このフレームワークは、QoSをサポートするためのドメイン内およびドメイン間ルーティングの現在のインターネットルーティングモデルの拡張に基づいています。
This document proposes a framework for QoS-based routing, with the objective of fostering the development of an Internet-wide solution while encouraging innovations in solving the many problems that arise. QoS-based routing has many complex facets and it is recommended that the following two-pronged approach be employed towards its development:
このドキュメントは、インターネット全体のソリューションの開発を促進しながら、発生する多くの問題を解決するための革新を奨励することを目的として、QoSベースのルーティングのフレームワークを提案します。 QoSベースのルーティングには多くの複雑な側面があります。その開発に向けて、次の2つのアプローチを使用することをお勧めします。
1. Encourage the growth and evolution of novel intradomain QoS-based routing architectures. This is to allow the development of independent, innovative solutions that address the many QoS-based routing issues. Such solutions may be deployed in autonomous systems (ASs), large and small, based on their specific needs.
1. 新しいドメイン内QoSベースのルーティングアーキテクチャの成長と進化を奨励します。これにより、QoSベースのルーティングに関する多くの問題に対処する独立した革新的なソリューションを開発できます。このようなソリューションは、特定のニーズに基づいて、大小の自律システム（AS）に展開できます。
2. Encourage simple, consistent and stable interactions between ASs implementing routing solutions developed as above.
2. 上記のように開発されたルーティングソリューションを実装するAS間のシンプルで一貫した安定した相互作用を奨励します。
This approach follows the traditional separation between intra and interdomain routing. It allows solutions like QOSPF [GKOP98, ZSSC97], Integrated PNNI [IPNNI] or other schemes to be deployed for intradomain routing without any restriction, other than their ability to interact with a common, and perhaps simple, interdomain routing protocol. The need to develop a single, all encompassing solution to the complex problem of QoS-based routing is therefore obviated. As a practical matter, there are many different views on how QoS-based routing should be done. Much overall progress can be made if an opportunity exists for various ideas to be developed and deployed concurrently, while some consensus on the interdomain routing architecture is being developed. Finally, this routing model is perhaps the most practical from an evolution point of view. It is superfluous to say that the eventual success of a QoS-based Internet routing architecture would depend on the ease of evolution.
このアプローチは、ドメイン内ルーティングとドメイン間ルーティングの間の従来の分離に従っています。これにより、QOSPF [GKOP98、ZSSC97]、統合PNNI [IPNNI]などのソリューションを、ドメイン内ルーティング用に、共通の、おそらく単純なドメイン間ルーティングプロトコルと対話する機能以外に、制限なしに展開できます。したがって、QoSベースのルーティングの複雑な問題に対する単一ですべてを網羅するソリューションを開発する必要がなくなります。実際問題として、QoSベースのルーティングをどのように行うべきかについては、さまざまな見方があります。さまざまなアイデアを同時に開発および展開する機会が存在し、ドメイン間ルーティングアーキテクチャに関するコンセンサスが開発されている場合、全体的な進歩は大きくなります。最後に、このルーティングモデルは、進化の観点からはおそらく最も実用的です。 QoSベースのインターネットルーティングアーキテクチャが最終的に成功するかどうかは、進化のしやすさにかかっていると言うのは不必要です。
The aim of this document is to describe the QoS-based routing issues, identify basic requirements on intra and interdomain routing, and describe an extension of the current interdomain routing model to support QoS. It is not an objective of this document to specify the details of intradomain QoS-based routing architectures. This is left up to the various intradomain routing efforts that might follow. Nor is it an objective to specify the details of the interface between reservation protocols such as RSVP and QoS-based routing. The specific interface functionality needed, however, would be clear from the intra and interdomain routing solutions devised. In the intradomain area, the goal is to develop the basic routing requirements while allowing maximum freedom for the development of solutions. In the interdomain area, the objectives are to identify the QoS-based routing functions, and facilitate the development or enhancement of a routing protocol that allows relatively simple interaction between domains.
このドキュメントの目的は、QoSベースのルーティングの問題を説明し、ドメイン内およびドメイン間ルーティングに関する基本的な要件を特定し、QoSをサポートするための現在のドメイン間ルーティングモデルの拡張について説明することです。ドメイン内のQoSベースのルーティングアーキテクチャの詳細を指定することは、このドキュメントの目的ではありません。これは、その後に続く可能性のあるさまざまなドメイン内ルーティング作業に任されています。 RSVPやQoSベースのルーティングなどの予約プロトコル間のインターフェイスの詳細を指定することも目的ではありません。ただし、必要な特定のインターフェイス機能は、考案されたドメイン内およびドメイン間ルーティングソリューションから明らかです。ドメイン内領域の目標は、ソリューションの開発に最大限の自由を与えながら、基本的なルーティング要件を開発することです。ドメイン間領域では、QoSベースのルーティング機能を識別し、ドメイン間の比較的単純な相互作用を可能にするルーティングプロトコルの開発または拡張を容易にすることが目的です。
In the next section, a glossary of relevant terminology is given. In Section 3, the objectives of QoS-based routing are described and the issues that must be dealt with by QoS-based Internet routing efforts are outlined. In Section 4, some requirements on intradomain routing are defined. These requirements are purposely broad, putting few constraints on solution approaches. The interdomain routing model and issues are described in Section 5 and QoS-based multicast routing is discussed in Section 6. The interaction between QoS-based routing and resource reservation protocols is briefly considered in Section 7. Security considerations are listed in Section 8 and related work is described in Section 9. Finally, summary and conclusions are presented in Section 10.
次のセクションでは、関連する用語の用語集を示します。セクション3では、QoSベースのルーティングの目的について説明し、QoSベースのインターネットルーティングの取り組みで対処する必要のある問題について概説します。セクション4では、ドメイン内ルーティングに関するいくつかの要件が定義されています。これらの要件は意図的に広く、ソリューションアプローチにほとんど制約を課していません。ドメイン間ルーティングモデルと問題についてはセクション5で説明し、QoSベースのマルチキャストルーティングについてはセクション6で説明します。QoSベースのルーティングとリソース予約プロトコル間の相互作用については、セクション7で簡単に説明します。セキュリティに関する考慮事項はセクション8に記載されています。作業についてはセクション9で説明します。最後に、要約と結論をセクション10で示します。
The following glossary lists the terminology used in this document and an explanation of what is meant. Some of these terms may have different connotations, but when used in this document, their meaning is as given.
次の用語集に、このドキュメントで使用されている用語とその意味の説明を示します。これらの用語の一部には異なる意味が含まれる場合がありますが、このドキュメントで使用されている場合、それらの意味は記載されているとおりです。
Alternate Path Routing : A routing technique where multiple paths, rather than just the shortest path, between a source and a destination are utilized to route traffic. One of the objectives of alternate path routing is to distribute load among multiple paths in the network.
代替パスルーティング：送信元と宛先の間の最短パスだけでなく、複数のパスを使用してトラフィックをルーティングするルーティング手法。代替パスルーティングの目的の1つは、ネットワーク内の複数のパス間で負荷を分散することです。
Autonomous System (AS): A routing domain which has a common administrative authority and consistent internal routing policy. An AS may employ multiple intradomain routing protocols internally and interfaces to other ASs via a common interdomain routing protocol.
自律システム（AS）：共通の管理権限と一貫した内部ルーティングポリシーを持つルーティングドメイン。 ASは、複数のドメイン内ルーティングプロトコルを内部で使用し、共通のドメイン間ルーティングプロトコルを介して他のASにインターフェイスすることができます。
Source: A host or router that can be identified by a unique unicast IP address.
ソース：一意のユニキャストIPアドレスによって識別できるホストまたはルーター。
Unicast destination: A host or router that can be identified by a unique unicast IP address.
ユニキャスト宛先：一意のユニキャストIPアドレスで識別できるホストまたはルーター。
Multicast destination: A multicast IP address indicating all hosts and routers that are members of the corresponding group.
マルチキャスト宛先：対応するグループのメンバーであるすべてのホストとルーターを示すマルチキャストIPアドレス。
IP flow (or simply "flow"): An IP packet stream from a source to a destination (unicast or multicast) with an associated Quality of Service (QoS) (see below) and higher level demultiplexing information. The associated QoS could be "best-effort".
IPフロー（または単に「フロー」）：送信元から宛先（ユニキャストまたはマルチキャスト）へのIPパケットストリームで、関連するサービス品質（QoS）（以下を参照）とより高いレベルの逆多重化情報。関連するQoSは「ベストエフォート」である可能性があります。
Quality-of-Service (QoS): A set of service requirements to be met by the network while transporting a flow.
サービス品質（QoS）：フローの転送中にネットワークが満たす必要がある一連のサービス要件。
Service class: The definitions of the semantics and parameters of a specific type of QoS.
サービスクラス：特定のタイプのQoSのセマンティクスとパラメーターの定義。
Integrated services: The Integrated Services model for the Internet defined in RFC 1633 allows for integration of QoS services with the best effort services of the Internet. The Integrated Services (IntServ) working group in the IETF has defined two service classes, Controlled Load Service [W97] and Guaranteed Service [SPG97].
統合サービス：RFC 1633で定義されているインターネットの統合サービスモデルでは、QoSサービスをインターネットのベストエフォートサービスと統合できます。 IETFの統合サービス（IntServ）ワーキンググループは、2つのサービスクラス、Controlled Load Service [W97]と保証サービス[SPG97]を定義しています。
RSVP: The ReSerVation Protocol [BZBH97]. A QoS signaling protocol for the Internet.
RSVP：ReSerVationプロトコル[BZBH97]。インターネット用のQoSシグナリングプロトコル。
Path: A unicast or multicast path.
パス：ユニキャストまたはマルチキャストパス。
Unicast path: A sequence of links from an IP source to a unicast IP destination, determined by the routing scheme for forwarding packets.
ユニキャストパス：IPソースからユニキャストIP宛先への一連のリンク。パケットを転送するためのルーティングスキームによって決定されます。
Multicast path (or Multicast Tree): A subtree of the network topology in which all the leaves and zero or more interior nodes are members of the same multicast group. A multicast path may be per-source, in which case the subtree is rooted at the source.
マルチキャストパス（またはマルチキャストツリー）：すべてのリーフと0個以上の内部ノードが同じマルチキャストグループのメンバーであるネットワークトポロジのサブツリー。マルチキャストパスはソースごとにすることができます。その場合、サブツリーはソースをルートとします。
Flow set-up: The act of establishing state in routers along a path to satisfy the QoS requirement of a flow.
フローのセットアップ：フローのQoS要件を満たすために、パスに沿ったルーターで状態を確立する行為。
Crankback: A technique where a flow setup is recursively backtracked along the partial flow path up to the first node that can determine an alternative path to the destination.
クランクバック：フロー設定が部分フローパスに沿って最初のノードまで再帰的にバックトラックされ、宛先への代替パスを決定できる手法。
QoS-based routing: A routing mechanism under which paths for flows are determined based on some knowledge of resource availability in the network as well as the QoS requirement of flows.
QoSベースのルーティング：ネットワーク内のリソースの可用性の知識とフローのQoS要件に基づいてフローのパスが決定されるルーティングメカニズム。
Route pinning: A mechanism to keep a flow path fixed for a duration of time.
ルートの固定：流路を一定時間固定するメカニズム。
Flow Admission Control (FAC): A process by which it is determined whether a link or a node has sufficient resources to satisfy the QoS required for a flow. FAC is typically applied by each node in the path of a flow during flow set-up to check local resource availability.
フローアドミッション制御（FAC）：リンクまたはノードに、フローに必要なQoSを満たすのに十分なリソースがあるかどうかを判断するプロセス。 FACは通常、ローカルリソースの可用性を確認するために、フローのセットアップ中にフローのパス内の各ノードによって適用されます。
Higher-level admission control: A process by which it is determined whether or not a flow set-up should proceed, based on estimates and policy requirements of the overall resource usage by the flow. Higher-level admission control may result in the failure of a flow set-up even when FAC at each node along the flow path indicates resource availability.
上位のアドミッションコントロール：フローによる全体的なリソース使用量の見積もりとポリシー要件に基づいて、フローのセットアップを続行するかどうかを決定するプロセス。より高いレベルのアドミッション制御は、フローパスに沿った各ノードのFACがリソースの可用性を示している場合でも、フローのセットアップに失敗することがあります。
Routing deployed in today's Internet is focused on connectivity and typically supports only one type of datagram service called "best effort" [WC96]. Current Internet routing protocols, e.g. OSPF, RIP, use "shortest path routing", i.e. routing that is optimized for a single arbitrary metric, administrative weight or hop count. These routing protocols are also "opportunistic," using the current shortest path or route to a destination. Alternate paths with acceptable but non-optimal cost can not be used to route traffic (shortest path routing protocols do allow a router to alternate among several equal cost paths to a destination).
今日のインターネットで展開されているルーティングは接続性に焦点を当てており、通常は「ベストエフォート」と呼ばれる1種類のデータグラムサービスのみをサポートします[WC96]。現在のインターネットルーティングプロトコル。 OSPF、RIP、「最短経路ルーティング」、つまり単一の任意のメトリック、管理上の重み、またはホップカウント用に最適化されたルーティングを使用します。これらのルーティングプロトコルも「便宜的」であり、宛先への現在の最短パスまたはルートを使用します。許容できるが最適ではないコストの代替パスを使用してトラフィックをルーティングすることはできません（最短パスルーティングプロトコルでは、宛先への複数の等コストパス間でルーターを切り替えることができます）。
QoS-based routing must extend the current routing paradigm in three basic ways. First, to support traffic using integrated-services class of services, multiple paths between node pairs will have to be calculated. Some of these new classes of service will require the distribution of additional routing metrics, e.g. delay, and available bandwidth. If any of these metrics change frequently, routing updates can become more frequent thereby consuming network bandwidth and router CPU cycles.
QoSベースのルーティングは、3つの基本的な方法で現在のルーティングパラダイムを拡張する必要があります。まず、統合サービスサービスクラスを使用してトラフィックをサポートするには、ノードペア間の複数のパスを計算する必要があります。これらの新しいサービスクラスの一部では、追加のルーティングメトリックの配布が必要になります。遅延、および利用可能な帯域幅。これらのメトリックのいずれかが頻繁に変更されると、ルーティングの更新が頻繁になり、ネットワーク帯域幅とルーターのCPUサイクルが消費される可能性があります。
Second, today's opportunistic routing will shift traffic from one path to another as soon as a "better" path is found. The traffic will be shifted even if the existing path can meet the service requirements of the existing traffic. If routing calculation is tied to frequently changing consumable resources (e.g. available bandwidth) this change will happen more often and can introduce routing oscillations as traffic shifts back and forth between alternate paths. Furthermore, frequently changing routes can increase the variation in the delay and jitter experienced by the end users.
第2に、今日の日和見ルーティングは、「より良い」パスが見つかるとすぐにトラフィックを1つのパスから別のパスにシフトします。既存のパスが既存のトラフィックのサービス要件を満たしている場合でも、トラフィックはシフトされます。ルーティングの計算が頻繁に変化する消費可能なリソース（使用可能な帯域幅など）に関連付けられている場合、この変更はより頻繁に発生し、トラフィックが代替パス間を行き来するときにルーティングの変動を引き起こす可能性があります。さらに、ルートを頻繁に変更すると、エンドユーザーが経験する遅延とジッタの変動が大きくなる可能性があります。
Third, as mentioned earlier, today's optimal path routing algorithms do not support alternate routing. If the best existing path cannot admit a new flow, the associated traffic cannot be forwarded even if an adequate alternate path exists.
第3に、前述のように、今日の最適パスルーティングアルゴリズムは代替ルーティングをサポートしていません。既存の最適なパスが新しいフローを許可できない場合、適切な代替パスが存在していても、関連するトラフィックを転送できません。
It is important to understand the difference between QoS-based routing and resource reservation. While resource reservation protocols such as RSVP [BZBH97] provide a method for requesting and reserving network resources, they do not provide a mechanism for determining a network path that has adequate resources to accommodate the requested QoS. Conversely, QoS-based routing allows the determination of a path that has a good chance of accommodating the requested QoS, but it does not include a mechanism to reserve the required resources.
QoSベースのルーティングとリソース予約の違いを理解することが重要です。 RSVP [BZBH97]などのリソース予約プロトコルは、ネットワークリソースを要求および予約する方法を提供しますが、要求されたQoSに対応する十分なリソースを持つネットワークパスを決定するメカニズムを提供しません。逆に、QoSベースのルーティングでは、要求されたQoSに対応できる可能性が高いパスを決定できますが、必要なリソースを予約するメカニズムは含まれていません。
Consequently, QoS-based routing is usually used in conjunction with some form of resource reservation or resource allocation mechanism. Simple forms of QoS-based routing have been used in the past for Type of Service (TOS) routing [M98]. In the case of OSPF, a different shortest-path tree can be computed for each of the 8 TOS values in the IP header [ISI81]. Such mechanisms can be used to select specially provisioned paths but do not completely assure that resources are not overbooked along the path. As long as strict resource management and control are not needed, mechanisms such as TOS-based routing are useful for separating whole classes of traffic over multiple routes. Such mechanisms might work well with the emerging Differential Services efforts [BBCD98].
その結果、QoSベースのルーティングは通常、何らかの形のリソース予約またはリソース割り当てメカニズムと組み合わせて使用されます。 QoSベースのルーティングの単純な形式は、サービスの種類（TOS）ルーティング[M98]にこれまで使用されてきました。 OSPFの場合、IPヘッダー内の8つのTOS値[ISI81]ごとに異なる最短パスツリーを計算できます。このようなメカニズムは、特別にプロビジョニングされたパスを選択するために使用できますが、リソースがパスに沿ってオーバーブッキングされないことを完全には保証しません。厳密なリソース管理と制御が不要である限り、TOSベースのルーティングなどのメカニズムは、複数のルートでトラフィックのクラス全体を分離するのに役立ちます。このようなメカニズムは、新たな差別化サービスの取り組み[BBCD98]でうまく機能する可能性があります。
Combining a resource reservation protocol with QoS-based routing allows fine control over the route and resources at the cost of additional state and setup time. For example, a protocol such as RSVP may be used to trigger QoS-based routing calculations to meet the needs of a specific flow.
リソース予約プロトコルとQoSベースのルーティングを組み合わせることにより、追加の状態とセットアップ時間を犠牲にして、ルートとリソースを細かく制御できます。たとえば、RSVPなどのプロトコルを使用して、QoSベースのルーティング計算をトリガーし、特定のフローのニーズを満たすことができます。
Under QoS-based routing, paths for flows would be determined based on some knowledge of resource availability in the network, as well as the QoS requirement of flows. The main objectives of QoS-based routing are:
QoSベースのルーティングでは、フローのパスは、ネットワークでのリソースの可用性の知識とフローのQoS要件に基づいて決定されます。 QoSベースのルーティングの主な目的は次のとおりです。
1. Dynamic determination of feasible paths: QoS-based routing can determine a path, from among possibly many choices, that has a good chance of accommodating the QoS of the given flow. Feasible path selection may be subject to policy constraints, such as path cost, provider selection, etc.
1. 実行可能なパスの動的な決定：QoSベースのルーティングは、可能性のある多くの選択肢の中から、特定のフローのQoSに対応できる可能性が高いパスを決定できます。実現可能なパスの選択は、パスのコスト、プロバイダーの選択などのポリシーの制約の影響を受ける場合があります。
2. Optimization of resource usage: A network state-dependent QoS-based routing scheme can aid in the efficient utilization of network resources by improving the total network throughput. Such a routing scheme can be the basis for efficient network engineering.
2. リソース使用量の最適化：ネットワーク状態に依存するQoSベースのルーティングスキームは、ネットワークスループット全体を改善することにより、ネットワークリソースの効率的な利用に役立ちます。このようなルーティングスキームは、効率的なネットワークエンジニアリングの基礎となります。
3. Graceful performance degradation: State-dependent routing can compensate for transient inadequacies in network engineering (e.g., during focused overload conditions), giving better throughput and a more graceful performance degradation as compared to a state-insensitive routing scheme [A84].
3. 優雅なパフォーマンスの低下：状態に依存するルーティングは、ネットワークエンジニアリングの一時的な不十分さを補うことができ（たとえば、過負荷状態が集中しているとき）、状態に依存しないルーティングスキーム[A84]と比較して、より優れたスループットとより優雅なパフォーマンスの低下をもたらします。
QoS-based routing in the Internet, however, raises many issues:
ただし、インターネットでのQoSベースのルーティングには多くの問題があります。
- How do routers determine the QoS capability of each outgoing link and reserve link resources? Note that some of these links may be virtual, over ATM networks and others may be broadcast multi-access links.
- ルーターは各発信リンクのQoS機能をどのように決定し、リンクリソースを予約しますか？これらのリンクには、ATMネットワークを介した仮想リンクや、ブロードキャストマルチアクセスリンクが含まれる場合があります。
- What is the granularity of routing decision (i.e., destination-based, source and destination-based, or flow-based)?
- ルーティング決定の細分性は何ですか（つまり、宛先ベース、送信元と宛先ベース、またはフローベース）？
- What routing metrics are used and how are QoS-accommodating paths computed for unicast flows?
- どのルーティングメトリックが使用され、ユニキャストフローに対してQoS対応パスがどのように計算されますか？
- How are QoS-accommodating paths computed for multicast flows with different reservation styles and receiver heterogeneity?
- 予約スタイルと受信機の異質性が異なるマルチキャストフローのQoS収容パスはどのように計算されますか？
- What are the performance objectives while computing QoS-based paths?
- QoSベースのパスを計算する際のパフォーマンス目標は何ですか？
- What are the administrative control issues?
- 管理統制の問題は何ですか？
- What factors affect the routing overheads?, and
- ルーティングのオーバーヘッドに影響を与える要因は何ですか？、および
- How is scalability achieved?
- スケーラビリティはどのようにして達成されますか？
Some of these issues are discussed briefly next. Interdomain routing is discussed in Section 5.
次に、これらの問題のいくつかについて簡単に説明します。ドメイン間ルーティングについては、セクション5で説明します。
To determine whether the QoS requirements of a flow can be accommodated on a link, a router must be able to determine the QoS available on the link. It is still an open issue as to how the QoS availability is determined for broadcast multiple access links (e.g., Ethernet). A related problem is the reservation of resources over such links. Solutions to these problems are just emerging [GPSS98].
フローのQoS要件がリンクに対応できるかどうかを判断するには、ルーターがリンクで利用可能なQoSを判断できる必要があります。ブロードキャストマルチアクセスリンク（イーサネットなど）のQoS可用性がどのように決定されるかについては、未解決の問題です。関連する問題は、そのようなリンクを介したリソースの予約です。これらの問題の解決策は、最近出現しました[GPSS98]。
Similar problems arise when a router is connected to a large non-broadcast multiple access network, such as ATM. In this case, if the destination of a flow is outside the ATM network, the router may have multiple egress choices. Furthermore, the QoS availability on the ATM paths to each egress point may be different. The issues then are,
ルータがATMなどの大規模な非ブロードキャストマルチアクセスネットワークに接続されている場合にも、同様の問題が発生します。この場合、フローの宛先がATMネットワークの外部にある場合、ルーターには複数の出力の選択肢がある可能性があります。さらに、各出口ポイントへのATMパスでのQoSの可用性は異なる場合があります。次に問題は、
o how does a router determine all the egress choices across the ATM network? o how does it determine what QoS is available over the path to each egress point?, and o what QoS value does the router advertise for the ATM link.
o ルータは、ATMネットワーク全体のすべての出力の選択をどのように決定しますか？ o各出力ポイントへのパスを介して利用可能なQoSをどのように決定しますか？oルータがATMリンクにアドバタイズするQoS値
Typically, IP routing over ATM (e.g., NHRP) allows the selection of a single egress point in the ATM network, and the procedure does not incorporate any knowledge of the QoS required over the path. An approach like I-PNNI [IPNNI] would be helpful here, although it introduces some complexity.
通常、ATM上のIPルーティング（NHRPなど）では、ATMネットワーク内の単一の出力ポイントを選択できます。この手順では、パスに必要なQoSの知識は組み込まれていません。 I-PNNI [IPNNI]のようなアプローチは、多少複雑になりますが、ここでは役立ちます。
An additional problem with resource reservation is how to determine what resources have already been allocated to a multicast flow. The availability of this information during path computation improves the chances of finding a path to add a new receiver to a multicast flow. QOSPF [ZSSC97] handles this problem by letting routers broadcast reserved resource information to other routers in their area.
リソース予約に関する追加の問題は、マルチキャストフローにすでに割り当てられているリソースを判別する方法です。パス計算中にこの情報を利用できると、新しいフローをマルチキャストフローに追加するためのパスを見つける可能性が高くなります。 QOSPF [ZSSC97]は、ルーターに予約されたリソース情報をそのエリア内の他のルーターにブロードキャストさせることで、この問題を処理します。
Alternate path routing [ZES97] deals with this issue by using probe messages to find a path with sufficient resources. Path QoS Computation (PQC) method, proposed in [GOA97], propagates bandwidth allocation information in RSVP PATH messages. A router receiving the PATH message gets an indication of the resource allocation only on those links in the path to itself from the source. Allocation for the same flow on other remote branches of the multicast tree is not available. Thus, the PQC method may not be sufficient to find feasible QoS-accommodating paths to all receivers.
代替パスルーティング[ZES97]は、プローブメッセージを使用して十分なリソースを持つパスを見つけることにより、この問題に対処します。 [GOA97]で提案されたパスQoS計算（PQC）メソッドは、RSVP PATHメッセージで帯域幅割り当て情報を伝達します。 PATHメッセージを受信したルーターは、ソースから自身へのパスにあるリンク上のリソース割り当てのみを示します。マルチキャストツリーの他のリモートブランチ上の同じフローへの割り当ては使用できません。したがって、PQC方法は、すべての受信機への実現可能なQoS収容パスを見つけるのに十分ではない場合があります。
Routing in the Internet is currently based only on the destination address of a packet. Many multicast routing protocols require routing based on the source AND destination of a packet. The Integrated Services architecture and RSVP allow QoS determination for an individual flow between a source and a destination. This set of routing granularities presents a problem for QoS routing solutions.
現在、インターネットでのルーティングは、パケットの宛先アドレスのみに基づいています。多くのマルチキャストルーティングプロトコルでは、パケットの送信元と宛先に基づいたルーティングが必要です。統合サービスアーキテクチャとRSVPにより、送信元と宛先の間の個々のフローのQoS決定が可能になります。この一連のルーティングの細分性は、QoSルーティングソリューションに問題をもたらします。
If routing based only on destination address is considered, then an intermediate router will route all flows between different sources and a given destination along the same path. This is acceptable if the path has adequate capacity but a problem arises if there are multiple flows to a destination that exceed the capacity of the link.
宛先アドレスのみに基づくルーティングを検討する場合、中間ルーターは、異なるソースと特定の宛先間のすべてのフローを同じパスに沿ってルーティングします。パスに十分な容量がある場合はこれで問題ありませんが、リンクの容量を超える宛先へのフローが複数ある場合は問題が発生します。
One version of QOSPF [ZSSC97] determines QoS routes based on source and destination address. This implies that all traffic between a given source and destination, regardless of the flow, will travel down the same route. Again, the route must have capacity for all the QoS traffic for the source/destination pair. The amount of routing state also increases since the routing tables must include source/destination pairs instead of just the destination.
QOSPF [ZSSC97]の1つのバージョンは、送信元アドレスと宛先アドレスに基づいてQoSルートを決定します。これは、フローに関係なく、特定の送信元と宛先の間のすべてのトラフィックが同じルートを通過することを意味します。この場合も、ルートには、送信元/宛先ペアのすべてのQoSトラフィック用の容量が必要です。ルーティングテーブルには宛先だけでなく送信元/宛先のペアを含める必要があるため、ルーティング状態の量も増加します。
The best granularity is found when routing is based on individual flows but this incurs a tremendous cost in terms of the routing state. Each QoS flow can be routed separately between any source and destination. PQC [GOA97] and alternate path routing [ZES97], are examples of solutions which operate at the flow level.
ルーティングが個々のフローに基づいている場合に最良の細分性が見つかりますが、これによりルーティングの状態の面で莫大なコストが発生します。各QoSフローは、任意の送信元と宛先の間で個別にルーティングできます。 PQC [GOA97]と代替パスルーティング[ZES97]は、フローレベルで動作するソリューションの例です。
Both source/destination and flow-based routing may be susceptible to packet looping under hop-by-hop forwarding. Suppose a node along a flow or source/destination-based path loses the state information for the flow. Also suppose that the flow-based route is different from the regular destination-based route. The potential then exists for a routing loop to form when the node forwards a packet belonging to the flow using its destination-based routing table to a node that occurs earlier on the flow-based path. This is because the latter node may use its flow-based routing table to forward the packet again to the former and this can go on indefinitely.
送信元/宛先とフローベースのルーティングはどちらも、ホップバイホップ転送でのパケットループの影響を受けやすい場合があります。フローまたは送信元/宛先ベースのパスに沿ったノードがフローの状態情報を失うと仮定します。また、フローベースのルートが通常の宛先ベースのルートとは異なると仮定します。ノードが宛先ベースのルーティングテーブルを使用してフローに属するパケットを、フローベースのパスで以前に発生したノードに転送するときに、ルーティングループが形成される可能性があります。これは、後者のノードがフローベースのルーティングテーブルを使用してパケットを前者に再度転送し、これが無期限に続く可能性があるためです。
There are some considerations in defining suitable link and node metrics [WC96]. First, the metrics must represent the basic network properties of interest. Such metrics include residual bandwidth, delay and jitter. Since the flow QoS requirements have to be mapped onto path metrics, the metrics define the types of QoS guarantees the network can support. Alternatively, QoS-based routing cannot support QoS requirements that cannot be meaningfully mapped onto a reasonable combination of path metrics. Second, path computation based on a metric or a combination of metrics must not be too complex as to render them impractical. In this regard, it is worthwhile to note that path computation based on certain combinations of metrics (e.g., delay and jitter) is theoretically hard. Thus, the allowable combinations of metrics must be determined while taking into account the complexity of computing paths based on these metrics and the QoS needs of flows. A common strategy to allow flexible combinations of metrics while at the same time reduce the path computation complexity is to utilize "sequential filtering". Under this approach, a combination of metrics is ordered in some fashion, reflecting the importance of different metrics (e.g., cost followed by delay, etc.). Paths based on the primary metric are computed first (using a simple algorithm, e.g., shortest path) and a subset of them are eliminated based on the secondary metric and so forth until a single path is found. This is an approximation technique and it trades off global optimality for path computation simplicity (The filtering technique may be simpler, depending on the set of metrics used. For example, with bandwidth and cost as metrics, it is possible to first eliminate the set of links that do not have the requested bandwidth and then compute the least cost path using the remaining links.)
適切なリンクとノードのメトリックを定義するには、いくつかの考慮事項があります[WC96]。まず、メトリックは、対象となる基本的なネットワークプロパティを表す必要があります。このようなメトリックには、残留帯域幅、遅延、ジッターが含まれます。フローQoS要件はパスメトリックにマッピングする必要があるため、メトリックはネットワークがサポートできるQoS保証のタイプを定義します。または、QoSベースのルーティングは、パスメトリックの合理的な組み合わせに意味のある形でマッピングできないQoS要件をサポートできません。第二に、メトリックまたはメトリックの組み合わせに基づくパス計算は、それらを非実用的にするほど複雑にしてはなりません。この点で、メトリックの特定の組み合わせ（遅延やジッターなど）に基づくパスの計算は理論的に難しいことに注意してください。したがって、これらのメトリックに基づく計算パスの複雑さとフローのQoSニーズを考慮しながら、メトリックの許容可能な組み合わせを決定する必要があります。メトリックの柔軟な組み合わせを可能にすると同時に、パス計算の複雑さを軽減するための一般的な戦略は、「順次フィルタリング」を利用することです。このアプローチでは、メトリックの組み合わせが何らかの方法で順序付けされ、さまざまなメトリックの重要性を反映しています（たとえば、コストの後に遅延が続くなど）。プライマリメトリックに基づくパスが最初に計算され（最短パスなどの単純なアルゴリズムを使用）、それらのサブセットはセカンダリメトリックに基づいて削除され、単一のパスが見つかるまで続きます。これは近似手法であり、パスの計算を単純にするためにグローバルな最適性とトレードオフします（使用するメトリックのセットに応じて、フィルタリング手法はより単純になる場合があります。たとえば、帯域幅とコストをメトリックとして使用すると、最初に要求された帯域幅を持たないリンク、残りのリンクを使用して最小コストパスを計算）
Now, once suitable link and node metrics are defined, a uniform representation of them is required across independent domains - employing possibly different routing schemes - in order to derive path metrics consistently (path metrics are obtained by the composition of link and node metrics). Encoding of the maximum, minimum, range, and granularity of the metrics are needed. Also, the definitions of comparison and accumulation operators are required. In addition, suitable triggers must be defined for indicating a significant change from a minor change. The former will cause a routing update to be generated. The stability of the QoS routes would depend on the ability to control the generation of updates. With interdomain routing, it is essential to obtain a fairly stable view of the interconnection among the ASs.
現在、適切なリンクおよびノードメトリックが定義されたら、パスメトリックを一貫して導出するために、独立したドメイン間でそれらの統一された表現が必要です-異なるルーティングスキームを使用する必要があります（パスメトリックはリンクおよびノードメトリックの構成によって取得されます）。メトリックの最大、最小、範囲、および粒度のエンコードが必要です。また、比較演算子と累積演算子の定義も必要です。さらに、小さな変更からの大きな変更を示すために、適切なトリガーを定義する必要があります。前者はルーティング更新を生成させます。 QoSルートの安定性は、更新の生成を制御する機能に依存します。ドメイン間ルーティングでは、AS間の相互接続のかなり安定したビューを取得することが不可欠です。
A hierarchy can be defined among various classes of service based on the degree to which traffic from one class can potentially degrade service of traffic from lower classes that traverse the same link. In this hierarchy, guaranteed constant bit rate traffic is at the top and "best-effort" datagram traffic at the bottom. Classes providing service higher in the hierarchy impact classes providing service in lower levels. The same situation is not true in the other direction. For example, a datagram flow cannot affect a real-time service. Thus, it may be necessary to distribute and update different metrics for each type of service in the worst case. But, several advantages result by identifying a single default metric. For example, one could derive a single metric combining the availability of datagram and real-time service over a common substrate.
階層は、1つのクラスからのトラフィックが、同じリンクを通過する下位クラスからのトラフィックのサービスを潜在的に低下させる可能性に基づいて、さまざまなサービスクラス間で定義できます。この階層では、保証された固定ビットレートのトラフィックが一番上にあり、「ベストエフォート」データグラムトラフィックが一番下にあります。階層の上位でサービスを提供するクラスは、下位レベルでサービスを提供するクラスに影響を与えます。同じ状況は他の方向には当てはまりません。たとえば、データグラムフローがリアルタイムサービスに影響を与えることはありません。したがって、最悪の場合、サービスのタイプごとに異なるメトリックを配布および更新することが必要になる場合があります。ただし、単一のデフォルトメトリックを識別することにより、いくつかの利点が得られます。たとえば、共通の基盤でのデータグラムの可用性とリアルタイムサービスを組み合わせた単一のメトリックを導出できます。
A delay-sensitive metric is probably the most obvious type of metric suitable for datagram flows. However, it requires careful analysis to avoid instabilities and to reduce storage and bandwidth requirements. For example, a recursive filtering technique based on a simple and efficient weighted averaging algorithm [NC94] could be used. This filter is used to stabilize the metric. While it is adequate for smoothing most loading patterns, it will not distinguish between patterns consisting of regular bursts of traffic and random loading. Among other stabilizing tools, is a minimum time between updates that can help filter out high-frequency oscillations.
遅延の影響を受けやすいメトリックは、おそらくデータグラムフローに適した最も明白なタイプのメトリックです。ただし、不安定さを回避し、ストレージと帯域幅の要件を減らすには、慎重な分析が必要です。たとえば、シンプルで効率的な加重平均アルゴリズム[NC94]に基づく再帰的なフィルタリング手法を使用できます。このフィルターは、メトリックを安定させるために使用されます。ほとんどの負荷パターンを平滑化するには十分ですが、トラフィックの通常のバーストとランダムな負荷からなるパターンを区別しません。他の安定化ツールの中で、高周波振動をフィルターで取り除くのに役立つ更新間の最小時間です。
In real-time quality-of-service, delay variation is generally more critical than delay as long as the delay is not too high. Clearly, voice-based applications cannot tolerate more than a certain level of delay. The condition of varying delays may be expected to a greater degree in a shared medium environment with datagrams, than in a network implemented over a switched substrate. Routing a real-time flow therefore reduces to an exercise in allocating the required network resources while minimizing fragmentation of bandwidth. The resulting situation is a bandwidth-limited minimum hop path from a source to the destination. In other words, the router performs an ordered search through paths of increasing hop count until it finds one that meets all the bandwidth needs of the flow. To reduce contention and the probability of false probes (due to inaccuracy in route tables), the router could select a path randomly from a "window" of paths which meet the needs of the flow and satisfy one of three additional criteria: best-fit, first-fit or worst-fit. Note that there is a similarity between the allocation of bandwidth and the allocation of memory in a multiprocessing system. First-fit seems to be appropriate for a system with a high real-time flow arrival rates; and worst-fit is ideal for real-time flows with high holding times. This rather nonintuitive result was shown in [NC94].
リアルタイムのサービス品質では、遅延が高すぎない限り、遅延変動は一般に遅延よりも重要です。明らかに、音声ベースのアプリケーションは、一定レベル以上の遅延を許容できません。変化する遅延の状態は、スイッチド基板上に実装されたネットワークよりも、データグラムを使用した共有媒体環境でより大きく期待できます。したがって、リアルタイムフローのルーティングは、帯域幅の断片化を最小限に抑えながら、必要なネットワークリソースの割り当てを実行することになります。結果として生じる状況は、送信元から宛先への帯域幅が制限された最小ホップパスです。つまり、ルーターは、フローのすべての帯域幅のニーズを満たすパスが見つかるまで、ホップカウントが増加するパスを順番に検索します。 （ルートテーブルの不正確さによる）競合と誤ったプローブの確率を減らすために、ルーターは、フローのニーズを満たし、3つの追加基準の1つを満たすパスの「ウィンドウ」からランダムにパスを選択できます。 、最初の適合または最悪の適合。マルチプロセッシングシステムにおける帯域幅の割り当てとメモリの割り当てには類似点があることに注意してください。 First-fitは、リアルタイムのフロー到着率が高いシステムに適しているようです。ワーストフィットは、保持時間が長いリアルタイムフローに最適です。このかなり直感的でない結果は[NC94]に示されました。
Path computation by itself is merely a search technique, e.g., Shortest Path First (SPF) is a search technique based on dynamic programming. The usefulness of the paths computed depends to a large extent on the metrics used in evaluating the cost of a path with respect to a flow.
経路計算自体は単なる検索手法です。たとえば、最短経路優先（SPF）は動的プログラミングに基づく検索手法です。計算されたパスの有用性は、フローに関するパスのコストの評価に使用されるメトリックに大きく依存します。
Each link considered by the path computation engine must be evaluated against the requirements of the flow, i.e., the cost of providing the services required by the flow must be estimated with respect to the capabilities of the link. This requires a uniform method of combining features such as delay, bandwidth, priority and other service features. Furthermore, the costs must reflect the lost opportunity of using each link after routing the flow.
パス計算エンジンによって考慮される各リンクは、フローの要件に対して評価する必要があります。つまり、フローが必要とするサービスを提供するコストは、リンクの機能に関して見積もる必要があります。これには、遅延、帯域幅、優先度、その他のサービス機能などの機能を組み合わせるための統一された方法が必要です。さらに、コストは、フローのルーティング後に各リンクを使用する機会の喪失を反映する必要があります。
One common objective during path computation is to improve the total network throughput. In this regard, merely routing a flow on any path that accommodates its QoS requirement is not a good strategy. In fact, this corresponds to uncontrolled alternate routing [SD95] and may adversely impact performance at higher traffic loads. It is therefore necessary to consider the total resource allocation for a flow along a path, in relation to available resources, to determine whether or not the flow should be routed on the path. Such a mechanism is referred to in this document as "higher level admission control". The goal of this is to ensure that the "cost" incurred by the network in routing a flow with a given QoS is never more than the revenue gained. The routing cost in this regard may be the lost revenue in potentially blocking other flows that contend for the same resources. The formulation of the higher level admission control strategy, with suitable administrative hooks and with fairness to all flows desiring entry to the network, is an issue. The fairness problem arises because flows with smaller reservations tend to be more successfully routed than flows with large reservations, for a given engineered capacity. To guarantee a certain level of acceptance rate for "larger" flows, without over-engineering the network, requires a fair higher level admission control mechanism. The application of higher level admission control to multicast routing is discussed later.
パス計算時の一般的な目的の1つは、ネットワーク全体のスループットを向上させることです。この点で、QoS要件に対応する任意のパスでフローをルーティングするだけでは適切な戦略ではありません。実際、これは制御されていない代替ルーティング[SD95]に対応し、より高いトラフィック負荷でパフォーマンスに悪影響を与える可能性があります。したがって、利用可能なリソースに関連して、パスに沿ったフローの総リソース割り当てを検討して、フローをパスにルーティングする必要があるかどうかを判断する必要があります。このようなメカニズムは、このドキュメントでは「上位レベルのアドミッションコントロール」と呼ばれています。この目標は、特定のQoSを使用してフローをルーティングする際にネットワークで発生する「コスト」が、獲得した収益を超えないようにすることです。この点でのルーティングコストは、同じリソースをめぐって競合する他のフローを潜在的にブロックすることで収益が失われる可能性があります。適切な管理フックと、ネットワークへのエントリを必要とするすべてのフローに対する公平性を備えた、より高いレベルのアドミッションコントロール戦略の策定が問題です。与えられた設計された容量に対して、予約が小さいフローは、予約が大きいフローよりもルーティングが成功する傾向があるため、公平性の問題が発生します。ネットワークを過度に設計せずに、「より大きな」フローの特定のレベルの受け入れ率を保証するには、かなり高いレベルのアドミッション制御メカニズムが必要です。マルチキャストルーティングへの高レベルのアドミッション制御の適用については、後で説明します。
There are several administrative control issues. First, within an AS employing state-dependent routing, administrative control of routing behavior may be necessary. One example discussed earlier was higher level admission control. Some others are described in this section. Second, the control of interdomain routing based on policy is an issue. The discussion of interdomain routing is defered to Section 5.
いくつかの管理上の制御問題があります。まず、状態依存ルーティングを採用するAS内では、ルーティング動作の管理制御が必要になる場合があります。前述の1つの例は、より高いレベルのアドミッションコントロールでした。このセクションでは、その他のいくつかについて説明します。次に、ポリシーに基づくドメイン間ルーティングの制御が問題になります。ドメイン間ルーティングについては、セクション5で説明します。
Two areas that need administrative control, in addition to appropriate routing mechanisms, are handling flow priority with preemption, and resource allocation for multiple service classes.
適切なルーティングメカニズムに加えて、管理制御を必要とする2つの領域は、プリエンプションを使用したフローの優先順位の処理と、複数のサービスクラスのリソース割り当てです。
If there are critical flows that must be accorded higher priority than other types of flows, a mechanism must be implemented in the network to recognize flow priorities. There are two aspects to prioritizing flows. First, there must be a policy to decide how different users are allowed to set priorities for flows they originate. The network must be able to verify that a given flow is allowed to claim a priority level signaled for it. Second, the routing scheme must ensure that a path with the requested QoS will be found for a flow with a probability that increases with the priority of the flow. In other words, for a given network load, a high priority flow should be more likely to get a certain QoS from the network than a lower priority flow requesting the same QoS. Routing procedures for flow prioritization can be complex. Identification and evaluation of different procedures are areas that require investigation.
他のタイプのフローよりも高い優先度を与える必要がある重要なフローがある場合、フローの優先度を認識するメカニズムをネットワークに実装する必要があります。フローの優先順位付けには2つの側面があります。まず、異なるユーザーがどのようにしてそれらが発信するフローの優先順位を設定できるかを決定するポリシーが必要です。ネットワークは、特定のフローがそのために通知された優先レベルを要求できることを確認できる必要があります。第2に、ルーティングスキームは、フローの優先度とともに増加する確率で、要求されたQoSを持つパスがフローに対して確実に見つかるようにする必要があります。つまり、特定のネットワーク負荷に対して、優先度の高いフローは、同じQoSを要求する優先度の低いフローよりも、ネットワークから特定のQoSを取得する可能性が高くなります。フローの優先順位付けのルーティング手順は複雑になる場合があります。さまざまな手順の識別と評価は、調査が必要な領域です。
If there are multiple service classes, it is necessary to engineer a network to carry the forecasted traffic demands of each class. To do this, router and link resources may be logically partitioned among various service classes. It is desirable to have dynamic partitioning whereby unused resources in various partitions are dynamically shifted to other partitions on demand [ACFH92]. Dynamic sharing, however, must be done in a controlled fashion in order to prevent traffic under some service class from taking up more resources than what was engineered for it for prolonged periods of time. The design of such a resource sharing scheme, and its incorporation into the QoS-based routing scheme are significant issues.
複数のサービスクラスがある場合は、各クラスの予測トラフィック需要を伝送するようにネットワークを設計する必要があります。これを行うには、ルーターとリンクのリソースをさまざまなサービスクラス間で論理的に分割します。さまざまなパーティション内の未使用のリソースをオンデマンドで他のパーティションに動的にシフトする動的パーティション化が望ましいです[ACFH92]。ただし、動的共有は、一部のサービスクラスでのトラフィックが長期間にわたって設計されたものよりも多くのリソースを占有しないように、制御された方法で行う必要があります。このようなリソース共有スキームの設計と、QoSベースのルーティングスキームへの組み込みは、重要な問題です。
QoS-based multicast routing is an important problem, especially if the notion of higher level admission control is included. The dynamism in the receiver set allowed by IP multicast, and receiver heterogeneity add to the problem. With straightforward implementation of distributed heuristic algorithms for multicast path computation [W88, C91], the difficulty is essentially one of scalability. To accommodate QoS, multicast path computation at a router must have knowledge of not only the id of subnets where group members are present, but also the identity of branches in the existing tree. In other words, routers must keep flow-specific state information. Also, computing optimal shared trees based on the shared reservation style [BZBH97], may require new algorithms. Multicast routing is discussed in some detail in Section 6.
QoSベースのマルチキャストルーティングは、特に高レベルのアドミッション制御の概念が含まれている場合、重要な問題です。 IPマルチキャストで許容されるレシーバーセットのダイナミズムとレシーバーの不均一性が問題を追加します。マルチキャストパス計算のための分散ヒューリスティックアルゴリズムの単純な実装[W88、C91]の場合、難しさは本質的にスケーラビリティの1つです。 QoSに対応するには、ルーターでのマルチキャストパス計算は、グループメンバーが存在するサブネットのIDだけでなく、既存のツリー内のブランチのIDも知っている必要があります。つまり、ルーターはフロー固有の状態情報を保持する必要があります。また、共有予約スタイル[BZBH97]に基づいて最適な共有ツリーを計算するには、新しいアルゴリズムが必要になる場合があります。マルチキャストルーティングについては、セクション6で詳しく説明します。
The overheads incurred by a routing scheme depend on the type of the routing scheme, as well as the implementation. There are three types of overheads to be considered: computation, storage and communication. It is necessary to understand the implications of choosing a routing mechanism in terms of these overheads.
ルーティングスキームによって発生するオーバーヘッドは、ルーティングスキームのタイプと実装によって異なります。考慮すべきオーバーヘッドには、計算、ストレージ、通信の3つのタイプがあります。これらのオーバーヘッドの観点からルーティングメカニズムを選択することの影響を理解する必要があります。
For example, considering link state routing, the choice of the update propagation mechanism is important since network state is dynamic and changes relatively frequently. Specifically, a flooding mechanism would result in many unnecessary message transmissions and processing. Alternative techniques, such as tree-based forwarding [R96], have to be considered. A related issue is the quantization of state information to prevent frequent updating of dynamic state. While coarse quantization reduces updating overheads, it may affect the performance of the routing scheme. The tradeoff has to be carefully evaluated. QoS-based routing incurs certain overheads during flow establishment, for example, computing a source route. Whether this overhead is disproportionate compared to the length of the sessions is an issue. In general, techniques for the minimization of routing-related overheads during flow establishment must be investigated. Approaches that are useful include pre-computation of routes, caching recently used routes, and TOS routing based on hints in packets (e.g., the TOS field).
たとえば、リンク状態ルーティングを考えると、ネットワーク状態は動的で比較的頻繁に変化するため、更新伝播メカニズムの選択は重要です。具体的には、フラッディングメカニズムにより、多くの不要なメッセージの送信と処理が発生します。ツリーベースの転送[R96]などの代替手法を検討する必要があります。関連する問題は、動的状態の頻繁な更新を防ぐための状態情報の量子化です。粗い量子化は更新のオーバーヘッドを減らしますが、ルーティングスキームのパフォーマンスに影響を与える可能性があります。トレードオフは慎重に評価する必要があります。 QoSベースのルーティングでは、ソースルートの計算など、フローの確立中に特定のオーバーヘッドが発生します。このオーバーヘッドがセッションの長さに比べて不釣り合いであるかどうかは問題です。一般に、フロー確立中のルーティング関連のオーバーヘッドを最小限に抑えるための手法を調査する必要があります。有用なアプローチには、ルートの事前計算、最近使用されたルートのキャッシング、およびパケットのヒント（例：TOSフィールド）に基づくTOSルーティングが含まれます。
QoS-based routing should be scalable, and hierarchical aggregation is a common technique for scaling (e.g., [PNNI96]). But this introduces problems with regard to the accuracy of the aggregated state information [L95]. Also, the aggregation of paths under multiple constraints is difficult. One of the difficulties is the risk of accepting a flow based on inaccurate information, but not being able to support the QoS requirements of flow because the capabilities of the actual paths that are aggregated are not known during route computation. Performance impacts of aggregating path metric information must therefore be understood. A way to compensate for inaccuracies is to use crankback, i.e., dynamic search for alternate paths as a flow is being routed. But crankback increases the time to set up a flow, and may adversely affect the performance of the routing scheme under some circumstances. Thus, crankback must be used judiciously, if at all, along with a higher level admission control mechanism.
QoSベースのルーティングはスケーラブルである必要があり、階層集約はスケーリングの一般的な手法です（[PNNI96]など）。ただし、これにより、集計された状態情報の精度に関する問題が発生します[L95]。また、複数の制約の下でのパスの集約は困難です。困難なことの1つは、不正確な情報に基づいてフローを受け入れるリスクですが、集約された実際のパスの機能がルート計算中にわからないため、フローのQoS要件をサポートできません。したがって、パスメトリック情報の集約によるパフォーマンスへの影響を理解する必要があります。不正確さを補正する方法は、クランクバックを使用することです。つまり、フローがルーティングされているときに代替パスを動的に検索します。ただし、クランクバックはフローをセットアップする時間を増加させ、状況によってはルーティングスキームのパフォーマンスに悪影響を与える可能性があります。したがって、クランクバックは、たとえあったとしても、より高いレベルのアドミッションコントロールメカニズムと一緒に、慎重に使用する必要があります。
At the intradomain level, the objective is to allow as much latitude as possible in addressing the QoS-based routing issues. Indeed, there are many ideas about how QoS-based routing services can be provisioned within ASs. These range from on-demand path computation based on current state information, to statically provisioned paths supporting a few service classes.
ドメイン内レベルでの目的は、QoSベースのルーティングの問題に対処する際に、可能な限り多くの自由度を許容することです。実際、QoSベースのルーティングサービスをAS内でプロビジョニングする方法については、多くのアイデアがあります。これらは、現在の状態情報に基づくオンデマンドパス計算から、いくつかのサービスクラスをサポートする静的にプロビジョニングされたパスにまで及びます。
Another aspect that might invite differing solutions is performance optimization. Based on the technique used for this, intradomain routing could be very sophisticated or rather simple. Finally, the service classes supported, as well as the specific QoS engineered for a service class, could differ from AS to AS. For instance, some ASs may not support guaranteed service, while others may. Also, some ASs supporting the service may be engineered for a better delay bound than others. Thus, it requires considerable thought to determine the high level requirements for intradomain routing that both supports the overall view of QoS-based routing in the Internet and allows maximum autonomy in developing solutions.
異なるソリューションを招く可能性があるもう1つの側面は、パフォーマンスの最適化です。これに使用される技術に基づいて、ドメイン内ルーティングは非常に洗練されているか、またはかなり単純である可能性があります。最後に、サポートされるサービスクラス、およびサービスクラス用に設計された特定のQoSは、ASごとに異なる可能性があります。たとえば、一部のASは保証されたサービスをサポートしない場合があり、他の場合はサポートします。また、サービスをサポートする一部のASは、他のASよりも優れた遅延限界を実現するように設計されている場合があります。したがって、インターネット内のQoSベースのルーティングの全体像をサポートし、ソリューションの開発における最大の自律性を可能にするドメイン内ルーティングの高レベルの要件を決定するには、十分な検討が必要です。
Our view is that certain minimum requirements must be satisfied by intradomain routing in order to be qualified as "QoS-based" routing. These are:
私たちの見解では、「QoSベースの」ルーティングとして認定されるためには、ドメイン内ルーティングによって特定の最小要件を満たす必要があります。これらは：
- The routing scheme must route a flow along a path that can accommodate its QoS requirements, or indicate that the flow cannot be admitted with the QoS currently being requested.
- ルーティングスキームは、QoS要件に対応できるパスに沿ってフローをルーティングするか、現在要求されているQoSでフローを許可できないことを示す必要があります。
- The routing scheme must indicate disruptions to the current route of a flow due to topological changes.
- ルーティングスキームは、トポロジの変更によるフローの現在のルートの中断を示す必要があります。
- The routing scheme must accommodate best-effort flows without any resource reservation requirements. That is, present best effort applications and protocol stacks need not have to change to run in a domain employing QoS-based routing.
- ルーティング方式は、リソース予約の要件なしでベストエフォートフローに対応する必要があります。つまり、現在のベストエフォートアプリケーションとプロトコルスタックは、QoSベースのルーティングを採用するドメインで実行するために変更する必要はありません。
- The routing scheme may optionally support QoS-based multicasting with receiver heterogeneity and shared reservation styles.
- ルーティングスキームは、オプションで、QoSベースのマルチキャスティングをサポートし、レシーバの異質性と共有予約スタイルをサポートします。
In addition, the following capabilities are also recommended:
さらに、次の機能も推奨されます。
- Capabilities to optimize resource usage.
- リソースの使用を最適化する機能。
- Implementation of higher level admission control procedures to limit the overall resource utilization by individual flows.
- 個々のフローによる全体的なリソース使用率を制限するための高レベルのアドミッション制御手順の実装。
Further requirements along these lines may be specified. The requirements should capture the consensus view of QoS-based routing, but should not preclude particular approaches (e.g., TOS-based routing) from being implemented. Thus, the intradomain requirements are expected to be rather broad.
これらの線に沿ってさらに要件を指定することができます。要件は、QoSベースのルーティングのコンセンサスビューをキャプチャする必要がありますが、特定のアプローチ（TOSベースのルーティングなど）の実装を妨げるものであってはなりません。したがって、ドメイン内の要件はかなり広いと予想されます。
The fundamental requirement on interdomain QoS-based routing is scalability. This implies that interdomain routing cannot be based on highly dynamic network state information. Rather, such routing must be aided by sound network engineering and relatively sparse information exchange between independent routing domains. This approach has the advantage that it can be realized by straightforward extensions of the present Internet interdomain routing model. A number of issues, however, need to be addressed to achieve this, as discussed below.
ドメイン間QoSベースのルーティングの基本的な要件はスケーラビリティです。これは、ドメイン間ルーティングが非常に動的なネットワーク状態情報に基づくことができないことを意味します。むしろ、そのようなルーティングは、健全なネットワークエンジニアリングと、独立したルーティングドメイン間の比較的疎な情報交換によって支援される必要があります。このアプローチには、現在のインターネットドメイン間ルーティングモデルを直接拡張することで実現できるという利点があります。ただし、以下で説明するように、これを実現するにはいくつかの問題に対処する必要があります。
The interdomain QoS-based routing model is depicted below:
ドメイン間QoSベースのルーティングモデルを以下に示します。
AS1 AS2 AS3
___________ _____________ ____________
| | | | | |
| B------B B----B |
| | | | | |
-----B----- B------------- --B---------
\ / /
\ / /
____B_____B____ _________B______
| | | |
| B-------B |
| | | |
| B-------B |
--------------- ----------------
AS4 AS5
Here, ASs exchange standardized routing information via border nodes B. Under this model, each AS can itself consist of a set of interconnected ASs, with standardized routing interaction. Thus, the interdomain routing model is hierarchical. Also, each lowest level AS employs an intradomain QoS-based routing scheme (proprietary or standardized by intradomain routing efforts such as QOSPF). Given this structure, some questions that arise are:
ここで、ASは境界ノードBを介して標準化されたルーティング情報を交換します。このモデルでは、各AS自体が、標準化されたルーティング相互作用を備えた相互接続されたASのセットで構成できます。したがって、ドメイン間ルーティングモデルは階層的です。また、最下位レベルの各ASは、ドメイン内のQoSベースのルーティングスキームを採用します（QOSPFなどのドメイン内ルーティングの取り組みによって独自に開発または標準化されています）。この構造を前提として、発生するいくつかの質問は次のとおりです。
- What information is exchanged between ASs?
- AS間で交換される情報は何ですか？
- What routing capabilities does the information exchange lead to? (E.g., source routing, on-demand path computation, etc.)
- 情報交換はどのようなルーティング機能をもたらしますか？ （例：ソースルーティング、オンデマンドパス計算など）
- How is the external routing information represented within an AS?
- AS内で外部ルーティング情報はどのように表されますか？
- How are interdomain paths computed?
- ドメイン間パスはどのように計算されますか？
- What sort of policy controls may be exerted on interdomain path computation and flow routing?, and
- ドメイン間パスの計算とフロールーティングに対して、どのようなポリシー制御を行うことができますか。
- How is interdomain QoS-based multicast routing accomplished?
- ドメイン間QoSベースのマルチキャストルーティングはどのように行われますか？
At a high level, the answers to these questions depend on the routing paradigm. Specifically, considering link state routing, the information exchanged between domains would consist of an abstract representation of the domains in the form of logical nodes and links, along with metrics that quantify their properties and resource availability. The hierarchical structure of the ASs may be handled by a hierarchical link state representation, with appropriate metric aggregation.
高レベルでは、これらの質問に対する答えはルーティングパラダイムによって異なります。具体的には、リンク状態ルーティングを考えると、ドメイン間で交換される情報は、論理ノードとリンクの形式でのドメインの抽象的な表現と、そのプロパティとリソースの可用性を定量化するメトリックで構成されます。 ASの階層構造は、適切なメトリック集約を使用して、階層リンク状態表現によって処理できます。
Link state routing may not necessarily be advantageous for interdomain routing for the following reasons:
リンク状態ルーティングは、次の理由により、ドメイン間ルーティングに必ずしも有利ではない場合があります。
- One advantage of intradomain link state routing is that it would allow fairly detailed link state information be used to compute paths on demand for flows requiring QoS. The state and metric aggregation used in interdomain routing, on the other hand, erodes this property to a great degree.
- ドメイン内リンク状態ルーティングの1つの利点は、QoSを必要とするフローのオンデマンドでパスを計算するためにかなり詳細なリンク状態情報を使用できることです。一方、ドメイン間ルーティングで使用される状態とメトリックの集約は、このプロパティを大幅に侵食します。
- The usefulness of keeping track of the abstract topology and metrics of a remote domain, or the interconnection between remote domains is not obvious. This is especially the case when the remote topology and metric encoding are lossy.
- リモートドメインの抽象的なトポロジとメトリック、またはリモートドメイン間の相互接続を追跡することの有用性は明らかではありません。これは、リモートトポロジとメトリックエンコーディングに損失がある場合に特に当てはまります。
- ASs may not want to advertise any details of their internal topology or resource availability.
- ASは、内部トポロジまたはリソースの可用性の詳細をアドバタイズしたくない場合があります。
- Scalability in interdomain routing can be achieved only if information exchange between domains is relatively infrequent. Thus, it seems practical to limit information flow between domains as much as possible.
- ドメイン間のルーティングのスケーラビリティは、ドメイン間の情報交換が比較的少ない場合にのみ実現できます。したがって、ドメイン間の情報の流れをできるだけ制限することが現実的です。
Compact information flow allows the implementation QoS-enhanced versions of existing interdomain protocols such as BGP-4. We look at the interdomain routing issues in this context.
コンパクトな情報フローにより、BGP-4などの既存のドメイン間プロトコルのQoS拡張バージョンを実装できます。ここでは、ドメイン間のルーティングの問題について説明します。
The information flow between routing domains must enable certain basic functions:
ルーティングドメイン間の情報フローは、特定の基本機能を有効にする必要があります。
1. Determination of reachability to various destinations
1. さまざまな目的地への到達可能性の決定
2. Loop-free flow routes
2. ループのないフロールート
3. Address aggregation whenever possible
3. 可能な限りアドレス集約
4. Determination of the QoS that will be supported on the path to a destination. The QoS information should be relatively static, determined from the engineered topology and capacity of an AS rather than ephemeral fluctuations in traffic load through the AS. Ideally, the QoS supported in a transit AS should be allowed to vary significantly only under exceptional circumstances, such as failures or focused overload.
4. 宛先へのパスでサポートされるQoSの決定。 QoS情報は比較的静的であり、ASを介したトラフィック負荷の一時的な変動ではなく、設計されたトポロジとASの容量から決定されます。理想的には、トランジットASでサポートされるQoSは、障害や集中的な過負荷などの例外的な状況でのみ大幅に変化することを許可する必要があります。
5. Determination, optionally, of multiple paths for a given destination, based on service classes.
5. オプションで、サービスクラスに基づいて、特定の宛先の複数のパスを決定します。
6. Expression of routing policies, including monetary cost, as a function of flow parameters, usage and administrative factors.
6. フローパラメータ、使用状況、および管理要素の関数としての金銭的コストを含むルーティングポリシーの表現。
Items 1-3 are already part of existing interdomain routing. Item 5 is also a straightfoward extension of the current model. The main problem areas are therefore items 4 and 6.
項目1〜3はすでに既存のドメイン間ルーティングの一部です。アイテム5も、現在のモデルを単純に拡張したものです。したがって、主な問題領域は、アイテム4と6です。
The QoS of an end-to-end path is obtained by composing the QoS available in each transit AS. Thus, border routers must first determine what the locally available QoS is in order to advertise routes to both internal and external destinations. The determination of local "AS metrics" (corresponding to link metrics in the intradomain case) should not be subject to too much dynamism. Thus, the issue is how to define such metrics and what triggers an occasional change that results in re-advertisements of routes.
エンドツーエンドパスのQoSは、各中継ASで利用可能なQoSを構成することによって取得されます。したがって、境界ルーターは、内部と外部の両方の宛先にルートをアドバタイズするために、ローカルで利用可能なQoSを最初に決定する必要があります。ローカルの「ASメトリック」（ドメイン内の場合のリンクメトリックに対応）の決定は、過度のダイナミズムの影響を受けるべきではありません。したがって、問題は、そのようなメトリックをどのように定義するか、およびルートの再アドバタイズメントをもたらす不定期の変更をトリガーするものです。
The approach suggested in this document is not to compute paths based on residual or instantaneous values of AS metics (which can be dynamic), but utilize only the QoS capabilities engineered for aggregate transit flows. Such engineering may be based on the knowledge of traffic to be expected from each neighboring ASs and the corresponding QOS needs. This information may be obtained based on contracts agreed upon prior to the provisioning of services. The AS metric then corresponds to the QoS capabilities of the "virtual path" engineered through the AS (for transit traffic) and a different metric may be used for different neighbors. This is illustrated in the following figure.
このドキュメントで提案されているアプローチは、ASメティクスの動的または動的な値に基づいてパスを計算するのではなく、集約トランジットフロー用に設計されたQoS機能のみを利用します。このようなエンジニアリングは、各隣接ASから予想されるトラフィックの知識と、対応するQOSのニーズに基づいている場合があります。この情報は、サービスの提供前に合意された契約に基づいて取得できます。次に、ASメトリックは、ASを介して設計された「トランジットトラフィック用の」「仮想パス」のQoS機能に対応し、異なるネイバーには異なるメトリックを使用できます。これを次の図に示します。
AS1 AS2 AS3
___________ _____________ ____________
| | | | | |
| B------B1 B2----B |
| | | | | |
-----B----- B3------------ --B---------
\ /
\ /
____B_____B____
| |
| |
| |
| |
---------------
AS4
Here, B1 may utilize an AS metric specific for AS1 when computing path metrics to be advertised to AS1. This metric is based on the resources engineered in AS2 for transit traffic from AS1. Similarly, B3 may utilize a different metric when computing path metrics to be advertised to AS4. Now, it is assumed that as long as traffic flow into AS2 from AS1 or AS4 does not exceed the engineered values, these path metrics would hold. Excess traffic due to transient fluctuations, however, may be handled as best effort or marked with a discard bit.
ここで、B1は、AS1にアドバタイズされるパスメトリックを計算するときに、AS1に固有のASメトリックを利用できます。このメトリックは、AS1からの通過トラフィック用にAS2で設計されたリソースに基づいています。同様に、B3は、AS4にアドバタイズされるパスメトリックを計算するときに、別のメトリックを利用できます。ここで、AS1またはAS4からAS2へのトラフィックフローが設計値を超えない限り、これらのパスメトリックが保持されると想定されています。ただし、一時的な変動による過剰なトラフィックは、ベストエフォートとして処理されるか、破棄ビットでマークされます。
Thus, this model is different from the intradomain model, where end nodes pick a path dynamically based on the QoS needs of the flow to be routed. Here, paths within ASs are engineered based on presumed, measured or declared traffic and QoS requirements. Under this model, an AS can contract for routes via multiple transit ASs with different QoS requirements. For instance, AS4 above can use both AS1 and AS2 as transits for same or different destinations. Also, a QoS contract between one AS and another may generate another contract between the second and a third AS and so forth.
したがって、このモデルは、エンドノードがルーティングされるフローのQoSニーズに基づいて動的にパスを選択するドメイン内モデルとは異なります。ここでは、AS内のパスは、推定、測定、または宣言されたトラフィックとQoS要件に基づいて設計されています。このモデルでは、ASは、QoS要件が異なる複数のトランジットASを介してルートを契約できます。たとえば、上記のAS4は、AS1とAS2の両方を同じ宛先または異なる宛先へのトランジットとして使用できます。また、１つのＡＳと別のＡＳとの間のＱｏＳ契約は、第２と第３のＡＳとの間などに別の契約を生成することができる。
An issue is what triggers the recomputation of path metrics within an AS. Failures or other events that prevent engineered resource allocation should certainly trigger recomputation. Recomputation should not be triggered in response to arrival of flows within the engineered limit.
問題は、AS内のパスメトリックの再計算をトリガーするものです。設計されたリソース割り当てを妨げる障害またはその他のイベントは、確実に再計算をトリガーするはずです。設計された制限内のフローの到着に応答して再計算をトリガーしないでください。
Path computation for an external destination at a border node is based on reachability, path metrics and local policies of selection. If there are multiple selection criteria (e.g., delay, bandwidth, cost, etc.), mutiple alternaives may have to be maintained as well as propagated by border nodes. Selection of a path from among many alternatives would depend on the QoS requests of flows, as well as policies. Path computation may also utilze any heuristics for optimizing resource usage.
境界ノードでの外部宛先のパス計算は、到達可能性、パスメトリック、および選択のローカルポリシーに基づいています。複数の選択基準（たとえば、遅延、帯域幅、コストなど）がある場合、複数の代替手段を維持し、境界ノードによって伝播する必要がある場合があります。多くの選択肢からのパスの選択は、フローのQoS要求とポリシーに依存します。パスの計算では、リソースの使用を最適化するためにヒューリスティックを利用することもできます。
An important issue in interdomain routing is the amount of flow state to be processed by transit ASs. Reducing the flow state by aggregation techniques must therefore be seriously considered. Flow aggregation means that transit traffic through an AS is classified into a few aggregated streams rather than being routed at the individual flow level. For example, an entry border router may classify various transit flows entering an AS into a few coarse categories, based on the egress node and QoS requirements of the flows. Then, the aggregated stream for a given traffic class may be routed as a single flow inside the AS to the exit border router. This router may then present individual flows to different neighboring ASs and the process repeats at each entry border router. Under this scenario, it is essential that entry border routers keep track of the resource requirements for each transit flow and apply admission control to determine whether the aggregate requirement from any neighbor exceeds the engineered limit. If so, some policy must be invoked to deal with the excess traffic. Otherwise, it may be assumed that aggregated flows are routed over paths that have adequate resources to guarantee QoS for the member flows. Finally, it is possible that entry border routers at a transit AS may prefer not to aggregate flows if finer grain routing within the AS may be more efficient (e.g., to aid load balancing within the AS).
ドメイン間ルーティングの重要な問題は、トランジットASによって処理されるフロー状態の量です。したがって、集約手法によるフロー状態の削減は真剣に検討する必要があります。フロー集約とは、ASを通過するトランジットトラフィックが、個々のフローレベルでルーティングされるのではなく、いくつかの集約されたストリームに分類されることを意味します。たとえば、エントリ境界ルーターは、フローの出口ノードとQoS要件に基づいて、ASに入るさまざまなトランジットフローをいくつかの大まかなカテゴリに分類できます。次に、特定のトラフィッククラスの集約ストリームは、AS内の単一のフローとして出口境界ルータにルーティングされます。このルーターは、個々のフローを異なる隣接ASに提示し、プロセスは各エントリ境界ルーターで繰り返されます。このシナリオでは、エントリ境界ルーターが各トランジットフローのリソース要件を追跡し、アドミッションコントロールを適用して、ネイバーからの集約要件が設計された制限を超えているかどうかを判断することが重要です。その場合、過剰なトラフィックに対処するために、いくつかのポリシーを呼び出す必要があります。そうでない場合、集約されたフローは、メンバーフローのQoSを保証するための適切なリソースを持つパスを介してルーティングされると想定される場合があります。最後に、AS内のより細かいルーティングがより効率的である場合（AS内のロードバランシングを支援するためなど）、トランジットASのエントリ境界ルーターがフローを集約しないことを好む可能性があります。
It is hoped that the integrated services Internet architecture would allow providers to charge for IP flows based on their QoS requirements. A QoS-based routing architecture can aid in distributing information on expected costs of routing flows to various destinations via different domains. Clearly, from a provider's point of view, there is a cost incurred in guaranteeing QoS to flows. This cost could be a function of several parameters, some related to flow parameters, others based on policy. From a user's point of view, the consequence of requesting a particular QoS for a flow is the cost incurred, and hence the selection of providers may be based on cost. A routing scheme can aid a provider in distributing the costs in routing to various destinations, as a function of several parameters, to other providers or to end users. In the interdomain routing model described earlier, the costs to a destination will change as routing updates are passed through a transit domain. One of the goals of the routing scheme should be to maintain a uniform semantics for cost values (or functions) as they are handled by intermediate domains. As an example, consider the cost function generated by border node B1 in domain A and passed to node B2 in domain B below. The routing update may be injected into domain B by B2 and finally passed to B4 in domain C by router B3. Domain B may interpret the cost value received from domain A in any way it wants, for instance, adding a locally significant component to it. But when this cost value is passed to domain C, the meaning of it must be what domain A intended, plus the incremental cost of transiting domain B, but not what domain B uses internally.
統合サービスインターネットアーキテクチャにより、プロバイダーはQoS要件に基づいてIPフローに課金できることが期待されます。 QoSベースのルーティングアーキテクチャは、ルーティングフローの予想コストに関する情報を、さまざまなドメイン経由でさまざまな宛先に配信するのに役立ちます。明らかに、プロバイダーの観点から見ると、フローへのQoSを保証するにはコストがかかります。このコストは、いくつかのパラメータの関数であり、フローパラメータに関連するものもあれば、ポリシーに基づくものもあります。ユーザーの観点から見ると、フローに対して特定のQoSを要求すると、発生するコストが発生するため、プロバイダーの選択はコストに基づいている場合があります。ルーティングスキームは、プロバイダーがさまざまな宛先へのルーティングのコストを、いくつかのパラメーターの関数として、他のプロバイダーまたはエンドユーザーに配布するのに役立ちます。前述のドメイン間ルーティングモデルでは、ルーティングの更新が中継ドメインを通過すると、宛先へのコストが変化します。ルーティングスキームの目標の1つは、コスト値（または関数）が中間ドメインによって処理されるときに、それらのコスト値（または関数）のセマンティクスを統一することです。例として、ドメインAの境界ノードB1によって生成され、以下のドメインBのノードB2に渡されるコスト関数を考えます。ルーティングアップデートは、B2によってドメインBに注入され、最後にルータB3によってドメインCのB4に渡されます。ドメインBは、ドメインAから受け取ったコスト値を、ローカルに重要なコンポーネントを追加するなど、任意の方法で解釈できます。ただし、このコスト値がドメインCに渡される場合、その意味は、ドメインAが意図したものと、ドメインBを通過するための増分コストであり、ドメインBが内部で使用するものではありません。
Domain A Domain B Domain C
____________ ___________ ____________
| | | | | |
| B1------B2 B3---B4 |
| | | | | |
------------ ----------- ------------
A problem with charging for a flow is the determination of the cost when the QoS promised for the flow was not actually delivered. Clearly, when a flow is routed via multiple domains, it must be determined whether each domain delivers the QoS it declares possible for traffic through it.
フローの課金に関する問題は、フローに対して約束されたQoSが実際に配信されなかった場合のコストの決定です。明らかに、フローが複数のドメインを介してルーティングされる場合、各ドメインがフローを通過するトラフィックに対して可能であると宣言したQoSを各ドメインが配信するかどうかを決定する必要があります。
The goals of QoS-based multicast routing are as follows:
QoSベースのマルチキャストルーティングの目的は次のとおりです。
- Scalability to large groups with dynamic membership
- 動的なメンバーシップを持つ大規模なグループへの拡張性
- Robustness in the presence of topological changes
- トポロジーの変化がある場合の堅牢性
- Support for receiver-initiated, heterogeneous reservations
- 受信者が開始する異種混合予約のサポート
- Support for shared reservation styles, and
- 共有予約スタイルのサポート、および
- Support for "global" admission control, i.e., administrative control of resource consumption by the multicast flow.
- 「グローバル」アドミッション制御、つまりマルチキャストフローによるリソース消費の管理制御のサポート。
The RSVP multicast flow model is as follows. The sender of a multicast flow advertises the traffic characteristics periodically to the receivers. On receipt of an advertisement, a receiver may generate a message to reserve resources along the flow path from the sender. Receiver reservations may be heterogeneous. Other multicast models may be considered.
RSVPマルチキャストフローモデルは次のとおりです。マルチキャストフローの送信者は、トラフィック特性を定期的に受信者にアドバタイズします。広告を受信すると、受信者はメッセージを生成して、送信者からのフローパスに沿ってリソースを予約します。レシーバーの予約は、異種の場合があります。他のマルチキャストモデルが考慮される場合があります。
The multicast routing scheme attempts to determine a path from the sender to each receiver that can accommodate the requested reservation. The routing scheme may attempt to maximize network resource utilization by minimizing the total bandwidth allocated to the multicast flow, or by optimizing some other measure.
マルチキャストルーティング方式は、要求された予約に対応できる送信者から各受信者へのパスを決定しようとします。ルーティングスキームは、マルチキャストフローに割り当てられる合計帯域幅を最小化するか、他の方法を最適化することにより、ネットワークリソースの使用率を最大化しようとする場合があります。
When addressing scalability, two aspects must be considered:
スケーラビリティに取り組む場合、2つの側面を考慮する必要があります。
1. The overheads associated with receiver discovery. This overhead is incurred when determining the multicast tree for forwarding best-effort sender traffic characterization to receivers.
1. レシーバー検出に関連するオーバーヘッド。このオーバーヘッドは、ベストエフォートの送信者トラフィック特性を受信者に転送するためのマルチキャストツリーを決定するときに発生します。
2. The overheads associated with QoS-based multicast path computation. This overhead is incurred when flow-specific state information has to be collected by a router to determine QoS-accommodating paths to a receiver.
2. QoSベースのマルチキャストパス計算に関連するオーバーヘッド。このオーバーヘッドは、ルーターがフロー固有の状態情報を収集して、レシーバーへのQoS対応パスを決定する必要がある場合に発生します。
Depending on the multicast routing scheme, one or both of these aspects become important. For instance, under the present RSVP model, reservations are established on the same path over which sender traffic characterizations are sent, and hence there is no path computation overhead. On the other hand, under the proposed QOSPF model [ZSSC97] of multicast source routing, receiver discovery overheads are incurred by MOSPF [M94] receiver location broadcasts, and additional path computation overheads are incurred due to the need to keep track of existing flow paths. Scaling of QoS-based multicast depends on both these scaling issues. However, scalable best-effort multicasting is really not in the domain of QoS-based routing work (solutions for this are being devised by the IDMR WG [BCF94, DEFV94]). QoS-based multicast routing may build on these solutions to achieve overall scalability.
マルチキャストルーティング方式に応じて、これらの側面の一方または両方が重要になります。たとえば、現在のRSVPモデルでは、送信トラフィック特性が送信されるのと同じパスで予約が確立されるため、パス計算のオーバーヘッドはありません。一方、マルチキャストソースルーティングの提案されたQOSPFモデル[ZSSC97]では、MOSPF [M94]レシーバーロケーションブロードキャストによってレシーバー発見のオーバーヘッドが発生し、既存のフローパスを追跡する必要があるため、追加のパス計算オーバーヘッドが発生します。 。 QoSベースのマルチキャストのスケーリングは、これら両方のスケーリングの問題に依存します。ただし、スケーラブルなベストエフォートマルチキャストは、QoSベースのルーティング作業の領域には実際にはありません（この解決策はIDMR WG [BCF94、DEFV94]によって考案されています）。 QoSベースのマルチキャストルーティングは、これらのソリューションに基づいて構築され、全体的なスケーラビリティを実現します。
There are several options for QoS-based multicast routing. Multicast source routing is one under which multicast trees are computed by the first-hop router from the source, based on sender traffic advertisements. The advantage of this is that it blends nicely with the present RSVP signaling model. Also, this scheme works well when receiver reservations are homogeneous and the same as the maximum reservation derived from sender advertisement. The disadvantages of this scheme are the extra effort needed to accommodate heterogeneous reservations and the difficulties in optimizing resource allocation based on shared reservations.
QoSベースのマルチキャストルーティングには、いくつかのオプションがあります。マルチキャストソースルーティングは、送信元トラフィックアドバタイズメントに基づいて、マルチキャストツリーがソースからの最初のホップのルーターによって計算されるルーティングです。これの利点は、現在のRSVPシグナリングモデルとうまく調和することです。また、このスキームは、受信者の予約が同種であり、送信者のアドバタイズメントから導出された最大予約と同じである場合にうまく機能します。この方式の短所は、異種混合の予約に対応するために必要な追加の労力と、共有予約に基づいてリソース割り当てを最適化することの困難さです。
In these regards, a receiver-oriented multicast routing model seems to have some advantage over multicast source routing. Under this model:
これらの点で、レシーバー指向のマルチキャストルーティングモデルには、マルチキャストソースルーティングよりもいくつかの利点があるようです。このモデルでは：
1. Sender traffic advertisements are multicast over a best-effort tree which can be different from the QoS-accommodating tree for sender data.
1. 送信者トラフィックアドバタイズメントは、送信者データのQoS対応ツリーとは異なる可能性があるベストエフォートツリーを介してマルチキャストされます。
2. Receiver discovery overheads are minimized by utilizing a scalable scheme (e.g., PIM, CBT), to multicast sender traffic characterization.
2. スケーラブルなスキーム（PIM、CBTなど）を利用して送信者のトラフィック特性をマルチキャストすることで、受信者の発見のオーバーヘッドを最小限に抑えます。
3. Each receiver-side router independently computes a QoS-accommodating path from the source, based on the receiver reservation. This path can be computed based on unicast routing information only, or with additional multicast flow-specific state information. In any case, multicast path computation is broken up into multiple, concurrent nunicast path computations.
3.各レシーバー側ルーターは、レシーバー予約に基づいて、ソースからのQoS収容パスを個別に計算します。このパスは、ユニキャストルーティング情報のみ、または追加のマルチキャストフロー固有の状態情報に基づいて計算できます。いずれの場合も、マルチキャストパス計算は、複数の同時ユニキャストパス計算に分割されます。
4. Routers processing unicast reserve messages from receivers aggregate resource reservations from multiple receivers.
4. レシーバーからのユニキャスト予約メッセージを処理するルーターは、複数のレシーバーからのリソース予約を集約します。
Flow-specific state information may be limited in Step 3 to achieve scalability [RN98]. In general, limiting flow-specific information in making multicast routing decisions is important in any routing model. The advantages of this model are the ease with which heterogeneous reservations can be accommodated, and the ability to handle shared reservations. The disadvantages are the incompatibility with the present RSVP signaling model, and the need to rely on reverse paths when link state routing is not used. Both multicast source routing and the receiver-oriented routing model described above utilize per-source trees to route multicast flows. Another possibility is the utilization of shared, per-group trees for routing flows. The computation and usage of such trees require further work.
フロー固有の状態情報は、スケーラビリティを実現するためにステップ3で制限される場合があります[RN98]。一般に、マルチキャストルーティングの決定を行う際にフロー固有の情報を制限することは、どのルーティングモデルでも重要です。このモデルの利点は、異機種混合の予約に容易に対応できること、および共有予約を処理できることです。欠点は、現在のRSVPシグナリングモデルとの互換性がないことと、リンクステートルーティングが使用されていない場合にリバースパスに依存する必要があることです。上記のマルチキャストソースルーティングとレシーバー指向ルーティングモデルはどちらも、ソースごとのツリーを利用してマルチキャストフローをルーティングします。別の可能性は、ルーティングフローにグループごとの共有ツリーを使用することです。このようなツリーの計算と使用には、さらに作業が必要です。
Finally, scalability at the interdomain level may be achieved if QoS-based multicast paths are computed independently in each domain. This principle is illustrated by the QOSPF multicast source routing scheme which allows independent path computation in different OSPF areas. It is easy to incorporate this idea in the receiver-oriented model also. An evaluation of multicast routing strategies must take into account the relative advantages and disadvantages of various approaches, in terms of scalability features and functionality supported.
最後に、QoSベースのマルチキャストパスが各ドメインで個別に計算される場合、ドメイン間レベルでのスケーラビリティが達成されます。この原理は、さまざまなOSPFエリアでの独立したパス計算を可能にするQOSPFマルチキャストソースルーティングスキームによって示されています。このアイデアをレシーバー指向のモデルに組み込むことも簡単です。マルチキャストルーティング戦略の評価では、サポートされるスケーラビリティ機能と機能の観点から、さまざまなアプローチの相対的な利点と欠点を考慮する必要があります。
Higher level admission control, as defined for unicast, prevents excessive resource consumption by flows when traffic load is high. Such an admission control strategy must be applied to multicast flows when the flow path computation is receiver-oriented or sender-oriented. In essence, a router computing a path for a receiver must determine whether the incremental resource allocation for the receiver is excessive under some administratively determined admission control policy. Other admission control criteria, based on the total resource consumption of a tree may be defined.
ユニキャストに対して定義されているように、より高いレベルのアドミッション制御は、トラフィックの負荷が高いときにフローによる過度のリソース消費を防ぎます。このようなアドミッション制御戦略は、フローパスの計算がレシーバ指向またはセンダー指向の場合、マルチキャストフローに適用する必要があります。基本的に、レシーバーのパスを計算するルーターは、管理者が決定したアドミッションコントロールポリシーの下で、レシーバーの増分リソース割り当てが過剰かどうかを判断する必要があります。ツリーの総リソース消費量に基づいて、他の許可制御基準を定義できます。
There must clearly be a well-defined interface between routing and resource reservation protocols. The nature of this interface, and the interaction between routing and resource reservation has to be determined carefully to avoid incompatibilities. The importance of this can be readily illustrated in the case of RSVP.
ルーティングプロトコルとリソース予約プロトコルの間には、明確に定義されたインターフェイスが必要です。このインターフェースの性質、およびルーティングとリソース予約の間の相互作用は、非互換性を回避するために慎重に決定する必要があります。これの重要性は、RSVPの場合に容易に説明できます。
RSVP has been designed to operate independent of the underlying routing scheme. Under this model, RSVP PATH messages establish the reverse path for RESV messages. In essence, this model is not compatible with QoS-based routing schemes that compute paths after receiver reservations are received. While this incompatibility can be resolved in a simple manner for unicast flows, multicast with heterogeneous receiver requirements is a more difficult case. For this, reconciliation between RSVP and QoS-based routing models is necessary. Such a reconciliation, however, may require some changes to the RSVP model depending on the QoS-based routing model [ZES97, ZSSC97, GOA97]. On the other hand, QoS-based routing schemes may be designed with RSVP compatibility as a necessary goal. How this affects scalability and other performance measures must be considered.
RSVPは、基盤となるルーティング方式とは関係なく動作するように設計されています。このモデルでは、RSVP PATHメッセージはRESVメッセージの逆のパスを確立します。本質的に、このモデルは、受信者の予約が受信された後にパスを計算するQoSベースのルーティング方式と互換性がありません。この非互換性はユニキャストフローの場合は簡単な方法で解決できますが、異種のレシーバー要件を持つマルチキャストの方が難しいケースです。このためには、RSVPとQoSベースのルーティングモデル間の調整が必要です。ただし、このような調整には、QoSベースのルーティングモデル[ZES97、ZSSC97、GOA97]に応じて、RSVPモデルにいくつかの変更が必要になる場合があります。一方、QoSベースのルーティングスキームは、RSVP互換性を必要な目標として設計される場合があります。これがスケーラビリティやその他のパフォーマンス測定にどのように影響するかを考慮する必要があります。
Security issues that arise with routing in general are about maintaining the integrity of the routing protocol in the presence of unintentional or malicious introduction of information that may lead to protocol failure [P88]. QoS-based routing requires additional security measures both to validate QoS requests for flows and to prevent resource-depletion type of threats that can arise when flows are allowed to make arbitratry resource requests along various paths in the network. Excessive resource consumption by an errant flow results in denial of resources to legitimate flows. While these situations may be prevented by setting up proper policy constraints, charging models and policing at various points in the network, the formalization of such protection requires work [BCCH94].
一般にルーティングで発生するセキュリティの問題は、プロトコルの失敗につながる可能性のある、意図しないまたは悪意のある情報の導入が存在する場合にルーティングプロトコルの整合性を維持することに関するものです[P88]。 QoSベースのルーティングでは、フローのQoS要求を検証するためと、フローがネットワーク内のさまざまなパスに沿って任意のリソース要求を行うことを許可されたときに発生する可能性があるリソース枯渇タイプの脅威を防ぐための追加のセキュリティ対策が必要です。誤ったフローによる過剰なリソース消費は、正当なフローへのリソースの拒否につながります。これらの状況は、適切なポリシーの制約、課金モデル、およびネットワーク内のさまざまなポイントでのポリシングを設定することによって防ぐことができますが、そのような保護の正式化には作業が必要です[BCCH94]。
"Adaptive" routing, based on network state, has a long history, especially in circuit-switched networks. Such routing has also been implemented in early datagram and virtual circuit packet networks. More recently, this type of routing has been the subject of study in the context of ATM networks, where the traffic characteristics and topology are substantially different from those of circuit-switched networks [MMR96]. It is instructive to review the adaptive routing methodologies, both to understand the problems encountered and possible solutions.
ネットワーク状態に基づく「アダプティブ」ルーティングには、特に回線交換ネットワークにおいて長い歴史があります。このようなルーティングは、初期のデータグラムおよび仮想回線パケットネットワークにも実装されています。最近では、このタイプのルーティングは、トラフィックの特性とトポロジが回線交換ネットワークのそれとは実質的に異なる[MMR96] ATMネットワークのコンテキストでの研究対象となっています。発生した問題と考えられる解決策の両方を理解するために、アダプティブルーティングの方法論を確認することは有益です。
Fundamentally, there are two aspects to adaptive, network state-dependent routing:
基本的に、適応型のネットワーク状態依存ルーティングには2つの側面があります。
1. Measuring and gathering network state information, and 2. Computing routes based on the available information.
1. ネットワーク状態情報の測定と収集、および2.利用可能な情報に基づくルートの計算。
Depending on how these two steps are implemented, a variety of routing techniques are possible. These differ in the following respects:
これらの2つのステップの実装方法に応じて、さまざまなルーティング手法が可能です。これらは次の点で異なります。
- what state information is used - whether local or global state is used - what triggers the propagation of state information - whether routes are computed in a distributed or centralized manner - whether routes are computed on-demand, pre-computed, or in a hybrid manner - what optimization criteria, if any, are used in computing routes - whether source routing or hop by hop routing is used, and - how alternate route choices are explored
- 使用される状態情報-ローカル状態とグローバル状態のどちらが使用されるか-状態情報の伝播をトリガーするもの-ルートが分散方式または集中方式のどちらで計算されるか-ルートがオンデマンド、事前計算、またはハイブリッドのいずれで計算されるか-ルートの計算に使用される最適化基準（ある場合）-ソースルーティングまたはホップバイホップルーティングのどちらを使用するか、および-代替ルートの選択肢を探索する方法
It should be noted that most of the adaptive routing work has focused on unicast routing. Multicast routing is one of the areas that would be prominent with Internet QoS-based routing. We treat this separately, and the following review considers only unicast routing. This review is not exhaustive, but gives a brief overview of some of the approaches.
適応ルーティング作業のほとんどはユニキャストルーティングに焦点を合わせていることに注意してください。マルチキャストルーティングは、インターネットQoSベースのルーティングで顕著になる領域の1つです。これは個別に扱い、次のレビューではユニキャストルーティングのみを考慮します。このレビューは完全ではありませんが、いくつかのアプローチの概要を示します。
The most common optimization criteria used in adaptive routing is throughput maximization or delay minimization. A general formulation of the optimization problem is the one in which the network revenue is maximized, given that there is a cost associated with routing a flow over a given path [MMR96, K88]. In general, global optimization solutions are difficult to implement, and they rely on a number of assumptions on the characteristics of the traffic being routed [MMR96]. Thus, the practical approach has been to treat the routing of each flow (VC, circuit or packet stream to a given destination) independently of the routing of other flows. Many such routing schemes have been implemented.
適応ルーティングで使用される最も一般的な最適化基準は、スループットの最大化または遅延の最小化です。最適化問題の一般的な定式化は、特定のパスを介してフローをルーティングすることに関連するコストがあることを考えると、ネットワーク収益が最大になる問題です[MMR96、K88]。一般に、グローバル最適化ソリューションは実装が困難であり、ルーティングされるトラフィックの特性に関する多くの仮定に依存しています[MMR96]。したがって、実際のアプローチは、他のフローのルーティングとは無関係に、各フロー（VC、回路、またはパケットストリームから特定の宛先へ）のルーティングを処理することです。このようなルーティング方式の多くが実装されています。
Many adaptive routing concepts have been proposed for circuit-switched networks. An example of a simple adaptive routing scheme is sequential alternate routing [T88]. This is a hop-by-hop destination-based routing scheme where only local state information is utilized. Under this scheme, a routing table is computed for each node, which lists multiple output link choices for each destination. When a call set-up request is received by a node, it tries each output link choice in sequence, until it finds one that can accommodate the call. Resources are reserved on this link, and the call set-up is forwarded to the next node. The set-up either reaches the destination, or is blocked at some node. In the latter case, the set-up can be cranked back to the previous node or a failure declared. Crankback allows the previous node to try an alternate path. The routing table under this scheme can be computed in a centralized or distributed manner, based only on the topology of the network. For instance, a k-shortest-path algorithm can be used to determine k alternate paths from a node with distinct initial links [T88]. Some mechanism must be implemented during path computation or call set-up to prevent looping.
回線交換ネットワークに対して、多くの適応ルーティングの概念が提案されています。単純な適応ルーティング方式の例は、順次代替ルーティング[T88]です。これは、ホップバイホップの宛先ベースのルーティング方式であり、ローカル状態情報のみが利用されます。このスキームでは、ノードごとにルーティングテーブルが計算され、宛先ごとに複数の出力リンクの選択肢が一覧表示されます。ノードが呼び出し設定要求を受信すると、呼び出しに対応できる出力リンクが見つかるまで、各出力リンクの選択を順番に試行します。リソースはこのリンクで予約され、コールセットアップは次のノードに転送されます。セットアップは宛先に到達するか、一部のノードでブロックされます。後者の場合、セットアップを前のノードに戻すか、障害を宣言することができます。クランクバックにより、前のノードは代替パスを試すことができます。この方式のルーティングテーブルは、ネットワークのトポロジーのみに基づいて、集中または分散方式で計算できます。たとえば、k最短経路アルゴリズムを使用して、異なる初期リンクを持つノードからkの代替経路を決定できます[T88]。ループを防ぐために、パスの計算または呼び出しのセットアップ中に、いくつかのメカニズムを実装する必要があります。
Performance studies of this scheme illustrate some of the pitfalls of alternate routing in general, and crankback in particular [A84, M86, YS87]. Specifically, alternate routing improves the throughput when traffic load is relatively light, but adversely affects the performance when traffic load is heavy. Crankback could further degrade the performance under these conditions. In general, uncontrolled alternate routing (with or without crankback) can be harmful in a heavily utilized network, since circuits tend to be routed along longer paths thereby utilizing more capacity. This is an obvious, but important result that applies to QoS-based Internet routing also.
このスキームのパフォーマンス調査は、一般的な代替ルーティング、特にクランクバックの落とし穴のいくつかを示しています[A84、M86、YS87]。具体的には、代替ルーティングは、トラフィック負荷が比較的軽い場合にスループットを向上させますが、トラフィック負荷が重い場合にはパフォーマンスに悪影響を及ぼします。クランクバックは、これらの条件下でパフォーマンスをさらに低下させる可能性があります。一般に、制御されていない代替ルーティング（クランクバックの有無にかかわらず）は、使用率の高いネットワークでは有害になる可能性があります。これは、回路がより長いパスに沿ってルーティングされる傾向があり、それによってより多くの容量が使用されるためです。これは明らかですが、QoSベースのインターネットルーティングにも適用される重要な結果です。
The problem with alternate routing is that both direct routed (i.e., over shortest paths) and alternate routed calls compete for the same resource. At higher loads, allocating these resources to alternate routed calls result in the displacement of direct routed calls and hence the alternate routing of these calls. Therefore, many approaches have been proposed to limit the flow of alternate routed calls under high traffic loads. These schemes are designed for the fully-connected logical topology of long distance telephone networks (i.e., there is a logical link between every pair of nodes). In this topology, direct routed calls always traverse a 1-hop path to the destination and alternate routed calls traverse at most a 2-hop path.
代替ルーティングの問題は、直接ルーティング（つまり、最短パス経由）と代替ルーティングコールの両方が同じリソースで競合することです。より高い負荷では、これらのリソースを代替ルーティングされたコールに割り当てると、直接ルーティングされたコールが置き換えられ、これらのコールの代替ルーティングが行われます。したがって、トラフィックの負荷が高いときに代替ルーティングコールのフローを制限するための多くのアプローチが提案されています。これらのスキームは、長距離電話ネットワークの完全に接続された論理トポロジ用に設計されています（つまり、ノードのすべてのペア間に論理リンクがあります）。このトポロジでは、直接ルーティングされたコールは常に宛先への1ホップパスを通過し、代替ルーティングされたコールは最大で2ホップパスを通過します。
"Trunk reservation" is a scheme whereby on each link a certain bandwidth is reserved for direct routed calls [MS91]. Alternate routed calls are allowed on a trunk as long as the remaining trunk bandwidth is greater than the reserved capacity. Thus, alternate routed calls cannot totally displace direct routed calls on a trunk. This strategy has been shown to be very effective in preventing the adverse effects of alternate routing.
「トランク予約」とは、各リンクで特定の帯域幅を直接ルーティングされた通話用に予約する方式です[MS91]。残りのトランク帯域幅が予約済み容量を超えている限り、代替ルーティングコールはトランク上で許可されます。したがって、代替ルーティングコールは、トランク上の直接ルーティングコールを完全に置き換えることはできません。この戦略は、代替ルーティングの悪影響を防ぐのに非常に効果的であることが示されています。
"Dynamic alternate routing" (DAR) is a strategy whereby alternate routing is controlled by limiting the number of choices, in addition to trunk reservation [MS91]. Under DAR, the source first attempts to use the direct link to the destination. When blocked, the source attempts to alternate route the call via a pre-selected neighbor. If the call is still blocked, a different neighbor is selected for alternate routing to this destination in the future. The present call is dropped. DAR thus requires only local state information. Also, it "learns" of good alternate paths by random sampling and sticks to them as long as possible.
「ダイナミック代替ルーティング」（DAR）は、トランクの予約に加えて、選択肢の数を制限することで代替ルーティングを制御する戦略です[MS91]。 DARでは、ソースは最初に宛先への直接リンクを使用しようとします。ブロックされている場合、ソースは事前に選択されたネイバーを介してコールを代替ルートしようとします。コールがまだブロックされている場合、将来この宛先への代替ルーティング用に別のネイバーが選択されます。現在の通話は切断されます。したがって、DARはローカル状態情報のみを必要とします。また、ランダムサンプリングによって適切な代替パスを「学習」し、可能な限りそれらに固執します。
More recent circuit-switched routing schemes utilize global state to select routes for calls. An example is AT&T's Real-Time Network Routing (RTNR) scheme [ACFH92]. Unlike schemes like DAR, RTNR handles multiple classes of service, including voice and data at fixed rates. RTNR utilizes a sophisticated per-class trunk reservation mechanism with dynamic bandwidth sharing between classes. Also, when alternate routing a call, RTNR utilizes the loading on all trunks in the network to select a path. Because of the fully-connected topology, disseminating status information is simple under RTNR; each node simply exchanges status information directly with all others.
最近の回線交換ルーティング方式では、グローバル状態を使用して、コールのルートを選択します。例は、AT＆Tのリアルタイムネットワークルーティング（RTNR）スキーム[ACFH92]です。 DARなどのスキームとは異なり、RTNRは固定レートの音声やデータを含む複数のサービスクラスを処理します。 RTNRは、クラス間で動的な帯域幅を共有するクラスごとの高度なトランク予約メカニズムを利用します。また、コールを代替ルーティングする場合、RTNRはネットワーク内のすべてのトランクの負荷を利用してパスを選択します。完全に接続されたトポロジーがあるため、RTNRではステータス情報の伝達は簡単です。各ノードは、ステータス情報を他のすべてのノードと直接交換するだけです。
From the point of view of designing QoS-based Internet routing schemes, there is much to be learned from circuit-switched routing. For example, alternate routing and its control, and dynamic resource sharing among different classes of traffic. It is, however, not simple to apply some of the results to a general topology network with heterogeneous multirate traffic. Work in the area of ATM network routing described next illustrates this.
QoSベースのインターネットルーティングスキームを設計する観点からは、回線交換ルーティングから学ぶべきことがたくさんあります。たとえば、代替ルーティングとその制御、およびトラフィックの異なるクラス間での動的リソース共有。ただし、結果の一部を異種マルチレートトラフィックのある一般的なトポロジネットワークに適用するのは簡単ではありません。次に説明するATMネットワークルーティングの領域での作業は、これを示しています。
The VC routing problem in ATM networks presents issues similar to that encountered in circuit-switched networks. Not surprisingly, some extensions of circuit-switched routing have been proposed. The goal of these routing schemes is to achieve higher throughput as compared to traditional shortest-path routing. The flows considered usually have a single QoS requirement, i.e., bandwidth.
ATMネットワークにおけるVCルーティングの問題は、回線交換ネットワークで発生する問題と同様の問題を引き起こします。当然のことながら、回線交換ルーティングのいくつかの拡張が提案されています。これらのルーティングスキームの目標は、従来の最短パスルーティングと比較して、より高いスループットを実現することです。通常、考慮されるフローには、単一のQoS要件、つまり帯域幅があります。
The first idea is to extend alternate routing with trunk reservation to general topologies [SD95]. Under this scheme, a distance vector routing protocol is used to build routing tables at each node with multiple choices of increasing hop count to each destination. A VC set-up is first routed along the primary ("direct") path. If sufficient resources are not available along this path, alternate paths are tried in the order of increasing hop count. A flag in the VC set-up message indicates primary or alternate routing, and bandwidth on links along an alternate path is allocated subject to trunk reservation. The trunk reservation values are determined based on some assumptions on traffic characteristics. Because the scheme works only for a single data rate, the practical utility of it is limited.
最初のアイデアは、トランク予約を使用した代替ルーティングを一般的なトポロジに拡張することです[SD95]。この方式では、距離ベクトルルーティングプロトコルを使用して、各宛先へのホップカウントを増やすという複数の選択肢を持つ各ノードでルーティングテーブルを作成します。 VCセットアップは、まずプライマリ（「ダイレクト」）パスに沿ってルーティングされます。このパスで十分なリソースを利用できない場合は、ホップカウントの増加順に代替パスが試行されます。 VCセットアップメッセージのフラグはプライマリまたは代替ルーティングを示し、代替パスに沿ったリンクの帯域幅はトランク予約に従って割り当てられます。トランク予約値は、トラフィック特性に関するいくつかの仮定に基づいて決定されます。このスキームは単一のデータレートに対してのみ機能するため、その実用性は限られています。
The next idea is to import the notion of controlled alternate routing into traditional link state QoS-based routing [GKR96]. To do this,
次のアイデアは、制御された代替ルーティングの概念を従来のリンク状態QoSベースのルーティング[GKR96]にインポートすることです。これをする、
first each VC is associated with a maximum permissible routing cost. This cost can be set based on expected revenues in carrying the VC or simply based on the length of the shortest path to the destination. Each link is associated with a metric that increases exponentially with its utilization. A switch computing a path for a VC simply determines a least-cost feasible path based on the link metric and the VC's QoS requirement. The VC is admitted if the cost of the path is less than or equal to the maximum permissible routing cost. This routing scheme thus limits the extent of "detour" a VC experiences, thus preventing excessive resource consumption. This is a practical scheme and the basic idea can be extended to hierarchical routing. But the performance of this scheme has not been analyzed thoroughly. A similar notion of admission control based on the connection route was also incorporated in a routing scheme presented in [ACG92].
最初に、各VCは最大許容ルーティングコストに関連付けられます。このコストは、VCを伝送する際の予想収益に基づいて、または単純に宛先への最短経路の長さに基づいて設定できます。各リンクは、その使用率とともに指数関数的に増加するメトリックに関連付けられています。 VCのパスを計算するスイッチは、リンクメトリックとVCのQoS要件に基づいて、最小コストの実現可能なパスを単純に決定します。パスのコストが最大許容ルーティングコスト以下の場合、VCは許可されます。したがって、このルーティングスキームは、VCが経験する「迂回」の範囲を制限し、過剰なリソースの消費を防ぎます。これは実用的なスキームであり、基本的な考え方は階層型ルーティングに拡張できます。しかし、このスキームのパフォーマンスは完全に分析されていません。接続ルートに基づくアドミッションコントロールの同様の概念は、[ACG92]で提示されたルーティングスキームにも組み込まれました。
Considering the ATM Forum PNNI protocol [PNNI96], a partial list of its stated characteristics are as follows:
ATMフォーラムのPNNIプロトコル[PNNI96]を考慮すると、指定された特性の部分的なリストは次のとおりです。
o Scales to very large networks o Supports hierarchical routing o Supports QoS o Uses source routed connection setup o Supports multiple metrics and attributes o Provides dynamic routing
o 非常に大規模なネットワークに対応o階層型ルーティングをサポートo QoSをサポートoソースルーテッド接続セットアップを使用o複数のメトリックと属性をサポートo動的ルーティングを提供
The PNNI specification is sub-divided into two protocols: a signaling and a routing protocol. The PNNI signaling protocol is used to establish point-to-point and point to multipoint connections and supports source routing, crankback and alternate routing. PNNI source routing allows loop free paths. Also, it allows each implementation to use its own path computation algorithm. Furthermore, source routing is expected to support incremental deployment of future enhancements such as policy routing.
PNNI仕様は、シグナリングプロトコルとルーティングプロトコルの2つのプロトコルに細分されます。 PNNIシグナリングプロトコルは、ポイントツーポイントおよびポイントツーマルチポイント接続を確立するために使用され、ソースルーティング、クランクバック、および代替ルーティングをサポートします。 PNNIソースルーティングでは、ループのないパスを使用できます。また、各実装で独自のパス計算アルゴリズムを使用できます。さらに、ソースルーティングは、ポリシールーティングなどの将来の拡張機能の段階的な展開をサポートすることが期待されています。
The PNNI routing protocol is a dynamic, hierarchical link state protocol that propagates topology information by flooding it through the network. The topology information is the set of resources (e.g., nodes, links and addresses) which define the network. Resources are qualified by defined sets of metrics and attributes (delay, available bandwidth, jitter, etc.) which are grouped by supported traffic class. Since some of the metrics used will change frequently, e.g., available bandwidth, threshold algorithms are used to determine if the change in a metric or attribute is significant enough to require propagation of updated information. Other features include, auto configuration of the routing hierarchy, connection admission control (as part of path calculation) and aggregation and summarization of topology and reachability information.
PNNIルーティングプロトコルは動的で階層的なリンクステートプロトコルであり、ネットワークを介してフラッディングすることによりトポロジ情報を伝播します。トポロジ情報は、ネットワークを定義するリソース（ノード、リンク、アドレスなど）のセットです。リソースは、サポートされるトラフィッククラスごとにグループ化された、定義されたメトリックと属性（遅延、使用可能な帯域幅、ジッターなど）のセットによって修飾されます。使用されるメトリックの一部（使用可能な帯域幅など）は頻繁に変更されるため、しきい値アルゴリズムを使用して、メトリックまたは属性の変更が、更新された情報の伝播を必要とするほど重要かどうかを判断します。その他の機能には、ルーティング階層の自動設定、接続許可制御（パス計算の一部として）、トポロジーと到達可能性情報の集約と要約などがあります。
Despite its functionality, the PNNI routing protocol does not address the issues of multicast routing, policy routing and control of alternate routing. A problem in general with link state QoS-based routing is that of efficient broadcasting of state information. While flooding is a reasonable choice with static link metrics it may impact the performance adversely with dynamic metrics.
その機能にもかかわらず、PNNIルーティングプロトコルは、マルチキャストルーティング、ポリシールーティング、および代替ルーティングの制御の問題に対処していません。リンク状態QoSベースのルーティングに関する一般的な問題は、状態情報の効率的なブロードキャストの問題です。フラッディングは静的リンクメトリックでは妥当な選択ですが、動的メトリックではパフォーマンスに悪影響を与える可能性があります。
Finally, Integrated PNNI [I-PNNI] has been designed from the start to take advantage of the QoS Routing capabilities that are available in PNNI and integrate them with routing for layer 3. This would provide an integrated layer 2 and layer 3 routing protocol for networks that include PNNI in the ATM core. The I-PNNI specification has been under development in the ATM Forum and, at this time, has not yet incorporated QoS routing mechanisms for layer 3.
最後に、統合PNNI [I-PNNI]は、PNNIで利用可能なQoSルーティング機能を利用してレイヤー3のルーティングと統合するように最初から設計されています。これにより、統合されたレイヤー2およびレイヤー3ルーティングプロトコルが提供されます。 ATMコアにPNNIを含むネットワーク。 I-PNNI仕様は、ATMフォーラムで開発中であり、現時点では、レイヤ3のQoSルーティングメカニズムはまだ組み込まれていません。
Early attempts at adaptive routing in packet networks had the objective of delay minimization by dynamically adapting to network congestion. Alternate routing based on k-shortest path tables, with route selection based on some local measure (e.g., shortest output queue) has been described [R76, YS81]. The original ARPAnet routing scheme was a distance vector protocol with delay-based cost metric [MW77]. Such a scheme was shown to be prone to route oscillations [B82]. For this and other reasons, a link state delay-based routing scheme was later developed for the ARPAnet [MRR80]. This scheme demonstrated a number of techniques such as triggered updates, flooding, etc., which are being used in OSPF and PNNI routing today. Although none of these schemes can be called QoS-based routing schemes, they had features that are relevant to QoS-based routing.
パケットネットワークでの適応ルーティングの初期の試みは、ネットワークの輻輳に動的に適応することにより、遅延を最小限に抑えることを目的としていました。 k最短パステーブルに基づく代替ルーティングと、一部のローカルメジャー（たとえば、最短出力キュー）に基づくルート選択について説明しました[R76、YS81]。元のARPAnetルーティングスキームは、遅延ベースのコストメトリックを備えた距離ベクトルプロトコルでした[MW77]。そのような計画は、振動をルーティングする傾向があることが示された[B82]。この理由と他の理由により、リンク状態遅延ベースのルーティング方式は、後でARPAnet [MRR80]用に開発されました。このスキームは、トリガーされた更新やフラッディングなど、OSPFおよびPNNIルーティングで現在使用されている多くの手法を実証しました。これらのスキームはどれもQoSベースのルーティングスキームとは言えませんが、QoSベースのルーティングに関連する機能がありました。
IBM's System Network Architecture (SNA) introduced the concept of Class of Service (COS)-based routing [A79, GM79]. There were several classes of service: interactive, batch, and network control. In addition, users could define other classes. When starting a data session an application or device would request a COS. Routing would then map the COS into a statically configured route which marked a path across the physical network. Since SNA is connection oriented, a session was set up along this path and the application's or device's data would traverse this path for the life of the session. Initially, the service delivered to a session was based on the network engineering and current state of network congestion. Later, transmission priority was added to subarea SNA. Transmission priority allowed more important traffic (e.g. interactive) to proceed before less time-critical traffic (e.g. batch) and improved link and network utilization. Transmission priority of a session was based on its COS.
IBMのシステムネットワークアーキテクチャ（SNA）は、サービスクラス（COS）ベースのルーティングの概念を導入しました[A79、GM79]。いくつかのサービスクラスがありました：インタラクティブ、バッチ、およびネットワーク制御。さらに、ユーザーは他のクラスを定義できます。データセッションを開始すると、アプリケーションまたはデバイスはCOSを要求します。ルーティングは、COSを静的に構成されたルートにマッピングし、物理ネットワーク全体のパスをマークします。 SNAは接続指向であるため、このパスに沿ってセッションがセットアップされ、アプリケーションまたはデバイスのデータは、セッションの存続期間中、このパスを通過します。当初、セッションに配信されるサービスは、ネットワークエンジニアリングとネットワークの輻輳の現在の状態に基づいていました。その後、サブエリアSNAに伝送優先順位が追加されました。伝送優先順位により、重要度の高いトラフィック（インタラクティブなど）を先に進めてから、タイムクリティカルではないトラフィック（バッチなど）を減らし、リンクとネットワークの使用率を改善しました。セッションの送信優先度は、そのCOSに基づいていました。
SNA later evolved to support multiple or alternate paths between nodes. But, although assisted by network design tools, the network administrator still had to statically configure routes. IBM later introduced SNA's Advanced Peer to Peer Networking (APPN) [B85]. APPN added new features to SNA including dynamic routing based on a link state database. An application would use COS to indicate it traffic requirements and APPN would calculate a path capable of meeting these requirements. Each COS was mapped to a table of acceptable metrics and parameters that qualified the nodes and links contained in the APPN topology Database. Metrics and parameters used as part of the APPN route calculation include, but are not limited to: delay, cost per minute, node congestion and security. The dynamic nature of APPN allowed it to route around failures and reduce network configuration.
SNAはその後、ノード間の複数のパスまたは代替パスをサポートするように進化しました。しかし、ネットワーク設計ツールの支援を受けながらも、ネットワーク管理者は静的にルートを構成する必要がありました。 IBMは後にSNAのAdvanced Peer to Peer Networking（APPN）[B85]を導入しました。 APPNは、リンク状態データベースに基づく動的ルーティングなどの新機能をSNAに追加しました。アプリケーションはCOSを使用してトラフィック要件を示し、APPNはこれらの要件を満たすことができるパスを計算します。各COSは、APPNトポロジデータベースに含まれるノードとリンクを修飾する許容可能なメトリックとパラメーターのテーブルにマップされました。 APPNルート計算の一部として使用されるメトリックとパラメーターには、遅延、1分あたりのコスト、ノードの輻輳、およびセキュリティが含まれますが、これらに限定されません。 APPNの動的な性質により、障害を迂回してネットワーク構成を減らすことができました。
The service delivered by APPN was still based on the network engineering, transmission priority and network congestion. IBM later introduced an extension to APPN, High Performance Routing (HPR)[IBM97]. HPR uses a congestion avoidance algorithm called adaptive rate based (ARB) congestion control. Using predictive feedback methods, the ARB algorithm prevents congestion and improves network utilization. Most recently, an extension to the COS table has been defined so that HPR routing could recognize and take advantage of ATM QoS capabilities.
APPNが提供するサービスは、依然としてネットワークエンジニアリング、伝送優先度、およびネットワークの輻輳に基づいていました。 IBMは後にAPPNへの拡張であるHigh Performance Routing（HPR）[IBM97]を導入しました。 HPRは、適応レートベース（ARB）輻輳制御と呼ばれる輻輳回避アルゴリズムを使用します。予測フィードバック手法を使用して、ARBアルゴリズムは輻輳を防止し、ネットワーク使用率を向上させます。ごく最近、COSテーブルの拡張が定義され、HPRルーティングがATM QoS機能を認識して利用できるようになりました。
Considering IP routing, both IDRP [R92] and OSPF support type of service (TOS)-based routing. While the IP header has a TOS field, there is no standardized way of utilizing it for TOS specification and routing. It seems possible to make use of the IP TOS feature, along with TOS-based routing and proper network engineering, to do QoS-based routing. The emerging differentiated services model is generating renewed interest in TOS support. Among the newer schemes, Source Demand Routing (SDR) [ELRV96] allows on-demand path computation by routers and the implementation of strict and loose source routing. The Nimrod architecture [CCM96] has a number of concepts built in to handle scalability and specialized path computation. Recently, some work has been done on QoS-based routing schemes for the integrated services Internet. For example, in [M98], heuristic schemes for efficient routing of flows with bandwidth and/or delay constraints is described and evaluated.
IPルーティングを考えると、IDRP [R92]とOSPFの両方がサービスタイプ（TOS）ベースのルーティングをサポートしています。 IPヘッダーにはTOSフィールドがありますが、TOS仕様とルーティングにそれを利用する標準化された方法はありません。 QoSベースのルーティングを行うために、TOSベースのルーティングおよび適切なネットワークエンジニアリングと共にIP TOS機能を利用することは可能であるようです。新しい差別化サービスモデルは、TOSサポートへの新たな関心を生み出しています。新しいスキームの中で、ソースデマンドルーティング（SDR）[ELRV96]は、ルーターによるオンデマンドパス計算と、厳密でルーズなソースルーティングの実装を可能にします。 Nimrodアーキテクチャ[CCM96]には、スケーラビリティと特殊なパス計算を処理するために組み込まれた多くの概念があります。最近、統合サービスインターネット用のQoSベースのルーティングスキームでいくつかの作業が行われました。たとえば、[M98]では、帯域幅および/または遅延の制約があるフローの効率的なルーティングのためのヒューリスティックスキームが記述され、評価されています。
In this document, a framework for QoS-based Internet routing was defined. This framework adopts the traditional separation between intra and interdomain routing. This approach is especially meaningful in the case of QoS-based routing, since there are many views on how QoS-based routing should be accomplished and many different needs. The objective of this document was to encourage the development of different solution approaches for intradomain routing, subject to some broad requirements, while consensus on interdomain routing is achieved. To this end, the QoS-based routing issues were described, and some broad intradomain routing requirements and an interdomain routing model were defined. In addition, QoS-based multicast routing was discussed and a detailed review of related work was presented.
このドキュメントでは、QoSベースのインターネットルーティングのフレームワークが定義されています。このフレームワークは、ドメイン内ルーティングとドメイン間ルーティングの間の従来の分離を採用しています。この方法は、QoSベースのルーティングの場合に特に意味があります。QoSベースのルーティングをどのように実行するか、および多くの異なるニーズについて多くの見解があるためです。このドキュメントの目的は、ドメイン間ルーティングに関するコンセンサスが得られている間、いくつかの広範な要件に従って、ドメイン内ルーティングのさまざまなソリューションアプローチの開発を促進することでした。このために、QoSベースのルーティングの問題が説明され、いくつかの広範なドメイン内ルーティング要件とドメイン間ルーティングモデルが定義されました。さらに、QoSベースのマルチキャストルーティングが議論され、関連する作業の詳細なレビューが提示されました。
The deployment of QoS-based routing across multiple administrative domains requires both the development of intradomain routing schemes and a standard way for them to interact via a well-defined interdomain routing mechanism. This document, while outlining the issues that must be addressed, did not engage in the specification of the actual features of the interdomain routing scheme. This would be the next step in the evolution of wide-area, multidomain QoS-based routing.
複数の管理ドメインにまたがるQoSベースのルーティングの導入には、ドメイン内ルーティングスキームの開発と、明確に定義されたドメイン間ルーティングメカニズムを介して相互作用するための標準的な方法の両方が必要です。このドキュメントでは、対処する必要のある問題の概要を説明しましたが、ドメイン間ルーティングスキームの実際の機能の仕様については触れていません。これは、広域マルチドメインQoSベースのルーティングの進化における次のステップです。
REFERENCES
参考文献
[A79] V. Ahuja, "Routing and Flow Control in SNA", IBM Systems Journal, 18 No. 2, pp. 298-314, 1979.
[A79] V. Ahuja、「SNAにおけるルーティングとフロー制御」、IBM Systems Journal、18 No. 2、pp。298-314、1979。
[A84] J. M. Akinpelu, "The Overload Performance of Engineered Networks with Non-Hierarchical Routing", AT&T Technical Journal, Vol. 63, pp. 1261-1281, 1984.
[A84] J. M. Akinpelu、「非階層型ルーティングによるエンジニアリングネットワークの過負荷パフォーマンス」、AT＆T Technical Journal、Vol。 63、pp。1261-1281、1984。
[ACFH92] G. R. Ash, J. S. Chen, A. E. Frey and B. D. Huang, "RealTime Network Routing in a Dynamic Class-of-Service Network", Proceedings of ITC 13, 1992.
[ACFH92] G. R.アッシュ、J。S.チェン、A。E.フレイ、B。D.フアン、「動的サービスクラスネットワークにおけるリアルタイムネットワークルーティング」、ITC 13、1992年の議事録。
[ACG92] H. Ahmadi, J. Chen, and R. Guerin, "Dynamic Routing and Call Control in High-Speed Integrated Networks", Proceedings of ITC-13, pp. 397-403, 1992.
[ACG92] H.アフマディ、J。チェン、およびR.ゲリン、「高速統合ネットワークにおけるダイナミックルーティングおよびコール制御」、ITC-13の議事録、pp。397-403、1992。
[B82] D. P. Bertsekas, "Dynamic Behavior of Shortest Path Routing Algorithms for Communication Networks", IEEE Trans. Auto. Control, pp. 60-74, 1982.
[B82] D. P. Bertsekas、「通信ネットワークの最短経路ルーティングアルゴリズムの動的動作」、IEEEトランス。自動。コントロール、pp。60-74、1982。
[B85] A. E. Baratz, "SNA Networks of Small Systems", IEEE JSAC, May, 1985.
[B85] A. E.バラッツ、「SNA Networks of Small Systems」、IEEE JSAC、1985年5月。
[BBCD98] Black, D., Blake, S., Carlson, M., Davies, E., Wang, Z., and W. Weiss, "An Architecture for Differentiated Services", Work in Progress.
[BBCD98] Black、D.、Blake、S.、Carlson、M.、Davies、E.、Wang、Z.、W。Weiss、「差別化されたサービスのアーキテクチャ」、進行中。
[BCCH94] Braden, R., Clark, D., Crocker, D., and C. Huitema, "Report of IAB Workshop on Security in the Internet Architecture", RFC 1636, June 1994.
[BCCH94] Braden、R.、Clark、D.、Crocker、D。、およびC. Huitema、「インターネットアーキテクチャのセキュリティに関するIABワークショップのレポート」、RFC 1636、1994年6月。
[BCF94] A. Ballardie, J. Crowcroft and P. Francis, "Core-Based Trees: A Scalable Multicast Routing Protocol", Proceedings of SIGCOMM `94.
[BCF94] A. Ballardie、J。CrowcroftおよびP. Francis、「Core-Based Trees：A Scalable Multicast Routing Protocol」、Proceedings of SIGCOMM `94。
[BCS94] Braden, R., Clark, D., and S. Shenker, "Integrated Services in the Internet Architecture: An Overview", RFC 1633, July 1994.
[BCS94] Braden、R.、Clark、D。、およびS. Shenker、「Integrated Services in the Internet Architecture：An Overview」、RFC 1633、1994年7月。
[BZ92] S. Bahk and M. El Zarki, "Dynamic Multi-Path Routing and How it Compares with Other Dynamic Routing Algorithms for High Speed Wide Area Networks", Proc. SIGCOMM `92, pp. 53-64, 1992.
[BZ92] S. BahkとM. El Zarki、「ダイナミックマルチパスルーティングと高速ワイドエリアネットワークの他の動的ルーティングアルゴリズムとの比較」、Proc。 SIGCOMM `92、pp。53-64、1992。
[BZBH97] Braden, R., Zhang, L., Berson, S., Herzog, S., and S. Jamin, "Resource ReSerVation Protocol (RSVP) -- Version 1 Functional Spec", RFC 2205, September 1997.
[BZBH97] Braden、R.、Zhang、L.、Berson、S.、Herzog、S。、およびS. Jamin、「Resource ReSerVation Protocol（RSVP）-Version 1 Functional Spec」、RFC 2205、1997年9月。
[C91] C-H. Chow, "On Multicast Path Finding Algorithms", Proceedings of the IEEE INFOCOM `91, pp. 1274-1283, 1991.
[C91] C-H。 Chow、 "On Multicast Path Finding Algorithms"、Proceedings of the IEEE INFOCOM `91、pp。1274-1283、1991。
[CCM96] Castineyra, I., Chiappa, J., and M. Steenstrup, "The Nimrod Routing Architecture", RFC 1992, August 1996.
[CCM96] Castineyra、I.、Chiappa、J。、およびM. Steenstrup、「The Nimrod Routing Architecture」、RFC 1992、1996年8月。
[DEFV94] S. E. Deering, D. Estrin, D. Farinnacci, V. Jacobson, C-G. Liu, and L. Wei, "An Architecture for Wide-Area Multicast Routing", Technical Report, 94-565, ISI, University of Southern California, 1994.
[DEFV94] S. E.ディアリング、D。エストリン、D。ファリンナッチ、V。ヤコブソン、C-G。 LiuとL. Wei、「An Area for Multi-Area Multicast Routing」、テクニカルレポート、94-565、ISI、南カリフォルニア大学、1994年。
[ELRV96] Estrin, D., Li, T., Rekhter, Y., Varadhan, K., and D. Zappala, "Source Demand Routing: Packet Format and Forwarding Specification (Version 1)", RFC 1940, May 1996.
[ELRV96] Estrin、D.、Li、T.、Rekhter、Y.、Varadhan、K。、およびD. Zappala、「Source Demand Routing：Packet Format and Forwarding Specification（Version 1）」、RFC 1940、1996年5月。
[GKR96] R. Gawlick, C. R. Kalmanek, and K. G. Ramakrishnan, "On-Line Routing of Permanent Virtual Circuits", Computer Communications, March, 1996.
[GKR96] R.ゴーリック、C。R.カルマネク、およびK. G.ラマクリシュナン、「永久仮想回線のオンラインルーティング」、コンピュータコミュニケーション、1996年3月。
[GPSS98] A. Ghanwani, J. W. Pace, V. Srinivasan, A. Smith and M. Seaman, "A Framework for Providing Integrated Services over Shared and Switched IEEE 802 LAN Technologies", Work in Progress.
[GPSS98] A. Ghanwani、J。W. Pace、V。Srinivasan、A。Smith、およびM. Seaman、「共有およびスイッチIEEE 802 LANテクノロジーを介して統合サービスを提供するためのフレームワーク」、進行中。
[GM79] J. P. Gray, T. B. McNeil, "SNA Multi-System Networking", IBM Systems Journal, 18 No. 2, pp. 263-297, 1979.
[GM79] J. P.グレイ、T。B.マクニール、「SNAマルチシステムネットワーキング」、IBMシステムジャーナル、18 No. 2、pp。263-297、1979。
[GOA97] Y. Goto, M. Ohta and K. Araki, "Path QoS Collection for Stable Hop-by-Hop QoS Routing", Proc. INET '97, June, 1997.
[GOA97]後藤Y.、太田M.、荒木K. "安定したホップバイホップQoSルーティングのためのパスQoSコレクション"、Proc。 INET '97、1997年6月。
[GKOP98] R. Guerin, S. Kamat, A. Orda, T. Przygienda, and D. Williams, "QoS Routing Mechanisms and OSPF extensions", work in progress, March, 1998.
[GKOP98] R. Guerin、S。Kamat、A。Orda、T。Przygienda、およびD. Williams、「QoS Routing Mechanisms and OSPF extensions」、1998年3月に進行中。
[IBM97] IBM Corp, SNA APPN - High Performance Routing Architecture Reference, Version 2.0, SV40-1018, February 1997.
[IBM97] IBM Corp、SNA APPN-ハイパフォーマンスルーティングアーキテクチャリファレンス、バージョン2.0、SV40-1018、1997年2月。
[IPNNI] ATM Forum Technical Committee. Integrated PNNI (I-PNNI) v1.0 Specification. af-96-0987r1, September 1996.
[IPNNI] ATMフォーラム技術委員会。統合PNNI（PNNI）v1.0仕様。 af-96-0987r1、1996年9月。
[ISI81] Postel, J., "Internet Protocol", STD 5, RFC 791, September 1981.
[ISI81] Postel、J。、「インターネットプロトコル」、STD 5、RFC 791、1981年9月。
[JMW83] J. M. Jaffe, F. H. Moss, R. A. Weingarten, "SNA Routing: Past, Present, and Possible Future", IBM Systems Journal, pp. 417-435, 1983.
[JMW83] J. M.ジャフェ、F。H.モス、R。A.ウェインガルテン、「SNAルーティング：過去、現在、そして起こり得る未来」、IBMシステムジャーナル、pp。417-435、1983。
[K88] F.P. Kelly, "Routing in Circuit-Switched Networks: Optimization, Shadow Prices and Decentralization", Adv. Applied Prob., pp. 112-144, March, 1988.
[K88] F.P.ケリー、「回線交換ネットワークでのルーティング：最適化、シャドー価格および分散化」、Adv。 Applied Prob。、pp。112-144、1988年3月。
[L95] W. C. Lee, "Topology Aggregation for Hierarchical Routing in ATM Networks", ACM SIGCOMM Computer Communication Review, 1995.
[L95] W. C.リー、「ATMネットワークにおける階層型ルーティングのトポロジ集約」、ACM SIGCOMM Computer Communication Review、1995年。
[M86] L. G. Mason, "On the Stability of Circuit-Switched Networks with Non-hierarchical Routing", Proc. 25th Conf. On Decision and Control, pp. 1345-1347, 1986.
[M86] L. G.メイソン、「非階層型ルーティングによる回線交換ネットワークの安定性について」、Proc。第25回会議Decision and Control、pp。1345-1347、1986。
[M98] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[M98] Moy、J。、「OSPFバージョン2」、STD 54、RFC 2328、1998年4月。
[M94] Moy, J., "MOSPF: Analysis and Experience", RFC 1585, March 1994.
[M94] Moy、J。、「MOSPF：Analysis and Experience」、RFC 1585、1994年3月。
[M98] Q. Ma, "Quality-of-Service Routing in Integrated Services Networks", PhD thesis, Computer Science Department, Carnegie Mellon University, 1998.
[M98] Q. Ma、「Integrated Services NetworksにおけるQuality-of-Service Routing」、博士論文、カーネギーメロン大学、コンピューターサイエンス学部、1998年。
[MMR96] D. Mitra, J. Morrison, and K. G. Ramakrishnan, "ATM Network Design and Optimization: A Multirate Loss Network Framework", Proceedings of IEEE INFOCOM `96, 1996.
[MMR96] D.ミトラ、J。モリソン、およびK. G.ラマクリシュナン、「ATMネットワークの設計と最適化：マルチレート損失ネットワークフレームワーク」、IEEE INFOCOM `96、1996の議事録。
[MRR80] J. M. McQuillan, I. Richer and E. C. Rosen, "The New Routing Algorithm for the ARPANET", IEEE Trans. Communications, pp. 711-719, May, 1980.
[MRR80] J. M. McQuillan、I。RicherおよびE. C. Rosen、「ARPANETの新しいルーティングアルゴリズム」、IEEEトランス。コミュニケーション、pp.711-719、1980年5月。
[MS91] D. Mitra and J. B. Seery, "Comparative Evaluations of Randomized and Dynamic Routing Strategies for Circuit Switched Networks", IEEE Trans. on Communications, pp. 102- 116, January, 1991.
[MS91] D. MitraおよびJ. B. Seery、「回線交換ネットワークのランダム化および動的ルーティング戦略の比較評価」、IEEE Trans。 on Communications、pp。102-116、1991年1月。
[MW77] J. M. McQuillan and D. C. Walden, "The ARPANET Design Decisions", Computer Networks, August, 1977.
[MW77] J. M.マッキヤンとD. C.ウォルデン、「ARPANET設計決定」、コンピュータネットワーク、1977年8月。
[NC94] Nair, R. and Clemmensen, D. : "Routing in Integrated Services Networks", Proc. 2nd International Conference on Telecom. Systems Modeling and Analysis, March 1994.
[NC94] Nair、R。およびClemmensen、D .:「統合サービスネットワークでのルーティング」、Proc。テレコムに関する第2回国際会議。システムのモデリングと分析、1994年3月。
[P88] R. Perlman, "Network Layer Protocol with Byzantine Robustness", Ph.D. Thesis, Dept. of EE and CS, MIT, August, 1988.
[P88] R.パールマン、「ビザンチンの堅牢性を備えたネットワーク層プロトコル」、Ph.D。論文、EEおよびCS部門、MIT、1988年8月。
[PNNI96] ATM Forum PNNI subworking group, "Private Network-Network Interface Spec. v1.0 (PNNI 1.0)", afpnni-0055.00, March 1996.
[PNNI96] ATMフォーラムPNNIサブワーキンググループ、「プライベートネットワークネットワークインターフェース仕様V1.0（PNNI 1.0）」、afpnni-0055.00、1996年3月。
[R76] H. Rudin, "On Routing and "Delta Routing": A Taxonomy and Performance Comparison of Techniques for Packet-Switched Networks", IEEE Trans. Communications, pp. 43-59, January, 1996.
[R76] H. Rudin、「ルーティングと「デルタルーティング」：タクソノミーとパケット交換ネットワークの技術のパフォーマンス比較」、IEEEトランス。コミュニケーション、pp。43-59、1996年1月。
[R92] Y. Rekhter, "IDRP Protocol Analysis: Storage Overhead", ACM Comp. Comm. Review, April, 1992.
[R92] Y.レクター、「IDRPプロトコル分析：ストレージオーバーヘッド」、ACM Comp。通信。レビュー、1992年4月。
[R96] B. Rajagopalan, "Efficient Link State Routing", Work in Progress, available from braja@ccrl.nj.nec.com.
[R96] B. Rajagopalan、「Efficient Link State Routing」、Work in Progress、braja @ ccrl.nj.nec.comから入手可能。
[RN98] B. Rajagopalan and R. Nair, "Multicast Routing with Resource Reservation", to appear in J. of High Speed Networks, 1998.
[RN98] B. RajagopalanおよびR. Nair、「Resource Reservation with Multicast Routing」、J。of High Speed Networks、1998に登場。
[SD95] S. Sibal and A. Desimone, "Controlling Alternate Routing in General-Mesh Packet Flow Networks", Proceedings of ACM SIGCOMM, 1995.
[SD95] S. SibalおよびA. Desimone、「General-Mesh Packet Flow Networksにおける代替ルーティングの制御」、ACM SIGCOMMのプロシーディングス、1995年。
[SPG97] Shenker, S., Partridge, C., and R. Guerin, "Specification of Guaranteed Quality of Service", RFC 2212, September 1997.
[SPG97]シェンカー、S。、パートリッジ、C。、およびR.ゲリン、「保証されたサービス品質の仕様」、RFC 2212、1997年9月。
[T88] D. M. Topkis, "A k-Shortest-Path Algorithm for Adaptive Routing in Communications Networks", IEEE Trans. Communications, pp. 855-859, July, 1988.
[T88] D. M.トプキス、「通信ネットワークにおける適応ルーティングのためのk最短経路アルゴリズム」、IEEEトランス。コミュニケーション、pp.855-859、1988年7月。
[W88] B. M. Waxman, "Routing of Multipoint Connections", IEEE JSAC, pp. 1617-1622, December, 1988.
[W88] B. M.ワックスマン、「マルチポイント接続のルーティング」、IEEE JSAC、pp。1617-1622、1988年12月。
[W97] Wroclawski, J., "Specification of the Controlled-Load Network Element Service", RFC 2211, September 1997.
[W97] Wroclawski、J。、「Controlled-Load Network Element Serviceの仕様」、RFC 2211、1997年9月。
[WC96] Z. Wang and J. Crowcroft, "QoS Routing for Supporting Resource Reservation", IEEE JSAC, September, 1996.
[WC96] Z. WangおよびJ. Crowcroft、「リソース予約をサポートするためのQoSルーティング」、IEEE JSAC、1996年9月。
[YS81] T. P. Yum and M. Schwartz, "The Join-Based Queue Rule and its Application to Routing in Computer Communications Networks", IEEE Trans. Communications, pp. 505-511, 1981.
[YS81] T. P.ユムとM.シュワルツ、「Join-Based Queue Rule and its Application to Routing in Routing in Computer Communications Networks」、IEEE Trans。コミュニケーション、pp.505-511、1981。
[YS87] T. G. Yum and M. Schwartz, "Comparison of Routing Procedures for Circuit-Switched Traffic in Nonhierarchical Networks", IEEE Trans. Communications, pp. 535-544, May, 1987.
[YS87] T. G.ヤムとM.シュワルツ、「非階層型ネットワークにおける回線交換トラフィックのルーティング手順の比較」、IEEEトランス。コミュニケーション、pp。535-544、1987年5月。
[ZES97] Zappala, D., Estrin, D., and S. Shenker, "Alternate Path Routing and Pinning for Interdomain Multicast Routing", USC Computer Science Technical Report #97-655, USC, 1997.
[ZES97] Zappala、D.、Estrin、D。、およびS. Shenker、「ドメイン間マルチキャストルーティングの代替パスルーティングおよびピン接続」、USC Computer Scienceテクニカルレポート＃97-655、USC、1997。
[ZSSC97] Zhang, Z., Sanchez, C., Salkewicz, B., and E. Crawley, "QoS Extensions to OSPF", Work in Progress.
[ZSSC97] Zhang、Z.、Sanchez、C.、Salkewicz、B。、およびE. Crawley、「QoS Extensions to OSPF」、Work in Progress。
AUTHORS' ADDRESSES
著者のアドレス
Bala Rajagopalan NEC USA, C&C Research Labs 4 Independence Way Princeton, NJ 08540 U.S.A
Bala Rajagopalan NEC USA、C＆C Research Labs 4 Independence Way Princeton、NJ 08540 U.S.A
Phone: +1-609-951-2969
EMail: braja@ccrl.nj.nec.com
Raj Nair Arrowpoint 235 Littleton Rd. Westford, MA 01886 U.S.A
Raj Nair Arrowpoint 235 Littleton Rd。ウェストフォード、MA 01886アメリカ
Phone: +1-508-692-5875, x29
EMail: nair@arrowpoint.com
Hal Sandick Bay Networks, Inc. 1009 Slater Rd., Suite 220 Durham, NC 27703 U.S.A
Hal Sandick Bay Networks、Inc. 1009 Slater Rd。、Suite 220 Durham、NC 27703 U.S.A
Phone: +1-919-941-1739
EMail: Hsandick@baynetworks.com
Eric S. Crawley Argon Networks, Inc. 25 Porter Rd. Littelton, MA 01460 U.S.A
Eric S. Crawley Argon Networks、Inc. 25 Porter Rd。リテルトン、MA 01460 U.S.A
Phone: +1-508-486-0665
EMail: esc@argon.com
Full Copyright Statement
完全な著作権表示
Copyright (C) The Internet Society (1998). All Rights Reserved.
Copyright（C）The Internet Society（1998）。全著作権所有。
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.
このドキュメントとここに含まれる情報は「現状有姿」で提供され、インターネット社会およびインターネット技術タスクフォースは、明示または黙示を問わず、ここに記載されている情報の使用が保証するものに限定されないいかなる保証も含め、一切の保証を否認します。商品性または特定の目的への適合性に関する権利または黙示の保証を侵害すること。