摘 要 本文分析了现有的以太网链路层拓扑发现算法，在此基础上提出了虚拟交换机拓扑发现改进算法，给出了算法的具体实现方法和实现。使得原有算法的应用范围更广，适应性更强。改进后的算法可以发现网络中原算法无法发现的设备。
1、引言
随着计算机性能的提高及通信量的巨增，传统局域网已经愈来愈超出了自身的负荷，交换式以太网技术应运而生，大大提高了局域网的性能。与过去基于网桥，集线器，路由器的共享媒体的局域网拓扑结构相比，网络交换机能显著的增加带宽。交换技术的加入，就可以建立地理位置相对分散的网络，使局域网交换机的每个端口可平行、安全、同时的互相传输信息，而且使局域网可以高度扩充。局域网交换机根据使用的网络技术可分为：以太网交换机、令牌环交换机、FDDI 交换机、ATM 交换机、快速以太网交换机。由于以太网的简单与易用性，所以目前大部分的LAN 均采用了以太网交换机与快速以太网交换机作为自己的网络交换设备。本文中的链路层拓扑发现正是针对以太网中的二层设备。
目前很多算法都是针对纯可管理得交换机网络设计的，但在实际应用中，经常会出现交换机网络中夹杂着HUB 或不可管理的哑交换机。这种类型设备的存在使网络拓扑发现算法的准确性大打折扣，我们把这类型的设备定义为虚拟交换机。因此提出一种对虚拟交换机的拓扑发现算法能使得原有算法的应用范围更广，适应性更强。
2、现有链路层拓扑发现算法
从交换机工作原理上我们能够发现，交换机并未提供一种有效、直接的方法确定其直接连接的设备。对于一个异构的网络我们唯一可行的方法就是利用SNMP 中的MIBⅡ bridge组的信息（各个厂家都实现），得到交换机的地址转发表，并分析其特性，利用提出得简单连接关系确定直接连接关系，来确定物理网路的拓扑关系。
2．1 现有算法描述
以给定的子网号和掩码地址作为输入，以交换机对象链表, 网段对象链表，主机对象链表，打印机对象链表和2 层连接对象链表为算法的输出。给定子网的拓扑信息全部包含在上述的链表中。
1）算法的第一部分首先根据子网地址和子网掩码计算出子网的范围，然后扫描该范围内的所有IP 地址，并判断设备的类型以及其它信息。该过程用伪代码表示如下：
for （子网范围内的每一个地址 ipAddr）
｛
if（存在某个设备的IP 地址为ipAddr）
｛
deviceType = getTypeofDevice（ipAddr）；
if （deviceType == switch）生成交换机对象，添加到交换机对象链表中；
else if （deviceType == printer）生成打印机对象，添加到打印机对象链表中；
else
生成主机对象，添加到主机对象链表中；
｝
｝
2) 找到子网内所有主机的MAC 地址。
3) 遍历子网中所有的交换机，下载交换机的FDB 表。
4）基于每个交换机的FDB 表，利用[4]所描述的方法计算交换机之间的连接关系。
5）重新调整子网内的所有网段。
6）把网段和交换机的连接关系构造成对象，添加到2 层连接对象链表中。
在算法的第（2）步，之所以要找到物理地址是因为交换机FDB 中的地址是MAC 地址，在为主机划分网段时，要用到这些MAC 地址。找到主机MAC 地址的方法有两种。第一种是利用主机的MIBII 中的inferfaces 组中的ifPhysAddress 对象，另一种是利用与该子网相连的路由器中的ipNetToMediaTable 来找到该子网内的所有主机的MAC 地址。
2．2 算法所存在的问题
算法的假设条件是整个网络都是可管理的交换机，即可以通过 SNMP 协议取得相应信息。并且所有交换机是连接在一棵树上，当网络中存在HUB 和哑交换机时，因为它们没有MIB 表或取不到MIB 信息，因此有许多设备就不能自动被发现，而只能通过手动方式添加。在中提到虚拟交换机的概念及简单的解决方法，但并没有给出具体的实现算法。
3、虚拟交换机拓扑发现算法描述
虚拟交换机拓扑发现算法主要目的就是要检测哪些交换机是直接连接到虚拟交换设备以及哪些交换机又是这些设备的下连设备。为了实现这个目标，根据中简单连接原理，能得到每个设备和它们所有的根设备之间的连接关系集合。如果某一根设备跟它的集合中所有设备都没有直接连接关系，则该设备下联唯一可能就是一个虚拟交换设备。这样就确定了虚拟交换机的位置，下来是要找出与虚拟交换设备直接连接的下级设备。如果某一个或多个设备是其它所有设备到虚拟交换机所连接的根设备都必须经过的节点（集合的交集），则这种设备一定是跟虚拟交换机直接连接的下级设备。
发现程序遍历网络中的每个交换机，下载交换机中的 FDB 表，然后构造两张表：间接连接表和直接连接表。其中，间接连接表是一张二维表，每个表项都是一个STruct，如下所示：
typedef struct _SimpleCONnectRecord{
SInterface *pSInterface;
struct _SimpleConnectRecord *portDown; //point to the next simple connect record
struct _SimpleConnectRecord *portRight; //point to the SInterface of switch simply connected
} SimpleConnectRecord
表的每一行以交换机的某一个接口 a 开始，在接口a 后面的同行的接口是以a 为根，与a 有简单连接关系的所有接口。表的第一列包含了整个表中出现的所有的接口，并且两两互不相同，可以作为表的索引。
第二张表是直接连接表，直接连接表是一张一维链表。链表中的每个元素是下面的结构体：
typedef struct _DirectConnectRecord{
SInterface *pSInterfaceSource;
SInterface *pSinterfaceDestin;
struct _DirectConnectRecord *pNext;
} DirectConnectRecord;
拓扑发现程序通过对间接连接表的计算得到直接连接表，最后在根据直接连接表生成链路层连接对象。存储在数据库中。
3．1 算法的实现
本算法采用 java 语言实现主要代码如下：
Vector portRight[]=new Vector[1024];
Vector portDown[]=new Vector[1024];
Vector counter[]=new Vector[1024];
int index=0;
public void getDirectConnected(String host){
createSimpleConnected（String host）;//利用Vector 构建一个可变大小的二维表
//对简单连接表进行识别得到直接连接关系
ListIterator it = portDown[index].listIterator();
int i = 0; //表示简单连接表的行元素个数
int n=0;
counter[index] = new Vector();
counter[index].addElement(new Integer(i));
while (it.hasNext()) {//遍历简单连接表
i = Integer.parseInt(counter[index].get(0).toString());
int portSize = ( (Vector) portDown[index].elementAt(i)).size();
String nextIP= ( (Vector) portDown[index].elementAt(i)).elementAt(0).toString();
if (portSize == 2) {//如果一个端口上仅仅连接一个设备，则与该设备是直接连接
┇
i++;
index++;
getDirectConnected(nextIP);//以该设备为根得到其下级设备的连接关系
index--;
break;
}
else if (portSize > 2) {//连接多个设备的话，则通过算法得到直接连接关系
┇
i++;
n++;
}
}
if (n == portSize) { //如果所有的简单连接设备的上连端口与其他设备之间均没有简单连接关系，则所有设备连接在
HUB 上
//判断哪些设备是与HUB 简单连接的设备
getHUBConnected()；
//遍历所有设备得到被各个设备包含的最大数
String tmp=getMax();
//包含数为最大的设备，该设备即是与HUB 直接连接的设备
index++;
getDirectConnected(nextIP);//以该设备为根得到其下级设备的连接关系
index--;
}
4、结束语
利用本文提出的虚拟交换机拓扑算法，在实际运行中能发现哑交换设备和共享设备，使原有的拓扑发现算法准确性更高，适应性更强。
