服务质量qos路由理论与实现的核心问题

《服务质量qos路由理论与实现的核心问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、服务质量(QoS)路由理论与实现的核心问题清华大学计算机系博士后解放军炮兵学院副教授崔逊学一、问题背景二、过去不成熟的解决方案三、核心问题四、研究展望Agenda一、问题背景当前的互联网只能提供尽力而为的发送服务，网络层无法区分用户业务的种类，而将网络资源公平地提供给各类业务，在对分组丢失率、延迟等方面的考虑上公平地处理各类业务。这种机制使网络层无法控制传输的质量。因此，为不同应用提供不同的服务质量(QoS)是互联网面临的重要研究课题。如果在网络上真正实现了服务质量路由（或称多约束路由：MCP），网络就达到了很好的负载均衡，则目前流量工程中的许多问题也就迎刃而解

2、。目前的研究成果表明：在区域内部通过合理的配置基于链路状态的服务质量路由协议，对于支持服务质量所引入的开销是可以接受的。因此说，在当前的互联网上实现服务质量总体上是可行的。二、过去不成熟的解决方案集成服务(IntServ)是为了实现网络服务质量最早提出的框架，它具有面向连接和资源预留的特点。面向连接的机制会导致核心路由器所维护的信息量爆炸而降低可扩展性；资源预留机制会引起网络使用率的下降和代价的增加。因此，集成服务框架类似于电信网络，它与互联网的基本机制相悖离，在大规模互联网环境下集成服务不具有可行性。为了提高网络传输的可扩展性，人们提出区分服务(DiffSer

3、v)框架，通过聚类解决了集成服务所面临的可扩展性问题。但是，区分服务框架无法区分参数类型，并不能从根本上提供服务质量。现有的服务质量路由研究常常面向连接，可扩展性较差。最好的升级路由的方法是实现基于现有互联网的无连接逐跳路由。但以前的研究证明，寻找满足多约束的可行路径具有NPC的复杂度。人们对此问题研究很多，有关的启发式路由算法已经比较成熟。但是启发式路由算法在实现时，是在集成服务框架中来提供服务质量。这意谓着将采用面向连接的方式并要求资源预留。因此这种体系就会与集成服务一样缺乏可行性。目前最好的启发式服务质量路由算法是H_MCOP算法。它的复杂度很低；找到可行

4、解的成功率很接近精确算法。三、核心问题服务质量路由包括协议和算法两部分。当前对这两方面的研究都存在严重的不足。多个加性度量的服务质量路由已被证明为NP完全问题，这个定理极大地影响了研究机构，导致人们普遍认为精确的路由在实际中是不可行的。因此针对该问题涌现了许多启发式算法。但是，很少有人认真地分析过哪些最坏的情形导致了NPC行为。实际上MCP问题不是强NPC的，这表明精确算法可以在多项式时间内求解。另外，实际网络中人们很少遇到网络传输的NP-C行为。在大多数真实网络中，服务质量路由问题是不是在多项式时间内无法求解，有待于进一步研究。1996年Wang和Crowcr

5、oft证明了当约束条件数大于等于2时，服务质量路由问题为NP完全问题。他们主要是将约束数目为2的MCP问题归结为分割问题的一个实例，而分割问题属于典型的NP完全问题。但一些实验表明事实并非如此。包括分割问题在内的一类问题已经被许多人验证为是可解的。目前也已经有伪多项式算法来求解路由问题。至少已发现三种情况在多项式时间内可解:(1)服务质量参数之间是相关的，即如果所有参数都与某一种度量相关，则它可在多项式时间内求解。(2)如果多个服务质量参数除了其中一种外，其它都在有界整数中取值，则这类问题可通过扩展的Dijkstra或Bellman-Ford算法在多项式时间内求

6、解。(3)MCP问题不是强NP完全问题，因为目前已有伪多项式算法来精确求解该问题。本人认为路由协议才是目前实现服务质量的关键。但现在对这方面的探索很少，研究它的难度远比算法困难。(一）协议问题四、研究展望在面向联接的网络中路由协议（ATM中的PNNI）已经标准化，但在无联接的网络（Internet）中服务质量路由协议尚无标准。域内的路由协议相对容易些升级，但域间的BGP-4协议就很难升级为服务质量路由协议。目前对于无联接的网络，还不存在可行的服务质量路由协议。因此，研究的焦点应该适当地从算法转移到协议上来。（二）可扩展性问题基于全局状态和源路由的协议和算法的可扩

7、展性都比较差。虽然通过网络状态聚集能以对数缩减信息量，使得相应的分层路由解决可扩展性问题，但是又产生了新的问题：目前所设计的状态聚集方法，往往会丢失大量的可用信息，严重影响了性能。随着网络规模的扩大，可扩展性始终是网络研究的一个主题。无论是现在还是将来的路由体系结构，都须采用层次化的模型。层次化的目的在于压缩和聚集网络的状态信息，但压缩和聚集会引起网络状态信息的丢失。如何从根本上解决这一矛盾从而提高路由算法的性能，也是一个重要的研究方向。通常需要模拟试验对设计的算法或协议进行评价，这就要采用一定的网络拓扑和业务流模型。目前存在几种常用的拓扑模型：1)采用众所周知

8、的拓扑结构，如ARPAn