论文部分内容阅读
设计一个大型通信网络需要多种概算与评估。需要预测各种服务需求和维护规划的假定。由于供应商的频繁升级,配置设备站点的数量和位置以及设备的容量通常是不确定的。因此,与其在早期的设计阶段做详细的链路规划还不如根据不同的实际情况快速评估干线的损耗,用动态的方法把小型网络整合为更大的网络。随着计算机运算性能的提高,互连网络的性能也在不断改善。而计算机网络规模的越来越大,使网络互连问题变得日趋严重。这些问题促使分层网络拓扑的研究不断前进和深入。本文要研究的课题表现为一类可以运用在计算机网络、道路交通等拓扑结构上的优化设计问题。在分层拓扑网络算法设计中,假设建立一个有n个节点的网络,要求使用最优化设计使得所有节点互连节点所使用的消耗最小。同时网络应满足:网络直径限制最大值为d、节点度数限制最大值为△,以及单链路的失效网络必须仍然是连通的等。本文所做的主要工作有以下几个方面:(1)介绍了网络拓扑与图论的相关概念以及路由算法的基本原理,研究并分析了网络拓扑分层算法的实现思路和过程,讨论了网络节点的度,网络直径和可生存性等问题;(2)根据分层网络拓扑模型和算法,引入图论的相关知识和概念,在解决典型网络问题时把隐枚举法应用在网络拓扑最优设计中,给出了可以设计出满足约束条件的网络拓扑结构所使用的隐枚举法的一般舍弃测试方法,并给出解决通用问题的计算机算法程序,针对典型网络进行了仿真;(3)针对现有网络分层算法在空闲端口及主干网度计算上的不足,给出了网络拓扑结构分层的改进算法,并通过仿真实验证明了改进算法的可行性,讨论了直径为2的连通图的性质,并将其应用在本文的拓扑网络中,从而进一步改进了算法的递归方程;(4)最后针对分层网络拓扑结构及其算法设计,研究网络的扩展算法和路由算法,给出扩展算法的一般步骤,同时进行仿真。此外在网络的路由问题上提出一些研究思路和算法步骤。