Towards Scalable Quality of Service Routing

迈向可扩展的服务质量路由

• 批准号: 0106706
• 负责人: Xin Yuan
• 金额: $ 14.27万
• 依托单位: Florida State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-15 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0106706&HistoricalAwards=false
• 关键词: Towards; Scalable; Quality; Service; Routing

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.

为了支持下一代互联网的服务质量（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路由方案。