07_生成树实验
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的优先级
当两个端口都连在一个共享介质上，交换机会选择一个高优先级的端口进入
步骤7：验证交换机SwitchB的G0/1，G0/2，端口的状态
由上图可知，SwitchB的G0/1端口处于转发状态，G0/2端口处于组阻塞状态。
步骤8：
步骤7后每个交换机的信息如下：
两交换机G0/1端口链路down之后SwitchB的端口2信息如下：
此时每个交换机的信息：
与之前相比，SwitchB的RootPort变为G0/2,其他均未变化。说明一条链路down 之后，生成树协议启用了备用端口使得整个链路恢复数据传输。
SwitchA和SwitchB之间的一条链路down掉时，PC1和PC2仍然能相互ping通，但会丢包：
说明生成树在链路断掉后重新构筑，原先阻塞的链路已经变为转发状态，一个端口断开时会将流量切换到另一个端口上，中间有短暂的联路中段，丢包数为一个。
此时每个交换机的生成树信息如下：
与步骤8的（1）相比，SwitchB的根端口变为G0/2，转换时间大约为2秒。
实验思考
1）在实验开始产生广播风暴时，实验设备中存在环路，在生成树协议开启后不在存在环路，因为广播风暴现象已经消除。
2）冗余链路会引起MAC地址表不稳定和多帧复制等问题。
MAC表不稳定
当PC1发送数据到PC2时，如果Switch A和Switch B也是刚刚启动，这时候它们MAC表里都没有PC2的MAC地址
收到数据包后，Switch A就会广播该数据包，并把源MAC添加到MAC表，然后认为PC1在端口0
收到数据包后，Switch B就会广播该数据包，并把源MAC添加到MAC表，然后认为PC1在端口0
当Switch B在收到Switch A的广播包后又认为PC1在端口1
当Switch A在收到Switch B的广播包后又认为PC1在端口1
这时就会造成交换机MAC表的不稳定
多帧复制
在冗余链路中出现广播风暴后，当PC1向PC2发送数据报时，如果两个交换机刚刚启动，这时候它们的MAC地址表里都没有PC2的MAC地址，SwitchA将会广播该数据包，SwitchB收到SwichA的广播包之后发现自己的MAC地址表里也没有PC2的MAC地址，就会继续广播该数据包，如此循环PC2就会收到多个同样的数据包造成多帧复制。
(2)分析生成树协议数据包
STP协议传输过程中wireshark捕获到的STP数据包如下：
具体信息如下（frame1）：
具体信息：
DMA 01:80:v2:00:00:00
SMA 58:69:6c:15:57:36
L/T 39
LLC Header
Payload信息如下：
具体信息如下：
协议号 0x0000
版本号 2
报文类型 0x02
标记 0x7c
根网桥号 4096/58:69:6c:15:57:36 根路径成本 0
发送网桥ID 4096/58:69:6c:15:57:36
端口ID 0x8003
呼叫时间 2s
转发延迟 15s
(3)VLAN生成树其它相关重要信息
全部实验步骤结束后的交换机生成树配置信息如下：
Switch A：
STP版本 RSTP
STP协议运行状态运行
最大生存时间 20
呼叫时间 2s
转发延迟 15s
网桥最大生存时间 20
网桥呼叫时间 2s
网桥转发延迟 15s
最大跳转次数 20
路径成本模式长
BPDUGuard 未运行
BPDUFilter 未运行
LoopGuardDef 未运行
网桥地址 5869.6c15.5736
优先级 4096
拓扑结构变动时间 1分4秒
拓扑结构变动数 3
指派端口 4096.5869.6c15.5736
根路径成本 0（本交换机为根）
根端口 0（本交换机为根）
Switch B
STP版本 RSTP
STP协议运行状态运行
最大生存时间 20
呼叫时间 2s
转发延迟 15s
网桥最大生存时间 20
网桥呼叫时间 2s
网桥转发延迟 15s
最大跳转次数 20
路径成本模式长
BPDUGuard 未运行
BPDUFilter 未运行
LoopGuardDef 未运行
网桥地址 5869.6c15.5730
优先级 32768
拓扑结构变动时间 46秒
拓扑结构变动数 6
指派端口 4096.5869.6c15.5736
根路径成本 20000
根端口 Gi0/2
交换机的端口状态：
Gi0/1：
默认端口加速不可用
操作端口加速不可用
自动配置默认端口不可用
自动配置操作端口不可用
默认连接类型自动
操作连接类型点对点
BPDUGuard 未运行
BPDUFilter 未运行
端口监视模式无
端口状态转发状态
端口优先级 128
根指派端口 32768.5869.6c15.5730
指派成本 0
指派网桥 32768.5869.6c15.5730
指派端口优先级 128
指派端口号 1
转发跳转数 2
默认路径成本 20000
操作路径成本 20000
矛盾状态正常
Gi0/2
默认端口加速不可用
操作端口加速不可用
自动配置默认端口不可用
自动配置操作端口不可用
默认连接类型自动
操作连接类型点对点
BPDUGuard 未运行
BPDUFilter 未运行
端口监视模式无
端口状态阻塞状态
端口优先级 128
根指派端口 32768.5869.6c15.5730
指派成本 0
指派网桥 32768.5869.6c15.5730
指派端口优先级 128
指派端口号 2
转发跳转数 0
默认路径成本 20000
操作路径成本 20000
矛盾状态正常
端口角色替换端口
生成树的发展历程
生成树（STP）技术的部署与调试案例 8.1 生成树（STP）技术与实现原理 在一个包含有交换机与网桥的网络中，消除环路对于获得可靠通信与防止流量在网络中不停循环必不可少。生成树协议（Spanning-tree Protocol，STP），工作在ISO七层模型中第二层，其应用能够使交换机或者网桥通过构成“生成树”，在网络拓扑中动态执行“环路遍历”，通过逻辑判断网络的链路，达到网络无环路和链路冗余的目的。 8.1.1 生成树的发展历程 网络发展过程中，以太网设备由Hub发展到透明网桥到智能交换机。透明网桥比Hub 智能，Hub收到数据包后，向除自己外的其他所有端口进行广播，而透明网桥则记录物理端口上连接设备的MAC，收到数据帧后按照记录的MAC地址向该端口发送数据帧，这样大大减少数据帧冲突。 但是透明网桥由于他的透明性，一旦网络中存在环路，一台透明网桥收到的数据帧，又会在环路中返回，这样数据帧不停在网络中增生，最终形成广播风暴，导致整个网络瘫痪；一种阻止网络环路的协议——生成树协议（STP），IEEE 802.1D标准，生成树模拟自然界树的生长规律，从树根到树梢不会形成环路，生成树协议通过对比环路网络中的设备属性的优先级、链路的开销、端口优先级等来判断环路中链路的优先级，从而逻辑上阻断优先级低的网络链路。 生成树从阻断到转发状态需要经过阻断、监听、学习、转发延迟等阶段，这个阶段大约需要30~50s的时间，对于要求高可靠性的网络来，这是不允许的。快速生成树协议（RSTP）IEEE 802.1W按结构需求产生，RSTP将阻断的端口设置备用端口，一旦检测到主链路中断，备用端口直接进入转发状态，大大加大收敛速度。 上一章介绍了VLAN在园区网中的应用与划分，很多企业在网络中都会规划多个VLAN。STP和RSTP只支持一个VLAN，对于只有一个VLAN的网络非常适用，但现在网络中全部是多VLAN的结构，每VLAN生成树和多VLAN生成树协议被提上议程。其中，每VLAN生成树 PVST 为Cisco专有的协议，该协议不兼容其他厂家的生成树协议。同时，如果VLAN多的话，过多的生成树可能导致交换机CPU、内存过载，而IEEE 802.1S 制定的多生成树协议（MSTP）通过划分域的概念，解决了CPU过度运算的问题，同时向下兼容STP、RSTP协议。本章的后续案例将分别介绍各种生成树技术的应用。
最小生成树实验报告
数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 2011—2012年度第 2 学期 一、需求分析
1.问题描述： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。 二、概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={
07-生成树实验
1. 实验报告如有雷同，雷同各方当次实验成绩均以0分计。 2. 当次小组成员成绩只计学号、姓名登录在下表中的。 3. 在规定时间内未上交实验报告的，不得以其他方式补交，当次成绩按0分计。 4. 实验报告文件以PDF 格式提交。 【实验题目】生成树协议 【实验目的】理解快速生成树协议的配置及原理。使网络在有冗余链路的情况下避免环路的产生，避免广播风暴等。 【实验内容】 (1)完成实验教程实例3-8的实验，回答实验提出的问题及实验思考。（P117） (2)抓取生成树协议数据包，分析桥协议数据单元（BPDU ）。 (3)在实验设备上查看VLAN 生成树，并学会查看其它相关重要信息。 【实验要求】 一些重要信息需给出截图。 注意实验步骤的前后对比！ 【实验记录】(如有实验拓扑请自行画出, 要求自行画出拓扑图) (1) 实例3-8 实验拓扑图如下： 院系 班 级 组长 学号 学生 实验分工 陈 刘 3-8 、 宗良 警示
步骤0： 将PC1和PC2配置好IP地址和掩码后按照拓扑图连接实验设备。 在PC1上启动Wireshark 软件观察包的数量变化如下： 此时已经产生了广播风暴。 两台交换机此时的生成树配置信息如下： 无生成树配置信息。 用PC1pingPC2时包增长情况如下：
可见此时包增长的更快，已经产生广播风暴，但是PC并未发生死锁。步骤1： 配置交换机A： 步骤2： 配置交换机B： 步骤3: 配置两交换机的快速生成树协议：
再按照拓扑图连接实验设备，此时包增长情况如下： 此时两PC间可以相互ping通，且无广播风暴。由此可见生成树协议的作用为避免网络中存在交换环路的时候产生广播风暴，确保在网络中有环路时自动切断环路。
最小生成树的Prim算法提高型实验报告
黄冈师范学院 提高型实验报告 实验课题最小生成树的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<
07_生成树实验
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的优先级 当两个端口都连在一个共享介质上，交换机会选择一个高优先级的端口进入
Prim最小生成树算法实验报告材料
算法分析与设计之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();
实验报告
算法与数据结构 实验报告 系（院）：计算机科学学院 专业班级：软工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菜单，菜单运行成果如图所示：
生成树STP基本概念与实验
二层交换：生成树STP基本概念与实验 如果你把两台傻瓜式交换机之间连两根网线，那么这俩交换机就会出现环路从而产生广播风暴。 可能你会觉得好笑，但实际工作中，我却碰到了，一些不懂网络的装修包工头，就会这样做。 ==================================================================== 生成树就是为了让交换网络中防环而出现的。 生成树最原始的版本是802.1d，也就是STP（Spanning Tree Protocol）， 但这个版本的标准是所有VLAN共用一个生成树，所以也叫CST（Common Spanning Tree） 思科在此基础上增强了一下，发布了PVST+（Per Vlan Spanning Tree） 802.1d的下一个版本是802.1w，也就是RSTP（Rapid STP），但还是共用生成树，搞不懂IEEE不长点记性。 于是思科又搞了一下，发布了PVRST+ IEEE又基于思科的MISTP的方案，发布了802.1s（MSTP），这个就屌爆了，之后再说为何这么屌，凡是大一点的交换网络都用MSTP。 ===================================================================== STP的基础 要学习更高级的RSTP/MST，还是需要STP的基础，尽管现在已经很少用到STP。 STP的工作流程
1. 在整个交换网段里选择一台做根桥，这根桥就是整棵树的根部，所有其他交换机就选一条到这个根桥的最短路径，其余的路径阻塞掉。所有交换机中桥优先级最低的成为根桥。 2. 选择所有非根桥交换机的根端口，就是那条最短路径的接口。如果有超过1条等价路径，则选择对端指定端口优先级最低的本地端口（有点绕口，通过实验来说明） 3. 选择各网段的指定端口。这个网段其实就是指一根链接，其中一头一定是指定端口，另外一头可能是根端口，也可能是非指定端口。 根端口——只出现在非根桥交换机上，就是到达根桥最短路径的那个接口。如下图，SW1被设置较低的桥优先级成为了根桥，注意，根桥上是没有根端口的。根端口转发数据帧。 指定端口（和非指定端口）——所有交换机上都可能有，根桥上的所有端口都是指定端口（接终端的那些不算啊），非根桥之间的指定端口通过判断优先级，谁低谁是指定端口，对端是非指定端口或根端口，非指定端口禁止转发数据帧，不过仍会监听BPDU。 如下图，SW1上的接口都是指定端口，SW2/3上离根桥最短路径的端口就是根端口。而SW2<->SW3之间的链路，记住，一条链接上一定有一头是指定端口，另外一头如果不是根端口，那就一定是非指定端口。那哪边是指定端口呢？哪边的桥优先级更低，哪边就是指定端口。而SW3上非指定端口被阻塞了，所以SW2<->SW3之间的链路其实是被阻塞了不能用于转发数据。
数据结构课程设计报告(最小生成树完整版)
武 夷 学 院 课程设计报告 课程名称： 数据结构 设计题目： 最小生成树的应用 学生班级： 09计科2班 学生姓名： 蒋家权，陈相财，吴继伟，梁丽春 指导教师： 林丽惠 完成日期： 2011-1-19
课程设计项目研究报告 目录 一、问题分析和任务定义....................................................................................... - 1 - 二、实现本程序需要解决的问题如下................................................................... - 1 - 三、测试数据........................................................................................................... - 2 - 四、算法思想........................................................................................................... - 3 - 五、模块划分........................................................................................................... - 4 - 六、算法设计与分析............................................................................................... - 7 - 七、源程序............................................................................................................. - 11 - 八、测试数据......................................................................................................... - 14 - 九、课程设计项目进度表及任务分配表及任务分配表..................................... - 16 - 十、设计心得......................................................................................................... - 17 -十、参考书目......................................................................................................... - 18 -
神州数码生成树实验
实验二十一、生成树实验 一、实验目的 1、了解生成树协议的作用。 2、熟悉生成树协议的配置。 二、应用环境 交换机之间具有冗余链路本来是一件很好的事情，但是它有可能引起的问题比它能够解决的问题还要多。如果你真的准备两条以上的路，就必然形成了一个环路，交换机并不知道如何处理环路，只是周而复始地转发帧，形成一个“死循环”，这个死循环会造成整个网络处于阻塞状态，导致网络瘫痪。 采用生成树协议可以避免环路。 生成树协议的根本目的是将一个存在物理环路的交换网络变成一个没有环路的逻辑树形网络。IEEE802.1d 协议通过在交换机上运行一套复杂的算法STA（spanning-tree algorithm），使冗余端口置于“阻断状态”，使得接入网络的计算机在与其他计算机通讯时，只有一条链路生效，而当这个链路出现故障无法使用时，IEEE802.1d 协议会重新计算网络链路，将处于“阻断状态”的端口重新打开，从而既保障了网络正常运转，又保证了冗余能力。 三、实验设备 1、DCS-3926S 交换机2 台 2、PC 机2 台 3、Console 线1-2 根 4、直通网线 4-8 根 四、实验拓扑 五、实验要求 IP 地址设置：
如果生成树成功，则PC1 可以ping 通PC2。 六、实验步骤 第一步：正确连接网线，恢复出厂设置之后，做初始配置 交换机A： switch#config switch(Config)#hostname switchA switchA(Config)#interface vlan 1 switchA(Config-If-Vlan1)#ip address 10.1.157.100 255.255.255.0 switchA(Config-If-Vlan1)#no shutdown switchA(Config-If-Vlan1)#exit switchA(Config)# 交换机B： switch#config switch(Config)#hostname switchB switchB(Config)#interface vlan 1 switchB(Config-If-Vlan1)#ip address 10.1.157.101 255.255.255.0 switchB(Config-If-Vlan1)#no shutdown switchB(Config-If-Vlan1)#exit switchB(Config)# 第二步：“PC1 ping PC2 –t ”观察现象 1、ping不通； 2、所有连接网线的端口的绿灯很频繁地闪烁，表明该端口收发数据量很大，已经 在交换机内部形成广播风暴。 第三步：在两台交换机中都使用启用生成树协议 switchA(Config)#spanning-tree mode stp
离散数学 最小生成树
实验五 实验名称： 得到最小生成树 实验目的： 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条边就是需要求出的最小生成树的边。
生成树实验
2.当次小组成员成绩只计学号、姓名登录在下表中的。 3.在规定时间内未上交实验报告的，不得以其他方式补交，当次成绩按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的生成树信息： SwitchB中RootCost和RootPort值都为0，因此SwitchB为根交换机。 根端口为G0/1。 步骤5：设置交换机的优先级 将SwitchA的优先级设置为4096 步骤6: 验证SwitchA的优先级 当两个端口都连在一个共享介质上，交换机会选择一个高优先级的端口进入forwarding状态，低优先级的端口进入discarding状态。 步骤7：验证交换机SwitchB的G0/1，G0/2，端口的状态 由上图可知，SwitchB的G0/1端口处于转发状态，G0/2端口处于组阻塞状态。 步骤8： 步骤7后每个交换机的信息如下： 两交换机G0/1端口链路down之后SwitchB的端口2信息如下：
生成树的详细配置及实验
STP及其优化实验拓扑图：
实验步骤： 1. 设置SW1，SW2，SW3主机名分别为Core1,Core2, ED-SW 2. 把Core1与Core2间的两条链路绑定成etherchannel2，并设置成Trunk mode Core1: interface range fa0/23 - 24 switchport trunk encapsulation dot1q //支持ISL及dot1Q的交换机必须设置trunk的封装协议。低端的C2950，C2960，C2918只支持dot1Q，无此命令。 switch mode trunk //接口设置为Trunk模式。 channel-group 2 mode on //接口加入Etherchannel2。 Creating a port-channel interface Port-channel 2 //系统提示自动创建port-channel2。 interface Port-channel2 // Port-channel2接口配置必须同物理接口一致。 switchport trunk encapsulation dot1q switchport mode trunk Core2: interface range fa0/23 - 24 switchport trunk encapsulation dot1q switch mode trunk channel-group 2 mode on Creating a port-channel interface Port-channel 2 interface Port-channel2 switchport trunk encapsulation dot1q switchport mode trunk 3.验证etherchannel设置 Core1#sh etherchannel summary //显示etherchannel的详细信息 Flags: D - down P - in port-channel I - stand-alone s - suspended H - Hot-standby (LACP only) R - Layer3 S - Layer2 U - in use f - failed to allocate aggregator u - unsuitable for bundling w - waiting to be aggregated d - default port Number of channel-groups in use: 1 //目前已经建好1个etherchannel。Number of aggregators: 1 Group Port-channel Protocol Ports ------+-------------+-----------+----------------------------------------------- 2 Po2(SU) - fa0/23(P) fa0/24(P) // S - Layer2 U - in use P - in port-channel
Packet Tracer 5.0实验(五) 快速生成树配置
二、实验背景 学校为了开展计算机教学和网络办公，建立了一个计算机教室和一个校办公区，这两处的计算机网络通过两台交换机互相连接组成内部校园网，为了提高网络的可靠性，作为网络管理员，你要用2条链路将交换机互连，现要求在交换机上做适当的配置，使网络避免环路。 三、技术原理 生成树协议(spanning-tree)，作用是在交换网络中提供冗余备份链路，并且解决交换网络中的环路问题； 生成树协议是利用SPA算法，在存在交换环路的网络中生成一个没有环路的树形网络。运用该算法将交换网络的冗余备份链路从逻辑上断开，当主链路出现故障时，能够自动的切换到备份链路，保证数据的正常转发； 生成树协议版本：STP、RSTP(快速生成树)、MSTP(多生成树协议)； 生成树协议的特点是收敛时间长，从主要链路出现故障到切换至备份链路需要50秒的时间； 快速生成树协议在生成树协议的基础上增加了两种端口角色：替换端口和备份端口，分别做为根端口和指定端口的冗余端口。当根端口或指定端口出现故障时，冗余端口不需要经过50秒的收敛时间，可以直接切换到替换端口或备份端口，从而实现RSTP协议小于1秒的快速收敛。 四、实验步骤
实验拓扑 默认情况下STP协议启用的，通过两台交换机之间传送BPDU协议数据单元，选出根交换机、根端口等，以便确定端口的转发状态。上图中标记为橙色的端口处于block堵塞状态。 设置RSTP 查看交换机 show spanning-tree 状态，了解根交换机和根端口情况； 通过更改交换机生成树的优先级spanning-tree vlan * priority 4096 可以变化根交换机的角色； S1: Switch>en Switch#conf t Enter configuration commands, one per line. End with CNTL/Z. Switch(config)#hostname S1 S1(config)#end S1# %SYS-5-CONFIG_I: Configured from console by console
生成树协议STP的应用实验1
实验四、生成树协议 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 上，则具有最高优先级的端口被选为指定端口。根桥上的端口都可以成为
STP是生成树的终极版解析
生成树协议（STP）是干嘛的？我告诉你是生成树的！没错，你听到这个答案瞬间懵逼了！ 实际工程中我们必须考虑的一个问题是链路和设备的冗余问题，就是下图sw1去sw2有两条路，如果我们只有一条路网络就存在风险，万一这唯一的一条路断掉怎么办？所以我们要做多条冗余链路，以确保网络的稳定和可靠！ 但是问题来了，冗余链路多了会产生环路，如下图。环路会造成网络二的广播风暴，单播帧复制和MAC地址表不稳定！ 哇！这么多问题咋解决呢！那就是今天的生成树协议帮我们解决环路问题，把环路去掉，生成树状的拓扑就可以了！所以啥是生成树，就是把环路去掉成为树状的策略就是生成树。 生成树类型有：STP、RSTP、MSTP，（思科的私有PVST） STP工作原理：（可以先把口诀记住） 1.选举一个根桥。
2.每个非根交换机选举一个根端口。 3.每个网段选举一个指定端口。 4.阻塞非根、非指定端口。 这些概念没基础的更是懵！！！说简单点就是这个环怎么变成树的！既然要去环变树，交换机之间要沟通，沟通就要数据报文交换信息，这个报文就是BPDU(Bridge Protocol Data Unit，网桥协议数据单元）报文，你就认为他是个传话的。注意这个传话的比较勤快，每2S发送一次报文。（又称hello时间）。 1.选举一个根桥。 第一步：先找一个树根，这个树根我们叫根交换机（由于历史遗留问题，交换机的前身是网桥），所以也叫根桥。 其实链路开启后，所有的交换机都认为自己是老大（根），咋办呢？肯定要比较比如谁的力气大，谁的个子高等。交换机比较啥呢，比较网桥的ID（bridge id）。桥ID由16位的桥优先级（Bridge Priority）和48位的MAC地址构成。在STP网络中，桥优先级是可以配置的，取值范围是0～65535，默认值为32768。优先级最高的设备（桥ID最小）会被选举为根桥。如果优先级相同，则会比较MAC地址，MAC地址越小则越优先。
最小生成树模型与实验
最小生成树模型与实验
第六章 最小生成树模型与实验 树是图论中的一个重要概念，由于树的模型简单而实用，它在企业管理、线路设计等方面都有很重要的应用。 §6.1树与树的性质 上章已讨论了图和树的简单基本性质。为使更清楚明了，现在使用实例来说明。 例6.1 已知有五个城市，要在它们之 间架设电话线，要求任何两个城市都可以互相 通话（允许通过其它城市），并且电话线的根 数最少。 用五个点54321,,,,v v v v v 代表五个城市，如果 在某两个城市之间架设电话线，则在相应的两个点之间联一条边，这样一个电话线网就可以用一个图来表示。为了任何两个城市都可以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图6.1的表达式满足要求的一个电话线网。 定义6.1 一个无圈的连通图称为树. 例6.2 某大学的组织机构如下所示: v 5v 4v 图
教务处 研究处 校行政办公室 研究生院 财务科 行政科 理工学院 人事学院 外语学院 …… 如果用图表示，该工厂的组织机构图就是一个树。上章给出了一些树的性质，为使能进一步研究这部分知识，先再列出常用一些树和生成树的性质。 树的性质： （1） 树必连通，但无回路（圈）； （2） n 个顶点的树必有1-n 条边； （3） 树中任意两点间，恰有一条初等链； （4） 树连通，但去掉任一条边，必变为不连通； （5） 树无回路（圈），但不相邻顶点连一条边，恰得一回路（圈）。 生成树与最小树 定义6.2 设图),(11E V G =是图},{E V G =的生成子图，如果1G 是一棵树，记),(1E V T =，则称T 是G 的一棵生成树。 定理6.1 图G 有生成树的充分必要条件是图G 的连通的。 数学物理文科 理校教学校长