现有网络拓扑图的生成方法研究与新思路

现有网络拓扑图的生成方法研究与新思路

摘要本文研究了现有的网络拓扑图的意义和功能，介绍了常用布局生成方法，然后引入相关的网络拓扑图生成方面的研究，可靠性、可视化技术、相关算法以及在无线网中的应用等；基于此，本文提出了一种新思路，以实现一种宏观性强且效果贡献明显的网络拓扑图生成方法，该网络拓扑图生成方法包括三个比较具体的步骤或方法：在通信网络中收集网络拓扑图信息、网络拓扑图生成、对网络拓扑图信息改变进行更新管理，通过上述三个部分有机结合产生了一套更加科学、高效及后期维护稳定的网络拓扑图的生成方法。关键词：网络拓扑图生成宏观性贡献明显收集网络拓扑拓扑更新管理引言在电信运营支撑系统中，所有电信设备的网络拓扑通常以图形的方式显示在网络拓扑图中。网络拓扑图一般分为物理拓扑图和逻辑拓扑图。在物理拓扑图中，根据设备节点的实际地理坐标，将每个设备节点绘制在地理地图上，从而客观地显示整个网络的实际空间分布。特别是每个设备节点的位置是设备节点的实际地理坐标。在逻辑拓扑图中，可以图形化地显示网络元件设备之间的逻辑关系、连接设备之间的逻辑关系和端口之间的拓扑关系。在逻辑拓扑图中，网络元件设备、连接设备和端口都称为节点。节点在逻辑拓扑图中的位置不取决于节点的实际物理坐标，而是取决于节点所在网络的拓扑结构和网络中节点的层次关系等信息。节点按照节点间的逻辑关系排列，使得整个网络拓扑图能够与网络的实际拓扑相匹配，使用户对整个网络的管理和维护更加方便。现有研究中，网络拓扑图的常用布局生成方法包括：分层布局生成方法、树形布局生成方法、总线布局生成方法、网格布局生成方法和嵌入式布局生成方法。例如，在分层布局生成方法中，根据预先确定的层次结构，将网络中的所有节点按一定的顺序分层排列，从而显示整个网络的层次关系。在树形布局生成方法中，网络中的所有节点按照树形层次结构从根到叶逐层排列，从而显示整个网络的层次关系。在总线布局生成方法中，网络中的所有节点相互连接，统一分布在总线的一侧，从而显示整个网络的连接关系。现有研究方法在一些研究中，对网络拓扑图的生成方法的研究都比较具体林丽美提出了拓扑图的可靠性及其在移动社会网络中的应用，并且分别分析了拓仆图的外连通度、条件诊断度、子图可靠度、移动社会网络的研巧热点的国内外研究现状和目前已有的研究工作中存在的问题[8]。赵龙厚提出了大规模网络拓扑可视化工具的研究并介绍了一种灵感源于原子核外电子排布的拓扑点布局算法,先采用网络拓扑大轮廓上进行分层,继而又根据子节点个数、所处层数,连邻节点的半径等多种因素细分不同轨道的方法以避免拓扑点过密、重叠,便于清晰显示,并基于此布局算法,开发了网络拓扑可视化系统[3]。刘永斌等人提出了LXI网络仪器拓扑图生成的设计与实现[7]。周安宇提出了网络拓扑图划分算法研究，通过构建具有内在调节机制的网络拓扑图划分的求解模式，规范网络拓扑图划分算法的求解过程，从根本机制上切实保证划分质量。通过扩展图划分定义，打破传统的图划分只能最小化边切割，不能最大化边切割的观念，拓宽图划分的应用领域[2]。邹松,晏蒲柳,朱培红等人则研究了网络拓扑图的生成与Web技术的结合，其主要阐述了主动网络及主动网络管理概念，对主动网络管理的各个实现方案进行了详细的分析[4]。张慧君则在动态网络拓扑图自动布局研究中改进力导向ＦＲ布局算法，使其在增加减少节点时，利用布局结果，进行局部更新，以最小代价更加快速清晰重新布局并保持拓扑图的稳定性，并给本文提出了启示[1]。现今随着无线网络的发展，网络拓扑在无线应用越来越密切，在有关研究中张秀娟,禹继国提出了无线网络拓扑控制中支撑图构造算法，且具体提出了集中式算法为无线网络中支撑图的构造提供了很多思路，但无线网络本身就是一个分布式系统,所以分布式算法更适用于无线网络的观点[6]。苏涛,顾晶晶等人则提出了无线传感器网络分布式拓扑图生成模型，提出了ＭＥＮＳ－ＤＴＰＭ模型，该模型能减小拓扑图的扭曲程度。实验结果表明，相比于同类算法，ＭＥＮＳ－ＤＴＰＭ模型具有更好的效果[5]。生成方法研究的新思路现有的研究中虽然在具体领域上涉猎范围很广，但是个别研究比较具体，同时其效果或贡献也比较细微，很难在整个网络拓扑图的绘制或生成中有决定作用，并且上述研究基本都是遵循常见的拓扑图生成方法或思路。基于此，本文提出一种新思路，以实现一种宏观性强且效果贡献明显的网络拓扑图生成方法，该网络拓扑图生成方法包括三个比较具体的步骤或方法：在通信网络中收集网络拓扑图信息、网络拓扑图生成、对网络拓扑图信息改变进行更新管理。收集网络拓扑图信息的方法目的整体是保证网络拓扑图信息的完整性和科学性；网络拓扑图生成方法则是基于上述网络拓扑图信息生成网络拓扑图；对网络拓扑图信息改变进行更新管理则是主要考虑虚拟网络或网络的维护。通过上述三个部分有机结合产生了一套更加科学、高效及后期维护稳定的网络拓扑图的生成方法。在通信网络中收集网络拓扑图信息在通信网络中收集网络拓扑图信息实质是一种数学的处理方法，该方法包括：收集通信网络的网络拓扑图的详细信息，详细信息包括网络拓扑图的顶点元数据和边缘元数据的详细信息；在n维坐标系中嵌入网络拓扑图，具体取决于顶点元数据或者是边缘元数据，其中嵌入的网络拓扑图由n维坐标系中的一组点表示；处理嵌入式网络拓扑图信息；导出处理后的网络拓扑图信息。收集通信网络的网络拓扑图的详细信息收集通信网络的网络拓扑图详细信息的步骤包括：通过边界网关协议从网络设备、具体是路由器、监视设备获取网络拓扑图信息，路由分析解决方案或网络管理系统。计算描述网络拓扑图的网络拓扑图元数据，所述网络拓扑图元数据包括从由各个顶点表示的通信网络和从由各个边表示的通信网络的链路的度量派生的边缘元数据。从包含节点和链路的地理网络拓扑图计算出虚拟网络拓扑图，其中节点对应的顶点由顶点元数据描述，链路对应的边由顶点元数据描述。虚拟化网络拓扑图包含地理网络拓扑图的所有信息，并且以适合的通信角度描述网络的方式提供该信息。地理网络拓扑图和虚拟网络拓扑图都可以称为原始网络拓扑图，因为这两种表示是可交换的，它们提供的信息是相同的，只是表示方式不同。原始地理拓扑对应于现实中的网络拓扑图，包括节点（如发送方、发射站等）和链路（由有线或无线通信提供的通信路径）。原始虚拟拓扑图则主要对应于网络拓扑图中的数据，例如网络度量数据适合于评估通信网络的通信容量（例如带宽、数据速率等）。地理距离的信息作为一个数据值提供在顶点和/或边缘的元数据中。例如，边被描述为在一个顶点和另一个顶点之间提供的带宽，两个顶点之间的地理距离仍然存在于两个顶点之间的边的元数据中。将网络拓扑图嵌入到n维坐标系中将网络拓扑图嵌入到n维坐标系中的步骤包括：将嵌入函数应用于一个或多个顶点元数据或者是一个或多个边缘元数据;嵌入函数将一个或多个顶点元数据或者是边缘元数据的值转换为n维坐标系中的点的向量坐标;在嵌入之前每个点对应于网络拓扑图中的顶点，每个向量计算出网络拓扑图的顶点元数据或者是边缘元数据中的一个或多个的坐标。通过将原始的虚拟网络拓扑图嵌入到一个嵌入式网络拓扑图中，网络被表示为一组具有对应点的向量。这些点可以看作向量的端点。在这种情况下，矢量坐标是在正交坐标系中给出的（例如x值和y值；而不是长度和度数），矢量坐标和点坐标是相同的。用相应和等价的向量来描述点的原因可以看出，在数学运算中，向量尤其是用它们的长度和程度来描述可能更容易在计算机处理中处理，至少在某些计算中是这样。一般来说，嵌入式网络拓扑图中的点和嵌入式网络拓扑图中相应的向量可以看作是等价的。选择顶点元数据或者是边缘元数据的用户特定子集，并将嵌入函数应用于所选顶点元数据或者是边缘元数据子集，以计算矢量坐标。嵌入是可视化的，嵌入不仅能够可视化，而且能够在嵌入表示中使用几何关系（例如欧几里德范数、三角形不等式）而不是原始图形特征。例如，原始网络拓扑中的两个图顶点之间的距离可以被测量为嵌入网络拓扑图中两点位置之间的欧几里德距离。处理所述嵌入式网络拓扑图的网络拓扑图信息处理所述嵌入式网络拓扑图的网络拓扑图信息的步骤包括：使用所述嵌入式网络拓扑图的点的特性，选择所述嵌入式网络拓扑图的一个或多个点的特性，例如所收集的网络拓扑图信息的一个或多个顶点元数据或者是边缘元数据或者是策略信息的相对位置、距离、带宽、数据速率或者是属性。将嵌入式网络拓扑图的一个或多个点聚合成一个或多个簇，该簇包括嵌入式网络拓扑图的一个或多个点。通过将点合并为单个点来抽象所述嵌入式网络拓扑图。通过几何运算，具体是通过缩放、规范化、拉伸、平移，变换嵌入式网络拓扑图的一个或多个点的矢量坐标，移动、反射或者是旋转。在大的层面上重复地或者是以改变的顺序执行选择、提取或者是转换嵌入网络拓扑图信息的一个或多个步骤。导出所处理的网络拓扑图信息导出所处理的网络拓扑图信息的步骤包括：从所处理的网络拓扑图信息中创建网络地图，也就是从处理的网络拓扑图信息中创建网络映射信息。除了使用所处理的网络拓扑图信息边缘元数据之外，还可以使用顶点从嵌入式网络拓扑图衍生的元数据，属性值或者是从所收集的网络拓扑图信息衍生的成本值、度量。为了配合上述在通信网络中收集网络拓扑图信息的实现，在实际中需要提前配置相关的设备，至少需要配置一种适于收集通信网络的网络拓扑图的详细信息的数据处理组件。通常我们会配置用于存储网络拓扑图详细信息的数据设备及处理设备。上述的信息包括网络拓扑图的顶点元数据和边缘元数据的详细信息，将被处理设备将通信网络的网络拓扑图嵌入到n维坐标系中。其中，数据处理组件执行时，嵌入式网络拓扑图由n维坐标系中的一组点表示，以处理嵌入式网络拓扑图的信息并导出经处理的网络拓扑图信息。网络拓扑图生成网络拓扑图生成框架的方法步骤有：采集并存储信息：采集用于生成图像的原始信息，将前面提到的用于生成图像的原始信息保存在提前配置的信息存储设备中；绘制首层图级：基于前面提到的用于生成图像的原始信息中的路径连接信息，使用客户所配置好的线交点配置网络拓扑图的首个图级，前面提到的首个图级位于网络拓扑图的第一个图级；绘制次层图级：与前面提到的首个图级相连的线交点为次个图级，次个图级在网络拓扑图中位于前面提到的首个图级的后一个层级；循环绘制全部层级：依靠往复循环遍历依次每个级别绘制，具体地，遍历当前所有的线交点数组，配置每一个线交点的横数学地图参考点和纵数学地图参考点，一直到绘制完成最终的网络拓扑图。网络拓扑图的绘制方法是水平分级绘制，同一层级的线交点具有不同的横数学地图参考点和相同的纵数学地图参考点，不同层级的层间距是相同，不同线交点的间距也是相同。基于以上原理，如何使用信息系统快速生成网络拓扑图？需要做好两点。首先，准备用于生成图像的原始信息。具体包括：线交点信息和路径连接信息；线交点信息包括网元专属身份标识号和物理的位置；路径连接信息包括总部专属身份标识号和接口、分部专属身份标识号和接口。其次，网络拓扑图生成也需要配置相关的网络拓扑图生成设备，相关的设备可以采用具体的硬件也可以采用软件，所以可以使用“设备”一词代为表示硬件主体或软件主体。生成设备的具体模块包括：采集信息模块，采集信息模块可以采集生成图像的原始信息，将前面提到的用于生成图像的原始信息保存在提前配置的信息存储设备中；配置首个图级模块，配置首个图级模块可以基于前面提到的用于生成图像的原始信息中的路径连接信息，根据客户配置好的线交点配置网络拓扑图的首个图级，前面提到的首个图级位于网络拓扑图的第一个图级；配置次个图级模块，配置次个图级模块可以与前面提到的首个图级相连的线交点为次个图级，在网络拓扑图中位于前面提到的首个图级的后一个层级；循环绘制模块，循环绘制模块可以依靠往复循环遍历依次每个级别绘制，直至绘制完成网络拓扑图。对网络拓扑图信息改变进行更新管理对网络拓扑图信息改变进行更新管理具体也可以通过开发一种软件来实现，该方法实质是先开发一种网络管理系统，用于监测和响应拓扑更改事件，通过对响应的处理在宏观上对网络拓扑图信息改变进行更新管理；响应的定义应包含：与拓扑更改事件对应的拓扑更改信息的报告消息基于拓扑信息生成确认查找消息以及确认拓扑更改事件基于对寻找确认信息的寻求消息受拓扑改变事件影响的网络元素/设备的环回地址、拓扑改变事件的类型、拓扑改变事件的状态以及指示网络拓扑图中的网络元素的位置的信息基于物理网络层面的拓扑更新对于基于物理网络层面的信息改变更新，在具体应用场景中，大致流程为根据跟踪到的改变消息，生成反映报告消息，包含拓扑更改信息的预确认数据记录，以及将预确认数据记录存储在预确认拓扑数据库中。在更新网络拓扑图数据集后，将预确认数据记录存储在确认后拓扑数据库中。确定与受拓扑改变事件影响的网络元素对应的确认后数据记录是否存储在确认后拓扑数据库中。根据确认后数据记录是否被确定存储在确认后数据库中，将确认前数据记录存储在确认前拓扑数据库中。在具体应用场景中，更新拓扑数据集包括当对确认寻求消息的响应指示拓扑更改事件已被确认时，将确认后数据记录存储在确认后数据库中。预确认数据记录是第二预确认数据记录，并且第二预确认数据记录存储在预确认数据库中，所述预确认数据库是在预确认拓扑中存储与受拓扑变化事件影响的网络元件对应的第一预确认数据记录数据库。本文所指出的跟踪对网络拓扑图的改变，包括可跟踪存储有机器可读指令的存储器和执行指令以执行操作的处理器。在具体应用场景中，这些操作包括响应与拓扑更改事件对应的拓扑更改信息的报告消息，生成验证查找消息以验证拓扑更改事件，以及基于对验证查找的响应更新表示网络拓扑图的拓扑数据集信息。具体操作还包括生成预验证拓扑记录、反映报告消息中包含的拓扑更改信息的预验证拓扑记录，以及将预验证拓扑记录存储在预验证拓扑数据库中。更新拓扑数据集的操作包括使用预验证拓扑记录创建验证后拓扑记录，以及基于对验证查找消息的响应将验证后拓扑记录存储在验证后拓扑数据库中。在进一步的具体操作中，验证查找消息包括受拓扑更改事件影响的网络元素的环回地址、标识拓扑更改事件类型的类型信息以及拓扑更改事件的状态。此外，具体操作还包括确定与受拓扑更改事件影响的网络设备对应的验证后拓扑记录是否存储在验证后拓扑数据库中。根据验证后数据记录是否确定存储在验证后数据库中，验证前拓扑记录存储在验证前拓扑数据库中。在进一步的具体操作中，更新拓扑数据集包括在验证后拓扑数据库中存储验证后拓扑记录，当对验证查找消息的响应指示已确认拓扑更改事件时。在实际操作中，需要配置对接网络设备的计算机，以可读介质存储计算机可读指令，当执行时，计算机可读指令响应于与网络设备改变相对应的报告消息，发送确认寻求消息以确认网络设备改变，以及基于对确认寻求消息的响应来更新网络配置数据集以反映网络设备的改变。在具体应用场景中，这些指令进一步使计算机基于报告消息确定受网络设备改变影响的网络设备，并将与该网络设备对应的预确认配置记录存储在预确认配置数据库中。预确认配置记录包括从报告消息获得的网络设备改变信息。进一步的具体指令使得计算机确定与网络设备改变相对应的确认后配置记录是否存储在确认后配置数据库中。基于软件定义网络层面的拓扑更新网络管理系统正日益成为维护网络健康和性能的重要工具，特别是随着网络规模和复杂性的不断扩大。通常网络管理系统会有一套监视工具用于监视网络流量并识别导致性能低下的问题（例如瓶颈、数据包丢失等）。当监控工具识别出性能问题时，网络管理工具依赖于配置/拓扑信息来理解现有的网络拓扑图结构，然后根据需要重新路由网络流量和/或重新配置网络。因此，此类监视工具通常包括收集有关哪些网络元素/设备耦合到网络的信息并使用该信息填充配置数据库的机制。这些工具还可以收集关于网络元件/设备如何相对彼此定位的信息，以便可以根据需要重新路由网络通信以保持网络性能。为确保重新路由流量或重新配置网络的计划有效，配置数据库应尽可能保持最新。然而，因为网络不断发展和扩大的规模和复杂性以不断增长的速度，及时收集网络拓扑图/配置信息是一个越来越困难的挑战。此外，软件定义的网络的易用性和可重新配置的速度进一步提高了及时收集网络配置信息的机制的需求。与传统网络中的重新配置操作通常涉及物理接口/元件的安装和/或移除不同，在软件定义的网络中，可以在几分钟甚至几秒钟内添加甚至移除数百甚至数千个接口。所以，在软件定义网络层面，本文提供了使用基于两阶段提交的事件驱动的网络拓扑图/配置信息收集方法来解决其中的一些问题。该方法是事件驱动的，每当软件定义的网络控制器进行网络配置更改（也称为拓扑更改事件和/或配置事件）时，软件定义网络控制器会向网络管理系统发送消息。网络管理系统能够在拓扑改变事件发生时监测到网络配置/拓扑的改变，而不是在以后网络管理人员向网络管理系统报告拓扑改变事件时意识到。在具体的应用场景中，软件定义网络控制器向网络管理系统报告一个挂起的拓扑更改事件，以指示特定的拓扑更改事件将在稍后的日期/时间发生。因此，与通常具有陈旧配置/拓扑信息的传统网络管理系统不同，本文描述的网络管理系统和方法能够实时监视网络配置和收集关于配置更改/拓扑更改事件的信息，并使用该信息创建和维护最新拓扑数据库。例如：在接收到报告消息（例如，报告拓扑改变事件已经发生和/或将发生的消息）时，这里描述的具体网络管理系统和方法发送确认寻求消息以确认拓扑改变事件已经发生。相对应的，软件定义网络控制器发送的报告消息指示正在添加、移除和/或修改网络元件/设备，并且进一步提供识别网络元件/设备和网络元件/设备的特性的信息。网络管理系统响应于拓扑变化事件报告消息而生成的确认寻求消息由网络管理系统发送到报告消息中标识的网络元件/设备。当接收到确认寻求消息时，网络元件/设备通过发送确认拓扑改变事件的确认消息来响应。如果网络管理系统没有接收到确认消息，则网络管理系统可以向软件定义网络控制器发送请求消息，请求关于拓扑改变事件的更新信息。因此，本文描述的网络管理系统基于从软件定义网络控制器接收报告消息的第一阶段和从受拓扑改变事件影响的网络元件/设备接收确认消息的第二阶段来收集关于网络拓扑图改变事件的信息。在第一阶段和第二阶段都完成之后（例如，已经报告并确认拓扑更改事件），拓扑更改事件被提交到由网络管理系统维护的配置/拓扑数据库。可以周期性地向网络元件/设备发送发现消息以识别自上次发送发现消息以来发生的任何拓扑更改事件，本文描述的网络管理系统和方法被配置为响应于软件定义网络控制器提供的实时拓扑改变事件信息来寻求拓扑改变事件的确认。结果，本文描述的网络管理系统和方法能够维护拓扑数据库