Towards Scalable Quality of Service Routing

为了支持下一代互联网的服务质量（QoS），需要对路由、调度和接纳控制等网络组件提出新的算法。 QoS路由是QoS提供的重要组成部分之一，它识别具有足够资源以满足连接的QoS要求的路径，并为该连接选择路径。 虽然已经提出了许多QoS路由算法，但要在大规模网络中实现高效的QoS路由，即可扩展的QoS路由，仍有许多理论和实践问题有待解决。 本研究将试图解决其中的一些问题。 具体而言，我们将重点关注以下四个方面：网络状态聚合。 对于大型网络，实现可扩展路由的常用方法是根据网络的层次结构聚合信息来减小全局网络状态的大小。 ATM专用网络-网络接口（PNNI）标准已经采用了这种方法。 然而，当涉及多个QoS度量时，精确地聚合域的信息可能是不可行的，因为它需要相对于域的大小呈指数增长的存储器空间。 在本研究中，我们将设计不同的拓扑聚合方案，研究所需的空间量和有效性之间的权衡方案，总结域信息，调查不同的拓扑聚合方案的QoS路由性能，并确定拓扑聚合方案是有效的，在实践中的QoS路由与多个QoS指标。处理全局网络状态信息的随机不精确性。在大规模网络中，维护精确的全局状态信息需要频繁分布链路状态，这导致沿着多个维度（包括带宽、存储、更新处理和相关上下文切换）的大量协议开销。 为了控制协议开销，可能会降低链路状态更新频率，这导致全局状态信息不精确。 由不频繁的链路状态更新引起的不精确性在路由器不能估计准确的全局网络状态的意义上是随机的。 因此，一个实用的QoS路由算法必须能够使用不精确的全局网络状态信息执行有效的路由。 在这项研究中，我们提出了一种新的路由方案，执行有效的路由存在不精确的全局状态信息。 我们的方案是不同于现有的方法，它结合了静态和动态路由，并适应基于网络状态的路由方案。 我们将比较我们的计划与现有的方法在路由性能和协议开销方面，并通过大量的模拟，确定每种方法的优点和缺点。 资源预留与QoS路由的交互。 目前大多数QoS路由算法假设一个单独的协议来执行资源预留。 然而，在未来的大规模高速网络中，希望将联合收割机资源预留与QoS路由相结合。 将资源预留与QoS路由结合可能会对路由性能产生负面影响，特别是对于大型网络。 本研究将尝试了解资源预留对各种QoS路由方案的影响，并开发在资源预留流量存在下实现有效路由的技术。多约束QoS路由和通用QoS路由算法。 多约束QoS路由查找满足多个独立QoS约束的路径。 这个问题是NP难的。然而，分布式应用，如互联网电话和分布式游戏有非常不同的QoS要求的延迟，成本，延迟抖动，丢失率，带宽等，以支持这样的应用，实用的多约束QoS路由算法必须开发。 此外，由于多约束QoS路由的复杂性，现有的QoS路由算法对QoS约束的类型和数量有很大的限制，这意味着不同的应用需要不同的QoS路由算法。在未来的网络中，人们希望使用一种通用的QoS路由算法，可以有效地处理不同的QoS要求。 在本研究中，我们将研究在实践中有效地解决多约束路由问题的启发式算法，并开发出一种通用算法，无论QoS要求的数量和类型，我们计划通过在Qbone中实现所提出的技术来评估我们的技术，并通过在真实的网络中的实现和实验来验证这些技术。 我们相信，通过开发有效的机制来解决这四个问题，我们将能够集成的机制，并开发高效的可扩展的QoS路由方案，为未来的大规模高速网络。

To support Quality of Service (QoS) in the Next Generation Internet, new algorithms are needed for many network components, including routing, scheduling and admission control. QoS routing, which identifies paths that have sufficient resources to satisfy the QoS requirement of a connection and selects a path for that connection, is one of the most important components for QoS provision. Although many QoS routing algorithms have been proposed, a number of theoretical and practical issues remain to be addressed to achieve efficient QoS routing in large scale networks, that is, scalable QoS routing. This research will attempt to address some of these issues. Specifically, we will focus on the following four areas.Networking state aggregation. For a large network, a common approach to achieve scalable routing is to reduce the size of global network state by aggregating information according to the hierarchical structure of the network. This approach has been adopted by the ATM private network-network interface (PNNI) standard. However, when multiple QoS metrics are involved, precisely aggregating information of a domain may not be feasible since it requires memory space that grows exponentially with respect to the size of the domain. In this research, we will design various topology aggregation schemes, study the trade-offs of the schemes between the amount of space needed and the effectiveness in summarizing the domain information, investigate the QoS routing performance with different topology aggregation schemes, and determine the topology aggregation schemes that are effective in practice for QoS routing with multiple QoS metrics. Handling random imprecision of the global network state information. In large scale networks, maintaining precise global state information requires link states to be distributed frequently, which results in large protocol overheads along multiple dimensions including bandwidth, storage, update processing, and the associated context switching. To control the protocol overhead, the link state update frequency may be reduced, which results in the imprecise global state information. The imprecision caused by the infrequent link state updates is random in the sense that a router cannot estimate the accurate global network state. Thus, a practical QoS routing algorithm must be able to perform effective routing using the imprecise global network state information. In this research, we propose a novel routing scheme that performs effective routing in the presence of imprecise global state information. Our scheme is different from the existing methods in that it combines static and dynamic routing and adapts the routing schemes based on network status. We will compare our scheme with the existing methods in terms of routing performance and protocol overheads and identify the strengths and weaknesses of each method through extensive simulations. Interaction between resource reservation and QoS routing. Most current QoS routing algorithms assume a separate protocol to perform resource reservation. However, in the future large scale high speed networks, it is desirable to combine resource reservation with QoS routing. Combing resource reservation with QoS routing may have negative impacts on the routing performance, especially for large networks. This research will try to understand the impact of resource reservation on various QoS routing schemes and develop techniques to achieve effective routing in the presence of resource reservation traffic.Multi-constrained QoS routing and generic QoS routing algorithms. Multi-constrained QoS routing finds a path that satisfies multiple independent QoS constraints. This problem is NP-hard. However, distributed applications such as the Internet phone and distributed games have very diverse QoS requirements on delay, cost, delay jitter, loss ratio, bandwidth, etc. To support such applications, practical multi-constrained QoS routing algorithms must be developed. Furthermore, due to the complexity of multi-constrained QoS routing, existing QoS routing algorithms are very restrictive on the type and the number of QoS constraints, which implies that different QoS routing algorithms will be needed for different applications. In the future networks, it is desirable to use a generic QoS routing algorithm that can efficiently handle different QoS requirements. In this research, we will study the heuristic algorithms that solve the multi-constrained routing problem effectively in practice and develop a generic algorithm that performs well regardless of the number and the types of QoS requirements.We plan to evaluate our techniques by implementing the proposed techniques in Qbone and to validate the techniques through implementation and experimentation in the real network. We believe that by developing effective mechanisms to address these four issues, we will be able to integrate the mechanisms and develop efficient scalable QoS routing schemes for the future large scale high speed networks.