实验八生成树配置——生成树协议
一、实验名称
生成树协议STP
二、实验目的
理解生成树协议STP的配置及原理。
三、实验步骤
1、在每台交换机上开启生成树协议．例如对SwitchA做如下配置：
SwitchA#configure terminal //进入全局配置模式
SwitchA(config)#spanning-tree //开启生成树协议
SwitchA(config)#end
验证测试：验证生成树协议已经开启
SwitchA#show spanning-tree //显示交换机生成树的状态
SwitchA#show spanning-tree interface fastthernet 0/1
//显示交换机接口fastthernet 0/1的状态
2、设置生成树模式
SwitchA(config)#spanning-tree mode stp //设置生成树模式为STP (802.1D) 验证测试：验证生成树协模式为802.1D
SwitchA#show spanning-tree
3、设置交换机的优先级
SwitchA(config)#spanning-tree priority 4096
//设置交换机SwitchA的优先级为4096
验证测试：验证交换机SwitchA的优先级
SwitchA#show spanning-tree
4、综合验证测试
1、验证交换机SwitchB的端口F0/1和F0/1的状态
SwitchB#show spanning-tree interface fastEthernet 0/1 //显示SwitchB的端口fastthernet 0/1的状态
SwitchB#show spanning-tree interface fastEthernet 0/2
//显示SwitchB的端口fastthernet 0/2的状态
2. 验证网络拓扑发生变化时，ping的丢包情况, 显示丢包数为30个。
实验二：快速生成树协议RSTP
设置生成树模式
SwitchA(config)#spanning-tree rstp ！设置生成树模式为802.1W
验证测试：验证生成树协模式为802.1W
设置交换机的优先级
SwitchA(config)#spanning-tree priority 8192 ！设置交换机SwithA的优先级为8192 验证测试：验证交换机SwithA的优先级
以下为从PC1 ping PC2的结果（注：PC1的IP地址为192.168.0.137，PC2的IP地址为192.168.0.136）
C:\>ping 192.168.0.136 –t ！从主机PC1 ping PC2（用连续ping），然后拔掉SwitchA 与SwitchB的端口F0/1之间的连线，观察丢包情况。显示结果如下：
以上结果显示丢包数为1个。
四、实验总结：
1．要注意查看端口状态时，PortState显示的结果在通的情况下是forwarding，表示处于转发的状态，否则在ping的时候ping不通。
2. 在拔掉一号端口线时，若未出现丢失包的情况，则要注意两台PC机的相应号线要连接
在相应的交换机上。
3. 在验证交换机SwitchB的端口状态时，要注意已经设定好的优先级4096，如果没有显
示，则说明配置未成功。
4. 在show spanning-tree时，有时候状态显示distabled，是不影响的。
编号：_______________本资料为word版本，可以直接编辑和打印，感谢您的下载 三层交换机生成树协议 甲方：___________________ 乙方：___________________ 日期：___________________
三层交换机生成树协议 篇一：网络工程技术生成树协议 1. 生成树stp的计算推导 (1) 手工计算推导出下图中的根交换机、根端口、指 定端口和阻塞端口 (假设每条链路带宽均为100mbps),最后 在packettracer6.0 模拟器上进行验证，通过抓包路径跟踪 的方法演示当主链路出现故障后的收敛过程和结果。 (2) 若使收敛时间更快速，可以采用哪种该进协议， 该方法的优势是什么？ 优势： a、stp没有明确区分端口状态与端口角色，收敛时主要 依赖于端口状态的切换。Rstp比较明确的区分了端口状态与端口角色，且其收敛时更多的是依赖于端口角色的切换。 b、stp端口状态的切换必须被动的等待时间的超时。而 Rstp 端口状态的切换却是一种主动的协商。 c、stp中的非根网桥只能被动的中继bpdu。而Rstp中的非根网桥对bpdu的中继具有一定的主动性。 1、为根端口和指定端口设置了快速切换用的替换端口(alternateport) 和备
份端口(backupport) 两种角色，在根 端口/指定端口失效的情况下，替换端口/备份端口就会无 时延地进入转发状态，而无需等待两倍的转发时延(Forwarddelay)时间。 2、在只连接了两个交换端口的点对点链路中，指定端口只需与下游网桥进行一次握手就可以无时延地进入转发 状态。如果是连接了三个以上网桥的共享链路，下游网桥是不会响应上游指定端口发出的握手请求的，只能等待两倍Forwarddelay 时间进入转发状态。 3、将直接与终端相连而不是与其他网桥相连的端口定义为边缘端口(edgeport)。边缘端口可以直接进入转发状态，不需要任何延时。由于网桥无法知道端口是否直接与终端相连，因此需要人工配置。 (3) 交换机端口的颜色灯和闪烁频率，分别代表哪些含义？若要求交换机的端口直接接用户的pc机而不参与stp 运算，应如何进行设置？ 颜色灯： 绿色灯表示可以发出 而黄色灯表示阻塞，不能发出闪烁频率：灯光闪烁说明有数据在传输，闪的快就说明比较频繁，也就是连续在端口上酉己置spanning-treeportfast 或
数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 2011—2012年度第 2 学期 一、需求分析
1.问题描述： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。 二、概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={
实验八生成树配置--生成树协议STP 1、实验名称 生成树协议STP。 2、实验目的 理解生成树协议STP的配置及原理。 3、背景描述 某学校为了开展计算机教学和网络办公，建立了一个计算机教室和一个校办公区，这两处的计算机网络通过两台交换机互连组成内部校园网，为了提高网络的可靠性，网络管理员用2条链路将交换机互连，现要在交换机上做适当配置，使网络避免环路。 本实验以2台S2126G交换机为例，2台交换机分别命名为SwitchA, SwitchB。PC1与PC2在同一个网段，假设IP地址分别为192.168.0.137，192.168.0.136，网络掩码为255.255.255.0 。 4、实现功能 使网络在有冗余链路的情况下避免环路的产生，避免广播风暴等。 5、实验拓扑 6、实验步骤 步骤1.在每台交换机上开启生成树协议并验证： SwitchA#configure terminal ！进入全局配置模式 SwitchA(config)#spanning-tree ！开启生成树协议 SwitchA(config)#end
SwitchAB#show spanning-tree interface fastthernet 0/1 ！显示交换机接口 PortState : forwarding ！显示接口fastthernet 0/1处于转发（forwarding ）状态
步骤2.设置生成树模式并验证测试。 SwitchB(config)#spanning-tree mode stp ！设置生成树模式为STP (802.1D) SwitchB#show spanning-tree 步骤3.设置交换机的优先级并验证测试。 SwitchA(config)#spanning-tree priority 4096 ！设置交换机SwitchA的优先级为 4096, 数值最小的交换机为根交换机（也称根桥），交换机SwitchB的优先级采用默认优先 级（32768），因此SwitchA将成为根交换机。
实验四、生成树协议 STP的应用实验 【相关知识】 1．生成树协议 STP简介 在局域网中，为了提高网络连接可靠性，经常提供冗余链路。所谓冗余链路就像公路、铁路一 样，条条道路通北京，这条不通走那条。例如在大型企业网中，多半在核心层配置备份交换机（网 桥），则与汇聚层交换机形成环路，这样做使得企业网具备了冗余链路的安全优势。但原先的交换机 并不知道如何处理环路，而是将转发的数据帧在环路里循环转发，使得网络中出现广播风暴，最终 导致网络瘫痪。 为了解决冗余链路引起的问题， IEEE802 通过了 IEEE 802.1d协议， 即生成树协议 （Spanning Tree Protocol，STP）。IEEE 802.1d协议通过在交换机上运行一套复杂的算法，使冗余端口置于“阻塞状 ，从而使网络中的计算机通信时只有一条链路生效，而当这个链路出现故障时，STP 将会重新计 态” 算出网络的最优链路，将“阻塞状态”的端口重新打开，从而确保网络连接的稳定可靠。 生成树协议和其它协议一样，是随着网络的不断发展而不断更新换代的。在生成树协议发展的 过程中，老的缺陷不断被克服，新的特性不断被开发出来。按照功能特点的改进情况，习惯上生成 树协议的发展过程被分为三代： 第一代生成树协议：STP/RSTP 第二代生成树协议：PVST/PVST+ 第三代生成树协议：MISTP/MSTP 2．IEEE 801.1D生成树协议简介 生成树协议（Spanning Tree Protocol，STP）最初是由美国数字设备公司（DEC）开发的，后经 IEEE 修改并最终制定了 IEEE 802.1d标准。 STP 协议的主要思想是当网络中存在备份链路时，只允许主链路激活，如果主链路失效，备份 链路才会被打开。大家知道，自然界中生长的树是不会出现环路的，如果网络也能够像树一样生长 就不会出现环路。STP 协议的本质就是利用图论中的生成树算法，对网络的物理结构不加改变，而 在逻辑上切断环路，封闭某个网桥，提取连通图，形成一个生成树，以解决环路所造成的严重后果。 为了理解生成树协议，必先了解以下概念： （1）桥协议数据单元（Bridge Protocol Data Unit，BPDU）：交换机通过交换 BPDU来获得建立 最佳树型拓扑结构所需的信息。生成树协议运行时， 交换机使用共同的组播地址 “01-80-C2-00-00-00”来发送 BPDU； （2）每个交换机有唯一的桥标识符（Brideg ID），由桥优先级和 MAC 地址组成； （3）每个交换机的端口有唯一的端口标识符（Port ID），由端口优先级和端口号组成； （4）对生成树的配置时，对每个交换机配置一个相对的优先级，对每个交换机的每个端口也配 置一个相对的优先级，该值越小优先级越高； （5）具有最高优先级的交换机被称为根桥（Root Bridge），如果所有设备都具有相同的优先级， 则具有最低 MAC 地址的设备将成为根桥； （6）网络中每个交换机端口都有一个根路径开销（Root Path Cost），根路径开销是某交换机到 根桥所经过的路径开销（与链路带宽有关）的总和； （7）根端口是各个交换机通往根桥的根路径开销最低的端口，若有多个端口具有相同的根路径 开销，则端口标识符小的端口为根端口； （8）在每个 LAN 中都有一个交换机被称为指定交换机（Designated Bridge），它是该 LAN 中与 根桥连接而且根路径开销最低的交换机； （9）指定交换机和 LAN 连接的端口被称为指定端口（Designated Port）。如果指定桥中有两个 以上的端口连在这个 LAN 上，则具有最高优先级的端口被选为指定端口。根桥上的端口都可以成为
黄冈师范学院 提高型实验报告 实验课题最小生成树的Prim算法 （实验类型：□综合性■设计性□应用性） 实验课程算法程序设计 实验时间 2010年12月24日 学生姓名周媛鑫 专业班级计科 0801 学号 200826140110
一．实验目的和要求 （1）根据算法设计需要, 掌握连通网的灵活表示方法; （2）掌握最小生成树的Prim算法; （3）熟练掌握贪心算法的设计方法; 二．实验条件 （1）硬件环境：实验室电脑一台 （2）软件环境：winTC 三．实验原理分析 （1）最小生成树的定义： 假设一个单位要在n个办公地点之间建立通信网，则连通n个地点只需要n-1条线路。可以用连通的无向网来表示n个地点以及它们之间可能设置的通信线路，其中网的顶点表示城市，边表示两地间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以表示一个通信网。其中一棵使总的耗费最少，即边的权值之和最小的生成树，称为最小生成树。 （2）构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为MST的性质：假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一棵包含边 (u.v)的最小生成树。 （3）普里姆（Prim）算法即是利用MST性质构造最小生成树的算法。算法思想如下： 假设N=(V,{E})和是连通网，TE是N上最小生成树中边的集合。算法从U={u0}( u0∈V)，TE={}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u, v) ∈E 中找一条代价最小的边(u0, v0)并入集合TE，同时v0并入U，直到U=V为止。此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。 四．实验步骤 （1）数据结构的设计： 采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作： 邻接矩阵的抽象数据结构定义： #define INFINITY INT_MAX //最大值 #define MAX_ERTEX_NUM 20 //最大顶点数 typedef enum {DG,DN,UDG,UDN}GraphKind;//{有向图,有向网，无向网，无向图} typedef struct Arc Cell{ VRType adj ; // VRType 是顶点关系的类型。对无权图用1和0表示相邻否；InfoType * info; //该弧相关信息的指针 }ArcCell ，AdjMatrix [ MAX_VERTEX_NUM][MAX_VERTEX_NUM]； Typedef struct { VertexType vexs [ MAX_VERTEX_NUM] ; //顶点向量
实验五最小生成树 一、需求分析 1、本程序の目の是要建设一个最经济の网，，输出相应の最小生成树。在这里都用整型数来代替。 2、测试数据 见下程序。 二、概要设计 主程序： int main() { 初始化； while (条件) { 接受命令; 处理命令; } return 0; } 三、详细设计 #include
{ char adjvex; int lowcost; }Close,close[MAX_VERTEX_NUM]; typedef struct ArcNode { int adjvex; ArcNode *nextarc; int info; }ArcNode; typedef struct VNode { char data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList verties; int vexnum,arcnum; }ALGraph; ALGraph G;//对象G int LocateVek(ALGraph ,char );//返回结点位置 int minimum(close);//返回最小数 void MinSpanTree_PRIM(ALGraph,char);//最小生成树 void Create(ALGraph &);//创建邻接表 int main() { char a;int i=1; Create(G); /*for(int i=1;i<=G.vexnum;i++) { for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc) cout<
实验3：交换机端口配置与生成树协议配 置
实验三：交换机端口配置与生成树协议配置 一、实验目的 掌握Quidway系列以太网交换机端口常见配置命令的使用方法、重点掌握端口聚合的配置命令的使用方法；掌握STP协议基本配置，通过改变交换机参数来改变生成树结构，从而进一步加深对STP协议的理解。 二、实验原理和内容 1、交换机的基本工作原理 2、配置交换机的方法和命令 3、STP的基本原理及配置 三、实验环境以及设备 环境一：2台交换机、2台Pc机、双绞线若干 环境二：4台交换机、2台Pc机、双绞线若干 四、实验步骤（操作方法及思考题） 0、在作实验前，请在用户视图下使用“reset saved-configuration”命令和“reboot” 命令分别将2台交换机的配置都清空，以免前一个班的实验留下的配置对本次实验产生影响。 1、请任选一台交换机，练习使用如下端口配置或显示命令，请把它们的语法和 功能写到实验报告中。 （1）description（1分） （2）duplex（1分） （3）speed（1分）
（4）flow-control（1分） （5）display interface（1分） 答：对以太网端口进行必要的描述：[Quidway-Ethernet0/1]description <任意词> 端口工作模式配置：[Quidway-Ethernet0/1] duplex { full | half | auto} 端口速率配置：[Quidway-Ethernet0/1] speed { 10 | 100 | 1000 | auto } 流量控制配置：[Quidway-Ethernet0/1] flow-control [Quidway-Ethernet0/1] undo flow-control 显示端口配置信息：[任意视图] display interface ethernet0/1 2、链路聚合配置： ?Skip Record If...? 图1：链路聚合配置 （1）请采用2台交换机组网，交换机之间通过3条双绞线互连，网络环境如图1所示（注：E0/1即为 Ethernet0/1端口,在39或36系列的交 换机上，是E1/0/1端口）。请分别在两台交换机上输入必要的命 令，实现三条链路的聚合。请把你所输入的命令写到实验报告中。 （两台交 （2）换机上的命令都要写）（10分） 答：SwitchA： SwitchB： [Quidway]sysname SwitchA [Quidway]sysname SwitchB [SwitchA]interface ethernet0/1 [SwitchB]interface ethernet0/1 [SwitchA -Ethernet0/1] duplex full [SwitchB -Ethernet0/1] duplex full [SwitchA -Ethernet0/1] speed 100 [SwitchB -Ethernet0/1] speed 100 [SwitchA-Ethernet0/1]return [SwitchA-Ethernet0/1]return
附件2： 北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 班级学号姓名指导教师成绩实验题目生成树协议故障排除实验时间 拓扑图 地址表
端口分配－ S2 学习目标 ?观察所有中继的初始状态 ?更正存在的错误 ?记录交换机配置 场景 拓扑图所示的冗余交换 LAN 由您负责维护。您和您的用户发现在网络高峰期延时会变长，经过分析，您怀疑是中继拥塞所致。您发现在所配置的六条中继中，只有两条在当前运行的默认 STP 配置中转发数据包。要解决此问题，就需要提高对可用中继的使用率。 任务1：观察所有中继的初始状态 在每台交换机上，使用show spanning-tree命令列出其上的生成树表。注意观察每台交换机上的转发端口，找出在默认配置中哪些中继没有被使用。您可以使用网络拓扑图来记录所有中继端口的初始状态。 任务2：更正存在的错误 修改生成树配置，使所有三条中继都能用上。假设三个用户LAN（10、20 和30）承载等量的流量。尝试找出一个解决方案，使三个用户VLAN 中的每一个都使用不同的一组端口进行转发。 要使本次练习得到正确评分，您必须满足以下条件： ?S1 成为VLAN 10 的根桥（优先级4096）、VLAN 20 的备用根桥（优先级16384）?S2 成为VLAN 20 的根桥（优先级4096）、VLAN 30 的备用根桥（优先级16384）?S3 成为VLAN 30 的根桥（优先级4096）、VLAN 10 的备用根桥（优先级16384） 任务3：记录交换机配置 实施完毕您的解决方案后，在每台交换机上捕获show run命令的输出并保存在文本文件中。
３６２ 《商场现代化》２００７年５月（中旬刊）总第５０３期 ３．进一步整理，形成报告。花了大量的人力、物力、财力收集到的情报若没有得到有效利用是最大的浪费。如何使自己的工作成果能有效地被相关部门与人员充分地利用也是情报人员值得思考的问题。从已有的经验来看，情报部门的工作成果一般以两种方式发挥作用：一种是情报“硬产品”类，情报通讯（针对若干专题的定期资料简报）、专题情报报告（一般由情报人员与研究分析人员共同完成）及其有关资料库是一般情报部门反映其工作成果最直接的方式。其优点是其资料直观、系统、有条理，易于把握；不足之处在于其工作周期一般较长，情报需求方难于控制其工作的进度与方向，容易产生偏差。第二种是情报服务类，情报服务是情报部门使其工作成果发生效益的一种高级形式，它往往需要情报部门与人力、行政部门紧密配合，针对某些专题组织专项的培训、在公司内部局域网上进行互动式的讨论等。这种方式的优点是针对性强、信息量大且可针对实际效果及时做出调整；不足之处在于，这类服务对情报部门的综合素质及与其他部门的协同能力要求较高，要搞好有一定难度。 四、情报收集整理过程中的反情报工作问题 我们对竞争对手开展情报工作，自然也要防备竞争对手对我方开展情报工作。开展反情报工作同样是企业竞争性情报收集与整理过程中的重要工作，可以说贯穿整个竞争性情报的收集整理过程。 １．反情报工作的程序。首先要明确任务，情报人员要明确自己企业确定的须保护的情报范围、内容以及主要防范的竞争对手。其次要对竞争对手的情报收集能力进行评估，包括其情报收集方式、手段和主要情报源等，然后有针对性地加强这些方面地防范措施。第三企业还要及时进行自我评估，随时发现需要加强保护的薄弱环节。最后，根据上述的分析结果实施具体的保密措施并根据实施效果做出形影的反馈与调整。 ２．开展反情报工作的一般方法。堵漏法是最常见的办法，其核心就是找到各种可能泄露保密资讯的渠道并塞住它。一般来说，常见的泄密渠道有：媒体对于某些问题的深度采访，向政府及专业机构、团体提交、披露的有关档案、报告，技术与营销人员的专业论文、公司领导涉及过多细节的演讲，对预有图谋的外来参观人员疏于管理，对关联单位可获得的有关资讯缺乏追踪，心怀不满或易于收买的离职与在职员工，管理不严的公司档案与电脑资料等。隐真示假法属于障眼法，情报工作是花费人力、物力、财力都很大的一项工作，如果能使竞争对手的情报部门在一些无意义或虚假的资讯中纠缠不休，事实上也就保护了本企业方敏感的重要的资讯。所以，在对方有明显不道德行为的前提下，情报人员也可以以适时、适当散布假情报──用“以其人之道还制其人之身”的方式加以反击。 总之，企业要想在复杂与动荡的环境中立稳脚跟，就必须全面准确地了解与本企业、本行业有关的竞争性情报，只有对其做出积极正确的反应，企业才能求得更好的生存与发展。 参考文献： ［１］郑 刚：企业竞争性情报．财经天空，ｈｔｔｐ：／／ｗｗｗ．ｃａｉｊ．ｃｎ／ｇｕａｎｌｉ／ｄａｑｕａｎ／ｚｌ／２００６０３／１５８９．ｈｔｍｌ［２００７－０３－２２］ ［２］刘西友：强化我国企业竞争性情报工作的对策．中国乡镇企业会计，２００６（５）：２２－２３ ［３］高 慧 黎 慧：论企业竞争情报源及其搜集方法．现代情报，２００２（１）：８８－８９ 由于生成树协议本身比较小，所以并不像路由协议那样广为人知。但是它却掌管着端口的转发和开关的大权。在和别的协议一起运行的时候生成树就有可能切断其他协议报文通路，造成种种奇怪的现象。生成树协议和其他协议一样是随着网络的不断发展而不断更新换代的。总的来说可以分成以下三代生成树协议。 一、第一代生成树协议ＳＴＰ和ＲＳＴＰ１．Ｓｐａｎｎｉｎｇ Ｔｒｅｅ Ｐｒｏｔｏｃｏｌ 以太网络发展初期，透明网桥是一个不得不提的重要功能。它比只会放大和广播信号的ＨＵＢ功能强大很多。它能把发向它的数据帧的源ＭＡＣ和端口记录下来，下次如果再遇到这个目的ＭＡＣ的帧就只从记录中的端口号发送出去，可以加快处理帧的速度。除非目的ＭＡＣ没有记录或者目的ＭＡＣ就是多播地址才会向所有端口发送。通过透明网桥不同的局域网之间可以互相通讯，而且由于具备ＭＡＣ地址学习功能，不会像ＨＵＢ那样造成网络流量的碰撞，但是透明网桥也有它的不足之处，就是透明网桥并不能像路由器那样知道数据帧可以经过多少次转发，一旦网络存在环路就会造成数据帧在环路内不断循环和增生甚至造成广播风暴，导致网络不可用。另外由于在大型网络中不好定位，所以广播风暴是二层网络灾难性的故障。 在这种环境下产生的生成树协议很好地解决了这一问题，生成树协议的基本思想十分简单。因为自然界中生长的树是不会出现环路的，所以如果网络也能够像一棵树那样生长就永远不会出现环路。因此生成树协议定义了以下一些概念。 根桥 Ｒｏｏｔ Ｂｒｉｄｇｅ 根端口 Ｒｏｏｔ Ｐｏｒｔ 指定端口 Ｄｅｓｉｇｎａｔｅｄ Ｐｏｒｔ 路径开销 Ｐａｔｈ Ｃｏｓｔ 定义这些概念的目的就在于通过构造一棵自然树的方法达到 生成树协议的 发展历程浅析 吴 君 湖北省消防总队 ［摘 要］ 生成树协议（ＳＴＰ，Ｓｐａｎｎｉｎｇ Ｔｒｅｅ Ｐｒｏｔｏｃｏｌ）作为目前交换式以太网的基础技术，已经使用了很长时间，其协议本身也跟随以太网不断的发展而更新，从最开始的ＳＴＰ到现在的ＭＳＴＰ，本文从生成树的协议入手，简单分析了历代生成树协议的特点，并进行比较，希望让读者能够对生成树协议有一个直观的了解。 ［关键词］ 交换网络 生成树 协议
算法分析与设计之Prim 学院：软件学院学号：201421031059 ：吕吕 一、问题描述 1.Prim的定义 Prim算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。 2.实验目的 选择一门编程语言，根据Prim算法实现最小生成树，并打印最小生成树权值。 二、算法分析与设计 1.Prim算法的实现过程 基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U ＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作： 在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。 此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。 Prim算法的核心:始终保持TE中的边集构成一棵生成树。 2.时间复杂度 Prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，N 为顶点数，而看ruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。 三、数据结构的设计 图采用类存储，定义如下： class Graph { private: int *VerticesList; int **Edge; int numVertices; int numEdges; int maxVertices; public: Graph(); ~Graph(); bool insertVertex(const int vertex); bool insertEdge(int v1,int v2,int cost); int getVertexPos(int vertex); int getValue(int i); int getWeight(int v1,int v2); int NumberOfVertices();
实验八生成树配置——生成树协议 一、实验名称 生成树协议STP 二、实验目的 理解生成树协议STP的配置及原理。 三、实验步骤 1、在每台交换机上开启生成树协议．例如对SwitchA做如下配置： SwitchA#configure terminal //进入全局配置模式 SwitchA(config)#spanning-tree //开启生成树协议 SwitchA(config)#end 验证测试：验证生成树协议已经开启 SwitchA#show spanning-tree //显示交换机生成树的状态
SwitchA#show spanning-tree interface fastthernet 0/1 //显示交换机接口fastthernet 0/1的状态 2、设置生成树模式 SwitchA(config)#spanning-tree mode stp //设置生成树模式为STP (802.1D) 验证测试：验证生成树协模式为802.1D SwitchA#show spanning-tree 3、设置交换机的优先级
SwitchA(config)#spanning-tree priority 4096 //设置交换机SwitchA的优先级为4096 验证测试：验证交换机SwitchA的优先级 SwitchA#show spanning-tree 4、综合验证测试 1、验证交换机SwitchB的端口F0/1和F0/1的状态 SwitchB#show spanning-tree interface fastEthernet 0/1 //显示SwitchB的端口fastthernet 0/1的状态
1，交换机的好处，和交换机所带来的问题，就是产生环路。 交换机能够扩大网络直径，能让更多的网络直径参与到网络通信中来，但是交换机同时也带来了一个问题，就是会产生环路。 2，环路是如何产生的？ 交换机基本工作原理是，通过学习维护一个mac和端口对应的表格，交换机只对报文进行透传，不会像路由器那样，对报文添加标记，根据局域网的工作原理，这样就必然会导致环路的产生。如下图例子： 如上图，我们假定终端A是第一次发消息，发出一个消息1发给B，根据局域网的工作原理，该消息会被交换机S1 S2 S3收到，S1透传出消息1，发给终端B，同时也会给该消息发给S2 S3，依次类推，在网络中形成的环路的信息会急剧的增加，迅速将网络堵死。 3，生成树协议概念的产生，生成树是如何避免环路的？ 802标准委员会，为了解决这个问题，提出了STP协议生成树的概念。 生成树就是通过将一个物理上有环存在的网络中，通过逻辑上阻塞某些端口，将网络中存在的环拆解开，使整个网络在逻辑上是一种树状结构，并保证其数据传输的效率。 对上图的说明：图中的每个矩形代表一个网桥，深颜色矩形为跟桥，也就是一棵树的根。深
色端口为阻塞端口，也就是被生成树协议，根据一定的算法，所阻塞掉的端口。这样我们可以从这科树的根出发，走实线的路径，那么我们可以清晰的看到是一棵树的形状，这棵树没有环路。 4，介绍STP。bpdu包结构。其中各个字段的含义。 生成树的基本原理， 1，选择跟桥，在参与本局域网通信的所有网桥中，选择一个网桥作为根网桥，也就是树的根。 2，选择根端口，根端口就是某一网桥通过该端口到达根网桥，路径开销最小。 3，选择指定端口，端口优先级向量劣于根优先级向量的端口。 生成树实现这一机制是通过相互发送BPDU消息来实现的，BPDU中携带一些生成树计算所需要的必要信息。如下BPDU格式：
算法与数据结构 实验报告 系（院）：计算机科学学院 专业班级：软工11102 姓名：潘香杰 学号： 201104449 班级序号： 18 指导教师：詹泽梅老师 实验时间：2013.6.17 - 2013.6.29 实验地点：4号楼5楼机房
目录 1、课程设计目的．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 2、设计任务．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 3、设计方案．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 4、实现过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 5、测试．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 6、使用说明．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 7、难点与收获．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8、实现代码．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 9、可改进的地方．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．
算法与数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力，进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储结构及算法，并编写出结构清楚且正确易读的程序，提高程序设计基本技能和技巧。 一．设计目的 1．提高数据抽象能力。根据实际问题，能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构，并设计出有效解决问题的算法。 2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3．初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。二．设计任务 设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下： ①创建无向图的邻接表 ②无向图的深度优先遍历 ③无向创建无向图的邻接矩阵 ④无向图的基本操作及应用 ⑤图的广度优先遍历 1．有向图的基本操作及应用 ①创建有向图的邻接矩阵 ②创建有向图的邻接表 ③拓扑排序 2．无向网的基本操作及应用 ①创建无向网的邻接矩阵 ②创建无向网的邻接表 ③求最小生成树 3．有向网的基本操作及应用 ①创建有向网的邻接矩阵 ②创建有向网的邻接表 ③关键路径 ④单源最短路径 三．设计方案 第一步：根据设计任务，设计DOS菜单，菜单运行成果如图所示：
0分计。 4. 实验报告文件以PDF 格式提交。 【实验题目】生成树协议 【实验目的】理解快速生成树协议的配置及原理。使网络在有冗余链路的情况下避免环路的产生，避免广播风暴等。 【实验内容】 (1)完成实验教程实例3-8的实验，回答实验提出的问题及实验思考。（P117） (2)抓取生成树协议数据包，分析桥协议数据单元（BPDU ）。 (3)在实验设备上查看VLAN 生成树，并学会查看其它相关重要信息。 【实验要求】 一些重要信息需给出截图。 注意实验步骤的前后对比！ 【实验记录】(如有实验拓扑请自行画出, 要求自行画出拓扑图) (1) 实例3-8 实验拓扑图如下：
步骤0： 将PC1和PC2配置好IP地址和掩码后按照拓扑图连接实验设备。 在PC1上启动Wireshark 软件观察包的数量变化如下： 此时已经产生了广播风暴。 两台交换机此时的生成树配置信息如下： 无生成树配置信息。 用PC1pingPC2时包增长情况如下：
可见此时包增长的更快，已经产生广播风暴，但是PC并未发生死锁。步骤1： 配置交换机A： 步骤2： 配置交换机B： 步骤3: 配置两交换机的快速生成树协议：
再按照拓扑图连接实验设备，此时包增长情况如下： 此时两PC间可以相互ping通，且无广播风暴。由此可见生成树协议的作用为避免网络中存在交换环路的时候产生广播风暴，确保在网络中有环路时自动切断环路。
步骤4：验证测试 SwitchA的生成树信息： SwitchB的生成树信息：
步骤5：设置交换机的优先级 将SwitchA的优先级设置为4096 步骤6: 验证SwitchA的优先级 当两个端口都连在一个共享介质上，交换机会选择一个高优先级的端口进入
惠州学院《计算机网络》实验报告 实验三生成树的协议配置 一．实验目的 在掌握环路产生的原因及危害性的基础上，学习STP的功能、原理及配置方法，从而了解利用冗余链路来提高网络安全性和可靠性的相关技术。 二．实验环境 1.交换机2台，二层三层均可，本实验使用的是二层交换机 2.实验用PC机2台 3.Console电缆2根 4.直连双绞线2根 5.交叉双绞线2根 三．实验内容和要求 （1）掌握链路冗余的重要性。 （2）了解广播风暴对网络性能造成的影响。 （3）掌握STP、RSTP和MSTP的概念以及相互之间的区别。 （4）学习生成树协议的配置方法。 四．网络拓扑图 五、实验步骤 生成树协议在部分交换机（如思科）上是自动打开的，管理员不需要进行配置。但在一些交换机（如锐捷）上默认是关闭的，如果网络中存在环路，则必须手动开启。根据如上的拓扑图，具体配置如下： 1.在交换机A上创建一个VLAN，然后将与PC1连接的端口添加到VLAN 10中。同时，将用于交换机之间连接的两个端口设置为tag模式。 Switch-A#configure terminal Switch-A(config)#vlan 10
Switch-A(config-vlan)#name test Switch-A(config-vlan)#exit Switch-A(config)#interface FastEthernet 0/6 Switch-A(config-if)#switchport access vlan 10 Switch-A(config-if)#end Switch-A(config)#interface FastEthernet 0/3 Switch-A(config-if)#Switchport mode trunk Switch-A(config-if)#exit Switch-A(config)#interface FastEthernet 0/4 Switch-A(config-if)#Switchport mode trunk Switch-A(config-if)#end 2.在交换机B上创建一个VLAN，然后将与PC2连接的端口添加到VLAN 10中。同时，将用于交换机之间连接的两个端口设置为tag模式。 Switch-B#configure terminal Switch-B(config)#vlan 10 Switch-B(config-vlan)#name test Switch-B(config-vlan)#exit Switch-B(config)#interface FastEthernet 0/6 Switch-B(config-if)#switchport access vlan 10 Switch-B(config-if)#end Switch-B(config)#interface FastEthernet 0/3 Switch-B(config-if)#Switchport mode trunk Switch-B(config-if)#exit Switch-B(config)#interface FastEthernet 0/4 Switch-B(config-if)#Switchport mode trunk Switch-B(config-if)#end 3.如果该交换机没有启用生成树协议，则分别在A和B交换机上启用相应的协议，以免产生环路。Cisco交换机开启生成树协议的命令为：spanning-tree vlan 1 Switch-A(config)#spanning-tree vlan 1 Switch-B(config)#spanning-tree vlan 1 锐捷交换机开启生成树协议的命令为：spanning-tree mode rstp 六、实验截图
生成树协议试验范例分析 目录 生成树协议试验范例 (1) 1. 验证内容： (1) 2 试验环境： (1) 3 测试前准备： (3) 4试验过程： (6) 4.1.单独接入： (6) 4.2.基站逐步串接回环： (7) 4.3.66下挂111，使用光模块连接： (8) 4.4.电口向下接入基站31的port1口 (12) 4.5.31基站通port2接交换机，形成环 (16) 4.6.断开port2，66光口恢复 (20) 1.验证内容： 生成树的主要功能，切断阻断冗余拓扑环路，形成树形结构。拓扑改变时阻断能够恢复，避免影响通信。 生成树的工作步骤，选举根桥，确定根端口，指定端口，阻断端口。Tcn发出，阻断端口。拓扑改变时，恢复阻断端口通信。 生成树根据bpdu进行计算的过程。 拓扑改变时，tcn发出，tca的应答，tc+root拓扑改变的发出。 验证端口状态的变化和各定时器大小。 2试验环境： 三个具有生成树协议的基站，一个交换机，一台pc，一个usb转串口。 Ip和mac地址：
基站31,18.250.0.31 00:0e:5e:18:9a:9d 可提供2个fe接口和两个10m光接口。 基站111,18.250.0.111, 00:0e:5e:18:9b:5f,提供一个fe接口，两个10m光接口 基站66,18.250.0.66,00:15:e1:00:04:7c，提供一个fe接口，两个10m光接口 基站上有一个6口的交换芯片，所以相当于交换机相连。交换机是一个没有生成树协议的设备，对bpdu消息当做普通包处理。Putty接基站串口进行基站打印进行跟踪。
实验五 实验名称： 得到最小生成树 实验目的： 1.熟悉地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。 2.掌握图论中的最小生成树及Prim 和 Kruskal 算法等，进一步能用它们来解决实际问题。 实验内容： 输入一个图的权矩阵，得到该图的生成树，用Kruskal算法的最小生成树，用Prim算法的最小生成树。
Kruskal算法 假设T中的边和顶点均涂成红色，其余边为白色。开始时G中的边均为白色。 1）将所有顶点涂成红色； 2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红； 3）重复2）直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合。 Prim算法 假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树: 1)初始化:U={u 0},TE={f}。此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。 2)在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U 中,其次边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。 3)如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。