显示和分析多播分布的拓扑图算法

摘要

显示和分析多播分布的拓扑图算法，采用客户端/服务端架构，服务端分为通讯线程和服务线程。通讯线程负责接收客户端的邻居信息和多播地址信息并建立公共数据结构，该结构存放设备信息、端口相连的邻居信息、多播地址信息，并建立三者之间关联。服务线程负责绘制拓扑图和接收用户查询，用户可查看设备的多播地址并查询特定多播地址在网络中的分布。客户端进程和LLDP协议、GMRP协议、IGMP协议同步协作，将邻居信息和多播地址信息发给客户进程，客户进程处理后发给服务端。

说明书

技术领域

本发明为显示和分析多播分布的拓扑图算法，属于网络通信领域。该算法采用客户端/服务端架构，网络中一台PC机作为服务端，网络中的交换机或路由器作为客户端，客户端收集数据上报给服务端，服务端按照客户端上报的数据生成整个网络的拓扑图，同时反映网络中的多播分布情况。

背景技术

现在网络中多播应用非常广泛，多播和广播相比有明显的优势：一点发送，多点接收，接收方可以选择离开或加入该多播组。和广播不同的是，不加入多播组的设备，可以不受多播影响，减轻了这些设置处理负担。多播的广泛的应用带来的一个问题就是管理员需要了解当前网络的多播分布情况，比如一个特定多播地址在网络中流动的路径，该多播的源发起端在何处，它的最终的目的端在何处，中间通过何种设备。

发明内容

本发明提出的算法可以解决上述问题，它计算整个网络的拓扑图，同时在拓扑图上显示多播分布情况，帮助用户诊断网络。它直观、实时地显示网络中的多播路径，查看特定多播流所经过的设备，以及该多播流的发送端和接收端。本算法支持复杂的拓扑图生成，和多播路径结合起来，可以在生成的网络拓扑图上显示特定拓扑节点的多播流，同时实时展示特定的多播流流经的拓扑节点，方便管理员的监视和管理。

本算法采用客户端/服务端结构，选择网络中一台PC作为服务端，网络中交换机和路由器作为客户端，客户端和服务端之间采用UDP协议通讯。服务端的程序分成两个独立的线程，分别是通讯线程和服务线程。通讯线程负责和客户端通讯并接收客户端的上传信息，根据上传信息生成网络拓扑图，保存各种上传数据，建立各网络节点和多播地址的对应关系。服务线程主要用来展现拓扑图，展现各个节点上的多播表，同时提供查询入口供管理人员使用。两个线程使用公共的数据结构来存放拓扑图和多播表的数据。两个线程采用同步机制，通讯线程收到客户端的数据，建立维护公共数据结构，在操作完公共数据结构后则通知服务线程，服务线程接收到通知，读取公共的数据结构，按照公共数据结构存放的信息重新绘制拓扑图。通讯线程和服务线程的同步关系如图1所示。

公共数据结构包括三个部分：设备链表、多播地址表。设备链表包含设备节点。设备节点包括设备标示、设备IP地址、设备MAC地址，指向端口节点的指针、指向下一个设备节点的指针。端口节点包括：本端的端口编号、对端的端口编号，邻居设备指针、指向同一个设备的下一个端口节点的指针；多播地址表包括：多播地址节点，该节点包含多播地址的类型、多播MAC地址、多播IP地址、指向的多播设备节点的指针，指向下一个多播地址节点的指针。多播设备节点包括指向设备节点的指针、该多播地址使用的设备端口向量，指向下一个多播设备节点的指针。公共数据结构之间的关系如图2所示。

服务端和客户端采用UDP协议，客户端发现连接变化或IP/MAC多播流变化时，主动上传信息给服务端。网络稳定的情况下需要上传的数据很少，当网络产生变化时需要及时将变化信息发给服务端，服务端和客户端经常是短连接，传输的数据量不大，对时间要求较高，故采用UDP协议，同时相比TCP服务器采用UDP服务端可以支持更多的UDP客户端。服务端对客户端上传的报文进行确认，为此通讯双方定义两种数据格式：客户端上传的数据格式和服务端确认的数据格式。上传的数据格式包含：序列号、发送者IP地址、发送者MAC地址、命令类型、命令的正文部分。其中一个上传的UDP报文包含一个或者多个命令的类型和命令的正文部分，命令的类型决定了正文部分的内容，命令的类型及其正文有下面几种：

1.  命令类型0x01，含义是加入新的邻居；该命令的正文包括：发送者的IP地址，发送者的MAC地址，本端的端口编号，对端的端口编号，邻居的IP地址，邻居的MAC地址。

2.  命令类型0x11，含义是失去邻居连接；该命令的正文包括：发送者的IP地址，发送者的MAC地址，本端的端口编号，对端的端口编号，邻居的IP地址，邻居的MAC地址。

3.  命令类型0x02，含义是新加入多播地址；该命令正文包括：发送者的IP地址，发送者的MAC地址，多播地址的类型，多播IP地址，多播MAC地址，对应的端口向量。

4. 命令类型0x22，含义是多播地址离开；该命令正文包括：发送者的IP地址，发送者的MAC地址，多播地址的类型，多播IP地址，多播MAC地址，对应的端口向量。

首先服务端绑定双方约定的公共的UDP端口，等待客户端数据到达。服务端收到客户端的上传报文后，首先发出回应报文，回应报文内容包括上传报文的序列号，然后解析报文的内容，操作公共数据结构。服务端取出报文中发送方的IP和发送方的MAC地址，据此查询对应的设备链表。如果没有查询到对应的设备节点，则新建一个设备节点，然后查看命令的类型。

如果命令类型是0x01，用命令正文中发送者设备的IP和MAC在设备链表中找到对应的发送设备节点，如果可以找到对应的设备，按照命令正文中的本端的端口编号，查找设备节点指向的端口链表有无对应的本端的端口编号的端口节点，如果有对应的端口节点存在，则将端口节点的邻居设备针指向的设备节点与命令正文中邻居设备的IP和MAC进行比较。如果相等，则证明该邻居关系已经存在，结束处理；如果邻居设备不能匹配，则用命令正文中邻居设备的IP和MAC在设备链表中找到对应的设备节点，若找到对应的邻居设备节点，则修改端口节点的邻居设备指针指向新找到的设备节点，若没有找到邻居设备，则创建一个新的设备节点，插入到设备链表的末尾，然后端口节点的邻居设备指针指向该设备；如果没找到对应的发送设备的本端的端口编号，则创建一个端口节点，插入到设备节点端口链表的尾部，用命令正文中的邻居设备的IP和MAC在设备链表中找对应的设备节点，如果找到对应的邻居设备将新创建的端口节点的邻居设备指针指向找到的设备节点，如果没有找到邻居设备，创建一个新的设备节点，插入到设备链表的末尾，该端口节点的邻居设备指针指向该设备。

如果命令类型是0x11，用命令正文中发送者设备的IP和MAC在设备链表中找到对应的发送设备节点，如果没有对应的发送设备结束处理。如果有对应的发送设备，按照命令正文中的本端的端口编号，查找设备节点指向的端口表有无对应的端口，如果没有对应端口结束处理；如果有对应的端口节点，将端口节点的邻居设备指针指向的设备节点的IP和MAC与命令正文中的邻居设备的IP和MAC进行比较。如果比较相同，则把端口的设备指针设为空指针；如果比较不相同，则不作处理。

如果命令的类型是0x02，则代表有新的多播地址加入，首先查找多播地址表，如果找到多播地址节点，则查找多播地址指向的多播设备节点，如果多播设备节点的设备指针所指向的设备节点的IP和MAC和报文中的IP和MAC一样，则用用命令正文中端口向量填充该节点的端口向量，结束处理流程；如果没有找到对应的设备节点，创建一个新的设备节点，插入到设备链表的末尾，用命令正文中端口向量填充该节点的端口向量，多播设备节点的设备指针所指向新建立的设备。如果没有找到多播地址节点，则添加一个多播地址节点；然后查找该多播地址关联的设备节点是否存在，如果不存在则新建一个设备节点，该设备节点放到设备链表的末尾，然后按照报文中的端口向量创建一个或多个端口节点，新创建的设备链表节点的端口节点指针指向新创建的端口节点；新的多播地址节点的设备链表设备指针指向新建的设备节点，用命令正文中端口向量填充该节点的端口向量，设备指针指向创建的设备节点。如果找到多播地址节点，然后查找该多播地址关联的设备节点是否存在，如果不存在则新建一个设备链表节点，该设备链表节点放到设备链表的末尾，然后按照报文中的端口向量创建一个或多个端口节点，新创建的设备链表节点的端口节点指针指向新创建的端口节点；新的多播地址节点的设备链表设备指针指向新建的设备节点，用命令正文中端口向量填充该节点的端口向量，设备指针指向创建的设备节点。如果存在该设备节点，查看多播设备节点的端口向量是否相同，若果不相同则替换，相同则结束处理。如果多播地址节点存在的同时对应的设备也存在，则查看多播设备节点的端口向量是否相同，若果不相同则替换，相同则结束处理。

如果命令的类型是0x22，则代表有多播地址离开，首先查找多播地址表，如果找到多播地址节点，查找它指向的设备节点指针，然后比较设备指针指向的多播设备节点的设备的IP地址和MAC地址与报文发送方的IP地址和MAC地址是否相等。如果相等判断报文中的端口向量和多播设备节点中端口向量按位进行比较，如果对应的位两者都是1，则该多播设备对应的端口向量的该位置0；若多播设备指针指向的多播设备的ip地址和mac于报文中不相等，比较下一个多播设备节点指针指向的下一个多播设备节点。上述服务端接收命令的处理流程如图3所示。

如上所述，服务端的通讯线程负责建立并维护公共数据结构，如果通讯线程发现公共数据结构有任何更改，通知服务线程开始重新绘制拓扑图。服务端长时间运行，随着时间的推移，公共数据结构会有越来越多的垃圾数据，为此通讯线程打开定时器，定时收集清理公共数据结构中不需要的数据。具体的清理方法如下： 

首先清理孤立的设备节点，孤立的设备节点是没有任何邻居设备的节点。依次扫描设备链表，查看设备链表指向的端口链表指针是否是空指针，如果是空指针，表明该设备没有邻居，是一个孤立的设备，则删除该设备节点；如果端口链表指针非空，检查该设备的所有的端口节点的邻居设备指针是否都是空指针，如果都是空指针，则可以删除该设备的所有端口节点，然后删除该设备节点。其次清空无效的多播地址，无效的多播地址是指该多播地址不在任何设备上。清除的步骤是：扫描多播地址表，查看多播地址节点的多播设备节点指针是否为空指针，如果是空指针，删除该多播地址节点。

服务线程的功能之一是生成网络拓扑图，生成拓扑图的可以采用深度优先搜索算法和广度优先搜索的算法。本算法采用深度优先搜索，其具体步骤是：

A.  设置环网标志量为0表明没有出现环路，设备链表的每个节点设置为没有搜索完成标志；

B.  寻找一个没有搜索完成的设备，如果没有找到该设备退出整个步骤。如果找到该设备，把该设备的当前深度和最大深度置0，建立当前设备当前深度路径向量，当前深度路径向量，最深深度路径向量，同时把所有设备的所有端口设置为未被访问标志；

C.   建立一个栈，栈的元素包含节点的类型，设备节点，端口节点；如果类型等于0代表存放的是设备，端口节点清零代表没有意义；如果类型等于1存放的是端口，此时设备存放的是端口所在的设备节点，端口存放端口节点数据，代表当前设备节点入栈；把步骤B找到的未搜索完成设备节点入栈，设备节点存入当前深度路径向量，当前深度值1；

D. 判断栈是否为空，如果栈为空，最近出栈的设备节点设置为搜索已完成，转步骤B；如果不为空，取栈顶元素，如果栈顶元素是端口节点则转向步骤E；如果栈顶元素是设备节点，查找该设备未被访问过的端口节点并入栈，设置该端口为已访问标志，同时把端口节点指向的邻居设备的对应的端口设置为已访问标志；如果设备没有找到未被访问过的端口节点，则出栈，当前深度减1，当前路径深度向量移除该设备，转向步骤D；如果找到该端口，该端口入栈，设置该端口为已访问标志，同时把端口节点指向的邻居设备的对应的端口设置为已访问标志；如果该端口节点的邻居设备指针存在，查看指针所指的设备节点和路径向量中的节点是否相同，相同转步骤G，如果都不相同，则当前深度加1，邻居设备存入当前深度路径向量，然后跳转到邻居设备指针指向的设备节点，邻居设备入栈，同时移入当前深度路径向量；转步骤F；

E. 如果栈顶元素是端口节点，从该栈顶元素中得到端口所在的设备，查找该设备的未访问的端口节点，找到该端口入栈，设置该端口为已访问标志，同时把端口节点指向的邻居设备的对应的端口设置为已访问标志，端口节点所指邻居设备节点入栈，转向步骤D；未访问的端口节点不存在，出栈，转向步骤D；

F. 当前深度加1，当前深度大于最大深度时，用当前深度更新最大深度，同时当前深度路径向量复制到最大深度向量，转向步骤D； 

G. 如果相同，则证明出现环路，记录环路上的所有节点并保存，设置环网标志量为1表明出现环路，同时保存该环存在的节点数，放弃本次深度搜索，把环路中出现的所有节点，设置为已搜索完成标记，然后开始寻找下个深度优先搜索的根节点，该节点没有在记录的环路中出现过。转向步骤B；

重复上述所有步骤直到所有设备都设置了搜索完成标志，通过上述操作可以求出所有以该设备为根节点的最大深度。如果在求最大深度过程中没有发现在重复的节点，则网络结构是树形拓扑结构。求最大深度的算法流程如图4所示。

求出最大深度后，开始计算设备之间的距离，每个设备所占的面积，用正方形代表设备，设备之间的距离等于画布的总高度除以最大深度：假设该距离为D，代表设备的正方形的边长等于设备距离的八分之一，即边长a=D/8。每个设备有2个隐藏画布，一个画布记录设备的基本信息包括设备标示、IP地址、MAC地址，另一个画布记录设备的每个端口关联的多播地址。同时每2个设备的连线的两端有一个隐藏画图，记录所连设备的端口号。

网络拓扑图有两大类：树形拓扑结构、环形拓扑结构。按照深度优先搜索和广度优先搜索，在搜索路径中出现两个和多个同样的设备节点，则可以判断是环形拓扑结构，否则是树形拓扑结构，本算法求设备节点的最大深度过程中判断网络是环形还是树形拓扑，并采用不同的方法绘制拓扑图。

树形拓扑结构的绘制步骤为：检测环网标志量，如果为0，则代表是树形结构，检查每个设备节点的最大深度，如果深度相同则比较设备的mac地址，mac地址小的优先，把它们进行降序排列，找到排列第一个设备，把它置于画布的最上方的中央位置，然后遍历该设备的路径向量，当前扫描下标的设备指向排列的开始，从下标指向的排列的第1个设备开始，在设备的正下方的D距离，画出下一个设备，然后画线连接这两个设备。按此方法画出此设备的最大深度路径上的所有设备。当深度最深设备的最深路径的所有设备连线绘制完成以后，当前扫描下标加1，开始绘制扫描下标所指的设备最大深度的设备节点路径：首先判断该设备是否在以前绘制的图形中出现过，如果出现过则不用单独绘制，找出该节点，然后按照绘制第一条最深路径的方法进行绘制。每次绘制该节点之前，首先判断该节点是否已经存在，如果已经存在则不用绘制，直接用直线连接即可。如果该节点未出现过，水平偏移D距离，垂直偏移H（H=（最大深度-当前节点深度）×D），绘制该节点。另外为了图的总体保持平衡，轮流在最深的路径左右两边绘制路径和设备，每次绘制向下方偏离D距离，同时向左边或右边偏离D距离。按照此种方法直到队列中的所有设备都绘制完成。然后再次扫描设备链表，这次按照广度优先搜索，检查哪些设备连线没有绘制，如果没有绘制则用指向连上这两个设备。树形结构的绘制方法如图5所示。

环形拓扑图的绘制，检测环网标志量，如果为1，检查保存的所有的环网节点和环网中节点数数据，从中找出保存的节点数最多的那个环。如果几个环的节点数一样，则先检测的优先，把该环的节点数设置为深度H，绘制该环上的设备并连线，在画布的中央确定一点，以该点为圆心、画布的1/4宽度为半径，开始绘制圆周长上的设备。每次增加360/H度圆心角，绘制出环上的所有设备并直线连接。然后再依次以该环上的设备为源点，做广度搜索，首先查看它邻居设备在已绘制的图中是否出现，如果出现过并且他们之间没有连线，则直接画直线连接这两个设备；如果没有出现过，以环上的设备为圆心，画布的1/8宽度为半径，把它的未出现的邻居设备都绘制在画布上。每次绘制增加一个固定角度的圆心角，假设它为T=360/未出现过的邻居数，当把环上所有设备的邻居都绘制完以后，再按照同样的方式，以这些新加入的设备为圆心开始绘制，直到所有的边和设备都在画布上出现过。

按照上述的树形结构和环形结构的绘制方法，在绘制每个设备的同时，在隐藏图层的同样位置添加该设备的IP地址、MAC地址、描述信息、设备连线两边的端口信息。在所有设备及设备之间的连线绘制完成后，扫描多播地址表，将多播地址添加到多播地址关联设备的隐藏画布上，同时也添加该多播地址对应设备的端口向量。

服务端的服务线程负责用户接口部分，它具有显示并隐藏图层、查询设备信息、查询多播地址信息、查询多播路径等各种功能。用户查询特定设备的多播地址，只需要把设备隐藏的多播地址画布重新显示出来。用户要想查询特定的多播地址是否在当前网络中存在，首先需查询该地址是否存在于多播地址表中，如果在多播地址表中不存在，返回查询失败信息；如果存在，则查询多播地址指向的多播设备指针链表，然后在画布上把指针所指向的这些相关设备加亮显示，连线也加粗显示。藉此可以查看当前网络中的任何一个多播地址在网络中的分布情况。

客户端负责上传信息给服务端，客户端需要知道服务端的IP地址和端口号，一般端口号保持不变，但是有时网络管理员会更改服务端的IP设置，或者管理员把服务端从一台电脑迁移到另一台电脑，此时在常规情况下所有的客户端都需要重新配置。本发明提出以下的方案解决该问题：服务端运行过程中，周期性的对外广播自己的IP地址，客户端在刚开始运行中首先采用以前保存的IP来探测服务端是否正常，如果超时没有收到服务端的响应信息，开始接收服务端的广播信息，从接收的广播信息的内容中得到新的服务端的IP地址，然后用新的IP地址和服务端通讯，并保存该IP地址，到下次运行时使用该地址。

客户端需要上传邻居信息和多播地址信息，客户端进程和LLDP协议进程，GMRP协议进程，IGMP协议进程进行同步协作。同步协作的方式有管道、消息队列、共享内存、网络套接字等几种类型。在本算法中采用消息队列，这里消息类型和服务端处理的命令的类型是完全一样的，消息类型的编号和含义如下：

1. 消息类型0x01，发现新的邻居。

2.  消息类型0x02，以前的邻居失去联系。

3.  消息类型0x11，发现新的多播地址。

4. 消息类型0x12，多播地址离开一个端口。

客户端进程需要和LLDP协议进程协作得到邻居信息，两个进程之间采用消息队列进行数据传送和同步。LLDP协议发现一个新的邻居后，设置消息类型0x01，将发送者的IP地址、发送者的MAC地址、邻居的IP地址、MAC地址及对应的端口号等这些信息，通过消息队列发给客户端进程。客户端进程在消息队列中收到该信息后，组装成UDP报文发给服务端。LLDP协议发现邻居失去联系后，设置消息类型0x02，将发送者的IP地址、发送者的MAC地址、邻居的IP地址、MAC地址及对应的端口号这些信息，通过消息队列发给客户端进程，客户端进程在队列中收到该信息后，组装成UDP报文发给服务端。

客户端进程需要和GMRP协议或者IGMP协议进程协作得到多播地址信息，当GMRP协议或者IGMP协议进程收到加入报文注册多播地址时，设置消息类型0x11，将发送者的IP地址、发送者的MAC地址、多播地址类型、多播地址、对应的端口向量，写到消息队列中，当GMRP协议或者IGMP协议进程收到离开报文注销多播地址时或者多播地址超时被清楚时，设置消息类型0x12，把发送者的IP地址、发送者的MAC地址、多播地址类型、多播地址、对应的端口向量、写到消息队列中。客户端进程在队列中收到该信息后，组装成UDP报文发给服务端。服务端和客户端的进程间的协作关系如图5所示。

 附图说明

图1通讯线程和服务线程的同步关系

图2公共数据结构之间关系图

图3服务端处理命令的流程

图4以设备节点为根求最大深度的算法流程

图5树形结构的绘制方法

图6环形结构的绘制方法

图7服务端和客户端的进程间的协作关系

具体实施方式

首先选择一台高性能的服务器作为服务端，它具有并行处理大量网络数据的能力同时具有良好的人机界面，运行服务端进程。服务端的通讯线程周期性对外发布自己的IP地址，接收客户端的上传信息，建立公共数据结构。如果公共数据结构有变动，发信号通知服务线程刷新拓扑图。服务端周期性清理无效的设备、无效的设备邻居关系、当前无用的多播地址，在此过程中若发现数据结构被清除，则发信号通知服务线程刷新拓扑图。服务端的服务线程等待接收信号，收到信号后，扫描公共数据结构，生成新的拓扑图。服务线程在生成拓扑图后，根据公共数据结构中多播地址表信息，在隐藏图层上填充每个设备的多播地址信息，同时它接收用户的查询请求，收到查询请求后，查询公共数据机构和生成的拓扑图，然后打开隐藏图层的内容展现给用户。当用户查询特定设备的多播地址时，只需把该设备隐藏填充的多播地址信息画布显示出来。当用户查询特定多播地址的分布时，首先查询特定多播地址表中是否存在，如果在多播地址表中不存在，返回查询失败信息；如果该多播地址存在，查询多播地址指向的设备指针链表，然后在画布上把指针所指向的这些相关设备加点、加亮显示，连线也加粗显示。藉此可以查看当前网络中的任何一个多播地址在网络中的分布情况。

客户端包含支持LLDP协议，GMRP协议，IGMP协议的设备，一般情况包括智能交换机，路由器，智能电子设备。客户端需要修改LLDP协议，GMRP协议，IGMP协议，打开各自的消息队列，这些队列连接到客户端进程，需要将这些协议的源代码进行修改，在GMRP协议，IGMP协议发现需要注册和注销特定多播地址时，将这些信息都过消息队列发给客户进程进行处理。在LLDP协议发现新的邻居设备或者有邻居设备失去联系时，将这些信息都过消息队列发给客户进程进行处理。客户端进程在收到这些消息后，通过UDP报文发给服务端进行处理。

以上所述内容，只是本发明的一个具体的实例，并不仅用于限定本发明的保护范围。凡在本发明的原创范围以内的任何修改，等价替换，改进和任何参数调整，都应包含在本发明的保护范围之中。