服务质量(QoS)路由理论与实现的核心问题.ppt

1、清华大学计算机科学系、中国人民解放军炮兵学院博士后副教授崔训学是QoS路由理论与实现的核心问题。首先，问题的背景。第二，过去不成熟的解决方案。第三，核心问题。第四，研究展望，议程。首先，问题的背景是，当前的互联网只能提供尽力而为的交付服务，而网络层不能区分用户服务的类型，而是公平地为各种服务提供网络资源。在丢包率和延迟等方面。这种机制使得网络层无法控制传输质量。因此，为不同的应用提供不同的服务质量是互联网面临的一个重要研究课题。如果服务质量路由(MCP)真正在网络上实现，网络将实现良好的负载平衡，当前流量工程中的许多问题将很容易解决。目前的研究结果表明，通过合理配置区域内基于链路状态的服务质量

2、路由协议，支持服务质量的成本是可以接受的。因此，在当前的互联网上实现服务质量一般是可行的。第二，IntServ是过去不成熟的解决方案，是最早提出的实现网络服务质量的框架，它具有面向连接和资源预留的特点。面向连接的机制会导致核心路由器维护的信息爆炸，降低可扩展性；资源预留机制会导致网络利用率的降低和成本的增加。因此，综合业务框架类似于电信网络，违背了互联网的基本机制，在大规模互联网环境下综合业务是不可行的。为了提高网络传输的可扩展性，人们提出了区分服务(DiffServ)框架，通过分簇来解决综合业务所面临的可扩展性问题。然而，差异化服务框架不能区分参数类型，也不能从根本上提供服务质量。现有的服务

3、质量路由研究往往是面向连接的，扩展性差。升级路由的最好方法是在现有互联网的基础上实现无连接逐跳路由。然而，先前的研究已经证明，寻找满足多个约束的可行路径具有NPC复杂性。人们对这个问题已经做了大量的研究，相关的启发式路由算法也比较成熟。然而，当启发式路由算法被实现时，它在集成服务框架中提供服务质量。这意味着将采用面向连接的方法，并且需要资源预留。因此，这个系统将像综合服务一样不可行。目前，最好的启发式服务质量路由算法是MCOP算法。它的复杂性非常低；找到可行解的成功率接近精确算法。第三，核心问题，服务质量路由包括两个部分：协议和算法。目前，这两个方面的研究存在严重不足。具有多个附加度量的服务质

4、量路由被证明是NP完全问题。这个定理极大地影响了研究机构，这导致人们普遍认为准确的路由在实践中是不可行的。因此，出现了许多启发式算法来解决这个问题。然而，很少有人认真分析过哪些最坏的情况会导致NPC行为。实际上，MCP问题不是强NPC问题，这表明精确算法可以在多项式时间内求解。另外，人们在实际网络中很少遇到网络传输的NP-C行为。在大多数实际网络中，服务质量路由问题是否不能在多项式时间内解决，需要进一步研究。1996年，王和克罗夫特证明了当约束数大于或等于2时，服务质量路由问题是NP完全的。他们主要将带有两个约束的主成分分析问题归结为一个典型的NP完全问题分割问题。但是一些实验表明事实并非如此

5、。一类问题，包括分割问题，已经被许多人证明是可以解决的。目前，有伪多项式算法来解决路由问题。至少有三种情况在多项式时间内是可解的。(1)服务质量参数是相关的，也就是说，如果所有参数都与某个度量相关，则可以在多项式时间内求解。(2)如果服务质量参数中除一个以外都是有界整数，这类问题可以用扩展的迪克斯特拉算法或贝尔曼-福特算法在多项式时间内求解。(3)微通道板问题不是一个强NP完全问题，因为伪多项式算法已经被用来精确地求解这个问题。在我看来，路由协议是目前实现服务质量的关键。然而，这方面的探索很少，而且研究起来比研究算法要困难得多。(1)协议问题；(4)研究前景：在面向连接的网络中，路由协议(自动

6、柜员机中的PNNI)已经标准化，但在无连接网络(互联网)中，没有服务质量路由协议的标准。域内路由协议相对容易升级，但域间BGP-4协议很难升级到服务质量路由协议。目前，无连接网络没有可行的服务质量路由协议。因此，研究的重点应该适当地从算法转向协议。(2)可扩展性。基于全局状态和源路由的协议和算法的可扩展性较差。虽然网络状态聚合可以将信息量以对数形式减少，使得相应的分层路由解决了可扩展性问题，但也带来了一个新问题：目前设计的状态聚合方法往往会丢失大量可用信息，严重影响性能。随着网络规模的扩大，可扩展性一直是网络研究的话题。当前和未来的路由体系结构都必须采用分层模型。层次结构的目的是压缩和聚合网络

7、状态信息，但是压缩和聚合会导致网络状态信息的丢失。如何从根本上解决这一矛盾，提高路由算法的性能也是一个重要的研究方向。通常，需要模拟实验来评估所设计的算法或协议，这需要一定的网络拓扑和服务流模型。目前，有几种常用的拓扑模型：1)采用众所周知的拓扑结构，如ARPAnet网络；2)随机生成拓扑结构，例如平面随机图；3)特定规则的结构，如网格结构。根据实际网络的研究结果，目前还没有“典型”的网络拓扑和流量模型来指导路由的研究。(3)拓扑模型。目前，互联网已经有了相当大的规模。彻底取代现有的尽力而为的IPv4网络将是一个漫长而艰巨的过程。未来的网络应该是服务质量路由和尽力传输的结合。从目前状态分析，改

8、造过程应采用覆盖模式，即在新增加的网络设备中逐步增加具有服务质量功能的路由器，或者逐步更换原有设备。因此，基于覆盖的理论框架和核心算法设计是实际应用中的一个重要问题。(4)实施模式，中国学者闵华英指出，目前理论界对网络基础研究存在两个思想障碍：一是认为互联网上路由器的硬件和软件已经形成，不太可能改变，骨干网上的核心路由器技术完全被思科等国外大公司所控制。这种观点只来自于工程技术发展的角度，只看到了目前国内的情况。(5)理论研究的重要性从自然科学基础研究的角度来看，如果国内研究人员受现有协议和RFC的约束，很难看到原创作品的价值和意义。只有当基础研究工作做得充分而扎实，突破了现有的或不完善的国际协定和草案，并能实际转化为应用时，工业部门将不可避免地接受这些理论成果。另一个是人们对实用性的误