当前位置：搜档网 › 多生成树(MultipleSpanningTreeProtocol)

多生成树(MultipleSpanningTreeProtocol)

多生成树（Multiple Spanning Tree Protocol）

1、概述

1.1 产生背景

1.1.1 IEEE 80

2.1D STP

1.1.2 IEEE 80

2.1w RSTP

1.2 MSTP技术优点

2、MSTP详细介绍

2.1 相关术语

2.2 MSTP算法实现

2.2.1 初始状态

2.2.2 端口角色的选择原则

2.2.3 优先级向量计算

2.2.4 角色选择过程

2.2.5 计算结果

3、Comware实现的技术特色

3.1 MSTP的三种工作模式

3.2 Path Cost缺省值的计算

3.3 设置超时因子特性

3.4 指定根桥和备份根桥

3.5 BPDU保护

3.6 Root保护

3.7 Loop保护

3.8 TC保护

3.9 配置摘要侦听

3.10 No Agreement Check特性实现

3.11 MSTP标准报文格式特性实现

3.12 VLAN Ignore特性

4、典型组网案例

5、总结

1概述

1.1 产生背景

在二层交换网络中，一旦存在环路就会造成报文在环路不断循环和增生，产生广播风暴，从而占用所有的有效带宽，使网络变得不可用。

在这种环境下STP协议应运而生，STP是一种二层管理协议，它通过有选择性地阻塞网络冗余链路来达到消除网络二层环路的目的，同时具备链路的备份功能。

STP协议和其他协议一样，是随着网络的不断发展而不断更新换代的。最初被广泛应用的是IEEE 802.1D STP，随后以它为基础产生了IEEE 802.1w RSTP、IEEE 802.1s MSTP。

1.1.1 IEEE 80

2.1D STP

STP协议的基本思想十分简单。自然界中生长的树是不会出现环路的，如果网络也能够像一棵树一样生长就不会出现环路。于是，STP协议中定义了根桥（Root Bridge）、根端口（Root Port）、指定端口（Designated Port）、路径开销（Path Cost）等概念，目的就在于通过构造一棵树的方法达到裁剪冗余环路的目的，同时实现链路备份和路径最优化。用于构造这棵树的算法称为生成树算法（Spanning Tree Algorithm）。

要实现这些功能，网桥之间必须要进行一些信息的交互，这些信息交互单元就称为配置消息BPDU（Bridge Protocol Data Unit）。STP BPDU是一种二层报文，目的MAC是多播地址01-80-C2-00-00-00，所有支持STP 协议的网桥都会接收并处理收到的BPDU报文。该报文的数据区里携带了用于生成树计算的所有有用信息。STP的工作过程是：首先进行根桥的选举。选举的依据是网桥优先级和网桥MAC地址组合成的桥ID，桥ID 最小的网桥将成为网络中的根桥，它的所有端口都连接到下游桥，所以端口角色都成为指定端口。接下来，连接根桥的下游网桥将各自选择一条“最粗壮”的树枝作为到根桥的路径，相应端口的角色就成为根端口。循环这个过程到网络的边缘，指定端口和根端口确定之后一棵树就生成了。生成树经过一段时间（默认值是30秒左右）稳定之后，指定端口和根端口进入转发状态，其他端口进入阻塞状态。STP BPDU会定时从各个网桥的指定端口发出，以维护链路的状态。如果网络拓扑发生变化，生成树就会重新计算，端口状态也会随之改变。这就是生成树的基本原理。

随着应用的深入和网络技术的发展，STP的缺点在应用中也被暴露了出来。STP协议的缺陷主要表现在收敛速度上。

当拓扑发生变化，新的配置消息要经过一定的时延才能传播到整个网络，这个时延称为Forward Delay，协议默认值是15秒。在所有网桥收到这个变化的消息之前，若旧拓扑结构中处于转发的端口还没有发现自己应该在新的拓扑中停止转发，则可能存在临时环路。为了解决临时环路的问题，STP使用了一种定时器策略，即在端口从阻塞状态到转发状态中间加上一个只学习MAC地址但不参与转发的中间状态，两次状态切换的

时间长度都是Forward Delay，这样就可以保证在拓扑变化的时候不会产生临时环路。但是，这个看似良好的解决方案实际上带来的却是至少两倍Forward Delay的收敛时间！这在某些实时业务（如语音视频）中是不能接受的。

1.1.2 IEEE 80

2.1w RSTP

为了解决STP协议的收敛速度缺陷，2001年IEEE定义了基于IEEE 802.1w标准的快速生成树协议RSTP。RSTP协议在STP协议基础上做了三点重要改进，加快了收敛速度（最快可在1秒以）：

(1) 为根端口和指定端口设置了快速切换用的替换端口（Alternate Port）和备份端口（Backup Port）两种角色。当根端口失效的情况下，替换端口就会快速转换为新的根端口并无时延地进入转发状态；当指定端口失效的情况下，备份端口就会快速转换为新的指定端口并无时延地进入转发状态。

(2) 在只连接了两个交换端口的点对点链路中，指定端口只需与下游网桥进行一次握手就可以无时延地进入转发状态。如果是连接了三个以上网桥的共享链路，下游网桥是不会响应上游指定端口发出的握手请求的，只能等待两倍Forward Delay时间进入转发状态。

(3) 直接与终端相连而不与其他网桥相连的端口定义为边缘端口（Edge Port）。边缘端口可以直接进入转发状态，不需要任何延时。由于网桥无法知道端口是否是直接与终端相连，所以需要人工配置。

RSTP协议相对于STP协议的确有很多改进，并且向下兼容STP协议，可以混合组网。但是，RSTP和STP一样同属于单生成树SST（Single Spanning Tree），有它自身的诸多缺陷，主要表现在三个方面：

(1) 由于整个交换网络只有一棵生成树，在网络规模比较大的时候会导致较长的收敛时间。

(2) 因为RSTP是单生成树协议，所有VLAN共享一棵生成树，为了保证VLAN部可以正常通信，网络每个VLAN都必须沿着生成树的路径方向连续分布，否则将会出现有的VLAN由于部链路被阻塞而被分隔开，从而导致VLAN部无法通信的问题。

(3) 当某条链路被阻塞后将不承载任何流量，无法实现负载均衡，造成了带宽的极大浪费。这些缺陷都是单生成树无法克服的，于是支持VLAN的多生成树协议MSTP出现了。

1.2 MSTP技术优点

多生成树协议MSTP是IEEE 802.1s中定义的一种新型生成树协议，相对于STP和RSTP，优势非常明显。MSTP 的特点如下：

◆ MSTP引入“域”的概念，把一个交换网络划分成多个域。每个域形成多棵生成树，生成树之间彼此独立；在域间，MSTP利用CIST保证全网络拓扑结构的无环路存在。

◆ MSTP引入“实例（Instance）”的概念，将多个VLAN映射到一个实例中，以节

省通信开销和资源占用率。MSTP各个实例拓扑的计算是独立的（每个实例对应一棵单独的生成树），在这些实例上就可以实现VLAN数据的负载分担。

◆ MSTP可以实现类似RSTP的端口状态快速迁移机制。

◆ MSTP兼容STP和RSTP。

2 MSTP详细介绍

2.1 相关术语

在图1中的每台设备都运行MSTP。下面将结合图形解释MSTP的一些基本概念。

图1 MSTP基本概念示意图

(1) MST域

MST域是由交换网络中的多台设备以及它们之间的网段所构成。这些设备具有下列特点：都启动了MSTP；具有相同的域名；具有相同的VLAN到生成树实例映射配置；具有相同的MSTP修订级别配置；这些设备之间在物理上有链路连通。例如，图1中的区域A0就是一个MST域。

(2) VLAN映射表

VLAN映射表是MST域的一个属性，用来描述VLAN和生成树实例的映射关系。例如，图1中MST域A0的VLAN 映射表就是：VLAN 1映射到生成树实例1，VLAN 2映射到生成树实例2，其余VLAN映射到CIST。

(3) IST

IST是域实例0上的生成树。IST和CST共同构成整个交换网络的CIST。IST是CIST在MST域的片段。图1中，CIST在每个MST域都有一个片段，这个片段就是各个域的IST。

(4) CST

CST是连接交换网络所有MST域的单生成树。如果把每个MST域看作是一个“设备”，CST就是这些“设备”通过STP协议、RSTP协议计算生成的一棵生成树。图1中红色线条描绘的就是CST。

(5) CIST

CIST是连接一个交换网络所有设备的单生成树，由IST和CST共同构成。图1中，每个MST域的IST加上MST域间的CST就构成整个网络的CIST。

(6) MSTI

一个MST域可以通过MSTP生成多棵生成树，各棵生成树之间彼此独立。每棵生成树都称为一个MSTI。例如图1中，每个域可以存在多棵生成树，每棵生成树和相应的VLAN对应。这些生成树就被称为MSTI。

(7) 域边界端口

域边界端口是指位于MST域的边缘，用于连接不同MST域、MST域和运行STP的区域、MST域和运行RSTP 的区域的端口。

(8) 桥ID

由桥的优先级和MAC地址组成。

(9) 总根

总根是指CIST实例中桥ID最优的桥。

(10) 外部根路径开销

外部根路径开销指的是端口到总根的最短路径开销。

(11) 域根

MST域的IST和每个MSTI的根桥都是一个域根。MST域各棵生成树的拓扑不同，域根也可能不同。

(12) 部根路径开销

到域根的最短路径开销。

(13) 指定桥ID

由指定桥的优先级和MAC地址组成。

(14) 指定端口ID

由指定端口的优先级和端口号组成。

(15) 端口角色

在MSTP的计算过程中，端口角色有根端口、指定端口、Master端口、Alternate端口和Backup端口。端口在不同的生成树实例中可以担任不同的角色。端口角色示意如图2所示。

图2 端口角色示意图

◆根端口：负责向根桥方向转发数据的端口。

◆指定端口：负责向下游网段或设备转发数据的端口。

◆ Master端口：连接MST域到总根的端口，位于整个域到总根的最短路径上。

◆ Alternate端口：根端口和Master端口的备份端口。当根端口或Master端口被阻塞后，Alternate端口将成为新的根端口或Master端口。

◆ Backup端口：当开启了MSTP的同一台设备的两个端口互相连接时就存在一个环路，此时设备会阻塞端口ID较小的端口，此阻塞端口称为Backup端口，而另外一个端口则处于转发状态，成为指定端口。Backup端口是指定端口的备份端口，当指定端口被阻塞且无法发送协议报文后，Backup 端口的报文超时后就会快速转换为新的指定端口，并无时延的转发数据。

(16) 端口状态

MSTP中，根据端口是否学习MAC地址和是否转发用户流量，可将端口状态划分为以下三种：

◆ Forwarding状态：学习MAC地址，转发用户流量；

◆ Learning状态：学习MAC地址，不转发用户流量；

◆ Discarding状态：不学习MAC地址，不转发用户流量。

数据结构课程设计图的遍历和生成树求解

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 6014389 题目: 图的遍历和生成树求解实现年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日完成时间: 2012 年 12 月 26 日课程设计成绩：指导教师签名：年月日

目录摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26)

摘要《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：计算机；图；算法。

多生成树协议MSTP的配置

实验六：多生成树协议MSTP 的配置实验目的了解并掌握多生成树协议的配置背景描述某企业网络管理员认识到，传统的生成树协议(STP)是基于整个交换网络产生一个树形拓扑结构，所有的VLANs 都共享一个生成树，这种结构不能进行网络流量的负载均衡，使得有些交换设备比较繁忙，而另一些交换设备又很空闲，为了克服这个问题，他决定采用基于VLAN 的多生成树协议MSTP ，现要在交换机上做适当配置来完成这一任务。实验拓扑完整实验拓扑图实例1的生成树拓扑图实例2的生成树拓扑图 Switch1 Switch4 Switch3 Fa0/3 Fa0/4 Fa0/1 Fa0/2 BridgeAddr ： 00d0.f8b8.dc8e BridgeAddr ：00d0.f8bc.9b33 BridgeAddr ： 00d0.f8bc.9a8f Switch2 Switch4 Switch3 Fa0/4 Fa0/3 Fa0/2 Fa0/1 BridgeAddr ： 00d0.f8b8.1bf8 BridgeAddr ：00d0.f8bc.9b33 BridgeAddr ： 00d0.f8bc.9a8f Switch1 Switch2 Switch4 Switch3 Fa0/1 Fa0/2 Fa0/2 Fa0/1 Fa0/4 Fa0/3 Fa0/2 Fa0/2 Fa0/1 Fa0/3 Fa0/4 Fa0/1

实验步骤 1.交换机Switch1的一些相应配置 (1)创建Vlan10和Vlan20 Switch1(config)#vlan 10 Switch1(config-vlan)#exit Switch1(config)#vlan 20 Switch1(config-vlan)#exit (2)设置Trunk口和端口fa0/1与fa0/2的聚合 Switch1(config)#inter range fa 0/1-2 Switch1(config-if-range)#switchport mode trunk Switch1(config-if-range)#exit Switch1(config)#inter range fa 0/1-2 Switch1(config-if-range)#port-group 1 Switch1(config-if-range)#exit ！设置端口fa0/1-2为trunk并端口聚合 Switch1(config)#inter range fa 0/3-4 Switch1(config-if-range)#switchport mode trunk Switch1(config-if-range)#exit (3)开启生成树协议设为MSTP模式，并作相应设置 Switch1(config)#spanning-tree！开启生成树 Switch1(config)#spanning-tree mode mstp！配置生成树模式为MSTP Switch1(config)#spanning-tree mst configuration! 进入MSTP配置模式 Switch1(config-mst)#name taishan！配置域名称 Switch1(config-mst)#revision 1！配置版本（修订号） Switch1(config-mst)#instance 1 vlan 10！配置instance 1（实例1）并关联Vlan 10 Switch1(config-mst)#instance 2 vlan 20！配置instance 2（实例2）并关联Vlan 20 Switch1(config-mst)#exit Switch1(config)#spanning-tree mst 1 priority 8192 ！提升交换机Switch1在实例1上的优先级,缺省是32768，值越小越优先成为该instance 中的root switch,这一配置能确定Switch1为instance的根桥 Switch1(config)#end 【注意事项】 l 对规模很大的交换网络可以划分多个域（region），在每个域里可以创建多个instance（实例）； 2 划分在同一个域里的各台交换机须配置相同的域名（name）、相同的修订号（revision number）、相同的instance—vlan 对应表； 3 交换机可以支持65个MSTP instance，其中实例0是缺省实例，是强制存在的，其它实例可以创建和删除； 4 将整个spanning-tree恢复为缺省状态用命令spanning-tree reset 。 5 注意各个交换机的查看（验证）配置信息应该在所有的交换机配置完成后进行。

华为HCSE交换知识点

华为HCSE交换知识点 1. 以太网最初基于同轴电缆．1972年发明，1979年Xeroxinter和DEC提出DIX版. 2. 1983年，IEEE802.3标准提出. 3. CSMA/CD 通讯过程，传输—监听—干扰—随机等待—传输。 4. 传统以太网用网桥来分割主机，用路由器连接网段。 5. 交换式以太网，平时主机都不连通，当需要通信时，通过交换设备连接对端主机，完成后断开。交换设备包括，交换式集线器和交换机。 6. 交换式以太网物理逻辑均为星型。分割冲突域，将网络冲突限制到最小范围。 7. RMON共九组，常用的端口统计、历史、告警、事件4组。 8. 数据流量区分，按组织行政构成、按主机类型、按物理分布、根据应用类型。 9. 80／20规则，80％在本地，20％其他网段。20／80规则，相反。 10. 交换机单个百兆口64字节包转发1488810pps，路由器整机64字节包转发小与100100pps。 11. 三层交换技术的实现硬件的路由转发，转发路由表也是由软件通过路由协议建立的。 12. 三层交换与路由均为根据逻辑地址确定路径、运行三层校验和、使用TTL、对信息处理和相应，分析报文、用MIB更新SNMP管理。 13. 三层交换优点：基于硬件包转发、低时延、低花费。 14. 四层交换基于数据流，实现一次路由，多次交换。考虑端口号和协议字段。 15. 局域网设计原则，考察物理链路、分析数据流特征、采用层次化模型、考虑冗余。 16. 局域网管理系统功能：配置功能、监控功能、故障隔离。 17. 必须保证的网络性能，带宽和时延。其取决的一个重要因素，线缆的类型和布局。 18. 为用户增加带宽，增加总体带宽&减少在一个共享介质上的用户数量。 19. 快速以太网（100M）标准为802.3u。 20. 自协商使用物理芯片来完成，不需要专用的数据报文。发送16bi的报文，整个保文按16ms间隔重复。 21. 速率不通过自协商一样可完成，但工作方式会产生问题。一段强制10m全双工，另一端会自协商为10m半双工。 22. 自协商优先级：100BASE-TX全双工、100BASE-T4、100BASE-TX、10BASE-T全双工、 10BASE-T 23. 千兆以太网自协商已经实现，但光纤上的以太网自协商不能成功。 24. 交换机属于MDIX设备，PC为MDI设备。物理芯片实现。 25. 半双工采用后推压力（backpressure）技术实现，流量控制。

图的遍历和生成树求解实现_课程设计报告

中北大学数据结构课程设计说明书 2011年12月19日

1设计目的：《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 2设计内容和要求设计内容： (1)采用合适的存储结构来创建图，并实现图的遍历；（2）计算图的最小生成树，求联通分量设计要求：（1）先任意创建一个图；（2) 图的DFS,BFS的递归和非递归算法的实现（3) 最小生成树（两个算法）的实现，求连通分量的实现（4) 要求用邻接矩阵、邻接表、十字链表多种结构存储实现 3．本设计所采用的数据结构：本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。 4.1 详细设计思想这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和

详解生成树协议STP RSTP

详解生成树协议STP/RSTP 生成树协议是一种二层管理协议，它通过有选择性地阻塞网络冗余链路来达到消除网络二层环路的目的，同时具备链路的备份功能。生成树协议和其他协议一样，是随着网络的不断发展而不断更新换代的。“生成树协议”是一个广义的概念，并不是特指IEEE 802.1D中定义的STP协议，而是包括STP以及各种在STP基础上经过改进了的生成树协议。 STP/RSTP 在网络发展初期，透明网桥的运用。它比只会放大和广播信号的集线器聪明得多。它的学习能力是把发向它的数据帧的源MAC地址和端口号记录下来，下次碰到这个目的MAC地址的报文就只从记录中的端口号发送出去，除非目的MAC地址没有记录在案或者目的MAC地址本身就是多播地址才会向所有端口发送。通过透明网桥，不同的局域网之间可以实现互通，网络可操作的范围得以扩大，而且由于透明网桥具备MAC地址学习功能而不会像Hub那样造成网络报文冲撞泛滥。透明网桥也有它的缺陷，它的缺陷就在于它的透明传输。透明网桥并不能像路由器那样知道报文可以经过多少次转发，一旦网络存在环路就会造成报文在环路内不断循环和增生，出现广播风暴。为了解决这一问题，后来提出了生成树协议。 STP协议中定义了根桥（RootBridge）、根端口（RootPort）、指定端口（DesignatedPort）、路径开销（PathCost）等概念，目的就在于通过构造一棵自然树的方法达到裁剪冗余环路的目的，同时实现链路备份和路径最优化。用于构造这棵树的算法称为生成树算法SPA（Spanning TreeAlgorithm）。要实现这些功能，网桥之间必须要进行一些信息的交流，这些信息交流单元就称为配置消息BPDU（BridgeProtocol Data Unit）。STP BPDU是一种二层报文，目的MAC是多播地址01-80-C2-00-00-00，所有支持STP协议的网桥都会接收并处理收到的BPDU报文。该报文的数据区里携带了用于生成树计算的所有有用信息。生成树协议的工作过程：首先进行根桥的选举。选举的依据是网桥优先级和网桥MAC地址组合成的桥ID（Bridge ID），桥ID最小的网桥将成为网络中的根桥。在网桥优先级都一样（默认优先级是32768）的情况下，MAC地址最小的网桥成为根桥。接下来，确定根端口，根据与根桥连接路径开销最少的端口为根端口，路径开销等于‘1000’除于‘传输介质的速率’假设中SW1和跟桥之间

交换机知识生成树协议

交换机知识--生成树协议 STP（Spanning Tree Protocol，生成树协议）是根据IEEE 802.1D 标准建立的，用于在局域网中消除数据链路层物理环路的协议。运行该协议的设备通过彼此交互信息发现网络中的环路，并有选择的对某些端口进行阻塞，最终将环路网络结构修剪成无环路的树型网络结构，从而防止报文在环路网络中不断增生和无限循环，避免设备由于重复接收相同的报文所造成的报文处理能力下降的问题发生。 STP采用的协议报文是BPDU（Bridge Protocol Data Unit，桥协议数据单元），也称为配置消息，BPDU 中包含了足够的信息来保证设备完成生成树的计算过程。STP即是通过在设备之间传递BPDU来确定网络的拓扑结构。 BPDU格式及字段说明要实现生成树的功能，交换机之间传递BPDU报文实现信息交互，所有支持STP协议的交换机都会接收并处理收到的报文。该报文在数据区里携带了用于生成树计算的所有有用信息。标准生成树的BPDU帧格式及字段说明： Protocol identifier：协议标识 Version：协议版本 Message type：BPDU类型 Flag：标志位 Root ID：根桥ID，由两字节的优先级和6字节MAC地址构成 Root path cost：根路径开销 Bridge ID：桥ID，表示发送BPDU的桥的ID，由2字节优先级和6字节MAC地址构成 Port ID：端口ID，标识发出BPDU的端口 Message age：BPDU生存时间

Maximum age：当前BPDU的老化时间，即端口保存BPDU的最长时间 Hello time：根桥发送BPDU的周期 Forward delay：表示在拓扑改变后，交换机在发送数据包前维持在监听和学习状态的时间 STP的基本概念桥ID（Bridge Identifier）：桥ID是桥的优先级和其MAC地址的综合数值，其中桥优先级是一个可以设定的参数。桥ID越低，则桥的优先级越高，这样可以增加其成为根桥的可能性。根桥（Root Bridge）：具有最小桥ID的交换机是根桥。请将环路中所有交换机当中最好的一台设置为根桥交换机，以保证能够提供最好的网络性能和可靠性。指定桥（Designated Bridge）：在每个网段中，到根桥的路径开销最低的桥将成为指定桥，数据包将通过它转发到该网段。当所有的交换机具有相同的根路径开销时，具有最低的桥ID的交换机会被选为指定桥。根路径开销（Root Path Cost）：一台交换机的根路径开销是根端口的路径开销与数据包经过的所有交换机的根路径开销之和。根桥的根路径开销是零。桥优先级（Bridge Priority）：是一个用户可以设定的参数，数值范围从0到32768。设定的值越小，优先级越高。交换机的桥优先级越高，才越有可能成为根桥。根端口（Root Port）：非根桥的交换机上离根桥最近的端口，负责与根桥进行通信，这个端口到根桥的路径开销最低。当多个端口具有相同的到根桥的路径开销时，具有最高端口优先级的端口会成为根端口。指定端口（Designated Port）：指定桥上向本交换机转发数据的端口。端口优先级（Port Priority）：数值范围从0到255，值越小，端口的优先级就越高。端口的优先级越高，才越有可能成为根端口。路径开销（Path Cost）：STP协议用于选择链路的参考值。STP协议通过计算路径开销，选择较为“强壮”的链路，阻塞多余的链路，将网络修剪成无环路的树型网络结构。生成树基本概念的组网示意图如图所示。交换机A、B、C三者顺次相连，经STP计算过后，交换机A被选为根桥，端口2和端口6之间的线路被阻塞。桥：交换机A为整个网络的根桥；交换机B是交换机C的指定桥。端口：端口3和端口5分别为交换机B和交换机C的根端口；端口1和端口4分别为交换机A和交换机B 的指定端口；端口6为交换机C的阻塞端口。

华为实验指导书(更新)讲解

实验1 计算机和交换机基本配置 1.1组网及业务描述添加一台S3700交换机，两台PC。熟悉计算机、交换机命令。 1.2配置与验证 1、配置交换机双击交换机，进入终端配置： system-view ;进入系统视图 [Huawei]sysnam e SW1 ;交换机命名 [SW1]display current-config ;显示当前配置 [SW1]dis curr ;上一行命令的缩写 [SW1]display interface brief ;查看所有端口状态 [SW1]interface ethernet0/0/1 ;进入接口视图 [SW1-Ethernet0/0/1]undo negotiation auto ;配置端口工作在非自协商模式[SW1-Ethernet0/0/1]speed 100 ;配置端口工作速率为100M [SW1-Ethernet0/0/1]duplex full ;配置端口双工模式为全双工[SW1-Ethernet0/0/1]port link-type access ;配置本端口为Access端口[SW1-Ethernet0/0/1]quit [SW1]display interface e0/0/1 ;查看端口状态 [SW1]dis curr [SW1]interface ethernet0/0/1 [SW1-Ethernet0/0/1]shutdown ;关闭端口 [SW1-Ethernet0/0/1]undo shutdown ;激活端口 [SW1-Ethernet0/1]quit [SW1]vlan 10 ;创建/进入Vlan [SW1-vlan10]port ethernet0/0/1 ;将端口e0/0/1加入vlan10 [SW1-vlan10]port ethernet0/0/2 ;将端口e0/0/2加入vlan10 [SW1-vlan10]quit [SW1]dis vlan ;显示vlan配置 [SW1]quit save ;保存配置 2、配置PC 双击PCA，进入基础配置，将PCA的IP地址设为172.16.1.21，掩码为255.255.0.0同样，将PCB的IP地址设为172.16.1.22，掩码为255.255.0.0 双击PCA，进入命令行： PC>ipconfig ;显示IP地址 PC>ping 172.16.1.22 ;测试连通性

图习题及标准答案

————————————————————————————————作者：————————————————————————————————日期：

第7章图一、选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（） A） O(n) B） O(n+e) C） O(n*n) D） O(n*n*n) 【答案】B 2．设无向图的顶点个数为n，则该图最多有（）条边。 A）n-1 B）n(n-1)/2 C） n(n+1)/2 D）n2 【答案】B 3．连通分量指的是（） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图【答案】B 4．n个结点的完全有向图含有边的数目（） A）n*n B）n（n+1）C）n/2 D）n*（n-1）【答案】D 5．关键路径是（） A） AOE网中从源点到汇点的最长路径 B） AOE网中从源点到汇点的最短路径 C） AOV网中从源点到汇点的最长路径 D） AOV网中从源点到汇点的最短路径【答案】A 6．有向图中一个顶点的度是该顶点的（） A）入度 B）出度 C）入度与出度之和 D）（入度+出度）/2 【答案】C 7．有e条边的无向图，若用邻接表存储，表中有（）边结点。 A） e B） 2e C） e-1 D） 2(e-1)

【答案】B 8．实现图的广度优先搜索算法需使用的辅助数据结构为（） A）栈 B）队列 C）二叉树 D）树【答案】B 9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（） A）栈 B）队列 C）二叉树 D）树【答案】A 10．存储无向图的邻接矩阵一定是一个（） A）上三角矩阵 B）稀疏矩阵 C）对称矩阵 D）对角矩阵【答案】C 11．在一个有向图中所有顶点的入度之和等于出度之和的（）倍 A） 1/2 B）1 C） 2 D） 4 【答案】B 12．在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（）A） O(n) B） O(n+e) C） O(n2) D） O(n3) 【答案】B 13．下列关于AOE网的叙述中，不正确的是（） A）关键活动不按期完成就会影响整个工程的完成时间 B）任何一个关键活动提前完成，那么整个工程将会提前完成 C）所有的关键活动提前完成，那么整个工程将会提前完成 D）某些关键活动提前完成，那么整个工程将会提前完成【答案】B 14．具有10个顶点的无向图至少有多少条边才能保证连通（） A） 9 B）10 C） 11 D） 12 【答案】A 15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A） e B）2e C） n2-e D）n2-2e 【答案】D 16.对于一个具有n个顶点和e条边的无向图，如果采用邻接表来表示，则其表

数据结构课程设计-图的遍历和生成树的求解实现说明书

******************* 实践教学 ******************* 兰州理工大学计算机与通信学院 2012年春季学期算法与数据结构课程设计题目：图的遍历和生成树的求解实现专业班级：计算机科学与技术姓名：*** 学号：1234567 指导教师：**** 成绩：

目录摘要 (3) 前言 (4) 正文 (5) 1.问题描述： (5) 2.采用类C语言定义相关的数据类型 (5) 3．各模块流程图及伪码算法 (6) 4．函数的调用关系图 (8) 5．调试分析 (9) 1.调试中遇到的问题及对问题的解决方法 (9) 2.算法的时间复杂度和空间复杂度 (9) 6.测试结果 (10) 参考文献 (14)

图是一种复杂的非线性数据结构，一个图G（Grah）由两个集合V和E 构成，图存在两种遍历方式，深度优先遍历和广度优先遍历，广度优先遍历基本思路是假设从图中某顶点U出发，在访问了顶点U之后依次访问U的各个未访问的领接点，然后分别从这些领接点出发依次访问他们的领接点，并使先访问的顶点的领接点先于后访问的顶点被访问。直至所有领接点被访问到。深度优先的基本思路是从某个顶点出发，访问此顶点，然后依次从V的未被访问的领接点出发深度优先检索土。直至图中所有顶点都被访问到。PRIM算法—KRUSKAL算法；可以对图形进行最小生成树的求解。主要问题是：（1）当给出一个表达式时，如何创建图所表达的树，即相应的逻辑结构和存储结构？（2）表达式建立好以后，如何求出其遍历？深度优先和广度优先遍历。（3）计算它的最小生成树？主要是prim算法和kruscal算法两种形式。

MSTP是一个多生成树协议

MSTP是一个多生成树协议。MSTP的“多生成树”包括两层含义：一是在一个交换网络中可以基于VLAN划分出多个生成树实例（STI），二是在每个生成树实例中可以包括多个VLAN。而不是像Cisco的PVST、PVST+这样，虽然在整个交换网络中可以基于VLAN划分出多个生成树实例，但是每个生成树实例中仅包括一个VLAN。所以相对PVST、PVST+来说，MSTP更适用于比较大的网络中，划分生成树实例也更灵活，可以根据实际应用需要求来进行。虽然在整体来看，MSTP网络可分为以下层次（如图21-1所示）： ●MSTP网络 ●多生成树域MST Region（Multiple Spanning Tree Region） ●多生成树实例MSTI（Multiple Spanning Tree Instance）图21-1 MSTP的网络层次示意图而且这三者之间依次是包含关系，即MSTP网络包含MST域和MSTI，MST 域又包含MSTI，因为在一个MSTP网络中可以有多个MST域，一个MST域中又可以有多个MSTI。 1.MST域 MST域（Multiple Spanning Tree Regions，多生成树域）是由交换网络中的多台交换机以及它们之间的网段构成（在Cisco中是叫“MST区域”）。这

些交换机都启动了MSTP、具有相同的域名、相同的VLAN到生成树映射（是一个描述了VLAN和MSTI之间映射关系的映射表）配置和相同的MSTP修订级别配置，并且物理上有链路连通。一个局域网中可以存在多个MST域，各MST域之间在物理上直接或间接相连。用户可以通过MSTP配置命令把多台交换机划分在同一个MST域内。在如图21-1所示的MSTP网络中有三个MST域（MST域1、MST域2和MST 域3），域内所有交换机（图中每个生成树实例中的每个小圆圈代表一台交换机）都有相同的MST域配置。 2.MSTI MSTI（Multiple Spanning Tree Instance，多生成树实例）是指MST域内的生成树。一个MST域内可以通过MSTP生成多棵生成树，各棵生成树之间彼此独立。一个MSTI可以与一个或者多个VLAN对应，但一个VLAN只能与一个MSTI 对应。既然是生成树，那就不允许存在环路。在如图21-2所示的MSTP网络（由四台交换机相互串联形成）就形成了三个MSTI（图中的MSTI1、MSTI2、MSTI3，注意看他们的拓扑，总有一个方向的交换机连接是断开的），每个MSTI都没有环路。图21-2 MSTI划分示例

网络配置：锐捷、华为生成树配置

【实训目的】（1）理解生成树协议工作原理；（2）掌握快速生成树协议RSTP基本配置方法；（3）学会查看当网络出现故障时，交换机端口状态的变化及网络现象；【实训技术原理】生成树协议（spanning-tree），作用是在交换网络中提供冗余备份链路，并且解决交换网络中的环路问题；生成树协议是利用SPA算法，在存在交换环路的网络中生成一个没有环路的树形网络。运用该算法将交换网络冗余不备份链路逻辑上断开，当主链路出现故障时，能够自动的切换到备份链路，保证数据的正常转发；生成树协议版本：STP、RSTP(快速生成树)、MSTP（多生成树协议）快速生成树在生成树协议的基础上增加了两种端口角色：替换端口和备份端口，分别做为根端口和指定端口的冗余端口。当根端口或指定端口出现故障时，冗余端口不需要经过50秒的收敛时间，可以直接切换到替换端口或备份端口，从而实现RSTP协议小于1秒的快速收敛。【实现功能】使网络在有冗余链路的情况下避免环路的产生，避免广播风暴等。【实训背景描述】学校为了开展计算机教学和网络办公，建立了一个计算机教室和一个校办公区，这两处的计算机网络通过两台交换机互连组成内部校园网，为了提高网络的可靠性，作为网络管理员的你要用2条链路将交换机互连，现要求在交换机上做适当配置，使网络避免环路。【实训设备】 S2126G（2台），PC（2台）、直连线（4条）【实训内容】（1）根据拓扑将主机和交换机进行连接（未形成环路）（2）测试主机之间可以相互ping通（3）配置快速生成树协议（4）测试（形成环路）（5）测试（断开主要链路）【实训拓扑图】【实训步骤】（1）交换机1的基本配置（两台交换机只用一根网络通过F0/24端口相连） Switch# configure terminal Switch(config)# vlan 10

华为stp生成树协议笔记

STP 为什么会有stp 为了保证可靠，设计了一种环网拓扑，又因为交换机的工作原理，会出现环路问题，为了解决环路，才有了stp生成树 1 mac地址表震荡 2 广播风暴作用：在保证可靠的基础上，解决环路问题原理：阻塞端口（预备端口）通过选举阻塞端口，来防止环路 1 根桥（根交换机）： 1 比较每台交换机上的网桥id （优先级+mac地址）越小越优先默认优先级 32768 修改优先级修改的时候要改成4096的倍数交换机上有默认的stp版本为mstp （多实例生成树）stp （生成树）rstp (快速生成树) [系统]stp mode stp 修改stp的模式 Stp priority 4096 修改优先级 2 根端口：非根交换机到达根交换机的最优端口比较规则 1 路径开销值 2 对端网桥id 3 对端对口id 4 本端端口id （hub） 3 指定端口：每条链路上到达根交换机最优端口根交换机上所有端口都是指定端口比较规则 1 路径开销 2 本端网桥id

3 本端端口id （端口优先级和端口编号）端口优先级默认是128 4 剩下的端口就叫做阻塞端口 Stp中的报文交互 BPDU 桥协议数据单元两种bpdu 1 配置bpdu 作用：用于角色（端口）选举维护网络拓扑 2秒1次最多20秒20 秒没有根的回应，则认为根down掉 2 tcn bpdu 拓扑变化bpdu 作用：当拓扑发生变化时，会发tcn bpdu Bpdu 字段 1 bpdu flsges标识字段 Tca 位拓扑变化确认位 Tc 位拓扑变化位发生变化时置1 2 root identifier 根网桥id 3 root path cost 到达根的开销值 4 bridge id 本交换机的网桥id 5 port id 端口id 0x8001 前面的80 代表优先级128 ， 01代表端口号 6 message age 消息寿命每经过一台交换机message age +1 7 max age 最大寿命 20 秒 8 hello time 2秒 9 forward delay 转发延迟 15秒端口的状态变化 1 disable 开启stp时特点：不进行stp计算 2 blocking 阻塞端口直接进入blocking 状态 3 listening 非阻塞端口才进入侦听状态特点：加速mac地址表老化中间有15秒的间隔时间，目的是为了加速mac地址表老化，mac地址表老化时间300秒 4 learning 学习状态中间有相隔15秒的时间，加速mac地址表的学习 5 forwarding 转发状态

数据结构课程设计之图的遍历和生成树求解

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 2011.6.20 指导教师:

2010—2011年度第 2 学期一、需求分析 1.问题描述：图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。 2.基本功能 1) 先任意创建一个图； 2) 图的DFS,BFS的递归和非递归算法的实现 3) 最小生成树（两个算法）的实现，求连通分量的实现 4) 要求用邻接矩阵、邻接表等多种结构存储实现 3.输入输出

输入数据类型为整型和字符型，输出为整型和字符二、概要设计 1.设计思路： a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用∞表示。 b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。 c.图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。 d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。 e.图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。 2.数据结构设计： ADT Queue{ 数据对象：D={a i | a i ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| a i-1 ,a i ∈D,i=1,2,3,……，n} 基本操作： InitQueue(&Q) 操作结果：构造一个空队列Q。 QueueEmpty(Q) 初始条件：Q为非空队列。操作结果：若Q为空队列，则返回真，否则为假。 EnQueue(&Q,e) 初始条件：Q为非空队列。操作结果：插入元素e为Q的新的队尾元素。 DeQueue(&Q,e) 初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue