基于演化算法的qos约束选播路由研究

《基于演化算法的qos约束选播路由研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、根据选播通信模式的特点，选播可以被广泛地应用到多种网络服务中，例如：将选播应用到分布式复制服务器技术时，能够用一个选播地址来标识多个镜像服务器，当用户发出服务请求时，根据路由协议从这个包含多个镜像服务器的选播组中选择出一个对当前用户来说是最合适的服务器来提供服务，这种通信模式能够有效地改善网络流量分布，防止某一个服务器被过多用户选择而造成网络拥塞。选播也支持主机自动配置，为DNS、www“mirror”站点等提供透明服务；支持移动IP本地代理的查找，使得节点能方便地获取就近服务而不需要更换代理重新注册。因而，选播通信模式能够有效地降低

2、此类网络服务的复杂性，合理地调整网络流量分布，减轻现有网络负担，提高服务的可用性。传统Internet在保障服务质量方面存在着诸多问题，只能够提供“尽力而为（Best-effort）”的数据传输服务，在服务时间和服务可靠性上缺乏保障。QoS路由是解决这些问题的有效手段，QoS路由是一种基于网络的可用资源和业务流的QoS要求来选择网络路径的路由机制，常见QoS度量有：带宽、时延、时延抖动、丢包率以及代价等。[4]已有研究表明，基于多个不相关可加度量的QoS路由问题是一个NP完全问题。近年来，演化算法作为求解NP难问题和最优化问题的有效工

3、具，引起了越来越多人的关注。演化[5]算法是模拟生物在自然环境中的遗传演化过程而发展起来的一种全局优化概率搜索算法，它的基本思想是借鉴达尔文的“适者生存”的自然法则，利用染色体来表达问题可行解的具体结构，通过对染色体进行选择、交叉和变异等演化操作，实现优胜劣汰的自然选择来指导问题的解朝着最优解的方向演化并最终得到问题的解。在单播、多播等传统通信模式中，针对QoS路由问题有着广泛且深入的研究，并已[6-8]取得了不少的研究成果，例如：以Dijkstra算法为基础的众多路由算法能够很好地解决具有可加性度量的QoS约束路由问题。但选播通信模

4、式作为一个新的网络技术研究方向，在国外内相关研究工作开展较少，因此本论文根据选播通信模式的特点，着重研究如何解决满足多项QoS约束的选播路由问题，为将来选播通信模式的具体实施应用奠定基础，对提高和促进我国在计算机网络技术及其相关领域技术的发展也具有重要的战略意义。1.2国内外研究现状1.2.1选播通信模式从选播通信模式的语义特点中可得出，选播通信的本质是从众多的镜像服务器中选出一个相对于请求服务的客户端来说是“最优”的服务器来提供服务，这种“最优”的标准不是固定的，可以是跳数最小，或带宽最大，或时延最小等，还可以是同时要求多个最优标准

5、。目前，国内外对选播通信模式的研究主要是从两个方面展开：2一方面是从应用层着手，包括：模型的研究、目标站点选取策略的研究等，主要是通过管理手段来应用选播，优化网络服务。通常这种方式以选播组管理协议为基础，对服务器进行一些关键性能参数的度量，例如：测试服务器的时间响应长短、判断服务器已有的连接数量、测量服务器的处理能力等。另一方面是在网络层来开展选播通信的研究，主要方式是在网络层构造合适的路由算法或者制定相关的路由协议来实现选播通信，例如：研究网络层路由算法中路由表的组成，用选播路由技术实现选播通信，可提高服务的可用性和均衡网络负载。选

6、播通信模式具有广泛的应用前景，正吸引着越来越多的科研技术人员进行研究。[2]1993年，C.Partridge等人在RFC1546中首次提出选播的概念，将选播用作服务器定位和主机自动配置的解决方案等，开创了选播通信研究的先河。1997年，BhattacharjeeSamrat[9]等人提出了一种在应用层上实现选播通信的方法，提出在应用层上利用选播解析服务器来解析从选播域名到一个或者多个IP地址的映射，给出了基于策略和基于度量两种方法[3]的过滤器来影响选择过程。1998年，R.Hinden等人在RFC2373中给出了选播通信的具体定义

7、，同时也定义了选播地址在IPv6中的具体结构形式，为选播服务在IPv6中的实施[4]应用奠定了基础。2000年，XuanDong和JiaWeijia等人提出了一种分布式选播路由协议，此协议包含两个子协议：路由表建立协议和数据包转发协议。根据路由器的有序性，路由表建立子协能够在路径选择过程中消除路由环路；为了避免网络出现堵塞的情况，在数据包转发子协议中提出了一种用于多路选择的加权随机方法。最后，实验结果说明他们提出的这种协议在性能上虽然和基于动态状态信息的网络路由算法相当，但其代价却大大地降低了。他们的研究工作取得了一定的成果，考虑了本

8、地接入记录、路由距离和可用带宽这三项QoS要求；但也存在着一定的局限性，比如未考虑不同的服务质量、准确性和[10]安全性，不能为用户提供有区分的服务质量。同年，ZeguraEllenW等人提出一种选播解析服务器架构，将选