随着计算机网络规模不断扩大,网络的异构性越来越高。目前异构网络的特点主要体现在以下三个方面:网络中包含多子网、网络中包含不同类型的设备或者网络中配置了VLAN。拓扑发现是利用拓扑工具寻找网络设备的互连关系的方法和技术。近年来拓扑发现被国内外的许多网络科研工作者所关注,成为计算机网络领域研究的热点问题。拓扑发现广泛应用于网络故障定位、性能测试和计费管理等方面。本文在深入分析国内外拓扑发现相关理论、技术和应用的基础上,提出了单子网物理拓扑发现算法,将单子网物理拓扑发现算法扩展到多子网中,并提出多子网物理拓扑发现算法。在研究单子网和多子网物理拓扑发现算法的基础上,提出了基于生成树协议的物理拓扑发现算法。该算法讨论了确定根网桥、根端口、指定网桥和指定端口的相关规则和定理,正确运用了STP、SNMP、ARP等协议,成功地确定了网络中路由器、交换机和主机之间的连接关系。该算法很好地解决网络中不同类型设备的物理拓扑发现问题。最后作者进一步提出了基于IEEE802.1QVLAN物理拓扑发现算法,并对此算法进行实现和验证。本文的创新之处主要体现在以下四个方面:在单子网物理拓扑发现算法中,增加了判断简单连接的条件,使算法更加完善;在多子网物理拓扑发现算法中采用图的广度优先遍历方法、端口删除方法等,该算法更加有效;在生成树协议物理拓扑发现算法中,正确使用STP、SNMP和ARP三种协议,物理拓扑发现非常准确;在VLAN物理拓扑发现算法中,正确运用了IEEE802.1Q协议,该算法具有通用性。