平面网络中QOS多播路由算法研究与设计

梅创社

（陕西工业职业技术学院 陕西 咸阳 712000）

网络路由[1]包括两个方面的任务:一方面是收集网络状态信息并力求保持最新；另一方面，在获取状态信息的基础上，为连接请求找到满足某种要求的网络路径。目前所用到的大多数路由算法，不管是单播路由算法还是多播路由算法，都要求网络中的每个节点维护着整个网络的状态信息。然而，由于网络流量负载的快速变化，使得网络中的节点所获取的状态信息变得不及时和不精确，即动态网络中的状态信息存在着固有的非精确性。

随着Internet中多媒体业务与实时业务快速发展，QOS多播路由问题在网络研究领域己经得到了越来越多的重视和关注。多播路由及其QOS扩展的主要目标是要构造一棵满足某些性能约束（例如，端到端的延迟有界、延迟抖动有界、最小可用带宽以及最大包丢失率等）并对某个目标函数（例如，能反应网络资源利用的网络代价）进行优化的多播树。

传统的多播路由协议，例如DVMRP和PIM，主要为“尽力而为”的数据流设计，其多播树的构造主要是基于网络拓扑的连接性，并且不带有QOS约束。但最近却出现了一些带QOS约束的多播路由算法，这些算法通常运用一个启发式的方案来化解带约束的Steiner树（例如，延迟受限的最小代价树）这类NP一完全问题。然而，这些算法在计算路由时，通常需要用到全局的网络状态信息，而且也没有能够很好地处理多播组成员的动态加入和退出，消息交换的负载也很大，因此，它们中的多数在Internet中并不实用。……