Network Working Group G. Apostolopoulos
Request for Comments: 2676 D. Williams
Category: Experimental IBM
S. Kamat
Lucent
R. Guerin
UPenn
A. Orda
Technion
T. Przygienda
Siara Systems
August 1999
Network Working Group G. Apostolopoulos
Request for Comments: 2676 D. Williams
Category: Experimental IBM
S. Kamat
Lucent
R. Guerin
UPenn
A. Orda
Technion
T. Przygienda
Siara Systems
August 1999
QoS Routing Mechanisms and OSPF Extensions
QoS路由机制与OSPF扩展
Status of this Memo
本备忘录的状况
This memo defines an Experimental Protocol for the Internet community. It does not specify an Internet standard of any kind. Discussion and suggestions for improvement are requested. Distribution of this memo is unlimited.
这份备忘录为互联网社区定义了一个实验性协议。它没有规定任何类型的互联网标准。要求进行讨论并提出改进建议。本备忘录的分发不受限制。
Copyright Notice
版权公告
Copyright (C) The Internet Society (1999). All Rights Reserved.
版权所有（C）互联网协会（1999年）。版权所有。
Abstract
摘要
This memo describes extensions to the OSPF [Moy98] protocol to support QoS routes. The focus of this document is on the algorithms used to compute QoS routes and on the necessary modifications to OSPF to support this function, e.g., the information needed, its format, how it is distributed, and how it is used by the QoS path selection process. Aspects related to how QoS routes are established and managed are also briefly discussed. The goal of this document is to identify a framework and possible approaches to allow deployment of QoS routing capabilities with the minimum possible impact to the existing routing infrastructure.
本备忘录描述了OSPF[Moy98]协议的扩展，以支持QoS路由。本文档的重点是用于计算QoS路由的算法，以及为支持此功能而对OSPF进行的必要修改，例如，所需信息、其格式、其分布方式以及QoS路径选择过程如何使用。还简要讨论了与如何建立和管理QoS路由相关的方面。本文档的目标是确定一个框架和可能的方法，以允许在对现有路由基础设施影响最小的情况下部署QoS路由功能。
In addition, experience from an implementation of the proposed extensions in the GateD environment [Con], along with performance measurements is presented.
此外，还介绍了在门控环境[Con]中实现所建议扩展的经验，以及性能度量。
Table of Contents
目录
1. Introduction 3
1.1. Overall Framework . . . . . . . . . . . . . . . . . . . . 3
1.2. Simplifying Assumptions . . . . . . . . . . . . . . . . . 5
2. Path Selection Information and Algorithms 7
2.1. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2. Advertisement of Link State Information . . . . . . . . . 8
2.3. Path Selection . . . . . . . . . . . . . . . . . . . . .10
2.3.1. Path Computation Algorithm . . . . . . . . . . .11
3. OSPF Protocol Extensions 16
3.1. QoS -- Optional Capabilities . . . . . . . . . . . . . .17
3.2. Encoding Resources as Extended TOS . . . . . . . . . . .17
3.2.1. Encoding bandwidth resource . . . . . . . . . . .19
3.2.2. Encoding Delay . . . . . . . . . . . . . . . . .21
3.3. Packet Formats . . . . . . . . . . . . . . . . . . . . .21
3.4. Calculating the Inter-area Routes . . . . . . . . . . . .22
3.5. Open Issues . . . . . . . . . . . . . . . . . . . . . . .22
4. A Reference Implementation based on GateD 22
4.1. The Gate Daemon (GateD) Program . . . . . . . . . . . . .22
4.2. Implementing the QoS Extensions of OSPF . . . . . . . . .23
4.2.1. Design Objectives and Scope . . . . . . . . . . .23
4.2.2. Architecture . . . . . . . . . . . . . . . . . .24
4.3. Major Implementation Issues . . . . . . . . . . . . . . .25
4.4. Bandwidth and Processing Overhead of QoS Routing . . . .29
5. Security Considerations 32
A. Pseudocode for the BF Based Pre-Computation Algorithm 33
B. On-Demand Dijkstra Algorithm for QoS Path Computation 36
C. Precomputation Using Dijkstra Algorithm 39
D. Explicit Routing Support 43
Endnotes 45
References 46
Authors' Addresses 48
Full Copyright Statement 50
1. Introduction 3
1.1. Overall Framework . . . . . . . . . . . . . . . . . . . . 3
1.2. Simplifying Assumptions . . . . . . . . . . . . . . . . . 5
2. Path Selection Information and Algorithms 7
2.1. Metrics . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2. Advertisement of Link State Information . . . . . . . . . 8
2.3. Path Selection . . . . . . . . . . . . . . . . . . . . .10
2.3.1. Path Computation Algorithm . . . . . . . . . . .11
3. OSPF Protocol Extensions 16
3.1. QoS -- Optional Capabilities . . . . . . . . . . . . . .17
3.2. Encoding Resources as Extended TOS . . . . . . . . . . .17
3.2.1. Encoding bandwidth resource . . . . . . . . . . .19
3.2.2. Encoding Delay . . . . . . . . . . . . . . . . .21
3.3. Packet Formats . . . . . . . . . . . . . . . . . . . . .21
3.4. Calculating the Inter-area Routes . . . . . . . . . . . .22
3.5. Open Issues . . . . . . . . . . . . . . . . . . . . . . .22
4. A Reference Implementation based on GateD 22
4.1. The Gate Daemon (GateD) Program . . . . . . . . . . . . .22
4.2. Implementing the QoS Extensions of OSPF . . . . . . . . .23
4.2.1. Design Objectives and Scope . . . . . . . . . . .23
4.2.2. Architecture . . . . . . . . . . . . . . . . . .24
4.3. Major Implementation Issues . . . . . . . . . . . . . . .25
4.4. Bandwidth and Processing Overhead of QoS Routing . . . .29
5. Security Considerations 32
A. Pseudocode for the BF Based Pre-Computation Algorithm 33
B. On-Demand Dijkstra Algorithm for QoS Path Computation 36
C. Precomputation Using Dijkstra Algorithm 39
D. Explicit Routing Support 43
Endnotes 45
References 46
Authors' Addresses 48
Full Copyright Statement 50
In this document, we describe a set of proposed additions to the OSPF routing protocol (these additions have been implemented on top of the GateD [Con] implementation of OSPF V2 [Moy98]) to support Quality-of-Service (QoS) routing in IP networks. Support for QoS routing can be viewed as consisting of three major components:
在本文档中，我们描述了OSPF路由协议的一组拟议新增内容（这些新增内容是在OSPF V2[Moy98]的门控[Con]实现之上实现的），以支持IP网络中的服务质量（QoS）路由。对QoS路由的支持可被视为由三个主要组件组成：
1. Obtain the information needed to compute QoS paths and select a path capable of meeting the QoS requirements of a given request,
1. 获取计算QoS路径所需的信息，并选择能够满足给定请求QoS要求的路径，
2. Establish the path selected to accommodate a new request,
2. 建立所选路径以适应新请求，
3. Maintain the path assigned for use by a given request.
3. 维护分配给给定请求使用的路径。
Although we touch upon aspects related to the last two components, the focus of this document is on the first one. In particular, we discuss the metrics required to support QoS, the extension to the OSPF link state advertisement mechanism to propagate updates of QoS metrics, and the modifications to the path selection to accommodate QoS requests. The goal of the extensions described in this document is to improve performance for QoS flows (likelihood to be routed on a path capable of providing the requested QoS), with minimal impact on the existing OSPF protocol and its current implementation. Given the inherent complexity of QoS routing, achieving this goal obviously implies trading-off "optimality" for "simplicity", but we believe this to be required in order to facilitate deployment of QoS routing capabilities.
尽管我们涉及与最后两个部分相关的方面，但本文件的重点是第一个部分。特别是，我们讨论了支持QoS所需的度量、对OSPF链路状态播发机制的扩展以传播QoS度量的更新，以及对路径选择的修改以适应QoS请求。本文档中描述的扩展的目标是在对现有OSPF协议及其当前实现影响最小的情况下，提高QoS流的性能（在能够提供请求的QoS的路径上路由的可能性）。考虑到QoS路由的内在复杂性，实现这一目标显然意味着要在“优化性”和“简单性”之间进行权衡，但我们认为这是为了促进QoS路由能力的部署所必需的。
In addition to describing the proposed extensions to the OSPF protocol, this document also reports experimental data based on performance measurements of an implementation done on the GateD platform (see Section 4).
除了描述OSPF协议的拟议扩展外，本文件还报告了基于门控平台上实现的性能测量的实验数据（见第4节）。
We consider a network (1) that supports both best-effort packets and packets with QoS guarantees. The way in which the network resources are split between the two classes is irrelevant, except for the assumption that each QoS capable router in the network is able to dedicate some of its resources to satisfy the requirements of QoS packets. QoS capable routers are also assumed capable of identifying and advertising resources that remain available to new QoS flows. In addition, we limit ourselves to the case where all the routers involved support the QoS extensions described in this document, i.e., we do not consider the problem of establishing a route in a heterogeneous environment where some routers are QoS-capable and others are not. Furthermore, in this document, we focus on the case
我们考虑一个网络（1），支持尽最大努力的数据包和QoS保证的数据包。网络资源在这两个类别之间划分的方式是不相关的，除非假设网络中的每个具有QoS能力的路由器能够专用其一些资源来满足QoS数据包的要求。支持QoS的路由器也被假定能够识别和广告仍然可用于新QoS流的资源。此外，我们限制我们所涉及的所有路由器支持本文档中描述的QoS扩展，即，我们不考虑在异构环境中建立路由的问题，其中一些路由器具有QoS能力，而另一些路由器则不是。此外，在本文件中，我们重点关注该案例
of unicast flows, although many of the additions we define are applicable to multicast flows as well.
虽然我们定义的许多添加项也适用于多播流，但也适用于单播流。
We assume that a flow with QoS requirements specifies them in some fashion that is accessible to the routing protocol. For example, this could correspond to the arrival of an RSVP [RZB+97] PATH message, whose TSpec is passed to routing together with the destination address. After processing such a request, the routing protocol returns the path that it deems the most suitable given the flow's requirements. Depending on the scope of the path selection process, this returned path could range from simply identifying the best next hop, i.e., a hop-by-hop path selection model, to specifying all intermediate nodes to the destination, i.e., an explicit route model. The nature of the path being returned impacts the operation of the path selection algorithm as it translates into different requirements for constructing and returning the appropriate path information. However, it does not affect the basic operation of the path selection algorithm (2).
我们假设具有QoS需求的流以路由协议可以访问的某种方式指定它们。例如，这可能对应于RSVP[RZB+97]路径消息的到达，其TSpec与目标地址一起传递给路由。在处理这样一个请求之后，路由协议返回它认为在给定流要求的情况下最合适的路径。根据路径选择过程的范围，该返回路径的范围可以从简单地识别最佳下一跳（即逐跳路径选择模型）到指定到目的地的所有中间节点（即显式路由模型）。返回的路径的性质会影响路径选择算法的操作，因为它会转化为构造和返回适当路径信息的不同要求。然而，它不影响路径选择算法（2）的基本操作。
For simplicity and also because it is the model currently supported in the implementation (see Section 4 for details), in the rest of this document we focus on the hop-by-hop path selection model. The additional modifications required to support an explicit routing model are discussed in appendix D, but are peripheral to the main focus of this document which concentrates on the specific extensions to the OPSF protocol to support computation of QoS routes.
为了简单起见，也因为它是实现中当前支持的模型（有关详细信息，请参见第4节），在本文档的其余部分中，我们将重点介绍逐跳路径选择模型。附录D中讨论了支持显式路由模型所需的其他修改，但这些修改与本文件的主要重点无关，本文件的重点是OPSF协议的特定扩展，以支持QoS路由的计算。
In addition to the problem of selecting a QoS path and possibly reserving the corresponding resources, one should note that the successful delivery of QoS guarantees requires that the packets of the associated "QoS flow" be forwarded on the selected path. This typically requires the installation of corresponding forwarding state in the router. For example, with RSVP [RZB+97] flows a classifier entry is created based on the filter specs contained in the RESV message. In the case of a Differentiated Service [KNB98] setting, the classifier entry may be based on the destination address (or prefix) and the corresponding value of the DS byte. The mechanisms described in this document are at the control path level and are, therefore, independent of data path mechanisms such as the packet classification method used. Nevertheless, it is important to notice that consistent delivery of QoS guarantees implies stability of the data path. In particular, while it is possible that after a path is first selected, network conditions change and result in the appearance of "better" paths, such changes should be prevented from unnecessarily affecting existing paths. In particular, switching over to a new (and better) path should be limited to specific conditions, e.g., when the initial selection turns out to be inadequate or extremely "expensive". This aspect is beyond the scope
除了选择QoS路径和可能保留相应资源的问题之外，应当注意，QoS保证的成功交付要求相关联的“QoS流”的分组在所选路径上转发。这通常需要在路由器中安装相应的转发状态。例如，对于RSVP[RZB+97]流，将根据RESV消息中包含的过滤器规格创建分类器条目。在区分服务[KNB98]设置的情况下，分类器条目可以基于目的地地址（或前缀）和DS字节的对应值。本文中描述的机制处于控制路径级别，因此独立于数据路径机制，例如所使用的分组分类方法。尽管如此，重要的是要注意，QoS保证的一致交付意味着数据路径的稳定性。特别是，虽然在第一次选择路径之后，网络条件可能发生变化并导致“更好”路径的出现，但应防止此类变化不必要地影响现有路径。特别是，切换到新的（更好的）路径应限于特定条件，例如，当初始选择结果不充分或极其“昂贵”时。这方面超出了范围
of QoS routing and belongs to the realm of path management, which is outside the main focus of this document. However, because of its potentially significant impact on the usefulness of QoS routing, we briefly outline a possible approach to path management.
属于路径管理领域，这超出了本文的主要重点。然而，由于它对QoS路由的有用性有潜在的重大影响，我们简要介绍了一种可能的路径管理方法。
Avoiding unnecessary changes to QoS paths requires that state information be maintained for each QoS path after it has been selected. This state information is used to track the validity of the path, i.e., is the current path adequate or should QoS routing be queried again to generate a new and potentially better path. We say that a path is "pinned" when its state specifies that QoS routing need not be queried anew, while a path is considered "un-pinned" otherwise. The main issue is then to define how, when, and where path pinning and un-pinning is to take place, and this will typically depend on the mechanism used to request QoS routes. For example, when the RSVP protocol is the mechanism being used, it is desirable that path management be kept as synergetic as possible with the existing RSVP state management. In other words, pinning and un-pinning of paths should be coordinated with RSVP soft states, and structured so as to require minimal changes to RSVP processing rules. A broad RSVP-routing interface that enables this is described in [GKR97]. Use of such an interface in the context of reserving resources along an explicit path with RSVP is discussed in [GLG+97]. Details of path management and a means for avoiding loops in case of hop-by-hop path setup can be found in [GKH97], and are not addressed further in this document.
为了避免对QoS路径进行不必要的更改，需要在选择每个QoS路径后为其维护状态信息。该状态信息用于跟踪路径的有效性，即当前路径是否足够，或者是否应再次查询QoS路由以生成新的、可能更好的路径。当路径的状态指定不需要重新查询QoS路由时，我们称其为“固定”，否则路径被视为“未固定”。然后，主要问题是定义路径固定和取消固定的方式、时间和地点，这通常取决于用于请求QoS路由的机制。例如，当使用RSVP协议时，希望路径管理尽可能与现有RSVP状态管理保持协同。换句话说，路径的固定和取消固定应与RSVP软状态相协调，并且其结构应确保对RSVP处理规则的更改最小。[GKR97]中描述了支持此功能的广泛RSVP路由接口。[GLG+97]中讨论了在使用RSVP沿显式路径保留资源的情况下使用此类接口。在逐跳路径设置的情况下，路径管理和避免循环的方法的详细信息可在[GKH97]中找到，本文档中不作进一步说明。
In order to achieve our goal of minimizing impact to the existing protocol and implementation, we impose certain restrictions on the range of extensions we initially consider to support QoS. The first restriction is on the type of additional (QoS) metrics that will be added to Link State Advertisements (LSAs) for the purpose of distributing metrics updates. Specifically, the extensions to LSAs that we initially consider, include only available bandwidth and delay. In addition, path selection is itself limited to considering only bandwidth requirements. In particular, the path selection algorithm selects paths capable of satisfying the bandwidth requirement of flows, while at the same time trying to minimize the amount of network resources that need to be allocated, i.e., minimize the number of hops used.
为了达到最小化对现有协议和实现的影响的目标，我们对最初支持QoS的扩展范围进行了一定限制。第一个限制是为了分发度量更新而添加到链路状态公告（LSA）中的附加（QoS）度量的类型。具体地说，我们最初考虑的LSA的扩展仅包括可用带宽和延迟。此外，路径选择本身仅限于考虑带宽要求。具体而言，路径选择算法选择能够满足流的带宽需求的路径，同时尝试最小化需要分配的网络资源量，即最小化使用的跳数。
This focus on bandwidth is adequate in most instances, and meant to keep initial complexity at an acceptable level. However, it does not fully capture the complete range of potential QoS requirements. For example, a delay-sensitive flow of an interactive application could be put on a path using a satellite link, if that link provided a
这种对带宽的关注在大多数情况下是足够的，并且意味着将初始复杂性保持在可接受的水平。然而，它并没有完全捕获潜在QoS需求的完整范围。例如，交互式应用程序的延迟敏感流可以通过卫星链路放在一条路径上，如果该链路提供
direct path and had plenty of unused bandwidth. This would clearly be an undesirable choice. Our approach to preventing such poor choices, is to assign delay-sensitive flows to a "policy" that would eliminate from the network all links with high propagation delay, e.g., satellite links, before invoking the path selection algorithm. In general, multiple policies could be used to capture different requirements, each presenting to the path selection algorithm a correspondingly pruned network topology, on which the same algorithm would be used to generate an appropriate path. Alternatively, different algorithms could be used depending on the QoS requirements expressed by an incoming request. Such extensions are beyond the scope of this document, which limits itself to describing the case of a single metric, bandwidth. However, it is worth pointing out that a simple extension to the path selection algorithm proposed in this document allows us to directly account for delay, under certain conditions, when rate-based schedulers are employed, as in the Guaranteed Service proposal [SPG97]; details can be found in [GOW97].
直接路径和大量未使用的带宽。这显然是一个不可取的选择。我们防止这种错误选择的方法是，在调用路径选择算法之前，将延迟敏感流分配给“策略”，该策略将从网络中消除所有具有高传播延迟的链路，例如卫星链路。一般来说，可以使用多个策略来捕获不同的需求，每个策略向路径选择算法呈现相应的修剪网络拓扑，在其上使用相同的算法来生成适当的路径。或者，根据传入请求表示的QoS要求，可以使用不同的算法。此类扩展超出了本文档的范围，本文档仅限于描述单个度量（带宽）的情况。然而，值得指出的是，本文中提出的路径选择算法的一个简单扩展允许我们在某些条件下，当采用基于速率的调度器时，直接考虑延迟，如保证服务建议[SPG97]；详情请参阅[GOW97]。
Another important aspect to ensure that introducing support for QoS routing has the minimal possible impact, is to develop a solution that has the smallest possible computing overhead. Additional computations are unavoidable, but it is desirable to keep the computational cost of QoS routing at a level comparable to that of traditional routing algorithms. One possible approach to achieve this goal, is to allow pre-computation of QoS routes. This is the method that was chosen for the implementation of the QoS extensions to OSPF and is, therefore, the one described in detail in this document. Alternative approaches are briefly reviewed in appendices. However, it should be noted that although several alternative path selection algorithms are possible, the same algorithm should be used consistently within a given routing domain. This requirement may be relaxed when explicit routing is used, as the responsibility for selecting a QoS path lies with a single entity, the origin of the request, which then ensures consistency even if each router uses a different path selection algorithm. Nevertheless, the use of a common path selection algorithm within an AS is recommended, if not necessary, for proper operation.
另一个重要的方面是开发一个计算开销最小的解决方案，以确保引入对QoS路由的支持具有最小的可能影响。额外的计算是不可避免的，但最好将QoS路由的计算成本保持在与传统路由算法相当的水平。实现这一目标的一种可能方法是允许预先计算QoS路由。这是为实现OSPF的QoS扩展而选择的方法，因此，这是本文档中详细描述的方法。附录中简要回顾了替代方法。然而，应该注意的是，尽管有几种可选的路径选择算法是可能的，但是在给定的路由域中应该一致地使用相同的算法。当使用显式路由时，这一要求可以放宽，因为选择QoS路径的责任在于单个实体，即请求的来源，这样即使每个路由器使用不同的路径选择算法，也可以确保一致性。然而，如果没有必要，建议在AS中使用公共路径选择算法以实现正确的操作。
A last aspect of concern regarding the introduction of QoS routing, is to control the overhead associated with the additional link state updates caused by more frequent changes to link metrics. The goal is to minimize the amount of additional update traffic without adversely affecting the performance of path selection. In Section 2.2, we present a brief discussion of various alternatives that trade accuracy of link state information for protocol overhead. Potential enhancements to the path selection algorithm, which seek to (directly) account for the inaccuracies in link metrics, are described in [GOW97], while a comprehensive treatment of the subject
关于引入QoS路由的最后一个关注点是控制与链路度量的更频繁更改引起的额外链路状态更新相关的开销。目标是在不影响路径选择性能的情况下，最大限度地减少额外的更新流量。在第2.2节中，我们简要讨论了以链路状态信息的准确性换取协议开销的各种备选方案。[GOW97]中描述了对路径选择算法的潜在增强，该算法寻求（直接）解释链路度量中的不精确性，同时对该主题进行了综合处理
can be found in [LO98, GO99]. In Section 4, we also describe the design choices made in a reference implementation, to allow future extensions and experimentation with different link state update mechanisms.
可在[LO98，GO99]中找到。在第4节中，我们还描述了在参考实现中做出的设计选择，以允许将来使用不同的链路状态更新机制进行扩展和实验。
The rest of this document is structured as follows. In Section 2, we describe the general design choices and mechanisms we rely on to support QoS request. This includes details on the path selection metrics, link state update extensions, and the path selection algorithm itself. Section 3 focuses on the specific extensions that the OSPF protocol requires, while Section 4 describes their implementation in the GateD platform and also presents some experimental results. Section 5 briefly addresses security issues that the proposed schemes may raise. Finally, several appendices provide additional material of interest, e.g., alternative path selection algorithms and support for explicit routes, but somewhat outside the main focus of this document.
本文件其余部分的结构如下。在第2节中，我们描述了支持QoS请求所依赖的一般设计选择和机制。这包括有关路径选择度量、链路状态更新扩展以及路径选择算法本身的详细信息。第3节重点介绍OSPF协议需要的特定扩展，而第4节描述了它们在门控平台中的实现，并给出了一些实验结果。第5节简要介绍了拟议方案可能提出的安全问题。最后，几个附录提供了其他感兴趣的材料，例如，替代路径选择算法和对显式路由的支持，但有些超出了本文档的主要重点。
This section reviews the basic building blocks of QoS path selection, namely the metrics on the which the routing algorithm operates, the mechanisms used to propagate updates for these metrics, and finally the path selection algorithm itself.
本节回顾QoS路径选择的基本构建块，即路由算法操作的度量、用于传播这些度量的更新的机制，最后是路径选择算法本身。
The process of selecting a path that can satisfy the QoS requirements of a new flow relies on both the knowledge of the flow's requirements and characteristics, and information about the availability of resources in the network. In addition, for purposes of efficiency, it is also important for the algorithm to account for the amount of resources the network has to allocate to support a new flow. In general, the network prefers to select the "cheapest" path among all paths suitable for a new flow, and it may even decide not to accept a new flow for which a feasible path exists, if the cost of the path is deemed too high. Accounting for these aspects involves several metrics on which the path selection process is based. They include:
选择能够满足新流的QoS要求的路径的过程依赖于流的要求和特性的知识，以及关于网络中资源可用性的信息。此外，为了提高效率，算法还必须考虑网络为支持新流而必须分配的资源量。通常，网络倾向于在适合新流的所有路径中选择“最便宜”的路径，并且如果认为路径的成本太高，它甚至可能决定不接受存在可行路径的新流。考虑这些方面涉及路径选择过程所基于的几个指标。这些措施包括：
- Link available bandwidth: As mentioned earlier, we currently assume that most QoS requirements are derivable from a rate-related quantity, termed "bandwidth." We further assume that associated with each link is a maximal bandwidth value, e.g., the link physical bandwidth or some fraction thereof that has been set aside for QoS flows. Since for a link to be capable of accepting a new flow with given bandwidth requirements, at least that much bandwidth must be still available on the link, the relevant link metric is, therefore, the (current) amount of available (i.e.,
- 链路可用带宽：如前所述，我们目前假设大多数QoS需求可从速率相关量（称为“带宽”）推导得出。我们进一步假设与每个链路相关联的是最大带宽值，例如，链路物理带宽或为QoS流预留的部分带宽。由于为了使链路能够接受具有给定带宽要求的新流，链路上必须至少有那么多带宽仍然可用，因此，相关链路度量是可用带宽的（当前）量（即。，
unallocated) bandwidth. Changes in this metric need to be advertised as part of extended LSAs, so that accurate information is available to the path selection algorithm.
未分配的）带宽。此度量的更改需要作为扩展LSA的一部分进行公布，以便路径选择算法能够获得准确的信息。
- Link propagation delay: This quantity is meant to identify high latency links, e.g., satellite links, which may be unsuitable for real-time requests. This quantity also needs to be advertised as part of extended LSAs, although timely dissemination of this information is not critical as this parameter is unlikely to change (significantly) over time. As mentioned earlier, link propagation delay can be used to decide on the pruning of specific links, when selecting a path for a delay sensitive request; also, it can be used to support a related extension, as described in [GOW97].
- 链路传播延迟：该数量用于识别可能不适合实时请求的高延迟链路，例如卫星链路。该数量也需要作为扩展LSA的一部分进行宣传，尽管及时传播该信息并不重要，因为该参数不太可能随时间发生（显著）变化。如前所述，当为延迟敏感请求选择路径时，链路传播延迟可用于决定特定链路的修剪；此外，它还可用于支持相关扩展，如[GOW97]所述。
- Hop-count: This quantity is used as a measure of the path cost to the network. A path with a smaller number of hops (that can support a requested connection) is typically preferable, since it consumes fewer network resources. As a result, the path selection algorithm will attempt to find the minimum hop path capable of satisfying the requirements of a given request. Note that contrary to bandwidth and propagation delay, hop count is a metric that does not affect LSAs, and it is only used implicitly as part of the path selection algorithm.
- 跃点计数：该数量用作网络路径成本的度量。具有较小跳数（可支持请求的连接）的路径通常更可取，因为它消耗较少的网络资源。因此，路径选择算法将试图找到能够满足给定请求要求的最小跳数路径。请注意，与带宽和传播延迟相反，跳数是一个不影响LSA的度量，它仅作为路径选择算法的一部分隐式使用。
The new link metrics identified in the previous section need to be advertised across the network, so that each router can compute accurate and consistent QoS routes. It is assumed that each router maintains an updated database of the network topology, including the current state (available bandwidth and propagation delay) of each link. As mentioned before, the distribution of link state (metrics) information is based on extending OSPF mechanisms. The detailed format of those extensions is described in Section 3, but in addition to how link state information is distributed, another important aspect is when such distribution is to take place.
上一节中确定的新链路指标需要在网络上公布，以便每个路由器能够计算准确一致的QoS路由。假设每个路由器维护网络拓扑的更新数据库，包括每个链路的当前状态（可用带宽和传播延迟）。如前所述，链路状态（度量）信息的分布基于扩展OSPF机制。这些扩展的详细格式在第3节中描述，但除了如何分发链路状态信息外，另一个重要方面是何时进行此类分发。
One option is to mandate periodic updates, where the period of updates is determined based on a tolerable corresponding load on the network and the routers. The main disadvantage of such an approach is that major changes in the bandwidth available on a link could remain unknown for a full period and, therefore, result in many incorrect routing decisions. Ideally, routers should have the most current view of the bandwidth available on all links in the network, so that they can make the most accurate decision of which path to select. Unfortunately, this then calls for very frequent updates, e.g., each time the available bandwidth of a link changes, which is
一种选择是强制执行定期更新，其中更新周期基于网络和路由器上可容忍的相应负载来确定。这种方法的主要缺点是，链路上可用带宽的重大变化可能在一整段时间内都是未知的，因此会导致许多错误的路由决策。理想情况下，路由器应该拥有网络中所有链路上可用带宽的最新视图，以便它们能够最准确地决定选择哪条路径。不幸的是，这需要非常频繁的更新，例如，每次链路的可用带宽发生变化时，这是
neither scalable nor practical. In general, there is a trade-off between the protocol overhead of frequent updates and the accuracy of the network state information that the path selection algorithm depends on. We outline next a few possible link state update policies, which strike a practical compromise.
既不可扩展也不实用。通常，在频繁更新的协议开销和路径选择算法所依赖的网络状态信息的准确性之间存在权衡。接下来，我们将概述几种可能的链路状态更新策略，它们达成了实际的折衷。
The basic idea is to trigger link state advertisements only when there is a significant change in the value of metrics since the last advertisement. The notion of significance of a change can be based on an "absolute" scale or a "relative" one. An absolute scale means partitioning the range of values that a metric can take into equivalence classes and triggering an update whenever the metric changes sufficiently to cross a class boundary (3). A relative scale, on the other hand, triggers updates when the percentage change in the metric value exceeds a predefined threshold. Independent of whether a relative or an absolute change trigger mechanism is used, a periodic trigger constraint can also be added. This constraint can be in the form of a hold-down timer, which is used to force a minimum spacing between consecutive updates. Alternatively, a transmit timer can also be used to ensure the transmission of an update after a certain time has expired. Such a feature can be useful if link state updates advertising bandwidth changes are sent unreliably. The current protocol extensions described in Section 3 as well as the implementation of Section 4 do not consider such an option as metric updates are sent using the standard, and reliable, OSPF flooding mechanism. However, this is clearly an extension worth considering as it can help lower substantially the protocol overhead associated with metrics updates.
其基本思想是，仅当自上次发布以来度量值发生重大变化时，才触发链接状态发布。变化的重要性概念可以基于“绝对”尺度或“相对”尺度。绝对尺度意味着将度量值的范围划分为等价类，并在度量值发生足够大的变化以跨越类边界时触发更新（3）。另一方面，当度量值的百分比变化超过预定义的阈值时，相对比例会触发更新。无论使用相对还是绝对更改触发机制，也可以添加周期性触发约束。此约束可以是按住计时器的形式，用于强制连续更新之间的最小间隔。或者，也可以使用发送定时器来确保在特定时间到期后发送更新。如果不可靠地发送链路状态更新和带宽更改，则此功能可能很有用。在第3节中描述的当前协议扩展以及第4节的实现不考虑这样的选项，即使用标准的可靠的OSPF洪泛机制发送度量更新。然而，这显然是一个值得考虑的扩展，因为它可以帮助显著降低与度量更新相关的协议开销。
In both the relative and absolute change approaches, the metric value advertised in an LSA can be either the actual or a quantized value. Advertising the actual metric value is more accurate and, therefore, preferable when metrics are frequently updated. On the other hand, when updates are less frequent, e.g., because of a low sensitivity trigger or the use of hold-down timers, advertising quantized values can be of benefit. This is because it can help increase the number of equal cost paths and, therefore, improve robustness to metrics inaccuracies. In general, there is a broad space of possible trade-offs between accuracy and overhead and selecting an appropriate design point is difficult and depends on many parameters (see [AGKT98] for a more detailed discussion of these issues). As a result, in order to help acquire a better understanding of these issues, the implementation described in Section 4 supports a range of options that allow exploration of the available design space. In addition, Section 4 also reports experimental data on the traffic load and processing overhead generated by links state updates for different configurations.
在相对和绝对变化方法中，LSA中公布的度量值可以是实际值或量化值。公布实际度量值更准确，因此，在频繁更新度量值时更可取。另一方面，当更新频率较低时，例如，由于低灵敏度触发器或使用抑制定时器，广告量化值可能是有益的。这是因为它可以帮助增加等成本路径的数量，从而提高对度量不准确的鲁棒性。一般来说，在精度和开销之间存在广泛的可能权衡空间，选择合适的设计点很困难，并且取决于许多参数（有关这些问题的更详细讨论，请参见[AGKT98]）。因此，为了帮助更好地理解这些问题，第4节中描述的实施支持一系列选项，允许探索可用的设计空间。此外，第4节还报告了不同配置的链路状态更新产生的流量负载和处理开销的实验数据。
There are two major aspects to computing paths for QoS requests. The first is the actual path selection algorithm itself, i.e., which metrics and criteria it relies on. The second is when the algorithm is actually invoked.
计算QoS请求的路径有两个主要方面。第一个是实际的路径选择算法本身，即它所依赖的度量和标准。第二个是算法实际被调用的时间。
The topology on which the algorithm is run is, as with the standard OSPF path selection, a directed graph where vertices (4) consist of routers and networks (transit vertices) as well as stub networks (non-transit vertices). When computing a path, stub networks are added as a post-processing step, which is essentially similar to what is done with the current OSPF routing protocol. The optimization criteria used by the path selection are reflected in the costs associated with each interface in the topology and how those costs are accounted for in the algorithm itself. As mentioned before, the cost of a path is a function of both its hop count and the amount of available bandwidth. As a result, each interface has associated with it a metric, which corresponds to the amount of bandwidth that remains available on this interface. This metric is combined with hop count information to provide a cost value, whose goal is to pick a path with the minimum possible number of hops among those that can support the requested bandwidth. When several such paths are available, the preference is for the path whose available bandwidth (i.e., the smallest value on any of the links in the path) is maximal. The rationale for the above rule is the following: we focus on feasible paths (as accounted by the available bandwidth metric) that consume a minimal amount of network resources (as accounted by the hop-count metric); and the rule for selecting among these paths is meant to balance load as well as maximize the likelihood that the required bandwidth is indeed available.
与标准OSPF路径选择一样，运行算法的拓扑是一个有向图，其中顶点（4）由路由器和网络（中转顶点）以及存根网络（非中转顶点）组成。在计算路径时，存根网络作为后处理步骤添加，这与当前OSPF路由协议的操作基本相似。路径选择使用的优化标准反映在拓扑中与每个接口相关的成本中，以及这些成本在算法本身中的计算方式。如前所述，路径的成本是其跳数和可用带宽量的函数。因此，每个接口都与一个度量相关联，该度量对应于此接口上保持可用的带宽量。该度量与跳数信息相结合，以提供成本值，其目标是在能够支持请求带宽的跳数中选择具有最小可能跳数的路径。当多个这样的路径可用时，首选可用带宽（即，路径中任何链路上的最小值）最大的路径。上述规则的基本原理如下：我们关注消耗最少网络资源的可行路径（如可用带宽指标所述）（如跳数指标所述）；在这些路径中进行选择的规则旨在平衡负载，并最大限度地提高所需带宽确实可用的可能性。
It should be noted that standard routing algorithms are typically single objective optimizations, i.e., they may minimize the hop-count, or maximize the path bandwidth, but not both. Double objective path optimization is a more complex task, and, in general, it is an intractable problem [GJ79]. Nevertheless, because of the specific nature of the two objectives being optimized (bandwidth and hop count), the complexity of the above algorithm is competitive with even that of standard single-objective algorithms. For readers interested in a thorough treatment of the topic, with insights into the connection between the different algorithms, linear algebra and modification of metrics, [Car79] is recommended.
应该注意的是，标准路由算法通常是单目标优化，也就是说，它们可以最小化跳数或最大化路径带宽，但不能两者兼而有之。双目标路径优化是一项更为复杂的任务，通常是一个棘手的问题[GJ79]。然而，由于优化的两个目标（带宽和跳数）的特殊性质，上述算法的复杂性甚至与标准单目标算法的复杂性相竞争。对于对该主题有兴趣的读者，建议读者深入了解不同算法、线性代数和度量修改之间的联系[Car79]。
Before proceeding with a more detailed description of the path selection algorithm itself, we briefly review the available options when it comes to deciding when to invoke the algorithm. The two main options are: 1) to perform on-demand computations, that is, trigger
在继续对路径选择算法本身进行更详细的描述之前，我们简要回顾了在决定何时调用该算法时可用的选项。两个主要选项是：1）执行按需计算，即触发
a computation for each new request, and 2) to use some form of pre-computation. The on-demand case involves no additional issues in terms of when computations should be triggered, but running the path selection algorithm for each new request can be computationally expensive (see [AT98] for a discussion on this issue). On the other hand, pre-computing paths amortizes the computational cost over multiple requests, but each computation instance is usually more expensive than in the on-demand case (paths are computed to all destinations and for all possible bandwidth requests rather than for a single destination and a given bandwidth request). Furthermore, depending on how often paths are recomputed, the accuracy of the selected paths may be lower. In this document, we primarily focus on the case of pre-computed paths, which is also the only method currently supported in the reference implementation described in Section 4. In this case, clearly, an important issue is when such pre-computation should take place. The two main options we consider are periodic pre-computations and pre-computations after a given (N) number of updates have been received. The former has the benefit of ensuring a strict bound on the computational load associated with pre-computations, while the latter can provide for a more responsive solution (5). Section 4 provides some experimental results comparing the performance and cost of periodic pre-computations for different period values.
每个新请求的计算，以及2）使用某种形式的预计算。按需情况下，在何时应触发计算方面不涉及其他问题，但为每个新请求运行路径选择算法可能会在计算上花费很大（有关此问题的讨论，请参阅[AT98]）。另一方面，预计算路径将计算成本分摊到多个请求上，但每个计算实例通常比按需情况下更昂贵（路径计算到所有目的地和所有可能的带宽请求，而不是单个目的地和给定带宽请求）。此外，取决于路径重新计算的频率，所选路径的精度可能较低。在本文档中，我们主要关注预计算路径的情况，这也是第4节中描述的参考实现中当前支持的唯一方法。显然，在这种情况下，一个重要的问题是何时进行这种预计算。我们考虑的两个主要选项是在接收到给定（n）个更新之后的周期性预计算和预计算。前者的优点是确保与预计算相关的计算负载有严格的界限，而后者可以提供更具响应性的解决方案（5）。第4节提供了一些实验结果，比较了不同周期值的定期预计算的性能和成本。
This section describes a path selection algorithm, which for a given network topology and link metrics (available bandwidth), pre-computes all possible QoS paths, while maintaining a reasonably low computational complexity. Specifically, the algorithm pre-computes for any destination a minimum hop count path with maximum bandwidth, and has a computational complexity comparable to that of a standard Bellman-Ford shortest path algorithm. The Bellman-Ford (BF) shortest path algorithm is adapted to compute paths of maximum available bandwidth for all hop counts. It is a property of the BF algorithm that, at its h-th iteration, it identifies the optimal (in our context: maximal bandwidth) path between the source and each destination, among paths of at most h hops. In other words, the cost of a path is a function of its available bandwidth, i.e., the smallest available bandwidth on all links of the path, and finding a minimum cost path amounts to finding a maximum bandwidth path. However, because the BF algorithm progresses by increasing hop count, it essentially provides for free the hop count of a path as a second optimization criteria.
本节介绍一种路径选择算法，该算法针对给定的网络拓扑和链路度量（可用带宽），预先计算所有可能的QoS路径，同时保持合理的低计算复杂度。具体地说，该算法为任何目的地预先计算具有最大带宽的最小跳数路径，并且具有与标准Bellman-Ford最短路径算法相当的计算复杂度。Bellman-Ford（BF）最短路径算法适用于计算所有跳数的最大可用带宽路径。BF算法的一个特性是，在其第h次迭代时，它在最多h跳的路径中确定源和每个目的地之间的最佳（在我们的上下文中：最大带宽）路径。换句话说，路径的成本是其可用带宽的函数，即，路径的所有链路上的最小可用带宽，找到最小成本路径等于找到最大带宽路径。然而，由于BF算法是通过增加跳数来进行的，因此它本质上提供了免费的路径跳数作为第二个优化标准。
Specifically, at the kth (hop count) iteration of the algorithm, the maximum bandwidth available to all destinations on a path of no more than k hops is recorded (together with the corresponding routing
具体地说，在算法的第k次（跳数）迭代时，记录不超过k跳的路径上所有目的地可用的最大带宽（以及相应的路由）
information). After the algorithm terminates, this information provides for all destinations and bandwidth requirements, the path with the smallest possible number of hops and sufficient bandwidth to accommodate the new request. Furthermore, this path is also the one with the maximal available bandwidth among all the feasible paths with at most these many hops. This is because for any hop count, the algorithm always selects the one with maximum available bandwidth.
信息）。在算法终止后，该信息提供所有目的地和带宽要求、具有最小可能跳数的路径和足够带宽以适应新请求。此外，在最多跳数的所有可行路径中，该路径也是可用带宽最大的路径。这是因为对于任何跳数，算法总是选择具有最大可用带宽的跳数。
We now proceed with a more detailed description of the algorithm and the data structure used to record routing information, i.e., the QoS routing table that gets built as the algorithm progresses (the pseudo-code for the algorithm can be found in Appendix A). As mentioned before, the algorithm operates on a directed graph consisting only of transit vertices (routers and networks), with stub-networks subsequently added to the path(s) generated by the algorithm. The metric associated with each edge in the graph is the bandwidth available on the corresponding interface. Let us denote by b(n;m) the available bandwidth on the link from node n to m. The vertex corresponding to the router where the algorithm is being run, i.e., the computing router, is denoted as the "source node" for the purpose of path selection. The algorithm proceeds to pre-compute paths from this source node to all possible destination networks and for all possible bandwidth values. At each (hop count) iteration, intermediate results are recorded in a QoS routing table, which has the following structure:
现在，我们继续对算法和用于记录路由信息的数据结构进行更详细的描述，即随着算法的进展而构建的QoS路由表（算法的伪代码可在附录a中找到）。如前所述，该算法在一个仅由中转顶点（路由器和网络）组成的有向图上运行，随后将存根网络添加到该算法生成的路径中。与图中每条边关联的度量是相应接口上的可用带宽。让我们用b（n；m）表示从节点n到m的链路上的可用带宽。与运行算法的路由器（即计算路由器）对应的顶点被表示为“源节点”，用于路径选择。该算法继续预计算从该源节点到所有可能的目标网络的路径以及所有可能的带宽值。在每次（跃点计数）迭代中，中间结果记录在QoS路由表中，该表具有以下结构：
The QoS routing table:
QoS路由表：
- a KxH matrix, where K is the number of destinations (vertices in the graph) and H is the maximal allowed (or possible) number of hops for a path.
- 一个KxH矩阵，其中K是目的地（图中的顶点）的数量，H是路径允许（或可能）的最大跳数。
- The (n;h) entry is built during the hth iteration (hop count value) of the algorithm, and consists of two fields:
- （n；h）项是在算法的hth迭代（跃点计数值）期间生成的，它由两个字段组成：
* bw: the maximum available bandwidth, on a path of at most h hops between the source node (router) and destination node n;
* bw：最大可用带宽，在源节点（路由器）和目标节点n之间最多h个跃点的路径上；
* neighbor: this is the routing information associated with the h (or less) hops path to destination node n, whose available bandwidth is bw. In the context of hop-by-hop path selection (6), the neighbor information is simply the identity of the node adjacent to the source node on that path. As a rule, the "neighbor" node must be a router and not a network, the only exception being the case where the network is the destination node (and the selected path is the single edge interconnecting the source to it).
* 邻居：这是与到目标节点n的h（或更少）跳路径相关联的路由信息，其可用带宽为bw。在逐跳路径选择（6）的上下文中，邻居信息只是该路径上与源节点相邻的节点的标识。通常，“邻居”节点必须是路由器，而不是网络，唯一的例外是网络是目标节点的情况（所选路径是将源节点与之互连的单边）。
Next, we provide additional details on the operation of the algorithm and how the entries in the routing table are updated as the algorithm proceeds. For simplicity, we first describe the simpler case where all edges count as "hops," and later explain how zero-hop edges are handled. Zero-hop edges arise in the case of transit networks vertices, where only one of the two incoming and outgoing edges should be counted in the hop count computation, as they both correspond to the same physical hop. Accounting for this aspect requires distinguishing between network and router nodes, and the steps involved are detailed later in this section as well as in the pseudo-code of Appendix A.
接下来，我们将提供有关该算法操作的更多详细信息，以及如何在算法进行时更新路由表中的条目。为了简单起见，我们首先描述了一种更简单的情况，即所有边都计算为“跳数”，然后解释如何处理零跳边。零跳边出现在公交网络顶点的情况下，在跳数计算中，两条传入和传出边中只有一条应被计数，因为它们都对应于相同的物理跳。考虑到这一点，需要区分网络节点和路由器节点，相关步骤将在本节后面以及附录A的伪代码中详细说明。
When the algorithm is invoked, the routing table is first initialized with all bw fields set to 0 and neighbor fields cleared. Next, the entries in the first column (which corresponds to one-hop paths) of the neighbors of the computing router are modified in the following way: the bw field is set to the value of the available bandwidth on the direct edge from the source. The neighbor field is set to the identity of the neighbor of the computing router, i.e., the next router on the selected path.
调用该算法时，首先初始化路由表，将所有bw字段设置为0，并清除邻居字段。接下来，以以下方式修改计算路由器的邻居的第一列（对应于一跳路径）中的条目：bw字段被设置为来自源的直接边缘上的可用带宽的值。邻居字段设置为计算路由器的邻居的身份，即所选路径上的下一个路由器。
Afterwards, the algorithm iterates for at most H iterations (considering the above initial iteration as the first). The value of H could be implicit, i.e., the diameter of the network or, in order to better control the worst case complexity, it can be set explicitly thereby limiting path lengths to at most H hops. In the latter case, H must be assigned a value larger than the length of the minimum hop-count path to any node in the graph.
之后，该算法最多迭代H次（将上述初始迭代视为第一次迭代）。H的值可以是隐式的，即网络的直径，或者，为了更好地控制最坏情况的复杂性，可以显式地设置它，从而将路径长度限制为最多H跳。在后一种情况下，必须为H分配一个大于图中任何节点的最小跳数路径长度的值。
At iteration h, we first copy column h-1 into column h. In addition, the algorithm keeps a list of nodes that changed their bw value in the previous iteration, i.e., during the (h-1)-th iteration. The algorithm then looks at each link (n;m) where n is a node whose bw value changed in the previous iteration, and checks the maximal available bandwidth on an (at most) h-hop path to node m whose final hop is that link. This amounts to taking the minimum between the bw field in entry (n;h-1) and the link metric value b(n;m) kept in the topology database. If this value is higher than the present value of the bw field in entry (m;h), then a better (larger bw value) path has been found for destination m and with at most h hops. The bw field of entry (m;h) is then updated to reflect this new value. In the case of hop-by-hop routing, the neighbor field of entry (m;h) is set to the same value as in entry (n;h-1). This records the identity of the first hop (next hop from the source) on the best path identified thus far for destination m and with h (or less) hops.
在迭代h中，我们首先将列h-1复制到列h中。此外，该算法还保留了在上一次迭代（即在（h-1）次迭代中）更改其bw值的节点列表。然后，该算法查看每个链路（n；m），其中n是一个节点，其bw值在上一次迭代中发生了变化，并检查（最多）到节点m的h-hop路径上的最大可用带宽，节点m的最后一跳就是该链路。这相当于在条目（n；h-1）中的bw字段和拓扑数据库中保存的链路度量值b（n；m）之间取最小值。如果该值高于条目（m；h）中bw字段的当前值，则为目标m找到了一条更好的（更大的bw值）路径，最多有h个跃点。然后更新bw输入字段（m；h）以反映此新值。在逐跳路由的情况下，条目的邻居字段（m；h）设置为与条目（n；h-1）中相同的值。这记录了迄今为止为目的地m识别的最佳路径上的第一跳（来自源的下一跳）的身份，以及具有h个（或更少）跳的身份。
As mentioned earlier, extending the above algorithm to handle zero-hop edges is needed due to the possible use of multi-access networks, e.g., T/R, E/N, etc., to interconnect routers. Such entities are also represented by means of a vertex in the OSPF topology, but a network connecting two routers should clearly be considered as a single hop path rather than a two hop path. For example, consider three routers A, B, and C connected over an Ethernet network N, which the OSPF topology represents as in Figure 1.
如前所述，由于可能使用多接入网络（例如T/R、e/N等）来互连路由器，因此需要扩展上述算法以处理零跳边缘。这些实体也通过OSPF拓扑中的顶点来表示，但是连接两个路由器的网络显然应该被视为单跳路径，而不是两跳路径。例如，考虑在以太网网络N上连接的三个路由器A、B和C，OSPF拓扑结构如图1所示。
A----N----B
|
|
C
A----N----B
|
|
C
Figure 1: Zero-Hop Edges
图1：零跳边
In the example of Figure 1, although there are directed edges in both directions, an edge from the network to any of the three routers must have zero "cost", so that it is not counted twice. It should be noted that when considering such environments in the context of QoS routing, it is assumed that some entity is responsible for determining the "available bandwidth" on the network, e.g., a subnet bandwidth manager. The specification and operation of such an entity is beyond the scope of this document.
在图1的示例中，尽管在两个方向上都有定向边，但从网络到三个路由器中任何一个的边必须具有零“成本”，因此它不会被计算两次。应注意，当在QoS路由的上下文中考虑此类环境时，假定某些实体负责确定网络上的“可用带宽”，例如子网带宽管理器。此类实体的规范和操作超出了本文件的范围。
Accommodating zero-hop edges in the context of the path selection algorithm described above is done as follows: At each iteration h (starting with the first), whenever an entry (m;h) is modified, it is checked whether there are zero-cost edges (m;k) emerging from node m. This is the case when m is a transit network. In that case, we attempt to further improve the entry of node k within the current iteration, i.e., entry (k;h) (rather than entry (k;h+1)), since the edge (m;k) should not count as an additional hop. As with the regular operation of the algorithm, this amounts to taking the minimum between the bw field in entry (m;h) and the link metric value b(m;k) kept in the topology database (7). If this value is higher than the present value of the bw field in entry (k;h), then the bw field of entry (k;h) is updated to this new value. In the case of hop-by-hop routing, the neighbor field of entry (k;h) is set, as usual, to the same value as in entry (m;h) (which is also the value in entry (n;h-1)).
在上述路径选择算法的上下文中容纳零跳边如下所述：在每次迭代h（从第一次开始），每当修改条目（m；h）时，检查是否存在从节点m出现的零代价边（m；k）。当m是公交网络时，就是这种情况。在这种情况下，我们尝试在当前迭代中进一步改进节点k的入口，即入口（k；h）（而不是入口（k；h+1）），因为边缘（m；k）不应计为额外的跳。与算法的常规操作一样，这相当于在条目（m；h）中的bw字段和拓扑数据库（7）中保存的链路度量值b（m；k）之间取最小值。如果该值高于条目（k；h）中bw字段的当前值，则条目（k；h）中的bw字段将更新为该新值。在逐跳路由的情况下，条目（k；h）的邻居字段通常被设置为与条目（m；h）中的值相同的值（这也是条目（n；h-1）中的值）。
Note that while for simplicity of the exposition, the issue of equal cost, i.e., same hop count and available bandwidth, is not detailed in the above description, it can be easily supported. It only requires that the neighbor field be expanded to record the list of next (previous) hops, when multiple equal cost paths are present.
注意，虽然为了简化说明，相同成本的问题，即相同的跳数和可用带宽，在上述描述中没有详细说明，但是可以容易地支持。当存在多个等成本路径时，它只需要扩展邻居字段以记录下一个（上一个）跳的列表。
Addition of Stub Networks
添加存根网络
As was mentioned earlier, the path selection algorithm is run on a graph whose vertices consist only of routers and transit networks and not stub networks. This is intended to keep the computational complexity as low as possible as stub networks can be added relatively easily through a post-processing step. This second processing step is similar to the one used in the current OSPF routing table calculation [Moy98], with some differences to account for the QoS nature of routes.
如前所述，路径选择算法在顶点仅由路由器和公交网络而非存根网络组成的图上运行。这是为了保持尽可能低的计算复杂度，因为可以通过后处理步骤相对容易地添加存根网络。第二个处理步骤与当前OSPF路由表计算[Moy98]中使用的步骤类似，但在考虑路由的QoS性质方面存在一些差异。
Specifically, after the QoS routing table has been constructed, all the router vertices are again considered. For each router, stub networks whose links appear in the router's link advertisements will be processed to determine QoS routes available to them. The QoS routing information for a stub network is similar to that of routers and transit networks and consists of an extension to the QoS routing table in the form of an additional row. The columns in that new row again correspond to paths of different hop counts, and contain both bandwidth and next hop information. We also assume that an available bandwidth value has been advertised for the stub network. As before, how this value is determined is beyond the scope of this document. The QoS routes for a stub network S are constructed as follows:
具体地说，在构造QoS路由表之后，再次考虑所有路由器顶点。对于每个路由器，其链路出现在路由器链路公告中的存根网络将被处理以确定它们可用的QoS路由。存根网络的QoS路由信息类似于路由器和传输网络的QoS路由信息，并以附加行的形式包含QoS路由表的扩展。新行中的列再次对应于不同跳数的路径，并且包含带宽和下一跳信息。我们还假设为存根网络发布了可用带宽值。如前所述，如何确定该值超出了本文档的范围。存根网络的QoS路由构造如下：
Each entry in the row corresponding to stub network S has its bw(s) field initialized to zero and its neighbor set to null. When a stub network S is found in the link advertisement of router V, the value bw(S,h) in the hth column of the row corresponding to stub network S is updated as follows:
与存根网络对应的行中的每个条目都将其bw（S）字段初始化为零，并将其邻居设置为null。当在路由器V的链路通告中发现存根网络S时，对应于存根网络S的行的hth列中的值bw（S，h）更新如下：
bw(S,h) = max ( bw(S,h) ; min ( bw(V,h) , b(V,S) ) ),
bw（S，h）=最大（bw（S，h）；最小（bw（V，h），b（V，S）），
where bw(V,h) is the bandwidth value of the corresponding column for the QoS routing table row associated with router V, i.e., the bandwidth available on an h hop path to V, and b(V,S) is the advertised available bandwidth on the link from V to S. The above expression essentially states that the bandwidth of a h hop path to stub network S is updated using a path through router V, only if the minimum of the bandwidth of the h hop path to V and the bandwidth on the link between V and S is larger than the current value.
其中bw（V，h）是与路由器V相关联的QoS路由表行的对应列的带宽值，即，到V和b（V，S）的h跳路径上的可用带宽是从V到S的链路上的广告可用带宽。上述表达式基本上表示，只有当到V的h-hop路径的带宽和到V和S之间的链路上的带宽的最小值大于当前值时，才使用通过路由器V的路径更新到存根网络S的h-hop路径的带宽。
Update of the neighbor field proceeds similarly whenever the bandwidth of a path through V is found to be larger than or equal to the current value. If it is larger, then the neighbor field of V in the corresponding column replaces the current neighbor field of S. If it is equal, then the neighbor field of V in the corresponding column is concatenated with the existing field for S, i.e., the current set of neighbors for V is added to the current set of neighbors for S.
每当发现通过V的路径的带宽大于或等于当前值时，邻域字段的更新类似地进行。如果较大，则对应列中V的邻居字段替换S的当前邻居字段。如果相等，则对应列中V的邻居字段与S的现有字段串联，即V的当前邻居集添加到S的当前邻居集。
Extracting Forwarding Information from Routing Table
从路由表中提取转发信息
When the QoS paths are precomputed, the forwarding information for a flow with given destination and bandwidth requirement needs to be extracted from the routing table. The case of hop-by-hop routing is simpler than that of explicit routing. This is because, only the next hop needs to be returned instead of an explicit route.
当预先计算QoS路径时，需要从路由表中提取具有给定目的地和带宽要求的流的转发信息。逐跳路由的情况比显式路由简单。这是因为，只需要返回下一个跃点，而不是显式路由。
Specifically, assume a new request to destination, say, d, and with bandwidth requirements B. The index of the destination vertex identifies the row in the QoS routing table that needs to be checked to generate a path. Assuming that the QoS routing table was constructed using the Bellman-Ford algorithm presented later in this section, the search then proceeds by increasing index (hop) count until an entry is found, say at hop count or column index of h, with a value of the bw field which is equal to or larger than B. This entry points to the initial information identifying the selected path.
具体地说，假设一个到目的地的新请求，比如d，带宽要求B。目的地顶点的索引标识QoS路由表中需要检查以生成路径的行。假设QoS路由表是使用本节后面介绍的Bellman-Ford算法构建的，然后通过增加索引（跃点）计数进行搜索，直到找到一个条目，例如在跃点计数或列索引h处，bw字段的值等于或大于B。此入口指向标识所选路径的初始信息。
If the path computation algorithm stores multiple equal cost paths, then some degree of load balancing can be achieved at the time of path selection. A next hop from the list of equivalent next hops can be chosen in a round robin manner, or randomly with a probability that is weighted by the actual available bandwidth on the local interface. The latter is the method used in the implementation described in Section 4.
如果路径计算算法存储多个等成本路径，那么在选择路径时可以实现一定程度的负载平衡。从等效下一跳列表中的下一跳可以以循环方式选择，或者以由本地接口上的实际可用带宽加权的概率随机选择。后者是第4节描述的实现中使用的方法。
The case of explicit routing is discussed in Appendix D.
附录D中讨论了显式路由的情况。
As stated earlier, one of our goals is to limit the additions to the existing OSPF V2 protocol, while still providing the required level of support for QoS based routing. To this end, all of the existing OSPF mechanisms, data structures, advertisements, and data formats remain in place. The purpose of this section of the document is to describe the extensions to the OSPF protocol needed to support QoS as outlined in the previous sections.
如前所述，我们的目标之一是限制对现有OSPF V2协议的添加，同时仍然为基于QoS的路由提供所需级别的支持。为此，所有现有的OSPF机制、数据结构、广告和数据格式都保持不变。本文档本节的目的是描述支持QoS所需的OSPF协议扩展，如前几节所述。
The OSPF Options field is present in OSPF Hello packets, Database Description packets and all LSAs. The Options field enables OSPF routers to support (or not support) optional capabilities, and to communicate their capability level to other OSPF routers. Through this mechanism, routers of differing capabilities can be mixed within an OSPF routing domain. Currently, the OSPF standard [Moy98] specifies the following 5 bits in the options octet:
OSPF选项字段出现在OSPF Hello数据包、数据库描述数据包和所有LSA中。选项字段使OSPF路由器能够支持（或不支持）可选功能，并将其功能级别与其他OSPF路由器进行通信。通过这种机制，不同功能的路由器可以在OSPF路由域中混合使用。目前，OSPF标准[Moy98]在选项八位字节中指定以下5位：
+-----------------------------------------------+
| * | * | DC | EA | N/P | MC | E | * |
+-----------------------------------------------+
+-----------------------------------------------+
| * | * | DC | EA | N/P | MC | E | * |
+-----------------------------------------------+
Note that the least significant bit (`T' bit) that was used to indicate TOS routing capability in the older OSPF specification [Moy94] has been removed. However, for backward compatibility with previous versions of the OSPF specification, TOS-specific information can be included in router-LSAs, summary-LSAs and AS-external-LSAs.
请注意，在较旧的OSPF规范[Moy94]中，用于指示TOS路由能力的最低有效位（`T'位）已被删除。然而，为了与以前版本的OSPF规范向后兼容，TOS特定信息可以包含在路由器LSA、摘要LSA和外部LSA中。
We propose to reclaim the `T' bit as an indicator of router's QoS routing capability and refer to it as the `Q' bit. In fact, QoS capability can be viewed as an extension of the TOS-capabilities and QoS routing as a form of TOS-based routing. A router sets this bit in its hello packets to indicate that it is capable of supporting such routing. When this bit is set in a router or summary links link state advertisement, it means that there are QoS fields to process in the packet. When this bit is set in a network link state advertisement it means that the network described in the advertisement is QoS capable.
我们建议回收'T'位作为路由器QoS路由能力的指标，并将其称为'Q'位。事实上，QoS能力可以看作是TOS能力的扩展，QoS路由是基于TOS的路由的一种形式。路由器在其hello数据包中设置该位，以表明它能够支持这种路由。当在路由器或摘要链路链路状态播发中设置此位时，这意味着数据包中有要处理的QoS字段。当在网络链路状态播发中设置该位时，意味着播发中描述的网络具有QoS能力。
We need to be careful in this approach so as to avoid confusing any old style (i.e., RFC 1583 based) TOS routing implementations. The TOS metric encoding rules of QoS fields introduced further in this section will show how this is achieved. Additionally, unlike the RFC 1583 specification that unadvertised TOS metrics be treated to have same cost as TOS 0, for the purpose of computing QOS routes, unadvertised TOS metrics (on a hop) indicate lack of connectivity for the specific TOS metrics (for that hop).
在这种方法中，我们需要小心，以避免混淆任何旧式（即基于RFC1583的）TOS路由实现。本节进一步介绍的QoS字段的TOS度量编码规则将说明如何实现这一点。此外，与RFC 1583规范不同，RFC 1583规范将未经广告的TOS度量视为具有与TOS 0相同的成本，为了计算QOS路由，未经广告的TOS度量（在一个跃点上）指示特定TOS度量（对于该跃点）缺乏连接性。
Introduction of QoS should ideally not influence the compatibility with existing OSPFv2 routers. To achieve this goal, necessary extensions in packet formats must be defined in a way that either is understood by OSPFv2 routers, ignored, or in the worst case "gracefully" misinterpreted. Encoding of QoS metrics in the TOS field which fortunately enough is longer in OSPF packets than
QoS的引入在理想情况下不应影响与现有OSPFv2路由器的兼容性。为了实现这一目标，必须以OSPFv2路由器能够理解、忽略或在最坏情况下“优雅地”误解的方式定义数据包格式中的必要扩展。TOS字段中QoS度量的编码，幸运的是，OSPF数据包中的QoS度量比
officially defined in [Alm92], allows us to mimic the new facility as extended TOS capability. OSPFv2 routers will either disregard these definitions or consider those unspecified. Specific precautions are taken to prevent careless OSPF implementations from influencing traditional TOS routers (if any) when misinterpreting the QoS extensions.
[Alm92]中的正式定义允许我们将新设施模拟为扩展TOS能力。OSPFv2路由器要么忽略这些定义，要么考虑那些未指定的。在误解QoS扩展时，采取了特定的预防措施，以防止粗心的OSPF实施影响传统TOS路由器（如果有）。
For QoS resources, 32 combinations are available through the use of the fifth bit in TOS fields contained in different LSAs. Since [Alm92] defines TOS as being four bits long, this definition never conflicts with existing values. Additionally, to prevent naive implementations that do not take all bits of the TOS field in OSPF packets into considerations, the definitions of the `QoS encodings' is aligned in their semantics with the TOS encoding. Only bandwidth and delay are specified as of today and their values map onto `maximize throughput' and `minimize delay' if the most significant bit is not taken into account. Accordingly, link reliability and jitter could be defined later if necessary.
对于QoS资源，通过使用不同LSA中包含的TOS字段中的第五位，可以使用32种组合。由于[Alm92]将TOS定义为四位长，因此此定义从不与现有值冲突。此外，为了防止未考虑OSPF数据包中TOS字段的所有位的幼稚实现，“QoS编码”的定义在语义上与TOS编码一致。目前只指定了带宽和延迟，如果不考虑最高有效位，则它们的值映射到“最大吞吐量”和“最小化延迟”。因此，如有必要，可在稍后定义链路可靠性和抖动。
OSPF encoding RFC 1349 TOS values
___________________________________________
0 0000 normal service
2 0001 minimize monetary cost
4 0010 maximize reliability
6 0011
8 0100 maximize throughput
10 0101
12 0110
14 0111
16 1000 minimize delay
18 1001
20 1010
22 1011
24 1100
26 1101
28 1110
30 1111
OSPF encoding RFC 1349 TOS values
___________________________________________
0 0000 normal service
2 0001 minimize monetary cost
4 0010 maximize reliability
6 0011
8 0100 maximize throughput
10 0101
12 0110
14 0111
16 1000 minimize delay
18 1001
20 1010
22 1011
24 1100
26 1101
28 1110
30 1111
OSPF encoding `QoS encoding values'
OSPF编码“QoS编码值”
-------------------------------------------
32 10000
34 10001
36 10010
38 10011
40 10100 bandwidth
42 10101
44 10110
46 10111
48 11000 delay
50 11001
52 11010
54 11011
56 11100
58 11101
60 11110
62 11111
-------------------------------------------
32 10000
34 10001
36 10010
38 10011
40 10100 bandwidth
42 10101
44 10110
46 10111
48 11000 delay
50 11001
52 11010
54 11011
56 11100
58 11101
60 11110
62 11111
Representing TOS and QoS in OSPF.
在OSPF中表示TOS和QoS。
Given the fact that the actual metric field in OSPF packets only provides 16 bits to encode the value used and that links supporting bandwidth ranging into Gbits/s are becoming reality, linear representation of the available resource metric is not feasible. The solution is exponential encoding using appropriately chosen implicit base value and number bits for encoding mantissa and the exponent. Detailed considerations leading to the solution described are not presented here but can be found in [Prz95].
鉴于OSPF分组中的实际度量字段仅提供16位来编码所使用的值，并且支持到gbit/s的带宽范围的链路正在成为现实，可用资源度量的线性表示是不可行的。解决方案是使用适当选择的隐式基值和数字位对尾数和指数进行指数编码。此处未给出导致所述解决方案的详细注意事项，但可在[Prz95]中找到。
Given a base of 8, the 3 most significant bits should be reserved for the exponent part and the remaining 13 for the mantissa. This allows a simple comparison for two numbers encoded in this form, which is often useful during implementation.
如果基数为8，则指数部分应保留3个最高有效位，尾数部分应保留其余13个最高有效位。这允许对以这种形式编码的两个数字进行简单比较，这在实现过程中通常很有用。
The following table shows bandwidth ranges covered when using different exponents and the granularity of possible reservations.
下表显示了使用不同指数时覆盖的带宽范围以及可能保留的粒度。
exponent
value x range (2^13-1)*8^x step 8^x
-------------------------------------------------
0 8,191 1
1 65,528 8
2 524,224 64
3 4,193,792 512
4 33,550,336 4,096
5 268,402,688 32,768
6 2,147,221,504 262,144
7 17,177,772,032 2,097,152
exponent
value x range (2^13-1)*8^x step 8^x
-------------------------------------------------
0 8,191 1
1 65,528 8
2 524,224 64
3 4,193,792 512
4 33,550,336 4,096
5 268,402,688 32,768
6 2,147,221,504 262,144
7 17,177,772,032 2,097,152
Ranges of Exponent Values for 13 bits, base 8 Encoding, in Bytes/s
13位的指数值范围，基数为8编码，以字节/秒为单位
The bandwidth encoding rule may be summarized as: "represent available bandwidth in 16 bit field as a 3 bit exponent (with assumed base of 8) followed by a 13 bit mantissa as shown below and advertise 2's complement of the above representation."
带宽编码规则可以总结为：“将16位字段中的可用带宽表示为3位指数（假定基数为8），然后是13位尾数，如下所示，并公布2对上述表示的补充。”
0 8 16
| | |
-----------------
|EXP| MANT |
-----------------
0 8 16
| | |
-----------------
|EXP| MANT |
-----------------
Thus, the above encoding advertises a numeric value that is
因此，上述编码播发一个数值，该数值为
2^16 -1 -(exponential encoding of the available bandwidth):
2^16-1-（可用带宽的指数编码）：
This has the property of advertising a higher numeric value for lower available bandwidth, a notion that is consistent with that of cost.
它的特点是为较低的可用带宽宣传较高的数值，这一概念与成本一致。
Although it may seem slightly pedantic to insist on the property that less bandwidth is expressed higher values, it has, besides consistency, a robustness aspect in it. A router with a poor OSPF implementation could misuse or misunderstand bandwidth metric as normal administrative cost provided to it and compute spanning trees with a "normal" Dijkstra. The effect of a heavily congested link advertising numerically very low cost could be disastrous in such a scenario. It would raise the link's attractiveness for future traffic instead of lowering it. Evidence that such considerations are not speculative, but similar scenarios have been encountered, can be found in [Tan89].
虽然坚持带宽越小表示值越高的特性似乎有点迂腐，但除了一致性之外，它还有一个健壮性方面。OSPF实现不佳的路由器可能会误用或误解带宽指标，将其视为正常的管理成本，并使用“正常”Dijkstra计算生成树。在这种情况下，严重拥挤的链接广告成本非常低的效果可能是灾难性的。这将提高连接线对未来交通的吸引力，而不是降低它。[Tan89]中有证据表明，此类考虑不是推测性的，但也遇到过类似的情况。
Concluding with an example, assume a link with bandwidth of 8 Gbits/s = 1024^3 Bytes/s, its encoding would consist of an exponent value of 6 since 1024^3= 4,096*8^6, which would then have a granularity of 8^6 or approx. 260 kBytes/s. The associated binary representation would then be %(110) 0 1000 0000 0000% or 53,248 (8). The bandwidth cost (advertised value) of this link when it is idle, is then the 2's complement of the above binary representation, i.e., %(001) 1 0111 1111 1111% which corresponds to a decimal value of (2^16 - 1) - 53,248 = 12,287. Assuming now a current reservation level of 6;400 Mbits/s = 200 * 1024^2, there remains 1;600 Mbits/s of available bandwidth on the link. The encoding of this available bandwidth of 1'600 Mbits/s is 6,400 * 8^5, which corresponds to a granularity of 8^5 or approx. 30 kBytes/s, and has a binary representation of %(101) 1 1001 0000 0000% or decimal value of 47,360. The advertised cost of the link with this load level, is then %(010) 0 0110 1111 1111%, or (2^16-1) -47,360 = 18,175.
以一个示例结束，假设带宽为8 Gbits/s=1024^3字节/s的链路，其编码将由指数值6组成，因为1024^3=4096*8^6，其粒度将为8^6或约260 kBytes/s。然后，关联的二进制表示将是%（110）0 1000 0000 0000%或53248（8）。该链路空闲时的带宽成本（公布值）是上述二进制表示的2的补码，即%（001）10111 1111 1111%，对应于（2^16-1）-53248=12287的十进制值。假设目前的保留水平为6；400Mbits/s=200*1024^2，剩余1个；链路上的可用带宽为600 Mbits/s。该1600 Mbits/s可用带宽的编码为6400*8^5，对应于8^5或约30 kBytes/s的粒度，二进制表示为%（101）1 1001 0000 0000%或十进制值47360。具有此负载级别的链路的公布成本为%（010）0 0110 1111 1111%，或（2^16-1）-47360=18175。
Note that the cost function behaves as it should, i.e., the less bandwidth is available on a link, the higher the cost and the less attractive the link becomes. Furthermore, the targeted property of better granularity for links with less bandwidth available is also achieved. It should, however, be pointed out that the numbers given in the above examples match exactly the resolution of the proposed encoding, which is of course not always the case in practice. This leaves open the question of how to encode available bandwidth values when they do not exactly match the encoding. The standard practice is to round it to the closest number. Because we are ultimately interested in the cost value for which it may be better to be pessimistic than optimistic, we choose to round costs up and, therefore, bandwidth down.
请注意，成本函数的行为与其应有的一样，即链路上可用的带宽越少，成本越高，链路的吸引力就越低。此外，对于可用带宽较少的链路，还实现了更好粒度的目标特性。然而，应该指出的是，上述示例中给出的数字与建议编码的分辨率完全匹配，这在实践中当然并不总是如此。这就留下了一个悬而未决的问题，即当可用带宽值与编码不完全匹配时，如何对其进行编码。标准做法是将其四舍五入到最接近的数字。因为我们最终对成本价值感兴趣，对此，悲观可能比乐观好，所以我们选择将成本四舍五入，从而降低带宽。
Delay is encoded in microseconds using the same exponential method as described for bandwidth except that the base is defined to be 4 instead of 8. Therefore, the maximum delay that can be expressed is (2^13-1) *4^7 i.e., approx. 134 seconds.
延迟使用与带宽相同的指数方法以微秒为单位进行编码，但基数定义为4而不是8。因此，可以表示的最大延迟为（2^13-1）*4^7，即约134秒。
Given the extended TOS notation to account for QoS metrics, no changes in packet formats are necessary except for the (re)introduction of T-bit as the Q-bit in the options field. Routers not understanding the Q-bit should either not consider the QoS metrics distributed or consider those as `unknown' TOS.
考虑到QoS度量的扩展TOS表示法，除了在选项字段中（重新）引入T位作为Q位外，无需更改数据包格式。不理解Q-BIT的路由器不应考虑分配的QoS度量，也不考虑那些未知的TOS。
To support QoS, there are additions to two Link State Advertisements, the Router Links Advertisement and the Summary Links Advertisement. As stated above, a router identifies itself as supporting QoS by setting the Q-bit in the options field of the Link State Header. When a router that supports QoS receives either the Router Links or Summary Links Advertisement, it should parse the QoS metrics encoded in the received Advertisement.
为了支持QoS，添加了两个链路状态播发，路由器链路播发和摘要链路播发。如上所述，路由器通过在链路状态报头的选项字段中设置Q位来标识自己支持QoS。当支持QoS的路由器接收到路由器链接或摘要链接播发时，它应该解析在接收到的播发中编码的QoS度量。
This document proposes a very limited use of OSPF areas, that is, it is assumed that summary links advertisements exist for all networks in the area. This document does not discuss the problem of providing support for area address ranges and QoS metric aggregation. This is left for further studies.
本文件建议对OSPF区域进行非常有限的使用，即假设该区域内的所有网络都存在摘要链接广告。本文档不讨论为区域地址范围和QoS度量聚合提供支持的问题。这有待进一步研究。
Support for AS External Links, Virtual Links, and incremental updates for summary link advertisements are not addressed in this document and are left for further study. For Virtual Links that do exist, it is assumed for path selection that these links are non-QoS capable even if the router advertises QoS capability. Also, as stated earlier, this document does not address the issue of non-QoS routers within a QoS domain.
对AS外部链接、虚拟链接和摘要链接广告的增量更新的支持未在本文档中讨论，请留待进一步研究。对于确实存在的虚拟链路，在路径选择中假设这些链路不具备QoS能力，即使路由器宣传QoS能力。此外，如前所述，本文件不涉及QoS域内的非QoS路由器问题。
In this section we report on the experience gained from implementing the pre-computation based approach of Section 2.3.1 in the GateD [Con] environment. First, we briefly introduce the GateD environment, and then present some details on how the QoS extensions were implemented in this environment. Finally, we discuss issues that arose during the implementation effort and present some measurement based results on the overhead that the QoS extensions impose on a QoS capable router and a network of QoS routers. For further details on the implementation study, the reader is referred to [AGK99]. Additional performance evaluation based on simulations can be found in [AGKT98].
在本节中，我们报告了在门控[Con]环境中实施第2.3.1节中基于预计算的方法所获得的经验。首先，我们简要介绍门控环境，然后介绍如何在此环境中实现QoS扩展的一些细节。最后，我们讨论了在实现过程中出现的问题，并根据QoS扩展对具有QoS能力的路由器和QoS路由器网络施加的开销给出了一些基于度量的结果。有关实施研究的更多详细信息，请参考[AGK99]。基于模拟的其他性能评估可在[AGKT98]中找到。
GateD [Con] is a popular, public domain (9) program that provides a platform for implementing routing protocols on hosts running the Unix operating system. The distribution of the GateD software also includes implementations of many popular routing protocols, including the OSPF protocol. The GateD environment offers a variety of services useful for implementing a routing protocol. These services
门控[Con]是一个流行的公共域（9）程序，它为在运行Unix操作系统的主机上实现路由协议提供了一个平台。门控软件的发行版还包括许多流行路由协议的实现，包括OSPF协议。门控环境提供了多种可用于实现路由协议的服务。这些服务
include a) support for creation and management of timers, b) memory management, c) a simple scheduling mechanism, d) interfaces for manipulating the host's routing table and accessing the network, and e) route management (e.g., route prioritization and route exchange between protocols).
包括a）对计时器创建和管理的支持，b）内存管理，c）简单的调度机制，d）用于操作主机路由表和访问网络的接口，以及e）路由管理（例如，路由优先级和协议之间的路由交换）。
All GateD processing is done within a single Unix process, and routing protocols are implemented as one or several tasks. A GateD task is a collection of code associated with a Unix socket. The socket is used for the input and output requirements of the task. The main loop of GateD contains, among other operations, a select() call over all task sockets to determine if any read/write or error conditions occurred in any of them. GateD implements the OSPF link state database using a radix tree for fast access to individual link state records. In addition, link state records for neighboring network elements (such as adjacent routers) are linked together at the database level with pointers. GateD maintains a single routing table that contains routes discovered by all the active routing protocols. Multiple routes to the same destination are prioritized according to a set of rules and administrative preferences and only a single route is active per destination. These routes are periodically downloaded in the host's kernel forwarding table.
所有门控处理都在单个Unix进程中完成，路由协议作为一个或多个任务实现。门控任务是与Unix套接字关联的代码集合。套接字用于任务的输入和输出需求。在其他操作中，门控的主循环包含对所有任务套接字的select（）调用，以确定其中是否有读/写或错误情况。门控使用基数树实现OSPF链路状态数据库，以便快速访问单个链路状态记录。此外，相邻网络元素（如相邻路由器）的链路状态记录在数据库级别通过指针链接在一起。门控维护一个路由表，其中包含所有活动路由协议发现的路由。到同一目的地的多条路由根据一组规则和管理首选项进行优先级排序，每个目的地只有一条路由处于活动状态。这些路由定期下载到主机的内核转发表中。
One of our major design objectives was to gain substantial experience with a functionally complete QoS routing implementation while containing the overall implementation complexity. Thus, our architecture was modular and aimed at reusing the existing OSPF code with only minimal changes. QoS extensions were localized to specific modules and their interaction with existing OSPF code was kept to a minimum. Besides reducing the development and testing effort, this approach also facilitated experimentation with different alternatives for implementing the QoS specific features such as triggering policies for link state updates and QoS route table computation. Several of the design choices were also influenced by our assumptions regarding the core functionalities that an early prototype implementation of QoS routing must demonstrate. Some of the important assumptions/requirements are:
我们的主要设计目标之一是获得功能完整的QoS路由实现的丰富经验，同时控制总体实现的复杂性。因此，我们的体系结构是模块化的，旨在重用现有的OSPF代码，只需进行最小的更改。QoS扩展局限于特定的模块，它们与现有OSPF代码的交互保持在最低限度。除了减少开发和测试工作量外，该方法还促进了对不同备选方案的实验，以实现特定于QoS的特性，例如用于链路状态更新和QoS路由表计算的触发策略。我们对QoS路由的早期原型实现必须证明的核心功能的假设也影响了一些设计选择。一些重要的假设/要求如下：
- Support for only hop-by-hop routing. This affected the path structure in the QoS routing table as it only needs to store next hop information. As mentioned earlier, the structure can be easily extended to allow construction of explicit routes.
- 仅支持逐跳路由。这会影响QoS路由表中的路径结构，因为它只需要存储下一跳信息。如前所述，该结构可以很容易地扩展，以允许构建显式路由。
- Support for path pre-computation. This required the creation of a separate QoS routing table and its associated path structure, and was motivated by the need to minimize processing overhead.
- 支持路径预计算。这需要创建一个单独的QoS路由表及其关联的路径结构，其动机是最小化处理开销。
- Full integration of the QoS extensions into the GateD framework, including configuration support, error logging, etc. This was required to ensure a fully functional implementation that could be used by others.
- 将QoS扩展完全集成到门控框架中，包括配置支持、错误记录等。这是确保其他人可以使用的完整功能实现所必需的。
- Ability to allow experimentation with different approaches, e.g., use of different update and pre-computation triggering policies with support for selection and parameterization of these policies from the GateD configuration file.
- 能够使用不同的方法进行实验，例如，使用不同的更新和计算前触发策略，并支持从门控配置文件中选择和参数化这些策略。
- Decoupling from local traffic and resource management components, i.e., packet classifiers and schedulers and local call admission. This is supported by providing an API between QoS routing and the local traffic management module, which hides all internal details or mechanisms. Future implementations will be able to specify their own mechanisms for this module.
- 与本地流量和资源管理组件（即数据包分类器和调度器）以及本地呼叫允许分离。这是通过在QoS路由和本地流量管理模块之间提供API来支持的，该API隐藏了所有内部细节或机制。未来的实现将能够为此模块指定自己的机制。
- Interface to RSVP. The implementation assumes that RSVP [RZB+97] is the mechanism used to request routes with specific QoS requirements. Such requests are communicated through an interface based on [GKR97], and used the RSVP code developed at ISI, version 4.2a2 [RZB+97].
- 与RSVP的接口。该实现假设RSVP[RZB+97]是用于请求具有特定QoS需求的路由的机制。此类请求通过基于[GKR97]的接口进行通信，并使用ISI 4.2a2版本[RZB+97]开发的RSVP代码。
In addition, our implementation also relies on several of the simplifying assumptions made earlier in this document, namely:
此外，我们的实施还依赖于本文件前面提出的几个简化假设，即：
- The scope of QoS route computation is currently limited to a single area.
- 目前，QoS路由计算的范围仅限于单个区域。
- All routers within the area are assumed to run a QoS enabled version of OSPF, i.e., inter-operability with non-QoS aware versions of the OSPF protocol is not considered.
- 假设该区域内的所有路由器都运行支持QoS的OSPF版本，即不考虑与不支持QoS的OSPF协议版本的互操作性。
- All interfaces on a router are assumed to be QoS capable.
- 假定路由器上的所有接口都具有QoS能力。
The above design decisions and assumptions resulted in the architecture shown in Figure 2. It consists of three major components: the signaling component (RSVP in our case); the QoS routing component; and the traffic manager. In the rest of this section we concentrate on the structure and operation of the QoS routing component. As can be seen in Figure 2, the QoS routing extensions are further divided into the following modules:
上述设计决策和假设形成了图2所示的体系结构。它由三个主要组件组成：信令组件（在本例中为RSVP）；QoS路由组件；还有交通经理。在本节的其余部分中，我们将重点介绍QoS路由组件的结构和操作。如图2所示，QoS路由扩展进一步分为以下模块：
- Update trigger module determines when to advertise local link state updates. This module implements a variety of triggering policies: periodic, threshold based triggering, and class based triggering. This module also implements a hold-down timer that enforces minimum spacing between two consecutive update triggerings from the same node.
- 更新触发模块确定何时公布本地链路状态更新。此模块实现多种触发策略：定期、基于阈值的触发和基于类的触发。该模块还实现了一个按住计时器，该计时器强制执行来自同一节点的两个连续更新触发之间的最小间隔。
- Pre-computation trigger module determines when to perform QoS path pre-computation. So far, this module implements only periodic pre-computation triggering.
- 预计算触发模块确定何时执行QoS路径预计算。到目前为止，该模块仅实现定期预计算触发。
- Path pre-computation module computes the QoS routing table based on the QoS specific link state information as described in Section 2.3.1.
- 路径预计算模块根据第2.3.1节中描述的QoS特定链路状态信息计算QoS路由表。
- Path selection and management module selects a path for a request with particular QoS requirements, and manages it once selected, i.e., reacts to link or reservation failures. Path selection is performed as described in Section 2.3.1. Path management functionality is not currently supported.
- 路径选择和管理模块为具有特定QoS要求的请求选择路径，并在选择后对其进行管理，即对链路或预约故障作出反应。路径选择按照第2.3.1节所述进行。当前不支持路径管理功能。
- QoS routing table module implements the QoS specific routing table, which is maintained independently of the other GateD routing tables.
- QoS路由表模块实现QoS特定的路由表，该路由表独立于其他选通路由表进行维护。
- Tspec mapping module maps request requirements expressed in the form of RSVP Tspecs and Rspecs into the bandwidth requirements that QoS routing uses.
- Tspec映射模块将以RSVP Tspec和RSPEC形式表示的请求需求映射为QoS路由使用的带宽需求。
Mapping the above design to the framework of the GateD implementation of OSPF led to a number of issues and design decisions. These issues mainly fell under two categories: a) interoperation of the QoS extensions with pre-existing similar OSPF mechanisms, and b) structure, placement, and organization of the QoS routing table. Next, we briefly discuss these issues and justify the resulting design decisions.
将上述设计映射到OSPF的门控实现框架导致了许多问题和设计决策。这些问题主要分为两类：a）QoS扩展与预先存在的类似OSPF机制的互操作，以及b）QoS路由表的结构、放置和组织。接下来，我们将简要讨论这些问题，并证明最终的设计决策是正确的。
+--------------------------------------------------+
| +-----------------------------+ |
| | QoS Route Table Computation | |
| +-----------------------------+ |
| | | |
| V | |
| +-----------------+ | |
+-------------->| QoS Route Table | | |
| | +-----------------+ | |
| | | |
| | +----------------------+ +---------------+ |
| | | Core OSPF Functions | | Precomputation| |
| | | + | | Trigger | |
| | | (Enhanced) Topology | +---------------+ |
| | | Data Base | | |
| | +----------------------+ | |
| | | | | |
| | | +----------------------------+ |
| | | | Receive and update QoS-LSA | |
| | | +----------------------------+ |
| | | | |
| | | +----------------+ |
| | | | Local Interface| |
| | | | Status Monitor | |
| | | +----------------+ |
+----------------+ | | | |
| Path Selection | | +--------------+ +----------------+ |
| & Management | | | Build and | | Link State | |
+----------------+ | | Send QoS-LSA |----------| Update Trigger | |
| | +--------------+ +----------------+ |
+----------------+ | | |
| QoS Parameter | | | |
| Mapping | | OSPF with QoS Routing Extensions | |
|----------------+ +-------------------------------------------|------+
| |
+----------------+ +----------+
| QoS Route | | Local |
| Request Client |<---------------------------------------->| Resource |
| (e.g. RSVP) | | Manager |
+----------------+ +----------+
+--------------------------------------------------+
| +-----------------------------+ |
| | QoS Route Table Computation | |
| +-----------------------------+ |
| | | |
| V | |
| +-----------------+ | |
+-------------->| QoS Route Table | | |
| | +-----------------+ | |
| | | |
| | +----------------------+ +---------------+ |
| | | Core OSPF Functions | | Precomputation| |
| | | + | | Trigger | |
| | | (Enhanced) Topology | +---------------+ |
| | | Data Base | | |
| | +----------------------+ | |
| | | | | |
| | | +----------------------------+ |
| | | | Receive and update QoS-LSA | |
| | | +----------------------------+ |
| | | | |
| | | +----------------+ |
| | | | Local Interface| |
| | | | Status Monitor | |
| | | +----------------+ |
+----------------+ | | | |
| Path Selection | | +--------------+ +----------------+ |
| & Management | | | Build and | | Link State | |
+----------------+ | | Send QoS-LSA |----------| Update Trigger | |
| | +--------------+ +----------------+ |
+----------------+ | | |
| QoS Parameter | | | |
| Mapping | | OSPF with QoS Routing Extensions | |
|----------------+ +-------------------------------------------|------+
| |
+----------------+ +----------+
| QoS Route | | Local |
| Request Client |<---------------------------------------->| Resource |
| (e.g. RSVP) | | Manager |
+----------------+ +----------+
Figure 2: The software architecture
图2：软件架构
The ability to trigger link state updates in response to changes in bandwidth availability on interfaces is an essential component of the QoS extensions. Mechanisms for triggering these updates and controlling their rate have been mentioned in Section 2.2. In addition, OSPF implements its own mechanism for triggering link state updates as well as its own hold down timer, which may be incompatible with what is used for the QoS link state updates. We handle such potential conflicts as follows. First, since OSPF triggers updates on a periodic basis with low frequency, we expect these updates to be only a small part of the total volume of updates generated. As a result, we chose to maintain the periodic update triggering of OSPF. Resolving conflicts in the settings of the different hold down timer settings requires more care. In particular, it is important to ensure that the existing OSPF hold down timer does not interfere with QoS updates. One option is to disable the existing OSPF timer, but protection against transient overloads calls for some hold down timer, albeit with a small value. As a result, the existing OSPF hold down timer was kept, but reduced its value to 1 second. This value is low enough (actually is the lowest possible, since GateD timers have a maximum resolution of 1 second) so that it does not interfere with the generation of the QoS link state updates, which will actually often have hold down timers of their own with higher values. An additional complexity is that the triggering of QoS link state updates needs to be made aware of updates performed by OSPF itself. This is necessary, as regular OSPF updates also carry bandwidth information, and this needs to be considered by QoS updates to properly determine when to trigger a new link state update.
触发链路状态更新以响应接口带宽可用性变化的能力是QoS扩展的一个重要组成部分。触发这些更新并控制其速率的机制已在第2.2节中提到。此外，OSPF实现了自己的触发链路状态更新的机制以及自己的保持计时器，这可能与用于QoS链路状态更新的机制不兼容。我们按如下方式处理此类潜在冲突。首先，由于OSPF定期以较低的频率触发更新，我们预计这些更新只占生成的更新总量的一小部分。因此，我们选择保持OSPF的定期更新触发。解决不同按住计时器设置中的冲突需要更加小心。特别是，确保现有OSPF保持计时器不会干扰QoS更新非常重要。一个选项是禁用现有的OSPF定时器，但是防止瞬时过载需要一些按住定时器，尽管其值很小。因此，保留了现有的OSPF保持计时器，但将其值减少到1秒。该值足够低（实际上是可能的最低值，因为选通定时器的最大分辨率为1秒），因此它不会干扰QoS链路状态更新的生成，而QoS链路状态更新通常会使其自身的保持定时器具有更高的值。另一个复杂性是，QoS链路状态更新的触发需要知道OSPF本身执行的更新。这是必要的，因为定期的OSPF更新也携带带宽信息，QoS更新需要考虑这一点，以正确确定何时触发新的链路状态更新。
Another existing OSPF mechanism that has the potential to interfere with the extensions needed for QoS routing, is the support for delayed acknowledgments that allows aggregation of acknowledgments for multiple LSAs. Since link state updates are maintained in retransmission queues until acknowledged, excessive delay in the generation of the acknowledgement combined with the increased rates of QoS updates may result in overflows of the retransmission queues. To avoid these potential overflows, this mechanism was bypassed altogether and LSAs received from neighboring routers were immediately acknowledged. Another approach which was considered but not implemented, was to make QoS LSAs unreliable, i.e., eliminate their acknowledgments, so as to avoid any potential interference. Making QoS LSAs unreliable would be a reasonable design choice because of their higher frequency compared to the regular LSAs and the reduced impact that the loss of a QoS LSA has on the protocol operation. Note that the loss of a QoS LSA does not interfere with the base operation of OSPF, and only transiently reduces the quality of paths discovered by QoS routing.
另一种可能干扰QoS路由所需扩展的现有OSPF机制是对延迟确认的支持，它允许聚合多个LSA的确认。由于链路状态更新保持在重传队列中直到被确认，因此在生成确认时的过度延迟与QoS更新的增加速率相结合可能导致重传队列的溢出。为了避免这些潜在的溢出，该机制被完全绕过，并立即确认从相邻路由器接收到的LSA。另一种被考虑但未实施的方法是使QoS LSA不可靠，即消除它们的确认，以避免任何潜在的干扰。使QoS LSA不可靠将是一种合理的设计选择，因为与常规LSA相比，QoS LSA的频率更高，并且QoS LSA的丢失对协议操作的影响更小。请注意，QoS LSA的丢失不会干扰OSPF的基本操作，只会暂时降低QoS路由发现的路径的质量。
The structure and placement of the QoS routing table also raises some interesting implementation issues. Pre-computed paths are placed into a QoS routing table. This table is implemented as a set of path structures, one for each destination, which contain all the available paths to this destination. In order to be able to efficiently locate individual path structures, an access structure is needed. In order to minimize the develpement effort, the radix tree structure used for the regular GateD routing tables was reused. In addition, the QoS routing table was kept independent of the GateD routing tables to conform to the design goal of localizing changes and minimizing the impact on the existing OSPF code. An additional reason for maintaining the QoS routing separate and self-contained is that it is re-computed under conditions that are different from those used for the regular routing tables.
QoS路由表的结构和位置也提出了一些有趣的实现问题。预先计算的路径被放入QoS路由表中。此表实现为一组路径结构，每个目标对应一个，其中包含指向此目标的所有可用路径。为了能够有效地定位各个路径结构，需要访问结构。为了最大限度地减少开发工作量，重用了用于常规选通路由表的基树结构。此外，QoS路由表独立于选通路由表，以符合本地化更改和最小化对现有OSPF代码影响的设计目标。保持QoS路由独立和自包含的另一个原因是，它是在不同于常规路由表的条件下重新计算的。
Furthermore, since the QoS routing table is re-built frequently, it must be organized so that its computation is efficient. A common operation during the computation of the QoS routing table is mapping a link state database entry to the corresponding path structure. In order to make this operation efficient, the link state database entries were extended to contain a pointer to the corresponding path structure. In addition, when a new QoS routing table is to be computed, the previous one must be de-allocated. This is accomplished by traversing the radix tree in-order, and de-allocating each node in the tree. This full de-allocation of the QoS routing table is potentially wasteful, especially since memory allocation and de-allocation is an expensive operation. Furthermore, because path pre-computations are typically not triggered by changes in topology, the set of destinations will usually remain the same and correspond to an unchanged radix tree. A natural optimization would then be to de-allocate only the path structures and maintain the radix tree. A further enhancement would be to maintain the path structures as well, and attempt to incrementally update them only when required. However, despite the potential gains, these optimizations have not been included in the initial implementation. The main reason is that they involve subtle and numerous checks to ensure the integrity of the overall data structure at all times, e.g., correctly remove failed destinations from the radix tree and update the tree accordingly.
此外，由于QoS路由表经常被重新构建，因此必须对其进行组织以使其计算高效。QoS路由表计算期间的一个常见操作是将链路状态数据库条目映射到相应的路径结构。为了提高此操作的效率，链接状态数据库条目被扩展为包含指向相应路径结构的指针。此外，当要计算新的QoS路由表时，必须取消分配前一个QoS路由表。这是通过按顺序遍历基数树并取消分配树中的每个节点来实现的。这种对QoS路由表的完全取消分配可能会造成浪费，特别是因为内存分配和取消分配是一项昂贵的操作。此外，由于路径预计算通常不会由拓扑的更改触发，因此目的地集通常保持不变，并对应于不变的基树。然后，一个自然的优化就是只分配路径结构，并维护基数树。进一步的增强是维护路径结构，并且仅在需要时尝试增量更新它们。然而，尽管有潜在的收益，这些优化还没有包括在最初的实现中。主要原因是，它们涉及微妙且大量的检查，以确保整个数据结构始终保持完整性，例如，从基树中正确删除失败的目标，并相应地更新树。
After completing the implementation outlined in the previous sections, it was possible to perform an experimental study of the cost and nature of the overhead of the QoS routing extensions proposed in this document. In particular, using a simple setup consisting of two interconnected routers, it is possible to measure the cost of individual QoS routing related operations. These operations are: a) computation of the QoS routing table, b) selection of a path from the QoS routing table, c) generation of a link state update, and d) reception of a link state update. Note that the last two operations are not really specific to QoS routing since regular OSPF also performs them. Nevertheless, we expect the more sensitive update triggering mechanisms required for effective QoS routing to result in increased number of updates, making the cost of processing updates an important component of the QoS routing overhead. An additional cost dimension is the memory required for storing the QoS routing table. Scaling of the above costs with increasing sizes of the topology database was investigated by artificially populating the topology databases of the routers under measurement.
完成前几节中概述的实现后，可以对本文中提出的QoS路由扩展的开销的成本和性质进行实验研究。特别是，使用由两个互连路由器组成的简单设置，可以测量单个QoS路由相关操作的成本。这些操作是：a）计算QoS路由表，b）从QoS路由表选择路径，c）生成链路状态更新，以及d）接收链路状态更新。请注意，最后两个操作实际上并不特定于QoS路由，因为常规OSPF也执行它们。然而，我们期望有效的QoS路由所需的更敏感的更新触发机制会导致更新数量的增加，从而使处理更新的成本成为QoS路由开销的一个重要组成部分。另一个成本维度是存储QoS路由表所需的内存。通过人工填充被测路由器的拓扑数据库，研究了上述成本随拓扑数据库大小的增加而增加的比例。
Table 1 shows how the measured costs depend on the size of the topology. The topology used in the measurements was built by replicating a basic building block consisting of four routers connected with transit networks in a rectangular arrangement. The details of the topology and the measurements can be found in [AGK99]. The system running the GateD software was an IBM IntelliStation Z Pro with a Pentium Pro processor at 200 MHz, 64 MBytes or real memory, running FreeBSD 2.2.5-RELEASE and GateD 4. From the results of Table 1, one can observe that the cost of path pre-computation is not much higher than that of the regular SPF computation. However, path pre-computation may need to be performed much more often than the SPF computation, and this can potentially lead to higher processing costs. This issue was investigated in a set of subsequent experiments, that are described later in this section. The other cost components reported in Table 1 include memory, and it can be seen that the QoS routing table requires roughly 80% more memory than the regular routing table. Finally, the cost of selecting a path is found to be very small compared to the path pre-computation times. As expected, all the measured quantities increase as the size of the topology increases. In particular, the storage requirements and the processing costs for both SPF computation and QoS path pre-computation scale almost linearly with the network size.
表1显示了测量的成本如何取决于拓扑的大小。测量中使用的拓扑结构是通过复制一个基本构建块来构建的，该构建块由四个路由器组成，这些路由器以矩形排列与公交网络相连。有关拓扑和测量的详细信息，请参见[AGK99]。运行门控软件的系统是一个IBM IntelliStation Z Pro，具有200 MHz、64 MB或真实内存的奔腾Pro处理器，运行FreeBSD 2.2.5版本和门控4。从表1的结果可以看出，路径预计算的成本并不比常规SPF计算的成本高得多。然而，可能需要比SPF计算更频繁地执行路径预计算，这可能导致更高的处理成本。这一问题在随后的一系列实验中进行了研究，本节稍后将对此进行描述。表1中报告的其他成本组件包括内存，可以看出，QoS路由表比常规路由表需要大约80%的内存。最后，与路径预计算时间相比，选择路径的成本非常小。正如预期的那样，所有测量的数量都会随着拓扑大小的增加而增加。特别是，SPF计算和QoS路径预计算的存储需求和处理成本几乎与网络大小成线性关系。
________________________________________________________________________
|Link_state_database_size_______|_25_|__49_|__81__|__121_|__169_|__225_|
|Regular_SPF_time_(microsec)____|215_|_440_|_747__|_1158_|_1621_|_2187_|
|Pre-computation_time_(microsec)|736_|_1622|_2883_|_4602_|_6617_|_9265_|
|SPF_routing_table_size_(bytes)_|2608|_4984|_8152_|_12112|_16864|_22408|
|QoS_routing_table_size_(bytes)_|3924|_7952|_13148|_19736|_27676|_36796|
|Path_Selection_time_(microsec)_|_.7_|_1.6_|__2.8_|__4.6_|__6.6_|__9.2_|
________________________________________________________________________
|Link_state_database_size_______|_25_|__49_|__81__|__121_|__169_|__225_|
|Regular_SPF_time_(microsec)____|215_|_440_|_747__|_1158_|_1621_|_2187_|
|Pre-computation_time_(microsec)|736_|_1622|_2883_|_4602_|_6617_|_9265_|
|SPF_routing_table_size_(bytes)_|2608|_4984|_8152_|_12112|_16864|_22408|
|QoS_routing_table_size_(bytes)_|3924|_7952|_13148|_19736|_27676|_36796|
|Path_Selection_time_(microsec)_|_.7_|_1.6_|__2.8_|__4.6_|__6.6_|__9.2_|
Table 1: Stand alone QoS routing costs
表1：独立QoS路由成本
In addition to the stand alone costs reported in Table 1, it is important to assess the actual operational load induced by QoS routing in the context of a large network. Since it is not practical to reproduce a large scale network in a lab setting, the approach used was to combine simulation and measurements. Specifically, a simulation was used to obtain a time stamped trace of QoS routing related events that occur in a given router in a large scale network. The trace was then used to artificially induce similar load conditions on a real router and its adjacent links. In particular, it was used to measure the processing load at the router and bandwidth usage that could be attributed to QoS updates. A more complete discussion of the measurement method and related considerations can be found in [AGK99].
除了表1中报告的独立成本外，重要的是评估大型网络环境中QoS路由引起的实际操作负载。由于在实验室环境中重现大规模网络是不现实的，因此采用的方法是将模拟和测量结合起来。具体来说，模拟用于获得大规模网络中给定路由器中发生的QoS路由相关事件的时间戳跟踪。然后，该跟踪被用于在真实路由器及其相邻链路上人工诱导类似的负载条件。特别是，它被用来测量路由器上的处理负载以及可能归因于QoS更新的带宽使用情况。有关测量方法和相关注意事项的更完整讨论，请参见[AGK99]。
The use of a simulation further allows the use of different configurations, where network topology is varied together with other QoS parameters such as a) period of pre-computation, and b) threshold for triggering link state updates. The results reported here were derived using two types of topologies. One based on a regular but artificial 8x8 mesh network, and another (isp) which has been used in several previous studies [AGKT98, AT98] and that approximates the network of a nation-wide ISP. As far as pre-computation periods are concerned, three values of 1, 5 and 50 seconds were chosen, and for the triggering of link state update thresholds of 10% and 80% were used. These values were selected as they cover a wide range in terms of precision of pre-computed paths and accuracy of the link state information available at the routers. Also note that 1 second is the smallest pre-computation period allowed by GateD.
使用模拟还允许使用不同的配置，其中网络拓扑与其他QoS参数（例如a）预计算周期和b）触发链路状态更新的阈值）一起变化。这里报告的结果是使用两种拓扑得出的。一个基于常规但人工的8x8网状网络，另一个（isp）已在之前的几项研究[AGKT98，AT98]中使用，近似于全国isp的网络。就预计算周期而言，选择了3个值1、5和50秒，并使用10%和80%的链路状态更新阈值触发链路状态更新。选择这些值是因为它们涵盖了预计算路径的精度和路由器可用链路状态信息的精度方面的广泛范围。还要注意，1秒是门控允许的最小预计算时间。
Table 2 provides results on the processing load at the router driven by the simulation trace, for the two topologies and different combinations of QoS parameters, i.e., pre-computation period and threshold for triggering link state updates. Table 3 gives the bandwidth consumption of QoS updates on the links adjacent to the router.
表2提供了两种拓扑和QoS参数的不同组合（即预计算周期和触发链路状态更新的阈值）下，由模拟跟踪驱动的路由器处理负载的结果。表3给出了路由器附近链路上QoS更新的带宽消耗。
________________________________________________________________
|_____________________|_________Pre-computation_Period_________|
|Link_state_threshold_|___1_sec____|____5_sec____|____50_sec___|
|_________10%_________|.45%_(1.6%)_|__.29%_(2%)__|__.17%_(3%)__|
|_________80%_________|.16%_(2.4%)_|__.04%_(3%)__|_.02%_(3.8%)_|
________________________________________________________________
|_____________________|_________Pre-computation_Period_________|
|Link_state_threshold_|___1_sec____|____5_sec____|____50_sec___|
|_________10%_________|.45%_(1.6%)_|__.29%_(2%)__|__.17%_(3%)__|
|_________80%_________|.16%_(2.4%)_|__.04%_(3%)__|_.02%_(3.8%)_|
isp
isp
________________________________________________________________
|_________10%_________|3.37%_(2.1%)|_2.23%_(3.3%)|_1.78%_(7.7%)|
|_________80%_________|1.54%_(5.4%)|_.42%_(6.6%)_|_.14%_(10.4%)|
________________________________________________________________
|_________10%_________|3.37%_(2.1%)|_2.23%_(3.3%)|_1.78%_(7.7%)|
|_________80%_________|1.54%_(5.4%)|_.42%_(6.6%)_|_.14%_(10.4%)|
8x8 mesh
8x8网格
Table 2: Router processing load and (bandwidth blocking).
表2：路由器处理负载和带宽阻塞。
In Table 2, processing load is expressed as the percentage of the total CPU resources that are consumed by GateD processing. The same table also shows the routing performance that is achieved for each combination of QoS parameters, so that comparison of the different processing cost/routing performance trade-offs can be made. Routing performance is measured using the bandwidth blocking ratio, defined as the sum of requested bandwidth of the requests that were rejected over the total offered bandwidth. As can be seen from Table 2, processing load is low even when the QoS routing table is recomputed every second, and LSAs are generated every time the available bandwidth on a link changes by more than 10% of the last advertised value. This seems to indicate that given today's processor technology, QoS routing should not be viewed as a costly enhancement, at least not in terms of its processing requirements. Another general observation is that while network size has obviously an impact, it does not seem to drastically affect the relative influence of the different parameters. In particular, despite the differences that exist between the isp and mesh topologies, changing the pre-computation period or the update threshold translates into essentially similar relative changes.
在表2中，处理负载表示为门控处理消耗的CPU总资源的百分比。该表还显示了每种QoS参数组合所获得的路由性能，因此可以比较不同的处理成本/路由性能权衡。路由性能使用带宽阻塞率来衡量，带宽阻塞率定义为在总提供带宽上被拒绝的请求的请求带宽之和。从表2中可以看出，即使每秒重新计算QoS路由表，处理负载也很低，并且每次链路上的可用带宽变化超过最后公布值的10%时，都会生成LSA。这似乎表明，考虑到当今的处理器技术，QoS路由不应被视为代价高昂的增强，至少在处理需求方面是如此。另一个普遍的观察结果是，虽然网络大小有明显的影响，但它似乎不会显著影响不同参数的相对影响。特别是，尽管isp和mesh拓扑之间存在差异，但更改预计算周期或更新阈值会转化为基本相似的相对变化。
Similar conclusions can be drawn for the update traffic shown in Table 3. In all cases, this traffic is only a small fraction of the link's capacity. Clearly, both the router load and the link bandwidth consumption depend on the router and link that was the target of the measurements and will vary for different choices. The results shown here are meant to be indicative, and a more complete discussion can be found in [AGK99].
对于表3所示的更新流量，也可以得出类似的结论。在所有情况下，这些流量只是链路容量的一小部分。显然，路由器负载和链路带宽消耗都取决于作为测量目标的路由器和链路，并且会因不同的选择而有所不同。此处显示的结果仅供参考，更完整的讨论见[AGK99]。
_______________________________________
|_Link_state_threshold_|_______________|
|_________10%__________|3112_bytes/sec_|
|_________80%__________|177_bytes/sec__|
_______________________________________
|_Link_state_threshold_|_______________|
|_________10%__________|3112_bytes/sec_|
|_________80%__________|177_bytes/sec__|
isp
________________________________________
|_________10%__________|15438_bytes/sec_|
|_________80%__________|1053_bytes/sec__|
isp
________________________________________
|_________10%__________|15438_bytes/sec_|
|_________80%__________|1053_bytes/sec__|
8x8 mesh
8x8网格
Table 3: Link state update traffic
表3：链路状态更新流量
Summarizing, by carrying out the implementation of the proposed QoS routing extensions to OSPF we demonstrated that such extensions are fairly straightforward to implement. Furthermore, by measuring the performance of the real system we were able to demonstrate that the overheads associated with QoS routing are not excessive, and are definitely within the capabilities of modern processor and workstation technology.
综上所述，通过对OSPF的QoS路由扩展的实现，我们证明了这种扩展的实现相当简单。此外，通过测量实际系统的性能，我们能够证明与QoS路由相关的开销并不过度，并且肯定在现代处理器和工作站技术的能力范围内。
The QoS extensions proposed in this document do not raise any security considerations that are in addition to the ones associated with regular OSPF. The security considerations of OSPF are presented in [Moy98]. However, it should be noted that this document assumes the availability of some entity responsible for assessing the legitimacy of QoS requests. For example, when the protocol used for initiating QoS requests is the RSVP protocol, this capability can be provided through the use of RSVP Policy Decision Points and Policy Enforcement Points as described in [YPG97]. Similarly, a policy server enforcing the acceptability of QoS requests by implementing decisions based on the rules and languages of [RMK+98], would also be capable of providing the desired functionality.
除了与常规OSPF相关的安全注意事项外，本文件中提出的QoS扩展并未提出任何安全注意事项。OSPF的安全注意事项见[Moy98]。但是，应该注意的是，本文档假设有一些实体负责评估QoS请求的合法性。例如，当用于发起QoS请求的协议是RSVP协议时，可以通过使用RSVP策略决策点和策略实施点来提供此功能，如[YPG97]所述。类似地，通过实施基于[RMK+98]的规则和语言的决策来强制QoS请求的可接受性的策略服务器也能够提供所需的功能。
APPENDICES
附录
A. Pseudocode for the BF Based Pre-Computation Algorithm
A.基于BF的预计算算法的伪代码
Note: The pseudocode below assumes a hop-by-hop forwarding approach in updating the neighbor field. The modifications needed to support explicit route construction are straightforward. The pseudocode also does not handle equal cost multi-paths for simplicity, but the modification needed to add this support are straightforward.
注意：下面的伪代码假设在更新邻居字段时采用逐跳转发方法。支持显式路由构造所需的修改非常简单。为了简单起见，伪代码也不处理等成本多路径，但是添加此支持所需的修改非常简单。
Input: V = set of vertices, labeled by integers 1 to N. L = set of edges, labeled by ordered pairs (n,m) of vertex labels. s = source vertex (at which the algorithm is executed). For all edges (n,m) in L: * b(n,m) = available bandwidth (according to last received update) on interface associated with the edge between vertices n and m. * If(n,m) outgoing interface corresponding to edge (n,m) when n is a router. H = maximum hop-count (at most the graph diameter).
输入：V=顶点集，由整数1到N标记。L=边集，由顶点标签的有序对（N，m）标记。s=源顶点（在该顶点执行算法）。对于L:*b（n，m）中的所有边（n，m）=与顶点n和m*之间的边关联的接口上的可用带宽（根据上次接收的更新）*当n是路由器时，对应于边缘（n，m）的If（n，m）输出接口。H=最大跃点计数（最多为图形直径）。
Type: tab_entry: record bw = integer, neighbor = integer 1..N.
类型：tab_条目：记录bw=integer，邻居=integer 1..N。
Variables: TT[1..N, 1..H]: topology table, whose (n,h) entry is a tab_entry record, such that: TT[n,h].bw is the maximum available bandwidth (as known thus far) on a path of at most h hops between vertices s and n, TT[n,h].neighbor is the first hop on that path (a neighbor of s). It is either a router or the destination n.
变量：TT[1..N，1..H]：拓扑表，其（N，H）项是选项卡项记录，例如：TT[N，H].bw是顶点s和N之间最多H个跃点的路径上的最大可用带宽（目前已知），TT[N，H]。邻居是该路径上的第一个跃点（s的邻居）。它要么是路由器，要么是目的地n。
S_prev: list of vertices that changed a bw value in the TT table in the previous iteration. S_new: list of vertices that changed a bw value (in the TT table etc.) in the current iteration.
S_prev：在上一次迭代中更改TT表中bw值的顶点列表。S_new：在当前迭代中更改bw值（在TT表等中）的顶点列表。
The Algorithm:
算法：
begin;
开始
for n:=1 to N do /* initialization */
begin;
TT[n,0].bw := 0;
for n:=1 to N do /* initialization */
begin;
TT[n,0].bw := 0;
TT[n,0].neighbor := null
TT[n,1].bw := 0;
TT[n,1].neighbor := null
end;
TT[s,0].bw := infinity;
TT[n,0].neighbor := null
TT[n,1].bw := 0;
TT[n,1].neighbor := null
end;
TT[s,0].bw := infinity;
reset S_prev;
for all neighbors n of s do
begin;
TT[n,1].bw := max( TT[n,1].bw, b[s,n]);
if (TT[n,1].bw = b[s,n]) then TT[n,1].neighbor := If(s,n);
/* need to make sure we are picking the maximum */
/* bandwidth path for routers that can be reached */
/* through both networks and point-to-point links */
if (n is a router) then
S_prev := S_prev union {n}
/* only a router is added to S_prev, */
/* if it is not already included in S_prev */
else /* n is a network: */
/* proceed with network--router edges, without */
/* counting another hop */
for all (n,k) in L, k <> s, do
/* i.e., for all other neighboring routers of n */
begin;
TT[k,1].bw := max( min( TT[n,1].bw, b[n,k]), TT[k,1].bw );
/* In case k could be reached through another path */
/* (a point-to-point link or another network) with */
/* more bandwidth, we do not want to update TT[k,1].bw */
if (min( TT[n,1].bw, b[n,k]) = TT[k,1].bw )
/* If we have updated TT[k,1].bw by going through */
/* network n */
then TT[k,1].neighbor := If(s,n);
/* neighbor is interface to network n */
if ( {k} not in S_prev) then S_prev := S_prev union {k}
/* only routers are added to S_prev, but we again need */
/* to check they are not already included in S_prev */
end
end;
reset S_prev;
for all neighbors n of s do
begin;
TT[n,1].bw := max( TT[n,1].bw, b[s,n]);
if (TT[n,1].bw = b[s,n]) then TT[n,1].neighbor := If(s,n);
/* need to make sure we are picking the maximum */
/* bandwidth path for routers that can be reached */
/* through both networks and point-to-point links */
if (n is a router) then
S_prev := S_prev union {n}
/* only a router is added to S_prev, */
/* if it is not already included in S_prev */
else /* n is a network: */
/* proceed with network--router edges, without */
/* counting another hop */
for all (n,k) in L, k <> s, do
/* i.e., for all other neighboring routers of n */
begin;
TT[k,1].bw := max( min( TT[n,1].bw, b[n,k]), TT[k,1].bw );
/* In case k could be reached through another path */
/* (a point-to-point link or another network) with */
/* more bandwidth, we do not want to update TT[k,1].bw */
if (min( TT[n,1].bw, b[n,k]) = TT[k,1].bw )
/* If we have updated TT[k,1].bw by going through */
/* network n */
then TT[k,1].neighbor := If(s,n);
/* neighbor is interface to network n */
if ( {k} not in S_prev) then S_prev := S_prev union {k}
/* only routers are added to S_prev, but we again need */
/* to check they are not already included in S_prev */
end
end;
for h:=2 to H do /* consider all possible number of hops */
begin;
reset S_new;
for all vertices m in V do
begin;
TT[m,h].bw := TT[m,h-1].bw;
TT[m,h].neighbor := TT[m,h-1].neighbor
end;
for h:=2 to H do /* consider all possible number of hops */
begin;
reset S_new;
for all vertices m in V do
begin;
TT[m,h].bw := TT[m,h-1].bw;
TT[m,h].neighbor := TT[m,h-1].neighbor
end;
for all vertices n in S_prev do
/* as shall become evident, S_prev contains only routers */
begin;
for all edges (n,m) in L do
if min( TT[n,h-1].bw, b[n,m]) > TT[m,h].bw then
begin;
TT[m,h].bw := min( TT[n,h-1].bw, b[n,m]);
TT[m,h].neighbor := TT[n,h-1].neighbor;
if m is a router then S_new := S_new union {m}
/* only routers are added to S_new */
else /* m is a network: */
/* proceed with network--router edges, without counting */
/* them as another hop */
for all (m,k) in L, k <> n,
/* i.e., for all other neighboring routers of m */
if min( TT[m,h].bw, b[m,k]) > TT[k,h].bw then
begin;
/* Note: still counting it as the h-th hop, as (m,k) is */
/* a network--router edge */
TT[k,h].bw := min( TT[m,h].bw, b[m,k]);
TT[k,h].neighbor := TT[m,h].neighbor;
S_new := S_new union {k}
/* only routers are added to S_new */
end
end
end;
S_prev := S_new;
/* the two lists can be handled by a toggle bit */
if S_prev=null then h=H+1 /* if no changes then exit */
end;
for all vertices n in S_prev do
/* as shall become evident, S_prev contains only routers */
begin;
for all edges (n,m) in L do
if min( TT[n,h-1].bw, b[n,m]) > TT[m,h].bw then
begin;
TT[m,h].bw := min( TT[n,h-1].bw, b[n,m]);
TT[m,h].neighbor := TT[n,h-1].neighbor;
if m is a router then S_new := S_new union {m}
/* only routers are added to S_new */
else /* m is a network: */
/* proceed with network--router edges, without counting */
/* them as another hop */
for all (m,k) in L, k <> n,
/* i.e., for all other neighboring routers of m */
if min( TT[m,h].bw, b[m,k]) > TT[k,h].bw then
begin;
/* Note: still counting it as the h-th hop, as (m,k) is */
/* a network--router edge */
TT[k,h].bw := min( TT[m,h].bw, b[m,k]);
TT[k,h].neighbor := TT[m,h].neighbor;
S_new := S_new union {k}
/* only routers are added to S_new */
end
end
end;
S_prev := S_new;
/* the two lists can be handled by a toggle bit */
if S_prev=null then h=H+1 /* if no changes then exit */
end;
end.
终止
B. On-Demand Dijkstra Algorithm for QoS Path Computation
B.用于QoS路径计算的按需Dijkstra算法
In the main text, we described an algorithm that allows pre-computation of QoS routes. However, it may be feasible in some instances, e.g., limited number of requests for QoS routes, to instead perform such computations on-demand, i.e., upon receipt of a request for a QoS route. The benefit of such an approach is that depending on how often recomputation of pre-computed routes is triggered, on-demand route computation can yield better routes by using the most recent link metrics available. Another benefit of on-demand path computation is the associated storage saving, i.e., there is no need for a QoS routing table. This is essentially the standard trade-off between memory and processing cycles.
在正文中，我们描述了一种允许预先计算QoS路由的算法。然而，在某些情况下，例如，有限数量的QoS路由请求，在接收到QoS路由请求时，按需执行这种计算是可行的。这种方法的好处在于，根据预先计算的路由的重新计算被触发的频率，按需路由计算可以通过使用可用的最新链路度量来产生更好的路由。按需路径计算的另一个好处是相关的存储节省，即不需要QoS路由表。这本质上是内存和处理周期之间的标准权衡。
In this section, we briefly describe how a standard Dijkstra algorithm can, for a given destination and bandwidth requirement, generate a minimum hop path that can accommodate the required bandwidth and also has maximum bandwidth. Because the Dijkstra algorithm is already used in the current OSPF route computation, only differences from the standard algorithm are described. Also, while for simplicity we do not consider here zero-hop edges, the modification required for supporting them is straightforward.
在本节中，我们将简要介绍标准Dijkstra算法如何针对给定的目的地和带宽需求生成能够容纳所需带宽且具有最大带宽的最小跳数路径。由于Dijkstra算法已用于当前OSPF路由计算，因此仅描述与标准算法的差异。此外，为简单起见，我们不考虑这里零跳边，支持它们所需的修改是直接的。
The algorithm essentially performs a minimum hop path computation, on a graph from which all edges, whose available bandwidth is less than that requested by the flow triggering the computation, have been removed. This can be performed either through a pre-processing step, or while running the algorithm by checking the available bandwidth value for any edge that is being considered (see the pseudocode that follows). Another modification to a standard Dijkstra based minimum hop count path computation, is that the list of equal cost next (previous) hops which is maintained as the algorithm proceeds, needs to be sorted according to available bandwidth. This is to allow selection of the minimum hop path with maximum available bandwidth. Alternatively, the algorithm could also be modified to, at each step, only keep among equal hop count paths the one with maximum available bandwidth. This would essentially amount to considering a cost that is function of both hop count and available bandwidth.
该算法本质上是在一个图上执行最小跳数路径计算，从该图中删除了所有可用带宽小于触发计算的流所请求的带宽的边。这可以通过预处理步骤来执行，也可以在运行算法时通过检查正在考虑的任何边缘的可用带宽值来执行（请参见下面的伪代码）。对基于Dijkstra的标准最小跳数路径计算的另一个修改是，需要根据可用带宽对算法进行维护的等成本下一（前）跳列表进行排序。这是为了允许选择具有最大可用带宽的最小跃点路径。或者，该算法也可以修改为，在每一步中，仅在等跳数路径中保持具有最大可用带宽的路径。这实质上相当于考虑一个成本，该成本是跳数和可用带宽的函数。
Note: The pseudocode below assumes a hop-by-hop forwarding approach in updating the neighbor field. Addition of routes to stub networks is done in a second phase as usual. The modifications needed to support explicit route construction are straightforward. The pseudocode also does not handle equal cost multi-paths for simplicity, but the modifications needed to add this support are also easily done.
注意：下面的伪代码假设在更新邻居字段时采用逐跳转发方法。向存根网络添加路由通常在第二阶段完成。支持显式路由构造所需的修改非常简单。为了简单起见，伪代码也不能处理相同成本的多路径，但是添加此支持所需的修改也很容易完成。
Input: V = set of vertices, labeled by integers 1 to N. L = set of edges, labeled by ordered pairs (n,m) of vertex labels. s = source vertex (at which the algorithm is executed). For all edges (n,m) in L: * b(n,m) = available bandwidth (according to last received update) on interface associated with the edge between vertices n and m. * If(n,m) = outgoing interface corresponding to edge (n,m) when n is a router. d = destination vertex. B = requested bandwidth for the flow served.
输入：V=顶点集，由整数1到N标记。L=边集，由顶点标签的有序对（N，m）标记。s=源顶点（在该顶点执行算法）。对于L:*b（n，m）中的所有边（n，m）=与顶点n和m*之间的边关联的接口上的可用带宽（根据上次接收的更新）*If（n，m）=当n是路由器时，对应于边缘（n，m）的输出接口。d=目标顶点。B=所服务流的请求带宽。
Type: tab_entry: record hops = integer, neighbor = integer 1..N, ontree = boolean.
类型：tab_条目：记录跃点=整数，邻居=整数1..N，ontree=布尔值。
Variables:
TT[1..N]: topology table, whose (n) entry is a tab_entry
record, such that:
TT[n].bw is the available bandwidth (as known
thus far) on a shortest-path between
vertices s and n,
TT[n].neighbor is the first hop on that path (a
neighbor of s). It is either a router or the
destination n.
S: list of candidate vertices;
v: vertex under consideration;
Variables:
TT[1..N]: topology table, whose (n) entry is a tab_entry
record, such that:
TT[n].bw is the available bandwidth (as known
thus far) on a shortest-path between
vertices s and n,
TT[n].neighbor is the first hop on that path (a
neighbor of s). It is either a router or the
destination n.
S: list of candidate vertices;
v: vertex under consideration;
The Algorithm:
算法：
begin;
for n:=1 to N do /* initialization */
begin;
TT[n].hops := infinity;
TT[n].neighbor := null;
TT[n].ontree := FALSE;
end;
TT[s].hops := 0;
begin;
for n:=1 to N do /* initialization */
begin;
TT[n].hops := infinity;
TT[n].neighbor := null;
TT[n].ontree := FALSE;
end;
TT[s].hops := 0;
reset S;
v:= s;
while v <> d do
begin;
TT[v].ontree := TRUE;
for all edges (v,m) in L and b(v,m) >= B do
begin;
reset S;
v:= s;
while v <> d do
begin;
TT[v].ontree := TRUE;
for all edges (v,m) in L and b(v,m) >= B do
begin;
if m is a router
begin;
if not TT[m].ontree then
begin;
/* bandwidth must be fulfilled since all links >= B */
if TT[m].hops > TT[v].hops + 1 then
begin
S := S union { m };
TT[m].hops := TT[v].hops + 1;
TT[m].neighbor := v;
end;
end;
end;
else /* must be a network, iterate over all attached routers */
begin; /* each network -- router edge treated as zero hop edge */
for all (m,k) in L, k <> v,
/* i.e., for all other neighboring routers of m */
if not TT[k].ontree and b(m,k) >= B then
begin;
if TT[k].hops > TT[v].hops then
begin;
S := S union { k };
TT[k].hops := TT[v].hops;
TT[k].neighbor := v;
end;
end;
end;
end; /* of all edges from the vertex under consideration */
if m is a router
begin;
if not TT[m].ontree then
begin;
/* bandwidth must be fulfilled since all links >= B */
if TT[m].hops > TT[v].hops + 1 then
begin
S := S union { m };
TT[m].hops := TT[v].hops + 1;
TT[m].neighbor := v;
end;
end;
end;
else /* must be a network, iterate over all attached routers */
begin; /* each network -- router edge treated as zero hop edge */
for all (m,k) in L, k <> v,
/* i.e., for all other neighboring routers of m */
if not TT[k].ontree and b(m,k) >= B then
begin;
if TT[k].hops > TT[v].hops then
begin;
S := S union { k };
TT[k].hops := TT[v].hops;
TT[k].neighbor := v;
end;
end;
end;
end; /* of all edges from the vertex under consideration */
if S is empty then
begin;
v=d; /* which will end the algorithm */
end;
else
begin;
v := first element of S;
S := S - {v}; /* remove and store the candidate to consider */
end;
end; /* from processing of the candidate list */
end.
if S is empty then
begin;
v=d; /* which will end the algorithm */
end;
else
begin;
v := first element of S;
S := S - {v}; /* remove and store the candidate to consider */
end;
end; /* from processing of the candidate list */
end.
C. Precomputation Using Dijkstra Algorithm
C.使用Dijkstra算法的预计算
This appendix outlines a Dijkstra-based algorithm that allows pre-computation of QoS routes for all destinations and bandwidth values. The benefit of using a Dijkstra-based algorithm is a greater synergy with existing OSPF implementations. The solution to compute all "best" paths is to consecutively compute shortest path spanning trees starting from a complete graph and removing links with less bandwidth than the threshold used in the previous computation. This yields paths with possibly better bandwidth but of course more hops. Despite the large number of Dijkstra computations involved, several optimizations such as incremental spanning tree computation can be used and allow for efficient implementations in terms of complexity as well as storage since the structure of computed paths leans itself towards path compression [ST83]. Details including measurements and applicability studies can be found in [Prz95] and [BP95].
本附录概述了基于Dijkstra的算法，该算法允许预先计算所有目的地的QoS路由和带宽值。使用基于Dijkstra的算法的好处是与现有OSPF实现有更大的协同作用。计算所有“最佳”路径的解决方案是从一个完整的图开始连续计算最短路径生成树，并移除带宽小于先前计算中使用的阈值的链接。这就产生了带宽可能更好但跳数当然更多的路径。尽管涉及大量Dijkstra计算，但可以使用一些优化，例如增量生成树计算，并允许在复杂性和存储方面进行有效实现，因为计算路径的结构倾向于路径压缩[ST83]。有关测量和适用性研究的详细信息，请参见[Prz95]和[BP95]。
A variation of this theme is to trade the "accuracy" of the pre-computed paths, (i.e., the paths being generated may be of a larger hop count than needed) for the benefit of using a modified version of Dijkstra shortest path algorithm and also saving on some computations. This loss in accuracy comes from the need to rely on quantized bandwidth values, which are used when computing a minimum hop count path. In other words, the range of possible bandwidth values that can be requested by a new flow is mapped into a fixed number of quantized values, and minimum hop count paths are generated for each quantized value. For example, one could assume that bandwidth values are quantized as low, medium, and high, and minimum hop count paths are computed for each of these three values. A new flow is then assigned to the minimum hop path that can carry the smallest quantized value, i.e., low, medium, or high, larger than or equal to what it requested. We restrict our discussion here to this "quantized" version of the algorithm.
该主题的一个变体是，为了使用修改版的Dijkstra最短路径算法并节省一些计算，交换预先计算的路径的“准确性”（即，正在生成的路径的跳数可能大于需要的跳数）。这种精度损失源于需要依赖量化带宽值，在计算最小跳数路径时使用量化带宽值。换句话说，新流可以请求的可能带宽值的范围被映射成固定数量的量化值，并且为每个量化值生成最小跳数路径。例如，可以假设带宽值被量化为低、中、高，并且为这三个值中的每一个计算最小跳数路径。然后将新的流分配给最小跳路径，该最小跳路径可以携带最小的量化值，即，低、中或高，大于或等于它所请求的值。我们在此仅讨论该算法的“量化”版本。
Here too, we discuss the elementary case where all edges count as "hops", and note that the modification required for supporting zero-hop edges is straightforward.
在这里，我们也讨论了所有边都被计算为“跳数”的基本情况，并注意到支持零跳边所需的修改非常简单。
As with the BF algorithm, the algorithm relies on a routing table that gets built as the algorithm progresses. The structure of the routing table is as follows:
与BF算法一样，该算法依赖于随着算法的进展而构建的路由表。路由表的结构如下所示：
The QoS routing table:
QoS路由表：
- a K x Q matrix, where K is the number of vertices and Q is the number of quantized bandwidth values.
- 一个K x Q矩阵，其中K是顶点的数量，Q是量化带宽值的数量。
- The (n;q) entry contains information that identifies the minimum hop count path to destination n, which is capable of accommodating a bandwidth request of at least bw[q] (the qth quantized bandwidth value). It consists of two fields:
- （n；q）项包含标识到目的地n的最小跳数路径的信息，该路径能够容纳至少bw[q]（第qth量化带宽值）的带宽请求。它包括两个字段：
* hops: the minimal number of hops on a path between the source node and destination n, which can accommodate a request of at least bw[q] units of bandwidth.
* 跳数：源节点和目标节点n之间路径上的最小跳数，可容纳至少bw[q]单位带宽的请求。
* neighbor: this is the routing information associated with the minimum hop count path to destination node n, whose available bandwidth is at least bw[q]. With a hop-by-hop routing approach, the neighbor information is simply the identity of the node adjacent to the source node on that path.
* 邻居：这是与到目标节点n的最小跳数路径相关联的路由信息，目标节点n的可用带宽至少为bw[q]。使用逐跳路由方法，邻居信息只是该路径上与源节点相邻的节点的标识。
The algorithm operates again on a directed graph where vertices correspond to routers and transit networks. The metric associated with each edge in the graph is as before the bandwidth available on the corresponding interface, where b(n;m) is the available bandwidth on the edge between vertices n and m. The vertex corresponding to the router where the algorithm is being run is selected as the source node for the purpose of path selection, and the algorithm proceeds to compute paths to all other nodes (destinations).
该算法再次在有向图上运行，其中顶点对应于路由器和公交网络。与图中每条边相关联的度量与之前一样是对应接口上的可用带宽，其中b（n；m）是顶点n和m之间边上的可用带宽。与运行算法的路由器相对应的顶点被选择为源节点，用于路径选择，并且算法继续计算到所有其他节点（目的地）的路径。
Starting with the highest quantization index, Q, the algorithm considers the indices consecutively, in decreasing order. For each index q, the algorithm deletes from the original network topology all links (n;m) for which b(n;m) < bw[q], and then runs on the remaining topology a Dijkstra-based minimum hop count algorithm (10) between the source node and all other nodes (vertices) in the graph. Note that as with the Dijkstra used for on-demand path computation, the elimination of links such that b(n;m) < bw[q] could also be performed while running the algorithm.
该算法从最高量化索引Q开始，按降序连续考虑索引。对于每个索引q，该算法从原始网络拓扑中删除b（n；m）<bw[q]的所有链路（n；m），然后在剩余拓扑上运行源节点和图中所有其他节点（顶点）之间基于Dijkstra的最小跳数算法（10）。注意，与用于按需路径计算的Dijkstra一样，也可以在运行该算法时执行链路消除，使得b（n；m）<bw[q]。
After the algorithm terminates, the q-th column in the routing table is updated. This amounts to recording in the hops field the hop count value of the path that was generated by the algorithm, and by updating the neighbor field. As before, the update of the neighbor field depends on the scope of the path computation. In the case of a hop-by-hop routing decision, the neighbor field is set to the identity of the node adjacent to the source node (next hop) on the path returned by the algorithm. However, note that in order to ensure that the path with the maximal available bandwidth is always chosen among all minimum hop paths that can accommodate a given quantized bandwidth, a slightly different update mechanism of the neighbor field needs to be used in some instances. Specifically, when for a given row, i.e., destination node n, the value of the hops field in column q is found equal to the value in column q+1 (here we
算法终止后，将更新路由表中的第q列。这相当于在hops字段中记录由算法生成的路径的hop计数值，并更新邻居字段。与前面一样，邻居字段的更新取决于路径计算的范围。在逐跳路由决策的情况下，邻居字段设置为算法返回的路径上与源节点（下一跳）相邻的节点的标识。然而，注意，为了确保在能够容纳给定量化带宽的所有最小跳路径中始终选择具有最大可用带宽的路径，在一些实例中需要使用稍微不同的邻居字段更新机制。具体地说，当对于给定的行，即目的地节点n，发现列q中的hops字段的值等于列q+1中的值（这里我们
assume q<Q), i.e., paths that can accommodate bw[q] and bw[q+ 1] have the same hop count, then the algorithm copies the value of the neighbor field from entry (n;q+1) into that of entry (n;q).
假设q<q），即可以容纳bw[q]和bw[q+1]的路径具有相同的跳数，则算法将相邻字段的值从条目（n；q+1）复制到条目（n；q）的值。
Note: The pseudocode below assumes a hop-by-hop forwarding approach in updating the neighbor field. The modifications needed to support explicit route construction are straightforward. The pseudocode also does not handle equal cost multi-paths for simplicity, but the modification needed to add this support have been described above. Details of the post-processing step of adding stub networks are omitted.
注意：下面的伪代码假设在更新邻居字段时采用逐跳转发方法。支持显式路由构造所需的修改非常简单。为了简单起见，伪代码也不处理等成本多路径，但添加此支持所需的修改已在上面描述。省略添加存根网络的后处理步骤的细节。
Input: V = set of vertices, labeled by integers 1 to N. L = set of edges, labeled by ordered pairs (n,m) of vertex labels. s = source vertex (at which the algorithm is executed). bw[1..Q] = array of bandwidth values to "quantize" flow requests to. For all edges (n,m) in L: * b(n,m) = available bandwidth (according to last received update) on interface associated with the edge between vertices n and m. * If(n,m) = outgoing interface corresponding to edge (n,m) when n is a router.
输入：V=顶点集，由整数1到N标记。L=边集，由顶点标签的有序对（N，m）标记。s=源顶点（在该顶点执行算法）。bw[1..Q]=用于“量化”流请求的带宽值数组。对于L:*b（n，m）中的所有边（n，m）=与顶点n和m*之间的边关联的接口上的可用带宽（根据上次接收的更新）*If（n，m）=当n是路由器时，对应于边缘（n，m）的输出接口。
Type: tab_entry: record hops = integer, neighbor = integer 1..N, ontree = boolean.
类型：tab_条目：记录跃点=整数，邻居=整数1..N，ontree=布尔值。
Variables:
TT[1..N, 1..Q]: topology table, whose (n,q) entry is a tab_entry
record, such that:
TT[n,q].bw is the available bandwidth (as known
thus far) on a shortest-path between
vertices s and n accommodating bandwidth b(q),
TT[n,q].neighbor is the first hop on that path (a
neighbor of s). It is either a router or the
destination n.
S: list of candidate vertices;
v: vertex under consideration;
q: "quantize" step
Variables:
TT[1..N, 1..Q]: topology table, whose (n,q) entry is a tab_entry
record, such that:
TT[n,q].bw is the available bandwidth (as known
thus far) on a shortest-path between
vertices s and n accommodating bandwidth b(q),
TT[n,q].neighbor is the first hop on that path (a
neighbor of s). It is either a router or the
destination n.
S: list of candidate vertices;
v: vertex under consideration;
q: "quantize" step
The Algorithm:
算法：
begin;
for r:=1 to Q do
begin;
for n:=1 to N do /* initialization */
begin;
for r:=1 to Q do
begin;
for n:=1 to N do /* initialization */
begin;
TT[n,r].hops := infinity;
TT[n,r].neighbor := null;
TT[n,r].ontree := FALSE;
end;
TT[s,r].hops := 0;
end;
for r:=1 to Q do
begin;
S = {s};
while S not empty do
begin;
v := first element of S;
S := S - {v}; /* remove and store the candidate to consider */
TT[v,r].ontree := TRUE;
for all edges (v,m) in L and b(v,m) >= bw[r] do
begin;
if m is a router
begin;
if not TT[m,r].ontree then
begin;
/* bandwidth must be fulfilled since all links >= bw[r] */
if TT[m,r].hops > TT[v,r].hops + 1 then
begin
S := S union { m };
TT[m,r].hops := TT[v,r].hops + 1;
TT[m,r].neighbor := v;
end;
end;
end;
else /* must be a network, iterate over all attached
routers */
begin;
for all (m,k) in L, k <> v,
/* i.e., for all other neighboring routers of m */
if not TT[k,r].ontree and b(m,k) >= bw[r] then
begin;
if TT[k,r].hops > TT[v,r].hops + 2 then
begin;
S := S union { k };
TT[k,r].hops := TT[v,r].hops + 2;
TT[k,r].neighbor := v;
end;
end;
end;
end; /* of all edges from the vertex under consideration */
end; /* from processing of the candidate list */
end; /* of "quantize" steps */
begin;
TT[n,r].hops := infinity;
TT[n,r].neighbor := null;
TT[n,r].ontree := FALSE;
end;
TT[s,r].hops := 0;
end;
for r:=1 to Q do
begin;
S = {s};
while S not empty do
begin;
v := first element of S;
S := S - {v}; /* remove and store the candidate to consider */
TT[v,r].ontree := TRUE;
for all edges (v,m) in L and b(v,m) >= bw[r] do
begin;
if m is a router
begin;
if not TT[m,r].ontree then
begin;
/* bandwidth must be fulfilled since all links >= bw[r] */
if TT[m,r].hops > TT[v,r].hops + 1 then
begin
S := S union { m };
TT[m,r].hops := TT[v,r].hops + 1;
TT[m,r].neighbor := v;
end;
end;
end;
else /* must be a network, iterate over all attached
routers */
begin;
for all (m,k) in L, k <> v,
/* i.e., for all other neighboring routers of m */
if not TT[k,r].ontree and b(m,k) >= bw[r] then
begin;
if TT[k,r].hops > TT[v,r].hops + 2 then
begin;
S := S union { k };
TT[k,r].hops := TT[v,r].hops + 2;
TT[k,r].neighbor := v;
end;
end;
end;
end; /* of all edges from the vertex under consideration */
end; /* from processing of the candidate list */
end; /* of "quantize" steps */
end.
终止
D. Explicit Routing Support
D.显式路由支持
As mentioned before, the scope of the path selection process can range from simply returning the next hop on the QoS path selected for the flow, to specifying the complete path that was computed, i.e., an explicit route. Obviously, the information being returned by the path selection algorithm differs in these two cases, and constructing it imposes different requirements on the path computation algorithm and the data structures it relies on. While the presentation of the path computation algorithms focused on the hop-by-hop routing approach, the same algorithms can be applied to generate explicit routes with minor modifications. These modifications and how they facilitate constructing explicit routes are discussed next.
如前所述，路径选择过程的范围可以从简单返回为流选择的QoS路径上的下一跳到指定计算的完整路径，即显式路由。显然，路径选择算法返回的信息在这两种情况下是不同的，构建它对路径计算算法及其所依赖的数据结构提出了不同的要求。虽然路径计算算法的介绍侧重于逐跳路由方法，但同样的算法可以应用于生成显式路由，只需稍加修改。接下来将讨论这些修改以及它们如何促进构建显式路由。
The general approach to facilitate construction of explicit routes is to update the neighbor field differently from the way it is done for hop-by-hop routing as described in Section 2.3. Recall that in the path computation algorithms the neighbor field is updated to reflect the identity of the router adjacent to the source node on the partial path computed. This facilitates returning the next hop at the source for the specific path. In the context of explicit routing, the neighbor information is updated to reflect the identity of the previous router on the path.
促进显式路由构造的一般方法是更新邻居字段，与第2.3节中描述的逐跳路由不同。回想一下，在路径计算算法中，邻居字段被更新，以反映在计算的部分路径上与源节点相邻的路由器的身份。这有助于在源位置返回特定路径的下一个跃点。在显式路由的上下文中，邻居信息被更新以反映路径上先前路由器的身份。
In general, there can be multiple equivalent paths for a given hop count. Thus, the neighbor information is stored as a list rather than single value. Associated with each neighbor, additional information is stored to facilitate load balancing among these multiple paths at the time of path selection. Specifically, we store the advertised available bandwidth on the link from the neighbor to the destination in the entry.
通常，对于给定的跃点计数，可以有多个等效路径。因此，邻居信息被存储为列表而不是单个值。与每个邻居相关联的附加信息被存储，以便于在路径选择时在这些多条路径之间实现负载平衡。具体地说，我们将从邻居到目的地的链路上公布的可用带宽存储在条目中。
With this change, the basic approach used to extract the complete list of vertices on a path from the neighbor information in the QoS routing table is to proceed `recursively' from the destination to the origin vertex. The path is extracted by stepping through the precomputed QoS routing table from vertex to vertex, and identifying at each step the corresponding neighbor (precursor) information. The process is described as recursive since the neighbor node identified in one step becomes the destination node for table look up in the next step. Once the source router is reached, the concatenation of all the neighbor fields that have been extracted forms the desired explicit route. This applies to algorithms of Section 2.3.1 and Appendix C. If at a particular stage there are multiple neighbor choices (due to equal cost multi-paths), one of them can be chosen at random with a probability that is weighted, for example, by the
通过此更改，用于从QoS路由表中的邻居信息提取路径上的完整顶点列表的基本方法是“递归地”从目的地到原点顶点。通过从一个顶点到另一个顶点逐级遍历预先计算的QoS路由表，并在每一步识别相应的邻居（前体）信息来提取路径。该过程被描述为递归的，因为在一个步骤中标识的邻居节点成为下一个步骤中查找表的目标节点。一旦到达源路由器，已提取的所有相邻字段的串联形成所需的显式路由。这适用于第2.3.1节和附录C中的算法。如果在特定阶段存在多个相邻选择（由于成本相等的多条路径），则可以随机选择其中一个，概率加权，例如：
associated bandwidth on the link from the neighbor to the (current) destination.
从邻居到（当前）目标的链路上的关联带宽。
Specifically, assume a new request to destination, say, d, and with bandwidth requirements B. The index of the destination vertex identifies the row in the QoS routing table that needs to be checked to generate a path. The row is then searched to identify a suitable path. If the Bellman-Ford algorithm of Section 2.3.1 was used, the search proceeds by increasing index (hop) count until an entry is found, say at hop count or column index of h, with a value of the bw field that is equal to or greater than B. This entry points to the initial information identifying the selected path. If the Dijkstra algorithm of Appendix C is used, the first quantized value qB such that qB >= B is first identified, and the associated column then determines the first entry in the QoS routing table that identifies the selected path.
具体地说，假设一个到目的地的新请求，比如d，带宽要求B。目的地顶点的索引标识QoS路由表中需要检查以生成路径的行。然后搜索该行以确定合适的路径。如果使用了第2.3.1节的Bellman-Ford算法，搜索将通过增加索引（跃点）计数继续进行，直到找到一个条目，例如在跃点计数或列索引h处，bw字段的值等于或大于B。该条目指向识别所选路径的初始信息。如果使用附录C中的Dijkstra算法，则首先识别第一个量化值qB，使得qB>=B，然后相关列确定QoS路由表中识别所选路径的第一个条目。
Once this first entry has been identified, reconstruction of the complete list of vertices on the path proceeds similarly, whether the table was built using the algorithm of Section 2.3.1 or Appendix C. Specifically, in both cases, the neighbor field in each entry points to the previous node on the path from the source node and with the same bandwidth capabilities as those associated with the current entry. The complete path is, therefore, reconstructed by following the pointers provided by the neighbor field of successive entries.
一旦识别出第一个条目，路径上完整顶点列表的重建将以类似方式进行，无论该表是使用第2.3.1节或附录C中的算法构建的。具体而言，在这两种情况下，每个入口中的邻居字段指向源节点路径上的前一个节点，并且具有与当前入口相关联的带宽功能。因此，完整路径是通过遵循相邻字段提供的指针来重建的。
In the case of the Bellman-Ford algorithm of Section 2.3.1, this means moving backwards in the table from column to column, using at each step the row index pointed to by the neighbor field of the entry in the previous column. Each time, the corresponding vertex index specified in the neighbor field is pre-pended to the list of vertices constructed so far. Since we start at column h, the process ends when the first column is reached, i.e., after h steps, at which point the list of vertices making up the path has been reconstructed.
对于第2.3.1节的Bellman-Ford算法，这意味着在表中从一列向后移动到另一列，每一步都使用前一列中条目的相邻字段所指向的行索引。每次，在“邻居”字段中指定的对应顶点索引都会预先挂起到目前为止构造的顶点列表。因为我们从h列开始，所以过程在到达第一列时结束，即在h步之后，此时构成路径的顶点列表已重建。
In the case of the Dijkstra algorithm of Appendix C, the backtracking process is similar although slightly different because of the different relation between paths and columns in the routing table, i.e., a column now corresponds to a quantized bandwidth value instead of a hop count. The backtracking now proceeds along the column corresponding to the quantized bandwidth value needed to satisfy the bandwidth requirements of the flow. At each step, the vertex index specified in the neighbor field is pre-pended to the list of vertices constructed so far, and is used to identify the next row index to move to. The process ends when an entry is reached whose neighbor field specifies the origin vertex of the flow. Note that since there are as many rows in the table as there are vertices in the graph, i.e., N, it could take up to N steps before the process terminates.
在附录C的Dijkstra算法的情况下，回溯过程类似，尽管略有不同，因为路由表中的路径和列之间的关系不同，即，列现在对应于量化带宽值而不是跳数。回溯现在沿着与满足流的带宽要求所需的量化带宽值相对应的列进行。在每一步中，“邻居”字段中指定的顶点索引都会预先挂起到目前为止构造的顶点列表，并用于标识要移动到的下一行索引。当到达其相邻字段指定流的原点顶点的条目时，该过程结束。请注意，由于表中的行数与图中的顶点数相同，即N，因此在进程终止之前，可能需要多达N个步骤。
Note that the identification of the first entry in the routing table is identical to what was described for the hop-by-hop routing case. However, as described in this section, the update of the neighbor fields while constructing the QoS routing tables, is being performed differently in the explicit and hop-by-hop routing cases. Clearly, two different neighbor fields can be kept in each entry and updates to both could certainly be performed jointly, if support for both xplicit routing and hop-by-hop routing is needed.
请注意，路由表中第一个条目的标识与针对逐跳路由情况所描述的标识相同。然而，如本节所述，在显式和逐跳路由情况下，在构造QoS路由表时，邻居字段的更新以不同的方式执行。显然，每个条目中可以保留两个不同的邻居字段，如果需要同时支持xplicit路由和逐跳路由，那么对这两个字段的更新肯定可以联合执行。
Endnotes
尾注
1. In this document we commit the abuse of notation of calling a "network" the interconnection of routers and networks through which we attempt to compute a QoS path.
1. 在本文档中，我们滥用了将“网络”称为路由器和网络互连的符号，我们试图通过它来计算QoS路径。
2. This is true for uni-cast flows, but in the case of multi-cast flows, hop-by-hop and an explicit routing clearly have different implications.
2. 这对于单播流是正确的，但是在多播流的情况下，逐跳和显式路由显然有不同的含义。
3. Some hysteresis mechanism should be added to suppress updates when the metric value oscillates around a class boundary.
3. 当度量值围绕类边界振荡时，应该添加一些滞后机制来抑制更新。
4. In this document, we use the terms node and vertex interchangeably.
4. 在本文档中，我们交替使用术语节点和顶点。
5. Various hybrid methods can also be envisioned, e.g., periodic computations except if more than a given number of updates are received within a shorter interval, or periodic updates except if the change in metrics corresponding to a given update exceeds a certain threshold. Such variations are, however, not considered in this document.
5. 还可以设想各种混合方法，例如，周期性计算，除非在较短的间隔内接收到超过给定数量的更新，或者周期性更新，除非与给定更新相对应的度量变化超过某个阈值。但是，本文件不考虑此类变更。
6. Modifications to support explicit routing are discussed in Appendix D.
6. 附录D中讨论了支持显式路由的修改。
7. Note, that this does not say anything on whether to differentiate between outgoing and incoming bandwidth on a shared media network. As a matter of fact, a reasonable option is to set the incoming bandwidth (from network to router) to infinity, and only use the outgoing bandwidth value to characterize bandwidth availability on the shared network.
7. 请注意，这并没有说明是否区分共享媒体网络上的传出和传入带宽。事实上，一个合理的选择是将传入带宽（从网络到路由器）设置为无穷大，并且仅使用传出带宽值来表征共享网络上的带宽可用性。
8. exponent in parenthesis
8. 括号中的指数
9. Access to some of the more recent versions of the GateD software is restricted to the GateD consortium members.
9. 对某些最新版本的门控软件的访问仅限于门控联盟成员。
10. Note that a Breadth-First-Search (BFS) algorithm [CLR90] could also be used. It has a lower complexity, but would not allow reuse of existing code in an OSPF implementation.
10. 请注意，还可以使用广度优先搜索（BFS）算法[CLR90]。它具有较低的复杂性，但不允许在OSPF实现中重用现有代码。
References
工具书类
[AGK99] G. Apostolopoulos, R. Guerin, and S. Kamat. Implementation and performance meassurements of QoS routing extensions to OSPF. In Proceedings of INFOCOM'99, pages 680--688, New York, NY, March 1999.
[AGK99]G.Apostolopoulos、R.Guerin和S.Kamat。OSPF QoS路由扩展的实现和性能测量。1999年3月，纽约，INFOCOM'99会议记录，第680-688页。
[AGKT98] G. Apostolopoulos, R. Guerin, S. Kamat, and S. K. Tripathi. QoS routing: A performance perspective. In Proceedings of ACM SIGCOMM'98, pages 17--28, Vancouver, Canada, October
[AGKT98]G.Apostolopoulos、R.Guerin、S.Kamat和S.K.Tripathi。QoS路由：性能透视图。《ACM SIGCOMM'98会议记录》，第17-28页，加拿大温哥华，10月
[Alm92] Almquist, P., "Type of Service in the Internet Protocol Suite", RFC 1349, July 1992.
[Alm92]Almquist，P.，“互联网协议套件中的服务类型”，RFC 1349，1992年7月。
[AT98] G. Apostolopoulos and S. K. Tripathi. On reducing the processing cost of on-demand QoS path computation. In Proceedings of ICNP'98, pages 80--89, Austin, TX, October 1998.
[AT98]G.Apostolopoulos和S.K.Tripathi。降低按需QoS路径计算的处理成本。1998年10月，德克萨斯州奥斯汀，ICNP'98会议记录，第80-89页。
[BP95] J.-Y. Le Boudec and T. Przygienda. A Route Pre-Computation Algorithm for Integrated Services Networks. Journal of Network and Systems Management, 3(4), 1995.
[BP95]J.-Y.Le Boudec和T.Przygienda。一种综合业务网路由预计算算法。网络与系统管理杂志，3（4），1995年。
[Car79] B. Carre. Graphs and Networks. Oxford University Press, ISBN 0-19-859622-7, Oxford, UK, 1979.
[Car79]B.Carre。图形和网络。牛津大学出版社，ISBN 0-19-859622-7，英国牛津，1979年。
[CLR90] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1990.
[CLR90]T.H.Cormen、C.E.Leiserson和R.L.Rivest。算法简介。麻省理工学院出版社，马萨诸塞州剑桥，1990年。
[Con] Merit GateD Consortium. The Gate Daemon (GateD) project.
[反对]有价值的联盟。门守护程序（门控）项目。
[GJ79] M.R. Garey and D.S. Johnson. Computers and Intractability. Freeman, San Francisco, 1979.
[GJ79]M.R.Garey和D.S.Johnson。计算机和难处理性。Freeman，旧金山，1979岁。
[GKH97] R. Guerin, S. Kamat, and S. Herzog. QoS Path Management with RSVP. In Proceedings of the 2nd IEEE Global Internet Mini-Conference, pages 1914-1918, Phoenix, AZ, November
[GKH97]R.Guerin、S.Kamat和S.Herzog。使用RSVP进行QoS路径管理。第二届IEEE全球互联网小型会议记录，1914-1918页，亚利桑那州凤凰城，11月
[GKR97] Guerin, R., Kamat, S. and E. Rosen, "An Extended RSVP Routing Interface, Work in Progress.
[GKR97]Guerin，R.，Kamat，S.和E.Rosen，“一个扩展的RSVP路由接口，正在进行中。
[GLG+97] Der-Hwa G., Li, T., Guerin, R., Rosen, E. and S. Kamat, "Setting Up Reservations on Explicit Paths using RSVP", Work in Progress.
[GLG+97]Der Hwa G.，Li，T.，Guerin，R.，Rosen，E.和S.Kamat，“使用RSVP在显式路径上设置保留”，工作正在进行中。
[GO99] R. Guerin and A. Orda. QoS-Based Routing in Networks with Inaccurate Information: Theory and Algorithms. IEEE/ACM Transactions on Networking, 7(3):350--364, June 1999.
[GO99]R.Guerin和A.Orda。信息不准确网络中基于QoS的路由：理论和算法。IEEE/ACM网络交易，7（3）：350-364，1999年6月。
[GOW97] R. Guerin, A. Orda, and D. Williams. QoS Routing Mechanisms and OSPF Extensions. In Proceedings of the 2nd IEEE Global Internet Mini-Conference, pages 1903-1908, Phoenix, AZ, November 1997.
[GOW97]R.Guerin、A.Orda和D.Williams。QoS路由机制和OSPF扩展。《第二届IEEE全球互联网小型会议记录》，第1903-1908页，亚利桑那州凤凰城，1997年11月。
[KNB98] Nichols, K., Blake, S., Baker F. and D. Black, "Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers", RFC 2474, December 1998.
[KNB98]Nichols，K.，Blake，S.，Baker F.和D.Black，“IPv4和IPv6标头中区分服务字段（DS字段）的定义”，RFC 2474，1998年12月。
[LO98] D. H. Lorenz and A. Orda. QoS Routing in Networks with Uncertain Parameters. IEEE/ACM Transactions on Networking, 6(6):768--778, December 1998.
[LO98]D.H.洛伦兹和A.奥达。参数不确定网络中的QoS路由。IEEE/ACM网络交易，6（6）：768-7781998年12月。
[Moy94] Moy, J., "OSPF Version 2", RFC 1583, March 1994.
[Moy94]Moy，J.，“OSPF版本2”，RFC 1583，1994年3月。
[Moy98] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[Moy98]Moy，J.，“OSPF版本2”，STD 54，RFC 23281998年4月。
[Prz95] A. Przygienda. Link State Routing with QoS in ATM LANs. Ph.D. Thesis Nr. 11051, Swiss Federal Institute of Technology, April 1995.
[Prz95]A.普济吉恩达。ATM局域网中具有QoS的链路状态路由。博士。论文编号11051，瑞士联邦理工学院，1995年4月。
[RMK+98] R. Rajan, J. C. Martin, S. Kamat, M. See, R. Chaudhury, D. Verma, G. Powers, and R. Yavatkar. Schema for differentiated services and integrated services in networks. INTERNET-DRAFT, October 1998. work in progress.
[RMK+98]R.Rajan、J.C.Martin、S.Kamat、M.See、R.Chaudhury、D.Verma、G.Powers和R.Yavatkar。网络中区分服务和集成服务的模式。因特网草稿，1998年10月。正在进行的工作。
[RZB+97] Braden, R., Editor, Zhang, L., Berson, S., Herzog, S. and S. Jamin, "Resource reSerVation Protocol (RSVP) Version 1, Functional Specification", RFC 2205, September 1997.
[RZB+97]Braden，R.，编辑，Zhang，L.，Berson，S.，Herzog，S.和S.Jamin，“资源预留协议（RSVP）版本1，功能规范”，RFC 22052997年9月。
[SPG97] Shenker, S., Partridge, C. and R. Guerin, "Specification of Guaranteed Quality of Service", RFC 2212, November 1997.
[SPG97]Shenker，S.，Partridge，C.和R.Guerin，“保证服务质量规范”，RFC 2212，1997年11月。
[ST83] D.D. Sleator and R.E. Tarjan. A Data Structure for Dynamic Trees. Journal of Computer Systems, 26, 1983.
[ST83]D.D.Sleator和R.E.Tarjan。动态树的数据结构。《计算机系统杂志》，1983年第26期。
[Tan89] A. Tannenbaum. Computer Networks. Addisson Wesley, 1989.
[Tan89]A.Tannenbaum。计算机网络。艾迪森·韦斯利，1989年。
[YPG97] Yavatkar, R., Pendarakis, D. and R. Guerin, "A Framework for Policy-based Admission Control", INTERNET-DRAFT, April 1999. Work in Progress.
[YPG97]Yavatkar，R.，Pendarakis，D.和R.Guerin，“基于政策的准入控制框架”，互联网草案，1999年4月。正在进行的工作。
Authors' Addresses
作者地址
George Apostolopoulos IBM T.J. Watson Research Center P.O. Box 704 Yorktown Heights, NY 10598
George Apostolopoulos IBM T.J.Watson研究中心纽约约克敦高地704号信箱，邮编10598
Phone: +1 914 784-6204
Fax: +1 914 784-6205
EMail: georgeap@watson.ibm.com
Phone: +1 914 784-6204
Fax: +1 914 784-6205
EMail: georgeap@watson.ibm.com
Roch Guerin University Of Pennsylvania Department of Electrical Engineering, Rm 367 GRW 200 South 33rd Street Philadelphia, PA 19104--6390
宾夕法尼亚大学电气工程系，费城南部第三十三街200号，RM 367，19104—6390
Phone: +1 215-898-9351
EMail: guerin@ee.upenn.edu
Phone: +1 215-898-9351
EMail: guerin@ee.upenn.edu
Sanjay Kamat Bell Laboratories Lucent Technologies Room 4C-510 101 Crawfords Corner Road Holmdel, NJ 07733
Sanjay Kamat Bell Laboratories Lucent Technologies 4C-510室新泽西州霍姆德尔克劳福德角路101号07733
Phone: (732) 949-5936 email: sanjayk@dnrc.bell-labs.com
电话：（732）949-5936电子邮件：sanjayk@dnrc.bell-实验室网站
Ariel Orda Dept. Electrical Engineering Technion - I.I.T Haifa, 32000 - ISRAEL
Ariel Orda电气工程技术部-I.I.T海法，32000-以色列
Phone: +011 972-4-8294646
Fax: +011 972-4-8323041
EMail: ariel@ee.technion.ac.il
Phone: +011 972-4-8294646
Fax: +011 972-4-8323041
EMail: ariel@ee.technion.ac.il
Tony Przygienda Siara Systems 300 Ferguson Drive Moutain View California 94043
Tony Przygienda Siara Systems 300 Ferguson Drive Mountain View加利福尼亚94043
Phone: +1 732 949-5936
Email: prz@siara.com
Phone: +1 732 949-5936
Email: prz@siara.com
Doug Williams IBM T.J. Watson Research Center P.O. Box 704 Yorktown Heights, NY 10598
Doug Williams IBM T.J.Watson研究中心纽约约克敦高地704号信箱，邮编10598
Phone: +1 914 784-5047
Fax: +1 914 784-6318
EMail: dougw@watson.ibm.com
Phone: +1 914 784-5047
Fax: +1 914 784-6318
EMail: dougw@watson.ibm.com
Full Copyright Statement
完整版权声明
Copyright (C) The Internet Society (1999). All Rights Reserved.
版权所有（C）互联网协会（1999年）。版权所有。
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
本文件及其译本可复制并提供给他人，对其进行评论或解释或协助其实施的衍生作品可全部或部分编制、复制、出版和分发，不受任何限制，前提是上述版权声明和本段包含在所有此类副本和衍生作品中。但是，不得以任何方式修改本文件本身，例如删除版权通知或对互联网协会或其他互联网组织的引用，除非出于制定互联网标准的需要，在这种情况下，必须遵循互联网标准过程中定义的版权程序，或根据需要将其翻译成英语以外的其他语言。
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
上述授予的有限许可是永久性的，互联网协会或其继承人或受让人不会撤销。
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
本文件和其中包含的信息是按“原样”提供的，互联网协会和互联网工程任务组否认所有明示或暗示的保证，包括但不限于任何保证，即使用本文中的信息不会侵犯任何权利，或对适销性或特定用途适用性的任何默示保证。
Acknowledgement
确认
Funding for the RFC Editor function is currently provided by the Internet Society.
RFC编辑功能的资金目前由互联网协会提供。