论文部分内容阅读
路由一直是计算机网络通信的关键理论和技术问题，尤其是目前Internet发展非常迅速，而且其节点数还正在呈指数级增长；网络传输正在向大容量、高速化、多媒体化方向发展，传统的路由算法已经不能满足日益增长的、对路由的各种QoS需求，因此必须研究新的具有QoS约束的路由算法。本文将多QoS约束路由算法作为研究课题，以小世界理论为基础，建立小世界网络模型，提出Internet静态网络模型和动态网络模型的新概念，获得分布式路由算法从一个源节点s到一个目标节点t消息传输期望步骤数的上限与下限；通过对随机图理论的研究，建立基于随机图的k-叉树网络模型，获得单播与组播平均跳数的函数关系式，得到分布式路由算法对于巨型、复杂网络来讲是高效的结论，建立了随机图仿真模型和方法，为研究多QoS约束路由算法奠定理论基础；设计和实现基于二值编码单亲GA的分布式QoS路由算法DQRGA，分析该算法的时间复杂度和空间复杂度，并与传统的源路由算法进行性能比较，结果证明该算法优于传统的集中式算法：在时间复杂度上优于N／[log2N]倍，在空间复杂度上优于（log2N）2，其中N为网络的节点数；设计与实现一种新的基于小世界和随机图理论的分布式路由算法DRBSR，分析和计算该算法的时间复杂度和空间复杂度，并与传统的路由算法进行性能比较，结果证明DRBSR算法优于传统的集中式算法；根据业务划分的不同，考虑到多QoS约束和网络资源利用率，设计和实现基于Dijkstra策略的QoS路由算法Fallback++，分析该算法的时间复杂度和空间复杂度，结果证明该算法优于Fallback+。多QoS约束组播路由一直是路由算法研究中的难点问题之一，不但由于该问题是一个NP完全问题，而且还因为QoS参数是不确定的，甚至是模糊的，传统的多QoS约束组播路由算法大多数属于精确算法，不能很好地反映网络的实际情况。本文提出基于模糊信息的综合QoS约束的组播路由新算法IQMRFI，首次将模糊集理论应用到路由算法中，定义各个QoS参数的隶属度和理想点，建立计算各个QoS参数到理想点的距离的模型和方法，将多目标规划简化为单目标规划，设计和实现了IQMRFI算法，分析该算法的时间复杂度和空间复杂度，分别为O（mn2）和O（5|E|），并进行了仿真，结果证明IQMRFI算法在路由选择成功率和运行时间上都优于传统的QoS组播路由算法。本内容属于网络基础理论的原始性创新研究，不仅在理论上具有重要的意义，而且对未来新的Internet路由协议的设计与实现具有重要的现实意义。