2016, Vol. 27
2. 北京交通大学 计算机与信息技术学院, 北京 100080
2. School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100080, China
网络拓扑发现是指利用计算机软件自动识别网络元素之间的物理或逻辑连接关系,确定网络的拓扑结构.拓扑发现是配置管理的核心,是故障和性能管理的基础.至今,网络的自动拓扑发现仍是一个富有挑战性的研究项目.网络拓扑发现分为逻辑拓扑发现(网络层,3层)与物理拓扑发现(链路层,2层)两种:逻辑拓扑发现是指发现路由器间及路由器和各个子网间的连接关系,忽略子网内交换机与主机等设备的物理连接关系;物理拓扑发现是指发现管理域内交换机与主机及路由器等设备间的实际连接关系.
网络层的拓扑发现按发现的不同级别可以分为[1]IP接口级、路由器级、PoP级和AS级,发现方法主要有Ping方法、Traceroute方法、DNS方法、SNMP和ARP方法、路由协议方法和Tomography方法等.网络层拓扑发现技术的研究相对成熟,有很多项目和产品应用这些技术进行拓扑发现,比如惠普的Open View和IBM的Tivoli等.然而这些产品都依赖于私有协议,难以发现大型局域网中含有不同厂商交换设备的二层拓扑结构.许多网络管理任务,比如性能分析、网络规划和模拟、异常检测等都依赖于二层的拓扑发现.准确、实时的二层拓扑发现对于网络管理和应用具有重要意义.
基于地址转发表(address forwarding table,简称AFT)的物理拓扑发现是目前学术界研究的热点问题,也是物理拓扑发现的最重要方法.一套完备的拓扑计算规则对于通过不完整的AFT发现网络拓扑结构是至关重要的.我们在文献[2]中通过将AFT转换为谓词逻辑并提出了一套BRR规则,但当时并没能对BRR的完备性进行证明.拓扑计算规则的完备性证明对于基于AFT进行拓扑发现意义是非常重要的:首先,一套完备的拓扑计算规则可以用来指导和检验其他拓扑发现方法;其次,基于完备的计算规则所提出的拓扑发现方法才可能充分利用AFT表蕴含的网络拓扑信息,从而提高拓扑发现的效率和准确性.本文首先提出并定义了满足子网的最小约束的AFT,并将BRR修改完善为更加实用的BRR2;在此基础上,从理论上证明BRR和BRR2的完备性.此外,本文还进一步分析说明了文献[3]提出的满足分割限制的AFT在物理拓扑发现上的NP难问题,并深入讨论了任意网络不完整的AFT通过BRR2推导后的各种可能情况,以及目前AFT方法的局限性.本文的工作对于基于AFT进行物理拓扑发现具有重要的理论指导意义;同时,也为进一步发掘新的物理拓扑发现方法奠定了坚实的理论基础.
1 相关工作二层的拓扑之所以难以发现的主要原因是:
(1) 大部分的拓扑发现工具主要用于发现网络层拓扑,要求管理员手工维护二层连接信息,而且MIB中并不直接提供网络节点间的直接链接信息;
(2) 二层设备的地址转发表包含了可达信息,但信息通常不完整.
为了克服这些困难,IETF于2000年推出物理拓扑MIB[4],试图解决网络层以下拓扑结构的发现问题,但是由于没有确定如何获取这些MIB对象的机制而难以应用.为了改善这种状况,IEEE提出链路层发现协议(LLDP)作为802.1AB-205标准的一部分.LLDP是一个厂商无关的二层协议,它允许网络设备在本地子网中通告自己的设备标识和性能.简单说来,LLDP是一种邻近发现协议,它为以太网网络设备,如交换机、路由器和无线局域网接入点定义了一种标准的方法,使其可以向网络中其他节点公告自身的存在,并保存各个邻近设备的发现信息.但是,目前已部署的很多设备上并不支持这个协议.还有一种邻居发现协议CDP,而CDP是思科私有的协议,只能发现思科的二层设备.
除了可以应用邻居发现协议来直接发现二层设备的连接关系外,目前二层拓扑发现算法主要有基于生成树协议、基于地址转发表、基于端口流量特征及基于探测包的方法.
文献[5-7]将网络流量特征引入拓扑发现算法中,把网络设备接口的流量变化看作随机过程进行研究,尝试通过流量特征相近程度来推断网络的物理拓扑.但这些方法依赖于统计相关,只能大致推断出可能的链接,而且在不同子网间的设备互联时,这种方法的正确性还有待验证.
文献[8]中提出一种基于生成树协议的方法,其基本思想是利用生成树的信息构建网桥设备之间的连接关系.该方法的优点在于时间和空间消耗较小,可以发现局域网中的备用链路;缺点是许多交换机不支持生成树协议,适用范围受到一定的限制,并且该方法不能发现交换机和主机之间的连接关系.
文献[9]中提出一种基于探测包的方法,其基本思想是:在每个主机上设置一个代理进程,产生一些探测包,并把网卡设置在混杂模式下(在该工作模式下,网卡可以接收到所在网段内的所有数据包);然后,根据每个主机所接收的数据包来判断设备之间的连接关系.该种方法可以判断出交换机之间、交换机和主机之间的连接关系,缺点是在每个主机设备上都要设置一个代理进程,这对一个较大型网络来说是不太可能的事情.
总之,上述方法都具有较大的局限性.目前的二层拓扑发现的研究重点主要基于地址转发表,每台交换机都维护一张地址转发表.地址转发表的记录格式可以简单地表示为〈port,MAC〉信息对,其中,port称为转发端口,MAC称为转发地址.转发端口为p的转发条目构成一个子集,称为端口p的转发表.如果交换机端口p的地址转发表中包含了该端口所能接收到的所有数据帧的MAC地址,则称该端口的地址转发表是完整的.
贝尔实验室的Breitbart等人提出了基于完整地址转发表的物理拓扑发现方法[10, 11],可以发现跨子网交换域的拓扑结构.其算法的核心是直接连接定理:分属两个交换机的一对端口是相连的,当且仅当这两个端口的地址转发条目集合的交集为空,且其并集中包含了该子网中所有交换机的地址条目.该性质的前提条件是每个交换机上的地址转发信息都是完整无缺的.Bejerano等人[12]进一步提出一种基于不同完整地址转发表的多子网拓扑发现算法,该方法首先根据地址转发表和子网信息构造出不同节点之间的粗略路径,然后进一步为每一条路径构造出一组路径约束,利用路径约束信息,不断细化粗略路径,最终确定一条唯一的路径.他们证明了该方法的完备性,即如果地址转发表和子网信息可以唯一确定网络拓扑,则使用该方法就可以把这个网络拓扑结构发现出来.
基于完整地址转发表的方法存在一个难以克服的缺点,即需要保证地址转发表的完整性.为了做到这一点,Breitbart[10, 11]提出增加额外流量和连续采集两种方法来提高地址转发表的完整性.郑海等人[13]通过在管理站上Ping所有交换机的方法来保证下行端口的地址转发表的完整性.在实际网络中,由于地址转发表老化机制的存在,地址转发表长度的限制以及SNMP协议采用无连接的UDP进行通信,不能提供可靠的数据传输,因此,交换机地址转发表的完整性很难保证,从而影响这些算法的准确性.
郑海等人[13]提出了一种方法,该方法仅要求只要下行端口的地址转发表是完整的,就可以构造出交换机之间的连接关系.陈福等人[14]提出了一种新型的数据结构树型图,也仅要求下行端口的地址转发表完整即可构造出连接关系.Lowekamp等人[15]提出了一种更为宽松的基于非完整地址转发表的拓扑发现算法,算法要求一对交换机节点的AFT间至少共享3个转发条目.该算法把网络拓扑中的连接分为两种类型:直接连接和间接连接.该算法基于这样一个定理(间接连接定理):如果两个交换机仅有一对端口的通过集相交为空,则这对端口必然相连(间接连接).交换机S上端口x的通过集,是指该网桥上除去x以外的其他端口地址转发表的并集.但这3种方法一个致命的缺点是:只能适用于一个子网的拓扑发现,在交换域跨越多个子网时很容易出错.
文献[2]试图提出一个完备的规则,如果仅依赖地址转发表,两个交换机之间的端口连接是可以唯一确定的,则利用此规则,就可以唯一确定这两个端口.在此规则的基础上,文中提出了一种有效的算法推导出交换式以太网的物理拓扑关系,但文中并没有对规则的完备性作证明.Bejerano[16, 17]提出了一个很简单的方法来发现多子网局域网的拓扑结构,文中定义了一种Skeleton-Tree的数据结构,算法主要思想是:用Skeleton-Tree自顶向下构建每个子网的拓扑结构,然后子网间合并出整个交换域的拓扑结构.这个算法能发现大部分的网络拓扑情况,但这个算法要求下行端口AFT完整且上行端口AFT中含有根节点的地址.
Gobjuka等人在他们的工作[3, 18-21]中证明了AFT不完整时二层拓扑发现的NP难问题,并且给定AFT表是否能定义一个唯一的拓扑也是NP难问题.在给定AFT完整时,他们提出一种算法能发现所有可能的拓扑图并定义了拓扑唯一的条件.在给定AFT不完整时,他们提出了一组规则来扩展AFT并提出了3种算法满足不同情况需要:第1个是当所有节点的AFT中都含有同一个节点地址的情况,第2个是每个节点的AFT在半完全的情况,第3个是针对任意AFT情况但并不保证能发现.
在对相关工作的阐述中我们可以看到:由于不同厂商产品对LLDP的支持不同导致了二层拓扑的发现困难,现有的商用产品也不能很好地发现局域网的物理拓扑结构.AFT能提供一定的连接信息,但并不能提供设备的直接连接信息.如何利用AFT得出实际的拓扑结构,是二层拓扑发现的热点研究问题.但由于实际网络的AFT通常不完整导致了拓扑发现的困难,因此,一套完备的规则对于通过不完整的AFT发现网络拓扑结构是至关重要的.因为如果规则是完备的,不完整的AFT仅通过这组完备的规则就可以最大限度的扩展原有的AFT,从而最大限度地去发现可能的拓扑结构.
2 BRR完备性证明及应用 2.1 子网最小约束由于交换域内的交换机必须遵循生成树协议,其他链路只作为备用链路而不参与实际的数据传输,因此,参与数据交互的物理设备的拓扑结构是一个树型结构.树型结构中的任意链路为活动链路,活动链路连接的节点的端口称为活动端口.这样,可以将交换域建模为一棵无向树G=(D,E),D是交换域内所有节点(网络设备)的集合,E是设备端口之间的直接连接集合.若S表示所有交换机的集合,H表示所有主机和路由器的集合(二层拓扑发现可以将路由器作为主机处理),则D=S+H.每台交换机都维护一张地址转发表(address forwarding table,简称AFT),以Si表示交换域中第i台交换机,Sij表示Si的第j个接口,Aij表示端口Sij的地址转发表,如果Aij包含了Sij所能接收到的所有数据帧的MAC地址,则称Sij的地址转发表是完整的.在根交换机确定的情况下,我们称树型结构中交换机上连链路的端口为上行端口.显然,上行端口是唯一的.交换机其他的端口称为下行端口.
需要说明的是,当网络中含有HUB等哑设备(无法得到MIB的网络设备)时,此时,和不含哑设备的生成树不同的是:含哑设备生成树G的下行端口可能同时下连多个孩子,而不含哑设备的网络生成树G的下行端口只有一个孩子,因此,可以以网络节点下行端口的孩子数量情况来推断是否存在哑设备的连接.另外,网络中度数为2的哑设备是任何基于AFT的方法都无法发现的设备,这种设备通过其他物理拓扑发现方法也无法发现,而且在实际网络中,这种设备除了中继作用,没有其他功能,因此,我们假定后文中的网络不包含这类设备连接的情况.
如果一个交换域只包含一个子网,那么Aij就对应于网络中节点Si通过端口Sij在交换域生成树的路径中可能到达的节点集合.当AFT完整时,Aij含有了路径中所有节点的集合[10, 11].但这对于交换域含有多个子网的情况并不成立,因此,一个多子网的交换域内即使所有端口的AFT完整也并一定能确定唯一的拓扑结构[10, 11].如果我们假定网络中不含有度数为2的哑设备,这时,单子网交换域网络的AFT完整必定可以唯一确定这个网络的拓扑结构.因此,单子网交换域的生成树G有以下性质:
性质1. 单子网交换域网络的AFT完整时,这样的AFT必定可以唯一确定网络生成树G的拓扑结构.
证明:由于生成树G中任意一个节点Si的Aij完整,此时,Aij含有了端口Sij在交换域生成树的路径中所有可达节点的集合.这时,对于网络中的另外一个任意节点的端口Smn的地址转发表Amn与Aij只可能存在两种情况:
1) Amn≠Aij,两者不等时,则这两个端口的连接也必定不同,否则必然Amn=Aij;
2) Amn=Aij,即这两个端口的AFT完全相同,这时可以判定是存在一个哑设备连接这两个端口.
因此,无论对于哪种情况,都可以唯一确定网络生成树的拓扑结构.
性质2. 网络生成树G中节点的上行端口是唯一的.
这是树的基本性质.
除了性质2,树的其他性质也可以用于网络生成树G中,根据性质1,完整的AFT可以确定唯一正确的网络生成树的拓扑结构.因此对于单子网交换域,我们定义如下最小约束:
定义 1(单子网AFT最小约束). 如果网络节点的AFT可以确定唯一正确的网络生成树的拓扑结构,则称这样的AFT满足单子网的最小约束.
定义 2(叶交换机). 交换机的所有下行端口都连接的是非交换机设备,称这样的交换机为叶交换机.
定义 3(中间交换机). 定义所有的非叶交换机为中间交换机.
定义 4(叶端口). 定义交换机连接叶交换机的端口为叶端口.
定义 5(叶子). 定义所有终端设备(如主机和路由器)为叶子节点.
树中,叶交换机的下行端口可以连接主机、路由器等H设备.显然,中间交换机至少有两个端口连接其他交换机.另外,叶子节点在拓扑树中只有一条链路,中间节点至少有两个或两个以上的链路.
定理 1. 满足最小约束AFT的子网中任意节点的活动端口的AFT不能为空.
证明:这个定理是显而易见的.如果某个节点Si活动端口j的AFT为空,即Aij=∅,若Si的非活动端口k存在两种情况:一是和某条备用链路连接但不参加数据交换,二是不连接任何设备,无论是哪种情况,均有Aik=∅,这时,Si活动端口j和Si的非活动端口k无法区分,因此不可能得到正确的拓扑结构.
显然,完整的AFT是满足最小约束的,但满足最小约束的AFT并不一定是完整的,但满足最小约束的AFT和完整的AFT都可以唯一定义一个子网的拓扑结构.因此,总可以找到一些规则,使得满足最小约束的AFT经规则推导后成为完整的AFT.显然,最小约束和完整性的AFT是多对一的关系.从最小约束的定义可以知道,满足最小约束AFT是能通过AFT得到子网唯一正确拓扑结构的AFT不完整的最松约束.
从子网的最小约束定义我们知道:对于一个子网不完整的AFT,符合最小约束的AFT是确定子网唯一正确拓扑结构的最基本条件.如果给定子网的AFT不满足最小约束,那么通过这样的AFT无法得到唯一正确的子网拓扑结构.由于子网的拓扑结构可以确定子网唯一的完整的AFT,因此,符合子网最小约束的AFT总可以通过一组规则推导出这个子网的完整的AFT.本文试图确定一组完备的规则,符合子网最小约束的AFT可以通过这一组规则推导出这个子网的完整的AFT;反之,不符合子网最小约束的AFT通过这一组规则推导不出这个子网的完整的AFT.
2.2 基本推理规则我们在文献[2]中把AFT转换为等价的谓词公式集合,并在此基础上提出一组推导规则.若用AFT(A,p)表示交换机A端口p的AFT中的节点集合,用四元谓词Link(A,x,B,y)表示设备A的x端口和设备B的y端口间接连接,简记为AxBy,其中,A,B,x,y都是变元.根据AFT的含义,AFT就可以表示为一组谓词公式的集合,地址转发表和谓词公式集是等价的,因此,可以从谓词公式集出发推导设备之间的连接关系.如图 1所示(源于文献[2]).
|
Fig. 1 AFTs and formulas set 图 1 转发表和谓词公式集 |
基于谓词逻辑,文献[2]中提出一种称为连接推理技术CRT(connections reasoning technique)的谓词逻辑推理方法,推导任意两个节点之间的端口连接关系.下面是文献[2]提出的一组CRT方法的基本推理规则BRR (basic reasoning rule).
1) 对称律:Link(A,i,B,j)⇔Link(B,j,A,i):Port(A,i)和Port(B,j)相连当且仅当Port(B,j)和Port(A,i)相连.
2) 传递律Ⅰ:Link(A,i,C,u)∧Link(C,v,B,j)∧(u≠v)⇒Link(A,i,B,j).
3) 传递律ⅠI:Link(A,i,C,u)∧Link(C,v,B,j)⇒∃xLink(A,i,B,x)∨∃yLink(A,y,B,j).其中,u和v是未知数.
4) 互斥律:Link(A,i,B,j)⇒¬(∃x∃y(Link(A,x,B,y)∧(x≠i∨y≠j))).
5) 互斥律推论:Link(A,i,B,x)∧Link(A,y,B,j)⇒Link(A,i,B,j).
我们将上面5个BRR简单用谓词公式表示,并进一步修改完善(记为BBR2).
1) 对称律:AiBj⇔BjAi.
2) 传递律Ⅰ:AiCu∧CvBj∧(u≠v)⇒AiBj.
3) 传递律ⅠI:AiCu∧CuBj⇒AiBx∨AyBj.其中,x和y是端口变量.
4) 互斥律:AiBj⇒¬(AxBy∧(x≠i∨y≠j)).其中,x和y是端口变量.
5) 互斥律推论:AiBx∧AyBj⇒AiBj.其中,x和y是端口变量.
6) 传递律推论:AxCu∧CvBy∧AiBj∧(u≠v)⇒AiCu∧CvBj.其中,x和y是端口变量.
BRR2与文献[2]的传递律Ⅱ略有不同.文献[2]的传递律Ⅰ是传递律Ⅱ的特殊情况,且在证明传递律Ⅱ时列举了网络中可能出现拓扑结构的各种情况,比较复杂,也不严谨.我们在此严谨并简捷地证明修改后的传递律Ⅱ.
传递律Ⅱ证明:如图 2(a)所示(注:本文图中虚线连接表示可达链路或简单连接,实线表示直接连接),由于拓扑树中任意两个节点都是连通的,即节点A和B间必定连通,则必有AxBy.如果x≠i∧y≠j,由于AiCu∧CuBj,则节点A,B,C间必定存在环路,与拓扑树型结构矛盾;当x≠i∧y≠j不成立时,即AiBx∨AyBj,可能出现图 2(b)~图 2(d)这3种情况.
|
Fig. 2 Illustration of transmit law Ⅱ 图 2 传递律Ⅱ图示 |
另外,我们提出的BRR2增加了一个传递律的推论,传递律Ⅰ和传递律Ⅱ是通过第3个节点推断两个节点的连接情况,传递律推论是通过两个节点间的连接关系确定它们和第3个节点间的连接关系.下面我们证明此推论,并且后续对BRR2完备性的证明中会用到传递律推论.
传递律推论证明:如图 3所示,由传递律Ⅰ可以得到AxCu∧CvBy∧(u≠v)⇒AxBy,但由于AiBj,根据互斥律,因此图 3中x=i且v=j,即AiCu∧BjCv.
|
Fig. 3 Illustration of transmit law reference 图 3 传递律推论图示 |
一组规则是完备的,是指定义在公式集FS上的一组最基本规则,其他推理规则都可以由这些规则推导出来.换句话说:如果一个连接关系可以从公式集FS中推导出来,则仅使用这组规则就可以把这个连接关系推导出来.
我们在文献[2]中认为提出的BRR是完备的,但当时并没有能证明BRR的完备性.本文一个最大的贡献在于对于BRR2及BRR完备性的证明,当子网节点的AFT满足最小约束,即子网的AFT可以定义唯一的拓扑结构,也就是说,网络中任何两个节点间的连接关系可以从满足最小约束的AFT的公式集中推导出来,这时,如果证明满足最小约束的AFT的公式集通过BRR2总可以推导出子网完整的AFT(由于子网完整的AFT可以确定唯一正确的网络拓扑结构,也就是确定任意两个节点间的连接关系),那么就可以证明BRR2是完备的.其他任何新的规则无非是将AFT推导完整,如果BRR2可以完成任何满足最小约束的AFT完整性推导,那么其他规则一定可以通过这组BRR2推导出来.下面我们用数学归纳法证明BRR2的完备性,即当子网节点的AFT满足最小约束时,一定可以通过这组BRR2推导出子网完整的AFT.因此,我们有定理2.
定理 2. BRR和BRR2规则在网络节点端口AFT的关系推导中是完备的.
证明:
对于任意两个节点的网络拓扑树,如图 4(a)所示:如果满足最小约束,由定理1,任何一个活动链路端口的AFT不能为空,必然有AFT(A,i)={B},且AFT(B,j)={A},这时,AFT本身就是完整的,即两个节点满足最小约束的AFT是完整的.
|
Fig. 4 Network topology tree of two and three nodes 图 4 2个和3个节点网络拓扑树 |
对于3个节点,可能存在拓扑树的形状只有图 4(b)这一种情况.如果满足最小约束,由定理1,任何一个活动链路端口的AFT不能为空,必然有AFT(B,j)={A},AFT(B,u)={C},AFT(A,i)={B或C},AFT(C,v)={A或B},由于A和C的位置是对称的,只需证明以下3种情况:
1) AFT(B,j)={A}∧AFT(B,u)={C}∧AFT(A,i)={B}∧AFT(C,v)={B}⇒AFT(A,i)={B,C}∧AFT(C,v)={A,B};
2) AFT(B,j)={A}∧AFT(B,u)={C}∧AFT(A,i)={C}∧AFT(C,v)={A}⇒AFT(A,i)={B,C}∧AFT(C,v)={A,B};
3) AFT(B,j)={A}∧AFT(B,u)={C}∧AFT(A,i)={B}∧AFT(C,v)={A}⇒AFT(A,i)={B,C}∧AFT(C,v)={A,B}.
就可以由最小约束经过BRR2推导得到完整的AFT.
用谓词公式表示为(除i,j,u,v外,其他小写字母均为端口变量):
1) BjAx∧BuCy∧AiBz∧CvBk⇒AiCy∧CvAx,其中,AiBz和CvBk不需要推导,前提本身就含有;
2) BjAx∧BuCy∧AiCz∧CvAk⇒AiBm∧CvBn,其中,AiCz和CvAk不需要推导,前提本身就含有;
3) BjAx∧BuCy∧AiBz∧CvAk⇒AiCy∧CvBn,其中,AiBz和CvAk不需要推导,前提本身就含有.
下面我们就通过BRR2来进行推导(部分推导中对称律省略):
1) BjAx⇔AxBj(对称率):
¬ AxBj∧AiBz⇒AiBj(互斥律推论);
¬ AiBj∧BuCy∧(u≠j)⇒AiCy(传递律Ⅰ);
¬ CvBk∧BuCy⇔CvBk∧CyBu(对称率);
¬ CvBk∧CyBu⇒CvBu(互斥律);
¬ CvBu∧BjAx∧(u≠j)⇒CvAx(传递律Ⅰ).
即AiCy∧CvAx;
2) AiCz∧CvAk⇔AiCz∧AkCv(对称率);
¬ AiCz∧AkCv⇒AiCv(互斥律推论);
¬ AiCv∧BjAx∧BuCy∧(u≠j)⇒AiBj∧CvBu(传递律推论).
由于m,n为任意端口变量,即得到:AiBm∧CvBn
3) BjAx∧AiBz⇒AiBj(互斥律推论);
¬ AiBj∧BuCy∧(u≠j)⇒AiCy(传递律Ⅰ);
¬ AiCy∧CvAk⇒AiCv(互斥律推论);
¬ AiBj∧AiCv⇒BjCm∨CvBn(传递律Ⅱ);
¬ BuCy⇒¬(BjCm∧(j≠u∨m≠y))(互斥律);
因此必有:CvBn;
即AiCy∧CvBn.
这样,我们就证明了对于两个和3个节点的网络拓扑树,在AFT满足最小约束时,可以通过BRR2推导出完整的AFT.任何形态的拓扑树都可以这样生成,给定根节点,每次要么加入一个度数为1的叶子节点,要么加入一个度数为2的中间节点,叶子节点可以加入到任何节点上,中间节点的加入方式是只能加入到任意两个直接相连的节点链路间(否则会破坏树的节点度和链路树的关系,造成回路).
因此,对于任意网络的拓扑生成树,我们都用上述方法进行生成.对于这样生成的拓扑树,就可以利用数学归纳法进行证明.假设n个节点的网络生成拓扑树满足最小约束AFT,并且可以用BRR2推导出完整的AFT,当网络拓扑树中加入第n+1个节点时,可分为两种情况:第1种情况是加入的第n+1个节点是度数为1的叶子节点,第2种情况是加入的第n+1个节点是度数为2的中间节点.
1) 当加入的第n+1个节点是叶子节点时如图 4(c)中的节点C为新加入的叶子节点,A是C的父亲节点,B为拓扑树中任意一个其他节点,由于拓扑树是连通的,因此,树中任意节点B可以通过A到达C,即C到A间存在一条简单路径.由于n个节点时的 AFT是完整的,如果对于新加入的节点C,AFT(C,v)含有树中所有的节点,并且任意一个节点B的AFT(B,j)含有C即可使新的树中节点AFT完整.即需要证明树中任意一个节点B,使得CvBz∧BjCx即可.
由定理 1,任意一个活动端口的AFT不为空,因此,AuCx∧CvBy.
· 树中原有节点AFT完整,必存在ByAn∧(n≠u),则ByAn∧AuCx∧CvBy∧(n≠u)⇒CvAu (传递律推论);
· 又AFT完整,可得到AiBz,CvAu∧AiBz∧(u≠i)⇒CvBz(传递律Ⅰ);
· 又AFT完整,可得到AuBj,AiBz∧AuBj⇒AiBj(互斥律推论);
· BjAi∧AuCx∧(u≠i)⇒BjCx(传递律Ⅰ).
即得到CvBz∧BjCx(从上面的推导过程来看,这个结果显然可以通过AuCv推导得到).
2) 当加入的第n+1个节点是中间节点时如图 4(d)中的节点C为新加入的中间节点,A和D是C的直接连接节点,B和E为拓扑树中通过C两侧可达的任意一个其他节点.显然,两个方向具有对称性,只要以一个方向进行证明即可.我们以上侧进行证明,从上面1)的结论看,只要证明AuCv即可.
根据定理1,必然存在CvQy,其中,Q为原拓扑树中上侧任意一个节点;
a) 若上侧同时存在AuCx,则证明方法同1),不需要利用下侧节点的AFT就可以证明;
b) 若不存在AuCx,则必然存在AFT(C,v)含有A或者AFT(C,v)至少含有节点A的两个不同端口的可达地址,否则,图 4(d)中的节点A和C可以互换,就不满足AFT最小约束.即存在CvAy或者存在CvMp∧ CvNq∧ArMk∧AsNo∧(r≠s),p,q为端口变量.对于后者,可以通过BRR2推导出前者CvAy.首先,如果(p≠k∨ q≠o),根据传递律和互斥律容易得出环路,因此有CvMk∧CvNo∧ArMk∧AsNo∧(r≠s).因为CvMk∧ArMk⇒ CvAy∨CxAr,CvNo∧AsNo⇒CvAy∨CxAs;又(r≠s),所以有CvAy.这两种情况都可以归结为CvAy.这时,要利用下侧节点的AFT进行推导.下侧节点对于这种情况同样存在两种可能:
¬ 一种是存在a)的情况,这时有Cv′Du′;同时,在插入节点C之前AFT是完整的,容易得出Du′Au,因此有AyCv∧Cv′Du∧Du′Au∧(v≠v′)⇒AuCv(传递律推论);
¬ 另一种是存在b)的情况,这时有Cv′Dz,因此有AyCv∧Cv′Dz∧Du′Au∧(v≠v′)⇒AuCv∧Cv′Du′(传递律推论).
因此,我们证明了当加入第n+1个节点时,只要节点仍满足最小约束AFT,仍然可以用BRR2推导出完整的AFT.这样,我们就可以得出BRR2是完备的结论.BRR2是文献[2]中BRR的变体,可以由BRR推导出.因此,我们在文献[2]中提出的BRR也是完备的.
2.3 BRR2 讨论我们通过定义满足最小约束子网的AFT,并在此基础上证明了BRR的完备性.因此,对于一个子网的AFT,如果满足最小约束,则一定可以通过BRR2推导出完整的AFT.对于不满足最小约束子网的不完整的AFT,仍然可以利用BRR2进行推导,以得到最大化的节点连接关系.但推导最终形成的AFT并不能唯一确定正确的拓扑结构.
Gobjuka等人在他们的工作[3]中证明了AFT不完整时二层拓扑发现的NP难问题,给定AFT表是否能定义一个唯一的拓扑也是NP难问题.因此,Gobjuka等人在文献[3]中提出:要么文献[2]提出的BRR是不完备的;要么即使BRR是完备的,但通过BRR推导出完整的AFT也需要指数级的时间复杂度.但Gobjuka等人在文献[3]中对拓扑发现的NP难证明对AFT是有一定的前提限制的,即网络节点的AFT满足如下分割限制:网络N中有两个节点a和b,网络N中的任意节点c可以看到(表示AFT中含有相应节点地址)a或b或两者都可以看到.但是在网络N中,既不能所有节点都看到a,也不能所有节点都看到b.
满足分割限制的不完整的AFT进行拓扑发现时是NP难的,这就是AFT不完整时二层拓扑发现的NP难问题.因此,并不是任何AFT不完整时进行拓扑发现都是NP难的.例如,当网络中所有节点可以看到同一节点时,作者在文献[3]中提出一个算法,可以以O(n2)的算法复杂度发现满足这样条件的拓扑结构.另外,很容易找到许多满足最小约束的AFT,但并不满足分割限制,即网络N中有两个节点a和b,分割限制要求网络N中任意节点c必须看到a或b的任意一个,但网络N中的任意节点c可能既看不到a又看不到b.如图 5所示,网络中不存在任何两个节点中的其中一个都可以被网络中的任意一个节点都看到,即网络中的AFT不满足分割限制.但这样非常不完整的AFT却满足最小约束,很容易通过BBR2推导出完整的AFT(推导过程略,读者可以自行推导).因此我们认为,Gobjuka等人在文献[3]中的观点“要么BRR是不完备的;要么即使BRR是完备的,但通过BRR推导出完整的AFT也需要指数级的时间复杂度”是不准确的.因此我们认为:满足分割限制的AFT并不一定满足最小约束,不满足分割限制的AFT应该满足最小约束,通过BRR扩展可以得出完整的AFT;满足最小约束的AFT可以满足分割限制,也可以不满足分割限制.我们认为,正确的观点应该是:对于AFT满足分割限制并且不满足最小约束时,这时通过BRR推导出正确的拓扑结构是NP难的.原因是,不满足最小约束的AFT本身就无法确定正确的拓扑结构.
|
Fig. 5 AFT satisfying minimal restraint but not satisfying separation restriction and the corresponding topology 图 5 不满足分割限制但满足最小约束的AFT及其拓扑结构 |
为了进一步验证BRR的完备性,我们采用NS2网络仿真软件对不同规模的网络进行仿真.网络拓扑采用树型结构,根据节点数量交换机的端口数目(12个)、每个交换机下连接的交换机数目(5个)和主机数目(7个)等参数自动生成.网络流量随机产生,其连接时长平均为5s,按照指数On/OFF分布(EXPOO_Traffic)产生数据.仿真时间长度为10分钟.具体的仿真数据见表 1.
|
Table 1 Inferring test of AFT meeting minimal constraint 表 1 满足最小约束的AFT推导验证 |
第1种情况是实际采集的AFT不完整但满足最小约束时,来实验分析BRR是否能将采集的不完整的AFT扩展为完整地AFT.具体实验时,我们选择地址转发表老化时间为300s,这时,地址转发表条目采集率很低,比如在2 000个节点的网络中,采集率仅为15.9%,但是这些地址转发表都可以满足最小约束的限制.由表 1的BRR推导结果可以看到,这种情况下,BRR可以推导出完整的AFT,即可以正确地推导出网络拓扑结构.
除了对BRR的完备性进行验证外,我们对BRR的推导时间进行实验验证.从表 1可以看出,虽然节点数量增加1倍,推导时间分别增加5倍(节点数量为500~1 000)和3.5倍(节点数量为1 000~2 000),不是一个线性增加的过程,但是需要注意的是:虽然节点增加了1倍,需要推导的转发表条目(丢失条目)却增加了不止1倍,分别为4.9倍和4.5倍,转发表推导时间和和推导出转发表条目数量接近线性关系.上述仿真结果也证实了在地址转发表满足于AFT满足最小约束的情况下,文献[3]认为推导完整的AFT需要指数级的时间复杂度的观点是不准确的.另外,对于一个节点数量多达2 000个节点的网络,在14s内完成推导过程.这个速度是非常快的,因此,BRR算法在时间上是完全可以满足网络管理系统对网络拓扑发现的需求.
第2种情况是实际采集的AFT不完整但同时不满足最小约束时,具体实验时,当地址转发表老化时间为120s时,地址转发表条目采集率进一步降低.比如在2 000个节点的网络中,采集率仅为8.8%,但是这些地址转发表不满足最小约束的限制.从表 2中可以看到:经过BRR推导扩展并不能补齐所有的AFT表项,但是这种情况下的AFT仍然可以通过BRR进行最大限度的扩展.
|
|
Table 2 Inferring test of AFT not meeting minimal constraint 表 2 不满足最小约束的AFT推导验证 |
从表 2中还可以看到:当地址转发表不满足最小约束限制时,地址转发表条目的推导速度明显下降;并且随着网络规模和转发表条目丢失数量和丢失比例的增加,推导速度进一步下降.
我们在文献[2]中提出了一个以矩阵作为数据结构的基于BRR的连接推导算法,可以应用BRR来推导出完整的AFT,即补齐矩阵的所有为空的元素.BRR2可以用类似的连接推导算法,这里不再阐述.如果满足最小约束,必定可以通过BRR或BRR2把矩阵所有空的元素补齐,得到唯一正确的拓扑结构;若不满足,则无法通过规则补齐,这时无法确定唯一正确的拓扑结构.由于连接推导算法每次推导一对节点间的连接关系都需要借助剩余的其他节点进行规则推导,若n表示网络节点数,则每对节点进行一次推导的时间复杂度为O(n).由于节点对为O(n2),因此连接推导的时间复杂度至少是O(n3).
推导出完整的AFT后,可以用自顶向下[2]或自底向上[11, 13]的算法来确定网络拓扑节点间的直接连接关系.自顶向下的方法是先选定一个根节点,然后从上到下进行递归发现.自底向上的方法基于这样一个简单思想:如果一棵树所有的分叉及其连接的叶子被砍掉,而砍掉的分叉变成一个新叶子,这样树就可以一层层被砍光.即确定所有的叶交换机然后砍掉,把树中砍掉的叶交换机替换新的叶子,一层层砍到树根.具体算法这里不再描述,可参见相关文献.
2.4 多子网交换域应用文献[2]将BRR应用到了交互域中含有多个子网的情况,显然,BRR或BRR2是可以应用到多子网交换域进行AFT推导的,对多子网交换域的AFT的最小约束我们作以下定义.
定义 6(多子网最小约束). 如果多子网交换域中的AFT通过BRR或BRR2进行推导,可以得出完整的AFT,则称这样的AFT满足多子网的最小约束.
文献[10, 11]说明了对于多子网交换域的情况,即使网络中的AFT是完整的,也有可能得不出唯一的拓扑结构.因此,与单子网交换域网络不同,多子网交换域网络中的AFT即使满足最小约束,也不一定能推断出唯一正确的网络拓扑结构.下面我们用文献[10, 11]的例子进行说明.
如图 6(来自文献[8]),交换机S1和S4和路由器R1属于同一个子网,而交换机S2和路由器R2属于同一个子网,交换机S3和路由器R3属于一个子网,图 6(a)和图 6(b)两个子图所有交换机的AFT是相同的,而且都是完整的,但出现了两个不同的拓扑结构.即对于多子网交换域的网络,即使AFT完整,仅从AFT也不一定得出唯一的拓扑结构.
|
Fig. 6 Example indistinguishable network topologies 图 6 不可区分的网络拓扑示例 |
图 6中省略了交换机下连端口的AFT,即A12={R1},A23={R2},A33={R3}.如果图 6中的A21={S1},A31= {S1},这时,AFT不完整,但显然可以通过BBR2推导出完整的AFT.因此,这时的AFT是满足多子网最小约束的,虽然这样的最小约束并不能定义唯一正确的拓扑结构.
因此,对于任何一个网络不完整的AFT,通过BRR推导完成后形成的AFT可能出现3种情况.
1) 新的AFT可以得出唯一的拓扑结构;
2) 新的AFT得不到某个端口和其他端口的具体连接关系;
3) 新的AFT得到某个端口和多个端口可能具有连接关系.
· 如果是第1种情况,说明得出了完整的AFT,并且完整的AFT定义了唯一的拓扑结构;
· 如果是第2种情况,说明无论网络是单子网还是多子网,原始的AFT都不满足最小约束,推导不出完整的AFT,导致无法确定某些节点的连接关系;
· 如果是第3种情况,则有两种可能:一种是原始的AFT不满足最小约束所致,另一种是AFT本身无法定义多子网交换域的确定网络形态所致(即图 6所示的情况).
注意:实际网络中,可能出现情况2)和情况3)同时存在的情况.当情况2)或情况3)出现时,目前所有基于AFT的拓扑发现方法是无法确定正确的网络拓扑结构的.
3 总 结一套完备的规则对于通过不完整的AFT发现网络拓扑结构是至关重要的,我们在文献[2]中通过将AFT转换为谓词逻辑并提出了一套BRR规则,并认为这套BRR是完备的,但当时并没能对BRR的完备性进行证明.显然,无论是提出还是证明一套完备的规则,对于基于AFT进行物理拓扑发现意义都是非常重大的.本文通过定义满足子网的最小约束的AFT,将BRR修改完善为更加实用的BRR2,用数学归纳法证明了BRR2及BRR的完备性.
基于BRR的完备性,我们进一步讨论说明了文献[3]提出的满足分割限制的AFT在物理拓扑发现上的NP难问题,这样的NP难问题与完备的BRR是不冲突的.接着,我们定义了多子网交换域的最小约束,将BRR推广应用到多子网交换域网络,并且深入讨论了任意网络不完整的AFT通过BRR推导后的各种可能情况.本文的主要贡献是理论性的:一方面证明了BRR的完备性;另一方面深入讨论了AFT在物理拓扑发现上的NP难问题,并对BRR/BRR2的完备性和通过BBR进行AFT扩展的时间的非指数性进行了详细的实验验证.
由于实际网络中存在单纯依靠AFT无法唯一确定网络拓扑的情况,后续工作拟提出一种基于将BBR推导后的AFT和端口流量特征相结合的算法,以更好地解决实际网络中的拓扑发现问题.基本思路是:先通过BRR对AFT进行扩展,当存在仍无法确定的节点连接关系时,借助两个节点端口间的流量特征进一步确定直接连接关系.由于仅使用基于端口流量特征方法的最大缺点是对于两个端口仅能知道它们直接连接的概率大小,而并不能确定一定相连,但在AFT方法确定某个端口和另外一些端口中的某个肯定存在直接连接关系时,再使用基于端口流量特征的方法确定出概率最大的那个端口为直连端口,正好充分结合了两种方法的优势.
致谢 感谢刘艺博士详细和中肯的修改意见;感谢陈福博士关于物理拓扑发现方法的讨论;感谢总参第63研究所三室其他同事在本文写作过程中给予的无私支持和帮助.| [1] | Siamwalla R, Sharma R, Keshav S. Discovering internet topology. In: Proc. of the IEEE Infocom. 1999. 1-16. |
| [2] | Sun YT, Wu ZM, Shi JQ. A method of topology discovery for switched ethernet based on address forwarding tables. Ruan Jian Xue Bao/Journal of Software, 2006, 17 (12) :2565–2576(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/2565.htm |
| [3] | Gobjuka H, Breitbart Y. Ethernet topology discovery for networks with incomplete information. IEEE/ACM Trans. on Networking, 2010, 18 (4) :14–153. [doi:10.1109/TNET.2009.2039757] |
| [4] | Bierman A, Jones K. Physical Topology MIB. Internet RFC-2922, 2000 . |
| [5] | Dawes N, Schenkel D, Slavitch M. Method of determining the topology of a network of objects. U.S.Patent, 2002, 6,411,997 :B1. |
| [6] | Schenkel D, Slavitch M, Dawes N. Method of determining topology of a network of objects which compares the similarity of the traffic sequences/volumes of a pair of devices. U.S. Patent, 1999, 5,926 :462. |
| [7] | Qiu L, Zhang JZ, Wu GY. Physical topology discovery method study based on ports traffic. Computer Engineering and Application, 2002, 22 (4) :171–172(in Chinese with English abstract). |
| [8] | Son MH, Joo BS, Kim BC, Lee JY. Physical topology discovery for metro ethernet networks. ETRI Journal, 2005, 9 (4) :175–186. [doi:10.4218/etrij.05.0104.0167] |
| [9] | Black R, Donnelly A, Fournet C. Ethernet topology discovery without network assistance. In: La Porta T, Ramjee R, Koenig H, Effelsberg W, eds. Proc. of the 12th IEEE Int’l Conf. on Network Protocols (ICNP 2004). Los Alamitos: IEEE Computer Society, 2004. 130-159. [doi:10.1109/ICNP.2004.1348122] |
| [10] | Breitbart Y, Garofalakis M, Martin C, Rastogi R, Seshadri S, Silberschatz A. Topology discovery in heterogeneous IP networks. In: Sidi M, Sengupta B, eds. Proc. of the INFOCOM 2000. New York: IEEE Press, 2000 :85–94. [doi:10.1109/INFCOM.2000.832196] |
| [11] | Breitbart Y, Garofalakis M, Jai B, Martin C, Rastogi R, Silberschatz A. Topology discovery in heterogeneous IP networks: The NetInventory system. IEEE/ACM Trans. on Networking, 2004, 12 (3) :2221–234. [doi:10.1109/TNET.2004.828963] |
| [12] | Bejerano Y, Breitbart Y, Garofalakis M, Rastogi R. Physical topology discovery for large multi-subnet networks. In: Bauer F, Roberts J, Shroff N, eds. Proc. of the IEEE INFOCOM 2003. New York: IEEE Press, 2003. 162-172. [doi:10.1109/INFCOM.2003.1208686] |
| [13] | Zheng H, Zhang GQ. An algorithm for physical network topology discovery. Journal of Computer Research and Development, 2002, 39 (3) :264–268(in Chinese with English abstract). |
| [14] | Chen F, Yang JH, Yang Y. New algorithms on IP network topology discovery and its implement. Acta Electronica Sinica, 2008, 36 (8) :1620–1625(in Chinese with English abstract). |
| [15] | Lowekamp B, O’Hallaron DR, Gross TR. Topology discovery for large ethernet networks. In: Govindan R, ed. Proc. of the ACM SIGCOMM 2001. New York: ACM Press, 2001. 57-68. [doi:10.1145/964723.383078] |
| [16] | Bejerano Y. Taking the skeletons out of the closets: A simple and efficient topology discovery scheme for large multisubnet networks. In: Proc. of the IEEE INFOCOM. 2006. 1-13. [doi:10.1109/INFOCOM.2006.237] |
| [17] | Bejerano Y. Taking the skeletons out of the closets: A simple and efficient topology discovery scheme for large ethernet lans. IEEE/ACM Trans. on Networking, 2009, 17 (2) :205–1218. [doi:10.1109/TNET.2009.2022264] |
| [18] | Gobjuka H, Breitbart Y. Characterization of layer-2 unique topologies in multisubnet local networks. In: Proc. of the IEEE LCN. 2006. 540-542. [doi:10.1109/LCN.2006.322160] |
| [19] | Gobjuka H, Breitbart Y. Ethernet topology discovery for networks with incomplete information. In: Proc. of the IEEE ICCCN. 2007. 613-620. [doi:10.1109/ICCCN.2007.4317888] |
| [20] | Gobjuka H, Breitbart Y. Finding ethernet-type network topology is not easy. Technical Report, TR-KSU-CS-207-03, Kent State University, 2007 . |
| [21] | Gobjuka H, Breitbart Y. Discovering network topology of large multisubnet ethernet networks. In: Proc. of the IEEE LCN. 2007. 230-237. [doi:10.1109/LCN.2007.25] |
| [2] | 孙延涛, 吴志美, 石志强. 基于地址转发表的交换式以太网拓扑发现方法. 软件学报, 2006,17 (12) :2565–2576. http://www.jos.org.cn/1000-9825/17/2565.htm |
| [7] | 邱林, 张建忠, 吴功宜. 基于端口流量的物理网络拓扑发现方法研究. 计算机工程与应用, 2002,22 (4) :171–172. |
| [13] | 郑海, 张国清. 物理网络拓扑发现算法的研究. 计算机研究与发展, 2002,39 (3) :264–268. |
| [14] | 陈福, 杨家海, 杨扬. 网络拓扑发现新算法及其实现. 电子学报, 2008,36 (8) :1620–1625. |